小町算
Posted feedbacks - OCaml
ocamlyaccとかストリームパーサーとか色々な道具を試した結果、LL(1) 再帰下降パーサーを手書きしました。
計算途中の値はint*int型の分数で持っています。
結果は101件で実行時間は0.23秒でした。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | type token = Int of int | Mul | Div | Add | Sub
let add (a1, b1) (a2, b2) = (a1 * b2 + a2 * b1), (b1 * b2)
let sub (a1, b1) (a2, b2) = (a1 * b2 - a2 * b1), (b1 * b2)
let mul (a1, b1) n = (a1 * n), b1
let div (a1, b1) n = a1, (b1 * n)
let factor list =
let rec factor' n = function
| Int x :: tl -> factor' (n * 10 + x) tl
| x -> n, x in
factor' 0 list
let term input =
let rec term' (f,input) = match input with
| Mul :: tl -> let f2, tl2 = factor tl in term' ((mul f f2), tl2)
| Div :: tl -> let f2, tl2 = factor tl in term' ((div f f2), tl2)
| x -> f, x in
let n, input = factor input in term' ((n,1), input)
let expr input =
let rec expr' (f,input) = match input with
| Add :: tl -> let f2, tl2 = term tl in expr' ((add f f2), tl2)
| Sub :: tl -> let f2, tl2 = term tl in expr' ((sub f f2), tl2)
| _ -> f in
expr' (term input)
let op = [| Add; Sub; Mul; Div |]
let rec makeexpr list o n =
if n = 0 then list else match (o mod 5) with
| 4 -> makeexpr (Int n :: list) (o / 5) (n - 1)
| x -> makeexpr (Int n :: op.(x) :: list) (o / 5) (n - 1)
let rec makestr s = function
| [] -> s
| hd :: tl -> makestr (s ^ (match hd with
| Int x -> string_of_int x | Mul->"*" | Div->"/" | Add->"+" | Sub->"-")) tl
let rec main n = if n >= 0 then
let ex = makeexpr [ Int 9 ] n 8 in
let a, b = expr ex in
let _ = if b * 100 = a then Printf.printf "%s\n" (makestr "" ex) in
main (n - 1)
let _ = main 390624
|
dpp
#4509()
Rating0/2=0.00
古典的なパズルである小町算を解くプログラムを作成してください。
小町算とは：
1□2□3□4□5□6□7□8□9＝100
四角の中に、空白、＋、－、×、÷のいずれかを一つ入れ、等式が成り立つようにするパズルです。
解答例：
1－2－3＋4×56÷7＋8×9＝100
1＋234×5÷6－7－89＝100
参考： http://ja.wikipedia.org/wiki/%E5%B0%8F%E7%94%BA%E7%AE%97
手元で20数行ほどのPythonスクリプトを書いてみたところ、101個の解答が得られました。
[ reply ]