Primitive Low Level Optimization in Ruby

...

Step 1. Create a gem

        
❯ bundle gem --test=rspec --no-ci --no-linter --mit --no-changelog primitive
        
        
Creating gem 'primitive'...
rspec is already configured, ignoring --test flag.
MIT License enabled in config
Initializing git repo in /home/vlad/Code/primitive
create  primitive/Gemfile
create  primitive/lib/primitive.rb
create  primitive/lib/primitive/version.rb
create  primitive/sig/primitive.rbs
create  primitive/primitive.gemspec
create  primitive/Rakefile
create  primitive/README.md
create  primitive/bin/console
create  primitive/bin/setup
create  primitive/.gitignore
create  primitive/.rspec
create  primitive/spec/spec_helper.rb
create  primitive/spec/primitive_spec.rb
create  primitive/LICENSE.txt
Gem 'primitive' was successfully created.
        
      

Step 2. Add code that does something useful

Specs

        
# frozen_string_literal: true

RSpec.describe Primitive do
  describe "#edit_distance" do
    let(:examples) do
      [['', 'abc', 3],
       ['abc', '', 3],
       ['a', 'abcdefgh', 7],
       ['kitten', 'sitting', 3],
       ['saturday', 'sunday', 3],
       ['tuesday', 'thursday', 2],
       ['hematology', 'hepatology', 1],
       # Counts characters rather than bytes: dropping '語' is one edit, not three.
       ['日本語', '日本', 1],
       ['café', 'cafe', 1],
    end

    specify do
      examples.each do |s1, s2, expected_distance|
        expect(described_class.edit_distance(s1, s2)).to eq(expected_distance)
      end
    end
  end
end
        
      

Implementation

        
# frozen_string_literal: true

require_relative "primitive/version"

module Primitive
  class Error < StandardError; end

  def edit_distance(s1, s2)
    table = Array.new(s1.size + 1) { |i| Array.new(s2.size + 1) { |j| i + j } }
    1.upto(s1.size) do |i|
      1.upto(s2.size) do |j|
        table[i][j] =
          [
            table[i][j - 1] + 1,
            table[i - 1][j] + 1,
            table[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1)
          ].min
      end
    end
    table[s1.size][s2.size]
  end

  module_function :edit_distance
end