Gęstość cyfr liczby kwadratowej (SNDD) pewnej liczby - wynalezionej przeze mnie - jest stosunkiem liczby liczb kwadratowych znalezionych w kolejnych cyfrach do długości liczby. Na przykład 169 jest trzycyfrową liczbą zawierającą 4 liczby kwadratowe - 1, 9, 16, 169 - a zatem ma gęstość cyfr liczby kwadratowej 4/3 lub 1,33. 4-cyfrowy numer 1444 ma 6 kwadratów - 1, 4, 4, 4, 144, 1444 - a zatem stosunek 6/4 lub 1,5. Zwróć uwagę w poprzednim przykładzie, że kwadraty mogą się powtarzać. Również 441 nie jest dozwolone, ponieważ nie można go znaleźć kolejno pod numerem 1444.

Twoim zadaniem jest napisanie programu, który będzie wyszukiwał w danym zakresie od A do B (włącznie) liczbę o największej gęstości cyfr kwadratowych. Twój program powinien być zgodny z następującymi specyfikacjami:

• Weź dane wejściowe A, B w zakresie od 1 do 1 000 000 000 (1 miliard). Przykład:sndd 50 1000
• W rezultacie zwróć liczbę o największym SNDD. W przypadku remisu zwróć najmniejszą liczbę.
• 0 nie jest liczone jako kwadrat w żadnej formie, 0, 00, 000 itd. Nie należy również kwadratów rozpoczynających się od 0, takich jak 049 lub 0049.
• Zauważ, że cały numer nie musi być liczbą kwadratową.

Przykłady:

sndd 14000 15000
Output: 14441

sndd 300 500
Output: 441

Premia: jaka jest liczba przy największym SNDD od 1 do 1 000 000 000? Czy możesz udowodnić, czy jest to największy możliwy, czy może być większy w wyższym zakresie?

Aktualne wyniki:

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

Teraz, gdy wybrano odpowiedź, oto moja (nie golfowa) referencyjna implementacja w JavaScript: http://jsfiddle.net/ywc25/2/

Ruby 1.9, 142 znaki

$><<($*[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): Naprawiono wydajność w przypadku remisu.

Odpowiadając na bonus: najlepszy wynik dla liczb <1e9 to 5/3 = 1,666 ..., wygenerowany przez 144411449 (a może inne?).

Ale możesz zrobić lepiej z większymi liczbami. Ogólnie, jeśli n ma wynik x, możesz połączyć dwie kopie n i uzyskać taki sam wynik x. Jeśli masz szczęście, a n ma tę samą pierwszą i ostatnią cyfrę, możesz upuścić jedną z tych cyfr w konkatenacji i nieznacznie poprawić swój wynik (jeden mniej niż dwukrotność liczby kwadratów i jeden mniej niż dwukrotność liczby cyfr) .

n = 11449441 ma wynik 1,625 i ma tę samą pierwszą i ostatnią cyfrę. Korzystając z tego faktu, otrzymujemy następującą sekwencję wyników:

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

co daje nieskończoną sekwencję liczb, które są ściśle (choć malejąco) lepsze niż poprzednie liczby, a wszystkie z wyjątkiem pierwszych 2 są lepsze niż najlepszy wynik dla liczb <1e9.

Ta sekwencja może jednak nie być najlepsza. Jest zbieżny do wyniku skończonego (12/7 = 1,714) i mogą istnieć inne liczby z lepszymi wynikami niż limit.

Edycja : lepsza sekwencja, zbieżna do 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]

Dzięki Ventero za redukcję o jeden bajt byłem zbyt głupi, żeby się znaleźć.

Wyjaśnienie wersji 154-bajtowej:

$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: Wyczyściłem kod analizujący argumenty dzięki wskazówce Keitha Randalla .

Może to być o wiele krótsze, jeśli odczytano by zakres stdinw przeciwieństwie do argumentów wiersza poleceń.

Edytować:

W odniesieniu do premii moje eksperymenty sugerują, co następuje:

Domysł 1 . Dla każdego n ∈ ℕ liczba w ℕ _{≤ n} przy największym SNDD musi zawierać wyłącznie cyfry 1, 4 i 9.

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

Szkic dowodowy . Zbiór kwadratów z cyframi 1, 4 i 9 jest prawdopodobnie skończony . ∎

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

(Wymagany Scala 2.9.)

Biorąc pod uwagę dodatkowe pytanie: poza zakresem najwyższy możliwy SNDD jest nieskończony.

Przynajmniej, jeśli poprawnie przeczytam pytanie, kwadrat taki jak 100 (10 * 10) się liczy.

Jeśli weźmiesz pod uwagę liczbę 275625, wynik to 5/6, ponieważ 25, 625, 5625, 75625 i 275625 są kwadratowe.

Dodanie 2 zer daje 27562500, który ma wynik 10/8. Granica tej sekwencji wynosi 5/2 = 2,5

Wzdłuż tych samych linii można znaleźć kwadraty, które kończą się dowolną liczbą mniejszych kwadratów. Mogę to udowodnić, ale prawdopodobnie masz pomysł.

Wprawdzie nie jest to bardzo miłe rozwiązanie, ale dowodzi, że nie ma górnej granicy dla SNDD.

Clojure - 185 znaków

Prawdopodobnie można go jeszcze zoptymalizować, ale oto:

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

Używany jako funkcja z dwoma parametrami:

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

Galaretka , 21 bajtów, wyzwanie dla postdate języka

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

Wypróbuj online!

Wyjaśnienie

Funkcja pomocnicza (oblicza gęstość cyfr na wejściu):

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}

Główny program:

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

Program jest prawdopodobnie bardziej interesujący bez Ḣ- w ten sposób zwraca wszystkie liczby o maksymalnej gęstości zamiast tylko jednej - ale dodałem go, aby był zgodny ze specyfikacją.