diff options
61 files changed, 2616 insertions, 1037 deletions
diff --git a/challenge-117/e-choroba/perl5/ch-1.pl b/challenge-117/e-choroba/perl/ch-1.pl index 637e595b08..637e595b08 100755 --- a/challenge-117/e-choroba/perl5/ch-1.pl +++ b/challenge-117/e-choroba/perl/ch-1.pl diff --git a/challenge-117/e-choroba/perl5/ch-2.pl b/challenge-117/e-choroba/perl/ch-2.pl index e44e7f73e9..e44e7f73e9 100755 --- a/challenge-117/e-choroba/perl5/ch-2.pl +++ b/challenge-117/e-choroba/perl/ch-2.pl diff --git a/challenge-117/perlboy1967/perl/ch-1.pl b/challenge-117/perlboy1967/perl/ch-1.pl index 109b8e42e7..a19af8d516 100755 --- a/challenge-117/perlboy1967/perl/ch-1.pl +++ b/challenge-117/perlboy1967/perl/ch-1.pl @@ -25,5 +25,8 @@ sub missingRows { open(my $fh,'<',$f) || die; - return grep /\d/,slide{($a+1..$b-1)if($b-$a>1)}sort{$a<=>$b}map{/^(\d+)/;$_=$1}<$fh>; + return map { @$_ } slide {$b - $a > 1 ? [$a + 1 .. $b - 1] : [] } + sort { $a <=> $b } + map { /^(\d+)/; $_ = $1 } + <$fh>; } diff --git a/challenge-119/abigail/awk/ch-2.awk b/challenge-119/abigail/awk/ch-2.awk index c0f502e082..351c34a6b7 100644 --- a/challenge-119/abigail/awk/ch-2.awk +++ b/challenge-119/abigail/awk/ch-2.awk @@ -9,9 +9,21 @@ # function next_num (prev_num, tail) { + # + # Find the trailing 3s + # match (prev_num, /3*$/) tail = substr (prev_num, RSTART) + + # + # Replace them with 3s + # gsub (/3/, 1, tail) + + # + # Put the tail back in, incrementing the number before it. + # If we matched the full number, add a 1 + # if (RLENGTH == length (prev_num)) { prev_num = 1 tail } @@ -24,11 +36,7 @@ function next_num (prev_num, tail) { # # Replace the trailing 1s with 1212... # - if (match (prev_num, /1+$/)) { - tail = substr (prev_num, RSTART) - gsub (/11/, "12", tail) - prev_num = substr (prev_num, 1, RSTART - 1) tail - } + gsub (/11/, "12", prev_num) return prev_num } diff --git a/challenge-119/abigail/c/ch-2.c b/challenge-119/abigail/c/ch-2.c index 45effb48c5..aa5bd4682a 100644 --- a/challenge-119/abigail/c/ch-2.c +++ b/challenge-119/abigail/c/ch-2.c @@ -35,13 +35,14 @@ int main (void) { * Increment the digit before the trailing 3s */ number [i] ++; + /* - * Replace every second 1 into a 2 of the trailing 1s + * Replace any '11' by '12' */ - for (i = BUF_SIZE - 1; i > 0 && number [i] == '1'; i --); - i += 2; - for (;i < BUF_SIZE; i += 2) { - number [i] = '2'; + for (i = 0; i < BUF_SIZE - 1; i ++) { + if (number [i] == '1' && number [i + 1] == '1') { + number [i + 1] = '2'; + } } } /* diff --git a/challenge-119/abigail/lua/ch-2.lua b/challenge-119/abigail/lua/ch-2.lua new file mode 100644 index 0000000000..e0c940767d --- /dev/null +++ b/challenge-119/abigail/lua/ch-2.lua @@ -0,0 +1,36 @@ +#!/opt/local/bin/lua + +-- +-- See ../README.md +-- + +-- +-- Run as: lua ch-2.lua < input-file +-- + +function next_number (prev_num) + -- + -- Get the trailing 3s (tail), and the number before (num) + -- and anything before it (prefix) + -- + local _, _, prefix, num, tail = + ("0" .. prev_num) : find ("(.*)([012])(3*)$") + + -- + -- Combine the prefix, num (with 1 added) and the tail (with + -- its 3s replaced by 1s), then in the result, replace each '11' + -- with '12', and remove the leading 0 (if any). + -- + return (prefix .. tostring (tonumber (num) + 1) + .. tail : gsub ("3", "1")) : gsub ("11", "12") + : gsub ("^0", "") +end + + +for num in io . lines () do + local number = "0" + for _ = 1, tonumber (num) do + number = next_number (number) + end + print (number) +end diff --git a/challenge-119/abigail/node/ch-2.js b/challenge-119/abigail/node/ch-2.js new file mode 100644 index 0000000000..656c218f54 --- /dev/null +++ b/challenge-119/abigail/node/ch-2.js @@ -0,0 +1,39 @@ +#!/usr/local/bin/node + +// +// See ../README.md +// + +// +// Run as: node ch-2.js < input-file +// + + require ('readline') +. createInterface ({input: process . stdin}) +. on ('line', (num) => { + let number = "0"; + for (let i = 0; i < + num; i ++) { + number = next_number (number) + } + console . log (number) +}) + + +function next_number (prev_number) { + // + // Grab the trailing 3s (tail), its preceding number (num), and + // anything before that (prefix). + // + let [match, prefix, num, tail] = + ("0" + prev_number) . match (/^(.*)([012])(3*)$/) + + // + // First, we take the prefix, and add (num + 1) to it, + // then the tail, where we have replaced each 3 by a 1. + // Then replace any '11' with '12' (we can only have 11s at the end). + // Finally, remove any leading 0. + // + return (prefix + (+ num + 1) + (tail . replace (/3/g, "1"))) . + replace (/11/g, "12") . + replace (/^0/, "") +} diff --git a/challenge-119/abigail/perl/ch-2.pl b/challenge-119/abigail/perl/ch-2.pl index b53a827411..4f405c93eb 100644 --- a/challenge-119/abigail/perl/ch-2.pl +++ b/challenge-119/abigail/perl/ch-2.pl @@ -21,15 +21,13 @@ sub next_num ($prev_num) { # # First, replace any trailing 3's with 1's, incrementing the # digit which comes before. - # Then replace any trailing sequence of 1s with 12121... of the same - # length. - # Note we prepend the incoming number with "00" so we can anchor - # against it; we remove any leading 0s at the end. + # Then replace any 11 with 12 (we can only have 11s at the end) + # Note we prepend the incoming number with "0" so we can anchor + # against it; we remove any leading 0 at the end. # - "00$prev_num" =~ - s!([012])(3*)$!($1 + 1) . (1 x length $2)!re =~ - s!([023])((?:11)+)(1?)$!$1 . (12 x ((length $2) / 2)) . $3!re =~ - s!^0+!!r; + "0$prev_num" =~ s!([012])(3*)$!($1 + 1) . ($2 =~ s/3/1/rg)!re + =~ s!11!12!rg + =~ s!^0!!r } while (<>) { diff --git a/challenge-119/adherzog/perl/ch-1.pl b/challenge-119/adherzog/perl/ch-1.pl new file mode 100755 index 0000000000..01420abd81 --- /dev/null +++ b/challenge-119/adherzog/perl/ch-1.pl @@ -0,0 +1,64 @@ +#!/usr/bin/env perl + +############################################################################## +# Perl Weekly Challenge #119 +############################################################################## +# +# Task #1 - Swap Nibbles +# +# You are given a positive integer $N. +# +# Write a script to swap the two nibbles of the binary representation of the +# given number and print the decimal number of the new binary representation. +# +# > A nibble is a four-bit aggregation, or half an octet. +# +############################################################################## + +use strict; +use warnings; +use v5.10; + +use Test::More; + +if (@ARGV) { + say swap_nibbles(@ARGV); +} +else { + my @tests = ( + { input => 101, output => 86, }, + { input => 18, output => 33, }, + + { input => 255, output => 255, }, + ); + + for my $test (@tests) { + is( swap_nibbles( $test->{'input'} ), $test->{'output'}, ); + } + + done_testing(); +} + +exit; + +############################################################################## +# We could convert the number into a binary string, and use substr or a regex +# to extract the nibbles, concatanate them together and then convert back into +# decimal. +# +# Instead, we'll use bit manipulation. +# +# & is bitwise AND. Using $N & 0xF0 gives us the high nibble. $N & 0x0F gives +# us the low nibble. +# +# << and >> are bit shift operators. Shifting by 4 can convert the high nibble +# into the low, and vice versa. +# +# Then recombine with a bitwise OR (|). +# +############################################################################## + +sub swap_nibbles { + my $N = shift; + return ( ( $N & 0xF0 ) >> 4 ) | ( ( $N & 0x0F ) << 4 ); +} diff --git a/challenge-119/adherzog/perl/ch-2.pl b/challenge-119/adherzog/perl/ch-2.pl new file mode 100755 index 0000000000..9e1135ad8b --- /dev/null +++ b/challenge-119/adherzog/perl/ch-2.pl @@ -0,0 +1,78 @@ +#!/usr/bin/env perl + +############################################################################## +# Perl Weekly Challenge #119 +############################################################################## +# +# Task #2 - Sequence without 1-on-1 +# +# Write a script to generate sequence starting at 1. Consider the increasing +# sequence of integers which contain only 1’s, 2’s and 3’s, and do not have +# any doublets of 1’s like below. Please accept a positive integer $N and +# print the $Nth term in the generated sequence. +# +# > 1, 2, 3, 12, 13, 21, 22, 23, 31, 32, 33, 121, 122, 123, 131, … +# +############################################################################## + +use strict; +use warnings; +use v5.10; + +use Test::More; + +if (@ARGV) { + say get_nth_term_in_sequence(@ARGV); +} +else { + my @tests = ( + { input => 1, output => 1, }, + { input => 2, output => 2, }, + { input => 3, output => 3, }, + { input => 4, output => 12, }, + { input => 5, output => 13, }, + { input => 6, output => 21, }, + { input => 7, output => 22, }, + { input => 8, output => 23, }, + { input => 9, output => 31, }, + { input => 10, output => 32, }, + { input => 11, output => 33, }, + { input => 12, output => 121, }, + { input => 13, output => 122, }, + { input => 14, output => 123, }, + { input => 15, output => 131, }, + { input => 16, output => 132, }, + { input => 17, output => 133, }, + { input => 18, output => 212, }, + { input => 60, output => 2223, }, + { input => 200, output => 31221, }, + { input => 1000, output => 1332223, }, + ); + + for my $test (@tests) { + my $output = get_nth_term_in_sequence( $test->{'input'} ); + is( $output, $test->{'output'} ); + } + + done_testing(); +} + +exit; + +############################################################################## +# +# This is just a basic bruteforce implementation, but it works. +# +############################################################################## + +sub get_nth_term_in_sequence { + my $N = shift; + + my $term = 0; + while ( $N > 0 ) { + $term++; + $N-- if ( $term =~ /^[123]+$/ && $term !~ /11/ ); + } + + return $term; +} diff --git a/challenge-119/belmark-caday/README b/challenge-119/belmark-caday/README new file mode 100644 index 0000000000..6726590965 --- /dev/null +++ b/challenge-119/belmark-caday/README @@ -0,0 +1 @@ +Solutions by Belmark Caday. diff --git a/challenge-119/duane-powell/perl/ch-1.pl b/challenge-119/duane-powell/perl/ch-1.pl new file mode 100644 index 0000000000..f0d0ecf19e --- /dev/null +++ b/challenge-119/duane-powell/perl/ch-1.pl @@ -0,0 +1,64 @@ +#!/usr/bin/perl +use warnings; +use strict; +use feature 'say'; + +# Problem: https://perlweeklychallenge.org/blog/perl-weekly-challenge-119/ TASK #1 +my $d = shift || 0; +my $f = BinaryFOO->new(); +say $f->nibble_swap($d); +exit; + +package BinaryFOO; +sub new { + return bless {}, shift; +} +sub dec_to_bin { + my $self = shift; + my $dec = shift; + return sprintf "%b", $dec; +} +sub bin_to_dec { + my $self = shift; + my $bin = shift; + return oct("0b".$bin); +} +sub is_palidrome { + my $self = shift; + my $bin = shift; + return ($bin eq reverse($bin)); +} +sub nibble_split { + my $self = shift; + my $bin = shift; + + # make sure we have an octet (8 char length minimum) + $bin = '0'x8 . $bin; + $bin = substr($bin,-8); + # split into 2 nibbles + return (substr($bin,0,4), substr($bin,-4)); +} +sub nibble_swap { + my $self = shift; + my $dec = shift; + return "$dec is greater than 255" if ($dec > 255); + my @n = $self->nibble_split($self->dec_to_bin($dec)); + return $self->bin_to_dec($n[1].$n[0]); +} +1; + +__END__ + +./ch-1.pl +0 +./ch-1.pl 101 +86 +./ch-1.pl 18 +33 +./ch-1.pl 255 +255 +./ch-1.pl 15 # 00001111 => 11110000 +240 +./ch-1.pl 240 +15 + diff --git a/challenge-119/duane-powell/perl/ch-2.pl b/challenge-119/duane-powell/perl/ch-2.pl new file mode 100644 index 0000000000..55a6f564d1 --- /dev/null +++ b/challenge-119/duane-powell/perl/ch-2.pl @@ -0,0 +1,55 @@ +#!/usr/bin/perl +use warnings; +use strict; +use feature 'say'; + +# Problem: https://perlweeklychallenge.org/blog/perl-weekly-challenge-119/ TASK #2 + +my $N = shift || 1; +$N = seq_without_1_on_1($N); +say $N; +exit; + +sub seq_without_1_on_1 { + my $N = shift; + + # init counter i, Nth in sequence n, and base4 number t + my ($i, $n, $t) = (1, 0, 1); + # loop until we reach the Nth number in the sequence + while ($n < $N) { + # base4 number can only be composed of the digits 0-3 + $t = base4($i++); + + # discard this number if it matches '0' or '11' + next if ($t =~ m/0|11/); + + $n++; + } + return $t +} + +sub base4 { + my $n = shift; + + return $n if ($n == 0 || $n == 1 || $n == 2 || $n == 3); + my $k = int($n/4); + my $b = $n % 4; + my $E = base4($k); + return $E . $b; +} + +__END__ + +./ch-2.pl 5 +13 +./ch-2.pl 10 +32 +./ch-2.pl 60 +2223 +./ch-2.pl 1223 +2222222 +./ch-2.pl 1929 +3333333 +./ch-2.pl 10000 +231233321 + diff --git a/challenge-119/e-choroba/perl/ch-1.pl b/challenge-119/e-choroba/perl/ch-1.pl new file mode 100755 index 0000000000..67bc443d5c --- /dev/null +++ b/challenge-119/e-choroba/perl/ch-1.pl @@ -0,0 +1,17 @@ +#!/usr/bin/perl +use warnings; +use strict; + +sub swap_nibbles { + my ($n) = @_; + return unpack C => + pack h2 => + unpack H2 => + pack C => $n +} + +use Test2::V0; +plan(2); + +is swap_nibbles(101), 86, 'Example 1'; +is swap_nibbles(18), 33, 'Example 2'; diff --git a/challenge-119/e-choroba/perl/ch-2.pl b/challenge-119/e-choroba/perl/ch-2.pl new file mode 100755 index 0000000000..c380384251 --- /dev/null +++ b/challenge-119/e-choroba/perl/ch-2.pl @@ -0,0 +1,108 @@ +#!/usr/bin/perl +use warnings; +use strict; +use feature qw{ say }; + +sub seq_naive { + my ($n) = @_; + my $e = 0; + while ($n--) { + 1 while ++$e =~ /[^123]|11/; + } + return $e +} + +use PDL; +sub _of_length { + my ($n) = @_; + my $recurrence = pdl([[0, 1], [2, 2]]); + my $m = $recurrence; + $m x= $recurrence for 0 .. $n - 2; + $m x= pdl([[1], [3]]); + return $m->at(0, 0) +} + +sub seq_matrix { + my ($n) = @_; + my $l = 1; + my $predecessors = 0; + my $o = 0; + do { + $o = _of_length($l++); + $predecessors += $o; + } while $predecessors < $n; + + my $element; + if ($n < $predecessors - $o / 2) { + $element = '3' x ($l - 2); + $predecessors -= $o; + until ($predecessors++ == $n) { + 1 while ++$element =~ /[^123]|11/; + } + } else { + $element = '3' x ($l - 1); + until ($predecessors-- == $n) { + 1 while --$element =~ /[^123]|11/; + } + + } + return $element +} + +use Test2::V0 qw{ plan is }; +plan(31); + +is seq_naive(5), 13, 'Example 1 naive'; +is seq_naive(10), 32, 'Example 2 naive'; +is seq_naive(60), 2223, 'Example 3 naive'; + +is seq_matrix(5), 13, 'Example 1 matrix'; +is seq_matrix(10), 32, 'Example 2 matrix'; +is seq_matrix(60), 2223, 'Example 3 matrix'; + +my @inputs = (1 .. 20, 100, 250, 500, 750, 1000); +is seq_matrix($_), seq_naive($_), "same $_" for @inputs; + +use Benchmark qw{ cmpthese }; +cmpthese(-3, { + naive => sub { seq_naive($_) for @inputs }, + matrix => sub { seq_matrix($_) for @inputs }, +}); + +=head1 Sequence without 1-on-1 + +=head2 Using a matrix + +Let's call the sequence without 1-on-1 "Sw1". + +Let's consider a sequence s[1], s[2], s[3], ... where each s[i] says how many +elements of length i exist in Sw1. This sequence can be computed from a matrix, +using + + | s[i] | | 0 1 |^i-2 |1| + | s[i+1] | = | 2 2 | x |3| + +If we define + + s'[i] = s[1] + s[2] + ... + s[i-1] + +then s'[i] tells us how many elements in the sequence Sw1 precedes the first +element of length i. + +Calculating Sw1[n] can be a bit faster now: find the i such that + + s'[i] <= n <= s'[i+1] + +If n is closer to s'[i] than s'[i+1], start with '3' x (i-1) and "increment" it +(n - s'[i]) times. Otherwise, start with '3' x i and "decrement" it (s'[i+1] - +n) times; where in/de-crement means finding the following or preceding number +in the Sw1 sequence. + +Results like 222222 still take a lot of time, but results closer to the +increment of length are found much faster. + + Rate naive matrix + naive 1.17/s -- -35% + matrix 1.79/s 53% -- + |