Hersrch is a search program for searching for open or closed Herschel tracks
in Conway's Game of Life.  An "open" track is one in which the start and end
spacetime locations for the Herschel signals are specified by a script, via
one or more -e switches (see "Script syntax" section at the end of this file.)
A "closed" track is one in which the start and end coordinates are identical,
producing an oscillator or gun of the specified period.

For definitions of any unfamiliar terms in this document, see Stephen Silver's
online Life Lexicon at http://www.argentum.freeserve.co.uk/lex.htm .


Switches
--------

    -p <period>

Specifies the period of the track. It affects both selected
components (their compression must support the selected period) and the track
length (it must be a multiple of the specified period, if the -d switch is 
not used) If this switch is not present and the -o switch is present, Hersrch 
produces a test pattern containing all component variant pairs and all 
impossible component sequences.

    -c <compression>

Specifies the compression for which the track may be used. If not specified,
the period value is used.
  
    -d <dx> <dy> <dt> <dir>

Specifies the ending point of the track and the direction of the end. 
By default, program searches for closed tracks but using this switch, a search
for open tracks or for closed tracks using unusual component is also possible.
DX and DY are numbers specifying the track endpoint - DY is in the Life32
polarity, i.e. it grows down. DT specifies the temporary offset added to the
track - for instance, if you search for a closed track using an unusual
component that passes a herschel in 1000 steps, put -1000 as DT. If you
search for a track that is exactly 500 generations long, put 500 as DT and 500
for the -u parameter (see below). If you don't use the -u parameter, the result 
length can be 500+n.<period>.
DIR means the ending direction of the herschel. The following values are
possible (case sensitive):
F Fx B Bx L Lx R Rx

    -e <script>

Enables extended search target specification. The script is read and
interpreted to create a number of targets. See the script syntax section.
If -e switch is used, implicit targets (from -p and -d switches) are not
created. The -e switch can be used multiple times in one hersrch run if a 
single script is not sufficient to define all targets.

    -t <treesize>

Specifies the Aho/Corasick tree size in kilobytes. The tree helps the program
to avoid non-working component sequences during the track construction instead
of during the track check. Default value is 1000, maximum value is 100000. 
Tree construction takes time independently on the search so use with care.

    -m

Allows Hersrch to use lots of memory to gain search speed. If this switch is 
used, Hersrch creates lookup tables for variant collisions, creates a search 
map containing all reachable states and uses a different search algorithm, 
which makes use of the map. The memory usage varies and depends on settings, 
generally it is about 130 MB but can go over 300 MB. The memory usage depends
on number of variants selected for search, maximum DT searched and marginally
also on number of targets. I tried to make the memory usage as swap-friendly 
as possible but I didn't really tested it when swapping occured.

    -l <minlength>

Specifies the minimum track length in generations. If not specified, any track
length above zero is searched.

    -u <maxlength>

Specifies the maximum track length in generations. Only track lengths equal to
a period multiple smaller or equal to this number are searched. Default value
is 1500 generations.

    -x <maxcells>

Specifies maximum track bounding rectangle size. Any tracks greater than this
value are not reported as solutions. The track size is calculated from pure
components, without eaters required to suppress herschel natural gliders.
If not specified, tracks of any size are reported as solutions.

    -n <maxresults>

Specifies maximum number of results in rle file.
If the -s switch is present, all results are calculated and only the first 
(smallest) n are written to the rle file (all are written to log).
If the -s switch is not present, the search is stopped after first n results.

    -f <logfile>

Specifies the log file. All found tracks are reported to this file including the
components they contain (in right order) and size. If not specified, the output
is only done on screen.

    -o <rlefile>

Specifies the filename where the constructed tracks are saved in rle format.
It produces a slightly incorrect rle format - the x= and y= tags don't show the
actual result size.
If not specified, rle output is not written anywhere.

    -s

Specifies that the rle file is sorted by the track size.
If this switch is not present, each result is written to the rle file as soon
as it is found.
If this switch is present, results are stored in memory and dumped to the rle
file in sorted order after the search finishes

    -i <ignore>

Allows to skip a number of component sets. This way the search can be
interrupted and restored later given the component definitions and search
parameters didn't change. On interrupt, the number of the interrupted set
is written to the logfile. Setting the -i parameter one number lower than
the reported number allows to continue the search almost exactly from the 
point where it was interrupted.


Script syntax
-------------

This section describes the syntax used for the -e switch.
First of all, there should be no spaces in the script. Spaces are included
in the following syntax definitions for readability only.

The script consists of two parts - variables definition and target definition

<script> ::= <var_def><target_def>

Variable definition:
There are 26 variables available for use named A through Z. Any variable can be
used as a constant or as a cycle. A cycle variable has two values defined
instead of one and during the script interpretation it gets each value in the
defined interval. This allows creating more than one target using the script
- each variable value creates a new target. If there are more than one variable
defined as cycle, all combinations are generated.

<var_def> ::= '(' <var_def_list> ')'

<var_def_list> ::= <single_var_def> { ',' <var_def_list> }

<single_var_def> ::= <var_name> '=' <expression> { '..' <expression> }

<var_name> ::= 'A' | 'B' | ... | 'Z'

Note that variable name parser is not case sensitive so you can use 'A' or 'a'
for the same variable. Some variables come predefined:

P = value of -p switch
C = value of -c switch
U = value of -u switch
L = value of -l switch
X, Y, T = values acquired from -d switch

These values are defined only if appropriate switch precedes the -e switch. 
All other variables are set to zero initially.
Even predefined variables can be used for other purposes, i.e. as a (different)
constant or a cycle variable.

In expressions, only integer values and results are supported. The following
binary operations are supported:
+ ... addition
- ... subtraction
* ... multiplication
/ ... division
% ... modulus
@ ... tweaked modulus (result of A @ B is always between 0 and B)
Unary minus is also supported.
Binary operations use usual precedence.

<expression> ::= <term> { '+' <expression> } | <term> '-' <expression>

<term> ::= <member> { '*' <term> } | <member> '/' <term> | <member> '%' <term> 
         | <member> '@' <term> 

<member> ::= '(' <expression> ')' | '-' <member> | <var_name> | <number>

<number> ::= non-negative integer number, do I need to draw it? ;-)

Note: during variable definition, only previously defined variables are set to
values defined. Cycle variables are set to their lower bound (not the first or
second expression but the lower of them).

Target definition can be one-point or two-point. If two-point definition is
used, the search is done from the first point to the second point. If one-point
definition is used, it defines the ending position and a kanonical herschel 
origin (F0[0,0]) is used as start point. Note that all two-point definitions
are internally converted to targets starting at canonical origin.

<target_def> ::= <point_def> { '..' <point_def> }

<point_def> ::= <direction> <delta-t> '[' <delta-x> ',' <delta-y> ']'

<delta-t> ::= <expression>

<delta-x> ::= <expression>

<delta-y> ::= <expression>

<direction> ::= 'F' | 'Fx' | 'L' | 'Lx' | 'R' | 'Rx' | 'B' | 'Bx'

Note that unlike variable parser, direction parser is case sensitive.

Example script follows:

(t=0..u/p,r=0..100,s=-50..50)R(-4*r)[-9+r,157+r]..F(5+p*t+4*s)[-95-s,60-s]

There are three cycle variables: r, s, and t, and predefined constants
u and p are used. The target is defined as two-point, starting in direction R 
and ending in direction F. The parentheses after directions are used to improve
readability, they are not required.

See sample1var.bat and sample2var.bat for complete examples of search parameters
that allow one and two degrees of freedom, respectively.


Additional note
---------------

The application traps SIGINT so a signal interrupt (usually Ctrl+C) can be sent
to application to stop it working. It saves all results and closes output files
before finishing. The signal doesn't stop preparation steps such as tree 
construction - use SIGBRK (Ctrl+Break) instead.

