小町算 in Haskell DouKaku?

古典的なパズルである小町算を解くプログラムを作成してください。

小町算とは：

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

evalやそれに類するものを使うか否かは自由です。
割り算の際には小数点以下の切捨てが起こらないのが望ましいです。(必須ではない)
- 切捨てが起こる場合の解答例：1÷2÷3＋4＋5÷6＋7＋89＝100
余裕があれば括弧を含むようにしてもいいかもしれません。

手元で20数行ほどのPythonスクリプトを書いてみたところ、101個の解答が得られました。

ナイーブに全探索。

opparseで演算子順位文法を使って式をRPNに変換し、calcで計算してます。

opsの定義を変えれば演算子を増やしたり優先順位を買えたりできます。同じ優先度の演算子は左結合。

import Numeric

data Item a b = Value a | Op (a->a->a) b [Char]

cat a b = a*10+b

ops :: [Item Double Integer]
ops = [Op cat 2 "", Op (+) 0 "+", Op (-) 0 "-", Op (*) 1 "*", Op (/) 1 "/"]
 
opparse [] _ vs = reverse vs
opparse (op:ops) (i:is) vs = opparse ops is $ push op (Value i) vs

push op@(Op o p _) v (op'@(Op o' p' _):vs)
  | (p <= p') = (op:v:op':vs)
  | otherwise = (op':push op v vs)
push op v vs = op:v:vs

calc [a] [] = a
calc ns ((Value a):vs) = calc (a:ns) vs
calc (a:b:ns) ((Op op _ _):vs) = calc ((op b a):ns) vs
calc _ _ = error "invalid stack state"

showFormula ops = "1" ++ rec [2..] ops where
   rec _ [] = ""
   rec (i:is) ((Op _ _ n):ops) = n ++ (showInt . round) i (rec is ops)

genops 0 = [[]]
genops n = [o:os | o <- map (ops!!) [0..4], os <- genops (n-1)]

komachi n = [ops | ops <- genops n, test 100 ops] where
   test sum ops = abs (sum - (calc [] $ opparse ops [2..] [Value 1])) <= 1.0e-10

main = putStr $ unlines $ map showFormula $ komachi 8

高階関数と有理数を使って書き直してみました。
一部私好みに書き換えています。

import Ratio

data Item a b c = Value a | Op (b->b->b) c String

cat a b = a*10+b

ops :: [Item Integer Rational Integer]
ops = [Op cat 2 "", Op (+) 0 "+", Op (-) 0 "-", Op (*) 1 "*", Op (/) 1 "/"]

opparse ops = reverse $ foldl push [Value 1] (zip ops $ map Value [2..])

push (op'@(Op o' p' _):vs) opv@(op@(Op o p _), v)
  | p <= p' = op:v:op':vs
  | otherwise = op':push vs opv
push vs (op, v) = op:v:vs

calc vs = head $ foldl g [] vs where
  g ns (Value a) = a%1:ns
  g (a:b:ns) (Op op _ _) = op b a:ns
  g _ _ = error "invalid stack state"

showFormula ops = concat $ ["1"] ++ zipWith (\(Op _ _ n) i -> n ++ show i) ops [2..]

genops n = sequence $ replicate n ops

komachi n = filter (test 100) $ genops n where
   test sum ops = sum == (calc $ opparse ops)

DouKaku?

小町算

Posted feedbacks - Haskell

Index

Feed

Other

Link

Pathtraq