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

61–70 of 105 posts

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

#61

Post by joshlemer »

hoten wrote: post #55
joshlemer wrote: post #51

I've been thinking recently about how things like Project Euler, LeetCode, and to a bit less of an extent, Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms, that it makes them suboptimal as a tools for getting familiar with a new programming language. I know that that critique isn't new to anyone but it makes me think about how it would be cool if there were a code p…

to be fair, PE is not designed or meant for helping people learn a language. that isn't the project's intent. people do like to say they use PE for learning new languages, but I doubt that is a useful exercise beyond maybe the first dozen problems or so. And even then, if the solution isn't obvious to you, you're doing two things at once - learning a language and solving a math puzzle. I don't see why people would si…

Oh yeah totally, it's not a criticism of PE, that's not what it's meant for. People just use PE and LC and AoC because that's the closest thing, but I think there is space in the market for a product I describe that really drills down on getting you familiar with the common tasks and stdlib of various languages.

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

#62

Post by cjohnson318 »

joshlemer wrote: post #51

I've been thinking recently about how things like Project Euler, LeetCode, and to a bit less of an extent, Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms, that it makes them suboptimal as a tools for getting familiar with a new programming language. I know that that critique isn't new to anyone but it makes me think about how it would be cool if there were a code p…

I really, really like this list. I've been wondering for the last year what the "optimal" problem is to learn at least the syntax of a language. After learning to run something, how to print to the console, I like using heapsort to start learning syntax of a new language, then reading/writing to a file, then building a small TodoList server.

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

#63

Post by CSMastermind »

joshlemer wrote: post #51

I've been thinking recently about how things like Project Euler, LeetCode, and to a bit less of an extent, Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms, that it makes them suboptimal as a tools for getting familiar with a new programming language. I know that that critique isn't new to anyone but it makes me think about how it would be cool if there were a code p…

The best recommendation I have for anyone trying to learn a new programming language is to try and program a board game.

There will be clear rules (business logic), UI, etc.

It's a confined enough problem that you can implement it without too much effort but deep enough that you can get a feel for how that programming language, framework, whatever works.

Plus there's a near endless set to choose from and it's easily scalable to the level of complexity you want. If it works add AI players, network play, etc.

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

#64

Post by 110jawefopiwa »

joshlemer wrote: post #51

I've been thinking recently about how things like Project Euler, LeetCode, and to a bit less of an extent, Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms, that it makes them suboptimal as a tools for getting familiar with a new programming language. I know that that critique isn't new to anyone but it makes me think about how it would be cool if there were a code p…

> Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms

I've done a fair amount of Advent of Code and I wouldn't say it's at all "focused" on this. The vast majority of the questions use hash tables and graph traversal as the full extent of their use of math/DS/algos.

There's always one or two puzzles every year that require some particular math/CS insight but most of them just need you to know BFS and/or how to write a parser.

Your examples are also not bad, but they seem to be primarily concerned with "getting familiar with a new programming language" in the context of writing a web server, which is one of the parts of programming I try to stay away from. Most of your examples require less familiarity with the language's features and more with libraries you might use, which is less interesting to me personally (then again, I'm a PL fan and I write compilers for a living).

Meanwhile, I like AoC because I've used language features to take the fairly straightforward potential implementations and write them more elegantly in the language I choose. e.g. I use Monads in Haskell, or use Rust's easy threading to parallelize solutions, etc.

For me, learning a new programming language is largely uninteresting unless it changes the fundamental "shape" I think in, rather than what the exact names of the libraries I use change to. e.g. I already know Java so I'm not really going to bother "learning" C#. I already know Python so I don't really bother diving deep into Ruby, etc. However, I learn Haskell, Rust, Forth, Erlang, Scheme, etc.

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

#65

Post by sbrother »

archgoon wrote: post #43
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.

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 #912: Where are the Odds?

#66

Post by marin049 »

sbrother wrote: post #65
archgoon wrote: post #43

Earlier quoted context omitted.

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.

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?

Integer overflow is actually undefined behaviour thus the compiler is free to assume it doesn't happen.

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

#67

Post by pncnmnp »

CSMastermind wrote: post #63
joshlemer wrote: post #51

I've been thinking recently about how things like Project Euler, LeetCode, and to a bit less of an extent, Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms, that it makes them suboptimal as a tools for getting familiar with a new programming language. I know that that critique isn't new to anyone but it makes me think about how it would be cool if there were a code p…

The best recommendation I have for anyone trying to learn a new programming language is to try and program a board game. There will be clear rules (business logic), UI, etc. It's a confined enough problem that you can implement it without too much effort but deep enough that you can get a feel for how that programming language, framework, whatever works. Plus there's a near endless set to choose from and it's easily…

I think we are a bit alike in our views, but I have a slightly different take on it. I consider coding something like a Chip-8 emulator to be more fun and optimal. It gives a holistic view of the language - you get to work with simple graphics, sound effects, and gain a feel for memory operations and data structures, as well as control structures like conditionals, looping, and exception handling. If that’s not all - for beginners, it provides an introduction to virtualizing CPUs with registers, stacks, opcode handling, memory units, arithmetic/bitwise operations, and more. You’ll even learn a bit about concurrency and synchronization, and by extension, threading. Also, performance optimization.

I suppose a decent game project could achieve these things too, but the real fun of Chip-8 is in throwing different ROMs at it and debugging the issues until it’s perfect enough to play all your favorite games!

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

#68

Post by jiggawatts »

joshlemer wrote: post #51

I've been thinking recently about how things like Project Euler, LeetCode, and to a bit less of an extent, Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms, that it makes them suboptimal as a tools for getting familiar with a new programming language. I know that that critique isn't new to anyone but it makes me think about how it would be cool if there were a code p…

Something I'd love to see is "AoC hard mode": the exact same problems but the input data set is ~10 GB, and/or similarly "scaled" such that naive solutions fail outright.

Other scaling-of-inputs could include: Text with line-lengths over 2 GB, numbers above 2^60, data designed such that naive nested-loop solutions (quadratic scaling) take over a year to compute the answer, etc...

Basically, force developers to solve the problem robustly with: streaming, parallelism, efficient algorithms with good big-O properties, correct data type choice (including intermediate accumulator values!), and so forth.

It could be a three-star challenge feature added to the current version. It wouldn't even require large downloads: a Python script or something similar could be used to generate arbitrarily large inputs. (Alternatively, a common CDN-cacheable prefix with a distinct suffix per competitor.)

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

#69

Post by philiplu »

jiggawatts wrote: post #68
joshlemer wrote: post #51

I've been thinking recently about how things like Project Euler, LeetCode, and to a bit less of an extent, Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms, that it makes them suboptimal as a tools for getting familiar with a new programming language. I know that that critique isn't new to anyone but it makes me think about how it would be cool if there were a code p…

Something I'd love to see is "AoC hard mode": the exact same problems but the input data set is ~10 GB, and/or similarly "scaled" such that naive solutions fail outright. Other scaling-of-inputs could include: Text with line-lengths over 2 GB, numbers above 2^60, data designed such that naive nested-loop solutions (quadratic scaling) take over a year to compute the answer, etc... Basically, force developers to solve…

That's exactly what Project Euler problems often do, especially once you get past the first hundred or two. Problems are scaled so a brute-force often means hours to days of compute time, or worse.

You get to recognize the effect - if I see a problem that's clearly number-theory related and with a limit of 10^12, I know they're looking for a sublinear algorithm, probably O(n^(2/3)) thanks to various multiplicative function ideas that appear over and over.

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

#70

Post by fulafel »

110jawefopiwa wrote: post #64
joshlemer wrote: post #51

I've been thinking recently about how things like Project Euler, LeetCode, and to a bit less of an extent, Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms, that it makes them suboptimal as a tools for getting familiar with a new programming language. I know that that critique isn't new to anyone but it makes me think about how it would be cool if there were a code p…

> Advent of Code, are so heavily focused on making clever use of math, data structures and algorithms I've done a fair amount of Advent of Code and I wouldn't say it's at all "focused" on this. The vast majority of the questions use hash tables and graph traversal as the full extent of their use of math/DS/algos. There's always one or two puzzles every year that require some particular math/CS insight but most of the…

AoC is still is algorithms and data structures: there's minimal interaction with the outside world, just solving the problem for the input data. It's just about coming up with the algorithm yourself instead of applying fancy well-known ones.
Post reply on HN