[Community Puzzle] Unit Fractions

As people are asking for tips to solve this puzzle, I could provide pointers to kick-start but not too much to reveal the answer.

Tips
  1. Change subject of the equation. Make x to become the subject.
    In algebra we represent it as x = f(n, y). But this representation is useless to you until you finish change subject.

What is change subject?
https://www.google.com/search?q=math+equation+change+subject

  1. Do you find that the value of y is always within a specific range, from [start] to [end]?
    Define [start] and [end] for y.

  2. Write a for-loop, for y = [start] to [end], test whether x is an integer under the given n and y

  3. Within the for-loop, if “x is integer” is TRUE, calculate value of x, then output one line of answer.

Note: Using the test case examples, you may have to test through 100,000 different values of y.
Your testing method has to be efficient to run at least 100k times in a flash.

How can it be so fast like that?
The test result is either TRUE or FALSE only. You do not need to know the true value of x in the test.
Calculate the exact value of x only after confirming x is an integer.

The above is just one possible approach. It does not rule out other algorithms that may run even faster.

Enjoy coding!

1 Like

I try to solve this in Haskell (which I don’t speak… but hey that’s the challenge :slight_smile: )
I use a recursive function instead of loop, something like this:

loop :: Int -> Int -> IO ()
loop y n
    | _is-end-of-loop-expression_ = ()
    | _is-valid-solution-expression_ = do
        let x = _expression_
        putStrLn $ "1/" ++ n ++ "= 1/" ++ x ++ "+ 1/" ++ y;
        (loop (y + 1) n)
    | otherwise = loop (y + 1) n

I get an error message ‘couldn’t match expected type IO () with actual type ()’ .
It seems to me that the problem that I generate output with putStrLn only in the second match, but not in the first.
I couldn’t fix my code with ‘try and error’ nor found relevant Haskell article.
Haskell coders, please help! Thanks.

You declared your function as returning IO (), but its first clause (end of loop expression) has type (). Hence the type mismatch error.

You can lift a term of type () (or, really, any type) to the IO monad (or, really, any monad) using pure or return.

1 Like

Thanks for the help, this solved the issue!
PS: the code excerpt I posted also missed some ‘show’ functions in the putStrLn and the ; was error but these were easier to find out.

This was a really good puzzle. Seemingly harder at first glance but with a suprisingly easy solution once you start to analyze the hand calculated output. There are several ways that you could go down a rabbit hole on this one.

Good job.

Hi everybody,
Did anybody solve this using C language ?
I can’t do it because of the variable storing limitations.
“integers” in C cannot store a value exceeding a limit.
This means that I always failed the two last tests because the numbers are too big.
So, if anybody found a solution to this, I’d love if he can share it with my in PM.

PS: I passed all the tests with the same algorithm using Python.
Have a good week-end.

C is more flexible than many other languages in terms of data type choices.

Besides the usual “int”, have you ever heard of “long int”, “unsigned long int”, “long long int” or even “unsigned long long int” ?

If not, this puzzle is a chance for you to try them out.

1 Like

Thanks for your quick answer. Unfortunately, I tried them all.
I used an unsigned long long int (which is supposed to be 64 bit) and the two last cases don’t work.

Then, I checked the version of the C compiler Codingame uses. And, to my surprise, they use one of the latest (most recent) compilers!!!
This means I could use uint64_t types as integers.
They don’t work either.

For instance for the before last case if you do:
unsigned long long int result = 71339 * 71340
Then fprintf(stderr, “result = %llu\n”, result)
The displayed result is absolutely false (1632927230790790372) .
On my calculator, the result is: 5089324260

I really need someone who actually tried using C and succeeded.
Unfortunately, I cannot see any C solutions because I didn’t get 100% using C language but Python instead.

Try copy and paste this code to CG’s online IDE (choose C), and test run

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int main()
{
    long x = 71339L * 71340L;
	printf("%ld\n", x);
    return 0;
}

What output do you see?

1 Like

It works. of course because of the “L” suffix on the numbers.
On the other side, I was able to solve this using C language at last.
I made a mistake with the scanf at the beginning of the auto-generated program.
The default one is using “%d” which is for simple int.
If I choose unsigned long long int, then, that could not work.
Thanks again for your help!
It’s very appreciated.

Seen your note so that I reviewed the statement and the stub. They are still correct because all input numbers are within the range of normal “int”. In the middle of calculation it is programmers’ responsibility to promote the input data type into other suitable data types as needed. You already know that writing in python there is no need for this promotion. The puzzle auto-gen stub is responsible for getting correct inputs but should not too much pre-define how to use the inputs.
Congrets you finally succeeded in solving it in C.

1 Like

You are definetely right. I shouldn’t have changed the way the autogen program handles the input.
I changed back and made it worked again. That was a better coddE.
Thanks again for your help!
Have a safe end of week-end.

I think i have the right formula for finding y. but the rounding of the numbers is too precise for me. y isn’t an integer it’s 15.99999999999999 (for instance). when i use round(y, 10) it’s either too precise or too crude it seems.

Your formula may be perfect but float-point calculation by computer is notorious to be inaccurate. It gives surprise more often than you expect. This puzzle can be solved by using no float-point variables in the whole processing.

1 Like

Thanks! That was the pointer i needed. finally got it :smiley: