Conmutaciones ondulantes

PorJosé A. Alonso 21-noviembre-201628-noviembre-2016

Una lista binaria es ondulante si sus elementos son alternativamente 0 y 1. Por ejemplo, las listas [0,1,0,1,0] y [1,0,1,0] son ondulantes.

Definir la función

   minConmutacionesOndulante :: [Int] -> Int

1	minConmutacionesOndulante :: [Int] -> Int

tal que (minConmutacionesOndulante xs) es el mínimo número de conmutaciones (es decir, cambios de 0 a 1 o de 1 a 0) necesarias para transformar xs en una lista ondulante. Por ejemplo,

   minConmutacionesOndulante [1,1,1]                ==  1
   minConmutacionesOndulante [0,0,0,1,0,1,0,1,1,1]  ==  2

1 2	minConmutacionesOndulante [1,1,1] == 1 minConmutacionesOndulante [0,0,0,1,0,1,0,1,1,1] == 2

En el primer ejemplo basta conmutar el elemento en la posición 1 para obtener [1,0,1] y el segundo ejemplo los elementos en las posiciones 1 y 8 para obtener [0,1,0,1,0,1,0,1,0,1].

Soluciones

minConmutacionesOndulante :: [Int] -> Int
minConmutacionesOndulante xs =
  min (diferencia xs ondulante0)
      (diferencia xs ondulante1)

-- (diferencia xs ys) es el número de posiciones con elementos
-- distintos. Por ejemplo,
--    diferencia [1,1,1] [1,0,1]            ==  1
--    diferencia "0001010111" "0101010101"  ==  2
diferencia :: Eq a => [a] -> [a] -> Int
diferencia xs ys =
  sum [1 | (x,y) <- zip xs ys, x /= y]

-- ondulante0 es la lista binaria ondulante cuyo primer elemento es
-- 0. Por ejemplo,
--    take 10 ondulante0  ==  [0,1,0,1,0,1,0,1,0,1]
ondulante0 :: [Int]
ondulante0 = 0 : ondulante1

-- ondulante1 es la lista binaria ondulante cuyo primer elemento es
-- 1. Por ejemplo,
--    take 10 ondulante1  ==  [1,0,1,0,1,0,1,0,1,0]
ondulante1 :: [Int]
ondulante1 = 1 : ondulante0

minConmutacionesOndulante :: [Int] -> Int

minConmutacionesOndulante xs =

min (diferencia xs ondulante0)

(diferencia xs ondulante1)

-- (diferencia xs ys) es el número de posiciones con elementos

-- distintos. Por ejemplo,

-- diferencia [1,1,1] [1,0,1] == 1

-- diferencia "0001010111" "0101010101" == 2

diferencia :: Eq a => [a] -> [a] -> Int

diferencia xs ys =

sum [1 | (x,y) <- zip xs ys, x /= y]

-- ondulante0 es la lista binaria ondulante cuyo primer elemento es

-- 0. Por ejemplo,

-- take 10 ondulante0 == [0,1,0,1,0,1,0,1,0,1]

ondulante0 :: [Int]

ondulante0 = 0 : ondulante1

-- ondulante1 es la lista binaria ondulante cuyo primer elemento es

-- 1. Por ejemplo,

-- take 10 ondulante1 == [1,0,1,0,1,0,1,0,1,0]

ondulante1 :: [Int]

ondulante1 = 1 : ondulante0

5 Comentarios

import Data.List (cycle)

minConmutacionesOndulante :: [Int] -> Int
minConmutacionesOndulante xs =
  min (dif xs (cycle [0,1])) (dif xs (cycle [1,0]))
  where dif xs ys = sum $ zipWith (\x y -> abs (x-y)) xs ys

import Data.List (cycle)

minConmutacionesOndulante :: [Int] -> Int

minConmutacionesOndulante xs =

min (dif xs (cycle [0,1])) (dif xs (cycle [1,0]))

where dif xs ys = sum $ zipWith (\x y -> abs (x-y)) xs ys

Responder

import Data.List (partition)

minConmutacionesOndulante :: [Int] -> Int
minConmutacionesOndulante xs =
  min (posImpares - nImpares + nPares) (nImpares + posPares - nPares) 
  where
    (pares, impares) = partition (even.fst) (zip [0..] xs)
    nPares           = sum (map snd pares)
    nImpares         = sum (map snd impares)
    posImpares       = div (length xs) 2
    posPares         = length xs - posImpares

import Data.List (partition)

minConmutacionesOndulante :: [Int] -> Int

minConmutacionesOndulante xs =

min (posImpares - nImpares + nPares) (nImpares + posPares - nPares)

where

(pares, impares) = partition (even.fst) (zip [0..] xs)

nPares = sum (map snd pares)

nImpares = sum (map snd impares)

posImpares = div (length xs) 2

posPares = length xs - posImpares

Responder

minConmutacionesOndulante :: [Int] -> Int
minConmutacionesOndulante xs =
  minimum [length (diferencias xs a) ,
           length (diferencias xs b)]
  where a = map (`mod` 2) [1..length xs]
        b = map (`mod` 2) [0..length xs - 1]

diferencias :: [Int] -> [Int] -> [Int]
diferencias [] ys = ys
diferencias (x:xs) (y:ys)
  | x == y    = diferencias xs ys
  | otherwise = x : diferencias xs ys

minConmutacionesOndulante :: [Int] -> Int

minConmutacionesOndulante xs =

minimum [length (diferencias xs a) ,

length (diferencias xs b)]

where a = map (`mod` 2) [1..length xs]

b = map (`mod` 2) [0..length xs - 1]

diferencias :: [Int] -> [Int] -> [Int]

diferencias [] ys = ys

diferencias (x:xs) (y:ys)

| x == y = diferencias xs ys

| otherwise = x : diferencias xs ys

Responder

import Data.List (intersperse)

minConmutacionesOndulanteA44 :: [Int] -> Int
minConmutacionesOndulanteA44 xs =
  minimum [sum (map abs (zipWith (-) xs (intersperse 1 (replicate (length xs) 0)))),
           sum( map abs (zipWith (-) xs (intersperse 0 (replicate (length xs) 1))))]

import Data.List (intersperse)

minConmutacionesOndulanteA44 :: [Int] -> Int

minConmutacionesOndulanteA44 xs =

minimum [sum (map abs (zipWith (-) xs (intersperse 1 (replicate (length xs) 0)))),

sum( map abs (zipWith (-) xs (intersperse 0 (replicate (length xs) 1))))]

Responder

import Data.List

minConmutacionesOndulante :: [Int] -> Int
minConmutacionesOndulante xs =
  min (numDiferentes xs (aOndulante1 xs))
      (numDiferentes xs (aOndulante2 xs)) - 1
                                
aOndulante1 :: [Int] -> [Int]
aOndulante1 xs = [snd a | a <- ys]
  where ys = sort ((zip [1,3..length xs] (repeat 0)) ++
                   (zip [0,2..length xs] (repeat 1)))

aOndulante2 :: [Int] -> [Int]
aOndulante2 xs = [snd a | a <- ys]
  where ys = sort ((zip [1,3..length xs] (repeat 1)) ++
                   (zip [0,2..length xs] (repeat 0))) 

numDiferentes :: [Int] -> [Int] -> Int
numDiferentes [] [] = 0
numDiferentes xs [] = length xs
numDiferentes [] xs = length xs
numDiferentes (x:xs) (y:ys) | x == y    = numDiferentes xs ys
                            | otherwise = 1 + numDiferentes xs ys

import Data.List

minConmutacionesOndulante :: [Int] -> Int

minConmutacionesOndulante xs =

min (numDiferentes xs (aOndulante1 xs))

(numDiferentes xs (aOndulante2 xs)) - 1

aOndulante1 :: [Int] -> [Int]

aOndulante1 xs = [snd a | a <- ys]

where ys = sort ((zip [1,3..length xs] (repeat 0)) ++

(zip [0,2..length xs] (repeat 1)))

aOndulante2 :: [Int] -> [Int]

aOndulante2 xs = [snd a | a <- ys]

where ys = sort ((zip [1,3..length xs] (repeat 1)) ++

(zip [0,2..length xs] (repeat 0)))

numDiferentes :: [Int] -> [Int] -> Int

numDiferentes [] [] = 0

numDiferentes xs [] = length xs

numDiferentes [] xs = length xs

numDiferentes (x:xs) (y:ys) | x == y = numDiferentes xs ys

| otherwise = 1 + numDiferentes xs ys

Responder

Conmutaciones ondulantes

Soluciones

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico