Nuts and bolts - Programming contest

PIEBALDconsult

I'll post mine later. After viewing it with fresh eyes this morning. P.S. I have an idea for a change to mine, so maybe I'll have it ready tonight.

Harrison Pratt

Something like this, using Visual Prolog:

class predicates
match : (integer_list NutSizes, integer_list BoltSizes, integer_list CurrentMatches) -> integer_list SizesMatched.
clauses
match([], [], RevMM) = list::reverse(RevMM) :-
!.
match(NN, BB, CurrMM) = MM :-
N in NN,
B in BB,
N = B,
!,
UnatchedNN = list::remove(NN, N),
UnatchedBB = list::remove(BB, N),
write("\nUnmatched Nuts: ", NN),
write("\nUnmatched Bolts: ", BB),
write("\nCurrent matches: ", [N | CurrMM]),
MM = match(UnatchedNN, UnatchedBB, [N | CurrMM]).
match(_, _, _) = [] :-
exception::raise_error("Input lists contain an unmatched item or list lengths are unequal.").

realJSOP

BTW, my sort version doesn't directly compare two nuts or two bolts. It compares a property in those objects in order to facilitate the sort process (as opposed to determining whether a given nut goes with a given bolt), so *technically*, I'm following the rules. Furthermore, I'm not matching a nut to a bolt via any kind of comparison. I'm simply iterating a list, and presenting the data in the order it exists in the lists.

".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

Harrison Pratt

And if you want to elaborate and analyze the Nuts and Bolts as structures:

domains
itemDOM = item(integer ID, integer Size).

class predicates
matchItems : (itemDOM* Nuts, itemDOM* Bolts, tuple{itemDOM Nut, itemDOM Bolt}*) -> tuple{itemDom Nut, itemDOM BoltID}*.
clauses
matchItems([], [], RevMM) = list::reverse(RevMM) :-
!.
matchItems(NN, BB, CurrItems) = MM :-
item(IdN, SizeN) in NN,
item(IdB, SizeB) in BB,
SizeN = SizeB,
!,
UnmatchedNN = list::remove(NN, item(IdN, SizeN)),
UnmatchedBB = list::remove(BB, item(IdB, SizeB)),
MM = matchItems(UnmatchedNN, UnmatchedBB, [tuple(item(IdN, SizeN), item(IdB, SizeB)) | CurrItems]).
matchItems(_, _, _) = [] :-
exception::raise_error("Input lists contain an unmatched item or list lengths are unequal.").

And invoke the matching like this:

clauses
run() :-
write("\n\n", "Testing", "\n\n"),
IDs = mkList(5, []), % create a list of 5 random integers
NutItems = [ item(ID, ID * 100) || ID in IDS ], % set sizes to be 5 X the ID
BoltItems = [ item(ID + 300, Size) || item(ID, Size) in NutItems ], % set Bolt IDs to 300 greater than Nut IDs
MM = matchItems(NutItems, BoltItems, []),
write(MM),
write("\nPress [Enter] to exit"),
_ = readLine(),
!.

PIEBALDconsult

Yeah, I think you're cheating. :-D The nuts and bolts should be presented in random order.

Member_5893260

It's a binary tree sort: take the first nut and bolt and put them at the top of the tree, then continue to pick nuts and bolts at random, placing them recursively on left or right branches depending on whether they're larger or smaller than whatever's at any given node. Something like that. Matching nuts and bolts stay together. By the time you've tried all of them, they'll all have a match.

PIEBALDconsult

Why would there be any swaps?

Kirk 10389821

So, if I have this right. I can tell if a Bolt+NUT is Bigger OR FITS or "not" meaning it is clearly smaller. The simplest algorithm is a bubble sort type loop/loop (O(n^2)).

// Z = Number of nuts/bolts, N[1..Z], B[1..Z] hold the nuts/bots

For X = 1 to Z
For Y = 1 to Z
If Fits(B[X],N[Y]) then F[X]=Y : Break;
Next Y
Next X

For X = 1 to Z
Print "Bolt " & X & " Fits with Nut " & F[X]
Next X

// Accepting that if the output is all that is needed, do the print in the main loop, before the break;

for 0 or something to skip it if assigned

// No optimizations here. But short, clear, concise.
// Simplest optimization is to process the second loop in reverse, deleting an element as it is matched

// The list of Nuts will shrink by one with each pass, cutting the comparisons in half.
// Unfortunately requires a modifiable array.

For X = 1 to Z
For Y = Length(N) to 1 Step -1
If Fits(B[X],N[Y]) then F[X]=Y : N.delete(Y) : Break;
Next Y
Next X

Jorgen Andersson

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

PIEBALDconsult

No. And it's not sorting either. More like inserting into a sorted list -- at least that's what I'm doing.

James Lonero

Assuming a mixed pile of nuts and bolts where 1. Each nut matches exactly one bolt. 2. Must fit a nut and bolt together to compare “which is bigger” (size) 3. Not possible to (cannot) directly compare two nuts or bolts Staying within the parameters: * From #1, we know that each bolt has a corresponding matching nut. Then the matching bolt and nut are eliminated from further searches. * From #2, ‘bigger’ assumes size. Not head configuration, pitch, left or right-handed, or composition. Also, since we need to fit the nut onto the bolt, we are only concerned about the width/diameter (of the bolt and nut) and not the length. * From #3, we cannot compare the nuts or the bolts therefore, we are not allowed to sort them. (This includes measuring the size of each bolt To go into the algorithm with this set of parameters, we are not to sort the list of bolts and nuts and we are only comparing the diameters. So, we know that we have a set of N nuts to match up with a similar number of bolts. Here is a simple algorithm:

int boltDiameters[n] // Resizable array
int nutDiameters[n] // Resizable array

do {
boltsize = boltDiameters[0]
for (int i = 0; i < nutDiameters.Length; i++) {
if (nutDiameters[i] == boltsize) {
println(“Found nut-bolt with size of: “ + boltsize)
nutDiameters.RemoveAt(i)
boltDiameters.RemoveAt(0)
}
}
} Until (boltDiameters.Length == 0)

Each iteration through the loop, we reduce the arrays by one element. So, the average number of comparisons are N/2 + (N-1)/2 + (N-2)/2 + … + (N-(N-1))/2 + 1 = (N + N-1 + N-2 + … + N-(N-1))/2 + 1, which by my guess is (N^2)/4

Jorgen Andersson

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

PIEBALDconsult

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.

Jorgen Andersson

I'm looking forward to see your solution

Wrong is evil and must be defeated. - Jeff Ello Never stop dreaming - Freddie Kruger

realJSOP

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

PIEBALDconsult

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.

PIEBALDconsult

I think it's implied. You're handed a bag of nuts and a bag of bolts and you have to match them up.

Jorgen Andersson

"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

PIEBALDconsult

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

PIEBALDconsult

Posted.