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

15

m | Y bR | ain es 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 en h (a) lf wh | En (I) s (e) e Th | em. Wh | EN Empecé Haciéndolo, es | oK un meN | TaL esfuerzo - B (u) TI casi podría (l) no N (o) T d | o it. N (o) w, lo hice en la parte de atrás de mi cabeza, a (n) d casi no lo | evito. Sin embargo, pensé que esto sería un gran desafío.

Definiciones

Para este desafío, a cada letra se le asigna un puntaje, basado en mi juicio de su ancho en una fuente sans-serif. Utilizará este ancho para cortar una palabra en dos mitades del mismo ancho. Los caracteres que utilizará este desafío son el alfabeto en minúsculas y mayúsculas, el apóstrofe y el guión.

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

Para mis explicaciones y casos de prueba, |denota la ubicación en la que una palabra se puede dividir limpiamente por la mitad. (y )a cada lado de una letra indica que esa letra se dividirá por la mitad para crear una división limpia.

Entrada

La entrada consistirá en una sola "palabra" (que no se requiere que esté en el diccionario). Puede tomar esta palabra en cualquier entrada de texto que desee (String, char array, etc.). Esta palabra solo contendrá letras ', y -(ver tabla anterior). Debido a lo que harás con esta palabra (ver más abajo), el caso de entrada queda a discreción del desarrollador. Nuevas líneas finales permitidas si es necesario.

La tarea

Permuta a través de todas las formas de la entrada (todas las letras en todas las posiciones mayúsculas o minúsculas posibles). Por ejemplo, para la entrada it's, a continuación se muestran todas las permutaciones:

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

Para dividir una permutación de una palabra por la mitad, los puntos en un lado de la palabra deben ser los mismos que los puntos del otro lado de la palabra. Sin embargo, si una letra está atrapada entre dos secciones pares, también puede cortar una letra limpiamente por la mitad.

Tenga en cuenta que "mitad" no significa que se haya movido hasta la mitad de la cadena. "Medio" significa que los puntos en ambos lados son iguales.

Ejemplos:

WSon 5 puntos. ies 1 punto Dividir la permutación Wiiiiia la mitad dará como resultado W | iiiii, con 5 puntos a cada lado de la |.

TSon 3 puntos. Dividir la permutación TTTTa la mitad dará como resultado TT | TT, con 6 puntos a cada lado de la |.

wSon 4 puntos. a es de 3 puntos. Dividir la permutación wawa la mitad dará como resultado w (a) w, con 5.5 puntos en cada lado. Los puntos de ase distribuyen a ambos lados, como ase divide por la mitad.

Salida

Su salida es un número entero de la cantidad de permutaciones únicas de la entrada que se pueden dividir limpiamente por la mitad. Nuevas líneas finales permitidas si es necesario.

Casos de prueba

Voy a generar todas las permutaciones válidas de la entrada para los casos de prueba. Recuerde que eso no es parte de las especificaciones para usted.

En mi salida intermedia, los números indican el valor en puntos de la letra sobre ellos, por lo que la salida es un poco más fácil de visualizar.

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

Victoria

Este es el , por lo que la respuesta más corta en bytes gana. Debe poder generar todos los casos de prueba (por lo tanto, todas las entradas de hasta 10 caracteres) en un período de tiempo razonable. No limite artificialmente su aporte.

Generosidad

No sé si esto está en el ámbito de la posibilidad. Sin embargo, ustedes son golfistas, harán cualquier cosa por representante. Estoy ofreciendo una recompensa de 200 repeticiones (comenzaré una vez que se cumpla esta condición de recompensa, ya que me parece básicamente imposible) para un programa que genera la salida correcta antidisestablishmentarianismen menos de 15 segundos en una computadora promedio (también conocida como mía). Tenga en cuenta que este caso de prueba no debe estar codificado de ninguna manera.

@DigitalTrauma aplastó mi recompensa, llegando en menos de dos segundos. Mira su respuesta aquí .

Stephen
fuente
2
@MackenzieMcClane, excepto que hay cinco 'i' que lo llevan a 2 ^ 23 = 8,388,608.
Jonathan Allan
2
Mi primer recuento para antidisestablishmentarianism(no golfista) es 83307040(y coincide con todos los casos de prueba) pero tarda ~ 37 segundos en mi computadora portátil (tenga en cuenta que es Python). ¿Alguien también tiene una cuenta para ello?
Jonathan Allan
2
43 segundos en TIO
Jonathan Allan
8
Mi cerebro es raro Estás en el lugar correcto
Luis Mendo
66
No debería intentar hacer lo mismo. No debería intentar hacer lo mismo. Enseñé n (o) tt (r) yt | od | ot (h) e sa | me. O | h cr | ap ...
Arnauld

Respuestas:

8

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

Pruébalo en línea!

Por el amor de Dios, ni siquiera lo intentes antidisestablishmentarianismen el intérprete. Lo estrellarás.

Explicación

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

Desglosemos este código en X partes.

La primera parte: generar versiones encapsuladas y mapeo a los valores

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

Seamos claros aquí. En ninguna parte del proceso las letras están en mayúscula. Solo necesitamos asignar una letra a dos valores (y los signos de puntuación a un valor), sin la necesidad de ponerlos en mayúscula. Decidiremos para qué personajes necesitaremos dos valores y para qué personajes necesitaremos uno:

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

Como puede ver, incluso la primera parte es demasiado larga.

El primer valor es para la versión en minúscula, que incluye 'y -. El segundo valor es para la versión en mayúscula, con 'y -no tomará.

El primer valor:

|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 primera cadena contiene "mw"en el índice 0. Tiene un valor de 4, lo que explica la necesidad de la lógica o. Tenga en cuenta que Pyth usa indexación 0. Además, el espacio antes del 4es separarlo de 1.

El segundo valor (mayúscula):

|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 des así "i", da 1en el primer paso. De lo contrario, continúa. Si des "m"o "w", entonces el tercer paso da 1, que se agrega 4a dar 5. Si dno es "m"o "w", entonces el tercer paso da 0, que se agrega 4a dar 4.

La segunda parte: hacer el trabajo

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

Esto se antepone a la primera parte, que técnicamente no está separada de la segunda parte (sigue siendo un comando). Entonces, el valor de la primera parte se pasa a la derecha.

Resumen: en la primera parte, asignamos las letras a sus posibles valores (minúsculas y mayúsculas para las letras, solo un valor para los dos signos de puntuación). Para la entrada "ab", uno obtendría [[3,4],[3,4]].

Para generar las diferentes versiones encapsuladas (lo que debería haberse hecho en la primera parte, pero que se desbordaría), usamos el producto cartesiano repetidamente y luego aplanamos el resultado. Los problemas surgen cuando solo hay una letra (primer caso de prueba), porque el producto cartesiano no nos daría una matriz, y el comando de aplanar ( .n) se desborda para dar resultados extraños a los números. Veremos cómo eludí este problema.

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

Si es una división en el medio por |, entonces el prefijo tendría la suma duplicada siendo la suma del total.

Si se divide por (), entonces la suma del prefijo duplicado menos el valor entre paréntesis sería la suma del total.

Monja permeable
fuente
Sí, cuando tengo tiempo para hacerlo. (Pido disculpas por mi apretada agenda.)
Leaky Nun
11

c, 378 bytes; aproximadamente 0.6s paraantidisestablishmentarianism

Respuesta actualizada . @ Leí el comentario de JonathanAllan sobre is, y al principio no entendía esta optimización, pero ahora veo que, dado que tanto iy Itener una anchura de 1, entonces podemos contar las permutaciones asociadas dos veces con tener sólo una vez para validar. Anteriormente, mi solución usaba múltiples subprocesos para distribuir la carga en múltiples CPU y con eso pude pasar por las 2 28 posibilidades en mi máquina. Ahora con la ioptimización no hay necesidad de meterse con hilos: un solo hilo hace el trabajo fácilmente dentro de la restricción de tiempo.

Sin más preámbulos, la función c golfizada:

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 función recursiva ftoma 3 parámetros: un puntero a la cadena de entrada, la longitud de la cadena y el desplazamiento en la cadena para comenzar el procesamiento (debe ser 0 para la llamada de nivel superior). La función devuelve el número de permutaciones.

Pruébalo en línea . TIO parece correr típicamente a través de todos los casos de prueba (incluso antidisestablishmentarianismen menos de 2 segundos.

Tenga en cuenta que hay algunos no imprimibles en la cadena en la que se bcopy()edita m[]. El TIO parece manejar esto correctamente.

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

Tengo una MacBook Pro de mediados de 2015 con MacOS 10.12.4. El compilador es el clang predeterminado de MacOS. Estoy compilando con:

cc splitwords.c -O2 -o splitwords

Ejecutar todos los casos de prueba, incluyendo antidisestablishmentarianismda:

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

Esto de ninguna manera es óptimo. El algoritmo simplemente se abre paso por todas las posibilidades (módulo i- vea los comentarios anteriores), y cuenta las palabras que pueden dividirse de acuerdo con los criterios.

Trauma digital
fuente
Buen trabajo, realmente creo que es probable que sea posible evaluar el resultado en O (n), usando los efectos fijos de las 7 clases de letra, i, -, ', l, mw, fjrt, y abcdeghknopqsuvxyz, pero se necesitaría una aplicación de la Pólya enumeración teorema (o un método de enumeración combinatoria equivalente), en el que no estoy bien versado.
Jonathan Allan
Destruiste mis expectativas, como esperaba. Así es como usas la recursión :)
Stephen
1

JavaScript (ES6), 199 169 167 bytes

Espera la cadena de entrada en minúsculas. Demasiado lento para la recompensa.

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

Casos de prueba

Arnauld
fuente
1

C, 403 394 bytes,

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

Pruébalo en línea

Código sin 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;
}
Johan du Toit
fuente
Olvidó jugar al golf en algunos espacios aquí: f(char* w, int l){->f(char*w,int l){
Kevin Cruijssen