Saturday, July 4, 2015

Announcing the winner of the Powershell Oneliner Contest 2015

A week ago I invited the Powershell Community to take part to a Powershell Oneliner Contest. People joined from across the world in search of glory and of riddles that could put them at wits' end. Today a winner has been selected:

Here's the top 10 oneliner warriors in the contest:

1st - Johannes Rössel (aka Joey)
2nd - John Roos

3rd - Simon Wåhlin
4th - Simon Walsh
5th - Bartek Bielawski
6th - Nathan Hartley
7th - Kevin Marquette
8th - Max Kozlov
9th - Rhys Edwards
10th - Wes


Congratulations to Joey for winning the Powershell Oneliner Contest 2015 with the following solutions:
 
Task 1: Who's taller? - 34 chars
($n-match'\.'|sort)[-1]-replace'-'
Task 2: Can you count to five? - 8 chars
+'〹'['']
Task 3: PowerShell is the secret word - 164 chars
-join(-split'XXXXXXXXXXXX XXXXXXXXXXX XXXXXXXXXXXXXXXXXXX X XXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXX X XXXXXXXX XXXXXXXX'|%{$x=0}{[char]($_.Length+100-32*($x++%5-eq0))})

 - GUEST BLOGGER JOEY -

I am proud to announce that Joey has accepted to be our special guest blogger today. I am very honored to have you here.

Joey, tell us a bit about yourself.
 
I live in a small town in southern Germany named Tübingen (near-ish Stuttgart), working on a graph visualization (Note: We do have an awesome free graph/diagram/flowchart editor called yEd). I grew up and studied computer science with specialization in usability and UX in Rostock in northern Germany, which is a quite pretty city. This also wasn’t too long ago, so my professional experience is still quite limited. That doesn’t stop me from reading and trying to learn all kinds of new things in my spare time.

I am a daily bicycle commuter, even in winter. And I love board games.
 
How did you get to Powershell?
 
I read the announcements in the very beginning and actually found the concept quite cool. I think I played around with the beta back then, but not very productively. Around the time PowerShell v1 was current I decided on a whim to start learning it – by trying to golf Project Euler tasks. Since those tasks progress slowly in difficulty and the initial ones are trivial to solve with a bit of programming experience it’s actually quite a nice way of starting out. You don’t need to think so much about how to even solve the problem and instead can concentrate on how to express it in the language before you. And in the process you actually learn quite a few things how to use a language well. In PowerShell’s case this means for me using the pipeline as much as possible. Advice I’ve frequently given to others on Stack Overflow as well.

Eventually, although currently less active, I became involved with Pash, the open-source re-implementation of PowerShell on Mono.
 
Where does you one-liner passion comes from?

Well, I said before, I started learning the language by golfing Project Euler tasks. This eventually grew into a contest with a friend who was using Ruby. It was akin to a battle between the languages (PowerShell is better with date/time stuff, but overall golfs worse, sadly). I wouldn’t exactly narrow it down to only one-liners, though. You can golf quite well on multiple lines, too ;-)

The nice thing about golfing to learn a language is that eventually you learn every obscure little corner of the language and learn how to use it to your advantage. This also sometimes helps with real-world code in explaining surprising behavior of a particular script.
 
How did you approach Task 1?

Task 1 was the trivial one and didn’t leave that much room for varying approaches (at least not approaches that were also short). After initial confusion about the task itself it came down almost immediately to my final answer. First you need to grab all double numbers. You could do this with $n|?{$_-is[double]}, but that’s horribly long. What’s more, we actually need to iterate over the array for that to work, so that was right out.

The nicer approach here was $n-match’\.’ which exploits how comparison operators work in PowerShell: When the left operand is an array, they return all matching values instead of a boolean result. Another thing that’s at work here is that –match implicitly converts its left argument to a string – and those string conversions always use the invariant culture, thus ensuring that the decimal numbers have a dot in them. This implicit conversion is only applied during evaluation of the result, so the resulting items are still doubles, not strings.

Then we obviously needed to find the largest number. After a while of golfing you realize that there is only one way of doing that shortly and that is via sort and either using [-1] or [0], depending on whether you want the first or last result.

After that, the only thing left is trying to obtain the absolute value of the result. The obvious solution would be [Math]::Abs(), but that weighs in at 13 characters. Surely there are better options. Remember the part about implicit string conversion earlier? Turns out we can just use the –replace operator to get rid of the minus sign. Of course, in this case the result will be a string, but hey, that was allowed, so be it.

Another approach I tried, which didn’t work out was (''+($n-match'\.'|sort)[-1]).Trim('-') which has the unfortunate drawback that .Trim() needs the left operand to be a string. And there is no nice way of enforcing that here, thus requiring too many characters to fix that, pushing it to 38 – four more than my actual solution.

How did you cope with Task 2?

Task 2 had an evil restriction, in that no ASCII decimal digits were allowed in the code. This makes some things longer, of course. But then the challenge lies in trying to figure out how to avoid doing those things in the first place.

My very first attempt was abysmal: +-join([char[]]'+,-./'|%{[char](' '.Length+$_)}). 53 characters, just trying to represent the five digits by shifting their Unicode values down by six and then adding that again, converting the result into a char, then joining them into a string and converting that into an integer. Lots of conversions going on here, and the calculation isn’t pretty because I’m not allowed to use numbers (and there was no constant handy I could rely on). One thing is handy here, though, which is the leading unary + to convert the operand to a number; this will stick with us through the end.

A fun thing to try can be to just use control or otherwise unprintable characters. Heck, PowerShell strings may contain almost anything, so getting rid of part of the length above can be done simply by removing the need of adding numbers – there are Unicode characters with numbers 1 through 5. We can just use them (the following code uses the old IBM character set glyphs for those characters, so you can’t just copy the code, but you can enter those characters with Alt+01 through Alt+05): +-join[int[]][char[]]'☺☻♥♦♣'. 28 characters, just about half of the previous attempt, with essentially the same approach.

But maybe there’s another approach that cuts down on the frequent conversions here. Remember that PowerShell strings may contain any character. Maybe there is a Unicode character with number 12345? Well, sure, there is: , U+3039, Hangzhou Numeral Twenty. Now, in this context I don’t particularly care about what the character represents as long as it’s a convenient encoding for the number 12345. +[char]'〹' brings us down to 10 characters, which is much better than the previous attempts. This just leaves the pesky conversion of the string to char (PowerShell has no character literals, but you can cast and convert one-character strings to char). Well, the shortest way of casting a one-character string to char is by indexing into it, but +'〹'[0] wouldn’t be allowed. But there are quite a few things that can get coerced to the number 0 in this context: Uninitialized variables (and thus $null), $false, or, conveniently, the empty string. I’m fairly confident that it’s hard to get shorter than +'〹'['']. Unless we allow digits again.

What's your take on Task 3? It was quite of open question, wasn't it?

It was, indeed and usually I don’t like such questions too much in a contest, since they simply invite way too many non-serious answers. I’ve hosted contests myself, I also posted tasks to the Programming Puzzles and Code Golf StackExchange site. Golfing is ultimately about finding creative ways to solve a task within the confines of the task restrictions. However, in my experience too vague restrictions and conditions just invite people to be lazy and “funny” by posting joke answers one then has to sift through.

Given that you actually accepted my worst attempt at this task it seems like your interpretation of the task was more strict than mine. I interpreted the whitespace requirement way more loosely, coming up with all kinds of other solutions along the way.
As far as the task specification goes, “starting from a string” is too vague. Of course, it implies it has to be input of some sort, but I’d probably have defined it such that changing the string would have to change the output and that, depending on the string, more than one output would be possible.

So, task 3 went through quite a lot of iterations for me, most of them apparently invalid ;-). The first and accepted one was a trivial attempt: Subtract a common number from all characters in the output, then do an unary encoding of the resulting numbers and put that in the string. I chose to be clever with the two uppercase letters by conditionally adding 32, but that didn’t help too much: -join(-split'…'|%{$x=0}{[char]($_.Length+100-32*($x++%5-eq0))}) – 102 characters for the string alone (164 total), and the decoding logic is also quite long (the {$x=0} can be omitted, depending on how one’s stance on running in an unknown environment is – I chose to err on the safe side here). The part in the end can get a bit shorter with 32*!($x++%5), but unary encoding of direct character values is quite long regardless. In fact, I didn’t even bother submitting this variant.

I dabbled a bit with binary encoding and eventually hexadecimal with 15 different whitespace characters, with only minor reduction in character count. Eventually I used unary encoding of indices into a string with all the necessary characters to reduce it to 89, which probably was against your ideas of the task as well ;-).

Should I have accepted the answer "X"|%{"PowerShell"}? What is to you the spirit of a oneliner contest?

No, you shouldn’t. The spirit to me is to have fun, the other part of it is finding creative solutions around the restrictions of the tasks (if there are any). Such solutions don’t require any cognitive effort, many people will come up with the exact same one and to me they don’t represent the spirit of such contests. Now, I’ve said I hosted a few contests myself and one thing I learned is that the task specification should be very clear and, if possible, leave little room for language-lawyering that would result in solutions as the above one. In this particular case it’s difficult to specify the task where there is a clear line between solutions that are allowed and those that are not allowed. I usually try to have such a clear line, which is easiest by not including restrictions for the program at all, apart from the usual ones (e.g. putting the program in the file name and eval-ing that).

What's your opinion of loops in a oneliner... like for loops or while do until?

Well, in your particular case at least for loops weren’t allowed because of the no-semicolons rule. Generally, why not? If they make the solution shorter, I’m all for them. However, in my experience this will only be the case for the for loop which has a few opportunities for shortening that aren’t possible with pipelines. With while or do I never saw any benefit.

What's your take on Powershell for one-liners if compared to other languages you might know?

Mostly it works quite well. It’s about on par with Python, but can’t reach Ruby or Perl levels. Overall still nice for a language that wasn’t designed to be concise. The most annoying parts when golfing are the $ for variables, and forced braces around control structures like if.

Is there any oneliner-oriented community you know and would like to talk about?

Oh, well, there is the Programming Puzzles and Code Golf StackExchange site which has grown quite a bit in recent months. By now I’m rarely active there anymore, though, mostly because of a lack of time.

I have collected a few golfing tips for PowerShell there, too: http://codegolf.stackexchange.com/q/191/15

Thank you, Joey, for sharing your time and knowledge! The 'Hyper-V Best ¨Practices' book is yours!

For those wishing to contact Joey, here's where you can find him:
For those wishing to make the project Euler experience with Powershell, here's the place to go.

 - GUEST BLOGGER JOHN -

As a bonus, let me now introduce you John Roos. John came second in the contest and I got in touch with him as soon as I saw the nice Powershell V5 solution he produced for task 3. He immediately accepted to be my guest blogger today.
 

John, tell us a bit about you and show us the way to your v5 solution to Task 3.

Hi, I am currently working with Business Intelligence within Operations at H&M in Stockholm and spend a decent amount of time with PowerShell. I first started with PowerShell last year. I think it was around September when I wanted to get started with C# and stumbled upon the "Getting started with PowerShell 3.0" series on Channel 9 by Jason Helmick and Jeffrey Snover and I was hooked right away.

When I saw the third task in this contest I immediately started to think about a binary string where "X" would represent number 1 and a space would represent 0. That was my starting point.

Since I already had the result that this one-liner will produce I thought about this backwards. What number would represent a "P" and what number would be "o" and so on. The following code gets the numbers I need to have represented as binary:

[int][char]'P'
[int][char]'o'
[int][char]'w'
[int][char]'e'
[int][char]'r'
[int][char]'S'
[int][char]'h'
[int][char]'e'
[int][char]'l'
[int][char]'l'
Results:

80
111
119
101
114
83
104
101
108
108
Since I am lazy I used an online tool to convert these numbers to binary and ended up with the following:

80 = 01010000
111 = 01101111
119 = 01110111
101 = 01100101
114 = 01110010
83 = 01010011
104 = 01101000
101 = 01100101
108 = 01101100
108 = 01101100
Next is to put it all togehter in one string and then replace 1 with "X" and 0 with a space:

'01010000011011110111011101100101011100100101001101101000011001010110110001101100'.Replace(1,'X').Replace('0',' ')
Result:
' X X     XX XXXX XXX XXX XX  X X XXX  X  X X  XX XX X    XX  X X XX XX   XX XX  '
So now I had the starting string with just "X" and spaces and need to work my way back to the "PowerShell" output. The string need to be split into an array of strings with 8 characters each (one for each letter of the word). Regular expressions works well for this:

[regex]::Matches(' X X     XX XXXX XXX XXX XX  X X XXX  X  X X  XX XX X    XX  X X XX XX   XX XX  '.Replace(' ',0).Replace('X',1),'\d{8}')
Now lets pipe it further so that each binary string can be converted to [INT] (using base 2 since its binary) and then convert that to [CHAR].

[regex]::Matches(' X X     XX XXXX XXX XXX XX  X X XXX  X  X X  XX XX X    XX  X X XX XX   XX XX  '.Replace(' ',0).Replace('X',1),'\d{8}')|%{[char][Convert]::ToInt32("$_",2)}
Result:
P
o
w
e
r
S
h
e
l
l
Almost there. Now the result need to be converted from an array to a string. In Powershell 4 it doesnt really work well with string for this particular case:

[string]([regex]::Matches(' X X     XX XXXX XXX XXX XX  X X XXX  X  X X  XX XX X    XX  X X XX XX   XX XX  '.Replace(' ',0).Replace('X',1),'\d{8}')|%{[char][Convert]::ToInt32("$_",2)})
Result:
P o w e r S h e l l
I dont want those spaces between every character, but fortunately in Powershell 5 we get access to a new string method called New() which accepts an array of chars. So lets encapsulate the entire thing with this method:

[string]::new(([regex]::Matches(' X X     XX XXXX XXX XXX XX  X X XXX  X  X X  XX XX X    XX  X X XX XX   XX XX  '.Replace(' ',0).Replace('X',1),'\d{8}')|%{[char][Convert]::ToInt32("$_",2)}))
Result:
PowerShell
Now I have the answer to the question, but its 191 characters long. At this point I realised that all the binary strings start with "01". What if I remove that from the long string and add them in the loop in the end? In that case I would have to split the string with regex on only 6 chars instead of 8 and add "1" when converting back to integers (the leading zero is assumed since its binary):

[string]::new(([regex]::Matches(' X    X XXXXXX XXXX  X XXX  X  X  XXX X   X  X XX XX  X XX  '.Replace(' ',0).Replace('X',1),'\d{6}')|%{[char][Convert]::ToInt32("1$_",2)}))
The one-liner is now down to 172 characters and thats as far as I got. I tried lots of different solutions but this was the shortest I could come up with.

Thanks John for your explanation!

For those wishing to contact John Roos, here's where you can find him:
A last mention goes to a couple of fellow heavyweigth Microsoft MVPs who took part in the Contest:
  • Bartek Bielawski, who wrote a must-read blog post on his solutions. Check it here. Bartek was the winner of the Powershell Scripting Games in 2011, and he is an author at Powershell Magazine with excellent skills in Powershell golfing.
  • Emin Atac, who wrote an excellent blog post on his approach to the three tasks. Check it here. Even if Emin is not on the top-10 (just because he offered a solution to task 3 that didn't match my very subjective restrictions), this guy knows what he is talking about.
That's all for the Powershell Contest 2015. I hope you enjoyed reading the expert answers of our winners. Personally, I was very happy to host such an event and I want to thank you everyone who entered the game as well as our sponsor, Packt Publishing, for offering the prize.

4 comments:

  1. Please, publish BiS solutions for every task. It will help to learn best practices for onliners :)

    I really impressed with [''] array enumerations and '+' for [int] conversion but can discuss about '-match"\." ' vs '-is[double]'
    the first breaks the "The one-liner must work also with different values of $n" rule. think about $n='a.b.c.d', .....

    ReplyDelete
    Replies
    1. Max,
      all other submissions are online on the previous post.
      I was quite happy with Johannes solution, but I see your point. And have hade a decent amount of mail from people that did not agree on some points, but, I see it positively: I have created interest. Interest about the Contest. Interest around Powershell. Interest around the people who solved it quickly/creatively. And I supose we all benefit from such an event because we are given an occasion to learn. I speak for myself too.
      That what it was all about :-)
      If you want, if are free to be a guest blogger and share your point of view. Jus drop me an e-mail.

      Delete
    2. Yes, It's all about learning.

      I see all submissions, but not all of it have lengh posted. and I think (sorry for laziness ;) ) that you have all of it well organized to post the best :)

      I take a deep look...

      Thanks for your offer but my literary ability and knowledge of English do now allow me to write any noticeable article :)

      Delete
    3. Max, indeed I did not think about strings containing a dot in my solution. Very good point and a lapse on my part. In that case the shortest solution I can think of is 41 characters, replacing the -match with the traditional |?{$_-is[double]}.

      In any case, that also shows something I highlighted a bit in my interview, that I'd rather have strict guidelines and a good set of test cases to work with. You can weed out many joke answers or those that don't work properly that way.

      Delete

Related Posts Plugin for WordPress, Blogger...