Soluzione(?) problema dei 4 quattro

Afelium (770 points)
3 11 18
asked Oct 10, 2020 in Programmare in Python by Afelium (770 points)
recategorized Oct 10, 2020 by andrea.sterbini

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

459 views

1 Answer

andrea.sterbini (168140 points)
488 897 1729
answered Oct 10, 2020 by andrea.sterbini (168,140 points)
Qual'è la domanda?
Afelium (770 points)
3 11 18
commented Oct 11, 2020 by Afelium (770 points)
edited Oct 11, 2020 by Afelium

I posted the algorithm on this forum because it might help other people to come up with a more efficient solution

Principalmente volevo vedere se qualcuno mi può aiutare a rendere l'algoritmo piu efficiente , o  trovarne uno migliore. In generale speravo di portare più attenzione su questo problema, dopo essermici impuntato. Chiedo scusa se ho utilizzato il forum in modo errato

andrea.sterbini (168140 points)
488 897 1729
commented Oct 11, 2020 by andrea.sterbini (168,140 points)

Certo laugh.

Nello spiegare i vostri algoritmi nella ricerca di migliori soluzioni ricordate che parecchi altri sono alle prime armi e che una descrizione molto dettagliata può "spoilerare" il ragionamento, togliendogli il gusto di cercare la soluzione da sè.

Quindi aspettate un attimo prima di postare algoritmi completi, fate domande più indirette, che lasciano spazio di ragionamento anche agli altri ma che possono aprire la discussione anche in modo approfondito.

(e proprio perchè ti sei appassionato al problema sarebbe un peccato rischiare di sembrare uno show-off wink)

Afelium (770 points)
3 11 18
commented Oct 12, 2020 by Afelium (770 points)
Grazie del chiarimento, vedrò di tenerlo a mente per i miei post futuri