Publish days 6-10

4 files changed, 180 insertions, 0 deletions

diff --git a/10/input.txt b/10/input.txt
new file mode 100644
index 0000000..59db45c
--- /dev/null
+++ b/10/input.txt
@@ -0,0 +1 @@
+31,2,85,1,80,109,35,63,98,255,0,13,105,254,128,33
diff --git a/10/lib.scm b/10/lib.scm
new file mode 100644
index 0000000..11ad449
--- /dev/null
+++ b/10/lib.scm
@@ -0,0 +1,123 @@
+(library (lib)
+  (export solve-part1 solve-part2)
+  (import (chezscheme))
+
+  ; Split list at first delimiter into `prefix' and `suffix'
+  ; Return value is a pair like `((p r e f i x) s u f f i x)'
+  (define (list-split-left delimiter? xs)
+    (let loop ((prefix '())
+               (suffix xs))
+      (if (null? suffix)
+        (cons prefix suffix)
+        (let ((x (car suffix)))
+          (if (delimiter? x)
+              ; Found first delimiter, so return immediately
+              (cons prefix (cdr suffix))
+              ; `x' isn't a delimiter, so append it to `prefix'
+              (loop (append prefix (list x)) (cdr suffix)))))))
+
+  ; Split list at given delimiter into list of sublists
+  (define (list-split delimiter? xs)
+    (let loop ((pieces '())
+               (rest xs))
+      (if (null? rest)
+          ; Fix order and remove all empty sublists from output
+          ; (which are caused by consecutive delimiters in `xs')
+          (reverse (remp null? pieces))
+          ; Extract next piece from `rest' and prepend it to `pieces'
+          (let ((next (list-split-left delimiter? rest)))
+            (loop (cons (car next) pieces) (cdr next))))))
+
+  ; Split string at commas into list of substrings
+  (define (string-split str)
+    (define (char-comma? c) (char=? c #\,))
+    (map list->string (list-split char-comma? (string->list str))))
+
+  ; Reverse order of numbers in index range `[pos, pos+len)' in state
+  (define (reverse-range state-old pos len)
+    (define state-length (vector-length state-old))
+    ; Initialize `state-new' as a copy of `state-old'
+    (define state-new (apply vector (vector->list state-old)))
+    (let loop ((i 0)) ; `i' is the offset from `pos'
+      (if (>= i len)
+          state-new
+          (begin
+            ; Copy `state-old[pos+i]' to `state-new[pos+len-i-1]'
+            (vector-set!
+              state-new
+              (mod (+ pos i) state-length)
+              (vector-ref
+                state-old
+                (mod (- (+ pos len) i 1) state-length)))
+            (loop (+ i 1))))))
+
+  ; Apply a single round of the (main phase of the) hash function
+  (define (single-round lengths0 state0 pos0 skip0)
+    (let loop ((lengths lengths0)
+               (state   state0)
+               (pos     pos0)
+               (skip    skip0))
+      (if (null? lengths)
+          ; Once we've exhausted `lengths', return the full internal state
+          (values state pos skip)
+          ; Call `reverse-range' for `(car lengths)', and update state
+          (loop
+            (cdr lengths)
+            (reverse-range state pos (car lengths))
+            ; (We just let `pos' grow, ignoring circularity)
+            (+ pos (car lengths) skip)
+            (+ skip 1)))))
+
+  ; Apply `single-round' `n' times, reusing the full internal state each time
+  (define (multi-round n lengths state-old pos-old skip-old)
+    (if (<= n 0)
+        state-old
+        (let-values
+          (((state-new pos-new skip-new)
+            (single-round lengths state-old pos-old skip-old)))
+          (multi-round (- n 1) lengths state-new pos-new skip-new))))
+
+  ; Initialize state and apply `n' rounds of knot-tying algorithm
+  (define (solve-puzzle n lengths)
+    (define state0 (list->vector (iota 256)))
+    (multi-round n lengths state0 0 0))
+
+  ; Convert "sparse hash" to "dense hash" as per part 2's description
+  (define (sparse->dense sparse)
+    ; At first, storing `state' as a vector was more convenient
+    ; because of all the indexing, but now a list seems better.
+    (let loop ((state (vector->list sparse))
+               (dense '()))
+      (if (null? state)
+          (reverse dense)
+          (loop
+            ; Remove the first 16 elements from `sparse'
+            (cddddr (cddddr (cddddr (cddddr state))))
+            (cons
+              ; XOR together the first 16 elements of `sparse'
+              (apply bitwise-xor
+                     (list-tail (reverse state) (- (length state) 16)))
+              dense)))))
+
+  (define (solve-part1 str)
+    (define lengths (map string->number (string-split str)))
+    (define state (solve-puzzle 1 lengths))
+    (* (vector-ref state 0) (vector-ref state 1)))
+
+  (define (solve-part2 str)
+    ; For part 2, `lengths' must be initialized differently
+    (define lengths
+      (append (map char->integer (string->list str))
+              '(17 31 73 47 23)))
+    (define sparse-hash (solve-puzzle 64 lengths))
+    (define dense-hash (sparse->dense sparse-hash))
+    ; Convert `dense-hash' into lower-case hexadecimal representation
+    (let loop ((bytes dense-hash)
+               (final ""))
+      (if (null? bytes)
+          final
+          (loop
+            (cdr bytes)
+            (string-append final (format #f "~(~2,'0x~)" (car bytes)))))))
+
+)
diff --git a/10/main.scm b/10/main.scm
new file mode 100644
index 0000000..554b259
--- /dev/null
+++ b/10/main.scm
@@ -0,0 +1,14 @@
+(import (chezscheme))
+
+; Where the magic happens
+(import (lib))
+
+; Read my personal puzzle input
+(define input
+  (call-with-input-file "input.txt" get-line))
+
+; Part 1 gives 6952 for me
+(printf "Part 1 solution: ~a\n" (solve-part1 input))
+
+; Part 2 gives "28e7c4360520718a5dc811d3942cf1fd" for me
+(printf "Part 2 solution: ~a\n" (solve-part2 input))
diff --git a/10/test.scm b/10/test.scm
new file mode 100644
index 0000000..50a425d
--- /dev/null
+++ b/10/test.scm
@@ -0,0 +1,42 @@
+(import (chezscheme))
+
+; Where the magic happens
+(import (lib))
+
+; My quick-and-dirty unit testing framework (copied for each day)
+(define (run-test name proc input expected)
+  (let ((result (proc input)))
+    (if (equal? result expected)
+      (printf "\x1b;[32;1mPASS\x1b;[0m: ~a\n"
+              name)
+      (printf "\x1b;[31;1mFAIL\x1b;[0m: ~a: got ~a, expected ~a\n"
+              name result expected))))
+
+; I've disabled part 1's test because it uses a 5-element list
+; instead of 256 elements like the main problem and part 2, and
+; I'm too lazy to structure my code properly to deal with that.
+
+;(printf "Part 1 tests:\n")
+
+;(define (test-part1 name input expected)
+;  (run-test name solve-part1 input expected))
+
+;(test-part1 "part 1 example 1"
+;            "3,4,1,5" 12)
+
+(printf "Part 2 tests:\n")
+
+(define (test-part2 name input expected)
+  (run-test name solve-part2 input expected))
+
+(test-part2 "part 2 example 1"
+            "" "a2582a3a0e66e6e86e3812dcb672a272")
+
+(test-part2 "part 2 example 2"
+            "AoC 2017" "33efeb34ea91902bb2f59c9920caa6cd")
+
+(test-part2 "part 2 example 3"
+            "1,2,3" "3efbe78a8d82f29979031a4aa0b16a9d")
+
+(test-part2 "part 2 example 4"
+            "1,2,4" "63960835bcdc130f0b66d7ff4f6a5a8e")