Większość Liczba kwadratowa mieć co najmniej 1 inny numer kwadratowy z których ich odległość Levenshteina jest dokładnie 1. Dla danego kwadratu , każdy kwadrat, który spełnia ten warunek jest nazywana Levenshteina sąsiad z . Na przykład to sąsiad Levenshtein z liczbą , ponieważ wymagana jest tylko 1 edycja ( ). Jednak nie jest sąsiadem Levenshtein z , ponieważ wymaga co najmniej 2 edycji. Liczby, które mają wiodące zera ( ), nie są sąsiadami Levenshteina.$x$x 36 16 1 → 3 64 16 2025 → 025$x$$36$$16$$1 \to 3$$64$$16$$2025 \to 025$

Twoim zadaniem jest przyjęcie liczby kwadratowej jako danych wejściowych i wydrukowanie, w dowolnym rozsądnym formacie, pełnej listy sąsiadów Levenshtein. Jeśli chcesz, możesz dołączyć powtarzających się sąsiadów na liście, ale nie możesz dołączyć oryginalnego wejścia, ponieważ nie jest ono sąsiadem Levenshtein.

Każdy rozsądny format powinien zawierać pewnego rodzaju separator między wyjściami, taki jak ,lub nowa linia, i może wypisywać znaki o odpowiedniej wartości Unicode (tj. Pieprzenie mózgu), a nie same liczby. Kolejność danych wyjściowych nie ma znaczenia.

To wejście będzie zawsze liczbą kwadratową, większą niż . Twój program nie powinien mieć teoretycznego limitu, ale jeśli z powodów praktycznych (np. Powyżej liczb 32-bitowych) zawiedzie, to nie ma problemu.$0$

Jeśli dane wejściowe nie mają żadnych sąsiadów Levenshteina, dane wyjściowe muszą wyraźnie to odzwierciedlać, takie jak brak danych wyjściowych, pusta tablica / ciąg znaków, ujemna liczba całkowita, itd.$0$

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.

Przypadki testowe

Oto wyniki dla kwadratów od do :$1$$20$

  1: 4, 9, 16, 81
  4: 1, 9, 49, 64
  9: 1, 4, 49
 16: 1, 36, 169, 196
 25: 225, 256, 625
 36: 16, 361
 49: 4, 9
 64: 4
 81: 1, 841
100: 400, 900, 1600, 8100
121: 1521
144: 1444
169: 16, 1369
196: 16, 1296, 1936
225: 25, 625, 1225, 2025, 4225, 7225
256: 25
289: 2809
324: 3249
361: 36, 961
400: 100, 900, 4900, 6400

Ponadto 1024nie ma żadnych sąsiadów, więc jest to dobry przypadek testowy.

05AB1E ,  11 10  6 bajtów

-4 dzięki Grimy !! (najpierw kwadrat zamiast szukać kwadratów zapisuje 3; użyj 10 ^ n zapisów 1)

°Lnʒ.L

Pobiera liczbę całkowitą, wypisuje listę, być może pustą

Wypróbuj online! - To szalenie powolne z powodu°, więc nie ma sensu nawet próbować9.
Lub Wypróbuj nieco szybszą wersję - ta zamiast niej dodaje osiem, a8+następnie używa tego samego podejścia.

W jaki sposób?

°Lnʒ.L - f(integer)    stack = n
°      - push 10^n             10^n
 L     - range                 [1,2,3,...,10^n]
  n    - square                [1,4,9,...,10^2n]
   ʒ   - filter keep if == 1:
    .L -   Levenshtein distance

Retina 0.8.2 , 142 138 bajtów

.?
$'¶$`#$&$'¶$`#$'¶$`$&
#
0$%'¶$%`1$%'¶$%`2$%'¶$%`3$%'¶$%`4$%'¶$%`5$%'¶$%`6$%'¶$%`7$%'¶$%`8$%'¶$%`9
A`^0
Dr`
\d+
$*
-2G`(\b1|11\1)+\b
%`1

Wypróbuj online! Wyjaśnienie:

.?
$'¶$`#$&$'¶$`#$'¶$`$&

Dla każdej cyfry spróbuj a) usunąć ją b) poprzedzić inną cyfrą c) zmienić ją na inną cyfrę. Na razie inna cyfra jest oznaczona symbolem #.

#
0$%'¶$%`1$%'¶$%`2$%'¶$%`3$%'¶$%`4$%'¶$%`5$%'¶$%`6$%'¶$%`7$%'¶$%`8$%'¶$%`9

Dla każdej potencjalnej innej cyfry zamień każdą możliwą cyfrę.

A`^0

Usuń liczby zaczynające się teraz od zera.

Dr`

Usuń wszystkie zduplikowane numery. (To pozostawia puste linie.)

\d+
$*

Konwertuj na unary.

-2G`(\b1|11\1)+\b

Zachowaj wszystkie liczby kwadratowe oprócz ostatniej (która zawsze jest liczbą wejściową).

%`1

Konwertuj pozostałe liczby z powrotem na dziesiętne.

R , 42 41 bajtów

$(9n)^2$

function(n,y=(1:(9*n))^2)y[adist(n,y)==1]

Wypróbuj online!

$n$$91n$$1\to 91$$100\to9100$$(9n)^2=81n^2$$n>1$$81n^2>91n$$n=1$$1\to91$$91$ to nie jest kwadrat, nic nam nie jest.

$1$$(9n)^2$

Python 2 , 173 167 149 148 147 144 139 138 bajtów

lambda n,I=int:{(I(I(v)**.5)**2==I(v))*I(v)for v in[`n`[:i]+`j-1`[:j]+`n`[i+k:]or 0for j in range(11)for i in range(n)for k in 0,1]}-{0,n}

Wypróbuj online!

19 + 3 + 5 + 1 = 28! dziękuję Jonathanowi Allanowi .

Oracle SQL, 93 bajty

select level*level from t where utl_match.edit_distance(x,level*level)=1connect by level<10*x

Testuj w SQL * PLus.

SQL> set heading off
SQL> with t(x) as (select 225 from dual)
  2  select level*level from t where utl_match.edit_distance(x,level*level)=1connect by level<10*x
  3  /

         25
        625
       1225
       2025
       4225
       7225

6 rows selected.

PHP , 62 bajty

for(;$argn*92>$n=++$i**2;levenshtein($argn,$n)==1&&print$n._);

Wypróbuj online!

Ten skrypt drukuje sąsiadów wejścia Levenshtein oddzielonych przez _separator końcowy, a jeśli nie zostaną znalezieni sąsiedzi, nic nie drukuje.

Na szczęście PHP ma wbudowaną funkcję Levenshtein ! Ten skrypt zapętla wszystkie liczby kwadratowe od 1 do input * 91, ponieważ wszyscy ważni sąsiedzi Levenshteina (odległość 1) znajdują się w tym zakresie. Następnie wypisuje każdą liczbę z tego zakresu, który ma odległość Levenshteina 1 z wejściem.

JavaScript (V8) ,  129 125  123 bajtów

Pobiera dane wejściowe jako ciąg. Drukuje sąsiadów Levenshtein do STDOUT.

s=>{for(t=9+s;t;t--)(t+='')**.5%1||(g=m=>m*n?1+g(m,--n)*(g(--m)-(s[m]==t[n++]))*g(m):m+n)(s.length,n=t.length)-1||print(t)}

Wypróbuj online!

Skomentował

s => {                        // s = input
  for(                        // loop:
    t = 9 + s;                //   start with t = '9' + s
    t;                        //   repeat while t > 0
    t--                       //   decrement t after each iteration
  )                           //
    (t += '')                 //   coerce t to a string
    ** .5 % 1 ||              //   abort if t is not a square
    ( g =                     //   g is a recursive function to test whether the
                              //   Levenshtein distance between s and t is exactly 1
      m =>                    //   m = pointer into s (explicit parameter)
                              //   n = pointer into t (defined in the global scope)
        m * n ?               //     if both m and n are greater than 0:
          1 +                 //       add 1 to the final result and add the product of:
          g(m, --n) * (       //         - a recursive call with m and n - 1
            g(--m) -          //         - a recursive call with m - 1 and n - 1
            (s[m] == t[n++])  //           minus 1 if s[m - 1] = t[n - 1]
          ) *                 //
          g(m)                //         - a recursive call with m - 1 and n
        :                     //       else:
          m + n               //         stop recursion and return m + n
    )(s.length, n = t.length) //   initial call to g with m = s.length, n = t.length
    - 1 ||                    //   abort if the final result is not 1
    print(t)                  //   otherwise, print t
}                             //

Galaretka , 53 38 bajtów

D;Ɱ⁵ṭJœP,œṖjþ⁵Ẏṭ@ḢF${ʋʋ€$ƲẎ%⁵1ị$ƇḌƲƇḟ

Wypróbuj online!

Nie ma wbudowanego dystansu Levenshteina, więc generuje wszystkie możliwe edycje o 1 odległości, a następnie wyklucza te z wiodącym zerem i zachowuje tylko idealne kwadraty. Nie filtruje duplikatów (jak dozwolone).

Wolfram Language (Mathematica) , 62 59 bajtów

f@n_:=Select[Range[9n]^2,EditDistance@@ToString/@{n,#}==1&]

Wypróbuj online!

Używanie związany z odpowiedzią R .