2012-09-04

## And you wonder why you never finished your CS degree

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.

## So what’s going on with my slope check logic?

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.

## So, what now?

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.

## Bishopry

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.

## Rooks?

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

Following the same basic structure2 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.
1. 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.
2. 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}`.
3. 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.