<h2 id="heading-url">URL</h2>
<a target="_blank" href="https://leetcode.com/problems/knight-dialer/description/?envType=daily-question&amp;envId=2023-11-27">Knight Dialer - LeetCode</a>
<h2 id="heading-code">Code</h2>
<a target="_blank" href="https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0935/main.fsx">https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0935/main.fsx</a>
<pre><code class="lang-fsharp">let knightDialer (n: int) : int =
 let modulo = 1_000_000_007

 let moves =
 [| [ 4; 6 ]
 [ 6; 8 ]
 [ 7; 9 ]
 [ 4; 8 ]
 [ 3; 9; 0 ]
 []
 [ 1; 7; 0 ]
 [ 2; 6 ]
 [ 1; 3 ]
 [ 2; 4 ] |]

 let rec knightDialer' n pos cache =
 if n = 1 then
 1, cache
 else
 match Map.tryFind (n, pos) cache with
 | Some(v) -&gt; v, cache
 | None -&gt;
 let ret, cache' =
 moves.[pos]
 |&gt; List.fold
 (fun (acc, cache) next -&gt;
 let ret, cache' = knightDialer' (n - 1) next cache
 (acc + ret) % modulo, cache')
 (0, cache)

 ret, Map.add (n, pos) ret cache'

 seq { 0..9 }
 |&gt; Seq.fold
 (fun (acc, cache) pos -&gt;
 let ret, cache' = knightDialer' n pos cache
 (acc + ret) % modulo, cache')
 (0, Map.empty)
 |&gt; fst
</code></pre>

## URL

[Knight Dialer - LeetCode](https://leetcode.com/problems/knight-dialer/description/?envType=daily-question&envId=2023-11-27)

## Code

[https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0935/main.fsx](https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0935/main.fsx)

```fsharp
let knightDialer (n: int) : int =
    let modulo = 1_000_000_007

    let moves =
        [| [ 4; 6 ]
           [ 6; 8 ]
           [ 7; 9 ]
           [ 4; 8 ]
           [ 3; 9; 0 ]
           []
           [ 1; 7; 0 ]
           [ 2; 6 ]
           [ 1; 3 ]
           [ 2; 4 ] |]

    let rec knightDialer' n pos cache =
        if n = 1 then
            1, cache
        else
            match Map.tryFind (n, pos) cache with
            | Some(v) -> v, cache
            | None ->
                let ret, cache' =
                    moves.[pos]
                    |> List.fold
                        (fun (acc, cache) next ->
                            let ret, cache' = knightDialer' (n - 1) next cache
                            (acc + ret) % modulo, cache')
                        (0, cache)

                ret, Map.add (n, pos) ret cache'

    seq { 0..9 }
    |> Seq.fold
        (fun (acc, cache) pos ->
            let ret, cache' = knightDialer' n pos cache
            (acc + ret) % modulo, cache')
        (0, Map.empty)
    |> fst
```

LeetCode 935. Knight Dialer in F#

URL

Code