[Personal project] AlgeZip: navigate and manipulate boolean expressions (github.com)

submitted 5 months ago by shape-warrior-t@kbin.social to c/programming@programming.dev

0 comments fedilink

For some time now, I've been thinking about the concept of interactively manipulating mathematical expressions and equations via software. Like doing some quick algebra in Notepad or similar, except there's no potential for arithmetic/algebra errors, typos, etc. ruining any results.

At the same time, I also wanted to experiment a bit with zippers from functional programming. You need some way of specifying what (sub)expression to perform operations on, and it seemed like this kind of data structure could help with that.

And so, I made AlgeZip, a small proof-of-concept of the whole general idea. Although this polished Python version was completed only a few days ago, there were various other versions before this one in different languages and with worse-quality code. Instructions for things are on GitHub; requires Python 3.12 to run.

For simplicity, I decided to use boolean expressions instead of generic numeric algebraic expressions/equations, and only decided to include the minimum in terms of commands and functionality. From my understanding, it should be possible to transform any boolean expression into any other boolean expression in AlgeZip (without using the r! command except to set things up), though I could be wrong.

Thoughts, comments, and criticism on the idea as a whole, the program, or the source code are welcome, though I'm not sure if I'll be making any changes at this time.

[Easy] Bracket Simplification by shape-warrior-t in c/challenges@programming.dev

[-] shape-warrior-t@kbin.social 1 points 1 year ago

Here's an O(n) solution using a stack instead of repeated search & replace:

closing_to_opening = {')': '(', ']': '[', '}': '{'}
brackets = input()
acc = []
for bracket in brackets:
    if bracket in closing_to_opening:
        if acc and acc[-1] == closing_to_opening[bracket]:
            acc.pop()
        else:
            acc.append(bracket)
    else:
        acc.append(bracket)
print(''.join(acc))

Haven't thoroughly thought the problem through (so I'm not 100% confident in the correctness of the solution), but the general intuition here is that pairs of brackets can only match up if they only have other matching pairs of brackets between them. You can deal with matching pairs of brackets on the fly simply by removing them, so there's actually no need for backtracking.

Golfed, just for fun:

a=[]
[a.pop()if a and a[-1]==dict(zip(')]}','([{')).get(b)else a.append(b)for b in input()]
print(''.join(a))

shape-warrior-t

joined 1 year ago