|
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.
|
|
|
|
|
"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".
Wrong is evil and must be defeated. - Jeff Ello
Never stop dreaming - Freddie Kruger
|
|
|
|
|
: cough : .45 cal : cough :
|
|
|
|
|
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
|
|
|
|
|
I'm going to be bold and say you're a nut
|
|
|
|
|
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(),
!.
|
|
|
|
|
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.
|
|
|
|
|
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;
// If "Fits()" is an expensive function, then pre-check F[X] 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
|
|
|
|
|
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]
int nutDiameters[n]
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
|
|
|
|
|
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.
0) Begin with a pile of all of the Nuts on the "null" Tray and a pile of all the of Bolts.
1) Draw one Bolt from the pile of Bolts.
2) 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.
3) Create a new Tray, put the Bolt on it, shift any "larger" Trays to the right, and insert the new Tray.
4) 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 are.
5) If there are more Bolts to match, repeat from 1)
6) Done.
For this implementation, in place of the "size" of a Nut or a Bolt, I use the index of them in the input array, but this should prove equivalent.
These are guaranteed to be unique, non-negative integers and allows for matching more complex items. It also allows duplicates if the user wishes.
namespace PIEBALD
{
public static partial class Tester
{
public static int
Main
(
string[] args
)
{
int result = 0 ;
System.Collections.Generic.IList<NutAndBolt.Pair> list = NutAndBolt.Run ( args ) ;
for ( int i = 0 ; i < list.Count ; i++ )
{
System.Console.WriteLine
(
"{0,2} : {1}"
,
i
,
list [ i ]
) ;
}
return ( result ) ;
}
}
public static partial class NutAndBolt
{
public sealed partial class Pair
{
public Nut Nut { get ; private set ; }
public Bolt Bolt { get ; private set ; }
public Pair
(
Nut Nut
,
Bolt Bolt
)
{
if ( Nut.CompareTo ( Bolt ) != 0 )
{
throw ( new System.Exception ( "" ) ) ;
}
this.Nut = Nut ;
this.Bolt = Bolt ;
return ;
}
public override string
ToString
(
)
{
return ( System.String.Format
(
"{0} Nut and {1} Bolt"
,
this.Nut.Description
,
this.Bolt.Description
) ) ;
}
}
public static System.Collections.Generic.IList<Pair>
Run
(
params string[] Description
)
{
System.Collections.Generic.List<Pair> result =
new System.Collections.Generic.List<Pair> ( Description.Length ) ;
BoltList boltlist = new BoltList ( Description.Length ) ;
TrayList traylist = new TrayList ( Description.Length ) ;
NutList nutlist = traylist [ 0 ].NutList ;
for ( int i = 0 ; i < Description.Length ; i++ )
{
nutlist.Add ( new Nut ( i , Description [ i ] ) ) ;
boltlist.Add ( new Bolt ( i , Description [ i ] ) ) ;
}
nutlist.Shuffle() ;
boltlist.Shuffle() ;
Resolve ( traylist , boltlist ) ;
for ( int i = 1 ; i < traylist.Count ; i++ )
{
result.Add ( new Pair ( traylist [ i ].Nut , traylist [ i ].Bolt ) ) ;
}
return ( result.AsReadOnly() ) ;
}
private static int
Resolve
(
TrayList TrayList
,
BoltList BoltList
)
{
for ( int b = BoltList.Count - 1 ; b >= 0 ; b-- )
{
int t = TrayList.Insert ( BoltList [ b ] ) ;
Tray tray = TrayList [ t ] ;
NutList nutlist = TrayList [ t - 1 ].NutList ;
for ( int n = nutlist.Count - 1 ; n >= 0 ; n-- )
{
int d = nutlist [ n ].CompareTo ( tray.Bolt ) ;
if ( d > 0 )
{
tray.NutList.Add ( nutlist.Fetch ( n ) ) ;
}
else if ( d == 0 )
{
tray.AddNut ( nutlist.Fetch ( n ) ) ;
}
}
}
return ( TrayList.Count ) ;
}
public abstract partial class Base
{
private int ID ;
public string Description { get ; private set ; }
protected Base
(
int ID
,
string Description
)
{
if ( System.String.IsNullOrWhiteSpace ( Description ) && ( ID != -1 ) )
{
throw ( new System.Exception ( "" ) ) ;
}
this.ID = ID ;
this.Description = Description ;
return ;
}
protected static int
Compare
(
Base Op0
,
Base Op1
)
{
return ( Op0.ID.CompareTo ( Op1.ID ) ) ;
}
}
private abstract partial class BaseList<T> : System.Collections.Generic.List<T>
where T : Base
{
protected BaseList
(
int Capacity
)
: base
(
Capacity
)
{
return ;
}
public virtual void
Shuffle
(
)
{
for ( int i = this.Count ; i > 0 ; i-- )
{
int j = Random.Next ( i ) ;
T n = this [ j ] ;
this.RemoveAt ( j ) ;
this.Add ( n ) ;
}
return ;
}
protected virtual B
Fetch<B>
(
int Index
)
where B : Base
{
B result = this [ Index ] as B ;
this.RemoveAt ( Index ) ;
return ( result ) ;
}
}
public sealed partial class Nut : Base , System.IComparable<Bolt>
{
public Nut
(
int ID
,
string Descrption
)
: base
(
ID
,
Descrption
)
{
return ;
}
public int
CompareTo
(
Bolt Bolt
)
{
return ( Compare ( this , Bolt ) ) ;
}
}
private sealed partial class NutList : BaseList<Nut>
{
public NutList
(
int Capacity
)
: base
(
Capacity
)
{
return ;
}
public Nut
Fetch
(
int Index
)
{
return ( this.Fetch<Nut> ( Index ) ) ;
}
}
public sealed partial class Bolt : Base , System.IComparable<Nut>
{
public Bolt
(
int ID
,
string Descrption
)
: base
(
ID
,
Descrption
)
{
return ;
}
public int
CompareTo
(
Nut Nut
)
{
return ( Compare ( this , Nut ) ) ;
}
}
private sealed partial class BoltList : BaseList<Bolt>
{
public BoltList
(
int Capacity
)
: base
(
Capacity
)
{
return ;
}
public Bolt
Fetch
(
int Index
)
{
return ( this.Fetch<Bolt> ( Index ) ) ;
}
}
private sealed partial class Tray
{
public Nut Nut { get ; private set ; }
public Bolt Bolt { get ; private set ; }
public NutList NutList { get ; private set ; }
public Tray
(
Bolt Bolt
,
int Capacity
)
{
if ( Bolt == null ) throw ( new System.Exception() ) ;
this.Bolt = Bolt ;
this.NutList = new NutList ( Capacity ) ;
return ;
}
public void
AddNut
(
Nut Nut
)
{
if ( Nut == null ) throw ( new System.Exception() ) ;
if ( this.Nut != null ) throw ( new System.Exception() ) ;
this.Nut = Nut ;
return ;
}
}
private sealed partial class TrayList
{
private System.Collections.Generic.List<Tray> list ;
public TrayList
(
int Capacity
)
{
this.list = new System.Collections.Generic.List<Tray> ( Capacity ) ;
Tray tray = new Tray ( new Bolt ( -1 , null ) , Capacity ) ;
tray.AddNut ( new Nut ( -1 , null ) ) ;
this.list.Add ( tray ) ;
return ;
}
public int
Count
{
get
{
return ( this.list.Count ) ;
}
}
public int
Insert
(
Bolt Bolt
)
{
int result = 0 ;
if ( Bolt == null ) throw ( new System.Exception() ) ;
while
(
( result < this.Count )
&&
( this.list [ result ].Nut.CompareTo ( Bolt ) < 0 )
)
{
result++ ;
}
this.list.Insert ( result , new Tray ( Bolt , this.list [ result - 1 ].NutList.Count ) ) ;
return ( result ) ;
}
public Tray
this
[
int Index
]
{
get
{
return ( this.list [ Index ] ) ;
}
}
}
private static partial class Random
{
private static System.Random rnd ;
static Random
(
)
{
rnd = new System.Random ( (int) System.DateTime.Now.Ticks ) ;
return ;
}
public static int
Next
(
int Max
)
{
for ( int i = System.DateTime.Now.Millisecond / 100 ; i > 0 ; i-- )
{
rnd.Next() ;
}
return ( rnd.Next ( Max ) ) ;
}
}
}
}
|
|
|
|
|
Test Data
For nuts
1
7
4
2
3
5
4
9
8
For bolts
6
4
9
7
8
1
2
3
4
Does it meet the specifications. No, but then real data almost never is as the user said it would be.
There are 2 matching 4s and one has an unmatched 5 the other an unmatched 6.
Good data in > good data out
Garbage in > report errors and depending on the situation quit or process what you can.
|
|
|
|
|
Yeah, I should review mine to see what happens with unmatched items, but I don't think it will cause trouble.
I know mine won't handle duplicates, but I could easily change it so that it does.
Still, not required by the spec.
|
|
|
|
|
Was Noel Coward terrified of Christmas?
"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!
|
|
|
|
|
More likely, Father Time was afraid of the near term.*
These seasonal offerings are a bit limiting.
Ravings en masse^ |
---|
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein | "If you are searching for perfection in others, then you seek disappointment. If you seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010 |
|
|
|
|
|
Yes, he was Clausetrophobic.
"the debugger doesn't tell me anything because this code compiles just fine" - random QA comment
"Facebook is where you tell lies to your friends. Twitter is where you tell the truth to strangers." - chriselst
"I don't drink any more... then again, I don't drink any less." - Mike Mullikins uncle
|
|
|
|
|
Does he need to be admitted to a santarium for treatment?
Anything that is unrelated to elephants is irrelephant Anonymous
- The problem with quotes on the internet is that you can never tell if they're genuine Winston Churchill, 1944
- Never argue with a fool. Onlookers may not be able to tell the difference. Mark Twain
|
|
|
|
|
Nah, he just needs to elf isolate for 10 days.
"the debugger doesn't tell me anything because this code compiles just fine" - random QA comment
"Facebook is where you tell lies to your friends. Twitter is where you tell the truth to strangers." - chriselst
"I don't drink any more... then again, I don't drink any less." - Mike Mullikins uncle
|
|
|
|
|
I've been trying to speed up my JSON processing and the bottleneck was my I/O class.
So I added a function to my I/O classes called skipToAny() which takes a string of characters and advances the input until it finds one of them.
Depending on the kind of source you use (like memory mapped file sources) it's *fast*
apparently strpbrk() is optimized for SSE and AVX instructions w/ some stdlib implementations.
So using the builtin C function to scan over my memory mapped buffer increases my performance by a factor of almost 4. I'm in spitting distance of 600MB/s now.
And I didn't even need to bit twiddle.
Higher level optimizations > bit twiddling
Real programmers use butterflies
|
|
|
|
|