diff options
| -rw-r--r-- | challenge-077/jeongoon/haskell/ch-2.hs | 3 | ||||
| -rw-r--r-- | challenge-077/jeongoon/perl/ch-1.pl | 8 | ||||
| -rw-r--r-- | challenge-077/jeongoon/raku/ch-1.raku | 131 | ||||
| -rw-r--r-- | challenge-077/jeongoon/raku/ch-2.raku | 41 |
4 files changed, 180 insertions, 3 deletions
diff --git a/challenge-077/jeongoon/haskell/ch-2.hs b/challenge-077/jeongoon/haskell/ch-2.hs index 94ba2ded42..953512a198 100644 --- a/challenge-077/jeongoon/haskell/ch-2.hs +++ b/challenge-077/jeongoon/haskell/ch-2.hs @@ -18,7 +18,8 @@ getMatrixFromStdin = getContents >>= matrixLines >>= return . map parseMatrixLine >>= return . map (map (\x -> case toUpper( x!!0 ) of 'O' -> 1 - 'X' -> 0 )) -- convert into integer + 'X' -> 0 + _ -> 1)) -- convert into integer >>= return . filterEmptyRow where parseMatrixLine = filter (not.isPrefixOf " "). diff --git a/challenge-077/jeongoon/perl/ch-1.pl b/challenge-077/jeongoon/perl/ch-1.pl index c5eb2a3eab..edd812c4d5 100644 --- a/challenge-077/jeongoon/perl/ch-1.pl +++ b/challenge-077/jeongoon/perl/ch-1.pl @@ -44,6 +44,11 @@ so I concluded that chaging the fibonacci number into two lower fibonacci numbers (right next to the current) until not overlapping is the only way to make sub cases. +the sequence definitely looks like + + a b c -> a b _ (d e) -> a b _ (d _ (f g)) -> a b _ d _ f _ h i -> ... + cmp: a b c -> a b c d e -> a b c d e f g a b c d e f g h i -> ... + =cut use strict; use warnings; @@ -181,7 +186,7 @@ sub productRevFibCombination ($$) { } sub minRevFibSumCombination ($$); -sub minRevFibSumCombination ($$) { # found a case tally the target sum. +sub minRevFibSumCombination ($$) { # find a case tally the target sum. my ( $targetSum, $allRevFibRef ) = @_; #my @allRevFib = grep { $_ <= $targetSum } @{$allRevFibRef}; my @allRevFib = @{$allRevFibRef}; # assuming it's already sieved. @@ -195,7 +200,6 @@ sub minRevFibSumCombination ($$) { # found a case tally the target sum. $majorFib == $targetSum and return ($majorFib); } - my @rest = minRevFibSumCombination( ($targetSum-$majorFib), \@allRevFib ); ::dprint "[DBG] rest for $majorFib: @rest\n"; return ( @rest > 0 ? ( $majorFib, @rest ) : () ) diff --git a/challenge-077/jeongoon/raku/ch-1.raku b/challenge-077/jeongoon/raku/ch-1.raku new file mode 100644 index 0000000000..446091e9b8 --- /dev/null +++ b/challenge-077/jeongoon/raku/ch-1.raku @@ -0,0 +1,131 @@ +#!/usr/bin/env raku +# -*- Mode: Raku; indent-tabs-mode: nil; coding: utf-8 -*- +# vim: set et ts=4 sw=4: + +# tested with: +# raku ch-1.raku 9999 + +use v6.d; + +our $d is export = False; + +sub test { say $d } + +multi sub fibs ( 1 ) { (1) } +multi sub fibs ( 2 ) { (1,2) } +multi sub fibs ( Int $limit ) { + my @fibs = 1,2; + while ( (my $new-fib = ( @fibs[*-2] + @fibs[*-1] )) <= $limit ) { + push @fibs, $new-fib; + } + @fibs +} + +sub rfibs ( $limit ) { fibs($limit).reverse } # r: reverse +say "reverse fibs(100) test: {rfibs(100)}" if $d; + + +class CombiFibSum { + has ( @!rfibs, $.target-sum ); + method rfibs { + ( @!rfibs.elems == 0 or @!rfibs[*-1] < $!target-sum ) + and @!rfibs = rfibs( $!target-sum ); + + @!rfibs + } + + # return the all possible ways a fib number can be expressed + # which includes the fib number itself + # ex) f(55)-> [55], [34, 21], [34, 13, 8], [34, 13, 5, 3], [34, 13, 5, 2, 1] + method a-fib-subcases( $a-fib, @fibs-not-to-use ) { + my $beg = Nil; + my @all-cases; + for 0 .. self.rfibs.end -> $i { # call .rfibs to ensure to get @!rfibs + @!rfibs[$i] == $a-fib and ( $beg = $i+1, last ); + } + $beg.defined or Empty.return; # not a fibonacci num. + @all-cases.push( ( $a-fib,) ); # note: comma required + + loop ( my $fi = $beg; $fi+1 < @!rfibs.elems; $fi+=2 ) { + my @last-fibs-except-last-fib = @all-cases[*-1][1..*-1]; + my @two-new-fibs = @!rfibs[$fi, $fi+1]; + # don't go further on purpose of my solution + any(@two-new-fibs) ∈ @fibs-not-to-use and last; + @all-cases.push( ( |@last-fibs-except-last-fib, |@two-new-fibs ) ); + } + if $d { + print "sub cases of fib({$a-fib}): "; + say @all-cases.map( *.Array.raku ).join(" | "); + }; + @all-cases + } + + method all-fibs-subcases( @rfibs ) { + my @ban-list = @rfibs.clone; + my $bi = 0; # for ban list indexing + + my @all-fibs-subcases; + @rfibs.map( + -> $f { + @all-fibs-subcases.push( + self.a-fib-subcases( $f, @ban-list[$bi++ .. *]) ); + } ); + + dd @all-fibs-subcases if $d; + @all-fibs-subcases + } + + # find a case tally the target sum + multi method min-combi-fib-sum ( $tsum = $!target-sum, + @given-rfibs is copy = self.rfibs.clone ) { + my ( $major-fib, $skip ) = Nil, 0; + through-rfibs: + for ( 0 .. @given-rfibs.end ) -> $fi { + + given @given-rfibs[$fi] { + when ( * > $tsum ) { next through-rfibs } + when ( $tsum ) { .return } + $major-fib = $_; + } + + $skip = $fi+1; + last; + } + + $major-fib.defined or Empty.return; + my @rest = samewith( $tsum-$major-fib, @given-rfibs[$skip..*] ); + @rest.elems > 0 ?? ( $major-fib, |@rest ) !! Empty; + } + + method all-combi-sum { + my @a-combi = self.min-combi-fib-sum; + @a-combi.elems == 0 and ().return; + say "found a combination of sum({$!target-sum}):" + ~ " {@a-combi.Array.raku}" if $d; + + my @all-fibs-subcases = self.all-fibs-subcases( @a-combi ); + ( [X] @all-fibs-subcases ).map( *.flat ); + } +} + +sub MAIN ( + UInt:D \S, #= target fibonacci sum + Bool :$debug = False #= show verbose message +) { + $d = $debug; + my CombiFibSum $F .= new( :target-sum(S) ); + my @all-combi = $F.all-combi-sum; + + say "Input: " ~ S; + say "Output:"; + + if ( @all-combi.elems == 0 ) { + say "0"; # I couldn't find this case. + } else { + @all-combi.map( + -> @a-combi { + say @a-combi».List.flat.join(" + ") ~ " = " ~ S; + } ); + say "Total {@all-combi.elems} case(s) found."; + } +} diff --git a/challenge-077/jeongoon/raku/ch-2.raku b/challenge-077/jeongoon/raku/ch-2.raku new file mode 100644 index 0000000000..a78e0d2d5b --- /dev/null +++ b/challenge-077/jeongoon/raku/ch-2.raku @@ -0,0 +1,41 @@ +#!/usr/bin/env raku +# -*- Mode: Raku; indent-tabs-mode: nil; coding: utf-8 -*- +# vim: set et ts=4 sw=4: + +use v6.d; + +sub USAGE { + say "Usage:"; + say 'echo -e "[O O X][X X O][X O O]" | raku ch-2.raku'; + say "# or input ending with EOF (Ctrl-D or Ctrl-Z .. or ...??? )"; +} + +unit sub MAIN; +my @matrix = +$*IN.lines. # read lines from STDIN +map( |*.split( /"]" \s* "\n"* | "\n"/ ) ). # split rows by newline or `]' +map( -> $l { next if $l ~~ ""; # skip empty line + S:g/ '[' || \s+ //.comb.cache with $l } ); # remove unused chars. + +my $cnt = 0; +say "Input: (Ctrl-D or Ctrl-Z to finish to input.)"; + +with @matrix { + say "{.Array.raku}" for $_; + say ""; + for 0 .. .end -> $r { + for 0.. .[0].end -> $c { + next if .[$r][$c] ne 'X'; + if 1 == (-1..1).map( + -> $dy + { | (-1..1).map( + -> $dx + { .[$r+$dy]:exists + and .[$r+$dy][$c+$dx]:exists + ??.[$r+$dy][$c+$dx] !!'O' })}). + grep('X').elems { + say "{++$cnt}: Lonely X at Row {$r+1}, Col {$c+1}"; + } + } + } +} |