Friday Quiz maths problem and Heap's algorithm

 T

oday's Friday Quiz maths problem is a corker:

When the official answer came, a simple solution was given with the answer (I'll save that till later) which didn't make things clear to me.

But without seeing an easier way, my approach, as usual, was to find all the permutations of the 9 digits, and count the ones that meet the criteria. 

The *number* of ways you can arrange some objects is easy to calculate. But how to actually shuffle those around in memory so that you can test them?

Long story short, I devised my own way to shuffle the numbers around, which I thought would work and it nearly did. But not quite. I turned to the web and found Heap's algorithm, which is very similar to what I was trying to do, except that it does actually work. 

It's simple, and the Wikipedia page gives some example code which is recursive.

Here's my version of that in C (I made my array global, rather than passing pointers around)

In my program, printNumber() also performs the test. If that number passes the test, it increases the 'result' counter and also prints an asterisk. 

This runs in 2-3 seconds on my M1 Mac, and that's the correct answer. (the number of permutations of the 9 digits is 9! which is 362880)

This week I've had an Amiga out and among other things I've been revisiting C on that computer. I find it amazing that the C I use every day targeting modern computers and microcontrollers is exactly the same as it was 30 years ago. So my same source compiled and ran on the Amiga (you can see that I added my own bool and true/false definitions because I like writing them lowercase)

And after an hour and a half, here's the same answer:

Another remarkable thing is that a friend on Twitter suggested that quite a bit of that time was probably used printing the numbers to the screen, so I took the printf's out and recompiled, and the program ran in less than a minute!!

• My source file is here (the version that works with old and new compilers).

It's not meant to be exemplary code, and I didn't spend any time on optimisations. Feel free to do those things.  Also note the typedef and defines for lowercase bool, true and false in my earlier screenshot.

The answer is 2898, and the official explanation given by the quizmaster is (126*(24-1)). This baffled me at first, but my friend George has explained in this Twitter thread:

https://twitter.com/markgbeckett/status/1594685436622143488