Die meisten Quadratzahlen haben mindestens eine unterschiedliche Quadratzahl, mit der ihr Levenshtein-Abstand genau 1 beträgt. Für ein gegebenes Quadrat $x$ wird jedes Quadrat, das diese Bedingung erfüllt, als Levenshtein-Nachbar von $x$ . Beispielsweise ist $36$ ein Levenshtein-Nachbar von $16$ , da nur 1 Bearbeitung ( $1 \to 3$ ) erforderlich ist. Jedoch $64$ ist kein Levenshtein Nachbar von $16$ , da es ein Minimum von 2 Änderungen erfordert. Zahlen mit führenden Nullen ( $2025 \to 025$ ) sind keine levenshteinischen Nachbarn.

Ihre Aufgabe ist es, eine quadratische Zahl als Eingabe zu verwenden und in einem angemessenen Format die vollständige Liste der Levenshtein-Nachbarn auszugeben. Sie können wiederholte Nachbarn in die Liste aufnehmen, wenn Sie möchten, aber Sie können nicht die ursprüngliche Eingabe aufnehmen, da es sich nicht um einen Levenshtein-Nachbarn handelt.

Jedes vernünftige Format sollte eine Art Trennzeichen zwischen den Ausgaben enthalten, z. B. ,oder eine neue Zeile, und kann Zeichen mit dem entsprechenden Unicode-Wert (z. B. Brainfuck) anstelle der Zahlen selbst ausgeben. Die Reihenfolge der Ausgabe spielt keine Rolle.

Diese Eingabe ist immer eine quadratische Zahl, die größer als $0$ . Ihr Programm sollte keine theoretische Begrenzung haben, aber wenn es aus praktischen Gründen (z. B. über 32-Bit-Zahlen hinaus) ausfällt, ist das völlig in Ordnung.

Wenn die Eingabe keine Levenshtein-Nachbarn hat, muss die Ausgabe dies deutlich widerspiegeln, z. B. nichts ausgeben, ein leeres Array / eine leere Zeichenfolge, eine negative Ganzzahl, $0$ usw.

Das ist Code-Golf , also gewinnt der kürzeste Code in Bytes.

Testfälle

Dies sind die Ergebnisse für die Quadrate von $1$ bis $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

Darüber hinaus 1024hat keine Nachbarn, so ist ein guter Testfall.

05AB1E ,  11 10  6 Bytes

-4 danke an Grimy !! (Quadrat zuerst, anstatt nach Quadraten zu suchen, ergibt 3; benutze 10 ^ n ergibt 1)

°Lnʒ.L

Nimmt eine Ganzzahl und gibt eine möglicherweise leere Liste aus

Probieren Sie es online! - Das ist verrückt-langsam wegen der°, also macht es keinen Sinn, es auch nur für zu versuchen9.
Oder versuchen Sie es mit einer etwas schnelleren Version - Diese fügt stattdessen acht hinzu 8+und verwendet dann denselben Ansatz.

Wie?

°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 Bytes

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

Probieren Sie es online! Erläuterung:

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

Versuchen Sie für jede Ziffer, a) sie zu entfernen, b) sie mit einer anderen Ziffer voranzustellen, c) sie in eine andere Ziffer zu ändern. Die andere Ziffer ist vorerst mit einem gekennzeichnet #.

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

Ersetzen Sie für jede mögliche andere Ziffer jede mögliche Ziffer.

A`^0

Entfernen Sie Zahlen, die jetzt mit Null beginnen.

Dr`

Entfernen Sie alle doppelten Nummern. (Dies lässt nur die Zeilen leer.)

\d+
$*

In Unary konvertieren.

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

Behalten Sie alle quadratischen Zahlen außer der letzten (die immer die eingegebene Nummer ist).

%`1

Konvertieren Sie die verbleibenden Zahlen zurück in Dezimalzahlen.

R , 42 41 Bytes

$(9n)^2$

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

Probieren Sie es online!

$n$$91n$$1\to 91$$100\to9100$$(9n)^2=81n^2$$n>1$$81n^2>91n$$n=1$$1\to91$$91$ ist kein Quadrat, es geht uns gut.

$1$$(9n)^2$

Python 2 , 173 167 149 148 147 144 139 138 Bytes

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}

Probieren Sie es online!

19 + 3 + 5 + 1 = 28! Danke an Jonathan Allan .

Oracle SQL, 93 Byte

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

Test in 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 Bytes

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

Probieren Sie es online!

Dieses Skript druckt Levenshtein Nachbarn der Eingabe getrennt durch _ ein nachstehendes Trennzeichen getrennt sind. Wenn keine Nachbarn gefunden werden, wird nichts gedruckt.

Glücklicherweise hat PHP eine eingebaute Levenshtein-Distanz ! Dieses Skript durchläuft alle Quadratzahlen von 1 bis input * 91, da sich alle gültigen Levenshtein-Nachbarn (Abstand von 1) in diesem Bereich befinden. Dann wird jede Zahl in dem Bereich gedruckt, der mit der Eingabe einen Levenshtein-Abstand von 1 hat.

JavaScript (V8) ,  129 125  123 Byte

Übernimmt die Eingabe als Zeichenfolge. Gibt die Levenshtein-Nachbarn an STDOUT aus.

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

Probieren Sie es online!

Kommentiert

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

Jelly , 53 38 Bytes

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

Probieren Sie es online!

Es gibt keine eingebaute Levenshtein-Distanz, so dass alle möglichen 1-Distanz-Bearbeitungen generiert werden und diejenigen mit führender Null ausgeschlossen werden und nur perfekte Quadrate beibehalten werden. Filtert keine Duplikate (wie zulässig).

Wolfram Language (Mathematica) , 62 59 Bytes

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

Probieren Sie es online!

Verwendung der Schranke aus der R-Antwort .