PROG0445 - Wrong number

Steve "Woz" Wozniak — co-founder of Apple Computers — collected telephone numbers, amongst other things. His big dream was to get hold of a telephone number in which only one digit was repeated. However, for the largest part of his life, Silicon Valley did not have any zone codes of three equal digits. Therefore, Woz had to be satisfied with numbers like 221-111-1111.

When he was eavesdropping on the mobile telephone traffic, he noticed that a new zone code had been taken into use: 888. After months of administrative fuss and waiting he finally got hold of his number: 888-888-8888. It was his new mobile phone number and with that his most valuable collector's item. 

The number soon appeared to be useless. He received more than a hundred mistaken calls a day. At first, this amount of wrong connections seemed pretty inexplicable, given the fact that it was almost impossible to dial the number incorrectly. What was even more unusual was that no one could ever be heard on the other side of the connection. Just silence. Well, actually is was silence under various forms: death silence, sometimes the sound of a television in the background, or someone that was talking very quietly in English or in Spanish, or sometimes weird gargling sounds. Woz often kept listening, intrigued.

But one day, while he had his phone pressed to his ear, Woz clearly heard a woman's voice at a certain distance saying "Hey! What are you doing with that?". The receiver on the other side was torn away and the connection was broken. This was the solving piece of the puzzle. The hundreds of calls, the dead silence, the gargling sounds: babies. They had picked up the receiver and started pushing buttons on the bottom of the machine. And that made the same sound over and over: 'Beep beep beep beep beep beep beep beep beep beep." The American children had played their first prank, subconsciously. And the person who answered their calls was Woz.

This story contains a sense of justice being served, as Woz started his career as a prank caller and hacker of telephone systems. 

Assignment

To determine the chance that a baby coincidentally presses a certain telephone number, we have developed a score system for telephone numbers. The higher the score, the smaller the chance that that particular number will be called by accident. To calculate the score, we use the keyboard below. Here we have the rows and columns of the grid that is formed by the digits. The key 8, for example, is on row 2 and in column 1.

vingerbeweging
Keyboard of a mobile phone, of which we have numbered the rows and columns. 

Asked:

  • Write a function position to which a number $n \in \mathbb{N}$ must be given, to which applies that $0 \leq n < 10$. This number represents a key on the keyboard of a mobile phone. The function should print two integers, that respectively represent the number of the row and the number of the column of the key. Try to minimize the number of conditions that need to be tested to implement this function. 
  • Use the function position to write a function movement to which two numbers $n, m \in \mathbb{N}$ must be given, to which applies that $0 \leq n, m < 10$. These numbers represent two keys of the keyboard of a mobile phone. The function should print an integer that indicates how many positions at the least you should move your finger horizontally and vertically in order to move from one key to another. We assume you never move your finger diagonally. Every movement to another row or column is seen as a single movement. For example, to move from key 8 to key 1, you have to make one horizontal and two vertical moves. This is a total of three moves.
  • Use the function movement to write a function fingermovement. To this function, the string representation of a phone number should be given. The string may consist of a random sequence of characters, but only the digits of the string form the actual phone number. The function should print an integer, that represents the total amount of movements your fingers should do in order to dial the phone number. 

Example

>>> position(8)
(2, 1)
>>> position(0)
(3, 1)

>>> movement(8, 8)
0
>>> movement(8, 9)
1
>>> movement(8, 1)
3

>>> fingermovement('888-888-8888')
0
>>> fingermovement('053/67.83.47')
16

Steve "Woz" Wozniak — medeoprichter van Apple Computers — verzamelde onder andere telefoonnummers. Zijn grote droom was om een telefoonnummer te bemachtigen waarin slechts één cijfer herhaald wordt. Het grootste deel van zijn leven had Silicon Valley echter geen zonenummers met drie gelijke cijfers. Dus moest Woz zich tevreden stellen met telefoonnummers zoals 221-111-1111.

Toen hij op een dag echter het mobiele telefoonverkeer aan het afluisteren was, viel hem op dat er een nieuw zonenummer in gebruik genomen was: 888. Na maanden van administratieve rompslomp en wachten kreeg hij het uiteindelijk in handen: 888-888-8888. Dit was zijn nieuw mobiel telefoonnummer en meteen zijn meest waardevolle collectors item.

Al snel bleek echter dat het telefoonnummer zo goed als onbruikbaar was. Hij ontving immers meer dan honderd verkeerd verbonden oproepen per dag. Een dergelijk aantal verkeerde oproepen was op het eerste gezicht vrij onverklaarbaar, gegeven het feit dat het quasi onmogelijk is om het nummer verkeerd in te voeren. Wat het nog vreemder maakte is dat er nooit iemand te horen was aan de andere kant van de lijn. Enkel stilte. Wel, eigenlijk stilte in verschillende vormen, gaande van doodse stilte, soms met het geluid van een televisie in de achtergrond, of iemand die zachtjes aan het praten was in het Engels of het Spaans, of bizarre gorgelende geluiden. Woz bleef vaak geïntrigeerd luisteren.

Maar op een dag had hij de telefoon aan zijn oor gedrukt, toen Woz duidelijk een vrouwenstem op een zekere afstand hoorde zeggen "Hé, wat ben je daarmee aan het doen?". De hoorn aan de andere kant werd weggerukt en de verbinding werd verbroken. Dit deed de puzzel in elkaar vallen. De honderden gesprekken, de doodse stilte, de gorgelende geluiden: baby's. Ze hadden de hoorn opgenomen en waren een toets aan het indrukken aan de onderkant van het toestel. Opnieuw en opnieuw. En het maakte zelfs een geluid: "Biep biep biep biep biep biep biep biep biep biep." De Amerikaanse kinderen haalden zo onbewust hun eerste kwajongensstreeks uit, en de persoon die hun telefoontjes beantwoordde was Woz.

Woz startte zijn carrière als telefoongrappenmaker en hacker van telefoonsystemen, dus zit er ergens wel een grond van rechtvaardigheid in dit verhaal.

Opgave

Om te bepalen hoe groot de kans is dat een baby toevallig een bepaald telefoonnummer zal intoetsen, hebben we een scoresysteem voor telefoonnummers ontwikkeld. Hoe hoger de score, hoe kleiner de kans dat het nummer puur toevallig zal opgebeld worden. Om de score te berekenen, gaan we uit van onderstaand toetsenbord van een mobiel telefoontoestel. Hierbij hebben we de rijen en kolommen van het rooster dat gevormd wordt door de toetsen op de aangegeven manier genummerd. De toets 8 staat bijvoorbeeld op rij 2 en kolom 1.

vingerbeweging
Toetsenbord van een mobiel telefoontoestel, waarbij we de rijen en kolommen genummerd hebben.

Gevraagd wordt:

  • Schrijf een functie positie waaraan een getal $n \in \mathbb{N}$ moet doorgegeven worden, waarvoor geldt dat $0 \leq n < 10$. Dit getal stelt een toets op het toetsenbord van een mobiele telefoontoestel voor. De functie moet twee natuurlijke getallen teruggeven, die respectievelijk het rijnummer en het kolomnummer van de toets op het toetsenbord voorstellen. Probeer het aantal voorwaarden die moeten getest worden om deze functie te implementeren tot een minimum te herleiden.
  • Gebruik de functie positie om een functie verplaatsing te schrijven waaraan twee getallen $n, m \in \mathbb{N}$ moeten doorgegeven worden, waarvoor geldt dat $0 \leq n, m < 10$. Deze getallen stellen twee toetsen op het toetsenbord van een mobiel telefoontoestel voor. De functie moet een natuurlijk getal teruggeven, dat aangeeft hoeveel posities je je vinger minimaal horizontaal en verticaal moet verplaatsen om van de ene toets naar de andere toets op het toetsenbord te bewegen. We gaan er hierbij van uit dat je je vinger nooit diagonaal beweegt. Elke verplaatsing naar een andere rij of kolom wordt als één enkele verplaatsing geteld. Om van toets 8 naar toets 1 te bewegen, moet je bijvoorbeeld één horizontale verplaatsing en twee verticale verplaatsingen maken, goed voor een totaal van drie verplaatsingen.
  • Gebruik de functie verplaatsing om een functie vingerbeweging te schrijven. Aan deze functie moet de stringvoorstelling van een telefoonnummer doorgegeven worden. Deze string mag bestaan uit een willekeurige reeks karakters, maar enkel de cijfers van de string vormen het eigenlijke telefoonnummer. De functie moet een natuurlijk getal teruggeven, dat de totale verplaatsing voorstelt die je vingers moeten maken als achtereenvolgens alle cijfers op het toetsenbord van een mobiele telefoon intoetst worden.

Voorbeeld

>>> positie(8)
(2, 1)
>>> positie(0)
(3, 1)

>>> verplaatsing(8, 8)
0
>>> verplaatsing(8, 9)
1
>>> verplaatsing(8, 1)
3

>>> vingerbeweging('888-888-8888')
0
>>> vingerbeweging('053/67.83.47')
16

Added by:Peter Dawyndt
Date:2014-01-20
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:PY_NBC
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.