Last active
December 15, 2015 22:32
-
-
Save davingee/8278b9f6c66f0c53f5e9 to your computer and use it in GitHub Desktop.
Given an array of -2000 to 2000, find all the combinations of numbers that equal 10
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# gem install awesome_print | |
# gem install benchmark | |
# gem install pry | |
require 'awesome_print' | |
require 'pry' | |
require 'benchmark' | |
# Given an array of -2000 to 2000, find all the combinations of numbers that equal 10 | |
class SumOfEach | |
attr_accessor :numbers, :numbers_count, :target, :matches, :searched, :to_remove | |
def initialize( args = { } ) | |
self.target = args.fetch( :target, 30 ) | |
self.numbers = ( args.fetch( :from, -50 )..args.fetch( :to, 50 ) ).to_a | |
self.numbers_count = numbers.count | |
self.matches = { } | |
self.to_remove = [ ] | |
self.searched = { } | |
end | |
def self.find( args = { } ) | |
target = args.fetch(:target, -10) | |
from = args.fetch(:from, -2000) | |
to = args.fetch(:to, 2000) | |
sum_of_each = SumOfEach.new( target: target, from: from, to: to ) | |
Benchmark.bm do |x| | |
x.report('equals1') { | |
sum_of_each.equals1 | |
sum_of_each.matches[ :count ] = sum_of_each.matches.count | |
} | |
end | |
ap sum_of_each.matches[ :count ] | |
sum_of_each = SumOfEach.new( target: target, from: from, to: to ) | |
Benchmark.bm do |x| | |
x.report('equals2') { | |
sum_of_each.equals2 | |
sum_of_each.matches[ :count ] = sum_of_each.matches.count | |
} | |
end | |
ap sum_of_each.matches[ :count ] | |
sum_of_each = SumOfEach.new( target: target, from: from, to: to ) | |
Benchmark.bm do |x| | |
x.report('equals3') { | |
sum_of_each.equals3 | |
sum_of_each.matches[ :count ] = sum_of_each.matches.count | |
} | |
end | |
ap sum_of_each.matches[ :count ] | |
sum_of_each = SumOfEach.new( target: target, from: from, to: to ) | |
Benchmark.bm do |x| | |
x.report('equals4') { | |
sum_of_each.equals4 | |
sum_of_each.matches[ :count ] = sum_of_each.matches.count | |
} | |
end | |
ap sum_of_each.matches[ :count ] | |
sum_of_each = SumOfEach.new( target: target, from: from, to: to ) | |
Benchmark.bm do |x| | |
x.report('equals5') { | |
sum_of_each.equals5 | |
sum_of_each.matches[ :count ] = sum_of_each.matches.count | |
} | |
end | |
ap sum_of_each.matches[ :count ] | |
# ap sum_of_each.matches | |
end | |
def equals1 | |
remove_numbers_from_array_logic | |
( numbers - to_remove ).map.with_index do | n, i | | |
matches[ "#{ n }_plus_#{ target - n }" ] = target if numbers[ i, numbers_count].include?( target - n ) | |
end | |
end | |
def equals2 | |
remove_numbers_from_array_logic | |
( numbers - to_remove ).map.with_index{ | n, i | numbers[ i, numbers_count ].each{ | n2 | matches[ "#{ n }_plus_#{ n2 }" ] = target if n + n2 == target } } | |
end | |
def equals3 | |
numbers.each_with_index do | number, index | | |
numbers.each do |number_two| | |
matches[ "#{ number }_plus_#{ number_two }" ] = target if sum_equals_number_to_check?( number_two, number ) && not_already_awnsered?( number, number_two ) | |
end | |
end | |
end | |
def equals4 # 50000 | |
remove_numbers_from_array_logic | |
( numbers - to_remove ).map.with_index{ | n, i | | |
numbers[ i, numbers_count ].map{ | n2 | | |
matches[ "#{ n }_plus_#{ n2 }" ] = target if n + n2 == target | |
} | |
} | |
end | |
def equals5 | |
numbers.unshift( numbers.first + -1 ) | |
numbers.push( numbers.last + 1 ) | |
numbers.each do |number| | |
if searched[ target - number ] == true | |
matches[ "#{ number }_plus_#{ target - number }" ] = target | |
end | |
searched[ number ] = true | |
end | |
end | |
def equals5_solo | |
numbers = ( -10..10 ).to_a | |
numbers.unshift( numbers.first + -1 ) | |
numbers.push( numbers.last + 1 ) | |
target = 10 | |
searched = { } | |
matches = { } | |
numbers.each do |number| | |
if searched[ target - number + 1 ] == true | |
matches[ "#{ number }_plus_#{ target - number }" ] = target | |
end | |
searched[ number + 1 ] = true | |
end | |
ap matches | |
end | |
def equals7 | |
first = numbers.first | |
last = numbers.last | |
numbers.each do |n| | |
val = target - n | |
if searched[val].nil? | |
matches[ "#{n}_plus_#{val}" ] = target unless( val < first || val > last ) | |
searched[n] = true | |
end | |
end | |
end | |
private | |
def not_already_awnsered?( number, number_two ) | |
true if matches[ "#{ number }_plus_#{ number_two }" ].nil? && matches[ "#{ number_two }_plus_#{ number }" ].nil? | |
end | |
def sum_equals_number_to_check?( number_two, number ) | |
number + number_two == target | |
end | |
def remove_numbers_from_array_logic | |
numbers.reverse.each do |n| | |
if n + n > target | |
self.to_remove << n | |
else | |
break | |
end | |
end | |
numbers.each do |n| | |
if n + n > target | |
self.to_remove << n | |
else | |
break | |
end | |
end | |
end | |
end | |
SumOfEach.find |
find pair and increment by 1 for even and skip if odd
require 'pry'
require "awesome_print"
class AddUp
attr_accessor :lower_bound, :upper_bound, :target, :pairs
def initialize(info = {})
@lower_bound = info.fetch(:lower_bound, -100000)
@upper_bound = info.fetch(:upper_bound, 100000)
@target = info.fetch(:target, 11)
@pairs = []
end
def find_mid_pair
target % 2 == 0 ? [ target / 2, target / 2 ] : [ ( target - 1 ) / 2 , ( target - 1 ) / 2 + 1 ]
end
def founded_end?( pair )
pair[ 0 ] == lower_bound || pair[ 1 ] == upper_bound
end
def get_next_pair( pair )
[ pair[ 0 ] - 1, pair[ 1 ] + 1 ]
end
def find_pairs
start_pair = find_mid_pair
# not sure what this is
# return unless start_pair
self.pairs.push( start_pair )
while !founded_end?( pairs.last )
next_pair = get_next_pair( pairs.last )
pairs.push( next_pair )
end
end
end
add_up = AddUp.new
add_up.find_pairs
ap add_up.pairs
array = (-50..50).to_a.product (-50..50).to_a
p array
array1 = array.select do |e|
e.first + e.last == 10
end
p array1
array2 = array1.map do |e|
e.sort
end
p array2
array3 = array2.uniq
p array3
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
equals7
looks like it has about .0025s onequals5
, though at such small time scales it might not be relevant.