DWITE#5 (in turing)

[A.J]

Can someone tell me what's wrong with this.

(it doesn't work for the 4th test case, even though I am dropping the pieces from way above the 'ground')

I couldn't add comments since I didn't have time

tell me if you do not understand any part of my code

thx
(I also attached the test case)

[A.J]

GUYS I REAlly need help with this question!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

[zylum]

Your code is somewhat hard to follow especially with the lack of comments. Thus I wont find the error in your code and instead will post my solution to give you some ideas as how to improve your solution. It is heavy on bitwise operators so you may want to read the tutorial on the subject.

If you clean up your code a bit and comment it, I will be glad to take a look at it

Turing:

/* Solution by Michael Lucarz aka zylum                                      *  *                                                                           *  * This method uses bit masks to represent the board and piece. Store each   *  * row of the piece as an integer bitmask where a 1 represents a part of the *  * piece. Also store each rotation of each piece. Therefore a piece is       *  * stored as a 4 x 4 array (4 rotations and 4 rows). To make computations    *  * easy, we use an 11 x 16 board where the bottom row is full and every      *  * other row contains blocks in the first and last 3 columns. The 'middles'  *  * of the bottom 6 rows contain the boards from the test data. The bottom    *  * row is full so that we can easily determine if a piece has reached the    *  * bottom and the 3 block padded sides are to easily determine if a piece is *  * fully on the board. Once the piece and board have been initialized, we    *  * loop through each starting position and each rotation. Then we lower the  *  * peice into the board. If we encounter an overlap, we know the last        *  * position is the piece's 'resting' position. We back up once and count how *  * many rows are full (other than the bottom row).                           */ var fi, L, TL : int                              %file in, lines, temp lines open : fi, "DATA5.txt", get var line : string                                %file line var p : array 1 .. 4, 1 .. 4 of int              %piece (rotation, row) var b : array 1 .. 11 of int                     %board (rows) var tempBool : boolean                           %used for calling a function                                                  %for which we don't care about                                                  %the returned value /* xors the peice onto/off the board at position x, y and rotation r.   *  * returns whether or not the insertion was illegal (ie overlap occured */ fcn xorb (x, y, r : int) : boolean     var ret := false     for i : 1 .. 4         if i + y > 0 then                        %check if we are on the board             ret| = (b (i + y) & (p (r, i) shl (13 - x))) > 0 %check for overlap             b (i + y) xor= p (r, i) shl (13 - x)             %insertion         end if     end for     result ret end xorb for : 1 .. 5                                     %for each test case     L := 0     for i : 1 .. 4                               %for each piece rotation         for j : 1 .. 4                           %for each piece row             p (i, j) := 0         end for     end for     for i : 1 .. 4                               %for each piece row         get : fi, line         for j : 1 .. 4                           %for each piece column             if line (j) = '#' then                 p (1, 5 - i)| = 1 shl (4 - j)    %0 degrees   \                 p (2, j)| = 1 shl (4 - i)        %90 degrees   \ CCW                 p (3, i)| = 1 shl (j - 1)        %180 degrees  /                 p (4, 5 - j)| = 1 shl (i - 1)    %270 degrees /             end if         end for     end for     b (1) := 65535                               %fills the bottom row     for i : 2 .. 11                              %for each board row         b (13 - i) := 57351                      %adds 3 blocks to each side         if i > 5 then                            %if we are in the first 6 rows             get : fi, line             for j : 1 .. 10                      %for each board column                 if line (j) = '#' then                     b (13 - i)| = 1 shl (13 - j) %insert a block on the board                 end if             end for         end if     end for     for i : 0 .. 12                              %for every starting location         for j : 1 .. 4                           %for every starting rotation             TL := 0             for k : 0 .. 10                      %move the peice down                 if xorb (i, 7 - k, j) then       %if insertion illegal                     tempBool := xorb (i, 7 - k, j) %remove piece from board                     if k > 0 then                %check if we can take a step                                                  %back                         tempBool := xorb (i, 7 - k + 1, j) %insert peice one                                                  %step back                         for l : 2 .. 10          %for each row of the board                             if b (l) = 65535 then %check if it is full                                 TL += 1                             end if                         end for                         tempBool := xorb (i, 7 - k + 1, j) %remove piece                     end if                     exit                         %have gone as far as possible                 end if                 tempBool := xorb (i, 7 - k, j)   %remove piece from board             end for             L := max (L, TL)                     %update max lines         end for     end for     put L end for

[A.J]

SO many bitwise operators for my head..........looks like a good solution though (like I would know )
I'll look them up at the Turing Walkthrough, but I don't get how:

Turing:

ret| = (b (i + y) & (p (r, i) shl (13 - x))) > 0

checks for overlap, and how

Turing:

b (i + y) xor= p (r, i) shl (13 - x)

inserts.

sry, but I am a noob to bitwise operators and their uses.

[zylum]

Well the |= and xor= are basically what you would expect (work the same as +=). ret initially starts as false. Due to ors nature, if the expression to the right ever evaluates to true, then ret will be true for the remainder of the loop and thus return whether or not the expression evaluates to true at least once. If it does evaluate to true then there was an overlap.. b(i + y) is the row of the board we are checking and p(r, i) is the row and rotation of the piece we are checking. We shift the piece to the left by the appropriate number to get it in the proper position and 'and' it with the board column. If any bit in the board row is 'high' and the corresponding bit in piece is 'high' then the corresponding bit in the value of the expression will be high, thus making the expression non-zero and resulting as true.

This is a somewhat long topic. For a more detailed description, check out the tutorial.

[A.J]

thnx.
i read through the tutorial and I understand most of what you are doing.
Thank you so much .
I still don't get one part:

Turing:

b (1) := 65535

why 65535?
and could you just give a BRIEF (don't want to waste your time) explanation on how the following works:

Turing:

for i : 2 .. 11                              %for each board row         b (13 - i) := 57351                      %adds 3 blocks to each side         if i > 5 then                            %if we are in the first 6 rows             get : fi, line             for j : 1 .. 10                      %for each board column                 if line (j) = '#' then                     b (13 - i)| = 1 shl (13 - j) %insert a block on the board                 end if             end for         end if     end for

you the greatest zylum!

[zylum]

65535 in binary is 16 ones so that represents a full row. 57351 is 3 ones followed by 10 zeroes and another 3 ones. When i is > 5 then 13-i is the 6th row of the board (not including the bottom full row) and we can start reading in values of the board from the test data. Each test data row consists of 10 columns, so we iterate through them and or in a 1 when we encounter a '#'. We place the 1 in the appropriate position by shifting it.

[A.J]

thnx a lot!