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/ , pastebin, or github (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)
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
🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard
Used Shoelace Algorithm to get the interior area and then Pick's Theorem to get the number of interior points based on the area and the points along the boundary loop.
It's so humbling when you've hammered out a solution and then realise you've been paddling around in waters that have already been mapped out by earlier explorers!
from .solver import Solver
_EXITS_MAP = {
'|': ((0, -1), (0, 1)),
'-': ((-1, 0), (1, 0)),
'L': ((1, 0), (0, -1)),
'J': ((-1, 0), (0, -1)),
'7': ((-1, 0), (0, 1)),
'F': ((1, 0), (0, 1)),
'.': (),
'S': (),
}
class Day10(Solver):
def __init__(self):
super().__init__(10)
self.maze: dict[tuple[int, int], str] = {}
self.start: tuple[int, int] = (0, 0)
self.dists: dict[tuple[int, int], int] = {}
def _pipe_has_exit(self, x: int, y: int, di: int, dj: int, inverse: bool = False) -> bool:
if inverse:
di, dj = -di, -dj
return (di, dj) in _EXITS_MAP[self.maze[(x, y)]]
def presolve(self, input: str):
self.maze: dict[tuple[int, int], str] = {}
self.start: tuple[int, int] = (0, 0)
for y, line in enumerate(input.rstrip().split('\n')):
for x, c in enumerate(line):
self.maze[(x, y)] = c
if c == 'S':
self.start = (x, y)
next_pos: list[tuple[int, int]] = []
directions_from_start = []
for di, dj in ((0, -1), (1, 0), (0, 1), (-1, 0)):
x, y = self.start[0] + di, self.start[1] + dj
if (x, y) not in self.maze:
continue
if not self._pipe_has_exit(x, y, di, dj, inverse=True):
continue
next_pos.append((x, y))
directions_from_start.append((di, dj))
self.maze[self.start] = [c for c, dmap in _EXITS_MAP.items()
if set(directions_from_start) == set(dmap)][0]
dists: dict[tuple[int, int], int] = {}
cur_dist = 0
while True:
cur_dist += 1
new_next_pos = []
for x, y in next_pos:
if (x, y) in dists:
continue
dists[(x, y)] = cur_dist
for di, dj in ((0, -1), (1, 0), (0, 1), (-1, 0)):
nx, ny = x + di, y + dj
if (nx, ny) not in self.maze:
continue
if not self._pipe_has_exit(x, y, di, dj):
continue
new_next_pos.append((nx, ny))
if not new_next_pos:
break
next_pos = new_next_pos
self.dists = dists
def solve_first_star(self) -> int:
return max(self.dists.values())
def solve_second_star(self) -> int:
area = 0
for y in range(max(y for _, y in self.dists.keys()) + 1):
internal = False
previous_wall = False
wall_start_symbol = None
for x in range(max(x for x, _ in self.dists.keys()) + 1):
is_wall = (x, y) == self.start or (x, y) in self.dists
wall_continues = is_wall
pipe_type = self.maze[(x, y)]
if is_wall and pipe_type == '|':
internal = not internal
wall_continues = False
elif is_wall and not previous_wall and pipe_type in 'FL':
wall_start_symbol = pipe_type
elif is_wall and not previous_wall:
raise RuntimeError(f'expecting wall F or L at {x}, {y}, got {pipe_type}')
elif is_wall and previous_wall and pipe_type == 'J':
wall_continues = False
if wall_start_symbol == 'F':
internal = not internal
elif is_wall and previous_wall and pipe_type == '7':
wall_continues = False
if wall_start_symbol == 'L':
internal = not internal
elif not is_wall and previous_wall:
raise RuntimeError(f'expecting wall J or 7 at {x}, {y}, got {pipe_type}')
if internal and not is_wall:
area += 1
previous_wall = wall_continues
return area
The squeezing component in part 2 made this really interesting.
I had a thought on a naïve solution consisting of expanding the input grid, painting all the walked pipes, and then doing a flood fill from the outside of the expanded map. There are a lot cleverer ways to do it, but the idea stuck with me and so...
The code's a bit of a mess, but I actually kind of like the result. It visualizes really well and still runs both parts in under 8 seconds, so it's not even particularly slow considering how it does it.
E.g;
Ruby
A snippet from the expansion/flood fill;
def flood_fill(used: [])
new_dim = @dim * 3
new_map = Array.new(new_dim.size, '.')
puts "Expanding #{@dim} to #{new_dim}, with #{used.size} visited pipes." if $args.verbose
# Mark all real points as inside on the expanded map
(0..(@dim.y - 1)).each do |y|
(0..(@dim.x - 1)).each do |x|
expanded_point = Point.new x * 3 + 1, y * 3 + 1
new_map[expanded_point.y * new_dim.x + expanded_point.x] = 'I'
end
end
# Paint all used pipes onto the expanded map
used.each do |used_p|
expanded_point = Point.new used_p.x * 3 + 1, used_p.y * 3 + 1
new_map[expanded_point.y * new_dim.x + expanded_point.x] = '#'
offsets = @links[used_p].connections
offsets.shift
offsets.each do |offs|
diff = offs - used_p
new_map[(expanded_point.y + diff.y) * new_dim.x + (expanded_point.x + diff.x)] = '#'
end
end
puts "Flooding expanded map..." if $args.verbose
# Flood fill the expanded map from the top-left corner
to_visit = [Point.new(0, 0)]
until to_visit.empty?
at = to_visit.shift
new_map[at.y * new_dim.x + at.x] = ' '
(-1..1).each do |off_y|
(-1..1).each do |off_x|
next if (off_x.zero? && off_y.zero?) || !(off_x.zero? || off_y.zero?)
off_p = at + Point.new(off_x, off_y)
next if off_p.x < 0 || off_p.y < 0 \
|| off_p.x >= new_dim.x || off_p.y >= new_dim.y \
|| to_visit.include?(off_p)
val = new_map[off_p.y * new_dim.x + off_p.x]
next unless %w[. I].include? val
to_visit << off_p
end
end
end
return new_map, new_dim
end
With the fully expanded map for the actual input it ends up working a 420x420 tile grid, and it has to do both value lookups as well as mutations into that, alongside inclusion testing for the search array (which could probably be made cheaper by building it as a set). It ends up somewhat expensive simply on the number of tests.
The sample I posted the picture of runs in 0.07s wall time though.
Finally got round to solving part 2. Very easy once I realised it's just a matter of counting line crossings.
Edit: having now read the other comments here, I'm reminded that the line-crossing logic is actually an application of Jordan's Curve Theorem which looks like a mathematical joke when you first see it, but turns out to be really useful here!
var up = Point(0, -1),
down = Point(0, 1),
left = Point(-1, 0),
right = Point(1, 0);
var pipes = >>{
'|': [up, down],
'-': [left, right],
'L': [up, right],
'J': [up, left],
'7': [left, down],
'F': [right, down],
};
late List> grid; // Make grid global for part 2
Set> buildPath(List lines) {
grid = lines.map((e) => e.split('')).toList();
var points = {
for (var row in grid.indices())
for (var col in grid.first.indices()) Point(col, row): grid[row][col]
};
// Find the starting point.
var pos = points.entries.firstWhere((e) => e.value == 'S').key;
var path = {pos};
// Replace 'S' with assumed pipe.
var dirs = [up, down, left, right].where((el) =>
points.keys.contains(pos + el) &&
pipes.containsKey(points[pos + el]) &&
pipes[points[pos + el]]!.contains(Point(-el.x, -el.y)));
grid[pos.y][pos.x] = pipes.entries
.firstWhere((e) =>
(e.value.first == dirs.first) && (e.value.last == dirs.last) ||
(e.value.first == dirs.last) && (e.value.last == dirs.first))
.key;
// Follow the path.
while (true) {
var nd = dirs.firstWhereOrNull((e) =>
points.containsKey(pos + e) &&
!path.contains(pos + e) &&
(points[pos + e] == 'S' || pipes.containsKey(points[pos + e])));
if (nd == null) break;
pos += nd;
path.add(pos);
dirs = pipes[points[pos]]!;
}
return path;
}
part1(List lines) => buildPath(lines).length ~/ 2;
part2(List lines) {
var path = buildPath(lines);
var count = 0;
for (var r in grid.indices()) {
var outside = true;
// We're only interested in how many times we have crossed the path
// to get to any given point, so mark anything that's not on the path
// as '*' for counting, and collapse all uninteresting path segments.
var row = grid[r]
.indexed()
.map((e) => path.contains(Point(e.index, r)) ? e.value : '*')
.join('')
.replaceAll('-', '')
.replaceAll('FJ', '|') // zigzag
.replaceAll('L7', '|') // other zigzag
.replaceAll('LJ', '') // U-bend
.replaceAll('F7', ''); // n-bend
for (var c in row.split('')) {
if (c == '|') {
outside = !outside;
} else {
if (!outside && c == '*') count += 1;
}
}
}
return count;
}
My solution for today is quite sloppy. For part 2, I chose to color along both sides of the path (each side different colors) and then doing a fill of the empty space based on what color the empty space is touching. Way less optimal than scanning, and I didn't cover every case for coloring around the start point, but it was interesting to attempt. I ran into a bunch of issues on dealing with nested arrays in Raku, I need to investigate if there's a better way to handle them.
This one was tricky but interesting. In part 2 I basically did Breadth-First-Search starting at S to find all spots within the ring. The trick for me was to move between fields, meaning each position is at the corner of four fields. I never cross the pipe ring, and if I hit the area bounds I know I started outside the ring not inside and start over at a different corner of S.
I got a late start on part 1, and then had to sleep on part 2. Just finished everything up with a little time to spare before day 11.
Part 2 probably would have been easier if I knew more about image processing, but I managed:
Made a copy of the grid and filled it with . tiles
Copied all of the path tiles that I had calculated in part 1
Flood-filled all the . tiles that are connected to the outside edges of the grid with O tiles
Walked along the path, looking for an adjacent O tile at each step. Stopped when one was found, and recorded whether it was to the left or right of the path.
Walked the path again, flood-filling any adjacent inside . tiles with I, and counted them
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: [email protected]
I always felt I was one fix away from the solution, which was both nice and bad.
Walking the path was fine, and part 2 looked easy until I missed the squeezed pipes. I for some silly reason thought I only had to expand the grid by x2 instead of x3 and had to re-do that. Fill is hyper bad but works for <1 minute.
Python
import re
import math
import argparse
import itertools
from enum import Flag,Enum
class Connection(Flag):
Empty = 0b0000
North = 0b0001
South = 0b0010
East = 0b01000
West = 0b10000
def connected_directions(first:Connection,second:Connection) -> bool:
return bool(((first.value >> 1) & second.value) or
((first.value << 1) & second.value))
def opposite_direction(dir:Connection) -> Connection:
if dir.value & 0b00011:
return Connection(dir.value ^ 0b00011)
if dir.value & 0b11000:
return Connection(dir.value ^ 0b11000)
return Connection(0)
class PipeElement:
def __init__(self,symbol:chr) -> None:
self.symbol = symbol
self.connection = Connection.Empty
if symbol in [*'|LJS']:
self.connection |= Connection.North
if symbol in [*'|7FS']:
self.connection |= Connection.South
if symbol in [*'-LFS']:
self.connection |= Connection.East
if symbol in [*'-J7S']:
self.connection |= Connection.West
if self.connection == Connection.Empty:
self.symbol = '.'
def __repr__(self) -> str:
return f"Pipe({self.connection})"
def __str__(self) -> str:
return self.symbol
def connected_to(self,pipe,direction:Connection) -> bool:
if not (self.connection & direction):
return False
if self.connection & direction and pipe.connection & opposite_direction(direction):
return True
return False
class Navigator:
def __init__(self,list:list,width) -> None:
self.list = list
self.width = width
def at(self,position):
return self.list[position]
def neighbor(self,position,direction:Connection) -> tuple | None:
match direction:
case Connection.North:
return self.prev_row(position)
case Connection.South:
return self.next_row(position)
case Connection.East:
return self.next(position)
case Connection.West:
return self.prev(position)
raise Exception(f"Direction not found: {direction}")
def prev_row(self,position) -> tuple | None:
p = position - self.width
if p < 0:
return None
return (p,self.list[p])
def next_row(self,position) -> tuple | None:
p = position + self.width
if p >= len(self.list):
return None
return (p,self.list[p])
def prev(self,position) -> tuple | None:
p = position - 1
if p < 0:
return None
return (p,self.list[p])
def next(self,position) -> tuple | None:
p = position + 1
if p >= len(self.list):
return None
return (p,self.list[p])
def all_neighbors(self,position) -> list:
l = list()
for f in [self.next, self.prev, self.next_row,self.prev_row]:
t = f(position)
if t != None:
l.append(t)
return l
def find_connected(self,position,exclude=Connection.Empty) -> tuple | None:
for dir in [Connection.East,Connection.West,Connection.North,Connection.South]:
if dir == exclude:
continue
n = self.neighbor(position,dir)
if n == None:
continue
if self.at(position).connected_to(n[1],dir):
return (*n,dir)
return None
class TileType(Enum):
Inside = 1
Outside = 0
Pipe = 2
PlaceHolder = 3
def pipe_to_tile_expand(pipe:PipeElement) -> list:
s = str(pipe)
expansions = {
'.': '.PP'+ 'PPP' + 'PPP',
'-': 'PPP'+ '---' + 'PPP',
'|': 'P|P'+ 'P|P' + 'P|P',
'F': 'PPP'+ 'PF-' + 'P|P',
'7': 'PPP'+ '-7P' + 'P|P',
'J': 'P|P'+ '-JP' + 'PPP',
'L': 'P|P'+ 'PL-' + 'PPP',
'S': 'P|P'+ '-S-' + 'P|P'
}
l = expansions[s]
return [pipe_to_tile(x) for x in [*l]]
def pipe_to_tile(pipe:str) -> TileType:
expansions = {
'.': TileType.Inside,
'-': TileType.Pipe,
'|': TileType.Pipe,
'F': TileType.Pipe,
'7': TileType.Pipe,
'J': TileType.Pipe,
'L': TileType.Pipe,
'S': TileType.Pipe,
'P': TileType.PlaceHolder
}
return expansions[pipe]
def chunks(lst, n):
"""Yield successive n-sized chunks from lst."""
for i in range(0, len(lst), n):
yield lst[i:i + n]
def print_tiles(tile_list:list,width:int):
for c in chunks(tile_list,width):
print("".join([str(t.value) for t in c]))
def print_pipes(tile_list:list,width:int):
for c in chunks(tile_list,width):
print("".join([str(t) for t in c]))
def main(line_list:list,part:int):
width = None
pipe_list = list()
tile_list = list()
start_o = None
for line in line_list:
line = line + ' ' # stops east/west joining over new lines
if width == None:
width = len(line)
for c in [*line]:
o = PipeElement(c)
pipe_list.append(o)
tile_list.append(TileType.Inside)
if c == 'S':
start_o = o
#print(pipe_list)
start_pos = pipe_list.index(start_o)
start_co = (start_pos // width, start_pos % width)
print(f"starting index: {start_pos}: {start_co}")
nav = Navigator(pipe_list,width)
cur_pos = None
last_dir = Connection.Empty
steps = 0
while cur_pos != start_pos:
if cur_pos == None:
cur_pos = start_pos
pipe = nav.find_connected(cur_pos,exclude=opposite_direction(last_dir))
if pipe == None:
raise Exception(f"end of pipe at: {cur_pos}, {nav.at(cur_pos)}")
cur_pos = pipe[0]
last_dir = pipe[2]
steps += 1
#print(f"{cur_pos}->",end="")
tile_list[cur_pos] = TileType.Pipe
print(f"end: {cur_pos}, steps: {steps}")
clean_pipe = list()
for i in range(0,len(pipe_list)):
if tile_list[i] == TileType.Pipe:
clean_pipe.append(pipe_list[i])
else:
clean_pipe.append(PipeElement('.'))
print_pipes(clean_pipe,width)
print(f"part 1: {steps/2}")
# part 2 outputs
#print("start tile:")
#print_tiles(tile_list,width)
# add outsides to edge of map
tile_list2 = list()
#first row
expanded_width = (width*3)+2
for i in range(0,expanded_width):
tile_list2.append(TileType.Outside)
for row in chunks(clean_pipe, width):
## we need to expand this to 2x size tiles
t_rows = [ list() for x in range(0,3)]
[ x.append(TileType.Outside) for x in t_rows]
for r in row:
parts = pipe_to_tile_expand(r)
[ t_rows[x].extend( parts[x*3:(x*3)+3] ) for x in range(0,3)]
[ x.append(TileType.Outside) for x in t_rows]
[ tile_list2.extend(x) for x in t_rows]
for i in range(0,expanded_width):
tile_list2.append(TileType.Outside)
#print("with o tile:")
#print_tiles(tile_list2,width+2)
tilenav = Navigator(tile_list2,expanded_width)
changes = True
while changes == True:
changes = False
count_in = 0
for i in range(0,len(tile_list2)):
t = tilenav.at(i)
if t == TileType.Inside or t == TileType.PlaceHolder:
n = tilenav.all_neighbors(i)
if any([x[1] == TileType.Outside for x in n]):
tilenav.list[i] = TileType.Outside
changes = True
continue
if t == TileType.Inside:
count_in += 1
print("with outside tile:")
print_tiles(tile_list2,expanded_width)
print(count_in)
if __name__ == "__main__":
parser = argparse.ArgumentParser(description="template for aoc solver")
parser.add_argument("-input",type=str)
parser.add_argument("-part",type=int)
args = parser.parse_args()
filename = args.input
if filename == None:
parser.print_help()
exit(1)
part = args.part
file = open(filename,'r')
main([line.rstrip('\n') for line in file.readlines()],part)
file.close()
I have zero idea how this functions correctly. I fear to touch it more than necessary or it would fall apart in a moment.
I got second star after 8 hours (3 hours for part 1 + 4 hour break + 1 hour part 2), at that moment I've figured out how to mark edges of enclosed tiles. Then I just printed the maze and counted all in-between tiles manually. A bit later I've returned and fixed the code with an ugly regex hack, but atleast it works.
Code: day_10/solution.nim
Double expansion seams like a nice approach, but I didn't think of that. Instead, I just scan the lines and “remember” if I am in a component or not by counting the number of pipe crossings.
This was a great challenge, it was complex enough to get me to explore more of the Nim language, mainly (ref) types, iterators, operators, inlining.
I first parse the input to Tiles stored in a grid. I use a 1D seq for fast tile access, in combination with a 2D Coord type. From the tile "shapes" I get the connection directions to other tiles based on the lookup table shapeConnections. The start tile's connections are resolved based on how the neighbouring tiles connect.
Part 1 is solved by traversing the tiles branching out from the start tile in a sort of pathfinding-inspired way. Along the way I count the distance from start, a non-negative distance means the tile has already been traversed. The highest distance is tracked, once the open tiles run our this is the solution to part 1.
Part 2 directly builds on the path found in Part 1. Since the path is a closed loop that doesn't self-intersect, I decided to use the raycast algorithm for finding if a point lies inside a polygon. For each tile in the grid that is not a path tile, I iterate towards the right side of the grid. If the number of times the "ray" crosses the path is odd, the point lies inside the path. Adding all these points up give the solution for Part 2.
Initially it ran quite slow (~8s), but I improved it by caching the tile connections (instead of looking them up based on the symbol), and by ditching the "closed" tiles list I had before which kept track of all the path tiles, and switched to checking the tile distance instead. This and some other tweaks brought the execution speed down to ~7ms, which seems like a nice result :)
proc solve*(input:string):array[2, int]=
let lines = input.readFile.strip.splitLines.filterIt(it.len != 0)
# build grid
var grid = Grid(width:lines[0].len, height:lines.len)
for line in lines:
grid.tiles.add(line.mapIt(Tile(shape:it)))
# resolve tile connections
for t in grid.tiles:
t.connections = shapeConnections[t.shape]
# find start coordinates and resolve connections for it
let startCoords = grid.find('S')
let startTile = grid[startCoords]
startTile.connections = startCoords.findConnections(grid)
startTile.distance = 0
# Traverse both ends of path from start
var open: Deque[Coord]
open.addLast(startCoords)
while open.len != 0:
let c = open.popFirst # current coordinate
let ct = grid[c] # tile at c
#find and add connected neighbour nodes
for d in ct.connections:
let n = c+d
let nt = grid[n]
# if not already on found path and not in open tiles
if nt.distance == -1 and not (n in open):
nt.distance = ct.distance + 1
result[0] = max(result[0], nt.distance)
open.addLast(n)
# Part 2
for c in grid:
let ct = grid[c]
#path tiles are never counted
if ct.distance >= 0:
continue
# search from tile to end of row
var enclosed = false
for sx in c.x.. 0):
enclosed = not enclosed
result[1] += ord(enclosed)
Well, star one is solved. I don't love the code, but yet again, it works for now. I don't love the use of a label to continue/break a loop, and the valid_steps function is a mess that could probably be done much cleaner.
Upon looking at star 2 I don't even have the slightest idea of where to start. I may have to come back to this one at a later date. Sigh.