Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2007-09-10

L-99 (55)

| 22:42 | L-99 (55) - わだばLisperになる を含むブックマーク はてなブックマーク - L-99 (55) - わだばLisperになる

L-99 P55に挑戦 - L-99:Ninety-Nine Lisp Problems

実に4ヶ月ぶり。以前、12時間考えてどうにも分からな

かった問題を思い出して再挑戦。

しかし、久しぶりに考えてみたら案外あっさりできた。

難しく考え過ぎてたらしい。

残りの問題:'(58-60 63 66 80-94 96-99) 解答状況 61/84

P55

解答
;; Common Lisp
;; -----------------------------------------------------------------------------
(defpackage l99 (:use #:cl))

(in-package :l99)

(defun cbal-tree (n)
  (if (zerop n)
      '(())
      (if (>= 1 n)
	  '((x () () ))
	  (reduce (lambda (res x) 
		    (let ((tree `(x ,@x)))
		      (if (cbal-tree-p tree)
			  `(,tree ,@res)
			  res)))
		  (let ((half (/ (1- n) 2))) ;balanced
		    (if (zerop (mod half 1))
			(comb2 (cbal-tree half)
			       (cbal-tree half))
			(let ((g (ceiling (/ (1- n) 2))) ;greater
			      (l (truncate (/ (1- n) 2)))) ;less
			`(,@(comb2 (cbal-tree l)
				   (cbal-tree g))
			    ,@(comb2 (cbal-tree g)
				     (cbal-tree l))))))
		  :initial-value () ))))

(defun cbal-tree-p (tree)
  (>= 1 (abs (- (count-leaf (cadr tree))
		(count-leaf (caddr tree))))))

(defun count-leaf (tree)
  (if tree
      (+ 1 (count-leaf (cadr tree)) (count-leaf (caddr tree)))
      0))

(defun comb2 (xs ys)
  (mapcan (lambda (y)
	    (mapcar (lambda (x) `(,x ,y)) xs))
	  ys))
テスト
(defun ppt (tree) (mapc #'print tree))

(ppt (cbal-tree 4))
=>
 (X (X NIL (X NIL NIL)) (X NIL NIL)) 
 (X (X (X NIL NIL) NIL) (X NIL NIL)) 
 (X (X NIL NIL) (X NIL (X NIL NIL))) 
 (X (X NIL NIL) (X (X NIL NIL) NIL))

ゲスト



トラックバック - http://cadr.g.hatena.ne.jp/g000001/20070910