Advent of Code (in MiniScript), Day 18

Welcome back to my series of Advent of Code solutions in MiniScript! Day 18 was pretty straightforward, though it presents some interesting choices in how to represent the data -- choices I'm not sure I made optimally.

We are given the coordinates of a bunch of blocks in a 3D grid. Think of something like a small floating island in Minecraft.

Our first task is to simply report how many exposed block faces are in this bunch.

The first choice faced is: how do we represent 3D coordinates? In Mini Micro, there are two common conventions: either an [x, y, z] list, or a map with x, y, and z members. And then of course when declaring a function, there is a third option, which is to take separate x, y, and z parameters.

The other big decision to be made is: how to represent the blocks? The two obvious approaches are as a 3D array, which you can easily set up using list.init3d from the listUtil module; or as a map, with one entry for each block. The latter is more memory-efficient if your space is very sparse (i.e., has few blocks for the volume of possible blocks); but a 3D array is easier and often more performant to access any particular location.

I chose to represent coordinates (mostly) as little maps, and to store those in a larger cubes map. So solving this task was just a matter of loading that data, and then iterating over my cubes and checking for neighbors in each of the six directions.

import "aoc"

if 0 then fname = "input.txt" else fname = "example.txt"
lines = file.readLines(fname)
if not lines[-1] then lines.pop

// map of cubes in the input file
// index: "1,2,3"; value: map with x,y,z
cubes = {}  

for line in lines
    m = line.match("{x},{y},{z}")
    m.applyToValues @val
    cubes[line] = m
end for

hasNeighbor = function(cube, dx, dy, dz)
    k = (cube.x+dx) + "," + (cube.y+dy) + "," + (cube.z+dz)
    return cubes.hasIndex(k)
end function

count = 0
for cube in cubes.values
    print "checking " + cube
    count = count + (not hasNeighbor(cube, -1, 0, 0))
    count = count + (not hasNeighbor(cube, 1, 0, 0))
    count = count + (not hasNeighbor(cube, 0, -1, 0))
    count = count + (not hasNeighbor(cube, 0, 1, 0))
    count = count + (not hasNeighbor(cube, 0, 0, -1))
    count = count + (not hasNeighbor(cube, 0, 0, 1))
end for
print "Faces: " + count

Part Two

In the second part of the challenge, we now have to discount interior air pockets which are not connected to the outside, and report just how many outside faces there are.

Here I suffered a bit for some of the choices I made in Part 1. The obvious solution in this case is to have a 3D array representing the whole volume of interest (which upon inspection, is only 20 cubes on a side), and do a flood fill from any corner to identify all the "outside" spaces.

That was in fact my final solution, but only after I wasted time on a much less efficient approach, where I used path-finding on every empty space to see if there was a path to corner 0,0,0. Honestly, I don't know what I was thinking. It started chugging away, and I was able to code my second solution (below) and run it to completion before the first attempt finished its run!

import "aoc"

if 1 then fname = "input.txt" else fname = "example.txt"
lines = file.readLines(fname)
if not lines[-1] then lines.pop

cubes = {}

for line in lines
    m = line.match("{x},{y},{z}")
    m.applyToValues @val
    cubes[line] = m
end for

outside = list.init3d(21, 21, 21, false)
toDo = [ [0,0,0] ]
while toDo
    item = toDo.pop
    k = item.join(",")
    if cubes.hasIndex(k) then continue
    if item[0] < 0 or item[0] > 20 then continue
    if item[1] < 0 or item[1] > 20 then continue
    if item[2] < 0 or item[2] > 20 then continue

    if outside[item[0]][item[1]][item[2]] then continue

    outside[item[0]][item[1]][item[2]] = true
    toDo.push [item[0]+1, item[1], item[2]]
    toDo.push [item[0]-1, item[1], item[2]]
    toDo.push [item[0], item[1]+1, item[2]]
    toDo.push [item[0], item[1]-1, item[2]]
    toDo.push [item[0], item[1], item[2]+1]
    toDo.push [item[0], item[1], item[2]-1]
end while

isOutside = function(cube, dx, dy, dz)
    x = cube.x + dx
    y = cube.y + dy
    z = cube.z + dz
    if x < 0 or x > 20 or y < 0 or y > 20 or z < 0 or z > 20 then return true
    return outside[cube.x+dx][cube.y+dy][cube.z+dz]
end function

count = 0
for cube in cubes.values
    count = count + isOutside(cube, -1, 0, 0)
    count = count + isOutside(cube, 1, 0, 0)
    count = count + isOutside(cube, 0, -1, 0)
    count = count + isOutside(cube, 0, 1, 0)
    count = count + isOutside(cube, 0, 0, -1)
    count = count + isOutside(cube, 0, 0, 1)
end for
print "Faces: " + count

This returns an answer in under a second, even for the real input file. And as you can see, the code is pretty simple too.

Results and Conclusions

Despite — or perhaps because of — being a relatively simple problem, my ranking last night was mediocre: 771 on Part One, and 1341 on both parts combined. It certainly hurt me that I didn't choose to use the 3D array right away, especially when it came to Part Two.

It also felt like it took an annoyingly large amount of time to type out the six lines required to deal with each face of a cube (and I had to do this in multiple places). I should probably standardize on [x, y, z] lists to represent 3D vectors, and have functions like orthogonalNeighbors and allNeighbors to represent the 6 or 26 neighboring positions.

One reason I often use maps instead is that it's much neater and more readable to refer to (say) pos.z in code than pos[2]. But I could make list extension methods that make list.x equivalent to list[0], and so on for y and z. Then there would be really no advantage to the maps. I could put this in a "vector3" module along with any other handy 3D-related stuff one might need.

Why did I never think of that before?

(EDIT: See the follow-up!)