An ID is invalid if and only if it is divisible by a number of the form 1001001001, where the 1’s are separated by the same number of 0’s and the block length times the number of blocks equals the digit length of the ID. Given that, the problem reduces to summing the members of some arithmetic progressions; we never have to iterate over the members of a range at all.

(ql:quickload :str)

(defun parse-range (range)
  (mapcar #'parse-integer (str:split "-" range)))

(defun parse-line (line)
  (mapcar #'parse-range (str:split "," line)))

(defun read-inputs (filename)
  (let ((input-lines (uiop:read-file-lines filename)))
    (parse-line (car input-lines))))

(defun split-range (start end)
  "Split the range (start end) into a list of ranges whose bounds have same number of digits."
  (let ((start-digits (1+ (floor (log start 10))))
        (end-digits (1+ (floor (log end 10)))))
    (if (< start-digits end-digits)
        (cons (list start (1- (expt 10 start-digits)))
              (split-range (expt 10 start-digits) end))
        (list (list start end)))))

(defun sum-multiples-in-range (d start end)
  "Add up the sum of all multiples n of d satisfying start <= n <= end."
  (multiple-value-bind (q0 r0) (floor start d)
    ;; q1, q2 are coefficients of the least and greatest multiple of d potentially in range
    (let ((q1 (if (zerop r0) q0 (1+ q0)))
          (q2 (floor end d)))
      (if (> q1 q2)
          0
          (flet ((arith-up-to (n) (floor (* n (1+ n)) 2)))
            (* d (- (arith-up-to q2) (arith-up-to (1- q1)))))))))

(defun sum-invalid-in-range (range repeat-count)
  "Add up the sum of all IDs in range start <= n <= end which are invalid due to having
  exactly repeat-count repeats."
  (loop for homogeneous-range in (apply #'split-range range)
        sum (destructuring-bind (hstart hend) homogeneous-range
              (let ((digits (1+ (floor (log hstart 10)))))
                (if (not (zerop (mod digits repeat-count)))
                    0
                    (let ((divisor
                            (loop for k from 0 to (1- digits) by (floor digits repeat-count)
                                  sum (expt 10 k))))
                      (sum-multiples-in-range divisor hstart hend)))))))

(defun main-1 (filename)
  (reduce #'+ (mapcar #'(lambda (range) (sum-invalid-in-range range 2))
                      (read-inputs filename))))

(defun sum-all-invalids-in-range (range)
  "Add up the sum of _all_ invalid IDs (with any available repeat count) in range."
  ;; Composite repeat counts will be overcounted. Because the maximum digit length of
  ;; inputs is limited, we can cheat and just use an explicit constant for weights.
  (let ((repeat-weights '((2 1) (3 1) (5 1) (6 -1) (7 1) (10 -1))))
    (loop for repeat-weight in repeat-weights
          sum (destructuring-bind (repeat-count weight) repeat-weight
                (* weight (sum-invalid-in-range range repeat-count))))))

(defun main-2 (filename)
  (reduce #'+ (mapcar #'sum-all-invalids-in-range (read-inputs filename))))

C

There are interesting analytical observations to be made about the problem to sidestep most of the actual iteration, but I wasn’t up to working it all out and the runtime was pretty much instant anyway.

Here’s my original solution with ints, using divions with powers of 10 to do the splitting: day02-u64.c

But I’m only doing the C implementations to prototype my assembly solutions, and dealing with 64-bit numbers, especially divisions, on x86-16 is painful, so I rewrote the solution using a fixed-length string “numbers” instead: day02.c

Still working on the assembly version

Assembly update: have part 1 working now! It’s dog slow on DOSBox, but on QEMU it’s good: day02.asm

c

#include "aoc.h"
#include <stdio.h>
#include <string.h>

constexpr usize LINE_BUFSZ = (1 << 9);
constexpr usize PID_BUFSZ = (1 << 4);

static void
solve(strl re) {
  FILE* input = fopen("input", "r");
  c8 line[LINE_BUFSZ] = {};
  fgets(line, sizeof(line), input);
  line[strcspn(line, "\n")] = 0;
  usize total = 0;
  strc tok = strtok(line, ",");
  while (tok) {
    Point rng = {};
    sscanf(tok, "%zu-%zu", &rng.x, &rng.y);
    for (usize i = rng.x; i <= rng.y; i++) {
      c8 pid[PID_BUFSZ] = {};
      snprintf(pid, sizeof(pid), "%zu", i);
      is_regex_match(pid, re) ? total += i : 0;
    }
    tok = strtok(nullptr, ",");
  }
  fclose(input);
  printf("%zu\n", total);
}

i32
main(void) {
  solve("^(.+)\\1$");
  solve("^(.+)\\1+$");
}

Janet

• part1
• part2

Another day where the dumb way would have so much quicker and easier, but I’m not competing for time.

I decided to solve it numerically without regex or using to_string(), which was more taxing for the ol’ grey matter but is perhaps fairly optimal (if I bothered to pre-compute all those pow() calls, anyway).

Part 2 runs in 35ms (on my AMD Ryzen 7 9800X3D), whereas the to_string() version runs in 40ms. So… not really worth it, and it’s less readable.

Rust

use std::fs;

use color_eyre::eyre::{Result, bail};

type InvalidChecker = fn(usize) -> bool;

fn sum_invalids(input: &str, checkfn: InvalidChecker) -> Result<usize> {
    let total = input
        .trim()
        .split(',')
        .map(|idrange| {
            if let Some((start, end)) = idrange.split_once('-') {
                let mut sum = 0;
                for n in start.parse::<usize>()?..=end.parse::<usize>()? {
                    if checkfn(n) {
                        sum += n;
                    }
                }
                Ok(sum)
            } else {
                bail!("Couldn't parse {idrange}")
            }
        })
        .sum::<Result<usize, _>>()?;
    Ok(total)
}

fn is_invalid_p1(n: usize) -> bool {
    let len = n.ilog10() + 1;
    // odd-length numbers can't repeat
    if len % 2 == 1 {
        return false;
    }

    let lhs = n / 10_usize.pow(len / 2);
    let rhs = n - (lhs * 10_usize.pow(len / 2));
    lhs == rhs
}

const SPANS: &[&[u32]] = &[
    &[],              // i = 0
    &[],              // i = 1
    &[1],             // i = 2
    &[1],             // i = 3
    &[1, 2],          // i = 4
    &[1],             // i = 5
    &[1, 2, 3],       // i = 6
    &[1],             // i = 7
    &[1, 2, 4],       // i = 8
    &[1, 3],          // i = 9
    &[1, 2, 5],       // i = 10
    &[1],             // i = 11
    &[1, 2, 3, 4, 6], // i = 12
];

fn is_invalid_p2(n: usize) -> bool {
    let len = n.ilog10() + 1;
    // 1-length numbers can't repeat
    if len == 1 {
        return false;
    }

    SPANS[len as usize].iter().any(|&span| {
        let lhs = n / 10_usize.pow(len - span);
        let mut remainder = n;
        let mut rhs = lhs;
        (2..=(len / span)).all(|i| {
            remainder -= rhs * 10_usize.pow(len - (i - 1) * span);
            rhs = remainder / 10_usize.pow(len - i * span);
            lhs == rhs
        })
    })
}

fn part1(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let res = sum_invalids(&input, is_invalid_p1)?;
    Ok(res)
}

fn part2(filepath: &str) -> Result<usize> {
    let input = fs::read_to_string(filepath)?;
    let res = sum_invalids(&input, is_invalid_p2)?;
    Ok(res)
}

to_string version:

fn is_invalid_p2(n: usize) -> bool {
    let s = n.to_string();
    let len = s.len();
    // 1-length numbers can't repeat
    if len == 1 {
        return false;
    }

    SPANS[len].iter().any(|&span| {
        let span = span as usize;
        let lhs = &s[0..span].as_bytes();
        s.as_bytes().chunks(span).all(|rhs| *lhs == rhs)
    })
}

When you have regex, everything looks like a haystack.

Nearly solved pt2 by accident in pt1. Just showing the invalid checks, rest of the code is uninteresting.

fn check_invalid(p0: usize) -> bool {
        let str = format!("{}", p0);
        let len = str.len();
        if len % 2 == 1 {
            return false;
        }
        let len = len / 2;
        str[0..len] == str[len..]
    }

    fn check_invalid2(p0: usize) -> bool {
        let str = format!("{}", p0);
        let re = Regex::new(r"^([0-9]{1,})\1{1,}$").unwrap();
        if re.is_match(str.as_bytes()).unwrap() {
            return true;
        }
        false
    }

edit: The bot worked as well! With some slight human intervention. Tomorrow might be automatic if we are lucky.

Easy one to get through, no edge-cases biting me this time.

I learned this year again: running in interpreted mode can cause significant slowdowns. Later, I’ll hopefully find the time clean it up, this solution feels ugly. Reading everyone else did it also like this or with regex makes me feel better about it though.

Haskell

module Main (main) where
import qualified Text.ParserCombinators.ReadP as ReadP
import Numeric.Natural (Natural)
import Control.Monad ((<$!>), guard)
import qualified Data.List as List
import Control.Arrow ((>>>))
import qualified Data.Text as Text
import qualified Data.Foldable as Foldable

newtype Range = Range { getRange :: (Natural, Natural) }
  deriving Show

parseRange :: ReadP.ReadP Range
parseRange = do
  n1 <- ReadP.readS_to_P reads
  _ <- ReadP.char '-'
  n2 <- ReadP.readS_to_P reads
  pure . Range $ (n1, n2)

parseLine :: ReadP.ReadP [Range]
parseLine = parseRange `ReadP.sepBy` ReadP.char ','

main :: IO ()
main = do
  ranges <- fst . last . ReadP.readP_to_S parseLine <$!> getContents
  print $ part1 ranges
  print $ part2 ranges

part1 :: [Range] -> Natural
part1 = List.concatMap (uncurry enumFromTo . getRange)
  >>> List.filter isDoublePattern
  >>> Foldable.sum

part2 :: [Range] -> Natural
part2 = List.concatMap (uncurry enumFromTo . getRange)
  >>> List.filter isMultiplePattern
  >>> Foldable.sum

isMultiplePattern :: Natural -> Bool
isMultiplePattern n = let
    textN = Text.show n
    textLength = Text.length textN
  in flip any (divisorsOf textLength) $ \ divisor -> let
      patternLength = textLength `div` divisor
      patternPart = Text.take (fromIntegral patternLength) textN
    in Text.replicate (fromIntegral divisor) patternPart == textN

isDoublePattern :: Natural -> Bool
isDoublePattern n = let
  textN = Text.show n
  evenLength = even (Text.length textN)
  (first, second) = Text.splitAt (Text.length textN `div` 2) textN
  in evenLength && first == second

divisorsOf :: Integral b => b -> [b]
divisorsOf n = do
  x <- [2..n]
  guard ((n `mod` x) == 0)
  pure x

Using the interpreter, this solution made me wait for two minutes until I could submit. x.x After testing it again in compiled mode, it only takes four seconds.

Javascript

More bruteforcing! There are probably better ways to do this but I’m happy enough with this lol.

const input = require('fs').readFileSync('input-day2.txt', 'utf-8');

let idsPart1 = [];
let idsPart2 = [];

input.split(',').forEach(range => {
    const [start, end] = range.split('-').map(v => parseInt(v, 10));
    let cursor = start;

    while (cursor <= end) {
        const cursorString = cursor.toString(10);

        // part 1 check
        let halfLength = Math.floor(cursorString.length / 2);
        let left = cursorString.slice(0, halfLength);
        let right = cursorString.slice(halfLength, cursorString.length);
        if (left === right) {
            idsPart1.push(cursor);
        }

        // part 2 check
        let sequenceLength = 1;
        while (sequenceLength <= halfLength) {
            const sequence = cursorString.slice(0, sequenceLength);
            let builtString = sequence;
            while (builtString.length < cursorString.length) {
                builtString = `${builtString}${sequence}`;
            }
            if (builtString === cursorString) {
                idsPart2.push(cursor);
                break;
            }

            sequenceLength += 1;
        }

        cursor += 1;
    }
})

const answer1 = idsPart1.flat().reduce((acc, cur) => acc += cur, 0);
const answer2 = idsPart2.flat().reduce((acc, cur) => acc += cur, 0);

console.log(`Part 1 Answer: ${answer1}`);
console.log(`Part 2 Answer: ${answer2}`);

Uiua

Considerably easier than Day 1 for me. Uiua does have regex support, but no back references, so this is my poor man’s version.

"11-22,95-115,998-1012,1188511880-1188511890,222220-222224,1698522-1698528,446443-446449,38593856-38593862,565653-565659,824824821-824824827,2121212118-2121212124"
⊜(⊜⋕⊸≠@-)⊸≠@,
R    ← +⊙⇡⟜-⊙+₁°⊟
Dup  ← ¬˜∊0⦷⊸↙⌈÷2⊸⧻°⋕
Dup₂ ← ⨬(/↥≡⌟(¬˜∊0⦷⊸↙)↘1⇡+1⌈÷2⊸⧻|0)<2÷∩⧻⊸⊸◴°⋕
⊃≡(/+▽⊸≡Dup R)≡(/+▽⊸≡Dup₂ R)
∩/+

You can run the code on Uiua Pad, btw.