scheme - Racket 累加器列表功能

Question

我正在努力创建您可能玩过的2048游戏。它在线上有很多网站。

基本上，此功能的全部作用是：
1）所有空格都移到后面
和2）如果前两个数字相等，则将其加倍并检查每两个数字

这些是我坚持的步骤的说明：


设计左滑函数，以便它使用APS（累加器传递样式）助手在给定行上运行一次传递。您将需要维护两个累加器。第一个累加器会记住最后一个未合并的数字。最初，该值为false，表示我们尚未看到数字。第二个累加器是我们在遇到空白时将它们堆积起来的地方（空白为'-）。最简单的方法是为此目的使用列表，因此其初始值为空。

一次性完成：您可能会认为，起初，使用累加器作为解决方案是一个好主意。但随后订单出现了问题。您可以使用类似（添加解决方案（列表编号））的方法将新元素添加到当前解决方案的末尾，但是追加操作是递归的，并且所花费的时间与解决方案列表的长度成比例。如果可以的话，我们绝对希望避免在APS递归过程中进行非平凡的操作。相反，您可以决定（使用缺点）在当前解决方案的开头添加新数字，以期在末尾反转解决方案。这肯定比追加方法更好。缺点是它需要对数据进行第二次传递才能进行反转。我们希望一口气做到这一点，我们可以。因此，最简单，最快的方法是在退出递归时以正确的顺序构建解决方案。


我在此处添加了一堆检查期望，以便您了解其工作情况：

(check-expect (slide-row-left '(2 2 4 -))(list 4 4 '- '-))
(check-expect (slide-row-left '(2 2 - 4))(list 4 4 '- '-))
(check-expect (slide-row-left '(2 - 2 4))(list 4 4 '- '-))
(check-expect (slide-row-left '(- 2 2 4))(list 4 4 '- '-))

(check-expect (slide-row-left '(2 2 2 2))(list 4 4 '- '-))
(check-expect (slide-row-left '(4 2 2 2))(list 4 4 2 '-))
(check-expect (slide-row-left '(2 4 2 2))(list 2 4 4 '-))
(check-expect (slide-row-left '(2 2 4 2))(list 4 4 2 '-))
(check-expect (slide-row-left '(2 2 4 4))(list 4 8 '- '-))

好了，这就是我所拥有的：

(define (blank? item) (equal? item '-))

(define (slide-row-left b)
  (blank-help (slide-row-left/help b false) '()))

(define (slide-row-left/help ls acc)
  (cond [(empty? ls) acc]
        [(not (equal? (first ls) (first (rest ls)))) 
         (slide-row-left/help (rest (rest ls)) 
           (cons (first (rest ls)) (cons (first ls) acc)))]
        [else (slide-row-left/help (rest (rest ls)) acc)]))

(define (blank-help ls acc)
  (cond [(empty? ls) acc]
        [(blank? (first ls)) (blank-help (rest ls) (cons (first ls) acc))]     
        [else (cons (first ls) (blank-help (rest ls) acc))]))

第一个累加器slide-row-left / help创建一个将不合并的数字的列表。它检查第一个数字和第二个数字是否相等，并将它们添加到列表中。如果它们相等（这意味着它们合并以使原始数量加倍），则仅重复出现。第二个累加器空白帮助将所有空格'-推到列表的末尾，因此所有数字都向左移动。

问题是我不知道如何使用这些元素合并这些片段，尤其是单次通过。

我要去过夜了，所以希望你们在明天之前回复。任何帮助都将如此巨大。这也适用于ISL +

Answer 1

我想我找到了你的问题。坦白说，你还没到那儿。作业明确指出，您必须在递归返回的同时建立结果。这是因为您不想在程序结束时使用reverse，或者在执行尾递归时不执行append。

以下是一些说明每种方法的示例：

;; Using an accumulator
(define (double ls acc)
  (if (empty? ls)
      acc
      (double (rest ls) (cons (* 2 (first ls)) acc))))

(double '(1 2 3) '())
;; = '(6 4 2)
;; So you could reverse the result: (reverse '(1 2 3) '()))
;; but this requires looping over the list again!

;; Using append
(define (double2 ls acc)
  (if (empty? ls)
      acc
      (double2 (rest ls) (append acc (list (* 2 (first ls)))))))

(double2 '(1 2 3) '())
;; = '(2 4 6)
;; But the append operation is very expensive and you don't want that!

(define (double3 ls)
  (if (empty? ls)
      '()
      (cons (* 2 (first ls)) (double3 (rest ls)))))

(double3 '(1 2 3))
;; Cons *after* the recursive call.
;; Requires more memory though, becuase you can not do tail call optimisation!
;; Info: http://c2.com/cgi/wiki?TailRecursion

因此，对于功能slide-row-left/help的不同输入：

情况1：前两个数字相等

输入：'(2 2 4 -)
结果：'(4 4 '- '-)

您要在此处进行的是将两个第一个元素相加（4）。然后，您要计算列表的其余部分。列表的其余部分现在也应该包含一个额外的空格，因为将两个元素加在一起会使列表更短一个元素。因此，您在递归调用中将新的空格传递给acc值。因此，您首先要在此处计算列表的其余部分。因此，使用(drop ls 2)和(cons '- acc)递归调用。这会删除列表中的前2个元素。一旦获得该结果（结果将为'(4 '- '-)，您只需在其前面加上cons您的总和即可。这导致总结果为'(4 4 '- '-)。

情况2：前两个数字不同

输入：'(4 2 2 2)
结果：'(4 4 2 '-)

如果前两个数字不同，我们将无能为力。我们从列表中删除第一个数字（4），这样您就剩下了'(2 2 2)。您不能删除前两个元素，因为第二个和第三个元素可能可以求和。您会记住第一个元素，然后递归调用函数以计算其余结果。该函数返回并为您提供'(4 2 '-)。现在，您需要做的就是在其前面的第一个元素cons生成'(4 4 2 '-)。

情况3：第一个元素为空白

输入：'(- 2 2 4)
结果：'(4 4 '- '-)

如果第一个数字为空白，则不能执行任何操作。您可能会认为在这种情况下情况2适用，但情况并非如此。解决方案的后面应放置空白。但是你该怎么做呢？很简单，您将空白放入累加器中。如您将很快看到的，累加器基本上是列表的末尾。因此，将空白从列表中移走，这将使您剩下'(2 2 4)。将'-放在累加器前面，这会使累加器等于'('- <rest of acc>)并进行递归调用。因此，您可以使用列表'(2 2 4)和累加器'('- <rest of acc>)对其进行调用。您的递归调用将产生'(4 4 '- '-)。因此，您不必再在其前面的任何内容，这只是您的结果。

情况4：第二个元素为空白

输入：cons
结果：'(2 - 2 4)

如果第二个数字为空白，则情况会比较棘手。您将不得不从列表中删去空白。因此，您需要'(4 4 '- '-)。为此，您可以执行(2 2 4)。毛坯可以再次丢弃，不能丢弃。您将需要将其放在列表的末尾。列表的结尾在哪里？确实是累加器。因此，您将(cons (first ls) (rest (rest ls)))所需的元素（空白）留在cons的下方，例如：acc。同样，您将空格放在最后，然后进行递归调用。递归调用的解决方案之前没有必要放置任何元素，这样调用才能为您提供总的答案。

情况5：输入为空

输入：(cons (second ls) acc)
结果：'()

如果输入为空，则需要返回acc值。由于您的输入为空，因此您需要返回列表的末尾，我们知道这是acc值。

情况6：输入为长度1

输入：acc
结果：'(4)

如果输入只是一个元素，则不能对其应用任何总和。您只有一个元素。因此，结果是(cons 4 acc)前面的cons d元素。

资源

#lang racket

;; A shorthand for (first (rest ls))
(define (second ls) (first (rest ls)))

(define (blank? item) (equal? item '-))

(define (slide-row-left b)
  (blank-help (slide-row-left/help b '()) '()))

(define (slide-row-left/help ls acc)
  (cond [(empty? ls) acc]
        [(= (length ls) 1) (cons (first ls) acc)]
        ;; When the first element is blank (e.g., '(- 2 4))
        ;; -> Discard the blank
        ;; -> call the function on the rest of the list.
        [(blank? (first ls))
         (slide-row-left/help (rest ls) (cons (first ls) acc))]
        ;; When the second element is blank (e.g., '(2 - 2 4))
        ;; -> Discard the second element
        ;; -> Run the function again with the entire list (without the blank)
        [(blank? (second ls))
         (slide-row-left/help (cons (first ls) (drop ls 2)) (cons (second ls) acc))]        
        ;; If the first two elements are not equal:
        ;; -> drop 1 element from the list
        ;; -> cons this element to the result of the recursive call
        [(not (equal? (first ls) (second ls)))
         (let  ([fst (first ls)]
                [snd (second ls)]
                [rst (rest ls)]) 
           (cons fst (slide-row-left/help rst acc)))]

        ;; If the first two elements are the same:
        ;; -> drop 2 elements from the list
        ;; -> Sum them
        ;; -> cons the sum in front of the recursive call
        [else
         (let  ([fst (first ls)]
                [snd (second ls)]
                [rst (drop ls 2)]) 
           (cons (* 2 snd) (slide-row-left/help rst (cons '- acc))))]))


(define (blank-help ls acc)
  (cond [(empty? ls) acc]
        [(blank? (first ls)) (blank-help (rest ls) (cons (first ls) acc))]     
        [else (cons (first ls) (blank-help (rest ls) acc))]))

(define (check-expect x y)
  (display x)
  (display y)
  (equal? x y))

(check-expect (slide-row-left '(2 2 4 -))(list 4 4 '- '-))
(check-expect (slide-row-left '(2 2 - 4))(list 4 4 '- '-))
(check-expect (slide-row-left '(2 - 2 4))(list 4 4 '- '-))
(check-expect (slide-row-left '(- 2 2 4))(list 4 4 '- '-))

(check-expect (slide-row-left '(2 2 2 2))(list 4 4 '- '-))
(check-expect (slide-row-left '(4 2 2 2))(list 4 4 2 '-))
(check-expect (slide-row-left '(2 4 2 2))(list 2 4 4 '-))
(check-expect (slide-row-left '(2 2 4 2))(list 4 4 2 '-))
(check-expect (slide-row-left '(2 2 4 4))(list 4 8 '- '-))

编辑

acc函数用于删除列表的drop首个元素。可以如下所示实现。但是，您也可以改用n。为简洁起见，我用它。

下降

(define (drop ls n)
  (cond [(empty? ls)
         ls]
        [(>= 0 n)
         ls]
        [else
         (drop (rest ls) (- n 1))]))