Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# KöMaL Problems in Informatics, February 2009

Show/hide problems of signs:

## Problems with sign 'I'

Deadline expired on March 16, 2009.

I. 205. A cellular automaton is a collection of identical cells. Every cell has a state which evolves in each simulation step according to a rule. A rule specifies the state of a cell in the next step based on the current state of the cell and its neighbours. The states of cells are updated simultaneously in each simulation step.

In our model, a one-dimensional cellular automaton is considered, where each cell has two states, 1 or 0. Each generation is displayed in one line. The state of a cell in the next step depends on the state of the cell and its two neighbours. The first and last cells in each generation are always 0.

In the figures, környezet'' is neighbourhood, vizsgált cella'' is the actual cell, állapot'' is state, while eredmény'' is the updated state.

The actual cell and its two neighbours can have 23=8 different states. In the example, Rule 30 is shown: the states in the neighbourhood specify the updated state of the actual cell in the next step.

There are altogether 28=256 rules. Rules are numbered according to the second line of this table: the updated states are interpreted as a binary number, for example 00011110 in binary is 30 in decimal.

The behaviour of a cellular automation is determined by both the initial state and the rule. The long-term behaviour of an automaton can be stable, periodic, random, but complex or self-similar patterns may also emerge.

Your task is to simulate 150 generations of a one-dimensional cellular automaton by using a spreadsheet application. You should use two sheets: sheet Rule'' should contain the description of the rule in cells A1:I2 in a similar format to the example above. The second Simulation'' sheet should contain consecutive generations in cells A1:ET150 by using a copyable formula. The first and last columns should always contain a 0. The first line contains the initial state. Column widths and heights of lines should be chosen so that cells are visible squares on the screen. Use conditional formatting for the graphics.

In the example (Minta''), Rule 30 is 30-as szabály'' and Rule 154 is 154-es szabály''.

The sheet (i205.xls, i205.ods, ...) together with a short documentation (i205.txt, i205.pdf, ...) should be submitted, also containing a brief description of your solution and the name and version number of the spreadsheet application. You should include an interesting initial state and rule as well.

(10 pont)

solution (in Hungarian), statistics

I. 206. Before the advent of graphical operating systems, ASCII animations, that is, movies consisting only of ASCII characters were quite popular. A program displays each frame consisting of ASCII characters on the screen, pauses for a given time period, clears the screen, then displays the next frame until it reaches the end of the movie file.

Write a program that is capable of displaying the ASCII movie from the input file. You should also make your own ASCII animation.

The command line argument of your program is the name of the file containing frames of the animation. The first line of the file contains 4 integers separated by a space. These describe the number of frames, the number of columns and rows of a frame, and the pause in milliseconds between two frames. The following lines then contain rows of the frames, consisting of spaces and other ASCII characters. The output of your program is the animation displayed on the screen.

In the example (Példa bemenet részlet''), the beginning of a movie file is shown.

You can use the file f1.dat to test your program.

The source code of your movie player (i206.pas, i206.cpp, ...), an animation (i206film.dat, i206film.txt, ...) created by you and a short documentation (i206.txt, i206.pdf, ...) should be submitted, also describing briefly how to create a movie and specifying the name of the developer environment to use.

(10 points: 5 points for the player and 5 for the movie)

(10 pont)

solution (in Hungarian), statistics

I. 207. Thanks to the successes of the national team, ice hockey is gaining popularity in Hungary. From the webpage of the Hungarian Ice Hockey Federation, you can download results of the matches in 2008 (www.icehockey.hu). (The file jeghoki.csv on our server also contains these data.)

1. Create a database named i207. The above table containing data about the matches should be imported as match'' into the database. The source file is a semicolon-separated text file.

2. After importing, the appropriate data format and key should be set.

Table: match (id, date, opponent, type, city, country, scoreh, scoreo)

You should create queries to solve the following problems. Try to implement each task by using a single SQL query (or an equivalent reformulation).

3. Determine the date when the Hungarian team won with the biggest difference in scores. Create a query to get the date, the name of the opponent and the result. If there is more than one answer, you can give any or all of them. (3winning)

4. Create a query to determine how many times the Hungarian team won in consecutive years. (4years)

5. Create a query to list when a given opponent was first defeated by the Hungarian team. (5first)

6. Create a query to list those opponents that were never defeated by the Hungarian team. Each opponent should be listed only once. (6notwon)

7. As for football, Austria was the most common opponent for Hungary. Is the situation similar in ice hockey? Make a query to list those opponents that were more common opponents than Austria. (7austria)

8. Create a single query to determine the number of matches in which the Hungarian team won, achieved a draw or lose. (8stat)

9. Create a query to list the matches played against Romania in chronological order. The first column is the number of the match, the next column is the date, then the city follows, then points scored by the Hungarian team, finally, points scored by the opponent are listed. (9romania)

The following example shows the first few lines of query 9romania.

The database (i207.odb, i207.mdb) or a text document (i207.txt, i207.pdf, ...) should be submitted, containing the creation of the table and SQL codes of the queries (arranged neatly), together with a short documentation (i207dok.txt, i207dok.pdf, ...), also describing the name and version number of the database application.

(10 pont)

solution (in Hungarian), statistics

## Problems with sign 'S'

Deadline expired on March 16, 2009.

S. 42. Create a program capable of playing the following variant of Tetris''.

The playing field is a grid consisting of unit squares. The left, right and bottom sides of the playing area are closed walls, only the upper part is open. Various shapes composed of unit squares fall down the playing field randomly, one by one, from infinite height, and the player has to stack these shapes. The aim is to properly position these shapes such that the height of this continuously growing tower is minimal.

A shape is properly positioned on the playing field, if

- it is disjoint from any other shapes, and if

- the bottom of at least one of its unit square components touches a previously positioned shape, or touches the bottom wall of the playing field, and if

- it is possible to position the shape as a composition of a rotation and horizontal translation (performed infinitely high above the bottom wall), then a vertical dropping, such that the current shape does not overlap with any other shapes already on the playing field during this operation.

Possible shapes are encoded by 6 letters (see the Figure).

During execution, your program interactively communicates with a main application via the standard input and output, by using newline-separated text messages. The main application is responsible for producing the next random shape and checking the answers. If an event happens, the main application notifies your program by sending a message on the standard input in the following syntax:

start <W>

o It is sent only once, at the beginning of the game, and gives the width of the playing area 3W32. This message should not be answered by your program.

item [ojlszi]

o A new shape encoded by one of the six letters o, j, l, s, z or i will arrive next. The answer by your program to this should be a pos message.

Your program should write only the following type of message on the standard output in the following syntax:

pos <position of the left side of the shape after rotation> <rotation\ anticlockwise in degrees>

o This is the expected answer to an item message. It describes the requested position of the actual shape: in which row to position its left side after the rotation (an integer between 1 and W-s+1, with s being the width of the shape after rotation), further, the angle of the rotation (being 0, 90, 180 or 270 degrees anticlockwise).

Your program gets a message from the standard input describing the next shape only after the position of the previous item has been written on the standard output. Always use the standard input and output (and not the keyboard or the screen). Always put a newline-character at the end of each message and clear the output buffer after the message has been sent. In case of Pascal, do not use the Crt module, and in case of C or C++, conio.h is not allowed.

The example (see the figure) contains a possible dialogue between your program and the main application (the answers of your program are in italics).

(10 pont)

solution (in Hungarian), statistics

\$Var(Body)