irori @ ICFP Programming Contest 2012

lifter.cc

#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
#include <signal.h>
#include <stdio.h>
#include <string.h>
using namespace std;

#define ALLOW_WAIT 0  // 1 for beard4, 0 for flood5
#define PUSH_CHECK 1  // 0 for contest6

#define UP(pos) ((pos) + g_width)
#define DOWN(pos) ((pos) - g_width)
#define LEFT(pos) ((pos) - 1)
#define RIGHT(pos) ((pos) + 1)
#define X_OF(pos) ((pos) % g_width)
#define Y_OF(pos) ((pos) / g_width)

int g_width;
int g_height;
int g_size;
int g_max_turn;
int g_num_lambda;
int g_initial_water = 0;
int g_flooding = 0;
int g_waterproof = 10;
char g_trampoline[9];  // k targets g_trampoline[k - 'A']
int g_growth = 25;
int g_initial_razors = 0;

bool g_signal = false;
vector<int> g_distance;

enum Condition {
  OK,
  WIN,
  LOSE,
  INVALID,
  ABORT
};

inline bool is_rock(char c) {
  return c == '*' || c == '@';
}

inline bool is_trampoline(char c) {
  return 'A' <= c && c <= 'I';
}

inline bool is_target(char c) {
  return '1' <= c && c <= '9';
}

bool analyze_board(string board) {
  // Mark reachable cells
  char* mark = new char[g_size];
  memset(mark, 0, g_size);

  queue<size_t> q;
  q.push(board.find('R'));
  mark[q.front()] = 1;

  while (!q.empty()) {
    size_t pos = q.front();
    q.pop();
    const int offset[] = {-g_width, -1, 1, g_width};
    for (int i = 0; i < 4; i++) {
      size_t p = pos + offset[i];
      if (mark[p] || board[p] == '#' || is_target(board[p]))
        continue;
      if (is_rock(board[p])) {
        if (mark[DOWN(p)] || board[DOWN(p)] == ' ' ||
#if PUSH_CHECK
            (mark[LEFT(p)] && board[RIGHT(p)] == ' ') ||
            (mark[RIGHT(p)] && board[LEFT(p)] == ' ') ||
#endif
            (is_rock(board[DOWN(p)]) &&
             (mark[LEFT(p)] && mark[DOWN(LEFT(p))] ||
              board[LEFT(p)] == ' ' && board[DOWN(LEFT(p))] == ' ')) ||
            ((is_rock(board[DOWN(p)]) || board[DOWN(p)] == '\\') &&
             (mark[RIGHT(p)] && mark[DOWN(RIGHT(p))] ||
              board[RIGHT(p)] == ' ' && board[DOWN(RIGHT(p))] == ' '))) {
          mark[p] = 1;
          q.push(p);
        }
      } else if (is_trampoline(board[p])) {
        mark[p] = 1;
        size_t dest = board.find(g_trampoline[board[p] - 'A']);
        mark[dest] = 1;
        q.push(dest);
      } else {
        mark[p] = 1;
        q.push(p);
      }
    }
    if (is_rock(board[LEFT(UP(pos))]) && !mark[LEFT(UP(pos))] && mark[UP(pos)] &&
        (is_rock(board[LEFT(pos)]) || board[LEFT(pos)] == '\\')) {
      mark[LEFT(UP(pos))] = 1;
      q.push(LEFT(UP(pos)));
    }
    if (is_rock(board[RIGHT(UP(pos))]) && !mark[RIGHT(UP(pos))] &&
        mark[UP(pos)] && is_rock(board[RIGHT(pos)])) {
      mark[RIGHT(UP(pos))] = 1;
      q.push(RIGHT(UP(pos)));
    }
  }

  for (int i = 0; i < board.length(); i++) {
    if (!mark[i] && (board[i] == '\\' || board[i] == 'L' || board[i] == 'O')) {
#if 0
      for (int y = g_height - 2; y >= 1; y--) {
        for (int x = 1; x < g_width; x++)
          putchar(mark[y * g_width + x] ? ' ' : board[y * g_width + x]);
        putchar('\n');
      }
#endif
      delete[] mark;
      return false;
    }
  }

  delete[] mark;
  return true;
}


class State {
public:
  explicit State(string board)
    : board_(board), pos_(board.find('R')), moves_(),
      lambda_collected_(0), underwater_(0), razors_(g_initial_razors) {
    update_farthest_lambda();
  }

  Condition move(char command) {
    moves_ += command;

    // Robot Movement
    if (command == 'L' && is_rock(board_[pos_ - 1]) && board_[pos_ - 2] == ' ') {
      board_[pos_ - 2] = board_[pos_ - 1];
      board_[pos_ - 1] = ' ';
    }
    if (command == 'R' && is_rock(board_[pos_ + 1]) && board_[pos_ + 2] == ' ') {
      board_[pos_ + 2] = board_[pos_ + 1];
      board_[pos_ + 1] = ' ';
    }
    int offset = (command == 'U') ? g_width
      : (command == 'D') ? -g_width
      : (command == 'L') ? -1
      : (command == 'R') ? 1
      : 0;
    if (offset != 0) {
      switch (board_[pos_ + offset]) {
      case 'O':
        return WIN;

      case '\\':
        lambda_collected_++;
        if (lambda_collected_ == g_num_lambda) {
          size_t lift = board_.find('L');
          board_[lift] = 'O';
        }
        board_[pos_ + offset] = 'R';
        board_[pos_] = ' ';
        pos_ += offset;
        if (g_distance[pos_] == farthest_lambda_)
          update_farthest_lambda();
        break;

      case '!':
        razors_++;
        // fall through
      case ' ': case '.':
        board_[pos_ + offset] = 'R';
        board_[pos_] = ' ';
        pos_ += offset;
        break;

      case 'A': case 'B': case 'C': case 'D': case 'E':
      case 'F': case 'G': case 'H': case 'I':
        {
          board_[pos_] = ' ';
          char target = g_trampoline[board_[pos_ + offset] - 'A'];
          pos_ = board_.find(target);
          board_[pos_] = 'R';
          for (int i = 0; i < board_.length(); i++) {
            if (is_trampoline(board_[i]) &&
                g_trampoline[board_[i] - 'A'] == target)
              board_[i] = ' ';
          }
        }
        break;

      default:
        return INVALID;
      }
    } else if (command == 'S') {
      if (!razors_--)
        return INVALID;
      char changed = 0;
      if (board_[UP(LEFT(pos_))] == 'W')
        changed = board_[UP(LEFT(pos_))] = ' ';
      if (board_[UP(pos_)] == 'W')
        changed = board_[UP(pos_)] = ' ';
      if (board_[UP(RIGHT(pos_))] == 'W')
        changed = board_[UP(RIGHT(pos_))] = ' ';
      if (board_[LEFT(pos_)] == 'W')
        changed = board_[LEFT(pos_)] = ' ';
      if (board_[RIGHT(pos_)] == 'W')
        changed = board_[RIGHT(pos_)] = ' ';
      if (board_[DOWN(LEFT(pos_))] == 'W')
        changed = board_[DOWN(LEFT(pos_))] = ' ';
      if (board_[DOWN(pos_)] == 'W')
        changed = board_[DOWN(pos_)] = ' ';
      if (board_[DOWN(RIGHT(pos_))] == 'W')
        changed = board_[DOWN(RIGHT(pos_))] = ' ';
      if (!changed)
        return INVALID;
    }

    // Map Update
    string new_board = board_;
    for (int p = g_width; p < board_.length(); p++) {
      switch (board_[p]) {
      case '*': case '@':
        if (board_[DOWN(p)] == ' ') {
          new_board[p] = ' ';
          if (board_[p] == '@' && board_[DOWN(DOWN(p))] != ' ') {
            new_board[DOWN(p)] = '\\';
            update_farthest_lambda();
          } else
            new_board[DOWN(p)] = board_[p];
        } else if (board_[p+1] == ' ' && board_[DOWN(p+1)] == ' ' &&
                   (is_rock(board_[DOWN(p)]) || board_[DOWN(p)] == '\\')) {
          new_board[p] = ' ';
          if (board_[p] == '@' && board_[DOWN(DOWN(p+1))] != ' ') {
            new_board[DOWN(p+1)] = '\\';
            update_farthest_lambda();
          } else
            new_board[DOWN(p+1)] = board_[p];
        } else if (board_[p-1] == ' ' && board_[DOWN(p-1)] == ' ' &&
                   is_rock(board_[DOWN(p)])) {
          new_board[p] = ' ';
          if (board_[p] == '@' && board_[DOWN(DOWN(p-1))] != ' ') {
            new_board[DOWN(p-1)] = '\\';
            update_farthest_lambda();
          } else
            new_board[DOWN(p-1)] = board_[p];
        }
        break;
      case 'W':
        if (turn() % g_growth == 0) {
          if (board_[UP(LEFT(p))] == ' ')
            new_board[UP(LEFT(p))] = 'W';
          if (board_[UP(p)] == ' ')
            new_board[UP(p)] = 'W';
          if (board_[UP(RIGHT(p))] == ' ')
            new_board[UP(RIGHT(p))] = 'W';
          if (board_[LEFT(p)] == ' ')
            new_board[LEFT(p)] = 'W';
          if (board_[RIGHT(p)] == ' ')
            new_board[RIGHT(p)] = 'W';
          if (board_[DOWN(LEFT(p))] == ' ')
            new_board[DOWN(LEFT(p))] = 'W';
          if (board_[DOWN(p)] == ' ')
            new_board[DOWN(p)] = 'W';
          if (board_[DOWN(RIGHT(p))] == ' ')
            new_board[DOWN(RIGHT(p))] = 'W';
        }
        break;
      }
    }
    if (new_board[UP(pos_)] == '*' && board_[UP(pos_)] != '*' ||
        new_board[UP(pos_)] == '\\' && board_[UP(pos_)] != '\\')
      return LOSE;
    if (command == 'W' && board_ == new_board)
      return INVALID;
    board_ = new_board;

    // Water check
    if (Y_OF(pos_) > prev_water_level())
      underwater_ = 0;
    if (Y_OF(pos_) <= water_level()) {
      if (++underwater_ > g_waterproof)
        return LOSE;
    }

    return OK;
  }

  string seen_key() const { return board_; }
  const string& moves() const { return moves_; }
  int turn() const { return moves_.length(); }
  bool analyze() const { return analyze_board(board_); }

  int water_level() const {
    if (g_flooding > 0)
      return g_initial_water + turn() / g_flooding;
    else
      return g_initial_water;
  }
  int prev_water_level() const {
    if (g_flooding > 0)
      return g_initial_water + (turn() - 1) / g_flooding;
    else
      return g_initial_water;
  }

  int score(Condition cond) const {
    int sc = lambda_collected_ * 25 - moves_.length();
    if (cond == ABORT)
      sc += lambda_collected_ * 25;
    if (cond == WIN)
      sc += lambda_collected_ * 50;
    return sc;
  }

  void display(FILE* fp) const {
    for (int y = g_height - 2; y >= 1; y--) {
      for (int x = 1; x < g_width; x++)
        fputc(at(x, y), fp);
      if (y == water_level())
        fputc('~', fp);
      fputc('\n', fp);
    }
    if (razors_ > 0)
      fprintf(fp, "razors = %d\n", razors_);
    if (underwater_ > 0)
      fprintf(fp, "underwater = %d\n", underwater_);
  }

  char at(int x, int y) const { return board_[y * g_width + x]; }

  int eval() const {
    int score = lambda_collected_ * 50 + razors_ * 5
      - count(board_.begin(), board_.end(), 'W') * 5
      - turn() - estimate_steps();
    if (g_flooding > 0) {
      for (int i = 0; i < g_size; i++) {
        if (board_[i] == '\\')
          score -= max(0, water_level() - Y_OF(i)) * 20;
      }
    }
    return score;
  }

  int estimate_steps() const {
    if (g_num_lambda == lambda_collected_)
      return g_distance[pos_];
    if (g_distance[pos_] > farthest_lambda_)
      return g_distance[pos_];
    return farthest_lambda_ + farthest_lambda_ - g_distance[pos_];
  }

private:
  void update_farthest_lambda() {
    farthest_lambda_ = 0;
    for (int i = 0; i < g_size; i++) {
      if (board_[i] == '\\' || board_[i] == '@')
        farthest_lambda_ = max(farthest_lambda_, g_distance[i]);
    }
  }

  string board_;
  string moves_;
  int pos_;  // position of the robot
  int underwater_; // time spent underwater
  int razors_;
  int lambda_collected_;
  int farthest_lambda_;
};


struct StateCompare {
  bool operator()(const State* lhs, const State* rhs) {
    return lhs->eval() < rhs->eval();
  }
};


class Lifter {
public:
  Lifter(string board) : abort_score_(0) {
    queue_.push(new State(board));
    disable_analysis_ = !queue_.top()->analyze();
  }

  string solve() {
    const int gc_threshold = min(100000, 100000000 / g_size);
    int count;
    for (count = 0; !queue_.empty() && !g_signal; count++) {
#ifdef DEBUG
      if (count % 100000 == 0) {
        cerr << count << ' '
             << queue_.size() << ' '
             << queue_.top()->turn() << endl;
        // queue_.top()->display(stderr);
      }
#endif

      State* st = queue_.top();
      queue_.pop();
      step(*st);
      delete st;

      if (queue_.size() > gc_threshold)
        cut();
      if (seen_.size() * g_size > 500000000) {
#ifdef DEBUG
        cerr << "seen_.clear()" << endl;
#endif
        seen_.clear();
      }
    }
#ifdef DEBUG
    cout << count << " steps" << endl;
#endif
    if (shortest_.empty())
      return abort_seq_ + 'A';
    else
      return shortest_;
  }

  void step(const State& st) {
    if (st.turn() + st.estimate_steps() >=
        (shortest_.empty() ? g_max_turn : shortest_.length()))
      return;

#if ALLOW_WAIT
    for (int dir = 0; dir < 6; dir++) {
#else
    for (int dir = 0; dir < 5; dir++) {
#endif
      State* newst = new State(st);
      Condition result = newst->move("ULRDSW"[dir]);
      if (result == INVALID || result == LOSE) {
        delete newst;
        continue;
      }
      if (result == WIN) {
#ifdef DEBUG
        cerr << newst->moves() << endl;
#endif
        if (shortest_.empty() || newst->turn() < shortest_.length())
          shortest_ = newst->moves();
        return;
      }
      string key = newst->seen_key();
      auto it = seen_.find(key);
      if (it == seen_.end() || it->second > newst->turn()) {
        seen_[key] = newst->turn();
        if (disable_analysis_ || newst->analyze()) {
          queue_.push(newst);
          if (newst->score(ABORT) > abort_score_) {
            abort_score_ = newst->score(ABORT);
            abort_seq_ = newst->moves();
          }
        }
      } else
        delete newst;
    }
  }

  void cut() {
    const int CUT_SIZE = 1000;

#ifdef DEBUG
    cerr << "GC" << endl;
#endif
    State *buf[CUT_SIZE];
    for (int i = 0; i < CUT_SIZE; i++) {
      buf[i] = queue_.top();
      queue_.pop();
    }
    while (!queue_.empty()) {
      delete queue_.top();
      queue_.pop();
    }
    for (int i = 0; i < CUT_SIZE; i++)
      queue_.push(buf[i]);
  }

private:
  priority_queue<State*, vector<State*>, StateCompare> queue_;
  unordered_map<string, int> seen_;
  string shortest_;
  int abort_score_;
  string abort_seq_;
  bool disable_analysis_;
};


void init_distance(const string& board) {
  g_distance.resize(g_size, 1000000);

  queue<size_t> q;
  q.push(board.find('L'));
  g_distance[q.front()] = 0;
  while (!q.empty()) {
    int d = g_distance[q.front()] + 1;
    const int offset[] = {-g_width, -1, 1, g_width};
    for (int i = 0; i < 4; i++) {
      size_t pos = q.front() + offset[i];
      if (board[pos] != '#' && g_distance[pos] > d) {
        if (is_target(board[pos])) {
          g_distance[pos] = d;
          for (int p = 0; p < board.length(); p++) {
            if (is_trampoline(board[p]) &&
                g_trampoline[board[p] - 'A'] == board[pos]) {
              g_distance[p] = d;
              q.push(p);
            }
          }
          q.push(pos);
        } else {
          g_distance[pos] = d;
          q.push(pos);
        }
      }
    }
    q.pop();
  }
}

string load_board(istream& is) {
  vector<string> lines;
  string line;
  while (getline(is, line) && !line.empty()) {
    lines.push_back(line);
    g_width = max(g_width, (int)line.length());
  }
  g_height = lines.size();
  g_max_turn = g_width * g_height + 1;

  // Add surrounding wall
  g_width++;
  g_height += 2;
  g_size = g_width * g_height;

  string board(g_width, '#');
  while (!lines.empty()) {
    lines.back().resize(g_width - 1, ' ');
    board += '#';
    board += lines.back();
    lines.pop_back();
  }
  board += string(g_width, '#');

  g_num_lambda = count(board.begin(), board.end(), '\\') +
    count(board.begin(), board.end(), '@');

  // Read metadata
  while (getline(is, line)) {
    sscanf(line.c_str(), "Water %d", &g_initial_water);
    sscanf(line.c_str(), "Flooding %d", &g_flooding);
    sscanf(line.c_str(), "Waterproof %d", &g_waterproof);

    char c, d;
    if (sscanf(line.c_str(), "Trampoline %c targets %c", &c, &d) == 2)
      g_trampoline[c - 'A'] = d;

    sscanf(line.c_str(), "Growth %d", &g_growth);
    sscanf(line.c_str(), "Razors %d", &g_initial_razors);
  }
  if (g_growth == 0)
    g_growth = 25;

  init_distance(board);
  return board;
}

void handle_sigint(int signo) {
  g_signal = true;
}

void simulate(string board, string moves, bool quiet) {
  State st(board);

  if (!quiet) {
    printf("%d x %d (%d, %d, %d)\n",
           g_width, g_height,
           g_initial_water, g_flooding, g_waterproof);
    printf("turn 0:\n");
    st.display(stdout);
  }

  Condition result = OK;
  for (int i = 0; i < moves.length(); i++) {
    if (moves[i] == 'A')
      result = ABORT;
    else
      result = st.move(moves[i]);
    if (!quiet) {
      printf("\nturn %d: score = %d\n", st.turn(), st.score(result));
      st.display(stdout);
    }
    if (result != OK)
      break;
  }
  if (!quiet) {
    switch (result) {
    case OK:
      puts("END");
      break;
    case WIN:
      puts("WIN!");
      break;
    case LOSE:
      puts("LOSE...");
      break;
    case INVALID:
      puts("INVALID MOVE");
      break;
    }
  }
  printf("score = %d\n", st.score(result));
}

int main(int argc, char *argv[]) {
  bool simulator = false;
  string moves;
  if (argc > 1 && strcmp(argv[1], "-s") == 0) {
    // Simulator mode
    simulator = true;
    getline(cin, moves);
    argc--;
    argv++;
  } else {
    signal(SIGINT, handle_sigint);
  }

  string board;
  if (argc > 1) {
    ifstream ifs(argv[1]);
    board = load_board(ifs);
    ifs.close();
  } else
    board = load_board(cin);

  if (simulator) {
    simulate(board, moves, false);
  } else {
    Lifter lifter(board);
    string moves = lifter.solve();
    cout << moves << endl;
#ifdef DEBUG
    simulate(board, moves, true);
#endif
  }
}