3 ms·

What a tragedy. I remember Bob’s code that generates certain numbers: https://www.beust.com/weblog/coding-challenge/ https://www.beust.com/weblog/coding-challen

What a tragedy. I remember Bob’s code that generates certain numbers: https://www.beust.com/weblog/coding-challenge/ https://www.beust.com/weblog/coding-challenge/. Bob’s code is in Java, yet uses clever backtracking techniques to achieve the best performance among many solutions in all kinds of languanges.

somekyle 4y ago
Hah! I was just remembering the exact same thing. His fingerprints are all over my development as a professional Java programmer.
scythe 4y ago
I was curious about this, but it looks like the links to crazybob.org now 404. It seems to me like the trick would be to find a way to generate, in order, the numbers you can't print, then you just print the gaps between them.
bootsygw 4y ago
https://web.archive.org/web/20080912181335/crazybob.org/BeustSequence.java.html https://web.archive.org/web/20080912181335/crazybob.org/Beus...
- hintymad 4y ago
  Huh, it seems Bob further optimized his code. The one I remember used the similar approach, but employed a doubly-linked list for backtracking. The pleasant surprise that I got from his code was that recursion plus a linked list still beat those "faster" languages, a classical example of optimizing algorithms first, as beautifully argued in Steven Skiena's Algorithm Design Manual
  - bdwedding 4y ago
    Here's the one you were thinking of. This was the one "further optimized", not the first one posted: https://web.archive.org/web/20090723015302/http://crazybob.org/FastBeustSequence.java.html https://web.archive.org/web/20090723015302/http://crazybob.o...
    - hintymad 4y ago
      Ah, yes. Thanks!
bdwedding 4y ago
I ported his code to C++, the linked list version and the other recursive version. Then I removed the recursion. For me, the linked list is 2X slower and the non-recursive version using a stack is slightly faster than his original version. https://gist.github.com/bwedding/19c1bd0e967cfb62084fabdd6bfcd598 https://gist.github.com/bwedding/19c1bd0e967cfb62084fabdd6bf...
swagv1 4y ago
Put it on his epitaph

somekyle 4y ago

Hah! I was just remembering the exact same thing. His fingerprints are all over my development as a professional Java programmer.

scythe 4y ago

I was curious about this, but it looks like the links to crazybob.org now 404. It seems to me like the trick would be to find a way to generate, in order, the numbers you can't print, then you just print the gaps between them.

bootsygw 4y ago

https://web.archive.org/web/20080912181335/crazybob.org/BeustSequence.java.html https://web.archive.org/web/20080912181335/crazybob.org/Beus...

hintymad 4y ago
Huh, it seems Bob further optimized his code. The one I remember used the similar approach, but employed a doubly-linked list for backtracking. The pleasant surprise that I got from his code was that recursion plus a linked list still beat those "faster" languages, a classical example of optimizing algorithms first, as beautifully argued in Steven Skiena's Algorithm Design Manual
- bdwedding 4y ago
  Here's the one you were thinking of. This was the one "further optimized", not the first one posted: https://web.archive.org/web/20090723015302/http://crazybob.org/FastBeustSequence.java.html https://web.archive.org/web/20090723015302/http://crazybob.o...
  - hintymad 4y ago
    Ah, yes. Thanks!

bdwedding 4y ago

I ported his code to C++, the linked list version and the other recursive version. Then I removed the recursion. For me, the linked list is 2X slower and the non-recursive version using a stack is slightly faster than his original version. https://gist.github.com/bwedding/19c1bd0e967cfb62084fabdd6bfcd598 https://gist.github.com/bwedding/19c1bd0e967cfb62084fabdd6bf...

swagv1 4y ago

Put it on his epitaph