title: Write a Magic Spellchecker

text:
# Question
Title: 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 `F`ingers
* proffered `P`alm
* `S`nap
* `W`ave
* `D`igit pointing
* `C`lap
* sta`B`
* `N`othing

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
DWWFWc      Raise dead
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"]]

```

# Answer
# CJam, ~~987 931 925~~ 663 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
> 3 votes

# Answer
# 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 form`exec "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']

```
> 4 votes

# Answer
# 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.
> 2 votes

# Answer
# 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 `1`s 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)`
> 1 votes

---
Tags: code-golf, string, game
---


title: Partition of a positive integer N

text:
# Question
Title: Partition of a positive integer N
Find the number of partitions of a positive integer n. Hope someone uses the explicit finite formula for the partition function defined in Jan Hendrik Brunier and Ken Ono paper here.

```
Sample Input
8
Sample Output
22

```

N is less than or equal to 1000. Write the complete program. More than anything I would like to see the different approaches.

# Answer
> 1 votes
**Java Solution**

```
 public class IntegerPartition {
        public static void main(String[] args) {
            int n = 8; //set integer here!!
            int[][] a = new int[n + 1][n + 1];
            int i, j, k;
            for (i = 0; i < a.length; i++) {
                a[i][0] = 0;
                a[0][i] = 1;
            }
            for (i = 1; i < a.length; i++) {
                a[i][1] = 1;
                for (j = 2; j < a[0].length; j++) {
                    k = i - j;
                    if (k < 0)
                        a[i][j] = a[i][j - 1];
                    else
                        a[i][j] = a[i][j - 1] + a[k][j];
                }
            }
            i--;
            int answer = a[i][i - 1];
            System.out.println(answer + 1);
        }
    }

```

# Answer
> 2 votes
## Python (109 89)

```
n=input()
s=0
l=[(n,n)]
while l:a,i=l.pop(0);s+=a==0;l+=[(a-i,i),(a,i-1)]*(a*i>0)
print s

```

# Answer
> 1 votes
## Mathematica 11 chars

Sorry, no need to implement the algorithm

```
PartitionsP

```

Usage

```
%[8]
22

```

# Answer
> 1 votes
# Ruby - 95 chars

Based on Hoa Long Tam's solution

```
s=0
l=[[n=gets.to_i,n]]
(a,i=l.pop;a>0&&i>0&&l+=[[a-i,i],[a,i-1]];a==0&&s+=1)until l==[]
p s

```

# Answer
> 1 votes
# Perl, 92 chars

Recursive solution using `p(k,n)` = number of partitions of `n` using numbers \>= `k`. Uses dynamic programming and partitions 1000 in 2s on my machine.

```
sub p{my($k,$n)=@_;$c{$k,$n}||($c{$k,$n}=$k<$n?p($k+1,$n)+p($k,$n-$k):$n==$k)}print p(1,pop)

```

Ungolfed:

```
sub p {
    my ( $k, $n ) = @_;
    $c{$k,$n}
    || (
        $c{$k,$n} =
        $k < $n
            ? p($k+1,$n) + p($k,$n-$k)
            : $n == $k
    )
}
print p( 1, pop );

```

# Answer
> 1 votes
# Perl, 70 chars

Since there was no time limit:

```
sub p{my($k,$n)=@_;$k<$n?p($k+1,$n)+p($k,$n-$k):$n==$k}print p(1,pop);

```

Partitions 50 in 2.3 s.

# Answer
> 1 votes
## J, 72

Modified from the manual:

```
f=:[:(0<@-."1~>@{:)](,([:<@;(-i.)@#([,.(>:{."1)#])&.>]))@]^:[(<i.1 0)"_

```

eg

```
#f 8
22

```

# Answer
> 1 votes
# APL, 23 characters

`{⍵=0:1⋄+/⍵(-∇¨⍨⊢⌊-)⍳⍺}⍨`

# Answer
> 0 votes
# Haskell, ~~51~~ 39

```
f=(%1)
0%k=1
n%k=sum[(n-r)%r|r<-[k..n]]

```

the `%` function gets two parameters - `n` and `k`, and returns the amount of partitions of `n` at which every part is at least `k`.

`%`'s definition works by choosing `r` to be the next part of the partition. we compute the amount of possibilities when this is the next part (note that all consequent parts must be bigger or equal to it) by a recursive call and sum all possibilities.

---
Tags: code-challenge, popularity-contest, integer-partitions
---


title: String generator based on a wildcard

text:
# Question
Title: String generator based on a wildcard
Your task, if you accept it, is to make a string generator that generates strings based on a wildcard.

You can make a function or a full program that receives 1 argument and sends to the standard output/console a string that matches.

**Wildcard characters and sequences:**

* `*` produces 0 or more random characters
* `?` produces exactly 1 random character
* `[]` detonates a group and produces any one of the characters from the group, exactly once.
* `[]*` produces at least 0 of the characters from that group
* `[]?` produces any one of the characters from that group, at most once
* `[]{n}` produces `n` characters in that group
* Anything else is a literal string

The supported characters to return are `a-z`, `A-Z` and `0-9`.
Casing doesn't matter.

You can do whatever you want with invalid input.

Examples:

```
f('a[d-f]{3}') //return 'addd', 'adde', 'addf' ...

f('a*') //returns 'a' or anything starting with 'a'

f('[bt]est') //returns 'best', 'test'

```

**Scoring:**

* Shortest code in **bytes** wins.
* -10% bonus if you support symbols
* -10% bonus if you implement multiple matches, inside each group (e.g.: `[ae,c-d,0-5]`)
* -20% bonus if you implement negated group (e.g.: `[^a-f]` returns anything that doesn't start with `a-f`)
* -10% if you support at least 3 regex character classes (e.g.: `\d`,`\s`,`\D`)
* Standard loopholes are **not** allowed!

Any doubts, feel free to ask in a comment.

# Answer
> 1 votes
# Python 3, 511 bytes - 10% = 459.9

It's early morning over here so golfing mode hasn't quite kicked into my system yet, but it was a really fun-looking problem so I thought I'd try it anyway.

```
from random import*
C=0
r=input()
i=0
S=""
Q=""
while i<len(r):
 c=r[i]
 if i<len(r)-1:d=r[i+1]
 if"]"==c:
  C=0
  if d not in"*?{":S+=choice(Q)
 elif"["==c:C=1;Q=""
 elif"*"==c:
  while random()>.2:S+=choice(Q)
 elif"?"==c:S+=choice(Q)*randint(0,1)
 elif"{"==c:
  a=""
  while r[i+1]!="}":a+=r[i+1];i+=1
  S+="".join(choice(Q)for _ in range(int(a)))
 elif"}"!=c:
  if"-"==d:Q+="".join(chr(x)for x in range(ord(c),ord(r[i+2])+1));i+=2
  else:
   Q=C*Q+c
   if not C and d not in"*?{":S+=choice(Q)
 i+=1
print(S)

```

I'm claiming the "multiple matches, inside each group" bonus. You can try it out like so:

```
[abA-C0]*

```

---
Tags: code-golf, string, generation
---


title: Forcing the Horse

text:
# Question
Title: Forcing the Horse
This is a simple one: create the shortest browser script to change every appearance of force on a web page into horse. This script needs to be able to be pasted into the console and work on most modern browsers.

You must replace **all** occurences of the word force and conjugates of the word force (forcing, forced, reinforce). The cases must also be preserved.

You must not change any occurences which are not visible when the page is displayed in a browser. For example, meta tags or comments.

## Example

This is a `fOrcE log`. It makes people who touch it very forceful. Don't try forcing it.
This is a `hOrsE log`. It makes people who touch it very horseful. Don't try horsing it.

Unfortunately this is a Javascript only challenge. The shortest code wins.

# Answer
## 175 bytes, ES5, XPATH

This tests successfully in the latest Firefox and Chrome. Criticism is welcome! This is my first golf swing, and I hope I'm doing it right.

```
d=document,f=d.evaluate('//text()',d,{},7,{});for(i=0;t=f.snapshotItem(i++);)t.data=t.data.replace(/(f)(or)(c)/ig,function(a,b,c,e){return(b=='f'?'h':'H')+c+(e=='c'?'s':'S')})

```

The `document.evaluate()` method is supported by all major browsers except IE, which I hope satisfies the requirement for "most modern browsers". And because the XPath selector selects only text nodes, this ought to leave attributes, comments, namespaces, and other data not intended for display untouched without needing to check for each node's `offsetParent`.

### Ungolfed version:

```
var force = document.evaluate('//text()', document, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);

for (var i = 0; textNode = force.snapshotItem(i++); /* nothing */) {
    textNode.data = textNode.data.replace(
        /(f)(or)(c)/ig,
        function (full, $1, $2, $3) {
            return ($1 == 'f' ? 'h' : 'H' )
                + $2
                + ($3 == 'c' ? 's' : 'S' );
        }
    );
}

```

---

Or if I replace `function / return` with ECMA6 fat arrow notation, I can get it down to 163 characters.

```
d=document,f=d.evaluate('//text()',d,{},7,{});for(i=0;t=f.snapshotItem(i++);)t.data=t.data.replace(/(f)(or)(c)/ig,r=(a,b,c,e)=>(b=='f'?'h':'H')+c+(e=='c'?'s':'S'))

```

This syntax currently only works in Firefox though, I think. Until more browsers adopt this syntax, the 175-byte solution above shall remain my official entry for the game.
> 5 votes

# Answer
# ECMAScript 5, ~~248~~ ~~233~~ ~~193~~ ~~191~~ 182 bytes

```
for(w=(d=document).createTreeWalker(d,4);t=w.nextNode();)
if(t.parentNode.offsetParent)t.data=t.data.replace(/(f)(or)(c)/gi,
function(a,b,c,d){return(b<'f'?'H':'h')+c+(d<'c'?'S':'s')})

```

Tested in Chrome and Firefox.

### Ungolfed version

We should only modify visible TextNodes; URLs, attributes, etc. are not displayed in the browser. We can use a TreeWalker to find all of them. Visible TextNodes will be identified by checking if their ParentNode has a truthy offsetParent.1

```
// Create a TreeWalker that walks through all TextNodes.

var walker = document.createTreeWalker(document, NodeFilter.SHOW_TEXT, null, false);

// While there are nodes left,

while(node = walker.nextNode())

// if the node is visible,

    if(node.parentNode.offsetParent)

// search for the string "forc" (ignoring case)

        node.data = node.data.replace(/(f)(or)(c)/gi,

// and replace an uppercase/lowercase F/C with an uppercase/lowercase H/S.

            function(match, F, OR, C)
            {
                return (F != 'f' ? 'H' : 'h') + OR + (C != 'c' ? 'S' : 's')
            }
)

```

1 This is buggy in IE 9.
> 3 votes

# Answer
## 200 bytes, ES6

Here is an ES6 version. Run it in latest Firefox's web console.

```
for(a=document.all,i=0;n=a[i++];)(p=>p&&p.offsetParent?n.innerHTML=n.innerHTML.replace(/f[o0]rc(e|ing)/gi,m=>(v=>{k=[...m];k[0]=k[0]<'F'?'H':'h';k[3]=k[3]<'C'?'S':'s'})()||k.join("")):0)(n.parentNode)

```

~~I'll add the ungolfed version if requested :)~~

Here is the ungolfed version

```
var all = document.all;
for (var i = 0; i < all.length; i++) {
  if (all[i].parentNode && all[i].parentNode.offsetParent) {
    all[i].innerHTML = all[i].innerHTML.replace(/f[o0]rc(e|ing)/gi, function(matched) {
      var k = matched.split(""); // convert to array
      k[0] = k[0] == "F"? "H" : "h";
      k[3] = k[3] == "C"? "S" : "s";
      return k.join("");
    })
  }
}

```
> 2 votes

---
Tags: code-golf, javascript
---


title: Magic box problem

text:
# Question
Title: Magic box problem
You have an input array of size m\*n. Each cell in the array is populated with either P or T. The only operation you can do on the array is flip columns. When you flip a column, the letters in all the cells of that column switch (P becomes T and viceversa). If you have 'x' number of rows with same letter (e.g. PPPP) then you get a point. Design an algorithm that takes in the array and returns a solution (which columns to flip) such that the resulting array has maximum number of points possible.

Note: In case there are multiple solutions that yield the highest score, choose the one with lowest number of flips. Example:

Input Array:

```
PPTPP
PPTPP
PPTTP
PPPTT
PPPTT

```

Output:

```
3

```

Explanation:
A solution that yields the highest points: Flip column no. 3
Then the original array would be:

```
PPPPP // 1 point
PPPPP // 1 point
PPPTP
PPTTT
PPTTT

//Total: 2 points

```

Note that one could also flip columns 4 and 5 to get a score of two, but that needs an additional flip.

You may use any convenient input format to represent the two dimensional array, and you may also any two distinct, but fixed, values to represent `P` and `T`.

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

# Answer
> 3 votes
# APL, 37

```
{x/1+⍳⍴x←y[↑⍋(+/∘.≠⍨2⊥⍉y),¨+/y←⍵⍪~⍵]}

```

Example:

```
{x/1+⍳⍴x←y[↑⍋(+/∘.≠⍨2⊥⍉y),¨+/y←⍵⍪~⍵]} 5 5⍴0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1

```

Tested here.

# Answer
> 1 votes
# Pyth, 28

```
f@eo+/QN/Qm!dN_osZ^U2lhQTUhQ

```

Takes input in the form of a nested list, e.g.

```
[[0,0,1,0,0],[0,0,1,0,0],[0,0,1,1,0],[0,0,0,1,1],[0,0,0,1,1]]

```

Gives output 0-indexed, e.g.

```
[2]

```

`^U2lhQ`: Generates all possible lists of 0s and 1s of the right length.

`_osZ`: Orders these lists from most 1s to least.

`+/QN/Qm!dN`: Counts how many times each list (`N`) and its inverse, 0s and 1s swapped (`m!dN`) occur in the input. The former corresponds to a series of flips leaving all zeros, the latter to leaving all ones.

`eo`: Orders the list by the above key, and takes its last element, which will be the result with the most matching columns, and among them the one with the least ones.

`f@ ... TUhQ`: Converts this list of 1s and 0s to a list of indices to be flipped.

For 1-indexing, change the `d` to a `k`, then put `mhd` at the beginning.

# Answer
> 0 votes
# Haskell, 98

```
g s=snd$maximum[((sum[1|o<-s,o==r||o==map(1-)r],-sum r),[i|(i,1)<-zip[1..]r])|r<-s++map(map(1-))s]

```

input format is a list of list of ints. you can use a string version for testing:

```
gg = g . map (map (\c -> case c of 'T' -> 0 ; _ -> 1) ) . lines

```

oh no the spaces! it hurts!

this works by iterating over the rows and calculating the number of points we will get if we flipped the columns in a way that this row gains us a point.

first thing to notice is that flipping the row to either all `True` or all `False` doesn't matter, because the grids will be exactly the inverse of each other and thus will have the exact same score.

the way we calculate the count when a given row gains a point is so: we iterate over the rows again, and sum the points each row gives us, using the fact that they do exactly when the rows are either identical or the exact inverse.

for example, if the row we are flipping is `TPPTP` and the current row we are iterating over is `PTTPT` or `TPPTP` then the row gains us a point, but when it's any other row, it doesn't gain us any points.

# Answer
> 0 votes
# CJam, ~~53~~ 51 bytes

```
l~z:X,,La\{1$f++}/{,}${X\{_X=:!t}/z{_&,(},,}$0=:)S*

```

This reads a two-dimensional array of 0s and 1s from STDIN. E.g. the example in the question would be

```
[[0 0 1 0 0] [0 0 1 0 0] [0 0 1 1 0] [0 0 0 1 1] [0 0 0 1 1]]

```

Test it here.

This first gets all possible subsets of columns, in order of increasing length, then performs the flips for each subsets and sorts them by how many rows still have both 0s and 1s in them. Finally, we just return the first such subset. This relies on the sorting being stable, such that the initial order of increasing length takes care of the tie-breaker.

# Answer
> 0 votes
# CJam, 37

```
q~_{:!}%+:T{T1$a-,\0-+}$0={U):U*}%0-`

```

Input format:

```
[[0 0 1 0 0] [0 0 1 0 0] [0 0 1 1 0] [0 0 0 1 1] [0 0 0 1 1]]

```

# Answer
> 0 votes
# Mathematica - 76

```
{
{P, P, T, P, P},
{P, P, T, P, P},
{P, P, T, T, P},
{P, P, P, T, T},
{P, P, P, T, T}
}/.{P -> 1, T -> 0};
First@MaximalBy[
  Subsets@Range@Length[%],
  MapAt[1-#&,%,{All,#}]~Count~{1..}&
]

```

# Answer
> 0 votes
## Python 2, 234

```
from itertools import *
A=input()
n=len(A[0])
R=range(n)
S=(0,)
for p in[q for i in R[:-1] for q in combinations(R,i)]:
    s=[sum([(l[q]+(q in p))%2 for q in R])for l in A]
    m=s.count(n)+s.count(0)
    if m>S[0]:S=(m,p)
print S[1]

```

Input is a list of lists:

```
[[0,0,1,0,0],[0,0,1,0,0],[0,0,1,1,0],[0,0,0,1,1],[0,0,0,1,1]]

```

Output is a tuple of flips using python indexing from 0:

```
(2,)

```

If the output must be indexed from 1, then the code is 272 characters with 0 denoting no flips:

```
print 0 if len(S[1])==0 else [p+1 for p in S[1]]

```

---
Tags: code-golf
---


title: Construct a graph

text:
# Question
Title: Construct a graph
In this challenge, your task is to construct an undirected graph from a sequence of directives. There is one directive for each nonnegative integer, and each transforms a given graph into a new one.

* Directive `0`: Add a new disconnected node.
* Directive `1`: Add a new node, and connect it to every existing node.
* Directive `m > 1`: Remove all nodes whose degree (number of neighbors) is divisible by `m`. Note that `0` is divisible by all `m`, so disconnected nodes are always removed.

The directives are applied one by one, from left to right, starting with the empty graph. For example, the sequence `[0,1,0,1,0,1,3]` is processed as follows, explained using awesome ASCII art. We start with the empty graph, and add a single vertex as directed by `0`:

```
a

```

Then, add another vertex and connect it to the first, as directed by `1`:

```
a--b

```

We add another disconnected vertex and then a connected one, as directed by `0` and `1`:

```
a--b   c
 \  \ /
  `--d

```

We repeat this one more time, as directed by `0` and `1`:

```
  ,--f--e
 /  /|\
a--b | c
 \  \|/
  `--d

```

Finally, we remove the degree-3 vertices `a` and `b`, as directed by `3`:

```
f--e
|\
| c
|/
d

```

This is the graph defined by the sequence `[0,1,0,1,0,1,3]`.

# Input

A list of nonnegative integers, representing a sequence of directives.

# Output

The number of nodes in the graph defined by the sequence.

# Test cases

```
[] -> 0
[5] -> 0
[0,0,0,11] -> 0
[0,1,0,1,0,1,3] -> 4
[0,0,0,1,1,1] -> 6
[0,0,1,1,0,0,1,1,2,5,7,0,1] -> 6
[0,0,1,1,1,1,5,1,4,3,1,0,0,0,1,2] -> 6
[0,0,1,1,0,0,1,1,5,2,3,0,0,1,1,0,0,1,1,3,4,0,0,1,1,2,1,1] -> 8
[0,0,1,1,0,0,1,1,2,5,7,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,8] -> 14

```

# Detailed rules

You can write a function or a full program. The shortest byte count wins. Standard loopholes are disallowed. Please explain your algorithm in your answer.

---

It's been a week, so I have accepted the shortest answer. If an even shorter one comes along later, I'll update my choice. An honorable mention goes to Peter Taylor's answer, on which several others were based on, including the winner.

# Answer
> 4 votes
# Pyth, ~~37~~ 31

```
lu?+GH<H2m@Gdf%+*@GTtTs>GTHUGQY

```

This solution uses a reduce function (`u`) to build up a list, where each entry corresponds to a node remaining in the list, and the value of the entry corresponding to whether the node was originally added under directive 0 or 1.

`G` is the accumulator variable in the reduce function, and holds the aforementioned list. It is initialized to the empty list, `Y`.

`H` takes the value of each member of `Q`, the input, one by one. The result of the expression is assigned to `G` each time, and the next entry of `Q` is assigned to `H`, and the expression is rerun.

To update `G` properly, there are two possibilities, one for directive 0 or 1, and one for the other directives. These case are distinguished with the ternary `? ... <H2 ...`

If `H` is 0 or 1, then all we need to do is append `H` to `G`. `+GH` accomplishes this.

Otherwise, the first thing that is need is to determine, for every node in the graph, how many neighbors it has. This is accomplished in two steps:

First, `s>GT` counts the number of nodes at or after the input node which are 1s. These are all connected to the input node, except that we will over count by 1 if the input node is a 1.

Second, we need the number of nodes earlier than the input node which are connected to it. This is 0 if the input node is a 0, and the index of the input node, `T`, if the input node is a 1. This value would be given by `*@GTT`. However, there is still the over count from the first section which needs to be corrected. Thus, we calculate `*@GTtT` instead, which is 1 less if the input node is a 1. These values are summed, to give the number of nodes connected to the input node.

`% ... H` will give 0 is that number is divisible by `H`, and thus should be removed, and will not give 0 otherwise.

`f ... UG` will thus give the indices of the input which should not be removed, since `f` is a filter, and 0 is falsy.

`m@Gd` converts these indices to the 0s and 1s of the corresponding nodes.

Finally, once the resultant list of nodes labeled 0 and 1 is found, its length is computed (`l`) and printed (implicit).

Broad idea thanks to @PeterTaylor.

# Answer
> 12 votes
## GolfScript (53 bytes)

```
])~{:^1>{.-1:H)-,:T;{..H):H*T@-:T+^%!{;}*}%}{^+}if}/,

```

Online demo

I haven't actually golfed this yet, but I have discovered that it's not very easy to eliminate the `H` and `T` variables so this might be a local minimum.

Takes input on stdin in the format `[0 1 2 3]`. Leaves output on stdout.

Ungolfed:

```
])~{
  :^1>{
    # array of 0s and 1s
    # Each 0 has degree equal to the number of 1s after it
    # Each 1 has degree equal to the number of values before it plus the number of 1s after it
    .-1:H)-,:T;
    {
      # Stack: x
      # T' = T - x is the number of 1s after it
      # H' = H + 1 is the number of values before it
      # Degree is therefore H' * x + T' = H * x + T - x = (H-1)*x + T
      # Keep x unless degree % ^ == 0
      ..H):H*T@-:T+^%!{;}*
    }%
  }{^+}if
}/,

```

# Answer
> 4 votes
# CJam, ~~129 75 73 68 61 46~~ 42 bytes

Solution based on Peter's algorithm:

```
Lq~{I+I1>{0:U(<:L{LU<,*LU):U>1b+I%},}*}fI,

```

Code expansion to follow.

---

Previous solution (61 bytes):

```
Lq~{:N2<{U):UaN{f+U1$0f=+}*a+}{{:X,(N%_!{X0=L+:L;}*},Lf-}?}/,

```

Takes input from STDIN like:

```
[0 0 1 1 0 0 1 1 5 2 3 0 0 1 1 0 0 1 1 3 4 0 0 1 1 2 1 1]

```

Output is the number on STDOUT:

```
8

```

**Algorithm**:

* Maintain an incrementing variable `U` which stores id of the node to be added.
* Maintain a list of list in which , each list is a node with a unique id made up by the first element of the list and the remaining elements being the ids of connected nodes.
* In each iteration (while reading the input directives),
    + If the directive is `0`, add `[U]` to a list of list
    + If the directive is `1`, add `U` to each list in the list of list and add another list comprised of first element of each of the list of list and `U`
    + For directive to remove, I filter out all lists of `length - 1` divisible by `m` and keep noting the first element of those lists. After filtering, I remove all the removed id from remaining list of ids.

**Code expansion**:

```
Lq~{:N2<{U):UaN{f+U1$0f=+}*a+}{{:X,(N%_!{X0=L+:L;}*},Lf-}?}/,
L                                            "Put an empty array on stack";
 q~                                          "Evaluate the input";
   {                                }/       "For each directive";
    :N                                       "Store the directive in N";
      2<{     ...    }{    ...    }?         "If directive is 0 or 1, run the first";
                                             "block, else second";
{U):UaN{f+U1$0f=+}*a+}
 U):U                                        "Increment and update U (initially 0)";
     a                                       "Wrap it in an array";
      N{         }*                          "Run this block if directive is 1";
        f+                                   "Add U to each list in list of list";
          U1$                                "Put U and list of lists on stack";
             0f=                             "Get first element of each list";
                +                            "Prepend U to the above array";
                   a+                        "Wrap in array and append to list of list";
{{:X,(N%_!{X0=L+:L;}*},Lf-}
 {                   },                      "Filter the list of list on this block";
  :X,(                                       "Get number of connections of this node";
      N%_                                    "mod with directive and copy the result";
         !{        }*                        "If the mod is 0, run this block";
           X0=                               "Get the id of this node";
              L+:L;                          "Add to variable L and update L";
                       Lf-                   "Remove all the filtered out ids from the";
                                             "remaining nodes";
,                                            "After the whole process is completed for"
                                             "all directives, take length of remaining ";
                                             "nodes in the list of list";

```

Try it here

# Answer
> 4 votes
# APL, ~~71~~ ~~65~~ 55 characters

~~`{⍬≡⍺:≢⍵⋄r←1↓⍺⋄1<c←⊃⍺:r∇i⌿⍵/⍨i←0≠c|+/⍵⋄c:r∇∨⌿↑a(⍉a←⍵,1)⋄r∇0,0⍪⍵}∘(0 0⍴0)`~~

~~`{⍺←0 0⍴0⋄⍬≡⍵:≢⍺⋄(⍺{1<⍵:i⌿⍺/⍨i←×⍵|+/⍺⋄⍵:-⌿↑(1,1⍪⍺)1⋄0,0⍪⍺}⊃⍵)∇1↓⍵}`~~

`{g←0 0⍴0⋄(≢g)⊣{1<⍵:g⌿⍨←g/⍨←×⍵|+/g⋄(⊃g)-←g⍪⍨←g,⍨←⍵}¨2,⍵}`

The graph is represented as a boolean adjacency matrix. Rows/columns are added and removed as necessary.

# Answer
> 3 votes
# Pyth, ~~88~~ ~~80~~ 75 characters

```
JYFHQI!H~Y]]lY)IqH1=Y+m+dlYY]UhlY)VYI&Hq%l@YNH1~J]N))=Ymf!}TJ@YkUlYY;-lYl{J

```

I'm done. Maybe someone else has some golfing tips.

`Y` is the adjacency list of the graph. For golfing reasons, I also keep a node in this list, even after the node got deleted (Otherwise I would have to update all indices). Each node has itself as neighbor. The list `J` keeps track of the deleted nodes.

I show the changes of the adjacency list on the example input `[0,1,0,1,0,1,3]`:

```
input 0: Y=[[0]]                                                         J=[]
input 1: Y=[[0,1],[0,1]] 0                                               J=[]
input 0: Y=[[0,1],[0,1],[2]]                                             J=[]
input 1: Y=[[0,1,3],[0,1,3],[2,3],[0,1,2,3]]                             J=[]
input 0: Y=[[0,1,3],[0,1,3],[2,3],[0,1,2,3],[4]]                         J=[]
input 1: Y=[[0,1,3,5],[0,1,3,5],[2,3,5],[0,1,2,3,5],[4,5],[0,1,2,3,4,5]] J=[]
input 3: Y=[[3,5],[3,5],[2,3,5],[2,3,5],[4,5],[2,3,4,5]]                 J=[0,1]

```

The algorithm then is pretty simple: Iterate over all inputs, if input==0: add a new node with itself as neighbour, if input==1: add a new node with all nodes as neighbors (also the deleted ones) and add this node to the adjacency list of all nodes, if input\>1: determine the nodes with #neighbor-1%input==0 and add them to `J`, in each case, update the neighbors of each node using `J`. At the end print the length of `Y` minus the length of (the set of) `J`.

```
JYFHQI!H~Y]]lY)IqH1=Y+m+dlYY]UhlY)VYI&Hq%l@YNH1~J]N))=Ymf!}TJ@YkUlYY;-lYl{J
JY                      set J=[]
  FHQ                   for H in: input()
I!H      )                if H==0:
   ~Y]]lY                   Y.append([len(Y)])
IqH1              )       if H==1:
    =Y+                     Y=                 +
       m+dlYY                 old nodes updated
             ]UhlY                              new node with all neighbors
VY                )       for N in range(len(Q)):
  I&Hq%l@YNH1    )          if H>0 and len(Y[N])%H==1:
             ~J]N             J.append(N) //this node gets deleted
=Ym           Y           Y=[           for k in Y]
   f!}TJ@YkUlY               k-filtered  //all items of J are removed
;                       end input for loop
-lYl{J                  print len(Y) - len(set(J))

```

## Usage

Just call the script and give as input `[0,1,0,1,0,1,3]` or some other test-case.

# Answer
> 2 votes
## Python 2, 296

```
s=input();e=[];n=[];c=0
for t in s:
    if t<2:e=e+[[]]if t==0 else [x+[c]for x in e]+[n[:]];n+=[c];c+=1
    else:
        M=zip(*[(i,n[i])for i,x in enumerate(e)if not len(x)%t])
        if M:e=[list(set(z)-set(M[1]))for j,z in enumerate(e)if j not in M[0]];n=list(set(n)-set(M[1]))
print len(n)

```

Each node is given a unique id and the neighbor ids of each node are recorded. When the directive is 0, an empty neighbor list is added for the new node. When the directive is 1, the ids of all existing nodes become the neighbor list for the new node, and all other neighbor lists are updated to include the new node id. For m\>1, nodes with neighbor lists that are a multiple of m are removed from the node list and all neighbor lists. Thanks to @Optimizer for catching a bug in an earlier version.

# Answer
> 2 votes
# NetLogo, 160

```
to f[t]foreach t[if ? = 0[crt 1]if ? = 1[crt 1[create-links-with other turtles]]if ? > 1[ask turtles with[count my-links mod ? = 0][die]]]show count turtles
end

```

The implementation is straightforward, reading each symbol and doing the appropriate action.

```
to f[t]
  foreach t [
    if ? = 0 [
      crt 1
    ]
    if ? = 1 [
      crt 1 [create-links-with other turtles]
    ]
    if ? > 1 [
      ask turtles with [count my-links mod ? = 0] [die]
    ]
  ]
  show count turtles
end

```

You can run from the command line as `f[0 0 1 1 0 0 1 1 2 5 7 0 1]`.

# Answer
> 2 votes
## Ruby ~~159~~ 157 (demo)

```
N=Struct.new:l
G=->c{n=[]
c.map{|m|m<1?n<<N.new([]):m<2?(w=N.new([])
n.map{|x|x.l<<w;w.l<<x}
n<<w):(n-=r=n.select{|x|x.l.size%m<1}
n.map{|x|x.l-=r})}
n.size}

```

This defines a function called `G` using stabby-lambda syntax. Use `G[[0, 1]]` to call it with commands `0` and `1`.

The implementation is pretty straightforward: there is a `Node` structure (called `N` above) which holds references to all linked nodes via the `l` property. `G` creates nodes as needed and manipulates their links. A readable version is available here.

# Answer
> 1 votes
# CJam, ~~99~~ 97 bytes

```
Lal~{I2<{_0={{If+z}2*));0+a+}{;Iaa}?}{_0=!!{{{_:+I%+}%z}2*));1+a+{{W=},z}2*);z_{);}{a}?}*}?}fI0=,

```

There is still a lot to be golfed in this. The algorithm is based on keeping track of the adjacency matrix, but representing the empty matrix without having to treat it specially is giving me headaches.

Test it here.

Input is a CJam-style array:

```
[0 0 1 1 0 0 1 1 2 5 7 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 8]

```

You can use this test harness to run all tests:

```
"[]
[5]
[0,0,0,11]
[0,1,0,1,0,1,3]
[0,0,0,1,1,1]
[0,0,1,1,0,0,1,1,2,5,7,0,1]
[0,0,1,1,1,1,5,1,4,3,1,0,0,0,1,2]
[0,0,1,1,0,0,1,1,5,2,3,0,0,1,1,0,0,1,1,3,4,0,0,1,1,2,1,1]
[0,0,1,1,0,0,1,1,2,5,7,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,8]"

","SerN/{
La\~{I2<{_0={{If+z}2*));0+a+}{;Iaa}?}{_0=!!{{{_:+I%+}%z}2*));1+a+{{W=},z}2*);z_{);}{a}?}*}?}fI0=,
N}/

```

# Answer
> 1 votes
## Python 2, 174

```
l=input()
g={}
n=0
for x in l:
 n+=1;g[n]=set()
 if x>1:h={i for i in g if len(g[i])%x};g={i:g[i]&h for i in set(g)&h}
 if x==1:
  for i in g:g[i]^={n};g[n]^={i}
print len(g)

```

This can probably still be golfed a lot.

I used a dictionary `g` to represent the graph. The nodes are labelled by numbers, and they map to the set of adjacent nodes. This means that each update of an edge needs to be executed at both of its endpoints.

Fresh node indices are created by counting up `n`. Each time, I create a new empty node `n`. For command `0`, it just remains. For command `1`, it's connected to each other node via `g[i]^={n};g[n]^={i}`; using xor make its so that the node isn't connected to itself. For commands \>1, it's immediately deleted.

The filtering of nodes whose degree is a multiple is done by first finding nodes that the remain (`h`), then `and`ing it with the list of nodes and the neighbors of each node.

Finally, the number of entries in the graph dictionary is the answer.

# Answer
> 0 votes
# Mathematica, 223 bytes

Wow, this turned out longer than I expected.

```
f=(g={};t=Append;l=Length;m=ListQ;h=Flatten;k=Position;o=If;(d=#;o[d==0,g=g~t~{},o[d==1,g=o[m@#,t[#,l@g+1],#]&/@g;g=t[g,h@k[g,_?m,1]],g=o[l@#~Mod~d==0,0,#]&/@g;p=h@k[g,0];(c=#;g=#~DeleteCases~c&/@g)&/@p]])&/@#;g~Count~_?m)&

```

Usage:

```
f@{0, 1, 0, 1, 0, 1, 3}

```

Here are the results from the test cases:

```
f /@ {
  {},
  {5},
  {0, 0, 0, 11},
  {0, 1, 0, 1, 0, 1, 3},
  {0, 0, 0, 1, 1, 1},
  {0, 0, 1, 1, 0, 0, 1, 1, 2, 5, 7, 0, 1},
  {0, 0, 1, 1, 1, 1, 5, 1, 4, 3, 1, 0, 0, 0, 1, 2},
  {0, 0, 1, 1, 0, 0, 1, 1, 5, 2, 3, 0, 0, 1, 1, 0, 0, 1, 1, 3, 4, 0, 0, 1, 1, 2, 1, 1},
  {0, 0, 1, 1, 0, 0, 1, 1, 2, 5, 7, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 8}
}

Out: {0, 0, 0, 4, 6, 6, 6, 8, 14}

```

Less golfed:

```
f = (
   a = #;
   g = {};
   Table[
    If[a[[n]] == 0,
     AppendTo[g, {}],
     If[a[[n]] == 1,
      g = If[ListQ@#, Append[#, Length@g + 1], #] & /@ g;
      g = Append[g, Flatten@Position[g, _?ListQ, 1]],
      If[a[[n]] > 1,
       g = If[Mod[Length@#, a[[n]]] == 0, 0, #] & /@ g;
       p = Flatten@Position[g, 0];
       (c = #; g = DeleteCases[#, c] & /@ g) & /@ p
       ]
      ]
     ],
    {n, Length@a}];
   Count[g, _?ListQ]
   ) &

```

The way this works is by representing the graph as list of "lists of neighbors".
For the **0** directive, I just append an empty list.
For the **1** directive, I append a list of all the previous nodes, and add the new node to all the previous nodes.
For a directive **\>1**, I removed the specified nodes and update the rest.

---
Tags: code-golf, graph-theory
---


title: How many towers can you see?

text:
# Question
Title: How many towers can you see?
This question is based on the number-placement puzzle Towers (also known as Skyscrapers), which you can play online. Your goal is to take a solution to the puzzle and determine the clues -- the numbers of towers visible along each row and column. This is code golf, so fewest bytes wins.

**How Towers works**

The solution to a Towers puzzle is a Latin square -- a `n*n` grid in which every row and column contains a permutation of the numbers `1` through `n`. An example for `n=5` is:

```
4 3 5 2 1
5 4 1 3 2
1 5 2 4 3
2 1 3 5 4
3 2 4 1 5

```

Each row and column is labelled with a clue at each end like:

```
       2 3 1 4 5
       v v v v v

 2 >   4 3 5 2 1   < 3
 1 >   5 4 1 3 2   < 4
 2 >   1 5 2 4 3   < 3
 3 >   2 1 3 5 4   < 2
 3 >   3 2 4 1 5   < 1

       ^ ^ ^ ^ ^
       2 2 2 2 1

```

Each clue is a number from `1` to `n` that tells you how many towers you "see" looking along the row/column from that direction, if the numbers are treated as towers with that height. Each tower blocks shorter towers behind it. In other words, the towers you can see are the ones that are taller than any tower before them.

For example, let's look at the first row.

```
 2 >   4 3 5 2 1   < 3

```

It has a clue of `2` from the left because you can see the `4` and the `5`. The `4` blocks the `3` from sight and the `5` blocks everything else. From the right, you can see `3` towers: `1`, `2`, and `5`.

**Program requirements**

Write a program or function that takes in the grid of numbers and outputs or prints the clues, going clockwise from the top left.

**Input**

An `n*n` Latin-square with `2<=n<=9`.

The format is flexible. You can use any data structure that represents a grid or list containing numbers or digit characters. You may require a separator between the rows or no separator at all. Some possibilities are a list, a list of lists, a matrix, a token-separated string like

```
43521 54132 15243 21354 32415,

```

or a string without spaces.

You're not given `n` as part of the input.

**Output**

Return or print the clues starting from the top left and going clockwise. So, first the upper clues reading rightwards, then the right clues reading downwards, then the lower clues reading leftwards, the the left clues reading upwards.

This would be `23145 34321 12222 33212` for the previous example

```
       2 3 1 4 5
       v v v v v

 2 >   4 3 5 2 1   < 3
 1 >   5 4 1 3 2   < 4
 2 >   1 5 2 4 3   < 3
 3 >   2 1 3 5 4   < 2
 3 >   3 2 4 1 5   < 1

       ^ ^ ^ ^ ^
       2 2 2 2 1

```

Just as for the input, you can use a list, string, or any ordered structure. The four "groups" can be separated or not, in a nested or a flat structure. But, the format must be the same for each group.

**Example test cases:**

(Your input/output format doesn't have to be the same as these.)

```
>> [[1 2] [2 1]]

[2 1]
[1 2]
[2 1]
[1 2]

>> [[3 1 2] [2 3 1] [1 2 3]]

[1 2 2]
[2 2 1]
[1 2 3]
[3 2 1]

>> [[4 3 5 2 1] [5 4 1 3 2] [1 5 2 4 3] [2 1 3 5 4] [3 2 4 1 5]]

[2 3 1 4 5]
[3 4 3 2 1]
[1 2 2 2 2]
[3 3 2 1 2]

>> [[2 6 4 1 3 7 5 8 9] [7 2 9 6 8 3 1 4 5] [5 9 7 4 6 1 8 2 3] [6 1 8 5 7 2 9 3 4] [1 5 3 9 2 6 4 7 8] [3 7 5 2 4 8 6 9 1] [8 3 1 7 9 4 2 5 6] [9 4 2 8 1 5 3 6 7] [4 8 6 3 5 9 7 1 2]]

[4 2 2 3 3 3 3 2 1]
[1 3 3 2 2 2 2 3 3]
[4 3 2 1 2 3 3 2 2]
[3 1 2 4 3 3 2 2 5]

```

For you convenience, here are the same test cases in a flat string format.

```
>> 1221

21
12
21
12

>> 312231123

122
221
123
321

>> 4352154132152432135432415

23145
34321
12222
33212

>> 264137589729683145597461823618572934153926478375248691831794256942815367486359712

422333321
133222233
432123322
312433225

```

# Answer
> 22 votes
## APL 19

```
≢¨∪/⌈\(⍉⍪⌽⍪⊖∘⌽∘⍉⍪⊖)

```

(golfed a bit more after ngn's suggestion, thanks)

Explanation:

```
(⍉⍪⌽⍪⊖∘⌽∘⍉⍪⊖)  rotates matrix 4 times appending results
⌈\ gets maximums for each row up to current column (example: 4 2 3 5 1 gives 4 4 4 5 5)
≢¨∪/ counts unique elements for each row

```

Try it on tryapl.org

# Answer
> 12 votes
# Python 2, 115 bytes

```
def T(m):o=[];exec'm=zip(*m)[::-1]\nfor r in m[::-1]:\n n=k=0\n for x in r:k+=x>n;n=max(x,n)\n o+=[k]\n'*4;return o

```

There's an awful lot of list flipping going on in there.

Takes input as a nested list (e.g. call with `T([[4,3,5,2,1],[5,4,1,3,2],[1,5,2,4,3],[2,1,3,5,4],[3,2,4,1,5]])`). Output is a single flat list.

Ungolfed:

```
def T(m):
 o=[]
 for _ in [0]*4:
  m=zip(*m)[::-1]
  for r in m[::-1]:
   n=k=0
   for x in r:k+=x>n;n=max(x,n)
   o+=[k]
 return o

```

Alternative 115:

```
def T(m):o=[];exec'm=zip(*m)[::-1];o+=[len(set([max(r[:i+1])for i in range(len(r))]))for r in m[::-1]];'*4;return o

```

I have no idea why this works with a list comprehension, but chucks a `NameError` with a set comprehension...

A bit too long, but if anyone's interested — yes, it's possible to get this down to a lambda!

```
T=lambda m:[len({max(r[:i+1])for i in range(len(r))})for k in[1,2,3,4]for r in eval("zip(*"*k+"m"+")[::-1]"*k)[::-1]]

```

---

# Pyth, 25 bytes

```
V4=Q_CQ~Yml{meS<dhkUd_Q)Y

```

Obligatory Pyth port.

Input the list via STDIN, e.g. `[[4, 3, 5, 2, 1], [5, 4, 1, 3, 2], [1, 5, 2, 4, 3], [2, 1, 3, 5, 4], [3, 2, 4, 1, 5]]`.

Try it online... is what I would say but unfortunately, for security reasons, the online interpreter disallows the use of eval on nested brackets. Try the workaround code `JcQ5V4=J_CJ~Yml{meS<dhkUd_J)Y` instead, and input as a flattened list like `[4, 3, 5, 2, 1, 5, 4, 1, 3, 2, 1, 5, 2, 4, 3, 2, 1, 3, 5, 4, 3, 2, 4, 1, 5]`.

*(Thanks to @isaacg who helped golf out a few bytes)*

# Answer
> 11 votes
# CJam, ~~29~~ 27 bytes

```
q~{z_{[{1$e>}*]_&,}%pW%}4*;

```

Input like

```
[[4 3 5 2 1] [5 4 1 3 2] [1 5 2 4 3] [2 1 3 5 4] [3 2 4 1 5]]

```

Output like

```
[2 3 1 4 5]
[3 4 3 2 1]
[1 2 2 2 2]
[3 3 2 1 2]

```

## How it works

The basic idea is to have the code work along rows and rotate the grid counter-clockwise 4 times. To count the towers, I'm raising each tower as far as it doesn't make a "visual difference" (i.e., don't change it if it's visible, or pull it up to the same height of the tower in front of it), and then I'm counting distinct heights.

```
q~                          "Read and evaluate the input.";
  {                    }4*  "Four times...";
   z                        "Transpose the grid.";
    _                       "Duplicate.";
     {            }%        "Map this block onto each row.";
      [       ]             "Collect into an array.";
       {    }*              "Fold this block onto the row.";
        1$                  "Copy the second-to-topmost element.":
          e>                "Take the maximum of the top two stack elements.";
                            "This fold replaces each element in the row by the
                             maximum of the numbers up to that element. So e.g.
                             [2 1 3 5 4] becomes [2 2 3 5 5].";
               _&,          "Count unique elements. This is how many towers you see.";
                    p       "Print array of results.";
                     W%     "Reverse the rows for the next run. Together with the transpose at
                             the start this rotates the grid counter-clockwise.";
                          ; "Get rid of the grid so that it isn't printed at the end.";

```

# Answer
> 5 votes
# APL, 44

```
{{+/~0∊¨↓(∘.>⍨⍵)≥∘.<⍨⍳⍴⍵}¨↓(⌽∘⍉⍪⊢⍪⊖∘⍉⍪⊖∘⌽)⍵}

```

Tested here.

# Answer
> 5 votes
# J, 35 chars

```
(+/@((>./={:)\)"2@(|.@|:^:(<4)@|:))

```

Example:

```
   t=.4 3 5 2 1,. 5 4 1 3 2,. 1 5 2 4 3,. 2 1 3 5 4,. 3 2 4 1 5
   (+/@((>./={:)\)"2@(|.@|:^:(<4)@|:)) t
2 3 1 4 5
3 4 3 2 1
1 2 2 2 2
3 3 2 1 2

```

Try it here.

# Answer
> 5 votes
# Haskell, 113

```
import Data.List
f(x:s)=1+f[r|r<-s,r>x]
f _=0
r=reverse
t=transpose
(?)=map
l s=[f?t s,(f.r)?s,r$(f.r)?t s,r$f?s]

```

# Answer
> 4 votes
# Mathematica, ~~230,120,116,113~~ 110 bytes

```
f=(t=Table;a=#;s=Length@a;t[v=t[c=m=0;t[h=a[[y,x]];If[h>m,c++;m=h],{y,s}];c,{x,s}];a=Thread@Reverse@a;v,{4}])&

```

Usage:

```
f[{
  {4, 3, 5, 2, 1},
  {5, 4, 1, 3, 2},
  {1, 5, 2, 4, 3},
  {2, 1, 3, 5, 4},
  {3, 2, 4, 1, 5}
}]

{{2, 3, 1, 4, 5}, {3, 4, 3, 2, 1}, {1, 2, 2, 2, 2}, {3, 3, 2, 1, 2}}

```

# Answer
> 4 votes
## JavaScript, ~~335~~ ~~264~~ ~~256~~ 213

```
T=I=>((n,O)=>(S=i=>i--&&O.push([])+S(i)+(R=(j,a,x)=>j--&&R(j,0,0)+(C=k=>k--&&((!(a>>(b=I[(F=[f=>n-k-1,f=>j,f=>k,f=>n-j-1])[i]()][F[i+1&3]()])))&&++x+(a=1<<b))+C(k))(n)+O[i].push(x))(n,0,0))(4)&&O)(I.length,[],[])

```

Evaluate in the browser's JavaScript console (I used Firefox 34.0, doesn't seem to work in Chrome 39??) Test with:

```
JSON.stringify(T([[4, 3, 5, 2, 1], [5, 4, 1, 3, 2], [1, 5, 2, 4, 3], [2, 1, 3, 5, 4], [3, 2, 4, 1, 5]]));

```

Here's the current incarnation of the ungolfed code - it's getting harder to follow:

```
function countVisibleTowers(input) {
  return ((n, out) =>
      (sideRecurse = i =>
          i-- &&
          out.push([]) +
          sideRecurse(i) +
          (rowRecurse = (j, a, x) =>
              j-- &&
              rowRecurse(j, 0, 0) +
              (columnRecurse = k =>
                  k-- &&
                  ((!(a >> (b = input[
                                        (offsetFtn = [
                                            f => n - k - 1,   // col negative
                                            f => j,           // row positive
                                            f => k,           // col positive
                                            f => n - j - 1    // row negative
                                        ])[i]()
                                     ]
                                     [
                                        offsetFtn[i + 1 & 3]()
                                     ]))) &&
                  ++x +
                  (a = 1 << b)) +
                  columnRecurse(k)
              )(n) +
              out[i].push(x)
          )(n, 0, 0)
      )(4) && out
  )(input.length, [], [])
}

```

I intentionally didn't look at any of the other answers, I wanted to see if I could work something out myself. My approach was to flatten the input arrays to a one-dimensional array and precompute offsets to the rows from all four directions. Then I used shift right to test whether the next tower was falsy and if it was, then increment the counter for each row.

I am hoping there is lots of ways to improve this, perhaps not precalculate the offsets, but rather use some sort of overflow/modulo on the 1D input array? And perhaps combine my loops, get more functional, deduplicate.

**Any suggestions would be appreciated!**

**Update #1** : Progress, we have the technology! I was able to get rid of the precalculated offsets and do them inline with ternary operators strung together. Also was able to get rid of my if statement and convert the for loops into whiles.

**Update #2** : This is pretty frustrating; no pizza party for me. I figured going functional and using recursion would shave off many bytes, but my first few tries ended up being larger by as much as 100 characters! In desperation, I went whole-hog on using ES6 fat arrow functions to really pare it down. Then I took to replacing boolean operators with arithmetic ones and removing parens, semi-colons and spaces whereever I could. I even quit declaring my vars and polluted the global namespace with my local symbols. Dirty, dirty. After all that effort, I beat my Update #1 score by a whopping 8 characters, down to 256. Blargh!

If I applied the same ruthless optimizations and ES6 tricks to my Update #1 function, I'd beat this score by a mile. I may do an Update #3 just to see what that would look like.

**Update #3** : Turns out the fat arrow recursive approach had lots more life in it, I just needed to work with the 2 dimensional input directly rather than flattening it and get better about leveraging the closure scopes. I rewrote the inner array offset calculations twice and got the same score, so this approach may be close to minned out!

# Answer
> 3 votes
# Java, *only* ~~352~~ ~~350~~ 325 bytes...

```
class S{public static void main(String[]a){int n=a.length,i=0,j,k,b,c;int[][]d=new int[n][n];for(;i<n;i++)for(j=0;j<n;)d[i][j]=a[i].charAt(j++);for(i=0;i<4;i++){int[][]e=new int[n][n];for(k=0;k<n;k++)for(j=0;j<n;)e[n-j-1][k]=d[k][j++];d=e;for(j=n;j-->(k=c=b=0);System.out.print(c))for(;k<n;k++)b=d[j][k]>b?d[j][k]+0*c++:b;}}}

```

Input like `43521 54132 15243 21354 32415`

Output like: `23145343211222233212`

Indented:

```
class S{
    public static void main(String[]a){
        int n=a.length,i=0,j,k,b,c;
        int[][]d=new int[n][n];
        for(;i<n;i++)
            for(j=0;j<n;)d[i][j]=a[i].charAt(j++);
        for(i=0;i<4;i++){
            int[][]e=new int[n][n];
            for(k=0;k<n;k++)
                for(j=0;j<n;)e[n-j-1][k]=d[k][j++];
            d=e;
            for(j=n;j-->(k=c=b=0);System.out.print(c))
                for(;k<n;k++)b=d[j][k]>b?d[j][k]+0*c++:b;
        }
    }
}

```

***Any tips would be greatly appreciated!***

# Answer
> 1 votes
# Python 2 - 204 bytes

```
def f(l):n=len(l);k=[l[c]for c in range(n)if l[c]>([0]+list(l))[c]];return f(k)if k!=l else n
r=lambda m:(l[::-1]for l in m)
m=input();z=zip(*m);n=0
for t in z,r(m),r(z),m:print map(f,t)[::1-(n>1)*2];n+=1

```

This is probably a really poor golf. I thought the problem was interesting, so I decided to tackle it without looking at anyone else's solution. As I type this sentence I have yet to look at the answers on this question. I wouldn't be surprised if someone else has already done a shorter Python program ;)

**I/O Example**

```
$ ./towers.py <<< '[[4,3,5,2,1],[5,4,1,3,2],[1,5,2,4,3],[2,1,3,5,4],[3,2,4,1,5]]'
[2, 3, 1, 4, 5]
[3, 4, 3, 2, 1]
[1, 2, 2, 2, 2]
[3, 3, 2, 1, 2]

```

You may optionally include whitespace in the input. Pretty much anywhere, honestly. So long as you can `eval()` it, it'll work.

**Explanation**

The only interesting part of this program is the first line. It defines a function `f(l)` that tells you how many towers can be seen in a row, and the rest of the program is just applying that function to every possible position.

When called, it finds the length of `l` and saves it in a variable `n`. Then it creates a new variable `k` with this pretty monstrous list comprehension:

```
[l[c]for c in range(n)if l[c]>([0]+list(l))[c]]

```

It's not too bad when you break it down. Since `n==len(l)`, everything before the `if` just represents `l`. However, using `if` we can remove some elements from the list. We construct a list with `([0]+list(l))`, which is just "`l` with a `0` added to the beginning" (ignore the call to `list()`, that's only there because sometimes `l` is a generator and we need to make sure it's actually a list here). `l[c]` is only put into the final list if it's greater than `([0]+list(l))[c]`. This does two things:

* Since there's a new element at the beginning of the list, the index of each `l[c]` becomes `c+1`. We're effectively comparing each element to the element to the left of it. If it's greater, it's visible. Otherwise it's hidden and removed from the list.
* The first tower is always visible because there's nothing that can block it. Because we put 0 at the beginning, the first tower is always greater. (If we didn't do this `[0]+` nonsense and just compared `l[c]` to `l[c-1]`, Python would compare the first tower to the last one (you can index into a list from the end with `-1`, `-2`, etc.), so if the last tower was taller than the first one we'd get the wrong result.

When all is said and done, `l` contains some number of towers and `k` contains each one of those that isn't shorter than its immediate neighbour to the left. If none of them were (e.g. for `f([1,2,3,4,5])`), then `l == k`. We know there's nothing left to do and return `n` (the length of the list). If `l != k`, that means at least one of the towers was removed this time around and there may be more to do. So, we return `f(k)`. God, I love recursion. Interestingly, `f` always recurses one level deeper than is strictly "necessary". When the list that will be returned is generated, the function has no way of knowing that at first.

When I started writing this explanation, this program was 223 bytes long. While explaining things I realized that there were ways to save characters, so I'm glad I typed this up! The biggest example is that `f(l)` was originally implemented as an infinite loop that was broken out of when the computation was done, before I realized recursion would work. It just goes to show that the first solution you think of won't always be the best. :)

# Answer
> 0 votes
# Matlab, (123)(119)

```
function r=m(h);p=[h rot90(h) rot90(h,2) rot90(h,3)];for i=2:size(p) p(i,:)=max(p(i,:),p(i-1,:));end;r=sum(diff(p)>0)+1

```

used like this:

```
m([
 4     3     5     2     1;
 5     4     1     3     2;
 1     5     2     4     3;
 2     1     3     5     4;
 3     2     4     1     5])

 [2 3 1 4 5 3 4 3 2 1 1 2 2 2 2 3 3 2 1 2]

```

# C#, down to 354...

Different approach than TheBestOne used.

```
using System;
using System.Linq;

class A
{
    static void Main(string[] h)
    {
        int m = (int)Math.Sqrt(h[0].Length),k=0;
        var x = h[0].Select(c => c - 48);
        var s = Enumerable.Range(0, m);
        for (; k < 4; k++)
        {
            (k%2 == 0 ? s : s.Reverse())
                .Select(j =>
                        (k > 0 && k < 3 ? x.Reverse() : x).Where((c, i) => (k % 2 == 0 ? i % m : i / m) == j)
                                                          .Aggregate(0, (p, c) =>
                                                                        c > p%10
                                                                            ? c + 10 + p/10*10
                                                                            : p, c => c/10))
                .ToList()
                .ForEach(Console.Write);
        }
    }
}

```

---
Tags: code-golf, grid
---


title: Solve the BattleBlock Theater Puzzle

text:
# Question
Title: Solve the BattleBlock Theater Puzzle
The game BattleBlock Theater occasionally contains a puzzle which is a generalised version of Lights Out. You've got three adjacent blocks, each of which indicates a level between 1 and 4 inclusive with bars, e.g.:

```
|
||||
||

```

If you touch a block, then that block as well as any adjacent block will increment its level (wrapping back from 4 to 1). The puzzle is solved when all three blocks show the same level (it doesn't matter which level). Since, the order you touch the blocks in doesn't matter, we denote a solution by how often each block is touched. The optimal solution for the above input would be `201`:

```
|    --> || --> |||     |||
||||     |      ||      |||
||       ||     ||  --> |||

```

The game very easily generalises any number of blocks, although for some numbers, not all configurations are solvable.

## The Challenge

Given a sequence of block levels, return how often each block needs to be touched to solve the puzzle. E.g. the above example would be given as `142` and could yield `201` as a result. If there is no solution, return some *consistent* output of your choice, which is distinguishable from all potential solutions, e.g. `-1` or an empty string.

You may write a function or program, take input via STDIN, command-line argument or function argument, in any convenient list or string format, and similarly output via a return value or by printing to STDOUT.

Your code should return correct results for all test cases within a minute on a reasonable machine. (This is not a completely strict limit, so if your solution takes a minute and ten seconds, that's fine, but if it takes 3 minutes, it isn't. A good algorithm will easily solve them in seconds.)

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

## Examples

Solutions are not unique, so you may get different results.

```
Input                          Output

1                              0
11                             00
12                             No solution
142                            201
434                            101
222                            000
4113                           0230
32444                          No solution
23432                          10301
421232                         212301
3442223221221422412334         0330130000130202221111
22231244334432131322442        No solution
111111111111111111111222       000000000000000000000030
111111111111111111111234       100100100100100100100133
412224131444114441432434       113013201011001101012133

```

As far as I know, there are exactly 4 solutions for each input where the number of blocks is 0 mod 3, or 1 mod 3, and there are 0 or 16 solutions where it is 2 mod 3.

# Answer
# Python 2, 115 bytes

```
n=input()
for F in range(4):
 t=[F];b=0;exec"x=(-n[b]-sum(t[-2:]))%4;t+=x,;b+=1;"*len(n)
 if x<1:print t[:-1];break

```

This is the golfed version of the program I wrote while discussing the problem with Martin.

Input is a list via STDIN. Output is a list representing the last solution found if there is a solution, or zero if there isn't. For example:

```
>>>
[1, 4, 2]
[2, 1, 1]
>>>
[1, 2]
0
>>>
map(int,"3442223221221422412334")
[2, 3, 3, 2, 1, 3, 2, 0, 0, 2, 1, 3, 2, 2, 0, 0, 2, 2, 3, 1, 1, 3]

```

---

# Pyth, ~~32~~ 29 bytes

```
V4J]NVQaJ%_+s>J_2@QN4)I!eJPJB

```

The obligatory port. Thanks to @Jakube for the 3 byte saving.

Input method is the same as above, try it online.

---

## Explanation (long and full of logic!)

First, two basic observations:

* **Observation 1:** It doesn't matter which order you touch the blocks
* **Observation 2:** If you touch a block 4 times, it's equivalent to touching it once

In other words, if there is a solution then there is a solution where the number of touches is between 0 and 3 inclusive.

Since modulo 4 is so nice, let's do that with the blocks too. For the rest of this explanation, block level 0 is equivalent to block level 4.

Now let's denote `a[k]` to be the current level of block `k` and `x[k]` to be the number of times we touch block `k` in a solution. Also let `n` be the total number of blocks. As @Jakube has noted, a solution must satisfy:

```
  a[0]   + x[0] + x[1]
= a[1]   + x[0] + x[1] + x[2]
= a[2]          + x[1] + x[2] + x[3]
= a[3]                 + x[2] + x[3] + x[4]
...
= a[n-1]                                     ...  + x[n-2] + x[n-1] + x[n]
= a[n]                                       ...           + x[n-1] + x[n]
= C

```

where `C` is the final level all blocks end up on, between 0 and 3 inclusive (remember we're treating level 4 as level 0) and all equations above are really congruences modulo 4.

Now here's the fun part:

* **Observation 3**: If a solution exists, a solution exists for any final block level `0 <= C <= 3`.

There are three cases based on the number of blocks modulo 3. The explanation for each of them is the same — for any number of blocks, there exists a subset of blocks which, if you touch each of them once, increases **all** block levels by exactly 1.

```
0 mod 3 (touch every third block starting from the second):
    .X. / .X. / .X.

1 mod 3 (touch every third block starting from the first):
    X. / .X. / .X. / .X

2 mod 3 (touch every third block starting from either the first or second):
    X. / .X. / .X. / .X.
    .X. / .X. / .X. / .X

```

This explains why there are 4 solutions for `0 mod 3` and `1 mod 3`, and usually 16 solutions for `2 mod 3`. If you have a solution already, touching the blocks as above gives another solution which ends up at a higher block level (wrapping around).

So what does this mean? We can pick any final block level `C` we want! Let's pick `C = 0`, because this saves on bytes.

Now our equations become:

```
0 = a[0] + x[0] + x[1]
0 = a[1] + x[0] + x[1] + x[2]
0 = a[2] + x[1] + x[2] + x[3]
0 = a[3] + x[2] + x[3] + x[4]
...
0 = a[n-1] + x[n-2] + x[n-1] + x[n]
0 = a[n] + x[n-1] + x[n]

```

And rearrange:

```
x[1] = -a[0] - x[0]
x[2] = -a[1] - x[0] - x[1]
x[3] = -a[2] - x[1] - x[2]
x[4] = -a[3] - x[2] - x[3]
...
x[n] = a[n-1] - x[n-2] - x[n-1]
x[n] = a[n] - x[n-1]

```

So what we can see is, if we have `x[0]`, then we can use all the equations except the last to find out every other `x[k]`. The last equation is an additional condition we must check.

This gives us an algorithm:

* Try all values for `x[0]`
* Use the above equations to work out all of the other `x[k]`
* Check if the last condition is satisfied. If so, save the solution.

That gives the solution above.

So why do we sometimes get no solution for `2 mod 3`? Let's take a look at these two patterns again:

```
X. / .X. / .X. / .X.
.X. / .X. / .X. / .X

```

Now consider the equations at those positions, i.e. for the first one:

```
0 = a[0] + x[0] + x[1]
0 = a[3] + x[2] + x[3] + x[4]
0 = a[6] + x[5] + x[6] + x[7]
0 = a[9] + x[8] + x[9] + x[10]

```

Add them up:

```
0 = (a[0] + a[3] + a[6] + a[9]) + (x[0] + x[1] + ... + x[9] + x[10])

```

For the second one:

```
0 = a[1] + x[0] + x[1] + x[2]
0 = a[4] + x[3] + x[4] + x[5]
0 = a[7] + x[6] + x[7] + x[8]
0 = a[10] + x[9] + x[10]

```

Add them up again:

```
0 = (a[1] + a[4] + a[7] + a[10]) + (x[0] + x[1] + ... + x[9] + x[10])

```

So if `(a[1] + a[4] + a[7] + a[10])` and `(a[0] + a[3] + a[6] + a[9])` are not equal, then we have no solution. But if they are equal, then we get 16 solutions. This was for the `n = 11` case, but of course this generalises to any number that is `2 mod 3` — take the sum of every third element starting from the second, and compare to the sum of every third element starting from the first.

Now finally, is it possible to figure out what `x[0]` has to be instead of trying all of the possibilities? After all, since we restricted our target level `C` to be 0, there is only one `x[0]` which gives a solution in the `0 mod 3` or `1 mod 3` case (as `4 solutions / 4 final levels = 1 solution for a specific final level`).

The answer is... yes! We can do this for `0 mod 3`:

```
 .X..X
.X..X.

```

Which translates to:

```
0 = a[2] + x[1] + x[2] + x[3]   -> 0 = (a[2] + a[5]) + (x[1] + ... + x[5])
0 = a[5] + x[4] + x[5]          /

0 = a[1] + x[0] + x[1] + x[2]   -> 0 = (a[1] + a[4]) + (x[0] + x[1] + ... + x[5])
0 = a[4] + x[3] + x[4] + x[5]   /

```

Subtracting gives:

```
x[1] = (a[2] + a[5]) - (a[1] + a[4])

```

Similarly for `1 mod 3` we can do this pattern:

```
 .X..X.
X..X..X

```

Which gives:

```
x[0] = (a[2] + a[5]) - (a[0] + a[3] + a[6])

```

These of course generalise by extending the indices by increments of 3.

For `2 mod 3`, since we have two subsets which cover every block, we can actually pick any `x[0]`. In fact, this is true for `x[0], x[1], x[3], x[4], x[6], x[7], ...` (basically any index not congruent to `2 mod 3`, as they are not covered by either subset).

So we have a way of picking an `x[0]` instead of trying all possibilities...

... but the bad news is that this doesn't save on bytes (124 bytes):

```
def f(n):s=[];L=len(n);B=sum(n[~-L%3::3])-sum(n[-~L%3::3]);x=A=0;exec"s+=B%4,;A,B=B,-n[x]-A-B;x+=1;"*L*(L%3<2or B<1);print s

```
> 10 votes

# Answer
# Pyth, ~~72~~ ~~76~~ ~~73~~ ~~66~~ ~~39~~ 38 character

```
Ph+f!eTmu+G%+&H@G_3-@QH@QhH4UtQd^UT2]Y

```

**edit 4:** Realized, that the calculations `Q[N]-Q[N+1]+solution[-3]` and `Q[-2]-Q[-1]+solution[-3]` are ident. Therefore I overcalculate the solution by 1, and filter the solutions, where the last entry is 0. Then I pop the last entry. Luckily the special cases doesn't need an extra treatment with this approach. -27 character

**edit 3:** Applying some golfing tricks from FryAmTheEggman: -7 character

**edit 2:** Using filter, reduce and map: -3 character

**edit 1:**In my first version I didn't printed anything, if there was no solution. I don't think that's allowed, therefore +4 character.

Expects a list of integers as input `[1,4,2]` and outputs a valid solution `[2,0,1]` if there is one, otherwise an empty list `[]`.

## Explanation:

Let `Q` be the list of 5 levels and `Y` the list of the solution. The following equations have to hold:

```
  Q0 + Y0 + Y1
= Q1 + Y0 + Y1 + Y2
= Q2      + Y1 + Y2 + Y3
= Q3           + Y2 + Y3 + Y4
= Q4                + Y3 + Y4

```

Therefore if we use any `Y0` and `Y1`, we can calculate `Y2`, `Y3` and `Y4` in the following way.

```
Y2 = (Q0 - Q1     ) mod 4
Y3 = (Q1 - Q2 + Y0) mod 4
Y4 = (Q2 - Q3 + Y1) mod 4

```

Than all levels exept the last one are equal (because we didn't used the equation `= Q4 + Y3 + Y4`. To check, if this last one is also equal to the other levels, we can simply check if `(Q3 - Q4 + Y2) mod 4 == 0`. Notice, that the left part would be the value `Y5`. If I calculate the 6th part of the solution, I can simply check, if it is zero.

In my approach I simply iterate over all possible starts (`[0,0]`, to `[3,3]`), and calculate length(input)-1 more entries and filter all solutions that end with a zero.

```
mu+G%+&H@G_3-@QH@QhH4UtQd^UT2   generates all possible solutions

```

it's basically the following:

```
G = start value           //one of "^UT2", [0,0], [0,1], ..., [9,9]
                          //up to [3,3] would be enough but cost 1 char more
for H in range(len(Q)-1): //"UtQ"
   G+=[(H and G[-3])+(Q(H)-Q(H+1))%4] //"+G%+&H@G_3-@QH@QhH4"
   //H and G[-3] is 0, when H is empty, else G[-3]

```

then I filter these possible solutions for valid ones:

```
f!eT //only use solutions, which end in 0

```

to this list of solutions I append an empty list, so that it has at least one item in it

```
 +....]Y

```

and take the first solution `h`, pop the last element `p` and print it

```
 Ph

```

Notice, that this also works, if there is only one block. In my approach I get the starting position \[0,0\] and doesn't extend it. Since the last entry is 0, it prints the solution \[0\].

The second special case (2 blocks) isn't that special after all. Not sure, why I overcomplicated things earlier.
> 4 votes

# Answer
# Ruby, ~~320~~ 313 chars

```
m=gets.chop.chars.map{|x|x.to_i-1}
a=m.map{0}
t=->n{m[n]+=1
m[n-1]+=1if n>0
m[n+1]+=1if n<m.size-1
m.map!{|x|x%4}
a[n]=(a[n]+1)%4}
t[0]until m[0]==1
(2...m.size).map{|n|t[n]until m[n-1]==1}
r=0
while m.uniq.size>1&&m[-1]!=1
(0...m.size).each_with_index{|n,i|([1,3,0][i%3]).times{t[n]}}
(r+=1)>5&&exit
end
$><<a*''

```

Can definitely be golfed more. Outputs nothing for unsolvable puzzles.

Ungolfed version:

```
#!/usr/bin/ruby

nums = gets.chomp.chars.map {|x| x.to_i-1 }
touches = nums.map {0}

# our goal: make all the numbers 1
# utility function
touch = ->n {
    nums[n] += 1
    nums[n-1] += 1 if n > 0
    nums[n+1] += 1 if n < (nums.length-1)
    nums.map! {|x| x % 4 }
    touches[n] = (touches[n] + 1) % 4
}

# first, start with the very first number
touch[0] until nums[0] == 1

# then, go from index 2 to the end to make the previous index right
(2...nums.length).each {|n|
    touch[n] until nums[n-1] == 1
}

iters = 0
if nums.uniq.length != 1
    # I have no idea why this works
    while nums[-1] != 1
        (0...nums.length).each_with_index {|n, i|
            ([1, 3, 0][i % 3]).times { touch[n] }
        }
        if (iters += 1) > 5
            puts -1
            exit
        end
    end
end

puts touches * ''

```

Okay, this one was fun. Here's the basic algorithm, with `{n}` representing n "touch"es on the number above the `n`, as demonstrated on one of the examples:

```
we want each number to be a 1
first make the first number a 1
3442223221221422412334
2}
1242223221221422412334
 {3} now keep "touch"ing until the number to the left is a 1
1131223221221422412334
  {2}
1113423221221422412334
   {2}
1111243221221422412334
... (repeat this procedure)
1111111111111111111110

```

I got stumped for a bit here. How can I turn the `111...1110` into a series of same numbers? So I compared my solution and the correct solution (note: the "touch" counts all are one greater than they should be because the input is 1-indexed, while the output is 0-indexed):

```
3033233103233301320210
0330130000130202221111

```

I noticed that each number was one away from the correct one `mod 4`, so I marked them with `+`s, `-`s, and `=`s:

```
3033233103233301320210 original program output
+-=+-=+-=+-=+-=+-=+-=+ amount to modify by (+1, -1, or 0 (=))
4334534404534602621511 result (the correct answer)

0330130000130202221111 (the original solution, digits equal to result mod 4)

```

That worked for a while, until I noticed that sometimes the final result was `111...11112` or `11...1113` as well! Fortunately, repeatedly applying the magical formula that makes no sense but works also sorted these out.

So, there you have it. A program that starts out making sense, but degrades into more and more ugly hackiness as it goes. Quite typical for a code golf solution, I think. :)
> 3 votes

# Answer
# Python 2, ~~294,289,285,281~~ 273 bytes

```
n=input();l=len(n);s=[0]*l
for i in range(2,l):
 a=(n[i-2]-n[i-1])%4;s[i]+=a;n[i-1]+=a;n[i]+=a
 if i+1<l:n[i+1]+=a
 n=[a%4for a in n]
if l%3>1 and n!=[n[0]]*l:print"x"
else:
 for i in range(l%3,l-1,3):s[i]+=(n[l-1]-n[l-2])%4
 m=min(s);s=[(a-m)%4 for a in s];print s

```

**DEMO**

I'm sure this can be golfed further..

Here are the results from the test cases:

```
[1]
-> [0]

[1,1]
-> [0, 0]

[1,2]
-> x

[1,4,2]
-> [2, 0, 1]

[4,3,4]
-> [1, 0, 1]

[2,2,2]
-> [0, 0, 0]

[4,1,1,3]
-> [0, 2, 3, 0]

[3,2,4,4,4]
-> x

[2,3,4,3,2]
-> [0, 0, 3, 3, 1]

[4,2,1,2,3,2]
-> [2, 0, 2, 3, 3, 1]

[3,4,4,2,2,2,3,2,2,1,2,2,1,4,2,2,4,1,2,3,3,4]
-> [0, 3, 3, 0, 1, 3, 0, 0, 0, 0, 1, 3, 0, 2, 0, 2, 2, 2, 1, 1, 1, 1]

[2,2,2,3,1,2,4,4,3,3,4,4,3,2,1,3,1,3,2,2,4,4,2]
-> x

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2]
-> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0]

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,3,4]
-> [1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 3, 3]

[4,1,2,2,2,4,1,3,1,4,4,4,1,1,4,4,4,1,4,3,2,4,3,4]
-> [1, 0, 3, 0, 0, 3, 2, 3, 1, 0, 0, 1, 0, 3, 1, 1, 3, 1, 0, 0, 2, 1, 2, 3]

```

The algorithm first makes sure that the values of all blocks except the last block are the same (by iterating through and adding to the "touch counts" of all blocks except the first 2). Then, if the number of blocks allows for it (`(num_of_blocks - 1) % 3 != 1`), goes back and makes sure the values of the rest of the blocks match the last block. Prints `x` if there is no solution.
> 2 votes

---
Tags: code-golf, puzzle-solver
---


# Question
Title: Solving Three Open Problems with a Halting Oracle
You are given the functions: h1(f,\*args) and h2(f,\*args)

Both are methods which are already defined for you (here the asterisk indicates a variable number of arguments)

f is a function, \*args is a list of parameters to be passed to that function

h1 returns a boolean value: True if the function f ever halts when called on \*args and False if it doesn't (assuming the machine running it has infinite time and memory and that the interpreter/compiler for the language you're writing in knows how to handle infinite time and memory).

If f(\*args) would ever make a call to h1 or h2, h1 throws an exception

h2 behaves exactly like h1 except that if f makes calls to h1, then h2 will not throw an exception

In as few characters as possible, write a program which takes no input and should output:

```
The Collatz Conjecture is {True/False}
Goldbach's Conjecture is {True/False}
The Twin Primes Conjecture is {True/False}

```

based on the validity of each of those conjectures.

Here are wikipedia links explaining each of the conjectures:

http://en.wikipedia.org/wiki/Collatz\_conjecture

http://en.wikipedia.org/wiki/Goldbach%27s\_conjecture

http://en.wikipedia.org/wiki/Twin\_prime

You may assume any big integer library in whatever language you choose to use will successfully represent arbitrary large integers. In other words, we'll assume any language/library which is capable of expressing `3**(3**10)` is also capable of expressing `3**(3**(3**10))` on a sufficiently beefy machine.

Obviously since it's impossible to run your program, please provide an explanation of how it works along with the code

# Answer
# J, 207

```
(('The Collatz';'Goldbach''s';'The Twin Primes'),.<'Conjecture is'),.((>:^:((((-:`>:@*&3)^:(~:&1))^:_)&f)^:_ g 2)((+&2)^:(+./@1&p:@(-p:@_1&p:))^:_ f 4)(>:^:((4&p:)^:(2&~:&(-~4&p:))&f)^:_ g 3){'True':'False')

```

I chose to use `f` and `g` in place of `h1` and `h2`, as according to the bounty; two additional lines with **10** total characters prior is sufficient to switch: `f=:h1`,`g=:h2`.

And the actual logic:

### Collatz

```
>:^:((((-:`>:@*&3)^:(~:&1))^:_)&f)^:_ g 2

```

`((-:`>:@*&3)^:(~:&1))^:_` is the meat of it; it's essentially a loop that does `while (x != 1) x = collatz(x)`. If we call that sentence `reduce`:

```
>:^:(reduce&f)^:_ g 2

```

`reduce&f` is meant to be a monadic verb (see end), where `reduce&f n` is true iff `reduce(n)` halts. The other loop-y bits, `>:^:()^:_`, are essentially an infinite loop (`>:` is increment, `^:` can be used as a conditional and an iterator) which breaks upon encountering a Collatz reduction that does not halt. Finally the `g` is called to see if the infinite loop ever terminates.

### Goldbach

```
(+&2)^:(+./@1&p:@(-p:@_1&p:))^:_ f 4

```

The same logic, for the most part, the obvious difference being the core calculation is now `+./@1&p:@(-p:@_1&p:)`. `-p:@_1&p:` calculates the difference between a number and all the primes less than that number, `1&p:` is an `isPrime` function, and `+./` is logical OR. Hence, if the difference between a number and any prime less than that number is also a prime, then the Goldbach conjecture is satisfied, and the infinite loop continues on. Again, `f` is used in a final test of whether said infinite loop is truly infinite.

### Twin Primes

```
>:^:((4&p:)^:(2&~:@(-~4&p:))&f)^:_ g 3

```

Same as above, excepting `(4&p:)^:(2&~:@(-~4&p:))`. `4&p:` returns the next largest prime after a given number. `-~4&p:` returns the difference between a number and the next largest prime after it. `2&~:` is `!= 2`. So the innermost loop is analogous to `while (nextPrimeAfter(p) - p != 2) p = nextPrimeAfter(p)`.

### Notes

There may be syntactical errors, since I haven't tested with dummy `f` and `g` yet. Also, I assumed that `f` and `g` would take some sort of form that can be composed with a verb on the left and a noun on the right, which I'm not completely sure adheres to the J grammar in any way. They're inherently higher order functions, and I'm too tired to look up a proper construction as adverbs/conjunctions/what-have-you at the moment, if there even is such an appropriate construct.

I didn't really use proper string concatenation, and instead opted to leave individual strings boxed. The output (assuming all else is correct) would therefore be a 3 column table, with the left column being "The Collatz", etc., the middle column being "Conjecture is", and the right column "True"/"False".

I'm also pretty sure J doesn't convert integers to arbitrary precision by default, and the crucial prime number utility function `p:` does not have an arbitrarily large domain. On the other hand, given that J does support a standard arbitrary precision number type, I'm not sure how much effort it'd take to get this code up to par.
> 4 votes

# Answer
# Haskell, 242

```
p n=and[rem n r>0|r<-[2..n-1]]
c 1=1
c n|odd n=c$3*n+1|0<1=c$div n 2
s!f=putStr(s++" Conjecture is ")>>print(not$h2$all(h1.f)[4..])
main=do"The Collatz"!c;"Goldbach's"! \n->or[p$n-r|r<-[2..n-2],p r];"The Twin Primes"! \n->or[p$r+2|r<-[n..],p r]

```

because in Haskell variables can contain not only values, but computations (this is called laziness) I let myself make `h1, h2` take a single argument and return weather or not it's evaluation will halt.

somewhat ungolfed code:

```
h1 = undefined
h2 = undefined

prime n=and[rem n r>0|r<-[2..n-1]]
collatz 1=1
collatz n
    |odd n=collatz (3*n+1)
    |0<1  =collatz (div n 2)

s!f=do
    putStr (s++" Conjecture is ")
    print$not$h2$all(h1.f)[4..]

main=do
    "The Collatz"!c                                         --collatz
    "Goldbach's"! \n->or[prime (n-r)|r<-[2..n-2],prime r]   --goldbach
    "The Twin Primes"! \n->or[prime (r+2)|r<-[n..],prime r] --twin primes

```

a bit of explanation:

when `all` is applied to an infinite list, it will halt iff one of the elements of the list is `False`, due to laziness (short-circuiting, for all non-Haskell folks out there). we use this to compute the collatz conjecture and the twin primes conjecture.

`!` packages this trickery along with printing. the result is `True` when `f` terminates on all the numbers `4..`. (this doesn't matter for the collatz conjecture or the twin primes conjecture, because we already know they are true for such small numbers).

the code for the collatz conjecture is `"The Collatz"!c`. it prints "The Collatz Conjecture is " and the result, which is weather `c` terminates on all numbers `4..`.

the code for the goldbach conjecture is `"Goldbach's"! \n->or[p$n-r|r<-[2..n-2],p r]`. `\n->or[p$n-r|r<-[2..],p r,r<n+1]` is a function which given `n`, if it is a sum of two primes, returns `True`, but otherwise loops indefinitely. thus, if it halts for every `4..` goldbach's conjecture is true.

the code for the twin primes conjecture is `"The Twin Primes"! \n->or[p$r+2|r<-[n..],p r]`. `\n->or[p$r+2|r<-[n..],p r]` is a function which given `n`, if there are twin primes greater than `n`, returns True, but otherwise loops indefinitely. thus, if it halts for every `4..` the twin prime conjecture is true.
> 7 votes

# Answer
## APL (234)

It's obviously untested, but the logic seems sound. Printing commands are all included, the output is `104` characters and the actual logic is `130`.

```
Z←' Conjecture is '∘,¨'True' 'False'
⎕←'The Collatz',Z[1+{~{1=⍵:⍬⋄2|⍵:∇1+3×⍵⋄∇⍵÷2}h1⍵:⍬⋄∇⍵+1}h2 1]
⎕←'Goldbach''s',Z[1+{~⍵∊∘.+⍨N/⍨~N∊∘.×⍨N←1+⍳⍵:⍬⋄∇⍵+2}h1 2]
⎕←'The Twin Primes',Z[1+{~(T←{∧/{2=+/(⌈=⌊)⍵÷⍳⍵}¨N←⍵+1:N⋄∇N})h1⍵:⍬⋄∇T⍵}h2 4 2]

```

Ungolfed:

```
⍝ Environment assumptions: ⎕IO=1 ⎕ML=1
⍝ I've also assumed h1 and h2 are APL operators
⍝ i.e. x F y = f(x,y); x (F h1) y = h1(F,x,y)

⍝ 'Conjecture is True', 'Conjecture is False'
Z←' Conjecture is '∘,¨'True' 'False'

⍝⍝⍝ Collatz Conjecture
⍝ halts iff 1 is reached from given ⍵
collatzLoop←{
   1=⍵:⍬       ⍝ ⍵=1: halt
   2|⍵:∇1+3×⍵  ⍝ ⍵ uneven: loop with new val
   ∇⍵÷2        ⍝ ⍵ even: loop with new val
}

⍝ halts iff 1 is *not* reached from a value ≥ ⍵ (collatz false)
collatzHalt←{~collatzLoop h1 ⍵:⍬⋄∇⍵+1}

⍝ does it halt?
⎕←'The Collatz',Z[1+ collatzHalt h2 1]

⍝⍝⍝ Goldbach's Conjecture

⍝ Can ⍵ be expressed as a sum of two primes?
sumprimes←{
    N←1+⍳⍵         ⍝ N=[2..⍵+1]
    P←(~N∊N∘.×N)/N ⍝ P=primes up to ⍵+1×⍵+1
    ⍵∊P∘.+P        ⍝ can two P be summed to ⍵?
}

⍝ halts iff Goldbach is false
goldbachHalt←{
    ~sumprimes ⍵:⍬ ⍝ not a sum of primes: halt
    ∇⍵+2           ⍝ try next even number
}

⍝ does it halt?
⎕←'Goldbach''s',Z[1+ goldbachHalt h1 2]

⍝⍝⍝ Twin Primes

⍝ is it a prime?
isPrime←{
   2=+/(⌊=⌈)⍵÷⍳⍵    ⍝ ⍵ is a prime if ⍵ is divisible by exactly two
                   ⍝ numbers in [1..⍵] (i.e. 1 and ⍵)
}

⍝ find next twin
nextTwin←{
   N←⍵+1            ⍝ next possible twin
   ∧/ isPrime¨ N:N  ⍝ return it if twin
   ∇N               ⍝ not a twin, search on
}

⍝ halts iff no next twin for ⍵
twinPrimeHalt←{
   ~nextTwin h1 ⍵: ⍬  ⍝ if no next twin for ⍵, halt
   ∇nextTwin ⍵        ⍝ otherwise try next twin
}

⍝ does it halt?
⎕←'The Twin Primes',Z[1+ twinPrimeHalt h2 4 2]

```
> 3 votes

---
Tags: code-golf, math
---