|
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
|
|
|
|
|
This is a very specific topic but oddly I received an email from a colleague today about a library called simdjson which gives a significant performance improvement over other c++ json libraries.
simdjson claim 'Standalone UTF8 Validation' at 13/GB/s
|
|
|
|
|
simdjson is cool, but it doesn't run everywhere. My JSON thing will even run on arduinos
Real programmers use butterflies
|
|
|
|
|
What are you doing on an Arduino that needs to process large Json files so quickly?
Or is this just a case of seeing how many people can fit in a phone booth?
If you can't laugh at yourself - ask me and I will do it for you.
|
|
|
|
|
It's not fast on an 8 bit Arduino, it's just that it scales to workstations and servers.
The advantage of it over ArduinoJSON is the same library also blazes on traditional computers, and it actually uses far less RAM than ArduinoJSON, which cannot process large online dumps from say, a mongoDB backed repository, like the one tbdb.com runs.
ETA: Originally I wrote it to try out a novel way of parsing and running queries, but it turns out simdjson just recently invented something similar. =)
Real programmers use butterflies
|
|
|
|
|
I want to build something, basically an analog clock where, when power is interrupted, the clock stops. But then, when power is restored, the clock zips around to the correct time.
Back in my SATCOM days, the az/el motors would follow the back-in-the-controlroom position controls, but wouldn't move if no power was applied to them. Then slew around to the correct position when the power was turned on.
So, basically, like that, in principle.
I have no idea what I'd need to get this to work these days. A digitally-controlled analog clock is probably the simplest...if I can figure out how to do it.
Suggestions?
|
|
|
|
|
|
Thanks. I was thinking that. Way simpler than a synchro.
|
|
|
|
|
So if you have a digital battery backed 'clock' keeping time, you could feed out to a couple of octal counters for the hour, six decades counters for the minutes. The time is read from from the counters and translated to a signal for the clock motor, if the power is lost the clock face just stops. Once the power is back up the signal will be a series of steps on from when power was lost the counters 'jump' to the correct time, the hands are not so will spin as fast as they can to show the right time. I think the issue will be getting the correct ammount and style of counters. This is sort of silly thing I enjoy give me chance I'll have a think.
|
|
|
|
|
That sounds simplest, so far.
|
|
|
|
|
It is my task in life to find the simple way to do things! Engineers are essance lazy, they find generally find a simple cheap way of doing things, managment complicate
|
|
|
|
|
If you plan the clock for the Central European market, you are within the coverage of DCF77[^] - it reaches half way up Norway.
The DFC77 signals, at 77.5 kHz (really longwave!) are so primitive, both at the physical modulation level and the data format, that I often refer to them as 'Morse code Mark II'. The frequency is so low that you could probably sample the signal from the antenna directly (after a simple tuning circuit) using any standard microprocessor that can take an analog input.
(My PC sound card is capable of producing 192 kHz sample rate sound, sufficient for generating the right on-the-air waveforms. I have jokingly suggested that once I get myself a new stereo amp capable of handling analog 192 kHz, I will plug an antenna into the speaker connectors and have my PC generate DCF77 signals to adjust all the DCF77 clocks in my neighborhood by an hour or two .)
The DCF77 data gives you exact time and date directly in binary format. The simpler way to do it is to feed these digital values directly to a numeric LED display. If you very much want an analog clock, you would use a stepper motor (moving arms 6 degrees/pulse) that at reset moves the arms to 00:00:00, and then moves each arm as many steps as the digital time value indicates. After a power down, you would have to do a reset (which may cause each arm to move all the way around - in theory almost twice: One to go from 1 to 00, and then from 00 to 59, if the arms were at 01:01:01 and the correct time is 11:59:59), but you need not worry about anything else to keep it in sync.
If you have battery backup for the stepper motors and the (very simple) electronics - it is as if the smallest Arduino is overkill - the clock doesn't have to stop, unless you want it to. One of my DCF77 clocks says in the documentation that to save battery power, it turns on the receiver once an hour checking for drifts of the internal oscillator, possibly holding back one pulse or giving one extra to the seconds arm, but even the cheapest oscillators nowadays are so stable that hourly check is probably overkill. You can just turn off the receiver completely if external power goes out.
I haven't been using a soldering iron for years, so I never build a DCF77 clock like this (but I have come as far as to buy the stepper motors for it ) - I guess you know how to handle the electronics much better than I can. Now that you post at CP, I take it that you also handle the software part well .
ps. If you do this, write a CP article about it!
|
|
|
|
|
Never even considered that. Even though I'm old and am used to things like LORAN-C (we used it just for the pulses, not positioning).
|
|
|
|
|
You might be able to use an Arduino or better yet, an ESP32 to control the steppers on the thing
An IoT Smart Clock Using an ESP32 Development Board[^]
IoT Smart Clock using the Mega 2560+WiFi R3[^]
These clocks use WiFi and NTP rather than a radio based sync mechanism so they don't support time zones but could be made to be configurable or modified to use the radio system.
Anyway, some of the principles therein might be useful. Get an ESP32 as they are cheaper and more capable than arduinos + smaller. I included both for the sake of completeness although the arduino one uses an ESP8266 as it's primary worker CPU, not the ATmega2560
Real programmers use butterflies
|
|
|
|
|
Thank you. More things to read about.
|
|
|
|
|
[^]555 is also 'yer friend ...
|
|
|
|
|
Going from simple to complex:
Asynchronous motors with a good reduction and an external encoder can work.
Steppers will do it if you don't need much torque and you don't need them to rotate fast (they can loose position feedback if they turn too fast) (you would need an external encoder to prevent that).
Servomotors will give you a bigger range of speeds and torque while not suffering from the loss of precision at fast speeds.
|
|
|
|
|