topic Re: Code Miniatures! in BreakPoint

Code Miniatures!

altenbach — Thu, 14 May 2015 19:23:51 GMT

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. 😮

Re: Code Miniatures!

jcarmody — Thu, 14 May 2015 20:00:12 GMT

Where's the string conversion???

Ill try...

Re: Code Miniatures!

altenbach — Thu, 14 May 2015 20:09:57 GMT

@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. 😄

Re: Code Miniatures!

John_P1 — Thu, 14 May 2015 23:58:44 GMT

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,

Re: Code Miniatures!

altenbach — Fri, 15 May 2015 00:02:30 GMT

What's your hardware?

Re: Code Miniatures!

Oligarlicky — Fri, 15 May 2015 00:05:49 GMT

@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.

Re: Code Miniatures!

John_P1 — Fri, 15 May 2015 00:11:17 GMT

@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,

Re: Code Miniatures!

altenbach — Fri, 15 May 2015 00:12:26 GMT

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.

Re: Code Miniatures!

John_P1 — Fri, 15 May 2015 00:21:42 GMT

@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,

Re: Code Miniatures!

Jacobson-ni — Fri, 15 May 2015 04:57:38 GMT

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).

Re: Code Miniatures!

altenbach — Fri, 15 May 2015 06:27:56 GMT

Sorry, I can only test on my ancient laptop (~2006) at the moment, but here are some approximate times and solutions.

can ayone verify if these solutions are correct? (The longer solutions use I64 of course)

size time solution

06 129us 906609
08  60us 99000099
10 115ms 9966006699
12  30ms 999000000999
14  35s  99956644665999
16   6s  9999000000009999

Re: Code Miniatures!

altenbach — Fri, 15 May 2015 08:01:35 GMT

@Jacobson-ni wrote:

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.

Yours seems to be a few orders of magnitude slower, but you are using a completely different algorithm overall. 😄

Re: Code Miniatures!

John_P1 — Fri, 15 May 2015 17:48:01 GMT

@altenbach wrote:

Sorry, I can only test on my ancient laptop (~2006) at the moment, but here are some approximate times and solutions.

can ayone verify if these solutions are correct? (The longer solutions use I64 of course)
size time solution

06 129us 906609
08  60us 99000099
10 115ms 9966006699
12  30ms 999000000999
14  35s  99956644665999
16   6s  9999000000009999

Those execution times are interesting (the solutions are right as far as I can tell).

For mine (without knowing answer is a multiple of 11) I got:

6: 400 us (906609 = 993 * 913)

8: 833 us (99000099 = 9999 * 9901)

10: 14.2 ms (9966006699 = 99979 * 99681)

12: 156 ms (999000000999 = 999999 * 999001)

14: 1.65 s (99956644665999 = 9998017 * 9997647)

16: 19 s (9999000000009999 = 99999999 * 99990001)

Yours is faster when the answer happens to include the maximum number in the range (e.g. 999999 * 999001), so I bet you're checking like this:

999999 * 999999
999999 * 999998

999999 * 999997

999999 * 999996

etc...

Mine is faster (for higher order cases anyway) when the answer does not include the maximum number in the range (e.g. 9998017 * 9997647). I'm doing the check like this:

9999999 * 9999999

9999998 * 9999999

9999998 * 9999998

9999997 * 9999999

9999997 * 9999998

9999997 * 9999997

9999996 * 9999999

etc...

Best Regards,

Re: Code Miniatures!

Jacobson-ni — Fri, 15 May 2015 17:56:12 GMT

@John_P1 wrote:

Yours is faster when the answer happens to include the maximum number in the range (e.g. 999999 * 999001), so I bet you're checking like this:

999999 * 999999
999999 * 999998

999999 * 999997

999999 * 999996

etc...

Wouldn't this method possibly skip over the correct answer if we are looking for the largest number?

Re: Code Miniatures!

altenbach — Fri, 15 May 2015 18:00:38 GMT

@John_P1 wrote:
Mine is faster (for higher order cases anyway) when the answer does not include the maximum number in the range (e.g. 9998017 * 9997647). I'm doing the check like this:

Yes, there are many ways to roll the numbers and it depends where the solution is. I start both numbers from the top, but stop the current train once the product is less than the best found so far.

Here are the current numbers on my 3.1GHz Xeon. A current generation I7 would probably be quite a bit faster)

size time solution

06  35us 906609
08  13us 99000099
10  25ms 9966006699
12   7ms 999000000999
14  13s  99956644665999
16   2s  9999000000009999

Re: Code Miniatures!

altenbach — Fri, 15 May 2015 18:15:28 GMT

@Jacobson-ni wrote:
Wouldn't this method possibly skip over the correct answer if we are looking for the largest number?

Well, we just need to keep the current largest and keep going until there are no larger products possible anymore.

The full search is

999999 * 999999
999999 * 999998

999999 * 999997

999999 * 999996

etc...

999998 * 999998

999998 * 999997

999998 * 999996

etc.

999997 * 999997

999997 * 999996

999997 * 999995

etc,

We terminate the inner loop if the product is less than the currently best. And terminate the outer loop (and the search!) if the square of the first number is less than the currently best.

Re: Code Miniatures!

Jacobson-ni — Fri, 15 May 2015 18:21:56 GMT

Clever, I was wondering where the square fit in to the VI.

Re: Code Miniatures!

John_P1 — Fri, 15 May 2015 18:32:32 GMT

@Jacobson-ni wrote:

Wouldn't this method possibly skip over the correct answer if we are looking for the largest number?

All numbers are tested in either algorithm (like Altenbach's, I move on to the next set once the product is below the best found palindromic number).

The space of products you have to check looks like this (e.g. the 2 digit case -- I blacked out the duplicates in the bottom left half of the graph):

Both algorithms start in the top left corner.

Altenbach's moves from left to right, moving down to the next row after each row is completed (or the exit criteria is met).

Mine moves from top to bottom, moving over to the next column after each column is completed (or the exit criteria is met).

My reason for slicing it this way is that the higher value products will mostly be tested first (e.g. checking 99*10 before checking 98*98 seems inefficient to me). As it turns out though, it is fairly common for the answer to fall on the top row so Altenbach's algorithm wins out in those cases. I think he also has some additional tricks to his that I am lacking (e.g. I'm still using the string conversion) that improve his performance.

Best Regards,

Re: Code Miniatures!

altenbach — Fri, 15 May 2015 19:09:07 GMT

I was rewriting mine in terms of Jacobsons algorithm (Checking 6 digit numbers for palinomicity :D), then see if there is a product of two 3 digit numbers. Takes about 1ms for the original 6 digit problem. Probably could be improved.

Re: Code Miniatures!

altenbach — Sat, 16 May 2015 00:19:55 GMT

Yes, your oder seems different but there is no clear winner.

Here are my preliminary times on the 3.1GHz Xeon for your input ordering. Still need to polish up the code....

size time solution

06  20us 906609
08  24us 99000099
10   2ms 9966006699
12  15ms 999000000999
14 520ms 99956644665999
16   7s  9999000000009999

A better way might be to sweep in a somewhat radial diagonal pattern such that the first one found is also the largest. 😄