Encuentra el primo contiguo más grande en una cadena

8

Para ser justos, esto se basa en una pregunta de StackExchange, pero es una buena pregunta.

El desafío es bastante simple:

  1. Tomar una cadena de números
  2. Encuentra e imprime el número primo contiguo más grande en la cadena

Puntuación:

  • El menor número de personajes gana.
  • Víctor probablemente será una entrada de golfscript, pero no lo consideraremos en contra de ellos, porque todos nos divertimos y aprendemos cosas, ¿verdad?
  • El ganador será premiado cuando note que en realidad no he marcado el botón verde.

Suposiciones

  • La cadena es solo números
    • Si la cadena contiene letras, puede tener un comportamiento indefinido
  • La cadena contiene al menos 1 primo
    • Si la cadena no contiene 1 número primo válido, puede tener un comportamiento indefinido
  • La velocidad no es una restricción.
    • Use un algoritmo principal más corto sobre uno más rápido.
    • Si su entrada finalmente termina, está bien, solo asegúrese de que pueda suceder antes de la muerte por calor del universo.
  • Se puede suponer que la longitud de la cadena tiene menos de 15 caracteres.

Por ejemplo:

>> Input:  3571
<< Output: 3571

>> Input:  123
<< Output: 23

>> Input:  1236503
<< Output: 236503

>> Input:  46462
<< Output:  2

>> Input:  4684
<< Output: ValueError: max() arg is an empty sequence

>> Input:  460
<< Output: 0   # Note, zero is not a prime, but the above string has no valid prime

>> Input:  4601
<< Output: 601

>> Input:  "12 monkeys is a pretty good movie, but not as good as se7en"
<< Output: ValueError: Fight Club was also good, I find Brad Pitt to be a consistantly good actor.

Posibles implementaciones:

  1. Encuentre todas las subcadenas de la entrada, verifique si son primos. - Legostormtroopr (original)
  2. Encuentre todos los enteros menos que la entrada, verifique si están en la entrada y luego verifique si es primo - Ben Reich
  3. Tome una lista de todos los números primos menos que la entrada, verifique si está en la entrada - daniero
Comunidad
fuente
1
Esto parece básicamente: encontrar una forma de iterar sobre cada subcadena de la cadena y verificar la primalidad de la subcadena. Suena como un problema divertido.
Justin
1
@Quincunx Correcto. Pero quería hacerlo lo más inequívoco posible. Y también descartar referencias de la cultura pop.
1
@Quincunx ¡Sin embargo, ese no es el único algoritmo posible! Vea mi respuesta, que puede describirse como: Iterar sobre todos los enteros menos que la entrada, y determinar el más grande que sea una subcadena de la entrada y sea primo.
Ben Reich
@BenReich O, como hice, iterar sobre todos los números primos menores o iguales a la entrada y ver si están en la cadena.
daniero
1
¿Por qué me importa un campo de juego parejo? Sabemos qué guiones ganan, pero ganar no lo es todo. Haga el código más corto e inteligente posible en su idioma favorito.

Respuestas:

6

GolfScript 40 37

.{`\`?)}+\~),\,{.,(;\{\%!}+,,1=},)\;

Esto observa todos los números menores o iguales a la entrada, se filtra a los que son subcadenas de la entrada y luego se filtra más abajo a los números primos. Luego, toma el elemento más grande (que obviamente tiene la mayor cantidad de dígitos).

Vamos a dividirlo en dos secciones principales:

.{`\`?)}+\~,\,

Esta parte del código se filtra a todas las cadenas enteras contenidas en la entrada. Utiliza acento grave para convertir los números en cadenas y luego ?para determinar el índice de la subcadena. Dado que se ?devuelve -1en el caso de que no haya contención, incremente el uso )para que la salida sea 0para no subcadenas, lo que se comportará bien con el ,filtrado.

{.,(;\{\%!}+,,1=},

Esta parte del código se filtra hasta los números primos contando el número de factores menor que el número dado (un número entero es un factor solo si number factor %!es 1. Un número primo tendrá exactamente 1 factor estrictamente menor que él mismo) 1=.

Como los números están en orden, toma el último y limpia la pila usando )\;

Obviamente, esto no es tan eficiente como sea posible (ya que itera innecesariamente sobre todos los enteros menos que la entrada), pero aún termina con una gran entrada como 1236503relativamente rápido en mi computadora (1 minuto).

Ben Reich
fuente
1
Gracias a ti afeité casi tantas respuestas como
1
Si la entrada es un número primo, esto no lo encontrará, porque el primer filtro se aplica a los números hasta, pero sin incluirlo. La corrección cuesta un carácter, pero hay dos caracteres que se guardarán almacenando la entrada en una variable en lugar de concatenar con el bloque (porque de esa manera elimina algunos volteos).
Peter Taylor
4

Python 2.7 - 84

Aquí hay una implementación de referencia para superar, la usé para el resultado de ejemplo en la pregunta, por lo que está garantizado que funcione * No es una garantía real

Mejora descarada basada en la solución mucho mejor de Ben Reich que la original. Con la mayor asistencia de Volatility

N=input()
print max(x for x in range(N+1)if(`x`in`N`)&all(x%i for i in range(2,x)))

Los encantamientos anteriores de la segunda línea incluyen:

print max(x for x in range(N+1)if`x`in`N`and 0 not in(x%i for i in range(2,x)))
print max(x for x in range(N+1)if`x`in`N`and sum(x%i<1 for i in range(2,x))<1)

La versión original - 143

N=`input()`
p=lambda n:[n%i for i in range(2,n)if n%i==0]
print max(int(N[j:i])for i in range(len(N)+1)for j in range(i)if not p(int(N[j:i])))
Comunidad
fuente
2
Deshágase py reemplácelo not p(x)con sum(x%i for i in range(2,x))<1: debería funcionar y reducirlo a 86 caracteres.
Volatilidad
@Volatility No del todo, sum(x%i for i in range(2,x))será bastante alto para la mayoría de los números. Pero el generador es una gran idea y lo llegué a 91.
En realidad, sabes qué, creo que puedes usar all(x%i for i in range(2,x))en su lugar.
Volatilidad
Ahorra uno más, gracias :)
¡Cambiando ally ahorrando entre los (`x`in`N`)ahorrados unos cuantos más también!
1

Rubí 61

Tome todos los números primos hasta N y vea si están en la cadena

require'prime'
p Prime.each(gets.to_i).select{|i|~/#{i}/}.max

Creo que esto solo funciona en Ruby 1.9 y versiones posteriores, pero no estoy seguro.

daniero
fuente
¿Qué devuelve su programa para el último ejemplo de prueba? El primer, 2, está en él, pero no debe ser reconocido (si entiendo los requisitos correctamente).
DavidC
1
@DavidCarraher: Suposiciones: la cadena es solo números; Si la cadena contiene letras, es posible que tenga un comportamiento indefinido . Creo que "comportamiento indefinido" significa que podría escupir 2 o escupir papilla
Kyle Kanos
Kyle, ¡Muy buena observación!
DavidC
1

Scala (83 caracteres)

No estaba seguro de cómo proporcionar entradas al programa, así que consideré nla entrada. Aquí está la solución real (según la cual se evalúa la longitud de la solución). Debajo de eso hay una forma ejecutable de la solución (que aún no está desarrollada) para su ejecución junto con la salida (para las muestras que da OP).

Solución:

n.inits.flatMap(_.tails.toList.init.map(BigInt(_))).filter(_ isProbablePrime 1).max

Solución ejecutable:

object A {
  def main(x:Array[String])=List("3571","123","23","1236503","46462","4684","460","4601","12 monkeys..").foreach(e=>println(e+" => "+q(e)))

  private def p(n: String)=n.inits.flatMap(_.tails.toList.init.map(BigInt(_))).filter(_ isProbablePrime 1).max
  private def q(n: String)=try p(n)catch{case e=>e.toString}
}

Salida de muestra:

3571 => 3571
123 => 23
23 => 23
1236503 => 236503
46462 => 2
4684 => java.lang.UnsupportedOperationException: empty.max
460 => java.lang.UnsupportedOperationException: empty.max
4601 => 601
12 monkeys.. => java.lang.NumberFormatException: For input string: "12 "

Explicación:

Los pasos son bastante sencillos.

input -> Buscar todas las subcadenas -> filtrar no primos -> buscar el valor más largo

  • main(Array[String]): El método proporciona una entrada de muestra y ejecuta el método q(String)para cada entrada
  • q(String): Ajusta la lógica real del programa de p(String)modo que cualquier excepción se informe adecuadamente. Ayuda a formatear mejor la salida porque las entradas no válidas van a llegar NumberFormatExceptiona donde la falta de un primo arrojará unUnsupportedOperationException
  • p(String): Lógica real del programa. Dividamos la explicación de esto en partes
    • n.inits: Crea un Iteratorpara iterar sobre la entrada de cadena ( n)
    • flatMap(f): Aplica una operación en Iteratory empuja el resultado a unList
      • _.tails.toList.init.map(BigInt(_)): Divide Stringy elimina los Strings vacíos de la resultante List. Finalmente convierte el Stringa a BigIntque es equivalente a java.math.BigInteger. Por razones de golf, BigIntse selecciona (nombre más corto).
    • filter(f): si fdevuelve false, el valor se elimina de la resultanteList
      • _ isProbablePrime 1: Esta línea podría haberse escrito como _.isProbablePrime(1)pero la representación utilizada guarda 1 byte. Esta línea en realidad verifica si el valor es primo (probabilísticamente; dado que certaintyestá configurado como 1, el tiempo de ejecución aumenta pero el sistema se asegura (más o menos) de que el número es primo.
    • max: Encuentra el valor máximo ( Stringlongitud no basada. Valor máximo real)
javatarz
fuente
1

J ( 24 22)

Leer desde el teclado es en realidad más corto que definir una función.

>./(*1&p:);".\.\1!:1[1

Prueba:

   >./(*1&p:);".\.\1!:1[1
3571
3571
   >./(*1&p:);".\.\1!:1[1
46462
2
   >./(*1&p:);".\.\1!:1[1
1236503
236503
   >./(*1&p:);".\.\1!:1[1
4684
0
   >./(*1&p:);".\.\1!:1[1
4680
0
   >./(*1&p:);".\.\1!:1[1
twelve monkeys is a pretty good movie
__

Explicación:

  • 1!:1[1: lee una línea de texto desde el teclado
  • ".\.\: la evaluación ( ".) de cada sufijo ( \.) de cada prefijo ( \) de la cadena.
  • ;: aplanar la matriz
  • *1&p:: multiplique cada valor por si es primo o no (por lo que todos los no primos serán cero)
  • >./: obtener el mayor valor en la lista
marinus
fuente
1

Haskell, 94

main=getLine>>=print.maximum.filter(\x->and$map((0/=).mod x)[2..x-1]).map read.init.scanr(:)[]

Vektorweg
fuente
3
¿Te importaría explicar el proceso detrás de esto para aquellos que no hacen Haskell?
@LegoStormtroopr Claro, lo intento. main = getLine >>= print . maximum . filter isPrime . map read . allNumsEs la forma original. obtiene una línea y le da ( >>=) a la gran función combinada, combinada con el .operador infijo, que simplemente coloca el resultado de la función derecha en la función izquierda. cosas como (\x -> ...)son expresiones lambda. los parámetros de la función se aplican sin paréntesis y las funciones se pueden aplicar parcialmente ( (0/=)por ejemplo, es una función que verifica si un número no es 0).
Vektorweg
allNums = init . scanr (:) []. scanrexplora e inicializa elimina el último valor del resultado del explorador, que es una cadena vacía, que no se puede leer en un entero. map readlee una lista de cadenas a sus valores destinados. en este caso, Integer u otra cosa de la clase de tipos Integral, porque isPrimenecesita una Integral. filter isPrimehace exactamente lo que dice. isPrime x = and $ map ((0/=). mod x) [2..(x-1)]significa, dada una lista de 2 a (x-1), hacer la verificación de división y luego aplicar anda la lista Bool.
Vektorweg
Hay algunas funciones más claras y potentes en otros módulos estándar, pero intenté trabajar solo con el módulo Prelude. ;)
Vektorweg
1

Perl 6 (40 caracteres, 41 bytes)

$_=get;say max grep &is-prime,+«m:ex/.+/

Primera getentrada en $_, esto acorta la llamada de coincidencia de expresiones regulares. :exda una concordancia exhaustiva para la expresión regular, dará todas las posibilidades. El hiperoperador (o +<<también funciona) creará números con los objetos Match, a los que se pasa grepcon &is-primesub como selector. Finalmente, tome el máximo de la lista restante y envíela.

Ayiko
fuente
0

Mathematica 67 47

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&

Explicación

El código es una función pura. No tiene nombre En él, #representa la cadena de entrada completa.

StringCasestoma la entrada, # y comprueba las subcadenas, ade un carácter o más (es por eso que se usó __ en lugar de _) que son primos; PrimeQ debe devolver True para la subcadena.

Todos los casos favorables, es decir, las subcadenas que son primos, se devuelven por defecto en una lista. 〚1〛, o [[1]]toma la primera parte, es decir, el primer elemento de esa lista de primos. element[[1]]es la abreviatura Part[element, 1]. Si hay más de un primo, el primero será el primo más largo ( StringCasesverifica primero las subcadenas más largas).

Ejemplos

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&["1236503"]

"236503"

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&/@ 
{"1236503", "123", "46462", "4684", "460", "4601", 
"12 monkeys is a pretty good movie, but not as good as se7en"}

{"236503", "23", "2", {} [[1]], {} [[1]], "601", "2"}

DavidC
fuente
¿Te importaría explicar el proceso detrás de esto para aquellos que no hacen Mathematica?
1
Debo decir que el uso de 〚1〛personajes fue sádico para nosotros, no matemáticos, programadores. (localización frenéticamente me preocupaba que me estoy quedando ciego, a continuación, buscar en otros soportes con la confusión que aparezcan nítidamente, mientras que éste no es!)
eithed
〚1〛tiene corchetes dobles y es equivalente a [[1]]. Los usé porque un paréntesis doble cuenta como un solo carácter.
DavidC
@David Carraher Sí, pero creo que tienes que contarlo como dos bytes para que realmente no te ahorre nada.
Michael Stern el
Pero estoy contando caracteres, no bytes. Por favor explique.
DavidC
0

Perl 6 (50 caracteres, 51 bytes)

say max +«get.match(/(.+)<?{(+$0).is-prime}>/,:ex)

asigna cadenas a números, maxobtiene el mayor número, getrecibe una línea./(.+)<?{(+$0).is-prime}>/es una expresión regular que obtiene todos los primos <?{}>es una aserción de código. is-primees Intun método de clase que verifica si el número es primo. Necesito convertir el valor en número usando +, porque es Strpor defecto. :exsignifica que intenta encontrar TODAS las coincidencias (incluidas aquellas en las que se superponen otras). Debido al error de Rakudo Perl, actualmente es imposible de usar m//aquí.

Esto funciona para cualquier número, y si elimina max (o lo reemplaza sort) obtendrá una lista de todos los números primos en el número, para obtener un bono adicional (no es que esto le dé puntos, ni nada). Por ejemplo (con sorten este caso):

1234567890
2 3 5 7 23 67 89 4567 23456789
Konrad Borowski
fuente