オフラインリアルタイムどう書くE15の問題のPython実装例

問題 : http://nabetani.sakura.ne.jp/hena/orde15nohil/
解答リンク集 : http://qiita.com/Nabetani/items/705fa83cfbf20377b92f
イベント : https://yhpg.doorkeeper.jp/events/61418

1. 「番号」を「3進数」にして、NxNブロックの集まりを構成するの数字範囲毎に桁となる数字列を作る
2. 「番号」を2x2を最小単位とする「x,y座標」に変換するため、3進数の各桁を0か1に調整して「2進数」にする
3. 上下左右に隣接する4か所の各「x,y座標」から隣接する「番号」を求める
4. 「番号」の求め方は、「x,y座標」の「2進数」の各桁を 0, 1, 2 に調整して「3進数」にする
5. ただし、右下の空白に該当する「x,y座標」は「番号」にならない

number	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
3進	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
2進変換 ⇒X座標	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
2進変換 ⇒Y座標	0	0	1	0	0	1	2	2	3	0	0	1	0	0	1	2	2	3	4

#!/usr/bin/env python

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")