Advent of Code

[David Martin]

OK, there is no easy way to calculate the number of occurences of a substring in Perl so I had to craft a simple function for it.

(click to show/hide)

use List::MoreUtils qw(uniq);

sub count{
   $count=0;
   while ($_[0]=~/$_[1]/g){$count++;}
   return $count;
}


open FH, 'day4input.txt';
$scount=0;
while (<FH>){
    $_=~m/^([a-z-]+)([0-9]+)\[([a-z]+)\]/;
    $name=$1;
    $sid=$2;
    $code = $3;
    $name=~s/-//g;
    $chksum=substr (join ('', sort( { count($name, $b) <=> count($name,$a) or $a cmp $b} uniq split //, $name)), 0,5);
    if ($code eq $chksum){
        $scount+=int $sid;
        #print "$code\t$chksum\n";
    }
}
print "Count $scount\n";


This does away with needing any hashes at the expense of efficiency.

[red marley]

Day 5:

(click to show/hide)

Very similar to Day 4 a year ago. My input (YIMV) required about 7 seconds to compute the relevant hashes for both parts. Helps if your language of choice has access to an MD5 hash generator.

I rather like the challenge to produce a HollywoodOS version of the password decryption. Might have to have a go at that. Now where are those beeps...

[David Martin]

Took mine nearly half a minute. I did have a text console holywood version.. ish.

[Diver300]

The server that I ran the .php file on took about 45 seconds to do the second half.

(click to show/hide)

I didn't bother writing code to assemble the final answer. I gradually increased the number of results until I had the ones that I needed. I finished by getting it to stop when it found "00000n" when all I needed was the nth character.

[red marley]

From the creator of Advent of Code this morning...

I hope everyone has been enjoying #AdventOfCode! Today ends the warmup puzzles. It's uphill from here!

[Oaky]

From the creator of Advent of Code this morning...

I hope everyone has been enjoying #AdventOfCode! Today ends the warmup puzzles. It's uphill from here!

I was just about to post that the first six days felt like "limbering up", and I had a feeling that the difficult stuff was about to start.

[David Martin]

Today was straightforward. I have then worked out how to do it in R without loops. One line to read the data in and one very long line to generate the answer.

(click to show/hide)

day6<-read.table('input.txt') #note this is a table with column header X1
paste(unlist(lapply(1:8, function(y){names(table(as.factor(unlist(lapply(day6$X1, function(x){unlist(strsplit(x, split=character(0)))[y]})))))[order(table(as.factor(unlist(lapply(day6$X1, function(x){unlist(strsplit(x, split=character(0)))[y]})))))][1]})), collapse="")

[Tim Hall]

The Boy, last night, informed me he's cracked 1-4 and was working on 5.   

[Oaky]

Today was straightforward. I have then worked out how to do it in R without loops. One line to read the data in and one very long line to generate the answer.

(click to show/hide)

day6<-read.table('input.txt') #note this is a table with column header X1
paste(unlist(lapply(1:8, function(y){names(table(as.factor(unlist(lapply(day6$X1, function(x){unlist(strsplit(x, split=character(0)))[y]})))))[order(table(as.factor(unlist(lapply(day6$X1, function(x){unlist(strsplit(x, split=character(0)))[y]})))))][1]})), collapse="")

(click to show/hide)

I did it initially in Python with the collections library, where the Counter() class makes it very simple.  (My default approach is to do these first in Python, adopting a test-driven approach with unittest, using whatever standard libraries suggest themselves.  If it looks amenable, I then have another go using Pandas.).

Since this looked amenable, I re-did it in Pandas...

Code: [Select]

import pandas as pd

input_l = []
with open('input.txt') as fd:
    for line in fd:
        input_l.append([c for c in line.rstrip('\n')])
       
data = pd.DataFrame(input_l)

part1 = part2 = ''
for col in data.columns:
    part1 += data[col].value_counts().index[0]
    part2 += data[col].value_counts().index[-1]

print 'Part 1 answer is: {}'.format(part1)
print 'Part 2 answer is: {}'.format(part2)

Then I saw David Martin's R version, so I scratched my head a bit and re-did it in Pandas with no loops...

Code: [Select]

import pandas as pd
df = pd.read_table('input.txt', header=None).apply(lambda x: pd.Series(list(x[0])), axis=1)
part1 = ''.join(df.apply(lambda x: x.value_counts().index[0]))
part2 = ''.join(df.apply(lambda x: x.value_counts().index[-1]))

print 'Message1 is: {}\nMessage2 is: {}'.format(part1, part2)


[David Martin]

My colleague has commented how he has learned so much in the last few days. I have too, and will certainly look at the bear bones of the Pandas implementation. Python seems to be my 'goto' to start off with (typically with a few sanity checks, not really tests, along the way). Then I might try something else for fun like R or the Perl from previous. I've not really looked at Pandas - I should do. Numpy is as close as I have got.

Looking forward to something a bit more stretching tomorrow.

[Oaky]

I did consider trying this year in something other than Python, but to be honest, up until now, my day job hasn't involved enough opportunity for data munging for me to have fully assimilated Python yet, despite learning it several years back. 

That's changing right now as I start to spend time with another team in $EMPLOYER, and one of the tools of choice in that team is pandas (plus Jupyter notebooks) so I'm sticking to Python and also playing with the Jupyter/pandas approach on some of these this year.

[David Martin]

I like the Jupyter notebooks approach to problem solving as you document each step along the way (or should).

[red marley]

Day 7: (ABBA internet protocols)

Do'h. Couldn't work out why I was getting the wrong answer for part a. Spent ages slowly debugging but could not find any problems with the logic of my code. Finally redownloaded the input text to find that my first attempt to download it had missed the last few lines.

Good challenge today though with plenty of scope for creating efficient pattern matching.

[David Martin]

i'm sure there is an efficient and elegant way to do it. Spent far too long trying to vectorise it in R with moderate amounts of nearly success then gave up and brute-forced it in python.

(click to show/hide)

There were two efficiency things. 1. If you split into alternate parts (in/out etc) then calculate the cumulative product of the part numbers in which the pattern is found, then an odd/even test will let you know if it is valid or invalid.and 2. for the second I put all the patterns found for one address into odd or even bins, then checked each pattern in the even bin to see if the inverse was in the odd bin.

[Oaky]

i'm sure there is an efficient and elegant way to do it. Spent far too long trying to vectorise it in R with moderate amounts of nearly success then gave up and brute-forced it in python.

(click to show/hide)

There were two efficiency things. 1. If you split into alternate parts (in/out etc) then calculate the cumulative product of the part numbers in which the pattern is found, then an odd/even test will let you know if it is valid or invalid.and 2. for the second I put all the patterns found for one address into odd or even bins, then checked each pattern in the even bin to see if the inverse was in the odd bin.

Brute force here too...

(click to show/hide)

for efficiency I created a look-up list of all ABBAs, (working from all distinct two letter itertools.combinations from string.ascii_lowercase) so that I could use "substr in ABBAs" as a test.

for part 2, I constructed two set()s one containing ABAs in the supernets and one containing the inverses of the BABs in the hypernets.  I could then use the set1.isdisjoint(set2) method to test for SSLness

[Pickled Onion]

Interesting approaches.

Regular expressions seemed the obvious approach...

(click to show/hide)

   
my $count;
map { ! /\[\w*(\w)(?!\1)(\w)(\2)(\1)\w*\]/      # not an ABBA in a hypernet
    and /(\w)(?!\1)(\w)(\2)(\1)/                # and an ABBA in a supernet
    and $count++ } <DATA>;                      # supports TLS
print $count;

[R_nger]

I'm using node.js and tried to use regular expressions as far as possible. Difficulties today due to not reading the instructions properly 😳

[David Martin]

Interesting approaches.

Regular expressions seemed the obvious approach...

(click to show/hide)

   
my $count;
map { ! /\[\w*(\w)(?!\1)(\w)(\2)(\1)\w*\]/      # not an ABBA in a hypernet
    and /(\w)(?!\1)(\w)(\2)(\1)/                # and an ABBA in a supernet
    and $count++ } <DATA>;                      # supports TLS
print $count;

And I have just learned what a zero width look ahead assertion is. Strangely most of the pages on perl re don't cover that...

[Oaky]

checkout askalski's brute-force Perl regexp solutions over on the adventofcode subreddit

And Eric Wastl's response:-

[–]topaz2078(AoC creator) 13 points 10 hours ago

Did you do this just to make me cry? Because it worked.

 

[David Martin]

Did you look at Part 2 of that thread?

[Oaky]

Did you look at Part 2 of that thread?

His Part 2 solution?  Yep!

[David Martin]

There is some pretty rank coding on display there..

[R_nger]

There is some pretty rank coding on display there..

yep, I'm glad I don't have to support some of that !  I'm not saying mine is pretty or elegant, but at least I'm not on a mission to minimise the line count (and ergo readability)!

[Ben T]

They put in a thing to deliberately confuse (some) regex parsing implementations, i.e.
zazbz
must match zaz and zbz.

not sure whether the challenge was to simply code in one that supports one match starting before another has ended?
or simply to realise that that is what was going on


https://github.com/bjtaylor1/AoC_2016

[red marley]

There is some pretty rank coding on display there..

yep, I'm glad I don't have to support some of that !  I'm not saying mine is pretty or elegant, but at least I'm not on a mission to minimise the line count (and ergo readability)!

Sure. Despite spending most of my career teaching people to prioritise clarity over brevity in programming, there is nevertheless something akin to magic when a 40 line block of procedural code can be replicated with

(click to show/hide)

grep -Pc '(.)(?!\1)(.)\1\w*(([][]\w*){2})*[][]\w*\2\1\2'

(an answer to Day 7 pt b from Reddit)

There's lots of geeky humour on that reddit with people deliberately choosing difficult languages (Brainfuck anyone?) so I'd take the one line solutions in that spirit. I've been impressed with the K language that some have been using. Seems to produce concise and efficient functional expressions  with a limited vocabulary for the kinds of list processing that has been the main feature of the challenges so far.