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
68
69
70
71
72
#
# Uses a depth-first search to find a path from a randomly-generated point to
# the "treasure" at (0, 1) on a 4x4 coordinate plane:
#
# 0 1 2 3
# 0 - - - -
# 1 * - - -
# 2 - - - -
# 3 - - - -
#
class Coordinates
attr_accessor :x
attr_accessor :y
def print
puts "(#{@x}, #{@y})"
end
def is_on_treasure?
@x == 0 and @y == 1
end
end
coordinates = Coordinates.new
srand # reset the random seed
coordinates.x = rand 4
srand # reset the random seed
coordinates.y = rand 4
visited = []
to_visit = []
while not coordinates.is_on_treasure?
visited.append coordinates.dup
if coordinates.x < 3
right = coordinates.dup
right.x += 1
to_visit.append right
end
if coordinates.y < 3
down = coordinates.dup
down.y += 1
to_visit.append down
end
if coordinates.x > 0
left = coordinates.dup
left.x -= 1
to_visit.append left
end
if coordinates.y > 0
up = coordinates.dup
up.y -= 1
to_visit.append up
end
coordinates = to_visit.last
end
visited.append coordinates
puts "path: "
visited.each do |c|
print "- "
c.print
end