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

21–30 of 105 posts

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

#21

Post by Sohcahtoa82 »

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 took about 3 minutes to solve. I thought, the logic of this is incredibly simple, why not do it in assembly?

My assembly solution took 5 minutes.

I decompiled the compiled C code to see what it had done, but I couldn't understand it. My assembly knowledge was too basic.

Thinking on it now, I wonder if a modern compiler would solve the entire problem at compile-time and just hard-code the answer to be output at runtime.

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

#22

Post by johnsonjo »

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…

Sounds like problem 15 [1]?

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

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

#23

Post by guessmyname »

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…

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?

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

#24

Post by philiplu »

procparam wrote: post #11
philiplu wrote: post #9

Earlier quoted context omitted.

It’s my game plan for keeping my brain active in retirement. Been heavily involved for the past 7 years. Been at the 100% solved level since summer 2023, though I’m back to one away the past couple weeks - PE910 is _hard_

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 problems build on each other to introduce new topics. I also got good at figuring out the right search term to find some random paper in number theory, combinatorics, probability, whatever.

Later problems introduced new, more niche areas, like chromatic polynomials and impartial & partisan game theory. But by then, I found it much easier to figure out what part of math a problem was based on and how to find relevant literature.

It helps to be really really stubborn, and to have the patience to let a problem stew in my brain, sometimes for weeks at a time. That seems to help lead to that Eureka moment.

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

#25

Post by Sohcahtoa82 »

johnsonjo wrote: post #22
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…

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

Yup! That was it!

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

#26

Post by Sohcahtoa82 »

guessmyname wrote: post #23
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…

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. ─────────┐ ────┐ ────┐ ┌───┬───┐│ ┌───│───┐ ┌───│───┐ │ │ ││ │ │ │ │ │ │ ├───┼───┤│ ├───└────┐ ├───│───┤ │ │ ││ │ │ ││ │ │ │ └───┴───┘│ └───┴───┘│ └───│───┘ ▼ ▼ └────▶ │┌───┬───┐ │┌───┬───┐ │┌───┬───┐ ││ │ │ ││ │…

Yup! That was it!

Good job on the ASCII art, btw.

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

#27

Post by [deleted] »

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…

[deleted]

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

#28

Post by dotancohen »

guessmyname wrote: post #23
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…

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! ?

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

#29

Post by Jtsummers »

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! ?

Nope, and only off by a few orders of magnitude.

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

#30

Post by fallingknife »

guessmyname wrote: post #23
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…

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. ─────────┐ ────┐ ────┐ ┌───┬───┐│ ┌───│───┐ ┌───│───┐ │ │ ││ │ │ │ │ │ │ ├───┼───┤│ ├───└────┐ ├───│───┤ │ │ ││ │ │ ││ │ │ │ └───┴───┘│ └───┴───┘│ └───│───┘ ▼ ▼ └────▶ │┌───┬───┐ │┌───┬───┐ │┌───┬───┐ ││ │ │ ││ │…

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