10
\$\begingroup\$

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.

                                                        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 Connections 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

\$\endgroup\$
  • \$\begingroup\$ The only suggestion I have is to change PointBetween to not throw an exception. Since it's returning a bool, I can give two suggestions: return false if the arguments are invalid; or return bool option instead, returning None if the arguments are invalid. \$\endgroup\$ – Christopher Stevenson Oct 26 '14 at 20:24
  • \$\begingroup\$ I agree with the comment above about avoiding exceptions, but instead of booleans consider creating a new type modeling each result. \$\endgroup\$ – Mauricio Scheffer Oct 27 '14 at 1:27
  • \$\begingroup\$ @MauricioScheffer Could you give an example of a result which would be appropriate as a type? \$\endgroup\$ – Ben Aaronson Oct 27 '14 at 2:26
  • 1
    \$\begingroup\$ type AddBridgeResult = InvalidBridge | BridgeAdded of Board. Even better would be designing things such that the invalid operation doesn't even compile. \$\endgroup\$ – Mauricio Scheffer Oct 27 '14 at 3:44
  • \$\begingroup\$ I rolled back the edit because I don't think "Idiomaticness" is a word, and the code is for a solver, not a game. Also while the "Code" heading may seem a bit redundant because what follows is obviously code, without that heading it seems like the code is within the "Problem Statement" section. \$\endgroup\$ – Ben Aaronson Nov 2 '14 at 21:37
3
+200
\$\begingroup\$

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.

Let's explore what this would look like with an adjacency-list representation of the graph. Apologies for any errors I introduce along the way.

One motivating factor is that a lot of operations that we do are local, not global -- we're often just interested in the neighbours of a particular island.

First let's change the data types:

type Island = {
    Position : int * int
    Required : int
}

type Connection = {
    Origin : Island
    Destination : Island
    Bridges : int
}

type Board = {
    Islands : Island list
    Connections : Connection list
}
type Island = {
    Position : int * int
    Required : int
    Connections : Map<Island, int>
}

type Board = {
    Islands : Island list
}

There are other possible choices for Map<Island, int>, but let's stick with this for now.

The original definition of RemainingBridges looks a bit off:

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

I think it's counting the number of connections, when it should be counting bridges. Assuming the logic of the original is correct, we can rewrite it as

let RemainingBridges (island : Island) =
    island.Required - (Seq.length island.Connections)

Or if we're supposed to count bridges,

let RemainingBridges (island : Island) =
    island.Required - Seq.sumBy snd (Map.toSeq island.Connections)

We can use RemainingBridges to simplify IncompleteIsland

let IncompleteIslands board =
    let incomplete island =
        IslandConnections board island
        |> Seq.sumBy (fun connection -> connection.Bridges)
        |> (>) island.Required
    board.Islands
    |> List.filter incomplete
let IncompleteIslands (board : Board) =
    List.filter (fun island -> RemainingBridges island > 0) board.Islands

At this point we can remove IslandConnections altogether.

Next up is ConnectedTo. Here's a good example of us being interested in local operations -- we can remove the board parameter.

let ConnectedTo (island : Island) =
    let allConnectedTo (island : Island) =
        island.Connections |> Map.toList |> List.map fst
    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

Which leads to

let Connected (board : Board) =
    board.Islands.Length = Set.count (ConnectedTo board.Islands.[0])

The remaining functions don't look as nice as I would like them to. I'll post them here for completeness, but there are (hopefully!) cleaner ways to express them.

let Bridges (island : Island) (other : Island) =
    match Map.tryFind other island.Connections with
    | Some n -> n
    | None -> 0

let Cross (aOrig : int * int) (aDest : int * int) (bOrig : int * int) (bDest : int * int) =
    PointBetween aOrig aDest bOrig
    && PointBetween aOrig aDest bDest
    && PointBetween bOrig bDest aOrig
    && PointBetween bOrig bDest aDest

let CanAddBridges board (a : Island) (b : Island) count =
    let blockedBy (d : Island) =
        Map.exists (fun c _ -> Cross a.Position b.Position c.Position d.Position) d.Connections
    Bridges a b + count - 1 < MaxBridgesInConnection
    && (List.exists blockedBy board.Islands |> not)

let AddBridge board islandA islandB =
    if CanAddBridges board islandA islandB 1 |> not then failwith "Tried to add invalid bridge"

    let addBridge (island : Island) (other : Island) =
        let bridges = Bridges island other
        { island with Connections = Map.add island (bridges + 1) island.Connections }

    let incrementMatching candidate =
        if candidate = islandA then addBridge candidate islandB
        else if candidate = islandB then addBridge candidate islandA
        else candidate
    { board with Islands = List.map incrementMatching board.Islands }
\$\endgroup\$
  • \$\begingroup\$ Was difficult to decide where to award the bounty between these two great answers, but overall I think this one edged out the other in substantive suggestions \$\endgroup\$ – Ben Aaronson Nov 7 '14 at 10:22
7
\$\begingroup\$
module Core

This sounds way too general to me. Unless this code is in a namespace that you're not showing here, you should use a more descriptive name.


type Connection = {
    Origin : Island
    Destination : Island
    Bridges : int
}

I don't like that you have undirected graph, but you're calling the edges Origin and Destination, as if the edge was directed. Though I'm not sure what would be a better solution: tuples are also ordered and creating a custom "unordered pair" type just for this is an overkill.


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"

I don't think this can work. Vertical line is not just a line that has both X coordinates zero, it's a line that has both X coordinates the same.

To fix the pattern, you could do something like:

match start, finish with
| (startX, startY), (finishX, finishY) when startX = finishX -> between startY finishY Y
| (startX, startY), (finishX, finishY) when startY = finishY -> between startX finishX X
| _ -> failwith "Between must be used for a horizontal or vertical line"

But that's not very nice and I think it would be better using if-elif-else:

let (startX, startY) = start
let (finishX, finishY) = finish

if startX = finishX then between startY finishY Y
elif startY = finishY then between startX finishX X
else failwith "Between must be used for a horizontal or vertical line"

match (a.Origin.Position, a.Destination.Position, b.Origin.Position, b.Destination.Position) with 
| (aOrig, aDest, bOrig, bDest) -> 

I don't think you should be using pattern matching like this. If you want to assign to multiple variables at the same time, you can use let:

let (aOrig, aDest, bOrig, bDest) =
    (a.Origin.Position, a.Destination.Position, b.Origin.Position, b.Destination.Position)

PointBetween aOrig aDest bOrig
&& PointBetween aOrig aDest bDest
&& PointBetween bOrig bDest aOrig
&& PointBetween bOrig bDest aDest

You could get rid of some of the duplication here by writing a list of tuples of the parameter combinations and then calling List.forall PointBetween:

[aOrig, aDest, bOrig; aOrig, aDest, bDest;
 bOrig, bDest, aOrig; bOrig, bDest, aDest] |>
    List.forall PointBetween

Though this requires that you declare PointBetween in tupled form:

let PointBetween(start, finish, (X, Y)) =

I have also considered generating the sequence of points, instead of hard-coding it, but the best I could figure out is:

[ for (con1, con2) in [a, b; b, a] do
  for v in [con2.Origin; con2.Destination] do
  yield (con1.Origin.Position, con1.Destination.Position, v.Position) ]

I think think makes the structure more obvious, but it's also more complicated, so it's probably the worse option.


IslandConnections board island
|> Seq.sumBy (fun connection -> connection.Bridges)
|> (>) island.Required

That |> (>) part looks confusing to me. I would probably write this as:

let existingConnections = 
    IslandConnections board island
    |> Seq.sumBy (fun connection -> connection.Bridges)
existingConnections > island.Required
\$\endgroup\$
  • \$\begingroup\$ Lots of great points here, thanks very much. Since these are generally about lower-level details, does that mean you like the overall design (in particular the main data structures used to represent the game state)? Or was that just not an area you decided to cover? \$\endgroup\$ – Ben Aaronson Nov 2 '14 at 21:21
  • \$\begingroup\$ @BenAaronson Yeah, I think the overall design is reasaoble, as long as you're okay with the inefficiencies (e.g. finding a neighbor of a an island requires walking through all connections). \$\endgroup\$ – svick Nov 2 '14 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.