Converting from C to Racket Scheme

Question

I have written the following C code to recursively solve for a given problem, which is to take in a non-empty list of integers and a target value, and return the closest positive value without going over the target. e.g. (3 4) with target 2 should return 1. The only combination is -3 + 4 = 1.:

int closest(int arr[], int target, int i, int n)
{
    
    if (i == n)
        return 0; 

    int sum1 = arr[i] + closest(arr, target - arr[i], i + 1, n); 
                                                                
    int sum2 = -1 * arr[i] + closest(arr, target + arr[i], i + 1, n); 

    if (abs(sum1 - target) < abs(sum2 - target))
    {
        return sum1; 
    }
    else
    {
        return sum2;
    }
}

Unfortunately, the problem is meant to be written in Racket, with the restriction of using car + cdr and not using let to create a variable for sum1/sum2 and I'm having major difficulties.

So far:

(define closest (lambda (l target i n)
  (cond
    ((= i n)0) 
   )
  )
  )

My question is: how does one convert the arr[i] and pointer to car/cdr logic? I vaguely understand that it controls two values but iterating seems to be breaking my brain in two.

Answer 1

You really should learn how to "think in Scheme", but "thinking in Scheme, in C" can also be valuable.

First, use pointer arithmetic instead of array indexing.
If you squint hard enough, you will see that *p is a bit like (car p) - "the first element" - and p + 1 a bit like (cdr p) - "the rest of the elements".
Then you count down to zero instead of up to n (that is, you ask "how many elements are there left to do?" instead of "how many elements have we done?").

int closest(int *arr, int target, int n)
{
    if (n == 0)
        return 0; 
    /* I rearranged these two slightly in order to emphasize the symmetry. */
    int sum1 = closest(arr + 1, target - *arr, n-1) + *arr; 
    int sum2 = closest(arr + 1, target + *arr, n-1) - *arr; 
    if (abs(sum1 - target) < abs(sum2 - target))
    {
        return sum1; 
    }
    else
    {
        return sum2;
    }
}

Now we need to get rid of the "let-bindings", sum1 and sum2.
We can do that by introducing a function:

int pick(int target, int sum1, int sum2)
{
    return abs(sum1 - target) < abs(sum2 - target) ? sum1 : sum2;
}

int closest(int *arr, int target, int n)
{
    if (n == 0)
        return 0; 
    return pick(target,
                closest(arr + 1, target - *arr, n-1) + *arr,
                closest(arr + 1, target + *arr, n-1) - *arr);
}

(As the Fundamental Theorem says, any problem can be solved by adding a level of indirection.)

This can be formulated in Scheme in a pretty straightforward way - it's mostly a matter of changing the punctuation.
Note that we don't need the counter any more since we can tell from the list itself that we have reached the end:

(define (pick target sum1 sum2)
    (if (< (abs (- sum1 target)) (abs (- sum2 target)))
        sum1
        sum2))

(define (closest arr target)
    (if (null? arr)
        0
        (pick target
              (+ (closest (cdr arr) (- target (car arr))) (car arr))
              (- (closest (cdr arr) (+ target (car arr))) (car arr)))))

And now we can "inline" pick, removing the target parameter since it's available in the surrounding context:

(define (closest arr target)
    (if (null? arr)
        0
        ((lambda (sum1 sum2)
             (if (< (abs (- sum1 target)) (abs (- sum2 target))) sum1 sum2))
         (+ (closest (cdr arr) (- target (car arr))) (car arr))
         (- (closest (cdr arr) (+ target (car arr))) (car arr)))))