アルゴリズム研究『カラーボックスで作る本棚』 (Remix.asia)

『プログラマ脳を鍛える数学パズルシンプルで高速なコードが書けるようになる70問』
こちら、全部ルビーだったら残念だと思いきや、C言語やJavaScriptでのソースコードダウンロードが可能。
http://codezine.jp/article/detail/8985
辺の比２：３の長方形を任意の長方形となるように敷き詰める組み合わせ
が興味深かったのでJavaに移植．．．▼

最新の言語使用には依存していないのでご安心。

public class Bookshelf{
    static int box[];

    public static int bookshelf( int w, int h, int x, int y ){
        if( x >= w ){    //    一行を埋めた場合、次の行に移動
            return bookshelf( w, h, 0, y+1 );
        }
        if( y >= h ){    //    すべて埋まっていた場合1、空きがあった場合0を返す
            for( int i=0; i<box.length; i++ ){
                if( 0 == box[i] ){
                    return 0;
                }
            }
            return 1;
        }
        int c = 0;
        if( 0 == box[x + y * w] ){
            if( (x + 2 <= w) && (y + 3 <= h) ){    //    縦に配置
                if(
                    (0 == box[x + (y + 0) * w]) && (0 == box[x + (y + 0) * w +1])
                &&    (0 == box[x + (y + 1) * w]) && (0 == box[x + (y + 1) * w +1])
                &&    (0 == box[x + (y + 2) * w]) && (0 == box[x + (y + 2) * w +1])
                ){
                    box[x + (y + 0) * w]= 1;    box[x + (y + 0) * w +1]= 1;
                    box[x + (y + 1) * w]= 1;    box[x + (y + 1) * w +1]= 1;
                    box[x + (y + 2) * w]= 1;    box[x + (y + 2) * w +1]= 1;
                    c += bookshelf( w, h, x + 2, y );
                    box[x + (y + 0) * w]= 0;    box[x + (y + 0) * w +1]= 0;
                    box[x + (y + 1) * w]= 0;    box[x + (y + 1) * w +1]= 0;
                    box[x + (y + 2) * w]= 0;    box[x + (y + 2) * w +1]= 0;
                }
            }
            if( (x + 3 <= w) && (y + 2 <= h) ){    //    横に配置
                if(
                    (0 == box[x + (y + 0) * w]) && (0 == box[x + (y + 0) * w +1]) && (0 == box[x + (y + 0) * w +2])
                &&    (0 == box[x + (y + 1) * w]) && (0 == box[x + (y + 1) * w +1]) && (0 == box[x + (y + 1) * w +2])
                ){
                    box[x + (y + 0) * w]= 1; box[x + (y + 0) * w +1]= 1; box[x + (y + 0) * w +2]= 1;
                    box[x + (y + 1) * w]= 1; box[x + (y + 1) * w +1]= 1; box[x + (y + 1) * w +2]= 1;
                    c += bookshelf( w, h, x + 3, y );
                    box[x + (y + 0) * w]= 0; box[x + (y + 0) * w +1]= 0; box[x + (y + 0) * w +2]= 0;
                    box[x + (y + 1) * w]= 0; box[x + (y + 1) * w +1]= 0; box[x + (y + 1) * w +2]= 0;
                }
            }
        }else{
            c += bookshelf( w, h, x + 1, y );
        }
        return c;
    }

    public static void main( String args[] ){
        int N=20;    //    カラーボックスの個数
        int S=N*2*3;//    長方形の面積
        box = new int[S];
        int cnt=0;
        
        for( int i=2; i<S; i++ ){
            if( S != (S/i)*i )    continue;
            cnt += bookshelf( S/i, i, 0, 0 );
        }
        System.out.println( cnt );
    }
}

せっかくなので敷き詰めたパターンを表示。

public class Bookshelf{
    static String box[];

    public static void main( String args[] ){
        int N=20;    //    カラーボックスの個数
        int S=N*2*3;//    長方形の面積
        box = new String[S];
        int cnt=0;
        for( int i=0; i<S; i++ )    box[i]= "";
        
        for( int i=2; i<S; i++ ){
            if( S != (S/i)*i )    continue;
            System.out.println( "height:" + i );
            cnt += bookshelf( S/i, i, 0, 0 );
        }
        System.out.println( "total:" + cnt );
    }

    public static int bookshelf( int w, int h, int x, int y ){
        if( x >= w ){    //    一行を埋めた場合、次の行に移動
            return bookshelf( w, h, 0, y+1 );
        }
        if( y >= h ){    //    すべて埋まっていた場合1、空きがあった場合0を返す
            for( int i=0; i<box.length; i++ ){
                if( "" == box[i] ){
                    return 0;
                }
            }
            //    完成したパターンを表示
            for( int i=0; i<box.length; i++ ){
                System.out.print( box[i] );
                if( 0 == (i+1)%w )    System.out.println( "" );
            }
            System.out.println( "" );
            return 1;
        }
        int c = 0;
        if( "" == box[x + y * w] ){
            if( (x + 2 <= w) && (y + 3 <= h) ){    //    縦に配置
                if(
                    ("" == box[x + (y + 0) * w]) && ("" == box[x + (y + 0) * w +1])
                &&    ("" == box[x + (y + 1) * w]) && ("" == box[x + (y + 1) * w +1])
                &&    ("" == box[x + (y + 2) * w]) && ("" == box[x + (y + 2) * w +1])
                ){
                    box[x + (y + 0) * w]= "┌";    box[x + (y + 0) * w +1]= "┐";
                    box[x + (y + 1) * w]= "│";    box[x + (y + 1) * w +1]= "│";
                    box[x + (y + 2) * w]= "└";    box[x + (y + 2) * w +1]= "┘";
                    c += bookshelf( w, h, x + 2, y );
                    box[x + (y + 0) * w]= "";    box[x + (y + 0) * w +1]= "";
                    box[x + (y + 1) * w]= "";    box[x + (y + 1) * w +1]= "";
                    box[x + (y + 2) * w]= "";    box[x + (y + 2) * w +1]= "";
                }
            }
            if( (x + 3 <= w) && (y + 2 <= h) ){    //    横に配置
                if(
                    ("" == box[x + (y + 0) * w]) && ("" == box[x + (y + 0) * w +1]) && ("" == box[x + (y + 0) * w +2])
                &&    ("" == box[x + (y + 1) * w]) && ("" == box[x + (y + 1) * w +1]) && ("" == box[x + (y + 1) * w +2])
                ){
                    box[x + (y + 0) * w]= "┌"; box[x + (y + 0) * w +1]= "─"; box[x + (y + 0) * w +2]= "┐";
                    box[x + (y + 1) * w]= "└"; box[x + (y + 1) * w +1]= "─"; box[x + (y + 1) * w +2]= "┘";
                    c += bookshelf( w, h, x + 3, y );
                    box[x + (y + 0) * w]= ""; box[x + (y + 0) * w +1]= ""; box[x + (y + 0) * w +2]= "";
                    box[x + (y + 1) * w]= ""; box[x + (y + 1) * w +1]= ""; box[x + (y + 1) * w +2]= "";
                }
            }
        }else{
            c += bookshelf( w, h, x + 1, y );
        }
        return c;
    }
}

Remix.asia ...

アルゴリズム研究『カラーボックスで作る本棚』

トラックバック

コメントを投稿

検索

最近のエントリー

カテゴリー