Roman Numeral Converter with JavaScript and underscore.js

This post demonstrates how to convert a number to a Roman numeral and vice versa with JavaScript. We’ve already covered how to convert a Roman numeral to an integer and how to convert an integer to a Roman numeral with Ruby. Check out the Roman numeral Wikipedia page to refresh your memory on this archaic number system.

Underscore.js

Underscore.js is an enormously helpful library that provides helper methods to give JavaScript some utility functions that are built-in to most other modern, high-level languages. Underscore helps prevent your code from deteriorating into a hopeless mess of for loops and counter variables.

Converting a Roman Numeral to a Number

A Roman numeral like “LXIV” can be converted to 64 by iterating through all the letters, converting each letter to a number, and summing the numbers. Numbers that are less than the subsequent number are treated as negative to account for irregularities in Roman numeral notation.

romanToNumber = function (roman) {
  var mapping = {
    "M": 1000,
    "D": 500,
    "C": 100,
    "L": 50,
    "X": 10,
    "V": 5,
    "I": 1
  }

  var arr = roman.split("");
  return _.inject(arr, function(memo, letter, i) {
    var num = mapping[letter];
    var next = mapping[arr[i + 1]];
    if (next === undefined || next <= num) {
      return memo + num;
    } else {
      return memo - num;
    }
  }, 0);
};

_.inject() is built into the underscore library. The first argument to inject is a collection and the second is a function that’s run for each iteration. The underscore code is much more readable for programmers coming from a language like Ruby.

Converting a Number to a Roman Numeral

Converting a number to a Roman numeral is a bit more tricky because some Roman numerals are irregular (e.g. 4 equals IV, not IIII). The number to Roman numeral mapping is updated to reflect the irregular Roman numerals.

The Roman numeral is constructed by iterating over every element in the mapping, performing integer division, appending letters to the result, and continuing the process with the remainder of the integer division (aka the modulus). For example, 3100 goes into 1000 three times with a remainder of 100. Three “M”s are appended to the result and the iteration continues with the remainder. 100 goes into 100 one time with a remainder of 0, so the final result if MMMC.

numberToRoman = function (number) {
  var mapping = {
    1000: "M",
    900: "CM",
    500: "D",
    400: "CD",
    100: "C",
    90: "XC",
    50: "L",
    40: "XL",
    10: "X",
    9: "IX",
    5: "V",
    4: "IV",
    1: "I"
  }

  var result = [];
  var keys = _.keys(mapping).reverse();
  _.each(keys, function(k) {
    var div = Math.floor(number / k);
    var mod = number % k;
    _(div).times(function() {
      result.push(mapping[k]);
    });
    number = mod;
  });
  return result.join("");
}
Advertisements

How to Learn Programming Concepts

Software engineers have to retain a massive amount of knowledge and constantly learn new technologies, so it’s important to understand the basic neuroscience behind how the brain absorbs and stores information. The human brain is the most complex device in the known universe, but software developers only need to know some basics to learn more effectively.

Sleep
The brain produces toxins in the awake state that are washed away during sleep, so it’s important to get a good night’s rest. It’s beneficial to attack hard problems first thing in the morning with a “fresh” mind. The behavioral economist Dan Ariely is even making an app to help humans fully utilize their “two hours of peak cognitive capacity”, which is typically first thing in the morning.

Exercise
For most of the brain, neurons are not created or destroyed during life, so the neurons you’re born with are the same as the neurons you die with. It was recently discovered that new neurons are created (called neurogenesis) in the hippocampus, a critical part of the brain for learning and memory. Neurogenesis in the hippocampus is enhanced by exercise and/or a stimulating learning environment.

Practice and Repetition
The brain has working memory and long term memory. Working memory is stored in the prefrontal cortex and can hold 4 chunks of information (think of trying to remember a phone number you just learned). Information in working memory is ephemeral and it requires a concerted effort to hold data in working memory (think of repeating a phone number you just learned over and over to remember it).

Repeatedly studying concepts is the best way to store information in long term memory and practice retrieving the information. It’s best for the practice to be spread out over many days for the brain to fully work out the storage and retrieval of the data. Cramming does not work because the information is not properly stored in long term memory and quickly evaporates.

Letting Your Mind Wander
There are two types of learning:
1. focused – concentrating intently on a subject
2. diffuse – thinking about a subject broadly (how you think about a topic when you’re going on a walk or taking a shower)

When learning, it’s important to engage in both focused and diffuse thinking. It’s important to hit the books and concentrate hard, but then take a break, and contemplate the material at a higher level while relaxing in a chair or walking in the park. Taking a break to broadly brainstorm a problem is not lazy, it’s a critical technique for building strong neural connections.

Practical Suggestions
Living a generally healthy life with adequate sleep and regular exercise creates a healthy body and a healthy mind. The brain is freshest first thing in the morning and it’s best to use this time on productive tasks, not waste it commuting.

Reading over technical concepts passively without revisiting them frequently over the course of several days does not allow the brain to develop strong neural networks and store the information in long term memory. Merely reading a technical book is a waste of time. Learners need to read the book, take notes, write blog posts on what they’re learning, and create quizzes that can be constantly revisited to solidify neural connections. Repetition is the only way to train the brain to store information in long term memory and load the information into working memory at will.

Diffuse thinking should be prioritized. When going for a walk, make an effort to have your mind ponder computer science, not family gossip. Turn your computer off and draw a picture of what your learning. Metaphors and analogies are powerful learning techniques. When I was learning object oriented programming, I always thought of classes as factories that worked to product objects, like an automobile factory. Make your own metaphors and have fun using diffuse thinking to build strong neural connections and efficiently store data in long term memory.

P.S. This post was motivated by the first class of the Coursera Learning How to Learn class.

Ruby’s Ancestors Method

The ancestors method returns an ordered list of classes and modules that corresponds with the method lookup sequence. In the following example, instances of the class A will search for methods in A, Object, Kernel, and BasicObject before calling A#method_missing.

class A; end
A.ancestors # => [A, Object, Kernel, BasicObject]

Before Ruby 2.1, the ancestors method behaved oddly when the receiver was a singleton_class. The ancestors method is now fixed and the interesting method lookup process for singleton methods is on full display.

class A; end
A.singleton_class.ancestors # => [#<Class:A>, #<Class:Object>, #<Class:BasicObject>, Class, Module, Object, Kernel, BasicObject]

When messages are sent to to A, Ruby looks for corresponding methods in A’s singleton class, Object’s singleton class, and BasicObject’s singleton_class. BasicObject.singleton_class.superclass == Class, so the method lookup process continues all the way up to BasicObject, just like regular instance methods. This surprisingly causes A to respond to instance methods defined in Class, Module, Object, and BasicObject.

class A; end
class Module
  def hi; 'hi'; end
end
A.hi # => 'hi'

As 7stud mentioned on StackOverflow, “the lookup path of any method called on a class has to include Class somewhere because ALL classes inherit from Class”.

In any case, Ruby 2.1’s ancestors method is a major improvement because it gives accurate results when the receiver is a singleton class.

Ruby methods aren’t first-class, but procs are first-class

Ruby methods are not functions or first-class citizens because they cannot be passed to other methods as arguments, returned by other methods, or assigned to variables. Ruby procs are first-class, similar to JavaScript’s first-class functions.

Jorg Mittag says it well:

Ruby doesn’t have functions. It only has methods (which aren’t first-class) and Procs which are first-class, but are not associated with any object.

The following code demonstrates how Ruby methods cannot be stored in variables or returned from methods and therefore do not meet the ‘first-class’ criteria:

class Dog
  def speak
    'ruff'
  end
end

fido = Dog.new
# Ruby methods cannot be stored in variables
# Methods are executed and variables only store values
x = fido.speak
# x stores the method's return value, not the method itself
x # => 'ruff'

# Methods cannot return other methods
# Methods can only return values from other methods
def hi
  Dog.new.speak
end
# hi returns the method's return value, not the method itself
hi # => 'ruff'

Here is the Wikipedia definition of first-class functions:

In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. Specifically, this means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures.

The first-class function definition depends on the definition of first-class citizens:

In programming language design, a first-class citizen (also object, entity, or value) in a given programming language is an entity which supports all the operations generally available to other entities. These operations typically include being passed as a parameter, returned from a function, and assigned to a variable.

JavaScript is a language that has first-class functions that can be returned from other functions, assigned to variables, and stored in data structures.

function hi() {
  return('hello');
}

// functions can be assigned to a variable
var x = hi;
// x stores the actual function, not the return value of the function
console.log(x); // returns hi function
// variable can be used to invoke function
x(); // => 'hello'

// function can be returned by another function
function blah() { return hi; }
blah() // returns hi function

// functions can be stored in data structures
[hi, 3, 4, 'boo']

Ruby procs are objects that are like anonymous functions and are treated as first-class citizens.

# procs can be assigned to variables
multiplier = Proc.new {|x, y| x * y}

# procs can be returned from methods
def proc_returner(proc)
  proc
end
proc_returner(multiplier) # => multiplier proc

# procs can be stored in data structures
a = [multiplier]
a.first.call(3, 4) # => 12

Ruby’s Method Class

Ruby methods can be accessed as objects that are bound to a class. Methods aren’t technically objects in Ruby, but you can wrap them in objects. The distinction doesn’t matter for this blog post – we’ll simply investigate how use Ruby method objects that are easily accessible as instances of the Method class.

class A
  def hi
    'A#hi'
  end
end

method = A.new.method(:hi)
p method # => #<Method: A#hi>
p method.call # => 'A#hi'

Method objects can be compared with other method object, called, and unbound from an object.

class Cow
  def moo
    'A method'
  end
end

c = Cow.new
method = c.method(:moo)
method == c.method(:moo) # => true
method.call # => 'A method'
unbound = method.unbind # => #<UnboundMethod: Cow#moo>
unbound.call # => error because UnboundMethod objects cannot be called
unbound.bind(c) # rebind the unbound method to the c object

Ruby’s Binding Class (binding objects)

Instances of the Binding class (binding objects) capture the environment bindings (variables, methods, and self) at any point of a Ruby program (scope is also referred to as ‘environment’ or ‘context’), so the bindings can be reused later, when the scope has changed. The Kernel#binding() method creates binding objects and is often used in conjunction with the Kernel#eval() method.

class A
  def hi
    @a = 'a'
    b = 'b'
    binding
  end
end

binding = A.new.hi # returns a binding object
eval("b.concat('aaaaa')", binding) # => "baaaaa"
eval("self", binding) # => "baaaaa" # => #<A:0x007f87022c8ce8 @a="a">
eval("instance_variable_get('@a')", binding) # => "a"

In the A#hi method, the scope is captured in a binding object and re-access the scope in the eval() method, even though the scope of the program has changed when the eval() method is called. Ruby supports closures, which is a language features that allow scope to be captured and reused when the scope is changed. See this blog post (https://codequizzes.wordpress.com/2014/04/29/why-ruby-procs-are-closures/) for more about closures in Ruby.

Here’s a description of the Binding class from the wonderful book, Metaprogramming Ruby:

A Binding is a whole scope packaged as an object. The idea is that you can create a Binding to capture the local scope and carry it around. Later, you can execute code in that scope by using the Binding object in conjunction with eval( ), instance_eval( ), or class_eval( ). You can create a binding with the Kernel#binding() method.

The TOPLEVEL_BINDING object stores a reference to the top-level scope:

@blah = 'moo'
module M
  def self.hi
    eval("@blah", TOPLEVEL_BINDING)
  end
end

M::hi # => 'moo'

The @blah instance_variable is bound to the main object, which is also know as the top-level scope. The top-level scope can be accessed in the M.hi method with the TOPLEVEL_BINDING constant. Again, Ruby supports closures because scope can be captured and reaccessed, even when the scope has changed.

The Binding class also defines an eval() method that can be used on binding objects. This is semantically the same as passing a binding object to the Kernel#eval() method, but syntactically different:

class Cat
  def sad
    sound = 'meow'
    binding
  end
end

binding = Cat.new.sad
binding.eval("sound") # => 'meow'

# Kernel#eval() can be used instead of Binding#eval()
eval("sound", binding) # => 'meow'

Mimicking Ruby’s OpenStruct Class with method_missing()

Ruby’s OpenStruct class instantiates object with getter and setter methods that can be dynamically defined, so the object behaves like a hash This post shows how to use method_missing() to create a class that behaves similarly to the built-in OpenStruct class.

We’ll start by demonstrating the functionality of the built-in OpenStruct() class:

require 'ostruct'
phish = OpenStruct.new
phish.fluffhead # => nil
phish.fluffhead = 'was a man'
phish.fluffhead # => 'was a man'

OpenStruct objects return nil for attributes that are not defined. When new attributes are defined, they are accessible with a getter method.

Getter and setter methods are responsible for retrieving and setting instance variable values. method_missing() can be used in conjunction with instance_variable_get() and instance_variable_set() to create a class that behaves like OpenStruct.

class MyOpenStruct
  private
  def method_missing(name, *args)
    iv = "@#{name.to_s}"
    if name[-1] == '='
      instance_variable_set(iv.chop, args.first)
    else
      instance_variable_get(iv)
    end
  end
end

c = MyOpenStruct.new
c.bob = 'lob'
p c.bob # => 'lob'
p c.phil # => nil
c.phil = 'phhhhhil'
p c.phil # => 'phhhhhil'
p c.instance_variables # => [:@bob, :@phil]

This blog post was inspired by Metaprogramming Ruby, a must-read book for all Ruby programmers.