Sumable sin vecinos

PorJosé A. Alonso 21-diciembre-201719-febrero-2018

En la lista [3,2,5,7,4] el número 12 se puede escribir como una suma de elementos de la lista sin incluir sus vecinos (ya que es la suma de 3, 5 y 4); en cambio, 14 no lo es (porque es la suma de 3, 7 y 4, pero 7 y 4 son vecinos).

Definir la función

   esSumableSinVecinos :: [Int] -> Int -> Bool

1	esSumableSinVecinos :: [Int] -> Int -> Bool

tal que (esSumableSinVecinos xs n) se verifica si n se puede escribir como una suma de elementos de xs que no incluye a ninguno de sus vecinos. Por ejemplo,

   esSumableSinVecinos [3,2,5,7,4] 12  ==  True
   esSumableSinVecinos [3,2,5,7,4] 9   ==  True
   esSumableSinVecinos [3,2,5,7,4] 6   ==  True
   esSumableSinVecinos [3,2,5,7,4] 14  ==  False
   esSumableSinVecinos [3,2,5,7,4] 1   ==  False

esSumableSinVecinos [3,2,5,7,4] 12 == True

esSumableSinVecinos [3,2,5,7,4] 9 == True

esSumableSinVecinos [3,2,5,7,4] 6 == True

esSumableSinVecinos [3,2,5,7,4] 14 == False

esSumableSinVecinos [3,2,5,7,4] 1 == False

Soluciones

esSumableSinVecinos :: [Int] -> Int -> Bool
esSumableSinVecinos _  0       = True
esSumableSinVecinos []  _      = False
esSumableSinVecinos [x] n      = x == n
esSumableSinVecinos (x:y:zs) n = esSumableSinVecinos zs (n - x) ||
                                 esSumableSinVecinos (y:zs) n

esSumableSinVecinos :: [Int] -> Int -> Bool

esSumableSinVecinos _ 0 = True

esSumableSinVecinos [] _ = False

esSumableSinVecinos [x] n = x == n

esSumableSinVecinos (x:y:zs) n = esSumableSinVecinos zs (n - x) ||

esSumableSinVecinos (y:zs) n

8 Comentarios

esSumableSinVecinos :: [Int] -> Int -> Bool
esSumableSinVecinos _ 0  = True
esSumableSinVecinos xs n = elem n $ noVecinos xs
 
noVecinos :: [Int] -> [Int]
noVecinos []       = []
noVecinos [x]      = [x]
noVecinos (x:y:xs) = x: (map (+ x) (noVecinos xs)) ++ noVecinos (y:xs)

esSumableSinVecinos :: [Int] -> Int -> Bool

esSumableSinVecinos _ 0 = True

esSumableSinVecinos xs n = elem n $ noVecinos xs

noVecinos :: [Int] -> [Int]

noVecinos [] = []

noVecinos [x] = [x]

noVecinos (x:y:xs) = x: (map (+ x) (noVecinos xs)) ++ noVecinos (y:xs)

Responder

esppercab dice:

26-diciembre-2017 a las 19:50

Hola Antonio, ¿me podrías explicar como defines noVecinos?
¡¡Gracias!!

Responder

esSumableSinVecinos' :: [Int] -> Int -> Bool
esSumableSinVecinos'  _            0 = True
esSumableSinVecinos' [ ]           _ = False
esSumableSinVecinos' [x]           n = x == n
esSumableSinVecinos' (x:ys@(_:xs)) n = (n >= x && esSumableSinVecinos' xs (n - x)) || esSumableSinVecinos' ys n


-- En el peor caso sigue teniendo coste exponencial, pero recorre el árbol
-- mínimo necesario y sólo hasta encontrar solución:
> esSumableSinVecinos' [1..2000] 1000000
True
(0.01 secs, 1,353,032 bytes)

esSumableSinVecinos' :: [Int] -> Int -> Bool

esSumableSinVecinos' _ 0 = True

esSumableSinVecinos' [ ] _ = False

esSumableSinVecinos' [x] n = x == n

esSumableSinVecinos' (x:ys@(_:xs)) n = (n >= x && esSumableSinVecinos' xs (n - x)) || esSumableSinVecinos' ys n

-- En el peor caso sigue teniendo coste exponencial, pero recorre el árbol

-- mínimo necesario y sólo hasta encontrar solución:

> esSumableSinVecinos' [1..2000] 1000000

True

(0.01 secs, 1,353,032 bytes)

Responder

antgongar dice:

22-diciembre-2017 a las 20:53

Falla en casos como el siguiente

λ> esSumableSinVecinos' [3,0,-2] 1 False

1
2

λ> esSumableSinVecinos' [3,0,-2] 1
False

Responder
1. josejuan dice:
  
  22-diciembre-2017 a las 21:23
  
  Explícitamente no he considerado los negativos, pero si quieres considerarlos hay una reducción trivial con coste O(n) (y dado que el algoritmo es exponencial no importa mucho) de uno que admite sólo no negativos a otro que admite todos los enteros.
  
  Responder

Una propuesta usando matrices:

import Data.Matrix (fromLists,multStd2,transpose,getRow)
import Data.Vector as V (elem)

esSumableSinVecinos :: [Int] -> Int -> Bool
esSumableSinVecinos xs n =
  V.elem n
  (getRow 1
   ((fromLists (listas10 xs))
    `multStd2` (transpose (fromLists [xs]))))

listas10 :: [Int] -> [[Int]]
listas10 [x]      = [[1],[0]]
listas10 (x:y:xs) =
  (map ([0,0]++) $ listas00 xs)
  ++ (map ([1,0]++) $ listas10 xs)
  ++ (map ([0,1]++) $ listas01 xs)
listas10 _        = [[]]

listas01 :: [Int] -> [[Int]]
listas01 [x]      = [[0]]
listas01 (x:y:xs) =
  (map ([0,0]++) $ listas00 xs)
  ++ (map ([0,1]++) $ listas01 xs)
listas01 _        = [[]]

listas00 :: [Int] -> [[Int]]
listas00 [x]      = [[1]]
listas00 [x,y]    = [[1,0],[0,1]]
listas00 (x:y:xs) =
  (map ([0,0]++) $ listas00 xs)
  ++ (map ([1,0]++) $ listas10 xs)
  ++ (map ([0,1]++) $ listas01 xs)
listas00 _        = [[]]

import Data.Matrix (fromLists,multStd2,transpose,getRow)

import Data.Vector as V (elem)

esSumableSinVecinos :: [Int] -> Int -> Bool

esSumableSinVecinos xs n =

V.elem n

(getRow 1

((fromLists (listas10 xs))

`multStd2` (transpose (fromLists [xs]))))

listas10 :: [Int] -> [[Int]]

listas10 [x] = [[1],[0]]

listas10 (x:y:xs) =

(map ([0,0]++) $ listas00 xs)

++ (map ([1,0]++) $ listas10 xs)

++ (map ([0,1]++) $ listas01 xs)

listas10 _ = [[]]

listas01 :: [Int] -> [[Int]]

listas01 [x] = [[0]]

listas01 (x:y:xs) =

(map ([0,0]++) $ listas00 xs)

++ (map ([0,1]++) $ listas01 xs)

listas01 _ = [[]]

listas00 :: [Int] -> [[Int]]

listas00 [x] = [[1]]

listas00 [x,y] = [[1,0],[0,1]]

listas00 (x:y:xs) =

(map ([0,0]++) $ listas00 xs)

++ (map ([1,0]++) $ listas10 xs)

++ (map ([0,1]++) $ listas01 xs)

listas00 _ = [[]]

Responder

Falla en el primer ejemplo

λ> esSumableSinVecinos [3,2,5,7,4] 12
False

1 2	λ> esSumableSinVecinos [3,2,5,7,4] 12 False

pero 12 = 3 + 5 + 4

Responder

Es verdad, es que no es un vector fila lo que se obtiene, si no un vector columna. Entonces la definición debería de ser:

import Data.Matrix (fromLists,multStd2,transpose,getCol)
import Data.Vector as V (elem)

esSumableSinVecinos :: [Int] -> Int -> Bool
esSumableSinVecinos xs n =
  V.elem n
  (getCol 1
   ((fromLists (listas10 xs))
    `multStd2` (transpose (fromLists [xs]))))

listas10 :: [Int] -> [[Int]]
listas10 [x]      = [[1],[0]]
listas10 (x:y:xs) =
  (map ([0,0]++) $ listas00 xs)
  ++ (map ([1,0]++) $ listas10 xs)
  ++ (map ([0,1]++) $ listas01 xs)
listas10 _        = [[]]

listas01 :: [Int] -> [[Int]]
listas01 [x]      = [[0]]
listas01 (x:y:xs) =
  (map ([0,0]++) $ listas00 xs)
  ++ (map ([0,1]++) $ listas01 xs)
listas01 _        = [[]]

listas00 :: [Int] -> [[Int]]
listas00 [x]      = [[1]]
listas00 [x,y]    = [[1,0],[0,1]]
listas00 (x:y:xs) =
  (map ([0,0]++) $ listas00 xs)
  ++ (map ([1,0]++) $ listas10 xs)
  ++ (map ([0,1]++) $ listas01 xs)
listas00 _        = [[]]

import Data.Matrix (fromLists,multStd2,transpose,getCol)

import Data.Vector as V (elem)

esSumableSinVecinos :: [Int] -> Int -> Bool

esSumableSinVecinos xs n =

V.elem n

(getCol 1

((fromLists (listas10 xs))

`multStd2` (transpose (fromLists [xs]))))

listas10 :: [Int] -> [[Int]]

listas10 [x] = [[1],[0]]

listas10 (x:y:xs) =

(map ([0,0]++) $ listas00 xs)

++ (map ([1,0]++) $ listas10 xs)

++ (map ([0,1]++) $ listas01 xs)

listas10 _ = [[]]

listas01 :: [Int] -> [[Int]]

listas01 [x] = [[0]]

listas01 (x:y:xs) =

(map ([0,0]++) $ listas00 xs)

++ (map ([0,1]++) $ listas01 xs)

listas01 _ = [[]]

listas00 :: [Int] -> [[Int]]

listas00 [x] = [[1]]

listas00 [x,y] = [[1,0],[0,1]]

listas00 (x:y:xs) =

(map ([0,0]++) $ listas00 xs)

++ (map ([1,0]++) $ listas10 xs)

++ (map ([0,1]++) $ listas01 xs)

listas00 _ = [[]]

Responder

Sumable sin vecinos

Soluciones

8 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

8 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico