adamcrussell

Perl Weekly Challenge 030

I was traveling for work most of this past week and so the creativity behind the solutions to this week's Perl Weekly Challenge might not be at exactly the highest level! Then again, although stressed for time, I think my preferred solutions to these problems are as straightforward as what I ended up implementing anyway.

Part 1

Sample Run

$ perl perl5/ch-1.pl
2022
2033
2039
2044
2050
2061
2067
2072
2078
2089
2095

What I Did

I have used Sakamoto's algorithm previously for day of week calculations, most recently for challenge 019. Here I repeat that calculation but for every 25 December for the years stated and check if the result is Sunday, which has a numerical value of 0. If the result does happen on a Sunday the year is printed.

Part 2

Sample Run

$ perl perl5/ch-2.pl
-7 9 10
-6 8 10
-5 7 10
-5 8 9
-4 6 10
-4 7 9
-3 5 10
-3 6 9
-3 7 8
-2 4 10
-2 5 9
-2 6 8
-1 3 10
-1 4 9
-1 5 8
-1 6 7
0 2 10
0 3 9
0 4 8
0 5 7
1 2 9
1 3 8
1 4 7
1 5 6
2 3 7
2 4 6
3 4 5

What I Did

First off, the challenge statement didn't specify any particular range of numbers to consider. Obviously, if we only consider positive numbers then the total number of combinations possible is small, only 11, but if we include negative numbers an infinite number of combinations are possible. For fun I decided to consider negative numbers. Clearly when we consider triplets from a wide range of values the number of combinations because extraordinarily large and so for this challenge I selected a range of [-10, 10]. I don't compute all he combinations directly, instead I decided to rely on Math::Combinatorics to provide these. Each combination is evaluated for the two criteria (i.e. at least one even number and must sum to 12) and any passing both criteria are printed.


Notes

The number of combinations possible are computed as follows. Let's consider the case of triplets selected from 21 numbers, as in the example of all the integers in the interval [-10, 10].

C(n,r)   =    C(21,3)

=                21!
           -----------
           (3!(21−3)!)

=          1330

So in the solution to Part 2 we evaluated 1330 possibilities. How many would we have to evaluate if we expanded the range to [-100, 100]? 1,333,300!

For a tenfold increase of the input we have a thousand fold increase in the output. This rapid growth from small input changes is what is often called a combinatorial explosion.

To read more on this, the Binomial Co-efficient, I suggest starting with the Mathworld article.

Comments for this post were locked by the author