You will write an algorithm that opens a file input.txt and follows a series of instructions to switch supply crates between stacks. You must track the crates that are on the top of each stack.
The top of the file contains the current arrangement of the crates. Following that is the rearrangement procedure.
The Marines must know which crates will be on top of the stack. Submit your flag as the order of what's on the top of each stack wrapped in flag braces, i.e. flag{CMZ}.
Stuck? Open one hint at a time before reading the walkthrough.
move N from A to B moves crates one at a time: pop from A, push onto B, N times. Parsing with strtok()? Watch for a carriage return (\r) at the end of lines.This is a difficult challenge. This is a complicated file to parse. The primary difference between this file and the challenges before this is that this challenge comes with initial data, meaning we can't simply start parsing instructions. We need to take time to collect the initial data before parsing the instructions. We'll quickly learn that doing this in C isn't all that fun.
Before we start, let's pick a data structure. We'll choose a stack as a good choice for this problem. There are two ways to implement stacks in C:
For this solution, I chose to use a static array, which is less space-efficient. I challenge you to rework this solution to use a linked list instead.
We will complete this challenge in two parts. First, we will read and store the initial data in our stack. Then, we will read the instructions and update our stack accordingly.
We'll start with the same initializations as the previous challenges. We'll open the file, ensure it's opened, and initialize our read buffer.
1// open the file
2FILE *fp = fopen("input.txt", "r");
3if (fp == NULL)We will use the same getline loop to read the data. When we read the stack data, we are unsure which stacks have data on each line, so it's easier to parse it knowing the entire line.
1while ((read = getline(&line, &len, fp)) != -1)
2{
The first thing we must do is determine the number of stacks. At the same time, we will track the last line of stack data so we know how much to parse when we initialize the stacks.
Based on the input, the line containing the stack numbers begins with a space. We will read until our first character is a space. Once we have this line, we will go to the end of the line and read off the last number. This will be the number of stacks.
1// read until the newline
2size_t des_line = 0;
3int num_stacks;
4whileWe define des_line as the number of lines containing stack data. This way, when we return to read the data, we know how many lines to read.
Since we aren't sure of the size of the number, we have to read from the last number to the space. There are better solutions than this, but it works. A plausible second solution would be to use strtok() to get each line number. Here is that solution:
1size_t des_line = 0;
2int num_stacks;
3while ((read = getline(strtok() to delimit the stack numbers. However, when we reach the end of the line, we'll notice that we hit a 0xd. This is a carriage return. This is a unique character used to delimit new lines. For modern processing, newlines can be represented as 0xd0xa or \r\n. This is because the original ASCII standard used 0xd to represent newlines. We must check for 0xd in our strtok() loop.This is not an intuitive solution. I initially tried checking token[0] == \n, and it took me a minute to debug why this solution didn't work.
Now that we have the number of stacks, we need to re-read the start of the file until we reach this line. First, we need to reset the file pointer to the beginning of the file.
fseek(fp, 0, SEEK_SET);fp = fopen("input.txt", "r");This is not a wrong solution; fseek() is more efficient.
Next, we should allocate the storage. We need num_stacks stacks. Since we chose to use a static array, we will define a size for each stack. I chose 100.
1// allocate the storage
2char **stacks = malloc(num_stacks * sizeof(char *));
3At the same time, we also must track the number of crates on each stack. We will use a second array to track this.
size_t *size = calloc(num_stacks, sizeof(size_t));Once we do this, we need to read the data. We defined des_line earlier, which we tracked as the number of lines containing stack data. We will read lines until we reach this number of lines
1size_t line_num = 0;
2while (line_num != des_line)
3{
4 // get the line
We need to parse the data for each line. The data format can help us determine which column we're in.
1 + char_num / 4. This is because each stack item is four characters long (two brackets, one letter, and one space).char_num / 4 will tell us what column we're in. Note: I removed the 1 + because our array uses zero-based indexing, while the stack numbers are one-based.Let's make this happen.
1size_t line_num = 0;
2while (line_num != des_line)
3{
4We now have the initial data stored. However, it's not quite right. We read the stacks from top to bottom, meaning that the top of the stacks are at the bottom. We need to reverse each stack to fix this.
1// we put them in backward, reverse the lists
2for (size_t i = 0; i < num_stacks; ++i)
3{We're almost done! All we need to do is move the FILE* pointer to the start of the instructions. We know this is two lines away (the stack numbers line plus the newline).
1// push the line twice to get to the right spot
2getline(&line, &len, fp);
3getline(&line, &len,Now, our data is initialized. We can move on to parsing the instructions.
Thankfully, this is the easy part. We can easily read the rest of the lines and get the needed data.
We need three unsigned integers: the number of moving items, the source stack, and the destination stack. We can use strtok() to get these values. We can ignore the strings in between but need to remember to read them.
1size_t moving, origin, destination;
2while (getline(&line, &len, fp) != How do we move the items between stacks? We need to move them in reverse order. We can use a for loop to count from 0 to moving and move them from the old stack to the new stack. At the same time, we can post-decrement size[destination] and size[origin].
We can do this in a nice ugly one-liner.
1for (size_t action = 0; action < moving; ++action)
2{
3 stacks[destination][Now that the data has been processed, we can print the flag. The flag is simply the top of each stack. We can use a nice for loop to handle this:
1// get the top stacks
2printf("flag{");
3for (size_t i = 0; i < num_stacks; ++Remember to free the memory! We allocated memory for the stacks, the sizes, and the line buffer. We need to free all of these.
1// free the memory
2for (size_t i = 0; i < num_stacks; ++i)
3 free(stacks[Running this prints our flag.
A linked list solution mitigates this problem.
The full solution is below:
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int main(void)
6{
7 // open the file
8 FILE *fp = fopen("input.txt", "r");
9 if (fp == NULL)
10 exit(EXIT_FAILURE);
11
12 // prep the input
13 char *line = NULL;
14 ssize_t read;
15 size_t len = 0;
16
17 // read until the newline
18 size_t des_line = 0;
19 int num_stacks;
20 while ((read = getline(&line, &len, fp)) != 1)
21 {
22 // our desired line guaranteed starts with a space
23 if (line[0] == ' ')
24 {
25 char *token = strtok(line, " ");
26 while ((token = strtok(NULL, " ")) != NULL && token[0] != 0xd)
27 num_stacks = atoi(token);
28 break;
29 }
30 else
31 {
32 ++des_line;
33 }
34 }
35
36 // this resets the file to start reading from the beginning
37 fseek(fp, 0, 0);
38
39 // allocate the storage
40 char **stacks = malloc(num_stacks * sizeof(char *));
41 for (size_t i = 0; i < num_stacks; ++i)
42 {
43 stacks[i] = malloc(100 * sizeof(char));
44 }
45 size_t *size = calloc(num_stacks, sizeof(size_t));
46
47 // now read the first 8 lines and get the data
48 size_t line_num = 0;
49 while (line_num != des_line)
50 {
51 // get the line
52 read = getline(&line, &len, fp);
53
54 // read across the line looking for chars
55 for (size_t i = 0; i < read; ++i)
56 {
57 if (line[i] >= 'A' && line[i] <= 'Z')
58 {
59 if (i / 4 < num_stacks)
60 {
61 stacks[i / 4][size[i / 4]++] = line[i];
62 }
63 else
64 {
65 printf("Out of bounds error on line %zu\n", line_num);
66 exit(EXIT_FAILURE);
67 }
68 }
69 }
70
71 ++line_num;
72 }
73
74 // we put them in backwards, reverse the lists
75 for (size_t i = 0; i < num_stacks; ++i)
76 {
77 char *rev_stack = malloc(100 * sizeof(char));
78 for (size_t j = 0; j < size[i]; ++j)
79 rev_stack[j] = stacks[i][size[i] - j - 1];
80 free(stacks[i]);
81 stacks[i] = rev_stack;
82 }
83
84 // push the line twice to get to the right spot
85 getline(&line, &len, fp);
86 getline(&line, &len, fp);
87
88 // now we need to parse the rest of the lines
89 size_t moving, origin, destination;
90 while (getline(&line, &len, fp) != -1)
91 {
92 strtok(line, " "); // Moving
93
94 size_t moving = atoi(strtok(NULL, " "));
95 strtok(NULL, " "); // from
96
97 size_t origin = atoi(strtok(NULL, " ")) - 1;
98 strtok(NULL, " "); // to
99
100 size_t destination = atoi(strtok(NULL, " ")) - 1;
101
102 // perform the action
103 for (size_t action = 0; action < moving; ++action)
104 {
105 stacks[destination][size[destination]++] = stacks[origin][(size[origin]--) - 1];
106 }
107 }
108
109 // get the top stacks
110 printf("flag{");
111 for (size_t i = 0; i < num_stacks; ++i)
112 printf("%c", stacks[i][size[i] - 1]);
113 printf("}\n");
114
115 // free the memory
116 for (size_t i = 0; i < num_stacks; ++i)
117 free(stacks[i]);
118 free(stacks);
119 free(size);
120 if (line)
121 free(line);
122
123 return 0;
124}