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-2020-09) - 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-2020-09
(:use :common-lisp
:iterate
:parseq
:fiveam)
(:export :problem-a
:problem-b))
(in-package :aoc-2020-09)(defun read-input (file)
(iter (for line in-file file using #'read)
(collect line)))(defparameter *input*
(read-input "input/09.txt"))(defun is-valid (number list)
(loop for l in list
do (when (member (- number l) (remove l list))
(return t))))
(defun first-invalid (list)
(loop for i from 25 below (length list)
if (not (is-valid (elt list i) (subseq list (- i 25) i)))
do (return (elt list i))))(defun problem-a () (format t "Problem 09 A: ~a~%" (first-invalid *input*)))Find a contiguous block that sums to the value in part 1. Can be anywhere in the data, return the sum of the smallest and largest.
(defun find-block (list target)
(loop for i from 2 to (length list)
do (loop for j from 0
while (<= (+ j i) (length list))
for s = (subseq list j (+ j i))
for total = (reduce #'+ s)
if (= target total)
do (return-from find-block
(+ (reduce #'min s)
(reduce #'max s))))))So a dumb thing about the above is that I expand the window on the
outside. I’m also using elt which is slow for accessing elements of
lists, especially deeper into the list structure.
The following is faster, though perhaps not as clean as it could
be. Taking advantage of the list structure. Getting either the car or
cdr of a cons cell is fast. The sum, and min and max, are collected as
the window is expanded so when the target is found (if it is found)
(defun find-block (list target)
(loop for l = list then (cdr l)
do (loop named inner
for w in (cdr l)
for min = (min (car l) w) then (min min w)
for max = (max (car l) w) then (max max w)
for total = (+ (car l) w) then (incf total w)
until (< target total)
if (= target total)
do (return-from find-block (+ min max)))))This one is the fastest. Though it’s not really any different than the above in terms of the algorithm. It’s completely recursive, no loops left.
(defun find-block (list target)
(labels ((recurse (w min max sum)
(cond ((< target sum) nil)
((= sum target) (+ min max))
((null w) nil)
(t (recurse
(cdr w)
(min min (car w))
(max max (car w))
(+ sum (car w)))))))
(or (recurse (cddr list)
(min (car list) (cadr list))
(max (car list) (cadr list))
(+ (car list) (cadr list)))
(find-block-recurse (cdr list) target))))(defun problem-b ()
(format t "Problem 09 B: ~a~%"
(find-block *input* 552655238)))<<read-input>>
<<input>>
<<first-invalid>>
<<find-block>><<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)Problem 09 A: 552655238 Problem 09 B: 70672245
(def-suite aoc.2020.09)
(in-suite aoc.2020.09)
(run! 'aoc.2020.09)Simple runner.
with AOC2020.Day09;
procedure Day09 is
begin
AOC2020.Day09.Run;
end Day09;with Text_IO; use Text_IO;
with Ada.Text_IO;
with Ada.Containers.Vectors;package Long_Long_Integer_Vectors is new Ada.Containers.Vectors
(Element_Type => Long_Long_Integer,
Index_Type => Natural);
use Long_Long_Integer_Vectors;
package Long_Long_Integer_Text_IO is new Ada.Text_IO.Integer_IO(Long_Long_Integer);
use Long_Long_Integer_Text_IO;Input is straightforward, all lines contain integers so I’m using the
built-in Ada.Integer_Text_IO package.
procedure Read_File (Data : out Vector) is
Fin : File_Type;
N : Long_Long_Integer;
begin
Open (Fin, In_File, "../input/09.txt");
while not End_Of_File (Fin) loop
Get(Fin, N);
Data.Append(N);
end loop;
Close (Fin);
end Read_File;This will be a simple iterative solution, like the second lisp one I did above.
function Is_Valid_Code (Data : Vector; I : Natural) return Boolean is
begin
for J in I - 26 .. I - 1 loop
for K in J + 1 .. I - 1 loop
if Data(I) = Data(J) + Data(K)
then return True;
end if;
end loop;
end loop;
return False;
end Is_Valid_Code;
function Invalid_Code (Data : Vector) return Long_Long_Integer is
Result : Long_Long_Integer := 0;
begin
for I in Data.First_Index + 26 .. Data.Last_Index loop
if not Is_Valid_Code(Data, I)
then return Data(I);
end if;
end loop;
return Result;
end Invalid_Code;function Find_Block (Data : Vector; Target : Long_Long_Integer) return Long_Long_Integer is
Min, Max, Sum : Long_Long_Integer := 0;
begin
for I in Data.First_Index .. Data.Last_Index - 2 loop
Min := Data (I);
Max := Data (I);
Sum := Data (I);
for J in I + 1 .. Data.Last_Index loop
Min := Long_Long_Integer'Min(Data (J), Min);
Max := Long_Long_Integer'Max(Data (J), Max);
Sum := Sum + Data (J);
exit when Target < Sum;
if Sum = Target then return Min + Max; end if;
end loop;
end loop;
return Min + Max;
end Find_Block;After seeing some other solutions and doing some algebra, I realized I’d selected a very inefficient approach (above). Finding the range (though not the min/max) can be done in a single pass by keeping a running sum.
function Find_Block (Data : Vector; Target : Long_Long_Integer) return Long_Long_Integer is
Min, Max, Sum : Long_Long_Integer := 0;
I, J : Natural;
begin
I := Data.First_Index;
J := I + 1;
Sum := Data(I) + Data(J);
while Sum /= Target and J <= Data.Last_Index loop
if Target < Sum then
Sum := Sum - Data(I);
I := I + 1;
end if;
if I = J or Sum < Target then
J := J + 1;
Sum := Sum + Data(J);
end if;
end loop;
Min := Data(I);
Max := Data(I);
for K in I+1 .. J loop
Min := Long_Long_Integer'Min(Data (J), Min);
Max := Long_Long_Integer'Max(Data (J), Max);
end loop;
return Min + Max;
end Find_Block;That runs in about 1/3rd the time than the previous version needed.
Specification for solution.
package AOC2020.Day09 is
procedure Run;
end AOC2020.Day09;Actual implementation body.
<<with-use>>
package body AOC2020.Day09 is
<<vectors>>
<<read-file>>
<<part-1>>
<<part-2>>
procedure Run is
Data : Vector;
Invalid : Long_Long_Integer;
begin
Read_File (Data);
Put_Line ("Advent of Code 2020 - Day 09"); New_Line;
Invalid := Invalid_Code(Data);
Put_Line ("The result for Part 1 is: " & Invalid'Image);
Put_Line ("The result for Part 2 is: " & Find_Block(Data, Invalid)'Image);
end Run;
end AOC2020.Day09;In order to run this you have to “tangle” the code first using C-c
C-v C-t.
cd ada
gnatmake day09
./day09Advent of Code 2020 Day 09 - The result for Part 1 is: 552655238 The result for Part 2 is: 70672245