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.
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...