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 + bSo, first, let’s find b:
y = mx + b
y - mx = bTough 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:
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 > X1We’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).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.0And 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} ).
infinitySince 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
endAnd, 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}]}
okAnd 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 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
endAnd 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
endAnd 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:
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.↩