Sunflower creative solution for Colder-Warmer by veky - python coding challenges

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

Sunflower solution in Creative category for Colder-Warmer by veky

def sgn(x):  # signum function
    try: return x//abs(x)
    except ZeroDivisionError: return 0


def checkio(steps):
    for index in range(100):  # 61 is 100//goldenratio, prime to 10
        oldQ, point1 = None, divmod(61 * index % 100, 10)
        for *point2, direction in steps:  # comparing quadrances
            Q = sum((x1 - x2)**2 for x1, x2 in zip(point1, point2))
            if not Q or oldQ and sgn(oldQ - Q) != direction: break
            oldQ = Q
        else: return point1

Dec. 24, 2013

Comments:

veky on Dec. 24, 2013, 3:53 a.m.
Let's see who will get the sunflower reference. ;-)

floord on Dec. 24, 2013, 10:37 a.m.
what is this sunflower reference you're talking about? (sorry, I'm super curious)

veky on Dec. 24, 2013, 10:46 a.m.
Let's wait a bit more... there's plenty of hints in the comments. ;-)

bryukh on Dec. 24, 2013, 10:20 p.m.
I can suppose, Is it related for Fibonacci numbers in subflower (and golden ratio)

bryukh on Dec. 24, 2013, 10:26 p.m.
I mean the pattern of seeds in a sunflower.

veky on Dec. 24, 2013, 11:46 p.m.
Yeah, good catch. But why is it used here? :-) (It's not just aestetics.;)

bryukh on Dec. 25, 2013, 12:12 a.m.
I've not read it too deep yet. But now i'm excited in doing it stronger :)

veky on Dec. 29, 2013, 9:10 p.m.
Ok, enough time has passed, I think noone is still trying to figure it out. (If you do, spoiler alert. If you don't, apologies for length of this:). So, what's the difference from (Parentheses) solution? This one is deterministic. The previous solution relied on randomness of set.pop to provide a good "next" candidate to try. Of course, randomness isn't really needed - what's needed is a good "coverage", such that candidates in order tried fall on various distances from the goal, so we can extract useful information from "colder" and "warmer" hints. For example, if we tried them in order, most probably we would get many "warmer" answers in the beginning. And if the goal were around (8,8), we would need about 15 tries, which is obviously too much. So, we need the tries to cover as much "area" as possible, and do it fast. This is a pretty hard problem in general, so let's move to 1D instead of 2D, and hope that the solution for 1D will be ok in 2D, too. So we'll consider Z_100 (or in Python speak, range(100), modulo 100). Also, coverage is not the only requirement - we would like them to be easily generated, ideally by calling one built-in Python function. range is pretty simple, and it generates arithmetical sequences, so let's try only arithmetical sequences (mod 100). Even simpler, let's start them at 0 (so we don't need parentheses, writing i * d % 100 instead of (a0 + i * d) % 100 :)). We've reduced the problem to finding an appropriate d. But first, one important condition on d is that it actually generates all numbers in Z_100. Not all d are such - for example, if we try d = 5, we would get only numbers divisible by 5: 0, 5, 10, 15,..., 95, and 0 again. So we'll never get 1 for example. Math tells us this condition is equivalent to d being coprime to 100 (nice thing is that, since 100 is square of 10, this is equivalent to being coprime to 10, and it gives us a good hunch that reduction from 2D to 1D is not so bad here). There are only EulerPhi(100) = 40 of them. Of course, some of them are obviously no good: up there we've shown that 1 is bad, and 99 is also, by the same argument. Moreover, d and 100 - d are almost equally good, in the same fashion - so we can try only those up to 50. That leaves 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47 and 49. We could try them all (and I actually have, results are below), but let's try to be mathematical a bit more. Why is 33 not so good? Because one, we need 4 tries to cover the whole board (0, 33, 66, 99), and two and more important, when we do, we start covering almost the same numbers as in the previous pass (32, 65, 98, then 31, 64, 97,...) The number 16 will take a very long time to get close to. Good numbers shouldn't behave like that: the passes themselves have to be short, and not close to each other on adjacent passing. This property, as vague as it seems, actually can be quantified mathematically: Euclid's algorithm with numbers d and 100 not only has to give 1 as final answer (they have to be coprime), but also has to have as many steps as possible. For example, 100 % 33 = 1 already (1 step). That's pretty bad (of course, d = 1 takes 0 steps, that's worse:). A "random" number such as 13 is a bit better: 100 % 13 = 9, 13 % 9 = 4, 9 % 4 = 1 (3 steps). Can we top that? Math comes to the rescue again. Steps are bounded by diminishing remainders: every remainder has to be less than the divisor, so 100 > 13 > 9 > 4 > 1. When we want to have as many steps as possible, that means that remainder has to get smaller slowly. But it can get smaller by at least one divisor, so the smallest difference we'll get is when all quotients are equal to 1. Even this we don't have to guess: math tells us it happens when we do Euclid's algorithm with consecutive Fibonacci numbers (for example, 55 % 34 = 21, 34 % 21 = 13, 21 % 13 = 8, 13 % 8 = 5, 8 % 5 = 3, 5 % 3 = 2, 3 % 2 = 1, all with the quotient 1). In fact it's easy to prove by induction, by reversing the algorithm: the smallest before 1 must be 2, and then the one before that has to be 1 + 1 * 2 = 3, the next one 2 + 1 * 3 = 5, and we get Fibonacci sequence). The only problem here is that one number is fixed at 100, and 100 is not a Fibonacci number, not even close (after 55 we have 89, and then 144). :-( Can we save ourselves? Of course. Math tells us that consecutive Fibonacci numbers have ratios approximating famous golden section, g = (1 + sqrt(5)) / 2 . What number has the same approximating ratio to number 100? Of course, 100 // g. If we're lucky, it will be coprime to 100 (and 10), and we're done. Actually, g is about 1.618, and golden section has a nice property g = a / b => g = (a + b) / a, so 1.618... = 1.618... / 1 = (1 + 0.618...) / 1 = 1 / 0.618... = 100 / 61.8..., which means that our number is int(100 / 1.618...) = int(61.8...) = 61. It is prime, not only coprime to 10(0), so we're good. (62 would be a better approximation to 61.8..., but it's not coprime to 10, since both are even.) Now, what on Earth does it have to do with sunflowers? Turns out that plants have almost the same problem, and they solve it in the same way (more precisely, they find the same solution by completely different means: blind genetic engineering through millions of years:). Their leaves, and in the case of sunflower their seeds, have to be a) equidistantly distributed around the stalk (or stigma), and b) have as much coverage as possible, to collect as much Sun's energy as possible and not to get in the way of one another. That gives a quasiperiodic order shown on <a href="http://momath.org/home/fibonacci-numbers-of-sunflower-seed-spirals/">this nice page</a>. The sunflowers are better than most plants to study since they solve the problem in 2D, instead of 3D (for leaves of most plants). Now, what changes when we look at our original problem in 2D instead of 1D? Conceptually not much, surprisingly. If we ignore carries when adding d to current position, it's almost as if Z100 is Z10 squared, with adding by components. So we can apply the above thinking to each digit separately, and since EulerPhi(10) is only 4 (1, 3, 7 and 9), there are only a few promising candidates for d. Trying these, and varying the a0 (starting point for arithmetical sequence, which helps a bit since we're not starting at the corner, so second try isn't almost certainly "warmer", it gives us a bit more information ["a bit" here used in mathematical sense, about one bit of entropy:]), we find a few really good ones. So, results of my tests: these d(<50) and a0 give arithmetical sequences (mod 100) that find every goal in 8 steps or less. <pre class='brush: python'>d: possible a0s 3: 41, 42 9: 25, 36, 37, 79, 89 11: 23, 33, 42, 52 27: 26 </pre> But still I like d = 61 with a0 = 0. It's simple, mathematically elegant, reminds me of sunflowers, and good enough for this task (finds all goals in at most 10 tries). Any questions (has anybody survived, at all)? :-D

bryukh on Dec. 29, 2013, 9:28 p.m.
Awesome. I will leave it for holiday weekends reading :)

floord on Dec. 30, 2013, 9:43 a.m.
Hahaha, Veky, you are something... :)

nickie on Feb. 3, 2014, 8:49 p.m.
What you have here is an awesome solution; well done! I believe that you need 9 steps (also counting the first one) even for the best pairs of (d, a0) and 11 steps with (61, 0). E.g. for (11, 42) it takes 9 steps if the hidden square is (9, 9). My solution uses at most 8 steps but it takes much more time. Unfortunately, in the way I've written it, you cannot call it with l=[] so it's hard to compare them directly. I'll publish one that can be called with l=[] soon.

_Chico__5d82cee4f5234e78a5c65e on May 31, 2021, 1:52 p.m.
Ok I just scrolled down this page than I saw this big message... T h I s is t o o l o n g;) Btw. Good solution!

veky on June 1, 2021, 4:39 p.m.
I don't usually ask people this, but how old are you? You seem very childish, not necessarily in a positive way.

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.