How many squares - http://hascanvas.com/Counting-Squares

counting_squares.pde

// Answering the "how many squares" problem (my answer = 40):
//
//     http://media-geeks.com/special-features/how-many-squares-indeed/
//
// HasCanvas:
//    
//     http://hascanvas.com/Counting-Squares
//
//  GIF outptu:
//
//     http://www.cs.unm.edu/~jmob/counting-squares.gif

void draw()
{    
    iterateLengths();
    background(125);
    drawSquares();          
    updateStatus();
}

void setup()
{
  size(420, 430);
  background(125);
  connectPoints();
  frameRate(5);
}


class Point
{
  public int X; public int Y;
  
  public Point E; public Point S;
  
  public Point(int x, int y)
  {
    this.E = null; this.S = null;
    this.X = x; this.Y = y;
  } 
}

Point x0y0 = new Point(0, 0); Point x0y2 = new Point(0, 2); Point x0y4 = new Point(0, 4);
Point x0y6 = new Point(0, 6); Point x0y8 = new Point(0, 8);

Point x1y3 = new Point(1, 3); Point x1y4 = new Point(1, 4); Point x1y5 = new Point(1, 5);

Point x2y0 = new Point(2, 0); Point x2y2 = new Point(2, 2); Point x2y3 = new Point(2, 3);
Point x2y4 = new Point(2, 4); Point x2y5 = new Point(2, 5); Point x2y6 = new Point(2, 6);
Point x2y8 = new Point(2, 8);

Point x3y3 = new Point(3, 3); Point x3y4 = new Point(3, 4); Point x3y5 = new Point(3, 5);

Point x4y0 = new Point(4, 0); Point x4y2 = new Point(4, 2); Point x4y4 = new Point(4, 4);
Point x4y6 = new Point(4, 6); Point x4y8 = new Point(4, 8);

Point x5y3 = new Point(5, 3); Point x5y4 = new Point(5, 4); Point x5y5 = new Point(5, 5);

Point x6y0 = new Point(6, 0); Point x6y2 = new Point(6, 2); Point x6y3 = new Point(6, 3);
Point x6y4 = new Point(6, 4); Point x6y5 = new Point(6, 5); Point x6y6 = new Point(6, 6);
Point x6y8 = new Point(6, 8);

Point x7y3 = new Point(7, 3); Point x7y4 = new Point(7, 4); Point x7y5 = new Point(7, 5);

Point x8y0 = new Point(8, 0); Point x8y2 = new Point(8, 2); Point x8y4 = new Point(8, 4);
Point x8y6 = new Point(8, 6); Point x8y8 = new Point(8, 8);

void connectPoints()
{
  x0y0.E = x0y2; x0y0.S = x2y0; x0y2.E = x0y4; x0y2.S = x2y2; x0y4.E = x0y6; x0y4.S = x1y4;
  x0y6.E = x0y8; x0y6.S = x2y6; x0y8.E = null; x0y8.S = x2y8;

  x1y3.E = x1y4; x1y3.S = x2y3; x1y4.E = x1y5; x1y4.S = x2y4; x1y5.E = null; x1y5.S = x2y5;

  x2y0.E = x2y2; x2y0.S = x4y0; x2y2.E = x2y3; x2y2.S = x4y2; x2y3.E = x2y4; x2y3.S = x3y3;
  x2y4.E = x2y5; x2y4.S = x3y4; x2y5.E = x2y6; x2y5.S = x3y5; x2y6.E = x2y8; x2y6.S = x4y6;
  x2y8.E = null; x2y8.S = x4y8;

  x3y3.E = x3y4; x3y3.S = null; x3y4.E = x3y5; x3y4.S = x4y4; x3y5.E = null; x3y5.S = null;

  x4y0.E = x4y2; x4y0.S = x6y0; x4y2.E = x4y4; x4y2.S = x6y2; x4y4.E = x4y6; x4y4.S = x5y4;
  x4y6.E = x4y8; x4y6.S = x6y6; x4y8.E = null; x4y8.S = x6y8;

  x5y3.E = x5y4; x5y3.S = x6y3; x5y4.E = x5y5; x5y4.S = x6y4; x5y5.E = null; x5y5.S = x6y5;

  x6y0.E = x6y2; x6y0.S = x8y0; x6y2.E = x6y3; x6y2.S = x8y2; x6y3.E = x6y4; x6y3.S = x7y3;
  x6y4.E = x6y5; x6y4.S = x7y4; x6y5.E = x6y6; x6y5.S = x7y5; x6y6.E = x6y8; x6y6.S = x8y6;
  x6y8.E = null; x6y8.S = x8y8;

  x7y3.E = x7y4; x7y3.S = null; x7y4.E = x7y5; x7y4.S = x8y4; x7y5.E = null; x7y5.S = null;

  x8y0.E = x8y2; x8y0.S = null; x8y2.E = x8y4; x8y2.S = null; x8y4.E = x8y6; x8y4.S = null;
  x8y6.E = x8y8; x8y6.S = null; x8y8.E = null; x8y8.S = null;
}

Point[] points = {
  x0y0, x0y2, x0y4, x0y6, x0y8,
  x1y3, x1y4, x1y5,
  x2y0, x2y2, x2y3, x2y4, x2y5, x2y6, x2y8,
  x3y3, x3y4, x3y5,
  x4y0, x4y2, x4y4, x4y6, x4y8,
  x5y3, x5y4, x5y5,
  x6y0, x6y2, x6y3, x6y4, x6y5, x6y6, x6y8,
  x7y3, x7y4, x7y5,
  x8y0, x8y2, x8y4, x8y6, x8y8,
};

int dx = 400; int dy = 400;

int maxX = 8; int maxY = 8;

float scaleX = dx / maxX; float scaleY = dy / maxY;

int padding = 16; int strokeWeightValue = 3; int pad = (padding/2);

static final int CHECKING = 1; static final int HIGHLIGHT = 2; static final int NONE = 0;

void scaledLine3(Point p1, Point p2, int highlight)
{
  if ( p1 == null || p2 == null )
    return;

  if ( highlight == HIGHLIGHT )
  {
    stroke(204, 102, 0);
  }
  else if ( highlight == CHECKING )
  {
    stroke(255, 255, 255);
  }
  else
  {
    stroke(50, 50, 50);
  }

  strokeWeight(strokeWeightValue);
  int bump = 0;
  if ( p1 == p2 ) bump = 1;
  line(pad +  p1.Y * scaleY, (3 * pad) + (p1.X * scaleX), (pad + (p2.Y * scaleY)) + bump, ((3 * pad) + (p2.X * scaleX)));
}

void scaledLine(Point p1, Point p2) { scaledLine3(p1, p2, NONE); }

Point hlCheckingPoint = null; Point hlTopLeft = null; Point hlBottomLeft = null;
Point hlTopRight = null; Point hlBottomRight = null;

void drawSquares()
{


  for (int i = 0; i < points.length; i++)
  {
    Point p = points[i];
    if ( p.E != null )
      scaledLine(p, p.E);
    if ( p.S != null )
      scaledLine(p, p.S);
  }

  if ( hlTopLeft != null )
  {
    scaledLine3(hlTopLeft, hlTopRight, HIGHLIGHT);
    scaledLine3(hlTopLeft, hlBottomLeft, HIGHLIGHT);
    scaledLine3(hlBottomLeft, hlBottomRight, HIGHLIGHT);
    scaledLine3(hlTopRight, hlBottomRight, HIGHLIGHT);
  }

  if ( hlCheckingPoint != null )
  {
    scaledLine3(hlCheckingPoint, hlCheckingPoint, CHECKING);
    scaledLine3(hlCheckingPoint, hlCheckingPoint, CHECKING);
  }
}

int squareCount = 0;
int initialLength = 1;
int sideLength = initialLength;

void updateStatus()
{
  fill(255);
  text("Square tally: " + squareCount + ", side length: " + sideLength, padding/2, padding);
}

Point findPoint(int ofLength, Point forPoint, int currentLength, boolean goEast)
{
  //println("forPoint: X=" + forPoint.X + 
  //        ", Y=" + forPoint.Y + ", ofLength: " + 
  //        ofLength + ", currentLength: " + currentLength);

  while ( true )
  {
    if ( ofLength == currentLength )
      return forPoint;    

    if ( (goEast && forPoint.E == null) || (!goEast && forPoint.S == null) )
      return null;

    if ( goEast )
    {
      currentLength += (forPoint.E.Y - forPoint.Y);
      forPoint = forPoint.E;
    }
    else
    {
      currentLength += (forPoint.S.X - forPoint.X);
      forPoint = forPoint.S;
    }
  }
  //return findPoint(ofLength, forPoint.S, currentLength + (forPoint.S.X - forPoint.X), goEast);
}

Point findEastPoint(int ofLength, Point forPoint, int currentLength)
{
  return findPoint(ofLength, forPoint, currentLength, true);
}

Point findSouthPoint(int ofLength, Point forPoint, int currentLength)
{
  return findPoint(ofLength, forPoint, currentLength, false);
}

Point hasSquare(int ofLength, Point forPoint)
{
  Point southPoint = findSouthPoint(ofLength, forPoint, 0);
  if ( southPoint == null )
  {
    //println("south point null");
    return null;
  }
  Point eastPoint = findEastPoint(ofLength, forPoint, 0);
  if ( eastPoint == null )
  {
    //println("east point null");
    return null;
  }
  Point southOfEastPoint = findSouthPoint(ofLength, eastPoint, 0);
  if ( southOfEastPoint == null )
  {
    //println("south of east point null");
    return null;
  }
  Point eastOfSouthPoint = findEastPoint(ofLength, southPoint, 0);
  if ( eastOfSouthPoint == null )
  {
    //println("east of south point null");
    return null;
  }
  if ( southOfEastPoint != eastOfSouthPoint )
  {
    //println("end points not equal");
    return null;
  }
  int dX = eastOfSouthPoint.X - forPoint.X;
  int dY = eastOfSouthPoint.Y - forPoint.Y;
  if ( dX != dY )
  {
    //println("dX and dY differed");
    return null;
  }
  if ( dX != ofLength )
  {
    //println("dX not equal of target length");
    return null;
  }
  hlTopLeft = forPoint;
  hlTopRight = eastPoint;
  hlBottomLeft = southPoint;
  hlBottomRight = eastOfSouthPoint;
  return eastOfSouthPoint;
}

void findSquare(int ofLength, Point thePoint)
{
  Point corner = hasSquare(ofLength, thePoint);
  if ( corner != null )
  {
    hlTopLeft = thePoint;
    hlBottomRight = corner;
    squareCount++;
  }
  hlCheckingPoint = thePoint;
}

int pointIndex = 0;

void iterateLengths()
{
  findSquare(sideLength, points[pointIndex]);  
  pointIndex++;
  if ( pointIndex >= points.length )
  {
    pointIndex = 0;
    sideLength++;
  }
  if ( sideLength > maxX )
  {
    squareCount = 0;
    sideLength = initialLength;
    hlCheckingPoint = null;
    hlTopLeft = null;
    hlTopRight = null;
    hlBottomLeft = null;
    hlBottomRight = null;
  }
}