Nuts and bolts - Programming contest

[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.)

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

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

[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:

[DRHuff]

Robertson is a screw. Not a bolt.

If you can't laugh at yourself - ask me and I will do it for you.

[DRHuff]

And how does the sort work since the problem states that you can’t compare nut to nut or bolt to bolt?

If you can't laugh at yourself - ask me and I will do it for you.

[DRHuff]

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.

[Lost User]

I think the "cannot compare" rule applies. Assume you have mittens on. You can't tell if the nut / bolt is bigger or smaller; only that it does or does not match.

It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it. ― Confucian Analects: Rules of Confucius about his food

[OriginalGriff]

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!

[realJSOP]

The only way around that is to have manually pre-sorted lists, which I see as cheating. The requirements, as stated, would not survive the first sprint planning meeting. I'm the only person that has presented code, so I guess I win the contest. And here's a version that doesn't sort (but it won't be included in the final product because I'm the project lead dev and the customer does not determine technique used in the code):

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

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