Cuerdas Primarias

27

Una cadena primaria ( binaria-prima ) es aquella que, cuando se escribe como una cuadrícula binaria, cada fila y columna tiene un total primo.

Esa es una explicación bastante vaga, así que analicemos con un ejemplo trabajado ...

Para este ejemplo usaremos la cadena bunny:

Primero, encuentre el punto de código ASCII de cada carácter y su representación binaria:

Char | ASCII | Binary

b      98      1100010
u      117     1110101
n      110     1101110
n      110     1101110
y      121     1111001

Tome estos valores binarios, de arriba a abajo, y organícelos en cuadrícula (agregando ceros a la izquierda si es necesario):

1 1 0 0 0 1 0
1 1 1 0 1 0 1
1 1 0 1 1 1 0
1 1 0 1 1 1 0
1 1 1 1 0 0 1

Luego, cuente el número de 1s en cada fila y columna:

1 1 0 0 0 1 0   > 3
1 1 1 0 1 0 1   > 5
1 1 0 1 1 1 0   > 5
1 1 0 1 1 1 0   > 5
1 1 1 1 0 0 1   > 5

v v v v v v v

5 5 2 3 3 3 2

Si, y solo si, cada total es primo (como aquí), entonces la cadena es un primo binario válido.

El reto

Su tarea es crear una función o programa que, cuando se le da una cadena, devuelve / emite truthysi la cadena es primaria, y de lo falsycontrario.

Reglas / Detalles

  • Puede suponer que los caracteres de la cadena siempre estarán en el rango ASCII 33-126(inclusive).
  • La cadena no estará vacía.
  • Una cadena primaria no tiene que tener una longitud principal; por ejemplo, W1n*es válida, a pesar de tener 4 caracteres.
  • Este es el código de golf , por lo que gana la respuesta más corta (en bytes), pero todas las presentaciones son bienvenidas.
  • Las lagunas estándar están prohibidas.

Casos de prueba

'husband'     -> True
'HOTJava'     -> True
'COmPaTIBILE' -> True
'AuT0HACk'    -> True

'PPCW'        -> False
'code-golf'   -> False
'C++'         -> False
'/kD'         -> False

'HI'          -> False
'A'           -> False

También hay un ejemplo de Python que funciona, pero increíblemente detallado en repl.it con el que puede probar su solución.

code-golf string primes binary decision-problem FlipTack
fuente
¿Puedo preguntar cómo descubriste que eso husbandera válido? O alguno de ellos? ¡Gran problema, sin embargo!
Gabriel Benamy
3
@GabrielBenamy ¡Me alegra que alguien haya preguntado! Revisé un archivo de diccionario en línea , probé algunas mayúsculas al azar de cada letra, a veces cambié las letras por números, etc. Luego eché un vistazo a la lista de resultados y elegí un par de casos de prueba que me gustaron
FlipTack el
Se garantiza que cada entrada de 1-2 caracteres regrese False, ¿correcto?
mbomb007
... porque 0y 1no son primos, y se garantiza que cada cadena de entrada de caracteres 1-2 que contiene solo caracteres en el rango dado contiene al menos uno 0o 1como una suma vertical. Debe agregar algunas cadenas de caracteres 1 y 2 como casos de prueba.
mbomb007
@ mbomb007 Las entradas de 1 carácter no pueden tener números primos en columnas, por lo que volverán false. 2 entradas de caracteres podrían, pero no en el rango ASCII que estamos usando, por lo que para este escenario está en lo correcto.
FlipTack

Respuestas:

8

MATL, 10 bytes

BtXsw!shZp

Pruébalo en línea!

Este es el lenguaje ideal para el trabajo. Es más o menos una transcripción literal de la especificación de desafío.

Bt % Converts input to binary matrix, duplicate
Xs  % Sum columns (alternative X version to prevent defaulting to sum along first non-singleton dimension, thanks @Jonathan Allan)
w! % Get the duplicate to the top of the stack, transpose
s  % Sum again
h  % Concatenate horizontally
Zp % Check primality element-wise. Display implicitly.

Dado que cualquier cero hace que una matriz MATL sea falsa según el meta , no se necesita nada más, básicamente, Ase llama a un implícito ?(if).

Sanchises
fuente
adebería ser falso, pero vuelve 1 1? (sus columnas no se suman a los números primos)
FlipTack
Creo BtXsw!shZpque solucionaría esto y sería un ganador para 10.
Jonathan Allan
@ Flp.Tck Olvidé por completo el comportamiento 'indulgente' de MATLAB al trabajar con vectores de fila. Lo siento, lo arreglé ahora.
Sanchises
Funciona ahora :) (es posible que desee actualizar el enlace de prueba en línea aunque)
FlipTack
@ Flp.Tkc Hecho. Gracias por un buen desafío!
Sanchises
4

Jalea , 13 12 11 bytes

OBUZ;$S€ÆPẠ

TryItOnline! o todos los casos de prueba

¿Cómo?

OBUZ;$S€ÆPẠ - Main link: word                  e.g. ha!
O           - cast to ordinals                 e.g. [104,97,33]
 B          - convert to binary                e.g. [[1,1,0,1,0,0,0],[1,1,0,0,0,0,1],[1,0,0,0,0,1]]
  U         - reverse each entry (say "b")     e.g. [[0,0,0,1,0,1,1],[1,0,0,0,0,1,1],[1,0,0,0,0,1]]
     $      - last two links as a monad
   Z        - transpose                        e.g. [[0,1,1],[0,0,0],[0,0,0],[1,0,0],[0,0,0],[1,1,1],[1,1]]
    ;       - concatenate with "b"             e.g. [[0,1,1],[0,0,0],[0,0,0],[1,0,0],[0,0,0],[1,1,1],[1,1],[0,0,0,1,0,1,1],[1,0,0,0,0,1,1],[1,0,0,0,0,1]]
      S€    - sum €ach                         e.g. [2,0,0,1,0,3,2,3,3,2]
        ÆP  - is prime (1 if prime, 0 if not)  e.g. [1,0,0,0,0,1,1,1,1,1]
          Ạ - all truthy?                      e.g. 0
Jonathan Allan
fuente
3

Jalea , 15 bytes

O+⁹Bṫ€3µS€;SÆPP

Pruébalo en línea! o Verificar todos los casos de prueba. .

Explicación

O+⁹Bṫ€3µS€;SÆPP  Main link. Input: string z
O                Ordinal, get ASCII value of each char
  ⁹              Nilad representing 256
 +               Add 256 to each ordinal value
   B             Binary digits of each
    ṫ€3          Tail, take each list of digits from the 3rd value to the end
                 These are the last seven digits of each
       µ         Start a new monadic chain
        S€       Sum each list of digits by rows
           S     Sum by column
          ;      Concatenate
            ÆP   Test if each is prime, 1 if true else 0
              P  Product
millas
fuente
3

Mathematica, 75 bytes

And@@Join@@PrimeQ@{+##&@@#,+##&@@@#}&@IntegerDigits[ToCharacterCode@#,2,7]&

Función sin nombre que toma una cadena como entrada y devuelve Trueo False.

ToCharacterCode@#convierte la entrada en la lista de sus valores ASCII; IntegerDigits[...,2,7]convierte cada valor en la lista de sus bits, rellenado a la longitud 7 si es necesario. Así que ahora tenemos una matriz 2D y queremos todas sus sumas de filas y sumas de columnas; he aquí, el carácter-espasmo {+##&@@#,+##&@@@#}&@...hace exactamente eso (aplica la función +##&"sumar todos los argumentos" a la lista de vectores en la primera coordenada usando @@, y a cada vector como su propia lista de enteros en la segunda coordenada usando @@@) . Luego, solo verificamos si los resultados son PrimeQ, aplanamos la lista Join@@y tomamos Andtodos esos valores.

Greg Martin
fuente
2

Ruby -rprime , 100 bytes

->s{a=s.bytes.map{|b|b.digits 2}
a.all?{|r|r.sum.prime?}&([0]*7).zip(*a).all?{|c|c.count(1).prime?}}

Pruébalo en línea!

Explicación

->s{
    a=s.bytes                       # Get byte values from string
             .map{|b|b.digits 2}    # For each, map it to its binary digits
                                    #   (least significant digits first)
a.all?{|r|r.sum.prime?}             # Each character has a prime number of 1's?
    &                               # Bit-and (because it saves bytes here)
    ([0]*7).zip(*a)                 # Zip bit array with an all-zero array
                                    #   (If we don't, then uneven array lengths
                                    #   cause some columns to not be returned.)
    .all?{|c|c.count(1).prime?}     # All columns have a prime number of 1's?
                                    #   (We use count instead of sum here because
                                    #   zip pads columns with trailing nils, which
                                    #   can't be added to numbers via sum.)
}
Tinta de valor
fuente
1

Perl, 151 121 111 + 3 = 114 bytes

Corre con -lF. El programa solo funcionará correctamente para la primera entrada. Termine el programa y vuelva a ejecutarlo para su próxima entrada.

Gracias a @Dada por dejarme saber que los //despues Ffueron redundantes. Se puede eliminar un byte adicional (para 112) conectando la entrada a través de via echo -n, pero creo que técnicamente está agregando más código, por lo que YMMV.

for$c(@a=map{sprintf"%07b",ord}@F){$b[$_].=substr$c,$_,1 for 0..6}s/0//g,$d|=/^1?$|^(11+?)\1+$/ for@a,@b;say!$d

Legible:

                                     #Implicitly split input into characters in @F array
for$c(@a=map{sprintf"%07b",ord}@F)  #Convert @F to 7-bit binary as @a, then loop through it                        
    $b[$_].=substr$c,$_,1 for 0..6   #Transpose @a's bits into @b
}
s/0//g,$d|=/^1?$|^(11+?)\1+$/ for@a,@b; #Remove any zeros, then run through composite regex
say!$d                          #If all composite regex checks fail, then it's fully prime.
Gabriel Benamy
fuente
1
Una versión que solo funciona en la primera entrada está perfectamente bien, por lo que puede colocar la versión de 141 bytes como la principal y sugerir la otra para usar en múltiples entradas.
Dada
También tenga en cuenta que puede omitir el //después -Fy puede tomar la entrada sin una nueva línea final (con echo -n) para deshacerse de la -lbandera.
Dada
1

Python 3, 228 227 225 bytes

No es una gran respuesta, no pude jugar al golf tanto como me hubiera gustado, pero pasé tanto tiempo en él que creo que debería publicarlo. Las sugerencias sobre el corte de bytes serían muy apreciadas.

r=range
n=[format(ord(c),"08b")for c in input()]
n=map(lambda s:s.count("1"),n+["".join([f[1]for f in filter(lambda e:e[0]%8<1,enumerate("X"*-~i+"".join(n)))][1:])for i in r(8)])
print(all(all(s%d for d in r(2,s))for s in n))

Edición 1: reemplazado e[0]%8==0por e[0]%8<1, perdiendo un byte. Gracias Flp.Tkc!

Edición 2: reemplazo (i + 1) con - ~ i, perdiendo dos bytes adicionales. Gracias Erik por exponer cuán malo es mi conocimiento de nivel de bits :) Al probar esta revisión, descubrí que kappaes válida ... haz de eso lo que quieras.

Cuatro oh cuatro
fuente
1
se puede cambiar e[0]%8==0a e[0]%8<1?
FlipTack
@ Flp.Tkc ¡Buen lugar! No hay razón para que eso no se pueda hacer.
FourOhFour
1
@ Flp.Tkc No creo que pueda guardar bytes haciéndolo una función. Me gusta cómo tienes 404 rep. Por cierto :)
FourOhFour
Se supone que debe ser <1, <0¿ no ?
Destructible Lemon
@ Sandía Destructible sí, déjame corregir eso.
FourOhFour
1

Groovy, 151 137 bytes

{p={x->x<3||(2..(x**0.5)).every{x%it}};y={it.every{p(it.count("1"))}};x=it.collect{0.toString((int)it,2) as List};y(x)&&y(x.transpose())}

Sin verificación de primalidad en groovy ...

p={x->x<3||(2..(x**0.5)).every{x%it}}; - Cierre para pruebas de primalidad.

y={it.every{p(it.count("1"))}}; - Cierre para garantizar que todos los recuentos de "1" para una matriz 2D binaria aprobada sean primos.

x=it.collect{0.toString((int)it,2) as List}; - Coversion de cadena a matriz binaria.

y(x)&&y(x.transpose()) - Para todas las sumas con validación principal en la matriz principal y la matriz transpuesta, asegúrese de que devuelvan verdadero.

Urna de pulpo mágico
fuente
1

Pyth , 37 bytes

L.AmP_sdb=sMM.[L\0lh.MlZQ=.BMQ&yZy.TZ

Pruébalo en línea!

                                 Code | Explanation
--------------------------------------+----------------------------------------------------------------
L.AmP_sdb=sMM.[L\0lh.MlZQ=.BMQ&yZy.TZ | Full code
L                                     | Define function y(b):
   m    b                             |   For each d in b:
    P_sd                              |     Is the sum of the elements of the list prime?
 .A                                   |   Return whether all elements of the resulting list are truthy
                         =   Q        | Assign the following to Q:
                          .BMQ        |   The list of binary strings for each character in the input
         =             Z              | Assign the following to Z:
               L             Q        |   For every element in Q:
             .[ \0                    |     Pad with 0 on the left
                  lh.MlZQ             |     To the length of the longest element in Q
            M                         |   For each element in the resulting list:
          sM                          |     Convert each character to an integer
                              &yZ     | Print y(Z) AND
                                 y.TZ |   y( <Transpose of Z> )
hakr14
fuente
1

Brachylog , 14 bytes

ạḃᵐB↔ᵐz₁,B+ᵐṗᵐ

Pruébalo en línea!

Salidas por éxito o fracaso. (En el caso de éxito, una lista de todas las sumas de columnas y filas está disponible a través de la variable de salida.

   B              The variable B is
ạ                 the codepoints of the input
 ḃᵐ               converted to lists of binary digits,
    ↔ᵐ            which with each list reversed
      z₁          then zipped without cycling
        ,B        and concatenated with B
          +ᵐ      has elements which all sum to
            ṗᵐ    prime numbers.
Cadena no relacionada
fuente
1

O5AB1E, 12 bytes

Çžy+bø€SOp¦W

Pruébalo en línea!

Este es mi primer código de golf, así que ve fácil :)

Ç              % Converts the implicit input into ascii values
 žy+           % Adds 128 to each value, inspired by Emigna as a way to pad zeros
    b          % Convert all values into bits
     ø         % Transpose
      €SO      % Sum each string of binary digits created
         p¦    % Check if each element is prime and cut the first element out (adding 128 makes it equal to the number of characters)
           W   % Take the minimum value to effectively "and" all the elements
Alex Waese-Perlman
fuente
Esto produce un resultado vacío para una entrada de una sola letra. No estoy bien versado en O5AB1E, pero si ese es un valor falso, está bien.
Sanchises
1

Python 3 , 209 189 180 171 160 bytes

Calamar Thanx para -9 bytes :)

def p(s):n=s.count('1');return(n>1)*all(n%i for i in range(2,n))
def f(s):t=[f'{ord(c):07b}'for c in s];return all(map(p,t+[[u[j]for u in t]for j in range(7)]))

Pruébalo en línea!

movatica
fuente
Me gusta cómo reescribiste la declaración de impresión del caso de prueba :)
movatica
Sí, soy un obsesivo obsesivo compulsivo con las cadenas f ... Además, ¿no es equivalente si eliminas t+la declaración del mapa?
Restablece a Mónica el
No, porque la verificación principal debe cubrir tanto las filas como las columnas en la matriz de bits. ttiene todas las filas, mientras que [[t[i][j]..i..]..j..]se transpone t, es decir, las columnas. Si hay una forma más corta de transponer la matriz, podemos guardar más bytes :)
movatica
Está funcionando cuando lo intento , ¿sabes de una cadena que lo rompe?
Restablece a Monica el
Sí. beezzdebería devolver falso, pero no lo hace. Es porque la verificación principal está rota, regresa Truepor 4 bits. Tratar print(p('1111')). Lo arregló ahora. Todos los casos de prueba no cubrieron eso, porque todos los caracteres utilizados son primarios.
movatica
1

K (oK) , 40 33 bytes

Solución:

&/{2=+/d=_d:x%!x}'+/'m,+m:(7#2)\'

Pruébalo en línea!

Explicación:

La mitad es crear la matriz, la otra mitad es la verificación de primalidad.

&/{2=+/d=_d:x%!x}'+/'m,+m:(7#2)\' / the solution
                                ' / apply to each (')
                               \  / decode
                          (   )   / do this together
                           7#2    / 7#2 => 2 2 2 2 2 2 2
                        m:        / save as m
                       +          / transpose
                     m,           / append to m
                  +/'             / sum (+/) each (')
                 '                / apply to each
  {             }                 / lambda taking implicit x
              !x                  / range 0..x
            x%                    / x divided by ...
          d:                      / save as d
         _                        / floor
       d=                         / equal to d?
     +/                           / sum (+/)
   2=                             / equal to 2?
&/                                / minimum
callejero
fuente
0

PHP, 173 bytes

for($r=1;$b=substr_count($t[$i]=sprintf('%07b',ord($argv[1][$i++])),1);)$r&=$b==2|$b%2&$b>2;for(;$k++<7;){for($b=$j=0;$t[++$j];$b+=$t[$j][$k-1]);$r&=$b==2|$b%2&$b>2;}echo$r;

Pruébelo en línea

Cripto
fuente
0

JavaScript, 234 bytes

f=z=>(z=[...z].map(v=>v.charCodeAt(0))).map(v=>v.toString(2).replace(/0/g,"").length).every((p=v=>{for(i=2;i<v;i++){if(v%i===0){return 0}};return v>1}))&&[...""+1e6].map((v,i)=>z.reduce((a,e)=>!!(e&Math.pow(2,i))+a,0)).every(v=>p(v))

Obtenemos los valores horizontales al convertir el número a binario, eliminando los ceros usando un reemplazo de cadena y luego contando los 1s. Las sumas verticales se obtienen haciendo un bucle de 1 a 7 y usando un bit Y con 2 elevado a la enésima potencia.

Grax32
fuente
Math.pow(2,i)se puede acortar a (1<<i)suponer i<32, tal vez guardar 7 bytes, tal vez no.
Naruyoko
0

Clojure, 180 bytes

#(let[S(for[i %](for[j[1 2 4 8 16 32 64]](min(bit-and(int i)j)1)))A apply](not-any?(fn[i](or(= i 1)(seq(for[d(range 2 i):when(=(mod i d)0)]d))))(into(for[s S](A + s))(A map + S))))

Puede haber una forma más corta de generar listas de bits y también la prueba de primalidad.

NikoNyrh
fuente
0

Perl 5 -MList::Util=all,sum -pF , 96 92 bytes

$_=all{//;all{$'%$_}2..$_-1}(map{$_=sprintf'%07b',ord;y/1//}@F),map{sum map{s/.//;$&}@F}0..6

Pruébalo en línea!

Xcali
fuente
0

Python 3, 164 bytes

import numpy;a=numpy.array([list(f'{ord(_):07b}')for _ in input()]).astype(int);print(all([(v>1)*all(v%i for i in range(2,v))for v in set(a.sum(0))|set(a.sum(1))]))
Zulfiqaar
fuente
0

Ruby 2.7 -rprime, 95 bytes

->s{a=s.bytes.map{[*@1.digits(2),0][..6]}
(a.map(&:sum)+a.transpose.map(&:sum)).all?(&:prime?)}

No hay enlace de TiO porque TiO todavía ejecuta Ruby 2.5.5. 😭

Explicación

Bastante simple. La primera línea obtiene los dígitos binarios de cada carácter como una matriz rellenada con siete dígitos, lo que realmente debería ser más fácil:

a = s.bytes.map { [*@1.digits(2), 0][..6] }

Salida que numerada parámetro de bloque ( @1) y rango beginless ( ..6) picor .

La segunda línea suma las filas y columnas y prueba si todas son primas:

(a.map(&:sum) + a.transpose.map(&:sum)).all?(&:prime?)
Jordán
fuente
0

JavaScript (Node.js) , 149 146 ... 134 130 129 bytes

x=>[...x].map(y=>a=[...a.map(n=>y.charCodeAt()&2**i++?++z&&-~n:n,z=i=0),z],a=[...Array(7)])&&!a.some(n=>(P=r=>n%--r?P(r):~-r)(n))

Pruébalo en línea!

Explicación

x=>                        // Main function:
 [...x].map(               //  For each y in x:
  y=>
   a=[...a.map(            //   For each i in range(0, len(a)):
    n=>                   
     y.charCodeAt()&2**i++ //    If y AND 2**i is not zero:
     ?++z&&-~n:n,          //     z = z + 1; a[i] = a[i] + 1 (1 if a[i] is undefined)
    z=i=0                  //   Initially z = 0
   ),z],                   //   Then push z at the end of a
  a=[...Array(7)]          //  Initially a = [undefined] * 7
 )&&!a.some(               //  Then for each n in a:
  n=>(
   P=r=>                   //   Composite function:
    n%--r?                 //    If n % (r - 1) == 0 or r == 1:
     P(r)                  //     Return P(r - 1)
    :~-r                   //    Else: Return r - 2
  )(n)                     //   Starting from r = n
 )                         //  Return whether the composite function returns 0 for all n.

¿Cómo funciona?

  • y.charCodeAt()&2**i
    • Necesitamos este código para devolver el bit correspondiente de y.charCodeAt()if 0 <= i < 7, y 0 de lo contrario.
    • Cuando i < 7, el código aparentemente funciona como de costumbre.
    • Cuando 7 <= i <= 32, dado que el bit correspondiente de y.charCodeAt()es 0 de todos modos, el resultado es 0 como se esperaba.
    • Cuando 32 < i < 1024, desde entonces int32(2**i) == 0, el resultado es 0 como se esperaba.
    • Cuando 1024 <= i, tenemos 2**i == Infinity, y desde entonces int32(Infinity) == 0, el resultado es 0 como se esperaba.
  • (P=r=>n%--r?P(r):~-r)(n)
    • Por simplicidad lo dejamos R = --r = r - 1.
    • Esta función auxiliar termina cuando n % R == 0o n % R is NaN.
      • n % R == 0: Res un factor de n.
        • Si R == 1, entonces nes primo porque no todos 1 < R < npueden dividirse n. Devuelve 0 (falso).
        • Si R == -1, entonces n == 0. Regresar -2 (verdad).
        • De lo contrario, regrese a R - 1donde R - 1 > 0(verdad).
      • n % R is NaN: Cálculo modular no válido.
        • Si R == 0: n == 1. Regreso -1 (verdad).
        • Si n is NaN: R is NaN. Regreso -1 (verdad).
    • Como resultado, solo cuando R == 1esta función puede devolver un valor falso, indicando que nes primo.
Shieru Asakoto
fuente