ABC problem
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 set of blocks. The rules are simple:
- Once a letter on a block is used that block cannot be used again
- The function should be case-insensitive
- Show your output on this page for the following words:
- Example
<lang python>
>>> can_make_word("") False >>> 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
</lang>
D
<lang d>import std.stdio, std.typecons, std.array, std.algorithm, std.string;
bool abc(in string word, string[] blocks) pure /*nothrow*/ {
static Tuple!(bool, string[]) inner(in string w, string[] blocks) pure /*nothrow*/ { foreach (immutable i, immutable ch; w) { const whatsLeft = w[i + 1 .. $]; foreach (blk; blocks.filter!(b => b.canFind(ch))) { auto bLeft = blocks.dup; bLeft = bLeft.remove(bLeft.countUntil(blk)); if (whatsLeft.empty) return tuple(true, bLeft); if (bLeft.empty) return tuple(false, bLeft); auto ans_blocksLeft = inner(whatsLeft, bLeft); if (ans_blocksLeft[0]) return ans_blocksLeft; } break; } return tuple(false, blocks); }
return inner(word.toUpper, blocks)[0];
}
void main() {
auto blocks = "BO XK DQ CP NA GT RE TG QD FS JW HU VI AN OB ER FS LY PC ZM".split;
foreach (word; "" ~ "A BARK BoOK TrEAT COmMoN SQUAD conFUsE".split) writefln(`"%s" %s`, word, abc(word, blocks));
}</lang>
- Output:
"" false "A" true "BARK" true "BoOK" false "TrEAT" true "COmMoN" false "SQUAD" true "conFUsE" true
J
Solution: <lang j>can_make_word=: #/.~@] *./@:<: #/.~@[ {~ i.&(tolower@~.)</lang>
Examples <lang j>Blocks=: , ];._2 noun define BO XK DQ CP NA GT RE TG QD FS JW HU VI AN OB ER FS LY PC ZM )
ExampleWords=: a: , ;:'A BARK BOOK TREAT COMMON SQUAD'
Blocks&can_make_word &> ExampleWords
1 1 1 1 1 0 1</lang>
Python
<lang python>BLOCKS = 'BO XK DQ CP NA GT RE TG QD FS JW HU VI AN OB ER FS LY PC ZM'.split()
def _abc(word, blocks):
for i, ch in enumerate(word): for blk in (b for b in blocks if ch in b): whatsleft = word[i + 1:] blksleft = blocks[:] blksleft.remove(blk) if not whatsleft: return True, blksleft if not blksleft: return False, blksleft ans, blksleft = _abc(whatsleft, blksleft) if ans: return ans, blksleft else: break return False, blocks
def abc(word, blocks=BLOCKS):
return _abc(word.upper(), blocks)[0]
if __name__ == '__main__':
for word in [] + 'A BARK BoOK TrEAT COmMoN SQUAD conFUsE'.split(): print('Can we spell %9r? %r' % (word, abc(word)))</lang>
- Output:
Can we spell ''? False Can we spell 'A'? True Can we spell 'BARK'? True Can we spell 'BoOK'? False Can we spell 'TrEAT'? True Can we spell 'COmMoN'? False Can we spell 'SQUAD'? True Can we spell 'conFUsE'? True
REXX
<lang rexx>/*REXX program tests if a word(s) can be spelt from a pool of toy blocks*/ blocks = 'BO XK DQ CP NA GT RE TG QD FS JW HU VI AN OB ER FS LY PC ZM' list = 'A baRk bOOk trEat coMMon squaD conFuse' /*can be in any case. */
do k=0 to words(list) /*traipse through list. */ if k==0 then call can_make_word /*perform a NULL test.*/ else call can_make_word word(list,k) /*a vanilla test.*/ end /*k*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────CAN_MAKE_WORD subroutine────────────*/ can_make_word: procedure expose blocks; arg x . /*X: word to be built. */ z=' ' blocks " "; upper z /*pad pool, uppercase it*/ try=0; OK=0; L=length(x) /*set some REXX vars. */
do n=1 for L; y=substr(x,max(1,n),1) /*find particular letter*/ if try//2 then p= pos(y,z) /*try to find letter by */ else p=lastpos(y,z) /*one method or another.*/
if p==0 then do; try=try+1 /*Not found? Try again.*/ n=n-2; iterate /*back up (to previous).*/ end if pos(' 'y,z)\==0 then q=' 'y /*try to locate Y≈ */ else q=y' ' /* " " ≈Y */ parse var z a (q) b /*split it up into two. */ z=a b do k=1 for words(z); _=word(z,k) /*scrub the block pool. */ if length(_)==1 then z=delword(z,k,1) /*is block 1 char?*/ end /*k*/ /* [↑] elide any 1char.*/ OK= n==L /*a flag: built or not.*/ end /*n*/
if x== then x="(null)" /*express a NULL better.*/
say right(x,20) right(word("can't can",OK+1),6) 'be spelt.'
return OK /*also, return flag. */</lang>
output
[Spelling note: spelt is an alternate version of spelled.]
(null) can't be spelt. A can be spelt. BARK can be spelt. BOOK can't be spelt. TREAT can be spelt. COMMON can't be spelt. SQUAD can be spelt. CONFUSE can be spelt.