F-Script 版 Reverse ゲーム

2009年 8月改訂

記事一覧

基礎

その他

Paul Bissex が、様々な言語で、Reverse ゲームをどのように実装できるかについて書いている。

Reverse ゲームは、ある数の並びを、左から右に数値の順番になる様に並べ替えるゲームだ。並べ替えるには、コンピュータに、(左から数えて) 何個の数の並びを反転 (reverse) せよと指示する。例えば、もし現在の並びが 2 3 4 5 1 6 7 8 9 だとすると、４個の数を反転 (reverse) すれば、その結果は 5 4 3 2 1 6 7 8 9 になるだろう。さあ、５個の数を反転 (reverse) すれば、あなたの勝ちだ。

ここに F-Script で書いたバージョンがある。

numbers := (9 random:9) + 1.
steps := -1.

flip := [:flipCount| 
    numbers at:flipCount iota put:(numbers at:flipCount iota) reverse.
    steps := steps + 1.
    (numbers isEqual: 9 iota + 1) ifTrue:['Done! That took you ' ++ steps printString ++ ' steps.']
                                  ifFalse:[numbers]
].

flip value:0.

このプログラムを実行すると、F-Scriptは、最初の数のリストを表示する。 F-Script の精神に則り、このゲームとの遣り取りは F-Script 自身を使って行おう。反転させる要素の個数を引数にして、flip ブロックを評価することでプレイするのだ。ゲームはこんな具合に終了する：

...
{3, 1, 2, 4, 5, 6, 7, 8, 9}

> flip value:3

{2, 1, 3, 4, 5, 6, 7, 8, 9}

> flip value:2

'Done! That took you 9 steps.'

これで対話的にプレイするのも良いが、ゲームの実装が手元にあるのだから、ゲームを自動実行する（しかも勝てる）プログラムを書いて楽しむこともできる。以下に示すのは、そんなプログラムの一つだ。ゲームが完了すると、ゲームの各段階の詳細と勝つまでに要したステップ数を表示する。

sorted := numbers at:numbers sort.
unsortedCount := numbers count.
journal := {numbers copy}.

[numbers isEqual:sorted] whileFalse:
[
    maxIndex := numbers indexOfObject:(numbers at:unsortedCount iota) \ #max: .
    maxIndex + 1 = unsortedCount ifFalse:
    [
        maxIndex = 0 ifFalse:[flip value:maxIndex + 1. journal addObject:numbers copy].
        result := flip value:unsortedCount.
        journal addObject:numbers copy.
    ].
    unsortedCount := unsortedCount - 1.
].

journal printString ++ '\n' ++ result.

このプログラムは、以下の手続きに基づいている。

リストの中で最大の数を見つける
その数がリストの最初に来る様に、数の並びを反転する
今度は、その数がリストの末尾に来る様に、数の並びを反転する
そうしたら、現在のリストの先頭からその数まで (その数は含めない) の範囲のサブリストを対象に、同じ手続きを適用する