write-ups-challenges-2022-2023/scheme-challenge/SOLUTION.md

# Solutions for all 4 challenges
Point estimates are fairly arbitrary and can be changed by the organizers.

## Challenge 0
### Difficulty
- Free (5 points)

### How To Solve
`(lambda (a) (+ a 1))`

### Flag
IGCTF{YouPassedTheSanityCheck!}

-------------------------------------
## Challenge 1
### Difficulty
- Easy (35 points)

### How To Solve
The readable version:
```scheme
(lambda (str)
  (define str-l (string-length str))
  (define prefix-length 2)
  (define (loop idx pref-idx)
    (cond
      ((= pref-idx prefix-length) ;Entire prefix was found
       (- idx prefix-length)) ;Return the start of the prefix
      ((= idx str-l) ;End of the string, prefix not found
       -1)
      ((char=? (string-ref str idx) ;Did we find part of the prefix?
               (string-ref prefix pref-idx))
       (loop (+ idx 1) (+ pref-idx 1))) ;Advance prefix-idx, keep going
      (else
        (loop (+ idx 1) 0)))) ;No match, reset prefex-idx and continue
  (loop 0 0))
```
Applying the constraints from the challenge gives:
```scheme
(lambda (a)
  (define b (string-length a))
  (define c 2)
  (define (f d e)
    (if (= e c)
       (- d c)
      (if (= d b)
       -1
      (if (char=? (string-ref a d)
               (string-ref "re" e))
       (f (+ d 1) (+ e 1))
       (f (+ d 1) 0)))))
  (f 0 0))
```

### Flag
IGCTF{WeHaveRegexesForThis}

-----------------------------------------------
## Challenge 2
### Difficulty
- Average (60 points)

### How To Solve
Readable version:
```scheme
(define (get-prefix-idx str)
  (define l (string->list str))
  (define l-padded (append l (list #\a))) ;Padding in case of empty string as input
  (define r-eq  ;For every char in the string, is it equal to 'r'
    (map (lambda (c)
           (char=? #\r c))
         l-padded))
  (define e-eq  ;For every char in the string is it equal to 'e'
    (map (lambda (c)
           (char=? #\e c))
         (append (cdr l-padded) (list #\a)))) ;We shift this one to the right (and add more padding)
  (cdr (foldl ; Iterate through both lists at once
    (lambda (r e acc) ; Accumulate current idx and potential result
      (if (and r e (= (cdr acc) -1))
        (cons (car acc) (car acc))
        (cons (+ 1 (car acc)) (cdr acc))))
    (cons 0 -1)
    r-eq e-eq)))
```

Renaming all variables and turning it into a lambda gives us:
```scheme
(lambda (a)
  (define b (string->list a))
  (define c (append b (list #\a)))
  (define d 
    (map (lambda (j)
           (char=? #\r j))
         c))
  (define e 
    (map (lambda (j)
           (char=? #\e j))
         (append (cdr c) (list #\a))))
  (cdr (foldl
    (lambda (f h g)
      (if (and f h (= (cdr g) -1))
        (cons (car g) (car g))
        (cons (+ 1 (car g)) (cdr g))))
    (cons 0 -1)
    d e)))
```

### Flag
IGCTF{WhyWriteALoopWhenYouCanJustWriteAContrivedFold}

-------
## Challenge 3
### Difficulty
- Hard (80 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. The Y-combinator or
fixpoint operator come to our rescue here.

Combine (1) and (2) and you get:

```scheme
(lambda (a)
  ((lambda (b)
     ((lambda (i)
        (i 0 0))
      ((lambda (e d)
         (e d))
       (lambda (c)
         ((lambda (b) (b b))
          (lambda (b) (c (lambda (i j) ((b b) i j))))))
       (lambda (f)
         (lambda (d e)
           (if (= e 2)
             (- d 2)
             (if (= d b)
               -1
               (if (char=? (string-ref a d)
                           (string-ref "re" e))
                 (f (+ d 1) (+ e 1))
                 (f (+ d 1) 0)))))))))
   (string-length a)))
```

### Flag
IGCTF{YouBetterHaveMadeAFixpointOperatorForThis}