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

Advertisements

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 8 (c++)

Previous:

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 8

Start: 12/9/2016

Finish 12/9/2016

Language: C++

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 has been my favorite challenge so far.  So I decided to dip a bit into my wheelhouse with C++, and see if I could complete Day 8. I’m a little worried about using languages I know (C++, Javascript and Python) so early, as all I have left that I’m truly comfortable with is Elixir.

Anyway, this challenge was all about manipulating pixels to be on or off on a screen.  You could turn all the pixels in a rectangle on (starting at upper left corner), or you could rotate the pixels to the right on a row (overflowing to the beginning of the rote), or rotate a column of pixels down (with overflow going to the top of the column).

Let’s take a look at the (rather verbose) C++ code


#include <algorithm>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <iterator>
#include <ostream>
#include <numeric>
#include <regex>
#include <sstream>
#include <string>
#include<<vector>

class Pixel
{
public:
    bool on;
    friend std::ostream& operator<<( std::ostream& stream, const Pixel &p);
};

std::ostream& operator<<(std::ostream & stream, const Pixel & p)
{
    stream << (p.on ? "*" : ".");
    return stream;
}

class Panel
{  
public:
    typedef std::vector Row;
    typedef std::vector Rows;
   
    Panel(uint8_t width, uint8_t height);
    void rect(uint8_t width, uint8_t height);
    void rotateColumn(uint8_t columnNumber, uint8_t num);
    std::vector getColumn(uint8_t columnNumber) const;
    void applyColumn(uint8_t columnNumber, std::vector column);

    void rotateRow(uint8_t rowNumber, uint8_t num);
    uint16_t getNumberOfPixelsLit() const;
    

    friend std::ostream& operator<<(std::ostream& stream, Panel panel);

private:
    Row makeRow(uint8_t width);
    
    Rows rows;

};

Panel::Panel(uint8_t width, uint8_t height) :
        rows(height, makeRow(width))
{
}

Panel::Row Panel::makeRow(uint8_t width)
{
    return Panel::Row(width, Pixel{false});
}

std::ostream& operator<<(std::ostream& stream, Panel panel)
{
    std::for_each(panel.rows.begin(), panel.rows.end(), [&stream](Panel::Row & row){
        std::copy(row.begin(), row.end(), std::ostream_iterator(stream));
        stream <<"\n";
    });
    return stream;
}

void Panel::rect(uint8_t width, uint8_t height)
{
    auto turnOnPixel = [](Pixel & p){p.on = true;};
    auto turnOnRowPixel = [turnOnPixel, width](Row & row){ 
        std::for_each(row.begin(), row.begin() + width, turnOnPixel);
    };
    std::for_each(rows.begin(), rows.begin() + height, turnOnRowPixel);
}

void Panel::rotateColumn(uint8_t columnNumber, uint8_t num)
{
    std::vector column = getColumn(columnNumber);
    std::rotate(column.rbegin(), column.rbegin()+num, column.rend() );
    applyColumn(columnNumber, column);
}

void Panel::rotateRow(uint8_t rowNumber, uint8_t num)
{
    auto& row = rows[rowNumber];
    std::rotate(row.rbegin(), row.rbegin()+num, row.rend());
}
    

std::vector Panel::getColumn(uint8_t columnNumber) const
{
    std::vector pixels;
    auto getPixel = [columnNumber](const Row & row){
        return row[columnNumber];
    };
    std::transform(rows.begin(), rows.end(), std::inserter(pixels, pixels.begin()), getPixel);
    return pixels;
}

void Panel::applyColumn(uint8_t columnNumber, std::vector column)
{
    uint8_t index = 0;
    std::for_each(rows.begin(), rows.end(), [&index, columnNumber, &column](Row &row){
        row[columnNumber] = column[index++];
    });
}

uint16_t Panel::getNumberOfPixelsLit() const
{
    auto isOn = [](const Pixel & p) { return p.on;};
    auto getCount = [isOn](const Row & row){ return std::count_if(row.begin(), row.end(), isOn);};
    std::vector counts;
    std::transform(rows.begin(), rows.end(), std::inserter(counts, counts.begin()), getCount);
    return std::accumulate(counts.begin(), counts.end(), 0);
}

void applyRectOperationIfMatching(Panel & panel, std::string operation)
{
    std::smatch sm;
    std::regex regex("rect (\\d+)x(\\d+)");
    std::regex_match(operation, sm, regex);
    if (sm.size() == 3)
    {
        panel.rect(stoi(sm[1]), stoi(sm[2]));
    }
}

void applyRotateRowOperationIfMatching(Panel & panel, std::string operation)
{
    std::smatch sm;
    std::regex regex("rotate row y=(\\d+) by (\\d+)");
    std::regex_match(operation, sm, regex);
    if (sm.size() == 3)
    {
        panel.rotateRow(stoi(sm[1]), stoi(sm[2]));
    }
}

void applyRotateColumnOperationIfMatching(Panel & panel, std::string operation)
{
    std::smatch sm;
    std::regex rotateColumnRegex("rotate column x=(\\d+) by (\\d+)");
    std::regex_match(operation, sm, rotateColumnRegex);
    if (sm.size() == 3)
    {
        panel.rotateColumn(stoi(sm[1]), stoi(sm[2]));
    }
}

void applyOperationOnPanel(Panel & panel, std::string op)
{
    applyRectOperationIfMatching(panel, op);
    applyRotateRowOperationIfMatching(panel, op);
    applyRotateColumnOperationIfMatching(panel, op);
}

int main()
{
    Panel panel(50,6);
    std::ifstream infile; 
    infile.open("../day8.txt");
    std::string data;
    while(getline(infile, data))
    {
        applyOperationOnPanel(panel, data);
    }
    infile.close();;
    std::cout << panel << "\n" << panel.getNumberOfPixelsLit() << "\n";
}

Whew, that’s a lot.  First I created a Pixel class.  I could have just kept it a bool, but vector has weird behaviors in C++, so I didn’t want to run into anything strange.


class Pixel
{
public:
    bool on;
    friend std::ostream& operator<<( std::ostream& stream, const Pixel &p);
};

std::ostream& operator<<(std::ostream & stream, const Pixel & p)
{
    stream << (p.on ? "*" : ".");
    return stream;
}

 

Then I compose a panel, which has a member variable Rows (which is just a vector of type Row, which is a vector of Pixels.)  This gives me my 2-dimensional array of pixels, and I just had to define functions to operate on them.

Here’s the class declaration in entirety:


class Panel
{  
public:
    typedef std::vector Row;
    typedef std::vector Rows;
   
    Panel(uint8_t width, uint8_t height);
    void rect(uint8_t width, uint8_t height);
    void rotateColumn(uint8_t columnNumber, uint8_t num);
    std::vector getColumn(uint8_t columnNumber) const;
    void applyColumn(uint8_t columnNumber, std::vector column);

    void rotateRow(uint8_t rowNumber, uint8_t num);
    uint16_t getNumberOfPixelsLit() const;
    

    friend std::ostream& operator<<(std::ostream& stream, Panel panel);

private:
    Row makeRow(uint8_t width);
    
    Rows rows;

};

First up is rect:


void Panel::rect(uint8_t width, uint8_t height)
{
    auto turnOnPixel = [](Pixel & p){p.on = true;};
    auto turnOnRowPixel = [turnOnPixel, width](Row & row){ 
        std::for_each(row.begin(), row.begin() + width, turnOnPixel);
    };
    std::for_each(rows.begin(), rows.begin() + height, turnOnRowPixel);
}

Just a nested for each loop to turn on things.

Then I wrote how to rotate a row (thank god for the algorithm library)

 


void Panel::rotateRow(uint8_t rowNumber, uint8_t num)
{
    auto& row = rows[rowNumber];
    std::rotate(row.rbegin(), row.rbegin()+num, row.rend());
}

 

Then I had to write rotate Column, which was a bit tricker


void Panel::rotateColumn(uint8_t columnNumber, uint8_t num)
{
    std::vector column = getColumn(columnNumber);
    std::rotate(column.rbegin(), column.rbegin()+num, column.rend() );
    applyColumn(columnNumber, column);
}

I get the column of pixels as a vector, rotate it, and then re-apply it back to the pixels. HEre’s the get and apply functions. I created a temp vectors of pixels and got the entire column for the get function, and then I apply the column back in through a similar method.



std::vector Panel::getColumn(uint8_t columnNumber) const
{
    std::vector pixels;
    auto getPixel = [columnNumber](const Row & row){
        return row[columnNumber];
    };
    std::transform(rows.begin(), rows.end(), std::inserter(pixels, pixels.begin()), getPixel);
    return pixels;
}

void Panel::applyColumn(uint8_t columnNumber, std::vector column)
{
    uint8_t index = 0;
    std::for_each(rows.begin(), rows.end(), [&index, columnNumber, &column](Row &row){
        row[columnNumber] = column[index++];
    });
}

 

FInally, I have to get the number of pixels lit:



uint16_t Panel::getNumberOfPixelsLit() const
{
    auto isOn = [](const Pixel & p) { return p.on;};
    auto getCount = [isOn](const Row & row){ return std::count_if(row.begin(), row.end(), isOn);};
    std::vector counts;
    std::transform(rows.begin(), rows.end(), std::inserter(counts, counts.begin()), getCount);
    return std::accumulate(counts.begin(), counts.end(), 0);
}

 

Part 2

Part two was so easy, I didn’t have to change any code.  Luckily, I was printing the screen for debugging, and that’s all the puzzle required.  So, no code for day 2.

 

Wrap-up

I liked this problem and I liked the solution.  I was happy with using the algorithm library to try and do as little for loops as I could.  It was also the first time I used regex in C++, and I was happy to see that it wasn’t as obtuse as expected (looking at you, lambda expressions).

I grade myself a solid A on this one.  I got the first problem right on the first try, and it worked for the second problem too.  I tried to use C++’s type system well throughout, and it actually caught some bugs for me.

Next up, I’m going to try the stack-oriented language, Factor, for day 9.