Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/*
Change log
----------
*/
import javax.swing.*;
import java.awt.*;
import java.awt.event.KeyAdapter;
import java.awt.event.KeyEvent;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.security.SecureRandom;
import java.util.*;
import java.util.List;
class Constants {
public static final int[] DY = new int[]{1, 0, -1, 0};
public static final int[] DX = new int[]{0, -1, 0, 1};
public static final double PENALTY = 100;
}
class TestCase {
public static final int MIN_YARD_SIZE = 20;
public static final int MAX_YARD_SIZE = 80;
public static final int MAX_HEIGHT = 10;
public static final int MIN_BEDS = 0;
public static final int MAX_BEDS = 30;
public static final int MIN_LEVELS = 1;
public static final int MAX_LEVELS = 100;
public static final int MAX_TURN_COST = 10;
public static final int MAX_FORWARD_COST = 10;
public static final int MAX_SLOPE_COST = 10;
public int yardSize;
public char[][] yard;
public int startX, startY;
public int turnCost, forwardCost, slopeCost;
public SecureRandom rnd = null;
public void addRectangular(int maxr, char ch) {
int x1 = rnd.nextInt(yardSize);
int y1 = rnd.nextInt(yardSize);
int x2 = x1 + rnd.nextInt(maxr);
int y2 = y1 + rnd.nextInt(maxr);
for (int x = x1; x <= x2; x++)
for (int y = y1; y <= y2; y++)
yard[y % yardSize][x % yardSize] = ch;
}
public void addCircular(int maxr, char ch) {
int x1 = rnd.nextInt(yardSize);
int y1 = rnd.nextInt(yardSize);
int r = rnd.nextInt(maxr);
double rx = 1.0 + rnd.nextDouble();
double ry = 1.0 + rnd.nextDouble();
for (int x = x1 - r * 2; x <= x1 + r * 2; x++)
for (int y = y1 - r * 2; y <= y1 + r * 2; y++) {
double d = (x - x1) * (x - x1) * rx + (y - y1) * (y - y1) * ry;
if (d <= r * r) {
yard[(y + yardSize * 2) % yardSize][(x + yardSize * 2) % yardSize] = ch;
}
}
}
public TestCase(long seed) {
try {
rnd = SecureRandom.getInstance("SHA1PRNG");
} catch (Exception e) {
System.err.println("ERROR: unable to generate test case.");
System.exit(1);
}
rnd.setSeed(seed);
yardSize = rnd.nextInt(MAX_YARD_SIZE - MIN_YARD_SIZE + 1) + MIN_YARD_SIZE;
if (seed == 1) yardSize = 20;
yard = new char[yardSize][yardSize];
turnCost = yardSize * (rnd.nextInt(MAX_TURN_COST) + 1) / 4;
forwardCost = rnd.nextInt(MAX_FORWARD_COST) + 1;
slopeCost = yardSize * (rnd.nextInt(MAX_SLOPE_COST) + 1);
int nLevels = rnd.nextInt(MAX_LEVELS - MIN_LEVELS + 1) + MIN_LEVELS;
int nBeds = rnd.nextInt(MAX_BEDS - MIN_BEDS + 1) + MIN_BEDS;
// Make a clean level area
for (int y = 0; y < yardSize; y++)
for (int x = 0; x < yardSize; x++)
yard[y][x] = '0';
// Add levels
for (int i = 0; i < nLevels; i++) {
int h = rnd.nextInt(MAX_HEIGHT);
if (rnd.nextInt(2) == 0) {
addCircular(yardSize / 2, (char) ('0' + h));
} else {
addRectangular(yardSize / 2, (char) ('0' + h));
}
}
// Smooth levels
for (int k = 0; k < 2; k++)
for (int y = 0; y < yardSize; y++)
for (int x = 0; x < yardSize; x++) {
int v = (yard[y][x] * 4 +
yard[(y + 1) % yardSize][x] +
yard[(y - 1 + yardSize) % yardSize][x] +
yard[y][(x + 1) % yardSize] +
yard[y][(x - 1 + yardSize) % yardSize]) / 8;
yard[y][x] = (char) v;
}
// Add beds
for (int i = 0; i < nBeds; i++) {
if (rnd.nextInt(2) == 0) {
addCircular(yardSize / 5, '.');
} else {
addRectangular(yardSize / 5, '.');
}
}
// Add mower
do {
startX = rnd.nextInt(yardSize);
startY = rnd.nextInt(yardSize);
} while (yard[startY][startX] == '.');
}
}
class Drawer extends JFrame {
public static final int EXTRA_WIDTH = 300;
public static final int EXTRA_HEIGHT = 50;
public World world;
public DrawerPanel panel;
public int cellSize, yardSize;
public int width, height;
public boolean pauseMode = false;
public boolean debugMode = false;
class DrawerKeyListener extends KeyAdapter {
public void keyPressed(KeyEvent e) {
synchronized (keyMutex) {
if (e.getKeyChar() == ' ') {
pauseMode = !pauseMode;
}
if (e.getKeyChar() == 'd') {
debugMode = !debugMode;
}
keyPressed = true;
keyMutex.notifyAll();
}
}
}
class DrawerPanel extends JPanel {
public void paint(Graphics g) {
synchronized (world.worldLock) {
g.setColor(new Color(0, 128, 0));
g.fillRect(15, 15, cellSize * yardSize + 1, cellSize * yardSize + 1);
g.setColor(Color.BLACK);
for (int i = 0; i <= yardSize; i++) {
g.drawLine(15 + i * cellSize, 15, 15 + i * cellSize, 15 + cellSize * yardSize);
g.drawLine(15, 15 + i * cellSize, 15 + cellSize * yardSize, 15 + i * cellSize);
}
for (int i = 0; i < yardSize; i++) {
for (int j = 0; j < yardSize; j++) {
if (world.tc.yard[i][j] >= '0' && world.tc.yard[i][j] <= '9') {
int col = 64 + (world.tc.yard[i][j] - '0') * 192 / 10;
g.setColor(new Color(0, col, 0));
g.fillRect(15 + j * cellSize + 1, 15 + i * cellSize + 1, cellSize - 1, cellSize - 1);
} else if (world.tc.yard[i][j] == '.') {
g.setColor(new Color(64, 64, 0));
g.fillRect(15 + j * cellSize + 1, 15 + i * cellSize + 1, cellSize - 1, cellSize - 1);
} else if (world.tc.yard[i][j] >= 'A' && world.tc.yard[i][j] <= 'J') {
int col = 64 + (world.tc.yard[i][j] - 'A') * 192 / 10;
for (int yy = 0; yy < 4; yy++)
for (int xx = 0; xx < 4; xx++) {
if (((xx + yy) & 1) == 1)
g.setColor(new Color(0, col, 0));
else
g.setColor(new Color(0, 0, 0));
g.fillRect(15 + j * cellSize + 1 + xx * cellSize / 4, 15 + i * cellSize + 1 + yy * cellSize / 4, cellSize / 4, cellSize / 4);
}
}
}
}
g.setColor(Color.WHITE);
g.fillOval(15 + (world.mowX) * cellSize + cellSize / 4, 15 + (world.mowY) * cellSize + cellSize / 4, cellSize - cellSize / 2, cellSize - cellSize / 2);
g.drawLine(15 + (world.mowX) * cellSize + cellSize / 2, 15 + (world.mowY) * cellSize + cellSize / 2,
15 + (world.mowX + Constants.DX[world.mowD]) * cellSize + cellSize / 2, 15 + (world.mowY + Constants.DY[world.mowD]) * cellSize + cellSize / 2);
g.drawRect(15 + world.tc.startX * cellSize, 15 + world.tc.startY * cellSize, cellSize + 1, cellSize + 1);
g.setColor(Color.BLACK);
g.setFont(new Font("Arial", Font.BOLD, 12));
Graphics2D g2 = (Graphics2D) g;
int horPos = 40 + yardSize * cellSize;
g2.drawString("Yard size = " + yardSize, horPos, 30);
g2.drawString("Step = " + world.curStep, horPos, 50);
g2.drawString(String.format("Forward cost = %.2f", world.numForward * world.tc.forwardCost), horPos, 70);
g2.drawString(String.format("Turn cost = %.2f", world.numTurns * world.tc.turnCost), horPos, 90);
g2.drawString(String.format("Slope cost = %.2f", world.numSlope * world.tc.slopeCost), horPos, 110);
double score = world.numForward * world.tc.forwardCost + world.numTurns * world.tc.turnCost + world.numSlope * world.tc.slopeCost;
int grass = 0;
for (int y = 0; y < world.tc.yardSize; y++)
for (int x = 0; x < world.tc.yardSize; x++)
if (world.isGrass(x, y)) grass++;
g2.drawString(String.format("Penalty = %.2f", world.tc.slopeCost * Constants.PENALTY * grass), horPos, 130);
score += world.tc.slopeCost * Constants.PENALTY * grass;
g2.drawString(String.format("Score = %.2f", score), horPos, 160);
}
}
}
class DrawerWindowListener extends WindowAdapter {
public void windowClosing(WindowEvent event) {
System.exit(0);
}
}
final Object keyMutex = new Object();
boolean keyPressed;
public void processPause() {
synchronized (keyMutex) {
if (!pauseMode) {
return;
}
keyPressed = false;
while (!keyPressed) {
try {
keyMutex.wait();
} catch (InterruptedException e) {
// do nothing
}
}
}
}
public Drawer(World world, int cellSize) {
super();
panel = new DrawerPanel();
getContentPane().add(panel);
addWindowListener(new DrawerWindowListener());
this.world = world;
yardSize = world.tc.yardSize;
this.cellSize = cellSize;
width = cellSize * yardSize + EXTRA_WIDTH;
height = cellSize * yardSize + EXTRA_HEIGHT;
addKeyListener(new DrawerKeyListener());
setSize(width, height);
setTitle("TCO'15 Marathon Championship Round");
setResizable(false);
setVisible(true);
}
}
class World {
final Object worldLock = new Object();
TestCase tc;
int curStep = -1;
double numTurns;
double numSlope;
double numForward;
int mowX, mowY, mowD;
public World(TestCase tc) {
this.tc = tc;
numTurns = numSlope = numForward = 0;
mowX = tc.startX;
mowY = tc.startY;
mowD = 0;
}
public int getHeight(int x, int y) {
if (tc.yard[y][x] >= '0' && tc.yard[y][x] <= '9') {
return tc.yard[y][x] - '0';
} else if (tc.yard[y][x] >= 'A' && tc.yard[y][x] <= 'J') {
return tc.yard[y][x] - 'A';
}
return 0;
}
public boolean isGrass(int x, int y) {
return (tc.yard[y][x] >= '0' && tc.yard[y][x] <= '9');
}
public boolean updateMower(char cmd) {
synchronized (worldLock) {
if (cmd == 'S') {
int newX = (mowX + Constants.DX[mowD] + tc.yardSize) % tc.yardSize;
int newY = (mowY + Constants.DY[mowD] + tc.yardSize) % tc.yardSize;
int slope = Math.max(0, getHeight(newX, newY) - getHeight(mowX, mowY));
if (isGrass(mowX, mowY)) {
tc.yard[mowY][mowX] = (char) (tc.yard[mowY][mowX] - '0' + 'A');
numForward += 1.0;
numSlope += slope;
} else {
// already mowed, add 20% of cost
numForward += 0.2;
numSlope += 0.2 * slope;
}
mowX = newX;
mowY = newY;
if (tc.yard[mowY][mowX] == '.') {
System.err.println("ERROR: You can only move over grass areas. Invalid move going over non-grass area at (" + mowY + "," + mowX + ").");
return false;
}
} else if (cmd == 'L') {
mowD = (3 + mowD) % 4;
if (isGrass(mowX, mowY))
numTurns += 1.0;
else
numTurns += 0.2;
} else if (cmd == 'R') {
mowD = (1 + mowD) % 4;
if (isGrass(mowX, mowY))
numTurns += 1.0;
else
numTurns += 0.2;
} else {
System.err.println("ERROR: Invalid command [" + cmd + "] received, command must be L,R or S.");
return false;
}
}
return true;
}
public void startNewStep() {
curStep++;
}
}
public class LawnMowingVis {
public static boolean vis = false;
public static boolean debug = false;
public static int cellSize = 12;
public static int delay = 100;
public static boolean startPaused = false;
public Result runTest(long seed) {
TestCase tc = new TestCase(seed);
Result res = new Result();
res.seed = seed;
res.N = tc.yardSize;
res.TC = tc.turnCost;
res.SC = tc.slopeCost;
res.FC = tc.forwardCost;
World world = new World(tc);
Drawer drawer = null;
if (vis) {
drawer = new Drawer(world, cellSize);
drawer.debugMode = debug;
if (startPaused) {
drawer.pauseMode = true;
}
}
LawnMowing obj = new LawnMowing();
long startTime = System.currentTimeMillis();
String[] yard = new String[tc.yardSize];
res.elapsed = System.currentTimeMillis() - startTime;
for (int i = 0; i < tc.yardSize; i++) {
yard[i] = String.valueOf(tc.yard[i]);
}
String cmd = obj.getMoves(yard, tc.turnCost, tc.forwardCost, tc.slopeCost, tc.startX, tc.startY);
for (int t = 0; t < cmd.length(); t++) {
if (vis) {
drawer.processPause();
drawer.repaint();
try {
Thread.sleep(delay);
} catch (Exception e) {
// do nothing
}
}
world.startNewStep();
if (!world.updateMower(cmd.charAt(t))) {
return res;
}
}
// Count un-cut grass
int grass = 0;
for (int y = 0; y < tc.yardSize; y++)
for (int x = 0; x < tc.yardSize; x++)
if (world.isGrass(x, y)) {
grass++;
}
// Should end at starting cell
if (world.mowX != tc.startX || world.mowY != tc.startY) {
System.err.println("ERROR: Ending location should be where you started. The mower ended at (" + world.mowY + "," + world.mowX + ") instead of (" + tc.startY + "," + tc.startX + ").");
return res;
}
res.score = world.numTurns * tc.turnCost + world.numForward * tc.forwardCost + world.numSlope * tc.slopeCost;
res.penalty = tc.slopeCost * Constants.PENALTY * grass;
res.score += res.penalty;
return res;
}
private static final int THREAD_COUNT = 35;
public static void main(String[] args) throws Exception {
long seed = 1, begin = -1, end = -1;
for (int i = 0; i < args.length; i++)
if (args[i].equals("-seed")) {
seed = Long.parseLong(args[++i]);
} else if (args[i].equals("-b")) {
begin = Long.parseLong(args[++i]);
} else if (args[i].equals("-e")) {
end = Long.parseLong(args[++i]);
} else if (args[i].equals("-vis")) {
vis = true;
} else if (args[i].equals("-debug")) {
debug = true;
} else if (args[i].equals("-sz")) {
cellSize = Integer.parseInt(args[++i]);
} else if (args[i].equals("-delay")) {
delay = Integer.parseInt(args[++i]);
} else if (args[i].equals("-pause")) {
startPaused = true;
} else {
System.out.println("WARNING: unknown argument " + args[i] + ".");
}
if (begin != -1 && end != -1) {
vis = false;
ArrayList<Long> seeds = new ArrayList<>();
for (long i = begin; i <= end; ++i) {
seeds.add(i);
}
int len = seeds.size();
Result[] results = new Result[len];
TestThread[] threads = new TestThread[THREAD_COUNT];
int prev = 0;
for (int i = 0; i < THREAD_COUNT; ++i) {
int next = len * (i + 1) / THREAD_COUNT;
threads[i] = new TestThread(i, prev, next - 1, seeds, results);
prev = next;
}
for (int i = 0; i < THREAD_COUNT; ++i) {
threads[i].start();
}
for (int i = 0; i < THREAD_COUNT; ++i) {
threads[i].join();
}
double sum = 0;
for (Result result : results) {
System.out.println(result);
System.out.println();
sum += result.score;
}
System.out.println("ave:" + (sum / results.length));
} else {
LawnMowingVis tester = new LawnMowingVis();
Result res = tester.runTest(seed);
System.out.println(res);
}
}
private static class TestThread extends Thread {
int threadId;
int begin, end;
ArrayList<Long> seeds;
Result[] results;
TestThread(int threadId, int begin, int end, ArrayList<Long> seeds, Result[] results) {
this.threadId = threadId;
this.begin = begin;
this.end = end;
this.seeds = seeds;
this.results = results;
}
public void run() {
for (int i = begin; i <= end; ++i) {
try {
LawnMowingVis f = new LawnMowingVis();
Result res = f.runTest(seeds.get(i));
results[i] = res;
} catch (Exception e) {
e.printStackTrace();
results[i] = new Result();
results[i].seed = seeds.get(i);
}
}
}
}
private static class Result {
long seed;
int N, TC, FC, SC;
double score, penalty;
long elapsed;
public String toString() {
String ret = String.format("seed:%4d\n", seed);
ret += String.format("N:%2d TC:%3d FC:%3d SC:%3d\n", N, TC, FC, SC);
ret += String.format("elapsed:%.4f\n", elapsed / 1000.0);
ret += String.format("score:%.2f penalty:%.2f", score, penalty);
return ret;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment