Skip to main content

Friday quiz problem 10 Jun, an exercise in the mod function

T

oday's Friday Quiz question seems to have been devised as an exercise in writing a computer program using the mod() function:

A platoon of soldiers is lining up for a parade.  When they line up in rows of 3, one soldier is left over.  When they line up in rows of 4, two soldiers are left over.  When they line up in rows of 5, three soldiers are left over.  When they line up in rows of 6, four soldiers are left over.  However, they can line up in rows of with no-one left over.  What is the smallest possible number of soldiers in the platoon?

Spoiler alert: my answer is in the video. But writing the program is the fun part for me, not coming up with the answer.

As I say in the video, any language should have the mod() function. If not, you can write your own function / routine / word ,  it's the remainder after dividing one number by another.  Which is basically what the question is asking for. The lowest number where n mod 3 = 1, n mod 4 = 2 etc.

Here's my program. I haven't really gone for elegance, just bashed it out, but I will be pleased to see anyone else's program, in any language, particularly if there's a more efficient / elegant way to write it 

: run ( -- ) 1000 7 do 
i 3 mod 1 = if
i 4 mod 2 = if
i 5 mod 3 = if
i 7 mod 0 = if
    i . cr
then then then then 
loop ;

I don't think I've nested so many if/thens in Forth but that's no problem for the Jupiter Ace system. On my first attempt I tried looping to 100, and didn't find the answer, so here I've tried 7 to 1000 (we know from the question that the answer isn't less than 7. )

In the video I'm using my Minstrel 4th Jupiter Ace clone from Tynemouth Software / Future was 8-bit,  with my USB keyboard interface.

UPDATE

Thanks to Mr A's suggestions in the comments, I've made a couple of improvements to my program. 

1. counting in steps of 7 makes the program more efficient (we know the answer will be a multiple of 7). Plus it cuts out the test for being divisible by 7!

2. we don't need the nested if/thens.  if we deduct the target from each mod, we'll have zero if the test is passed. I've chosen to OR those answers together (a bitwise or) so that only a zero for each test will leave us with a zero when we have a valid answer. Here's the shorter program:

: run ( -- ) 1000 7 do 
i 3 mod 1 -
i 4 mod 2 - or
i 5 mod 3 - or
0= if 
    i . cr
then 
7 +loop ;




Works beautifully!

Are there further efficiencies?





Comments

  1. It's certainly simple enough...
    loop through each number and check we can satisfy all of those mod checks.

    Seems pretty efficient to me, if any one fails, we go to next number.

    ReplyDelete
    Replies
    1. One efficiency improvement is to count up from 7 using a step of 7.

      Delete

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 category, includ

How to convert images for TMS9918A graphics on the RC2014

For me, graphics capability is essential for an 8-bit computer. My graphics chip of choice for the RC2014 is the very capable TMS9918A. It has 15 colours, sprites, several modes and a max resolution of 256x192. It makes arcade-style games possible, such as Tut-Tut above.  I enjoy simply displaying images and have a bunch on my CF card (my 'hard drive') and have written image viewer and slideshow apps to display them. Some useful links: Convert9918 Tutorial of Convert9918's settings Multipaint J B Langston's TMS9918A video module my own TMSEMU video module my respository of TMS9918A software, games and .s2/.sc3 images Image conversion I did dabble in writing my own utility to convert .png images but then settled on the Multipaint app which can open a png in a MSX 'screen 2', allow you to tidy it up with paint tools and save as a .sc2 file. (An sc2 file is little more than a video-memory dump and so it's easy to blast that back into vram to display the image.

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