Random array program eating my memory

Question

I wanted to write a perl program to generate array with non-repetitive single digit numbers of length 8(Numbers 1-8 in random order) and ninth element to be a underscore. I have written a code like this. I want to use this generated array for a number based puzzle game.

@mat = (0,0,0,0,0,0,0,0,0);

sub randgen { 

    $randigit = int(rand(9));

    if ($randigit == 0) {  
        &randgen;   
    }

    elsif (    $mat[0] == $randigit
            || $mat[1] == $randigit
            || $mat[2] == $randigit
            || $mat[3] == $randigit
            || $mat[4] == $randigit
            || $mat[5] == $randigit
            || $mat[6] == $randigit
            || $mat[7] == $randigit
            || $mat[8] == $randigit
          )
    {
        &randgen;
    }
}

&randgen;

for ( $assign = 0; $assign <= 8; $assign++) {

    $mat[$assign] = $randigit;
    print "@mat \n"; # To see to what extent the program has generated the array
    &randgen;
}

for ($i = 0; $i <= $#mat; $i++) {   

    $sum = $sum + $mat[$i];
}

$miss = 36 - $sum ;
$mat[7] = $miss;
$mat[8] = "_";
print "@mat \n";

The program After assigning 7th element, my program started eating memory(10 GB). I don't understand reason for that. I've used a mathematical logic to find the missing number(sum of numbers - 36 (n(n+1)/2)). Why is it eating my memory ? Or is there any effective way of writing the same program ?

Answer 1

Is there any effective way of writing the same program?

You bet. A few lines is all you need:

use List::Util 'shuffle';       # import shuffle
my @array = shuffle( 1 .. 8 );  # shuffle 1 to 8
push @array, '_';               # add the underscore

In one line:

my @array = ( shuffle( 1 .. 8 ), '_' );

Consider the following:

• Structure your sub to return a value
• Avoid writing &randgen; when randgen(); does the same thing
• Lexical scoping via my
• use strict; use warnings;
• Avoid making recursive calls where possible (this is probably the source of your memory consumption)

Answer 2

I haven't looked at what's eating your memory, but here's a simpler approach to achieving what you want:

#!/usr/bin/env perl
use strict;
use warnings;
use List::Util 'shuffle';

my @mats = shuffle 1 .. 8;
push @mats, '_';

print "@mats\n";

Sample output:

3 1 5 8 2 7 4 6 _

Answer 3

Of course, using shuffle is the One Right Way for your problem. This is a discussion about what went wrong with your code, and how such an algorithm could be expressed more elegantly.

Once you use warnings, you get a warning about deep recursion — the call stack is eating your memory. In your for-loop, you call randgen after the 8th element (index 7) was filled. In that case, the recursion condition is always true (as the eight elems are unique, there now is always an element for which $randigit is equal).

There are a few other things in your code that could be improved:

Loops like for ($i = MIN; $i <= MAX; $i++) are better written as foreach-loops:

for my $i (MIN .. MAX)

Subroutines can take parameters (these are in @_) and return values. This removes the need to use global variables to convey arguments.

Also, use strict; use warnings. This points out many errors, and forces you to declare all your variables (you can declare vars with my).

Here is an updated version of your code. It doesn't feature recursion, but a loop. And it works flawlessly:

#!/usr/bin/perl

use strict; use warnings;

# randgen takes
#   - the largest number that may be used, and
#   - a list of all forbidden numbers.
sub randgen { 
    my ($max, @forbidden) = @_; # unpack arguments
    my $rand;
    do {
        $rand = int rand($max + 1);
    } while grep {$_ == $rand} 0, @forbidden;
    return $rand;  # return the rand value.
}

my $digits = 8;
my @mat;  # don't prefill fields.
for ( 1 .. $digits ) {                 # do $digits times 
    push @mat, randgen($digits, @mat); # push appends item to array
    print "@mat\n";
}
push @mat, "_";

print "@mat\n";

Example output:

8
8 4
8 4 7
8 4 7 2
8 4 7 2 3
8 4 7 2 3 5
8 4 7 2 3 5 1
8 4 7 2 3 5 1 6
8 4 7 2 3 5 1 6 _

The grep builtin takes an expression or a block, plus a list of values. It returns all values to which the expression evaluates to true. The current item is accessible via $_. In my loop, it returns true as long as there is a value in @forbidden or the value 0 that is equal to $rand.