ラベル logic programming の投稿を表示しています。 すべての投稿を表示
ラベル logic programming の投稿を表示しています。 すべての投稿を表示

2011年12月9日金曜日

Prolog で楽典クイズ

我々が日ごろ聞いてるふつうの音楽は、1オクターブの中に高さの異なる音が12個あって、それぞれの音は「音名」という名前を持っている。

実は、ほとんどの音はそれぞれ三つの音名を持っている。例えば、ミ♯、ファ、ソ♭♭の組み合わせや、レx、ミ、ファ♭の組み合わせは同じ音高であったりする。

ところが、ある音だけは二つの音名しか持っていない。この音が何かわかるだろうか。

ダブルシャープとかダブルフラットを使ってるから、小学校で習うかどうかは分からないけど、たぶん義務教育の範囲には入ってる気がするくらいの基礎的な楽典知識だけで構成された問いだけど、面白いことに、意外と音楽をやってる人でも即座には答えられなかったりする。

ピアノの鍵盤を思い浮かべて単なる図形として捉えたら簡単なんだけど、今日は、これを「寝る前ちょこっとプログラミング」のお題にしてみようと、帰りの電車で思いついた。Prolog でやってみる。

====

note(0, 'C').
note(2, 'D').
note(4, 'E').
note(5, 'F').
note(7, 'G').
note(9, 'A').
note(11, 'B').

notes([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]).

alteration('x', -2).
alteration('♯',  -1).
alteration('♮',   0).
alteration('♭',   1).
alteration('♭♭',  2).

noteWithThreeNames(Names)   :- findNoteNamesByCount(Names, 3).
noteWithOnlyTwoNames(Names) :- findNoteNamesByCount(Names, 2).

findNoteNamesByCount(Names, Count) :-
   notes(Notes), member(Note, Notes),
   collectNoteNames(Note, Names),
   length(Names, Count).

collectNoteNames(Note, Names) :-
  findall(Name, findName(Note, Name), Names).

findName(Note, Names) :- 
  alteration(Alteration, Diff), 
  getNote(Note + Diff, NaturalTone),
  concat_atom([NaturalTone, Alteration], Names).

getNote(N, X) :- N2 is N mod 12, note(N2, X).

素朴な実装だけど、以下のように正しい結果が得られる。
?- noteWithThreeNames(Names).
Names = ['B♯', 'C♮', 'D♭♭'] ;
Names = ['Bx', 'C♯', 'D♭'] ;
Names = ['Cx', 'D♮', 'E♭♭'] ;
Names = ['D♯', 'E♭', 'F♭♭'] ;
Names = ['Dx', 'E♮', 'F♭'] ;
Names = ['E♯', 'F♮', 'G♭♭'] ;
Names = ['Ex', 'F♯', 'G♭'] ;
Names = ['Fx', 'G♮', 'A♭♭'] ;
Names = ['Gx', 'A♮', 'B♭♭'] ;
Names = ['A♯', 'B♭', 'C♭♭'] ;
Names = ['Ax', 'B♮', 'C♭'].

?- noteWithOnlyTwoNames(Names).
Names = ['G♯', 'A♭'] ;
false.

====

音楽の話題でいえば、厳格対位法という、こんなのとは比較にならないくらいパズルっぽいやつがある。これは与えられた音の配列(定旋律)に対して、たくさんの「禁則」をくぐり抜けてごく限られた音の配列(対旋律)を見つけ出していくという、古典音楽作曲の伝統的なトレーニングなんだけど、視点を変えるとパズルの「川渡り問題」に似てなくもない。

たぶん、とっくにどこかのプログラマが挑戦してるだろうけど、もうちょいヒマができたら自分でもやってみたい気がする。

2011年11月13日日曜日

論理パズル で Prolog のウォーミングアップ

テストケース(開発者が作る、いわゆる DeveloperTest のテストケースじゃなくて、開発はやらないテスト部隊が使うテストケース)を作るための小道具として Prolog を使うと便利かもと思って、自宅の環境に SWI-Prolog を用意してみた。

Fedora の「ソフトウェアの追加/削除」でリストアップされてたので、選択して適用するだけでインストールできた。

本当は、与えられた条件にしたがって、縦に要因、横にテストケースを並べた直交表もどきの表を生成するような仕組みを作りたいんだけど、その前にウォーミングアップしてみる。

手元にある論理パズル集の中から簡単なものを選んで、Prolog で解いてみる事にする。

お題は以下のようなもの。

  • とあるミスコンで、好美、恵美、明美、麻美、宏美が予選通過した
  • なかよし4人組が以下のように優勝者を予想した
    • まゆみ:好美と恵美ではないだろう
    • 大貴:恵美か明美だろう
    • 崇臣:好美か麻美だろう
    • やす美:好美と麻美ではないだろう
  • 予想が的中した人数は2名だった。
優勝したのはだれか?

あまり Prolog に詳しいわけではないけど、素朴に書くと以下のようになるのではないだろうか。
% 出場者
contestant(akemi). 
contestant(asami). 
contestant(hiromi). 
contestant(emi). 
contestant(yoshimi).

% 誰が誰の優勝を予想しているか
expect(mayumi, akemi). expect(mayumi, asami). expect(mayumi, hiromi).
expect(daiki, akemi). expect(daiki, emi).
expect(takaomi, yoshimi). expect(takaomi, asami).
expect(yasumi, emi). expect(yasumi, akemi). expect(yasumi, asami).

% 結局、優勝者は2名の予想者に予想された出場者だった
winner(Contestant):- expectors(Contestant, 2).

% 優勝者と予想者数の関係
expectors(Contestant, Count):-
  contestant(Contestant),  
  countExpectators(Contestant, [mayumi, daiki, takaomi, yasumi], Count).

% 優勝者を予想した人を数える
countExpectators(_, [], 0 ).
countExpectators(Contestant, [Expector|OtherExpectors], Count) :-
  expect(Expector, Contestant), 
  countExpectators(Contestant, OtherExpectors, Count2),
  Count is Count2 + 1.
countExpectators(Contestant, [Expector|OtherExpectors], Count) :-
  not(expect(Expector, Contestant)),
  countExpectators(Contestant, OtherExpectors, Count).
これを SWI-Prolog に読ませて、以下のようにすると答えが出る。
?- winner(Winner).
Winner = emi .
ちなみに明美の優勝を予想した人数は、上で定義した述語 expectors 使って、以下のように求められる。
?- expectors(akemi, Count).
Count = 3 .
逆に、同じ expectors を使って、3名が優勝を予想した出場者を求めることもできる。これがPrologの面白いところでもある。
?- expectors(W, 3).
W = akemi ;
W = asami ;
false.

====

ソフトウェアのテストケースを作ろうとすると、あるテスト対象の振る舞いに影響を与える条件群について、すべての条件を掛け合わせると現実的でないテストケース数になったりする

なので、少ないテストケース数でなるべく各条件を網羅できるように工夫する事になるんだけど、その辺りの作業がちょっとしたパズルみたいになってくる事がある。

で、せっかくプログラミングを生業としているのだから、プログラムでなんとかしようかって発想になるんだけど、手続き型言語を使うと、やりたい事とコード上の表現がいまいち直截性に欠けていたりする。

あまり流行ってはいなけど、こういう時は Prolog が割と使えそうな気がしないでもない。

2011年10月18日火曜日

Coq をインストールしてみた

今日、現場の昼休みに、最近噂の Coq のチュートリアルを見つけたので、早速インストールしてみる。

Fedora 15 でアプリケーションの追加と削除を開くと、Coq 8.3がリストアップされてきたので、チェックを入れて適用。

さらに、端末を開いて coqide と打ち込んでみると、ひとしきり追加のインストールが実行されたあと、CoqIDE が開いた。 とりあえず、チュートリアル 一回目の練習問題を解いてみるが、初回なんで難しくない。

結構面白い。明日もやろっと。

2010年1月11日月曜日

Motzart/Logic puzzle

だいぶ前にインストールした Mozart という Oz 言語実装を、初めて使ってみた。

Wikipedia でロジックパズルを引くと、こんな簡単な例題が載っている(2010/01/11現在)。これを Mozart で書いてみる。
3人のそれぞれの発言から、それぞれの今日の昼食を当ててください。ただし、カレーライス、ラーメン、そばのうちから3人とも別々のものを食べました。
トンキチ:…。
チンペイ:あいつみたいにそばだったら僕は足りないな。
カンタ:僕はカレーライスもそばも嫌いなんだ。
答え
トンキチ:そば
チンペイ:カレーライス
カンタ:ラーメン

下のコードを Oz Programming Interface に入力して、C-M-x で読み込ませると、
local Kan Chin Ton
Lanch = [curry ramen soba]
NotIn = fun {$ Ex}
{Filter Lanch fun {$ X} {Not {Member X Ex}} end}
end
in
thread (Ton |_)= {NotIn [Kan Chin]} end
thread (Chin|_)= {NotIn [Kan soba]} end
thread (Kan |_)= {NotIn [curry soba]} end
{Browse [tonkichi#Ton chinpei#Chin kanta#Kan]}
end
Oz ブラウザに
[tonkichi#soba chinpei#curry tanta#ramen] 
と表示される。

うーん、まだよくわからんが Prolog とはだいぶ違う。

====
以下を参考にした

2009年8月9日日曜日

Mozart インストール

最近、論理型言語を触っていないので久しぶりに Prolog でパズルでも解いてみようと思った。ただ、ちょっとググってみると Prolog から派生したもので Oz という言語があるらしいので、フリー実装の Mozart と言うものをインストールしてみた。

OS はWindows XP SP3。Mozart のバージョンは1.4。Vistaの人は一個古いバージョンじゃないと対応されていない。Unix系の環境は一通りあり。

間抜けな事に、チュートリアルをチラ見してるうちに何故だか Linux 環境のものだと勘違いして andLinux をインストールしてしまったが、これは不要だった。Windows でOK。まあでもいずれインストールしようと思っていたので、まあ良し。

インストール後に作成されたメニューから最初に起動しようとしたとき、emacs が無いから起動できないと言われたが、emacsをインストールしたらすんなり立ち上がった(GNU emacs 20.7.1)。下の画面は Hello World の実行結果。


これからなるべく時間見つけて少しずつ覚えていきたい。

あと論理型言語で Mercury というやつに前からずっと興味があって、今までにも何度か試したりしたが、なんだかイマイチ品質が悪くてその都度気持ちが萎えて中断していた。だけど、さっき本家のサイトを見てみると、地味ながらずっと活動を続けているようなので、機会をみてまた試してみようと思う。

本業以外の言語では、本当は関数型より論理型の方に興味があるんだけど、世間的には何だかいつまで経っても盛り上がらない。何が不人気なんだろう?