diff options
| author | Paulo Custodio <pauloscustodio@gmail.com> | 2021-01-28 00:40:53 +0000 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-01-28 00:40:53 +0000 |
| commit | 31e71edbc488c401e26fd11d802f3145f6eee8fa (patch) | |
| tree | 8a7ed84804d12606f4e08790e4a657018c552ba1 /challenge-097 | |
| parent | dbd5acc0043f19ac068a9c9a7737ed7a2a1a9cba (diff) | |
| parent | 978ad5065e463bf52cd11ea13c1a2c1519a2c07b (diff) | |
| download | perlweeklychallenge-club-31e71edbc488c401e26fd11d802f3145f6eee8fa.tar.gz perlweeklychallenge-club-31e71edbc488c401e26fd11d802f3145f6eee8fa.tar.bz2 perlweeklychallenge-club-31e71edbc488c401e26fd11d802f3145f6eee8fa.zip | |
Merge branch 'master' into 003
Diffstat (limited to 'challenge-097')
32 files changed, 916 insertions, 42 deletions
diff --git a/challenge-097/abigail/README.md b/challenge-097/abigail/README.md index 9e5afd71ff..3427067f32 100644 --- a/challenge-097/abigail/README.md +++ b/challenge-097/abigail/README.md @@ -1,84 +1,98 @@ # Solution by Abigail -## [Reverse Words](https://perlweeklychallenge.org/blog/perl-weekly-challenge-096/#TASK1) +## [Ceasar Cipher](https://perlweeklychallenge.org/blog/perl-weekly-challenge-097/#TASK1) -You are given a string `$S`. +You are given string `$S` containing alphabets `A..Z` only and a number `$N`. -Write a script to reverse the order of words in the given string. -The string may contain leading/trailing spaces. The string may have -more than one space between words in the string. Print the result -without leading/trailing spaces and there should be only one space -between words. +Write a script to encrypt the given string `$S` using Caesar Cipher with +left shift of size `$N`. -### Examples -~~~~ -Input: $S = "The Weekly Challenge" -Output: "Challenge Weekly The" - -Input: $S = " Perl and Raku are part of the same family " -Output: "family same the of part are Raku and Perl" +### Example ~~~~ +Input: $S = "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG", $N = 3 +Output: "QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD" -### Notes +Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ +Cipher: XYZABCDEFGHIJKLMNOPQRSTUVW -The challenge isn't quite clear on whether we should output a number -(the minimal number of operations required), or the actual operations. -The examples show both -- but separated by a blank line. Previous -challenges typically use a blank line to separate the required output -from the explaination on why that it is the correct answer. +Plaintext: THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG +Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD +~~~~ -We're opting to only print the number of operations, not the actual -operations. +### Note +We will be reading the plain text from STDIN, and use an option (-s) +to indicate the left shift. ### Solutions * [AWK](awk/ch-1.awk) -* [Bash](sh/ch-1.sh) -* [C](c/ch-1.c) +* [Bash](bash/ch-1.sh) * [Lua](lua/ch-1.lua) +* [C](c/ch-1.c) * [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 96: Reverse Words](https://wp.me/pcxd30-mj) -## [Edit Distance](https://perlweeklychallenge.org/blog/perl-weekly-challenge-096/#TASK2) +## [Binary Substrings](https://perlweeklychallenge.org/blog/perl-weekly-challenge-097/#TASK2) -You are given two strings `$S1` and `$S2`. +You are given a binary string `$B` and an integer `$S`. -Write a script to find out the minimum operations required to convert -`$S1` into `$S2`. The operations can be insert, remove or replace a -character. Please check out [Wikipedia -page](https://en.wikipedia.org/wiki/Edit_distance) for more information. +Write a script to split the binary string `$B` of size `$S` and then +find the minimum number of flips required to make it all the same. -### Example +### Examples +#### Example 1 ~~~~ -Input: $S1 = "kitten"; $S2 = "sitting" -Output: 3 +Input: $B = "101100101" $S = 3 +Output: 1 -Operation 1: replace 'k' with 's' -Operation 2: replace 'e' with 'i' -Operation 3: insert 'g' at the end +Binary Substrings: + "101": 0 flip + "100": 1 flip to make it "101" + "101": 0 flip ~~~~ +#### Example 2 ~~~~ -Input: $S1 = "sunday"; $S2 = "monday" +Input $B = "10110111", $S = 4 Output: 2 -Operation 1: replace 's' with 'm' -Operation 2: replace 'u' with 'o' +Binary Substrings: + "1011": 0 flip + "0111": 2 flips to make it "1011" ~~~~ +### Notes +We will be reading the strings from STDIN. The number of sections +will be passed in as an option: -s SECTIONS. + +To calculate the mininim number of flips required, note that we +can calculate the number of flips for each position independently; +that is, flipping a bit at position $i doesn't influence how the +number of flips required for position $j, if $i != $j. + +For each position $i, we either need to flip all the 0s to 1s, +or all the 1s to 0s. To minimize the number of flips, we count +the number of 0s in each position, and compare that with the +number of 1s in that position. Then we take the minimum of 0s +and 1s, and sum this for all positions. + +There is no need to split the input string into chunks, +we can leave it as is. The $i-th character of the $j-th section +is as position $j * $s_len + $i, where $s_len is the length +of a section. + ### Solutions * [AWK](awk/ch-2.awk) +* [Bash](bash/ch-2.sh) * [C](c/ch-2.c) * [Lua](lua/ch-2.lua) -* [Node.js](node/ch-2.js) +* [Node](node/ch-2.js) * [Perl](perl/ch-2.pl) * [Python](python/ch-2.py) * [Ruby](ruby/ch-2.rb) ### Blog -[Perl Weekly Challenge 96: Edit Distance](https://wp.me/pcxd30-n7) diff --git a/challenge-097/abigail/awk/ch-1.awk b/challenge-097/abigail/awk/ch-1.awk new file mode 100644 index 0000000000..a33507ee33 --- /dev/null +++ b/challenge-097/abigail/awk/ch-1.awk @@ -0,0 +1,53 @@ +#!/usr/bin/awk + +# +# See ../README.md +# + +# +# Run as: awk -f ch-1.awk -s SHIFT < input-file +# + +BEGIN { + NR_OF_LETTERS = 26 + ORD_A = 65 + + # + # Create a letter to number mapping + # + for (i = ORD_A; i < ORD_A + NR_OF_LETTERS; i ++) { + t = sprintf ("%c", i) + ord [t] = i + } + + # + # Parse command line + # + for (i = 1; i < ARGC; i ++) { + if (ARGV [i] == "-s") { + shift = ARGV [i + 1] + } + } + ARGC = 0 +} + +{ + split($0, letters, "") + out = "" + # + # Iterate over the individual letters, shifting capital letters + # + for (i = 1; i <= length (letters); i ++) { + char = letters [i] + if (ord [char]) { + n = ord [char] - shift + if (n < ORD_A) { + n = n + NR_OF_LETTERS + } + char = sprintf ("%c", n) + } + out = out char + } + print out +} + diff --git a/challenge-097/abigail/awk/ch-2.awk b/challenge-097/abigail/awk/ch-2.awk new file mode 100644 index 0000000000..892ca2bdc7 --- /dev/null +++ b/challenge-097/abigail/awk/ch-2.awk @@ -0,0 +1,46 @@ +#!/usr/bin/awk + +# +# See ../README.md +# + +# +# Run as: awk -f ch-2.awk -s SECTIONS < input-file +# + +BEGIN { + # + # Parse command line + # + for (i = 1; i < ARGC; i ++) { + if (ARGV [i] == "-s") { + sections = ARGV [i + 1] + } + } + ARGC = 0 +} + +{ + # + # Split the string into individual letters, use + # indexing to get the ith letter of the jth section + # + sum = 0 + s_len = length ($0) / sections # Length of a section + for (i = 0; i < s_len; i ++) { + zeros = 0; # Count the zeros on position i + for (j = 0; j < sections; j ++) { + indx = j * s_len + i + 1 # Can't use 'index' as a variable + if (substr ($0, indx, 1) == "0") { + zeros ++ + } + } + ones = sections - zeros + # + # Sum the minimum of the 0's and 1's + # + sum += zeros < ones ? zeros : ones + } + print sum +} + diff --git a/challenge-097/abigail/bash/ch-1.sh b/challenge-097/abigail/bash/ch-1.sh new file mode 100644 index 0000000000..8e275a6519 --- /dev/null +++ b/challenge-097/abigail/bash/ch-1.sh @@ -0,0 +1,34 @@ +#!/bin/sh + +# +# See ../README.md +# + +# +# Run as: bash ch-1.sh -s SHIFT < input-file +# + +# +# Disable pathname expansion +# +set -f + +# +# Read the option +# +while getopts "s:" name +do if [ "$name" = "s" ] + then shift=$OPTARG + fi +done + + +# +# Iterate over the input, shifting each line as many times as needed +# +while read line +do for ((i = 0; i < $shift; i ++)) + do line=`echo $line | tr A-Z ZA-Y` + done + echo $line +done diff --git a/challenge-097/abigail/bash/ch-2.sh b/challenge-097/abigail/bash/ch-2.sh new file mode 100644 index 0000000000..ad82b5ecab --- /dev/null +++ b/challenge-097/abigail/bash/ch-2.sh @@ -0,0 +1,45 @@ +#!/bin/sh + +# +# See ../README.md +# + +# +# Run as: bash ch-2.sh -s SECTIONS < input-file +# + +# +# Disable pathname expansion +# +set -f + +# +# Read the option +# +while getopts "s:" name +do if [ "$name" = "s" ] + then sections=$OPTARG + fi +done + + +# +# Iterate over the input. For each position, count the number of 0s, +# and calculate the number of 1s. Sum the minimum of those numbers. +# +while read line +do s_len=$((${#line} / $sections)) + sum=0 + for ((i = 0; i < s_len; i ++)) + do zeros=0 + for ((j = 0; j < sections; j ++)) + do index=$(($j * $s_len + $i)) + if [ "${line:$index:1}" == "0" ] + then zeros=$(($zeros + 1)) + fi + done + ones=$(($sections - $zeros)) + sum=$(($sum + ($zeros < $ones ? $zeros : $ones) )) + done + echo $sum +done diff --git a/challenge-097/abigail/c/ch-1.c b/challenge-097/abigail/c/ch-1.c new file mode 100644 index 0000000000..8219361e36 --- /dev/null +++ b/challenge-097/abigail/c/ch-1.c @@ -0,0 +1,50 @@ +# include <stdlib.h> +# include <stdio.h> +# include <string.h> +# include <unistd.h> +# include <ctype.h> + +/* + * See ../README.md + */ + +/* + * Run as: cc -o ch-1.o ch-1.c; ./ch-1.o -s SHIFT < input-file + */ + +int main (int argc, char ** argv) { + char * line = NULL; + size_t len = 0; + size_t strlen; + int ch; + int shift = -1; + int NR_OF_LETTERS = 26; + + while ((ch = getopt (argc, argv, "s:")) != -1) { + switch (ch) { + case 's': + shift = atoi (optarg) % NR_OF_LETTERS; + break; + } + } + if (shift < 0) { + fprintf (stderr, "Requires an -s parameter\n"); + exit (1); + } + + while ((strlen = getline (&line, &len, stdin)) != -1) { + char * line_ptr = line; + while (* line_ptr) { + if (isupper (* line_ptr)) { + * line_ptr -= shift; + if (* line_ptr < 'A') { + * line_ptr += NR_OF_LETTERS; + } + } + line_ptr ++; + } + printf ("%s", line); + } + free (line); + return (0); +} diff --git a/challenge-097/abigail/c/ch-2.c b/challenge-097/abigail/c/ch-2.c new file mode 100644 index 0000000000..47a0a65a61 --- /dev/null +++ b/challenge-097/abigail/c/ch-2.c @@ -0,0 +1,53 @@ +# include <stdlib.h> +# include <stdio.h> +# include <string.h> +# include <unistd.h> +# include <ctype.h> + +/* + * See ../README.md + */ + +/* + * Run as: cc -o ch-2.o ch-2.c; ./ch-2.o -s SECTIONS < input-file + */ + +int main (int argc, char ** argv) { + char * line = NULL; + size_t len = 0; + size_t strlen; + int ch; + int sections = -1; + + while ((ch = getopt (argc, argv, "s:")) != -1) { + switch (ch) { + case 's': + sections = atoi (optarg); + break; + } + } + if (sections < 0) { + fprintf (stderr, "Requires an -s SECTIONS parameter\n"); + exit (1); + } + + while ((strlen = getline (&line, &len, stdin)) != -1) { + strlen --; /* We don't care about the newline */ + int s_len = strlen / sections; /* Section length */ + int sum = 0; + for (int i = 0; i < s_len; i ++) { + int zeros = 0; + for (int j = 0; j < sections; j ++) { + int index = j * s_len + i; + if (line [index] == '0') { + zeros ++; + } + } + int ones = sections - zeros; + sum += zeros < ones ? zeros : ones; + } + printf ("%d\n", sum); + } + free (line); + return (0); +} diff --git a/challenge-097/abigail/lua/ch-1.lua b/challenge-097/abigail/lua/ch-1.lua new file mode 100644 index 0000000000..d674cdf7c2 --- /dev/null +++ b/challenge-097/abigail/lua/ch-1.lua @@ -0,0 +1,47 @@ +#!/opt/local/bin/lua + +-- +-- See ../README.md +-- + +-- +-- Run as: lua ch-1.lua -s SHIFT < input-file +-- + +local shift = -1 +local NR_OF_LETTERS = 26 +local ORD_A = string . byte ("A") + +-- +-- Parse option, and exit if incorrect +-- +if #arg == 2 and arg [1] == "-s" +then shift = arg [2] % NR_OF_LETTERS +end + +if shift < 0 +then io . stderr : write ("Requires a '-s SHIFT' option\n") + os . exit (1) +end + + +-- +-- Shift a capital letter 'shift' places to the left, +-- rotating if shifted before 'A' +-- +function do_shift (char, shift) + local n = string . byte (char) - shift + if n < ORD_A + then n = n + NR_OF_LETTERS + end + return string . char (n) +end + +-- +-- Shift capital letters +-- +for line in io . lines () do + io . write (string . gsub (line, "[A-Z]", function (ch) + return do_shift (ch, shift) + end), "\n") +end diff --git a/challenge-097/abigail/lua/ch-2.lua b/challenge-097/abigail/lua/ch-2.lua new file mode 100644 index 0000000000..0136c0c1e5 --- /dev/null +++ b/challenge-097/abigail/lua/ch-2.lua @@ -0,0 +1,49 @@ +#!/opt/local/bin/lua + +-- +-- See ../README.md +-- + +-- +-- Run as: lua ch-2.lua -s SECTIONS < input-file +-- + +-- +-- Parse option, and exit if incorrect +-- + +local sections = -1 +if #arg == 2 and arg [1] == "-s" +then sections = arg [2] + 0 +end + +if sections < 0 +then io . stderr : write ("Requires a '-s SECTIONS' option\n") + os . exit (1) +end + + +-- +-- Iterate over the input, line by line. +-- For each line, count the number of 0's on each position of the sections +-- Calculate the number of 1's. Add the minimum of the two to a running sum. +-- +for line in io . lines () do + local s_len = #line / sections + local sum = 0 + for i = 0, s_len - 1 do + local zeros = 0 + for j = 0, sections - 1 do + index = j * s_len + i + 1 + if string . sub (line, index, index) == "0" + then zeros = zeros + 1 + end + end + local ones = sections - zeros + if zeros < ones + then sum = sum + zeros + else sum = sum + ones + end + end + io . write (sum, "\n") +end diff --git a/challenge-097/abigail/node/ch-1.js b/challenge-097/abigail/node/ch-1.js new file mode 100644 index 0000000000..0cba6f1a23 --- /dev/null +++ b/challenge-097/abigail/node/ch-1.js @@ -0,0 +1,50 @@ +#!/usr/local/bin/node + +// +// See ../README.md +// + +// +// Run as: node ch-1.js -s TIMES < input-file +// + +const NR_OF_LETTERS = 26 + +// +// Parse input +// +const argv = require ('yargs') +. option ('s', { + type: 'number', + }) +. demandOption ('s') +. argv; + +const shift = argv . s + +// +// Shift capital letters, by a given amount. +// +function shift_char (char, shift) { + if (char . match (/[A-Z]/)) { + let n = char . charCodeAt (0) - (shift % NR_OF_LETTERS) + if (n < 65) { + n = n + NR_OF_LETTERS + } + return String . fromCharCode (n) + } + else { + return char + } +} + + +// +// Iterate over the input, and shift characters +// +require ('readline') +. createInterface ({input: process . stdin}) +. on ('line', _ => console . log (_ . split ("") + . map (_ => shift_char (_, shift)) + . join (""))) +; diff --git a/challenge-097/abigail/node/ch-2.js b/challenge-097/abigail/node/ch-2.js new file mode 100644 index 0000000000..c28c3fb2b8 --- /dev/null +++ b/challenge-097/abigail/node/ch-2.js @@ -0,0 +1,59 @@ +#!/usr/local/bin/node + +// +// See ../README.md +// + +// +// Run as: node ch-2.js -s SECTIONS < input-file +// + +const NR_OF_LETTERS = 26 + +// +// Parse input +// +const argv = require ('yargs') +. option ('s', { + type: 'number', + }) +. demandOption ('s') +. argv; + +const sections = argv . s + +// +// Iterate over the input +// +require ('readline') +. createInterface ({input: process . stdin}) +. on ('line', _ => { + let sum = 0 + let s_len = _ . length / sections // Length of a segment + // + // Iterate over the positions + // + for (let i = 0; i < s_len; i ++) { + // + // Count the number of zeros in a specific position + // + let zeros = 0 + for (let j = 0; j < sections; j ++) { + let index = j * s_len + i; + if (_ . substring (index, index + 1) == "0") { + zeros ++ + } + } + // + // Calculate the ones + // + let ones = sections - zeros + + // + // Add the minimum of the zeros and ones + // + sum += zeros < ones ? zeros : ones + } + console . log (sum) +}) +; diff --git a/challenge-097/abigail/perl/ch-1.pl b/challenge-097/abigail/perl/ch-1.pl new file mode 100644 index 0000000000..7558150f4d --- /dev/null +++ b/challenge-097/abigail/perl/ch-1.pl @@ -0,0 +1,32 @@ +#!/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 -s SHIFT < input-file +# + +use Getopt::Long; + +GetOptions 's=i' => \my $shift; + +die "-s option required" unless defined $shift; + +$shift %= 26; + +while (<>) { + chomp; + s/([A-Z])/my $ch = ord ($1) - $shift; $ch += 26 if $ch < 65; chr $ch/eg; + say; +} diff --git a/challenge-097/abigail/perl/ch-2.pl b/challenge-097/abigail/perl/ch-2.pl new file mode 100644 index 0000000000..179745252b --- /dev/null +++ b/challenge-097/abigail/perl/ch-2.pl @@ -0,0 +1,58 @@ +#!/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 -s SECTIONS < input-file +# + +use Getopt::Long; +use List::Util qw [min]; + +GetOptions 's=i' => \my $sections; + +die "-s option required" unless defined $sections && $sections > 0; + +# +# There is no need to split the input string into chunks, +# we can leave it as is. The $i-th character of the $j-th section +# is as position $j * $s_len + $i, where $s_len is the length +# of a section. +# +# To calculate the minimum number of flips, for each position $i, we +# calculate the number of 0s there are on the $i-th positions of +# each section. Given the number of 0s, we can calculate the number +# of 1s. The minimum number of flips required to get all the bits +# on position equal is the minimum of the number of 0s and the number +# of 1s. +# +# So, to calculate the minimum number of flips, for each postion, +# we sum the minimum of the number of 0s and the number of 1s. +# + +while (<>) { + chomp; + my $s_len = length () / $sections; + my $sum = 0; + for my $i (0 .. $s_len - 1) { + my $zeros = 0; + for my $j (0 .. $sections - 1) { + my $index = $j * $s_len + $i; + $zeros ++ if substr ($_, $index, 1) eq "0"; + } + my $ones = $sections - $zeros; + $sum += min ($zeros, $ones); + } + say $sum; +} diff --git a/challenge-097/abigail/python/ch-1.py b/challenge-097/abigail/python/ch-1.py new file mode 100644 index 0000000000..d5a42bbcf2 --- /dev/null +++ b/challenge-097/abigail/python/ch-1.py @@ -0,0 +1,46 @@ +#!/opt/local/bin/python + +# +# See ../READ.md +# + +# +# Run as python ch-1.py -s SHIFT < input-file +# + +import fileinput +import sys +import getopt + +NR_OF_LETTERS = 26 +ORD_A = ord ("A") + +# +# Parse and validate options +# +shift = -1 +opts, args = getopt . getopt (sys . argv [1:], 's:') +for opt, val in opts: + if opt == "-s": + shift = int (val) % NR_OF_LETTERS + +sys . argv [1:] = [] + +if shift < 0: + sys . stderr . write ("Argument -s SHIFT is required\n") + sys . exit (1) + +# +# Iterate over the input. Shift capital letters +# +for line in fileinput . input (): + out = "" + for i in range (len (line)): + if "A" <= line [i] <= "Z": + n = ord (line [i]) - shift + if n < ORD_A: + n = n + NR_OF_LETTERS + out += chr (n) + else: + out += line [i] + sys . stdout . write (out) diff --git a/challenge-097/abigail/python/ch-2.py b/challenge-097/abigail/python/ch-2.py new file mode 100644 index 0000000000..828c6fcf12 --- /dev/null +++ b/challenge-097/abigail/python/ch-2.py @@ -0,0 +1,45 @@ +#!/opt/local/bin/python + +# +# See ../READ.md +# + +# +# Run as python ch-2.py -s SECTIONS < input-file +# + +import fileinput +import sys +import getopt + +# +# Parse and validate options +# +shift = -1 +opts, args = getopt . getopt (sys . argv [1:], 's:') +for opt, val in opts: + if opt == "-s": + sections = int (val) + +sys . argv [1:] = [] + +if sections < 0: + sys . stderr . write ("Argument -s SECTIONS is required\n") + sys . exit (1) + +# +# Iterate over the input. For each position, count the number of 0s, +# and calculate the number of 1s. Sum the minimum of those numbers. +# +for line in fileinput . input (): + s_len = len (line) / sections + sum = 0 + for i in range (s_len): + zeros = 0 + for j in range (sections): + index = j * s_len + i + if line [index : index + 1] == "0": + zeros += 1 + ones = sections - zeros + sum += min (zeros, ones) + print (sum) diff --git a/challenge-097/abigail/ruby/ch-1.rb b/challenge-097/abigail/ruby/ch-1.rb new file mode 100644 index 0000000000..1225bd290c --- /dev/null +++ b/challenge-097/abigail/ruby/ch-1.rb @@ -0,0 +1,46 @@ +#!/usr/bin/ruby + +# +# See ../README.md +# + +# +# Run as: ruby ch-1.rb -s SHIFT < input-file +# + +require 'optparse' + +NR_OF_LETTERS = 26 + + +# +# Parse and validate options +# |
