Introduction
I'm primarily a C# programmer, just starting out with learning F#. I found myself with a problem which felt like it was appropriate for a functional language, and now that I have the first module in place, I want to get a review before ploughing on
Problem Statement
The game Bridges works as follows:
- The board is an NxM grid of locations
- Each location can (but doesn't have to) contain an island which has a number written on it
- Each island can also be connected horizontally or vertically to an adjacent island by a bridge. The adjacent island can be any distance, as long as it is directly along a compass direction.
- There can be at most two bridges connecting a pair of islands, and bridges may not cross
- The aim of the game is to draw bridges such that every island has a number of bridges connected to it equal to the number written on it. Additionally, every island must be reachable from every other island by the network of bridges.
The ultimate aim of the program will be to have a Bridges solver, which can take any board and solve it by applying some algorithms and using a tree search where it can't work out a certain next move. But what I'm including for this review is just the core module, which defines the relevant types and provides the basic functions needed to interact with the game.
The Code
module Core
let MaxBridgesInConnection = 2
type Island = {
Position : int * int
Required : int
}
type Connection = {
Origin : Island
Destination : Island
Bridges : int
}
type Board = {
Islands : Island list
Connections : Connection list
}
let PointBetween start finish (X, Y) =
let between a b x =
(x >= a && x <= b) || (x <= a && x >= b)
match start, finish with
| (0, startY), (0, finishY) -> between startY finishY Y
| (startX, 0), (finishX, 0) -> between startX finishX X
| _ -> failwith "Between must be used for a horizontal or vertical line"
let Cross a b =
match (a.Origin.Position, a.Destination.Position, b.Origin.Position, b.Destination.Position) with
| (aOrig, aDest, bOrig, bDest) ->
PointBetween aOrig aDest bOrig
&& PointBetween aOrig aDest bDest
&& PointBetween bOrig bDest aOrig
&& PointBetween bOrig bDest aDest
let IslandConnections board island =
board.Connections
|> List.filter (fun con -> con.Origin = island || con.Destination = island)
|> Set.ofList
let RemainingBridges board island =
let connections =
IslandConnections board island
|> Set.count
island.Required - connections
let CanAddBridges board connection count =
let blockedBy other =
other.Bridges > 0 && Cross connection other
connection.Bridges + count - 1 < MaxBridgesInConnection
&& (List.exists blockedBy board.Connections |> not)
let AddBridge board connection =
if CanAddBridges board connection 1 |> not then failwith "Tried to add invalid bridge"
let incrementMatching candidate =
if candidate=connection
then { connection with Bridges = connection.Bridges + 1 }
else connection
{ board with Connections = List.map incrementMatching board.Connections }
let IncompleteIslands board =
let incomplete island =
IslandConnections board island
|> Seq.sumBy (fun connection -> connection.Bridges)
|> (>) island.Required
board.Islands
|> List.filter incomplete
let ConnectedTo board island =
let otherEnd island connection =
match connection with
| { Bridges = 0 } -> None
| { Origin = orig; Destination = dest } when orig = island -> Some(dest)
| { Origin = orig; Destination = dest } when dest = island -> Some(orig)
| _ -> None
let allConnectedTo island =
board.Connections |> List.choose (otherEnd island)
let rec loop islands seen =
match islands with
| head::tail when Set.contains head seen -> loop tail (seen.Add head)
| head::tail -> loop (tail@(allConnectedTo head)) (seen.Add head)
| [] -> seen
loop [ island ] Set.empty
let Connected board =
ConnectedTo board board.Islands.[0]
|> Set.count
|> (=) board.Islands.Length
let Finished board =
IncompleteIslands board |> List.isEmpty
&& Connected board
Notes
As I said, I'm just starting out, so a lot of what I'm looking for is basic code-style stuff. That's with a particular focus on writing idiomatic F# code, but at the same time I'm aware that it's possible that I'm over-compensating and- for example- putting functions at the module level that really should be members on a type. I'm also interested in any advice relating to encapsulation.
As for the design, I always find myself having a lot of trouble when trying to deal with something that needs to be thought of as both a graph (checking all islands are connected) and as having an actual physical location (bridges can't cross) at the same time. This design is the best way I could come up with for this particular problem, after some false starts, but I'd be happy to hear high-level alternatives. If it's not clear, a Board
should already have all possible Connection
s at all times; when a bridge is added, the Bridges
field for the Connection
will be incremented. Creation of boards from just a list of islands will be handled by another module
PointBetween
to not throw an exception. Since it's returning abool
, I can give two suggestions: returnfalse
if the arguments are invalid; or returnbool option
instead, returningNone
if the arguments are invalid. \$\endgroup\$type AddBridgeResult = InvalidBridge | BridgeAdded of Board
. Even better would be designing things such that the invalid operation doesn't even compile. \$\endgroup\$