SPOJ.com - Problem PROG0579

PROG0579 - Ergonomics

We've been making things awfully hard on our spirits. People often make use of an ouija board to communicate with the dead. Ouija consists of a planchette (a small heart-shaped piece of wood or plastic) as a movable indicator and a flat board marked with the letters of the alphabet, the numbers 0-9 and various words, symbols and graphics. Participants place their fingers on the planchette, and it is moved about the board to spell out words that answer questions asked to the spirits. Paranormal and supernatural beliefs associated with ouija have been harshly criticized by the scientific community, since they are characterized as pseudoscience. The action of the board can be parsimoniously explained by unconscious movements of those controlling the pointer, a psychophysiological phenomenon known as the ideomotor effect.

The standard ouija board lays out the alphabet in two stacked rows, which means it's easy for the dead to tell us about FEEDERS, but terribly hard to refer to LAYAWAY, even though these words are equally long.

In the interests of better communication, Eric Iverson made a study about the level of difficulty in spelling certain words. Using an image of the ouija bord, he determined the distance the planchette would have to travel in order to spell out various English words. The results are dismaying: the most exhausting four-letter word (MAMA) requires fully 17 times as much travel as the simple FEED. Longer words are more consistent: the hardest 23-letter word (DISESTABLISMENTARIANISM) requires little more work than the easiest (ELECTROENCEPHALOGRAPHIC). But do dead people have that kind of stamina?

What's the answer? Iverson experimented with different layouts and found a hexagonal grid that minimizes the average travel distance for a typical word (Iverson, 2005). Even rearranging the letters on a standard board to

ZXVGINAROFUPQ
JKWCHTESDLMYB

rather than the standard alphabet increases efficiency by about a third. Now maybe we can have some better conversations.

Assignment

In this assignment we use the positioning of the letters on the standard ouija board. This means that the letters are layed out in alphabetic order across two rows and thirteen columns, where we index the rows and columns in the following way.

The distance the planchette has to travel from one letter to another letter, is expressed as the total number of horizontal and vertical movements it has to make to neighbouring letters. For example, to move the planchette from the letter D to the letter U, 5 neighbouring movements have to be made. As a result, this distance measure does not take into account the possibility to make diagonal moves. Your task:

Write a function position that takes a letter as its argument. The function must return two integers, that respectively indicate the index of the row and the column where the letter is found on the ouija board.
Write a function shift that takes two letters as its arguments. The function must return the total number of horizontal and vertical movements the planchette has to make to neighbouring letters, in order to travel from the first letter to the second letter on the standard ouija board. This does not take into account the possibility to make diagonal moves.
Write a function ergonomics that takes a single string argument. The function may assume that this string only contains letters. The function must return the total distance the planchette has to travel to visit all letters of the given string in succession, starting at the first letter of the string.

None of these functions may make distinction between uppercase and lowercase letters.

Example

>>> row, col = position('K')
>>> row
0
>>> col
10
>>> row, col = position('q')
>>> row
1
>>> col
3

>>> shift('K', 'q')
8
>>> shift('f', 'e')
1

>>> ergonomics('FEED')
2
>>> ergonomics('MAMA')
36
>>> ergonomics('feeders')
5
>>> ergonomics('layaway')
67
>>> ergonomics('disestablismentarianism')
113
>>> ergonomics('electroencephalographic')
108

Resources

Iverson E (2005). Traveling Around the Ouija Board. Word ways 38(3), 174-177.

We hebben de dingen altijd al verschrikkelijk lastig gemaakt voor onze nabestaanden. Bij het oproepen van geesten wordt doorgaans gebruik gemaakt van een ouijabord bestaande uit een plankje op wieltjes en een speelvlak waarop letters en veelgebruikte woorden staan afgebeeld. Wanneer de deelnemers gezamenlijk het plankje over de letters bewegen, kunnen antwoorden ontstaan op vooraf gestelde vragen. Doordat iedereen tegelijkertijd aan het spel deelneemt, is het nooit duidelijk van wie de antwoorden precies vandaan komen.

Op een standaard ouijabord staan de letters in alfabetische volgorde verdeeld over twee rijen, waardoor het bijvoorbeeld weinig moeite vraagt om het woord EERST te spellen, maar veel meer inspanning vraagt om het woord VAZAL te spellen, ondanks het feit dat deze twee woorden evenveel letters tellen.

Om onze communicatie met geesten te kunnen verbeteren, voerde Eric Iverson in 2005 een studie uit naar de moeilijkheidsgraad bij het spellen van woorden. Hiervoor gebruikte hij de afbeelding van een ouijabord en bepaalde de afstand waarover het plankje moet verplaatst worden om de letters van verschillende Engelse woorden te spellen. De resultaten waren onthutsend: MAMA is het vierletterwoord dat het meeste inspanning vraagt, met een totale verplaatsing die 17 keer zo groot is als het minst vermoeiende vierletterwoord FEED. Het moeilijkste 23-letterwoord (DISESTABLISMENTARIANISM) vereist dan weer niet zoveel meer inspanning dan het makkelijkste (ELECTROENCEPHALOGRAPHIC). Maar hebben dode mensen wel het vereiste uithoudingsvermogen om dergelijke lange woorden te vormen?

Wat is het antwoord? Iverson experimenteerde met verschillende layouts en ontdekte dat de totale verplaatsing die nodig is om een woord te spellen kan geminimaliseerd worden door de letters in de vorm van een honingraat te rangschikken (Iverson, 2005). Zelfs het herschikken van de letters op een standaard ouijabord naar

ZXVGINAROFUPQ
JKWCHTESDLMYB

in plaats van de alfabetische volgorde van de letters aan te houden, verhoogt de efficiëntie reeds met een derde. Wellicht zullen we hierdoor in de toekomst betere gesprekken kunnen voeren met de doden.

Opgave

In deze opgave maken we gebruik van de positionering van de letters op een standaard ouijabord. Hierbij worden de letters in alfabetische volgorde uitgeschreven over twee rijen en dertien kolommen, waarbij we de rijen en kolommen op de volgende manier nummeren.

De afstand die het plankje moet afleggen om een verplaatsing te maken van een letter naar een andere letter, drukken we uit als het aantal horizontale en verticale verplaatsingen die moeten gemaakt worden naar naburige letters. Om het plankje bijvoorbeeld te verplaatsen van de letter D naar de letter U, moeten 5 naburige verplaatsingen gemaakt worden. Hierbij houden we dus geen rekening met de mogelijkheid om schuine verplaatsingen te maken. Gevraagd wordt:

Schrijf een functie positie waaraan een letter moet doorgegeven worden. De functie moet twee integers teruggeven, die respectievelijk de rij- en de kolomindex van de gegeven letter op het standaard ouijabord aangeven.
Schrijf een functie verschuiving waaraan twee letters moeten doorgegeven worden. De functie moet het totaal aantal horizontale en verticale verplaatsingen teruggeven die het plankje moet maken naar naburige letters om van de eerste letter naar de tweede letter te bewegen op een standaard ouijabord. Hierbij mag dus geen rekening gehouden worden met de mogelijkheid om schuine verplaatsingen te maken.
Schrijf een functie ergonomie waaraan een string moet doorgegeven worden. De functie mag ervan uitgaan dat de string enkel uit letters bestaat. De functie moet de totale afstand teruggeven die het plankje moet maken om naar de opeenvolgende letters van de gegeven string te bewegen, als het plankje vertrekt vanaf de eerste letter van de gegeven string.

Geen enkele van deze functies mag onderscheid maken tussen hoofdletters en kleine letters.

Voorbeeld

>>> rij, kolom = positie('K')
>>> rij
0
>>> kolom
10
>>> rij, kolom = positie('q')
>>> rij
1
>>> kolom
3

>>> verschuiving('K', 'q')
8
>>> verschuiving('f', 'e')
1

>>> ergonomie('EERST')
3
>>> ergonomie('VAZAL')
46
>>> ergonomie('feestsfeer')
8
>>> ergonomie('vakdiploma')
83
>>> ergonomie('verantwoordelijkheidsgebieden')
90
>>> ergonomie('chloorfluorkoolstofverbinding')
146

Bronnen

Iverson E (2005). Traveling Around the Ouija Board. Word ways 38(3), 174-177.

Submit solution!

Added by:	Peter Dawyndt
Date:	2015-10-17
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC