0votos

Obtener el mayor número menor a X que no contenga el dígito Y en Haskell

por josejuan hace 4 años

El algoritmo trivial de decrementar hasta encontrar no sirve para números de unos pocos dígitos (ej. 20 dígitos). Puede obtenerse el número casi directamente para los dígitos 1 a 9, el dígito 0 exige volver atrás en la cabecera, pero la solución tiene coste O(log n).

Se tiene un número X y se indica un dígito Y. Devolver un número Z que sea menor a X y que no posea el dígito Y.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
nodigit :: (Integral a, Show a, Read a) => a -> Char -> a 
nodigit n d | n <= 0     = error "Sólo se consideran números naturales mayores que cero" 
            | d `elem` s = read $ pfx ++ map (const g) (tail $ dropWhile (/=d) s) 
            | otherwise  = n 
            where g = if d == '9' then '8' else '9' 
                  s = show n 
                  hs = takeWhile (/=d) s 
                  pfx = case d of 
                        '0' -> reverse (zero (reverse hs)) ++ "9" 
                        _   -> hs ++ [pred d] 
                  zero "1" = "" 
                  zero [x] = [pred x] 
                  zero ('1':xs) = '9': zero xs 
                  zero (x:xs) = pred x: xs 
 
{- 
 
  Con el algoritmo trivial (de ir decrementando N) el coste es proporcional 
  al tamaño de N (en el peor caso de que el dígito a eliminar esté a la izquierda 
  del todo). 
   
  Con números de tan sólo 20 dígitos, a un procesador a 3Ghz le tomaría 1000 años 
  obtener el resultado con ese algoritmo. 
 
  Por ejemplo, con el algoritmo trivial, obtener el resultado para 
 
    N = 102233445566778899 (dígito 0) 
 
  tomaría 
 
    102233445566778899 - 99999999999999999 = 2233445566778900 
 
  operaciones de decremento, suponiendo que éstas toman un único ciclo de 
  reloj y que tenemos un procesador con 16 núcleos a 3 Ghz cada uno (y paralelizáramos 
  el proceso), serían 
 
    46530 segundos = 13 horas 
 
  Revisando los dígitos (la solución aquí posteada) el coste es proporcional al 
  logaritmo decimal de N (con 20 dígitos, el coste es proporcional a tan sólo 20 operaciones). 
   
  Por ejemplo, obtener el resultado para el primer número sin 1 del número 
   
    190876234908769876198051856185108751807418651239876140962345092435235 
   
  le toma 0.00 segundos para obtener 
   
    99999999999999999999999999999999999999999999999999999999999999999999 
 
  o del mismo número sin 0, los mismos 0.00 segundos en obtener 
   
    189999999999999999999999999999999999999999999999999999999999999999999 
     
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.