Advent of Code 2025 Day 2: Gift Shop 🎁

#adventofcode #rust #programming #algorithms

The Problem

We need to find "invalid" product IDs in given ranges. An ID is invalid if it's made of a repeated digit sequence.

Part 1: Find IDs repeated exactly twice (e.g., 1212, 345345)

Part 2: Find IDs repeated at least twice (e.g., 123123, 1111, 12121212)

Part 1: The Easy One

Part 1 was straightforward. For each number in the range:

Convert to string
Check if length is even
Split in half and compare

fn invalid_id_sum1(ranges: Vec<(u128, u128)>) -> u128 {
    let mut id_sum: u128 = 0;
    for (start, end) in ranges.iter() {
        for i in *start..*end+1 {
            let s = i.to_string();
            if s.len() % 2 != 0 {
                continue;
            }
            let (a, b) = s.split_at(s.len() / 2);
            let x: u128 = a.parse().expect("Expected a number");
            let y: u128 = b.parse().expect("Expected a number");
            if x == y {
                id_sum += i;
            }
        }
    }
    id_sum
}

Simple: if both halves match, it's invalid.

Part 2: The Tricky One

Part 2 got me thinking. Numbers can repeat 2, 3, 4+ times. My first approach only checked one specific split, which failed for cases like:

12121212 (should be 1212|1212, not something else)
12211221 (should be 1221|1221)

The fix: Try all possible split counts from 2 up to the maximum.

Here's my approach:

fn invalid_id_sum2(ranges: Vec<(u128, u128)>) -> u128 {
    let mut id_sum: u128 = 0;
    for (start, end) in ranges.iter() {
        for i in *start..*end+1 {
            let s = i.to_string();
            let mut map: [usize; 10] = [0; 10];
            for c in s.chars() {
                if let Some(digit) = c.to_digit(10) {
                    map[digit as usize] += 1;
                }
            }
            let mut splits: usize= 1000;

            for j in 0..10 {
                if map[j] != 0 {
                    splits = min(splits, map[j]);
                }
            }
            for split in 2..splits+1 {
                let len = s.len() / split ;
                let mut parts: Vec<i128> = Vec::new();
                let mut start = 0;

                for _ in 0..split {
                    let end = start + len;
                    parts.push((&s[start..end]).parse().expect("Expected a number"));
                    start = end;
                }
                if start < s.len() {
                    parts.push((&s[start..]).parse().expect("Expected a number"));
                }
                let num = parts[0];
                let mut invalid = true;
                for x in 1..parts.len() {
                    if num != parts[x] {
                        invalid = false;
                    }
                }
                if parts.len() == 1 {
                    invalid = false;
                }
                if invalid {
                    id_sum += i;
                    break
                }
            }
        }
    }
    id_sum
}