Problema de la bicicleta de Turing

En ciencias de la computación, la bicicleta de Turing es un problema muy utilizado.

Cuentan que Alan Turing tenía una bicicleta vieja, que tenía una cadena con un eslabón débil y además uno de los radios de la rueda estaba doblado. Cuando el radio doblado coincidía con el eslabón débil, entonces la cadena se rompía.

La bicicleta se identifica por los parámetros (i,d,n) donde:

  • i es el número del eslabón que coincide con el radio doblado al empezar a andar,
  • d es el número de eslabones que se desplaza la cadena en cada vuelta de la rueda y
  • n es el número de eslabones de la cadena (el número n es el débil).

Si i = 2, d = 7 y n = 25, entonces la lista con el número de eslabón que toca el radio doblado en cada vuelta es

[2,9,16,23,5,12,19,1,8,15,22,4,11,18,0,7,14,21,3,10,17,24,6,...

Con lo que la cadena se rompe en la vuelta número 14.

Implementación en Haskell

Definir la función:

eslabones :: Int -> Int -> Int -> [Int]

tal que (eslabones i d n) es la lista con los números de eslabones que tocan el radio doblado en cada vuelta en una bicicleta de tipo (i,d,n).

Por ejemplo, take 10 (eslabones 2 7 25) == [2,9,16,23,5,12,19,1,8,15]

Solución

eslabones :: Int -> Int -> Int -> [Int] eslabones i d n = [(i+d*j) `mod` n | j <- [0..]]

Se puede definir usando iterate:

eslabones2 :: Int -> Int -> Int -> [Int] eslabones2 i d n = map (\x-> mod x n) (iterate (+d) i)

Definir la función

numeroVueltas :: Int -> Int -> Int -> Int tal que (numeroVueltas i d n) es el número de vueltas que pasarán hasta que la cadena se rompa en una bicicleta de tipo (i,d,n).

Por ejemplo,

numeroVueltas 2 7 25 == 14

Solución

numeroVueltas :: Int -> Int -> Int -> Int numeroVueltas i d n = length (takeWhile (/=0) (eslabones i d n))

Bibliografía

  • A. Alonso Jiménes, José,Piensa en Haskell (2012)Sevilla
  • Lenar Michel TR, (2018) Universidad de Las Tunas, Cuba