JoeStroutWelcome 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!
