We will write a seeking algorithm that takes in the file data.bin, which contains a series of instructions that must be performed on a Linked List. The flag can be printed by reading the list after performing the operations.
You have been provided data.bin, which contains the serialized array. Each element contains an operational code (OP) that tells what operation to perform, which in turn has the following form:
0: Add a node to the end of the list. Following this sequence is a char value to add.
| OP | c |
| 0 | 1 |1: Add a node to the front of the list. Following this sequence is a char value to add.
| OP | c |
| 0 | 1 |2: Add a node to a specific index. Following the sequence is the index to add at and then a char value to add.
| OP | index | c |
| 0 | 1 | 2 | 3 |3: Remove a node from the end of the list.
| OP |
| 0 |4: Remove a node from the front of the list.
| OP |
| 0 |5: Remove a node from a specific index. Following the sequence is the index to remove from.
| OP | index |
| 0 | 1 | 2 |The flag is generated by performing the sequence of operations provided in the data.bin file and printing out the Linked List once the operations have been completed.
The flag will be represented in ASCII. Surround the data that you get in flag{} braces.
Stuck? Open one hint at a time before reading the walkthrough.
This challenge is a bit different than the previous one. Rather than the serialization representing a raw data structure, we are provided raw operations to generate our own.
For this challenge, we must define how we will build the linked list, then build the linked list, and then print it once it's fully initialized.
Despite the serialized data being operations on a linked list, we still must define a linked list. The linked list holds characters. Each item must contain a pointer to the next node. We can represent this as a struct containing these two values:
1typedef struct ArrayItem
2{
3 uint8_t letter;
4 struct ArrayItem *next;
5From now on, we can simply refer to the struct ArrayItem as node.
We will open the file as always and ensure it has been opened.
1FILE *fp = fopen("data.bin", "rb");
2if (fp == NULL)
3{After this, we must initialize the data structure. We define the head node as NULL, indicating that the list is empty.
node *head = NULL;Now, we can begin the while loop. Counting the number of elements before the loop is impractical because each element has a different size. It's easier to simply run an infinite loop that breaks when no more elements are read. We can check when reading the opcode.
opcode?opcode, the rest of the structure is guaranteed to follow.1uint16_t num_elements = 0;
2while (1)
3{
4 /** Read and process data **/
5For each entry, we first need to find the opcode. We can break the loop if we don't read any bytes at this step.
1uint8_t opcode;
2uint32_t bytes = fread(&opcode, sizeof(opcode), 1, fp);
3Our next step depends on the opcode. You can use a series of if statements or a switch to handle the opcode. I chose if statements because that's the first thing that comes to mind when I build solutions.
Let's handle each case:
Case 0: Add a node to the end of the list. We need to read one more byte (the character to insert) and then insert this node at the end of the list. We also must increment the number of elements.
1if (opcode == 0)
2{
3 fread(&chr, sizeof(chrLet's handle the insertNode and removeNode methods. These methods are standard linked list operations. You could quickly look online for linked list implementations, but I'll explain my own. Rather than making separate functions for inserting and removing at the start, end, and index, it's easier to use the same method. It makes the data reading code a lot simpler.
Here are the declarations for both methods:
1void insertNode(node **head, uint16_t loc, char letter);
2void removeNode(node **head,Inserting a Node
To insert a node, we must make a new node for it. I'll dynamically allocate it to ensure it doesn't lose scope and get deleted.
1// make a new node
2node *new = malloc(sizeof(node));
3new->letter = letter;
4We must handle the edge cases. If we're inserting to an empty list (meaning head = NULL), we can simply set the head to the new node.
1// handle empty list
2if (*head == NULL)
3{
4 *head = new;
If we insert it into the front, we can combine this with the other edge case. Both have the same methodology.
1// edge case: empty list or inserting beginning
2if (*head == NULL || loc == 0)
3{
4Now, we can handle the main case: inserting in the center or end. We first must iterate to the location we want to insert. We want to stop at the node before the location we want to insert. At the same time, we should ensure that we aren't inserting beyond the length of the list.
1// main case: inserting center
2node *current = *head;
3for (uint16_t index = 0; index < loc -Finally, once we have the location, we link in new after next .
1// link the nodes
2new->next = current->next;
3current->next = new;Removing a Node
Removing a node is a similar process. We first handle the two edge cases: (1) when the list is already empty or (2) when we're removing from the start.
1if (*head == NULL)
2 return; // list is empty
3
4if (loc ==Then, we cover the main case: removing from the center. We navigate to the node before the one we want to remove using the same logic as inserting a node.
1// main case: remove from center
2node *current = *head;
3for (uint16_t index = 0; index < loc Once we're here, we can remove the node by linking the surrounding nodes.
1node *toDelete = current->next;
2current->next = toDelete->next;
3free(toDelete);This is it! Now, we can print the flag.
We can make a function that prints a linked list for us. We'll encapsulate the flag braces at the same time.
1void printNode(node **head)
2{
3 printf("flag{");
4 forRunning this prints the flag:
gcc -o solve solve.c && ./solve && rm solveflag{FORGEDLINKS}Here is the full solution:
Case 1: Insert at the front of the list. We need to read one more byte, being the character to insert.
1if (opcode == 1)
2{
3 fread(&chr, sizeof(chr), 1, fp);
4 insertNode(&head, 0, chr);
5 ++num_elements;
6}Case 2: Insert at an index. We need to read two bytes for the index and one for the character. Then, we can insert.
1if (opcode == 2)
2{
3 fread(&index, sizeof(index), 1, fp);
4 fread(&chr, sizeof(chr), 1, fp);
5 insertNode(&head, index, chr);
6 ++num_elements;
7}Case 3: Remove a node from the end of the list. We don't need any more data, so we remove the node and then decrease the number of elements.
1if (opcode == 3)
2{
3 removeNode(&head, num_elements - 1);
4 --num_elements;
5}Case 4: Remove a node from the front of the list. We don't need any more data, so we remove the node and then decrease the number of elements.
1if (opcode == 4)
2{
3 removeNode(&head, 0);
4 --num_elements;
5}Case 5: Remove a node from an index. We need to read two bytes for the index. We remove the node and then decrement the number of elements.
1if (opcode == 5)
2{
3 fread(&index, sizeof(index), 1, fp);
4 removeNode(&head, index);
5 --num_elements;
6}Default Case: We shouldn't ever reach here. If we read this, we should print it out and exit. This means we read something wrong.
1else
2{
3 printf("Bad read: %01x", opcode);
4 exit(EXIT_FAILURE);
5}1#include <stdint.h>
2#include <stdio.h>
3#include <stdlib.h>
4
5typedef struct ArrayItem
6{
7 uint8_t letter;
8 struct ArrayItem *next;
9} node;
10
11void insertNode(node **head, uint16_t loc, char letter)
12{
13 // make a new node
14 node *new = malloc(sizeof(node));
15 new->letter = letter;
16 new->next = NULL;
17
18 // edge case: empty list or inserting beginning
19 if (*head == NULL || loc == 0)
20 {
21 new->next = *head;
22 *head = new;
23 return;
24 }
25
26 // main case: inserting center
27 node *current = *head;
28 for (uint16_t index = 0; index < loc - 1 && current != NULL; ++index)
29 current = current->next;
30
31 if (current == NULL)
32 { // error: beyond edge length
33 free(new);
34 return;
35 }
36
37 // link the nodes
38 new->next = current->next;
39 current->next = new;
40}
41
42void removeNode(node **head, uint16_t loc)
43{
44 if (*head == NULL)
45 return; // list is empty
46
47 if (loc == 0)
48 { // remove from start
49 node *toDelete = *head;
50 *head = (*head)->next;
51 free(toDelete);
52 return;
53 }
54
55 // main case: remove from center
56 node *current = *head;
57 for (uint16_t index = 0; index < loc - 1 && current != NULL; ++index)
58 current = current->next;
59
60 if (current == NULL || current->next == NULL)
61 {
62 // error: beyond edge length
63 return;
64 }
65
66 node *toDelete = current->next;
67 current->next = toDelete->next;
68 free(toDelete);
69}
70
71void printNode(node **head)
72{
73 printf("flag{");
74 for (node *c = *head; c != NULL; c = c->next)
75 printf("%c", c->letter);
76 printf("}\n");
77}
78
79int main()
80{
81 FILE *fp = fopen("data.bin", "rb");
82 if (fp == NULL)
83 {
84 printf("Error opening file.\n");
85 exit(EXIT_FAILURE);
86 }
87
88 node *head = NULL;
89
90 uint16_t num_elements = 0;
91 while (1)
92 {
93 uint8_t opcode = 0;
94 uint16_t bytes_read = fread(&opcode, sizeof(opcode), 1, fp);
95 if (bytes_read == 0)
96 break;
97
98 uint8_t chr;
99 uint16_t index;
100 if (opcode == 0)
101 { // insert end
102 fread(&chr, sizeof(chr), 1, fp);
103 insertNode(&head, num_elements, chr);
104 ++num_elements;
105 }
106 else if (opcode == 1)
107 { // insert front
108 fread(&chr, sizeof(chr), 1, fp);
109 insertNode(&head, 0, chr);
110 ++num_elements;
111 }
112 else if (opcode == 2)
113 { // insert index
114 fread(&index, sizeof(index), 1, fp);
115 fread(&chr, sizeof(chr), 1, fp);
116 insertNode(&head, index, chr);
117 ++num_elements;
118 }
119 else if (opcode == 3)
120 { // remove end
121 removeNode(&head, num_elements - 1);
122 --num_elements;
123 }
124 else if (opcode == 4)
125 { // remove front
126 removeNode(&head, 0);
127 --num_elements;
128 }
129 else if (opcode == 5)
130 { // remove index
131 fread(&index, sizeof(index), 1, fp);
132 removeNode(&head, index);
133 --num_elements;
134 }
135 else
136 {
137 printf("Bad read: %01x", opcode);
138 exit(EXIT_FAILURE);
139 }
140 }
141
142 printNode(&head);
143 return 0;
144}