Advent of Code (in MiniScript), Day 23
Tags: miniscript, adventofcode, programming
Published: 2022-12-23 18:08:43

Welcome back to my [series](https://dev.to/search?q=JoeStrout%20%23adventofcode&sort_by=published_at&sort_direction=asc) of [Advent of Code](https://adventofcode.com/) solutions in [MiniScript](https://miniscript.org)!  [Day 23](https://adventofcode.com/2022/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.

![Animation of elves spreading out over 10 rounds](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/samzqjm8q17602ml7op6.gif)

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
```

{% spoiler 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)
```
{% endspoiler %}

## 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](https://miniscript.org/MiniMicro/), 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.

![Animation of all 2754 elves spreading out](https://miniscript.org/img/elves-animation.webp)

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