Flood-It Solver

deluge.cc

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <string.h>

#include <X11/Xlib.h>
#include <X11/Xutil.h>
#include <X11/extensions/XTest.h>

#include <functional>
#include <map>
#include <queue>
#include <set>
#include <utility>
#include <vector>

using std::binary_function;
using std::make_pair;
using std::map;
using std::multimap;
using std::pair;
using std::priority_queue;
using std::set;
using std::vector;

static const int kWidth = 14;
static const int kHeight = 14;

const unsigned int kColors[] = {
  0x000000, 0xed70a1, 0x605ca8, 0xf3f61d, 0xdc4a20, 0x46b1e2, 0x7e9d1e,
};
static const int kColorCount = (sizeof(kColors) / sizeof(kColors[1])) - 1;
static const int kFloodColor = 0;

typedef vector<int> State;

static int PixelToColor(const unsigned long pixel) {
  for (unsigned int i = 0; i < (sizeof(kColors) / sizeof(kColors[0])); ++i) {
    if (pixel == kColors[i]) {
      return i;
    }
  }
  return -1;
}

static State ReadState() {
  Display *const display = XOpenDisplay(NULL);
  const int screen = DefaultScreen(display);
  const Window root = DefaultRootWindow(display);

  XWindowAttributes root_attributes;
  XGetWindowAttributes(display, root, &root_attributes);
  XImage *const image = XGetImage(display, RootWindow(display, screen), 0, 0,
      root_attributes.width, root_attributes.height, AllPlanes, ZPixmap);

  const int x_origin = 762;
  const int y_origin = 258;
  const int x_offset = 24;
  const int y_offset = 24;

  State result;
  for (int y = 0; y < 14; ++y) {
    for (int x = 0; x < 14; ++x) {
      const int computed_x = x_origin + x_offset * x;
      const int computed_y = y_origin + y_offset * y;
      const unsigned long pixel = XGetPixel(image, computed_x, computed_y);
      result.push_back(PixelToColor(pixel));
    }
  }

  XDestroyImage(image);
  return result;
}

static State GenerateGoalState() {
  return State(kWidth * kHeight);
}

static State ApplyFlood(const State &state, const int color, int *gain) {
  if (gain) {
    *gain = 0;
  }

  State result(state);
  State current_state(state);
  while (true) {
    int gain_delta = 0;
    current_state = result;
    for (int i = 0; i < kHeight; ++i) {
      for (int j = 0; j < kWidth; ++j) {
        if (current_state[i * kHeight + j] == kFloodColor) {
          const int left_index = i * kHeight + (j - 1);
          if (j > 0 && current_state[left_index] == color) {
            result[left_index] = kFloodColor;
            gain_delta++;
          }

          const int right_index = i * kHeight + (j + 1);
          if (j < (kWidth - 1) && current_state[right_index] == color) {
            result[right_index] = kFloodColor;
            gain_delta++;
          }

          const int up_index = (i - 1) * kHeight + j;
          if (i > 0 && current_state[up_index] == color) {
            result[up_index] = kFloodColor;
            gain_delta++;
          }

          const int down_index = (i + 1) * kHeight + j;
          if (i < (kHeight - 1) && current_state[down_index] == color) {
            result[down_index] = kFloodColor;
            gain_delta++;
          }
        }
      }
    }
    if (gain_delta == 0) {
      break;
    }
    if (gain) {
      (*gain) += gain_delta;
    }
  }
  return result;
}

static void GenerateNeighborStates(const State &state, set<pair<State, int> > *neighbors) {
  for (int i = 1; i <= kColorCount; ++i) {
    int flood_gain;
    const State flood_state(ApplyFlood(state, i, &flood_gain));
    if (flood_gain > 0) {
      neighbors->insert(make_pair(flood_state, flood_gain));
    }
  }
}

void PrintState(const State &state) {
  for (int i = 0; i < kHeight; ++i) {
    for (int j = 0; j < kWidth; ++j) {
      printf("\x1b[%dm  ", 40 + state[i * kWidth + j]);
    }
    printf("\x1b[m\n");
  }
  printf("\x1b[m");
}

static const int kControlXOrigin = 618;
static const int kControlYOrigin = 264;
static const int kControlOffset = 45;
static const int kNextBoardXOrigin = 840;
static const int kNextBoardYOrigin = 475;

void SendSolution(const vector<int> &solution) {
  Display *const display = XOpenDisplay(NULL);

  for (int i = 0; i < solution.size(); ++i) {
    const int color = solution[i] - 1;
    const int x_index = color % 3;
    const int y_index = color / 3;
    const int x = kControlXOrigin + x_index * kControlOffset;
    const int y = kControlYOrigin + y_index * kControlOffset;
    XTestFakeMotionEvent(display, 0, x, y, CurrentTime);
    XTestFakeButtonEvent(display, 1, true, CurrentTime);
    XTestFakeButtonEvent(display, 1, false, CurrentTime);
    XSync(display, 0);
    usleep(100000);
  }

  usleep(500000);
  XTestFakeMotionEvent(display, 0, kNextBoardXOrigin, kNextBoardYOrigin,
      CurrentTime);
  XTestFakeButtonEvent(display, 1, true, CurrentTime);
  XTestFakeButtonEvent(display, 1, false, CurrentTime);
  XTestFakeMotionEvent(display, 0, kControlXOrigin, kControlYOrigin,
      CurrentTime);
  XSync(display, 0);
  usleep(500000);
}

struct CompareStateGain : public binary_function<pair<State, int>,
    pair<State, int>, bool> {
  bool operator()(const pair<State, int> &a, const pair<State, int> &b) const {
    return a.second < b.second;
  }
};

static int ColorsRemaining(const State &state) {
  set<int> colors;
  for (int i = 0; i < state.size(); ++i) {
    colors.insert(state[i]);
  }
  colors.erase(0);
  return colors.size();
}

static int Remaining(const State &state) {
  int result = 0;
  for (int i = 0; i < state.size(); ++i) {
    if (state[i] != kFloodColor) {
      ++result;
    }
  }
  return result;
}

static bool Solve(const State state, const State &goal, vector<int> *solution) {
  if (state == goal) {
    return true;
  }

  if (solution->size() >= 25) {
    return false;
  }

  if ((25 - solution->size()) < ColorsRemaining(state)) {
    return false;
  }

  multimap<int, pair<int, State> > next_states;
  for (int i = 1; i <= kColorCount; ++i) {
    int gain;
    const State next_state(ApplyFlood(state, i, &gain));
    if (gain > 0) {
      next_states.insert(make_pair(gain, make_pair(i, next_state)));
    }
  }

  for (multimap<int, pair<int, State> >::const_reverse_iterator i =
      next_states.rbegin(); i != next_states.rend(); ++i) {
    solution->push_back(i->second.first);
    if (Solve(i->second.second, goal, solution)) {
      return true;
    }
    solution->pop_back();
  }

  return false;
}

void PrepareState(State *state) {
  const int initial_color = (*state)[0];
  (*state)[0] = kFloodColor;
  *state = ApplyFlood(*state, initial_color, NULL);
}

int main(int argc, char **argv) {
  int solved = 0;
  while (true) {
    State initial_state(ReadState());
    PrepareState(&initial_state);

    printf("\x1b[H\x1b[2J");
    printf("Solved: %d\n", solved++);
    PrintState(initial_state);

    vector<int> solution;
    if (Solve(initial_state, GenerateGoalState(), &solution)) {
      printf("Solution found.\n");
      if (argc == 2 && !strcmp(argv[1], "--solve")) {
        SendSolution(solution);
      }
    } else {
      printf("No solution found.\n");
    }
  }

  return 0;
}