Avanzado

Caminos en un grafo

PorJosé A. Alonso 2-junio-201526-marzo-2022

Definir las funciones

   grafo   :: [(Int,Int)] -> Grafo Int Int
   caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

1 2	grafo :: [(Int,Int)] -> Grafo Int Int caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

(grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,

     ghci> grafo [(2,4),(4,5)]
     G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

1 2	ghci> grafo [(2,4),(4,5)] G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

(caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,

     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
     [[1,3,5,7],[1,3,7]]
     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
     [[2,5,3,7],[2,5,7]]
     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
     [[1,3,5,2],[1,3,7,5,2]]
     ghci> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
     []
     ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
     109601

ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)

[[1,3,5,7],[1,3,7]]

ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)

[[2,5,3,7],[2,5,7]]

ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)

[[1,3,5,2],[1,3,7,5,2]]

ghci> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4

[]

ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)

109601

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.

Soluciones

import Data.List (sort)
import I1M.Grafo
import I1M.BusquedaEnEspaciosDeEstados

grafo :: [(Int,Int)] -> Grafo Int Int
grafo as = creaGrafo ND (m,n) [(x,y,0) | (x,y) <- as]
    where ns = map fst as ++ map snd as
          m  = minimum ns
          n  = maximum ns

-- 1ª solución
-- ===========

caminos :: Grafo Int Int -> Int -> Int -> [[Int]]
caminos g a b = aux [[b]] where 
    aux [] = []
    aux ((x:xs):yss)
        | x == a    = (x:xs) : aux yss
        | otherwise = aux ([z:x:xs | z <- adyacentes g x
                                   , z `notElem` (x:xs)] 
                           ++ yss) 

-- 2ª solución (mediante espacio de estados)
-- =========================================

caminos2 :: Grafo Int Int -> Int -> Int -> [[Int]]
caminos2 g a b = buscaEE sucesores esFinal inicial
    where inicial          = [b]
          sucesores (x:xs) = [z:x:xs | z <- adyacentes g x
                                     , z `notElem` (x:xs)] 
          esFinal (x:xs)   = x == a

-- Comparación de eficiencia
-- =========================

--    ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
--    109601
--    (3.57 secs, 500533816 bytes)
--    ghci> length (caminos2 (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
--    109601
--    (3.53 secs, 470814096 bytes)

import Data.List (sort)

import I1M.Grafo

import I1M.BusquedaEnEspaciosDeEstados

grafo :: [(Int,Int)] -> Grafo Int Int

grafo as = creaGrafo ND (m,n) [(x,y,0) | (x,y) <- as]

where ns = map fst as ++ map snd as

m = minimum ns

n = maximum ns

-- 1ª solución

-- ===========

caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

caminos g a b = aux [[b]] where

aux [] = []

aux ((x:xs):yss)

| x == a = (x:xs) : aux yss

| otherwise = aux ([z:x:xs | z <- adyacentes g x

, z `notElem` (x:xs)]

++ yss)

-- 2ª solución (mediante espacio de estados)

-- =========================================

caminos2 :: Grafo Int Int -> Int -> Int -> [[Int]]

caminos2 g a b = buscaEE sucesores esFinal inicial

where inicial = [b]

sucesores (x:xs) = [z:x:xs | z <- adyacentes g x

, z `notElem` (x:xs)]

esFinal (x:xs) = x == a

-- Comparación de eficiencia

-- =========================

-- ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)

-- 109601

-- (3.57 secs, 500533816 bytes)

-- ghci> length (caminos2 (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)

-- 109601

-- (3.53 secs, 470814096 bytes)

Problema de las bolas de Dijkstra

PorJosé A. Alonso 1-junio-201513-junio-2015

En el juego de las bolas de Dijkstra se dispone de una bolsa con bolas blancas y negras. El juego consiste en elegir al azar dos bolas de la bolsa y añadir una bola negra si las dos bolas elegidas son del mismo color o una bola blanca en caso contrario. El juego termina cuando queda sólo una bola en la bolsa.

Vamos a representar las bolas blancas por 0, las negras por 1 y la bolsa la representaremos por una lista cuyos elementos son 0 ó 1.

Definir las funciones

   juego  :: [Int] -> [[Int]]
   ultima :: [Int] -> Int

1 2	juego :: [Int] -> [[Int]] ultima :: [Int] -> Int

tales que

(juego xs) es la lista de los pasos aleatorios de un juego de Dijkstra a partir de la lista xs. Por ejemplo,

     juego [1,1,0,0,1]  ==  [[1,1,0,0,1],[1,1,0,0],[1,1,1],[1,1],[1]]
     juego [1,1,0,0,1]  ==  [[1,1,0,0,1],[0,1,1,0],[0,0,1],[1,1],[1]]
     juego [1,0,0,0,1]  ==  [[1,0,0,0,1],[0,0,0,1],[0,1,1],[1,0],[0]]
     juego [1,0,1,1,1]  ==  [[1,0,1,1,1],[1,1,0,1],[1,0,1],[0,1],[0]]

juego [1,1,0,0,1] == [[1,1,0,0,1],[1,1,0,0],[1,1,1],[1,1],[1]]

juego [1,1,0,0,1] == [[1,1,0,0,1],[0,1,1,0],[0,0,1],[1,1],[1]]

juego [1,0,0,0,1] == [[1,0,0,0,1],[0,0,0,1],[0,1,1],[1,0],[0]]

juego [1,0,1,1,1] == [[1,0,1,1,1],[1,1,0,1],[1,0,1],[0,1],[0]]

(ultima xs) es la bola que queda en la bolsa al final del juego de Dijkstra a partir de xs. Por ejemplo,

     ultima [1,1,0,0,1]  ==  1
     ultima [1,0,0,0,1]  ==  0
     ultima [1,0,1,1,1]  ==  0

ultima [1,1,0,0,1] == 1

ultima [1,0,0,0,1] == 0

ultima [1,0,1,1,1] == 0

Comprobar con QuickCheck que la bola que queda en la bolsa al final del juego de Dijkstra es blanca si, y sólo si, el número de bolas blancas en la bolsa inicial es impar.

Soluciones

import System.IO.Unsafe
import System.Random
import Test.QuickCheck

-- (aleatorio a b) es un número aleatorio entre a y b. Por ejemplo, 
--    ghci> aleatorio 0 1000
--    681
--    ghci> aleatorio 0 1000
--    66
aleatorio :: Random t => t -> t -> t
aleatorio a b = unsafePerformIO $ 
                getStdRandom (randomR (a,b))

-- (aleatorios m n) es una lista infinita de números aleatorios entre m y
-- n. Por ejemplo, 
--    ghci> take 20 (aleatorios 2 9)
--    [6,5,3,9,6,3,6,6,2,7,9,6,8,6,2,4,2,6,9,4]
--    ghci> take 20 (aleatorios 2 9)
--    [3,7,7,5,7,7,5,8,6,4,7,2,8,8,2,8,7,6,5,5]
aleatorios :: Random t => t -> t -> [t]
aleatorios m n = aleatorio m n : aleatorios m n

-- (selecciona n x) es el par formado por el n-ésimo elemento de xs y
-- los restantes elementos. Por ejemplo,
--    selecciona 0 "abc"  ==  ('a',"bc")
--    selecciona 1 "abc"  ==  ('b',"ac")
--    selecciona 2 "abc"  ==  ('c',"ab")
selecciona :: Int -> [a] -> (a,[a])
selecciona n xs = (z,ys++zs)
    where (ys,z:zs) = splitAt n xs

-- (extraeAleatorio xs) es el par formado aleatoriamente por un elemento
-- de xs y las restantes. Por ejemplo, 
--    extraeAleatorio [1,0,0,1,1]  ==  (0,[1,0,1,1])
--    extraeAleatorio [1,0,0,1,1]  ==  (1,[0,0,1,1])
--    extraeAleatorio [1,0,0,1,1]  ==  (0,[1,0,1,1])
--    extraeAleatorio [1,0,0,1,1]  ==  (1,[1,0,0,1])
extraeAleatorio :: [a] -> (a,[a])
extraeAleatorio xs = selecciona n xs
    where n = aleatorio 0 (length xs - 1)

-- (inserta n x xs) inserta, en la posición n, el elemento x en la lista
-- xs. Por ejemplo,  
--    inserta 0 'a' "bcd"  ==  "abcd"
--    inserta 1 'a' "bcd"  ==  "bacd"
--    inserta 2 'a' "bcd"  ==  "bcad"
--    inserta 3 'a' "bcd"  ==  "bcda"
inserta :: Int -> a -> [a] -> [a]
inserta n x xs = us ++ (x:vs)
    where (us,vs) = splitAt n xs

-- (insertaAleatorio x xs) inserta aleatoriamente el elemento x en la
-- lista xs. Por ejemplo,
--    insertaAleatorio 9 [0..8]  ==  [0,1,2,3,4,9,5,6,7,8]
--    insertaAleatorio 9 [0..8]  ==  [0,1,9,2,3,4,5,6,7,8]
--    insertaAleatorio 9 [0..8]  ==  [0,1,2,3,4,5,6,9,7,8]
insertaAleatorio :: a -> [a] -> [a]
insertaAleatorio x xs = inserta n x xs
    where n = aleatorio 0 (length xs - 1)

-- (paso xs) elige aleatoriamente dos bolas de xs e inserta
-- aleatoriamente una bola negra si las dos extraídas son del mismo
-- color o una blanca, en caso contrario. Por ejemplo, 
--    paso [1,0,1,1,0,0,1,1,1,0,0,0]  ==  [0,1,1,0,0,1,1,0,1,0,0]
--    paso [1,0,1,1,0,0,1,1,1,0,0,0]  ==  [1,0,0,0,1,1,1,0,0,1,0]
paso :: [Int] -> [Int]
paso [x] = []
paso xs | x == y    = insertaAleatorio 1 zs
        | otherwise = insertaAleatorio 0 zs 
    where (x,ys) = extraeAleatorio xs
          (y,zs) = extraeAleatorio ys

-- (juego xs) es la lista de los pasos aleatorios de un juego a partir
-- de la lista xs. Por ejemplo,
--    juego [1,1,0,0,1]  ==  [[1,1,0,0,1],[1,1,0,0],[1,1,1],[1,1],[1]]
--    juego [1,1,0,0,1]  ==  [[1,1,0,0,1],[0,1,1,0],[0,0,1],[1,1],[1]]
--    juego [1,1,0,0,0]  ==  [[1,1,0,0,0],[0,1,0,0],[1,1,0],[0,1],[0]]
juego :: [Int] -> [[Int]]
juego xs = takeWhile (not . null) (iterate paso xs)

-- (ultima xs) es la bola que queda en la bolsa al final del juego de
-- Dijkstra. Por ejemplo, 
--    ultima [1,0,0,1]  ==  1
ultima :: [Int] -> Int
ultima = head . last . juego

-- (numeroDeCeros xs) es el número de ceros en xs. Por ejemplo,
--    numeroDeCeros [1,0,0,1,0]  ==  3
numeroDeCeros :: [Int] -> Int
numeroDeCeros xs = length (filter (==0) xs)

-- Propiedad. La bola que queda en la bolsa al final del juego de
-- Dijkstra es blanca si, y sólo si, el número de bolas blancas en la
-- bolsa inicial es impar. 
prop_Dijkstra :: [Int] -> Property
prop_Dijkstra xs = 
    not (null xs) ==> (ultima ys == 0) == odd (numeroDeCeros ys)
    where ys = [x `mod` 2 | x <- xs]

-- La comprobación es
--    ghci> quickCheck prop_Dijkstra
--    +++ OK, passed 100 tests.

100

101

102

import System.IO.Unsafe

import System.Random

import Test.QuickCheck

-- (aleatorio a b) es un número aleatorio entre a y b. Por ejemplo,

-- ghci> aleatorio 0 1000

-- 681

-- ghci> aleatorio 0 1000

-- 66

aleatorio :: Random t => t -> t -> t

aleatorio a b = unsafePerformIO $

getStdRandom (randomR (a,b))

-- (aleatorios m n) es una lista infinita de números aleatorios entre m y

-- n. Por ejemplo,

-- ghci> take 20 (aleatorios 2 9)

-- [6,5,3,9,6,3,6,6,2,7,9,6,8,6,2,4,2,6,9,4]

-- ghci> take 20 (aleatorios 2 9)

-- [3,7,7,5,7,7,5,8,6,4,7,2,8,8,2,8,7,6,5,5]

aleatorios :: Random t => t -> t -> [t]

aleatorios m n = aleatorio m n : aleatorios m n

-- (selecciona n x) es el par formado por el n-ésimo elemento de xs y

-- los restantes elementos. Por ejemplo,

-- selecciona 0 "abc" == ('a',"bc")

-- selecciona 1 "abc" == ('b',"ac")

-- selecciona 2 "abc" == ('c',"ab")

selecciona :: Int -> [a] -> (a,[a])

selecciona n xs = (z,ys++zs)

where (ys,z:zs) = splitAt n xs

-- (extraeAleatorio xs) es el par formado aleatoriamente por un elemento

-- de xs y las restantes. Por ejemplo,

-- extraeAleatorio [1,0,0,1,1] == (0,[1,0,1,1])

-- extraeAleatorio [1,0,0,1,1] == (1,[0,0,1,1])

-- extraeAleatorio [1,0,0,1,1] == (0,[1,0,1,1])

-- extraeAleatorio [1,0,0,1,1] == (1,[1,0,0,1])

extraeAleatorio :: [a] -> (a,[a])

extraeAleatorio xs = selecciona n xs

where n = aleatorio 0 (length xs - 1)

-- (inserta n x xs) inserta, en la posición n, el elemento x en la lista

-- xs. Por ejemplo,

-- inserta 0 'a' "bcd" == "abcd"

-- inserta 1 'a' "bcd" == "bacd"

-- inserta 2 'a' "bcd" == "bcad"

-- inserta 3 'a' "bcd" == "bcda"

inserta :: Int -> a -> [a] -> [a]

inserta n x xs = us ++ (x:vs)

where (us,vs) = splitAt n xs

-- (insertaAleatorio x xs) inserta aleatoriamente el elemento x en la

-- lista xs. Por ejemplo,

-- insertaAleatorio 9 [0..8] == [0,1,2,3,4,9,5,6,7,8]

-- insertaAleatorio 9 [0..8] == [0,1,9,2,3,4,5,6,7,8]

-- insertaAleatorio 9 [0..8] == [0,1,2,3,4,5,6,9,7,8]

insertaAleatorio :: a -> [a] -> [a]

insertaAleatorio x xs = inserta n x xs

where n = aleatorio 0 (length xs - 1)

-- (paso xs) elige aleatoriamente dos bolas de xs e inserta

-- aleatoriamente una bola negra si las dos extraídas son del mismo

-- color o una blanca, en caso contrario. Por ejemplo,

-- paso [1,0,1,1,0,0,1,1,1,0,0,0] == [0,1,1,0,0,1,1,0,1,0,0]

-- paso [1,0,1,1,0,0,1,1,1,0,0,0] == [1,0,0,0,1,1,1,0,0,1,0]

paso :: [Int] -> [Int]

paso [x] = []

paso xs | x == y = insertaAleatorio 1 zs

| otherwise = insertaAleatorio 0 zs

where (x,ys) = extraeAleatorio xs

(y,zs) = extraeAleatorio ys

-- (juego xs) es la lista de los pasos aleatorios de un juego a partir

-- de la lista xs. Por ejemplo,

-- juego [1,1,0,0,1] == [[1,1,0,0,1],[1,1,0,0],[1,1,1],[1,1],[1]]

-- juego [1,1,0,0,1] == [[1,1,0,0,1],[0,1,1,0],[0,0,1],[1,1],[1]]

-- juego [1,1,0,0,0] == [[1,1,0,0,0],[0,1,0,0],[1,1,0],[0,1],[0]]

juego :: [Int] -> [[Int]]

juego xs = takeWhile (not . null) (iterate paso xs)

-- (ultima xs) es la bola que queda en la bolsa al final del juego de

-- Dijkstra. Por ejemplo,

-- ultima [1,0,0,1] == 1

ultima :: [Int] -> Int

ultima = head . last . juego

-- (numeroDeCeros xs) es el número de ceros en xs. Por ejemplo,

-- numeroDeCeros [1,0,0,1,0] == 3

numeroDeCeros :: [Int] -> Int

numeroDeCeros xs = length (filter (==0) xs)

-- Propiedad. La bola que queda en la bolsa al final del juego de

-- Dijkstra es blanca si, y sólo si, el número de bolas blancas en la

-- bolsa inicial es impar.

prop_Dijkstra :: [Int] -> Property

prop_Dijkstra xs =

not (null xs) ==> (ultima ys == 0) == odd (numeroDeCeros ys)

where ys = [x `mod` 2 | x <- xs]

-- La comprobación es

-- ghci> quickCheck prop_Dijkstra

-- +++ OK, passed 100 tests.

Reparto de escaños por la ley d’Hont

PorJosé A. Alonso 26-mayo-201525-abril-2021

El sistema D’Hondt es una fórmula electoral, creada por Victor d’Hondt, que permite obtener el número de cargos electos asignados a las candidaturas, en proporción a los votos conseguidos.

Tras el recuento de los votos, se calcula una serie de divisores para cada partido. La fórmula de los divisores es V/N, donde V representa el número total de votos recibidos por el partido, y N representa cada uno de los números enteros desde 1 hasta el número de cargos electos de la circunscripción objeto de escrutinio. Una vez realizadas las divisiones de los votos de cada partido por cada uno de los divisores desde 1 hasta N, la asignación de cargos electos se hace ordenando los cocientes de las divisiones de mayor a menor y asignando a cada uno un escaño hasta que éstos se agoten

Definir la función

   reparto :: Int -> [Int] -> [(Int,Int)]

1	reparto :: Int -> [Int] -> [(Int,Int)]

tal que (reparto n vs) es la lista de los pares formados por los números de los partidos y el número de escaño que les corresponden al repartir n escaños en función de la lista de sus votos. Por ejemplo,

   ghci> reparto 7 [340000,280000,160000,60000,15000]
   [(1,3),(2,3),(3,1)]
   ghci> reparto 21 [391000,311000,184000,73000,27000,12000,2000]
   [(1,9),(2,7),(3,4),(4,1)]

ghci> reparto 7 [340000,280000,160000,60000,15000]

[(1,3),(2,3),(3,1)]

ghci> reparto 21 [391000,311000,184000,73000,27000,12000,2000]

[(1,9),(2,7),(3,4),(4,1)]

es decir, en el primer ejemplo,

al 1º partido (que obtuvo 340000 votos) le corresponden 3 escaños,
al 2º partido (que obtuvo 280000 votos) le corresponden 3 escaños,
al 3º partido (que obtuvo 160000 votos) le corresponden 1 escaño.

Soluciones

import Data.List (sort, group)

-- Para los ejemplos que siguen, se usará la siguiente ditribución de
-- votos entre 5 partidos.
ejVotos :: [Int]
ejVotos = [340000,280000,160000,60000,15000]

ejVotos2 :: [Int]
ejVotos2 = [391000,311000,184000,73000,27000,12000,2000]

-- ghci> reparto 21 ejVotos2
-- [(1,9),(2,7),(3,4),(4,1)]

ejVotos3 :: [Int]
ejVotos3 = [221,195,40,6,4]

-- (votosPartidos vs) es la lista con los pares formados por los votos y
-- el número de cada partido. Por ejemplo, 
--    ghci> votosPartidos ejVotos
--    [(340000,1),(280000,2),(160000,3),(60000,4),(15000,5)]
votosPartidos :: [Int] -> [(Int,Int)]
votosPartidos vs = zip vs [1..]

-- (restos n (x,i)) es la lista obtenidas dividiendo n entre 1, 2,..., n.
-- Por ejemplo, 
--    ghci> restos 5 (340000,1)
--    [(340000,1),(170000,1),(113333,1),(85000,1),(68000,1)]
restos :: Int -> (Int,Int) -> [(Int,Int)]
restos n (x,i) = [(x `div` k,i) | k <- [1..n]]

-- (reparto1 n vs) es la lista formada por los n restos mayores
-- correspondientes a la lista de votos vs. Por ejemplo,
--    ghci> reparto1 7 ejVotos
--    [(340000,1),(280000,2),(170000,1),(160000,3),(140000,2),(113333,1),
--     (93333,2)]
reparto1 :: Int -> [Int] -> [(Int,Int)]
reparto1 n vs = 
    take n $ reverse $ sort (concatMap (restos n) (votosPartidos vs))

-- (reparto2 n vs) es el número de los partidos, cuyos votos son vs, que
-- obtienen los n escaños. Por ejemplo,
--    ghci> reparto2 7 ejVotos
--    [1,2,1,3,2,1,2]
reparto2 :: Int -> [Int] -> [Int]
reparto2 n vs = map snd (reparto1 n vs)

-- (reparto n vs) es la lista de los pares formados por los números de
-- los partidos y el número de escaño que les corresponden al repartir n
-- escaños en función de la lista de sus votos. Por ejemplo, 
--    ghci> reparto 7 ejVotos
--    [(1,3),(2,3),(3,1)]
reparto :: Int -> [Int] -> [(Int,Int)]
reparto n vs = 
    [(x,1 + length xs) | (x:xs) <- group (sort (reparto2 n vs))]

import Data.List (sort, group)

-- Para los ejemplos que siguen, se usará la siguiente ditribución de

-- votos entre 5 partidos.

ejVotos :: [Int]

ejVotos = [340000,280000,160000,60000,15000]

ejVotos2 :: [Int]

ejVotos2 = [391000,311000,184000,73000,27000,12000,2000]

-- ghci> reparto 21 ejVotos2

-- [(1,9),(2,7),(3,4),(4,1)]

ejVotos3 :: [Int]

ejVotos3 = [221,195,40,6,4]

-- (votosPartidos vs) es la lista con los pares formados por los votos y

-- el número de cada partido. Por ejemplo,

-- ghci> votosPartidos ejVotos

-- [(340000,1),(280000,2),(160000,3),(60000,4),(15000,5)]

votosPartidos :: [Int] -> [(Int,Int)]

votosPartidos vs = zip vs [1..]

-- (restos n (x,i)) es la lista obtenidas dividiendo n entre 1, 2,..., n.

-- Por ejemplo,

-- ghci> restos 5 (340000,1)

-- [(340000,1),(170000,1),(113333,1),(85000,1),(68000,1)]

restos :: Int -> (Int,Int) -> [(Int,Int)]

restos n (x,i) = [(x `div` k,i) | k <- [1..n]]

-- (reparto1 n vs) es la lista formada por los n restos mayores

-- correspondientes a la lista de votos vs. Por ejemplo,

-- ghci> reparto1 7 ejVotos

-- [(340000,1),(280000,2),(170000,1),(160000,3),(140000,2),(113333,1),

-- (93333,2)]

reparto1 :: Int -> [Int] -> [(Int,Int)]

reparto1 n vs =

take n $ reverse $ sort (concatMap (restos n) (votosPartidos vs))

-- (reparto2 n vs) es el número de los partidos, cuyos votos son vs, que

-- obtienen los n escaños. Por ejemplo,

-- ghci> reparto2 7 ejVotos

-- [1,2,1,3,2,1,2]

reparto2 :: Int -> [Int] -> [Int]

reparto2 n vs = map snd (reparto1 n vs)

-- (reparto n vs) es la lista de los pares formados por los números de

-- los partidos y el número de escaño que les corresponden al repartir n

-- escaños en función de la lista de sus votos. Por ejemplo,

-- ghci> reparto 7 ejVotos

-- [(1,3),(2,3),(3,1)]

reparto :: Int -> [Int] -> [(Int,Int)]

reparto n vs =

[(x,1 + length xs) | (x:xs) <- group (sort (reparto2 n vs))]

Ciclos de un grafo

PorJosé A. Alonso 18-mayo-201526-marzo-2022

Un ciclo en un grafo G es una secuencia [v(1),v(2),v(3),…,v(n)] de nodos de G tal que:

(v(1),v(2)), (v(2),v(3)), (v(3),v(4)), …, (v(n-1),v(n)) son aristas de G,
v(1) = v(n), y
salvo v(1) = v(n), todos los v(i) son distintos entre sí.

Definir la función

   ciclos :: Grafo Int Int -> [[Int]]

1	ciclos :: Grafo Int Int -> [[Int]]

tal que (ciclos g) es la lista de ciclos de g. Por ejemplo, si g1 y g2 son los grafos definidos por

   g1, g2 :: Grafo Int Int
   g1 = creaGrafo D (1,4) [(1,2,0),(2,3,0),(2,4,0),(4,1,0)]
   g2 = creaGrafo D (1,4) [(1,2,0),(2,1,0),(2,4,0),(4,1,0)]

g1, g2 :: Grafo Int Int

g1 = creaGrafo D (1,4) [(1,2,0),(2,3,0),(2,4,0),(4,1,0)]

g2 = creaGrafo D (1,4) [(1,2,0),(2,1,0),(2,4,0),(4,1,0)]

entonces

   ciclos g1  ==  [[1,2,4,1],[2,4,1,2],[4,1,2,4]]
   ciclos g2  ==  [[1,2,1],[1,2,4,1],[2,1,2],[2,4,1,2],[4,1,2,4]]

1 2	ciclos g1 == [[1,2,4,1],[2,4,1,2],[4,1,2,4]] ciclos g2 == [[1,2,1],[1,2,4,1],[2,1,2],[2,4,1,2],[4,1,2,4]]

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.

Soluciones

import Data.List (nub, subsequences, permutations, sort)
import I1M.Grafo

-- 1ª definición (por fuerza bruta)
-- ================================

ciclos1 :: Grafo Int Int -> [[Int]]
ciclos1 g = 
    sort [ys | (x:xs) <- concatMap permutations (subsequences (nodos g)) 
             , let ys = (x:xs) ++ [x]
             , esCiclo ys g]

-- (esCiclo vs g) se verifica si vs es un ciclo en el grafo g. Por
-- ejemplo, 
esCiclo :: [Int] -> Grafo Int Int -> Bool
esCiclo vs g = 
    all (aristaEn g) (zip vs (tail vs)) &&
    head vs == last vs &&
    length (nub vs) == length vs - 1    

-- 2ª definición
-- =============

ciclos2 :: Grafo Int Int -> [[Int]]
ciclos2 g = sort [ys | (x:xs) <- caminos g
                     , let ys = (x:xs) ++ [x]
                     , esCiclo ys g]

-- (caminos g) es la lista de los caminos en el grafo g. Por ejemplo,
--    caminos g1  ==  [[1,2,3],[1,2,4],[2,3],[2,4,1],[3],[4,1,2,3]]
caminos :: Grafo Int Int -> [[Int]]
caminos g = concatMap (caminosDesde g) (nodos g)

-- (caminosDesde g v) es la lista de los caminos en el grafo g a partir
-- del vértice v. Por ejemplo,
--    caminosDesde g1 1  ==  [[1],[1,2],[1,2,3],[1,2,4]]
--    caminosDesde g1 2  ==  [[2],[2,3],[2,4],[2,4,1]]
--    caminosDesde g1 3  ==  [[3]]
--    caminosDesde g1 4  ==  [[4],[4,1],[4,1,2],[4,1,2,3]]
caminosDesde :: Grafo Int Int -> Int -> [[Int]]
caminosDesde g v = 
    map (reverse . fst) $
    concat $ 
    takeWhile (not.null) (iterate (concatMap sucesores) [([v],[v])])
    where sucesores (x:xs,ys) = [(z:x:xs,z:ys) | z <- adyacentes g x
                                               , z `notElem` ys]

-- 3ª solución (Pedro Martín)
-- ==========================

ciclos3 :: Grafo Int Int -> [[Int]]
ciclos3 g = concat [aux [n] (adyacentes g n) | n <- nodos g] where 
    aux _ [] = []
    aux xs (y:ys)
        | notElem y xs = aux (xs ++ [y]) (adyacentes g y) ++ aux xs ys
        | y == head xs = (xs ++ [y]) : aux xs ys
        | otherwise    = aux xs ys

-- 4ª solución (Chema Cortés)
-- ==========================

ciclos4 :: Grafo Int Int -> [[Int]]
ciclos4 g = concat [ caminos a a [] | a <- nodos g ] where
    -- caminos posibles de b hasta a, sin pasar dos veces por un mismo nodo
    caminos a b vs
        | a == b && (not.null) vs = [[b]]
        | otherwise = [ b:xs | c <- adyacentes g b
                             , c `notElem` vs
                             , xs <- caminos a c (c:vs)]

-- Comparación de eficiencia
-- =========================

-- ghci> let ejemplo n = creaGrafo D (1,n) ((n,1,0) : [(i,i+1,0) | i <- [1..n-1]])
-- 
-- ghci> length (ciclos1 (ejemplo 9))
-- 9
-- (4.92 secs, 1371229152 bytes)
--
-- ghci> length (ciclos2 (ejemplo 9))
-- 9
-- (0.01 secs, 2577736 bytes)
-- 
-- ghci> length (ciclos3 (ejemplo 9))
-- 9
-- (0.01 secs, 1038932 bytes)
-- 
-- ghci> length (ciclos4 (ejemplo 9))
-- 9
-- (0.01 secs, 2589288 bytes)
-- 
-- ghci> length (ciclos2 (ejemplo 400))
-- 400
-- (11.74 secs, 5148997000 bytes)
-- 
-- ghci> length (ciclos3 (ejemplo 400))
-- 400
-- (4.99 secs, 936520100 bytes)
-- 
-- ghci> length (ciclos4 (ejemplo 400))
-- 400
-- (1.56 secs, 66701772 bytes)

100

101

102

import Data.List (nub, subsequences, permutations, sort)

import I1M.Grafo

-- 1ª definición (por fuerza bruta)

-- ================================

ciclos1 :: Grafo Int Int -> [[Int]]

ciclos1 g =

sort [ys | (x:xs) <- concatMap permutations (subsequences (nodos g))

, let ys = (x:xs) ++ [x]

, esCiclo ys g]

-- (esCiclo vs g) se verifica si vs es un ciclo en el grafo g. Por

-- ejemplo,

esCiclo :: [Int] -> Grafo Int Int -> Bool

esCiclo vs g =

all (aristaEn g) (zip vs (tail vs)) &&

head vs == last vs &&

length (nub vs) == length vs - 1

-- 2ª definición

-- =============

ciclos2 :: Grafo Int Int -> [[Int]]

ciclos2 g = sort [ys | (x:xs) <- caminos g

, let ys = (x:xs) ++ [x]

, esCiclo ys g]

-- (caminos g) es la lista de los caminos en el grafo g. Por ejemplo,

-- caminos g1 == [[1,2,3],[1,2,4],[2,3],[2,4,1],[3],[4,1,2,3]]

caminos :: Grafo Int Int -> [[Int]]

caminos g = concatMap (caminosDesde g) (nodos g)

-- (caminosDesde g v) es la lista de los caminos en el grafo g a partir

-- del vértice v. Por ejemplo,

-- caminosDesde g1 1 == [[1],[1,2],[1,2,3],[1,2,4]]

-- caminosDesde g1 2 == [[2],[2,3],[2,4],[2,4,1]]

-- caminosDesde g1 3 == [[3]]

-- caminosDesde g1 4 == [[4],[4,1],[4,1,2],[4,1,2,3]]

caminosDesde :: Grafo Int Int -> Int -> [[Int]]

caminosDesde g v =

map (reverse . fst) $

concat $

takeWhile (not.null) (iterate (concatMap sucesores) [([v],[v])])

where sucesores (x:xs,ys) = [(z:x:xs,z:ys) | z <- adyacentes g x

, z `notElem` ys]

-- 3ª solución (Pedro Martín)

-- ==========================

ciclos3 :: Grafo Int Int -> [[Int]]

ciclos3 g = concat [aux [n] (adyacentes g n) | n <- nodos g] where

aux _ [] = []

aux xs (y:ys)

| notElem y xs = aux (xs ++ [y]) (adyacentes g y) ++ aux xs ys

| y == head xs = (xs ++ [y]) : aux xs ys

| otherwise = aux xs ys

-- 4ª solución (Chema Cortés)

-- ==========================

ciclos4 :: Grafo Int Int -> [[Int]]

ciclos4 g = concat [ caminos a a [] | a <- nodos g ] where

-- caminos posibles de b hasta a, sin pasar dos veces por un mismo nodo

caminos a b vs

| a == b && (not.null) vs = [[b]]

| otherwise = [ b:xs | c <- adyacentes g b

, c `notElem` vs

, xs <- caminos a c (c:vs)]

-- Comparación de eficiencia

-- =========================

-- ghci> let ejemplo n = creaGrafo D (1,n) ((n,1,0) : [(i,i+1,0) | i <- [1..n-1]])

-- ghci> length (ciclos1 (ejemplo 9))

-- 9

-- (4.92 secs, 1371229152 bytes)

-- ghci> length (ciclos2 (ejemplo 9))

-- 9

-- (0.01 secs, 2577736 bytes)

-- ghci> length (ciclos3 (ejemplo 9))

-- 9

-- (0.01 secs, 1038932 bytes)

-- ghci> length (ciclos4 (ejemplo 9))

-- 9

-- (0.01 secs, 2589288 bytes)

-- ghci> length (ciclos2 (ejemplo 400))

-- 400

-- (11.74 secs, 5148997000 bytes)

-- ghci> length (ciclos3 (ejemplo 400))

-- 400

-- (4.99 secs, 936520100 bytes)

-- ghci> length (ciclos4 (ejemplo 400))

-- 400

-- (1.56 secs, 66701772 bytes)

El teorema de Midy

PorJosé A. Alonso 12-mayo-201513-junio-2015

El ejercicio de hoy, propuesto por Antonio García Blázquez, tiene como objetivo comprobar la veracidad del Teorema de Midy, este teorema dice:

Sea a/p una fracción, donde a < p y p > 5 es un número primo. Si esta fracción tiene una expansión decimal periódica, donde la cantidad de dígitos en el período es par, entonces podemos partir el período en dos mitades, cuya suma es un número formado únicamente por nueves.

Por ejemplo, 2/7 = 0’285714285714… El período es 285714, cuya longitud es par (6). Lo partimos por la mitad y las sumamos: 285+714 = 999.

Definir la función

   teoremaMidy :: Integer -> Bool

1	teoremaMidy :: Integer -> Bool

tal que (teoremaMidy n) se verifica si para todo todo número primo p menor que n y mayor que 5 y todo número natural a menor que p tales que la cantidad de dígitos en el período de a/p es par, entonces podemos partir el período de a/p en dos mitades, cuya suma es un número formado únicamente por nueves. Por ejemplo,

   teoremaMidy 200  ==  True

1	teoremaMidy 200 == True

Además, comprobar el teorema de Midy usando QuickCheck.

Soluciones

import Data.List (genericTake)
import Data.Numbers.Primes (primes, isPrime)
import Test.QuickCheck

teoremaMidy :: Integer -> Bool
teoremaMidy n = 
    all conclusionMidy [(a,p) | p <- takeWhile (<n) (drop 3 primes),
                                a <- [1..p-1],
                                tienePeriodoDeLongitudPar (a,p)]

-- (tienePeriodoDeLongitudPar (a,p)) se verifica si el período de a/p
-- (con p un primo mayor que 5 y que a) es de longitud par. Por ejemplo,  
--    tienePeriodoDeLongitudPar (1,7)   ==  True
--    tienePeriodoDeLongitudPar (1,37)  ==  False
tienePeriodoDeLongitudPar :: (Integer,Integer) -> Bool
tienePeriodoDeLongitudPar (a,p) =
    even (longitudPeriodo p)

-- (expansionDec (a,p)) es la expansión decimal de a/p. Por ejemplo, 
--    take 10 (expansionDec (1,4))    ==  [0,2,5]
--    take 10 (expansionDec (1,7))    ==  [0,1,4,2,8,5,7,1,4,2]
--    take 12 (expansionDec (90,7))   ==  [12,8,5,7,1,4,2,8,5,7,1,4]
--    take 12 (expansionDec (23,14))  ==  [1,6,4,2,8,5,7,1,4,2,8,5]
expansionDec :: (Integer,Integer) -> [Integer]
expansionDec (x,y) 
    | r == 0    = [q] 
    | otherwise = q : expansionDec (r*10,y)
    where (q,r) = quotRem x y

-- (longitudPeriodo p) es la longitud del período de 1/p (y de
-- cualquier fracción irreducible de denominador p), donde p es un
-- número primo mayor que 5. Por ejemplo, 
--    longitudPeriodo 7   ==  6
--    longitudPeriodo 37  ==  3
--    longitudPeriodo 83  ==  41
longitudPeriodo :: Integer -> Integer
longitudPeriodo p = head [k | k <- [1..], 10^k `mod` p == 1]

-- (periodo (a,p)) es el período de a/b (para a < p y p > 5 es primo). 
-- Por ejemplo, 
--    periodo (1,7)   ==  [1,4,2,8,5,7]
--    periodo (2,7)   ==  [2,8,5,7,1,4]
--    periodo (6,7)   ==  [8,5,7,1,4,2]
--    periodo (1,73)  ==  [0,1,3,6,9,8,6,3]
periodo :: (Integer,Integer) -> [Integer]
periodo (a,p) = genericTake t xs
    where (_:xs) = expansionDec (a,p)
          t      = longitudPeriodo p

-- (conclusionMidy (a,p)) se verifica si a/p verifica la conclusión del
-- teorema de Midy; es decir, podemos partir el período de a/p en dos
-- mitades, cuya suma es un número formado únicamente por nueves. Por
-- ejemplo,  
--    conclusionMidy (1,7)   ==  True
--    conclusionMidy (1,37)  ==  False
conclusionMidy :: (Integer,Integer) -> Bool
conclusionMidy (a,p) = 
    all (==9) (zipWith (+) ys zs)
    where xs      = periodo (a,p)
          (ys,zs) = splitAt (length xs `div` 2) xs

-- ---------------------------------------------------------------------
-- § Comprobación con QuickCheck                                      --
-- ---------------------------------------------------------------------

-- (condicionMidy (a,p)) se verifica si a/p cumple las condiciones del
-- teorema de Midy. Por ejemplo,
--    condicionMidy (1,7)   ==  True
--    condicionMidy (1,37)  ==  False
condicionMidy :: (Integer,Integer) -> Bool
condicionMidy (a,p) = 
    a > 0 && 
    a < p && 
    isPrime p && 
    p > 5 && 
    tienePeriodoDeLongitudPar (a,p)

-- La propiedad es 
prop_teoremaMidy :: (Integer,Integer) -> Property
prop_teoremaMidy (a,p) = 
    condicionMidy (a,p) ==> conclusionMidy (a,p)

-- La comprobación es 
--    ghci> quickCheck prop_teoremaMidy
--    *** Gave up! Passed only 24 tests.

-- En la comprobación se observa que la mayoría de los ejemplos
-- generados no cumplen la condición del teorema de Midy y sólo 24 de
-- ellos la cumplen y también la conclusión. 

-- Para aumentar el número de casos en lo que se cumpla la condición, se
-- puede aumentar el valor de maxSuccess; por ejemplo,   
--    ghci> quickCheckWith (stdArgs {maxSuccess=700}) prop_teoremaMidy
--    *** Gave up! Passed only 137 tests.

-- Otra forma de conseguirlo es definir un generador de números de Midy
-- (es decir, de pares (a,p) que cumplan la condición del teorema de
-- Midy). Por ejemplo, 
--    ghci> sample numeroMidy
--    (15,19)
--    (5,7)
--    (1,23)
--    (7,11)
numeroMidy :: Gen (Integer,Integer)
numeroMidy = suchThat arbitrary condicionMidy

-- La propiedad es
prop_teoremaMidy2 :: Property
prop_teoremaMidy2 = forAll numeroMidy conclusionMidy

-- La comprobación es
--    ghci> quickCheck prop_teoremaMidy2
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

import Data.List (genericTake)

import Data.Numbers.Primes (primes, isPrime)

import Test.QuickCheck

teoremaMidy :: Integer -> Bool

teoremaMidy n =

all conclusionMidy [(a,p) | p <- takeWhile (<n) (drop 3 primes),

a <- [1..p-1],

tienePeriodoDeLongitudPar (a,p)]

-- (tienePeriodoDeLongitudPar (a,p)) se verifica si el período de a/p

-- (con p un primo mayor que 5 y que a) es de longitud par. Por ejemplo,

-- tienePeriodoDeLongitudPar (1,7) == True

-- tienePeriodoDeLongitudPar (1,37) == False

tienePeriodoDeLongitudPar :: (Integer,Integer) -> Bool

tienePeriodoDeLongitudPar (a,p) =

even (longitudPeriodo p)

-- (expansionDec (a,p)) es la expansión decimal de a/p. Por ejemplo,

-- take 10 (expansionDec (1,4)) == [0,2,5]

-- take 10 (expansionDec (1,7)) == [0,1,4,2,8,5,7,1,4,2]

-- take 12 (expansionDec (90,7)) == [12,8,5,7,1,4,2,8,5,7,1,4]

-- take 12 (expansionDec (23,14)) == [1,6,4,2,8,5,7,1,4,2,8,5]

expansionDec :: (Integer,Integer) -> [Integer]

expansionDec (x,y)

| r == 0 = [q]

| otherwise = q : expansionDec (r*10,y)

where (q,r) = quotRem x y

-- (longitudPeriodo p) es la longitud del período de 1/p (y de

-- cualquier fracción irreducible de denominador p), donde p es un

-- número primo mayor que 5. Por ejemplo,

-- longitudPeriodo 7 == 6

-- longitudPeriodo 37 == 3

-- longitudPeriodo 83 == 41

longitudPeriodo :: Integer -> Integer

longitudPeriodo p = head [k | k <- [1..], 10^k `mod` p == 1]

-- (periodo (a,p)) es el período de a/b (para a < p y p > 5 es primo).

-- Por ejemplo,

-- periodo (1,7) == [1,4,2,8,5,7]

-- periodo (2,7) == [2,8,5,7,1,4]

-- periodo (6,7) == [8,5,7,1,4,2]

-- periodo (1,73) == [0,1,3,6,9,8,6,3]

periodo :: (Integer,Integer) -> [Integer]

periodo (a,p) = genericTake t xs

where (_:xs) = expansionDec (a,p)

t = longitudPeriodo p

-- (conclusionMidy (a,p)) se verifica si a/p verifica la conclusión del

-- teorema de Midy; es decir, podemos partir el período de a/p en dos

-- mitades, cuya suma es un número formado únicamente por nueves. Por

-- ejemplo,

-- conclusionMidy (1,7) == True

-- conclusionMidy (1,37) == False

conclusionMidy :: (Integer,Integer) -> Bool

conclusionMidy (a,p) =

all (==9) (zipWith (+) ys zs)

where xs = periodo (a,p)

(ys,zs) = splitAt (length xs `div` 2) xs

-- ---------------------------------------------------------------------

-- § Comprobación con QuickCheck --

-- ---------------------------------------------------------------------

-- (condicionMidy (a,p)) se verifica si a/p cumple las condiciones del

-- teorema de Midy. Por ejemplo,

-- condicionMidy (1,7) == True

-- condicionMidy (1,37) == False

condicionMidy :: (Integer,Integer) -> Bool

condicionMidy (a,p) =

a > 0 &&

a < p &&

isPrime p &&

p > 5 &&

tienePeriodoDeLongitudPar (a,p)

-- La propiedad es

prop_teoremaMidy :: (Integer,Integer) -> Property

prop_teoremaMidy (a,p) =

condicionMidy (a,p) ==> conclusionMidy (a,p)

-- La comprobación es

-- ghci> quickCheck prop_teoremaMidy

-- *** Gave up! Passed only 24 tests.

-- En la comprobación se observa que la mayoría de los ejemplos

-- generados no cumplen la condición del teorema de Midy y sólo 24 de

-- ellos la cumplen y también la conclusión.

-- Para aumentar el número de casos en lo que se cumpla la condición, se

-- puede aumentar el valor de maxSuccess; por ejemplo,

-- ghci> quickCheckWith (stdArgs {maxSuccess=700}) prop_teoremaMidy

-- *** Gave up! Passed only 137 tests.

-- Otra forma de conseguirlo es definir un generador de números de Midy

-- (es decir, de pares (a,p) que cumplan la condición del teorema de

-- Midy). Por ejemplo,

-- ghci> sample numeroMidy

-- (15,19)

-- (5,7)

-- (1,23)

-- (7,11)

numeroMidy :: Gen (Integer,Integer)

numeroMidy = suchThat arbitrary condicionMidy

-- La propiedad es

prop_teoremaMidy2 :: Property

prop_teoremaMidy2 = forAll numeroMidy conclusionMidy

-- La comprobación es

-- ghci> quickCheck prop_teoremaMidy2

-- +++ OK, passed 100 tests.

Representación decimal de números racionales

PorJosé A. Alonso 11-mayo-201525-abril-2021

Continuando con los ejercicios propuestos por los alumnos, Antonio García Blázquez ha propuesto un ejercicio que usa el período de los números decimales. El ejercicio de hoy, basado en su propuesta, trata de la representación decimal de los números racionales.

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

    6/2  = 3                  se representa por (3,[],[])
    1/2  = 0.5                se representa por (0,[5],[])
    1/3  = 0.333333...        se representa por (0,[],[3])  
   23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

6/2 = 3 se representa por (3,[],[])

1/2 = 0.5 se representa por (0,[5],[])

1/3 = 0.333333... se representa por (0,[],[3])

23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

   type Decimal = (Integer,[Integer],[Integer])

1	type Decimal = (Integer,[Integer],[Integer])

Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

   type Racional = (Integer,Integer)

1	type Racional = (Integer,Integer)

Definir las funciones

   decimal  :: Racional -> Decimal
   racional :: Decimal -> Racional

1 2	decimal :: Racional -> Decimal racional :: Decimal -> Racional

tales que

(decimal r) es la representación decimal del número racional r. Por ejemplo,

        decimal (1,4)    ==  (0,[2,5],[])
        decimal (1,3)    ==  (0,[],[3])
        decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])

decimal (1,4) == (0,[2,5],[])

decimal (1,3) == (0,[],[3])

decimal (23,14) == (1,[6],[4,2,8,5,7,1])

(racional d) es el número racional cuya representación decimal es d. Por ejemplo,

        racional (0,[2,5],[])           ==  (1,4)
        racional (0,[],[3])             ==  (1,3)
        racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)

racional (0,[2,5],[]) == (1,4)

racional (0,[],[3]) == (1,3)

racional (1,[6],[4,2,8,5,7,1]) == (23,14)

Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,

   ghci> let (_,_,p) = decimal (23,14) in concatMap show p
   "428571"
   ghci> let (_,_,p) = decimal (1,47) in concatMap show p
   "0212765957446808510638297872340425531914893617"
   ghci> let (_,_,p) = decimal (1,541) in length (concatMap show p)
   540

ghci> let (_,_,p) = decimal (23,14) in concatMap show p

"428571"

ghci> let (_,_,p) = decimal (1,47) in concatMap show p

"0212765957446808510638297872340425531914893617"

ghci> let (_,_,p) = decimal (1,541) in length (concatMap show p)

540

Comprobar con QuickCheck si las funciones decimal y racional son inversas.

Soluciones

-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------

import Data.List
import Test.QuickCheck

-- ---------------------------------------------------------------------
-- § Tipos                                                            --
-- ---------------------------------------------------------------------

-- Un número racional se representa por un par de enteros, donde el
-- primer elemento es el numerador y el segundo el denominador.
type Racional = (Integer,Integer)

-- Un número decimal es una terna donde el primer elemento es la parte
-- entera, el segundo es el anteperíodo y el tercero es el período.
type Decimal = (Integer,[Integer],[Integer])

-- ---------------------------------------------------------------------
-- § De racional a decimal                                            --
-- ---------------------------------------------------------------------

-- (mayorExponente a x) es el mayor n tal que a^n divide a x. Por ejemplo,
--    mayorExponente 2 40  ==  3
--    mayorExponente 5 40  ==  1
--    mayorExponente 5 41  ==  0
mayorExponente :: Integer -> Integer -> Integer
mayorExponente a x = head [n | n <- [1..], mod x (a^n) /= 0] - 1

-- (longitudAnteperiodo n) es la longitud del anteperíodo de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo, 
--    longitudAnteperiodo 2   ==  1
--    longitudAnteperiodo 3   ==  0
--    longitudAnteperiodo 14  ==  1
longitudAnteperiodo :: Integer -> Integer
longitudAnteperiodo n = max (mayorExponente 2 n) (mayorExponente 5 n)

-- (longitudPeriodo n) es la longitud del período de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo, 
--    longitudPeriodo 2  ==  0
--    longitudPeriodo 3  ==  1
--    longitudPeriodo 7  ==  6
longitudPeriodo :: Integer -> Integer
longitudPeriodo n
    | m == 1    = 0 
    | otherwise = head [k | k <- [1..], (10^k) `mod` m == 1]
    where m = n `div` (2^(mayorExponente 2 n) * 5^(mayorExponente 5 n))

-- (expansionDec (x,y)) es la expansión decimal de x/y. Por ejemplo, 
--    take 10 (expansionDec (1,4))    ==  [0,2,5]
--    take 10 (expansionDec (1,7))    ==  [0,1,4,2,8,5,7,1,4,2]
--    take 12 (expansionDec (90,7))   ==  [12,8,5,7,1,4,2,8,5,7,1,4]
--    take 12 (expansionDec (23,14))  ==  [1,6,4,2,8,5,7,1,4,2,8,5]
expansionDec :: Racional -> [Integer]
expansionDec (x,y) 
    | r == 0    = [q] 
    | otherwise = q : expansionDec (r*10,y)
    where (q,r) = quotRem x y

-- (parteEntera (a,b)) es la parte entera de a/b. Por ejemplo,
--    parteEntera (125,3)  ==  41
parteEntera :: Racional -> Integer
parteEntera (a,b) = a `div` b

-- (antePeriodo (a,b)) es el anteperíodo de a/b; es decir, la lista de
-- cifras que se encuentran entre la parte entera y el primer período de
-- a/b. Por ejemplo,
--    antePeriodo (23,14)  ==  [6]
--    antePeriodo (1,5)    ==  [2]
antePeriodo :: Racional -> [Integer]
antePeriodo (a,b) = genericTake s (tail xs)
    where xs = expansionDec (a,b)
          s  = longitudAnteperiodo b

-- (periodo (a,b)) es el período de a/b. Por ejemplo, 
--    periodo (1,3)                   ==  [3]
--    periodo (1,5)                   ==  []
--    periodo (1,7)                   ==  [1,4,2,8,5,7]
--    periodo (23,14)                 ==  [4,2,8,5,7,1]
--    concatMap show $ periodo (1,29) == "0344827586206896551724137931"
periodo :: Racional -> [Integer]
periodo (a,b) = genericTake t (genericDrop (1+s) xs)
    where xs = expansionDec (a,b)
          s  = longitudAnteperiodo b
          t  = longitudPeriodo b

-- (reducido (a,b)) es la forma reducida del número racional a/b. Por
-- ejemplo, 
--    reducido (40,80)  ==  (1,2)
reducido :: Racional -> Racional
reducido (a,b) = (a `div` m, b `div` m) 
    where m = gcd a b

-- (decimal (x,y)) es la forma decimal de x/y; es decir, la terna
-- formada por la parte entera, la parte decimal pura y la parte decimal
-- periódica. Por ejemplo, 
--    decimal (1,4)    ==  (0,[2,5],[])
--    decimal (1,3)    ==  (0,[],[3])
--    decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])
decimal :: Racional -> Decimal
decimal (a,b) = (parteEntera r, antePeriodo r, periodo r)
    where r = reducido (a,b)

-- ---------------------------------------------------------------------
-- § De decimal a racional                                            --
-- ---------------------------------------------------------------------

-- (digitosAnumero xs) es el número correspondiente a la lista de
-- dígitos xs. Por ejemplo,
--    digitosAnumero [3,2,5]  ==  325
digitosAnumero :: [Integer] -> Integer
digitosAnumero = foldl (\a y -> 10*a+y) 0

-- 2ª definición de digitosAnumero (por comprensión)
digitosAnumero2 :: [Integer] -> Integer
digitosAnumero2 xs = sum [x*(10^i) | (x,i) <- zip xs [n-1,n-2..0]]
    where n = length xs

-- (racional (x,ys,zs)) es el número racional cuya representación
-- decimal es (x,ys,zs). Por ejemplo,
--    racional (0,[2,5],[])           ==  (1,4)
--    racional (0,[],[3])             ==  (1,3)
--    racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)
racional :: Decimal -> Racional
racional (x,ys,[]) = reducido (a,b) where
    a = digitosAnumero (x:ys)
    b = 10^(length ys)
racional (x,ys,zs) = reducido (a,b) where 
    a = digitosAnumero (x:ys++zs) - digitosAnumero (x:ys)
    b = digitosAnumero (replicate (length zs) 9 ++ replicate (length ys) 0)

-- ---------------------------------------------------------------------
-- § Propiedades                                                      --
-- ---------------------------------------------------------------------

-- La 1ª propiedad es
prop_RacionalDecimal :: Racional -> Property
prop_RacionalDecimal (a,b) =
    a >= 0 && b > 0  ==>
    racional (decimal (a,b)) == reducido (a,b)

-- La comprobación es 
--    ghci> quickCheck prop_RacionalDecimal
--    +++ OK, passed 100 tests.

-- En lugar de reducido se puede usar un generador de números racionales
numeroRacional :: Gen Racional
numeroRacional = do a <- arbitrary
                    b <- arbitrary
                    return (reducido (abs a, 1+ abs b))

-- La propiedad es
prop_RacionalDecimal2 :: Property
prop_RacionalDecimal2 =
    forAll numeroRacional
           (\(a,b) -> racional (decimal (a,b)) == (a,b))

-- La comprobación es
--   ghci> quickCheck prop_RacionalDecimal2
--   +++ OK, passed 100 tests.

-- Para la 2ª propiedad se define un generador de números decimales
numeroDecimal :: Gen Decimal
numeroDecimal = do a <- arbitrary
                   b <- arbitrary
                   return (decimal (abs a, 1+ abs b))

-- La 2ª propiedad es
prop_DecimalRacional :: Property
prop_DecimalRacional =
    forAll numeroDecimal 
           (\(x,ys,zs) -> decimal (racional (x,ys,zs)) == (x,ys,zs))

-- La comprobación es
--   ghci> quickCheck prop_DecimalRacional
--   +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

-- ---------------------------------------------------------------------

-- § Librerías auxiliares --

-- ---------------------------------------------------------------------

import Data.List

import Test.QuickCheck

-- ---------------------------------------------------------------------

-- § Tipos --

-- ---------------------------------------------------------------------

-- Un número racional se representa por un par de enteros, donde el

-- primer elemento es el numerador y el segundo el denominador.

type Racional = (Integer,Integer)

-- Un número decimal es una terna donde el primer elemento es la parte

-- entera, el segundo es el anteperíodo y el tercero es el período.

type Decimal = (Integer,[Integer],[Integer])

-- ---------------------------------------------------------------------

-- § De racional a decimal --

-- ---------------------------------------------------------------------

-- (mayorExponente a x) es el mayor n tal que a^n divide a x. Por ejemplo,

-- mayorExponente 2 40 == 3

-- mayorExponente 5 40 == 1

-- mayorExponente 5 41 == 0

mayorExponente :: Integer -> Integer -> Integer

mayorExponente a x = head [n | n <- [1..], mod x (a^n) /= 0] - 1

-- (longitudAnteperiodo n) es la longitud del anteperíodo de 1/n (y de

-- cualquier fracción irreducible de denominador n). Por ejemplo,

-- longitudAnteperiodo 2 == 1

-- longitudAnteperiodo 3 == 0

-- longitudAnteperiodo 14 == 1

longitudAnteperiodo :: Integer -> Integer

longitudAnteperiodo n = max (mayorExponente 2 n) (mayorExponente 5 n)

-- (longitudPeriodo n) es la longitud del período de 1/n (y de

-- cualquier fracción irreducible de denominador n). Por ejemplo,

-- longitudPeriodo 2 == 0

-- longitudPeriodo 3 == 1

-- longitudPeriodo 7 == 6

longitudPeriodo :: Integer -> Integer

longitudPeriodo n

| m == 1 = 0

| otherwise = head [k | k <- [1..], (10^k) `mod` m == 1]

where m = n `div` (2^(mayorExponente 2 n) * 5^(mayorExponente 5 n))

-- (expansionDec (x,y)) es la expansión decimal de x/y. Por ejemplo,

-- take 10 (expansionDec (1,4)) == [0,2,5]

-- take 10 (expansionDec (1,7)) == [0,1,4,2,8,5,7,1,4,2]

-- take 12 (expansionDec (90,7)) == [12,8,5,7,1,4,2,8,5,7,1,4]

-- take 12 (expansionDec (23,14)) == [1,6,4,2,8,5,7,1,4,2,8,5]

expansionDec :: Racional -> [Integer]

expansionDec (x,y)

| r == 0 = [q]

| otherwise = q : expansionDec (r*10,y)

where (q,r) = quotRem x y

-- (parteEntera (a,b)) es la parte entera de a/b. Por ejemplo,

-- parteEntera (125,3) == 41

parteEntera :: Racional -> Integer

parteEntera (a,b) = a `div` b

-- (antePeriodo (a,b)) es el anteperíodo de a/b; es decir, la lista de

-- cifras que se encuentran entre la parte entera y el primer período de

-- a/b. Por ejemplo,

-- antePeriodo (23,14) == [6]

-- antePeriodo (1,5) == [2]

antePeriodo :: Racional -> [Integer]

antePeriodo (a,b) = genericTake s (tail xs)

where xs = expansionDec (a,b)

s = longitudAnteperiodo b

-- (periodo (a,b)) es el período de a/b. Por ejemplo,

-- periodo (1,3) == [3]

-- periodo (1,5) == []

-- periodo (1,7) == [1,4,2,8,5,7]

-- periodo (23,14) == [4,2,8,5,7,1]

-- concatMap show $ periodo (1,29) == "0344827586206896551724137931"

periodo :: Racional -> [Integer]

periodo (a,b) = genericTake t (genericDrop (1+s) xs)

where xs = expansionDec (a,b)

s = longitudAnteperiodo b

t = longitudPeriodo b

-- (reducido (a,b)) es la forma reducida del número racional a/b. Por

-- ejemplo,

-- reducido (40,80) == (1,2)

reducido :: Racional -> Racional

reducido (a,b) = (a `div` m, b `div` m)

where m = gcd a b

-- (decimal (x,y)) es la forma decimal de x/y; es decir, la terna

-- formada por la parte entera, la parte decimal pura y la parte decimal

-- periódica. Por ejemplo,

-- decimal (1,4) == (0,[2,5],[])

-- decimal (1,3) == (0,[],[3])

-- decimal (23,14) == (1,[6],[4,2,8,5,7,1])

decimal :: Racional -> Decimal

decimal (a,b) = (parteEntera r, antePeriodo r, periodo r)

where r = reducido (a,b)

-- ---------------------------------------------------------------------

-- § De decimal a racional --

-- ---------------------------------------------------------------------

-- (digitosAnumero xs) es el número correspondiente a la lista de

-- dígitos xs. Por ejemplo,

-- digitosAnumero [3,2,5] == 325

digitosAnumero :: [Integer] -> Integer

digitosAnumero = foldl (\a y -> 10*a+y) 0

-- 2ª definición de digitosAnumero (por comprensión)

digitosAnumero2 :: [Integer] -> Integer

digitosAnumero2 xs = sum [x*(10^i) | (x,i) <- zip xs [n-1,n-2..0]]

where n = length xs

-- (racional (x,ys,zs)) es el número racional cuya representación

-- decimal es (x,ys,zs). Por ejemplo,

-- racional (0,[2,5],[]) == (1,4)

-- racional (0,[],[3]) == (1,3)

-- racional (1,[6],[4,2,8,5,7,1]) == (23,14)

racional :: Decimal -> Racional

racional (x,ys,[]) = reducido (a,b) where

a = digitosAnumero (x:ys)

b = 10^(length ys)

racional (x,ys,zs) = reducido (a,b) where

a = digitosAnumero (x:ys++zs) - digitosAnumero (x:ys)

b = digitosAnumero (replicate (length zs) 9 ++ replicate (length ys) 0)

-- ---------------------------------------------------------------------

-- § Propiedades --

-- ---------------------------------------------------------------------

-- La 1ª propiedad es

prop_RacionalDecimal :: Racional -> Property

prop_RacionalDecimal (a,b) =

a >= 0 && b > 0 ==>

racional (decimal (a,b)) == reducido (a,b)

-- La comprobación es

-- ghci> quickCheck prop_RacionalDecimal

-- +++ OK, passed 100 tests.

-- En lugar de reducido se puede usar un generador de números racionales

numeroRacional :: Gen Racional

numeroRacional = do a <- arbitrary

b <- arbitrary

return (reducido (abs a, 1+ abs b))

-- La propiedad es

prop_RacionalDecimal2 :: Property

prop_RacionalDecimal2 =

forAll numeroRacional

(\(a,b) -> racional (decimal (a,b)) == (a,b))

-- La comprobación es

-- ghci> quickCheck prop_RacionalDecimal2

-- +++ OK, passed 100 tests.

-- Para la 2ª propiedad se define un generador de números decimales

numeroDecimal :: Gen Decimal

numeroDecimal = do a <- arbitrary

b <- arbitrary

return (decimal (abs a, 1+ abs b))

-- La 2ª propiedad es

prop_DecimalRacional :: Property

prop_DecimalRacional =

forAll numeroDecimal

(\(x,ys,zs) -> decimal (racional (x,ys,zs)) == (x,ys,zs))

-- La comprobación es

-- ghci> quickCheck prop_DecimalRacional

-- +++ OK, passed 100 tests.

Potencias de primos con exponentes potencias de dos

PorJosé A. Alonso 8-mayo-201513-junio-2015

Se llaman potencias de Fermi-Dirac a los números de la forma p^(2^k), donde p es un número primo y k es un número natural.

Definir la sucesión

   potencias :: [Integer]

1	potencias :: [Integer]

cuyos términos sean las potencias de Fermi-Dirac ordenadas de menor a mayor. Por ejemplo,

   take 14 potencias    ==  [2,3,4,5,7,9,11,13,16,17,19,23,25,29]
   potencias !! 60      ==  241
   potencias !! (10^6)  ==  15476303

take 14 potencias == [2,3,4,5,7,9,11,13,16,17,19,23,25,29]

potencias !! 60 == 241

potencias !! (10^6) == 15476303

Soluciones

import Data.Numbers.Primes (primes)

potencias :: [Integer]
potencias = 2 : mezcla (tail primes) (map (^2) potencias)

-- (mezcla xs ys) es la lista obtenida mezclando las dos listas xs e ys,
-- que se suponen ordenadas y disjuntas. Por ejemplo,
--    ghci> take 15 (mezcla [2^n | n <- [1..]] [3^n | n <- [1..]])
--    [2,3,4,8,9,16,27,32,64,81,128,243,256,512,729]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys)
                     | x > y = y : mezcla (x:xs) ys

import Data.Numbers.Primes (primes)

potencias :: [Integer]

potencias = 2 : mezcla (tail primes) (map (^2) potencias)

-- (mezcla xs ys) es la lista obtenida mezclando las dos listas xs e ys,

-- que se suponen ordenadas y disjuntas. Por ejemplo,

-- ghci> take 15 (mezcla [2^n | n <- [1..]] [3^n | n <- [1..]])

-- [2,3,4,8,9,16,27,32,64,81,128,243,256,512,729]

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys)

| x > y = y : mezcla (x:xs) ys

Fracciones cancelativas

PorJosé A. Alonso 22-abril-201529-abril-2015

Una fracción x/y es cancelativa si se cumplen las siguientes condiciones:

x/y es propia (es decir, x < y),
ninguno de los números x e y son múltiplos de 10 y
existe un dígito d tal que al borrar una ocurrencia de d en x y otra en y se obtiene una fracción cuyo valor coincide con x/y.

Por ejemplo, 16/64 es cancelativa ya que borrando el 6 en el numerador y el denominador se obtiene 1/4 que es igual a la original: 16/64 = 1/4.

Definir la función

   cancelativas :: Int -> Int -> [((Int, Int), (Int, Int))]

1	cancelativas :: Int -> Int -> [((Int, Int), (Int, Int))]

tal que (cancelativas m n) es la lista de las fracciones cancelativas con su denominador entre m y n. Por ejemplo,

   ghci> cancelativas 1 100
   [((16,64),(1,4)),((26,65),(2,5)),((19,95),(1,5)),((49,98),(4,8))]
   ghci> cancelativas 101 150
   [((22,121),(2,11)),((33,132),(3,12)),((34,136),(4,16)),((44,143),(4,13))]
   ghci> length (cancelativas 1 200)
   18

ghci> cancelativas 1 100

[((16,64),(1,4)),((26,65),(2,5)),((19,95),(1,5)),((49,98),(4,8))]

ghci> cancelativas 101 150

[((22,121),(2,11)),((33,132),(3,12)),((34,136),(4,16)),((44,143),(4,13))]

ghci> length (cancelativas 1 200)

Soluciones

import Data.List (intersect, nub)

cancelativas :: Int -> Int -> [((Int, Int), (Int, Int))]
cancelativas m n = 
    nub [((x,y),(a,b))
         | y <- [m..n], 
           y `mod` 10 /= 0,
           x <- [1..y-1],
           x `mod` 10 /= 0,
           (as,bs) <- reducciones (show x) (show y),
           not (null as),
           not (null bs),
           let (a,b) = (read as, read bs),
           b /= 0,
           a*y == b*x]

-- (reducciones xs ys) es la lista de los pares obtenidos eliminando una
-- ocurrencia de un elemento de xs tanto en xs como en ys. Por ejemplo,
--    ghci> reducciones "abac" "bcba"
--    [("bac","bcb"),("abc","bcb"),
--     ("aac","cba"),("aac","bca"),
--     ("aba","bba")]
reducciones :: Eq a => [a] -> [a] -> [([a],[a])]
reducciones xs ys =
    concat [[(us,vs) | us <- eliminaciones xs x, vs <- eliminaciones ys x]
            | x <- nub (intersect xs ys)]

-- (eliminaciones xs y) es la lista de las listas obtenidas eliminando
-- una ocurrencia del elemento y en la lista xs. Por ejemplo,  
--    eliminaciones "abacda" 'a'  ==  ["bacda","abcda","abacd"]
--    eliminaciones "abacd"  'a'  ==  ["bacd","abcd"]
--    eliminaciones "abacd"  'b'  ==  ["aacd"]
--    eliminaciones "abacd"  'e'  ==  []
eliminaciones :: Eq a => [a] -> a -> [[a]]
eliminaciones [] _ = []
eliminaciones (x:xs) y
    | x == y    = xs : [x:zs | zs <- zss]
    | otherwise = [x:zs | zs <- zss]
    where zss = eliminaciones xs y

import Data.List (intersect, nub)

cancelativas :: Int -> Int -> [((Int, Int), (Int, Int))]

cancelativas m n =

nub [((x,y),(a,b))

| y <- [m..n],

y `mod` 10 /= 0,

x <- [1..y-1],

x `mod` 10 /= 0,

(as,bs) <- reducciones (show x) (show y),

not (null as),

not (null bs),

let (a,b) = (read as, read bs),

b /= 0,

a*y == b*x]

-- (reducciones xs ys) es la lista de los pares obtenidos eliminando una

-- ocurrencia de un elemento de xs tanto en xs como en ys. Por ejemplo,

-- ghci> reducciones "abac" "bcba"

-- [("bac","bcb"),("abc","bcb"),

-- ("aac","cba"),("aac","bca"),

-- ("aba","bba")]

reducciones :: Eq a => [a] -> [a] -> [([a],[a])]

reducciones xs ys =

concat [[(us,vs) | us <- eliminaciones xs x, vs <- eliminaciones ys x]

| x <- nub (intersect xs ys)]

-- (eliminaciones xs y) es la lista de las listas obtenidas eliminando

-- una ocurrencia del elemento y en la lista xs. Por ejemplo,

-- eliminaciones "abacda" 'a' == ["bacda","abcda","abacd"]

-- eliminaciones "abacd" 'a' == ["bacd","abcd"]

-- eliminaciones "abacd" 'b' == ["aacd"]

-- eliminaciones "abacd" 'e' == []

eliminaciones :: Eq a => [a] -> a -> [[a]]

eliminaciones [] _ = []

eliminaciones (x:xs) y

| x == y = xs : [x:zs | zs <- zss]

| otherwise = [x:zs | zs <- zss]

where zss = eliminaciones xs y

Caminos reducidos

PorJosé A. Alonso 21-abril-201525-abril-2021

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

   data Direccion = N | S | E | O deriving (Show, Eq)
   type Camino = [Direccion]

1 2	data Direccion = N \| S \| E \| O deriving (Show, Eq) type Camino = [Direccion]

Definir la función

   reducido :: Camino -> Camino

1	reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

   reducido []                              ==  []
   reducido [N]                             ==  [N]
   reducido [N,O]                           ==  [N,O]
   reducido [N,O,E]                         ==  [N]
   reducido [N,O,E,S]                       ==  [] 
   reducido [N,O,S,E]                       ==  [N,O,S,E]
   reducido [N,S,S,E,O,N]                   ==  []
   reducido [N,S,S,E,O,N,O]                 ==  [O]
   reducido (take (10^7) (cycle [N,E,O,S])) ==  []

reducido [] == []

reducido [N] == [N]

reducido [N,O] == [N,O]

reducido [N,O,E] == [N]

reducido [N,O,E,S] == []

reducido [N,O,S,E] == [N,O,S,E]

reducido [N,S,S,E,O,N] == []

reducido [N,S,S,E,O,N,O] == [O]

reducido (take (10^7) (cycle [N,E,O,S])) == []

Nótese que en el penúltimo ejemplo las reducciones son

       [N,S,S,E,O,N,O]  
   --> [S,E,O,N,O]  
   --> [S,N,O]  
   --> [O]

[N,S,S,E,O,N,O]

--> [S,E,O,N,O]

--> [S,N,O]

--> [O]

Soluciones

data Direccion = N | S | E | O deriving (Show, Eq)

type Camino = [Direccion]

-- 1ª solución (por recursión):
reducido1 :: Camino -> Camino
reducido1 [] = []
reducido1 (d:ds) | null ds'                = [d]
                 | d == opuesta (head ds') = tail ds'
                 | otherwise               = d:ds'
    where ds' = reducido1 ds

opuesta :: Direccion -> Direccion
opuesta N = S
opuesta S = N
opuesta E = O
opuesta O = E

-- 2ª solución (por plegado)
reducido2 :: Camino -> Camino
reducido2 = foldr aux []
    where aux N (S:xs) = xs
          aux S (N:xs) = xs
          aux E (O:xs) = xs
          aux O (E:xs) = xs
          aux x xs     = x:xs

-- 3ª solución 
reducido3 :: Camino -> Camino
reducido3 []       = []
reducido3 (N:S:ds) = reducido3 ds
reducido3 (S:N:ds) = reducido3 ds
reducido3 (E:O:ds) = reducido3 ds
reducido3 (O:E:ds) = reducido3 ds
reducido3 (d:ds) | null ds'                = [d]
                 | d == opuesta (head ds') = tail ds'
                 | otherwise               = d:ds'
    where ds' = reducido3 ds

-- 4ª solución
reducido4 :: Camino -> Camino
reducido4 ds = reverse (aux ([],ds)) where 
    aux (N:xs, S:ys) = aux (xs,ys)
    aux (S:xs, N:ys) = aux (xs,ys)
    aux (E:xs, O:ys) = aux (xs,ys)
    aux (O:xs, E:ys) = aux (xs,ys)
    aux (  xs, y:ys) = aux (y:xs,ys)
    aux (  xs,   []) = xs

-- Comparación de eficiencia
--    ghci> reducido1 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (3.87 secs, 460160736 bytes)
--    ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (1.16 secs, 216582880 bytes)
--    ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (0.58 secs, 98561872 bytes)
--    ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (0.64 secs, 176154640 bytes)
--    
--    ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))
--    []
--    (5.43 secs, 962694784 bytes)
--    ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))
--    []
--    (9.29 secs, 1722601528 bytes)
-- 
--    ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
--    400002
--    (4.52 secs, 547004960 bytes)
--    ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
--    400002
--    (2.17 secs, 379049224 bytes)
--    
--    ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S)
--    []
--    (7.35 secs, 537797096 bytes)
--    ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S)
--    []
--    (2.30 secs, 244553404 bytes)
--    ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S)
--    []
--    (8.08 secs, 545043608 bytes)
--    ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S)
--    []
--    (1.96 secs, 205552240 bytes)

data Direccion = N | S | E | O deriving (Show, Eq)

type Camino = [Direccion]

-- 1ª solución (por recursión):

reducido1 :: Camino -> Camino

reducido1 [] = []

reducido1 (d:ds) | null ds' = [d]

| d == opuesta (head ds') = tail ds'

| otherwise = d:ds'

where ds' = reducido1 ds

opuesta :: Direccion -> Direccion

opuesta N = S

opuesta S = N

opuesta E = O

opuesta O = E

-- 2ª solución (por plegado)

reducido2 :: Camino -> Camino

reducido2 = foldr aux []

where aux N (S:xs) = xs

aux S (N:xs) = xs

aux E (O:xs) = xs

aux O (E:xs) = xs

aux x xs = x:xs

-- 3ª solución

reducido3 :: Camino -> Camino

reducido3 [] = []

reducido3 (N:S:ds) = reducido3 ds

reducido3 (S:N:ds) = reducido3 ds

reducido3 (E:O:ds) = reducido3 ds

reducido3 (O:E:ds) = reducido3 ds

reducido3 (d:ds) | null ds' = [d]

| d == opuesta (head ds') = tail ds'

| otherwise = d:ds'

where ds' = reducido3 ds

-- 4ª solución

reducido4 :: Camino -> Camino

reducido4 ds = reverse (aux ([],ds)) where

aux (N:xs, S:ys) = aux (xs,ys)

aux (S:xs, N:ys) = aux (xs,ys)

aux (E:xs, O:ys) = aux (xs,ys)

aux (O:xs, E:ys) = aux (xs,ys)

aux ( xs, y:ys) = aux (y:xs,ys)

aux ( xs, []) = xs

-- Comparación de eficiencia

-- ghci> reducido1 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (3.87 secs, 460160736 bytes)

-- ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (1.16 secs, 216582880 bytes)

-- ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (0.58 secs, 98561872 bytes)

-- ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (0.64 secs, 176154640 bytes)

-- ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))

-- []

-- (5.43 secs, 962694784 bytes)

-- ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))

-- []

-- (9.29 secs, 1722601528 bytes)

-- ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])

-- 400002

-- (4.52 secs, 547004960 bytes)

-- ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])

-- 400002

-- (2.17 secs, 379049224 bytes)

-- ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S)

-- []

-- (7.35 secs, 537797096 bytes)

-- ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S)

-- []

-- (2.30 secs, 244553404 bytes)

-- ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S)

-- []

-- (8.08 secs, 545043608 bytes)

-- ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S)

-- []

-- (1.96 secs, 205552240 bytes)

Casas con números equilibrados

PorJosé A. Alonso 14-abril-20151-mayo-2015

Continuando con los problema propuestos por alumnos, el de hoy es el propuesto por Rafael Jiménez.

Se tiene una calle en la que las casas sólo están en un lado de ésta y las casas están numeradas de 1 hasta n, donde n es el número total de casas en la calle. Se dice que el número de una casa es equilibrado si y solamente si la suma de los números de las casas anteriores es igual a la suma de los números posteriores a la casa. Por ejemplo, el número de la 6ª casa, en una calle con 8 casas, es equilibrado ya que

   1 + 2 + 3 + 4 + 5 = 7 + 8

1	1 + 2 + 3 + 4 + 5 = 7 + 8

Definir la función

   soluciones :: Integer -> Integer -> [(Integer,Integer)]

1	soluciones :: Integer -> Integer -> [(Integer,Integer)]

tal que (soluciones x y) es la lista de pares (a,n) tales que a es el número equilibrado de una casa en una calle con n casas y n está entre x e y. Por ejemplo,

   soluciones 1 500          ==  [(1,1),(6,8),(35,49),(204,288)]
   soluciones 1000 3000      ==  [(1189,1681)]
   soluciones (10^5) (10^6)  ==  [(235416,332928)]
   soluciones (10^6) (10^7)  ==  [(1372105,1940449)]
   (fst $ head $ soluciones (10^100) (10^101))  `mod` (10^9)  ==  763728460
   (fst $ head $ soluciones (10^800) (10^1000)) `mod` (10^9)  ==  311156546

soluciones 1 500 == [(1,1),(6,8),(35,49),(204,288)]

soluciones 1000 3000 == [(1189,1681)]

soluciones (10^5) (10^6) == [(235416,332928)]

soluciones (10^6) (10^7) == [(1372105,1940449)]

(fst $ head $ soluciones (10^100) (10^101)) `mod` (10^9) == 763728460

(fst $ head $ soluciones (10^800) (10^1000)) `mod` (10^9) == 311156546

Soluciones

import Test.QuickCheck

-- 1ª solución
-- ===========

soluciones1 :: Integer -> Integer -> [(Integer,Integer)]
soluciones1 x y =
    [(n,n+m) | n <- [x..y], m <- [0..y-n], 
               sum [1..n-1] == sum [n+1..n+m]]
               
-- 2ª solución
-- ===========

soluciones2 :: Integer -> Integer -> [(Integer,Integer)]
soluciones2 x y =
    [(n,n+m) | n <- [x..y], m <- [0..y-n], 
               esSolucion (n,n+m)]

esSolucion :: (Integer,Integer) -> Bool
esSolucion (n,m) = suma (n-1) == suma m - suma n
    where suma n = n*(n+1) `div` 2
    
-- 3ª solución
-- ===========

-- Con las definiciones anteriores se pueden calcular los cuatro
-- primeros números de las casas equilibradas:
--    ghci> map fst (soluciones2 1 500)
--    [1,6,35,204]
-- Conjeturando que el n-ésimo número p(n) se calcula mediante una
-- recurrencia del tipo p(n) = x*p(n-1) + y*p(n-2) se tiene   
--    p(1) =   1
--    p(2) =   6
--    p(3) =  35 =  6x +  y
--    p(4) = 204 = 35x + 6y
-- al resolverlo se obtiene x = 6 e y = -1. Por tanto,
--    p(1) = 1
--    p(2) = 6
--    p(n) = 6*p(n-1) - p(n-2)
--
-- Haciendo lo mismo con las segundas componentes, 
--    ghci> map snd (soluciones2 1 2000)
--    [1,8,49,288,1681]
-- Conjeturando que el n-ésimo número s(n) se calcula mediante una
-- recurrencia del tipo s(n) = x*s(n-1) + y*s(n-2) + z se tiene   
--    s(1) =    1
--    s(2) =    8
--    s(3) =   49 =   8x +   y + z
--    s(4) =  288 =  49x +  8y + z
--    s(5) = 1681 = 288x + 49y + z 
-- al resolverlo se obtiene x = 6, y = -1, z = 2. Por tanto,
--    s(1) = 1
--    s(2) = 8
--    s(n) = 6*s(n-1) - s(n-2) + 2

-- El número de la n-ésimo casa equilibrada, p(n), se puede calcular por
-- recursión: 
casa :: Integer -> Integer
casa 1 = 1
casa 2 = 6
casa n = 6 * (casa (n-1)) - (casa (n-2))

-- La sucesión de los números de las casas equilibradas se puede
-- calcular por programación dinámica:
casas :: [Integer]
casas = 
    1 : 6 : zipWith (\x y -> 6*x-y) (tail casas) casas

-- El número de casas en la n-ésima calle con casas equilibradas, s(n),
-- se puede calcular por recursión: 
calle :: Integer -> Integer
calle 1 = 1
calle 2 = 8
calle n = 6 * (calle (n-1)) - (calle (n-2)) + 2

-- La sucesión de los números de las casas equilibradas se puede
-- calcular por programación dinámica:
calles :: [Integer]
calles = 
    1 : 8 : zipWith (\x y -> 6*x-y+2) (tail calles) calles

-- Usando casas se obtiene la 3ª solución:
soluciones3 :: Integer -> Integer -> [(Integer,Integer)]
soluciones3 x y =
   takeWhile (<=(y,y)) (dropWhile (<(x,x)) (zip casas calles))

-- Comprobación de soluciones
-- ==========================

-- La propiedad es
prop_soluciones :: Integer -> Integer -> Property
prop_soluciones x y =
    0 < x && x <= y ==>
    all esSolucion (soluciones3 x y)

-- La comprobación es
--    ghci> quickCheck prop_soluciones
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia:
--    ghci> soluciones1 1 2000
--    [(1,1),(6,8),(35,49),(204,288),(1189,1681)]
--    (337.30 secs, 396493594456 bytes)
--    ghci> soluciones2 1 2000
--    [(1,1),(6,8),(35,49),(204,288),(1189,1681)]
--    (23.47 secs, 3859436176 bytes)
--    ghci> soluciones3 1 2000
--    [(1,1),(6,8),(35,49),(204,288),(1189,1681)]
--    (0.01 secs, 1029592 bytes)

100

101

102

103

104

105

106

107

108

109

import Test.QuickCheck

-- 1ª solución

-- ===========

soluciones1 :: Integer -> Integer -> [(Integer,Integer)]

soluciones1 x y =

[(n,n+m) | n <- [x..y], m <- [0..y-n],

sum [1..n-1] == sum [n+1..n+m]]

-- 2ª solución

-- ===========

soluciones2 :: Integer -> Integer -> [(Integer,Integer)]

soluciones2 x y =

[(n,n+m) | n <- [x..y], m <- [0..y-n],

esSolucion (n,n+m)]

esSolucion :: (Integer,Integer) -> Bool

esSolucion (n,m) = suma (n-1) == suma m - suma n

where suma n = n*(n+1) `div` 2

-- 3ª solución

-- ===========

-- Con las definiciones anteriores se pueden calcular los cuatro

-- primeros números de las casas equilibradas:

-- ghci> map fst (soluciones2 1 500)

-- [1,6,35,204]

-- Conjeturando que el n-ésimo número p(n) se calcula mediante una

-- recurrencia del tipo p(n) = x*p(n-1) + y*p(n-2) se tiene

-- p(1) = 1

-- p(2) = 6

-- p(3) = 35 = 6x + y

-- p(4) = 204 = 35x + 6y

-- al resolverlo se obtiene x = 6 e y = -1. Por tanto,

-- p(1) = 1

-- p(2) = 6

-- p(n) = 6*p(n-1) - p(n-2)

-- Haciendo lo mismo con las segundas componentes,

-- ghci> map snd (soluciones2 1 2000)

-- [1,8,49,288,1681]

-- Conjeturando que el n-ésimo número s(n) se calcula mediante una

-- recurrencia del tipo s(n) = x*s(n-1) + y*s(n-2) + z se tiene

-- s(1) = 1

-- s(2) = 8

-- s(3) = 49 = 8x + y + z

-- s(4) = 288 = 49x + 8y + z

-- s(5) = 1681 = 288x + 49y + z

-- al resolverlo se obtiene x = 6, y = -1, z = 2. Por tanto,

-- s(1) = 1

-- s(2) = 8

-- s(n) = 6*s(n-1) - s(n-2) + 2

-- El número de la n-ésimo casa equilibrada, p(n), se puede calcular por

-- recursión:

casa :: Integer -> Integer

casa 1 = 1

casa 2 = 6

casa n = 6 * (casa (n-1)) - (casa (n-2))

-- La sucesión de los números de las casas equilibradas se puede

-- calcular por programación dinámica:

casas :: [Integer]

casas =

1 : 6 : zipWith (\x y -> 6*x-y) (tail casas) casas

-- El número de casas en la n-ésima calle con casas equilibradas, s(n),

-- se puede calcular por recursión:

calle :: Integer -> Integer

calle 1 = 1

calle 2 = 8

calle n = 6 * (calle (n-1)) - (calle (n-2)) + 2

-- La sucesión de los números de las casas equilibradas se puede

-- calcular por programación dinámica:

calles :: [Integer]

calles =

1 : 8 : zipWith (\x y -> 6*x-y+2) (tail calles) calles

-- Usando casas se obtiene la 3ª solución:

soluciones3 :: Integer -> Integer -> [(Integer,Integer)]

soluciones3 x y =

takeWhile (<=(y,y)) (dropWhile (<(x,x)) (zip casas calles))

-- Comprobación de soluciones

-- ==========================

-- La propiedad es

prop_soluciones :: Integer -> Integer -> Property

prop_soluciones x y =

0 < x && x <= y ==>

all esSolucion (soluciones3 x y)

-- La comprobación es

-- ghci> quickCheck prop_soluciones

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia:

-- ghci> soluciones1 1 2000

-- [(1,1),(6,8),(35,49),(204,288),(1189,1681)]

-- (337.30 secs, 396493594456 bytes)

-- ghci> soluciones2 1 2000

-- [(1,1),(6,8),(35,49),(204,288),(1189,1681)]

-- (23.47 secs, 3859436176 bytes)

-- ghci> soluciones3 1 2000

-- [(1,1),(6,8),(35,49),(204,288),(1189,1681)]

-- (0.01 secs, 1029592 bytes)

Caminos en un grafo

Soluciones

Problema de las bolas de Dijkstra

Soluciones

Reparto de escaños por la ley d’Hont

Soluciones

Ciclos de un grafo

Soluciones

El teorema de Midy

Soluciones

Representación decimal de números racionales

Soluciones

Potencias de primos con exponentes potencias de dos

Soluciones

Fracciones cancelativas

Soluciones

Caminos reducidos

Soluciones

Casas con números equilibrados

Soluciones

Entradas recientes

Buscar

Correo electrónico