DouKaku? 4344 jijixi: リストのネスト具合の辻褄合わせが大変だっ...(自然数の分割)

Comment detail

リストのネスト具合の辻褄合わせが大変だった。静的型言語ならコンパイルするだけでチェックできるのに……

(use util.match)

(define-constant USAGE
  (string-join '("usage: command n m"
                 "       n, m -> positive integer (n >= m > 0)") "\n"))

(define (split-num_ base n m acc)
  (cond ((= m 0) `((,n)))
        ((< n 0) acc)
        (else
          (let* ((base_ (- base n))
                 (sub   (split-num_ base_ base_ (- m 1) '()))
                 (acc_  (map (pa$ cons n) sub)))
            (split-num_ base (- n 1) m (append acc_ acc))))))

(define (split-num n m)
  (cond ((not (and (>= n m) (> m 0))) (print USAGE))
        (else
          (let* ((nums (split-num_ n n (- m 1) '()))
                 (lines (map (lambda (lst)
                               (string-join (map number->string lst) ", " 'suffix))
                             nums))
                 (sorted (sort lines (lambda (a b) (compare b a)))))
            (string-join sorted "\n")))))

(define (main argv)
  (match argv
         ((_ n m)
          (print (split-num (string->number n) (string->number m))))
         (_ (print USAGE))))

#4344 の移植。エラー処理はあまり意味が無いので省いた。あと、sort とかいらなかったので、これも削除。 (当初は、完全に末尾再帰にしようと思っていて、その時点では順番が崩れるだろうという予想だったんですが……)

rev_map や rev_append でリストの方向がころころ変わってる辺りが OCaml らしいと言えばらしいところ。

let rec split_num' base n m acc =
   match n, m with
   | _, 0 -> [[n]]
   | n, _ when n < 0 -> acc
   | n, m ->
        let base' = base - n in
        let sub   = split_num' base' base' (pred m) [] in
        let acc'  = List.rev_map (fun xs -> n::xs) sub in
        split_num' base (pred n) m (List.rev_append acc' acc)

let split_num n m =
   let nums  = split_num' n n (pred m) [] in
   let lines =
      List.rev_map begin fun lst ->
         String.concat ", " (List.map string_of_int lst)
      end nums
   in
   String.concat "\n" lines

let main () =
   match Sys.argv with
   | [|_; n; m|] ->
        print_endline (split_num (int_of_string n) (int_of_string m))
   | _ ->
        print_endline "usage: command m n"

let () = if not !Sys.interactive then main ()

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq