« first day (4 days earlier)    last day (15 days later) » 

6:02 AM
@WayneConrad Hi... you there ?
 
 
7 hours later…
1:16 PM
Hello
 
Hi
How would I solve this using Ruby ?
I am not able to understand
 
2:15 PM
What do you not understand?
 
3:09 PM
@WayneConrad The whole algorithm.... I am not good with that olanguage
 
The algorithm is described in English in the three bullet points under "The detail is as follows"
 
I am not getting the second bullet point
I did -
input_string = '1101000'
input_ary = input_string.chars.map { |c| c == '0' ? -1 : c.to_i }
# => [1, 1, -1, 1, -1, -1, -1]
cost_arry = input_ary.each_index.map { |i| input_ary[0..i].inject(:+) }
# => [1, 2, 1, 2, 1, 0, -1]
then second bullet point..
a bit confused
 
3:29 PM
Find the longest run in const_array where the first and last item of the run are equal.
 
I made it as hash -
input_string = '1101000'
input_ary = input_string.chars.map { |c| c == '0' ? -1 : c.to_i }
# => [1, 1, -1, 1, -1, -1, -1]
cost_hash = {}
input_ary.each_index { |i| cost_hash[i] = input_ary[0..i].inject(:+) }
cost_hash # => {0=>1, 1=>2, 2=>1, 3=>2, 4=>1, 5=>0, 6=>-1}
Here I am getting |j-i| as maximum for 2 entries.. My bad not getting what I am missing
 
4:42 PM
What happened to const_arry? You need it.
 
@WayneConrad I created hash... with const_ary I am not getting how to solve it.. this puzzle is a bit hard for me...
:(
@WayneConrad I didn't get what did you mean by long run.
 
A "run" is a subset of the array: a series of contiguous elements. In [1, 2, 1, 2, 1, 0, -1], the runs with equal first and last elements are [1, 2, 1], [1, 2, 1, 2, 1], [1, 2, 1], and [2, 1, 2]. Write code to find the longest run with equal first and last elements.
 
5:00 PM
Ok... Today, I don't know why my brain is not working... How to get it in O(n) time. ?
 
To get O(N) time you have to visit each array element a constant number of times (preferably just once).
 
Yes,,, that's I am not getting.. What I am trying is O(N2)
:(
 
What information would you collect if you went through the array just once?
 
Index..
 
Index of what?
Remember, you are trying to find the longest run with equal first and last values.
So you might care about the minimum and maximum index at which a given value occurs.
 
5:10 PM
I am trying somewhat below :
sub_ary = cost_arry.map.with_index do |e,i|
  cost_arry[i+1..-1].find_all { |j| e == j }
end

sub_ary # => [[1, 1], [2], [1], [], [], [], []]
But it is wrong..
 
5:30 PM
@WayneConrad But the longest run sub array is giving 11010, but it should give us 110100...
 
 
2 hours later…
7:27 PM
@WayneConrad Hi
I did -
input_string = '00011000001'

source_ary = input_string.chars

ary_after_transform = source_ary.map { |c| c == '0' ? -1 : c.to_i }

ar = []
ary_after_transform.each_index do |ind|
  index = ind + 1
  loop do
    sum = ary_after_transform[ind..index].inject(:+)
    break ar << source_ary[ind..index] if sum == 0
    break if index > ary_after_transform.size
    index += 1
  end
end

ar.max_by(&:size).join # => "0011"
but O(n2)
 

« first day (4 days earlier)    last day (15 days later) »