METHINKS IT IS A WEASEL
Posted feedbacks - Common Lisp
kozima
#6288()
[
Common Lisp
]
近さのうまい定義ってそんなに自明じゃないんですね。下のプログラムではアスキーコードの差を足していますが、もっといい方法がありそうです。
文字変化のやり方も焼きなまし法を使うとかいろいろ考えられそうです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | (defun random-char (&optional random-state)
(code-char (+ 65 (random 26 random-state))))
(defun random-string (length &optional random-state)
(let ((s (make-string length)))
(dotimes (i length)
(setf (elt s i) (random-char random-state)))
s))
(defun modify (s &optional random-state)
(let ((i (random (length s) random-state))
(r (copy-seq s)))
(setf (elt r i)
(code-char (+ (random 3 random-state)
(char-code (elt s i))
-1)))
r))
(defun weasel (target)
(let ((state (make-random-state t)))
(flet ((key (s)
(loop for c1 across s and c2 across target
sum (abs (- (char-code c1) (char-code c2))))))
(do ((strings (loop repeat 300
as s = (random-string (length target) state)
collect (cons s (key s)))
(sort (mapcan (lambda (p)
(loop repeat 3
as s = (modify (car p) state)
collect (cons s (key s))))
strings)
#'< :key #'cdr))
(i 1 (1+ i)))
((string= target (caar strings))
(format t "~D: ~A (~D)~%" i (caar strings) (cdar strings))
(format t "Finished after ~D steps.~%" i))
(setf (cdr (nthcdr 299 strings)) nil)
(format t "~D: ~A (~D)~%" i (caar strings) (cdar strings))))))
(weasel "METHINKSITISAWEASEL")
|
ytakenaka
#6287()
Rating4/8=0.50
ランダムな文字からMETHINKS IT IS A WEASELを作るプログラムを作れ。
簡単に流れを書いてみます。
１：ランダムな２０文字を持つ文字列をもった３００個作ります。
２：その文字列が"METHINKSITISAWEASEL"に近いものからソートします。
３：それぞれの文字列のなか1文字を別の文字に変化させたものを３つ用意します。
４：それを２：のソートをして上位３００個残す。（９００個あるうちで上位３００個残すということです。）
５：以後３：と４：を繰り返す。
ランダムな文字変化は大文字だけでいいです。簡単にするために空白文字を外してあります。
METHINKS IT IS WEASELができたら終了。３と4の間でソートしたもので一番上位のものを毎回表示させると変化が楽しめます。:-)
Rickard Dawkinsがブラインドウォッチメイカー(現題：盲目の時計職人）の３章で書いていた有名なものです。さらに一般化してもらってもいいです。
参考
[ reply ]