//////////////////////////////////////////////////////////////////////////////// // Revised tables & functions for knight's path distance and count // Magma, Fred Lunnon, Maynooth 18/05/14 hoptab := // knight move offsets [ [2, 1], [2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2], [-2, 1], [-2, -1] ]; // Knight-move path length: recursive table for board radius l // d(x, y) = 1 + \min_{[u, v] nhbr & d(u, v) < d(x, y)} d(u, v) ; // require all d-distant points available before increment to d+1 !! infty := -1; // unset function disthop (l) local m, dist, i, j, k, P, Q, R; m := l+2; // wiggle room dist := [ [ infty : j in [-m..+m] ] : i in [-m..+m] ]; // reset lengths dist[0+m+1, 0+m+1] := 0; // initialise array, centre origin newlis := [ [0, 0] ]; k := 0; // Dijkstra distance finder while #newlis gt 0 do curlis := newlis; newlis := {}; k := k+1; // k := dist[ P[1]+m+1, P[2]+m+1 ] + 1; for P in curlis do for Q in hoptab do R := [ P[1]+Q[1], P[2]+Q[2] ]; if dist[ R[1]+m+1, R[2]+m+1 ] eq infty then dist[ R[1]+m+1, R[2]+m+1 ] := k; if Max(Abs(R[1]), Abs(R[2])) le l then Include(~newlis, R); end if; end if; end for; end for; end while; return [ [ dist[i+m+1, j+m+1] : j in [-l..+l] ] : i in [-l..+l] ]; // clip end function; //l := 10; // table size //disttab := disthop(l); //Matrix(disttab); // output entire // Knight-move path number: recursive table for board radius l // e(x, y) = \sum_{[u, v] nhbr & d(u, v) < d(x, y)} e(u, v) ; // require all d-distant points available before increment to d+1 !! unset := 0; // uncounted function pathhop (l) local m, path, i, j, P, Q, R, S; m := l+4; // wiggle room path := [ [ unset : j in [-m..+m] ] : i in [-m..+m] ]; // reset counts path[0+m+1, 0+m+1] := 1; // initialise array, centre origin newlis := [ [0, 0] ]; // Dijkstra distance finder while #newlis gt 0 do curlis := newlis; newlis := {}; for P in curlis do for Q in hoptab do R := [ P[1]+Q[1], P[2]+Q[2] ]; if Max(Abs(R[1]), Abs(R[2])) le l+2 and path[ R[1]+m+1, R[2]+m+1 ] eq unset then path[ R[1]+m+1, R[2]+m+1 ] := &+[ path[ R[1]+S[1]+m+1, R[2]+S[2]+m+1 ] : S in hoptab]; Include(~newlis, R); end if; end for; end for; end while; return [ [ path[i+m+1, j+m+1] : j in [-l..+l] ] : i in [-l..+l] ]; // clip end function; // Explicit formula for length d of minimal path to [x, y] : // in general d = (X-Y) - 2*[min( (X-2Y)/4, (X-2Y)/3 )] ; // (adapted and corrected from SACO 2007 Day 1) function distfun (x, y) local X,Y; X := Max(Abs(x), Abs(y)); Y := Min(Abs(x), Abs(y)); // first octant return /*if*/ ([X,Y] eq [1,0]) select 3 else /*if*/ ([X,Y] eq [2,2]) select 4 // special cases // else /*if*/ ([X,Y] eq [1,1]) select 4 // [0,0] corner else (X-Y) - 2*Floor(Min( (X-2*Y)/4, (X-2*Y)/3 )) /*end if*/; end function; // Explicit formulae for length, number [d, e] of minimal paths to [x, y] : // 7 cases; note A,B-regions overlap for 0 <= Z <= 2 . function dispatfun (x, y) local e, d, s, t, X, Y, Z; X := Max(Abs(x), Abs(y)); Y := Min(Abs(x), Abs(y)); // first octant Z := X-2*Y; if [X,Y] eq [1,0] then d := 3; e := 12; // special cases elif [X,Y] eq [2,2] then d := 4; e := 54; elif Z ge 0 then // A-region: axial, rook-like s := Z mod 4; t := Z div 4; d := (X-Y) - 2*t; e := Binomial(d, t); if s eq 1 then e := e * ( d^2 - (2*t+1)*d + 2*t*(t+1) ) / (t+1) ; elif s eq 2 then e := e * ( d^4 + (-4*t-6)*d^3 + (8*t^2+24*t+15)*d^2 + (-8*t^3-32*t^2-36*t-10)*d + (4*t^4+16*t^3+20*t^2+8*t) ) / ( 2*(t+2)*(t+1) ); elif s eq 3 then e := e * ( d^6 + (-6*t-15)*d^5 + (18*t^2+90*t+103)*d^4 + (-32*t^3-228*t^2-496*t-315)*d^3 + (36*t^4+312*t^3+936*t^2+1110*t+418)*d^2 + (-24*t^5-228*t^4-808*t^3-1290*t^2-866*t-156)*d + (8*t^6+72*t^5+260*t^4+480*t^3+452*t^2+168*t) ) / ( 6*(t+3)*(t+2)*(t+1) ); else; end if; // s eq 0 else // Z le 2 : B-region: diagonal, bishop-like s := Z mod 3; t := -(Z div 3); d := (X-Y) + 2*t; e := Binomial(d, t); if s eq 1 then e := e * d * ( d^2 - 3*t*d + (3*t^2-1) ) / ( (t+1)*(d-t+1) ); elif s eq 2 then e := e * d * ( d^5 + (-6*t-3)*d^4 + (15*t^2+17*t-1)*d^3 + (-18*t^3-32*t^2+12*t+23)*d^2 + (9*t^4+30*t^3-12*t^2-59*t)*d + (-15*t^4+59*t^2-20) ) / ( 2*(t+2)*(t+1)*(d-t+2)*(d-t+1) ) ; else; end if; // s eq 0 end if; return [d, IntegerRing()!e]; end function; // Count a(d) along path hugging axis y = 0 qua function of distance d // e(4t+1, 1), e(4t+3, 0) ; [x, y] = [2 d - 3, (d + 1)mod 2] function axiscter (d) return Max(1, Binomial(d, d div 2 - 1)/6 * ( /*if*/ IsEven(d) select (d^2-2*d+6)*(d^2+8)/(d+4) else (d-1)*(d^2-2*d+15) /*end if*/ )); end function; // Count b(d) along path hugging diagonal x = y qua function of distance d // e(-3t-2, -3t-2), e(-3t, -3t-1) ; [x, y] = [ [(3 d - 3)/2], [(3 d - 4)/2] ] function diagcter (d) return Max(1, Binomial(d, d div 2 - 1)/2 * // diagonal-hugging path ( /*if*/ IsEven(d) select (d^3-d^2+30*d-40)/(d+4) else d*(d^2+2*d+33)/(d+5) /*end if*/ )); end function; // Output 2-D tables l := 19; // table size disttab := disthop(l); pathtab := pathhop(l); Matrix(disttab); // output entire Matrix(pathtab); // output entire [ [ dispatfun(x, y)[1] : y in [0..l] ] : x in [0..l] ]; [ [ dispatfun(x, y)[2] : y in [0..l] ] : x in [0..l] ]; // Compare explicit functions with recursive tables for distance & number // Note "disttab[x+l+1, y+l+1] le k" is replaceable by "... eq k" l := 100; // ~2 sec disttab := disthop(l); pathtab := pathhop(l); { dispatfun(x, y)[1] - disttab[x+l+1, y+l+1] : y in [0..l], x in [0..l] }; // check old = new function : { 0 } OK { dispatfun(x, y)[2] - pathtab[x+l+1, y+l+1] : y in [0..l], x in [0..l] }; // check old = new function : { 0 } OK // Check maximum count conjectures: m = [(3 d - 3)/2] { axiscter(k) - Max([ pathtab[x+l+1, y+l+1] : y in [0..2*k], x in [0..2*k] | disttab[x+l+1, y+l+1] le k ]) : k in [5..l div 2] }; // { 0 } OK { diagcter(Ceiling(2*(m+1)/3)) - Max([ pathtab[x+l+1, y+l+1] : y in [0..m], x in [0..m] ]) : m in [6..l] }; // { 0 } OK // Output [ axiscter (d) : d in [0..l] ]; [ diagcter (d) : d in [0..l] ]; [ Max([ pathtab[x+l+1, y+l+1] : y in [0..2*k], x in [0..2*k] | disttab[x+l+1, y+l+1] eq k ]) : k in [0..l div 2] ]; [ Max([ pathtab[x+l+1, y+l+1] : y in [0..m], x in [0..m] ]) : m in [0..l] ]; [ 1, 1, 2, 6, 28, 100, 330, 1050, 3024, 8736, 23220, 62700, 158004, 406692, 986986, 2452450, 5788640, 14002560, 32357052, 76640148, 174174520, 405623400, 909582212, 2089064516, 4633556448, 10519464000, 23120533800, 51977741400, 113365499940, 252725219460, 547593359850, 1211884139250, 2610998927040, 5741708459520, 12309472580460, 26917328938500, 57457069777800, 125016198060600, 265832233972140, 575824335603660, 1220234181784800 ]; [ 1, 1, 2, 9, 32, 85, 240, 588, 1512, 3564, 8700, 19965, 47124, 105963, 244244, 540540, 1224080, 2674984, 5974956, 12924522, 28553200, 61250490, 134104432, 285689624, 620826672, 1314933000, 2839363800, 5984393805, 12852021420, 26973910215, 57655813500, 120569654700, 256649540640, 535009931280, 1134692142540, 2358818719950, 4986548028000, 10340761857030, 21796919253120, 45102668144040, 94821703158000 ]; [ 1, 1, 2, 12, 54, 100, 330, 1050, 3024, 8736, 23220, 62700, 158004, 406692, 986986, 2452450, 5788640, 14002560, 32357052, 76640148, 174174520, 405623400, 909582212, 2089064516, 4633556448, 10519464000, 23120533800, 51977741400, 113365499940, 252725219460, 547593359850, 1211884139250, 2610998927040, 5741708459520, 12309472580460, 26917328938500 ]; [ 1, 12, 54, 54, 54, 54, 85, 240, 240, 588, 1512, 1512, 3564, 8700, 8700, 19965, 47124, 47124, 105963, 244244, 244244, 540540, 1224080, 1224080, 2674984, 5974956, 5974956, 12924522, 28553200, 28553200, 61250490, 134104432, 134104432, 285689624, 620826672, 620826672, 1314933000, 2839363800, 2839363800, 5984393805, 12852021420, 12852021420, 26973910215, 57655813500, 57655813500, 120569654700, 256649540640, 256649540640, 535009931280, 1134692142540, 1134692142540, 2358818719950, 4986548028000, 4986548028000, 10340761857030, 21796919253120, 21796919253120, 45102668144040, 94821703158000, 94821703158000, 195825873726600, 410720543218440, 410720543218440, 846739738410930, 1772108740270440, 1772108740270440, 3647615648094990, 7618942347630120, 7618942347630120, 15660031688889048, 32650847564232672 ]; // 2-D tables of path distance and count in triangular order l := 19; [ dispatfun(x, y)[1] : y in [0..x], x in [0..l] ]; [ dispatfun(x, y)[2] : y in [0..x], x in [0..l] ]; [ 0, 3, 2, 2, 1, 4, 3, 2, 3, 2, 2, 3, 2, 3, 4, 3, 4, 3, 4, 3, 4, 4, 3, 4, 3, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 6, 4, 5, 4, 5, 4, 5, 6, 5, 6, 5, 6, 5, 6, 5, 6, 5, 6, 7, 6, 6, 5, 6, 5, 6, 5, 6, 7, 6, 7, 8, 7, 6, 7, 6, 7, 6, 7, 6, 7, 8, 7, 8, 6, 7, 6, 7, 6, 7, 6, 7, 8, 7, 8, 9, 8, 7, 8, 7, 8, 7, 8, 7, 8, 7, 8, 9, 8, 9, 10, 8, 7, 8, 7, 8, 7, 8, 7, 8, 9, 8, 9, 10, 9, 10, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 10, 9, 10, 11, 10, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 10, 9, 10, 11, 10, 11, 12, 9, 10, 9, 10, 9, 10, 9, 10, 9, 10, 9, 10, 11, 10, 11, 12, 11, 12, 10, 9, 10, 9, 10, 9, 10, 9, 10, 9, 10, 11, 10, 11, 12, 11, 12, 13, 12, 11, 10, 11, 10, 11, 10, 11, 10, 11, 10, 11, 10, 11, 12, 11, 12, 13, 12, 13, 14 ]; [ 1, 12, 2, 2, 1, 54, 6, 2, 9, 2, 2, 6, 1, 3, 32, 6, 28, 6, 24, 3, 8, 24, 3, 18, 1, 12, 85, 6, 100, 16, 95, 12, 60, 4, 25, 240, 6, 70, 4, 50, 1, 30, 201, 10, 60, 40, 330, 35, 266, 20, 150, 5, 66, 588, 20, 210, 10, 180, 5, 120, 1, 60, 462, 15, 147, 1512, 1050, 90, 952, 66, 672, 30, 357, 6, 147, 1344, 35, 336, 20, 546, 15, 420, 6, 252, 1, 105, 1044, 21, 336, 3564, 70, 210, 3024, 182, 2464, 112, 1576, 42, 784, 7, 288, 2970, 56, 756, 8700, 1456, 35, 1288, 21, 896, 7, 476, 1, 168, 2277, 28, 702, 7965, 126, 1680, 8736, 448, 7938, 336, 5868, 176, 3453, 56, 1584, 8, 513, 6390, 84, 1620, 19965, 252, 70, 3528, 56, 2808, 28, 1764, 8, 828, 1, 252, 4720, 36, 1350, 17182, 210, 3630, 47124, 1008, 23220, 882, 19260, 576, 13050, 261, 7090, 72, 2970, 9, 850, 13310, 120, 3267, 43824, 462, 7920, 8820, 126, 7920, 84, 5715, 36, 3240, 9, 1350, 1, 360, 9251, 45, 2420, 35970, 330, 7524, 105963, 924, 62700, 2100, 57387, 1620, 43725, 930, 27335, 370, 13706, 90, 5225, 10, 1331, 26664, 165, 6204, 92950, 792, 16731, 244244 ]; ////////////////////////////////////////////////////////////////////////////////