2012-09-04

Yeah, yeah.

It’s finally time to tackle diagonals. And horizontal/vertical paths as well, but I’m hoping those are easy, right?

So a reminder: our objective is to find a list of squares between our source and destination, so that a yet-to-be-defined part of our code can check for obstacles.

This could be done purely with addition and subtraction: if I take the “source” square to be the origin, and the target to be in one of the 4 quadrants, I could figure out whether I need to add or subtract from each of my tuple values and proceed until I hit the target.

But let’s be brave and dive headlong into the kind of math I excelled at 30 years ago (le sigh).

`y = mx + b`

So, first, let’s find `b`

:

```
y = mx + b
y - mx = b
```

Tough math there. Anyway:

```
bfinder(M, {X, Y}) ->
Y - (M * X).
```

Now for the fun part. I want my `next_point`

function to be tail recursive, so we’ll need to include an accumulator for the resulting list of intermediate values. Thus, our arguments to `next_point`

:

- M, the slope
- B, the y-intercept (right? I’m going out on a limb by not double-checking that basic factoid)
- Current square in tuple form
- Destination square in tuple form
- List accumulator

The base case for our recursion occurs when current and target squares are the same, so:

```
next_point(_, _, Final, Final, Accum) ->
Accum;
```

Now I repeat the same pattern match with different guards because I don’t want to make this any uglier than it has to be:

```
next_point(M, B, {X1, _Y}, {Xf, Yf}, Accum) when Xf < X1
next_point(M, B, {X1, _Y}, {Xf, Yf}, Accum) when Xf > X1
```

We’ll either increment or decrement `X1`

to find the next Y value depending on whether the target square is to the right or to the left of the current square.

I suspect this will also be a handy guard concept for vertical (`Xf =:= X1`

) or horizontal (`Yf =:= Y1`

) paths.

```
next_point(_, _, Final, Final, Accum) ->
Accum;
next_point(M, B, {X1, _Y}, {Xf, Yf}, Accum) when Xf < X1 ->
NewX = X1 - 1,
Loc = { NewX, M * NewX + B },
next_point(M, B, Loc, {Xf, Yf}, [Loc|Accum]);
next_point(M, B, {X1, _Y}, {Xf, Yf}, Accum) when Xf > X1 ->
NewX = X1 + 1,
Loc = { NewX, M * NewX + B },
next_point(M, B, Loc, {Xf, Yf}, [Loc|Accum]).
```

So if we wish to find all the squares starting at `{ 3, 4 }`

on the path to `{ 0, 1 }`

:

```
4> piece:bfinder(-1, { 3, 4 }).
7
5> piece:next_point(1, piece:bfinder(1, { 3, 4 }), { 3, 4 }, { 0, 1 }, []).
[{0,1},{1,2},{2,3}]
```

So, the squares between `{ 3, 4 }`

and `{ 0, 1 }`

are in reverse order, which doesn’t matter (and is expected for tail recursion). However:

`{ 0, 1 }`

, the destination square, shouldn’t show up in the results (per my half-developed spec).- We still have to manually specify the slope.

The first problem turns out to be very easy to rectify *because* the list is reversed:

```
next_point(_, _, Final, Final, [_H|T]) ->
T;
```

So now, the question of how best to handle the slope. One requirement: we need to make sure the slope is always -1 or +1 for diagonals. Also, don’t waste time recalculating `M`

and `B`

for each recursive call.

This leads me to rename `next_point/5`

to `diag_next_point/5`

and introduce `next_point/2`

as the standard entry point. Renaming it isn’t required by the language, but it allows me to make sure that the slope sent to `diag_next_point/5`

is always 1 or -1 by introducing a pattern match purely for throwing exceptions.

New code:

```
next_point(Final, Final) ->
[];
next_point({X1, Y1}, {Xf, Yf}) when X1 /= Xf, Y1 /= Yf ->
M = (Yf - Y1) div (Xf - X1),
B = bfinder(M, {X1, Y1}),
diag_next_point(M, B, {X1, Y1}, {Xf, Yf}, []).
diag_next_point(M, _B, Start, End, _) when abs(M) =/= 1 ->
throw({invalid_diagonal, Start, End});
diag_next_point(_, _, Final, Final, [_H|T]) ->
T;
diag_next_point(M, B, {X1, _Y}, {Xf, Yf}, Accum) when Xf < X1 ->
NewX = X1 - 1,
Loc = { NewX, M * NewX + B },
diag_next_point(M, B, Loc, {Xf, Yf}, [Loc|Accum]);
diag_next_point(M, B, {X1, _Y}, {Xf, Yf}, Accum) when Xf > X1 ->
NewX = X1 + 1,
Loc = { NewX, M * NewX + B },
diag_next_point(M, B, Loc, {Xf, Yf}, [Loc|Accum]).
```

I’m going to remove `bfinder/2`

and place the calculation inline:

```
next_point(Final, Final) ->
[];
next_point({X1, Y1}, {Xf, Yf}) when X1 /= Xf, Y1 /= Yf ->
M = (Yf - Y1) div (Xf - X1),
B = Y1 - (M * X1),
diag_next_point(M, B, {X1, Y1}, {Xf, Yf}, []).
```

And let’s test some valid and invalid invocations:

```
24> piece:next_point({ 3, 4 }, { 5, 5 }).
** exception throw: {invalid_diagonal,{3,4},{5,5}}
in function piece:diag_next_point/5 (/Users/jdaily/github/local/Erlang-Chessboard/piece.erl, line 39)
```

This makes sense: `{3, 4}`

and `{5, 5}`

are not on the same diagonal.

```
25> piece:next_point({ 3, 4 }, { 5, 6}).
[{4,5}]
```

`{3, 4}`

and `{5, 6}`

definitely are on the same diagonal, with `{4, 5}`

betwixt.

```
26> piece:next_point({ 3, 4 }, { 5, 7}).
** exception error: no function clause matching
piece:diag_next_point(1,1,{5,6},{5,7},[{5,6},{4,5}]) (/Users/jdaily/github/local/Erlang-Chessboard/piece.erl, line 38)
```

This is an interesting error condition which I think tells me that my slope check is not working. More in a moment.

```
27> piece:next_point({ 3, 4 }, { 3, 5}).
** exception error: no function clause matching piece:next_point({3,4},{3,5}) (/Users/jdaily/github/local/Erlang-Chessboard/piece.erl, line 31)
```

This is expected: my guards in `next_point/2`

ensure that the two X values and two Y values are never the same, so we’re always talking about diagonals. Horizontal and vertical, coming soon.

This is a bit of a mess. Let’s walk through the problem.

```
26> piece:next_point({ 3, 4 }, { 5, 7}).
** exception error: no function clause matching
piece:diag_next_point(1,1,{5,6},{5,7},[{5,6},{4,5}]) (/Users/jdaily/github/local/Erlang-Chessboard/piece.erl, line 38)
```

Notice that `diag_next_point`

is being called with a slope of 1, even though it’s technically a slope of 1.5 (ΔY / ΔX => 3 / 2 => 1.5).

That’s because I deliberately chose to use `(Yf - Y1) div (Xf - X1)`

(**div** means integer division) instead of `(Yf - Y1) / (Xf - X1)`

(floating point division) because I wanted `M`

to always be an integer ±1.

Does it matter? I’m still getting an exception because the two points aren’t on the same line, but I don’t want to risk an infinite loop, and more generally I want the code to be correct.

However, introducing floating point numbers when I only want integers makes for hairier code if I’m not careful. Here’s an implementation that behaves as desired, but I’m not at all happy with:

```
next_point(Final, Final) ->
[];
next_point({X1, Y1}, {Xf, Yf}) when X1 /= Xf, Y1 /= Yf ->
M = (Yf - Y1) / (Xf - X1),
B = Y1 - (M * X1),
diag_next_point(M, trunc(B), {X1, Y1}, {Xf, Yf}, []).
diag_next_point(M, _B, Start, End, _) when abs(M) =/= 1.0 ->
throw({invalid_diagonal, Start, End});
diag_next_point(_, _, Final, Final, [_H|T]) ->
T;
diag_next_point(M, B, {X1, _Y}, {Xf, Yf}, Accum) when Xf < X1 ->
NewX = X1 - 1,
Loc = { NewX, trunc(M) * NewX + B },
diag_next_point(M, B, Loc, {Xf, Yf}, [Loc|Accum]);
diag_next_point(M, B, {X1, _Y}, {Xf, Yf}, Accum) when Xf > X1 ->
NewX = X1 + 1,
Loc = { NewX, trunc(M) * NewX + B },
diag_next_point(M, B, Loc, {Xf, Yf}, [Loc|Accum]).
```

Notice that I’m truncating `B`

at the entry point to `diag_next_point/5`

because I made it a floating point number when I allowed `M`

to be a float.

But I can’t truncate `M`

yet because I need to check to make certain that it is exactly ± 1.0 in `diag_next_point/5`

.

Yet once I’ve passed that initial sanity check, I need to make sure to convert it back to the integer ± 1 when calculating each square, so I keep invoking `trunc`

.

Furthermore, the two guards below are not equivalent:

```
diag_next_point(M, _B, Start, End, _) when abs(M) =/= 1.0
diag_next_point(M, _B, Start, End, _) when not abs(M) =:= 1.0
```

And I’m not sure why. Only the first does what I need.

What a mess.

Anyone who actually knows Erlang, please feel free to let me know what I **should** be doing here, but what I **am** doing is this:

```
next_point(Final, Final) ->
[];
next_point({X1, Y1}, {Xf, Yf}) when X1 /= Xf, Y1 /= Yf ->
M = (Yf - Y1) / (Xf - X1),
IntM = validate_slope(M),
B = Y1 - (IntM * X1),
diag_next_point(IntM, trunc(B), {X1, Y1}, {Xf, Yf}, []).
validate_slope(1.0) ->
1;
validate_slope(-1.0) ->
-1;
validate_slope(M) ->
throw({invalid_slope, M}).
diag_next_point(_, _, Final, Final, [_H|T]) ->
T;
diag_next_point(M, B, {X1, _Y}, {Xf, Yf}, Accum) when Xf < X1 ->
NewX = X1 - 1,
Loc = { NewX, M * NewX + B },
diag_next_point(M, B, Loc, {Xf, Yf}, [Loc|Accum]);
diag_next_point(M, B, {X1, _Y}, {Xf, Yf}, Accum) when Xf > X1 ->
NewX = X1 + 1,
Loc = { NewX, M * NewX + B },
diag_next_point(M, B, Loc, {Xf, Yf}, [Loc|Accum]).
```

And to verify…

```
46> piece:next_point({ 3, 4 }, { 5, 7}).
** exception throw: {invalid_slope,1.5}
in function piece:validate_slope/1 (/Users/jdaily/github/local/Erlang-Chessboard/piece.erl, line 44)
in call from piece:next_point/2 (/Users/jdaily/github/local/Erlang-Chessboard/piece.erl, line 35)
47> piece:next_point({ 3, 4 }, { 5, 6}).
[{4,5}]
48> piece:next_point({ 3, 4 }, { 9, 10}).
[{8,9},{7,8},{6,7},{5,6},{4,5}]
49> piece:next_point({ 3, 4 }, { 9, 11}).
** exception throw: {invalid_slope,1.1666666666666667}
in function piece:validate_slope/1 (/Users/jdaily/github/local/Erlang-Chessboard/piece.erl, line 44)
in call from piece:next_point/2 (/Users/jdaily/github/local/Erlang-Chessboard/piece.erl, line 35)
```

`validate_slope/1`

definitely feels like a hack, but it makes for very easy to read code.

So now we have a problem. If I define bishop move functions that dive straight into `next_point/2`

, I’m going to throw an exception if the slope is invalid. That by itself wouldn’t be awful, except that my standard response to all invalid move requests is to send back `{no,Loc}`

where `Loc`

is the origin square.

I could catch the exception in the bishop move function, but remember that I hope to move the move functions out of this module eventually, and I really shouldn’t have to worry about that `invalid_slope`

exception.

Did I waste all that error checking? I don’t think so; I think it’s a good idea to have it in any event. However, I’m going to introduce a slope calculator to use from all of our long-range pieces.

```
calculate_slope(Loc, Loc) ->
none;
calculate_slope({X1, Y1}, {X1, Yf}) ->
infinity;
calculate_slope({X1, Y1}, {Xf, Y1}) ->
0.0;
calculate_slope({X1, Y1}, {Xf, Yf}) ->
(Yf - Y1) / (Xf - X1).
```

Shell verification:

```
56> piece:calculate_slope( {3, 4}, {3, 4} ).
none
57> piece:calculate_slope( {3, 4}, {4, 4} ).
0.0
58> piece:calculate_slope( {3, 4}, {4, 5} ).
1.0
59> piece:calculate_slope( {3, 4}, {4, 6} ).
2.0
60> piece:calculate_slope( {3, 4}, {5, 6} ).
1.0
61> piece:calculate_slope( {3, 4}, {5, 7} ).
1.5
62> piece:calculate_slope( {3, 4}, {3, 7} ).
infinity
```

Since I can’t use a function I define (like `calculate_slope/2`

) in a guard statement, I’m finally going to have to move beyond my reliance on pattern matching and use the Erlang `case`

statement. (`if`

statements also use guards, so `case`

is my only option.)

Here’s my `bishopmove`

anonymous function:^{1}

```
fun(Start, End, _) ->
case piece:calculate_slope(Start, End) of
1.0 ->
{ End, next_point(Start, End) };
-1.0 ->
{ End, next_point(Start, End) };
_ ->
{ Start, [] }
end
end
```

And, finally:

```
80> [ B ] = [ X || {bishopmove, X} <- piece:movefuns() ].
[#Fun<piece.4.116427261>]
81> Bishop = spawn(piece, piece_loop, [ bishop, B, B ]).
<0.259.0>
82> Bishop ! { self(), move, {2, 3}, {3, 4}, white }.
{<0.231.0>,move,{2,3},{3,4},white}
83> flush().
Shell got {yes,bishop,{2,3},{3,4},[]}
ok
84> Bishop ! { self(), move, {2, 3}, {4, 4}, white }.
{<0.231.0>,move,{2,3},{4,4},white}
85> flush().
Shell got {no,bishop,{2,3},{4,4},[]}
ok
86> Bishop ! { self(), move, {2, 3}, {4, 5}, white }.
{<0.231.0>,move,{2,3},{4,5},white}
87> flush().
Shell got {yes,bishop,{2,3},{4,5},[{3,4}]}
ok
88> Bishop ! { self(), move, {9, 4}, {5, 0}, black }.
{<0.231.0>,move,{9,4},{5,0},black}
89> flush().
Shell got {yes,bishop,{9,4},{5,0},[{6,1},{7,2},{8,3}]}
ok
```

And there was much rejoicing.

I knew I was afraid of diagonals.

We’re on a roll, so let’s keep at it.

Following the same basic structure^{2} as we’ve already seen:

```
next_point(Final, Final) ->
[];
next_point({X1, Y1}, {Xf, Yf}) when X1 /= Xf, Y1 /= Yf ->
M = calculate_slope({X1, Y1}, {Xf, Yf}),
IntM = validate_diag_slope(M),
B = Y1 - (IntM * X1),
diag_next_point(IntM, trunc(B), {X1, Y1}, {Xf, Yf}, []);
next_point({X1, Y1}, {Xf, Yf}) when X1 =:= Xf ->
row_next_point(X1, Y1, Yf, []);
next_point({X1, Y1}, {Xf, Yf}) when Y1 =:= Yf ->
column_next_point(Y1, X1, Xf, []).
row_next_point(_, _Y, _Y, [_H|T]) ->
lists:reverse(T);
row_next_point(X, Y1, Yf, Accum) when Y1 > Yf ->
row_next_point(X, Y1 - 1, Yf, [{X, Y1 - 1}|Accum]);
row_next_point(X, Y1, Yf, Accum) when Y1 < Yf ->
row_next_point(X, Y1 + 1, Yf, [{X, Y1 + 1}|Accum]).
column_next_point(_, _X, _X, [_H|T]) ->
lists:reverse(T);
column_next_point(Y, X1, Xf, Accum) when X1 > Xf ->
column_next_point(Y, X1 - 1, Xf, [{X1 - 1, Y}|Accum]);
column_next_point(Y, X1, Xf, Accum) when X1 < Xf ->
column_next_point(Y, X1 + 1, Xf, [{X1 + 1, Y}|Accum]).
```

I could *almost* consolidate `row_next_point/4`

and `column_next_point/4`

by passing the constant value first, regardless of whether it’s a row or column (`X`

or `Y`

), but I wouldn’t know which order to place the values in the tuple at the very end.^{3}

And my rook move becomes:

```
fun(Start, End, _) ->
case piece:calculate_slope(Start, End) of
0.0 ->
{ End, next_point(Start, End) };
infinity ->
{ End, next_point(Start, End) };
_ ->
{ Start, [] }
end
end
```

And at this point, the queen becomes trivial:

```
fun(Start, End, _) ->
case piece:calculate_slope(Start, End) of
1.0 ->
{ End, next_point(Start, End) };
-1.0 ->
{ End, next_point(Start, End) };
0.0 ->
{ End, next_point(Start, End) };
infinity ->
{ End, next_point(Start, End) };
_ ->
{ Start, [] }
end
end
```

And let’s see…

```
23> [ Q ] = [ X || {queenmove, X} <- piece:movefuns() ].
[#Fun<piece.6.71089158>]
24> Queen = spawn(piece, piece_loop, [ queen, Q, Q ]).
<0.72.0>
25> Queen ! { self(), move, {2, 3}, {9, 3}, white }.
{<0.44.0>,move,{2,3},{9,3},white}
26> Queen ! { self(), move, {2, 3}, {2, 6}, white }.
{<0.44.0>,move,{2,3},{2,6},white}
27> Queen ! { self(), move, {2, 3}, {9, 10}, white }.
{<0.44.0>,move,{2,3},{9,10},white}
28> Queen ! { self(), move, {2, 3}, {9, 9}, white }.
{<0.44.0>,move,{2,3},{9,9},white}
29> flush().
Shell got {yes,queen,{2,3},{9,3},[{3,3},{4,3},{5,3},{6,3},{7,3},{8,3}]}
Shell got {yes,queen,{2,3},{2,6},[{2,4},{2,5}]}
Shell got {yes,queen,{2,3},{9,10},[{3,4},{4,5},{5,6},{6,7},{7,8},{8,9}]}
Shell got {no,queen,{2,3},{9,9},[]}
```

And that, my dear reader, is all he wrote for the evening. Forthcoming tasks:

- Look for a way to trap infinite loops.
- Add unit tests.
- Create the board process.

Why not use

`abs(piece:calculate_slope(Start, End))`

in my`case`

statement and just check for`1.0`

as a result? Because`abs(infinity)`

is`badarg`

exception, amazingly enough.↩I decided to reverse the lists at the base case for my

`*_next_point`

functions so that the first piece in the way of a move is the one reported. For example, if we’re trying to move from`{3, 4}`

to`{3, 8}`

, I want`{3, 5}`

to show up in the list of traversed squares first so that any piece at`{3, 5}`

is reported as a blocker, instead of one at`{3, 7}`

.↩I could pass an anonymous function as another argument to my consolidated

`rowcol_next_point`

function that would know which value goes first in that tuple, but that seems like it would be quite difficult to follow.↩