Problem 79 - セキュリティキーを解読せよ
これは面白かった。
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may asked for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.
セキュリティキーがあるんだけど、そのうちの3文字かがランダムでkeylog.txtに記録される。
531278の中から、3,1,8をランダムに記録した。みたいな感じ。
kyelog.txtからセキュリティキーを解読せよ。という問題。
kyelog.tetの最初のほうはこんなん。
319
680
180
690
129
620
762
689
思考手順を考えてみる。
319と680か。まだわからないな。
お、180があるから、3 1 (9 6) 8 0という並びになるなぁ。
次が、690だから、3 1 6 9 8 0になる。決定。
と、柔軟にやっていける。簡単なもんだ。
(実はこの時点で6の位置は決まっていない)
人間なら簡単なんだけど、コンピュータじゃ結構大変で・・・むにゃむにゃ・・・ぷしゅー
ま、人間の思考をシミュレートするのは大変なので、総当り作戦で行くことにした。
フェーズは2個。
- まず、一番最初に現れる数字を探す。
- １個ポップしておいて、2番目以降にその文字が現れたら入れ替える。
- 一番最初に現れた数字を消す。
- 全部なくなるまで繰り返す。
一番最初にある奴は2番目以降には登場しないのだよ。
ははは、予測なんぞイラン！！
(define (problem79 data) (letrec ((search (lambda (d) (fold-right (lambda (l f) (if (find (lambda (k) (= k f)) (cdr l)) (car l) f)) (caar d) d))) (delete (lambda (s d) (fold-right (lambda (l acc) (let ((r (remove (lambda (i) (eq? i s)) l))) (if (null? r) acc (cons r acc)))) '() d))) (iter (lambda (d) (if (null? d) '() (let ((s (search d))) (cons s (iter (delete s d)))))))) (iter (map number->list data)))) (problem79 *log*) ; (7 3 1 6 2 8 9 0)
イマイチみたい。
バグあり
どうやら、バグがあるみたいだ。
一直線に読んでるだけではダメで、新しいのが見つかったら戻り読む必要がある。
C D A B B C
僕のは先頭から、C A Bと見て行って、Bが先頭になっちゃう。
ダメなパターン
B C A D C D
このシステムではAとBどちらが先か判断できない。
と思ったら、人間でも判断できないな。
Dの前に、B CとAがある。そこまでの状況までしかわからない。
一番先頭にあるものは二番目以降に現れないという理論はとりあえず間違いない！？
バグ修正
とりあえず、戻り読みに対応した。
単純に順番が悪い時。
C D A B B C
C D, B Cと見たら、Bの方が前にあった。
つまり、Bの前にある可能性があるので、戻ってやり直す。
(define (problem79 data) (letrec ((search (lambda (acc f d) (cond ((null? d) f) ((find (lambda (k) (eq? k f)) (cdar d)) (search '() (caar d) (append acc d))) (else (search (cons (car d) acc) f (cdr d)))))) (delete (lambda (s d) (fold-right (lambda (l acc) (let ((r (remove (lambda (i) (eq? i s)) l))) (if (null? r) acc (cons r acc)))) '() d))) (iter (lambda (d) (if (null? d) '() (let ((s (search () (caar d) d))) (cons s (iter (delete s d)))))))) (iter data)))
trace結果を見ると、
(problem79 '((C D) (A B) (B C))) ;|(search () C ((C D) (A B) (B C))) ;|(search ((C D)) C ((A B) (B C))) ;|(search ((A B) (C D)) C ((B C))) ;|(search () B ((A B) (C D) (B C))) <-やりなおし ;|(search () A ((A B) (C D) (B C))) <-やりなおし ;|(search ((A B)) A ((C D) (B C))) ;|(search ((C D) (A B)) A ((B C))) ;|(search ((B C) (C D) (A B)) A ()) ;|A ;|(search () C ((C D) (B) (B C))) ;|(search ((C D)) C ((B) (B C))) ;|(search ((B) (C D)) C ((B C))) ;|(search () B ((B) (C D) (B C))) <-やりなおし ;|(search ((B)) B ((C D) (B C))) ;|(search ((C D) (B)) B ((B C))) ;|(search ((B C) (C D) (B)) B ()) ;|B ;|(search () C ((C D) (C))) ;|(search ((C D)) C ((C))) ;|(search ((C) (C D)) C ()) ;|C ;|(search () D ((D))) ;|(search ((D)) D ()) ;|D ;(A B C D)
じっくり。慎重に進みます。
いらんこと思いついた
重複あり。
ムリすぎなので、今度じっくり考える。
お、
一列に見て行っても先頭の可能性があるものと、無いものに分ければ、戻り読む必要は無くなるようだ。
