If you have a lisp installation, emacs, org-mode, and org-babel support for lisp installed you can run this by:
- Starting slime (
M-x slime) - Typing
C-c C-cin the block initialize. - In the repl type
(in-package :aoc-2017-10) - Typing
C-c C-cin the block answers
(unless (find-package :cl-ppcre)
(ql:quickload "cl-ppcre"))
(unless (find-package :iterate)
(ql:quickload "iterate"))
(unless (find-package :parseq)
(ql:quickload "parseq"))
(unless (find-package :fiveam)
(ql:quickload "fiveam"))
(unless (find-package :series)
(ql:quickload "series"))
(unless (find-package :cl-permutation)
(ql:quickload "cl-permutation"))
(unless (find-package :bordeaux-threads)
(ql:quickload "bordeaux-threads"))<<packages>>
(defpackage :aoc-2017-10
(:use :common-lisp
:iterate
:parseq
:fiveam)
(:export :problem-a
:problem-b))
(in-package :aoc-2017-10)The input is a series of numbers separated by commas. I’ll use cl-ppcre for this, ignoring the commas and just finding all matching numbers.
(defun read-input (file)
(with-open-file (in file)
(let ((line (read-line in)))
(mapcar #'parse-integer (ppcre:all-matches-as-strings "-?\\d+" line)))))(defparameter *input*
(read-input "input/10.txt"))
(defparameter *raw-input* (with-open-file (in "input/10.txt") (read-line in)))Alright, so what is the problem?
The input is a series of lengths. These are lengths that are to be reversed, starting at the present position (initially 0), and then we skip ahead by the length + however many reversals we’ve already done.
(defun knot-reverse (orig pos len)
(let* ((s (copy-seq orig)))
(setf (cdr (last s)) s)
(loop for i from pos
for j downfrom (+ pos len -1)
while (< i j)
do (psetf (nth i s) (nth j s)
(nth j s) (nth i s)))
(subseq s 0 (length orig))))
(defun knot-round (lengths string &optional (skip 0) (pos 0))
(loop
for l in lengths
with skip = skip
with pos = pos
with string = (copy-seq string)
finally (return (values string skip pos))
do (setf string (knot-reverse string pos l))
(incf pos (+ l skip))
(setf pos (mod pos (length string)))
(incf skip)))
(defun part-1 (lengths)
(let ((hash (knot-round lengths (loop for i from 0 below 256 collect i))))
(print (* (first hash) (second hash)))))(defun problem-a () (format t "Problem 10 A: ~a~%" (part-1 *input*)))Turns out we were not supposed to parse the initial input. So I’ll put the raw version of it in a different global variable. We are supposed to treat the input as a sequence of ASCII characters (easy enough) and use the ASCII codes themselves for the inputs to the hash above.
Also, instead of one round of hashing we do it 64 times, keeping the
position and skip values from the prior rounds. After that’s done the
final result is found by xor‘ing each group of 16 values and
creating a new sequence. I’ll rename the above to knot-round and
make the real knot-hash below.
(defun knot-dense-hash (sparse)
(loop
for i from 0 below 16
collect
(let ((vals (subseq sparse (* i 16) (* (1+ i) 16))))
(reduce (lambda (x y) (boole boole-xor x y)) vals))))
(defun knot-hash (size input)
(let ((sparse-hash (loop repeat 64
with skip = 0
with position = 0
with string = (loop for i from 0 below size collect i)
with key = (append (map 'list #'char-code input) (list 17 31 73 47 23))
finally (return string)
do (multiple-value-bind
(st sk pos) (knot-round key string skip position)
(setf string st
skip sk
position pos)))))
(string-downcase (format nil "~{~2,'0X~}" (knot-dense-hash sparse-hash)))))(defun problem-b () (format t "Problem 10 B: ~a~%" (knot-hash 256 *raw-input*)))<<read-input>>
<<input>>
<<knot-round>>
<<knot-hash>><<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)29240 Problem 10 A: 29240 Problem 10 B: 4db3799145278dc9f73dcdbc680bd53d
(def-suite aoc.2017.10)
(in-suite aoc.2017.10)
(test knot-hash
(is (string= "a2582a3a0e66e6e86e3812dcb672a272" (knot-hash 256 "")))
(is (string= "33efeb34ea91902bb2f59c9920caa6cd" (knot-hash 256 "AoC 2017")))
(is (string= "3efbe78a8d82f29979031a4aa0b16a9d" (knot-hash 256 "1,2,3")))
(is (string= "63960835bcdc130f0b66d7ff4f6a5a8e" (knot-hash 256 "1,2,4"))))
(run! 'aoc.2017.10)Running test suite AOC.2017.10
Running test KNOT-HASH ....
Did 4 checks.
Pass: 4 (100%)
Skip: 0 ( 0%)
Fail: 0 ( 0%)
Simple runner.
with AOC2017.Day10;
procedure Day10 is
begin
AOC2017.Day10.Run;
end Day10;Specification for solution.
package AOC2017.Day10 is
procedure Run;
end AOC2017.Day10;with GNAT.Regpat; use GNAT.Regpat;
with Text_IO; use Text_IO;Actual implementation body.
<<ada-packages>>
package body AOC2017.Day10 is
<<types-and-generics>>
-- Used as an example of matching regular expressions
procedure Parse_Line (Line : Unbounded_String; P : out Password) is
Pattern : constant String := "(\d+)-(\d+) ([a-z]): ([a-z]+)";
Re : constant Pattern_Matcher := Compile(Pattern);
Matches : Match_Array (0..4);
Pass : Unbounded_String;
P0, P1 : Positive;
C : Character;
begin
Match(Re, To_String(Line), Matches);
P0 := Integer'Value(Slice(Line, Matches(1).First, Matches(1).Last));
P1 := Integer'Value(Slice(Line, Matches(2).First, Matches(2).Last));
C := Element(Line, Matches(3).First);
Pass := To_Unbounded_String(Slice(Line, Matches(4).First, Matches(4).Last));
P := (Min_Or_Pos => P0,
Max_Or_Pos => P1,
C => C,
P => Pass);
end Parse_Line;
procedure Run is
begin
Put_Line("Advent of Code 2017 - Day 10");
Put_Line("The result for Part 1 is " & Integer'Image(0));
Put_Line("The result for Part 2 is " & Integer'Image(0));
end Run;
end AOC2017.Day10;In order to run this you have to “tangle” the code first using C-c
C-v C-t.
cd ada
gnatmake day10
./day10