|
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!
|
|
|
|
|
|
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!
"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!
|
|
|
|
|
|
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.
|
|
|
|
|
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)
{
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}
public class Part : IComparable<Part>
{
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);
}
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<Part>
{
public Parts(bool populate=true)
{
if (populate)
{
List<int> diameters = new List<int>(){ 1, 2, 3, 4, 5, 6, 7, 8, 9,10 };
List<int> pitches = new List<int>(){ 11,12,13,14,15,16,17,18,19,20 };
Random diaRandom = new Random(1);
Random pitRandom = new Random(3);
int diaIndex;
int pitIndex;
int id = 0;
do
{
diaIndex = diaRandom.Next(0, diameters.Count-1);
pitIndex = pitRandom.Next(0, pitches.Count-1);
this.Add(new Part(id, diameters[diaIndex], pitches[pitIndex], HardwareType.NUT));
diameters.RemoveAt(diaIndex);
pitches.RemoveAt(pitIndex);
id++;
} while (diameters.Count > 1);
this.Add(new Part(id, diameters[0], pitches[0], HardwareType.NUT));
diameters.RemoveAt(0);
pitches.RemoveAt(0);
}
}
public Parts(Parts parts)
{
Parts cloned = new Parts(false);
cloned.AddRange(new List<Part>(parts));
Random random = new Random();
int index;
int id = 0;
do
{
index = random.Next(0,cloned.Count-1);
this.Add(new Part(id, cloned[index].Diameter, cloned[index].Pitch, HardwareType.BOLT));
cloned.RemoveAt(index);
id++;
} while (cloned.Count > 1);
this.Add(new Part(id, cloned[0].Diameter, cloned[0].Pitch, HardwareType.BOLT));
cloned.RemoveAt(0);
}
}
}
".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
modified 28-Dec-20 18:13pm.
|
|
|
|
|
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.
|
|
|
|
|
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
modified 29-Dec-20 2:45am.
|
|
|
|
|
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.
modified 29-Dec-20 12:09pm.
|
|
|
|
|
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
|
|
|
|
|
Yeah, I think you're cheating.
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 think it's implied. You're handed a bag of nuts and a bag of bolts and you have to match them up.
|
|
|
|
|