133 lines
3.1 KiB
Python
133 lines
3.1 KiB
Python
|
#!/bin/python3
|
||
|
|
import sys
|
||
|
|
from pprint import pprint
|
||
|
|
import numpy as np
|
||
|
|
from math import ceil, sqrt
|
||
|
|
from itertools import cycle, count
|
||
|
|
import copy
|
||
|
|
|
||
|
|
def manhattan_distance(a, b):
|
||
|
|
return np.abs(a - b).sum()
|
||
|
|
def spiral_distances():
|
||
|
|
"""
|
||
|
|
Yields 1, 1, 2, 2, 3, 3, ...
|
||
|
|
"""
|
||
|
|
for distance in count(1):
|
||
|
|
for _ in (0, 1):
|
||
|
|
yield distance
|
||
|
|
|
||
|
|
def clockwise_directions():
|
||
|
|
"""
|
||
|
|
Yields right, down, left, up, right, down, left, up, right, ...
|
||
|
|
"""
|
||
|
|
left = (-1, 0)
|
||
|
|
right = (1, 0)
|
||
|
|
up = (0, -1)
|
||
|
|
down = (0, 1)
|
||
|
|
return cycle((right, up, left, down))
|
||
|
|
|
||
|
|
def spiral_movements():
|
||
|
|
"""
|
||
|
|
Yields each individual movement to make a spiral:
|
||
|
|
right, down, left, left, up, up, right, right, right, down, down, down, ...
|
||
|
|
"""
|
||
|
|
for distance, direction in zip(spiral_distances(), clockwise_directions()):
|
||
|
|
for _ in range(distance):
|
||
|
|
yield direction
|
||
|
|
|
||
|
|
def square(width):
|
||
|
|
"""
|
||
|
|
Returns a width x width 2D list filled with Nones
|
||
|
|
"""
|
||
|
|
return [[None] * width for _ in range(width)]
|
||
|
|
|
||
|
|
def spiral(inp):
|
||
|
|
width = int(ceil(sqrt(len(inp))))
|
||
|
|
print(width)
|
||
|
|
result = square(width)
|
||
|
|
x = width // 2
|
||
|
|
y = width // 2
|
||
|
|
for value, movement in zip(inp, spiral_movements()):
|
||
|
|
result[y][x] = value
|
||
|
|
dx, dy = movement
|
||
|
|
x += dx
|
||
|
|
y += dy
|
||
|
|
return result
|
||
|
|
|
||
|
|
def find_index(array, value):
|
||
|
|
for i, row in enumerate(array): # Loop through rows with their indices
|
||
|
|
for j, element in enumerate(row): # Loop through elements with their indices
|
||
|
|
if element == value: # Check if the element matches the value
|
||
|
|
return (i, j) # Return the row and column indices
|
||
|
|
return None # Return None if the value is not found
|
||
|
|
|
||
|
|
input_f = sys.argv[1]
|
||
|
|
|
||
|
|
number = int(input_f)
|
||
|
|
org = number
|
||
|
|
while not sqrt(number).is_integer():
|
||
|
|
number+=1
|
||
|
|
|
||
|
|
mid = int((sqrt(number)-1)/2)
|
||
|
|
|
||
|
|
length = int(sqrt(number))
|
||
|
|
|
||
|
|
a = [mid, mid]
|
||
|
|
|
||
|
|
ina = np.arange(1,number+1)
|
||
|
|
arr = spiral(ina)
|
||
|
|
pprint(np.array(arr))
|
||
|
|
|
||
|
|
tmp_arr = copy.deepcopy(arr)
|
||
|
|
|
||
|
|
for idx,i in enumerate(tmp_arr):
|
||
|
|
for jdx,j in enumerate(tmp_arr):
|
||
|
|
tmp_arr[jdx][idx] = 0
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
count = 1
|
||
|
|
x,y = find_index(arr,count)
|
||
|
|
tmp_arr[mid][mid] = 1
|
||
|
|
while True:
|
||
|
|
#pprint(np.array(arr))
|
||
|
|
#pprint(np.array(tmp_arr))
|
||
|
|
|
||
|
|
tmp = 0
|
||
|
|
x,y = find_index(arr,count)
|
||
|
|
#print(x,y)
|
||
|
|
#print("count:",count)
|
||
|
|
#print("arr:",arr[x][y])
|
||
|
|
#print("tmp_arr",tmp_arr[x][y])
|
||
|
|
|
||
|
|
# x y cant be negative. change x y everywhere to temp x y values and check they aren't negative.
|
||
|
|
|
||
|
|
cords = [[x+1,y],[x-1,y],[x,y+1],[x,y-1],[x+1,y+1],[x+1,y-1],[x-1,y+1],[x-1,y-1]]
|
||
|
|
|
||
|
|
for c in cords:
|
||
|
|
#print(c)
|
||
|
|
try:
|
||
|
|
if c[0] < 0 or c[1] < 0:
|
||
|
|
raise ValueError('Negative')
|
||
|
|
if tmp_arr[c[0]][c[1]] != 0:
|
||
|
|
#print(tmp_arr[c[0]][c[1]])
|
||
|
|
#print(c)
|
||
|
|
tmp+=tmp_arr[c[0]][c[1]]
|
||
|
|
#print("tmp:",tmp)
|
||
|
|
except Exception as e:
|
||
|
|
print('Error1',e)
|
||
|
|
|
||
|
|
|
||
|
|
tmp_arr[x][y] += tmp
|
||
|
|
if tmp > org:
|
||
|
|
print('Value:',tmp)
|
||
|
|
print('Org:',org)
|
||
|
|
exit()
|
||
|
|
#print(np.array(tmp_arr))
|
||
|
|
count += 1
|
||
|
|
#input()
|
||
|
|
|
||
|
|
|