alphabet_soup.c File Reference

Word search puzzle solver implementation with NASA Power-of-10 safety guarantees. More...

#include "alphabet_soup.h"
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include "ra8_attributes.h"
#include "ra8_err.h"
#include "ra8_io_stream.h"

Include dependency graph for alphabet_soup.c:

Go to the source code of this file.

Data Structures
struct	soup_dir_t
	Direction vector for 2D grid navigation. More...

Enumerations
enum	soup_numeric_constants_t : uint32_t {   k_decimal_base = 10U ,   k_decimal_overflow_cap = 429496729U }
	Numeric constants for parsing and search navigation. More...

Functions
ra8_err_t	soup_init (soup_context_t *ctx)
	Initialize a caller-owned puzzle solver context.
static bool	internal_match_ray (const soup_grid_t *grid, const char *key, int32_t span, int32_t r, int32_t c, soup_dir_t dir)
	Match word characters along a single directional ray.
static bool	internal_check_cell (const soup_grid_t *grid, const char *key, int32_t span, int32_t r, int32_t c, uint32_t *out_end_row, uint32_t *out_end_col)
	Check all directions starting at a specific cell.
bool	soup_find_word (const soup_grid_t *grid, const char *search_key, uint32_t key_len, uint32_t *out_start_row, uint32_t *out_start_col, uint32_t *out_end_row, uint32_t *out_end_col)
	Search a grid for a normalized word along all 8 compass directions.
static ra8_err_t	internal_parse_uint32 (const char **text_ptr, const char *text_end, uint32_t *out_val)
	Parse a positive decimal integer with overflow detection.
static ra8_err_t	internal_parse_dimensions (const char **text_ptr, const char *text_end, uint32_t *out_rows, uint32_t *out_cols)
	Parse board header dimensions and validate against capacity limits.
static ra8_err_t	internal_parse_single_row (const char **text_ptr, const char *text_end, char *row_cells, uint32_t expected_cols)
	Parse a single grid row into grid cells with eager validation.
static ra8_err_t	internal_parse_grid (const char **text_ptr, const char *text_end, soup_grid_t *grid)
	Parse complete grid character matrix from text stream.
static void	internal_emit_match (ra8_io_stream_t *out_stream, const char *word, uint32_t start_row, uint32_t start_col, uint32_t end_row, uint32_t end_col)
	Emit single solved word result line to the stream.
static void	internal_parse_word_entry (const char **text_ptr, const char *text_end, char *word, size_t word_cap, char *search_key, size_t key_cap, uint32_t *out_search_len)
	Parse one target word line into word and search key buffers.
static ra8_err_t	internal_solve_words (soup_context_t *ctx, const char *ptr, const char *text_end, ra8_io_stream_t *out_stream)
	Solve all words following the grid in the text buffer.
ra8_err_t	soup_solve (soup_context_t *ctx, const char *text, uint32_t text_len, ra8_io_stream_t *out_stream)
	Parse board and words from puzzle text and emit solutions to the output stream.

Detailed Description

Word search puzzle solver implementation with NASA Power-of-10 safety guarantees.

Tag

[Ring 4 / App] {World: Host}

Implements bounded grid parsing, space-stripped search key normalization, and 8-way directional ray matching within caller-owned context memory. Every loop enforces static iteration bounds, every parameter is bounds-checked, and stack frames remain minimal (< 256 bytes).

Copyright

Copyright (c) 2026 Brighton Sikarskie SPDX-License-Identifier: MIT

Since

0.1.0

Definition in file alphabet_soup.c.

Enumeration Type Documentation

soup_numeric_constants_t

enum soup_numeric_constants_t : uint32_t

Numeric constants for parsing and search navigation.

Enumerator
k_decimal_base	Base 10 decimal multiplier.
k_decimal_overflow_cap	(UINT32_MAX - 9) / 10 threshold.

Definition at line 37 of file alphabet_soup.c.

Function Documentation

internal_check_cell()

bool internal_check_cell ( const soup_grid_t * grid, const char * key, int32_t span, int32_t r, int32_t c, uint32_t * out_end_row, uint32_t * out_end_col )

static

Check all directions starting at a specific cell.

Iterates through all 8 compass search directions starting from (r, c). Upon finding a complete match, populates out_end_row and out_end_col.

Parameters

[in]	grid	Board state.
[in]	key	Target characters.
[in]	span	Ray length minus 1.
[in]	r	Start row.
[in]	c	Start column.
[out]	out_end_row	End row.
[out]	out_end_col	End col.

Returns

bool True if word matched from this cell.

Return values

true	A matching ray was found in one of the 8 directions.
false	No matching ray found from this cell.

Precondition

grid, key, out_end_row, out_end_col are non-null.

(r, c) coordinates are within grid bounds.

Postcondition

Output coordinates are updated if match is found.

Grid state is preserved.

Note

Helper function.

Since

0.1.0

Direction delta lookup table for 8-way word search.

< East

< South-East

< South

< South-West

< West

< North-West

< North

< North-East

Definition at line 129 of file alphabet_soup.c.

References soup_dir_t::delta_col, soup_dir_t::delta_row, internal_match_ray(), k_soup_direction_count, and RA8_INTERNAL.

Referenced by soup_find_word().

internal_emit_match()

void internal_emit_match ( ra8_io_stream_t * out_stream, const char * word, uint32_t start_row, uint32_t start_col, uint32_t end_row, uint32_t end_col )

static

Emit single solved word result line to the stream.

Formats and writes the output string "<WORD> <START_ROW>:<START_COL> <END_ROW>:<END_COL>\n" into the provided I/O stream.

Parameters

[in,out]	out_stream	Bound destination stream.
[in]	word	Original word text.
[in]	start_row	Start row.
[in]	start_col	Start col.
[in]	end_row	End row.
[in]	end_col	End col.

Precondition

out_stream and word are non-null.

Coordinates are valid non-negative integers.

Postcondition

Line is written to out_stream.

Stream state reflects appended bytes.

Note

Helper function.

Since

0.1.0

Definition at line 433 of file alphabet_soup.c.

References RA8_INTERNAL, ra8_io_stream_put_u32(), ra8_io_stream_putc(), and ra8_io_stream_puts().

Referenced by internal_solve_words().

internal_match_ray()

bool internal_match_ray ( const soup_grid_t * grid, const char * key, int32_t span, int32_t r, int32_t c, soup_dir_t dir )

static

Match word characters along a single directional ray.

Validates the ray endpoint bounds against the grid boundaries, then checks each cell along the ray direction up to the specified span length.

Parameters

[in]	grid	Board state.
[in]	key	Target characters.
[in]	span	Ray length minus 1.
[in]	r	Start row.
[in]	c	Start column.
[in]	dir	Direction vector.

Returns

bool True if all characters along ray match.

Return values

true	All characters match along the ray.
false	One or more characters mismatch or ray exits grid.

Precondition

grid and key are non-null.

span is non-negative and within grid bounds.

Postcondition

Grid memory is unmodified.

Scan terminates within span steps.

Note

Helper function with strict bounded loop.

Since

0.1.0

Definition at line 76 of file alphabet_soup.c.

References soup_grid_t::cells, soup_grid_t::col_count, soup_dir_t::delta_col, soup_dir_t::delta_row, RA8_INTERNAL, and soup_grid_t::row_count.

Referenced by internal_check_cell().

internal_parse_dimensions()

ra8_err_t internal_parse_dimensions ( const char ** text_ptr, const char * text_end, uint32_t * out_rows, uint32_t * out_cols )

static

Parse board header dimensions and validate against capacity limits.

Parses the "RxC" dimension prefix, validates row and column counts against maximum grid dimensions, and advances the cursor to the first row of cells.

Parameters

[in,out]	text_ptr	In-out pointer to current parse position.
[in]	text_end	End of text buffer.
[out]	out_rows	Number of rows parsed.
[out]	out_cols	Number of columns parsed.

Returns

ra8_err_t Error code.

Return values

k_ra8_ok	Dimensions successfully parsed and within bounds.
k_ra8_err_invalid_arg	Format was not "RxC" with decimal numbers.
k_ra8_err_range_check_failed	Row or column count exceeded limits.

Precondition

text_ptr, text_end, out_rows, out_cols are non-null.

*text_ptr points to the start of the grid header line.

Postcondition

*text_ptr points to the first byte after the header line.

Output dimensions are within [1, k_soup_max_grid_rows/cols].

Note

Helper function.

Since

0.1.0

Definition at line 275 of file alphabet_soup.c.

References internal_parse_uint32(), k_ra8_err_invalid_arg, k_ra8_err_range_check_failed, k_ra8_ok, k_soup_max_grid_cols, k_soup_max_grid_rows, k_soup_max_line_steps, and RA8_INTERNAL.

Referenced by soup_solve().

internal_parse_grid()

ra8_err_t internal_parse_grid ( const char ** text_ptr, const char * text_end, soup_grid_t * grid )

static

Parse complete grid character matrix from text stream.

Loops over each row index in the grid structure, calling internal_parse_single_row to populate every cell in sequence.

Parameters

[in,out]	text_ptr	In-out pointer to current parse position.
[in]	text_end	End of text buffer.
[out]	grid	Grid structure to populate.

Returns

ra8_err_t Status of parsing.

Return values

k_ra8_ok	Entire grid matrix parsed successfully.
k_ra8_err_invalid_size	A row had incorrect column count.

Precondition

text_ptr, text_end, grid are non-null.

grid->row_count and grid->col_count are pre-populated.

Postcondition

*text_ptr points to the character following the grid rows.

grid->cells is fully populated on success.

Note

Helper function.

Since

0.1.0

Definition at line 401 of file alphabet_soup.c.

References soup_grid_t::cells, soup_grid_t::col_count, internal_parse_single_row(), k_ra8_ok, and soup_grid_t::row_count.

Referenced by soup_solve().

internal_parse_single_row()

ra8_err_t internal_parse_single_row ( const char ** text_ptr, const char * text_end, char * row_cells, uint32_t expected_cols )

static

Parse a single grid row into grid cells with eager validation.

Reads space-separated non-whitespace characters for one row into the row buffer, verifying that the column count exactly matches expected_cols.

Parameters

[in,out]	text_ptr	Pointer to parse position.
[in]	text_end	End of text buffer.
[out]	row_cells	Array of cells for current row.
[in]	expected_cols	Number of columns required.

Returns

ra8_err_t Error status.

Return values

k_ra8_ok	Exactly expected_cols were parsed for this row.
k_ra8_err_invalid_size	Too few or too many columns found.

Precondition

text_ptr, text_end, row_cells are non-null.

expected_cols > 0 and <= k_soup_max_grid_cols.

Postcondition

*text_ptr points to the beginning of the next line.

row_cells contains expected_cols valid characters on success.

Note

Helper function with NASA Rule 2 bounded loop and eager failure on column surplus.

Since

0.1.0

Definition at line 341 of file alphabet_soup.c.

References k_ra8_err_invalid_size, k_ra8_ok, k_soup_max_line_steps, and RA8_INTERNAL.

Referenced by internal_parse_grid().

internal_parse_uint32()

ra8_err_t internal_parse_uint32 ( const char ** text_ptr, const char * text_end, uint32_t * out_val )

static

Parse a positive decimal integer with overflow detection.

Accumulates base-10 digits from the stream buffer until reaching a non-digit or hitting the digit count limit, failing if arithmetic overflow occurs.

Parameters

[in,out]	text_ptr	Stream pointer.
[in]	text_end	End of text buffer.
[out]	out_val	Destination for parsed integer.

Returns

ra8_err_t Error status.

Return values

k_ra8_ok	Integer parsed successfully.
k_ra8_err_invalid_arg	No digits found at cursor.
k_ra8_err_range_check_failed	Arithmetic overflow encountered.

Precondition

text_ptr, text_end, out_val are non-null.

*text_ptr is within [text_ptr, text_end).

Postcondition

*text_ptr advances past all parsed digits.

*out_val contains the parsed value on success.

Note

NASA P10 Rule 2 bounded loop.

Since

0.1.0

Definition at line 223 of file alphabet_soup.c.

References k_decimal_base, k_decimal_overflow_cap, k_ra8_err_invalid_arg, k_ra8_err_range_check_failed, k_ra8_ok, and k_soup_max_dim_digits.

Referenced by internal_parse_dimensions().

internal_parse_word_entry()

void internal_parse_word_entry ( const char ** text_ptr, const char * text_end, char * word, size_t word_cap, char * search_key, size_t key_cap, uint32_t * out_search_len )

static

Parse one target word line into word and search key buffers.

Reads the raw word text preserving spaces into the word buffer, and extracts a space-stripped uppercase key into the search_key buffer.

Parameters

[in,out]	text_ptr	Current stream pointer.
[in]	text_end	End of text buffer.
[out]	word	Original word string.
[in]	word_cap	Word buffer capacity.
[out]	search_key	Normalized word string.
[in]	key_cap	Search key buffer capacity.
[out]	out_search_len	Output search key length.

Precondition

text_ptr, text_end, word, search_key, out_search_len are non-null.

word_cap and key_cap are greater than 0.

Postcondition

*text_ptr advances to the start of the next line.

*out_search_len contains the normalized key character count.

Note

Helper function with NASA Rule 2 bounded loop.

Since

0.1.0

Definition at line 474 of file alphabet_soup.c.

References k_soup_max_line_steps, and RA8_INTERNAL.

Referenced by internal_solve_words().

internal_solve_words()

ra8_err_t internal_solve_words ( soup_context_t * ctx, const char * ptr, const char * text_end, ra8_io_stream_t * out_stream )

static

Solve all words following the grid in the text buffer.

Iterates through each remaining line of target words, searching for matches across the pre-parsed grid and streaming match results.

Parameters

[in,out]	ctx	Solver context.
[in]	ptr	Text stream cursor at word list.
[in]	text_end	End of text buffer.
[in,out]	out_stream	Output stream.

Returns

ra8_err_t Error code.

Return values

k_ra8_ok	All words solved and output flushed.
other	Stream flush error status.

Precondition

ctx, ptr, text_end, out_stream are non-null.

ctx->grid contains valid parsed puzzle grid.

Postcondition

Matching word coordinates are emitted to out_stream.

Out stream is flushed before return.

Note

Helper function.

Since

0.1.0

Definition at line 537 of file alphabet_soup.c.

References soup_context_t::grid, internal_emit_match(), internal_parse_word_entry(), k_soup_max_parse_steps, memset(), RA8_INTERNAL, ra8_io_stream_flush(), soup_context_t::search_key_buffer, soup_find_word(), and soup_context_t::word_buffer.

Referenced by soup_solve().

soup_find_word()

bool soup_find_word ( const soup_grid_t * grid, const char * search_key, uint32_t key_len, uint32_t * out_start_row, uint32_t * out_start_col, uint32_t * out_end_row, uint32_t * out_end_col )

nodiscard

Search a grid for a normalized word along all 8 compass directions.

Parameters

[in]	grid	Pointer to populated board.
[in]	search_key	Normalized uppercase/stripped word string.
[in]	key_len	Length of normalized word.
[out]	out_start_row	Start row coordinate.
[out]	out_start_col	Start column coordinate.
[out]	out_end_row	End row coordinate.
[out]	out_end_col	End column coordinate.

Returns

bool True if word was found, false otherwise.

Precondition

grid, search_key, out_start_row, out_start_col, out_end_row, out_end_col are non-null.

key_len > 0.

Postcondition

Coordinates populated when true is returned.

Note

First-character candidate filtering provides optimal zero-allocation embedded search efficiency. For dynamic systems with massive dictionaries (10,000+ words), a multi-string Trie / Aho-Corasick automaton would be asymptotically preferred.

Since

0.1.0

Definition at line 162 of file alphabet_soup.c.

References soup_grid_t::cells, soup_grid_t::col_count, internal_check_cell(), k_soup_max_grid_cols, k_soup_max_grid_rows, k_soup_max_word_chars, and soup_grid_t::row_count.

Referenced by internal_solve_words().

soup_init()

ra8_err_t soup_init ( soup_context_t * ctx )

nodiscard

Initialize a caller-owned puzzle solver context.

Parameters

[out]

ctx

Solver context to zero-initialize.

Returns

ra8_err_t Result status.

Return values

k_ra8_ok	Context initialized.
k_ra8_err_null_ptr	ctx was null.

Precondition

ctx is non-null.

Postcondition

ctx is zero-initialized and ready for use.

Since

0.1.0

Definition at line 42 of file alphabet_soup.c.

References k_ra8_err_null_ptr, k_ra8_ok, and memset().

Referenced by soup_solve().

soup_solve()

ra8_err_t soup_solve ( soup_context_t * ctx, const char * text, uint32_t text_len, ra8_io_stream_t * out_stream )

nodiscard

Parse board and words from puzzle text and emit solutions to the output stream.

Parameters

[in,out]	ctx	Caller-owned solver context.
[in]	text	Null-terminated input file content.
[in]	text_len	Byte length of text.
[in,out]	out_stream	Bound destination stream for answer key emission.

Returns

ra8_err_t Status of parsing and emission.

Return values

k_ra8_ok	Puzzle parsed and output emitted.
k_ra8_err_null_ptr	A required pointer was null.
k_ra8_err_invalid_size	Text exceeded bounds or invalid dimensions.
k_ra8_err_range_check_failed	Dimensions or coordinates out of range.

Precondition

ctx, text, out_stream are non-null.

text_len <= k_soup_max_file_capacity.

out_stream is initialized and writable.

Postcondition

Answer key lines are written and flushed to out_stream.

Since

0.1.0

Definition at line 582 of file alphabet_soup.c.

References soup_grid_t::col_count, soup_context_t::grid, internal_parse_dimensions(), internal_parse_grid(), internal_solve_words(), k_ra8_err_invalid_size, k_ra8_err_null_ptr, k_ra8_ok, k_soup_max_file_capacity, soup_grid_t::row_count, and soup_init().

Referenced by main().