Nuts and bolts - Programming contest
-
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.
-
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
-
Yeah, I think you're cheating. :-D The nuts and bolts should be presented in random order.
That wasn't stated as a requirement, however I did create a random collection of each. My example also assumes that there will only be one occurrence of each diameter and pitch, but changing that will only affect the sort comparison method, which everyone seems to think is not valid.
".45 ACP - because shooting twice is just silly" - JSOP, 2010
-----
You can never have too much ammo - unless you're swimming, or on fire. - JSOP, 2010
-----
When you pry the gun from my cold dead hands, be careful - the barrel will be very hot. - JSOP, 2013 -
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.
-
That wasn't stated as a requirement, however I did create a random collection of each. My example also assumes that there will only be one occurrence of each diameter and pitch, but changing that will only affect the sort comparison method, which everyone seems to think is not valid.
".45 ACP - because shooting twice is just silly" - JSOP, 2010
-----
You can never have too much ammo - unless you're swimming, or on fire. - JSOP, 2010
-----
When you pry the gun from my cold dead hands, be careful - the barrel will be very hot. - JSOP, 2013I think it's implied. You're handed a bag of nuts and a bag of bolts and you have to match them up.
-
That wasn't stated as a requirement, however I did create a random collection of each. My example also assumes that there will only be one occurrence of each diameter and pitch, but changing that will only affect the sort comparison method, which everyone seems to think is not valid.
".45 ACP - because shooting twice is just silly" - JSOP, 2010
-----
You can never have too much ammo - unless you're swimming, or on fire. - JSOP, 2010
-----
When you pry the gun from my cold dead hands, be careful - the barrel will be very hot. - JSOP, 2013"You have a mixed pile of N nuts and N bolts" Also: "But it is not possible to directly compare two nuts or two bolts", so yes, it affects the comparison method quite a bit. But I really enjoy reading how you "renegotiate" the "rules". :-D
Wrong is evil and must be defeated. - Jeff Ello Never stop dreaming - Freddie Kruger
-
How about a little programming puzzle for the Holiday? I found this puzzle in a text by G. J. E. Rawlins. "You have a mixed pile of N nuts and N bolts and need to quickly find the corresponding pairs of nuts and bolts. Each nut matches exactly one bolt, and each bolt matches exactly one nut. By fitting a nut and bolt together, you can see which is bigger. But it is not possible to directly compare two nuts or two bolts." Selecting the winner will be heavily influenced by upvotes and Reactions™ :)
Wrong is evil and must be defeated. - Jeff Ello Never stop dreaming - Freddie Kruger
The algorithm I chose isn't all that complex and the code is fairly simple. It does rely on a number of classes, though, so there's a bit of code. I would not assign the implementation during an interview, but having a candidate describe the algorithm could be OK.
Algorithm:
I assume that separating the "pile of N nuts and N bolts" into a pile of nuts and a pile of bolts is allowed.
I wrote a Nut class and a Bolt class (both deriving from a Base class).
I wrote a NutList class and a BoltList class (both deriving from a BaseList class).
These hold a "pile" of Nuts or Bolts.
The lists can be Shuffled to simulate drawing one item at random, as you would from an actual pile.
If you were actually performing this task (during an interview perhaps), you might have some divided disposable plates on hand.
One common type of disposable plate for low-class dinner parties has a large section and two small sections.
I wrote a Tray class to represent this; it can hold one Nut, one Bolt, and one NutList (pile of Nuts).Diagram of a Tray:
__________________________
| |
| |
| Pile of unmatched Nuts |
| |
|________________________|
| | |
| Matched | Matched |
| Nut | Bolt |
|____________|___________|You could use a number of these disposable plates -- one for each nut-and-bolt you have matched up and that subset of the Nuts which are "larger" than them.
I wrote a TrayList class to hold an ordered list of Trays.
A TrayList begins with one item, containing a "null" nut-and-bolt, which is guaranteed to test "smaller" than all other Nuts and Bolts.- Begin with a pile of all of the Nuts on the "null" Tray and a pile of all the of Bolts.
- Draw one Bolt from the pile of Bolts.
- Beginning with the "null" Tray, compare the Bolt with the (matched) Nuts on the Trays in front of you.
2.1) When you reach the end of the Trays or a Tray with a "larger" Nut, that's where you want to insert a new Tray for this Bolt. - Create a new Tray, put the Bolt on it, shift any "larger" Trays to the right, and insert the new Tray.
- Test each Nut in the pile of (unmatched) Nuts on the Tray to the left of the new Tray against the Bolt.
4.1) Any Nuts which are "larger" than the Bolt get moved to the new Tray's pile of (unmatched) Nuts.
4.2) When you find the Nut which matches the Bolt, move it to the Tray.
4.3) Any Nuts which are "smaller" than the Bolt remain where they
-
I'm looking forward to see your solution
Wrong is evil and must be defeated. - Jeff Ello Never stop dreaming - Freddie Kruger
Posted.
-
"You have a mixed pile of N nuts and N bolts" Also: "But it is not possible to directly compare two nuts or two bolts", so yes, it affects the comparison method quite a bit. But I really enjoy reading how you "renegotiate" the "rules". :-D
Wrong is evil and must be defeated. - Jeff Ello Never stop dreaming - Freddie Kruger
: cough : .45 cal : cough :
-
How about a little programming puzzle for the Holiday? I found this puzzle in a text by G. J. E. Rawlins. "You have a mixed pile of N nuts and N bolts and need to quickly find the corresponding pairs of nuts and bolts. Each nut matches exactly one bolt, and each bolt matches exactly one nut. By fitting a nut and bolt together, you can see which is bigger. But it is not possible to directly compare two nuts or two bolts." Selecting the winner will be heavily influenced by upvotes and Reactions™ :)
Wrong is evil and must be defeated. - Jeff Ello Never stop dreaming - Freddie Kruger
Test Data For nuts 1 7 4 2 3 5 4 9 8 For bolts 6 4 9 7 8 1 2 3 4 Does it meet the specifications. No, but then real data almost never is as the user said it would be. There are 2 matching 4s and one has an unmatched 5 the other an unmatched 6. Good data in > good data out Garbage in > report errors and depending on the situation quit or process what you can.
-
Test Data For nuts 1 7 4 2 3 5 4 9 8 For bolts 6 4 9 7 8 1 2 3 4 Does it meet the specifications. No, but then real data almost never is as the user said it would be. There are 2 matching 4s and one has an unmatched 5 the other an unmatched 6. Good data in > good data out Garbage in > report errors and depending on the situation quit or process what you can.
Yeah, I should review mine to see what happens with unmatched items, but I don't think it will cause trouble. I know mine won't handle duplicates, but I could easily change it so that it does. Still, not required by the spec.
