Author Archives: koyahata

Art of Prolog

Art of Prologをちまちまと読んでいます。

邦訳の「Prologの技芸」は高価かつレアでなかなか手に入りませんが、英語版は検索するとpdfが無料でダウンロードできます。

PrologのDCGは多分必須の知識だと思うけど、自分が調べた限りでは日本語のwebの情報はなく英語の解説サイトを読んで勉強しました。

このArt of PrologにもDCGのことが書いてありました。日本語でDCGのこと勉強したい人は「Prologの技芸」以外の資料は多分、ない(2016年5月現在)

希望する人がいれば僕が解説書いても良いです。

Prologは大学のとき授業でやってぜんぜんわからず憧れだけあって社会人になって真剣に勉強し始めましたが、現在は
CLPFDやAttributed VariableやCHRなど、大学の授業で学んだときより格段にパワーアップしている印象です。しかし日本ではPrologは超下火なので全然情報がない。必然的に英語を読まねばなりません。

Prolog好きな人たち(理屈っぽい文法オタクな人ではなく、Prologだとすごくパワフルに扱える事象に興味がある人)とつながりたいものだ。

簡単な巡回セールスマン問題をPrologで解く

「鉄道のスケジューリングアルゴリズム」という本を買って読んでいます。
その中で以下のような簡単な巡回セールスマン問題があったのでPrologでさくっと解いてみました。

あなたの会社は東京にある。札幌、大阪、博多、那覇にそれぞれクライアントを抱えており、それぞれの都市間の距離は以下である。
東京から出発してクライアント全員を1回づつ訪問し、東京に戻らなければいけない。このとき、移動距離の総和が2900km以下であるような経路は存在するだろうか?

sapporo-tokyo,511km
sapporo-osaka,667km
sapporo-hakata,883km
sapporo-naha,1398km
tokyo-osaka,278km
tokyo-hakata,566km
tokyo-naha,984km
osaka-hakata,289km
osaka-naha,740km
hakata-naha,537km

プログラム

実行結果

2900km以下の経路は存在しないようですね。

今回は経路が4!とおりで網羅が簡単だったけど、実際の問題はこれよりうんと複雑だろう。
自分は健康診断の会社で9年間働いていたのですが、いろいろな会社を回る健診バスの運行経路を決めるのは道路状況やリソース(人、機械)の問題もありかなり複雑そうでした。

小町算のパズルを制約論理プログラムとDCGを使用して解く

自分がPrologの勉強のために参考にしているM.Hiroiさんのページで掲載されている小町算の問題を、広井さんの解法とは異なり制約論理プログラミングと最近勉強したDCGを使用して解いてみました。
(参照:http://www.geocities.jp/m_hiroi/prolog/prolog14.html)

問題:
小町算
1 から 9 までの数字を順番に並べ、間に + と – を補って 100 になる式を作ってください。
例:1 + 2 + 3 – 4 + 5 + 6 + 78 + 9 = 100

プログラム

実行結果

広井さんのページ

自分はM.hiroiさんのページでPrologの基礎を学びその後Swi-Prologの英文マニュアルを読み制約論理プログラミングなど知ったのですが、広井さんにメールで制約論理プログラミングを紹介したら広井さんも興味を持たれたようで早速ホームページで取り上げられていました。

http://www.geocities.co.jp/SiliconValley-Oakland/1680/memo.html

僕の名前も紹介者として掲載されてました。ワーイ

前回からの続き Zebra Puzzleを制約論理プログラミングで解く2

前回の問題よりさらに複雑な以下のZebra Puzzleを制約論理プログラミングで解いてみる
参照:https://en.wikipedia.org/wiki/Zebra_Puzzle

問題:
The following version of the puzzle appeared in Life International in 1962:

There are five houses.
The Englishman lives in the red house.
The Spaniard owns the dog.
Coffee is drunk in the green house.
The Ukrainian drinks tea.
The green house is immediately to the right of the ivory house.
The Old Gold smoker owns snails.
Kools are smoked in the yellow house.
Milk is drunk in the middle house.
The Norwegian lives in the first house.
The man who smokes Chesterfields lives in the house next to the man with the fox.
Kools are smoked in the house next to the house where the horse is kept.
The Lucky Strike smoker drinks orange juice.
The Japanese smokes Parliaments.
The Norwegian lives next to the blue house.
Now, who drinks water? Who owns the zebra?

In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]. One other thing: in statement 6, right means your right.

プログラム

実行結果

解説
% Race 1:English 2:Spaniard 3:Ukrainian 4:Norwegian 5:Japanese
% HouseColor 1:red 2:green 3:ivory 4:yellow 5:blue
% Pet 1:dog 2:snails 3:fox 4:horse 5:zebra
% Drink 1:coffee 2:tea 3:milk 4:orange juice 5:water
% Smoke 1:Old Gold 2:Kool 3:Chesterfields 4:Lucky Strike 5:Parliaments

Now, who drinks water? Who owns the zebra?
5:water を飲んでいるのは 4:Norwegian
5:zebra を飼っているのは 5:Japanese

単純に条件を書いていけば簡単にプログラミングできたのですが、”next to” の制約を書く書き方で若干間違えた(解が増えてしまった)のとスペルミスなどのチェックが面倒くさかった。

ゼブラパズル(Zebra Puzzle)を制約論理プログラミングで解く

以下のパズル(ゼブラパズルというらしい)を制約論理プログラミングで解いてみた。

問題:
1.家が3軒あります。その3軒の家はそれぞれ赤・青・緑で塗られています。そしてその住人は、それぞれ異なる国籍で、それぞれ異なるペットを買っています。
2.イギリス人は赤い家に住んでいます。
3.スペイン人は犬を飼っています。
4.日本人は、猫を飼っている人の右側に住んでいます。
5.猫を飼っている人は青色の家の左に住んでいます。

誰がシマウマを飼っているでしょうか?

プログラム

実行結果

解説
Race 1:Japanese 2:English 3:Spanish
Color 1:Red 2:Blue 3:Green
Pet 1:Cat 2:Dog 3:Zebra
PetがZebra(3)と同じ要素番号のRaceは必ず1(日本人)
よってシマウマは日本人が飼っている。
家、ペット、国籍 の並びの組み合わせは上記2パターンある。

※ 「~の右に」という文章を「1軒右」と解釈しています。
  (2軒右も含むというコードに変更するのも簡単です)

中国の安い対局時計の手番スイッチの仕組み

中国の\2000の安い対局時計を分解して手番のスイッチの仕組みを見ているんだけどボタンの接点がなく、スイッチを押したときに片側の鉄片が近づくことによる静電容量の変化を認識してるっぽい。接点がないから長持ちするのかもしれない。
(2016/04/12 訂正 3枚目の写真の透明の素子が「リードリレー」とのことで、静電容量の変化を認識しているのではなく、スイッチの片側につけられた磁石が近づくことによりON/OFFになる仕組みのようです)

自分の作った対局時計で採用しているマイコンPIC1939でも静電容量変化感知機能があってそれを使用するとタッチパネルみたいに指を近づけると反応するようなスイッチが作成できる。

ただ自分の対局時計では電池を節約するため必要な処理を行った後スリープするようにしていて、これを、

・手番ボタンの押下
・時計用水晶からの外部タイマ割り込み(0.5sec毎)

の2種類のイベントで解除するようにして電池を節約しているのですが、

静電容量が変化したときにスリープ解除するような割り込みは存在しないようだったので静電容量感知スイッチを利用するのをあきらめたのだった。

静電容量スイッチだけで作成できればスイッチが基板のパターンだけでいけるのでボタン買わずにすみ安くできる。

KIMG0644

KIMG0645

KIMG0646

KIMG0643

みなみとかおりの数字当て問題を制約論理プログラミングで解く

ネットで以下のような問題が出ていた。(「これが解けるような秀才は募集しておりません」という塾の広告の問題?)

問題:
みなみとかおりの二人が数当てゲームをしていて、さやかが横で見ている。

このゲームは二人が1~13のトランプのカードの中から1枚取り、
先に相手の数字を当てた方が勝ちになるもので、みなみとかおりは自分のカードの数字しか見ることはできないが、さやかは二人のカードの数字を見ている。
3人が次の順で会話したとき、みなみとかおりのカードの数字を答えなさい。

さやか「二人のカードは異なる数字で、どちらも1ではない。片方がもう一方の整数倍の数字になっている」
みなみ「うーん、わからない」
かおり「私もわからない」
みなみ「そうか、今わかった」

3人が嘘をついていないものとして、みなみとかおりのカードの数字を当てなさい。

(※原文から誤解しやすい表記を少し直しています。)

面白そうな問題だったので、自分の好きなSWI-PROLOGとその制約論理ライブラリCLPFDを使用して解いてみた。

以下 SWI-PROLOGのコード

実行結果:

みなみが10、かおりが2で、そのほかの組み合わせはないようです。

うそつき娘問題を制約プログラミングで解く

ネットで以下の問題を見つけたのでSWI-PrologのCLPFDライブラリで解いてみた

問題:水泳大会

水泳大会で、この4人が1位から4位を獲得しました(同順位はありません)。

スタート前の予想は下のとおりで、3人が当たり、1人が外れました。

誰が何位だったのでしょう?

ことり「私は1位」
なる 「私はすずより上位」
すず 「私は1位か2位」
あゆ 「私は1位か2位」

プログラム:

実行結果:

実行結果は
[ことり順位,なる順位,すず順位,あゆ順位]
[ことり発言,なる発言,すず発言,あゆ発言 (1:真実 0:嘘)]

プログラム作成に10分くらいかかった。