Advent of Code 2022, Day 6

6.cpp

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

char *read_file_to_string(const char *filename)
{
  FILE *handle = fopen(filename, "r");
  fseek(handle, 0, SEEK_END);
  long size = ftell(handle);
  fseek(handle, 0, SEEK_SET);
  char *mem = (char*)malloc(size+1);
  size_t n = fread(mem, 1, size, handle);
  fclose(handle);
  mem[n] = 0;
  return mem;
}

// Theta(n) search of the first index of a substring of given length that
// contains all unique characters, or -1 if not found.
int find_first_unique_substr_index(const char *str, int len)
{
  int last_seen[256];
  memset(last_seen, -1, sizeof(last_seen));
  int next_candidate_index = len-1;
  for(int i = 0; str[i]; ++i)
  {
    int skip_to = last_seen[str[i]] + len;
    if (skip_to > next_candidate_index) next_candidate_index = skip_to;
    else if (next_candidate_index <= i) return i+1-len;
    last_seen[str[i]] = i;
  }
  return -1;
}

int main(int argc, char **argv)
{
  char *input = read_file_to_string(argc > 1 ? argv[1] : "input.txt");
  printf("first unique substr of len 4 ends at: %d\n", find_first_unique_substr_index(input, 4) + 4);
  printf("first unique substr of len 14 ends at: %d\n", find_first_unique_substr_index(input, 14) + 14);
  return 0;
}