Greetings Friends,

This video https://www.youtube.com/watch?v=iSNsgj1OCLA introduces an algorithm
that's easy to write and I found it intriguing. SDL might not be ideal for this
sort of thing (relatively slow) but it's all I have set up for use at the moment
so that's what I used. It's not necessary to watch the video to see what's going
on with the POV code, by the way.

There are two issues with this code. One might be a bug in POV-Ray, and the
other is probably a feature but it doesn't work the way that would make sense to
me. (Disclaimer: I'm an amateur so there's probably a reason that it works the
way that it does that I'm not aware of.)

Issue number one, possible POV bug: When I run the attached file with version
3.7, the final result that's displayed is 80% success rate. This is not an
anticipated result. However, un-commenting the line "#local Dummy = 0;" changes
the final result to 50% success rate, which appears to be correct. The variable
"Dummy" is never used and should have no effect on anything.

Issue number two, #break directive behavior: Without the #if () test marked with
the comment "//Why is this test necessary?" the #break directive will exit not
only the #for (K...) loop, but also the #for (J...) loop if the #break directive
is executed on the last iteration of the #for (K...) loop. When that happens,
the remainder of the #for (J...) loop is not completed as it should be (or as I
think it should be, anyway).

I'm mentioning these issues in case they might persist into version 3.8...

Have a wonderful day folks!

Kind regards,
Dave Blandston

Post a reply to this message

Attachments:
Download 'riddle.pov.dat' (2 KB)

hi,

"Dave Blandston" <IsN### [at] protonmailch> wrote:
> ...
> There are two issues with this code. One might be a bug in POV-Ray, and the
> other is probably a feature but it doesn't work the way that would make sense to
> me. (Disclaimer: I'm an amateur so there's probably a reason that it works the
> way that it does that I'm not aware of.)
>
> Issue number one, possible POV bug: When I run the attached file with version
> 3.7, the final result that's displayed is 80% success rate. This is not an
> anticipated result. However, un-commenting the line "#local Dummy = 0;" changes
> the final result to 50% success rate, which appears to be correct. The variable
> "Dummy" is never used and should have no effect on anything.
>
> Issue number two, #break directive behavior: Without the #if () test marked with
> the comment "//Why is this test necessary?" the #break directive will exit not
> only the #for (K...) loop, but also the #for (J...) loop if the #break directive
> is executed on the last iteration of the #for (K...) loop. When that happens,
> the remainder of the #for (J...) loop is not completed as it should be (or as I
> think it should be, anyway).
>
> I'm mentioning these issues in case they might persist into version 3.8...

"Issue number one" -- a beauty :-) -- also happens in 3.8.0-beta.2, on a Linux.
need to do more/better tests of "Issue number two" but didn't see a difference
with conditional commented out.


regards, jr.

Post a reply to this message

"jr" <cre### [at] gmailcom> wrote:
> need to do more/better tests of "Issue number two" but didn't see a difference
> with conditional commented out.


Hey jr, thanks for taking a look at this! I did some more testing with issue
number two and it's really weird. Commenting out the #if () conditional does not
change the results, even with thousands of iterations, which suggests that it
doesn't affect the execution flow. BUT... replacing the "#local Dummy = 0;" line
with this "#debug concat ("Comparing: ", str (J, 0, 0), ", " str (Box
[WhichBox], 0, 0), "\n")" produces interesting/bazaar results. The purpose of
this line is to make sure that the "loop" described in the video is being
followed correctly, which it is. The "J" variable represents each prisoner so it
should go from 0 to N - 1 since each prisoner gets a turn at looking for his
number. The "Box [WhichBox]" variable represents the number on the slip of paper
inside each box.

With the #if () conditional in place, here are the results of the new #debug
statement for six prisoners and random seed 12:

Comparing: 0, 0

Comparing: 1, 4
Comparing: 1, 3
Comparing: 1, 1

Comparing: 2, 2

Comparing: 3, 1
Comparing: 3, 4
Comparing: 3, 3

Comparing: 4, 3
Comparing: 4, 1
Comparing: 4, 4

Comparing: 5, 5

This is exactly the output that I want. It shows that comparisons are made until
the correct number is found, and if it's found before the maximum allowed number
of attempts, the remaining allowed comparisons are skipped.

Here is the output with the #if () conditional commented out:

Comparing: 0, 0

Comparing: 1, 4
Comparing: 1, 3
Comparing: 1, 1

It appears that without the #if () conditional, when the maximum allowed number
of comparisons are made, then the outer loop is exited inappropriately by the
#break instruction. Values for J = 2 through 5 are totally missing, yet the
final computed result is the same! Madness! Here's some more diagnostic
information indicating that the program execution is being affected - for values
of 100 prisoners and 10000 iterations, there was a 16-second difference in
processing times and a large difference in the "Parsing ____K tokens" number
that POV displays. It would take a mathematical genius to figure out why the
final result is unaffected by this issue (I may have inadvertently discovered
something significant and am about to become famous - ha ha) but the issue with
the #for (J...) loop being exited prematurely (in my opinion) does seem to be a
real issue - unless that's how it's supposed to work.

I've attached a file to demonstrate the issue more clearly. The #if ()
conditional with the comment "//Why is this test necessary?" can be commented
out for comparison purposes.

Kind regards,
Dave Blandston

Post a reply to this message

Attachments:
Download 'riddle2.pov.dat' (4 KB)

hi,

"Dave Blandston" <IsN### [at] protonmailch> wrote:
> ...
> I've attached a file to demonstrate the issue more clearly. The #if ()
> conditional with the comment "//Why is this test necessary?" can be commented
> out for comparison purposes.

afaict the conditional is needed only for 3.7.x, the 3.8.0-beta.2 works without.

question re code - NSuccesses only gets updated after all prisoners have looked
at their boxes?  wondering, ought that not be something like:

  #if (!MatchFound)  // fail
    #break
  #else
    // add to NSuccesses
  #end

also re the "Dummy" making a difference, have looked for, but cannot find, a
link to a story I read a few years ago; in a Californian chip foundry they used
an AI to optimise a chip design, and that (then, too) had a single unconnected
diode in the layout which, when removed, stopped everything working, no
explanation was given :-).

regards, jr.

Post a reply to this message

"jr" <cre### [at] gmailcom> wrote:
> question re code - NSuccesses only gets updated after all prisoners have looked
> at their boxes?  wondering, ought that not be something like:
>
>   #if (!MatchFound)  // fail
>     #break
>   #else
>     // add to NSuccesses
>   #end



Thanks jr! The #break instruction that gets executed when MatchFound is false
stops one round of the exercise early as soon as one prisoner fails to find his
number, then the next exercise begins which is controlled by the #for (I...)
loop. NSuccesses does not count the number of individual prisoners who find
their numbers, it counts the number of successful exercises in which all
prisoners find their numbers. I think it would be interesting to count how many
individual prisoners succeed though because, due to the inadvertent discovery,
it's obvious that the success or failure of the exercise can be determined well
before all the prisoners have actually completed the search for their numbers.

There is one part of the simulation that needs to be improved first, which is
the part that puts a random slip in each box. The current code is extremely
inefficient and will take about a week to complete for one million prisoners. I
have an idea to speed this operation up significantly, which will be a fun
exercise of its own.

Have an awesome day!

Kind regards,
Dave Blandston

Post a reply to this message

hi,

"Dave Blandston" <IsN### [at] protonmailch> wrote:
> "jr" <cre### [at] gmailcom> wrote:
> > question re code ...
> ... NSuccesses does not count the number of individual prisoners who find
> their numbers, it counts the number of successful exercises in which all
> prisoners find their numbers. ...

thanks  (makes sense, "or all fail together..").


> There is one part of the simulation that needs to be improved first, which is
> the part that puts a random slip in each box. The current code is extremely
> inefficient and will take about a week to complete for one million prisoners. I
> have an idea to speed this operation up significantly, which will be a fun
> exercise of its own.

ideally that code/macro would take two args - the number of prisoners/boxes, and
the number of chains (and perhaps dictate their lengths too?).  (have a feeling
this code can find other uses :-))


regards, jr.

Post a reply to this message

"jr" <cre### [at] gmailcom> wrote:
> ideally that code/macro would take two args - the number of prisoners/boxes, and
> the number of chains (and perhaps dictate their lengths too?).  (have a feeling
> this code can find other uses :-))



If I understand correctly, a chain that's too long can be split into two chains
by altering only two slips. I'm guessing that it would be just as easy to
combine two chains into one. So what you're suggesting is very possible.

I was so intrigued by the riddle that I thought it would be fun to conduct a
successful simulated exercise with one million prisoners. It looks like that
will take about three weeks using POV-Ray so I probably won't do that after all.
But I think the array of randomly numbered slips could be analyzed quickly to
determine the longest chain and therefore if the actual exercise would succeed.

If anyone is interested, here's a version with a much quicker slip randomization
algorithm. That part was a lot of fun too because it depends on balancing two
slow operations (moving large numbers of array elements around versus randomly
picking array elements that haven't already been picked) and the balance point
turned out to be much different than I thought it would be.

Kind regards,
Dave Blandston

Post a reply to this message

Attachments:
Download 'riddle3.pov.dat' (6 KB)