DWITE#5 (in turing)
Author |
Message |
A.J
|
Posted: Sun Feb 17, 2008 3:07 pm Post subject: DWITE#5 (in turing) |
|
|
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)
Description: |
|
Download |
Filename: |
DATA5.txt |
Filesize: |
478 Bytes |
Downloaded: |
329 Time(s) |
Description: |
|
Download |
Filename: |
tetris.t |
Filesize: |
2.59 KB |
Downloaded: |
438 Time(s) |
|
|
|
|
|
|
Sponsor Sponsor
|
|
|
A.J
|
Posted: Sat Mar 08, 2008 4:29 pm Post subject: Re: DWITE#5 (in turing) |
|
|
GUYS I REAlly need help with this question!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
|
|
|
|
|
|
zylum
|
Posted: Tue Mar 11, 2008 6:06 am Post subject: RE:DWITE#5 (in turing) |
|
|
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
|
Posted: Tue Mar 11, 2008 9:44 am Post subject: Re: DWITE#5 (in turing) |
|
|
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
|
Posted: Tue Mar 11, 2008 4:47 pm Post subject: RE:DWITE#5 (in turing) |
|
|
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
|
Posted: Tue Mar 11, 2008 6:09 pm Post subject: Re: DWITE#5 (in turing) |
|
|
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:
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
|
Posted: Tue Mar 11, 2008 11:33 pm Post subject: RE:DWITE#5 (in turing) |
|
|
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
|
Posted: Tue Mar 11, 2008 11:45 pm Post subject: Re: DWITE#5 (in turing) |
|
|
thnx a lot!
|
|
|
|
|
|
Sponsor Sponsor
|
|
|
|
|