Project Euler

Discovered at 2011-06-05-LearningProgrammingThroughProjectEuler

JamesSomers finally got through to Learning Programming by using Project Euler Math problems.

There are 341 problems so far. Of the first 10, the least-solved has been solved 65k times. Of the last 41, the max-solved was solved by 1282 people, the min-solved was solved by 40.

I just found "pandigital" as a term that applies to a problem I have an old program to submit - I wrote it to solve a math problem that Number Two Son was supposed to solve by hand...

Issues with learning from this:

• forums flag solutions by language, but don't let you browse only the responses from the language you used, so it's a pain to browse
• people tend to compete for the most efficient (e.g. shortest code or fastest completion) process, whereas my bias is toward "simplest" (to read). No process of voting for "best" by any criteria, so I guess you revert to browsing all the responses (by your language) and seeing what you find. I don't have the patience for that...
• so having exercises and getting confirmation that I got the right answer is good, but otherwise not a great learning process.

I did 1-9, then jumped ahead to do 25.

Then jumped ahead to 49, which is tricky:

• there are lots of 4-dig numbers with more than 3 permutations that are prime
• for the example they gave, those 3 permutations are a subset of the 6 prime permutations!
• so you have to find all the numbers with 3+ prime permutations, then take all the triple subsets of that group and test them.
• blech very ugly but got final answer

Found that you can sort problems by difficulty, which isn't quite the same as by ID, esp once you get up into the higher IDs.

Jumped to 92 which was much easier. (Solved by 10,564 people.)

Jumped to 145. (Only 5095 solved.) Code is easy, except that numbers get too big.

• Ah, I just dump the range() function and just use a while loop.
• Hmm, seemed like running forever. Then realized that maybe it just wasn't finding any new matches, so added more logging, and confirmed that's what was happening. Trick solved!

I may be "cheating" by picking the problems I want to solve, therefore skipping certain classes or problems. Tsk tsk.

Hmm, 96 has been solved by 4470, and involves writing a Su Do Ku solver. That's kinda tempting, though I've never done one on paper, and haven't done any matrix coding since college...

Jumped to 108 for now (3896 solvers).

• Easy (to get started) except for issues with precision! Getting some false positives because instead of 220 it's getting 219.9999 and then int()=219. Considering how far to push that....
  • Settled for a tiny rounding error buffer
• Pretty slow (up at 20k got max of 361 solutions). Time to look for patterns...
• Already figured out that max(x)=2x.
• Now noticing that for their example all the y values are multiples of x. Oh, wait, not every multiple of x gives a correct y. Look at some places where number of solutions jumps (120, 180, 210, 360, 420): not finding great patterns.
• but duh, at least noticed that jump points are always divisible by 10, so at least can run stupid tests 10x as fast now...
• at n=200,970 have 544 solutions
• ultimately get to 240,240 having 1006 solutions. But this is rejected!
• go back and start again from 45200, get close at 180,180 having 945, but then continues through to 240,240 again!
• go back and start again from 420, run through 51390 getting same results
• possibilities
  • my assumption about jumping by 10 was a mistake
  • at these big numbers my rounding-error slush (0.00001) isn't the right size
    • add 2 more decimal places - definitely changes counts - e.g. get same local max of 18480 but with 336 solutions instead of 468.
    • so start at 240240, it has only 795 solutions now!
    • and if I add 2 more decimal places to slush (0.000000001), then 240240 has only 518 solutions!
    • doh! Generate reciprocal equation, plug in y=round(y), see if equation is true.
    • Now it says that 240240 has 1094 solutions. I start the calculations over and get to 180180 having 1013 solutions. Win!
• reading the forum discovered a database of integer sequences! So you enter in a series that you run across, and then it returns info on a variety of algorithms that generate it! Entering the sequence of local-max above, it returned 3 related series which had basically identical results. So I could have just taken their series of values and run the number of solutions for each, and been done in 30sec!

Dec'2015: Decide to play with GCHQ XMas NonoGram puzzle as exercise.

• realize I never put any of this Euler code in Git or anything, so do it now.
• work on/off on GCHQ bit.
• Jan10'2016, let it run 100M cycles without making much progress, on a brute-force approach (doesn't toggle individual cells, but it sequentially slides runs across rows, so still huge combinatorial explosion). So research to find what other people have done.
  • using MixedIntegerProgramming
  • using SAT/SMT solver
  • a more DIY NonoGram solver approach. Pretty cool, above my pay-grade.
• ah, results in a QR Code