Joshua - 4 months ago 15

C# Question

I have been working on three small programs that extract all the sub-strings of a given string (or even a list of integers) as well as all the different combinations of their elements. I now understand them...

My aim to start like this (originally) was to see if I can solve a puzzle, by learning these programs. Here is the puzzle:

Say I am trekking and I have

`6`

`{ 11, 16, 5, 5, 12, 10 }`

`3`

Perhaps I could do only 11 kilometers during day 1, 16 and 5 and 5 kilometers during day 2, and 12 and 10 kilometers during day 3.

etc . . . etc . . .

My goal is to work out the "minimum" walked distance over the course of these three days. So, in this example, 11 in day 1 and 26 in day 2 and 22 in day 3 would give a maximum of 26, and that 26 is actually the minimum - it does not get better than this.

No matter what combination of three chunks (days) I choose, the daily walked distance doe not get less than 26. For example, if I choose 11+16 for day 1 and 5+5 for day 2 and 12+10 for days 3, I am looking at a max of 27.

However, I cannot quite figure out how to divide up the list elements in 3, which is the number of days. If it was four, I could have four chunks with arbitrary number of distances in each day. And then add up all the divided elements and see which maximum comes out as minimum.

I appreciate this might be a too-big-a-bite for me at this point (I can just about understand the programs that I have put below) but I was wondering if someone perhaps could help me understand this and help me write a function that can handle any number of days and walking stages.

All I have been able to produce so far is a function that can print all the sub-lists and combinations of these 6 walking stages...

`static void Main(string[] args)`

{

string str = Console.ReadLine();

for (int i = 1; i <= str.Length; i++)

{

for (int j = 0; j <= (str.Length - i); j++)

{

string subStr = str.Substring(j, i);

Console.WriteLine(subStr);

}

}

Console.ReadLine();

}

static void Main(string[] args)

{

List<int> list = new List<int>() { 11, 16, 5, 5, 12, 10 };

for (int i = 0; i <= list.Count-1; i++)

{

for (int j = 0; j <= list.Count-i; j++)

{

string subList = string.Concat( list.GetRange(i, j) );

Console.WriteLine(subList);

}

}

Console.ReadLine();

}

static void Main(string[] args)

{

GetCombination( new List<int> { 11, 16, 5, 5, 12, 10 } );

Console.ReadLine();

}

static void GetCombination( List<int> list )

{

double count = Math.Pow(2, list.Count);

for (int i = 1; i <= (count-1); i++)

{

string str = Convert.ToString(i, 2).PadLeft(list.Count, '0');

for (int j = 0; j < str.Length; j++)

{

if ( str[j] == '1' )

{

Console.Write( list[j] );

}

}

Console.WriteLine();

}

}

Answer

This problem can be solved by dynamic programming. Here is my code for it with top-down approach:

```
class Program
{
static void Main(string[] args)
{
int[] array = { 11, 16, 5, 5, 12, 10 };
// change last parameter to the number or days
int min = MinDistance(array, 0, 0, 3);
Console.WriteLine(min);
}
static int MinDistance(int[] array, int day, int prevDayDistance, int daysLeft)
{
if (day == array.Length)
{
return prevDayDistance;
}
if (daysLeft == 0)
{
return int.MaxValue;
}
// Keep walking.
int keepWalkResult = MinDistance(array, day + 1, prevDayDistance + array[day], daysLeft);
// Postpone it to the next day.
int sleepResult = MinDistance(array, day, 0, daysLeft - 1);
// Choose the best solution.
return Math.Min(keepWalkResult, Math.Max(prevDayDistance, sleepResult));
}
}
```

For big input arrays you can consider caching `MinDistance`

results for triples `(day,prevDayDistance,daysLeft)`

.