Guest User

COTO Stabilizer Java Code

a guest
Oct 11th, 2014
211
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.File;
  3. import java.io.FileReader;
  4. import java.io.IOException;
  5. import java.util.*;
  6. import java.util.stream.Stream;
  7.  
  8. public final class Bricks {
  9.     static final boolean IS_DEBUG = false;
  10.  
  11.     static final String BRICKS_FILE = "bricks.txt";
  12.  
  13.     public static void main( String[] sArgs ) {
  14.         SortedSet<Brick> S_Bks,
  15.             S_Bks1 = loadBricks( new File( BRICKS_FILE ), PillarPreference.LEFT ),
  16.             S_Bks2 = loadBricks( new File( BRICKS_FILE ), PillarPreference.RIGHT  ),
  17.             S_Bks3 = loadBricks( new File( BRICKS_FILE ), PillarPreference.STRAIGHT );
  18.  
  19.         int iScore,
  20.             iScore1 = runOnce( S_Bks1 ),
  21.             iScore2 = runOnce( S_Bks2 ),
  22.             iScore3 = runOnce( S_Bks3 );
  23.  
  24.         if( iScore1 <= iScore2 && iScore1 <= iScore3 ) {
  25.             S_Bks = S_Bks1;
  26.             iScore = iScore1;
  27.         } else if( iScore2 <= iScore3 ) {
  28.             S_Bks = S_Bks2;
  29.             iScore = iScore2;
  30.         } else {
  31.             S_Bks = S_Bks3;
  32.             iScore = iScore3;
  33.         }
  34.  
  35.         System.out.println( "Best solution requires " + iScore + " block(s).\n\n" );
  36.         dumpBricks( S_Bks );
  37.     }
  38.  
  39.     private static int runOnce( SortedSet<Brick> S_Bks ) {
  40.         if( IS_DEBUG ) {
  41.             System.out.println( "Initial configuration for " + S_Bks.first().BkC.PPr.name() +
  42.                 " pillar preference:\n" );
  43.  
  44.             dumpBricks( S_Bks );
  45.         }
  46.  
  47.         int nInit = nonemptyBrickCount( S_Bks );
  48.  
  49.         Stream<Brick> SmBksProc = S_Bks.stream().filter( Brick::isNonempty );
  50.         while( true ) {
  51.             SortedSet<Brick> S_BksMod = new TreeSet<>();
  52.  
  53.             SmBksProc.forEach( Bk -> S_BksMod.addAll( Bk.stabilize() ) );
  54.             if( IS_DEBUG ) {
  55.                 System.out.println( "Stabilization step yielded " + S_BksMod.size() + " new brick(s).\n" );
  56.                 dumpBricks( S_Bks );
  57.             }
  58.  
  59.             if( S_BksMod.isEmpty() )
  60.                 break;
  61.  
  62.             SmBksProc = S_BksMod.stream();
  63.         }
  64.  
  65.         while( true ) {
  66.             int iMod = S_Bks.stream().filter( Brick::isAdded ).mapToInt( Brick::jenga ).sum();
  67.  
  68.             if( IS_DEBUG ) {
  69.                 System.out.println( "Jenga step removed " + iMod + " brick(s).\n" );
  70.                 dumpBricks( S_Bks );
  71.             }
  72.  
  73.             if( iMod == 0 )
  74.                 break;
  75.         }
  76.  
  77.         int nFinal = nonemptyBrickCount( S_Bks );
  78.         return nFinal - nInit;
  79.     }
  80.  
  81.  
  82.     static SortedSet<Brick> loadBricks( File F, PillarPreference PPr ) {
  83.         List<char[]> chsAs = new LinkedList<>(),
  84.             chsBs = new LinkedList<>();
  85.  
  86.         boolean isA = true;
  87.         int nCharsPerTier = 0;
  88.         try( BufferedReader BR = new BufferedReader( new FileReader( F ) ) ) {
  89.             while( BR.ready() ) {
  90.                 String s = BR.readLine();
  91.  
  92.                 if( s.isEmpty() ) {
  93.                     BR.close();
  94.                     return new TreeSet<>();
  95.                 }
  96.  
  97.                 char[] chs = s.toCharArray();
  98.                 if( chsAs.isEmpty() ) {
  99.                     char[] chsBlank = new char[chs.length];
  100.  
  101.                     nCharsPerTier = chs.length;
  102.                     Arrays.fill( chsBlank, '.' );
  103.                     chsAs.add( chsBlank );
  104.                     isA = false;
  105.                 }
  106.                 if( isA )
  107.                     chsAs.add( chs );
  108.                 else chsBs.add( chs );
  109.  
  110.                 isA = !isA;
  111.             }
  112.             BR.close();
  113.         } catch( IOException ioe ) {
  114.             System.err.println( "Unable to read contents of bricks file: " + F );
  115.             System.exit( 1 );
  116.         }
  117.  
  118.         final boolean isWideA = chsAs.parallelStream().anyMatch( chs -> {
  119.             for( int i = 0; i < chs.length; i += 4 )
  120.                 if( chs[i] == '[' )
  121.                     return true;
  122.  
  123.             return false;
  124.         } );
  125.  
  126.         SortedSet<Brick> S_Bks = new TreeSet<>();
  127.         int nTiers = chsAs.size() + chsBs.size();
  128.         Brick[][] Bks = new Brick[nTiers][];
  129.         BrickContext BkC = new BrickContext( nTiers, nCharsPerTier, isWideA, PPr );
  130.  
  131.         brickify( chsAs, Bks, S_Bks, 0, BkC );
  132.         brickify( chsBs, Bks, S_Bks, 1, BkC );
  133.  
  134.         for( Brick Bk : S_Bks )
  135.             Bk.initFrom( Bks );
  136.  
  137.         return S_Bks;
  138.     }
  139.  
  140.     private static void brickify( List<char[]> chss, Brick[][] Bks, Set<Brick> S_Bks, int iTier0, BrickContext BkC ) {
  141.         int iTier = iTier0;
  142.         for( char[] chs : chss ) {
  143.             int nBrk, i0;
  144.             if( BkC.isWide( iTier ) ) {
  145.                 nBrk = chs.length/4;
  146.                 i0 = 0;
  147.             } else {
  148.                 nBrk = chs.length/4 - 1;
  149.                 i0 = 2;
  150.             }
  151.             Brick[] BksTier = new Brick[nBrk];
  152.             for( int i = i0, iOrd = 0; i < chs.length - 2; i += 4, iOrd++ ) {
  153.                 Brick Bk = new Brick( iTier, iOrd, chs[i] == '[' ? Type.FIXED : Type.EMPTY, BkC );
  154.  
  155.                 BksTier[iOrd] = Bk;
  156.                 S_Bks.add( Bk );
  157.             }
  158.  
  159.             Bks[iTier] = BksTier;
  160.             iTier += 2;
  161.         }
  162.     }
  163.  
  164.     static void dumpBricks( SortedSet<Brick> S_Bks ) {
  165.         BrickContext BkC = S_Bks.first().BkC;
  166.         char[] chsOut = new char[BkC.nTiers*(1 + BkC.nCharsPerTier)];
  167.  
  168.         Arrays.fill( chsOut, '.' );
  169.         for( int i = BkC.nCharsPerTier; i < chsOut.length; i += BkC.nCharsPerTier + 1 )
  170.             chsOut[i] = '\n';
  171.  
  172.         S_Bks.stream().filter( Brick::isNonempty ).forEach(
  173.             Bk -> System.arraycopy( Bk.Ty.chsGfx, 0, chsOut, Bk.iOrd*4 + (1 + BkC.nCharsPerTier)*Bk.iTier +
  174.                 (BkC.isWide( Bk.iTier ) ? 0 : 2), 4 ) );
  175.  
  176.         System.out.print( new String( chsOut ) );
  177.     }
  178.  
  179.     static int nonemptyBrickCount( Set<Brick> S_Bks ) {
  180.         return (int)S_Bks.parallelStream().filter( Brick::isNonempty ).count();
  181.     }
  182.  
  183.     static final class Brick implements Comparable<Brick> {
  184.         final int iTier;
  185.         final int iOrd;
  186.         final BrickContext BkC;
  187.  
  188.         Brick BkTL;
  189.         Brick BkTR;
  190.         Brick BkBL;
  191.         Brick BkBR;
  192.  
  193.         Type Ty;
  194.  
  195.         Brick( int iTier, int iOrd, Type Ty, BrickContext BkC ) {
  196.             this.iTier = iTier;
  197.             this.iOrd = iOrd;
  198.             this.Ty = Ty;
  199.             this.BkC = BkC;
  200.         }
  201.  
  202.         void initFrom( Brick[][] Bks ) {
  203.             boolean isWide = BkC.isWide( iTier );
  204.  
  205.             if( iTier != 0 && (!isWide || iOrd != 0) )
  206.                 BkTL = Bks[iTier - 1][iOrd - (isWide ? 1 : 0)];
  207.             if( iTier != 0 && (!isWide || iOrd != Bks[iTier].length-1) )
  208.                 BkTR = Bks[iTier - 1][iOrd + (isWide ? 0 : 1)];
  209.             if( iTier != Bks.length-1 && (!isWide || iOrd != 0) )
  210.                 BkBL = Bks[iTier + 1][iOrd - (isWide ? 1 : 0)];
  211.             if( iTier != Bks.length-1 && (!isWide || iOrd != Bks[iTier].length-1) )
  212.                 BkBR = Bks[iTier + 1][iOrd + (isWide ? 0 : 1)];
  213.         }
  214.  
  215.         boolean isStable() {
  216.             if( isOnBottom() )
  217.                 return true;
  218.  
  219.             boolean isR = isFlushRight(),
  220.                 isL = isFlushLeft(),
  221.                 isT = isOnTop();
  222.  
  223.             return !isR && !isL && BkBR.isNonempty() && BkBL.isNonempty() ||
  224.                 !isR && !isT && BkBR.isNonempty() && BkTR.isNonempty() ||
  225.                 !isL && !isT && BkBL.isNonempty() && BkTL.isNonempty();
  226.         }
  227.  
  228.         Set<Brick> stabilize() {
  229.             if( isStable() )
  230.                 return Collections.emptySet();
  231.  
  232.             SortedSet<Brick> S = new TreeSet<>();
  233.             if( isFlushRight() ) {
  234.                 if( !BkBL.isNonempty() ) {
  235.                     BkBL.Ty = Type.ADDED;
  236.                     S.add( BkBL );
  237.                 }
  238.                 if( !BkTL.isNonempty() ) {
  239.                     BkTL.Ty = Type.ADDED;
  240.                     S.add( BkTL );
  241.                 }
  242.             } else if( isFlushLeft() ) {
  243.                 if( !BkBR.isNonempty() ) {
  244.                     BkBR.Ty = Type.ADDED;
  245.                     S.add( BkBR );
  246.                 }
  247.                 if( !BkTR.isNonempty() ) {
  248.                     BkTR.Ty = Type.ADDED;
  249.                     S.add( BkTR );
  250.                 }
  251.             } else {
  252.                 if( !BkBL.isNonempty() ) {
  253.                     BkBL.Ty = Type.ADDED;
  254.                     S.add( BkBL );
  255.                 }
  256.                 if( !BkBR.isNonempty() ) {
  257.                     BkBR.Ty = Type.ADDED;
  258.                     S.add( BkBR );
  259.                 }
  260.             }
  261.             return S;
  262.         }
  263.  
  264.         boolean registerFundamentalDependencies( Set<Brick> S_DepsIn ) {
  265.             S_DepsIn.add( this );
  266.             Ty = Type.EMPTY;
  267.  
  268.             if( addDependenciesFor( S_DepsIn, BkBL ) ) {
  269.                 Ty = Type.ADDED;
  270.                 return true;
  271.             }
  272.             if( addDependenciesFor( S_DepsIn, BkBR ) ) {
  273.                 Ty = Type.ADDED;
  274.                 return true;
  275.             }
  276.             if( addDependenciesFor( S_DepsIn, BkTL ) ) {
  277.                 Ty = Type.ADDED;
  278.                 return true;
  279.             }
  280.             if( addDependenciesFor( S_DepsIn, BkTR ) ) {
  281.                 Ty = Type.ADDED;
  282.                 return true;
  283.             }
  284.  
  285.             Ty = Type.ADDED;
  286.             return false;
  287.         }
  288.  
  289.         private static boolean addDependenciesFor( Set<Brick> S_DepsIn, Brick Bk ) {
  290.             return Bk != null &&
  291.                  Bk.isNonempty() &&
  292.                 !S_DepsIn.contains( Bk ) &&
  293.                 !Bk.isStable() &&
  294.                 (!Bk.isAdded() || Bk.registerFundamentalDependencies( S_DepsIn ));
  295.         }
  296.  
  297.         int jenga() {
  298.             if( !isAdded() )
  299.                 return 0;
  300.  
  301.             Set<Brick> S = new TreeSet<>();
  302.  
  303.             boolean isMod = !registerFundamentalDependencies( S );
  304.             if( isMod )
  305.                 S.stream().forEach( Bk -> Bk.Ty = Type.EMPTY );
  306.  
  307.             return isMod ? S.size() : 0;
  308.         }
  309.  
  310.         boolean isNonempty() {
  311.             return Ty != Type.EMPTY;
  312.         }
  313.  
  314.         boolean isAdded() {
  315.             return Ty == Type.ADDED;
  316.         }
  317.  
  318.         boolean isOnBottom() {
  319.             return BkBL == null && BkBR == null;
  320.         }
  321.  
  322.         boolean isOnTop() {
  323.             return BkTL == null && BkTR == null;
  324.         }
  325.  
  326.         boolean isFlushRight() {
  327.             return BkTR == null && BkBR == null;
  328.         }
  329.  
  330.         boolean isFlushLeft() {
  331.             return BkTL == null && BkBL == null;
  332.         }
  333.  
  334.         @Override public int compareTo( Brick Bk ) {
  335.             int iOrdSign = BkC.PPr == PillarPreference.RIGHT ? -1 :
  336.                 (BkC.PPr == PillarPreference.LEFT ? 1 : (BkC.isWide( iTier ) ? 1 : -1) );
  337.  
  338.             return iTier < Bk.iTier ? -1 : (iTier > Bk.iTier ? 1 :
  339.                 (iOrd < Bk.iOrd ? -1 : (iOrd > Bk.iOrd ? 1 : 0))*iOrdSign);
  340.         }
  341.  
  342.         public boolean equals( Object o ) {
  343.             if( !(o instanceof Brick) )
  344.                 return false;
  345.  
  346.             Brick Bk = (Brick)o;
  347.             return Bk.iTier == iTier && Bk.iOrd == iOrd;
  348.         }
  349.  
  350.         public int hashCode() {
  351.             return iTier*13189 + iOrd;
  352.         }
  353.     }
  354.  
  355.     static final class BrickContext {
  356.         final int nTiers;
  357.         final int nCharsPerTier;
  358.         final boolean isTier0Wide;
  359.         final PillarPreference PPr;
  360.  
  361.         BrickContext( int nTiers, int nCharsPerTier, boolean isTier0Wide, PillarPreference PPr ) {
  362.             this.nTiers = nTiers;
  363.             this.nCharsPerTier = nCharsPerTier;
  364.             this.isTier0Wide = isTier0Wide;
  365.             this.PPr = PPr;
  366.         }
  367.  
  368.         boolean isWide( int iTier ) {
  369.             return ((iTier &1) == 0) == isTier0Wide;
  370.         }
  371.     }
  372.  
  373.     enum Type {
  374.         FIXED( "[XX]" ),
  375.         ADDED( "[  ]" ),
  376.         EMPTY( "...." );
  377.  
  378.         final char[] chsGfx;
  379.  
  380.         Type( String sGfx ) {
  381.             chsGfx = sGfx.toCharArray();
  382.         }
  383.     }
  384.  
  385.     enum PillarPreference {
  386.         RIGHT,
  387.         LEFT,
  388.         STRAIGHT
  389.     }
  390. }
RAW Paste Data