7 votes

Day 2: Gift Shop

Automatically posted
Tags: advent of code.2025

Today's problem description: https://adventofcode.com/2025/day/2

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

10 comments

  1. lily
    Link
    To be honest, I didn't really know what I was doing with this one. Still don't have a clue how to do it in a "smart" way. I just bruteforced it, and it takes a couple seconds to run, which I'm not...

    To be honest, I didn't really know what I was doing with this one. Still don't have a clue how to do it in a "smart" way. I just bruteforced it, and it takes a couple seconds to run, which I'm not super happy with, but I'll take the win for tonight. Maybe I'll come back to it in the morning and see if I can figure out a nicer solution. I'm doing a lot of string copying right now, which I think is the main source of overhead.

    Solution (Lily) 
    var invalid_sum_half_width = 0
var invalid_sum_any_width = 0

for range in File.read_to_string("inputs/day_02.txt").split(",").map(|string|
    string.split("-").map(String.parse_i).map(Option.unwrap)
): {
    for id in range[0]...range[1]: {
        var string = id.to_s()
        var size = string.size()
        var half_width = size / 2

        if string.slice(0, half_width) == string.slice(half_width): {
            invalid_sum_half_width += id
            invalid_sum_any_width += id
            continue
        }

        for width in 1...size: {
            if size % width: {
                continue
            }

            var left = 0
            var right = width
            var previous = string.slice(left, right)
            var invalid = true

            do: {
                left += width
                right += width

                var current = string.slice(left, right)

                if current != previous: {
                    invalid = false
                    break
                }

                previous = current
            } while right < size

            if invalid: {
                invalid_sum_any_width += id
                break
            }
        }
    }
}

print("Part 1: {}\nPart 2: {}".format(
    invalid_sum_half_width, invalid_sum_any_width
))
    3 votes
  2. scarecrw
    Link
    Brute-forced it again, but learned a lot in doing so! Had one of my first "aha!" moments in using string_concat/3 backwards to both check if one string was a prefix of another and find the suffix...

    Brute-forced it again, but learned a lot in doing so!

    Had one of my first "aha!" moments in using string_concat/3 backwards to both check if one string was a prefix of another and find the suffix that matched. No idea if it's the most efficient approach, but super neat!

    Prolog Solution 
    parse_range(RangeString, Range):-
    split_string(RangeString, "-", "", RangeStrings),
    maplist(number_string, Range, RangeStrings).

find_invalids(IsInvalid, [RangeStart, RangeEnd], Invalids):-
    numlist(RangeStart, RangeEnd, Nums),
    include(IsInvalid, Nums, Invalids).

is_invalid_1(Num):-
    number_string(Num, NumString),
    string_length(NumString, L),
    PartLength is div(L, 2),
    sub_string(NumString, 0, PartLength, PartLength, Left),
    sub_string(NumString, PartLength, PartLength, 0, Right),
    Left == Right.

is_invalid_2(Num):-
    number_string(Num, NumString),
    string_length(NumString, L),
    between(2, L, NumParts),
    0 is mod(L, NumParts),
    Before is div(L, NumParts),
    sub_string(NumString, 0, Before, _, Part),
    string_repeat(Part, NumString).

string_repeat(_, "").
string_repeat(Part, String):-
    string_concat(Part, Rest, String),
    string_repeat(Part, Rest).

main:-
    Filename = 'inputs/day02.txt',
    read_file_to_string(Filename, Input, []),
    split_string(Input, ",", "", RangeStrings),
    maplist(parse_range, RangeStrings, Ranges),

    maplist(find_invalids(is_invalid_1), Ranges, Invalids),
    maplist(sum_list, Invalids, InvalidSums),
    sum_list(InvalidSums, Result1),
    write("Part 1: "), write(Result1), nl,

    maplist(find_invalids(is_invalid_2), Ranges, Invalids2),
    maplist(sum_list, Invalids2, InvalidSums2),
    sum_list(InvalidSums2, Result2),
    write("Part 2: "), write(Result2), nl,

    halt.

:- initialization(main).

    I made a note to learn about records, as right now I'm just using lists for everything.

    3 votes
  3. tomf
    (edited )
    Link
    This is only part one. I'll do the second later. Google Sheets =INDEX( LET( _i,SPLIT(TOCOL(SPLIT(A1,",")),"-"), _n,--REPT(ROW(1:99999),2), SUM( SPLIT( BYROW( _i, LAMBDA( _x, LET( _l,INDEX(_x,0,1),...

    This is only part one. I'll do the second later.

    Google Sheets 
    =INDEX(
  LET(
   _i,SPLIT(TOCOL(SPLIT(A1,",")),"-"),
   _n,--REPT(ROW(1:99999),2),
   SUM(
    SPLIT(
     BYROW(
      _i,
      LAMBDA(
       _x,
       LET(
        _l,INDEX(_x,0,1),
        _r,INDEX(_x,0,2),
        JOIN(
         ",",
         IFERROR(
          QUERY(
           _n,
           "where
             Col1 >="&_l&" and 
             Col1 <="&_r&""),
          ","))))),
    ","))))

    edit: faster

    2 votes
  4. netsplit
    (edited )
    Link
    Here are my solutions for both parts in Perl using a feature from the relatively newly released v5.42. I always find that I lean a little heavily on regular expressions for my Advent of Code...

    Here are my solutions for both parts in Perl using a feature from the relatively newly released v5.42. I always find that I lean a little heavily on regular expressions for my Advent of Code solutions.

    Part 1 (Perl) 
    #!/usr/bin/env perl

use strict;
use warnings;

use v5.42.0;

use feature 'keyword_all';
no warnings 'experimental::keyword_all';

use File::Slurper 'read_lines';

my @content = read_lines 'input.txt';
my @ranges  = split ',', $content[0];
my $total   = 0;

foreach my $range (@ranges) {
    my ($start, $end) = split '-', $range;

    foreach my $id ($start..$end) {
        my @chars  = split //, $id;
        my $digits = scalar @chars;

        next if $digits % 2 != 0;

        my $count = int $digits / 2;
        my @parts = $id =~ /\d{$count}/g;

        $total += $id if scalar @parts == 2 && $parts[0] == $parts[1];
    }
}

print "The answer is: ${total}\n";
    Part 2 (Perl) 
    #!/usr/bin/env perl

use strict;
use warnings;

use v5.42.0;

use feature 'keyword_all';
no warnings 'experimental::keyword_all';

use File::Slurper 'read_lines';

my @content = read_lines 'input.txt';
my @ranges  = split ',', $content[0];
my $total   = 0;

foreach my $range (@ranges) {
    my ($start, $end) = split '-', $range;

    ID: foreach my $id ($start..$end) {
        my @chars  = split //, $id;
        my $digits = scalar @chars;

        next if $digits < 2;

        for (my $i = 2; $i <= $digits; ++$i) {
            next if $digits % $i != 0;

            my $count = int $digits / $i;
            my @parts = $id =~ /\d{$count}/g;

            if (scalar @parts == $i && all { $_ eq $parts[0] } @parts) {
                $total += $id;

                next ID;
            }
        }
    }
}

print "The answer is: ${total}\n";

    Slightly compacted versions...

    Part 1 (Perl) 
    perl -ne 'for(split/,/){($s,$e)=split/-/;for($s..$e){$t+=$_ if/^(.*)\1$/}}print$t' input.txt
    Part 2 (Perl) 
    perl -ne 'for(split/,/){($s,$e)=split/-/;for($s..$e){$t+=$_ if/^(.*)\1+$/}}print$t' input.txt
    1 vote
  5. jonah
    Link
    I didn't post yesterday because I was annoyed at how long it took me. I was much happier today. My part 1 took very little time to write and executed pretty quickly, but part 2 took a little...

    I didn't post yesterday because I was annoyed at how long it took me. I was much happier today. My part 1 took very little time to write and executed pretty quickly, but part 2 took a little longer. On my machine I averaged about 1.2s. I decided to plug in some threading (not included here) to see if I could get it faster, and got it down to ~230ms. That was a cool win for today!

    Part 1 
    from common import load_input
input = load_input()

# There's gotta be a better way to do this
def id_is_invalid(prod_id: int) -> bool:
    str_id = str(prod_id)
    if len(str_id) % 2 != 0:
        return False
    mid = int(len(str_id) / 2)
    first, last = str_id[:mid], str_id[mid:]
    return first == last

# Gross, but it works
ranges = list(map(lambda x: list(map(lambda y: int(y), x.split('-'))), input.split(',')))
counter = 0

# Dumb solution but it works
for r in ranges:
    for prod_id in range(r[0], r[1] + 1):
        if id_is_invalid(prod_id):
            counter += prod_id

print(counter)
    Part 2 
    from common import load_input
input = load_input()

def has_pattern_count(s, m, k):
    if s.count(s[:m]) >= k:
        return True
    return False

def id_is_invalid(prod_id: int) -> bool:
    # Single digit IDs can't possibly match the criteria
    # And yes, this got me
    if prod_id < 10:
        return False

    str_id = str(prod_id)
    str_len = len(str_id)

    # m -> pattern length
    # k -> number of repetitions
    # m * k should always equal str_len
    # i.e., str_len / m should always be a whole number, and the result is k

    m = 1
    while m < (str_len / 2) + 1:
        if str_len % m == 0:
            k = str_len / m
            if has_pattern_count(str_id, m, k):
                return True
        m += 1

    return False

# Gross, but it works
ranges = list(map(lambda x: list(map(lambda y: int(y), x.split('-'))), input.split(',')))
counter = 0

# Dumb solution but it works
for r in ranges:
    print("Processing range:", r)
    for prod_id in range(r[0], r[1] + 1):
        if id_is_invalid(prod_id):
            counter += prod_id

print(counter)
    1 vote
  6. Berdes
    (edited )
    Link
    The problem today felt about as simple as yesterday, with my logic to find invalid IDs even uglier than the stuff I wrote yesterday. At least, I'm getting a hang of the syntax of Rust and didn't...

    The problem today felt about as simple as yesterday, with my logic to find invalid IDs even uglier than the stuff I wrote yesterday. At least, I'm getting a hang of the syntax of Rust and didn't need to spend much time searching the documentation.

    Instead of going through all the numbers in each range, I'm sure it's feasible to iterate over the first half of each number and directly check if the resulting repeating ID is inside the range. Thinking about it, I'm feeling like this could even yield a simpler logic than what I currently have.

    Part 1 and 2 (Rust) 
    use std::io;
use std::str::FromStr;

struct Range {
  a: u64,
  b: u64,
}

struct ParseRangeError {
  message: String,
}

impl FromStr for Range {
  type Err = ParseRangeError;

  fn from_str(s: &str) -> Result<Self, Self::Err> {
    let (a, b) = s.split_once('-').ok_or(ParseRangeError {
      message: format!("Invalid range {}, missing -", s),
    })?;
    let ia = a.parse::<u64>().map_err(|e| ParseRangeError {
      message: format!("Invalid number {}: {}", s, e),
    })?;
    let ib = b.parse::<u64>().map_err(|e| ParseRangeError {
      message: format!("Inavlid number {}: {}", s, e),
    })?;
    Ok(Range { a: ia, b: ib })
  }
}

fn is_invalid1(a: u64) -> bool {
  let mut mul = 10;
  while a > mul {
    if a < mul * mul && a > mul * mul / 10 {
      let tmp = a % mul;
      return a == tmp + tmp * mul;
    }
    mul *= 10;
  }
  return false;
}

fn is_invalid2(a: u64) -> bool {
  let mut mul = 10;
  while a > mul {
    let p = a % mul;
    let mut pmul = mul;
    while a > pmul {
      if (a / pmul) % mul != p {
        break;
      } else if a < pmul * mul && a > pmul * mul / 10 {
        return true;
      }
      pmul *= mul;
    }
    mul *= 10;
  }
  return false;
}

fn main() {
  let mut part1 = 0;
  let mut part2 = 0;
  let mut buffer = String::new();
  io::stdin().read_line(&mut buffer).unwrap();
  for range in buffer.trim().split(',').map(|e| e.parse::<Range>()) {
    match range {
      Ok(r) => {
        for n in r.a..r.b + 1 {
          part1 += if is_invalid1(n) { n } else { 0 };
          part2 += if is_invalid2(n) { n } else { 0 };
        }
      }
      Err(e) => panic!("Error reading range: {}", e.message),
    }
  }
  println!("Part 1: {}", part1);
  println!("Part 2: {}", part2);
}

    Edit: Indeed, it's possible to keep track of the part that is going to be repeated and iterate directly over it. Based on the result, it's not exactly simpler, especially since the second part still needs the is_invalid logic to avoid double-counting numbers in the range. At least, it's mighty fast: it's running in ~1ms including all the overhead of starting the process and parsing the input while the previous version took ~120ms.

    Implementation of the sum of invalid IDs over a range for both parts 
    fn length(mut a: u64) -> u64 {
  if a == 0 {
    return 1;
  }
  let mut l = 0;
  while a > 0 {
    a /= 10;
    l += 1;
  }
  return l;
}

fn pow(n: u64, e: u64) -> u64 {
  let mut ret = 1;
  for _ in 0..e {
    ret *= n;
  }
  return ret;
}

fn sum_range1(r: &Range) -> u64 {
  let l = length(r.a);
  let mut first_half = if l % 2 == 0 {
    r.a / pow(10, l / 2)
  } else {
    pow(10, l / 2)
  };
  let mut ret = 0;
  loop {
    let n = first_half * pow(10, length(first_half)) + first_half;
    if n > r.b {
      break;
    }
    if n >= r.a {
      ret += n;
    }
    first_half += 1;
  }
  return ret;
}

fn is_invalid2(a: u64) -> bool {
  let mut mul = 10;
  while a > mul {
    let p = a % mul;
    let mut pmul = mul;
    while a > pmul {
      if (a / pmul) % mul != p {
        break;
      } else if a < pmul * mul && a > pmul * mul / 10 {
        return true;
      }
      pmul *= mul;
    }
    mul *= 10;
  }
  return false;
}

fn sum_range2(r: &Range) -> u64 {
  let la = length(r.a);
  let lb = length(r.b);
  let mut ret = 0;
  for num_parts in 2..lb + 1 {
    let mut part = if la % num_parts == 0 {
      r.a / pow(10, (num_parts - 1) * la / num_parts)
    } else {
      pow(10, la / num_parts)
    };
    loop {
      let mut n = part;
      let mult = pow(10, length(part));
      for _ in 1..num_parts {
        n = n * mult + part;
      }
      if n > r.b {
        break;
      }
      // If the part is invalid, the number formed risks being counted multiple
      // times. E.g. 1111 can be decomposed as four 1 or two 11. When this
      // happens, exactly one decomposition will have a part that is also a
      // valid ID.
      if n >= r.a && !is_invalid2(part) {
        ret += n;
      }
      part += 1;
    }
  }
  return ret;
}

    Edit 2: actually, things can be pushed even further since the sum of invalid IDs (for part 1) in the range 123000..456999 is the same as the sum of numbers 123..456 times 101, which can be computer is O(1) using the fact that the sum of numbers from 1 to n (included) is n*(n+1)/2. Part 2 becomes even more interesting since you also want to exclude all the numbers that are invalid IDs from the sum of the consecutive numbers, which can be done using a recursive call to the function that computes the sum of invalid IDs for a given range. Thus, it's not actually necessary to have an is_valid function for part 2 either.

    1 vote
  7. [4]
    balooga
    Link
    I haven’t started writing code yet, just looking at the puzzle for now. Something’s bugging me… Can someone help me understand why 111 and 999 are apparently NOT invalid? I thought I understood...

    I haven’t started writing code yet, just looking at the puzzle for now. Something’s bugging me…

    Since the young Elf was just doing silly patterns, you can find the invalid IDs by looking for any ID which is made only of some sequence of digits repeated twice. So, 55 (5 twice), 6464 (64 twice), and 123123 (123 twice) would all be invalid IDs.

    None of the numbers have leading zeroes; 0101 isn't an ID at all. (101 is a valid ID that you would ignore.)

    Your job is to find all of the invalid IDs that appear in the given ranges. In the above example:

    • 11-22 has two invalid IDs, 11 and 22.
    • 95-115 has one invalid ID, 99.
    • 998-1012 has one invalid ID, 1010.
      […]

    Can someone help me understand why 111 and 999 are apparently NOT invalid? I thought I understood the rule but those two are throwing me off.

    1. [3]
      jonah
      Link Parent
      Because in those numbers, the repeated digits are repeated more than twice

      Because in those numbers, the repeated digits are repeated more than twice

      2 votes
      1. [2]
        balooga
        Link Parent
        D’oh! Thanks! That should actually make the logic a good deal simpler (at least until the Part 2 complication comes along and undoes everything…)!

        D’oh! Thanks!

        That should actually make the logic a good deal simpler (at least until the Part 2 complication comes along and undoes everything…)!

        2 votes
        1. jonah
          Link Parent
          You're welcome! good luck and have fun

          You're welcome! good luck and have fun

          1 vote