Wordament Solver

 

Many many years back in an interview I was asked to design a solver for the game Wordament. At that time I had no idea what the game was and the interviewer patiently explained it to me. I later learnt that couple of engineers in Microsoft came up with the game for the Windows phone platform and it was such a success that they went and bootstrapped a team and made that game their full time job. 

I was able to give a solution in the interview, but that always remained at the back of my mind. I wanted to go further than the theoretical solution and  really build the solver. I began tinkering with the idea a couple of weeks back and over the Thanksgiving long weekend I got enough time to sit down and complete the solution.

The sources are at github.com/abhinababasu/wordament/

You can see it in action at bonggeek.com/wordament/

Basic Idea

We begin by loading dictionary into a Trie data-structure.  Obviously there are fantastic Trie implementation out there, including ones that are highly optimized in memory by being able to collapse multiple nodes into one, however, the whole idea of this exercise was to write some code. So I rolled out a basic Trie.

If a particular Trie node is a end of word, then that node is marked as so. As an example a Trie created with the words, cat, car, men, man, mad will look as below. The green checks denote these are valid end of word nodes.

Now starting from each cell of Wordament, we start at the node for that cell character in the Trie. We look at the 8 adjacent cells (neighbors) and if there are Trie children with the same character as the neighbor, then it is a candidate to look into. And we recursively move to that node. At any point if we arrive at a valid word node, then we check to see if that word was previously found, if not, we add the word and the list of cells that created that word in the result.

Finally since Wordament gives higher score for longer words, we sort the list of words by their length.

The logic of this solution is implemented in wordament.go.

I built the solver into a web-service, that runs in a docker container inside Azure VM. The service exposes an API. Then I built a single page web-application, that calls this web-service and renders the solution.

You can hit the API directly with something like

curl -s commonvm1.westus2.cloudapp.azure.com:8090/?input=SPAVURNYGERSMSBE | jq .

The input is all the 16 characters of the Wordament to be solved.

CAYL - Code as you like day

Building an enterprise grade distributed service is like trying to fix and improve a car while driving it at high speed down the free-way. Engineering debt accumulates fast and engineers in the team yearn for the time to get to them. A common complaint is also that we need more time to tinker with cool features and tech to learn and experiment.

An approach many companies take is the big hackathon events. Even though they have their place, I think those are mostly for PR and getting eye candy. Which exec doesn’t want to show the world their company creates AI powered blockchain running on quantum computer in just a 3 day hackathon.

This is where CAYL comes in. CAYL or “Code As You Like” is named loosely on “go as you like” event I experienced as a student in India. In a lot of uniform based schools in Kolkata, it is common to have a go as you like day, where kids dress up however they want.

Even though we call it code as you like, it has evolved beyond coding. One of our extended Program Management team has also picked this up and call it the WAYL (Work as you like day). This is what we have set aside in our group calendar for this event.

“code as you like day” is a reserved date every month (first Monday of the month) where we get to code/document or learn something on our own.
There will be no scheduled work items and no standups.
We simply do stuff we want to do. Examples include but not limited to

1. Solve a pet peeve (e.g. fix a bug that is not scheduled but you really want to get done)
2. A cool feature
3. Learn something related to the project that you always wanted to figure out (how do we use fluentd to process events, what is helm)
4. Learn something technical (how does go channels work, go assembly code)
5. Shadow someone from a sibling team and learn what they are working on

We can stay late and get things done (you totally do not have to do that) and there will be pizza or ice-cream.

One requirement is that you *have* to present the next day, whatever you did.  5 minutes each

I would say we have had great success with it. We have had CAYL projects all over the spectrum

1. Speed up build system and just make building easier
2. ML Vision device that can tell you which bin trash needs to go in (e.g. if it is compostable)
3. Better BVT system and cross porting it to work on our Macs
4. Pet peeves like make function naming more uniform, remove TODO from code, spelling/grammar  etc.
5. Better logging and error handling
6. Fix SQL resiliency issues
7. Move some of our older custom management VMs move to AKS
8. Bring in gomock, go vet, static checking
9. 3D game where mommy penguin gets fish for her babies and learns to be optimal using machine learning
10. Experiment with Prometheus
11. A dev spent a day shadowing dev from another team to learn the cool tech they are using etc.

We just finished our CAYL yesterday and one of my CAYL items was to write a blog about it. So it’s fitting that I am hitting publish on this blog, as I sit in the CAYL presentation while eating Kale chips

Go Generics

Every month in our team we do a Code as You Like Day, which is basically a day of taking time off regular work and hacking something up, learning something new or even fixing some pet-peeves in the system. This month I chose to learn about go-lang generics.

I started go many years back while coming from mainly coding in C++ and C#. Also in Adobe almost 20 years back I got a week long class on generic programming from Alexander Stepanov himself. I missed generics terribly and hated all the code I had hand role out for custom container types. So I was looking forward to generics in go.

This was also the first time I was trying to use a non-stable version of go as generics is available currently as go 1.18 Beta 2. Installing this was a bit confusing for me.

I just attempted go install which seemed to work

but seemed like it did not work. I had to do an additional step of download. That wasn't very intuitive.

For my quick test, I decided to do a port my quick and dirty stack implementation from relying on interface{} to use generic type.

I created a Stack with generic type T which is implemented over a slice of T.

var Full = errors.New("Full")

var Empty = errors.New("Empty")

type Stack[T any] struct {

    arr  []T

    curr int

    max  int

}

Creating two functions to create a fixed size stack or growable was a breeze. Using the generic types was intuitive.

func NewSizedStack[T any] (size int) *Stack[T] {

    s := &Stack[T]{max: size}

    s.arr = make([]T, size)

    return s

}

func NewStack[T any]() *Stack[T] {

    return &Stack[T]{

        max: math.MaxInt32,

    }

}

However, I did fumble on creating the methods on that type. Because I somehow felt I need to write it as func (s *Stack[T])Length[T any]() int {}. However, the [T any] is actually not required.

func (s *Stack[T]) Length() int {

    return s.curr

}

func (s *Stack[T]) IsEmpty() bool {

    return s.Length() == 0

}

Push and Pop worked out as well

func (s *Stack[T]) Push(v T) error {

    if s.curr == len(s.arr) {

        if s.curr == s.max {

            return Full

        } else {

            s.arr = append(s.arr, v)

        }

    } else {

        s.arr[s.curr] = v

    }

    s.curr++

    return nil

}

func (s *Stack[T]) Pop() (T, error) {

    var noop T // 0 value

    if s.Length() == 0 {

        return noop, Empty

    }

    v := s.arr[s.curr-1]

    s.arr[s.curr-1] = noop // release the reference

    s.curr--

    return v, nil

}

However, for pop I needed to return a nil/0-value for the generic type. It did seem odd that go does not implement something specific for it. I had to create a variable as noop and they return that.

Using the generic type is a breeze too, no more type casting!

s := NewStack[int]()

s.Push(5)

if v, e := s.Pop(); e != nil {

    t.Errorf("Should get poped value")

}