m | Y bR | ain to 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 Zacząłem Robić to, to | Ok O MeN | TaL wysiłek - B (u) TI prawie cou (l) nie nie N (o) T d | o it. N (o) w, I d | o to z tyłu głowy, a (n) d ledwie nie | en nie | iCe it. Myślałem jednak, że to będzie duże wyzwanie.

Definicje

Za to wyzwanie każda litera otrzymuje punktową ocenę opartą na mojej ocenie jej szerokości czcionką bezszeryfową. Użyjesz tej szerokości, aby pokroić słowo na dwie połowy o jednakowej szerokości. Znaki, których użyje to wyzwanie, to alfabet pisany małymi i dużymi literami, apostrof i łącznik.

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

Dla moich wyjaśnień i przypadków testowych |oznacza miejsce, w którym słowo może być czysto podzielone na pół. (i) po obu stronach litery wskazuj, że ta litera zostanie podzielona na pół, aby utworzyć czysty podział.

Wejście

Dane wejściowe będą składać się z jednego „słowa” (które nie musi znajdować się w słowniku). Możesz wziąć to słowo w dowolny sposób, jaki chcesz wprowadzić (ciąg znaków, tablica znaków itp.). To słowo będzie zawierać tylko litery 'i- (patrz powyższa tabela). Ze względu na to, co zrobisz z tym słowem (patrz poniżej), przypadek wprowadzenia danych zależy od autora. W razie potrzeby dozwolone są końcowe znaki nowej linii.

Zadanie

Permutuj przez wszystkie formy wprowadzania (wszystkie litery we wszystkich możliwych pozycjach wielkich i małych liter). Na przykład dla danych wejściowych it'sponiżej podano wszystkie permutacje:

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

Aby podzielić permutację słowa na pół, punkty po jednej stronie słowa muszą być takie same jak punkty po drugiej stronie słowa. Jeśli jednak list utknie pomiędzy dwiema równymi sekcjami, możesz go również przeciąć na pół.

Pamiętaj, że „połowa” nie oznacza, że ​​przeszedłeś w połowie do łańcucha. „Połowa” oznacza, że ​​punkty po obu stronach są równe.

Przykłady:

Wwynosi 5 punktów. iwynosi 1 punkt. Podział permutacji Wiiiiina pół spowoduje W | iiiii5 punktów z każdej strony |.

Twynosi 3 punkty. Podział permutacji TTTTna pół spowoduje TT | TT6 punktów po każdej stronie |.

wwynosi 4 punkty. a to 3 punkty. Podział permutacji wawna pół da w (a) w5,5 punktów z każdej strony. Punkty z asą rozdzielane na obie strony, podobnie jak apodzielone na pół.

Wynik

Dane wyjściowe są liczbą całkowitą liczby unikatowych kombinacji danych wejściowych, które można jednoznacznie podzielić na pół. W razie potrzeby dozwolone są końcowe znaki nowej linii.

Przypadki testowe

Będę wyprowadzać wszystkie prawidłowe permutacje danych wejściowych dla przypadków testowych. Pamiętaj, że to nie jest część specyfikacji dla Ciebie.

Na moim pośrednim wyjściu liczby wskazują wartość punktową litery nad nimi, więc wynik jest nieco łatwiejszy do zwizualizowania.

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

Zwycięstwo

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach. Musisz być w stanie wydrukować wszystkie przypadki testowe (czyli wszystkie dane wejściowe do 10 znaków) w rozsądnym czasie. Nie ograniczaj sztucznie wkładu.

Hojność

Nie wiem, czy jest to możliwe. Jesteś jednak golfistą - zrobisz wszystko dla przedstawiciela. Oferuję nagrodę za 200 powtórzeń (rozpocznę ją, gdy ten warunek nagrody zostanie spełniony, ponieważ wydaje mi się to w zasadzie niemożliwe) za program, który generuje prawidłowe wyjście antidisestablishmentarianismw czasie krótszym niż 15 sekund na przeciętnym komputerze (czyli moim). Należy pamiętać, że ten przypadek testowy nie może być w żaden sposób zakodowany na stałe.

@DigitalTrauma zmiażdżył moją nagrodę, dochodząc znacznie poniżej dwóch sekund. Sprawdź jego odpowiedź tutaj .

Pyth , 75 74 73 70 bajtów

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

Wypróbuj online!

Na miłość boską, proszę nawet nie próbuj antidisestablishmentarianismtłumaczyć. Rozbijesz to.

Wyjaśnienie

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

Podzielmy ten kod na części X.

Pierwsza część: generowanie obudowanych wersji i mapowanie na wartości

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

Wyjaśnijmy tutaj. W żadnej części procesu litery nie są wielkie. Musimy tylko odwzorować jedną literę na dwie wartości (i znaki interpunkcyjne na jedną wartość), bez potrzeby ich wielkich liter. Będziemy decydować, dla których znaków będziemy potrzebować dwóch wartości, a dla których znaków będziemy potrzebować jedną:

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

Jak widać, nawet pierwsza część jest za długa.

Pierwsza wartość dotyczy wersji z małymi literami, która obejmuje 'i -. Druga wartość dotyczy wersji z dużymi literami, z 'i -nie będzie pobierana.

Pierwsza wartość:

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

Pierwszy ciąg zawiera "mw"indeks 0. Ma wartość 4, co wyjaśnia potrzebę logicznego lub. Zauważ, że Pyth używa indeksowania 0. Również przestrzeń przed nią 4ma ją oddzielić 1.

Druga wartość (wielkie litery):

|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

Jeśli dtak "i", to daje 1pierwszy krok. W przeciwnym razie trwa. Jeśli djest "m"lub "w", to trzeci krok daje 1, który jest dodawany 4do dać 5. Jeśli dnie "m"lub "w", to trzeci krok daje 0, który dodaje się 4do dawania 4.

Druga część: wykonanie pracy

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

Jest to dodawane do pierwszej części, która technicznie nie jest oddzielona od drugiej części (jest to nadal jedno polecenie). Tak więc wartość z pierwszej części jest przekazywana w prawo.

Podsumowanie: w pierwszej części zamapowaliśmy litery na ich możliwe wartości (małe i wielkie litery dla liter, tylko jedna wartość dla dwóch znaków interpunkcyjnych). Do wejścia "ab"dostaniemy jeden [[3,4],[3,4]].

Aby wygenerować różne wersje w obudowach (co powinno być zrobione w pierwszej części, ale to by się przepełniło), używamy produktu kartezjańskiego wielokrotnie, a następnie spłaszczamy wynik. Problemy pojawiają się, gdy jest tylko jedna litera (pierwsza przypadek testowy), ponieważ iloczyn kartezjański nie dałby nam tablicy, a polecenie spłaszczenia ( .n) zostało przepełnione, aby dać dziwne wyniki liczbom. Zobaczymy, jak obejdę ten problem.

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

Jeśli jest to podział na środek |, wówczas prefiks miałby podwójną sumę będącą sumą sumy.

Jeśli zostanie podzielone (), suma prefiksu podwojona minus wartość w nawiasach będzie sumą sumy.

c, 378 bajtów; około 0,6s dlaantidisestablishmentarianism

Zaktualizowana odpowiedź . Czytałem @ komentarzu JonathanAllan chodzi o is, a na początku nie rozumiałem tej optymalizacji, ale teraz widzę, że skoro oboje ii Imają szerokość 1, wtedy możemy liczyć związane permutacji dwukrotnie tylko konieczności sprawdzania raz. Wcześniej moje rozwiązanie wykorzystywało wiele wątków, aby rozłożyć obciążenie na wiele procesorów, dzięki czemu mogłem prawie przejść przez wszystkie ²⁸ możliwości na moim komputerze. Teraz zi optymalizacją nie ma potrzeby mieszania się z wątkami - pojedynczy wątek łatwo wykonuje zadanie w ograniczonym czasie.

Bez dodatkowej funkcji golfa c:

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

Funkcja rekurencyjna fprzyjmuje 3 parametry - wskaźnik do ciągu wejściowego, długość ciągu i przesunięcie w ciągu, aby rozpocząć przetwarzanie (powinno być 0 dla wywołania najwyższego poziomu). Funkcja zwraca liczbę permutacji.

Wypróbuj online . Wydaje się, że TIO zwykle przebiega przez wszystkie przypadki testowe (w tym antidisestablishmentarianismw czasie poniżej 2 sekund.

Należy zauważyć, że istnieją pewne unprintables w ciąg, który jest bcopy()ed do m[]. Wygląda na to, że TIO obsługuje je poprawnie.

Nie golfowany:

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

Mam MacBooka Pro z połowy 2015 roku z systemem MacOS 10.12.4. Kompilator jest domyślnym językiem MacOS. Kompiluję z:

cc splitwords.c -O2 -o splitwords

Uruchamianie wszystkich przypadków testowych, w tym antidisestablishmentarianismdaje:

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

Nie jest to bynajmniej optymalne. Algorytm po prostu brutalnie przebija wszystkie możliwości (modulo i- patrz komentarze powyżej) i zlicza słowa, które można podzielić według kryteriów.

JavaScript (ES6), 199 169 167 bajtów

Oczekuje, że ciąg wejściowy pisany małymi literami. Za wolno na nagrodę.

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

Przypadki testowe

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 bajtów,

Dzięki, 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;}

Wypróbuj online

Nieskluczony kod:

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