Racket rod cutting problem, how to use vectors in recursive functions-CodePudding

I'm trying to figure out why I'm getting the errors expected vector? and expected pair? and if there's a way to have a vector as a variable and access the vector for the rod cutting problem (similar to the knapsack problem).

#lang slideshow

; test input: (cutrod 5 #(0 1 2 3 2 2 6 1 2 3 10))

(define (square) (colorize(rectangle 20 15) "red"))
(define (rodpiece n) (apply hc-append(vector->list (make-vector n (square)))))

(define (cutrod n s)
    (rodpiece n)
      (cond
        ((null? s) '())
        (else
         (let
             ([cut (car (vector->list s))]
              [rods (cdr (vector->list s))])
            (cons cut (cutrod (- n (vector-ref s n)) rods))
            (cutrod n rods)
            n))))

Here's the C PrintSolution version I'm using to convert:

void PrintSolution(int n, int s[]){
   while(n>0){
      printf(“%d ”, s[n]);
      n = n ‐ s[n];
      }
}

This error happens when I try to convert the vector to a list, it says it expected a vector:

This error happens when I keep the vector as is, it says it expected a pair:

CodePudding user response：

Part of the problem is that (rodpiece) returns a list, rather than a vector. You can solve this easily by changing it to:

(define (rodpiece n)
  (make-vector 1
               (apply hc-append
                      (build-list n
                                  (lambda (x)
                                    (square))))))

There's no need to start with a vector, but the goal is to return one.

The next problem is that you are calling (rodpiece) in a location which basically discards the return value. You want something closer to this:

(define (cutrod n s)
  (let* ((sn (vector-ref s n))
         (rp (rodpiece sn)))

Which determines the size of the rod piece up front, then gets the current rod piece for use shortly afterwards. You then need to check for the base case of the recursion:

    (if (or (<= n 0)
            (> n (vector-length s))) 
        rp

Where if n is zero, or is longer than the remaining vector s, you simply return the current rod piece.

The recursion itself accumulates current rod piece with the remaining rod pieces:

        (vector-append rp (cutrod (- n sn) s)))))

Putting this all together, you have:

#lang slideshow

(define (square)
  (colorize (rectangle 20 20) "red"))

(define (rodpiece n)
  (make-vector 1
               (apply hc-append
                      (build-list n
                                  (lambda (x)
                                    (square))))))

(define (cutrod n s)
  (let* ((sn (vector-ref s n))
         (rp (rodpiece sn)))
    (if (or (<= n 0)
            (> n (vector-length s))) 
        rp
        (vector-append rp (cutrod (- n sn) s)))))

(define cut-vector  #(0 1 2 3 2 2 6 1 2 3 10))

(cutrod 5 cut-vector)
(cutrod 6 cut-vector)
(cutrod 7 cut-vector)
(cutrod 9 cut-vector)
(cutrod 10 cut-vector)