Home

Archivos

Buscar

Categorías

Feeds:

RSS / Atom

Project Euler 15· 27. February 2008, 22:26

Sigo barriendo los que me salte:

Enunciado

def fac(limite)
  (2..limite).inject(1) { |tot,a| tot*=a}
end
def algoritmo(limite)
  #cada camino tiene un total de limite*2 pasos (ejemplo, para 2x2 forzozo hay 4 pasos)
  #queremos ver como escoger los verticales (y con eso se escogen los horizontales
  #automaticamente) asi que son las combinaciones de 4 pasos en grupos de 2
  # C(n,k)=n!/[(n-k)!k!] <- formula de combinaciones
  #Estamos buscando las combinaciones de n partes de un total de 2n
  # C(2n,n)=(2n)!/[n!n!]
  fac(limite*2)/(fac(limite)**2)
end
puts algoritmo(20)

Realmente solo fue programar el calculo de combinaciones, pero me costo llegar a la formula correcta y de hecho tuve que hacer un poco de trampa y revisar google

Aqui va mi codigo original que tripea cuando subes de 12, esta basado en un programa para resolver laberintos que hice anteriormente

def brute_force(limite) 
  caminos=0
  x,y=0,0
  guardado=Array.new
  #~ Siempre buscamos primero a la derecha y luego hacia abajo
  while true do
    if x<=limite
      #~ puts "pushing #{x} #{y}"
      guardado.push([x,y])
      x+=1
    else #ya llegamos hasta la derecha, no hay mas bifurcaciones
      caminos+=1
      x,y=guardado.pop
      y+=1
      while y == limite do
        caminos+=1
        x,y=guardado.pop
        y+=1
      end
      #~ x+=1
    end
    break if guardado.empty?
  end
  p caminos
end