News for hackers. Stuff that matters.
Re:Project Euler by Sohcahtoa82 on Monday October 14, 2024 @07:20PM (#41843245)
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 by guessmyname on Monday October 14, 2024 @07:28PM (#41843301)
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 by dotancohen on Monday October 14, 2024 @08:02PM (#41843557)
> How many such routes are there through a 20x20 grid?

Is it 21! ?

Re:Project Euler by mdp2021 on Monday October 14, 2024 @08:09PM (#41843596)
No. It's 20!/(10!x10!)

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

Re:Project Euler by noapologies on Monday October 14, 2024 @08:20PM (#41843664)
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 by mdp2021 on Monday October 14, 2024 @08:26PM (#41843698)
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 by dotancohen on Tuesday October 15, 2024 @04:14AM (#41846175)
Now I see it. Twenty items (R operations) in 40 slots: 40!/(20!) and the order of the items does not matter, so again divide by 20!. The remaining slots are D operations.

The answer actually came to me in the shower this morning.

Re:Project Euler by Jtsummers on Monday October 14, 2024 @08:08PM (#41843587)
Nope, and only off by a few orders of magnitude.
Re:Project Euler by dotancohen on Tuesday October 15, 2024 @04:16AM (#41846184)
If it is any comfort, my answer produced a non-negative integer - just like the true answer ))
Re:Project Euler by fallingknife on Monday October 14, 2024 @08:08PM (#41843591)
Am I missing something here or would that be as simple as 2N nCr N for an NxN grid?
Re:Project Euler by xigoi on Tuesday October 15, 2024 @12:45PM (#41850457)
You’re not missing anything. This is an easy problem aimed at people who are not familiar with basic combinatorics.
Re:Project Euler by philiplu on Tuesday October 15, 2024 @05:55PM (#41853517)
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 by fallingknife on Tuesday October 15, 2024 @07:09PM (#41854050)
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 by nonameiguess on Tuesday October 15, 2024 @07:38PM (#41854220)
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 by Sohcahtoa82 on Monday October 14, 2024 @07:48PM (#41843464)
Yup! That was it!

Good job on the ASCII art, btw.

Re:Project Euler by FredPret on Monday October 14, 2024 @10:17PM (#41844288)
Did you just whip out that amazing ASCII art or do you use a tool?
Re:Project Euler by guessmyname on Monday October 14, 2024 @11:14PM (#41844563)
ASCII art by hand (⌐■_■) it only took me 5 minutes or so … That said, I think someone could have done it faster with a tool like Monodraw (https://monodraw.helftone.com/) or something similar.
Re:Project Euler by johnsonjo on Monday October 14, 2024 @07:27PM (#41843296)
Sounds like problem 15 [1]?

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

Re:Project Euler by Sohcahtoa82 on Monday October 14, 2024 @07:47PM (#41843453)
Yup! That was it!
Re:Project Euler by wging on Monday October 14, 2024 @08:27PM (#41843699)
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 by Sohcahtoa82 on Tuesday October 15, 2024 @07:45PM (#41854247)
Couldn't all three of those be solved using the A* path-finding algorithm?
Re:Project Euler by wging on Wednesday October 16, 2024 @01:10PM (#41861400)
Sshhh...
Re:Project Euler by archgoon on Monday October 14, 2024 @09:01PM (#41843878)
So fun fact, if you compile

  int sum(int n) {
      int sum = 0;
      for(int i = 0; i < n; i++) {
          sum +=i;
      }
      return sum;
  }
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 by j2kun on Monday October 14, 2024 @10:19PM (#41844299)
I believe the term for this is scalar evolution.
Re:Project Euler by archgoon on Monday October 14, 2024 @10:23PM (#41844325)
Yep! That is it alright.

Here's a talk from an llvm conference with the details.

https://www.youtube.com/watch?v=AmjliNp0_00

Re:Project Euler by sbrother on Tuesday October 15, 2024 @12:41AM (#41845005)
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?
Re:Project Euler by marin049 on Tuesday October 15, 2024 @01:00AM (#41845099)
Integer overflow is actually undefined behaviour thus the compiler is free to assume it doesn't happen.
Re:Project Euler by xigoi on Tuesday October 15, 2024 @12:47PM (#41850481)
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 by gerdesj on Monday October 14, 2024 @09:25PM (#41844013)
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".