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