diff options
33 files changed, 1975 insertions, 1022 deletions
diff --git a/challenge-055/javier-luque/blog.txt b/challenge-055/javier-luque/blog.txt new file mode 100644 index 0000000000..56430d807c --- /dev/null +++ b/challenge-055/javier-luque/blog.txt @@ -0,0 +1 @@ +https://perlchallenges.wordpress.com/2020/04/06/perl-weekly-challenge-055/ diff --git a/challenge-055/javier-luque/perl/ch-1.pl b/challenge-055/javier-luque/perl/ch-1.pl new file mode 100644 index 0000000000..c195f61949 --- /dev/null +++ b/challenge-055/javier-luque/perl/ch-1.pl @@ -0,0 +1,90 @@ +#!/usr/bin/perl +# Test: ./ch-1.pl 2 3 +use strict; +use warnings; +use feature qw /say/; + +my $b = $ARGV[0]; +my $n = $ARGV[1]; + +# Calculate $n if not supplied +$n = int(log($b) / log(2)) + 1 + unless($n); + +# Lets keep it to 1 to 32 bits and +# throw out bits outside of our range +$n = 32 if ($n > 32); +$n = 1 if ($n < 1); +my $mask = (2 ** $n - 1); +$b = $b & $mask; + +# Print the original number +say "ORIGINAL: " . sprintf("%0${n}B", $b) . "\n"; + +# Store the solution; +my %solutions; +my $longest_soluton = 0; + +# flip algorithm +for my $l (0 .. $n -1) { + for my $r ($l .. $n - 1) { + # We create two bit masks. + # The first mask is what we use to flip the bits + # and the second mask is what we use to keep the + # original builts then add up the flipped bits + # with the kept bits + + # Flip Mask + my $flip_mask = 0; + for my $i ($l .. $r) { + $flip_mask += (2 ** ($n - $i - 1) ); + } + + # Calculate the keep mask + my $keep_mask = (~ $flip_mask) & $mask; + + # Flip the relevant bits and calculate kept bits + my $flipped_bits = ~ ($b & $flip_mask) & $flip_mask; + my $kept_bits = $b & $keep_mask; + + # Add the bits outside the flipped bit + my $flipped_number = $flipped_bits + $kept_bits; + + # Now store the number of ones + my $length = calculate_true_bits($flipped_number); + + # Store the solutions + $solutions{$length} = [] + unless ($solutions{$length}); + + push @{$solutions{$length}}, { + L => $l, + R => $r, + number => $flipped_number + }; + + # Length of the longest solution + $longest_soluton = $length + if ($longest_soluton < $length); + } +} + +# Print the solutions +say "SOLUTIONS length($longest_soluton):"; +for my $solution (@{$solutions{$longest_soluton}}) { + say 'L: ' . $solution->{L} . + ' R: ' . $solution->{R} . + ' number: ' . sprintf("%0${n}B", $solution->{number}); +} + +# Calculate the number of true bits +sub calculate_true_bits { + my $number = shift; + my $count = 0; + + do { + $count++ if ($number & 1); + } while ($number = $number >> 1); + + return $count; +} diff --git a/challenge-055/javier-luque/perl/ch-2.pl b/challenge-055/javier-luque/perl/ch-2.pl new file mode 100644 index 0000000000..0658a75b6d --- /dev/null +++ b/challenge-055/javier-luque/perl/ch-2.pl @@ -0,0 +1,27 @@ +#!/usr/bin/perl +# Test: ./ch-1.pl 4 +use strict; +use warnings; +use feature qw /say/; +use Algorithm::Combinatorics qw(permutations); + +my $n = $ARGV[0]; +my @array = (1 .. $n); + +# Permutations +my $iter = permutations(\@array); + +# Loop through each combination +while (my $p = $iter->next) { + my $is_wave = 1; + + for (my $i = 1; $i < scalar(@$p); $i++) { + if ( $i % 2 == 1 && $p->[$i] >= $p->[$i - 1] || + $i % 2 == 0 && $p->[$i] <= $p->[$i - 1] ) {; + $is_wave = 0; + last; + } + } + + say join ' ', @$p if ($is_wave); +} diff --git a/challenge-055/javier-luque/raku/ch-1.p6 b/challenge-055/javier-luque/raku/ch-1.p6 new file mode 100644 index 0000000000..5fb8b9d065 --- /dev/null +++ b/challenge-055/javier-luque/raku/ch-1.p6 @@ -0,0 +1,80 @@ +# Test: perl6 ch-1.p6 2 3 + +multi MAIN(Int $b where * > 0) { + my $n = ((log($b) / log(2)) + 1).Int; + $n = 32 if ($n > 32); + MAIN($b, $n); +} + +multi MAIN(Int $a where * > 0 , Int $n where 0 < * < 32) { + # Throw out bits outside of our range + my $mask = (2 ** $n - 1); + my $b = $a +& $mask; + + # Original binary + say "ORIGINAL: " ~ sprintf("%0*b", $n, $b) ~ "\n"; + + # Store the solution; + my %solutions; + my $longest_solution = 0; + + # flip algorithm + for (0 .. $n -1) -> $l { + for ($l .. $n - 1) -> $r { + # Flip Mask + my $flip_mask = 0; + for ($l .. $r) -> $i { + $flip_mask += (2 ** ($n - $i - 1) ); + } + + # Calculate the keep mask + my $keep_mask = (+^ $flip_mask) +& $mask; + + # Flip the relevant bits and calculate kept bits + my $flipped_bits = +^ ($b +& $flip_mask) +& $flip_mask; + my $kept_bits = $b +& $keep_mask; + + # Add the bits outside the flipped bit + my $flipped_number = $flipped_bits + $kept_bits; + + # Now store the number of ones + my $length = calculate-true-bits($flipped_number); + + # Store the solutions + %solutions{$length} = [] + unless (%solutions{$length}); + + my %solution = ( + L => $l, + R => $r, + number => $flipped_number + ); + + %solutions{$length}.push(%solution); + + # Length of the longest solution + $longest_solution = $length + if ($longest_solution < $length); + } + } + + say "SOLUTIONS length($longest_solution):"; + for (@(%solutions{$longest_solution})) -> $solution { + say 'L: ' ~ $solution{'L'} ~ + ' R: ' ~ $solution{'R'} ~ + ' Number: ' ~ + sprintf("%0*b", $n, $solution{'number'}); + } +} + +# Calculate the number of true bits +sub calculate-true-bits(Int $n is copy) { + my $count = 0; + + repeat { + $count++ if ($n +& 1); + } while ($n = $n +> 1); + + return $count; +} + diff --git a/challenge-055/javier-luque/raku/ch-2.p6 b/challenge-055/javier-luque/raku/ch-2.p6 new file mode 100644 index 0000000000..e45180bb93 --- /dev/null +++ b/challenge-055/javier-luque/raku/ch-2.p6 @@ -0,0 +1,17 @@ +# Test: perl6 ch-2.p6 4 +sub MAIN(Int $n where * > 0) { + [1 .. $n].permutations.grep({is-wave($_)}).join("\n").say; +} + +# Is the array a wave +sub is-wave(@n) { + my $is_wave = True; + loop (my $i = 1; $i < @n.elems; $i++) { + if ( $i % 2 == 1 && @n[$i] >= @n[$i - 1] || + $i % 2 == 0 && @n[$i] <= @n[$i - 1] ) {; + $is_wave = False; + last; + } + } + return $is_wave; +} diff --git a/challenge-055/lubos-kolouch/perl/ch-1.pl b/challenge-055/lubos-kolouch/perl/ch-1.pl new file mode 100644 index 0000000000..f6145d3e5c --- /dev/null +++ b/challenge-055/lubos-kolouch/perl/ch-1.pl @@ -0,0 +1,42 @@ +##!/usr/bin/env perl + +use strict; +use warnings; +use Data::Dumper; +use feature qw/say/; + +sub process_all_flips { + my $binary = shift; + my %all_results; + + my $max = 0; + + my @numbers = split //, $binary; + + for my $l_count ( 0 .. scalar(@numbers)-1 ) { + for my $r_count ( $l_count .. scalar(@numbers)-1 ) { + my $inverted = do_flip( $l_count, $r_count, $binary ); + my $ones_count = () = $inverted =~ /1/gi; + push @{ $all_results{$ones_count} }, [ $l_count, $r_count ]; + $max = $ones_count if $ones_count > $max; + } + } + + return $all_results{$max}; +} + +sub do_flip { + + my ( $l_count, $r_count, $input ) = @_; + + my @binary = split //, $input; + + for my $str_pos ( $l_count .. $r_count ) { + $binary[$str_pos] = $binary[$str_pos] == 1 ? 0:1; + } + + return join '', @binary; +} + +my $result = process_all_flips("010"); +warn Dumper \$result; diff --git a/challenge-055/lubos-kolouch/perl/ch-2.pl b/challenge-055/lubos-kolouch/perl/ch-2.pl new file mode 100644 index 0000000000..d49b674046 --- /dev/null +++ b/challenge-055/lubos-kolouch/perl/ch-2.pl @@ -0,0 +1,50 @@ +##!/usr/bin/env perl + +use strict; +use warnings; +use Math::Combinatorics; +use Data::Dumper; +use feature qw/say/; + +sub process_all_waves { + + my $arr_ref = shift; + + my @result; + + my $combinat = Math::Combinatorics->new( + count => scalar(@$arr_ref), + data => [@$arr_ref], + ); + + while ( my @permu = $combinat->next_permutation ) { + push @result, \@permu if check_wave( \@permu ); + } + + return \@result; +} + +sub check_wave { + my $perm_ref = shift; + + # 1 = greater, -1 = smaller + my $direction = 1; + + for ( 0 .. scalar(@$perm_ref) - 2 ) { + if ( $direction == 1 ) { + # stop if wave is broken + return 0 if $$perm_ref[$_] < $$perm_ref[ $_ + 1 ]; + } + else { + return 0 if $$perm_ref[$_] > $$perm_ref[ $_ + 1 ]; + } + + $direction *= -1; + } + + return 1; +} + +my $all_waves = process_all_waves( [ 1, 2, 3, 4 ] ); + +warn Dumper \$all_waves; diff --git a/challenge-055/lubos-kolouch/python/ch-2.py b/challenge-055/lubos-kolouch/python/ch-2.py new file mode 100644 index 0000000000..aa459474af --- /dev/null +++ b/challenge-055/lubos-kolouch/python/ch-2.py @@ -0,0 +1,77 @@ +##!/usr/bin/env python +""" https://perlweeklychallenge.org/blog/perl-weekly-challenge-055/ + Challenge 2 - Wave Array """ + +from itertools import permutations +import sys + + +class WaveArray: + """ Does the wave according to the excercise """ + + def __init__(self, to_wave: str): + self.to_wave = to_wave + self.current_wave = None + self.all_waves = list() + + def process_all_waves(self): + """ process all possible permutations""" + + for my_permut in permutations(self.to_wave, len(self.to_wave)): + self.current_wave = my_permut + if self.check_wave: + self.all_waves.append(self.current_wave) + + return self.all_waves + + @property + def check_wave(self): + """ Check the wave """ + + # 1 = greater, -1 = smaller + direction = 1 + for seq_count in range(len(self.current_wave)-1): + if seq_count == len(self.current_wave): + break + if direction == 1: + # stop if wave is broken + if self.current_wave[seq_count] < self.current_wave[seq_count+1]: + return False + else: + if self.current_wave[seq_count] > self.current_wave[seq_count+1]: + return False + + direction *= -1 + + return True + + +class WaveTest: + """ run the tests """ + + def __init__(self): + self.test_waveper = None + + def test_all(self): + """ Do the tests """ + + self.test_waveper = WaveArray("1234") + all_waves = self.test_waveper.process_all_waves() + assert all_waves == [('2', '1', '4', '3'), ('3', '1', '4', '2'), + ('3', '2', '4', '1'), ('4', '1', '3', '2'), + ('4', '2', '3', '1')] + + +def main(): + """ main """ + waver = WaveArray(sys.argv[1]) + + all_waves = waver.process_all_waves() + print(f'{all_waves}') + wave_tester = WaveTest() + wave_tester.test_all() + + +if __name__ == "__main__": + assert len(sys.argv) == 2 + main() diff --git a/challenge-055/mohammad-anwar/perl/ch-1.pl b/challenge-055/mohammad-anwar/perl/ch-1.pl new file mode 100644 index 0000000000..698f8ec222 --- /dev/null +++ b/challenge-055/mohammad-anwar/perl/ch-1.pl @@ -0,0 +1,58 @@ +#!/usr/bin/perl + +use strict; +use warnings; + +my $binary_str = $ARGV[0]; + +print "$binary_str => ", flip_binary($binary_str), "\n"; + +# +# +# METHOD + +sub flip_binary { + my ($binary_str) = @_; + + die "ERROR: Missing binary string.\n" + unless defined $binary_str; + die "ERROR: Invalid binary string [$binary_str].\n" + unless ($binary_str =~ /^[01]+$/); + + my $result = {}; + my $size = length($binary_str); + foreach my $left (1 .. $size) { + foreach my $right ($left .. $size) { + my $_binary_str = $binary_str; + foreach my $i ($left .. $right) { + --$i; + my $c = substr($_binary_str, $i, 1); + $c = ($c) ? (0) : (1); + substr($_binary_str, $i, 1, $c); + } + $result->{ sprintf("%s (%s,%s)", $_binary_str, $left, $right) } = ($_binary_str =~ tr/1/1/); + } + } + + return flipped_binary($result); +} + +sub flipped_binary { + my ($result) = @_; + + my $v; + my @r; + foreach my $k (sort { $result->{$b} <=> $result->{$a} } sort keys %$result) { + if (defined $v) { + if ($result->{$k} == $v) { + push @r, $k; + } + } + else { + $v = $result->{$k}; + push @r, $k; + } + } + + return join (" | ", @r); +} diff --git a/challenge-055/mohammad-anwar/perl/ch-1a.pl b/challenge-055/mohammad-anwar/perl/ch-1a.pl new file mode 100644 index 0000000000..3366aaadff --- /dev/null +++ b/challenge-055/mohammad-anwar/perl/ch-1a.pl @@ -0,0 +1,62 @@ +#!/usr/bin/perl + +use strict; +use warnings; + +use Test::More; + +is (flip_binary("10001"), "11111 (2,4)"); +is (flip_binary("10101"), "10111 (4,4) | 11011 (2,4) | 11101 (2,2)"); +is (flip_binary("00101"), "11011 (1,4) | 11101 (1,2)"); + +done_testing; + +# +# +# METHOD + +sub flip_binary { + my ($binary_str) = @_; + + die "ERROR: Missing binary string.\n" + unless defined $binary_str; + die "ERROR: Invalid binary string [$binary_str].\n" + unless ($binary_str =~ /^[01]+$/); + + my $result = {}; + my $size = length($binary_str); + foreach my $left (1 .. $size) { + foreach my $right ($left .. $size) { + my $_binary_str = $binary_str; + foreach my $i ($left .. $right) { + --$i; + my $c = substr($_binary_str, $i, 1); + $c = ($c) ? (0) : (1); + substr($_binary_str, $i, 1, $c); + } + $result->{ sprintf("%s (%s,%s)", $_binary_str, $left, $right) } = ($_binary_str =~ tr/1/1/); + } + } + + return flipped_binary($result); +} + +sub flipped_binary { + my ($result) = @_; + + my $v; + my @r; + foreach my $k (sort { $result->{$b} <=> $result->{$a} } sort keys %$result) { + if (defined $v) { + if ($result->{$k} == $v) { + push @r, $k; + } + } + else { + $v = $result->{$k}; + push @r, $k; + } + } + + return join (" | ", @r); +} diff --git a/challenge-055/mohammad-anwar/raku/ch-1.p6 b/challenge-055/mohammad-anwar/raku/ch-1.p6 new file mode 100644 index 0000000000..1e7ac45a29 --- /dev/null +++ b/challenge-055/mohammad-anwar/raku/ch-1.p6 @@ -0,0 +1,58 @@ +#!/usr/bin/env perl6 + +use v6.c; + +multi sub MAIN(*@) is hidden-from-USAGE { + say $*USAGE; + say "\nERROR: Invalid binary string !!!"; +} + +multi sub MAIN(Str :$binary-str where { m/^ <[01]>+ $/ }) { + say ($binary-str, flip-binary($binary-str)).join(" => "); +} + +sub flip-binary(Str $binary-str) { + + my %result; + my $size = $binary-str.chars; + for 1 .. $size -> $left { + for $left .. $size -> $right { + my $_binary-str = $binary-str; + for $left .. $right -> $i is copy { + --$i; + my $c = $_binary-str.substr($i, 1); + $c = ($c eq "1") ?? (0) !! (1); + $_binary-str.substr-rw($i, 1) = $c; + } + + my $k = sprintf("%s (%s,%s)", $_binary-str, $left, $right); + my $v = $_binary-str.comb("1").elems; + %result{$k} = $v; + } + } + + return flipped-binary(%result); +} + +sub flipped-binary(%result) { + + my Int $value; + my @r; + for %result.sort({ $^b.value <=> $^a.value || $^a.key cmp $^b.key }) -> $pair { + + my $_k = $pair.keys; + my $_v = $pair.values.Str.Int; + + if defined $value { + if $_v == $value { + push @r, $_k; + } + } + else { + $value = $_v; + push @r, $_k; + } + } + + return @r.join(" | "); +} diff --git a/challenge-055/mohammad-anwar/raku/ch-1a.p6 b/challenge-055/mohammad-anwar/raku/ch-1a.p6 new file mode 100644 index 0000000000..500878bbcf --- /dev/null +++ b/challenge-055/mohammad-anwar/raku/ch-1a.p6 @@ -0,0 +1,58 @@ +#!/usr/bin/env perl6 + +use Test; + +my $unit-tests = { + "10001" => "11111 (2,4)", + "10101" => "10111 (4,4) | 11011 (2,4) | 11101 (2,2)", + "00101" => "11011 (1,4) | 11101 (1,2)" +}; + +is(flip-binary($_), $unit-tests{$_}, "Tesing binary $_") for $unit-tests.keys; + +done-testing; + +sub flip-binary(Str $binary-str) { + + my %result; + my $size = $binary-str.chars; + for 1 .. $size -> $left { + for $left .. $size -> $right { + my $_binary-str = $binary-str; + for $left .. $right -> $i is copy { + --$i; + my $c = $_binary-str.substr($i, 1); + $c = ($c eq "1") ?? (0) !! (1); + $_binary-str.substr-rw($i, 1) = $c; + } + my $k = sprintf("%s (%s,%s)", $_binary-str, $left, $right); + my $v = $_binary-str.comb("1").elems; + %result{$k} = $v; + } + } + + return flipped-binary(%result); +} + +sub flipped-binary(%result) { + + my Int $v; + my @r; + for %result.sort({ $^b.value <=> $^a.value || $^a.key cmp $^b.key }) -> $pair { + + my $_k = $pair.keys; + my $_v = $pair.values.Str.Int; + + if (defined $v) { + if ($_v == $v) { + push @r, $_k; + } + } + else { + $v = $_v; + push @r, $_k; + } + } + + return @r.join(" | "); +} diff --git a/challenge-055/richard-park/apl/FlipBinary.aplf b/challenge-055/richard-park/apl/FlipBinary.aplf new file mode 100644 index 0000000000..248a6f09dc --- /dev/null +++ b/challenge-055/richard-park/apl/FlipBinary.aplf @@ -0,0 +1,12 @@ + FlipBinary←{ +⍝ ⍵: Binary number b of length n + n←≢b←⍵ +⍝ Flip 2 indices L≤R<N and count the number of 1s +⍝ ←: L R pairs which result in maximum 1s + To←{⍺+⍳1+⍵-⍺} ⍝ Integers ⍺ to ⍵ inclusive + flip←{⍵/⍨≤/¨⍵},⍳n n ⍝ Possible flip indices L R + flerp←(⊃To/)¨flip ⍝ Interpolate integers from L to R + f←⍵∘{~@⍵⊢⍺}¨flerp ⍝ b flipped at each set of flip indices + max←⌈/sum←+/¨f ⍝ Maximum number of 1s + flip[⍸sum=max] ⍝ Flip indices which result in maximum 1s + } diff --git a/challenge-055/richard-park/apl/Pmat.aplf b/challenge-055/richard-park/apl/Pmat.aplf new file mode 100644 index 0000000000..12be0666b9 --- /dev/null +++ b/challenge-055/richard-park/apl/Pmat.aplf @@ -0,0 +1,6 @@ + Pmat←{⎕ML←1 ⍝ dfns pmat: Permutation matrix of ⍳⍵. + { ⍝ perms of ⍳⍵: + 1≥⍴⍵:↑,↓⍵ ⍝ short vector: done. + ↑⍪/⍵,∘∇¨⍵∘~¨⍵ ⍝ items prefix sub-perms of remainder. + }⍳⍵ ⍝ permutations of identity perm. + } diff --git a/challenge-055/richard-park/apl/WaveArray.aplf b/challenge-055/richard-park/apl/WaveArray.aplf new file mode 100644 index 0000000000..06fdfa0dd9 --- /dev/null +++ b/challenge-055/richard-park/apl/WaveArray.aplf @@ -0,0 +1,13 @@ + WaveArray←{ +⍝ Thanks to Total Array Ordering, an array ⍵ can be reordered so that its major cells, m, have the property +⍝ (1⌷⍵)≥(2⌷⍵)≤(3⌷⍵)≥(4⌷⍵)≤... +⍝ ⍵: Array +⍝ ←: Array of rank (1+≢⍴⍵) where each major cell is a wave permutation of ⍵ + n←≢⍵ + p←⍵⌷⍤0 99⍨Pmat n ⍝ Permutations of ⍵ + gte←(¯1+n)⍴1 0 ⍝ Wave-array greater-than or equal pattern + lte←~gte ⍝ Wave-array less-than or equal pattern + g←gte≡⍤1⊢2≥/(⍋⍋)⍤¯1⊢p ⍝ Permutations with wave gte pattern + l←lte≡⍤1⊢2≤/(⍋⍋)⍤¯1⊢p ⍝ Permutations with wave lte pattern + ∪(g∧l)⌿p ⍝ Unique wave permutations of ⍵ + } diff --git a/challenge-055/richard-park/apl/ch-1.aplf b/challenge-055/richard-park/apl/ch-1.aplf new file mode 100644 index 0000000000..248a6f09dc --- /dev/null +++ b/challenge-055/richard-park/apl/ch-1.aplf @@ -0,0 +1,12 @@ + FlipBinary←{ +⍝ ⍵: Binary number b of length n + n←≢b←⍵ +⍝ Flip 2 indices L≤R<N and count the number of 1s +⍝ ←: L R pairs which result in maximum 1s + To←{⍺+⍳1+⍵-⍺} ⍝ Integers ⍺ to ⍵ inclusive + flip←{⍵/⍨≤/¨⍵},⍳n n ⍝ Possible flip indices L R + flerp←(⊃To/)¨flip ⍝ Interpolate integers from L to R + f←⍵∘{~@⍵⊢⍺}¨flerp ⍝ b flipped at each set of flip indices + max←⌈/sum←+/¨f ⍝ Maximum number of 1s + flip[⍸sum=max] ⍝ Flip indices which result in maximum 1s + } diff --git a/challenge-055/richard-park/apl/ch-2.aplf b/challenge-055/richard-park/apl/ch-2.aplf new file mode 100644 index 0000000000..06fdfa0dd9 --- /dev/null +++ b/challenge-055/richard-park/apl/ch-2.aplf @@ -0,0 +1,13 @@ + WaveArray←{ +⍝ Thanks to Total Array Ordering, an array ⍵ can be reordered so that its major cells, m, have the property +⍝ (1⌷⍵)≥(2⌷⍵)≤(3⌷⍵)≥(4⌷⍵)≤... +⍝ ⍵: Array +⍝ ←: Array of rank (1+≢⍴⍵) where each major cell is a wave permutation of ⍵ + n←≢⍵ + p←⍵⌷⍤0 99⍨Pmat n ⍝ Permutations of ⍵ + gte←(¯1+n)⍴1 0 ⍝ Wave-array greater-than or equal pattern + lte←~gte ⍝ Wave-array less-than or equal pattern + g←gte≡⍤1⊢2≥/(⍋⍋)⍤¯1⊢p ⍝ Permutations with wave gte pattern + l←lte≡⍤1⊢2≤/(⍋⍋)⍤¯1⊢p ⍝ Permutations with wave lte pattern + ∪(g∧l)⌿p ⍝ Unique wave permutations of ⍵ + } diff --git a/challenge-055/ulrich-rieke/cpp/ch-2.cpp b/challenge-055/ulrich-rieke/cpp/ch-2.cpp new file mode 100644 index 0000000000..10adfc4756 --- /dev/null +++ b/challenge-055/ulrich-rieke/cpp/ch-2.cpp @@ -0,0 +1,67 @@ +#include <iostream> +#include <vector> +#include <iterator> +#include <algorithm> +#include <utility> +#include <cstdlib> + +//this function creates pairs of neighbouring numbers in a vector +std::vector<std::pair<int, int>> createDoublets ( const std::vector<int> & numbers ) { + std::vector<std::pair<int , int>> doublets ; + int len = numbers.size( ) ; + for ( int i = 0 ; i < len - 1 ; i++ ) { + std::pair<int , int> p { *(numbers.begin( ) + i ) , + *(numbers.begin( ) + i + 1 ) } ; + doublets.push_back( p ) ; + } + return doublets ; +} + +//in order to create a "wavy list of numbers", a vector of numbers is +//converted into a vector of pairs of neighbouring numbers. To be wavy, +//even-indexed pairs must be descending, odd-indexed ones must ascend. +//if this holds true for all pairs a permutation is "wavy" +bool myCondition( const std::vector<int> & numbers ) { + std::vector<std::pair<int, int>> doublets { createDoublets( numbers ) } ; + int len = doublets.size( ) ; + std::vector<bool> validWavy ; + for (int i = 0 ; i < len ; i++ ) { + std::pair<int , int> p = doublets[ i ] ; + validWavy.push_back (( i % 2 == 0 ) && ( p.first >= p.second ) ) ; + validWavy.push_back (( i % 2 == 1 ) && ( p.first <= p.second ) ) ; + } + int i = 0 ; + for ( auto b : validWavy ) { + if ( b ) + i++ ; + } + return ( i == len ) ; +} + +//numbers are entered as arguments on the command line. A minimum number +//of 2 is desirable and requested +int main( int argc, char * argv[] ) { + std::vector<int> input ; + if ( argc < 3 ) { + std::cout << "There is little sense in permuting such short sequences!\n" ; + return 1 ; + } + for ( int i = 1 ; i < argc ; i++ ) { + input.push_back( std::atoi( argv[ i ] ) ) ; + } + std::vector<std::vector<int>> permus ; + std::vector<std::vector<int>> wavies ; + do { + permus.push_back( input ) ; + } while ( std::next_permutation( input.begin( ) , input.end( ) )) ; + std::copy_if( permus.begin( ) , permus.end( ) , + std::back_inserter( wavies ) , myCondition ) ; + for ( auto & it : wavies ) { + std::cout << "[ " ; + for ( int i : it ) { + std::cout << i << " " ; + } + std::cout << " ]\n" ; + } + return 0 ; +} diff --git a/challenge-055/ulrich-rieke/haskell/ch-2.hs b/challenge-055/ulrich-rieke/haskell/ch-2.hs new file mode 100644 index 0000000000..b87dbe4034 --- /dev/null +++ b/challenge-055/ulrich-rieke/haskell/ch-2.hs @@ -0,0 +1,16 @@ +module Challenge055_2 + where +import Data.List.Split ( divvy ) +import Data.List ( permutations , (!!) ) + +wavyLi |