Labyrinth

[Equilibrilum]

Let's say we let a hamster run in a 3-dimensional labyrinth.

The labyrinth has a certain number of chambers and a certain number of tunnels connecting the chambers. Each tunnel connects two chambers.

We let the hamster in from one end of the labyrinth and it must come out from the other one.

All the tunnels are one-way. Also, the chambers and tunnels are positioned, so that the hamster can never go back to a chamber it has already been to.

The program itself has to count how many possibilities the hamster has to get from the releasing chamber to the chamber with the exit from the labyrinth.

We know the number of the chambers and we know the number of the tunnels. Every chamber has a number, so the hamster starts from chamber number 1 and ends in the last (the highest) numbered chamber.

We also know the number data of the tunnels (from which chamber can the hamster move to which chamber).

For example:

Chambers: 5
Tunnels: 6

Tunnels (A to 😎:
1 -> 2
1 -> 3
3 -> 4
4 -> 5
2 -> 3
3 -> 5

What kind of guidelines should I follow while solving the problem?

Thank you in advance!

[Weedpacket]

The ones you learned in class?

[Equilibrilum]

Everything I have learned I have learned by myself.

[Installer]

It seems the problem can be simply put like this:

These one-way tunnels exist:
1 -> 2
1 -> 3
3 -> 4 
4 -> 5
2 -> 3
3 -> 5
What are the possible paths from 1 to 5?

I don't know how to phrase any "guidelines" except as a solution:
Possible starting tunnels:
1 -> 2
1 -> 3
For each incomplete path add possible next tunnels:
1 -> 2, 2 -> 3
1 -> 3, 3 -> 4
1 -> 3, 3 -> 5 (complete)
For each incomplete path add possible next tunnels:
1 -> 2, 2 -> 3, 3 -> 4
1 -> 2, 2 -> 3, 3 -> 5 (complete)
1 -> 3, 3 -> 4, 4 -> 5 (complete)
For each incomplete path add possible next tunnels:
1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5 (complete)
No incomplete paths left, so done.

To do it programmatically, perhaps start with data structured like this:

$tunnels = array(1 => array(2, 3),
                 2 => array(3),
                 3 => array(4, 5),
                 4 => array(5));

[scrupul0us]

Give the directors of the movie "Cube" a call 😉

Good luck solving your problem, i will definitely be following along 🙂

you'll definitely be lookin at some calculus and using non-replacement permutations expressed as nPr, however that might not work 3-dimensionally

i got a 'D' in calc three so while I can point you in the direction, i can't help ya beyond there 🙂

[Installer]

The labarynth (as presented by op) is, of course, 2D, not 3D as op stated.

The code below will, I think, solve the problem, provided each room has a tunnel to at least one higher-numbered room and has no tunnels to itself or to a lower-numbered room. The last bit makes it slightly different, as op said the hamster can't go into a room it's already been in, not that it can't go to a lower-numbered room. But since the given setup shows no backward mobility I've kept it that way.

The setups were chosen arbitrarily from arrays generated by code that's too ugly to post.

Test data:

$setups = array(array(1 => array(2, 3),  // 5 rooms, op's problem
                      2 => array(3),
                      3 => array(4, 5),
                      4 => array(5)),
                array(1 => array(3, 4, 6),  // 6 rooms
                      2 => array(3, 5),
                      3 => array(4, 5, 6),
                      4 => array(5),
                      5 => array(6)),
                array(1 => array(2, 4),  // 7 rooms
                      2 => array(3, 5),
                      3 => array(4, 5, 7),
                      4 => array(5, 7),
                      5 => array(6, 7),
                      6 => array(7)),
                array(1 => array(3),  // 8 rooms
                      2 => array(3, 4),
                      3 => array(4, 5, 8),
                      4 => array(6, 7),
                      5 => array(6, 7),
                      6 => array(7),
                      7 => array(8)),
                array(1 => array(2, 3, 5, 7),  // 9 rooms
                      2 => array(3, 4),
                      3 => array(4, 5, 8, 9),
                      4 => array(6, 7),
                      5 => array(6, 7),
                      6 => array(7, 9),
                      7 => array(8),
                      8 => array(9)));

foreach ($setups as $setup_num => $rooms) {
    $first_room = 1;
    $last_room  = count($rooms) + 1;
    $incomplete_paths = array(array($first_room));
    $complete_paths   = array();
    while (!empty($incomplete_paths)) {
        $paths = array();
        foreach ($incomplete_paths as $key => $each_path) {
            if (end($each_path) == $last_room) {
                $complete_paths[] = $each_path;
            } else {
                foreach ($rooms[end($each_path)] as $dest_room) {
                    $tmp     = $each_path;
                    $tmp[]   = $dest_room;
                    $paths[] = $tmp;
               }
            }
        }
        $incomplete_paths = $paths;
    }

echo '<pre>';
echo 'Setup ' . $setup_num . ' has ' . count($complete_paths) . ' solutions<br />';
print_r($complete_paths);
echo '</pre>';
}