m | Y bR | ain est We | iRd. F (o) RT (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 J'ai commencé à le faire, ça pour | oK un effort meN | TaL - B (u) TI presque cou (l) pas N (o) T d | o it. N (o) w, je l'ai | à l'arrière de ma tête, un (n) d à peine év | en pas | iCe. Cependant, je pensais que cela ferait un grand défi.

Définitions

Pour ce défi, chaque lettre reçoit un score de points, basé sur mon jugement de sa largeur dans une police sans empattement. Vous utiliserez cette largeur pour couper un mot en deux moitiés de largeur égale. Les caractères que ce défi utilisera sont l'alphabet en minuscules et en majuscules, l'apostrophe et le tiret.

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

Pour mes explications et cas de test, |désigne l'emplacement dans lequel un mot peut être proprement divisé en deux. (et )de chaque côté d'une lettre indiquent que cette lettre sera divisée en deux pour créer une division nette.

Contribution

L'entrée consistera en un seul "mot" (qui ne doit pas nécessairement figurer dans le dictionnaire). Vous pouvez prendre ce mot dans la saisie de texte que vous souhaitez (chaîne, tableau de caractères, etc.). Ce mot ne contiendra que les lettres,, 'et -(voir le tableau ci-dessus). En raison de ce que vous ferez avec ce mot (voir ci-dessous), le cas de la saisie est laissé à la discrétion du développeur. Les nouvelles lignes de fin sont autorisées si nécessaire.

La tâche

Permutez à travers toutes les formes de saisie (toutes les lettres à toutes les positions majuscules ou minuscules possibles). Par exemple, pour l'entrée it's, ce qui suit est toutes les permutations:

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

Pour diviser une permutation d'un mot en deux, les points d'un côté du mot doivent être les mêmes que les points de l'autre côté du mot. Cependant, si une lettre est coincée entre deux sections paires, vous pouvez également couper une lettre proprement en deux.

Veuillez noter que «moitié» ne signifie pas que vous vous êtes déplacé à mi-chemin dans la chaîne. "Moitié" signifie que les points des deux côtés sont égaux.

Exemples:

West de 5 points. iest de 1 point. Diviser la permutation Wiiiiien deux se traduira par W | iiiii, avec 5 points de chaque côté de la |.

Test de 3 points. La division de la permutation TTTTen deux se traduira par TT | TT, avec 6 points de chaque côté de la |.

west de 4 points. a est de 3 points. Diviser la permutation wawen deux se traduira par w (a) w, avec 5,5 points de chaque côté. Les points de asont distribués des deux côtés, comme il aest divisé en deux.

Production

Votre sortie est un entier du nombre de permutations uniques de l'entrée qui peuvent être proprement divisées en deux. Les nouvelles lignes de fin sont autorisées si nécessaire.

Cas de test

Je produirai toutes les permutations valides de l'entrée pour les cas de test. N'oubliez pas que cela ne fait pas partie des spécifications pour vous.

Dans ma sortie intermédiaire, les chiffres indiquent la valeur en points de la lettre au-dessus d'eux, donc la sortie est un peu plus facile à visualiser.

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

La victoire

C'est le code-golf , donc la réponse la plus courte en octets l'emporte. Vous devez être en mesure de produire tous les cas de test (donc, toutes les entrées jusqu'à 10 caractères) dans un délai raisonnable. Ne limitez pas artificiellement votre entrée.

Prime

Je ne sais pas si cela est possible. Cependant, vous êtes des golfeurs - vous ferez tout pour le représentant. J'offre une prime de 200 répétitions (je vais la démarrer une fois que cette condition de prime est remplie, car cela me semble fondamentalement impossible) pour un programme qui génère la sortie correcte pendant antidisestablishmentarianismmoins de 15 secondes sur un ordinateur moyen (aka le mien). Veuillez noter que ce cas de test ne doit en aucun cas être codé en dur.

@DigitalTrauma a écrasé ma prime, arrivant bien en moins de deux secondes. Découvrez sa réponse ici .

Pyth , 75 74 73 70 octets

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} ré"'-
 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

Essayez-le en ligne!

Pour l'amour de Dieu, n'essayez même pas antidisestablishmentarianism dans l'interprète. Vous allez le planter.

Explication

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

Décomposons ce code en X parties.

La première partie: génération de versions casées et mise en correspondance avec les valeurs

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

Soyons clairs ici. Dans aucune partie du processus, les lettres ne sont en majuscules. Nous avons juste besoin de mapper une lettre à deux valeurs (et les signes de ponctuation à une valeur), sans avoir besoin de les mettre en majuscule. Nous déciderons pour quels caractères nous aurons besoin de deux valeurs et pour quels caractères nous en aurons besoin:

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

Comme vous le voyez, même la première partie est trop longue.

La première valeur est pour la version minuscule, qui inclut 'et -. La deuxième valeur est pour la version en majuscule, avec 'et -ne prendra pas.

La première valeur:

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

La première chaîne contient "mw"à l'index 0. Elle a une valeur de 4, ce qui explique la nécessité de la logique ou. Notez que Pyth utilise l'indexation 0. De plus, l'espace avant le 4doit le séparer 1.

La deuxième valeur (en majuscule):

|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

Si dc'est le cas "i", cela donne 1la première étape. Sinon, cela continue. Si dest "m"ou "w", alors la troisième étape donne 1, qui est ajoutée 4à donner 5. Si dn'est pas "m"ou "w", alors la troisième étape donne 0, qui est ajoutée 4à donner 4.

La deuxième partie: faire le travail

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

Ceci est ajouté à la première partie, qui n'est techniquement pas séparée de la deuxième partie (il s'agit toujours d'une commande). Ainsi, la valeur de la première partie est passée à droite.

Récapitulation: dans la première partie, nous avons mappé les lettres à leurs valeurs possibles (minuscules et majuscules pour les lettres, une seule valeur pour les deux signes de ponctuation). Pour l'entrée "ab", on obtiendrait [[3,4],[3,4]].

Pour générer les différentes versions casées (ce qui aurait dû être fait dans la première partie, mais qui déborderait), nous utilisons le produit cartésien à plusieurs reprises, puis aplatissons le résultat. Des problèmes surviennent lorsqu'il n'y a qu'une seule lettre (premier cas de test), car le produit cartésien ne nous donnerait pas de tableau et la commande d'aplatissement ( .n) déborde pour donner des résultats étranges aux nombres. Nous verrons comment j'ai contourné ce problème.

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

S'il s'agit d'une scission au milieu par | , alors le préfixe aurait la somme doublée étant la somme du total.

S'il est divisé par (), la somme du préfixe doublée moins la valeur entre parenthèses serait la somme du total.

c, 378 octets; environ 0,6 s pourantidisestablishmentarianism

Réponse mise à jour . J'ai lu le commentaire de @ JonathanAllan sur is, et au début je n'ai pas compris cette optimisation, mais maintenant je vois que puisque les deux iet Iont une largeur de 1, alors nous pouvons compter les permutations associées deux fois sans avoir à valider une seule fois. Auparavant, ma solution utilisait plusieurs threads pour répartir la charge sur plusieurs processeurs et avec cela, j'étais à peu près en mesure de parcourir les 2 ²⁸ possibilités sur ma machine. Maintenant avec lei optimisation, il n'est pas nécessaire de jouer avec les threads - un seul thread fait le travail facilement dans le délai imparti.

Sans plus tarder - fonction c golfée:

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;}

La fonction récursive fprend 3 paramètres - un pointeur sur la chaîne d'entrée, la longueur de la chaîne et le décalage dans la chaîne pour commencer le traitement (devrait être 0 pour l'appel de niveau supérieur). La fonction renvoie le nombre de permutations.

Essayez-le en ligne . TIO semble généralement parcourir tous les tests (y compris antidisestablishmentarianismen moins de 2 secondes).

Notez qu'il y a quelques non imprimables dans la chaîne qui est bcopy() ed pour m[]. Le TIO semble les gérer correctement.

Non golfé:

#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;
}

J'ai un MacBook Pro mi-2015 fonctionnant sous MacOS 10.12.4. Le compilateur est le clang MacOS par défaut. Je compile avec:

cc splitwords.c -O2 -o splitwords

Exécution de tous les tests, y compris antidisestablishmentarianism donne:

$ 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
$

Ce n'est en aucun cas optimal. L'algorithme force simplement son chemin à travers toutes les possibilités (modulo i- voir les commentaires ci-dessus), et compte les mots qui peuvent être divisés selon les critères.

JavaScript (ES6), 199 169 167 octets

Attend la chaîne d'entrée en minuscules. Trop lent pour la prime.

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)))

Cas de test

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))
)

C, 403 394 octets,

Merci 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;}

Essayez-le en ligne

Code non golfé:

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;
}