151 lines
3.8 KiB
Markdown
151 lines
3.8 KiB
Markdown
# 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}
|