From 26244318594daad841ae5d9a5e32ca27861e1622 Mon Sep 17 00:00:00 2001 From: Myoungjin JEON Date: Fri, 6 Nov 2020 21:31:58 +1100 Subject: [ch-085/jeongoon] Perl, Raku, Go, Haskell Soultion added. --- challenge-085/jeongoon/go/ch-1.go | 157 +++++++++++++++++++++ challenge-085/jeongoon/go/ch-2.go | 61 ++++++++ challenge-085/jeongoon/haskell/Combinations.hs | 25 ++++ challenge-085/jeongoon/haskell/ch-1.hs | 42 ++++++ challenge-085/jeongoon/haskell/ch-2.hs | 44 ++++++ .../jeongoon/perl/LazyCombinationsIndex.pm | 80 +++++++++++ challenge-085/jeongoon/perl/ch-1.pl | 36 +++++ challenge-085/jeongoon/perl/ch-1a.pl | 40 ++++++ challenge-085/jeongoon/perl/ch-2.pl | 94 ++++++++++++ challenge-085/jeongoon/raku/ch-1.raku | 40 ++++++ challenge-085/jeongoon/raku/ch-2.raku | 60 ++++++++ 11 files changed, 679 insertions(+) create mode 100644 challenge-085/jeongoon/go/ch-1.go create mode 100644 challenge-085/jeongoon/go/ch-2.go create mode 100644 challenge-085/jeongoon/haskell/Combinations.hs create mode 100644 challenge-085/jeongoon/haskell/ch-1.hs create mode 100644 challenge-085/jeongoon/haskell/ch-2.hs create mode 100644 challenge-085/jeongoon/perl/LazyCombinationsIndex.pm create mode 100644 challenge-085/jeongoon/perl/ch-1.pl create mode 100644 challenge-085/jeongoon/perl/ch-1a.pl create mode 100644 challenge-085/jeongoon/perl/ch-2.pl create mode 100644 challenge-085/jeongoon/raku/ch-1.raku create mode 100644 challenge-085/jeongoon/raku/ch-2.raku diff --git a/challenge-085/jeongoon/go/ch-1.go b/challenge-085/jeongoon/go/ch-1.go new file mode 100644 index 0000000000..b64fcb186e --- /dev/null +++ b/challenge-085/jeongoon/go/ch-1.go @@ -0,0 +1,157 @@ +package main + +/* tested with: + * go run ch-1.go 1.1 0.8 0.4 0.2 2.3 1.1 0.4 0.9 4.3 + * 1 as 1.0 < (0.200 + 0.400 + 0.800) < 2.0 + */ + +import ( + "os" + "fmt" + "strconv" + "strings" + "sort" +) + +func usage () { + fmt.Println( "Usage: go run ch-1.go ..." ); +} + +type combiIter struct { + dlen int // data length + nsel int // number of selection + ncsr int // next cursor + room []int + pos []int +} + +// adapted from challenge-083/jeongoon/ch-2.go +// this combinations implentation keep the status into combiIter +// and give next combination when calling nextIndices() +func lazyCombinationsIndex( M int, N int ) *combiIter { + iter := &combiIter{ + M, + N, + N-1, + make([]int, N), + make([]int, N), + } + + initRoomSize := M - N + + for i := 0; i < (N-1); i++ { + iter.room[i] = initRoomSize + iter.pos[i] = i + } + // note: we'll increase when nextIdices() called for the first time. + iter.room[N-1] = initRoomSize + 1 + iter.pos[N-1] = N - 2; + + return iter +} + +func (ci *combiIter) nextIndices() []int { + var new_case []int + + if ci.room[ci.ncsr] > 0 { + ci.room[ci.ncsr]-- + ci.pos[ci.ncsr]++ + new_case = make([]int, ci.nsel) + copy(new_case, ci.pos) + return new_case + } else { + cursor_moved := false + for i := ci.ncsr; i > 0; i-- { + if ci.room[i-1] > 0 { + ci.ncsr = i - 1; + cursor_moved = true + break + } + } + if cursor_moved { + new_room := ci.room[ci.ncsr] - 1 + base_pos := ci.pos[ci.ncsr]; + for p, i := 1, ci.ncsr; i < ci.nsel; i++ { + ci.room[i] = new_room + ci.pos[i] = base_pos + p + p++ + } + new_case = make([]int, ci.nsel) + copy(new_case, ci.pos) + ci.ncsr = ci.nsel - 1 + } else { + new_case = []int{} + } + } + return new_case +} + +func parseStringsToFloat64s( args []string ) []float64 { + var result []float64 + for i, maybe_f := range args { + f, err := strconv.ParseFloat(maybe_f, 64) + if err == nil { + result = append(result, f) + } else { + fmt.Fprintf(os.Stderr, + "wrong float value: [%d] [%s]\n", i, maybe_f) + } + } + return result +} + +func tidyList( flist []float64 ) []float64 { + var result []float64 + sorted := flist // copy + sort.Float64s(sorted) // sort (in place) + + // only numbers < 2.0 + for _, f := range(sorted) { + if f < 2.0 { + result = append(result, f) + } + } + return result +} + +func main() { + if len(os.Args[1:]) < 3 { + usage(); + os.Exit(1); + } + + flist_ := parseStringsToFloat64s(os.Args[1:]) + flist := tidyList( flist_ ) + + it := lazyCombinationsIndex(len(flist), 3) + var foundTripletStrs []string + for { + tripletIndices := it.nextIndices(); + if len(tripletIndices) == 0 { + break + } + + sum := 0.0; + for _, idx := range( tripletIndices ) { + sum += flist[idx] + } + if sum > 1.0 && sum < 2.0 { + for _, idx := range( tripletIndices ) { + fStr := strconv. + FormatFloat(flist[idx], 'f', 3, 64) + foundTripletStrs = append(foundTripletStrs,fStr) + } + break + } + } + + if len(foundTripletStrs) == 0 { + fmt.Println("0"); + os.Exit(2); + } else { + fmt.Println("1 as 1.0 < (" + + strings.Join(foundTripletStrs, " + ") + + ") < 2.0") + os.Exit(0); + } +} diff --git a/challenge-085/jeongoon/go/ch-2.go b/challenge-085/jeongoon/go/ch-2.go new file mode 100644 index 0000000000..86684c47f8 --- /dev/null +++ b/challenge-085/jeongoon/go/ch-2.go @@ -0,0 +1,61 @@ +package main + +import ( + "os" + "fmt" + "math" + "strconv" +) + +type MaybeNat string + +func (str MaybeNat) Nat() Nat { + n, err := strconv.Atoi(string(str)) + if err == nil { + return(Nat(n)) + } else { + return(Nat(0)) + } +} + +func (str MaybeNat) isNatural() bool { + return(str.Nat() > 0) +} + +type Nat int64 +func (n Nat) String() string { + return fmt.Sprintf("%d", n) +} + +func maxPowerFactor (n Nat) Nat { + return Nat(math.Floor(math.Sqrt(float64(n)))) +} + +func usage () { + fmt.Println("Usage: go run ch-2.go " ) +} + +func main() { + if len(os.Args[1:]) != 1 { + usage() + os.Exit(1) + } + + if MaybeNat(os.Args[1]).isNatural() == false { + usage() + os.Exit(2) + } + + n := MaybeNat(os.Args[1]).Nat() + + for f := maxPowerFactor(n); f > 1; f-- { + pow := math.Log( float64(n) ) / math.Log( float64(f) ) + if math.Floor(pow) == pow { + fmt.Println("1 as " + f.String() + + "^" + Nat(pow).String() + " = " + n.String()) + os.Exit(0) + } + } + fmt.Println("0") + os.Exit(3) +} diff --git a/challenge-085/jeongoon/haskell/Combinations.hs b/challenge-085/jeongoon/haskell/Combinations.hs new file mode 100644 index 0000000000..3e2a2d8a30 --- /dev/null +++ b/challenge-085/jeongoon/haskell/Combinations.hs @@ -0,0 +1,25 @@ +{- Copyright (c) 2020 JEON Myoungjin -} + +module Combinations + ( combinations + ) where + +combinations :: [a] -> Int -> [[a]] +combinations [] _ = [] +combinations (m:ms) 1 = [m] : (combinations ms 1) +combinations [_] 2 = [] +combinations [e,f] 2 = [[e,f]] +combinations (m:ms) 2 = sequence [[m], ms] ++ (combinations ms 2) +combinations mls n = + case totalLen `compare` n of + LT -> [] + EQ -> [mls] + _ -> [ let leaders = map (fst) tups + in leaders ++ followers | + tups <- combinations (zip mls [0 .. room]) n', + let skipCount = ((snd.last) tups) + 1, + followers <- (combinations (drop skipCount mls) 2) ] + where + totalLen = length mls + room = totalLen - 2 + n' = n - 2 diff --git a/challenge-085/jeongoon/haskell/ch-1.hs b/challenge-085/jeongoon/haskell/ch-1.hs new file mode 100644 index 0000000000..334cf81bda --- /dev/null +++ b/challenge-085/jeongoon/haskell/ch-1.hs @@ -0,0 +1,42 @@ +import System.Environment +import System.Exit +import Data.Char (isNumber) +import Data.Maybe (catMaybes) +import Data.List (find, intercalate) +import Combinations (combinations) + +{- tested with: +runhaskell ch-1.hs 0.8 0.4 1.2 0.9 1.7 0.2 +1 as 1.0 < (0.8 + 0.4 + 0.2) < 2.0 +-} + +answerTripletSum :: [Float] -> Maybe [Float] +answerTripletSum fs + | length fs < 3 = Nothing + | otherwise = findTriplet + where + findTriplet = + find (\tr -> + let trsum = sum tr + in 1.0 < trsum && trsum < 2.0) (combinations fs 3) + +showAnswerDetail_ :: Maybe [Float] -> String +showAnswerDetail_ fs' = + case fs' of + Nothing -> "0" + Just fs -> "1 as 1.0 < (" ++ ((intercalate " + " . + map show) fs) ++ ") < 2.0" + +main = do + (catMaybes.map (\fStr -> + if ((all (\c -> (isNumber c) || c == '.') fStr) + && length(filter (=='.') fStr) <= 1) + then Just(read fStr :: Float) + else Nothing )) `fmap` getArgs + >>= (\rnums -> + if length rnums < 1 then + die "Usage: runhaskell ch-2.hs ..." + else + (putStrLn . + showAnswerDetail_ . + answerTripletSum ) rnums ) diff --git a/challenge-085/jeongoon/haskell/ch-2.hs b/challenge-085/jeongoon/haskell/ch-2.hs new file mode 100644 index 0000000000..5ff624a2a2 --- /dev/null +++ b/challenge-085/jeongoon/haskell/ch-2.hs @@ -0,0 +1,44 @@ +import System.Environment +import System.Exit +import Data.Ratio (denominator) +import Data.Maybe (catMaybes) + +{- tested with: +runhaskell ch-2.hs 144 +1 as 12^2 = 144 +runhaskell ch-2.hs 107 +0 +-} + +maxFactor :: (Integral c, Integral a) => a -> c +maxFactor n = (floor . sqrt . fromIntegral) n + +findPowerOfTwoIntegers :: Integer -> Maybe (Integer, Integer) +findPowerOfTwoIntegers n = + case (take 1 abPairs) of + [] -> Nothing + [(f, p)] -> Just (f, p) + where abPairs = catMaybes [ if d == 1 then Just (f, (floor pow)) + else Nothing + | f <- [maxFac,(maxFac-1)..2], + let pow = logn'/(log' f) + d = (denominator . toRational) pow ] + + maxFac = maxFactor n + logn' = log' n + log' :: (Floating a, Integral c) => c -> a + log' = (log . fromIntegral) + +main = do + args <- getArgs; + if length args /= 1 + then die "Usage: runhaskell ch-2.hs " + else + let istr = args !! 0 + i = read istr :: Integer + ans = findPowerOfTwoIntegers i + in case ans of + Nothing -> putStrLn "0" + Just (a, b) -> putStrLn $ + "1 as " ++ (show a) ++ "^" ++ (show b) + ++ " = " ++ istr diff --git a/challenge-085/jeongoon/perl/LazyCombinationsIndex.pm b/challenge-085/jeongoon/perl/LazyCombinationsIndex.pm new file mode 100644 index 0000000000..fb356f17f6 --- /dev/null +++ b/challenge-085/jeongoon/perl/LazyCombinationsIndex.pm @@ -0,0 +1,80 @@ +# -*- Mode: cperl; cperl-indent-level:4; tab-width: 8; indent-tabs-mode: nil -*- +# Copyright (c) 2013,2020 JEON Myoungjin + +package LazyCombinationsIndex; +use strict; use warnings; + +use version 0.77; our $VERSION = version->declare( 'v0.1' ); + +use parent 'Exporter'; +our @EXPORT_OK = qw(combinationsIndexIter); + +sub DLEN () { 0 } # Data Lengh +sub NSEL () { 1 } # Number of selection +sub ROOM () { 2 } +sub POSI () { 3 } +sub NCSR () { 4 } # Next Cursor + +sub combinationsIndexIter { + my $class = __PACKAGE__; + my ( $C, $S ) = @_; # (C)hoice (S)slection + + my $self = []; + # minimum sanity check + if ( $C < $S ) { + warn "unable to choose $S from given selection of $C"; + bless $self, $class; + } + + $self = [ $C, # DLEN + $S, # NSEL + [ ( $C-$S ) x ($S-1), + $C-$S+1 ], # ROOM + [ 0 .. ($S-2), ($S-2) ], # POSI + ($S - 1) ]; # NCSR + + bless $self, $class; +} + +sub nextIndices { + my $s = shift; + my $csr = $$s[NCSR]; + my $S = $$s[NSEL]; + + if ( $s->[ROOM][$csr] > 0 ) { + # current csr can move to right so just do it. + ++( $s->[POSI][$csr] ); + --( $s->[ROOM][$csr] ); # room decreased of course + return [ @{$$s[POSI]} ]; # return copy of the case + } + else { + # no more room to move + # so find the next cursor to move + my $found = 0; + for ( my $i = $csr; $i > 0; --$i ) { + if ( $s->[ROOM][ $i-1 ] > 0 ) { + $csr = $i-1; + $found = 1; + last; + } + } + + if ( $found ) { + my $base_pos = $s->[POSI][$csr]; + @{$$s[POSI]}[$csr .. ($S-1)] + = map { $base_pos + $_ } 1 .. ($S-$csr); + @{$$s[ROOM]}[$csr .. ($S-1)] + = ( $s->[ROOM][$csr] - 1 ) x ($S-$csr); + + # next cursor to move will be ($S-1) + # or even if it is not next loop will find anohter + $$s[NCSR] = $S-1; + + # return copy of the case + return [ @{$$s[POSI]} ]; + } + } + return (); # return undef if there is no more cases +} + +!!"^^"; diff --git a/challenge-085/jeongoon/perl/ch-1.pl b/challenge-085/jeongoon/perl/ch-1.pl new file mode 100644 index 0000000000..3af0dec46a --- /dev/null +++ b/challenge-085/jeongoon/perl/ch-1.pl @@ -0,0 +1,36 @@ +#!/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; # for syntax: a < x < b + +use Algorithm::Combinatorics qw(combinations); +use List::Util qw(sum); + +sub tidyList(@) { + sort # as we will try from lowest sum of a group + grep { $_ < 2.0 } # as x >= 2.0 is not useful here + @_; + +} + +@ARGV > 2 or die "Need at least 3 real numbers!"; + +my @list = tidyList @ARGV; +my $it = combinations( \@list, 3 ); + +{ + local $" = " + "; + # take combination of triplet one by one + while ( my $triplet = $it->next() ) { + my $ts = sum @$triplet; + if ( 1.0 < $ts < 2.0 ) { + say "1.0 < ( @$triplet == $ts ) < 2.0"; + exit 0; + } + } +} + +say "0"; +exit 1; diff --git a/challenge-085/jeongoon/perl/ch-1a.pl b/challenge-085/jeongoon/perl/ch-1a.pl new file mode 100644 index 0000000000..3e6d2cc8b4 --- /dev/null +++ b/challenge-085/jeongoon/perl/ch-1a.pl @@ -0,0 +1,40 @@ +#!/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; # for syntax: a < x < b + +use FindBin; +use lib ( $FindBin::Bin ); +use LazyCombinationsIndex qw(combinationsIndexIter); + +use List::Util qw(sum); + +sub tidyList(@) { + sort # as we will try from lowest sum of a group + grep { $_ < 2.0 } # as x >= 2.0 is not useful here + @_; + +} + +scalar @ARGV > 2 or die "Need at least 3 real numbers!"; + +my @list = tidyList @ARGV; +my $it = combinationsIndexIter( scalar @list, 3 ); + +{ + local $" = " + "; + # take combination of triplet one by one + while ( my $triplet_idx = $it->nextIndices ) { + my @triplet = @list[ @$triplet_idx ]; + my $ts = sum @triplet; + if ( 1.0 < $ts < 2.0 ) { + say "1.0 < ( @triplet == $ts ) < 2.0"; + exit 0; + } + } +} + +say "0"; +exit 1; diff --git a/challenge-085/jeongoon/perl/ch-2.pl b/challenge-085/jeongoon/perl/ch-2.pl new file mode 100644 index 0000000000..a912833bb6 --- /dev/null +++ b/challenge-085/jeongoon/perl/ch-2.pl @@ -0,0 +1,94 @@ +#!/usr/bin/env perl +# -*- Mode: cperl; cperl-indent-level:4 tab-width: 8; indent-tabs-mode: nil -*- +# -*- coding: utf-8 -*- + +use utf8; +use strict; use warnings; +use v5.26; + +BEGIN { + binmode( STDERR, ':utf8' ); + binmode( STDOUT, ':utf8' ); +} + +our @POW_UTF8 = qw{⁰ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹}; +sub pow_utf8__ ($) { # does not check whether integer value or not + join "", @POW_UTF8[ split "", $_[0] ] +} + +sub maxFactor ($) { # find k where k² <= $_[0] + int # -> as an iteger value + sqrt $_[0] +} + +sub findPowerByComparing_ ($) { # note: do not check when N == 1 + my $N = shift; + my $fac = maxFactor $N; + + MAYBE_NEXT_FACTOR: + { + my $k = $fac; + my $pow = 1; + { + $k = $k * $fac; # produce k², k³ ... + ++$pow; + if ( $k == $N ) { + return [ $fac, $pow ]; + } + elsif ( $k < $N + and ( $N % $k == 0 ) # but we don't need to go further + # if $k is not a modular + ) { + redo; + } + } + redo if ( --$fac > 1 ); + } + + # could not find any integer where a to the power of b = N + return undef; +} + +sub findPowerByLog_ ($) { + my $N = shift; + my $fac = maxFactor $N; + + MAYBE_NEXT_FACTOR: + { + { + my $pow = log($N) / log($fac); + if ( int $pow == $pow ) { + return [ $fac, $pow ]; + } + } + redo if ( --$fac > 1 ); + } + + # could not find any integer where a to the power of b = N + return undef; +} + +package main; + + +my @ARGV_ = grep { !/^--*l(og)*/ } @ARGV; +my $finder = + ( @ARGV_ == @ARGV ) ? \&findPowerByComparing_ + : \&findPowerByLog_; + +my $N = shift @ARGV_; + +( defined $N and $N > 0 ) or die "Invalid number"; + +if ( $N == 1 ) { + say "1 as 1²"; + exit 0; +} + +else { + my $fac = maxFactor $N; + my $pair = $finder->( $N ); + defined $pair or say("0"), exit 1; + + say "1 as $N == $$pair[0]" . pow_utf8__( $$pair[1] ); +} diff --git a/challenge-085/jeongoon/raku/ch-1.raku b/challenge-085/jeongoon/raku/ch-1.raku new file mode 100644 index 0000000000..daf1c94de6 --- /dev/null +++ b/challenge-085/jeongoon/raku/ch-1.raku @@ -0,0 +1,40 @@ +#!/usr/bin/env raku + +# test with: +# raku ch-1.raku 0.1 0.2 0.5 2.4 1.2 0.8 +# or +# raku ch-1.raku --alt 0.1 0.2 0.5 2.4 1.2 0.8 + +multi sub MAIN ( *@r where { @r.elems > 0 and + @r.all ~~ Rat and @r.all > 0.0 } ) { + @r. + grep(* < 2.0). + combinations(3). + lazy. + first( 1.0 < *.sum < 2.0 ) + andthen say("1.0 < " + ~ "({join(' + ', $_.List)})" + ~ " < 2.0") + orelse say "0"; +} + +multi sub MAIN ( Bool:D :$alt, *@r where { @r.elems > 0 and + @r.all ~~ Rat and @r.all > 0.0 } ) { + $*ERR.say( "alternative solution using iterator ..." ); + my $triplet-it = @r.sort.combinations(3).lazy.iterator; + + my $found = False; + loop ( my $t := $triplet-it.pull-one; + ($t =:= IterationEnd).not + ; $t := $triplet-it.pull-one ) { + if 1.0 < $t.sum < 2.0 { + $found = True; + say("1.0 < " + ~ "({join(' + ', $t.List)})" + ~ " < 2.0"); + last; + } + } + + say 0 unless $found; +} diff --git a/challenge-085/jeongoon/raku/ch-2.raku b/challenge-085/jeongoon/raku/ch-2.raku new file mode 100644 index 0000000000..f7491fcd9a --- /dev/null +++ b/challenge-085/jeongoon/raku/ch-2.raku @@ -0,0 +1,60 @@ +#!/usr/bin/env raku + +# test with: +# raku ch-2.raku +# raku ch-2.raku --log # find by using log() + +sub largest-factor ( Int \n --> Int ) { n.sqrt.Int } + +sub pow-utf8 ( Int $n ) { + state @pow = <⁰ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹>; + @pow[ $n.comb ].join +} + + + +multi sub MAIN (1) { say "1 as 1²" } + +multi sub MAIN ( Int \N where * > 0 ) { + if N.is-prime { + say "0 as {N} is a prime number."; + } + else { + my $lf = largest-factor(N); + ( $lf ... 2 ). + lazy. + map( + -> $a { + ([\×] ($a,$a ... ∞)). # produce a¹, a², a³ + lazy. # in lazy way + skip(1). # but we don't need first one (a¹) + kv. + map( + -> \β, \κ { + if N == κ { ($a => β + 2) } # as `b' value + elsif N <= κ { last } + else { Empty } + } ).Slip + } ).first + andthen say "1 as {.key}{pow-utf8(.value)}" + orelse say "0" + } +} + +multi sub MAIN ( Int \N where * > 0, Bool:D :$log ) { + $*ERR.say( "alternative solution using log() ..." ); + if N.is-prime { + say "0 as {N} is a prime number."; + } + else { + my $lf = largest-factor(N); + ( $lf ... 2 ). + lazy.map( + { my $pow = log( N, $_ ).Rat( 1e-32 ); + ($_ => $pow.Int) if $pow.denominator == 1; + } + ).first + andthen say "1 as {.key}{pow-utf8(.value)}" + orelse say "0" + } +} -- cgit