4 ms·

Here's an actual case where understanding computer science would have been immensely helpful... > The motivation for this aberrant behavior was a contest put o

by hnfong 2y ago

Here's an actual case where understanding computer science would have been immensely helpful... > The motivation for this aberrant behavior was a contest put on by a local radio station. Each day a disk jockey would read a serial number aloud on the air, and if any listener was able to produce the matching dollar bill they would win $30,000. Michael reasoned that 100,000 one dollar bills was 100,000 opportunities to win the prize, giving him a statistical advantage. And even if his scheme proved fruitless he would just redeposit his money, so he figured he had nothing to lose. > Michael and Teresa spent each day rifling through piles of cash looking for matches, pausing only for such distractions as eating, bathing, and excreting. They soon realized that it was impossible for two people to examine that much money in the allotted time (sort then binary search)

taneq 2y ago
Maybe less lucrative but when we had some new bookshelves installed and moved all our books onto them I used mergesort to get them in order. ;)
- marcosdumay 2y ago
  Bucket-(insert-)sort is also an all time favorite. I've taught it to many people already. It helps that it works in a very intuitive way.
  - noman-land 2y ago
    Teach it to us! I'm not familiar with this.
    - jasonjmcghee 2y ago
      It's bucket sort, and parent is suggesting insertion sort within each bucket as the pre-merge step. Say you're sorting alphabetically by title. You make one bucket per letter- put books into their respective bucket based on first letter of title. Then sort using insertion sort within each bucket. Then you're done. (insertion sort is the human natural one- look for where the next one goes based on what you have so far and insert) Same works for other heuristics.
- hennell 2y ago
  I've often pondered the optimal book organisation, sorting and inserting system. Organising by subject seems a good start, but then you have size to conser. Then you also tend to arrange by space - i.e. you might put two subjects together based more on similar size or shelf capacity then logical subject grouping. For inserts a reverse-sorted inserting-from-the-back makes most sense to reduce moving of books, but I suspect there's probably an optimal 'free space' value to allow for easier inserting.
  - lostlogin 2y ago
    > I've often pondered the optimal book organisation Let me introduce you to an option I recently found. I went to get a book from our (large) bookcase and found they’d all been reorganised based on cover colour.
    - kragen 2y ago
      that's grounds for divorce
    - gravescale 2y ago
      Makes it much easier to buy new books that way: https://www.ebay.com/sch/i.html?_nkw=red+books+by+foot https://www.ebay.com/sch/i.html?_nkw=red+books+by+foot
mattmaroon 2y ago
I had the same thought too, if you take the time to sort the bills the lookups are easy. And it probably doesn’t take much more time to sort them than it does to go through them all once looking for a number.
- tromp 2y ago
  For a radix sort on the 8 digit USD serial numbers, it takes 8x more time (the 2 letters can be ignored). That could be halved by radix sorting on pairs of digits, but then keeping track of 100 piles instead of 10 probably negates most of the gain. In practice, partial sorting suffices to reduce the serial number search time to a reasonably short amount, e.g. by 4 rounds of radix sorting.
  - mattmaroon 2y ago
    Right, so basically by your ninth time doing this you’d have broken even (ish) on time. He was doing it every day so that’d be a great investment. It also would reduce the possibility of errors greatly I’d think.
    - Retric 2y ago
      100k bills doesn’t need an exact sort to be vastly faster. Day one you sort by first digit, then keep sorting matching digits stopping when you have say 20 numbers in a pile. My guess is you break even on day 2 and the first day is only slightly worse.
      - mattmaroon 2y ago
        That’s a good point, each individual sort probably takes only slightly longer than just looking through them for the number. So the actual sorting might not really add much time at all
  - kragen 2y ago
    in a single round of digit-pair radix sorting, you can put 100 piles of ≈1000 bills each into 10×10 cubbyholes, a piece of furniture which is small enough to fit on a desk. then you need about 20 minutes to linearly search through one such pile when the dj announces a number, which is probably fast enough to win if you have a second cubbyhole array, when you linearly search through a pile chosen from the first cubbyhole array, you can radix-sort that pile by another two digits, dividing it into piles of ≈10 bills. those piles are small enough that you can keep them sorted as you build them without much loss of efficiency, even on a computer if you can fill the first array with 100 wallets with 10 numbered tabs each, like the tabbed dividers in a looseleaf notebook, you can divide the bills into 1000 piles on the first radix-sorting pass. in practice it might be too much work to find or make the wallets but i think the sad thing about michael larson's story is not that he didn't know enough about computer 'science' (or, i guess, library 'science'), but that he spent more effort searching for a hack that would make hard things easy than it would have taken to do them the hard way, destroying his personal relationships in the process
paxys 2y ago
Maybe, but even then I doubt the scheme was well thought out. He had 100,000 bills but the total number of serial numbers is many magnitudes greater than that. The chance that he'd actually have a hit was close to zero. And that is assuming the contest was legitimate in the first place.
- npilk 2y ago
  Seems like the classic form of this contest would be for the radio DJ to pull a bill out of his wallet and read that serial number over the air...
  - CleanRoomClub 2y ago
    Haha this is what I was thinking. Did anyone ever actually win this prize?
  - easton 2y ago
    IIRC serial numbers aren't unique. Even if the DJ was doing that, there would still be a chance. (albeit extremely small)
    - hiatus 2y ago
      > A unique combination of eleven numbers and letters appears twice on the front of the note. Each note has a unique serial number. The first letter of the serial number corresponds to the series year. https://www.uscurrency.gov/denominations/bank-note-identifiers https://www.uscurrency.gov/denominations/bank-note-identifie...
      - chungy 2y ago
        It's not the whole story. In genuine currency, serial numbers are only unique within a series. Series 2017A and series 2021 notes can (and in fact do, since they start over at A00000001A) have identical serial numbers.
        deleted 2y ago
uses 2y ago
Yeah this part bothered me. It's surprising if they really didn't immediately realize randomly looking at single bills was an impossible strategy. Kind of an interesting problem. Complete sorting in a timely manner is basically not possible because of the physical reality of 100k pieces of paper. But maybe you can group the bills into 100 piles of "last 2 digits", so then for each lookup you "only" have to check 1000 bills. And then later, while searching a group, you can take the time to further sort them by the 3rd digit. I guess it also depends on how long you expect the contest to go on, i.e. how many lookups you will do. Even with the simplified grouping strategy, let's be generous and assume it takes you 3 seconds to look at a bill, figure out what to do with it, and physically move it to the correct place. That's still 83 person-hours to do a single pass and put the bills into 100 groups for quicker lookup. With 2 people, that's 5 full 8 hour days of non-stop sorting.
- bluGill 2y ago
  I would copy the serials onto paper in sorted order. Then I only need to find the bill after I know I have it. I'd still need to find the bill on demand - but you typically get 10 minutes to call and then days to prove it (this was the 1980s - you couldn't email a digital photo back then. Today I'd forge the digital photo and have hours to set the real one aside for when they check)
  - nucleardog 2y ago
    This is more or less the way I’d go. It’s “what the client asked for” versus “what solves the client’s problem”. You don’t need to find the bill within minutes, you need to know that you _have_ the bill quickly. Grab a big binder, half dozen packs of dividers, a pack of loose leaf paper, and a box of pens. Divide the binder into ranges. In each range use a separate piece of paper for the next digit. Don’t worry about sorting past there, just write all your serial numbers down. Now you can use the dividers to narrow it down to around 2,000 bills. Flipping through ten pages to find the next digit you’ve narrowed it down to about 200 bills. You can probably scan two hundred numbers quickly enough.
- scottyah 2y ago
supportengineer 2y ago
This reminds me of the old website, "Where's George?" Sample bill report: https://www.wheresgeorge.com/b:QZHjxdYnJ&entry=17 https://www.wheresgeorge.com/b:QZHjxdYnJ&entry=17
- bsagdiyev 2y ago
  I got one of those bills as change on NAVSTA Rota back in the early 2000s, it was neat to see the path it took.

by hnfong 2y ago

taneq 2y ago

Maybe less lucrative but when we had some new bookshelves installed and moved all our books onto them I used mergesort to get them in order. ;)

marcosdumay 2y ago
Bucket-(insert-)sort is also an all time favorite. I've taught it to many people already. It helps that it works in a very intuitive way.
- noman-land 2y ago
  Teach it to us! I'm not familiar with this.
  - jasonjmcghee 2y ago
    It's bucket sort, and parent is suggesting insertion sort within each bucket as the pre-merge step. Say you're sorting alphabetically by title. You make one bucket per letter- put books into their respective bucket based on first letter of title. Then sort using insertion sort within each bucket. Then you're done. (insertion sort is the human natural one- look for where the next one goes based on what you have so far and insert) Same works for other heuristics.
hennell 2y ago
I've often pondered the optimal book organisation, sorting and inserting system. Organising by subject seems a good start, but then you have size to conser. Then you also tend to arrange by space - i.e. you might put two subjects together based more on similar size or shelf capacity then logical subject grouping. For inserts a reverse-sorted inserting-from-the-back makes most sense to reduce moving of books, but I suspect there's probably an optimal 'free space' value to allow for easier inserting.
- lostlogin 2y ago
  > I've often pondered the optimal book organisation Let me introduce you to an option I recently found. I went to get a book from our (large) bookcase and found they’d all been reorganised based on cover colour.
  - kragen 2y ago
    that's grounds for divorce
  - gravescale 2y ago
    Makes it much easier to buy new books that way: https://www.ebay.com/sch/i.html?_nkw=red+books+by+foot https://www.ebay.com/sch/i.html?_nkw=red+books+by+foot

mattmaroon 2y ago

I had the same thought too, if you take the time to sort the bills the lookups are easy. And it probably doesn’t take much more time to sort them than it does to go through them all once looking for a number.

tromp 2y ago
For a radix sort on the 8 digit USD serial numbers, it takes 8x more time (the 2 letters can be ignored). That could be halved by radix sorting on pairs of digits, but then keeping track of 100 piles instead of 10 probably negates most of the gain. In practice, partial sorting suffices to reduce the serial number search time to a reasonably short amount, e.g. by 4 rounds of radix sorting.
- mattmaroon 2y ago
  Right, so basically by your ninth time doing this you’d have broken even (ish) on time. He was doing it every day so that’d be a great investment. It also would reduce the possibility of errors greatly I’d think.
  - Retric 2y ago
    100k bills doesn’t need an exact sort to be vastly faster. Day one you sort by first digit, then keep sorting matching digits stopping when you have say 20 numbers in a pile. My guess is you break even on day 2 and the first day is only slightly worse.
    - mattmaroon 2y ago
      That’s a good point, each individual sort probably takes only slightly longer than just looking through them for the number. So the actual sorting might not really add much time at all
- kragen 2y ago
  in a single round of digit-pair radix sorting, you can put 100 piles of ≈1000 bills each into 10×10 cubbyholes, a piece of furniture which is small enough to fit on a desk. then you need about 20 minutes to linearly search through one such pile when the dj announces a number, which is probably fast enough to win if you have a second cubbyhole array, when you linearly search through a pile chosen from the first cubbyhole array, you can radix-sort that pile by another two digits, dividing it into piles of ≈10 bills. those piles are small enough that you can keep them sorted as you build them without much loss of efficiency, even on a computer if you can fill the first array with 100 wallets with 10 numbered tabs each, like the tabbed dividers in a looseleaf notebook, you can divide the bills into 1000 piles on the first radix-sorting pass. in practice it might be too much work to find or make the wallets but i think the sad thing about michael larson's story is not that he didn't know enough about computer 'science' (or, i guess, library 'science'), but that he spent more effort searching for a hack that would make hard things easy than it would have taken to do them the hard way, destroying his personal relationships in the process

paxys 2y ago

Maybe, but even then I doubt the scheme was well thought out. He had 100,000 bills but the total number of serial numbers is many magnitudes greater than that. The chance that he'd actually have a hit was close to zero. And that is assuming the contest was legitimate in the first place.

npilk 2y ago
Seems like the classic form of this contest would be for the radio DJ to pull a bill out of his wallet and read that serial number over the air...
- CleanRoomClub 2y ago
  Haha this is what I was thinking. Did anyone ever actually win this prize?
- easton 2y ago
  IIRC serial numbers aren't unique. Even if the DJ was doing that, there would still be a chance. (albeit extremely small)
  - hiatus 2y ago
    > A unique combination of eleven numbers and letters appears twice on the front of the note. Each note has a unique serial number. The first letter of the serial number corresponds to the series year. https://www.uscurrency.gov/denominations/bank-note-identifiers https://www.uscurrency.gov/denominations/bank-note-identifie...
    - chungy 2y ago
      It's not the whole story. In genuine currency, serial numbers are only unique within a series. Series 2017A and series 2021 notes can (and in fact do, since they start over at A00000001A) have identical serial numbers.
      - deleted 2y ago

uses 2y ago

Yeah this part bothered me. It's surprising if they really didn't immediately realize randomly looking at single bills was an impossible strategy. Kind of an interesting problem. Complete sorting in a timely manner is basically not possible because of the physical reality of 100k pieces of paper. But maybe you can group the bills into 100 piles of "last 2 digits", so then for each lookup you "only" have to check 1000 bills. And then later, while searching a group, you can take the time to further sort them by the 3rd digit. I guess it also depends on how long you expect the contest to go on, i.e. how many lookups you will do. Even with the simplified grouping strategy, let's be generous and assume it takes you 3 seconds to look at a bill, figure out what to do with it, and physically move it to the correct place. That's still 83 person-hours to do a single pass and put the bills into 100 groups for quicker lookup. With 2 people, that's 5 full 8 hour days of non-stop sorting.

bluGill 2y ago
I would copy the serials onto paper in sorted order. Then I only need to find the bill after I know I have it. I'd still need to find the bill on demand - but you typically get 10 minutes to call and then days to prove it (this was the 1980s - you couldn't email a digital photo back then. Today I'd forge the digital photo and have hours to set the real one aside for when they check)
- nucleardog 2y ago
  This is more or less the way I’d go. It’s “what the client asked for” versus “what solves the client’s problem”. You don’t need to find the bill within minutes, you need to know that you _have_ the bill quickly. Grab a big binder, half dozen packs of dividers, a pack of loose leaf paper, and a box of pens. Divide the binder into ranges. In each range use a separate piece of paper for the next digit. Don’t worry about sorting past there, just write all your serial numbers down. Now you can use the dividers to narrow it down to around 2,000 bills. Flipping through ten pages to find the next digit you’ve narrowed it down to about 200 bills. You can probably scan two hundred numbers quickly enough.
scottyah 2y ago

supportengineer 2y ago

This reminds me of the old website, "Where's George?" Sample bill report: https://www.wheresgeorge.com/b:QZHjxdYnJ&entry=17 https://www.wheresgeorge.com/b:QZHjxdYnJ&entry=17

bsagdiyev 2y ago
I got one of those bills as change on NAVSTA Rota back in the early 2000s, it was neat to see the path it took.