Advertisement
mikhail_dvorkin

GarlandOfLightsVis

Dec 22nd, 2017
383
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 17.57 KB | None | 0 0
  1. import java.awt.*;
  2. import java.awt.event.*;
  3. import java.awt.image.*;
  4. import java.io.*;
  5. import java.util.*;
  6. import java.security.*;
  7.  
  8. import javax.swing.*;
  9. import javax.imageio.*;
  10.  
  11. // --------------------------------------------------------
  12. public class GarlandOfLightsVis {
  13.     static int maxS = 100, minS = 10;
  14.     static int maxC = 4, minC = 2;
  15.     static int dr[] = { -1, 1,  0, 0 },
  16.                dc[] = {  0, 0, -1, 1 };
  17.     static int typeDirs[][] = { {1, 3}, {1, 2}, {0, 2}, {0, 3}, {2, 3}, {0, 1} };
  18.     // ---------------------------------------------------
  19.     int H, W;                       // space size
  20.     int C;                          // colors used for the lights
  21.     int N;                          // number of lights
  22.     int[] lightTypes;               // input lights types
  23.     char[] lightColors;             // input lights colors
  24.     String[] lightsArg;             // input lights: type 0..5 + color a..d
  25.     int[] lightsRet;                // a permutation of numbers 0..H*W-1 - the light used in appropriate position
  26.     boolean[] longestLoop;          // whether tile in slot i is part of the longest loop (for visualization)
  27.     // ---------------------------------------------------
  28.     String generate(String seedStr) {
  29.       try {
  30.         SecureRandom rnd = SecureRandom.getInstance("SHA1PRNG");
  31.         long seed = Long.parseLong(seedStr);
  32.         rnd.setSeed(seed);
  33.  
  34.         H = rnd.nextInt(maxS - minS + 1) + minS;
  35.         W = rnd.nextInt(maxS - minS + 1) + minS;
  36.         C = rnd.nextInt(maxC - minC + 1) + minC;
  37.         if (seed == 1) {
  38.             H = W = 5;
  39.             C = maxC;
  40.         }
  41.         else if (seed == 2) {
  42.             H = 5;
  43.             W = 10;
  44.             C = minC;
  45.         }
  46.         else if (seed == 3) {
  47.             H = W = maxS;
  48.             C = maxC;
  49.         }
  50.         else if (seed == 4) {
  51.             H = W = maxS;
  52.             C = minC;
  53.         }
  54.  
  55.         if (vis) {
  56.             SZX = W * SZ;
  57.             SZY = H * SZ;
  58.         }
  59.  
  60.         // generate the array of input lights (types)
  61.         N = W * H;
  62.         lightTypes = new int[N];
  63.         for (int i = 0; i < N; ++i) {
  64.             lightTypes[i] = rnd.nextInt(6);
  65.         }
  66.         // generate the colors of input lights
  67.         // verify that each color is used at least once
  68.         lightColors = new char[N];
  69.         while (true) {
  70.             int[] nColors = new int[C];
  71.             for (int i = 0; i < N; ++i) {
  72.                 int col = rnd.nextInt(C);
  73.                 lightColors[i] = (char)(col + 'a');
  74.                 nColors[col]++;
  75.             }
  76.             boolean ok = true;
  77.             for (int i = 0; i < C; ++i)
  78.                 if (nColors[i] == 0)
  79.                     ok = false;
  80.             if (ok)
  81.                 break;
  82.         }
  83.  
  84.         // convert to string argument
  85.         lightsArg = new String[N];
  86.         for (int i = 0; i < N; ++i) {
  87.             lightsArg[i] = lightTypes[i] + "" + lightColors[i];
  88.         }
  89.  
  90.         StringBuffer sb = new StringBuffer();
  91.         sb.append("H = ").append(H).append('\n');
  92.         sb.append("W = ").append(W).append('\n');
  93.         sb.append("C = ").append(C).append('\n');
  94.         if (seed < 3)
  95.             for (int i = 0; i < N; ++i)
  96.                 sb.append(lightsArg[i]).append((i+1) % W > 0 ? ' ' : '\n');
  97.         return sb.toString();
  98.       }
  99.       catch (Exception e) {
  100.         addFatalError("An exception occurred while generating test case.");
  101.         e.printStackTrace();
  102.         return "";
  103.       }
  104.     }
  105.     // ---------------------------------------------------
  106.     public double runTest(String seed) {
  107.       try {
  108.         String test = generate(seed);
  109.         if (debug)
  110.             System.out.println(test);
  111.  
  112.         // call user's solution and get return
  113.         lightsRet = new int[N];
  114.         boolean showOutput = true;
  115.         if (showOutput) {
  116.             try {
  117.                 if (exec != null) {
  118.                     lightsRet = create(H, W, lightsArg);
  119.                 } else {
  120.                     GarlandOfLights garlandOfLights = new GarlandOfLights();
  121.                     lightsRet = garlandOfLights.create(H, W, lightsArg);
  122.                 }
  123.             } catch (Exception e) {
  124.                 addFatalError("Failed to get result from create.");
  125.                 return 0;
  126.             }
  127.  
  128.             if (lightsRet.length != N) {
  129.                 addFatalError("Your return must contain " + N + " elements, but it contained " + lightsRet.length + ".");
  130.                 return 0;
  131.             }
  132.  
  133.             // check that this is a valid permutation
  134.             boolean[] usedP = new boolean[N];
  135.             for (int i = 0; i < N; ++i) {
  136.                 if (lightsRet[i] < 0 || lightsRet[i] >= N) {
  137.                     addFatalError("All elements of your return must be between 0 and " + (N-1) + ", and your return contained " + lightsRet[i] + ".");
  138.                     return 0;
  139.                 }
  140.                 if (usedP[lightsRet[i]]) {
  141.                     addFatalError("All elements of your return must be unique, and your return contained " + lightsRet[i] + " twice.");
  142.                     return 0;
  143.                 }
  144.                 usedP[lightsRet[i]] = true;
  145.             }
  146.         }
  147.         else {
  148.             // use the starting layout
  149.             for (int i = 0; i < N; ++i)
  150.                 lightsRet[i] = i;
  151.         }
  152.  
  153.         if (debug) {
  154.             StringBuffer sb = new StringBuffer();
  155.             for (int i = 0; i < N; ++i)
  156.                 sb.append(lightsArg[lightsRet[i]]).append((i+1) % W > 0 ? ' ' : '\n');
  157.             System.out.println("Return grid:");
  158.             System.out.println(sb.toString());
  159.         }
  160.  
  161.         // find the longest valid loop of garland tiles
  162.         if (vis) {
  163.             longestLoop = new boolean[N];
  164.         }
  165.         int maxLen = 0;
  166.         boolean[] used = new boolean[N];
  167.         boolean[] curLoop = new boolean[N];
  168.         // iterate through positions in the grid in row-wise order
  169.         for (int start = 0; start < N; ++start) {
  170.             if (used[start])
  171.                 continue;
  172.             boolean goodLoop = true, goodColors = true;
  173.             int len = 0;
  174.             int startR = start / W;
  175.             int startC = start % W;
  176.             Arrays.fill(curLoop, false);
  177.             curLoop[start] = true;
  178.             // track the garland starting at this tile
  179.             StringBuffer sb = new StringBuffer();
  180.             int startLight = lightsRet[start];
  181.             int startType = lightTypes[startLight];
  182.             // go in one direction at a time (clockwise first) unless it's a loop
  183.             for (int d = 1; d >= 0; d--) {
  184.                 int r = startR, c = startC;
  185.                 if (d == 1)
  186.                     sb.append("(" + r + "," + c + ")");
  187.                 int curColor = lightColors[startLight];
  188.                 int curDir = typeDirs[startType][d];
  189.                 while (true) {
  190.                     // move in the direction diven by curDir
  191.                     int nextR = r + dr[curDir];
  192.                     int nextC = c + dc[curDir];
  193.                     int nextCell = nextR * W + nextC;
  194.                     if (nextR < 0 || nextR == H || nextC < 0 || nextC == W || used[nextCell]) {
  195.                         // the direction leads outside the border or to a previously used cell - not a loop
  196.                         goodLoop = false;
  197.                         break;
  198.                     }
  199.                     int nextLight = lightsRet[nextCell];
  200.                     int nextType = lightTypes[nextLight];
  201.  
  202.                     // check whether next tile is connected to previous one
  203.                     int nextDir = -1;
  204.                     if (typeDirs[nextType][0] == (curDir ^ 1))
  205.                         nextDir = typeDirs[nextType][1];
  206.                     else if (typeDirs[nextType][1] == (curDir ^ 1))
  207.                         nextDir = typeDirs[nextType][0];
  208.                     else {
  209.                         // next tile is not connected to the previous one - not a loop
  210.                         goodLoop = false;
  211.                         break;
  212.                     }
  213.  
  214.                     // next tile is connected to the previous one - can continue
  215.                     // mark next tile as part of the loop
  216.                     len++;
  217.                     used[nextCell] = true;
  218.                     curLoop[nextCell] = true;
  219.                     sb.append(", (" + nextR + "," + nextC + ")");
  220.  
  221.                     // check the colors
  222.                     if (curColor == lightColors[nextLight]) {
  223.                         // two of the same color in row - mark as bad but continue along the loop
  224.                         goodColors = false;
  225.                     }
  226.                     if (nextR == startR && nextC == startC)
  227.                         break;
  228.  
  229.                     // next is now current
  230.                     r = nextR;
  231.                     c = nextC;
  232.                     curColor = lightColors[nextLight];
  233.                     curDir = nextDir;
  234.                 }
  235.                
  236.                 if (goodLoop)
  237.                     break;
  238.             }
  239.  
  240.             if (debug && (chains || goodLoop)) {
  241.                 System.out.print(goodLoop && goodColors ? "Good loop" : (goodLoop ? "Bad loop" : "Chain"));
  242.                 System.out.println(" of length " + (goodLoop ? len : len+1) + ": " + sb.toString());
  243.             }
  244.             if (goodLoop && goodColors) {
  245.                 // we returned to the starting tile with all connected tiles and alternating colors
  246.                 if (len > maxLen) {
  247.                     maxLen = len;
  248.                     if (vis) {
  249.                         longestLoop = Arrays.copyOf(curLoop, N);
  250.                     }
  251.                 }
  252.             }
  253.         }
  254.  
  255.         if (vis) {
  256.             // draw the image
  257.             jf.setSize(SZX+10,SZY+30);
  258.             jf.setVisible(true);
  259.             draw();
  260.         }
  261.         return maxLen * 1.0 / N;
  262.       }
  263.       catch (Exception e) {
  264.         addFatalError("An exception occurred while trying to process your program's results.");
  265.         e.printStackTrace();
  266.         return -1;
  267.       }
  268.     }
  269. // ------------- visualization part ----------------------
  270.     static String exec, fileName;
  271.     static boolean vis, debug, save, chains;
  272.     static Process proc;
  273.     JFrame jf;
  274.     Vis v;
  275.     InputStream is;
  276.     OutputStream os;
  277.     BufferedReader br;
  278.     // problem-specific drawing params
  279.     int SZX, SZY;
  280.     static int SZ;
  281.     // ---------------------------------------------------
  282.     int[] create(int H, int W, String[] lights) throws IOException {
  283.         // pass the params to the solution and get the return
  284.         int i;
  285.         StringBuffer sb = new StringBuffer();
  286.         sb.append(H).append('\n');
  287.         sb.append(W).append('\n');
  288.         for (i = 0; i < H*W; ++i)
  289.             sb.append(lights[i]).append('\n');
  290.         os.write(sb.toString().getBytes());
  291.         os.flush();
  292.  
  293.         // get the return - an array of integers
  294.         int nret = Integer.parseInt(br.readLine());
  295.         int[] ret = new int[nret];
  296.         for (i = 0; i < nret; ++i)
  297.             ret[i] = Integer.parseInt(br.readLine());
  298.         return ret;
  299.     }
  300.     // ---------------------------------------------------
  301.     void draw() {
  302.         if (!vis) return;
  303.         v.repaint();
  304.     }
  305.     // ---------------------------------------------------
  306.     int[] colors = {0xE43BA6, 0x00BCF2, 0xFCE100, 0x7CD300};
  307.     // ---------------------------------------------------
  308.     @SuppressWarnings("serial")
  309.     public class Vis extends JPanel implements WindowListener {
  310.         public void paint(Graphics g) {
  311.           try {
  312.             // do painting here
  313.             BufferedImage bi = new BufferedImage(SZX+5,SZY+5,BufferedImage.TYPE_INT_RGB);
  314.             Graphics2D g2 = (Graphics2D)bi.getGraphics();
  315.             // background
  316.             g2.setColor(new Color(0xE3E3E3));
  317.             g2.fillRect(0,0,SZX+10,SZY+10);
  318. //            FontMetrics fm = g2.getFontMetrics();
  319.  
  320.             // white background for cells which are part of the longest loop
  321.             g2.setColor(Color.WHITE);
  322.             for (int r = 0; r < H; ++r)
  323.             for (int c = 0; c < W; ++c) {
  324.                 if (longestLoop[r * W + c])
  325.                     g2.fillRect(c * SZ, r * SZ, SZ, SZ);
  326.             }
  327.  
  328.             // lines between cells
  329.             g2.setColor(new Color(0xAAAAAA));
  330.             for (int i = 0; i <= H; i++)
  331.                 g2.drawLine(0, i*SZ, W*SZ, i*SZ);
  332.             for (int i = 0; i <= W; i++)
  333.                 g2.drawLine(i*SZ, 0, i*SZ, H*SZ);
  334.  
  335.             // wires on tiles
  336.             g2.setColor(Color.BLACK);
  337.             int d = 0;
  338.             if (SZ > 12) {
  339.                 g2.setStroke(new BasicStroke(3.0f));
  340.                 d = 1;
  341.             }
  342.             for (int r = 0; r < H; ++r)
  343.             for (int c = 0; c < W; ++c) {
  344.                 int type = lightTypes[lightsRet[r * W + c]];
  345.                 for (int k = 0; k < 2; ++k) {
  346.                     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));
  347.                 }
  348.             }
  349.  
  350.             for (int r = 0; r < H; ++r)
  351.             for (int c = 0; c < W; ++c) {
  352.                 int color = lightColors[lightsRet[r * W + c]] - 'a';
  353.                 g2.setColor(new Color(colors[color]));
  354.                 g2.fillOval(c * SZ + SZ/2 - SZ/4, r * SZ + SZ/2 - SZ/4, SZ/2, SZ/2);
  355.             }
  356.  
  357.             g.drawImage(bi,0,0,SZX+5,SZY+5,null);
  358.             if (save) {
  359.                 ImageIO.write(bi,"png", new File(fileName +".png"));
  360.             }
  361.       }
  362.       catch (Exception e) { e.printStackTrace(); }
  363.         }
  364.         public Vis() {
  365.             jf.addWindowListener(this);
  366.         }
  367.         // WindowListener
  368.         public void windowClosing(WindowEvent e) {
  369.             if(proc != null)
  370.                 try { proc.destroy(); }
  371.                 catch (Exception ex) { ex.printStackTrace(); }
  372.             System.exit(0);
  373.         }
  374.         public void windowActivated(WindowEvent e) { }
  375.         public void windowDeactivated(WindowEvent e) { }
  376.         public void windowOpened(WindowEvent e) { }
  377.         public void windowClosed(WindowEvent e) { }
  378.         public void windowIconified(WindowEvent e) { }
  379.         public void windowDeiconified(WindowEvent e) { }
  380.     }
  381.     // ---------------------------------------------------
  382.     public GarlandOfLightsVis(long seed) {
  383.         this("" + seed);
  384.     }
  385.    
  386.     double score;
  387.    
  388.     public GarlandOfLightsVis(String seed) {
  389.         //interface for runTest
  390.         if (vis)
  391.         {   jf = new JFrame();
  392.             v = new Vis();
  393.             jf.getContentPane().add(v);
  394.         }
  395.         if (exec != null) {
  396.             try {
  397.                 Runtime rt = Runtime.getRuntime();
  398.                 proc = rt.exec(exec);
  399.                 os = proc.getOutputStream();
  400.                 is = proc.getInputStream();
  401.                 br = new BufferedReader(new InputStreamReader(is));
  402.                 new ErrorReader(proc.getErrorStream()).start();
  403.             } catch (Exception e) {
  404.                 e.printStackTrace();
  405.             }
  406.         }
  407.         score = runTest(seed);
  408.         if (debug) {
  409.             System.out.println("Score = "+score);
  410.         }
  411.         if (proc != null)
  412.             try { proc.destroy(); }
  413.             catch (Exception e) { e.printStackTrace(); }
  414.     }
  415.     // ---------------------------------------------------
  416.     public static void main(String[] args) {
  417.         String seed = "1";
  418.         SZ = 12;
  419.         for (int i = 0; i<args.length; i++)
  420.         {   if (args[i].equals("-seed"))
  421.                 seed = args[++i];
  422.             if (args[i].equals("-exec"))
  423.                 exec = args[++i];
  424.             if (args[i].equals("-vis"))
  425.                 vis = true;
  426.             if (args[i].equals("-debug"))
  427.                 debug = true;
  428.             if (args[i].equals("-size"))
  429.                 SZ = Integer.parseInt(args[++i]);
  430.             if (args[i].equals("-save"))
  431.                 save = true;
  432.             if (args[i].equals("-chains"))
  433.                 chains = true;
  434.         }
  435.         if ((seed.equals("1") || seed.equals("2")) && SZ < 30)
  436.             SZ = 30;
  437.         if (chains)
  438.             debug = true;
  439.         if (save) {
  440.             fileName = seed;
  441.             vis = true;
  442.         }
  443.        
  444.         // Visualize
  445.         boolean doVisualize = true;
  446.         if (doVisualize) {
  447.             vis = true;
  448.             GarlandOfLightsVis gv = new GarlandOfLightsVis(1);
  449.             System.out.println(gv.score);
  450.         }
  451.        
  452.         // Calculate score
  453.         boolean doCalculateScore = true;
  454.         if (doCalculateScore) {
  455.             vis = false;
  456.             double sum = 0;
  457.             int num = 0;
  458.             for (int i = 1; i <= 10; i++) {
  459.                 double score = new GarlandOfLightsVis(i).score;
  460.                 System.out.println(i + ": " + score);
  461.                 sum += score;
  462.                 num += 1;
  463.             }
  464.             System.out.println("Average score: " + sum / num);
  465.         }
  466.     }
  467.     // ---------------------------------------------------
  468.     void addFatalError(String message) {
  469.         System.out.println(message);
  470.     }
  471. }
  472.  
  473. class ErrorReader extends Thread{
  474.     InputStream error;
  475.     public ErrorReader(InputStream is) {
  476.         error = is;
  477.     }
  478.     public void run() {
  479.         try {
  480.             byte[] ch = new byte[50000];
  481.             int read;
  482.             while ((read = error.read(ch)) > 0)
  483.             {   String s = new String(ch,0,read);
  484.                 System.out.print(s);
  485.                 System.out.flush();
  486.             }
  487.         } catch(Exception e) { }
  488.     }
  489. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement