## PROG0438 - Sleepwalker

no tags

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).

The path followed by a sleepwalker on a roof of dimensions $3 \times 3$ (left) and $9 \times 9$ (right). The right picture also shows the tile at which the observation starts and the tile that has been removed. The sleepwalker takes exactly 20 steps to the hole from the moment the observation starts.

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).

Het traject dat door een slaapwandelaar wordt afgelegd op een dak met afmetingen $3 \times 3$ (links) en $9 \times 9$ (rechts). In het tweede geval worden de coördinaten aangegeven van het moment waarop we de slaapwandelaar beginnen te volgen en van de plaats op het dag waar een tegel ontbreekt. Vanaf de start van de observatie doet de slaapwandelaar er dan exact 20 stappen over om in het gat te vallen.

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