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

41–50 of 105 posts

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

#41

Post by philiplu »

tocs3 wrote: post #36
philiplu wrote: post #24

Earlier quoted context omitted.

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…

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 find pretty much any problem with John Conway's influence fun to do.

As for a single problem, I'm fond of PE589, "Poohsticks Marathon". That was my 501st solution, two years after first attempting it (solved 5 years ago, yikes). I like it because it's a problem with a 95% difficulty rating, so very tough, but the development team slotted it in as an easy problem (problems normally get scheduled in batches of 6 with a cadence of medium/easy/medium/easy/medium/hard). Once I solved it, I agreed that it was relatively easy, in that it uses techniques introduced by early PE problems, but something about it makes using those techniques unexpectedly difficult.

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

#42

Post by coffeemug »

Twirrim wrote: post #19
tocs3 wrote: post #3

I have spent a little time with Project Euler. Is it very popular with those here at HN?

I don't know that I'd gauge anything by popularity with the HN crowd. It's also a diverse group. I'm closing in on a hundred problems solved, in a not very completion-ist fashion (I've got a whole bunch of skips and random choices of puzzles). Maths isn't my strongest suit, and I have no academic comp-sci background, so there's been a number of these I sort of brute force and then go read the answers in the thread; o…

https://oeis.org/ is an incredible website! Thanks for sharing.

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

#43

Post by archgoon »

Sohcahtoa82 wrote: post #21

During the solving of a problem on Project Euler, I learned that compilers are smarter than me. I don't remember the problem number or its title, but it involved starting from the top-left corner of a 2D grid and finding how many possible paths there are to get to the bottom-right corner while only moving either down or right. My naive solution was a brute-force depth-first recursive search. On my CPU at the time, it…

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.

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

#44

Post by byearthithatius »

munchler wrote: post #39
SatvikBeri wrote: post #32

Project Euler is a lot of fun if you like a dash of math in your programming. The problems generally won't apply to your job or even to interviews, so don't go in expecting that. My favorite is https://projecteuler.net/problem=113 , "Non-Bouncy Numbers." It takes some clever tricks to figure out but doesn't require any significant background knowledge, and the optimizations required to get it to run within 60 seconds…

More than a dash. I would describe Project Euler as math problems that you need a computer to solve.

Well said, that is always how I saw it as well. The sort of math problem solving we did for fun in school but all the problems require programmatic thinking and usually eventually an algorithm. I learned so much from doing Eulers. Even basic stuff I thought I would know like the best way to get GCD

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

#45

Post by gerdesj »

Sohcahtoa82 wrote: post #21

During the solving of a problem on Project Euler, I learned that compilers are smarter than me. I don't remember the problem number or its title, but it involved starting from the top-left corner of a 2D grid and finding how many possible paths there are to get to the bottom-right corner while only moving either down or right. My naive solution was a brute-force depth-first recursive search. On my CPU at the time, it…

We all have our skills and super powers and yours do not involve optimizing for time by switching from C to ASM. Fuck that! I bet you have super powers of some sort.

Compilers are not smarter than you - that's daft. The nutters that program the compilers and tweak and twiddle them, are better informed about how to deliver faster machine code for a given task.

One of your super powers is to know when to say: "fuck it, I'm trotting off and getting by with a five minutes runtime".

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

#49

Post by degoodm »

ChatGPT o1 seems to understand the problem correctly but doesn't get far: https://chatgpt.com/share/670dbe0e-087c-8000-9856-996c3fbaa9...

o1 thought for 105 seconds, cycling through many relevant-sounding status messages like "looking for patterns," before writing a collection of thematic but flawed thoughts. The "Calculation Steps" approach is incorrect, but correctly implemented by the code.

It flubs a basic calculation that it correctly implements in python: "10^16 mod (10^9 + 7) = 49" (it's actually 930000007)

but succeeds in a seemingly harder calculation: "the modular inverse of 12 modulo 10^9 + 7 is 83333334"

Finally, o1 claims the code prints "0" when it actually prints "982790507" (both wrong answers).

Note: input was copied from the html-only Project Euler url since the formulas in the human-optimized url are not copyable: https://projecteuler.net/minimal=912

Post reply on HN