Had to reach for Haskell again. This may happen on the hard ones! Solved it using correct line segment intersections rather than enumerating every single coordinate.
Scratched my head on part 2 for a bit then realised each segment could store the accumulated length, then it was a simple shortening calculation for each line at the intersections.
{-# LANGUAGE OverloadedStrings #-}importData.Ord(comparing)importData.Foldable(minimumBy)importData.Maybe(maybeToList)importqualifiedData.TextasTimportTest.HspecdataDirection=U|D|L|Rderiving(Eq,Show)dataMove=MoveDirectionIntderiving(Eq,Show)dataPoint=PointIntIntderiving(Eq,Show)-- A Segment is the distance to its end and the start and end pointsdataSegment=SegmentIntPointPointderiving(Eq,Show)-- An Intersection is the crossing point and the distance along each wire to that pointdataIntersection=IntersectionPointIntIntderiving(Show)typeWire=[Segment]manhattan::Point->Intmanhattan(Pointxy)=(absx)+(absy)centralPort::PointcentralPort=Point00expandWire::[Move]->WireexpandWiresegs=tailsegmentswherefollow(Segmentlen_(Pointxy))(MoveUn)=Segment(len+n)(Pointx(y+1))(Pointx(y+n))follow(Segmentlen_(Pointxy))(MoveDn)=Segment(len+n)(Pointx(y-1))(Pointx(y-n))follow(Segmentlen_(Pointxy))(MoveLn)=Segment(len+n)(Point(x-1)y)(Point(x-n)y)follow(Segmentlen_(Pointxy))(MoveRn)=Segment(len+n)(Point(x+1)y)(Point(x+n)y)segments=scanlfollow(Segment0centralPortcentralPort)segsload::String->[Wire]load=mapexpandWire.mapwire.T.splitOn"\n".T.strip.T.packwherewire=map(segment.T.unpack.T.strip).T.splitOn","segment(d:len)=Move(dird)(readlen)dir'U'=Udir'D'=Ddir'L'=Ldir'R'=Rvertical::Segment->Boolvertical(Segment_(Pointx1_)(Pointx2_))=x1==x2horizontal::Segment->Boolhorizontal(Segment_(Point_y1)(Point_y2))=y1==y2wireIntersections::Wire->Wire->[Intersection]wireIntersections[]_=[]wireIntersections_[]=[]wireIntersections(x:xs)(y:ys)=maybeToList(intersectionxy)++wireIntersections[x]ys++wireIntersectionsxsyscrosses::Int->Int->Int->Boolcrossesabc=(minab)<c&&c<(maxab)intersection::Segment->Segment->MaybeIntersectionintersections1@(Segmentl1(Pointx1y1)(Pointx2y2))s2@(Segmentl2(Pointx3y3)(Pointx4y4))=ifverticals1&&horizontals2&&crossesy1y2y3&&crossesx3x4x1thenJust$Intersection(Pointx1y3)(l1-abs(y2-y3))(l2-abs(x4-x1))elseifhorizontals1&&verticals2&&crossesx1x2x3&&crossesy3y4y1thenJust$Intersection(Pointx3y1)(l1-abs(x2-x3))(l2-abs(y4-y1))elseNothingintersections::[Wire]->[Intersection]intersections[]=[]intersections(w:ws)=(intersections'wws)++(intersectionsws)whereintersections'wws=concat$map(wireIntersectionsw)wsintersectionManhattan::Intersection->IntintersectionManhattan(Intersectionp__)=manhattanpintersectionDistance::Intersection->IntintersectionDistance(Intersection_ab)=a+bbestIntersectionBy::(Intersection->Int)->[Intersection]->MaybeIntersectionbestIntersectionBy_[]=NothingbestIntersectionBycmpis=Just$minimumBy(comparingcmp)ispart1::[Wire]->MaybeIntpart1=fmapintersectionManhattan.bestIntersectionByintersectionManhattan.intersectionspart2::[Wire]->MaybeIntpart2=fmapintersectionDistance.bestIntersectionByintersectionDistance.intersectionstestCase1=load"R8,U5,L5,D3\nU7,R6,D4,L4"testCase2=load"R75,D30,R83,U83,L12,D49,R71,U7,L72\nU62,R66,U55,R34,D71,R55,D58,R83"testCase3=load"R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51\nU98,R91,D20,R16,D67,R40,U7,R15,U6,R7"main=dopart1testCase1`shouldBe`Just6part1testCase2`shouldBe`Just159part1testCase3`shouldBe`Just135part2testCase1`shouldBe`Just30part2testCase2`shouldBe`Just610part2testCase3`shouldBe`Just410input<-fmapload$readFile"input.txt"putStrLn$show(part1input)putStrLn$show(part2input)
Had to reach for Haskell again. This may happen on the hard ones! Solved it using correct line segment intersections rather than enumerating every single coordinate.
Scratched my head on part 2 for a bit then realised each segment could store the accumulated length, then it was a simple shortening calculation for each line at the intersections.
I'm not proud of that
intersection
function. 12 variables in scope. The horror!