RubyQuiz #60. Numeric Maze

En la época del año en la que estamos lo habitual es que o bien las vacaciones estén cerca o incluso ya estemos disfrutando de ellas. Sin duda es un buen momento para desconectar y hacer cosas que durante el año no podemos hacer.

A los que nos gustan los ordenadores, esto no tiene por que significar que dejemos de usarlos, simplemente podemos usarlos para otras cosas😉

Personalmente me encantan los problemas numéricos y para ello el ordenador es una herramienta perfecta para desarrollar simples algoritmos que los solucionen.

Hace poco descubrí el rubyquiz . En esta web y en la lista de correo se mandan regularmente diversos problemas y se propone el desarrollar un pequeño programa hecho en Ruby que lo solucione.

El primer reto que he escogido es el número 60, llamado Numeric Maze.

El objetivo es hacer un programa que te calcule la ruta desde un número inicial A a un numero final B, con solo 3 operaciones: sumar 2, dividir por 2 y multiplicar por 2.

Así por ejemplo para llegar de 2 a 9, la ruta seguida será. [2, 1, 3, 5, 7, 9]

Como podemos ver, una de las formas de resolver el problema se trata de construir un con las diferentes posibilidades. A priori lo podemos plantear como un caso de backtracking, o de exploración del árbol en profundidad, sin embargo, esta forma de intentar solucionarlo tiene un problema. No sabemos cuando parar descendiendo por el árbol de soluciones.

La alternativa es explorar el árbol de forma horizontal, es decir, para cada paso, sacar las posibles posibilidades y ir generando el árbol paso a paso con todos los casos en cada nivel. De esta manera nos aseguramos que encontraremos la solución tan pronto aparezca. Aunque la desventaja general de este tipo de métodos es que se generan pasos que no van a ser utilizados para nada.

Además, se plantea una interesante posibilidad de “poda” del árbol, pues no es necesario volver a explorar un número que ya se ha explorado.

De esta manera, el árbol ejemplo para el caso de 2 a 9 seria:

[2]
[4 1]
[8 6 3]
[16 10 12 5]
[18 32 20 24 14 7]
[36 9 64 34 22 40 ...]

Para representar este árbol en Ruby, he escogido una lista que esta compuesta por cada numero del nivel determinado. Como tenemos que guardar la ruta de números que nos ha llevado hasta el resultado, acompañando a cada número se guarda dicho histórico.

Así en el ejemplo anterior, la estructura de datos que manejamos es

[2 []]
[ [4, [2]], [1, [2]] ]
[ [8, [4, 2]], [6, [4, 2]], [3, [1,2]] ]
...
[... [9 [2, 4, 8, 16, 18, 9]],...]

De esta manera cuando lleguemos a la solución ya tenemos el conjunto de números por los que hemos ido pasando.

Finalmente el código Ruby que resuelve el problema es el siguiente:

def solve startNumber, endNumber
  current = []
  curStep = 0
  current[curStep] = [ [startNumber, []] ]
  numbers = [startNumber]
	while (numbers.index endNumber) == nil
	  curStep+=1
	  current[curStep] = []
    current[curStep-1].each do |tuple|
	    if (numbers.index tuple[0] << 1) == nil
	      current[curStep] << [(tuple[0] << 1), tuple[1] + [tuple[0]]]
	      numbers << (tuple[0] << 1)
      end

	    if ((tuple[0] % 2) == 0) and ((numbers.index(tuple[0] >> 1) ) == nil)
	      current[curStep] << [(tuple[0] >> 1), tuple[1] + [tuple[0]]]
	      numbers << (tuple[0] << 1)
      end

	    if (numbers.index tuple[0]+2) == nil
	      current[curStep] << [tuple[0]+2, tuple[1] + [tuple[0]]]
	      numbers << tuple[0]+2
      end
    end
  end

  current[curStep].each do |res|
    return res[1] + [endNumber], curStep if res[0] == endNumber
  end

  return nil
end

p solve 2, 9

# [[2, 4, 8, 16, 18, 9], 5]
# Siendo 5 el numero de pasos usados para llegar a la solución

Como veis el código, aunque en esta Ruby, aun le queda para tener ese toque “perl-extraño” que suelen tener los scripts hechos en Ruby. Esto se debe a que aún mi nivel del lenguaje no es muy alto😉

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: