tokenize.fsx

type Token = Text of string | Number of int | LeftBracket | RightBracket

let tokenize (compressed:string) : Token list =
    let folder tokens c =
        match c with
        | '[' -> LeftBracket :: tokens
        | ']' -> RightBracket :: tokens
        | _ when System.Char.IsDigit c -> 
            let digit = c |> string |> int
            match tokens with
            | (Number n :: rest) -> (Number (10*n+digit)) :: rest
            | _ -> Number digit :: tokens
        | _ ->
            let c = c |> string
            match tokens with
            | (Text s :: rest) -> Text (s+c) :: rest
            | _ -> Text c :: tokens

    compressed.ToCharArray() |> Array.toList |> List.fold folder [] |> List.rev

type SolutionState =
    | Basic 
    | Multiplier of int

type PartialSolution = {
    message : string;
    state : SolutionState;
    parent: PartialSolution option;
}

let solveTokens (tokens: Token list) =
    let folder solution token =
        match token with
        | Text s -> { solution with message = solution.message + s}
        | Number n ->
            match solution.state with
            | Basic -> { solution with state = Multiplier n}
            | _ -> failwith "illegal number"
        | LeftBracket ->
            match solution.state with
            | Multiplier n -> { message = ""; state = Basic; parent = Some solution}
            | _ -> failwith "illegal left bracket"
        | RightBracket ->
            match (solution.state, solution.parent) with
            | (Basic, Some parent) ->
                match parent.state with
                | Multiplier n ->
                    let replicated = solution.message |> String.replicate n
                    {parent with message = parent.message + replicated; state = Basic}
                | _ -> failwith "unexpected"
            | _ -> failwith "illegal right bracket"

    let empty = { message = ""; state = Basic; parent = None }
    let solution = tokens |> List.fold folder empty
    match solution.state, solution.parent with
    | Basic, None -> solution.message
    | _ -> failwith "invalid input"

let solve = tokenize >> solveTokens