Qualche giorno fa il prof. Spognardi ha proposto questa sfida da twiki
[spoiler]
Inseriamo nell'editor in un nuovo file questo testo (facciamo copia e incolla)
# Four fours challenge # Filename: fourfours.py # Problem description: The four fours challenge! from math import * print("Zero is", 4+4-4-4)
e salviamo il nuovo file con il nome fourfours.py. Adesso possiamo eseguire il file e vedere che stampa "Zero is 0".
La sfida consiste nello scrivere un programma che stampa a video tutti i numeri da 0 a 20 usando sempre e soltanto e comunque quattro 4... Vanno bene anche numeri con decimali (ovvero 1.0, 2.0 etc.) e frazionari (ovvero 0.4, 0.19).
Poiché abbiamo usato la riga from math import *, per affrontare la sfida possiamo usare anche due funzioni matematiche fondamentali, ovvero il fattoriale (factorial) e la radice quadrata (sqrt): avremo, ad esempio, che factorial(5) ritorna 5!=5*4*3*2*1=120 e che sqrt(9)=3.
[/spoiler]
For non-Italians, the exercise consists in finding an algorithm which prints every number from 0 to 20 as a result of operations between four fours. Allowed operations are +, -, *, /, factorial and sqrt.
I didnt want to implement an hardcoded solution, and in order to make it dynamic and scalable I had to follow one of two paths: either find a universal algorithm or a combinatorial one . I had no luck with the first option , so I chose the less efficent one, but it still turned out to be a good exercise. I posted the algorithm on this forum because it might help other people to come up with a more efficient solution.
"""
Created on Thu Oct 8 21:37:56 2020
@author: Sammarini Flavio
"""
"""
SEQUENCE SCHEME
0 1 2 3 4 5 6
O | O | O | O
Eg:
+4 / -4 (+) +!4 / +√4
O = every combination of 4 and any operator apart from * and / , .takes up even positions.
I nicknamed them "StandAlone" because they dont need a second operand in order to have meaning
(+4, -4, +!4, -!4, +√4, -√4 )
| = multiplication, division or no operator,takes up odd positions
except "no operator", they dont have meaning without a second operand
(*, /, or an hidden +\no operator)
"""
getCalcList
"""
This is the core function of my solution. It uses recursion to build every possible expression piece after piece (in the form of a string) so that they can be judged by the next method. In order to work this method needs several parameters:
- Digits: the number/value of the digits (Eg 4,4,4,4)
- NestLevel: the nesting level of the current call as a recursion (it is increased after intialization and then everytime the function calls itself), which also matches with the part of the expression considered at the moment
- Ops: a list containing the operations (codified with integers as explained in the "Sequence scheme" section) which is currently being evaluated (initialized at the first nesting level with null values and then gradually replaced with every possible combination at each NestLevel)
- Results: a list to save all the succesfully evaluated expressions. Passed by every call when calling itself, and then returned to the caller (going all the way up to the original call)
"""
TryPutInList
"""
This function, given the expression codified as integers, evaluates it and, if the result meets the conditions, puts it in the Result list given by and given back to the caller (the function described above). The parameters of this function are all shared and passed by the previous one
- Digits: needed to know which operands should be put into the string
- Ops: needed to know which operators should be put into the string
- Results: updated if the result of the evaluated expression meets the desired conditions (eg between 0 and 20)
"""
opIdToStr
"""
This method simply maps integers to the relative operation in order to create strings. To do so it needs the Ops list and the digits variable to write the correct number in the expression
"""
checkOpId
"""
This method just checks if an operation (still codified as an integer), based on its "StandAlone" quality (explained in the "Sequence scheme" section) is occupying the right place or not
"""
Btw hope this version of the post complies with the rules