aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--challenge-083/jeongoon/go/ch-1.go32
-rw-r--r--challenge-083/jeongoon/go/ch-2.go190
-rw-r--r--challenge-083/jeongoon/perl/CombinationsIndex.pm123
-rw-r--r--challenge-083/jeongoon/perl/ch-1.pl31
-rw-r--r--challenge-083/jeongoon/perl/ch-2.pl79
-rw-r--r--challenge-083/jeongoon/raku/ch-2.raku22
-rw-r--r--challenge-083/jeongoon/raku/ch-2.without-race.raku23
-rw-r--r--challenge-083/jeongoon/raku/ch-2.yet-another-race.raku38
8 files changed, 498 insertions, 40 deletions
diff --git a/challenge-083/jeongoon/go/ch-1.go b/challenge-083/jeongoon/go/ch-1.go
new file mode 100644
index 0000000000..d4f073f3e3
--- /dev/null
+++ b/challenge-083/jeongoon/go/ch-1.go
@@ -0,0 +1,32 @@
+package main
+
+import (
+ "os"
+ "fmt"
+ "strings"
+)
+
+func usage() {
+ fmt.Println( "Usage: go run ch-1.go \"a single string\"" )
+}
+
+func main() {
+ if len(os.Args[1:]) != 1 {
+ usage()
+ os.Exit(1);
+ }
+
+ words := strings.Split( os.Args[1], " " );
+ if len(words) < 3 {
+ fmt.Fprintln( os.Stderr,
+ "words must contain at least three words" )
+ os.Exit(2);
+ }
+
+ middleCharsExceptWhitespace := 0
+ for _, c := range words[ 1 : len(words)-1 ] {
+ middleCharsExceptWhitespace += len(c)
+ }
+
+ fmt.Println( middleCharsExceptWhitespace )
+}
diff --git a/challenge-083/jeongoon/go/ch-2.go b/challenge-083/jeongoon/go/ch-2.go
new file mode 100644
index 0000000000..60433a850f
--- /dev/null
+++ b/challenge-083/jeongoon/go/ch-2.go
@@ -0,0 +1,190 @@
+package main
+
+import (
+ "os"
+ "fmt"
+ "strconv"
+)
+
+func usage() {
+ fmt.Println( "Usage: go run ch-2.go <natural numbers> ..." );
+}
+
+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 int
+func (n Nat) String() string {
+ return fmt.Sprintf("%d", n)
+}
+
+/*
+ * Another my own version of making combinations without recursive call
+ * explanation in perl:
+ * https://github.com/jeongoon/pwc-by-me/blob/master/075/perl/CombinationsIndex.pm
+ * I found that this implementation very fast in Perl,
+ * so it will be the same in golang especially when compiled.
+ */
+
+func combinationsIndex( M int, N int ) [][]int {
+ // M: number of selection ( 0 ... (M-1) )
+ // N: number of choice
+ if M < N {
+ return [][]int{}
+ }
+
+ initRoomSize := M - N
+ room := make([]int, N)
+ pos := make([]int, N)
+ // https://stackoverflow.com/questions/39984957/is-it-possible-to-initialize-slice-with-specific-values
+ for i := range room {
+ room[i] = initRoomSize
+ }
+ for i := range pos {
+ pos[i] = i
+ }
+
+ var combis [][]int
+ new_case := make([]int, N)
+ copy(new_case, pos)
+ combis = append( [][]int{}, new_case )
+
+ cursor := N - 1 // initial: index of last elements in selection
+
+ for {
+ if room[cursor] > 0 {
+ room[cursor]--
+ pos[cursor]++
+ new_case := make([]int, N)
+ copy(new_case, pos)
+ combis = append(combis, new_case)
+ } else {
+ cursor_moved := false
+ for i := cursor; i > 0; i-- {
+ if room[i-1] > 0 {
+ cursor = i-1
+ cursor_moved = true
+ break
+ }
+ }
+ if cursor_moved {
+ new_room := room[cursor] - 1
+ base_pos := pos[cursor];
+ for p, i := 1, cursor; i < N; i++ {
+ room[i] = new_room
+ pos[i] = base_pos + p
+ p++ // p++, i++ not working on for()
+ }
+ new_case := make([]int, N)
+ copy(new_case, pos)
+ combis = append(combis, new_case)
+ cursor = N - 1
+ } else {
+ break
+ }
+ }
+
+ }
+
+ return combis
+}
+
+func main() {
+ if len(os.Args[1:]) < 1 {
+ usage();
+ os.Exit(1);
+ }
+
+ var N []Nat
+ all_good := true
+ debug := false
+
+ for _, str := range os.Args[1:] {
+ if MaybeNat(str).isNatural() {
+ N = append(N, MaybeNat(str).Nat())
+ } else {
+ all_good = false
+ break
+ }
+ }
+
+ if ! all_good {
+ usage();
+ os.Exit(2);
+ }
+
+ lenN := len(N)
+ if lenN == 1 {
+ // already minimum: no need to change
+ fmt.Println( "0" );
+ // but not error
+ os.Exit(0);
+ }
+
+ totalSum := 0
+ maxNum := 0
+ for _, n := range N {
+ totalSum += int(n)
+ if maxNum < int(n) {
+ maxNum = int(n)
+ }
+ }
+
+ minPositiveSum := totalSum
+ minPositiveElems := len(N)
+ for i := 1; i < lenN; i++ {
+ for _, cb := range combinationsIndex(lenN, i) {
+ negativeGroupSum := 0
+ for _, idx := range cb {
+ negativeGroupSum += int(N[idx])
+ }
+
+ diff := totalSum - 2 * negativeGroupSum
+ maybeNewElems := len(cb)
+
+ if debug {
+ fmt.Println( "before: ", diff,
+ " with ", maybeNewElems,
+ " <=> ", minPositiveSum,
+ " with ", minPositiveElems )
+ }
+
+ if diff >= 0 &&
+ minPositiveSum >= diff {
+ if minPositiveSum == diff {
+ if minPositiveElems > maybeNewElems {
+ minPositiveElems = maybeNewElems
+ }
+ } else { // minPositiveElems > diff
+ minPositiveElems = maybeNewElems
+ }
+
+ minPositiveSum = diff
+ }
+
+ if debug {
+ fmt.Println( "after: ", diff,
+ " with ", maybeNewElems,
+ " <=> ", minPositiveSum,
+ " with ", minPositiveElems )
+ }
+
+ if minPositiveSum == 0 && minPositiveElems == 1 {
+ break;
+ }
+ }
+ }
+ fmt.Println( minPositiveElems )
+}
diff --git a/challenge-083/jeongoon/perl/CombinationsIndex.pm b/challenge-083/jeongoon/perl/CombinationsIndex.pm
new file mode 100644
index 0000000000..385c8905cd
--- /dev/null
+++ b/challenge-083/jeongoon/perl/CombinationsIndex.pm
@@ -0,0 +1,123 @@
+# -*- Mode: cperl; cperl-indent-level:4; tab-width: 8; indent-tabs-mode: nil -*-
+# Copyright (c) 2013,2020 JEON Myoungjin <jeongoon@gmail.com>
+
+package CombinationsIndex;
+use strict; use warnings;
+
+use version 0.77; our $VERSION = version->declare( 'v0.3' );
+
+use parent 'Exporter';
+our @EXPORT_OK = qw(combinationsIndex);
+
+=pod
+
+=head1 Basic concept
+
+If we find the combintions when choosing 3 digits from index of 0 .. 4
+which shown below
+
+ 0 1 2 3 4
+ ^1 ^2 ^3 initial selection: index position: ( 0, 1, 2 )
+
+to get next combination we can move ^3 cursor from 2 to 3
+
+ 0 1 2 3 4
+ ^1 ^2 ^3 note: ^3 can move up to 4
+
+as you can see ^3 can only go up to 4, next movement we can imagine is that
+moving ^2 to next one and ^3 is just followed by ^2
+and next movement will be again ^3 to the index 4
+
+ 0 1 2 3 4 => 0 1 2 3 4 => 0 1 2 3 4
+ ^1 ^2 ^3 ^1 ^2 ^3 ^1 ^2 ^3
+
+and last case of combinations will be
+
+ 0 1 2 3 4
+ ^1 ^2 ^3
+
+so I make two arrays to record
+ 1. where each cursor is pointing now,
+ 2. how many rooms left for each cursor to move
+
+and also remember what is the current cursor move next.
+
+so we can also make combinations without recursive routine.
+
+=cut
+
+sub combinationsIndex ( $$ ) {
+ # I changed the order of arguments since v0.3
+ my $M = $_[0]; # choice" 0 .. ($M - 1)
+ my $N = $_[1]; # number of selection
+
+ my @result;
+
+ # minimum sanity check
+ if ( $M < $N ) {
+ warn "unable to choose $N from given selection of $M";
+ return ();
+ }
+
+ my ( @room, # number of spaces(rooms) each
+ @pos, # current position of cursor
+ $next_csr # next cursor to move
+ );
+
+ # set initial values ...
+ {
+ # each finger can move to right number of ( M-N ) space(s).
+ @room = ( $M-$N ) x $N;
+ @pos = 0 .. ($N - 1);
+ $next_csr = $N - 1; # last cursor at rightmost
+
+ # initial record; note: use not index number but real value
+ push @result, [ @pos ];
+ }
+
+ {
+ if ( $room[$next_csr] > 0 ) {
+ # current csr can move to right so just do it.
+ ++$pos[ $next_csr];
+ --$room[$next_csr]; # room decreased of course
+
+ # and make a record
+ push @result, [ @pos ];
+ redo;
+ }
+ else {
+ # no more room to move
+ # so find the next cursor to move
+ my $found = 0;
+ for ( my $i = $next_csr; $i > 0; --$i ) {
+ if ( $room[ $i-1 ] > 0 ) {
+ $next_csr = $i-1;
+ $found = 1;
+ last ;
+ }
+ }
+
+ if ( $found ) {
+ # move all the cursors which are starts from
+ # $next_csr to last one
+ @pos[ $next_csr .. ($N-1) ]
+ = map { $pos[$next_csr] + $_ } 1 .. ($N-$next_csr);
+ # note: all these finger has same room when moved
+ @room[ $next_csr .. ($N-1) ]
+ = ( $room[ $next_csr ] - 1 ) x ($N-$next_csr);
+
+ # and make a record
+ push @result, [ @pos ];
+
+ # next finger to move will be ($N-1)
+ # or even if it is not next loop will find anohter
+ $next_csr = ($N-1);
+
+ redo; # if we can move next cursor
+ }
+ }
+ }
+ @result;
+}
+
+!!"^^";
diff --git a/challenge-083/jeongoon/perl/ch-1.pl b/challenge-083/jeongoon/perl/ch-1.pl
new file mode 100644
index 0000000000..6db83a6e0b
--- /dev/null
+++ b/challenge-083/jeongoon/perl/ch-1.pl
@@ -0,0 +1,31 @@
+#!/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;
+
+use List::Util qw(sum);
+
+sub usage {
+ say 'Usage: perl ch-1.pl <a string with 3 or more words>', "\n",
+ 'ex) perl ch-1.pl "Perl Weekly Challenge"';
+}
+
+package main;
+
+my @words;
+
+@ARGV == 1 or usage, exit 1;
+@words = split /\s/, $ARGV[0];
+@words > 2 or usage, exit 2;
+
+say(
+ sum
+ map {length} # count each length
+ @words[
+ 1 # from the second word
+ ..
+ $#words-1 # to the second last one
+ ]
+ );
diff --git a/challenge-083/jeongoon/perl/ch-2.pl b/challenge-083/jeongoon/perl/ch-2.pl
new file mode 100644
index 0000000000..75af463b95
--- /dev/null
+++ b/challenge-083/jeongoon/perl/ch-2.pl
@@ -0,0 +1,79 @@
+#!/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;
+use List::Util qw(all sum);
+
+use FindBin;
+use lib ( $FindBin::Bin );
+use CombinationsIndex v0.3 qw(combinationsIndex);
+
+sub usage {
+ say 'Usage: perl ch-2.pl [-d|--debug] <natural num> ... ', "\n",
+ 'ex) perl ch-2.pl 12 2 10';
+}
+
+sub combinations ($$$) {
+ my ( $indexCount, $minSelection, $maxSelection ) = @_;
+ map { combinationsIndex( $indexCount, $_ ) }
+ $minSelection .. $maxSelection;
+}
+
+package main;
+
+my @N = grep { ! /-(h|-*help)/ } @ARGV;
+@N == @ARGV or usage, exit 0;
+
+@N = grep { ! /-(d|-*debug)/ } @ARGV;
+our $d = @N != @ARGV;
+
+( @N > 0
+ and
+ all { int($_) eq $_ and $_ > 0 } @N ) or usage, exit 1;
+
+@N == 1 and ( say( "0" ), exit 0 ); # already mimimum
+
+my $totalSum = sum @N;
+my $halfLen = int( .5 * @N ); # reduce the combinations in half
+
+# initial values ...
+my $minElems = +@N;
+my $minSum = $totalSum;
+
+for my $combi ( combinations( +@N, 1, $halfLen ) ) {
+ my $aSum = sum @N[ @$combi ];
+ my $bSum = $totalSum - $aSum;
+
+ my $curr =
+ ( # $aSum == $bSum
+ [ 0, ( scalar @$combi < $halfLen
+ ? scalar @$combi : scalar( @N - @$combi) ) ],
+ # $aSum > $bSum
+ [ $aSum - $bSum, scalar ( @N - @$combi) ],
+ # $aSum < $bSum
+ [ $bSum - $aSum, scalar @$combi ] )[ $aSum <=> $bSum ];
+
+ print "[sum: $$curr[0], elems: $$curr[1]] with @N[@$combi] ... " if $d;
+
+ if ( $$curr[0] > $minSum ) { # minimum sum not changed
+ say "skipped." if $d;
+ next;
+ }
+ elsif ( $$curr[0] < $minSum ) { # minimum sum cahnged
+ # so does minimum elements
+ say "**minium sum changed**" if $d;
+ ( $minSum, $minElems ) = @$curr;
+ }
+ elsif ( $$curr[1] < $minElems ) { # minimum sum is same
+ # also elements is less
+ say "**minimum count changed**" if $d;
+ $minElems = $$curr[1];
+ }
+ else {
+ say "" if $d;
+ }
+}
+
+say $minElems;
diff --git a/challenge-083/jeongoon/raku/ch-2.raku b/challenge-083/jeongoon/raku/ch-2.raku
index 45fbdcee95..0506ce2dc8 100644
--- a/challenge-083/jeongoon/raku/ch-2.raku
+++ b/challenge-083/jeongoon/raku/ch-2.raku
@@ -7,9 +7,29 @@
use v6.d;
multi MAIN ($n where * > 0) { say 0 }
+
+# without race
multi MAIN (*@n where { @n.all ~~ Int and @n.all > 0 }) {
my $s = @n.sum;
@n.combinations( 1..^ @n ).
+ map(
+ -> \n {
+ with $s - 2 * n.sum { # same as ( $s- n.sum ) - n.sum
+ next if $_ < 0;
+ $_ => n.elems
+ }
+ } ).
+ min.
+ value.
+ say
+}
+
+# tested with: raku jeongoon/raku/ch-2.raku --r 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13
+# finished in under 4 seconds on my laptop
+multi MAIN ( Bool:D :$r, *@n where { @n.all ~~ Int and @n.all > 0 }) {
+ $*ERR.say( "using race ..." );
+ my $s = @n.sum;
+ @n.combinations( 1..^ @n ).
race( :8degree:500batch ).
map(
-> \n {
@@ -18,7 +38,7 @@ multi MAIN (*@n where { @n.all ~~ Int and @n.all > 0 }) {
$_ => n.elems
}
} ).
- race( :8degree:5000batch ).
+ race( :8degree:500batch ).
min.
value.
say
diff --git a/challenge-083/jeongoon/raku/ch-2.without-race.raku b/challenge-083/jeongoon/raku/ch-2.without-race.raku
deleted file mode 100644
index 26dc21fbec..0000000000
--- a/challenge-083/jeongoon/raku/ch-2.without-race.raku
+++ /dev/null
@@ -1,23 +0,0 @@
-#!/usr/bin/env raku
-# -*- Mode: Raku; indent-tabs-mode: nil; coding: utf-8 -*-
-# vim: set et ts=4 sw=4:
-
-# personal-blog: https://dev.to/jeongoon/weekly-challenge-083-task-2-raku-2cjm
-
-use v6.d;
-
-multi MAIN ($n where * > 0) { say 0 }
-multi MAIN (*@n where { @n.all ~~ Int and @n.all > 0 }) {
- my $s = @n.sum;
- @n.combinations( 1..^ @n ).
- map(
- -> \n {
- with $s - 2 * n.sum { # same as ( $s- n.sum ) - n.sum
- next if $_ < 0;
- $_ => n.elems
- }
- } ).
- min.
- value.
- say
-}
diff --git a/challenge-083/jeongoon/raku/ch-2.yet-another-race.raku b/challenge-083/jeongoon/raku/ch-2.yet-another-race.raku
index 911d0f2136..6e0a952d6d 100644
--- a/challenge-083/jeongoon/raku/ch-2.yet-another-race.raku
+++ b/challenge-083/jeongoon/raku/ch-2.yet-another-race.raku
@@ -3,34 +3,40 @@
# vim: set et ts=4 sw=4:
# personal-blog: https://dev.to/jeongoon/weekly-challenge-083-task-2-raku-2cjm
-# I hoped that this will be faster but it wasn't :-/
+# I wished this implementation faster but it wasn't
+# I guess Raku doesn't like conditional flow control
+# so... generating is simpler and faster than filtering ??
use v6.d;
multi MAIN ($n where * > 0) { say 0 }
multi MAIN (*@n where { @n.all ~~ Int and @n.all > 0 }) {
- my \B = @n.Bag;
- my \S = @n.sum;
+ my \TotalSum = @n.sum;
my $half-len-floor = @n.elems div 2;
- @n.combinations( 1.. $half-len-floor ).
- race( :8degree:1000batch ).
+ @n.combinations( 1.. $half-len-floor ). # reduced combinations length
+ race( :8degree:500batch ).
map(
- -> $G
+ -> $grp # current combination
{
- my $a = $G.sum; # sum of selected group
- my $b = (S - $G.sum);
- given $a - $b {
- if $_ < 0 {
- -$_ => $G.elems
- } elsif $_ == 0 {
- |( 0 => $G.elems, 0 => (B (-) $G.Bag).total )
- } else {
- $_ => (B (-) $G.Bag).total
+ my $a = $grp.sum; # sum of selected group
+ my $b = (TotalSum - $grp.sum);
+ given $a cmp $b {
+ when Less {
+ ($b-$a) => $grp.elems
+ }
+ when More {
+ ($a-$b) => @n.elems - $grp.elems
+ }
+ default {
+ 0 => ($grp.elems < $half-len-floor
+ # using shorter elems
+ ?? $grp.elems !! @n.elems - $grp.elems)
}
}
}
).
- race( :8degree:1000batch ).
+ race( :8degree:500batch ).
min.
+ value.
say
}
generated by cgit (git 2.34.1) at 2026-07-03 18:21:49 +0000