Logo TIB AV-Portal Logo TIB AV-Portal

Solving the web most popular code shortening competition in Python.

Video in TIB AV-Portal: Solving the web most popular code shortening competition in Python.

Formal Metadata

Solving the web most popular code shortening competition in Python.
Title of Series
Part Number
Number of Parts
CC Attribution - NonCommercial - ShareAlike 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this license.
Release Date
Production Place
Bilbao, Euskadi, Spain

Content Metadata

Subject Area
Alessandro Amici - Solving the web most popular code shortening competition in Python. “Code shortening” is the “sport” where participants strive to achieve the shortest possible source code that solves a programming problem by exploiting all the tricks and quirks of the language. The [SIZECON on SPOJ] is one of the oldest and most popular code shortening problems on the web with a bizarre twist, only character above ASCII value 32 are counted for the penalty. During the talk we will take a journey into some frightening depths of the Python language in order to write shorter and shorter solutions to SIZECON until, exploiting a number of truly mind-blowing tricks, we will reach the current record solution of 28 characters (above ASCII 32!). I promise I’ll show you the most obfuscated, contrived and sick python code you have ever seen and (hopefully!) will ever see. I invite participants to give [SIZECON] a try and check their score against the [Python2] and [Python3] SPOJ rankings.
Keywords EuroPython Conference EP 2015 EuroPython 2015
image processes Software topology Development maximal solid Code open subsets web
time characteristics ones sets open subsets regular Code information goods SICS source code Rank testing platforms position web man web Quark heaps sample staff Code scans open subsets Types case website Rank Abstract
point constantly Numbers time equal unit Code icons van information source code different naturally level Rank integer structure input exception man algorithm standards NET construction sample plan Code scans Symbolic sign particle Computer animation functions statements input website sum
Numbers factor gaps Ranges print maximal Stream argument fields web Auswahlverfahren solution sets string input errors classes form exception systems man multiple standards graded counting maximal sun Code lines redundancy processes Computer animation case input website sort species peer-to-peer since Results clone
Actions building breadth states Ranges iked total Code CAN-bus different encode encrypted descriptions exception Chi-Quadrat-Verteilung man algorithm scans sequence means angles orders input website spacetime record Numbers functionality table print maximal translation Stream van powerful training string input Gamma Cats ascii text form counting Code lines cryptography Computer animation string life table
man Numbers NET time translation effects maximal staff Stream scans information mathematics words Computer animation string string different encrypted website box Right ascii text Results exception
point web pages Numbers states time maximal translation Stream programs training second subset source code different interpretations string Representation level integer structure Conversation partition exception default parsing Graph NET volume Code scans words Hexagon Computer animation case string topology orders normal sum pattern level objects
presentation Numbers files link breadth time views sources sheaf ones browser part heads information Forum string level Representation Code open subsets words radius Computer animation real vector case Right sum level functional space
we thank you to the minimizer emissions of the day job I work at the European solution was sponsoring my talk here and we do the software
development in Python and we worked mostly we just special that so all geographic geography and solid images and this can it as a hobby I do cutting competitions and not there is strong enough really people were really great and I'm just a hobbyist but I like very much there the tree you and
the things you will learn and the crazy stuff that you end up doing this talk will be about the coach shock and culture sharpening use kind of coding competition where you don't strive to solve the problem in the smallest amount of time or with other or taking all staff but you want to do it in the smallest possible source code and it's just for fun am in we will go through the dissolution of 1 of the problem 1 of the most popular problems where I have the shortest solutions but most of the have we will see that in this particular case it's really it's really interesting what you need to do to get the shortest code so far 1st of all the good shortening is usually the cold cold gold because you would strive to do the less that mean you you want to work the shortest and it's
similar to go also right I I mostly use cop could golf as as a way to call this part of and so we will be talking about this to be the sites gone problems on the sports sports resist your judged and actually if there is something that I assume you will read the abstract and hopefully you ever had a look at the uh coding competition yourself and so by you to go into some frightened and that of the by the language and to show you some mind-blowing tricks and to and that showing you the most obfuscated confronted with the type and could you have ever seen and hopefully will ever see not if there is something that you I really would like you to learned from this talk is to not overemphasize abstracts because then you at end up in a room full of people that you and say OK and here will my mind anyway let's see what we what we don't tend to so 1st of all then for people who don't do going competition and don't know what sport some spot is a cunning platform that we get 1 judge this is you can couple open problems and people can try to solve it supports a huge amount of languages and he said he a test it really amazing Truvel problems throughout the around 20 thousand problems that's a lot of them are quite easy but some of them are really really hard and some of them can be done just in Python that he's only known solutions are in Python most of them are forcible spouse etc. those they are found you need fast memory management what is a characteristic of spores with respect to other coding competition that you know but you mean all is that the while users costs are public and you have rank sample so you know what the regulars who are good ones and always good instable spot of light on the set of solutions are not public and not the public at the end of the day when you do in competition so you can actually compete any time and some of the data there have been problems are really all that and have been solved by a lot of people if you knew if you're looking to the Web someone publish their solution and you can find solutions for the the easy problems but they have problems are solved by people who we value there uh positioning Bush so they don't publish their code and you are not that you have to do it yourself
business by the way I'm publishing the codes for a 1 of the best solutions in Python for this problem so please do not use that solution to get half point in our actually you have to provide said that you're not going to cover the solution set the weights you have to leave now cites counties and user problems usually this dispersed problems are a standard that algorithm problems about the size going is 1 of the the few could cause problems it's 3 although it has been uploaded in 2005 and it's actually 1 of the top 20 most probable provinces Polish and 8 thousand people strike you it and we then thousand 400 solutions in Python actually competitors 1 of our and in 1 of the fathers of icon 1 of the best our so even if you Petersburg to do all of the this structure so let's go to meet this
that the the statement of the problem school sites gone sites competence and given a set of integer and the language 3 strange but given a set of integers from the sum of all positive integers in this year you're given an input to that is a Nash if I and ask 5 and you get the 1st number in the in the input is the number of the following integer that you have that you need to consider and that you have to sum only the positive integers discover that you will get is equal to the size of the source code of your program except symbols with ASCII code below equal or below 32 design and then you have a sample input if you get for it's the number of in and of following numbers that you have to consider them firemen 5 6 minus 1 and you have only 2 will some day positive integer so I was 6 it's like by these it is very easy actually it's not very interesting as a constructed problem might self because it is now what is the solution these 4 or 500 to reason and in this talk is that I have that 1 of the 2 best solutions I wrote 1 of the 2 best solutions that are being exploited to support and quite far but strangely the this they called that the problem must be published in 2005 and someone already after 6 months from the 29 solutions will be would all and only after 9 years How about and which is very no I mean it's 1 of the best coach shorter hours in Python and find the solutions just days before I find I found this 1 the solution so it's after 9 years to people in 2 weeks managed to get 20 by the free it's more or less the same and that is uh this solution can be rewritten in the same solutions is rewritten by the 3 and it's just slightly longer because the syntax is like so we are going to see the 2 . de Department solutions because it's the 1st 1 I developed and it's just slightly from so let's see general particles with the master plan actually that is to the steps that you do are more or less all with the same 1st you aim to correctness you build reference solution so you need to check that you understood what the problem want and because every time you submit solutions 1st it must be correct and then they count how many characters you use tool and the you score so 1st correctness than other algorithm wizardry usually you start with the standard algorithm and you can get to the same solution is really large that being in a large number of different with different algorithms sometimes you specialize something you generate them the reason for this is that of the 2nd the next level the language we of units that you try to find strange constant construction in Python syntax is that usually are not used to get the good short and sharp and sometimes work better with some strange algorithm and we just straightforward 1 so let's start with the reference solutions around 50 character this
is an extremely non shocked solution you just read the 1st input you initialise your counter range counts over all and the all the following number you get any number check if it's the bigger than 0 summit and redundancy of these works if you count which usually that could also the all the characters in your solutions 107 solution set of 107 the score but which sites constitutes since you can the you don't count all species and new lines it's you can easily write it sending everybody is able to write it in a more compact form are just using summer and for reuse and max so you here really need to know that somehow the input inside the range would be about wait before all the input inside the maximum input actually radio does the cast to integer so everything you this working nicely and you already getting the underage of 45 character now 2nd step is to try out other no if you don't read the fine print like you forget that you have these are a special character ASCII characters exception there's nothing to see in news just summing animals let's say let's factor European it as standard chord shorter cold shock and solutions 1st these are all tricks that you can find on the web by it's so quiet involves the processing understanding what users what what works and what not and it's very nice and you spend a lot of sleepless nights doing it but it's more or less from the 1st of all the inputs you can just give a short to make 2 important and you will save 1 characters there's just 1 character you call it people a you want the then there is the most used 1 of the most used that treats for code sharpening the stool the transformer for into the strain into string multiplication in this case you see the max 0 I began so the piece of history that I made it times I saw you read the 1st numbers I do this long of marks are much year adult I etc. and then I have all of a ballots so it goes and fields all the people treats the input from the from the standard input and then this makes the beak properly the amount will return in big trouble that you pass to some of the which just did the current results as summing max is making sure that you're standing only positive and we're down to 40 now there is the the the the trick that I liked a lot of the fact that you actually can remove the summer since you're really doing involved and you have a common on the other side you drop to come on the other side and who the class of the beginning of now you are already doing some and there is this nice trick that the sun at the beginning of the stream there would not be a problem because plus it's both if you were a unary and the beauty of it at all so you you you we are already using a lot of small treats and etc. and get into 35 now we suck in getting closer but the closer you get the the harder it is no this 1 of the nicer treats in in standard for goes from that this you don't you input it how actually input bring the arguments before the reading the input to control their whole breeding to you already have a shorter name for a imports and you print with actually the solution and we do a syntax error but that's no problem because the the system doesn't care what happens after you have created sort of self and the are to 33 grade now my knowledge this
is the shortest possible solution would stop using the standard cultural denied can be proven wrong with it but they tried so what and they didn't find anything else and I see a lot of people with 33 in the score in the ranking so I guess it's quite advanced solutions if your mind yet social class hopefully not because this was just you can find this stuff very it takes some time so that you
can find this stuff on the now we left some fine print somewhere the but then had algorithms actually since there is a strange exception we can make use it as many as ASCII characters below 30 do as we want what can we do with them the site code the only legal characters are space top I don't think you do anything that you can really doing that because they're just spaces but you have another place where you can put row ASCII character for leader of the legal characters and flanking Setsuna leader power a lot and at about 30 actuators capital after characters is not legal inside by strings must be escaped with the world FlashFax 0 0 and the new line is not legal because they want to do that single quote the the string so it will be a new line so what I've 30 characters this is all taken to the be extremely as big as it wants and I have to find creative ways to use now it's not that difficult to to try to think what to do because the best the building rocks of your modify out and the other in peace building a string literal with a lot of ASCII special characters turned that string with into something useful maybe code and then do something with that you train which is reduced training and now it's a string lecture after after you will translated into cold now how can we do something with a string of code we accept basically what we're saying is that what we're looking at what we're looking for what we are looking for is a can of the print function that takes a encrypted stream something that has been interpreted into us to special character and then pass it accept actually of these are the steps that you do to prepare the solution because you can't write it of is life in any form and you decide what is your original solution something that need to work and we 1 of the previous solutions than you ever the last 32 and creeps function you need to find is that treats it into just ask you special characters than you put it into you you have to write your asking 32 the crypt function is also a few characters as you can and then you pull the strings there and you get a solution and instruments of solution so what we are interested in is in buildings is as you 32 decrease so do you would does anybody have any suggestions on what we need is something that takes as input and him string leader of 1 gives training and then outputs another stream with possibly Python code and it must be as short as possible because this is the mean we're we want to go the dual 33 does anybody any idea of what can be used to do these what trick we need we need translated string translation and translated to the 1st power horse because if you know to imparted it's the 3rd the so it's really longer this spelling lock them in the if you save the importance already In the OK range now what's translate does it's recounts a copy of the string with up all characters have been mapped that through a given translation table which must be a string of length 200 56 but we can feel it which the contra characters so we really don't need the 200 56 characters we just need to to put inside the cat that there we need the in the translation decoding in the group this is how discrete function I alcohol power solution we look like so we haven't read that string it's an interesting full would ask to characters then we have a translate we we translated and we need to have the they print table that will make this go into code to that then we expect now the machinery the translation machinery our exact possibility the description is 20 characters last all known asking the number of known as contra characters that we need to put in to determine the critical the code is written with non-ascii coping with non-ascii uh we asked the a 32 characters so we will need to put some of those into the critical so we have we spent 20 characters and let's see how how many characters we need to make a nasty contra character strings began some nice coat this is how you do it then I mean I reproduce sexually there are small stuff like the fact that you don't want to use the 1st character in the the Greek table you can't use the 13th character because the online so that small the days that I mean which which I don't want to bother you and so if we get these their 1st the solution that we we 1st used we can use the counts the number of different characters in the states 19 and the character of the characters that are there now obviously 20 past 19 it's not really great we already have 30 300 39 so we start doing tricks so for example they underscore it's just you read like and I already I was already used by angle I can look at 18 and so and then I had to use nice streak I don't need this 0 the 0 it's just in you can just finished assessed instantiate the entire as you already using input that has order in the and you go to
17 cat so you see we just map the all problem into a new problem this is a quite unusual shopping problem is that we are looking for a solution to a problem we just the meaning number of different kinds let's call it cites come to problems
it's the same sites box the people you're looking for the minimum number of characters so we will who decided translates staff it's working it's that it's that as an effect I found at least to what the way to do the decryption who could be could could for gave good results is just the I spent a lot of weight nice and no how can we do better OK we try to use the same treats as before trying to find language traits together to use less and less characters but not as easy as it appears for example a few the change the projecting puts its it doesn't get you anything because the letters are already used to so a lot a lot a lot of time afterward by a really our the right to something that is quite convoluted by was 20 plus 14 that is 14 different characters so an even 13 different characters and if you look at the of this stuff I mean we it will take you some time to tool to understand does somebody words that's that all of them to be sure that it was not writing Stuart Vincent but we 33 any and all this work and we are back to 32 or 33 solutions how can we do better they were no we're talking to look into the
at this the so so How do you write corrodes we'd less different character maybe octal strings so we are not told me if you did you can write a string literal we just flesh and numbers from 0 to 7 but what do you do we did up Opel streams tell where I put them in the cynical and so you can see that the staff has although there a number and we have to go downward is the only way forward we are inside exact it what we want to do is another except so this is can already mentioned that exception where you need to go deeper and deeper in the dreaming up to actually get the work done now does it
actually work it does so you can get the string except it's and inside the string you want in except for the stream weight what is nice is that if you use all of the the octal contest you were back to 33 but obviously I mean you you have some wedding grown in you don't need all the numbers if you're very careful we II collected something like hundred dollar program or different solutions so I can just look for all the solution and see if I can get it a solution that doesn't use a character because now if you can read this this actually a working solution and it happens to not use the character 3 in the of of representation of a ends if you spent in hour knives looking for this stuff you write programs to see what characters you can use in all the cases buying all I science and this is all we this is less than than 32 it is the 1st 0 no it is not this out the toolkit is a 32 they've which is less than 33 so this is the 1st time we managed to use asked to character trait to get the better solutions than normal pattern of can we do better actually I remember that once I wrote the solution with this tree kept that was 31 characters but I can't find it any more and it's sums polished but when you don't know the solution at that make garbage of their ASCII characters so I don't know what the solutions I know that there is at least the 31 solution would just the streak and you will would debated the number that the optimal number that you don't need if you want it's a nice it suffices but we are 32 or 33 28 it's really how can we get you just that's them back you know that to get to 28 so we need to remove for characters from here it appears that if we accept that you are doing the exact and you have this slash and you need the double quotes you have just 3 let us laughter to use how do we do it now following going on on the inception that metaphor he met metaphor the only way this downward we do another except of an acceptance of a string literal why would you do that 1st because you can he does not it does not look any anything to discover because you're ready at all the letters tool for industry needed for building there there's solutions the string and the point is that now you can be the string literal as from Python a string literal you can build because after the partition of street of the the the the source code and it's not a string data anymore and this lecture the opt of representation doesn't work so you need to 1 more exchequer in order to build there string that compose composed uric second-string leader of which is the solution so what can we do all this is just to see how it works now we get a statement like green this is the optimal representation this is this training data that represents the optimal representation of the of and within the 1st 6 seconds we can actually compose that string we get that by default for example the 4 it's actually like a graph of the integer and director of integer for it's just the sum of 1 plus 1 plus 1 plus now obviously we're not going very far because representing the long but actually it's not that bad because he it's ready there because of the exact and the parentheses that we but we're beginning it's a lot of cost because of the parenthesis of the EU and our and also what we'll possible day blast there so we now need almost the final tree is second-to-last tree what how can we shorten red I care yes come their friends actually wrapper if you look in on page is written as being companion printable representation of an object and is the same volume value you the bike on the front which is reverse quality i.e. you know really called exists in the before us starting to playing with the shot coding but this is great that you throw all their parentheses and rapid away and you just get that you introduce last backwards and 1 3 characters and with these 3 characters you can deal the everything everything except you can all the numbers 1 2 3 up to 7 but not this 0 so we can do all of completely arbitrary the interesting code and running it with exact exact that with just perceived blast double-quote 0 1 slash rest commerce and the and X but this gives the was how do we get the word we don't like this 0 how do I true this year the you don't do a single character that you get the 60 page 2 1 plus 1 plus 1 plus Monday their seeks high furious and these works and we got plenty of now very fast because is exactly like the inception as another fight and is that many exactly exactly except to unstable no actually you can't it does work out it's a lot of work to build the dissolution because you have a lot of tricky cases but we have more or less the same you structure of the inception reality in the movie its opined interpret there and that we pass a stream and that stream the main work that we got the ways that we decrease the asked 32 and created stranger than we expected within the 1st except what we're doing we build numbers with the conversion traits and we believe all the numbers that we need an all with all the pieces we the build up the the exact lossily all the solution that then we expect and we go 1 more level the world every people and we passed the string literal we exactly once more and finally we around a completely arbitrary code to and we choose the code that this particular problem but we cancel any problem with 98 characters above 30 and whatever the
states of we also affected and my friend guidelines to show you mostly by the code you have overseen actually you can see it in the 90 . is a hex dump a lot of the actual solution that I submit and obviously you don't understand anything about I can show you what happens after translation you get this very nice trained as well which is the 2nd 2nd the play year and then we get to this which is the upper representation that we want to extract and we
go to which is just the the solution we start with and now it took me really a lot of time both to find a solution and to prepare the talk because it's really difficult to explain and I hope this work and your mind your mind the section blowing out and if it's not I just 1 word and also slightly however 6 characters and they'd probably this thing that we do you can feel the is a and B would my mind this isn't alone this applies 3
solution longer because the buck strict doesn't work uh um let's see if so I said remember for sure you don't sector Vicsek have parentheses so you would lose to what the very beginning of full parentheses and then I think yes is the vector the the the the the vector that doesn't work by they read on or I mean I would have to look at the at the solution then that would not do much because I can't treated but for my brain hurts them make listeners said develop any tools for building code in the different levels actually yes I mean it's not possible to write this down and I did not only to to write the code but also tool to analyze all the possibilities because whenever you try to look for solutions that means for example 1 of those numbers you need to tries and actually it was the previous solution that was befriended even use translated where I tried it is a huge space of functions that could do the might translation between below 32 and the character that they needed for the solution so it was quite so quite a journey also as a matter of fact I is slightly cheated you in the sense that if you look here actually there is 1 more trick you see that explanted 28 for example and there's 1 more trick in which if you ever 0 inductor representation sometimes you can talk to the uh exhibition hall representation since I already had the sum the x I could use that so I try to minimize the case where you need to some very very young ones not does the parole solution also are encoded into characters underneath 32 has I would pay to see that the person from ideas that that I guess so because a head there was quite the in 2005 2006 there was quite a lot of chapter in the forum about that and they were talking about uh how they could not read a solution but just had a tool that field the part of the 1st step and then another 2 that the the 2nd step and so on and so on so I guess they were doing the standard free trips have you considered switching to on a language actually did better suited if you look the better the sexually for pain and with 7 so hi that you're trying to so this is not the solution I must admit that I as I was writing the the the presentation hired a couple of ideas i I don't want move to to think of them otherwise I will need more a sleepless nights or the question and goal scorer view of the entries very with what was the actual goal schools the length of it including the horrible characters no I am sorry I did the gulf source what is what is the length of the string you've actually submit sitting around English I think it but I'm not sure you mean the length of the I'm not sure radius was several kilobytes like 30 but the link actually there is a limited which is 50 so I mean I still have some room this is the last question because the issue summit this week the browser no no I uploaded the file yes so in happens it is the reason I cannot download it anymore because the rights at the browser all maybe they're they're called the uh gametes Gabbouj other it when you try to download it again OK thank you very much to give you