Sp|Lit wo(r)dS, S(P)lit wO|rds

Question

m|Y bR|ain is We|iRd. F(o)R T(h)E La|sT fi(v)e YE|ars O|R s|o, (I) ha|ve C(u)T wO|rds in h(a)lf wh|En (I) s(e)e Th|em. Wh|EN I started Do|ing it, it To|oK a meN|TaL effort - B(u)T I almost cou(l)dn't N(o)T d|o it. N(o)w, I d|o it in the back of my head, a(n)d hardly ev|en not|iCe it. However, I thought this wo|uld make a great challenge.

Definitions

For this challenge, each letter is given a point score, based on my judgement of its width in a sans-serif font. You will use this width to cut a word into two halves of equal width. The characters that this challenge will use are the alphabet in lower and upper cases, apostrophe, and hyphen.

Width  Characters
1      i l I '
2      f j r t -
3      a b c d e g h k n o p q s u v x y z
4      m w A B C D E F G H J K L N O P Q R S T U V X Y Z
5      M W

For my explanations and test cases, | denotes the location in which a word can be cleanly split in half. ( and ) on either side of a letter indicate that that letter will be split in half to create a clean split.

Input

Input will consist of a single "word" (which is not required to be in the dictionary). You can take this word in whatever text input you would like (String, char array, etc.). This word will only contain letters, ', and - (see above table). Because of what you will do with this word (see below), case of input is left to the developer's discretion. Trailing newlines allowed if needed.

The Task

Permutate through all forms of the input (all letters at all possible upper or lower case positions). For example, for input it's, the below is all permutations:

it's
it'S
iT's
iT'S
It's
It'S
IT's
IT'S

To split a permutation of a word in half, the points on one side of the word must be the same as the points of the other side of the word. However, if a letter is stuck in between two even sections, you can also cut a letter cleanly in half.

Please note that "half" does not mean that you have moved halfway into the string. "Half" means that the points on both sides are equal.

Examples:

W is 5 points. i is 1 point. Splitting the permutation Wiiiii in half will result in W | iiiii, with 5 points on each side of the |.

T is 3 points. Splitting the permutation TTTT in half will result in TT | TT, with 6 points on each side of the |.

w is 4 points. a is 3 points. Splitting the permutation waw in half will result in w (a) w, with 5.5 points on each side. The points from a are distributed to both sides, as a is split in half.

Output

Your output is an integer of the number of unique permutations of the input that can be cleanly split in half. Trailing newlines allowed if needed.

Test Cases

I will be outputting all valid permutations of the input for the test cases. Remember that that is not part of the specs for you.

In my intermediate output, the numbers indicate the point value of the letter above them, so the output is a bit easier to visualize.

Input: a
( a ) 
  3   
( A ) 
  4   
Output: 2

Input: in
Output: 0

Input: ab
A | B 
4   4 
a | b 
3   3 
Output: 2

Input: abc
A ( B ) C 
4   4   4 
A ( b ) C 
4   3   4 
a ( B ) c 
3   4   3 
a ( b ) c 
3   3   3 
Output: 4

Input: will
W ( I ) L l 
5   1   4 1 
W ( I ) l L 
5   1   1 4 
W ( i ) L l 
5   1   4 1 
W ( i ) l L 
5   1   1 4 
w I | L l 
4 1   4 1 
w I | l L 
4 1   1 4 
w i | L l 
4 1   4 1 
w i | l L 
4 1   1 4 
Output: 8

Input: stephen
S T E ( P ) H E N 
4 4 4   4   4 4 4 
S T E ( p ) H E N 
4 4 4   3   4 4 4 
S T E | p h e n 
4 4 4   3 3 3 3 
S T e ( P ) H E n 
4 4 3   4   4 4 3 
S T e ( P ) H e N 
4 4 3   4   4 3 4 
S T e ( P ) h E N 
4 4 3   4   3 4 4 
S T e ( p ) H E n 
4 4 3   3   4 4 3 
S T e ( p ) H e N 
4 4 3   3   4 3 4 
S T e ( p ) h E N 
4 4 3   3   3 4 4 
S t E ( P ) H e n 
4 2 4   4   4 3 3 
S t E ( P ) h E n 
4 2 4   4   3 4 3 
S t E ( P ) h e N 
4 2 4   4   3 3 4 
S t E ( p ) H e n 
4 2 4   3   4 3 3 
S t E ( p ) h E n 
4 2 4   3   3 4 3 
S t E ( p ) h e N 
4 2 4   3   3 3 4 
S t e ( P ) h e n 
4 2 3   4   3 3 3 
S t e p | H E N 
4 2 3 3   4 4 4 
S t e ( p ) h e n 
4 2 3   3   3 3 3 
s T E ( P ) H E n 
3 4 4   4   4 4 3 
s T E ( P ) H e N 
3 4 4   4   4 3 4 
s T E ( P ) h E N 
3 4 4   4   3 4 4 
s T E ( p ) H E n 
3 4 4   3   4 4 3 
s T E ( p ) H e N 
3 4 4   3   4 3 4 
s T E ( p ) h E N 
3 4 4   3   3 4 4 
s T e ( P ) H e n 
3 4 3   4   4 3 3 
s T e ( P ) h E n 
3 4 3   4   3 4 3 
s T e ( P ) h e N 
3 4 3   4   3 3 4 
s T e ( p ) H e n 
3 4 3   3   4 3 3 
s T e ( p ) h E n 
3 4 3   3   3 4 3 
s T e ( p ) h e N 
3 4 3   3   3 3 4 
s t E ( P ) h e n 
3 2 4   4   3 3 3 
s t E p | H E N 
3 2 4 3   4 4 4 
s t E ( p ) h e n 
3 2 4   3   3 3 3 
s t e P | H E N 
3 2 3 4   4 4 4 
s t e p | H E n 
3 2 3 3   4 4 3 
s t e p | H e N 
3 2 3 3   4 3 4 
s t e p | h E N 
3 2 3 3   3 4 4 
Output: 37

Input: splitwords
S P L I T | W O r d s 
4 4 4 1 4   5 4 2 3 3 
<snip>
s p l i t w | o R d S 
3 3 1 1 2 4   3 4 3 4 
Output: 228

Input: 'a-r
' a ( - ) R 
1 3   2   4 
' a | - r 
1 3   2 2 
Output: 2

Input: '''''-
' ' ' ( ' ) ' - 
1 1 1   1   1 2 
Output: 1

Victory

This is code-golf, so shortest answer in bytes wins. You must be able to output all test cases (so, all inputs up to 10 characters) in a reasonable amount of time. Do not artificially cap your input.

Bounty

I do not know if this is in the realm of possibility. However, you're golfers - you'll do anything for rep. I am offering a 200 rep bounty (I'll start it once this bounty condition is fulfilled, as it seems basically impossible to me) for a program that outputs the correct output for antidisestablishmentarianism in under 15 seconds on an average computer (aka mine). Please note that this test case must not be hard coded in any way.

@DigitalTrauma crushed my bounty, coming in well under two seconds. Check out his answer here.

Answer 1

c, 378 bytes; about 0.6s for antidisestablishmentarianism

Updated answer. I read @JonathanAllan's comment about is, and at first I didn't understand this optimization, but now I see that since both i and I have a width of 1, then we can count the associated permutations twice with only having to validate once. Previously my solution used multiple threads to spread the load over multiple CPUs and with that I was just about able to go through all 2²⁸ possibilities on my machine. Now with the i optimization there is no need to mess with threads - a single thread does the job easily within the time restriction.

Without further ado - golfed c function:

char m[128]={[39]=10,[45]=20};f(s,l,p)char *s;{m[65]?:bcopy("PPPPPPPPPPPdPPPPPPPPPdPPP      <<<<<(<<(<P<<<<(<(<<P<<<",m+65,58);int g,h,u=0,v=0,x=0,y=0,c=0;if(p<l){g=s[p];if(g>64&&g-'i'){s[p]-=32;c+=f(s,l,p+1);}s[p]=g;c+=((g=='i')+1)*f(s,l,p+1);}else{for(l--,p=0,g=m[s[p]],h=m[s[l]];p<=l;){y=v;x=u;if(u+g>v+h){v+=h;h=m[s[--l]];}else{u+=g;g=m[s[++p]];}}c=u==v||y==x;}return c;}

The recursive function f takes 3 parameters - a pointer to the input string, the string length and the offset in the string to start processing (should be 0 for top-level call). The function returns the number of permutations.

Try it online. TIO seems to typically run through all testcases (including antidisestablishmentarianism in under 2 seconds.

Note that there are some unprintables in the string that is bcopy()ed to m[]. The TIO seems to handle these correctly.

Ungolfed:

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
#include <assert.h>

int width_tbl[] = {
    ['\''] = 1,
    ['-'] = 2,
    ['A'] = 4,4,4,4,4,4,4,4,1,4,4,4,5,4,4,4,4,4,4,4,4,4,5,4,4,4,
    ['a'] = 3,3,3,3,3,2,3,3,1,2,3,1,4,3,3,3,3,2,3,2,3,3,4,3,3,3
};

int
f (char *str, int len, int pos) {
    int lidx, ridx;
    int tot_width = 0;
    int lwidth, rwidth;
    int tot_lwidth = 0, tot_rwidth = 0;
    int prev_tot_lwidth = 0, prev_tot_rwidth = 0;
    char tmp;
    int perm_cnt = 0;
    
    if (pos < len) {
        tmp = str[pos];
        if (isalpha(tmp) && (tmp != 'i')) {
            str[pos] = toupper(str[pos]);
            perm_cnt += f(str, len, pos+1);
        }
        str[pos] = tmp;
        perm_cnt += ((tmp == 'i') + 1) * f(str, len, pos+1);
    } else {
        //puts(str);
        lidx = 0;
        ridx = len - 1;
        lwidth = width_tbl[str[lidx]];
        rwidth = width_tbl[str[ridx]];
        while (lidx <= ridx) {
            prev_tot_rwidth = tot_rwidth;
            prev_tot_lwidth = tot_lwidth;
            if (tot_lwidth + lwidth > tot_rwidth + rwidth) {
                tot_rwidth += rwidth;
                rwidth = width_tbl[str[--ridx]];
            } else {
                tot_lwidth += lwidth;
                lwidth = width_tbl[str[++lidx]];
            }
        }
        if (tot_lwidth == tot_rwidth) {
            perm_cnt = 1;
        } else if (prev_tot_rwidth == prev_tot_lwidth) {
            perm_cnt = 1;
        }
    }
    return perm_cnt;
}


int main (int argc, char **argv) {
    int i;
    int perm_cnt;

    if (argc > 0) {
        char *str = strdup(argv[1]);
        assert(str);
    
        perm_cnt = f(str, strlen(str), 0);

        printf("n = %d\n", perm_cnt);
    }
    
    return 0;
}

I have a mid-2015 MacBook Pro running MacOS 10.12.4. The compiler is the default MacOS clang. I am compiling with:

cc splitwords.c -O2 -o splitwords

Running all testcases, including antidisestablishmentarianism gives:

$ time ./splitwords
Testcase "a": n = 2
Testcase "in": n = 0
Testcase "ab": n = 2
Testcase "abc": n = 4
Testcase "will": n = 8
Testcase "stephen": n = 37
Testcase "splitwords": n = 228
Testcase "'a-r": n = 2
Testcase "'''''-": n = 1
Testcase "antidisestablishmentarianism": n = 83307040

real    0m0.573s
user    0m0.564s
sys 0m0.003s
$

This is by no means optimal. The algorithm simply brute-forces its way through all possibilities (modulo i - see comments above), and counts the words that may be split according to the criteria.

Answer 2

Pyth, 75 74 73 70 bytes

lfsm}sT-Bysded._Tm.n]d*Fmm?k|qd\i+4}d"mw"|}d"il'"h|}d"fjrt-"+2}d"mw"-2}d"'-
lfsm}sT-Bysded._Tm.n]d*Fmm?k|qd\i+4}d"mw"|x}Ld+c"mw il' fjrt-")G1 4-2}d"'-
lfsm}sT-Bysded._Tm.n]d*Fm<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"-2}d"'-
lfsm}sT-Bysded._Tm.n]d*Fm<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"h}dG

Try it online!

For the love of God, please don't even try antidisestablishmentarianism in the interpreter. You'll crash it.

Explanation

lfsm}sT-Bysded._Tm.n]d*Fm<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"h}dG

Let us break down this code into X parts.

The first part: generating cased versions and mapping to the values

m<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"h}dG

Let us be clear here. In no part of the process are letters capitalized. We just need to map one letter to two values (and the punctuation marks to one value), without the need of capitalizing them. We'll be deciding for which characters we will be needing two values, and for which characters we will be needing one:

m<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"h}dGQ  Q implicitly appended
m                                             Q  for d in Q:
                                           }dG       d in alphabet?
                                          h          +1 (T/F as 1/0)
 <   take the first ^ elements of the following array
     for d in alphabet, it will take 2 elements;
     for d being ' or -, it will take 1 element.
  ,          pair up the following two values
   |x}Ld+c"mw il' fjrt-")G1 4                  this is the first value
                             |qd\i+4}d"mw"    this is the second value

As you see, even the first part is too long.

The first value is for lowercase version, which includes ' and -. The second value is for uppercase version, with ' and - will not take.

The first value:

|x}Ld+c"mw il' fjrt-")G1 4
       "mw il' fjrt-"        does what it says on the tin
      c              )       split on spaces, creating an
                             array with three elements
     +                G      append another element, which
                             is the alphabet, as a fail-safe;
                             now the array has 4 elements
  }Ld                        check if d is in each array
                             as with above, True becomes 1
                             and False becomes 0 (T/F as 1/0)
 x                     1     find the first occurrence of 1
|                        4   logical or with 4. If it was 0,
                             it would become 4 now.

The first string contains "mw" at index 0. It has a value of 4, which explains the need of the logical or. Note that Pyth uses 0-indexing. Also, the space before the 4 is to separate it from 1.

The second value (uppercase):

|qd\i+4}d"mw"
 qd\i          d=="i"
|              logical OR
       }d"mw"  is d in "mw"? That is, is d "m" or "w"?
     +4        +4

If d is "i", then it gives 1 on the first step. Otherwise, it continues. If d is "m" or "w", then the third step gives 1, which is added to 4 to give 5. If d is not "m" or "w", then the third step gives 0, which is added to 4 to give 4.

The second part: getting the job done

lfsm}sT-Bysded._Tm.n]d*F

This is prepended to the first part, which technically is not separated from the second part (it is still one command). So, the value from the first part is passed to the right.

Recap: in the first part, we mapped the letters to their possible values (lowercase and uppercase for letters, just one value for the two punctuation marks). For input "ab", one would get [[3,4],[3,4]].

To generate the different cased versions (which should have been done in the first part, but that would overflow), we use the Cartesian product repeatedly, and then flatten the result. Problems arise when there is only one letter (first testcase), because the Cartesian product would not give us an array, and the flatten command (.n) is overflowed to give strange results to numbers. We'll see how I circumvented this issue.

lfsm}sT-Bysded._Tm.n]d*F
                      *F  reduce by Cartesian product
                 m   d    for d in each unflattened version:
                    ]         [d] (wrap in array)
                  .n          flatten
 f                filter for resulting arrays as T
              ._T all prefixes of T
   m              for d in each prefix:
          sd          find the sum of d
         y            double
       -B   ed        [above, above - last element of d]
    }sT               is the sum of T in the above array of 2 elements?
  s               sum the 1/0 generated in each prefix
                  any non-zero value is regarded as truthy
l                 length

If it is a split in the middle by |, then the prefix would have the sum doubled being the sum of the total.

If it is split by (), then the prefix sum doubled minus the value in parentheses would be the sum of the total.

Answer 3

JavaScript (ES6), 199 169 167 bytes

Expects the input string in lower case. Too slow for the bounty.

f=(s,r=[],t=R=0,i=3,x=parseInt("k1048cccctt"["i'l-fjrtmw".search(c=s[0])+1],36)+8>>i&7)=>x&&(c?(i&&f(s,r,t,0),f(s.slice(1),[x,...r],t+x)):R+=r.some(x=>t==x|!(t-=2*x)))

Test cases

f=(s,r=[],t=R=0,i=3,x=parseInt("k1048cccctt"["i'l-fjrtmw".search(c=s[0])+1],36)+8>>i&7)=>x&&(c?(i&&f(s,r,t,0),f(s.slice(1),[x,...r],t+x)):R+=r.some(x=>t==x|!(t-=2*x)))

;[ "a", "in", "ab", "abc", "will", "stephen", "splitwords", "'a-r", "'''''-" ]
.map(
  s => console.log(s, '->', f(s))
)

Answer 4

C, 403 394 bytes,

Thanks Kevin!

r;char*g[]={"","ilI'","fjrt-","","mw","MW",0},**p,b[99];q(c){for(p=g;*p;p++)if(strchr(*p,c))return p-g;return c>='a'&&c<='z'?3:4;}f(char*w,int l){int i,n,c,t,x,y;if(*w){for(i=0;i<2;i++)x=tolower(*w),y=toupper(*w),!i||x!=y?b[l]=i%2?x:y,b[l+1]=0,f(w+1,l+1):0;}else{t=0;for(c=0;c<2;c++)for(i=0;i<l;i++){x=y=0;for(n=0;n<l;n++)c==0||n!=i?((n<i)?(x+=q(b[n])):(y+=q(b[n]))):0;t|=x==y;}r+=t;}return r;}

Try it online

Ungolfed code:

int getwidth(int c)
{
    char **p, *g[] = { "", "ilI'", "fjrt-", "", "mw", "MW", 0};
    for (p=g; *p; p++)
    {
        if (strchr(*p,c))
            return p-g;
    }
    return c >= 'a' && c <= 'z' ? 3 : 4;
}

int test(char* w, int l)
{
    int i, n, c, t, x, y;

    if (*w)
    {
        for (i=0;i<2; i++)
        {
            x = tolower(*w);
            y = toupper(*w);
            if (!i || x != y)
            {
                b[l] = i % 2 ? x : y;
                b[l + 1] = 0;
                test(w + 1, l+1);
            }
        }
    }
    else
    {
        t = 0;
        for (c=0; c<2; c++)
        {
            for (i=0; i<l; i++)
            {
                x = 0;
                y = 0;
                for (n=0; n<l; n++)
                {
                    if (c == 0 || n != i)
                    {
                        if (n < i)
                            x += getwidth(b[n]);
                        else
                            y += getwidth(b[n]);
                    }
                }
                t |= x == y;
            }
        }
        r += t;
    }
    return r;
}