422 lines
14 KiB
C
422 lines
14 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdint.h>
|
|
#include <limits.h>
|
|
|
|
#define CODE_LEN 4
|
|
#define CODES 5
|
|
#define CODE_MAX_LEN 16*1024
|
|
#define sgn(a) ((a) < 0 ? -1 : ((a) > 0 ? 1 : 0))
|
|
#define min(a,b) ((a) < (b) ? (a) : (b))
|
|
#define abs(a) ((a) < 0 ? -(a) : (a))
|
|
|
|
typedef enum {
|
|
NUMERIC,
|
|
DIRECTIONAL
|
|
} panel_type;
|
|
|
|
typedef struct node {
|
|
struct node *children[11];
|
|
uint64_t value;
|
|
uint64_t value2;
|
|
char key;
|
|
uint8_t is_leaf;
|
|
} node_t;
|
|
|
|
|
|
typedef struct layer {
|
|
panel_type type;
|
|
struct layer *next_layer;
|
|
int current_position[2];
|
|
int id;
|
|
node_t *trie;
|
|
} layer_t;
|
|
|
|
const int numeric_panel[][2] = {
|
|
{3, 1}, // 0
|
|
{2, 0}, // 1
|
|
{2, 1}, // 2
|
|
{2, 2}, // 3
|
|
{1, 0}, // 4
|
|
{1, 1}, // 5
|
|
{1, 2}, // 6
|
|
{0, 0}, // 7
|
|
{0, 1}, // 8
|
|
{0, 2}, // 9
|
|
{3, 2}, // A
|
|
};
|
|
|
|
const int directional_panel[][2] = {
|
|
{0, 1}, // UP
|
|
{1, 0}, // LEFT
|
|
{1, 1}, // DOWN
|
|
{1, 2}, // RIGHT
|
|
{0, 2}, // A
|
|
};
|
|
|
|
#define UP 0
|
|
#define LEFT 1
|
|
#define DOWN 2
|
|
#define RIGHT 3
|
|
|
|
#define d2c(a) ((a) == UP ? '^' : ((a) == LEFT ? '<' : ((a) == DOWN ? 'v' : ((a) == RIGHT ? '>' : 'A'))))
|
|
|
|
layer_t* create_numeric_layer() {
|
|
layer_t *layer = calloc(1, sizeof(layer[0]));
|
|
layer->type = NUMERIC;
|
|
layer->next_layer = NULL;
|
|
layer->current_position[0] = numeric_panel[10][0];
|
|
layer->current_position[1] = numeric_panel[10][1];
|
|
layer->trie = calloc(1, sizeof(node_t));
|
|
return layer;
|
|
}
|
|
|
|
layer_t* create_directional_layer() {
|
|
layer_t *layer = calloc(1, sizeof(layer[0]));
|
|
layer->type = DIRECTIONAL;
|
|
layer->next_layer = NULL;
|
|
layer->current_position[0] = directional_panel[4][0];
|
|
layer->current_position[1] = directional_panel[4][1];
|
|
layer->trie = calloc(1, sizeof(node_t));
|
|
return layer;
|
|
}
|
|
|
|
int c2n(char code) {
|
|
if (code == 'A') {
|
|
return 10;
|
|
}
|
|
|
|
return code - 48;
|
|
}
|
|
|
|
node_t* create_node() {
|
|
node_t *node = calloc(1, sizeof(node[0]));
|
|
return node;
|
|
}
|
|
|
|
node_t* search(node_t* root, int* word, int len) {
|
|
node_t* node = root;
|
|
for (int i = 0; i < len; i++) {
|
|
if (node->children[word[i]] == NULL) {
|
|
return NULL;
|
|
}
|
|
node = node->children[word[i]];
|
|
}
|
|
return node;
|
|
}
|
|
|
|
void insert(node_t* root, int* word, int len, uint64_t value, int value2) {
|
|
node_t* node = root;
|
|
for (int i = 0; i < len; i++) {
|
|
if (node->children[word[i]] == NULL) {
|
|
node->children[word[i]] = create_node();
|
|
}
|
|
node = node->children[word[i]];
|
|
}
|
|
node->value = value;
|
|
node->value2 = value2;
|
|
node->is_leaf = 1;
|
|
}
|
|
|
|
void free_node(node_t* node) {
|
|
for (int i = 0; i < 11; i++) {
|
|
if (node->children[i] != NULL) {
|
|
free_node(node->children[i]);
|
|
}
|
|
}
|
|
|
|
free(node);
|
|
}
|
|
|
|
uint64_t process_layer(layer_t *layer, int *code, uint64_t code_len, int *new_code, uint64_t new_code_len);
|
|
uint64_t process_layer2(layer_t *layer, int* code, uint64_t code_len);
|
|
int coords_to_idx(layer_t *layer, int coords[2]);
|
|
uint64_t cost_of_activation(layer_t *layer, int button);
|
|
|
|
int main() {
|
|
char c;
|
|
|
|
char codes[CODES][CODE_LEN];
|
|
int code_count = 0, character_count = 0;
|
|
|
|
while ((c = getchar()) != EOF) {
|
|
codes[code_count][character_count++] = c;
|
|
if (c != '\n') {
|
|
continue;
|
|
}
|
|
character_count = 0;
|
|
code_count++;
|
|
}
|
|
|
|
// Create Layers
|
|
layer_t **layers = calloc(26, sizeof(layer_t*));
|
|
// First is the numeric panel
|
|
layers[0] = create_numeric_layer();
|
|
layers[0]->id = 0;
|
|
// Create directional layers
|
|
for (int i = 1; i < 26; i++) {
|
|
layers[i] = create_directional_layer();
|
|
layers[i]->id = i;
|
|
}
|
|
// Link layers
|
|
for (int i = 0; i < 25; i++) {
|
|
layers[i]->next_layer = layers[i+1];
|
|
}
|
|
|
|
uint64_t sum = 0;
|
|
for (int i = 0; i < code_count; i++) {
|
|
// Convert code chars to int
|
|
int code_encoded[4];
|
|
for (int j = 0; j < 4; j++) {
|
|
code_encoded[j] = c2n(codes[i][j]);
|
|
}
|
|
|
|
int *ccode = calloc(CODE_MAX_LEN, sizeof(ccode[0]));
|
|
//uint64_t a = process_layer(layers[0], code_encoded, 4, ccode, 0);
|
|
int code_encoded2[5];
|
|
for (int j = 0; j < 4; j++) {
|
|
code_encoded2[j+1] = c2n(codes[i][j]);
|
|
}
|
|
code_encoded2[0] = 10;
|
|
uint64_t a = process_layer2(layers[0], code_encoded2, 5);
|
|
free(ccode);
|
|
int b;
|
|
sscanf(codes[i], "%d", &b);
|
|
sum += a * (uint64_t)b;
|
|
}
|
|
printf("%lu\n", sum);
|
|
|
|
for (int i = 0; i < 26; i++) {
|
|
free_node(layers[i]->trie);
|
|
free(layers[i]);
|
|
}
|
|
free(layers);
|
|
}
|
|
|
|
uint64_t process_layer(layer_t *layer, int *code, uint64_t code_len, int *new_code, uint64_t new_code_len) {
|
|
if (code_len == 0) {
|
|
if (layer->next_layer == NULL) {
|
|
return new_code_len;
|
|
}
|
|
int *ccode = calloc(CODE_MAX_LEN, sizeof(ccode[0]));
|
|
uint64_t result = process_layer(layer->next_layer, new_code, new_code_len, ccode, 0);
|
|
free(ccode);
|
|
return result;
|
|
}
|
|
|
|
int current_position[2];
|
|
current_position[0] = layer->current_position[0];
|
|
current_position[1] = layer->current_position[1];
|
|
|
|
int (*panel)[2] = layer->type == NUMERIC ? numeric_panel : directional_panel;
|
|
// Check if we are on the right button
|
|
if (current_position[0] == panel[code[0]][0] && current_position[1] == panel[code[0]][1]) {
|
|
// Click button
|
|
new_code[new_code_len] = 4;
|
|
return process_layer(layer, code + 1, code_len - 1, new_code, new_code_len+1);
|
|
}
|
|
|
|
uint64_t ncl = new_code_len;
|
|
uint64_t value1 = UINT64_MAX, value2 = UINT64_MAX;
|
|
// Try going in each direction towards the next button
|
|
if (current_position[0] != panel[code[0]][0]) {
|
|
// Up or down
|
|
if (current_position[0] - panel[code[0]][0] > 0) {
|
|
for (int i = 0; i < current_position[0] - panel[code[0]][0]; i++) {
|
|
new_code[new_code_len++] = UP;
|
|
}
|
|
} else {
|
|
for (int i = 0; i < panel[code[0]][0] - current_position[0]; i++) {
|
|
new_code[new_code_len++] = DOWN;
|
|
}
|
|
}
|
|
layer->current_position[0] = panel[code[0]][0];
|
|
// Cannot go to empty space
|
|
if ((layer->type == NUMERIC && layer->current_position[0] == 3 && layer->current_position[1] == 0) || (layer->type == DIRECTIONAL && layer->current_position[0] == 0 && layer->current_position[1] == 0)) {
|
|
} else {
|
|
value1 = process_layer(layer, code, code_len, new_code, new_code_len);
|
|
}
|
|
}
|
|
layer->current_position[0] = current_position[0];
|
|
layer->current_position[1] = current_position[1];
|
|
new_code_len = ncl;
|
|
|
|
if (current_position[1] != panel[code[0]][1]) {
|
|
// Up or down
|
|
if (current_position[1] - panel[code[0]][1] > 0) {
|
|
for (int i = 0; i < current_position[1] - panel[code[0]][1]; i++) {
|
|
new_code[new_code_len++] = LEFT;
|
|
}
|
|
} else {
|
|
for (int i = 0; i < panel[code[0]][1] - current_position[1]; i++) {
|
|
new_code[new_code_len++] = RIGHT;
|
|
}
|
|
}
|
|
layer->current_position[1] = panel[code[0]][1];
|
|
// Cannot go to empty space
|
|
if ((layer->type == NUMERIC && layer->current_position[0] == 3 && layer->current_position[1] == 0) || (layer->type == DIRECTIONAL && layer->current_position[0] == 0 && layer->current_position[1] == 0)) {
|
|
} else {
|
|
value2 = process_layer(layer, code, code_len, new_code, new_code_len);
|
|
}
|
|
}
|
|
layer->current_position[0] = current_position[0];
|
|
layer->current_position[1] = current_position[1];
|
|
|
|
|
|
uint64_t value = min(value1, value2);
|
|
|
|
return value;
|
|
}
|
|
|
|
uint64_t process_layer2(layer_t *layer, int* code, uint64_t code_len) {
|
|
uint64_t sum = 0;
|
|
if (layer == NULL) {
|
|
return 1;
|
|
}
|
|
int (*panel)[2] = layer->type == NUMERIC ? numeric_panel : directional_panel;
|
|
int current_position[2];
|
|
int button_count = layer->type == NUMERIC ? 11 : 5;
|
|
|
|
// Build cache for each combination
|
|
if (layer->trie->children[0] == NULL) {
|
|
for (int i = 0; i < button_count; i++) {
|
|
for (int j = 0; j < button_count; j++) {
|
|
int combination[2] = {i, j};
|
|
int start1[2] = {panel[i][0], panel[i][1]};
|
|
int start2[2] = {panel[i][0], panel[i][1]};
|
|
int end[2] = {panel[j][0], panel[j][1]};
|
|
|
|
int last_action1 = 4;
|
|
// X first, Y second
|
|
uint64_t distance1 = 0;
|
|
while (start1[0] != end[0]) {
|
|
int dir = sgn(end[0] - start1[0]);
|
|
start1[0] += dir;
|
|
if ((layer->type == NUMERIC && start1[0] == 3 && start1[1] == 0) || (layer->type == DIRECTIONAL && start1[0] == 0 && start1[1] == 0)) {
|
|
distance1 = UINT64_MAX;
|
|
break;
|
|
}
|
|
int subcombination[2];
|
|
subcombination[0] = last_action1;
|
|
if (dir == -1) {
|
|
subcombination[1] = UP;
|
|
last_action1 = UP;
|
|
} else {
|
|
subcombination[1] = DOWN;
|
|
last_action1 = DOWN;
|
|
}
|
|
distance1 += process_layer2(layer->next_layer, subcombination, 2);
|
|
}
|
|
if (distance1 != UINT64_MAX) {
|
|
while (start1[1] != end[1]) {
|
|
int dir = sgn(end[1] - start1[1]);
|
|
start1[1] += dir;
|
|
int subcombination[2];
|
|
subcombination[0] = last_action1;
|
|
if (dir == -1) {
|
|
subcombination[1] = LEFT;
|
|
last_action1 = LEFT;
|
|
} else {
|
|
subcombination[1] = RIGHT;
|
|
last_action1 = RIGHT;
|
|
}
|
|
distance1 += process_layer2(layer->next_layer, subcombination, 2);
|
|
}
|
|
}
|
|
if (distance1 != UINT64_MAX) {
|
|
int activatecombination[2] = {last_action1, 4};
|
|
distance1 += process_layer2(layer->next_layer, activatecombination, 2);
|
|
}
|
|
|
|
int last_action2 = 4;
|
|
// Y first, X second
|
|
uint64_t distance2 = 0;
|
|
while (start2[1] != end[1]) {
|
|
int dir = sgn(end[1] - start2[1]);
|
|
start2[1] += dir;
|
|
if ((layer->type == NUMERIC && start2[0] == 3 && start2[1] == 0) || (layer->type == DIRECTIONAL && start2[0] == 0 && start2[1] == 0)) {
|
|
distance2 = UINT64_MAX;
|
|
break;
|
|
}
|
|
int subcombination[2];
|
|
subcombination[0] = last_action2;
|
|
if (dir == -1) {
|
|
subcombination[1] = LEFT;
|
|
last_action2 = LEFT;
|
|
} else {
|
|
subcombination[1] = RIGHT;
|
|
last_action2 = RIGHT;
|
|
}
|
|
distance2 += process_layer2(layer->next_layer, subcombination, 2);
|
|
}
|
|
if (distance2 != UINT64_MAX) {
|
|
while (start2[0] != end[0]) {
|
|
int dir = sgn(end[0] - start2[0]);
|
|
start2[0] += dir;
|
|
int subcombination[2];
|
|
subcombination[0] = last_action2;
|
|
if (dir == -1) {
|
|
subcombination[1] = UP;
|
|
last_action2 = UP;
|
|
} else {
|
|
subcombination[1] = DOWN;
|
|
last_action2 = DOWN;
|
|
}
|
|
distance2 += process_layer2(layer->next_layer, subcombination, 2);
|
|
}
|
|
}
|
|
if (distance2 != UINT64_MAX) {
|
|
int activatecombination[2] = {last_action2, 4};
|
|
distance2 += process_layer2(layer->next_layer, activatecombination, 2);
|
|
}
|
|
|
|
uint64_t distance = distance1;
|
|
int last_action = last_action1;
|
|
if (distance1 > distance2) {
|
|
distance = distance2;
|
|
last_action = last_action2;
|
|
}
|
|
|
|
//printf("Layer %i: cost from %i to %i is %lu\n", layer->id, i, j, distance);
|
|
insert(layer->trie, combination, 2, distance, last_action);
|
|
}
|
|
}
|
|
}
|
|
|
|
for (uint64_t i = 1; i < code_len; i++) {
|
|
int combination[2] = {code[i-1], code[i]};
|
|
node_t *node = search(layer->trie, combination, 2);
|
|
sum += node->value;
|
|
}
|
|
|
|
return sum;
|
|
}
|
|
|
|
int coords_to_idx(layer_t *layer, int coords[2]) {
|
|
int idx;
|
|
int (*panel)[2] = layer->type == NUMERIC ? numeric_panel : directional_panel;
|
|
for (idx = 0; idx < (layer->type == NUMERIC ? 11 : 5); idx++) {
|
|
if (coords[0] == panel[idx][0] && coords[1] == panel[idx][1]) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
return idx;
|
|
}
|
|
|
|
uint64_t cost_of_activation(layer_t *layer, int button) {
|
|
if (layer == NULL) {
|
|
return 1;
|
|
}
|
|
|
|
// Build cache if not present
|
|
if (layer->trie->children[0] == NULL) {
|
|
process_layer2(layer, NULL, 0);
|
|
}
|
|
|
|
int combination[2] = {button, 4};
|
|
node_t *node = search(layer->trie, combination, 2);
|
|
|
|
return node->value + cost_of_activation(layer->next_layer, node->value2);
|
|
}
|