2019年2月11日月曜日

循環リストの応用例その2（Luhnアルゴリズム）

Luhnアルゴリズム（Luhn algorithm）は、
様々な識別番号の認証に使われている単純なチェックサム方式。
たとえば、クレジットカード番号にもこの方式が使われている。
詳細は wikipeida参照。

このLuhnアルゴリズムのさまざな言語での実装が、
Implementation in 88 languages on the Rosetta Code project
に載っているので、そちらを見ていただいても構わない。

で、先日ISBNのコードを書いている途中、
たまたまLuhnアルゴリズムに出くわしたので、
「関数の循環リスト」を使った、schemeでの実装を書いてみた。
なお、入力は文字列として受け取る。
(define (check-luhn num-string)
  (define luhn-digit
    (circular-list (lambda (x) x)
                   (lambda (x) (vector-ref #(0 2 4 6 8 1 3 5 7 9) x))))
  (zero? (remainder (fold + 0 (map (lambda (f x) (f x))
                                   luhn-digit
                                   (reverse (map digit->integer (string->list num-string)))))
                    10)))
;; (check-luhn "1234567812345678")

なんというか、schemeならではの素敵なコードになったと思うので、
ここに記録しておく。

以上
投稿者 時刻:

2019年2月2日土曜日

ISBNチェッカー（循環リストの応用例）

循環リストの応用例

最近、ISBNの入力ミスを発見するためのスクリプトを書いた。
循環リストを使った美しいコードだと思う。

だけど、「循環リスト（Circular list）なんて観念で、
（理論の）完全性のために存在しているだけ」と言われることがある。
また、Googleで「循環リスト」を検索すると
関連検索として「循環リスト 応用例」を提案してくる。

でも、循環リストを使わないと実現しにくいアルゴリズムもあるし、
循環リストはSchemeの楽しさを高めている思っている。
そして私はこよなくschemeを愛している。
だから、ここに実用的な「循環リストの応用例」として
ISBNチェッカーを公開する。

ISBNチェッカー

ISBNは書籍を一意に示すための番号である。
ISBN-13の最後の1桁はチェックデジットであり、以下のように計算される。
----- -----
現行規格のISBN (ISBN-13) のチェックディジットは、JANコードと同じく、「モジュラス10 ウェイト3・1（モジュラス10 ウェイト3）」という計算法にて算出される。（チェックディジットを除いた一番左側の桁から順に1、3、1、3…を掛けてそれらの和を取る。和を10で割って出た余りを10から引く。ただし、10で割って出た余りの下1桁が0の場合はチェック数字を0とする。）
----- -----
「ISBN」（2018年12月21日 (金) 08:59UTCの版）『ウィキペディア日本語版』より引用[注1]。

これを実装すると以下のようになる。ただし、入力は文字列として受け取る。
(use srfi-1)
(define (check-isbn13 num)
  (define weight (circular-list 1 3))
  (zero? (remainder (fold + 0 (map (lambda (x y) (* x y))
                   weight
                   (map digit->integer (string->list num))))
            10)))
「一番左側の桁から順に1、3、1、3…を掛け」るところに循環リストを使っている （(circular-list 1 3)は'(1 3 1 3 ...)となる循環リストを返す。）。
左から1桁ずつループして拾っているのだけど、
掛ける数が1と3で交互なので、
(1 3 1 3 ...)となっている循環リストに対して、
carで先頭を拾って使い、cdrして残りを次のiterationに渡している。
場合分けとかフラグとかを使っていないところが美しいでしょう？

うさぎとかめのアルゴリズム

ところで、あるリストを与えられた時、それが循環リストになっているかをチェックする コードが以下にある。
大変美しく、ぜひご覧いただきたいので、ここで勝手に紹介する。

以上
投稿者 時刻:
登録: 投稿 (Atom)