Struggling with pythagorean triplet exercise. How to progress?

Programming C
1

I am getting segmentation fault from the online editor. On my local machine, using my own tests (not created with Unity so not an exact match) to mimic those provided, and compiling with gcc and options:

-O0 -Wall -Wextra -pedantic -ansi -std=c99 -o -g

I get no errors or warnings.

I did not spot that I needed to create the free_triplets() function until the end. I added this and checked the memory address in the argument passed the clear_triplets() match the memory address created for the triplets structure create in the triplets_with_sum function. I made sure I called free on triple a structure of type triplet_t I created with a malloc() call in the triplets_with_sum_function() before returning from that function.

To find the triplets I started with a straightforward approach, simply looping over a and b. But after getting this to “work” on the first six tests I found that I needed a different approach for the test:

test_triplets_for_large_number()

So I rewrote my code using a parametrisation approach.

I would prefer not to simply unlock the community solutions.

Is there a way to get better debugging feedback than:

make: *** [makefile:22: test] Segmentation fault (core dumped)

when I get no error or warnings on my local machine that would help me find what I is at fault in my code?

2

If you share your code, people can look at it and suggest what might be causing the seg fault ;) If you want to debug it yourself, you can enable core dumps and use GDB to examine the state when the segfault occurs.

3

Would sharing my code not spoil the pleasure of solving the exercise for others?

I have no idea how to “enable core dumps”.

I use gdb regularly but as there is no segfault locally gdb will not show the state when the segfault occurs. The segfault is reported only by the online editor in Exercism.

4

You could wrap it in a spoiler. Though people that want to solve X on their own should probably realize that a “Help me solve X” thread is going to have spoilers :slight_smile: I wouldn’t worry about that.

That would depend on your OS. On Linux, it might be a ulimit and/or coredumpctl setting.

Ah… well, then enabling coredumps locally won’t help. Sharing code and getting eyes on it might be the best option.

5

I am not too familiar with C, but a segfault suggests to me that something is going wrong in your management of heap-allocated memory. So the way you find/compute the triples should be irrelevant; only the way you store them should matter.

6

I think you are probably correct.

My code is below:

triplets_t *triplets_with_sum(uint16_t sum)
{
    uint16_t s2 = sum / 2, mlimit, m, sm, a, b, c, d, k, n;

    mlimit = (uint16_t) (ceil(sqrt(s2)) - 1);

    triplet_t *triple = malloc(sizeof(triplet_t) + sizeof(uint16_t) * 3);
    triplets_t *out_triplets = malloc(sizeof(triplets_t) + sizeof(triplet_t));

    out_triplets->count = 0;

    for (m = 2; m <= mlimit; ++m)
    {
        if ( (s2 % m) == 0)
        {
            sm = s2 / m;
            while ( (sm % 2) == 0)
            {
                sm = sm / 2;
            }
            if ( (m % 2) == 1)
            {
                k = m + 2;
            }
            else
            {
                k = m + 1;
            }
            while ( (k < (2 * m)) && (k <= sm) )
            {
                if ( ((sm % k) == 0) && (gcd(k, m) == 1) )
                {
                    d = s2 / (k * m);
                    n = k - m;
                    a = d * (m * m - n * n);
                    b = 2 * d * m * n;
                    c = d * (m * m + n * n);
                    if (a + b + c == sum)
                    {
                        if (a > b)
                        {
                            swap(&a, &b);
                        }
                        triple->a = a;
                        triple->b = b;
                        triple->c = c;
                        out_triplets->triplets[out_triplets->count] = *triple;
                        out_triplets->count++;
                    }
                }
                k += 2;
            }
        }
    }
    free(triple);
    return out_triplets;
}

uint16_t gcd(uint16_t a, uint16_t b)
{
    uint16_t temp;

    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

void swap(uint16_t *a, uint16_t *b)
{
    uint16_t temp;

    temp = *a;
    *a    = *b;
    *b    = temp;
}

void free_triplets(triplets_t *triplets)
{
    if (triplets)
    {
        free(triplets);
    }  
}

and the pythagorean_triplet.h file is below:

#ifndef PYTHAGOREAN_TRIPLET_H
#define PYTHAGOREAN_TRIPLET_H

#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <math.h>

typedef struct {
    uint16_t a;
    uint16_t b;
    uint16_t c;
} triplet_t;

typedef struct {
    uint16_t count;
    triplet_t triplets[];
} triplets_t;

triplets_t *triplets_with_sum(uint16_t sum);
uint16_t gcd(uint16_t a, uint16_t b);
void swap(uint16_t *a, uint16_t *b);
void free_triplets(triplets_t *triplets);

#endiftype or paste code here

It could be obvious to you what silly mistake I have made.

7 
triplet_t *triple = malloc(sizeof(triplet_t) + sizeof(uint16_t) * 3);
triplets_t *out_triplets = malloc(sizeof(triplets_t) + sizeof(triplet_t));

(If I am reading this right) these both look wrong to me:

  • triplet represents a single triplet, but the space allocated for it is big enough to fit 3 additional uint16_ts. This extra space appears unused (and therefore unlikely to be the cause of the segfault).
  • out_triplets receives enough space to fit 2 triplet_ts, but what exactly is this space used for?

Also, you never resize out_triplets, even though for some perimeters there are many solutions – see for example the tests file.

8

Brilliant not resizing out_triplets is my error. I had remembered to do this on the first simple looping algorithm I tried but forgot to carry it across when I switch to the new algorithm to handle the larger values. I should remember to “talk out loud to my rubber duck” when working back over my code to try and spot what I have missed of done wrong! I just put that single realloc() line in without changing anything else and I received back from the online editor:

Sweet. Looks like you've solved the exercise!

I am still somewhat baffled as to why I did not get an error, warning or segfault from that omission locally.

Note there is a struct named triplet_t and triplets_t. In my code “triple” is a triplet_t and “out_triplets” is a triplets_t.

I am already familiar with the tests file thanks. It would be impossible I think to solve the exercises without being familiar with it.

I think my initial calloc() calls are correct. At least I am following advise from an earlier exercise I received from one of your colleagues on Exercism.

I think I am making some headway in getting to grips with using the Unity unit test framework locally as well.

Thank you for excellent support.

9

Now that I see the additional s I see the sense of allocating space for an additional triplet_t for out_triplets. Note however that out_triplets receives ‘too much’ space if there are in fact no triplets to be found.

I still do not see the use of the additional 6 bytes allocated for triple.

10

This could be a difference in the malloc libraries used. One memory allocator may be generous and pre-allocate larger blocks than you need while the other might be more strict. One might allocate just the space you need but put it in the heap where there happens to be spare room for overrun (reserved for something else, used or unused).

11

The problem with undefined behavior is that anything can happen (e.g. the often quoted “nasal demons” or “pregnant cats”). But you could try this:

When you use the CLI to download the exercise and compile/run the tests locally you can execute make memcheck. It builds the tests with the AddressSanitizer and you would get an error message like this:

==24107==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000138 at pc 0x5556f29a75e0 bp 0x7ffe91836340 sp 0x7ffe91836330                                              
WRITE of size 6 at 0x602000000138 thread T0                                                                                                                                            
    #0 0x5556f29a75df in triplets_with_sum pythagorean_triplet.c:49                                                                                                                    
    #1 0x5556f29a84ff in test_returns_all_matching_triplets test_pythagorean_triplet.c:96                                                                                              
    #2 0x5556f29a6e44 in UnityDefaultTestRun test-framework/unity.c:1837                                                                                                               
    #3 0x5556f29a939c in main test_pythagorean_triplet.c:151                                                                                                                           
    #4 0x7f95e1b6bd8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f)                                                                                                                       
    #5 0x7f95e1b6be3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f)                                                                                                   
    #6 0x5556f29a3384 in _start (/vagrant/exercism/c/pythagorean-triplet/memcheck.out+0x3384)                                                                                          
                                                                                                                                                                                       
0x602000000138 is located 0 bytes to the right of 8-byte region [0x602000000130,0x602000000138)                                                                                        
allocated by thread T0 here:                                                                                                                                                           
    #0 0x7f95e1f05867 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x5556f29a7133 in triplets_with_sum pythagorean_triplet.c:10                        
    #2 0x5556f29a84ff in test_returns_all_matching_triplets test_pythagorean_triplet.c:96  
    #3 0x5556f29a6e44 in UnityDefaultTestRun test-framework/unity.c:1837                   
    #4 0x5556f29a939c in main test_pythagorean_triplet.c:151                               
    #5 0x7f95e1b6bd8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f)                           
                                                                                           
SUMMARY: AddressSanitizer: heap-buffer-overflow pythagorean_triplet.c:49 in triplets_with_sum

...
12

And because it hasn’t been mentioned yet in this thread:

With the CLI you can submit incomplete or invalid solutions, request mentoring, and ask for clarifications, hints, or help.
Then you will get 1-to-1 help from a mentor on the C track, the mentor can download your solution, compile/run it on their machine to reproduce the issue.

13

I have not been using the CLI to download the exercise and compile/run the tests locally to date.

Now, I see that I probably should, at least in cases were I am struggling. You make an important point which I have not picked up on until now. I did have a quick skim through the “Learn more about solving exercises locally” section but no more. Maybe, because I have a really old Windows 7 laptop, with Cygwin installed, I tend to resist the temptation to download this and that without careful consideration.

Thank you all for replies.