alphabet_soup.c

Go to the documentation of this file.

 
#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"

typedef struct {
  int32_t delta_row; 
  int32_t delta_col; 
} soup_dir_t;

typedef enum : uint32_t {
  k_decimal_base         = 10U,        
  k_decimal_overflow_cap = 429496729U, 
} soup_numeric_constants_t;
 
ra8_err_t soup_init(soup_context_t* ctx)
{
  if (ctx == nullptr) {
    return k_ra8_err_null_ptr;
  }
  (void)memset(ctx, 0, sizeof(soup_context_t));
  return k_ra8_ok;
}

RA8_INTERNAL 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)
{
  int32_t end_r = r + (dir.delta_row * span);
  int32_t end_c = c + (dir.delta_col * span);
  int32_t rows  = (int32_t)grid->row_count;
  int32_t cols  = (int32_t)grid->col_count;
 
  if ((end_r < 0) || (end_r >= rows) || (end_c < 0) || (end_c >= cols)) {
    return false;
  }
 
  for (int32_t k = 0; k <= span; ++k) {
    int32_t cur_r = r + (dir.delta_row * k);
    int32_t cur_c = c + (dir.delta_col * k);
    if (grid->cells[cur_r][cur_c] != key[k]) {
      return false;
    }
  }
 
  return true;
}

RA8_INTERNAL 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)
{
  static const soup_dir_t s_search_directions[k_soup_direction_count] = {
    {.delta_row = 0, .delta_col = 1},   
    {.delta_row = 1, .delta_col = 1},   
    {.delta_row = 1, .delta_col = 0},   
    {.delta_row = 1, .delta_col = -1},  
    {.delta_row = 0, .delta_col = -1},  
    {.delta_row = -1, .delta_col = -1}, 
    {.delta_row = -1, .delta_col = 0},  
    {.delta_row = -1, .delta_col = 1},  
  };
 
  for (uint32_t d = 0U; d < k_soup_direction_count; ++d) {
    soup_dir_t dir = s_search_directions[d];
    if (internal_match_ray(grid, key, span, r, c, dir)) {
      const int32_t end_row = r + (dir.delta_row * span);
      const int32_t end_col = c + (dir.delta_col * span);
      *out_end_row          = (uint32_t)end_row;
      *out_end_col          = (uint32_t)end_col;
      return true;
    }
  }
  return false;
}
 
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)
{
  if ((grid == nullptr) || (search_key == nullptr) || (out_start_row == nullptr) ||
      (out_start_col == nullptr) || (out_end_row == nullptr) || (out_end_col == nullptr) ||
      (key_len == 0U) || (key_len > k_soup_max_word_chars) || (grid->row_count == 0U) ||
      (grid->row_count > k_soup_max_grid_rows) || (grid->col_count == 0U) ||
      (grid->col_count > k_soup_max_grid_cols)) {
    return false;
  }
 
  int32_t rows = (int32_t)grid->row_count;
  int32_t cols = (int32_t)grid->col_count;
  int32_t span = (int32_t)key_len - 1;
  char    lead = search_key[0];
 
  for (int32_t r = 0; r < rows; ++r) {
    for (int32_t c = 0; c < cols; ++c) {
      if (grid->cells[r][c] != lead) {
        continue;
      }
      if (internal_check_cell(grid, search_key, span, r, c, out_end_row, out_end_col)) {
        *out_start_row = (uint32_t)r;
        *out_start_col = (uint32_t)c;
        return true;
      }
    }
  }
 
  return false;
}

RA8_INTERNAL static ra8_err_t
internal_parse_uint32(const char** text_ptr, const char* text_end, uint32_t* out_val)
{
  const char* ptr   = *text_ptr;
  uint32_t    val   = 0U;
  bool        found = false;
 
  for (uint32_t i = 0U; i < k_soup_max_dim_digits; ++i) {
    if ((ptr >= text_end) || (*ptr < '0') || (*ptr > '9')) {
      break;
    }
    uint32_t digit = (uint32_t)(*ptr - '0');
    if (val > k_decimal_overflow_cap) {
      return k_ra8_err_range_check_failed;
    }
    val   = (val * k_decimal_base) + digit;
    found = true;
    ptr++;
  }
 
  if (!found) {
    return k_ra8_err_invalid_arg;
  }
 
  *out_val  = val;
  *text_ptr = ptr;
  return k_ra8_ok;
}

RA8_INTERNAL static ra8_err_t internal_parse_dimensions(const char** text_ptr,
                                                        const char*  text_end,
                                                        uint32_t*    out_rows,
                                                        uint32_t*    out_cols)
{
  uint32_t  rows = 0U;
  uint32_t  cols = 0U;
  ra8_err_t err  = internal_parse_uint32(text_ptr, text_end, &rows);
  if (err != k_ra8_ok) {
    return err;
  }
 
  const char* ptr = *text_ptr;
  if ((ptr >= text_end) || ((*ptr != 'x') && (*ptr != 'X'))) {
    return k_ra8_err_invalid_arg;
  }
  ptr++;
  *text_ptr = ptr;
 
  err = internal_parse_uint32(text_ptr, text_end, &cols);
  if (err != k_ra8_ok) {
    return err;
  }
 
  ptr = *text_ptr;
  for (uint32_t step = 0U; step < k_soup_max_line_steps; ++step) {
    if ((ptr >= text_end) || ((*ptr != '\r') && (*ptr != '\n'))) {
      break;
    }
    ptr++;
  }
 
  if ((rows == 0U) || (rows > k_soup_max_grid_rows) || (cols == 0U) ||
      (cols > k_soup_max_grid_cols)) {
    return k_ra8_err_range_check_failed;
  }
 
  *out_rows = rows;
  *out_cols = cols;
  *text_ptr = ptr;
  return k_ra8_ok;
}

RA8_INTERNAL static ra8_err_t internal_parse_single_row(const char** text_ptr,
                                                        const char*  text_end,
                                                        char*        row_cells,
                                                        uint32_t     expected_cols)
{
  const char* ptr = *text_ptr;
  uint32_t    c   = 0U;
 
  for (uint32_t step = 0U; step < k_soup_max_line_steps; ++step) {
    if ((ptr >= text_end) || (*ptr == '\0') || (*ptr == '\n') || (*ptr == '\r')) {
      break;
    }
    if ((*ptr != ' ') && (*ptr != '\t')) {
      if (c >= expected_cols) {
        return k_ra8_err_invalid_size;
      }
      row_cells[c] = *ptr;
      c++;
    }
    ptr++;
  }
 
  if (c != expected_cols) {
    return k_ra8_err_invalid_size;
  }
 
  for (uint32_t step = 0U; step < k_soup_max_line_steps; ++step) {
    if ((ptr >= text_end) || ((*ptr != '\r') && (*ptr != '\n'))) {
      break;
    }
    ptr++;
  }
 
  *text_ptr = ptr;
  return k_ra8_ok;
}

RA8_INTERNAL static ra8_err_t
internal_parse_grid(const char** text_ptr, const char* text_end, soup_grid_t* grid)
{
  for (uint32_t r = 0U; r < grid->row_count; ++r) {
    ra8_err_t err = internal_parse_single_row(text_ptr, text_end, grid->cells[r], grid->col_count);
    if (err != k_ra8_ok) {
      return err;
    }
  }
  return k_ra8_ok;
}

RA8_INTERNAL 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)
{
  (void)ra8_io_stream_puts(out_stream, word);
  (void)ra8_io_stream_putc(out_stream, ' ');
  (void)ra8_io_stream_put_u32(out_stream, start_row);
  (void)ra8_io_stream_putc(out_stream, ':');
  (void)ra8_io_stream_put_u32(out_stream, start_col);
  (void)ra8_io_stream_putc(out_stream, ' ');
  (void)ra8_io_stream_put_u32(out_stream, end_row);
  (void)ra8_io_stream_putc(out_stream, ':');
  (void)ra8_io_stream_put_u32(out_stream, end_col);
  (void)ra8_io_stream_putc(out_stream, '\n');
}

RA8_INTERNAL 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)
{
  const char* ptr        = *text_ptr;
  uint32_t    word_len   = 0U;
  uint32_t    search_len = 0U;
 
  for (uint32_t step = 0U; step < k_soup_max_line_steps; ++step) {
    if ((ptr >= text_end) || (*ptr == '\0') || (*ptr == '\r') || (*ptr == '\n')) {
      break;
    }
    if ((word_len + 1U) < word_cap) {
      word[word_len] = *ptr;
      word_len++;
    }
    if ((*ptr != ' ') && (*ptr != '\t')) {
      if ((search_len + 1U) < key_cap) {
        search_key[search_len] = *ptr;
        search_len++;
      }
    }
    ptr++;
  }
 
  for (uint32_t step = 0U; step < k_soup_max_line_steps; ++step) {
    if ((ptr >= text_end) || ((*ptr != '\r') && (*ptr != '\n'))) {
      break;
    }
    ptr++;
  }
 
  *out_search_len = search_len;
  *text_ptr       = ptr;
}

RA8_INTERNAL static ra8_err_t internal_solve_words(soup_context_t*  ctx,
                                                   const char*      ptr,
                                                   const char*      text_end,
                                                   ra8_io_stream_t* out_stream)
{
  for (uint32_t step = 0U; step < k_soup_max_parse_steps; ++step) {
    if ((ptr >= text_end) || (*ptr == '\0')) {
      break;
    }
 
    (void)memset(ctx->word_buffer, 0, sizeof(ctx->word_buffer));
    (void)memset(ctx->search_key_buffer, 0, sizeof(ctx->search_key_buffer));
    uint32_t search_len = 0U;
 
    internal_parse_word_entry(&ptr,
                              text_end,
                              ctx->word_buffer,
                              sizeof(ctx->word_buffer),
                              ctx->search_key_buffer,
                              sizeof(ctx->search_key_buffer),
                              &search_len);
 
    if (search_len == 0U) {
      continue;
    }
 
    uint32_t start_row = 0U;
    uint32_t start_col = 0U;
    uint32_t end_row   = 0U;
    uint32_t end_col   = 0U;
    if (soup_find_word(&ctx->grid,
                       ctx->search_key_buffer,
                       search_len,
                       &start_row,
                       &start_col,
                       &end_row,
                       &end_col)) {
      internal_emit_match(out_stream, ctx->word_buffer, start_row, start_col, end_row, end_col);
    }
  }
 
  return ra8_io_stream_flush(out_stream);
}
 
ra8_err_t
soup_solve(soup_context_t* ctx, const char* text, uint32_t text_len, ra8_io_stream_t* out_stream)
{
  if ((ctx == nullptr) || (text == nullptr) || (out_stream == nullptr)) {
    return k_ra8_err_null_ptr;
  }
  if ((text_len == 0U) || (text_len > k_soup_max_file_capacity)) {
    return k_ra8_err_invalid_size;
  }
 
  ra8_err_t err = soup_init(ctx);
  if (err != k_ra8_ok) {
    return err;
  }
 
  const char* ptr      = text;
  const char* text_end = &text[text_len];
 
  err = internal_parse_dimensions(&ptr, text_end, &ctx->grid.row_count, &ctx->grid.col_count);
  if (err != k_ra8_ok) {
    return err;
  }
 
  err = internal_parse_grid(&ptr, text_end, &ctx->grid);
  if (err != k_ra8_ok) {
    return err;
  }
 
  return internal_solve_words(ctx, ptr, text_end, out_stream);
}