Solving the Lazy Hobo Riddle

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

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";

Also, consider adding a bit more whitespace within the multiple loop statements for added readability:

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

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)

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.

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;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

This calculates 1221 unique combinations for resultToReach==2000000 in about 19 seconds using C#.

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;
                            }
                        }
                    }
                }
            }
        }
    }

This calculates 1221 unique combinations for resultToReach==2000000 in about 4.5 seconds using C#.

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";
            }
        }

    }

}

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.

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)\$.

Combining a lot of suggestions from above and using Java as this is my favourite language, the following code performed quite well, I believe:

class x {
    public static void main(String argv[])
    {
        int a, b, c, d;
        int tmp1, tmp2, tmp3;
        int alim, blim, clim, dlim;

        int lim = 2000000;

        alim = (int) Math.sqrt(lim / 4);
        for(a = 1; a <= alim; a++) {
            tmp1 = a*a;
            blim = (int) Math.sqrt((lim - tmp1)/3);
            for(b = a; b <= blim; b++) {
                tmp2 = tmp1 + b*b;
                clim = (int) Math.sqrt((lim - tmp2)/2);
                for(c = b; c <= clim; c++) {
                    tmp3 = tmp2 + c*c;
                    d = (int) Math.sqrt(lim - tmp3);
                    if (tmp3 + d*d == lim)
                        System.out.println("a: " + a + " b: " + b + " c: " + c + " d: " + d);
                }
            }
        }
    }
}

A test revealed:

[ronald@cheetah tmp]$ time java x | wc -l
1221

real    0m1.553s
user    0m1.564s
sys 0m0.030s

which is even better than the 19s above. The main performance gain was reached by eliminating all superfluous calculations, and of course by eliminating all unnecessary iterations.

Of course, converting it back to c++ is easy.

Edit: A bit of explanation.

The algorithm produces solutions satisfying

a <= b <= c <= d

and (of course)

a^2 + b^2 + c^2 + d^2 == lim

Because of the first condition, the following must be true:

4 * a * a <= lim

This is the same as

a <= sqrt(lim / 4)

(since lim > 0). Having fixed a, the same kind of reasoning can be applied to b, because

a * a + 3 * b * b <= lim

hence

3 * b * b <= lim - a * a
b * b <= (lim - a * a) / 3
b <= sqrt((lim - a * a) / 3)

The upper limit of c can be calculated correspondingly. And we only have a solution if lim - a * a - b * b - c * c is a perfect square. No need to iterate in order to find d.

Using these rules an enormous amount of multiplications were eliminated at the cost of a few sqrt, which effectively sped up the algorithm by a factor of 100 or so.