ICFPCを早々に諦めて、ちょっと凹んでいたところ、サークル関係の内輪のチャットで比較的手軽に解けそうな問題が貼られていたので、暇つぶしに解いてみた。出典はどこかよくわからんのだけど、
http://ayacnews.blog57.fc2.com/blog-entry-6635.html
など、いくつかのURLに貼られているのを見つけることができた。
それぞれ異なる色の、５つの建物が並んでいます。
それらの家にはそれぞれ出身地の異なる家主が住んでいます。
5人全てが、何か飲み物を飲み、タバコを吸い、ペットを飼っています。
ただし、飲み物の種類、タバコの銘柄、ペットの種類はそれぞれべつべつです。問題： ↓の文を読み、誰が魚を飼っているかを当てて下さい。
１．日本人は赤い家に住んでいます。
２．アメリカ人は犬を飼っています。
３．中国人はお茶を飲みます。
４．緑の家は白い家の左にあります。
５．緑の家の家主はコーヒーを飲みます。
６．セブンスターを吸う家主は鳥を飼っています。
７．黄色い家の家主はマイルドセブンを吸っています。
８．ちょうど真ん中に位置する家の家主は牛乳を飲みます。
９．イタリア人は一番左の家に住んでいます。
１０．マルボロを吸う家主の家のお隣さんは猫を飼っています。
１１．馬を飼っている家主の家のお隣さんはマイルドセブンを吸っています。
１２．ホープを吸っている家主はビールを飲みます。
１３．ブラジル人はラークを吸っています。
１４．青い家の隣の家にイタリア人は住んでいます。
１５．マルボロを吸う家主の隣の家の家主は水を飲みます。
で、いかにも力技でプログラムに解かせると楽そうな問題なので、プログラムに解かせてみた。最初、候補を全部生成してから絞り込もうとしたが、計算してみると候補数が多過ぎてとてもまともな時間で終わりそうに無いので、そこそこ枝狩りするようにしたら、20秒くらいで解を出すようになった。一応、自分で解いてみたい人のために、続きを読む記法を使ってみた(今まで使ったこと無かった)
object 家 extends Enumeration {
val 赤 = Value("赤")
val 白 = Value("白")
val 緑 = Value("緑")
val 黄 = Value("黄")
val 青 = Value("青")
}
object 国 extends Enumeration {
val 日本 = Value("日本")
val アメリカ = Value("アメリカ")
val 中国 = Value("中国")
val ブラジル = Value("ブラジル")
val イタリア = Value("イタリア")
}
object 飲み物 extends Enumeration {
val 牛乳 = Value("牛乳")
val お茶 = Value("お茶")
val コーヒー = Value("コーヒー")
val 水 = Value("水")
val ビール = Value("ビール")
}
object タバコ extends Enumeration {
val マイルドセブン = Value("マイルドセブン")
val セブンスター = Value("セブンスター")
val マルボロ = Value("マルボロ")
val ホープ = Value("ホープ")
val ラーク = Value("ラーク")
}
object ペット extends Enumeration {
val 猫 = Value("猫")
val 犬 = Value("犬")
val 鳥 = Value("鳥")
val 馬 = Value("馬")
val 魚 = Value("魚")
}
case class 個人情報(の家: 家.Value, の国: 国.Value, の飲み物: 飲み物.Value, の吸うタバコ: タバコ.Value, のペット: ペット.Value)
def -->(c1: Boolean, c2: => Boolean): Boolean = {
if(c1) c2 else true
}
def select[T](s: List[T]): List[(T, List[T])] = s match {
case x::xs => (x, xs)::(select(xs).map{ case (y, ys) => (y, x::ys) })
case Nil => Nil
}
def forallWithIndex[T](a: Array[T])(pred: (T, Int) => Boolean): Boolean = {
var i = 0
while(i < a.length) {
if(!pred(a(i), i)) return false
i += 1
}
true
}
def solve(hs: List[家.Value], cs: List[国.Value], ds: List[飲み物.Value],
ts: List[タバコ.Value], ps: List[ペット.Value])(f: Array[個人情報] => Unit) {
def solve_(hs: List[家.Value], cs: List[国.Value], ds: List[飲み物.Value],
ts: List[タバコ.Value], ps: List[ペット.Value], acc: List[個人情報]) {
hs match {
case _::_ =>
var hs2 = select(hs)
var cs2 = select(cs)
var ds2 = select(ds)
var ts2 = select(ts)
var ps2 = select(ps)
for{ (h, hR) <- hs2
(c, cR) <- cs2 if -->(c == 国.日本, h == 家.赤)
(d, dR) <- ds2 if -->(c == 国.中国, d == 飲み物.お茶)
if -->(h == 家.緑, d == 飲み物.コーヒー)
(t, tR) <- ts2 if -->(h == 家.黄, t == タバコ.マイルドセブン)
if -->(t == タバコ.ホープ, d == 飲み物.ビール)
if -->(c == 国.ブラジル, t == タバコ.ラーク)
(p, pR) <- ps2 if -->(c == 国.アメリカ, p == ペット.犬)
if -->(t == タバコ.セブンスター, p == ペット.鳥)
} {
solve_(hR, cR, dR, tR, pR, 個人情報(h, c, d, t, p)::acc)
}
case Nil =>
val ps = acc.toArray
if(
(ps(0) の国) == 国.イタリア
&& (ps(2) の飲み物) == 飲み物.牛乳
&& forallWithIndex(ps){(p, i) =>
( -->(i > 0 && (p の家) == 家.白, (ps(i - 1) の家) == 家.緑)
&& -->((p の吸うタバコ) == タバコ.マルボロ, (i > 0 && (ps(i - 1) のペット) == ペット.猫) || (i < ps.length - 1 && (ps(i + 1) のペット) == ペット.猫))
&& -->((p の吸うタバコ) == タバコ.マルボロ, (i > 0 && (ps(i - 1) の飲み物) == 飲み物.水) || (i < ps.length - 1 && (ps(i + 1) の飲み物) == 飲み物.水))
&& -->((p の家) == 家.青, (i > 0 && (ps(i - 1) の国) == 国.イタリア) || (i < ps.length - 1 && (ps(i + 1) の国) == 国.イタリア))
&& -->((p のペット) == ペット.馬, (i > 0 && (ps(i - 1) の吸うタバコ) == タバコ.マイルドセブン) || (i < ps.length - 1 && (ps(i + 1) の吸うタバコ) == タバコ.マイルドセブン)))
}
) {
f(ps)
}
}
}
solve_(hs, cs, ds, ts, ps, Nil)
}
var count = 0
solve(
家.elements.toList,
国.elements.toList,
飲み物.elements.toList,
タバコ.elements.toList,
ペット.elements.toList){ps =>
println(ps.toList)
count += 1
}
println("count: " + count)出力結果。ちゃんと問題文の条件を満たせていることがわかる。
List(個人情報(黄,イタリア,水,マイルドセブン,猫), 個人情報(青,中国,お茶,マルボロ, 馬), 個人情報(赤,日本,牛乳,セブンスター,鳥), 個人情報(緑,ブラジル,コーヒー,ラー ク,魚), 個人情報(白,アメリカ,ビール,ホープ,犬)) count: 1
