PROG0438 - Sleepwalker
Consider a building with a flat square roof having size $3^k \times 3^k$ ($k \in \mathbb{N_0}$) metres and sides parallel to north-south and east-west directions. The roof is covered with square tiles having sides of length 1 metre. One of the tiles has been removed, so that there is a hole in the roof big enough to fall in. The tiles form a rectangular mesh on the roof, so their positions may be specified with $(x, y)$ co-ordinates. The tile at the southwestern corner has co-ordinates $(1, 1)$. The first co-ordinate increases while going eastwards, and the second co-ordinate increases while going northwards.
A sleepwalker wanders across the roof, in each step moving from the tile he is standing on to the adjacent tile on the east (E), west (W), south (S) or north (N). The sleepwalker roof ramble starts from the southwestern corner tile. The description of his path is a word $d_k$ containing the letters N, S, E and W denoting respectively a step to the north, south, east and west. For $k = 1$ the word describing the path of the sleepwalker is
$d_1$ = EENNWSWN
For $k = 2$ the word describing the path of the sleepwalker is
| $d_2$ = | NNEESWSEENNEESWSEEEENNWSWNNEENNWSWNNEENN |
| WSWNWWWSSENESSSSWWNENWWSSWWNENWNEENNWSWN |
The following pictures shows how the sleepwalker would go across a roof of dimensions $3 \times 3$ (left) and $9 \times 9$ (right).
Generally, if $k \geq 1$ the description of a sleepwalker's path on a roof of dimension $3^{k+1} \times 3^{k+1}$ voor $k \geq 1$ is described by the word
$d_{k + 1}$ = $p_a(d_k)$ E $p_a(d_k)$ E $d_k$ N $d_k$ N $d_k$ W $p_c(d_k)$ S $p_b(d_k)$ W $p_b(d_k)$ N $d_k$
where functions $p_a$, $p_b$ en $p_c$ denote
the following permutations of the directions
| E | W | N | S | |
|---|---|---|---|---|
| $p_a$ | N | S | E | W |
| $p_b$ | S | N | W | E |
| $p_c$ | W | E | S | N |
We have for example that $p_a$(SEN) = WNE, $p_b$(SEN) = ESW and $p_c$(SEN) = NWS.
Assignment
We start observing the sleepwalker at the moment he stands on the tile at co-ordinates $(s_x, s_y)$. After how many steps will the sleepwalker fall into the hole made after removing the tile at co-ordinates $(g_x, g_y)$. In order to answer this question, the following procedure must be followed
- Write a function permutation that takes two string arguments. The first argument must be a word containing directions (a string that only contains the letters N, S, E and W). The second argument must be one of the letters a, b, or c. This letter indicates whether the function permutation must respectively return the result of the permutation $p_a$, $p_b$ or $p_c$.
- Write a function path that takes an integer $k \in \mathbb{N_0}$. The function must return a string that contains the word of directions that is followed by a sleepwalker on a roof having size $3^k \times 3^k$.
- Write a function sleepwalker that computes the number of steps that a sleepwalker will make before he falls into the hole. This function takes five arguments. The first argument is an integer $k \in \mathbb{N_0}$ that determines the size of the roof ($3^k \times 3^k$). The next two arguments respectively represent the co-ordinates $s_x$ and $s_y$ of the tile the sleepwalker is standing on at the moment the observation starts. The final two arguments are the co-ordinates $g_x$ and $g_y$ of the tile that has been removed.
Example
>>> permutation('SEN', 'a') 'WNE' >>> permutation('SEN', 'b') 'ESW' >>> permutation('SEN', 'c') 'NWS' >>> path(1) 'EENNWSWN' >>> path(2) 'NNEESWSEENNEESWSEEEENNWSWNNEENNWSWNNEENNWSWNWWWSSENESSSSWWNENWWSSWWNENWNEENNWSWN' >>> route = path(3) >>> print('\\n'.join(route[x:x + 80] for x in range(0, len(route), 80))) EENNWSWNNEENNWSWNNNNEESWSEENNEESWSEENNEESWSESSSWWNENWWWWSSENESSWWSSENESENNEESWSE EEENNWSWNNEENNWSWNNNNEESWSEENNEESWSEENNEESWSESSSWWNENWWWWSSENESSWWSSENESENNEESWS EENNEESWSEENNEESWSEEEENNWSWNNEENNWSWNNEENNWSWNWWWSSENESSSSWWNENWWSSWWNENWNEENNWS WNNNNEESWSEENNEESWSEEEENNWSWNNEENNWSWNNEENNWSWNWWWSSENESSSSWWNENWWSSWWNENWNEENNW SWNNNNEESWSEENNEESWSEEEENNWSWNNEENNWSWNNEENNWSWNWWWSSENESSSSWWNENWWSSWWNENWNEENN WSWNWSSWWNENWWSSWWNENWWWWSSENESSWWSSENESSWWSSENESEEENNWSWNNNNEESWSEENNEESWSESWWS SENESSWWSSENESSWWSSENESSSSWWNENWWSSWWNENWWSSWWNENWNNNEESWSEEEENNWSWNNEENNWSWNWSS WWNENWWWWSSENESSWWSSENESSSSWWNENWWSSWWNENWWSSWWNENWNNNEESWSEEEENNWSWNNEENNWSWNWS SWWNENWNNNEESWSEENNEESWSEEEENNWSWNNEENNWSWNNEENNWSWNWWWSSENESSSSWWNENWWSSWWNENWN EENNWSWN >>> sleepwalker(2, 3, 2, 7, 2) 20 >>> sleepwalker(2, 9, 6, 3, 7) 43 >>> sleepwalker(3, 1, 1, 1, 27) 728
Een flatgebouw heeft een plat dak met afmetingen $3^k \times 3^k$ ($k \in \mathbb{N_0}$) meter en zijden parallel met noordzuidelijke en oostwestelijke richtingen. Het dak is bedekt met vierkante tegels die zijden hebben van 1 meter. Eén van de tegels werd echter verwijderd, waardoor een gat in het dak is ontstaan dat groot genoeg is om erdoor te vallen. De tegels vormen een vierkant rooster op het dak, waardoor hun posities kunnen aangeduid worden aan de hand van $(x, y)$-coördinaten. De tegel in de zuidwestelijke hoek heeft coördinaten $(1, 1)$. De eerste coördinaat neemt toe als we in oostelijke richting gaan, en de tweede coördinaat neemt toe als we naar het noorden gaan.
Op het dak van het gebouw doolt een slaapwandelaar rond, die telkens wandelt naar een naburige tegel ten oosten (O), westen (W), zuiden (Z) of noorden (N) van de tegel waarop hij staat. De tocht van de slaapwandelaar start op de tegel in de zuidwestelijke hoek van het dak. Het traject dat de slaapwandelaar aflegt kan omschreven worden als een woord $d_k$ dat enkel opgebouwd is uit de letters N, Z, O en W die respectievelijk een stap naar het noorden, zuiden, oosten en westen aangeven. Voor $k = 1$ wordt het traject omschreven door het woord
$d_1$ = OONNWZWN
Voor $k = 2$ wordt het traject van de slaapwandelaar omschreven door het woord
| $d_2$ = | NNOOZWZOONNOOZWZOOOONNWZWNNOONNWZWNNOONN |
| WZWNWWWZZONOZZZZWWNONWWZZWWNONWNOONNWZWN |
Onderstaande afbeelding geeft het traject weer dat door een slaapwandelaar gevolgd wordt op een dak met afmetingen van $3 \times 3$ (links) en $9 \times 9$ (rechts).
In het algemene geval wordt het traject van een slaapwandelaar op een dak met afmetingen $3^{k+1} \times 3^{k+1}$ voor $k \geq 1$ omschreven door het woord
$d_{k + 1}$ = $p_a(d_k)$ O $p_a(d_k)$ O $d_k$ N $d_k$ N $d_k$ W $p_c(d_k)$ Z $p_b(d_k)$ W $p_b(d_k)$ N $d_k$
waarbij de functies $p_a$, $p_b$ en $p_c$ de
volgende permutaties van de richtingen aangeven
| O | W | N | Z | |
|---|---|---|---|---|
| $p_a$ | N | Z | O | W |
| $p_b$ | Z | N | W | O |
| $p_c$ | W | O | Z | N |
We hebben dan bijvoorbeeld dat $p_a$(ZON) = WNO, $p_b$(ZON) = OZW en $p_c$(ZON) = NWZ.
Opgave
We beginnen de slaapwandelaar te observeren op het ogenblik dat hij zich op de tegel met coördinaten $(s_x, s_y)$ bevindt. De vraag is hoeveel stappen de slaapwandelaar erover zal doen om in het gat te vallen dat ontstaan is doordat de tegel met coördinaten $(g_x, g_y)$ werd verwijderd. Om deze vraag te beantwoorden ga je als volgt te werk
- Schrijf een functie permutatie waaraan twee stringargumenten moeten doorgegeven worden. Het eerste argument moet een woord met richtingen voorstellen (een string die enkel bestaat uit de letters N, Z, O en W). Het tweede argument is ofwel de letter a, b, of c. Deze letter geeft aan of de functie permutatie respectievelijk het resultaat van de permutatie $p_a$, $p_b$ of $p_c$ moet teruggeven.
- Schrijf een functie traject waaraan een getal $k \in \mathbb{N_0}$ als argument moet doorgegeven worden. De functie moet een string als resultaat teruggeven, die het woord met richtingen voorstelt dat een slaapwandelaar aflegt op een dak met afmetingen $3^k \times 3^k$.
- Schrijf een functie slaapwandelaar die bepaalt hoeveel stappen een slaapwandelaar erover zal doen om in het gat te vallen. Aan deze functie moeten vijf argumenten doorgegeven worden. Het eerste argument is een getal $k \in \mathbb{N_0}$ op basis waarvan de afmeting van het dak ($3^k \times 3^k$) bepaald wordt. De volgende twee argumenten stellen respectievelijk de coördinaten $s_x$ en $s_y$ voor van de tegel waarop de slaapwandelaar zich bevindt bij de start van de observatie. De laatste twee argumenten stellen respectievelijk de coördinaten $g_x$ en $g_y$ voor van de tegel die werd verwijderd.
Voorbeeld
>>> permutatie('ZON', 'a') 'WNO' >>> permutatie('ZON', 'b') 'OZW' >>> permutatie('ZON', 'c') 'NWZ' >>> traject(1) 'OONNWZWN' >>> traject(2) 'NNOOZWZOONNOOZWZOOOONNWZWNNOONNWZWNNOONNWZWNWWWZZONOZZZZWWNONWWZZWWNONWNOONNWZWN' >>> route = traject(3) >>> print('\\n'.join(route[x:x + 80] for x in range(0, len(route), 80))) OONNWZWNNOONNWZWNNNNOOZWZOONNOOZWZOONNOOZWZOZZZWWNONWWWWZZONOZZWWZZONOZONNOOZWZO OOONNWZWNNOONNWZWNNNNOOZWZOONNOOZWZOONNOOZWZOZZZWWNONWWWWZZONOZZWWZZONOZONNOOZWZ OONNOOZWZOONNOOZWZOOOONNWZWNNOONNWZWNNOONNWZWNWWWZZONOZZZZWWNONWWZZWWNONWNOONNWZ WNNNNOOZWZOONNOOZWZOOOONNWZWNNOONNWZWNNOONNWZWNWWWZZONOZZZZWWNONWWZZWWNONWNOONNW ZWNNNNOOZWZOONNOOZWZOOOONNWZWNNOONNWZWNNOONNWZWNWWWZZONOZZZZWWNONWWZZWWNONWNOONN WZWNWZZWWNONWWZZWWNONWWWWZZONOZZWWZZONOZZWWZZONOZOOONNWZWNNNNOOZWZOONNOOZWZOZWWZ ZONOZZWWZZONOZZWWZZONOZZZZWWNONWWZZWWNONWWZZWWNONWNNNOOZWZOOOONNWZWNNOONNWZWNWZZ WWNONWWWWZZONOZZWWZZONOZZZZWWNONWWZZWWNONWWZZWWNONWNNNOOZWZOOOONNWZWNNOONNWZWNWZ ZWWNONWNNNOOZWZOONNOOZWZOOOONNWZWNNOONNWZWNNOONNWZWNWWWZZONOZZZZWWNONWWZZWWNONWN OONNWZWN >>> slaapwandelaar(2, 3, 2, 7, 2) 20 >>> slaapwandelaar(2, 9, 6, 3, 7) 43 >>> slaapwandelaar(3, 1, 1, 1, 27) 728
| Added by: | Peter Dawyndt |
| Date: | 2013-09-11 |
| Time limit: | 20s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS