# Solving the Lazy Hobo Riddle

I would like help in optimizing this calculation, which is from the Lazy Hobo Riddle:

There once were 4 hoboes travelling across the country. During their journey, they ran short on funds, so they stopped at a farm to look for some work. The farmer said there were 200 hours of work that could be done over the next several weeks. The farmer went on to say that how they divided up the work was up to them. The hoboes agreed to start the next day.

The following morning, one of the hoboes - who was markedly smarter and lazier than the other 3 - said there was no reason for them all to do the same amount of work. This hobo went on to suggest the following scheme:

• The hoboes would all draw straws.
• A straw would be marked with a number.
• The number would indicate both the number of days the drawer must work and the number of hours to be worked on each of those days. For example, if the straw was marked with a 3, the hobo who drew it would work 3 hours a day for 3 days.

It goes without saying that the lazy hobo convinced the others to agree to this scheme and that through sleight of hand, the lazy hobo drew the best straw.

The riddle is to determine the possible ways to divide up the work according to the preceding scheme.

It basically just involves finding all possible solutions of $a,b,c,d$ such that $a^{2} + b^{2} + c^{2} + d^{2} = 200$

for(int a = 1;a<=100; a++)
for(int b = 1; b<=100; b++)
for(int c = 1; c<=100; c++)
for(int d = 1; d<=100; d++){
++counter;
if(a*a + b*b + c*c + d*d == 200)
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
}

• What is counter doing? – Quaxton Hale Oct 9 '14 at 6:10
• I was counting the iterations. – user54410 Oct 9 '14 at 6:10
• You have a hundred million passes through the loop here. Since 15^2 is already over 200 you really only need 14^4 = 38,416 passes. – Loren Pechtel Oct 13 '14 at 3:14

Notice how the square of a number 15 or greater exceeds 200? What you can do, is set the interval from 1 to 14. There is no advantage in evaluating the same combination over and over again. Realize that the most efficient way is to structure your for loops such that

$$a \leq b \leq c \leq d$$

In your attempt, you are iterating 38,416 times!

By limiting the interval, you iterate just 2380 times!

One more thing you can do: check and break when $a^{2} + b^{2} + c^{2} + d^{2} > 200$

for(int a = 1; a<=14; a++)
for(int b = a; b<=14; b++)
for(int c = b; c<=14; c++)
for(int d = c; d<=14; d++){
if(a*a + b*b + c*c + d*d == 200)
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
else if(a*a + b*b + c*c + d*d > 200)
break;
}


Now you iterate only 1,214 times! This is way more efficient.

• Was currently writing an answer along the same lines on my phone.... but damn that's slow as heck. Nice numbers though +1 – Vogel612 Oct 9 '14 at 6:20
• Let us assume a==14 this would result in 196 + b^2 + c^2 +d^2 == 200 this can't happen either. So you can limit the loop by 13 – Heslacher Oct 9 '14 at 6:26
• A spoon of tar if I may. The proposed solution is $O(n^2)$ (4 nested loops upto $\sqrt n$ each. Surely we can do better. Build a table of squares ($O(\sqrt n)$ time and space). Build a table of pairwise sums of squares ($O(n)$ time and space). Find all pairs adding up to target ($O(n)$ time, $O(1)$ space). – vnp Oct 9 '14 at 6:39
• @vnp how would it fulfill the condition that a <= b <= c <= d. If there is an $O(n)$ solution, it deserves it's own answer. – abuzittin gillifirca Oct 9 '14 at 6:55
• @IvoBeckers Check my solution for a similar idea. I made the loops go from big numbers to small to reduce the time spent in comparisons, but essentially it's the same idea. – Tibos Oct 9 '14 at 14:49

One thing you should note is that the fourth iteration is useless. Once you fixed the first 3 variables, you need to find the value for the fourth one that equals to 200 minus the sum of squares of the first 3. You don't have to go through all the possible numbers to check if one of them squared is equal to N, you can simply take the square root of N and check if it's an integer or not.

Another thing to notice is that you get the same solution several times in different order. This can be easily avoided (and avoid a lot of iterations because of it) by ordering the variables.

Finally, you can reduce the number of iterations if you fail early. Once you check a = 15 and see that a squared is more than 200, you no longer need to check higher values for a.

The clever thing to do is order the variables in descending order starting from the highest number that might still result in a solution.

Solution:

int N = 200;
for (int a = (int) sqrt(N); a >= 0; a--) {
for (int b = min(a, (int) sqrt(N - a*a)); b >= 0; b--) {
for (int c = min(b, (int) sqrt(N - a*a - b*b)); c >= 0; c--) {
double remaining = sqrt(N - a*a - b*b - c*c);
int d = (int) remaining;
if ((d == remaining) && (d <= c)) {
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
}
}
}
}


I apologize for possible type related errors, i haven't written C in ages.

Output:

a: 14 b: 2 c: 0 d: 0
a: 12 b: 6 c: 4 d: 2
a: 10 b: 10 c: 0 d: 0
a: 10 b: 8 c: 6 d: 0
a: 8 b: 8 c: 6 d: 6
iterations: 353

• You will find this does not generate the same results as the original. I see were you are going but there is one more step you need to add for you solution. for each found solutions, you also need to find all permutations. – Martin York Oct 10 '14 at 9:45
• Actually, the third loop is redundant, too. By Legendre's three squares theorem, a number can be expressed as the sum of three squares unless it is of the form (8m+7)4^n for integers m and n. 200 is not of this form (200=8*5*5), so there must be a solution of the form a^2 + b^2 + c^2 + 0 = 200 and you only need to loop to calculate a and b; the lazy hobo does no work. (Or, if you're a lazy programmer, you just assert that the lazy hobo knows Legendre's three squares theorem so finds a solution with d=0.) – David Richerby Oct 10 '14 at 10:28
• @DavidRicherby It does not help with finding all the solutions. – Tibos Oct 10 '14 at 10:58
• @Tibos Sure, if you want all the solutions Legendre doesn't help much. I'd not noticed that part of the question but I think I'll leave my comment as it's related (and, I think, interesting). – David Richerby Oct 10 '14 at 11:07
• sqrt is expensive. I would fill a 1..200 array with zeros and then for 1..14 assign the slot with the square to the value. Get 200 -a^2-b^2-c^2, if the entry is non-zero it's d, otherwise there's no answer for that a, b, c. – Loren Pechtel Oct 13 '14 at 3:19

Some minor things, but may still be worth mentioning:

Whenever std::endl is used, the buffer gets flushed, which can add to performance a bit, especially if it's done multiple times.

In order to get a newline without this added flush, use "\n" within an output statement:

std::cout << "\n";


for (int a = 1; a <= 100; a++)

• Namespace std is used... that's usually not good, right? ? – Vogel612 Oct 9 '14 at 6:27
• @Vogel612: Yeah, but I didn't mention it here since it's an even minor point. – Jamal Oct 9 '14 at 6:28

Style

Vogel612 raises an interesting point in his comment : using namespace std; is usually considered a bad practice.

Also, you should try to avoid having the same number hardcoded in different places : you could just use const int lim = 200;. It makes things easier to read/understand and easier to maintain : win-win !

Optimisation

Riding on EngieOP (and a bit on rolinger)'s answers : you can limit yourself to :

$$a \leq b \leq c \leq d$$

This leads to interesting conclusions to be found :

$$4 * a^{2} \leq a^{2} + b^{2} + c^{2} + d^{2} = 200$$ so $$a^{2} \leq 50$$ so $$a \leq 7$$

We can take this advantage in code by stopping when we know there is no hope to find more.

Let's forget about math and write this thing in simple C++ (storing the different computed values in variable for reuse) :

int main(int argc, char* argv[])
{
const int lim = 200;
std::cout << "Hello, world!" << std::endl;
for(int a = 1; 4*a*a <= lim; a++)
{
int tmp1 = a*a;
for(int b = a; tmp1 + 3*b*b <= lim; b++)
{
int tmp2 = tmp1 + b*b;
for(int c = b; tmp2 + 2*c*c <= lim; c++)
{
int tmp3 = tmp2 + c*c;
for(int d = c; tmp3 + d*d <= lim; d++){
if (tmp3 + d*d == lim)
std::cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << std::endl;
}
}
}
}
return 0;
}


More optimisations for you to consider

When a, b and c are fixed, looking for d could be optimised even more : we want to solve

$$d^{2} = lim - (a^{2} + b^{2} + c^{2})$$

You can just compute the root and see if it corresponds to an integer bigger than c.

As well as the excellent information from @EngieOP, you could also think about taking some repeated calculations out of the inner loop at the cost of an extra int per 'for' loop. These might be optimised by the compiler, but it shouldn't reduce clarity.

for(int a = 1; a<=14; a++){
sum_a = a*a;
for(int b = a; b<=14; b++){
sum_b = sum_a + b*b;
for(int c = b; c<=14; c++){
sum_c = sum_b + c*c;
/*[... etc ...] */


It won't reduce the number of iterations, but could reduce the number of cycles in the inner loop to a single add and compare (if the compiler doesn't already catch the optimisation and do it for you)

• We can extend this approach to reduce the number of iterations by adding a small test to the inner for-loops, i.e. for(int c = 1; c<=14 && sumB < 200; c++) and for(int d = 1; d<=14 && sumC < 200; d++). Done this way, the search produces the same result with 17,458 iterations instead of 38,416. – Desty Feb 6 '15 at 11:34

One thing to consider, doing repeated multiplications inside a loop and/or inside the loop declaration can be very expensive. Consider the following, which puts all the squares in an array and the loops only iterate through the array. This eliminates a lot of extra calculations. In my tests, even with the cost of an extra loop, this resulted in about a 30% increase in speed.

int squares[15];
const int limit = 200;
int it_limit = 15;
for (int i = 1; i < it_limit; i++)
squares[i] = i*i;
int temp = 0;
for (int a = 1; a < it_limit; a++)
{
temp = squares[a];
for (int b = a; b < it_limit; b++)
{
temp = squares[b] + squares[a];
if (temp > limit)
break;
for (int c = b; c < it_limit; c++)
{
temp = squares[c] + squares[b] + squares[a];
if (temp > limit)
break;
for (int d = c; d < it_limit; d++)
{
temp = squares[d] + squares[c] + squares[b] + squares[a];
if (temp > limit)
break;
if (temp == limit)
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << "\n";
}
}

}

}


Finding all the solutions in a low number of iterations:

#include <iostream>
#include <sstream>
#include <map>
#include <vector>

typedef unsigned int T;

int main()
{
const T LIMIT = 2000000;
std::map< T,std::vector< std::pair< T,T > > > pairs_of_squares;
T a, b, c, d, sum_of_squares, remaining;
unsigned long increment = 0;
unsigned long num_results = 0;
unsigned long index;
std::vector< std::pair< T, T > > array_of_pairs;
std::stringstream out;

for ( a = 1; 2 * a * a <= LIMIT - 2; ++a )
{
for ( b = a; (sum_of_squares = a*a + b*b) <= LIMIT - 2; ++b )
{
remaining = LIMIT - sum_of_squares;
// Check if it is possible to get another pair (c,d) such that either
// a <= b <= c <= d or c <= d <= a <= b and, if not, ignore this pair.
if ( a * a * 2 < remaining && remaining < b * b * 2 )
{
++increment;
continue;
}
pairs_of_squares[sum_of_squares].push_back( std::pair<T,T>(a,b) );

if ( pairs_of_squares.count( remaining ) != 0 )
{
array_of_pairs = pairs_of_squares[ remaining ];
for ( index = 0; index < array_of_pairs.size(); ++index )
{
c = array_of_pairs[index].first;
d = array_of_pairs[index].second;
if ( b <= c )
{
out         << a
<< ", " << b
<< ", " << c
<< ", " << d
<< '\n';
++num_results;
}
else if ( d <= a )
{
out         << c
<< ", " << d
<< ", " << a
<< ", " << b
<< '\n';
++num_results;
}
++increment;
}
}
else
{
++increment;
}
}
}

std::cout << out.str()
<< num_results << " possibilities found in " << increment << " increments." << std::endl;
return 0;
}


Output:

For a limit of 200:

2, 4, 6, 12
6, 6, 8, 8
2 possibilities found in 75 increments.

real    0m0.005s
user    0m0.003s
sys 0m0.002s


[Note: this only takes 75 iterations rather than over 1,000 to find all the possible answers.]

For a limit of 2,000,000:

...
104, 192, 984, 992
56, 112, 984, 1008
1221 possibilities found in 785771 increments.

real    0m0.890s
user    0m0.873s
sys 0m0.014s


Explanation:

Do not work on all 4 numbers individually - work on two pairs of numbers (a low valued pair and a high valued pair).

Start by generating a pair of numbers $(a,b)$ where $a \leq b$ and $a^2 + b^2 \leq LIMIT - 2$ (note: 2 is the minimum sum of squares for the other pair of numbers) and push that pair of numbers into a map.

It then checks whether the map contains another pair $(c,d)$ where $c \leq d$ and $c^2 + d^2 = LIMIT - a^2 - b^2$ such that either $a \leq b \leq c \leq d$ or $c \leq d \leq a \leq b$ in which case it is a valid answer and outputs it.

Then repeat for other pairs of $(a,b)$.

After reading the John's comment I thought we can do much better than EngieOP's answer

for(int a = 1; a<=14; a++)
for(int b = a; b<=14; b++)
for(int c = b; c<=14; c++)
for(int d = c; d<=14; d++){
if(a*a + b*b + c*c + d*d == 200)
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
else if(a*a + b*b + c*c + d*d > 200)
break;
}


How to speed this up ? Reduce the calculations !

int resultToReach = 200;
int maxBorder = (int)sqrt(200);
for(int a = 1; a<=maxBorder ; a++)
for(int b = a; b<=maxBorder ; b++)
for(int c = b; c<=maxBorder ; c++)
for(int d = c; d<=maxBorder ; d++){
int tempResult = a*a + b*b + c*c + d*d;
if(tempResult == resultToReach)
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
else if(tempResult > resultToReach)
break;
}


But in this way we still calculate a*a + b*b + c*c + d*d for each iteration. So let us reduce them like rolinger's answer already shows

    int resultToReach = 200;
int maxBorder = (int)sqrt(resultToReach);
for (int a = 1; a <= maxBorder; a++)
{
int firstResult = resultToReach - a * a;
for (int b = a; b <= maxBorder; b++)
{
int secondResult = firstResult - b * b;
for (int c = b; c <= maxBorder; c++)
{
int thirdResult = secondResult - c * c;
for (int d = c; d <= maxBorder; d++)
{
int tempResult = thirdResult - d * d;
if (tempResult == 0)
{
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
break;
}
else if (tempResult < 0)
{
break;
}
}
}
}
}


If we now reverse the loops and also adding some minor conditions we will get this

    int resultToReach = 200;
int maxBorder = (int)sqrt(resultToReach);

for (int a = maxBorder; a >= 1; a--)
{
int firstResult = resultToReach - a * a;
if (firstResult >= 3)
{
for (int b = a; b >= 1; b--)
{
int secondResult = firstResult - b * b;
if (secondResult >= 2)
{
for (int c = b; c >= 1; c--)
{
int thirdResult = secondResult - c * c;
if (thirdResult >= 1)
{
for (int d = c; d >= 1; d--)
{
int tmpResult = thirdResult - d * d;
if (tmpResult == 0)
{
counter++;
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
break;
}
else if (tmpResult > 0)
{
break;
}
}
}
}
}
}
}
}


As I didn't had C++ by hand, I did the timing in C#. This calculates 1221 unique combinations for resultToReach==2000000 in about 19 seconds.

Taking Josay's comment into account produces this

    int resultToReach = 200;
int maxBorder = (int)sqrt(resultToReach);

for (int a = maxBorder; a >= maxBorder/4; a--)
{
int firstResult = resultToReach - a * a;
if (firstResult >= 3)
{
int firstBorder = (int)sqrt(firstResult);
for (int b = min(a, firstBorder); b >= firstBorder/3; b--)
{
int secondResult = firstResult - b * b;
if (secondResult >= 2)
{
int secondBorder = (int)sqrt(secondResult);
for (int c = min(b, secondBorder); c >= secondBorder/2; c--)
{
int thirdResult = secondResult - c * c;
if (thirdResult >= 1)
{
int d = (int)sqrt(thirdResult);
if (d <= c && thirdResult == d * d)
{
cout << "a: " << a << " b: " << b << " c: " << c << " d: " << d << endl;
}
}
}
}
}
}
}


As I didn't had C++ by hand, I did the timing in C#. This calculates 1221 unique combinations for resultToReach==2000000 in about 4.5 seconds.

I'm actually not OK with the assumption that the answer to the hobo question is solving a*a+b*b+c*c+d*d = 200 in an iterative fashion.

I think it is a square root and rounding question that can be solved with a greedy algorithm.

The guy with the highest workload could do a max of sqrt(200) = 14.142 hours for 14.142 days. Rounded down, that'd be 14*14=196, leaving only 4 hours of work for the other 3. That doesn't work.

Try 13... 200-(13*13)=31 for the other 3 and then check the next guy recursively, which gives the following code:

int find_worst_hours( int workleft, int numguys )
{
static int num_interations = 0;
int mine = (int)floor(sqrt((double)workleft));
TRACE( "Num iterations = %d\n", ++num_interations );
while( mine > 0 )   {
int leftover = workleft - mine*mine;
TRACE( "Guys Left %d:I would do %d, rest would do %d\n", numguys, mine, leftover );
if ( numguys == 1 ) {
// last guy
if ( leftover > 0 ) {
return -1;      // bad solution, work left over.
} else {
// no work left, this is a good solution.
TRACE( "GOOD END, guy %d, work %d\n", numguys, mine );
return mine;
}
} else {
// check the rest of guys
if ( leftover == 0 )    {
return -1;      // bad solution, the other guys need work
}
int next_guys_work = find_worst_hours( leftover, numguys-1 );
if ( next_guys_work > 0 )   {
// valid solution
TRACE( "GOOD PARTIAL, guy %d, work %d\n", numguys, mine );
return mine;
} else {
// couldn't find a solution... try less hours
mine--;
// continue while loop
}
}

}
return -1;      // couldn't find solution
}


Which you can call once with:

find_worst_hours( 200, 4 );


And it should output:

Num iterations = 1
Guys Left 4:I would do 14, rest would do 4
Num iterations = 2
Guys Left 3:I would do 2, rest would do 0
Guys Left 4:I would do 13, rest would do 31
Num iterations = 3
Guys Left 3:I would do 5, rest would do 6
Num iterations = 4
Guys Left 2:I would do 2, rest would do 2
Num iterations = 5
Guys Left 1:I would do 1, rest would do 1
Guys Left 2:I would do 1, rest would do 5
Num iterations = 6
Guys Left 1:I would do 2, rest would do 1
Guys Left 3:I would do 4, rest would do 15
Num iterations = 7
Guys Left 2:I would do 3, rest would do 6
Num iterations = 8
Guys Left 1:I would do 2, rest would do 2
Guys Left 2:I would do 2, rest would do 11
Num iterations = 9
Guys Left 1:I would do 3, rest would do 2
Guys Left 2:I would do 1, rest would do 14
Num iterations = 10
Guys Left 1:I would do 3, rest would do 5
Guys Left 3:I would do 3, rest would do 22
Num iterations = 11
Guys Left 2:I would do 4, rest would do 6
Num iterations = 12
Guys Left 1:I would do 2, rest would do 2
Guys Left 2:I would do 3, rest would do 13
Num iterations = 13
Guys Left 1:I would do 3, rest would do 4
Guys Left 2:I would do 2, rest would do 18
Num iterations = 14
Guys Left 1:I would do 4, rest would do 2
Guys Left 2:I would do 1, rest would do 21
Num iterations = 15
Guys Left 1:I would do 4, rest would do 5
Guys Left 3:I would do 2, rest would do 27
Num iterations = 16
Guys Left 2:I would do 5, rest would do 2
Num iterations = 17
Guys Left 1:I would do 1, rest would do 1
Guys Left 2:I would do 4, rest would do 11
Num iterations = 18
Guys Left 1:I would do 3, rest would do 2
Guys Left 2:I would do 3, rest would do 18
Num iterations = 19
Guys Left 1:I would do 4, rest would do 2
Guys Left 2:I would do 2, rest would do 23
Num iterations = 20
Guys Left 1:I would do 4, rest would do 7
Guys Left 2:I would do 1, rest would do 26
Num iterations = 21
Guys Left 1:I would do 5, rest would do 1
Guys Left 3:I would do 1, rest would do 30
Num iterations = 22
Guys Left 2:I would do 5, rest would do 5
Num iterations = 23
Guys Left 1:I would do 2, rest would do 1
Guys Left 2:I would do 4, rest would do 14
Num iterations = 24
Guys Left 1:I would do 3, rest would do 5
Guys Left 2:I would do 3, rest would do 21
Num iterations = 25
Guys Left 1:I would do 4, rest would do 5
Guys Left 2:I would do 2, rest would do 26
Num iterations = 26
Guys Left 1:I would do 5, rest would do 1
Guys Left 2:I would do 1, rest would do 29
Num iterations = 27
Guys Left 1:I would do 5, rest would do 4
Guys Left 4:I would do 12, rest would do 56
Num iterations = 28
Guys Left 3:I would do 7, rest would do 7
Num iterations = 29
Guys Left 2:I would do 2, rest would do 3
Num iterations = 30
Guys Left 1:I would do 1, rest would do 2
Guys Left 2:I would do 1, rest would do 6
Num iterations = 31
Guys Left 1:I would do 2, rest would do 2
Guys Left 3:I would do 6, rest would do 20
Num iterations = 32
Guys Left 2:I would do 4, rest would do 4
Num iterations = 33
Guys Left 1:I would do 2, rest would do 0
GOOD END, guy 1, work 2
GOOD PARTIAL, guy 2, work 4
GOOD PARTIAL, guy 3, work 6
GOOD PARTIAL, guy 4, work 12


So it took only 33 iterations and we found the answer 2,4,6,12. This should be VERY fast to calculate.

• And how about 6^2 + 6^2 + 8^2 + 8^2 ? – Heslacher Oct 9 '14 at 14:47
• Could you change the algorithm to determine all the possible solutions? As it is right now it exits at the first solution which is not what the OP asked for. – Tibos Oct 9 '14 at 14:57
• Tibos - I'll do that if I have time, but since it is a greedy algorithm, and this guy is a greedy hobo, the first solution is the only solution in his mind. – Novicaine Oct 9 '14 at 15:09
• Except that it's clearly stated The riddle is to determine the possible ways to divide up the work according to the preceding scheme. Notice it says possible ways not the best way. – tinstaafl Oct 9 '14 at 15:42
• @DavidRicherby - Which is exactly the point I was making. – tinstaafl Oct 10 '14 at 12:15