Skip to content

Instantly share code, notes, and snippets.

@pjg pjg/exercise.rb
Last active Nov 22, 2018

Embed
What would you like to do?
Array#pairs
require 'rspec'
class Array
def pairs(sum)
end
end
# arr = [1,3,4,5,2,6,-1,0,2]
# p arr.pairs(4) # => [[1,3],[4,0],[5,-1],[2,2]]
# arr = [1,3,1]
# p arr.pairs(4) # => [[1,3]]
# arr = [1,3,3,3,1]
# p arr.pairs(4) # => [[1,3],[3,1]]
RSpec.configure do |config|
config.filter_run_when_matching :focus
end
RSpec.describe 'Array#pairs' do
it 'handles empty array' do
expect([].pairs(4)).to eql []
end
it 'finds pair if there are only 2 matching elements' do
expect([1, 3].pairs(4)).to match_array [a_collection_containing_exactly(1, 3)]
end
it 'handles negative numbers' do
expect([-1, 5].pairs(4)).to match_array [a_collection_containing_exactly(-1, 5)]
end
it 'takes into account each element only once' do
expect([1, 3, 1].pairs(4)).to match_array [a_collection_containing_exactly(1, 3)]
end
it 'handles two pairs' do
expect([2, 1, 3, 2].pairs(4)).to match_array [
a_collection_containing_exactly(2, 2),
a_collection_containing_exactly(1, 3)
]
end
it 'handles two pairs with more elements' do
expect([1, 3, 3, 3, 1].pairs(4)).to match_array [
a_collection_containing_exactly(1, 3),
a_collection_containing_exactly(3, 1)
]
end
it 'handles complex array' do
expect([1, 3, 4, 5, 2, 6, -1, 0, 2].pairs(4)).to match_array [
a_collection_containing_exactly(1, 3),
a_collection_containing_exactly(4, 0),
a_collection_containing_exactly(5, -1),
a_collection_containing_exactly(2, 2)
]
end
end
class Array
# crude solution O(n^3)
def pairs(sum)
result = []
reserved = []
each.with_index do |el, index|
each.with_index do |next_el, next_index|
next if next_index <= index
next if reserved.include? index
next if reserved.include? next_index
if el + next_el == sum
result << [el, next_el]
reserved << index
reserved << next_index
end
end
end
result
end
# solution with index O(n^2)
def pairs(sum)
result = []
reserved = {}
each.with_index do |el, index|
each.with_index do |next_el, next_index|
next if next_index <= index
next if reserved[index]
next if reserved[next_index]
if el + next_el == sum
result << [el, next_el]
reserved[index] = true
reserved[next_index] = true
end
end
end
result
end
# ideal solution O(n)
def pairs(sum)
result = []
elements = Hash.new(0)
each.with_index do |el, index|
desired = sum - el
if elements[desired] > 0
result << [el, desired]
elements[desired] -= 1
else
elements[el] += 1
end
end
result
end
end
@gotar

This comment has been minimized.

Copy link

commented Nov 22, 2018

def pairs(sum)
  return enum_for(:pairs, sum).to_a unless block_given?
  counter = Hash.new(0)
  each do |item|
    if counter[sum - item].zero?
      counter[item] += 1
    else
      counter[sum - item] -= 1
      yield [sum - item, item]
    end
  end
end
@gotar

This comment has been minimized.

Copy link

commented Nov 22, 2018

class Array
  def pairs(sum)
    each.with_object([[], []]) do |e, (singles, pairs)|
      if idx = singles.index { |s| ((s + e) ^ sum).zero? }
        pairs << [e, singles.delete_at(idx)]
      else
        singles << e
      end
    end.last
  end
end
@gotar

This comment has been minimized.

Copy link

commented Nov 22, 2018

^ podrzucone przez Macka Kubiaka

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.