User avatar
jahboater
Posts: 6672
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: A Birthday Present for Fido

Thu Oct 15, 2020 4:45 pm

Heater wrote:
Thu Oct 15, 2020 11:15 am
Interestingly Rust does much the same but does not require one to spell out what is captured. It just figures it out from the variable references used inside the lambda.
Interesting.
C++ does that if you give * for the capture list. If you do give the *, it seems to behave just like a C nested function.
Pi4 8GB (Raspberry Pi OS 64-bit), Pi4 4GB, Pi4 2GB, Pi1 Rev 1 256MB, Pi Zero

ejolson
Posts: 6596
Joined: Tue Mar 18, 2014 11:47 am

Re: A Birthday Present for Fido

Thu Oct 15, 2020 4:47 pm

lurk101 wrote:
Thu Oct 15, 2020 4:26 pm
ejolson wrote:
Thu Oct 15, 2020 4:07 pm
You are right having different graph generation algorithms will completely change the game. This prevents a robot from playing two different codes in lock step. If the graph generating algorithms are different, one could load the maze from a file and reinitialise the random number generator before starting the robot.
Prior to fuzzing, compliance testing is required no?

I was thinking of using your graphing output to verify that the generated caves are Euler graphs.
Given the fact that these graphs have valence three I think it would be quite remarkable if any were Euler graphs, however with the addition of super bats anything is possible.

lurk101
Posts: 379
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: A Birthday Present for Fido

Thu Oct 15, 2020 4:56 pm

ejolson wrote:
Thu Oct 15, 2020 4:47 pm
Given the fact that these graphs have valence three I think it would be quite remarkable if any were Euler graphs, however with the addition of super bats anything is possible.
True. Then what is the term for a valence three graph that contains a path, not necessarily a cycle, that visits every node once?

Edit: And would that be a minimum requirement for a wumpus cave?
Last edited by lurk101 on Thu Oct 15, 2020 5:02 pm, edited 1 time in total.

User avatar
jahboater
Posts: 6672
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: A Birthday Present for Fido

Thu Oct 15, 2020 4:59 pm

ejolson wrote:
Thu Oct 15, 2020 4:07 pm
Is there a strict K&R compatibility switch in gcc on the Pi that can be used instead?
From what I have seen, C89 is oldest option. Shame!
Pi4 8GB (Raspberry Pi OS 64-bit), Pi4 4GB, Pi4 2GB, Pi1 Rev 1 256MB, Pi Zero

ejolson
Posts: 6596
Joined: Tue Mar 18, 2014 11:47 am

Re: A Birthday Present for Fido

Thu Oct 15, 2020 5:08 pm

hippy wrote:
Wed Oct 14, 2020 4:33 pm
jahboater wrote:
Tue Oct 13, 2020 8:57 pm
They [nested functions] are just normal functions, usually small service functions, that are of no interest outside of the surrounding function.
The usual programming rule of reducing visibility as far as possible is one motivation.
+1 limiting scope and access is my basis for using nested functions.

Anyway ... back to Fido ...
I asked Fido the difference between nesting functions and closures. After a bit of howling about why we couldn't have the birthday party early, the dog developer whined, closures are a weak form of metaprogramming while nested functions are a dog standard aspect of structured programming that were left out of C as part of the worse is better philosophy of research Unix. The rest of the reply sounded like barking to me, especially the part about the advantages of using irrational line numbers in FidoBasic.

At the same time, there was one other thing I made out from the excessive barking that resonated with my recent programming experience: While the strong typing of Pascal strings seems like an example of ivory-tower better is better impracticality, as shown by the defined but unexpected behaviour of polymorphic types that talk like ducks, there is nothing so bad that it can't be made worse. Regrettably, my comment that at least ducks don't bark abruptly ended the conversation.

Back to a birthday present for Fido, does anyone have an idea how any of the Hunt the Wumpus programs can be improved using closures?

Heater
Posts: 17359
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Birthday Present for Fido

Thu Oct 15, 2020 5:13 pm

jahboater wrote:
Thu Oct 15, 2020 4:45 pm
Heater wrote:
Thu Oct 15, 2020 11:15 am
Interestingly Rust does much the same but does not require one to spell out what is captured. It just figures it out from the variable references used inside the lambda.
Interesting.
C++ does that if you give * for the capture list. If you do give the *, it seems to behave just like a C nested function.
Yes. Except it's not "[*]" it's "[=]" if you want to captured everything by value. Or "[&]" if you want to captured everything by reference.
https://docs.microsoft.com/en-us/cpp/cp ... 0reference.

Of course, being C++, if you use the wrong one in compiles without error and gives the wrong results.

Here is my first attempt at "Functional Programming" in C++. It has a function which composes two other functions to create a third.

Code: Select all

$ cat compose_lambdas.cpp
#include <functional>

typedef std::function<int (const int)> fun_t;

// Create a function that returns an offset version of it's parameter.
auto make_offsetter (int m) {
        auto function = [=](int n) {
                return (m + n);
        };
        return function;
}

// Create a function that returns a scaled version of it's parameter.
auto make_scaler (int m) {
        auto lambda_function = [=](int n) {
                return (m * n);
        };
        return lambda_function;
}

// Create a function that returns the result of applying fun_b then fun_a to it's parameter.
auto compose(fun_t fun_a, fun_t fun_b ) {
        auto function = [=] (int n) {
                return fun_b(fun_a(n));
        };
        return function;
}

int main () {
        auto offset_and_scale = compose(make_offsetter(42), make_scaler(33));
        auto x = offset_and_scale (100);
        printf("%d\n", x);
}

$ g++ -Wall -o compose_lambdas compose_lambdas.cpp
$ ./compose_lambdas
4686
$

Neat ha?

Change those "[=]" to "[&]" and see how it produces the wrong result without warning. Thanks a bunch Bjarne.

I'm sure the C++ committee has Functional Programming in mind for C++. Just type "C++ Functional" into youtube's search box and see how many presentations on it have popped up at C++ conferences in recent years.
Last edited by Heater on Thu Oct 15, 2020 5:35 pm, edited 2 times in total.
Memory in C++ is a leaky abstraction .

lurk101
Posts: 379
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: A Birthday Present for Fido

Thu Oct 15, 2020 5:30 pm

Is there an easily installed Pascal compiler for the Pi4?

Heater
Posts: 17359
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Birthday Present for Fido

Thu Oct 15, 2020 5:38 pm

lurk101 wrote:
Thu Oct 15, 2020 5:30 pm
Is there an easily installed Pascal compiler for the Pi4?
I presume Free Pascal is working on the Pi4:

Code: Select all

$ sudo apt-get install fpc
And probably the Lazarus IDE for it:

Code: Select all

$ sudo apt-get install lazarus
Memory in C++ is a leaky abstraction .

User avatar
jahboater
Posts: 6672
Joined: Wed Feb 04, 2015 6:38 pm
Location: Wonderful West Dorset

Re: A Birthday Present for Fido

Thu Oct 15, 2020 5:47 pm

Heater wrote:
Thu Oct 15, 2020 5:13 pm
Neat ha?
Impressive!
Heater wrote:
Thu Oct 15, 2020 5:13 pm
I'm sure the C++ committee has Functional Programming in mind for C++.
To make C++ even more "multi-paradigm" ... aaagh!
Pi4 8GB (Raspberry Pi OS 64-bit), Pi4 4GB, Pi4 2GB, Pi1 Rev 1 256MB, Pi Zero

ejolson
Posts: 6596
Joined: Tue Mar 18, 2014 11:47 am

Re: A Birthday Present for Fido

Thu Oct 15, 2020 5:57 pm

lurk101 wrote:
Thu Oct 15, 2020 4:56 pm
ejolson wrote:
Thu Oct 15, 2020 4:47 pm
Given the fact that these graphs have valence three I think it would be quite remarkable if any were Euler graphs, however with the addition of super bats anything is possible.
True. Then what is the term for a valence three graph that contains a path, not necessarily a cycle, that visits every node once?

Edit: And would that be a minimum requirement for a wumpus cave?
My understanding is
  • Euler graphs contain a cycle passing through every edge exactly once.
    • Hamiltonian graphs contain a cycle passing through every vertex exactly once.
      • Traceable graphs have a path passing through every vertex once.
        • Connected graphs have a path from any need to any other.
          • Wumpus graphs remain connected after removing the vertices with the pits and super bats.
          I recently attended a talk analysing the relative robustness of German, Spanish and English power grids based on a concept similar to Wumpus graphs. Following Murphy's law, the super bats were always placed in the worst location possible and the resulting power outages of the grid analyzed.

          If the possibility of shooting the bats is allowed as in the PDP-8 game, then it doesn't matter where they are. Thus, a maze with the weak Wumpus property should be possible to fully explore while shooting the bats and avoiding the pits. Therefore, one possibility is for the setup phase to check the graph remains connected after the vertices containing pits have been removed and then extend the code for the SuperPET to shoot super bats with crooked arrows as in the PDP-8 version.

          lurk101
          Posts: 379
          Joined: Mon Jan 27, 2020 2:35 pm
          Location: Cumming, GA (US)

          Re: A Birthday Present for Fido

          Thu Oct 15, 2020 6:05 pm

          Heater wrote:
          Thu Oct 15, 2020 5:38 pm
          I presume Free Pascal is working on the Pi4:

          Code: Select all

          $ sudo apt-get install fpc
          Yes, thanks. Installed a ton of dependencies!! libvorbis-dev no less.
          And probably the Lazarus IDE for it:

          Code: Select all

          $ sudo apt-get install lazarus
          
          Not planning on doing GUI development, looks like a Delphi clone.

          lurk101
          Posts: 379
          Joined: Mon Jan 27, 2020 2:35 pm
          Location: Cumming, GA (US)

          Re: A Birthday Present for Fido

          Thu Oct 15, 2020 6:21 pm

          ejolson wrote:
          Thu Oct 15, 2020 5:57 pm
          Wumpus graphs remain connected after removing the vertices with the pits and super bats.
          Ah yes. I guess that's a necessary condition. Currently that property can't be respected since the cave is generated prior to placing the hazards, and there doesn't seem to be any attempt to avoid splitting the hazard free sub-graph while deploying hazards..
          Last edited by lurk101 on Thu Oct 15, 2020 7:39 pm, edited 1 time in total.

          ejolson
          Posts: 6596
          Joined: Tue Mar 18, 2014 11:47 am

          Re: A Birthday Present for Fido

          Thu Oct 15, 2020 6:29 pm

          Heater wrote:
          Thu Oct 15, 2020 5:38 pm
          lurk101 wrote:
          Thu Oct 15, 2020 5:30 pm
          Is there an easily installed Pascal compiler for the Pi4?
          I presume Free Pascal is working on the Pi4:

          Code: Select all

          $ sudo apt-get install fpc
          And probably the Lazarus IDE for it:

          Code: Select all

          $ sudo apt-get install lazarus
          
          There is no need to install Lazarus, which in my opinion is mostly for coding up graphical interfaces.

          The previously posted Pascal code for the SuperPET was verified to run (actually developed) using Free Pascal on the Pi 4B. Note that the snarf routine, which gobbles up the prompt that appears in the input when reading from the smart terminal on the PET, doesn't interfere with Free Pascal running in a normal terminal window on the Pi.

          It also seems that Free Pascal, like Waterloo microPascal, allows one to access individual characters in a packed array of character without having to unpack it. The story of Unicode versus ASCII seems to be a repeat of ASCII versus Baudot.

          This suddenly reminds me of a friend who could read paper tape at about the same speed as a Teletype just by looking at it. Given the current state of Teletype technology, I suspect he can do the same with an SD card.
          Last edited by ejolson on Thu Oct 15, 2020 6:40 pm, edited 1 time in total.

          Heater
          Posts: 17359
          Joined: Tue Jul 17, 2012 3:02 pm

          Re: A Birthday Present for Fido

          Thu Oct 15, 2020 6:38 pm

          jahboater wrote:
          Thu Oct 15, 2020 5:47 pm
          To make C++ even more "multi-paradigm" ... aaagh!
          Aaaaaagh!!!

          Apologies for diverting this thread from Fido's birthday present.

          Perhaps we will converge again at some point. I'm losing sleep over creating a Wupus maze, and I don't want to peek an an existing solution...
          Memory in C++ is a leaky abstraction .

          lurk101
          Posts: 379
          Joined: Mon Jan 27, 2020 2:35 pm
          Location: Cumming, GA (US)

          Re: A Birthday Present for Fido

          Thu Oct 15, 2020 7:13 pm

          ejolson wrote:
          Thu Oct 15, 2020 5:57 pm
          ... as in the PDP-8 version.
          Where is the PDP-8 version?

          ejolson
          Posts: 6596
          Joined: Tue Mar 18, 2014 11:47 am

          Re: A Birthday Present for Fido

          Thu Oct 15, 2020 8:00 pm

          lurk101 wrote:
          Thu Oct 15, 2020 7:13 pm
          ejolson wrote:
          Thu Oct 15, 2020 5:57 pm
          ... as in the PDP-8 version.
          Where is the PDP-8 version?
          The PDP-8 version is linked in the post

          viewtopic.php?p=1740611#p1740611

          and essentially the code I tested with BBC Basic and later in Waterloo microBASIC. This program has the broken graph generator that occasionally gets stuck in an infinite loop, which you ported to C and (thankfully) fixed. I've thought about adding a count variable to the original code, as in Ken's generator, so it bails out and tries again when it gets stuck. I haven't done so out of wonder whether the pseudo-random number generator on the PDP-8 had some weird property that prevented such an infinite loop from manifesting on that machine. It seems back porting your C code might be a better way to remove that ancient bug.

          Philosophically I would prefer an algorithm that doesn't keep doing random stuff until it succeeds but instead would still work if the random number generator were replaced by a closure which, due to inexplicable psychokinetic stack influences, always returned the number 0. Interestingly, Fido's C code makes valence d graphs on n vertices without relying on any randomness. Unfortunately, they are not Wumpus graphs or even connected.

          Gregory Yob originally dodged the whole issue by setting the graph of a dodecahedron to be the maze. It is possible the dodecahedron has a sort of maximal robustness in the sense of remaining connected as randomly chosen vertices with pits and super bats are removed. If true, this makes a better explanation, in my opinion, of why a dodecahedron was originally chosen for the maze compared to the official story about having a kite as a child. Would a dodecahedral kite even fly?

          As a related thought, I wonder if the California power grid should be arranged in a dodecahedron for greater reliability. In case someone wants to submit such a research proposal, I'd be happy to write a letter of support explaining the connection of electricity to Wumpus graphs. As preliminary work, it appears--even after taking all the symmetries into account--that calculating the probability that randomly placing pits and super bats in a dodecahedron results in a Wumpus graph might be a task better suited for the super-cheap Pi Zero cluster

          viewtopic.php?f=49&t=199994

          rather than a SuperPET. They are each super in their own ways.
          Last edited by ejolson on Fri Oct 16, 2020 1:34 am, edited 2 times in total.

          lurk101
          Posts: 379
          Joined: Mon Jan 27, 2020 2:35 pm
          Location: Cumming, GA (US)

          Re: A Birthday Present for Fido

          Fri Oct 16, 2020 12:44 am

          ejolson wrote:
          Thu Oct 15, 2020 8:00 pm
          it appears--even after taking all the symmetries into account--that calculating the probability that randomly placing pits and super bats in a dodecahedron results in Wumpus graph might be a task better suited for the super-cheap Pi Zero cluster
          Trying to determine the answer the lazy man's way, statistically rather than mathematically, by running the init and setup functions 1000's of times, I made an unfortunate discovery. The cave generation algorithm I proposed is also subject to the evil infinite loop. Not as much, but still...

          Had I known this class would be so vexing I might have opted for English Lit.

          ejolson
          Posts: 6596
          Joined: Tue Mar 18, 2014 11:47 am

          Re: A Birthday Present for Fido

          Fri Oct 16, 2020 2:46 am

          lurk101 wrote:
          Fri Oct 16, 2020 12:44 am
          ejolson wrote:
          Thu Oct 15, 2020 8:00 pm
          it appears--even after taking all the symmetries into account--that calculating the probability that randomly placing pits and super bats in a dodecahedron results in Wumpus graph might be a task better suited for the super-cheap Pi Zero cluster
          Trying to determine the answer the lazy man's way, statistically rather than mathematically, by running the init and setup functions 1000's of times, I made an unfortunate discovery. The cave generation algorithm I proposed is also subject to the evil infinite loop.
          That's unfortunate. The official worse is better way of dealing with such infinite loops appears to be introducing a counter that detects when the algorithm is stuck and then starts over from the beginning.

          I was searching for Pascal versions of Hunt the Wumpus and found a translation of Gregory Yob's Wumpus 2 on Simtel SIG/M volume 21

          http://www.classiccmp.org/cpmarchives/f ... 0%2Fvol021

          which had the ability to load custom graphs from a file. There was also a Fibonacci random number generator, which looks like it would be faster than the code I wrote. While that generator doesn't reproduce the same dynamics as the linear congruential generator in the 7th edition of historic Unix, I think Fido might prefer the Fibonacci aspects even more.

          For me the most interesting aspect of the Pascal program was a file format for describing graphs that looks like

          Code: Select all

          a Dodecahedron
          02 05 08   01 03 10   02 04 12   03 05 14   01 04 06
          05 07 15   06 08 17   01 07 09   08 10 18   02 09 11
          10 12 19   03 11 13   12 14 20   04 13 15   06 14 16
          15 17 20   07 16 18   09 17 19   11 18 20   13 16 19
          
          The first line is the description of the graph. The following lines contain groups of numbers indicating the connections between vertices. While all the included files were valence 3 graphs on 20 vertices, it would appear that the same format could be used to describe graphs with an arbitrary degree and number of vertices. Note that the cave3 was missing from the Simtel archive but (if you are not afraid of all the banner advertisements) may be found at

          https://techtinkering.com/articles/hunt ... us-on-cpm/

          Note, the archiver lbrate

          http://www.svgalib.org/rus/lbrate.html

          can be used to unpack that CP/M archive on a Raspberry Pi.

          With this in mind, I have started to write a program that determines the probability a random placement of pits and super bats results in a Wumpus graph. If Fido knew how much work was going into this birthday surprise, then it wouldn't be a surprise.
          Last edited by ejolson on Fri Oct 16, 2020 4:50 am, edited 4 times in total.

          ejolson
          Posts: 6596
          Joined: Tue Mar 18, 2014 11:47 am

          Re: A Birthday Present for Fido

          Fri Oct 16, 2020 3:51 am

          Here is what graphviz outputs for the dodecahedral maze.

          Image

          While not the standard way of drawing that graph, it is clear that it remains connected as long as no more than 2 vertices are removed. Interestingly, the original game included exactly two pits and two super bats. Therefore, the graphs in Gregory Yob's original game, no matter where the obstacles were placed, were guaranteed to be weakly wumpus and, except for the possibility of an isolated vertex or edge, wumpus.

          The same does not seem true for the version of the game that appears in the 7th edition of historic Unix. Not only did that game have three bats and three pits, but randomly generated mazes do not likely have the robust connectedness properties of a dodecahedron. Still, it seems that the graphs produced by the Ken's program are statistically likely to be wumpus as well as weakly wumpus.

          But how likely?

          On the other hand, the Wumpus in the Unix version could be smelled from two vertices away. Therefore, there is also a chance that it would be possible to smell where the Wumpus is and shoot an arrow over an obstacle to reach it, even if the graph is not connected after removing the vertices corresponding to the obstacles. Since being able to smell well reflects physical characteristics of the dog developer, here is a possible definition for a smelly wumpus graph:
          • No matter where the Wumpus, it should be possible to move while avoiding obstacles to a location where one can smell a Wumpus.
          Note that the definition of a smelly wumpus graph depends on the pits, super bats and initial location of the player. I think the dodecahedron with four randomly placed obstacles will be a smelly wumpus graph, unless the player starts on an isolated vertex or edge. English literature sounds like it might be a good idea.

          Heater
          Posts: 17359
          Joined: Tue Jul 17, 2012 3:02 pm

          Re: A Birthday Present for Fido

          Fri Oct 16, 2020 5:36 pm

          I don't know if Fido is in to Rust but I have just spent half a day making his birthday present. A Wumpi maze generator in Rust.

          To be honest I had too much of a hangover to do anything else. And I it was a challenge not to be resisted.

          As I don't know what I'm doing and I have not peeked at any other solutions I came up with the following approach:

          Step 1) Put the set of numbers 0 to 19 into an array and shuffle them. Produce a bunch of connections, edges, that link all the nodes together in a loop. To do this just assume that every element in the array connects to the next one. And wrap around at the end. This ensures that we will never get disjoint graphs, we have already connected everything in a loop. Which gives us a "maze" like this:
          graph_1.png
          graph_1.png (65.46 KiB) Viewed 561 times
          Step 2) Looking at that nice loop it seems that if we pick any two, different, nodes at random and connect them together we create two nodes that both have the required number of exits, 3. Doing that produces two connected loops. Like so:
          graph_2.png
          graph_2.png (64.82 KiB) Viewed 561 times
          Produce the two selected nodes as an another edge in our output

          Step 3) Given that the two nodes connected above now have the required 3 exits we can remove them from further consideration. So remove them from the set of nodes.

          Step 4) Proceed from Step 2) above until there are no more nodes left in the set.

          Then we have a finished graph like so:
          graph_3.png
          graph_3.png (60.56 KiB) Viewed 561 times
          Last edited by Heater on Sat Oct 17, 2020 7:02 am, edited 3 times in total.
          Memory in C++ is a leaky abstraction .

          Heater
          Posts: 17359
          Joined: Tue Jul 17, 2012 3:02 pm

          Re: A Birthday Present for Fido

          Fri Oct 16, 2020 5:41 pm

          Oh yeah, all the above as code in Rust:

          Code: Select all

          use rand::seq::SliceRandom;
          use rand::Rng;
          
          fn main() {
              // Create a set of numbered nodes.
              let mut nodes = vec![0u8; 20];
              for i in 0..nodes.len() {
                  nodes[i] = i as u8;  
              }
          
              // Shuffle them for good luck.
              let mut rng = rand::thread_rng();
              nodes.shuffle(&mut rng);
          
              println!("graph WumpusGraph {{");
          
              // Prouduce connections of all nodes in a simple loop
              for i in 0..nodes.len() {
                  println!("    {} -- {}", nodes[i], nodes[(i + 1) % nodes.len()]);  
              }
          
              // Produce connections between randomly selected pairs of nodes.
              // Until all nodes have 3 conections.
              while nodes.len() > 0 {
                  // Select a random node as one end of a pair
                  let si = rng.gen_range(0, nodes.len());
                  let start_node = nodes[si];
          
                  // Remove the node from the node set, so as to ensure it is not reused.
                  nodes.retain(|&n| n != start_node);
          
                  // Select a random node as the end of a pair
                  let ei = rng.gen_range(0, nodes.len());
                  let end_node = nodes[ei];
          
                  // Remove the node from the node set, so as to ensure it is not reused.
                  nodes.retain(|&n| n != end_node);
          
                  // Produce a connection between the pair of selected nodes
                  println!("    {} -- {}", start_node, end_node);  
              }
          
              println!("}}");
          }
          
          Which outputs a dot format graph like so:

          Code: Select all

          graph WumpusGraph {
              2 -- 12
              12 -- 7
              7 -- 3
              3 -- 9
              9 -- 19
              19 -- 17
              17 -- 14
              14 -- 8
              8 -- 5
              5 -- 10
              10 -- 0
              0 -- 15
              15 -- 4
              4 -- 13
              13 -- 18
              18 -- 6
              6 -- 1
              1 -- 16
              16 -- 11
              11 -- 2
              0 -- 17
              18 -- 16
              4 -- 19
              3 -- 14
              9 -- 13
              10 -- 7
              1 -- 5
              11 -- 12
              2 -- 6
              8 -- 15
          }
          
          Now, this scheme will prevent connections being created that connect a node to itself, A -- A, but it will produce double connections between neighbors, A -- B and B -- A.

          Is that allowed in wumpus?
          Last edited by Heater on Sat Oct 17, 2020 7:13 am, edited 1 time in total.
          Memory in C++ is a leaky abstraction .

          lurk101
          Posts: 379
          Joined: Mon Jan 27, 2020 2:35 pm
          Location: Cumming, GA (US)

          Re: A Birthday Present for Fido

          Fri Oct 16, 2020 7:41 pm

          Heater wrote:
          Fri Oct 16, 2020 5:41 pm
          Now, this scheme will prevent connections being created that connect a node to itself, A -> A, but it will produce two way connections between neighbors, A -> B and B -> A.

          Is that allowed in wumpus?
          Depends by what you mean by a 'two way connection'. If by that you mean one edge of the graph, fine. If you mean 2 edges, then no.

          lurk101
          Posts: 379
          Joined: Mon Jan 27, 2020 2:35 pm
          Location: Cumming, GA (US)

          Re: A Birthday Present for Fido

          Fri Oct 16, 2020 7:53 pm

          ejolson wrote:
          Fri Oct 16, 2020 2:46 am
          The official worse is better way of dealing with such infinite loops appears to be introducing a counter that detects when the algorithm is stuck and then starts over from the beginning.
          Amazing what happens while asleep! I woke up understanding the futility of trying to fix a perceived bug that is not one at all, and the necessity of retries in the algorithm.

          Both the Unix version and my own version attempt the same strategy. Both algorithms start by creating a random Hamiltonian path of 20 rooms each with 2 tunnels. That leaves us with 10 edges to place in the graph. There is an easily fixed bug in the Unix version which can prevent it from creating that initial Hamiltonian path but that's not the problem. The real issue is that there is not always a valid combination of connections for the remaining 10 edges to the fixed Hamiltonian path. There usually is, but not always!

          ejolson
          Posts: 6596
          Joined: Tue Mar 18, 2014 11:47 am

          Re: A Birthday Present for Fido

          Fri Oct 16, 2020 8:01 pm

          Heater wrote:
          Fri Oct 16, 2020 5:41 pm
          Now, this scheme will prevent connections being created that connect a node to itself, A -> A, but it will produce two way connections between neighbors, A -> B and B -> A.

          Is that allowed in wumpus?
          Nice code and graphs! In my opinion your discussion should get included as comments in the source code. If only Microsoft had extended Visual Studio to allow formatted text and graphics in the comments when they controled the development tools, then open source projects could have copied their design and comments would be much more meaningful. Other than TempleOS and Donald Knuth's literate programming system, do you know of a development environment that allows the direct inclusion of graphs in comments?

          For Hunt the Wumpus in historic Unix on the PDP-11 and in OS/8 on the PDP-8, the randomly generated graphs are not directed, so you can always return from where you came by retracing your steps. Note that Gregory Yob's Wumpus 2 relaxed this constraint and allowed directed graphs. Having explored wild caves myself, I can verify that unless you are careful it can be very difficult to find your way back.

          At any rate, I prefer to draw graphs that correspond to caves without the arrows. The main point, however, is that in a directed graph the edge a->b and the edge b->a are different while in an undirected graph the edge a--b and b--a are the same and can't be counted twice My understanding is the graphs in Hunt the Wumpus also do not have edges of the form a--a.

          These two constraints are responsible for the infinite loops and the fail and then try again behaviour of existing Hunt the Wumpus graph generators.

          lurk101
          Posts: 379
          Joined: Mon Jan 27, 2020 2:35 pm
          Location: Cumming, GA (US)

          Re: A Birthday Present for Fido

          Fri Oct 16, 2020 8:35 pm

          Heater wrote:
          Fri Oct 16, 2020 5:41 pm
          Oh yeah, all the above as code in Rust
          Elegant! Worth translating back to Unix 7. In step 2 instead of 'any two nodes' shouldn't it be 'any two nodes which are not neighbors'?.

          Return to “Other projects”