Last active
March 27, 2022 21:31
-
-
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/)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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