def queen_spiral(a,b):
square_size = int(max(a,b)**.5)+1
complex_to_spiral = []
complex = 0
spiral_to_complex = [c] # add 0 first, so that it's 1-indexed later
result = [a]
for i in range(square_size):
complex_to_spiral.append([0]*square_size) # the rows of the spiral
for k in range(square_size**2):
row = int(complex.real)
column = int(complex.imag)
complex_to_spiral[row][column] = k+1 # 1-indexing
spiral_to_complex.append(complex)
quarter_turns = int((4*k+1)**.5-1)
complex += 1j**quarter_turns
z = spiral_to_complex[a] - spiral_to_complex[b]
v = spiral_to_complex[b]
x, y = int(z.real), int(z.imag)
r, s = int(v.real), int(v.imag)
while abs(x+y*1j):
if x < 0:
x += 1
elif x > 0:
x += -1
# else x == 0, do nothing
if y < 0:
y += 1
elif y > 0:
y += -1
vertex = complex_to_spiral[r+x][s+y]
result.append(vertex)
return result
Попробуйте онлайн!
-2 байта благодаря @ngn.
Анонимная функция, принимающая две конечные точки в качестве левого и правого аргументов.
Ungolfed и как это работает
Ферзь ходит первым по диагонали, поэтому достаточно заранее вычислить координаты каждого номера до def q(a,b):
m=int(max(a,b)**.5)+1;d=[];c=0;e=[c];t=[a]
for i in range(m):d+=[[0]*m]
for k in range(m*m):d[int(c.real)][int(c.imag)]=k+1;e+=[c];c+=1j**int((4*k+1)**.5-1)
z=e[a]-e[b];x,y=int(z.real),int(z.imag)
while abs(x+y*1j):x+=(x<0)^-(x>0);y+=(y<0)^-(y>0);t+=[d[int(e[b].real)+x][int(e[b].imag)+y]]
return t
.
Алгоритм генерации координат основан на нескольких ответах на связанная проблема, но немного отличается от любого из существующих ответов:
- Учитывая необходимую оценку 10
- Создать диапазон на основе 1
b
- Возьмите потолок половины каждого числа
a
- Повторите каждый элемент
def q(a,b)
m = ([a,b].max**0.5).to_i+1
n = m*m
d = [0]*n
c = 0
*e = c # same as e=[0]
*t = a # same as t=[a]
(1..n).each do |k|
d[c.real * m + c.imag] = k+1
e << c
c += 1i**((4*k+1)**0.5-1).to_i
end
x, y = (e[a] - g=e[b]).rect
while (x+y.i).abs > 0 do
if x<0
x += 1
elsif x>0
x += -1
end
if y<0
y += 1
elsif y>0
y -= 1
end
t << d[(g.real+x)*m+g.imag+y]
end
return t
end
by ->a,b{m=([a,b].max**0.5).to_i+1;d=[0]*n=m*m;*e=c=0;*t=a
n.times{|k|d[c.real*m+c.imag]=k+1;e<<c;c+=1i**((4*k+1)**0.5-1).to_i}
x,y=(e[a]-g=e[b]).rect
(x+=0<=>x;y+=0<=>y;t<<d[(g.real+x)*m+g.imag+y])while(x+y.i).abs>0
t}
. (x+y.i)
- Возьмите совокупную сумму мощности воображаемой единицы с начальной точкой 0. (эта часть является общей для различных решений Python для связанной задачи)
Тогда, как только вектор координат (x+y*1i) is ready, we can easily convert between the spiral index and coordinates using x,y=(e[a]-g=e[b]).rect; t<<d[(g.real+x)*m+g.imag+y] и 0<=>x (finding the first index of .rect в d=[0]*n=m*m;*e=c=0;*t=a ).
import scala.math._
type Grid=Array[Array[Int]]
def spiral(size: Int) = {
def up(grid:Grid, x: Int, y: Int, c: Int, r: Int): Unit = {
for (i <- 0 to r.min(y)) {
grid(y-i)(x) = c + i
}
if (r <= y)
right(grid,x,y-r,c+r,r)
}
def right(grid:Grid, x: Int, y: Int, c: Int, r: Int) = {
for (i <- 0 to r) {
grid(y)(x+i) = c + i
}
down(grid,x+r,y,c+r,r+1)
}
def down(grid:Grid, x: Int, y: Int, c: Int, r: Int) = {
for (i <- 0 to r) {
grid(y+i)(x) = c + i
}
left(grid,x,y+r,c+r,r)
}
def left(grid:Grid, x: Int, y: Int, c: Int, r: Int) = {
for (i <- 0 to r) {
grid(y)(x-i) = c + i
}
up(grid,x-r,y,c+r,r+1)
}
val grid = Array.ofDim[Int](size,size)
up(grid,size/2,size/2,1,1)
grid
}
def findPath(start: Int, end: Int): List[Int] = {
def findCoords(n: Int, grid: Grid): (Int, Int) = {
var (x,y)=(0,0)
for (i <- grid.indices) {
val j = grid(i).indexOf(n)
if (j >= 0) {
x = j
y = i
}
}
(x,y)
}
def sign(n: Int) = if (n == 0) 0 else if (n < 0) -1 else 1
def path(stc: (Int, Int), enc: (Int, Int)) : List[(Int, Int)] = {
val dx = sign(enc._1 - stc._1)
val dy = sign(enc._2 - stc._2)
if (dx == 0 && dy == 0) {
enc :: Nil
} else {
stc :: path((stc._1 + dx, stc._2 + dy), enc)
}
}
val size = ceil(sqrt(max(start, end))).toInt | 1
val spir = spiral(size)
path(findCoords(start, spir),findCoords(end, spir)).
map { case (x, y) => spir(y)(x) }
}
||answer||
Математика 615 530 байт
Это создает числовую сетку, преобразует ее в график, а затем находит кратчайший путь между двумя введенными числами.
без гольфа
def P(s:Int,e:Int):List[Int]={
import scala.math._
type G=Array[Array[Int]]
type I=Int
type T=(I,I)
def S(z:I)={def U(g:G,x:I,y:I,c:I,r:I):Unit={for(i<-0 to r.min(y)){g(y-i)(x)=c+i}
if(r<=y)R(g,x,y-r,c+r,r)}
def R(g:G,x:I,y:I,c:I,r:I)={for(i<-0 to r){g(y)(x+i)=c+i}
D(g,x+r,y,c+r,r+1)}
def D(g:G,x:I,y:I,c:I,r:I)={for(i<-0 to r){g(y+i)(x)=c+i}
L(g,x,y+r,c+r,r)}
def L(g:G,x:I,y:I,c:I,r:I)={for(i<-0 to r){g(y)(x-i)=c+i}
U(g,x-r,y,c+r,r+1)}
val g=Array.ofDim[I](z,z)
U(g,z/2,z/2,1,1)
g}
def C(n:I,g:G):T={var(x,y)=(0,0)
for(i<-g.indices){val j=g(i).indexOf(n)
if(j>=0){x=j
y=i}}
(x,y)}
def N(n:Int)=if(n==0)0 else if(n<0)-1 else 1
def Q(a:T,b:T):List[T]={val u=N(b._1-a._1)
val v=N(b._2-a._2)
if(u==0&&v==0)b::Nil else a::Q((a._1+u,a._2+v),b)}
val z=ceil(sqrt(max(s,e))).toInt|1
val p=S(z)
Q(C(s,p),C(e,p)).map{case(x,y)=>p(y)(x)}}
is from Mathworld Прайм Спираль. Он создает n на n Улам Спираль (без выделения простых чисел).
u=Module;
w@n_:=u[{a,i=(n+1)/2,j=(n+1)/2,c=1,d=0,l,p,v={{1,0},{0,-1},{-1,0},{0,1}}},
a=Table[j+n(i-1),{i,n},{j,n}];
Do[Do[Do[a[[j,i]]=c++;{i,j}+=v[[d+1]],{k,l}];d=Mod[d+1,4],{p,0,1}],{l,n-1}];a];
h[v1_,v2_]:=u[{f,z},
s_~f~n_:=n<->#&/@(s[[Sequence@@#]]&/@(Position[s,n][[1]]/.{r_,c_}:>
Cases[{{r-1,c},{r+1,c},{r,c-1},{r,c+1},{r-1,c-1},{r-1,c+1},{r+1,c+1},{r+1,c-1}},{x_,y_}/;0<x<k&&0<y<k]));
k=If[EvenQ[z=\[LeftCeiling]Sqrt[Sort[{v1,v2}][[-1]]]\[RightCeiling]],z+1,z];
FindShortestPath[g=Graph[Sort/@Flatten[f[ns=w@k,#]&/@Union@Range[k^2]]],v1,v2]]
converts the number grid into a graph. Edges are valid queen moves on the number grid.
findPath[80,1]
numberSpiral[9]//Grid
Примеры
findPath[4,5]
findPath[13,22]
findPath[16,25]
numberSpiral[5]//Grid
{4,5}
{13,3,1,7,22}
{16,4,1,9,25}
Кратчайший путь от 80 до 1 содержит 5, а не 6 вершин.
numberSpiral[n_Integer?OddQ]:=
Module[{a,i=(n+1)/2,j=(n+1)/2,cnt=1,dir=0,len,parity,vec={{1,0},{0,-1},{-1,0},{0,1}}},a=Table[j+n(i-1),{i,n},{j,n}];Do[Do[Do[a[[j,i]]=cnt++;{i,j}+=vec[[dir+1]],{k,len}];dir=Mod[dir+1,4],{parity,0,1}],{len,n-1}];a];
findPath[v1_, v2_] :=
Module[{f, z, k},
(*f creates edges between each number and its neighboring squares *)
f[sp_,n_]:=n<->#&/@(sp[[Sequence@@#]]&/@(Position[sp,n][[1]]/.{r_,c_}:>Cases[{{r-1,c},{r+1,c},{r,c-1},{r,c+1},{r-1,c-1},{r-1,c+1},{r+1,c+1}, {r+1,c-1}},{x_,y_}/; 0<x<k&&0<y<k]));k=If[EvenQ[
z=\[LeftCeiling]Sqrt[Sort[{v1, v2}][[-1]]]\[RightCeiling]],z+1,z];
FindShortestPath[Graph[Sort/@Flatten[f[ns=numberSpiral[k],#]&/@Range[k^2]] //Union],v1,v2]]
{80, 48, 24, 8, 1}
играл в гольф
findPath ||answer||
Скала (830 байт)
Строит спираль в квадратном двумерном массиве, используя четыре взаимно рекурсивные функции. Еще один рекурсивный поиск для создания списка путей.
numberSpiral
Негольфед
⍝ Define a function; ⍺=start, ⍵=end
f←{
⍝ Construct a vector of spiral coordinates v
v←9 11∘○¨+\0,0j1*{⍵/⍨⌈⍵÷2}⍳⍺⌈⍵
⍺⌈⍵ ⍝ max of start, end
⍳ ⍝ range of 1 to that number
{⍵/⍨⌈⍵÷2} ⍝ for each number n of above, copy itself ceil(n/2) times
0j1* ⍝ raise imaginary unit to the power of above
+\0, ⍝ prepend 0 and cumulative sum
⍝ (gives vector of coordinates as complex numbers)
9 11∘○¨ ⍝ convert each complex number into (real, imag) pair
v← ⍝ assign it to v
⍝ Extract start and end coordinates
a w←(⍺⊃v)(⍵⊃v)
⍝ Compute the path the Queen will take
v⍳+\(⊂a),↓⍉↑(|⍴¨×)w-a
w-a ⍝ coordinate difference (end-start)
(|⍴¨×) ⍝ generate abs(x) copies of signum(x) for both x- and y-coords
⍝ e.g. 4 -> (1 1 1 1), ¯3 -> (¯1 ¯1 ¯1)
↓⍉↑ ⍝ promote to matrix (with 0 padding), transpose and split again
⍝ (gives list of steps the Queen will take)
+\(⊂a), ⍝ prepend the starting point and cumulative sum
⍝ (gives the path as coordinates)
v⍳ ⍝ index into the spiral vector (gives the spiral numbers at those coordinates)
}
||answer||
Рубин, 262 218 216 байт
Это порт мой ответ на Python. Предложения по игре в гольф приветствуются.
Редактировать: 45 байт благодаря Джордану и его предложениям v , coord , v⍳coord and v[i] . Еще один байт из v to 1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10 .
n
Не в гольфе:
r ||answer||
Питон 3, 316 байт
В этом ответе рассматриваются координаты n=1 1 2 2 3 3 4 4 5 5 and r=1 2 3 4 5 6 7 8 9 10 по спирали (используя комплексные числа) и сначала добавляет диагональные ходы, а затем ортогональные ходы.
max(start,end)
Не в гольфе:
{v⍳+\v[⍺],↓⍉↑(|⍴¨×)⊃⍵⍺-.⊃⊂v←9 11∘○¨+\0,0j1*{⍵/⍨⌈⍵÷2}⍳⍺⌈⍵}
![[MediaCard] POSITIONS PRO + 34 New Extra Positions (POSITIONS Pro v.1.1 - for Template Perfectum)](/assets/images/icons/forum6.png){kind=icon}
![[XTR] View Conversations](/assets/images/icons/forum0.png){kind=icon}
