Nuts and bolts - Programming contest
-
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
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 }; -
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#realJSOP wrote:
The type of head is irrelevant.
I'm unable to keep it KSS. :sigh:
-
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
-
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 }; -
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!
-
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!
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
-
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.
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!
-
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 -
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
Can I bribe you by sending a box of matching nuts and bolts of your choice?
"The only place where Success comes before Work is in the dictionary." Vidal Sassoon, 1928 - 2012
-
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!
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
-
42
But, that is the answer to everything!
-
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
I'm going to be bold and say you're a nut :D
Best, Sander Azure DevOps Succinctly (free eBook) Azure Serverless Succinctly (free eBook) Migrating Apps to the Cloud with Azure arrgh.js - Bringing LINQ to JavaScript
-
Are nuts metric?
If you can keep your head while those about you are losing theirs, perhaps you don't understand the situation.
I believe that the official scale is neither metric nor imperial. Say you found yourself in a urologists' office with your pants down being told you had a tumor on old lefty and that it has to come out pronto. If this happened to you in Australia about 10 years ago the doctor would likely tell you that the government has a program offering free prosthetics and that he can whack in a replacement at the same time since he'll already have his hand in your scrotum. If you accepted this generous offer he would pull out something which looks a lot like a circle template a draftsman would of used many years ago to determine the appropriate size replacement. In a pretty dark day being told that you're a medium large in bollocks is a real highlight.
-
Are nuts metric?
If you can keep your head while those about you are losing theirs, perhaps you don't understand the situation.
I believe that the official scale is neither metric nor imperial. Say you found yourself in a urologists' office with your pants down being told you had a tumor on old lefty and that it has to come out pronto. If this happened to you in Australia about 10 years ago the doctor would likely tell you that the government has a program offering free prosthetics and that he can whack in a replacement at the same time since he'll already have his hand in your scrotum. If you accepted this generous offer he would pull out something which looks a lot like a circle template a draftsman would of used many years ago to determine the appropriate size replacement. In a pretty dark day being told that you're a medium large in bollocks is a real highlight.
-
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 -
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
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."). -
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.
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 -
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.").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(),
!. -
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 -
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
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.
