L-99 P70d

たまにはプログラミングの話題でも書きますか。

L-99 の p70 です。p70 は既出なので、「d」を付けました。
(あちこちの問題で間違いがあるような気がします。元は Prolog の問題集なので仕方ないかな。意味がよくわからないものもあります。)

a f g ^ ^ c ^ b d ^ e ^ ^ ^

こんなノード文字列が与えられた時にマルチウェイツリーを作りなさい、という問題。
ハットはバックトラックを表すマークです。

(define ht (make-hash-table 'equal?))
(define p-node nil)

(define (entry node) (car node))
(define (parent node) (cadr node))
(define (child node) (caddr node))
(define (branch node) (cadddr node))

(define (set-p-node! entry) (set! p-node entry))
(define (set-parent! node entry) (set-car! (cdr node) entry))
(define (set-child! node entry) (set-car! (cddr node) entry))
(define (set-branch! node entry) (set-car! (cdddr node) entry))

(define (make-node entry parent child branch)
  (hash-table-put! ht entry (list entry parent child branch))
  (set-p-node! entry))

(define (backtrack)
  (let ((node (hash-table-get ht p-node nil)))
    (if (null? node)
	(error "BACKTRACK ERROR")
	(set-p-node! (parent node)))))

(define (add-branch entry)
  (define (last-branch entry)
    (let ((node (hash-table-get ht entry nil)))
      (if (null? node)
	  p-node
	  (begin
	    (set-p-node! entry)
	    (last-branch (branch node))))))
  (let ((node (hash-table-get ht p-node nil)))
    (if (null? node)
	(error "ADD BRANCH ERROR")
	(begin
	  (last-branch (child node))
	  (let ((child (hash-table-get ht p-node nil)))
	    (make-node entry (parent child) nil nil)
	    (set-branch! child entry))))))

(define (add-child entry parent)
  (let ((node (hash-table-get ht p-node nil)))
    (if (null? node)
	(error "ADD CHILD ERROR")
	(begin
	  (make-node entry parent nil nil)
	  (set-child! node entry)))))

(define (construction-mtree root)
  (define (iter e)
    (let ((node (hash-table-get ht e nil)))
      (if (null? node)
	  nil
	  (append
	   (list (list (entry node) (iter (child node))))
	   (iter (branch node))))))
  (let ((node (hash-table-get ht root nil)))
    (list root (iter (child node)))))

(define (parse-node-string lst)
  (define (iter l p)
    (if (null? l)
	ht
	(begin
	  (cond ((null? p) (make-node (car l) nil nil nil))
		((eq? (car l) '^) (backtrack))
		((eq? p '^) (add-branch (car l)))
		(else (add-child (car l) p)))
	  (iter (cdr l) (car l)))))
  (hash-table-clear! ht)
  (iter lst nil))
  
(define (list->mtree lst)
  (begin
    (parse-node-string lst)
    (construction-mtree (car lst))))

バックトラックは Lisp らしいコードを書いていたのでは出来ない気がしたので、
外部変数使っています。きれいなコードとは言えません。
あと外部変数はアスタリスクで括るのが一般的です。

(define *ht* (make-hash-table 'equal?))
(define *p-node* nil)

みたいに。

バックトラックしないといけないので、
ノード文字列をパースしてノードの情報(リスト)を作ります。
親の情報を持たせるのがポイントです。

(ノードエントリ 親ノード 子ノード ブランチノード)

各ノードを見てみると、

gosh> (define zzz (parse-node-string '(a f g ^ ^ c ^ b d ^ e ^ ^ ^)))
zzz
gosh> (hash-table-get zzz 'a)
(a () f ())
gosh> (hash-table-get zzz 'f)
(f a g c)
gosh> (hash-table-get zzz 'g)
(g f () ())
gosh> (hash-table-get zzz 'c)
(c a () b)
gosh> (hash-table-get zzz 'b)
(b a d ())
gosh> (hash-table-get zzz 'd)
(d b () e)
gosh> (hash-table-get zzz 'e)
(e b () ())

という感じのものをハッシュテーブルに持ちます。
なお、p-node は現在処理中のノードを指し示すポインターもどきです。

これが出来てしまえば後は簡単です。

gosh> (list->mtree '(a f g ^ ^ c ^ b d ^ e ^ ^ ^))
(a ((f ((g ()))) (c ()) (b ((d ()) (e ())))))

という感じでマルチウェイツリーが出来上がりました。
図を書かないとなかなかわかりにくいですが、
p70, p70b それから p70c の問題を解くと、
見ただけでもなんとなくわかるようになるかも？です。

マルチウェイツリー図は紙に書いたのですが、
それをテキストに起こすの面倒くさいので、
誠に勝手ながら省略させていただきました。

新元号発表と密かな楽しみ

新元号が発表されましたね。

来月１日から令和元年。

最近は電子マネーで支払いする事が多くて、

なかなか現金でお釣りをもらうことが少なくなりました。

いつ「令和元年」と刻印された硬貨が自分の

財布にやってくるか楽しみですｗ

ポン子はかわいいな

これはきれいなポン子。素晴らしいです。

いろんなメディアから来る人が居ると思うけど、

いろいろ調べると「あれ？」ってなるかもｗ

「ウスゲ（注：地名です）は寒い？」

を連呼して、とどめは

「帽子はかぶったほうがいいですか？」

ってｗ

「飛ばされないように風が・・・」って、完全にｈｇ煽りじゃねーかｗｗｗ

結論：ポン子はかわいい。

L-99 P58

久々のプログラミングネタです。
L-99: Ninety-Nine Lisp Problems の P58 です。

P58

Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.
Example:

sym-cbal-trees(5,Ts).

Ts = [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))]

How many such trees are there with 57 nodes?
Investigate about how many solutions there are for a given number of nodes?
What if the number is even?
Write an appropriate predicate.

Q1 ノードが 57 個のとき、シンメトリーな木のパターンはいくつありますか？

これはまともに木と作っていたのでは解けない問題です。

いつものようにエクセル先生に計測結果のデータをはっつけて傾向と対策を探ります。
事象を計測し、データを集め、法則性を導き出します。物理測定的な解法アプローチです。

;; シンメトリになる木の形状数とノード数の関係

;; A ... 木が完全に釣り合い、かつ底辺の部分のノードが全てそろっているときの底辺のノード数
;; B ... A の補完用の数
;; C ... ノードの総個数
;; D ... シンメトリな木がいくつ出来るかの数

;;  A   B     C          D

;;  1         1          1
;;  2         3          1    
;;      3     5        2C1
;;  4         7          1    
;;      5     9        4C1
;;      6    11        4C2
;;      7    13        4C3
;;  8        15          1    
;;      9    17        8C1
;;     10    19        8C2
;;     11    21        8C3
;;     12    23        8C4
;;     13    25        8C5
;;     14    27        8C6
;;     15    29        8C7
;; 16        31          1    
;;     17    33       16C1
;;     18    35       16C2
;;     19    37       16C3
;;     20    39       16C4
;;     21    41       16C5
;;     22    43       16C6
;;     23    45       16C7
;;     24    47       16C8
;;     25    49       16C9
;;     26    51      16C10
;;     27    53      16C11
;;     28    55      16C12
;;     29    57      16C13  
;;     30    59      16C14
;;     31    61      16C15
;; 32        63          1    
;; ...

こうなります。
このように書き出す事で、法則性があることが簡単にわかります。

ではプログラムを書いていきましょう。
まず組み合わせを計算する手続きを定義します。

(define (fact n x)
  (if (= n 0)
      x
      (fact (- n 1) (* n x))))

(define (perm n r)
  (/ (fact n 1) (fact (- n r) 1)))

(define (comb n r)
  (/ (perm n r) (fact r 1)))

もっと最適化したほうが良い気がしますが、とりあえずこれで良いです。

次に sym-cbal-trees 手続きを定義します。

(define (sym-cbal-trees num)
  (if (even? num)
      0
      (let ((node (log (ceiling (/ num 2)) 2)))
	(if (integer? node)
	    1
	    (let* ((n (expt 2 (x->integer (floor node))))
		   (r (/ (- num (- (* n 2) 1)) 2)))
	      (comb n r))))))

評価してみます。

gosh> (sym-cbal-trees 57)
560

ノードが 57 個ある場合のシンメトリーな木のパターン数は 16C13 = 560 通りあります。

gosh> (time (sym-cbal-trees 9999))
;(time (sym-cbal-trees 9999))
; real   0.031
; user   0.016
; sys    0.016
11436577103049044761221198452518585133677289942544128222443208541369564296810237881125967457185479641859012730749157186026337918310836632184920317429918436832010257712575772912316220048781763180094007260818057119503806472024206237596484037000140955340252760462967607750042611650203259940138602730532492794523053088567877493404920122261243367706161155208567426628443813443651696627343049842580327429128644640369480496760583320982834694512737735411260748844111840176823690848814303441663535288847068276026265786809416498272260267278458991790785446499622063519550479432824371337083954743633428654825784779186826178487299263070808528918377649365725029528130681578375288057135466767026007948970298778625485276413177715104731228883683342449139314942649780402785046948110513608918309676805587816441279133004480534189254221248137175247422703164594490199643957079542420945088581088725822489773787042972410242180451209340578022707144445821125127680

ノードが 9999 個の場合もすぐ求まります。
巨大な数字すぎて読み方がわかりませんが、これだけの組み合わせがあります。

Q2 ノード数が偶数の場合はどうなりますか？

ノード数が偶数の場合は、シンメトリーな木は作れません。ノード数が偶数の場合は、0 通りです。

DiabloIII やっと使えるプライマルが出る

お目当てのプライマルがやっと１つ出ました。

高GRになると雑魚の魔法攻撃さえも相当痛い*1ので、

その対策でレジェンダリージェムの「精霊の守護石」を付けていますが、

物理耐性だけは増えないので、ベルトに特性変更で物理耐性を付けました。

偏りなく耐性は上げないとダメですね。攻撃力はもちろん大事なのですが、

GRレベルが上がるほど攻撃力に頼ったゴリ押しは難しくなります。

さらにカルデサンの絶望を付けましたよ。

プライマル最高ッスｂ

*1:特にサキュバスの撃ってくる弾は痛いｗ ついでにエリートの特殊攻撃(イライラ棒とかｗ)もヤバイｗ

DOA6 もう絶対に一銭たりとも払わない

はずだったのに、

気がついたら買っていますたｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

©コーエーテクモゲームス All rights reserved.

かわいい。

・・・・・。

だからって許したわけじゃないから！

開発陣は、無料版が★１つになっている事を受けて反省してください！

今後 DLC で衣装だしても絶対買わないから。

かすみの衣装だけは買うかも・・・（弱

DOA6 何度目かわからないその後

©コーエーテクモゲームス All rights reserved.

無料版出すの早いなーｗ

炎にガソリンをぶちまけていくスタイルですねｗｗｗ

かすみは無料版ですぐ使えるみたいですし、

なんといっても可愛いのでおすすめしますｗ