Menu Close

Puntos visibles en la cuadrícula de un plano

José A. Alonso,

La cuadrícula entera de lado n, Cₙ, es el conjunto de los puntos (x,y) donde x e y son números enteros tales que 1 ≤ x, y ≤ n.

Un punto (x,y) de Cₙ es visible desde el origen si el máximo común divisor de x e y es 1. Por ejemplo, el punto (4,6) no es visible porque está ocultado por el (2,3); en cambio, el (2,3) sí es visible.

El conjunto de los puntos visibles en la cuadrícula entera de lado 6 son (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,1), (2,3), (2,5), (3,1), (3,2), (3,4), (3,5), (4,1), (4,3), (4,5), (5,1), (5,2), (5,3), (5,4), (5,6), (6,1) y (6,5).

Definir la función

   nVisibles :: Integer -> Integer

tal que (nVisibles n) es el número de los puntos visibles en la cuadrícula de lado n.Por ejemplo,

   nVisibles 6       ==  23
   nVisibles 10      ==  63
   nVisibles 100     ==  6087
   nVisibles 1000    ==  608383
   nVisibles 10000   ==  60794971
   nVisibles 100000  ==  6079301507

Soluciones

import Data.List (genericLength, group, sort)
import Data.Numbers.Primes (primeFactors)
 
type Punto = (Integer,Integer)
 
-- (visible p) se verifica si el punto p es visible. Por ejemplo,
--    visible (4,5)  ==  True
--    visible (4,6)  ==  False
visible :: Punto -> Bool
visible (x,y) = gcd x y == 1
 
-- (visibles n) es el conjunto de los puntos visibles en la cuadrícula
-- de lado 1. Por ejemplo,
-- cuadrado 1 <= x, y <= n. Por ejemplo,
--    λ> sort (visibles 6)
--    [(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,1),(2,3),(2,5),(3,1),(3,2),(3,4),
--     (3,5),(4,1),(4,3),(4,5),(5,1),(5,2),(5,3),(5,4),(5,6),(6,1),(6,5)]
 
-- 1ª definición de visibles
visibles1 :: Integer -> [Punto]
visibles1 n = [(x,y) | x <- [1..n], y <- [1..n], visible (x,y)]
 
-- 2ª definición de visibles
visibles2 :: Integer -> [Punto]
visibles2 n = (1,1) : ps ++ [(y,x) | (x,y) <- ps] 
    where ps = [(x,y) | x <- [1..n], y <- [x+1..n], visible (x,y)]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> length (visibles1 1000)
--    608383
--    (3.40 secs, 758,346,208 bytes)
--    λ> length (visibles2 1000)
--    608383
--    (2.22 secs, 464,276,856 bytes)
 
-- Usaremos la 2ª definición de visibles
visibles :: Integer -> [Punto]
visibles = visibles2
 
-- 1ª definición de nVisibles
nVisibles1 :: Integer -> Integer
nVisibles1 = genericLength . visibles
 
 
-- 2ª definición de nVisibles
nVisibles2 :: Integer -> Integer
nVisibles2 n = 
    1 + 2 * genericLength [(x,y) | x <- [1..n], 
                                   y <- [x+1..n], 
                                   visible (x,y)]
 
-- 3ª definición de nVisibles
nVisibles3 :: Integer -> Integer
nVisibles3 1 = 1
nVisibles3 n = nVisibles3 (n-1) + (2 * phi n)
 
-- La función φ de Euler (del ejercicio anterior).
phi :: Integer -> Integer
phi n = product [(p-1)*p^(e-1) | (p,e) <- factorizacion n] 
 
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
    [(head xs,genericLength xs) | xs <- group (primeFactors n)]
 
-- 4ª definición de nVisibles
nVisibles4 :: Integer -> Integer
nVisibles4 n = 2 * sum [phi x | x <- [1..n]] - 1
 
-- Comparación de eficiencia
-- =========================
 
--    λ> nVisibles1 1000
--    608383
--    (2.69 secs, 521,599,512 bytes)
--    λ> nVisibles2 1000
--    608383
--    λ> nVisibles3 1000
--    608383
--    (0.05 secs, 0 bytes)
--    λ> nVisibles4 1000
--    608383
--    (0.04 secs, 0 bytes)

Referencias

Medio
, , , , , , , ,

2 soluciones de “Puntos visibles en la cuadrícula de un plano”

  1. Responder
    josejuan

    No se me ocurre nada más “rápido” (para n=100.000 toma casi 10 minutos!) que restar los puntos internos de todas las diagonales, por lo que el algoritmo es O(n^2) pues el nº de diagonales se aproxima a 3n^2/Pi (https://en.wikipedia.org/wiki/Farey_sequence#Next_term).

    nVisibles :: ℤ → ℤ
nVisibles n = 1 + n × (n - 1) - 2 × ∑(farey (0, 1) (1, n))
  where farey (a, b) (c, d) | c ≥ d     = []
                            | otherwise = (n ÷ d - 1): farey (c, d) (k × c - a, k × d - b)
                              where k = (b + n) ÷ d
  2. Responder
    abrdelrod 
    import Data.List
import Data.Numbers.Primes
 
nVisibles :: Integer -> Integer
nVisibles n = sum [2*phi x | x <- [1..n]] - 1
 
-- Donde la función phi de Euler ya la definimos como:
phi :: Integer -> Integer
phi n = product [p^r-p^(r-1) | (p,r) <- factorizacion n]
    where factorizacion n = zip (nub ys) [genericLength xs | xs <- group ys]
          ys              = primeFactors n
 
-- *Main> nVisibles 100000
-- 6079301507
-- (4.61 secs, 2,302,685,940 bytes)

Escribe tu solución

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