Advent of Code (in MiniScript), Day 23

Welcome back to my series of Advent of Code solutions in MiniScript! Day 23 was quite fun and interesting. It was a simulation task: given a bunch of elves, and rules about how they move relative to their neighbors, figure out how much area they cover after 10 turns.

The rules for how the elves move are a bit complex. First, any elf with no immediate neighbors does not move at all. Then, the elves look in each of the four directions. If there is an elf in that direction, or the two adjacent diagonal directions, the elf does not move.

Otherwise, the elf "proposes" to move in that direction. All the elves make their proposals first. Then, in any case where more than one elf proposes to move to the same square, none of those elves move. The ones who were the only one to propose to move to their square do move.

Oh, and as a final wrinkle, on each round they consider the four directions in a different order.

The result is that the elves gradually spread out.

My first thought was to keep the data for what elves were where, and how many elves proposed to move into each spot, in a 2D array (list of lists). But the problem is, these elves are moving around and spreading out on every turn — how big to make that array? I could have just sized it generously (and added an offset, to allow for elves at negative X or Y), but instead I chose to use:

• for the current elf positions, a list of [x,y] values called elves
• for each elf's proposed move, a map from [x,y] elf position to [x,y] new position to move to, called nextPos
• to find conflicting proposals, a map from [x,y] proposed move position to a count of how many elves are proposing to move there; this is called propCount.

In retrospect this maybe wasn't the most efficient choice, but it worked well enough (at least until Part 2).

To simplify dealing with directions, I made a map of the X and Y change implied by each of the four directions; and then another one that includes the diagonals.

dpos = [[0,-1], [0,1], [-1,0], [1,0]]   // North, South, West, East

dposWithDiagonals = [
    [[0,-1],[-1,-1],[1,-1]],
    [[0,1], [-1,1], [1,1]],
    [[-1,0], [-1,-1], [-1,1]],
    [[1,0], [1,-1], [1,1]] ]

These are in the order defined by the challenge description. So now we can represent a direction by an index (0-3) into the lists above.

The heart of the simulation is in the propose function, where each elf figures out which way it wants to move. This takes in a list of directions (those 0-3 indexes), in the order in which they should be considered.

propose = function(dirs)
    globals.nextPos = {}
    globals.propCount = {}
    for elf in elves
        if not hasAnyNeighbor(elf) then continue
        for dir in dirs
            // check to see if there is any elf in that direction or diagonal to it
            anyElf = false
            for d in dposWithDiagonals[dir]
                pos = elf.plus(d)
                if elves.contains(pos) then
                    anyElf = true
                    break
                end if
            end for
            if anyElf then continue
            // since not, propose to move in that direction
            newPos = elf.plus(dpos[dir])
            propCount[newPos] = propCount.get(newPos,0) + 1
            nextPos[elf] = newPos
            // ...and consider no other directions
            break
        end for  // next direction
    end for  // next elf
end function

After this routine has run to generate all the proposals, then a separate move routine is called to actually do the moves.

move = function()
    for elfIdx in elves.indexes
        elf = elves[elfIdx]
        p = nextPos.get(elf, null)
        if p == null then continue
        if propCount[p] > 1 then continue
        elves[elfIdx] = p
    end for
end function

With these in hand, the main loop is just:

dirs = [0, 1, 2, 3]
for round in range(1,10)
    print
    print "Round " + round + " (dirs " + dirs + ")"
    propose dirs
    move
    dirs.push dirs.pull
end for

Here's the complete code for Part 1.

import "mapUtil"
import "listUtil"
import "aoc"

if 1 then fname = "input.txt" else fname = "example.txt"
lines = file.readLines(fname)
if lines == null then
    print "Unable to read: " + fname
    exit
end if
if not lines[-1] then lines.pop

mapW = lines[0].len
mapH = lines[1].len
print "Map: " + mapW + " x " + mapH

// find the elves
elves = []          // each an [x,y] pair
for y in lines.indexes
    line = lines[y]
    for x in line.indexes
        if line[x] == "#" then elves.push [x,y]
    end for
end for
print elves.len + " elves"

dpos = [[0,-1], [0,1], [-1,0], [1,0]]   // North, South, West, East

dposWithDiagonals = [
    [[0,-1],[-1,-1],[1,-1]],
    [[0,1], [-1,1], [1,1]],
    [[-1,0], [-1,-1], [-1,1]],
    [[1,0], [1,-1], [1,1]] ]

nextPos = {}        // key: [x,y] of an elf; value: new [x,y] to move to
propCount = {}      // key: [x,y]; value: count of elves proposing to move there

hasAnyNeighbor = function(elf)
    x = elf[0]; y = elf[1]
    for i in range(-1,1)
        for j in range(-1,1)
            if i == 0 and j == 0 then continue
            if elves.contains([x+i, y+j]) then return true
        end for
    end for
end function

propose = function(dirs)
    globals.nextPos = {}
    globals.propCount = {}
    for elf in elves
        if not hasAnyNeighbor(elf) then continue
        for dir in dirs
            // check to see if there is any elf in that direction or diagonal to it
            anyElf = false
            for d in dposWithDiagonals[dir]
                pos = elf.plus(d)
                if elves.contains(pos) then
                    anyElf = true
                    break
                end if
            end for
            if anyElf then continue
            // since not, propose to move in that direction
            newPos = elf.plus(dpos[dir])
            propCount[newPos] = propCount.get(newPos,0) + 1
            nextPos[elf] = newPos
            // ...and consider no other directions
            break
        end for  // next direction
    end for  // next elf
end function

move = function()
    for elfIdx in elves.indexes
        elf = elves[elfIdx]
        p = nextPos.get(elf, null)
        if p == null then continue
        if propCount[p] > 1 then continue
        elves[elfIdx] = p
    end for
end function

calcMinMax = function()
    globals.minX = elves[0][0]; globals.maxX = minX
    globals.minY = elves[0][1]; globals.maxY = minY
    for elf in elves
        globals.minX = min(minX, elf[0])
        globals.maxX = max(maxX, elf[0])
        globals.minY = min(minY, elf[1])
        globals.maxY = max(maxY, elf[1])
    end for
end function

showElves = function()
    calcMinMax
    globals.emptyGround = 0
    for y in range(minY, maxY)
        s = []
        for x in range(minX, maxX)
            if elves.contains([x,y]) then
                s.push "#"
            else
                s.push "."
                globals.emptyGround = emptyGround + 1
            end if
        end for
        print s.join("")
    end for
end function

clear
showElves

dirs = [0, 1, 2, 3]
for round in range(1,10)
    print
    print "Round " + round + " (dirs " + dirs + ")"
    propose dirs
    move
    dirs.push dirs.pull
    //  showElves; key.get
end for

calcMinMax

area = (maxX-minX + 1) * (maxY-minY + 1)
print "Total area: " + area
print "Empty area: " + (area - elves.len)

Part 2

The second part is a fairly minor change: instead of running the simulation for 10 rounds and reporting the empty area covered, we are to keep running the simulation until all the elves stop moving, and report how many rounds that took.

So this was mostly a matter of making the move function return how many elves moved, and then changing the main loop to:

dirs = [N,S,W,E]
round = 1
while true
    print "Round " + round + " (dirs " + dirs + ")"
    propose dirs
    count = move
    print count + " elves moved"
    if count == 0 then break
    dirs.push dirs.pull
    round = round + 1
end while

Trouble is, when I ran this, I found it too slow. It takes a second or two for each round, and I saw that it was going to take hundreds, maybe thousands of rounds to finish.

So while it was still running, I started a second instance of Mini Micro, and modified my data structures a bit. I changed elves from a list into a set — that is, a map where all the values are 1 (and the point is just to give efficient lookup of the keys).

You have to be very careful using mutable objects, like lists or other maps, as keys in a map. If you use (say) such a list as a map key, and then change its contents, the map may be no longer able to find it correctly (because under the hood, it has been placed into the wrong hash bin for its new hash value). So in the move routine, I took care to move an elf from its current position (elf) to its new position (p) as follows:

        elves.remove elf
        elves.push p

With these relatively minor changes, the code ran much faster! I started the new version when the old version had done more than 400 iterations, but it quickly caught up and surpassed its predecessor. In the end, it took 1025 rounds for my elves to settle down.

Final Thoughts

This was a fun challenge. I love simulations in general — there's something inherently satisfying about them.

Part 1 took me 43 minutes to code up, partly because I originally missed the "elves stop moving if they have no neighbors" rule. That placed me 898th in the competition; given the popularity of Advent of Code, I'll take anything in the top 1000 as a win! On the second part, however, my rank was 1788 (with a total time of 1:16). This was certainly in part because of my initially slow implementation, and the 10 minutes I puttered around the room hoping it would finish before deciding to try a faster approach.

Only two more challenges to go for 2022! I've been having a blast, but it will be nice to go to bed at a reasonable hour and get a full night's sleep again. Happy holidays!