3 ms·
Kind of like the “uncooked spaghetti length” sorting algorithm: gravity. Hold them in your fist vertically, let them gently fall to a flat surface. Sorted.
by semireg 3mo ago
Kind of like the “uncooked spaghetti length” sorting algorithm: gravity. Hold them in your fist vertically, let them gently fall to a flat surface. Sorted.
- BretonForearm 3mo agoSpaghetti length is made visible (quickly comparable), but it's still not sorted.
- King-Aaron 3mo agoIt is sorted chronologically
- AlotOfReading 3mo agoDropping spaghetti is an O(1) operation. Once that's done there's a straightforward O(N) sort by removing noodles in the order that they're intersected by horizontal plane descending from max_noodle_length to the table.
- AndrewDucker 3mo agoAssuming that the spaghetti is being held in such a way that longer pieces hit the surface first. If the pieces are being held at random points, or such that the bottoms line up rather than the tops, then this approach won't work.
- AlotOfReading 3mo agoYou don't have to assume that. We can take each randomly oriented noodle and orient it correctly in O(1) as a preprocessing step. Since the complexity would be additive, the overall complexity remains O(N).