# Write a Magic Spellchecker

The game Waving Hands is somewhere between a pen-and-paper Magic: the Gathering and a very elaborate Rock Paper Scissors. Each turn you write down one of eight gestures for each hand:

• wiggled Fingers
• proffered Palm
• Snap
• Wave
• Digit pointing
• Clap
• staB
• Nothing

There are few important rules that take precedence over the rest:

• If both hands gesture P you automatically surrender. (This is a simplification, but we'll go with that.)
• Only one hand at a time can gesture B.

A series of gestures performed by the same hand can cast a spell, where each spell is tied to one particular sequence. These sequences can overlap, but each gesture can only be used as the final gesture of a single spell (so you can create up to two spells in a single turn). Some spells require a gesture to be made with both hands simultaneously.

Your task is, given a list of gestures for each hand, to determine which spells could be cast in the current turn. For each hand, the last letter in the list represents the gesture chosen for the current turn.

Here is the list of gesture sequences. Upper case letters refer to a gesture performed by a single hand, lower case letters refer to a gesture performed with both hands.

B           Stab
cDPW        Dispel magic
cSWWS       Summon elemental
cw          Magic mirror
DFFDD       Lightning bolt
DFPW        Cure heavy wounds
DFW         Cure light wounds
DPP         Amnesia
DSF         Confusion
DSFFFc      Disease
DWFFd       Blindness
DWSSSP      Delayed effect
DWWFWD      Poison
FFF         Paralysis
FPSFW       Summon troll
FSSDD       Fireball
P           Shield
p           Surrender
PDWP        Remove enchantment
PPws        Invisibility
PSDD        Charm monster
PSDF        Charm person
PSFW        Summon ogre
PWPFSSSD    Finger of death
PWPWWc      Haste
SD          Missile
SFW         Summon goblin
SPF         Antispell
SPFPSDW     Permanency
SPPc        Time stop
SSFP        Resist cold
SWD         Fear
SWWc        Fire storm
WDDc        Lightning bolt
WFP         Cause light wounds
WFPSFW      Summon giant
WPFD        Cause heavy wounds
WPP         Counterspell
WSSc        Ice storm
WWFP        Resist heat
WWP         Protection from evil
WWS         Counterspell


Yes, Lightning bolt and Counterspell have two different sequences each.

You may write a program or function, taking input in any convenient list or string format, via STDIN, command-line argument or function argument, as long as it's not pre-processed. You may output pairs of spells via return value or by printing to STDOUT. Again, you may use any convenient list or string format, as long as the output is unambiguous.

You may assume that the sequences for left and right hand are the same length, and that they are valid (in particular, B will never be performed by two hands at the same time). Note that the input will only contain upper case letters. Lower case letters are only used in the above list to indicate that both hands need to perform the same (upper-case) gesture.

For spells which end in a two-hand gesture you should just output a single spell. If one hand cannot perform a spell, this needs to be indicated by a string containing only a hyphen, -.

This is code golf, so the shortest answer (in bytes) wins.

## Examples

Each example consists of three lines: the left hand sequence, the right hand sequence (both input; the right-most gesture is the most recent one), and the list of all possible spell combinations (the output).

WFP
WWS
[["Cause light wounds","Counterspell"],["Shield","Counterspell"]]

SD
BB
[["Missile","Stab"]]

WWP
WPP
[["Surrender"]]

DFW
CCW
[["Cure light wounds","-"]]

FFW
WWF
[["-","-"]]

DCW
CCW
[["Magic mirror"]]

WFPSFW
PPDDPP
[["Summon goblin","Shield"],["Summon ogre","Shield"],["Summon troll","Shield"],
["Summon giant","Shield"],["Summon goblin","Amnesia"],["Summon ogre","Amnesia"],
["Summon troll","Amnesia"],["Summon giant","Amnesia"]]

BSWWS
CSWWS
[["Counterspell","Counterspell"]]

CSWWS
CSWWS
[["Counterspell","Counterspell"],["Counterspell","Summon elemental"],
["Summon elemental","Counterspell"],["Summon elemental","Summon elemental"]]

PWPWWC
BBSPPC
[["Haste"],["Time stop"]]

• @TheBestOne "in particular, B will never be performed by two hands at the same time" Dec 20, 2014 at 5:39

# Python 2, 685

Defines a function f accepting two strings. Return value is the string Surrender if the player surrenders; otherwise, a set consisting of strings (which indicate two-handed spells), and length-2 tuples of strings (indicating separate spells for each hand).

Base64 encoded source:

I2VuY29kaW5nOkxhdGluCmV4ZWMiIiJ42mVTTWvjMBC951foJntxy+61iwtNjLqFLJhqQYeQg2KPbYEsBUlOGtrub98Zp6Efe7Lm6c2H3jyvy9Y0KVuWXCa940VT1arklYl7sGzUvWkQk0pJJEzj6B0DCyO4pC0vKiGqquRr0w/JGdeznbeJYKqxmgKwAfThxI5+cm2kiwtuKeUdr+uS340OotEYSYEs77opGu8wVlJKJFRg9QlaBl0HXHK1UUoobF97E4knBObVOmh7igarilpSv7exU/AWRxZS0sjCBNhpArCwHAzYFo+VwugRRn9cMAauGbRL9FS8mZNWgw4jw2IxQZhBcQH3EOYZPrX0fVwwhFSNTeXc1PUQmO9YCzpccrwg8LeJ0Vjkfczs/c4aLCdr7HDn0rwOO8fYFXk1hFE7nPGEoBTz2PjoxBpPL5Gki1wwjVMqulzpKX4VXX3WpzeaXorDVhf+5+UpWtIKA3z82zhKfeiMbMonCevgE64It8e64EcGBzOz5ZcC+eK+tHrctZrZIhTrm+f1Jm47H1hkxrE1Mx2z14DtjyZcclm8nvYodJbn2rUMt5eFzV+zLctIn8ulD1zz2xmiSoYqBY3KZxZcFvM8f10sz65vjqg/eZyNJgRMJO8J0cw/XDDoCGQyIdqSL3EdLfozvtkOKY8aObRJck59jCV/cAcTzc5Yk07z3hXxfmm0C62uxuCPGYHF5Pe0I7olIxIQRhSoqpr//yZ0P6IPzYWWL3CeK75ooWNdhrrlN015T4dimb/cZ6GwePgZIE3BbZqX5+ypOOUkxRNJcWauUSbWMkJPZ5TSzujr1XPWFm3+bRasyW+/568F2iQE3AQaf7uxm6sfKHs4f3jNt/9cMNXTZmIiIiIuZGVjb2RlKCd6aXAnKQ==


The source is of the formexec "eu352909HE%#NTHQh".decode('zip') which executes the following code:

L=dict(B='Stab',cDPW='Dispel magic',cSWWS='Summon elemental',DFFDD='Lightning bolt',DFPW='Cure heavy wounds',DFW='Cure light wounds',DPP='Amnesia',DSF='Confusion',DWSSSP='Delayed effect',DWWFWD='Poison',FFF='Paralysis',FPSFW='Summon troll',FSSDD='Fireball',P='Shield',PDWP='Remove enchantment',PSDD='Charm monster',PSDF='Charm person',PSFW='Summon ogre',PWPFSSSD='Finger of death',SD='Missile',SFW='Summon goblin',SPF='Antispell',SPFPSDW='Permanency',SSFP='Resist cold',SWD='Fear',WFP='Cause light wounds',WFPSFW='Summon giant',WPFD='Cause heavy wounds',WPP='Counterspell',WWFP='Resist heat',WWP='Protection from evil',WWS='Counterspell')
G=lambda l,r,L:{L[s]for s in L if l.endswith(s.upper())and all(r[~i]==s[~i].upper()or'a'>s[~i]for i in range(len(s)))}
B=dict(cw='Magic mirror',DSFFFc='Disease',DWFFd='Blindness',DWWFWc='Raise dead',PPws='Invisibility',PWPWWc='Haste',SPPc='Time stop',SWWc='Fire storm',WDDc='Lightning bolt',WSSc='Ice storm')
d='-'
def f(l,r):c=G(l,r,B)|G(r,l,B);return[c|{(x,y)for x in G(l,r,L)or d for y in G(r,l,L)or d}-{(d,d)*(len(c)>0)},'Surrender'][l[-1]==r[-1]=='P']

• @FryAmTheEggman fixed. Dec 19, 2014 at 17:14
• Aha, neat use of sets to fix that :) Dec 19, 2014 at 19:22

# CJam, 987 931 925663 bytes

qN/:Q;"Üãã0Ð¨¬Áó:-/ð1$½Ï¶¶òu´dóá3äÑì?´ì>³3cïCà×M×âÀCÒû¬u?xO,ÆFv)pÙû!¼ eÖUÈRÙnÂo/µ¾H¼RÎÚç¡ñ>z"32f-222bCb" BcDPWSwFdps"f=S/"[zõs¢@>2¯f¥sy<éSGÆÄbÚØÜ}}¤ºÅd¸(EWfa¤éõbfXpÀS7éÛM¼å© Ñæ¶a«I³þ>ÙÜ¡/¦$lâ µãÆØ¢§&á¼óÀwÏU¤ôYðçQòÔR#pÓzP×°~ï]v«viÚY¶¨¯|o(Nê@æGÏ]ÌÉþMNÒÀ2yÌgÊ]Ê4Ê|BÃKWãIowIQ£Í-,_¥÷¶ºK-;Kr ÕtVæWï÷¦?+ÜÌÜóË¯çp2Mvmc!hàtc»¬}sIæTÌÂ&ë6º²>Nº¯¦F¤½{ÜOSµ¸Ñ'|²P³íD¿Z.c¢ Ò¿ñÅ¢MRöDk?à§iõ;­¡k'çTÑñ"31f-225b26b97f+:c"j"Ser'z/{(eu\+}%]z_{{~SaQX={_QV=W):W=={_el+m*}{m*:s}?}/:s{S+2$S+#)1$"-":D?@@}%-2<}%1:V(:X(:W;\}2*m*{z_,1>{)__~=\Da&,!={a+}{;}?$W>}*~}%_&_,({[D_]a-}*_{{D&,!},}:A~,{A}*_["Surrender"_]a:S&,{;S}*p  Note that this contain all ASCII characters of ASCII code 32 to 255 only. Some characters might be skipped by SE, so better to copy the code from the link above This above code is a base converted version of the following 925 byte solution: qN/:Q; "B|Stab|cDPW|Dispel magic|cSWWS|Summon elemental|cw|Magic mirror|DFFDD|Lightning bolt|DFPW|Cure heavy wounds|DFW|Cure light wounds|DPP|Amnesia|DSF|Confusion|DSFFFc|Disease|DWFFd|Blindness|DWSSSP|Delayed effect|DWWFWc|Raise dead|DWWFWD|Poison|FFF|Paralysis|FPSFW|Summon troll|FSSDD|Fireball|P|Shield|p|""Surrender":R"|PDWP|Remove enchantment|PPws|Invisibility|PSDD|Charm monster|PSDF|Charm person|PSFW|Summon ogre|PWPFSSSD|Finger of death|PWPWWc|Haste|SD|Missile|SFW|Summon goblin|SPF|Antispell|SPFPSDW|Permanency|SPPc|Time stop|SSFP|Resist cold|SWD|Fear|SWWc|Fire storm|WDDc|Lightning bolt|WFP|Cause light wounds|WFPSFW|Summon giant|WPFD|Cause heavy wounds|WPP|Counterspell|WSSc|Ice storm|WWFP|Resist heat|WWP|Protection from evil|WWS|Counterspell"]s'|/2/_ {{~SaQX={_QV=W):W=={_el+m*}{m*:s}?}/:s{S+2$S+#)1$"-":D?@@}%-2<}%1:V(:X(:W;\}2* m*{z_,1>{)__~=\Da&,!={a+}{;}?$W>}*~}%_&
_,({[D_]a-}*_{{D&,!},}:A~,{A}*
_[R_]a:S&,{;S}*p


Newlines are just for show. This can be golfed a lot, but at least I got it to pass all test cases -_- .

This took longer than expected.

UPDATE 1 - golfed the code part a bit. Still scope for more. The string part can also be golfed/base converted, but I will refrain from that now as all other answers are not doing that either.

UPDATE 2 - Done golfing the code, now time for compressing that string.

UPDATE 3 - Base converted the string to reduce the code size to 663 bytes (It can be reduced to 640 bytes, but then there are 0 to 31 ASCII code characters too, which are really hard to deal with and I will only reside to them when I get beaten again).

Try it online here

# Java, 1565 1388

Call with java M %leftString %rightString. Outputs Surrender if player surrenders. Otherwise outputs string in this form bothHandSpell;oneHandSpell,oneHandSpell;.... Note, this is a one liner solution for a rather complicated problem. : )

class M{String[]a="B,cDPW,cSWWS,DFFDD,DFPW,DFW,DPP,DSF,DWSSSP,DWWFWD,FFF,FPSFW,FSSDD,P,PDWP,PSDD,PSDF,PSFW,PWPFSSSD,SD,SFW,SPF,SPFPSDW,SSFP,SWD,WFP,WFPSFW,WPFD,WPP,WWFP,WWP,WWS,-".split(","),b="Stab,Dispel Magic,Summon elemental,Lightning bolt,Cure heavy wounds,Cure light wounds,Amnesia,Confusion,Delayed effect,Poison,Paralysis,Summon troll,Fireball,Shield,Remove enchantment,Charm monster,Charm person,Summon ogre,Finger of death,Missile,Summon goblin,Antispell,Permanency,Resist cold,Fear,Cause light wounds,Summon Giant,Cause heavy wounds,Counterspell,Resist heat,Protection from evil,Counterspell,-".split(","),c="cw,DSFFFc,DWFFd,DWWFWc,PPws,PWPWWc,SPPc,SWWc,WDDc,WSSc".split(",");public static void main(String[]a){System.out.println(new M().s(a[0],a[1]));}int e,f,g,h,i,j,k,l,m,n;String s(String o,String p){if(m(o,p,"p")>0)return"Surrender";String q="";f=e=0;for(;f<10;f++)q+=(m(o,p,c[f])|m(p,o,c[f]))>0?"Magic mirror,Disease,Blindness,Raise dead,Invisibility,Haste,Time stop,Fire storm,Lightning Bolt,Ice storm".split(",")[f*(e=1)]+";":"";for(f=0;f<33-e;f++)for(g=f<1?1:0,h=0;g<32-h&m(o,p,a[f])>0;)q+=m(p,o,a[++g*(e=1)])>0?b[f]+","+b[g*(h=1)]+";":"";return q;}int m(String o,String p,String r){k=n=0;if(r=="-")n=1;if((i=o.length())<(j=r.length()))return n;for(;k<j;)n|=((o.charAt(l=i-j+k)|32)!=((m=r.charAt(k++))|32)|((m|32)==m&(p.charAt(l)|32)!=(m|32)))?2:0;return n==2?0:1;}}


Indented:

class M{

String[]a="B,cDPW,cSWWS,DFFDD,DFPW,DFW,DPP,DSF,DWSSSP,DWWFWD,FFF,FPSFW,FSSDD,P,PDWP,PSDD,PSDF,PSFW,PWPFSSSD,SD,SFW,SPF,SPFPSDW,SSFP,SWD,WFP,WFPSFW,WPFD,WPP,WWFP,WWP,WWS,-".split(","),b="Stab,Dispel Magic,Summon elemental,Lightning bolt,Cure heavy wounds,Cure light wounds,Amnesia,Confusion,Delayed effect,Poison,Paralysis,Summon troll,Fireball,Shield,Remove enchantment,Charm monster,Charm person,Summon ogre,Finger of death,Missile,Summon goblin,Antispell,Permanency,Resist cold,Fear,Cause light wounds,Summon Giant,Cause heavy wounds,Counterspell,Resist heat,Protection from evil,Counterspell,-".split(","),c="cw,DSFFFc,DWFFd,DWWFWc,PPws,PWPWWc,SPPc,SWWc,WDDc,WSSc".split(",");

public static void main(String[]a){
System.out.println(new M().s(a[0],a[1]));
}

int e,f,g,h,i,j,k,l,m,n;

String s(String o,String p){
if(m(o,p,"p")>0)
return"Surrender";
String q="";
f=e=0;
for(;f<10;f++)
q+=(m(o,p,c[f])|m(p,o,c[f]))>0?"Magic mirror,Disease,Blindness,Raise dead,Invisibility,Haste,Time stop,Fire storm,Lightning Bolt,Ice storm".split(",")[f*(e=1)]+";":"";
for(f=0;f<33-e;f++)
for(g=f<1?1:0,h=0;g<32-h&m(o,p,a[f])>0;)
q+=m(p,o,a[++g*(e=1)])>0?b[f]+","+b[g*(h=1)]+";":"";
return q;
}

int m(String o,String p,String r){
k=n=0;
if(r=="-")
n=1;
if((i=o.length())<(j=r.length()))
return n;
for(;k<j;)
n|=((o.charAt(l=i-j+k)|32)!=((m=r.charAt(k++))|32)|((m|32)==m&(p.charAt(l)|32)!=(m|32)))?2:0;
return n==2?0:1;
}

}


Edit: Used Peter's suggestion to create a String array with less code.

Any hints to improve this would be appreciated.

• This general technique will save you a few hundred chars. Dec 21, 2014 at 8:30

# JavaScript (ES6), 1070 941

Base64 encoded:

Zj0obCxyKT0+e3k9WyItIl0sRD1bXSxSPVtdLEw9W10sZD17fSxidG9hKGBK1pvQHQOKyl6XWZqCJzRwM9bRK6aaifV6V6Z6e1qXRxJZZLQxqCJzWaKuuivRzDQuKCG2eKeDVuiW3QMUUMPQK6t7WF5q/LXCi6d2zQMU9bQK6t7WWKCG3XCi6d2zQMVbQCad6yJrQM8/QKid+6yKifQKIXQOKx5qx7QKIUUVzQGWKd2d6yzQNYUV3QN6VrJ53V5995y3QNZJJI/RFqKx7V15p3QKZYVZzQ+iKyifQNZYVYPQ9qtqXFysis0FFF0Summon1troll0FPSFW0Fireball0FSSDD0Shield0P0Surrender0p0Remove1enchantment0PDWP0Invisibility0PPws0Charm1monster0PSDD0Charm1person0PSDF0Summon1ogre0PSFW0Finger1of1death0PWPFSSSD0Haste0PWPWWc0Missile0SD0Summon1goblin0SFW0Antispell0SPF0Permanency0SPFPSDW0Time1stop0SPPc0Resist1cold0SSFP0Fear0SWD0Fire1storm0SWWc0Lightning1bolt0WDCs0Cause1light1wounds0WFP0Summon1giant0WFPSFW0Cause1heavy1xcKLp3bNFjxQ9AqLp7Xq7KXpZdFjz9CHHtbLaK5tFkknNEXrIrLdYXmrdFlhT9D66LXnLYqJ9X66JtXr4pdFlj9AqLp7Xq7KXpZdFlkmApLnJlcGxhY2UoLzEvZywiICIpLnNwbGl0KDApLmV2ZXJ5KCh2LHgsYSk9PmRbeCUyfHxhW3grMV1dPXYpO2s9KGgsbyxHKT0+KG49ZFtzXSxxPWgubWF0Y2gocysiJCIsImkiKSkmJlsuLi5zXS5ldmVyeSgoYyxpKT0+ISh3PWMubWF0Y2goIlthLXpdIikpfHxoW2o9aStoLnNlYXJjaChxKV09PW9bal0pJiYodz9+fkQuaW5kZXhPZihuKT9EOltdOkcpLnB1c2gobik7Zm9yKHMgaW4gZCl7ayhsLHIsTCk7ayhyLGwsUik7aWYoRD09ZFsicCJdKXJldHVybiBEfVI9Ui0xP3k6UjtMPUwtMT95Okw7cmV0dXJuIEQtMXx8UiE9TD9MLnNvbWUocz0+Ui5zb21lKHQ9PiFELnB1c2goW3MsdF0pKSl8fEQ6RH0=


You run it by doing eval(atob("Zj0obCxyK...")) in the Firefox console.

Golfed code (may include characters not supported by Stack Exchange):

f=(l,r)=>{y=["-"],D=[],R=[],L=[],d={},btoa(JÖÐÊ^Y'4p3ÖÑ+¦õzW¦z{ZGYd´1¨"sY¢®º+ÑÌ4.(!¶x§VèÝPÃÐ+«{X^jüµÂ§vÍõ´
êÞÖX Ýp¢éÝ³@Å[@&ë"k@Ï?@¨û¬ô
!t+jÇ´
!EÍ)Ýë,Ð5ÝzV²yÝ^}÷·@ÖI$Ñ¢±í]y§t eYÍ¢+(@ÖXUÐö«j\\¬Í]ºi¨[k¢Ytô[Ab­æÚ]I ÃÑ(bzWt?D®®·§uêô§D^ÞÕéÜ©íéíÐðÖ?B'¾+"n)b·-?4 «Y¨Ë^¯CÒ=ªæÖ«²ô= ÅÑ+¦õ¢ ÞÐô[Ab«Öõuæ­CÖ<TH=jË^ÐõYg42+,W´H=ºi¨X(nX§Ñ!VÐ íÊ^]<]z¹éÜËDô[Dâíl¶tHóÜÑ¬Ëur]Ñ$?A^j½X=·µ²Ú+DYÍm)àÕº%·E
ÍjëÖX Ýp¢éÝ³E?D®j'ÖÝô[@ºÇµæ¯Ë\\(ºwlÑcÅ@¨º{^®Ê^]<ýqíl¶æÑdsD^²+-Ö·Eý®^rØ¨Wë¢m^¾)tYcô
§µêì¥éeÑe).replace(/1/g," ").split(0).every((v,x,a)=>d[x%2||a[x+1]]=v);k=(h,o,G)=>(n=d[s],q=h.match(s+"$","i"))&&[...s].every((c,i)=>!(w=c.match("[a-z]"))||h[j=i+h.search(q)]==o[j])&&(w?~~D.indexOf(n)?D:[]:G).push(n);for(s in d){k(l,r,L);k(r,l,R);if(D==d["p"])return D}R=R-1?y:R;L=L-1?y:L;return D-1||R!=L?L.some(s=>R.some(t=>!D.push([s,t])))||D:D}  Since the spell dictionary consists of letters only, we can treat it as a base64-encoded string and use numbers as separators and spaces. I "decoded" the base64-like string into a binary string, which is 3/4 the size of the original. Mildly ungolfed: f=(l,r)=>{ // y - default array // D,R,L - result arrays for Doublehanded, Right and Left // d - dictionary mapping of spell combos to spell names y=["-"],D=[],R=[],L=[],d={}, // split string on 0 and replace 1s with spaces, to populate d btoa(<UGLY BINARY STRING>).replace(/1/g," ").split(0).every((v,x,a)=>d[x%2||a[x+1]]=v); // given a main hand, off hand, and result array to populate, // decide if current combo s applies k=(h,o,G)=> (n=d[s],q=h.match(s+"$","i")) // does s match the end of h, case insensitive?
&&
[...s].every((c,i)=>
!(w=c.match("[a-z]")) ||     // is every letter of s not lowercase
h[j=i+h.search(q)]==o[j]  // or (if lowercase), a match between the hands?
)
&&
(w?                    // if the last letter so s was lowercase
~~D.indexOf(n)?    //   if D doesn't already have this spell
D   //      add it to D
:    //   else
[]  //      add it to a throwaway array
:G).push(n);         // else, add it to this hand's result array

for(s in d){
k(l,r,L);    // test this spell against each hand
k(r,l,R);
if(D==d["p"]) return D  // if the doublehanded result is "Surrender"
// return immediately
}

R=R-1?y:R;   // replace empty arrays with ["-"]
L=L-1?y:L;   // ([]-1 is -1, which is truthy, while ["foo"]-1 is NaN, falsy)

return D-1||R!=L         // if D is empty, or R and L not both empty,
?        //   add all pairwise R/L combos to D and return D
L.some(s=>R.some(t=>!D.push([s,t])))
||D
:D      //    otherwise, just return D

}


One golf I particularly like is testing for empty arrays with array - 1.

• An empty array will produce a truthy value: [] - 1 => "" - 1 => 0 - 1 => -1 (truthy)
• A filled array will produce a falsey value: ["foo"] - 1 => "foo" - 1 => NaN (falsey)