Skip to content

Instantly share code, notes, and snippets.

@ebresafegaga
Last active March 27, 2022 21:31
Show Gist options
  • Save ebresafegaga/b5732833e7fe45187bf187acfc428784 to your computer and use it in GitHub Desktop.
Save ebresafegaga/b5732833e7fe45187bf187acfc428784 to your computer and use it in GitHub Desktop.
Excel Formula Leetcode problem in OCaml (https://leetcode.com/problems/design-excel-sum-formula/)
let rec range start stop = if start > stop then [] else start :: range (succ start) stop
let sum xs = List.fold_left (+) 0 xs
let (>>) f g a = a |> f |> g
module type Excel = sig
type t
val create: int -> char -> unit
val set: int -> char -> int -> unit
val get: int -> char -> int
val sum: int -> char -> string list -> int
end
module NaiveExcel () : Excel = struct
type cell = int * char
type range = cell * cell
type content = Number of int | Sum of range list
type t = content array array
let ci c = int_of_char c + 1 - int_of_char 'A' (* ci, as in, column index *)
let get_range ((sr, sc),(lr, lc)) =
let sc,lc = ci sc, ci lc in
range sr lr
|> List.concat_map (fun row ->
range sc lc
|> List.map (fun col -> row, col))
(* A range can be a single cell (e.g A1)
or two cells seperated by a ':' (e.g A1:C3) *)
let parse_range ur =
let parse_cell single =
match Str.split (Str.regexp "") single with
| [col;row] -> int_of_string row, col.[0]
| _ -> failwith "Range parse error"
in
match String.split_on_char ':' ur with
| [start;finish] -> parse_cell start, parse_cell finish
| [single] -> let c = parse_cell single in c, c
| _ -> failwith "Range parse error"
let state : t ref = ref [||]
let update st = state := st
let updateIndex (y, x) value = !state.(y-1).(x-1) <- value
let index (x, y) = !state.(y-1).(x-1)
let create height width =
let width = ci width in
let t = Array.init height (fun _ -> Array.init width (fun _ -> Number 0)) in
update t
let set row column value = updateIndex (row, ci column) (Number value)
let rec evaluate (expr : content) : int =
match expr with
| Number n -> n
| Sum ranges -> List.fold_right (get_range >> List.map (index >> evaluate) >> sum >> (+)) ranges 0
let get row column = evaluate (index (row, ci column))
let sum row column urs =
let ranges = List.map parse_range urs in
updateIndex (row, ci column) (Sum ranges) ;
get row column
end
let () =
let module E = NaiveExcel () in
E.create 3 'C' ;
E.set 1 'A' 2 ;
let _ = E.sum 3 'C' ["A1"; "A1:B2"] in
E.set 2 'B' 2 ;
let result = E.get 3 'C' in
Printf.printf "C3 = %d" result
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment