diff options
| author | Mistivia <i@mistivia.com> | 2024-02-16 11:07:30 +0800 |
|---|---|---|
| committer | Mistivia <i@mistivia.com> | 2024-02-16 11:07:30 +0800 |
| commit | e1a5304af2c35ff83819546953309764e24656d4 (patch) | |
| tree | 8992bf2a489e4dc7f6ff3b9661aae5a50d08cab9 | |
| parent | a19a1b970e5dd6983be8660ef6e0f5929fb5a149 (diff) | |
refactor from c to racket
30 files changed, 214 insertions, 1131 deletions
diff --git a/advent-of-code/2023/.gitignore b/advent-of-code/2023/.gitignore deleted file mode 100644 index 5e92c04..0000000 --- a/advent-of-code/2023/.gitignore +++ /dev/null @@ -1,2 +0,0 @@ -part1 -part2 diff --git a/advent-of-code/2023/01/1.rkt b/advent-of-code/2023/01/1.rkt index 58475ed..865e72e 100644 --- a/advent-of-code/2023/01/1.rkt +++ b/advent-of-code/2023/01/1.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (require "../lib/utils.rkt") diff --git a/advent-of-code/2023/01/2.rkt b/advent-of-code/2023/01/2.rkt index 85a0fd6..d00e2f9 100644 --- a/advent-of-code/2023/01/2.rkt +++ b/advent-of-code/2023/01/2.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (require "../lib/utils.rkt") diff --git a/advent-of-code/2023/02/1.rkt b/advent-of-code/2023/02/1.rkt index ab1e4c2..9213079 100644 --- a/advent-of-code/2023/02/1.rkt +++ b/advent-of-code/2023/02/1.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (require "../lib/utils.rkt") diff --git a/advent-of-code/2023/02/2.rkt b/advent-of-code/2023/02/2.rkt index da45d56..88fa571 100644 --- a/advent-of-code/2023/02/2.rkt +++ b/advent-of-code/2023/02/2.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (require "../lib/utils.rkt") diff --git a/advent-of-code/2023/03/1.rkt b/advent-of-code/2023/03/1.rkt new file mode 100644 index 0000000..537d65f --- /dev/null +++ b/advent-of-code/2023/03/1.rkt @@ -0,0 +1,84 @@ +#lang racket/base + +(require "../lib/utils.rkt") +(require "../lib/obj.rkt") + +(define (read-input) + (call-with-input-file "input" + (lambda (fp) + (list->vector (get-lines fp))))) + +(define schema (read-input)) + +(define (char-at line col) + (string-ref (vector-ref schema line) col)) + +(define height (vector-length schema)) +(define width (string-length (vector-ref schema 0))) + +(define make-num (obj-maker 'line 'col 'value 'length)) + +(define (scan-nums) + (define nums '()) + (let loop ((i 0)) + (if (>= i height) + (void) + (let () + (let loop ((j 0)) + (define curline (vector-ref schema i)) + (if (>= j width) + (void) + (let () + (define next 1) + (define (find-next) + (if (or (>= (+ j next) 140) + (not (char-numeric? (char-at i (+ j next))))) + (void) + (let () + (set! next (+ 1 next)) + (find-next)))) + (if (char-numeric? (char-at i j)) + (let () + (find-next) + (define value (string->number (substring curline j (+ j next)))) + (set! nums (cons (make-num i j value next) nums))) + (void)) + (loop (+ j next))))) + (loop (+ 1 i))))) + (reverse nums)) +(define nums (scan-nums)) + +(define (is-symbol? c) + (and (not (char-numeric? c)) + (not (char=? #\. c)))) + +(define (collect-adjacent num) + (define left + (if (= 0 (num 'col)) + '() + (list (char-at (num 'line) (- (num 'col) 1))))) + (define right + (if (= width (+ (num 'col) (num 'length))) + '() + (list (char-at (num 'line) (+ (num 'col) (num 'length)))))) + (define up + (if (= 0 (num 'line)) + '() + (string->list + (substring (vector-ref schema (- (num 'line) 1)) + (max 0 (- (num 'col) 1)) + (min width (+ (num 'col) (num 'length) 1)))))) + (define down + (if (= (- height 1) (num 'line)) + '() + (string->list + (substring (vector-ref schema (+ (num 'line) 1)) + (max 0 (- (num 'col) 1)) + (min width (+ (num 'col) (num 'length) 1)))))) + (append left right up down)) + +(define (is-part-num? num) + (findf is-symbol? (collect-adjacent num))) + +(apply + (map (lambda (x) (x 'value)) + (filter is-part-num? nums)))
\ No newline at end of file diff --git a/advent-of-code/2023/03/2.rkt b/advent-of-code/2023/03/2.rkt new file mode 100644 index 0000000..721a9d1 --- /dev/null +++ b/advent-of-code/2023/03/2.rkt @@ -0,0 +1,106 @@ +#lang racket + +(require "../lib/utils.rkt") +(require "../lib/obj.rkt") + +(define (read-input) + (call-with-input-file "input" + (lambda (fp) + (list->vector (get-lines fp))))) + +(define schema (read-input)) + +(define (char-at line col) + (string-ref (vector-ref schema line) col)) + +(define height (vector-length schema)) +(define width (string-length (vector-ref schema 0))) + +(define make-num (obj-maker 'line 'col 'value 'length)) + +(define (scan-nums) + (define nums '()) + (let loop ((i 0)) + (if (>= i height) + (void) + (let () + (let loop ((j 0)) + (define curline (vector-ref schema i)) + (if (>= j width) + (void) + (let () + (define next 1) + (define (find-next) + (if (or (>= (+ j next) 140) + (not (char-numeric? (char-at i (+ j next))))) + (void) + (let () + (set! next (+ 1 next)) + (find-next)))) + (if (char-numeric? (char-at i j)) + (let () + (find-next) + (define value (string->number (substring curline j (+ j next)))) + (set! nums (cons (make-num i j value next) nums))) + (void)) + (loop (+ j next))))) + (loop (+ 1 i))))) + (reverse nums)) +(define nums (scan-nums)) + +(define (is-symbol? c) + (and (not (char-numeric? c)) + (not (char=? #\. c)))) + +(define (collect-adjacent-positions num) + (define (position-range line start end) + (define delta (- end start)) + (map list (repeat delta line) (range start end))) + (define left + (if (= 0 (num 'col)) + '() + (list (list (num 'line) (- (num 'col) 1))))) + (define right + (if (= width (+ (num 'col) (num 'length))) + '() + (list (list (num 'line) (+ (num 'col) (num 'length)))))) + (define up + (if (= 0 (num 'line)) + '() + (position-range (- (num 'line) 1) + (max 0 (- (num 'col) 1)) + (min width (+ (num 'col) (num 'length) 1))))) + (define down + (if (= (- height 1) (num 'line)) + '() + (position-range (+ (num 'line) 1) + (max 0 (- (num 'col) 1)) + (min width (+ (num 'col) (num 'length) 1))))) + (append left right up down)) + +(define asterisks (make-hash)) + +(define (mark-adj-asterisk num) + (define adjs (collect-adjacent-positions num)) + (define (mark coord) + (if (not (char=? #\* (char-at (car coord) (cadr coord)))) + (void) + (let () + (when (not (hash-has-key? asterisks coord)) + (hash-set! asterisks coord '())) + (hash-set! asterisks coord (cons (num 'value) (hash-ref asterisks coord)))))) + (for-each mark adjs)) + +(for-each mark-adj-asterisk nums) + +(define aster-list (hash->list asterisks)) + +(define (is-gear? aster) + (define nums-list (cdr aster)) + (= 2 (length nums-list))) + +(define (power aster) + (define nums-list (cdr aster)) + (* (car nums-list) (cadr nums-list))) + +(apply + (map power (filter is-gear? aster-list))) diff --git a/advent-of-code/2023/03/Makefile b/advent-of-code/2023/03/Makefile deleted file mode 100644 index 44480b6..0000000 --- a/advent-of-code/2023/03/Makefile +++ /dev/null @@ -1,14 +0,0 @@ -all: run - -run: part1 part2 - ./part1 - ./part2 - -part1: part1.c - gcc -g -I../lib/ ../lib/*.c part1.c -o part1 - -part2: part2.c - gcc -g -I../lib/ ../lib/*.c part2.c -o part2 - -clean: - rm part1 part2 diff --git a/advent-of-code/2023/03/part1.c b/advent-of-code/2023/03/part1.c deleted file mode 100644 index 4ae9ef9..0000000 --- a/advent-of-code/2023/03/part1.c +++ /dev/null @@ -1,130 +0,0 @@ -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <ctype.h> -#include <assert.h> - -#include "vec.h" -#include "str.h" - -void* read_input() { - FILE* fp = fopen("./input", "r"); - void *vec = new_vec(); - while(1) { - char *line = fgetline(fp); - if (line == NULL) break; - char *stripped = str_strip(line); - if (strlen(stripped) == 0) break; - vec_push_back(vec, stripped); - } - return vec; -} - -typedef struct { - int line; - int column; - int value; - int length; -} num_t; - -void *parse_nums(void *schema) { - void *nums = new_vec(); - int j = 0; - const int IN_NUM = 0, IDLE = 1; - int state = IDLE; - for (int i = 0; i < vec_size(schema); i++) { - char *line = vec_get(schema, i); - int line_len = strlen(line); - int value = 0; - int length = 0; - state = IDLE; - j = 0; - while (1) { - char c = '.'; - if (j < line_len) c = line[j]; - if (state == IDLE) { - if (isdigit(c)) { - state = IN_NUM; - continue; - } else { - j++; - if (j >= line_len) break; - continue; - } - } else if (state == IN_NUM) { - if (isdigit(c)) { - value = value * 10 + (c - '0'); - length++; - j++; - continue; - } else { - num_t *n = malloc(sizeof(num_t)); - *n = (num_t){ - .line = i, - .column = j - length, - .value = value, - .length = length - }; - vec_push_back(nums, n); - value = 0; - length = 0; - state = IDLE; - if (j >= line_len) break; - continue; - } - } - } - } - return nums; -} - -int is_symbol(char c) { - if (c >= '0' && c <= '9') return 0; - if (c == '.') return 0; - return 1; -} - -int is_a_part(void *schema, num_t *num) { - int line_len = vec_size(schema); - int col_len = strlen(vec_get(schema, 0)); - for (int i = num->column - 1; i < num->column + num->length + 1; i++) { - if (num->line - 1 < 0) continue; - if (i < 0 || i >= col_len) continue; - if (is_symbol(((char*)vec_get(schema, num->line - 1))[i])) { - return 1; - } - } - for (int i = num->column - 1; i < num->column + num->length + 1; i++) { - if (num->line + 1 >= line_len) continue; - if (i < 0 || i >= col_len) continue; - if (is_symbol(((char*)vec_get(schema, num->line + 1))[i])) { - return 1; - } - } - if (num->column - 1 >= 0) { - if (is_symbol(((char*)vec_get(schema, num->line))[num->column - 1])) { - return 1; - } - } - if (num->column + num->length < col_len) { - char *line = vec_get(schema, num->line); - if (is_symbol(line[num->column + num->length])) { - return 1; - } - } - return 0; -} - -int main() { - void *schema = read_input(); - void *nums = parse_nums(schema); - int sum = 0; - for (int i = 0; i < vec_size(nums); i++) { - num_t *num = vec_get(nums, i); - if (is_a_part(schema, num)) { - sum += num->value; - } - } - printf("%d\n", sum); - return 0; -} diff --git a/advent-of-code/2023/03/part2.c b/advent-of-code/2023/03/part2.c deleted file mode 100644 index a5ab825..0000000 --- a/advent-of-code/2023/03/part2.c +++ /dev/null @@ -1,149 +0,0 @@ -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <ctype.h> -#include <assert.h> - -#include "vec.h" -#include "str.h" -#include "map.h" - -void* read_input() { - FILE* fp = fopen("./input", "r"); - void *vec = new_vec(); - while(1) { - char *line = fgetline(fp); - if (line == NULL) break; - char *stripped = str_strip(line); - if (strlen(stripped) == 0) break; - vec_push_back(vec, stripped); - } - return vec; -} - -typedef struct { - int line; - int column; - int value; - int length; -} num_t; - -char *compose_key(int x, int y) { - void* ss = new_ss(); - ss_add(ss, "%d,%d", x, y); - return ss_cstr(ss); -} - -void *parse_nums(void *schema) { - void *nums = new_vec(); - int j = 0; - const int IN_NUM = 0, IDLE = 1; - int state = IDLE; - for (int i = 0; i < vec_size(schema); i++) { - char *line = vec_get(schema, i); - int line_len = strlen(line); - int value = 0; - int length = 0; - state = IDLE; - j = 0; - while (1) { - char c = '.'; - if (j < line_len) c = line[j]; - if (state == IDLE) { - if (isdigit(c)) { - state = IN_NUM; - continue; - } else { - j++; - if (j >= line_len) break; - continue; - } - } else if (state == IN_NUM) { - if (isdigit(c)) { - value = value * 10 + (c - '0'); - length++; - j++; - continue; - } else { - num_t *n = malloc(sizeof(num_t)); - *n = (num_t){ - .line = i, - .column = j - length, - .value = value, - .length = length - }; - vec_push_back(nums, n); - value = 0; - length = 0; - state = IDLE; - if (j >= line_len) break; - continue; - } - } - } - } - return nums; -} - -char char_at(void *schema, int line, int column) { - char *buf = vec_get(schema, line); - return buf[column]; -} - -void mark_asterisks(void *asterisks, num_t *num, int x, int y) { - const char *key = compose_key(x, y); - void *num_list = dict_get(asterisks, key); - if (num_list == NULL) { - num_list = new_vec(); - dict_set(asterisks, key, num_list); - } - vec_push_back(num_list, num); -} - -void find_asterisks(void *schema, void *asterisks, num_t *num) { - int line_len = vec_size(schema); - int col_len = strlen(vec_get(schema, 0)); - for (int i = num->column - 1; i < num->column + num->length + 1; i++) { - if (num->line - 1 < 0) continue; - if (i < 0 || i >= col_len) continue; - char c = char_at(schema, num->line - 1, i); - if (c == '*') mark_asterisks(asterisks, num, num->line - 1, i); - } - for (int i = num->column - 1; i < num->column + num->length + 1; i++) { - if (num->line + 1 >= line_len) continue; - if (i < 0 || i >= col_len) continue; - char c = char_at(schema, num->line + 1, i); - if (c == '*') mark_asterisks(asterisks, num, num->line + 1, i); - } - if (num->column - 1 >= 0) { - char c = char_at(schema, num->line, num->column - 1); - if (c == '*') mark_asterisks(asterisks, num, num->line, num->column - 1); - } - if (num->column + num->length < col_len) { - char c = char_at(schema, num->line, num->column + num->length); - if (c == '*') mark_asterisks(asterisks, num, num->line, num->column + num->length); - } -} - -int main() { - void *schema = read_input(); - void *nums = parse_nums(schema); - int sum = 0; - void *asterisks = new_dict(); - for (int i = 0; i < vec_size(nums); i++) { - num_t *num = vec_get(nums, i); - find_asterisks(schema, asterisks, num); - } - for (void *iter = dict_begin(asterisks); - iter != NULL; - iter = dict_next(asterisks, iter)) { - void *list = dict_iter_value(iter); - if (vec_size(list) == 2) { - num_t* n1 = vec_get(list, 0); - num_t* n2 = vec_get(list, 1); - sum += n1->value * n2->value; - } - } - printf("%d\n", sum); - return 0; -} diff --git a/advent-of-code/2023/04/1.rkt b/advent-of-code/2023/04/1.rkt index a1edde2..5210420 100644 --- a/advent-of-code/2023/04/1.rkt +++ b/advent-of-code/2023/04/1.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (require "../lib/utils.rkt") (require "../lib/obj.rkt") diff --git a/advent-of-code/2023/04/2.rkt b/advent-of-code/2023/04/2.rkt index a9d751f..479f9d7 100644 --- a/advent-of-code/2023/04/2.rkt +++ b/advent-of-code/2023/04/2.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (require "../lib/utils.rkt") (require "../lib/obj.rkt") diff --git a/advent-of-code/2023/05/1.rkt b/advent-of-code/2023/05/1.rkt index f0ad5ed..411a36b 100755 --- a/advent-of-code/2023/05/1.rkt +++ b/advent-of-code/2023/05/1.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (define port (open-input-file "input")) diff --git a/advent-of-code/2023/05/2.rkt b/advent-of-code/2023/05/2.rkt index 5024c1e..9a0233f 100755 --- a/advent-of-code/2023/05/2.rkt +++ b/advent-of-code/2023/05/2.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (define port (open-input-file "input")) diff --git a/advent-of-code/2023/06/1.rkt b/advent-of-code/2023/06/1.rkt index ea0d013..92d0bf6 100644 --- a/advent-of-code/2023/06/1.rkt +++ b/advent-of-code/2023/06/1.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (define in (open-input-file "input")) diff --git a/advent-of-code/2023/06/2.rkt b/advent-of-code/2023/06/2.rkt index 5d124e0..cc381cf 100644 --- a/advent-of-code/2023/06/2.rkt +++ b/advent-of-code/2023/06/2.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (define in (open-input-file "input")) diff --git a/advent-of-code/2023/07/part1.rkt b/advent-of-code/2023/07/1.rkt index a22571d..635d6be 100644 --- a/advent-of-code/2023/07/part1.rkt +++ b/advent-of-code/2023/07/1.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (define input (with-input-from-file "input" diff --git a/advent-of-code/2023/07/part2.rkt b/advent-of-code/2023/07/2.rkt index 50d9526..e88f949 100644 --- a/advent-of-code/2023/07/part2.rkt +++ b/advent-of-code/2023/07/2.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (define input (with-input-from-file "input" diff --git a/advent-of-code/2023/lib/map.c b/advent-of-code/2023/lib/map.c deleted file mode 100644 index 846033e..0000000 --- a/advent-of-code/2023/lib/map.c +++ /dev/null @@ -1,90 +0,0 @@ -#include "map.h" -#include "rb_tree.h" - -#include <string.h> - -typedef int (*rb_cmp_t)(void*, void*); - -void* new_map(cmp_t compare) { - rb_tree_t *tree = malloc(sizeof(rb_tree_t)); - rb_cmp_t cmp = (rb_cmp_t)compare; - *tree = (rb_tree_t){NULL, cmp, NULL}; - return tree; -} - -void map_set(void* self, void* key, void* value) { - node_entry_t *iter = rb_tree_find(self, &key); - if (iter == NULL) { - iter = malloc(sizeof(*iter)); - iter->key = key; - iter->value = value; - rb_tree_insert(self, iter); - } else { - iter->value = value; - } -} - -void* map_get(void* self, void* key) { - node_entry_t *iter = rb_tree_find(self, &key); - if (iter == NULL) return NULL; - return iter->value; -} - -void map_erase(void* self, void* key) { - rb_tree_remove(self, key); -} - -void* map_begin(void *self) { - return rb_tree_min(self); -} - -void* map_next(void *self, void *iter) { - return rb_tree_next(self, iter); -} - -void* map_iter_key(void* iter_) { - node_entry_t *iter = iter_; - return iter->key; -} - -void* map_iter_value(void* iter_) { - node_entry_t *iter = iter_; - return iter->value; -} - -static int dict_cmp(void **a, void** b) { - return strcmp(*a, *b); -} -void* new_dict() { - return new_map(dict_cmp); -} - -void dict_set(void* self, const char *key, void* value) { - map_set(self, (void*)key, value); -} - -void* dict_get(void* self, const char* key) { - return map_get(self, (void*)key); -} - -void dict_erase(void* self, const char* key) { - map_erase(self, (void*)key); -} - -void* dict_begin(void *self) { - return map_begin(self); -} - -void* dict_next(void *self, void *iter) { - return map_next(self, iter); -} - -const char* dict_iter_key(void* iter) { - return map_iter_key(iter); -} - -void* dict_iter_value(void* iter) { - return map_iter_value(iter); -} - - diff --git a/advent-of-code/2023/lib/map.h b/advent-of-code/2023/lib/map.h deleted file mode 100644 index c54048c..0000000 --- a/advent-of-code/2023/lib/map.h +++ /dev/null @@ -1,33 +0,0 @@ -#ifndef MAP_H_ -#define MAP_H_ - -#include "rb_tree.h" - -typedef struct { - rb_node_t node; - void *key; - void *value; -} node_entry_t; -typedef int (*cmp_t)(void** a, void** b); - -void* new_map(cmp_t compare); -void map_set(void* self, void* key, void* value); -void* map_get(void* self, void* key); -void map_erase(void* self, void* key); - -void* map_begin(void *self); -void* map_next(void *self, void *iter); -void* map_iter_key(void* iter); -void* map_iter_value(void* iter); - -void* new_dict(); -void dict_set(void* self, const char *key, void* value); -void* dict_get(void* self, const char* key); -void dict_erase(void* self, const char* key); - -void* dict_begin(void *self); -void* dict_next(void *self, void *iter); -const char* dict_iter_key(void* iter); -void* dict_iter_value(void* iter); - -#endif diff --git a/advent-of-code/2023/lib/obj.rkt b/advent-of-code/2023/lib/obj.rkt index 9217976..578ea36 100644 --- a/advent-of-code/2023/lib/obj.rkt +++ b/advent-of-code/2023/lib/obj.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base (provide obj-maker obj-set diff --git a/advent-of-code/2023/lib/rb_tree.c b/advent-of-code/2023/lib/rb_tree.c deleted file mode 100644 index 5aa7905..0000000 --- a/advent-of-code/2023/lib/rb_tree.c +++ /dev/null @@ -1,378 +0,0 @@ -// Copyright (C) 2023 Mistivia <i@mistivia.com> -// Licensed under GPLv3. See LICENSE for details. - -/* - * Copyright 2002 Niels Provos <provos@citi.umich.edu> - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -#include "rb_tree.h" - -#define RED 1 -#define BLACK 0 - -static rb_node_t *rb_tree_minmax(rb_tree_t *, int); -void *rb_tree_min(rb_tree_t *head) { return rb_tree_minmax(head, -1); } -void *rb_tree_max(rb_tree_t *head) { return rb_tree_minmax(head, 1); } - -void *rb_tree_left(void *node) { - rb_node_t *elm = node; - if (node == NULL) return NULL; - return elm->entry.rbe_left; -} -void *rb_tree_right(void *node) { - rb_node_t *elm = node; - if (node == NULL) return NULL; - return elm->entry.rbe_right; -} -void *rb_tree_parent(void *node) { - rb_node_t *elm = node; - if (node == NULL) return NULL; - return elm->entry.rbe_parent; -} - -static void augment(rb_tree_t *head, rb_node_t *elm) { - if (head->augment != NULL) head->augment(elm); -} - -static void rb_tree_insert_color(rb_tree_t *head, rb_node_t *elm); -static void rb_tree_remove_color(rb_tree_t *head, rb_node_t *parent, - rb_node_t *elm); - -static void rotate_left(rb_tree_t *head, rb_node_t *elm) { - rb_node_t *tmp = elm->entry.rbe_right; - if ((elm->entry.rbe_right = tmp->entry.rbe_left)) { - tmp->entry.rbe_left->entry.rbe_parent = elm; - } - augment(head, elm); - if ((tmp->entry.rbe_parent = elm->entry.rbe_parent)) { - if (elm == elm->entry.rbe_parent->entry.rbe_left) - elm->entry.rbe_parent->entry.rbe_left = tmp; - else - elm->entry.rbe_parent->entry.rbe_right = tmp; - } else { - head->rbh_root = tmp; - } - tmp->entry.rbe_left = elm; - elm->entry.rbe_parent = tmp; - augment(head, tmp); - if (tmp->entry.rbe_parent) { - augment(head, tmp->entry.rbe_parent); - } -} - -static void rotate_right(rb_tree_t *head, rb_node_t *elm) { - rb_node_t *tmp = elm->entry.rbe_left; - if ((elm->entry.rbe_left = tmp->entry.rbe_right)) { - tmp->entry.rbe_right->entry.rbe_parent = elm; - } - augment(head, elm); - if ((tmp->entry.rbe_parent = elm->entry.rbe_parent)) { - if (elm == elm->entry.rbe_parent->entry.rbe_left) - elm->entry.rbe_parent->entry.rbe_left = tmp; - else - elm->entry.rbe_parent->entry.rbe_right = tmp; - } else { - head->rbh_root = tmp; - } - tmp->entry.rbe_right = elm; - elm->entry.rbe_parent = tmp; - augment(head, tmp); - if (tmp->entry.rbe_parent) { - augment(head, tmp->entry.rbe_parent); - } -} - -static void rb_tree_insert_color(rb_tree_t *head, rb_node_t *elm) { - rb_node_t *parent, *gparent, *tmp; - while ((parent = elm->entry.rbe_parent) && parent->entry.rbe_color == 1) { - gparent = parent->entry.rbe_parent; - if (parent == gparent->entry.rbe_left) { - tmp = gparent->entry.rbe_right; - if (tmp && tmp->entry.rbe_color == 1) { - tmp->entry.rbe_color = BLACK; - parent->entry.rbe_color = BLACK; - gparent->entry.rbe_color = RED; - elm = gparent; - continue; - } - if (parent->entry.rbe_right == elm) { - rotate_left(head, parent); - tmp = parent; - parent = elm; - elm = tmp; - } - parent->entry.rbe_color = BLACK; - gparent->entry.rbe_color = RED; - rotate_right(head, gparent); - } else { - tmp = gparent->entry.rbe_left; - if (tmp && tmp->entry.rbe_color == 1) { - tmp->entry.rbe_color = BLACK; - parent->entry.rbe_color = BLACK; - gparent->entry.rbe_color = RED; - ; - elm = gparent; - continue; - } - if (parent->entry.rbe_left == elm) { - rotate_right(head, parent); - tmp = parent; - parent = elm; - elm = tmp; - } - parent->entry.rbe_color = BLACK; - gparent->entry.rbe_color = RED; - rotate_left(head, gparent); - } - } - head->rbh_root->entry.rbe_color = BLACK; -} - -static void rb_tree_remove_color(rb_tree_t *head, rb_node_t *parent, - rb_node_t *elm) { - rb_node_t *tmp; - while ((elm == NULL || elm->entry.rbe_color == 0) && - elm != head->rbh_root) { - if (parent->entry.rbe_left == elm) { - tmp = parent->entry.rbe_right; - if (tmp->entry.rbe_color == 1) { - tmp->entry.rbe_color = BLACK; - parent->entry.rbe_color = RED; - rotate_left(head, parent); - tmp = parent->entry.rbe_right; - } - if ((tmp->entry.rbe_left == NULL || - tmp->entry.rbe_left->entry.rbe_color == 0) && - (tmp->entry.rbe_right == NULL || - tmp->entry.rbe_right->entry.rbe_color == 0)) { - tmp->entry.rbe_color = RED; - elm = parent; - parent = elm->entry.rbe_parent; - } else { - if (tmp->entry.rbe_right == NULL || - tmp->entry.rbe_right->entry.rbe_color == 0) { - rb_node_t *oleft; - if ((oleft = tmp->entry.rbe_left)) - oleft->entry.rbe_color = BLACK; - tmp->entry.rbe_color = RED; - rotate_right(head, tmp); - tmp = parent->entry.rbe_right; - } - tmp->entry.rbe_color = parent->entry.rbe_color; - parent->entry.rbe_color = BLACK; - if (tmp->entry.rbe_right) - tmp->entry.rbe_right->entry.rbe_color = BLACK; - rotate_left(head, parent); - elm = head->rbh_root; - break; - } - } else { - tmp = parent->entry.rbe_left; - if (tmp->entry.rbe_color == 1) { - tmp->entry.rbe_color = BLACK; - parent->entry.rbe_color = RED; - rotate_right(head, parent); - tmp = parent->entry.rbe_left; - } - if ((tmp->entry.rbe_left == NULL || - tmp->entry.rbe_left->entry.rbe_color == 0) && - (tmp->entry.rbe_right == NULL || - tmp->entry.rbe_right->entry.rbe_color == 0)) { - tmp->entry.rbe_color = RED; - elm = parent; - parent = elm->entry.rbe_parent; - } else { - if (tmp->entry.rbe_left == NULL || - tmp->entry.rbe_left->entry.rbe_color == 0) { - rb_node_t *oright; - if ((oright = tmp->entry.rbe_right)) - oright->entry.rbe_color = BLACK; - tmp->entry.rbe_color = RED; - rotate_left(head, tmp); - tmp = parent->entry.rbe_left; - } - tmp->entry.rbe_color = parent->entry.rbe_color; - parent->entry.rbe_color = BLACK; - if (tmp->entry.rbe_left) - tmp->entry.rbe_left->entry.rbe_color = BLACK; - rotate_right(head, parent); - elm = head->rbh_root; - break; - } - } - } - if (elm) elm->entry.rbe_color = BLACK; -} - -void rb_tree_remove(rb_tree_t *head, void *elmv) { - rb_node_t *elm = elmv; - rb_node_t *child, *parent; - int color; - if (elm->entry.rbe_left == NULL) - child = elm->entry.rbe_right; - else if (elm->entry.rbe_right == NULL) - child = elm->entry.rbe_left; - else { - rb_node_t *old = elm, *left; - elm = elm->entry.rbe_right; - while ((left = elm->entry.rbe_left)) - elm = left; - child = elm->entry.rbe_right; - parent = elm->entry.rbe_parent; - color = elm->entry.rbe_color; - if (child) child->entry.rbe_parent = parent; - if (parent) { - if (parent->entry.rbe_left == elm) - parent->entry.rbe_left = child; - else - parent->entry.rbe_right = child; - augment(head, parent); - } else - head->rbh_root = child; - if (elm->entry.rbe_parent == old) parent = elm; - elm->entry = old->entry; - if (old->entry.rbe_parent) { - if ((old->entry.rbe_parent)->entry.rbe_left == old) - (old->entry.rbe_parent)->entry.rbe_left = elm; - else - (old->entry.rbe_parent)->entry.rbe_right = elm; - augment(head, old->entry.rbe_parent); - } else - head->rbh_root = elm; - old->entry.rbe_left->entry.rbe_parent = elm; - if (old->entry.rbe_right) old->entry.rbe_right->entry.rbe_parent = elm; - if (parent) { - left = parent; - if (head->augment != NULL) { - do { - augment(head, left); - } while ((left = left->entry.rbe_parent)); - } - } - goto color; - } - parent = elm->entry.rbe_parent; - color = elm->entry.rbe_color; - if (child) child->entry.rbe_parent = parent; - if (parent) { - if (parent->entry.rbe_left == elm) - parent->entry.rbe_left = child; - else - parent->entry.rbe_right = child; - rb_node_t *goback = parent; - if (head->augment != NULL) { - do { - augment(head, goback); - } while ((goback = goback->entry.rbe_parent)); - } - } else - head->rbh_root = child; -color: - if (color == 0) rb_tree_remove_color(head, parent, child); -} - -void *rb_tree_insert(rb_tree_t *head, void *elmv) { - rb_node_t *elm = elmv; - rb_node_t *tmp; - rb_node_t *parent = NULL; - int comp = 0; - tmp = head->rbh_root; - while (tmp) { - parent = tmp; - comp = head->cmp((void *)elm->content, (void *)parent->content); - if (comp < 0) - tmp = tmp->entry.rbe_left; - else if (comp > 0) - tmp = tmp->entry.rbe_right; - else - return tmp; - } - elm->entry.rbe_parent = parent; - elm->entry.rbe_left = elm->entry.rbe_right = NULL; - elm->entry.rbe_color = RED; - if (parent != NULL) { - if (comp < 0) - parent->entry.rbe_left = elm; - else - parent->entry.rbe_right = elm; - rb_node_t *goback = parent; - if (head->augment != NULL) { - do { - augment(head, goback); - } while ((goback = goback->entry.rbe_parent)); - } - } else - head->rbh_root = elm; - rb_tree_insert_color(head, elm); - return (NULL); -} - -void *rb_tree_find(rb_tree_t *head, void *key) { - rb_node_t *tmp = head->rbh_root; - int comp; - while (tmp) { - comp = head->cmp(key, (void *)tmp->content); - if (comp < 0) - tmp = tmp->entry.rbe_left; - else if (comp > 0) - tmp = tmp->entry.rbe_right; - else - return tmp; - } - return (NULL); -} - -void *rb_tree_next(rb_tree_t *head, void *elmv) { - rb_node_t *elm = elmv; - if (elm->entry.rbe_right) { - elm = elm->entry.rbe_right; - while (elm->entry.rbe_left) - elm = elm->entry.rbe_left; - } else { - if (elm->entry.rbe_parent && - (elm == (elm->entry.rbe_parent)->entry.rbe_left)) - elm = elm->entry.rbe_parent; - else { - while (elm->entry.rbe_parent && - (elm == (elm->entry.rbe_parent)->entry.rbe_right)) - elm = elm->entry.rbe_parent; - elm = elm->entry.rbe_parent; - } - } - return elm; -} - -static rb_node_t *rb_tree_minmax(rb_tree_t *head, int val) { - rb_node_t *tmp = head->rbh_root; - rb_node_t *parent = NULL; - while (tmp) { - parent = tmp; - if (val < 0) - tmp = tmp->entry.rbe_left; - else - tmp = tmp->entry.rbe_right; - } - return parent; -}; - diff --git a/advent-of-code/2023/lib/rb_tree.h b/advent-of-code/2023/lib/rb_tree.h deleted file mode 100644 index 2096ff6..0000000 --- a/advent-of-code/2023/lib/rb_tree.h +++ /dev/null @@ -1,64 +0,0 @@ -// Copyright (C) 2023 Mistivia <i@mistivia.com> -// Licensed under GPLv3. See LICENSE for details. - -/* - * Copyright 2002 Niels Provos <provos@citi.umich.edu> - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -#ifndef RB_TREE_H_ -#define RB_TREE_H_ - -#include <stdlib.h> - -struct rb_node { - struct { - struct rb_node *rbe_left; - struct rb_node *rbe_right; - struct rb_node *rbe_parent; - int rbe_color; - } entry; - char content[0]; -}; -typedef struct rb_node rb_node_t; - -struct rb_tree { - rb_node_t *rbh_root; - int (*cmp)(void *k1, void *k2); - void (*augment)(void *elm); -}; -typedef struct rb_tree rb_tree_t; - -void rb_tree_remove(rb_tree_t *, void *iter); - -// return a iterator -void *rb_tree_insert(rb_tree_t *, void *treenode); -void *rb_tree_find(rb_tree_t *, void *val); -void *rb_tree_next(rb_tree_t *, void *iter); -void *rb_tree_min(rb_tree_t *); -void *rb_tree_max(rb_tree_t *); -void *rb_tree_left(void *node); -void *rb_tree_right(void *node); -void *rb_tree_parent(void *node); - -#endif diff --git a/advent-of-code/2023/lib/str.c b/advent-of-code/2023/lib/str.c deleted file mode 100644 index 511e45b..0000000 --- a/advent-of-code/2023/lib/str.c +++ /dev/null @@ -1,143 +0,0 @@ -// Copyright (C) 2023 Mistivia <i@mistivia.com> -// Licensed under GPLv3. See LICENSE for details. - -#include "str.h" - -#include <ctype.h> -#include <stdarg.h> -#include <stdbool.h> -#include <stddef.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -#include "vec.h" - -void *str_split(const char *str, char delim) { - void* ret = new_vec(); - - if (str == NULL) return NULL; - if (*str == '\n') { - return ret; - } - int count = 0; - const char *begin = str; - for (const char *p = str; *p != '\0'; p++) { - if (*p != delim && !(delim == '\0' && isspace(*p))) { - continue; - } - int size = p - begin; - if (size > 0) count++; - } - count++; - - begin = str; - int i = 0; - bool finished = false; - for (const char *p = str; !finished; p++) { - if (*p == '\0') finished = true; - if (*p != delim && *p != '\0' && !(delim == '\0' && isspace(*p))) { - continue; - } - int size = p - begin; - if (size == 0) { - begin = p + 1; - continue; - } - char *buf = malloc(sizeof(char) * (size + 1)); - buf[size] = '\0'; - memcpy(buf, begin, size * sizeof(char)); - begin = p + 1; - vec_push_back(ret, buf); - } - return ret; -} - -char *str_strip(const char *str) { - if (str == NULL) return NULL; - int len = strlen(str); - const char *begin = str; - const char *end = str + len - 1; - while (isspace(*begin) && begin < end) { - begin++; - } - while (isspace(*end) && end >= begin) { - end--; - } - len = end - begin + 1; - char *buf = malloc(sizeof(char) * (len) + 1); - buf[len] = '\0'; - memcpy(buf, begin, len); - return buf; -} - -typedef struct { - size_t size; - size_t cap; - char *buf; -} str_builder_t; - -// string stream -void* new_ss() { - str_builder_t *self = malloc(sizeof(str_builder_t)); - *self = (str_builder_t){.size = 0, .cap = 16}; - self->buf = malloc(sizeof(char) * 17); - return self; -} - -static void ss_reserve(str_builder_t *self, int extra) { - if (self->size + extra <= self->cap) { - return; - } - int new_cap = (self->size + extra) * 2; - self->buf = realloc(self->buf, new_cap + 1); - memset(self->buf + self->cap, 0, new_cap - self->cap + 1); - self->cap = new_cap; -} - -void ss_add(void *self_, char *format, ...) { - str_builder_t *self = self_; - va_list va1; - va_list va2; - va_start(va1, format); - va_copy(va2, va1); - int size = vsnprintf(NULL, 0, format, va1); - ss_reserve(self, size); - vsnprintf(self->buf + self->size, self->cap - self->size + 1, format, va2); - self->size += size; -} - -void ss_addc(void *self_, char c) { - str_builder_t *self = self_; - ss_reserve(self, 1); - self->buf[self->size] = c; - self->size++; -} - -char *ss_cstr(void *self_) { - str_builder_t *self = self_; - return self->buf; -} - -size_t ss_size(void *self_) { - str_builder_t *self = self_; - return self->size; -} - -char *fgetline(FILE *fp) { - void *ss = new_ss(); - while (true) { - int c = fgetc(fp); - if (c == EOF && ss_size(ss) == 0) return NULL; - if (c != EOF) ss_addc(ss, c); - if (c == EOF || c == '\n') return ss_cstr(ss); - } - return NULL; -} - -int fpeek(FILE *fp) { - int c = fgetc(fp); - if (c == EOF) return c; - ungetc(c, fp); - return c; -} diff --git a/advent-of-code/2023/lib/str.h b/advent-of-code/2023/lib/str.h deleted file mode 100644 index 214e297..0000000 --- a/advent-of-code/2023/lib/str.h +++ /dev/null @@ -1,24 +0,0 @@ -// Copyright (C) 2023 Mistivia <i@mistivia.com> -// Licensed under GPLv3. See LICENSE for details. - -#ifndef DYMC_STR_H_ -#define DYMC_STR_H_ - -#include <stdio.h> -#include <stddef.h> - -char *str_strip(const char *str); -void* str_split(const char *str, char delim); - - -// string stream -void* new_ss(); -void ss_add(void *self, char *format, ...); -void ss_addc(void *self, char c); -char *ss_cstr(void *self); -size_t ss_size(void* self); - -char *fgetline(FILE *fp); -int fpeek(FILE *fp); - -#endif diff --git a/advent-of-code/2023/lib/utils.rkt b/advent-of-code/2023/lib/utils.rkt index 946bb86..40c6f6b 100644 --- a/advent-of-code/2023/lib/utils.rkt +++ b/advent-of-code/2023/lib/utils.rkt @@ -1,7 +1,14 @@ -#lang racket +#lang racket/base (provide get-lines - enumerate) + enumerate + repeat) + +(define (repeat n e) + (let loop ((i 0) (ret '())) + (if (>= i n) + ret + (loop (+ 1 i) (cons e ret))))) (define (get-lines fp) (let loop ((lines '())) diff --git a/advent-of-code/2023/lib/vec.c b/advent-of-code/2023/lib/vec.c deleted file mode 100644 index c3d8a0a..0000000 --- a/advent-of-code/2023/lib/vec.c +++ /dev/null @@ -1,72 +0,0 @@ -#include "vec.h" - -#include <string.h> -#include "stdlib.h" - -struct vec { - size_t length; - size_t capacity; - void** buf; -}; - -static void vec_enlarge(struct vec* self) { - self->buf = realloc(self->buf, self->capacity * sizeof(void*) * 2); - self->capacity = self->capacity * 2; -} - -void *new_vec() { - struct vec* vec = malloc(sizeof(struct vec)); - vec->length = 0; - vec->capacity = 16; - vec->buf = malloc(16 * sizeof(void*)); - return vec; -} - -void vec_push_back(void *self_, void* obj) { - struct vec *self = self_; - if (self->length == self->capacity) vec_enlarge(self); - self->buf[self->length] = obj; - self->length++; -} - -void* vec_get(void *self_, size_t n) { - struct vec *self = self_; - if (n < 0 || n >= self->length) return NULL; - return self->buf[n]; -} - - -void vec_erase(void *self_, size_t n) { - struct vec *self = self_; - if (self->length <= n) { - return; - } - memmove(self->buf + n, self->buf + n + 1, (self->length - n - 1) * sizeof(void*)); - self->length--; -} - -size_t vec_size(void *self_) { - struct vec *self = self_; - return self->length; -} - -void vec_reserve(void *self_, size_t n) { - struct vec *self = self_; - if (n <= self->capacity) { - return; - } - self->buf = malloc(sizeof(void*) * n); - self->capacity = n; -} - -void vec_insert(void *self_, size_t pos, void *obj) { - struct vec *self = self_; - if (self->length == self->capacity) { - vec_enlarge(self); - } - if (pos > self->length || pos < 0) return; - memmove(self->buf + pos + 1, self->buf + pos, sizeof(void*) * (self->length - pos)); - self->buf[pos] = obj; - self->length++; -} - diff --git a/advent-of-code/2023/lib/vec.h b/advent-of-code/2023/lib/vec.h deleted file mode 100644 index 5778689..0000000 --- a/advent-of-code/2023/lib/vec.h +++ /dev/null @@ -1,15 +0,0 @@ -#ifndef VEC_H_ -#define VEC_H_ - -#include <stddef.h> - -void *new_vec(); -void vec_push_back(void *self, void* obj); -void* vec_get(void *self, size_t n); -size_t vec_length(void *self); -void vec_erase(void *self, size_t n); -size_t vec_size(void* self); -void vec_reserve(void* self, size_t n); -void vec_insert(void* self, size_t pos, void* obj); - -#endif diff --git a/codewars/6-kyu/pyramid-array/solution.rkt b/codewars/6-kyu/pyramid-array/solution.rkt index 0d6a00b..4973db9 100644 --- a/codewars/6-kyu/pyramid-array/solution.rkt +++ b/codewars/6-kyu/pyramid-array/solution.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base ;; https://www.codewars.com/kata/515f51d438015969f7000013 diff --git a/codewars/7-kyu/a-rule-of-divisibility-by-7/solution.rkt b/codewars/7-kyu/a-rule-of-divisibility-by-7/solution.rkt index 6859107..a8172a1 100644 --- a/codewars/7-kyu/a-rule-of-divisibility-by-7/solution.rkt +++ b/codewars/7-kyu/a-rule-of-divisibility-by-7/solution.rkt @@ -1,4 +1,4 @@ -#lang racket +#lang racket/base ;; https://www.codewars.com/kata/55e6f5e58f7817808e00002e |
