10
\$\begingroup\$

Inspired by the connection rules from Calvin's Hobbies' question Make me an alphabet tree take a number of lines of letters as input and output the number of distinct connected trees it represents.

Letters connect to diagonally adjacent letters (never horizontally or vertically) and only where such a connection is available. Available connections correspond to the end of a line in the shape of the letter. For example, X can potentially connect at all four corners as they are all the ends of lines. W can only connect at the top left and top right corners, as the bottom left and bottom right corners are not ends of lines.

Example 1

Input:

XXX
XXX
XXX

Output:

2

The two trees (which do not form part of the output):

X   X             X
 \ /             / \
  X             X   X
 / \             \ /
X   X             X

Example 2

Input:

AMF
QWK

Output:

3

The three trees (which do not form part of the output):

A   F                M
 \ /                  \
  W         Q          K

Rules

  1. The only valid characters are spaces, newlines, and the 23 upper case letters listed in Calvin's Hobbies' question: ACEFGHIJKLMNPQRSTUVWXYZ.
  2. The letters B, D and O are not valid.
  3. The output is undefined if the input contains invalid characters.
  4. A tree can be of any size, including just 1 letter and including over 23 letters.
  5. The same letter can appear an arbitrary number of times in a single tree.
  6. The input will not be more than 79 lines long.
  7. Each line (excluding newlines) will not be more than 79 characters long.
  8. The lines will not necessarily be the same length as each other.
  9. A tree is defined to be a set of connected letters. Since the connections are all diagonal this excludes letters which are horizontally or vertically adjacent from being part of the same tree.
  10. Input containing zero trees (for example, all spaces and newlines) gives output 0.
  11. To clarify, input and output are as defined on meta (so there is not already a variable containing the input).

This is code golf. The shortest correct code wins. Code length is measured in bytes.

If you have python 3.4, the alphabet tree counter outputs the number of connected trees in its input, and can be used to test your golfed code gives the same results. The alphabet tree checker confirms whether its input is a valid output for Calvin's Hobbies' original question, and outputs a list of the distinct trees in the input. This may be useful for visualising the trees if there is any dispute over the number of trees in a given input (although using it on large forests will give a lot of output - a visualisation of every single tree separately).

If the either of these is incorrect please let me know so I can fix it.

Table of connections.

1 is for upper left, 2 is for upper right, 3 lower left, 4 lower right.

A: 3 4
C: 2 4
E: 2 4
F: 2 3
G: 2
H: 1 2 3 4
I: 1 2 3 4
J: 1 3
K: 1 2 3 4
L: 1 4
M: 3 4
N: 2 3
P: 3
Q: 4
R: 3 4
S: 2 3
T: 1 2
U: 1 2
V: 1 2
W: 1 2
X: 1 2 3 4
Y: 1 2
Z: 1 4

Sample forest

Here is an example of a forest to test your code with. It has the maximum size of 79 x 79 and no spaces. The alphabet tree counter gives an output of 714. I don't recommend running the alphabet tree checker on it as it will try to output a separate visualisation of every single one of the 714 trees.

CKZNXXJEHCNHICKFHNAFZTMNXZKXSXAFHEKKFJYUZPCHRSNAUPEZKIHZJSKKPHQJYHKMXSHCXKEHCXQ
YSRCHHQLXXKKXITAAHSKMXISHIGFXMVXTZZKLXIXVHJYKTAHSHYPCFLHSWIHHCXXRXXJNKXXVVRNSKM
CZWJKKNIXXUHKXCKRTXXSVHQZERHXIXNHXPKELNKHXRHFKHIEPKUWKXKUPHEKKIKLLSFWUSLYEEXLSI
KHGURVKSXXKAGXIWKCSHFNVWWHNHNIVYKKAKZKFSKHCVRHUENHFIIKNUNICHYRKYXXHTLKYHPQKWHKI
KGAFRXJMKMJJSXCUTFAKLHHFXTIXKNHKKRHIZHXWRRXJNHXQEMKKXCNVHWFMPERJKKZLHIKIUZRKWLM
YRXXXCXXHVISVIYTHNHKSXKRXYHXUFYYKXTHXRYIIKHEWHXVZAZHTQKJAKKHXKKVCKJHWHIIZXXZZYK
FQLXHIHJFKSKWMTHXISAXTVIKKHTIXUAGUAJHHHHRVHXHRNWKXKUKWHVUJLKIJCWTLCHTXSYTKLTFWX
AEKNFXUXHXHICSNCYWNEVVALHXUSACWKRNJAKLLXKVJCZHSAKYHXLHHTHFKSMCGXHFHPKTHXTRYYWXK
HHHKHXGKFUHKSKHKKHHRHIKYNQSXMKQKIXHTXXHHIXCZIWGXKAHRXKRYXPXXXVSYIXWXVMUFYWHKINZ
XXWWHXUTXGKXFKZUTHHZPJGMAEHZVGHLEXHKKPXHZIVKFETHKXTIVKSMHWYEKHIMIHWEHKHIIJXXJZS
XHHXHRHKKXHHVXYZMNHIYHKKXXKAVWKUKEXYGGCHMLHFJCKXXXHEXGCZUKMHIXKVXKHZHFLCKXIPZHH
TCHAXXKHHNKKMKPRFKKURCWLFXWIXUGTKKXHKRSYKZUXQXIEYWWWKKIXGXHALKAXXJHEXXLMNXJKHHL
INKRHXMMXZSTAZZKGLAPKLHSPGKUINHUMXXXLTNZWENCXLKRIXHZXHHKHCSXSHHXXKCTXXXHSFHJIHI
SHXKTXKXWPYZXKCNYSAVMICKJHKSMXKAWVNHZKGPFYPAEKEWXNKXXHKEYHAYWKIYHKXEHNJJRISLXXI
IHZLMKYUTHWHIXEKRJIHFVHCFKLMSKIKHMUHQLYXILMHKXXXCJHZXJKKHSHXMVCHIGSICHITKIGMYYT
USKJTKLQYXYKKRKELMXVMLKNNNXIHPHMXKNXXYFKRHXRNNJRCQKEFKXXSWHUECTMCWVCXHLALKMSIZM
VCKPXRCSYRVEKTCUHKVIKAXHMNMJMTKMGXEPJXYZVLKQFIIJRZHXHHSSRKHHYRHZXFHXXLUKXCAHNXX
CGHQIQXTHRLIKKQFHQCUKZXLMVLSWHJKGKYKJMKVFIHHKYHCKAFXHMEHKJKMKWIXAYEKYKCXIMKHRXJ
XYIJIIAHHEXKIYGKHKIALIXKRHRXYXRAVHGXTUKKKXHIIGNHXFVVHTFUKHNIKHFKRXHXXNIIXTSQHIH
XSNXRHIUXHTXWYRHXHSXZKKKXIKHEKSHHWINIGEIXNJYSXILYIKHVYAMFNKXYWEINHHXSVFVXQRHUHW
FRIRFCKFKIVHCKYXKXMTXELJXNCKWYHKXVTXIIHFVFZVHYSXEXZNWKWIXESHXFHKCKVPXUXCIMRHNXR
XELHXNMKVHRHHHVKTKKPCXEXZHKPHNAWVXJKWWHMSKFFRUJVSHGXFATZSSWYXKHIHKAHXIEJXSKXFLE
KFKECCCPWKXJTVKXHJRYVXUIFHKUHHHLMKSVJICQHKXZKNIXHKEHKNYTKKFKHUCHZFILHRHKHQKIIEJ
MGIKXXPZQXHRHHXKXJHAGJKHIXKILXNEVWHXWWLTFWHHUMKJPZTJXXTXVPTMHHMGEPHIXRHLGQTWJCV
UKHXXYXHAFXXSIJXHHXKLJQJIIKXIKYHSRKUNNKHTMXTCTKXGWFHSJKQSCHINSKLGSKUTXKKAWAEXAM
LFKXWWXXSKKXPUIKTFREKIXLXNXKHHVXJKVWEFKFMYFIHGHXSHTEUJRIEAMQSXQMRJIHRETXYMHKIUX
XFAAMXHXUFITLAWNMJYHTCWQFNXAIXKSZXIXXKRKAHWHYEAMVHNKLHKVUTAIZLVXGCHHAZTTHCELIGK
XPJRXIVVFTJKQFNSKMKFKIHMRCHWFYVIRVXFPTKIKUKQKKMVKWIYIKRXWEVXUIHFHXASHHXVFWEWHHK
KYELCKHLXXHXHTVMJHNFQUFJXKUHIZXFEXRZMEYZHSJXVZKMYHNCVEXKXKATRFLGHXTHXRPHXLHKSTY
IXUUFXHWMKRIWWIRSKSCQHXSIIKRHXZNFCXXHSLXHRNHZXNWHKMQRPTHTHXXSVKHXZXICYHSXXXKXHU
TXESLHCCEHHHHKHICSILWLHFEKVKSUECLAZHZXIKRUKWKFHXILWNSTMXXAGKWVLQNXESKXYIIXKXZRI
HHSSHXRXKHNUWLKPXLIXFUIHXNKIKJCHTGWXLJZSLHSMZMSZTKLFAVEKIMGXJVAIKXHWUUHKHURIYMG
IXMYFVXIWMZVNVYWKYFVXJKKEHKMNLYXNXFSRHHSANKTKTNVKNTRHPXKLRCMHLHUWKIMGWVFAPZXWXH
RHIKVZWLHJYUKCQSSCNZFRRMXTJXQMRXCZIVPRHJMHVVXHHHLHKNKRKNXLKKREIWSTINKKXFSMPILXK
KSFKKXGIAKXKRWHNHZMVFVFUHIKJWIHUJHHNKKSXMMUVNHEJIYCCWEHHHGJXWJJVXWIPXCKWHSXFYXI
RWVXEHJLHANHXIVHMMQHAHHRKTMHXXXLHPCQRSHTHVXXJSXQZRHKKLSFYXKTKLKXHKHRSXLKKXUJXKJ
TNKIMHEXKVYMVMRKTXIXJHTXYIXKMHXKKWQGFLGIFIKXKTMXSYYMTVQITPWHXHHKXEYKXHHJETJHXVK
KXEWWAHIHVHXAUTCHZLRXKMKHKNKREKKMKHIHPXXZNFHFYIXHJXXWKIKHQWWISXZHJZKHHZXTGIIXJN
YKZHRXXFQKHKXZHVEWSHREHKIYTFSTHLREKHFJIAVWKMKJMXHXKWKWYRTKMHIIXNCVKXRHKKEMYERRL
KREZXUHKRQKFYKWKHEZXKWWXEHXYKLAIKYNVXFRPUNFHVJHKWZXSXKIHKYHKXFHYXXXTXIXIXGIXKHK
ZHIKXXXRCSKVKYVHXKRJHHXWCNEXRQIKAIHHTFHWCSCZCHKXMUMKLVKXPKLIZIYKRKHIKZSHHAKCNKK
ZUHHHWKMNIXRGAVXHCXAQUKXHHEXLIRNNHLHCKRZSXHKMKWTKHKVJEUSKHXEFPHMPKHYKKUMHFLKSIJ
KKKZXHRRNSSKXWIUCXPJUFLJSVXHMRKHXWHYURHXNKCWKIXKKWHXZMRAHHXCKIHKXXTJRHTEHUHTPZK
HAKHLHCEGIXIIVAYWWKXCEXIHKWMKEHILYZEXKHKYVWJVKVYHFTSNIHGHCIJXKNSXXTXHSYEXNFKHSY
KWGUHKCXWGCXKFSIPZXIZKPLHIXXYPKYHHFKYMNTXHIVMNTRYJPUKUKYUMZFTYSIIXVAXINHCMXKTEH
GQYGHKHIKKKIKXYGCHKLAYSXPHHKFSICIKFFHSKHMAWVYKHJKNZZXYISGZMJWRRIJILHHKKHFFKARKH
RIKUACKKMVIGHXKKMHFSXJEKXFMKSHXZXHKMHHXXSXHHLXHHEKKAKMXXECVLHEIKGWACSNKKVKARERJ
CXMVNITXXMKCYUIHUHUXUIKYHNZYHXXLTHJATGKHKTIKKYTWXRJIXCJNHTYXIRLTKAMEHZMKRJXHAWV
HKIMIQKMRSJNHZZYKHWWKSFIRHKHFWKKYFITXWATKKXSECSHKXHPQCNIIIWFMKUHUMXWCXYJHVSVELR
NXUKLFAHVGGHYVTAWNIXHKXHXHXXAKKANKYIFXUTLKKTHHIKHKATJXKXETTWEKNIHQSKIXXJXXYLXXJ
RXPCUSXZLZXVKIRLSVXHHXXKMAIXCXXQVIKIUKIXIXXJHXFRRSXXQREIWHXFKWISXYHVEKHYYXKZLMN
XCHKWYHJRWXRLXLEAXXHKVRKLGUMWSCXINKHMNHHISNKLVKWXRWKEKPCRGZNIXSXTXHEKEEKHXTHJUH
XGVNFTHKHNVGXGSRIPGKFXZTUKEKYKIINRKUHIKLHXRIYXRIKXSCENMZLXXHAXXWTIGJXHHWXHMIFIK
HEVJQXTXKPFSTVKWGKXTKYRXJHVPKKNLQLPSXPIZVNIAKJJRHZHKFXIGRHKVCTVXINNHTGLIHMVYINA
HIQHXXVZAHIHRHIHFTUWFKGKQKTAUXJSIXWHUXNXJIJIIAWUKHRLIHKVSIFSNKKHNTYCTPNWIKHHIKX
MRLCMZXPALCTFXPHVHSVNXTJWFHKQZTZEYMALXXIXRJIKCFJYSPXKZXKUGKZLQHKUYINNUKKKLKMVLI
VQHFXEKRVSHKKKHGWZWTLXRFWMVXHKKXWXKEHAJIXJKHXFNNGHKKLXKKKLJYKJEEHCKXTGHHICISHMF
ZXPUAXPXKXXVYAHPIJHLRCIKXLCGZXLWFJPHXAHFKSLFEHGLKHFIIHHKHHCTVAKWPXWGIQKHNILHQJW
XHPIQLZHKVUKXCMLHSFHEKHEKREWXKYIXSZHTAHIIEUYVUHSMKTHFKMGKSLMHXKYACCXXKATLYXKXFL
WKHIKFVFKUVXXRVEYUTCRNCXPZCCLSKTHWQXXJMHFLKXHNXCVZXHGXYAVYEXVJCHKXIKMSVAXVHNEXV
IXIKYSSJQKKPTXFXFREKXJAKKXEJXNVXHEUJHIMHHPNRVZHXUKZPWTXCCIHXAKZUSHXRMSLIUWHIHKK
MXIHKCKKHSIHXCKCRKATFKFSJXLRXIJNFYQISMKHSAYKZXPXNIHWSKHXYZLAVXIEXVTYHGSRXXAGQRK
IMCXXHXSCXVXCKCTHNSHWEIRAELTJMFKCXQIIXVFSZXHXXIPCCFIZXEXPWHEGJUHWXGZJCISRJSCIPV
HIXHUIHJXXLXXXZLNZCTJKYHNHAVIHIITLHXGEXXKUIXGNKLHHUVFJAFKHHPCJSUKXHCSIHKCXZEIFI
UKUHWRKSJFKZNYJMSZYRTXZKWHVIXLXHRFXTZHTHHHUMYTXKRXMFAKLUMAPNGHKKJUKYIHUXQHMIUVI
XHCKNCKTSXTZMHETTLTMYXHJKUUVXHHSHIVSZKHHWXAWMFXVVHFUCXHMXWKXHXKVLLHXZSICSACKIHC
FXFNPHXHTHCLHKJTSLVTHKHHXHXHHKTKSUTIXKYQUHAQXXNSLKUMTKHSKKYTXHTVPGVHHMXVNLHXIRF
WJFVVXITNRCXKHTFARSIXASVCNXJQNXIJVUHYIVNIRZXMHHFKHKMMNCUXFTEXEKEHTIHSKAKXZVTSKY
ZJGHRTHUWMHHZXHPAIHWHUSXXKLHKYKHJSHHNKXXKRSHMKHSIHIUIXKZXSUZHKXIMMIXMXTXZZLXXIM
EQZKRLALIEVHXYKHXIFYKXMAINSNIASMGLLYHXHRIXVWUKZHFREJCAXKXWYHXNUKTQCUKIHLWKTEKMC
MHLXXHHYQWHTXVHCMKKHGIUFSEHNEVYSXQHHXXKHMXUXQKHZHHHSHRKWHMMEHZMIKKYYWIUNEIJUIKT
NCHKRNSJYLLIXKXAIERXKKXIQZVHXFVIIAXHIYUGZURXFHSXKLIWESKHEXQSCUHWKALZIVEZHAFKKWA
IKCJWNVRKMITKNYXJYKYXVXXUKWHXXJAKLXXXVKXGXKKZXMHCKKCGRLZQINVHRLNVWXTKVLTEPTXUXH
XVCICKXXXEVTIKIHHSHCKYIJXNCJKJSLSHVXJHTHSIKUXPHWRIKMFXXMMHKHCAQWITIEWEXPFHYXXKU
XXSHHIXHWWRKITSHSXHJKEWHXIZHSHZCHFARIXNPHYSNIKJXLQENKFCXYRWMXAPIYTZKNMXFHNIMCCS
PAACXJMNVZZHMXXSNVSXEIINNCHLSTIXHHKYXLEHQHKHPRWIXXHRKVCXFKLHSHKGXJGKLLLWSHIISKT
WUYXTJHXXMKJCYIXQJRNFKYHHUUKTIAYXVUUXFCYLHXWWZAUHWZIUAIGKHKIMKXXXKJZXCKKRCJAKQJ
EVAGXIHTINSXENKWVXWCLFUVHXFPFCIFVHWXRIFZRYZKUUEMXNGAJLIFHJJIGUXFKKRIMKGFKXJYXKV
KKRHHWKIYXWXWKLWXWKFHXLXRXRKKENMHHIQRHTTMFYTGRLSHRXIXKKUEHXXJKRIKSYLTKYJMNIUWVE
\$\endgroup\$
4
\$\begingroup\$

GolfScript, 150 characters

I thought a GolfScript implementation is missing in this competition. While it is not a particularly fitting challenge for GolfScript it can be done quite nicely.

n%{.,' '80*>+}%n*:^,,{.80+'AFJMNPRS'\'CEFGNSTUVWY'3$'ACELMQRZ'3$2+'JLTUVWYZ'}%4/{2/.{~'HIKX'+\^[=]&},=},{~@;;]}%.,{:A{A{1$&},{|}/$}%.&}*^'
 '-,\{,-)}/

Note that edc65`s testcase takes only a few seconds but the huge forests may run for several minutes, depending on your computer. Although the algorithm itself is not extremely slow it is only slightly optimised for speed instead of size. It copies huge lists of trees several times which is a costly operation in GolfScript.

I am still trying to find a shorter representation of the encodings for the letters' connections. Also you can save 16 characters if you can guarantee that all lines have the same length.

\$\endgroup\$
8
+150
\$\begingroup\$

Ruby - 228

My very first Ruby golf. Still new to Ruby. Ruby is awesome language! Love learning it! =)
But I'm afraid will probably lose. =(

g=$<.each.map{|k|k.ljust 99}*''<<?@*1e5
p (0..1e4).map(&f=->k,a=!0{l=(0..3).map{|i|k+~0**i+99*~0**(i/2)if"xhv8gstx930ognx8puyr".to_i(36)>>(i+4*g[k].ord-260)&1>0};(g[k]=?@;l.map{|v|v&&f[v,k]})if(l&[a]!=[])|!a&l.any?}).count{|x|x}

To run, create a file with the forest as forest.txt and run using ruby test.rb forest.txt

GoRuby Edition - 188

g=A.e.m{|k|k.lj 99}.j.lj 1e5
p 9999.mp(&f=->k,a=N{l=4.mp{|i|k+~0**i+99*~0**(i/2)if"xhv8gstx930ognx8puyr".toi(36)>>(i+4*g.g(k)-260)&1>0}.cp;(g[k]=?@;l.m{|v|f[v,k]})if(l.i a)|!a&l.an}).cp.sz

Ok... So my fear came true. @Howard (I'd actually expected him) actually made a GS solution.

\$\endgroup\$
  • 1
    \$\begingroup\$ Why the pessimism? This is the shortest one so far... +1. \$\endgroup\$ – trichoplax Aug 14 '14 at 17:38
  • 2
    \$\begingroup\$ I was eating peacefully and checking code golf on my handphone.. and then I saw bounty. I was like.. If there is a time to learn ruby, its now. XD \$\endgroup\$ – Vectorized Aug 14 '14 at 17:48
  • 1
    \$\begingroup\$ you're leading now. \$\endgroup\$ – Stack Tracer Aug 14 '14 at 20:32
  • \$\begingroup\$ It's a race byte by byte \$\endgroup\$ – edc65 Aug 20 '14 at 16:54
  • \$\begingroup\$ Argh... GolfScript solution is here by @Howard, who can even use it for the most absurd of stuff (e.g. Wang tiles). I guess I shall just show all my cards. Nice race anyways! \$\endgroup\$ – Vectorized Aug 21 '14 at 0:34
6
\$\begingroup\$

JavaScript (E6) 235 238 240 276 284 291 294 319

A function with a string parameter (the forest), returning the tree count. This seems ok with the rules in meta about input/ouput (point 2).

This scans the forest numbering the branches (var u) and keeping a running count of joinined branches (var j now). Branches that have been joined are remembered in a set, so that two joined branches are recognizable even if they have different numbers.

Edit Slightly changed the algorithm, now it manages the forest string as a char array avoiding the split into lines. Simplified the branch joining - slower but shorter. Bonus: at the end the r array can be used as a map to extract any of the n trees from the forest. I'll elaborate.

Probably a little more golfable, but not so much as the answer in Ruby. I'll try.

Edit Ruby and goRuby passed. In the meantime @bitpwner has probably become a Ruby guru and he'll cut away half of his ruby code with his next edit ...

Here is a jsfiddle with less golfed code and the graphical output of tree connections.

C=t=>(r=['\n',...t]).map((e,i)=>
  e<' '?(a=b,p=i-h,b=[]):
   (k=(2&a[h=b.push(n='0x'+'30909a8ff6f53a0213accccfc5'[e.charCodeAt()-65]|0)]|1&a[h-2])&n/4,
   x=r[p-1],y=r[++p],k>2&&x-y?r=r.map(v=>v-x?v:y,++j):0,
   r[i]=k>1?y:k?x:n&&++u),j=u=h=b=0)|u-j

Test

C("AMF\nQWK")

Result: 3

A new testcase

CKZNXXJEHCNHICKFHNAFZTMNXZKXSXAFHEKKFJYU
YSRCHHQLXXKKXITAAHSKMXISHIGFXMVXTZZKLXIX
QZWJKKNIXXUHKXCKRTXXSVHQZERHXIXNHXPKELNW
 HGUR                              KZKF
 GAFR                              RZHX
 EXXXC                            THXRR
  LXHI                            UAJH
  KNFX                            NJAK
  TWWHXUTXGKXFKZUTHHZPJGMAEHZVGHLEXHKY
   XHRHKKXHHVXYZMNHIYHKKXXKAVWKUKEXYG
   AXXKHHNKKMKPRFKKURCWLFXWIXUGTKKXHK
   USHXK                        VNHZI
    LMKY                        MUHQ
    JTKL                        KNXX
    PVCKP                      XEPJA
     QIQX                      KYKJ
     IJIIHEXKIYGKHKIALIXKRHRXYXRAVH
     SXSNXRHIUXHTXWYRHXHSXZKKKXIKHF
      KIVHCKYXKXMTXELJXNCKWYHKXVHF
      HXNM                    WWHM
      GKFKE                  KSVJH
       KXXP                  WHXW
       UKHX                  RKUN
       JLFKX                EFKFK
        XFAAMXHXUFITLAWNMJYHTCWQ
        XPJRXIVVFTJKQFNSKMKFKIHM
        KYELCKHLXXHXHTVMJHNFQUFJ

C("CKZNXXJEHCNHICKFHNAFZTMNXZKXSXAFHEKKFJYU\nYSRCHHQLXXKKXITAAHSKMXISHIGFXMVXTZZKLXIX\nQZWJKKNIXXUHKXCKRTXXSVHQZERHXIXNHXPKELNW\n"
+" HGUR                              KZKF\n GAFR                              RZHX\n EXXXC                            THXRR\n"
+"  LXHI                            UAJH\n  KNFX                            NJAK\n  TWWHXUTXGKXFKZUTHHZPJGMAEHZVGHLEXHKY\n"
+"   XHRHKKXHHVXYZMNHIYHKKXXKAVWKUKEXYG\n   AXXKHHNKKMKPRFKKURCWLFXWIXUGTKKXHK\n   USHXK                        VNHZI\n"
+"    LMKY                        MUHQ\n    JTKL                        KNXX\n    PVCKP                      XEPJA\n"
+"     QIQX                      KYKJ\n     IJIIHEXKIYGKHKIALIXKRHRXYXRAVH\n     SXSNXRHIUXHTXWYRHXHSXZKKKXIKHF\n"
+"      KIVHCKYXKXMTXELJXNCKWYHKXVHF\n      HXNM                    WWHM\n      GKFKE                  KSVJH\n"
+"       KXXP                  WHXW\n       UKHX                  RKUN\n       JLFKX                EFKFK\n"
+"        XFAAMXHXUFITLAWNMJYHTCWQ\n        XPJRXIVVFTJKQFNSKMKFKIHM\n        KYELCKHLXXHXHTVMJHNFQUFJ")

Result: 149

The huge forest

C("CKZNXXJEHCNHICKFHNAFZTMNXZKXSXAFHEKKFJYUZPCHRSNAUPEZKIHZJSKKPHQJYHKMXSHCXKEHCXQ\nYSRCHHQLXXKKXITAAHSKMXISHIGFXMVXTZZKLXIXVHJYKTAHSHYPCFLHSWIHHCXXRXXJNKXXVVRNSKM\n"+
"CZWJKKNIXXUHKXCKRTXXSVHQZERHXIXNHXPKELNKHXRHFKHIEPKUWKXKUPHEKKIKLLSFWUSLYEEXLSI\nKHGURVKSXXKAGXIWKCSHFNVWWHNHNIVYKKAKZKFSKHCVRHUENHFIIKNUNICHYRKYXXHTLKYHPQKWHKI\n"+
"KGAFRXJMKMJJSXCUTFAKLHHFXTIXKNHKKRHIZHXWRRXJNHXQEMKKXCNVHWFMPERJKKZLHIKIUZRKWLM\nYRXXXCXXHVISVIYTHNHKSXKRXYHXUFYYKXTHXRYIIKHEWHXVZAZHTQKJAKKHXKKVCKJHWHIIZXXZZYK\n"+
"FQLXHIHJFKSKWMTHXISAXTVIKKHTIXUAGUAJHHHHRVHXHRNWKXKUKWHVUJLKIJCWTLCHTXSYTKLTFWX\nAEKNFXUXHXHICSNCYWNEVVALHXUSACWKRNJAKLLXKVJCZHSAKYHXLHHTHFKSMCGXHFHPKTHXTRYYWXK\n"+
"HHHKHXGKFUHKSKHKKHHRHIKYNQSXMKQKIXHTXXHHIXCZIWGXKAHRXKRYXPXXXVSYIXWXVMUFYWHKINZ\nXXWWHXUTXGKXFKZUTHHZPJGMAEHZVGHLEXHKKPXHZIVKFETHKXTIVKSMHWYEKHIMIHWEHKHIIJXXJZS\n"+
"XHHXHRHKKXHHVXYZMNHIYHKKXXKAVWKUKEXYGGCHMLHFJCKXXXHEXGCZUKMHIXKVXKHZHFLCKXIPZHH\nTCHAXXKHHNKKMKPRFKKURCWLFXWIXUGTKKXHKRSYKZUXQXIEYWWWKKIXGXHALKAXXJHEXXLMNXJKHHL\n"+
"INKRHXMMXZSTAZZKGLAPKLHSPGKUINHUMXXXLTNZWENCXLKRIXHZXHHKHCSXSHHXXKCTXXXHSFHJIHI\nSHXKTXKXWPYZXKCNYSAVMICKJHKSMXKAWVNHZKGPFYPAEKEWXNKXXHKEYHAYWKIYHKXEHNJJRISLXXI\n"+
"IHZLMKYUTHWHIXEKRJIHFVHCFKLMSKIKHMUHQLYXILMHKXXXCJHZXJKKHSHXMVCHIGSICHITKIGMYYT\nUSKJTKLQYXYKKRKELMXVMLKNNNXIHPHMXKNXXYFKRHXRNNJRCQKEFKXXSWHUECTMCWVCXHLALKMSIZM\n"+
"VCKPXRCSYRVEKTCUHKVIKAXHMNMJMTKMGXEPJXYZVLKQFIIJRZHXHHSSRKHHYRHZXFHXXLUKXCAHNXX\nCGHQIQXTHRLIKKQFHQCUKZXLMVLSWHJKGKYKJMKVFIHHKYHCKAFXHMEHKJKMKWIXAYEKYKCXIMKHRXJ\n"+
"XYIJIIAHHEXKIYGKHKIALIXKRHRXYXRAVHGXTUKKKXHIIGNHXFVVHTFUKHNIKHFKRXHXXNIIXTSQHIH\nXSNXRHIUXHTXWYRHXHSXZKKKXIKHEKSHHWINIGEIXNJYSXILYIKHVYAMFNKXYWEINHHXSVFVXQRHUHW\n"+
"FRIRFCKFKIVHCKYXKXMTXELJXNCKWYHKXVTXIIHFVFZVHYSXEXZNWKWIXESHXFHKCKVPXUXCIMRHNXR\nXELHXNMKVHRHHHVKTKKPCXEXZHKPHNAWVXJKWWHMSKFFRUJVSHGXFATZSSWYXKHIHKAHXIEJXSKXFLE\n"+
"KFKECCCPWKXJTVKXHJRYVXUIFHKUHHHLMKSVJICQHKXZKNIXHKEHKNYTKKFKHUCHZFILHRHKHQKIIEJ\nMGIKXXPZQXHRHHXKXJHAGJKHIXKILXNEVWHXWWLTFWHHUMKJPZTJXXTXVPTMHHMGEPHIXRHLGQTWJCV\n"+
"UKHXXYXHAFXXSIJXHHXKLJQJIIKXIKYHSRKUNNKHTMXTCTKXGWFHSJKQSCHINSKLGSKUTXKKAWAEXAM\nLFKXWWXXSKKXPUIKTFREKIXLXNXKHHVXJKVWEFKFMYFIHGHXSHTEUJRIEAMQSXQMRJIHRETXYMHKIUX\n"+
"XFAAMXHXUFITLAWNMJYHTCWQFNXAIXKSZXIXXKRKAHWHYEAMVHNKLHKVUTAIZLVXGCHHAZTTHCELIGK\nXPJRXIVVFTJKQFNSKMKFKIHMRCHWFYVIRVXFPTKIKUKQKKMVKWIYIKRXWEVXUIHFHXASHHXVFWEWHHK\n"+
"KYELCKHLXXHXHTVMJHNFQUFJXKUHIZXFEXRZMEYZHSJXVZKMYHNCVEXKXKATRFLGHXTHXRPHXLHKSTY\nIXUUFXHWMKRIWWIRSKSCQHXSIIKRHXZNFCXXHSLXHRNHZXNWHKMQRPTHTHXXSVKHXZXICYHSXXXKXHU\n"+
"TXESLHCCEHHHHKHICSILWLHFEKVKSUECLAZHZXIKRUKWKFHXILWNSTMXXAGKWVLQNXESKXYIIXKXZRI\nHHSSHXRXKHNUWLKPXLIXFUIHXNKIKJCHTGWXLJZSLHSMZMSZTKLFAVEKIMGXJVAIKXHWUUHKHURIYMG\n"+
"IXMYFVXIWMZVNVYWKYFVXJKKEHKMNLYXNXFSRHHSANKTKTNVKNTRHPXKLRCMHLHUWKIMGWVFAPZXWXH\nRHIKVZWLHJYUKCQSSCNZFRRMXTJXQMRXCZIVPRHJMHVVXHHHLHKNKRKNXLKKREIWSTINKKXFSMPILXK\n"+
"KSFKKXGIAKXKRWHNHZMVFVFUHIKJWIHUJHHNKKSXMMUVNHEJIYCCWEHHHGJXWJJVXWIPXCKWHSXFYXI\nRWVXEHJLHANHXIVHMMQHAHHRKTMHXXXLHPCQRSHTHVXXJSXQZRHKKLSFYXKTKLKXHKHRSXLKKXUJXKJ\n"+
"TNKIMHEXKVYMVMRKTXIXJHTXYIXKMHXKKWQGFLGIFIKXKTMXSYYMTVQITPWHXHHKXEYKXHHJETJHXVK\nKXEWWAHIHVHXAUTCHZLRXKMKHKNKREKKMKHIHPXXZNFHFYIXHJXXWKIKHQWWISXZHJZKHHZXTGIIXJN\n"+
"YKZHRXXFQKHKXZHVEWSHREHKIYTFSTHLREKHFJIAVWKMKJMXHXKWKWYRTKMHIIXNCVKXRHKKEMYERRL\nKREZXUHKRQKFYKWKHEZXKWWXEHXYKLAIKYNVXFRPUNFHVJHKWZXSXKIHKYHKXFHYXXXTXIXIXGIXKHK\n"+
"ZHIKXXXRCSKVKYVHXKRJHHXWCNEXRQIKAIHHTFHWCSCZCHKXMUMKLVKXPKLIZIYKRKHIKZSHHAKCNKK\nZUHHHWKMNIXRGAVXHCXAQUKXHHEXLIRNNHLHCKRZSXHKMKWTKHKVJEUSKHXEFPHMPKHYKKUMHFLKSIJ\n"+
"KKKZXHRRNSSKXWIUCXPJUFLJSVXHMRKHXWHYURHXNKCWKIXKKWHXZMRAHHXCKIHKXXTJRHTEHUHTPZK\nHAKHLHCEGIXIIVAYWWKXCEXIHKWMKEHILYZEXKHKYVWJVKVYHFTSNIHGHCIJXKNSXXTXHSYEXNFKHSY\n"+
"KWGUHKCXWGCXKFSIPZXIZKPLHIXXYPKYHHFKYMNTXHIVMNTRYJPUKUKYUMZFTYSIIXVAXINHCMXKTEH\nGQYGHKHIKKKIKXYGCHKLAYSXPHHKFSICIKFFHSKHMAWVYKHJKNZZXYISGZMJWRRIJILHHKKHFFKARKH\n"+
"RIKUACKKMVIGHXKKMHFSXJEKXFMKSHXZXHKMHHXXSXHHLXHHEKKAKMXXECVLHEIKGWACSNKKVKARERJ\nCXMVNITXXMKCYUIHUHUXUIKYHNZYHXXLTHJATGKHKTIKKYTWXRJIXCJNHTYXIRLTKAMEHZMKRJXHAWV\n"+
"HKIMIQKMRSJNHZZYKHWWKSFIRHKHFWKKYFITXWATKKXSECSHKXHPQCNIIIWFMKUHUMXWCXYJHVSVELR\nNXUKLFAHVGGHYVTAWNIXHKXHXHXXAKKANKYIFXUTLKKTHHIKHKATJXKXETTWEKNIHQSKIXXJXXYLXXJ\n"+
"RXPCUSXZLZXVKIRLSVXHHXXKMAIXCXXQVIKIUKIXIXXJHXFRRSXXQREIWHXFKWISXYHVEKHYYXKZLMN\nXCHKWYHJRWXRLXLEAXXHKVRKLGUMWSCXINKHMNHHISNKLVKWXRWKEKPCRGZNIXSXTXHEKEEKHXTHJUH\n"+
"XGVNFTHKHNVGXGSRIPGKFXZTUKEKYKIINRKUHIKLHXRIYXRIKXSCENMZLXXHAXXWTIGJXHHWXHMIFIK\nHEVJQXTXKPFSTVKWGKXTKYRXJHVPKKNLQLPSXPIZVNIAKJJRHZHKFXIGRHKVCTVXINNHTGLIHMVYINA\n"+
"HIQHXXVZAHIHRHIHFTUWFKGKQKTAUXJSIXWHUXNXJIJIIAWUKHRLIHKVSIFSNKKHNTYCTPNWIKHHIKX\nMRLCMZXPALCTFXPHVHSVNXTJWFHKQZTZEYMALXXIXRJIKCFJYSPXKZXKUGKZLQHKUYINNUKKKLKMVLI\n"+
"VQHFXEKRVSHKKKHGWZWTLXRFWMVXHKKXWXKEHAJIXJKHXFNNGHKKLXKKKLJYKJEEHCKXTGHHICISHMF\nZXPUAXPXKXXVYAHPIJHLRCIKXLCGZXLWFJPHXAHFKSLFEHGLKHFIIHHKHHCTVAKWPXWGIQKHNILHQJW\n"+
"XHPIQLZHKVUKXCMLHSFHEKHEKREWXKYIXSZHTAHIIEUYVUHSMKTHFKMGKSLMHXKYACCXXKATLYXKXFL\nWKHIKFVFKUVXXRVEYUTCRNCXPZCCLSKTHWQXXJMHFLKXHNXCVZXHGXYAVYEXVJCHKXIKMSVAXVHNEXV\n"+
"IXIKYSSJQKKPTXFXFREKXJAKKXEJXNVXHEUJHIMHHPNRVZHXUKZPWTXCCIHXAKZUSHXRMSLIUWHIHKK\nMXIHKCKKHSIHXCKCRKATFKFSJXLRXIJNFYQISMKHSAYKZXPXNIHWSKHXYZLAVXIEXVTYHGSRXXAGQRK\n"+
"IMCXXHXSCXVXCKCTHNSHWEIRAELTJMFKCXQIIXVFSZXHXXIPCCFIZXEXPWHEGJUHWXGZJCISRJSCIPV\nHIXHUIHJXXLXXXZLNZCTJKYHNHAVIHIITLHXGEXXKUIXGNKLHHUVFJAFKHHPCJSUKXHCSIHKCXZEIFI\n"+
"UKUHWRKSJFKZNYJMSZYRTXZKWHVIXLXHRFXTZHTHHHUMYTXKRXMFAKLUMAPNGHKKJUKYIHUXQHMIUVI\nXHCKNCKTSXTZMHETTLTMYXHJKUUVXHHSHIVSZKHHWXAWMFXVVHFUCXHMXWKXHXKVLLHXZSICSACKIHC\n"+
"FXFNPHXHTHCLHKJTSLVTHKHHXHXHHKTKSUTIXKYQUHAQXXNSLKUMTKHSKKYTXHTVPGVHHMXVNLHXIRF\nWJFVVXITNRCXKHTFARSIXASVCNXJQNXIJVUHYIVNIRZXMHHFKHKMMNCUXFTEXEKEHTIHSKAKXZVTSKY\n"+
"ZJGHRTHUWMHHZXHPAIHWHUSXXKLHKYKHJSHHNKXXKRSHMKHSIHIUIXKZXSUZHKXIMMIXMXTXZZLXXIM\nEQZKRLALIEVHXYKHXIFYKXMAINSNIASMGLLYHXHRIXVWUKZHFREJCAXKXWYHXNUKTQCUKIHLWKTEKMC\n"+
"MHLXXHHYQWHTXVHCMKKHGIUFSEHNEVYSXQHHXXKHMXUXQKHZHHHSHRKWHMMEHZMIKKYYWIUNEIJUIKT\nNCHKRNSJYLLIXKXAIERXKKXIQZVHXFVIIAXHIYUGZURXFHSXKLIWESKHEXQSCUHWKALZIVEZHAFKKWA\n"+
"IKCJWNVRKMITKNYXJYKYXVXXUKWHXXJAKLXXXVKXGXKKZXMHCKKCGRLZQINVHRLNVWXTKVLTEPTXUXH\nXVCICKXXXEVTIKIHHSHCKYIJXNCJKJSLSHVXJHTHSIKUXPHWRIKMFXXMMHKHCAQWITIEWEXPFHYXXKU\n"+
"XXSHHIXHWWRKITSHSXHJKEWHXIZHSHZCHFARIXNPHYSNIKJXLQENKFCXYRWMXAPIYTZKNMXFHNIMCCS\nPAACXJMNVZZHMXXSNVSXEIINNCHLSTIXHHKYXLEHQHKHPRWIXXHRKVCXFKLHSHKGXJGKLLLWSHIISKT\n"+
"WUYXTJHXXMKJCYIXQJRNFKYHHUUKTIAYXVUUXFCYLHXWWZAUHWZIUAIGKHKIMKXXXKJZXCKKRCJAKQJ\nEVAGXIHTINSXENKWVXWCLFUVHXFPFCIFVHWXRIFZRYZKUUEMXNGAJLIFHJJIGUXFKKRIMKGFKXJYXKV\n"+
"KKRHHWKIYXWXWKLWXWKFHXLXRXRKKENMHHIQRHTTMFYTGRLSHRXIXKKUEHXXJKRIKSYLTKYJMNIUWVE")

Result: 714

\$\endgroup\$
  • \$\begingroup\$ Taking input as a function argument is fine according to the meta post, as long as it's as part of a complete program. \$\endgroup\$ – trichoplax Aug 16 '14 at 16:30
  • \$\begingroup\$ @githubphagocyte that's not so clear to me, can you elaborate? Is mine a complete program - I don't think so - is it possible to make a "complete program" in JS? If not, what else? prompt + alert? \$\endgroup\$ – edc65 Aug 16 '14 at 16:35
  • \$\begingroup\$ @edc65 as far as I'm concerned, if you can run it without it being part of a larger piece of source code, then it's complete. \$\endgroup\$ – trichoplax Aug 16 '14 at 17:12
3
\$\begingroup\$

C - 691 571 Bytes

Any suggestions for further golfing are welcome.

#include <cstdio>
#include <cstring>
#define L(i) strlen(t[i])
#define R(a,b,c) if(z&a&&T(b,c)&8/a){f(b,c);}
#define S !!strstr(
#define U return
#define V if(i<0||j<0||j>=L(i)
char t[80][80];int n=0,I=0,J,C=0;int T(int i,int j){V)U 0;char c[]="i";c[0]=t[i][j];U 1*S"HIJKLTUVWXYZ",c)+2*S"CEFGHIKNSTUVWXY",c)+4*S"AFHIJKMNPRSX",c)+8*S"ACEHIKLMQRXZ",c);}int f(int i,int j){V||t[i][j]<0)U 0;int z=T(i,j);t[i][j]=-1;R(1,i-1,j-1)R(2,i-1,j+1)R(4,i+1,j-1)R(8,i+1,j+1)U 1;}main(){while(scanf("%s\n",t[n++])>0){};n--;for(;I<n;I++){for(J=0;J<L(I);J++){C+=f(I,J);}}printf("%d\n",C);}

Ungolfed

#include <cstdio>
#include <cstring>
#define L(i) strlen(t[i])

char t[80][80];
int n=0;

int T(int i,int j){
   if(i<0||j<0||j>=L(i)){return 0;}
   char c[]="i";
   c[0]=t[i][j];
   return 1*!!strstr("HIJKLTUVWXYZ",c) + 
          2*!!strstr("CEFGHIKNSTUVWXY",c) +
          4*!!strstr("AFHIJKMNPRSX",c) +
          8*!!strstr("ACEHIKLMQRXZ",c);
}

int f(int i,int j){
   if(i<0||j<0||j>=L(i)||t[i][j]<0){return 0;}
   int z=T(i,j);
   t[i][j]=-1;
   if(z&1&&T(i-1,j-1)&8){f(i-1,j-1);}
   if(z&2&&T(i-1,j+1)&4){f(i-1,j+1);}
   if(z&4&&T(i+1,j-1)&2){f(i+1,j-1);}
   if(z&8&&T(i+1,j+1)&1){f(i+1,j+1);}
   return 1;
}

int main(){
   while(scanf("%s\n",t[n++])>0){};
   n--;
   int c=0;
   for(int i=0;i<n;i++){
      for(int j=0;j<L(i);j++){
         c+=f(i,j);
      }
   }
   printf("%d\n",c);return 0;
}

Results

The result I get from the sample input provided in the question is 714.

\$\endgroup\$
  • \$\begingroup\$ I get 714 when I run my code on your sample. \$\endgroup\$ – Eric Tressler Aug 12 '14 at 16:05
  • \$\begingroup\$ suggestion: too many int declarations in your golfed code. \$\endgroup\$ – edc65 Aug 16 '14 at 18:45
  • \$\begingroup\$ Some other thought (515) ideone.com/EcPdEn \$\endgroup\$ – edc65 Aug 16 '14 at 20:04
  • \$\begingroup\$ @edc65 Thanks a lot for taking the time to go over this; I haven't fully digested your changes yet, but after I understand all of them, I'll update my entry. \$\endgroup\$ – Eric Tressler Aug 17 '14 at 6:01
3
\$\begingroup\$

Python - 437 429

Since forests contain newlines, I've set the input to come from a text file instead.
To run, specify the forest in a file called forest.txt,
save the code as forest_of_alphabets.py
and run from terminal/command line with python forest_of_alphabets.py forest.txt

Code:

import sys
N="@"
g=open(sys.argv[1]).read().replace(" ",N).split()
u=max(map(len,g))+1
g=[list(k)+[N]*(u-len(k))for k in g]+[[N]*u]
def f(y,x,a=0):
 c=g[y][x]
 if c>N:
    l=[zip([-1,-1,1,1],[1,-1]*2)[i]for i in 0,1,2,3if c in"CHAAEICFFJEHGKHIHLIJITKKKULMNVMNSWQPTXRRUYXSVZZXW___X___Y"[i::4]]
    if a<1 or a in l:g[y][x]=N;return[f(y+j,x+i,(-j,-i))for j,i in l]
 return 0
s=j=0
exec"i=0;exec's+=f(j,i)>0;i+=1;'*u;j+=1;"*len(g)
print s

Any suggestions are welcomed. Did this in a rush during my office break.
Tested with both test cases in this page and those in the alphabet tree question.

Update: Tested with the sample, which yields 714 too. Changed the while loops to the exec which is all the rage these days.

\$\endgroup\$
  • \$\begingroup\$ Thanks for mentioning test cases - I've added a large sample forest to the question. \$\endgroup\$ – trichoplax Aug 11 '14 at 22:28
  • \$\begingroup\$ For anyone wanting to run this code, it requires python 2.7, rather than python 3 \$\endgroup\$ – trichoplax Aug 11 '14 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.