Informatics2-2018/Lab09

A MathWikiből
(Változatok közti eltérés)
(Új oldal, tartalma: „previous up next =Exercises= == Dynamic programming== ===Pascal triangle=== Write a funct…”)
 
(Keystrokes)
 
(egy szerkesztő 6 közbeeső változata nincs mutatva)
6. sor: 6. sor:
 
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===
+
===Paint Bucket Tool===
Let's say that you have a bishop on the chessboard. Calculate how many steps does it take to optimally reach the other places at the board.
+
Save the following "text" as a list of lists in python!
  
Write a function '''knight(x,y)''' where the parameters are ''(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!
 
 
===Zárt terület kifestése===
 
Olvassuk be az alábbi "szöveget" listák listájába (minden karakter egy elem): mentsük le egy fájlba kézzel, majd nyissuk meg a fájlt Pythonnal! Írjunk egy fill(x,y) függvényt, ami ugyanazt csinálja, mint a Paint kitöltő funkciója! Az (x,y) pontból kiindulva a . helyére # jelet tesz, amíg a # jel által jelölt falba nem ütközik! A módszer rekurzív: kifestjük az (x,y) pontot, majd a szomszédait, ha azok nem # jelek. Hívjuk meg a szomszédokra (akik nem # jelek) a függvényt rekurzívan. Ha nincs kit kiszínezni, akkor álljunk meg!
 
 
  .....................................
 
  .....................................
 
  ...#######################...........
 
  ...#######################...........
40. sor: 32. sor:
 
  .....................................
 
  .....................................
  
== Állapotgép ==
+
Write a function '''fill(x,y)''' which fills a territory starting with the given coordinates, like the bucket tool in Paint.
  
=== Zárójelek ===
+
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.
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 ===
+
===Knight===
Töltsük le az alábbi adatfile-t: [http://sandbox.hlt.bme.hu/~gaebor/ea_anyag/Info2/raw_data.txt raw_data.txt]
+
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!
  
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:
+
== Finite-state machine==
  
* 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.
+
=== Parenthesis ===
* 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.
+
Given a string, replace the enclosed parts of the string with a '''$''' character.
* Az igaz-hamis érték a kis / nagy betűre vonatkozik, de mi ezzel most ne foglalkozzunk.
+
A formula is enclosed if it is surrounded by parenthesis. For example:
* 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:
+
(xc)aa(c(b)) -> $$$$aa$$$$$$
  
145 80 74 ...
+
Note that the parenthesis can be enclosed into each other.
  
A 145-öt az alábbi két sorból kapjuk:
+
=== Keystrokes ===
keydown 16 16 0 true 1444121075394
+
Download the following text file: [http://sandbox.hlt.bme.hu/~gaebor/ea_anyag/Info2/raw_data.txt raw_data.txt]
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!
+
This file contains keystroke data when someone was typing.
 +
The interesting part starts from the 5<sup>th</sup> line:
  
'''Segítség:'''
+
* 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.
  
Rengeteg módon megoldható a feladat, ez csak egy ötlet:
+
The exercise is to process the keystrokes and reconstruct the typed text.
* Tároljuk a már lenyomott és felengedésre váró gombokat egy szótárban.
+
Mind that there is a SHIFT key in the data.
* 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.
+
'''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

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!
  • You can see the keycodes here

previous up next

Személyes eszközök