Day 3: Gear Ratios
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ or pastebin (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
🔒This post will be unlocked when there is a decent amount of submissions on the leaderboard to avoid cheating for top spots
🔓 Edit: Post has been unlocked after 11 minutes
I like it, it’s simple and to the point. I’ve learned that one of the most helpful things to do when solving these puzzles is to not make it more complicated than it needs to be, and you certainly succeeded better at that today than I did.
My solution for day 1 part 1 was simple and to the point. The other ones are getting increasingly less so. You’re right that sometimes it’s best not to get too fancy, but I think soon I may have to break out such advanced programming techniques as “functions” and maybe “objects”, instead of writing increasingly convoluted piles of nested loops. xD
Hi there! Looks like you linked to a Lemmy community using a URL instead of its name, which doesn’t work well for people on different instances. Try fixing it like this: !nim@programming.dev
nested loops
This is the way
That was not fun to solve. Lots of ugly code. This is a less ugly second version. Language: Nim.
Rust
I’ve been using Regexes for every day so far, this time it helped in finding numbers along with their start and end position in a line. For the second part I mostly went with the approach of part 1 which was to look at all numbers and then figure out if it has a part symbol around it. Only in part 2 I saved all numbers next to a gear
*
in a hash table that maps each gear position to a list of adjacent numbers. Then in the end I can just look at all gears with exactly 2 numbers attached.Also it has to be said, multiplying two numbers is the exact opposite of getting their ratio!
I wrote today’s program in Python. (I am going to do a different language each day.) The only thing that gave me a little trouble was I was counting “\n” as a part label. Once I realized that I was able to get both problems done very quickly.
My code for the two parts is on github:-
deleted by creator
just more parsing problems
Language: C#
I aimed at keeping it as simple and short as reasonably possible this time, no overbuilding here!
I even used a goto to let me break out of multiple loops at once 🤮 (I had to look up how they worked!) I would totally fail me in a code review!
One solution for both
internal class Day3 : IRunnable { public void Run() { var input = File.ReadAllLines("Days/Three/Day3Input.txt"); int sum = 0; string numStr = ""; var starMap = new Dictionary<(int,int),List>(); for (int i = 0; i < input.Length; i++) for (int j = 0; j < input[i].Length; j++) { if (char.IsDigit(input[i][j])) numStr += input[i][j]; if (numStr.Length > 0 && (j == input[i].Length - 1 || !char.IsDigit(input[i][j + 1]))) { for (int k = Math.Max(0, i - 1); k < Math.Min(i + 2, input.Length); k++) for (int l = Math.Max(0, j - numStr.Length); l < Math.Min(j + 2, input[i].Length); l++) if (!char.IsDigit(input[k][l]) && input[k][l] != '.') { sum += int.Parse(numStr); if (input[k][l] == '*') { if (starMap.ContainsKey((k, l))) starMap[(k, l)].Add(int.Parse(numStr)); else starMap.Add((k,l),new List { int.Parse(numStr) }); } goto endSymbSearch; } endSymbSearch: numStr = ""; } } Console.WriteLine("Result1:"+sum.ToString()); Console.WriteLine("Result2:" + starMap.Where(sm => sm.Value.Count == 2).Sum(sm => sm.Value[0] * sm.Value[1])); } }
Edit: Updated now with part 2.
Managed to have a crack at this a bit earlier today, I’ve only done Part 01 so far. I’ll update with Part 02 later.
I tackled this with the personal challenge of not loading the entire puzzle input into memory, which would have made this a bit easier.
Solution in Rust 🦀
use std::{ env, fs, io::{self, BufRead, BufReader, Read}, }; fn main() -> io::Result<()> { let args: Vec = env::args().collect(); let filename = &args[1]; let file1 = fs::File::open(filename)?; let file2 = fs::File::open(filename)?; let reader1 = BufReader::new(file1); let reader2 = BufReader::new(file2); println!("Part one: {}", process_part_one(reader1)); println!("Part two: {}", process_part_two(reader2)); Ok(()) } fn process_part_one(reader: BufReader) -> u32 { let mut lines = reader.lines().peekable(); let mut prev_line: Option = None; let mut sum = 0; while let Some(line) = lines.next() { let current_line = line.expect("line exists"); let next_line = match lines.peek() { Some(Ok(line)) => Some(line), Some(Err(_)) => None, None => None, }; match (prev_line, next_line) { (None, Some(next)) => { let lines = vec![¤t_line, next]; sum += parse_lines(lines, true); } (Some(prev), Some(next)) => { let lines = vec![&prev, ¤t_line, next]; sum += parse_lines(lines, false); } (Some(prev), None) => { let lines = vec![&prev, ¤t_line]; sum += parse_lines(lines, false); } (None, None) => {} } prev_line = Some(current_line); } sum } fn process_part_two(reader: BufReader) -> u32 { let mut lines = reader.lines().peekable(); let mut prev_line: Option = None; let mut sum = 0; while let Some(line) = lines.next() { let current_line = line.expect("line exists"); let next_line = match lines.peek() { Some(Ok(line)) => Some(line), Some(Err(_)) => None, None => None, }; match (prev_line, next_line) { (None, Some(next)) => { let lines = vec![¤t_line, next]; sum += parse_lines_for_gears(lines, true); } (Some(prev), Some(next)) => { let lines = vec![&prev, ¤t_line, next]; sum += parse_lines_for_gears(lines, false); } (Some(prev), None) => { let lines = vec![&prev, ¤t_line]; sum += parse_lines_for_gears(lines, false); } (None, None) => {} } prev_line = Some(current_line); } sum } fn parse_lines(lines: Vec<&String>, first_line: bool) -> u32 { let mut sum = 0; let mut num = 0; let mut valid = false; let mut char_vec: Vec> = Vec::new(); for line in lines { char_vec.push(line.chars().collect()); } let chars = match first_line { true => &char_vec[0], false => &char_vec[1], }; for i in 0..chars.len() { if chars[i].is_digit(10) { // Add the digit to the number num = num * 10 + chars[i].to_digit(10).expect("is digit"); // Check the surrounding character for non-period symbols for &x in &[-1, 0, 1] { for chars in &char_vec { if (i as isize + x).is_positive() && ((i as isize + x) as usize) < chars.len() { let index = (i as isize + x) as usize; if !chars[index].is_digit(10) && chars[index] != '.' { valid = true; } } } } } else { if valid { sum += num; } valid = false; num = 0; } } if valid { sum += num; } sum } fn parse_lines_for_gears(lines: Vec<&String>, first_line: bool) -> u32 { let mut sum = 0; let mut char_vec: Vec> = Vec::new(); for line in &lines { char_vec.push(line.chars().collect()); } let chars = match first_line { true => &char_vec[0], false => &char_vec[1], }; for i in 0..chars.len() { if chars[i] == '*' { let surrounding_nums = get_surrounding_numbers(&lines, i); let product = match surrounding_nums.len() { 0 | 1 => 0, _ => surrounding_nums.iter().product(), }; sum += product; } } sum } fn get_surrounding_numbers(lines: &Vec<&String>, gear_pos: usize) -> Vec { let mut nums: Vec = Vec::new(); let mut num: u32 = 0; let mut valid = false; for line in lines { for (i, char) in line.chars().enumerate() { if char.is_digit(10) { num = num * 10 + char.to_digit(10).expect("is digit"); if [gear_pos - 1, gear_pos, gear_pos + 1].contains(&i) { valid = true; } } else if num > 0 && valid { nums.push(num); num = 0; valid = false; } else { num = 0; valid = false; } } if num > 0 && valid { nums.push(num); } num = 0; valid = false; } nums } #[cfg(test)] mod tests { use super::*; const INPUT: &str = "467..114.. ...*...... ..35..633. ......#... 617*...... .....+.58. ..592..... ......755. ...$.*.... .664.598.."; #[test] fn test_process_part_one() { let input_bytes = INPUT.as_bytes(); assert_eq!(4361, process_part_one(BufReader::new(input_bytes))); } #[test] fn test_process_part_two() { let input_bytes = INPUT.as_bytes(); assert_eq!(467835, process_part_two(BufReader::new(input_bytes))); } }
Python
Questions and comments welcome!
import collections import re from .solver import Solver class Day03(Solver): def __init__(self): super().__init__(3) self.lines = [] def presolve(self, input: str): self.lines = input.rstrip().split('\n') def solve_first_star(self): adjacent_to_symbols = set() for i, line in enumerate(self.lines): for j, sym in enumerate(line): if sym in ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.'): continue for di in (-1, 0, 1): for dj in (-1, 0, 1): adjacent_to_symbols.add((i + di, j + dj)) numbers = [] for i, line in enumerate(self. lines): for number_match in re.finditer(r'\d+', line): is_adjacent_to_symbol = False for j in range(number_match.start(), number_match.end()): if (i, j) in adjacent_to_symbols: is_adjacent_to_symbol = True if is_adjacent_to_symbol: numbers.append(int(number_match.group())) return sum(numbers) def solve_second_star(self): gear_numbers = collections.defaultdict(list) adjacent_to_gears = {} for i, line in enumerate(self.lines): for j, sym in enumerate(line): if sym == '*': for di in (-1, 0, 1): for dj in (-1, 0, 1): adjacent_to_gears[(i + di, j + dj)] = (i, j) for i, line in enumerate(self. lines): for number_match in re.finditer(r'\d+', line): adjacent_to_gear = None for j in range(number_match.start(), number_match.end()): if (i, j) in adjacent_to_gears: adjacent_to_gear = adjacent_to_gears[(i, j)] if adjacent_to_gear: gear_numbers[adjacent_to_gear].append(int(number_match.group())) ratios = [] for gear_numbers in gear_numbers.values(): match gear_numbers: case [a, b]: ratios.append(a * b) return sum(ratios)
Crystal
My computer crashed right most of the way through and I lost everything, so this was even more frustrating than it should have been
Also damn, lemmy’s tabs are massivewill post part 2 when I get to it
input = File.read("input.txt") lines = input.lines.map(&.chars) sum = 0 num_marker = nil lines.each_with_index do |line, y| line.each_with_index do |char, x| num_marker ||= x if char.number? if (!char.number? || x == line.size-1) && num_marker if check_symbol(y, (num_marker-1)..x, lines) sum += lines[y][(char.number? ? num_marker..x : num_marker...x)].join.to_i end num_marker = nil end end end puts sum def check_symbol(y, rx, lines) carr = [ lines[y][rx.begin]?, lines[y][rx.end]? ] carr += rx.map {|x| lines[y-1][x]? } if y > 0 carr += rx.map {|x| lines[y+1][x]? } if y < lines.size-1 carr.each {|c| return true if c && c != '.' && !c.number?} false end
Language: C
Part 2 stumped me for a little bit, it wasn’t an obvious extension of part 1. Part 1 was about numbers (with one or more …) while part 2 worked from the symbols (with exactly two …). Going the other way would require more bookkeeping to avoid double counting.
And for the implementation: if you loop over the grid and check surrounding cells for digits you’d have to account for a bunch of cases, e.g. NW/N or N/NE being part of the same number or NW and NE being part of separate numbers. And you’d have to parse the numbers again. But building a graph or reference list of some sort is both unergonomic with C and not necessarily any simpler.
I ended up just writing out the cases, and honestly it didn’t turn out too bad.
Abridged code
int main(int argc, char **argv) { static char G[GSZ][GSZ]; static int N[GSZ][GSZ]; int p1=0,p2=0, h=0, x,y, dx,dy, n=0,sym=0,r; for (h=0; fgets(&G[h+1][1], GSZ-1, stdin); h++) assert(h < GSZ); /* * Pass 1: parse numbers and solve part 1. For every digit in * G, the full number it is part of is stored in N. */ for (y=1; y<=h; y++) for (x=1; G[y][x]; x++) if (isdigit(G[y][x])) { n = n*10 + G[y][x]-'0'; for (dy=-1; dy<2; dy++) for (dx=-1; dx<2; dx++) sym = sym || (x && y && G[y+dy][x+dx] != '.' && ispunct(G[y+dy][x+dx])); } else { for (dx=-1; isdigit(G[y][x+dx]); dx--) N[y][x+dx] = n; if (sym) p1 += n; n = sym = 0; } /* * Pass 2: solve part 2 by finding all '*', then counting and * multiplying adjecent numbers. * * Horizontal adjecency is trivial but vertical/diagonal has * two situations: if there's a digit directly North of the '+', * it must be a single number: NW and NE would connect to it. * If N isn't a digit, digits in NW and NE belong to separate * numbers. */ for (y=1; y<=h; y++) for (x=1; G[y][x]; x++) { if (G[y][x] != '*') continue; n = 0; r = 1; if (N[y][x-1]) { n++; r *= N[y][x-1]; } if (N[y][x+1]) { n++; r *= N[y][x+1]; } if (N[y-1][x]) { n++; r *= N[y-1][x]; } else { if (N[y-1][x-1]) { n++; r *= N[y-1][x-1]; } if (N[y-1][x+1]) { n++; r *= N[y-1][x+1]; } } if (N[y+1][x]) { n++; r *= N[y+1][x]; } else { if (N[y+1][x-1]) { n++; r *= N[y+1][x-1]; } if (N[y+1][x+1]) { n++; r *= N[y+1][x+1]; } } if (n == 2) p2 += r; } printf("%d %d\n", p1, p2); return 0; }
Language: C++
Efficiency? Elegant Code? Nope but It works. Luckily I did part 1 by looking at the symbols first anyway, so extending to part two was trivial. Also originally had a bug where I treated all symbols as cogs, not only ‘*’. Interestingly it worked anyway as only '*'s had two adjacent numbers in my data. It is fixed in this version. Hacked together combined code (originally I did each part as separate programs but they shared so much that I ended up combining then so the post is shorter): https://pastebin.com/Dij2XSYe
Edit: anything in angle brackets is not displaying even with backslashes, idk why but i have moved the code to a pastebin.
Python, used a number map to search positions near symbols.
https://github.com/massahud/advent-of-code-2023/blob/main/day03/day03.ipynb
[LANGUAGE: C#]
I kept trying to create clever solutions, but ended up falling back on regex when it was taking to long. THE TLDR is we scan the list of strings for a symbol, then parse the three lines above, below and inline with the symbol for digits. Then we try and match the indexes of the match and the area around the symbol. Part 2 was a small modification, and was mostly about getting the existing code to conform the data into a pattern for each of the three lines.
Part 1
static char[] Symbols = { '@', '#', '$', '%', '&', '*', '/', '+', '-', '=' }; string pattern = @"\d+"; static List? list; list = new List((await File.ReadAllLinesAsync(@".\Day 3\PuzzleInput.txt"))); int count = 0; for (int row = 0; row < list.Count; row++) { for (int col = 0; col < list[row].Length; col++) { var c = list[row][col]; if (c == '.') { continue; } if (Symbols.Contains(c)) { var res = Calculate(list[row - 1], col); res += Calculate(list[row], col); res += Calculate(list[row + 1], col); count += res; } } } Console.WriteLine(count); private static int Calculate(string line, int col) { List indexesToCheck = new List { col - 1, col, col + 1 }; int count = 0; MatchCollection matches = Regex.Matches(line, pattern); foreach (Match match in matches) { string number = match.Value; if (AnyIndexInList(indexesToCheck, match.Index, match.Length)) { count += Int32.Parse(number); } } return count; } static bool AnyIndexInList(List list, int startIndex, int length) { for (int i = startIndex; i < startIndex + length; i++) { if (list.Contains(i)) { return true; } } return false; }
Part 2:
list = new List((await File.ReadAllLinesAsync(@".\Day 3\PuzzleInput.txt"))); int count = 0; for (int row = 0; row < list.Count; row++) { for (int col = 0; col < list[row].Length; col++) { var c = list[row][col]; if (c == '.') continue; if (c == '*') { var res1 = Calculate2(list[row - 1], col); var res2 = Calculate2(list[row], col); var res3 = Calculate2(list[row + 1], col); count += (res1, res2, res3) switch { {res1: not null, res2: null, res3: null } when res1[1] != null => res1[0].Value * res1[1].Value, {res1: null, res2: not null, res3: null } when res2[1] != null => res2[0].Value * res2[1].Value, {res1: null, res2: null, res3: not null } when res3[1] != null => res3[0].Value * res3[1].Value, {res1: not null, res2: not null, res3: null } => res1[0].Value * res2[0].Value, {res1: not null, res2: null, res3: not null } => res1[0].Value * res3[0].Value, {res1: null, res2: not null, res3: not null } => res2[0].Value * res3[0].Value, {res1: not null, res2: not null, res3: not null } => res1[0].Value * res2[0].Value * res3[0].Value, _ => 0 } ; } } } Console.WriteLine(count); private static int?[]? Calculate2(string line, int col) { List indexesToCheck = new List { col - 1, col, col + 1 }; int?[]? count = null; MatchCollection matches = Regex.Matches(line, pattern); foreach (Match match in matches) { string number = match.Value; if (AnyIndexInList(indexesToCheck, match.Index, match.Length)) { if (count == null) count = new int?[2] { Int32.Parse(number), null }; else { count[1] = Int32.Parse(number); }; } } return count; }
Dart Solution
Holy moley, if this year is intended to be impervious to AI solution, it’s also working pretty well as a filter to this paltry Human Intelligence.
Find interesting symbols, look around for digits, and expand these into numbers. A dirty hacky solution leaning on a re-used Grid class. Not recommended.
late ListGrid grid; Index look(Index ix, Index dir) { var here = ix; var next = here + dir; while (grid.isInBounds(next) && '1234567890'.contains(grid.at(next))) { here = next; next = here + dir; } return here; } /// Return start and end indices of a number at a point. (Index, Index) expandNumber(Index ix) => (look(ix, Grid.dirs['L']!), look(ix, Grid.dirs['R']!)); int parseNumber((Index, Index) e) => int.parse([ for (var i = e.$1; i != e.$2 + Grid.dirs['R']!; i += Grid.dirs['R']!) grid.at(i) ].join()); /// Return de-duplicated positions of all numbers near the given symbols. nearSymbols(Set syms) => [ for (var ix in grid.indexes.where((i) => syms.contains(grid.at(i)))) { for (var n in grid .near8(ix) .where((n) => ('1234567890'.contains(grid.at(n))))) expandNumber(n) }.toList() ]; part1(List lines) { grid = ListGrid([for (var e in lines) e.split('')]); var syms = lines .join('') .split('') .toSet() .difference('0123456789.'.split('').toSet()); // Find distinct number locations near symbols and sum them. return { for (var ns in nearSymbols(syms)) for (var n in ns) n }.map(parseNumber).sum; } part2(List lines) { grid = ListGrid([for (var e in lines) e.split('')]); // Look for _pairs_ of numbers near '*' and multiply them. var products = [ for (var ns in nearSymbols({'*'}).where((e) => e.length == 2)) ns.map(parseNumber).reduce((s, t) => s * t) ]; return products.sum; }
what language is this? I don’t recognize it
Sorry, it’s Dart. I’ll update it.