Array#pairs

exercise.rb

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

solutions.rb

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

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

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

^ podrzucone przez Macka Kubiaka