It is another tool in the box, and sometimes even the right tool. But regex is a sub-optimal general solution to what is often a quite specific task. One of my passions in programming is to show that real parsers are almost always better in the long run, and they're not hard to write.
Here's a recording of a talk I did at the Edinburgh Kotlin user's group last year on the subject: vimeo.com/393132096
Part 1 Python
New to coding and behind in the calendar but this one looked easy overall.
with open ('input.txt') as inp:
EW = 0
NS = 0
dir = 90
for line in inp:
action = line[0]
num = int(line[1:])
if action == "F" and dir == 90 or action == "E":
EW += num
elif action == "F" and dir == 180 or action == "S":
NS -= num
elif action == "F" and dir == 270 or action == "W":
EW -= num
elif action == "F" and dir == 0 or action == "N":
NS += num
elif action == "L":
dir -= num
if dir == 360 or dir == -360:
dir = 0
if dir == -90:
dir = 270
if dir == -180 or dir == 540:
dir = 180
if dir == -270 or dir == 450:
dir = 90
elif action == "R":
dir += num
if dir == 360 or dir == -360:
dir = 0
if dir == -90:
dir = 270
if dir == -180 or dir == 540:
dir = 180
if dir == -270 or dir == 450:
dir = 90
print(f"Manhatten Distance: {abs(NS)+ abs(EW)}")
not sure how to get syntax highlighting to show here
Part 2
with open ('input.txt') as inp:
ship_ew = 0
ship_ns = 0
way_ew = 10
way_ns = 1
for line in inp:
action = line[0]
num = int(line[1:])
if action == "F":
ship_ns += (way_ns * num)
ship_ew += (way_ew * num)
elif action == "N":
way_ns += num
elif action == "S":
way_ns -= num
elif action == "E":
way_ew += num
elif action == "W":
way_ew -= num
elif action == "L" and num == 90 or action == "R" and num == 270:
way_ns, way_ew = way_ew, -way_ns
elif action == "L" and num == 270 or action == "R" and num ==90:
way_ns, way_ew = -way_ew, way_ns
elif action == "L" and num == 180 or action == "R" and num == 180:
way_ns = -way_ns
way_ew = -way_ew
print(f"Manhattan Distance: {abs(ship_ns)+ abs(ship_ew)}")
Nice! I like how you folded the absolute directions and the forward commands into one action with checks on the current direction. Look into the % (modulo) operator for handling the circular arithmetic around the rotation additions - in short (dir + num) % 360 for right turns and (dir + 360 - num) % 360 for left.
There are (at least) two ways to "model" the solution: polar coordinates or vector/gonio math. Here is a Ruby OOP solution using the latter:
require'benchmark'classShipattr_reader:positiondefinitializeself.facing=90self.position=Position.new(0,0)self.waypoint=Waypoint.newenddefsail!(instruction)caseinstruction.actionwhen'N'position.translate!(0,-instruction.value)when'S'position.translate!(0,instruction.value)when'E'position.translate!(instruction.value,0)when'W'position.translate!(-instruction.value,0)when'L'self.facing=(self.facing-instruction.value)%360when'R'self.facing=(self.facing+instruction.value)%360when'F'direction=%w[N E S W][facing/90]sail!instruction.with_action(direction)# input only contains 90 180 270 so no need for# SOS Castoa (gonio).endenddefsail_with_waypoint!(instruction)if%w[N S E W L R].include?(instruction.action)waypoint.sail!instructionreturnenddx,dy=waypoint.position.difference(Position.new(0,0))self.position.translate!(dx*instruction.value,dy*instruction.value)endprivateattr_accessor:facing,:waypointattr_writer:positionendclassWaypointattr_reader:positiondefinitializeself.position=Position.new(10,-1)enddefsail!(instruction)caseinstruction.actionwhen'N'position.translate!(0,-instruction.value)when'S'position.translate!(0,instruction.value)when'E'position.translate!(instruction.value,0)when'W'position.translate!(-instruction.value,0)when'L'theta=-(instruction.value/180.to_f*Math::PI)self.position=Position.new((position.x*Math.cos(theta)-position.y*Math.sin(theta)).round,(position.x*Math.sin(theta)+position.y*Math.cos(theta)).round)when'R'theta=instruction.value/180.to_f*Math::PIself.position=Position.new((position.x*Math.cos(theta)-position.y*Math.sin(theta)).round,(position.x*Math.sin(theta)+position.y*Math.cos(theta)).round)endendprivateattr_accessor:facingattr_writer:positionendclassInstructionattr_reader:action,:valuedefinitialize(action,value)self.action=actionself.value=value.to_ienddefwith_action(new_action)Instruction.new(new_action,value)endprivateattr_writer:action,:valueendclassPositionattr_reader:x,:ydefinitialize(x,y)self.x=xself.y=yenddeftranslate!(x,y)self.x+=xself.y+=yselfenddefdistance(other)difference(other).map(&:abs).sumenddefdifference(other)[x-other.x,y-other.y]endprivateattr_writer:x,:yendmoduleNavigationInstructionsdefself.from_lines(lines)lines.mapdo|line|line=line.chompInstruction.new(line[0],line[1..])endendenddeftrack(ship)original=ship.position.dupyieldoriginal.distance(ship.position)endsource='input.txt'instructions=NavigationInstructions.from_lines(File.readlines(source))verbose=falseBenchmark.bmbmdo|x|x.report(:part_1)doship=Ship.newdistance=track(ship)doinstructions.eachdo|instruction|ship.sail!instructionputs"[ahoy] #{instruction.action} by #{instruction.value}: #{ship.position.x}, #{ship.position.y}"ifverboseendendputsdistanceendx.report(:part_2)doship=Ship.newdistance=track(ship)doinstructions.eachdo|instruction|ship.sail_with_waypoint!instructionputs"[ahoy] #{instruction.action} by #{instruction.value}: #{ship.position.x}, #{ship.position.y}"ifverboseendendputsdistanceendend
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.
Not too bad! I had an issue with the rotation in part 2, and I ended up writing so. many. tests. to find it. Which totally payed off!
Day12.h:
#ifndef AOC2020_DAY12_H
#define AOC2020_DAY12_H
#include <stdlib.h>
/// Possible actions the boat can taketypedefenum{AC_NORTH,AC_EAST,AC_SOUTH,AC_WEST,AC_LEFT,AC_RIGHT,AC_FORWARD,AC_COUNT}Action;/// String representation of actions for printingstaticchar*actions[AC_COUNT]={"North","East","South","West","Left","Right","Forward"};/// Figure out the Manhattan Distance after processing the instructions/// in `filename`.intpart1(constchar*filename);/// The state of the boat for part 2typedefstruct{intx;///< The E/W location of the boat (E+)inty;///< The N/S location of the boat (N+)intwx;///< The E/W location of the waypointintwy;///< The N/S location of the waypoint}ShipState;/// Move the ship or waypoint based on the action requested////// AC_NORTH: move the waypoint north/// AC_EAST: move the waypoint east/// AC_SOUTH: move the waypoint south/// AC_WEST: move the waypoint west/// AC_LEFT: rotate the waypoint left `amount` degrees about the ship/// AC_RIGHT: rotate the waypoint right `amount` degrees about the ship/// AC_FORWARd: move the ship to the waypoint `amount` times (waypoint/// always relocates so its final position relative to/// the ship is the same.)ShipStatemove(ShipStatecurrent,Actionaction,intamount);/// Following the new rules about waypoints followed in `move`, /// what is the Manhattan distance from the origin that the ship/// achieves by following the instructions in `filename`?intpart2(constchar*filename);/// Run both partsintday12(void);#endif
Day12.c:
#include "Day12.h"
#include <stdio.h>
#include "parsing.h"
/// Direction enum for part 1typedefenum{DIR_NORTH,DIR_EAST,DIR_SOUTH,DIR_WEST,}Direction;/// An instruction is one command to move the ship or waypointtypedefstruct{Actionaction;///< The `Action` to performintamount;///< A measure of how much to perform that action}Instruction;/// Parse the input file, which has lines of 'A123' where 'A' is a /// character specifying the action to take and '123' is some 1-3 digit/// number that specifies the "amount" to do the action.staticInstruction*parse(constchar*filename,int*count){FILE*fp;fp=fopen(filename,"r");if(fp==NULL){printf("Couldn't open file.\n");exit(EXIT_FAILURE);}*count=count_lines(fp);Instruction*instructions=(Instruction*)malloc(sizeof(Instruction)**count);for(inti=0;i<*count;i++){charc=0;intarg=0;fscanf(fp,"%c%d\n",&c,&arg);Actionaction;switch(c){case'N':action=AC_NORTH;break;case'E':action=AC_EAST;break;case'S':action=AC_SOUTH;break;case'W':action=AC_WEST;break;case'L':action=AC_LEFT;break;case'R':action=AC_RIGHT;break;case'F':action=AC_FORWARD;break;default:printf("Unrecognized action: %c\n",c);exit(EXIT_FAILURE);}instructions[i]=(Instruction){.action=action,.amount=arg};}fclose(fp);returninstructions;}/// Calculate the new direction based on an orientation and an amount/// to turn.staticDirectionturn(Directioncurrent,Actionaction,intamount){introtation=action==AC_LEFT?-1:1;intnew_dir=((int)current+(amount/90)*rotation)%4;if(new_dir<0)new_dir+=4;return(Direction)new_dir;}intpart1(constchar*filename){intcount;Instruction*instructions=parse(filename,&count);intx=0;inty=0;Directiondirection=DIR_EAST;for(inti=0;i<count;i++){Instructioninst=instructions[i];#ifdef STEPTHRU
printf("<%d, %d> Facing %d.\n",x,y,direction);printf("%d: %d\n",inst.action,inst.amount);getc(stdin);#endif
switch(inst.action){caseAC_NORTH:y+=inst.amount;break;caseAC_EAST:x+=inst.amount;break;caseAC_SOUTH:y-=inst.amount;break;caseAC_WEST:x-=inst.amount;break;caseAC_LEFT:direction=turn(direction,AC_LEFT,inst.amount);break;caseAC_RIGHT:direction=turn(direction,AC_RIGHT,inst.amount);break;caseAC_FORWARD:{switch(direction){caseDIR_NORTH:y+=inst.amount;break;caseDIR_EAST:x+=inst.amount;break;caseDIR_SOUTH:y-=inst.amount;break;caseDIR_WEST:x-=inst.amount;break;default:printf("Unrecognized direction state: %d\n",direction);exit(EXIT_FAILURE);};break;}default:printf("Unrecognized action. %d\n",inst.action);exit(EXIT_FAILURE);}}returnabs(x)+abs(y);}ShipStatemove(ShipStatecurrent,Actionaction,intamount){ShipStatenew=current;switch(action){caseAC_NORTH:new.wy+=amount;break;caseAC_EAST:new.wx+=amount;break;caseAC_SOUTH:new.wy-=amount;break;caseAC_WEST:new.wx-=amount;break;caseAC_LEFT:{for(intj=0;j<amount/90;j++){inttmp=new.wx;new.wx=new.wy*-1;new.wy=tmp;}};break;caseAC_RIGHT:{for(intj=0;j<amount/90;j++){inttmp=new.wx;new.wx=new.wy;new.wy=tmp*-1;}};break;caseAC_FORWARD:{new.x+=new.wx*amount;new.y+=new.wy*amount;};break;default:printf("Unrecognized action. %d\n",action);exit(EXIT_FAILURE);}returnnew;}intpart2(constchar*filename){intcount;Instruction*instructions=parse(filename,&count);ShipStatestate={0,0,10,1};for(inti=0;i<count;i++){Instructioninst=instructions[i];#ifdef STEPTHRU
printf("<%d, %d> wpt <%d, %d>.\n",state.x,state.y,state.wx,state.wy);printf("%s: %d\n",actions[inst.action],inst.amount);getc(stdin);#endif
state=move(state,inst.action,inst.amount);}returnabs(state.x)+abs(state.y);}intday12(){printf("====== Day 12 ======\n");printf("Part 1: %d\n",part1("data/day12.txt"));printf("Part 2: %d\n",part2("data/day12.txt"));returnEXIT_SUCCESS;}
useaoc_runner_derive::{aoc,aoc_generator};usestd::cmp::Ordering;#[derive(Debug)]enumDirection{East,West,North,South,Left,Right,Forward,}structCommand{direction:Direction,measure:usize,}#[aoc_generator(day12)]fnparse_input_day12(input:&str)->Vec<Command>{input.lines().map(|l|Command{direction:matchl.chars().next(){Some('F')=>Direction::Forward,Some('N')=>Direction::North,Some('S')=>Direction::South,Some('E')=>Direction::East,Some('W')=>Direction::West,Some('L')=>Direction::Left,Some('R')=>Direction::Right,_=>panic!("Invalid direction!"),},measure:str::parse(&l[1..]).expect("Unable to parse measure"),}).collect()}fnmanhattan_distance(point_1:&(isize,isize),point_2:&(isize,isize))->usize{((point_1.0-point_2.0).abs()+(point_1.1-point_2.1).abs())asusize}fnmove_ship(position:&mut(isize,isize),direction:&Direction,distance:usize){match*direction{Direction::North=>{position.1+=distanceasisize;}Direction::South=>{position.1-=distanceasisize;}Direction::East=>{position.0-=distanceasisize;}Direction::West=>{position.0+=distanceasisize;}_=>panic!("cannot move in specified Direction {:?}",direction),}}fnangle_lookup(direction:&Direction)->usize{matchdirection{Direction::North=>270,Direction::South=>90,Direction::East=>0,Direction::West=>180,_=>panic!("not a cardinal direction"),}}fndirection_lookup(angle:usize)->Direction{matchangle{0=>Direction::East,90=>Direction::South,180=>Direction::West,270=>Direction::North,_=>panic!("invalid angle"),}}fnturn_ship(orientation:&mutDirection,command:&Command){letmutdegree:isize=matchcommand.direction{Direction::Left=>-1*command.measureasisize,Direction::Right=>command.measureasisize,_=>panic!("cannot turn with specified Direction {:?}",command.direction),};letmutcurrent_angle=angle_lookup(orientation)asisize;whiledegree!=0{ifdegree<0{current_angle-=90;degree+=90;}else{current_angle+=90;degree-=90;}}letfinal_angle:usize=matchcurrent_angle.cmp(&0){Ordering::Less=>(current_angle%360)+360,_=>current_angle%360,}asusize;*orientation=direction_lookup(final_angle);}#[aoc(day12,part1)]fnget_travel_distance(input:&Vec<Command>)->usize{letorigin=(0,0);letmutposition=(0,0);letmutorientation=Direction::East;input.iter().for_each(|cmd|matchcmd.direction{Direction::North|Direction::South|Direction::East|Direction::West=>{move_ship(&mutposition,&cmd.direction,cmd.measure);}Direction::Forward=>{move_ship(&mutposition,&orientation,cmd.measure);}Direction::Left|Direction::Right=>{turn_ship(&mutorientation,&cmd);}});manhattan_distance(&origin,&position)}fnmove_waypoint(waypoint:&mut(isize,isize),cmd:&Command){matchcmd.direction{Direction::East=>waypoint.0+=cmd.measureasisize,Direction::West=>waypoint.0-=cmd.measureasisize,Direction::North=>waypoint.1+=cmd.measureasisize,Direction::South=>waypoint.1-=cmd.measureasisize,_=>panic!("Not a move Direction"),}}fnrotate_waypoint(waypoint:&mut(isize,isize),cmd:&Command){letangle=matchcmd.direction{Direction::Left=>((-1*cmd.measureasisize)+360)asusize,Direction::Right=>cmd.measure,_=>panic!("Not a rotational direction"),};matchangle{0=>(),270=>{letnew_x=-1*waypoint.1;letnew_y=waypoint.0;waypoint.0=new_x;waypoint.1=new_y;}180=>{waypoint.0=-1*waypoint.0;waypoint.1=-1*waypoint.1;}90=>{letnew_x=waypoint.1;letnew_y=-1*waypoint.0;waypoint.0=new_x;waypoint.1=new_y;}_=>panic!("invalid angle"),}}fnmove_ship_toward_waypoint(position:&mut(isize,isize),waypoint:&(isize,isize),times:usize,){for_in0..times{position.0+=waypoint.0;position.1+=waypoint.1;}}#[aoc(day12,part2)]fnget_travel_waypoint_distance(input:&Vec<Command>)->usize{letorigin=(0,0);letmutwaypoint=(10,1);letmutposition=(0,0);input.iter().for_each(|cmd|{matchcmd.direction{Direction::North|Direction::South|Direction::East|Direction::West=>{move_waypoint(&mutwaypoint,cmd);}Direction::Forward=>{move_ship_toward_waypoint(&mutposition,&waypoint,cmd.measure);}Direction::Left|Direction::Right=>rotate_waypoint(&mutwaypoint,&cmd),}});manhattan_distance(&origin,&position)}
Warning, lots of code today! I've been making an effort to model my solutions in ways that do not require special branching, or separate solutions for the 2 parts. Today was a fun one, and I think I came up with a good design, even if it's a little verbose!
At this point I think my enterprise development roots are showing. I've got inheritance, interfaces, strategies, factories, and even a DI container in my overall 2020 codebase 🤣
publicclassWaypointFerry:FerryBase{PointWaypoint=newPoint(0,0);publicWaypointFerry(Pointorigin,Pointwaypoint):base(origin){Waypoint=waypoint;}protectedoverridevoidMove(NavInstructioninstruction){if(instruction.Actionis'L'or'R'){Rotate(instruction.Action,instruction.Value);return;}if(instruction.Actionis'F'){for(inti=0;i<instruction.Value;i++){Location=newPoint(Location.X+Waypoint.X,Location.Y+Waypoint.Y);}return;}Waypoint=Move(Waypoint,GetDirection(instruction),instruction.Value);}protectedoverridevoidRotate(charturnDirection)=>Waypoint=turnDirectionswitch{'L'=>newPoint(-1*Waypoint.Y,Waypoint.X),'R'=>newPoint(Waypoint.Y,-1*Waypoint.X),_=>thrownewException($"turnDirection not supported: {turnDirection}")};}
Fun today, although solved part 1 before going out this morning, only to realise I needed slighty different function for part 2 :-) In the end just went with 2, mostly same, functions, as did not have the will power to generalize!
It's nice now that I'm starting to have a litlte library of "AOC" functions that I can call upon.
-- we need to accumulate, rather than simply foldfoldl'fz[]=zfoldl'fz(x:xs)=letz'=z`f`xinseqz'$foldl'fz'xs----------------------------------------------dataMove=N|E|S|W|F|B|L|Rderiving(Show,Eq,Enum)dataShip=Ship{--update :: Ship -> Move -> Ship,way::(Int,Int),northSouth::Int,eastWest::Int}derivingShow-- Simple parserlexer=Token.makeTokenParser(TP.emptyDef{Token.reservedNames=["nop","acc","jmp"]})reserved=Token.reservedlexer-- op codeinteger=Token.integerlexer-- integerwhiteSpace=Token.whiteSpacelexer-- whitespace-- parse individual opcodepMoveOp::TP.Parser(Int->(Move,Int))pMoveOp=TP.choice[(N,)<$TP.char'N',(S,)<$TP.char'S',(W,)<$TP.char'W',(E,)<$TP.char'E',(F,)<$TP.char'F',(B,)<$TP.char'B',(L,)<$TP.char'L',(R,)<$TP.char'R']-- parse an individual instructionrpMove::TP.Parser(Move,Int)pMove=pMoveOp<*>(fromIntegral<$>integer)-- parse all opsparseMoves::String->[(Move,Int)]parseMoves=either(error.show)id.TP.parse(TP.many1(whiteSpace>>pMove))""------moveship(m,i)=auxmwhereaux=\caseN->ship{northSouth=northSouthship+i}S->ship{northSouth=northSouthship-i}E->ship{eastWest=eastWestship+i}W->ship{eastWest=eastWestship-i}L|i==90->ship{way=let(dx,dy)=wayshipin(-dy,dx)}|i==180->ship{way=let(dx,dy)=wayshipin(-dx,-dy)}|i==270->ship{way=let(dx,dy)=wayshipin(dy,-dx)}R|i==90->ship{way=let(dx,dy)=wayshipin(dy,-dx)}|i==180->ship{way=let(dx,dy)=wayshipin(-dx,-dy)}|i==270->ship{way=let(dx,dy)=wayshipin(-dy,dx)}F->let(ns,ew,(dx,dy))=(northSouthship,eastWestship,wayship)inship{northSouth=ns+i*dy,eastWest=ew+i*dx}move'ship(m,i)=auxmwhereaux=\caseN->ship{way=let(dx,dy)=wayshipin(dx,dy+i)}S->ship{way=let(dx,dy)=wayshipin(dx,dy-i)}E->ship{way=let(dx,dy)=wayshipin(dx+i,dy)}W->ship{way=let(dx,dy)=wayshipin(dx-i,dy)}L|i==90->ship{way=let(dx,dy)=wayshipin(-dy,dx)}|i==180->ship{way=let(dx,dy)=wayshipin(-dx,-dy)}|i==270->ship{way=let(dx,dy)=wayshipin(dy,-dx)}R|i==90->ship{way=let(dx,dy)=wayshipin(dy,-dx)}|i==180->ship{way=let(dx,dy)=wayshipin(-dx,-dy)}|i==270->ship{way=let(dx,dy)=wayshipin(-dy,dx)}F->let(ns,ew,(dx,dy))=(northSouthship,eastWestship,wayship)inship{northSouth=ns+i*dy,eastWest=ew+i*dx}runbeginmove=manhattan.foldl'movebeginwheremanhattanship=abs(northSouthship)+abs(eastWestship)main=domoves<-readFile"day12_input"<&>parseMovesprint(run(Ship(1,0)00)movemoves)print(run(Ship(10,1)00)move'moves)
Still insisting on proper modelling, unit tests and real parsers over string splitting and regex.
I have to ask - why avoid regex use? Seems just another tool in the toolbox.
It is another tool in the box, and sometimes even the right tool. But regex is a sub-optimal general solution to what is often a quite specific task. One of my passions in programming is to show that real parsers are almost always better in the long run, and they're not hard to write.
Here's a recording of a talk I did at the Edinburgh Kotlin user's group last year on the subject: vimeo.com/393132096
So many
matchstatements.COBOL (part 2 on GitHub)
Part 1 Python
New to coding and behind in the calendar but this one looked easy overall.
not sure how to get syntax highlighting to show here
Part 2
I need to refactor this and function it out
Nice! I like how you folded the absolute directions and the forward commands into one action with checks on the current direction. Look into the
%(modulo) operator for handling the circular arithmetic around the rotation additions - in short(dir + num) % 360for right turns and(dir + 360 - num) % 360for left.There are (at least) two ways to "model" the solution: polar coordinates or vector/gonio math. Here is a Ruby OOP solution using the latter:
I'm gonna post the 2 parts separately, as it looks like it's gonna be easier to edit the code than to support both parts with the same module.
here's part 1:
Part 2:
Not too bad! I had an issue with the rotation in part 2, and I ended up writing so. many. tests. to find it. Which totally payed off!
Day12.h:
Day12.c:
Another javascript master piece: this gist.
Happy to use the javascript value swap shortcut in this one:
Got through this one fairly quickly (problem sat well with how my mind works, I guess).
As always, on Github.
Warning, lots of code today! I've been making an effort to model my solutions in ways that do not require special branching, or separate solutions for the 2 parts. Today was a fun one, and I think I came up with a good design, even if it's a little verbose!
At this point I think my enterprise development roots are showing. I've got inheritance, interfaces, strategies, factories, and even a DI container in my overall 2020 codebase 🤣
Part1
Part 2
FerryBase
Ferry (Part1's Implementation)
WaypointFerry (Part2's Implementation)
Fun today, although solved part 1 before going out this morning, only to realise I needed slighty different function for part 2 :-) In the end just went with 2, mostly same, functions, as did not have the will power to generalize!
It's nice now that I'm starting to have a litlte library of "AOC" functions that I can call upon.
My JavaScript walkthrough: