Nice!
I tried to basically remake this post's implementation but using a string as a stack (and not a list), so I'm not using lists anywhere and just evaluating if the stack is empty at the end of everything.
Also, there is an early escape when parens don't match, so we don't have to read the whole input:
whenheadin@closers,do:(stack_head<>headin@valid_matches)&&run_check(tail,stack_tail)# or using a mapwhenheadin@closersdo:@pairs[stack_head]==head&&run_check(tail,stack_tail)
This is what I came up with:
defmoduleParensdo@openers["{","[","("]@closers["}","]",")"]@pairs%{"{"=>"}","["=>"]","("=>")"}defis_matching?(input)whenis_binary(input),do:run_check(input,"")defis_matching?(input),do:"#{inspect(input)} is not a valid string."defis_matching?(),do:"input should be a valid string"defprun_check("",stack),do:stack==""# When head is an opener, simply put in the stackdefprun_check(<<head::binary-size(1)>><>tail,stack)whenheadin@openers,do:run_check(tail,head<>stack)# Edge case to ensure we can correctly return false when the stack is empty# and the next character is a closer. Without this, the function would not# match the run_check when in @closers because the stack can't be emptydefprun_check(<<head::binary-size(1)>><>_tail,"")whenheadin@closersdofalseend# Empty stacks does not match here, so I had to create a specific match for an# empty stack and a closerdefprun_check(<<head::binary-size(1)>><>tail,<<stack_head::binary-size(1)>><>stack_tail)whenheadin@closers,do:@pairs[stack_head]==head&&run_check(tail,stack_tail)# When head is not opener nor closer, simply ignoredefprun_check(<<_head::binary-size(1)>><>tail,stack)dorun_check(tail,stack)endend
I was testing the time execution by running this is IEx: :timer.tc(fn -> Parens.is_matching?("(((((((((([[{[]}]]))))()([[[]]]))))))){({({({{{{({()})}{({})}}}})})})}[]") end)
I got to the conclusion that using a map to check if the parens are matching is faster that a list with the valid matches, but not by much.
# Apparently this@pairs%{"{"=>"}","["=>"]","("=>")"}@pairs[stack_head]==head# is slightly faster than this@valid_matches["{}","[]","()"]stack_head<>headin@valid_matches
There is a way to avoid @valid_matches or @pairs (in your case) and make it even faster. Again, pattern matching is the Boss, right?!
So we can avoid a map and a list by this (in my case):
At first I didn't want to make so many repeated function definitions to match specifically "}", "]" or ")", I thought it wasn't that readable and too repetitive, but I changed my mind over a few months, and now looking at the perspective of speed, it looks pretty good.
Maybe a way to make it faster is to break the recursion everytime the accumulator was set to false and return the false itself? Or maybe the very first definition of run_check/2 could be
defprun_check(_input,[_openers,false]),do:false
?
I'm not sure how to make it faster, does it involve some change in strategy? 🤔
Well, if we could group the whitespaces together during the match, that would be great. The program would just have to check non-whitespace characters.
Something like this would work for only a single space
It would be perfect to match an unspecified amount of whitecharacters at once. Using a regex it would be a breeze, but I'm sure that is not what we want here.
In fact, we would like to match everything that is not one of { [ ( ) ] }, with unspecified length, not just whitespaces. Then we could ignore everything that is irrelevant, essentially doing a filter inside the match.
After achieving a way to do that, parsing abc {} would require the same amount of iterations as {}.
But how do I do it?
Matches like "{" <> irrelevant <> "{" fail because the size of the variable irrelevant is unknown, and "{" <> <<irr::binary>> <> "{" fails because a binary field without a size is only allowed as the last member of the match (basically the same problem, Elixir doesn't know up to what point to check).
I could write like 200 headers of the function for one, two, three, ..., 200 character length for the irrelevant variable, but that would be tedious. I am 100% sure there is a way to make Elixir itself write some Elixir code for me, maybe use some range to dynamically create these functions, and leave a last header matching whatever didn't match before. It would speed up the parsing for most cases, and in the worst scenario it would be the same as it is now.
I cleaned up/refactored my solution. Check it out down below.
There is a section ### making a recursive step wider ### - that code explains my thoughts. I left some logs in that part, so if you run code from iex you will clearly see what I was trying to say and the output looks like this:
iex::8> ParensBracketsBraces.matching?("(a + [ b - c ] )")
ELEMENT <> WHITESPACE
: [elem: "a", input_tail: "+ [ b - c ] )", stack: "("]
ELEMENT <> WHITESPACE
: [elem: "+", input_tail: "[ b - c ] )", stack: "("]
WHITESPACE <> ELEMENT
: [elem: "b", input_tail: " - c ] )", stack: "[("]
WHITESPACE <> ELEMENT
: [elem: "-", input_tail: " c ] )", stack: "[("]
WHITESPACE <> ELEMENT
: [elem: "c", input_tail: " ] )", stack: "[("]
BTW, hope you use iex - very powerful tool...
defmoduleParensBracketsBracesdo@openers["{","[","("]@closers["}","]",")"]@all@openers++@closersdefmatching?(input)whenis_binary(input),do:run_check("",input)defmatching?(input),do:"#{inspect(input)} is not a valid string."defmatching?(),do:"input should be a valid string"### --- BASE CASES --- #### matching pairsdefprun_check(""=_stack,""=_input),do:true# no matchesdefprun_check(_,""=_input),do:false### matches on opener only and putting it to the stack ###defprun_check(stack,<<opener::binary-size(1)>><>input_tail)whenopenerin@openers,do:run_check(opener<>stack,input_tail)### covering case where there are only closers ###defprun_check("",<<closer::binary-size(1)>><>_tail_input)whencloserin@closers,do:false### comparing top item in the stack with closer ###defprun_check("["<>stack_tail,"]"<>input_tail),do:run_check(stack_tail,input_tail)defprun_check("("<>stack_tail,")"<>input_tail),do:run_check(stack_tail,input_tail)defprun_check("{"<>stack_tail,"}"<>input_tail),do:run_check(stack_tail,input_tail)################################## making a recursive step wider ###defprun_check(stack,<<elem::binary-size(1)>><>" "<>input_tail)whenelemnotin@alldoIO.inspect(binding(),label:"\nELEMENT <> WHITESPACE \n\n")run_check(stack,input_tail)enddefprun_check(stack," "<><<elem::binary-size(1)>><>input_tail)whenelemnotin@alldoIO.inspect(binding(),label:"\nWHITESPACE <> ELEMENT \n\n")run_check(stack,input_tail)end################################## if not openers or/and closers ###defprun_check(stack,<<_::binary-size(1)>><>input_tail),do:run_check(stack,input_tail)end
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Nice!
I tried to basically remake this post's implementation but using a string as a stack (and not a list), so I'm not using lists anywhere and just evaluating if the stack is empty at the end of everything.
Also, there is an early escape when parens don't match, so we don't have to read the whole input:
This is what I came up with:
I was testing the time execution by running this is IEx:
:timer.tc(fn -> Parens.is_matching?("(((((((((([[{[]}]]))))()([[[]]]))))))){({({({{{{({()})}{({})}}}})})})}[]") end)
I got to the conclusion that using a map to check if the parens are matching is faster that a list with the valid matches, but not by much.
There is a way to avoid
@valid_matches
or@pairs
(in your case) and make it even faster. Again, pattern matching is the Boss, right?!So we can avoid a map and a list by this (in my case):
But again there is a way to make it even faster :)
Great job with cleaning up your solution!
At first I didn't want to make so many repeated function definitions to match specifically
"}"
,"]"
or")"
, I thought it wasn't that readable and too repetitive, but I changed my mind over a few months, and now looking at the perspective of speed, it looks pretty good.Maybe a way to make it faster is to break the recursion everytime the accumulator was set to false and return the false itself? Or maybe the very first definition of
run_check/2
could be?
I'm not sure how to make it faster, does it involve some change in strategy? 🤔
Many thanks! 😁
If we have 2 inputs:
{({})}
and 2.{ ( { } ) }
In
1
we have to perform 6 iterations to walk through it and in2
it's 11, right?So is there a way we can walk through both inputs with the same amount of iterations? If yes - we can apply the same approach to our solution.
(Pattern matching is whispering here something for us again 🙂 )
Well, if we could group the whitespaces together during the match, that would be great. The program would just have to check non-whitespace characters.
Something like this would work for only a single space
And then repeat for brackets and parenthesis.
It would be perfect to match an unspecified amount of whitecharacters at once. Using a regex it would be a breeze, but I'm sure that is not what we want here.
In fact, we would like to match everything that is not one of
{ [ ( ) ] }
, with unspecified length, not just whitespaces. Then we could ignore everything that is irrelevant, essentially doing a filter inside the match.After achieving a way to do that, parsing
abc {}
would require the same amount of iterations as{}
.But how do I do it?
Matches like
"{" <> irrelevant <> "{"
fail because the size of the variableirrelevant
is unknown, and"{" <> <<irr::binary>> <> "{"
fails because a binary field without a size is only allowed as the last member of the match (basically the same problem, Elixir doesn't know up to what point to check).I could write like 200 headers of the function for one, two, three, ..., 200 character length for the
irrelevant
variable, but that would be tedious. I am 100% sure there is a way to make Elixir itself write some Elixir code for me, maybe use some range to dynamically create these functions, and leave a last header matching whatever didn't match before. It would speed up the parsing for most cases, and in the worst scenario it would be the same as it is now.I cleaned up/refactored my solution. Check it out down below.
There is a section
### making a recursive step wider ###
- that code explains my thoughts. I left some logs in that part, so if you run code fromiex
you will clearly see what I was trying to say and the output looks like this:BTW, hope you use
iex
- very powerful tool...