Advent of Code - Day 6, 2024: BFS and FSM
To solve this Advent of Code (parts 1 and 2), I used Breadth-First Search (BFS) to keep moving the guard as well as Finite State Machine (FSM) to control the directions. This solves part 1 easily. Part 2 can be solved using the same technique, takes a little longer since you need to try every empty cell, but it eventually does the trick (takes a min or so). Code is down below, cheers, ACC.
using System.IO;
using System.Collections;
using System;
using System.Text;
using System.Text.RegularExpressions;
using System.ComponentModel.DataAnnotations;
Process2();
void Process()
{
string fileName = "input.txt";
FileInfo fileInfo = new FileInfo(fileName);
StreamReader sr = fileInfo.OpenText();
List map = new List();
int startRow = 0;
int startCol = 0;
while (!sr.EndOfStream)
{
string line = sr.ReadLine().Trim();
map.Add(new StringBuilder(line));
int indexStart = line.IndexOf('^');
if (indexStart >= 0)
{
startRow = map.Count - 1;
startCol = indexStart;
}
}
sr.Close();
int retVal = ProcessExitMap(map, startRow, startCol);
Console.WriteLine(retVal);
}
void Process2()
{
string fileName = "input.txt";
FileInfo fileInfo = new FileInfo(fileName);
StreamReader sr = fileInfo.OpenText();
List map = new List();
int startRow = 0;
int startCol = 0;
while (!sr.EndOfStream)
{
string line = sr.ReadLine().Trim();
map.Add(new StringBuilder(line));
int indexStart = line.IndexOf('^');
if (indexStart >= 0)
{
startRow = map.Count - 1;
startCol = indexStart;
}
}
sr.Close();
int retVal = 0;
for (int row = 0; row < map.Count; row++)
{
for (int col = 0; col < map[row].Length; col++)
{
if (map[row][col] == '.')
{
map[row][col] = '#';
if (ProcessExitMap(map, startRow, startCol) == -1)
retVal++;
map[row][col] = '.';
}
}
}
Console.WriteLine(retVal);
}
void PrintMap(List map, int guardRow, int guardCol)
{
for (int row = 0; row < map.Count; row++)
{
for(int col = 0; col < map[row].Length;col++)
{
if (row == guardRow && col == guardCol)
{
Console.Write("@");
}
else
{
Console.Write(map[row][col]);
}
}
Console.WriteLine();
}
Console.ReadLine();
}
int ProcessExitMap(List map, int startRow, int startCol)
{
Queue queue = new Queue();
HashSet visited = new HashSet();
MapCell initialCell = new MapCell(startRow, startCol, 1, "up");
queue.Enqueue(initialCell);
visited.Add(initialCell.key);
HashSet distinctPositionsVisited = new HashSet ();
while (queue.Count > 0)
{
MapCell currentCell = queue.Dequeue();
//Console.WriteLine("DISTINCT POSITIONS: {0}", distinctPositionsVisited.Count);
//PrintMap(map, currentCell.row, currentCell.col);
if (currentCell.row < 0 ||
currentCell.row >= map.Count ||
currentCell.col < 0 ||
currentCell.col >= map[startRow].Length)
{
//Console.WriteLine();
//Console.WriteLine("FOUND: {0}", distinctPositionsVisited.Count);
return distinctPositionsVisited.Count;
}
string position = currentCell.row.ToString() + "@" + currentCell.col.ToString();
if(!distinctPositionsVisited.Contains(position))
distinctPositionsVisited.Add(position);
int newRow = 0;
int newCol = 0;
string newDirection = "";
switch (currentCell.direction)
{
case "up":
if (currentCell.row - 1 >= 0 && map[currentCell.row - 1][currentCell.col] == '#')
{
newRow = currentCell.row;
newCol = currentCell.col;
newDirection = "right";
MapCell newCell = new MapCell(newRow, newCol, currentCell.numberSteps, newDirection);
queue.Enqueue(newCell);
}
else
{
newRow = currentCell.row - 1;
newCol = currentCell.col;
newDirection = "up";
MapCell newCell = new MapCell(newRow, newCol, currentCell.numberSteps + 1, newDirection);
if (!visited.Contains(newCell.key))
{
queue.Enqueue(newCell);
visited.Add(newCell.key);
}
}
break;
case "down":
if (currentCell.row + 1 < map.Count && map[currentCell.row + 1][currentCell.col] == '#')
{
newRow = currentCell.row;
newCol = currentCell.col;
newDirection = "left";
MapCell newCell = new MapCell(newRow, newCol, currentCell.numberSteps, newDirection);
queue.Enqueue(newCell);
}
else
{
newRow = currentCell.row + 1;
newCol = currentCell.col;
newDirection = "down";
MapCell newCell = new MapCell(newRow, newCol, currentCell.numberSteps + 1, newDirection);
if (!visited.Contains(newCell.key))
{
queue.Enqueue(newCell);
visited.Add(newCell.key);
}
}
break;
case "right":
if (currentCell.col + 1 < map[currentCell.row].Length && map[currentCell.row][currentCell.col + 1] == '#')
{
newRow = currentCell.row;
newCol = currentCell.col;
newDirection = "down";
MapCell newCell = new MapCell(newRow, newCol, currentCell.numberSteps, newDirection);
queue.Enqueue(newCell);
}
else
{
newRow = currentCell.row;
newCol = currentCell.col + 1;
newDirection = "right";
MapCell newCell = new MapCell(newRow, newCol, currentCell.numberSteps + 1, newDirection);
if (!visited.Contains(newCell.key))
{
queue.Enqueue(newCell);
visited.Add(newCell.key);
}
}
break;
case "left":
if (currentCell.col - 1 >= 0 && map[currentCell.row][currentCell.col - 1] == '#')
{
newRow = currentCell.row;
newCol = currentCell.col;
newDirection = "up";
MapCell newCell = new MapCell(newRow, newCol, currentCell.numberSteps, newDirection);
queue.Enqueue(newCell);
}
else
{
newRow = currentCell.row;
newCol = currentCell.col - 1;
newDirection = "left";
MapCell newCell = new MapCell(newRow, newCol, currentCell.numberSteps + 1, newDirection);
if (!visited.Contains(newCell.key))
{
queue.Enqueue(newCell);
visited.Add(newCell.key);
}
}
break;
}
}
return -1;
}
class MapCell
{
public int row = 0;
public int col = 0;
public int numberSteps = 0;
public string direction = "";
public string key = "";
public MapCell(int row, int col, int numberSteps, string direction)
{
this.row = row;
this.col = col;
this.numberSteps = numberSteps;
this.direction = direction;
this.key = row.ToString() + "@" + col.ToString() + "@" + direction.ToString();
}
}
Comments
Post a Comment