epnel algo
2021-10-05
Recently I had a technical interview for a junior positon with a following task: given a string, find the length of the longest substring without repeating characters. Fairly simple, but due to stress I wasn't able to properly solve it and completely failed the interview as a result. The problem and it's solutions are described here: https://www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/
To make up for that epic fail I decided to implement the solution in my own esoteric language that I wrote sometime in high-school - epnel. Below is a valid Python solution, adapted for easy translation.
inputs = ["abcabcbbc", "abcabcbbacbd", "ddabcdedd"]
for x in inputs:
d, b, r = dict(), 0, 0
for i, c in enumerate(x):
if c in d:
nb = d[c] + 1
if nb > b: b = nb
d[c] = i
nr = i - b + 1
if nr > r: r = nr
print(x, r)
You can find the epnel language on my GitLab: https://gitlab.com/wykwit/epnel
The curiosity that is epnel was also written in Python, but it doesn't provide much IO functionality. For that purpose, we can use the host language again.
import epnel
inputs = ["abcabcbbc", "abcabcbbacbd", "ddabcdedd"]
# convert input string to an integer for epnel to handle
convert_input = lambda x: int.from_bytes(bytes(x, "ascii"), "big")
# main epnel code
algorithm = """
= 0 {}
"""
# apply algorithm to each input
for x in inputs:
s = algorithm.format(convert_input(x))
p = epnel.Parser(string=s)
# and because we want to have a clean start
epnel.interpreter.symbol_table.clear()
r = epnel.interpret(p.root())
print(x, r)
Mind that it doesn't matter whether we traverse the string from the beggining or from the end - we should get the same result, therefore endianness in our conversion shouldn't matter. What we need now is an actual algorithm to plug into the code above. Let's start off with a simple example and translate the loop first.
All variables (previously undefined symbols) have a value of zero by default. Our sample input string translates to 1796423792463439880801, we can set it like this:
. in 1796423792463439880801
There are no indentation rules in epnel. Sometimes I myself am not sure what would make most sense. The only requirement is that all parameters should be separated with at least a single whitespace, everything else is up to the programmer. I try to make my examples clean, but it's perfectly fine to simply have everything in a single line.
Once we have a loop, we would want that loop to execute some body. For now we can simply count the number of iterations to make sure our loop works right.
, body . r + r 1 !
Now the actual loop would look something like this:
, loop
? > in 0
| . c & in 255
| body
| . i + i 1
| . in / in 256
| loop !
!
loop
We define a loop and call it in the last parameter of the definition. First statement we execue is a check on whether there is still some input to handle. This condition will end recursion. Then we assign current character to a variable and execute our body. Before we recursively call the loop again, we increment our loop counter and remove the character we've just looked at. Finally we finish the loop off with a couple of exclamation marks to fill remaining parameters with boolean false.
We can chain these three blocks with ampersands (binary and) and wrap with another binary or to get a clean result.
| & . in 1796423792463439880801
& , body . r + r 1 !
& , loop
? > in 0
| . c & in 255
| body
| . i + i 1
| . in / in 256
| loop !
!
loop
!
r
Save the file as loop.e and we get a following result when we run it.
$ epnel loop.e
9
Our input string consists of 9 characters, so this matches our expectations. Apparently the loop works.
We can now move on to translate the loop's body, which consists of a conditional statement and a few assignments. This is simple enough, but in our reference we are using a dictionary (hashmap) which doesn't have an obvious translation to epnel. Since we deal with characters that fit in one byte, we don't really need a dictionary (hashmap) - an array should suffice. Still, how do we solve this in epnel? We can use regular assignments and the (most confusing) epnel dereference operator. Assignments in epnel could overwrite numeric values and additionally confuse some code (which is awesome btw). Just to stay on the safe side, we can denote a variable to be our offset into negative numbers, which are not used in the algorithm.
For more details on assignments check out README in the epnel repo. Dereference is called "number reassignment". Play around with the REPL a little to figure out how exactly it works.
In the end - the body translates neatly.
, body
| ? = : + d c 0
!
| . nb + : + d c 1
? > nb b . b nb !
| . + d c i
| | . nr + - i b 1
? > nr r . r nr !
!
!
The final solution takes way more than 10 LOC and is more complex in practice, but theoreticaly the underlaying algorithm is also linear (and it looks cool).
import epnel
inputs = ["abcabcbbc", "abcabcbbacbd", "ddabcdedd"]
# convert input string to an integer for epnel to handle
convert_input = lambda x: int.from_bytes(bytes(x, "ascii"), "big")
# main epnel code
algorithm = """
| & | . in {}
| . d - ! 9999
!
& , body
| ? = : + d c 0
!
| . nb + : + d c 1
? > nb b . b nb !
| . + d c i
| | . nr + - i b 1
? > nr r . r nr !
!
!
& , loop
? > in 0
| . c & in 255
| body
| . i + i 1
| . in / in 256
| loop !
!
loop
!
r
"""
# apply algorithm to each input
for x in inputs:
s = algorithm.format(convert_input(x))
p = epnel.Parser(string=s)
# and because we want to have a clean start
epnel.interpreter.symbol_table.clear()
r = epnel.interpret(p.root())
print("{} : {}".format(x, r))
It looks even more cool when you get rid of indendation and rename variables that are too descriptive.
:) | & . x 1796423792463439880801 & . d - ! 9999 & , l ? > x 0 | . c & x 255 | | ? = : + d c 0 ! | . _b + : + d c 1 ? > _b b . b _b ! | . + d c i | ? > + - i b 1 r . r + - i b 1 ! ! | . i + i 1 | . x / x 256 | l ! ! l ! r
3
That's how problem-solving in epnel works. That is, if you can come up with the algorithm on time, of course.