Shortest 5 Wrap up

This codefu shortest was all about python.
Very shortly everyone realized that in python the solutions are much shorter, due to not specifying the types and working with lists and sets.

The winner is: SkyDriver

Also special congratulations to best problem solutions:

Problem 100: lazzrov, anikov, hsilomedus with 408 points
Problem 200: SkyDriver, bedjovski, FILOZOF, lazzrov, mmarko, kamikaza, vl4d1m1r4, anikov, hsilomedus, boro with 409 points
Problem 300: anikov with 401 points

Problem 1

Problem description
The solution is pretty simple once you realize that we just need to generate all the possible elements (Ai), put them in the list and return the size of the list.

Some tricks here:
The for cycle need to loop m times, and this is achieved by looping through a list of m. Instead of range(m), we can use [0]*m which is 3 characters shorter
Also, python can have chained assignments, so we can chain the a[A] and A assignments resulting in:

Problem 2

Problem descrption
The solution here is to split the string by ',', then reverse the order and then join again by ' ', and in the end capitalize the first character.
Python provides all of these so the solution is quite straightforward.

We can do additional optimization by using list[::-1] instead of reversed(list) to reverse the elements.

Problem 3

Problem description
This an interesting problem.
It can be solved with recursion or dynamic programing with either 3, 2 or one dimensional array.

First thing in the dynamic programming is to carefully define the state.

The state we can use here is the maximum skill when n consecutive pilots are used.
We start with an array z[] with K elements.
z[0] means maximum skill of all previous pilots when the last pilot was not used.
z[1] means max skill when the last pilot was used
z[n] means max skill when last n consecutive pilots were used
Obviously we don't need to have z[K + 1] because we can't use more than K consecutive pilots

We start with the first pilot, iterate and add all pilots one by one to the list.
When assigning each pilot skill, we choose to either use the pilot or not.
When we don't use the pilot, then we need to put the maximum of all z[] elements in z[0]
Otherwise, we go through all consecutive skills in z[] (iterate by n = 1 to n <= K) and we put z[n+1] = z[n] + s[i]

The solution would be like:

If we pass the second for in reverse order, we don't need the temporary list.

Now, by carefully examining the solution we realise that we:
- put max(z) as the first element
- shift all other elements to the right and add s[i] to them.

So, here is the final, neat solution in less than 100 characters.

New topic