SPOJ.com - Problem PROG0462

PROG0462 - Stubborn

no tags

Choose a random number $n \in \mathbb{N}$. Form a new number $n'$ by writing the digits of the number $n$ backwards. Calculate the sum $n + n'$ of these numbers.

In most cases, repeating this procedure will eventually yield a palindrome:

For some obscure reason, this doesn't apply to number 196 — at least, computer simulations that repeated the procedure until they got numbers of more than 300 million digits long, have never found a palindrome. Until this moment, nobody has found any sound proof for or against, so for now the answer to this question in unknown.

Assignment

A palindrome is a word, sentence or number or another sequence of characters that reads the same from left to right as from right to left. The term palindrome was introduced in the 17th century by the English author Ben Johnson, and is a compound of the Greek words palin (πάλιν, "again") and dromos (δρόμος, "direction").

Write a function palindrome to which a string must be given. The function must print a Boolean value that indicates whether the string given is a palindrome. When deciding if the string is symmetrical, the function should take into account all characters and it should also distinguish between uppercase and lowercase letters. Furthermore, the function has three optional parameters that can change this behaviour. A Boolean value can be given to each of these parameters, it's default value is True. The optional parameters have the following name, order and meaning:

digits: if the value False is given to this parameter, the function should ignore all digits in the string
other: if the value False is given to this parameter, the function should ignore all characters of the string that are not a letter or a digit
uppercasesensitive: if the value False is given to this parameter, the function shouldn't distinguish between lowercase and uppercase letters

Use the function palindrome to write a function stubborn, to which a number $n \in \mathbb{N}$ should be given. The function must print how many times the function above has to be repeated before it becomes a palindrome. Because there are values for which the procedure is likely not to become a palindrome, this function has an optional parameter maximum to which a number $m \in \mathbb{N}$ (default value: 1000) can be given. If the function hasn't found a palindrome after $m$ repetitions, the function should print the value $m$ as a result.

Example

>>> palindrome('a1b2c3c2b1a')
True
>>> palindrome('a1b2c3C2B1A')
False
>>> palindrome('a1b2c3C2B1A', uppercasesensitive=False)
True
>>> palindrome('a1b2c3c4b5a')
False
>>> palindrome('a1b2c3c4b5a', digits=False)
True

>>> palindrome('step on no pets')
True
>>> palindrome('Step on no pets')
False
>>> palindrome('Step on no pets', uppercasesensitive=False)
True
>>> palindrome("No 'x' in 'Nixon'", other=False, uppercasesensitive=False)
True

>>> stubborn(871)
3
>>> stubborn(196)
1000
>>> stubborn(196, maximum=200)
200
>>> stubborn(78552)
31
>>> stubborn(78552, maximum=25)
25

Kies een willekeurig getal $n \in \mathbb{N}$. Vorm een nieuw getal $n'$ door de cijfers van het getal $n$ van achter naar voor te schrijven. Bereken de som $n + n'$ van deze twee getallen.

In de meeste gevallen zal het herhalen van deze procedure uiteindelijk een palindroom opleveren:

Op de één of andere perverse manier geldt dit echter niet voor het getal 196 — althans, computersimulaties die de procedure herhaald hebben tot getallen van meer dan 300 miljoen cijfers lang, hebben nooit een palindroom gevonden. Is 196 immuun voor het genereren van palindromen? Tot nu toe heeft niemand een sluitend bewijs voor of tegen weten te leveren, dus voorlopig kent niemand nog het antwoord op deze vraag.

Opgave

Een palindroom is een woord, zin, getal of andere reeks karakters die hetzelfde lezen van links naar rechts als van rechts naar links. De term palindroom werd in de 17e eeuw geïntroduceerd door de Engelse schrijver Ben Johnson, en is een samenstelling van de Griekse woorden palin (πάλιν, "opnieuw") en dromos (δρόμος, "weg, richting").

Schrijf een functie palindroom waaraan een string moet doorgegeven worden. De functie moet een Booleaanse waarde teruggeven die aangeeft of de gegeven string al dan niet een palindroom is. Bij het bepalen of de string symmetrisch is, moet de functie standaard rekening houden met alle karakters en moet de functie ook onderscheid maken tussen hoofdletters en kleine letters. De functie heeft echter ook nog drie optionele parameters die dit gedrag kunnen wijzigen. Aan deze parameters kan telkens een Booleaanse waarde doorgegeven worden, die standaard ingesteld is op True. De optionele parameters hebben de volgende naam, volgorde, en betekenis:

cijfers: als de waarde False wordt doorgegeven aan deze parameter, moet de functie alle cijfers in de gegeven string negeren
andere: als de waarde False wordt doorgegeven aan deze parameter, moet de functie alle karakters in de gegeven string negeren die geen letter of cijfer zijn
hoofdlettergevoelig: als de waarde False wordt doorgegeven aan deze parameter, moet de functie geen onderscheid maken tussen hoofdletters en kleine letters

Gebruik de functie palindroom om een functie hardnekkig te schrijven, waaraan een getal $n \in \mathbb{N}$ moet doorgegeven worden. De functie moet teruggeven hoeveel keer de hierboven beschreven procedure moet uitgevoerd worden, alvorens een getal bekomen wordt dat een palindroom is. Omdat er getallen bestaan waarvoor de procedure naar alle waarschijnlijkheid nooit een palindroom oplevert, heeft de functie ook een optionele parameter maximum waaraan een getal $m \in \mathbb{N}$ (standaardwaarde: 1000) kan doorgegeven worden. Indien de functie na $m$ herhalingen nog geen palindroom heeft opgeleverd, moet de functie de waarde $m$ als resultaat teruggeven.

Voorbeeld

>>> palindroom('a1b2c3c2b1a')
True
>>> palindroom('a1b2c3C2B1A')
False
>>> palindroom('a1b2c3C2B1A', hoofdlettergevoelig=False)
True
>>> palindroom('a1b2c3c4b5a')
False
>>> palindroom('a1b2c3c4b5a', cijfers=False)
True

>>> palindroom('step on no pets')
True
>>> palindroom('Step on no pets')
False
>>> palindroom('Step on no pets', hoofdlettergevoelig=False)
True
>>> palindroom("No 'x' in 'Nixon'", andere=False, hoofdlettergevoelig=False)
True

>>> hardnekkig(871)
3
>>> hardnekkig(196)
1000
>>> hardnekkig(196, maximum=200)
200
>>> hardnekkig(78552)
31
>>> hardnekkig(78552, maximum=25)
25

Submit solution!

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