[Community Puzzle] Unit Fractions

Puzzles
#22

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
#23

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.

#24

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
#25

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.

#26

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.

#27

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.

#28

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
#29

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.

#30

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
#31

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.

#32

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
#33

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.

#34

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.

#35

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
#36

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

#37

Hello !
My code seems to be ok and passes all tests, but after submission, the second “validator” always gives an error message ??!!!?! I can’t find why !! Can anyone give me some help to understand the difference between tests and validators ? Thanks.

#38

Give you another sample. Can you get the same result?

1/102 = 1/10506 + 1/103
1/102 = 1/5304 + 1/104
1/102 = 1/3570 + 1/105
1/102 = 1/2703 + 1/106
1/102 = 1/1836 + 1/108
1/102 = 1/1258 + 1/111
1/102 = 1/969 + 1/114
1/102 = 1/714 + 1/119
1/102 = 1/680 + 1/120
1/102 = 1/408 + 1/136
1/102 = 1/391 + 1/138
1/102 = 1/306 + 1/153
1/102 = 1/255 + 1/170
1/102 = 1/204 + 1/204
1 Like
#39

Calling this problem “Easy” is outrageous
The description is totally incomplete
At least put a link to the math beneath it
Read the other “Easy” problems and tell me if you find it correctly marked as it, @java_coffee_cup

#40

The math is a little challenging; maybe more than most people could handle with just high school algebra. I think JCC intended that to be part of the fun. Outside of not giving away the math, the description is clear and complete and the actual coding is easy. There are multiple good solutions that take just a few lines and use only primitive types. The biggest frustration I ran into was getting Java to stop casting my long values to int.

Hint: It helps to think about the 1/n = 1/x + 1/y : {x >= y} equation in terms of limits.

#41

@ ToshiTuringMachine You did very well to relay this puzzle to a classic school of maths study. You need these references when you are writing an academic paper in research.

While this problem belongs to the spectrum of Diophantine equations, one does not need to know or apply any Diophantu maths theory or equation or any advanced maths to solve it.

Diophantus started his study 2000 years ago.

In terms of solving this problem, it is probably still a piece of cake for an average coder today equiped with modern technologies but without the Diophentus maths knowledge. On the contrary, Diophantus and his followers who know their school of study well but without knowing computer or programming will find it hard to manually doing all calculations.

Easy or hard depends on what year you are living in and what tools you are using.