fbpx

C++: ABC Problem

Bjarne-stroustrup
 

You are given a collection of ABC blocks. Just like the ones you had when you were a kid. There are twenty blocks with two letters on each block. You are guaranteed to have a complete alphabet amongst all sides of the blocks. The sample blocks are:

((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))

The goal of this task is to write a function that takes a string and can determine whether you can spell the word with the given collection of blocks. The rules are simple:

  1. Once a letter on a block is used that block cannot be used again
  2. The function should be case-insensitive
  3. Show your output on this page for the following words:
Example
 
    >>> 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

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <cctype>


typedef std::pair<char,char> item_t;
typedef std::vector<item_t> list_t;

bool can_make_word(const std::string& w, const list_t& vals) {
	std::set<uint32_t> used;
	while (used.size() < w.size()) {
		const char c = toupper(w[used.size()]);
		uint32_t x = used.size();
		for (uint32_t i = 0, ii = vals.size(); i < ii; ++i) {
			if (used.find(i) == used.end()) {
				if (toupper(vals[i].first) == c || toupper(vals[i].second) == c) {
					used.insert(i);
					break;
				}
			}
		}
		if (x == used.size()) break;
	}
	return used.size() == w.size();
}


int main() {
	list_t vals{ {'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'} };
	std::vector<std::string> words{"A","BARK","BOOK","TREAT","COMMON","SQUAD","CONFUSE"};
	for (const std::string& w : words) {
		std::cout << w << ": " << std::boolalpha << can_make_word(w,vals) << ".\n";
	}

}

 

Output:
A: true.
BARK: true.
BOOK: false.
TREAT: true.
COMMON: false.
SQUAD: true.
CONFUSE: true.

SOURCE

Content is available under GNU Free Documentation License 1.2.