オフラインリアルタイムどう書く E11 を python で解いてみた

問題 : http://nabetani.sakura.ne.jp/hena/orde11tredis/
実装リンク集 : http://qiita.com/Nabetani/items/10b2ccc28301e44e09e6

ツリー内のノードをクラスにしました。
同じ値のノードがいくつも登場するのでキャッシュあり版も作ってみました。

* 子ノードに２つの距離を聞いてみる。ない場合もある
* 自ノードを挟んで２つの距離を調べる。ない場合もある。
* 子ノード内の距離と自ノードを挟んだ距離の短い方を選ぶ。ルートノードでは必ず見つかる。

```py:E11.py(キャッシュなし版)
class Node:
    def __init__(self, number):
        self.number = number
        self.children = [Node(i + 1)
                         for i in range(2, number // 2 + 1)
                         if number % i == 0]

    def distances(self, number):
        if number  > self.number: return []
        if number == self.number: return [0]
        return [distance + 1
                for child in self.children
                for distance in child.distances(number)]

    def distances_between(self, a, b):
        distances_in_children = [distance
                                 for child in self.children
                                 for distance in child.distances_between(a, b)]
        da, db = self.distances(a), self.distances(b)
        distance_across_self = [min(da) + min(db)] if da and db else []
        return distances_in_children + distance_across_self

    def distance_between(self, a, b):
        return min(self.distances_between(a, b))

def solve(data):
    root, ab = data.split(':')
    a, b = map(int, ab.split(','))
    return str(Node(int(root)).distance_between(a, b))

def test(no, data, correct):
    answer = solve(data)
    result = "OK" if answer == correct else "NG"
    print result, '%2d' % no, data, correct, '->', answer

if __name__ == '__main__':
    test( 0, "50:6,3", "1" );    
    test( 1, "98:5,11", "4" );    
    test( 2, "1000:33,20", "7" );    
    test( 3, "514:9,18", "8" );    
    test( 4, "961:5,4", "3" );    
    test( 5, "1369:1369,3", "2" );    
    test( 6, "258:16,12", "5" );    
    test( 7, "235:13,3", "2" );    
    test( 8, "1096:19,17", "8" );    
    test( 9, "847:7,17", "6" );    
    test(10, "1932:3,5", "2" );    
    test(11, "2491:4,8", "3" );    
    test(12, "840:421,36", "2" );    
    test(13, "1430:37,111", "3" );    
    test(14, "496:17,9", "2" );    
    test(15, "891:6,10", "1" );    
    test(16, "1560:196,21", "2" );    
    test(17, "516:20,12", "5" );    
    test(18, "696:30,59", "2" );    
    test(19, "1760:5,441", "2" );    
    test(20, "1736:11,26", "5" );    
    test(21, "1518:17,34", "4" );    
    test(22, "806:63,16", "5" );    
    test(23, "1920:3,97", "2" );    
    test(24, "1150:13,22", "4" );    
    test(25, "920:116,5", "1" );    
    test(26, "2016:7,337", "2" );    
    test(27, "408:9,25", "2" );    
    test(28, "735:36,8", "2" );    
    test(29, "470:5,31", "2" );    
    test(30, "2100:12,351", "3" );    
    test(31, "870:36,10", "1" );    
    test(32, "1512:253,13", "2" );    
    test(33, "697:12,15", "3" );    
    test(34, "1224:5,14", "2" );    
    test(35, "986:125,17", "3" );    
    test(36, "864:12,13", "3" );    
    test(37, "500:21,51", "2" );    
    test(38, "819:33,21", "4" );    
    test(39, "594:55,3", "2" );    
    test(40, "638:17,24", "3" );
```

```py:E11.py(キャッシュあり版)
class Node:
    cache = {}

    @staticmethod
    def get(number):
        if number in Node.cache: return Node.cache[number]
        Node.cache[number] = node = Node(number)
        return node

    def __init__(self, number):
        self.number = number
        self.children = [Node.get(i + 1)
                         for i in range(2, number // 2 + 1)
                         if number % i == 0]

    def distances(self, number):
        if number  > self.number: return []
        if number == self.number: return [0]
        return [distance + 1
                for child in self.children
                for distance in child.distances(number)]

    def distances_between(self, a, b):
        distances_in_children = [distance
                                 for child in self.children
                                 for distance in child.distances_between(a, b)]
        da, db = self.distances(a), self.distances(b)
        distance_across_self = [min(da) + min(db)] if da and db else []
        return distances_in_children + distance_across_self

    def distance_between(self, a, b):
        return min(self.distances_between(a, b))

def solve(data):
    number, ab = data.split(':')
    a, b = map(int, ab.split(','))
    return str(Node.get(int(number)).distance_between(a, b))

def test(no, data, correct):
    answer = solve(data)
    result = "OK" if answer == correct else "NG"
    print result, '%2d' % no, data, correct, '->', answer

if __name__ == '__main__':
    test( 0, "50:6,3", "1" );    
    test( 1, "98:5,11", "4" );    
    test( 2, "1000:33,20", "7" );    
    test( 3, "514:9,18", "8" );    
    test( 4, "961:5,4", "3" );    
    test( 5, "1369:1369,3", "2" );    
    test( 6, "258:16,12", "5" );    
    test( 7, "235:13,3", "2" );    
    test( 8, "1096:19,17", "8" );    
    test( 9, "847:7,17", "6" );    
    test(10, "1932:3,5", "2" );    
    test(11, "2491:4,8", "3" );    
    test(12, "840:421,36", "2" );    
    test(13, "1430:37,111", "3" );    
    test(14, "496:17,9", "2" );    
    test(15, "891:6,10", "1" );    
    test(16, "1560:196,21", "2" );    
    test(17, "516:20,12", "5" );    
    test(18, "696:30,59", "2" );    
    test(19, "1760:5,441", "2" );    
    test(20, "1736:11,26", "5" );    
    test(21, "1518:17,34", "4" );    
    test(22, "806:63,16", "5" );    
    test(23, "1920:3,97", "2" );    
    test(24, "1150:13,22", "4" );    
    test(25, "920:116,5", "1" );    
    test(26, "2016:7,337", "2" );    
    test(27, "408:9,25", "2" );    
    test(28, "735:36,8", "2" );    
    test(29, "470:5,31", "2" );    
    test(30, "2100:12,351", "3" );    
    test(31, "870:36,10", "1" );    
    test(32, "1512:253,13", "2" );    
    test(33, "697:12,15", "3" );    
    test(34, "1224:5,14", "2" );    
    test(35, "986:125,17", "3" );    
    test(36, "864:12,13", "3" );    
    test(37, "500:21,51", "2" );    
    test(38, "819:33,21", "4" );    
    test(39, "594:55,3", "2" );    
    test(40, "638:17,24", "3" );
```

```text:実行結果
$ python E11.py
OK  0 50:6,3 1 -> 1
OK  1 98:5,11 4 -> 4
OK  2 1000:33,20 7 -> 7
OK  3 514:9,18 8 -> 8
OK  4 961:5,4 3 -> 3
OK  5 1369:1369,3 2 -> 2
OK  6 258:16,12 5 -> 5
OK  7 235:13,3 2 -> 2
OK  8 1096:19,17 8 -> 8
OK  9 847:7,17 6 -> 6
OK 10 1932:3,5 2 -> 2
OK 11 2491:4,8 3 -> 3
OK 12 840:421,36 2 -> 2
OK 13 1430:37,111 3 -> 3
OK 14 496:17,9 2 -> 2
OK 15 891:6,10 1 -> 1
OK 16 1560:196,21 2 -> 2
OK 17 516:20,12 5 -> 5
OK 18 696:30,59 2 -> 2
OK 19 1760:5,441 2 -> 2
OK 20 1736:11,26 5 -> 5
OK 21 1518:17,34 4 -> 4
OK 22 806:63,16 5 -> 5
OK 23 1920:3,97 2 -> 2
OK 24 1150:13,22 4 -> 4
OK 25 920:116,5 1 -> 1
OK 26 2016:7,337 2 -> 2
OK 27 408:9,25 2 -> 2
OK 28 735:36,8 2 -> 2
OK 29 470:5,31 2 -> 2
OK 30 2100:12,351 3 -> 3
OK 31 870:36,10 1 -> 1
OK 32 1512:253,13 2 -> 2
OK 33 697:12,15 3 -> 3
OK 34 1224:5,14 2 -> 2
OK 35 986:125,17 3 -> 3
OK 36 864:12,13 3 -> 3
OK 37 500:21,51 2 -> 2
OK 38 819:33,21 4 -> 4
OK 39 594:55,3 2 -> 2
OK 40 638:17,24 3 -> 3
```