It's been a fantastic experience just to see what accomplished devs are working on-- it's all unbelievably cool. Just unreal. The host has a number of different projects going on, among them applications for a device called Leap Motion. I got to play with it a bit-- it's a (compound, I assume) camera that detects the locations and positioning of your hands and translates them into a 3D on-screen environment (created by whatever application it is that's using it). It's pretty similar to an Xbox Kinect in that it detects the positioning of individual bones (your fingers) in order to render the exact position of your body/body parts onscreen.
I played a few games with it, and apparently you can use it to manipulate your OS's GUI. Super interesting. If that sort of GUI interaction were to take off, I figure the interface would eventually start to resemble Minority Report. Maybe it already does.
Another attendee is working on v2v applications, which I'd never even heard of before-- it stands for "vehicle to vehicle communication". How cool is that? He works with hardware in automobiles that communicate with one another to decrease congestion, pollution and auto accidents. What a reason to get up in the morning!
MEANWHILE, my humble beginner self faced the task of making a Ruby program that can take a chess knight and give the shortest possible route from one space to another.
http://www.theodinproject.com/ruby-programming/data-structures-and-algorithms?ref=lc-pb
This one was really interesting for me in terms of breaking the problem down into parts and solving each one. I made my application without having to get any ideas from outside sources (beyond what the problem suggested and programming that I'd already done), which was really rewarding when I got it working.
My thought process went something like this:
We're going to need square objects that represent spaces on the chess board and have instance variables @x and @y to represent their coordinates. Each square will have children that represent possible knight moves from that square. For example, a square in the middle of the board would have 8 children, whereas a corner square would only have 2 since 6 of the moves fitting the knight's movement pattern would place it off the board.
Great. But if we generate a square object, and its children are also square objects, the children will have children will have children will have children... we'll be in an infinite loop of wanton square child creation. This makes sense since you could very well sit there at a chess board and move a knight around endlessly if you really wanted to-- the squares themselves are finite, but the series of moves you could make is infinite.
So generating all the children at once is no good.
Let's make an instance variable @children, and have it initialize to an empty array.
So far our code would look something like:
class Square
attr_reader :x, :y, :children
def initialize(x, y)
@x = x
@y = y
@children = []
end
end
Great. Now, we'll make a make_children method that will generate that square object's children, so that we only make children one generation at a time and don't wind up in an infinite loop.def make_children
candidates = []
candidates.push([@x + 2, @y - 1]).push([@x + 2, @y + 1]).
push([@x + 1, @y -2]).push([@x + 1, @y + 2]).
push([@x - 1, @y - 2]).push([@x - 1, @y + 2]).
push([@x - 2, @y - 1]).push([@x - 2, @y + 1])
children = candidates.select{|cand| cand[0] >= 0 &&
cand[0] <= 7 && cand[1] >= 0 && cand[1] <= 7}
# make objects out of the possible move coordinates.
children = children.map{|child_coords| Square.new
(child_coords[0], child_coords[1])}
@children = children
end
This method generates 8 candidate coordinate arrays, weeds out those that aren't actually on the board (defined as 8 spaces on the x- and y-axes numbered from 0 to 7), and then generates square objects from those coordinates. It saves an array consisting of these new square objects as the first square (self)'s @children instance variable.
Super. Now let's find a path from the first square to our target square.
If we were to use a depth-first search, we'd wind up with situations where we'd be going in circles without covering all the space on the board. Example: consider the square [7, 1]. Given that I chose (arbitrarily) to add possible moves in the following order:
1. [+2, -1] 5. [-1, -2]
2. [+2, +1] 6. [-1, +2]
3. [+1, -2] 7. [-2, -1]
4. [+1, +2] 8. [-2, +1]
The first legal move from [7, 1] would place us at [6, 3].
From [6, 3], our first legal move would place us at [7, 1].
In a depth-first search, we'd continuously check the first available child of each node (square), and since there are no leaves (because there are always moves possible from any given square), we'd wind up in an endless cycle going from [7, 1] to [6, 3]. We wouldn't check any other squares, thus the search would never end unless you happened to be looking for the route to [6, 3]. We'd never exit the loop, angels would cry, and civilization as we know it may well cease to be**
So in order to preserve reason, order and democracy, I opted for a breadth-first search.
I had already made one for the last project I worked on, so implementing it was easy. I set it up to look for a square object (search_obj) and start from another square object (root_obj):
def get_search_obj(search_obj, root_obj)
queue = []
queue << root_obj
loop do
current = queue.shift
return current if current.x == search_obj.x
&& current.y == search_obj.y
current.make_children.each {|child| queue << child}
end
end
Great! Now we can find the destination square.
Which... we already knew was on the board.
Right. Our task is to generate the route taken from the initial square to the destination square, not to *find* the destination, which is obviously on the chess board.
Hmm...
We can't simply list each child that we test along the way, since this would do nothing to define the route that's taken; it would just be a list of all the squares we tested until we happened upon the destination. As the code is set up now, there is no "route" per se; we simply iterate through entire sets of children, one after another for each possible move, until we find a child square that matches the destination square.
How can we represent the route? What is the route?
I thought about this for a while until it hit me: of all the children that we test, we only wind up "taking" one per generation in navigating to the destination square, but that route (the sequence of children that we "take") isn't decided until we get there. The route winds up something like: "We make this move, then this move, then this one and we're there".
So we need to establish parent-child relationships between the squares that we test, so that once we get to the destination, we can see what move got us there, what move got us to the square before that, etc.; we can retrace our steps by examining each square's parent. This gives us our route.
In other words, once we find our destination square object, we'll be able to traverse its "family tree". The destination square is our last square in the route, its parent is the second-to-last square, its grandparent is the third-to-last square, etc., until we're all the way back at our first square in the route: the square from which we began our search.
To do this, we'll need to include an instance variable for each square object representing its parent square object. It will default to nil since the very first square doesn't have a parent.
Adding the parent instance variable made my square class look like this:
attr_reader :x, :y, :parent_obj, :children
def initialize(x, y, parent_obj = nil)
@x = x
@y = y
@parent_obj = parent_obj
@children = []
end
def make_children
candidates = []
candidates.push([@x + 2, @y - 1]).push([@x + 2, @y + 1]).
push([@x + 1, @y - 2]).push([@x + 1, @y + 2]).
push([@x - 1, @y - 2]).push([@x - 1, @y + 2]).
push([@x - 2, @y - 1]).push([@x - 2, @y + 1])
children = candidates.select{|cand| cand[0] >= 0 &&
cand[0] <= 7 && cand[1] > 0 && cand[1] <= 7}
# make objects out of the possible move coordinates.
children = children.map{|child_coords| Square.new
(child_coords[0], child_coords[1], self)}
@children = children
end
end
Note that in the revised #make_children method, we generate children with the arguments (child_coords[0], child_coords[1], self). This sets up each child square object's coordinates, of course, and also establishes its parent square, which is the square upon which #make_children was called (the square that is making children), ie, self.
Lovely. So now our get_search_obj method will find, or rather retrieve, a square object that has a parent that has a parent that has... until we're back at the square we started from.
I then made a method that takes in an array of starting coordinates (root_arr) and destination coordinates (search_arr), calls get_search_obj, and traverses the search result object's parental line as described.
def get_route(root_arr, search_arr)
search_obj = Square.new(search_arr[0], search_arr[1])
root_obj = Square.new(root_arr[0], root_arr[1])
result = get_search_obj(search_obj, root_obj)
route = []
route.unshift([search_obj.x, search_obj.y])
current = result.parent_obj
until current == nil
route.unshift [current.x, current.y]
current = current.parent_obj
end
puts "You made it in #{route.length - 1} moves! Here's your route:"
route.each {|square| puts square.inspect}
return nil
end
We make an empty route array ( route = [] ) in which to put coordinates representing our route from the starting square to the end square.
As mentioned above, we're starting with the destination object and working backwards, so we'll be using #unshift to place elements at the front of our route array so that the first thing we put in will be the last element in the array, and vice versa*** So, we immediately add the destination square's coordinates (route << [search_obj.x, search_obj.y]), since the destination square has no children (we stop our search/children generation once we get to it) and thus isn't added to the route by the parent-unshifting loop that we go into next.
We enter that loop, which iterates through all squares along the route, starting with the destination square. It unshifts each square's parent into the route array until that parent winds up being nil, which is what happens when we get to the square we began the search from, since it has no parent.
And that does it! We have our route, and it's in order. Felt good to figure it out.
Here's my code:
https://github.com/johnwquarles/Ruby-binary-trees-knights-travails/blob/master/knight.rb
** I stand by these assertions. Perhaps more relevant than the potential of an infinite loop, however, is the fact that a depth-first search wouldn't be looking for the shortest route from square A to square B; it'd be looking for any route.
A breadth-first search, on the other hand, will necessarily find the (a?) shortest route due to the nature of how it works. You start by testing all of the first square's children, ie, all possible routes that only contain one step. Assuming that there wasn't a one-step route, you then add all of the children's children to the queue and test them-- ie, all possible routes that contain two steps. Assuming we're not done, we test all possible routes for three steps, etc., until we find a match and the search ends. So if there happens to be a seven-step route and a three-step route, we would never get to the longer, undesirable route since we'd find the quicker one first and the search would terminate.
*** In retrospect, it would have made for more readable code to just build the array in reverse order and then use #reverse!
Nice post, i've had problem with that project and the last one
ReplyDeletenow is that for me more obvious ;)