COTO TetPack Java Code - Rev. 1

import java.util.*;

public final class TetPack
{
    static final boolean DEBUG = false;

    /* The following constant should be consistent with the pieces defined by the Piece enum. */

    static final int OMINO = 4;

    static final char CLEAR_CELL = ' ';
    static final char RESERVED_EMPTY_CELL = 'X';
    static final char PLACEHOLDER_CELL = '*';

    public static void main( String[] sArgs ) {
        final int iWidth,
            nPcs = sArgs.length - 1;

        final EnumMap<Piece,Integer> M_Pcs = new EnumMap<>( Piece.class );
        try {
            iWidth = Integer.parseInt( sArgs[0] );
            for( String s : Arrays.asList( sArgs ).subList( 1, sArgs.length ) ) {
                Piece Pc = Piece.fromChar( s.charAt( 0 ) );
                M_Pcs.put( Pc, M_Pcs.getOrDefault( Pc, 0 ) + 1 );
            }
        } catch( RuntimeException REx ) {
            System.err.println( "Invalid argument(s).\nUsage: java ./TetPack.class <width> <shape> <shape> ...\n" );
            throw REx;
        }

        if( nPcs == 0 ) {
            System.out.println( "Nothing to do!" );
            System.exit( 1 );
        }

        int iHeight0 = (int)Math.ceil( nPcs*OMINO / (double)iWidth ),
            iHeight = iHeight0;

        Frame F;
        while( !solveInFrame( F = new Frame( iWidth, iHeight, nPcs, M_Pcs ) ) )
            if( iHeight >= iHeight0 + 3 ) {
                System.out.println( "Specified input cannot be packed." );
                System.exit( 2 );
            } else iHeight++;

        F.dump();
        if( F.isOptimal() )
            System.out.println( "Displayed solution is optimal." );
    }

    private static boolean solveInFrame( Frame F ) {
        while( true ) {
            if( solveWithReservedCells( F ) )
                return true;
            if( !F.advanceReservedCellPermutation() )
                return false;
        }
    }

    private static boolean solveWithReservedCells( Frame F ) {
        Deque<StackFrame> SFs = new LinkedList<>();

        SFs.push( new StackFrame( F.M_Pcs, F.firstEmptyCell( 0 ) ) );
        while( !SFs.isEmpty() ) {
            StackFrame SF = SFs.peek();

            if( SF.isPieceLoaded() )
                F.subtractPieceInFrame( SF );

            if( !SF.advance() ) {
                if( DEBUG ) {
                    System.out.println( "\nConfiguration has no solutions:\n" );
                    F.dump();
                    try {
                        Thread.sleep( 250 );
                    } catch( InterruptedException IEx ) { /* ignore */ }
                }
                SFs.pop();
                continue;
            }
            if( F.canAddPieceInFrame( SF ) ) {
                F.addPieceInFrame( SF );

                if( DEBUG ) {
                    System.out.println( "\nAdded piece at stack level " + SFs.size() + ":\n" );
                    F.dump();
                    try {
                        Thread.sleep( 250 );
                    } catch( InterruptedException IEx ) { /* ignore */ }
                }
                if( SFs.size() == F.nPcs )
                    return true;

                SFs.push( SF.withoutCurrentPiece( F.firstEmptyCell( SF.iCell + 1 ) ) );
            }
        }
        return false;
    }


    private static final class Frame {
        final int iWidth;
        final int iHeight;
        final int nPcs;
        final int nCell;
        final int nEmpty;
        final EnumMap<Piece,Integer> M_Pcs;
        final char[] chCells;
        final List<List<Integer>> nsEmptyByLine;

        final List<Integer> RESERVE_ALL;

        Frame( int iWidth, int iHeight, int nPcs, EnumMap<Piece,Integer> M_Pcs ) {
            this.iWidth = iWidth;
            this.iHeight = iHeight;
            this.nPcs = nPcs;
            this.M_Pcs = M_Pcs;

            nCell = iWidth*iHeight;
            nEmpty = nCell - nPcs*OMINO;

            chCells = new char[nCell];
            Arrays.fill( chCells, CLEAR_CELL );

            RESERVE_ALL = new ArrayList<>( iWidth );
            for( int i = 0; i < iWidth; i++ )
                RESERVE_ALL.add( i );

            nsEmptyByLine = new ArrayList<>( iHeight );
            initReservedCellPermutations();
        }

        void initReservedCellPermutations() {
            if( nEmpty == 0 )
                return;

            for( int i = 0; i < Math.min( nEmpty, iHeight ); i++ )
                nsEmptyByLine.add( new ArrayList<>( iWidth ) );

            arcFirstEnPerm( Math.min( nEmpty, iWidth ), 0 );
            arcRepack( 1 );
        }

        boolean advanceReservedCellPermutation() {
            if( nEmpty == 0 )
                return false;

            int iLine = arcLowestOccupiedLine();
            while( true ) {
                int nLineCells = nsEmptyByLine.get( iLine ).size();

                if( arcNextPermForLine( iLine ) )
                    return true;
                if( iLine + 1 < nsEmptyByLine.size() && nsEmptyByLine.get( iLine + 1 ).size() < nLineCells - 1 ) {
                    arcFirstEnPerm( nLineCells - 1, iLine );
                    arcRepack( iLine + 1 );
                    return true;
                }
                if( iLine == 0 )
                    return false;

                iLine--;
            }
        }

        boolean isOptimal() {
            return nEmpty == 0;
        }

        void dump() {
            char[] chs = new char[nCell + iHeight];
            for( int i = 0; i < iHeight; i++ ) {
                System.arraycopy( chCells, i*iWidth, chs, i*(iWidth + 1), iWidth );
                chs[i*(iWidth + 1) + iWidth] = '\n';
            }
            System.out.println( new String( chs ) );
        }

        private int arcLowestOccupiedLine() {
            for( int i = nsEmptyByLine.size() - 1; i >= 0; i-- )
                if( !nsEmptyByLine.get( i ).isEmpty() )
                    return i;

            throw new InternalError();
        }

        private List<Integer> arcReservableCellsForLine( int iLine ) {
            return iLine == 0 ? RESERVE_ALL : nsEmptyByLine.get( iLine - 1 );
        }

        private boolean arcNextPermForLine( int iLine ) {
            List<Integer> iLineCells = nsEmptyByLine.get( iLine ),
                iReservables = arcReservableCellsForLine( iLine );

            int iLim = iReservables.size();
            for( int i = iLineCells.size() - 1; i >= 0; i-- ) {
                int iCell = Collections.binarySearch( iReservables, iLineCells.get( i ) );

                if( iCell < iLim - 1 ) {
                    for( int j = 0; j < iLineCells.size() - i; j++ )
                        iLineCells.set( i + j, iReservables.get( iCell + 1 + j ) );

                    arcSyncLine( iLine );
                    arcRepack( iLine + 1 );
                    return true;
                }
                iLim = iCell;
            }
            return false;
        }

        private void arcRepack( int iFirstLine ) {
            int nOutstanding = nEmpty,
                nRepackable = arcReservableCellsForLine( iFirstLine ).size();

            for( int i = 0; i < iFirstLine; i++ )
                nOutstanding -= nsEmptyByLine.get( i ).size();

            for( int iLine = iFirstLine; iLine < nsEmptyByLine.size(); iLine++ ) {
                int nPack = Math.min( nRepackable, nOutstanding );

                arcFirstEnPerm( nPack, iLine );
                nOutstanding -= nPack;
            }
        }

        private void arcFirstEnPerm( int n, int iLine ) {
            List<Integer> iLineCells = nsEmptyByLine.get( iLine ),
                iReservables = arcReservableCellsForLine( iLine );

            iLineCells.clear();
            iLineCells.addAll( iReservables.subList( 0, n ) );
            arcSyncLine( iLine );
        }

        private void arcSyncLine( int iLine ) {
            Arrays.fill( chCells, iLine*iWidth, (iLine + 1)*iWidth, CLEAR_CELL );
            for( int i : nsEmptyByLine.get( iLine ) )
                chCells[iLine*iWidth + i] = RESERVED_EMPTY_CELL;
        }

        int firstEmptyCell( int i0 ) {
            for( int i = i0; i < nCell; i++ )
                if( chCells[i] == CLEAR_CELL )
                    return i;

            throw new InternalError();
        }

        void addPieceInFrame( StackFrame SF ) {
            fillPieceCells( SF.PaO.Pc.iCells[SF.PaO.iOrient], SF.iCell, SF.PaO.Pc.chRep );
            SF.load();
        }

        void subtractPieceInFrame( StackFrame SF ) {
            fillPieceCells( SF.PaO.Pc.iCells[SF.PaO.iOrient], SF.iCell, CLEAR_CELL );
            SF.unload();
        }

        boolean canAddPieceInFrame( StackFrame SF ) {
            PieceAndOrientation PaO = SF.PaO;
            int[] iBounds = PaO.Pc.iBounds[PaO.iOrient];

            int iX = SF.iCell %iWidth,
                iY = SF.iCell/iWidth;

            if( iX + iBounds[0] < 0 || iX + iBounds[1] > iWidth || iY + iBounds[2] > iHeight )
                return false;

            int[][] isCells = PaO.Pc.iCells[PaO.iOrient];
            for( int[] iCells : isCells )
                if( chCells[SF.iCell + iCells[1]*iWidth + iCells[0]] != CLEAR_CELL )
                    return false;

            fillPieceCells( isCells, SF.iCell, PLACEHOLDER_CELL );

            int iX0 = Math.max( iX + iBounds[0] - 1, 0 ),
                iX1 = Math.min( iX + iBounds[1], iWidth );

            /* The following gap-finding routine is optimized for OMINO <= 5.  It will erroneously detect gaps for
               larger polyominos.  A more general gap-finder would examine all cells in the
               range [x0 <= x < x1, Y <= y < Y+B[2]] and report a gap iff an empty cell is found without a 4-connected
               path to the highest-index unoccupied cell in chCells. */

            assert OMINO <= 5 + /* keep the IDE happy */ Math.min(0,1);

            boolean hasGap = false;
            for( int iY_ = iY; iY_ < iY + iBounds[2]; iY_++ )
                for( int iX_ = iX0; iX_ < iX1; iX_++ )
                    if( chCells[iY_*iWidth + iX_] == CLEAR_CELL ) {
                        if( iX_ < iWidth - 1 && chCells[iY_*iWidth + iX_ + 1] == CLEAR_CELL )
                            continue;
                        if( iY_ < iHeight - 1 && chCells[(iY_ + 1)*iWidth + iX_] == CLEAR_CELL )
                            continue;
                        if( iX_ > 0 && iY_ < iHeight - 1 && chCells[iY_*iWidth + iX_ - 1] == CLEAR_CELL &&
                            chCells[(iY_ + 1)*iWidth + iX_ - 1] == CLEAR_CELL )
                        {
                            continue;
                        }

                        hasGap = true;
                        break;
                    }

            fillPieceCells( isCells, SF.iCell, CLEAR_CELL );

            return !hasGap;
        }

        private void fillPieceCells( int[][] isCells, int i0, char ch ) {
            for( int[] iCells : isCells )
                chCells[i0 + iCells[1]*iWidth + iCells[0]] = ch;
        }
    }


    private static final class StackFrame {
        final EnumMap<Piece,Integer> M_Pcs;
        final Iterator<Piece> I_Pcs;
        final int iCell;

        PieceAndOrientation PaO;
        boolean isLoaded;

        StackFrame( EnumMap<Piece,Integer> M_Pcs, int iCell ) {
            this.M_Pcs = M_Pcs;
            this.iCell = iCell;

            I_Pcs = byFrequencyIterator( M_Pcs );
            PaO = new PieceAndOrientation( null, -1 );
            isLoaded = false;
        }

        boolean isPieceLoaded() {
            return isLoaded;
        }

        boolean advance() {
            Piece Pc = PaO.Pc;
            int iOrient = PaO.iOrient;

            if( iOrient == -1 || iOrient == Pc.nOrient - 1 ) {
                if( !I_Pcs.hasNext() )
                    return false;

                Pc = I_Pcs.next();
                iOrient = 0;
            } else iOrient++;

            PaO = new PieceAndOrientation( Pc, iOrient );
            return true;
        }

        StackFrame withoutCurrentPiece( int iNewCell ) {
            EnumMap<Piece,Integer> M_NewPcs = M_Pcs.clone();

            int n = M_NewPcs.get( PaO.Pc );
            if( n == 1 )
                M_NewPcs.remove( PaO.Pc );
            else M_NewPcs.put( PaO.Pc, n - 1 );

            return new StackFrame( M_NewPcs, iNewCell );
        }

        void load() {
            assert !isLoaded;
            isLoaded = true;
        }

        void unload() {
            assert isLoaded;
            isLoaded = false;
        }

        static Iterator<Piece> byFrequencyIterator( EnumMap<Piece,Integer> M_ForPcs ) {
            List<Piece> Pcs = new ArrayList<>( M_ForPcs.keySet() );

            Collections.sort( Pcs, (Pc1,Pc2) -> M_ForPcs.get( Pc2 ) - M_ForPcs.get( Pc1 ) );
            return Pcs.iterator();
        }
    }


    private static final class PieceAndOrientation {
        final Piece Pc;
        final int iOrient;

        PieceAndOrientation( Piece Pc, int iOrient ) {
            this.Pc = Pc;
            this.iOrient = iOrient;
        }
    }


    enum Piece {
        T( 'T', new int[][] { { -1, 2, 2 }, { 0, 2, 3 }, { 0, 3, 2 }, { -1, 1, 3 } },
            new int[][][] {
                { { 0, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 } },
                { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 0, 2 } },
                { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 1, 1 } },
                { { 0, 0 }, { -1, 1 }, { 0, 1 }, { 0, 2 } }
            } ),

        I( 'I', new int[][] { { 0, 4, 1 }, { 0, 1, 4 } },
            new int[][][] {
                { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 } },
                { { 0, 0 }, { 0, 1 }, { 0, 2 }, { 0, 3 } }
            } ),

        J( 'J', new int[][] { { -1, 1, 3 }, { 0, 3, 2 }, { 0, 2, 3 }, { 0, 3, 2 } },
            new int[][][] {
                { { 0, 0 }, { 0, 1 }, { -1, 2 }, { 0, 2 } },
                { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 2, 1 } },
                { { 0, 0 }, { 1, 0 }, { 0, 1 }, { 0, 2 } },
                { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 2, 1 } }
            } ),

        L( 'L', new int[][] { { 0, 2, 3 }, { 0, 3, 2 }, { 0, 2, 3 }, { -2, 1, 2 } },
            new int[][][] {
                { { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 2 } },
                { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 0, 1 } },
                { { 0, 0 }, { 1, 0 }, { 1, 1 }, { 1, 2 } },
                { { 0, 0 }, { -2, 1 }, { -1, 1 }, { 0, 1 } }
            } ),

        S( 'S', new int[][] { { -1, 2, 2 }, { 0, 2, 3 } },
            new int[][][] {
                { { 0, 0 }, { 1, 0 }, { -1, 1 }, { 0, 1 } },
                { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 2 } }
            } ),

        Z( 'Z', new int[][] { { 0, 3, 2 }, { -1, 1, 3 } },
            new int[][][] {
                { { 0, 0 }, { 1, 0 }, { 1, 1 }, { 2, 1 } },
                { { 0, 0 }, { -1, 1 }, { 0, 1 }, { -1, 2 } }
            } ),

        O( 'O', new int[][] { { 0, 2, 2 } },
            new int[][][] {
                { { 0, 0 }, { 1, 0 }, { 0, 1 }, { 1, 1 } }
            } );

        final char chRep;
        final int nOrient;
        final int[][] iBounds;
        final int[][][] iCells;

        Piece( char chRep, int[][] iBounds, int[][][] iCells ) {
            this.chRep = chRep;
            this.iBounds = iBounds;
            this.iCells = iCells;
            nOrient = iBounds.length;
        }

        static Piece fromChar( char ch ) {
            for( Piece Pc : Piece.values() )
                if( Pc.chRep == ch )
                    return Pc;

            throw new IllegalArgumentException( "unknown shape mnemonic: '" + ch + "'" );
        }
    }
}