139 lines
3.2 KiB
C
139 lines
3.2 KiB
C
#include <string.h>
|
|
#include <stdlib.h>
|
|
#include "lib.h"
|
|
|
|
struct Vec expand_disk_map(char* input) {
|
|
size_t input_length = strlen(input);
|
|
size_t required_length = 0;
|
|
|
|
for (size_t i = 0; i < input_length; i++) {
|
|
required_length += input[i] - '0';
|
|
}
|
|
|
|
int* data = malloc(sizeof(int) * required_length);
|
|
int id = 0;
|
|
int data_idx = 0;
|
|
for (size_t i = 0; i < input_length; i++) {
|
|
size_t digit = input[i] - '0';
|
|
|
|
for (size_t j = 0; j < digit; j++) {
|
|
if (i % 2 == 0) {
|
|
data[data_idx] = id;
|
|
} else {
|
|
data[data_idx] = -1;
|
|
}
|
|
data_idx++;
|
|
}
|
|
|
|
if (i % 2 == 0) {
|
|
id++;
|
|
}
|
|
}
|
|
|
|
struct Vec vec = { required_length, data };
|
|
return vec;
|
|
}
|
|
|
|
void compress_fs(struct Vec vec) {
|
|
size_t last_digit_search_start = vec.length - 1;
|
|
for (size_t i = 0; i < vec.length; i++) {
|
|
if (vec.data[i] != -1) {
|
|
continue;
|
|
}
|
|
|
|
size_t j;
|
|
for (j = last_digit_search_start; j > i; j--) {
|
|
if (vec.data[j] == -1) {
|
|
continue;
|
|
}
|
|
|
|
break;
|
|
}
|
|
|
|
if (j == i) {
|
|
break;
|
|
}
|
|
|
|
last_digit_search_start = j - 1;
|
|
vec.data[i] = vec.data[j];
|
|
vec.data[j] = -1;
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Find a range of spaces of the required length.
|
|
* Returns the index of the start of the range.
|
|
* Returns 0 if the range is not found.
|
|
*/
|
|
size_t find_space(struct Vec vec, size_t max_idx, size_t len) {
|
|
size_t counter = 0;
|
|
|
|
for (size_t i = 0; i <= max_idx; i++) {
|
|
if (vec.data[i] != -1) {
|
|
counter = 0;
|
|
continue;
|
|
}
|
|
|
|
counter++;
|
|
if (counter == len) {
|
|
return i + 1 - counter;
|
|
}
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
void compress_fs_by_blocks(struct Vec vec) {
|
|
int id = -1;
|
|
size_t block_end;
|
|
for (size_t i = vec.length - 1; i > 0; i--) {
|
|
if (vec.data[i] == id) {
|
|
continue;
|
|
}
|
|
|
|
// Last digit of the block was found.
|
|
if (id == -1) {
|
|
id = vec.data[i];
|
|
block_end = i;
|
|
continue;
|
|
}
|
|
|
|
// First digit of the block was found.
|
|
size_t block_start = i + 1;
|
|
size_t block_len = block_end - block_start + 1;
|
|
|
|
size_t space_idx = find_space(vec, block_start - 1, block_len);
|
|
// Space was found.
|
|
if (space_idx != 0) {
|
|
for (size_t si = space_idx; si < space_idx + block_len; si++) {
|
|
vec.data[si] = id;
|
|
}
|
|
for (size_t bi = block_start; bi <= block_end; bi++) {
|
|
vec.data[bi] = -1;
|
|
}
|
|
}
|
|
|
|
id = vec.data[i];
|
|
block_end = i;
|
|
}
|
|
}
|
|
|
|
long calc_checksum(struct Vec vec) {
|
|
long sum = 0;
|
|
for (size_t i = 0; i < vec.length; i++) {
|
|
if (vec.data[i] == -1) {
|
|
continue;
|
|
}
|
|
|
|
sum += i * vec.data[i];
|
|
}
|
|
return sum;
|
|
}
|
|
|
|
struct Vec copy_vec(struct Vec vec) {
|
|
int data_size = sizeof(int) * vec.length;
|
|
int* data_copy = malloc(data_size);
|
|
memcpy(data_copy, vec.data, data_size);
|
|
struct Vec vec_copy = { vec.length, data_copy };
|
|
return vec_copy;
|
|
}
|