【Project Euler】Problem 79:パスコードの推測

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 79.パスコードの推測

原文 Problem 79: Passcode derivation

問題の要約：パスコードの指定された位置の数3桁（位置の順番になっている）を入力した結果が50回分与えられたとき考えられる最短の元のパスコードを求めよ

• 例えばパスコードが531278のとき、2,3,5番目の数字を指定されたら317を入力する

以下のようなステップで考えて行きます。

1. 最短のパスコードということなので入力した3桁の数字に含まれていないものは除外し、それ以外の数字は1個づつしかないと仮定します。
2. 3桁の数字が位置の順番になっているので、例えば317だとすると元のパスコードで1は3より右に、7は1より右にあるので、順番が違っていれば入れ替える。

これをプロクラムにしたのがこちらです。ファイルから読む部分は例によって下に添付してあるます。

from collections import Counter
from functools import reduce

# Remove unused numbers, create pcode candidate list (un-ordered)
csum = reduce(lambda a, b: a+b, [Counter(k) for k in keyLogs]) # count the digit appeared
pcode = list(map(int,csum.keys()))

# swap the positions of two numbers if the order is wrong
def swapn(p,pl):
  if p[0] > p[1]: 
    pl[p[0]], pl[p[1]] =  pl[p[1]],  pl[p[0]]

for nums in keyLogs:
  pos = [pcode.index(int(d)) for d in nums]  # index of each number
  swapn(pos[:2],pcode)
  swapn(pos[1:],pcode)

print(f"Answer {''.join(list(map(str,pcode)))}") 

(別解) トポロジカルソート(networkx)

この問題の別解としてグラフ理論の「トポロジカルソート(Wikipedia)」を使う方法があります。各桁の数字をノードとし、3桁の数字から得られる順番を「半順序（部分的な順序）」としてそれから「トポロジカルソートとは、これを全順序になるように拡張」したものということです。

Pythonにはグラフ理論をサポートするパッケージnetworkxがありますのでこれを使ってみます。以下のステップでプログラムにします。

1. 0~9をノードに登録
2. 3桁の数字から得られる順番を有向の辺(directed edge)に登録（重複を除く）
3. どのノードともつながっていない孤立ノードを調べてグラフから除く
4. トポロジカルソートを掛けて結果を取り出す

# Using Topological Sort
import networkx as nx
import matplotlib.pyplot as plt

node_list = [str(i) for i in range(10)] # ["0","1","2",...]
# --- Create directed edge list (removing duplicated)
edge_list = set()
for s in keyLogs:
  edge_list.add((s[0],s[1]))
  edge_list.add((s[1],s[2]))
# print(edge_list)

# --- Create the graph from nodes/edges
G = nx.DiGraph()
G.add_nodes_from(node_list)
G.add_edges_from(edge_list)
# --- Remove isolated node
isolated = [n for n in G.nodes if len([ i for i in nx.all_neighbors(G, n)]) == 0]
print(f"isolated nodes: {isolated}")
for n in isolated:
  G.remove_node(n)
  
print(f"Answer : {''.join(list(nx.topological_sort(G)))}")
nx.draw_networkx(G)
plt.show

入力されたグラフをplt.showで図示した結果がこれです。

ファイルから読むプログラム

# show upload dialog
from google.colab import files
uploaded = files.upload()
# ---- read numbers from file 
f = open("p079_keylog.txt")
keyLogs = f.readlines()
f.close()
keyLogs = list(map(lambda s: s.strip(),keyLogs))
print(keyLogs[:10])

（開発環境：Google Colab）