章の途中で定義したlast-nameを改造して、タイトル（っていうんか？）を取り扱えるようにする。 考えられるケースは取り扱えって言っても、どんな慣習があるんでしょう？ 取りあえず例題のケースだけに対応。 ;;; Exercise 1.1 [m] Define a version of last…

L-99もP46以降からPrologの問題そのままになってきた。 取りあえず、この辺りでいったん終了。PAIP本でPrologの実装を調べてくるか。 ;; P54A (defun istree (tree) (cond ((null tree) t) ((not (consp tree)) nil) ((not (= (length tree) 3)) nil) (t (an…

指定した範囲に対するgoldbach conjectureの結果を整形して表示。goldbach-rangeは後の、条件を超える素数の組の数を求める問題のために分離しておいた。 ;; P41 (defun goldbach-range (start end &optional (pred #'identity)) (remove-if #'(lambda (n) (…

P22で定義したrangeと、P31で定義したprime-pを使う。 ;; P39 (defun prime-list (m n) (remove-if-not #'prime-p (range m n))) (prime-list 50 100) ;; => (53 59 61 67 71 73 79 83 89 97)

g000001さんの解法を参考にさせてもらいました。まずは、次の素数を見つける関数next-primeを定義。 例によって、P31のprime-pを使います。 (defun next-prime (n) (if (prime-p (1+ n)) (1+ n) (next-prime (1+ n)))) (next-prime 40) ;; => 41 奇数と2は対…

ACLで動作確認。 P34の実装はconsしまくっている模様。 CL-USER> (time (totient-phi 65535)) ; cpu time (non-gc) 540 msec user, 10 msec system ; cpu time (gc) 130 msec user, 0 msec system ; cpu time (total) 670 msec user, 10 msec system ; real …

L-99の問題文では各素数の演算に対する和になっているけど、どうも積っぽい。参照：http://www.geocities.com/hmaxf_urlcr/euler.htm [音が出るので注意] ;; P37 (defun fold1 (func n lis) (if (null lis) n (fold1 func (funcall func n (car lis)) (cdr l…

;; P36 (defun prime-factor-mult (n) (labels ((append-val (m res) (cond ((null res) (list (list m 1))) ((= m (caar res)) (incf (cadar res)) res) (t (cons (list m 1) res)))) (iter (n m limit res) (cond ((> m limit) (reverse (append-val n res…

整数mに対しcoprimeである整数r (1 P33の結果を使い、直接的に実装。 もっとスマートな方法は、後の問題で議論するらしい。 ;; P34 (defun totient-phi (m) (do ((result 0 (if (or (= n 1) (coprime m n)) (1+ result) result)) (n m (1- n))) ((< n 1) res…

直接的に実装。 本当は、mは1+ではなく、次の素数を返す関数で増加させたいところ。 ;; P35 (defun prime-factor (n) (labels ((iter (n m limit res) (cond ((> m limit) (reverse (cons n res))) ((= (mod n m) 0) (iter (/ n m) m (sqrt (/ n m)) (cons m…

椅子から立ち上がったら腰のあたりで「パキッ」という音が…。 歩くのも辛い状況。腰曲がってます。 明日、接骨院に行くか…。

gcdが1を返す整数の組をcoprimeというらしい。 ;; P33 (defun coprime (m n) (= (gcd m n) 1)) (coprime 35 64) ;; => T 日本語では、「互いに素」 以下を参照。 http://homepage3.nifty.com/kanzakijuku/a07.html

これもSICPから。 ;; P32 (defun my-gcd (m n) (cond ((< m n) (my-gcd n m)) ((= n 0) m) (t (my-gcd n (rem m n)))))

SICPの1.2.6から。 ;; P31 (defun square (x) (* x x)) (defun expmod (base exp m) (cond ((= exp 0) 1) ((evenp exp) (rem (square (expmod base (/ exp 2) m)) m)) (t (rem (* base (expmod base (- exp 1) m)) m)))) (defun fermat-test (n) (labels ((t…

P27はリストをグループ分けする問題。 P26で定義したcombinationを流用する。 まずは、9要素のリストを2 3 4の要素に分割する関数 group3をつくる。 その後に、分割パターンをリストとして受け取る関数 groupをつくる。groupは、順番が違うだけで、実質同じ…

サブリストの長さで並び替える。 さらに、サブリストの長さの頻度で並び替える。まずは、sort関数を定義。 (defun my-sort (lis smaller-p &key (key #'identity)) (if (null lis) nil (do ((x (car lis)) (bigger '()) (smaller '()) (l (cdr lis) (cdr l))…

リストからn個の要素を取り出す。 取り得る全てのパターンをリストとして列挙する。 ;; P26 (defun combination (n list) (cond ((or (= n 0) (null list)) nil) ((= n 1) (mapcar (lambda (res) (cons res nil)) list)) (t (append (mapcar (lambda (res) (…

P22,P23の結果を使う。 P24では、1〜mまでの整数からn個の整数を重複無しに選択する。 P25では、リストをランダムに並べ替える。 ;; P24 (defun lotto-select (n m) (rnd-select (range 1 m) n)) (time (lotto-select 6 49)) ;; => (7 14 37 11 33 43) ;; P2…

multiple-value-bindは使ってみたかっただけです。はい。 ;; P23 (defun nth-and-remove (n list &optional (acc nil)) (if (or (<= n 0) (null list)) (values (car list) (append (nreverse acc) (cdr list))) (nth-and-remove (1- n) (cdr list) (cons (c…

endからstartへ寄せることにより、reverseを省略してみた。 ;; P22 (defun range (start end) (do ((op (if (> end start) #'1- #'1+)) (i end (funcall op i)) (acc '())) ((= i start) (push i acc)) (push i acc))) (range 1 10) ;; => (1 2 3 4 5 6 7 8 …

副作用ばりばりで。 ;; P13 (defun encode-direct (lis) (if (null lis) lis (do ((acc '()) (target (car lis)) (count 1) (l (cdr lis) (cdr l))) ((null l) (reverse (cons target acc))) (if (and (eql target (car l))) (incf count) (progn (push (if …

そろそろPSP版の海腹川背が発売するらしいという情報を もらったので、調べてみた。けっこう、ひどい出来らしい。 ↓http://www32.atwiki.jp/kawasepsp/pages/12.html曰く、 ロープが壁に張り付く ロープが壁にめり込む ロープが壁をすり抜ける etc …海腹川背…

g:cadr:id:g000001:20080321の記事をみて、パターンマッチが無性に使いたくなったのでGaucheで実装してみる。末尾再帰にしなければ、意外とすっきり書ける？ (use util.match) (define (encode-direct lis) (match lis [() '()] [(a) (list a)] [((num a) . …

だいたい同様の手順で解ける細かい問題。pushして最後にreverse。 ;; P14 (defun dupli (list) (let ((acc '())) (dolist (elm list) (dotimes (i 2) (push elm acc))) (reverse acc))) (dupli '(a b c d e)) ;; => (A A B B C C D D E E) ;; P15 (defun rep…

pushが結構便利。 ;;; ;; P09 (**) Pack consecutive duplicates of list elements into sub-lists. ;; If a list contains repeated elements they should be placed in separate ;; sub-lists. ;; ;; Example: ;; * (pack '(a a a a b c c a a d e e e e )…

(car nil) (cdr nil)がそれぞれnilを返すのを忘れててはまりました。 ;;; ;; P08 (**) Eliminate consecutive duplicates of list elements ;; If a list contains repeated elements they should be replaced with a single ;; copy of the elemnt. The ord…

consだったら再帰で木を下る。 結果はaccに溜めていって、最後にreverse。 ;;; ;; P07 (**) Flatten a nested list structure. ;; Transform a list, possibly holding lists as elemnts into a 'flat' list by ;; Replacing each list with its elements (r…

少し悩んだけど、簡単な方法で。 ;;; ;; P06 (*) Find out whether a list a palindrome. ;; A palindrome can be read forward or backward; e.g. (x a m a x) ;; Example: ;; * (palindrome-p '(a b c b a)) ;; t ;; * (palindrome-p '(a b c b)) ;; nil (…

;;; ;; P12 (**) Decode a run-length encoded list. ;; Given a run-length code list generated as specified in ;; problem P11. Construct its uncompressed version. (defun decode (lis) (let ((acc nil)) (dolist (elem lis) (cond ((atom elem) (pus…

;;; ;; P11 (*) Modified run-length encoding. ;; Modify the result of problem P10 in such a way that if an element ;; has no duplicates it is simply copied into the result list. ;; Only elements with duplicates are transferred as (N E) list…