[Community Puzzle] Fractal Carpet

Puzzles
1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

2

In case this bites anyone else…

The stub generator for Fractal Carpet reads int from the input. I needed to change this to long in C# to be able to read the last test, and it turns out that the final validator needs a ulong. Also, even with this change, I was failing the final validator because I was using Math.Pow() in my solution, and it returns a double. At the size of the numbers in use, double does not provide enough precision. I needed to change my code to call BigInteger.Pow() instead.

I’m providing this information just in case (like me) someone can’t figure out why all the tests pass, but the last validator fails.

  • danBhentschel
3 Likes
3

I’ve helped out a fellow on the chat yesterday who had the exact same problem in C or C++, so yes, I think it’s going to be useful.

IMHO using floating point pow() is the user’s own damn fault and good as is; but it is notable that the final validation case, though within constraints, is orders of magnitude bigger than the final test case, and indeed enough to overflow a double’s mantissa.

My easy recommendation for TPTB would be to just swap test and validation for the final case. Both overflow the naive approach anyway, so no need to keep the floating point resolution surprise hidden.

4

My solution does not use powers.

1 Like
5

I had problems with this puzzle too. In the description, X and Y are considered to be Long, i.e. less than 9*10^18. However, the generated code do not use Long (I program in Scala) but Int. Moreover, for the last test, number higher than Long are sometimes generated (which is supposed to be impossible). So, finally, I had to use BigInt just to be able to read data.

6

Yes, I have been sufficiently humbled. Thank you. :slight_smile:

As I have said before, this is the place to make such mistakes, and learn from it. I’d rather make an idiot of myself in solving a CG puzzle than in the workplace.

Good call. Looks like TPTB have taken your suggestion.

  • danBhentschel
7

FYI, the largest number in this puzzle is:

4 052 555 153 018 976 266

or if you multiply out 3^39:

4 052 555 153 018 976 267

This is less than half of 9*10^18:

9 000 000 000 000 000 000

So the problem statement is correct. Even so, yes, these are very big numbers.

  • danBhentschel
8

Sorry, my bad, I have miscounted the digits :frowning: Nevertheless, the generated code should use Long and not Int.

9

I agree.

  • danBhentschel
10

For JS programmers, if you can’t pass the last test

Summary

you can exploit the different symmetries of the carpet (and some tricks with string parsing) to get rid of the big number constraint.

EDIT: I have got excited too quickly, there… I managed to solved that last test in JS by reprogramming addition, substraction, mod3 (easy, this one) and division with decimal string representation, digit by digit. It took me a while (15min for the regular program, replacing Int by Long in C/C++, 3h30min to learn back string based division algorithm…).
A little reminder why you should study your constraints before choosing how you’ll implement your solution…

Be brave <3

2 Likes
11

For JS programmers: you just have to use BigInt for the numbers. No need to reimplement it in your own code (although it can be a good exercise :slight_smile: ). Mind that the boilerplate code will use parseInt for the piece coordinates, just change those to BigInt and go from there.

3 Likes
12

Now that’s problem solving )

1 Like
13

I can get the first 3 cases working in golang but can’t get the last case. They all seem to converge to a single value. Can anyone provide a hint regarding the last case.

14

Solved the last case by writing my own power function in golang which uses int64 instead of the float64. Hope this helps anyone who is facing the same issue

17

Thank you ! That was exactly what I was looking for :pray:

1 Like
18

Hello everybody!

I’ve managed to get all test cases successfully in Python, but when I submit my answer, I’m getting the “Magic Microscope Detail” wrong. I know it’s the most complicated case, but I thought I managed to solve it.

Anybody can help?

Thanks!

1 Like
19

Remember that tests and validators are different for most of the time for most puzzles.

In the “Magic Microscope Detail” validator, L = 39, and X1, Y1, X2 and Y2 are all 19-digit numbers.

20

Hi, I am solving this puzzle in Javascript and like many of us I am not able to pass the last case. The approach I am using is: first I am generating pattern based on the given level and then return the chunk of generated pattern based on given x1, y1, x2 and y2. For pattern generation, I am looping through the length of pattern that is supposed to be 3^L, so for the level 39 the length would be 4052555153018976000. Even a single loop is not efficient for this huge number. I think there’s something wrong with my approach. Instead of generating the pattern based on the level, I should use some other approach but I can’t think of any other approach. Any hint or help from anyone would be highly appreciated. :slight_smile:
Thank you

1 Like
21

You can write a procedure that, given the level and the (x, y) coordinates, computes whether the character at that coordinates is 0 or + without generating the whole pattern.

3 Likes
22

Oh, I didn’t know BigInt. For this puzzle, it’s too late, but big thanks for the future me in some other challenges where I would need it!

1 Like