「お買い物チャレラン」をグラフで解いてみた

Twitterでこういう画像を拾った。赤数字はこちらで追加したもの。

これはひょっとして膨大なパターンがあって、死ぬほど解くのが大変なのでは？と察したのだけれど、さて、何で解こうかちょっと考えた。

むかーし、仕事の一つに某道路公団の料金計算があり、C言語で修正ダイクストラ法を実装して経路を求めるのは散々やったのをふと思い出したが、今やるなら何が良いのかな、と。

Cosmos DBにはグラフデータにアクセスするGremlin APIがあるのでC#やPythonでゴッソリとノードとエッジを入れるのは何度か書いてる。しかし、Pythonそのものでグラフデータを扱ったことがあるかと言われると、そういや無いな？

ふむ、networkxちゅうのがあるのか。

% pip3 install networkx

してから

#!/usr/bin/env python3

import networkx as nx

各ノードの金額をリストに放り込む。

prices=[
    0,
    446, 358, 704, 514, 298,
    214, 697, 256, 225, 471,
    853, 151, 584, 387, 953,
    685, 188, 489, 285, 498,
    397, 295, 926, 405, 382,
    678, 486, 341, 816, 509,
    839, 570, 189, 287, 646,
    385, 768, 415, 163, 307,
    964, 137, 501, 470, 0
]

で、まずノードを作る。ノードの番号は画像に入れた赤数字の通り。

Graph = nx.DiGraph()
for k,v in enumerate(prices):
    Graph.add_node(k, price=v)

さて、ここからがちょっと面倒で、画像の通りにノードをエッジで接続する。まず、スタートから1段目。

Graph.add_edge(0, 1)
Graph.add_edge(0, 2)
Graph.add_edge(0, 3)
Graph.add_edge(0, 4)
Graph.add_edge(0, 5)

1段目から8段目までは同じ構造をしている。つまり、

左右両端のノードは奇数段の時は2つ下のノードに接続される
奇数段のノードは右のノードへ、偶数段のノードは左のノードに接続される
いずれのノードも（存在すれば）左下、下、右下のノードに接続される

ので、以下のように書いておいた。

for i in range(1, 40):
    mod = i % 10
    if mod == 1 or mod == 5:
        Graph.add_edge(i, i + 10) #2つ下のノードへ
    Graph.add_edge(i, i + 5) #下のノードへ
    if mod <= 4:
        Graph.add_edge(i, i + 1) #右のノードへ
    if mod >= 7 or mod == 0:
        Graph.add_edge(i, i - 1) #左のノードへ
    if mod != 1 and mod != 6:
        Graph.add_edge(i, i + 4) #左下のノードへ
    if mod != 0 and mod != 5:
        Graph.add_edge(i, i + 6) #右下のノードへ

最下段のノードは右のノードに接続されているから、こうだろう。

Graph.add_edge(41, 42)
Graph.add_edge(42, 43)
Graph.add_edge(43, 44)
Graph.add_edge(44, 45)

さて、スタートからゴールへの全経路を探索してぶん回す。

nodes = Graph.nodes(data=True)

for path in nx.all_simple_paths(Graph, source=0, target=45):
    sum = 0
    for n in path:
        sum = sum + nodes[n]['price']
        # sum = sum + prices[n] と書いても同じ。
    if sum == 10000:
        print("path: {}, sum:{}".format(path, sum))

こういう風に結果が出てきて、

path: [0, 1, 11, 12, 17, 22, 23, 24, 25, 30, 29, 28, 27, 31, 32, 33, 34, 39, 38, 37, 43, 44, 45], sum:10000
path: [0, 1, 11, 12, 13, 18, 23, 24, 29, 28, 27, 26, 32, 38, 37, 41, 42, 43, 44, 45], sum:10000
path: [0, 1, 11, 12, 13, 18, 17, 16, 21, 22, 23, 24, 28, 27, 26, 32, 33, 39, 38, 37, 43, 44, 45], sum:10000
...

1つ目の答えは以下なんだけど、

事前の予想通り、ものすごいパターンがある。最終的に、27,799通りの経路でちょうど1万円になることが分かったが、ちょっと答えが多すぎて問題の意図を間違って解釈しているんじゃないか？という気になっているし、Pythonでベタに書いたため非常に時間がかかる。cuGraphで爆速になるという話も見つけたので、時間あったら試してみよう。

コードと答えはGitHubに置いておいた。

「お買い物チャレラン」をグラフで解いてみた

関連

コメント