AoC recap and Looking towards 2019

So for the first time ever, I have finished Advent Of Code.

 The Highs

  • Man it felt good to complete it AoC for once.  Finishing that last challenge, watching the animations, and reading the final piece of the story gave me such a feeling of accomplishment, that I just had to step back from my computer and grin.
  • There were some really diverse challenges that I had fun working through.  Recursive solutions, mapping 3d space, transpiling custom assembly, I definitely had my work cut out for me.
  • I got to learn way more than I thought I was going to in Python.  I knew itertools was awesome, but I got to learn some new things (accumulate, chain.from_iterable).  I also got to play with Counter for the first time.  And I got to play with mypy, which gives you type annotations.

 The Lows

  • Not everything was hunky dory.  For instance, Day 15. Day 15 took me days to do.  There were some very specific edge cases that I had to work out.
  • Day 17 was tricky too, but I ended up liking that one, but it took a little bit to figure out as well.
  • Day 23.  Oh Day 23.  I almost quit due to day 23.  I had an idea, but I knew it wasn’t mathematically sound.  I didn’t understand any of the things they were saying on reddit for this problem.  Eventually I figured out how to make my solution work with the math, but it was rough.

Continue reading

Advertisements

Advent of Code 2018 Week 1: Recap

So I’ve decided to do Advent of Code this year again (no surprise there), but this time, I’m encouraging everyone in HSV.py to join me as well.

I’ve completed 8 challenges, and thought it was time for a recap.  I plan on breaking down solutions day by day, and then ending with some lessons learned that might help others.  I compete each night with ugly hacked together code, then work on refactoring it the next day.  What I share is the refactored version (Don’t think I spit something like this out in just an hour).  You can find all my code on my GitHub

So let’s get started.

Continue reading

AdventOfCode2017 Day 5 and 6

Another two days down, no sweat (minus a segfault on day 6, but shhhh.)

Day 5’s challenge was to take a list of jump offsets and determine how many jumps you need to take before exiting the block of code (modifying the jump offsets each time)

Day 6’s challenge was to take a list of memory banks, run through a balancing algorithm regarding allocations, and count how many steps until an infinite loop.

Let’s take a look at the code, as they clock in at <40 lines apiece.

Continue reading

AdventOfCode2017 – Day 4

Hooray, another easy one.  After Day number 3, I could certainly use it.  This challenge involved taking a list of passphrases, and counting up the number of passphrases that had no duplicate words.   This seems simple, just a split, sort and application of std::unique.

Part 2 had me check for anagrams rather than duplicate words.  This was also easy, as I could map over a sort function to each word in the passphrase, and then check for uniqueness.

Let’s look at the code


#include <algorithm>
#include <iostream>
#include <string>

#include "algo.h"
#include "input.h"

std::string sortString(std::string s) {
    std::sort(s.begin(), s.end());
    return s;
}

bool isUnique(const std::string& passphrase) {
    auto words = algo::map(input::split(passphrase), sortString);
    std::sort(words.begin(), words.end());
    return words.end() == std::unique(words.begin(), words.end());
}

int main() {
    auto passPhrases = input::readMultiLineFile("input/input04.txt");
    auto count = std::count_if(passPhrases.begin(), passPhrases.end(), isUnique);
    std::cout << count << "\n";
    return 0;
}

Super straight forward.  I think the trickiest thing was std::unique, because I didn’t realize it returned the end iterator of the range.  But once I figured that out, this wasn’t so bad.

Stay tuned for day 5!

AdventOfCode2017 Day 3

So this day was a tad bit rougher.  I wasn’t expecting the sudden difficulty increase on day 3.  The problems were straight-forward enough, but I didn’t want to brute force my way through them.  Unfortunately, I didn’t get the math worked out, so brute force became one of my last options

However, on the bright side, I got to play with std::optional, so I got that going for me.

 

I’m going to have a tough time explaining the problem any better than advent of code, so I’m just going to link you there instead

Continue reading

AdventOfCode2017 Days 1 and 2

It’s December and you know what that means!  Advent Of Code is back!.

This year, I’m not going to try the 25 languages in 25 days, but instead focus on my C++ skills.  More specifically, here are the constraints I am putting on myself.

  • Use C++17 where I can if it makes sense
  • Avoid raw loops on containers unless I have a performance concern
  • If there are any raw loops needed, see if it can be abstracted into a generic algorithm

So Challenge 1: here we go. Continue reading

Advent Of Code 2016 Day 21 (PHP)

Advent of Code 2016 Day 20 (F#)
Advent of Code 2016 – Day 19 (Swift)

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 20

Start: 1/6/2016

Finish 1/7/2017

Language: PHP

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 challenge was to take a string, and apply a series of transformations on it (Swapping letters, rotating, reversing, etc.)

My idea was to keep an array where the head pointer moves around based on rotations, and operating based on that (similar to the idea of a circular array)

 

Part 1

Code Code Code ……


<?php

$head = 0;
$arr = array("a", "b", "c", "d", "e", "f", "g", "h");

function convertIndex($index){
    global $arr, $head;
    $newIndex = $index+$head;
    while($newIndex < 0){
        $newIndex += sizeof($arr);
    }
    return  $newIndex%sizeof($arr);
}
function getCharAt($index)
{
    global $arr, $head;
    $newIndex =convertIndex($index);
    return $arr[$newIndex];
}

function setCharAt($index, $value)
{
    global $arr, $head;
    $arr[convertIndex($index)] = $value;
}

function swapPos($pos1, $pos2) {
    $tmp1 = getCharAt($pos1);
    $tmp2 = getCharAt($pos2);
    setCharAt($pos1, $tmp2);
    setCharAt($pos2, $tmp1);
}

function swapLetters($letter1, $letter2) {
    global $arr;
    $index1 = array_search($letter1, $arr);
    $index2 = array_search($letter2, $arr);
    $arr[$index2] = $letter1;
    $arr[$index1] = $letter2;
}

function reverse($pos1, $pos2) {
    for ($i = $pos1, $j=$pos2; $i < $j; $i++, $j--){
        swapPos($i, $j);
    }
}

function printArray() {
    global $arr;
    for ($i = 0; $i < sizeof($arr); $i++){
        echo getCharAt($i);
    }
    echo "\n";
}

function rotateLeft($steps)
{
    global $head;
    $head += $steps;
}

function rotateRight($steps)
{
    global $head;
    $head -= $steps;
}

function move($from, $to) {
    global $arr;
    
    if ($to =$to; $i--){ 
            $newChar = getCharAt($i);
            setCharAt($i, $char);
            setCharAt($i+1, $newChar);
        }
    }
    else {
        $char = getCharAt($from);
        for ($i = $from+1; $i<=$to; $i++){ 
            $newChar = getCharAt($i);
            setCharAt($i, $char);
            setCharAt($i-1, $newChar);
        }
    }
}

function rotatePos($letter) {
    global $arr, $head;
    $index = 0;
    for ($i = 0; $i = 4) {
        $index += 1;
    }
    rotateRight($index+1);
}

function getLines() {
    $f = fopen("../day21.txt", "r");
    $lines = array();
    while (($buffer = fgets($f)) !== false) {
        $lines[] = trim($buffer);
    }
    fclose($f);
    return $lines;
}

function processLine($line) {
    $words = explode(" ", $line);
    if($words[0] == "swap" && $words[1] =="position"){
        swapPos($words[2], $words[5]);
    }
    if($words[0] == "swap" && $words[1] =="letter"){
        swapLetters($words[2], $words[5]);
    }
    if($words[0] == "rotate" && $words[1] =="left"){
        rotateLeft($words[2]);
    }
    if($words[0] == "rotate" && $words[1] =="right"){
        rotateRight($words[2]);
    }
    if($words[0] == "rotate" && $words[1] =="based"){
        rotatePos($words[6]);
    }
    if($words[0] == "reverse"){
        reverse($words[2], $words[4]);
    }
    if($words[0] == "move"){
        move($words[2], $words[5]);
    }
}


$lines = getLines();
foreach($lines as $line){   
    processLine($line);
}
printArray();
?>

This was my first foray in PHP in quite some time.  It was a bit more verbose than I remembered, but I still got this one relatively easy.

The main loop was easy, as it mostly took things line by line by line, and then chose a transformation based on the text.

Most transformations are straight forward.  I keep a global array and head pointer, along with a way to convert indices, get characters and set characters in the array.


$head = 0;
$arr = array("a", "b", "c", "d", "e", "f", "g", "h");

function convertIndex($index){
    global $arr, $head;
    $newIndex = $index+$head;
    while($newIndex < 0){
        $newIndex += sizeof($arr);
    }
    return  $newIndex%sizeof($arr);
}
function getCharAt($index)
{
    global $arr, $head;
    $newIndex =convertIndex($index);
    return $arr[$newIndex];
}

function setCharAt($index, $value)
{
    global $arr, $head;
    $arr[convertIndex($index)] = $value;
}

Swapping based on positions and swapping based on letters are pretty straight forward



function swapPos($pos1, $pos2) {
    $tmp1 = getCharAt($pos1);
    $tmp2 = getCharAt($pos2);
    setCharAt($pos1, $tmp2);
    setCharAt($pos2, $tmp1);
}

function swapLetters($letter1, $letter2) {
    global $arr;
    $index1 = array_search($letter1, $arr);
    $index2 = array_search($letter2, $arr);
    $arr[$index2] = $letter1;
    $arr[$index1] = $letter2;
}

Reversing and Rotating were also pretty easy.


function reverse($pos1, $pos2) {
    for ($i = $pos1, $j=$pos2; $i < $j; $i++, $j--){
        swapPos($i, $j);
    }
}

function rotateLeft($steps)
{
    global $head;
    $head += $steps;
}

function rotateRight($steps)
{
    global $head;
    $head -= $steps;
}

Once we get into moving (removing from one index and inserting in the other index), it took me a little while longer to get this.  I treat moving differently based on which direction I’m going to, and then I effectively “bubble” the values to the appropriate position.  I originally tried to do array slicing and recombining, but my wonky index recalculations made it tricky.


function move($from, $to) {
    global $arr;
    
    if ($to =$to; $i--){ 
            $newChar = getCharAt($i);
            setCharAt($i, $char);
            setCharAt($i+1, $newChar);
        }
    }
    else {
        $char = getCharAt($from);
        for ($i = $from+1; $i<=$to; $i++){ 
            $newChar = getCharAt($i);
            setCharAt($i, $char);
            setCharAt($i-1, $newChar);
        }
    }
}

Lastly, I worked on the rotate based on the position of a letter.  I pretty much searched for the letter in my array, then figured out how many rotations needed to happen.


function rotatePos($letter) {
    global $arr, $head;
    $index = 0;
    for ($i = 0; $i = 4) {
        $index += 1;
    }
    rotateRight($index+1);
}

 

Part 2

This part was to unscramble a password rather than scramble a password.  I reversed the lines of code, and reversed the relevant sections (such as rotating left when the command is rotate right)


function processLine($line) {
    $words = explode(" ", $line);
    if($words[0] == "swap" && $words[1] =="position"){
        swapPos($words[2], $words[5]);
    }
    if($words[0] == "swap" && $words[1] =="letter"){
        swapLetters($words[2], $words[5]);
    }
    if($words[0] == "rotate" && $words[1] =="left"){
        rotateRight($words[2]);
    }
    if($words[0] == "rotate" && $words[1] =="right"){
        rotateLeft($words[2]);
    }
    if($words[0] == "rotate" && $words[1] =="based"){
        rotatePos($words[6]);
    }
    if($words[0] == "reverse"){
        reverse($words[2], $words[4]);
    }
    if($words[0] == "move"){
        move($words[5], $words[2]);
    }
}

The tricky part of this one was figuring out how the rotate based on the position of a letter was handled.  Based on some pen and paper calculations, I found a way to derive how many rotations were needed to get to the next password


function rotatePos($letter) {
    global $arr, $head;
    $index = 0;
    for ($i = 0; $i < sizeof($arr); $i++){
        if (getCharAt($i) == $letter) {
            $index = $i;
            break;
        }
    }
    $numRotations=0;
    for ($j = 0; $j < sizeof($arr); $j++) {
        if ($j = 4 && ($j + $j + 2) % sizeof($arr) == $index) {
            $numRotations = $j+2;
            break;
        }
    }
    rotateLeft($numRotations);
}

 

Wrap-up

I had a lot of stupid mistakes in my part 2.  I kept not thinking through the problem.  Also PHP’s verbosity was weighing me down.  I felt like the array functions were clunky, and my code endd up all over the place.

I give myself a B- on this one.  I could have done better, and thought through the problems better.  My PHP code isn’t great either, so I wasn’t satisfied with this, but it’s better than some other ones.

Next up, is Day 22 with Elm.