|
I was making a state removal method that would turn a state machine into a regular expression.
In the process I needed to do a subtask, to wit, I needed to set up a quick and dirty finite automaton engine to hold the states.
Rather than make a bunch of objects/states that point to other objects/states using dictionaries, I simply stored all the dictionary transitions as a single tuple (int from, int to, string input) in a flat list.
The result is smaller, and allows me to do complicated queries on the relationships between the states (now represented as simple integers) very simply.
In fact, the result is so good, I may be able to rewrite a more compact and efficient state engine using this technique. And it was originally just intended to be "just enough of a thing" to be scaffolding for my overarching algorithm to work with.
I'm elated. Even if the overarching algorithm doesn't work, it means far more compact and efficient code potentially in terms of the finite automata code it works with.
Real programmers use butterflies
modified 23-Oct-21 14:03pm.
|
|
|
|
|
That reminds me of a third-party product a colleague was using.
It didn't support proper Order-of-Operations.
I said, "it's wrong", and he said, "but it's faaaasssst!"
|
|
|
|
|
Sometimes it doesn't have to be completely right to work for a situation. Honestly I respect code that does just enough to do the job for a particular application - very efficiently. It's to my mind, one of the higher achievements in code such that if you can pull it off regularly you are way more clever than I. I have to respect it. 
Real programmers use butterflies
|
|
|
|
|
You're a real innovator!
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Accidentally, so. I wish it was repeatable, but when I stumble on something, I'll take it.
Real programmers use butterflies
|
|
|
|
|
honey the codewitch wrote: Accidentally, so.
Penicillin was accidental too 
M.D.V.
If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?
Help me to understand what I'm saying, and I'll explain it better to you
Rating helpful answers is nice, but saying thanks can be even nicer.
|
|
|
|
|
honey the codewitch wrote: turn a state machine into a regular expression
That phrase is a bit odd. The way regular expressions work, depending on the match expression, is to create a state machine (and perhaps even more than one.)
|
|
|
|
|
This is doing the reverse of that.
Real programmers use butterflies
|
|
|
|
|
Yes but just want to be clear that although you are using a regular expression it will in fact end up using a state machine to implement that regular expression.
|
|
|
|
|
Yes, but specifically I'm talking about taking that state machine and turning it back into a regular expression.
Real programmers use butterflies
|
|
|
|
|
I like the state machine setup that is basically an abstract/pure virtual super class where each possible input is a method that returns the next state. Each state is a concrete class that must implement all of the input methods.
It would likely take up more memory with vtables than your approach, but I like that it makes the introduction of a new input a compile time check on all of the states. Same if you add a new state; you have to define transitions for every input.
I prefer compile time checks, but I work on a memory hog of a system where we have that luxury.😊
|
|
|
|
|
If you take a look at Reggie: A Non-Backtracking Streaming Regular Expression Code Generator[^] you'll see that since the state machines end up compiled, the input states are about as checked as they're going to get.
In this way you dictate the state machine specs, it then creates an in memory digraph of the states, which it then does some transformations on before compiling into code, at which point *everything* is compiled - in this case into goto tables - one label for each state. Although it can also generate a table/array based matcher
Because of how that works, your solution actually doesn't actually fit that particular application (and this is how i most often use them). Because it goes spec->state-machine->code, not spec->coded-state-machine
At least if I understand you.
Real programmers use butterflies
|
|
|
|
|
Whenever I let the blessing of my intelligence go to my head, as happens from time to time - which makes me foolish as a result - I try to solve Arden's Theorem in code. It's readily doable. It's proven possible. A CS major could do it over lunch. I've been trying for years.
I've also tried to implement an alternative algorithm. It's equally frustrating.
But it reminds me that I don't know everything, and certain things may remain beyond my reach.
Part of me hopes I never solve it. It's a wonderful lesson in humility.
Real programmers use butterflies
|
|
|
|
|
I thought you were going to say it's chow mein.
|
|
|
|
|
I like the Ardens in Belgium too 
|
|
|
|
|
I prefer the Ardennes.
Good paté.
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Ah, spelling error, all too common amongst developers
|
|
|
|
|
 Best smoked ham I ever had was in the Ardennes.
|
|
|
|
|
Ardens, Ardennes, smoked ham .... now my head hurts! 
Get me coffee and no one gets hurt!
|
|
|
|
|
|
You should probably pose the question to a butterfly 
Thar's only two possibilities: Thar is life out there in the universe which is smarter than we are, or we're the most intelligent life in the universe. Either way, it's a mighty sobering thought. (Porkypine - via Walt Kelly)
|
|
|
|
|
Interesting problem... I've never looked into it because there was no such thing when I was programming for a living. It seems that the Keene's algorithm is key to the solution. This is something worth investigating, as I love state machines, and they seem to have gone out of favor.
Will Rogers never met me.
|
|
|
|
|
Vexed - Epiphany[^]
Last week I was checking out my bookmarked album on Spotify and decided a lot had to go.
Vexed was on the nominee list, added them some weeks ago because the (debut) album got good reviews, but it didn't stick with me and never listened to it since.
So I gave it one last chance and then removed it from my bookmarks after the third song or so...
Except after a few songs more I really got into it and re-added it to my list.
Been listening pretty much nothing else since.
Love the mix of technical brutal death metal with the female vocals (all the vocals are sung by that same woman by the way).
Some reviewer gave them the label "brutal 'female-fronted' progressive metalcore", so there's that.
It's a bit hard to choose just one song because the entire album is just killer, but Epiphany has a nice clean refrain (just like Aurora, but this one also had a video).
Not just song of the week, but album of the week
|
|
|
|
|
|
I must confess, I expected more bleeps and bloops.
Still good stuff though
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
