Parentheses Puzzle

Over my spring break, I've been trying to get more into network security. One amazing resource I've found for an introduction to hacking is a website called picoCTF. It's a CTF (Capture The Flag), which is a collection of hacking exercises. Originally it was a competition, but it's now open to anybody signing up.

IF YOU DON'T WANT SPOILERS, DON'T READ THIS ARTICLE!

One of the later problems in this competition is as follows:

Can you understand the language and answer the questions to retrieve the flag? Connect to the service with nc 2018shell.picoctf.com 8672

I connected to the server using netcat as directed. Upon connecting, I got the following prompt:

Rules:
() + () = ()()                                      => [combine]
((())) + () = ((())())                              => [absorb-right]
() + ((())) = (()(()))                              => [absorb-left]
(())(()) + () = (())(()())                          => [combined-absorb-right]
() + (())(()) = (()())(())                          => [combined-absorb-left]
(())(()) + ((())) = ((())(())(()))                  => [absorb-combined-right]
((())) + (())(()) = ((())(())(()))                  => [absorb-combined-left]
() + (()) + ((())) = (()()) + ((())) = ((()())(())) => [left-associative]

Example:
(()) + () = () + (()) = (()())

Let's start with a warmup.
(()(())) + (()) = ???

>

As a Lisp developer, I felt that I needed to solve this problem. I was a little frustrated that it wasn't really a formal set of rules (rather, a collection of examples). Additionally, looking through messes of tiny parentheses makes it near impossible to debug large output.

Initially, I assumed that the only thing affecting how an addition operation was performed was whether one (or both) of the operations was (). For example, in this expression:

(()) + () => (() [()] ) => (()())

The () gets absorbed on the right. Likewise,

() + ((()()())) => ( [()] (()()())) => (()(()()()))

When both arguments are (), we apply the [combine] rule:

() + () => ()()

This was pretty simple to implement. I wrote the following Lime code for the operations:

(function combine (str1:str str2:str) -> str
          (sjoin str1 str2))

(function absorb_left (str1:str str2:str) -> str
          (sjoin "(" (sjoin
              str1
              (sslice str2 1)))))

(function absorb_right (str1:str str2:str) -> str
          (sjoin (sjoin
                 (sslice str1 0 (isub (slength str1) 1))
                 str2) ")")

My rules were working, when I encountered this example:

()() + () = ()()()

According to my rules, the result should be ()(()). However, this isn't the case. I then thought that the importance was in adjacent parentheses, i.e.:

...() + ()... = ...()()...

However, this only worked about 50% of the time. Getting frustrated, I googled the problem and found a great clue from Redditor u/hielkew:

So, the rule I found was that absorption takes place by the element that has the largest parenthesis depth. For #6 for example (())(()) goes only 2 deep and ((())) goes 3 deep, so the latter will absorb the former.

This rule matches all of my earlier rules. To check max parenthese depth, I wrote a simple recursive Lime function:

(function max_depth_ (str:str depth:int current_max:int) -> int
          (if (sequal str "")
              current_max
              (if (sequal (sslice str 0 1) "(")
                  (max_depth_ (sslice str 1) (iadd depth 1) current_max)
                  (if (sequal (sslice str 0 1) ")")
                      (if (igreater depth current_max)
                          (max_depth_ (sslice str 1) (isub depth 1) depth)
                          (max_depth_ (sslice str 1) (isub depth 1) current_max))
                      -1))))

(function max_depth (str:str) -> int
          (max_depth_ str 0 0))

Wrapping it all up, here's the final Lime program.

(function combine (str1:str str2:str) -> str
          (sjoin str1 str2))

(function absorb_left (str1:str str2:str) -> str
          (sjoin "(" (sjoin
                 str1
                 (sslice str2 1))))

(function absorb_right (str1:str str2:str) -> str
          (sjoin (sjoin
                 (sslice str1 0 (isub (slength str1) 1))
                 str2) ")"))

(function max_depth_ (str:str depth:int current_max:int) -> int
          (if (sequal str "")
              current_max
              (if (sequal (sslice str 0 1) "(")
                  (max_depth_ (sslice str 1) (iadd depth 1) current_max)
                  (if (sequal (sslice str 0 1) ")")
                      (if (igreater depth current_max)
                          (max_depth_ (sslice str 1) (isub depth 1) depth)
                          (max_depth_ (sslice str 1) (isub depth 1) current_max))
                      -1))))

(function max_depth (str:str) -> int
          (max_depth_ str 0 0))

(function op (str1:str str2:str) -> str
          (if (igreater (max_depth str1) (max_depth str2))
              (absorb_right str1 str2)
              (if (igreater (max_depth str2) (max_depth str1))
                  (absorb_left str1 str2)
                  (combine str1 str2))))

(function compute (in:str) -> str (foldl op (ssplit in " + ")))
(function main () (sprint (compute "() + ()() +...")))

This article was written as of Lime 1.4.2. Code examples may not work in newer versions.