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 7 with no-one left over. What is the smallest possible number of soldiers in the platoon?
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
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:
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?
It's certainly simple enough...
ReplyDeleteloop 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.
One efficiency improvement is to count up from 7 using a step of 7.
Delete