Nuts and bolts - Programming contest

Jorgen Andersson

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

PIEBALDconsult

I'd be interested in seeing the test data set. :-D But more importantly, I'd like a more detailed spec. Are there both left- and right- handed nuts and bolts? Are there nuts and bolts with the same diameter but different pitch (or whatever)? Are there nuts and bolts with incompatible composition? (E.g. leading to electrolysis or similar?)

OriginalGriff

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!

PIEBALDconsult

If you always go back and compare with the already-matched sets, I can see that.

Jorgen Andersson

Well, that would have been my method too.

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

Jorgen Andersson

Whitworth or metric. How about cap or flange? Do we care about hex bolts or Phillips? (Or Robertson for the Canadians)

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

Jorgen Andersson

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

OriginalGriff

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! :laugh:

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

Slacker007

42

theoldfool

Are nuts metric?

If you can keep your head while those about you are losing theirs, perhaps you don't understand the situation.

PIEBALDconsult

Binary tree maybe, I was thinking of an ordered List and a binary search.

OriginalGriff

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!

PIEBALDconsult

Mine aren't.

PIEBALDconsult

(Cashews are seeds.)

OriginalGriff

Most nuts are seeds. As Brian O'Driscoll said: "Knowledge is knowing that a tomato is a fruit. Wisdom is knowing not to put it in a fruit salad." Cashews are still good in a stir fry or curry! :laugh:

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

theoldfool

These programming contests are difficult. I think I will go to QA and ask for the codez.

If you can keep your head while those about you are losing theirs, perhaps you don't understand the situation.

realJSOP

the only thing that matters in terms of "matching are pitch and diameter. The type of head is irrelevant.

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

Peter_in_2780

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

realJSOP

Most of the work was getting the collections of nuts and bolts built. This code builds a collection of 10 nuts with randomly selected diameter and pitch, and then builds a random list of bolts from the list of nuts. These collections assume that each nut with have a unique diameter and pitch combination, and that each nut as a matching bolt. Finally, I simply sort both lists on diameter, and present the pairs by iterating the nuts list (without doing any comparison for diameter and pitch).

using System;
using System.Collections.Generic;

namespace ConsoleApp3
{
class Program
{
static void Main(string[] args)
{
// prep the data
Parts nuts = new Parts();
Parts bolts = new Parts(nuts);

        nuts.Sort();
        bolts.Sort();

        foreach(Part nut in nuts)
        {
            Part bolt = bolts\[nuts.IndexOf(nut)\];
            Console.WriteLine("Pair: \[{0}\] - \[{1}\]", nut, bolt);
        }
        Console.ReadKey();
    }
}

public enum HardwareType { BOLT=0, NUT}

/// The "part" (all parts have a hardware type, a diameter and pitch)
public class Part : IComparable
{
    public HardwareType Hardware { get; set; }
    public int ItemID { get; set; }
    public int Diameter { get; set; }
    public int Pitch { get; set; }
    public Part(int itemID, int diameter, int pitch, HardwareType hardware)
    {
        this.ItemID   = itemID;
        this.Diameter = diameter;
        this.Pitch    = pitch;
        this.Hardware = hardware;
    }

    public int CompareTo(Part p)
    {
        return this.Diameter.CompareTo(p.Diameter);
    }

    // make it more convenient to look at in the debugger
    public override string ToString()
    {
        return string.Format("{0}, ID={1}, D={2}, P={3}", this.Hardware.ToString(), this.ItemID, this.Diameter, this.Pitch);
    }
}

public class Parts : List
{
    // This constructor builds a collection of nuts
    public Parts(bool populate=true)
    {
        if (populate)
        {
            // create a list of "part"s with randomly selected combinations of diameter and pitch
            List diameters = new List(){  1, 2, 3, 4, 5, 6, 7, 8, 9,10 };
            List pitches   = new List(){ 11,12,13,14,15,16,17,18,19,20 };

PIEBALDconsult

#realJSOP wrote:

The type of head is irrelevant.

I'm unable to keep it KSS. :sigh: