パスワードを忘れた? アカウント作成
7533636 story
プログラミング

正規表現クロスワード、解ける? 15

ストーリー by headless
出題 部門より
ヒントがすべて正規表現で書かれたクロスワードパズルが本家/.で紹介されている(A Regular Crossword: PDFI Programmerの記事本家/.)。

このクロスワードは1月の「2013 MIT Mystery Hunt」で出題されたパズルの1つ。各列のヒントは「.*H.*H.*」のような正規表現で書かれており、難易度を上げるため3つの列が交差する6角形のグリッドを使用している。ただし、答えは意味のある語句にならないため、I Programmerの記事で指摘されているように、クロスワードというよりも数独に近いようだ。
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • これはピクロスを拡張したゲーム、と捉えた方が良いと思います

    ピクロスは 絵の画素の並びを 3 1 2 という数字列で表現しますが、
    これを正規表現に代えて、さらに画素を文字列に置き換えると、
    このregular crosswordになります。

    (ただしピクロスは縦横の2方向だけど、regular crosswordは3方向。しかし
    この拡張は手間が爆発的に増えるだけで、ゲームのルールには無影響)

    なので、ピクロスと同じ解法・戦略が使える筈。

  • by Anonymous Coward on 2013年02月16日 17時55分 (#2326676)

    スラドは超短時間でできる気分転換 [srad.jp]に向いてないな!全く!

  • by Anonymous Coward on 2013年02月16日 22時14分 (#2326795)

    「正規表現」と「数独」で思いついたんだけど
    「1~9の数字をそれぞれ1度だけ使った9桁の数字」にマッチする正規表現ってあるのかな?
    ぜんぜんアイデアが沸かない

    • ものすごく長い正規表現であれば可能ですね。これ以外のスマートな書き方は思いつきません。

      --
      HIRATA Yasuyuki
      親コメント
    • by Anonymous Coward

      9!通りの可能性を全部書き出して | で並べる。

      • by Anonymous Coward on 2013年02月17日 0時43分 (#2326894)

        それしかないね。
        『1~9の数字をそれぞれ1度だけ』を人間がスマートにやろうとすると、入力を読んでいくときに『それまでにどの数が出現したか』を覚えておこうとするのが普通だろう。
        それに対し、正規表現は『入力をどこまで読んだか』『正規表現のどこまでがマッチしたか』ということしか状態を持てない。
        そういう問題を文法でどうにかするのは向いてないな。

        親コメント
        • by Anonymous Coward on 2013年02月17日 1時05分 (#2326903)

          とか思ったけど、古典的な正規表現だと無理でも、
          ほかの人が言っている通り後方参照が使える言語ならベタに展開しなくてもできるね。
          あんまり書きやすくはないし、かなり長いけど……

          3文字だけの例:
          http://ideone.com/T8Zxww [ideone.com]

          親コメント
        • by Anonymous Coward

          数学者は(計算複雑性理論とか計算機科学とかの一部の分野を除くと)効率を考慮しないから有限の長さの正規表現で書けるなら「書ける」という結論にしかならないけどな。下手すると実際に正規表現を書き下すことなしに存在を示すだけ。

    • by Anonymous Coward
      (\d)(?!\1)(\d)(?!\1|\2)(\d)(?!\1|\2|\3)(\d)(?!\1|\2|\3|\4)(\d)(?!\1|\2|\3|\4|\5)(\d)(?!\1|\2|\3|\4|\5|\6)(\d)(?!\1|\2|\3|\4|\5|\6|\7)(\d)(?!\1|\2|\3|\4|\5|\6|\7|\8)(\d)

      これじゃだめかな?
      正規表現とは呼べないかもしれないけど。
      • by Anonymous Coward

        0は入らないから駄目じゃ?

        • by Anonymous Coward
          ああ、うっかりしてた。じゃあ (\d) の代わりに ([1-9]) で。
    • by Anonymous Coward

      「そういうものだけが単独で現れる行」になら
      ^(?!.*(.).*\1)[1-9]{9}$
      でマッチさせられる。
      他の文字列の中にそういうものが混じっている場合にはこの手は使えないけど。

    • by Anonymous Coward

      (?=.*1.*)(?=.*2.*)(?=.*3.*)(?=.*4.*)(?=.*5.*)(?=.*6.*)(?=.*7.*)(?=.*8.*)(?=.*9.*)[1-9]{9}

typodupeerror

最初のバージョンは常に打ち捨てられる。

読み込み中...