Computer Science Canada

Shortest Tetris Challenge

Author:  zylum [ Fri Feb 01, 2008 12:24 pm ]
Post subject:  Shortest Tetris Challenge

OK, so there's been a few tetris submissions in the turing forums, some of which had comments relating to how long a tetris program should be. Thus I propose a challenge: program tetris in as few lines as possible.

Rules:
1) Your program must more or less conform to the standard tetris rules outlined in section 5 here
2) The official line count will be the number of lines after hitting F2 in the turing environment
3) You may post your code here or you may PM me with your submissions
4) Deadline is Sunday February 10th, 2008 at midnight

Bits will be awarded based on how many lines your program is. To make things more interesting you have a choice:

Bits = round (10000 / max (lines - 50, 1)) - 50
or
Bits = round (1000 / max (lines - zylumLines + 1, 1))

I suppose other languages could be allowed, though the graphics wouldn't be as easy.

That's about all for now. I look forward to some creative solutions!

BTW here's my submission. I will post the password to the source once the contest is over...

Author:  Clayton [ Fri Feb 01, 2008 12:28 pm ]
Post subject:  RE:Shortest Tetris Challenge

Is there a character limit per line?

Author:  zylum [ Fri Feb 01, 2008 12:42 pm ]
Post subject:  RE:Shortest Tetris Challenge

Well if the lines are too long, they are wrapped after hitting F2. If you are referring to languages other than turing, then no, there is no line limit but standard coding conventions should be used.

Author:  fishtastic [ Fri Feb 01, 2008 1:20 pm ]
Post subject:  RE:Shortest Tetris Challenge

I am in!

since exam has been delayed till monday i will spend some time changing my code.
current lengh is around 400 with all the extra features now let me get rid of them XD

Author:  fishtastic [ Fri Feb 01, 2008 11:56 pm ]
Post subject:  Re: Shortest Tetris Challenge

here it is, still very long. it looks like i can only get something like 10 bits.

Is that all the features i need?

Author:  StealthArcher [ Sat Feb 02, 2008 12:35 am ]
Post subject:  RE:Shortest Tetris Challenge

If I decide to try this, being relatively horrible at tetris, and at game making in general, what is the limitation of external files?

Author:  zylum [ Sat Feb 02, 2008 1:47 am ]
Post subject:  RE:Shortest Tetris Challenge

fishtastic> your board is only 8x18.. Also, your controls seem a bit sticky at times, and at other times over responsive (ie rotates a few times from pushing up once). Standard tetris says "All inputs take effect on the rising-edge of the positive input (i.e., on button press, as opposed to button release)"

Other than that, everything seems to be in good shape Wink

StealthArcher> What do you mean external files? If your source is divided amongst several files, then the sum of the line counts will be the total line count..

Author:  StealthArcher [ Sat Feb 02, 2008 1:54 am ]
Post subject:  RE:Shortest Tetris Challenge

I mean, using files to store data (numbers etc.), not source code.

Author:  zylum [ Sat Feb 02, 2008 3:16 am ]
Post subject:  RE:Shortest Tetris Challenge

Lets keep it to 1 file as I stored all my data in my source code..

Author:  fishtastic [ Sat Feb 02, 2008 9:29 am ]
Post subject:  Re: RE:Shortest Tetris Challenge

zylum @ Sat Feb 02, 2008 12:47 am wrote:
Also, your controls seem a bit sticky at times, and at other times over responsive (ie rotates a few times from pushing up once). Standard tetris says "All inputs take effect on the rising-edge of the positive input (i.e., on button press, as opposed to button release)"


you mean each time you press a key the block should only rotate/move once??

how do you do that in turing? Shocked
well i cound but if i make a extra variable to make sure the key stops then it will take even more lines.

Author:  fishtastic [ Sat Feb 02, 2008 9:55 am ]
Post subject:  RE:Shortest Tetris Challenge

I changed from input.keydown to getchar.
now every key does something. and it will repeat if you hold down for i while.

it says
"When a button press occurs, this counts as a request. Holding a button down beyond a certain time may result in the "auto-repeat" feature of a keyboard, generating new button presses -- but this feature is external to the game engine. "

so i guess its ok.

Author:  Tony [ Sat Feb 02, 2008 2:27 pm ]
Post subject:  Re: RE:Shortest Tetris Challenge

fishtastic @ Sat Feb 02, 2008 9:29 am wrote:
how do you do that in turing? Shocked

When we are talking about input edges, or button states, there are 4 for each button. It's tracked over two frames -- that is, where the button was last time through the loop, and where it is now. This generates 4 unique possible states:

UP UP -- the button is up
DOWN DOWN -- the button is held down
UP DOWN -- the button has just be pressed down
DOWN UP -- the button has just been released up

In Turing you would copy the state of the keyboard into the "old_state" variable just before calling Input.KeyDown()

Author:  fishtastic [ Sat Feb 02, 2008 2:58 pm ]
Post subject:  Re: Shortest Tetris Challenge

Here it is! my final version.

This is the shortest I can do.
And i think i fixed all the problems.

I was being very cheap while coding this.
I was changing all "const" to actual number, all 2 layer for loop to 1 layer div/mod for loop.
I had a lot of fun making this and being cheap. hopefully, Zylum did not do the same thing. Rolling Eyes

you can still play the game
Anyway. i will tell everyone the password for code on the final day as the rule said.

Author:  Clayton [ Sat Feb 02, 2008 4:03 pm ]
Post subject:  RE:Shortest Tetris Challenge

Zylum probably did his in 25 lines.

Author:  fishtastic [ Sat Feb 02, 2008 4:13 pm ]
Post subject:  Re: RE:Shortest Tetris Challenge

Clayton @ Sat Feb 02, 2008 3:03 pm wrote:
Zylum probably did his in 25 lines.


what?? in turing?? Shocked Shocked OMGOMG Shocked OMGOMG Shocked Shocked

That is not possible. no way!
If he did it in 25 lines then the equation will not be 1000/(yourline - zylumline)
I say it took him at least 50 lines.

Author:  Tony [ Sat Feb 02, 2008 4:47 pm ]
Post subject:  RE:Shortest Tetris Challenge

If you take out the exact specifications of "standard tetris", zylum could make "a tetris" in 20 lines.

Author:  ericfourfour [ Sat Feb 02, 2008 5:31 pm ]
Post subject:  Re: Shortest Tetris Challenge

The file is 2734 Bytes. Each character is 1 Byte. To find out how many lines Zylum used you need to guess the average number of characters per line.

code:
nBytes / nLines = chars / line
nLines = nBytes / (chars / line)
nLines = 2734 / (chars / line)


Let's try 32 chars / line:
code:
nLines = 2734 / 32
nLines = approx. 85 lines


Let's try 80 chars / line:
code:
nLines = 2734 / 80
nLines = approx. 34 lines


My guess is 34 <= zylumLines <= 85.

Author:  Tony [ Sat Feb 02, 2008 6:55 pm ]
Post subject:  RE:Shortest Tetris Challenge

Keep in mind that there is a datafile in there as well.

Also, there's a lot of variance in "characters per line".

loop / end loop is 2 lines and only 11 characters.

Author:  zylum [ Sat Feb 02, 2008 9:48 pm ]
Post subject:  Re: Shortest Tetris Challenge

Clayton @ Sat Feb 02, 2008 5:03 pm wrote:
Zylum probably did his in 25 lines.

I was hoping to Laughing It's harder than it looks to apply the standard rules. Theres a lot more going on in tetris than in pong, and so far the record for that is 19 lines by Catalyst.. The user controls are more complex, there are more variables to keep track of, the collisions are much more complex, the drawing is more complex. You have to collapse the stack once a row is complete... You get the picture Wink

You guys over estimate me a bit Embarassed I would be lucky to make "a tetris" in 40 lines...

fishtastic> I'm glad you enjoyed the contest Smile And yes, I also used "cheap" tricks, but thats what makes it so fun.. Trying to squeeze out every last line is fun and challenging and makes you look at the problem differently.

As for your program, it's a lot better! Couple of small details though.. The pieces don't generate at the proper place (ie [6, 20]) and some of the pieces don't rotate properly (the I piece for instance), but these problems should be trivial to fix at this point.

So far fishtastic is the only submission. Looking forward to seeing more Wink


BTW here's a slightly shorter version of mine...

Author:  Clayton [ Sun Feb 03, 2008 11:03 am ]
Post subject:  RE:Shortest Tetris Challenge

I was kind of being a bit sarcastic, but you get my point Wink

Author:  fishtastic [ Sun Feb 03, 2008 2:07 pm ]
Post subject:  Re: Shortest Tetris Challenge

here. my newer version.
few lines shorter.
and i think i fixed the rotation.

I will post the code near the of this challenge. since i might change my code again.
Very Happy

Author:  ericfourfour [ Sun Feb 03, 2008 7:28 pm ]
Post subject:  Re: Shortest Tetris Challenge

If anyone wants to know a shortcut for doing rotations:

As long as you design your pieces the way the site Zylum linked to did, this should be no problem.

The formula for rotating a point around the origin is:
code:
newX = x * cos theta - y * sin theta
newY = x * sin theta + y * cos theta

Since we are only rotating counter-clockwise, the angle is: 90 degress (or pi / 2 radians).
code:
newX = x * cos 90 - y * sin 90
newY = x * sin 90 + y * cos 90

Since: sin 90 = 1 and cos 90 = 0:
code:
newX = x * 0 - y * 1
newY = x * 1 + y * 0

or:
code:
newX = -y
newY = x


An example of this in Turing:
Turing:
type Point :
    record
        x, y : int
    end record

fcn rotatePoint90 (point : Point) : Point
    var newPoint : Point
    newPoint.x := -point.y
    newPoint.y := point.x
    result newPoint
end rotatePoint90


If you want to rotate clockwise use theta = 270 (or 3 * pi / 2 radians).

You will also have to compensate for pieces that do not rotate or only rotate once.

Author:  fishtastic [ Sat Feb 09, 2008 1:23 pm ]
Post subject:  Re: Shortest Tetris Challenge

Here is my code.
It seems like no one else is doing this challenge, also i don't think i can make it shorter.
although I could use some really meaningless methods (such as putting all variables in one variable using div/mod).
But even if that makes the program having lesser lines, it wont really make the program smaller in size.
I think the contest would be better if it is marked based on the size(in bytes) instead of line number.

anyway. the program is 80 line (by that i mean after f2 and does not generate a not enough memory for indent message.)
I don't think i will have time to work on this since it ends on sunday and i have quite lot of things to do this week.

I would really like to see how zylum did it. zylum's is almost 1kb smaller
(still looks impossible Shocked Shocked Shocked )

Turing:
View.Set ("offscreenonly;graphics:200;300,position:bottom;left,nobuttonbar")
var m, bk, eb : array 1 .. 22, 1 .. 12 of boolean
var g, ol := false
var x, y, cb, dt, score := 0
var nx := Rand.Int (1, 7)
var data : array 1 .. 28 of string := init ("0000000011110000", "0000011001100000", "0000001101100000", "0000011000110000", "0000010001110000", "0000000101110000", "0000001001110000",
    "0010001000100010", "0000011001100000", "0000001000110001", "0000000100110010", "0000001100100010", "0000001000100011", "0000001000110010",
    "0000000011110000", "0000011001100000", "0000001101100000", "0000011000110000", "0000000001110001", "0000000001110100", "0000000001110010",
    "0010001000100010", "0000011001100000", "0000001000110001", "0000000100110010", "0000001000100110", "0000011000100010", "0000001001100010")
var keys : array 1 .. 20 of string := init (KEY_LEFT_ARROW, "1", "0", "0", "1", KEY_RIGHT_ARROW, "-1", "0", "0", "1", KEY_DOWN_ARROW, "0", "1", "0", "20", KEY_UP_ARROW, "0", "0", "1", "1",)
for i : 0 .. 22 * 12 - 1
    eb (i div 12 + 1, i mod 12 + 1) := false
    m (i div 12 + 1, i mod 12 + 1) := i div 12 + 1 = 1 or i div 12 + 1 = 22 or i mod 12 + 1 = 1 or i mod 12 + 1 = 12
end for
proc newb (b, x, y, sx, sy : int, DM, DB : boolean)
    ol := false
    g := false
    bk := eb
    for i : 0 .. 22 * 12 - 1
        if i > 0 and i <= 16 and y + (i - 1) div 4 > 0 and x + (i - 1) mod 4 > 0 and x + (i - 1) mod 4 <= 12 and data (b) (i) = '1' then
            bk (y + (i - 1) div 4, x + (i - 1) mod 4) := true
            ol := ol or ((m (y + (i - 1) div 4, x + (i - 1) mod 4)) and y + (i - 1) div 4 < 22)
            g := g or ((y + (i - 1) div 4 - 1 > 0 and m (y + (i - 1) div 4 - 1, x + (i - 1) mod 4)) and bk (y + (i - 1) div 4, x + (i - 1) mod 4))
        end if
        if (m ((i div 12 + 1), (i mod 12 + 1)) and DM) or (bk ((i div 12 + 1), (i mod 12 + 1)) and DB) then
            drawfillbox (sx + (i mod 12 + 1) * 10 - 8, sy + (i div 12 + 1) * 10 - 8, sx + (i mod 12 + 1) * 10, sy + (i div 12 + 1) * 10, 145)
        end if
    end for
end newb
loop
    cb := nx
    nx := Rand.Int (1, 7)
    x := 5
    y := 19
    newb (cb, x, y, 5, 5, true, true)
    exit when ol
    loop
        if hasch then
            var key := getchar
            for i : 0 .. 3
                if key = keys (i * 5 + 1) then
                    for j : 1 .. strint (keys (i * 5 + 5))
                        x -= strint (keys (i * 5 + 2))
                        y -= strint (keys (i * 5 + 3))
                        cb := (cb + strint (keys (i * 5 + 4)) * 7 - 1) mod 28 + 1
                        newb (cb, x, y, 5, 5, false, false)
                        exit when ol
                    end for
                    if ol then
                        x += strint (keys (i * 5 + 2))
                        y += strint (keys (i * 5 + 3))
                        cb := (cb - strint (keys (i * 5 + 4)) * 7 - 1) mod 28 + 1
                    end if
                end if
            end for
        end if
        dt += 1
        newb (cb, x, y, 5, 5, true, true)
        y += ord (ol) - ord (dt mod 5 = 0)
        exit when g and not ol and dt mod 5 = 0
        put "SCORE:  ", score
        newb (nx, 2, 2, 120, 220, false, true)
        View.Update
        Time.DelaySinceLast (100)
        cls
    end loop
    for i : 0 .. 22 * 12 - 1
        m (i div 12 + 1, i mod 12 + 1) := bk (i div 12 + 1, i mod 12 + 1) or m (i div 12 + 1, i mod 12 + 1)
    end for
    for decreasing i : 22 - 1 .. 2
        if m (i, 11) = true and m (i, 2) = true and m (i, 3) = true and m (i, 4) = true and m (i, 5) = true
                and m (i, 6) = true and m (i, 7) = true and m (i, 8) = true and m (i, 9) = true and m (i, 10) = true then
            score += 1
            for k : i * 12 .. (22 - 2) * 12
                m ((k div 12), k mod 12 + 1) := m ((k div 12) + 1, k mod 12 + 1)
            end for
        end if
    end for
end loop
put "Game Over"

Author:  zylum [ Mon Feb 11, 2008 4:25 am ]
Post subject:  RE:Shortest Tetris Challenge

OK so the contest is closed with a total of one submissions Laughing Before I post my code, I just need to know which prize you would like fishtastic...

BTW I'm quite impressed you made it so short Wink good job!

Author:  Tony [ Mon Feb 11, 2008 10:32 am ]
Post subject:  RE:Shortest Tetris Challenge

Awesome. I quite like this line, for initializing that 2D boolean array:
Turing:

m (i div 12 + 1, i mod 12 + 1) := i div 12 + 1 = 1 or i div 12 + 1 = 22 or i mod 12 + 1 = 1 or i mod 12 + 1 = 12

Nice! Smile

Author:  fishtastic [ Mon Feb 11, 2008 3:30 pm ]
Post subject:  Re: RE:Shortest Tetris Challenge

zylum @ Mon Feb 11, 2008 3:25 am wrote:
OK so the contest is closed with a total of one submissions Laughing Before I post my code, I just need to know which prize you would like fishtastic...

I dont really think mine is short enough to compare with yours.
first one please Very Happy : Bits = round (10000 / max (lines - 50, 1)) - 50

BTW I remember seeing 1kb tetris in flash before, just cant find the site anymore....

Author:  Clayton [ Mon Feb 11, 2008 3:44 pm ]
Post subject:  RE:Shortest Tetris Challenge

Turing:
if Sys.Exec ("tetris.exe") then
    put "Tetris in 3 lines, go me."
end if


I'll take option one, as that results in 9950 bits.

Author:  Tony [ Mon Feb 11, 2008 3:47 pm ]
Post subject:  RE:Shortest Tetris Challenge

Turing:

put Sys.Exec("tetris.exe")

gg Clayton

Author:  Clayton [ Mon Feb 11, 2008 3:48 pm ]
Post subject:  RE:Shortest Tetris Challenge

but that way you don't get my gloating-ness, also, what the hell does true/false mean to the end user? Wink

Author:  StealthArcher [ Mon Feb 11, 2008 5:34 pm ]
Post subject:  RE:Shortest Tetris Challenge

Turing:
var owned:boolean:=Sys.Exec("tetris.exe")

Author:  zylum [ Mon Feb 11, 2008 7:04 pm ]
Post subject:  Re: Shortest Tetris Challenge

Alright, here's my code.. Only marginally better than fishtastic's at 73 lines Cool I used a lot of bit manipulation to make it short. I think my main game loop can be shortened a bit but I'm too lazy now Laughing

Turing:
View.Set ("graphics:220;220,nobuttonbar,offscreenonly")
color (0)
colorback (7)
var p : array 1 .. 7, 1 .. 4 of int := init (1632, 1632, 1632, 1632, 3840, 17476, 3840, 17476, 3168, 19584, 3168,
    19584, 1728, 35904, 1728, 35904, 3616, 17600, 36352, 25664, 3712, 50240, 11776, 17504, 3648, 19520, 19968, 17984)
var b : array 0 .. 24 of int := init (0, 0, 0, 32760, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 16392, 32760)
var pnn := Rand.Int (1, 7)
var pn, pr, px, py, t : int
var lines := 0
var down := false
var k : array char of boolean
proc xorp
    for i : 0 .. 3
        b (py - i + 1) xor= ((p (pn, pr) & (15 shl (4 * (3 - i)))) shr (4 * (3 - i))) shl (px + 1)
    end for
end xorp
fcn overlap (i : int) : boolean
    result i <= 3 & ((b (py - i + 1) & (((p (pn, pr) & (15 shl (4 * (3 - i)))) shr (4 * (3 - i))) shl (px + 1))) > 0| overlap (i + 1))
end overlap
fcn makeMove (var v : int, vo, d, m : int) : boolean
    v := v mod m + d
    if overlap (0) then
        v := vo
    end if
    result false
end makeMove
loop
    pn := pnn
    pnn := Rand.Int (1, 7)
    pr := 1
    py := 23
    px := 6
    cls
    exit when overlap (0)
    put "\n\n\n\n\n\n\n\n\n\t\tLINES:\n\t\t======\n\t\t", lines : 6
    Draw.FillBox (130, 150, 190, 190, 0)
    for i : 0 .. 11
        Draw.FillBox ((i div 3) * 10 + 140, (i mod 3) * 10 + 150, (i div 3) * 10 + 150, (i mod 3) * 10 + 160, sign (p (pnn, 1) & (1 shl ((i mod 3) * 4 + (i div 3)))) * 7)
    end for
    loop
        py -= 1
        exit when overlap (0)
        t := Time.Elapsed
        loop
            exit when Time.Elapsed - t >= 500 - min (450, (lines div 10) * 50)
            Input.KeyDown (k)
            if ~down & (k (KEY_DOWN_ARROW)| ((k (KEY_UP_ARROW) & makeMove (pr, pr, 1, 4)| k (KEY_LEFT_ARROW) & makeMove (px, px, -1, 99)| k (KEY_RIGHT_ARROW) & makeMove (px, px, 1, 99)) & false)) then
                loop
                    py -= 1
                    exit when overlap (0)
                    t := Time.Elapsed
                end loop
                py += 1
            end if
            down := k (KEY_DOWN_ARROW)| k (KEY_UP_ARROW)| k (KEY_LEFT_ARROW)| k (KEY_RIGHT_ARROW)
            xorp
            for i : 0 .. 231
                Draw.FillBox ((i mod 11) * 10, (i div 11) * 10, (i mod 11) * 10 + 10, (i div 11) * 10 + 10, sign (b (i div 11 + 3) & (1 shl (i mod 11 + 3))) * 7)
            end for
            View.Update
            xorp
        end loop
    end loop
    py += 1
    xorp
    for decreasing i : 23 .. 4
        lines += b (i) div 32760
        for j : i .. (b (i) div 32760) * 20
            b (j) := b (j + 1)
        end for
    end for
end loop
put "\n\n\n\n\n\n\tGAME OVER"

I wonder if it's possible to make it <= 50 lines Question

fishtastic> You have been awarded 283 bits


: