Merge pull request #4165 from Abigail/abigail/week-114

Abigail/week 114

22 files changed, 2562 insertions, 44 deletions

diff --git a/challenge-114/abigail/README.md b/challenge-114/abigail/README.md
index a026cb8bf7..7548aee37d 100644
--- a/challenge-114/abigail/README.md
+++ b/challenge-114/abigail/README.md
@@ -1,76 +1,58 @@
 # Solutions by Abigail
-## [Represent Integer](https://perlweeklychallenge.org/blog/perl-weekly-challenge-113/#TASK1)
+## [Next Palindrome Number](https://perlweeklychallenge.org/blog/perl-weekly-challenge-114/#TASK1)
 
-> You are given a positive integer `$N` and a digit `$D`.
+> You are given a positive integer `$N`.
 >
-> Write a script to check if `$N` can be represented as a sum
-> of positive integers having `$D` at least once. If check passes
-> print `1` otherwise `0`.
+> Write a script to find out the next Palindrome Number higher than
+> the given integer `$N`.
 
 ### Example
 ~~~~
-Input: $N = 25, $D = 7
-Output: 0 as there are 2 numbers between 1 and 25 having the digit 7
-        i.e. 7 and 17. If we add up both we don't get 25.
+Input: $N = 1234
+Output: 1331
 
-Input: $N = 24, $D = 7
-Output: 1
+Input: $N = 999
+Output: 1001
 ~~~~
 
 ### Solutions
 * [AWK](awk/ch-1.awk)
 * [Bash](bash/ch-1.sh)
 * [C](c/ch-1.c)
-* [Lua](lua/ch-1.lua)
-* [Node.js](node/ch-1.js)
 * [Perl](perl/ch-1.pl)
-* [Python](python/ch-1.py)
-* [Ruby](ruby/ch-1.rb)
 
 ### Blog
-[Perl Weekly Challenge 113: Represent
-Integer](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-113-1.html)
+[Next Palindrome Number](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-114-1.html)
 
-## [Recreate Binary Tree](https://perlweeklychallenge.org/blog/perl-weekly-challenge-113/#TASK2)
+## [Higher Integer Set Bits](https://perlweeklychallenge.org/blog/perl-weekly-challenge-114/#TASK2)
 
-> You are given a Binary Tree.
+> You are given a positive integer `$N`.
 > 
-> Write a script to replace each node of the tree with the sum of
-> all the remaining nodes
+> Write a script to find the next higher integer having the same number of
+> `1` bits in binary representation as `$N`.
 
-### Example
-#### Input
+### Examples
 ~~~~
-        1
-       / \
-      2   3
-     /   / \
-    4   5   6
-     \
-      7
+Input: $N = 3
+Output: 5
 ~~~~
-#### Output
+
+Binary representation of `$N` is `011`. There are two `1` bits. So the next
+higher integer is `5` having the same the number of `1` bits i.e. `101`.
+
 ~~~~
-        27
-       /  \
-      26  25
-     /   /  \
-    24  23  22
-     \
-     21
+Input: $N = 12
+Output: 17
 ~~~~
 
+Binary representation of `$N` is `1100`. There are two `1` bits. So the next
+higher integer is `17` having the same number of `1` bits i.e. `10001`.
 
 ### Solutions
-* [AWK](awk/ch-2.awk)
+* [GNU AWK](awk/ch-2.gawk)
 * [Bash](bash/ch-2.sh)
 * [C](c/ch-2.c)
-* [Lua](lua/ch-2.lua)
-* [Node.js](node/ch-2.js)
 * [Perl](perl/ch-2.pl)
-* [Python](python/ch-2.py)
-* [Ruby](ruby/ch-2.rb)
 
 ### Blog
-[Perl Weekly Challenge 113: Recreate Binary
-Tree](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-113-2.html)
+[Higher Integet Set Bits](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-114-2.html)
diff --git a/challenge-114/abigail/awk/ch-1.awk b/challenge-114/abigail/awk/ch-1.awk
new file mode 100644
index 0000000000..3d1822ea29
--- /dev/null
+++ b/challenge-114/abigail/awk/ch-1.awk
@@ -0,0 +1,44 @@
+#!/usr/bin/awk
+
+#
+# See ../README.md
+#
+
+#
+# Run as: awk -f ch-1.awk < input-file
+#
+
+function reverse (word, out, i) {
+    for (i = length (word); i > 0; i --) {
+        out = out substr (word, i, 1)
+    }
+    return out
+}
+
+
+
+/^9+$/ {
+    print $1 + 2
+    next
+}
+
+length ($1) == 1 {
+    print $1 + 1
+    next
+}
+
+{
+    part1 = substr ($1, 1,  int (length ($1) / 2))
+    part2 = substr ($1, 1 + int (length ($1) / 2),  length ($1) % 2)
+    part3 = substr ($1, 1 + int (length ($1) / 2) + length ($1) % 2)
+
+    if (reverse(part1) <= part3) {
+        part1 = (part1 part2) + 1
+        if (length (part2)) {
+            part2 = substr (part1,    length (part1),  1)
+            part1 = substr (part1, 1, length (part1) - 1)
+        }
+    }
+
+    print part1 part2 reverse(part1)
+}
diff --git a/challenge-114/abigail/awk/ch-2.gawk b/challenge-114/abigail/awk/ch-2.gawk
new file mode 100644
index 0000000000..49c2ef960f
--- /dev/null
+++ b/challenge-114/abigail/awk/ch-2.gawk
@@ -0,0 +1,47 @@
+#!/usr/bin/awk
+
+#
+# See ../README.md
+#
+
+#
+# Run as: gawk -f ch-2.gawk < input-file
+#
+
+#
+# Take a number, and return a binary representation
+#
+function d2b (d, b) {
+    b = ""
+    while (d > 0) {
+        b = d % 2 b
+        d = int (d / 2)
+    }
+    return (b)
+}
+
+#
+# Take a binary representation of a number, return that number.
+#
+function b2d (b, d, i) {
+    d = 0
+    i = 0
+    while (length (b) > 0) {
+        if (substr (b, length (b), 1) == "1") {
+            d += 2 ^ i
+        }
+        i ++
+        b = substr (b, 1, length (b) - 1)
+    }
+    return (d)
+}
+
+
+{
+    #
+    # Take a number, turn it into a binary representation (d2b), prepend a 0.
+    # Replace the last 01 with 10, and swap trailing sequence of 1s and 0s.
+    # Turn this back into a decimal representation, and print it.
+    #
+    print (b2d(gensub (/^(.*)01(1*)(0*)$/, "\\110\\3\\2", 1, 0 d2b($1))))
+}
diff --git a/challenge-114/abigail/bash/ch-1.sh b/challenge-114/abigail/bash/ch-1.sh
new file mode 100644
index 0000000000..6ea7f4ff78
--- /dev/null
+++ b/challenge-114/abigail/bash/ch-1.sh
@@ -0,0 +1,62 @@
+#!/bin/sh
+
+#
+# See ../README.md
+#
+
+#
+# Run as: bash ch-1.sh < input-file
+#
+
+set -f
+
+#
+# Reverse a given string. Put the result into a global variable reverse.
+#
+function rev() {
+    local in=$1
+    reverse=""
+    for ((i = 0; i < ${#in}; i ++)) 
+    do  reverse=${in:$i:1}$reverse
+    done
+}
+
+while read number
+do    if   [[ $number =~ ^9+$ ]]
+      then echo $((number + 2))
+           continue
+      fi
+
+      if   ((${#number} == 1))
+      then echo $((number + 1))
+           continue
+      fi
+
+      #
+      # Split input in parts. Length of part1 and part3 are equal.
+      # part2 is the middle character if the input number has odd
+      # length, and empty otherwise.
+      #
+      part1=${number:0:$((${#number} / 2))}
+      part2=""
+      if   ((${#number} % 2))
+      then part2=${number:$((${#number} / 2)):1}
+      fi
+      part3=${number:$(((${#number} + 1) / 2))}
+      rev $part1
+      if   ((${reverse} > ${part3}))
+      then echo $part1$part2$reverse
+           continue
+      fi
+
+      #
+      # Add one of "$part1$part2", and reverse it.
+      #
+      inc=$(($part1$part2 + 1))
+      rev $inc
+
+      #
+      # Print result
+      #
+      echo $inc${reverse:$((${#number} % 2))}
+done
diff --git a/challenge-114/abigail/bash/ch-2.sh b/challenge-114/abigail/bash/ch-2.sh
new file mode 100644
index 0000000000..69980bd2b3
--- /dev/null
+++ b/challenge-114/abigail/bash/ch-2.sh
@@ -0,0 +1,39 @@
+#!/bin/sh
+
+#
+# See ../README.md
+#
+
+#
+# Run as: bash ch-2.sh < input-file
+#
+
+function d2b () {
+    local d=$1
+    b=""
+    while ((d > 0))
+    do b=$((d % 2))$b
+       ((d /= 2))
+    done
+}
+
+function b2d () {
+    local b=$1
+    local p=1
+    d=""
+    while ((${#b} > 0))
+    do  if   [[ ${b:$((${#b} - 1))} == "1" ]]
+        then ((d += p))
+        fi
+        ((p *= 2))
+        b=${b:0:$((${#b} - 1))}
+    done
+}
+
+
+while read number
+do    d2b $number
+      [[ 0$b =~ ^(.*)(01)(1*)(0*)$ ]]
+      b2d ${BASH_REMATCH[1]}10${BASH_REMATCH[4]}${BASH_REMATCH[3]}
+      echo $d
+done
diff --git a/challenge-114/abigail/blog.txt b/challenge-114/abigail/blog.txt
new file mode 100644
index 0000000000..087a442f76
--- /dev/null
+++ b/challenge-114/abigail/blog.txt
@@ -0,0 +1 @@
+https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-114-1.html
diff --git a/challenge-114/abigail/blog1.txt b/challenge-114/abigail/blog1.txt
new file mode 100644
index 0000000000..aee5ae3122
--- /dev/null
+++ b/challenge-114/abigail/blog1.txt
@@ -0,0 +1 @@
+https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-114-2.html
diff --git a/challenge-114/abigail/c/ch-1.c b/challenge-114/abigail/c/ch-1.c
new file mode 100644
index 0000000000..798f875954
--- /dev/null
+++ b/challenge-114/abigail/c/ch-1.c
@@ -0,0 +1,97 @@
+# include <stdlib.h>
+# include <stdio.h>
+# include <string.h>
+# include <stdbool.h>
+
+/*
+ * See ../README.md
+ */
+
+/*
+ * Run as: cc -o ch-1.o ch-1.c; ./ch-1.o < input-file
+ */
+
+int main (void) {
+    char *  line    = NULL;
+    size_t  len     = 0;
+    size_t  str_len;
+
+    while ((str_len = getline (&line, &len, stdin)) != -1) {
+        char * line_ptr = line;
+        str_len --;   /* Don't care about newline. */
+        /*
+         * Do we have just 9s?
+         */
+        bool all_nines = true;
+        for (size_t i = 0; i < str_len; i ++) {
+            if (line [i] != '9') {
+                all_nines = false;
+                break;
+            }
+        }
+        if (all_nines) {
+            printf ("1");
+            for (size_t i = 0; i < str_len - 1; i ++) {
+                printf ("0");
+            }
+            printf ("1\n");
+            continue;
+        }
+
+        /*
+         * Single character?
+         */
+        if (str_len == 1) {
+            line [0] ++;
+            printf ("%s", line);
+            continue;
+        }
+
+        size_t mid = str_len / 2;
+
+        /*
+         * Is the first part reversed greater than the last part?
+         */
+        bool is_greater = false;
+        ssize_t i;
+        size_t j;
+        for (i = mid - 1, j = mid + (str_len & 1); i >= 0; i --, j ++) {
+            if (line [i] > line [j]) {
+                is_greater = true;
+                break;
+            }
+            if (line [i] < line [j]) {
+                break;
+            }
+        }
+        /*
+         * If not greater, we need to add one of the first part (including
+         * the middle part). We do this by starting from the middle, turning
+         * 9s into 0s, and adding 1 to something not a 9. In the latter
+         * case, we terminate the loop.
+         */
+        if (!is_greater) {
+            for (i = mid - 1 + (str_len & 1); i >= 0; i --) {
+                if (line [i] == '9') {
+                    line [i] = '0';
+                }
+                else {
+                    line [i] ++;
+                    break;
+                }
+            }
+        }
+
+        /*
+         * Now, copy the first half to the second; reversed
+         */
+        for (i = mid - 1, j = mid + (str_len & 1); i >= 0; i --, j ++) {
+            line [j] = line [i];
+        }
+
+        printf ("%s", line);
+    }
+    free (line);
+
+    return (0);
+}
diff --git a/challenge-114/abigail/c/ch-2.c b/challenge-114/abigail/c/ch-2.c
new file mode 100644
index 0000000000..265f0ed0a4
--- /dev/null
+++ b/challenge-114/abigail/c/ch-2.c
@@ -0,0 +1,69 @@
+# include <stdlib.h>
+# include <stdio.h>
+# include <string.h>
+# include <limits.h>
+
+/*
+ * See ../README.md
+ */
+
+/*
+ * Run as: cc -o ch-2.o ch-2.c; ./ch-2.o < input-file
+ */
+
+int main (void) {
+    unsigned long long d;
+    while (scanf ("%llu", &d) == 1) {
+        char b [LONG_BIT + 1];
+        /*
+         * Transfer the decimal number into a binary representation,
+         * LSB first.
+         */
+        for (size_t i = 0; i < LONG_BIT; i ++) {
+            b [i] = (d & 1);
+            d = d >> 1;
+        }
+        /*
+         * End with a 0
+         */
+        b [LONG_BIT] = 0;
+
+        /*
+         * Count the number of 0s at the beginning, followed by a count of
+         * the number of 1s. 
+         */
+        size_t count_0 = 0;
+        size_t count_1 = 1;
+        while (!b [count_0]) {
+            count_0 ++;
+        }
+        while (b [count_0 + count_1]) {
+            count_1 ++;
+        }
+        /*
+         * Now, b [count_0 + count_1 - 1] == 1 and
+         *      b [count_0 + count_1]     == 0.
+         * Swap those two, and place the 1s and 0s
+         */
+        b [count_0 + count_1]     = 1;
+        b [count_0 + count_1 - 1] = 0;
+        count_1 --;
+        for (size_t i = 0; i < count_1; i ++) {
+            b [i] = 1;
+        }
+        for (size_t i = count_1; i < count_1 + count_0; i ++) {
+            b [i] = 0;
+        }
+
+        /*
+         * Turn binary expansion back to decimal
+         */
+        d = 0;
+        unsigned long long p2 = 1;
+        for (size_t i = 0; i < LONG_BIT; i ++) {
+            d  += p2 * b [i];
+            p2 *= 2;
+        }
+        printf ("%llu\n", d);
+    }
+}
diff --git a/challenge-114/abigail/perl/ch-1.pl b/challenge-114/abigail/perl/ch-1.pl
new file mode 100644
index 0000000000..510376da90
--- /dev/null
+++ b/challenge-114/abigail/perl/ch-1.pl
@@ -0,0 +1,50 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# See ../README.md
+#
+
+#
+# Run as: perl ch-1.pl < input-file
+#
+
+#
+# See https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-114-1.html
+# for a description of the algorithm.
+#
+
+while (<>) {
+    chomp;
+    if (/^9+$/) {
+        say $_ + 2;
+        next;
+    }
+
+    if (length ($_) == 1) {
+        say $_ + 1;
+        next;
+    }
+
+    #
+    # Split the number into parts 2 equal parts, with a middle part
+    # of at most one digit.
+    #
+    my $part1 = substr $_, 0, int length ($_) / 2;
+    my $part2 = substr $_,    int length ($_) / 2,  length ($_) % 2;
+    my $part3 = substr $_,    int length ($_) / 2 + length ($_) % 2;
+
+    if (reverse ($part1) <= $part3) {
+        $part1 = "$part1$part2" + 1;
+        $part2 = chop $part1 if length $part2;
+    }
+    say $part1, $part2, scalar reverse ($part1);
+}
diff --git a/challenge-114/abigail/perl/ch-2.pl b/challenge-114/abigail/perl/ch-2.pl
new file mode 100644
index 0000000000..61e2ddf1ea
--- /dev/null
+++ b/challenge-114/abigail/perl/ch-2.pl
@@ -0,0 +1,27 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# See ../README.md
+#
+
+#
+# Run as: perl ch-2.pl < input-file
+#
+
+#
+# For a description of the algorithm, see
+# https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-114-2.html
+#
+
+say oct sprintf ("0b0%b" => $_) =~ s {01(1*)(0*)$} {10$2$1}r while <>;
+
+__END__
diff --git a/challenge-114/abigail/t/ctest.ini b/challenge-114/abigail/t/ctest.ini
new file mode 100644
index 0000000000..cfcb77b668
--- /dev/null
+++ b/challenge-114/abigail/t/ctest.ini
@@ -0,0 +1,11 @@
+# 

+# Configuration file for running tests, using ctest.

+# See https://github.com/Abigail/Misc/blob/master/ctest

+# 

+

+[names]

+1-1 = Given examples

+1-2 = More tests

+1-3 = Single digits

+2-1 = Given examples

+2-2 = First 1024 positive integers

diff --git a/challenge-114/abigail/t/input-1-1 b/challenge-114/abigail/t/input-1-1
new file mode 100644
index 0000000000..9d315f546d
--- /dev/null
+++ b/challenge-114/abigail/t/input-1-1
@@ -0,0 +1,2 @@
+1234
+999
diff --git a/challenge-114/abigail/t/input-1-2 b/challenge-114/abigail/t/input-1-2
new file mode 100644
index 0000000000..250da2dbce
--- /dev/null
+++ b/challenge-114/abigail/t/input-1-2
@@ -0,0 +1,6 @@
+12345678
+87654321
+1234567
+7654321
+2222222
+222222
diff --git a/challenge-114/abigail/t/input-1-3 b/challenge-114/abigail/t/input-1-3
new file mode 100644
index 0000000000..8b1acc12b6
--- /dev/null
+++ b/challenge-114/abigail/t/input-1-3
@@ -0,0 +1,10 @@
+0
+1
+2
+3
+4
+5
+6
+7
+8
+9
diff --git a/challenge-114/abigail/t/input-2-1 b/challenge-114/abigail/t/input-2-1
new file mode 100644
index 0000000000..fd5972620b
--- /dev/null
+++ b/challenge-114/abigail/t/input-2-1
@@ -0,0 +1,2 @@
+3
+12
diff --git a/challenge-114/abigail/t/input-2-2 b/challenge-114/abigail/t/input-2-2
new file mode 100644
index 0000000000..b732f2cff3
--- /dev/null
+++ b/challenge-114/abigail/t/input-2-2
@@ -0,0 +1,1024 @@
+1
+2
+3
+4
+5
+6
+7
+8
+9
+10
+11
+12
+13
+14
+15
+16
+17
+18
+19
+20
+21
+22
+23
+24
+25
+26
+27
+28
+29
+30
+31
+32
+33
+34
+35
+36
+37
+38
+39
+40
+41
+42
+43
+44
+45
+46
+47
+48
+49
+50
+51
+52
+53
+54
+55
+56
+57
+58
+59
+60
+61
+62
+63
+64
+65
+66
+67
+68
+69
+70
+71
+72
+73
+74
+75
+76
+77
+78
+79
+80
+81
+82
+83
+84
+85
+86
+87
+88
+89
+90
+91
+92
+93
+94
+95
+96
+97
+98
+99
+100
+101
+102
+103
+104
+105
+106
+107
+108
+109
+110
+111
+112
+113
+114
+115
+116
+117
+118
+119
+120
+121
+122
+123
+124
+125
+126
+127
+128
+129
+130
+131
+132
+133
+134
+135
+136
+137
+138
+139
+140
+141
+142
+143
+144
+145
+146
+147
+148
+149
+150
+151
+152
+153
+154
+155
+156
+157
+158
+159
+160
+161
+162
+163
+164
+165
+166
+167
+168
+169
+170
+171
+172
+173
+174
+175
+176
+177
+178
+179
+180
+181
+182
+183
+184
+185
+186
+187
+188
+189
+190
+191
+192
+193
+194
+195
+196
+197
+198
+199
+200
+201
+202
+203
+204
+205
+206
+207
+208
+209
+210
+211
+212
+213
+214
+215
+216
+217
+218
+219
+220
+221
+222
+223
+224
+225
+226
+227
+228
+229
+230
+231
+232
+233
+234
+235
+236
+237
+238
+239
+240
+241
+242
+243
+244
+245
+246
+247
+248
+249
+250
+251
+252
+253
+254
+255
+256
+257
+258
+259
+260
+261
+262
+263
+264
+265
+266
+267
+268
+269
+270
+271
+272
+273
+274
+275
+276
+277
+278
+279
+280
+281
+282
+283
+284
+285
+286
+287
+288
+289
+290
+291
+292
+293
+294
+295
+296
+297
+298
+299
+300
+301
+302
+303
+304
+305
+306
+307
+308
+309
+310
+311
+312
+313
+314
+315
+316
+317
+318
+319
+320
+321
+322
+323
+324
+325
+326
+327
+328
+329
+330
+331
+332
+333
+334
+335
+336
+337
+338
+339
+340
+341
+342
+343
+344
+345
+346
+347
+348
+349
+350
+351
+352
+353
+354
+355
+356
+357
+358
+359
+360
+361
+362
+363
+364
+365
+366
+367
+368
+369
+370
+371
+372
+373
+374
+375
+376
+377
+378
+379
+380
+381
+382
+383
+384
+385
+386
+387
+388
+389
+390
+391
+392
+393
+394
+395
+396
+397
+398
+399
+400
+401
+402
+403
+404
+405
+406
+407
+408
+409
+410
+411
+412
+413
+414
+415
+416
+417
+418
+419
+420
+421
+422
+423
+424
+425
+426
+427
+428
+429
+430
+431
+432
+433
+434
+435
+436
+437
+438
+439
+440
+441
+442
+443
+444
+445
+446
+447
+448
+449
+450
+451
+452
+453
+454
+455
+456
+457
+458
+459
+460
+461
+462
+463
+464
+465
+466
+467
+468
+469
+470
+471
+472
+473
+474
+475
+476
+477
+478
+479
+480
+481
+482
+483
+484
+485
+486
+487
+488
+489
+490
+491
+492
+493
+494
+495
+496
+497
+498
+499
+500
+501
+502
+503
+504
+505
+506
+507
+508
+509
+510
+511
+512
+513
+514
+515
+516
+517
+518
+519
+520
+521
+522
+523
+524
+525
+526
+527
+528
+529
+530
+531
+532
+533
+534
+535
+536
+537
+538
+539
+540
+541
+542
+543
+544
+545
+546
+547
+548
+549
+550
+551
+552
+553
+554
+555
+556
+557
+558
+559
+560
+561
+562
+563
+564
+565
+566
+567
+568
+569
+570
+571
+572
+573
+574
+575
+576
+577
+578
+579
+580
+581
+582
+583
+584
+585
+586
+587
+588
+589
+590
+591
+592
+593