Levenshtein NeighboursRr IiOm.td E89Aywhlli4p 121l Mc 8Qq Uul17iS3
Most square numbers have at least 1 different square number with which their Levenshtein distance is exactly 1. For a given square \\$x\\$, each square that meets this condition is called a Levenshtein neighbour of \\$x\\$. For example, \\$36\\$ is a Levenshtein neighbour of \\$16\\$, as only 1 edit (\\$1 \\to 6\\$) is required. However, \\$64\\$ is not a Levenshtein neighbour of \\$16\\$, as it requires a minimum of 2 edits. Numbers that have leading 0s (\\$2025 \\to 025\\$) are not Levenshtein neighbours.
Your task is to take a square number as input and to output, in any reasonable format, the complete list of it's Levenshtein neighbours. You may include repeat neighbours in the list, if you wish.
Any reasonable format should include some sort of separator between the outputs, such as , or a newline, and can output characters with the corresponding Unicode value (i.e. brainfuck) rather than the numbers themselves. The order of the output doesn't matter.
This input will always be a square number, greater than \\$0\\$. Your program should have no theoretical limit, but if it fails for large numbers for practical reasons (e.g. beyond 32-bit numbers), that's completely fine.
If the input does not have any Levenshtein neighbours, the output must clearly reflect this, such as outputting nothing, an empty array/string, a negative integer, \\$0\\$, etc.
This is code-golf, so the shortest code in bytes wins.
Test cases
These are the results for the squares of \\$1\\$ through to \\$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
In addition, 1024 does not have any neighbours, so is a good test case.
4 Answers
05AB1E, 11 10 bytes
т*LʒŲ}ʒ.L
Takes an integer, outputs a, possibly empty, list
Try it online!
How?
т*LʒŲ}ʒ.L - f(integer) stack = n
т - push 100 n, 100
* - multiply 100n
L - range [1,2,3,...,100n]
ʒ } - filter keep if == 1:
Ų - isSquare?
ʒ - filter keep if == 1:
.L - Levenshtein distance
Previous 11 will be faster for large numbers: 9s«LʒŲ}ʒ.L
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
Try it online! Explanation:
.?
$'¶$`#$&$'¶$`#$'¶$`$&
For each digit, try a) removing it b) preceding it with a different
digit c) changing it to a different digit. For now, the different digit is marked with a #.
#
0$%'¶$%`1$%'¶$%`2$%'¶$%`3$%'¶$%`4$%'¶$%`5$%'¶$%`6$%'¶$%`7$%'¶$%`8$%'¶$%`9
For each potential different digit, substitute each possible digit.
A`^0
Remove numbers that now begin with zero.
Dr`
Remove all duplicated numbers. (This just leaves the lines blank.)
\\d+
$*
Convert to unary.
-2G`(\\b1|11\\1)+\\b
Keep all square numbers except the last (which is always the input number).
%`1
Convert the remaining numbers back to decimal.
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}
Try it online!
19+3+5+1=28! bytes thx to Jonathan Allan.
-
\\$\\begingroup\\$ Save 48.
[p for p in...]is redundant. We can return a set (or duplicates).'0'<v[:1]can be'1'<=v. It's much slower butrange(len(a)+1)can berange(n). Use a variable foriandi+1slices to avoid the sum. Use a lambda. EDIT save 48 from your previous. \\$\\endgroup\\$ – Jonathan Allan 5 hours ago -
\\$\\begingroup\\$ @Jonathan Allan: I'd already made some of the same changes; but definitely appreciate the 18 bytes! \\$\\endgroup\\$ – Chas Brown 5 hours ago
-
\\$\\begingroup\\$ Another one \\$\\endgroup\\$ – Jonathan Allan 4 hours ago
-
\\$\\begingroup\\$ @Jonathan Allan: Nice! It's now barely readable :). \\$\\endgroup\\$ – Chas Brown 4 hours ago
-
1\\$\\begingroup\\$ @Jonathan Allan: Lol, I'm just gonna stop updating - I can't keep up! :) \\$\\endgroup\\$ – Chas Brown 4 hours ago
Jelly, 53 bytes
Ḋ}Ṗ}¦,ṖœPFɗ@ṭ@;@Ḋ}¥ṭ@;€Ḋ}¥Ṗ}¦F¥
DçⱮJp⁵Ḷ¤Ɗ$Ẏ1ị$ƇQḌƲƇḟ
Try it online!
Rather long. There’s no built-in for Levenshtein distance so generates all possible 1-distance edits and then excludes those with leading zero and keeps only perfect squares.
81test case would seem to imply so. \\$\\endgroup\\$ – Shaggy 8 hours ago2025are. \\$\\endgroup\\$ – Neil 8 hours ago32 * 32 = 1024has no square Levenshtein neighbours. \\$\\endgroup\\$ – xnor 7 hours ago