Page 1 of 1
Which problems are the most underappreciated?
Posted: Sun May 18, 2008 7:31 am
by 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.
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 8:00 am
by 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.
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 10:40 am
by Tommy137
I really enjoyed Problem 180.
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 10:48 am
by 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.
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 12:37 pm
by 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?
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 12:47 pm
by Georg
I had much fun solving problem #126. I could not solve problem #181 until I found an equivalent question.
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 1:18 pm
by 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
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 2:31 pm
by euler
stijn263 wrote: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.
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 7:05 pm
by 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.
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 7:08 pm
by 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:
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.
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 7:47 pm
by 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.
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 7:55 pm
by 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!
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 8:06 pm
by 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.
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 9:25 pm
by 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?
Re: Which problems are the most underappreciated?
Posted: Sun May 18, 2008 9:53 pm
by 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.
Re: Which problems are the most underappreciated?
Posted: Mon May 19, 2008 12:12 pm
by stijn263
Colin wrote: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.
Re: Which problems are the most underappreciated?
Posted: Tue May 20, 2008 4:00 am
by 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!!!"
Re: Which problems are the most underappreciated?
Posted: Tue May 20, 2008 12:07 pm
by 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.
Re: Which problems are the most underappreciated?
Posted: Tue May 20, 2008 2:27 pm
by 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
Re: Which problems are the most underappreciated?
Posted: Tue May 20, 2008 8:31 pm
by 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!