diff options
Diffstat (limited to '2018/aoc2018-d15.py')
| -rw-r--r-- | 2018/aoc2018-d15.py | 175 |
1 files changed, 175 insertions, 0 deletions
diff --git a/2018/aoc2018-d15.py b/2018/aoc2018-d15.py new file mode 100644 index 0000000..2911a4d --- /dev/null +++ b/2018/aoc2018-d15.py @@ -0,0 +1,175 @@ +#advent of code 2018 +#day 15 +#part 1 and 2 +#oop too hard for scriptkid + +import heapq + +class creature: + def __init__(self, pos, team, unitID,health,attack): + self.team = team; + self.pos = pos; + self.isAlive = True; + self.health = health; + self.attack = attack; + self.unitID = unitID; + + def __str__(self): + return f'{self.team} #{self.unitID}: {self.health}/200'; + + def GetAttacked(self,dmg): + self.health -= dmg; + if self.health <= 0: + self.isAlive = False; + self.health = 0; + + def LookAround(self,enemyset): + targets = []; + p0,p1 = self.pos; + for direction in ReadOrder: + neighbor = (p0+direction[0],p1+direction[1]); + if neighbor in enemyset: + targets.append(neighbor); + return targets; + + def pathfinding(self, enemyset, occupiedset): + paths = []; + pathlimit = len(grid); + queue = []; + heapq.heappush( queue,(0,[self.pos]) ); + visited = set(); + while queue: + d, path = heapq.heappop(queue); + if d > pathlimit: + return paths; + if path[-1] in enemyset: + if pathlimit >= len(path): + paths.append(path); + pathlimit = len(path); + continue; + if path[-1] in visited: continue; + visited.add(path[-1]); + p0,p1 = path[-1]; + for direction in ReadOrder: + neighbor = (p0+direction[0],p1+direction[1]); + if grid.get(neighbor,"#") != ".":continue; + if neighbor in occupiedset: continue; + heapq.heappush(queue,(d+1,path+[neighbor])); + return paths; + + def MakeMove(self, enemyset,occupiedset): + PossiblePaths = self.pathfinding(enemyset,occupiedset); + if len(PossiblePaths) != 0: + for nextpath in sorted( PossiblePaths, key = lambda node: node[1]): + self.pos = nextpath[1]; + return True; + break; + return False; + + +def run(ulist,att,part2): + units = dict(); + u_hp = 200; + for unit in ulist: + u_pos, u_team, u_id = unit; + u_att = 3; + if u_team == "E": u_att = att; + units[u_id] = creature(u_pos,u_team,u_id,u_hp,u_att) ; + + TotalHP = dict(); + TotalHP["E"] = 1; + TotalHP["G"] = 1; + Round = 0; + while TotalHP["E"] > 0 and TotalHP["G"] > 0: + if part2 and len([1 for uid in units if units[uid].isAlive==False and units[uid].team=="E"]) != 0: + return 0; + + for unit_id in sorted(units, key=lambda p: units[p].pos): + if not units[unit_id].isAlive : continue; + enemyLocation = dict(); + for Unit in units: + if units[Unit].team != units[unit_id].team and units[Unit].isAlive: + enemyLocation[units[Unit].pos] = Unit; + + occupied = set([units[Unit].pos for Unit in units if units[Unit].isAlive and units[Unit].team == units[unit_id].team]); + InRangeTargets = units[unit_id].LookAround(enemyLocation); + + if len(InRangeTargets) != 0: + TargetsOrdered = sorted([enemyLocation[tar] for tar in InRangeTargets], key = lambda en: (units[en].health,units[en].pos)); + targetEnemy = TargetsOrdered[0]; + units[targetEnemy].GetAttacked( units[unit_id].attack ); + continue; + + MadeMove = units[unit_id].MakeMove(enemyLocation,occupied); + if not MadeMove: continue; + InRangeTargets = units[unit_id].LookAround(enemyLocation); + if len(InRangeTargets) != 0: + TargetsOrdered = sorted([enemyLocation[tar] for tar in InRangeTargets], key = lambda en: (units[en].health,units[en].pos)); + targetEnemy = TargetsOrdered[0]; + units[targetEnemy].GetAttacked( units[unit_id].attack ); + + TotalHP["E"] = sum([units[uid].health for uid in units if units[uid].team=="E"]); + TotalHP["G"] = sum([units[uid].health for uid in units if units[uid].team=="G"]); + Round += 1; + ################### + #optional turn by turn battleground output + ''' + print(); + locations = dict(); + for unitprint in units: + if not units[unitprint].isAlive: + locations[ units[unitprint].pos ] = units[unitprint].team.casefold() ; + else: + locations[ units[unitprint].pos ] = units[unitprint].team ; + print(units[unitprint]); + + + print("Round",Round); + for y in range(bgsizeY+1): + for x in range(bgsizeX+1): + c = locations.get((y,x),grid[(y,x)]); + print(c,end=""); + print(); + #input(); + ''' + ################### + #part 2 requires all elves to be alive so it's a different check than in part 1 + if part2 and len([1 for u in units if units[u].isAlive==False and units[u].team=="E"]) != 0: + return 0; + else: + #"number of full rounds that were completed (not counting the round in which combat ends)" + elfscore = (Round-1)*sum([units[uid].health for uid in units if units[uid].team=="E"]); + gobscore = (Round-1)*sum([units[uid].health for uid in units if units[uid].team=="G"]); + return(max(elfscore,gobscore)); + + +bgsizeY = 0; +bgsizeX = 0; +grid = dict(); +unitlist = []; +ReadOrder = [(-1,0),(0,-1),(0,1),(1,0)]; +unit_counter = 0; +PuzzleInput = open("15.in","r"); +for y,l in enumerate(PuzzleInput): + l = l.replace("\n",""); + bgsizeY = max(bgsizeY,y); + for x, c in enumerate(l): + bgsizeX = max(bgsizeX,x); + if c == "#": + grid[(y,x)] = "#"; + elif c == ".": + grid[(y,x)] = "."; + else: + unitlist.append(((y,x),c,unit_counter)); + unit_counter += 1; + grid[(y,x)] = "."; +PuzzleInput.close(); + +AttackValue = 3; +p1 = run(unitlist,AttackValue,False); +print("part 1 =", p1); +p2 = 0; +while p2 == 0: + AttackValue += 1; + p2 = run(unitlist,AttackValue,True); +print("part 2 =", p2); |