Haskell - Cifras y Letras P51437

Recordeu el famós concurs Cifras y Letras de La 2 amb la mítica Elisenda Roca? Potser sou massa joves...

Tant li fa! Aquest problema aborda la solució dels exercicis de xifres d’aquell programa mític.

Preparats?

Donat un nombre objectiu i una llista de nombres, podem operar amb sumes, restes i productes tots els nombres de la llista i obtenir l’objectiu? Per exemple, si l’objectiu és 4 i la llista és $[2,2]$, es podria aconseguir l’objectiu amb $2+2$ o amb $2\times2$. També, si l’objectiu és 5 i la llista és $[7,2,1]$, es podria aconseguir l’objectiu amb $1\times(7-2)$. En canvi, li l’objectiu és 9 i la llista és $[8,2,6]$, no hi cap manera.

Per resoldre-ho en Haskell, definim les expressions de la forma següent:

    data Operator = Add | Sub | Mul
        deriving (Show)

    data Expression = Value Int | Operation Operator Expression Expression
        deriving (Show)

i us demanem que implementeu una funció

    solve :: Int -> [Int] -> Maybe Expression

que, donat un objectiu i una llista de nombres, retorni (si existeix) una expressió que, usant exactament un cop tots els nombres de la llista, sigui igual a l’objectiu.

Observació

Com que hi pot haver més d’una solució possible, el Jutge comprovarà que la vostra sortida sigui correcta, encara que pugui ser diferent en els casos dels exemples.