Informatics2-2018/Lab09

A MathWikiből
(Változatok közti eltérés)
a (Paint Bucket Tool)
a
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.
 
===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===
 
===Paint Bucket Tool===
44. sor: 35. sor:
  
 
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.
 
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==
 
== Finite-state machine==

A lap 2018. április 18., 10:03-kori változata

previous up next

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!

previous up next

Személyes eszközök