Avatar of exklamationmark

exklamationmark's solution

to Robot Name in the Go Track

Published at Aug 24 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This exercise has changed since this solution 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.

Bonus exercise

Once you get go test passing, try go test -tags bonus. This uses a build tag to enable a test that wasn't previously enabled. Build tags control which files should be included in the package. You can read more about those at the Go documentation.

For this exercise it limits go test to only build the tests in the robot_name_test.go file. We can then include the bonus test in the bonus_test.go file with the tags flag as described above.

To get the bonus test to pass you'll have to ensure a robot's name has not been used before.

Running the tests

To run the tests run the command go test from within the exercise directory.

If the test suite contains benchmarks, you can run these with the --bench and --benchmem flags:

go test -v --bench . --benchmem

Keep in mind that each reviewer will run benchmarks on a different machine, with different specs, so the results from these benchmark tests may vary.

Further information

For more detailed information about the Go track, including how to get help if you're having trouble, please visit the exercism.io Go language page.

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.

bonus_test.go

// +build bonus

package robotname

import "testing"

func TestCollisions(t *testing.T) {
	m := map[string]bool{}
	// Test uniqueness for new robots.
	// 10k should be plenty to catch names generated
	// randomly without a uniqueness check.
	for i := 0; i < 10000; i++ {
		n := New().Name()
		if m[n] {
			t.Fatalf("Name %s reissued after %d robots.", n, i)
		}
		m[n] = true
	}
	// Test that names aren't recycled either.
	r := New()
	for i := 0; i < 10000; i++ {
		r.Reset()
		n := r.Name()
		if m[n] {
			t.Fatalf("Name %s reissued after Reset.", n)
		}
		m[n] = true
	}
}

robot_name_test.go

package robotname

import (
	"regexp"
	"testing"
)

var namePat = regexp.MustCompile(`^[A-Z]{2}\d{3}$`)

func New() *Robot { return new(Robot) }

func TestNameValid(t *testing.T) {
	n := New().Name()
	if !namePat.MatchString(n) {
		t.Errorf(`Invalid robot name %q, want form "AA###".`, n)
	}
}

func TestNameSticks(t *testing.T) {
	r := New()
	n1 := r.Name()
	n2 := r.Name()
	if n2 != n1 {
		t.Errorf(`Robot name changed.  Now %s, was %s.`, n2, n1)
	}
}

func TestSuccessiveRobotsHaveDifferentNames(t *testing.T) {
	n1 := New().Name()
	if New().Name() == n1 {
		t.Errorf(`Robots with same name.  Two %s's.`, n1)
	}
}

func TestResetName(t *testing.T) {
	r := New()
	n1 := r.Name()
	r.Reset()
	if r.Name() == n1 {
		t.Errorf(`Robot name not cleared on reset.  Still %s.`, n1)
	}
}

// Note if you go for bonus points, this benchmark likely won't be
// meaningful.  Bonus thought exercise, why won't it be meaningful?
func BenchmarkName(b *testing.B) {
	// Benchmark combined time to create robot and name.
	for i := 0; i < b.N; i++ {
		New().Name()
	}
}
// Package robotname help create robots with names.
//
// Here, we assumes that the questions wants all issued name (with/without reset) to be unique.
// That means, if there is only one robot, and it got reset 676e3 times, all issued names must be unique.
package robotname

import (
	"fmt"
	"math/rand"
)

const (
	// up to 26 * 26 * 10 * 10 * 10 - 1 unique names.
	// 0 is reserved, since all new robot will have serial == 0.
	maxNames int = 676e3 - 1
)

var (
	// stored contains used serials. At most it uses ~= 676e3 * 4 bytes ~= 2.5MB
	stored map[int]struct{}
)

func init() {
	rand.Seed(0) // any seed will do
	loadUsedSerials(&stored)
}

// loadUsedSerials populates the list of used serials.
// IRL, this comes from a persistent storage (HDD, database, etc) & work across restarts.
// Here, we can assumes the main program don't die :)
func loadUsedSerials(store *map[int]struct{}) {
	(*store) = make(map[int]struct{}, maxNames)
	(*store)[0] = struct{}{}
}

// Robot represents a manufactured robot with a name.
// NOTE: using Name() and Reset() is not thread-safe.
type Robot struct {
	serial int // in [1, 676e3), maps to a name
}

// newUnusedSerial returns a new, unused serial that we can create a name from.
// If there is no more serial to assign, it returns an error.
func newUnusedSerial() (int, error) {
	if len(stored) == maxNames {
		return 0, fmt.Errorf("all %d serials have been used", maxNames)
	}

	sr := rand.Intn(maxNames)
	for {
		if _, used := stored[sr]; !used {
			stored[sr] = struct{}{}
			return sr, nil
		}
		sr = rand.Intn(maxNames)
	}
}

// Reset sets the serial back to the zero-value (0).
func (r *Robot) Reset() {
	r.serial = 0
}

// Name either sets the Robot's name on first run/after reset, or returns the robot's current name.
func (r *Robot) Name() string {
	// TODO(): it would be nicer if we can do this in New()
	if r.serial == 0 { // not issued
		unused, err := newUnusedSerial()
		if err != nil {
			panic(err.Error()) // TODO(): the spec should have handled this
		}

		r.serial = unused
	}

	return decodeSerial(r.serial)
}

// decodeSerial return the string mapped to this serial.
// Similar to how we convert hex -> decimal, we first split the serial into:
// serial = ch1 * 767e3 + ch2 * 26e3 + dg1 * 1e3 + dg2 * 1e2 + dg3
//
// The name is <ch1 + 'A'><ch2 + 'A'><dg1 + '0'><dg2 + '0'><<dg3 + '0'>.
func decodeSerial(sr int) string {
	// decode the serial
	dg3 := sr % 10
	sr /= 10
	dg2 := sr % 10
	sr /= 10
	dg1 := sr % 10
	sr /= 10
	ch2 := sr % 26
	sr /= 26
	ch1 := sr % 26

	return string([]byte{
		byte(ch1 + 'A'),
		byte(ch2 + 'A'),
		byte(dg1 + '0'),
		byte(dg2 + '0'),
		byte(dg3 + '0'),
	})
}

Community comments

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

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?