Home > Steve > Puzzles > Teleports

# Teleports In A Linear Array

## A Recreational Mathematical Investigation 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.

#### After all that introduction, I now pose some of my questions:

1. Is there a formula or simple method to determine the largest required step length for an array of a given size?
2. Is the graph of (1) montonic?
3. How does one generate an optimal pattern?

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.

#### Maximum necessary journey lengths for optimally patterned telported linear arrays.

(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.
```

#### A Fuller list

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 "99 9 9" is unquestionably better than "99 9 7", the non-optimal entries have been removed. Where there is a pattern with more steps but with (many?) fewer teleports these have been retained - this latter group is not complete and may not be optimal within its number of steps.

The list is a text file, use your ``` back ``` button to return here.

#### Pattern merging

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`". Then add teleport "d" from sub-pattern "a" to "b", "`ad..ab.d.bc...c`". Add teleport "e" from sub-pattern "b" to "c", "`ad..abed.bc.e.c`". Add teleport "f" from sub-pattern "c" to "a", "`adf.abed.bcfe.c`". We now have an array of size ( N * 3 ) with maximum journey ( ( J * 2 ) + 1 ).

Note also that there are still three empty cells, so we can repeat the process to get an array of size ( N * 9 ) with maximum journey ( ( J * 4 ) + 3 ). And again: an array of size ( N * 27 ) with maximum journey ( ( J * 8 ) + 7 ). And yet again: an array of size ( N * 81 ) with maximum journey ( ( J * 16 ) + 15 ). Etc: an array of size ( N * 3x ) with maximum journey ( ( J * 2x ) + ( 2x - 1 ) )..

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.

#### Minimal journey lengths

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 2J+1 - 1 = 1 + 2 * ( 2J - 1 ) cells. Hence the maximum with 3 steps is an array of length 15. We can conclude that an array of 16 needs at least 4 steps.

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 1 + 3 * ( 2J - 1).

#### The following tables illustrate the journeys in the "P N J Pattern" table above justifying part of the above statements.

 ```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: . > >> >> 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: . > >> >> 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: . > >> >> >c 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: . > >> b< >b 03: . > >> b<< b< b 04: . > >> >> >>> 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: . > >> >>> b< >b 03: . > >> >>> b<< b< b 04: . > >> >>> >> >>> < >> >>> 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 >> >b< >b >b> 03: . > >> >>> b<< b< b b> 04: . > >> >>> c 05: . > >> c<< c< c 06: . > >> >> >>> 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 >> b>> >>c 03: . > >> >>> >c< >c 04: . > >> >>> < >> >>> >d< >d >> d< d d> 07: . > >> 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: . > >> >>> b<< b< b b> 03: . > >> >>> <c< >c 04: . > >> c<< c< c c> c>> >>d 05: . > >> >d< >d 06: . > >> >>> d<< d< d 07: . > >> >>> >> >>> < >> >>> 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>c a>f 02: . > >> >c< >c >c> 03: . > >> >>> >d< >d 04: . > >> d< d d> >e< >e 05: . > >> e>> 06: . > >> >>> f< >f 07: . > >> >>> f<< f< f 08: . > >> >>> >> >>> < >> >>> 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> af >>c 02: . > >> b<< b< b b> b>> >c< >c 03: . > >> >>> cd< >d c<< c< c 04: . > >> d<< d< d d> >e< >e >> e>> 06: . > >> >>> a>b f >f> 07: . > >> >>> f<< f< f f> 08: . > >> >>> 09: . > >> >>> < >> >>> 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> af >>c 02: . > >> >>> b<< b< b b> b>> >c< >c 03: . > >> >>> <d< >d c<< c< c 04: . > >> >>> d<< d< d d> d>> >>e >> >>> >e< >e >e> < >> >>> < e>> 07: . > >> >>> a>b f >f> 08: . > >> >>> f<< f< f f> 09: . > >> >>> 10: . > >> >>> < >> >>> 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: . > >> >>> >>>> > b<<< b<< b< b b> 03: . > >> >>> >>>> < >>c< >>c 04: . > >> >>> >>>> <<c<< >c< >c >c> < 05: . > >> >>> c<<< c<< c< c c> c>> c>>> >>>d 06: . > >> >>> > >>d< >>d 07: . > >> >>> < >d<< >d< >d 08: . > >> >>> >>>> d<<< d<< d< d 09: . > >> >>> >>>> >> >>> >>>> < >> >>> >>>> << >> >>> >>>> 13: . > >> >>> 14: . > >> 15: . > 16: . Max Length = 4 ```

Home > Steve > Puzzles > Teleports
Last updated 2004-08-10