This month’s Exercise both terrified and enticed me. Yes, I code these solutions myself after I think up the challenges. No cheating here! This particular puzzle was more fun than I imagined, but also required a lot of mental work.

The first thing I did was to look up the three steps to simplify a fraction: Discover the common factors, obtain the greatest common denominator (GCD), and then divide the numerator and denominator by the GCD. This approach required a lot of code.

Here is the main() function from my first solution, which you can find on Github:

int main()
{
    const int size = 7;
    int numerator[size] = { 28, 13, 14, 1, 9, 276, 4 };
    int denominator[size] = { 42, 52, 91, 50, 15, 23, 100 };
    int numerator_factors[BUFFER_LIMIT];
    int denominator_factors[BUFFER_LIMIT];
    int x,m;

    for( x=0; x<size; x++ )
    {
        /* output the original fraction */
        printf("%d/%d ",numerator[x],denominator[x]);

        /* obtain factors for the numerator and denominator */
        factors(numerator_factors,numerator[x]);
        factors(denominator_factors,denominator[x]);

        /* obtain the maximum common factor */
        m = maxfactor(numerator_factors,denominator_factors);

        if( m )
        {
            /* reduce the fraction */
            printf("is simplified to %d/%d\n",
                    numerator[x]/m,
                    denominator[x]/m
                  );
        }
        else
        {
            /* the fraction cannot be reduced */
            puts("cannot be simplified");
        }
    }

    return(0);
}

The defined constant BUFFER_LIMIT equals 100, which is a guess of how many factors are possible for a given value. This is the kludgiest part of this solution; a number could have more factors than 100, but I didn’t want to manipulate a dynamic array to store them.

A for loop processes each of the fractions, which are output as was done in the skeleton code. Within the loop, the factors() function obtains the factors for numerator[x] and denominator[x]. The results are stored in the numerator_factors[] and denominator_factors[] arrays. See this Lesson for more details on finding factors.

The maxfactor() (heh) function returns the maximum shared factor value between the two arrays, numerator_factors[] and denominator_factors[]. I use a bubble sort to compare the values and find the maximum, which is returned in variable m.

If variable m isn’t zero, its value divides both numerator[x] and denominator[x] to output the simplified fraction. Otherwise, the fraction cannot be simplified.

Here’s a sample run:

28/42 is simplified to 2/3
13/52 is simplified to 1/4
14/91 is simplified to 2/13
1/50 cannot be simplified
9/15 is simplified to 3/5
276/23 is simplified to 12/1
4/100 is simplified to 1/25

My second solution uses Euclid’s algorithm to reduce the numerator and denominator values by their differences. The algorithm is quite clever, and I need not repeat the details or fancy graphics from the Wikipedia page. Here is the entirety of my second solution:

2022_03-Exercise-b.c

#include <stdio.h>
#include <stdlib.h>

int main()
{
    const int size = 7;
    int numerator[size] = { 28, 13, 14, 1, 9, 276, 4 };
    int denominator[size] = { 42, 52, 91, 50, 15, 23, 100 };
    int x,diff,larger,smaller;

    for( x=0; x<size; x++ )
    {
        /* output the original fraction */
        printf("%d/%d ",numerator[x],denominator[x]);

        /* calculate differences between the larger and smaller values */
        larger = numerator[x]>denominator[x] ? numerator[x] : denominator[x];
        smaller = numerator[x]<denominator[x] ? numerator[x] : denominator[x];
        diff = larger-smaller;
        /* keep calculating until the common denominator is found */
        while( diff!=larger )
        {
            larger = smaller>diff ? smaller : diff;
            smaller = smaller==larger ? diff : smaller;
            diff = larger-smaller;
        }

        /* if the difference is more than 1, the fraction can be reduced */
        if( diff>1 )
        {
            printf("is simplified to %d/%d\n",
                    numerator[x]/diff,
                    denominator[x]/diff
                  );
        }
        else
        {
            /* the fraction cannot be reduced */
            puts("cannot be simplified");
        }
    }

    return(0);
}

Not being Euclid, I would have never thought of this approach. Yet it works beautifully: The algorithm starts at Lines 17 through 19, then repeats in a while loop until the GCD is found. The output is the same, but I admire this code far better than my first, plodding solution.

Whether you tried one solution or both, I hope you met with success. And I further hope I never have to type the word denominator so many times again in my life.