challenge 070 completed

4 files changed, 541 insertions, 0 deletions

diff --git a/challenge-070/jeongoon/perl/ch-1.pl b/challenge-070/jeongoon/perl/ch-1.pl
new file mode 100644
index 0000000000..8bd9815a46
--- /dev/null
+++ b/challenge-070/jeongoon/perl/ch-1.pl
@@ -0,0 +1,227 @@
+#!/usr/bin/env perl
+# -*- Mode: cperl; cperl-indent-level:4 tab-width: 8; indent-tabs-mode: nil -*-
+# -*- coding: utf-8 -*-
+
+use strict; use warnings;
+use Getopt::Long qw(:config no_ignore_case);
+use Pod::Usage;
+
+BEGIN {
+    $::debugging = 0;
+
+    my $help = 0;
+
+    GetOptions( 'debug' => \$::debugging,
+                "help"  => \$help
+        ) or pod2usage(2);
+
+    pod2usage( -exitval => 0, -verbose => 2 ) if $help;
+
+    our $dprint = sub( @ ) {
+        ++$|;
+        print STDERR "[DBG] ",@_;
+    };
+
+    *::dprint = $::debugging ? $dprint : sub {};
+}
+
+=pod
+
+=head1 Character Swapping
+
+ch-1.pl [--debug] [--help] "String to swap" [Count] [Offset]
+
+=cut
+
+sub charactersSwappedAsExplain ( $$$ ) {
+
+=pod
+
+=head1 Challenge
+
+You are given a string $S of size $N.
+
+=cut
+
+my ( $S, $C, $O ) = @_;
+my $N = length $S;
+
+=pod
+
+You are also given swap count $C and offset $O such that
+$C >= 1, $O >= 1 and $C + $O <= $N.
+
+=cut
+
+::dprint "in charactersSwappedAsExplain:\n";
+die_if_invalid_value( $C, $O, $N );
+
+=pod
+
+ Write a script to perform character swapping like below:
+
+ $S[ 1 % $N ] <=> $S[ (1 + $O) % $N ]
+ $S[ 2 % $N ] <=> $S[ (2 + $O) % $N ]
+ $S[ 3 % $N ] <=> $S[ (3 + $O) % $N ]
+ ...
+ ...
+ $S[ $C % $N ] <=> $S[ ($C + $O) % $N ]
+
+=cut
+
+for my $c ( 1 .. $C ) {
+    my $bak;
+    my $bak_r = '';
+    $bak_r = substr $S, ( $c + $O ) % $N, 1 if $::debugging;
+    $bak = substr $S, $c % $N, 1,
+      ( defined $bak_r  ? $bak_r : substr( $S, ( $c + $O ) % $N, 1 ) );
+    substr $S, ( $c + $O ) % $N, 1, $bak;
+    # or according to https://perldoc.perl.org/functions/substr.html
+    #substr( $S, ( $c + $O ) % $N, 1 ) = $bak;
+
+    ::dprint "Character Swapping:\n";
+    ::dprint "swap $c: $bak <=> $bak_r = $S\n";
+}
+
+=pod
+
+ Input:
+     $S = 'perlandraku'
+     $C = 3
+     $O = 4
+
+ Character Swapping:
+     swap 1: e <=> n = pnrlaedraku
+     swap 2: r <=> d = pndlaerraku
+     swap 3: l <=> r = pndraerlaku
+
+ Output:
+     pndraerlaku
+
+=cut
+
+return $S;
+}
+
+=pod
+
+=head1 My Solution
+ I could simplyfy the process a little bit because I ccould divide the
+pattern into 3 groups ( I wrote alphabet `O' as Ou for clearity of meaning. )
+
+=over
+
+=item 1. when C < O, each index numbers are devided into 5 groups
+
+ [ 0 ] [ C+2 .. C+Ou ] [ C+1 .. Ou ] [ 1 .. C ] [ C+Ou+1 .. N-1 ]
+
+=item 2. C == 0
+
+ [ 0 ] [ C+2 .. C+Ou ] [ 1 .. C ] [ C+Ou+1 .. N-1 ]
+
+=item 3. C > 0
+
+ [ 0 ] [ C+2 .. C+Ou ][ C-Ou .. C ] [ 1.. C+Ou+ 1 ] [ C+O+2 .. N-1 ]
+
+=back
+
+ So I realized that part #1, #2 are always has the same rule, and follow things.
+( note: K = boolean( C > Ou ) )
+
+=over
+
+=item Part #3
+
+ part #3 can rewritten as if K { [ (C-O) .. C ] } else { [ C+1 .. Ou ] }
+
+=item Part #4
+
+ part #4 can be rewritten as [ 1 .. ( C + ( K *(Ou+1) ) ) ]
+
+=item Part #5
+
+ part #5 can be rewritten as [ ( C+Ou+1+K ) .. N-1 ]
+
+=back
+
+=cut
+
+sub charactersSwapped_DBG ( $$$ ) {
+    my ( $S, $C, $O ) = @_;
+    my $N = length $S;
+    my $K = int( $C > $O );
+
+    ::dprint "in charactersSwapped_DBG:\n";
+    die_if_invalid_value( $C, $O, $N );
+
+    my $n;
+    my $part = substr $S, 0, 1;                         # P1
+    ::dprint "P".++$n.": $part\n";
+    my $result = $part;
+    $part = substr $S, $C+2, ( $O-1 );                  # P2
+    ::dprint "P".++$n.": $part\n";
+    $result .= $part;
+    $part = ( $K ? substr( $S, $C-$O, $O+1 )
+              : substr( $S, $C+1, ( $O-$C ) ) );        # P3
+    ::dprint "P".++$n.": $part\n";
+    $result .= $part;
+    $part = substr( $S, 1, $C + ( $K*($O+1) ) );        # P4
+    ::dprint "P".++$n.": $part\n";
+    $result .= $part;
+    $part =substr( $S, ($C+$O+1+$K), ($N-$C-$O-$K-1) ); # P5
+    ::dprint "P".++$n.": $part\n";
+    $result .= $part;
+
+    return $result;
+}
+
+sub charactersSwapped ( $$$ ) {
+    my ( $S, $C, $O ) = @_;
+    my $N = length $S;
+    my $K = int( $C > $O );
+
+    ::dprint "in charactersSwapped:\n";
+    die_if_invalid_value( $C, $O, $N );
+
+    my $result = substr $S, 0, 1;                       # P1
+    $result .= substr $S, $C+2, ( $O-1 );               # P2
+    $result .= ( $K ? substr( $S, $C-$O, $O+1 )
+              : substr( $S, $C+1, ( $O-$C ) ) );        # P3
+    $result .= substr( $S, 1, $C + ( $K*($O+1) ) );     # P4
+    $result .=substr( $S, ($C+$O+1+$K), ($N-$C-$O-$K-1) ); # P5
+
+    return $result;
+}
+
+sub die_if_invalid_value( $$$ ) {
+    my ( $C, $O, $N ) = @_;
+    unless ( $C >=1 || $O >=1 ) {
+        die "[ERR] C(count) and O(Offset) must be equal or more than 1";
+    }
+    unless ( ( $C + $O ) <= $N ) {
+        die "[ERR] \$C($C) + \$O($O) <= \$N($N)";
+    }
+}
+
+package main;
+
+my $Str = shift // 'perlandraku';
+my $Cnt = shift // 3;
+my $Off = shift // 4;
+
+my $answer = '';
+my $try;
+if ( $::debugging ) {
+    $answer = charactersSwappedAsExplain( $Str, $Cnt, $Off );
+    $try = charactersSwapped_DBG( $Str, $Cnt, $Off );
+}
+else {
+    $try = charactersSwapped( $Str, $Cnt, $Off );
+}
+
+
+
+print STDERR "Output:\n";
+::dprint "Expected Answer: ".$answer.$/;
+::dprint "And.. my Answer: ";
+print $try.$/;
diff --git a/challenge-070/jeongoon/perl/ch-2.pl b/challenge-070/jeongoon/perl/ch-2.pl
new file mode 100644
index 0000000000..384728e7fb
--- /dev/null
+++ b/challenge-070/jeongoon/perl/ch-2.pl
@@ -0,0 +1,206 @@
+#!/usr/bin/env perl
+# -*- Mode: cperl; cperl-indent-level:4 tab-width: 8; indent-tabs-mode: nil -*-
+# -*- coding: utf-8 -*-
+
+use strict; use warnings;
+use Getopt::Long qw(:config no_ignore_case);
+use Pod::Usage;
+
+
+BEGIN {
+    $::debugging   = 0;
+    $::maximum = 5;
+
+    my $help = 0;
+
+    GetOptions( 'debug'         => \$::debugging,
+                "help"          => \$help,
+                'max=i'         => \$::maximum,
+        ) or pod2usage(2);
+
+    pod2usage( -exitval => 0, -verbose => 2 ) if $help;
+
+    our $dprint = sub( @ ) {
+        ++$|;
+        print STDERR "[DBG] ",@_;
+    };
+
+    *::dprint = $::debugging ? $dprint : sub {};
+}
+
+=pod
+
+=head1 2-bit Gray Code Sequence
+
+ch-2.pl [--debug] [--help] [--max=N] [N]
+
+    new-max: if you want increase the maximum value
+    N: where  2 <= N <= 5
+
+=cut
+
+our $seq_two = [ 0, 1, 3, 2 ];
+our @seq_all = ( $seq_two );
+
+sub makeNextSequenceOf ( $ ) { # basic method : not used here
+    my $prev = shift;  # ref !!!
+    my $len = scalar @{$prev};
+    if ( $len % 2 ) {
+        warn 'invalid sequence given: return Nil';
+        return undef;
+    }
+    my $n = 1;
+    while ( $len * 0.5 != 1 ) {
+        ++$n;
+        $len = 0.5 * $len;
+    }
+
+    my ( @left, @right );
+    for ( @$prev ) {
+        push @left, $_;  unshift @right, ( $_ + 2**$n );
+    }
+    return [ @left, @right ];
+}
+
+sub getRef_NBitGrayCodeSeq ( $ ) {
+
+=pod
+
+=head1 Challenge
+
+You are given an integer 2 <= $N <= 5.
+
+Write a script to generate $N-bit gray code sequence.
+
+=cut
+
+    my $N = shift;
+    if ( not defined $N or int($N) ne $N
+         or not ( 2 <= $N and $N <= $::maximum ) ) {
+        # but 5 is too short, I think.
+        die "N is not a number or out of range ( 2 <= N <= $::maximum )";
+}
+
+=pod
+
+To generate the 3-bit Gray code sequence from the 2-bit Gray code sequence, follow the step below:
+
+ 2-bit Gray Code sequence
+ [0, 1, 3, 2]
+ 
+ Binary form of the sequence
+ a) S1 = [00, 01, 11, 10]
+ 
+ Reverse of S1
+ b) S2 = [10, 11, 01, 00]
+ 
+ Prefix all entries of S1 with '0'
+ c) S1 = [000, 001, 011, 010]
+ 
+ Prefix all entries of S2 with '1'
+ d) S2 = [110, 111, 101, 100]
+ 
+ Concatenate S1 and S2 gives 3-bit Gray Code sequence
+ e) [000, 001, 011, 010, 110, 111, 101, 100]
+ 
+ 3-bit Gray Code sequence
+ [0, 1, 3, 2, 6, 7, 5, 4]
+
+=head1 Example:
+
+Input: $N = 4
+
+Output: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
+
+=cut
+
+=pod
+
+=head1 My Solution
+
+if we are looking at the 4th sequence and 2nd sequence we found some similarity
+when we devide 4th sequence into 4 parts it looks like below
+
+ [ 0, 1, 3, 2 ] [ 6, 7, 5, 4 ] [ 12, 13, 15, 14 ] [ 10, 11, 9, 8 ]
+
+and when we number the each part by ascending order it would be
+
+ [ 0, 1, 3, 2 ] [ 6, 7, 5, 4 ] [ 12, 13, 15, 14 ] [ 10, 11, 9, 8 ]
+ ~~~~~  0 ~~~~~  ~~~~~ 1 ~~~~~ ~~~~~~~~~ 3 ~~~~~~ ~~~~~~ 2 ~~~~~~~
+
+this is exactly same as 2nd sequence's number, and we already know what is the
+minimum number and maximum number of each sequence, we can calculate based on
+the 2nd sequence,
+
+Generally speaking, in this case,
+I found that we could skip one step to find out N'th step if we know (N-2)'th sequence.
+
+and every 8 digits must be in order like
+
+ [ 0, 1, 3, 2 ] [ 2, 3, 1, 0 ] [ 0, 1, 3, 2 ] [ 2, 3, 1, 0 ]
+
+which means that if we know the order of each group (in which 4 number is) we can
+sort them in that order.
+
+=cut
+
+    return $seq_all[0] if $N == 2;
+
+    my ( $base, $depth, $is_odd );
+    if ( $N == 3 ) {
+        return makeNextSequenceOf( $seq_two );
+    }
+    else {
+        $base = $N - 4;
+        for ( $depth = 0; not defined $seq_all[$base - $depth]; ++$depth ){ 1 }
+
+        $is_odd = $depth %2;
+    }
+    ::dprint "base = $base;  depth = $depth\n";
+
+    # make bases if needed
+    for ( my $i = 0; $i <= $depth; $i += 2 ) {
+        ::dprint "\$i+2 = ".($i+2). " from \$i = $i\n";
+        my $offset = $base - $depth + $i;
+        $seq_all[$offset+2] = get_sequence_by_using_base( $seq_all[$offset],0 );
+    }
+    $is_odd and
+      $seq_all[$base+2] = get_sequence_by_using_base( $seq_all[$base+1], 1 );
+
+    return $seq_all[$N-2];
+}
+
+sub get_sequence_by_using_base ( $$ ) {
+    my $base_seq = shift;
+    my $first_half_only = shift;
+    my $last_idx = $#{$base_seq};
+    $last_idx *= 0.5 if $first_half_only;
+
+    my @ret;
+
+    my $odd_filp = 1; # initial: odd
+    for my $q ( 0.. $last_idx ) {
+        my $pt = 4* $$base_seq[$q];
+        my @real_value;
+        if ( $odd_filp ) {  # 0      1      3      2
+            @real_value = ( $pt, $pt+1, $pt+3, $pt+2 );
+        } else {            #   2      3     1    0
+            @real_value = ( $pt+2, $pt+3, $pt+1, $pt );
+        }
+        push @ret, @real_value;
+        $odd_filp ^= 1;
+    }
+    return \@ret;
+}
+
+package main;
+
+my $N = shift;
+my $n_seq = getRef_NBitGrayCodeSeq( $N );
+
+die unless scalar @$n_seq;
+
+print STDERR "Input: \$N = $N\n";
+print STDERR  "Output: ";
+$" = ', ';
+print "[@{$n_seq} ]\n";
diff --git a/challenge-070/jeongoon/raku/ch-1.raku b/challenge-070/jeongoon/raku/ch-1.raku
new file mode 100644
index 0000000000..a43ecf111b
--- /dev/null
+++ b/challenge-070/jeongoon/raku/ch-1.raku
@@ -0,0 +1,26 @@
+#!/usr/bin/env raku
+# -*- Mode: Raku; indent-tabs-mode: nil; coding: utf-8 -*-
+# vim: set et ts=4 sw=4:
+
+sub MAIN (
+    Str:D $S = 'perlandraku',        #= string to change: default: 'peralandraku'
+    Int:D $C where { $C >= 1 } = 3, #= how many times to change: >= 1; default: 3
+    Int:D $O where { $O >= 1 && $C+$O < $S.chars } = 4, #= offset between character: default 4
+) {
+
+    my $N = $S.chars;
+    my $K = $C > $O;
+    $*ERR.say: "String: $S";
+    $*ERR.say: "Params: C = {$C};   O = {$O};   N = {$N}";
+
+    my $result;
+    with $S {
+        $result  = .substr( 0, 1 ) # 1
+        ~ .substr( $C+2 .. $C+$O ) # 2
+        ~ .substr( $K ?? $C-$O .. $C !! $C+1 .. $O ) # 3
+        ~ .substr( 1 .. ( $C + $K*($O+1) ) ) # 4
+        ~ .substr( ( $C+$O+1+$K) .. $N -1 );
+    }
+    $*ERR.say: "Output:";
+    $result.say;
+}
diff --git a/challenge-070/jeongoon/raku/ch-2.raku b/challenge-070/jeongoon/raku/ch-2.raku
new file mode 100644
index 0000000000..8ed93906fc
--- /dev/null
+++ b/challenge-070/jeongoon/raku/ch-2.raku
@@ -0,0 +1,82 @@
+#!/usr/bin/env raku
+# -*- Mode: Raku; indent-tabs-mode: nil; coding: utf-8 -*-
+# vim: set et ts=4 sw=4:
+
+# test: raku ch-2.raku --max=6 6
+
+our $seqTwo = [ 0, 1, 3, 2 ];
+our @seqCache = $seqTwo;
+
+class NbitGrayCode {
+    has Int $.N;
+    method base-index () returns Int  { return $!N-4 } # N=4 => base index (N=2): 0
+    method depth-to-defined () returns Int {
+        my $depth = 0;
+        while ( @seqCache[ self.base-index - $depth ].defined.not ) { ++$depth }
+        return $depth;
+    }
+
+    method my-index () returns Int { self.base-index + 2 }
+
+    submethod BUILD ( Int:D :$max where { $max >= 5 },
+                      Int:D :$N   where  { 2 <= $N <= $max } )  {
+        $!N = $N; # XXX
+
+    }
+
+    method get-graycode () returns Array {
+        given $!N {
+            when 2 { return  $seqTwo }
+            when 3 { # test basic method
+                return @seqCache[ 1 ] = ( $seqTwo.flat,
+                                     ( $seqTwo.reverse X+ 2**2)).flat.Array;
+            }
+        }
+
+        my $d = self.depth-to-defined;
+        loop ( my $i = 0; $i < $d + 1; $i += 2 ) {
+            my $offset = self.base-index - $d + $i;
+            self!generate-seq-from-base( :first($offset+1), :second($offset+2),
+                                       :part-seq( @seqCache[$offset] ) )
+        }
+        if so ( $d % 2 ) { # N = 5, 7, 9 ...
+            self!generate-seq-from-base( :first( self.my-index ),
+                                       :part-seq( @seqCache[ self.my-index - 1 ] ) );
+        }
+        return @seqCache[ self.my-index ].Array;
+    }
+
+    method !generate-seq-from-base( List :$part-seq,
+                               Int:D :$first where { $first > 0 },
+                               Int   :$second? ) {
+        my $half-size = ( $part-seq.elems * 0.5 ).Int;
+
+        @seqCache[$first] = Empty;
+        # slip or |() is very important !! quite different from perl
+        for ^$half-size -> $l, $r {
+            @seqCache[$first] = |( slip(@seqCache[$first]) ),
+                                |( ( 0, 1, 3, 2 ) X+ 4* $part-seq[$l]),
+                                |( ( 2, 3, 1, 0 ) X+ 4* $part-seq[$r]);
+        }
+        #say "first>>>" ~ @seqCache[ $first ];
+
+        return unless $second.defined and $first + 1 == $second;
+
+        @seqCache[$second] = |@seqCache[$first];
+        for $half-size ..$half-size*2 -1 -> $l, $r {
+            @seqCache[ $second ] = |( @seqCache[$second] ),
+            |( ( 0, 1, 3, 2 ) X+ 4* $part-seq[$l] ),
+            |( ( 2, 3, 1, 0 ) X+ 4* $part-seq[$r] );
+        }
+        #say "second>>>" ~ @seqCache[ $second];
+    }
+}
+
+sub MAIN (
+    Int:D $N = 5,          #= N bit where 2 <= $N <= 5
+    Int:D :$max = 5, #= if you want to increase default maximum value
+) {
+    my $ncode = NbitGrayCode.new( :$N, :max( $max ) );
+    $*ERR.print: "Input: \$N = $N\nOutput: ";
+    say ~$ncode.get-graycode.Array.raku;
+}