Task 1: Prime Partition
Task
You are given two positive integers, $m and $n.
Write a script to find out the Prime Partition of the given number. No duplicates allowed.
My solution
This is one of those interesting tasks where there are multiple ways to tackle it. And the method really depends on the value of m and (more importantly) n.
I took the quick and easy option, given that the examples provided have small values. In this method, I collect a list of all primes <=m and store it in a list (array in Perl) called primes. I then use itertool's combinations method to work out all combinations of size n. If I find a combination that sums to the value of m, I print the results and exit. If I don't find one, I also print an appropriate message.
For the Perl version, I use the Algorithm::Combinatorics module to perform the same function that Python's itertools provides. This is available as a RPM package in Fedora (the OS my server uses), so seems like a good choice.
Now for a discussion about the case where m and n are larger. The problem with the above method is when n is larger, the number of combinations grows exponentially. This leads to a lot of calculations where the sum is clearly going to be too high or too low.
Take for example trying to find 10 primes of 7920. The 1000th prime number is 7919. As I sorted the list highest to lowest, it means the first gazillion (well not quite, but it is a number with 26 digits in it, 999 × 998 × ... × 991) combinations will always result in a number that is too large. Rather than working through all combinations, we can eliminate ones that clearly won't be valid. For example, if we take the first number as 7829 (the 990th prime), we know that the sum of the remain digits can't be larger than 91.
However, the example clearly sets an expectation that m and n are (relatively speaking) on the smaller side, so the brute force method is good enough.
Example
$ ./ch-1.py 18 2
(13, 5)
$ ./ch-1.py 19 3
(11, 5, 3)
Task 2: Five-number Summary
Task
You are given an array of integers.
Write a script to compute the five-number summary of the given set of integers.
My solution
The easy solution would just be use numpy which supports this out the box, but where is the fun in that? If this was code I needed to use at work, indeed import numpy would be at the top of the script.
This task is pretty straight forward, so no real explanation is needed. Take the integers, sort them from lowest to highest, and find the position at each quartile. If that position is not a single value, then take the two values and half it.
Example
$ ./ch-2.py 0 0 1 2 63 61 27 13
0, 0.5, 7.5, 44, 63
Top comments (0)