# Bucket expression arithmetic

Updated for ver. 2.006. 2021-03-11

This document describes in detail the syntax and semantics of expressions used in determining the set of buckets into which a piece can be moved. These expressions appear as the last field of each "atom" in rule sets.

## Set-based evaluation

Whenever a given "atom" of a rule matches the position, shape, and color of a piece which the player attempts to move, the game engine evaluates the expression in the "bucket" field of the atom, obtaining the list of buckets into which this piece can be moved. The move is allowed only if the destination bucket chosen by the player is among the buckets on this list.

The expression in the bucket list is always evaluated to a set. It can be an empty set (which means that the piece cannot be moved), a set with one element (i.e. there is only one possible destination), or a set with several elements.

## Syntax

Formally, the syntax of the expression in the bucket field can be described by the following grammar:

- Any expression:
  E ::= E5
- A logical expression can be composed of 2 additive expressions:
  E5 ::= E4 | E4`==` E4
- An additive expression can be composed of any number of multiplicative expressions:
  E4 ::= E3 | E4 additiveOp E3
- additiveOp ::= `+` | `-`
- A multiplicative expression can be composed of any number of elementary expressions:
  E3 ::= E2 | E3 multOp E2
- multOp ::= `*` | `/` | `%`
- A unary expression consists of a unary operator (of which we have only one, the negation) preceding an elementary expression or a unary expression:
  E2 ::= E1 | unaryOp E2
- unaryOp ::= `!`
- An elementary expression is an ID, a Number, a parenthesized expression, or a bracket list:
  E1 ::= ID | Number | `[`E5 {, E5}+ `]` | `(`E5`)`
- An ID is one of the 5 predefined variable names (case-sensitive):
  ID ::= `p` |`pc` |`ps` |`Nearby` |`Remotest`
- A Number is a non-negative integer number, written as a sequnce of decimal digits:
  Number ::= digit+
- digit := 0|1|2|3|4|5|6|7|8|9

The table above also shows the precedence of operators (i.e. the order of execution): operators composing any E1-type expressions have the highest precedence, following by those composing E2-type expressions, etc.

As in most languages, additive and multiplicative expressions are evaluated from the left to the right, i.e. `p-pc+ps-3` is the same as `(((p-pc)+ps)-3)`

## Semantics

The arithmetic is performed on sets, but, as long as all sets involved have exactly one value, the process looks entirely like the evaluation of an expression in a language such as Java or C++, with an exception for the equality and negation operations (discussed below).

- A number (a numerical constant) represents a set of one value.
- An ID may be evaluated to an empty set (e.g. for `p`, `pc`, or `ps` early in the episode), a set of one value (usually), or (potentially, in the future) to a set of several values (e.g. `Nearby` or `Remotest` for some cells on an odd-sized board)
- A parenthesized expression evaluates to whatever the expression inside the parentheses evaluates; the parentheses simply serve to control the order of operations.
- A bracket list is evaluated to the union of the sets to which the elements are evaluated. E.g. `[[0, 2], [2, 3], 0]` evaluates to `[0, 2, 3`.
- An additive or multiplicative operation on set-valued arguments produces a cross-product. E.g. S1`+`S2 produces a set that includes every value x1`+`x2 with an x1 in S1 and x2 in S21. For example, [1,2,10]*[5,10] = [5,10,20,50,100]; [0,1,2]+[0] = [0,1,2]; [0,1,2]+[] = [].
- The division (/) and the remainder operation (%) are performed like integer operatins in Java or C, with rounding toward zero. For example, [2,5,10]/[3] = [0,1,3]; [-4,4]%[3]=[-1,1].
- A division by zero (or remainder from division by zero) produces no result; in other words, no expression for the pair involved is included into the result set. For example, [7]/[0,2] = [3]; [0]/[0]=[].
- Unlike C++ or Java, the equality operation S1`==`S2 is also computed as a crossproduct, producing an empty set if S1 has not a single element that's equal to an element from S2, or a set with one element, [1], if S1 has an element that's equal to an element from S2. For example, [0,2]==[1,3] produces [], while [0,2,3]==[3] produces [1]. Somewhat counterintuitively, []==[] produces [] as well.
- The negation operator works as follows: if E is an empty set, `!`E evaluates to [1]; otherwise, to [].

As in most programming languages, one can insert additional (unnecessary) parentheses around high-precedence subexpressions without affecting their meaning. So, for example, !!p has the same meaning as (!(!(p))), and 2*3-1, as ((2*3)-1).

## Final modulo-4 processing

Since buckets are numbered 0 thru 3, a bucket number outside of this range makes no sense. Therefore, after the bucket expression is computed, every memeber of the resulting set is translated to the [0..3] range by a modulo-4 transformation, i.e. n := ((n%4)+4)%4. (It is not simply (n%4) because the % operation in Java or C, or in our language, produces a negative result on a negative argument; e.g. (-5)%4=(-1)). Therefore, it is safely, for example, to write simply `p+1`, instead of `(p+1)%4`, to mean "the next bucket (in the clockwise order) after the bucket into which accepted the previous moved piece".

## Examples

Top left bucket | 0
Top left bucket or top right bucket | [0,1]
The same bucket into which the last piece of the same color was put, or the opposite bucket | [pc,pc+2]
Any bucket along the same horizontal edge of the board as the previously used bucket. (That is, if the previous bucket was at the top edge of the board (0 or 1), then you can use 0 or 1 now; if the previous bucket was at the bottom edge of the board (2 or 3), then you can use 2 or 3 now). | [(p/2)*2, (p/2)*2+1]
Ditto | [(p==[0,1])*[0,1], (p==[2,3])*[2,3]]
If pc is defined (i.e. if any piece of this color has been put into a bucket already), then [0,1]; otherwise, empty set []. | (pc==[0,1,2,3])*[0,1]
Ditto | !!pc*[0,1]
If p is defined (i.e. at least one piece has been picked), you can pick any pieces in the quadrant of the board that's closest to the most recently used bucket. Otherwise (i.e. if it's the first move of the game), no piece can be picked. | (p==Nearby)*Nearby
If p is defined, then empty set []; otherwise, [1] | !p
If p is defined, then [1]; otherwise, [] | !!p
Ditto | (p==[0,1,2,3])*1
If p is defined, you then p-1 (modulo 4); otherwise, [0,1,2,3]. In other words, if no piece has been put into a bucket yet, you can use any bucket; otherwise, you must use the bucket that's next in the counterclockwise order to the last bucket that was used. | [!p*[0,1,2,3], !!p*(p-1)]

## Rule set examples

### Example 1

    (1,*,*,*,[!p*[0,1,2,3], !!p*(p-1)])
    (*,*,*,*,(p==Nearby)*p)

- The first piece can be put into any bucket. (First line, where !p evaluates to [1]).
- After that, the second line becomes active; the player then must pick every piece in the quadrant of the board adjacent to the bucket that was used for the first piece, and put them into the same bucket.
- After that, the control reverts to the first line, where !!p evaluates to [1], which means that the player can put any piece and put it the bucket that is the next one, in counterclockwise order, to the first used bucket.
- Contol goes to the second line again; the player now must pick all pieces in the quadrant adjacent to the last-used bucket, and put them into that bucket. Etc.

## Try it!

You can test your arithmetic in this form: Expression entry form.

[Rule set syntax] [Main page]