Equation Greatest Common Divisior for a list of integers

Equation Greatest Common Divisior for a list of integers

#!/usr/bin/env ruby

module Algo
  # Gets the Greatest Common Divisior of integers a and b
  def self.gcd(a, b)
    if b == 0
      a.abs
    else
      gcd(b, a % b)
    end
  end

  # Gets the Greatest Common Divisior Tree of array of integers
  #
  # Parameters:
  # values  : array of integers
  #
  # Returns : array of GCD integers
  #
  def self.gcdn(values)
    value = values.shift
    if values == []
      return [value]
    end
    
    g = gcdn(values)
    [gcd(value, g[0])] + g
  end
  
  # Solves the equation:
  # gcd(a, b, c, ...) = xa + yb + zc + ...
  # where:
  # gcd(a, b) = xa + yb
  # gcd(a, b, c) = gcd(a, gcd(b, c)
  # 
  # Parameters:
  #  
  # values  : array of integers (a, b, c, ...)
  # gcds    : array of GCD integers
  #
  # Returns : array of integer coefficients
  #
  def self.solve(values, gcds, results = [1])
    # Clean value unused in calculations
    values.pop
    
    if values == []
      # We're done, just return the results
      return results
    end
    
    # Picking a, b and gcd required for calculations
    a = values[values.length - 1]
    b = gcds.pop
    gcd = gcds[gcds.length - 1]
    
    # Cycling from -b to +b as we need to find x in:
    # gcd(a, b) = xa + yb, where gcd, a, b are given, thus:
    # y = (gcd - x*a) / b
    # but we only can accept integer y, i.e.
    # (gcd - x*a) % b should be 0
    # Cycling from 0 to calculate the smallest x possible,
    # checking both positive and negative values
    0.upto(b) do |x|
      if (gcd - x*a) % b == 0
        y = (gcd - x*a) / b
        results.map! { |v| v * y}
        return solve(values, gcds, [x] + results)
      end
      if (gcd + x*a) % b == 0
        y = (gcd + x*a) / b
        results.map! { |v| v * y}
        return solve(values, gcds, [-x] + results)
      end
    end
  end
  
  # Returns the string representation of the target equation
  #
  # Parameters:
  # values  : array of integers
  #
  # Returns : string like -8941*26016 + 6061*38378 = 2 
  #
  def self.formula(args)
    
    # At least two integers required
    if args.length < 2
      help
      return
    end
    
    # Only accepting integers
    values = args.map do |s|
      if /[0-9]+/.match(s).nil?
        help
        return
      end
      s.to_i
    end
    
    # Calculating GCDs
    gcds = gcdn(values.clone)

    # GCD for all the values
    gcd = gcds[0]
    
    # Calculating coefficients
    coeffs = solve(values.clone, gcds.clone)
    
    r = ''
    p = ''
    while values != []
      v = values.shift
      c = coeffs.shift
      r = r + "#{p}#{c}*#{v}"
      p = ' + '
    end
    r = r + " = #{gcd}"
    
    puts r
  end
  
  # Prints usage instructions
  def self.help
    puts "Input: space delimited list of integers: a b ..."
    puts "Output: an equation x*a + y*b ... = greatest_common_divider(a, b, ...)"
    puts "Can be run with --test parameter to test itself"
  end
end

module AlgoTest
  def self.suite
    failed = false
    [
      gcd_is(21, 1071, 1029),
      gcd_is(21, 1071, -1029),
      gcd_is(21, -1071, -1029),
      gcd_is(21, 252, 105),
      gcd_is(21, 252, 105, -1071, -1029),
      gcd_is(2, 8672, -640, 26016, 38378),
      coeffs_are([0, 0, -8941, 6061], [8672, -640, 26016, 38378])
    ].each do |t|
      if t
        print '.'
      else
        failed = true
        print 'F'
      end
    end
    puts ''
    puts 'Failed' if failed
    puts 'Passed ok' unless failed
  end

  def self.gcd_is(expected, *a)
    Algo::gcdn(a)[0] == expected
  end
  
  def self.coeffs_are(expected, values)
    gcds = Algo::gcdn(values.clone)
    Algo::solve(values, gcds) == expected
  end
end

if ARGV[0] == '--test'
  AlgoTest::suite
else
  Algo::formula(ARGV)
end