Offline real-time how to write Python implementation example of E15 problem

Problem: http://nabetani.sakura.ne.jp/hena/orde15nohil/ Answer links: http://qiita.com/Nabetani/items/705fa83cfbf20377b92f Event: https://yhpg.doorkeeper.jp/events/61418

  1. Set "Number" to "3rd digit" and create a digit string for each number range that makes up a set of NxN blocks.
  2. In order to convert the "number" to "x, y coordinates" with 2x2 as the minimum unit, adjust each digit of the ternary number to 0 or 1 to make it "binary".
  3. Find the adjacent "number" from each of the four adjacent "x, y coordinates" on the top, bottom, left, and right.
  4. To find the "number", adjust each digit of the "binary number" of the "x, y coordinates" to 0, 1, 2 to make it a "ternary number".
  5. However, the "x, y coordinates" corresponding to the blank in the lower right do not become the "number".
number 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Ternary 0 1 2 10 11 12 20 21 22 100 101 102 110 111 112 120 121 122 200
2⇒0 0 1 0 10 11 10 00 01 00 100 101 100 110 111 110 100 101 100 000
Binary conversion ⇒ X coordinate 0 1 0 2 3 2 0 1 0 4 5 4 6 7 6 4 5 4 0
1⇒0 2⇒1 0 0 1 00 00 01 10 10 11 000 000 001 000 000 001 010 010 011 100
Binary conversion ⇒ Y coordinate 0 0 1 0 0 1 2 2 3 0 0 1 0 0 1 2 2 3 4
#!/usr/bin/env python
# -*- coding:utf-8 -*-

def base(n, b):
    return (n // b and base(n // b, b) or '') + str(n % b)

def number(x, y):
    return (x < 0 or y < 0 or x & y != 0 or  # return True if there is no number
            int(str(int(bin(x)[2:]) + int(bin(y)[2:].replace('1', '2'))), 3))  # x:0or1 + y:0or2

def solve(data):
    digits = base(int(data), 3)
    x = int(digits.replace('2', '0'), 2)                    # x:012 -> 010
    y = int(digits.replace('1', '0').replace('2', '1'), 2)  # y:012 -> 001
    neighbors = number(x, y - 1), number(x - 1, y), number(x + 1, y), number(x, y + 1)
    return ','.join(str(n) for n in neighbors if n is not True)

def test(n, data, correct):
    answer = solve(data)
    if answer == correct:
        print('OK #%s: "%s" -> "%s"' % (n, data, answer))
    else:
        print('NG #%s: "%s" -> "%s" != "%s"' % (n, data, answer, correct))

test(0, "21", "19,22,23")
test(1, "0", "1,2")
test(2, "1", "0,3")
test(3, "2", "0,6")
test(4, "3", "1,4,5")
test(5, "4", "3,9")
test(6, "9", "4,10,11")
test(7, "15", "11,16,17")
test(8, "27", "13,28,29")
test(9, "32", "30")
test(10, "47", "45,51")
test(11, "65", "63,69")
test(12, "80", "78,162")
test(13, "199", "198,201")
test(14, "204", "200,205,206")
test(15, "243", "121,244,245")
test(16, "493", "492")
test(17, "508", "507")
test(18, "728", "726,1458")
test(19, "793", "792,795")
test(20, "902", "900,906")
test(21, "981", "976,982,983")
test(22, "1093", "1092,2187")
test(23, "1202", "1200")
test(24, "1300", "1299,1305")
test(25, "1962", "1952,1963,1964")
test(26, "2188", "2187,2190")
test(27, "2405", "2403,2409")
test(28, "3326", "3324")
test(29, "6561", "3280,6562,6563")
test(30, "6612", "6608,6613,6614")
test(31, "7058", "7056,7062")
test(32, "8444", "8442,8448")
test(33, "9841", "9840,19683")
test(34, "15243", "15239,15244,15245")
test(35, "19946", "19944,19950")
test(36, "21148", "21147")
test(37, "39365", "39363")
test(38, "39366", "19682,39367,39368")
test(39, "55694", "55692,55698")
test(40, "57245", "57243")
test(41, "66430", "66429,66432")
test(42, "92740", "92739")
test(43, "115250", "115248")
test(44, "163031", "163029")
test(45, "221143", "221142,221157")
test(46, "410353", "410352")
test(47, "412649", "412647,412659")
test(48, "550391", "550389")
test(49, "699921", "699880,699922,699923")
test(50, "797161", "797160,1594323")
test(51, "1000000", "999999,1000002")


Recommended Posts

Offline real-time how to write Python implementation example of E15 problem
Offline real-time how to write Python implementation example of E14
Offline real-time how to write E11 ruby and python implementation example
Answer to "Offline Real-time How to Write E13 Problem"
How to write offline real-time Solving E05 problems with Python
The 15th offline real-time I tried to solve the problem of how to write with python
The 15th offline real-time how to write reference problem in Python
The 14th offline real-time how to write reference problem in python
The 18th offline real-time how to write reference problem in Python
Answer to "Offline real-time how to write F02 problem"
Answer to "Offline Real-time How to Write F01 Problem"
The 16th offline real-time how to write problem was solved with Python
The 17th offline real-time how to write reference problem implemented in Python
The 16th offline real-time how to write reference problem to solve with Python
The 19th offline real-time how to write reference problem to solve with Python
The 15th offline real-time how to write problem was solved with python
20th Offline Real-time How to Write Problems in Python
Answer to "Offline Real-Time Writing E12 Problem"
Part 1 I wrote an example of the answer to the reference problem of how to write offline in real time in Python
The 10th offline real-time writing reference problem. Implementation example by Python.
How to write offline real time Solve E04 problems in Python
The 11th offline real-time writing reference problem. Implementation example by python.
How to write offline real time I tried to solve the problem of F02 with Python
How to write offline real time I tried to solve E12 with python
Part 1 I wrote the answer to the reference problem of how to write offline in real time in Python
How to write a list / dictionary type of Python3
13th Offline Real-time How to Solve Writing Problems in Python
The twelfth offline real-time writing reference problem. Implementation by python
How to write a Python class
The 17th Offline Real-time How to Solve Writing Problems in Python
How to write offline real time Solve F01 problems with Python
[Python] Summary of how to use pandas
Answer to "Offline real-time writing F04 problem"
Answer to "Offline real-time writing F05 problem"
[Python2.7] Summary of how to use unittest
Summary of how to use Python list
[Python2.7] Summary of how to use subprocess
How to write Ruby to_s in Python
Summary of how to write AWS Lambda
[Question] How to use plot_surface of python
A simple example of how to use ArgumentParser
[Python] How to use two types of type ()
Summary of how to import files in Python 3
Summary of how to use MNIST in Python
How to specify attributes with Mock of python
The 18th offline real-time writing problem in Python
How to get dictionary type elements of Python 2.7
The 19th offline real-time writing problem in Python
[Python] Summary of eval / exec functions + How to write character strings with line breaks
Implementation example of simple LISP processing system (Python version)
How to get the number of digits in Python
How to install Python
I tried to summarize how to use matplotlib of python
How to write string concatenation in multiple lines in Python
How to install python
How to use Python Kivy ① ~ Basics of Kv Language ~
[Python] How to write a docstring that conforms to PEP8
[Python] How to split and modularize files (simple, example)
Review of atcoder ABC158, up to question E (Python)
The 14th offline real-time writing reference problem with Python
[Python] Summary of how to specify the color of the figure