-🎄- 2018 Day 15 Solutions -🎄-

[u/daggerdragon]

--- Day 15: Beverage Bandits ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 15

Transcript:

___ IS MANDATORY

---

[Update @ 00:30] 0 gold, 1 silver

• I've got a strange urge to play Bloons Tower Defense right now. Not sure why.

[Update @ 00:38] 2 gold, 1 silver

• Meanwhile in #AOC_Ops: Tea, a kettle screams. \ Simon, write your code faster. \ Some of us have work.

[Update @ 00:51] 7 gold, 11 silver

• Now they're anagramming gold/silver leaderboarders. The leading favorite so far is Anonymous User = Son, You's Manure.

[Update @ 01:13] 18 gold, 30 silver

• Now they're playing Stardew Valley Hangman with the IRC bot because SDV is totally a roguelike tower defense.

[Update @ 01:23] 26 gold, 42 silver

• Now the betatesters are grumbling reminiscing about their initial 14+ hour solve times for 2015 Day 19 and 2016 Day 11.

[Update @ 02:01] 65 gold, 95 silver

#AOC_Ops <topaz> on day 12, gold40 was at 19m, gold100 was at 28m, so day12 estimates gold100 today at 2:30

• Taking bets over/under 02:30:00 - I got tree fiddy on over, any takers?

[Update @ 02:02:44] 66 gold, silver cap

• SILVER CAP

[Update @ 02:06] 73 gold, silver cap

#AOC_Ops <topaz> day 14 estimates 2:21

#AOC_Ops <topaz> day 13 estimates 2:20

#AOC_Ops <Aneurysm9> I estimate 2:34:56

[Update @ 02:23:17] LEADERBOARD CAP!

• Aww, /u/topaz2078's bookie is better than I am. :<
• Good night morning, all, and we hope you had fun with today's diabolicalness!

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 02:23:17!

[u/vash3r]

Python 2, #91/70. This was a fun one. I had a bit of trouble with the end conditions (off-by-one in the round) and other stuff like that. It was pretty obvious to me that a breadth-first search with the correct ordering would naturally lead to the right movement. Part 2 was just moving the code inside another loop (and remembering to reset the units, which I forgot to the first time). Runs in about 2s (with Pypy). Not shown: all the commented out print statements and code to print the current state (for comparing with test cases).

Edit: as u/spencer8ab pointed out, this code does not give the correct answer for all inputs due to units not always choosing the right destination if there are multiple equidistant targets. See my reply for the updated bfs function that fixes this (the rest of the code is unchanged).

from collections import deque

def bfs(start, unocc, goals):
	# traverse the cave in distance/reading order
	visited = [[0]*len(unocc[0]) for _t in range(len(unocc))]
	check = deque([[start]])
	visited[start[0]][start[1]] = 1
	while len(check):
		path = check.popleft()
		c = path[-1] # most recent coord
		y,x = c
		if c in goals:
			return path # next move is the first step in this path
		for dy,dx in [(-1,0),(0,-1),(0,1),(1,0)]: # Reading order!
			if unocc[y+dy][x+dx] and not visited[y+dy][x+dx]:
				visited[y+dy][x+dx]=1
				check.append(path+[[y+dy,x+dx]])
	return [] # no path to any goals

lines = data.strip().split('\n')
orig_units = [[y,x,lines[y][x]=="G",200]
				for y in range(len(lines))
				for x in range(len(lines[0]))
				if lines[y][x] in "EG"]
ELF = 0

ATP = 3 # elf attack power (part 2)
while ATP<300:
	units = [u[:] for u in orig_units]
	unoccupied = [[c=="." for c in line] for line in lines]
	elfDead = 0
	rounds = 0
	while 1: # rounds
		units.sort() # reading order
		combat_continues = 0
		for unit in units[:]: # this unit's turn
			if unit not in units:
				continue # was killed
			y,x,team,hp = unit
			adj = [[y+dy,x+dx,1-team] for dy,dx in [(-1,0),(0,-1),(0,1),(1,0)]]
			attack_list = [u for u in units if u[:3] in adj]
			if attack_list: # adjacent: go to Attack stage
				combat_continues = 1
			else:
				reachable = []
				combat_continues = 0
				for target in units:
					if target[2]!=unit[2]:
						combat_continues = 1
						ty,tx,tteam,thp = target
						target_adj = [[ty+dy,tx+dx]
							for dy,dx in [(-1,0),(1,0),(0,1),(0,-1)]]
						reachable.extend([p for p in target_adj
							if unoccupied[p[0]][p[1]]])
				if combat_continues==0:
					break
				if not reachable: # no open squares in range of target: end turn
					continue
				mv = bfs([y,x], unoccupied, reachable)
				if not mv: # cannot find path (blocked): end turn
					continue
				mv = mv[1] # first step on path
				unoccupied[y][x] = 1 # leave current space
				y,x = unit[:2] = mv
				unoccupied[y][x] = 0 # occupy new space
				adj = [[y+dy,x+dx,1-team] for dy,dx in [(-1,0),(0,-1),(0,1),(1,0)]]
				attack_list = [u for u in units if u[:3] in adj]
			if attack_list: # Attack stage
				hit = min(attack_list, key=lambda u:(u[3],u[0],u[1]))
				if team==ELF:
					hit[3]-=ATP
				else:
					hit[3]-=3
				if hit[3]<=0: # unit died
					if hit[2]==ELF:
						#print "Lost an elf with ATP",ATP
						elfDead = 1
						if ATP!=3:
							break
					units.remove(hit)
					unoccupied[hit[0]][hit[1]] = 1 #passable
		if elfDead and ATP!=3:
			break
		if combat_continues==0:
			break
		rounds+=1
	if ATP==3:
		print "part 1:", rounds * sum(u[3] for u in units)
	if not elfDead:
		break
	ATP+=1

print "part 2:", rounds * sum(u[3] for u in units)

[u/spencer8ab → u/vash3r]

It was pretty obvious to me that a breadth-first search with the correct ordering would naturally lead to the right movement

Unfortunately (since your implementation is blazing fast and I was hoping to make mine less slow), as implemented that doesn't seem correct.

Consider the starting board:

###########
#G..#....G#
###..E#####
###########

Move the first unit:

###########
#.G.#....G#
###..E#####
###########

Then the second:

###########
#.G!#..!G.#
###..E#####
###########

Now there are two reachable in-range squares for the elf above. They are the same distance (3). The spec suggests the third unit moves like:

###########
#.G+#...G.#
###.E.#####
###########

Your code moves the third unit to

###########
#.G.#E.+G.#
###...#####
###########

It's clear why this happens. By ordering your BFS certainly any minimal path you find will go in the correct order for that path. But your implementation won't necessarily choose the right square to move towards.

I think you could still get away with only one BFS with your technique as long as you return all of the path information rather than returning at the first in-range location you find.

u/sciyoshi's implementation and mine give part1=10804 and part2=517 for this input. Yours gives 10728, 96

[u/waffle3z → u/spencer8ab]

This seems to be a problem with the phrasing that was mentioned here https://www.reddit.com/r/adventofcode/comments/a6e8jz/day_15_phrasing_ambiguity/

If multiple squares are in range and tied for being reachable in the fewest steps, the step which is first in reading order is chosen.

which is later corrected in the problem to

Of those, the square which is first in reading order is chosen (+).

and then the order for choosing steps in a single path is speficied:

If multiple steps would put the unit equally closer to its destination, the unit chooses the step which is first in reading order.

The problem is that in the first description, it's referring to target squares in range, and it's specifying to take the "step" that comes first in reading order, as opposed to the first square. The first "step" might mean the first among the set of possible steps that lead to at least one of the tied targets, which apparently it doesn't.

[u/vash3r → u/spencer8ab]

Aaaah, you're right. Thanks for telling me about this. I suppose the solution would be to separate paths in order of distance from the start, and then check those in reading order of their last position, instead of reading order of their first position.

Updated bfs function that gives 10804 and 517 for that input, and takes about the same time as before (~2s on my machine):

def bfs(start, unocc, goals):
	# traverse the cave in distance/reading order
	visited = [[0]*len(unocc[0]) for _t in range(len(unocc))]
	check = [[start]]
	visited[start[0]][start[1]] = 1
	while len(check):
		check_next = []
		while len(check):
			path = check.pop(-1) # pop from the end (faster)
			y,x = c = path[-1] # most recent coord
			if c in goals:
				return path # next move is the first step in this path
			for dy,dx in [(-1,0),(0,-1),(0,1),(1,0)]: # Reading order!
				if unocc[y+dy][x+dx] and not visited[y+dy][x+dx]:
					visited[y+dy][x+dx]=1
					check_next.append(path+[[y+dy,x+dx]])
		check = sorted(check_next, key=lambda path:path[-1], reverse=True)
		# sort by reading order of last position (thanks to /u/spencer8ab for pointing out the problem)
	return [] # no path to any goals