1 Problem, 8 Programming Languages (C++ vs Rust vs Clojure vs Haskell...)

A video taking a look at 8 programming language solutions (C++, Rust, Clojure, Ruby, Elixir, Scala, Haskell and APL)to one problem.

Contest: 210
Problem Name: Maximum Nesting Depth of the Parentheses
Problem Type: Greedy

Github Links:

[johnwarren]

Iterators in Rust return either Some(x) or None, with None being the terminator of the iteration. By explicitly returning the iterator values, Rust's scan gives you the option of terminating the iteration early. Since iterators in Rust are lazy, this could yield a substantial performance improvement for large sequences. Rust is all about performance.

[Voltra_]

APL looks like someone wanted maths to be a programming language but decided to only keep half of the syntax of everything

[jaysistar]

For Rust:
1. The scan() function returns an Option because iterators in Rust are potentially infinite, and if the iterator that you're scanning doesn't end, then the scan function needs a way to end the sequence.
2. max() is what causes the Option to be returned at the end, not scan(), and it does so because while iterators can be infinite, they can also be empty.

Rust forces you to write code that handles edge cases, which is a good thing, IMHO.

[Mohammad-myyl]

Understanding machine code is much easier than reading APL

[amieres]

Here is the F# version using 'choose' which combines filter and map:
let maxDepth : string -> int =
Seq.choose(function '(' -> Some 1 | ')' -> Some -1 | _ -> None)
>> Seq.scan (+) 0
>> Seq.max

[marekkedzierski]

Doesn't the solution here seem way too complicated and costly - with all those regex's and such?
Why not just
1. set temp variable to 0,
2. go through the string one character at a time, add 1 to out temp variable when character is '(', subtract 1 when it is ')' and remember highest value (store highest value in another variable).
3. At string end just return this highest value if your temp variable is 0. If temp variable is different then 0 then input string is not valid

[nobodyinparticular]

9:10 the Clojure solution can be simplified a great deal. Here's my version:
(defn max-depth [s]
(->> (reductions #(+ %1 ({\( 1, \) -1} %2 0)) 0 s)
(reduce max)))

The function we're passing to reductions adds to the accumulator 1 for every opening parenthesis, -1 for every closing parenthesis, and 0 for any other character.

[MrMomoro]

You can use \case in haskell instead of the if-else (also you don't need a filter, just map non-parens to 0)
maxDepth = maximum
. scanl (+) 0
. map (\case '(' -> 1
')' -> -1
_ -> 0)

[harishonstar]

Absolutely loved the deep dive into APL!

[gurn]

Nice video.

But I think it would be a more interesting video if you can compare the optimal solutions for each language, rather than trying to find the functions that do the same thing in different languages. Each language has their own design philosophy and that's what makes them unique, and that's what we should appreciate the most.

That may be a lot of extra work, but the community is happy to help.

[franksonjohnson]

Currently on an APL dive thanks to this video, wow love it.

[mikemerinoff]

A small one about scala: don’t use return. Just remove it here. Curly braces can go too here.

[Brozium]

The '&' in Elixir is the capture operator. It is basically syntax sugar to represent a function. It's equivalent to writing the function as:
fn (num, acc) -> num + acc end. The &1 and &2 represent the respective parameters.

[JaihindhReddy]

In your #Clojure impl, the `re-seq` and the `map` steps can be replaced with `(keep {\( 1 \) -1})`.
`keep` is a variant of `map` that swallows (omits) `nil`s returned by the mapping fn.

[WildStriker]

I'm not an expert with rust (started learning last year), and I personally never used scan but I have used other methods of iter before. I "Scanned" (heh) the documentation and this is what I think:

First off my understanding of most of (if not all) of the iteration method signatures return an Option<T> type. It does this because once a None is returned this will signify the end of the iterator.

So you can call collect() after your .map or .scan and it will return a Vec<i32> without having to do any unwraps. I believe internally this would be calling iter.next() to return Some(i32) and will unwrap and push these into a Vec until None is returned.

I think the confusion comes from your closure function, as you expect it to behave like .map method (and others) you do not return an Option<i32> but just the i32 value.

My guess here is the Scan method is special and allows you to basically pass a None at any point during the "Scanning of the States"
to Stop the iterator early. Try adding a conditional statement to return a None if the acc value is greater than 2 then call collect(). You will see it will drop all values once your acc value hits 3. You could even do it like this: if acc == 3 then return None, even if the next acc value returns a Some(4) we would never see it as collect() stops at the first None it sees

Final thing to note: Your unwrap_or(0) isn't actually unwrapping your scan, that is for the max() function. This is because if you call it on an empty iterator / array this will return a None, so you need to tell it how to handle that.

Hope this makes sense and helps!

[Speykious]

I would say that this is a very functional approach to the problem.
With languages like C++ and Rust, I would probably have done something way more imperative, and also with only one iteration of the array. Here is some pseudo-code (it's really not ideal to make code on YouTube):

int acc = 0, max = 0
For each char c in s:
match c with
'(' => acc++
')' => acc--
_ => do nothing
if acc>max then max = acc
return max

[glob]

Thanks for the awesome video! For elixir, the ampersand notation is an alternate notation for describing anonymous functions and is not only for use in scan, what you you have as &(&1+&2) is equivalent to having written: fn a, b -> a + b end, the ampersand notation and the shortened if syntax could also have been useful to clean up the function passed to map and avoid having repetitive ends as such: &(if &1 == "(", do: 1, else: -1)

[OlegNizhnik]

For scala it's
def maxDepth(s: String) = s.collect{case '(' => 1 ; case ')' => -1}.scanLeft(0)(_ + _).max

[Dgby]

Rust has a filter_map function on iterators, and a match statement if you don't like using an if-else like that.

.filter_map(|value| match value { '(' => Some(1), ')' => Some(-1), _ => None })

[zyxzevn]

That is the simplest problem I can think of.

Just one simple loop.
int GetMax(char *str){
int max= 0; int depth=0;
for ( int i=0; i<length(str);i++){
if(str[i]=='('){ depth++; max= MAX(depth, max) }
}else if(str[i]==')'){ depth--;}
return max;
};