Toad speedy solution for Striped Words by veky - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Toad solution in Speedy category for Striped Words by veky

def checkio(text, transition=(
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,192,192,192,192,
192,192,192,192,192,192,192,192,192,192,192,192,96,96,96,96,96,96,96,96,96,96,
192,192,192,192,192,192,192,576,288,288,288,576,288,288,288,576,288,288,288,288,
288,576,288,288,288,288,288,576,288,288,288,576,288,192,192,192,192,192,192,576,
288,288,288,576,288,288,288,576,288,288,288,288,288,576,288,288,288,288,288,576,
288,288,288,576,288,192,192,192,192,192,192,192,192,192,192,192,192,192,192,192,
192,192,192,192,192,192,96,96,96,96,96,96,96,96,96,96,192,192,192,192,192,192,
192,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,
96,192,192,192,192,192,192,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,96,
96,96,96,96,96,96,96,96,96,192,192,192,192,192,192,192,192,192,192,192,192,192,
192,192,192,192,192,192,192,192,96,96,96,96,96,96,96,96,96,96,192,192,192,192,
192,192,192,576,288,288,288,576,288,288,288,576,288,288,288,288,288,576,288,288,
288,288,288,576,288,288,288,576,288,192,192,192,192,192,192,576,288,288,288,576,
288,288,288,576,288,288,288,288,288,576,288,288,288,288,288,576,288,288,288,576,
288,192,192,192,192,192,192,192,192,192,192,192,192,192,192,192,192,192,192,192,
192,192,96,96,96,96,96,96,96,96,96,96,192,192,192,192,192,192,192,384,96,96,96,
384,96,96,96,384,96,96,96,96,96,384,96,96,96,96,96,384,96,96,96,384,96,192,192,
192,192,192,192,384,96,96,96,384,96,96,96,384,96,96,96,96,96,384,96,96,96,96,96,
384,96,96,96,384,96,192,192,192,192,192,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,96,96,
96,96,96,96,96,96,96,96,0,0,0,0,0,0,0,96,480,480,480,96,480,480,480,96,480,480,
480,480,480,96,480,480,480,480,480,96,480,480,480,96,480,0,0,0,0,0,0,96,480,480,
480,96,480,480,480,96,480,480,480,480,480,96,480,480,480,480,480,96,480,480,480,
96,480,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,96,96,96,96,96,96,96,96,96,96,
0,0,0,0,0,0,0,384,96,96,96,384,96,96,96,384,96,96,96,96,96,384,96,96,96,96,96,
384,96,96,96,384,96,0,0,0,0,0,0,384,96,96,96,384,96,96,96,384,96,96,96,96,96,
384,96,96,96,96,96,384,96,96,96,384,96,0,0,0,0,0,192,192,192,192,192,192,192,
192,192,192,192,192,192,192,192,192,96,96,96,96,96,96,96,96,96,96,192,192,192,
192,192,192,192,96,480,480,480,96,480,480,480,96,480,480,480,480,480,96,480,480,
480,480,480,96,480,480,480,96,480,192,192,192,192,192,192,96,480,480,480,96,480,
480,480,96,480,480,480,480,480,96,480,480,480,480,480,96,480,480,480,96,480,192,
192,192,192,192
)):
    striped = state = 0
    for byte in text.encode():
        state = transition[state + byte]
        if not state:
            striped += 1
    return striped + (state == 480 or state == 384)

March 1, 2015

Comments:

veky on March 1, 2015, 6 a.m.
This should be fast enough for you performance fetishists. :-P Explanation of a title, since I've seen many people not get the point of my titles: Besides hopping as a toad from state to state, this is also ugly as one. :-P Also see the `)):` in line 33. Python is very sad. :-(

StefanPochmann on April 18, 2015, 10:14 p.m.
This really is fast. I compared it with <a href="http://www.checkio.org/mission/striped-words/publications/ale1ster/python-3/regexes-all-the-way/">ale1ster's "Regexes all the way"</a> which I thought would be a faster FSM in C, but yours won 8 seconds to 9 seconds (on `"Dog,cat,mouse,bird.Human." * 1000000`).

veky on April 19, 2015, 10:36 a.m.
As I said, I just wanted to show that writing Python with the primary intention to be fast is totally pointless. Python is a tool for explaining algorithms. It is an executable pseudocode. You just don't look at a piece of pseudocode and wonder how fast it executes, except in complexity-class sense.

Paul-Yuchao-Dong on Jan. 6, 2017, 1:27 a.m.
I totally wish Python could be executable pseudocode. Learning algorithms now, I found it hard to actually translate the pseudocode into Python. An MIT OpenCourse <a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/">6.006</a> helped quite a bit, but I'm still filling the gaps.

veky on Jan. 6, 2017, 3:15 a.m.
It might be hard to translate your thoughts into Spanish, if you don't speak Spanish very well. :-P But that's not the problem of Spanish language. :-] Can you be more specific, what do you have problems with?

Paul-Yuchao-Dong on Jan. 7, 2017, 3:03 a.m.
Precisely. I'm actually having problems with A star search. I don't want to just copy a bunch of code from the internet because I would never learn that way, so I found these pseudo code <a href="http://web.mit.edu/eranki/www/tutorials/search/">link</a> and want to code it up myself. <pre class='brush: python'>// A* initialize the open list initialize the closed list put the starting node on the open list (you can leave its f at zero) while the open list is not empty find the node with the least f on the open list, call it "q" pop q off the open list generate q's 8 successors and set their parents to q for each successor if successor is the goal, stop the search successor.g = q.g + distance between successor and q successor.h = distance from goal to successor successor.f = successor.g + successor.h if a node with the same position as successor is in the OPEN list \ which has a lower f than successor, skip this successor if a node with the same position as successor is in the CLOSED list \ which has a lower f than successor, skip this successor otherwise, add the node to the open list end push q on the closed list end </pre> I'm having trouble understand what "same position" means. If I need a position dictionary to to record a node's position, how should I calculate this value? Case in point being your solution to the haunted house puzzle (<a href="https://py.checkio.org/mission/haunted-house/publications/veky/python-3/4d/),">https://py.checkio.org/mission/haunted-house/publications/veky/python-3/4d/),</a> my plan was to cross reference your code with this pseudo code then understand this mysterious position value, but I don't think the f dictionary do much in your code and may be you just implemented Dijkstra?

Paul-Yuchao-Dong on Jan. 7, 2017, 6:33 a.m.
My mistake. After some sweat on the treadmill and coffee, I had certain clarity. I think the f dictionary is used to select that next exploration point in the graph. I had the wrong impression before because I didn't figure out what the heuristic function does. With heuristic being 0 all the time, a star sort of became Dijkstra, but if I implement the heuristics, a star would prioritize nodes "closer" to the goal. Let me learn why that can still produce the shortest path.

veky on Jan. 7, 2017, 10:18 p.m.
I'm not quite sure if it is a question, but I think I have already explained what heuristic is for. It gives the lower bound to actual distance from the goal, so A* knows which nodes are too far to be useful in the optimal path, even before it explores them.

bsquare on Aug. 7, 2019, 2:29 p.m.
I guess to reach this goal with this evil solution ^^

Splitter on July 27, 2019, 11:15 a.m.
How does it work?

veky on July 27, 2019, 12:50 p.m.
Have you heard of Finite State Automata? :-)

Splitter on July 27, 2019, 12:56 p.m.
Not much and almost doesn't remember.

veky on July 27, 2019, 2:03 p.m.
Well, the main idea is to have a giant table, indexed by all the possible states of your machine and all the possible inputs, giving new state when an input happens. The only "innovation" here is that the "table" is 1D, not 2D, but I think it's not hard to see how that's accomplished. :-)

Splitter on July 27, 2019, 3:06 p.m.
I wonder how did you manage to compose the table.

veky on July 27, 2019, 5:18 p.m.
Well, there are quite well-researched techniques to do that. See Sipser for example. Or just google "constructing dfa techniques". :-)

piter239 on April 23, 2020, 1:25 p.m.
So you didn't do it by hand? Now I am disappointed :)

veky on April 23, 2020, 1:29 p.m.
I learned long ago that you always disappoint someone no matter what you do. :-)

Happiness on March 2, 2015, 12:16 p.m.
This is little crazy thing :-D

veky on March 2, 2015, 3:43 p.m.
Of course. But it's also fast. :-)

viktor.chyrkin on Oct. 23, 2021, 4:09 p.m.
<h1>trollingisart</h1>

veky on Oct. 23, 2021, 8:01 p.m.
<h1>educationtoo :-P</h1>

Kverde on Aug. 14, 2022, 7:56 a.m.
Are the states generated by another python program? It is interesting to look at this.

veky on Aug. 15, 2022, 6:08 a.m.
<a href="https://py.checkio.org/mission/ghosts-age/publications/veky/python-3/finite/share/1eb17c0f9af8f148018c1b205a8a8b5a/#comment-18147">Obviously</a>. :-)

mithilkotak on Sept. 16, 2022, 1:50 p.m.
Creative and fast! I like this very much.

veky on Sept. 16, 2022, 2:45 p.m.
OMG, people have started to find darn lookup tables creative, as long as I write them. :-D

mithilkotak on Sept. 17, 2022, 1:38 p.m.
It is different from other solutions and obfuscated enough to be outside my grasp.

veky on Sept. 17, 2022, 1:44 p.m.
See the comments above, they might help.

Strings Theory

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.