Home > Steve > Puzzles > Teleports
This file relates to a mathematical topic I have been investigating purely because I am curious about it. I do not know if it has already been analysed - I expect it has - but I have no idea how to find this out.
Originally I wanted to analyse a 2-dimensional hexagonal grid. That seemed to hard to analyse, so I am starting by attempting a similar analysis on a 1-dimensional grid.
A limited discussion of this topic has occurred on Compuserve's Science and Maths Forum.
My rate of progress on this topic is limited as I spend very little time on it!
Imagine a linear array of cells, say 3 (call the cells '1', '2' and '3'). If it takes one "step" to move from one cell to a neighbouring cell, the longest journey is from '1' to '3', a distance of 2 steps.
Additionally we add teleport machines which also take one "step" to function. They are constrained by only allowing one teleport machine per cell to a fixed destination cell, and that destination cell can only teleport back to its matching cell. I name teleport machine pairs with letters 'a', 'b' and use '-' if no teleport is installed in a cell.
Given that, a three cell array can now be traversed in only one step
if the array is arranged as:
1 2 3
a - a
The journey from cell '1' to cell '3' being by teleport.
I have a program which works out a shortest route between all cells for a given pattern. Its output for the three cell array just described is:
Dst> 01 02 03
vSrc a - a
------------
01: . > a
02: . >
03: .
Max Length = 1
Where the three cells are '01', '02' and '03'.
Where '01' has half of teleport 'a', '02' has no teleport and '03' has
the other half of teleport 'a'.
To get from '01' to '01' needs no steps at all (shown by a ".").
To get from '01' to '02' needs 1 step right (shown by a ">").
To get from '01' to '03' needs 1 teleport step using teleport "a" (shown
by "a").
Only half of the grid is shown as it is totally reversible.
Here is a bigger pattern:
Dst> 01 02 03 04 05 06 07
vSrc a b c - a c b
-----------------------------------
01: . > >> a< a a> >b
02: . > >> <a b< b
03: . > c< c c>
04: . > >> >>>
05: . > >>
06: . >
07: .
Max Length = 3
Which shows you can get from cell 2 to cell 5 in 2 steps (take one
step left then teleport).
With this pattern, the maximum required length is from cell 4 to cell 7
which requires 3 steps (right, right, right is one option, there may be
others).
If any reader would like a copy of the QBASIC program which does this, email me, webmaster@stocton.org.
Which leads on to the question "What is optimal?"
Within any patterns of a particular size and traversable with a particular number of steps, optimal patterns are those which use fewest teleports. This leaves the most options free for later expansion of the pattern.
One answer is that an optimal pattern is one which traverses the array in the minimum number of steps and within that number of steps has the minimum number of teleports.
There may be other answers with non-minimal step numbers if the number of teleports used is fewer.
This report summarises what I presentably know at present.
(IE every journey between every pair of cells can be achieved in less than or equal to this journey length. Some journeys are listed after the table.)
In this table: N is array length; J is maximum required journey length; Pattern is an "alphalist" being one example pattern which achieves J; P is either "y" if J is proven or "n" if it is an example but not proven.
P N J Pattern
~~~~~~~~~~~~~~~~~~~
y 1 0 . Self evident. 0 is sufficient to stay still.
y 2 1 .. Self evident. 1 is sufficient and necessary.
y 3 1 a.a Fully evaluated. 1 is sufficient and necessary.
y 4 2 a..a All journeys can be done in at most 2 steps.
Cell 1 has three required destination cells
(2,3,4) and only two single step moves (Right
or Teleport) therefore at least 2 steps must be
necessary.
y 5 2 a...a As N=4
y 6 2 ab..ab As N=4
y 7 2 ab.cacb As N=4
y 8 3 a.b..a.b With only 2 steps, Cell 1 can move to 1,2,3 by
steps; it can also "step,teleport" for 1 more
destination; and "teleport,step" for 3 more.
Grand total of 7 cells. Therefore 8 cells
require at least 3 steps.
The example given here is a guess which worked,
it is presumed to be not optimal (whatever
that means).
y 9 3 a.b...a.b As N=8
y 10 3 a.b.ca..bc As N=8
y 11 3 ab.cad.b.dc As N=8
y 12 3 ab.c.da.c.bd As N=8
y 13 3 abcdeafdb.ecf As N=8
y 14 3 abcdeaf.db.efc As N=8
y 15 3 abcd.eaf.db.efc As N=8
y 16 4 ab..c..da..c..bd See Minimal journey lengths below.
which proves that a 16 cell linear array
requires at least 4 steps.
Another program is able to generate optimal patterns, by
scanning through all non-duplicate patterns progressinvely minimising
the number of steps and the number of teleports used. The output has
then been hand edited to remove the 'progressive' patterns that were
non-minimal. Each entry lists the array size (pattern length), number of
steps required and number of non-teleport cells (rather than number of
teleport cells). Where there is no debate over optimal-ness (eg
The list is a text file, use your back
button to return here.
Imagine an array of size N which can be traversed in a journey of J steps which has E cells without teleports. Then several of these array can be joined together using the empty cells to teleports between the sub-patterns.
For example "a...a" has three empty cells and can be traversed in 2 steps.
Concatenate three copies of this to form
a...ab...bc...c".ad..ab.d.bc...c".ad..abed.bc.e.c".adf.abed.bcfe.c".
Note also that there are still three empty cells, so we can repeat
the process to get an array of size
Whilst merging is an easy way of getting a reasonable pattern for a bigger array, it is unlikely to be optimal. In the example given, N=5 with J=2 results in N=15 with J=5. We know we can do N=15 with J=3.
Any step can be one of three types, left, right or jump. However one of those options will take you back to where you came from, so there can be at most two steps from a cell to new cells.
On a finite or semi-infinite array, the leftmost cell is visited with no steps. One step visits (at most) two new cells (right and jump), total 1 + 2. Each of these new cells visit (at most) two new cells, total 1 + 2 + 22. Etc.
Thus in J steps we can visit at most
Note that for an infinite or circular array, the very first step may
visit 3 new cells, so that the maximum number of cells visitable in J
steps is
Line Length = 1 Line =. Dst> 01 vSrc . ---- 01: . Max Length = 0 |
Line Length = 2 Line =.. Dst> 01 02 vSrc . . -------- 01: . > 02: . Max Length = 1 |
Line Length = 3 Line =a.a Dst> 01 02 03 vSrc a . a ------------ 01: . > a 02: . > 03: . Max Length = 1 |
Line Length = 4 Line =a..a Dst> 01 02 03 04 vSrc a . . a ---------------- 01: . > a< a 02: . > >> 03: . > 04: . Max Length = 2 |
Line Length = 5 Line =a...a Dst> 01 02 03 04 05 vSrc a . . . a -------------------- 01: . > >> a< a 02: . > >> <a 03: . > >> 04: . > 05: . Max Length = 2 |
Line Length = 6 Line =ab..ab Dst> 01 02 03 04 05 06 vSrc a b . . a b ------------------------ 01: . > >> a< a a> 02: . > >> b< b 03: . > >> <b 04: . > >> 05: . > 06: . Max Length = 2 |
Line Length = 7 Line =ab.cacb Dst> 01 02 03 04 05 06 07 vSrc a b . c a c b ---------------------------- 01: . > >> a< a a> >b 02: . > >> <a b< b 03: . > >> >c <b 04: . > c c> 05: . > >> 06: . > 07: . Max Length = 2 |
Line Length = 8 Line =a.b..a.b Dst> 01 02 03 04 05 06 07 08 vSrc a . b . . a . b -------------------------------- 01: . > >> a<< a< a a> a>> 02: . > >> <a< <a >b< >b 03: . > >> b<< b< b 04: . > >> <b< <b 05: . > >> >>> 06: . > >> 07: . > 08: . Max Length = 3 |
Line Length = 9 Line =a.b...a.b Dst> 01 02 03 04 05 06 07 08 09 vSrc a . b . . . a . b ------------------------------------ 01: . > >> >>> a<< a< a a> a>> 02: . > >> >>> <a< <a >b< >b 03: . > >> >>> b<< b< b 04: . > >> >>> <b< <b 05: . > >> >>> <<b 06: . > >> >>> 07: . > >> 08: . > 09: . Max Length = 3 |
Line Length = 10 Line =a.b.ca..bc Dst> 01 02 03 04 05 06 07 08 09 10 vSrc a . b . c a . . b c ---------------------------------------- 01: . > >> a<< a< a a> a>> >>b a<c 02: . > >> <a< <a <a> >b< >b >b> 03: . > >> >>> b<< b< b b> 04: . > >> >>> <b< <b >c 05: . > >> c<< c< c 06: . > >> <c< <c 07: . > >> >>> 08: . > >> 09: . > 10: . Max Length = 3 |
Line Length = 11 Line =ab.cad.b.dc Dst> 01 02 03 04 05 06 07 08 09 10 11 vSrc a b . c a d . b . d c -------------------------------------------- 01: . > >> a< a a> >b< >b >b> a>d a<c 02: . > >> <a b<< b< b b> b>> >>c 03: . > >> >>> <b< <b <b> >c< >c 04: . > >> >>> <<b c<< c< c 05: . > >> >>> >d< >d <c 06: . > >> d< d d> 07: . > >> <d <d> 08: . > >> >>> 09: . > >> 10: . > 11: . Max Length = 3 |
Line Length = 12 Line =ab.c.da.c.bd Dst> 01 02 03 04 05 06 07 08 09 10 11 12 vSrc a b . c . d a . c . b d ------------------------------------------------ 01: . > >> >>> a<< a< a a> a>> >b< >b >b> 02: . > >> >>> <a< <a <a> b<< b< b b> 03: . > >> >>> <<a >c< >c <b< <b <b> 04: . > >> c<< c< c c> c>> >>d 05: . > >> <c< <c <c> >d< >d 06: . > >> >>> d<< d< d 07: . > >> >>> <d< <d 08: . > >> >>> <<d 09: . > >> >>> 10: . > >> 11: . > 12: . Max Length = 3 |
Line Length = 13 Line =abcdeafdb.ecf Dst> 01 02 03 04 05 06 07 08 09 10 11 12 13 vSrc a b c d e a f d b . e c f ---------------------------------------------------- 01: . > >> a<< a< a a> >b< >b >b> a<e >>c a>f 02: . > >> <a< <a b<< b< b b> >c< >c >c> 03: . > >> >>> >d< >d <b c<< c< c c> 04: . > >> d< d d> >e< >e <c <c> 05: . > >> <d e<< e< e e> e>> 06: . > >> >>> <e< <e >f< >f 07: . > >> >>> f<< f< f 08: . > >> >>> <f< <f 09: . > >> >>> <<f 10: . > >> >>> 11: . > >> 12: . > 13: . Max Length = 3 |
Line Length = 14 Line =abcdeaf.db.efc Dst> 01 02 03 04 05 06 07 08 09 10 11 12 13 14 vSrc a b c d e a f . d b . e f c -------------------------------------------------------- 01: . > >> a<< a< a a> a>> >b< >b >b> a<e a>f >>c 02: . > >> <a< <a <a> b<< b< b b> b>> >c< >c 03: . > >> >>> c<f >d< >d <b <b> c<< c< c 04: . > >> d<< d< d d> >e< >e <c< <c 05: . > >> <d< <d e<< e< e e> e>> 06: . > >> >>> a>b <e< <e >f >f> 07: . > >> >>> f<< f< f f> 08: . > >> >>> <f< <f <f> 09: . > >> >>> <<f d<c 10: . > >> >>> b>c 11: . > >> >>> 12: . > >> 13: . > 14: . Max Length = 3 |
Line Length = 15 Line =abcd.eaf.db.efc Dst> 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 vSrc a b c d . e a f . d b . e f c ------------------------------------------------------------ 01: . > >> >>> a<< a< a a> a>> >b< >b >b> a<e a>f >>c 02: . > >> >>> <a< <a <a> b<< b< b b> b>> >c< >c 03: . > >> >>> <<a c<f >d< >d <b <b> c<< c< c 04: . > >> >>> d<< d< d d> d>> >>e <c< <c 05: . > >> >>> <d< <d <d> >e< >e >e> <<c 06: . > >> >>> <<d e<< e< e e> e>> 07: . > >> >>> a>b <e< <e >f >f> 08: . > >> >>> f<< f< f f> 09: . > >> >>> <f< <f <f> 10: . > >> >>> <<f d<c 11: . > >> >>> b>c 12: . > >> >>> 13: . > >> 14: . > 15: . Max Length = 3 |
Line Length = 16 Line =ab..c..da..c..bd Dst> 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 vSrc a b . . c . . d a . . c . . b d -------------------------------------------------------------------------------- 01: . > >> >>> >>>> a<<< a<< a< a a> a>> a>>> >b<< >b< >b >b> 02: . > >> >>> >>>> <a<< <a< <a <a> <a>> b<<< b<< b< b b> 03: . > >> >>> >>>> <<a< <<a <<a> >>c< >>c <b<< <b< <b <b> 04: . > >> >>> >>>> <<<a >c<< >c< >c >c> <<b< <<b <<b> 05: . > >> >>> c<<< c<< c< c c> c>> c>>> >>>d 06: . > >> >>> <c<< <c< <c <c> <c>> >>d< >>d 07: . > >> >>> <<c< <<c <<c> >d<< >d< >d 08: . > >> >>> >>>> d<<< d<< d< d 09: . > >> >>> >>>> <d<< <d< <d 10: . > >> >>> >>>> <<d< <<d 11: . > >> >>> >>>> <<<d 12: . > >> >>> >>>> 13: . > >> >>> 14: . > >> 15: . > 16: . Max Length = 4 |
Home >
Steve >
Puzzles >
Teleports
Last updated 2004-08-10
This page is part of http://www.stocton.org/
Email: webmaster@stocton.org