# Evolutes

`This next article was inspired by two sources:`

An Advent of Code puzzle from 2017

An evolute is a matrix whose cells are numbered to spiral out from the center.

``````17  16  15  14  13
18   5   4   3  12
19   6   1   2  11
20   7   8   9  10
21  22  23---> ...``````

The first question asks us to find the Manhattan distance between some positive integer cell and the 1st cell.

I see two ways to do this:

1. Build the evolute, find the location of the integer and then calculate the distance
2. Calculate the coordinate with respect to the center directly and take the sum of the absolute value of the coordinates.

I will start with the second method because it is simpler. If we look at the structure of the evolute we will see that each new layer of the matrix will have an odd square in it’s bottom right corner. 1 9 25 49 ….

That means we can locate the layer by finding the nearest odd square root. Here is the code for that:

`f:{j:floor sqrt x; j - not j mod 2}q)f 103q)f 255q)f 243`

Next we can find the grid coordinate or how far we are from the center for that corner. I plugged in max x so we can use the function on lists of numbers. The ‘?’ verb is being used to find index which corresponds to the steps away from the center.

`g:{(1+2*til max x)?f x} q)g 101q)g 252q)g 241`

Now all we need to do is figure out where we are on the layer.

We can be in one of 5 places:

1. Exactly at the end of a layer
2. Between the bottom right corner and the top right corner
3. Between the top right corner and the top left corner
4. Between the top left corner and the bottom left corner
5. Between the bottom left corner and the end of the layer

We can divide by the size of the layer to calculate this. We can also find the remainder to know how far between we are. This gives us the following code:

`place:{(x-j*j) div 1+j:f x}offset:{(x-j*j) mod 1+j:f x}q)place 1+til 250 0 1 1 2 2 3 3 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 0q)offset 1+til 250 1 0 1 0 1 0 1 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0`

This allows us to write the full function to calculate the coordinate. All we need to do is to check which of those conditions are met fill in the coordinates from g, plus the appropriate offset and correct sign.

`coordinate:{[x]    x:(),x;    f:{j:floor sqrt x; j - not j mod 2};    g:{(1+2til max x)?y};     place:{(x-yy) div 1+y};    offset:{(x-yy) mod 1+y};      j:f x;     brc:x=jj;     grid:g[x;j];     p:place[x;j];     o:offset[x;j];    ?[brc;flip (grid;neg[grid]);     ?[0=p;flip (grid+1;neg[grid]+o);      ?[1=p;flip (grid+1-o;grid+1);       ?[2=p;flip (neg[grid+1];1+grid-o);        flip (neg[grid+1]+o;neg[1+grid])]]]]    }q)coordinate 1+til 90  0 1  1 1  1 0  1 -1 1 -1 0 -1 -10  -11  -1`

At this point we can find the coordinate of any cell number. Since we can do this for all the points, we should be able to create the evolute for any dimension by generating all the coordinates and then shifting them to the appropriate column/row number and inserting them into that matrix. We can do this cleverly by sorting the row and column separately, since we want a particular orientation and sorting each of them corresponds to either a horizontal transposition or a vertical transposition.

`evol:{t:`row`col!(x div 2)+flip cordinate j:1+til x*x; (x;x)#exec val from `col xdesc `row xasc flip update val:j from t} q)evol 737 36 35 34 33 32 3138 17 16 15 14 13 3039 18 5  4  3  12 2940 19 6  1  2  11 2841 20 7  8  9  10 2742 21 22 23 24 25 2643 44 45 46 47 48 49`

Now that we can create a evolute and we see that given an evolute we can find the coordinates, we also see that permuting the row and column indexes gives us different orientations. This leads us to see how Joey Tuttle/Eugene McDonnell created an evolute from  scratch. Let’s raze an evolute:

`q)raze evol 517 16 15 14 13 18 5 4 3 12 19 6 1 2 11 20 7 8 9 10 21 22 23 24 25`

Now let us permute it by the magnitude and then look at the differences:

`q)iasc raze evol 512 13 8 7 6 11 16 17 18 19 14 9 4 3 2 1 0 5 10 15 20 21 22 23 24q)deltas iasc raze evol 512 1 -5 -1 -1 5 5 1 1 1 -5 -5 -5 -1 -1 -1 -1 5 5 5 5 1 1 1 1q)deltas iasc raze evol 34 1 -3 -1 -1 3 3 1 1`

We now see a pretty clear pattern. We are repeating a pattern of 1,neg x,-1,x.
Each time we are taking 2 elements from the pattern. We take an increasing number of them and continue until we take x elements in shot. Here is Eugene’s explanation translated into q

`f:{-1+2*x}g:{(-1;x;1;neg x)}k:{(f x)#g x}h:{1+til x}j:{-1 _ raze 2#'h x}l:{-1 rotate raze (j x)#'k x}m:{iasc sums l x}n:{(x;x)#m x}q)f 59  q)g 5- -1 5 1 -5  q)k 5-1 5 1 -5 -1 5 1 -5 -1  q)h 51 2 3 4 5  q)j 51 1 2 2 3 3 4 4 5q)l 5-1 -1 5 1 1 -5 -5 -1 -1 -1 5 5 5 1 1 1 1 -5 -5 -5 -5 -1 -1 -1 -1  q)m 524 23 22 21 20 9 8 7 6 19 10 1 0 5 18 11 2 3 4 17 12 13 14 15 16  q)n 524 23 22 21 209  8  7  6  1910 1  0  5  1811 2  3  4  1712 13 14 15 16`

Combining this into function we get:

`evolute:{(x;x)#iasc sums -1 rotate raze (-1 _ raze 2#'1+til x)#'(-1+2*x)#(1;neg x;-1;x)}`

We can shorten it just a bit and make it a bit faster by seeing that grabbing parts j,k,l can make use of how kdb overloads ‘where’. In KDB ‘where’ gives you the indexes of the 1s in a boolean mask. For example:
q)where 101b
0 2
However, a little thought reveals that we are returning the index of the element the number at that index. So we return one 0, zero 1,one 2. Generalizing this, we can think that where of 1 2 3 should return one 0,two 1s and three 2s and indeed KDB does this.
q) where 1 2 3
0 1 1 2 2 2
Knowing this, we can rewrite j k and l, which make heavy use of each and remove all the razing.
I am going to show how I built this up.

`q){((x-1)#2),1} 52 2 2 2 1q){1+where ((x-1)#2),1} 5 1 1 2 2 3 3 4 4 5q){(where 1+(where ((x-1)#2),1))} 50 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 8q){(where 1+(where ((x-1)#2),1)) mod 4} 5 /so that we cycle0 1 2 2 3 3 0 0 0 1 1 1 2 2 2 2 3 3 3 3 0 0 0 0 0q){(1;neg x;-1;x)(where 1+(where ((x-1)#2),1)) mod 4} 5 1 -5 -1 -1 5 5 1 1 1 -5 -5 -5 -1 -1 -1 -1 5 5 5 5 1 1 1 1 1q){-1 rotate (1;neg x;-1;x)(where 1+(where ((x-1)#2),1)) mod 4} 51 1 -5 -1 -1 5 5 1 1 1 -5 -5 -5 -1 -1 -1 -1 5 5 5 5 1 1 1 1`

The last step recreates l. So the whole function using where looks like this:

`evolute:{(x;x)#iasc sums -1 rotate (1;neg x;-1;x)(where 1+(where ((x-1)#2),1)) mod 4}`

Part 2 of the advent of code is even more interesting. It describes us filling the spiral by summing the neighbors, the center square starts at 1. Here is the description from advent.

`Then, in the same allocation order as shown above, they store the sum of the values in all adjacent squares, including diagonals.So, the first few squares' values are chosen as follows:Square `1` starts with the value `1`.Square `2` has only one adjacent filled square (with value `1`), so it also stores `1`.Square `3` has both of the above squares as neighbors and stores the sum of their values, `2`.Square `4` has all three of the aforementioned squares as neighbors and stores the sum of their values, `4`.Square `5` only has the first and fourth squares as neighbors, so it gets the value `5`.Once a square is written, its value does not change. Therefore, the first few squares would receive the following values:`
``````147  142  133  122   59
304    5    4    2   57
330   10    1    1   54
351   11   23   25   26
362  747  806--->   ...``````
`What is the first value written that is larger than your puzzle input?`

Now given our earlier coordinate function, we just need to add elements in into empty matrix of 0s and sum the neighbors at each step to determine what to add.  First, let’s write the simple pieces of finding the neighbors and summing them. Then we will conquer the composition.

`/To find the neighbors according to our rule, / we basically find the coordinates for (1..9)/ then we can add to x pair so it's centered around that one neighbors:{x+/:coordinate 1+til 9}q)neighbors (1;0)0  11  11  20  2-1 2-1 1-1 00  01  0/We need to shift our coordinate system depending on the size of the matrix shift:{i:div[count x;2]; (i+y)}q)shift[3 3#0;coordinate 5]0 2/calculate the sum of the neighbors sumN:{sum over .[x] each neighbors y}q)(1+evolute 5)17 16 15 14 1318 5  4  3  1219 6  1  2  1120 7  8  9  1021 22 23 24 25q)(1+evolute 5)[2;3]2/Manually sum the neghbors of 2q)sum 4 3 12 1 2 11 8 9 1060q)sumN[1+evolute 5;(2;3)]60`

Okay, we are going to start with a matrix that has single 1 in the center.

`center1:{.[(x;x)#0;(a;a:x div 2);:;1]} /we are ammending a 1 at the x div 2q)center1  50 0 0 0 00 0 0 0 00 0 1 0 00 0 0 0 00 0 0 0 0`

Now that we see how easy it is to amend an element at a particular index, we can combine this with the notion of a fold(over). The idea is that we will keep updating this matrix with new elements based on the neighbor sum:

`cumEvolute:{{.[x;y;:;sumN[x;y]]}/[j;shift[j:center1[x]] coordinate 1+til (x*x)]}q)cumEvolute 5362 351 330 304 147747 11  10  5   142806 23  1   4   133880 25  1   2   122931 26  54  57  59 /If we want to rotate it we can simply reverse flipq)reverse flip cumEvolute 5147 142 133 122 59 304 5   4   2   57 330 10  1   1   54 351 11  23  25  26 362 747 806 880 931`

Using cumEvolute we can find when we generate the first integer bigger than the input, by creating a stopping condition and counting the number of iterations.

`stopCum:{{\$[z<max over x;x;.[x;y;:;sumN[x;y]]]}/[j;shift[j:center1[x]] coordinate 1+til (x*x);y]}q)stopCum[5;20]0 0  0  0 00 11 10 5 00 23 1  4 00 0  1  2 00 0  0  0 0q)max over stopCum[5;20]23q)max over stopCum[10;100]122`

# Controlling the Tower

I recently came across this problem and it looked interesting enough, so I solved it. It’s from Topcoder, which is nice because they provide test cases so you can be sure that you have solved it.

Unfortunately, Topcoder has dracanion copyright laws, so I will paraphrase the problem in case the link to the description dies. You want to control some territory, the territory has t (an integer) towers and each tower is a certain number of stories s (an integer). To control the territory you must control the majority of the active towers. A tower is active if someone controls the majority of stories in a tower. If a tower has no majority controller, it is inactive and does not count. What is the minimum number of stories you must win to guarantee control of the territory?

The first thing that helped me was converting the test cases into the following two lists and created a table:

inputs:((47);(9;9);(1;1;1;1;1;1);(2;2;2;2;2;2);(1;2;3;4;5;6;7;8;9);(1;2;3;4;5;6;7;8;9;10);(1;1;100;100;100;100;200;200);(2);(999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999;999);(2;3;9);(1);(3);(4);(5);(6);(1;1);(1;2);(2;2);(1;3);(1;4);(2;3);(2;4);(3;3);(100;100);(1;1;1);(1;2;1);(2;2;1);(2;2;2);(10;100;900);(9;99;999);(2;8;4);(2;2;2;2);(2;2;2;2;4);(784;451;424;422;224;478;509;380;174;797;340;513;842;233;527;342;654;816;637);(342;574;20;606;413;479;51;630;802;257;16;925;938;951;764;393;766;414;764;208;959;222;85;526;104;848;53;638;969;214;806;318;461;950;768;200;972;746;171;463);(877;587;587;325;528;5;500;714;548;688;243;5;508;783;561;659;297;44;70;131;329;621;374;268;3;113;782;295;902);(159;797;323;629;647;941;75;226);(528;259;717;920;633;957;712;966;216;812;362;146;472;462;140;743;672;512;232;16;186;721;171;831;641;446;183;483;198;55;610;489;884;396;344;499;368;618;812;211;771;449;289);(608;405;630;751;288;836))
results:(24;14;4;7;36;45;699;2;37451;12;1;2;3;3;4;2;3;3;4;5;4;5;5;150;2;3;4;4;955;1053;11;5;8;7806;18330;10838;3404;18074;2866)
t:([]inputs;results)

q)select results, inputs from asc t  / just to give a visual sample

results inputs
———————————–
1      1
2      2
2      3
3      4
3      5
4      6
24     47
2      1 1
2      1 1 1
4      1 1 1 1 1 1
699  1 1 100 100 100 100 200 200

That way, I could write a function and start testing and seeing if I was making progress.

If there is only one tower, then I obviously need to take it, which means I need to take the majority.

So that is pretty easy:

f{[x] if[count[x]=1; :sum 1+floor x%2]; :0} /one tower,
/ otherwise return 0 this is wrong but we want to return a number

I can run my function and see which cases I still haven’t solved:

q) select myResult, results, inputs from (update myResult:f each inputs from t ) where myResult<>results

This gave me a way to check if I was making progress.

Next, we know that we need to win the majority of the towers and we need to win them in the most expensive way possible in order to guarantee a victory because we don’t get to chose how our stories our distributed. So we sort the towers desc by height and fill up half of them. Then comes the tricky part, the opposition can have a simple majority in all the other towers. In that case, there will be one final tower that decides everything.

For example, suppose there are 5 towers, 6 6 5 5 4. We need to win three towers. So we win the first 2 by getting 12 stories. Then we only need one more tower but the opposition can strategically win the shortest towers. It’s important to note that winning a 4 story tower and a 5 story tower takes 3 either way. So they can do better by winning the two 5 story towers and simply stop me from winning the 4 story tower by taking 2 stories.

This explains the following slightly convoluted algorithm:

f:{
if[count[x]=1;:sum 1+floor x%2]; /one tower
t:floor count[x]%2; / majority of towers, one less if there are an odd number
v:sum t#x:desc x; /most expensive way to win t towers
r:reverse (t-count[x])#x; /remaining towers
o:sum 1+floor %[;2] t#r; /opposition needs to take at least t towers
o+:sum floor 0.5+%[;2] d _ r; /oppositions needs to prevent the rest
o-:(any(d _ r)mod 2)*(any not(d#r)mod 2) ;
/subtract if opposition wins during preventing
/ and you can strategically exchange an odd tower with an even one
v+1+sum[r]-o
};

If anyone has a simpler, more straightforward approach, or wants to tell me how my approach is wrong, I would love to hear about it.