Critical Mass

Been doing a healthy amount of Rails reading lately and get the feeling that I'll soon be able to put some baby steps on the ground and build things. The general concepts are starting to click, which is really exciting-- it's already quite rewarding in that I'm feeling a sense of newfound literacy, but beyond that, I'm also going to get to build things... whatever I want. Can't ask for more than that.

Progress report!

I'm about halfway through step five of Hartl's Rails tutorial, read up (via the The Odin Project and Ruby on Rails guides) on the basics of routing, controllers, views and the asset pipeline, am continuing to read through Sandy Metz' POODR, and am gitting along with git (apologies) better thanks to yochiyochi.rb.

During the last meetup we discussed Rails' preprocessor engines, primarily CSS/SCSS using the Sprockets gem, and I frantically and desperately expanded my git knowledge in order to keep up with the group's weekly collaborations-- specifically I learned more about rebasing as opposed to merging, was introduced to a really cool interactive git exercise/visualization site, and was introduced to a CSS to SASS/SCSS converter.  All new to me, but it's super helpful to have people pointing me in the right direction.

I also got to overhear a nuanced discussion on the relative merits of different text editors. VIM? Emacs? Nano? Do people use Nano as a general-purpose editor? So far I've only been seeing it when git demands an explanation for my merges and have been totally lost as to how to operate it. Well, not lost anymore, but the first time was a doozy (ctrl + s? No? ctrl + q? Esc? What? CTRL+ALT+DEL???).

I see a lot of Sublime Text and am using Textmate myself.

Text editors: absolutely interesting. And GNU/Linux naming controversy? I do enjoy my Wikipedia rabbit holes. Which means it's about time to go for a run before this gets out of hand.

See you soon and with new code!

of Blogs and Books

On the agenda for the week:

The Rspec Book

Practical Object-Oriented Design in Ruby

Finish the Odin Project's Rspec section

Work through Hartl's Rails tutorial's chapters 3-5 (however long that winds up taking) to catch up yochiyochi.rb (Tokyo-based Rails study group).

I tried to get through some of the latter today and wound up both 

A: not getting very far, and 

B: getting a lot done in process.

I'd been using c9.io as a (free!) remote development environment for working through the Rails tutorial, as Hartl himself advocates, but since I've since switched to a Mac and will need to have everything up and running on this machine for the study group meetings, I figured I'd go ahead and get it taken care of today.

This necessitated setting up different gemsets with RVM, using homebrew to update Git and then updating my bash profile such that it doesn't default to Apple's bundled (older) git version, making a new ssh key to use with bitbucket and heroku, etc. Not difficult per se, but took a while and was a lot of new stuff. Solid Google game has got to be worth a good 20 IQ points in this day and age.

At the Rails meetup I attended last week, I met a gentleman who'd relocated from Tokyo to NYC for the duration of his Dev Bootcamp program before returning to look for work. We both talked about what we'd been studying, and he had a number of  book recommendations.

The one he pushed the hardest for is the one I'm reading now-- Practical Object-Oriented Design in Ruby. His parting words about it stuck out: "You've gotta read that so you can stop writing, y'know, stupid code."

Emotional response: You haven't even seen my code but it works so how stupid could it be?

Rational response: Important book? Important book. I should read important book.

Actual verbal response: "OK."

Sure is handy to have awareness of each of those. Thanks, adulthood!

And sure enough, the book has absolutely been a red pill in terms of how I'm seeing code and its design, which hadn't been on my radar to this point. Things I'd read but evidently not fully taken to heart, like why one should reference the attr_reader wrapper method of an instance variable instead of the variable itself, make a lot more sense conceptually now (doing so keeps all references to that of the method's behavior, which is defined once, as opposed to data, which isn't as DRY).

Sure, I've made games and such that work, but as the author (Sandi Metz) so eloquently puts it, "Anyone can arrange code to make it work right now. Today's application can be beat into submission by sheer force of will. It's a standing target at a known range. It is at your mercy. Your application needs to... be easy to change forever. This quality of easy changeability reveals the craft of programming."

Great writing, right? Makes me want to get craftier.

Knight's Travails-- moving a chess knight from one space to another in as few moves as possible

Greetings from my first developer meetup! An American gentleman working for a certain extremely large Japanese telecom's web communications division has borrowed their cafeteria/lounge space for the day and is hosting local developers for project work and study.

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:

class Square
  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!

Mini-HTTP browser/server, how the server determines the end of a request

I'm writing a mini-HTTP browser and server in Ruby for the Odin Project:

http://www.theodinproject.com/ruby-programming/ruby-on-the-web

The browser's requests are structured as prescribed on this page:

http://www.jmarshall.com/easy/http/#structure

I've been getting tripped up on how to have the server read all the data that it needs from its socket (incoming data connection; the connection to which the browser is sending its request). The header part of the request ends with a CRLF (a blank line; "\r\n\r\n" in Ruby), and I originally had the server read the socket within a loop, using #gets, until it either hit one such CRLF in the case of a GET request, or two in the case of a POST request.

Problem: according to http://www.w3.org/Protocols/rfc2616/rfc2616-sec4.html , POST requests aren't supposed to have a CRLF following the last line of the transmission, after the request body.

The page says: "Certain buggy HTTP/1.0 client implementations generate extra CRLF's after a POST request. To restate what is explicitly forbidden by the BNF, an HTTP/1.1 client MUST NOT preface or follow a request with an extra CRLF."

Given that, I tried to update the loop according to what another student did: have it read the socket until the first CRLF in order to get the header portion of the request, which is good enough for a GET request.

That code looks like this:

client = server.accept
header = ""
while line = client.gets
  header += line
  break if header =~ /\r\n\r\n$/
end

Then, in the case of a POST request, start reading again (we're reading lines using gets and haven't closed the connection, so we can pick up where we left off) and read until...

Oh.

So if there isn't a second CRFL, I'm not sure how to determine that the request transmission is over.

I was stumped on this for a while, until finding this Q/A on StackOverflow:
http://stackoverflow.com/questions/4824451/detect-end-of-http-request-body

Of course! It's so simple. The browser specifies and sends the request body file size in bytes. So, the server just needs to parse that size from the header, and wait until the request body is exactly that size.

So, I tried making a loop, using #gets as above, to concatenate lines to the variable "body" until its size equalled the size specified in the header lines. Something like:

# parse out the size, in bytes, of the request body from the header
body_size = header_lines[-2].split(" ")[1].to_i
body = ""
while line = client.gets
  body += line
  break if body_size == body.size
end 

Heartbreak and anguish!

Here's why: I think that #gets will read until it sees a newline. So since there's no \r\n\r\n, or even a \n at the end of the request body, it won't stop reading and won't even let the server do anything past "line = client.gets". It gets totally stuck.

Solution!

Don't use #gets! Use #read, with which you can specify the exact amount of bytes you want to read. Which suits our needs perfectly, since we happen to have that very number.

Here's how the code will look:

# parse out the size, in bytes, of the request body from the header
body_size = header_lines[-2].split(" ")[1].to_i
# and read exactly that many bytes out of the socket
body = client.read(body_size)

And with that, my mini-browser and mini-server are able to issue and handle GET and POST requests.

Here's my code: https://github.com/johnwquarles/simple-server-and-client

Happy New Year from zozo-ji temple in Tokyo!

Here's to new beginnings.