Practice Code Typing – SkillsTyping

Choose your language:

ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:

Ready

Exercise Algorithm Area

Correct typos to continue.

1(* DSL parser for configuration files with error reporting.
2Supports key-value pairs and sections.
3Uses a simple parser combinator approach with custom error handling.
4*)
5
6module Parser =
7struct
8(* Basic types for configuration data *)
9type value = string
10type key = string
11type section_name = string
12
13(* Represents a parsed configuration entry *)
14type config_entry =
15| KeyValue of key * value
16| Section of section_name * config_entry list
17
18(* Error type *)
19type error =
20| UnexpectedToken of string * string (* Expected, Got *)
21| UnexpectedEOF of string (* Expected *)
22| CustomError of string
23
24(* Result type for parsing operations *)
25type ('a, 'e) result = Ok of 'a | Error of 'e
26
27(* Parser type: takes input string, returns result *)
28type 'a parser = string -> ('a, error) result
29
30(* Helper to combine results *)
31let bind (p : 'a parser) (f : 'a -> 'b parser) : 'b parser =
32fun input ->
33match p input with
34| Error e -> Error e
35| Ok (result, remaining_input) -> f result remaining_input
36
37(* Helper to return a successful result *)
38let return_ (value : 'a) : 'a parser =
39fun input -> Ok (value, input)
40
41(* --- Primitive Parsers --- *)
42
43(* Parses a specific string literal *)
44let literal (s : string) : string parser =
45fun input ->
46if String.is_prefix s input then
47Ok (s, String.drop_prefix (String.length s) input)
48else
49Error (UnexpectedToken (s, if String.length input > 0 then String.sub input 0 10 else "EOF"))
50
51(* Parses a sequence of characters matching a predicate *)
52let take_while (pred : char -> bool) : string parser =
53fun input ->
54let len = String.length input in
55let rec go i =
56if i < len && pred input.[i] then go (i + 1)
57else i
58in
59let count = go 0 in
60if count > 0 then
61Ok (String.sub input 0 count, String.drop_prefix count input)
62else
63Error (UnexpectedToken ("non-empty string", if len > 0 then String.sub input 0 10 else "EOF"))
64
65(* Parses a character that is not in a given set *)
66let not_char (c : char) : char parser =
67fun input ->
68match input with
69| [] -> Error (UnexpectedEOF (Printf.sprintf "character not '%c'" c))
70| hd :: tl ->
71if hd <> c then Ok (hd, tl)
72else Error (UnexpectedToken (Printf.sprintf "character not '%c'" c, String.make 1 hd))
73
74(* Parses a specific character *)
75let char (c : char) : char parser =
76fun input ->
77match input with
78| [] -> Error (UnexpectedEOF (String.make 1 c))
79| hd :: tl ->
80if hd = c then Ok (hd, tl)
81else Error (UnexpectedToken (String.make 1 c, String.make 1 hd))
82
83(* --- Combinators --- *)
84
85(* Sequence: parse p1 then p2 *)
86let seq (p1 : 'a parser) (p2 : 'b parser) : ('a * 'b) parser =
87fun input ->
88match p1 input with
89| Error e -> Error e
90| Ok (res1, rem1) ->
91match p2 rem1 with
92| Error e -> Error e
93| Ok (res2, rem2) -> Ok ((res1, res2), rem2)
94
95(* Choice: try p1, if it fails, try p2 *)
96let choice (p1 : 'a parser) (p2 : 'a parser) : 'a parser =
97fun input ->
98match p1 input with
99| Ok res -> Ok res
100| Error _ -> p2 input
101
102(* Many: parse p zero or more times *)
103let many (p : 'a parser) : 'a list parser =
104fun input ->
105let rec loop acc current_input =
106match p current_input with
107| Ok (res, next_input) -> loop (res :: acc) next_input
108| Error _ -> Ok (List.rev acc, current_input)
109in
110loop [] input
111
112(* Many1: parse p one or more times *)
113let many1 (p : 'a parser) : 'a list parser =
114fun input ->
115match p input with
116| Error e -> Error e
117| Ok (res, rem) ->
118let (res_list, final_rem) = (many p) rem in
119Ok (res :: res_list, final_rem)
120
121(* Skip whitespace *)
122let skip_whitespace : unit parser =
123let is_whitespace c = c = ' ' || c = '\t' || c = '\n' || c = '\r' in
124let _ = many (take_while is_whitespace) in
125fun input -> Ok ((), input) (* Always succeeds, consumes whitespace *)
126
127(* --- Grammar Parsers --- *)
128
129(* Parses a key: alphanumeric characters *)
130let parse_key : key parser =
131let is_key_char c = Char.is_alphanumeric c in
132let _ = skip_whitespace in
133bind (take_while is_key_char) (fun k -> return_ k)
134
135(* Parses a value: anything until newline or end of string *)
136let parse_value : value parser =
137let is_value_char c = c <> '\n' && c <> '\r' in
138let _ = skip_whitespace in
139bind (take_while is_value_char) (fun v -> return_ v)
140
141(* Parses a key-value pair: key = value *)
142let parse_key_value : config_entry parser =
143fun input ->
144match seq parse_key (literal "=") input with
145| Error e -> Error e
146| Ok (key, rem1) ->
147match parse_value rem1 with
148| Error e -> Error e
149| Ok (value, rem2) ->
150let _ = skip_whitespace in (* Consume trailing whitespace/newline *)
151Ok (KeyValue (key, value), rem2)
152
153(* Parses a section: [section_name] *)
154let parse_section_header : section_name parser =
155fun input ->
156match seq (char '[') (take_while (fun c -> c <> ']')) input with
157| Error e -> Error e
158| Ok (_, (name, rem1)) ->
159match char ']' rem1 with
160| Error e -> Error e
161| Ok (_, rem2) -> Ok (name, rem2)
162
163(* Parses the content of a section: key-value pairs or nested sections *)
164let rec parse_section_content : config_entry list parser =
165fun input ->
166let rec loop acc current_input =
167match skip_whitespace current_input with
168| Error e -> Error e (* Should not happen if skip_whitespace is correct *)
169| Ok (_, rem_ws) ->
170match parse_section_header rem_ws with
171| Ok (section_name, rem_sec) ->
172match parse_section_content rem_sec with
173| Error e -> Error e
174| Ok (entries, rem_final) ->
175loop (Section (section_name, entries) :: acc) rem_final
176| Error _ -> (* Not a section, try key-value pair *)
177match parse_key_value rem_ws with
178| Ok (kv_entry, rem_kv) -> loop (kv_entry :: acc) rem_kv
179| Error _ -> (* If it's not a section or KV, it might be end of section or error *)
180if String.length rem_ws = 0 || String.is_prefix "[" rem_ws then
181Ok (List.rev acc, current_input) (* End of section or EOF *)
182else
183Error (CustomError "Expected key-value pair or section header")
184in
185loop [] input
186
187(* Parses the entire configuration file *)
188let parse_config : config_entry list parser =
189fun input ->
190let rec loop acc current_input =
191match skip_whitespace current_input with
192| Error e -> Error e
193| Ok (_, rem_ws) ->
194match parse_section_header rem_ws with
195| Ok (section_name, rem_sec) ->
196match parse_section_content rem_sec with
197| Error e -> Error e
198| Ok (entries, rem_final) ->
199loop (Section (section_name, entries) :: acc) rem_final
200| Error _ -> (* Not a section, try key-value pair *)
201match parse_key_value rem_ws with
202| Ok (kv_entry, rem_kv) -> loop (kv_entry :: acc) rem_kv
203| Error _ -> (* If it's not a section or KV, it might be end of file or error *)
204if String.length rem_ws = 0 then
205Ok (List.rev acc, "") (* End of file *)
206else
207Error (CustomError "Expected key-value pair or section header")
208in
209loop [] input
210
211(* --- Public API --- *)
212let parse (config_string : string) : (config_entry list, error) result =
213parse_config config_string
214
215end
216
217(* Example usage:
218let config_str = "[Database]\n  host = localhost\n  port = 5432\n\n[Server]\n  timeout = 30\n"
219match Parser.parse config_str with
220| Ok entries -> List.iter (fun e -> Printf.printf "%A\n" e) entries
221| Error err -> Printf.printf "Error: %A\n" err
222*)

Algorithm description viewbox

OCaml DSL Pattern: Configuration Parser with Error Combinators

Algorithm description:

This OCaml code implements a parser for a simple configuration file DSL using a combinator-style approach. It defines parsers for basic elements like keys, values, and section headers, and combines them to parse the overall structure. Crucially, it incorporates error handling using a custom `result` type and specific `error` constructors, providing informative messages for syntax errors. This DSL pattern is widely used for creating flexible and readable configuration systems, scripting languages, and query interfaces, where clear error reporting is essential for user experience.

Algorithm explanation:

The parser is built using a set of primitive parsers (e.g., `literal`, `take_while`, `char`) and combinators (`seq`, `choice`, `many`, `many1`) that build more complex parsers. Each parser takes an input string and returns a `result` type: either `Ok (parsed_value, remaining_input)` or `Error error_details`. The `error` type includes specific messages like `UnexpectedToken` and `UnexpectedEOF`, aiding in debugging. The `parse_config` function orchestrates the parsing of sections and key-value pairs. The `skip_whitespace` parser is used throughout to ignore irrelevant characters. The time complexity is roughly O(N*M) in the worst case for naive combinators, where N is the input length and M is the number of parsers, but with optimizations and careful design, it approaches O(N). Space complexity is O(N) for intermediate string manipulations and the resulting AST. Edge cases include empty input, malformed keys/values, missing delimiters, and incorrect section nesting.

Pseudocode:

define result = Ok(value, remaining_input) | Error(error_details)
define error = UnexpectedToken(expected, got) | UnexpectedEOF(expected) | CustomError(message)
define parser = input_string -> result

// Primitive parsers
function literal(s): returns parser that matches string s
function take_while(predicate): returns parser that matches chars satisfying predicate
function char(c): returns parser that matches character c

// Combinators
function seq(p1, p2): returns parser that runs p1 then p2, returning (res1, res2)
function choice(p1, p2): returns parser that tries p1, then p2 if p1 fails
function many(p): returns parser that runs p zero or more times, returning list
function many1(p): returns parser that runs p one or more times, returning list

// Grammar parsers
function skip_whitespace(): consumes whitespace
function parse_key(): parses an alphanumeric key
function parse_value(): parses a value until newline
function parse_key_value(): parses "key = value"
function parse_section_header(): parses "[section_name]"
function parse_section_content(): parses list of entries within a section
function parse_config(): parses the entire configuration file

function parse(config_string):
  return parse_config(config_string)

Library

Playable exercises

Choose Exercise

Filter, sort, and preview algorithm before you choose one to play.

Total 6 published items

Pages 1 pages available

Language

Sort by Direction

Browse published coding scenarios with filters, sorting, and pagination.

Published

OCaml Functional (ocaml)

OCaml: Binary Search Tree Insertion (Recursive)

Difficulty: writing: 9; length: 8
Popularity: 0
Created: 2026-01-26 14:00 UTC
Published: 2026-01-26 16:41 UTC
Author: Damian

#binary search tree #recursion #data structures #trees #OCaml #immutable data

goal: Implement recursive insertion into a Binary Search Tree. input: An integer value to insert and a BST of integers. output: A new BST with the value inserted, or the original BST if the value already exists.

Canonical Algorithm Text

(* OCaml implementation of Binary Search Tree (BST) insertion using recursion. *) (* Define the structure for a BST node. *) type 'a bst_node = | Empty | Node of 'a * 'a bst_node * 'a bst_node (* Helper function to create a new node. *) let create_node value left right = Node (va...

Description Algorithm

This OCaml code defines and implements insertion into a Binary Search Tree (BST) using a recursive approach. A BST is a data structure where each node has at most two children, referred to as the left child and the right...

Explanation

The provided OCaml code implements recursive insertion into a Binary Search Tree (BST). The `bst_node` type is defined as either `Empty` or a `Node` containing a value and two child BSTs. The `insert` function takes a value and a tree, returning a new tree with the value inserted. The base case for the recursion is when the tree is `Empty`; in this scenario, a new `Node` is created with the given value and two `Empty` children. For a non-empty `Node`, the function compares the `value` to be inserted with the `node_value`. If `value` is smaller, it recursively calls `insert` on the `left` subtree. If `value` is larger, it recursively calls `insert` on the `right` subtree. If `value` is equal to `node_value`, the tree remains unchanged to ensure unique values. The `create_node` helper constructs a new node, ensuring immutability by returning a new tree structure rather than modifying existing nodes. The time complexity for insertion in a balanced BST is O(log n), where n is the number of nodes. However, in the worst case (a skewed tree), it can degrade to O(n). The space complexity is O(log n) for a balanced tree due to the recursion stack, and O(n) for a skewed tree. Edge cases like inserting into an empty tree, inserting smaller/larger values than existing ones, and handling duplicates are addressed.

Pseudocode

type bst_node: Empty Node(value, left_child, right_child) function insert(value, tree): if tree is Empty: return Node(value, Empty, Empty) else: node_value = tree.value left_child = tree.left_child right_child = tree.rig...

Published

OCaml Functional (ocaml)

OCaml Immutable Graph: Depth-First Search for Cycle Detection

Difficulty: writing: 10; length: 7
Popularity: 0
Created: 2026-01-26 12:32 UTC
Published: 2026-01-26 13:42 UTC
Author: Admin

#graph #dfs #cycle detection #immutable #ocaml #algorithms

goal: Detect cycles in a directed graph. input: An immutable directed graph represented as an adjacency list (Hashtbl). output: A boolean indicating whether a cycle exists.

Canonical Algorithm Text

(* Immutable directed graph cycle detection using DFS. Graph represented as an adjacency list: Map from node ID to list of neighbor IDs. Uses three states for nodes during DFS: Unvisited, Visiting, Visited. *) module Graph = struct type node_id = int type graph = (node_id, node_i...

Description Algorithm

This OCaml code implements a Depth-First Search (DFS) algorithm to detect cycles in a directed graph. The graph is represented immutably using an adjacency list (a Hashtbl mapping node IDs to lists of neighbor IDs). The...

Explanation

The `dfs` function performs the core traversal. It marks a node as `Visiting` upon entry. For each neighbor, it checks its state: if `Visiting`, a cycle is found. If `Unvisited` (or not yet in the `visited_states` map, implying `Unvisited`), it recursively calls `dfs`. If a neighbor is `Visited`, it's ignored. Upon returning from all neighbor explorations, the node is marked `Visited`. The `has_cycle` function iterates through all nodes, initiating DFS from any `Unvisited` node to handle disconnected components. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is visited at most once. The space complexity is O(V) for storing the `visited_states` and the recursion stack. Edge cases include empty graphs, graphs with no edges, and graphs with multiple disconnected components.

Pseudocode

function has_cycle(graph): visited_states = map of node -> state (Unvisited, Visiting, Visited) initialize all nodes in graph to Unvisited for each node in graph: if node is Unvisited: if dfs(graph, node, visited_states)...

Published

OCaml Functional (ocaml)

OCaml Functional Parser for Simple Arithmetic Expressions

Difficulty: writing: 1; length: 9
Popularity: 0
Created: 2026-01-26 12:32 UTC
Published: 2026-01-26 13:42 UTC
Author: Admin

#parser #recursive descent #ast #functional #ocaml #lexer

goal: Parse arithmetic expressions into an AST. input: A string representing an arithmetic expression. output: An abstract syntax tree (AST) of type Parser.expr.

Canonical Algorithm Text

(* Parser for simple arithmetic expressions. Supports +, -, *, /, parentheses, and integers. Handles operator precedence and associativity. Uses a lexer to tokenize the input string. *) module Lexer = struct type token = | Int of int | Add | Sub | Mul | Div | LParen | RParen | Eo...

Description Algorithm

This OCaml code implements a recursive descent parser for arithmetic expressions. It first tokenizes the input string using a simple lexer, then constructs an abstract syntax tree (AST) representing the expression. This...

Explanation

The parser uses a top-down, recursive descent approach. The `parse_expr` function initiates the parsing process, delegating to `parse_add_sub` to handle addition and subtraction, which have lower precedence. `parse_add_sub` in turn calls `parse_mul_div` for multiplication and division, and `parse_mul_div` calls `parse_atom` for the most basic elements like numbers and parenthesized sub-expressions. This structure naturally enforces operator precedence. Associativity is handled by the recursive calls within `parse_add_sub_cont` and `parse_mul_div_cont`, which allow for sequences of the same-precedence operators. Error handling is included for malformed input, such as mismatched parentheses or unexpected tokens. The time complexity is O(N) where N is the number of tokens, as each token is processed a constant number of times. The space complexity is O(N) in the worst case due to the recursion depth and the AST construction.

Pseudocode

function parse(tokens): result, remaining = parse_expression(tokens) if remaining contains only EOF: return result else: raise ParseError("Unexpected tokens") function parse_expression(tokens): left, tokens' = parse_add_...

Published

OCaml Functional (ocaml)

OCaml Pattern Matching State Machine for Simple Vending Machine

Difficulty: writing: 9; length: 10
Popularity: 0
Created: 2026-01-26 12:32 UTC
Published: 2026-01-26 13:42 UTC
Author: Admin

#state machine #pattern matching #ocaml #modeling #adt

goal: Model a vending machine's behavior using a state machine. input: An initial state and a list of user inputs. output: The final state of the vending machine after processing all inputs.

Canonical Algorithm Text

(* State machine for a simple vending machine using pattern matching. States: Idle, HasCoin, Dispensing. Inputs: InsertCoin, SelectProduct, Cancel. Products: Soda (price 100), Chips (price 75). *) type coin_value = int type product_id = string (* States of the vending machine *)...

Description Algorithm

This OCaml code defines a state machine for a simple vending machine using algebraic data types and pattern matching. The machine has states like 'Idle', 'HasCoin', and 'Dispensing', and transitions based on inputs like...

Explanation

The state machine is implemented using OCaml's powerful pattern matching on algebraic data types. The `state` type enumerates all possible configurations of the machine, and the `input` type defines all valid user interactions. The `process_input` function is the core transition logic: it takes the current state and an input, and returns the next state. Each `match` clause covers a specific `(current_state, input)` combination, defining the resulting state and any side effects (though this example focuses purely on state transitions). The use of `HasCoin of coin_value` and `Dispensing of product_id * coin_value` allows the state itself to carry context. The `simulate_vending_machine` function applies a list of inputs sequentially. The time complexity is O(N) where N is the number of inputs, as each input is processed in constant time. Space complexity is O(1) for the state itself, plus O(N) for the input list. Edge cases include invalid coin amounts, insufficient funds, and invalid product selections, all handled by specific pattern matches.

Pseudocode

define state = Idle | HasCoin(amount) | Dispensing(product, change) define input = InsertCoin(amount) | SelectProduct(product_id) | Cancel function process_input(current_state, input): case (current_state, input) of: (Id...

Published

OCaml Functional (ocaml)

OCaml Immutable Graph: Breadth-First Search for Shortest Path (Unweighted)

Difficulty: writing: 8; length: 9
Popularity: 0
Created: 2026-01-26 12:32 UTC
Published: 2026-01-26 13:42 UTC
Author: Admin

#graph #bfs #shortest path #immutable #ocaml #algorithms

goal: Find the shortest path in an unweighted graph. input: An immutable graph (adjacency list), a source node, and a target node. output: An option containing a list of node IDs representing the shortest path, or None if no path exists.

Canonical Algorithm Text

(* Immutable graph BFS for shortest path in an unweighted graph. Graph represented as an adjacency list: Map from node ID to list of neighbor IDs. Finds the shortest path (number of edges) from a source to a target node. *) module Graph = struct type node_id = int type graph = (n...

Description Algorithm

This OCaml code implements Breadth-First Search (BFS) to find the shortest path in an unweighted directed graph. The graph is represented using an adjacency list. BFS explores the graph level by level, guaranteeing that...

Explanation

The `shortest_path` function initializes a queue, a `distances` map (all nodes to -1, source to 0), and a `predecessors` map. The BFS loop dequeues a node, explores its unvisited neighbors, updates their distances (current_dist + 1), records their predecessor, and enqueues them. This process continues until the queue is empty. If the target's distance is still -1, it's unreachable. Otherwise, the path is reconstructed by backtracking from the target using the `predecessors` map. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is processed at most once. The space complexity is O(V) for the queue, distances, and predecessors. Edge cases include the source and target being the same, the target being unreachable, and the source or target not existing in the graph.

Pseudocode

function shortest_path(graph, source, target): queue = empty queue distances = map of node -> distance (initialize all to -1) predecessors = map of node -> predecessor if source not in graph or target not in graph: retur...

Published

OCaml Functional (ocaml)

OCaml DSL Pattern: Configuration Parser with Error Combinators

Difficulty: writing: 2; length: 10
Popularity: 0
Created: 2026-01-26 12:32 UTC
Published: 2026-01-26 13:42 UTC
Author: Admin

#dsl #parser #combinators #error handling #ocaml #configuration

goal: Parse a configuration file into a structured list of entries. input: A string representing the configuration file content. output: A result type: either Ok(list of config_entry, "") or Error(error).

Canonical Algorithm Text

(* DSL parser for configuration files with error reporting. Supports key-value pairs and sections. Uses a simple parser combinator approach with custom error handling. *) module Parser = struct (* Basic types for configuration data *) type value = string type key = string type se...

Description Algorithm

This OCaml code implements a parser for a simple configuration file DSL using a combinator-style approach. It defines parsers for basic elements like keys, values, and section headers, and combines them to parse the over...

Explanation

The parser is built using a set of primitive parsers (e.g., `literal`, `take_while`, `char`) and combinators (`seq`, `choice`, `many`, `many1`) that build more complex parsers. Each parser takes an input string and returns a `result` type: either `Ok (parsed_value, remaining_input)` or `Error error_details`. The `error` type includes specific messages like `UnexpectedToken` and `UnexpectedEOF`, aiding in debugging. The `parse_config` function orchestrates the parsing of sections and key-value pairs. The `skip_whitespace` parser is used throughout to ignore irrelevant characters. The time complexity is roughly O(N*M) in the worst case for naive combinators, where N is the input length and M is the number of parsers, but with optimizations and careful design, it approaches O(N). Space complexity is O(N) for intermediate string manipulations and the resulting AST. Edge cases include empty input, malformed keys/values, missing delimiters, and incorrect section nesting.

Pseudocode

define result = Ok(value, remaining_input) | Error(error_details) define error = UnexpectedToken(expected, got) | UnexpectedEOF(expected) | CustomError(message) define parser = input_string -> result // Primitive parsers...

Language (required)

Paste your code (required)

Max 20,000 characters. (Dangerous HTML/script fragments will be blocked)

Normalized preview:

I agree to Publish this, after admin approval (queued for review). (Not required) I confirm this submission is anonymous and does not contain personal data. I grant SkillsTyping a free, non-exclusive, worldwide, and irrevocable license to store, modify, adapt, and publish this content after review. I understand that publication is not guaranteed, that I retain no ownership or usage claims over published versions, and that no compensation will be provided. See Privacy Policy

Publish details

Shown only if you opt to submit for review. Required when consent is checked.

Title (required with consent)

Short description / summary (required with consent)

Algorithm explanation (required with consent)

Pseudocode (required with consent)