Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Square Spiral by colinmcnicholl
from math import sqrt, ceil
def make_spiral(R):
"""Input: R as an integer, the radius of the Ulam spiral.
Output: A list of complex numbers (x, y coordinates).
"""
spiral = [(0 + 0j)]
for r in range(R + 1):
corner = r + 1j * r
side_len = 2 * r
current_pos = corner
for side, direction in zip(range(4), [-1j, -1, 1j, 1]):
for step in range(side_len):
current_pos += direction
spiral.append(current_pos)
return spiral
def spiral_graph(spiral_coords):
"""Input: A list of complex numbers (x, y coordinates).
Output: A distionary with complex numbers (x, y coordinates) as keys and
integers from 1 to the maximum value in the Ulam spiral map as the values.
"""
return dict(zip(spiral_coords, range(1, len(spiral_coords) + 1)))
def get_key_for_value(dictionary, value):
"""Input: A distionary with complex numbers (x, y coordinates) as keys and
integers from 1 to the maximum value in the Ulam spiral map as the values.
'value' as an integer is the mark of a given cell in the Ulam spiral map.
Output: A complex number (x and y coordinate).
"""
return next(key for key in dictionary.keys() if dictionary[key] == value)
def find_distance(first, second):
"""Inputs: Two marks of cells as an integers.
The function creates a circuit board in which all of its elements are
connected in a spiral and it is possible to connect the neighboring
elements vertically and horizontally.
The map of the circuit consists of a series of square cells.
The first element in the center is marked as 1, and continuing in a
clockwise spiral, each other elements is marked in ascending order.
Output: The manhattan distance between the two cells as an integer.
"""
side_length = int(ceil(sqrt(max(first, second))))
radius = side_length // 2
my_spiral = make_spiral(radius)
my_map = spiral_graph(my_spiral)
pt1, pt2 = [get_key_for_value(my_map, val) for val in [first, second]]
diff = pt1 - pt2
return int(abs(diff.real) + abs(diff.imag))
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert find_distance(1, 9) == 2, "First"
assert find_distance(9, 1) == 2, "Reverse First"
assert find_distance(10, 25) == 1, "Neighbours"
assert find_distance(5, 9) == 4, "Diagonal"
assert find_distance(26, 31) == 5, "One row"
assert find_distance(50, 16) == 10, "One more test"
Jan. 15, 2020
Comments: