|
|
4. sor: |
4. sor: |
| == Dynamic programming== | | == Dynamic programming== |
| | | |
− | === Euclidean algorithm === | + | ===Deep Sum=== |
− | Implement the greatest common divisor (gcd) function using the [https://en.wikipedia.org/wiki/Euclidean_algorithm Euclidean algorithm]. Implement it with and without recursion!
| + | |
| | | |
− | ===Paint Bucket Tool=== | + | ===Palindrome=== |
− | Download the [http://sandbox.hlt.bme.hu/~gaebor/ea_anyag/Info2/picture.txt picture.txt] file and read it as a list of lists in python!
| + | |
| | | |
− | .....................................
| + | ===Factorial=== |
− | ...#######################...........
| + | |
− | ...#.....................#...........
| + | |
− | ...#.....................#...........
| + | |
− | ...#.....................#...........
| + | |
− | ...#.....................#...........
| + | |
− | ...#.....................#...........
| + | |
− | ...#.....................#######.....
| + | |
− | ...###.................##......#.....
| + | |
− | ...#..##.............##........#.....
| + | |
− | ...#....##.........##..........#.....
| + | |
− | ...#......##.....##............#.....
| + | |
− | ...#........#####..............#.....
| + | |
− | ...#........#..................#.....
| + | |
− | ...#.......##..................#.....
| + | |
− | ...#.....##....................#.....
| + | |
− | ...#...##......................#.....
| + | |
− | ...#############################.....
| + | |
− | .....................................
| + | |
− | .....................................
| + | |
− | .....................................
| + | |
− | .....................................
| + | |
| | | |
− | Write a function '''fill(x,y)''' which fills a territory starting with the given coordinates, like the bucket tool in Paint.
| + | ===Sum Digit=== |
| | | |
− | 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.
| + | ===Sum Series=== |
| | | |
− | ===Knight=== | + | ===Power=== |
− | 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.
| + | ===Target=== |
− | 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== | + | |
− | === 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]
| + | |
| | | |
| + | == Finite State Machine== |
| === Parenthesis === | | === Parenthesis === |
| Given a string, replace the enclosed parts of the string with a '''$''' character. | | Given a string, replace the enclosed parts of the string with a '''$''' character. |
75. sor: |
24. sor: |
| | | |
| (xc)aa(c(b)) -> $$$$aa$$$$$$ | | (xc)aa(c(b)) -> $$$$aa$$$$$$ |
− |
| |
− | Note that the parenthesis can be enclosed into each other.
| |