Skip to content

Instantly share code, notes, and snippets.

@htruong
Created December 24, 2020 06:30
Show Gist options
  • Save htruong/2481e47da2a94ad7c472c4b214349c25 to your computer and use it in GitHub Desktop.
Save htruong/2481e47da2a94ad7c472c4b214349c25 to your computer and use it in GitHub Desktop.
HT_TANGXONG.C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Compile:
// Cross compile on Linux:
// open-watcom.owcc-dos -bdos -o HT_HEART.EXE HT_TANGXONG.C
// On openwatcom on DOS:
// wcl386 HT_TANGXONG.C
void addToSortedArray(int * arr_len, int *arr, int el) {
int lower, upper, guess;
int i;
if (*arr_len == 0 || el < arr[0]) {
//printf("Add %d at beginning\n", el);
for (i = *arr_len; i > 0; i--) {
arr[i] = arr[i-1];
}
arr[0] = el;
*arr_len = (*arr_len)+1;
return;
}
if (el > arr[(*arr_len) - 1]) {
//printf("Add %d at end\n", el);
arr[(*arr_len)] = el;
*arr_len = (*arr_len)+1;
return;
}
lower = 0;
upper = (*arr_len);
guess = (lower + upper) / 2;
//printf("Guess = %d val = %d\n", guess, arr[guess]);
while (! ( el >= arr[guess] && el <= arr[guess + 1] )) {
if (el < arr[guess]) {
upper = guess;
} else {
lower = guess;
}
guess = (lower + upper) / 2;
//printf("Guess = %d val = %d\n", guess, arr[guess]);
}
guess++;
//printf("Add %d at position %d\n", el, guess);
for (i = *arr_len; i > guess; i--) {
arr[i] = arr[i-1];
}
arr[guess] = el;
(*arr_len)++;
return;
}
void removeOnce(int * arr_len, int *arr, int el) {
int lower, upper, guess;
int i;
lower = 0;
upper = (*arr_len);
guess = (lower + upper) / 2;
//printf("Guess = %d val = %d\n", guess, arr[guess]);
while ( arr[guess] != el ) {
if (arr[guess] > el) {
upper = guess;
} else {
lower = guess;
}
guess = (lower + upper) / 2;
//printf("Guess = %d val = %d\n", guess, arr[guess]);
}
//printf("Remove %d at position %d val = %d\n", el, guess, arr[guess]);
for (i = guess; i < *arr_len - 1; i++) {
arr[i] = arr[i+1];
}
* arr_len = * arr_len - 1;
}
int twiceMedian(int c, int*m) {
if (c % 2 == 1) {
return 2 * m[ (c-1) /2 ];
} else {
return m [ c / 2] + m [ c / 2 - 1 ];
}
}
void print_arr(int arr_len, int * arr) {
int i;
printf("Array dump [%2d]: ", arr_len);
for (i = 0 ; i < arr_len; i++) {
printf("[%2d] %2d ", i, arr[i]);
}
printf("\n");
}
int test() {
int test_arr[] = { 0, 55, 82, 168, 180 };
int test_arr_len = 5;
print_arr(test_arr_len, test_arr);
addToSortedArray(&test_arr_len, test_arr, 41);
print_arr(test_arr_len, test_arr);
return 0;
print_arr(test_arr_len, test_arr);
removeOnce(&test_arr_len, test_arr, 12);
print_arr(test_arr_len, test_arr);
addToSortedArray(&test_arr_len, test_arr, 15);
print_arr(test_arr_len, test_arr);
addToSortedArray(&test_arr_len, test_arr, 22);
print_arr(test_arr_len, test_arr);
addToSortedArray(&test_arr_len, test_arr, 0);
print_arr(test_arr_len, test_arr);
removeOnce(&test_arr_len, test_arr, 0);
print_arr(test_arr_len, test_arr);
removeOnce(&test_arr_len, test_arr, 22);
print_arr(test_arr_len, test_arr);
removeOnce(&test_arr_len, test_arr, 10);
print_arr(test_arr_len, test_arr);
removeOnce(&test_arr_len, test_arr, 20);
print_arr(test_arr_len, test_arr);
removeOnce(&test_arr_len, test_arr, 8);
print_arr(test_arr_len, test_arr);
removeOnce(&test_arr_len, test_arr, 2);
print_arr(test_arr_len, test_arr);
return 0 ;
}
int tangXongCount(int measurement_count, int* measurement, int d) {
int * lookback;
int lookback_len;
int ret;
int i, j;
ret = 0;
lookback_len = 0;
lookback = (int*)(malloc(d * sizeof(int)));
for (i = 0 ; i < d; i++) {
addToSortedArray(&lookback_len, lookback, measurement[i]);
}
for (i = d; i < measurement_count; i++) {
if (measurement[i] >= twiceMedian(d, lookback)) {
ret ++;
}
removeOnce(&lookback_len, lookback, measurement[i - d]);
addToSortedArray(&lookback_len, lookback, measurement[i]);
}
return ret;
}
int main(int argc, char *argv[])
{
FILE *fptr = NULL;
int measurement_count;
int d;
int* measurement;
int i;
int result;
if (argc <= 1) {
printf("Usage: %s INPUT.TXT\n", argv[0]);
printf("INPUT is the input sequence\n");
exit(EXIT_FAILURE);
}
fptr = fopen(argv[1], "r");
fscanf(fptr, "%d", &measurement_count);
fscanf(fptr, "%d", &d);
measurement = (int*) malloc(measurement_count * sizeof(int));
for (i = 0; i < measurement_count; i++) {
fscanf(fptr, "%d", measurement + i);
}
result = tangXongCount(measurement_count, measurement, d);
printf("%d\n", result);
fclose(fptr);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment