|
#realJSOP wrote: The type of head is irrelevant.
I'm unable to keep it KSS.
|
|
|
|
|
Robertson is a screw. Not a bolt.
If you can't laugh at yourself - ask me and I will do it for you.
|
|
|
|
|
First guess on an algorithm:
Grab a nut at random and test all bolts against it to form two piles "bigger than" and "smaller than" plus one bolt "same as".
Now use the matching bolt to do the same thing for all nuts to form two piles.
Process each pile the same way, to get 4 piles of nuts, 4 piles of bolts (and two matching pairs)
Repeat.
My gut feeling is that it'll be a lot quicker than a "brute force" compare all: it's kinda using QuickSort to match 'em up.
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
If you always go back and compare with the already-matched sets, I can see that.
|
|
|
|
|
Well, that would have been my method too.
Wrong is evil and must be defeated. - Jeff Ello
Never stop dreaming - Freddie Kruger
|
|
|
|
|
But I think the devil might be in the details here, how would you implement the collection?
Wrong is evil and must be defeated. - Jeff Ello
Never stop dreaming - Freddie Kruger
|
|
|
|
|
Binary tree, with two lists per node, probably - but it would likely depend on the language (and the size of N: it would probably be worth adding a test on that and brute-forcing low values as the memory allocations wouldn't be that cheap in time terms). An assembler solution wouldn't look anything like a C# implementation!
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Binary tree maybe, I was thinking of an ordered List and a binary search.
|
|
|
|
|
My first thought too. Somewhere I have a book describing the historical development of heapsort, and I suspect a lot of the nuts and bolts could be found there (awful pun intended).
[edit] On refection, and now with a measurable caffeine content, bits of Quicksort may be more relevant. Pivoting... [/edit]
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
modified 28-Dec-20 17:57pm.
|
|
|
|
|
Is there an implied constraint to stop testing once a nut and bolt match? In that case you have 3 piles (usually) at the end of the first sort. Big small and untested.
If you can't laugh at yourself - ask me and I will do it for you.
modified 29-Dec-20 1:27am.
|
|
|
|
|
No, you test the whole pile and each becomes two piles and a match.
But since that means each pile is smaller than the source pile you end up with considerably less comparisons in total.
If I remember Big O notation correctly - and it's been 40 years since I last had to - it's something like O(n2) vs O(n * log(n))
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
O(n * log(n)) would be an average, if you consistently select the wrong pivot you might end up with O(n2)
It isn't just about the number of comparisons though, the number of swaps is also important
Wrong is evil and must be defeated. - Jeff Ello
Never stop dreaming - Freddie Kruger
|
|
|
|
|
Why would there be any swaps?
|
|
|
|
|
If you're sorting something you need to swap elements in the collection, right?
Wrong is evil and must be defeated. - Jeff Ello
Never stop dreaming - Freddie Kruger
|
|
|
|
|
No. And it's not sorting either.
More like inserting into a sorted list -- at least that's what I'm doing.
|
|
|
|
|
Ah, but I was referring to Griffs original comment:
Griff wrote: it's kinda using QuickSort to match 'em up.
That would most probably use swapping of elements, and that's where quicksort is excelling by doing fewer of them than most sorting algorithms.
Wrong is evil and must be defeated. - Jeff Ello
Never stop dreaming - Freddie Kruger
|
|
|
|
|
True, but this particular challenge doesn't require sorting or swapping.
And at one point I thought he was talking about inserting to a binary tree.
|
|
|
|
|
I'm looking forward to see your solution
Wrong is evil and must be defeated. - Jeff Ello
Never stop dreaming - Freddie Kruger
|
|
|
|
|
Just refactoring, reordering methods now, trying to make it at least a little more understandable.
Last night I tried making a big change, but it didn't work.
The thing is, it wound up being more code than I expected -- a bunch of classes to support a fairly simple algorithm.
|
|
|
|
|
|
|
But, that is the answer to everything!
|
|
|
|
|
Are nuts metric?
If you can keep your head while those about you are losing theirs, perhaps you don't understand the situation.
|
|
|
|
|
Only Cash-ews.
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|