Rosetta Code

ABC problem

Revision as of 12:31, 9 January 2014 by rosettacode>Bearophile (Modified the task description tests: can_make_word is now True for empty input word because you can compose it using zero blocks.)

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:

Task
ABC problem
You are encouraged to solve this task according to the task description, using any language you may know.
((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:

  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

<lang python> 

   >>> can_make_word("")
   True
   >>> 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

Translation of: Python

A simple greedy algorithm is enough for the given sequence of blocks. canMakeWord is true on an empty word because you can compose it using zero blocks. <lang d>import std.stdio, std.algorithm, std.string;

bool canMakeWord(in string word, in string[] blocks) pure /*nothrow*/ { 

   auto bs = blocks.dup;
   outer: foreach (immutable ch; word.toUpper) {
       foreach (immutable block; bs)
           if (block.canFind(ch)) {
               bs = bs.remove(bs.countUntil(block));
               continue outer;
           }
       return false;
   }
   return true;

}

void main() { 

   /*immutable*/
   const 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, canMakeWord(word, blocks));

}</lang>

Output:
"" true
"A" true
"BARK" true
"BoOK" false
"TrEAT" true
"COmMoN" false
"SQUAD" true
"conFUsE" true

J

Solution: <lang j>reduce=: verb define 

 'rows cols'=. i.&.> $y
 for_c. cols do.
   r=. 1 i.~ c {"1 y             NB. row idx of first 1 in col
   if. r = #rows do. continue. end.
   y=. 0 (<((r+1)}.rows);c) } y  NB. zero rest of col
   y=. 0 (<(r;(c+1)}.cols)) } y  NB. zero rest of row
 end.

)

abc=: *./@(+./)@reduce@(e."1~ ,)&toupper :: 0:</lang> Examples: <lang j> Blocks=: ];._2 'BO XK DQ CP NA GT RE TG QD FS JW HU VI AN OB ER FS LY PC ZM ' 

  ExampleWords=: <;._2 ' A BaRK BOoK tREaT COmMOn SqUAD CoNfuSE '

  Blocks&abc &> ExampleWords

0 1 1 0 1 0 1 1 

  require 'format/printf'
  '%10s  %s' printf (dquote ; 'FT' {~ Blocks&abc) &> ExampleWords
       ""  F
      "A"  T
   "BaRK"  T
   "BOoK"  F
  "tREaT"  T
 "COmMOn"  F
  "SqUAD"  T
"CoNfuSE"  T</lang>

Python

Python: Iterative, with tests

<lang python> blocks = [("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")]


def can_make_word(word, block_collection=blocks): 

   """
   Return True if `word` can be made from the blocks in `block_collection`.

   >>> 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("coNFused")
   True
   """
   if not word:
       return False

   blocks_remaining = block_collection[:]
   for char in word.upper():
       for block in blocks_remaining:
           if char in block:
               blocks_remaining.remove(block)
               break
       else:
           return False
   return True


if __name__ == "__main__": 

   import doctest
   doctest.testmod()
   print(", ".join("'%s': %s" % (w, can_make_word(w)) for w in
                   ["", "a", "baRk", "booK", "treat", 
                    "COMMON", "squad", "Confused"]))

</lang>

Output:
'': False, 'a': True, 'baRk': True, 'booK': False, 'treat': True, 'COMMON': False, 'squad': True, 'Confused': True

Python: Recursive

<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:
              (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.

Tcl

Works with: Tcl version 8.6

<lang tcl>package require Tcl 8.6

proc abc {word {blocks {BO XK DQ CP NA GT RE TG QD FS JW HU VI AN OB ER FS LY PC ZM}}} { 

   set abc {{letters blocks abc} {

set rest [lassign $letters ch] set i 0 foreach blk $blocks { if {$ch in $blk && (![llength $rest] || [apply $abc $rest [lreplace $blocks $i $i] $abc])} { return true } incr i } return false 

   }}
   return [apply $abc [split $word ""] [lmap b $blocks {split $b ""}] $abc]

}

foreach word {"" A BARK BOOK TREAT COMMON SQUAD CONFUSE} { 

   puts [format "Can we spell %9s? %s" '$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
Retrieved from "https://rosettacode.org/wiki/ABC_problem?oldid=238123"