Code Review Request - Unbalanced Parenthesis correction

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Code Review Request - Unbalanced Parenthesis correction

Michael Litchard-2

I'm prepping for a coding interview, and am examining the task of correcting unbalanced parentheses. The finger tree seems to be the right data structure. As a proof of concept I've used Data.Sequence to test my idea. If this is the right direction to go, I'll write more specialized finger tree code. The code works on the few test cases I have tried. Feedback appreciated.

{-# LANGUAGE ViewPatterns #-}
module Parenthesis where
import BasicPrelude hiding (concat,null,empty)

import Data.Sequence hiding (length)
import Data.Foldable hiding (length,null)

balanceParens :: String -> String
balanceParens str = go str [] empty
  where
    go [] [] (null -> True) = []
    go [] [] parens = Data.Foldable.toList parens
    go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(')
    go (')':xs) [] (null -> True) = go xs [] (fromList "()")
    go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(')
    go (')':xs) [] parens = go xs [] corrected
      where corrected = ('(' <| parens) |> ')'
    go (')':xs) (RP:debit) parens = go xs debit (parens |> ')')
    go (_:xs) debit parens = go xs debit parens
    go [] (RP:debit) parens = go [] debit (parens |> ')')

example:

balanceParens "))("
"(())()"
balanceParens ")))"
"((()))"

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

David Turner-2
Hi Michael,

Are there any strange constraints on the problem, such as the input string being 10s of GB long, or any particular correction strategy being required? Your code seems to add some parens to the start/end of the entire string to balance it, whereas I think I might have balanced "))(" to "()()()" given free reign. Is the goal efficiency or clarity or something else?

From personal taste, I would recommend including a suite of automated tests alongside your implementation even if it is not explicitly requested. A quickcheck test asserting that the output is always balanced and that the input string is a substring of the output might be appropriate.




On 21 March 2017 at 16:53, Michael Litchard <[hidden email]> wrote:

I'm prepping for a coding interview, and am examining the task of correcting unbalanced parentheses. The finger tree seems to be the right data structure. As a proof of concept I've used Data.Sequence to test my idea. If this is the right direction to go, I'll write more specialized finger tree code. The code works on the few test cases I have tried. Feedback appreciated.

{-# LANGUAGE ViewPatterns #-}
module Parenthesis where
import BasicPrelude hiding (concat,null,empty)

import Data.Sequence hiding (length)
import Data.Foldable hiding (length,null)

balanceParens :: String -> String
balanceParens str = go str [] empty
  where
    go [] [] (null -> True) = []
    go [] [] parens = Data.Foldable.toList parens
    go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(')
    go (')':xs) [] (null -> True) = go xs [] (fromList "()")
    go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(')
    go (')':xs) [] parens = go xs [] corrected
      where corrected = ('(' <| parens) |> ')'
    go (')':xs) (RP:debit) parens = go xs debit (parens |> ')')
    go (_:xs) debit parens = go xs debit parens
    go [] (RP:debit) parens = go [] debit (parens |> ')')

example:

balanceParens "))("
"(())()"
balanceParens ")))"
"((()))"

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

David McBride
In reply to this post by Michael Litchard-2
Whether your algorithm is correct depends on how you are supposed to
rebalance them.  My naive attempt gives very different results.

bal :: String -> String
bal = go 0
  where
    go :: Int -> String -> String
    go 0 "" = ""
    go n "" = replicate n ')'
    go n ('(':xs) = '(' : (go (n + 1) xs)
    go 0 (')':xs) = '(' : ')' : (go 0 xs)
    go n (')':xs) = ')' : (go (n - 1) xs)

bal "))("
"()()()"

bal ")))"
"()()()"

On Tue, Mar 21, 2017 at 12:53 PM, Michael Litchard
<[hidden email]> wrote:

> I'm prepping for a coding interview, and am examining the task of correcting
> unbalanced parentheses. The finger tree seems to be the right data
> structure. As a proof of concept I've used Data.Sequence to test my idea. If
> this is the right direction to go, I'll write more specialized finger tree
> code. The code works on the few test cases I have tried. Feedback
> appreciated.
>
> {-# LANGUAGE ViewPatterns #-}
> module Parenthesis where
> import BasicPrelude hiding (concat,null,empty)
>
> import Data.Sequence hiding (length)
> import Data.Foldable hiding (length,null)
>
> balanceParens :: String -> String
> balanceParens str = go str [] empty
>   where
>     go [] [] (null -> True) = []
>     go [] [] parens = Data.Foldable.toList parens
>     go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(')
>     go (')':xs) [] (null -> True) = go xs [] (fromList "()")
>     go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(')
>     go (')':xs) [] parens = go xs [] corrected
>       where corrected = ('(' <| parens) |> ')'
>     go (')':xs) (RP:debit) parens = go xs debit (parens |> ')')
>     go (_:xs) debit parens = go xs debit parens
>     go [] (RP:debit) parens = go [] debit (parens |> ')')
>
> example:
>
> balanceParens "))("
> "(())()"
> balanceParens ")))"
> "((()))"
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

David Turner-2
My attempt to replicate the OP's strategy but not impl:

balanceParens :: String -> String
balanceParens s =  replicate neededOpening '('
           ++ s ++ replicate neededClosing ')'
  where
  depthChange '(' = 1
  depthChange ')' = -1
  depthChange _   = 0

  depths = scanl (+) 0 $ map depthChange s
  neededOpening = negate $ minimum depths
  neededClosing =          last    depths + neededOpening



On 21 March 2017 at 17:16, David McBride <[hidden email]> wrote:
Whether your algorithm is correct depends on how you are supposed to
rebalance them.  My naive attempt gives very different results.

bal :: String -> String
bal = go 0
  where
    go :: Int -> String -> String
    go 0 "" = ""
    go n "" = replicate n ')'
    go n ('(':xs) = '(' : (go (n + 1) xs)
    go 0 (')':xs) = '(' : ')' : (go 0 xs)
    go n (')':xs) = ')' : (go (n - 1) xs)

bal "))("
"()()()"

bal ")))"
"()()()"

On Tue, Mar 21, 2017 at 12:53 PM, Michael Litchard
<[hidden email]> wrote:
> I'm prepping for a coding interview, and am examining the task of correcting
> unbalanced parentheses. The finger tree seems to be the right data
> structure. As a proof of concept I've used Data.Sequence to test my idea. If
> this is the right direction to go, I'll write more specialized finger tree
> code. The code works on the few test cases I have tried. Feedback
> appreciated.
>
> {-# LANGUAGE ViewPatterns #-}
> module Parenthesis where
> import BasicPrelude hiding (concat,null,empty)
>
> import Data.Sequence hiding (length)
> import Data.Foldable hiding (length,null)
>
> balanceParens :: String -> String
> balanceParens str = go str [] empty
>   where
>     go [] [] (null -> True) = []
>     go [] [] parens = Data.Foldable.toList parens
>     go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(')
>     go (')':xs) [] (null -> True) = go xs [] (fromList "()")
>     go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(')
>     go (')':xs) [] parens = go xs [] corrected
>       where corrected = ('(' <| parens) |> ')'
>     go (')':xs) (RP:debit) parens = go xs debit (parens |> ')')
>     go (_:xs) debit parens = go xs debit parens
>     go [] (RP:debit) parens = go [] debit (parens |> ')')
>
> example:
>
> balanceParens "))("
> "(())()"
> balanceParens ")))"
> "((()))"
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

Michael Orlitzky
In reply to this post by David McBride
On 03/21/2017 01:16 PM, David McBride wrote:
> Whether your algorithm is correct depends on how you are supposed to
> rebalance them.  My naive attempt gives very different results.
>

You guys are trying to hard. Here's an algorithm that meets the stated
requirements:

   balance _ = ""


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

Michael Litchard-2
In reply to this post by David Turner-2
I got this idea from looking at glassdoor comments of previous interviewees. The spec was vague, but I imagined that the requirement would need to be efficient and keep contiguous parenthesis unaltered.
so
balanceParens ")))" == "()()()" would be incorrect.



On Tue, Mar 21, 2017 at 10:20 AM, David Turner <[hidden email]> wrote:
My attempt to replicate the OP's strategy but not impl:

balanceParens :: String -> String
balanceParens s =  replicate neededOpening '('
           ++ s ++ replicate neededClosing ')'
  where
  depthChange '(' = 1
  depthChange ')' = -1
  depthChange _   = 0

  depths = scanl (+) 0 $ map depthChange s
  neededOpening = negate $ minimum depths
  neededClosing =          last    depths + neededOpening



On 21 March 2017 at 17:16, David McBride <[hidden email]> wrote:
Whether your algorithm is correct depends on how you are supposed to
rebalance them.  My naive attempt gives very different results.

bal :: String -> String
bal = go 0
  where
    go :: Int -> String -> String
    go 0 "" = ""
    go n "" = replicate n ')'
    go n ('(':xs) = '(' : (go (n + 1) xs)
    go 0 (')':xs) = '(' : ')' : (go 0 xs)
    go n (')':xs) = ')' : (go (n - 1) xs)

bal "))("
"()()()"

bal ")))"
"()()()"

On Tue, Mar 21, 2017 at 12:53 PM, Michael Litchard
<[hidden email]> wrote:
> I'm prepping for a coding interview, and am examining the task of correcting
> unbalanced parentheses. The finger tree seems to be the right data
> structure. As a proof of concept I've used Data.Sequence to test my idea. If
> this is the right direction to go, I'll write more specialized finger tree
> code. The code works on the few test cases I have tried. Feedback
> appreciated.
>
> {-# LANGUAGE ViewPatterns #-}
> module Parenthesis where
> import BasicPrelude hiding (concat,null,empty)
>
> import Data.Sequence hiding (length)
> import Data.Foldable hiding (length,null)
>
> balanceParens :: String -> String
> balanceParens str = go str [] empty
>   where
>     go [] [] (null -> True) = []
>     go [] [] parens = Data.Foldable.toList parens
>     go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(')
>     go (')':xs) [] (null -> True) = go xs [] (fromList "()")
>     go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(')
>     go (')':xs) [] parens = go xs [] corrected
>       where corrected = ('(' <| parens) |> ')'
>     go (')':xs) (RP:debit) parens = go xs debit (parens |> ')')
>     go (_:xs) debit parens = go xs debit parens
>     go [] (RP:debit) parens = go [] debit (parens |> ')')
>
> example:
>
> balanceParens "))("
> "(())()"
> balanceParens ")))"
> "((()))"
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.



_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

MarLinn
In reply to this post by Michael Litchard-2

Hi Michael,

I think you're making your own task harder than necessary. For one thing, -XViewPatterns is nice, but in this case they hide some of the structure. Most importantly, they hide that all the special null-cases are actually unnecessary because the normal cases already cover them. I would further advise to use layout to reveal even more structure. That's especially useful when you later convert the explicit recursion into a fold.

But even then, on a different level you're still working too hard: You're parsing the string and building/correcting the tree in one step. Why not create the tree, convert the tree, and then read out the tree in three steps? It's still the same complexity class but much easier to write and read. And once you are free to think of the tree manipulations on their own it might help recognize optimizations like those the solutions of other commenters use.

That's not to say your modifications are useless. But the exploratory phase seems too early to apply them.

Cheers,
MarLinn

On 2017-03-21 17:53, Michael Litchard wrote:

I'm prepping for a coding interview, and am examining the task of correcting unbalanced parentheses. The finger tree seems to be the right data structure. As a proof of concept I've used Data.Sequence to test my idea. If this is the right direction to go, I'll write more specialized finger tree code. The code works on the few test cases I have tried. Feedback appreciated.

{-# LANGUAGE ViewPatterns #-}
module Parenthesis where
import BasicPrelude hiding (concat,null,empty)

import Data.Sequence hiding (length)
import Data.Foldable hiding (length,null)

balanceParens :: String -> String
balanceParens str = go str [] empty
  where
    go [] [] (null -> True) = []
    go [] [] parens = Data.Foldable.toList parens
    go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(')
    go (')':xs) [] (null -> True) = go xs [] (fromList "()")
    go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(')
    go (')':xs) [] parens = go xs [] corrected
      where corrected = ('(' <| parens) |> ')'
    go (')':xs) (RP:debit) parens = go xs debit (parens |> ')')
    go (_:xs) debit parens = go xs debit parens
    go [] (RP:debit) parens = go [] debit (parens |> ')')

example:

balanceParens "))("
"(())()"
balanceParens ")))"
"((()))"


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

David Turner-2
In reply to this post by Michael Litchard-2
... or it could be a ploy to see how you deal with incomplete or vague specs; how you ask clarifying questions etc.

Adding sufficiently many opening parens at the start can't obviously be done without traversing the whole input first, whereas adding them as you discover excesses of closing parens is possible to implement in a streaming fashion, i.e. with O(1) memory usage and only traversing the input once.

On 21 Mar 2017 17:44, "Michael Litchard" <[hidden email]> wrote:
I got this idea from looking at glassdoor comments of previous interviewees. The spec was vague, but I imagined that the requirement would need to be efficient and keep contiguous parenthesis unaltered.
so
balanceParens ")))" == "()()()" would be incorrect.



On Tue, Mar 21, 2017 at 10:20 AM, David Turner <[hidden email]> wrote:
My attempt to replicate the OP's strategy but not impl:

balanceParens :: String -> String
balanceParens s =  replicate neededOpening '('
           ++ s ++ replicate neededClosing ')'
  where
  depthChange '(' = 1
  depthChange ')' = -1
  depthChange _   = 0

  depths = scanl (+) 0 $ map depthChange s
  neededOpening = negate $ minimum depths
  neededClosing =          last    depths + neededOpening



On 21 March 2017 at 17:16, David McBride <[hidden email]> wrote:
Whether your algorithm is correct depends on how you are supposed to
rebalance them.  My naive attempt gives very different results.

bal :: String -> String
bal = go 0
  where
    go :: Int -> String -> String
    go 0 "" = ""
    go n "" = replicate n ')'
    go n ('(':xs) = '(' : (go (n + 1) xs)
    go 0 (')':xs) = '(' : ')' : (go 0 xs)
    go n (')':xs) = ')' : (go (n - 1) xs)

bal "))("
"()()()"

bal ")))"
"()()()"

On Tue, Mar 21, 2017 at 12:53 PM, Michael Litchard
<[hidden email]> wrote:
> I'm prepping for a coding interview, and am examining the task of correcting
> unbalanced parentheses. The finger tree seems to be the right data
> structure. As a proof of concept I've used Data.Sequence to test my idea. If
> this is the right direction to go, I'll write more specialized finger tree
> code. The code works on the few test cases I have tried. Feedback
> appreciated.
>
> {-# LANGUAGE ViewPatterns #-}
> module Parenthesis where
> import BasicPrelude hiding (concat,null,empty)
>
> import Data.Sequence hiding (length)
> import Data.Foldable hiding (length,null)
>
> balanceParens :: String -> String
> balanceParens str = go str [] empty
>   where
>     go [] [] (null -> True) = []
>     go [] [] parens = Data.Foldable.toList parens
>     go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(')
>     go (')':xs) [] (null -> True) = go xs [] (fromList "()")
>     go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(')
>     go (')':xs) [] parens = go xs [] corrected
>       where corrected = ('(' <| parens) |> ')'
>     go (')':xs) (RP:debit) parens = go xs debit (parens |> ')')
>     go (_:xs) debit parens = go xs debit parens
>     go [] (RP:debit) parens = go [] debit (parens |> ')')
>
> example:
>
> balanceParens "))("
> "(())()"
> balanceParens ")))"
> "((()))"
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.




_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

Michael Litchard-2
David,

Am I mistaken in believing the code I have in both O(1) in time and space?
I'm certain that my use of Data.Sequence, and therefore finger trees, has this code at O(1) time.
Doesn't using a lazy list mean I am using O(1) space? Or, would I have to use the conduits or pipes library?

On Tue, Mar 21, 2017 at 10:52 AM, David Turner <[hidden email]> wrote:
... or it could be a ploy to see how you deal with incomplete or vague specs; how you ask clarifying questions etc.

Adding sufficiently many opening parens at the start can't obviously be done without traversing the whole input first, whereas adding them as you discover excesses of closing parens is possible to implement in a streaming fashion, i.e. with O(1) memory usage and only traversing the input once.

On 21 Mar 2017 17:44, "Michael Litchard" <[hidden email]> wrote:
I got this idea from looking at glassdoor comments of previous interviewees. The spec was vague, but I imagined that the requirement would need to be efficient and keep contiguous parenthesis unaltered.
so
balanceParens ")))" == "()()()" would be incorrect.



On Tue, Mar 21, 2017 at 10:20 AM, David Turner <[hidden email]> wrote:
My attempt to replicate the OP's strategy but not impl:

balanceParens :: String -> String
balanceParens s =  replicate neededOpening '('
           ++ s ++ replicate neededClosing ')'
  where
  depthChange '(' = 1
  depthChange ')' = -1
  depthChange _   = 0

  depths = scanl (+) 0 $ map depthChange s
  neededOpening = negate $ minimum depths
  neededClosing =          last    depths + neededOpening



On 21 March 2017 at 17:16, David McBride <[hidden email]> wrote:
Whether your algorithm is correct depends on how you are supposed to
rebalance them.  My naive attempt gives very different results.

bal :: String -> String
bal = go 0
  where
    go :: Int -> String -> String
    go 0 "" = ""
    go n "" = replicate n ')'
    go n ('(':xs) = '(' : (go (n + 1) xs)
    go 0 (')':xs) = '(' : ')' : (go 0 xs)
    go n (')':xs) = ')' : (go (n - 1) xs)

bal "))("
"()()()"

bal ")))"
"()()()"

On Tue, Mar 21, 2017 at 12:53 PM, Michael Litchard
<[hidden email]> wrote:
> I'm prepping for a coding interview, and am examining the task of correcting
> unbalanced parentheses. The finger tree seems to be the right data
> structure. As a proof of concept I've used Data.Sequence to test my idea. If
> this is the right direction to go, I'll write more specialized finger tree
> code. The code works on the few test cases I have tried. Feedback
> appreciated.
>
> {-# LANGUAGE ViewPatterns #-}
> module Parenthesis where
> import BasicPrelude hiding (concat,null,empty)
>
> import Data.Sequence hiding (length)
> import Data.Foldable hiding (length,null)
>
> balanceParens :: String -> String
> balanceParens str = go str [] empty
>   where
>     go [] [] (null -> True) = []
>     go [] [] parens = Data.Foldable.toList parens
>     go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(')
>     go (')':xs) [] (null -> True) = go xs [] (fromList "()")
>     go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(')
>     go (')':xs) [] parens = go xs [] corrected
>       where corrected = ('(' <| parens) |> ')'
>     go (')':xs) (RP:debit) parens = go xs debit (parens |> ')')
>     go (_:xs) debit parens = go xs debit parens
>     go [] (RP:debit) parens = go [] debit (parens |> ')')
>
> example:
>
> balanceParens "))("
> "(())()"
> balanceParens ")))"
> "((()))"
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.





_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

David Turner-2
It can't be done in better than O(n) time as you have to look at the whole input.

I think you must be using O(n) space too. Consider a string of the form "()()()()...()())": You know the output starts with a '(' but you cannot know the second character of the output until you have read all the way to the end of the string and found the final character is unmatched.

On 21 Mar 2017 18:04, "Michael Litchard" <[hidden email]> wrote:
David,

Am I mistaken in believing the code I have in both O(1) in time and space?
I'm certain that my use of Data.Sequence, and therefore finger trees, has this code at O(1) time.
Doesn't using a lazy list mean I am using O(1) space? Or, would I have to use the conduits or pipes library?

On Tue, Mar 21, 2017 at 10:52 AM, David Turner <[hidden email]> wrote:
... or it could be a ploy to see how you deal with incomplete or vague specs; how you ask clarifying questions etc.

Adding sufficiently many opening parens at the start can't obviously be done without traversing the whole input first, whereas adding them as you discover excesses of closing parens is possible to implement in a streaming fashion, i.e. with O(1) memory usage and only traversing the input once.

On 21 Mar 2017 17:44, "Michael Litchard" <[hidden email]> wrote:
I got this idea from looking at glassdoor comments of previous interviewees. The spec was vague, but I imagined that the requirement would need to be efficient and keep contiguous parenthesis unaltered.
so
balanceParens ")))" == "()()()" would be incorrect.



On Tue, Mar 21, 2017 at 10:20 AM, David Turner <[hidden email]> wrote:
My attempt to replicate the OP's strategy but not impl:

balanceParens :: String -> String
balanceParens s =  replicate neededOpening '('
           ++ s ++ replicate neededClosing ')'
  where
  depthChange '(' = 1
  depthChange ')' = -1
  depthChange _   = 0

  depths = scanl (+) 0 $ map depthChange s
  neededOpening = negate $ minimum depths
  neededClosing =          last    depths + neededOpening



On 21 March 2017 at 17:16, David McBride <[hidden email]> wrote:
Whether your algorithm is correct depends on how you are supposed to
rebalance them.  My naive attempt gives very different results.

bal :: String -> String
bal = go 0
  where
    go :: Int -> String -> String
    go 0 "" = ""
    go n "" = replicate n ')'
    go n ('(':xs) = '(' : (go (n + 1) xs)
    go 0 (')':xs) = '(' : ')' : (go 0 xs)
    go n (')':xs) = ')' : (go (n - 1) xs)

bal "))("
"()()()"

bal ")))"
"()()()"

On Tue, Mar 21, 2017 at 12:53 PM, Michael Litchard
<[hidden email]> wrote:
> I'm prepping for a coding interview, and am examining the task of correcting
> unbalanced parentheses. The finger tree seems to be the right data
> structure. As a proof of concept I've used Data.Sequence to test my idea. If
> this is the right direction to go, I'll write more specialized finger tree
> code. The code works on the few test cases I have tried. Feedback
> appreciated.
>
> {-# LANGUAGE ViewPatterns #-}
> module Parenthesis where
> import BasicPrelude hiding (concat,null,empty)
>
> import Data.Sequence hiding (length)
> import Data.Foldable hiding (length,null)
>
> balanceParens :: String -> String
> balanceParens str = go str [] empty
>   where
>     go [] [] (null -> True) = []
>     go [] [] parens = Data.Foldable.toList parens
>     go ('(':xs) [] (null -> True) = go xs [RP] (singleton '(')
>     go (')':xs) [] (null -> True) = go xs [] (fromList "()")
>     go ('(':xs) debit parens = go xs (RP:debit) (parens |> '(')
>     go (')':xs) [] parens = go xs [] corrected
>       where corrected = ('(' <| parens) |> ')'
>     go (')':xs) (RP:debit) parens = go xs debit (parens |> ')')
>     go (_:xs) debit parens = go xs debit parens
>     go [] (RP:debit) parens = go [] debit (parens |> ')')
>
> example:
>
> balanceParens "))("
> "(())()"
> balanceParens ")))"
> "((()))"
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.





_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

Richard A. O'Keefe
In reply to this post by Michael Litchard-2

On 22/03/2017, at 5:53 AM, Michael Litchard <[hidden email]> wrote:

I'm prepping for a coding interview, and am examining the task of correcting unbalanced parentheses.

Where is that task specified?

Back when the CWI in Amsterdam were working on an Algol 68
compiler, they had a technical report that looked at bracket
repair.  They had to deal with multiple kinds of brackets:
(-) [-] begin-end if-fi do-od case-esac.  It sounds as though
you don't have that problem, but it's still not clear what
you are supposed to do.  Given
 "(()"
is the correction "(())" or "()" or something else?  Given
 ")"
is the correction "() or ""?  How do you decide?

The finger tree seems to be the right  data structure.

Why?

Suppose we adopt the rules
- right parenthesis with no matching left: insert one
- n left parentheses with no match at the end: insert n rights

repair :: String -> String
repair ps = loop ps 0
 where loop []       n = map (\_ -> ')') [1..n]
       loop ('(':ps) n = '('   : loop ps (n+1)
       loop (')':ps) 0 = "()" ++ loop ps 0
       loop (')':ps) n = ')'   : loop ps (n-1)
       loop (x  :ps) n = x     : loop ps n

*Main> repair "(()"
"(())"
*Main> repair ")"
"()"
*Main> repair "))("
"()()()"                -- you want (())()
*Main> repair ")))"
"()()()"                -- you want ((()))

A rule of the form
 given a block of R ")" characters
 when the "(" stack is L deep:
 insert max(R-L,0) "(" characters
 copy the block of R ")" characters
 the "(" stack is now max(L-R,0) deep.
would produce the output you show without requiring any
complex data structure.

So what _is_ the specification?


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

Richard A. O'Keefe
In reply to this post by Michael Litchard-2

> On 22/03/2017, at 6:44 AM, Michael Litchard <[hidden email]> wrote:
>
> I got this idea from looking at glassdoor comments of previous interviewees. The spec was vague, but I imagined that the requirement would need to be efficient and keep contiguous parenthesis unaltered.
> so
> balanceParens ")))" == "()()()" would be incorrect.

One parenthesIs two parenthesEs.

Perhaps you could link to those glassdoor comments?

It really is not obvious to me that "keep[ing] contiguous
parenthes[e]s unaltered" even makes sense, let alone
being desirable.  Entirely by coincidence, I had a
parenthesis problem about an hour ago, where I had changed
   fabs(X-(k-1))
to
   fabs(d))
and the right repair was to delete one of the right parentheses.

The point of the question may well be not the code you
come up with but the questions you ask on your way.

I'd probably ask questions like these:
 1. Do you have a precise specification?
 2. Are you looking for an obviously correct solution,
    a solution with small workspace, a fast solution, or what?
 3. What operations am I allowed to perform on a string?
    Which characters may I insert?
    Which characters may I delete?
    Is transposition of adjacent characters allowed?
 4. Are you looking for a repair of minimal cost in some
    sense?  If so, how is that cost computed?
    For example, inserting ( might cost 2 units and
    deleting ) might cost 3 units.
 5. There's been a lot of work done on least cost syntax
    repair (e.g., Roland Backhouse).
    Am I allowed to look that up?
 


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

Richard A. O'Keefe
In reply to this post by Michael Litchard-2
I note that Ying's thesis on repairing bracket structure in XML
is a cubic time algorithm.  It's not immediately obvious to me
that an algorithm computing "optimal" repairs for bracket structures
can be faster than quadratic time.  Everything hinges on what the
requirements actually are.

space?
> I'm certain that my use of Data.Sequence, and therefore finger trees, has this code at O(1) time.
> Doesn't using a lazy list mean I am using O(1) space?

If the input has m characters and the output has n characters,
the algorithm MUST take at least O(m+n) time.

Two people have independently proposed basically the same
streaming algorithm taking O(m+n) time and O(1) space with
lazy Strings, and one of them proposed an algorithm that
would reproduce the few test cases you provided, still with
O(m+n) time and O(1) space, without finger or any other trees.

Negotiating the specification comes first.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Code Review Request - Unbalanced Parenthesis correction

Andreas Abel-2
In reply to this post by Michael Orlitzky
 >   balance _ = ""
Haha!

The other trivial solution simply replaces each parenthesis by "()":

   balance = concatMap $ const "()"

balance "))(" then returns "()()()".

This achieves that the balanced string is a superstring of the original
string.  (Not a minimal one.)

On 21.03.2017 18:23, Michael Orlitzky wrote:
> On 03/21/2017 01:16 PM, David McBride wrote:
>> Whether your algorithm is correct depends on how you are supposed to
>> rebalance them.  My naive attempt gives very different results.
>>
>
> You guys are trying to hard. Here's an algorithm that meets the stated
> requirements:
>
>   balance _ = ""
--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www.cse.chalmers.se/~abela/
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.