# Exercises

## Dynamic programming

### Pascal triangle

Write a function that returns the nth row of the Pascal triangle as a list.

### Knight

Let's say that you have a knight on the chessboard. Calculate how many steps does it take to optimally reach the other places on the board.

Write a function knight(x,y) where the parameters are the x, y coordinates of the initial place. Return an 8-by-8 table of integers containing the minimum number of steps to reach that position. For example the initial state should have 0 on it.

Use a dynamic programming table!

### Paint Bucket Tool

Save the following "text" as a list of lists in python!

Write a function fill(x,y) which fills a territory starting with the given coordinates, like the bucket tool in Paint.

Starting from the (x, y) coordinate replace . with #, if you encounter a # then stop. Do this recursively for every neighbor of the given point. This will fill out an enclosed territory.

```.....................................
...#######################...........
...#.....................#...........
...#.....................#...........
...#.....................#...........
...#.....................#...........
...#.....................#...........
...#.....................#######.....
...###.................##......#.....
...#..##.............##........#.....
...#....##.........##..........#.....
...#......##.....##............#.....
...#........#####..............#.....
...#........#..................#.....
...#.......##..................#.....
...#.....##....................#.....
...#...##......................#.....
...#############################.....
.....................................
.....................................
.....................................
.....................................
```

## Állapotgép

### Zárójelek

Adott egy sztring. Cseréljük le azokat a karaktereket \$ jelre, amelyek zárójelek között vannak (a zárójeleket is beleértve)! Figyelem, a zárójelek lehetnek egymásba ágyazva is, tehát, ha a bemeneti sztring (xc)aa(c(b)), akkor a kimenet \$\$\$\$aa\$\$\$\$\$\$ legyen!

### Billentyűk

Töltsük le az alábbi adatfile-t: raw_data.txt

A file tartalma egy rövid szöveg begépelése alatt történt billentyű lenyomásokat kódolja. Az érdekes rész az 5. sortól kezdődik:

• Az első szó az esemény, a számunkra érdekesek a keydown és keyup események, ezek rendre a billentyű lenyomás és felengedés.
• A következő három szám a karakter kódja, innen a 2. (azaz a sorban 3. elem) a megbízható, használjuk ezt.
• Az igaz-hamis érték a kis / nagy betűre vonatkozik, de mi ezzel most ne foglalkozzunk.
• Az utolsó elem az érdekes még számunkra, ez az esemény időpontja (pontosan az 1970 január 1. óta eltelt milliszekundumok).

A feladat az, hogy úgy dolgozzuk fel ezt az adathalmazt, hogy a billentyű lenyomások és felengedések közti időt megkapjuk. Csak egy ilyen idősor érdekel minket, a sorrend legyen a lenyomás pillanata szerint. Például az eleje így nézne ki:

```145 80 74 ...
```

A 145-öt az alábbi két sorból kapjuk:

```keydown 16 16 0 true 1444121075394
keyup 16 16 0 false 1444121075539
```

majd a 80-at:

```keydown 84 84 0 true 1444121075462
keyup 84 84 0 false 1444121075542
```

a 74-et:

```keydown 72 72 0 false 1444121075693
keyup 72 72 0 false 1444121075767
```

Az így kapott számsort írjuk egy kimenet.txt file-ba!

Segítség:

Rengeteg módon megoldható a feladat, ez csak egy ötlet:

• Tároljuk a már lenyomott és felengedésre váró gombokat egy szótárban.
• Ha megérkezett egy várt gomb felengedése akkor mentsük a lenyomás időtartamát, majd töröljük a szótárból.

Bónusz: rekonstruáljuk a beírt szöveget. Vigyázat, ez a file tartalmazza a backspace, SHIFT, stb. billentyűk lenyomását is.