Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Project Euler #912: Where are the Odds?

projecteuler.net

Post reply on HN
Print view View original

91–100 of 105 posts

Re: Project Euler #912: Where are the Odds?

#91

Post by xigoi »

sbrother wrote: post #65
archgoon wrote: post #43

Earlier quoted context omitted.

So fun fact, if you compile int sum(int n) { int sum = 0; for(int i = 0; i clang, with -O2, will turn this into the polynomial (n+1)*n//2. It can also do similar transformations for multiple loops. https://godbolt.org/z/so6neac33 So if you do a brute force solution which could have been reduced to a polyomial, clang has a shot of doing just that.

That is mind blowing, but it’s not immediately obvious to me that it’s equivalent for n > sqrt(INT_MAX). Is it? And if so, is the compiler somehow smart enough to know that?

If you assume two’s complement arithmetic, then this is always equivalent because you’re basically just calculating the answer in a modular ring.

Re: Project Euler #912: Where are the Odds?

#92

Post by legends2k »

110jawefopiwa wrote: post #64
joshlemer wrote: post #51

I've been thinking recently about how things like Project Euler, LeetCode, and to a bit less of an extent, Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms, that it makes them suboptimal as a tools for getting familiar with a new programming language. I know that that critique isn't new to anyone but it makes me think about how it would be cool if there were a code p…

> Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms I've done a fair amount of Advent of Code and I wouldn't say it's at all "focused" on this. The vast majority of the questions use hash tables and graph traversal as the full extent of their use of math/DS/algos. There's always one or two puzzles every year that require some particular math/CS insight but most of the…

Exercism.io does what you want? It has language tracks and each track has questions geared to seal your understanding of some language concept. It also has it gamified by building a community around it and folks comparing their solutions.

Re: Project Euler #912: Where are the Odds?

#93

Post by legends2k »

joshlemer wrote: post #51

I've been thinking recently about how things like Project Euler, LeetCode, and to a bit less of an extent, Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms, that it makes them suboptimal as a tools for getting familiar with a new programming language. I know that that critique isn't new to anyone but it makes me think about how it would be cool if there were a code p…

Exercism.io does what you want? It has language tracks and each track has questions geared to seal your understanding of some language concept. It also has it gamified by building a community around it and folks comparing their solutions.

Re: Project Euler #912: Where are the Odds?

#94

Post by joshlemer »

legends2k wrote: post #93
joshlemer wrote: post #51

I've been thinking recently about how things like Project Euler, LeetCode, and to a bit less of an extent, Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms, that it makes them suboptimal as a tools for getting familiar with a new programming language. I know that that critique isn't new to anyone but it makes me think about how it would be cool if there were a code p…

Exercism.io does what you want? It has language tracks and each track has questions geared to seal your understanding of some language concept. It also has it gamified by building a community around it and folks comparing their solutions.

Thanks, I'll take a look!

Re: Project Euler #912: Where are the Odds?

#95

Post by philiplu »

xigoi wrote: post #90
fallingknife wrote: post #30

Earlier quoted context omitted.

Am I missing something here or would that be as simple as 2N nCr N for an NxN grid?

You’re not missing anything. This is an easy problem aimed at people who are not familiar with basic combinatorics.

Something this illustrates, though - once you solve a problem, read the forum thread (the link will be at the bottom of the problem page when solved).

I learned so much poring over the solutions of earlier solvers. Without that knowledge, there's no way I could have gotten lots of later problems.

Sure, problem #15 is very early and I happened to know the answer right off, back the first day I started solving PE problems. But even so, there are some gems in the posts from other solvers.

Re: Project Euler #912: Where are the Odds?

#96

Post by philiplu »

philiplu wrote: post #24
procparam wrote: post #11

Earlier quoted context omitted.

Wow. The idea of getting to 100% on PE is almost incomprehensible to me. I've solved basically none outside the first couple pages. What was your strategy like? How much math background do you have?

I've got a bachelor's in math, but that's 40+ years ago. I had intended to go on for a PhD in math, but fell into computers instead - programming was easier and way more lucrative, even in the early 80s. Once I was retired and found my way to Project Euler, it became an obsession, tickling that desire to go deeper into math that I had in my college days. I attacked roughly the first 250 problems in order. The early p…

One other thing - can't believe I forgot to mention this: once you solve a problem, read the solvers' thread in the forum! I learned so much by doing that, which fed into success on later problems. The link will be at the bottom of the problem page once you've solved it.

There are some much later problems where some obscure technique gets mentioned, even though the problem is doable without that technique. But then later on, there are other problems where that technique is practically required. I can think of multiple 100% difficulty problems which were actually much easier than that for me, because I had already seen and tried out the techniques that enable a fast solution.

And sorry, not going to mention any of those techniques. A lot of the fun I have in solving PE problems is that incremental increase in knowledge as time goes on.

Re: Project Euler #912: Where are the Odds?

#97

Post by lynguist »

Chatgpt can write a solution for this problem if we go up to 10^10. 10^16 is too hard!

I don’t understand this problem (I didn’t tackle it myself) but wanted to see how quickly chatgpt could solve it and how far along it would go.

First it made a naive solution that would work until 10^6. Then we used that output to verify improved versions.

And we managed to improve it until 10^10 only. (Staying within a minute timeout.)

It did a DP approach (it suggested itself). I suggested to try numba and numpy. And with that it managed until 10^10. I think it’s still brute forcing it and one might leverage much better techniques in order to reach 10^16.

Re: Project Euler #912: Where are the Odds?

#98

Post by fallingknife »

xigoi wrote: post #90
fallingknife wrote: post #30

Earlier quoted context omitted.

Am I missing something here or would that be as simple as 2N nCr N for an NxN grid?

You’re not missing anything. This is an easy problem aimed at people who are not familiar with basic combinatorics.

On second look I think it can be further generalized to N+M nCr M for all grids NxM where N >= M since the number of ways should depend on combinations of the smaller number.

Re: Project Euler #912: Where are the Odds?

#99

Post by nonameiguess »

xigoi wrote: post #90
fallingknife wrote: post #30

Earlier quoted context omitted.

Am I missing something here or would that be as simple as 2N nCr N for an NxN grid?

You’re not missing anything. This is an easy problem aimed at people who are not familiar with basic combinatorics.

I'm a bit disappointed I didn't see this quicker back when I did this problem like 15 years ago or whatever it is now. My solution was to use matrix exponentiation on the adjacency matrix of the path graph, which is a heck of a lot better than brute force enumeration of all paths, but still roughly cubic rather than linear like computing a bunch of factorials. Even as a math major, I'd done a lot more linear algebra than combinatorics.

Re: Project Euler #912: Where are the Odds?

#100

Post by Sohcahtoa82 »

wging wrote: post #38
Sohcahtoa82 wrote: post #25

Earlier quoted context omitted.

Yup! That was it!

If you want a few similar problems, in ascending order of difficulty, try #81 through #83: https://projecteuler.net/problem=81 https://projecteuler.net/problem=82 https://projecteuler.net/problem=83

Couldn't all three of those be solved using the A* path-finding algorithm?
Post reply on HN