Lexicographic paths

lexicographic_paths.rb

# Ruby version from https://github.com/derekhh/HackerRank/blob/master/mathematics/combinatorics/lexicographic-steps.cpp
# Build the 'Lower Pascal matrix'
# http://rosettacode.org/wiki/Pascal_matrix_generation#Ruby
ng = (g = 0..20).collect{ [] }
g.each { |i| g.each { |j| ng[i][j] = j == 0 ? 1 : i < j ? 0 : ng[i - 1][j - 1] + ng[i - 1][j] } }

# Uncomment the line bellow to print the matrix
# ng.each { |i| i.each { |j| print "#{j}\t" }; puts }

t = gets.chomp.to_i
while t > 0
  n, m, k = gets.chomp.split(' ').map(&:to_i)
  cx, cy = 0, 0

  while cx != n || cy != m
    nh, nv = n - cx, m - cy

    if nh == 0
      print 'V'
      cy += 1

    elsif nv == 0
      print 'H'
      cx += 1

    else
      temp = ng[nh + nv - 1][nh -1]
      if k >= temp && temp > 0
        print 'V'
        k -= temp
        cy += 1

      else
        print 'H'
        cx += 1
      end
    end
  end

  puts

  t -= 1
end