RubyGems 1.5.0 Released: Now Supports Ruby 1.9.2

rubygems.pngRyan Davis has announced the release of RubyGems 1.5.0. It comes just a month after the release of 1.4 which, notoriously, didn’t work with Ruby 1.9.2. These problems have now all been ironed out and Ruby 1.8 and 1.9 users alike can safely upgrade (fingers crossed).

RubyGems is the popular (and official – as of Ruby 1.9) Ruby package manager with which most significant Ruby libraries and tools are distributed. The 1.5 release sees it pick up a few bug fixes and some enhancements, including:

  • Ruby 1.9 support
  • Post-build hooks that can cancel the gem install
  • Gem.find_files is now 40% faster (on Ruby 1.9)
  • Better errors for corrupt Gem files, including paths
  • A new UPGRADING documentation file to help with Ruby 1.9-related issues
  • gem update no longer erroneously tries to update RubyGems itself by default

To upgrade to RubyGems 1.5.0, run:

gem update --system

Alternatively, you can learn more in the new UPGRADING documentation, or if you don’t already have RubyGems for some reason, you can download it from RubyGems.org.

UPDATE: RubyGems 1.5.0 and Bundler are not the best of friends! If you’re depending on Bundler tonight, don’t install RubyGems 1.5.0 just yet. However, a 1.5 compatible version of Bundler is due within the next 24 hours. A new version of Bundler has been released, supporting RubyGems 1.5.0. Upgrade now 🙂

[ad] Spreadable is a powerful ‘tell a friend’ referral tool you can easily plug into your site. It brings your app powerful viral social tools you and your users can use to spread the word about your work.

How I became a Haml-tonian

I mentioned on Twitter the other day that I was starting to like using Haml and it was surprising me because I used to dislike it so much. Colin Harris asked me to elaborate, but Twitter was too short, so here goes.

I assume that most people reading this have some idea of what Haml is, if you don’t, it’s an ERb replacement for view depleting which uses Python-style indentation for blocks, and a couple of other tricks for simplifying the amount of markup you need to write in your view — here’s a sample from the Haml tutorial, which gives you the flavor.

#profile
  .left.column
    #date= print_date
    #address= current_user.address
  .right.column
    #email= current_user.email
    #bio= current_user.bio

I don’t really intend to turn this into its own-mini tutorial, but suffice to say that “=” indicates Ruby execution, and the “.” and “#” allow you to specify CSS selectors, with a div tag being implied, and indentation indicating the extent of the outer tag.

So, how did I go from really hating Haml to mostly liking it? Well, here’s how I came to dislike it.

My first exposure to Haml in use came on a legacy project that I was asked to take over. The project seemed to have been worked on by two people who rarely spoke, as evidenced by, among other things, the fact that the view code was half ERb, half Haml. And the Haml seemed to be tied to some of the ugliest code in the system.

As a longtime Python programmer, I have no problem with using whitespace to mark blocks. In fact, I kind of like it. However, you have to acknowledge that the side-effect of whitespace blocks is to keep your blocks short, and try not to let them get too deep. That’s part of the point — the structure of the code is supposed to guide you to keeping the code concise and well factored. If you don’t pay attention, then the whitespace code — Python or Haml — becomes very hard to follow and maintain.

I’m sure you see where this is going. This first Haml project had long files, with deep nesting. It also, I realize now, wasn’t particularly good at using Haml’s strengths in specifying DOM elements. Every time I needed to touch that code it was a bad experience, and I got very averse to seeing Haml.

I also had a couple of other issues. Among my coding quirks, I tend to be aggressive about keeping line lengths under 80-90, and Haml 2.x didn’t allow you to insert line breaks in executing Ruby code, which led to unavoidably long lines in some cases. (I realize that the point was to keep you from having long Ruby calls, but sometimes, especially in that code base, it was unavoidable.) To a much lesser extent, I was also not attracted to the “If you don’t like Haml you have no poetry in your soul” tone of the Haml website. I’ve come to terms with that, too.

So what happened?

A couple of things. Haml 3.0 made it possible to break lines in Ruby code, and that was enough to get me to look at Haml again. The addition of SCSS over SASS for writing CSS helped a lot — I love SCSS and never really got into the SASS syntax. I started working on projects that used Haml and were smarter about using CSS, making the Haml’s easy creation of complex CSS selectors more attractive. I saw better examples of Haml code that showed it in a better light.

And one day, working on a totally different project that also happened to be half Haml, half ERb, I noticed that the ERb started to fell clunky and heavyweight. The Haml started to feel disturbingly natural.

I started to prefer Haml, using it as the default on new projects.

What do I like about it?

  • It’s concise, but after you get used to it, completely readable (again, when written well). It did take me a little while to get used to it.
  • Haml makes it much more difficult to write invalid markup, effectively eliminating a source of error
  • Haml encourages treating markup like code and writing it in small pieces
  • Haml implies the use of SCSS, which is pretty unambiguously awesome.
  • As Brian Hogan pointed out on Twitter, Haml makes it easier to restructure the hierarchy of your view output because it’s much easier to change the relative placement of tags.

It’s not perfect. Like all HTML tools that assume an HTML structure, unstructured text is challenging. Ruby blocks still look strange without endings. Other than that, I’m happy making Haml my default view layer. And I’m glad I got over it enough to give it another look

Filed under: Uncategorized

#251 MetaWhere & MetaSearch

MetaWhere provides a way to do complex find conditions without SQL in Active Record. MetaSearch makes it easy to create search forms with many find options.

#251 MetaWhere & MetaSearch

MetaWhere provides a way to do complex find conditions without SQL in Active Record. MetaSearch makes it easy to create search forms with many find options.

Data Modeling in Performant Systems

I have been working on Words With Friends, a high traffic app, for over six months. Talk about trial by fire. I never knew what scale was. Suffice to say that I have learned a lot.

Keeping an application performant is all about finding bottlenecks and fixing them. The problem is each bottleneck you fix leads to more usage and a new bottleneck. It is a constant game of cat and mouse. Sometimes you are the cat and sometimes, well, you are not.

Most of the time, the removal of those bottlenecks is about moving hot data to places that can serve it faster. Disks are slow, memory is fast, enter more memcached.

Over time, you work and work to move hot data into memory and simplify your data access to fit into memory. Key here, value there. Eventually, you get to a place where you have simplified how you access your data into simple key/value lookups.

Games get marshaled into a key named "Game:#{id}". Joins are simplified to selecting ids and caching the array of ids into a key such as "User:#{id}:active_game_ids" or "User:#{id}:over_game_ids". In turn, those arrays are turned into objects by un-marshaling the contents of "Game:#{id}", etc.

Your data model morphs from highly relational to key/value because key/value is fast and memcached can withstand a bruising.

Do it once, and you know how to do it in the future. The problem is by the time you get to this data model, it is kind of bolted on/in to your app.

What if you could design it this way from the beginning? What if you had no option but to think through your data model in keys and values? Need your data in two different ways? Put it in two different places, etc, etc.

I have good news. Now you can.

A Little History

Not long into my tenure with WWF, we were hitting a lot of walls and there was a lot of talk about NoSQL. Mongo? Membase? Cassandra? Riak?

Which one will work best for the problem at hand? What if we could try them all really easily by just changing which place the data went to? What if we could try out more than one at once?

I sat down one weekend and started thinking about the app and realized what I just talked about above. Along the way, our data access changed from relational to key lookups. This made me think about a hash.

Hashes are so versatile, and yet, so constrained. Hashes are for reading, writing and deleting keys, just like key/value stores. I did a bit of GitHub searching and stumbled across moneta, by Yehuda Katz.

Moneta immediately struck me as brilliant. I was shocked there was no activity around it. If you only allow yourself to read, write and delete with the same API, you can make nearly any data store talk the correct language.

I fiddled with it and forked it, but in the end, it was not quite what I was looking for. I liken it to my first house. I like the house, but having lived in it for six years, I know exactly what I want out of my next house.

The folks at Newtoy (now Zynga with Friends) had mentioned that they wanted to build their own object mapper and name it ToyStore—such a great name.

In a fit of inspiration over the 4th of July weekend, I cranked out attributes and initialization, relying heavily on ActiveModel. It was really fun. I emailed the crew when the next work day came around and they were stoked.

It began to occupy some of my work-related time and Geoffrey Dagley started helping me with it. Over the next few weeks, Geof and I hammered out validations, serialization, callbacks, dirty tracking, and much more.

Everything was built on the premise that the only acceptable methods that could be used to read, write and delete data were read, write and delete.

Adapter: The Common Interface

Over time Brandon Keepers got involved and ToyStore started looking pretty legit. We switched from using Moneta as the base to something I whipped together in a few hours, Adapter.

Defining an adapter is as simple as telling it how the client reads, writes and deletes data. You also have to define a clear method for convenience and to stick close the Ruby hash API.

The client can be anything that you want to have a unified interface. For example, this is how you would create an adapter to store things in a ruby hash.

Adapter.define(:memory) do
  def read(key)
    decode(client[key_for(key)])
  end

  def write(key, value)
    client[key_for(key)] = encode(value)
  end

  def delete(key)
    client.delete(key_for(key))
  end

  def clear
    client.clear
  end
end

key_for ensures that most things can work as a key. encode and decode allow one to hook some kind of serialization in, whatever you fancy, be it Marshal, JSON, or whatever you can imagine.

By defining those methods, we can now get an instance of this adapter and connect it to a client. In the example above, the client is just a plain ruby hash, but in other adapters, it could be an instance of Redis (adapter), Memcached (adapter), or maybe a Riak bucket (adapter).

adapter = Adapter[:memory].new({}) # sets {} to client
adapter.write('foo', 'bar')
adapter.read('foo') # 'bar'
adapter.delete('foo')
adapter.fetch('foo', 'bar') # returns bar and sets foo to bar

# [] and []= are aliased to read and write
adapter['foo'] = 'bar'
adapter['foo'] # 'bar'

Adapters can also be defined using a block (like above), a module, or both (module included first, then block so you can override module with block).

Adapters can also define atomic locking mechanisms, see the memcached and redis adapters for their locking implementations. The more opaque the object, the more you need to lock. Or, in the case of riak, the adapter can handle read conflicts.

ToyStore: The Mapper Fixings on top of Adaper

Once you have secured how your data layer speaks the adapter interface you can use the real power, ToyStore.

Lets say you want to store your users in redis. Create your class, include the Toy::Store, and set it to store in redis.

require 'toystore'
require 'adapter/redis'

class User
  include Toy::Store
  store :redis, Redis.new

  attribute :email, String
end

From there, you can go to town, defining attributes, validations, callbacks and more.

class User
  include Toy::Store
  store :redis, Redis.new

  attribute :email, String
  validates_presence_of :email
  before_save :lower_case_email

private
  def lower_case_email
    self.email = email.downcase if email
  end
end

user = User.new
pp user.valid?

user.email = 'John'
pp user.save

pp user
pp User.get(user.id)

user.destroy
pp User.get(user.id)

Change your mind? Decide that you do not want to use Redis? Fancy Riak? Simply change the store to use the riak adapter and you are rolling.

require 'toystore'
require 'adapter/riak'

class User
  include Toy::Store
  store :riak, Riak::Client.new['users']

  attribute :email, String
end

Boom. You just completely changed your data store in a couple lines of code. Practical? Yes and no. Cool? Heck yeah.

What all does Toy::Store come with out of the box? So glad you asked.

  • Attributes – attribute :name, String (or some other type) Can be virtual which works just like attr_accessor but all the power of dirty tracking, serialization, etc. Also, can be abbreviated which means :first_name could be the method you use, but in the data store the attribute is :fn. Save those bytes! Allows for default values and defaults can be procs.
  • Typecasting – Same type system as MongoMapper. One day they will share the exact same type system in its own gem, for now duplicated.
  • Callbacks – all the usual suspects.
  • Dirty Tracking – save, create, update, destroy
  • Mass assignment security – attr_accessible and attr_protected
  • Proper cloning
  • Lists – arrays of ids. If user has many games, user would have list :games which stores in game_ids key on user and works just like an association.
  • Embedded Lists – array of hashes. More consistent than MongoMapper, which will soon reap the benefits of the work on Toy Store embedded lists.
  • References – think belongs_to by a different (better?) name. Post model could reference :creator, User to add creator_id key and relate creator to post.
  • Identity Map – On by default. Should be thread-safe.
  • Read/write through caching – If you specify a cache adapter (say memcached), ToyStore will write to memcached first and read from memcached first, populating the cache if it was not present.
  • Indexing – Need to do lookups by email? index :email and whenever a user is saved the user data is written to one key and the email is written as another key with a value of the user id.
  • Logging
  • Serialization (XML and JSON)
  • Validations
  • Primary key factories

It pretty much has you covered. Adapters for redis, memcached, riak, and cassandra already exist. Expect a Mongo one soon. Have to make a few tweaks to adapter. Yep, even Mongo.

What are other adapters that could be created? Membase? Just start with the memcached adapter and override key_for. Git? File system? REST? MySQL?! I love it!

The Future

The future is not picking a database and forcing all your data into it. The future (heck, now even) is the right database for the job and your application may need several of them.

All this said, in no way do I think ToyStore is going to take the world by storm. It is a different way to build applications. This way comes with great power, but great confusion as well.

Currently, each model is serialized into one key in the store, based on how the adapter does encode/decode. Eventually, I would like to add the ability to store different attributes in different keys. For example, maybe you want active_game_ids to be stored in a key by itself so you don’t have to constantly save the entire user object.

I can also see a use for being able to store an attribute not just a different key, but a different store entirely. Store your user objects in Riak, but active_game_ids in a Redis set. This is where it would get really powerful.

At any rate, I am very excited about this project and I think it has a lot of potential. I would also like to add that MongoMapper is here to stay.

In fact, I learned from my mistakes on MongoMapper when building ToyStore and will be back-porting those learned experiences very soon. Expect a flurry of activity over the next little while.

Closing Thanks

Huge thanks to Newtoy (now Zynga with Friends) for allowing Geof and I to open source this. Several pieces of ToyStore were built on their dime and I really appreciate their contribution to the Ruby and Rails community!

As is typical with new projects, there are probably rough spots and good luck finding documentation. I have included a bevy of examples and the tests do a superb job at explaining the functionality of each method/feature.

Let me know what your thoughts are and be sure to kick the tires!

Roundup of Links

Maze Generation: Growing Tree algorithm

Remember way back in the first article of this series, where I said that Recursive Backtracking was my favorite for generating mazes? Well, I changed my mind. My new favorite is the Growing Tree algorithm.

This algorithm is pretty cool. Configured one way, it mimics the behavior of the Recursive Backtracking algorithm. Configured another, it works almost exactly like Prim’s algorithm. Another trivial change, and you can generate mazes with attributes of both.

It’s really pretty slick. Here’s how it works:

  1. Let C be a list of cells, initially empty. Add one cell to C, at random.
  2. Choose a cell from C, and carve a passage to any unvisited neighbor of that cell, adding that neighbor to C as well. If there are no unvisited neighbors, remove the cell from C.
  3. Repeat #2 until C is empty.

Pretty straight-forward, really. But the fun lies in how you choose the cells from C, in step #2. If you always choose the newest cell (the one most recently added), you’ll get the recursive backtracker. If you always choose a cell at random, you get Prim’s. It’s remarkably fun to experiment with other ways to choose cells from C.

Let’s look at a simple example.

An example

I’ll demonstrate the “choose newest” cell selection method, which will hopefully be enlightening enough that you can imagine on your own how the “choose random” method might proceed.

The algorithm begins by adding an arbitrary cell to the list. We mark the cell as “in”; I’m also going to assign the cell a number, visually, to help keep track of the relative age of each cell. Also, cells in red are in the list of “live” cells; they’ll go white once they’ve been removed from the list.

So, onward!

1

Next step: we choose the newest cell from the list, randomly select one of its unvisited neighbors, carve a path to it, and add the neighbor to the list:

1
2

Let’s do it again, once more choosing the newest cell from the list:

1
3 2

See the pattern? By always choosing the cell most recently added to the list, each subsequent step simply extends the passage one more step, effectively doing a random walk. But how does the algorithm behave when the passage cannot be extended any further?

Let’s fast forward a bit and see what the behavior is. Here we are now, six iterations further along, and we’ve hit a dead-end at cell #9.

1
3 2 7 8
4 5 6 9

At this point, the algorithm would select the newest cell (#9), and then try to find an unvisited neighbor cell. Alas, there isn’t one! So cell #9 is voted off the island removed from the list:

1
3 2 7 8
4 5 6 9

Then the algorithm goes around again, grabbing the newest cell from the list. This time, that’s #8, and sure enough, there is an unvisited adjacent cell that we can move to:

1 10
3 2 7 8
4 5 6 9

Did you see that?! It backtracked!

Not really. It wasn’t intentionally backtracking; it just happened that the algorithm’s choice of cell was the same one that the backtracking algorithm would have chosen. And it will continue to choose identically to the backtracker, clear up until every cell has been visited and it has to “backtrack” all the way back to the original cell. At that point, the list of cells will be empty, and the algorithm will terminate.

Pretty cool!

Take a moment and think about how the algorithm would change if, instead of choosing the newest cell each time, we chose one at random. I’ve already told you it would behave like Prim’s algorithm in this case, but can you see why? I hope so, because I’m not going to draw any more diagrams tonight. 🙂

Instead, you can play with the following demo, which has presets for several different cell-selection methods. Choose a few different ones and compare how they behave.

<link href=”http://jamisbuck.org/mazes/css/mazes.css” />

Cell selection method: <select>
<option>Newest (Recursive Backtracker)</option>
<option>Random (Prim’s)</option>
<option>Newest/Random, 75/25 split</option>
<option>Newest/Random, 50/50 split</option>
<option>Newest/Random, 25/75 split</option>
<option>Oldest</option>
<option>Middle</option>
<option>Newest/Oldest, 50/50 split</option>
<option>Oldest/Random, 50/50 split</option>
</select>

Implementation

Implementation-wise, this is one of the simplest algorithms (another reason to love it!). In fact, in my own implementation, the most complex part came from code that I added that lets you specify the cell-selection method when the script is executed!

It starts by selecting a random cell and adding it to the list:

1
2
x, y = rand(width), rand(height)
cells << [x, y]

The program them simply loops until the list is empty:

1
2
3
until cells.empty?
  # ...
end

Within the loop, we first select the cell to operate on. I’m going to mask my own program’s complexity here behind a simple “choose_index” method; it takes a number and returns a number less than that.

1
2
index = choose_index(cells.length)
x, y = cells[index]

Next, we iterate over a randomized list of directions, looking for an unvisited neighbor. If no such neighbor is found, we delete the given cell from the list before continuing.

1
2
3
4
5
6
7
8
[N, S, E, W].shuffle.each do |dir|
  nx, ny = x + DX[dir], y + DY[dir]
  if nx >= 0 && ny >= 0 && nx < width && ny < height && grid[ny][nx] == 0
    # ...
  end
end

cells.delete_at(index) if index

When a valid, unvisited neighbor is located, we carve a passage between the current cell and that neighbor, add the neighbor to the list, set index to nil (to indicate that an unvisited neighbor was found), and then break out of the innermost loop.

1
2
3
4
5
grid[y][x] |= dir
grid[ny][nx] |= OPPOSITE[dir]
cells << [nx, ny]
index = nil
break

And that’s really all there is to it. Some possible implementations of the choose_index method might be:

1
2
3
4
5
6
def choose_index(ceil)
  return ceil-1 if choose_newest?
  return 0 if choose_oldest?
  return rand(ceil) if choose_random?
  # or implement your own!
end

Try it out and see what new cell selection methods you discover!

Conclusion

Personally, I love the flexibility of this algorithm. It’s surprisingly easy—and addicting!—to try crazy new ideas for selecting cells, and the algorithm itself is almost trivially simple to implement. Performance-wise, the algorithm is one of the faster ones (assuming you can make removing a cell from the list reasonably fast), and while memory use is proportional to the size of the maze itself, that’s not unusual for most of these algorithms.

Seriously, what’s not to like?!

Give it a try and link to your implementations in the comments. Share your ideas for new cell selection methods, too—I’d love to see what you come up with!

For reference, the complete source of my implementation, in Ruby, is below. Remember that most of the code in my implementation is for cell selection and displaying the maze; the algorithm itself is only the tiny bit at the end!

<noscript>growing-tree.rb on gist.github.com</noscript>

Enjoy!

Rails Drinkup Pune – Jan 28th

Rails Drinkup Pune – Jan 28th

It’s that time again. Rails Drinkup will be in Pune, India on Jan. 28th and we’re doing a drinkup at the Royal Connaught Boat Club. If you want some free beer, be there at or around 6 pm. We shall have 1 or 2 technical sessions (like “Rhodes in a Nutshell”) followed by networking.

The Drinkup is sponsored by IntelleCap. The earlier Drinkup sponsored by JoshSoftware was a big success. Be there.

Pune Rails Meetup
Royal Connaught Boat Club

Royal Connaught Boat Club
Boat Club Rd,
Sangamvadi,
Pune
Friday, Jan 28, 6:00pm
Free Beer

Update

Pune Rails Meetup
Gautam Rege of JoshSoftware at the Rhodes session

The drinkup was a big success with hackers from other programming languages like Clojure and guests from Holland joining in.

Technorati Tags: , , ,

Quick Rails Test Prescriptions Update

It’s been quiet on the Rails Test Prescription front. Those of you on the beta program should have gotten Beta 11 earlier this week. There are no major changes in this beta, but it does contain the final copyedit, a pass through the errata, and a couple of late-breaking reviewer comments.

At the moment, the book is being typeset, which means that non-typesetter changes to the source files are definitely contraindicated.

My understanding, which is guaranteed to be somewhat incorrect, is that the typesetter will be done early next week. At that point, we’ll have a couple of days to make sure everything looks okay, and then it’ll actually go to the printer. Once it goes to the printer, I think it will go out of beta for the purposes of buying the book. I expect to have more concrete dates once it’s actually at the printer.

I’m not saying I’m excited about this finally being a physical book, but my first commit to the original, self-published repo was November 7th, 2008.

Filed under: Uncategorized

Using JRuby: Bringing Ruby to Java; new Podcast

Using JRuby: Bringing Ruby to Java now available in print and shipping; new podcast with Johanna Rothman and Ian Dees, on multitasking and how to get stuff done at a sustainable pace.

Clever Algorithms: A Free Book of Nature-Inspired Ruby Recipes

cleveralgorithms.pngClever Algorithms is a newly released book by Jason Brownlee PhD that describes 45 algorithms from the Artificial Intelligence (AI) field with Ruby-based examples. It’s well produced and, notably, free in its PDF and online formats. A print copy is available at a small cost.

The book kicks off with a chapter of background regarding AI and its problem domains and moves on to an array of algorithms in the probabilistic, neural networking, stochastic, swarm, and evolutionary spaces.

Ruby purists will note that even though the demonstrations are in Ruby, they’re not very Ruby like. Classes are rarely defined and using methods defined in the main context as functions is the order of the day. Nonetheless, the book remains well written and interesting and the Ruby code – as generic as it is – will nonetheless help Rubyists get the idea behind many of the processes demonstrated.

This book provides a handbook of algorithmic recipes from the fields of Metaheuristics, Biologically Inspired Computation and Computational Intelligence that have been described in a complete, consistent, and centralized manner. These standardized descriptions were carefully designed to be accessible, usable, and understandable.

Most of the algorithms described in this book were originally inspired by biological and natural systems, such as the adaptive capabilities of genetic evolution and the acquired immune system, and the foraging behaviors of birds, bees, ants and bacteria. An encyclopedic algorithm reference, this book is intended for research scientists, engineers, students, and interested amateurs.

Jason Brownlee

Check out Jason’s book at cleveralgorithms.com and the content and code are in this GitHub repository.

[ad] Jaconda is a chat system designed for teams working on projects. It works from the browser, your IM app, or your phone, and lets you chat, share files, and keep up with tickets and project activity you can have sent automatically to your rooms.

The Redis Show

Peter and Jason talk conferences, split testing, redis, and more.

It’s Time To Double Up (Using Amazon’s RDS Read Replication Database Servers With Heroku For Master-Slave Replication)

Heroku is great for rapid application development but if you want to run multiple databases it doesn’t provide any options. Running multiple databases in a master-slave orientation can provide an elegant solution to many scaling issues. This can be accomplished on heroku using my forked version of schoefmax’s gem multi_db. First a quick look at […]

Maze Generation: Hunt-and-Kill algorithm

(Note: if you’re reading this in a feed reader, you’re going to be missing out on the illustrations and demonstrations.)

Alright, so the theme last week was “algorithms for generating uniform spanning trees.” If this week has a theme, it might be something like “algorithms that sometimes act like the recursive backtracker, but only kind of.”

Today’s algorithm is the “hunt-and-kill algorithm”. Sounds violent, doesn’t it? It’s actually quite tame. In a nutshell, it works like this:

  1. Choose a starting location.
  2. Perform a random walk, carving passages to unvisited neighbors, until the current cell has no unvisited neighbors.
  3. Enter “hunt” mode, where you scan the grid looking for an unvisited cell that is adjacent to a visited cell. If found, carve a passage between the two and let the formerly unvisited cell be the new starting location.
  4. Repeat steps 2 and 3 until the hunt mode scans the entire grid and finds no unvisited cells.

Let’s walk through an example.

An example

I’ll just use a basic 4×4 grid:

Now, I’ll give you the walk phase as a sequence of frames here; it’s not that interesting, really, until it reaches a dead-end.

And there our liesurely inebriated stroll comes to a screeching halt. All possible directions lead either out of bounds, or into an already-visited neighbor. At this point, the recursive backtracker would begin backtracking, looking for a previously visited cell in the stack that had unvisited neighbors. The hunt-and-kill algorithm is not nearly so sophisticated: stuck? Go hunting.

And so we hunt. Beginning at the first row, we begin scanning each row for an unvisited cell with a visited neighbor. It turns out to be our lucky day: our very first cell is a match: unvisited, with a visited neighbor. We connect the two:

And then we start a random walk from our new starting point:

Stuck again, so we go hunting. There are no cells in the first row that match:

And no matches in the second row, either. (Remember, we’re looking for unvisited cells with visited neighbors.)

The third row, however, has a match in its last cell:

So, we connect that unvisited cell to any one of its visited neighbors (at random), and do our random walk:

And we again stub our digital toes (see what I did there?) on another dead-end. We’re stuck, so we go hunting again, looking row-by-row for an unvisited cell.

The scan completed without finding any unvisited cells, so the algorithm terminates and leaves us with our maze.

Try the following demonstrations to see how the algorithm behaves at larger resolutions:

<link href=”http://jamisbuck.org/mazes/css/mazes.css” />

Implementation

This algorithm is pretty straightforward to implement. It even has a few simple optimizations that you can do, though I won’t touch on those here.

My implementation begins by choosing a random starting point, and then looping over the two phases, “walk” and “hunt”, until the hunt phase terminates without finding any new location. My walk and hunt implementations both return either a two-element array (indicating the coordinates of the next starting location), or a nil (indicating that the phase in question has terminated).

1
2
3
4
5
6
7
x, y = rand(width), rand(height)

loop do
  x, y = walk(grid, x, y)
  x, y = hunt(grid) unless x
  break unless x
end

The walk implementation is straightforward. It just iterates over a randomized list of directions, and returns nil if none of the directions are valid:

1
2
3
4
5
6
7
def walk(grid, x, y)
  [N, S, E, W].shuffle.each do |dir|
    # ...
  end

  nil
end

For each direction, it computes the neighbor in that direction, and then tests it to see if it is within the bounds of the maze and unvisited:

1
2
3
4
nx, ny = x + DX[dir], y + DY[dir]
if nx >= 0 && ny >= 0 && ny < grid.length && nx < grid[ny].length && grid[ny][nx] == 0
  # ..
end

When a neighbor is found that fits the bill, the neighbor and the current cell are connected, and the neighbor is returned as the new current cell:

1
2
3
grid[y][x] |= dir
grid[ny][nx] |= OPPOSITE[dir]
return [nx, ny]

The hunt phase, on the other hand, is a little more involved (but not much). It iterates over each cell in the grid, row-wise, skipping visited cells, and returning nil if it does not find any unvisited cellls:

1
2
3
4
5
6
7
8
9
10
11
def hunt(grid)
  grid.each_with_index do |row, y|
    row.each_with_index do |cell, x|
      next unless cell == 0

      # ...
    end
  end

  nil
end

Within that innermost loop, if the cell is unvisited, we compute a list of neighbors that are already part of the maze:

1
2
3
4
5
neighbors = []
neighbors << N if y > 0 && grid[y-1][x] != 0
neighbors << W if x > 0 && grid[y][x-1] != 0
neighbors << E if x+1 < grid[y].length && grid[y][x+1] != 0
neighbors << S if y+1 < grid.length && grid[y+1][x] != 0

Then, we randomly choose one of them (skipping to the next cell if there are no neighbors to select):

1
direction = neighbors[rand(neighbors.length)] or next

Then, we compute the coordinates of the neighbor in the chosen direction, carve a passage to it, and then return the new current coordinates:

1
2
3
4
5
6
nx, ny = x + DX[direction], y + DY[direction]

grid[y][x] |= direction
grid[ny][nx] |= OPPOSITE[direction]

return [x, y]

And there’s your hunt-and-kill algorithm!

Conclusion

The random walk phase tends to produce long, windy passages that are reminiscent of the recursive backtracking algorithm, so if you like the aesthetic of one, you’ll probably enjoy the other, too. Both algorithms produce mazes with fewer dead-ends than most of the other algorithms.

The hunt-and-kill algorithm will always have a place in my heart, because it was a variation on it that introduced me to maze generation back in high school. It was first shown to me by Stefano Mazzocchi when he was an exchange student at my alma mater (Siuslaw High School, in tiny Florence, Oregon). In fact, it was this variation on the hunt-and-kill that I used when I wrote a (somewhat popular) random dungeon generator for D&D back in 2001! (All that remains now is some C source code on GitHub, alas.)

Anyway, enough nostalgic wallowing. Have a go at the hunt-and-kill algorithm, and share links to your creations in the comments. For reference, the complete source for my own implementation is here:

<noscript>hunt-and-kill.rb on gist.github.com</noscript>

Enjoy!

#250 Authentication from Scratch

Password authentication is not too complicated to make from scratch, it will also help to get a better understanding of how it works.

#250 Authentication from Scratch

Password authentication is not too complicated to make from scratch, it will also help to get a better understanding of how it works.

Ruby Programming 22nd Batch: An Intensive, Online Course For Beginners

Introducing an intensive, online course for beginners that helps you get started with Ruby programming.

What’s Ruby?

Ruby

According to http://www.ruby-lang.org/en/ – “Ruby is a dynamic, open source programming language with a focus on simplicity and productivity. Ruby’s elegant syntax is natural to read and easy to write.”

Yukihiro Matsumoto, the creator of Ruby, in an interview says –

I believe people want to express themselves when they program. They don’t want to fight with the language. Programming languages must feel natural to programmers. I tried to make people enjoy programming and concentrate on the fun and creative part of programming when they use Ruby.

What Will I Learn?

In the Ruby programming course, you will learn the essential features of Ruby that you will end up using every day.

Depending on participation levels, we throw a Ruby coding challenge in the mix, appropriate for the level we are at. We have been known to give out a prize or two for the ‘best’ solution.

Who’s It For?

An absolute beginner but with some experience in some other programming language.

You can read what past participants have to say about the course. Click here.

Mentors

Satish Talim, Satoshi Asakawa, Victor Goff III and others from the RubyLearning team.

Dates

The course starts on Saturday, 5th March 2011 and runs for two months.

RubyLearning’s IRC Channel

Most of the mentors and students hang out at RubyLearning’s IRC (irc.freenode.net) channel (#rubylearning.org) for both technical and non-technical discussions. Everyone benefits with the active discussions on Ruby with the mentors.

Update

24th Feb. 2011: Today is Ruby’s 18th birthday and we are celebrating this occasion by offering a US$ 10 discount till 1st March 2011 on the course fees and eBook.

How do I register and pay the course fees?

  • The course is based on the The Ultimate Guide to Ruby Programming eBook. This book is normally priced at US$ 19.95 and we are discounting it US$ 10.00 by combining it in the Course+eBook option below.
  • You can pay either by Paypal or send cash via Western Union Money Transfer or by bank transfer (if you are in India). The fees collected helps RubyLearning maintain the site, this Ruby course, the Ruby eBook, and provide quality content to you.
  • Once you pay the fees below, register on the RubyLearning.org site and send us your name and registered email id while creating an account at RubyLearning.org to satish [at] rubylearning [dot] com
  • We will enroll you into the course. If you have purchased the eBook at the time of registration, we will personally email you the eBook within 24 hours.

You can pay the Course Fees by selecting your option from the menu below.

Register

At the end of this course you should have all the knowledge to explore the wonderful world of Ruby on your own.

Here are some details on how the course works:

Important:

Once the course starts, you can login and start with the lessons any day and time and post your queries in the forum under the relevant lessons. Someone shall always be there to answer them. Just to set the expectations correctly, there is no real-time ‘webcasting’.

Methodology:

  • The Mentors shall give you URL’s of pages and sometimes some extra notes; you need to read through. Read the pre-class reading material at a convenient time of your choice – the dates mentioned are just for your guideline. While reading, please make a note of all your doubts, queries, questions, clarifications, comments about the lesson and after you have completed all the pages, post these on the forum under the relevant lesson. There could be some questions that relate to something that has not been mentioned or discussed by the mentors thus far; you could post the same too. Please remember that with every post, do mention the operating system of your computer.
  • The mentor shall highlight the important points that you need to remember for that day’s session.
  • There could be exercises every day. Please do them.
  • Participate in the forum for asking and answering questions or starting discussions. Share knowledge, and exchange ideas among yourselves during the course period. Participants are strongly encouraged to post technical questions, interesting articles, tools, sample programs or anything that is relevant to the class / lesson. Please do not post a simple "Thank you" note or "Hello" message to the forum. Please be aware that these messages are considered noises by people subscribed to the forum.

Outline of Work Expectations:

  1. Most of the days, you will have exercises to solve. These are there to help you assimilate whatever you have learned till then.
  2. Some days may have some extra assignments / food for thought articles / programs
  3. Above all, do take part in the relevant forums. Past participants will confirm that they learned the best by active participation.

Some Commonly Asked Questions

  • Qs. Is there any specific time when I need to be online?
    Ans. No. You need not be online at a specific time of the day.
  • Qs. Is it important for me to take part in the course forums?
    Ans. YES. You must Participate in the forum(s) for asking and answering questions or starting discussions. Share knowledge, and exchange ideas among yourselves (participants) during the course period. Participants are strongly encouraged to post technical questions, interesting articles, tools, sample programs or anything that is relevant to the class / lesson. Past participants will confirm that they learned the best by active participation.
  • Qs. How much time do I need to spend online for a course, in a day?
    Ans. This will vary from person to person. All depends upon your comfort level and the amount of time you want to spend on a particular lesson or task.
  • Qs. Is there any specific set time for feedback (e.g., any mentor responds to me within 24 hours?)
    Ans. Normally somebody should answer your query / question within 24 hours.
  • Qs. What happens if nobody answers my questions / queries?
    Ans. Normally, that will not happen. In case you feel that your question / query is not answered, then please post the same in the thread – “Any UnAnswered Questions / Queries”.
  • Qs. What happens to the class (or forums) after a course is over? Can you keep it open for a few more days so that students can complete and discuss too?
    Ans. The course and its forum is open for a month after the last day of the course.

Remember, the idea is to have fun learning Ruby.

Technorati Tags: , , ,

Rails Ready: Ruby and Rails on Ubuntu in One Line

How would you like to get a full Ruby on Rails stack up on Ubuntu with one command?

Now you can by running Rails Ready. Rails Ready is a setup script that gets Ruby and Rails running on a fresh install of Ubuntu with one command (Tested on Ubuntu server 10.04 LTS (Long-term Support)).

Adam Stacoviak

Rails Ready is essentially just a shell script but one you might find useful if you’re running Ubuntu (or – update – CentOS) and want to get the installation process done and over as quickly as possible. It follows on rather nicely to our last post: Ruby Installer: Ruby and Rails on Windows in a Single, Easy Install!

If you have the time or you’re installing this on your main development machine, however, I would recommend following Ryan Biggs’ RVM based instructions (or my equivalent screencast) because RVM gives you more developer-level control later on (such as gem sets). UPDATE – Josh has been working hard and says that Rails Ready “now asks you if you want to build from source or install RVM” – nice!

Nonetheless, if you want to get a new Ubuntu (or CentOS) box running Rails as quickly as possible, Rails Ready is worth a try. The short version:

wget --no-check-certificate https://github.com/joshfng/railsready/raw/master/railsready.sh && bash railsready.sh

Before running the above, though, be aware of the ramifications. You should probably take a look at https://github.com/joshfng/railsready/raw/master/railsready.sh yourself to see if it’s suitable for you.

Maze Generation: Wilson’s algorithm

The last algorithm I mentioned, Aldous-Broder, was (if you’ll recall) originally devised as a way to generate uniform spanning trees (UST). (Review: a spanning tree is a tree that connects all the vertices of a graph. A uniform spanning tree is any one of the possible spanning trees of a graph, selected randomly and with equal probability.)

Aldous-Broder was effective, but inefficient. For this (the seventh!) article in my series on maze algorithms, I’ll focus on Wilson’s algorithm for selecting uniform spanning trees.

The algorithm goes something like this:

  1. Choose any vertex at random and add it to the UST.
  2. Select any vertex that is not already in the UST and perform a random walk until you encounter a vertex that is in the UST.
  3. Add the vertices and edges touched in the random walk to the UST.
  4. Repeat 2 and 3 until all vertices have been added to the UST.

So, it’s still doing the random walk, but I think you’ll see that this algorithm converges much more rapidly than Aldous-Broder. It’s still annoying to watch an animation of the early stages of the process, but not nearly as bad as the other.

As before, here’s a simple example of the algorithm in action.

An example

A 4×4 grid will suffice for this demo.

We begin by randomly adding a cell to the maze:

Then, we pick another unvisited cell at random and do a random walk until we encounter that first cell. Note that this random walk has a few constraints: although it can cross cells it has already walked (as long as they are not already in the maze), we don’t want to allow the final path to have any loops in it. Thus, we also record the direction most recently used to exit each cell, and will use those directions to form the final path once the walk encounters an “in” cell.

Once we reach a cell that is already part of the maze, the walk terminates. The next phase simply goes back to the cell at the beginning of the walk, and follows the arrows, adding vertices and edges to the maze as we go, until we reach the final cell of the walk.

All the other cells that were visited during the walk, but which did not make the “final cut”, as it were, are simply reset to “out”.

Now, we do it again. Notice that this time there are four cells in the maze, rather than just one, giving us many more targets for the walk to hit. This is what lets the algorithm converge more rapidly than Aldous-Broder: each pass through the algorithm increases the odds that the next pass will terminate sooner.

Here we go, another pass. I’m going to “cheat” and let this one consume more cells than it might (probabalistically) do otherwise. Just to keep the article shorter. 🙂

Then we walk the path and add the vertices and edges to the maze, again:

By now you should be able to see the pattern emerging. Each pass would add another random “branch” to the tree, proceeding until all cells have been added to the maze.

Try the following demos if you’d like to see an animation of the algorithm in action, or step through it more carefully:

<link href=”http://jamisbuck.org/mazes/css/mazes.css” />

Implementation

Personally, I found Wilson’s algorithm to be one of the messiest to implement, mostly due to the necessity of keeping track of directions while doing the random walk. I’m sure there are cleaner ways to implement this. Yes, that is a challenge! (Admittedly, some of the complexity of my implementation is due to it trying to animate the algorithm; feel free to simplify your own attempt.)

The algorithm begins by setting a random cell as “in”, and recording how many cells still remain outside:

1
2
grid[rand(height)][rand(width)] = IN
remaining = width * height - 1

Then, I simply loop until there are no more cells that are outside the maze:

1
2
3
while remaining > 0
  # ...
end

Within the loop, the random walk is performed. For now, I’m going to wave my hands and we’ll move on, but I’ll describe the walk method more closely in a bit. It returns the path that was taken as an array of (x, y, direction) tuples:

1
2
3
walk(grid).each do |x, y, dir|
  # ...
end

For each cell in the random walk, we add it to the maze (by applying the given direction bit to each cell in the path), and then decrement the number of remaining cells:

1
2
3
4
5
6
nx, ny = x + DX[dir], y + DY[dir]

grid[y][x] |= dir
grid[ny][nx] |= OPPOSITE[dir]

remaining -= 1

Now, the walk method itself is the messy bit. It begins by looping until a random cell is selected that is not in the maze:

1
2
3
4
5
6
7
8
def walk(grid)
  loop do
    cx, cy = rand(grid[0].length), rand(grid.length)
    next if grid[cy][cx] != 0

    # ...
  end
end

Once a starting point is found, I initialize a hash of visited cells (where I will record both the coordinates of each cell in the walk, as well as the direction last used to exit the cell). And then I start walking:

1
2
3
4
5
6
7
8
visits = { [cx, cy] => 0 }

start_x, start_y = cx, cy # where the random walk started
walking = true

while walking
  # ...
end

Now, inside the walking loop, I first set walking to false (since I’m going to be optimistic and assume that the next move will hit an “in” cell). Then, I look at a randomized list of directions:

1
2
3
4
walking = false # cross fingers!
[N,S,E,W].shuffle.each do |dir|
  # ...
end

For each direction in the randomized list, we’ll compute the neighbor in that direction and then check that the neighbor is actually a valid cell (within the boundaries of the grid):

1
2
3
4
nx, ny = cx + DX[dir], cy + DY[dir]
if nx >= 0 && ny >= 0 && ny < grid.length && nx < grid[ny].length
  # ...
end

Once a valid neighbor is found, we immediately record that direction as the exit vector from the current cell.


visits[[cx, cy]] = dir

Then, if the neighbor cell is already in the maze, we get to break out of the loop (because we’ve finished the walk). Otherwise, we set the neighbor to be our current cell, and we continue walking:

1
2
3
4
5
6
7
if grid[ny][nx] != 0
  break
else
  cx, cy = nx, ny
  walking = true
  break
end

Once we’re done walking, we still need to convert the visits hash to a valid path, which we’ll return. I do this by following the visits from the start cell, through the direction used to exit visited cell, until the path ends:

1
2
3
4
5
6
7
path = []
x, y = start_x, start_y
loop do
  dir = visits[[x, y]] or break
  path << [x, y, dir]
  x, y = x + DX[dir], y + DY[dir]
end

Finally, we return the path, which the top-level loop uses to add the cells to the maze:


return path

Whew!

Conclusion

Wilson’s is still not a very efficient algorithm: on large grids, the first walk can be excruciatingly slow. However, it’s much nicer than Aldous-Broder, and is still guaranteed to return a uniform spanning tree.

I’m sure any of you could do a better job implementing this than I’ve presented here. In fact, I’d love for you to prove it. 🙂 Give it a try and link to your implementations in the comments!

For reference, the complete source for my own (Ruby) implementation is here:

<noscript>wilsons.rb on gist.github.com</noscript>

Enjoy!

Agile in a Flash (Cards!)

It’s not a book. It’s a deck of cards. Agile in a Flash: Speed-Learning Agile Software Development now in print and shipping.

Ruby on Rails Engineer at Tupalo.com

Ruby on Rails Engineer at Tupalo.com

Tupalo.com

Tupalo.com is one of Austria’s fastest growing privately held internet startups, creating a local search community where millions of people review and share the best local businesses around the World every month.

Tupalo.com is looking for Ruby on Rails engineers to join their development team full-time in Vienna, Austria. You should enjoy building scalable, high-performing web services and love all things web, especially location-based services. In addition, you should enjoy working in a startup environment where you can flex your entrepreneurial spirit, but still work closely with a group of passionate developers, designers and their office dog, Laika the Beagle.

Interested in working at a profitable, development-driven startup with heart, character and enthusiasm in the center of Vienna, Austria? Head over to Jobs at Tupalo.

Post supported by Tupalo.com: Their social yellow-pages app developed using Ruby on Rails uses many of the other exciting tools like Cucumber, RSpec, Capistrano and Puppet, Ruby developers came to appreciate.

Technorati Tags: , , ,