Skip to main content

Friday Quiz maths problem and Heap's algorithm

 T

oday's Friday Quiz maths problem is a corker:

916237458 is an example of a 9-digit number that contains all the digits 1-9 once. It also has the digits 1 to 5 appearing in their natural order, whilst the digits 6 to 9 do not. How many such numbers are there?

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!!
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


Labels

Labels:

Comments

Post a Comment

Popular posts from this blog

RC2024/10 - my entry

A while ago I made this MIDI module for RC2014: It works but a better design would have its own serial chip and port decoding.  As it is, it provides the MIDI interface and a clock signal for the second SIO2 serial port. This means that it requires a little setting up and will only work for RC2014s with an SIO2 (and port B not already used). I think people might reasonably expect it to be plug-and-play and self-contained, ie do all the serial itself. My challenge to myself is to:  learn how to connect a serial chip (probably 68B50 ACIA) to receive the incoming MIDI and to serialise outgoing MIDI design the module, including the port decoding write a library so that it can easily be used on any RC2014. Potential applications include a MIDI sequencer and using incoming MIDI to trigger notes on the AY or SID sound chips. Entering the Retro Challenge 2024 (aka RC2024/10)  has given me an incentive to get on with this! I'm happy to see several more entries in the RC2014 catego...
3 comments
Read more

IM53 8080 birthday cake

 Each year I've been trying to get more creative with ideas for Spencer's birthday cake. The plan this year was to incorporate LEDs in place of candles. I eventually settled on an Altair / IMSAI / PDP -style computer since those are the type of computers that inspired his RC2014. The IMSAI 8080 has the most colourful switches as well as a name that I could twist. The thought that it could show randomly flashing lights (as if the computer were running) and that it could also play a game of 'kill the bit' was very appealing. A plan formed to use a capacitive touch pad on the cake itself. The first job is to bake the fruitcake. I often use a 7" square tin and one of those cut in half and rearranged makes a cake of suitable proportions.  Even after taking a slice off the faces to make them nice and square, there are still some rounded corners, so after putting on the marzipan, I used more marzipan as a filler to flatten the whole thing. Even though I wanted to end up w...
Post a Comment
Read more

New MSX graphics / sound / joystick module for RC2014 / RCBus

I'm impressed at what Les has packed onto this standard-sized module. It contains an FPGA replacement for the TMS9918A, a YM/AY sound module and joystick interface.  The project is open-source and is here . In MSX terms this is the VDP (vidio display processor) and PSG (programmable sound generator), thus being an alternative for both the J B Langston TMS9918A video module and Ed Brindley's YM/AY sound module and adds two joystick ports to boot. All on a single module for RC2014 or compatible computers. There's no room for the d-sub joystick ports, so headers are provided so that these ribbon cables can be used.  This is a neat solution for those wishing to take advantage of Les' MSX8 system , which loads most MSX rom files along with a modified MSX BIOS from CP/M on a ROMWBW RC2014.  It is hard-wired to the MSX ports for the sound and video, so it won't be suitable for those wanting to run Colecovision ROMs, for example. I'm torn myself between the real TMS ...
Post a Comment
Read more