Skip to content

Latest commit

 

History

History
278 lines (269 loc) · 8.18 KB

2020.14.org

File metadata and controls

278 lines (269 loc) · 8.18 KB

Day 14

Executing this code

If you have a lisp installation, emacs, org-mode, and org-babel support for lisp installed you can run this by:

  1. Starting slime (M-x slime)
  2. Typing C-c C-c in the block initialize.
  3. In the repl type (in-package :aoc-2020-14)
  4. Typing C-c C-c in the block answers

Initial stuffs

Packages to load

(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"))

Create package for this day

<<packages>>
(defpackage :aoc-2020-14
  (:use :common-lisp
        :iterate
        :parseq
        :fiveam)
  (:export :problem-a
           :problem-b))
(in-package :aoc-2020-14)

Input

(defun read-input (file)
  (iter (for line in-file file using #'read-line)
        (collect line)))
(defparameter *input*
  (read-input "input/14.txt"))

Part 1

The task is to sum up the actual values stored into memory after applying a mask. The mask either does’t change (X) the bit, or sets it to 1 or 0.

I feel like I’m overthinking this one.

(defun apply-mask (n mask)
  (loop for c across (reverse mask)
     for i from 0
     with result = 0
     do
       (case c
          (#\X (incf result (logand (expt 2 i) n)))
          (#\0 nil)
          (#\1 (incf result (expt 2 i))))
     finally (return result)))
(defun parse-line (line)
  (let ((parts (cl-ppcre:split " " line)))
    (cond ((string= (first parts) "mask")
           (third parts))
          (t (list
              (parse-integer (cl-ppcre:scan-to-strings "\\d+" (first parts)))
              (parse-integer (third parts)))))))
(defun sum-memory (commands)
  (loop for c in commands
     for todo = (parse-line c)
     with mask = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
     with memory = (make-hash-table)
     if (stringp todo)
     do (setf mask todo)
     if (consp todo)
     do (setf (gethash (first todo) memory)
              (apply-mask (second todo) mask))
     finally (return (loop for v being the hash-values of memory
                        sum v))))
(defun problem-a () (format t "Problem 14 A: ~a~%" (sum-memory *input*)))

Part 2

Basically the same problem, except now the mask applies to the memory address. And instead of X meaning unchanged, it now means floating. So for each X we double the number of possible resulting memory addresses. Each address is assigned to now. So a mask like 1X would assign to both 2 and 3, XX would assign to each of 0 to 3. 0 now means that the original value is unchanged.

The first thing I need to do is update the apply-mask function so that it returns a list of addresses. I’ll make this a simple recursive function.

(defun apply-floating-mask (n mask)
(let ((mask (reverse mask)))
  (labels ((recurse (index value)
             (if (= (length mask) index)
                 (list value)
                 (case (char mask index)
                   (#\0
                    (recurse (1+ index)
                             (if (logbitp index n)
                                 (+ value (expt 2 index))
                                 value)))
                   (#\1 (recurse (1+ index)
                                 (+ value (expt 2 index))))
                   (#\X (append
                         (recurse (1+ index) value)
                         (recurse (1+ index) (+ value (expt 2 index)))))))))
    (recurse 0 0))))
(defun sum-floating-memory (commands)
  (loop for c in commands
     for todo = (parse-a c)
     with mask = "0"
     with memory = (make-hash-table)
     if (stringp todo)
     do (setf mask todo)
     if (consp todo)
     do (loop for address in (apply-floating-mask (first todo) mask)
           do (setf (gethash address memory)
                    (second todo)))
     finally (return (loop for v being the hash-values of memory
                        sum v))))
(defun problem-b () (format t "Problem 14 B: ~a~%" (sum-floating-memory *input*)))

Putting it all together



<<read-input>>
<<input>>
<<apply-mask>>
<<sum-memory>>
<<apply-floating-mask>>
<<sum-floating-memory>>


<<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)


Answer


Problem 14 A: 6559449933360
Problem 14 B: 3369767240513



Test Cases


(def-suite aoc.2020.14)
(in-suite aoc.2020.14)
(defparameter *test-input*
  '("mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X"
    "mem[8] = 11"
    "mem[7] = 101"
    "mem[8] = 0"))

(test sum-memory
  (is (= 165 (sum-memory *test-input*))))
(run! 'aoc.2020.14)


Test Results


Running test suite AOC.2020.14
 Running test SUM-MEMORY .
 Did 1 check.
    Pass: 1 (100%)
    Skip: 0 ( 0%)
    Fail: 0 ( 0%)



Thoughts


Ada


Runner


Simple runner.


with AOC2020.Day14;
procedure Day14 is
begin
  AOC2020.Day14.Run;
end Day14;


Specification


Specification for solution.


package AOC2020.Day14 is
   procedure Run;
end AOC2020.Day14;


Packages


with GNAT.Regpat; use GNAT.Regpat;
with Text_IO; use Text_IO;


Types and generics




Implementation


Actual implementation body.


<<ada-packages>>
package body AOC2020.Day14 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 2020 - Day 14");
      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 AOC2020.Day14;


Run the program


In order to run this you have to “tangle” the code first using C-c
  C-v C-t.


cd ada
gnatmake day14
./day14