API tools faq
paste
Advertisement
Guest User

COTO Water Puzzle Solver

a guest
Dec 16th, 2014
620
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 8.54 KB | None | 0 0
raw download clone embed print report
  1. import java.util.*;
  2.  
  3. public final class Water {
  4.     static final int[] ROW_FILLS = { 4, 5, 6, 5, 6, 4, 7, 7, 4, 5, 7, 6 };
  5.     static final int[] COL_FILLS = { 4, 6, 5, 4, 8, 7, 4, 4, 6, 6, 6, 6 };
  6.  
  7.     static final Piece[] Pcs = {
  8.         new Piece( new Row[] { // 1
  9.             new Row( 3, new int[] { 2, 3 } ), new Row( 2, new int[] { 2 } ), new Row( 1, new int[] { 1, 2, 3 } )
  10.         } ),
  11.         new Piece( new Row[] { // 2
  12.             new Row( 2, new int[] { 3, 4, 5 } ), new Row( 1, new int[] { 4 } )
  13.         } ),
  14.         new Piece( new Row[] { // 3
  15.             new Row( 3, new int[] { 5, 6 } ), new Row( 2, new int[] { 6 } ), new Row( 1, new int[] { 5, 6 } )
  16.         } ),
  17.         new Piece( new Row[] { // 4
  18.             new Row( 1, new int[] { 7, 8, 9, 10} )
  19.         } ),
  20.         new Piece( new Row[] { // 5
  21.             new Row( 3, new int[] { 10 } ), new Row( 2, new int[] { 9, 10, 11 } ), new Row( 1, new int[] { 11, 12 } )
  22.         } ),
  23.         new Piece( new Row[] { // 6
  24.             new Row( 3, new int[] { 1 } ), new Row( 2, new int[] { 1 } )
  25.         }, 1 ),
  26.         new Piece( new Row[] { // 7
  27.             new Row( 4, new int[] { 6, 7 } ), new Row( 3, new int[] { 7 } ), new Row( 2, new int[] { 7, 8 } )
  28.         } ),
  29.         new Piece( new Row[] { // 8
  30.             new Row( 5, new int[] { 12 } ), new Row( 4, new int[] { 12 } ), new Row( 3, new int[] { 11, 12 } ),
  31.             new Row( 2, new int[] { 12 } )
  32.         } ),
  33.         new Piece( new Row[] { // 9
  34.             new Row( 5, new int[] { 1, 3 } ), new Row( 4, new int[] { 1, 2, 3, 4 } ), new Row( 3, new int[] { 4 } )
  35.         }, 2 ),
  36.         new Piece( new Row[] { // 10
  37.             new Row( 4, new int[] { 9, 10, 11 } ), new Row( 3, new int[] { 8, 9 } )
  38.         } ),
  39.         new Piece( new Row[] { // 11
  40.             new Row( 6, new int[] { 5 } ), new Row( 5, new int[] { 4, 5, 6, 7 } ), new Row( 4, new int[] { 5 } )
  41.         }, 3 ),
  42.         new Piece( new Row[] { // 12
  43.             new Row( 6 , new int[] { 9, 10 } ), new Row( 5, new int[] { 8, 9 } ), new Row( 4, new int[] { 8 } )
  44.         } ),
  45.         new Piece( new Row[] { // 13
  46.             new Row( 7, new int[] { 1 } ), new Row( 6, new int[] { 1, 2, 3, 4 } ), new Row( 5, new int[] { 2 } )
  47.         }, 4 ),
  48.         new Piece( new Row[] { // 14
  49.             new Row( 8, new int[] { 11 } ), new Row( 7, new int[] { 10, 11 } ), new Row( 6, new int[] { 11 } ),
  50.             new Row( 5, new int[] { 10, 11 } )
  51.         } ),
  52.         new Piece( new Row[] { // 15
  53.             new Row( 8, new int[] { 4 } ), new Row( 7, new int[] { 4, 5, 6 } ), new Row( 6, new int[] { 6 } )
  54.         }, 5 ),
  55.         new Piece( new Row[] { // 16
  56.             new Row( 9, new int[] { 8 } ), new Row( 8, new int[] { 6, 7, 8 } ), new Row( 7, new int[] { 7 } ),
  57.             new Row( 6, new int[] { 7, 8 } )
  58.         } ),
  59.         new Piece( new Row[] { // 17
  60.             new Row( 8 , new int[] { 12 } ), new Row( 7, new int[] { 12 } ), new Row( 6, new int[] { 12 } )
  61.         } ),
  62.         new Piece( new Row[] { // 18
  63.             new Row( 10, new int[] { 1, 2 } ), new Row( 9, new int[] { 2 } ), new Row( 8, new int[] { 2 } ),
  64.             new Row( 7, new int[] { 2, 3 } )
  65.         }, 6 ),
  66.         new Piece( new Row[] { // 19
  67.             new Row( 8, new int[] { 9, 10 } ), new Row( 7, new int[] { 8, 9 } )
  68.         } ),
  69.         new Piece( new Row[] { // 20
  70.             new Row( 9, new int[] { 1 } ), new Row( 8, new int[] { 1 } )
  71.         }, 7 ),
  72.         new Piece( new Row[] { // 21
  73.             new Row( 9, new int[] { 3, 4, 5 } ), new Row( 8, new int[] { 3, 5 } )
  74.         } ),
  75.         new Piece( new Row[] { // 22
  76.             new Row( 11, new int[] { 5, 6, 7 } ), new Row( 10, new int[] { 6 } ), new Row( 9, new int[] { 6 } )
  77.         }, 8 ),
  78.         new Piece( new Row[] { // 23
  79.             new Row( 12, new int[] { 8 } ), new Row( 11, new int[] { 8 } ), new Row( 10, new int[] { 7, 8 } ),
  80.             new Row( 9, new int[] { 7 } )
  81.         } ),
  82.         new Piece( new Row[] { // 24
  83.             new Row( 11, new int[] { 9 } ), new Row( 10, new int[] { 9, 10 } ), new Row( 9, new int[] { 9 } )
  84.         } ),
  85.         new Piece( new Row[] { // 25
  86.             new Row( 11, new int[] { 12 } ), new Row( 10, new int[] { 12 } ), new Row( 9, new int[] { 10, 11, 12 } )
  87.         } ),
  88.         new Piece( new Row[] { // 26
  89.             new Row( 11, new int[] { 2, 3 } ), new Row( 10, new int[] { 3, 4, 5 } )
  90.         }, 9 ),
  91.         new Piece( new Row[] { // 27
  92.             new Row( 12, new int[] { 11, 12 } ), new Row( 11, new int[] { 10, 11 } ), new Row( 10, new int[] { 11 } )
  93.         } ),
  94.         new Piece( new Row[] { // 28
  95.             new Row( 12, new int[] { 1, 2, 3 } ), new Row( 11, new int[] { 1 } )
  96.         }, 10 ),
  97.         new Piece( new Row[] { // 29
  98.             new Row( 12, new int[] { 4, 5, 6, 7 } ), new Row( 11, new int[] { 4 } )
  99.         } ),
  100.         new Piece( new Row[] { // 30
  101.             new Row( 12, new int[] { 9, 10 } )
  102.         }, 11 )
  103.     };
  104.  
  105.  
  106.     public static void main( String[] sArgs ) {
  107.         final int[] iRowSums = new int[12],
  108.             iColSums = new int[12];
  109.  
  110.         final Deque<StackElement> SEs = new LinkedList<>();
  111.  
  112.         SEs.push( new StackElement( 1 ) );
  113.  
  114.         pieceHeap: while( !SEs.isEmpty() ) {
  115.             StackElement SE = SEs.peek();
  116.  
  117.             if( !SE.isMutable() ) {
  118.                 SEs.pop();
  119.                 continue;
  120.             }
  121.             while( SE.isMutable() ) {
  122.                 boolean isOverfull = SE.fillToNextLevel( iRowSums, iColSums );
  123.                 if( !isOverfull ) {
  124.                     if( SE.iPieceIndex == 30 ) {
  125.                         if( iRowSums[11] == ROW_FILLS[11] )
  126.                             break pieceHeap;
  127.  
  128.                         continue;
  129.                     }
  130.  
  131.                     int iDeadRow = Pcs[SE.iPieceIndex + 1 - 1].iDeadRow;
  132.                     if( iDeadRow != -1 && iRowSums[iDeadRow - 1] < ROW_FILLS[iDeadRow - 1] )
  133.                         break;
  134.  
  135.                     SEs.push( new StackElement( SE.iPieceIndex + 1 ) );
  136.                     continue pieceHeap;
  137.                 }
  138.             }
  139.             SE.repeal( iRowSums, iColSums );
  140.             SEs.pop();
  141.         }
  142.         if( SEs.isEmpty() )
  143.             System.out.println( "Unable to find solution." );
  144.         else {
  145.             System.out.println( "Found solution:\n" );
  146.  
  147.             Iterator<StackElement> I_SE = SEs.descendingIterator();
  148.             while( I_SE.hasNext() )
  149.                 System.out.println( "\t" + I_SE.next().fillString() );
  150.         }
  151.     }
  152.  
  153.  
  154.     static class StackElement {
  155.         final int iPieceIndex;
  156.         final Piece Pc;
  157.         int iFillLevel;
  158.  
  159.         StackElement( int iPieceIndex ) {
  160.             this.iPieceIndex = iPieceIndex;
  161.             Pc = Pcs[iPieceIndex - 1];
  162.             iFillLevel = -1;
  163.         }
  164.  
  165.         boolean isMutable() {
  166.             return iFillLevel != 0;
  167.         }
  168.  
  169.         boolean fillToNextLevel( int[] iRowSums, int[] iColSums ) {
  170.             if( iPieceIndex == 9 ) {
  171.  
  172. /* Hack for piece 9, which doesn't obey the canonical fill rules (that I'd initially assumed). */
  173.  
  174.                 if( iFillLevel == -1 ) {
  175.                     iRowSums[2] += 1;
  176.                     iRowSums[3] += 4;
  177.                     iRowSums[4] += 2;
  178.                     iColSums[0] += 2;
  179.                     iColSums[1] += 1;
  180.                     iColSums[2] += 2;
  181.                     iColSums[3] += 2;
  182.                     iFillLevel = 5;
  183.                 } else if( iFillLevel == 5 ) {
  184.                     iRowSums[2] -= 1;
  185.                     iColSums[3] -= 1;
  186.                     iFillLevel = 4;
  187.                 } else if( iFillLevel == 4 ) {
  188.                     iRowSums[3] -= 4;
  189.                     iColSums[0] -= 1;
  190.                     iColSums[1] -= 1;
  191.                     iColSums[2] -= 1;
  192.                     iColSums[3] -= 1;
  193.                     iFillLevel = 3;
  194.                 } else if( iFillLevel == 3 ) {
  195.                     iRowSums[4] -= 1;
  196.                     iColSums[2] -= 1;
  197.                     iFillLevel = 2;
  198.                 } else if( iFillLevel == 2 ) {
  199.                     iColSums[2] += 1;
  200.                     iColSums[0] -= 1;
  201.                     iFillLevel = 1;
  202.                 } else if( iFillLevel == 1 ) {
  203.                     iColSums[2] -= 1;
  204.                     iRowSums[4] -= 1;
  205.                     iFillLevel = 0;
  206.                 }
  207.                 for( int iRow = 2; iRow <= 4; iRow++ )
  208.                     if( iRowSums[iRow] > ROW_FILLS[iRow] )
  209.                         return true;
  210.  
  211.                 for( int iCol = 0; iCol <= 3; iCol++ )
  212.                     if( iColSums[iCol] > COL_FILLS[iCol] )
  213.                         return true;
  214.  
  215.                 return false;
  216.             }
  217.  
  218.             if( iFillLevel == -1 ) {
  219.                 boolean isOverfull = false;
  220.  
  221.                 iFillLevel = Pc.Rws.length;
  222.                 for( Row Rw : Pc.Rws ) {
  223.                     iRowSums[Rw.iRow - 1] += Rw.iCols.length;
  224.                     if( iRowSums[Rw.iRow - 1] > ROW_FILLS[Rw.iRow - 1] )
  225.                         isOverfull = true;
  226.  
  227.                     for( int iCol : Rw.iCols )
  228.                         if( ++iColSums[iCol - 1] > COL_FILLS[iCol - 1] )
  229.                             isOverfull = true;
  230.                 }
  231.                 return isOverfull;
  232.             }
  233.             iFillLevel--;
  234.  
  235.             Row Rw = Pc.Rws[iFillLevel];
  236.  
  237.             iRowSums[Rw.iRow - 1] -= Rw.iCols.length;
  238.             for( int iCol : Rw.iCols )
  239.                 iColSums[iCol - 1]--;
  240.  
  241.             for( int iRow = 0; iRow < iFillLevel; iRow++ ) {
  242.                 Rw = Pc.Rws[iRow];
  243.                 if( iRowSums[Rw.iRow - 1] > ROW_FILLS[Rw.iRow - 1] )
  244.                     return true;
  245.  
  246.                 for( int iCol : Rw.iCols )
  247.                     if( iColSums[iCol - 1] > COL_FILLS[iCol - 1] )
  248.                         return true;
  249.             }
  250.             return false;
  251.         }
  252.  
  253.         void repeal( int[] iRowSums, int[] iColSums ) {
  254.             for( int iRow = 0; iRow < iFillLevel; iRow++ ) {
  255.                 Row Rw = Pc.Rws[iRow];
  256.  
  257.                 iRowSums[Rw.iRow - 1] -= Rw.iCols.length;
  258.                 for( int iCol : Rw.iCols )
  259.                     iColSums[iCol - 1]--;
  260.             }
  261.         }
  262.  
  263.         String fillString() {
  264.             return "Piece " + iPieceIndex + " filled to level " + iFillLevel + ".";
  265.         }
  266.     }
  267.  
  268.  
  269.     static class Piece {
  270.         final Row[] Rws;
  271.         final int iDeadRow;
  272.  
  273.         Piece( Row[] Rws ) {
  274.             this( Rws, -1 );
  275.         }
  276.  
  277.         Piece( Row[] Rws, int iDeadRow ) {
  278.             this.Rws = Rws;
  279.             this.iDeadRow = iDeadRow;
  280.         }
  281.     }
  282.  
  283.  
  284.     static class Row {
  285.         final int iRow;
  286.         final int[] iCols;
  287.  
  288.         Row( int iRow, int[] iCols ) {
  289.             this.iRow = iRow;
  290.             this.iCols = iCols;
  291.         }
  292.     }
  293. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!