2024-10-21: AoC 2015 Day 10 - Extendable Vectors

This puzzle requires us to create an ever-increasing sequence of digits:

"1" -> "11" -> "21" -> "1211" etc.

Each subsequent sequence reflects how you would say the previous one: "21" is "one 2 one 1" -> "1211" - hence, it's called "say and tell". The puzzle input provides the initial sequence, and the two parts of the puzzle require the length of the resulting sequence after 40 and then 50 turns, respectively.

Plan

The basic structure of a solution is straightforward:

1. read in the initial sequence - from stdin is a good option
2. iterate the required number of times to find the final sequence
3. report the overall length

The key function is the one that takes one sequence and returns the new sequence: i.e. does the "say and tell" step. The procedure is not difficult: start at the beginning of the original sequence, look at the number you have and count forward while you have the same number, append the count and number to the growing string when the number changes or the sequence ends.

The steps could look like the following:

1. result sequence is empty
2. set last-number to the first number in the original sequence
3. set total as 1
4. loop through each number in the original sequence
   • if the number is the same as last-number, then increment total
   • if not, then add total and last-number to the result before resetting total to 1 and last-number to the current number
5. when the loop is finished, add final total and last-number to result
6. return result

When I first solved this puzzle in Icon, I did not pay it much thought, using a string for the original and result sequences: extending the string is done easily in Icon: result || total || last-char and produces a result fast.

I initially tried the same in Lisp, but came unstuck: (format nil "~a~a~a" result total last-char) led to a solution taking many minutes. A solution that worked is to make the sequence a vector of numbers, and make the result sequence a fully resizable vector.

Extendable Vectors

A vector is a one-dimensional array. One feature of a vector is that looking up an item by its index position is fast.

There are three kinds of vectors:

• fixed size
• resizable, up to a fixed maximum
• fully resizable

Although we call these "vectors", Lisp's vectors are one-dimensional arrays.

Fixed Size Vectors

A fixed vector can be created using (make-array size). Items can be set/get into the given indexed slots, but new slots cannot be added.

[23]> (defvar *a1* (make-vector 5))
*A1*
[24]> *a1*
#(NIL NIL NIL NIL NIL)
[25]> (setf (elt *a1* 2) 3)
3
[26]> *a1*
#(NIL NIL 3 NIL NIL)

Resizable Vectors

Vectors can be created with a fill-pointer: this points to the next free item. New items can then be added to the end of the vector using vector-push, and items removed using vector-pop. However, vector-push does not work if there is no remaining space:

[33]> (defvar *a2* (make-array 5 :fill-pointer 0))
#()
[34]> *a2*
#()
[35]> (length *a2*)
0
[36]> (vector-push 1 *a2*)
0
[37]> *a2*
#(1)
[38]> (length *a2*)
1
[39]> (dotimes (i 4) (vector-push i *a2*))
NIL
[40]> *a2*
#(1 0 1 2 3)
[41]> (vector-push 5 *a2*)
NIL
[42]> *a2*
#(1 0 1 2 3)
[43]> (vector-pop *a2*)
3
[44]> *a2*
#(1 0 1 2)

Notice in step 34 that the array is empty. In step 41, pushing to a full vector does nothing - returns NIL instead of the index of the filled slot.

A vector's fill-pointer need not start from 0, in which case there will be some filled slots in the vector when created.

[45]> (defvar *a3* (make-array 5 :fill-pointer 3))
*A3*
[46]> *a3*
#(NIL NIL NIL)
[47]> (vector-push 1 *a3*)
3
[48]> *a3*
#(NIL NIL NIL 1)
[49]> (length *a3*)
4

Fully Resizable

The resizable vectors had an upper-limit: to make vectors which can grow as large as memory permits, then they should be made adjustable. Such arrays work just like the ones above, except vector-push-extend must be used to resize the array beyond the initial size:

[53]> (defvar *a4* (make-array 5 :fill-pointer 0 :adjustable t))
*A4*
[54]> (dotimes (i 10) (vector-push i *a4*))
NIL
[55]> *a4*
#(0 1 2 3 4)
[56]> (dotimes (i 10) (vector-push-extend i *a4*))
NIL
[57]> *a4*
#(0 1 2 3 4 0 1 2 3 4 5 6 7 8 9)

Notice how vector-push in step 54 fails after 5 items are added, but vector-push-extend in step 56 has extended the size of the vector.

Final Code

The data structure is important for an efficient solution. Here, the initial-sequence is converted to a vector of numbers, and then each result sequence is created as a fully resizable vector of numbers.

(defun say-and-tell (original-seq)
  (let ((result (make-array (length original-seq)
                            :fill-pointer 0
                            :adjustable t))
        (total 1)
        (last-number (elt original-seq 0)))
    (do ((posn 1 (+ posn 1)))
      ((>= posn (length original-seq))
       (vector-push-extend total result)
       (vector-push-extend last-number result)
       result)
      ;
      (if (= (elt original-seq posn) last-number)
        (incf total)
        (progn
          (vector-push-extend total result)
          (vector-push-extend last-number result)
          (setf last-number (elt original-seq posn)
                total 1))))))

(defun play-say-and-tell (current-sequence n)
  (dotimes (i n current-sequence)
    (setf current-sequence (say-and-tell current-sequence))))

(let ((initial-sequence (map 'vector #'digit-char-p (read-line))))
  (format t "Part 1: ~d~&" (length (play-say-and-tell initial-sequence 40)))
  (format t "Part 2: ~d~&" (length (play-say-and-tell initial-sequence 50))))