9月に中途で入社した@wat-aroです．
前職はプログミングと全く関係のない仕事でしたが，プログラムを書く仕事がしたくて退職しました．
退職してからはまず基礎を身につけようとSICPを読み，ほとんどの問題を解き終わったのでFjrodのリモートインターンに参加して勉強していました．
今日は永和システムマネジメントの技術面接で出されたアルゴリズムの問題を紹介しようと思います．
出された問題はアナグラムの判定です．
アナグラムとは文字列の順番を入れかえて，別の文字列になっているものです．
eros と rose は文字の順番を入れ替えているだけなのでアナグラムです．
eros と lose は文字を入れ替えただけでは一致しないのでアナグラムではありません．
これを判定するコードを書きます．
面接ではRubyで書くのが難しければ疑似コードでもいいし，口頭でアルゴリズムを説明するだけでもいいと言われたので慣れているSchemeで考えることにしました．
さらに文字列は考えにくいのでリストで考えることにしました．
まずは一致する条件を考えます．
二つのリストの要素を順に比べていって，最後に両方のリストが空ならtrueです．
片方が空なのに，もう片方にまだ要素が残っていれば要素の数が違うのでfalseです．
ここまでをとりあえず書いてみます．
(define (anagram lst1 lst2) (cond ((and (null? lst1) (null? lst2)) #t) ((or (null? lst1) (null? lst2)) #f) (else ...)))
次にlst1の最初の要素をlst2から取り除く補助関数を作ります．
lst1の最初の要素がlst2に含まれていなければfalseを返してくれると
含まれているかの判定と次の再帰で使うリストの作成が同時にできるのでそのようにします．
もちろん，末尾再帰のほうが嬉しいのでそうします．
(define (remove-item item lst result) (cond ((null? lst) #f) ((eq? (car lst) item) (append (reverse result) (cdr lst))) (else (remove-item item (cdr lst) (cons (car lst) result)))))
これを最初の関数に組み合わせます．
(define (anagram lst1 lst2) (define (remove-item item lst result) (cond ((null? lst) #f) ((eq? (car lst) item) (append (reverse result) (cdr lst))) (else (remove-item item (cdr lst) (cons (car lst) result))))) (cond ((and (null? lst1) (null? lst2)) #t) ((or (null? lst1) (null? lst2)) #f) (else (let ((removed-list (remove-item (car lst1) lst2 '()))) (if removed-list (anagram (cdr lst1) removed-list) #f)))))
動かしてみると
gosh> (anagram '(e r o s) '(r o s e)) #t gosh> (anagram '(e r o s) '(r o s )) #f gosh> (anagram '(e r o s) '(l o s e)) #f gosh> (anagram '(e r o) '(r o s e)) #f
大丈夫そうですね．
実際の面接では後半は口頭で説明しただけでした．
リストをこねくり回すのは楽しいですね．
動きそうだということで答え合わせです． モニタに写されたコードは次のようなものでした．
def anagram(s1, s2) s1.chars.sort == s2.chars.sort end
とても簡単です… 最後に悔しくなりましたが，ホワイトボードに向かってLispを書くのは楽しかったです．
