2023 パズル in F#

他の人の回答などを見ずに愚直に解いてみたが全部を算出しようとすると遅すぎた.

type Opcode =
    | Add
    | Sub
    | Mul
    | Div

type Operand =
    | Opcode of Opcode
    | Number of int

let calculateRpnExpression (exp: Operand list) : Option<int> =
    let rec calculateRpnExpression' exp stack =
        match exp with
        | [] -> Some(List.head stack)
        | Number (n) :: t -> calculateRpnExpression' t (n :: stack)
        | Opcode (op) :: t ->
            match stack with
            | n2 :: n1 :: rest ->
                match op with
                | Add -> calculateRpnExpression' t ((n1 + n2) :: rest)
                | Sub -> calculateRpnExpression' t ((n1 - n2) :: rest)
                | Mul -> calculateRpnExpression' t ((n1 * n2) :: rest)
                | Div ->
                    if n2 = 0 then
                        None
                    else
                        calculateRpnExpression' t ((n1 / n2) :: rest)
            | _ ->
                printfn $"stack=${stack} exp=${exp}"
                failwith "never reach here"

    calculateRpnExpression' exp []

let normalizeRpnExpression (exp: Operand list) : string =
    let rec normalizeRpnExpression' exp stack =
        match exp with
        | [] -> List.head stack
        | Number (n) :: t -> normalizeRpnExpression' t ((string n) :: stack)
        | Opcode (op) :: t ->
            match stack with
            | v2 :: v1 :: rest ->
                match op with
                | Add -> normalizeRpnExpression' t ((sprintf "(%s+%s)" v1 v2) :: rest)
                | Sub -> normalizeRpnExpression' t ((sprintf "(%s-%s)" v1 v2) :: rest)
                | Mul -> normalizeRpnExpression' t ((sprintf "(%s*%s)" v1 v2) :: rest)
                | Div -> normalizeRpnExpression' t ((sprintf "(%s/%s)" v1 v2) :: rest)
            | _ -> failwith "never reach here"

    normalizeRpnExpression' exp []

let createRpnExpression (nums: int list) (target: int) =
    let len = nums |> List.length
    let limit = len * 2 - 1

    let rec createRpnExpression' nums prevNum numCount opCount exp acc =
        if numCount + opCount >= limit then
            let exp' = List.rev exp

            match calculateRpnExpression exp' with
            | None -> acc
            | Some (v) ->
                if v = target then
                    printfn "%A" (normalizeRpnExpression exp')
                    exp' :: acc
                else
                    acc
        else
            let acc' =
                if numCount - opCount >= 2 then
                    let ops =
                        if prevNum = 8 then
                            [ Div ]
                        else
                            [ Add; Sub; Mul; Div ]

                    ops
                    |> List.fold
                        (fun acc' op ->
                            createRpnExpression' nums -1 numCount (opCount + 1) (Opcode(op) :: exp) acc')
                        acc
                else
                    acc

            if prevNum <> 8 && numCount < len then
                let n = List.head nums
                createRpnExpression' (List.tail nums) n (numCount + 1) opCount (Number(n) :: exp) acc'
            else
                acc'

    createRpnExpression' nums -1 0 0 [] []


let quiz2023 (nums: int list) (target: int) : string list =
    let rpnExpressions = createRpnExpression nums target
    rpnExpressions |> List.map normalizeRpnExpression

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

この本に単純な場合のものは載っているので全くわからない人は見ても良いかもしれません。