ABC Problem

This is a Rosetta Code post.

Story

You are given a collection of ABC blocks (maybe like the ones you had when you were a kid).

There are twenty blocks with two letters on each block.

A complete alphabet is guaranteed amongst all sides of the blocks.

The sample collection of blocks:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(B O)
(X K)
(D Q)
(C P)
(N A)
(G T)
(R E)
(T G)
(Q D)
(F S)
(J W)
(H U)
(V I)
(A N)
(O B)
(E R)
(F S)
(L Y)
(P C)
(Z M)

Task

Write a function that takes a string (word) and determines whether the word can be spelled with the given collection of blocks.

The rules are simple:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> can_make_word("A")
True
>>> can_make_word("BARK")
True
>>> can_make_word("BOOK")
False
>>> can_make_word("TREAT")
True
>>> can_make_word("COMMON")
False
>>> can_make_word("SQUAD")
True
>>> can_make_word("CONFUSE")
True

The word BARK was made up using blocks as follows:

BARK

Solutions

For the possible solutions blow, each time I ran the console application I got a different result in terms of elapsed time. I guess an average of a few runs would be the best to have an unbiased result but the below paints a pretty clear picture (for me anyway) that the action deligate is the fastest.

1
2
3
4
5
6
7
8
9
10
11
ForeachLoop:    00:00:00.0056731
ActionDelegate: 00:00:00.0015526  < fastest run and solution
Regex:          00:00:00.0122734

ForeachLoop:    00:00:00.0077697
ActionDelegate: 00:00:00.0016330
Regex:          00:00:00.0170153

ForeachLoop:    00:00:00.0080737
ActionDelegate: 00:00:00.0015944
Regex:          00:00:00.0170100

foreach

Using a normal foreach loop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public bool MakeWord(string word, List<string> blocks) 
{
    var blocksLeft = new List<string>(blocks);
    var stringComparison = StringComparison.CurrentCultureIgnoreCase;

    foreach (var letter in word)
    {
        if (!blocksLeft.Any(b => b.Contains(letter, stringComparison)))
            return false;

        blocksLeft.Remove(blocksLeft.First(b => b.Contains(letter, stringComparison)));
    }

    return true;
}

action

Trying to make things faster with an Action

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public bool MakeWord2(string word, List<string> blocks)
{
    var letters = word.ToList();
    var blocksLeft = new List<string>(blocks);
    var stringComparison = StringComparison.CurrentCultureIgnoreCase;

    letters.ForEach(letter => {

        if (!blocksLeft.Any(b => b.Contains(letter, stringComparison)))
            return;

        blocksLeft.Remove(blocksLeft.First(b => b.Contains(letter, stringComparison)));

    });

    return blocksLeft.Count() + letters.Count() == blocks.Count();
}

regex

Implementation from http://rosettacode.org/wiki/ABC_Problem#Regex

1
2
3
4
5
6
7
8
9
10
11
public bool MakeWord3(string word, string blocks)
{
    for (int i = 0; i < word.Length; ++i)
    {
        int length = blocks.Length;
        var rgx = new Regex("([a-z]" + word[i] + "|" + word[i] + "[a-z])", RegexOptions.IgnoreCase);
        blocks = rgx.Replace(blocks, "", 1);
        if (blocks.Length == length) return false;
    }
    return true;
}

References