Beginning Perl - Sneak Peek

In my chapter on subroutines, I need to explain recursion. One example program I give draws mazes recursively. Here's a variation of the program, somewhat expanded beyond the book example.

Note that most of the "big comments" in this cover things a bit beyond my sample code. That's because I want the downloadable version to "redraw" the maze while it's building it. The code in the book is much simpler because I want the reader to focus on recursion and not get distracted by the bells and whistles.

#!perl

use strict;
use warnings;
use diagnostics;
use List::Util 'shuffle';

# The size of the maze. Take the arguments from the command line or from the
# default.
my ( $HEIGHT, $WIDTH ) = @ARGV ? @ARGV : ( 20, 20 );

# Time::HiRes was officially released with Perl 5.8.0, though Module::Corelist
# reports that it was actually released as early as v5.7.3. If you don't have
# this module, your version of Perl is probably over a decade old
use Time::HiRes 'usleep';

# In Perl, $^O is the name of your operating system. On Windows (as of this
# writing), it always 'MSWin32'.
use constant IS_WIN32 => 'MSWin32' eq $^O;

# On windows, we assume that the command to clear the screen is 'cls'. On all
# other systems, we assume it's 'clear'. You may need to adjust this.
use constant CLEAR => IS_WIN32 ? 'cls' : 'clear';

# We will only redraw the screen (and thus show the recursive maze generation)
# if and only if the system is capable of clearing the screen. The system()
# command returns 0 upon success. See perldoc -f system.
# The following line works because $x == $y returns a boolean value.
use constant CAN_REDRAW => 0 == system(CLEAR);

# Time in microseconds between screen redraws. See Time::HiRes and the usleep
# function
use constant DELAY => 10000;

use constant OPPOSITE_OF => {
    north => 'south',
    south => 'north',
    west  => 'east',
    east  => 'west',
};

my @maze;

sub tunnel {
    my ( $x, $y, $maze ) = @_;

    if (CAN_REDRAW) {
        my $render = render_maze($maze);
        system(CLEAR);
        print $render;
        usleep DELAY;
    }

    # Here we need to use a unary plus in front of OPPOSITE_OF so that
    # Perl understands that this is a constant and that we're not trying
    # to access the %OPPOSITE_OF variable.
    my @directions = shuffle keys %{ +OPPOSITE_OF };

    foreach my $direction (@directions) {
        my ( $new_x, $new_y ) = ( $x, $y );

        if    ( 'east'  eq $direction ) { $new_x += 1; }
        elsif ( 'west'  eq $direction ) { $new_x -= 1; }
        elsif ( 'south' eq $direction ) { $new_y += 1; }
        else                            { $new_y -= 1; }

        if ( have_not_visited( $new_x, $new_y, $maze ) ) {
            $maze->[$y][$x]{$direction} = 1;
            $maze->[$new_y][$new_x]{ OPPOSITE_OF->{$direction} } = 1;

            # This program will often recurse more than one hundred levels
            # deep and this is Perl's default recursion depth level prior to
            # issuing warnings. In this case, we're telling Perl that we know
            # that we'll exceed the recursion depth and to now warn us about
            # it
            no warnings 'recursion';
            tunnel( $new_x, $new_y, $maze );
        }
    }
}

sub have_not_visited {
    my ( $x, $y, $maze ) = @_;

    # the first two lines return false  if we're out of bounds
    return if $x < 0 or $y < 0;
    return if $x > $WIDTH - 1 or $y > $HEIGHT - 1;

    # this returns false if we've already visited this cell
    return if $maze->[$y][$x];

    # return true
    return 1;
}

tunnel( 0, 0, \@maze );

system(CLEAR) if CAN_REDRAW;
print render_maze( \@maze );

sub render_maze {
    my $maze = shift;

    my $as_string = "_" x ( 1 + $WIDTH * 2 );
    $as_string .= "\n";

    for my $y ( 0 .. $HEIGHT - 1 ) {
        $as_string .= "|";
        for my $x ( 0 .. $WIDTH - 1 ) {
            my $cell = $maze->[$y][$x];
            $as_string .= $cell->{south} ? " " : "_";
            $as_string .= $cell->{east}  ? " " : "|";
        }
        $as_string .= "\n";
    }
    return $as_string;
}

You may think it uses far too may "global" type variables at the top and you'd be right, particularly since the subroutine is accessing data declared outside of itself, but for a small one-off script designed to show recursion, it's just fine.

Have fun!

Update: Here's a sample maze it prints out.

_________________________________________
| |_ _   _ _ _    |  _  |   |   |  _ _  |
| |   |  _|  _ _| |_  | |_|  _|_ _|   | |
| | | |_|  _|   |_ _ _|_  |_ _  |  _|_ _|
|_ _|_  | |  _|_ _ _  |  _|  _ _|_ _ _  |
| |  _ _| | |   |  _ _| |_ _ _|   |  _  |
| | |  _ _|  _|_|_ _  | |  _  | |_ _|  _|
| | |  _ _ _|   |  _ _|_ _| |_ _|  _|_  |
| | | |_  |  _|_ _|     |_ _   _|  _  | |
| | |_   _|_ _  |  _| |_ _ _  |  _| | | |
|  _|  _|   |  _|_ _|_  |   | |_  | |_ _|
|_  |_|  _|_ _|  _ _   _|_|_ _  | |  _  |
| |_  |_    |  _|_ _ _|  _ _  | | |_ _| |
|  _|_  |_| |  _ _ _ _ _| |   |_|_ _ _  |
|  _  | |  _| |  _   _ _ _| |_|     |  _|
|_  |_ _| |  _|_ _|  _ _  | |  _| |_| | |
| | |_   _| |  _  | | |  _|_ _| | |  _| |
| |_ _ _|  _| |  _|_  | |     | |_ _|   |
|  _  |  _|  _| |_ _ _|  _| | |  _  | | |
|_  | | |  _| | |  _  |_|  _|_ _| | |_| |
|_ _|_ _ _|_ _ _ _|_ _ _ _|_ _ _ _ _ _ _|

9 Comments

If you use "#!perl" as shebang line. you will not able to execute your script like the following. $ chmod a+x maze.pl $ ./maze.pl -bash: ./maze.pl: perl: bad interpreter: No such file or directory $

If you want to take the first perl in $PATH, use "#!/usr/bin/env perl" instead.

http://www.perlmonks.org/?node_id=716740

@Ovid For all i know, Windows ignores the shebang line. Exceptionall, Apache interprets shebang paths even in windows. It can be avoided with the following instructions.

http://stackoverflow.com/questions/2036577/how-do-i-ignore-the-perl-shebang-on-windows-with-apache-2

http://www.imladris.com/Scripts/PythonForWindows.html

(comment may be repeat; I have no faith in Movable Type).

Maybe just drop the shebang in the sample scripts?

The lines in the comments are too long for the blog and get cropped (by overflow: hidden css).

I'm not too fond of use constant; it trips up newbies who think it actually does something (string interpolation is the usual tripping point). Might just as well rewrite things like

use constant DELAY => 10000;

as:

sub DELAY { 10000 };

which is shorter and more informative for people reading the code: you're declaring a policy, not a fixed value that can be optimized away (although probably it can).

Anyway, isn't Const::Fast the current module of choice for this? Or does it not support older perls?

Note, that OPPOSITE_OF is not really a constant. Or to be exact it is constant reference to non-constant hash.

cool, it's work;)

Great piece of code! My only question is where is the entry point? The outer border is solid and unbroken so where do I begin my trek through the maze? Thanks.

Leave a comment

About Ovid

user-pic Have Perl; Will Travel. Freelance Perl/Testing/Agile consultant. Photo by http://www.circle23.com/. Warning: that site is not safe for work. The photographer is a good friend of mine, though, and it's appropriate to credit his work.