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.

 

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