Which problems are the most underappreciated?

[Tirian]

Greetings. I found this website a few days ago and have been eagerly delving through it. I was struck by two of the problems that I found tonight toward the "difficult" end of the spectrum.

The first was #173, which despite only having been solved by 534 people at the time of this posting strikes me as deserving of being among the 10% of easiest problems on the site. But I suppose that novice programmers don't think to search through the entire archive and trust that it has few solvers because it is challenging. So it becomes a vicious cycle, where newbies come in and solve the first ten problems and the newer easy problems seem relatively even more intractable.

The other problem was #156, which has quite a number of comments from people effectively smoking an e-cigarette and saying how good that was for them. But the shame of it is that you don't see people saying how enjoyable the problem is until after you've solved it, which is an hour or two (or more) after you decided to attempt it. I'm not suggesting a formal rating process, but it would be neat to hear some word-of-mouth about which challenges are particularly fulfilling.

So, which problems do you think deserve to be attempted by more people? I'm starting to run out of problems that can be solved in five minutes with six lines of code, so I'm definitely interested in hearing about which of the hours-long projects people have enjoyed the most.

[jaap]

My favourite is #184 (Triangles containing the origin).
It is hard but, as with all good problems, there are several approaches you can take and insights you can get in order to cut through the difficulties and avoid complications.

[Tommy137]

I really enjoyed Problem 180.

[stijn263]

The first was #173, which despite only having been solved by 534 people at the time of this posting strikes me as deserving of being among the 10% of easiest problems on the site. But I suppose that novice programmers don't think to search through the entire archive and trust that it has few solvers because it is challenging. So it becomes a vicious cycle, where newbies come in and solve the first ten problems and the newer easy problems seem relatively even more intractable.

I think a lot of people solve the problems in numerical order for some reason. But you can still see which of the newer problems are among the easier ones by comparing the number of solvers to the adjacent problems. 173 and 145 have a relatively very high number of solvers for instance.

However, I liked 167 (investigating Ulam sequences) best. It's so much fun to discover all the patterns imho .

I think the harder problems give more satisfaction if you manage to crack them.

[stijn263]

But the shame of it is that you don't see people saying how enjoyable the problem is until after you've solved it

Colin, is it possible to create some sort of poll that asks people right after they've solved a problem, how much fun they had solving the problem. And then perhaps add an extra column to problems page showing the average opinion.

Only requires the database to store 2 extra integers per problem. Shouldn't cause that much extra server load right?

[Georg]

I had much fun solving problem #126. I could not solve problem #181 until I found an equivalent question.

[stijn263]

yup, 126 is lots of fun

I had the most trouble with problem 161, and I must confess I still don't know how to solve that one decently

[euler]

Colin, is it possible to create some sort of poll that asks people right after they've solved a problem, how much fun they had solving the problem. And then perhaps add an extra column to problems page showing the average opinion.

Only requires the database to store 2 extra integers per problem. Shouldn't cause that much extra server load right?

Indeed such a rating system would be a good addition, but doing it retrospectively might result in an unavoidable skew for older problems. It could certainly be done with two fields: "number of votes" and "total of votes". However, it would require a considerable addition to the database if we were to allow members to retract or alter their votes. Similarly if we had a voting system on difficulty we would find that opinions are relative to current experience and as members improve their skills they may wish to re-evaluate their rating; that is, what they considered hard one month before now seems trivial and they quickly run out of numbers on the scale to rate considerably harder problems.

Of course, if anyone has any suggestions on how this could be managed I would gladly entertain it, as I think it has the potential to be a valuable addition to Project Euler.

[Tirian]

Yeah, when I said that I wasn't recommending a formal rating system in my original post, it was because those concerns seemed thorny. Now that I've had a good night's sleep, I'll take a stab at it.

I share your feelings that asking a person how hard a problem was is not going to be useful information. On the other hand, it might be fruitful to compute the number of people who have solved a problem as a fraction of the number of people who have "tried" in the form of viewing the problem page at least once. In theory, two problems that have been solved by 80% of passersby are equally difficult even if one has been solved by 20,000 players and the other by 500. It's a little bit arbitrary, since you never know if someone is reading a summary without actually being interested in the problem, but it's probably more effective than the current scheme of punishing easy problems that were posted in the past year. Oh, and if you went ahead with this you would have to initially set players to have seen exactly the problems that they have solved; you'd need to collect "seeing" data for a few weeks before doing this difficulty sort to keep from having a 194-way tie for first.

But I think that an "enjoyment" poll would be very nice. Just a 1-5 thing, and make it clear from the start that 1 is the pleasure that you get from performing a Google search and 6 would theoretically be the satisfaction you would get from settling the Goldbach Conjecture (so that hopefully people don't overfill the high values too early in their PE "career"), but you'd let players be able to change their votes afterwards anyways by putting the poll down with the solution and forum link in the problem page for solved problems. An additional check would to weigh a player's rating by a factor of the square of their Genius percentage, so that someone who has solved 10% of the problems would only have 1% of the impact of a player who has experienced all of them. It may be a very gradual process at first, but eventually the cream will rise to the top.

I'm no master of database design, but this could theoretically all be handled with an extra three bits for each problem in the player profile (0 = unseen, -1 = seen but unsolved, 1-5 = solved) -- if your current design is more bulky than a simple bitfield then you may have enough room already for it. Data-intensive things like a problem's average weighted enjoyment rating and the number of players who have seen a puzzle could be recalculated on an hourly (or whatever) basis and stored as two additional fields in the problem file.

[ed_r]

How about computing, for each question, the ratio of forum posts to solvers. (Hypothesis being, of course, that if you loved a problem then you'd say so.)

Here are scores for problems 170-194 inclusive:

•  [1]  194 0.84615385
   [2]  177 0.34444444
   [3]  184 0.33613445
   [4]  192 0.33333333
   [5]  186 0.32919255
   [6]  180 0.31578947
   [7]  175 0.25352113
   [8]  188 0.24100719
   [9]  189 0.22413793
  [10]  185 0.22388060
  [11]  193 0.21951220
  [12]  178 0.20000000
  [13]  183 0.19526627
  [14]  181 0.19200000
  [15]  179 0.17035775
  [16]  191 0.16967509
  [17]  172 0.15662651
  [18]  171 0.15000000
  [19]  190 0.14410480
  [20]  170 0.13194444
  [21]  187 0.12778905
  [22]  176 0.12500000
  [23]  182 0.11510791
  [24]  174 0.10362694
  [25]  173 0.09514925

Stijn's #194 is the winner by miles! I expect his score will tail off a little as the currently-brand-new problem ages, though.

jaap's and Tommy137's favourites do well, too. Perhaps I'm on to something.

[daniel.is.fischer]

With our top solvers always being in early, it's clear that the latest problems will always be at the top with that, because there are still few solutions and most of the top solvers have the habit of posting their ideas and codes. The ratio of posts to solutions becomes more interesting after a few weeks. But even then the newer problems will have a higher ratio. It's an interesting measure for problems between two and ?? weeks of age, I'd say.

[ed_r]

Take a look at a scatterplot for my data: there is only a slight trend towards newer problems having higher score.

If someone can automate computation of the scores then we could identify the bias more accurately and perhaps attempt to remove it.

btw, it's not beyond the realms of possibility that we're getting better at setting interesting PE problems!

[hk]

Is it not a good habit to refrain from posting in the forum if one has nothing new to add?
Just some time ago we closed the fora with more than 100 posts because these fora became so long that everyone, without reading previous entrances, lifted his paw and put his scent flag there.
If we would misuse the forum as a hidden popularity poll I fear the number of posts with the single line: "Nice one" will start to outnumber the content rich posts.

[ed_r]

So do the stats now to get a baseline and then ignore them as the false posts roll in.

Honestly, you don't really think that a "proper" voting system is any more resistant to abuse do you?

[hk]

Let me be honest: I'm not that interested in any public voting system at all. That is allways liable to undesirable influencing. Your suggestion could be used in the background as extra information.

[stijn263]

Indeed such a rating system would be a good addition, but doing it retrospectively might result in an unavoidable skew for older problems. It could certainly be done with two fields: "number of votes" and "total of votes". However, it would require a considerable addition to the database if we were to allow members to retract or alter their votes. Similarly if we had a voting system on difficulty we would find that opinions are relative to current experience and as members improve their skills they may wish to re-evaluate their rating; that is, what they considered hard one month before now seems trivial and they quickly run out of numbers on the scale to rate considerably harder problems.

I was thinking about just a single poll whenever you get the green tick (and only then), asking how much you enjoyed solving the problem. I don't think people would want to retract or alter their votes later. I wouldn't implement it retrospectively, might be too much of a hassle and I honestly don't have a clue anymore about how much I enjoyed fi problem 47. So I'd say implement it for new problems only, or for all problems and people who've solved a problem already can't vote anymore.

[rayfil]

The enjoyment of solving a problem is also VERY relative. For instance, the top solvers may not really enjoy easy-to-medium problem which they can often solve within minutes of the problem being published. That same problem may be VERY enjoyable by some other person who may not have the same abilities and not be expected to solve more than half the published problems.

"Beauty is in the eye of the beholder!!!"

[miodrag.milenkovic]

I think it might be better for everybody, and a very enjoyable exercise for the original poster, if he developed a little statistical model for himself that would help him offset all the biases that he thinks he noticed.

[hk]

For those problems where the forum has not reached 100 posts one can see the number of posts only in the forum itself.
I compiled manually a list containing:
problem ID, date of publication, number of posts and number of solvers. Numbers were harvested today about an hour ago.
The list is below. Anyone interested in doing whatever arithmatic he likes on those numbers can do so now.

Code: Select all

ID    Date   posts solved 
1 05 Oct 2001  949 22120  
2 19 Oct 2001  621 18483  
3 02 Nov 2001  458 13662  
4 16 Nov 2001  449 12992  
5 30 Nov 2001  462 15271  
6 14 Dec 2001  442 16028  
7 28 Dec 2001  395 13314  
8 11 Jan 2002  445 12051  
9 25 Jan 2002  374 11997  
10 08 Feb 2002  347 10927  
11 22 Feb 2002  321 8285  
12 08 Mar 2002  266 6659  
13 22 Mar 2002  285 8691  
14 05 Apr 2002  325 7928  
15 19 Apr 2002  273 6522
16 03 May 2002  285 9225  
17 17 May 2002  257 5459  
18 31 May 2002  176 5620  
19 14 Jun 2002  248 5130  
20 21 Jun 2002  278 8962  
21 05 Jul 2002  231 5725  
22 19 Jul 2002  248 5411  
23 02 Aug 2002  120 3486  
24 16 Aug 2002  194 4672  
25 30 Aug 2002  236 7023  
26 13 Sep 2002  138 3095  
27 27 Sep 2002  113 3207  
28 11 Oct 2002  254 5403  
29 25 Oct 2002  205 4066  
30 08 Nov 2002  173 4915  
31 22 Nov 2002  165 3260  
32 06 Dec 2002  104 2554  
33 20 Dec 2002  118 3028  
34 03 Jan 2003  150 4265  
35 17 Jan 2003  130 3779  
36 31 Jan 2003  210 4406  
37 14 Feb 2003  127 3012  
38 28 Feb 2003  107 2411 
39 14 Mar 2003  138 3091  
40 28 Mar 2003  187 3702  
41 11 Apr 2003  105 2722  
42 25 Apr 2003  147 3332  
43 09 May 2003  123 2209  
44 23 May 2003  94  2146  
45 06 Jun 2003  138 3186  
46 20 Jun 2003  90  2197  
47 04 Jul 2003  100 2191  
48 18 Jul 2003  240 6008  
49 01 Aug 2003  81  2048  
50 15 Aug 2003  100 2147  
51 29 Aug 2003  63  1064 
52 12 Sep 2003  156 3488  
53 26 Sep 2003  160 3218  
54 10 Oct 2003  133 1409  
55 24 Oct 2003  128 2572  
56 07 Nov 2003  113 3050  
57 21 Nov 2003  102 1829  
58 05 Dec 2003  95  1760  
59 19 Dec 2003  127 2211  
60 02 Jan 2004  58   874  
61 16 Jan 2004  72   971  
62 30 Jan 2004  84  1324   
63 13 Feb 2004  114 2400  
64 27 Feb 2004  71   909  
65 12 Mar 2004  63  1335  
66 26 Mar 2004  85   877  
67 09 Apr 2004  200 4435  
68 23 Apr 2004  64   864  
69 07 May 2004  97  1807  
70 21 May 2004  79  1094 
71 04 Jun 2004  100 1643  
72 18 Jun 2004  77  1108  
73 02 Jul 2004  93  1494  
74 16 Jul 2004  70  1380  
75 30 Jul 2004  77   746  
76 13 Aug 2004  106 1597  
77 27 Aug 2004  81   841  
78 10 Sep 2004  58   727 
79 17 Sep 2004  144 3229  
80 08 Oct 2004  99  1006  
81 22 Oct 2004  92  1863  
82 05 Nov 2004  78  1176  
83 19 Nov 2004  68   902  
84 03 Dec 2004  75   618 
85 17 Dec 2004  84  1496  
86 07 Jan 2005  48   591 
87 21 Jan 2005  71  1159  
88 04 Feb 2005  55   428 
89 18 Feb 2005  94   971  
90 04 Mar 2005  63   515 
91 18 Mar 2005  71   841 
92 01 Apr 2005  96  2395  
93 15 Apr 2005  62   554  
94 29 Apr 2005  59   584  
95 13 May 2005  39   676 
96 27 May 2005  101 1056  
97 10 Jun 2005  135 3332  
98 17 Jun 2005  40   496 
99 01 Jul 2005  100 1922   
100 15 Jul 2005  65  653   
101 29 Jul 2005  71  525  
102 12 Aug 2005  100 1274  
103 26 Aug 2005  24   432  
104 09 Sep 2005  62   962  
105 23 Sep 2005  29   424 
106 07 Oct 2005  42   345 
107 21 Oct 2005  57   607 
108 04 Nov 2005  59   856 
109 18 Nov 2005  42   461 
110 02 Dec 2005  64   517 
111 16 Dec 2005  36   422 
112 30 Dec 2005  83  1423  
113 10 Feb 2006  79   709 
114 17 Feb 2006  53   657
115 24 Feb 2006  53   600 
116 03 Mar 2006  50   792 
117 10 Mar 2006  55   739 
118 24 Mar 2006  38   395 
119 07 Apr 2006  60   699 
120 21 Apr 2006  53   831 
121 19 May 2006  61   542 
122 02 Jun 2006  66   511 
123 16 Jun 2006  51   762 
124 14 Jul 2006  78  1023  
125 04 Aug 2006  67   762 
126 18 Aug 2006  48   283 
127 01 Sep 2006  38   366 
128 29 Sep 2006  29   303 
129 27 Oct 2006  32   389 
130 27 Oct 2006  68   391 
131 10 Nov 2006  51   459 
132 01 Dec 2006  41   392 
133 01 Dec 2006  19   339 
134 15 Dec 2006  48   406 
135 29 Dec 2006  32   392 
136 29 Dec 2006  30   348 
137 12 Jan 2007  41   366 
138 20 Jan 2007  56   414 
139 27 Jan 2007  34   343 
140 03 Feb 2007  38   273 
141 17 Feb 2007  33   233 
142 24 Feb 2007  35   364 
143 02 Mar 2007  47   177 
144 09 Mar 2007  48   285 
145 16 Mar 2007  61   961 
146 24 Mar 2007  34   313 
147 31 Mar 2007  28   197 
148 07 Apr 2007  52   326 
149 13 Apr 2007  23   306 
150 13 Apr 2007  23   246 
151 20 Apr 2007  46   325 
152 27 Apr 2007  28   177 
153 05 May 2007  18   159 
154 12 May 2007  24   172 
155 19 May 2007  34   240 
156 25 May 2007  35   173 
157 01 Jun 2007  20   199 
158 15 Jun 2007  25   270
159 30 Jun 2007  33   251 
160 07 Sep 2007  35   219 
161 21 Sep 2007  26   149 
162 05 Oct 2007  46   309 
163 13 Oct 2007  27   137 
164 20 Oct 2007  57   369 
165 27 Oct 2007  34   173 
166 03 Nov 2007  37   290 
167 09 Nov 2007  42   123 
168 16 Nov 2007  37   183 
169 23 Nov 2007  58   276 
170 01 Dec 2007  19   144 
171 08 Dec 2007  24   161 
172 15 Dec 2007  39   250 
173 22 Dec 2007  51   539 
174 22 Dec 2007  40   391
175 28 Dec 2007  36   142 
176 04 Jan 2008  20   161 
177 11 Jan 2008  31    90 
178 19 Jan 2008  42   211 
179 26 Jan 2008  100  592 
180 02 Feb 2008  36   114 
181 09 Feb 2008  24   126 
182 15 Feb 2008  16   139 
183 22 Feb 2008  66   340 
184 29 Feb 2008  41   121 
185 08 Mar 2008  46   205 
186 15 Mar 2008  54   162 
187 22 Mar 2008  63   498 
188 04 Apr 2008  68   284 
189 11 Apr 2008  26   119 
190 18 Apr 2008  33   234 
191 26 Apr 2008  47   282 
192 03 May 2008  27    82 
193 10 May 2008  18    90 
194 17 May 2008  26    39 

[ed_r]

Thanks Hans. It's now clear that there is a strong relationship, as Daniel predicted, that fewer solvers => higher posting rate. Modelling it seems tricky, though. If the number of posts is p and the number of solvers s, then a reasonable fit is log(p/s) = 1.012 - 5.544log(log(log(s))) ... but the variance of points around the best fit line seems hard to judge, so calculation of significance levels looks like a step too far down the route of damned lies and statistics.

Instead, then, I abandoned statistics and performed a simple search to find all problems whose posting rate was maximal among all problems with at the same or more solvers. By that measure, the top tier is:

• Gold: 1 17 19 29 31 40 54 59 71 75 76 80 84 96 113 130 143 167 177 179 183 186 188 194

Deleting those from the original list and repeating the calculation, we find the other medal winners:

• Silver: 2 4 8 11 14 15 22 28 36 43 53 55 57 62 66 73 85 89 93
• Bronze: 94 100 101 102 121 126 138 144 148 164 169 175 184 185

The lesser places:

• Fourth tier: 3 5 6 12 21 24 25 48 58 63 64 67 69 70 72 77 82 99 110 112 122 124 151 156 162 168 178 180 189 191 192
• Fifth tier: 7 9 10 13 30 47 50 52 61 74 81 83 87 88 90 91 107 125 140 160 163 165 172 173 187 193
• Sixth tier: 16 18 20 34 39 42 51 60 65 68 78 79 104 106 109 115 117 119 131 134 147 152 155 159 161 166 181
• Seventh tier: 23 26 35 45 86 97 108 111 114 118 132 137 141 145 171 190
• Eighth tier: 27 33 37 38 56 98 120 123 127 135 146 154 174

And, finally, the also-rans:

• Ninth tier: 32 41 44 46 105 116 129 139 142 157 170 176
• Tenth tier: 92 95 128 136 153 182
• Bottom tier: 49 103 133 149 150 158

So there you have it. All completely indefensible, of course, but it was fun!