News for hackers. Stuff that matters.
Re:Locating the Source of a Mysterious Beep by tristanj on Monday November 09, 2026 @09:05PM (#50435186)
You can also solve this in O(logn) using a physical binary search:

1) Move half the boxes to another room.

2) Listen for a beep and determine which room the beep comes from.

3) Take the boxes in that room and split it in half again.

4) Repeat until one box is left.

Re:Locating the Source of a Mysterious Beep by ARandomerDude on Monday November 09, 2026 @09:13PM (#50435251)
> Move half the boxes to another room.

Alternatively, no.

Re:Locating the Source of a Mysterious Beep by malfist on Monday November 09, 2026 @10:18PM (#50435650)
Alternatively, you can unpack
Re:Locating the Source of a Mysterious Beep by tunapizza on Tuesday November 10, 2026 @12:25AM (#50436417)
Came here to say this.
Re:Locating the Source of a Mysterious Beep by growse on Tuesday November 10, 2026 @01:35AM (#50436825)
Who's got that kind of time?
Re:Locating the Source of a Mysterious Beep by justsomehnguy on Tuesday November 10, 2026 @01:44AM (#50436871)
Yes, if you still didn't unpacked it when you don't need it.
Re:Locating the Source of a Mysterious Beep by yjftsjthsd-h on Tuesday November 10, 2026 @02:09AM (#50437034)
I am confident that inventing a new networked sound locating system is far easier than that.
Re:Locating the Source of a Mysterious Beep by bluescrn on Tuesday November 10, 2026 @02:59AM (#50437381)
More interesting for sure
Re:Locating the Source of a Mysterious Beep by entropie on Monday November 09, 2026 @10:15PM (#50435632)
Or you could use a very heavy blanked to just cover some boxes to supress the sound enough to simulate moving boxes.
Re:Locating the Source of a Mysterious Beep by aizk on Monday November 09, 2026 @10:35PM (#50435750)
It's O(logn) but you haven't accounted for how heavy each item in the array of n is.
Re:Locating the Source of a Mysterious Beep by tonyarkles on Monday November 09, 2026 @11:04PM (#50435927)
Lol classic “ignore the constant factor” gotcha when using Big-O.
Re:Locating the Source of a Mysterious Beep by aizk on Tuesday November 10, 2026 @02:15PM (#50444859)
This is a pretty good real world example to show off how O(n) can't always tell the full story.
Re:Locating the Source of a Mysterious Beep by mauvehaus on Monday November 09, 2026 @11:06PM (#50435939)
This is true, but it probably isn't a box of books that's beeping.

I also feel like ordering the moves by lightest box first is reasonable as a real-world optimization.

Re:Locating the Source of a Mysterious Beep by Spare_account on Tuesday November 10, 2026 @05:15AM (#50438240)
Typically, the heavy boxes are at the bottom too; to some extent, the piles will already be sorted by weight.
Re:Locating the Source of a Mysterious Beep by kelseyfrog on Monday November 09, 2026 @11:34PM (#50436098)
If you randomly index them and there's enough of them then on average the partitions average out.
Re:Locating the Source of a Mysterious Beep by StilesCrisis on Tuesday November 10, 2026 @07:55AM (#50439662)
You can just move the lightest half of the boxes each time.
Re:Locating the Source of a Mysterious Beep by dolmen on Tuesday November 10, 2026 @10:23AM (#50441681)
A few additional constraints:

  - the boxes are stacked
  - the heavy boxes are at the bottom of a stack, and you can't stack a heavy box on top of a light one
  - boxes aren't the same size
  - some boxes are open, so must be put on top
  - storage space and height are limited
Re:Locating the Source of a Mysterious Beep by bombcar on Tuesday November 10, 2026 @11:05AM (#50442288)
Some boxes contain a wolf, some a sheep, and some a cabbage; the sheep and the wolf cannot be left together, nor the cabbage and the sheep.
Re:Locating the Source of a Mysterious Beep by peri-cl on Monday November 09, 2026 @11:14PM (#50435994)
Yes, but that's also O(log n) physical effort. This one's O(1) sitting on your butt.

(Solely for entertainment purposes: I think "physical binary search" is more properly O(n^{1/3} log(n)), or maybe O(n^{1/2} log(n)). Because real objects have sizes, and moving things (or moving between things) takes time proportional to distance).

Re:Locating the Source of a Mysterious Beep by akoboldfrying on Tuesday November 10, 2026 @12:02AM (#50436271)
Good point about the moving effort required. But if moving an object takes constant time, then it's O(n) overall -- since even though there are O(log n) steps, among all n-1 non-beeping items, either (i) all are moved exactly once (this case occurs when the beeping item is not moved during the initial halving) or (ii) half are never moved and the other half are moved exactly twice for O(2 * n/2) = O(n) work, and this term dominates the log n term.
Re:Locating the Source of a Mysterious Beep by peri-cl on Tuesday November 10, 2026 @12:28AM (#50436440)
Yeah, that interpretation is more realistic!

O(log n) is if you can split the collection in half in an O(1) step, like, *shoving* the whole pile together as a unit

O(n) if you're moving items one at a time. So, splitting the pile in half is O(n)

O(n^{3/2}) if the project is growing out of control and walking distances start to matter

O(n^{4/3}) if that, but somehow it's taking place in 3-dimensions

Re:Locating the Source of a Mysterious Beep by MisterMunchkin on Tuesday November 10, 2026 @01:15AM (#50436712)
It’s not sitting on your butt if you have to code an entire system and set up notes throughout the house and monitor them.
Re:Locating the Source of a Mysterious Beep by pyrolistical on Monday November 09, 2026 @11:23PM (#50436038)
That requires you to stand in the room and listen for which side. So it’s nlogn times a very long time constant
Re:Locating the Source of a Mysterious Beep by globular-toast on Tuesday November 10, 2026 @01:30AM (#50436795)
You could also solve it by getting rid of the boxes of stuff you clearly don't need (if you needed it, it wouldn't still be in a box). The best way to solve a problem is to make the problem go away.
Re:Locating the Source of a Mysterious Beep by QuantumNomad_ on Tuesday November 10, 2026 @02:28AM (#50437178)
> if you needed it, it wouldn't still be in a box

I like to keep a lot of things in storage, and sometimes go through my boxes and “rediscover” things I haven’t used in a while.

Sure I have a lot of things I never use also. Some things I could sell, and some things I could give away, and some things I could throw away.

But just because a lot of things are in boxes, doesn’t mean that I might as well get rid of all of it for that reason alone.

Re:Locating the Source of a Mysterious Beep by jeffrallen on Tuesday November 10, 2026 @02:34AM (#50437208)
[delayed]
Re:Locating the Source of a Mysterious Beep by Spare_account on Tuesday November 10, 2026 @05:17AM (#50438248)
This has got me thinking, I wonder how many garbage trucks are beeping right now.

And the piles of rubbish at the landfill are probably beeping too.

Re:Locating the Source of a Mysterious Beep by AnneTrotter on Tuesday November 10, 2026 @05:55AM (#50438539)
What a horrifying thought.
Re:Locating the Source of a Mysterious Beep by tourmalinetaco on Tuesday November 10, 2026 @03:30AM (#50437562)
That was my proposed solution to finding something just today; it didn’t work, but one of the bags ended up containing an old contract from General Development Company. Apparently a late family member had been buying some land down there through them, but county appraisers showed that the land never changed hands until after GDC’s bankruptcy. Not even their kid had heard about this, so it really makes me wonder what the story was behind that considering they lived in the Midwest (but did have some relatives nearby in Florida).
Re:Locating the Source of a Mysterious Beep by bajard on Tuesday November 10, 2026 @04:49AM (#50438076)
You are moving n objects log(n) times, so its O(n.log(n))
Re:Locating the Source of a Mysterious Beep by wky on Tuesday November 10, 2026 @10:03AM (#50441390)
Only half of the remaining boxes need to be moved, not half of the total.
Re:Locating the Source of a Mysterious Beep by nukanse on Tuesday November 10, 2026 @12:49PM (#50443647)
You move n/2, then n/4,...n/2^-i

n. Sum(2^-i)=n

So its o(n. Log(n))

Re:Locating the Source of a Mysterious Beep by bajard on Wednesday November 11, 2026 @05:55AM (#50451942)
Actually,

sum_{i=1}^{log_2(n)} {(n/2^i)} = n - 1

So it's O(n).

Re:Locating the Source of a Mysterious Beep by cannonpalms on Tuesday November 10, 2026 @07:29AM (#50439383)
Never ignore the constant factor.
Re:Locating the Source of a Mysterious Beep by wky on Tuesday November 10, 2026 @10:02AM (#50441368)
In terms of physical effort taken it’s O(n). Move half, then a quarter, then one eighth, etc.

The number of partitions doesn’t matter either, the most straightforward case is the beeping box always being in the original room, so regardless of strategy you move n-1 boxes to narrow it down, and by symmetry it doesn’t matter which room beeps.

Re:Locating the Source of a Mysterious Beep by BobBagwill on Tuesday November 10, 2026 @10:23AM (#50441691)
You just look in the last box first, duh.
Re:Locating the Source of a Mysterious Beep by tim333 on Tuesday November 10, 2026 @04:43PM (#50446724)
I did roughly that to find my mum's missing hearing aid the other day. The bluetooth would locate which room it was in but not much more detailed than that. It was stuck to some orange peel in a recycling bin.
Re:Locating the Source of a Mysterious Beep by pseudohadamard on Tuesday November 10, 2026 @11:31PM (#50449760)
Close the door of the room the boxes are in.

I'll see myself out...