|
| |
|
|
A360923
|
|
Table T(i,j), i >= 0, j >= 0, read by antidiagonals giving the smallest number of moves needed to win Integer Lunar Lander, starting from position (i,j). Game rules in comments.
|
|
5
|
|
|
|
0, 2, 1, 3, 3, 4, 4, 4, 5, 7, 4, 5, 6, 7, 9, 5, 5, 6, 8, 10, 12, 5, 6, 7, 8, 10, 12, 14, 6, 6, 7, 9, 10, 12, 14, 17, 6, 7, 8, 9, 11, 13, 15, 17, 19, 6, 7, 8, 9, 11, 13, 15, 17, 19, 21, 7, 7, 8, 10, 11, 13, 15, 17, 19, 22, 24, 7, 8, 9, 10, 12, 13, 15, 17, 20, 22, 24, 26
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
A position in the game of Integer Lunar Lander consists of an ordered pair (i,j) of integers. There are always 3 legal moves, to (i+1,j+i+1), (i,j+i), and (i-1,j+i-1). The object of the game is to reach (0,0) in the minimum possible number of moves, T(i,j). The listed data was provided by Tom Karzes.
The ordered pair may be interpreted as the upward velocity and altitude of a vehicle; the object is to land the vehicle at zero velocity. In this version negative altitudes are permitted (that is, there is no crash detection, and the optimal trajectory is allowed to go underground without ill effects).
Are any of the numbers different if crashes are forbidden? It seems not, slowing to a soft landing always seems to produce a better solution than overshooting the surface and climbing back up. Of course from some initial positions like (-5,1) it is impossible not to crash. But it appears that if a soft landing is possible, then the optimal solution doesn't crash.
The game was invented in the early 1970's as a trivial version of a two-dimensional pencil-and-paper game that has been played at least since the first half of the 20th century.
Solution lengths for the corresponding game on triples would be interesting for (0,0,n) or (n,0,0).
Conjecture 1: For all i, j, T(i,j) differs from its eight neighbors by at most 3. The array of differences {T(i+1,j) - T(i,j)} might be worth studying, as well as the array {T(i,j) mod 2}. - N. J. A. Sloane, Feb 25 2023
Conjecture 2 (Start)
The zeroth row (0,j) is T(0,j) = 1+ floor(sqrt(4j-3)). j>0.
Let t_k = k(k+1)/2 be a triangular number.
Then the i-th row, {(i,j), j>=0}, is given by
T(i,j) = T(0, j+t_{i-1}) + i for i>0.
In other words, to get the i-th row, shift the zeroth row to the left by i*(i-1)/2 places and add i to each term.
This would imply that the leading column, T(i,0), is equal to i+1+floor(sqrt(2*i^2-2*i-3)) for i >= 2.
Conjecture 1 seems to hold for all (i,j) except (1,0) and (2,1). - M. F. Hasler, Feb 27 2023
|
|
|
REFERENCES
|
Martin Gardner, "Sim, Chomp, and Race Track", "Mathematical Games", Scientific American, January, 1973. Reprinted in "Knotted Doughnuts and Other Mathematical Entertainments", W. H. Freeman, 1986, pp. 109-122.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
For the starting position (2,3), a 6-move solution is (1,4), (0,4), (-1,3), (-2,1), (-1,0), (0,0). No shorter solution is possible, so T(2,3) = 6.
The upper left corner of the table i:
0 2 3 4 4 5
1 3 4 5 5
4 5 6 6
7 7 8
9 10
12
The first few antidiagonals are
0
2 1
3 3 4
4 4 5 7
4 5 6 7 9
|
|
|
PROG
|
(C++) See Links section.
(PARI) M360923=Map(); T360923=0; S360923=[[0, 0]]; A360923(v, x)={iferr(mapget( M360923, [v, x]), E, while(!setsearch(S360923, [v, x]), foreach(S360923, vx, vx[1]>=0 && mapput(M360923, vx, T360923)); S360923 = Set(concat([[[u, vx[2]-vx[1]] | u<-[vx[1]-1..vx[1]+1], !mapisdefined(M360923, [u, vx[2]-vx[1]])] | vx <- S360923, vx[2]>=vx[1]])); T360923 += 1); T360923)} \\ M. F. Hasler, Feb 27 2023
T(i, j)=if(i, T(0, j+i*(i-1)\2)+i, j, sqrtint(4*j-3)+1) \\ Implementing Conjecture 2. - M. F. Hasler, Feb 27 2023
def A360923(v, x, A={0:0, 1:{(0, 0)}}):
if (v, x) in A: return A[v, x]
while (v, x) not in A[1]:
A.update((vx, A[0]) for vx in A[1] if vx[0]>=0); A[0] += 1
A[1] = {(u, x-v) for v, x in A[1] if x >= v
for u in range(v-1, v+2) if (u, x-v) not in A}
return A[0] # (End)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
