与えられた並べ替えを実現するあみだくじの生成
Posted feedbacks - Scheme
あんまり綺麗じゃないけど。 gosh> (amida '(3 5 2 4 0 1)) 0 1 2 3 4 5 | |-| | | | |-| |-| |-| | |-| |-| | |-| |-| |-| | |-| |-| | 3 5 2 4 0 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | (define (amida-sort1 state)
(define (loop prev lis acc strs skip)
(cond ((null? lis)
(values (reverse (cons prev acc))
(reverse strs)))
((or skip (< prev (car lis)))
(loop (car lis) (cdr lis) (cons prev acc)
(cons " " strs) #f))
((> prev (car lis))
(loop prev (cdr lis) (cons (car lis) acc)
(cons "-" strs) #t))
(else
(error "must not happen"))))
(loop (car state) (cdr state) '() '() #f))
(define (amida-sort final-state)
(define (loop state strs)
(cond ((apply < state) strs)
(else
(receive (state1 strs1) (amida-sort1 state)
(loop state1 (cons strs1 strs))))))
(loop final-state '()))
(define (make-amidakuji strs-list)
(define (line strs)
(string-append "|" (string-join strs "|") "|"))
(string-join (map line strs-list) "\n"))
(define (amida final-state)
(define (numbers->line nums)
(string-join (map number->string nums) " "))
(let ((start (numbers->line (iota (length final-state))))
(end (numbers->line final-state)))
(print start)
(print (make-amidakuji (amida-sort final-state)))
(print end)))
|
shiro
#4704()
Rating13/13=1.00
お題#4476を見て思いつきました。
0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。
与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します：
一応、制約条件を示しておきます。
一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。
[ reply ]