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 (1646 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 (1644 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 (1640 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 (1627 views)
Post deleted by Chris Charley [In reply to]
 


BillKSmith
Veteran

Sep 23, 2012, 9:08 PM

Post #5 of 10 (1617 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 (1610 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
Enthusiast

Sep 24, 2012, 11:27 AM

Post #7 of 10 (1589 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 (1583 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 (1559 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 (1554 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