Page 1 of 1

10411 - Another Game of Tetris

Posted: Tue Mar 04, 2003 2:02 pm
by Ghost77 dimen

The request is stated below:

Find a solution with no more than 10,000 operations to achieve the goal, i.e clean up the whole board.

What kind of searching stategy can have it done well??? :roll:

By the way, the problem 197 is also complicated like this or even harder.

I guess the main ideas of them are similar.

Would anyone like give me some clues?Thanks.

Posted: Wed Mar 05, 2003 10:21 am
by Larry
There's a simple filtering that makes this problem computationally a lot simpler. If a column is really tall, think about how you would get rid of it..

Posted: Wed Mar 05, 2003 1:08 pm
by Ghost77 dimen

Filter some situations can reduce the judge time and the operations.

But I have no idea how to generate a program to solve this problem.

That is, I don't know how to search in this complicated problem.


Posted: Wed Mar 05, 2003 5:43 pm
by Larry
Alright, another hint then:

There's a condition that holds for a column that has height over 4. How would you reduce it to lower than height 4?

Posted: Thu Mar 06, 2003 10:43 pm
by Yarin
Problem 197 and this problem is completely different. 197 is a brute force search over all possible states, which is feasible. In this problem, no such search is necessary since you don't need the optimal solution.

I made a greedy solution - find the lowest column, try placing all pieces in all rotations so this column is filled (and no holes appear). Select the combination which flattens all the columns most (sum of the squares of neighbouring column differences). In case of a tie, choose at random (important, didn't work otherwise). Maybe not the best solution, but it worked ;-) (and I'm pretty sure it will always work under the problem constraints).

Posted: Sun Mar 09, 2003 11:35 am
by Ghost77 dimen


I also use greedy method to approach a solution.

But I got OLE.

My strategy is :

1. Find the lowest column, and search for i <- 1 to 19 operation

2. If the operation can fill in this column without further spaces, goto 3

3. Set some attribute of the situaction.

One is the rate of eveness 1 2 1 0 --> 4 ; 1 1 1 1 --> 0

;another is the difference of height between the highest column

and lowest one.

4. Finally, choose the best one operation ,according to the attributes,

to fill in.

:D Hmmm~~, how about the stategy above?

Where can be improved or any algorithm is better?

Posted: Sun Mar 09, 2003 3:53 pm
by Larry
There is a filter that basically lowers all the columns so that the end result will be n columns, each with less than 4 in height, which is probably optimal in what it suppose to do. PM me if you want more..

10411 Another Game of Tetris.

Posted: Mon Apr 07, 2003 12:37 pm
by Andrey Mokhov
Hi, everyone!

I'm trying to solve this problem, but I can't understand this phrase
For each column, the occupied blocks should be successive starting from bottom at ANY TIME, so the board can be represented by an array of n integers indicating the 'height'(number of occupied blocks) of each column.
What will happen if I will make a 'hole' with my move, i.e. I'll put such a piece that under one of its squares there will be an empty square? Will that empty square be considered to be filled or I just can't do such a move?

And another question. What if a puzzle has no solution? I mean for exapmle such an input:

Code: Select all

0 1
We can't here clean up all the board as all the pieces have even number of squares in it (four).

Thank you in advance.

Re: 10411 - Another Game of Tetris

Posted: Thu Aug 16, 2012 4:25 am
by brianfry713
You can't make a move that will create a hole.

All puzzles have a solution. I used an algorithm similar to Yarin's and got AC in 0.02 sec. I also checked that there is never a case where n is even and the sum of the heights is odd. There is also never a case where n is divisible by 4 and the sum of the heights modulo 4 is 2.