Skip to content

Instantly share code, notes, and snippets.

@hamadu

hamadu/FixTheFence.java

Created March 13, 2013 17:07
Show Gist options
  • Save hamadu/5154147 to your computer and use it in GitHub Desktop.
Save hamadu/5154147 to your computer and use it in GitHub Desktop.
Download ZIP
Marathon Match 78
Raw
FixTheFence.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class FixTheFence {
boolean _debug = false;
long _xtime = 10000;
long _start_time = -1;
static final XorShift _rnd = new XorShift();
static final boolean VALID = true;
static final boolean INVALID = false;
static final int[] Dx = { 1, 0, 0, -1, 0 };
static final int[] Dy = { 0, 1, -1, 0, 0 };
static final char[] Dc = { 'R', 'D', 'U', 'L' };
static int N;
static final int ROW = 128;
static final int ROW2 = 7;
static final int NMAX = ROW * ROW;
static final int[] Data = new int[NMAX];
static final int[] DataCnt = new int[NMAX];
static final int[] Dir = { 1, ROW, -ROW, -1 };
static final int[] Dir9 = { -ROW - 1, -ROW, -ROW + 1, -1, 1, ROW - 1, ROW, ROW + 1, 0 };
static final int[] Dir25 = { -ROW * 2 - 2, -ROW * 2 - 1, -ROW * 2, -ROW * 2 + 1, -ROW * 2 + 2, -ROW * 1 - 2, -ROW * 1 - 1, -ROW * 1, -ROW * 1 + 1,
-ROW * 1 + 2, -2, -1, 1, 2, ROW * 1 - 2, ROW * 1 - 1, ROW * 1, ROW * 1 + 1, ROW * 1 + 2, ROW * 2 - 2, ROW * 2 - 1, ROW * 2, ROW * 2 + 1,
ROW * 2 + 2, 0, };
static final boolean[] within = new boolean[20000];
public void init(String[] diagram) {
N = diagram.length;
Arrays.fill(Data, -1);
for (int i = 1 ; i <= N ; i++) {
for (int j = 1 ; j <= N ; j++) {
within[(i << 7) + j] = true;
if (diagram[i - 1].charAt(j - 1) == '-') {
Data[(i << 7) + j] = -1;
} else {
Data[(i << 7) + j] = diagram[i - 1].charAt(j - 1) - '0';
}
}
}
}
public String findLoop(String[] diagram) {
_start_time = System.currentTimeMillis();
long duration = _start_time + _xtime * 19 / 20;
init(diagram);
int bestScore = Integer.MAX_VALUE;
boolean[] isInside = null;
boolean[] bestInside = null;
int[] counter = new int[NMAX];
bestInside = buildFixedRect(3);
isInside = bestInside.clone();
int K = 80000;
boolean[] validField = new boolean[NMAX];
bestScore = evaluate(bestInside, counter);
int currentScore = bestScore;
int[] candidate = new int[Math.max(100000, N * N * 32)];
int threshold = N * N * 2;
int cidx = threshold + 1;
long tr = 0;
double maxTemp = 1.0d;
double temp = maxTemp;
int itemp = 0;
long left_time = duration - System.currentTimeMillis();
boolean[] rem = new boolean[200];
for (int i = 1 ; i <= N ; i++) {
for (int j = 1 ; j <= N ; j++) {
validField[(i << 7) + j] = isvalid((i << 7) + j, isInside, counter);
}
}
int r2 = 50;
int r3 = 50;
int r4 = 50;
long lup = System.currentTimeMillis();
long time = lup;
while (true) {
if ((tr++ & 255) == 0) {
time = System.currentTimeMillis();
if (time >= duration) {
break;
}
temp = Math.pow(1.0d * (duration - time) / left_time, 1.4) * maxTemp;
itemp = (int) (temp * 1024);
}
if (cidx >= threshold) {
cidx = 0;
for (int i = 1 ; i <= N ; i++) {
for (int j = 1 ; j <= N ; j++) {
int p = (i << 7) + j;
if (validField[p]) {
candidate[cidx++] = p;
}
}
}
}
int pos1 = -1, cl = cidx;
int pos2 = -1;
int pos3 = -1;
int pos4 = -1;
didx = 0;
do {
pos1 = candidate[_rnd.nextInt(cl)];
} while (!validField[pos1]);
int diff = evaluateDiffX(isInside, counter, pos1);
isInside[pos1] = !isInside[pos1];
if (_rnd.nextInt(100) <= r2) {
int ad = 0;
for (int d = 0 ; d < 8 ; d++) {
int dpos = pos1 + Dir9[d];
rem[d] = validField[dpos];
validField[dpos] = isvalid(dpos, isInside, counter);
if (validField[dpos]) {
candidate[cidx++] = dpos;
ad++;
}
}
if (ad == 0) {
do {
pos2 = candidate[_rnd.nextInt(cl)];
} while (!validField[pos2]);
diff += evaluateDiffX(isInside, counter, pos2);
isInside[pos2] = !isInside[pos2];
} else {
pos2 = candidate[(cl + _rnd.nextInt(ad))];
diff += evaluateDiffX(isInside, counter, pos2);
isInside[pos2] = !isInside[pos2];
if (_rnd.nextInt(100) <= r3) {
cl += ad;
ad = 0;
for (int d = 0 ; d < 8 ; d++) {
int dpos = pos2 + Dir9[d];
rem[9 + d] = validField[dpos];
validField[dpos] = isvalid(dpos, isInside, counter);
if (validField[dpos]) {
candidate[cidx++] = dpos;
ad++;
}
}
if (ad == 0) {
do {
pos3 = candidate[_rnd.nextInt(cl)];
} while (!validField[pos3]);
diff += evaluateDiffX(isInside, counter, pos3);
isInside[pos3] = !isInside[pos3];
} else {
pos3 = candidate[(cl + _rnd.nextInt(ad))];
diff += evaluateDiffX(isInside, counter, pos3);
isInside[pos3] = !isInside[pos3];
if (_rnd.nextInt(100) <= r4) {
cl += ad;
ad = 0;
for (int d = 0 ; d < 8 ; d++) {
int dpos = pos3 + Dir9[d];
rem[18 + d] = validField[dpos];
validField[dpos] = isvalid(dpos, isInside, counter);
if (validField[dpos]) {
candidate[cidx++] = dpos;
ad++;
}
}
if (ad == 0) {
do {
pos4 = candidate[_rnd.nextInt(cl)];
} while (!validField[pos4]);
diff += evaluateDiffX(isInside, counter, pos4);
isInside[pos4] = !isInside[pos4];
} else {
pos4 = candidate[(cl + _rnd.nextInt(ad))];
diff += evaluateDiffX(isInside, counter, pos4);
isInside[pos4] = !isInside[pos4];
}
}
}
}
}
}
int score = currentScore + diff;
if (bestScore > score) {
bestScore = score;
bestInside = isInside.clone();
}
boolean willKeep = (diff <= 0);
if (!willKeep) {
willKeep = _rnd.nextInt(K) * diff < itemp;
}
if (willKeep) {
if (pos4 >= 0) {
for (int d = 0 ; d < 8 ; d++) {
int dpos = pos4 + Dir9[d];
boolean bf = validField[dpos];
boolean nv = isvalid(dpos, isInside, counter);
validField[dpos] = nv;
if (nv) {
if (!bf) {
candidate[cidx++] = dpos;
}
}
}
validField[pos4] = VALID;
} else if (pos3 >= 0) {
for (int d = 0 ; d < 8 ; d++) {
int dpos = pos3 + Dir9[d];
boolean bf = validField[dpos];
boolean nv = isvalid(dpos, isInside, counter);
validField[dpos] = nv;
if (nv) {
if (!bf) {
candidate[cidx++] = dpos;
}
}
}
validField[pos3] = VALID;
} else if (pos2 >= 0) {
for (int d = 0 ; d < 8 ; d++) {
int dpos = pos2 + Dir9[d];
boolean bf = validField[dpos];
boolean nv = isvalid(dpos, isInside, counter);
validField[dpos] = nv;
if (nv) {
if (!bf) {
candidate[cidx++] = dpos;
}
}
}
validField[pos2] = VALID;
} else {
for (int d = 0 ; d < 8 ; d++) {
int dpos = pos1 + Dir9[d];
boolean bf = validField[dpos];
boolean nv = isvalid(dpos, isInside, counter);
validField[dpos] = nv;
if (nv) {
if (!bf) {
candidate[cidx++] = dpos;
}
}
}
validField[pos1] = VALID;
}
currentScore = score;
} else {
// recover it
if (pos4 >= 0) {
isInside[pos4] = !isInside[pos4];
validField[pos4] = VALID;
for (int d = 0 ; d < 8 ; d++) {
int dpos = pos3 + Dir9[d];
validField[dpos] = rem[18 + d];
}
}
if (pos3 >= 0) {
isInside[pos3] = !isInside[pos3];
validField[pos3] = VALID;
for (int d = 0 ; d < 8 ; d++) {
int dpos = pos2 + Dir9[d];
validField[dpos] = rem[9 + d];
}
}
if (pos2 >= 0) {
isInside[pos2] = !isInside[pos2];
validField[pos2] = VALID;
for (int d = 0 ; d < 8 ; d++) {
int dpos = pos1 + Dir9[d];
validField[dpos] = rem[d];
}
}
isInside[pos1] = !isInside[pos1];
validField[pos1] = VALID;
while (didx >= 1) {
didx--;
counter[diffxPos[didx]] = diffxCnt[didx];
}
}
}
for (boolean[] ptn : new boolean[][]{ buildZero(), buildOne(), buildTwo() }) {
int sc = evaluate(ptn, counter);
if (sc < bestScore) {
bestScore = sc;
bestInside = ptn.clone();
}
}
System.err.println(tr);
return output(bestInside);
}
private boolean[] buildFixedRect(int bsize) {
boolean[][] isInside = new boolean[N + 2][N + 2];
for (int i = bsize ; i <= N + 1 - bsize ; i++) {
for (int j = bsize ; j <= N + 1 - bsize ; j++) {
isInside[i][j] = true;
}
}
return convert(isInside);
}
private boolean[] convert(boolean[][] cv) {
boolean[] ret = new boolean[NMAX];
for (int i = 0 ; i <= N + 1 ; i++) {
for (int j = 0 ; j <= N + 1 ; j++) {
ret[(i << 7) + j] = cv[i][j];
}
}
return ret;
}
private boolean[] buildZero() {
boolean[][] isInside = new boolean[N + 2][N + 2];
isInside[1][1] = true;
return convert(isInside);
}
private boolean[] buildOne() {
boolean[][] isInside = new boolean[N + 2][N + 2];
for (int i = 1 ; i <= N ; i += 4) {
for (int row = i ; row <= Math.min(N, i + 1) ; row++) {
for (int j = 1 ; j <= N ; j++) {
isInside[row][j] = true;
}
}
}
int md = 1;
for (int i = 3 ; i <= N ; i += 4) {
for (int row = i ; row <= Math.min(N, i + 1) ; row++) {
if (md == 1) {
isInside[row][N - 1] = isInside[row][N] = true;
} else {
isInside[row][1] = isInside[row][2] = true;
}
}
md *= -1;
}
return convert(isInside);
}
private boolean[] buildTwo() {
boolean[][] isInside = new boolean[N + 2][N + 2];
for (int i = 1 ; i <= N ; i += 2) {
for (int j = 1 ; j <= N ; j++) {
isInside[i][j] = true;
}
}
int md = 1;
for (int i = 2 ; i <= N ; i += 2) {
if (md == 1) {
isInside[i][N] = true;
} else {
isInside[i][1] = true;
}
md *= -1;
}
return convert(isInside);
}
public boolean isvalid(int pos, boolean[] isInside, int[] count) {
if ((count[pos] & 3) == 0) {
return INVALID;
}
if (count[pos] == 3) {
return VALID;
}
int deg = 0;
int y = ROW;
int x = 0;
if (isInside[pos] != isInside[pos + ROW]) {
deg++;
y = -ROW;
}
if (isInside[pos] != isInside[pos - ROW]) {
deg++;
}
if (isInside[pos] != isInside[pos + 1]) {
deg++;
x = -1;
}
if (isInside[pos] != isInside[pos - 1]) {
deg++;
x = 1;
}
if (deg == 2) {
if (isInside[pos + 1] == isInside[pos - 1]) {
return INVALID;
}
return (isInside[pos] == isInside[pos + y + x]);
} else {
if (x != 0) {
return (isInside[pos] == isInside[pos + x + ROW]) && (isInside[pos] == isInside[pos + x - ROW]);
} else {
return (isInside[pos] == isInside[pos + 1 + y]) && (isInside[pos] == isInside[pos - 1 + y]);
}
}
}
/**
* evaluate the data
*
* @param inside
* @return
*/
public int evaluate(boolean[] inside, int[] counter) {
int score = 0;
for (int i = 1 ; i <= N ; i++) {
for (int j = 1 ; j <= N ; j++) {
int pos = (i << 7) + j;
counter[pos] = 0;
for (int d = 0 ; d < 4 ; d++) {
if (inside[pos] != inside[pos + Dir[d]]) {
counter[pos]++;
}
}
if (Data[pos] >= 0) {
if (counter[pos] != Data[pos]) {
score += 1;
}
}
}
}
return score;
}
static final int[] diffxPos = new int[1001];
static final int[] diffxCnt = new int[1001];
static int didx = 0;
public int evaluateDiffX(boolean[] inside, int[] counter, int pos) {
int score = 0;
int df = didx;
{
int dpos = pos + Dir[0];
if (within[dpos]) {
int cnt = counter[dpos];
int tcnt = (inside[dpos] == inside[pos]) ? cnt+1 : cnt-1;
diffxPos[df] = dpos;
diffxCnt[df++] = cnt;
if (Data[dpos] >= 0) {
if (Data[dpos] != cnt) {
score -= 1;
}
if (Data[dpos] != tcnt) {
score += 1;
}
}
counter[dpos] = tcnt;
}
}
{
int dpos = pos + Dir[1];
if (within[dpos]) {
int cnt = counter[dpos];
int tcnt = (inside[dpos] == inside[pos]) ? cnt+1 : cnt-1;
diffxPos[df] = dpos;
diffxCnt[df++] = cnt;
if (Data[dpos] >= 0) {
if (Data[dpos] != cnt) {
score -= 1;
}
if (Data[dpos] != tcnt) {
score += 1;
}
}
counter[dpos] = tcnt;
}
}
{
int dpos = pos + Dir[2];
if (within[dpos]) {
int cnt = counter[dpos];
int tcnt = (inside[dpos] == inside[pos]) ? cnt+1 : cnt-1;
diffxPos[df] = dpos;
diffxCnt[df++] = cnt;
if (Data[dpos] >= 0) {
if (Data[dpos] != cnt) {
score -= 1;
}
if (Data[dpos] != tcnt) {
score += 1;
}
}
counter[dpos] = tcnt;
}
}
{
int dpos = pos + Dir[3];
if (within[dpos]) {
int cnt = counter[dpos];
int tcnt = (inside[dpos] == inside[pos]) ? cnt+1 : cnt-1;
diffxPos[df] = dpos;
diffxCnt[df++] = cnt;
if (Data[dpos] >= 0) {
if (Data[dpos] != cnt) {
score -= 1;
}
if (Data[dpos] != tcnt) {
score += 1;
}
}
counter[dpos] = tcnt;
}
}
int cnt = counter[pos];
if (cnt == 2) {
didx = df;
return score;
}
diffxPos[df] = pos;
diffxCnt[df++] = cnt;
if (Data[pos] != cnt) {
score -= 1;
}
cnt = 4 - cnt;
if (Data[pos] != cnt) {
score += 1;
}
counter[pos] = cnt;
didx = df;
return score;
}
/**
* output
*
* @param inside
* @return
*/
private String output(boolean[] inside) {
boolean[][][] lines = new boolean[N + 3][N + 3][4];
for (int i = 0 ; i <= N + 1 ; i++) {
for (int j = 0 ; j <= N + 1 ; j++) {
int pos = i * ROW + j;
if (!inside[i * ROW + j]) {
// up
if (i >= 1 && inside[pos - ROW]) {
lines[i][j][0] = true;
lines[i][j + 1][3] = true;
}
// left
if (j >= 1 && inside[pos - 1]) {
lines[i][j][1] = true;
lines[i + 1][j][2] = true;
}
// bottom
if (i <= N && inside[pos + ROW]) {
lines[i + 1][j][0] = true;
lines[i + 1][j + 1][3] = true;
}
// right
if (j <= N && inside[pos + 1]) {
lines[i][j + 1][1] = true;
lines[i + 1][j + 1][2] = true;
}
}
}
}
StringBuffer b = new StringBuffer();
int startX = -1;
int startY = -1;
build: for (int i = 0 ; i <= N + 1 ; i++) {
for (int j = 0 ; j <= N + 1 ; j++) {
boolean isok = false;
for (int d = 0 ; d < 4 ; d++) {
if (lines[i][j][d]) {
isok = true;
}
}
if (isok) {
startX = j;
startY = i;
int prevX = -1;
int prevY = -1;
int nowX = startX;
int nowY = startY;
while (true) {
for (int d = 0 ; d < 4 ; d++) {
if (lines[nowY][nowX][d]) {
if (nowX + Dx[d] == prevX && nowY + Dy[d] == prevY) {
continue;
}
prevX = nowX;
prevY = nowY;
nowX += Dx[d];
nowY += Dy[d];
b.append(Dc[d]);
break;
}
}
if (nowX == startX && nowY == startY) {
break;
}
}
break build;
}
}
}
return (startY - 1) + " " + (startX - 1) + " " + b.toString();
}
/**
* main
*
* @param args
* @throws NumberFormatException
* @throws IOException
*/
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int SZ = Integer.valueOf(reader.readLine());
String[] diagram = new String[SZ];
for (int i = 0 ; i < SZ ; i++) {
diagram[i] = reader.readLine();
}
FixTheFence fence = new FixTheFence();
if (args.length >= 1) {
fence._xtime = Long.valueOf(args[0]);
}
if (args.length >= 2) {
fence._debug = Integer.valueOf(args[1]) >= 1;
}
String ret = fence.findLoop(diagram);
System.out.println(ret);
System.out.flush();
}
static final class XorShift {
int x = 123456789;
int y = 362436069;
int z = 521288629;
int w = 88675123;
int nextInt(int n) {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = (w ^ (w >>> 19)) ^ (t ^ (t >>> 8));
final int r = w % n;
return r < 0 ? r + n : r;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment