davearonson's solution to Robot Name on the Ruby track

Instructions

Test suite

Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

Manage robot factory settings.

When robots come off the factory floor, they have no name.

The first time you boot them up, a random name is generated in the format of two uppercase letters followed by three digits, such as RX837 or BC811.

Every once in a while we need to reset a robot to its factory settings, which means that their name gets wiped. The next time you ask, it will respond with a new random name.

The names must be random: they should not follow a predictable sequence. Random names means a risk of collisions. Your solution must ensure that every existing robot has a unique name.

In order to make this easier to test, your solution will need to implement a Robot.forget method that clears any shared state that might exist to track duplicate robot names.

Bonus points if this method does not need to do anything for your solution.

For installation and learning resources, refer to the exercism help page.

For running the tests provided, you will need the Minitest gem. Open a terminal window and run the following command to install minitest:

gem install minitest

If you would like color output, you can require 'minitest/pride' in the test file, or note the alternative instruction, below, for running the test file.

Run the tests from the exercise directory using the following command:

ruby robot_name_test.rb

To include color from the command line:

ruby -r minitest/pride robot_name_test.rb

Source

A debugging session with Paul Blackwell at gSchool. http://gschool.it

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

robot_name_test.rb

require 'minitest/autorun'
require_relative 'robot_name'

class RobotTest < Minitest::Test
  NAME_REGEXP = /^[A-Z]{2}\d{3}$/

  def setup
    Robot.forget
  end

  def test_can_create_a_robot
    skip
    refute_nil Robot.new
  end

  def test_has_name
    skip
    assert_match NAME_REGEXP, Robot.new.name
  end

  def test_name_sticks
    skip
    robot = Robot.new
    original_name = robot.name
    assert_equal original_name, robot.name
  end

  def test_reset_changes_name
    skip
    robot = Robot.new
    original_name = robot.name
    robot.reset
    refute_equal original_name, robot.name
  end

  def test_reset_before_name_called_does_not_cause_an_error
    skip
    robot = Robot.new
    robot.reset
    assert_match NAME_REGEXP, Robot.new.name
  end

  def test_reset_multiple_times
    skip
    robot = Robot.new
    names = []
    5.times do
      robot.reset
      names << robot.name
    end
    # This will probably be 5, but name uniqueness is only a requirement
    # accross multiple robots and consecutive calls to reset.
    assert names.uniq.size > 1
  end

  def test_different_robots_have_different_names
    skip
    refute_equal Robot.new.name, Robot.new.name
  end

  # This test assumes you're using Kernel.rand as a source of randomness
  def test_different_name_when_chosen_name_is_taken
    skip
    same_seed = 1234
    Kernel.srand same_seed
    robot_1 = Robot.new
    name_1  = robot_1.name
    Kernel.srand same_seed
    robot_2 = Robot.new
    name_2 = robot_2.name
    refute_equal name_1, name_2
  end

  def test_generate_all_robots
    skip
    all_names_count = 26 * 26 * 1000
    time_limit = Time.now + 60 # seconds
    seen_names = Hash.new(0)
    robots = []
    while seen_names.size < all_names_count && Time.now < time_limit
      robot = Robot.new
      seen_names[robot.name] += 1
      robots << robot
    end
    timeout_message = "Timed out trying to generate all possible robots"
    assert_equal all_names_count, robots.size, timeout_message
    assert seen_names.values.all? { |count| count == 1 }, "Some names used more than once"
    assert seen_names.keys.all? { |name| name.match(NAME_REGEXP) }, "Not all names match #{NAME_REGEXP}"
  end

  def test_version
    assert_equal 3, BookKeeping::VERSION
  end
end

class RandomNameGeneratorWithDupChars
  def self.call
    (2.times.map { ('A'..'Z').to_a.sample } +
     3.times.map { ('0'..'9').to_a.sample }).join
  end
end


class RandomNameGeneratorWithoutDupChars
  def self.call
    (("A".."Z").to_a.sample(2) + ("0".."9").to_a.sample(3)).join
  end
end


# could have others generators, like constant, incremental, etc.; each
# may be a class or other object, just so long as it has a .call method.


class RobotNameUniquenessError < RuntimeError
end


class RobotNameManager

  require 'set'

  attr_reader :max_tries
  attr_reader :name_generator
  attr_reader :names_used

  def initialize(options={})
    parse_options(options)
    @names_used = Set.new
  end

  def generate_unique_name
    tries = 0
    begin
      name = name_generator.call
      tries += 1
    end while names_used.include?(name) && tries < max_tries
    check_name_uniqueness(name)
    names_used << name
    name
  end

  def release_name(name)
    names_used.delete name
    # not worrying about whether it was indeed UNavailable before....
  end

  private

  def check_name_uniqueness(name)
    if names_used.include? name
      raise(RobotNameUniquenessError,
            "ERROR: Could not make unique robot name in #{max_tries} tries!")
    end
  end

  def parse_options(options)
    @name_generator = (options[:name_generator] ||
                       RandomNameGeneratorWithDupChars)
    @max_tries = (options[:max_tries] || 100)
  end

end


class Robot

  attr_reader :name
  attr_reader :name_manager

  def initialize(options={})
    parse_options(options)
    set_to_factory_defaults
  end

  # needed mainly to test name recycling -- just going out of scope does not
  # guarantee gc will collect it (and therefore call its finalizer if any)
  def remove_from_service
    release_name
  end

  def reset
    set_to_factory_defaults
  end

  private

  def self.default_name_manager
    # memoize it so each robot w/ unspecified name mgr gets the same one,
    # not just any old name manager with the default name generator.
    @_default_name_manager ||= RobotNameManager.new
  end

  def parse_options(options)
    @name_manager = (options[:name_manager] || self.class.default_name_manager)
  end

  def release_name
    name_manager.release_name(name) if name
  end

  def set_to_factory_defaults
    release_name
    @name = @name_manager.generate_unique_name
    # any additional future [re-]settings can go here
  end

end

Community comments

Find this solution interesting? Ask the author a question to learn more.

davearonson

Solution Author

commented almost 5 years ago

Gave up on the finalizer approach to determining when a robot's name should be removed from service, since just going out of scope does not guarantee that an object will be GC'ed. Now I'm using an explicit remove_from_service method. See the prior iteration, which is the updated test suite.

remcopeereboom

commented almost 5 years ago

I was inspired by your ideas, so I tried some tangents. I went quite far of, going so far as to create an Identfier (Name) object so that robot wouldn't need to know about name_managers. You just pass in a factory and the factory wires up the name to make sure that it is always unique. No more calling release_name in Robot, just fire and forget. This did introduce yet two more classes, but the actual length of code is about the same, so I guess it was an okay trade-off. I am still not sure that I'm happy with it. It feels like a Türing tarpit. All those options and flexibility. I'd feel more confident with the entire code base to look at...

I copied your RobotNameManger code verbatim, but then refactored it, so I thought you might want to compare: class IdentifierPool def initialize(options={}) @generator = options[:generator] || RandomNameGeneratorWithDupChars @max_tries = options[:max_tries] || 100 @ids = Set.new end

def take id = generate_unique_identifier or failed_to_generate_name @ids << id id end

def release(id) @ids.delete id end

private

def generate_unique_identifier @max_tries.times do id = @generator.call return id unless @ids.include?(id) end end

def failed_to_generate_name fail IdentifierUniquenessError, "ERROR: Failed to make unique identifier in #{@max_tries} tries!" end end

I renamed some stuff. Everything is now identifier, but that's just because I prefer it over name. I did remove the name_ prefix, since generator seems like a fair enough option argument. The context makes it clear what kind of generator we need I think.

I removed all the attributes (I could have made them private), because I don't think clients should want to query this. In your own code none of the code is interested in it and I think that's a good sign.

I inlined the options, since it's only two and unlikely to grow. It removes a bit of clutter I think.

I separated generating a unique name from adding it to the pool, although you might feel that they logically belong together. I'm undecided.

I know it's not technically a pool, but I feel that this more clearly indicates to clients (in my case the new Identifier class, in your case Robot) that they are responsible for calling release

I moved the require 'Set' statement to outside the class.

I copied your RobotNameManger code verbatim, but then refactored it, so I thought you might want to compare:
class IdentifierPool
  def initialize(options={})
    @generator = options[:generator] || RandomNameGeneratorWithDupChars
    @max_tries = options[:max_tries] || 100
    @ids = Set.new
  end

def take
    id = generate_unique_identifier or failed_to_generate_name
    @ids &lt;&lt; id
    id
  end

def release(id)
    @ids.delete id
  end

private

def generate_unique_identifier
    @max_tries.times do
      id = @generator.call
      return id unless @ids.include?(id)
    end
  end

def failed_to_generate_name
    fail IdentifierUniquenessError,
         "ERROR: Failed to make unique identifier in #{@max_tries} tries!"
  end
end

I inlined the options, since it's only two and unlikely to grow. It removes a bit of clutter I think.

I separated generating a unique name from adding it to the pool, although you might feel that they logically belong together. I'm undecided.

I know it's not technically a pool, but I feel that this more clearly indicates to clients (in my case the new Identifier class, in your case Robot) that they are responsible for calling release

I moved the require 'Set' statement to outside the class.

Cancel

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

What compromises have been made?
Are there new concepts here that you could read more about to improve your understanding?

davearonson's solution

to Robot Name in the Ruby Track