For my own development I try to write algorithms that I find on the Web/books/Udemy. One of the more interesting ones I've come across is the one looking for Widest Path Without Trees. In a nutshell: there are N trees (numbered from 0 to N-1) in a forest. The K-th tree is located at coordinates (X[K], Y[K]). The goal is to build the widest possible vertical path, such that there is no tree on it.
Expected result from the link should be:
Write a function:
def solution(X, Y)
that, given two arrays X and Y consisting of N integers each, denoting the positions of trees, returns the widest possible path that can be built.
Example 3:
Input: X = [4, 1, 5, 4], Y=[4, 5, 1, 3]
Output: 3
How to achieve that?
[EDIT]
What I've so far is to sort X array (Y doesn't matter I guess(?)) and iterate through each element to find length between those two:
> x
=> [4, 1, 5, 4]
> y
=> [4, 5, 1, 3]
> x.sort.map.with_index { |e, i| x[i 1] - x[i] unless x[i 1].nil?}.compact.max
=> 4
I don't know if there is a mistake inside the task or I don't understand something but my code produce 4 instead of 3.
CodePudding user response：
One way to figure out what is going wrong with your code is to step through what it does step-by-step.
You can do that using a debugger, inspecting the state of the program at each step, you can do that in a more manual fashion by printing out the state of the program at each step, or you can simply do it using pen and paper.
The first thing you do is create a new array which is the sorted version of x using the Array#sort method:
sorted_x = x.sort
#=> [1, 4, 4, 5]
The next thing you do is create an Enumerator for the Array#map method of said sorted array:
map_enum = sorted_x.map
map_enum.to_a
#=> [1, 4, 4, 5]
Next, you use Enumerator#with_index to pair each element with its index:
map_with_index_enum = map_enum.with_index
map_with_index_enum.to_a
#=> [[1, 0], [4, 1], [4, 2], [5, 3]]
Within the block you pass to Enumerator#with_index, you use the array destructuring feature of block argument binding to bind the element to e and the index to i, which gives you the following bindings for each iteration of the block:
| Iteration | e |
i |
|---|---|---|
| 1 | 1 |
0 |
| 2 | 4 |
1 |
| 3 | 4 |
2 |
| 4 | 5 |
3 |
However, within the block you never use e anywhere, so it is actually completely irrelevant:
| Iteration | i |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
Really, all that you are doing in the block is counting up from 0 to x.size - 1, or in other words, iterating over all indices of x. You never make use of the elements of the sorted array sorted_x, so the whole song and dance with sorting x and mapping it with the indices is superfluous. You could just use something like
x.each_index.map {|i| x[i 1] - x[i] unless x[i 1].nil? }.compact.max
or
x.each_index.filter_map {|i| x[i 1] - x[i] unless x[i 1].nil? }.max
instead.
But that's just a side-note, let's just step through the block step-by-step:
| Iteration | i |
x[i 1] |
x[i] |
result |
|---|---|---|---|---|
| 1 | 0 |
x[1] == 1 |
x[0] == 4 |
1 - 4 == -3 |
| 2 | 1 |
x[2] == 5 |
x[1] == 1 |
5 - 1 == 4 |
| 3 | 2 |
x[3] == 4 |
x[2] == 5 |
4 - 5 == -1 |
| 4 | 3 |
x[4] == nil |
x[3] == 4 |
nil |
Or, in short, the result of the iteration is the array
result = [-3, 4, -1, nil]
As the next step, you use Array#compact to remove all nil elements, which results in
compacted_result = result.compact
#=> [-3, 4, -1]
And lastly, you use Array#max to find the largest element of the compacted result:
compacted_result.max
#=> 4
What your algorithm is doing is just computing the difference between neighboring elements of x and finding the maximum, which could be expressed in Ruby like this:
x.each_cons(2).map { |a, b| b - a }.max
#=> 4
Actually, we are only interested in the absolute difference between neighboring elements, so we should use Numeric#abs inside the block:
x.each_cons(2).map { |a, b| (b - a).abs }.max
#=> 4
or alternatively, map the result to the absolute value:
x.each_cons(2).map { |a, b| b - a }.map(&:abs).max
#=> 4
However, as you can see, that doesn't change the outcome.
The major problem is that there is no relationship between the neighboring elements, so taking their difference does not make sense. However, when we sort the array, then the neighboring elements in the sorted array actually represent neighboring trees in the forest, and suddenly, it does make sense to take their difference:
x.sort.each_cons(2).map { |a, b| b - a }.max
#=> 3
Note that we no longer need to take the absolute difference because the fact that the array is in non-decreasing order guarantees that the difference of neighboring elements is always non-negative.
So, that is the problem with your code: you are taking the difference of neighboring elements in x, but those neighboring elements are actually not related to each other in the real-world problem you are trying to solve.
You had the right idea in sorting the array, but you never used the sorted array anywhere.
The real problem, though, is that you are not writing Ruby code. Ruby, like most modern mainstream programming languages, has a powerful collections library with all sorts of higher-level iterators such as map, reduce, select, and many, many more. In Ruby, whenever you have to fiddle with array indices, loops, or even with each or its friends, that is a sure sign that you are doing something wrong.
In all that fiddling with indices, you lost track of the fact that you are never actually using the sorted array anywhere. This would have been much more obvious if you had written your code in a more Ruby style, e.g. here:
x.sort.each_cons(2).map { |a, b| b - a }.max
# vs.
x.each_cons(2).map { |a, b| b - a }.max