15 votes

Day 3: Gear Ratios

Automatically posted
Tags: advent of code.2023

Today's problem description: https://adventofcode.com/2023/day/3

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>

17 comments

  1. [2]
    akk
    Link
    Not too easy, not too hard. Had to take some breaks to help with my mother who is currently recovering from neck/back surgery. It's also a lot verbose than I've seen compared to others. I also...

    Not too easy, not too hard. Had to take some breaks to help with my mother who is currently recovering from neck/back surgery. It's also a lot verbose than I've seen compared to others. I also switched over to using JetBrains IntelliJ IDEA's built-in HTTP client for sending my input vs using the excellent RapidAPI for Mac (formerly Paw)

    Ran into a lot of issues with an off-by-one, but I solved it :-D

    Java 
    package com.michaeleisemann.aoc23.services;

import com.michaeleisemann.aoc23.interfaces.DayInterface;
import org.springframework.stereotype.Service;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

// https://adventofcode.com/2023/day/3
@Service
public class Day3Service implements DayInterface {

    private static class Schematic {

        private record PartNumber(int partNumber, int startX, int endX, int y) {
        }

        private record PartSymbol(String symbol, int x, int y) {
        }

        private final List<String> schematic = new ArrayList<>();

        private final List<PartNumber> partNumbers = new ArrayList<>();
        private final List<PartSymbol> partSymbols = new ArrayList<>();

        public Schematic(String schematic) {
            String[] lines = schematic.split("\n");
            this.schematic.addAll(Arrays.asList(lines));
            parseSchematic();
        }

        public List<String> getSchematic() {
            return schematic;
        }

        public List<PartNumber> getPartNumbers() {
            return partNumbers;
        }

        public List<PartSymbol> getPartSymbols() {
            return partSymbols;
        }

        private void parseSchematic() {
            for (int y = 0; y < schematic.size(); y++) {
                String line = schematic.get(y);
                StringBuilder partNumber = new StringBuilder();
                int startX = 0;
                int endX = 0;
                for (int x = 0; x < line.length(); x++) {
                    if (Character.isDigit(line.charAt(x))) {
                        if (partNumber.isEmpty()) {
                            startX = x;
                        }
                        partNumber.append(line.charAt(x));
                        // I hate off by one errors
                        if (x == line.length() - 1) {
                            endX = x - 1;
                            PartNumber part = new PartNumber(
                                    Integer.parseInt(partNumber.toString()),
                                    startX,
                                    endX,
                                    y
                            );
                            partNumber = new StringBuilder();
                            partNumbers.add(part);
                        }
                    } else {
                        // we are done collecting part numbers
                        if (!partNumber.isEmpty()) {
                            endX = x - 1;
                            PartNumber part = new PartNumber(
                                    Integer.parseInt(partNumber.toString()),
                                    startX,
                                    endX,
                                    y
                            );
                            partNumber = new StringBuilder();
                            partNumbers.add(part);
                        }
                        if (line.charAt(x) != '.') {
                            PartSymbol partSymbol = new PartSymbol(
                                    String.valueOf(line.charAt(x)),
                                    x,
                                    y
                            );
                            partSymbols.add(partSymbol);
                        }
                    }
                }
            }
        }
    }

    public String part1(String puzzleInput) {
        Schematic schematic = new Schematic(puzzleInput);

        int partNumberSum = 0;

        for (Schematic.PartNumber partNumber : schematic.getPartNumbers()) {
            for (Schematic.PartSymbol partSymbol : schematic.getPartSymbols()) {
                if (partNumber.y() == partSymbol.y()) {
                    if (partNumber.startX() - 1 <= partSymbol.x() && partNumber.endX() + 1 >= partSymbol.x()) {
                        logger.debug("Same line: {} {} {}", partNumber.partNumber(), partSymbol.symbol());
                        partNumberSum += partNumber.partNumber();
                    }
                } else if (partNumber.y() - 1 <= partSymbol.y() && partNumber.y() + 1 >= partSymbol.y()) {
                    if (partNumber.startX() - 1 <= partSymbol.x() && partNumber.endX() + 1 >= partSymbol.x()) {
                        logger.debug("Different line: {} {} {}", partNumber.partNumber(), partSymbol.symbol());
                        partNumberSum += partNumber.partNumber();
                    }
                }
            }
        }

        return String.valueOf(partNumberSum);

    }

    public String part2(String puzzleInput) {

        Schematic schematic = new Schematic(puzzleInput);


        HashMap<Schematic.PartSymbol, ArrayList<Schematic.PartNumber>> partSymbolPartNumberHashMap = new HashMap<>();

        for (Schematic.PartNumber partNumber : schematic.getPartNumbers()) {
            for (Schematic.PartSymbol partSymbol : schematic.getPartSymbols()) {
                if (partNumber.y() == partSymbol.y()) {
                    addPartToSymbol((HashMap<Schematic.PartSymbol, ArrayList<Schematic.PartNumber>>) partSymbolPartNumberHashMap, partNumber, partSymbol);
                } else if (partNumber.y() - 1 <= partSymbol.y() && partNumber.y() + 1 >= partSymbol.y()) {
                    addPartToSymbol((HashMap<Schematic.PartSymbol, ArrayList<Schematic.PartNumber>>) partSymbolPartNumberHashMap, partNumber, partSymbol);
                }
            }
        }

        // go through the hashmap and see which * have exactly 2 part numbers
        int gearRatioSum = 0;
        for (Schematic.PartSymbol partSymbol : partSymbolPartNumberHashMap.keySet()) {
            if (partSymbol.symbol().equals("*")) {
                if (partSymbolPartNumberHashMap.get(partSymbol).size() == 2) {
                    // multiply the part numbers together
                    int gearRatio = 1;
                    for (Schematic.PartNumber partNumber : partSymbolPartNumberHashMap.get(partSymbol)) {
                        gearRatio *= partNumber.partNumber();
                    }
                    gearRatioSum += gearRatio;
                }
            }
        }

        return String.valueOf(gearRatioSum);
    }

    private void addPartToSymbol(HashMap<Schematic.PartSymbol, ArrayList<Schematic.PartNumber>> partSymbolPartNumberHashMap, Schematic.PartNumber partNumber, Schematic.PartSymbol partSymbol) {
        if (partNumber.startX() - 1 <= partSymbol.x() && partNumber.endX() + 1 >= partSymbol.x()) {
            // add the part number to the hashmap
            if (partSymbolPartNumberHashMap.containsKey(partSymbol)) {
                partSymbolPartNumberHashMap.get(partSymbol).add(partNumber);
            } else {
                ArrayList<Schematic.PartNumber> partNumbers = new ArrayList<>();
                partNumbers.add(partNumber);
                partSymbolPartNumberHashMap.put(partSymbol, partNumbers);
            }
        }
    }
}
    3 votes
    1. tjf
      Link Parent
      Very enterprise!

      Very enterprise!

      2 votes
  2. Crespyl
    Link
    This seems tricky for the third day, but it's really just another parsing problem at its core. I was able to re-use a utility class from previous years, which helps a lot with handling grids like...

    This seems tricky for the third day, but it's really just another parsing problem at its core. I was able to re-use a utility class from previous years, which helps a lot with handling grids like this (they come up frequently in AoC problems).

    Part 1 - Ruby 
    def compute_p1(input)
  symbols = "*#/+%$&=@-".chars
  g = Grid.new(input)
  # find each symbol
  g.coords_where { |c| symbols.include?(c) }
   .map { |x,y| get_neighboring_numbers(g, x, y) }
   .flatten
   .sum
end

def read_number(grid, start_x, start_y)
  str = grid.get(start_x,start_y).clone
  return nil unless str.match?(/[[:digit:]]/)
  x, y = start_x-1, start_y
  while grid.get(x,y) != nil && grid.get(x,y).match?(/[[:digit:]]/)
    str.insert(0, grid.get(x,y))
    x -= 1
  end
  x = start_x+1
  while grid.get(x,y) != nil && grid.get(x,y).match?(/[[:digit:]]/)
    str.concat(grid.get(x,y))
    x += 1
  end
  str.to_i
end

def get_neighboring_numbers(grid, start_x, start_y)
    [
      [-1, -1], [0, -1], [+1, -1],
      [-1,  0],          [+1,  0],
      [-1, +1], [0, +1], [+1, +1]
    ].map { |dx, dy| [start_x+dx, start_y+dy] }
     .filter { |x, y| grid.get(x,y).match?(/[[:digit:]]/) }
     .map { |x, y| read_number(grid, x, y) }
     .uniq # assuming there are no two identical numbers on the same symbol
end

class Grid
  attr_accessor :grid
  attr_accessor :width
  attr_accessor :height
  attr_accessor :default

  def initialize(input, default: nil)
    @grid = input.lines
              .map(&:strip)
              .map(&:chars)
    @width = @grid[0].size
    @height = @grid.size
    @default = default
  end

  def in_bounds?(x, y)
    x >= 0 && x < @width && y >= 0 && y < @height
  end

  def get(x,y)
    if x < 0 || x >= @width || y < 0 || y >= @height
      @default
    else
      @grid[y][x]
    end
  end

  def set(x,y,val)
    if x < 0 || x >= @width || y < 0 || y >= @height
      raise "Tried to write out of bounds"
    else
      @grid[y][x] = val
    end
  end

  def all_coords
    (0...width).to_a.product((0...height).to_a)
  end

  def coords_where
    all_coords.filter { |x, y| yield(@grid[y][x]) }
  end

  def each_index
    all_coords.each do |x,y|
      yield(x,y)
    end
  end

  def update
    each_index do |x, y|
      @grid[y][x] = yield(x, y, @grid[y][x])
    end
  end

  def ==(other)
    return false if other.class != Grid
    return other.grid == @grid
  end

  def all?(value)
    return @grid.flatten.all?(value)
  end

  def neighbors(x,y)
    [
      [-1, -1], [0, -1], [+1, -1],
      [-1,  0],          [+1, 0],
      [-1, +1], [0, +1], [+1, +1]
    ].map { |dx, dy| get(x+dx, y+dy) }
  end

  def to_s
    s = ""
    height.times do |y|
      width.times do |x|
        s << get(x,y) || default.to_s
      end
      s << "\n"
    end
    return s
  end

  def count(value)
    if block_given?
      @grid.flatten.count(&block)
    else
      @grid.flatten.count(value)
    end
  end
end
    Part 2

    Part 2 becomes easy when we already have everything in a searchable grid format.

    def compute_p2(input)
  g = Grid.new(input)
  g.coords_where { |c| c == "*" }
   .map { |x,y| get_neighboring_numbers(g, x, y) }
   .filter { |numbers| numbers.length == 2 }
   .map { |numbers| numbers.inject(&:*) }
   .sum
end
    2 votes
  3. csos95
    (edited )
    Link
    Today's puzzle tripped me up for a bit and then I got stuck at part two because of a dumb issue where I set the final result to the last calculation rather than summing them up. I'll probably go...

    Today's puzzle tripped me up for a bit and then I got stuck at part two because of a dumb issue where I set the final result to the last calculation rather than summing them up.
    I'll probably go back over it tomorrow to make a better/more concise version.

    Rust 
    use aoc_runner_derive::aoc;
use logos::{Lexer, Logos};
use std::collections::{HashMap, HashSet};

fn get_count(lex: &mut Lexer<Num>) -> Option<i64> {
    Some(lex.slice().parse().unwrap())
}

#[derive(Logos)]
enum Num {
    #[regex("[0-9]+", get_count)]
    Num(i64),

    #[error]
    #[regex(r"([^0-9])", logos::skip)]
    Error,
}

#[aoc(day3, part1)]
fn part1(input: &str) -> i64 {
    let grid: Vec<Vec<char>> = input.lines().map(|line| line.chars().collect()).collect();

    let mut part_sum = 0;
    input.lines().enumerate().for_each(|(row, line)| {
        let row = row as i64;
        for (num, range) in Num::lexer(line).spanned() {
            match num {
                Num::Num(n) => {
                    for col in range {
                        let col = col as i64;
                        let mut to_check = Vec::new();
                        let up = row - 1;
                        let down = row + 1;
                        let left = col - 1;
                        let right = col + 1;
                        if up > 0 {
                            to_check.push((up, col));
                        }
                        if down < 140 {
                            to_check.push((down, col));
                        }
                        if left > 0 {
                            to_check.push((row, left));
                        }
                        if right < 140 {
                            to_check.push((row, right));
                        }
                        if up > 0 && left > 0 {
                            to_check.push((up, left));
                        }
                        if down < 140 && right < 140 {
                            to_check.push((down, right));
                        }
                        if left > 0 && down < 140 {
                            to_check.push((down, left));
                        }
                        if right < 140 && up > 0 {
                            to_check.push((up, right));
                        }

                        let mut is_part_num = false;
                        for (x, y) in to_check {
                            if !grid[x as usize][y as usize].is_ascii_digit()
                                && grid[x as usize][y as usize] != '.'
                            {
                                is_part_num = true;
                                break;
                            }
                        }
                        if is_part_num {
                            part_sum += n;
                            break;
                        }
                    }
                }
                _ => {}
            }
        }
    });

    part_sum
}

#[aoc(day3, part2)]
fn part2(input: &str) -> i64 {
    let grid: Vec<Vec<char>> = input.lines().map(|line| line.chars().collect()).collect();

    let mut gear_nums: HashMap<(i64, i64), Vec<i64>> = HashMap::new();
    input.lines().enumerate().for_each(|(row, line)| {
        let row = row as i64;
        for (num, range) in Num::lexer(line).spanned() {
            match num {
                Num::Num(n) => {
                    let mut seen_gears: HashSet<(i64, i64)> = HashSet::new();
                    for col in range {
                        let col = col as i64;
                        let mut to_check = Vec::new();
                        let up = row - 1;
                        let down = row + 1;
                        let left = col - 1;
                        let right = col + 1;

                        if up > 0 {
                            to_check.push((up, col));
                        }
                        if down < 140 {
                            to_check.push((down, col));
                        }
                        if left > 0 {
                            to_check.push((row, left));
                        }
                        if right < 140 {
                            to_check.push((row, right));
                        }
                        if up > 0 && left > 0 {
                            to_check.push((up, left));
                        }
                        if down < 140 && right < 140 {
                            to_check.push((down, right));
                        }
                        if left > 0 && down < 140 {
                            to_check.push((down, left));
                        }
                        if right < 140 && up > 0 {
                            to_check.push((up, right));
                        }

                        for (x, y) in to_check {
                            if grid[x as usize][y as usize] == '*' && !seen_gears.contains(&(x, y))
                            {
                                gear_nums.entry((x, y)).or_default().push(n);
                                seen_gears.insert((x, y)); //
                            }
                        }
                    }
                }
                _ => {}
            }
        }
    });

    let mut gear_sum: i64 = 0;
    for (_, nums) in gear_nums {
        if nums.len() == 2 {
            gear_sum += nums.into_iter().product::<i64>();
        }
    }

    gear_sum
}
    2 votes
  4. tjf
    Link
    Harder day three than expected -- felt more like a one-week-in problem. There were a couple of edge cases in my input that were not present in the sample, which was frustrating. I don't love the...

    Harder day three than expected -- felt more like a one-week-in problem. There were a couple of edge cases in my input that were not present in the sample, which was frustrating. I don't love the "look" of my solutions, but I guess a couple of nested for loops is common for these grid-style problems.

    Anyway here are my Python solutions:

    Part 1 
    #!/usr/bin/env pypy3

def adjacents(board, r, c, nlen):
    for rr in range(r - 1, r + 2):
        for cc in range(c - 1, c + nlen + 1):
            if (0 <= rr < len(board) and 0 <= cc < len(board[0])
                and not (r == rr and c <= cc < c + nlen)):
                yield (rr, cc)

total = 0
board = [[*line.strip()] for line in open(0)]
for r in range(len(board)):
    for c in range(len(board[0])):
        if board[r][c].isdigit() and board[r][c] != '0':
            n = board[r][c]
            for cc in range(c + 1, len(board[0])):
                if not board[r][cc].isdigit():
                    break
                n += board[r][cc]
                board[r][cc] = '0'
            if any(board[rr][cc] not in ('0123456789.')
                   for rr, cc in adjacents(board, r, c, len(n))):
                total += int(n)

print(total)
    Part 2 
    #!/usr/bin/env pypy3

from collections import defaultdict
from math import prod

def adjacents(board, r, c, nlen):
    for rr in range(r - 1, r + 2):
        for cc in range(c - 1, c + nlen + 1):
            if (0 <= rr < len(board) and 0 <= cc < len(board[0])
                and not (r == rr and c <= cc < c + nlen)):
                yield (rr, cc)

gearnums = defaultdict(list)
board = [[*line.strip()] for line in open(0)]
for r in range(len(board)):
    for c in range(len(board[0])):
        if board[r][c].isdigit() and board[r][c] != '0':
            n = board[r][c]
            for cc in range(c + 1, len(board[0])):
                if not board[r][cc].isdigit():
                    break
                n += board[r][cc]
                board[r][cc] = '0'
            for rr, cc in adjacents(board, r, c, len(n)):
                if board[rr][cc] == '*':
                    gearnums[(rr, cc)].append(int(n))

total = sum(prod(nums) for nums in gearnums.values() if len(nums) == 2)
print(total)
    2 votes
  5. whs
    (edited )
    Link
    I thought yesterday that I'll use Nix for day 3. Oh boy, that was a mistake. At least the problem didn't ask me to walk vertically. Part 2 took me like 2 hours due to an off-by-one error in...

    I thought yesterday that I'll use Nix for day 3. Oh boy, that was a mistake. At least the problem didn't ask me to walk vertically.

    Part 2 took me like 2 hours due to an off-by-one error in getNumberAt, and the gearsNeighbors grid in part 2 had the bottom left written as +, + instead of +, -. I had to built my own test case to find these.

    I can't figure out how to use nix repl to run a non-repl code. So instead, this file build a test derivation with dummy value, and crash on test assertion failures. For the real solutions the output will be in the derivation build result file. And of course, to compute the gear values Nix will need to build/download a new bash, gcc, etc..

    {
	outputs = { nixpkgs, ... }: with builtins; let
		lib = nixpkgs.lib;
		pkgs = import nixpkgs { system = "x86_64-linux"; };
		input = readFile ./input.txt;
		exampleInput1 = readFile ./example.txt;
		isSymbol = v: ! (elem v ["." "0" "1" "2" "3" "4" "5" "6" "7" "8" "9"]);
		# Like foldl but op is called with (op acc index value)
		ifoldl0 = op: nul: list: foldl' (acc: i: op acc i (elemAt list i)) nul (genList (i: i) (length list));
		isSymbolAt = lines: row: col:
			let
				line = elemAt lines row;
				char = substring col 1 line;
			in 
				# This also handle overflows...
				if row < 0 then false
				else if col < 0 then false
				else if row >= length lines then false
				else if col >= stringLength line then false
				else isSymbol char;
		# Return [{number; col} ...]
		getNumbers = line: 
			let
				chars = lib.strings.stringToCharacters line;
				numbers = ifoldl0 (
					acc: index: char:
						let
							last = lib.lists.last acc;
						in if isSymbol char || char == "." then
							# If this is symbol, ensure that the last member of acc is [0]
							if last.col == -1 then acc
							else acc ++ [{number = 0; col = -1;}]
						else
							# This is a number, add it to the last number
							(lib.lists.init acc)
							++ [{
								number = (last.number*10) + (lib.strings.toInt char);
								col = if last.col != -1 then last.col else index;
							}]
				) [{number = 0; col = -1;}] chars;
			in
				# The last number might be invalid, remove it
				if (lib.lists.last numbers).col == -1 then lib.lists.init numbers
				else numbers;
		# Return [{number; col; row;} ..]
		getNumberLines = lines: lib.lists.flatten (lib.lists.imap0 (row: line: map (item: item // {inherit row;}) (getNumbers line)) lines);
		sumNumbers = numbers: foldl' (acc: cur: acc + cur.number) 0 numbers;
		filterNumberNextToSymbol = lines: numbers: filter (
			number: let
				_isSymbolAt = isSymbolAt lines;
				numberLen = stringLength (toString number.number);
				rowRange = lib.lists.range (number.col - 1) (number.col + numberLen);
			in any lib.trivial.id (lib.lists.flatten [
				# above row
				(map (col: _isSymbolAt (number.row - 1) col) rowRange)
				# left
				(_isSymbolAt number.row (number.col - 1))
				# right
				(_isSymbolAt number.row (number.col + numberLen))
				# bottom row
				(map (col: _isSymbolAt (number.row + 1) col) rowRange)
			])
		) numbers;
		solve1 = problem: let
			lines = lib.strings.splitString "\n" (lib.strings.removeSuffix "\n" problem);
			numbers = getNumberLines lines;
		in
			# numbers;
			# filterNumberNextToSymbol lines numbers;
			sumNumbers (filterNumberNextToSymbol lines numbers);

		getGearPositionsLine = line:
			filter
				(x: x != null)
				(
					lib.lists.imap0
					(i: ch: if ch == "*" then {col=i;} else null)
					(lib.strings.stringToCharacters line)
				);
		getGearPositions = lines: lib.lists.flatten (lib.lists.imap0 (row: line: map (item: item // {inherit row;}) (getGearPositionsLine line)) lines);
		# Return the number occupying the space at {row, col}
		getNumberAt = numbers: row: col: lib.lists.findFirst (
			number: let
				numberLen = stringLength (toString number.number);
			in
				number.row == row && number.col <= col && number.col + numberLen > col
		) null numbers;
		solve2 = problem: let
			lines = lib.strings.splitString "\n" (lib.strings.removeSuffix "\n" problem);
			numbers = getNumberLines lines;
			gears = getGearPositions lines;
			gearsNeighbors = map (
				gear: let
					_getNumberAt = getNumberAt numbers;
					neighbors = [
						(_getNumberAt (gear.row - 1) (gear.col - 1)) (_getNumberAt (gear.row - 1) (gear.col)) (_getNumberAt (gear.row - 1) (gear.col + 1))
						(_getNumberAt (gear.row    ) (gear.col - 1))                                          (_getNumberAt (gear.row    ) (gear.col + 1))
						(_getNumberAt (gear.row + 1) (gear.col - 1)) (_getNumberAt (gear.row + 1) (gear.col)) (_getNumberAt (gear.row + 1) (gear.col + 1))
					];
				in lib.lists.unique (lib.lists.remove null neighbors)
			) gears;
			correctGearNeighbors = filter (l: length l == 2) gearsNeighbors;
			# _dbgCorrectGearNeighbors = lib.debug.traceSeq (toJSON correctGearNeighbors) correctGearNeighbors;
			correctGearNeighborsRatio = map (x: (elemAt x 0).number * (elemAt x 1).number) correctGearNeighbors;
		in
			foldl' builtins.add 0 correctGearNeighborsRatio;
	in {
		part1 = pkgs.writeText "$out" "${toString (solve1 input)}";
		part2 = pkgs.writeText "$out" "${toString (solve2 input)}";
		test = assert !isSymbol ".";
			assert !isSymbol "0";
			assert !isSymbol "1";
			assert isSymbol "$";
			assert isSymbol "!";
			assert isSymbol "*";
			assert ifoldl0 (acc: i: elem: elem) 0 ["a" "b" "c"] == "c";
			assert ifoldl0 (acc: i: elem: i) 0 ["a" "b" "c"] == 2;
			assert lib.debug.traceValSeq (getNumbers "467..114..") == [{number = 467; col=0;} {number=114; col=5;}];
			assert lib.debug.traceValSeq (getNumbers "467..114") == [{number = 467; col=0;} {number=114; col=5;}];
			assert lib.debug.traceValSeq (getNumbers "..467..114..") == [{number = 467; col=2;} {number=114; col=7;}];
			assert lib.debug.traceValSeq (getNumberLines ["1.." "..2"]) == [{number = 1; col=0; row=0;} {number=2; col=2; row=1;}];
			assert getNumberAt [{number = 467; col=0; row = 0;} {number=114; col=5; row=0;}] 0 2 == {number = 467; col=0; row=0;};
			assert getNumberAt [{number = 268; col=5; row = 0;}] 0 4 == null;
			assert getNumberAt [{number = 514; col=1; row = 0;}] 0 4 == null;
			assert sumNumbers [{number = 467; col=0;} {number=114; col=5;}] == 467+114;
			assert isSymbolAt ["1.$" "..2"] 0 2;
			assert !isSymbolAt ["1.$" "..2"] 0 0;
			assert !isSymbolAt ["1.$" "..2"] (-1) 2;
			assert !isSymbolAt ["1.$" "..2"] 3 0;
			assert !isSymbolAt ["1.$" "..2"] 0 3;
			assert lib.debug.traceValSeq (getGearPositionsLine "...*......") == [{col=3;}];
			assert lib.debug.traceValSeq (solve1 exampleInput1) == 4361;
			assert lib.debug.traceValSeq (solve2 exampleInput1) == 467835;
			assert solve2 "2\n*\n2" == 4;
			assert solve2 "2.3\n.*." == 6;
			assert solve2 "2.3\n*.." == 0;
			assert solve2 "123\n.*.\n4.." == 123*4;
			assert solve2 "123*345" == 123*345;
			assert solve2 "#514.268\n.....*..\n...305.." == 268*305;
			pkgs.writeText "$out" "true";
	};
}
    2 votes
  6. pnutzh4x0r
    (edited )
    Link
    Language: Python Classic AoC grid problem... Tedious as usual, but very doable. Took my time and I'm pretty happy with the result. :] Part 1 For the first part, I decided to break the problem...

    Language: Python

    Classic AoC grid problem... Tedious as usual, but very doable. Took my time and I'm pretty happy with the result. :]

    Part 1

    For the first part, I decided to break the problem into: 1. Reading the schematic, 2. Finding the numbers, 3. Finding the parts. This was useful for Part 2 as I could re-use my read_schematic and find_numbers functions.

    Two things I typically do for grid problems:

    1. Pad the grid so you can avoid annoying boundary checks.
    2. I have a DIRECTIONS list I loop through so I can check easily check the neighbors.
    Schematic  = list[str]
Number     = tuple[int, int, int]

DIRECTIONS = (
    (-1, -1),
    (-1,  0),
    (-1,  1),
    ( 0, -1),
    ( 0,  1),
    ( 1, -1),
    ( 1,  0),
    ( 1,  1),
)

def read_schematic(stream=sys.stdin) -> Schematic:
    schematic = [line.strip() for line in stream]
    columns   = len(schematic[0]) + 2
    return [
        '.'*columns,
        *['.' + line + '.' for line in schematic],
        '.'*columns,
    ]

def is_symbol(s: str) -> bool:
    return not (s.isdigit() or s == '.')

def find_numbers(schematic: Schematic) -> Iterator[Number]:
    rows    = len(schematic)
    columns = len(schematic[0])

    for r in range(1, rows):
        for number in re.finditer(r'[0-9]+', schematic[r]):
            yield (r, *number.span())

def find_parts(schematic: Schematic, numbers: Iterator[Number]) -> Iterator[int]:
    for r, c_head, c_tail in numbers:
        part = int(schematic[r][c_head:c_tail])
        for c in range(c_head, c_tail):
            neighbors = (schematic[r + dr][c + dc] for dr, dc in DIRECTIONS)
            if any(is_symbol(neighbor) for neighbor in neighbors):
                yield part
                break

def main(stream=sys.stdin) -> None:
    schematic = read_schematic(stream)
    numbers   = find_numbers(schematic)
    parts     = find_parts(schematic, numbers)
    print(sum(parts))
    Part 2

    For the second part, I just found the stars, and then I found the gears by checking if the stars are next to two numbers (which I had found previously).

    def find_stars(schematic: Schematic) -> Iterator[Star]:
    rows    = len(schematic)
    columns = len(schematic[0])

    for r in range(1, rows):
        for c in range(1, columns):
            token = schematic[r][c]
            if token == '*':
                yield (r, c)

def find_gears(schematic: Schematic, stars: Iterator[Star], numbers: list[Number]) -> Iterator[int]:
    for star_r, star_c in stars:
        gears = [                                                                                                                      
            int(schematic[number_r][number_c_head:number_c_tail])
            for number_r, number_c_head, number_c_tail in numbers
            if any(star_r + dr == number_r and number_c_head <= (star_c + dc) < number_c_tail for dr, dc in DIRECTIONS)
        ]
        if len(gears) == 2:
            yield gears[0] * gears[1]

def main(stream=sys.stdin) -> None:
    schematic = read_schematic(stream)
    numbers   = find_numbers(schematic)
    stars     = find_stars(schematic)
    gears     = find_gears(schematic, stars, list(numbers))
    print(sum(gears))

    GitHub Repo

    2 votes
  7. jzimbel
    Link
    In case anyone else had the same bug in their code as I did, here's a hint. If you swap the sample input given in the puzzle instructions from this: Original sample input 467..114.. ...*.........

    In case anyone else had the same bug in their code as I did, here's a hint.

    If you swap the sample input given in the puzzle instructions from this:

    Original sample input 
    467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..
    to this:
    Tweaked sample input covering an extra edge case 
    467..114..
...*......
..35...633  # <- line changed
617....#..  # <- line changed
...*......  # <- line changed
.....+.58.
..592.....
......755.
...$.*....
.664.598..

    Your code should produce the same result.

    Elixir

    I started on this when the puzzle released at midnight in my timezone, but ended up deciding to sleep on it because I wasn't sure how best to represent the schematic as a data structure.

    I'm glad I took some time to think the structure through, because it made querying the data pretty straightforward for both parts.

    The code to parse the schematic into my struct is one giant list comprehension, by far the most complicated one I've written in this language, so that was... fun.

    Part 1 runs in 4.5-5ms, part 2 runs in 5-5.5ms, which I think is pretty good given everything that's going on here?

    Parts 1 and 2

    The Schematic module defines the data structure (the defstruct and the @type def), logic to parse it from the input string, and functions to query it for parts 1 and 2.

    Since you can't implicitly "re-use" a compound value (like a list or a map) with a pointer/reference in elixir, I had to explicitly make a lookup table using the built-in reference type.
    Coordinates of individual digits, which form part of a whole number, are mapped to a common reference. Then, a second map maps the reference to the number formed by the group of digits.
    This allows me to look up the number(s) adjacent to a symbol in logarithmic time, as well as uniquely identifying each number so I can avoid counting it more than once. The same number can also appear in multiple places in the schematic, so this helped me avoid bugs related to that as well.

    defmodule AdventOfCode.Solution.Year2023.Day03.Schematic do
  @type coords :: {non_neg_integer, non_neg_integer}
  @type t :: %__MODULE__{
          symbols: %{coords => char},
          digits: %{coords => reference},
          numbers: %{reference => non_neg_integer}
        }

  defstruct symbols: %{}, digits: %{}, numbers: %{}

  def from_input(input) do
    for {line, y} <- Enum.with_index(String.split(input, "\n", trim: true)),
        # Put an additional '.' at the end to make sure trailing digits get finalized as numbers
        line = line <> ".",
        {char, x} <- Enum.with_index(String.to_charlist(line)),
        reduce: %__MODULE__{} do
      # Non-symbol, completes a number
      {acc, start_coords, digits} when char == ?. ->
        finalize_number(acc, start_coords, digits)

      # Non-symbol
      acc when char == ?. ->
        acc

      # Digit, continues a number
      {acc, start_coords, digits} when char in ?0..?9 ->
        {acc, start_coords, [char - ?0 | digits]}

      # Digit, starts a new number
      acc when char in ?0..?9 ->
        {acc, {x, y}, [char - ?0]}

      # Symbol, completes a number
      {acc, start_coords, digits} ->
        acc
        |> finalize_number(start_coords, digits)
        |> then(&%{&1 | symbols: Map.put(&1.symbols, {x, y}, char)})

      # Symbol
      acc ->
        %{acc | symbols: Map.put(acc.symbols, {x, y}, char)}
    end

    # We know the acc will not end up in its {acc, start_coords, digits} alternate form
    # because the string will always end with '.', which will cause `finalize_number`
    # to be called even if the original input ends with a digit.
  end

  def symbol_adjacent_numbers(schematic) do
    # Get coords of all symbols
    schematic.symbols
    |> Map.keys()
    # Get all coords adjacent to those symbols
    |> Stream.flat_map(&adjacent_coords/1)
    # Get number refs for all those coords
    |> Stream.map(&schematic.digits[&1])
    # Remove duplicate refs
    |> Stream.uniq()
    # Remove nil
    |> Stream.reject(&is_nil/1)
    # Look up number for each ref
    |> Stream.map(&schematic.numbers[&1])
  end

  def gear_ratios(schematic) do
    # Get coords of all '*' symbols
    schematic.symbols
    |> Stream.flat_map(fn {coords, symbol} -> if symbol == ?*, do: [coords], else: [] end)
    # Get all coords adjacent to those symbols, keeping a separate list of adjacents per symbol
    |> Stream.map(&adjacent_coords/1)
    # Get number refs for each set of adjacent coords, filtering out duplicates & nil
    |> Stream.map(fn adjacents ->
      adjacents
      |> Stream.map(&schematic.digits[&1])
      |> Stream.uniq()
      |> Enum.reject(&is_nil/1)
    end)
    # Filter to those with exactly 2 adjacent number refs
    |> Stream.filter(&match?([_, _], &1))
    # Look up number for each ref and multiply each pair of numbers
    |> Stream.map(fn [ref1, ref2] -> schematic.numbers[ref1] * schematic.numbers[ref2] end)
  end

  # List of coords that produce the 8 coordinates surrounding a given coord when added to it
  @all_adjacent_deltas for x <- -1..1, y <- -1..1, not (x == 0 and y == 0), do: {x, y}

  defp adjacent_coords(coords) do
    Enum.map(@all_adjacent_deltas, &sum_coords(&1, coords))
  end

  defp sum_coords({x1, y1}, {x2, y2}), do: {x1 + x2, y1 + y2}

  defp finalize_number(acc, {x, y} = _start_coords, digits) do
    number = digits |> Enum.reverse() |> Integer.undigits()
    ref = make_ref()
    digit_positions = Map.new(0..(length(digits) - 1)//1, &{{x + &1, y}, ref})

    %{
      acc
      | digits: Map.merge(acc.digits, digit_positions),
        numbers: Map.put(acc.numbers, ref, number)
    }
  end
end

defmodule AdventOfCode.Solution.Year2023.Day03 do
  alias __MODULE__.Schematic

  def part1(input) do
    input
    |> Schematic.from_input()
    |> Schematic.symbol_adjacent_numbers()
    |> Enum.sum()
  end

  def part2(input) do
    input
    |> Schematic.from_input()
    |> Schematic.gear_ratios()
    |> Enum.sum()
  end
end
    2 votes
  8. whispersilk
    (edited )
    Link
    Rust This was fun! A little bit harder than yesterday but easier than day 1, I think. My solution isn't exactly optimized — there's definitely some nested looping going on that would slow things...

    Rust

    This was fun! A little bit harder than yesterday but easier than day 1, I think. My solution isn't exactly optimized — there's definitely some nested looping going on that would slow things down on larger inputs — but it's pretty quick at this scale and the hard part is still just the grid parsing. Because of that, I'll put my parser in a block of its own and then the solutions will be their own little follow-on blocks.

    Data structures and parser 
    #[derive(Debug)]
struct Part {
    id: u32,
    row: u32,
    col_left: u32,
    col_right: u32,
}

#[derive(Debug)]
struct Symbol {
    kind: char,
    row: u32,
    col: u32,
}

impl Part {
    fn new(id: u32, row: u32, col_left: u32, col_right: u32) -> Self {
        Self {
            id,
            row,
            col_left,
            col_right,
        }
    }

    fn adjacent_to(&self, other: &Symbol) -> bool {
        other.row >= self.row.saturating_sub(1)
            && other.row <= self.row + 1
            && other.col >= self.col_left.saturating_sub(1)
            && other.col <= self.col_right + 1
    }
}

fn parse_grid() -> Result<(Vec<Part>, Vec<Symbol>)> {
    let (mut row, mut col) = (0, 0);
    let (mut parts, mut symbols) = (Vec::new(), Vec::new());
    let mut curr_id = None;
    for c in load_input(3)?.chars() {
        match c {
            '\n' => {
                if let Some(id) = curr_id.take() {
                    parts.push(Part::new(id, row, col - 1 - id.ilog10(), col - 1));
                };
                row += 1;
                col = 0;
            }
            '.' => {
                if let Some(id) = curr_id.take() {
                    parts.push(Part::new(id, row, col - 1 - id.ilog10(), col - 1));
                };
                col += 1;
            }
            '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' => {
                let curr = c as u32 - 48;
                curr_id = curr_id.map(|v| v * 10 + curr).or(Some(curr));
                col += 1;
            }
            kind => {
                if let Some(id) = curr_id.take() {
                    parts.push(Part::new(id, row, col - 1 - id.ilog10(), col - 1));
                };
                symbols.push(Symbol { kind, row, col });
                col += 1;
            }
        };
    }
    parts.sort_unstable_by(|a, b| a.row.cmp(&b.row).then(a.col_left.cmp(&b.col_left)));
    symbols.sort_unstable_by(|a, b| a.row.cmp(&b.row).then(a.col.cmp(&b.col)));
    Ok((parts, symbols))
}
    Part 1 
    fn first() -> Result<String> {
    let (parts, symbols) = parse_grid()?;
    let sum = parts
        .iter()
        .filter_map(|part| {
            symbols
                .iter()
                .find(|s| part.adjacent_to(s))
                .map(|_| part.id)
        })
        .sum::<u32>();
    Ok(sum.to_string())
}
    Part 2 
    fn second() -> Result<String> {
    let (parts, symbols) = parse_grid()?;
    let ratio = symbols
        .iter()
        .filter(|symbol| symbol.kind == '*')
        .filter_map(|symbol| {
            let mut iter = parts.iter().filter(|part| part.adjacent_to(symbol));
            match (iter.next(), iter.next(), iter.next()) {
                (Some(part1), Some(part2), None) => Some(part1.id * part2.id),
                _ => None,
            }
        })
        .sum::<u32>();
    Ok(ratio.to_string())
}

    After completing yesterday's puzzles I put what I've got so far up on GitHub, and I'll do my best to keep it updated as the month goes on.

    2 votes
  9. first-must-burn
    Link
    Pretty nice little problem. I solved it, then went back and refactored my code into a more general grid structure out of my code, since I expect there to be more grid problems in the coming days....

    Pretty nice little problem. I solved it, then went back and refactored my code into a more general grid structure out of my code, since I expect there to be more grid problems in the coming days. I also took some time to write some tests for the grid code.

    With this structure, the only extra part is identifying the numbers as regions, everything else is provided by the adjacency methods in the grid structure.

    2 votes
  10. lily
    Link
    I would've gotten top 1000 on this, but wasted 25 minutes fixing a stupid bug where newlines were treated as symbols. Oh well. So far all the problems have been primarily based on just parsing the...

    I would've gotten top 1000 on this, but wasted 25 minutes fixing a stupid bug where newlines were treated as symbols. Oh well. So far all the problems have been primarily based on just parsing the input; hopefully there are some more interesting ones soon.

    Solution 
    # Advent of Code 2023
# Day 3: Gear Ratios

with open("inputs/day_3.txt") as file:
    schematic = [line.rstrip("\n") for line in file]

used_positions = []
part_sum = 0
ratio_sum = 0

for y, line in enumerate(schematic):
    for x, char in enumerate(line):
        if char not in ".0123456789":
            adj_count = 0
            ratio = 1

            for pos in (
                (x + 1, y), (x + 1, y + 1), (x, y + 1), (x - 1, y + 1),
                (x - 1, y), (x - 1, y - 1), (x, y - 1), (x + 1, y - 1)
            ):
                if 0 <= pos[0] < len(line) and 0 <= pos[1] < len(schematic):
                    if (
                        schematic[pos[1]][pos[0]] in "0123456789"
                        and pos not in used_positions
                    ):
                        part = schematic[pos[1]][pos[0]]
                        used_positions.append(pos)

                        check_x = pos[0] - 1

                        while (
                            check_x >= 0
                            and schematic[pos[1]][check_x] in "0123456789"
                            and (check_x, pos[1]) not in used_positions
                        ):
                            part = schematic[pos[1]][check_x] + part
                            used_positions.append((check_x, pos[1]))
                            check_x -= 1

                        check_x = pos[0] + 1

                        while (
                            check_x < len(line)
                            and schematic[pos[1]][check_x] in "0123456789" 
                            and (check_x, pos[1]) not in used_positions
                        ):
                            part = part + schematic[pos[1]][check_x]
                            used_positions.append((check_x, pos[1]))
                            check_x += 1

                        part_sum += int(part)

                        if char == "*" and adj_count < 2:
                            adj_count += 1
                            ratio *= int(part)

            if adj_count == 2:
                ratio_sum += ratio

print(f"Part 1: {part_sum}")
print(f"Part 2: {ratio_sum}")
    1 vote
  11. spit-evil-olive-tips
    Link
    part 1 package day03 import ( "fmt" "os" "strings" "github.com/spf13/cobra" ) type Schematic [][]byte type Position struct { row int col int } type PartNumber struct { value int row int startCol...
    part 1 
    package day03

import (
	"fmt"
	"os"
	"strings"

	"github.com/spf13/cobra"
)

type Schematic [][]byte

type Position struct {
	row int
	col int
}

type PartNumber struct {
	value    int
	row      int
	startCol int
	endCol   int
}

func parseInput(path string) (Schematic, error) {
	data, err := os.ReadFile(path)
	if err != nil {
		return nil, err
	}
	contents := string(data)

	var s Schematic

	lines := strings.Split(contents, "\n")

	for _, line := range lines {
		runes := []byte(line)
		s = append(s, runes)
	}

	return s, nil
}

func (s Schematic) isValidPartNumber(pn PartNumber) bool {
	var candidates []Position

	for col := pn.startCol - 1; col <= pn.endCol + 1; col++ {
		candidates = append(candidates, Position{pn.row - 1, col})
		candidates = append(candidates, Position{pn.row + 1, col})
	}

	candidates = append(candidates, Position{pn.row, pn.startCol - 1})
	candidates = append(candidates, Position{pn.row, pn.endCol + 1})

	for _, candidate := range candidates {
		if candidate.row < 0 || candidate.row >= len(s) {
			continue
		}

		if candidate.col < 0 || candidate.col >= len(s[candidate.row]) {
			continue
		}

		switch s[candidate.row][candidate.col] {
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			continue
		case '.':
			continue
		default:
			return true
		}
	}

	return false
}

func (s Schematic) getPartNumbersFromLine(row int, line []byte) []PartNumber {
	var partNumbers []PartNumber

	startCol := 0
	value := 0

	for col := 0; col <= len(line); col++ {
		var char byte
		if col == len(line) {
			char = '.'
		} else {
			char = line[col]
		}

		switch char {
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			if value == 0 {
				startCol = col
			}

			digit := int(char - '0')
			value = (value * 10) + digit

		default:
			if value > 0 {
				pn := PartNumber{
					value:    value,
					row:      row,
					startCol: startCol,
					endCol:   col - 1,
				}
				partNumbers = append(partNumbers, pn)
				value = 0
			}
		}
	}

	return partNumbers
}

func (s Schematic) getPartNumbers() []PartNumber {
	var partNumbers []PartNumber

	for row, line := range s {
		lineNumbers := s.getPartNumbersFromLine(row, line)
		partNumbers = append(partNumbers, lineNumbers...)
	}

	return partNumbers
}

var CommandA = &cobra.Command{
	Use:  "03a",
	Args: cobra.ExactArgs(1),
	RunE: func(cmd *cobra.Command, args []string) error {
		s, err := parseInput(args[0])
		if err != nil {
			return err
		}

		partNumbers := s.getPartNumbers()

		sum := 0
		for _, partNumber := range partNumbers {
			if s.isValidPartNumber(partNumber) {
				sum += partNumber.value
			}
		}

		fmt.Printf("%v\n", sum)

		return nil
	},
}
    part 1 discussion

    I had an annoying bug where I wasn't including a part number that happened to occur at the very end of a line of input, because my getPartNumbersFromLine function only registered it when it found the first character after the number. I solved this by pretending there's a . character at the end of every line.

    part 2

    I modified my isValidPartNumber function to return the character that's adjacent to the part, as well as its position:

    --- day03/day03a.go      2023-12-02 23:25:12.827319289 -0800
+++ day03/day03b.go      2023-12-02 23:13:23.613715480 -0800
@@ -41,7 +41,7 @@
        return s, nil
 }

-func (s Schematic) isValidPartNumber(pn PartNumber) bool {
+func (s Schematic) isValidPartNumber(pn PartNumber) (bool, byte, Position) {
        var candidates []Position

        for col := pn.startCol - 1; col <= pn.endCol + 1; col++ {
@@ -61,17 +61,18 @@
                        continue
                }

-               switch s[candidate.row][candidate.col] {
+               char := s[candidate.row][candidate.col]
+               switch char {
                case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
                        continue
                case '.':
                        continue
                default:
-                       return true
+                       return true, char, candidate
                }
        }

-       return false
+       return false, '.', Position{}

 func (s Schematic) getPartNumbersFromLine(row int, line []byte) []PartNumber {
@@ -138,7 +139,8 @@

                sum := 0
                for _, partNumber := range partNumbers {
-                       if s.isValidPartNumber(partNumber) {
+                       isValid, _, _ := s.isValidPartNumber(partNumber)
+                       if isValid {
                                sum += partNumber.value
                        }
                }

    and from there it was easy to build up a map of gear positions to adjacent parts:

    var CommandB = &cobra.Command{
	Use:  "03b",
	Args: cobra.ExactArgs(1),
	RunE: func(cmd *cobra.Command, args []string) error {
		s, err := parseInput(args[0])
		if err != nil {
			return err
		}

		partNumbers := s.getPartNumbers()

		matchingParts := make(map[Position][]PartNumber)

		for _, partNumber := range partNumbers {
			_, char, position := s.isValidPartNumber(partNumber)
			if char == '*' {
				matchingParts[position] = append(matchingParts[position], partNumber)
			}
		}

		sum := 0

		for _, parts := range matchingParts {
			if len(parts) == 2 {
				gearRatio := parts[0].value * parts[1].value
				sum += gearRatio
			}
		}

		fmt.Printf("%v\n", sum)

		return nil
	},
}
    1 vote
  12. Crestwave
    Link
    Longer day 3 than expected; might be because it's a weekend. Part 2 was pretty simple, at least. Part 1 POSIX AWK doesn't seem to have a way to handle multiple matches so I had to manually...

    Longer day 3 than expected; might be because it's a weekend. Part 2 was pretty simple, at least.

    Part 1

    POSIX AWK doesn't seem to have a way to handle multiple matches so I had to manually implement it. Overall went pretty smoothly other than a couple off-by-one errors.

    #!/usr/bin/awk -f
{
	str = $0
	len = 0
	while (length(str) > 0) {
		i = match(str, /[0-9]+/)
		if (i == 0)
			break
		grid[i + len, NR] = substr(str, i, RLENGTH)
		len += i + RLENGTH - 1
		str = substr(str, i + RLENGTH)
	}

	str = $0
	len = 0
	while (length(str) > 0) {
		i = match(str, /[^0-9.]/)
		if (i == 0)
			break
		sym[i + len, NR] = substr(str, i, 1)
		len += i + RLENGTH - 1
		str = substr(str, i + RLENGTH)
	}
}

END {
	for (k in grid) {
		split(k, xy, SUBSEP)
		for (x = xy[1] - 1; x <= xy[1] + length(grid[k]); ++x)
			for (y = xy[2] - 1; y <= xy[2] + 1; ++y)
				if (sym[x, y])
					total += grid[k]
	}

	print(total)
}
    Part 2

    Very minor changes. The instructions specified "adjacent to exactly two part numbers", but I didn't have any that were more than two in my input so ¯\_(ツ)_/¯

    #!/usr/bin/awk -f
{
	str = $0
	len = 0
	while (length(str) > 0) {
		i = match(str, /[0-9]+/)
		if (i == 0)
			break
		grid[i + len, NR] = substr(str, i, RLENGTH)
		len += i + RLENGTH - 1
		str = substr(str, i + RLENGTH)
	}

	str = $0
	len = 0
	while (length(str) > 0) {
		i = match(str, /[^0-9.]/)
		if (i == 0)
			break
		sym[i + len, NR] = substr(str, i, 1)
		len += i + RLENGTH - 1
		str = substr(str, i + RLENGTH)
	}
}

END {
	for (k in grid) {
		split(k, xy, SUBSEP)
		for (x = xy[1] - 1; x <= xy[1] + length(grid[k]); ++x)
			for (y = xy[2] - 1; y <= xy[2] + 1; ++y)
				if (sym[x, y] == "*")
					if (gear[x, y])
						total += gear[x, y] * grid[k]
					else
						gear[x, y] = grid[k]
	}

	print(total)
}
    1 vote
  13. guissmo
    Link
    Hoping for more problems beyond parsing! But at least I got to use some functions that I haven't used in a while. Posted my solution and explanation here:...

    Hoping for more problems beyond parsing! But at least I got to use some functions that I haven't used in a while. Posted my solution and explanation here: https://guissmo.com/blog/advent-of-code-2023-day-3/

    Here's the complete code:

    Parts 1 and 2 
    import re

def padded_grid(inp):
    pad = '.'*(len(inp[0])+2)
    mid = [f'.{i}.' for i in inp]
    return([pad] + mid + [pad])

class Symbol():
    
    def __init__(self, num, i, j):
        self.value = num
        self.i = i
        self.j = j
        
    def __str__(self):
        return f'symbol {self.value} at row {self.i} and column {self.j}'
    
    def __eq__(self, other):
        return self.value == other.value and self.i == other.i and self.j == other.j

class Number():
    
    def __init__(self, num, i, j0, j1):
        self.value = int(num)
        self.i = i
        self.j0 = j0
        self.j1 = j1
        
    def __str__(self):
        return f'number {self.value} at row {self.i} spanning columns {self.j0} to {self.j1}'

class Grid():
    
    def __init__(self, inp):
        self.grid = padded_grid(inp)
        self.numbers = self.detect_numbers()
        self.symbols = self.detect_symbols()
        self.asterisks = self.detect_asterisks()
    
    def __str__(self):
        ret = ""
        for l in self.grid:
            ret += l
            ret += '\n'
        return ret
    
    def detect_numbers(self):
        ret = []
        for i,l in enumerate(self.grid):
            for m in re.finditer(r'[0-9]+', l):
                (j0, j1) = m.span()
                ret.append(Number(m[0], i, j0, j1-1))
        return ret
    
    def detect_symbols(self):
        ret = []
        for i,l in enumerate(self.grid):
            for m in re.finditer(r'[^0-9\.]', l):
                (j0, j1) = m.span()
                ret.append(Symbol(m[0], i, j0))
        return ret
    
    def detect_asterisks(self):
        ret = []
        for i,l in enumerate(self.grid):
            for m in re.finditer(r'[\*]', l):
                (j0, j1) = m.span()
                ret.append(Symbol(m[0], i, j0))
        return ret
    
    def detect_adjacent_symbols(self, num):
        ret = []
        for s in self.symbols:
            if num.i-1 <= s.i and s.i <= num.i+1 and num.j0-1 <= s.j and s.j <= num.j1+1:
                ret.append(s)
        return ret
    
    def sum_of_part_numbers(self):
        ret = 0
        for n in self.numbers:
            if len(self.detect_adjacent_symbols(n)) > 0:
                ret += n.value
        return ret
    
    def find_gear_ratio(self):
        dic = {}
        for n in self.numbers:
            adjacent_symbols = self.detect_adjacent_symbols(n)
            for s in adjacent_symbols:
                if s.value != '*':
                    continue
                k = (s.i, s.j)
                if k not in dic:
                    dic[k] = []
                dic[k].append(n)
                
        ret = 0
        for k in dic:
            l = dic[k]
            if len(l) == 2:
                ret += l[0].value*l[1].value
        return ret

    Then it was a matter of doing

    grid = Grid(my_input)
print(grid.sum_of_part_numbers())
print(grid.find_gear_ratio())
    1 vote
  14. wycy
    Link
    Rust Highly involved for a day 3. I hope it's just the early problems that have had their complexity increased to combat LLMs. If the whole challenge has had its complexity scaled up this much,...

    Rust

    Highly involved for a day 3. I hope it's just the early problems that have had their complexity increased to combat LLMs. If the whole challenge has had its complexity scaled up this much, it's going to be really hard by day 10.

    Day 3 
    use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::HashMap;

use point2d::point2d::Point2D;

fn neighbors(start: &Point2D, end: &Point2D) -> Vec<Point2D> {
    let mut neighbors = Vec::new();
    neighbors.push(Point2D {x: start.x - 1, y: start.y    }); // start:left
    neighbors.push(Point2D {x: start.x - 1, y: start.y - 1}); // start:left-up
    neighbors.push(Point2D {x: start.x - 1, y: start.y + 1}); // start:left-down
    neighbors.push(Point2D {x: end.x   + 1, y: end.y      }); // end:right
    neighbors.push(Point2D {x: end.x   + 1, y: end.y   - 1}); // end:right-up
    neighbors.push(Point2D {x: end.x   + 1, y: end.y   + 1}); // end:right-down
    for x in start.x..=end.x {
        neighbors.push(Point2D {x: x      , y: start.y - 1}); // up
        neighbors.push(Point2D {x: x      , y: start.y + 1}); // down
    }
    neighbors
}

fn is_number(ch: char) -> bool {
    match ch {
        '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' => true,
        _ => false,
    }
}

fn is_symbol(ch: char) -> bool {
    if is_number(ch) { return false }
    if ch == '.'     { return false }
    true
}

fn is_gear_symbol(ch: char) -> bool {
    if ch == '*' { return true }
    false
}

// Returns the actual number from a vec of numeric characters
fn number_from_digits(digits: Vec<char>) -> i64 {
    digits
        .iter()
        .rev()
        .enumerate()
        .map(|(i,digit)| digit.to_digit(10).unwrap() as i64 * i64::pow(10,i.try_into().unwrap()))
        .sum()
}

// Verifies that a given part number is valid based on adjacency to any symbol
fn is_valid_part_number(start: &Point2D, end: &Point2D, map: &HashMap<Point2D,char>) -> bool {
    for n in neighbors(&start, &end) {
        match map.get(&n) {
            Some(ch) => if is_symbol(*ch) { return true },
            None => {},
        }
    }
    false
}

// Returns all gear symbol Point2D adjacent to a number
fn adjacent_gears(start: &Point2D, end: &Point2D, map: &HashMap<Point2D,char>) -> Vec<Point2D> {
    let mut gears: Vec<Point2D> = Vec::new();
    for n in neighbors(&start, &end) {
        match map.get(&n) {
            Some(ch) => if is_gear_symbol(*ch) { gears.push(n) },
            None => {},
        }
    }
    gears
}

// Extracts the current number and returns the end point thereof
fn extract_number(start: &Point2D, map: &HashMap<Point2D,char>) -> (i64, Point2D) {
    let mut digits: Vec<char> = Vec::new();
    let mut end_pt = Point2D { x: start.x, y: start.y };
    'find_lp: loop {
        match map.get(&end_pt) {
            Some(ch) => {
                if is_number(*ch) { digits.push(*ch); }
                else { break 'find_lp }
            },
            None => break 'find_lp,
        }
        end_pt.x += 1;
    }
    end_pt.x -= 1;
    (number_from_digits(digits),end_pt)
}

fn solve(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // Input
    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {err}"),
        Ok(result) => result,
    };

    // Build map
    let mut part_numbers: HashMap<Point2D,char> = HashMap::new();
    for (y,line) in input.iter().enumerate() {
        for (x,ch) in line.chars().enumerate() {
            let pt = Point2D { x: x as i64, y: y as i64 };
            part_numbers.insert(pt, ch);
        }
    }
    let xmax = &part_numbers.keys().map(|&pt| pt.x).max().unwrap();
    let ymax = &part_numbers.keys().map(|&pt| pt.y).max().unwrap();

    // Solve
    let mut part1: i64 = 0;
    let mut potential_gears: HashMap<Point2D,Vec<i64>> = HashMap::new();
    for y in 0..=*ymax {
        let mut pt = Point2D { x: 0, y: y };
        loop {
            let ch = part_numbers.get(&pt).unwrap();
            if is_number(*ch) {
                let (num,end) = extract_number(&pt, &part_numbers);
                // Part 1
                if is_valid_part_number(&pt, &end, &part_numbers) {
                    part1 += num;
                }
                // Part 2
                for gear in adjacent_gears(&pt, &end, &part_numbers) {
                    if potential_gears.contains_key(&gear) {
                        potential_gears.get_mut(&gear).unwrap().push(num);
                    } else {
                        potential_gears.insert(gear,vec![num]);
                    }
                }
                pt.x = end.x + 1;
            } else {
                pt.x += 1;
            }
            if pt.x >= *xmax { break }
        }
    }
    println!("Part 1: {part1}"); // 525119

    // Part 2
    let part2: i64 = potential_gears
        .iter()
        .filter(|(_,v)| v.len() == 2)
        .map(|(_,v)| v.iter().product::<i64>())
        .sum();
    println!("Part 2: {part2}"); // 76504829

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}
    1 vote
  15. infinitesimal
    Link
    Just wondering, do people ever use fancy spatial data structures for these 2D (or eventually 3D) AoC grid problems instead of just nested loops? Kotlin object Day3 { data class Number(val i: Int,...

    Just wondering, do people ever use fancy spatial data structures for these 2D (or eventually 3D) AoC grid problems instead of just nested loops?

    Kotlin 
    object Day3 {
    data class Number(val i: Int, val row: Int, val col: IntRange)
    data class Symbol(val c: Char, val row: Int, val col: Int)
    data class Schematic(val nums: List<Number>, val syms: List<Symbol>)

    private fun parse(lines: List<String>) = lines.mapIndexed { row, line ->
        val nums = Regex("""\d+""").findAll(line).map { Number(it.value.toInt(), row, it.range) }
        val syms = Regex("""[^\d.]""").findAll(line).map { Symbol(it.value.first(), row, it.range.first) }
        Schematic(nums.toList(), syms.toList())
    }.reduce { prev, next -> Schematic(prev.nums + next.nums, prev.syms + next.syms) }

    private fun isAdjacent(num: Number, sym: Symbol) = let {
        val vert = (num.row - 1)..(num.row + 1)
        val horz = num.col + (num.col.first - 1) + (num.col.last + 1)
        val neighborhood = vert.flatMap { row -> horz.map { col -> Pair(row, col) } }
        Pair(sym.row, sym.col) in neighborhood
    }

    fun part1(lines: List<String>) = let {
        val (nums, syms) = parse(lines)
        nums.filter { num -> syms.any { sym -> isAdjacent(num, sym) } }.sumOf { num -> num.i }
    }

    fun part2(lines: List<String>) = let {
        val (nums, syms) = parse(lines)
        syms.filter { it.c == '*' }.sumOf { sym ->
            val neighbors = nums.filter { num -> isAdjacent(num, sym) }.toList()
            if (neighbors.size == 2) neighbors[0].i * neighbors[1].i else 0
        }
    }
}
    1 vote
  16. Macil
    Link
    Using Typescript and Deno together still. I flipped my approach to solving this a few times. Originally I decided I would process the text character-by-character to look for symbols, and then also...

    Using Typescript and Deno together still. I flipped my approach to solving this a few times. Originally I decided I would process the text character-by-character to look for symbols, and then also do that to look for numbers, but then I would have to do some annoying book-keeping to remember where I encountered each of a number's digits. I realized it would be much easier if I used a regex to recognize strings of multiple digits together, and then searched for symbols around it. I also used regexes to search for the symbols. I would use the slice() method on the strings of the surrounding rows to make a substring of only the positions neighboring the number, and then use a regex to search those for symbols.

    For part 2, I did a similar search, but I would only look for "*" symbols neighboring the numbers, and I kept track of the locations of all "*" symbols and the numbers that neighbored them in a Map object. Then I iterated through the map looking at all locations which had exactly two numbers as neighbors.

    Typescript 
    import { assertEquals } from "https://deno.land/std@0.208.0/assert/mod.ts";
import { runPart } from "https://deno.land/x/aocd@v1.5.1/mod.ts";

class Coordinate {
  row: number;
  column: number;

  constructor(row: number, column: number) {
    this.row = row;
    this.column = column;
  }

  toString() {
    return `${this.row},${this.column}`;
  }

  static fromString(str: string): Coordinate {
    const [row, column] = str.split(",").map(Number);
    return new Coordinate(row, column);
  }
}

function parse(input: string): string[] {
  return input.trimEnd().split("\n");
}

function* getNumberSymbolNeighbors(
  lines: string[],
  numberCoordinate: Coordinate,
  numberLength: number,
  symbolRegex = /[^0-9.]/g,
): Generator<Coordinate> {
  for (
    let row = numberCoordinate.row - 1;
    row <= numberCoordinate.row + 1;
    row++
  ) {
    const line = lines[row];
    if (!line) {
      continue;
    }
    const searchPartStart = Math.max(0, numberCoordinate.column - 1);
    const searchPart = line.slice(
      searchPartStart,
      numberCoordinate.column + numberLength + 1,
    );
    for (const symbolMatch of searchPart.matchAll(symbolRegex)) {
      yield new Coordinate(row, searchPartStart + symbolMatch.index!);
    }
  }
}

function numberHasSymbolNeighbors(
  lines: string[],
  numberCoordinate: Coordinate,
  numberLength: number,
  symbolRegex?: RegExp,
): boolean {
  for (
    const _value of getNumberSymbolNeighbors(
      lines,
      numberCoordinate,
      numberLength,
      symbolRegex,
    )
  ) {
    // Just return true as soon as we've found one, don't need to keep looking.
    return true;
  }
  return false;
}

function part1(input: string): number {
  const lines = parse(input);
  const partNumbers: number[] = [];
  lines.forEach((line, row) => {
    for (const numberMatch of line.matchAll(/[0-9]+/g)) {
      const numberCoordinate = new Coordinate(row, numberMatch.index!);
      if (
        numberHasSymbolNeighbors(lines, numberCoordinate, numberMatch[0].length)
      ) {
        partNumbers.push(Number(numberMatch[0]));
      }
    }
  });
  return partNumbers.reduce((a, b) => a + b, 0);
}

function part2(input: string): number {
  const lines = parse(input);
  // keys are stringified coordinates
  const gearCoordsToNumbers = new Map<string, number[]>();
  lines.forEach((line, row) => {
    for (const numberMatch of line.matchAll(/[0-9]+/g)) {
      const numberCoordinate = new Coordinate(row, numberMatch.index!);
      for (
        const gearCoordinate of getNumberSymbolNeighbors(
          lines,
          numberCoordinate,
          numberMatch[0].length,
          /\*/g,
        )
      ) {
        const gearCoordinateString = gearCoordinate.toString();
        let gearNumbers = gearCoordsToNumbers.get(gearCoordinateString);
        if (!gearNumbers) {
          gearNumbers = [];
          gearCoordsToNumbers.set(gearCoordinateString, gearNumbers);
        }
        gearNumbers.push(Number(numberMatch[0]));
      }
    }
  });
  return Array.from(gearCoordsToNumbers.values())
    .filter((gearNumbers) => gearNumbers.length === 2)
    .map(([a, b]) => a * b)
    .reduce((a, b) => a + b, 0);
}

if (import.meta.main) {
  runPart(2023, 3, 1, part1);
  runPart(2023, 3, 2, part2);
}

const TEST_INPUT = `\
467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..
`;

Deno.test("part1", () => {
  assertEquals(part1(TEST_INPUT), 4361);
});

Deno.test("part2", () => {
  assertEquals(part2(TEST_INPUT), 467835);
});
    1 vote