write-ups-challenges-2024-2025/scheme/SOLUTION.md

Solutions for all 4 challenges

Point estimates are fairly arbitrary and can be changed by the organizers.

Category

All of these challenges can be put in something like a programming category.

Challenge 0

Difficulty

Free (5 points)

How To Solve

(lambda (a) (+ a 1))

Flag

IGCTF{YouPassedTheSanityCheck!}

---

Challenge 1

Difficulty

Easy (30 points)

How To Solve

The algorithm is fairly simple to implement:

(define (f n)
  (if (zero? (- n 1))
    0
    (if (even? n)
      (+ 1 (f (/ n 2)))
      (+ 1 (f (+ 1 (* n 3)))))))

Applying the constraints from the challenge gives:

(begin
  (define (a b)
    (if (zero? (- b 1))
      0
      (if (even? b)
        (+ 1 (a (/ b 2)))
        (+ 1 (a (+ 1 (* b 3)))))))
  a)

Flag

IGCTF{TJMtKPpKsQNRHkUmricn}

---

Challenge 2

Difficulty

Easy to Average (45 points)

How To Solve

We can reuse the code from before, but we'll need to implement multiplication and division ourself. That's not very difficult to do.

(begin
  (define (times x y)
    (if (= 0 y)
      0
      (+ x (times x (- y 1)))))
  (define (div x y)
    (if (= x 0)
      0
      (+ 1 (div (- x y) y))))
  (define (f n)
  (if (zero? (- n 1))
    0
    (if (even? n)
      (+ 1 (f (div n 2)))
      (+ 1 (f (+ 1 (times n 3)))))))
  f)

Renaming all variables and turning it into a lambda gives us:

(begin
  (define (a b c)
    (if (zero? c)
      0
      (+ b (a b (- c 1)))))
  (define (b c d)
    (if (zero? c)
      0
      (+ 1 (b (- c d) d))))
  (define (c d)
    (if (zero? (- d 1))
      0
      (if (even? d)
        (+ 1 (c (b d 2)))
        (+ 1 (c (+ 1 (a d 3)))))))
  c)

Flag

IGCTF{KMCxgtSxUqwVuZbqQZkg}

---

Challenge 3

Difficulty

• Hard (75 points)

How To Solve

We can start working from the solution to Challenge 1. Two problems need to be solved

1. We can't use define to bind variables, and we don't have any let either. We can work around this by using lambdas instead to bind values.
2. Without define or letrec, we can't explicitly do recursion. Writing a fixed-point/Y combinator can help us.

First, let's rewrite the solution from the first challenge using a Y combinator, ignoring the other constraints. This eliminates all explicit recursion, which is what we need define for.

(define (collatz n)
  (define Y
    (lambda (le)
      ((lambda (f) (f f))
       (lambda (f)
         (le (lambda (x) ((f f) x)))))))
  (define (collatz-rec f)
    (lambda (n)
    (if (zero? (- n 1))
      0
      (if (even? n)
        (+ 1 (f (/ n 2)))
        (+ 1 (f (+ 1 (* n 3))))))))
  ((Y collatz-rec) n))

Now all we need to do is apply two transformations:

1. Replace defines by lambdas, just as you can replace let by a lambda application.
2. Rename our variables.

The first transformation gives us the following code:

(define (collatz n)
  ((lambda (Y collatz-rec)
     ((Y collatz-rec) n))
   (lambda (le)
     ((lambda (f) (f f))
      (lambda (f)
        (le (lambda (x) ((f f) x))))))
   (lambda (f)
     (lambda (n)
       (if (zero? (- n 1))
         0
         (if (even? n)
           (+ 1 (f (/ n 2)))
           (+ 1 (f (+ 1 (* n 3))))))))))

Finally, we can rename our variables to the ones required by the challenge and get rid of that top level define. We only have 3 variable names, but if we play it smart that is sufficient. This snipped yields the flag:

(lambda (a)
  ((lambda (b c)
     ((b c) a))
   (lambda (b)
     ((lambda (c) (c c))
      (lambda (c)
        (b (lambda (a) ((c c) a))))))
   (lambda (b)
     (lambda (c)
       (if (zero? (- c 1))
         0
         (if (even? c)
           (+ 1 (b (/ c 2)))
           (+ 1 (b (+ 1 (* c 3))))))))))

Flag

IGCTF{MEzFXubIUSRRLYQuJfdm}