public
Last active

Greatest Common Divisor by Matma.Rex (Bartosz Dziewoński) on ruby-talk http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/405031

  • Download Gist
gcd.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
# original code
gcd=->(_){_.sort_by(&:-@).inject{|p,q|q.nonzero?&&gcd[[q,p-q]]||--p}}
$/=' ';gets;puts gcd[[$_,gets].map &(method :Integer)]
 
 
# original code modified (puts&gets removed, made example explicit, etc.)
# === 1st line ===
gcd=->(_){_.sort_by(&:-@).inject{|p,q|q.nonzero?&&gcd[[q,p-q]]||--p}}
# -@ unary minus—returns the receiver’s value, negated.
# Numeric.instance_methods(false).grep /@/ #=> [:+@, :-@]
 
### I. meaning of ".sort_by(&:-@)"
# for reference: a.sort {|x,y| y <=> x }
a = [6, 8]
a.sort_by(&:-@) #=> [8, 6]
# same as
a.sort_by {|x| -x}
# same as
a.sort_by {|x| x.-@} # :-@ can be turned to block with the & operator
# ( Symbol#to_proc is implicitly called )
### II. "inject"-part
# Breaking it down with [6,8]
gcd[[6,8]] #=> 2
gcd=->(_){_.sort_by(&:-@).inject{|p,q|q.nonzero?&&gcd[[q,p-q]]||--p}}
# ( I am sure that I am missing something here )
### Matma.Rex:
# > #inject on a two-element array is essentially the same as splatting it in
# > two separate variables. The following two snippets do the same thing:
# >
# > result = [1, 2].inject{|a, b| do_stuff_with(a, b) }
# > a, b = *[1, 2]
# > result = do_stuff_with(a, b)
#
# 1st iteration: [8,6] -> 6 && gcd[[6,2]] || --8
# 2nd iteration: [6,2] -> 6 && 2 && gcd[[2,4]] || --6
# 3rd iteration: [4,2] -> 6 && 2 && 2 && gcd[[2,2]] || --4
# 4th iteration: [2,2] -> 6 && 2 && 2 && 2 && gcd[[2,0]] || --2
# 5th iteration: [2,0] -> 6 && 2 && 2 && 2 && nil && gcd[[0,2]] || --2
# On the last iteration everything evaluates to nil before the ||.
# (One remaining question: why --p?)
### Matma.Rex:
# > "--p" is just for laughs. While this looks like decrementation in C / C++,
# > it parses as "-(-p)" as is the same as simply "p".
 
# === 2nd line ===
gcd[%w( 27 108 ).map &(method :Integer)] #=> 27
# same as
gcd[%w( 27 108 ).map {|x| Integer(x)} ] #=> 27
# Kernel#Integer(arg) (private) returns arg to Bignum or Fixnum
# Object#method(sym) Looks up the named method as a receiver in obj,
# returning a Method object
#
# As Kernel#Integer is a private method, it cannot be explicitly invoked on an
# object but Object#method can be used to call it in that object's context.
#
# "method :Integer" returns a Method object in the global scope,
# and the ampersand converts it to a block, that can be fed to map:
a = method :Integer #=> #<Method: Object(Kernel)#Integer>
gcd[%w( 27 108 ).map &a] #=> 27

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.