Snowplough Turns

[DDRM]

Santa’s toy factory site has been buried in snow! It is necessary to clear paths (blue lines, with numbers) between the different workshops (shown by letters), but it is hard work, and the elves are very busy, so they only want to clear the easiest route that will ensure all sites can be reached. The diagram below shows the effort involved for each path, but not all routes need to be cleared. What is the lowest number of elf-hours that will allow all sites to be reached from any other?

Hint: you are looking for a “minimum spanning tree”: there is a very “Prim” algorithm for this!

[Richard Russell]

I asked DeepSeek "Can you write a BBC BASIC program for the Prim Minimum Spanning Tree algorithm?". This was its response:

Certainly! Below is a BBC BASIC program that implements Prim's algorithm to find the Minimum Spanning Tree (MST) of a connected, undirected graph. The program assumes that the graph is represented as an adjacency matrix.

Code: Select all

   10 REM Prim's Minimum Spanning Tree Algorithm
   20 DIM graph(4,4), key(4), parent(4), inMST(4)
   30 INF = 9999
   40 V = 5  REM Number of vertices in the graph
   50 
   60 REM Example graph represented as an adjacency matrix
   70 graph(0,0) = 0  : graph(0,1) = 2  : graph(0,2) = 0  : graph(0,3) = 6  : graph(0,4) = 0
   80 graph(1,0) = 2  : graph(1,1) = 0  : graph(1,2) = 3  : graph(1,3) = 8  : graph(1,4) = 5
   90 graph(2,0) = 0  : graph(2,1) = 3  : graph(2,2) = 0  : graph(2,3) = 0  : graph(2,4) = 7
  100 graph(3,0) = 6  : graph(3,1) = 8  : graph(3,2) = 0  : graph(3,3) = 0  : graph(3,4) = 9
  110 graph(4,0) = 0  : graph(4,1) = 5  : graph(4,2) = 7  : graph(4,3) = 9  : graph(4,4) = 0
  120 
  130 REM Initialize key values and MST set
  140 FOR i = 0 TO V-1
  150   key(i) = INF
  160   inMST(i) = FALSE
  170 NEXT i
  180 
  190 REM Start with the first vertex
  200 key(0) = 0
  210 parent(0) = -1  REM First node is the root of MST
  220 
  230 REM Construct MST
  240 FOR count = 0 TO V-1
  250   REM Find the vertex with the minimum key value
  260   min = INF
  270   u = -1
  280   FOR v = 0 TO V-1
  290     IF inMST(v) = FALSE AND key(v) < min THEN
  300       min = key(v)
  310       u = v
  320     ENDIF
  330   NEXT v
  340 
  350   REM Add the found vertex to the MST set
  360   inMST(u) = TRUE
  370 
  380   REM Update key values and parent index of adjacent vertices
  390   FOR v = 0 TO V-1
  400     IF graph(u,v) > 0 AND inMST(v) = FALSE AND graph(u,v) < key(v) THEN
  410       parent(v) = u
  420       key(v) = graph(u,v)
  430     ENDIF
  440   NEXT v
  450 NEXT count
  460 
  470 REM Print the constructed MST
  480 PRINT "Edge   Weight"
  490 FOR i = 1 TO V-1
  500   PRINT parent(i); " - "; i; "    "; graph(i, parent(i))
  510 NEXT i
  520 
  530 END

And it offered the following explanation of the code:

• Lines 10-110: Define the graph as an adjacency matrix. The graph is a 5x5 matrix where graph(i,j) represents the weight of the edge between vertex i and vertex j. A value of 0 indicates no edge.
  
  
• Lines 140-170: Initialize the key array to store the minimum weight edge to connect each vertex to the MST, and the inMST array to keep track of vertices included in the MST.
  
  
• Lines 200-210: Start with the first vertex (vertex 0) and set its key to 0 (since it's the starting point) and its parent to -1 (indicating it's the root).
  
  
• Lines 240-450: The main loop of Prim's algorithm. It iterates over all vertices, selecting the vertex with the minimum key value that is not yet in the MST, adds it to the MST, and updates the key values of its adjacent vertices.
  
  
• Lines 480-510: Print the edges of the MST along with their weights.

Notes:

• The program assumes that the graph is connected. If the graph is not connected, the algorithm will only find the MST for the connected component containing the starting vertex.
  
  
• The graph is hardcoded in this example, but you can modify the program to read the graph from user input or a file if needed.

Plugging in the challenge parameters, and after a minor tweak to the output routine to show letters rather than numbers (where N is the warehouse and O is the sleigh loading) this is what the otherwise unmodified DeepSeek program produces. I have no idea if it is correct (DDRM?).

Code: Select all

Edge   Weight
A - B    5
B - C    3
C - D    4
D - E    2
E - F    2
F - G    3
G - H    4
H - I    4
I - J    8
H - K    6
C - L    5
D - M    4
J - N    2
N - O    4

The total is 56 hours.

[Richard Russell]

This is the change I made to the DeepSeek program to plug in the challenge parameters:

Code: Select all

   20 DIM graph(14,14), key(14), parent(14), inMST(14)
   30 INF = 9999
   40 V = 15  REM Number of vertices in the graph
   50
   60 REM Graph represented as an adjacency matrix (N = warehouse, O = sleigh loading)
   70 graph() = 0,5,0,0,0,0,0,0,0,12,0,0,0,0,0, \ A - B, A - J
   80 \         5,0,3,0,0,0,0,0,0, 0,8,0,0,0,0, \ B - A, B - C, B - K
   90 \         0,3,0,4,0,0,0,0,0, 0,0,5,0,0,0, \ C - B, C - D, C - L
  100 \         0,0,4,0,2,0,0,0,0, 0,0,0,4,0,0, \ D - C, D - E, D - M
  110 \         0,0,0,2,0,2,0,0,0, 0,0,0,6,0,0, \ E - D, E - F, E - M
  120 \         0,0,0,0,2,0,3,0,0, 0,0,0,5,0,0, \ F - E, F - G, F - M
  130 \         0,0,0,0,0,3,0,4,0, 0,0,5,0,0,0, \ G - F, G - H, G - L
  140 \         0,0,0,0,0,0,4,0,4, 0,6,0,0,0,0, \ H - G, H - I, H - K
  150 \         0,0,0,0,0,0,0,4,0, 8,0,0,0,0,0, \ I - H, I - J
  160 \        12,0,0,0,0,0,0,0,8, 0,8,0,0,2,0, \ J - A, J - I, J - K, J - N
  170 \         0,8,0,0,0,0,0,6,0, 8,0,7,0,0,0, \ K - B, K - H, K - J, K - L
  180 \         0,0,5,0,0,0,5,0,0, 0,7,0,5,0,0, \ L - C, L - G, L - K, L - M
  190 \         0,0,0,4,6,5,0,0,0, 0,0,5,0,0,0, \ M - D, M - E, M - F, M - L
  200 \         0,0,0,0,0,0,0,0,0, 2,0,0,0,0,4, \ N - J, N - O
  210 \         0,0,0,0,0,0,0,0,0, 0,0,0,0,4,0  REM O - N

[DDRM]

Nice! Looks about right, though I can't remember the solution, if I ever worked it out...

So do you reckon programming is becoming like chess? People will do it only as a recreational activity (which, to be fair, is all these problems were meant to be), with computer analysis of whether the solution is correct/optimal?



D

[Richard Russell]

So do you reckon programming is becoming like chess? People will do it only as a recreational activity (which, to be fair, is all these problems were meant to be), with computer analysis of whether the solution is correct/optimal?

I don't think we're in any danger of machines taking over from human programmers any time soon! But when it comes to implementing a standard algorithm, or any piece of self-contained code the functionality of which can be succinctly described, an AI is likely to be able to do it more quickly and with a lot less effort than a human.

What's changed with DeepSeek, it seems to me, is that the likelihood of the AI writing complete and correct code has increased markedly. In this case I made no changes at all, other than to plug in your data; the output modifications were cosmetic only.

[Richard Russell]

On 04/02/2025 16:01, Richard Weir via groups.io wrote:

If AI does develop to the point where it can usefully generate solutions to larger applications, then a different human skill will be required: the ability to unambiguously, accurately and concisely specify the nature of the problem. This a skill which is seriously lacking in human programming endeavours...

Is it really "seriously lacking"? Don't professional programmers always start by describing what is needed in a very 'high level' way, before any actual coding takes place? I'd like to think so!

[DDRM]

Don't professional programmers always start by describing what is needed in a very 'high level' way, before any actual coding takes place? I'd like to think so!

So my software engineering courses demanded! More recent "agile" approaches also involve revisiting requirements regularly throughout the development process.

Perhaps what Richard was getting at is that software engineers aren't always very good at agreeing with the user group / understanding exactly what is required - so the software may be beautifully engineered, and (almost) free of bugs, but still not really fulfill the user's needs...



D

[Richard Russell]

Nice! Looks about right, though I can't remember the solution, if I ever worked it out...

I don't know anything about the Prim algorithm - I'd never even heard of it before you published your challenge - but since the array contains each weight twice do I conclude that it's possible to specify different weights for A->B and B->A say (such as might be the case in your example if one direction is uphill and the other downhill)?

[DDRM]

Hi Richard,

My diagram showed what is called an undirected graph: all the links are bidirectional, and have equal weighting in each direction. I think that is an assumption of Prim's algorithm. That means you could, in principle, store the links more compactly, without duplication.

Prim's algorithm is basically:
1) start with any node. This is your starting "tree".
2) Choose the lowest-cost edge that comes out of the tree, joining it to a node that is not yet included, and add it (attaching a new point).
3) Repeat (2) until all nodes are connected.

It's easier, and more efficient computationally, to have easy access to both "directions" in the array: it means that you don't need to go off searching for all the connections from this node to other ones, particularly given that you are allowed an arbitrary starting node.

What you describe, with different weights in the two directions, is called a directed graph (and actually you'd normally show the two directions as distinct arrows): in the limiting case the weight in one direction might be infinite (you can't go that way!) - that's actually very common.

I don't think Prim's algorithm is guaranteed to work on directed graphs: consider a situation where you are going to have to connect a node through a very expensive link (because that's the only way in), but it might then provide a very cheap route to some other nodes that you can reach more expensively through other routes.

A ----- 25 -----> B
. |
. |
. |
10 2
. |
. |
. v
> C

Here, Prim would add A - C first, but then be forced to add A - B, for a total cost of 35.
Better would be to add A - B and B - C, for a total cost of 27
(Also, since I haven't given any backward paths, it would fail if you started at B or C!).

Oh, sorry, that doesn't render well, does it? Basically it's a network with a directed arrow from A to B of cost 25, a directed arrow from A to C of cost 10, and a directed arrow from B to C of cost 2.

[Richard Russell]

I don't think Prim's algorithm is guaranteed to work on directed graphs

So, is the code that DeepSeek generated (I've not studied it at all) really an implementation of Prim's algorithm? If it is, I'm puzzled that the array representing the graph contains each weight twice: every array element graph(i,j) has the same value as the element graph(j,i).