覆面算 SEND+MORE=MONEY を解いてみました

http://www.itpl.co.jp/ocaml-nagoya/index.php?%A5%CD%A5%BF%B5%AD%CF%BF%B8%CB%2FSEND%2BMORE%3DMONEY

「もっと金送れ」かっこいい！調べてみたら、こういうのを覆面算っていうのですね、ちっとも知りませんでした。取り敢えず解いてみました。

type pairs = (char * int) list

let toint (li : int list) =
  List.fold_left (fun a b -> (a * 10 + b)) 0 li;;

let score (d : pairs) =
  let f l = (toint (List.map (fun a -> List.assoc a d) l)) in
  if (List.assoc 'S' d = 0) || (List.assoc 'M' d = 0) then 99999
  else
    let sum = (f ['S'; 'E'; 'N'; 'D']) + (f ['M'; 'O'; 'R'; 'E'])
    and money = f ['M'; 'O'; 'N'; 'E'; 'Y'] in
    abs (sum - money)

let compare' a b = compare (score a) (score b);;

let exchange (pairs:pairs) char =
  let unused =
    List.nth (List.filter (fun elt ->
      not (List.mem elt (snd (List.split pairs)))
    ) [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]) (Random.int 2)
  in
  (char, unused) :: (List.remove_assoc char pairs)
;;

let swap (pairs:pairs) a b =
  let char_a, num_a = List.nth pairs a
  and char_b, num_b = List.nth pairs b in
  (char_a, num_b)::(char_b, num_a)::
    (List.remove_assoc char_b (List.remove_assoc char_a pairs))
;;

let rec change (pairs:pairs) =
  match Random.int 9, Random.int 8 with
    | 8, idx -> exchange pairs (fst (List.nth pairs idx))
    | a, b -> if a <> b then swap pairs a b else change pairs

let print_score n pairs =
  Printf.printf "G%d: " n;
  List.iter (fun (char, num) -> Printf.printf "%c: %d " char num) pairs;
  Printf.printf "(%d)" (score pairs);
  print_newline ()
;;

let rec generation n list =
  let sorted =
    List.sort compare' (List.flatten (List.map (fun pairs ->
      [pairs; change pairs; change pairs; change pairs; change pairs;]
    ) list))
  in
  print_score n (List.hd sorted);
  if (score (List.hd sorted)) = 0 then List.hd sorted
  else
    generation (n+1) (snd (List.fold_left (fun (i, res) pairs ->
      if i > 0 then i-1, pairs::res else i, res
    ) (300, []) sorted))
;;

let rec choose numbers =
  if List.length numbers < 8 then
    let n = Random.int 10 in
    choose (if List.mem n numbers then numbers else n::numbers)
  else numbers
;;

let make_pairs list = function
  | 0 -> list
  | _ -> (List.combine ['S';'E';'N';'D';'M';'O';'R';'Y'] (choose []))::list
;;

let main = Random.self_init (); generation 0 (make_pairs [] 300);;

頭を使わない偶然頼り方式、でもおかげで5秒くらいで解けます。

G0: R: 9 M: 4 S: 7 E: 1 N: 8 D: 6 O: 0 Y: 2 (29535)
G1: Y: 9 M: 2 E: 8 N: 1 S: 7 D: 6 O: 0 R: 4 (10325)
G2: M: 1 S: 9 E: 7 N: 8 D: 6 O: 0 R: 4 Y: 2 (39)
G3: S: 9 M: 1 E: 7 N: 8 D: 6 O: 0 R: 4 Y: 2 (39)
G4: R: 4 Y: 2 M: 1 S: 9 E: 7 N: 8 D: 6 O: 0 (39)
G5: D: 4 E: 6 M: 1 R: 8 N: 7 S: 9 O: 0 Y: 2 (2)
G6: E: 6 S: 9 N: 7 D: 4 M: 1 R: 8 O: 0 Y: 2 (2)
G7: Y: 2 N: 7 D: 4 E: 6 R: 8 M: 1 S: 9 O: 0 (2)
G8: E: 6 N: 7 R: 8 D: 4 S: 9 M: 1 O: 0 Y: 2 (2)
G9: D: 5 E: 6 R: 8 M: 1 O: 0 N: 7 S: 9 Y: 2 (1)
G10: R: 8 D: 7 Y: 2 N: 6 E: 5 S: 9 M: 1 O: 0 (0)
4.21s user 0.04s system 94% cpu 4.470 total

解が複数ある時ダメだよね。でもちゃんと解けたから満足！