C find all possible sides of a triangle from the perimeter

Question

I keep getting a negative number for c, b just prints 23, a is looping like it should. At least the output adds up to 24 when I put that in for the perimeter. I feel like I'm close just some stupid logic error. My code is below.

Write a program to find all the triangles with integer side lengths and a user specified perimeter. Your program should find all the triples a,b and c where a + b + c is user specified perimeter value.

  1 #include <stdio.h>
  2 
  3 int main() {
  4     int p, a, b, c;
  5     printf("Enter a perimeter: ");
  6     scanf("%d", &p);
  7 
  8     printf("Triangles with a perimeter: " " %d\n", p);
  9 
 10     for(a = 1; a < p; a++) {
 11         for(b = a;  b < p; b++)
 12             c = p - (a + b);
 13             b = p - (a + c);
 14             a = p - (b + c);
 15 
 16             printf("%d, %d, %d\n",a,b,c);
 17 
 18 }
 19     return 0;
 20 }

I think this is more of an interview question than a beginner problem.

Questions seeking debugging help ("why isn't this code working?") must include the desired behavior, a specific problem or error and the shortest code necessary to reproduce it in the question itself. Questions without a clear problem statement are not useful to other readers. See: How to create a Minimal, Complete, and Verifiable example. — too honest for this site, Feb 04 '17 at 02:28
To get the right answers mathematically you also need to think about the [triangle inequality](https://en.wikipedia.org/wiki/Triangle_inequality) — M.M, Feb 04 '17 at 02:41
You need to put brackets around your inner loop, right now on the outer loop has them — samgak, Feb 04 '17 at 02:46
Also, integer lengths pretty much guarantees that b and c will be at least 1. So you can shorten your loops a bit. — aghast, Feb 04 '17 at 03:17
You should also consider that `a + b` cannot be shorter than `c`. For example, `p=24`, when `a=1` and `b=1`, it can't be a triangle even though `c=24-(1+1)`. Imagine a triangle with `1`, `1`, and `22` sides? — alvits, Feb 04 '17 at 03:30

score 5 · Accepted Answer · edited May 23 '17 at 11:45

There's several things wrong in the original code. Some related to what makes a triangle a triangle and some are fundamental logic gone wrong.

for (a = 1; a < p; a++) is wrong because one side of a triangle can't be longer than half the perimeter. Even at half the perimeter, that will make 2 lines, not a triangle.

for (b = 1; b < (p - a); b++) is wrong because a+b will be smaller than half the perimeter at the start.

c is calculated based on the value of p, a and b.

c = p - (a + b);

What's the point of calculating b and a?

b = p - (a + c);
a = p - (b + c);

As Jonathan Leffler pointed out, the code should only print the unique triangles. This can be easily accomplished by adding a condition a<=b && b<=c before the printf statement.

Thanks to @JonathanLeffler for taking the time to debug this short code. A bug was found that caused the code to skip some output due to b being initialized to a higher value, and the inner for loop condition that terminates the loop prematurely.

Here's a corrected version of the code.

#include <stdio.h>
int main() {
    int p, a, b, c;
    printf("Enter a perimeter: ");
    scanf("%d", &p);

    printf("Triangles with a perimeter: " " %d\n", p);

    for (a = 1; 2*a < p; a++) {
        for (b = 1; a+b < p; b++)
            if ((p-2*a) > 0 && (p-2*b) > 0 && (2*a+2*b-p) > 0) {
                c = p - (a + b);
                if(a<=b && b<=c)
                    printf("%d, %d, %d\n", a ,b, c);
            }
    }
    return 0;
}

Now let's try it.

Enter a perimeter: 6
Triangles with a perimeter:  6
2, 2, 2

That's right. A triangle with perimeter 6 only has 1 possible combination. A 1, 1, 4 unit long sides will not be a triangle unless you are willing to bend the side that is 4 units long.

Enter a perimeter: 12
Triangles with a perimeter:  12
2, 5, 5
3, 4, 5
4, 4, 4

Great answer! I wasn't thinking of it from the standpoint of geometry and the rules of trig, merely programmatically based on what the asker provided, but this is very good work. Thanks! — clearlight, Feb 04 '17 at 04:28
This code is a lot more logical. I think you can tell I'm still a beginner. I'll have to do more practice problems. — slyalys, Feb 04 '17 at 06:28
I previously suggested that by adding the condition `if (a <=b && b <= c)` before the `printf()` for results, you can ensure that you only generate each combination of lengths once. I noted, for example, with p = 12, you get: `(2, 5, 5)`, `(3, 4, 5)`, `(4, 4, 4)` as the output. What I missed though is that with `p = 11`, adding the condition omits `(3, 5, 3)` (because the code does not generate `(3, 3, 5)` for reasons which elude me). So, the condition isn't good enough — it does eliminate a lot of duplicate entries (good) but does throw some non-duplicate entries away (bad). — Jonathan Leffler, Feb 05 '17 at 18:10
@JonathanLeffler - thanks for finding this bug. The elusive `3, 3, 5` is caused by the initial value of `b` being set to `(p-a)/2` which is `4`, in effect skipping `3, 3, 5`. Some other permutations are also skipped because `(p-2*a) > 0 && (p-2*b) > 0 && (2*a+2*b-p) > 0` causes the inner for loop to terminate prematurely. I'll modify and add your suggestion to limit the printout to unique triangles. — alvits, Feb 06 '17 at 18:46

score 2 · Answer 2 · edited May 23 '17 at 12:33

Duplicate information in the output

The currently accepted answer by alvits generates a lot of duplicate outputs where the combination is a permutation of the same combination of sides. I adapted the code to print all triangles for perimeters from 3 to 29, and also added a suggested condition if (a <= b && b <= c) before the printing operation.

`tp17.c`

^{Caution: incorrect code.}

#include <stdio.h>

int main(void)
{
    int p, a, b, c;
    // printf("Enter a perimeter: ");
    // scanf("%d", &p);
    for (p = 3; p < 30; p++)
    {
        printf("Triangles with perimeter: %d\n", p);

        for (a = 1; 2 * a < p; a++)
        {
            for (b = (p - a) / 2; (p - 2 * a) > 0 && (p - 2 * b) > 0 && (2 * a + 2 * b - p) > 0; b++)
            {
                c = p - (a + b);
                if (a <= b && b <= c)
                    printf("%d, %d, %d\n", a, b, c);
            }
        }
    }
    return 0;
}

The condition if (a <=b && b <= c) before the printf() for results is intended to ensure that you only generate each combination of lengths once. I noted, for example, with p = 12, you get: (2, 5, 5), (3, 4, 5), (4, 4, 4) as the output. What I missed though is that with p = 11, adding the condition omits (3, 5, 3) (because the code does not generate (3, 3, 5) for reasons which elude me). So, the condition isn't good enough — it does eliminate a lot of duplicate entries (good) but also throws some non-duplicate entries away (bad).

Consequently, the code should eliminate the condition, which leaves the program generating a lot of redundant outputs, greatly complicating output comparisons.

`tp13.c`

I also created a closely related program, starting from the same base:

#include <stdio.h>

int main(void)
{
    for (int p = 3; p < 30; p++)
    {
        printf("Triangles with perimeter: %d\n", p);
        for (int a = 1; a <= p / 2; a++)
        {
            for (int b = 1; b + a < p; b++)
            {
                int c = p - (a + b);
                if (a + b <= c || a + c <= b || b + c <= a)
                    continue;
                if (a <= b && b <= c)
                    printf("%d, %d, %d\n", a, b, c);
            }
        }
    }
    return 0;
}

Output comparisons

Part of the diff -u output from comparing tp13 and tp17 output is:

 Triangles with perimeter: 11
 1, 5, 5
 2, 4, 5
-3, 3, 5
+2, 5, 4
 3, 4, 4
+3, 5, 3
+4, 3, 4
+4, 4, 3
+4, 5, 2
+5, 3, 3
+5, 4, 2
+5, 5, 1
 Triangles with perimeter: 12
 2, 5, 5
 3, 4, 5
+3, 5, 4
 4, 4, 4
+4, 5, 3
+5, 3, 4
+5, 4, 3
+5, 5, 2
 Triangles with perimeter: 13

Looking at the results for a perimeter of 12, it is clear that tp17 just generates different permutations. However, looking at the results for a perimeter of 11 shows that tp17 generates (3, 5, 3) and (5, 3, 3) but not (3, 3, 5) whereas tp13 generates (3, 3, 5) and not the other two permutations. However, all the other extra lines in the output from tp17 in the fragment of output shown are permutations of other lines.

Different output formatting required

The output formats above do not lend themselves to automatic comparison, so I revised the output to print the perimeter followed by three sides listed in non-decreasing order. I therefore added code to tp17.c to sort the sides into non-decreasing order before printing. There are probably simpler ways to do it for three elements, but this works.

`tp47.c`

/* SO 4203-5818 - Calculate all triangles with given perimeter */
#include <stdio.h>
#include <stdlib.h>

static int int_cmp(const void *va, const void *vb)
{
    int a = *(int *)va;
    int b = *(int *)vb;
    return (a > b) - (a < b);
}

int main(void)
{
    int p, a, b, c;
    for (p = 3; p < 30; p++)
    {
        for (a = 1; 2 * a < p; a++)
        {
            for (b = (p - a) / 2; (p - 2 * a) > 0 && (p - 2 * b) > 0 && (2 * a + 2 * b - p) > 0; b++)
            {
                c = p - (a + b);
                {
                int d[] = { a, b, c };
                qsort(d, 3, sizeof(d[0]), int_cmp);
                printf("%d: %d, %d, %d\n", p, d[0], d[1], d[2]);
                }
            }
        }
    }
    return 0;
}

`tp43.c`

/* SO 4203-5818 - Calculate all triangles with given perimeter */

#include <stdio.h>

int main(void)
{
    for (int p = 3; p < 30; p++)
    {
        for (int a = 1; a <= p / 2; a++)
        {
            for (int b = 1; b + a < p; b++)
            {
                int c = p - (a + b);
                if (a + b <= c || a + c <= b || b + c <= a)
                    continue;
                if (a <= b && b <= c)
                    printf("%d: %d, %d, %d\n", p, a, b, c);
            }
        }
    }
    return 0;
}

(Except for the printing, this is the same as tp13.c.)

Comparisons

The outputs can now be sorted and compared. The -u option for tp43 is superfluous but symmetric.

$ tp43 | sort -u -k1n -k2n -k3n -k4n > tp43.out
$ tp47 | sort -u -k1n -k2n -k3n -k4n > tp47.out
$ diff tp43.out tp47.out
$

So, the unique outputs are the same, but when you count the differences, there are 390 extra lines in the output from tp47:

$ tp43 | sort -k1n -k2n -k3n -k4n > tp43-all.out
$ tp47 | sort -k1n -k2n -k3n -k4n > tp47-all.out
$ diff tp43-all.out tp47-all.out | diffcount
deleted 0, inserted 390
$ wc -l tp4?.out tp4?-all.out
     206 tp43.out
     206 tp47.out
     206 tp43-all.out
     596 tp47-all.out
    1214 total
$

Just for the record, the files tp43.out, tp47.out, tp43-all.out are identical. Their content is:

3: 1, 1, 1
5: 1, 2, 2
6: 2, 2, 2
7: 1, 3, 3
7: 2, 2, 3
8: 2, 3, 3
9: 1, 4, 4
9: 2, 3, 4
9: 3, 3, 3
10: 2, 4, 4
10: 3, 3, 4
11: 1, 5, 5
11: 2, 4, 5
11: 3, 3, 5
11: 3, 4, 4
12: 2, 5, 5
12: 3, 4, 5
12: 4, 4, 4
13: 1, 6, 6
13: 2, 5, 6
13: 3, 4, 6
13: 3, 5, 5
13: 4, 4, 5
14: 2, 6, 6
14: 3, 5, 6
14: 4, 4, 6
14: 4, 5, 5
15: 1, 7, 7
15: 2, 6, 7
15: 3, 5, 7
15: 3, 6, 6
15: 4, 4, 7
15: 4, 5, 6
15: 5, 5, 5
16: 2, 7, 7
16: 3, 6, 7
16: 4, 5, 7
16: 4, 6, 6
16: 5, 5, 6
17: 1, 8, 8
17: 2, 7, 8
17: 3, 6, 8
17: 3, 7, 7
17: 4, 5, 8
17: 4, 6, 7
17: 5, 5, 7
17: 5, 6, 6
18: 2, 8, 8
18: 3, 7, 8
18: 4, 6, 8
18: 4, 7, 7
18: 5, 5, 8
18: 5, 6, 7
18: 6, 6, 6
19: 1, 9, 9
19: 2, 8, 9
19: 3, 7, 9
19: 3, 8, 8
19: 4, 6, 9
19: 4, 7, 8
19: 5, 5, 9
19: 5, 6, 8
19: 5, 7, 7
19: 6, 6, 7
20: 2, 9, 9
20: 3, 8, 9
20: 4, 7, 9
20: 4, 8, 8
20: 5, 6, 9
20: 5, 7, 8
20: 6, 6, 8
20: 6, 7, 7
21: 1, 10, 10
21: 2, 9, 10
21: 3, 8, 10
21: 3, 9, 9
21: 4, 7, 10
21: 4, 8, 9
21: 5, 6, 10
21: 5, 7, 9
21: 5, 8, 8
21: 6, 6, 9
21: 6, 7, 8
21: 7, 7, 7
22: 2, 10, 10
22: 3, 9, 10
22: 4, 8, 10
22: 4, 9, 9
22: 5, 7, 10
22: 5, 8, 9
22: 6, 6, 10
22: 6, 7, 9
22: 6, 8, 8
22: 7, 7, 8
23: 1, 11, 11
23: 2, 10, 11
23: 3, 9, 11
23: 3, 10, 10
23: 4, 8, 11
23: 4, 9, 10
23: 5, 7, 11
23: 5, 8, 10
23: 5, 9, 9
23: 6, 6, 11
23: 6, 7, 10
23: 6, 8, 9
23: 7, 7, 9
23: 7, 8, 8
24: 2, 11, 11
24: 3, 10, 11
24: 4, 9, 11
24: 4, 10, 10
24: 5, 8, 11
24: 5, 9, 10
24: 6, 7, 11
24: 6, 8, 10
24: 6, 9, 9
24: 7, 7, 10
24: 7, 8, 9
24: 8, 8, 8
25: 1, 12, 12
25: 2, 11, 12
25: 3, 10, 12
25: 3, 11, 11
25: 4, 9, 12
25: 4, 10, 11
25: 5, 8, 12
25: 5, 9, 11
25: 5, 10, 10
25: 6, 7, 12
25: 6, 8, 11
25: 6, 9, 10
25: 7, 7, 11
25: 7, 8, 10
25: 7, 9, 9
25: 8, 8, 9
26: 2, 12, 12
26: 3, 11, 12
26: 4, 10, 12
26: 4, 11, 11
26: 5, 9, 12
26: 5, 10, 11
26: 6, 8, 12
26: 6, 9, 11
26: 6, 10, 10
26: 7, 7, 12
26: 7, 8, 11
26: 7, 9, 10
26: 8, 8, 10
26: 8, 9, 9
27: 1, 13, 13
27: 2, 12, 13
27: 3, 11, 13
27: 3, 12, 12
27: 4, 10, 13
27: 4, 11, 12
27: 5, 9, 13
27: 5, 10, 12
27: 5, 11, 11
27: 6, 8, 13
27: 6, 9, 12
27: 6, 10, 11
27: 7, 7, 13
27: 7, 8, 12
27: 7, 9, 11
27: 7, 10, 10
27: 8, 8, 11
27: 8, 9, 10
27: 9, 9, 9
28: 2, 13, 13
28: 3, 12, 13
28: 4, 11, 13
28: 4, 12, 12
28: 5, 10, 13
28: 5, 11, 12
28: 6, 9, 13
28: 6, 10, 12
28: 6, 11, 11
28: 7, 8, 13
28: 7, 9, 12
28: 7, 10, 11
28: 8, 8, 12
28: 8, 9, 11
28: 8, 10, 10
28: 9, 9, 10
29: 1, 14, 14
29: 2, 13, 14
29: 3, 12, 14
29: 3, 13, 13
29: 4, 11, 14
29: 4, 12, 13
29: 5, 10, 14
29: 5, 11, 13
29: 5, 12, 12
29: 6, 9, 14
29: 6, 10, 13
29: 6, 11, 12
29: 7, 8, 14
29: 7, 9, 13
29: 7, 10, 12
29: 7, 11, 11
29: 8, 8, 13
29: 8, 9, 12
29: 8, 10, 11
29: 9, 9, 11
29: 9, 10, 10