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.

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

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 wrote: ↑Thu Oct 15, 2020 4:26 pmPrior to fuzzing, compliance testing is required no?ejolson wrote: ↑Thu Oct 15, 2020 4:07 pmYou 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.

I was thinking of using your graphing output to verify that the generated caves are Euler graphs.

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.

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

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?

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 .

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`

Code: Select all

```
$ sudo apt-get install lazarus
```

Memory in C++ is a leaky abstraction .

Impressive!

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

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.

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.

Yes, thanks. Installed a ton of dependencies!! libvorbis-dev no less.Heater wrote: ↑Thu Oct 15, 2020 5:38 pmI presume Free Pascal is working on the Pi4:Code: Select all

`$ sudo apt-get install fpc`

Not planning on doing GUI development, looks like a Delphi clone.And probably the Lazarus IDE for it:

Code: Select all

`$ sudo apt-get install lazarus`

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.

There is no need to install Lazarus, which in my opinion is mostly for coding up graphical interfaces.Heater wrote: ↑Thu Oct 15, 2020 5:38 pmI presume Free Pascal is working on the Pi4:And probably the Lazarus IDE for it:Code: Select all

`$ sudo apt-get install fpc`

Code: Select all

`$ sudo apt-get install lazarus`

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.

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 .

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

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.

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.

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.lurk101 wrote: ↑Fri Oct 16, 2020 12:44 amTrying 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.

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
```

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.

Here is what graphviz outputs for the dodecahedral maze.

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:

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.

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:

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:

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:

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:

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:

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:

Last edited by Heater on Sat Oct 17, 2020 7:02 am, edited 3 times in total.

Memory in C++ is a leaky abstraction .

Oh yeah, all the above as code in Rust:
Which outputs a dot format graph like so:
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?

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!("}}");
}
```

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
}
```

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 .

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.

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!

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.