Previous market:
Here's how it works:
You're given the string "?<????????????)??]???????}??"
The task is to find the number of ways to replace each question mark with one of the characters in the string "()<>[]{}" such that the end result is valid parentheses sequence.
For example:
()[]{}<> is valid
([]()){} is valid
]() is not valid
(]{} is not valid
([)) is not valid.
Here are some test cases:
?[?? has 4 completions.
???? has 32 completions.
)??? has 0 complteions.
More formally validity is defined by:
The empty string is valid.
If a string S is valid then a+S+b is valid where "+" is string concatenation. And a,b are open/close brackets of identical type.
If S_1 and S_2 are valid bracket strings then S_1 + S_2 is a valid bracket string.
Market resolves YES if anyone posts the answer in the comments or NO if market closes before that.
Market closes 7th of april.
1,000🏅 Top traders
| # | Name | Total profit |
|---|---|---|
| 1 | Ṁ87 | |
| 2 | Ṁ61 | |
| 3 | Ṁ6 | |
| 4 | Ṁ4 | |
| 5 | Ṁ1 |
360217313280
I programmed it in the Lean 4 Programming Language, it was a fun little exercise. Here is the code: https://gist.github.com/fpvandoorn/872ab3d3841cab977ee109b29f97e834
I tested it on various smaller problems.
@FlorisvanDoorn this matches what I got this morning :) Was planning on double checking my code when I had a chance.
@FlorisvanDoorn nice, what is the time complexity of this, and how long did it take you to run it?
@levifinkelstein
Here's mine: https://pastebin.com/ZLDUSn3G
Took roughly 10 minutes to run, time complexity should is O(n * 4^0.5n) I believe? I think there's probably some optimization available with checking only a generic "open" bracket in the recursive step and multiplying the result by 4? But this worked so I didn't think too hard about it.
@levifinkelstein I actually recorded the number of recursive calls that were made, the recursive tree had 1137346618 nodes.
@levifinkelstein It takes about 1.3s to run and 1965040 small memory allocations.
It scales exponentially with the number of question marks, a factor of 3-4 more every time you add two more question marks.
It can definitely be optimized further.
Oh, you'll actually have to do something smart here, since the solution for 28 question marks is
```
C_14 x 4^14 = 717914520944640 ≈ 7 x 10^14
```
where C_n is the n-th Catalan number (seriously? I cannot write two times "*" in a code snippet without turning a part italic?)
The answer will be roughly 7 x 10^14 / 8^4 = 1.7 x 10^11, by assuming that the 4 given symbols could have been any of the 8 symbols with equal probability, independently, but that will of course not be exactly correct.
I was curious if GPT-4 could solve this so I tried it, this was the result (I specifically asked it to write in Python):
```
def valid_parentheses_count(s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1, 2):
for start in range(n - length + 1):
end = start + length - 1
if s[start] in ")]}>":
continue
for k in range(start, end, 2):
open_bracket = s[start]
close_bracket = {'(': ')', '[': ']', '{': '}', '<': '>'}[open_bracket]
if s[k + 1] == '?' or s[k + 1] == close_bracket:
open_count = 1 if open_bracket == '?' else 2
dp[start][end] += open_count (dp[start + 1][k] if k > start else 1) (dp[k + 2][end] if k + 2 <= end else 1)
return dp[0][n - 1]
# Test cases
print(valid_parentheses_count("?[??")) # Output: 4
print(valid_parentheses_count("????")) # Output: 32
print(valid_parentheses_count(")???")) # Output: 0
print(valid_parentheses_count("?<????????????)??]???????}??")) # Output: 3528
```
It quickly errors out with a key error. Its approach... vaguely resembles something that would work, but I can't follow the logic and I think it's largely nonsensical in the details. I don't think memoizing on substrings works here in general either but might be missing how one would make that technique work.