Took so much time for part two. Actually went ahead and rewrote part one as well. Solution in swift
structPoint:CustomStringConvertible,Equatable,Hashable{varx:Intvary:Intvardescription:String{get{return"X: \(self.x) Y: \(self.y)"}}}vargrid:[Point]=[]_=input.enumerated().map{(y,layer)in_=layer.enumerated().map{(x,point)inifpoint=="#"{grid.append(Point.init(x:x,y:y))}}}funcangleBtw(_x:Point,_y:Point)->Double{return(atan2(Double(x.y-y.y),Double(x.x-y.x))*180)/Double.pi}structLos:CustomStringConvertible{varpoint:Pointvarangle:Doublevardescription:String{get{return"point: \(self.point) angle: \(self.angle)"}}}funcgetAstroidsInLOS(_base:Point)->[Los]{varlos:[Los]=[]letastroids=grid.filter{$0!=base}_=astroids.map{pointinletangle=angleBtw(base,point)varblocked=false_=los.map{aLosinifaLos.angle==angle{blocked=true}}if!blocked{los.append(Los.init(point:point,angle:angle))}}returnlos}funcpartOne(){letresult=grid.map{point->IntinreturngetAstroidsInLOS(point).count}.max()print("Part One answer is :\(result??0)")}funcpartTwo(){letroot=grid.map{point->(Point,Int)inreturn(point,getAstroidsInLOS(point).count)}.max{(p1,p2)->Boolinreturnp1.1<p2.1}!.0varlos=getAstroidsInLOS(root)los.sort{a,bina.angle<b.angle}letbase=los.firstIndex{(aLos)->BoolinreturnaLos.angle==90}letresult=los[199+(base??0)-los.count]print("Part Two is \(result.point.x*100+result.point.y)")}partOne()partTwo()
I'm a Staff Software Engineer at Cisco. I specialize in Python and Go, building functional, practical, and maintainable web systems leveraging Kubernetes and the cloud. Blog opinions are my own.
Things have settled down a little bit since Christmas, so I've got some time to actually complete AOC2019. Better 4 months late than never! Here's my solution to Day 10. Had some trouble deciding how to handle vertical slopes gracefully, and switching back and forth from global to relative coordinates, but finally got it handled.
"""Figure out the best asteroid to look at other asteroids. And then BLAST THEM!"""fromdataclassesimportdataclassfrommathimportgcdfromtypingimportList,Set@dataclass(frozen=True)classPoint:"""An X, Y coordinate on a grid"""x:inty:intdefparse(text:str)->Set[Point]:"""Expects a 2D grid of characters. '#' denote asteroids.
Note: Here, Y+ is down.
"""asteroids=set()rows=text.splitlines()fory,rowinenumerate(rows):forx,cellinenumerate(row):ifcell=="#":asteroids.add(Point(x,y))returnasteroidsdeffind_best(asteroids:Set[Point])->(Point,int):"""Finds the asteroid that can see the most other asteroids.
Returns that asteroid and how many others it can see.
"""scores=[(a,count_visible(a,asteroids))forainasteroids]returnmax(scores,key=lambdax:x[1])defcount_visible(base:Point,asteroids:Set[Point])->int:"""Counts how many asteroids are in line of sight."""returnsum(1forasteroidinasteroidsifcan_see(base,asteroid,asteroids))defcan_see(a:Point,b:Point,asteroids:Set[Point])->bool:"""Determines whether or not an asteroid can see another in an asteroid field."""# Asteroids can't see themselves.
ifa==b:returnFalsedx=b.x-a.xdy=b.y-a.ydivisor=gcd(dy,dx)ifdivisor!=0:# Line isn't vertical or horizontal. Get basic slope.
dx//=divisordy//=divisorelse:# Line is vertical or horizontal. Divisor becomes simply
# the magnitude of the non-zero component.
divisor=max(dx,dy)# Step over every cell on the line between a and b and see if
# it's an asteroid. If any of them are, then b can't be seen from a.
forstepinrange(1,divisor):ifPoint(a.x+step*dx,a.y+step*dy)inasteroids:returnFalsereturnTrue@dataclass(order=True)classLaserPriority:"""A helper class for prioritizing which asteroids get blasted first.
Quadrant assumes X+ is right and Y+ is up, with base at the origin.
Slope uses Y/X, but gets multiplied by -1 so that Laser Priorities
get sorted based on quadrant and then slope in descending order.
"""quadrant:intslope:floatdeflaser_priority_sort_key(asteroid:Point)->LaserPriority:"""Prioritize asteroids based on how they clock around the origin.
Starting at Y+ (up) and going CW.
This function assumes all asteroids being compared are visible.
"""result=LaserPriority(0,0)# Simulate vertical slope as ">> size of grid"
# because ~~~InFiNiTy Is HaRd FoR cOmPuTeRs~~~
ifasteroid.x==0:result.slope=1000else:result.slope=asteroid.y/asteroid.xresult.slope*=-1# Flip so sort goes largest to smallest
ifasteroid.x>=0andasteroid.y>0:result.quadrant=1elifasteroid.x>0andasteroid.y<=0:result.quadrant=2elifasteroid.x<=0andasteroid.y<0:result.quadrant=3else:result.quadrant=4returnresultdefcreate_laser_plan(base:Point,asteroids:Set[Point])->List[Point]:"""Specify the order in which asteroids get BLASTED, assuming we start
at 12 o'clock and go CW, blasting only one asteroid at a time for a
particular clocking before moving on.
"""asteroids=asteroids-{base}# Convert everything so that Y+ is up and base is at 0, 0
relative_asteroids={Point(a.x-base.x,-(a.y-base.y))forainasteroids}plan=[]# Blast asteroids in rounds, removing the ones that get blasted
# after every cycle
whilerelative_asteroids:visible={aforainrelative_asteroidsifcan_see(Point(0,0),a,relative_asteroids)}plan+=sorted(visible,key=laser_priority_sort_key)relative_asteroids-=visible# Unconvert back to global coordinates with Y+ down
plan=[Point(base.x+a.x,base.y-a.y)forainplan]returnplanif__name__=="__main__":withopen("data/day10.txt")asf:grid=f.read()asteroids=parse(grid)best,score=find_best(asteroids)print(f"Best is {best} with {score} visible.")plan=create_laser_plan(best,asteroids)answer=plan[199]# O-based counting!!!
print(f"Lucky number 200 is {answer}.")print(f"Magic number is {answer.x * 100 + answer.y}.")
In the first part I tried an arithmetic approach, trying to find - for each asteroid - if there was another one in line with the target location. JavaScript as usual:
The second part showed that it would have been too complex. So I just converted all the coordinates in polar, sorted them out and counted to the 200th asteroid. Finally, converted back to orthogonal coordinates:
// `asteroids` defined as above...conststationRow=29;conststationColumn=23;constpolarCoords=newMap();asteroids.forEach(([column,row])=>{if(column===stationColumn&&row===stationRow){return;}constdiffColumn=stationColumn-column;constdiffRow=stationRow-row;consttheta=(Math.atan2(diffColumn,-diffRow)+Math.PI)%(Math.PI*2);constrho=Math.sqrt(diffColumn**2+diffRow**2);if(polarCoords.has(theta)){polarCoords.get(theta).add(rho);}else{polarCoords.set(theta,newSet([rho]));}});function*getTargets(){constsortedAngles=newSet([...polarCoords.keys()].sort((a,b)=>a-b));while(sortedAngles.size){for(constthetaofsortedAngles){constrhos=polarCoords.get(theta);if(rhos.size===1){sortedAngles.delete(theta);yield[theta,...rhos];}else{constnearest=Math.min(...rhos);rhos.delete(nearest);yield[theta,nearest];}}}}functiontoOrtho(theta,rho){return[stationColumn+Math.round(Math.sin(theta)*rho),stationRow-Math.round(Math.cos(theta)*rho)]}consttargets=getTargets();letvalue;for(leti=0;i<200;i++){({value}=targets.next());}const[resColumn,resRow]=toOrtho(...value);console.log(resColumn*100+resRow);
Ahh... that's better... More Sealed Classes/Discriminated Unions to the rescue. Managed to cut a lot of duplicated code out.
importDay10.destructionimportDay10.mostVisibleimportarrow.core.andThenimportjava.nio.file.Filesimportjava.nio.file.Pathsimportkotlin.math.PIimportkotlin.math.absimportkotlin.math.atanimportkotlin.math.powimportkotlin.math.sqrtdata classPoint(valx:Int,valy:Int)privatefunPoint.slope(b:Point)=(y-b.y).toDouble()/(x-b.x).toDouble()privatefunPoint.distance(b:Point)=sqrt(abs(x.toDouble()-b.x.toDouble()).pow(2.0)+abs(y.toDouble()-b.y.toDouble()).pow(2.0))privatefunPoint.anglePair(entry:Map.Entry<EuclideanGrouping,List<Point>>)=entry.key.anglePair(this,entry.value)privatefunPoint.countByGroup(entry:Map.Entry<EuclideanGrouping,List<Point>>)=entry.key.count(this,entry.value)sealedclassEuclideanGroupingobjectDown:EuclideanGrouping()objectDownLeft:EuclideanGrouping()objectDownRight:EuclideanGrouping()objectLeft:EuclideanGrouping()objectRight:EuclideanGrouping()objectUp:EuclideanGrouping()objectUpLeft:EuclideanGrouping()objectUpRight:EuclideanGrouping()funPoint.mapEuclideanGroup(other:Point):EuclideanGrouping{returnwhen{other.x>x&&other.y>y->DownRightother.x>x&&other.y<y->UpRightother.x>x&&other.y==y->Rightother.x<x&&other.y>y->DownLeftother.x<x&&other.y<y->UpLeftother.x<x&&other.y==y->Leftother.x==x&&other.y>y->Downother.x==x&&other.y<y->Upelse->throwError("Invalid point comparison: $this to $other")}}funPoint.sortByDistanceFromKeyValue(entry:Map.Entry<Double,List<Point>>)=entry.keytoentry.value.sortedBy(this::distance)funPoint.radiansConverter(offset:Double)={p:Point->(atan(p.slope(this))+offset)}privatefunEuclideanGrouping.anglePair(station:Point,list:List<Point>)=when(this){Up->listOf(0.0tolist)Down->listOf(PItolist)DownLeft,UpLeft->list.groupBy(station.radiansConverter(3*PI/2)).map(station::sortByDistanceFromKeyValue).toList()DownRight,UpRight->list.groupBy(station.radiansConverter(PI/2)).map(station::sortByDistanceFromKeyValue).toList()Left->listOf(3*PI/2tolist)Right->listOf(PI/2tolist)}funEuclideanGrouping.count(station:Point,list:List<Point>)=when(this){Up,Down,Left,Right->list.take(1).count()DownLeft,DownRight,UpLeft,UpRight->list.groupBy{station.slope(it)}.count{(_,v)->v.any()}}objectDay10{privateconstvalFILENAME="src/main/resources/day10.txt"valfileData=Files.readAllLines(Paths.get(FILENAME)).onlyAsteroids()privatefunList<String>.onlyAsteroids()=mapIndexed{y,row->row.mapIndexed{x,c->Point(x,y)toc}}.flatten().filter(Pair<Point,Char>::secondandThen'#'::equals).map(Pair<Point,Char>::first)funmostVisible(data:List<Point>)=data.map{station->stationtodata.asSequence().filterNot(station::equals).groupBy(station::mapEuclideanGroup).asSequence().sumBy(station::countByGroup)}.maxBy{it.second}fundestruction(data:List<Point>):Int{valstation=Point(20,20)valgroupedAsteroids=data.asSequence().filterNot(station::equals).groupBy(station::mapEuclideanGroup).flatMap(station::anglePair)valinitial=emptyList<Point>()togroupedAsteroids.sortedBy{it.first}return(0..(groupedAsteroids.maxBy{it.second.size}?.second?.size?:0)).fold(initial){(destroyed,remaining),_->valnextDestroyed=destroyed+remaining.flatMap{(_,list)->list.take(1)}valnextRemaining=remaining.map{(angle,list)->angletolist.drop(1)}nextDestroyedtonextRemaining}.first[199].let{it.x*100+it.y}}}funmain(){println(mostVisible(Day10.fileData))println(destruction(Day10.fileData))}
Done with part one in swift. need bit more time for part two
Took so much time for part two. Actually went ahead and rewrote part one as well. Solution in swift
Things have settled down a little bit since Christmas, so I've got some time to actually complete AOC2019. Better 4 months late than never! Here's my solution to Day 10. Had some trouble deciding how to handle vertical slopes gracefully, and switching back and forth from global to relative coordinates, but finally got it handled.
Part 1 of day 10:
JS, spent way too long on this because I was mutating state in a for loop!
Things are getting complicated now! I like it!
In the first part I tried an arithmetic approach, trying to find - for each asteroid - if there was another one in line with the target location. JavaScript as usual:
The second part showed that it would have been too complex. So I just converted all the coordinates in polar, sorted them out and counted to the 200th asteroid. Finally, converted back to orthogonal coordinates:
An ugly kotlin solution.
I'll clean it up tomorrow.
Ahh... that's better... More Sealed Classes/Discriminated Unions to the rescue. Managed to cut a lot of duplicated code out.
Python today. And what a tough problem, especially part 2. Glad that's over.
@jon Guess you added wrong title for this post. It should be Day 10!
I was fixing it just as you noticed! That’s what I get for posting past my bedtime.
JS, I like and hate that you could pass part 1 with a bug in your code, that got me thinking for a while when doing part 2!!