Kepadatan digit angka kuadrat (SNDD) dari suatu angka - diciptakan sendiri - adalah perbandingan jumlah angka kuadrat yang ditemukan dalam digit berurutan dengan panjang angka. Misalnya, 169 adalah angka 3 digit yang mengandung 4 angka kuadrat - 1, 9, 16, 169 - dan dengan demikian memiliki kepadatan angka angka kuadrat 4/3, atau 1,33. Angka 4 digit 1444 memiliki 6 kotak - 1, 4, 4, 4, 144, 1444 - dan dengan demikian rasio 6/4, atau 1,5. Perhatikan pada contoh sebelumnya bahwa kotak diizinkan untuk diulang. Juga, 441 tidak diperbolehkan, karena tidak dapat ditemukan secara berurutan di dalam nomor 1444.

Tugas Anda adalah menulis program yang mencari rentang A - B (inklusif) untuk angka dengan kepadatan digit angka kuadrat tertinggi. Program Anda harus mematuhi spesifikasi berikut:

• Ambil input A, B dalam kisaran 1 hingga 1.000.000.000 (1 miliar). Contoh:sndd 50 1000
• Hasilnya adalah nomor dengan SNDD terbesar. Dalam kasus seri, kembalikan nomor terkecil.
• 0 tidak dihitung sebagai kotak dalam bentuk apa pun, 0, 00, 000, dll. Kotak juga tidak dimulai dengan 0, seperti 049 atau 0049.
• Perhatikan bahwa seluruh angka tidak harus berupa angka kuadrat.

Contoh:

sndd 14000 15000
Output: 14441

sndd 300 500
Output: 441

Bonus: Berapa angka dengan SNDD terbesar antara 1 dan 1.000.000.000? Bisakah Anda membuktikan apakah ini adalah yang terbesar, atau mungkin ada yang lebih besar dalam kisaran yang lebih tinggi?

Skor saat ini:

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

Sekarang setelah jawaban telah dipilih, berikut ini adalah implementasi referensi saya (tidak diunggah) dalam JavaScript: http://jsfiddle.net/ywc25/2/

Ruby 1.9, 142 karakter

$><<($*[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): Memperbaiki output jika terjadi seri.

Menjawab bonus: skor terbaik untuk angka <1e9 adalah 5/3 = 1.666 ..., dihasilkan oleh 144411449 (dan mungkin yang lain?).

Tetapi Anda dapat melakukannya dengan lebih baik dengan jumlah yang lebih besar. Umumnya jika n memiliki skor x, maka Anda dapat menggabungkan dua salinan n dan mendapatkan skor yang sama x. Jika Anda beruntung dan n memiliki angka pertama dan terakhir yang sama, maka Anda dapat menjatuhkan salah satu dari angka-angka itu dalam rangkaian dan meningkatkan skor Anda sedikit (satu kurang dari dua kali lipat jumlah kotak dan satu kurang dari dua kali lipat jumlah digit) .

n = 11449441 memiliki skor 1,625 dan memiliki angka pertama & terakhir yang sama. Dengan menggunakan fakta itu, kita mendapatkan urutan skor berikut:

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

yang memberikan urutan angka tak terbatas yang secara ketat (meskipun semakin menurun) lebih baik dari angka sebelumnya, dan semua kecuali 2 pertama lebih baik daripada skor terbaik untuk angka <1e9.

Namun, urutan ini mungkin bukan yang terbaik secara keseluruhan. Konvergen ke skor terbatas (12/7 = 1.714) dan mungkin ada angka lain dengan skor lebih baik dari batas.

Sunting : urutan yang lebih baik, konvergen ke 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]

Berkat Ventero untuk pengurangan satu byte saya terlalu bodoh untuk menemukan diri saya sendiri.

Versi 154-byte menjelaskan:

$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: Membersihkan kode parsing argumen berkat tip dari Keith Randall .

Ini bisa menjadi jauh lebih pendek jika rentang dibaca dari yang stdinbertentangan dengan argumen baris perintah.

Edit:

Sehubungan dengan bonus, percobaan saya menyarankan yang berikut:

Dugaan 1 . Untuk setiap n ∈ ℕ , angka dalam ℕ _{≤ n} dengan SNDD terbesar harus berisi hanya angka 1, 4, dan 9.

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

Sketsa bukti . Himpunan kotak dengan angka 1, 4, dan 9 kemungkinan terbatas . ∎

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

(Diperlukan Scala 2.9.)

Mempertimbangkan pertanyaan bonus: Di luar kisaran SNDD tertinggi yang mungkin tak terbatas.

Setidaknya, jika saya membaca pertanyaan dengan benar, kuadrat seperti 100 (10 * 10) tidak masuk hitungan.

Jika Anda mempertimbangkan angka 275625, skornya adalah 5/6, karena 25, 625, 5625, 75625 dan 275625 semuanya persegi.

Menambahkan 2 nol memberi: 27562500, yang memiliki skor 10/8. Batas urutan ini adalah 5/2 = 2.5

Di sepanjang garis yang sama, Anda dapat menemukan kotak yang berakhir dengan jumlah kotak yang lebih kecil yang diinginkan. Saya bisa buktikan ini, tetapi Anda mungkin mendapatkan ide.

Diakui, ini bukan solusi yang sangat bagus, tetapi ini membuktikan tidak ada batas atas SNDD.

Clojure - 185 karakter

Mungkin bisa dioptimalkan lebih lanjut tetapi begini:

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

Digunakan sebagai fungsi dengan dua parameter:

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

Jelly , 21 byte, tantangan tanggal kiriman bahasa

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

Cobalah online!

Penjelasan

Fungsi pembantu (menghitung kerapatan digit inputnya):

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}

Program utama:

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 ini bisa dibilang lebih menarik tanpa Ḣ- dengan cara itu, ia mengembalikan semua angka kepadatan maksimal daripada hanya satu - tetapi saya menambahkannya untuk memenuhi spesifikasi.