Table of Contents

IronForgeCyber

Courses

Resources

Blog

Log In



IronForgeCyber

AboutPrivacyTerms

© 2026 IronForgeCyber. All rights reserved.

  1. courses
  2. c-programming
  3. mountain-climbers
24 min read

Mountain Climbers

From Advent of Code
This challenge is based on Day 12: Hill Climbing Algorithm from Advent of Code 2022, an annual collection of programming puzzles by Eric Wastl.

Problem Description

You will write a program that opens the file input.txt and finds the shortest path from the starting position to the end position. The elevation of the surrounding area constrains the path.

  • The contour map is broken into a grid; the elevation of each square on the grid is given by a single lowercase letter, where a is the lowest elevation and z is the highest elevation.
  • The height map also includes your current position (S) and the target position for the best view (E). Your current position has elevation a, and the target position has elevation z.
  • You would like to reach E, but to save energy for the rest of the trip home, you want to do it in as few steps as possible. You can move exactly one square up, down, left, or right during each step. Because a certain MIDN forgot their climbing gear at home, the elevation of the destination square can be, at most, one higher than the elevation of the current square. This means if you are at an elevation of height m, you can step to n but not to o. This also means that the elevation of the destination square can be much lower than that of your current square.

You have two parts to this challenge:

  1. Find the fewest number of steps to move from starting position S to the target location.
  2. Find the fewest steps to move from any base position a to the target location.

Concatenate these answers in flag braces separated by a semicolon (flag{part1:part2}).

Stuck? Open one hint at a time before reading the walkthrough.

Hint 1
Read the map into a 2-D array, treating S as a and E as z. A step can climb at most one letter but drop any amount.
Hint 2
"Fewest steps" on a grid means breadth-first search: explore every square one step away, then every square two steps away, and so on.
Hint 3
Keep a queue of squares to explore, each with its step count, and never visit a square twice.
Hint 4
For part 2, run the same search from every a and keep the shortest result. (Searching backwards from E once also works.)

Walkthrough

This challenging problem is aptly worth the points it is worth. This challenge tests your ability to implement a BFS algorithm with proper backtracking to find the shortest path.

We are using a BFS to solve this problem. Let's talk about data structures:

  • I chose to store the current length as an int. I could have used an unsigned integer, but with BFS/DFS algorithms, I like having a sanity check to ensure the number won't underflow.
  • We need to store the grid map. Since its size is unchanging, I chose a 2-D static array. I made the variable global so any function can access it.
  • We need to store the current queue of positions in each state. I used a linked list to do this.
  • We also need to store the visited positions. I used a linked list for this as well.

For the linked list, we need to know the position and the fewest steps to get to it. I made a struct to hold this information.

c
1typedef struct node
2{
3    int x, y, steps;
4    struct node *

We'll need to keep a global linked list containing the queue of nodes plus the visited nodes.

c
node *queue, *visited;

We also want to know the height and width of the board. We'll also store this globally so every function can see it.

c
int height, width;

With this out of the way, we can open the file and initialize data. We'll open the file as normal.

c
1// Open file for reading
2FILE *file = fopen("input.txt", "r");
3if (file == NULL)

Reading the File

Once we have the file opened, we need to initialize the data. This involves reading the array into the map we created. This time, I chose to use fscanf() to get the string, but getline() works too.

c
1// Read data for file
2int index = 0;
3map[index] = malloc(100);
4

Once this is done, we must initialize the height and width of the map.

c
1// Declare height and width of the heightmap
2height = index;
3width = strlen(map[0]);

Once this is initialized, the processing can begin. We do almost all this in sub-functions, so we'll discuss the looping mechanism in this part and the processing in the next.

We must parse through all the data for both parts. In each part, we check for something different:

  • Part 1: We check for the starting position S.
  • Part 2: We check for any position.

For the BFS algorithm, we simply check to ensure that any finish result is less than the current best case. If it is, we update the best case.

c
1// Find Starting coordinates and calculate shortest path
2int part1 = INT_MAX;
3int part2 = INT_MAX;
4for

From here, we can parse the data and perform the BFS algorithm.

Parsing the Data

Here comes the challenge. We need to define a function BFS() that takes a coordinate and returns the shortest path to the end.

First, we must free queue and visited because we are starting a new BFS algorithm. This ensures the lists are empty.

c
1// Free memory of the queue and visited
2free_memory(queue);
3free_memory(visited);
4queue = visited = NULL

Next, we need to make a new node for the starting position. We'll build nodes often enough that it's worthy of its own function. This function should take the three values we need to make a node, allocate a new one, and return a pointer to the node.

c
1node *buildNode(int x, int y, int steps)
2{
3    node *new_node = malloc

We'll use this to make a new node for the starting position. At the same time, we'll start our queue with this node.

c
1// Create new node
2node *start = buildNode(x, y, 0);
3// Add starting node to the queue
4queue 

We are going to run the BFS algorithm until the queue is empty. When the queue is empty, we have no more nodes to check. Since BFS doesn't require backtracking, we can make this a simple while loop.

c
1while (queue != NULL)
2{
3    /* BFS algorithm */
4}

We need to get the data from the current node. We'll store this in variables for ease of use.

c
1// Get data from current node
2int x = queue->x;
3int y = queue->y;
4int value =

We introduce a new function getValue that finds the value of that position in the map.

c
1int getValue(int x, int y)
2{
3    char value = map[y][x
Why do we define S as 0 and E as 25?
In this case, these represent the start and end positions. We want to ensure that the start position is always the lowest value and the end position is always the highest value. This ensures that we don't backtrack to a position we've already been to.

We need to remove the current node from the queue. We should also add the current node to the visited list.

c
1// Remove node from the queue
2node *current = queue;
3queue = queue->next;
4current->next = NULL

We need to iterate through the current node's neighbors. To represent the directional arrays for the neighbors, we can define dx and dy.

c
1// Neighbors coordinates
2int dx[] = { 1, 0, -1, 0 };
3

At each iteration, we need to do the following checks:

  • Get the coordinates of the neighbor
  • Check if the neighbor is in the map. If so:
    • Check if the node is the goal node (E). If so, return the number of steps.
    • Check if the node is movable. If so:
      • Build a new node for the neighbor.
      • Check if the node is already in the queue. If not, add it to the queue.
      • If it is, free the node.
c
1// Find neighbors
2for (int i = 0; i < 4; i++)

We made two new functions here.

  • The first function is inQueue(), which checks if the node is in the queue.

    c
    1int inQueue(node *curr)
    2{
    3    // Check if node is in the queue
    4

If we reach the end of the queue and do not return a value, there is no path to the end. In this case, we should return INT_MAX to indicate that there is no path.

This is everything we need to execute a BFS algorithm. We can use this to print the flag.

Printing the Flag

To print the flag, we simply combine the answers from the two parts.

c
printf("flag{%d:%d}\n", part1, part2);

Once we're done, we free the memory. map is a 2D array, so we need to free each row individually. We also need to free our linked lists and close the file.

c
1// Free memory
2for (int i = 0; i < index + 1; i++)
3    free(

We define free_memory() to free a Linked List.

c
1void free_memory(node *list)
2{
3    // Free memory of the list
4    while (list)

Running this method will return the flag! This method will take some time to run, depending on the machine. This method has to run a BFS algorithm for every a in the map. BFS is an O(V + E) algorithm, so the overall time is O(V + E * a). This is a very large number, so running will take some time.

Full Solution

The full solution is below:

solve.c
next
;
5} node;
4{
5 printf("Could not open file.\n");
6 exit(EXIT_FAILURE);
7}
while
(
fscanf
(
file
,
"%s"
,
map
[
index
]
)
!=
EOF
)
5{
6 map[++index] = malloc(100);
7}
(
int
y
=
0
;
y
<
height
;
y
++
)
5{
6 for (int x = 0; x < width; x++)
7 {
8 // part 1 - provided start point
9 if (map[y][x] == 'S')
10 {
11 if (BFS(x, y) < part1)
12 part1 = BFS(x, y);
13 }
14 // part 2 - any 'a' start point
15 if (map[y][x] == 'a')
16 {
17 if (BFS(x, y) < part2)
18 part2 = BFS(x, y);
19 }
20 }
21}
;
(
sizeof
(
node
)
)
;
4 new_node->x = x;
5 new_node->y = y;
6 new_node->steps = steps;
7 new_node->next = NULL;
8 return new_node;
9}
=
start
;
getValue
(
x
,
y
)
;
5int steps = queue->steps;
]
;
4 switch (value)
5 {
6 case 'S':
7 return 0;
8 case 'E':
9 return 25;
10 default:
11 return value - 'a';
12 }
13}
;
5
6// Add current node to the visited queue
7current->next = visited;
8visited = current;
int
dy
[
]
=
{
0
,
1
,
0
,
-
1
}
;
3{
4 // Get neighbor coordinates
5 int nx = x + dx[i];
6 int ny = y + dy[i];
7
8 // Check if neighbor is in the map
9 if (nx >= 0 && nx < width && ny >= 0 && ny < height)
10 {
11 // Check if node is the goal
12 if (value >= 24 && map[ny][nx] == 'E')
13 return steps + 1;
14
15 // check if neighbor is movable
16 int neighbor_value = getValue(nx, ny);
17 if (neighbor_value <= value + 1)
18 {
19 node *n = buildNode(nx, ny, steps + 1);
20
21 // Check if node is already in the queue
22 if (!inQueue(n))
23 // Add node to the queue
24 enqueue(&queue, n);
25 else
26 free(n);
27 }
28 }
29}
node
*
ptr
=
queue
;
5 while (ptr != NULL)
6 {
7 if (curr->x == ptr->x && curr->y == ptr->y && curr->steps >= ptr->steps)
8 return 1;
9 ptr = ptr->next;
10 }
11
12 // Check if node is in the visited queue
13 ptr = visited;
14 while (ptr != NULL)
15 {
16 if (curr->x == ptr->x && curr->y == ptr->y && curr->steps >= ptr->steps)
17 return 1;
18
19 ptr = ptr->next;
20 }
21 return 0;
22}
  • The second function is enqueue(), which adds a node to the back of the queue.

    c
    1void enqueue(node **list, node *n)
    2{
    3    if (*list == NULL)
    4    { // If list is empty
    5        *list = n;
    6    }
    7    else
    8    { // else add node to the end of the list
    9        node *current = *list;
    10        while (current->next != NULL)
    11            current = current->next;
    12
    13        current->next = n;
    14    }
    15}
  • map
    [
    i
    ]
    )
    ;
    4
    5free_memory(visited);
    6free_memory(queue);
    7fclose(file);
    5 {
    6 node *temp = list;
    7 list = list->next;
    8 free(temp);
    9 }
    10}
    1#include <limits.h>
    2#include <stdio.h>
    3#include <stdlib.h>
    4#include <string.h>
    5
    6typedef struct node
    7{
    8    int x, y, steps;
    9    struct node *next;
    10} node;
    11
    12// Global variable declaration
    13char *map[50];
    14node *queue, *visited;
    15int height, width;
    16
    17// Functions declarations
    18int BFS(int x, int y);
    19int inQueue(node *n);
    20void free_memory(node *list);
    21int getValue(int x, int y);
    22node *buildNode(int x, int y, int steps);
    23void enqueue(node **list, node *n);
    24
    25int BFS(int x, int y)
    26{
    27    // Free memory of the queue and visited
    28    free_memory(queue);
    29    free_memory(visited);
    30    queue = visited = NULL;
    31
    32    // Create new node
    33    node *start = buildNode(x, y, 0);
    34
    35    // Neighbors coordinates
    36    int dx[] = { 1, 0, -1, 0 };
    37    int dy[] = { 0, 1, 0, -1 };
    38
    39    // Add starting node to the queue
    40    queue = start;
    41
    42    while (queue != NULL)
    43    {
    44        // Get data from current node
    45        int x = queue->x;
    46        int y = queue->y;
    47        int value = getValue(x, y);
    48        int steps = queue->steps;
    49
    50        // Remove node from the queue
    51        node *current = queue;
    52        queue = queue->next;
    53        current->next = NULL;
    54
    55        // Add current node to the visited queue
    56        current->next = visited;
    57        visited = current;
    58
    59        // Find neighbors
    60        for (int i = 0; i < 4; i++)
    61        {
    62            // Get neighbor coordinates
    63            int nx = x + dx[i];
    64            int ny = y + dy[i];
    65
    66            // Check if neighbor is in the map
    67            if (nx >= 0 && nx < width && ny >= 0 && ny < height)
    68            {
    69                // Check if node is the goal
    70                if (value >= 24 && map[ny][nx] == 'E')
    71                    return steps + 1;
    72
    73                // check if neighbor is movable
    74                int neighbor_value = getValue(nx, ny);
    75                if (neighbor_value <= value + 1)
    76                {
    77                    node *n = buildNode(nx, ny, steps + 1);
    78
    79                    // Check if node is already in the queue
    80                    if (!inQueue(n))
    81                        // Add node to the queue
    82                        enqueue(&queue, n);
    83                    else
    84                        free(n);
    85                }
    86            }
    87        }
    88    }
    89    return INT_MAX;
    90}
    91
    92int inQueue(node *curr)
    93{
    94    // Check if node is in the queue
    95    node *ptr = queue;
    96    while (ptr != NULL)
    97    {
    98        if (curr->x == ptr->x && curr->y == ptr->y && curr->steps >= ptr->steps)
    99            return 1;
    100        ptr = ptr->next;
    101    }
    102
    103    // Check if node is in the visited queue
    104    ptr = visited;
    105    while (ptr != NULL)
    106    {
    107        if (curr->x == ptr->x && curr->y == ptr->y && curr->steps >= ptr->steps)
    108            return 1;
    109
    110        ptr = ptr->next;
    111    }
    112    return 0;
    113}
    114
    115void free_memory(node *list)
    116{
    117    // Free memory of the list
    118    while (list)
    119    {
    120        node *temp = list;
    121        list = list->next;
    122        free(temp);
    123    }
    124}
    125
    126int getValue(int x, int y)
    127{
    128    char value = map[y][x];
    129    switch (value)
    130    {
    131    case 'S':
    132        return 0;
    133    case 'E':
    134        return 25;
    135    default:
    136        return value - 'a';
    137    }
    138}
    139
    140node *buildNode(int x, int y, int steps)
    141{
    142    node *new_node = malloc(sizeof(node));
    143    new_node->x = x;
    144    new_node->y = y;
    145    new_node->steps = steps;
    146    new_node->next = NULL;
    147    return new_node;
    148}
    149
    150void enqueue(node **list, node *n)
    151{
    152    if (*list == NULL)
    153    { // If list is empty
    154        *list = n;
    155    }
    156    else
    157    { // else add node to the end of the list
    158        node *current = *list;
    159        while (current->next != NULL)
    160            current = current->next;
    161
    162        current->next = n;
    163    }
    164}
    165
    166int main(void)
    167{
    168    // Open file for reading
    169    FILE *file = fopen("input.txt", "r");
    170    if (file == NULL)
    171    {
    172        printf("Could not open file.\n");
    173        exit(EXIT_FAILURE);
    174    }
    175
    176    // Read data for file
    177    int index = 0;
    178    map[index] = malloc(100);
    179    while (fscanf(file, "%s", map[index]) != EOF)
    180    {
    181        map[++index] = malloc(100);
    182    }
    183
    184    // Declare height and width of the heightmap
    185    height = index;
    186    width = strlen(map[0]);
    187
    188    // Find Starting coordinates and calculate shortest path
    189    int part1 = INT_MAX;
    190    int part2 = INT_MAX;
    191    for (int y = 0; y < height; y++)
    192    {
    193        for (int x = 0; x < width; x++)
    194        {
    195            // part 1 - provided start point
    196            if (map[y][x] == 'S')
    197            {
    198                if (BFS(x, y) < part1)
    199                    part1 = BFS(x, y);
    200            }
    201            // part 2 - any 'a' start point
    202            if (map[y][x] == 'a')
    203            {
    204                if (BFS(x, y) < part2)
    205                    part2 = BFS(x, y);
    206            }
    207        }
    208    }
    209
    210    // Print results to console
    211    printf("flag{%d:%d}\n", part1, part2);
    212
    213    // Free memory
    214    for (int i = 0; i < index + 1; i++)
    215        free(map[i]);
    216
    217    free_memory(visited);
    218    free_memory(queue);
    219    fclose(file);
    220}