Emacs Lispで「ソフトウェアエンジニアならば1時間以内に解けなければいけない5つの問題」を解いてみた

http://mattn.kaoriya.net/software/vim/20150527121332.htm

ちょうど 1時間程度. 1-4はすぐに書けて, 5に時間を要した.
(追記: 2015年6月1日 問4に誤りがあり修正しました)

問題1

'for'の代わりに loopで.

(require 'cl-lib)

(defun problem1-for (lst)
  (cl-loop for i in lst
           sum i))

(defun problem1-while (lst)
  (let ((sum 0)
        (xs lst))
    (while xs
      (setq sum (+ sum (car xs))
            xs (cdr xs)))
    sum))

(defun problem1-recursive (lst)
  (if (null lst)
      0
    (+ (car lst) (problem1-recursive (cdr lst)))))

(defun problem1-tail-recursive (lst)
  (cl-labels ((func (lst acc)
                (if (null lst)
                    acc
                  (func (cdr lst) (+ acc (car lst))))))
    (func lst 0)))

(let ((input '(1 2 3 4 5 6 7 8 9 10)))
  (cl-assert (= 55
                (problem1-for input)
                (problem1-while input)
                (problem1-recursive input)
                (problem1-tail-recursive input))))

問題2

(require 'cl-lib)

(defun problem2 (xs ys)
  (cl-loop for x in xs
           for y in ys
           collect x
           collect y))

(cl-assert (equal '(a 1 b 2 c 3)
                  (problem2 '(a b c) '(1 2 3))))

他には mapcanを使うとかだろか.

(cl-mapcan (lambda (a b) (list a b)) '(1 2 3) '(a b c))

問題3

表現範囲の問題で, calcを使用. すぐ書けたものでは正しく表示できず.

(require 'cl-lib)
(require 'calc-arith)

(defun bignum-to-string (n)
  (let ((sign (if (eq (car n) 'bigpos) "" "-")))
    (concat sign
            (mapconcat #'number-to-string
                       (reverse (cdr n))
                       ""))))

(defun problem3 (n)
  (cond ((= n 1) '(0))
        ((= n 2) '(0 1))
        (t
         (cl-loop with acc = '(1 0)
                  repeat (- n 2)
                  do
                  (push (calcFunc-add (cl-first acc) (cl-second acc)) acc)
                  finally
                  return (reverse (mapcar (lambda (e)
                                            (if (listp e) (bignum-to-string e) e)) acc))))))

(cl-assert
 (string= (nth 99 (problem3 100)) "218922995834555169026"))

問題4

(1つめのコードは誤っています.)

(require 'cl-lib)

(defun problem4 (lst)
  (let ((xs (sort lst (lambda (a b)
                        (string< (number-to-string b) (number-to-string a))))))
    (string-to-number (mapconcat #'number-to-string xs ""))))

(cl-assert
 (= (problem4 '(50 2 1 9)) 95021))

追記: 2015/JUN/1 修正版

(require 'cl-lib)

(defun compare (a b)
  (let ((ab-val (string-to-number (format "%s%s" a b)))
        (ba-val (string-to-number (format "%s%s" b a))))
    (> ab-val ba-val)))

(defun problem4 (lst)
  (let ((xs (sort lst #'compare)))
    (string-to-number (mapconcat #'number-to-string xs ""))))

(cl-assert
 (= (problem4 '(420 42 423)) 42423420)
 (= (problem4 '(50 2 1 9)) 95021))

問題5

他はすぐに思いついたけど, これは時間がかかった.
evalは使わず. 演算子の全組み合わせを出せばすぐだなと思ったけど,
文字列連結を先にするのがうまくいかず, 苦労した.

(require 'cl-lib)

(defun concat-num (a b)
  (string-to-number (concat (number-to-string a) (number-to-string b))))

(defun permute-ops (n)
  (let ((accs nil))
    (cl-labels ((permute-ops- (n i acc)
                  (if (= n i)
                      (push (reverse acc) accs)
                    (cl-loop for op in '(+ - concat-num)
                             do
                             (permute-ops- n (1+ i) (cons op acc))))))
      (permute-ops- n 0 '())
      accs)))

(defun apply-concat (lst ops)
  (cl-loop with stack = (list (car lst))
           for e in (cdr lst)
           for op in ops
           if (eq op 'concat-num)
           do
           (let ((a (pop stack)))
             (push (concat-num a e) stack))
           else
           do
           (push e stack)
           finally return (reverse stack)))

(defun calc-ops (lst- ops-)
  (let ((lst (apply-concat lst- ops-))
        (ops (cl-loop for op in ops-
                      unless (eq op 'concat-num)
                      collect op)))
    (if (null ops) ;; all ops are concat
        (car lst)
      (cl-loop with acc = (funcall (car ops) (cl-first lst) (cl-second lst))
               for op in (cdr ops)
               for num in (cddr lst)
               do
               (setq acc (funcall op acc num))
               finally return acc))))

(defun format-ops (lst ops)
  (concat (number-to-string (car lst))
          (cl-loop for op in ops
                   for num in (cdr lst)
                   if (eq op 'concat-num)
                   concat (number-to-string num)
                   else
                   concat (format "%s%s" op num))))

(defun problem5 (lst)
  (let ((opss (permute-ops (1- (length lst)))))
    (cl-loop for ops in opss
             when (= (calc-ops lst ops) 100)
             collect (format-ops lst ops))))

(cl-assert
 (member "1+2+34-5+67-8+9" (problem5 '(1 2 3 4 5 6 7 8 9))))