正規表現クロスワード、解ける？ 15
ストーリー by headless
出題 部門より
出題 部門より
ヒントがすべて正規表現で書かれたクロスワードパズルが本家/.で紹介されている(A Regular Crossword: PDF、
I Programmerの記事、
本家/.)。
このクロスワードは1月の「2013 MIT Mystery Hunt」で出題されたパズルの1つ。各列のヒントは「.*H.*H.*」のような正規表現で書かれており、難易度を上げるため3つの列が交差する6角形のグリッドを使用している。ただし、答えは意味のある語句にならないため、I Programmerの記事で指摘されているように、クロスワードというよりも数独に近いようだ。
このクロスワードは1月の「2013 MIT Mystery Hunt」で出題されたパズルの1つ。各列のヒントは「.*H.*H.*」のような正規表現で書かれており、難易度を上げるため3つの列が交差する6角形のグリッドを使用している。ただし、答えは意味のある語句にならないため、I Programmerの記事で指摘されているように、クロスワードというよりも数独に近いようだ。
ピクロスの拡張と捉えるべき (スコア:3)
これはピクロスを拡張したゲーム、と捉えた方が良いと思います
ピクロスは 絵の画素の並びを 3 1 2 という数字列で表現しますが、
これを正規表現に代えて、さらに画素を文字列に置き換えると、
このregular crosswordになります。
（ただしピクロスは縦横の２方向だけど、regular crosswordは３方向。しかし
この拡張は手間が爆発的に増えるだけで、ゲームのルールには無影響）
なので、ピクロスと同じ解法・戦略が使える筈。
Re:ピクロスの拡張と捉えるべき (スコア:1)
ピクロスも、例えば「3 1 2」の場合の3と1の間の空白がゼロ個を許すならば、結構面倒になると思う。
＃思うだけで、検証したわけではないけど。
Re:ピクロスの拡張と捉えるべき (スコア:3, 参考になる)
実際にクリアしてみましたけど、「*?でゼロ個」等の引っかけがあり得るのがピクロスと違う感じですね。
あと、グループマッチの使い方が面白いです。
休日出勤の時間が奪われる (スコア:3, おもしろおかしい)
スラドは超短時間でできる気分転換 [srad.jp]に向いてないな！全く！
[1-9]{9} じゃなくて (スコア:2, 興味深い)
「正規表現」と「数独」で思いついたんだけど
「1～9の数字をそれぞれ1度だけ使った9桁の数字」にマッチする正規表現ってあるのかな？
ぜんぜんアイデアが沸かない
Re:[1-9]{9} じゃなくて (スコア:2)
ものすごく長い正規表現であれば可能ですね。これ以外のスマートな書き方は思いつきません。
HIRATA Yasuyuki
Re: (スコア:0)
9!通りの可能性を全部書き出して | で並べる。
Re:[1-9]{9} じゃなくて (スコア:1)
それしかないね。
『1～9の数字をそれぞれ1度だけ』を人間がスマートにやろうとすると、入力を読んでいくときに『それまでにどの数が出現したか』を覚えておこうとするのが普通だろう。
それに対し、正規表現は『入力をどこまで読んだか』『正規表現のどこまでがマッチしたか』ということしか状態を持てない。
そういう問題を文法でどうにかするのは向いてないな。
Re:[1-9]{9} じゃなくて (スコア:1)
とか思ったけど、古典的な正規表現だと無理でも、
ほかの人が言っている通り後方参照が使える言語ならベタに展開しなくてもできるね。
あんまり書きやすくはないし、かなり長いけど……
３文字だけの例：
http://ideone.com/T8Zxww [ideone.com]
Re: (スコア:0)
数学者は(計算複雑性理論とか計算機科学とかの一部の分野を除くと)効率を考慮しないから有限の長さの正規表現で書けるなら「書ける」という結論にしかならないけどな。下手すると実際に正規表現を書き下すことなしに存在を示すだけ。
Re: (スコア:0)
これじゃだめかな？
正規表現とは呼べないかもしれないけど。
Re: (スコア:0)
0は入らないから駄目じゃ？
Re: (スコア:0)
Re: (スコア:0)
「そういうものだけが単独で現れる行」になら
^(?!.*(.).*\1)[1-9]{9}$
でマッチさせられる。
他の文字列の中にそういうものが混じっている場合にはこの手は使えないけど。
Re: (スコア:0)
(?=.*1.*)(?=.*2.*)(?=.*3.*)(?=.*4.*)(?=.*5.*)(?=.*6.*)(?=.*7.*)(?=.*8.*)(?=.*9.*)[1-9]{9}