Code Golf - Tetris Fitting

Question

Time for NP-Complete code golf! Given a rectangular board, and a set of tetrominoes, can the tetrominoes be fit into the board such that all pieces are used, no space is left over, and the pieces don't overlap? See Wikipedia if you've been living under a rock and don't know what Tetrominoes are - they're just the pieces from Tetris.

Input: Two digits representing the number of rows and number of columns you have to fill. Next, 7 numbers representing how many of each piece you have. These give you the number of pieces, in the order of I, J, L, O, S, T, Z pieces Their area is guaranteed to be that of the board, so you don't have to check for trivial examples.

Sample input:

6 4 2 2 2 0 0 0 0

Output: A 1 if they can fit, a 0 otherwise.

Correct output for the input:

1

This is because you can fit the pieces as follows:

J J L L
J I I L
J I I L
L I I J
L I I J
L L J J

The input will come in through stdin. The code count includes the whole program, including reading the input from stdin.

There are no inherent limits to the size of the board, but considering it would take forever for any board larger than 30x30, let's have that as the upper limit for both rows and columns.

Answer 1

Probably not the most suitable problem for code-golf, but then again I'm not the brightest bulb in the socket.

I'll post my non-working (except for simple cases), very verbose, C# code to perhaps get some ideas going. I'm sure that I'm not following one or more of the rules, but again, I'm just posting this to get some ideas.

The problem is that each shape can be rotated and my code does not account for those rotations in the permutations (that makes this problem outrageous (in terms of permutations)!).

I am using a modified Permutation Generating class (Recursion) from here:

http://69.10.233.10/KB/recipes/Premutations.aspx

Here's my code:

/*

// o - 0xCC00

1100
1100
0000
0000

// i - 0x8888, 0xF000   

1000
1000
1000
1000

1111
0000
0000
0000

// t - 0x4E00, 0x4C40, 0xE400, 0x8C80

0100
1110
0000
0000

0100
1100
0100
0000

1110
0100
0000
0000

1000
1100
1000
0000

// l - 0x88C0, 0xE800, 0xC440, 0x2E00

1000
1000
1100
0000

1110
1000
0000
0000

1100
0100
0100
0000

0010
1110
0000
0000

// j - 0x44C0, 0x8E00, 0xC880, 0xE200

0100
0100
1100
0000

1000
1110
0000
0000

1100
1000
1000
0000

1110
0010
0000
0000

// z - 0x4C80, 0xC600 

0100
1100
1000
0000

1100
0110
0000
0000

// s - 0x8C40, 0x6C00

1000
1100
0100
0000

0110
1100
0000
0000

*/

    class Recursion
    {
        private int elementLevel = -1;
        private int numberOfElements;
        private int[] permutationValue = new int[0];
        public List<string> permutations = new List<string>();

        private char[] inputSet;
        public char[] InputSet
        {
            get { return inputSet; }
            set { inputSet = value; }
        }

        private int permutationCount = 0;
        public int PermutationCount
        {
            get { return permutationCount; }
            set { permutationCount = value; }
        }

        public char[] MakeCharArray(string InputString)
        {
            char[] charString = InputString.ToCharArray();
            Array.Resize(ref permutationValue, charString.Length);
            numberOfElements = charString.Length;
            return charString;
        }

        public void CalcPermutation(int k)
        {            
            elementLevel++;
            permutationValue.SetValue(elementLevel, k);

            if (elementLevel == numberOfElements)
            {
                OutputPermutation(permutationValue);
            }
            else
            {
                for (int i = 0; i < numberOfElements; i++)
                {
                    if (permutationValue[i] == 0)
                    {
                        CalcPermutation(i);
                    }
                }
            }
            elementLevel--;
            permutationValue.SetValue(0, k);
        }

        private void OutputPermutation(int[] value)
        {
            String s = "";
            foreach (int i in value)
            {
                //Console.Write(inputSet.GetValue(i - 1));
                s += inputSet.GetValue(i - 1);
            }
            //Console.WriteLine();
            permutations.Add(s);
            PermutationCount++;
        }
    };

    class Program
    {
        static int rows, cols;                                       
        static int[,] a;

        static void SearchShape(UInt16[] p, ref int count)
        {
            if (count > 0)
            {
                for (int u = 0; u < p.Length; u++)
                {
                    if (FindPlace(p[u]) > 0)
                    {
                        count--;
                        break;
                    }
                }
            }
        }

        static int WillFit(UInt16 s, int r, int c)
        {
            int row = 0, col = 0;

            for (int bit = 0x8000; bit >= 0x0001; bit >>= 1)
            {                
                if ((bit & s) > 0)
                {
                    if (((row + r) > (rows - 1)) || ((col + c) > (cols - 1)))
                    {
                        return 0;
                    }

                    if (a[row + r, col + c] == 1)
                    {
                        return 0;
                    }
                }

                col++;
                if (col == 4)
                {
                    row++;
                    col = 0;
                }
            }

            return 1;
        }

        static void PlaceShape(UInt16 s, int r, int c)
        {
            int row = 0, col = 0;

            for (int bit = 0x8000; bit >= 0x0001; bit >>= 1)
            {
                if ((bit & s) > 0)
                {
                    a[row + r, col + c] = 1;
                }

                col++;
                if (col == 4)
                {
                    row++;
                    col = 0;
                }
            }            
        }

        static int FindPlace(UInt16 s)
        {
            for (int r = 0; r < rows; r++)
            {
                for (int c = 0; c < cols; c++)
                {
                    if (WillFit(s, r, c) == 1)
                    {
                        PlaceShape(s, r, c);
                        return 1;
                    }
                }
            }

            return 0;
        }

        static void Main(string[] args)
        {
            UInt16[] o = new UInt16[] { 0xCC00 };
            UInt16[] i = new UInt16[] { 0x8888, 0xF000 };
            UInt16[] t = new UInt16[] { 0x4E00, 0x4C40, 0xE400, 0x8C80 };
            UInt16[] l = new UInt16[] { 0x88C0, 0xE800, 0xC440, 0x2E00 };
            UInt16[] j = new UInt16[] { 0x44C0, 0x8E00, 0xC880, 0xE200 };
            UInt16[] z = new UInt16[] { 0x4C80, 0xC600 }; 
            UInt16[] s = new UInt16[] { 0x8C40, 0x6C00 };

            rows = int.Parse(args[0]);
            cols = int.Parse(args[1]);                       

            Recursion rec = new Recursion();
            rec.InputSet = rec.MakeCharArray("0123456");
            rec.CalcPermutation(0);

            bool found = false;
            for (int y = 0; y < rec.PermutationCount; y++)
            {
                Console.WriteLine(y.ToString());
                a = new int[rows, cols];

                int ic = int.Parse(args[2]);
                int jc = int.Parse(args[3]);
                int lc = int.Parse(args[4]);
                int oc = int.Parse(args[5]);
                int sc = int.Parse(args[6]);
                int tc = int.Parse(args[7]);
                int zc = int.Parse(args[8]);

                int k = 0;
                int r = y;
                while (k < rec.PermutationCount)
                {
                    foreach (Char c in rec.permutations[r])
                    {
                        switch (c)
                        {
                            case '0':
                                SearchShape(i, ref ic);
                                break;
                            case '1':
                                SearchShape(j, ref jc);
                                break;
                            case '2':
                                SearchShape(l, ref lc);
                                break;
                            case '3':
                                SearchShape(o, ref oc);
                                break;
                            case '4':
                                SearchShape(s, ref sc);
                                break;
                            case '5':
                                SearchShape(t, ref tc);
                                break;
                            case '6':
                                SearchShape(z, ref zc);
                                break;
                        }
                    }

                    k++;
                    r++;
                    if (r == rec.PermutationCount)
                        r = 0;
                }

                if ((ic + jc + lc + oc + sc + tc + zc) == 0)
                {
                    found = true;
                    break;
                }                
            }

            if (found == true)
                Console.WriteLine("1");
            else
                Console.WriteLine("0");

            for (int k = 0; k < rows; k++)
            {
                for (int p = 0; p < cols; p++)
                {
                    Console.Write(a[k, p].ToString() + " ");
                }
                Console.WriteLine();
            }
        }
    }

Answer 2

Python 3.1, 467C

Horribly inefficient, and yes, it really requires Python 3.1.

from itertools import*
S=sum
R=range
r=lambda t:S((1<<i&t)<<(503195562368432924944083>>i*5&31)for i in R(16))>>16
s=[(t,r(t),r(r(t)),r(r(r(t))))for t in(61440,57856,59392,52224,27648,50688,58368)]
h,w,*n=map(int,input().split())
print(int(any(2**(h*w)-1==S(S(((t[o]>>r*4&15<<m*4)>>m*4+l&2**(w-j)-1)<<(i+m)*w+j for m in R(4-r))for t,(i,j,r,l,o)in zip(S([n*[t]for t,n in zip(s,n)],[]),c))for c in combinations_with_replacement(product(R(h),R(w),R(4),R(4),R(4)),S(n)))))

Tested with all inputs for fields of size 2x2, 2x4 and 4x2. For 3x4 and 4x3 the code returns 1 on the correct inputs, but takes too long to finish for tiles which cannot be made to fit (eventually I quit the script).

Answer 3

J, 296 characters

c=:[:,i.@{.{@(,&<)i.@{:
4(1!:2)~0~:#>4 :0&.>/((2}.i)#|:@|.&.>^:(i.4)&.><"0(1 4$1);((|.;])4>i.2 3),(2 2$1);(2 3$1|.1<i.6);(0~:2(~:*])i.2 3);3 2$1|.1<i.6),<0$~1,2{.i=:".1!:1]3
r=.0#y
for_a.x do.d=.$>a
for_b.y do.for_o.c>:d-~2{.i do.t=:o+&.>(c d)({#[)>a
if.-.+./t{b do.r=.r,1 t}b end.end.end.end.r
)

No clever algorithms here: it's a dumb breadth-first search (easier to implement than a back-tracking depth-first search), and horribly inefficient resource-wise. The board and pieces are stored as 2-D boolean arrays (rotated with |:@|. (transpose after reverse), which I thought was pretty clever), and that looong second line is my attempt at compressing the piece information.