Informatics 1

Multiple choice: which of the following equations are correct?

1. $6 \times 9 = 54$
2. $6 \times 9 = 46$
3. $6 \times 9 = 42$
4. $6 \times 9 = 39$

You may probably be surprised when we state that all of them are correct, as long as they are evaluated in the correct numeral system. The decimal system is the most commonly used numeral system in the Western world. In this system, the digits of a number have a numerical value that is a power of 10. As such, the number $abc$ is interpreted as $c$ + $10 \times b$ + $10^2 \times a$ and the ten digits $0\ldots 9$ are used. In the binary numeral system, numerical values are powers of two and only the digits $0$ and $1$ are used. Hence, the number $abc$ is interpreted in the binary numeral system (base 2) as $c$ + $2 \times b$ + $2^2 \times a$. In numeral systems with base $10 < b \leq 36$, aside from the arabic digits $0, 1, \ldots, 9$ also the letters of the alphabet $A, B, \ldots, Z$ are used as digits. The latter then correspond to the values $10, 11, \ldots, 35$. In this case, no distinction is made between upper case and lower case letters. 

When we now return to the equations above, we see that the second equation is valid in the numeral system with base 12, the third in the numeral system with base 13 and the fourth in the numeral system with base 15.

The fact that $6 \times 9 = 42$ is a valid equation in the numeral system with base 13 is well-known among science fiction fans that have read the books in "The Hitchhiker's Guide to the Galaxy" series (or have watched the movies). In this comic series by Douglas Adams, a group of hyper-intelligent pan-dimensional beings had built a supercomputer — Deep Tought — that was demanded to learn the Answer to the Ultimate Question of Life, the Universe and Everything. After having computed for 7½ million years, the supercomputer finally came up with the answer, which turned out to be $42$. Deep Thought pointed out that the answer seems meaningless because the beings who instructed it never actually knew what the Question was.

When asked to produce The Ultimate Question, Deep Thought says that it cannot; however, it can help to design an even more powerful computer that can. This new computer will incorporate living beings into the "computational matrix" and will run for ten million years. It is revealed as being the planet Earth, with its pan-dimensional creators assuming the form of mice to observe its running. The process is hindered after eight million years by the unexpected arrival on Earth of the Golgafrinchans and then is ruined completely, five minutes before completion, when the Earth is destroyed by the Vogons to make way for a new Hyperspace Bypass. In The Restaurant at the End of the Universe, this is revealed to have been a ruse: the Vogons had been hired to destroy the Earth by a consortium of psychiatrists, led by Gag Halfrunt, who feared for the loss of their careers when the meaning of life became known.

Lacking a real question, the mice decide not to go through the whole thing again and settle for the out-of-thin-air suggestion "How many roads must a man walk down?" from Bob Dylan's song "Blowin' in the Wind". At the end of the story, Arthur Dent, having escaped the Earth's destruction, potentially has some of the computational matrix in his brain. He attempts to discover The Ultimate Question by extracting it from his brainwave patterns, as abusively suggested by Ford Prefect, when a Scrabble-playing caveman spells out forty two. Arthur pulls random letters from a bag, but only gets the sentence "What do you get if you multiply six by nine?"

"Six by nine. Forty two."
"That's it. That's all there is."
"I always thought something was fundamentally wrong with the universe"

Six times nine is actually fifty-four. The program on the "Earth computer" should have run correctly, but the unexpected arrival of the Golgafrinchans on prehistoric Earth caused input errors into the system — computing (because of the garbage in, garbage out rule) the wrong question — the question in Arthur's subconscious being invalid all along. Some readers noticed that $(6 \times 9 = 42)_{13}$ (using base 13). Douglas Adams later joked about this observation, saying, "I may be a sorry case, but I don't write jokes in base 13."

Assignment

The goal of this exercise is to find the smallest possible base $b \leq 36$ for which a given equation is valid. You may assume that equations only contain digits, brackets, + and *. In order to do so, you should proceed as follows:

• Write a function evaluation that takes two arguments. The first argument is a string describing a mathematical expression (e.g. 14 * 3). The second argument indicates the base of the numeral system in which the expression must be evaluated. The function must return the decimal value that results from evaluating of the expression, where each number of the expression is interpreted in the numeral system with base $b$.
• Use the function evaluation to write a function numeralSystem that takes the string representation of an equation. Both the left hand side and right hand side of this equation are expressions that are composed of summations and multiplications. The function must return that integer $b \leq 36$ that is the smallest base of the numeral system in which the equation is valid.

Preparation

Python has a built-in function eval that can be used to evaluate the string representation of an expression that is passed as an argument to the function. This evaluation function always interprets the expression in the decimal numeral system. The built-in function int can be used to convert the string representation of an integer in a numeral system with base $b$ into the corresponding integer in the decimal numeral system. Use the optional second argument (base) to pass the base of the numeral system to the function int.

>>> eval('12 * 3 + 6')
42
>>> int('2C', base=15)
42

Example

>>> evaluation('6 * 9', 13)
54
>>> evaluation('42', 13)
54
>>> evaluation('17 + 33 * 56', 23)
8742
>>> evaluation('41 * 42', 23)
8742

>>> numeralSystem('6 * 9 = 42')
13
>>> numeralSystem('17 + 33 * 56 = 41 * 42')
23

Multiple choice: welke van de volgende vergelijkingen zijn juist?

1. $6 \times 9 = 54$
2. $6 \times 9 = 46$
3. $6 \times 9 = 42$
4. $6 \times 9 = 39$

Je zal misschien vreemd opkijken als we zeggen dat elk van deze vergelijkingen correct is, op voorwaarde dat je rekent in het juiste talstelsel. In de westerse wereld wordt voornamelijk gerekend in het decimale talstelsel, waarin de cijfers van een getal een getalwaarde hebben die een macht van tien is. In dit talstelsel wordt een getal $abc$ geïnterpreteerd als $c$ + $10 \times b$ + $10^2 \times a$ en worden de tien cijfers $0\ldots 9$ gebruikt. Bij het binair talstelsel zijn de getalwaarden machten van twee, en wordt enkel gewerkt met de cijfers $0$ en $1$. Een getal $abc$ wordt dan in het binair talstelsel (grondtal 2) geïnterpreteerd als $c$ + $2 \times b$ + $2^2 \times a$. In talstelsels met grondtal $10 < b \leq 36$ worden naast de arabische cijfers $0, 1, \ldots, 9$ ook de letters $A, B, \ldots, Z$ gebruikt als cijfers. Deze laatste corresponderen dan met de waarden $10, 11, \ldots, 35$. Hierbij wordt geen onderscheid gemaakt tussen hoofdletters en kleine letters.

Als we met deze kennis terugkijken naar de bovenstaande vergelijkingen, dan gaat de tweede vergelijking bijvoorbeeld op in het talstelsel met grondtal 12, de derde in het talstelsel met grondtal 13 en de vierde in het talstelsel met grondtal 15.

Het feit dat $6 \times 9 = 42$ een geldige vergelijking is in het talstelsel met grondtal 13 is een algemeen bekend bij science fiction fanaten die de boeken uit de reeks "The Hitchhiker's Guide to the Galaxy" gelezen hebben (of de films hebben bekeken). In deze komische reeks van Douglas Adams bouwen hyperintelligente wezens een supercomputer die het antwoord op de ultieme vraag over het leven, het universum en alles moet berekenen. Na 7½ miljoen jaar rekenen gaf deze supercomputer het antwoord $42$. Dit resultaat had natuurlijk geen betekenis omdat ze niet wisten wat de ultieme vraag was. Dus werd er een tweede computer gebouwd die de vraag moest berekenen. Deze computer was de planeet aarde en het berekenen zou 10 miljoen jaar duren, maar vijf minuten voordat de aarde de vraag had berekend, werd ze vernietigd. Daarmee was de ultieme vraag van het leven nog altijd niet gekend. Aangezien de hyperintelligente wezens niet nog eens zo lang wilden wachten, besloten ze om een van de overlevende mensen van de planeet aarde, die dus deel was van de supercomputer, willekeurige letters uit een zak te laten trekken. Deze letters vormden de zin: "Wat krijg je als je zes met negen vermenigvuldigd?". Natuurlijk is $6 \times 9$ decimaal gelijk aan $54$, maar het talstelsel met grondtal $13$ is $6 \times 9$ wel degelijk gelijk aan $42$. Slimme lezers van de boekenreeks hadden dit al snel opgemerkt, waarop de auteur spottend liet weten dat hij geen grappen maakte met grondtal 13. Volgens hem was er iets misgelopen in de berekening waardoor de vraag nog altijd niet geweten was.

Opgave

Bij deze opgave is het de bedoeling om voor een gegeven vergelijking de kleinste basis $b \leq 36$ te bereken waarin de vergelijking opgaat. Je mag ervan uit gaan dat de vergelijkingen alleen cijfers, haakjes, + en * bevatten. Hiervoor ga je als volgt te werk:

• Schrijf een functie evaluatie waaraan twee argumenten moeten doorgegeven worden. Het eerste argument is een string die een wiskundige uitdrukking omschrijft (bijvoorbeeld 14 * 3). Het tweede argument geeft het grondtal aan van het talstelsel waarin de uitdrukking moet berekend worden. De functie moet het decimaal resultaat teruggeven van de evaluatie van de expressie, waarbij ieder getal in de expressie in het talstelsel met het gegeven grondtal geïnterpreteerd moet worden.
• Gebruik de functie evaluatie om een functie talstelsel te schrijven waaraan de stringvoorstelling van een vergelijking moet doorgegeven worden. De expressies in het linkerlid en rechterlid van deze vergelijking bestaat telkens uit een reeks optellingen en vermenigvuldigingen. De functie moet een geheel getal $b \leq 36$ teruggeven dat het kleinste grondtal vormt van een talstelsel waarvoor de vergelijking opgaat.

Voorbereiding

In Python kan je gebruik maken van de ingebouwde functie eval om de waarde te bepalen van een expressie die als een stringargument aan de functie wordt doorgegeven. Deze evaluatiefunctie werkt altijd in het decimale talselsel. De ingebouwde functie int kan dan weer gebruikt worden om de stringvoorstelling van een getal in een talstelsel met grondtal $b$ om te zetten naar het corresponderende gehele getal in het decimale talstelsel. Gebruik het optionele tweede argument (base) van de functie int, om het grondtal van het talstelsel op te geven.

>>> eval('12 * 3 + 6')
42
>>> int('2C', base=15)
42

Voorbeeld

>>> evaluatie('6 * 9', 13)
54
>>> evaluatie('42', 13)
54
>>> evaluatie('17 + 33 * 56', 23)
8742
>>> evaluatie('41 * 42', 23)
8742

>>> talstelsel('6 * 9 = 42')
13
>>> talstelsel('17 + 33 * 56 = 41 * 42')
23