-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathselfavoid.py
More file actions
68 lines (51 loc) · 1.62 KB
/
selfavoid.py
File metadata and controls
68 lines (51 loc) · 1.62 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#-----------------------------------------------------------------------
# selfavoid.py
#-----------------------------------------------------------------------
import stdio
import stdarray
import sys
import random
# Accept integers n and trialCount as command-line arguments. Do
# trialCount random self-avoiding walks in an n-by-n lattice.
# Write to standard output the percentage of dead ends encountered.
n = int(sys.argv[1])
trials = int(sys.argv[2])
deadEnds = 0
for t in range(trials):
# Create an n-by-n array, with all elements set to False.
a = stdarray.create2D(n, n, False)
x = n//2
y = n//2
while (x > 0) and (x < n-1) and (y > 0) and (y < n-1):
# Check for dead end and make a random move.
a[x][y] = True
if a[x-1][y] and a[x+1][y] and a[x][y-1] and a[x][y+1]:
deadEnds += 1
break
r = random.randrange(1, 5)
if (r == 1) and (not a[x+1][y]):
x += 1
elif (r == 2) and (not a[x-1][y]):
x -= 1
elif (r == 3) and (not a[x][y+1]):
y += 1
elif (r == 4) and (not a[x][y-1]):
y -= 1
stdio.writeln(str(100*deadEnds//trials) + '% dead ends')
#-----------------------------------------------------------------------
# python selfavoid.py 5 100
# 0% dead ends
# python selfavoid.py 20 100
# 27% dead ends
# python selfavoid.py 40 100
# 80% dead ends
# python selfavoid.py 80 100
# 96% dead ends
# python selfavoid.py 5 1000
# 0% dead ends
# python selfavoid.py 20 1000
# 33% dead ends
# python selfavoid.py 40 1000
# 77% dead ends
# python selfavoid.py 80 1000
# 98% dead ends