Card Trick Leads to New Bound on Data Compression (2010)

Re:Card Trick Leads to New Bound on Data Compression (2010) by nly on Sunday August 17, 2014 @06:37AM (#8189099)

De Bruijn sequences are cool. Last time I came across them was a fast way to do bit scans. On the older Intel Atoms, an optimised De Bruijn routine to count the numbers of bits set in a word, is competitive with the x86 intrinsic.

https://chessprogramming.wikispaces.com/BitScan

[ Parent | on HN ]

Re:Card Trick Leads to New Bound on Data Compression (2010) by andrelaszlo on Sunday August 17, 2014 @07:11AM (#8189164)

I found out about de Bruijn sequences while brute forcing a digital door lock (it was my own door, my landlord changes the code sometimes). It only works when you are able to keep entering digits until you hit the correct sequence. If the thing resets every four digits, it's useless of course.

A four digit key will yield a 10003 digit de Bruijn sequence so if you push 2.5 keys/s it will take you at most 7 hours to hit the correct key. Doing all keys in sequence 0000, 0001, ..., 9999 will take you at most 28 hours.

Did I find the code? Yes, I asked the neighbor.

[ Parent | on HN ]