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

101–105 of 105 posts

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

#101

Post by tocs3 »

philiplu wrote: post #41
tocs3 wrote: post #36

Earlier quoted context omitted.

Do you have a favorite?

As a class of problems, I'd say the combinatorial game theory ones are my favorites. There are a lot of impartial game theory problems - look for problems mentioning Nim or stone games. They build on each other nicely, from the mid 300s on. The site has been getting into partisan game theory problems in the past year, which finally got me to buy "Winning Ways For Your Mathematical Plays", vol 1, and "Lessons In Play"…

I have been working on PE problems for most of 10 years. One thing I would sort of like to do is make a library (mostly I have been using python) for some of the more common functions. Do you have anything like that?

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

#102

Post by kevinventullo »

lynguist wrote: post #97

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 time…

It hadn’t occurred to me that PE is a pretty good test for ChatGPT or SOTA LLM’s in general. Even if explicit solutions for earlier problems do appear somewhere on the web, it’s probably a fairly safe bet that the latest version of ChatGPT did not include the latest Project Euler problem in its training data.

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

#103

Post by philiplu »

tocs3 wrote: post #101
philiplu wrote: post #41

Earlier quoted context omitted.

As a class of problems, I'd say the combinatorial game theory ones are my favorites. There are a lot of impartial game theory problems - look for problems mentioning Nim or stone games. They build on each other nicely, from the mid 300s on. The site has been getting into partisan game theory problems in the past year, which finally got me to buy "Winning Ways For Your Mathematical Plays", vol 1, and "Lessons In Play"…

I have been working on PE problems for most of 10 years. One thing I would sort of like to do is make a library (mostly I have been using python) for some of the more common functions. Do you have anything like that?

I do, but there's nothing too obscure in it. Efficient prime number sieve, prime factorization using trial division, generating list of divisors from the prime factorization, modular inverse via Euclidean algorithm, Chinese Remainder Theorem.

I also have some stand-alone modules, one to solve generalized Pell equations, another to find a polynomial given a sequence via the differences (e.g. 2, 5, 10, 17, first differences 3, 5, 7, second 2, 2 is enough to find n^2+1). There's another to find the closed form for a sequence as a linear recurrence.

Some solvers have much more extensive libraries, but I tend to grab bits of code from old solutions to reuse on the fly.

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

#104

Post by _xiaz »

joshlemer wrote: post #86
_xiaz wrote: post #73

Earlier quoted context omitted.

Most of these wouldn't qualify as "puzzles", would they? I find it nice to learn new languages via data structure puzzles, because to me the data structures of a language feel like the grammar and once I have that down everything else falls into place

I disagree. Yes, you have to learn how to work with the basic data structures of a language, but 90% of programming, for most people, is not that. It's IO, error handling, db querying, logging, input parsing, parameterization, business logic, preserving backwards compatibility, persistence, state management, testing, mocking, benchmarking, build design (for lack of better term -- futzing around with Make/Gradle/Npm,…

Imo DS/Algs to an extent are a good prerequisite. Once you know them in one language that knowledge is portable enough to get you up-to-speed in $lang. Then, and no earlier will I start worrying about doing real things in my programs and the "idiosyncracies"

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

#105

Post by wging »

Sohcahtoa82 wrote: post #100
wging wrote: post #38

Earlier quoted context omitted.

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?

Sshhh...
Post reply on HN