import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import java.io.*;
import java.util.*;
import java.security.*;
import javax.swing.*;
import javax.imageio.*;
// --------------------------------------------------------
public class GarlandOfLightsVis {
static int maxS = 100, minS = 10;
static int maxC = 4, minC = 2;
static int dr[] = { -1, 1, 0, 0 },
dc[] = { 0, 0, -1, 1 };
static int typeDirs[][] = { {1, 3}, {1, 2}, {0, 2}, {0, 3}, {2, 3}, {0, 1} };
// ---------------------------------------------------
int H, W; // space size
int C; // colors used for the lights
int N; // number of lights
int[] lightTypes; // input lights types
char[] lightColors; // input lights colors
String[] lightsArg; // input lights: type 0..5 + color a..d
int[] lightsRet; // a permutation of numbers 0..H*W-1 - the light used in appropriate position
boolean[] longestLoop; // whether tile in slot i is part of the longest loop (for visualization)
// ---------------------------------------------------
String generate(String seedStr) {
try {
SecureRandom rnd = SecureRandom.getInstance("SHA1PRNG");
long seed = Long.parseLong(seedStr);
rnd.setSeed(seed);
H = rnd.nextInt(maxS - minS + 1) + minS;
W = rnd.nextInt(maxS - minS + 1) + minS;
C = rnd.nextInt(maxC - minC + 1) + minC;
if (seed == 1) {
H = W = 5;
C = maxC;
}
else if (seed == 2) {
H = 5;
W = 10;
C = minC;
}
else if (seed == 3) {
H = W = maxS;
C = maxC;
}
else if (seed == 4) {
H = W = maxS;
C = minC;
}
if (vis) {
SZX = W * SZ;
SZY = H * SZ;
}
// generate the array of input lights (types)
N = W * H;
lightTypes = new int[N];
for (int i = 0; i < N; ++i) {
lightTypes[i] = rnd.nextInt(6);
}
// generate the colors of input lights
// verify that each color is used at least once
lightColors = new char[N];
while (true) {
int[] nColors = new int[C];
for (int i = 0; i < N; ++i) {
int col = rnd.nextInt(C);
lightColors[i] = (char)(col + 'a');
nColors[col]++;
}
boolean ok = true;
for (int i = 0; i < C; ++i)
if (nColors[i] == 0)
ok = false;
if (ok)
break;
}
// convert to string argument
lightsArg = new String[N];
for (int i = 0; i < N; ++i) {
lightsArg[i] = lightTypes[i] + "" + lightColors[i];
}
StringBuffer sb = new StringBuffer();
sb.append("H = ").append(H).append('\n');
sb.append("W = ").append(W).append('\n');
sb.append("C = ").append(C).append('\n');
if (seed < 3)
for (int i = 0; i < N; ++i)
sb.append(lightsArg[i]).append((i+1) % W > 0 ? ' ' : '\n');
return sb.toString();
}
catch (Exception e) {
addFatalError("An exception occurred while generating test case.");
e.printStackTrace();
return "";
}
}
// ---------------------------------------------------
public double runTest(String seed) {
try {
String test = generate(seed);
if (debug)
System.out.println(test);
// call user's solution and get return
lightsRet = new int[N];
boolean showOutput = true;
if (showOutput) {
try {
if (exec != null) {
lightsRet = create(H, W, lightsArg);
} else {
GarlandOfLights garlandOfLights = new GarlandOfLights();
lightsRet = garlandOfLights.create(H, W, lightsArg);
}
} catch (Exception e) {
addFatalError("Failed to get result from create.");
return 0;
}
if (lightsRet.length != N) {
addFatalError("Your return must contain " + N + " elements, but it contained " + lightsRet.length + ".");
return 0;
}
// check that this is a valid permutation
boolean[] usedP = new boolean[N];
for (int i = 0; i < N; ++i) {
if (lightsRet[i] < 0 || lightsRet[i] >= N) {
addFatalError("All elements of your return must be between 0 and " + (N-1) + ", and your return contained " + lightsRet[i] + ".");
return 0;
}
if (usedP[lightsRet[i]]) {
addFatalError("All elements of your return must be unique, and your return contained " + lightsRet[i] + " twice.");
return 0;
}
usedP[lightsRet[i]] = true;
}
}
else {
// use the starting layout
for (int i = 0; i < N; ++i)
lightsRet[i] = i;
}
if (debug) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < N; ++i)
sb.append(lightsArg[lightsRet[i]]).append((i+1) % W > 0 ? ' ' : '\n');
System.out.println("Return grid:");
System.out.println(sb.toString());
}
// find the longest valid loop of garland tiles
if (vis) {
longestLoop = new boolean[N];
}
int maxLen = 0;
boolean[] used = new boolean[N];
boolean[] curLoop = new boolean[N];
// iterate through positions in the grid in row-wise order
for (int start = 0; start < N; ++start) {
if (used[start])
continue;
boolean goodLoop = true, goodColors = true;
int len = 0;
int startR = start / W;
int startC = start % W;
Arrays.fill(curLoop, false);
curLoop[start] = true;
// track the garland starting at this tile
StringBuffer sb = new StringBuffer();
int startLight = lightsRet[start];
int startType = lightTypes[startLight];
// go in one direction at a time (clockwise first) unless it's a loop
for (int d = 1; d >= 0; d--) {
int r = startR, c = startC;
if (d == 1)
sb.append("(" + r + "," + c + ")");
int curColor = lightColors[startLight];
int curDir = typeDirs[startType][d];
while (true) {
// move in the direction diven by curDir
int nextR = r + dr[curDir];
int nextC = c + dc[curDir];
int nextCell = nextR * W + nextC;
if (nextR < 0 || nextR == H || nextC < 0 || nextC == W || used[nextCell]) {
// the direction leads outside the border or to a previously used cell - not a loop
goodLoop = false;
break;
}
int nextLight = lightsRet[nextCell];
int nextType = lightTypes[nextLight];
// check whether next tile is connected to previous one
int nextDir = -1;
if (typeDirs[nextType][0] == (curDir ^ 1))
nextDir = typeDirs[nextType][1];
else if (typeDirs[nextType][1] == (curDir ^ 1))
nextDir = typeDirs[nextType][0];
else {
// next tile is not connected to the previous one - not a loop
goodLoop = false;
break;
}
// next tile is connected to the previous one - can continue
// mark next tile as part of the loop
len++;
used[nextCell] = true;
curLoop[nextCell] = true;
sb.append(", (" + nextR + "," + nextC + ")");
// check the colors
if (curColor == lightColors[nextLight]) {
// two of the same color in row - mark as bad but continue along the loop
goodColors = false;
}
if (nextR == startR && nextC == startC)
break;
// next is now current
r = nextR;
c = nextC;
curColor = lightColors[nextLight];
curDir = nextDir;
}
if (goodLoop)
break;
}
if (debug && (chains || goodLoop)) {
System.out.print(goodLoop && goodColors ? "Good loop" : (goodLoop ? "Bad loop" : "Chain"));
System.out.println(" of length " + (goodLoop ? len : len+1) + ": " + sb.toString());
}
if (goodLoop && goodColors) {
// we returned to the starting tile with all connected tiles and alternating colors
if (len > maxLen) {
maxLen = len;
if (vis) {
longestLoop = Arrays.copyOf(curLoop, N);
}
}
}
}
if (vis) {
// draw the image
jf.setSize(SZX+10,SZY+30);
jf.setVisible(true);
draw();
}
return maxLen * 1.0 / N;
}
catch (Exception e) {
addFatalError("An exception occurred while trying to process your program's results.");
e.printStackTrace();
return -1;
}
}
// ------------- visualization part ----------------------
static String exec, fileName;
static boolean vis, debug, save, chains;
static Process proc;
JFrame jf;
Vis v;
InputStream is;
OutputStream os;
BufferedReader br;
// problem-specific drawing params
int SZX, SZY;
static int SZ;
// ---------------------------------------------------
int[] create(int H, int W, String[] lights) throws IOException {
// pass the params to the solution and get the return
int i;
StringBuffer sb = new StringBuffer();
sb.append(H).append('\n');
sb.append(W).append('\n');
for (i = 0; i < H*W; ++i)
sb.append(lights[i]).append('\n');
os.write(sb.toString().getBytes());
os.flush();
// get the return - an array of integers
int nret = Integer.parseInt(br.readLine());
int[] ret = new int[nret];
for (i = 0; i < nret; ++i)
ret[i] = Integer.parseInt(br.readLine());
return ret;
}
// ---------------------------------------------------
void draw() {
if (!vis) return;
v.repaint();
}
// ---------------------------------------------------
int[] colors = {0xE43BA6, 0x00BCF2, 0xFCE100, 0x7CD300};
// ---------------------------------------------------
@SuppressWarnings("serial")
public class Vis extends JPanel implements WindowListener {
public void paint(Graphics g) {
try {
// do painting here
BufferedImage bi = new BufferedImage(SZX+5,SZY+5,BufferedImage.TYPE_INT_RGB);
Graphics2D g2 = (Graphics2D)bi.getGraphics();
// background
g2.setColor(new Color(0xE3E3E3));
g2.fillRect(0,0,SZX+10,SZY+10);
// FontMetrics fm = g2.getFontMetrics();
// white background for cells which are part of the longest loop
g2.setColor(Color.WHITE);
for (int r = 0; r < H; ++r)
for (int c = 0; c < W; ++c) {
if (longestLoop[r * W + c])
g2.fillRect(c * SZ, r * SZ, SZ, SZ);
}
// lines between cells
g2.setColor(new Color(0xAAAAAA));
for (int i = 0; i <= H; i++)
g2.drawLine(0, i*SZ, W*SZ, i*SZ);
for (int i = 0; i <= W; i++)
g2.drawLine(i*SZ, 0, i*SZ, H*SZ);
// wires on tiles
g2.setColor(Color.BLACK);
int d = 0;
if (SZ > 12) {
g2.setStroke(new BasicStroke(3.0f));
d = 1;
}
for (int r = 0; r < H; ++r)
for (int c = 0; c < W; ++c) {
int type = lightTypes[lightsRet[r * W + c]];
for (int k = 0; k < 2; ++k) {
g2.drawLine(c * SZ + SZ/2, r * SZ + SZ/2, c * SZ + SZ/2 + dc[typeDirs[type][k]] * (SZ/2-d), r * SZ + SZ/2 + dr[typeDirs[type][k]] * (SZ/2-d));
}
}
for (int r = 0; r < H; ++r)
for (int c = 0; c < W; ++c) {
int color = lightColors[lightsRet[r * W + c]] - 'a';
g2.setColor(new Color(colors[color]));
g2.fillOval(c * SZ + SZ/2 - SZ/4, r * SZ + SZ/2 - SZ/4, SZ/2, SZ/2);
}
g.drawImage(bi,0,0,SZX+5,SZY+5,null);
if (save) {
ImageIO.write(bi,"png", new File(fileName +".png"));
}
}
catch (Exception e) { e.printStackTrace(); }
}
public Vis() {
jf.addWindowListener(this);
}
// WindowListener
public void windowClosing(WindowEvent e) {
if(proc != null)
try { proc.destroy(); }
catch (Exception ex) { ex.printStackTrace(); }
System.exit(0);
}
public void windowActivated(WindowEvent e) { }
public void windowDeactivated(WindowEvent e) { }
public void windowOpened(WindowEvent e) { }
public void windowClosed(WindowEvent e) { }
public void windowIconified(WindowEvent e) { }
public void windowDeiconified(WindowEvent e) { }
}
// ---------------------------------------------------
public GarlandOfLightsVis(long seed) {
this("" + seed);
}
double score;
public GarlandOfLightsVis(String seed) {
//interface for runTest
if (vis)
{ jf = new JFrame();
v = new Vis();
jf.getContentPane().add(v);
}
if (exec != null) {
try {
Runtime rt = Runtime.getRuntime();
proc = rt.exec(exec);
os = proc.getOutputStream();
is = proc.getInputStream();
br = new BufferedReader(new InputStreamReader(is));
new ErrorReader(proc.getErrorStream()).start();
} catch (Exception e) {
e.printStackTrace();
}
}
score = runTest(seed);
if (debug) {
System.out.println("Score = "+score);
}
if (proc != null)
try { proc.destroy(); }
catch (Exception e) { e.printStackTrace(); }
}
// ---------------------------------------------------
public static void main(String[] args) {
String seed = "1";
SZ = 12;
for (int i = 0; i<args.length; i++)
{ if (args[i].equals("-seed"))
seed = args[++i];
if (args[i].equals("-exec"))
exec = args[++i];
if (args[i].equals("-vis"))
vis = true;
if (args[i].equals("-debug"))
debug = true;
if (args[i].equals("-size"))
SZ = Integer.parseInt(args[++i]);
if (args[i].equals("-save"))
save = true;
if (args[i].equals("-chains"))
chains = true;
}
if ((seed.equals("1") || seed.equals("2")) && SZ < 30)
SZ = 30;
if (chains)
debug = true;
if (save) {
fileName = seed;
vis = true;
}
// Visualize
boolean doVisualize = true;
if (doVisualize) {
vis = true;
GarlandOfLightsVis gv = new GarlandOfLightsVis(1);
System.out.println(gv.score);
}
// Calculate score
boolean doCalculateScore = true;
if (doCalculateScore) {
vis = false;
double sum = 0;
int num = 0;
for (int i = 1; i <= 10; i++) {
double score = new GarlandOfLightsVis(i).score;
System.out.println(i + ": " + score);
sum += score;
num += 1;
}
System.out.println("Average score: " + sum / num);
}
}
// ---------------------------------------------------
void addFatalError(String message) {
System.out.println(message);
}
}
class ErrorReader extends Thread{
InputStream error;
public ErrorReader(InputStream is) {
error = is;
}
public void run() {
try {
byte[] ch = new byte[50000];
int read;
while ((read = error.read(ch)) > 0)
{ String s = new String(ch,0,read);
System.out.print(s);
System.out.flush();
}
} catch(Exception e) { }
}
}
Comments