Jump to content
IGNORED

Get your thinking caps on!


Willsy

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 :grin:

Link to comment
Share on other sites

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

 

 

0 value #soldiers
#soldiers value remain
0 value position
: init ( --)
    #soldiers 0 do 1  pad i +  c!  loop
    -1 to position  #soldiers to remain ;
   
: soldiers' ( -- addr) pad position + ;
   
: 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
Link to comment
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 :grin:

 

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

 

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 ! ;
   
: SOLDIERS' ( --- addr ) PAD POSITION @ + ;
   
: 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

Link to comment
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

Link to comment
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

Link to comment
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 :-o

 

 

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

 

Brilliant :thumbsup:

Link to comment
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

Link to comment
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
Link to comment
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!

  • Like 1
Link to comment
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

Link to comment
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

Link to comment
Share on other sites

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.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...