Maybe it’s been the heat, but I’ve been a little run down lately, so I’ve been doing some serious … resting … on the weekends lately, as well as finding some simple, short-term problems to engage my programming faculties on.
I think too much multi-tasking, or multi-tasking during the wrong phase of programming, can train your brain into becoming a “make a start”er, and I like not to slip into that, so I like to find a problem or two that I figure I can tackle fairly quickly, and that I can only tackle if I can get my brains attention on it.
My only issue is that I won’t solve abstract problems. They have to be practical to me in some sense, so it can take a little effort finding a problem on which I will engage in all aspects.
This weeks problem, I will present for your entertainment, but in an abstract form ;)
The object is to traverse from a starting node in a network to an ending node. For each evaluation we are given a different network topography and linkage.
The nodes in the network are variously connected via unidirectional links, each having 4 outgoing links to other nodes. One link is always to the next node in the path for this network, while the destination of the others is unknown, but usually back down the path.
Links are one way: If node 5 links to node 6, then it will merely be coincidince if node 6 also links to node 5.
Each node always has four outgoing connections, although the connection may lead back to the same node.
You always – can only – start at node 1.
Should be simple, but here is the catch:
You cannot see inside the network.
For any given path the network shows three resulting states:
– GOAL: Reached (or passed thru) goal node,
– Middle: Terminated in the “middle” of the network,
– Start: Terminated (or failed to leave) the first node
The branches between nodes are always the same, e.g. node 1 always has one connection to node 2.
And if you want to try it out…
telnet ww2.kfs.org 9890
The network is regenerated each time you connect so, for example, you can start by inputting four simple paths:
* Enter Path: 4
Attempt #1 … 4 : reached Middle in 1 steps
* Enter Path: 3
Attempt #2 … 3 : reached Start in 1 steps
* Enter Path: 2
Attempt #3 … 2 : reached Start in 1 steps
* Enter Path: 1
Attempt #4 … 1 : reached Start in 1 steps
I dabbled with a variety of approaches to solving it, mostly in Perl. The first was messing with AI::Genetic, while the second was a slightly more hands-on, brute force approach, but that generates an awful lot of attempts on a standard run.
If you want to take a crack at it, feel free to have your client connect to my little app above to try out your theories :)