auswertung.rb

# Es gab insgesamt 4 Teilnehmer.
# Insgesamt 5 Lösungen.
# Davon 3 hatten richtige Ergebnisse.

#
# Lösungsansätze.
#
# Es gibt grundsätzlich 3 Lösungsansätze:
# 1. Iteration (Lösung 1, Lösung 2, Lösung 3). Einfach zu verstehen und zu implementieren.
# 2. "Divide and Conquer" mit Rekursion (Lösung 4). 
#    Auf einem Prozessor sehr ineffizient. 
#    Kann aber wegen funktionaler eigenschaften auf einen Cluster ausgelagert werden.
# 3. Formel (Lösung 5 ist "fast" nach der Formel, zumindest das Wort "Permutation" kommt dort vor).
#    Leider ist die Ruby-Permutation super ineffizient (http://rxr.whitequark.org/mri/source/array.c#4573).
#    Die Permutationsformel (m + n)! / (m! * n!) ist sehr einfach, serh effizient.
#    Mit http://www.luschny.de/math/factorial/ kann Fakultätrechnung noch optimiert werden.
#    Darüber hinaus gibt es Hardware, die Fakultätrechnung effizient durchführen kann.

# Es gibt 2 einfache Lösungen (Lösung 6 und 7).
# Die einfachste richtige Lösung ist die Permutationsformel (m + n)! / (m! * n!).

#
# Nun die Lösungen...
#

# Huy
# https://gist.github.com/Skudo/be8dbdd3701560e3859a
# Iteration. Korrekt.
# Laufzeit bei 100 x 100: 0.003007 (Platz 4).

def count_paths1(m, n)
  grid = []
  grid[0] = [1] * n
  (1..m).each { |x| grid[x] = [1] + ([0] * (n - 1)) }

  (1...m).each do |x|
    (1...n).each do |y|
      grid[x][y] = grid[x - 1][y] + grid[x][y - 1]
    end
  end

  grid[m - 1][n - 1]
end

# Kai
# https://gist.github.com/phorsuedzie/5ae6ccb9d07bc9677632
# Iteration. Korrekt.
# Laufzeit bei 100 x 100: 0.002484 (Platz 2)

def count_paths2(m, n)
  current = [0] * n
  current[0] = 1
  m.times {(n-1).times.inject(1) {|memo, i| current[i+1] += memo}}
  current.last
end

# Tomasz
# https://gist.github.com/tomaszp-infopark/dbacef4faa7f30f3f767
# Iteration. Korrekt.
# Laufzeit bei 100 x 100: 0.002511 (Platz 3)

def count_paths3(x, y)
  mem = (x+1).times.map { Array.new(y+1) }
  mem[x][y] = 0

  (x-1).downto(0) {|valid_x| mem[valid_x][y] = 1}
  (y-1).downto(0) {|valid_y| mem[x][valid_y] = 1}

  (x-1).downto(0) do |valid_x|
    (y-1).downto(0) do |valid_y|
      mem[valid_x][valid_y] = mem[valid_x+1][valid_y] + mem[valid_x][valid_y+1]
    end
  end

  #p mem

  return mem[0][0]
end

# Tomasz
# https://gist.github.com/tomaszp-infopark/dbacef4faa7f30f3f767
# "Divide and Conquer".
# Laufzeit bei 10 x 10: 0.098235.
# Bei 100 x 100: Sehr lange...

def count_paths4(x,y)
  if x==0 && y==0
    return 0
  elsif (x==1 && y==0) || (x==0 && y==1)
    return 1
  else
    count = 0
    if x > 0 && y >=0
      count += count_paths4(x-1, y)
    end
    if y > 0 && x >= 0
      count += count_paths4(x, y-1)
    end
    return count
  end
end

# Dave
# https://gist.github.com/dcsaszar/16be15e4394ac2750f53
# Permutation equation. Correct.
# Laufzeit bei 5 x 5 -> 11.163765
# Laufzeit bei 100 x 100: Bis ans Ende der Zeit...
def count_paths5(m, n)
  ([:right] * m + [:down] * n).permutation.to_a.uniq.size
end


# "Richtige" Lösung 1.
# "Divide and Conquer".
# Laufzeit bei 10 x 10: 0.023018.
# Bei 100 x 100: Ewig...
def count_paths6(m, n)
  _count_path6(0, 0, m, n)
end

def _count_path6(x, y, m, n)
  return 1 if x == m || y == n
  _count_path6(x + 1, y, m, n) + _count_path6(x, y + 1, m, n)
end


# "Richtige" Lösung 2.
# Die Permutationsformel.
# Laufzeit bei 100 x 100: 0.000180 (Platz 1)
# Es gibt aber Verfahren, um Fakultät-Rechnung zu optimieren: http://www.luschny.de/math/factorial/.

def count_paths7(m, n)
  fac(m + n) / (fac(m) * fac(n))
end

def fac(n)
  (1..n).reduce(:*)
end

require 'benchmark'

m, n = 5, 5
# m, n = 10, 10
# m, n = 100, 100
puts Benchmark.measure { count_paths1(m, n) }
puts Benchmark.measure { count_paths2(m, n) }
puts Benchmark.measure { count_paths3(m, n) }
puts Benchmark.measure { count_paths4(m, n) }
puts Benchmark.measure { count_paths5(m, n) }
puts Benchmark.measure { count_paths6(m, n) }
puts Benchmark.measure { count_paths7(m, n) }

Ich hatte (nach 10 min, deshalb ausserhalb der Wertung) noch diese Variante:

def count_paths8(m, n)
  Array.new(m + n).combination(n).size
end

p Benchmark.measure {count_paths7(50000, 50000)}.real
p Benchmark.measure {count_paths8(50000, 50000)}.real

7.748422012
2.98542481

1. ruby 1.9 hat noch kein .size direkt auf dem Enumerator. Uh-oh - das ergibt jede Menge Speicherverbrauch :-)

2. Wenn man bei der Berechnung noch einmal durch n! (bzw. m!, bei m > n) kürzt, sind die Berechnungen ungefähr gleich schnell. Interessanterweise wird die Fakultät bei wiederholter Ausführung schneller, die Combination bleibt eher gleich.