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 9

Start: 12/11/2016

Finish 12/11/2016

Language: Factor

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

Hoo boy.   This was a rough one.  It wasn’t too bad of a sounding problem (dealing with string expansion in compress/decompress encodings), but I chose Factor today.  I understand the idea of a stack-oriented concatenative language, and writing in it definitely makes you appreciate a stack.  I think these type of languages offer a great insight into how powerful composability is, but if you are sloppy in them, it will come back to haunt you.

So as I said, we were expanding strings.  There were (AxB) strings littered through the code, and they indicated how much a string should be expanded.  For instance(4×2)ABCD should transform into ABCDABCD (the following four characters repeated twice).

I started out with a few false starts.  First I wanted to write a state-machine, but that went nowhere.  Then I started trying to do a whole lot of regular expressions, and that didn’t help either (I can’t figure out how capture groups work in Factor).  So after two deletes of the file that I was writing (both the best and worst feeling in the world), here’s what I came up with (It’s a doozy and I’m not proud of it)

USE: accessors
USE: io
USE: io.encodings.utf8
USE: io.files
USE: kernel
USE: math
USE: math.parser
USE: pairs
USE: prettyprint
USE: regexp
USE: sequences
USE: splitting
USE: strings


IN: challenge1

: get-match ( str -- match ) R/ \((\d+)x(\d+)\)/ first-match ;
: extract-first-number ( str -- x ) dup R/ \d+x/ first-match [ from>> ] [ to>> 1 - ] bi pick subseq nip string>number ;
: extract-second-number ( str -- x ) dup R/ x\d+/ first-match [ from>> 1 + ] [ to>> ] bi pick subseq nip string>number ;
: extract-numbers ( str -- sel rep ) [ extract-first-number ] [ extract-second-number ] bi ;

: split-on-match ( match -- a b c match ) [ [ 0 ] 
                                    [ from>> ] 
                                    [ seq>> ] 
                                    tri subseq ] 
                                  [ [ from>> ] 
                                    [ to>> ] 
                                    [ seq>> ] 
                                    tri subseq extract-numbers * 48  ] 
                                  [ [ [ to>> ]
                                      [   
                                        [ from>> ] 
                                        [ to>> ] 
                                        [ seq>> ] 
                                        tri subseq extract-numbers  drop ]
                                      bi 
                                       + ] 
                                    [ seq>> length ] 
                                    [ seq>> ] 
                                    tri subseq  ] 
                                 tri  ;
: decompress ( str -- str ) dup get-match dup f eq? [ drop ] [ nip split-on-match decompress append append nip ] if ;
: read-file ( file-path encoding -- file-contents ) file-contents ;

"../day9.txt" utf8 read-file decompress dup . length .

First let’s talk about the regex handling.  Given the string, I wanted a way to grab the regular expression that matched (AxB) where A and B were numbers, and then have ways to get those two numbers out if I needed them.

: get-match ( str -- match ) R/ \((\d+)x(\d+)\)/ first-match ;
: extract-first-number ( str -- x ) dup R/ \d+x/ first-match [ from>> ] [ to>> 1 - ] bi pick subseq nip string>number ;
: extract-second-number ( str -- x ) dup R/ x\d+/ first-match [ from>> 1 + ] [ to>> ] bi pick subseq nip string>number ;
: extract-numbers ( str -- sel rep ) [ extract-first-number ] [ extract-second-number ] bi ;

Like I said not pretty, but wait for the behemoth that is coming up next.

I wrote a decompress function, that takes in a string, splits it into it’s three parts (before the (AxB), the (AxB) and A characters after the (AxB).  I took the AxB and replaced it with A*B instances of the 0 character

: split-on-match ( match -- a b c match ) [ [ 0 ] 
                                    [ from>> ] 
                                    [ seq>> ] 
                                    tri subseq ] 
                                  [ [ from>> ] 
                                    [ to>> ] 
                                    [ seq>> ] 
                                    tri subseq extract-numbers * 48  ] 
                                  [ [ [ to>> ]
                                      [   
                                        [ from>> ] 
                                        [ to>> ] 
                                        [ seq>> ] 
                                        tri subseq extract-numbers  drop ]
                                      bi 
                                       + ] 
                                    [ seq>> length ] 
                                    [ seq>> ] 
                                    tri subseq  ] 
                                 tri  ;
: decompress ( str -- str ) dup get-match dup f eq? [ drop ] [ nip split-on-match decompress append append nip ] if ;

For the A characters after the AxB, I recursed into decompress so that I could handle more than one decompression.

I then joined the strings back up and took their length.

: decompress ( str -- str ) dup get-match dup f eq? [ drop ] [ nip split-on-match decompress append append nip ] if ;

 

Part 2.

So now, we had to do recursive expansion inside any expanded text.  I stared at my computer a good long time trying to figure out how to mess with my ugly Factor code (the language isn’t ugly, it has a simple beauty to it like LISP does, but when I write, it sure is ugly).  Well I ended up making it uglier.

I changed decompress to return a length instead of the entire string:

: decompress ( str -- len ) dup get-match dup f eq? [ drop length ] [ nip split-on-match decompress dup fixnum? [  ] [ length ] if + + nip ] if ;

and I also changed how I handled the (AxB) expansion.  Instead of filling in with a set number of zeros, I had to grab the actual text, decompress it, and then multiply it by the B in (AxB).

                           [ ! length of the matched segment - b
                                    [ 
                                       ! selection number
                                       [ from>> ] 
                                       [ to>> ] 
                                       [ seq>> ] 
                                       tri subseq extract-numbers nip 
                                    ]
                                    
                                    [  ! repetition number
                                        [ from>> ] 
                                        [ to>> ] 
                                        [ seq>> ] 
                                        tri subseq extract-numbers drop 
                                    ] 
                                    [ ! everything after the (AxB) (up to x characters)
                                      [ to>> ]
                                      [ [ to>> ]
                                        [ [ from>> ] 
                                          [ to>> ] 
                                          [ seq>> ] 
                                          tri subseq extract-numbers drop  
                                        ]
                                        bi
                                        + 
                                      ] 
                                      [ seq>> ] 
                                      tri subseq  
                                    ]
                                    ! decompress the sequence
                                     tri decompress nip  * 
                                  ] 

 

Wrap-up

I’m sorry.  I really am.  This code was bad.  It wasn’t Factor’s fault.  I didn’t extract enough things out to functions, I didn’t plan out my stack calls with care.  I ended up having to do a lot of swapping, duping, and dropping to massage the stack in a way that was coherent.   I feel like there is elegant Factor that can be written for this problem (prove me right, Internet), but with this being my first Factor solution ever, I’m happy that this just worked.

The problem was a real fun problem, and I feel like I squandered some time doing it in a language that challenged me.  But that’s the point of this.  To challenge me, and I’m glad I did some Factor.  I’m just hoping that when I roll around to Forth, I write a bit better code.

Overall grade: C-.  I had to delete code a whole lot, and just scrolling through, I say it’s ugly.  I got the answers on the first try of submit each time, so that’s something, but I’m not proud of the code.

Tomorrow, I’m going to tackle Day 10 with OcaML.  Another new language.   Should be interesting :).