diff options
| -rw-r--r-- | challenge-086/jeongoon/perl/ch-1.pl | 25 | ||||
| -rw-r--r-- | challenge-086/jeongoon/perl/ch-2.pl | 248 | ||||
| -rw-r--r-- | challenge-086/jeongoon/raku/ch-1.raku | 18 | ||||
| -rw-r--r-- | challenge-086/jeongoon/raku/ch-2.raku | 213 |
4 files changed, 504 insertions, 0 deletions
diff --git a/challenge-086/jeongoon/perl/ch-1.pl b/challenge-086/jeongoon/perl/ch-1.pl new file mode 100644 index 0000000000..3eebe1e36d --- /dev/null +++ b/challenge-086/jeongoon/perl/ch-1.pl @@ -0,0 +1,25 @@ +#!/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 v5.26; + +# tested with: perl ch-1.pl 10 -5 -15 20 30 + +my ($A, @N ) = @ARGV; + +$A < 0 and die "difference between integers cannot be negative"; + +my @n = sort @N; + +for ( my $i = 1; $i < scalar @n; ) { + for ( ($n[$i] - $n[0]) <=> abs $A ) { + if ( $_ == -1 ) { ++$i } + elsif ( $_ == 1 ) { shift @n; $i = 1 } + else { say "1 as $n[$i] - $n[0] = $A"; exit 0 } + } +} + +say "0"; +exit 1; diff --git a/challenge-086/jeongoon/perl/ch-2.pl b/challenge-086/jeongoon/perl/ch-2.pl new file mode 100644 index 0000000000..91eff4c6ca --- /dev/null +++ b/challenge-086/jeongoon/perl/ch-2.pl @@ -0,0 +1,248 @@ +#!/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 v5.32; # syntax for a < x < b + +use Class::Struct; +use List::MoreUtils qw(indexes firstidx uniq); + +struct RowCandi => [ rowNum => '$', candidates=> '%', + NARow => '@', NACol => '@', NAArea => '@', + slots => '@', curValues => '@' ]; + +our $d = 0; +++$|; + +sub newRowCandi ($$) { + my ($sketch, $rn) = @_; + + if ($d) { + say "[$rn] base sketch:"; + say ("[@$_]") for @$sketch; + } + + my @row = @{$$sketch[$rn]}; # copy + my @row_range_for_area; + for ( int($rn / 3) ) { + @row_range_for_area = 3*$_ .. 3*(1+$_) -1 + } + + # generate unavailable numbers + my $na_row = [ uniq @row ]; + my $na_col = [ map { my $c = $_; + [ uniq map { $$sketch[$_][$c] } 0 .. 8 ] + } 0 .. 8 ]; + my $na_area = [ + map { + [ uniq + map { my $c = $_; + map { $$sketch[$_][$c] } @row_range_for_area + } 3*$_ .. (3*(1+$_) -1) ] + } 0..2 ]; # contains only 3 sections + # where the row is laid on + + my $slots = [ indexes { $_ eq '_' } @row ]; + my $rc = RowCandi->new( rowNum => $rn, candidates => {}, + NARow => $na_row, NACol => $na_col, + NAArea => $na_area, + slots => $slots, curValues => [] ); + fillSlots($rc); + $rc +} + +sub fillSlots ($) { + if ($d) { say "In fillSlots() ..." } + my $rc = shift; + my $rn = $rc->rowNum; + my %avail_nums = map { $_ => 1 } ( 1..9 ); + for (@{$rc->NARow}) { delete $avail_nums{$_} } + my %avail_nums_bak = %avail_nums; + + # find empty slots at rightmost + # (where slots[idx] exists but curValue[idx] doesn't) + for ( my $si = scalar @{$rc->curValues}; + $si < scalar @{$rc->slots}; + %avail_nums = %avail_nums_bak ) { + my $cn = $rc->slots->[$si]; # column number; + my $an = int( $cn / 3 ); # area number (0 .. 2) + if ($d) { + say "[$rn;$cn] idx in slot: $si; col: $cn; area: $an"; + say " given: @{[keys %avail_nums]}"; + say " used: @{$rc->curValues}"; + say " nar: @{$rc->NARow}; nac: @{$rc->NACol->[$cn]};"; + say " naa: @{$rc->NAArea->[$an]}"; + + } + + # remove more NA numbers + delete $avail_nums{$_} for ( @{$rc->NACol->[$cn]}, + @{$rc->NAArea->[$an]}, + @{$rc->curValues} ); + + if ($d) { + say " -> available: ". join( ", ", keys %avail_nums ); + } + + if ( %avail_nums ) { + my $avn = (keys %avail_nums)[0]; + if ($d) { say "[$rn;$cn] try $avn ->" } + push @{$rc->curValues}, $avn; # take one of the available + delete $avail_nums{$avn}; # reduce available nums. + $rc->candidates->{$cn} = # update candiates infos. + [keys %avail_nums] if (scalar %avail_nums); + if ($d) { + say "[$rn;$cn] values in slots: @{$rc->curValues}"; + if ( defined $rc->candidates + and defined $rc->candidates->{$cn} ) { + say " and candidates at $cn: @{$rc->candidates->{$cn}}"; + } else { + say " but no candidate at $cn"; + } + } + ++$si; + } + else { + # try next candiates in the current row + if ( not scalar %{$rc->candidates} ) { + return undef; # no more candidates + # at any columns in the row + } + if ($d) { say "[$rn;$cn] no available numbers: try next candidate" } + for my $colnum ( try_next_candidate_( $rc ) ) { + return undef unless defined $colnum; + $si = 1 + firstidx { $_ == $colnum } @{$rc->slots}; + %avail_nums = %avail_nums_bak; # revert available numbers + + } + } + } + !!'succeed' +} + +sub try_next_candidate_ ($) { + my $rc = shift; + return undef unless scalar %{$rc->candidates}; + + my $rn = $rc->rowNum; + my $cn = (sort keys %{$rc->candidates})[-1]; + my $si = firstidx { $_ == $cn } @{$rc->slots}; + + my $candis = $rc->candidates->{$cn}; + + if ($d) { + say "[$rn;$cn] trying anohter candiate($$candis[0]) at column: $cn"; + } + splice @{$rc->curValues}, ($si), (scalar @{$rc->slots}), + shift @{$candis}; # set candiate at cn and remove any after col num. + if (scalar @{$candis} == 0) { + delete $rc->candidates->{$cn}; + } + if ($d) { + say " after choosing values in slots: @{$rc->curValues}"; + say " and candidates at $cn: @{$rc->candidates->{$cn}}" + if defined $rc->candidates + and defined $rc->candidates->{$cn}; + } + + $cn +} + +sub tryNextCandidate ($) { + my $rc = shift; + if ( try_next_candidate_( $rc ) ) { + return fillSlots($rc) + } + undef +} + +sub isAllFilledRow ($) { + my $rc = shift; + scalar @{$rc->slots} == scalar @{$rc->curValues}; +} +sub getRefRowSnapshot ($$) { + my ( $sketch, $rc ) = @_; + my @vals = @{$rc->curValues}; + push @vals, ("?") x ((scalar @{$rc->slots}) - @vals); + + my $row = [ @{$sketch->[$rc->rowNum]} ]; # copy + @$row[ @{$rc->slots} ] = @vals; + return $row; +} + +sub getRefWholeSnapshot ($$) { + my ( $sketch, $rcs ) = @_; + [ map { + my $row = [ @$sketch[$_] ]; # copy + my $rc = $$rcs[$_]; + if ( defined $rc ) { + my @vals = @{$rc->curValues}; + push @vals, ("?") x ((scalar @{$rc->slots}) - @vals); + @$row[ @{$rc->slots} ] = @vals; + } + $row + } (0..$#{$sketch}) ] +} + +my @P = ( [ qw[_ _ _ 2 6 _ 7 _ 1] ], + [ qw[6 8 _ _ 7 _ _ 9 _] ], + [ qw[1 9 _ _ _ 4 5 _ _] ], + [ qw[8 2 _ 1 _ _ _ 4 _] ], + [ qw[_ _ 4 6 _ 2 9 _ _] ], + [ qw[_ 5 _ _ _ 3 _ 2 8] ], + [ qw[_ _ 9 3 _ _ _ 7 4] ], + [ qw[_ 4 _ _ 5 _ _ 3 6] ], + [ qw[7 _ 3 _ 1 8 _ _ _] ] ); + +my $ri; +my @rowCandidates = (); +my @canvas = map { [ @$_ ] } @P; # copy +say STDERR "Input:"; +say STDERR ("[@$_]") for @canvas; + +for ( $ri = 0; 0 <= $ri < 9; ) { + # $r will be increase or decreased + my $good = 1; + if ( defined $rowCandidates[$ri] ) { # we get here when solving + # lower case ($r+1) was + # not successful + tryNextCandidate( $rowCandidates[$ri] ) + or $good = 0; + } + else { + $rowCandidates[$ri] = newRowCandi( \@canvas, $ri ); + } + + if ( $good and + isAllFilledRow( $rowCandidates[$ri] ) ) { + my $snp = getRefRowSnapshot( \@P, $rowCandidates[$ri] ); + if ($d) { + say "[$ri] current snapshot: @$snp"; + } + # all good so far + @canvas[$ri++] = $snp; # paint and go next row + } + else { + if ($d) { + say "[$ri] no more useful candidates"; + } + $rowCandidates[$ri] = undef; # no more useuful candiates + if (defined $rowCandidates[$ri-1]) { # go previous row + if ($d) { + say "[$ri] going to previous row"; + } + --$ri; + $canvas[$ri] = $P[$ri]; + next; + } + } +} + +if ($ri < 9) { + say "Failed!!!"; + exit 1; +} + +say STDERR "\nOutput:"; +say("[@$_]") for @canvas; diff --git a/challenge-086/jeongoon/raku/ch-1.raku b/challenge-086/jeongoon/raku/ch-1.raku new file mode 100644 index 0000000000..b8e38cb60d --- /dev/null +++ b/challenge-086/jeongoon/raku/ch-1.raku @@ -0,0 +1,18 @@ +#!/usr/bin/env raku + +# test with: +# raku ch-1.raku 7 1 5 2 9 7 # first one is $A + +unit sub MAIN (Int \A, *@N where { .all ~~ Int and .elems > 1 } ); + +my @n = @N.sort; +loop ( my $i = 1; $i < @n.elems; ) { + given (@n[$i]- @n[0]) <=> A { + when Less { ++$i } + when More { shift @n; $i = 1 } + default { say "1 as @n[$i] - @n[0] = {A}"; exit 0 } + } + } + +"0".say; +exit 1; diff --git a/challenge-086/jeongoon/raku/ch-2.raku b/challenge-086/jeongoon/raku/ch-2.raku new file mode 100644 index 0000000000..ccb3f4778c --- /dev/null +++ b/challenge-086/jeongoon/raku/ch-2.raku @@ -0,0 +1,213 @@ +#!/usr/bin/env raku + +# test with: +# raku ch-2.raku --debug=False # otherwise it will show debug output as well. +# example is built-in this case for (maybe) easier review + +# note: this is a non-recursive implementaion +# entry point is localted in MAIN() + +our $d is export; + +class row-candidates { + has ( Hash $!cnd, Int $!r ); # candidates, row number + has Set ( $!nar, @!nac, @!naa ); # N/A(na) number in (r)ow, (c)olumn, + # and (a)rea + has Array ( $.base, # base for all rows + $!drf, # draft for current row only + $!slt, # slots (where we need to fill up) + $!cur, ); # current values in slots + + submethod BUILD (:$r, :$base where { 0 <= $r < 9 }) { + $!r = $r; + if $d { + say "base matrix for row[$r]:"; + .say for $base.Array + } + + $!base = $base.clone; # copy whole matrix. + my \ro = $!base[$!r]>>.Str; # : orginally IntStr, + # which makes Set or SetHash compare + # with Set of Int + # please also refer NOTE1. + # IntStr is sometimes very annoying :( + + my $rgr = do given $!r div 3 { 3* $_ ..^ 3* $_.succ }; # rows in the + # same area + + # generate unavailable number for row, column*s* area*s*) + $!nar = ro.Set; + for ^9 { @!nac[$_] = $!base[*;$_]>>.Str.Set } + for ^3 { + my $rgc = (3* $_) ..^ (3* $_.succ); + @!naa[$_] = $!base[$rgr[*];$rgc[*]]>>.Str.Set; # [*] is must!!! + #@!naa[$_].raku.say; + } + # copy draft from base + $!drf = ro.clone.Array; + $!slt = $!drf.grep({$_ eq '_'}, :k).Array; # register slots as idx + $!cur = (Nil xx $!slt).Array; # prepare spaces + + # and fill up the slots with available numbers for the first time + self.fill-slots; + } + + method fill-slots { + # NOTE1 $!nar stored as .Str so (1..9) must be all .Str + my $avn = (('1'..'9') ∖ $!nar).SetHash; # available numbers in row + my $avn0 = $avn; # backup + + # find the the column number where we start to fill up + # (where no current value is set at rightmost) or // zero + loop ( my $si = ($!cur.first({.defined}, :end, :k) andthen .succ) // 0; + $si < $!slt.elems; ) { + my $c = $!slt[$si]; + my $an = $c div 3; # area number ( 0 | 1 | 2 ) + my $avn1 = ( [∖] $avn, # (+) available numbers in row + $!cur.grep({.defined}),# (-) remove number used one + @!naa[$an], # (-) numbers used in area + @!nac[$c], # (-) numbers used in column + ).SetHash; + if $d { + say "[$!r;$c] si: $si, c: $c; area num: $an"; + say "[$!r:$c] avn: $avn, naa: @!naa[$an], nac: @!nac[$c]"; + say "[$!r;$c]:{self.snapshot(:force)}: "~ + "cur => {$!cur.map({.defined??$_!!'?'})} avn' => $avn1"; + } + + if $avn1.elems.so { + my $n = $avn1.grab(1); # note: returned as Seq + $!cur[$si] = $n[0]; # -> so take first elem + $!cnd{$c} = $avn1.clone # update candidates + if $avn1.elems.so; + $avn ∖= $n; # reduce avaiable num + ++$si; + } + else { + my $i; + if $!cnd andthen .elems.not # no more candis: failed + or ( $i = self!forward_ ) + !~~ any(Str,Int) { # forward_ will return index + # or Nil when failed to forward_ + Nil.return; + } + + $si = 1 + $i; + # reset available numbers + $avn = $avn0; + } + } + if $d { + say "[$!r] all filled up:"; + say self.snapshot; + if $!cnd andthen .elems.so { + say "... still have candiates: {$!cnd.raku}"; + } + else { + say "... but this is last case of row $!r"; + } + } + True # succeed to fill up + } + + method snapshot (Bool :$force = False) { + my $dup = $!drf.clone; + if $force.not and + $!cur.grep({.defined}).elems != $!slt.elems { + Nil.return; + } + else { + $dup[|$!slt] = $!cur.map({$_//'?'}).Array; + } + $dup + } + + # forward_: try to set up next possible case + method !forward_ { + + # find the slot has candidates at rightmost + with $!cnd andthen .sort.tail { + # .key: column num; .value: candidates(SetHash) + my $n = .value.grab(1); # grab a candidate + my $i = $!slt.first(.key, :k); + my $o = $!cur[$i]; + $!cur[$i] = $n[0]; # put into current value + $!cur[$i.succ ..*] = Nil,Nil...*; # undefine values + $!cnd{.key}:delete if .value.elems.not; # remove empty info + say "[$!r;{.key}] change $o to $n"~ + " and rest candidates: {$!cnd.raku}" if $d; + + $i.return # return changed index + # in $!cur + } + Nil + } + + method forward { + self!forward_ + andthen { + self.fill-slots. + return # repect the return value from fill-slots() + } + Nil + } +} + +sub MAIN ( Bool :$debug = True ) { + $d = $debug; + my @s = + #0 1 2 3 4 5 6 7 8 + <_ _ _ 2 6 _ 7 _ 1>, + <6 8 _ _ 7 _ _ 9 _>, + <1 9 _ _ _ 4 5 _ _>, + <8 2 _ 1 _ _ _ 4 _>, + <_ _ 4 6 _ 2 9 _ _>, + <_ 5 _ _ _ 3 _ 2 8>, + <_ _ 9 3 _ _ _ 7 4>, + <_ 4 _ _ 5 _ _ 3 6>, + <7 _ 3 _ 1 8 _ _ _>; + + my Int $r; + my @canvas = @s.Array; # .Array also kind of clone + my @rc; + + ################# + ## entry point ## + ################# + loop ( $r = 0; 0 <= $r < 9; ) { + # note: $r can be increased or decreased + if @rc[$r].defined { + # already exists: we get here when lower case is failed + # so try next case at $r + @rc[$r].forward orelse { + # go higher if failed + @rc[$r] = Nil; # remove all row candiates + @canvas = (@rc[--$r] andthen .base.Array) // @s.Array; + next; + } + } + else { + @rc[$r] = row-candidates.new( :$r, + :base(@canvas.clone)); + } + + if my $snp = @rc[$r].snapshot { # possible so far + @canvas[$r] = $snp; + ++$r; # going next row + } + else { + # there is no more alternative case for current row + # go higher row and try next candidate if any + @rc[$r] = Nil; + @canvas = ( @rc[--$r] andthen .base + orelse Nil ); # when $r < 0 + } + } + if $r < 9 { + say "Not Possible"; + exit 1; + } + + say "all good:" if $d; + .say for @canvas; +} |