Problem 353

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
User avatar
BostonBear
Posts: 17
Joined: Thu Apr 28, 2011 4:48 am
Location: Saugus, MA

Problem 353

Post by BostonBear »

I am a little confused about the new problem. This sphere has integer coordinates. Yet we are not given a specific size, so as far as I can tell , for a generic r, there are only 6 integer coordinates. (r,0,0), (0,r,0), (0,0,r) and its antipodals. Is there something I'm missing here? Does each trip to a station have to be a direct trip, or can you change directions before you get to the next station?

Edit, never mind, I figured out what I was not seeing right
Last edited by BostonBear on Sun Oct 09, 2011 5:36 am, edited 1 time in total.
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Euler Problem 353

Post by TripleM »

You are given a specific size - r is equal to 2^n - 1 for each value of n from 1 to 15.
cyrillic
Posts: 1
Joined: Wed Oct 12, 2011 11:25 am

Euler Problem 353

Post by cyrillic »

Could I check with someone the value of M(r) for n=15 I'm getting, to validate my code? Cheers.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Euler Problem 353

Post by thundre »

cyrillic wrote:Could I check with someone the value of M(r) for n=15 I'm getting, to validate my code? Cheers.
PM it to me and I'll tell you whether it matches mine.
Image
Arthelais
Posts: 3
Joined: Wed Oct 08, 2014 2:57 pm

Re: Problem 353

Post by Arthelais »

Could someone verify for me whether M(1000) is equal to 0.05174553024? I feel like I am facing a rounding error and I can't seem to figure it out.
MuthuVeerappanR
Posts: 495
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 353

Post by MuthuVeerappanR »

Is this problem prone to precision errors?? I tried a couple of methods and they all provide the same for value upto M(10). But somehow my answer is not getting accepted.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
User avatar
sjhillier
Administrator
Posts: 561
Joined: Sun Aug 17, 2014 4:59 pm
Location: Birmingham, UK
Contact:

Re: Problem 353

Post by sjhillier »

Well you certainly have to be precise, but no more so than many other problems. There are other possible error modes, but it would be wrong to say more.
MuthuVeerappanR
Posts: 495
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 353

Post by MuthuVeerappanR »

Thanks sjhillier. I solved it yesterday. Turns out one of my assumptions only fails for the k = 8 case.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
User avatar
sjhillier
Administrator
Posts: 561
Joined: Sun Aug 17, 2014 4:59 pm
Location: Birmingham, UK
Contact:

Re: Problem 353

Post by sjhillier »

MuthuVeerappanR wrote: Thu Jun 08, 2017 2:34 pm Thanks sjhillier. I solved it yesterday. Turns out one of my assumptions only fails for the k = 8 case.
I'm sure I made the same mistake too.
bleh0.5
Posts: 1
Joined: Tue Aug 14, 2018 5:54 pm

Re: Problem 353

Post by bleh0.5 »

Are we supposed to calculate every single integer set of coordinates or are the only coordinates going to be (0,r,r) and stuff like that
User avatar
RobertStanforth
Administrator
Posts: 1690
Joined: Mon Dec 30, 2013 11:25 pm

Re: Problem 353

Post by RobertStanforth »

bleh0.5 wrote: Tue Aug 14, 2018 5:57 pm Are we supposed to calculate every single integer set of coordinates or are the only coordinates going to be (0,r,r) and stuff like that
The admissible paths (from which you are asked to find the one with the lowest risk) are permitted to use any of the integer-coordinate points on the surface of $C$. The problem statement does not confine you to a special subset of them.
ChicoTobi
Posts: 1
Joined: Thu May 27, 2021 9:04 pm

Re: Problem 353

Post by ChicoTobi »

Uhm, so I hope i don't spoil anything... so if it's too much please feel free to delete...

So I started doing this problem, because I love those fancy geometry problems! And also I was thinking, that a lot of symmetry is going on here. After reproducing the solution for the small number example from the question (N=3, r=7), I tried scaling it up. And boy, was I wrong! Both the generation of the pythagorean tuples as well as the graph-matrix as well as the dijkstra algo only perform until N=11, N=12 within around a minute. But there's no way that I will reach N=15 within a minute.

I produced hashes for the smaller numbers. Can somebode check these plz? It's a simple md5 of the the utf-8 string in the form as in the problem "0.1784943998".

Hash for r= 1 : d310cb367d993fb6fb584b198a2fd72c
Hash for r= 3 : fca3319e19aa9137881ea13ea824edce
Hash for r= 7 : d0dfb92eb56f02b897654fe4652b2f1f
Hash for r= 15 : 5f9e89ed8d08fd895368256943196c5a
Hash for r= 31 : eb166b2e0288c93cccd7a4d47229b7a7
Hash for r= 63 : 0ba2dd95494dc35f356eb185dfcd5a9a
Hash for r= 127 : f7049ff1b5cb032b8c1fcee6acc1ffdc
Hash for r= 255 : 02aa0151cd3f7eb54469ab56dcf65f1f
Hash for r= 511 : d58bbfcfa5f91cd8b530109f45743000
Hash for r= 1023 : 6ccc1e655cdbf556ea1f9f63e152053b
Hash for r= 2047 : 846004309705e1a24389b67e2f298f7e

Then I would know if my implementation is wrong, or if it's only too slow/inefficient. I attached part of my shortest path for r=255.

Edit: Nevermind, I let it run, and it was correct in the end :D But still took like 30 minutes, sadly.
Attachments
Screenshot from 2021-05-27 22-11-20.png
Screenshot from 2021-05-27 22-11-20.png (45.38 KiB) Viewed 386 times
Post Reply