PHP, because I'm having to learn it at my internship at the moment. Something isn't right here, because it takes several minutes to run, but at least the solution appears eventually.
<?php$input=file("input3.txt");$wire1=explode(",",substr($input[0],0,strlen($input[0])-1));$wire2=explode(",",$input[1]);$wire1_posn=trace_wire($wire1);$wire2_posn=trace_wire($wire2);[$distance,$time]=find_intersections($wire1_posn,$wire2_posn);echo"\n min distance = $distance, min time = $time";functionfind_intersections($wire1,$wire2){$distances=array();$times=array();foreach($wire1as$posn){if(in_array($posn,$wire2)){[$x,$y]=explode(",",$posn);$distances[]=abs($x)+abs($y);$time1=array_search($posn,$wire1);$time2=array_search($posn,$wire2);$times[]=$time1+$time2+2;}echo".\n";}returnarray(min($distances),min($times));}functiontrace_wire($wire){$x=0;$y=0;foreach($wireas$path){$direction=$path[0];$distance=substr($path,1);if($direction=="U"){for($i=0;$i<$distance;$i++){$y--;$wire_posn[]="$x, $y";}}if($direction=="D"){for($i=0;$i<$distance;$i++){$y++;$wire_posn[]="$x, $y";}}if($direction=="L"){for($i=0;$i<$distance;$i++){$x--;$wire_posn[]="$x, $y";}}if($direction=="R"){for($i=0;$i<$distance;$i++){$x++;$wire_posn[]="$x, $y";}}}return$wire_posn;}
If you’re enumerating every point you’re operating with two lists of hundreds of thousands of items. Worse, I don’t think there’s a way around a cartesian join of the two sets (potentially squaring your already hideous number of data).
Running into performance problems is expected, driving the solution into minutes if you’re not careful (I crashed my jvm and lost a few minutes manually killing it and my ide as they consumed as much processor and memory power as they could)
So, I see everyone did it like I did - recording all visited nodes on the grid and checking for intersections. Now, without considering part 2, is there a smarter way? I'm pretty sure there has to be.
You can generate segments with only the start and end points and check where they intersect, which would require less memory. But the math is more complicated and I'm not sure it's faster, since you can't use a hash table to find the intersections.
The only thing I can see right off the bat is that you’re checking for vertical/horizontal via start/end points, but you could have kept that information (UDLR) alongside the line segment definition. Other than that it makes sense, and other than being too deeply nested for my compulsive refactoring instinct, it doesn’t look much longer than my full-point enumerator.
(If you use a linked list, it doesn’t take more than 30 seconds or so for part b)
you could have kept that information (UDLR) alongside the line segment definition
d'oh that would have made things much more readable.
I was complaining to a coworker that I've done collision detection for 2d games before, and this felt similar, but is sort of like "hard mode" because I didn't necessarily know which endpoint of each line was on the left/right or top/bottom. Keeping that info would have made things more straightforward!
It’s why I love working with people who know the same codebase as me! When you PR or rubber duck, you often get some perspective that makes the “ugly” bits fall into place that you were too close to see!
Not sure if it's the most efficient way of doing it, but this is how I solved it
# Get all the directions from the input
frominputimportmoving_input_1,moving_input_2# Create an object with coordinates for each step
defpopulate_grid(moving_input):coordinates_all={}# Set the current position
x=0y=0# Counter for each time the position moves
step=0# Loop through all the directions given by the file
formoveinmoving_input:direction=move[0]distance=int(move[1:])# Pick in which direction to move
move_x=move_y=0ifdirection=="L":move_x=-1ifdirection=="R":move_x=1ifdirection=="D":move_y=-1ifdirection=="U":move_y=1# Do the actual movement
for_inrange(0,distance):x+=move_xy+=move_ystep+=1if(x,y)notincoordinates_all:coordinates_all[(x,y)]=stepreturncoordinates_all# Get the coordinate grids for each line
line_1=populate_grid(moving_input_1)line_2=populate_grid(moving_input_2)# Get the intersections for both lines
intersections=list(set(line_1.keys())&set(line_2.keys()))# Get the shortest distance
defget_shortest():distances=[]forintersectioninintersections:dist=abs(intersection[0])+abs(intersection[1])distances.append(dist)returnmin(distances)# Get the fewest steps
defget_fewest():combined_steps=[line_1[i]+line_2[i]foriinintersections]returnmin(combined_steps)print("SOLUTION",get_shortest(),get_fewest())
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)
I still have nightmares from previous year's assignment based on coordinates, but luckily this wasn't as bad. Here's my solution for part two in Elixir:
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.
Took me an extra day to clean it up so I wasn't disgusted with it. I definitely followed the Advent of Code "Brute Force until proven otherwise" approach. I considered doing it by only considering each leg of wire as two endpoints and calculating the intersections, but this was easier and more straightforward.
I also tried out Rust's type aliases to make things read a bit easier, which I'm really happy with.
Part 2 almost got me with a sneaky "Off by Two" error. I forgot to count the step off of the origin on both wires, leading me to be short by 2 on my final answer. A quick test case based on the examples provided showed I landed at 608 instead of 610 and I got suspicious.
Altogether much happier with this than I was last night. :)
/// Day 3: Crossed Wires/// /// Figure out which directions wires go and where they crossusestd::collections::HashSet;usestd::iter::FromIterator;usestd::fs;usestd::ops::Add;/// A coordinate is a 2D location (or Vector change!) with X and Y components#[derive(Debug,PartialEq,Eq,Hash,Copy,Clone)]structCoordinate{x:isize,y:isize,}/// You can Add Coordinates together with + to get a new oneimplAddforCoordinate{typeOutput=Self;fnadd(self,other:Self)->Self{Self{x:self.x+other.x,y:self.y+other.y,}}}implCoordinate{pubfnnew(x:isize,y:isize)->Self{Self{x,y}}}/// A Wire is a chain of coordinates that are electrically connectedtypeWire=Vec<Coordinate>;/// Moves are an ordered list of delta moves to make to form a wiretypeMoves=Vec<Coordinate>;/// Expects two lines of comma separated move strings, one for each wire./// The move strings are of the pattern [UDLR][0-9]+/// [UDLR]: Specifies whether the wire is going up, down, left or right/// [0-9]+: Specifies how many spaces that leg of the wire covers/// /// Returns both processed wiresfnparse_input()->(Wire,Wire){lettext=fs::read_to_string("data/day3.txt").unwrap();letlines:Vec<&str>=text.split("\n").collect();letmutwires=lines.into_iter().map(build_moves).map(make_wire);(wires.next().unwrap(),wires.next().unwrap())}/// Builds a list of Moves out of an input comma separated string as described/// above.fnbuild_moves(text_moves:&str)->Moves{letmutresults:Vec<Coordinate>=Vec::new();forstepintext_moves.split(","){let(direction,count_text)=step.split_at(1);letcount:usize=count_text.parse().unwrap();letmove_coord=ifdirection=="U"{Coordinate::new(0,1)}elseifdirection=="D"{Coordinate::new(0,-1)}elseifdirection=="L"{Coordinate::new(-1,0)}elseifdirection=="R"{Coordinate::new(1,0)}else{panic!("Weird step {}",direction);};for_in0..count{results.push(move_coord);}}results}/// Build a Wire out of relative Movesfnmake_wire(moves:Moves)->Wire{letmutcurrent=Coordinate{x:0,y:0};letmutresults:Wire=Vec::new();forstepinmoves{current=step+current;results.push(current);}results}/// Calculate a Coordinate's absolute distance from the originfnorigin_manhattan_distance(coord:&Coordinate)->usize{(coord.x.abs()+coord.y.abs())asusize}/// Given two Wires, find the location where they cross that is closest to the/// origin (which is where both wires start, and doesn't count as a cross)fnfind_closest_cross(a:&Wire,b:&Wire)->Coordinate{leta_set:HashSet<&Coordinate>=HashSet::from_iter(a.iter());letb_set:HashSet<&Coordinate>=HashSet::from_iter(b.iter());**a_set.intersection(&b_set).min_by_key(|c|origin_manhattan_distance(c)).unwrap()}/// Find the first occurrence of a Coordinate in a Wire (index-wise, but 1-based)fnfind_in_wire(wire:&Wire,target:&Coordinate)->usize{wire.iter().position(|e|e==target).unwrap()+1}/// Find the shortest distance you can travel on each wire (summed) before you/// hit a cross.fnshortest_cross_distance(a:&Wire,b:&Wire)->usize{leta_set:HashSet<&Coordinate>=HashSet::from_iter(a.iter());letb_set:HashSet<&Coordinate>=HashSet::from_iter(b.iter());a_set.intersection(&b_set).map(|c|find_in_wire(a,c)+find_in_wire(b,c)).min().unwrap()}/// Main Day 3 logic to solve the puzzlespubfnrun(){let(a,b)=parse_input();letclosest_cross=find_closest_cross(&a,&b);println!("Closest cross distance is {}",origin_manhattan_distance(&closest_cross));println!("Fewest combined steps: {}",shortest_cross_distance(&a,&b));}
I'm hosting my solutions on repl.it, and this one they don't let me finish calculating - I'm gonna have to look for some better optimization in order to let it finish within the resource boundary they set.
Anyway, I was able to handle the calculation locally and got the answers. I used the instructions to create sets of visited points, and then used set intersection to find the crossings. From there, it was finding either the minimum distance from the origin, or finding the minimum walk distance.
(nsaoc2019.day3(:require[clojure.string:asst][clojure.set:refer[intersection]]))(defnnext-step[last-posdirection](let[[xy]last-pos](condp=direction\U[x(incy)]\D[x(decy)]\R[(incx)y]\L[(decx)y])))(defnwalk"Provide the list of coords passed when moving a direction"[current-pathstep](let[direction(firststep)distance(inc(Integer/parseInt(st/join(reststep))))start-from(lastcurrent-path)](applyconjcurrent-path(rest(takedistance(iterate#(next-step%direction)start-from))))))(defnall-wire-coords[steps](loop[path[[00]]stepssteps](if(empty?steps)(restpath); remove initial [0 0] coordinate(recur(walkpath(firststeps))(reststeps)))))(defnp2019-03-part1[input](let[lines(st/split-linesinput)wires(map#(all-wire-coords(st/split%#","))lines)crosses(applyintersection(map#(into#{}%)wires))](->>crosses(map(fn[[xy]](+(Math/absx)(Math/absy))))(applymin))))(defnwalk-distance[wirescoord](let[first-wire(firstwires)second-wire(lastwires)](+(inc(.indexOffirst-wirecoord))(inc(.indexOfsecond-wirecoord)))))(defnp2019-03-part2[input](let[lines(st/split-linesinput)wires(map#(all-wire-coords(st/split%#","))lines)crosses(applyintersection(map#(into#{}%)wires))](->>crosses(map(fn[coord](walk-distancewirescoord)))(applymin))))
My brute force JS code. Still looking into a more optimized solution
constclosestIntersectionToOrigin=(wirePath1,wirePath2)=>{consttrace1=traceWire(wirePath1);consttrace2=traceWire(wirePath2);// find intersection of tracesconstintersects=trace1.filter(x=>trace2.includes(x));constdistanceArr=intersects.slice(1).map(x=>manhattanDistance([0,0],x.split(',').map(Number)));returnMath.min(...distanceArr);};constleastStepsIntersection=(wirePath1,wirePath2)=>{consttrace1=traceWire(wirePath1);consttrace2=traceWire(wirePath2);// find intersection of tracesconstintersects=trace1.filter(x=>trace2.includes(x));constdistanceArr=intersects.slice(1).map(x=>{consttotalSteps=trace2.findIndex(y=>y==x)+trace1.findIndex(y=>y==x);returntotalSteps;});returnMath.min(...distanceArr);};consttraceWire=(wirePath,acc=['0,0'])=>{for(leti=0;i<wirePath.length;i++){constmove=wirePath[i];constdirection=move[0];conststeps=Number(move.slice(1));conststart=acc[acc.length-1].split(',').map(Number);let[x,y]=start;conststepMap={R:()=>`${x},${++y}`,L:()=>`${x},${--y}`,U:()=>`${++x},${y}`,D:()=>`${--x},${y}`};for(letj=0;j<steps;j++){acc.push(stepMap[direction]());}}returnacc;};constmanhattanDistance=(pos1,pos2)=>Math.abs(pos2[0]-pos1[0])+Math.abs(pos2[1]-pos1[1]);if(!module.parent){constwire1=['R75','D30','R83','U83','L12','D49','R71','U7','L72'];constwire2=['U62','R66','U55','R34','D71','R55','D58','R83'];console.log(leastStepsIntersection(wire1,wire2));}module.exports={closestIntersectionToOrigin,leastStepsIntersection};
Solution with Swift. Took a long route and first tried with Int Array and failed. Went with Set second time and seems working. But its very slow even on my MacBook Pro. :(
Definitely looking forward to improve my solution by getting inspiration from others code :)
importCocoa/// --- Day 3: Crossed Wires ---funcgrid(_path:[String],_path2:[String]){structPoint:CustomStringConvertible,Equatable,Hashable{varx:Intvary:Intvardescription:String{get{return"X: \(self.x) Y: \(self.y)"}}mutatingfuncmove(indirection:Character?){switchdirection{case"L":x-=1case"R":x+=1case"U":y-=1case"D":y+=1default:fatalError()}}}funcfillPath(_path:[String])->Set<Point>{varvisted:Set<Point>=[]varcenter=Point.init(x:0,y:0)foraPathinpath{letdirection=aPath.firstletend=Int(aPath.dropFirst())??1(1...end).forEach{_incenter.move(in:direction)visted.insert(center)}}returnvisted}funcfillPath2(_path:[String])->Dictionary<Point,Int>{varvistedDict:Dictionary<Point,Int>=Dictionary<Point,Int>()varcenter=Point.init(x:0,y:0)varsteps:Int=0foraPathinpath{letdirection=aPath.firstletend=Int(aPath.dropFirst())??1(1...end).forEach{_insteps=steps+1center.move(in:direction)ifvistedDict[center]==nil{vistedDict[center]=steps}}}returnvistedDict}funcpartTwo(){letfirstVisited=fillPath2(path)letsecondVisited=fillPath2(path2)letcrossPoint=firstVisited.keys.filter(secondVisited.keys.contains)letdistance=crossPoint.map{firstVisited[$0]!+secondVisited[$0]!}.min()print(distance)}funcpartOne(){letfirstVisited=fillPath(path)letsecondVisited=fillPath(path2)letcrossPoints=firstVisited.intersection(secondVisited)// let crossPoints = firstVisited.filter(secondVisited.contains)//letcenter=Point.init(x:0,y:0)vardistances:[Int]=[]for(_,aPoint)incrossPoints.enumerated(){letdistance=abs(center.x-aPoint.x)+abs(center.y-aPoint.y)distances.append(distance)}dump(crossPoints)print(distances)print(distances.min())}partOne()partTwo()}letpath="""
R1003,U756,L776,U308,R718,D577,R902,D776,R760,U638,R289,D70,L885,U161,R807,D842,R175,D955,R643,U380,R329,U573,L944,D2,L807,D886,L549,U592,R152,D884,L761,D915,L726,D677,L417,D651,L108,D377,L699,D938,R555,D222,L689,D196,L454,U309,L470,D234,R198,U689,L996,U117,R208,D310,R572,D562,L207,U244,L769,U186,R153,D756,R97,D625,R686,U244,R348,U586,L385,D466,R483,U718,L892,D39,R692,U756,L724,U148,R70,U224,L837,D370,L309,U235,R382,D579,R404,D146,R6,U584,L840,D863,R942,U646,R146,D618,L12,U210,R126,U163,R931,D661,L710,D883,L686,D688,L148,D19,R703,U530,R889,U186,R779,D503,R417,U272,R541,U21,L562,D10,L349,U998,R69,D65,R560,D585,L949,D372,L110,D865,R212,U56,L936,U957,L88,U612,R927,U642,R416,U348,L541,D416,L808,D759,R449,D6,L517,D4,R494,D143,L536,U341,R394,U179,L22,D680,L138,U249,L285,U879,L717,U756,L313,U222,R823,D208,L134,U984,R282,U635,R207,D63,L416,U511,L179,D582,L651,U932,R646,U378,R263,U138,L920,U523,L859,D556,L277,D518,R489,U561,L457,D297,R72,U920,L583,U23,L395,D844,R776,D552,L55,D500,R111,U409,R685,D427,R275,U739,R181,U333,L215,U808,R341,D537,R336,U230,R247,U748,R846,U404,R850,D493,R891,U176,L744,U585,L987,D849,R271,D848,L555,U801,R316,U753,L390,U97,L128,U45,R706,U35,L928,U913,R537,D512,R152,D410,R76,D209,R183,U941,R289,U632,L923,D190,R488,D934,R442,D303,R178,D250,R204,U247,R707,U77,R428,D701,R386,U110,R641,U925,R703,D387,L946,U415,R461,D123,L214,U236,L959,U517,R957,D524,R812,D668,R369,U340,L606,D503,R755,U390,R142,D921,L976,D36,L965,D450,L722,D224,L303,U705,L584
"""letpath2="""
L993,U810,L931,D139,R114,D77,L75,U715,R540,D994,L866,U461,R340,D179,R314,D423,R629,D8,L692,U446,L88,D132,L128,U934,L465,D58,L696,D883,L955,D565,R424,U286,R403,U57,L627,D930,R887,D941,L306,D951,R918,U587,R939,U821,L65,D18,L987,D707,L360,D54,L932,U366,R625,U609,R173,D637,R661,U888,L68,U962,R270,U369,R780,U845,L813,U481,R66,D182,R420,U605,R880,D276,L6,D529,R883,U189,R380,D472,R30,U35,L510,D844,L146,U875,R152,U545,R274,U920,R432,U814,R583,D559,L820,U135,L353,U975,L103,U615,R401,U692,L676,D781,R551,D985,L317,U836,R115,D216,L967,U286,R681,U144,L354,U678,L893,D487,R664,D185,R787,D909,L582,D283,L519,D893,L56,U768,L345,D992,L248,U439,R573,D98,L390,D43,L470,D435,R176,U468,R688,U388,L377,U800,R187,U641,L268,U857,L716,D179,R212,U196,L342,U731,R261,D92,R183,D623,L589,D215,L966,U878,L784,U740,R823,D99,L167,D992,R414,U22,L27,U390,R286,D744,L360,U554,L756,U715,R939,D806,R279,U292,L960,U633,L428,U949,R90,D321,R749,U395,L392,U348,L33,D757,R289,D367,L562,D668,L79,D193,L991,D705,L562,U25,R146,D34,R325,U203,R403,D714,R607,U72,L444,D76,R267,U924,R289,U962,L159,U726,L57,D540,R299,U343,R936,U90,L311,U243,L415,D426,L936,D570,L539,D731,R367,D374,L56,D251,L265,U65,L14,D882,L956,U88,R688,D34,R866,U777,R342,D270,L344,D953,L438,D855,L587,U320,L953,D945,L473,U559,L487,D602,R255,U871,L854,U45,R705,D247,R955,U885,R657,D664,L360,D764,L549,D676,R85,U189,L951,D922,R511,D429,R37,U11,R821,U984,R825,U874,R753,D524,L537,U618,L919,D597,L364,D231,L258,U818,R406,D208,R214,U530,R261
"""grid(path.components(separatedBy:","),path2.components(separatedBy:","));
I way over thought this last night, and had a solution that worked but it was gnarly. Refactored this morning:
defformat_coords(coords):return[(val[0],int(val[1:]))forvalincoords.split(",")]DIRECTIONS={"R":(1,0),"L":(-1,0),"U":(0,1),"D":(0,-1)}deffind_points(paths):points={}x=0y=0steps=0fordirection,distanceinpaths:forpointinrange(distance):x_change,y_change=DIRECTIONS[direction]x+=x_changey+=y_changesteps+=1points[(x,y)]=stepsreturnpointsdefget_intersections(points1,points2):returnset(points1.keys()).intersection(set(points2.keys()))defget_manhattan_distances(points):return[abs(x)+abs(y)forx,yinpoints]defget_least_steps(intersections,points1,points2):return[points1[point]+points2[point]forpointinintersections]withopen("input.txt")as_file:paths1=format_coords(_file.readline())points1=find_points(paths1)paths2=format_coords(_file.readline())points2=find_points(paths2)intersections=get_intersections(points1,points2)# Part 1
print(min(get_manhattan_distances(intersections)))# Part 2
print(min(get_least_steps(intersections,points1,points2)))
Woooooo, finally got this one! Took me 2 days, but dangit I solved it on my own and I feel super pleased and relieved. lol
What's lame is I basically had the right idea yesterday, but wasn't adding the absolute value of the coordinates, so was getting the wrong values back and thought my whole solution was wrong. 😒 So I rage deleted everything last night, and rewrote it all today and got it working! 😊
Got to use a set for the first real time, which worked out nicely! I figured I could plot out each coordinate visited by the first wire, and store those in a set (since where a wire crosses itself doesn't matter). Then, for the second wire, I go through and just check to see if the set contains that coordinate already, and if so, store that in it's own array to check over at the end. Ran pretty quickly, though I'm sure I could factor the code to be a bit more function-oriented than I did. Just wanted it to work! lol
Thankfully, part 2 didn't take me all that long...just refactoring my first path run to count the steps taken so far and figure out how/where to store them, then adding it as an extra value onto the end of my crossed points array. Easy! (Ending up reading my coords and counter as a string, so that comparisons were easier to do.)
I tried to draw the full layout represented by my input as ascii, but it turned out to be a 200MB file. Imagemagick filled my hard drive trying to parse it.
I'm using AoC this year to learn Python. Last year I used it to learn nodejs.
Day 3 was a doozy for me, partly because I started it at 11pm (I'm on American Central Time), but partly because I overthought the problem and thought I would map the whole thing as a 2D array. After screwing my head on a little bit more, I went with simply tracking the path of the wire with x/y tuples, then finding the intersections between the two wires. Manhattan distance was baked into each tuple (just add the absolute values of x and y together and voila).
For my first crack at Part One, I originally used sets. When I discovered Part Two, I just had to change the sets to lists and then I got path distance for free.
defmove(direction,coord,path):x=coord['x']y=coord['y']# remove any \n if it exists
dir=direction.rstrip()amt=int(dir[1:len(dir)])ifdir.startswith("R"):foriinrange(x+1,x+amt+1):path.append((i,y))coord['x']+=amtelifdir.startswith("L"):foriinrange(x-1,x-amt-1,-1):path.append((i,y))coord['x']-=amtelifdir.startswith("U"):foriinrange(y+1,y+amt+1):path.append((x,i))coord['y']+=amtelifdir.startswith("D"):foriinrange(y-1,y-amt-1,-1):path.append((x,i))coord['y']-=amtelse:# Fortunately we don't have any of these
print("Error! Wasn't expecting that!")returnpathdeffindDistancesToCommonPoints(path,intersections):positions={}previousCoord=(0,0)cumulativeDistance=0foriinrange(0,len(path)):cumulativeDistance+=calculateDistance(previousCoord,path[i])ifpath[i]inintersectionsandpath[i]notinpositions:positions[path[i]]=cumulativeDistance# make the current coord the previous one for the next iteration
previousCoord=path[i]returnpositionsdefcalculateDistance(point1,point2):returnabs(point1[0]-point2[0])+abs(point1[1]-point2[1])# Initialize: open file, put both wire directions into lists
withopen('day03.txt')asf:wireOneDirections=f.readline().split(",")wireTwoDirections=f.readline().split(",")# Setup: get the paths that the wires take, put the coordinate points into a trackable list
wireCoord={'x':0,'y':0}firstpath=[]foriinrange(0,len(wireOneDirections)):move(wireOneDirections[i],wireCoord,firstpath)wireCoord={'x':0,'y':0}secondpath=[]foriinrange(0,len(wireTwoDirections)):move(wireTwoDirections[i],wireCoord,secondpath)# Part One: find the intersection point closest to the central port (which is at (0, 0))
intersections=set(firstpath).intersection(set(secondpath))# (Initialize with large number...one that will be larger than any of the numbers we might encounter)
least=1000000fortupinintersections:sum=abs(tup[0])+abs(tup[1])ifsum<least:least=sumprint("Part One: %i"%least)# Part Two: find the fewest combined steps the wires must take to reach an intersection
distancesOne=findDistancesToCommonPoints(firstpath,intersections)distancesTwo=findDistancesToCommonPoints(secondpath,intersections)combinedDistances=[]forkeyindistancesOne:combinedDistances.append(distancesOne[key]+distancesTwo[key])print("Part Two: %i"%min(combinedDistances))
Here's my solution with Clojure. It is generating all the points in the lines, which seems a bit brute-force, but at least on my machine it works swiftly;)
Wow, your solution is so compact!
Mine is very verbose, and I am not done with part 2 yet! (will try tonight, but it's hard when working 11h a day...).
Maybe you could have a look on my solution and give me some pointers on how I could get better at Clojure?
Can somebody help with undesrstanding the premise.
I am a little bit confused from the description of part 1. What should be considered the central port?
PHP, because I'm having to learn it at my internship at the moment. Something isn't right here, because it takes several minutes to run, but at least the solution appears eventually.
If you’re enumerating every point you’re operating with two lists of hundreds of thousands of items. Worse, I don’t think there’s a way around a cartesian join of the two sets (potentially squaring your already hideous number of data).
Running into performance problems is expected, driving the solution into minutes if you’re not careful (I crashed my jvm and lost a few minutes manually killing it and my ide as they consumed as much processor and memory power as they could)
I was able to improve the speed hugely with just a little tweaking, from over 7 minutes to around 0.1 seconds!
So, I see everyone did it like I did - recording all visited nodes on the grid and checking for intersections. Now, without considering part 2, is there a smarter way? I'm pretty sure there has to be.
You can generate segments with only the start and end points and check where they intersect, which would require less memory. But the math is more complicated and I'm not sure it's faster, since you can't use a hash table to find the intersections.
This is how did it (I assumed the memory requirement of enumerating all of the visited nodes in the grid would be too much).
buuut the code got really messy and I don't know if there's a cleaner way to do it.
It's so long I don't want to reproduce it here 😱 github.com/MustafaHaddara/advent-o...
The only thing I can see right off the bat is that you’re checking for vertical/horizontal via start/end points, but you could have kept that information (UDLR) alongside the line segment definition. Other than that it makes sense, and other than being too deeply nested for my compulsive refactoring instinct, it doesn’t look much longer than my full-point enumerator.
(If you use a linked list, it doesn’t take more than 30 seconds or so for part b)
d'oh that would have made things much more readable.
I was complaining to a coworker that I've done collision detection for 2d games before, and this felt similar, but is sort of like "hard mode" because I didn't necessarily know which endpoint of each line was on the left/right or top/bottom. Keeping that info would have made things more straightforward!
It’s why I love working with people who know the same codebase as me! When you PR or rubber duck, you often get some perspective that makes the “ugly” bits fall into place that you were too close to see!
Not sure if it's the most efficient way of doing it, but this is how I solved it
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
intersectionfunction. 12 variables in scope. The horror!I still have nightmares from previous year's assignment based on coordinates, but luckily this wasn't as bad. Here's my solution for part two in Elixir:
Check part one here
Took me an extra day to clean it up so I wasn't disgusted with it. I definitely followed the Advent of Code "Brute Force until proven otherwise" approach. I considered doing it by only considering each leg of wire as two endpoints and calculating the intersections, but this was easier and more straightforward.
I also tried out Rust's type aliases to make things read a bit easier, which I'm really happy with.
Part 2 almost got me with a sneaky "Off by Two" error. I forgot to count the step off of the origin on both wires, leading me to be short by 2 on my final answer. A quick test case based on the examples provided showed I landed at 608 instead of 610 and I got suspicious.
Altogether much happier with this than I was last night. :)
Woo! Day 3 is in the bag. :D
I'm hosting my solutions on repl.it, and this one they don't let me finish calculating - I'm gonna have to look for some better optimization in order to let it finish within the resource boundary they set.
Anyway, I was able to handle the calculation locally and got the answers. I used the instructions to create sets of visited points, and then used set intersection to find the crossings. From there, it was finding either the minimum distance from the origin, or finding the minimum walk distance.
My brute force JS code. Still looking into a more optimized solution
Scala! I'm slowly falling in love with this language.
Solution with Swift. Took a long route and first tried with Int Array and failed. Went with Set second time and seems working. But its very slow even on my MacBook Pro. :(
Definitely looking forward to improve my solution by getting inspiration from others code :)
More browser antics. I think I can refactor this, and possibly make it faster, but it's fast enough.
C++
Part 1
Part 2
Beautiful code Sr. Really straight forward and easy to read and understand.
I way over thought this last night, and had a solution that worked but it was gnarly. Refactored this morning:
Woooooo, finally got this one! Took me 2 days, but dangit I solved it on my own and I feel super pleased and relieved. lol
What's lame is I basically had the right idea yesterday, but wasn't adding the absolute value of the coordinates, so was getting the wrong values back and thought my whole solution was wrong. 😒 So I rage deleted everything last night, and rewrote it all today and got it working! 😊
Got to use a set for the first real time, which worked out nicely! I figured I could plot out each coordinate visited by the first wire, and store those in a set (since where a wire crosses itself doesn't matter). Then, for the second wire, I go through and just check to see if the set contains that coordinate already, and if so, store that in it's own array to check over at the end. Ran pretty quickly, though I'm sure I could factor the code to be a bit more function-oriented than I did. Just wanted it to work! lol
Thankfully, part 2 didn't take me all that long...just refactoring my first path run to count the steps taken so far and figure out how/where to store them, then adding it as an extra value onto the end of my crossed points array. Easy! (Ending up reading my coords and counter as a string, so that comparisons were easier to do.)
JavaScript:
Kotlin Solution! No monads today, sadly, but I pulled in Java's LinkedList implementation for memory efficiency.
I tried to draw the full layout represented by my input as ascii, but it turned out to be a 200MB file. Imagemagick filled my hard drive trying to parse it.
Day 3 in two (convoluted) parts:
Day 3 part 1
Day 3 part 2
Both Clojure
I'm using AoC this year to learn Python. Last year I used it to learn nodejs.
Day 3 was a doozy for me, partly because I started it at 11pm (I'm on American Central Time), but partly because I overthought the problem and thought I would map the whole thing as a 2D array. After screwing my head on a little bit more, I went with simply tracking the path of the wire with x/y tuples, then finding the intersections between the two wires. Manhattan distance was baked into each tuple (just add the absolute values of x and y together and voila).
For my first crack at Part One, I originally used sets. When I discovered Part Two, I just had to change the sets to lists and then I got path distance for free.
My ugly solution in C , after hours unfortunately :(
It took me quite a bit of time to solve both problems, but I believe I've implemented a relatively optimized solution:
Here's my solution with Clojure. It is generating all the points in the lines, which seems a bit brute-force, but at least on my machine it works swiftly;)
I'm also posting my solutions to github.
Wow, your solution is so compact!
Mine is very verbose, and I am not done with part 2 yet! (will try tonight, but it's hard when working 11h a day...).
Maybe you could have a look on my solution and give me some pointers on how I could get better at Clojure?
gitlab.com/simonced/advent-of-code...
I am just beginning and I enjoy the language very much :).
Can somebody help with undesrstanding the premise.
I am a little bit confused from the description of part 1. What should be considered the central port?
Well, technically it can be anything you want!
However, since the answer is the distance from the "center port", you might as well make things easier on yourself by declaring that it is
(0,0)Oh, ok. Thank you!