CodeIQ プログラミング言語☆総選挙の問題をClojureで

先月、CodeIQでプログラミング言語総選挙なるものをやってました。

内容はおおむね、各人が好きな言語へ投票して言語ごとの得票数を競うものでした。まず予備選挙をやって、上位の8言語だけが本選挙に勝ち上がれるというやや手の込んだ形式です。
ユニークなのは、自分のお気に入りの言語へ投票するには与えられた問題をその言語で解かなければいけないという点。選択可能な言語はIdeoneで実行可能であればOKということみたいだったので、Clojureで問題を解いて一票入れてきました。

先週になってようやく問題の解説が出たので、ここで自分の解答を公開しておきます。

問題

細かい制約条件は異なっていたものの、予備選挙・本選挙とも基本的には同じ問題が出題されました。

大雑把には、矩形領域の中に格子状に並ぶすべてのマスに対して、上下左右に隣接するマス同士で重複のないペアを作ることができるかどうかを問う問題でした。ただし、マスには他とペアになれない"穴"が存在することがある設定になっています。

たとえば、以下のような入力の場合("O"が他のマスとペアになれるマス、"X"がペアになれない"穴"を表す)、

OOO
OOO
OOX

次のようなペアの作り方があるので、"yes"と回答します(同じ数字のマスが1つのペアを表すとする)。

112
332
44X

一方で、

OOO
OOX

や

OOO
OOO
OXO

の場合は、どう頑張ってもペアが作れないので"no"と回答します。

解答

解法には単純に深さ優先探索を使いました。問題自体はペアの作り方を求めることを要求してませんが、解答はペアの作り方がある場合には最初に求められたペアの作り方を返すように作ってあります。

(ns codeiq-pairs.core
  (:require [clojure.java.io :as io]
            [clojure.string :as str]))

(defn read-table [rdr]
  (mapv vec (line-seq rdr)))

(defn assign [table index val]
  (when (= (get-in table index) \O)
    (assoc-in table index val)))

;; for debug
(defn print-table [table]
  (println (str/join \newline (map str/join table))))

(defn next-unassigned-cell [table [i j]]
  (letfn [(cells-from [i j]
            (lazy-seq
              (cond (>= i (count table)) nil
                    (>= j (count (first table))) (cells-from (inc i) 0)
                    :else (cons [[i j] (get-in table [i j])]
                          (cells-from i (inc j))))))]
    (ffirst (filter #(= (second %) \O) (cells-from i j)))))

(defn solve
  ([table] (solve table [0 0] 0))
  ([table index n]
     (and table
          (if-let [index' (next-unassigned-cell table index)]
            (let [table' (assign table index' n)
                  next-step #(solve (assign table' (% index') n) index' (inc n))]
              (or (next-step (fn [[i j]] [i (inc j)]))
                  (next-step (fn [[i j]] [(inc i) j]))))
            table))))

(defn -main []
  (if (solve (read-table (io/reader *in*)))
    (println 'yes)
    (println 'no)))

Clojureみたいに、イミュータブル(かつ永続的)なベクタを持っていると、こういうバックトラックもシンプル(かつ比較的効率的)に書けていいですねー。

雑感

結局、選挙自体の結果としては、Clojureは得票数3で11位、残念ながら予備選挙を通過することができませんでした。まぁ、こういうのは母数が多くないとなかなか勝ち上がるのは難しいですねー。Haskellはそれでも本選挙まで残って、C#と並んで5位だったみたいですけどね。何なんでしょうね。あの人気は。

ところで、どう書く？orgが流行ってたくらいの時期には、こうやって「俺はこの問題をこう解いた」みたいなのをそれぞれが自分のブログに掲載したりトラックバック飛ばし合ったりとかよくやってたなぁ、なんていうのを思い出しました。僕はああいう牧歌的な雰囲気が結構好きでした。
最近では、CodeIQみたいなサービスも増えてきて、単に自己顕示欲を満たすだけじゃなくて、自分の解答した成果が就職にもつながるかもしれなかったりして、まったく便利な世の中になったもんです。でもその分、「この解答は公開しちゃダメだ」とか気にしなきゃいけなくなって、昔よりもギスギスした雰囲気になったようにも感じます。まぁ、「昔はよかった」なんて懐古に走るようになったのは、単純に今の自分が昔より歳を取ったってだけなのかもしれないけど。