The 7 Continents of the World

[DDRM]

After ditching his plan to use the “Three words” method, Santa decides to deliver his presents by doing a whole continent at once. Unfortunately, his sleigh has limited range, and can’t cross large ocean routes. Consider the map of possible intercontinental routes below. Is it possible for him to start and finish his trip in Europe using every route exactly once? If it is, what is that route? If it is not, can you make it possible by adding or removing exactly one route?

[Hated Moron]

Is it possible for him to start and finish his trip in Europe using every route exactly once? If it is, what is that route? If it is not, can you make it possible by adding or removing exactly one route?

I wouldn't have any idea how to tackle this by writing code, but if you are to return to your starting point having used every route exactly once there must be an even number of connections starting/ending where you are (half of them outbound, half return). Since on your map Europe has three such routes, no it isn't possible.

By inspection, removing the link from Europe to Asia would result in an even number of connections to every continent (four for Africa, two for each of the rest). But again I would have no idea how to tackle this by programming.

[DDRM]

Your analysis of the requirements is correct!

You could use a graph traversal method to do it programmatically?

Best wishes,

David

[Hated Moron]

You could use a graph traversal method to do it programmatically?

A what?! I've never heard of it (Google tells me "In computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited" but I'm not really any the wiser).

Do your challenges assume a Computer Science background then? My degree was in Physics (and there were no such thing as ICT classes when I was at school) so I've missed out on any formal Computer Science education. I've speculated before that the (relatively) poor performance of my interpreters, compared with Sophie's, may in part be a result of that.

In one of your replies you mentioned something about the challenges being suitable for novices, but I doubt if any 'novice' will have heard of Graph Traversal methods (unless it is now taught to everybody at school, which might mean young novices can tackle them!).

[DDRM]

Hi Richard,

I would say a formal approach to graph traversal comes under mathematics, rather than (or as well as!) computer science, and I'm quite surprised you didn't come across it in electrical engineering, because I'd have thought it would have lots of applications there, but there you are. It's quite an old field (see Bridges of Konigsberg - Euler solved this in 1736, according to Wikipedia).

In general, graphs are represented as a set of nodes (here the continents) and a set of edges (here the routes between them). Could you implement this as two arrays, perhaps with a marker to indicate which routes had been used, as well as its start and end points?

A slight complication is that routes can be used either way: you could put each edge in twice, but then you'd have to "cross them off" twice, so probably easier just to search both first and second ends of each edge when trying your path.

A simple approach would be a recursive depth-first search, starting in Europe, and marking off the edges as you go (probably on a local copy each time, to avoid having to "erase" marks when a route failed).

There are clever route-finding algorithms, but for a problem of this size they aren't necessary!

Best wishes,

D

[KenDown]

Actually Euler did not solve the bridge problem. He merely demonstrated that a solution is not possible (with the mathematical proof).

The Wikipedia article claims that the bridges problem had significance for topology, without explaining, but in fact topology allows of a solution. Euler's discovery is perfectly correct for a 2D plane, but as Konnisberg is situated on 3D globe, one can solve the problem - ie. cross all seven bridges just once - by travelling all the way round the globe. Thus one can fulfil the terms of the puzzle because you have not crossed the river except by one of the seven bridges.

If we represent the bridges thus:

1 2
3
4 5
6 7

and confine ourselves to the plane it is impossible. But if we start on the lower island and cross the bridges in this order: 6,4,5,2,1,round the world,7,3 (other solutions are possible) the puzzle is solved.

So far as I know, a 2D world is not one of the specifications of the problem.

[Hated Moron]

I would say a formal approach to graph traversal comes under mathematics, rather than (or as well as!) computer science

I only did mathematics to A-level, I certainly don't remember (more than 50 years later) 'graph traversal' being in the syllabus.

I'm quite surprised you didn't come across it in electrical engineering

As I said, my higher education was in physics (a degree from Oxford). I've no more had any teaching in electrical engineering than I have in computer science. My career was in electronics (entirely self-taught).

It's worthy of note that the Oxford physics course involved no mathematics teaching (A-level assumed good enough) whereas Oxford engineering - which was a 4 year course rather than 3 - involved a lot of mathematics teaching. It's one reason why I chose physics (or it was chosen for me by my school) because I was never that good at maths.

And before you point out that I am M.I.E.T. (which you might think means I am/was an electrical engineer) I should explain that I was originally a member of I.E.R.E. (Institution of Electronic and Radio Engineers) which got absorbed, first into the I.E.E. and then into the I.E.T.

In general, graphs are represented as a set of nodes (here the continents) and a set of edges (here the routes between them). Could you implement this as two arrays, perhaps with a marker to indicate which routes had been used, as well as its start and end points?

No idea. I rather assumed you knew how to solve the challenges before setting them! Perhaps I can set you the challenge of solving the 'Seven Continents of the World' using code this advent season.

[DDRM]

Hi Richard,

Interesting background!

Yes, I'll post some code after I've finished all my current coursework. It may be a bit of a challenge, since my mind is full of Python at the moment...



D

[DDRM]

Kendall, The surface of the world is still a 2D surface (give or take some fractal arguments), though a closed one....
... and the formulation of the problem does not include transoceanic routes - maybe they didnt have Santa's magical (but apparently limited) sledge...

Anyway, I'd say that proving a solution is not possible IS a solution to the puzzle, since the puzzle was "is it possible"!



D

[Hated Moron]

It may be a bit of a challenge, since my mind is full of Python at the moment...

Do you actually like Python, or are you forced to use it? During my professional career I used BBC BASIC whenever I could, of course, and whilst there were occasionally raised eyebrows nobody ever tried to stop me! And I wasn't the only one: Alan Roberts (the BBC's top colorimetry expert until he retired) used BBC BASIC extensively in his work.

If you' consider Python to have any significant advantages over BBC BASIC (other than popularity!) I'd certainly be interested to know what you think they are. It does have more data types, and there are some interesting 'collection' types (with associated operators), but I'm not convinced that they make coding any easier or the resulting program any clearer.

The main thing I dislike about Python is, you won't be surprised to hear, the way whitespace is significant to the syntax. It must be almost unique in that respect, with the vast majority of other languages delimiting blocks either with symbols like { ... } or keywords like BEGIN ... END or structures like BBC BASIC's REPEAT ... UNTIL, WHILE ... ENDWHILE.

I would say the 'killer' advantage of BBC BASIC over Python is the cross-platform support, when you include graphics, sound, shader code, Box2D etc. in the mix. Yes Python itself will run on a lot of platforms, even in a browser (sort of) using PyScript, but try using it to write, say, a video game that must run on all major desktop and mobile platforms, and in a browser! You'll be lucky if all the libraries you need are available.

But I must admit Python has done BBC BASIC one favour - it's made a slow, interpreted, language fashionable! No more do I have to make excuses for BBC BASIC's speed compared with, say, a compiled language like C; I can just point to Python!