257 lines
6.8 KiB
C
257 lines
6.8 KiB
C
#include <stdio.h>
|
|
#include <stdint.h>
|
|
#include <stdbool.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
#define DEFAULT_FILE "input.txt"
|
|
#define STRBUF_LEN 200
|
|
// #define GRID_ROWS 5
|
|
// #define GRID_COLS 5
|
|
#define GRID_ROWS 140
|
|
#define GRID_COLS 140
|
|
|
|
/**
|
|
* @brief Reads a file and loads the grid into
|
|
* an array of rows and columns
|
|
*/
|
|
void load_grid(FILE *file, char grid[GRID_ROWS][GRID_COLS])
|
|
{
|
|
char strbuf[STRBUF_LEN] = {0};
|
|
int i = 0;
|
|
|
|
for (i = 0; i < GRID_ROWS; i++)
|
|
{
|
|
fgets(strbuf, STRBUF_LEN, file);
|
|
memcpy(grid[i], strbuf, GRID_COLS);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* @brief Finds the row and col idx of the 'S' char and places them in row_idx and col_idx
|
|
*
|
|
* @return true if S is found
|
|
* @return false if S is not found
|
|
*/
|
|
bool find_s(char grid[GRID_ROWS][GRID_COLS], int *row_idx, int *col_idx)
|
|
{
|
|
int r;
|
|
int c;
|
|
for (r = 0; r < GRID_ROWS; r++)
|
|
{
|
|
for (c = 0; c < GRID_ROWS; c++)
|
|
{
|
|
if (grid[r][c] == 'S')
|
|
{
|
|
*row_idx = r;
|
|
*col_idx = c;
|
|
return true;
|
|
}
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
/**
|
|
* @brief Checks if the cell above should be populated, and populates it if so
|
|
*
|
|
* @return true if the cell was populated
|
|
* @return false if the cell was not populatd
|
|
*/
|
|
bool populate_distance_above(int row, int col, int distance_grid[GRID_ROWS][GRID_COLS], char grid[GRID_ROWS][GRID_COLS])
|
|
{
|
|
if (!row) return false;
|
|
|
|
char c = grid[row][col];
|
|
if (c != '|' && c != 'J' && c != 'L' && c != 'S') return false;
|
|
|
|
// Check for existing distance
|
|
char above = grid[row - 1][col];
|
|
if (above != '|' && above != '7' && above != 'F') return false;
|
|
|
|
// Check for existing distance
|
|
if (distance_grid[row - 1][col] != -1) return false;
|
|
|
|
int distance = distance_grid[row][col];
|
|
distance_grid[row - 1][col] = distance + 1;
|
|
return true;
|
|
}
|
|
|
|
/**
|
|
* @brief Checks if the cell to the left should be populated, and populates it if so
|
|
*
|
|
* @return true if the cell was populated
|
|
* @return false if the cell was not populatd
|
|
*/
|
|
bool populate_distance_left(int row, int col, int distance_grid[GRID_ROWS][GRID_COLS], char grid[GRID_ROWS][GRID_COLS])
|
|
{
|
|
if (!col) return false;
|
|
|
|
char c = grid[row][col];
|
|
if (c != '-' && c != '7' && c != 'J' && c != 'S') return false;
|
|
|
|
char left = grid[row][col - 1];
|
|
if (left != '-' && left != 'L' && left != 'F') return false;
|
|
|
|
// Check for existing distance
|
|
if (distance_grid[row][col - 1] != -1) return false;
|
|
|
|
int distance = distance_grid[row][col];
|
|
distance_grid[row][col - 1] = distance + 1;
|
|
return true;
|
|
}
|
|
|
|
/**
|
|
* @brief Checks if the cell to the right should be populated, and populates it if so
|
|
*
|
|
* @return true if the cell was populated
|
|
* @return false if the cell was not populatd
|
|
*/
|
|
bool populate_distance_right(int row, int col, int distance_grid[GRID_ROWS][GRID_COLS], char grid[GRID_ROWS][GRID_COLS])
|
|
{
|
|
if (row == GRID_ROWS) return false;
|
|
char c = grid[row][col];
|
|
if (c != '-' && c != 'L' && c != 'F' && c != 'S') return false;
|
|
|
|
// Check for connecting pipe
|
|
char right = grid[row][col + 1];
|
|
if (right != '-' && right != '7' && right != 'J') return false;
|
|
|
|
// Check for existing distance
|
|
if (distance_grid[row][col + 1] != -1) return false;
|
|
|
|
int distance = distance_grid[row][col];
|
|
distance_grid[row][col + 1] = distance + 1;
|
|
return true;
|
|
}
|
|
|
|
/**
|
|
* @brief Checks if the cell below should be populated, and populates it if so
|
|
*
|
|
* @param data
|
|
* @param list
|
|
* @param grid
|
|
* @return true if the cell was populated
|
|
* @return false if the cell was not populatd
|
|
*/
|
|
bool populate_distance_below(int row, int col, int distance_grid[GRID_ROWS][GRID_COLS], char grid[GRID_ROWS][GRID_COLS])
|
|
{
|
|
if (col == GRID_COLS) return false;
|
|
|
|
char c = grid[row][col];
|
|
if (c != '|' && c != 'F' && c != '7' && c != 'S') return false;
|
|
|
|
// Check for connecting pipe
|
|
char below = grid[row + 1][col];
|
|
|
|
if (below != '|' && below != 'J' && below != 'L') return false;
|
|
|
|
// Check for existing distance
|
|
if (distance_grid[row + 1][col] != -1) return false;
|
|
|
|
int distance = distance_grid[row][col];
|
|
distance_grid[row + 1][col] = distance + 1;
|
|
return true;
|
|
}
|
|
|
|
bool populate_distances_around(int row, int col, int distance_grid[GRID_ROWS][GRID_COLS], char grid[GRID_ROWS][GRID_COLS])
|
|
{
|
|
bool progress_made = false;
|
|
if (populate_distance_above(row, col, distance_grid, grid)) progress_made = true;
|
|
if (populate_distance_left(row, col, distance_grid, grid)) progress_made = true;
|
|
if (populate_distance_right(row, col, distance_grid, grid)) progress_made = true;
|
|
if (populate_distance_below(row, col, distance_grid, grid)) progress_made = true;
|
|
return progress_made;
|
|
}
|
|
|
|
/**
|
|
* @brief Preform pass of entire grid and populate next step of distances
|
|
*
|
|
* @param distance the current distance to populate around
|
|
*/
|
|
bool populate_distance_step(int current_distance, int distance_grid[GRID_ROWS][GRID_COLS], char grid[GRID_ROWS][GRID_COLS])
|
|
{
|
|
int row = 0;
|
|
int col = 0;
|
|
bool progress_made = false;
|
|
|
|
for (row = 0; row < GRID_ROWS; row++)
|
|
{
|
|
for (col = 0; col < GRID_COLS; col++)
|
|
{
|
|
if (distance_grid[row][col] == current_distance)
|
|
{
|
|
progress_made = populate_distances_around(row, col, distance_grid, grid);
|
|
}
|
|
}
|
|
}
|
|
|
|
return progress_made;
|
|
}
|
|
|
|
void print_distance_map(int distance_grid[GRID_ROWS][GRID_COLS])
|
|
{
|
|
int row = 0;
|
|
int col = 0;
|
|
for (row = 0; row < GRID_ROWS; row++)
|
|
{
|
|
for (col = 0; col < GRID_COLS; col++)
|
|
{
|
|
if (distance_grid[row][col] != -1) printf(" %0.2d", distance_grid[row][col]);
|
|
else printf(" .");
|
|
}
|
|
printf("\n");
|
|
}
|
|
}
|
|
|
|
int main(int argc, char **argv)
|
|
{
|
|
// Get filename as an argument, if there is one
|
|
char *path = (argc > 1) ? argv[1] : DEFAULT_FILE;
|
|
|
|
if (!path)
|
|
{
|
|
printf("Requires input file.\n");
|
|
return 1;
|
|
}
|
|
|
|
FILE *file = fopen(path, "r");
|
|
|
|
if (!file)
|
|
{
|
|
printf("Could not find file.");
|
|
return 1;
|
|
}
|
|
|
|
char grid[GRID_ROWS][GRID_COLS] = {0};
|
|
int distance_grid[GRID_ROWS][GRID_COLS];
|
|
memset(distance_grid, -1, sizeof(distance_grid));
|
|
|
|
load_grid(file, grid);
|
|
|
|
int r = 0;
|
|
int c = 0;
|
|
|
|
if (!find_s(grid, &r, &c))
|
|
{
|
|
printf("Could not find S???\n");
|
|
return 1;
|
|
}
|
|
|
|
int current_distance = 0;
|
|
distance_grid[r][c] = 0;
|
|
|
|
bool progress_made = true;
|
|
while (progress_made)
|
|
{
|
|
progress_made = populate_distance_step(current_distance, distance_grid, grid);
|
|
printf("---\n");
|
|
current_distance++;
|
|
}
|
|
|
|
print_distance_map(distance_grid);
|
|
|
|
printf("Longest route: %d", current_distance);
|
|
|
|
return 0;
|
|
} |