La densidad de dígitos de números cuadrados (SNDD) de un número, inventada por mí mismo, es la relación entre el recuento de números cuadrados encontrados en dígitos consecutivos y la longitud del número. Por ejemplo, 169 es un número de 3 dígitos que contiene 4 números cuadrados (1, 9, 16, 169) y, por lo tanto, tiene una densidad de dígitos de 4/3 o 1,33. El número de 4 dígitos 1444 tiene 6 cuadrados (1, 4, 4, 4, 144, 1444) y, por lo tanto, una relación de 6/4 o 1.5. Observe en el ejemplo anterior que los cuadrados pueden repetirse. Además, 441 no está permitido, porque no se puede encontrar consecutivamente dentro del número 1444.

Su tarea es escribir un programa que busque un rango dado A - B (inclusive) para el número con la mayor densidad de dígitos del número cuadrado. Su programa debe cumplir con las siguientes especificaciones:

• Tome la entrada A, B en el rango de 1 a 1,000,000,000 (1 billón). Ejemplo:sndd 50 1000
• Devuelve como resultado el número con el mayor SNDD. En caso de empate, devuelva el número más pequeño.
• 0 no cuenta como un cuadrado en ninguna forma, 0, 00, 000, etc. Tampoco los cuadrados que comienzan con 0, como 049 o 0049.
• Tenga en cuenta que el número completo no tiene que ser un número cuadrado.

Ejemplos:

sndd 14000 15000
Output: 14441

sndd 300 500
Output: 441

Bonificación: ¿Cuál es el número con el mayor SNDD entre 1 y 1,000,000,000? ¿Puede probar si este es el más grande posible o si podría haber uno más grande en un rango más alto?

Puntuaciones actuales:

1. Rubí: 142
2. Windows PowerShell: 153
3. Scala: 222
4. Python: 245

Ahora que se ha seleccionado una respuesta, aquí está mi implementación de referencia (sin golf) en JavaScript: http://jsfiddle.net/ywc25/2/

Ruby 1.9, 142 caracteres

$><<($*[0]..$*[1]).map{|a|n=0.0;(1..s=a.size).map{|i|n+=a.chars.each_cons(i).count{|x|x[0]>?0&&(r=x.join.to_i**0.5)==r.to_i}};[-n/s,a]}.min[1]

• (139 -> 143): salida fija en caso de empate.

Respondiendo al bono: el mejor puntaje para los números <1e9 es 5/3 = 1.666 ..., generado por 144411449 (¿y quizás otros?).

Pero puedes hacerlo mejor con números más grandes. En general, si n tiene una puntuación de x, puede concatenar dos copias de n y obtener la misma puntuación x. Si tiene suerte yn tiene el mismo primer y último dígito, puede colocar uno de esos dígitos en la concatenación y mejorar su puntaje ligeramente (uno menos del doble del número de cuadrados y otro menos del doble del número de dígitos) .

n = 11449441 tiene un puntaje de 1.625 y tiene el mismo primer y último dígito. Usando ese hecho, obtenemos la siguiente secuencia de puntajes:

1.625 for 11449441
1.666 for 114494411449441
1.682 for 1144944114494411449441
1.690 for 11449441144944114494411449441
1.694 for 114494411449441144944114494411449441

que proporciona una secuencia infinita de números que son estrictamente (aunque de manera decreciente) mejores que los números anteriores, y todos menos los primeros 2 son mejores que la mejor puntuación para los números <1e9.

Sin embargo, esta secuencia puede no ser la mejor en general. Converge en un puntaje finito (12/7 = 1.714) y puede haber otros números con mejores puntajes que el límite.

Editar : una secuencia mejor, converge a 1.75

1.600 14441
1.667 144414441
1.692 1444144414441
1.706 14441444144414441
1.714 144414441444144414441

Windows PowerShell, 153 154 155 164 174

$a,$b=$args
@($a..$b|sort{-(0..($l=($s="$_").length)|%{($c=$_)..$l|%{-join$s[$c..$_]}}|?{$_[0]-48-and($x=[math]::sqrt($_))-eq[int]$x}).Count/$l},{$_})[0]

Gracias a Ventero por una reducción de un byte, fui demasiado estúpido para encontrarme.

Versión de 154 bytes explicada:

$a,$b=$args   # get the two numbers. We expect only two arguments, so that
              # assignment will neither assign $null nor an array to $b.

@(   # @() here since we might iterate over a single number as well
    $a..$b |  # iterate over the range
        sort {   # sort
            (   # figure out all substrings of the number
                0..($l=($s="$_").length) | %{  # iterate to the length of the
                                               # string – this will run off
                                               # end, but that doesn't matter

                    ($c=$_)..$l | %{       # iterate from the current position
                                           # to the end

                        -join$s[$c..$_]    # grab a range of characters and
                                           # make them into a string again
                    }
                } | ?{                     # filter the list
                    $_[0]-48 -and          # must not begin with 0
                    ($x=[math]::sqrt($_))-eq[int]$x  # and the square root
                                                     # must be an integer
                }

            ).Count `  # we're only interested in the count of square numbers
            / $l       # divided by the length of the number
        },
        {-$_}  # tie-breaker
)[-1]  # select the last element which is the smallest number with the
       # largest SNDD

Python, 245 256

import sys
def t(n,l):return sum(map(lambda x:int(x**0.5+0.5)**2==x,[int(n[i:j+1])for i in range(l)for j in range(i,l)if n[i]!='0']))/float(l)
print max(map(lambda x:(x,t(str(x),len(str(x)))),range(*map(int,sys.argv[1:]))),key=lambda y:y[1])[0]

• 256 → 245: Limpió el código de análisis de argumentos gracias a un consejo de Keith Randall .

Esto podría ser mucho más corto si el rango se leyera en stdinlugar de los argumentos de la línea de comando.

Editar:

Con respecto a la bonificación, mis experimentos sugieren lo siguiente:

Conjetura 1 . Por cada n ∈ ℕ , el número en ℕ _{≤ n} con el SNDD más grande debe contener únicamente los dígitos 1, 4 y 9.

Conjetura 2. ∃ n ∈ ℕ ∀ i ∈ ℕ _{≥ n} : SNDD ( n ) ≥ SNDD ( i ).

Bosquejo de prueba . El conjunto de cuadrados con los dígitos 1, 4 y 9 son probablemente finitos . ∎

Scala, 222

object O extends App{def q(i: Int)={val x=math.sqrt(i).toInt;x*x==i}
println((args(0).toInt to args(1).toInt).maxBy(n=>{val s=n+""
s.tails.flatMap(_.inits).filter(x=>x.size>0&&x(0)!='0'&&q(x.toInt)).size.toFloat/s.size}))}

(Se requiere Scala 2.9.)

Teniendo en cuenta la pregunta adicional: fuera del rango, el SNDD más alto posible es infinito.

Al menos, si leo la pregunta correctamente, un cuadrado como 100 (10 * 10) sí cuenta.

Si considera el número 275625, el puntaje es 5/6, ya que 25, 625, 5625, 75625 y 275625 son todos cuadrados.

Sumar 2 ceros da: 27562500, que tiene una puntuación de 10/8. El límite de esta secuencia es 5/2 = 2.5

En la misma línea, puedes encontrar cuadrados que terminan en cualquier número de cuadrados más pequeños deseados. Puedo probar esto, pero probablemente entiendes la idea.

Es cierto que esta no es una solución muy buena, pero demuestra que no hay límite superior para el SNDD.

Clojure - 185 caracteres

Probablemente podría optimizarse aún más, pero aquí va:

(fn[A,B]((first(sort(for[r[range]n(r A(inc B))s[(str n)]l[(count s)]][(/(count(filter #(=(int%)(max 1%))(for[b(r(inc l))a(r b)](Math/sqrt(Integer/parseInt(subs s a b))))))(- l))n])))1))

Utilizado como una función con dos parámetros:

(crazy-function-as-above 14000 15000)
=> 14441

Jelly , 21 bytes, desafío de postdates de idioma

DµẆ1ị$ÐfḌƲS÷L
rµÇÐṀḢ

Pruébalo en línea!

Explicación

Función auxiliar (calcula la densidad de dígitos de su entrada):

DµẆ1ị$ÐfḌƲS÷L
Dµ              Default argument: the input's decimal representation
  Ẇ             All substrings of {the decimal representation}
      Ðf        Keep only those where
   1ị$          the first digit is truthy (i.e. not 0)
        Ḍ       Convert from decimal back to an integer
         Ʋ     Check each of those integers to see if it's square
           S    Sum (i.e. add 1 for each square, 0 for each nonsquare)
            ÷L  Divide by the length of {the decimal representation}

Programa principal:

rµÇÐṀḢ
rµ              Range from the first input to the second input
  ÇÐṀ           Find values that maximize the helper function
     Ḣ          Choose the first (i.e. smallest)

Podría decirse que el programa es más interesante sin el Ḣ, de esa manera, devuelve todos los números de densidad máxima en lugar de solo uno, pero lo agregué para cumplir con la especificación.