From 2f5a634972c673db4d80141ce72c09b713b7200f Mon Sep 17 00:00:00 2001 From: David Ferrone Date: Mon, 23 Sep 2024 11:56:29 -0400 Subject: Week 288 --- challenge-288/zapwai/c/ch-1.c | 55 ++++++ challenge-288/zapwai/c/ch-2.c | 208 ++++++++++++++++++++++ challenge-288/zapwai/c/vec.h | 294 ++++++++++++++++++++++++++++++++ challenge-288/zapwai/javascript/ch-1.js | 33 ++++ challenge-288/zapwai/perl/ch-1.pl | 34 ++++ challenge-288/zapwai/perl/ch-2.pl | 99 +++++++++++ challenge-288/zapwai/python/ch-1.py | 29 ++++ challenge-288/zapwai/python/ch-2.py | 83 +++++++++ challenge-288/zapwai/r/ch-1.r | 42 +++++ challenge-288/zapwai/rust/ch-1.rs | 44 +++++ challenge-288/zapwai/rust/ch-2.rs | 165 ++++++++++++++++++ 11 files changed, 1086 insertions(+) create mode 100644 challenge-288/zapwai/c/ch-1.c create mode 100644 challenge-288/zapwai/c/ch-2.c create mode 100644 challenge-288/zapwai/c/vec.h create mode 100644 challenge-288/zapwai/javascript/ch-1.js create mode 100644 challenge-288/zapwai/perl/ch-1.pl create mode 100644 challenge-288/zapwai/perl/ch-2.pl create mode 100644 challenge-288/zapwai/python/ch-1.py create mode 100644 challenge-288/zapwai/python/ch-2.py create mode 100644 challenge-288/zapwai/r/ch-1.r create mode 100644 challenge-288/zapwai/rust/ch-1.rs create mode 100644 challenge-288/zapwai/rust/ch-2.rs diff --git a/challenge-288/zapwai/c/ch-1.c b/challenge-288/zapwai/c/ch-1.c new file mode 100644 index 0000000000..56c14c3c41 --- /dev/null +++ b/challenge-288/zapwai/c/ch-1.c @@ -0,0 +1,55 @@ +#include +#include +#include +#include + +/* consumes s */ +void strrev(char* s) { + int length = strlen(s); + for (int i = 0; i < length / 2; i++) { + char tmp = s[i]; + s[i] = s[length - i - 1]; + s[length - i - 1] = tmp; + } +} + +bool is_pal(char* s) { + char r[50]; + strcpy(r, s); + strrev(r); + return 0 == strcmp(s,r) ? true : false; +} + +void proc(char* s) { + printf("Input: %s\n", s); + int n = atoi(s); + int found = 0; + int step = 1; + while (found == 0) { + int m = n - step; + char ms[50]; + sprintf(ms, "%d", m); + if (is_pal(ms)) { + found = 1; + n = m; + } else { + m = n + step; + sprintf(ms, "%d", m); + if (is_pal(ms)) { + found = 1; + n = m; + } + } + step++; + } + printf("Output: %d\n", n); +} + +int main() { + char* s = "123"; + proc(s); + s = "2"; + proc(s); + s = "1400"; + proc(s); +} diff --git a/challenge-288/zapwai/c/ch-2.c b/challenge-288/zapwai/c/ch-2.c new file mode 100644 index 0000000000..7843ebffb4 --- /dev/null +++ b/challenge-288/zapwai/c/ch-2.c @@ -0,0 +1,208 @@ +#include +#include +#include +#include "vec.h" + +#define ENTRYLEN 6 /* dd-dd\0 */ +#define BLOCKLEN 60001 +/* These constants work for matrix up to size 99^2 */ +/* "dd-dd " x 10,000 entries*/ + +struct hash { + char key[BLOCKLEN][ENTRYLEN]; + int val[BLOCKLEN]; + int size; +}; + +bool contains(struct hash h, char *entry) { + for (int i = 0; i < h.size; i++) + if (0 == strcmp(h.key[i], entry)) + return true; + return false; +} + +bool intersection(char *a, char *b) { + char *A = malloc(BLOCKLEN); + strcpy(A, a); + char *B = malloc(BLOCKLEN); + char *entry1; + char *saveptr1, *saveptr2; + entry1 = strtok_r(A, " ", &saveptr1); + while (entry1 != NULL) { + strcpy(B, b); + char *entry2; + entry2 = strtok_r(B, " ", &saveptr2); + while (entry2 != NULL) { + if (0 == strcmp(entry1, entry2)) { + free(A); free(B); + return true; + } + entry2 = strtok_r(NULL, " ", &saveptr2); + } + entry1 = strtok_r(NULL, " ", &saveptr1); + } + free(A); free(B); + return false; +} + +void merge(vec *c) { + for (int i1 = 0; i1 < c->size - 1; i1++) { + for (int i2 = i1 + 1; i2 < c->size; i2++) { + if (intersection(c->datas[i1], c->datas[i2])) { + struct hash h = { .size = 0 }; + char *C1 = malloc(BLOCKLEN); + strcpy(C1, c->datas[i1]); + char *entry1; + entry1 = strtok(C1, " "); + while (entry1 != NULL) { + if (!contains(h, entry1)) { + strcpy(h.key[h.size], entry1); + h.val[h.size++] = 1; + } + entry1 = strtok(NULL, " "); + } + char *C2 = malloc(BLOCKLEN); + strcpy(C2, c->datas[i2]); + char *entry2; + entry2 = strtok(C2, " "); + while (entry2 != NULL) { + if (!contains(h, entry2)) { + strcpy(h.key[h.size], entry2); + h.val[h.size++] = 1; + } + entry2 = strtok(NULL, " "); + } + free(C1); + free(C2); + strcpy(c->datas[i1], ""); + char *sr = malloc(BLOCKLEN); + strcpy(sr, ""); + for (int i = 0; i < h.size; i++) { + char *sq = malloc(ENTRYLEN); + sprintf(sq, "%s ", h.key[i]); + strcat(sr, sq); + free(sq); + } + strcpy(c->datas[i2], sr); + free(sr); + } + } + } +} + +void contigu(int m, int n, char matrix[m][n], char *entry, vec *c) { + vec *blocks = new_vec('s'); + push(blocks, entry); + for (int i = 0; i < blocks->size; i++) { + char *block = malloc(ENTRYLEN); + strcpy(block, blocks->datas[i]); + char *tok; + tok = strtok(block, "-"); + int y = atoi(tok); + tok = strtok(NULL, "-"); + int x = atoi(tok); + free(block); + if (x + 1 < n) { + if (matrix[y][x] == matrix[y][x+1]) { + char *ms = malloc(ENTRYLEN); + sprintf(ms, "%d-%d", y, x+1); + push(blocks, ms); + free(ms); + } + } + if (y + 1 < m) { + if (matrix[y][x] == matrix[y+1][x]) { + char *ms = malloc(ENTRYLEN); + sprintf(ms, "%d-%d", y+1, x); + push(blocks, ms); + free(ms); + } + } + + } + char *sr = malloc(BLOCKLEN); + strcpy(sr, ""); + for (int i = 0; i < blocks->size; i++) { + char *sq = malloc(ENTRYLEN); + sprintf(sq, "%s ", blocks->datas[i]); + strcat(sr, sq); + free(sq); + } + push(c, sr); + free(sr); + destroy_vec(blocks); +} + +void proc(int m, int n, char matrix[m][n]) { + printf( "Input: matrix = \n"); + for (int i = 0; i < m; i++) { + printf("\t"); + for (int j = 0; j < n; j++) + printf("%c", matrix[i][j]); + printf("\n"); + } + printf("\n"); + vec *contig = new_vec('s'); + contigu(m, n, matrix, "0-0", contig); + for (int i = 0; i < m; i++) { + for (int j = 0; j < n; j++) { + bool got_flag = false; + char *entry = malloc(ENTRYLEN); + sprintf(entry, "%d-%d", i, j); + for (int k = 0; k < contig->size; k++){ + char *b = malloc(BLOCKLEN); + strcpy(b, contig->datas[k]); + char s[BLOCKLEN][ENTRYLEN] = {}; + int slen = 0; + char *p = strtok(b, " "); + while(p != NULL) { + strcpy(s[slen++], p); + p = strtok(NULL, " "); + } + for (int i = 0; i < slen; i++) + if (0 == strcmp(s[i], entry)) + got_flag = true; + } + if (!got_flag) + contigu(m, n, matrix, entry, contig); + free(entry); + } + } + merge(contig); + int cnt = 0; + for (int i = 0; i < contig->size; i++) { + char *c = contig->datas[i]; + if (0 != strcmp("", c)) + printf("%s\n", c); + int len = 0; + for (int j = 0; j < strlen(c); j++) + if (c[j] == '-') + len++; + if (cnt < len) + cnt = len; + } + printf( "\nOutput: %d\n\n", cnt); + destroy_vec(contig); +} + +int main() { + char matrix[4][5] = {{'x', 'x', 'x', 'x', 'o'}, + {'x', 'o', 'o', 'o', 'o'}, + {'x', 'o', 'o', 'o', 'o'}, + {'x', 'x', 'x', 'o', 'o'}, + }; + proc(4, 5, matrix); + char matrix2[4][5] = {{'x', 'x', 'x', 'x', 'x'}, + {'x', 'o', 'o', 'o', 'o'}, + {'x', 'x', 'x', 'x', 'o'}, + {'x', 'o', 'o', 'o', 'o'}, + }; + proc(4, 5, matrix2); + char matrix3[4][5] = {{'x', 'x', 'x', 'o', 'o'}, + {'o', 'o', 'o', 'x', 'x'}, + {'o', 'x', 'x', 'o', 'o'}, + {'o', 'o', 'o', 'x', 'x'}, + }; + proc(4,5,matrix3); +} + diff --git a/challenge-288/zapwai/c/vec.h b/challenge-288/zapwai/c/vec.h new file mode 100644 index 0000000000..8a73798e45 --- /dev/null +++ b/challenge-288/zapwai/c/vec.h @@ -0,0 +1,294 @@ +#ifndef VEC_H +#define VEC_H +#include +#include +#define VECMAXSTRLEN 50 +#define VECCAP 10 +typedef struct vector { + size_t cap; /* actual size allocated (reduces calls to realloc)*/ + size_t size; /* size of data */ + int* data; /* integer data */ + char* datac; /* char data */ + char** datas; /* string data */ + char type; /* i, c, or s */ +} vec; + +vec* new_vec(char t) { + struct vector* v = malloc(sizeof(vec)); + if ( t != 'c' && t != 'i' && t != 's') { + exit(1); + } + v->type = t; + v->size = 0; + v->cap = VECCAP; + v->data = malloc(v->cap * sizeof(int)); + v->datac = malloc(v->cap * sizeof(char)); + v->datas = malloc(v->cap * sizeof(char*)); + for (int i = 0; i < v->cap; i++) + v->datas[i] = malloc(VECMAXSTRLEN); + return v; +} + +void destroy_vec(struct vector* v) { + free (v->data); /* good habit */ + free (v->datac); + int number_of_strings = (v->type == 's') ? v->cap : VECCAP; + for (int i = 0; i < number_of_strings; i++) + free(v->datas[i]); + free (v->datas); + free(v); +} + +/* If a vector needs more memory, add VECCAP (e.g. 10) slots */ +void stretch_vec(struct vector* v) { + if (v->size == v->cap) { + v->cap += VECCAP; + switch(v->type) { + case 'i': + v->data = realloc(v->data, sizeof(int) * v->cap); + break; + case 'c': + v->datac = realloc(v->datac, sizeof(char) * v->cap); + break; + case 's': + v->datas = realloc(v->datas, sizeof(char*) * v->cap); + for (int i = v->size; i < v->cap; i++) + v->datas[i] = malloc(VECMAXSTRLEN); + break; + } + } +} + +void push(struct vector* v, void* value) { + v->size++; + stretch_vec(v); + switch(v->type) { + case 'i': + v->data[v->size - 1] = *(int *) value; + break; + case 'c': + v->datac[v->size - 1] = *(char *) value; + break; + case 's': + strcpy(v->datas[v->size - 1], (char *) value); + break; + } +} + + +void unshift(struct vector* v, void* value) { + v->size++; + stretch_vec(v); + switch(v->type) { + case 'i': + for (int i = v->size - 1; i > 0; i--) + v->data[i] = v->data[i - 1]; + v->data[0] = * (int*) value; + break; + case 'c': + for (int i = v->size - 1; i > 0; i--) + v->datac[i] = v->datac[i - 1]; + v->datac[0] = * (char*) value; + break; + case 's': + for (int i = v->size - 1; i > 0; i--) + strcpy(v->datas[i], v->datas[i - 1]); + strcpy(v->datas[0], (char*) value); + break; + } +} + +void* shift(struct vector* v) { + void *x = NULL; + if (v->size == 0) return NULL; + v->size--; + switch(v->type) { + case 'i': + x = malloc(sizeof(int)); + if (x == NULL) return NULL; + *(int*)x = v->data[0]; + for (int i = 0; i < v->size; i++) + v->data[i] = v->data[i + 1]; + v->data[v->size] = 0; + break; + case 'c': + x = malloc(sizeof(char)); + if (x == NULL) return NULL; + *(char *)x = v->datac[0]; + for (int i = 0; i < v->size; i++) + v->datac[i] = v->datac[i + 1]; + v->datac[v->size] = '\0'; + break; + case 's': + x = malloc(VECMAXSTRLEN); + if (x == NULL) return NULL; + strcpy(x, v->datas[0]); + for (int i = 0; i < v->size; i++) + strcpy(v->datas[i], v->datas[i + 1]); + strcpy(v->datas[v->size], ""); + break; + } + return x; +} + +void* pop(struct vector* v) { + void *x = NULL; + if (v->size == 0) return NULL; + v->size--; + switch(v->type) { + case 'i': + x = malloc(sizeof(int)); + *(int*)x = v->data[v->size]; + v->data[v->size] = 0; + break; + case 'c': + x = malloc(sizeof(char)); + *(char*)x = v->datac[v->size]; + v->datac[v->size] = '\0'; + break; + case 's': + x = malloc(VECMAXSTRLEN); + strcpy(x, v->datas[v->size]); + strcpy(v->datas[v->size], " "); + break; + } + return x; +} + +void push_list(struct vector* v, void* list, int listlen) { + for (int i = 0; i < listlen; i++) + switch(v->type) { + case 'i': + push(v, &((int*)list)[i]); + break; + case 'c': + push(v, &((char*)list)[i]); + break; + case 's': + push(v, ((char**)list)[i]); + break; + } +} + +void sort(struct vector* v) { + int cnt; + do { + cnt = 0; + for (int i = 0; i < v->size - 1; i++) { + switch(v->type) { + case 'i': + if (v->data[i] > v->data[i + 1]) { + cnt++; + int tmp = v->data[i]; + v->data[i] = v->data[i+1]; + v->data[i+1] = tmp; + } + break; + case 'c': + if (v->datac[i] > v->datac[i + 1]) { + cnt++; + char tmp = v->datac[i]; + v->datac[i] = v->datac[i+1]; + v->datac[i+1] = tmp; + } + break; + case 's': + if (strcmp(v->datas[i], v->datas[i + 1]) > 0) { + cnt++; + char* tmp = v->datas[i]; + v->datas[i] = v->datas[i+1]; + v->datas[i+1] = tmp; + } + break; + } + } + } while(cnt > 0); +} + +void reverse(struct vector* v) { + if (v->size == 1) return; + int k = v->size / 2; + for (int i = 0; i < k; i++) { + int idx = (v->size % 2 == 0) ? k+i : k+1+i; + int idy = k - i - 1; + switch(v->type) { + case 'i': + { + int x = v->data[idy]; + v->data[idy] = v->data[idx]; + v->data[idx] = x; + } + break; + case 'c': + { + char x = v->datac[k-1-i]; + v->datac[idy] = v->datac[idx]; + v->datac[idx] = x; + } + break; + case 's': + { + char* x = v->datas[k-1-i]; + v->datas[idy] = v->datas[idx]; + v->datas[idx] = x; + } + break; + } + } +} + +void display(struct vector* v) { + printf("["); + if (v->size > 0){ + switch(v->type) { + case 'i': + for (int i = 0; i < v->size - 1; i++) printf("%d, ", v->data[i]); + printf("%d", v->data[v->size-1]); + break; + case 'c': + for (int i = 0; i < v->size - 1; i++) printf("%c, ", v->datac[i]); + printf("%c", v->datac[v->size-1]); + break; + case 's': + for (int i = 0; i < v->size - 1; i++) printf("%s, ", v->datas[i]); + printf("%s", v->datas[v->size-1]); + break; + } + } + printf("]"); +} + +void* get(struct vector* v, int k) { + void* x = NULL; + switch(v->type) { + case 'i': + x = malloc(sizeof(int)); + *(int*) x = v->data[k]; + break; + case 'c': + x = malloc(sizeof(char)); + *(char*) x = v->datac[k]; + break; + case 's': + x = malloc(VECMAXSTRLEN); + strcpy(x, v->datas[k]); + break; + } + return x; +} + +void set(struct vector* v, int k, void* value) { + switch(v->type) { + case 'i': + v->data[k] = *(int*) value; + break; + case 'c': + v->datac[k] = *(char*) value; + break; + case 's': + strcpy(v->datas[k], (char*) value); + break; + } + +} +#endif diff --git a/challenge-288/zapwai/javascript/ch-1.js b/challenge-288/zapwai/javascript/ch-1.js new file mode 100644 index 0000000000..8ce2f49c9a --- /dev/null +++ b/challenge-288/zapwai/javascript/ch-1.js @@ -0,0 +1,33 @@ +let s = "123"; +proc(s); +s = "2"; +proc(s); +s = "1400"; +proc(s); + +function is_pal(s) { + let r = s.split("").reduce((acc, char) => char + acc, ""); + return (s == r); +} + +function proc(s) { + console.log( "Input:", s); + let n = parseInt(s, 10); + let found = false; + let step = 1; + while (!found) { + let m = n - step; + if (is_pal(m.toString())) { + found = true; + n = m; + } else { + m = n + step; + if (is_pal(m.toString())) { + found = true; + n = m; + } + } + step++; + } + console.log( "Output:", n); +} diff --git a/challenge-288/zapwai/perl/ch-1.pl b/challenge-288/zapwai/perl/ch-1.pl new file mode 100644 index 0000000000..015aad9180 --- /dev/null +++ b/challenge-288/zapwai/perl/ch-1.pl @@ -0,0 +1,34 @@ +use v5.38; +my $s = "123"; +proc($s); +$s = "2"; +proc($s); +$s = "1400"; +proc($s); + +sub is_pal($s) { + my $r = reverse $s; + return ($s eq $r); +} + +sub proc($s) { + say "Input: $s"; + my $n = $s; + my $found = 0; + my $step = 1; + while ($found == 0) { + my $m = $n - $step; + if (is_pal($m)) { + $found = 1; + $n = $m; + } else { + $m = $n + $step; + if (is_pal($m)) { + $found = 1; + $n = $m; + } + } + $step++; + } + say "Output: $n"; +} diff --git a/challenge-288/zapwai/perl/ch-2.pl b/challenge-288/zapwai/perl/ch-2.pl new file mode 100644 index 0000000000..ee3879ef7c --- /dev/null +++ b/challenge-288/zapwai/perl/ch-2.pl @@ -0,0 +1,99 @@ +use v5.38; +my $matrix = [['x', 'x', 'x', 'x', 'o'], + ['x', 'o', 'o', 'o', 'o'], + ['x', 'o', 'o', 'o', 'o'], + ['x', 'x', 'x', 'o', 'o'], + ]; +proc($matrix); +$matrix = [['x', 'x', 'x', 'x', 'x'], + ['x', 'o', 'o', 'o', 'o'], + ['x', 'x', 'x', 'x', 'o'], + ['x', 'o', 'o', 'o', 'o'], + ]; +proc($matrix); +$matrix = [['x', 'x', 'x', 'o', 'o'], + ['o', 'o', 'o', 'x', 'x'], + ['o', 'x', 'x', 'o', 'o'], + ['o', 'o', 'o', 'x', 'x'], + ]; +proc($matrix); + +# Return true if these strings share an item +sub intersection($a, $b) { + for my $entry1 (split " ", $a) { + for my $entry2 (split " ", $b) { + if ($entry1 eq $entry2) { + return 1; + } + } + } + return 0; +} + +# Final processing step, any intersecting blocks are merged into one block. +sub merge($c) { + for my $i1 (0 .. $#{$c} - 1) { + for my $i2 ($i1 + 1 .. $#{$c}) { + if (intersection($$c[$i1], $$c[$i2])) { + my %h; + $h{$_} = 1 for (split " ", $$c[$i1]); + $h{$_} = 1 for (split " ", $$c[$i2]); + $$c[$i1] = ""; + $$c[$i2] = join(" ", sort keys %h); + } + } + } +} + +# From top left to bottom right, beginning at given entry +# pushes a block to the main contiguous array, @contig +sub contig($matrix, $m, $n, $entry, $c) { + my @blocks = ($entry); + for my $block (@blocks) { + my ($y, $x) = split "-", $block; + if ($x + 1 <= $n) { + if ($$matrix[$y][$x] eq $$matrix[$y][$x+1]) { + push @blocks, "$y-".($x+1); + } + } + if ($y + 1 <= $m) { + if ($$matrix[$y][$x] eq $$matrix[$y+1][$x]) { + push @blocks, ($y+1)."-$x"; + } + } + } + push @$c, join(" ", @blocks); +} + +# e.g. @blocks = ("0-0 0-1 0-2" "1-1 1-2 1-3") +# For each cell in a block, check right/down, then add to the current block +sub proc($matrix) { + say "Input: \$matrix = "; + say "\t@{$_}" for (@$matrix); + my $m = -1 + @$matrix; + my $n = -1 + @{$$matrix[0]}; + my @contig; + contig($matrix, $m, $n, "0-0", \@contig); + for my $i (0 .. $m) { + for my $j (0 .. $n) { + my $got_flag = 0; + my $entry = "$i-$j"; + for my $b (@contig) { + $got_flag = 1 if (grep /$entry/, split(" ", $b)); + } + contig($matrix, $m, $n, $entry, \@contig) unless ($got_flag); + } + } + merge(\@contig); + say ""; + my $cnt = 0; + for my $c (@contig) { + if ($c) { + say $c; + my $len = scalar split " ", $c; + $cnt = $len if ($cnt < $len); + } + } + say "\nOutput: $cnt\n"; +} + diff --git a/challenge-288/zapwai/python/ch-1.py b/challenge-288/zapwai/python/ch-1.py new file mode 100644 index 0000000000..48ebd7985c --- /dev/null +++ b/challenge-288/zapwai/python/ch-1.py @@ -0,0 +1,29 @@ +def is_pal(s) : + r = str(s)[::-1] + return (str(s) == r) + +def proc(s) : + print("Input:", s) + n = int(s) + found = False + step = 1 + while not found : + m = n - step + if is_pal(m) : + found = True + n = m + else : + m = n + step + if is_pal(m) : + found = True + n = m + step += 1 + print("Output:", n) + +s = "123" +proc(s) +s = "2" +proc(s) +s = "1400" +proc(s) + diff --git a/challenge-288/zapwai/python/ch-2.py b/challenge-288/zapwai/python/ch-2.py new file mode 100644 index 0000000000..d1976af50a --- /dev/null +++ b/challenge-288/zapwai/python/ch-2.py @@ -0,0 +1,83 @@ +import re + +def intersection(a, b): + for entry1 in a.split(" "): + for entry2 in b.split(" "): + if entry1 == entry2: + return True + return False + +def merge(c): + for i1 in range(len(c) - 1): + for i2 in range(i1 + 1, len(c)): + if intersection(c[i1], c[i2]): + h = {} + for i in c[i1].split(" "): + h[i] = 1 + for i in c[i2].split(" "): + h[i] = 1 + c[i1] = "" + c[i2] = " ".join(h.keys()) + +def contigu(matrix, m, n, entry, c): + blocks = [entry] + for block in blocks: + (a, b) = block.split("-") + y = int(a) + x = int(b) + if x + 1 <= n: + if matrix[y][x] == matrix[y][x+1]: + blocks.append(str(y)+"-"+str(x+1)) + if y + 1 <= m: + if matrix[y][x] == matrix[y+1][x]: + blocks.append(str(y+1)+"-"+str(x)) + c.append(" ".join(blocks)) + +def proc(matrix): + print("Input: matrix =") + for i in matrix: + print(i) + print() + m = -1 + len(matrix) + n = -1 + len(matrix[0]) + contig = [] + contigu(matrix, m, n, "0-0", contig) + for i in range(m+1): + for j in range(n+1): + got_flag = False + entry = str(i)+"-"+str(j) + for b in contig: + if entry in b.split(" "): + got_flag = True + break + if not got_flag: + contigu(matrix, m, n, entry, contig) + merge(contig) + cnt = 0 + for c in contig: + if c: + print(c) + leng = len(c.split(" ")) + if cnt < leng: + cnt = leng + print("\nOutput:", cnt, "\n") + +matrix = [['x', 'x', 'x', 'x', 'o'], + ['x', 'o', 'o', 'o', 'o'], + ['x', 'o', 'o', 'o', 'o'], + ['x', 'x', 'x', 'o', 'o'], + ] +proc(matrix) +matrix = [['x', 'x', 'x', 'x', 'x'], + ['x', 'o', 'o', 'o', 'o'], + ['x', 'x', 'x', 'x', 'o'], + ['x', 'o', 'o', 'o', 'o'], + ] +proc(matrix) +matrix = [['x', 'x', 'x', 'o', 'o'], + ['o', 'o', 'o', 'x', 'x'], + ['o', 'x', 'x', 'o', 'o'], + ['o', 'o', 'o', 'x', 'x'], + ] +proc(matrix) + diff --git a/challenge-288/zapwai/r/ch-1.r b/challenge-288/zapwai/r/ch-1.r new file mode 100644 index 0000000000..d3a8e17752 --- /dev/null +++ b/challenge-288/zapwai/r/ch-1.r @@ -0,0 +1,42 @@ +reverse <- function(s) { + r <- strsplit(s, "")[[1]] + q <- "" + for (i in 1:nchar(s)) { + q <- paste(q, r[nchar(s) - i + 1], sep = "") + } + return(q) +} + +is_pal <-function(s) { + r <- reverse(s) + return (s == r) +} + +proc <-function(s) { + cat( "Input:", s, "\n") + n <- as.numeric(s) + found <- 0 + step <- 1 + while (found == 0) { + m <- n - step + if (is_pal(toString(m))) { + found <- 1 + n <- m + } else { + m <- n + step + if (is_pal(toString(m))) { + found <- 1 + n <- m + } + } + step <- step + 1 + } + cat( "Output:", n, "\n") +} + +s <- "123" +proc(s) +s <- "2" +proc(s) +s <- "1400" +proc(s) diff --git a/challenge-288/zapwai/rust/ch-1.rs b/challenge-288/zapwai/rust/ch-1.rs new file mode 100644 index 0000000000..5fbc141c6a --- /dev/null +++ b/challenge-288/zapwai/rust/ch-1.rs @@ -0,0 +1,44 @@ +fn main() { + let s1 = "123"; + proc(s1); + let s2 = "2"; + proc(s2); + let s3 = "1400"; + proc(s3); +} + +fn reverse(s : String) -> String { + let r : Vec = s.chars().collect(); + let mut ans = String::new(); + for i in 0 .. r.len() { + ans.push_str(&r[r.len() - i - 1].to_string()); + } + return ans; +} + +fn is_pal(s : String) -> bool { + let r = reverse(s.clone()); + return s == r; +} + +fn proc(s : &str) { + println!( "Input: {s}"); + let mut n = s.parse::().unwrap(); + let mut found = false; + let mut step = 1; + while !found { + let mut m = n - step; + if is_pal(m.to_string()) { + found = true; + n = m; + } else { + m = n + step; + if is_pal(m.to_string()) { + found = true; + n = m; + } + } + step += 1; + } + println!( "Output: {n}"); +} diff --git a/challenge-288/zapwai/rust/ch-2.rs b/challenge-288/zapwai/rust/ch-2.rs new file mode 100644 index 0000000000..1fbe1f5f7b --- /dev/null +++ b/challenge-288/zapwai/rust/ch-2.rs @@ -0,0 +1,165 @@ +use std::collections::HashSet; + +struct Hash { + key: HashSet, +} + +impl Hash { + fn new() -> Self { + Hash { + key: HashSet::new(), + } + } + + fn contains(&self, entry: &str) -> bool { + self.key.contains(entry) + } + + fn insert(&mut self, entry: &str) { + self.key.insert(entry.to_string()); + } +} + +fn intersection(a: &str, b: &str) -> bool { + let entries_a: Vec<&str> = a.split_whitespace().collect(); + for entry_a in entries_a { + let entries_b: Vec<&str> = b.split_whitespace().collect(); + for entry_b in entries_b { + if entry_a == entry_b { + return true; + } + } + } + false +} + +fn merge(c: &mut Vec) { + for i1 in 0..c.len() - 1 { + for i2 in i1 + 1..c.len() { + if intersection(&c[i1], &c[i2]) { + let mut h = Hash::new(); + + let entries1: Vec<&str> = c[i1].split_whitespace().collect(); + for entry1 in entries1 { + if !h.contains(entry1) { + h.insert(entry1); + } + } + + let entries2: Vec<&str> = c[i2].split_whitespace().collect(); + for entry2 in entries2 { + if !h.contains(entry2) { + h.insert(entry2); + } + } + + c[i1].clear(); + let merged: String = h.key.iter().map(|s| format!("{} ", s)).collect(); + c[i2] = merged; + } + } + } +} + +fn contigu(m: usize, n: usize, matrix: &[[char; 5]], entry: &str, c: &mut Vec) { + let mut blocks = vec![entry.to_string()]; + + let mut changes = 1; + while changes > 0 { + changes = 0; + for i in 0..blocks.len() { + let block = &blocks[i]; + let mut parts = block.split('-'); + let y: usize = parts.next().unwrap().parse().unwrap(); + let x: usize = parts.next().unwrap().parse().unwrap(); + + if x + 1 < n && matrix[y][x] == matrix[y][x + 1] { + let new_entry: String = format!("{}-{}", y, x + 1); + if !blocks.contains(&new_entry) { + blocks.push(new_entry); + changes += 1; + } + } + + if y + 1 < m && matrix[y][x] == matrix[y + 1][x] { + let new_entry: String = format!("{}-{}", y + 1, x); + if !blocks.contains(&new_entry) { + blocks.push(new_entry); + changes += 1; + } + } + } + } + + let merged: String = blocks.iter().map(|s| format!("{} ", s)).collect(); + c.push(merged); +} + +fn proc(m: usize, n: usize, matrix: &[[char; 5]]) { + println!("Input: matrix ="); + for row in matrix { + println!("\t{}", row.iter().collect::()); + } + + let mut contig = Vec::new(); + contigu(m, n, matrix, "0-0", &mut contig); + + for i in 0..m { + for j in 0..n { + let entry = format!("{}-{}", i, j); + let mut got_flag = false; + + for b in &contig { + let s: Vec<&str> = b.split_whitespace().collect(); + if s.contains(&&entry[..]) { + got_flag = true; + } + } + + if !got_flag { + contigu(m, n, matrix, &entry, &mut contig); + } + } + } + + merge(&mut contig); + + let mut cnt = 0; + for c in &contig { + if !c.is_empty() { + println!("{}", c); + let len = c.matches('-').count(); + if cnt < len { + cnt = len; + } + } + } + + println!("\nOutput: {}\n", cnt); +} + +fn main() { + let matrix1: [[char; 5]; 4] = [ + ['x', 'x', 'x', 'x', 'o'], + ['x', 'o', 'o', 'o', 'o'], + ['x', 'o', 'o', 'o', 'o'], + ['x', 'x', 'x', 'o', 'o'], + ]; + proc(4, 5, &matrix1); + + let matrix2: [[char; 5]; 4] = [ + ['x', 'x', 'x', 'x', 'x'], + ['x', 'o', 'o', 'o', 'o'], + ['x', 'x', 'x', 'x', 'o'], + ['x', 'o', 'o', 'o', 'o'], + ]; + proc(4, 5, &matrix2); + + let matrix3: [[char; 5]; 4] = [ + ['x', 'x', 'x', 'o', 'o'], + ['o', 'o', 'o', 'x', 'x'], + ['o', 'x', 'x', 'o', 'o'], + ['o', 'o', 'o', 'x', 'x'], + ]; + proc(4, 5, &matrix3); +} -- cgit