Skip to content

Instantly share code, notes, and snippets.

@ksykulev
Created March 17, 2014 14:39
Show Gist options
  • Save ksykulev/9600461 to your computer and use it in GitHub Desktop.
Save ksykulev/9600461 to your computer and use it in GitHub Desktop.
wildcard problem2
#http://www.trywildcard.com/challenge/problem2
GENERATION = [9 , 10, 21, 20, 7, 11, 4, 15, 7, 7, 14, 5, 20, 6, 29, 8, 11, 19, 18, 22, 29, 14, 27, 17, 6, 22, 12, 18, 18, 30]
OVERHEAD = [21, 16, 19, 26, 26, 7, 1, 8, 17, 14, 15, 25, 20, 3, 24, 5, 28, 9, 2, 14, 9, 25, 15, 13, 15, 9, 6, 20, 27, 22]
BUDGET = ARGV[0].to_i #2912
def binary_search_insert(list, obj)
high = list.length
low = 0
mid = 0
direction = -1
while low < high
mid = (high + low) >> 1
direction = obj <=> list[mid][0]
return mid if direction == 0
high = mid if direction < 0
low = mid + 1 if direction > 0
end
return direction < 0 ? -mid : -mid-1
end
time_spent = 0
final_set = 0
total_cards = GENERATION.length
sorted = []
OVERHEAD.each_with_index do |number, index|
bindex = binary_search_insert(sorted, number)
sorted[-bindex, 0] = [ [number, GENERATION[index]] ] if bindex < 0
sorted[bindex, 0] = [ [number, GENERATION[index]] ] if bindex >= 0
end
puts sorted.inspect
while final_set < total_cards
sorted.take(final_set).each do |card|
overhead = card[0]
generation = card[1]
time_spent += generation + overhead * (final_set-1)
end
break if time_spent >= BUDGET
final_set += 1
time_spent = 0
end
puts "result: #{time_spent > BUDGET ? final_set - 1 : final_set}" #17
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment