DAY 24
1

# 24 - Best travel

Don't say so much, just coding...

## Instruction

John and Mary want to travel between a few towns A, B, C ... Mary has on a sheet of paper a list of distances between these towns. `ls = [50, 55, 57, 58, 60]`. John is tired of driving and he says to Mary that he doesn't want to drive more than `t = 174` miles and he will visit only `3` towns.

Which distances, hence which towns, they will choose so that the sum of the distances is the biggest possible to please Mary and John?

Example:

With list `ls` and 3 towns to visit they can make a choice between: `[50,55,57],[50,55,58],[50,55,60],[50,57,58],[50,57,60],[50,58,60],[55,57,58],[55,57,60],[55,58,60],[57,58,60]`.

The sums of distances are then: `162, 163, 165, 165, 167, 168, 170, 172, 173, 175`.

The biggest possible sum taking a limit of 174 into account is then 173 and the distances of the 3 corresponding towns is `[55, 58, 60]`.

The function chooseBestSum (or `choose_best_sum` or ... depending on the language) will take as parameters t (maximum sum of distances, integer >= 0), `k` (number of towns to visit, k >= 1) and `ls` (list of distances, all distances are positive or null integers and this list has at least one element). The function returns the "best" sum ie the biggest possible sum of k distances less than or equal to the given limit t, if that sum exists, or otherwise nil, null, None, Nothing, depending on the language. With C++, C, Rust, Swift, Go, Kotlin return `-1`.

Examples:

`ts = [50, 55, 56, 57, 58] choose_best_sum(163, 3, ts) -> 163`

`xs =  choose_best_sum(163, 3, xs) -> nil (or null or ... or -1 (C++, C, Rust, Swift, Go)`

`ys = [91, 74, 73, 85, 73, 81, 87] choose_best_sum(230, 3, ys) -> 228`

### Ruby

#### Init

``````  def choose_best_sum(t, k, ls)
end
``````

#### Sample Testing

``````  Test.describe("choose_best_sum") do
Test.it("Basic Tests") do
ts = [50, 55, 56, 57, 58]
Test.assert_equals(choose_best_sum(163, 3, ts), 163)
ts = 
Test.assert_equals(choose_best_sum(163, 3, ts), nil)
ts = [91, 74, 73, 85, 73, 81, 87]
Test.assert_equals(choose_best_sum(230, 3, ts), 228)
end
end
``````

### Javascript

#### Init

``````  function chooseBestSum(t, k, ls) {
}
``````

#### Sample Testing

``````  Test.describe("chooseBestSum",function() {
Test.it("Basic tests ",function() {
var ts = [50, 55, 56, 57, 58]
Test.assertEquals(chooseBestSum(163, 3, ts), 163)
ts = 
Test.assertEquals(chooseBestSum(163, 3, ts), null)
ts = [91, 74, 73, 85, 73, 81, 87]
Test.assertEquals(chooseBestSum(230, 3, ts), 228)
})})
``````

# Thinking • Ruby
• JavaScript

# Solution

### Ruby

``````  # Solution 1
def choose_best_sum(t, k, ls)
ls.combination(k)
.map{ |array| array.reduce(:+) }
.select{ |sum| sum <= t }
.max
end

# Solution 2
def choose_best_sum(t, k, ls)
ls.combination(k).map(&:sum).reject { |n| n > t }.max
end
``````

### Javascript

``````  // Solution 1
function chooseBestSum(t, k, ls) {
var biggestCount = 0;
var recurseTowns = function(townsSoFar, lastIndex) {
townsSoFar = townsSoFar || [];

if (townsSoFar.length === k) {
var sumDistance = townsSoFar.reduce((a,b)=>a+b);
if (sumDistance <= t && sumDistance > biggestCount) {
biggestCount = sumDistance;
}
return;
}

for (var i = lastIndex + 1 || 0; i < ls.length; i++) {
recurseTowns(townsSoFar.concat(ls[i]), i);
}
}
recurseTowns();

return biggestCount || null;
}
``````