データが扱える人を探せ！

xyzzy lisp

JAVA５．０でGO!! | プログラミングに自信があるやつこい！！


というわけで、気楽に作ってみた。topcoderからの出題なのね。

(defun who-can-see (usrs ability needs)
  (let ((l (mapcar (lambda (x y) (list x (split-string y #\SPC))) usrs ability)))
    (dolist (a needs)
      (setq l (remove-if-not (lambda (x) (find a x :test 'string=)) l :key 'cadr)))
    (mapcar 'car l)))

問題読んでからテスト終えるまで12分15秒。問題読むのに5分くらいかかったからちょっと時間オーバー。テストケースが複雑なんだって。

(who-can-see '("joe" "nick" "ted")
               '("clients products" "products orders" "clients orders")
               '("products" "clients"))
|("joe")
(who-can-see '("kathy" "john" "dan" "steve" "cheryl" "tony")
               '("users data" "data orders" "users permissions" "system users controls" "default" "admin users")
               '("users"))
|("kathy" "dan" "steve" "tony")
(who-can-see '("jim" "scott" "barbara")
               '("users order products" "products shipping" "tracking products orders")
               '("admin"))
| nil

引数の通りだと扱いにくいので、人と技能をまとめる。技能は予め要求と同じ形に直しておく。そうしたら要求1つごとに技能から探して、持ってない人から除去。残っている人を出力。という感じで作った。cadrがcdrで良いかと思い違ったので、そこを直すのに少し手間取ったり。


一応、よりエレガント（？）にletもdolistもsetqも省いたバージョン。こうなれば純粋関数型である（多分）。一つの関数にしたけど、実際は各段階で分けた方が分かりやすい。そこら辺はhaskellのwhereみたいに書けると格好いいのだが。

(defun who-can-see (usrs ability needs)
  (mapcar 'car
          (reduce (lambda (l a) (remove-if-not (lambda (x) (find a x :test 'string=)) l :key 'cdr))
                  (cons (mapcar (lambda (x y) (cons x (split-string y #\SPC))) usrs ability)
                        needs))))

見やすいように分割した例。どこでデータに手を加えるかで分割の仕方が色々考えられる。読みやすく書けるようになるにはかなりの知識と経験が必要だ。

(defun who-can-see (usrs ability needs)
  (mapcar 'car (who-can-see-sub (mapcar 'wcs-merge usrs ability) needs)))

(defun who-can-see-sub (data needs)
  (reduce 'wcs-remove (cons data needs)))

(defun wcs-remove (l a)
  (remove-if-not (lambda (x) (find a x :test 'string=)) l :key 'cdr))

(defun wcs-merge (x y)
  (cons x (split-string y #\SPC)))

(who-can-see '("joe" "nick" "ted")
'("clients products" "products orders" "clients orders")
'("products" "clients"))


それにしても、こういう形式のデータはlispにも向いてないし、オブジェクト指向にもなってない気がするけど、何を想定した例題なんだろう。簡単な例題だから良いのか。