Challenge 1: http://goo.gl/H5jUh. Androids bring a message to you!
@googlenexus
Submit Challenge 1 response as: "#GalaxyNexus is well-traveled, coming to @googlenexus from [answer]" Rules: http://goo.gl/5dpAK
@googlenexus
A googol of responses! If you haven't found the message, here's a hint: Dots are like flag signals
@googlenexus
ということで、最初はとっかかりがつかめず興味が持てなかったののですが、ネタが割れてみればなかなか面白そうだったので、各アンドロイドが示している可能性のある文字の組み合わせを列挙するコードを Squeak Smalltalk で書いてみました。
| dict pairs guessesOf androidDots | pairs := #(a (1 2) b (1 3) c (1 4) d (1 5) e (1 6) f (1 7) g (1 8) h (2 3) i (2 4) j (5 7) k (2 5) l (2 6) m (2 7) n (2 8) o (3 4) p (3 5) q (3 6) r (3 7) s (3 8) t (4 5) u (4 6) v (5 8) w (6 7) x (6 8) y (4 7) z (7 8)). dict := pairs pairsCollect: [:key :val | | array | array := #(0 0 0 0 0 0 0 0) copy. val do: [:idx | array at: idx put: 1]. key -> array]. guessesOf := [:dots | | queue results | results := Set new. queue := OrderedCollection with: '' -> dots. [queue notEmpty] whileTrue: [ | strRest | strRest := queue removeFirst. (strRest value allSatisfy: #isZero) ifTrue: [results add: strRest key] ifFalse: [ dict do: [:symFlag | | nextVal | nextVal := strRest value - symFlag value. (nextVal noneSatisfy: #negative) ifTrue: [queue addIfNotPresent: (strRest key, symFlag key) sort -> nextVal]]]]. results asSortedArray]. androidDots := #( (1 2 1 1 1 1 1 0) (2 1 0 1 2 0 0 0) (0 0 0 0 1 0 1 0) (1 1 2 3 1 0 0 0) (2 3 0 1 0 2 0 0) (2 5 1 2 0 1 1 0)). androidDots collect: [:dots | guessesOf value: dots]
#( #('ahju' 'ahtw' 'aijq' 'aipw' 'ajlo' 'akow' 'akqy' 'akru' 'alpy' 'alrt' 'ampu' 'amqt' 'bijl' 'bikw' 'bkly' 'bkmu' 'blmt' 'chjl' 'chkw' 'cklr' 'ckmq' 'clmp' 'dhiw' 'dhly' 'dhmu' 'dilr' 'dimq' 'dlmo' 'ehij' 'ehky' 'ehmt' 'eikr' 'eimp' 'ekmo' 'fhku' 'fhlt' 'fikq' 'filp' 'fklo') #('adt' 'cdk' 'ddi') #('j') #('aoot' 'biot' 'chot' 'ciop' 'ckoo' 'dioo') #('aalu' 'acll' 'aeil') #('aahiiw' 'aahily' 'aahimu' 'aaiilr' 'aaiimq' 'aailmo' 'abiilm' 'achilm' 'aehiim' 'afhiil') )
▼簡単な解説
dict は各アルファベット文字の手旗の向きとアンドロイドのドット位置との対応を「1文字の文字列(実際はシンボル)-> ドットのパターン(実体は対応する位置に 1 そうでない位置に 0 を置いた配列)」という k->v オブジェクトにして保持しています。
guessesOf は与えられたドットパターンから手旗の文字の組み合わせを推測してそれらを列挙して返す関数(ブロック)です。判定は、与えられたドットパターン(前述の通り実体は整数の配列)から手旗文字のパターン(同)を差し引いて、パターンがすべて 0 になればゴール、ひとつでもマイナスが出たらその先の可能性は破棄、そうでなければ新しい中間状態(後述)を作ってキューに追加、という処理をしています。探索は幅優先で、キューが空になったら探索は終了。キューに収める中間状態は「候補文字群 -> 残っているドットのパターン」という k->v 値で表現しました。