What spot in Manhattan is farthest from any subway stop?

January 25, 2012, 6:09 am

I thought I’d have a crack and writing some code to answer this Quora question.

Here is the resulting map, pixel value (grey scale) indicates pixel distance from nearest subway station:

I’m afraid the overlay is a bit of a mess, I’ll try and fix this tomorrow. But according to this map the answer is the far corner of Battery Park.

Here’s the code I used:


#include <png++/png.hpp>
#include <iostream>
#include <math.h>

using namespace std;

bool is_black(png::image< png::rgba_pixel > &image,size_t x,size_t y) {

  if(((image[y][x].red == 0) && (image[y][x].green == 0) && (image[y][x].blue == 0))) return true;

  return false;
}

int get_distance(int x,int y,int cx,int cy) {
  int xd = (cx-x);
  if(xd<0) xd = 0-xd;

  int yd = cy-y;
  if(yd<0) yd = 0-yd;

  return sqrt((xd*xd)+(yd*yd));
}

int get_nextdist(png::image< png::rgba_pixel > &image,size_t xin,size_t yin) {

  int x = xin;
  int y = yin;

  int mindist = 10000;
  for(int cx=(x-500);cx<(x+500);cx++) {
    for(int cy(y-500);cy<(y+500);cy++) {

      if((cx > 0) && (cy > 0) && (cx < image.get_width()) && (cy < image.get_height())) {

        if(is_black(image,cx,cy)) {
          int dist = get_distance(x,y,cx,cy);
          if(dist < mindist) mindist = dist;
        }

      }
    }
  }

  return mindist;
}


int main() {

  png::image< png::rgba_pixel > image("input.png");

  // Make image black and white.
  for (size_t y = 0; y < image.get_height(); ++y) {
    for (size_t x = 0; x < image.get_width(); ++x) {
      if(((image[y][x].red <  80 ) && (image[y][x].green <  80 ) && (image[y][x].blue <  80 ) && (image[y][x].alpha != 0)) ||
         ((image[y][x].red == 255) && (image[y][x].green == 255) && (image[y][x].blue == 255) && (image[y][x].alpha != 0))) {
        image[y][x] = png::rgba_pixel(0, 0, 0);
      } else {
        image[y][x] = png::rgba_pixel(255, 255, 255);
      }
    }
  }

  png::image< png::rgba_pixel > oimage = image;
  // Filter out isolated pixels...
  for (size_t y = 1; y < (image.get_height()-1); ++y) {
    for (size_t x = 1; x < (image.get_width()-1); ++x) {
      if(is_black(oimage,x,y)) {
        int adj = 0;
        if(is_black(oimage,x+1,y  )) {adj++; }
        if(is_black(oimage,x-1,y  )) {adj++; }
        if(is_black(oimage,x  ,y+1)) {adj++; }
        if(is_black(oimage,x  ,y-1)) {adj++; }
        if(adj > 3) {
          // do nothing...
          image[y][x] = png::rgba_pixel(0, 0, 0,255);
        } else {
          image[y][x] = png::rgba_pixel(255, 255, 255,255);
        }
      }
    }
  }


  oimage = image;
  // Set each pixel value to min distance to nearest pixel.

  for (size_t y = 0; y < image.get_height(); ++y) {
    for (size_t x = 0; x < image.get_width(); ++x) {
      if(!is_black(oimage,x,y)) {
        cout << "processing: " << x << "," << y << endl;

        int distance = get_nextdist(oimage,x,y);

        image[y][x] = png::rgba_pixel(distance, distance, distance,255);
      }
    }
  }


 image.write("output.png");
}

Assorted files used…

Input to the above code:

Original image:

Maps from:
http://www.mta.info/nyct/maps/submap.htm (cropped from PDF).

Category: Uncategorized  |  1 Comment

Working with PNG files in C++

January 25, 2012, 2:46 am

I’m working on MacOS X, so first of all I need to compile and install the libraries (libpng and png++):

#Download here: http://prdownloads.sourceforge.net/libpng/libpng-1.5.7.tar.gz?download
tar xvzf libpng-1.5.7.tar.gz
cd libpng-1.5.7
./configure
make
sudo make install

#Download png++
curl http://download.savannah.nongnu.org/releases/pngpp/png++-0.2.5.tar.gz > ./png++.tar.gz
tar xzvf png++.tar.gz
cd png++-0.2.5
make
sudo make install

Everything should be installed now, and we can write some code. Create the following C++ program:

#include <png++/png.hpp>

int main() {

  png::image< png::rgb_pixel > image("input.png");

  for (size_t y = 0; y < image.get_height(); ++y) {
    for (size_t x = 0; x < image.get_width(); ++x) {
      if(((x+y)%2) == 0) image[x][y] = png::rgb_pixel(0, 0, 0);
    }
  }

 image.write("output.png");
}

The program loads a file called input.png, sets every other pixel to black and writes it to output.png. Compile and run as follows:

g++ test.cpp -lpng
./a.out
Category: Uncategorized  |  Comment

Solving tic-tac-toe (Noughts and crosses)

January 20, 2012, 11:10 pm

The following is a simple recursive solver for tic-tac-toe games, which I used to answer a Quora question. It’s hardcoded to solve the board:

OO_
___
XX_

Here’s the code:

#include <vector>
#include <iostream>

using namespace std;

void dump_board(vector<vector<int> > &board) {

  for(size_t y=0;y<board.size();y++) {
    for(size_t x=0;x<board.size();x++) {
      if(board[x][y] == 0) cout << "_";
      if(board[x][y] == 1) cout << "O";
      if(board[x][y] == 2) cout << "X";
    }
    cout << endl;
  }
  cout << endl;
}

class Move {

public:

  Move() {}

  Move(int x_in,int y_in) : x(x_in), y(y_in) {}

  int x;
  int y;
};


int check_win(vector<vector<int> > &board) {

  // cols
  for(int x=0;x<board.size();x++) {
    bool win=true;
    for(int y=0;y<board[x].size();y++) {
      if(board[x][y] != board[x][0]) win = false;
    }
    if((board[x][0] != 0) && (win == true)) return board[x][0];
  }

  // rows
  for(int y=0;y<board.size();y++) {
    bool win=true;
    for(int x=0;x<board.size();x++) {
      if(board[x][y] != board[0][y]) win = false;
    }
    if((board[0][y] != 0) && (win == true)) return board[0][y];
  }

  // diags
  if((board[0][0] == board[1][1]) && (board[0][0] == board[2][2])) return board[0][0];
  if((board[0][2] == board[1][1]) && (board[0][2] == board[2][0])) return board[0][2];

  return -1;
}

vector<Move> get_available_moves(vector<vector<int> > &board) {

  vector<Move> moves;

  for(size_t x=0;x<board.size();x++) {
    for(size_t y=0;y<board[x].size();y++) {
      if(board[x][y] == 0) moves.push_back(Move(x,y));
    }
  }

  return moves;
}

int play(int player,vector<vector<int> > board) {
  vector<Move> moves = get_available_moves(board);

  for(size_t n=0;n<moves.size();n++) {
    vector<vector<int> > n_board = board;
    n_board[moves[n].x][moves[n].y] = player;
    int win = check_win(n_board);
    if(win == 2) dump_board(n_board);

    if(win == -1) {

      if(player == 1) player = 2; else player = 1;
      play(player,n_board);
    }
  }
}


int main(int argc,char **argv) {

  vector<vector<int> > board(3,vector<int>(3,0));

  board[0][0] = 1;
  board[1][0] = 1;
  board[0][2] = 2;
  board[1][2] = 2;

  dump_board(board);

  play(2,board);
}

And the solutions found were:


OOX
XOO
XXX

OOX
XO_
XXX

OO_
XO_
XXX

OOX
XOX
XXX

OOX
X_X
XXX

OOX
XX_
XXO

OOX
XXO
XXO

OO_
X__
XXX

OO_
XO_
XXX

OO_
_O_
XXX

OOX
OX_
XX_

OOX
OOX
XXX

OOX
O_X
XXX

OOX
OX_
XXO

OOX
_X_
XX_

OOX
OXX
XX_

OOX
O_X
XXX

OOX
_XX
XX_

OOX
__X
XXX

OOX
XXO
XXO

OOX
XOO
XXX

OOX
X_O
XXX

OOX
OXO
XX_

OOX
O_O
XXX

OOX
_XO
XX_

OOX
__O
XXX

OO_
___
XXX
Category: Uncategorized  |  Comment

GCC detect 32 or 64 bit system

January 16, 2012, 6:27 pm

For example:

#include <iostream>

#if __x86_64__
#define ENV64BIT
#else
#define ENV32BIT
#endif

using namespace std;

int main() {

  #ifdef ENV64BIT
  cout << "64 bit" << endl;
  #endif

  #ifdef ENV32BIT
  cout << "32 bit" << endl;
  #endif
}
Category: Uncategorized  |  Comment
« Previous Entries
Next Entries »