hackerrank ruby unbounded-knapsack

Given some digits 3,4,8 can you make some sum, or how close can you get to that sum. Like 9, or 12, or 133234.

9 is easy: 3+3+3
12 is easy 4+8 or even 3+3+3+3
1234 is not easy.

So, in the beginning it's easy.

So, how do you build up to the bigs?

You start thinking...What's the closest I can get to 1? 2? 3? .... 300? ....1234?

If I can figure out 1, 2, 3....., 300, surely I can get to 1234

because ex. 1234 = 300 + 300 + 300 + 300 + 34
so... the closest sum to 1234 = closest(300) + closest(300) + closest(300) + closest(300) + closest(34)

So the next reasonable question.... Sure, that's one way to get to 1234, but there's also myriad other combinations, so
closest(299) + closest(301) + closest(300) + closest(300) + closest(34)
would HAVE to get us
the SAME result as
closest(300) + closest(300) + closest(300) + closest(300) + closest(34)

We're given these numbers to work with....3,4, and 8
So we know any multiple of 3, 4, and 8
OR
any combination of any multiple of these guys
IS VALID

This mathematical expression expresses that:

3*i + 4*j + 8*k where 0 <= i,j,k <= ~450 ( 3*450 is > 1234 )

Now, let's start building.

What's the closest to 0 with 3,4,8 -> maxSum[0] = 0

1? -> maxSum[1] = 0

2? -> maxSum[2] = 0

3? -> maxSum[3] = 3

4? -> maxSum[4] = 4 

5? -> maxSum[5] = 4
6? -> maxSum[6] = 6 (3+3) 
7? -> maxSum[7] = 7 (3+4)
8? -> maxSum[8] = 8 
9? -> maxSum[9] = 9 (6+3)
10? -> maxSum[10] = 10  (6+4)
11? -> maxSum[11] = 11 (8+3)
12? -> maxSum[12] = 12 (9+3)
etc
etc

"I have to make my new maxSum[n] by adding either 3,4, or 8 (my only options) from a previous maxSum." So what are these "previous" maxSums? Well, they are the maxSums either a distance of 3, 4, or 8 away: maxSum[n-3], maxSum[n-4], or maxSum[n-8]

Which one to use? Well, which one gives you the MAX SUM?!

So, we take the max of:
             maxSum[n-3] + 3 
             maxSum[n-4] + 4
             maxSum[n-8] + 8 

The code in Ruby:

# Enter your code here. Read input from STDIN. Print output to STDOUT
def calculateAnswer(elements, capacity, memArr)
    for weight in 1..capacity do
        for i in 0...elements.length do
            evaluateElement(elements[i], weight, memArr)
        end
    end
    answer = capacity - (memArr.map{|val| capacity - val}.select{|val| val >= 0}.min)
    puts answer
end

def evaluateElement(element, weight, memArray)
    if element <= weight
        memArray[weight] = [memArray[weight],(element + memArray[weight - element])].max
    end
end

t = gets.chomp.to_i
t.times do
    n,expected_sum = gets.strip.split(' ').map(&:to_i)
    list = gets.strip.split(' ').map(&:to_i)
    memArr = Array.new(2001,0)
    calculateAnswer(list, expected_sum, memArr)
end 

   

BREADTH FIRST SEARCH

Visit. Queue

A.  [B,C]

B.  [C,D,E,F]

Gimme a Queue (First in, First out)
Push a Node

While queue is NOT empty
     Visit first in Queue
     Add Children to Queue

DEPTH FIRST SEARCH
Visit. Next in Line
A [B,C]
B [D,E,F,C]
D [E,F,C]
Visit Node
DFS for Node Children

HACKERRANK Ruby MINIMUM LOSS

# Enter your code here. Read input from STDIN. Print output to STDOUT

n = gets.chomp.to_i

vals = gets.chomp.split(" ").map(&:to_i)

min_diff = (1.0)/(0.0)

for i in 1...(vals.length)
    # compare all nums that come before val at index i
    for j in (i-1).downto(0)
        computed_diff = (vals[j] - vals[i])
        min_diff = computed_diff if computed_diff > 0 && computed_diff < min_diff
    end
end

puts min_diff




TIMEOUT for some of the solutions
Would sorting the already compared ints in array save run time?

Ex. 20 7 8 5 2
7 compared to 20                 
8 compared to 20,7
5 compared to 20,7,8            if sorted 5 compared to 20,8,7   stop as soon as num is > 5

HACKERRANK Solution Ruby Gridland Metro

This code does NOT cover the case where two ranges of tracks in a row do NOT instersect


vars = gets.chomp.split(" ").map(&:to_i)

num_rows = vars[0]
num_cols = vars[1]
num_tracks = vars[2]
tracks_hash = {}


num_tracks.times do |i|
    track_set = gets.chomp.split(" ").map(&:to_i)
    row = track_set[0]
    start = track_set[1]
    end = track_set[2]
    if tracks_hash[row].nil?
        tracks_hash[row] = [start, end]
    else
        tracks_hash[row][0] = start if (tracks_hash[row][0] > start)
        tracks_hash[row][1] =end if (tracks_hash[row][1] < end)
    end
end

count = 0


row_tracks.each do |k,v|
    num_tracks = (v[0]-v[1]).abs + 1
    count += num_tracks
end

puts (num_rows* num_cols) - count