Code Miniatures!

[altenbach]

Let us define a "Code Miniature" as code that achieves the goal with the smallest amount of code elements.

(Similarly, miniature chess puzzles are defined as having a very small number of pieces, typically <7).

Of course speed is important too, but is it really worth throwing 5x more code at something just to gain 5% in speed? Probably not!

As it turns out, well written miniature code is typically also very efficient. 😄

So let's start out with the problem discussed here. (Appropriate for palindrome week! :D)

General Problem:

Find the largest palindromic number consisting of the product of two 3-digit numbers. A panlindromic number is defined as one whose digits are the same as its reverse. For example, 99799 is the same as its reverse "99799".

Miniature version of the problem (details here):

Can you solve the above problem from first principles using LabVIEW code that contains exactly the following collection of functions (plus controls/indicators, benchmark skeleton, and possibly some diagram constants):

Of course it would be interesting to see of somebody can do it with even less without much loss in performance. 😮

[jcarmody]

Where's the string conversion???

Ill try...

[altenbach]

---

@jcarmody wrote:

Where's the string conversion???

---

Don't need it. However if I use the string conversion, it slows down to about 170µs. Still pretty good, but contains a little bit more code. 😄

[John_P1]

I love this format.

I found I couldn't really use the minimalist diagram as a starting point (deductive vs inductive reasoning or some such thing...), but I came up with my own solution (which still uses the string conversion):

 

If you know the answer is a multiple of 11, it takes ~34 us (I'm not sure this qualifies under "first principles" or not)

If not, it's closer to 400 us 

I wasn't sure how much of the performance came from just where the answer happened to fall so I went ahead and tested higher digit case (not using the multiple of 11 rule).

Palindromic numbers which are products of two numbers integers between 1000 and 9999 (max=99000099):

~833 us

Best Regards,

[altenbach]

What's your hardware?

[Oligarlicky]

---

@jcarmody wrote:

Where's the string conversion???

Ill try...

---

I'm guessing he uses the quotient remainder and the for loop to do the palindrome check. That's what I did.

[John_P1]

---

@altenbach wrote:
What's your hardware?

---

3.1 GHz Core i5.

I hastily wrote in my initial post the 5 digit case (which I edited out once I realized the answer was wrong due to requiring 64-bit integers).

I re-ran the 5 digit after changing my types to u64 and got:

~14.2 ms

(9966006699 = 99681 * 99979)

Best Regards,

[altenbach]

Assuming we know nothing about the solution or even if one exists, robust code also needs to ensure that (1) the program always actually terminates (I.e. not stuck in an infinite loop) and (2) gives a unique answer (e.g. -1) if no solution exists. Mine does.

[John_P1]

---

@altenbach wrote:
Assuming we know nothing about the solution or even if one exists, robust code also needs to ensure that (1) the program always actually terminates (I.e. not stuck in an infinite loop) and (2) gives a unique answer (e.g. -1) if no solution exists. Mine does.

---

Ditto...

Hypothetically if there were no palindromic numbers at all in the 3 digit case (no 11s rule) it would take my code ~35.3 ms to execute since it has to check all of the combinations--I tested this by changing my palindrome check to always be FALSE.  I'd bet yours is probably faster since it's not doing the string compare.

Best Regards,

[Jacobson-ni]

That was a fun little puzzle.  I ended up using the same amount of primitive functions as Altenbach did  but only ended up sharing 2/11 primitives which I thought was pretty interesting.

I couldn't figure out what math needed to be done to check palindromeness but I thought I ended up with a neat solution that I attached.

I also just realized that I forgot to add my main while loop to the list of functions as well meaning Altenbach has me by one item and John by two (maybe next time).