CODEWITHSUNDEEP
rubyreduceinject
hellothere1
hellothere1

Reputation: 85

How does using Array#reduce in this way work?

I have been learning ruby for the last few weeks and I came across something like:

array = [10, 20, 20];

array.reduce(:^)

# => 10

which evaluated to 10.

The purpose of the code was to find an element with an odd number of occurrences within a sequence such as [10, 20, 20].

Does anyone have a relatively simple explanation of how this works?

Upvotes: 3

Views: 1013

Answers (3)

Cary Swoveland
Cary Swoveland

Reputation: 110755

array = [10, 20, 20];

array.reduce(:^)
  #=> 10

produces the same result as

array.reduce { |t,n| t^n }
  #=> 10

Let's add a puts statement to see what is happening.

array.reduce do |t,n|
  puts "t = #{t}, n = #{n}, t^n = #{t^n}"
  t^n
end
  # t = 10, n = 20, t^n = 30
  # t = 30, n = 20, t^n = 10
  #=> 10

When Enumerable#reduce is not given an argument the "memo" (the block variablet) is set equal to the first element of the receiver (10) and the first element passed to the block is the second element of the receiver, 20.

Fixnum#^ is the bitwise "exclusive-or" operator (XOR).

When t #=> 10 and (the first) n #=> 20 is passed to the block:

t^n #=> 30

because

10.to_s(2)      #=> "01010" 
20.to_s(2)      #=> "10100"
                     ----- 
(10^20).to_s(2) #=> "11110"
"11110".to_i(2) #=>     30
10^20           #=>     30

When t #=> 30 and (the second) n #=> 20 is passed to the block:

t^n #=> 10

because

30.to_s(2)      #=> "11110" 
20.to_s(2)      #=> "10100" 
                     ----- 
(30^20).to_s(2) #=> "01010" 
"1010".to_i(2)  #=>     10     
(30^20)         #=>     10

Upvotes: 7

Phil Ross
Phil Ross

Reputation: 26120

reduce combines all the elements of an Enumerable by applying a binary operation. ^ is the bitwise exclusive OR (XOR) operator.

array.reduce(:^) performs the bitwise XOR of the elements of array. For array = [10, 20, 20], this performs (10 ^ 20) ^ 20, giving the result 10.

The bitwise XOR of a number and itself is 0 and XOR is associative (the order is not important). Every pair of identical numbers in the array is therefore cancelled out, leaving the XOR of any numbers that occur an odd number of times. If there is a single number in the array that occurs an odd number of times, then this number will be the result.

Upvotes: 2

mgarciaisaia
mgarciaisaia

Reputation: 15630

Fixnum#^ is the bitwise exclusive OR operator (XOR).

(10 ^ 20) ^ 20 #=> 10

I'm not sure how you'd filter the numbers with odd number of occurrences, though.

Upvotes: 0

Related Questions