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

ZX81 reversible internal 16k upgrade

T his post is an upvote for Tynemouth Software's  ZX81 reversible Internal 16K RAM upgrade . Their instructions are easy enough for even me to follow and don't involve cutting tracks. This is the ZX81 I've had out on display and used whenever I wanted to. It's an issue 1 and was probably a kit judging by some very untidy assembly. It has a ZX8-CCB  composite video mod and an external keyboard fitted. On board it has two 1k x 4-bit chips.  The ZX81 originally came with 1k on board. Thanks to a trick with compressing the display in ram, that was enough to type and run a small program but you soon felt the limitations. Back in the early 80s, the solution was a 16k ram pack which plugged into the back[1] and this is the way I've been using this particular machine. These ram packs are notorious for 'ram pack wobble'. Even if fastened into place, you can still randomly find your work disappearing. This is a very reliable solution using a more modern 32k chip (half

Driving NeoPixels with Z80

I 've long been thinking about a version two   RC2014 LED matrix module . I've had a matrix with a MAX 7219 on a module. It's a nice enhancement. But there's only so much you can do with a single-colour LED array right? Wouldn't it be cool to have RGB LEDs?  At Liverpool MakeFest I saw a wall-sized ping-pong ball NeoPixel display and picked up some NeoPixels with the intention of making one. Possibly driven by my RC2014.  I enjoy learning about protocols and have had some SPI devices working with the RC2014 - bit-banging SPI works really well because it doesn't care about timing. NeoPixels really do care about timing though. From Adafruit's web page about their 8x8  NeoPixel matrix: If there's one thing I want to get across in this blog post, it's don't just accept what you're told . Question everything. Learn about what's going on and find out why you're being told something isn't possible. Get creative with workarounds. I'

Making new ROMs for the Vic20 / Vicky Twenty

M y Vicky Twenty is very nearly complete.  As things stand, the board and every single component is new*. The processor and VIAs are newly-manufactured (W65C02 and W65C22).  Obviously the Vic1 chip isn't manufactured today, but there is 'new old' stock about. I have been able to buy a Vic 1, date code 1987 (which seems very late). It obviously hasn't been in a computer before, passes the acetone test and works. The same goes for two of the ROMs - character and BASIC. But I haven't been able to buy a new-old Kernal ROM (901486-07). I am able to borrow one - all of the boards I have, have this particular ROM socketed. I don't know whether all of this indicates that the Kernal has proved less reliable than the other two. I recently bought a TL866 for another project. Of all the retro-computing hardware things I've had to learn to do, making ROMs has been one of the simplest. So far, everything has been very easy and worked first time.  I'm not sure that it&