Advent of Code

[red marley]

Advent of Code 2016 is imminent! 

Looks like jo's private leaderboard from last year carries over to 2016 too.

In case it is not obvious to anyone new to the Advent of Code, the 'private leaderboard' allows you to view the number of completed challenge questions from YACF people who register. To join the board, simply enter the code 48462-ea506236 under 'leaderboard -> join private leaderboard'.

To enter the challenge at all you will need to log in to the site with one of the following credentials: twitter, Google, GitHub or Reddit. This is necessary as they are used to generate a (possibly) unique set of question variations and validation of your answers. No spamming is involved (as far as I am aware).

I'd really recommend the challenge to anyone with even a passing interest in coding. So far the challenges have been very well designed providing a manageable and satisfying learning curve over the 25 days. Whether you are a beginner wanting to develop skills in a new language (I'm going to attempt some in Elm and possibly Racket this year) or are an expert programmer with a familiar language, there is something on offer.

[Oaky]

from the Advent of Code author on Twitter:-

https://twitter.com/ericwastl/status/801715851510616064

 

[red marley]

I need to apologise as I have inadvertently given out the code for the YACF private leaderboard to colleagues at work (I thought I had generated a new code from a different account, but had passed the wrong one to colleagues). The upshot is that there may be a few others joining the YACF leaderboard this month. If that is a problem for anyone, now would be the time to start a new YACF one.

[David Martin]

I haven't done it yet but this is the approach I will take..

(click to show/hide)

Start at 0,0. Your direction is set by a number between 0 and 3 which indexes an array of 2d vectors. Turning left increments the number, turning right decrements. The vectors are (1,0), (0,1), (-1, 0), (0,-1)
For each step:
increment/decrement the index as appropriate and adjust to be in range.
Multiply the indexed vector by the number of steps and add to the current position.

Final result - sum the coordinates in the position vector.

[David Martin]

And then there is part 2

(click to show/hide)

Instead of adding the sum total of steps, increment one at a time and add the coordinates to a hash, checking to see if that position has already been seen.

[Diver300]

Both parts of day 1

(click to show/hide)

That was solved as David said, and done in Excel.

An X-Y plot of the result showed the answer to the second part very quickly

[red marley]

Day 1: I did pretty much the same as David Martin. Quite similar to one of the problems last year.

Diver300 - Initially I though your quick solution to part b was rather elegant but...

(click to show/hide)

It does not guarantee you the correct answer for many configurations with multiple crossing points. e.g. a 'B' shape trajectory could have the first intersection at several points all producing the same trail.

[Diver300]

Day 1: I did pretty much the same as David Martin. Quite similar to one of the problems last year.

Diver300 - Initially I though your quick solution to part b was rather elegant but...

(click to show/hide)

It does not guarantee you the correct answer for many configurations with multiple crossing points. e.g. a 'B' shape trajectory could have the first intersection at several points all producing the same trail.

(click to show/hide)

I don't think so.
The trajectory starts at 0,0 but doesn't end there. Just follow the line from 0,0 until it crosses itself for the first time.
The only problem with my data set was that most steps were single digit numbers of blocks, but some were in the hundreds. The crossing of the long steps were easy to see, but when the chart is scaled out to see the whole route, the short steps were a complete jumble. However, it didn't take long to zoom in and I found that the short steps didn't cross.

[David Martin]

Day 1: I did pretty much the same as David Martin. Quite similar to one of the problems last year.

Diver300 - Initially I though your quick solution to part b was rather elegant but...

(click to show/hide)

It does not guarantee you the correct answer for many configurations with multiple crossing points. e.g. a 'B' shape trajectory could have the first intersection at several points all producing the same trail.

(click to show/hide)

I don't think so.
The trajectory starts at 0,0 but doesn't end there. Just follow the line from 0,0 until it crosses itself for the first time.
The only problem with my data set was that most steps were single digit numbers of blocks, but some were in the hundreds. The crossing of the long steps were easy to see, but when the chart is scaled out to see the whole route, the short steps were a complete jumble. However, it didn't take long to zoom in and I found that the short steps didn't cross.

(click to show/hide)

You were fortunate you didn't come back through the origin or cross a second time closer to the origin. It is a heuristic but not exact method.

[tom_e]

Well, that was a bit disappointing.  I'd recommended this to mrs_e on the basis it started off really gently in last year's problems and only gradually picked up in intensity.  This was straight in with an equivalent of day 3 (2015) but with an extra level of complexity due to rotations.

[red marley]

I think Day 2 is easier so mrs_e may have more joy today.

Day 2, my solution

(click to show/hide)

Rather than encode the grid layout of the pad in part a, I went for simple lookup arrays for each of the four directions where the index of the array is the current digit (or rather current digit-1 for 0 indexed arrays) and the value at that index is the next digit given a move in the given direction:

nextDigit(num, dir)
{
   up    = {1,2,3,1,2,3,4,5,6};
   down  = {4,5,6,7,8,9,7,8,9};
   left  = {1,1,2,4,4,5,7,7,8};
   right = {2,3,3,5,6,6,8,9,9};
      
   switch (dir)
   {
      case 'U':
         return up[num-1];
      case 'D':
         return down[num-1];
      case 'L':
         return left[num-1];
      case 'R':
         return right[num-1];
   }
}

There are more elegant algorithmic solutions, but the lookup approach turned out to be useful for part b where the arrangement is more complex. For part b I encoded buttons A, B, C and D as integers 10-13 so I could still use the array lookup approach.

[David Martin]

Interesting. I took a slightly different approach, modelling the keypad more explicitly.

(click to show/hide)

I defined a function for each move that checked to see if it was at the edge of the pad, eg.

def U():
    ycoord = min(2, ycoord+1)

and call that via a lookup table

moves()

It was then trivial to extend to lookup in a  list of dimensions for extending the problem

ycoord = min(maxima[xcoord], ycoord+1)

And then get the digit from a 2D array (or 1D array of text strings) that model the pad.

code:

(click to show/hide)

data='''...''' # input data
coords=[1,1]
minima=[2,1,0,1,2]
maxima=[2,3,4,3,2]
def U():
    coords[1]=min(maxima[coords[0]],coords[1]+1)
   
def D():
    coords[1]=max(minima[coords[0]],coords[1]-1)


def R():
    coords[0]=min(maxima[coords[1]],coords[0]+1)
   
def L():
    coords[0]=max(minima[coords[1]],coords[0]-1)

moves= {'U': U, 'D','L':L,'R':R}   
keypad = ['  5  ',' A62 ','DB731',' C84 ','  9  ']

code =''
for press in data:
    for m in press:
        moves[m]()
    code = code+str(keypad[coords[0]][coords[1]])
print(code)

[Diver300]

(click to show/hide)

I used javascript this time.
I didn't encode the keypad at all. I did that manually at the end - it's only 5 numbers each time.

For the first half, I simply limited the x and y to 1 to 3

For the second half, I modelled the limits on x as a function of y and vice-versa:-

     
       if (digit == "U" && y + Math.abs(x-3) < 4.5 ) {y++;}
       if (digit == "D" && y - Math.abs(x-3) > 1.5 ) {y--;}
       if (digit == "R" && x + Math.abs(y-3) < 4.5 ) {x++;}
       if (digit == "L" && x - Math.abs(y-3) > 1.5 ) {x--;}

[tom_e]

I think Day 2 is easier so mrs_e may have more joy today.

S'alright, she got there in the end with day 1 last night.  And while still in bed this morning she reported the same thing you have just said after reading day 2. 

[David Martin]

Gone back to day1 in R to force myself to think differently.

(click to show/hide)

Part 1;
data <-''
moves <- strsplit(data,', ')
steps <- as.integer(lapply(moves,substr,2,4)[[1]])
turns <- lapply(moves,substr,1,1)[[1]]
turns[turns=='R']<- 1
turns[turns=='L']<- -1
turns<- as.integer(turns)*c(1,-1)
cp<- cumprod(turns)
xsteps<-seq(1,length(steps),2)
ysteps<-seq(2,length(steps),2)
x <- sum(steps[xsteps]*cp[xsteps])
y <- sum(steps[ysteps]*cp[ysteps])
abs(x+y)

And now to think about part 2..

[Diver300]

Day 3 seemed simpler to me than either of the previous days.

(click to show/hide)

Excel again. The maths was easy. Data handling any other way would take me longer.
For the second half, I used ability of Excel to copy an area into a larger area, to repeat the pattern.

[David Martin]

Agreed. Still trying to do Day 1 part 2 in R. It's very good for row level manipulations but doing all against all is taxing me a bit. I might try embedding an SQL query in the R code (because one can).

[red marley]

Day 3

Because I like drawing pictures, I thought I'd create some festive visualisations of my Day 3 answers. Here's part (a) with each green triangle being a 'real' triangle with edge lengths as provided and impossible ones shown as three pronged branches with the given lengths.



And here is part b with the vertically derived triangles added in red.

[David Martin]

A bit lengthier to solve today but not hard - bit of regex processing and understanding ascii. Had to look up how to do nested sorts in python as I'd not done that before, otherwise pretty straightforward.

[Diver300]

I used Javascript again today but kept falling over my own programming inability, but got there in the end.

[Pingu]

Late starter 

Day 1 done, a bit harder than expected.


AoC_day_01 by The Pingus, on Flickr

[Pickled Onion]

A bit lengthier to solve today but not hard - bit of regex processing and understanding ascii. Had to look up how to do nested sorts in python as I'd not done that before, otherwise pretty straightforward.

It was good to practice sort functions, but the best I could come up with for the checksum was

(click to show/hide)

sub checksum{
  my %letters;
  map {$letters{$_}++} split //, ( s/-//g, $_);
  my $ByFrequencyThenAlphabetically = sub {$letters{$b} <=> $letters{$a} or $a cmp $b };
  return substr((join '', sort $ByFrequencyThenAlphabetically keys %letters), 0, 5);
}

I'm sure there must be a way to create the hash anonymously on the fly, but it's eluding me.

[David Martin]

A bit lengthier to solve today but not hard - bit of regex processing and understanding ascii. Had to look up how to do nested sorts in python as I'd not done that before, otherwise pretty straightforward.

It was good to practice sort functions, but the best I could come up with for the checksum was

(click to show/hide)

sub checksum{
  my %letters;
  map {$letters{$_}++} split //, ( s/-//g, $_);
  my $ByFrequencyThenAlphabetically = sub {$letters{$b} <=> $letters{$a} or $a cmp $b };
  return substr((join '', sort $ByFrequencyThenAlphabetically keys %letters), 0, 5);
}

Would something like:

$data = <INPUT>;
$data=~m/([a-z-]+)(\n+)\[([a-z]+)\])/;
$name=$1
sort { $@{$name=~/$a/g} <=>$@{$name=~/$b/g} or $a cmp $b}  uniq split //, $name =~s/-//g;
be close to what you are looking for? Untested.
ETA: extra $$$$$ because it is perl and I haven't doen that for a while

I'm sure there must be a way to create the hash anonymously on the fly, but it's eluding me.

[Pickled Onion]

I see where you're going with that, but the wriggly problem is to keep track of the counts for each letter.

Looking forward to tomorrow's offering.

[David Martin]

I see where you're going with that, but the wriggly problem is to keep track of the counts for each letter.

Looking forward to tomorrow's offering.

It does that implicitly doesn't it? you are sorting on the letters and it is inefficient in that it runs the regex for every comparison. You don't need to keep track of the counts for each letter if they are readily recalculable.