(Browser-based) Javascript

This year I’m tired of dealing with reading from files and setting up IDEs, so I’m attempting to solve each day directly in my web browser’s console: after opening my problem input in a new tab I can do mySolutionFunction(document.body.textContent) in that tab’s console. Thankfully the browser I use (ff) has a mode that lets me write several lines and then run them, otherwise this would not be simpler. Unfortunately, this means I lost my code for day1 when I closed the tab a bit too quickly.

I didn’t want to use regex for today; you need backreferences and those are impossible to optimize if they blow up (computationally speaking). I’m not so sure my solution for part 2 actually does run in more linear time than a regex with a single backreference does…

function part1(input) {
  let sumOfValidIds = 0;
  for (const rangeDef of input.split(',')) {
    const [start, stop] = rangeDef.split('-').map(s => Number.parseInt(s, 10));
    const rangeLength = stop - start + 1;
    for (let id = start; id <= stop; id++) {
      const idLength = id.toString().length;
      if (idLength % 2 === 1) {
        continue
      }
      const halfLength = idLength / 2;
      const topHalf = Math.floor(id / Math.pow(10, halfLength));
      const bottomHalf = id - topHalf * Math.pow(10, halfLength);
      if (topHalf === bottomHalf) {
        sumOfValidIds += id;
      }
    }
  }
  return sumOfValidIds;
}
part1(document.body.textContent);

function extendsPattern(containerString, pattern) {
  let container = containerString;
  while (container.length > pattern.length) {
    if (!container.startsWith(pattern)) {
      return false;
    }
    container = container.slice(pattern.length)
  }
  return pattern.startsWith(container);
}
function findContainedPatterns(containerString) {
  const patterns = [];
  for (let i = 0; i < containerString.length; i++) {
    const upTillNow = containerString.substring(0, i+1);
    for (let j = 0; j < patterns.length; j++) {
      if (!extendsPattern(upTillNow, patterns[j])) {
        patterns.splice(j, 1);
        j--;
      }
    }
    patterns.push(upTillNow);
  }
  return patterns;
}
function part2(input) {
  let sumOfValidIds = 0;
  for (const rangeDef of input.split(',')) {
    const [start, stop] = rangeDef.split('-').map(s => Number.parseInt(s, 10));
    const rangeLength = stop - start + 1;
    for (let id = start; id <
      const idString = id.toString();
      const patterns = findContainedPatterns(idString);
      if (patterns.length > 1) {
        const shortestPatternCandidate = patterns[0];
        if (idString.length % shortestPatternCandidate.length === 0) {
          sumOfValidIds += id;
        }
      }
    }
  }
  return sumOfValidIds;
}
//part2(`11-22,95-115,998-1012,1188511880-1188511890,222220-222224,1698522-1698528,446443-446449,38593856-38593862,565653-565659,824824821-824824827,2121212118-2121212124`)
part2(document.body.textContent);

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

#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+$");
}

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

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.

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.

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)
    })
}

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}`);

Nim

Easy one today. Part 2 is pretty forgiving on performance, so regex bruteforce was only a couple seconds . But eventually I’ve cleaned it up and did a solution that runs in ~340 ms.

type
  AOCSolution[T,U] = tuple[part1: T, part2: U]

proc isRepeating(str:string, sectorLength=1): bool =
  if str.len mod sectorLength != 0: return false
  for i in countUp(0, str.len - sectorLength, sectorLength):
    if str.toOpenArray(i, i+sectorLength-1) != str.toOpenArray(0, sectorLength-1):
      return false
  true

proc solve(input: string): AOCSolution[int, int] =
  let ranges = input.split(',').mapIt:
    let parts = it.split('-')
    (parseInt parts[0], parseInt parts[1])

  for (a, b) in ranges:
    for num in a .. b:
      if num < 10: continue
      let strnum = $num
      let half = strnum.len div 2

      for i in countDown(half, 1):
        if strnum.isRepeating(i):
          if i == half and strnum.len mod 2 == 0:
            result.part1 += num
          result.part2 += num
          break

Full solution at Codeberg: solution.nim

C# - no regex, 235ms for part 2. down to 51ms when I put each range on its own thread

public class Day2
{
    public void Go()
    {
        //var input = File.ReadAllText("Day2/ExampleData.txt");
        var input = File.ReadAllText("Day2/RealData.txt");
        var inputs = input.Split(',', StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries);
        var pairs = inputs.Select(s =>
            s.Split('-', StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries))
            .Select(s => new Tuple<Int64,Int64>(Int64.Parse(s[0]), Int64.Parse(s[1])));

        Int64 sum = 0;
        foreach (var pair in pairs)
        {
            sum += CheckPair2(pair);
        }

        Console.WriteLine($"Total invalid sum: {sum}");
    }

    public Int64 CheckPair(Tuple<Int64, Int64> pair)
    {
        Int64 sum = 0;
        
        for (Int64 i = pair.Item1; i <= pair.Item2; i++)
        {
            var s =  i.ToString();
            if (s.Length%2 == 1)
            {
                continue;
            }
            
            var p1 = s.Substring(0, s.Length/2);
            var p2 = s.Substring(s.Length/2);

            if (p1 == p2)
            {
                Console.WriteLine($"INVALID PAIR: {s} is made up of {p1} and {p2}");
                sum += i;
            }
        }

        return sum;
    }
    
    public Int64 CheckPair2(Tuple<Int64, Int64> pair)
    {
        Int64 sum = 0;
        
        for (Int64 id = pair.Item1; id <= pair.Item2; id++)
        {
            var s =  id.ToString();
            
            for (int searchLength = 1; searchLength <= s.Length/2; searchLength++)
            {
                if (s.Length%searchLength != 0)
                {
                    continue;
                }

                var valid = true;
                var firstSet = s.Substring(0, searchLength);
                
                for (int repeatPosition = 1; repeatPosition < s.Length/searchLength; repeatPosition++)
                {
                    var checkSet = s.Substring(searchLength*repeatPosition, searchLength);

                    if (firstSet != checkSet)
                    {
                        valid = false;
                        break;
                    }
                }
                
                if (valid)
                {
                    Console.WriteLine($"INVALID ID: {s} is made up of {firstSet} {s.Length/searchLength} times");
                    sum += id;
                    break;
                }
                
            }
        }

        return sum;
    }
}

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.

Janet

• part1
• part2

Kotlin

got up early for this one, sadly it took me over 30 minutes to realize, that my code at the time was also considering a single digit valid .-.

also still pretty scuffed, but hey it works:

class Day02 : Puzzle {

    val ids = mutableSetOf<String>()

    override fun readFile() {
        val input = readInputFromFile("src/main/resources/a2025/day02.txt")
        ids.addAll(
            input.replace("\n", "")
                .split(",")
                .map { it.split("-") }
                .map(this::buildList)
                .flatten()
        )
    }

    private fun buildList(rangeList: List<String>): List<String> {
        val start = rangeList[0].toLong()
        val end = rangeList[1].toLong()
        val ids = mutableListOf<String>()
        for (i in start..end) {
            ids.add(i.toString())
        }
        return ids
    }

    override fun solvePartOne(): String {
        return ids.filter(this::idNotValid)
            .sumOf(String::toLong).toString()
    }

    override fun solvePartTwo(): String {
        return ids.filter { idNotValid(it, true) }
            .sumOf(String::toLong).toString()
    }

    private fun idNotValid(id: String, multipleSplits: Boolean = false): Boolean {
        val length = id.length

        // try all splits
        var split = 2
        while (split <= length) {
            if (length % split == 0) {
                val splits = mutableListOf<String>()
                var beg = 0
                var end = length / split
                val step = end
                for (i in 0..<split) {
                    splits.add(id.substring(beg, end))
                    beg += step
                    end += step
                }
                if (splits.all { it == splits[0] }) return true
            }
            if (multipleSplits) {
                split++
            } else {
                break
            }
        }
        return false
    }
}

full code on Codeberg

First I tried to to part 2 with a very poor regex strategy and the performance was abysmal. Switched to plain substrings and boom, instant result.

Golang

func part1() {
	ranges := readInput()
	invalidSum := 0

	for _, r := range ranges {
		parts := strings.Split(r, "-")
		start, _ := strconv.Atoi(parts[0])
		end, _ := strconv.Atoi(parts[1])

		for num := start; num <= end; num++ {
			current := strconv.Itoa(num)
			n := len(current)
			if n%2 != 0 {
				continue
			}
			left := current[:n/2]
			right := current[n/2:]
			if left == right {
				invalidSum += num
			}
		}
	}

	fmt.Println(invalidSum)
}

func part2() {
	ranges := readInput()
	invalidSum := 0

	for _, r := range ranges {
		parts := strings.Split(r, "-")
		start, _ := strconv.Atoi(parts[0])
		end, _ := strconv.Atoi(parts[1])

		for num := start; num <= end; num++ {
			current := strconv.Itoa(num)
			n := len(current)

			for index := 1; index <= n/2; index++ {
				if n%index != 0 {
					continue
				}

				left := 0
				right := index
				prefix := current[left:right]
				isRepeated := true
				for left < n && right < n {
					left = right
					right = right + index
					next := current[left:right]
					if next != prefix {
						isRepeated = false
						break
					}
				}

				if isRepeated {
					invalidSum += num
					break
				}
			}
		}
	}

	fmt.Println(invalidSum)
}

Haskell

Not much time for challenges right now sadly :/

import Data.Bifunctor  
import Data.IntSet qualified as IntSet  
import Data.List.Split  

repeats bound (from, to) = IntSet.elems $ IntSet.unions $ map go [2 .. bound l2]  
  where  
    l1 = length (show from)  
    l2 = length (show to)  
    go n =  
      let l = max 1 $ l1 `quot` n  
          start = if n > l1 then 10 ^ (l - 1) else read . take l $ show from  
       in IntSet.fromList  
            . takeWhile (<= to)  
            . dropWhile (< from)  
            . map (read . concat . replicate n . show)  
            $ enumFrom start  

main = do  
  input <-  
    map (bimap read (read . tail) . break (== '-')) . splitOn ","  
      <$> readFile "input02"  
  let go bound = sum $ concatMap (repeats bound) input  
  print $ go (const 2)  
  print $ go id