Cartwheel Letters

MC706.io
DailyProgrammer, Elm, Javascript, Python

One of my favorite channels in the phillydev slack channel is daily_programmer. Most days, someone posts a simple problem to that shouldn’t take too long to solve and people post their solutions in multiple languages. It is great to see how different languages look and how different people approach the same problem.

The problem

Today’s problem went something like this:

Check is a string us doing a letter cartwheel. Return true or false.

1
2
3
4
5
isLetterCartwheel('nun')
=> True

isLetterCartwheel('nunu')
=> False

This problem came from the meme: meme

Python Solution

Usually my gut reaction is to fall back on my python to solve this. Reasoning about the problem, “what is a letter cartwheel?”, I came up with the following requirements:

  • Must be more than 1 letter
  • Must have an odd number of letters
  • Must only have 2 characters repeated
  • The two characters must be one that is the upside-down of the other
  • The two characters must alternate.

So the first pass went something like this: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def isLetterCartwheel(string: str) -> bool:
    """
    Checks if a string is a letter chartwheel.
    
    >>> isLetterCartwheel('nun')
    True
    >>> isLetterCartwheel('nunu')
    False
    >>> isLetterCartwheel('nubun')
    False
    >>> isLetterCartwheel('bqbqb')
    True
    """
    mirrors = [frozenset(pair) for pair in ['nu', 'mw', 'oo', 'll', 'ss', 'xx', 'bq', 'dp', 'zz', 'yh', 'ae']]
    if not len(string) > 2 or len(string) % 2 == 0 or frozenset(string) not in mirrors:
        return False
    return len(set(string[::2])) == len(set(string[1::2])) == 1
        
if __name__ == "__main__":
    import doctest
    doctest.testmod()

So as a somewhat side note: for these kind of problems, I love doctest. For those of you who dont know doctest is a builtin library that allows you to write example use cases of a function being run inside of its docstring, and test that all of the expected outputs are correctly asserted. For problems like these, it allows me to follow a TDD pattern, where I can write a series of examples and expected outputs in the docs of the string, and write the code until the tests pass.

The elegance of this solution in python is hinged on frozenset. Frozensets in python are a less used data structure, but in certain cases, are very helpful. Here is how they fit as far as python data structures:

Mutable Immutable
Ordered list() tuple()
Unordered/Unique set() frozenset()

So they are basically a tuple with unique values and where order does not matter during comparison. This means that

1
frozenset('nu') == frozenset('un')

This means we can do comparisons in either direction quite easily. The other checks check if it is long enough, there an odd number of characters, and the last check verifies that all of the even and odd letter spaces are equal to each other.

After looking at this a bit, I managed to refactor to basically a one liner:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def isLetterCartwheel(string: str) -> bool:
    """
    Checks if a string is a letter chartwheel.
    
    >>> isLetterCartwheel('nun')
    True
    >>> isLetterCartwheel('nunu')
    False
    >>> isLetterCartwheel('nubun')
    False
    >>> isLetterCartwheel('bqbqb')
    True
    """
    return all([
        len(string) > 2,
        len(string) % 2 != 0,
        frozenset(string) in map(frozenset, ['nu', 'mw', 'o', 'l', 's', 'x', 'bq', 'dp', 'z', 'yh', 'ae']),
        len(set(string[::2])) == len(set(string[1::2])) == 1,
    ])

    
if __name__ == "__main__":
    import doctest
    doctest.testmod()

The improvements:

  • All conditions of a cartwheel letter are passed to an all
  • using map instead of a list comprehension allows for short-circuting
  • Don’t need double letters for things like "oo", because frozenset will remove the duplicate

I am pretty happy with this code snippet. It has the documentation and tests with the code, it has a very clear signal to noise ratio of what it is testing, it takes advantage of a nice python data structure, and elegantly returns a correct solution in one executable line.

Javascript Solution

I will break this into two solutions, the ES6 solution and the older pre-ES5 Javascript solution:

ES6

With ES6, we have a Set type, however unlike python’s set, all it enforces is uniqueness, not unorderedness which means: 

1
new Set('ab') != new Set('ba');

Unfortunately, it gets worse because: 

1
new Set('ab') != new Set('ab');

This means we need to write our own equivalence checker: 

1
2
3
4
5
6
const isEqual = (a, b) => {
    return [
        a.size === b.size,
        Array.from(a).every(i => b.has(i))
    ].every(x => x);
}

This gets us our frozenset equivalent, the length checks translate over nicely, and we can use reduce to do the odd, even checks:

1
var [odd, even] = Array.from(input).reduce((a,v,i) => {a[i%2].push(v); return a},[[],[]]);

This nice little reducer takes advantage that the callback function in javascript has a third optional input of currentIndex, in our case i. We start with an initial accumulator value of [[], []], an odd and even array. We then add to either the [0] or [1] position based on i%2, and push the current element to that array. We then use ES6 variable unpacking t get the odd and even letters.

Our final es6 script looks a bit like: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const identity = x => x;
const toSet = x => new Set(x);
const isEqual = (a, b) => a.size === b.size && Array.from(a).every(i => b.has(i));

const isLetterCartwheel = s => {
    let mirrors = ['nu', 'mw', 'o', 'l', 's', 'x', 'bq', 'dp', 'z', 'yh', 'ae'].map(toSet);
    let [odd, even] = Array.from(s).reduce((a,v,i) => {a[i%2].push(v); return a}, [[],[]]);
    return [
        s.length > 1,
        s.length % 2 !== 0,
        mirrors.some(x => isEqual(new Set(s), x)),
        (new Set(odd).length === new Set(even).length)     
    ].every(identity)
}

Pre-ES5 / Classic Javascript.

To take out some of the magic that ES6 gives you, and doing this in old school classic javascript, it takes a little bit more:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function isLetterCartwheel (string) {
    var mirrors = ['nu', 'mw', 'o', 'l', 's', 'x', 'bq', 'dp', 'z', 'hy', 'ae'],
        letters = [],
        evens = [],
        odds = [],
        i;
    if (string.length < 3 || string.length % 2 === 0) {
        return false;
    }
    for (i = 0; i < string.length; i++) {
        var letter = string[i];
        if (letters.indexOf(letter) === -1) {
            letters.push(letter);
        }
        if (i % 2 === 0) {
            if (evens.indexOf(letter) === -1) {
                evens.push(letter);    
            }
        } else {
            if (odds.indexOf(letter) === -1) {
                odds.push(letter);    
            }
        }
    }
    if (odds.length !== evens.length || letters.length > 2) {
        return false;
    }
    return mirrors.indexOf(letters.join('')) !== mirrors.indexOf(letters.reverse().join(''));
}

Here is a simple check that uses no magic, takes 1 pass a the string when it needs to, and does a simple compare at the end. While not as clean or elegant as the ES6 solution, it does give some insight on how to thought process is working.

Elm Solution

And lastly, for shits and giggles, I am going to try my hand at an Elm solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import Set


strToCharSet : String -> Set Char
strToCharSet string = 
    string 
        |> String.toList 
        |> Set.fromList

mirrors : List (Set Char)
mirrors = 
    [ "nu"
    , "mw"
    , "o"
    , "l"
    , "s"
    , "x"
    , "bq"
    , "dp"
    , "z"
    , "yh"
    , "ae"
    ]
        |> List.map strToCharSet

isEven : Int -> Bool
isEven i =
    i % 2 == 0

evensAndOddsAlign : String -> Bool
evensAndOddsAlign string = 
    let 
        (evens,odds) = 
            string
                |> String.toList
                |> List.indexedMap (,)
                |> List.partition (\i -> isEven (Tuple.first i))
        evenList = 
            List.map Tuple.second evens
        oddList = 
            List.map Tuple.second odds
    in
        Set.size (Set.fromList evenList) == Set.size (Set.fromList oddList)
        

isLetterCartwheel : String -> Bool
isLetterCartwheel string =
    [ String.length string > 2
    , String.length string % 2 /= 0
    , List.member (strToCharSet string) mirrors
    ]
        |> List.all (\i -> i)

Working in Elm and being purely functional is nice and has its benefits, but makes certain other things like splitting lists by their evens and odd numbers harder.