Menu Close

Mayor número borrando k dígitos

Definir la función

   mayorBorrando :: Int -> Integer -> Integer

tal que (mayorBorrando k n) es el mayor número obtenido borrando k dígitos de n (se supone que n tiene más de k dígitos). Por ejemplo,

   mayorBorrando 1 6782334  ==  782334
   mayorBorrando 3 6782334  ==  8334
   mayorBorrando 3 10020    ==  20
   mayorBorrando 1000000 (4256 + 10^1000004) == 14256

Soluciones

import Data.List (subsequences)
 
-- 1ª definición
-- =============
 
mayorBorrando :: Int -> Integer -> Integer
mayorBorrando k n = read (mayorBorrandoLista1 k (show n))
 
-- (mayorBorrandoLista1 k xs) es la mayor lista obtenida borrando k elementos de
-- xs (se supone que xs tiene más de k elementos). Por ejemplo,
--    mayorBorrandoLista1 1 "6782334"  ==  "782334"
--    mayorBorrandoLista1 3 "6782334"  ==  "8334"
mayorBorrandoLista1 :: Ord a => Int -> [a] -> [a]
mayorBorrandoLista1 k xs = maximum (borra1 k xs)
 
-- (borra1 k xs) es la lista de las listas obtenidas borrando k elementos
-- de xs. Por ejemplo,
--    borra1 1 "abcd"  ==  ["abc","abd","acd","bcd"]
--    borra1 2 "abcd"  ==  ["ab","ac","bc","ad","bd","cd"]
--    borra1 3 "abcd"  ==  ["a","b","c","d"]
borra1 n xs = [ys | ys <- subsequences xs, length ys == k]
  where k = length xs - n
 
-- 2ª definición
-- =============
 
mayorBorrando2 :: Int -> Integer -> Integer
mayorBorrando2 k n = read (mayorBorrandoLista2 k (show n))
 
-- (mayorBorrandoLista2 k xs) es la mayor lista obtenida borrando k elementos de
-- xs (se supone que xs tiene más de k elementos). Por ejemplo,
--    mayorBorrandoLista2 1 "6782334"  ==  "782334"
--    mayorBorrandoLista2 3 "6782334"  ==  "8334"
mayorBorrandoLista2 :: Ord a => Int -> [a] -> [a]
mayorBorrandoLista2 k xs = maximum (borra2 k xs)
 
-- (borra2 k xs) es la lista de las listas obtenidas borrando k elementos
-- de xs. Por ejemplo,
--    borra2 1 "abcd"  ==  ["abc","abd","acd","bcd"]
--    borra2 2 "abcd"  ==  ["ab","ac","ad","bc","bd","cd"]
--    borra2 3 "abcd"  ==  ["a","b","c","d"]
borra2 :: Eq a => Int -> [a] -> [[a]]
borra2 0 xs     = [xs]
borra2 n []     = []
borra2 n (x:xs) = [x:ys | ys <- borra2 n xs] ++ borra2 (n-1) xs
 
-- 3ª definición
-- =============
 
mayorBorrando3 :: Int -> Integer -> Integer
mayorBorrando3 k n = read (mayorBorrandoLista3 k (show n))
 
-- (mayorBorrandoLista3 k xs) es la mayor lista obtenida borrando k elementos de
-- xs (se supone que xs tiene más de k elementos). Por ejemplo,
--    mayorBorrandoLista3 1 "6782334"  ==  "782334"
--    mayorBorrandoLista3 3 "6782334"  ==  "8334"
mayorBorrandoLista3 :: Ord a => Int -> [a] -> [a]
mayorBorrandoLista3 k xs = maximum (itera k borraUnoListas [xs])
 
-- (borraUnoListas xss) es la lista obtenida borrando un elemento (de
-- todas las formas posibles de la lista de listas no vacías xss. Por
-- ejemplo,
--    borraUnoListas ["abc","def"]  ==  ["bc","ac","ab","ef","df","de"]
borraUnoListas :: [[a]] -> [[a]]
borraUnoListas = concatMap borraUno
 
-- (borraUno xs) es la lista de listas obtenidas borrando un elemento de la
-- lista no vacía xs de todas las formas posibles. Por ejemplo,
--    borraUno "abcde"  ==  ["bcde","acde","abde","abce","abcd"]
borraUno :: [a] -> [[a]]
borraUno [x] = [[]]
borraUno (x:xs) = xs : map (x:) (borraUno xs)
 
-- (itera k f x) es el resultado de aplicar k veces la función f al
-- elemento x. Por ejmplo,
--    itera 3 (*2) 1   ==  8
--    itera 4 (+2) 10  ==  18
itera :: Eq a => Int -> (a -> a) -> a -> a
itera 0 _ x = x
itera n f x = itera (n-1) f (f x)
 
-- 4ª definición
-- =============
 
mayorBorrando4 :: Int -> Integer -> Integer
mayorBorrando4 k n = read (mayorBorrandoLista4 k (show n))
 
-- (mayorBorrandoLista4 k xs) es la mayor lista obtenida borrando k elementos de
-- xs (se supone que xs tiene más de k elementos). Por ejemplo,
--    mayorBorrandoLista4 1 "6782334"  ==  "782334"
--    mayorBorrandoLista4 3 "6782334"  ==  "8334"
mayorBorrandoLista4 :: Ord a => Int -> [a] -> [a]
mayorBorrandoLista4 k = itera k mayorBorraUno
 
-- (mayorBorraUno xs) es la mayor lista obtenida eliminando un elemento de
-- xs. Por ejemplo,
--    mayorBorraUno "6782334"  ==  "782334"
--    mayorBorraUno "782334"   ==  "82334"
--    mayorBorraUno "82334"    ==  "8334"
mayorBorraUno :: Ord a => [a] -> [a]
mayorBorraUno = maximum . borraUno
 
-- 5ª definición
-- =============
 
mayorBorrando5 :: Int -> Integer -> Integer
mayorBorrando5 k n = read (mayorBorrandoLista5 k (show n))
 
-- (mayorBorrandoLista5 k xs) es la mayor lista obtenida borrando k elementos de
-- xs (se supone que xs tiene más de k elementos). Por ejemplo,
--    mayorBorrandoLista5 1 "6782334"  ==  "782334"
--    mayorBorrandoLista5 3 "6782334"  ==  "8334"
mayorBorrandoLista5 :: Ord a => Int -> [a] -> [a]
mayorBorrandoLista5 k = itera k mayorBorraUno2
 
-- (mayorBorraUno2 xs) es la mayor lista obtenida eliminando un elemento de
-- xs. Por ejemplo,
--    mayorBorraUno2 "6782334"  ==  "782334"
--    mayorBorraUno2 "782334"   ==  "82334"
--    mayorBorraUno2 "82334"    ==  "8334"
mayorBorraUno2 :: Ord a => [a] -> [a]
mayorBorraUno2 [x]      = []
mayorBorraUno2 (x:y:xs) | x < y     = y:xs
                        | otherwise = x : mayorBorraUno2 (y:xs)
 
-- 6ª definición
-- =============
 
mayorBorrando6 :: Int -> Integer -> Integer
mayorBorrando6 k n = read (mayorBorrandoLista6 k (show n))
 
-- (mayorBorrandoLista6 k xs) es la mayor lista obtenida borrando k elementos de
-- xs (se supone que xs tiene más de k elementos). Por ejemplo,
--    mayorBorrandoLista6 1 "6782334"  ==  "782334"
--    mayorBorrandoLista6 3 "6782334"  ==  "8334"
mayorBorrandoLista6 :: Ord a => Int -> [a] -> [a]
mayorBorrandoLista6 k xs = aux k [] xs
 
aux 0 ys     xs     = reverse ys ++ xs
aux k ys     []     = reverse (drop k ys)
aux k []     (x:xs) = aux k [x] xs
aux k (y:ys) (x:xs) | y >= x    = aux k     (x:y:ys) xs
                    | otherwise = aux (k-1) ys       (x:xs)
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> mayorBorrando 6 (product [1..18])
--    7705728000
--    (0.06 secs, 15,165,496 bytes)
--    λ> mayorBorrando2 6 (product [1..18])
--    7705728000
--    (0.04 secs, 19,662,816 bytes)
--    λ> mayorBorrando3 6 (product [1..18])
--    7705728000
--    (6.93 secs, 5,143,807,064 bytes)
--    λ> mayorBorrando4 6 (product [1..18])
--    7705728000
--    (0.01 secs, 183,728 bytes)
--    λ> mayorBorrando5 6 (product [1..18])
--    7705728000
--    (0.01 secs, 118,984 bytes)
--    λ> mayorBorrando6 6 (product [1..18])
--    7705728000
--
--    λ> mayorBorrando 17 (product [1..25])
--    998400000
--    (19.09 secs, 14,516,359,464 bytes)
--    λ> mayorBorrando2 17 (product [1..25])
--    998400000
--    (47.39 secs, 30,066,413,608 bytes)
--    λ> mayorBorrando4 17 (product [1..25])
--    998400000
--    (0.01 secs, 458,320 bytes)
--    λ> mayorBorrando5 17 (product [1..25])
--    998400000
--    (0.01 secs, 134,424 bytes)
--    λ> mayorBorrando6 17 (product [1..25])
--    984000000
--    (0.01 secs, 124,600 bytes)
--
--    λ> mayorBorrando4 600 (product [1..300])
--    999999999999999
--    (3.29 secs, 4,421,841,944 bytes)
--    λ> mayorBorrando5 600 (product [1..300])
--    999999999999999
--    (0.03 secs, 6,690,440 bytes)
--    λ> mayorBorrando6 600 (product [1..300])
--    960000000000000
--    (0.01 secs, 593,864 bytes)
--
--    λ> mayorBorrando5 10000 (4256 + 10^10004)
--    14256
--    (16.04 secs, 18,221,784,872 bytes)
--    λ> mayorBorrando6 10000 (4256 + 10^10004)
--    14256
--    (0.02 secs, 6,669,592 bytes)
--
--    λ> mayorBorrando6 1000000 (4256 + 10^1000004)
--    14256
--    (1.04 secs, 655,561,656 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

7 soluciones de “Mayor número borrando k dígitos

  1. María Ruiz
    mayorBorrando :: Int -> Integer -> Integer
    mayorBorrando k n = read $ aux 0 (show n)
      where aux i (x:y:xs) | i >= k    = x:y:xs
                           | x <= y    = aux (i+1) (y:xs)
                           | otherwise = x: aux i (y:xs)
            aux i xs       | i < k     = []
                           | otherwise = xs
    • Ana Blanco

      La solución de María da respuestas erróneas, Por ejemplo,

      λ> mayorBorrando 3 10020
      12

      pero debería de dar 20.

  2. Rubén Muñoz Mkrtchian
    import Data.List (\)
     
    -- Si bien con esta solución no se puede calcular el último ejemplo, parece que
    -- funciona con números no demasiado grandes.
     
    mayorBorrando :: Int -> Integer -> Integer
    mayorBorrando k n = read (mayorBorrandoLista k (show n))
     
    -- mayorBorrandoLista k xs, al igual que mayorBorrando k n, devuelve como valor
    -- el máximo número obtenido en forma de lista eliminando k elementos de xs.
     
    mayorBorrandoLista :: Ord a => Int -> [a] -> [a]
    mayorBorrandoLista _ [] = []
    mayorBorrandoLista k xs
      | k <= 0    = xs
      | k >= p-1  = m : borraMinimos (k - length ts + 1) ds
      | otherwise = drop k xs
          where (m,p) = head [(x,i) | (x,i) <- zip xs [1..], x == maximum xs]
                ds = drop p xs
                ts = take p xs
     
    -- borraMinimos k xs elimina los k elementos más pequeños de la lista xs.
     
    borraMinimos :: Ord a => Int -> [a] -> [a]
    borraMinimos _ [] = []
    borraMinimos k xs
      | k <= 0    = xs
      | otherwise = borraMinimos (k-1) (xs \ [minimum xs])
    • j0sejuan

      En el siguiente ejemplo, hay al menos dos nueves entre el primer grupo que puede quitarse o mantenerse, es decir, mejor empezar con 99 que con 97, por lo que la solución no parece correcta:

      *Main> let n = product [123..213]
      *Main> take (length (show n) - 127) (show n)
      "1021037014573779474549665338169634021181778108614148952783959963172960535276"
      *Main> mayorBorrando 127 n
      9796686968778868978999679676978877985678689696569558889966766678657765569968
  3. j0sejuan

    Diría que puede implementarse con coste en media algo como O(log n) (sí, no hace falta mirar todos los dígitos de entrada) y seguro con coste lineal en el número de dígitos. La siguiente implementación no es eficiente para que sea más legible (ej. está partiendo en los dígitos máximos del rango pero eso puede predecirse). En todo caso, pueden “optimizarse” números con centenas de miles de dígitos:

    -- heurística
    -- "dejamos el dígito más grande que podamos alcanzar...
    --    siempre que dejemos suficientes dígitos"
    borra :: Int -> String -> String
    borra 0  xs = xs
    borra n  xs = let g = maximum $ take (n + 1) xs
                      (ps, ss)  = splitFirst (g ==) xs
                  in  if n >= length xs
                        then []
                        else g: borra (n - length ps) ss
     
    {-
    *Main> let n = product [1234..80000]
    (0.00 secs, 134,080 bytes)
    *Main> let ds = show n
    (0.00 secs, 134,088 bytes)
    *Main> length ds
    354229
    (7.65 secs, 6,931,160,144 bytes)
    *Main> borra 354000 ds
    "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999"
    (16.01 secs, 10,444,752,584 bytes)
    -}
     
     
    splitFirst :: (a -> Bool) -> [a] -> ([a], [a])
    splitFirst f = r []
      where r hs [] = (reverse hs, [])
            r hs (x:xs) = if f x then (reverse hs, xs) else r (x:hs) xs
    • j0sejuan

      Perdiendo legibilidad pero en tiempo (casi) lineal (para serlo del todo hay que guardar los máximos para cada paso):

      borra :: Int -> String -> String
      borra n' xs' = r n' (length xs') xs'
        where r 0 _ xs = xs
              r !n !s xs = let (z, g, ss) = maxsplit n xs
                           in  if n >= s
                                then []
                                else g: r (n - z) (s - z - 1) ss
       
      maxsplit n = m 0 '/' 0 undefined
        where m !i !g !z rs qs = if i > n then (z, g, rs) else w i g z rs qs
              w !i !g !z  _ ('9':ys) = (i, '9', ys)
              w !i !g !z rs (  y:ys) = if y > g
                                         then m (i + 1) y i ys ys
                                         else m (i + 1) g z rs ys
       
      {- Ahora:
       
      *Main> let n = product [1234..80000]
      *Main> let ds = show n
      *Main> length ds
      354229
      *Main> :set +s
      *Main> borra 354000 ds
      "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999"
      (0.01 secs, 2,024,080 bytes)
       
      == 1 millón de dígitos
      *Main> xs <- mapM (const $ randomRIO ('0', '9')) [1..1000000]
      *Main> length $ borra 500000 xs
      500000
      (1.01 secs, 425,993,688 bytes)
       
      -}
  4. Juan María Jiménez Jiménez
     
    import Data.Numbers.Primes
    import Data.List
     
    mayorBorrando :: Int -> Integer -> Integer
    mayorBorrando k n = maximum(map(read)(filter (aux)(subsequences (dig n))))
      where dig n = show n
            l = length (dig n)
            aux xs = length xs == l-k

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.