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

31–40 of 105 posts

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

#31

Post by mdp2021 »

dotancohen wrote: post #28
guessmyname wrote: post #23

Earlier quoted context omitted.

Lattice Paths — https://projecteuler.net/problem=15 > Starting in the top left corner of a 2x2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. ─────────┐ ────┐ ────┐ ┌───┬───┐│ ┌───│───┐ ┌───│───┐ │ │ ││ │ │ │ │ │ │ ├───┼───┤│ ├───└────┐ ├───│───┤ │ │ ││ │ │ ││ │ │ │ └───┴───┘│ └───┴───┘│ └───│───┘ ▼ ▼ └────▶ │┌───┬───┐ │┌───┬───┐ │┌───┬───┐ ││ │ │ ││ │…

> How many such routes are there through a 20x20 grid? Is it 21! ?

No. It's 20!/(10!x10!)

You have 20 slots to be filled with 10 items vs other 10 items.

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

#32

Post by SatvikBeri »

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 (at least for my approach) all felt reasonable.

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

#33

Post by ThrowawayTestr »

guessmyname wrote: post #17

Why problem 912 specifically? On a side note, I remember when the website got hacked [1][2]. Many people, including myself, migrated to other platforms, but Project Euler problems always remained math-focused compared to the myriad of other websites like LeetCode and HackerRank, among others, listing programming-focused problems, which eventually popularized the use in modern tech interviews. [1] https://news.ycombin…

It's the most recent

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

#34

Post by noapologies »

mdp2021 wrote: post #31
dotancohen wrote: post #28

Earlier quoted context omitted.

> How many such routes are there through a 20x20 grid? Is it 21! ?

No. It's 20!/(10!x10!) You have 20 slots to be filled with 10 items vs other 10 items.

Close, it's 40!/(20!*20!)

20 Rs, 20 Ds in a 20x20 grid.

Example pattern: RRDDDR...D (40 letters)

Basically the number of permutations, with repetition, of 20 Rs and 20 Ds.

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

#35

Post by tocs3 »

glouwbug wrote: post #10
n4r9 wrote: post #6

Earlier quoted context omitted.

To be honest, I don't see people talking about it that much. But I'm certain that it would appeal to a good chunk of the people here.

But isn’t it mathematical computing? I feel like leetcode DSA is closer to your average HN user

Has here been any work done to find out about the average HN user? It seems like it would be a hard thing to do but it might be interesting to see. I do not even know what sort of metrics would be useful to measure.

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

#36

Post by tocs3 »

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…

Do you have a favorite?

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

#37

Post by mdp2021 »

noapologies wrote: post #34
mdp2021 wrote: post #31

Earlier quoted context omitted.

No. It's 20!/(10!x10!) You have 20 slots to be filled with 10 items vs other 10 items.

Close, it's 40!/(20!*20!) 20 Rs, 20 Ds in a 20x20 grid. Example pattern: RRDDDR...D (40 letters) Basically the number of permutations, with repetition, of 20 Rs and 20 Ds.

Oops! Thanks, just distraction... It's that first I wanted to see the general solution to those kind of problems (and I gave the solution for a wrong one in the class), then I wanted to verify the C implementation of the solution with POPCNT like the OP seems to have done (I am writing the code)...

Edit: ...and yes, it seems that brute-forcing (counting to one trillion) takes more time than I expected.

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

#38

Post by wging »

Sohcahtoa82 wrote: post #25
johnsonjo wrote: post #22

Earlier quoted context omitted.

Sounds like problem 15 [1]? [1]: https://projecteuler.net/problem=15

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

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

#39

Post by munchler »

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.

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

#40

Post by [deleted] »

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.

[deleted]
Post reply on HN