CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Beginner:
Creating a 100x100 grid in perl

 



minorsecond
New User

Sep 23, 2012, 12:17 PM

Post #1 of 10 (2518 views)
Creating a 100x100 grid in perl Can't Post

Hey everyone!

I'm writing code for an epidemiology class in which I'm supposed to have a random walker take 100 steps and determine the probability that it will become infected by walking over a contaminant. The grid on which the walker walks is 100x100. The walker is to begin at a random location on the grid.

My partner has done the bulk of the work so I'm trying to finish it up but I just can't seem to figure out how to limit the grid size. How do I make it so that the walker will either not make a move if the step would land it outside of the grid, or roll it over the other other side of the grid if it steps over the border?

Please don't think I'm asking you to do my work for me. I want to learn how to do this as I may use this again in the future.

Thank you so much!


Code
#!/usr/bin/perl -w 
# use strict;
use warnings;

# purpose: 2 dimensional random walk + Probability of infection
# First Computational epidemiology homework, Sept 26 2012.
# usage: perl HW1.pl

my $file_out = ">HW1.out";
my $cont_out = ">cont.out";
my $NO_OF_STEPS;
my $NO_OF_RUNS;

# use the perl open function to open the files
open(FILE_OUT, $file_out) or die "Could not open write $file_out, program halting.";
open(CONT_OUT, $cont_out) or die "Could not open $cont_out, program halting.";

# Number of steps in each walk
$NO_OF_STEPS = 100;

# # Number of runs or times the random walk is done
$NO_OF_RUNS = 100;

#declarations of variables
my %hash_walker_pos; #hash to store X positions
my $xpos_walker = 0;
my $ypos_walker = 0;
my %hash_cont_pos; #hash to store Y positions
my $ypos_cont;
my $xpos_cont;
my $xpos;
my $ypos;
my $dist_from_origin;
my $expected_dist;
my $count = $NO_OF_RUNS; #counter
my @all_expected_dist;
my $i;
my $j;
my $k;
my $random_num;
my @sum_cont_dist;
my $expected_dist_cont;
my $rangex = 2;
my $rangey = 2;
my $range_contx = 100;
my $range_conty = 100;
my $random_num_contx;
my $random_num_conty;
my $random_num_x;
my $random_num_y;
my @xpos_Arr;
my @ypos_Arr;
my $count_found = 0;
my $count_not_found =0;
my $count_run = 0;
my $count_total = 0;
my $probability;

# make STDIN for number of steps
# print "Number of steps? \n";
# my $NO_OF_STEPS = <>;

# # Make STDIN for number of steps
# print "Number of runs? \n";
# my $NO_OF_RUNS = <>;

#make STDIN for the number of contaminants
print "Number of contaminants?\n";
my $number_contaminant = <>;

#put srand funtion
{
srand (3)

}
#Create contaminants random positions
for ($k = 0; $k <$number_contaminant; $k++)
{

#random positions of the contaminants, put the random number as integrer
$random_num_contx = int(rand($range_contx));
$random_num_conty = int(rand($range_conty));

#Storing contaminant positions into hash
$xpos_cont = $random_num_contx;
$ypos_cont = $random_num_conty;
$hash_cont_pos{$xpos_cont}= $ypos_cont;

#Print contaminant file.
print CONT_OUT "$k Cont_xpos\t".$xpos_cont. "\t Cont_ypos\t".$ypos_cont."\n";
}


#Seed random number generator for walker
{
srand (5)
}

#Outer while loop to run specified number of walks
while($count > 0)
{
#initialize this values here to start over on each run
@xpos_Arr = ();
@ypos_Arr = ();
$xpos_walker = 0;
$ypos_walker = 0;
push(@xpos_Arr,"0");
push(@ypos_Arr,"0");

#Inner loop to perform each step of a random walk
for ($i = 0 ; $i < $NO_OF_STEPS; $i++)
{
#random positions of the walker, the random number is integrer
$random_num_x = int(rand($rangex));
$random_num_y = int(rand($rangey));

#Storing xpos, ypos into designated arrays
push(@xpos_Arr,$random_num_x);
push(@ypos_Arr,$random_num_y);

#creating x and y current position after sum the previous and store in hash
if($i == 0)
{
#this is only for the first position
$xpos_walker = $xpos_Arr[$i+1];
$ypos_walker = $ypos_Arr[$i+1];
}
else
{
$xpos_walker = $xpos_Arr[$i+1] + $xpos_walker;
$ypos_walker = $ypos_Arr[$i+1] + $ypos_walker;
$hash_walker_pos{$xpos_walker}= $ypos_walker;
}

#print the position of the walker each time
print FILE_OUT "xpos = $xpos_Arr[$i+1] ypos = $ypos_Arr[$i+1]\n";
print FILE_OUT"$i xpos\t".$xpos_walker. "\typos\t".$ypos_walker."\n";
}
$count --;

#compare both hashes with positions to see if walker gets the contaminant
my $found = 0;
my $count_found = 0;

foreach $xpos_cont (keys %hash_cont_pos)
{
if(exists($hash_walker_pos{$xpos_cont}))
{
if ($hash_walker_pos{$xpos_cont} eq $hash_cont_pos{$xpos_cont})
{
$found=1;
#print "found equal position\n";
$count_found ++;
$count_total ++;
}
}
if ($found != 1)
{
#print "not equal position\n";
$count_not_found ++;
}
else
{
$found=0;
}
}
if($count_found > 0)
{
$count_run ++;
}
}

#Calculate Probability
{
$probability = ($count_run / 100);
}

print "Total steps in all runs that infected the walker= $count_total\n";
print "Runs that infected walker = $count_run\n";
print "Probability of infection = $probability\n";


#calculate probability


#Averaging distance to compute expected distance
#$expected_dist = $expected_dist/$NO_OF_RUNS;
#print "Distance from origin: $expected_dist\n";
#print "cont n1 = $n1\ncont n5 = $n5[0]\ncont n10 = $n10[0]\ncont n20 = $n20[0]\ncont n50 = $n50[0]\ncont n100 = $n100[0]\n";

close FILE_OUT;



minorsecond
New User

Sep 23, 2012, 12:43 PM

Post #2 of 10 (2516 views)
Re: [minorsecond] Creating a 100x100 grid in perl [In reply to] Can't Post

I want to add that I just added code that doesn't seem to throw any errors. I 'think' it may be limiting the walker to the grid by adding 1 back to the run count. I put it in lines 140-149.

Do you think this works as intended?



Code
	#Check to see if walker is attempting to leave grid. Else, subtract 1 from count. Does this work? 
{
if ($xpos_walker > 100) {
$count ++
} elsif ($ypos_walker > 100) {
$count ++
} else {
$count --;
}
}



BillKSmith
Veteran

Sep 23, 2012, 2:00 PM

Post #3 of 10 (2512 views)
Re: [minorsecond] Creating a 100x100 grid in perl [In reply to] Can't Post

I have not had a chance to look at your code yet. I like the idea of "roll over". In that case your walker would be an ant walking on a contaminated doughnut. (Really, imagine your number grid laid out on the doughnut. One coordinate goes from 99 back to zero when he steps through the hole. The other coordinate goes from 99 back to zero when he finishes a complete lap around the doughnut without going through the hole.)

You implement the roll over with the mod operator (% in perl)


Code
x = (x+1) % 100;

Good Luck,
Bill


Chris Charley
User

Sep 23, 2012, 5:57 PM

Post #4 of 10 (2499 views)
Post deleted by Chris Charley [In reply to]

 


BillKSmith
Veteran

Sep 23, 2012, 9:08 PM

Post #5 of 10 (2489 views)
Re: [minorsecond] Creating a 100x100 grid in perl [In reply to] Can't Post

 Your original code has serious errors. First, lets agree on exactly what we mean by a "random walk" on a two dimensional grid. I believe that each step should be to one of the four positions (forward, backward, right, or left) with equal probability for each. Diagonal steps are not allowed. It is not clear what you intend.

Your use of hashes( %hash_walker_pos and %hash_cont_pos) to store lists of positions will not work. Whenever an x-position is repeated, the existing key will be reused. The existing y-value will be overwritten. The proper data structure depends in part on the expected length of these lists.
Good Luck,
Bill


minorsecond
New User

Sep 24, 2012, 6:57 AM

Post #6 of 10 (2482 views)
Re: [Chris Charley] Creating a 100x100 grid in perl [In reply to] Can't Post

Thanks, Chris. This is way better than what my partner and I wrote. I'll see what I can do to implement it in a way that I understand. The only problem I see with the application of your code to our "experiment" is that it isn't repeatable. That's the reason I was using srand. So I see that you randomly assigned 1s and 0s to each grid position and made the 1s contaminated spaces. Where is the code for the walker? Finally, how would one make this repeatable? Thanks again!


Quote
Your original code has serious errors. First, lets agree on exactly what we mean by a "random walk" on a two dimensional grid. I believe that each step should be to one of the four positions (forward, backward, right, or left) with equal probability for each. Diagonal steps are not allowed. It is not clear what you intend.

Your use of hashes( %hash_walker_pos and %hash_cont_pos) to store lists of positions will not work. Whenever an x-position is repeated, the existing key will be reused. The existing y-value will be overwritten. The proper data structure depends in part on the expected length of these lists.
Good Luck,
Bill


Correct. We only have up, down, left and right. The original code that our TA gave as an example included some code, which I think you are referring to. I added it at the bottom of this reply.


Code
#Storing xpos, ypos into designated arrays 
$xposArr[$i] = $xpos;
push(@yposArr, $ypos);
if($random_num < 0.25) {
$xpos--;
} elsif ($random_num < 0.5) {
$xpos++;
} elsif ($random_num < 0.75) {
$ypos--;
} else {
$ypos++;
}



Laurent_R
Veteran / Moderator

Sep 24, 2012, 11:27 AM

Post #7 of 10 (2461 views)
Re: [minorsecond] Creating a 100x100 grid in perl [In reply to] Can't Post

Someone else (at least I think it is someone else, perhaps it is you afterall) posted a question on exactly (100x100 grid, random walker, probability of contamination) in the last 3 to 4 days on this forum.

Maybe you want to have a look to it.


Chris Charley
User

Sep 24, 2012, 1:45 PM

Post #8 of 10 (2455 views)
Re: [minorsecond] Creating a 100x100 grid in perl [In reply to] Can't Post

The variable @grid could have more accurately named @path. If I understand the problem correctly, you want a (100 x 100) grid that remains constant from run to run and have random walks through that grid. (The @path var is @grid in the original code).

push @walks, scalar grep $_, @path[0 .. $steps - 1];

The line above takes $steps steps. The grid in effect remains constant, its only the path that changes for each run.

I did a similar problem in school in C++ and I can't find it now. It used a grid of letters and I had to find a (given) list of words in it. We could move in any direction, even diagonally, to find the words.

Have you tried it and does it give reasonable results? I would have to think about this more and then post back if I discover the error or correctness in the program.

I think it is how you look at it. The path is changing from run to run - it is random. The number of contaminated cells does not change from run to run.

Hope that helps and that I've understood the problem.

Just doing the math, if there are 100 contaminated cells out of 10,000 (in a 100 X 100 grid), then 1% of them are contaminated. The probability of taking 100 steps without stepping on a contaminated cell would be .99 to the hundreth power, (.99 ^ 100). That gives ~0.36 and I get results close to that when running my program (when using those parameters).

Update: My model solution doesn't account for the possibilty of revisiting a cell. I think the answer lies in creating a grid to randomly walk upon - as your problem originally suggested.


(This post was edited by Chris Charley on Sep 28, 2012, 1:46 PM)


Chris Charley
User

Sep 26, 2012, 9:50 AM

Post #9 of 10 (2431 views)
Re: [BillKSmith] Creating a 100x100 grid in perl [In reply to] Can't Post

BillKSmith pointed out the problem with the way you are using the hashes. A possible solution would be to use a compound key made from the xpos and ypos.

Code
my $key = "$xpos_cont$;$ypos_cont";


The 'separator' between the xpos and ypos is '$;'. It is safe to use that perl builtin variable for your problem because it is rarely if ever used by perl.

Then you could create a hash element like this.

Code
my $key = "$xpos_cont$;$ypos_cont"; 
$hash_cont_pos{$key}++;


Using srand in a program is almost always wrong as it influences all rand calls. I understand that you want to fix the grid the same from run to run. I think a solution would be to create the grid in one program, store it and then in the random_walk program, recall the hash from where it is stored and do the random walks with the grid that won't change from run to run. Only the steps taken would then be random. A Perl module that would store the hash is Storable. It is included in newer perl distributions (since perl version 5.7.3), so you would not need to install it if you are using a newer perl.

The grid creator could be like the following program. (redo starts at the first statement in the for block without incrementing the next '$k'). It 'redoes' the loop if the compound key has already been seen. If you have 100 contanimated cells, then this would generate all 100. Without the redo, you could have a duplicate compound key, (same xpos and ypos) and would not the have 100 infected cells.


Code
#!/usr/bin/perl 
use strict;
use warnings;
use Storable;

my $number_contaminant = 100;
my $range_contx = 100;
my $range_conty = 100;
my %hash_cont_pos;


for my $k (0 .. $number_contaminant-1)
{

#random positions of the contaminants, put the random number as integrer
my $xpos_cont = int(rand($range_contx));
my $ypos_cont = int(rand($range_conty));
my $key = "$xpos_cont$;$ypos_cont";
redo if $hash_cont_pos{$key}; # if duplicate
$hash_cont_pos{$key}++;

#Print contaminant file.
#print CONT_OUT "$k Cont_xpos\t".$xpos_cont. "\t Cont_ypos\t".$ypos_cont."\n";
print "$k Cont_xpos\t".$xpos_cont. "\t Cont_ypos\t".$ypos_cont."\n";
}

store \%hash_cont_pos, 'grid.dat';


The in the walker program, the stored constant grid of infected cells could be recalled from disk like below.


Code
my %cont_pos = %{ retrieve('grid.dat') };


In the walker program, the code your TA gave you could be like this.

Code
	#Inner loop to perform each step of a random walk  
for my $i (0 .. $NO_OF_STEPS-1)
{
my $random_num = rand;
my $steps = (1 + int( rand 6 ));
if($random_num < 0.25) {
$xpos = ($xpos - $steps) % $range_contx;
}
elsif ($random_num < 0.5) {
$xpos = ($xpos + $steps) % $range_contx;
}
elsif ($random_num < 0.75) {
$ypos = ($ypos - $steps) % $range_conty;
}
else {
$ypos = ($ypos + $steps) % $range_conty;
}
my $key = "$xpos$;$ypos";
$walker_pos{$key}++;

#print the position of the walker each time

}


The modulo operator here, (($xpos - $steps) % $range_contx), is to 'roll over' the position when they would otherwise stray out of the grid (when adding or subtracting from the current xpos ypos). (Can the steps be 1 to 6? That's how this is setup.)

There are a lot of issues here, but I think you can make your approach doable with the suggestions I have given.

Hope this is helpful.


BillKSmith
Veteran

Sep 26, 2012, 10:19 AM

Post #10 of 10 (2426 views)
Re: [Chris Charley] Creating a 100x100 grid in perl [In reply to] Can't Post

The code in the original post already writes the contamination data to a file. Why not read this file back in to reuse the contamination map.

Rather than the hash, I would recommend implementing the map as a 100x100 array of logic values. If memory were an issue, we could use an array of bit vectors, but an array of ordinary scalars is much easier to implement. Should we really care that the matrix is quite sparse?

The second hash is not needed at all because there is no need to store all the steps of a walk. If a future need arises, the data is in the other output file.
Good Luck,
Bill

 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives