diff options
| -rw-r--r-- | challenge-076/andinus/README.org | 82 | ||||
| -rw-r--r-- | challenge-077/andinus/README.org | 37 | ||||
| -rw-r--r-- | challenge-078/andinus/README.org | 54 | ||||
| -rw-r--r-- | challenge-079/andinus/README.org | 28 | ||||
| -rw-r--r-- | challenge-080/andinus/README.org | 94 | ||||
| -rw-r--r-- | challenge-081/andinus/README.org | 135 | ||||
| -rw-r--r-- | challenge-082/andinus/README.org | 43 | ||||
| -rw-r--r-- | challenge-083/andinus/README | 173 | ||||
| -rw-r--r-- | challenge-083/andinus/README.org | 131 | ||||
| -rw-r--r-- | challenge-083/andinus/blog-1.txt | 1 | ||||
| -rw-r--r-- | challenge-083/andinus/blog-2.txt | 1 | ||||
| -rwxr-xr-x | challenge-083/andinus/perl/ch-1.pl | 17 | ||||
| -rwxr-xr-x | challenge-083/andinus/perl/ch-2.pl | 25 |
13 files changed, 788 insertions, 33 deletions
diff --git a/challenge-076/andinus/README.org b/challenge-076/andinus/README.org new file mode 100644 index 0000000000..1c1e50c098 --- /dev/null +++ b/challenge-076/andinus/README.org @@ -0,0 +1,82 @@ +#+SETUPFILE: ~/.emacs.d/org-templates/level-2.org +#+HTML_LINK_UP: ../../writings/ +#+OPTIONS: toc:2 +#+EXPORT_FILE_NAME: index +#+TITLE: Challenge 076 + +* Task 1 - Prime Sum +You are given a number =$N=. Write a script to find the minimum number of +prime numbers required, whose summation gives you =$N=. + +- For the sake of this task, please assume 1 is not a prime number. +** Perl +- Program: [[file:perl/ch-1.pl]] +- Help taken from: [[https://stackoverflow.com/a/35756072]]. + +User input is stored in =$input=. +#+BEGIN_SRC perl +my $input = shift @ARGV; +chomp $input; +#+END_SRC + +1 is assumed not to be a prime number so we reject numbers less than or +equal to 1. +#+BEGIN_SRC perl +die "Invalid input, enter numbers greater than 1.\n" if $input <= 1; +#+END_SRC + +If it's a prime number then the minimum sum is the number itself so we +just return it & exit. +#+BEGIN_SRC perl +say $input and exit 0 if is_prime($input) == 1; +#+END_SRC + +If =$input= is even then we loop from 2 to =$input / 2= & check if both =$i= & +=$diff= are primes. If both are primes then we have our numbers. + +Eventually we'll find 2 primes to be a sum of even numbers. From +WikiPedia, [[https://en.wikipedia.org/wiki/Goldbach%2527s_conjecture][Goldbach's conjecture]] has been shown to hold for all integers +less than =4 × 10^18=. +#+BEGIN_SRC perl +if ($input % 2 == 0) { + foreach my $i (2 ... $input / 2) { + my $diff = $input - $i; + say "$i + $diff" + if is_prime($i) and is_prime($diff); + } +} +#+END_SRC + +If the input is odd then we first check if =$input - 2= is a prime, if it +is then input is the sum of two primes, 2 & =$input - 2=. +#+BEGIN_SRC perl +elsif (is_prime($input - 2)) { + say "2 + $input"; +} +#+END_SRC + +If even that doesn't match then the minimum sum will have three numbers. +3 & then we use the same function as for even numbers to find the other +two primes. +#+BEGIN_SRC perl +else { + foreach my $i (2 ... ($input - 3) / 2) { + my $diff = $input - 3 - $i; + say "3 + $i + $diff" + if is_prime($i) and is_prime($diff); + } +} +#+END_SRC + +If $num is divisible by any number between 2 & =sqrt($num)= then it's not +prime. +#+BEGIN_SRC perl +sub is_prime { + my $num = shift @_; + + foreach my $i (2 ... sqrt($num)) { + return 0 if $num % $i == 0; + } + return 1; +} +#+END_SRC diff --git a/challenge-077/andinus/README.org b/challenge-077/andinus/README.org new file mode 100644 index 0000000000..c8f4df5ce3 --- /dev/null +++ b/challenge-077/andinus/README.org @@ -0,0 +1,37 @@ +#+SETUPFILE: ~/.emacs.d/org-templates/level-2.org +#+HTML_LINK_UP: ../../writings/ +#+OPTIONS: toc:2 +#+EXPORT_FILE_NAME: index +#+TITLE: Challenge 077 + +* Task 1 - Fibonacci Sum +You are given a positive integer =$N=. + +Write a script to find the total number of Fibonacci Numbers required to +get =$N= on addition. You are NOT allowed to repeat a number. Print 0 if +none found. + +*Note*: This solution is incomplete. Others have pushed complete + solutions, look at those. +** Perl +- Program: [[file:perl/ch-1.pl]] + +Make a list of all possible sums of =$input=. +#+BEGIN_SRC perl +my @sums; +foreach my $num (0 ... $input / 2) { + my $diff = $input - $num; + push @sums, [$diff, $num]; +} +#+END_SRC + +Loop over =@sums= & then print those sets which have both =$sums->[0]= & +=$sums->[1]= in fibonacci series. +#+BEGIN_SRC perl +sub is_fib { return Math::Fibonacci::isfibonacci(@_) } + +foreach (@sums) { + next unless is_fib($_->[0]) and is_fib($_->[1]); + say "$_->[0] + $_->[1]"; +} +#+END_SRC diff --git a/challenge-078/andinus/README.org b/challenge-078/andinus/README.org new file mode 100644 index 0000000000..f77cb87b00 --- /dev/null +++ b/challenge-078/andinus/README.org @@ -0,0 +1,54 @@ +#+SETUPFILE: ~/.emacs.d/org-templates/level-2.org +#+HTML_LINK_UP: ../../writings/ +#+OPTIONS: toc:2 +#+EXPORT_FILE_NAME: index +#+TITLE: Challenge 078 + +* Task 1 - Leader Element +You are given an array @A containing distinct integers. + +Write a script to find all leader elements in the array @A. Print (0) if +none found. + +- An element is leader if it is greater than all the elements to its + right side. +** Perl +- Program: [[file:perl/ch-1.pl]] + +We take input from =@ARGV=, loop over it. And then we loop over the +elements at right, goto next if =$arg= is less than =$elm=. This will push +all the leader elements to =@leader=. +#+BEGIN_SRC perl +my @leader; +MAIN: while (my $arg = shift @ARGV) { + foreach my $elm (@ARGV) { + next MAIN if $arg < $elm; + } + push @leader, $arg; +} +#+END_SRC +* Task 2 - Left Rotation +You are given array @A containing positive numbers and @B containing one +or more indices from the array @A. + +Write a script to left rotate @A so that the number at the first index +of @B becomes the first element in the array. Similary, left rotate @A +again so that the number at the second index of @B becomes the first +element in the array. +** Perl +- Program: [[file:perl/ch-2.pl]] + +Loop over =@B= & then rotate the elements. Same could've been done with +Left Rotation, I find this easier to understand. +#+BEGIN_SRC perl +my @A = qw(10 20 30 40 50); +my @B = qw(3 4); + +foreach (@B) { + my @tmp = @A; + foreach (1 ... scalar @tmp - $_) { + unshift @tmp, pop @tmp; + } + print join(', ', @tmp), "\n"; +} +#+END_SRC diff --git a/challenge-079/andinus/README.org b/challenge-079/andinus/README.org new file mode 100644 index 0000000000..41a3371639 --- /dev/null +++ b/challenge-079/andinus/README.org @@ -0,0 +1,28 @@ +#+SETUPFILE: ~/.emacs.d/org-templates/level-2.org +#+HTML_LINK_UP: ../../writings/ +#+OPTIONS: toc:2 +#+EXPORT_FILE_NAME: index +#+TITLE: Challenge 079 + +* Task 1 - Count Set Bits +You are given a positive number $N. + +Write a script to count the total numbrer of set bits of the binary +representations of all numbers from 1 to $N and return +=$total_count_set_bit % 1000000007=. +** Perl +- Program: [[file:perl/ch-1.pl]] + +We loop from =1 ... $input=, convert each =$num= to binary & count the set +bits & add them to =$set_bits=. +#+BEGIN_SRC perl +my $input = shift @ARGV; + +my $set_bits; +foreach my $num (1 ... $input) { + my $binary = sprintf "%b", $num; + my $count = $binary =~ tr/1//; + $set_bits += $count; +} +print $set_bits % 1000000007, "\n"; +#+END_SRC diff --git a/challenge-080/andinus/README.org b/challenge-080/andinus/README.org new file mode 100644 index 0000000000..4db2e0b32d --- /dev/null +++ b/challenge-080/andinus/README.org @@ -0,0 +1,94 @@ +#+SETUPFILE: ~/.emacs.d/org-templates/level-2.org +#+HTML_LINK_UP: ../../writings/ +#+OPTIONS: toc:2 +#+EXPORT_FILE_NAME: index +#+TITLE: Challenge 080 + +* Task 1 - Smallest Positive Number Bits +You are given unsorted list of integers =@N=. + +Write a script to find out the smallest positive number missing. +** Perl +- Initial version didn't check for =1=, I might have assumed that it was + accounted for in this line =print "1\n" and exit 0 if $sorted[$#sorted] + < 1;=. + +- This was pointed out by [[https://octodon.social/@polettix]] - + [[https://tilde.zone/web/statuses/104981669595493301#]] + +- Program: [[file:perl/ch-1.pl]] + +We take input from =@ARGV=, sort it & remove all inputs less than 1. We +check if the smallest positive number is 1. We filter repeated inputs +using =%hash=. +#+BEGIN_SRC perl +my %hash; +%hash = map { $_ => 1 } @ARGV; + +my @sorted = sort { $a <=> $b } keys %hash; + +# Print 1 if there are no positive numbers in @sorted. +print "1\n" and exit 0 if $sorted[$#sorted] < 1; + +while (my $arg = shift @sorted) { + next if $arg < 1; + print "1\n" and exit 0 unless $arg == 1; + last; +} +#+END_SRC + +Now we are sure the smallest positive number is not 1 & =@sorted= doesn't +contain any number less than 2. + +We loop from =2 ... $sorted[$#sorted] + 1= & then over =@sorted= array. The +first number from the array is dropped if it's equal to =$num=. If not +then =$num= is the smallest positive number, we print it & exit the =MAIN= +loop. + +This won't print the smallest positive number if the user passed +consecutive set of numbers, we just add =print "$num\n"= at the end to +cover this case. +#+BEGIN_SRC perl +MAIN: foreach my $num (2 ... $sorted[$#sorted] + 1) { + foreach (@sorted) { + shift @sorted and next MAIN if $num == $_; + print "$num\n" and last MAIN; + } + # Print the last element if it was a continous series of positive + # numbers. + print "$num\n"; +} +#+END_SRC +* Task 2 - Count Candies +You are given rankings of =@N= candidates. + +Write a script to find out the total candies needed for all candidates. +You are asked to follow the rules below: + +1. You must given at least one candy to each candidate. +2. Candidate with higher ranking get more candies than their mmediate + neighbors on either side. +** Perl +- Program: [[file:perl/ch-2.pl]] + +Giving at least one day to all candidates. +#+BEGIN_SRC perl +my $candies = scalar @ARGV; +#+END_SRC + +Handling first & last index, we do this outside the loop to keep it +simple. +#+BEGIN_SRC perl +$candies++ if $ARGV[0] > $ARGV[1]; +$candies++ if $ARGV[$#ARGV] > $ARGV[$#ARGV - 1]; +#+END_SRC + +Loop handles rest of the entries. +#+BEGIN_SRC perl +foreach my $index (1 ... $#ARGV - 1) { + $candies++ if $ARGV[$index] > $ARGV[$index - 1]; + $candies++ if $ARGV[$index] > $ARGV[$index + 1]; +} + +print "$candies\n"; +#+END_SRC diff --git a/challenge-081/andinus/README.org b/challenge-081/andinus/README.org new file mode 100644 index 0000000000..1d9a22f8db --- /dev/null +++ b/challenge-081/andinus/README.org @@ -0,0 +1,135 @@ +#+SETUPFILE: ~/.emacs.d/org-templates/level-2.org +#+HTML_LINK_UP: ../../writings/ +#+OPTIONS: toc:2 +#+EXPORT_FILE_NAME: index +#+TITLE: Challenge 081 + +* Task 1 - Common Base String +You are given 2 strings, =$A= and =$B=. + +Write a script to find out common base strings in =$A= and =$B=. + +#+BEGIN_QUOTE +A substring of a string $S is called base string if repeated +concatenation of the substring results in the string. +#+END_QUOTE +** Perl +- Program: [[file:perl/ch-1.pl]] + +We will break =$A= & check if any subset of =$A= join to make =$B=. To speed +up the process we only break =$A= by common divisors of both =$A= & =$B=. + +I assume that the length of =$B= is greater than =$A= in later parts so we +make sure that it's true. +#+BEGIN_SRC perl +my $A = shift @ARGV; +my $B = shift @ARGV; + +# We assume length($B) is greater than length($A). +unless (length($B) > length($A)) { + my $tmp = $A; + $A = $B; + $B = $tmp; +} +#+END_SRC + +If the strings have different sets of characters then common base string +cannot exists so we exit early. +#+BEGIN_SRC perl +# Check if common base string is even possible. +my (%chars_in_A, %chars_in_B); +$chars_in_A{$_} = 1 foreach split //, $A; +$chars_in_B{$_} = 1 foreach split //, $B; +foreach my $char (sort keys %chars_in_A) { + last if exists $chars_in_B{$char} ; + print "No common base string.\n" and exit 0 +} +#+END_SRC + +Get all the common divisors of =$A= & =$B=. +#+BEGIN_SRC perl +# Get all common divisors. +my %divisors_of_A = divisors(length($A)); +my %divisors_of_B = divisors(length($B)); +my @common_divisors; +foreach my $num (sort { $a <=> $b } keys %divisors_of_A) { + push @common_divisors, $num + if exists $divisors_of_B{$num}; +} + +# Returns all divisors of a number. +sub divisors { + my $n = shift @_; + my %divisors; + foreach my $i ( 1 ... $n){ + if ($n % $i == 0) { + $divisors{$i} = 1; + } + } + return %divisors; +} +#+END_SRC + +We check if any subset of =$A= joins to make =$B=. +#+BEGIN_SRC perl +my @common; + +foreach my $num (@common_divisors){ + my $tmp; + my $base = substr($A, 0, $num); + foreach (1 ... length($B) / $num) { + $tmp .= $base; + } + push @common, $base if $tmp eq $B; +} + +print "No common base string.\n" and exit 0 + unless scalar @common; +print join(', ', @common), "\n"; +#+END_SRC +* Task 2 - Frequency Sort +You are given file named input. + +Write a script to find the frequency of all the words. + +It should print the result as first column of each line should be the +frequency of the the word followed by all the words of that frequency +arranged in lexicographical order. Also sort the words in the ascending +order of frequency. + +For the sake of this task, please ignore the following in the input +file: =. " ( ) , 's --= +** Perl +- Program: [[file:perl/ch-2.pl]] + +Swap unwanted characters with a space. +#+BEGIN_SRC perl +my $file = path(shift @ARGV)->slurp; + +$file =~ s/(--|'s)/ /g; +$file =~ s/[."(),]+/ /g; +$file =~ s/ / /g; +$file =~ s/\n/ /g; +#+END_SRC + +Get frequency of each word. +#+BEGIN_SRC perl +my %words; +foreach my $word (split / /, $file) { + $words{$word} = 1 and next unless exists $words{$word}; + $words{$word}++; +} +#+END_SRC + +Format the output. +#+BEGIN_SRC perl +my %out; +foreach my $word (sort keys %words) { + my $freq = $words{$word}; + push @{$out{$freq}}, $word; +} + +foreach my $freq (sort { $a <=> $b} keys %out) { + print "$freq ", join(' ', @{$out{$freq}}, "\n"); +} +#+END_SRC diff --git a/challenge-082/andinus/README.org b/challenge-082/andinus/README.org new file mode 100644 index 0000000000..a76142a2e2 --- /dev/null +++ b/challenge-082/andinus/README.org @@ -0,0 +1,43 @@ +#+SETUPFILE: ~/.emacs.d/org-templates/level-2.org +#+HTML_LINK_UP: ../../writings/ +#+OPTIONS: toc:2 +#+EXPORT_FILE_NAME: index +#+TITLE: Challenge 082 + +* Task 1 - Common Factors +You are given 2 positive numbers $M and $N. + +Write a script to list all common factors of the given numbers. +** Perl +- Program: [[file:perl/ch-1.pl]] + +We loop over all the numbers from =1 ... $M= to get their factors & then +just compare it with factors of =$N=. I took this code from Challenge +081's ch-1.pl. +#+BEGIN_SRC perl +my $A = shift @ARGV; +my $B = shift @ARGV; + +# Get all common divisors. +my %divisors_of_A = divisors($A); +my %divisors_of_B = divisors($B); +my @common_divisors; +foreach my $num (sort { $a <=> $b } keys %divisors_of_A) { + push @common_divisors, $num + if exists $divisors_of_B{$num}; +} + +# Returns all divisors of a number. +sub divisors { + my $n = shift @_; + my %divisors; + foreach my $i ( 1 ... $n){ + if ($n % $i == 0) { + $divisors{$i} = 1; + } + } + return %divisors; +} + +print join(', ', @common_divisors), "\n"; +#+END_SRC diff --git a/challenge-083/andinus/README b/challenge-083/andinus/README index 2ad8a0f3af..ec69694ff3 100644 --- a/challenge-083/andinus/README +++ b/challenge-083/andinus/README @@ -1,26 +1,33 @@ ━━━━━━━━━━━━━━━ - CHALLENGE 082 + CHALLENGE 083 Andinus ━━━━━━━━━━━━━━━ + 2020-10-23 + + Table of Contents ───────────────── -1. Task 1 - Common Factors +1. Task 1 - Words Length +.. 1. Perl +2. Task 2 - Flip Array .. 1. Perl +.. 2. Further thinking -1 Task 1 - Common Factors -═════════════════════════ +1 Task 1 - Words Length +═══════════════════════ - You are given 2 positive numbers $M and $N. + You are given a string $S with 3 or more words. - Write a script to list all common factors of the given numbers. + Write a script to find the length of the string except the first and + last words ignoring whitespace. 1.1 Perl @@ -28,33 +35,133 @@ Table of Contents • Program: <file:perl/ch-1.pl> - We loop over all the numbers from `1 ... $M' to get their factors & - then just compare it with factors of `$N'. I took this code from - Challenge 081's ch-1.pl. + We split the input by space character & remove the first & last word + with `shift' & `pop' respectively. ┌──── - │ my $A = shift @ARGV; - │ my $B = shift @ARGV; - │ - │ # Get all common divisors. - │ my %divisors_of_A = divisors($A); - │ my %divisors_of_B = divisors($B); - │ my @common_divisors; - │ foreach my $num (sort { $a <=> $b } keys %divisors_of_A) { - │ push @common_divisors, $num - │ if exists $divisors_of_B{$num}; - │ } - │ - │ # Returns all divisors of a number. - │ sub divisors { - │ my $n = shift @_; - │ my %divisors; - │ foreach my $i ( 1 ... $n){ - │ if ($n % $i == 0) { - │ $divisors{$i} = 1; - │ } - │ } - │ return %divisors; - │ } + │ my @words = split / /, $ARGV[0]; + │ shift @words; + │ pop @words; + └──── + + Then we loop over `@words' & add the length of each word to `$len' & + print it. + ┌──── + │ my $len; + │ $len += length($_) foreach @words; │ - │ print join(', ', @common_divisors), "\n"; + │ print $len, "\n"; └──── + + +2 Task 2 - Flip Array +═════════════════════ + + You are given an array @A of positive numbers. + + Write a script to flip the sign of some members of the given array so + that the sum of the all members is minimum non-negative. + + Given an array of positive elements, you have to flip the sign of some + of its elements such that the resultant sum of the elements of array + should be minimum non-negative(as close to zero as possible). Return + the minimum no. of elements whose sign needs to be flipped such that + the resultant sum is minimum non-negative. + + +2.1 Perl +──────── + + • Program: <file:perl/ch-2.pl> + + *Note*: The solution is incomplete. + + We start by eliminating possible values, here by value I mean the + minimum non-negative sum of those numbers. + + Input is sorted & stored in `@nums'. + ┌──── + │ my @nums = @ARGV; + │ @nums = sort { $a <=> $b} @nums; + └──── + + If the input contains a single number then the answer is `0' because + flipping nothing will give us the minimum non-negative sum. If the + input contains 2 numbers then the answer is `1' because flipping the + smaller number will give us the minimum non-negative sum. + ┌──── + │ print "0\n" and exit 0 if scalar @nums == 1; + │ print "1\n" and exit 0 if scalar @nums == 2; + └──── + + The sum of all inputs will be the ceiling for the value. We can + eliminate more numbers by subtracting rest of the numbers from the + largest one, for example we subtract [1, 2, 3] from 5 if input is [1, + 2, 3, 5]. We'll get `-1', just make it positive & we have our new + ceiling. + + In that example the value has to be 1 or less than 1. The value will + be one in that case but it's not the answer, for example it would fail + in [1, 2, 3, 4]. We'll get -2 which we mod to get 2 when the value is + 0. + + So, if we get a positive number when subtracting the rest from the + largest one then the number is the value. Because if you make the + largest one negative then adding the rest will give a negative number + so the largest one must be positive. And you cannot make any other + number positive because that'll just increase the sum. + ┌──── + │ # Multiplied by 2 because we'll subtract it once. + │ my $tmp = 2 * $nums[$#nums]; + │ $tmp -= $_ foreach @nums; + └──── + + If the sum is 0 then we just need to flip the largest number to get + minimum non-negative sum, if it's greater than 0 then we need to flip + all the numbers except the largest one. + ┌──── + │ print "1\n" and exit 0 if $tmp == 0; + │ print scalar @nums - 1, "\n" and exit 0 if $tmp > 0; + └──── + + I haven't yet completed it. + ┌──── + │ die "ch-2.pl: cannot solve\n"; + └──── + + +2.2 Further thinking +──────────────────── + + The value will always be zero if we have 4n consecutive numbers, where + n is a natural number. This is true because when we add `pop @input' & + `shift @input' we get same number & because there were 4n consecutive + numbers we get even number of same numbers, we can just subtract half + of same numbers from rest to get 0. + + For example, [2, 3, 4, 5]. `5 + 2' equals `3 + 4', just subtract one + set to get 0. + + I had missed the "minimum number of elements" part. We need minimum + number of elements with flipped sign to get minimum non-negative sum. + But that can be solved once we get minimum non-negative sum. What this + means is that if we have to flip a thousand signs to get the value + then the solution is thousand but if we get the same value in 10 flips + then the solution is 10. + + Back to minimum non-negative sum. We could just write down all + permutations & get the value but that's bad solution. + + Also, till now I just assumed that the numbers are not repeated + because it's easy to work around that. We will just keep count of how + many numbers are repeated & add that to the final count because those + numbers will cancel themselves. This does affect the set of numbers so + this might lead us to wrong solution. + + Actually that will lead us to the wrong solution, instead of + cancelling each other some those numbers could be used to bring down + the sum close to zero. For example, if in [1, 1, 1, 1, 5] we make the + 1's cancel each other then the value we get is 5 & the answer 2 but + that's wrong. We could've made the 1's bring down 5 to 1 (`5 -1 -1 -1 + -1') & the value would've been 1, the answer 4. + + I think I'll leave it there for now. diff --git a/challenge-083/andinus/README.org b/challenge-083/andinus/README.org new file mode 100644 index 0000000000..8afd9070a6 --- /dev/null +++ b/challenge-083/andinus/README.org @@ -0,0 +1,131 @@ +#+SETUPFILE: ~/.emacs.d/org-templates/level-2.org +#+HTML_LINK_UP: ../../writings/ +#+OPTIONS: toc:2 +#+EXPORT_FILE_NAME: index +#+DATE: 2020-10-23 +#+TITLE: Challenge 083 + +* Task 1 - Words Length +You are given a string $S with 3 or more words. + +Write a script to find the length of the string except the first and +last words ignoring whitespace. +** Perl +- Program: [[file:perl/ch-1.pl]] + +We split the input by space character & remove the first & last word +with =shift= & =pop= respectively. +#+BEGIN_SRC perl +my @words = split / /, $ARGV[0]; +shift @words; +pop @words; +#+END_SRC + +Then we loop over =@words= & add the length of each word to =$len= & print +it. +#+BEGIN_SRC perl +my $len; +$len += length($_) foreach @words; + +print $len, "\n"; +#+END_SRC +* Task 2 - Flip Array +You are given an array @A of positive numbers. + +Write a script to flip the sign of some members of the given array so +that the sum of the all members is minimum non-negative. + +Given an array of positive elements, you have to flip the sign of some +of its elements such that the resultant sum of the elements of array +should be minimum non-negative(as close to zero as possible). Return the +minimum no. of elements whose sign needs to be flipped such that the +resultant sum is minimum non-negative. +** Perl +- Program: [[file:perl/ch-2.pl]] + +*Note*: The solution is incomplete. + +We start by eliminating possible values, here by value I mean the +minimum non-negative sum of those numbers. + +Input is sorted & stored in =@nums=. +#+BEGIN_SRC perl +my @nums = @ARGV; +@nums = sort { $a <=> $b} @nums; +#+END_SRC + +If the input contains a single number then the answer is =0= because +flipping nothing will give us the minimum non-negative sum. If the input +contains 2 numbers then the answer is =1= because flipping the smaller +number will give us the minimum non-negative sum. +#+BEGIN_SRC perl +print "0\n" and exit 0 if scalar @nums == 1; +print "1\n" and exit 0 if scalar @nums == 2; +#+END_SRC + +The sum of all inputs will be the ceiling for the value. We can +eliminate more numbers by subtracting rest of the numbers from the +largest one, for example we subtract [1, 2, 3] from 5 if input is [1, 2, +3, 5]. We'll get =-1=, just make it positive & we have our new ceiling. + +In that example the value has to be 1 or less than 1. The value will be +one in that case but it's not the answer, for example it would fail in +[1, 2, 3, 4]. We'll get -2 which we mod to get 2 when the value is 0. + +So, if we get a positive number when subtracting the rest from the +largest one then the number is the value. Because if you make the +largest one negative then adding the rest will give a negative number so +the largest one must be positive. And you cannot make any other number +positive because that'll just increase the sum. +#+BEGIN_SRC perl +# Multiplied by 2 because we'll subtract it once. +my $tmp = 2 * $nums[$#nums]; +$tmp -= $_ foreach @nums; +#+END_SRC + +If the sum is 0 then we just need to flip the largest number to get +minimum non-negative sum, if it's greater than 0 then we need to flip +all the numbers except the largest one. +#+BEGIN_SRC perl +print "1\n" and exit 0 if $tmp == 0; +print scalar @nums - 1, "\n" and exit 0 if $tmp > 0; +#+END_SRC + +I haven't yet completed it. +#+BEGIN_SRC perl +die "ch-2.pl: cannot solve\n"; +#+END_SRC +** Further thinking +The value will always be zero if we have 4n consecutive numbers, where n +is a natural number. This is true because when we add =pop @input= & +=shift @input= we get same number & because there were 4n consecutive +numbers we get even number of same numbers, we can just subtract half of +same numbers from rest to get 0. + +For example, [2, 3, 4, 5]. =5 + 2= equals =3 + 4=, just subtract one set to +get 0. + +I had missed the "minimum number of elements" part. We need minimum +number of elements with flipped sign to get minimum non-negative sum. +But that can be solved once we get minimum non-negative sum. What this +means is that if we have to flip a thousand signs to get the value then +the solution is thousand but if we get the same value in 10 flips then +the solution is 10. + +Back to minimum non-negative sum. We could just write down all +permutations & get the value but that's bad solution. + +Also, till now I just assumed that the numbers are not repeated because +it's easy to work around that. We will just keep count of how many +numbers are repeated & add that to the final count because those numbers +will cancel themselves. This does affect the set of numbers so this +might lead us to wrong solution. + +Actually that will lead us to the wrong solution, instead of cancelling +each other some those numbers could be used to bring down the sum close +to zero. For example, if in [1, 1, 1, 1, 5] we make the 1's cancel each +other then the value we get is 5 & the answer 2 but that's wrong. We +could've made the 1's bring down 5 to 1 (=5 -1 -1 -1 -1=) & the value +would've been 1, the answer 4. + +I think I'll leave it there for now. diff --git a/challenge-083/andinus/blog-1.txt b/challenge-083/andinus/blog-1.txt new file mode 100644 index 0000000000..6bee0ca8ee --- /dev/null +++ b/challenge-083/andinus/blog-1.txt @@ -0,0 +1 @@ +https://andinus.tilde.institute/pwc/challenge-083/ diff --git a/challenge-083/andinus/blog-2.txt b/challenge-083/andinus/blog-2.txt new file mode 100644 index 0000000000..6bee0ca8ee --- /dev/null +++ b/challenge-083/andinus/blog-2.txt @@ -0,0 +1 @@ +https://andinus.tilde.institute/pwc/challenge-083/ diff --git a/challenge-083/andinus/perl/ch-1.pl b/challenge-083/andinus/perl/ch-1.pl new file mode 100755 index 0000000000..fe09b8cb18 --- /dev/null +++ b/challenge-083/andinus/perl/ch-1.pl @@ -0,0 +1,17 @@ +#!/usr/bin/perl + +use strict; +use warnings; + +die "usage: ./ch-1.pl <string with 3 or more words>\n" + unless scalar @ARGV == 1 + and scalar split(/ /, $ARGV[0]) >= 3; + +my @words = split / /, $ARGV[0]; +shift @words; +pop @words; + +my $len; +$len += length($_) foreach @words; + +print $len, "\n"; diff --git a/challenge-083/andinus/perl/ch-2.pl b/challenge-083/andinus/perl/ch-2.pl new file mode 100755 index 0000000000..d9d9bc18b9 --- /dev/null +++ b/challenge-083/andinus/perl/ch-2.pl @@ -0,0 +1,25 @@ +#!/usr/bin/perl + +use strict; +use warnings; + +die "usage: ./ch-2.pl <positive numbers>\n" + unless scalar @ARGV >= 1; + +my @nums = @ARGV; +@nums = sort { $a <=> $b} @nums; + +die "ch-2.pl: input array of positive numbers\n" + if $nums[0] <= 0; + +print "0\n" and exit 0 if scalar @nums == 1; +print "1\n" and exit 0 if scalar @nums == 2; + +# Multiplied by 2 because we'll subtract it once. +my $tmp = 2 * $nums[$#nums]; +$tmp -= $_ foreach @nums; + +print "1\n" and exit 0 if $tmp == 0; +print scalar @nums - 1, "\n" and exit 0 if $tmp > 0; + +die "ch-2.pl: cannot solve\n"; |