Non-standard solution of one problem with ProjectEuler

Problems with Project Euler are good because they allow you to have fun and train your brain at different levels of complexity for the same task. The simplest approach is brute force. The first two dozen tasks for 99% are solved with this approach. After sending the correct answer to the task, the forum thread opens on it. Fans from dozens of countries are competing, who quote the solution more sophisticatedly. The more advanced use the built-in capabilities of the languages ​​in which they write the solution, but the essence is the same — brute force or explicit with a bunch of nested loops or implicit through the call of special functions. It looks especially beautiful in Python or Ruby languages ​​(often in one or two lines), more numerous in Java and C ++. The farther, the more forceful the "power" solutions look, using classes like BigInteger. With the increase in the number of the task, brute force can be successfully applied less and less. There are many problems on pure mathematics, where you need to solve the problem on paper, and then encode something completely simple. Sometimes you can do without writing code at all, there are many such tasks - for example, to use combinatorics.

But sometimes it is more pleasant to find a completely non-standard solution.


Example. Task 9 . Find the Pythagorean triplet of integers a, b, c, such that a + b + c = 1000. Let me remind you that the Pythagorean triple is three positive integers a <b <c that are sides of a right triangle, i.e. a ^ 2 + b ^ 2 = c ^ 2. The most famous school example: 3, 4, 5.
')
Reorientation is obvious. It is greatly reduced in time, if you know the properties of such triplets, you can save a lot of iterations. But we will go the other way.

We will use the Solver optimization tool in the MS Excel package of any version for solving.



Solver can be a very powerful tool for finding solutions, although it is said that in very multidimensional cases it succumbs. I still remember the picture when I saw a person who was looking for a Solver to solve or at least a local approximation for a huge system of equations for several dozen variables. He wrote for a master's degree, something in economics. He could definitely write code in any of several languages, but it was a scrap. I put the settings in Solver on a huge maximum number of iterations, a huge maximum search time and started on my computer at work. Something counted there as a result.

By the way, I did not manage to stick the Solver to solve the problem of the maximum sum of the path - there is a non-smooth function, random.

Several problems, as I said, managed to be solved without code, analytically. Once I had to calculate the binomial coefficient, for this I used the engineering calculator Windows. One task at the end of the first hundred was solved with the help of SQL - it was only necessary to copy the data into a table - a regular schedule in Notepad ++, creating a DDL script, and then filling in the table and query in one line.

It is also very entertaining to look at the projectEuler statistics. The most effective languages ​​and environments used are not C ++ \ Java, but the French PARI / GP, Mathematica, Python, and Haskel. Used a lot of exotic (statistics at the time of writing the post):

	Language	Number of Users	Average Percent Solved	Score index
one	PARI / GP	79	23%	99
2	Mathematica	1272	13%	92
3	Python	26887	eight%	81
four	Haskell	4680	eight%	67
five	Sage	180	12%	62
6	Perl	2237	eight%	61
7	C / C ++	28454	6%	61
eight	APL / J / K	254	eleven%	60
9	Java	18158	6%	58
ten	C #	9122	6%	54
eleven	ML	436	9%	54
12	Maple	265	9%	49
13	Ruby	4229	6%	49
14	Scala	1270	7%	49
15	MUMPS	22	sixteen%	49
sixteen	Lisp	1096	7%	48
17	Delphi	451	eight%	48
18	F #	936	7%	47
nineteen	Scheme	744	7%	46
20	Matlab	2122	6%	45
21	Magma	21	15%	45
22	Racket	140	9%	44
23	Component pascal	7	22%	42
24	BASIC	1162	6%	42
25	Go	414	7%	41
26	Frink	ten	18%	41
27	Clojure	991	6%	41
28	D	163	eight%	40
29	Pencil / Paper	805	6%	39
thirty	Pascal	601	6%	38
31	Tcl	65	9%	37
32	R	496	6%	37
33	RPL	14	14%	36
34	Spreadsheet	412	6%	35
35	GAP	26	eleven%	35
36	Assembly	152	7%	34
37	Lua	332	6%	34
38	Fortran	308	6%	34
39	Fororth	39	9%	32
40	Smalltalk	90	7%	31
41	SAS	17	ten%	28
42	Ada	97	6%	27
43	ECMAScript	834	four%	26
44	Q	74	6%	25
45	Erlang	580	four%	25
46	Julia	36	7%	24
47	Autohotkey	12	ten%	24
48	Prolog	114	five%	23
49	Php	2445	3%	23
...	...	...	...	...
53	Octave	63	five%	20
54	Boo	17	7%	nineteen
55	Cobra	3	18%	nineteen
56	Logo	26	6%	nineteen
57	Groovy	38	five%	18
58	SQL	37	five%	17
59	COBOL	nineteen	6%	17
60	Powershell	68	four%	sixteen
...	...	...	...	...
68	Bourne shell	32	3%	ten
...	...	...	...	...

Most of the people, of course, from the States - about 28 thousand, from China and Russia about the same number - about 3000. But if you poke into the country and see the top 100 for the tasks, it is clear that the Chinese are more effective - there are more people who have decided, more 400, 350, 300, etc. tasks. And in India, on the contrary, there are approximately 2.5 times more participants, but less super-solvers than in the Russian Federation. In my opinion, if we normalize this all by the number of population, then, starting with a statistically significant number of participants per country, we can get an estimate of the effectiveness of higher education in it.