Haskell - Cifras y Letras P51437


Statement
 

pdf   zip

thehtml

[r] 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×2. També, si l’objectiu és 5 i la llista és [7,2,1], es podria aconseguir l’objectiu amb 1×(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.

Public test cases

  • Input

    solve 4 [2,2]
solve 5 [7,2,1]
solve 3 [4,1]
solve 9 [8,2,6]

    Output

    Just (Operation Add (Value 2) (Value 2))
Just (Operation Mul (Value 1) (Operation Sub (Value 7) (Value 2)))
Just (Operation Sub (Value 4) (Value 1))
Nothing
    • Information
    Author
    Jordi Petit
    Language
    Catalan
    Official solutions
    Haskell
    User solutions
    Haskell