March 31, 2010

春休みの宿題「計算力」 (解けない問題)

Final Workout 計算力Final Workout 計算力

クチコミを見る

配られたカードにある5つの数字に加減乗除を施して場にある数字を作るというゲームを買った.

caclulation
例えば右のような場合,
1,4,5,8,9を使って加減乗除して,
答えが59となる式を求める.

1つの解は,
(8 + 9 - 1) * 4 - 5 = 59 である.

その昔, 自分が子供のころ「クリプト」という似たようなゲームがあったのを思い出した.

で, これって, いつも解けるのだろうか...???

その昔は, 自分のプログラムの技量の限界か, 計算機の能力の限界か, 全部しらみつぶしで調べることは出来なかった...「クリプト」は1枚に1つづづ数が書かれたカードを5枚配っていたので, その組み合わせも多くて厄介だった! このゲームは5つの数が, まとめてかかれたカードを1枚配るだけ. 配られるカードは全部で54通りだけ.

というわけで, 解けない場合を全て求めてみた.
求める数のカード配られた数のカード
791,3,4,6,9
911,4,5,7,9
921,2,3,5,8
921,3,5,7,9
931,4,5,6,9
991,4,5,6,8
この6通りだけである. ところが, この製品は, これらの求める数が丁度, 解けない場合の配られた数のカードの裏に書いてあった. すなわち, 普通にゲームをしていたら, 求める数と配られた数のカードは別のカードになるので, 解けない場合は, 起こらないことになる!!
...良く出来ている...

※ 但し, 1つだけ例外があって, 求める数が92のときだけは出来ない場合が2通りある. 唯一現れるであろう不可能な場合は, 場に92が出て, 1,3,5,7,9のカードが配られた場合であることがわかった.


カードの裏に書かれている求める数は11から99までの数だが, カードが54枚なので全てではない. 求める数がカードにはないが, 以下の組み合わせも解けないことがわかる.
852,3,6,7,9
861,3,4,5,8
941,4,5,6,8
951,2,4,7,8
971,2,3,5,8
971,4,5,6,8
981,4,5,6,9
981,3,4,8,9
981,4,5,7,8
981,4,5,7,9


Haskell言語で書いた不可能な組み合わせを探すプログラム.
※ 間違ってたら, ゴメンナサイ!
import Data.List
subset 0 s = [([],s)]
subset n [] = []
subset n (x:xs) = a ++ b
where a = [(x:y, z)|(y,z)<-subset (n-1) xs]
b = [(y, x:z)|(y,z)<-subset n xs]

divtwo 0 y = [0]
divtwo x 0 = [0]
divtwo x y | (x == y) = [1]
| ((x > y) && ((mod x y)==0)) = [div x y]
| ((x < y) && ((mod y x)==0)) = [div y x]
| otherwise = []

difftwo x y | (x == y) = [0]
| (x > y) = [x-y]
| otherwise = [y-x]

all2 x y = nub $ [x+y, x*y]++(divtwo x y)++(difftwo x y)
all2set s = all2 (s!!0) (s!!1)
all2s xs ys = nub $ concat $ map f xs
where f x = nub $ concat $ map (all2 x) ys

all2s12 (x,y) = all2s x (all2set y)
all2s22 (x,y) = all2s (all2set x) (all2set y)
all2s13 (x,y) = all2s x (all3set y)
all2s23 (x,y) = all2s (all2set x) (all3set y)
all2s14 (x,y) = all2s x (all4set y)
all3set s = nub $ concat $ map all2s12 (subset 1 s)
all4set s = union s22 s13
where s22 = nub $ concat $ map all2s22 (subset 2 s)
s13 = nub $ concat $ map all2s13 (subset 1 s)

all5set s = sort $ union s23 s14
where s23 = nub $ concat $ map all2s23 (subset 2 s)
s14 = nub $ concat $ map all2s14 (subset 1 s)

badlist = sortBy k $ concat $ map h $ filter g $ zip (map f cards) cards
where f s = [11..99] \\ (all5set s)
g (x,y) = (not (x==[]))
h ([], y) = []
h (x:xs, y) = [(x,y)]++(h (xs,y))
k (x1,y1) (x2,y2) = compare x1 x2

cards = [[1, 2, 3, 5, 8], [1, 2, 5, 7, 8], [1, 3, 4, 6, 8],
[1, 3, 5, 6, 8], [1, 4, 5, 6, 9], [1, 4, 6, 7, 9],
[1, 2, 4, 6, 9], [1, 2, 5, 7, 9], [1, 3, 4, 6, 9],
[1, 3, 5, 6, 9], [2, 3, 5, 7, 9], [2, 4, 5, 6, 8],
[1, 2, 4, 7, 8], [1, 2, 6, 7, 8], [1, 3, 4, 7, 8],
[1, 3, 5, 7, 8], [2, 3, 5, 8, 9], [2, 4, 5, 6, 9],
[1, 2, 4, 7, 9], [1, 2, 6, 7, 9], [1, 3, 4, 7, 9],
[1, 3, 5, 7, 9], [2, 3, 6, 7, 8], [2, 4, 5, 7, 8],
[1, 2, 5, 6, 9], [1, 3, 4, 5, 8], [1, 3, 4, 8, 9],
[1, 3, 5, 8, 9], [2, 3, 6, 7, 9], [2, 4, 5, 7, 9],
[1, 3, 6, 7, 8], [1, 4, 5, 7, 8], [1, 4, 6, 8, 9],
[2, 3, 4, 7, 9], [2, 3, 6, 8, 9], [2, 4, 6, 7, 8],
[1, 3, 6, 7, 9], [1, 4, 5, 7, 9], [2, 3, 4, 5, 8],
[2, 3, 4, 8, 9], [2, 3, 4, 7, 8], [2, 3, 5, 7, 8],
[1, 3, 6, 8, 9], [1, 4, 5, 8, 9], [2, 3, 4, 6, 8],
[2, 3, 5, 6, 8], [2, 4, 6, 7, 9], [2, 5, 6, 7, 9],
[1, 4, 5, 6, 8], [1, 4, 6, 7, 8], [2, 3, 4, 6, 9],
[2, 3, 5, 6, 9], [2, 5, 6, 7, 8], [2, 5, 7, 8, 9]]
実行結果:
*Main> badlist
[(79,[1,3,4,6,9]),
(85,[2,3,6,7,9]),
(86,[1,3,4,5,8]),
(91,[1,4,5,7,9]),
(92,[1,2,3,5,8]),(92,[1,3,5,7,9]),
(93,[1,4,5,6,9]),
(94,[1,4,5,6,8]),
(95,[1,2,4,7,8]),
(97,[1,2,3,5,8]),(97,[1,4,5,6,8]),
(98,[1,4,5,6,9]),(98,[1,3,4,8,9]),(98,[1,4,5,7,8]),(98,[1,4,5,7,9]),
(99,[1,4,5,6,8])]



as-192414 at 23:03コメント(0)トラックバック(0)生活 | パソコン 

トラックバックURL

コメントする

名前
URL
 
  絵文字
 
 
Visitors

Profile
QRコード
QRコード

レンタルサーバーなら使えるねっと

最新コメント
  • ライブドアブログ