2008年05月01日

[Haskell] 簡単な数学パズルを解く

  
数学パズル
3桁の数値とその数値を2乗した値の各数字が1から9までの数字で構成されるような3桁の数値をすべて求めるプログラムを作成せよ。
例えば 763*763=582169 となるが、これは、1,2,3,5,6,7,8,9 からなり、4が抜けているからダメ。

これも、数年前に新人君向けの作ったC#の問題だが、Haskellで解いてみる。

戦略は、
[(100,10000),(101,10201),(102,10404),(103,10609)...(999,998001)]
といったタプルのリストを作成し、filter関数で条件にあうタプルを抜き出す。
というやり方でコードを書いてみることにする。

まずは、タプルのリストを作成する関数 makrtuplelist
maketuplelist :: [Integer] -> [(Integer,Integer)]
maketuplelist nums = zip nums $ map (\n -> n * n) nums

nums には、[100..999]のリストを渡す。
mapで、2乗のリストを作成し、zip関数で、numsとのタプルのリストを作る。

条件に一致するかどうかを判定する関数judgeを作成

judge :: (Integer,Integer) -> Bool
judge (a,b) =
let allstring = show a ++ show b
in (sort allstring) == "123456789"

タプルを受け取り、文字列として連結し、ソートした結果が、"123456789"と一致していれば、条件に一致しているとみなしている。
別の解法も考えられるが、ここは最もお手軽な方法を選択。

そして、条件に一致するタプルだけを抜き取る関数 workoutを作る。
workout :: [Integer] -> [(Integer,Integer)]
workout = filter jugde . maketuplelist

関数合成を使ってみた。
関数連鎖を使えば、
workout nums = filter jugde $ maketuplelist nums

だ。
まだ、関数連鎖は慣れていない。いったん、関数連鎖の形にしてからでないと、関数合成のコードを書くことができないです。

そして、最後が、main関数
main = do print $ workout [100..999]

出来あがったコードは、以下のようになる。

import System
import List
 
main = do print $ workout [100..999]
 
workout :: [Integer] -> [(Integer,Integer)]
workout = filter jugde . maketuplelist
 
maketuplelist :: [Integer] -> [(Integer,Integer)]
maketuplelist nums = zip nums $ map (\n -> n * n) nums
 
judge :: (Integer,Integer) -> Bool
judge (a,b) =
let allstring = show a ++ show b
in (sort allstring) == "123456789"

さらに、where を使ってみると、

import System
import List
 
main = do print $ workout [100..999]
 
workout :: [Integer] -> [(Integer,Integer)]
workout nums = filter judge maketuplelist
where
judge :: (Integer,Integer) -> Bool
judge (a,b) =
let allstring = show a ++ show b
in (sort allstring) == "123456789"
 
maketuplelist = zip nums $ map (\n -> n * n) nums

となる。このほうが、関数間の呼び出し関係が視覚的に分かるので良いかな。
Haskellで面白いのは、字下げそのものが文法的に意味を持つ、というところですね。

このパズルの答えを知りたい人は、自分で動かしてみてください。


この記事へのコメント
おもしろい問題ですね.C# 3.0 + Achiral でやってみました.

var seq = from i in 100.UpTo(999)
let str = i.ToString() + (i * i).ToString()
where !"123456789".Except(str).Any()
select i;

seq.ConsoleWriteLine();

中間変数を使う場合は,直接 Tuple 相当のものを書き下すより,クエリ式からコンパイラに自動生成してもらった方が楽な感じですね.

中間変数を除去するとすればこんな感じでしょうか.
100.UpTo(999)
.Where(i =>
!"123456789".Except(i.ToString())
.Except((i * i).ToString())
.Any())
.ConsoleWriteLine();
Posted by NyaRuRu at 2008年05月02日 21:18
NyaRuRu さん
コメントありがとうございます。
おおっ、ワンラインで書けるんですね。
C#3.0で書くとどうなるかも考えていたのですが、
AllとContainsでやろうとしてました。
ExceptとAnyを使うという発想は無かったです。
なるほど。
しかし、このコードを見ると従来のC#とはまったく別種の言語みたいですね。
やっぱり、言語は思考を規定してるんだなって思います。
Posted by Gushwell at 2008年05月02日 23:39
Haskellの方も、list comprehensionを使えばかなり簡潔に書けますよ。

import Data.List

main = mapM_ print [n | n <- [100..999], cond n]
 where
  cond = null . (\\) "123456789" . \n -> show n ++ show (n * n)
Posted by nsharp at 2008年05月03日 08:17
condの関数合成の仕方がちょっと無理やり感があるので、修正です。

  cond n = null . (\\) "123456789" . concatMap show $ [n, n * n]
Posted by nsharp at 2008年05月03日 09:24
nsharp さん
リスト内包表記ってやつですね。
確かに本で読んだ記憶が... orz

(\\)なんて演算子があったんですね。これで、リストの差(?)が取れるんだ。

Haskellが身につくのはまだまだ先のことのようです(笑)。
でもHaskell面白いです。

Posted by Gushwell at 2008年05月03日 10:51
はじめまして。ta183hです。

ためしに、作ってみました。

import List
main = print [n | n <- [100..999],(sort( show (n * (1000000 + n))))=="123456789"]

最近、Haskellにはまってます。
Posted by ta183h at 2008年06月16日 11:15
ta183hさん、はじめまして。
なるほど、show (n * (1000000 + n)) としてしまえば、
文字列の連結が不要になるのか。
いろんなやり方がありますね。

Posted by Gushwell at 2008年06月17日 00:12
 

この記事へのトラックバックURL

この記事へのトラックバック
数学パズル 3桁の数値とその数値を2乗した値の各数字が1から9までの数字で構成されるような3桁の数値をすべて求めるプログラムを作成せよ。 例えば 763*763=582169 となるが、これは、1,2,3,5,6,7,8,9 からなり、4が抜けているからダメ。 窓際プログラマーの独り言 -C#
[コーディング]パズルが面白そうだったのでVBとc#で書いてみた【NAL-6295の舌先三寸】at 2008年06月13日 11:10