DOS + BIOS boot (hybrid binary)

Repo | day02.asm | .COM download

Got the x86-16 assembly implementation working at last! Here, 64-bit integer math, especially lots of divisions by power of 10, wasn't going to do so the code instead operates on fixed-width, zero-padded numeric strings. Lots of time lost to debugging control flow/logic mistakes this time. I need to make printf() a priority!

Short input so no space issues, sitting comfortably at 45K, well below the 64K COM limit! Sadly no time yet to add animations or anything cool.

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  

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

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

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

Rust

View on github

I feared that this required some complicated maths to quickly figure out the next "invalid" number, but the total number of IDs to check was only about 2 million, so brute force it is.

use std::ops::RangeInclusive;

fn parse_input(input: &str) -> Vec<RangeInclusive<u64>> {
    input
        .trim()
        .split(',')
        .map(|r| {
            let (a, b) = r.split_once('-').unwrap();
            RangeInclusive::new(a.parse().unwrap(), b.parse().unwrap())
        })
        .collect()
}

fn part1(input: String) {
    let ranges = parse_input(&input);
    let mut sum = 0;
    for e in ranges.into_iter().flatten() {
        let width = e.ilog10() + 1;
        if width % 2 == 0 {
            let top = 10u64.pow(width / 2);
            if e / top == e % top {
                sum += e;
            }
        }
    }
    println!("{sum}");
}

fn part2(input: String) {
    let ranges = parse_input(&input);
    let mut sum = 0;
    'nums: for e in ranges.into_iter().flatten() {
        let width = e.ilog10() + 1;
        for rep in 2..=width {
            if width % rep == 0 {
                let top = 10u64.pow(width / rep);
                let mut a = e;
                let lowest = a % top;
                let mut invalid = true;
                while a > top {
                    a /= top;
                    if a % top != lowest {
                        invalid = false;
                        break;
                    }
                }
                if invalid {
                    sum += e;
                    // Don't check other numbers of repetitions
                    continue 'nums;
                }
            }
        }
    }
    println!("{sum}");
}

util::aoc_main!();

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.

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.

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

Janet

• part1
• part2

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.

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

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

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

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