よわよわCLerが「1時間以内に解けなければプログラマ失格となってしまう5つの問題」を解く

## 前書き

しばらくCommon Lispを書いておらず、この調子だと完全に頭から抜けそうなので、
久しぶりにまた書いてみて、思い出してから再び忘れようと思います。
そこで、今回は「1時間以内に解けなければプログラマ失格となってしまう5つの問題」に挑戦してみました。

https://softantenna.com/blog/5-programming-problems/

### ちなみに

コード中にmain関数を定義しているのはRoswellのrosコマンド実行すると自動的にmain関数が呼ばれるからです。

```text:こんな感じで動作確認してた
ros q1.lisp
```

~~Emacs？LEM？なにそれ美味しいの？~~

## Q1

>forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。

```common-lisp:q1.lisp
; 問題文に書かれていないけど、リストが空なら0を返すようにしとくよ。

; こんなforマクロはCommonLispの美しさを損なわすので普通は定義しないように。普通にloop使おう。
(defmacro for ((var init cond update) &body body)
  `(loop
     with ,var = ,init
     while ,cond
     do
     (progn
       ,@body
       ,update)))

; 車輪を再発明していく！
(defmacro while (cond &body body)
  `(loop while ,cond do ,@body))

; forループを使用した合計関数
(defun sum1 (nums)
  (let ((result 0))
    (for (i 0 (< i (length nums)) (incf i))
      (incf result (nth i nums)))
    result))

; whileループを使用した合計関数
(defun sum2 (nums)
  (let ((result 0))
    (while nums
      (incf result (car nums))
      (setf nums (cdr nums)))
    result))

; 再帰を利用した合計関数
(defun sum3 (nums)
  (if nums
      (+ (car nums) (sum3 (cdr nums)))
      0))

(defun main ()
  (format t "~a~%" (sum1 '(1 2 3))) ; 6
  (format t "~a~%" (sum2 '(4 5 6))) ; 15
  (format t "~a~%" (sum3 '(7 8 9))) ; 24
  )
```

## Q2

>交互に要素を取ることで、2つのリストを結合する関数を記述せよ。
例えば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。

```common-lisp:q2.lisp
; 問題文に書かれていないけど、リストのサイズが異なる場合は余った要素がケツに連結されることにしとくよ。
; 余りを考えなくていいならこれが一番シンプルだろうね。
; (defun intertwine-lists (list1 list2)
;   (apply #'append (mapcar #'list list1 list2)))

(defun intertwine-lists1 (list1 list2 &optional (result '()))
  (when list1
    (push (car list1) result))
  (when list2
    (push (car list2) result))
  (when (or (cdr list1) (cdr list2))
    (setf result (intertwine-lists1 (cdr list1) (cdr list2) result)))
  result)

(defun intertwine-lists (list1 list2 &optional (result '()))
  (nreverse (intertwine-lists1 list1 list2 result)))

(defun main ()
  (let ((list1 '(a b c))
        (list2 '(1 2 3)))
    (format t "~a~%" (intertwine-lists list1 list2))) ; (A 1 B 2 C 3)
  (let ((list1 '(a b c))
        (list2 '(1 2 3 4 5)))
    (format t "~a~%" (intertwine-lists list1 list2))) ; (A 1 B 2 C 3 4 5)
  (let ((list1 '(a b c d e))
        (list2 '(1 2 3)))
    (format t "~a~%" (intertwine-lists list1 list2))) ; (A 1 B 2 C 3 D E)
  )
```

## Q3

>最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。
定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。
例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。

```common-lisp:q3.lisp
(defun create-fib-list (max-count &optional (count 1) (result '()))
  (cond ((= count 1) (push 0 result))
        ((= count 2) (push 1 result))
        (t (push (+ (cadr result) (car result)) result)))
  (if (< count max-count)
      (create-fib-list max-count (1+ count) result)
      result))

(defun main ()
  (format t "~a~%" (apply #'+ (create-fib-list 100)))) ; 573147844013817084100

; いちいちフィボナッチ数列をリストに入れてから和を求めているのは自分のくだらないこだわりです。
; 別にひとつの関数で完結させてもいいでしょう。というかそっちが王道でしょう。
```

## Q4

>正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。
例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる

```common-lisp:q4.lisp
; 正直にいうと、この問題を解く前に別の言語で答えを見ているので答えのアルゴリズムは知っているよ。
; まあしゃあないね。

(defun sort-rule (num1 num2)
  (let ((num1+num2 (parse-integer (format nil "~a~a" num1 num2)))
        (num2+num1 (parse-integer (format nil "~a~a" num2 num1))))
    (> num1+num2 num2+num1)))

(defun main ()
  (format t "~{~a~}~%" (sort (list 50 2 1 9) #'sort-rule)) ; 95021
  (format t "~{~a~}~%" (sort (list 5002 5191 519) #'sort-rule)) ; 5195191505002
  )

; CommonLispのformat関数の変態さがよく分かりますね。
```

## Q5

>1,2,…,9の数をこの順序で、"+"、"-"、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。
例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる

```common-lisp:q5.lisp
; -1や-12などのケースは考えないことにします。

; 他の言語だとevalが使えるからかなり楽なんだけど、CommonLispだとむずいな。
; 中置記法が使えるようになるライブラリが存在するのは知ってるけど、使わない方針でいくよ。

(defun create-num-concat-lists (nums &optional (result '()) (result-list '()))
  (when (null nums)
    (return-from create-num-concat-lists (cons (reverse result) result-list)))
  (setf result-list (create-num-concat-lists (cdr nums) (cons (car nums) result) result-list))
  (when result
    (setf result-list
          (create-num-concat-lists (cdr nums)
                                   (cons (parse-integer (format nil "~a~a" (car result) (car nums))) (cdr result))
                                   result-list)))
  result-list)

(defun solve-q5-1 (nums expected-val &optional (result '()) (result-list '()) (firstp t))
  (when (and firstp nums)
    (setf result (format nil "~a" (car nums)))
    (decf expected-val (car nums))
    (setf nums (cdr nums)))
  (when (null nums)
    (return-from solve-q5-1
                 (if (zerop expected-val)
                     (cons result result-list)
                     result-list)))
  (setf result-list
        (solve-q5-1 (cdr nums)
                    (- expected-val (car nums))
                    (format nil "~a + ~a" result (car nums))
                    result-list
                    nil))
  (setf result-list
        (solve-q5-1 (cdr nums)
                    (+ expected-val (car nums))
                    (format nil "~a - ~a" result (car nums))
                    result-list
                    nil))
  result-list)

(defun solve-q5 (nums expected-val)
  (dolist (nums (create-num-concat-lists nums))
    (dolist (result (solve-q5-1 nums expected-val))
      (format t "~a = ~a~%" result expected-val))))

(defun main ()
  (solve-q5 '(1 2 3 4 5 6 7 8 9) 100))

; 結果
; 123 - 45 - 67 + 89 = 100
; 123 + 45 - 67 + 8 - 9 = 100
; 123 + 4 - 5 + 67 - 89 = 100
; 123 - 4 - 5 - 6 - 7 + 8 - 9 = 100
; 12 + 3 - 4 + 5 + 67 + 8 + 9 = 100
; 12 - 3 - 4 + 5 - 6 + 7 + 89 = 100
; 12 + 3 + 4 + 5 - 6 - 7 + 89 = 100
; 1 + 23 - 4 + 56 + 7 + 8 + 9 = 100
; 1 + 23 - 4 + 5 + 6 + 78 - 9 = 100
; 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
; 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
```

## 実装時間

Q1. 55分
Q2. 50分
Q3. 24分
Q4. 18分
Q5. 3時間くらい

合計：約5時間30分

余裕でプログラマ失格でした。

言語仕様の把握、マクロの定義方法の把握、デバッグなどに時間がかかりました。

## 関係ない話

さて、これらの問題を1時間以内に解けなければ、本当にプログラマ失格なのでしょうか？

私はそうは思いません。
なぜなら、プログラマに必要なスキルはコードの効率性、可読性、
テスト、問題解決のアプローチ、コミュニケーション能力など、幅広いからです。

これらの問題が1時間以内に解けなかったとしても、
困難に立ち向かった経験や、アルゴリズムを試行錯誤した姿勢は無駄ではありません。
むしろ、その状況を楽しむ心がプログラマにとって大切だと考えます。

つまり、1時間以内に解けなくても、
問題を解くことに楽しさややりがいを感じているなら、
その人はプログラマ失格ではないはずです。

楽しむ心があれば、自然とスキルが身につくでしょう。

---

とは言え、未熟なプログラマを納期ギリギリの炎上プロジェクトに突っ込むと、
鬱になってしまう可能性があるため、
それにアサインしても大丈夫かどうかの判断には使えるでしょう。