algorithm - 砍掉棍子 HackerRank 挑战 Lisp 实现

Question

我现在很困惑。请注意，这场斗争已经教会了我很多关于 lisp 的知识。但是，此时我可能需要一点插入或指导。

Cut the sticks challenge

给你 N 根木棍，每根木棍的长度都是正整数。对木棍执行切割操作，使所有木棍都减少最小木棍的长度。

假设我们有6根木棍的长度

5 4 4 2 2 8然后在一次切割操作中，我们从 6 根木棍中的每一根切割长度为 2。对于下一次切割操作，剩下 4 根木棍(非零长度)，其长度为

3 2 2 6重复以上步骤，直到没有木棍为止。

给定 N 根木棍的长度，打印在后续切割操作中切割的木棍数量。

输入格式第一行包含一个整数 N。下一行包含N个整数:a0,a1,...aN-1，中间用空格隔开，其中ai代表第i根木棍的长度。

输出格式对于每个操作，在单独的行中打印切割的木棍数量。

约束条件1≤N≤10001≤ai≤1000

所以我得到了所有的示例测试用例，但有些我没有。例如

输入:

8
8 8 14 10 3 5 14 12

他们期望的输出是

8
7
6
4
3
2

但是我的代码给出了

8
7
6
4
2

这是我现在想出的功能。

(defun cut-print (numbers cut-length)

    (let ((x numbers) (y cut-length) (k 0))
        (loop while (> (length x) 0) do
            (tagbody
                ;; subtracting the min value from all list elements
                (setq x (map 'list (lambda (i) (- i y)) x)) 

                ;; Don't print if the list length hasn't changed
                ;; from last iteration
                ;; else save length changes and print
                (cond ((= k (length x)) (go bottom))
                      ((not (= k (length x)))
                        (setq k (length x))
                        (format t "~d~%" k)))

                ;; move to here if nothing is printed to
                ;; stdout during the current iteration
                bottom
                    (setq x (remove-if (lambda (x) (<= x 0)) x))))))

我忽略了什么？根据测试用例，上面的逻辑似乎会根据预期输出跳过 cut 操作。

Answer 1

y 是如何变化的？在你的程序中它没有改变......

样式:

• 摆脱 TAGBODY 和 GO。
• 用 IF 替换 COND。
• 变量x和y有什么用？
• 使用描述性名称代替 x、y、i、k。

一个简单的递归版本:

(defun cut (sticks)
  (when sticks
    (print (length sticks))
    (let ((smallest (reduce #'min sticks)))
      (cut (remove-if-not #'plusp
                          (mapcar (lambda (stick)
                                    (- stick smallest))
                                  sticks))))))

另一个递归版本可能是这样的:

(defun cut (sticks)
  (labels ((%cut (sticks)
             (when sticks
               (print (length sticks))
               (let ((smallest (first sticks)))
                 (%cut (mapcar (lambda (stick)
                                 (- stick smallest))
                               (member smallest (rest sticks)
                                       :test-not #'=)))))))
    (%cut (sort sticks #'<))))

甚至:

(defun cut (sticks)
  (labels ((%cut (sticks length)
             (when sticks
               (print length)
               (let ((prefix-length (or (position (first sticks) sticks
                                                  :test-not #'=)
                                        1)))
                 (%cut (nthcdr prefix-length sticks)
                       (- length prefix-length))))))
    (setf sticks (sort sticks #'<))
    (%cut sticks (length sticks))))

一个简单的 LOOP 版本:

(defun cut (numbers)
  (loop with smallest
        while numbers do
        (print (length numbers))
        (setf smallest (reduce #'min numbers)
              numbers (loop for n in numbers 
                            for n1 = (- n smallest)
                            when (plusp n1)
                            collect n1))))