10
\$\begingroup\$

Here is a Battlehips game in F#. Now, before you start jumping up and down on my code, please understand that, for all its awesomeness, F# has a serious limitation: Its compilation is linear, and the solution structure cannot have folders. Any code that uses other code must be below the other code, whether in the same file, or in another file lower than the first file in the compilation sequence.

Here is my GeneralData file. It contains basic data and methods not specifically relevant to other groups.

module GeneralData

type direction = Horizontal | Vertical

type public point = {x :int; y :int}
type public battleship = {coordinate :point; direction :direction; length :int}

let charToDirection (character :char) :direction =
    match character with
    | 'H' | 'h' -> Horizontal
    | 'V' | 'v' -> Vertical
    | _ -> raise <| new System.ArgumentException("character must be 'H' or 'V'", "character")

let directionToChar (character :direction) :char =
    match character with
    | Horizontal -> 'H'
    | Vertical -> 'V'

Next in the compilation hierarchy is my Board class:

module Board

open GeneralData
open System

[<Flags>]
type public squareState = Empty = 0 | Ship = 1 | Bombarded = 2

type public Board() =
    let mutable board :squareState[,] = Array2D.init 10 10 (fun x y -> squareState.Empty)

    let getChar (state :squareState) :char =
        if state.HasFlag(squareState.Bombarded) && state.HasFlag(squareState.Ship) then
            'X'
        elif state.HasFlag(squareState.Bombarded) then
            'O'
        else
            ' '

    let getCharShowingShips (state :squareState) :char =
        if state.HasFlag(squareState.Bombarded) && state.HasFlag(squareState.Ship) then
            'X'
        elif state.HasFlag(squareState.Bombarded) then
            'O'
        elif state.HasFlag(squareState.Ship) then
            'S'
        else
            ' '

    member self.boardArray :squareState[,] = board

    member public self.placeShip(ship :battleship) =
        for i = 0 to ship.length - 1 do
            // This member should only be called before bombardment starts,
            // which means that all squares are either flagged "Empty" (0) or "Ship" (1)
            // No need to combine the exising flag with the "Ship` flag
            match ship.direction with
            | Horizontal -> board.[ship.coordinate.x, ship.coordinate.y + i] <- squareState.Ship
            | Vertical -> board.[ship.coordinate.x + i, ship.coordinate.y] <- squareState.Ship

    member public self.canPlaceShip (ship :battleship) :bool =
        let mutable allFreeCoordinates = true

        for i = 0 to ship.length - 1 do
            // This member should only be called before bombardment starts,
            // which means that all squares are either flagged "Empty" (0) or "Ship" (1)
            // No need to use the `HasFlag` member
            match ship.direction with
            | Horizontal -> allFreeCoordinates <- allFreeCoordinates
                                && not (ship.coordinate.y + i > 9)
                                && not (board.[ship.coordinate.x, ship.coordinate.y + i] = squareState.Ship)
            | Vertical -> allFreeCoordinates <- allFreeCoordinates
                                && not (ship.coordinate.x + i > 9)
                                && not (board.[ship.coordinate.x + i, ship.coordinate.y] = squareState.Ship)

        allFreeCoordinates

    member public self.bombard(coord :point) =
        if coord.x < 0 || coord.x > 10 ||
           coord.y < 0 || coord.y > 10 then
            raise <| new System.ArgumentException("Point must be in range ([0-9], [0-9]", "coord")

        if board.[coord.x, coord.y].HasFlag(squareState.Bombarded) then
            raise <| new System.ArgumentException("Square already bombarded", "coord")

        // Save the original "Ship" flag (if any) in addition to adding the "Bombarded" flag
        board.[coord.x, coord.y] <- board.[coord.x, coord.y] ||| squareState.Bombarded

    member public self.areAllShipsSunk() :bool =
        let mutable shipNotSunk = true
        for x = 0 to 9 do
            for y = 0 to 9 do
                let state = board.[x, y]
                if state.HasFlag(squareState.Ship) && not (state.HasFlag squareState.Bombarded) then
                        shipNotSunk <- false

        shipNotSunk

    member public self.state(coord :point) =
        if coord.x < 0 || coord.x > 10 ||
           coord.y < 0 || coord.y > 10 then
            raise <| new System.ArgumentException("Point must be in range ([0-9], [0-9]", "coord")

        board.[coord.x, coord.y]

    member public self.print() =
        printfn "--------------------------------------------"
        for i = 0 to 9 do
            // print row number and first token
            printf "%s%d" (if i = 9 then "" else " ") (i + 1)

            for j = 0 to 9 do
                printf " | %c" (getChar(board.[i, j]))

            printfn " |%s--------------------------------------------" Environment.NewLine

        printfn "%s" (String.Format("     1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10"))

    member public self.printShowingShips() =
        printfn "--------------------------------------------"
        for i = 0 to 9 do
            // print row number and first token
            printf "%s%d" (if i = 9 then "" else " ") (i + 1)

            for j = 0 to 9 do
                printf " | %c" (getCharShowingShips(board.[i, j]))

            printfn " |%s--------------------------------------------" Environment.NewLine

        printfn "%s" (String.Format("     1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10"))

The InputFunctions module follows the Board class, and contains a representation of a game board:

module InputFunctions

open Board
open GeneralData
open System

// internal for testing purposes only
let internal isValidInput (board :Board) (shipLength :int) (input :string[]) :bool =
    let mutable xInput : int = -1
    let mutable yInput : int = -1

    let isValidInput = input.Length = 3 &&
                       Int32.TryParse(input.[0], &xInput) &&
                       xInput >= 1 && xInput <= 10 &&
                       Int32.TryParse(input.[1], &yInput) &&
                       yInput >= 1 && yInput <= 10 &&
                       Array.contains input.[2].[0] [|'H'; 'V'; 'h'; 'v'|]

    // adjust coordinate for 1-based UI
    let coord = {x = xInput - 1; y = yInput - 1}
    isValidInput && (board.canPlaceShip {coordinate = coord; direction = charToDirection(input.[2].[0]); length = shipLength})

let inputBattleshipCoord (board :Board) (shipName :string) (shipLength :int) :battleship =

    // invalid array to trigger loop
    let mutable input = [|"-1"; "-1"; "I"|]

    // todo: check if input also fits on board
    while not (isValidInput board shipLength input) do
        printf "Please enter the upper left position for your %s (%d squares long) in the format 'Row:Column:{V or H}' (without the quotes or braces): " shipName shipLength
        input <- Console.ReadLine().Split(':')

    let coordinate :point = {x = Int32.Parse(input.[0]) - 1; y = Int32.Parse(input.[1]) - 1}
    {coordinate = coordinate; direction = charToDirection(input.[2].[0]); length = shipLength}

// internal for testing purposes only
let internal isValidBombardInput (board :Board) (input :string[]) =
    let mutable xInput :int = -1
    let mutable yInput :int = -1

    input.Length = 2 &&
    Int32.TryParse(input.[0], &xInput) &&
    xInput >= 1 && xInput <= 10 &&
    Int32.TryParse(input.[1], &yInput) &&
    yInput >= 1 && yInput <= 10 &&
    not (board.state({x = xInput - 1; y = yInput - 1}).HasFlag(squareState.Bombarded))

let inputBombardPoint (board :Board) :point =
    let mutable input = [||]

    while not (isValidBombardInput board input) do
        printf "Input the point you want to bombard as 'Row:Column' (without the quotes): "
        input <- Console.ReadLine().Split(':')

    {x = Int32.Parse(input.[0]) - 1; y = Int32.Parse(input.[1]) - 1}

Finally, here is the Battleships module, which runs the game:

module Start

open Board
open GeneralData
open InputFunctions
open System
open System.Collections.Generic

let ships :(string * int)[] =
    [|
        ("Aircraft carrier", 5)
        ("Battleship", 4)
        ("Frigate", 3)
        ("Submarine", 3)
        ("Minesweeper", 2)
    |]

let rand = new Random()

let placeUserShips (board :Board) =
    for i = 0 to ships.Length - 1 do
        let shipName, shipLength = ships.[i]
        let ship = inputBattleshipCoord board shipName shipLength
        board.placeShip ship
        board.printShowingShips()

let placeComputerShips (board :Board) =
    for i = 0 to ships.Length - 1 do
        // invalid value to trigger loop
        let mutable shipPlaced = false

        while not shipPlaced do
            let xCoord = rand.Next(0, 10)
            let yCoord = rand.Next(0, 10)
            let direction = if rand.Next(0, 2) = 0 then Horizontal else Vertical
            let ship = {coordinate = {x = xCoord; y = yCoord}; direction = direction; length = snd ships.[i]}

            if board.canPlaceShip ship then
                board.placeShip ship
                shipPlaced <- true

let userBombard (board :Board) =
    let mutable bombard = true

    while bombard do
        let point = inputBombardPoint board
        board.bombard point

        if not ((board.state point).HasFlag(squareState.Ship)) ||
           board.areAllShipsSunk() then
            bombard <- false

let computerBombard (board :Board) =
    let openPoints = new List<point>()

    for x = 0 to 9 do
        for y = 0 to 9 do
            let currentPoint = {x = x; y = y}
            if not (board.state(currentPoint).HasFlag(squareState.Bombarded)) then
                openPoints.Add(currentPoint)

    let mutable bombard = true
    while bombard do
        let nextPoint = rand.Next(0, openPoints.Count)
        board.bombard openPoints.[nextPoint]

        if not ((board.state openPoints.[nextPoint]).HasFlag(squareState.Ship)) ||
           board.areAllShipsSunk() then
            bombard <- false
        else
            openPoints.RemoveAt nextPoint

[<EntryPoint>]
let main argv =
    let userBoard = new Board()

    // display empty board so user knows how/where to place ships
    userBoard.printShowingShips()
    placeUserShips userBoard

    let computerBoard = new Board()
    placeComputerShips computerBoard

    while not (computerBoard.areAllShipsSunk()) && not (userBoard.areAllShipsSunk()) do
        // no need to check computer win because the loop would have ended
        userBombard computerBoard
        computerBoard.print()
        printfn ""

        // check user win
        if not (computerBoard.areAllShipsSunk()) then
            computerBombard userBoard
            userBoard.print()
            printfn ""

    printfn (if computerBoard.areAllShipsSunk() then "You won!" else "You lost!")
    0

I have this set up with a very basic algorithm for the computer to play (random-selection, hence the title--you'd have pretty bad luck to be fully sunk). Next, my plan is to create a Player interface with two classes implementing it (HumanPlayer and ComputerPlayer). This will help clean some of the muddle of the Battleships module up, and will make it easier to implement a better algorithm for the computer, and may make it easier to let the user choose to play the computer or another person.

Some of my specific concerns about this is that I may have implemented this in either a too-C# or too-OOP manner. I'm not really familiar with functional programming or F#, so feel free to comment on anything that should be done differently.

\$\endgroup\$
  • \$\begingroup\$ Quick nit-pick: the Board module must be second, not third, because it is used by InputFunctions \$\endgroup\$ – AlexFoxGill Sep 13 '16 at 11:22
  • \$\begingroup\$ @AlexFoxGill You are right--the Board module is second in my program. \$\endgroup\$ – Hosch250 Sep 13 '16 at 15:20
  • 1
    \$\begingroup\$ In case you didn't see it, there's a question here where someone has taken the functional route - it may help \$\endgroup\$ – AlexFoxGill Sep 20 '16 at 8:15
8
\$\begingroup\$

You are correct in your statement that this is a pretty standard OOP implementation. The key signs are lots of mutable state and explicit loops. It's hard to give a line-by-line critique because a functional program would be structured so differently (maybe this is why nobody has posted an answer yet!)

First let's tackle a small stylistic point: It's generally accepted that in F#, types and type members are PascalCase, whereas function names are camelCase.

Another thing that stands out is that the functions in your code are quite long. A common consequence of FP, and in particular designing with types, is that you end up with smaller functions at every level, which can be composed and used at the higher level.

A common temptation when modelling two-dimensional boards such as in Battleships (or Chess, Noughts and Crosses etc) is to try and model the physical nature of the board - ie, a 2-dimensional array. However, when you think about the domain, this is only superficial. What you really have on a "board" is a series of points/coordinates, a set of ships which occupy some of those points, and a series of guesses (again, points). With the 2d-array approach, you're immediately restricted to working with primitive values by indexing into the array. Although you had the right idea by creating the point record type, you didn't leverage the ability to work on the point level - instead, all the functions which use the point type are further up the conceptual hierarchy, mainly in the Board type. The mental model of the array restricts your thinking to X and Y values, rather than dealing in points.

I'd like to give a longer answer but I'm out of time right now, I'll gladly respond to any questions you have! I started working on a functional version of the problem, I only got as far as the "domain" (no input events or rendering yet) but perhaps this will help you visualise how a functional version would be structured:

module Common =
    type Result<'TSuccess,'TError> = 
     | Success of 'TSuccess 
     | Error of 'TError

module Seq =
    let overlaps (xs: 'a seq) (ys: 'a seq) = Seq.exists2 (=) xs ys

module Domain =
    type Direction = Horizontal | Vertical

    type Point = {
        X: int
        Y: int
    } with
        static member zero = { X = 0; Y = 0 }
        static member addX (p: Point) (i: int) = { p with X = p.X + i }
        static member addY (p: Point) (i: int) = { p with Y = p.Y + i }
        static member add = function
            | Horizontal -> Point.addX
            | Vertical -> Point.addY
        static member (>~=) (a: Point, b: Point) =
            a.X >= b.X && a.Y >= b.Y

    type Ship = {
        Name: string
        Length: int
    }

    let ships = [
        { Name = "Aircraft Carrier"; Length = 5 }
        { Name = "Battleship"; Length = 4 }
        { Name = "Frigate"; Length = 3 }
        { Name = "Submarine"; Length = 3 }
        { Name = "Minesweeper"; Length = 2 }
    ]

    type PlacedShip = {
        Ship: Ship
        Position: Point
        Direction: Direction
    } with
        static member allPoints (ps: PlacedShip) =
            List.init ps.Ship.Length (Point.add ps.Direction ps.Position)
        static member lastPoint (ps: PlacedShip) =
            Point.add ps.Direction ps.Position (ps.Ship.Length - 1)

    type BoardState = {
        Ships: PlacedShip list
        Guessed: Set<Point>
        Bounds: Point
    } with
        static member allPlacedPoints (bs: BoardState) =
            bs.Ships
            |> Seq.collect PlacedShip.allPoints
            |> Set.ofSeq

        static member placeShip (bs: BoardState) (s: PlacedShip) =
            let withinBounds =
                bs.Bounds >~= (PlacedShip.lastPoint s) && s.Position >~= Point.zero

            let overlapsOtherShips =
                bs
                |> BoardState.allPlacedPoints
                |> Seq.overlaps (PlacedShip.allPoints s)

            if not withinBounds then
                Common.Error "This ship placement is out of bounds"
            else if overlapsOtherShips then
                Common.Error "This ship placement overlaps another ship"
            else
                Common.Success { bs with Ships = s :: bs.Ships }

        static member addGuess (bs: BoardState) (p: Point) =
            if Set.contains p bs.Guessed then
                Common.Error <| sprintf "The coordinate %A has already been guessed" p
            else
                Common.Success { bs with Guessed = Set.add p bs.Guessed }

        static member hasLost (bs: BoardState) =
            bs
            |> BoardState.allPlacedPoints
            |> Set.isSubset bs.Guessed

    type Player = {
        Name: string
        Board: BoardState
    }
\$\endgroup\$
  • \$\begingroup\$ Thanks. I guess I have a lot to learn about FP. And I thought my functions were pretty short (I guess they were... for OOP functions...). \$\endgroup\$ – Hosch250 Sep 13 '16 at 16:13
6
\$\begingroup\$

Imperative Programming vs. Functional Programming

AlexFoxGill brought up the point that your code is structured a lot like something you'd write in an imperative language, however, the major differences between functional and imperative programming weren't brought up. The two biggest differences you need to know about are how code is structured and how flow control is different.

Code in imperative languages is structured in a way that describes how the performs tasks that manage the state. Code in functional languages is structured in a way that describes what inputs are required and how that input is transformed. Many functional languages, like F# and Haskell, allow you to write imperative code to some degree, but most of the time there's a better, functional, solution.

Flow control in imperative languages the stuff that you'd typically expect (if, for, foreach, do, while, etc.). Nothing out of the ordinary. Flow control in functional languages is based much more around function calls and recursion. Again, many functional languages allow you to write imperative flow control to some degree, but most of the time there's a better solution.

These are the two biggest things you should be aware of, but there are some more. This chart from MSDN provides some nice comparisons between imperative and functional languages, and I think it's very helpful.


Miscellaneous code tips

In F#, you typically want to avoid writing if-elif-else chains like you did here:

if state.HasFlag(squareState.Bombarded) && state.HasFlag(squareState.Ship) then
    'X'
elif state.HasFlag(squareState.Bombarded) then
    'O'
elif state.HasFlag(squareState.Ship) then
    'S'
else
    ' '

Instead of doing the above, you can use F# pattern matching using match. F# also provides a when clause that can be used in pattern matching to provide a condition for each pattern. If we use both of these things, the above piece of code becomes this:

match state with
| state when state.HasFlag(squareState.Bombarded) && state.HasFlag(squareState.Ship) -> 'X'
| state when state.HasFlag(squareState.Bombarded) -> 'O'
| state when state.HasFlag(squareState.Ship) -> 'S'
| _ -> ' '

Loops, especially for loops, are also generally something you want to avoid unless they're absolutely necessary. In many cases, for loops can be shortened down to a function being mapped over a range, or something similar.

In most cases, it's not necessary to explicitly specify variable, parameter and return types. For example, if I had the following function:

let f (a: int) (b: int): int =
    ...

It could be re-written as this:

let f a b =
    ...

As long as your variable names are good enough and your code is written clearly, you don't need to specify types. In fact - it often makes your code look less cluttered and more readable.

\$\endgroup\$

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.