Advent of Code F# – Day 12

The source code for this post (both Part 1 and Part 2) is avail­able here and you can click here to see my solu­tions for the oth­er Advent of Code chal­lenges.

Descrip­tion for today’s chal­lenge is here.

 

With the way Part 1 is phrased, it means we don’t actu­al­ly have to under­stand the JSON doc­u­ment itself — we can cheat by regex out all the num­bers and sim­ply add them up! 

day12_01

 

Part 2

This part is slight­ly more chal­leng­ing, but even so we still don’t nec­es­sar­i­ly have to under­stand the JSON doc­u­ment — we just need to find the scope of the object (as defined by matched { and }) that has a prop­er­ty val­ue “red”.

So let’s define two func­tions — find­Bound­aryL and find­Bound­aryR — that can find the left (the open { ) and right (the clos­ing } ) bound­aries of the object that has a “red” prop­er­ty (as deter­mined by the start­ing index):

day12_02

The log­ic for find­Bound­ary is per­haps slight­ly convoluted/abstract, so let’s go through it:

  • giv­en some direc­tion (+/- 1) that we’re tra­vers­ing through the input, and start­ing with 1 open door behind us;
  • if we saw an open door, then recurse by incre­ment­ing the accu­mu­lat­ed num­ber of open doors by 1
  • if we saw a closed door, then recurse by decre­ment­ing the accu­mu­lat­ed num­ber of open doors by 1
  • oth­er­wise, just recurse with the cur­rent num­ber of open doors
  • when the accu­mu­lat­ed num­ber of open doors is down to 0, it means we’ve man­aged to close all the open doors behind us, and there­fore dis­cov­ered the index of the close door that match­es the ini­tial open door

For exam­ple, if “red” is at index 102, and we’re try­ing to find the clos­ing } for the object, then start­ing from 102, we’ll iter­ate through the chars to the right of 102:

…:“red”, “b”:{“c”:42,“d”:“42”},“e”:8},…

start­ing with index = 102, acc = 1

index = 113, saw ‘{‘, acc incre­ment­ed to 2

index = 129, saw ’}’, acc decre­ment­ed to 1

index = 136, saw ’}’, acc decre­ment­ed to 0

acc = 0, right bound­ary is at index 136

repeat the same process in reverse to find the posi­tion of the open­ing { for this object.

 

Now we can find the bound­aries of objects that has a “red” prop­er­ty:

day12_03

and use this infor­ma­tion to fil­ter out num­bers that are part of any of these objects (i.e. the num­ber is inside any of these bound­aries):

day12_04