Android OS Pattern Screen Lock Simulator

// 2011 Aret Carlsen

// Android pattern screen lock simulator for a certain subset of users.
// Implements four constraints:
// 1.) No dot can be visited twice.
// 2.) Path must be at least four dots long. (OS enforces.)
// 3.) Only adjacent dots may be next in path.
// 3.) User never crosses their own line. (Implied by constraint (3).)

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#include <list>

struct Dot {
  int8_t x;
  int8_t y;

  Dot(int8_t new_x, int8_t new_y)
  : x(new_x), y(new_y)
  { }

  bool is_adjacent_to(Dot* otherDot){
    return ( (abs(otherDot->x - x) < 2) && (abs(otherDot->y - y) < 2) );
  }
};

typedef std::list<Dot*> DotList_t;

unsigned int search_path(DotList_t unvisited_dots, DotList_t visited_dots = DotList_t(), Dot* newly_arrived_dot = NULL){
  // Consraint (1).
  if(newly_arrived_dot){
    visited_dots.push_back(newly_arrived_dot);
    unvisited_dots.remove(newly_arrived_dot);
  }

  unsigned int path_count = 0;
  for(DotList_t::iterator it = unvisited_dots.begin();
      it != unvisited_dots.end();
      it++){
  // Constraints (3) and (4): Only adjacent dots can be next in the path.
    if(newly_arrived_dot && !newly_arrived_dot->is_adjacent_to(*it))
      continue;
  // Constraint (2): This is only a complete path if at least 3 dots were already visited.
    if(visited_dots.size() >= 3)
      path_count++;
    path_count += search_path(unvisited_dots, visited_dots, *it);
  }

  return path_count;
}

int main(){
  DotList_t dots;

  Dot* testDot = NULL;
  // Generate dot graph.
  for(uint8_t x = 0; x < 3; x++){
    for(uint8_t y = 0; y < 3; y++){
      // MEMORY LEAK
      dots.push_back(new Dot(x, y));
      //if((x == 1) && (y == 1))
      //  testDot = dots.back();
    }
  }

  unsigned int path_count = 0;
  if(testDot){
    // Test for a specific initial dot:
    fprintf(stderr, "Given initial dot: x=%d, y=%d\n", testDot->x, testDot->y);
    path_count = search_path(dots, DotList_t(), testDot);
  }else{
  // Simulate users who do not cross their own lines or move to non-adjacent
  // dots. The former constraint is implied by the latter, as it is impossible
  // to cross one's own lines without moving to a non-adjacent dot.
    path_count = search_path(dots);
  }
  fprintf(stdout, "Total path count: %u\n", path_count);

  return 0;
}