Edward Loveall

Random Access Permutations

Years ago, I was building a game. It was a puzzle game on a gridded board: clear the board in as few clicks as possible. The order you clicked mattered. It’s fun and I’ll blog about it someday.

A friend of mine suggested that I randomly generate levels and build a solver to create and evaluate infinite puzzles. As an amateur programmer my initial (and only) idea was to use brute-force to solve the puzzles. This meant clicking on every piece in every possible order, i.e. permutations.

Since there were many permutations on some boards (easily 1080 or more), I wanted to be able to split up the process. Do 100,000 now, and another 200,000 later. This meant I needed to resume where I left off.

The problem is, many permutation algorithms rely on the previous permutation to generate the next one. For example, Heap’s Algorithm uses a swapping method that swaps two elements every time to create the next permutation.

A B C D <-- swap A & B to get
B A C D <-- swap B & C to get
C A B D <-- swap A & C to get
A C B D ... etc

If I want permutation 100,000 I’d have to run through the first 99,999. I needed a way to get a permutation based on an offset (random access) instead of what came before it (sequential access). I worked on this problem on and off since then and I recently cracked it. That’s what this post is about.

How it works

If I’m being honest, this shouldn’t have taken me several years, even working on it occasionally. The solution didn’t end up being particularly complex in theory or implementation. (Although buckle up for my attempt to explain it with words.)

It works by taking advantage of the fact that one valid way to generate permutations keeps consecutive sections of each item in the first item of the permutation. The remaining items mirror the next-smallest permutation, including the consecutive item in the first slot.

For example, a 4-item permutation of A B C D:

A B C D
A B D C
A C B D
A C D B
A D B C
A D C B
B A C D
B A D C
B C A D
B C D A
B D A C
B D C A
C A B D
C A D B
C B A D
C B D A
C D A B
C D B A
D A B C
D A C B
D B A C
D B C A
D C A B
D C B A

The number of permutations is the number of items factorial which is 4! = 26 in the above case. You can see that for the first 6 permutations, A is in the first slot. I’m calling that a section. Each section lasts for the total number of permutations divided by the number of items in the set. There are 4 items and 26 permutations, so there are 4 sections of 6 permutations each.

Recap: 4-item set, 24 permutations total, 24/4 = 6 permutations per section. Each section features one of each item as the first item. First A, then B, etc.

The algorithm finds out which zero-indexed section you’re in based on the permutation offset you want. The permutation at the 6th offset is all_permutations[5]. That section number will be the index of the item in the set that goes in the first slot of the permutation. Section 0 = index 0 = A in this example.

Once you have the first index, reduce the number of items in the permutation by 1 (down from 4 to 3 for example) and find which section you’re in again. Do this until you have no items left.

You’ll end up with a list of indexes the same length as your set. Loop through each index and move the item at that index into a new array. At the end your new array will be your permutation.

Visualization

View this using Algorithm Visualizer

Depending on what kind of learner you are, learning about an algorithm through prose may not work for you. For those that learn better by visualizing and stepping through code, I’ve put the algorithm into Algorithm Visualizer. Check it out here.

Code

I’ve uploaded Ruby code for this here. The core algorithm is about 8-lines and the whole Ruby class is 30 including whitespace.

I did some benchmarks and in a worst-case scenario (retrieving the last permutation) my algorithm performs so much faster. Here are the results on an 8-item set (40,320 permutations):

       user        system    total     real
ruby:  12.313426   0.013559  12.326985 ( 12.341237)
new:    0.005471   0.000023   0.005494 (  0.005494)

4 orders of magnitude faster! I also tested it on large sets, like a 100-item sets and it doesn’t break a sweat. In computer science terms, it’s always O(n) instead of O(n!) where n is the number of items. For that 8 item set, that’s either a worst-case time of 40,320 operations, or 8.

Suffice it to say, I’m very happy with the algorithm. I don’t know if it will actually ever help me build a game, but this makes me feel like I got the high score.

Update

A helpful commenter on lobste.rs pointed out that this is like Lehmer codes! I knew there must be something else out there in the world that could do this, and it turns out it’s almost exactly the same as my algorithm, just with different names.

My Music Workflow

Finding good music isn’t so hard these days. It’s easy to open Spotify (or whatever) and take in the suggestions. Check out generated playlists, songs sorted by genre, and even good ol’ music blogs.

Making your own playlists is easy too, but sometimes it’s difficult to figure out what makes the cut. Deciding that a song “favorite” good or just “dinner party” good is never easy on the spot.

Well, I’ve got a system for generating a good playlist. It will generate a playlist that represents your unique musical style and yet is impossible to categorize. Best of all, it’s set up so you don’t have to make a hard decision the first time you hear the song.

Step 1 - Recommendations

Every week, listen to Spotify’s Discover Weekly and Release Radar. Don’t use Spotify? That’s fine. Seek out some music you’ve never heard before. Most (all?) music services have recommendations. Ideally you can find a playlist with songs from diverse sources.

Any song that captures your interest in any way, throw it into a playlist called Weekly Maybe. You may even decide halfway through the song it will not be for you long-term. That’s fine. Throw it in anyway.

Step 2 - Curate

At the end of the week I have about 5-10 songs in Weekly Maybe. Take those songs and pick which ones you want to keep from that list.

This part is admittedly a little tough. Again, what makes the cut? You’re looking for songs you wouldn’t mind hearing again, randomly, in most situations. You’ve already had some distance from your first listen, which is helpful. How does it strike you on listen 2? 3? 10?

Step 3 - Save

If you’re still enjoying after a few listens, you keep it. Chuck it in a playlist called Starred or Favorites or Heck Yes. I usually end up with 2-3 per week, but sometimes nothing makes the cut. It’s not always a great week for the algorithms, you know? This is the good stuff. If someone ever asks you “What kind of music do you like?” you point them here.

But what about the other Weekly Maybe songs? They were still interesting, but maybe not every-day songs. You put all those in different playlist. I call mine Dark Starred but Rainy Day or Yes These Are Songs is also fine.

This gives you a nice list to go to when your songs on heavy rotation are feeling stale. They will interest but not amaze. This is sometimes exactly what you need to kick off another deep dive to find that next good song.

Bonus

If your music service has a way to songs you like, you can select everything in that best-of playlist. It will then feed back into their recommendation algorithms and you’ll get more interesting music!

The Rails presence Method

Rails has a convenient method that I discovered the other day: presence. All it does is return itself if present?. It’s a pretty simple method:

def presence
  self if present?
end

The documentation has a great example that simplifies this:

state   = params[:state]   if params[:state].present?
country = params[:country] if params[:country].present?
region  = state || country || 'US'

to this:

region = params[:state].presence || params[:country].presence || 'US'

Here’s another use case. Imagine your app has a page where you can search for users. There’s a show.html.erb template, and two partials: user.html.erb and no_results.html.erb.

Your controller will search for users and assign them to an instance variable. If no users were found, we’d rather show the no_results partial instead of a blank page:

<% if @users.present? %>
  <%= render @users %>
<% else %>
  <% render 'no_results' %>
<% end %>

With presence we can make this code shorter but still readable.

<%= render @users.presence || 'no_results' %>

Most of the time present? is probably what you’re looking for, but sometimes presence really cleans up your code. Keep it in mind.

Comparing Rails and Lucky: Partials

If you’re a Rails developer, you’ve likely used partials. They’re a great way of splitting up a view into many reusable parts.

Consider displaying a search form:

<nav class="main">
  <%= render "search" %>
</nav>

We use render to insert a partial with the filename _search.html.erb. In this instance, it will render an input field and a button to fetch search results. This is especially useful when we want to use this search form all over the app.

Lucky also has the ability to reuse parts of a page, but in a slightly different way. These differences make for a more streamlined and safe approach.

Lucky will generate HTML programmatically rather than with templates. For example:

def content
  nav class: "main" do
    h1 "My Awesome App"

    link "Sign In", to: Users::New
  end
end

This gets converted into HTML. It’s a fresh change of pace from flipping back and forth between regular HTML and Ruby. But rendering partials is even nicer. Partials in Lucky are called Components. Here’s how to use one.

In src/components/searches/search_component.cr you would create a module:

module Searches::SearchComponent
  def render_search(search_form : SearchForm)
    form_for Searches::New do
      text_input search_form.query
      submit "Search"
    end
  end
end

This is the same as our _search.html.erb partial in Rails. If we wanted to use this on a page, we can include our new module and call the render_search method:

include Searches::SearchComponent

needs search_form : SearchForm

def content
  nav class: "main" do
    h1 "My Awesome App"
    render_search @search_form

    link "Sign In", to: Users::New
  end
end

This looks a lot like rendering a partial in Rails and the result is very similar. The big difference here is Lucky is written with Crystal which uses type checking. Type checking ensures that the only way to call a method is by passing all arguments.

Our render_search method requires a SearchForm object. Because of type checking, there is no way to call that method unless we pass a SearchForm.

Compare this to the Rails render method. We can’t guarantee a SearchForm will always be available to the partial. I’ll bet that anyone who has worked with Rails for a year or more has experienced this pain.

Lucky makes it impossible to forget these required objects. If we left out @search_form above, the app won’t even compile, let alone crash when running.

Put another way, to use a partial or component we need some kind of identifier. In the case of Rails, the only identifier is the file name, not the objects that are used inside of it. In the case of Lucky, it’s the name of the method and the objects you pass to it, including the objects that are used inside. If you can’t pass all the objects every time, the app will refuse to compile.

Of course, we can (and should!) use this technique often:

render_search(@search_form)
render_sign_in(@sign_in_form)
banner(@annoucments)
user_list(@users)

I haven’t decided on the best way to name these. They could all be render or display and are only differentiated by their method arguments. Or maybe they’re all verbose like render_search_form. Or maybe something else! I haven’t settled on the best pattern for this, yet.

One thing that comes up over and over again when working with Lucky is safety. As wonderful as Rails is, we can often find ourselves rendering a view with a nil or incomplete object. Since Lucky has Crystal as its foundation, it’s a much safer framework to work with than Rails. With safety comes benefits like fewer crashes and unwanted side-effects. But it also enables flexibility and developer confidence.

A Week with Lucky

A little over a week ago, thoughtbot announced they were building a new web framework called Lucky. It’s built with Crystal just as Rails is built with Ruby. Its goals are best summed in the description of the main repository:

Catch bugs early, forget about most performance issues, and spend more time on code instead of debugging and writing tests.

I’ve now spent about a week with Lucky building a test app and I’ll talk about what I’ve found here. As a professional Rails developer, I’ll be comparing it most to Rails. There are some stark, and welcome, differences. This isn’t just Crystal on Rails.

Crystal

First Crystal, the language that built Lucky. It bills itself as a type-safe, very performant alternative to Ruby and the likeness to Ruby is strong. You can take a look at their tutorials or even see the distinctions to Ruby in their Crystal for Rubyists document. TL;DR: if you’re comfortable with Ruby, it won’t take you long to learn much of Crystal.

Actions instead of Controllers

Rails uses controllers which contain multiple actions. Lucky splits everything up into individual actions. This likely has many advantages that I haven’t discovered yet, but one is now you can link directly to an action class:

link "Topics", to: Topics::Index

You can see this in…

Pages instead of Views

Pages are still largely being worked on and will likely go through many changes. One big separation from Rails is all of the page source is written with Crystal, not a templating language like ERB. I imagine this helps keep the views pretty fast as they are now complied along with the rest of the app. It also allows the framework to force developers to identify exactly what the view needs from the action.

Update: Crystal has its own equivalent to ERB called ECR. There’s also something similar to Slim called Slang. Thanks to Isaac Sloan for pointing this out!

For example, the view linked above has two needs declarations at the top. Every time the app renders this page (topics/index_page.cr) it must specify a topics object of type TopicQuery and a vote_form of type VoteForm. No more rendering views with critical dependencies missing!

Models haven’t gone anywhere

Models, along with migrations, are still the preferred pattern to generate and encapsulate data. The biggest differences are models are tiny and type-safe. You specify which fields (attributes) are required and which are optional. These get enforced not only with validations but at the database level too.

In this migration, title has a not-null constraint in the database. description, however, is nilable and doesn’t get that restriction. It forces you as a developer to think about what you’re adding and if it’s required.

Queries

Queries to me feel like they’re an extension of models. Instead of cramming all of your scopes and state checking into a model class, you can break that out into a query class. In the linked query object here, you can see a newest_first method that sorts queries by their created_at date in descending order.

Forms

I feel like of all the parts of Lucky, I understand forms the least. Talking to the creator, Paul Smith, they are still very much in flux. Forms are where you define validations. Previously, when I was mentioning how migrations can specify which columns have an automatic not-null constraint in the database, they also get an automatic required validation.

Breaking traditional Rails models into Lucky’s models, queries, and forms I think will serve it well in the long run.

Assets

Lucky is all-in on using yarn (with node) to manage assets. Rails put a lot of work into making yarn the default asset manager, and this is after 10 years of its asset pipeline. I think this is exactly the right thing to do.

As a side note, Lucky ships with PostCSS by default, something I hadn’t heard of or worked with before. It’s not quite a pre-processor for CSS. If you’re curious about it, I found these articles to be helpful.


Lucky seems promising. I’m excited to see how it evolves and what new community patterns develop around it. Crystal is a joy to work with while type-safe languages are in style.

While it’s not ready for prime-time, it’s worth spending a quick weekend on to see what it can do. You can use my project’s commits as a guide on how to build an app step by step or check out Lucky’s guides which are being added rapidly.

It’s very exciting to be at the dawn of a framework. Lucky has a lot of potential. I hope you’ll check it out.

Apple's Watch Series 3 Webpage

Have you seen the new Apple Watch Series 3 page? It’s incredible. Whether you care about the device itself, it’s a pretty amazing feat of web development.

If you have some kind of smooth scrolling device like a trackpad or your phone, look at the swimmer/bubbles while you scroll around. It looks like a whole 3D scene is set up with depth and lighting.

In fact, I’m pretty sure that’s what’s Apple created.

Poking around in their source code, we can see a few things.

three.js

three.js is a javascript library for creating and rendering interactive 3D scenes on the web. It’s great. Apple has used it in the past for things like its High Sierra page. It is also included in this Apple Watch page.

3D Assets

Included or downloaded with the page are a few different assets:

glTF: A format for storing models and 3D scenes in a JSON-like format. An example would be Swimmer.gltf.

Collada: This seems to be pretty similar to gltf but XML instead of JSON? I’m not sure, but I know you can download it and actually view it on a macOS natively. Download Swimmer.dae and open it in Preview.app on a Mac.

Binary files: There are also some binary files that I imagine hold color or image data. I can’t figure out how to read them though: Swimmer.bin.

With three.js and all these 3D asset files, it seems pretty clear that Apple is setting up a 3D scene, and moving a virtual camera around when you scroll. You can see that they’re setting up a perspective camera by searching for camera in this obfuscated Javascript file.

The folks working on the web team at Apple is doing are doing a hell of a job.

ColorClockSaver

Today I’m releasing ColorClockSaver. It’s a screensaver that:

It looks like this:

A screenshot of the ColorClock Screensaver

It also features:

ColorClockSaver is free and open-source. It can be downloaded here.

Inspiration and history

I always loved thecolourclock.co.uk but it is entirely based in Flash. So I made my own version of it using QuartzComposer. It’s all I knew how to use at the time.

I ran this as a screensaver for years and so did family and friends, but it was limited. It couldn’t use an embedded font, or have any settings.

This made for a great excuse to learn more about macOS development. After lots of trial and error, this is the result.

The time as a hex color code?

The screensaver shows two pieces of text, the current time and a hex number below it.

Because colors can be made up of three components (red, green, and blue), they are often represented as hex colors. For example:

6EC6E9

Each pair of digits represents the amount of intensity for each color component. 6E for red, C6 for green, and E9 for blue. This creates the soft blue you see in the screenshot above.

These numbers are picked because of the current time. Time also has three components: hour, minute, and second. Each component has 24 or 60 steps. However, these hex pairs have 256 steps. I’ve divided the hex numbers into 24 (hour) or 60 (minute, second) evenly spaced increments. These are then mapped back to the amount of red, green, or blue.

You can see a bunch of other colors and experiment yourself here: html-color.codes

And enjoy the screensaver!

The Stages of Video Game Obsession

While playing a video game, I’ve noticed that I’m usually experiencing one of five stages:

Ramp up

This consists of character creation, tutorials, looking up what things mean, and other beginner tasks. It’s often hard to get past this stage, but my initial excitement (and money spent) usually gets me through it.

Totally obsessed

I can’t stop thinking about this game. It’s all I want to do or read about. Left to my own devices, I would just play it all day, nonstop. I want everyone around me to play it too so I have more excuses to play and talk about it.

Good fun

I like playing the game and still choose to spend time on it. There are many fun challenges left to overcome, but I can also enjoy other activities. When with friends, I still enjoy talking about the game, but I don’t feel the urge to constantly bring it up.

Tedious grind

This happens when I feel I have a few challenges left I want to complete, but I start questioning if it’s worth the time. I still might complete them, and the reward might even feel good, but it often does not justify the work to get there.

Not fun

I’m sick of the game. I am uninterested in playing because it would be boring with little to no reward. I can find myself here if a friend wants me to play with them after I’ve completed the game.


I find that these stages are pretty common and I experience most of them with most video games. If the game is really good about effortlessly teaching you how to play, the first step feels like the second, and that’s really nice. AAA games are often (but not always) pretty bad at this step and can overwhelm you at first.

Your mileage may vary, of course.

Speeding Up PostgreSQL Database Imports

Instead of using one process to import data, you can use multiple with the --jobs=N flag, where N is the number of logical cores you have. It looks something like this:

pg_restore --clean --no-acl --no-owner --jobs=4 -h localhost -d my_app_development production-data.dump

Using -j N also works.

Don’t know how many logical cores you have?

What now?

Trump was elected. My goal now is to help people who need it. I’ve got a lot of work to do.

But how do I choose what to do? Someone once compared learning how to be an activist like leveling up a character in a game. When you start at first level, all you can do is cast “wear safety pin”. That’s a great start, but you’re not going to kill the evil dragon with it.

So you learn other spells, like “join committee”, or “read book”. Eventually, you learn so many spells that one day, you realize you’ve leveled up. Keep at this long enough, and you can now fight that evil dragon.

I know myself and if I try to level up without external motivations, I’ll let things drop. So I hope that making my plans public will help keep me honest and on track. Even if no one actually reads this, the fact that it exists will give me the motivation I need. Maybe you’ll be inspired to do the same.

Here’s a list of things I am doing or plan to start doing in the near future:

Railsbridge

RailsBridge (and RailsBridge Boston) is an organization that focuses on teaching underrepresented people in tech to program. I have been a TA at a few events and was recently invited to be an organizer. I’m helping with the next event in January.

Mentoring

I have been mentoring people one at a time for about a year, but this last week I took on one more mentee. I’m focusing on a similar group as RailsBridge, underrepresented people in tech.

Diversity/inclusion group

I joined a diversity/inclusion group through a local Unitarian church. Their goal is to “foster diversity and inclusion at the church, in Massachusetts, and beyond.” They hold meetings every week or so (I think) to talk about issues surrounding race, social class, gender, age, and more.

Reading The Righteous Mind

I heard about this book on a podcast and it piqued my interested. It’s about how the political left and right view morality differently. From the book’s introduction:

My hope is that this book will make conversations about morality, politics, and religion more common, more civil, and more fun, even in mixed company.

Seems useful. My hope is to better understand the people I disagree with so I can then focus on the best ways to talk with them, not at them.

Paying attention to what matters

I want to try and make sure I focus my limited attention on substance not fluff. There are enough terrible events right now to fill a garbage dump, and it’s not going to start smelling sweeter. But not all of them are worth my time. John Gruber summed this up well in his recent post:

Twitter is full of people talking about Mike Pence getting booed by the audience at Hamilton last night. Now Trump himself is tweeting about it, focusing news media on the incident. Booing is not meaningful opposition. But it has served to distract from a legitimate scandal: Trump settling a fraud lawsuit for $25 million yesterday. The smart opposition is focused on that today.

First, I want to be able to recognize the right issues instead of the fluff. Once I can do that, I want to make sure I boost those stories instead of non-stories.

Taking breaks from Twitter

Twitter can enable great things, but the constant emergency state that it can produce is too much sometimes. I took a break from Twitter all of last week. I had a lot more energy to accomplish everything in this blog post, and just felt a lot better. I’m not quitting Twitter or all social networks, but I’ll likely be taking more breaks.


This is a lot, but I have a lot of life left to accomplish it. I’m sure I’ll learn more about how to level up as I go. For now, we’ll see how this goes.