IGNORED

# Get your thinking caps on!

## Recommended Posts

Christmas Brain Teaser

From thedailywtf.com - post a solution to this problem in the language of your choice.

Titus Flavius Josephus was an important first-century historian. Having survived the siege and destruction of Jerusalem in 70 AD, he authored several works on Jewish history, including The Jewish War and Antiquities of the Jews. Not only have his writings given valuable insight into first century Judaism, they provide an extra-Biblical account of early Christianity. But aside from the books, and the writings, and all of his other invaluable contributions to history, Josephus also told the story of how he had escaped death by quickly standing in the "safe spot" of what is now called Josephus’ Circle.

As the legend goes, Josephus and forty of his fellow soldiers retreated from the siege of Yodfat to a small cave in the hills. Surrounded by the Roman legion with no chance of escape, the soldiers saw no other choice but to commit suicide. Like the people of Masada, they would rather die than face capture.

In order to decide who would die in which order, the soldiers stood in a circle and, starting with the top of the circle and continuing clockwise, counted to three. The third man got the ax and the counting resumed at one. The process continued until there was no one left. Josephus, who didn't quite agree with the whole "we should all kill ourselves" idea, figured out the perfect way to avoid death: be the last man standing.

Extra cudos if you post a solution in assembler

##### Share on other sites

Me? Well, it had to be Forth didn't it

```0 value #soldiers
#soldiers value remain
0 value position
: init ( --)
#soldiers 0 do 1  pad i +  c!  loop
-1 to position  #soldiers to remain ;

: position++ ( --)
position 1+ #soldiers mod to position ;

: kill3rd ( --)
0 begin
position++  soldiers' c@ if 1+ then
dup 3 = until drop
0 soldiers' c!  position 1+ .  remain 1- to remain ;

: killThem ( --) init begin remain 0> while kill3rd repeat
cr ." Last man standing at position " position 1+ . ;

: victims ( n -- ) to #soldiers  killThem ;
40 victims
```
##### Share on other sites

Note: for TI Forth/fbForth you'll need to use variables rather than values. I'll leave that as an excercise for the reader.

Interested to see solutions in TIB, XB (using subs - you can do it!) Fortran, C, and assembler!

Oh, and Forth

##### Share on other sites

I'll translate it to fbForth/TI Forth later today. Right now I have to start some Xmas food prep, including one of my favorites—mincemeat pie!

...lee

##### Share on other sites

Christmas Brain Teaser

From thedailywtf.com - post a solution to this problem in the language of your choice.

Extra cudos if you post a solution in assembler

Unless I missed something in your logic, Mark, you should run the program with 41 VICTIMS —there were 41 soldiers including Josephus.

Here it is in fbForth:

*

```0 VARIABLE #SOLDIERS
0 VARIABLE REMAIN
0 VARIABLE POSITION
: INIT ( --- )
#SOLDIERS @ 0 DO 1  PAD I +  C!  LOOP
-1 POSITION !  #SOLDIERS @ REMAIN ! ;

: POSITION++ ( --- )
POSITION @ 1+ #SOLDIERS @ MOD POSITION ! ;

: KILL3RD ( --- )
0 BEGIN
POSITION++  SOLDIERS' C@ IF 1+ THEN
DUP 3 = UNTIL DROP
0 SOLDIERS' C!  POSITION @ 1+ . -1 REMAIN +! ;

: KILLTHEM ( --- ) INIT BEGIN REMAIN @ 0 > WHILE KILL3RD REPEAT
CR ." LAST MAN STANDING AT POSITION " POSITION @ 1+ . ;

: VICTIMS ( n -- ) #SOLDIERS !  KILLTHEM ;

41 VICTIMS ```

*

...lee

##### Share on other sites

Here's one way to do in in assembly:

DEF START
REF VSBW

WKSP BSS 32
START LWPI WKSP
LI R3,3
JOSEP1 LI R2,REBELS
JOSEP2 MOVB *R2+,R4
JLT JOSEP1
DEC R3
JNE JOSEP2
LI R3,3
DEC R2
MOV R2,R4
JOSEP3 MOVB @1(R4),*R4+
JGT JOSEP3
CI R4,REBELS+2
JNE JOSEP2

LI R0,>0010
LI R6,10
MOVB @REBELS,R4
SRL R4,8
PRNUM1 MOV R4,R5
CLR R4
DIV R6,R4
JEQ OUT
MOVB @WKSP+11,R1
AI R1,>3000
BLWP @VSBW
DEC R0
JMP PRNUM1

OUT JMP OUT

REBELS BYTE 1,2,3,4,5,6,7,8,9,10
BYTE 11,12,13,14,15,16,17,18,19,20
BYTE 21,22,23,24,25,26,27,28,29,30
BYTE 31,32,33,34,35,36,37,38,39,40,41,255

END

##### Share on other sites

I copied my program and pasted it in the reply window and it was all formatted strangely and I had to manually adjust things. How in tarnation do you copy a program so it looks the same in your editor and the reply window?

##### Share on other sites

You put code tags around the code like this

[ code ]

Code here

[ / code ]

But *without the spaces*

So, for your assembler version of the problem, which is the last man standing out of 40 men?

##### Share on other sites

Willsy, the problem had 41 men - the 40 soldiers plus Josephus. Starting at the first man and counting clockwise, the first to get killed is 3, then 6 and so on. Set up like that the last man is number 31

##### Share on other sites

Willsy, the problem had 41 men - the 40 soldiers plus Josephus. Starting at the first man and counting clockwise, the first to get killed is 3, then 6 and so on. Set up like that the last man is number 31

I got 31 also, with a trusty old pencil and piece of paper.

Write down the numbers and cross them off as you count.

You guys all did it the hard way.

Gazoo

##### Share on other sites

Yep it sure was the hard way - first I wrote the program and got the number 31. Then I did what you did with pencil and paper and it took 3 or 4 tries before I was able to get the same answer.

##### Share on other sites

Edited by sometimes99er

He

##### Share on other sites

No. He's a soldier just like the rest. There's nothing special about him. There are 40 soldiers including him. The correct answer is 28 :-)

##### Share on other sites

My solution above occupies 320 bytes. I could make it smaller by using less descriptive names for the words, but that affects readability. I haven't counted senior_falcon's contribution (thanks!) but I guesstimate it's a little smaller than the Forth version (I haven't tested it, yet, either )

However, some total genius on the Forth Usenet group just posted a solution in Forth that occupies....

...62 bytes

```: josephus 0 1 begin dup 40 <= while swap 3 + over mod swap 1+ repeat
drop 1+ . ;```

Brilliant

##### Share on other sites

Okay, just assembled and ran senior's assembler solution. When I reduce the number of soldiers to 40 from 41, it does indeed give the correct answer of 28.

Occupies 256 bytes including the workspace.

Genius

##### Share on other sites

No. He's a soldier just like the rest. There's nothing special about him. There are 40 soldiers including him. The correct answer is 28 :-)

"...Josephus and forty of his fellow soldiers..."

Josephus = 1

and = +

forty of his fellow soldiers = 40

1 + 40 = 41

"Josephus and forty of his fellow soldiers" = 41

Gazoo

##### Share on other sites

Ah, good point. I see what you mean. Doh!

##### Share on other sites

Okay, just assembled and ran senior's assembler solution. When I reduce the number of soldiers to 40 from 41, it does indeed give the correct answer of 28.

Occupies 256 bytes including the workspace.

Don't know where those numbers come from. Here's what I get:

32 bytes for the WKSP

40 bytes for the main program

40 bytes to print out the number

42 bytes for the data

for a total of 154 bytes

It can be downsized by eliminating the WKSP BSS 32, eliminate LWPI WKSP and change MOV @WKSP+11,R1 to be MOV R5,R1 and SLA R1,8

Then the size is:

36 bytes for the main program

40 bytes to print out the number

42 bytes for the data

for a total of 118 bytes

Of course, a clever programmer could write this quite a bit more compactly.

Even so the FORTH program is a lot smaller, but my head hurts trying to understand it!

Edited by senior_falcon
##### Share on other sites

The only problem with all of this is... 40 is really variable!

What?? In most translations, "MANY" is translated to 40... Why? I don't know!

40 thieves, 40 days and night, wandered for 40 years.... etc.

So, Josephus was smarter than we can calculate!!!

##### Share on other sites

Don't know where those numbers come from. Here's what I get....

Woops! You're right... Sorry. What an ass... I produced a listing file from the assembler, and saw that the last byte of code was at address \$98 (relative to 0). In my head, 98+2=100. 100 hex=256 bytes! However (I'm an ass) 98+2=9A, not 100.

Too much eggnog me thinks!

##### Share on other sites

... However, some total genius on the Forth Usenet group just posted a solution in Forth that occupies....

...62 bytes

```: josephus 0 1 begin dup 40 <= while swap 3 + over mod swap 1+ repeat
drop 1+ . ;```

It's 56 bytes in fbForth and TI Forth after defining <= .

...lee

##### Share on other sites

It's 56 bytes in fbForth and TI Forth after defining <= .

...lee

Wow that's cool! How does it do that? Here's what mine looks like:

##### Share on other sites

... Even so the FORTH program is a lot smaller, but my head hurts trying to understand it!

Mine, too! My effort to try to understand it included calling the first number X because I really don't know what it tracks, and the second one C because it is obviously a counter. Each time through the loop, X and C are updated as follows:

*

```X = (X + 3) mod C
C = C + 1 ```

*

I didn't get beyond that. Maybe someone else can take it further to explain what X is doing.

...lee

##### Share on other sites

Wow that's cool! How does it do that? Here's what mine looks like:

TF's link fields are 2 bytes each instead of fbF's 1 byte; but, that's a wash in this case because 'JOSEPHUS' is an even number of characters.

The difference is probably due to the fact that 0 , 1 , 2 and 3 are defined as actual words in fbF and TIF because of their frequent usage. That saves 6 bytes in the definition of JOSEPHUS due to the 3 LITs required in TF.

...lee

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.