Google HashCode 2016, Practice Round [w/ Code]

Hello everyone!

Alvise here, I wanted to post online my solution for the practice round of the 2016 Google HashCode challenge (consider leaving a feedback as a comment) !

I didn’t develop any particular solution, mine is very straight forward, so nothing fancy sorry! I will upload my solution but I strongly recommend you try your own heading over at the challenge page:

https://hashcode.withgoogle.com/

The problem was controlling a robot with few instructions (paint square or straight lines or erasing a single cell) to paint a given input image with the fewest instructions to the robot. The fewer instructions the better.
My first approach was like:

  1. Fit squares, from large to small
  2. Fit lines, large to small (same dimension for horizontal and vertical)
  3. Fit remaining single cells

And then I improved like:

  1. Fit squares, from large to medium
  2. Fit lines, large to medium (same dimension for horizontal and vertical)
  3. Fit special squares (squares 3×3 with a single missing value, resulting in 2 commands to be drawn: a paint_square + erase_cell)
  4. Fit squares, from medium to small
  5. Fit lines, medium to small (same dimension for horizontal and vertical)
  6. Fit remaining single cells

The fitting of squares and lines is done by using a 2d convolutional linear filter: kernels are represented by squares, columns or rows, with each cell of the kernal having a vlua of cell_v = 1 / kernel_size. Applied to the whole image (with border wrapping constant, meaning 0 when the filter look for data outside the image) the resulting filtered image has values equal to 1 (255 using unsigned char values) only where those filers finds filling squares or lines.

Here the resulting scores:

results

And the output of the program at execution time:

run

The code is available here:

// Alvise Memo, 10/2/2016. Submission for the Google Hashcode challenge 2016.
// Practice problem.
// The 13 is my birthday!!

#include <iostream>
#include <fstream>
#include <string>

// OpenCV include, for 2d filtering, debug visualization and loading.
#include <opencv2\opencv.hpp>

using namespace std;
using namespace cv;

// Loading input .in files into OpenCV Mat objects, straight-forward
Mat load(string s)
{
 string line;
 ifstream myfile(s);
 Mat r;
 bool first = true;
 if (myfile.is_open())
 {
 int n, m;
 myfile >> n >> m;
 r = Mat::zeros(n, m, CV_8UC1);

 getline(myfile, line);

 int row = 0;
 while (getline(myfile, line))
 {
 const char * c = line.c_str();

 for (int i = 0; i < m; i++)
 {
 if (c[i] == '#')
 {
 r.at<unsigned char>(row, i) = 255;
 }
 }
 row++;

 }
 myfile.close();
 }
 return r;
}

// This function look in the image for SQUARES of dimension starting from the biggest possible (determined
// by the size of the input image) UP TO a maximum dimension of N (not included!)
int fitSquaresUpTo(Mat & m, Mat & m2, int n, vector<string> & comm)
{
 int max_s = (m.rows < m.cols ? m.rows : m.cols);
 max_s += max_s % 2 - 1;

 if (max_s > 25)
 max_s = 25;


 int ret = 0;

 for (int i = max_s; i > n; i -= 2)
 {
 int k_size = i;
 Mat kernel = Mat::ones(i, i, CV_32FC1);
 kernel /= i * i;

 Mat out;
 filter2D(m, out, -1, kernel, Point(-1, -1), 0, BORDER_CONSTANT);



 double max = 255;
 int pos[2];
 while (max == 255)
 {
 minMaxIdx(out, NULL, &max, NULL, pos);

 if (max == 255)
 {
 Rect r = Rect(pos[1] - i / 2, pos[0] - i / 2, i, i);
 rectangle(out, r, Scalar(0), -1);
 rectangle(m, r, Scalar(0), -1);
 rectangle(m2, r, Scalar(0, 0, 255), -1);
 comm.push_back("PAINT_SQUARE " + to_string(pos[0]) + " " + to_string(pos[1]) + " " + to_string((i - 1) / 2));
 ret++;
 }
 }
 }

 //cout << ret << endl;

 return ret;
}

// This function look in the image for SQUARES of dimension starting from N and
// going down to the minimum value of 3 (less than 3 would be a SINGLE cell/pixel)
int fitSquaresDownFrom(Mat & m, Mat & m2, int n, vector<string> & comm)
{
 int max_s = n;
 max_s += max_s % 2 - 1;

 if (max_s > 25)
 max_s = 25;


 int ret = 0;

 for (int i = max_s; i > 2; i -= 2)
 {
 int k_size = i;
 Mat kernel = Mat::ones(i, i, CV_32FC1);
 kernel /= i * i;

 Mat out;
 filter2D(m, out, -1, kernel, Point(-1, -1), 0, BORDER_CONSTANT);



 double max = 255;
 int pos[2];
 while (max == 255)
 {
 minMaxIdx(out, NULL, &max, NULL, pos);

 if (max == 255)
 {
 Rect r = Rect(pos[1] - i / 2, pos[0] - i / 2, i, i);
 rectangle(out, r, Scalar(0), -1);
 rectangle(m, r, Scalar(0), -1);
 rectangle(m2, r, Scalar(0, 0, 255), -1);
 comm.push_back("PAINT_SQUARE " + to_string(pos[0]) + " " + to_string(pos[1]) + " " + to_string((i - 1) / 2));
 ret++;
 }
 }
 }

 //cout << ret << endl;

 return ret;
}

// Special function: looks for squares of dimension 3x3, with a SINGLE missing cell:
// it then adds two commands: one for drawing the full square and one for removing the missing cell.
int fitSquaresSpecial(Mat & m, Mat & m2, vector<string> & comm)
{
 int ret = 0;
 int i = 3;

 Mat kernel = Mat::ones(i, i, CV_32FC1);
 kernel /= i * i;

 Mat out;
 filter2D(m, out, -1, kernel, Point(-1, -1), 0, BORDER_CONSTANT);

 double max = 255;
 int pos[2];
 while (max > 225)
 {
 minMaxIdx(out, NULL, &max, NULL, pos);

 if (max > 225) // cubo da 9 meno spicchio
 {
 // Find missing cell position, LAZY!
 Point missing(-1, -1);
 for (int x = 0; x < 3; x++)
 {
 for (int y = 0; y < 3; y++)
 {
 if (m.at<unsigned char>(pos[0] - i / 2 + y, pos[1] - i / 2 + x) == 0)
 {
 assert(missing.x == -1);
 missing.x = pos[1] - i / 2 + x;
 missing.y = pos[0] - i / 2 + y;
 }
 }
 }
 if (missing.x == -1)
 {
 Rect r = Rect(pos[1] - i / 2, pos[0] - i / 2, i, i);
 rectangle(out, r, Scalar(0), -1);
 rectangle(m, r, Scalar(0), -1);
 rectangle(m2, r, Scalar(0, 0, 255), -1);
 comm.push_back("PAINT_SQUARE " + to_string(pos[0]) + " " + to_string(pos[1]) + " " + to_string((i - 1) / 2));
 ret++;
 }
 else
 {
 Rect r = Rect(pos[1] - i / 2, pos[0] - i / 2, i, i);
 rectangle(out, r, Scalar(0), -1);
 rectangle(m, r, Scalar(0), -1);
 rectangle(m2, r, Scalar(0, 0, 125), -1);
 rectangle(m2, Rect(missing.x, missing.y, 1, 1), Scalar(125, 125, 125));
 comm.push_back("PAINT_SQUARE " + to_string(pos[0]) + " " + to_string(pos[1]) + " " + to_string((i - 1) / 2));
 comm.push_back("ERASE_CELL " + to_string(missing.y) + " " + to_string(missing.x));
 ret += 2;
 }
 }
 }


 //cout << ret << endl;

 return ret;
}

// Same as before, fits horizontal and vertical lines instead of squares. Look fitSquaresUpTo
int fitLinesUpTo(Mat & m, Mat & m2, int n, vector<string> & comm)
{
 int max_s = (m.rows < m.cols ? m.cols : m.rows);
 max_s += max_s % 2 - 1;

 int ret = 0;

 for (int i = max_s; i >= n; i--)
 {
 {
 Mat kernel = Mat::ones(1, i, CV_32FC1);
 kernel /= i;

 Mat out;
 filter2D(m, out, -1, kernel, Point(-1, -1), 0, BORDER_CONSTANT);

 double max = 255;
 int pos[2];
 while (max == 255)
 {
 minMaxIdx(out, NULL, &max, NULL, pos);

 if (max == 255)
 {
 Point r1 = Point(pos[1] - i / 2, pos[0]);
 Point r2 = Point(pos[1] + i / 2 - (1 - i % 2), pos[0]);

 line(out, r1, r2, Scalar(0));
 line(m, r1, r2, Scalar(0));
 line(m2, r1, r2, Scalar(0, 125, 125));
 comm.push_back("PAINT_LINE " + to_string(r1.y) + " " + to_string(r1.x) + " " + to_string(r2.y) + " " + to_string(r2.x));
 ret++;
 }
 }
 }
 if (i < m.rows)
 {
 Mat kernel = Mat::ones(i, 1, CV_32FC1);
 kernel /= i;

 Mat out;
 filter2D(m, out, -1, kernel, Point(-1, -1), 0, BORDER_CONSTANT);

 double max = 255;
 int pos[2];
 while (max == 255)
 {
 minMaxIdx(out, NULL, &max, NULL, pos);

 if (max == 255)
 {
 Point r1 = Point(pos[1], pos[0] - i / 2);
 Point r2 = Point(pos[1], pos[0] + i / 2 - (1 - i % 2));

 line(out, r1, r2, Scalar(0));
 line(m, r1, r2, Scalar(0));
 line(m2, r1, r2, Scalar(125, 125, 0));
 comm.push_back("PAINT_LINE " + to_string(r1.y) + " " + to_string(r1.x) + " " + to_string(r2.y) + " " + to_string(r2.x));
 ret++;
 }
 }
 }
 }


 //cout << ret << endl;

 return ret;
}

// Same as before, fits horizontal and vertical lines instead of squares. Look fitSquaresDownFrom
int fitLinesDownFrom(Mat & m, Mat & m2, int n, vector<string> & comm)
{
 int max_s = n;
 max_s += max_s % 2 - 1;

 int ret = 0;

 for (int i = max_s; i > 1; i--)
 {
 {
 Mat kernel = Mat::ones(1, i, CV_32FC1);
 kernel /= i;

 Mat out;
 filter2D(m, out, -1, kernel, Point(-1, -1), 0, BORDER_CONSTANT);

 double max = 255;
 int pos[2];
 while (max == 255)
 {
 minMaxIdx(out, NULL, &max, NULL, pos);

 if (max == 255)
 {
 Point r1 = Point(pos[1] - i / 2, pos[0]);
 Point r2 = Point(pos[1] + i / 2 - (1 - i % 2), pos[0]);

 line(out, r1, r2, Scalar(0));
 line(m, r1, r2, Scalar(0));
 line(m2, r1, r2, Scalar(0, 125, 125));
 comm.push_back("PAINT_LINE " + to_string(r1.y) + " " + to_string(r1.x) + " " + to_string(r2.y) + " " + to_string(r2.x));
 ret++;
 }
 }
 }
 if (i < m.rows)
 {
 Mat kernel = Mat::ones(i, 1, CV_32FC1);
 kernel /= i;

 Mat out;
 filter2D(m, out, -1, kernel, Point(-1, -1), 0, BORDER_CONSTANT);

 double max = 255;
 int pos[2];
 while (max == 255)
 {
 minMaxIdx(out, NULL, &max, NULL, pos);

 if (max == 255)
 {
 Point r1 = Point(pos[1], pos[0] - i / 2);
 Point r2 = Point(pos[1], pos[0] + i / 2 - (1 - i % 2));

 line(out, r1, r2, Scalar(0));
 line(m, r1, r2, Scalar(0));
 line(m2, r1, r2, Scalar(125, 125, 0));
 comm.push_back("PAINT_LINE " + to_string(r1.y) + " " + to_string(r1.x) + " " + to_string(r2.y) + " " + to_string(r2.x));
 ret++;
 }
 }
 }
 }


 //cout << ret << endl;

 return ret;
}

// Look in the image for a SINGLE cell, a square with dimension of 1x1
int fitSingles(Mat & m, Mat & m2, vector<string> & comm)
{
 int ret = 0;

 for (int x = 0; x < m.cols; x++)
 {
 for (int y = 0; y < m.rows; y++)
 {
 if (m.at<unsigned char>(y, x) == 255)
 {
 m.at<unsigned char>(y, x) = 0;
 m2.at<Vec3b>(y, x) = Vec3b(255, 0, 0);
 comm.push_back("PAINT_SQUARE " + to_string(y) + " " + to_string(x) + " 0");
 ret++;
 }
 }
 }
 return ret;
}

// Analyze script version 1
int analyzeVersion1(std::string name)
{
 Mat m_c = load(name);
 cv::imwrite(name + "input.png", m_c);
 
 Mat m_r = Mat::zeros(m_c.size(), CV_8UC3);
 vector<string> commands;

 int points = m_c.rows * m_c.cols;

 points -= fitSquaresUpTo(m_c, m_r, 2, commands);
 points -= fitLinesUpTo(m_c, m_r, 2, commands);
 points -= fitSingles(m_c, m_r, commands);

 cout << points << endl;

 
 cv::imwrite(name + "solved.png", m_r);

 ofstream fileOut;
 fileOut.open(name + "comm.txt");
 fileOut << commands.size() << "\n";
 for each (string s in commands)
 fileOut << s << "\n";
 fileOut.close();

 return points;
}

// Analyze script version 2
int analyzeVersion2(std::string name, int i, int j)
{
 Mat m_c = load(name);
 cv::imwrite(name + "input.png", m_c);
 
 Mat m_r = Mat::zeros(m_c.size(), CV_8UC3);
 vector<string> commands;

 int points = m_c.rows * m_c.cols;

 points -= fitSquaresUpTo(m_c, m_r, i, commands);
 points -= fitLinesUpTo(m_c, m_r, j, commands);

 points -= fitSquaresSpecial(m_c, m_r, commands);

 points -= fitSquaresDownFrom(m_c, m_r, i, commands);
 points -= fitLinesDownFrom(m_c, m_r, j, commands);

 points -= fitSingles(m_c, m_r, commands);

 cout << points << endl;

 cv::imwrite(name + "solved.png", m_r);

 ofstream fileOut;
 fileOut.open(name + "comm.txt");
 fileOut << commands.size() << "\n";
 for each (string s in commands)
 fileOut << s << "\n";
 fileOut.close();

 return points;
}

// Entry of the software
int main(int argc, char ** argv)
{
 std::cout << "Practice test." << std::endl;
 std::cout << "The 13/02 is my birthday!!" << std::endl;

 int total = 0;

 std::cout << "Analyze learn_and_teach.in" << std::endl;
 total += analyzeVersion2("learn_and_teach.in", 9, 4);

 std::cout << "Analyze logo.in" << std::endl;
 total += analyzeVersion1("logo.in");

 std::cout << "Analyze right_angle.in" << std::endl;
 total += analyzeVersion2("right_angle.in", 5, 3);

 cout << total << endl;

 std::getchar();
}

 

Output (Red: square, Senape:horizontal line, Acqua:vertical line, Blue: single square, Grey:erased cell)

right_angle.ininput right_angle.insolved

learn_and_teach.ininput learn_and_teach.insolved

logo.ininputlogo.insolved

 

Advertisements

3 thoughts on “Google HashCode 2016, Practice Round [w/ Code]

  1. evandrix

    Part of your posted solution is invalid C++ code:
    ““
    for each (string s in commands)
    fileOut << s << "\n";
    ““

    Also, unescape the HTML entities please.

    Liked by 1 person

    Reply
    1. Alvise Post author

      Hi and thanks for checking this article out!!
      That code works for me (not the prettiest I admit) and I’m using VS2015, msvc14 c++11.

      If you give me more insight of what’s not working for you maybe we can find the solution?

      Like

      Reply

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s