Triangle Wave creative solution for Square Spiral by gyahun_dash - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Triangle Wave solution in Creative category for Square Spiral by gyahun_dash

from math import sqrt

def triangle(t, period):
    return period / 4 - abs(t % period - period / 2)

def saturate(signal, threshold):
    return max(-threshold, min(threshold, signal))

def coordinate(index):
    if index == 1: return (0, 0)

    orbit = (sqrt(index - 1) + 1) // 2
    arc = index - (2 * orbit - 1)**2

    coord = (triangle(arc + shift, 8 * orbit) for shift in (-orbit, orbit))
    return [saturate(z, orbit) for z in coord]

def find_distance(first, second):
    firstvec, secondvec = map(coordinate, (first, second))
    return sum(abs(f - s) for f, s in zip(firstvec, secondvec))

May 30, 2014

Comments:

gyahun_dash on May 31, 2014, 8:29 a.m.
<h1>Appendix (but longer than code)</h1> In this approach, numbers are converted to 2-D coordinates (x, y) to calculate <a href="http://en.wikipedia.org/wiki/Taxicab_geometry">Manhattan distance</a> between them. <a href="http://en.wikipedia.org/wiki/Triangle_wave">Triangle wave</a> is used for the converting. <hr /> Let 1 be center(0, 0), horizontal be x-axis(right as positive) and vertical be y-axis(downward as positive). For example, 2(0, -1), 9(-1, -1) and 13(2, -2). <pre class='brush: python'>orbit = (sqrt(index - 1) + 1) // 2 </pre> We find that a shape containing numbers from 1 to another odd square(9, 25, 49, ...) is a square. Then, count-up means march along the edges of the squares clockwise from right of left top to the left top, and when march reaches the left top, march goes next square. So we call the four edges in one square "orbit". 1st orbit contains 2-9, 2nd 10-25. <pre class='brush: python'>arc = index - (2 * orbit - 1)**2 </pre> arc means clockwise distance from the left top of the square. In 1st orbit, arc(2) = 1, arc(5) = 4 and arc(9) = 8. <hr /> <pre class='brush: python'>number 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ------------------------------ ----------------------------------------------- arc 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 x 0 1 1 1 0 -1 -1 -1 -1 0 1 2 2 2 2 2 1 0 -1 -2 -2 -2 -2 -2 y -1 -1 0 1 1 1 0 -1 -2 -2 -2 -2 -1 0 1 2 2 2 2 2 1 0 -1 -2 </pre> We find that lengths of orbits are multiples of 8 and that x-values and y-values in one orbit are similar and periodic. So we can formulate the series. <pre class='brush: python'>def triangle(t, period): return period / 4 - abs(t % period - period / 2) </pre> When period = 8, the above function returns values as follows (looks like a pyramid): <pre class='brush: python'>t 0 1 2 3 4 5 6 7 ------------------------------ return -2 -1 0 1 2 1 0 -1 </pre> When period = 16: <pre class='brush: python'>t 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ------------------------------------------------------- return -4 -3 -2 -1 0 1 2 3 4 3 2 1 0 -1 -2 -3 </pre> So we can get same series as x,y-values by saturating values using following function: <pre class='brush: python'>def saturate(signal, threshold): # threshold = period / 4 return max(-threshold, min(threshold, signal)) </pre> When period = 16 (orbit = 2, 0 means 16): <pre class='brush: python'>t 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 -------------------------------------------------------- triangle -4 -3 -2 -1 0 1 2 3 4 3 2 1 0 -1 -2 -3 saturate -2 -2 -2 -1 0 1 2 2 2 2 2 1 0 -1 -2 -2 -------------------------------------------------------- x -2 -1 0 1 2 2 2 2 2 1 0 -1 -2 -2 -2 -2 y -2 -2 -2 -2 -2 -1 0 1 2 2 2 2 2 1 0 -1 </pre> Then, we find that x and y-values are shifted -2 and +2 (i.e. period / 8) from saturated triangle wave. So we get them by assigning tringle with shifted values as follows: <pre class='brush: python'>coord = (triangle(arc + shift, 8 * orbit) for shift in (-orbit, orbit)) return [saturate(z, orbit) for z in coord] </pre> <hr /> Finally, we can get the Manhattan distance between the coordinates. That's all folks!

gyahun_dash on May 31, 2014, 4:45 p.m.
Incorrect: <pre class='brush: python'>def saturate(signal, threshold): # threshold = period / 4 return max(-threshold, min(threshold, signal)) </pre> Correct: <pre class='brush: python'>def saturate(signal, threshold): # threshold = orbit = period / 8 return max(-threshold, min(threshold, signal)) </pre>

MackM on Aug. 4, 2014, 4:39 p.m.
Excellent code, and excellent explanation. Thank you for taking the time to share.

gyahun_dash on Aug. 5, 2014, 11:41 a.m.
It's my pleasure.

SandeepManilal on Dec. 1, 2014, 4:35 p.m.
Very Nice!

gyahun_dash on Dec. 11, 2014, 1:19 p.m.
Thank you!

Dropbox

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.