Comprehend creative solution for Mathematically Lucky Tickets by veky - python coding challenges

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

Comprehend solution in Creative category for Mathematically Lucky Tickets by veky

t=lambda s: {int(s)}|{x for p in range(1,len(s)) for a in t(s[:p]) for b in t(s[p:]) for x in {a+b,a-b,a*b,a/b if b else 0}}
checkio=lambda d: 100 not in t(d)

June 17, 2013

Comments:

bryukh on June 17, 2013, 5:08 a.m.
It's real short! But too slow. Yes, you are lazier than i am :)

veky on June 17, 2013, 5:13 a.m.
What do you mean, slow? This is Python. Everything under a few seconds is admissible. :-) No, seriously. The only thing I could do to easily make it faster is separate the last layer of recursion, and stop there as soon as I find 100. But I really don't think it would help much. Have you actually timed it, or is it just your intuition that it is slow?

bryukh on June 17, 2013, 5:27 a.m.
Intuition and little calculation.

veky on June 17, 2013, 5:34 a.m.
I don't know what calculation you're refering to, but ok, it's testing time. :-) Can you point me to some solution that is not "too slow" in your opinion, so I can compare?

bryukh on June 17, 2013, 5:38 a.m.
<pre class='brush: python'>python -m timeit -n 100 -v -s "from veky_l import checkio" "checkio('111111')" > raw times: 0.335 0.336 0.343 python -m timeit -n 100 -v -s "from bryukh_l import checkio" "checkio('111111')" > raw times: 0.0559 0.0552 0.0547 python -m timeit -n 100 -v -s "from veky_l import checkio" "checkio('999999')" raw times: 0.726 0.751 0.735 python -m timeit -n 100 -v -s "from bryukh_l import checkio" "checkio('999999')" raw times: 0.101 0.0997 0.0999 </pre> And mine is not fastest.

bryukh on June 17, 2013, 5:40 a.m.
Hm, but your solution is very fast for "000001" :)

bryukh on June 17, 2013, 5:41 a.m.
Sorry, your solution is very fast for "unlucky" ticket.

veky on June 17, 2013, 5:54 a.m.
Well, I don't know how many tickets are (un)lucky. But I'm still trying to see what your solution does that is so different. And as I said, everything under a second is ok for me. :-)

bryukh on June 17, 2013, 6 a.m.
<blockquote> everything under a second is ok for me. :-) </blockquote> Agree

veky on June 17, 2013, 7:14 a.m.
But now you've put a bug in my brain. :-] Well, I have bad news for you. As I suspected, much more tickets are unlucky, so for 3 times 100 random tickets, we have: <ul> <li>5 lucky, 95 unlucky, your algo ~20 seconds, my algo ~3 seconds.</li> <li>11 lucky, 89 unlucky, your ~30 s, my ~3 s</li> <li>12 lucky, 88 unlucky, your ~30 s, my ~2 s</li> </ul> So I'm about 10 times faster than you. :-P

veky on June 17, 2013, 7:17 a.m.
And now I see what is the main difference between us. I use set comprehensions, so I squeeze every level into just unique numbers, resulting in great savings in later levels.

bryukh on June 17, 2013, 7:50 a.m.
Yes, thanks. My intuition was wrong. Very interesting solution.

NickHaflinger on July 10, 2013, 8:27 p.m.
This 2 liner is elegant and blazing fast but I found it incomprehensible when I first saw it a couple weeks ago. So to understand it, I first spent the last couple weeks learning functional programming (Haskell, and then Python). I still didn't understand it (but I'm happy that I now "get" the basics of functional programming). So I rewrote your solution in a way that I could understand. Here's my rewrite (which is 40x slower, but IMHO much easier to read and understand): <pre class='brush: python'>def eval_expressions(s): set_of_values = {int(s)} for p in range(1, len(s)): for L in eval_expressions(s[:p]): for R in eval_expressions(s[p:]): for evaluated in {L + R, L - R, L * R, (L/R if R else 0)}: set_of_values = set_of_values | {evaluated} return set_of_values def checkio(s): set_of_evaluated_expressions = eval_expressions(s) is_lucky = 100 not in set_of_evaluated_expressions return is_lucky </pre> Question: when you write complicated comprehensions like this with lots of nesting and recursion, do you start with something like what I wrote and then switch to comprehensions for the increased speed? Or have you just done so many of them that you can easily think, read, and write them no matter how complicated they get?

kvas on July 10, 2013, 9:28 p.m.
I'm not veky, but I'll try to answer your question. In my opinion this program is quite readable, at least it took me less time to understand what it's doing compared to some other solutions. I think writing it would be possible in comprehension form from the start, although perhaps it wouldn't work the first time (unless you're a coding ninja :). Another question is whether it would be reasonable to include code like this into a production system. I would reformat it to be maybe 3-4 lines, but after that I don't have a universal answer. If the team has lots of FP experience, and there are many things written in similar style, I would say yes, do it. If people come from more mainstream languages or don't have much programming experience, it would reduce maintainability, so no. P.S. I hope you enjoyed learning Haskell. It's a gem of a language.

veky on July 10, 2013, 9:33 p.m.
A bit of both. The first version I write is usually a bit longer than what I finally publish, but I'm afraid it would be equally incomprehensible to you. My brain just works differently, and I can force myself to write long-winded way (I need it for my job after all), but I don't enjoy it as much. So this is a kind of release valve for me. :-D BTW, I never do it "for speed". Speed is just a nice side effect, since in interpreted languages, the less you write, the less the parser will have to chew on, and it is often the deciding factor. But there were occasions when I, for example, used min(generator) instead of next(generator) because it's one letter shorter, despite being a few times slower (of course, that was in a task where the longest times were still in milliseconds). Ask bryukh. ;-) For me, Python is "executable pseudocode". The most important thing is to express the idea so detailed that computer can understand it. Milliseconds are irrelevant - if you want that, use C.

bryukh on July 10, 2013, 9:44 p.m.
:-) At last, i was solving one task from coursera course and tried to solve it with python. It was too slow. I optimised it, but it slow. I changed buitin "max" (i used it for two arguments) and it give 5x speed. But it was slow. I took PyPy and got more 5x, But it was slow. After all of its, i took Java, spent 20 minutes for coding (i already had python prototype of algorithm realisation) and get 100x speed. So, i agree with you :-)

NickHaflinger on July 11, 2013, 9:01 p.m.
Thanks for your comments. I guess I just haven't done enough functional programming, comprehensions, recursion, etc. Perhaps it will become more intuitive with practice. BTW, my rewrite above is slower only because of one line. If you replace <pre class='brush: python'>set_of_values = set_of_values | {evaluated} </pre> with: setofvalues |= {evaluated} then the rewrite runs at a similar speed to your 2 liner. I've since played around some and added some optimization which makes it much faster than your 2 liner and I don't know how to make the optimizations in comprehension form - perhaps it's not possible. I'll post my speedy version in a few minutes. I ran it on all 1 million numbers in 11 minutes, 37 seconds. I found 74,918 (7.49%) lucky numbers.

veky on July 11, 2013, 9:11 p.m.
There is also a set.add method. While you're measuring, try set _ of _ values.add(evaluated). :-)

NickHaflinger on July 11, 2013, 9:29 p.m.
Just tested the set.add method and it's a bit faster.

kvas on July 10, 2013, 8:59 p.m.
Pretty awesome! BTW, the ratio of lucky to unlucky tickets is around 1/10.

kvas on July 10, 2013, 9:15 p.m.
Did some performance testing too. Seems that my solution with a bunch of yields is about 2 times faster. This is quite weird though, theoretically all this generator stuff should not be too fast... but maybe set comprehensions are also overrated ;)

veky on July 10, 2013, 9:36 p.m.
The obsession with "fast" in Python is what's most overrated. See <a href="http://www.python.org/doc/essays/list2str.html">An optimization anecdote</a>, by Guido. If even the language's author himself can be surprised with what's fast and what's slow, I'd say the language is really not meant for such considerations.

kvas on July 10, 2013, 9:47 p.m.
I think there are two sides to it. I'd expect people to use a reasonably efficient algorithm and reasonable data structures (like not doing 10k lookups in 10k-long list but converting it to a set first). Otherwise the program can become painfully slow on things that don't even have any complexity. It's also smart to use builtin functions where they fit, because they're often written in C and work much faster. However, I agree with you that python is not intended for high performance, so if you need some part to work really fast, you should probably start with rewriting it into a C extension (or check if somebody has already done it).

NickHaflinger on July 11, 2013, 10:07 p.m.
veky's concept is very cool and very fast. Using this basic concept but rewriting so that it doesn't use lambda's or comprehensions, I was able to achieve 6x speed increase. The two big time savings were caching known sets and aborting when 100 is found. I ran my new version on all 1 million numbers in 11 minutes and 37 seconds on my i5 m2430, and found 74,918 lucky numbers. I posted my solution as my "second" solution. My first solution was 70 lines and took a couple orders of magnitude longer to execute. The basic concept of my first solution was to generate every possible expression and then use eval() on all of them. Even though it aborted when 100 was found, it obviously had much more repetition than veky's solution, plus it used eval() which is slow.

AHrEJl on Aug. 2, 2013, 11:40 a.m.
awesome but completely unreadable :(

veky on Aug. 2, 2013, 2:30 p.m.
And that's the reason for -1?? Do you have some concrete problems with it, or are you just jealous it's so short? :-P Have you even read others' comments? NickHaflinger also found it unreadable, but he learned something from it. You could too. ;-)

veky on Aug. 2, 2013, 9:02 p.m.
Since people have asked me how would I write the same solution if I was writing professionally, here it is: <a href="http://pep8online.com/share/51fc1a526cee1659c2a34a0f">http://pep8online.com/share/51fc1a526cee1659c2a34a0f</a> You can probably see that the algorithm is completely the same. The only thing that's different is documentation (annotations, variable names, docstrings, comments).

bryukh on Aug. 3, 2013, 9:24 p.m.
Awesome! It's really nice code.

oduvan on Aug. 31, 2013, 1:32 p.m.
Why don't you make the second publication for this solution?

veky on Aug. 31, 2013, 4:03 p.m.
Because you're not paying me. :-P Really, I think it would just split the likes between the two. But since I have enough likes now for this task, ok, I'll publish it.

oduvan on Aug. 31, 2013, 4:45 p.m.
Thank you :)

StefanPochmann on Dec. 22, 2021, 11:52 a.m.
`Error 404: File not Found` So now there is no evidence here that you can write professionally :-P

veky on Dec. 22, 2021, 11:53 a.m.
There wasn't any even before, only now it's obvious. :-DD

StefanPochmann on Dec. 22, 2021, 12:01 p.m.
Well, I found the one in "Clear". Not 404, btw, confused it with another tab. But "Internal Server Error" anyway.

veky on Dec. 22, 2021, 12:02 p.m.
This is getting better and better. Now the only thing remaining is the dreaded Infinite Loading Page. :-DD

hrvoje on July 31, 2015, 12:30 a.m.
This is freakishly awesome and clever, I struggled with operators and generators, you just used sets ... boy, do I have a lot to learn. :-P

roelschlaeger on Jan. 23, 2017, 11:50 p.m.
This doesn't work for all of the current test cases... but is amazingly compact. After reformatting the code to the point that I could understand it, it is also amazingly elegant.

veky on Jan. 24, 2017, 11:04 a.m.
<blockquote> This doesn’t work for all of the current test cases </blockquote> Can you give an example? <blockquote> After reformatting the code to the point that I could understand it, </blockquote> Yes, I <a href="https://py.checkio.org/mission/mathematically-lucky-tickets/publications/veky/python-3/comprehend/share/5ee9a781f62fbe6cd147548aa2430083/#comment-4684">tend to do that</a> to people. :-]

Blizzard

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.