Advent of Code 2016 Day 7 (Javascript)

Previous:

Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)

Advent of Code 2016 – Day 4 (Perl 6)

Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)

Day 7

Start: 12/7/2016

Finish 12/8/2016

Language: Javascript

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

This time around, the goal was to take strings that were  sequences of characters, with some enclosed in square brackets, like so: ioxxoj[asdfgh]zxcvbn.

With those strings, we had to find ones where an ABBA pattern existed outside of the square bracketed enclosed sequence (it could be any two letters, not just A and B, but they had to be different).  It also could not have an ABBA sequence insidde the square bracket enclosed sequence.

I figured out I could use Javascript and regexes for this one, especially after learning about backreferences to solve http://jimbly.github.io/regex-crossword/.  Let’s look at the code:


const fs = require('fs')

function hasABBA(str){
    return str.match(/(\S)((?!\1).)\2\1/);
}

function splitOutSections(str){
    return str.split(/\[.*?\]/)
}

function getHypertext(str){
    return str.match(/\[(.*?)\]/g)
}

function isValid(str){
    return splitOutSections(str).some(hasABBA) &&
           getHypertext(str).every((str) => !hasABBA(str));

}

lines = fs.readFileSync("../day7.txt", "utf8").split("\n");
console.log(lines.filter(isValid).length);

This is pretty short.  I had a misstep with the regex, but a negative lookahead assertion helped me out.


function hasABBA(str){
    return str.match(/(\S)((?!\1).)\2\1/);
}

Then it was simple to split out what was in square brackets (Called “hypertext” in our example):


function isValid(str){
    return splitOutSections(str).some(hasABBA) &&
           getHypertext(str).every((str) => !hasABBA(str));

}

 

And that was really it to it.

 

 

Part 2

So now, the goal was to find an ABA sequence outside of the hypertext with a BAB in the hypertext.  I thought I could use a regular expression as well, but I could not get it to match a string like ABACA to match.  Instead, I had to write a normal for loop to do it.  (I even messed this up because I forgot about some of the global variable scoping in Javascript).

Let’s look at what was needed :


function isABA(substring) {
   
    return substring[0] === substring[2] && substring[1] !== substring[0]
}
function getABA(str){
    var abas = []
    for(let i = 0; i < str.length; i++){
        const substring = str.substring(i, i+3);
        if (substring.length == 3 && isABA(substring)) {
            abas.push(substring);
        } 
    }
    return abas;
}

I also had to change out the isValid function to check these.  Here, I get each section, get the ABA’s out of them, take out any empty strings and reduce the ABA sections to one list.  Then its a simple check to see if any of the ABA sequences are represented in BAB sections



function flip(str){
    return str[1] + str[0] + str[1];
}

function isValid(str){
    var abas = splitOutSections(str).map(getABA)
                                .filter((x) => {return x;})
                                .reduce((a,b) => { return a.concat(b)}, []);
    var babs = getHypertext(str).map(getABA)
                            .filter((x) => {return x;})
                            .reduce((a,b) => { return a.concat(b)}, []);

    return abas.some((aba) => {return babs.includes(flip(aba));});
}

 

Wrap-up

I had quite a few missteps in here.  I understood the Javascript part, but the Regexes fooled me a bit, and I should have really tested against the known input.  Overall I give myself a B-.  I did the first half great, but the second one had stupid mistakes in them, and I took too long to do it.

Next up, I’m going to use C++ to work on Day 8. Let’s hope it goes a lot better than this time around.

 

Advent of Code Day 6 (Julia)

Previous:

Advent of Code 2016 – Day 5( Java 8)
Advent of Code 2016 – Day 4 (Perl 6)

Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)

Day 6

Start: 12/7/2016

Finish 12/7/2016

Language: Julia

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

So I decided to take a stab at Julia this time around.  I was doing some column based reading of text, and I thought Julia’s arrays on steroids might give me something.

I was happy with how nicely this fit together, let’s take a look:


function getHighestCount(chars)
    dict = Dict()
    for char in chars
       dict[char] = get(dict, char, 0) + 1
    end
    return sort(collect(dict), by= tuple -> last(tuple), rev=true)[1]
end

f = open("../day6.txt")
    lines = readlines(f)
    chars = map(s -> split(strip(s), ""), lines)
    reshaped = hcat(chars...)
    columns = map(x -> getHighestCount(reshaped[x,:]), 1:length(reshaped[:,1]))
    answer = *(map(c -> c[1], columns)...)
    println(answer)
close(f)

That’s it, 16 lines of code.

Main processing part is straight-forward again (once you know Julia syntax).


f = open("../day6.txt")
    lines = readlines(f)
    chars = map(s -> split(strip(s), ""), lines)
    reshaped = hcat(chars...)
    columns = map(x -> getHighestCount(reshaped[x,:]), 1:length(reshaped[:,1]))
    answer = *(map(c -> c[1], columns)...)
    println(answer)
close(f)

First we read the lines in, then map a split over them so we get a whole bunch of char arrays.  With 624, 8 byte arrays, I decided to hcat the values, so that I ended up with a 624×8 array of characters.  Then, using Julia’s n-dimensional array slicing, I did this


columns = map(x -> getHighestCount(reshaped[x,:]), 1:length(reshaped[:,1]))

We’ll take a look at getHighestCount in a bit, but for now, just know that it retrieves the letter of the most frequency.  So in essence, we are getting the highest frequency of a column of the original text.

Then we map over the returned tuples and use the * to concatenate all of them together


*(map(c -> c[1], columns)...)

Looking at getHighestCount, it was simply a dictionary that tracked frequency, and then sorted by the values in reverse order.


function getHighestCount(chars)
    dict = Dict()
    for char in chars
       dict[char] = get(dict, char, 0) + 1
    end
    return sort(collect(dict), by= tuple -> last(tuple), rev=true)[1]
end

And that was it.

 

Part 2

This part was almost laughably easy.  I turned getHighestCount into a getLowestCount, and removed the rev=true argument in the sort.  That’s it.  All there was.  It is great when all you have to do to gain functionality is delete code.


function getLowestCount(chars)
    dict = Dict()
    for char in chars
       dict[char] = get(dict, char, 0) + 1
    end
    return sort(collect(dict), by= tuple -> last(tuple))[1]
end

 

Wrap-up

I’m not going to pretend I understand a lot of Julia’s n-dimensional mathematics, but I can definitely recognize how it would be a boon in numerical computing.  At first, I wished there was a few more things in the standard library (I spent a lot of time looking for group_by, chunk_by, frequency counts, and so on) but in the end, I couldn’t find them (they may have very well been there), and it led me to what I think was a very Julian solution.

I grade myself as an A on this one.  I solved this in about an hour and a half, and that included skimming back through 7 more languages in 7 weeks to refresh myself on Julia.

Next up, it looks like Regex will help me out again, so I’m going to take a stab in ECMAScript 2016+/Javascript.

 

Advent of Code 2016 – Day 5( Java 8)

Previous:

Advent of Code 2016 – Day 4 (Perl 6)
Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)

Day 5

Start: 12/7/2016

Finish 12/7/2016

Language: Java 8

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

So I really haven’t touched Java since my first job.  So, I saw a challenge that involved MD5, thought to the Java library that I remember using way back when, and decided to polish up some skills.  I wanted to dig into Java 8 since the introduction of lambda expressions and streams, but haven’t had a reason to.

So this time around, I had to MD5 a combination of a key and ever-incrementing numbers until I found 8 hashes that had a special property (started with 5 zeroes when converted to a string).   Then we had to grab the sixth character of those hashes and that forms our password. So this sounded perfect for an infinite stream.  Let’s take a look at the full code before I dive in.  (It’s a bit more verbose than others, but hey, it’s Java.)


import java.security.MessageDigest;
import java.util.stream.IntStream;
class Challenge1 
{
    static String doorId = "ffykfhsq";

    final protected static char[] hexArray = "0123456789ABCDEF".toCharArray();
    public static String bytesToHex(byte[] bytes) 
    {
        char[] hexChars = new char[bytes.length * 2];
        for ( int j = 0; j >> 4];
            hexChars[j * 2 + 1] = hexArray[v & 0x0F];
        }
        return new String(hexChars);
    }

    public static String md5(int index)
    {
        try
        {
            MessageDigest md = MessageDigest.getInstance("MD5");
            String str = doorId+new Integer(index).toString();
            byte[] digest = md.digest(str.getBytes("UTF-8"));
            return new String(Challenge1.bytesToHex(digest)); 
        }
        catch(Exception e)
        {
            return "";
        }
    }

    public static boolean isAGoodHash(int index)
    {
        String hash = Challenge1.md5(index);
        return hash.startsWith("00000");
    }

    public static int getKey(int index)
    {
        String hash = Challenge1.md5(index);
        return hash.charAt(5);
    }

    public static void main(String[] args)
    {
        
        IntStream.iterate(0, i-> i+1)
                 .filter(Challenge1::isAGoodHash)
                 .limit(8)
                 .map(Challenge1::getKey)
                 .forEach(i -> System.out.print((char)i));
        System.out.println();
    }
}

The main part is pretty self explanatory.  Start with an infinite sequence 1,2,3……., filter out anything that isn’t a good hash, take the first 8 and grab the keys, finally printing them all out.

 


    public static boolean isAGoodHash(int index)
    {
        String hash = Challenge1.md5(index);
        return hash.startsWith("00000");
    }

    public static int getKey(int index)
    {
        String hash = Challenge1.md5(index);
        return hash.charAt(5);
    }

    public static void main(String[] args)
    {
        
        IntStream.iterate(0, i-> i+1)
                 .filter(Challenge1::isAGoodHash)
                 .limit(8)
                 .map(Challenge1::getKey)
                 .forEach(i -> System.out.print((char)i));
        System.out.println();
    }

The MD5 code was able to heavily borrow off of java.security.MessageDigest to create the MD5


    public static String md5(int index)
    {
        try
        {
            MessageDigest md = MessageDigest.getInstance("MD5");
            String str = doorId+new Integer(index).toString();
            byte[] digest = md.digest(str.getBytes("UTF-8"));
            return new String(Challenge1.bytesToHex(digest)); 
        }
        catch(Exception e)
        {
            return "";
        }
    }

 

Finally, I took some code off the internet to convert a byte string to hex (I’d written this so, so many times before in Java that I didn’t feel like writing it once again.


    final protected static char[] hexArray = "0123456789ABCDEF".toCharArray();
    public static String bytesToHex(byte[] bytes) 
    {
        char[] hexChars = new char[bytes.length * 2];
        for ( int j = 0; j >> 4];
            hexChars[j * 2 + 1] = hexArray[v & 0x0F];
        }
        return new String(hexChars);
    }

And that was it!  That was all the code it took.  I really like how expressive streams are in languages that support that type of composability.  It reminds me of Clojure’s pipeline in Day 3, and I’m sure we’ll see it again in Elixir and Elm.

 

Part 2

Here was a kicker for the FP enthusiast in me.  It wasn’t enough to just grab the first 8 hashes anymore.  The fifth character in each hash was now the position of the final character in the password, and the sixth character was the character itself.  Any hash that didn’t have a position 0-7 should have been ignored, and only the first time the position is seen should we update the key.

I updated the isAGoodHash to at least check position 0-7


   public static boolean isAGoodHash(String hash)
    {
        return hash.startsWith("00000") && isValidPosition(hash.charAt(5));
    }

This means I have to track state through iteration.  I took a very precursory glance through Java docs to try and figure out if there was a way to use reduce or collect to stop iteration  when I the password was filled out, but wasn’t finding anything.  (I’m sure there’s something, I just didn’t have anything at the time.)

So, rather than try to make pure FP and bend the rules, I put in an explicit for loop to indicate that I’m mutating state.


 public static void main(String[] args)
    {
        
        Iterator it = IntStream.iterate(0, i-> i+1)
                                .mapToObj(Challenge2::md5)
                                .filter(Challenge2::isAGoodHash)
                                .iterator();
        List keys =  Arrays.asList('-', '-','-','-','-','-','-','-');
        while (it.hasNext())
        {
            String s = it.next();
            char pos = (char)(s.charAt(5) - 48);
            char c = s.charAt(6);
            if(keys.get(pos) == '-')
            {
                keys.set(pos,  c);
            }
            if(!keys.contains('-'))
            {
                break;
            }
        }

        keys.stream().forEach(c -> System.out.print(c));
        System.out.println();
    }

I found mapToObj this time around, which let me convert them to a String right away rather than dealing with ints the whole way through.

 

Wrap-up

I liked using Streams and Lambda Expressions in Java 8.  It definitely cuts down on some of the verbosity that plagued Java programs of the past.  However, it still had it’s limits, and Java as a whole felt fairly verbose to me.

I give this exercise of mine an A-.  I was able to use what I wanted, learned some new things, and got the problems right on my first try.  Next up, I’m going to take a stab at a numerical computing language, Julia.

 

Advent of Code 2016 – Day 4 (Perl)

Previous:

Advent of Code 216 – Day 3

Advent of Code – Day 2

Advent Of Code 2016 – Day 1

Day 4

Start: 12/5/2016

Finish 12/6/2016

Language: Perl

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

This day, the goal was to try and figure out which rooms out of a list were valid by matching up a checksum with their most frequent characters.  I really liked this idea.  What I didn’t like was the fact that I chose Perl for this.  I had never written Perl before in my life.  And I never want to ever again either.
Continue reading

Advent of Code 2016 – Day 3

Previous:

Advent of Code – Day 2

Advent Of Code 2016 – Day 1

Day 3

Start: 12/5/2016

Finish 12/5/2016

Language: Clojure

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

So this one wasn’t too bad.  Reminded me of a Project Euler problem.  Find the number of triplets that could be a valid triangle (the sum of two sides are always greater than the other)

Continue reading

Advent of Code – Day 2

Previous:

Advent Of Code 2016 – Day 1

Day 2

Start: 12/4/2016

Finish 12/4/2016

Language: Python3

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub:

 

Problem Statement

The problem started off simple enough.  There is a 9 digit keypad listed:

123
456
789

 

If you start at the 5 key, and are given directions to move up, down, right or left, multiple times, what are the keys that you end at after each iteration of directions?

Not too bad, and I was picking a language in my wheelhouse, Python.  I chose Python 3, since I don’t get much experience with it, but unfortunately, this program did not stretch my knowledge of Python 3.  There wasn’t enough meat to the problem to really dive in.

So let’s look at the code:
Continue reading

Advent Of Code 2016 – Day 1

So on Hacker News, I came across something awesome.  Advent of Code (http://adventofcode.com/)

A programming challenge that takes 25 2-part challenges, one  a day until Christmas.  I’ve been looking for a side project to hone my code, and this was perfect.  Especially after dragging my feet on board game bots, Alexa skills, general programs, and so on and so forth.  I’ve been having a bit of trouble lately because I haven’t felt like I was advancing my technical skills in a bit, and this will help.

I’ve done plenty of coding challenge sites before, with the most notable being Project Euler, so i wanted a nice challenge this time.  I knew I wasn’t going to be the fastest on the site, so speed wasn’t going to be an option.  Instead, I want to work on being a polyglot.  Let’s work in a few different programming languages.  The goal then, 25 languages in 25 days.  Am I going to be successful?  Probably not.  I have a hackathon week at work.  I have Christmas shopping to do.  I make dinner every night and have a wife and son to tend to.  But, once everyone goes to bed and the house is quiet, it’s my time to shine.

Let’s look at how the first day went……

Continue reading

DevspaceConf16 Day 2

Talk: The Joy of Desktop Apps with Electron (by David Neal – @ReverentGeek)

So this was the talk I was waiting for, but I just didn’t know it yet.  I knew about Electron (a cross-platform desktop application builder using web technologies) through the use of Atom, but I didn’t understand the intricacies.  But as David spoke (and he was a great speaker, with hand-drawn images peppering his slides, adding charm), I found myself not listening at times, and instead wondering what I could do with Electron.  To me, this is a successful talk, where it gets my brain spinning for new ideas and I want to go work with it.  In December, we have a week long hackathon at work, so I’m definitely interested in doing more.

Continue reading

Devspace16 Conf (Day 1)

Welp, I made it to DevSpace, securing my goal of going to a conference this year.

DevSpace is a conference in its second year in my hometown of Huntsville Alabama.  To be honest, the talks didn’t draw me in as strong as PyTennessee or StrangeLoop did last year, but I wanted to give it a chance and learn new things.

I went to a meetup earlier this week, and the conference organizer, Chris Gardner (@freestylecoder) talked about the conference.  He said something that stuck with me, in that this conference is all about learning new things.  They specifically organized it so that if you had a specific interest, it’d be present at the conference, but wouldn’t overwhelm us.  For instance, you can like web programming, but with 11 talk slots, you won’t be able to go to 11 web talks.  I liked that.  I liked the encouragement of stepping out of your comfort zone, and that renewed my interest and enthusiasm for the conference.

So between today and tomorrow, I’m going to try to step out of my comfort zone, and push my boundaries.  I’ll go to talks that I normally wouldn’t go to, or even if I don’t have interest in, because I’m here to learn something new.

I also want to keep a record of what I’ve seen, so I’m going to do a short write up on each of the talks.

Continue reading

First Conference Proposal

So a few days ago, I officially submitted my first conference talk!  Bdd to the Bone: Test-Driving Web Applications with Behave and Selenium.  It’s no secret that testing is close to my heart as far as software enginnering goes, so I wanted to give a talk representing some of my interests.  I want to talk about some of the things that went through my head on this.
Continue reading