Divide una palabra en partes con puntajes iguales

9

Suponiendo que A = 1, B = 2 ... Z = 26, y el valor de una palabra es la suma de estos valores de letras, es posible dividir algunas palabras en dos partes para que tengan valores iguales.

Por ejemplo, "divisor de palabras" se puede dividir en dos partes así: ordsl wpit, porque o + r + d + s + l = w + p + i + t.

Este fue un desafío que nos dio mi maestro de computación, aparentemente es un viejo desafío de Lionhead Studios. Lo he resuelto en Python, y publicaré mi respuesta en breve.

Desafío: el programa más corto que puede enumerar todas las divisiones posibles que tienen puntajes iguales. Tenga en cuenta que solo tiene que enumerar una para cada grupo de letras: ordsl wpit es lo mismo que rdosl wtip, por ejemplo. Es más fácil enumerarlos en el orden en que aparecen en la palabra.

Prima:

  • Si resalta pares donde ambas palabras son palabras válidas en inglés (o alguna permutación de las letras es), use una lista de palabras de algún tipo. (Esto podría hacerse colocando un asterisco al lado de cada uno u otro método, pero que quede claro).
  • Agregar la opción para eliminar duplicados (esto no debería ser el predeterminado).
  • Admite más de dos divisiones, por ejemplo, divisiones de tres, cuatro o incluso n-way.
Thomas O
fuente
¿El programa debe admitir entradas de mayúsculas y minúsculas? Y si es así, ¿puede descartar el caso de la salida?
Nemo157
@ Nemo157 Puede ignorar el caso y no tiene que preservarlo en la salida.
Thomas O
¿Puede el programa generar cosas adicionales, siempre que la parte solicitada de la salida sea clara para un humano?
JB
@JB Sí, puede.
Thomas O
ok, mejoraré ese Perl entonces;) Gracias
JB

Respuestas:

4

Perl, 115 118 123

@_=~/./g;for$i(1..1<<@_){$l=$
r;$i&1<<$_?$l:$r+=64-ord$_[$_
]for 0..$#_;$l-$r||$i&1<<$_&&
print$_[$_]for 0..$#_;say""}

Corre con perl -nE '<code goes here>'. Esa 'n' se cuenta en el tamaño del código.

Respaced:

@_ = /./g;
for $i (1 .. 1<<@_) {
  $l = $r;
  $i & 1<<$_ ? $l : $r -= 64 - ord $_[$_] for 0 .. $#_;

  $l - $r      ||
  $i & 1<<$_   &&
  print $_[$_]
    for 0 .. $#_;

  say ""
}

Con comentarios y nombres de variables:

# split a line of input by character
@chars = /./g;

# generate all binary masks of same length
for $mask (1 .. 1<<@_) {

  # start at "zero"
  $left_sum = $right_sum;

  # depending on mask, choose left or right count
  # 1 -> char goes left; 0 -> char goes right
  $mask & 1<<$_ ? $left_sum : $right_sum
    -= 64 - ord $chars[$_]   # add letter value
      for 0 .. $#chars;      # for all bits in mask

  # if left = right
  $left_sum - $right_sum ||

  # if character was counted left (mask[i] = 1)
  $mask & 1<<$_          &&

  # print it
  print $chars[$_]

  # ...iterating on all bits in mask
    for 0 .. $#chars;

  # newline
  say ""
}

Algunos de los trucos utilizados:

  • 1..1<<@_cubre el mismo rango de bits 0..(1<<@_)-1, pero es más corto. (tenga en cuenta que considerar el problema desde más lejos, incluyendo los límites del rango varias veces, no daría como resultado una salida incorrecta de todos modos)
  • $ left_range y $ right_range no se restablecen al cero numérico "0" real: como los acumulamos y los comparamos al final, todo lo que necesitamos es que comiencen con el mismo valor.
  • restar en 64-ord$_[$_]lugar de sumar ord$_[$_]-64gana un carácter invisible: dado que termina con un delimitador, hace que el espacio antes sea forinnecesario.
  • Perl le permite asignar a una variable determinada por el operador condicional ternario: cond ? var1 : var2 = new_value.
  • expresiones booleanas encadenadas con &&y ||se usan en lugar de condicionales apropiados.
  • $l-$r es más corto que $l!=$r
  • generará una nueva línea incluso en divisiones que no se equilibran. ¡Las líneas vacías están bien según las reglas! ¡Yo pregunté!
JB
fuente
¿Te importaría explicar a aquellos de nosotros que no hablamos ruido de línea? Parece que está utilizando un enfoque de máscara binaria similar al mío, y veo que el 64 significa '@' = 'A' - 1, y después de eso estoy bastante perdido.
dmckee --- ex gatito moderador
¿Es esta edición algo mejor?
JB
Agradable. Tengo que pensar en aprovechar la suma de cada cuenta a la izquierda o la suma de la derecha. Debería haber sido obvio, pero lo extrañé.
dmckee --- gatito ex moderador
3

J (109)

~.(/:{[)@:{&a.@(96&+)&.>>(>@(=/@:(+/"1&>)&.>)#[),}.@(split~&.>i.@#@>)@<@(96-~a.&i.)"1([{~(i.@!A.i.)@#)1!:1[1

Salida para wordsplit:

┌─────┬─────┐
│lorw │dipst│
├─────┼─────┤
│diltw│oprs │
├─────┼─────┤
│iptw │dlors│
├─────┼─────┤
│dlors│iptw │
├─────┼─────┤
│oprs │diltw│
├─────┼─────┤
│dipst│lorw │
└─────┴─────┘

Explicación:

  • 1!:1[1: leer una línea de stdin
  • ([{~(i.@!A.i.)@#): obtener todas las permutaciones
  • "1: para cada permutación:
  • (96-~a.&i.): obtener puntajes de letras
  • }.@(split~&.>i.@#@>)@<: divide cada permutación de las puntuaciones en cada espacio posible, excepto antes del primero y después del último número
  • >(>@(=/@:(+/"1&>)&.>)#[): vea qué permutaciones tienen mitades coincidentes y seleccione estas
  • {&a.@(96&+)&.>: convierte las puntuaciones de nuevo en letras
  • ~.(/:{[): eliminar variaciones triviales (p. ej. ordsl wpity ordsl wpti)
marinus
fuente
Algunas de sus respuestas son duplicados.
DavidC
@DavidCarraher: Bueno, o soy ciego o este no lo es, ni mis respuestas recientes. Nunca he copiado las respuestas de otras personas a propósito, aunque por supuesto podrías estar en lo cierto, he publicado aquí mientras estoy borracho a veces y no lo recuerdo hasta que recibí muchos votos negativos y resultó que había enviado algo que ni siquiera estaba cerca de corregir Si me ha visto portarse mal, tal vez deje el comentario donde me estoy portando mal, entonces eliminaré cualquier respuesta ofensiva; o tal vez los rechacen, ya que para eso están los votos negativos.
Marinus
No se pretendía desaprobar. Simplemente quise decir, por ejemplo, que su primera respuesta, {"lorw", "dipst"} es un duplicado de su respuesta final, {"dipst", "lorw"}. Solo el orden de las palabras es diferente.
DavidC
@DavidCarraher: whoops: PI pensó que querías decir que había copiado la respuesta de alguien ... de todos modos, esta pregunta dice (si lo he interpretado bien) eliminar los duplicados donde las partes individuales son solo permutaciones entre sí, pero no eliminar aquellos en los que el orden de las partes es diferente, es decir, si {a,bc}ya se encuentra, eliminar {a,cb}pero no eliminar {bc,a}. (Y, por supuesto, no me ofende, si realmente / hubiera / duplicado la respuesta de alguien, preferiría que alguien lo señalara)
Marinus
Parece que tienes razón. Las instrucciones dicen que está bien ignorar el orden de las palabras ("Tenga en cuenta que solo tiene que enumerar una para cada grupo de letras"), pero no lo requieren. Esto puede salvarme algunos personajes. Gracias.
DavidC
2

c99 - 379 caracteres necesarios

#include <stdio.h>
#include <string.h>
#include <ctype.h>
int s(char*w,int l,int m){int b,t=0;for(b=0;b<l;++b){t+=(m&1<<b)?toupper(w[b])-64:0;}return t;}
void p(char*w,int l,int m){for(int b=0;b<l;++b){putchar((m&1<<b)?w[b]:32);}}
int main(){char w[99];gets(w);int i,l=strlen(w),m=(1<<l),t=s(w,l,m-1);
for(i=0;i<m;i++){if(s(w,l,i)==t/2){p(w,l,i);putchar(9);p(w,l,~i);putchar(10);}}}

El enfoque es bastante obvio. Hay una función que suma las palabras según una máscara y una que también la imprime según una máscara. Entrada desde la entrada estándar. Una rareza es que la rutina de impresión inserta espacios para letras que no están en la máscara. Se utiliza una pestaña para separar los grupos.

No hago ninguno de los artículos de bonificación, ni se convierte fácilmente para apoyarlos.

Legible y comentado:

#include <stdio.h>
#include <string.h>
#include <ctype.h>
int s(char *w, int l, int m){ /* word, length, mask */
  int b,t=0;                  /* bit and total */
  for (b=0; b<l; ++b){        
/*     printf("Summing %d %d %c %d\n",b,m&(1<<b),w[b],toupper(w[b])-'A'-1); */
    t+=(m&1<<b)?toupper(w[b])-64:0; /* Add to toal if masked (A-1 = @ = 64) */
  }
  return t;
}
void p(char *w, int l, int m){
  for (int b=0; b<l; ++b){ 
    putchar((m&1<<b)?w[b]:32);  /* print if masked (space = 32) */
  }
}
int main(){
  char w[99];
  gets(w);
  int i,l=strlen(w),m=(1<<l),t=s(w,l,m-1);
/*   printf("Word is '%s'\n",w); */
/*   printf("...length %d\n",l); */
/*   printf("...mask   0x%x\n",m-1); */
/*   printf("...total  %d\n",t); */
  for (i=0; i<m; i++){
/*     printf("testing with mask 0x%x...\n",i); */
    if (s(w,l,i)==t/2) {p(w,l,i); putchar(9); p(w,l,~i); putchar(10);}
    /* (tab = 9; newline = 10) */
  }
}

Validación

 $ wc wordsplit_golf.c
  7  24 385 wordsplit_golf.c
 $ gcc -std=c99 wordsplit_golf.c
 $ echo wordsplit | ./a.out
warning: this program uses gets(), which is unsafe.
 or sp          w  d  lit
wor   l            dsp it
 ords l         w    p it
w    p it        ords l  
   dsp it       wor   l  
w  d  lit        or sp   
dmckee --- gatito ex moderador
fuente
1

Rubí: 125 caracteres

r=->a{a.reduce(0){|t,c|t+=c.ord-96}}
f=r[w=gets.chomp.chars]
w.size.times{|n|w.combination(n).map{|s|p([s,w-s])if r[s]*2==f}}

Ejecución de muestra:

bash-4.2$ ruby -e 'r=->a{a.reduce(0){|t,c|t+=c.ord-96}};f=r[w=gets.chomp.chars.to_a];w.size.times{|p|w.combination(p).map{|q|p([q,w-q])if r[q]*2==f}}' <<< 'wordsplit'
[["w", "o", "r", "l"], ["d", "s", "p", "i", "t"]]
[["w", "p", "i", "t"], ["o", "r", "d", "s", "l"]]
[["o", "r", "s", "p"], ["w", "d", "l", "i", "t"]]
[["w", "d", "l", "i", "t"], ["o", "r", "s", "p"]]
[["o", "r", "d", "s", "l"], ["w", "p", "i", "t"]]
[["d", "s", "p", "i", "t"], ["w", "o", "r", "l"]]
hombre trabajando
fuente
1

Mathematica 123 111

Encuentra todos los subconjuntos de palabras que tienen la media "ascii total" de la palabra, d. Luego encuentra los complementos de esos subconjuntos.

d = "WORDSPLIT"

{#, Complement[w, #]}&/@Cases[Subsets@#,x_/;Tr@x==Tr@#/2]&[Sort[ToCharacterCode@d - 64]];
FromCharacterCode[# + 64] & /@ %

{{"IPTW", "DLORS"}, {"LORW", "DIPST"}, {"OPRS", "DILTW"}, {"DILTW", "OPRS"}, {"DIPST", "LORW"} , {"DLORS", "IPTW"}}

DavidC
fuente
1

J, 66 caracteres

Usando dígitos de números base2 para seleccionar cada subconjunto posible.

   f=.3 :'(;~y&-.)"{y#~a#~(=|.)+/"1((+32*0&>)96-~a.i.y)#~a=.#:i.2^#y'
   f 'WordSplit'
┌─────┬─────┐
│Worl │dSpit│
├─────┼─────┤
│Wdlit│orSp │
├─────┼─────┤
│Wpit │ordSl│
├─────┼─────┤
│ordSl│Wpit │
├─────┼─────┤
│orSp │Wdlit│
├─────┼─────┤
│dSpit│Worl │
└─────┴─────┘
randomra
fuente
0

Mi solución está abajo. Es casi un anti-golf en su tamaño, pero funciona muy bien. Admite divisiones n-way (aunque el tiempo de cálculo se vuelve muy largo para más de aproximadamente 3 divisiones) y admite la eliminación de duplicados.

class WordSplitChecker(object):
    def __init__(self, word, splits=2):
        if len(word) == 0:
            raise ValueError, "word too short!"
        if splits == 0:
            raise ValueError, "splits must be > 1; it is impossible to split a word into zero groups"
        self.word = word
        self.splits = splits

    def solve(self, uniq_solutions=False, progress_notifier=True):
        """To solve this problem, we first need to consider all the possible
        rearrangements of a string into two (or more) groups.

        It turns out that this reduces simply to a base-N counting algorithm,
        each digit coding for which group the letter goes into. Obviously
        the longer the word the more digits needed to count up to, so 
        computation time is very long for larger bases and longer words. It 
        could be sped up by using a precalculated array of numbers in the
        required base, but this requires more memory. (Space-time tradeoff.)

        A progress notifier may be set. If True, the default notifier is used,
        if None, no notifier is used, and if it points to another callable,
        that is used. The callable must take the arguments as (n, count, 
        solutions) where n is the number of iterations, count is the total 
        iteration count and solutions is the length of the solutions list. The
        progress notifier is called at the beginning, on every 1000th iteration, 
        and at the end.

        Returns a list of possible splits. If there are no solutions, returns
        an empty list. Duplicate solutions are removed if the uniq_solutions
        parameter is True."""
        if progress_notifier == True:
           progress_notifier = self.progress 
        solutions = []
        bucket = [0] * len(self.word)
        base_tuple = (self.splits,) * len(self.word)
        # The number of counts we need to do is given by: S^N,
        # where S = number of splits,
        #       N = length of word.
        counts = pow(self.splits, len(self.word))
        # xrange does not create a list in memory, so this will work with very
        # little additional memory.
        for i in xrange(counts):
            groups = self.split_word(self.word, self.splits, bucket)
            group_sums = map(self.score_string, groups)
            if len(set(group_sums)) == 1:
                solutions.append(tuple(groups))
            if callable(progress_notifier) and i % 1000 == 0:
                progress_notifier(i, counts, len(solutions))
            # Increment bucket after doing each group; we want to include the
            # null set (all zeroes.)
            bucket = self.bucket_counter(bucket, base_tuple)
        progress_notifier(i, counts, len(solutions))
        # Now we have computed our results we need to remove the results that
        # are symmetrical if uniq_solutions is True.
        if uniq_solutions:
            uniques = []
            # Sort each of the solutions and turn them into tuples.  Then we can 
            # remove duplicates because they will all be in the same order.
            for sol in solutions:
                uniques.append(tuple(sorted(sol)))
            # Use sets to unique the solutions quickly instead of using our
            # own algorithm.
            uniques = list(set(uniques))
            return sorted(uniques)
        return sorted(solutions)

    def split_word(self, word, splits, bucket):
        """Split the word into groups. The digits in the bucket code for the
        groups in which each character goes in to. For example,

        LIONHEAD with a base of 2 and bucket of 00110100 gives two groups, 
        "LIHAD" and "ONE"."""
        groups = [""] * splits
        for n in range(len(word)):
            groups[bucket[n]] += word[n]
        return groups

    def score_string(self, st):
        """Score and sum the letters in the string, A = 1, B = 2, ... Z = 26."""
        return sum(map(lambda x: ord(x) - 64, st.upper()))

    def bucket_counter(self, bucket, carry):
        """Simple bucket counting. Ex.: When passed a tuple (512, 512, 512)
        and a list [0, 0, 0] it increments each column in the list until
        it overflows, carrying the result over to the next column. This could
        be done with fancy bit shifting, but that wouldn't work with very
        large numbers. This should be fine up to huge numbers. Returns a new
        bucket and assigns the result to the passed list. Similar to most
        counting systems the MSB is on the right, however this is an 
        implementation detail and may change in the future.

        Effectively, for a carry tuple of identical values, this implements a 
        base-N numeral system, where N+1 is the value in the tuple."""
        if len(bucket) != len(carry):
            raise ValueError("bucket and carry lists must be the same size")
        # Increase the last column.
        bucket[-1] += 1 
        # Carry numbers. Carry must be propagated by at least the size of the
        # carry list.
        for i in range(len(carry)):
            for coln, col in enumerate(bucket[:]):
                if col >= carry[coln]:
                    # Reset this column, carry the result over to the next.
                    bucket[coln] = 0
                    bucket[coln - 1] += 1
        return bucket

    def progress(self, n, counts, solutions):
        """Display the progress of the solve operation."""
        print "%d / %d (%.2f%%): %d solutions (non-unique)" % (n + 1, counts, (float(n + 1) / counts) * 100, solutions) 

if __name__ == '__main__':
    word = raw_input('Enter word: ')
    groups = int(raw_input('Enter number of required groups: '))
    unique = raw_input('Unique results only? (enter Y or N): ').upper()
    if unique == 'Y':
        unique = True
    else:
        unique = False
    # Start solving.
    print "Start solving"
    ws = WordSplitChecker(word, groups)
    solutions = ws.solve(unique)
    if len(solutions) == 0:
        print "No solutions could be found."
    for solution in solutions:
        for group in solution:
            print group,
        print

Salida de muestra:

Enter word: wordsplit
Enter number of required groups: 2
Unique results only? (enter Y or N): y
Start solving
1 / 512 (0.20%): 0 solutions (non-unique)
512 / 512 (100.00%): 6 solutions (non-unique)
dspit worl
ordsl wpit
orsp wdlit
Thomas O
fuente
1
En mi opinión, las respuestas que ciertamente hacen un intento cero de cumplir con el objetivo de la pregunta original (brevedad del código) están efectivamente fuera de tema. Admite que esta respuesta no tiene relación con el golf de código, por lo que en lugar de publicarla como respuesta, sugeriría publicarla en otro lugar y poner un enlace en un comentario sobre la pregunta.
Jeff Swensen
2
@Sugerman: es una implementación de referencia, no un intento de ganar el juego. Prefiero implementaciones de referencia como respuestas en lugar de ocupar espacio en la parte superior de la página, y las prefiero en el sitio para eliminar el riesgo de pudrición de enlaces.
dmckee --- gatito ex moderador
@Sugerman: ¿Por qué no enviarlo? Es mejor que nada. Podría minimizarse, pero ¿por qué molestarse? Realmente no puedo aceptar mi propia pregunta (bueno, puedo , pero no está en el espíritu de la misma)
Thomas O
Porque en la base de este, este es un sitio de preguntas y respuestas. Algo que no pretende ser una respuesta no debe publicarse como tal.
Jeff Swensen
1
Como dije en mi primer comentario, me habría vinculado a él en un comentario sobre la Pregunta o, dado que usted es el propietario de la Pregunta, edite el enlace allí. Tampoco tiene nada de malo enviar una respuesta a su propia pregunta siempre que no acepte automáticamente su propia respuesta sin tener en cuenta todas las demás (y los resultados de la votación).
Jeff Swensen
0

Lua - 195

a=io.read"*l"for i=0,2^#a/2-1 do z,l=0,""r=l for j=1,#a do b=math.floor(i/2^j*2)%2 z=(b*2-1)*(a:byte(j)-64)+z if b>0 then r=r..a:sub(j,j)else l=l..a:sub(j,j)end end if z==0 then print(l,r)end end

la entrada debe estar en mayúsculas:

~$ lua wordsplit.lua 
>WORDSPLIT
WDLIT   ORSP
DSPIT   WORL
WPIT    ORDSL
mniip
fuente
0

Python - 127

w=rawinput()
for q in range(2**len(w)/2):
 a=[0]*2;b=['']*2
 for c in w:a[q%2]+=ord(c)-96;b[q%2]+=c;q/=2
 if a[0]==a[1]:print b

y aquí una versión n-split con 182 bytes sin duplicados:

n,w=input()
def b(q):
 a=[0]*n;b=['']*n
 for c in w:a[q%n]+=ord(c)-96;b[q%n]+=c;q/=n
 return a[0]==a[1] and all(b) and frozenset(b)
print set(filter(None,map(b,range(n**len(w)/n))))

La entrada es, por ejemplo:

3, 'wordsplit'
Daniel
fuente