Advent of Code 2016 Day 18 (Bash)

Advent of Code 2016 Day 17 (Ruby)
Advent of Code 2016 Day 16 (Scala)

Advent of Code 2016 Day 15 (Typescript)

Advent of Code 2016 Day 14 (Go)

Advent of Code 2016 Day 13 (Lua)
Advent of Code 2016 Day 12 (C#)
Advent of Code 2016 Day 11 (Groovy)

Advent of Code 2016 Day 10 (OcaML)

Advent of Code 2016 Day 9 (Factor)

Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
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 18

Start: 12/22/2016

Finish 12/24/2016

Language: Bash

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 started with good intentions with Forth.  Then it took me an hour to get the toolchain installed on my linux box (had to go scraping through mailing lists).  Then I spent a lot of time poring over documentation.  After a few hours of working, I couldn’t even figure out how to read a file.  Sometimes you have to know when you’re beat, and I feel like to learn Forth, I really needed a week or two and a good reference to learn it.  I much preferred Factor.

So I made the tough decision to pivot to Bash.  I figured I’d use Bash much more than Forth in my career.  It stung having to back down, but it was bound to happen.

This challenge was about figuring out which tiles were safe to step on, and you could derive the next row of tiles from the previous row.  Then you had to sum up all the safe tiles across a whole lot of rows.

Part 1

Let’s look at the code.


#!/bin/bash
target=$(<"../day18.txt")

getChar() {
    sequence=$1
    index=$2
    if [ "$index" == "-1" ]; then
        char="."
    elif [ "$index" == "${#sequence}" ]; then
        char="."
    else
        char=${sequence:$index:1}
    fi
}
getNextChar() {
    getChar $1 $(($2-1))
    char1=$char
    getChar $1 $2
    char2=$char
    getChar $1 $(($2+1))
    char3=$char
    if [[ "$char1" = "^" && "$char2" = "^" && "$char3" = "." ]]; then
        nextChar="^";
    elif [[ "$char1" = "." && "$char2" = "^" && "$char3" = "^" ]]; then
        nextChar="^";
    elif [[ "$char2" = "." && "$char1" = "." && "$char3" = "^" ]]; then
        nextChar="^";
    elif [[ "$char2" = "." && "$char3" = "." && "$char1" = "^" ]]; then
        nextChar="^";
    else   
         nextChar=".";
    fi
}

getNextSequence() {
    sequence=$1
    target=""
    for (( i=0; i<${#sequence}; i++)) 
    do
        getNextChar $sequence $i
        target=$target$nextChar
    done
}

rows=40
fullString=""
for (( j=0; j<${rows}; j++))
do
    fullString=$fullString$target
    getNextSequence $target    
done
safe="${fullString//[^.]}"
echo ${#safe}

Starting with the main loop -> We keep looping over the rows getting the next sequence, and concatenating that onto a string.  Then we loop over the string and get the only safe tiles (“.”).



rows=40
fullString=""
for (( j=0; j<${rows}; j++))
do
    fullString=$fullString$target
    getNextSequence $target    
done
safe="${fullString//[^.]}"
echo ${#safe}

The next part is figuring out what each sequence should look like.  We simply loop over the string, determining what the next character should be.   The next character is determined by a set of rules outlined in the problem (see the big four if statements comparing three characters)


getNextChar() {
    getChar $1 $(($2-1))
    char1=$char
    getChar $1 $2
    char2=$char
    getChar $1 $(($2+1))
    char3=$char
    if [[ "$char1" = "^" && "$char2" = "^" && "$char3" = "." ]]; then
        nextChar="^";
    elif [[ "$char1" = "." && "$char2" = "^" && "$char3" = "^" ]]; then
        nextChar="^";
    elif [[ "$char2" = "." && "$char1" = "." && "$char3" = "^" ]]; then
        nextChar="^";
    elif [[ "$char2" = "." && "$char3" = "." && "$char1" = "^" ]]; then
        nextChar="^";
    else   
         nextChar=".";
    fi
}

getNextSequence() {
    sequence=$1
    target=""
    for (( i=0; i<${#sequence}; i++)) 
    do
        getNextChar $sequence $i
        target=$target$nextChar
    done
}

The last part is how to get character from a string.  I wanted to wrap this in a function so that out of bounds accesses returned a safe tile (this was important due to the rules of  the problem)


getChar() {
    sequence=$1
    index=$2
    if [ "$index" == "-1" ]; then
        char="."
    elif [ "$index" == "${#sequence}" ]; then
        char="."
    else
        char=${sequence:$index:1}
    fi
}

Part 2

Part 2 made us care about 400,000.  I tried to run the same code again with a different parameter, and after 30 hours of runtime, it wasn’t getting anywhere.

I did some quick profiling using the time command and a smaller solution space size, and figured out the string concatenation was taking the long part.  So I swapped the code up a bit, and ran a count each time during the loop


rows=400000
fullString=""
count=0
for (( j=0; j<${rows}; j++))
do
    safe="${target//[^.]}"
    count=$(($count+${#safe}))
    getNextSequence $target
done
echo $count

After about an hour and a half of runtime, I finally got the right answer

 

Wrap-up

I wanted to get Forth up and going, but I was worried that it was taking too long.  Its not like Bash was that much better, but I had to do something.  The code wasn’t pretty, and it took me three days, but it’s something.  My time is running out (I didn’t think I’d get all 25 languages in 25 days, but there’s still a chance if I motor on up.

I give myself a D- on this one.  I gave up early with Forth, and only with perseverance did I go through with Bash.  I learned some stuff about Bash (knowing I don’t want to do any significant programming in it), like how it handles return values (it doesn’t) and how it handles parameters of functions.

 

Next up, I’ll be trying Swift for Day 19 (assuming I don’t run into any toolchain problems)

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s