Building a Crossword in F# - Part I

April 9 2021 · tech fsharp fable feliz

Friends and I compete at the NYT Mini Crossword, a daily crossword published by the New York Times which can be completed in a couple of minutes. The crossword is made from a mixture of cryptic, pop culture, and typical crossword style clues. When you begin the crossword the timer starts and when you finish it displays the time it took you to solve it.

In this series of blog posts I create a crossword engine using in F# using Fable, Feliz, React, and Bulma. To start with we get familiar with the technologies and produce an MVP. In later posts I refactor into more idiomatic F# patterns and add more features to the crossword.

This is what we’re building. CSS responsiveness squashes the clues below the grid. You can also open the crossword in another tab.

Modelling the Domain

How do we model a crossword using F# types? I followed an approach outlined in Scott Wlaschin’s book Domain Modeling Made Functional. Thinking of the crossword domain in terms of data types and the events which will take place.

We represent the grid as a Cell list list (a list of list of Cell). Cells on the crossword grid are either Black or White. Black cells are blocked out spacers, whereas in White cells we must enter a guess.

type White = {
    Number: int option
    Solution: string
    Guess: string
    Solved: bool
    Id: int // uniquely identify each cell, needed by React
}

type Cell = 
    | Black
    | White of White

type Grid = Cell list list

The Grid and clues are modelled independently. There’s nothing in the type definition which connects them.

type Direction = Down | Across
type Clue = {
    Direction: Direction
    Number: int
    Clue: string
}

State with Fable and Feliz

For the crossword to be played in a web browser our F# code must be compiled to Javascript. For this we use Fable along with the library Feliz as a React DSL. I’m proficient in React so we’ll use the standard React primitive useReducer for state management. A common alternative in the F# community is the Elmish pattern.

With the useReducer hook we need to specify the state and messages (events) which are used in the component.

The game can be in one of several states which we model with GameState. When the page is first opened the state is Ready. When the user clicks the Start button the state transitions to Started and we record the time. Finally when the crossword is solved the state changes to Ended, a finishing time is recorded and displayed.

type GameState =
    | Ready
    | Started
    | Ended

State stores a copy of the Grid. This gets updates every time a guess gets made and the Check Solution button is clicked.

type State = {
    grid: Grid
    gameState: GameState
    startTime: DateTime option
    endTime: DateTime option
}

In the useReducer pattern the update function transitions our application from one state to the next. The function signature is State -> Msg -> State which means given an existing State and Msg which was dispatched, return a new State. This is a great functional programming pattern and it fits naturally with F#.

We only have a few messages (events) which take place within the component.

  • StartGame - Dispatched when the user clicks the Start Game button.
  • CheckSolution - Dispatched when the user clicks the Check Solution button.
  • GuessUpdated - Dispatched on the input form field onChange event - whenever the user types a guess into a white cell.
type Msg =
    | StartGame
    | CheckSolution
    | GuessUpdated of (White * string)


// State -> Msg -> State
let update (state: State) = function
    | StartGame -> { state with startTime = Some DateTime.Now; gameState = Started }
    | CheckSolution -> state |> checkCellsAndUpdateStateIfSolved |> checkGridAndUpdateStateIfSolved
    | GuessUpdated (cell, v) -> updateGuess state cell v

Connecting It All

With the state pattern established, and all messages defined, we can start establish the useReducer pattern.

let crosswordComponent = React.functionComponent(fun () ->
    let (state, dispatch) = React.useReducer(update, initialState)

    ... returns some Feliz (JSX) elements which get rendered on the screen ...

To specify the grid I’ve defined helper functions makeCell and makeCellWithNumber which return instances of Cell.White. In a future post I’ll show how we can dynamically load grids from JSON files.

let initialState: State = {
    grid = [
        [Black; Black; makeCellWithNumber "T" 1; makeCellWithNumber "V" 2; makeCellWithNumber "S" 3;]
        [makeCellWithNumber "B" 4; makeCellWithNumber "R" 5; makeCell "A"; makeCell "I"; makeCell "N";]
        [makeCellWithNumber "D" 6; makeCell "U"; makeCell "N"; makeCell "N"; makeCell "O";]
        [makeCellWithNumber "A" 7; makeCell "S"; makeCell "K"; makeCell "E"; makeCell "W";]
        [makeCellWithNumber "Y" 8; makeCell "E"; makeCell "S"; Black; Black]
    ];
    gameState = GameState.Ready
    startTime = None
    endTime = None
}

Feliz Views

Within the context of crosswordComponent we have access to the current application’s State as well as the function dispatch which we can use to fire events. These messages go through the update function above and will return a new copy of the state. Our View becomes almost declarative, given whatever State (a field of which is GameState : Ready, Started, Ended) we return Feliz JSX elements.

We’re using the library Feliz.Bulma which has bindings to the Bulma CSS library. This gives us consistent styling and makes it easy to define row and column layouts in CSS. The view code is quite verbose so I’ve omitted alot from this post.

let crosswordComponent = React.functionComponent(fun () ->
    let (state, dispatch) = React.useReducer(update, initialState)
    
    let startButtonOrClues =
        match state.gameState with
        | Ready -> Bulma.button.a [ prop.text "Start Game"
                                    prop.onClick (fun _ -> dispatch StartGame) ]
        | _ -> Html.div [
                    Html.div [
                        Bulma.button.a [
                            button.isLarge
                            color.hasBackgroundLight
                            prop.text "Check"
                            prop.onClick (fun _ -> dispatch CheckSolution)
                        ]
                    ]
                    Html.div [
                        Html.h3 [
                            text.hasTextWeightBold   
                            prop.text "Across"
                        ]
                        renderClues clues Across
                    ]
                    Html.div [
                        Html.h3 [
                            text.hasTextWeightBold   
                            prop.text "Down"
                        ]
                        renderClues clues Down
                    ]]
                
    let timeTakenToSolve =
        match state.gameState with
        | GameState.Ended -> Html.h1 [
            text.hasTextWeightBold
            prop.text (sprintf "You solved a puzzle in %.0f seconds" (state.endTime.Value - state.startTime.Value).TotalSeconds)
            ]
        | _ -> Html.h1 ""
        
    Html.div [
        Bulma.columns [
            Bulma.column [
                column.is12
                prop.children [
                    timeTakenToSolve
                ]
            ]
        ]
        Bulma.columns [
            Bulma.column [
                column.is3
                prop.children [
                    renderGrid state.grid dispatch
                ]
            ]
            Bulma.column [
                column.is3
                prop.className "content"
                prop.children [
                    startButtonOrClues
                ]
            ]
        ]
    ]
)

Some patterns in the view code become apparent:

  • matching on the State.gameState, this is the state machine pattern paying dividends.
  • Splitting up rendering logic into smaller functions. These functions take a subset of the state and return some Feliz elements. A couple of examples are below.
let renderClues clues direction =
    let renderedClues = 
        clues
        |> List.filter (fun clue -> clue.Direction = direction)
        |> List.map (fun clue -> Html.li (sprintf "%d - %s" clue.Number clue.Clue))

    Html.ul renderedClues


let renderCell (dispatch: Dispatch) (cell: Cell) = 
    let contents = 
        match cell with
        | Black -> Html.div []
        | White x -> renderWhiteCell x dispatch

    let className =
        match cell with
        | Black -> "black-cell"
        | White _ -> "white-cell"

    Html.td [
        prop.className className
        prop.children [ contents ]
    ]

let renderGrid (grid: Grid) (dispatch: Dispatch) = 

    let rows =
        grid
        |> List.map (fun row -> 
            Html.tr (row |> List.map (renderCell dispatch))
        )

    Html.table [
        Html.tbody rows
    ]

While verbose, F# language features combined with the useReducer pattern gives us a safe way to write views. State only flows in one direction - Views render state but never change it. F#’s pattern matching and pipelines makes our code easy to understand.

Conclusion

There’s the first take at implementing the crossword. We’ve got a working game with a good base state structure. Continue reading in Part II where we refactor some code to make it more idiomatic F#.

Full source code is available on Github.


Related Posts