オフラインリアルタイムどう書くE11 「ツリーの中の距離」の解をPrologで書いた

問題はこちら: http://nabetani.sakura.ne.jp/hena/orde11tredis/
みなさんの回答はこちらから: http://qiita.com/Nabetani/items/10b2ccc28301e44e09e6

solver.pro

factor1(N, F) :- 
  N2 is N div 2 + 1,
  between(3, N2, F),
  N mod (F - 1) =:= 0.

route([N|NS], RS) :-
  factor1(N, F),
  route([F, N|NS], RS).
route(NS, NS).

distance(RA, RB, D) :-
  append(SA, R, RA),
  append(SB, R, RB),
  length(SA, LA),
  length(SB, LB),
  D is LA + LB.

distance(N, A, B, D) :-
  findall(R, route([N], R), RS),
  member([A|RA], RS),
  member([B|RB], RS),
  distance([A|RA], [B|RB], D).

parse(Input, N, A, B) :-
  append(NS, [0':|ABS], Input),
  append(AS, [0',|BS], ABS),
  number_codes(N, NS),
  number_codes(A, AS),
  number_codes(B, BS).

solve(Input, Result) :-
  parse(Input, N, A, B),
  findall(D, distance(N, A, B, D), DS),
  min_list(DS, MD),
  number_codes(MD, Result),
  !.

orde11.pro

% $ gplc orde11.pro
% $ ./orde11

:- initialization(main).
:- include(solver).

judge(_, Expected, Expected) :-
  write(.),
  !.
judge(Input, Expected, Actual) :-
  format("~ninput    ~s~nexpected ~s~nactual   ~s~n", [Input, Expected, Actual]).

test(Input, Expected) :-
  solve(Input, Actual),
  judge(Input, Expected, Actual).

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

GNU-Prolog のコンパイラ gplc でコンパイルして、できた実行ファイルを起動します。

$ gplc orde11.pro
$ ./orde11