Timeline for Knuth's Power Tree
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 27, 2011 at 4:59 | comment | added | MtnViewMark | The skill in writing code-golf problems is to admit as much possible variation in implementation as possible, so that the smallest possible code can produce the desired result. If the requirements presume a particular implementation approach or language it's a fail. | |
| Jul 27, 2011 at 4:54 | comment | added | boothby | So, that's why I make the requirement that you compute the whole tree. The point of code-golf (IMO) is to satisfy all requirements in the smallest number of characters. If you're not satisfying all the requirements, it's a fail. | |
| Jul 27, 2011 at 4:31 | comment | added | MtnViewMark | The algorithm used was aiming for code-golf, not time efficiency: It is roughly O(n^3 lg n) in time, though oddly only O(n) in space. On my somewhat aging CPU, it can compute the chain for 10k in 9.58s, or just about 100x the time it took to compute the chain for 1k. I'm pretty sure computing the chain for 50M wouldn't be possible with this code. | |
| Jul 26, 2011 at 7:08 | comment | added | boothby | Fascinating. What kind of runtime do you get to compute the chain for 50M? The algorithm Knuth describes is O(n lg n) time and 2n+lg n space. | |
| Jul 26, 2011 at 3:16 | history | edited | MtnViewMark | CC BY-SA 3.0 |
made the pre-computing main example more clear
|
| Jul 26, 2011 at 2:51 | history | edited | MtnViewMark | CC BY-SA 3.0 |
added 1863 characters in body
|
| Jul 26, 2011 at 1:58 | comment | added | MtnViewMark | It wasn't clear how to apply the requirements to a lazy language. Usually, an input value like this is given as a help so solutions can just allocate a fixed array. Solutions in dynamic languages often ignore such input (or limits in the spec). I took the input to be a hint to the program as a bound on subsequent inputs. Indeed a program that meets the input/output requirements of this problem needn't use it at all. Typically, code-golf doesn't mandate how the internals achieve the results. | |
| Jul 25, 2011 at 7:33 | comment | added | boothby | This doesn't compute the complete tree with n nodes. | |
| Jul 25, 2011 at 5:13 | history | edited | MtnViewMark | CC BY-SA 3.0 |
deleted 105 characters in body
|
| Jul 24, 2011 at 4:01 | history | edited | MtnViewMark | CC BY-SA 3.0 |
added 58 characters in body
|
| Jul 23, 2011 at 6:56 | history | answered | MtnViewMark | CC BY-SA 3.0 |