Informatics2-2018/Lab09
(→Zárt terület kifestése) |
(→Keystrokes) |
||
(egy szerkesztő 4 közbeeső változata nincs mutatva) | |||
5. sor: | 5. sor: | ||
===Pascal triangle=== | ===Pascal triangle=== | ||
Write a function that returns the ''n''<sup>th</sup> row of the Pascal triangle as a list. | Write a function that returns the ''n''<sup>th</sup> row of the Pascal triangle as a list. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
===Paint Bucket Tool=== | ===Paint Bucket Tool=== | ||
Save the following "text" as a list of lists in python! | Save the following "text" as a list of lists in python! | ||
− | |||
− | |||
− | |||
− | |||
..................................... | ..................................... | ||
45. sor: | 32. sor: | ||
..................................... | ..................................... | ||
− | + | 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. | |
− | + | ||
− | === | + | ===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! | ||
− | + | == Finite-state machine== | |
− | + | === Parenthesis === | |
− | + | Given a string, replace the enclosed parts of the string with a '''$''' character. | |
− | + | A formula is enclosed if it is surrounded by parenthesis. For example: | |
− | + | ||
− | + | (xc)aa(c(b)) -> $$$$aa$$$$$$ | |
− | + | Note that the parenthesis can be enclosed into each other. | |
− | + | === Keystrokes === | |
− | + | Download the following text file: [http://sandbox.hlt.bme.hu/~gaebor/ea_anyag/Info2/raw_data.txt raw_data.txt] | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | This file contains keystroke data when someone was typing. | |
+ | The interesting part starts from the 5<sup>th</sup> line: | ||
− | ''' | + | * The first column is an event: '''keydown''' or '''keyup''' (others are irrelevant now) |
+ | * The next three numbers encode the key, actually the second one is important (third column). | ||
+ | * The fourth column refers to capital or lowercase, but thats also irrelevant now. | ||
+ | * The last one is a timestamp, the number of milliseconds elapsed since January 1<sup>st</sup>, 1970. | ||
− | + | The exercise is to process the keystrokes and reconstruct the typed text. | |
− | + | Mind that there is a SHIFT key in the data. | |
− | + | ||
− | ''' | + | '''Hint:''' |
+ | * Store a dictionary of keys which are pressed at a given time. | ||
+ | * if a key is released, and it was in the dictionary, then that letter was entered. | ||
+ | ** in this case, erase that key from the dictionary. | ||
+ | * store the state of the SHIFT key (up or down) | ||
+ | * There is also a BACKSPACE key! | ||
+ | * You can see the [https://www.w3schools.com/jsref/tryit.asp?filename=tryjsref_event_key_keycode2 keycodes here] | ||
[[Informatics2-2018/Lab08|previous]] [[Informatics2-2018|up]] [[Informatics2-2018/Lab10|next]] | [[Informatics2-2018/Lab08|previous]] [[Informatics2-2018|up]] [[Informatics2-2018/Lab10|next]] |
A lap jelenlegi, 2018. május 3., 08:44-kori változata
Tartalomjegyzék |
Exercises
Dynamic programming
Pascal triangle
Write a function that returns the nth row of the Pascal triangle as a list.
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.
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!
Finite-state machine
Parenthesis
Given a string, replace the enclosed parts of the string with a $ character. A formula is enclosed if it is surrounded by parenthesis. For example:
(xc)aa(c(b)) -> $$$$aa$$$$$$
Note that the parenthesis can be enclosed into each other.
Keystrokes
Download the following text file: raw_data.txt
This file contains keystroke data when someone was typing. The interesting part starts from the 5th line:
- The first column is an event: keydown or keyup (others are irrelevant now)
- The next three numbers encode the key, actually the second one is important (third column).
- The fourth column refers to capital or lowercase, but thats also irrelevant now.
- The last one is a timestamp, the number of milliseconds elapsed since January 1st, 1970.
The exercise is to process the keystrokes and reconstruct the typed text. Mind that there is a SHIFT key in the data.
Hint:
- Store a dictionary of keys which are pressed at a given time.
- if a key is released, and it was in the dictionary, then that letter was entered.
- in this case, erase that key from the dictionary.
- store the state of the SHIFT key (up or down)
- There is also a BACKSPACE key!
- You can see the keycodes here