This is my response to The Weekly Challenge #346.
( and ).
Input: $str = '(()())'
Output: 6
Valid Parenthesis: '(()())'
Input: $str = ')()())'
Output: 4
Valid Parenthesis: '()()' at positions 1-4.
Input: $str = '((()))()(((()'
Output: 8
Valid Parenthesis: '((()))()' at positions 0-7.
Input: $str = '))))((()('
Output: 2
Valid Parenthesis: '()' at positions 6-7.
Input: $str = '()(()'
Output: 2
Valid Parenthesis: '()' at positions 0-1 and 3-4.
This task can be divided in two:
gather/take.
I will use the term «balanced string» for all instances of «valid parenthesis», to stand out from «longest valid parenthesis».
File: longest-parenthesis (first part)
#! /usr/bin/env raku
unit sub MAIN ($str where $str ~~ /^ <[\(\)]>+ $/, # [1]
:v(:$verbose));
my $balanced := gather # [2]
{
for ^($str.chars) -> $i # [3]
{
my $match = ""; # [4]
my $balance = 0; # [5]
for $str.substr($i).comb -> $char # [6]
{
if $char eq "(" # [7]
{
$balance++; # [7a]
$match ~= "("; # [7b]
}
elsif $balance == 0 # [8]
{
last; # [8a]
}
else # [9]
{
$balance--; # [9a]
$match ~= ")"; # [9b]
}
take { index => $i, match => $match } if $balance == 0; # [10]
}
}
}
[1] A string containing parenthesis only, with at least one.
[2] Collect all the balanced strings,
if any, with gather.
See my Raku Gather, I Take article or docs.raku.org/language/control#gather/take for more information about gather/take.
[3] Iterate over the start position in the string; from the first character (index 0) to the very last one (index one less than the length).
Note that the last iteration will have one character to
consider, and this cannot form a balanced string. But special casing
this one is not worth the effort. (We could have written
0 .. $str.chars -2
[4] The current match, a potentially future balanced string.
[5] Balance count. We are going to add 1 for an opening parenthesis (in [7a]), and subtract one on a closing one (in [9a]).
[6] Iterate over the individual characters from the current index (from [3)).
[7] Is it an opening parenthesis? If so, count it [7a] and update the match [7b].
[8] No? Then it is a closing parenthesis. If the balance is zero, then adding a closing one would cause an unbalanced string and we can skip the rest of this iteration [8a] as adding more will not undo the damage.
[9] Still no, but the count allows for a closing parenthesis. Count it [9a] and update the match [9b].
[10] Return the current match (with take) if the match
string is balanced.
my $longest = 0; # [11]
for $balanced -> $curr # [12]
{
my $length = $curr<match>.chars; # [13]
my $is-max = $length > $longest; # [14]
$longest = $length if $is-max; # [15]
say ": Candidate '{ $curr<match> }' at index $curr<index> \
{ $is-max ?? " -> new max $length" !! "" }" if $verbose;
}
say $longest; # [16]
[11] The length of the longest balanced string encountered so far.
[12] Iterate over the balanced strings.
[13] Get the length.
[14] Is it longer than the previously recorded longest one?
[15] If so, update the longest length.
[16] Print the longest length.
Running it:
$ ./longest-parenthesis '(()())'
6
$ ./longest-parenthesis ')()())'
4
$ ./longest-parenthesis '((()))()(((()'
8
$ ./longest-parenthesis '))))((()('
2
$ ./longest-parenthesis '()(()'
2
Looking good.
With verbose mode:
$ ./longest-parenthesis -v '(()())'
: Candidate '(()())' at index 0 -> new max 6
: Candidate '()' at index 1
: Candidate '()()' at index 1
: Candidate '()' at index 3
6
$ ./longest-parenthesis -v ')()())'
: Candidate '()' at index 1 -> new max 2
: Candidate '()()' at index 1 -> new max 4
: Candidate '()' at index 3
4
$ ./longest-parenthesis -v '((()))()(((()'
: Candidate '((()))' at index 0 -> new max 6
: Candidate '((()))()' at index 0 -> new max 8
: Candidate '(())' at index 1
: Candidate '()' at index 2
: Candidate '()' at index 6
: Candidate '()' at index 11
8
$ ./longest-parenthesis -v '))))((()('
: Candidate '()' at index 6 -> new max 2
2
$ ./longest-parenthesis -v '()(()'
: Candidate '()' at index 0 -> new max 2
: Candidate '()' at index 3
2
+, - and *
between the digits in the given string that evaluates to target integer.
Input: $str = "123", $target = 6
Output: ("1*2*3", "1+2+3")
Input: $str = "105", $target = 5
Output: ("1*0+5", "10-5")
Input: $str = "232", $target = 8
Output: ("2*3+2", "2+3*2")
Input: $str = "1234", $target = 10
Output: ("1*2*3+4", "1+2+3+4")
Input: $str = "1001", $target = 2
Output: ("1+0*0+1", "1+0+0+1", "1+0-0+1", "1-0*0+1", "1-0+0+1",
"1-0-0+1")
Note that the empty string is also allowed as an operator (or rather in lieu of one), as shown by the second value in the output from the second example.
File: magic-expression
#! /usr/bin/env raku
unit sub MAIN ($str where $str ~~ /^ <[0..9]>+ $/, # [1]
Int $target, # [2]
:v(:$verbose));
my $op-size = $str.chars -1; # [3]
my @ops = (("+", "-", "*", "") xx $op-size).flat; # [4]
my @digits = $str.comb; # [5]
my @matches; # [6]
say ": Operators: { @ops.raku }" if $verbose;
for @ops.combinations($op-size) -> @op # [7]
{
my $eval = roundrobin(@digits, @perm)>>.join.join; # [8]
my $sum = $eval.EVAL; # [9]
my $is-equal = $sum == $target; # [10]
say ": $eval = $sum { $is-equal ?? "OK" !! "(!= $target)" }" if $verbose;
@matches.push: $eval if $is-equal; # [11]
}
say "({ @matches.unique.map('"' ~ * ~ '"').join(", ") })"; # [12]
[1] Digits only, with at least one.
[2] The target, which may be negative.
[3] The number of operators to use, one less than the number of digits.
[4]
It is possible (i.e. legal) to get all the operators identical
to each other, so we must have at least that many ($op-size) of each
one. This is done with the list repetition operator xx and a final
flat to to get a one dimentional list.
See docs.raku.org/routine/xx for more information about xx.
See docs.raku.org/routine/flat for more information about flat.
[5] Get the digist as a list of individual digits.
[6] The matches, the expressions that work out, will end up here.
[7] Iterate over the combinations of the operators with the required length.
Note that we normally would have to shuffle the order of
the combinations with permutations, but that is not necessary
now as we get them for free due to the duplicates:
> <* * + + - ->.combinations(2)
((* *) (* +) (* +) (* -) (* -) (* +) (* +) (* -) (* -) (+ +) (+ -) (+ -) \
(+ -) (+ -) (- -))
We will also get duplicates (e.g. four of (* +) as both operators come
in duplicate), and the number of them will increase exponentially as we add
on more digits (and operators). I'll ignore this performance issue for
now.
[8] Merge the digits and operators with roundrobin,
and glue them all together into a single string. First the pairs of
digit/operator, and them the outer list.
See docs.raku.org/routine/roundrobin for more information about roundrobin.
[9] Use EVAL on the resulting string to compute
the sum.
See docs.raku.org/routine/EVAL for more information about EVAL.
[10] Did we get the target value?
[11] If so, add the expression to the result.
[12] Print the result, but get rid of any duplicates.
Running it:
$ ./magic-expression 123 6
("1+2+3", "1*2*3")
$ ./magic-expression 105 5
("1*0+5", "10-5")
$ ./magic-expression 232 8
("2+3*2", "2*3+2")
$ ./magic-expression 1234 10
("1*2*3+4", "1+2+3+4")
$ ./magic-expression 1001 2
("1-0*0+1", "1+0-0+1", "1-0+0+1", "1-0-0+1", "1+0*0+1", "1+0+0+1")
Looking good.
Verbose mode:
$ ./magic-expression -v 123 6
: Operators: ["+", "-", "*", "", "+", "-", "*", ""]
: 1+2-3 == 0 (!= 6)
: 1+2*3 == 7 (!= 6)
: 1+23 == 24 (!= 6)
: 1+2+3 == 6 OK
: 1+2-3 == 0 (!= 6)
: 1+2*3 == 7 (!= 6)
: 1+23 == 24 (!= 6)
: 1-2*3 == -5 (!= 6)
: 1-23 == -22 (!= 6)
: 1-2+3 == 2 (!= 6)
: 1-2-3 == -4 (!= 6)
: 1-2*3 == -5 (!= 6)
: 1-23 == -22 (!= 6)
: 1*23 == 23 (!= 6)
: 1*2+3 == 5 (!= 6)
: 1*2-3 == -1 (!= 6)
: 1*2*3 == 6 OK
: 1*23 == 23 (!= 6)
: 12+3 == 15 (!= 6)
: 12-3 == 9 (!= 6)
: 12*3 == 36 (!= 6)
: 123 == 123 (!= 6)
: 1+2-3 == 0 (!= 6)
: 1+2*3 == 7 (!= 6)
: 1+23 == 24 (!= 6)
: 1-2*3 == -5 (!= 6)
: 1-23 == -22 (!= 6)
: 1*23 == 23 (!= 6)
("1+2+3", "1*2*3")
$ ./magic-expression -v 105 5
: Operators: ["+", "-", "*", "", "+", "-", "*", ""]
: 1+0-5 = -4 (!= 5)
: 1+0*5 = 1 (!= 5)
: 1+05 has a leading zero; skip
: 1+0+5 = 6 (!= 5)
: 1+0-5 = -4 (!= 5)
: 1+0*5 = 1 (!= 5)
: 1+05 has a leading zero; skip
: 1-0*5 = 1 (!= 5)
: 1-05 has a leading zero; skip
: 1-0+5 = 6 (!= 5)
: 1-0-5 = -4 (!= 5)
: 1-0*5 = 1 (!= 5)
: 1-05 has a leading zero; skip
: 1*05 has a leading zero; skip
: 1*0+5 = 5 OK
: 1*0-5 = -5 (!= 5)
: 1*0*5 = 0 (!= 5)
: 1*05 has a leading zero; skip
: 10+5 = 15 (!= 5)
: 10-5 = 5 OK
: 10*5 = 50 (!= 5)
: 105 = 105 (!= 5)
: 1+0-5 = -4 (!= 5)
: 1+0*5 = 1 (!= 5)
: 1+05 has a leading zero; skip
: 1-0*5 = 1 (!= 5)
: 1-05 has a leading zero; skip
: 1*05 has a leading zero; skip
("1*0+5", "10-5")
$ ./magic-expression -v 232 8
: Operators: ["+", "-", "*", "", "+", "-", "*", ""]
: 2+3-2 = 3 (!= 8)
: 2+3*2 = 8 OK
: 2+32 = 34 (!= 8)
: 2+3+2 = 7 (!= 8)
: 2+3-2 = 3 (!= 8)
: 2+3*2 = 8 OK
: 2+32 = 34 (!= 8)
: 2-3*2 = -4 (!= 8)
: 2-32 = -30 (!= 8)
: 2-3+2 = 1 (!= 8)
: 2-3-2 = -3 (!= 8)
: 2-3*2 = -4 (!= 8)
: 2-32 = -30 (!= 8)
: 2*32 = 64 (!= 8)
: 2*3+2 = 8 OK
: 2*3-2 = 4 (!= 8)
: 2*3*2 = 12 (!= 8)
: 2*32 = 64 (!= 8)
: 23+2 = 25 (!= 8)
: 23-2 = 21 (!= 8)
: 23*2 = 46 (!= 8)
: 232 = 232 (!= 8)
: 2+3-2 = 3 (!= 8)
: 2+3*2 = 8 OK
: 2+32 = 34 (!= 8)
: 2-3*2 = -4 (!= 8)
: 2-32 = -30 (!= 8)
: 2*32 = 64 (!= 8)
("2+3*2", "2*3+2")
$ ./magic-expression -v 1234 10
: Operators: ["+", "-", "*", "", "+", "-", "*", "", "+", "-", "*", ""]
: 1+2-3*4 = -9 (!= 10)
: 1+2-34 = -31 (!= 10)
... 216 rows not shown ...
: 1+2*34 = 69 (!= 10)
: 1-2*34 = -67 (!= 10)
("1+2+3+4", "1*2*3+4")
$ ./magic-expression -v 1001 2
: Operators: ["+", "-", "*", "", "+", "-", "*", "", "+", "-", "*", ""]
: 1+0-0*1 = 1 (!= 2)
: 1+0-01 has a leading zero; skip
... 216 rows not shown ...
: 1+0*01 has a leading zero; skip
: 1-0*01 has a leading zero; skip
("1+0-0+1", "1+0*0+1", "1+0+0+1", "1-0*0+1", "1-0+0+1", "1-0-0+1")
Then the performance issue. The last two examples were kind of slow. We got rid of the duplicates just in time for the output (in [12]), but should really have done this much earlier.
So let us do it now:
File: magic-expression-faster
#! /usr/bin/env raku
unit sub MAIN ($str where $str ~~ /^ <[0..9]>+ $/,
Int $target,
:v(:$verbose));
my $op-size = $str.chars -1;
my @ops = (("+", "-", "*", "") xx $op-size).flat;
my @digits = $str.comb;
my @matches;
my %seen;
say ": Operators: { @ops.raku }" if $verbose;
for @ops.combinations($op-size) -> @op
{
my $eval = roundrobin(@digits, @op)>>.join.join;
next if %seen{$eval}++;
if $eval ~~ /^0<[0..9]>/ || $eval ~~ /<[+*-]>0<[0..9]>/
{
say ": $eval has a leading zero; skip" if $verbose;
next;
}
my $sum = $eval.EVAL;
my $is-equal = $sum == $target;
say ": $eval = $sum { $is-equal ?? "OK" !! "(!= $target)" }" if $verbose;
@matches.push: $eval if $is-equal;
}
say "({ @matches.map('"' ~ * ~ '"').join(", ") })";
I have added a hash to store the expressions already computed, so that we can
skip EVAL-ing them again. The final say statement does not have any
duplicates to grapple with now.
$ ./magic-expression 10501 5
("1+0+5-0-1", "1+0+5+0-1", "1-0+5-0-1", "1-0+5+0-1", "1*0+5-0*1", "1*0+5+0*1", "10-5+0*1", "10-5-0*1")
$ ./magic-expression-faster 10501 5
("1+0+5-0-1", "1+0+5+0-1", "1-0+5-0-1", "1-0+5+0-1", "1*0+5-0*1", "1*0+5+0*1", "10-5+0*1", "10-5-0*1")
The speed increase is significant. The first one took 6 and a half seconds on my pc, whilst the second one took just 2.
And that's it.