Weekly Challenge 140

Challenge, My Solutions

So I discovered after doing last weeks challenge, that I was basically copying my Perl code and then converting it to Python. I've decided for future challenges I'm likely to do it the other way as Python is what challenges me the most.

TASK #1 › Add Binary

Task

You are given two decimal-coded binary numbers, $a and $b.

Write a script to simulate the addition of the given binary numbers. The script should simulate something like $a + $b. (operator overloading)

My solution

So for this task, I have a class called BinaryDecimal, that holds a value, which is a decimal number. I make a check that this value contains only ones and zeros.

I then use the __add__ method which overloads addition operator that adds two BinaryDecimal values together. Python does make a distinction between integers and strings so there will be no short cuts to be had :)

I'm sure I don't need to explain to Team PWC members how we were taught addition at primary school. I take the last digit of each number (using the modulus operator), and the carry value and add them up. If the result is two or 3, I set carry to be one. If the result is one or 3, I add the appropriate value to the result variable. I then divide both numbers by ten and continue until we have exhausted both numbers and the carry value.

For this task the Perl code is a transliteration of the Python code. All the extra my, dollar signs, semi-colons and brackets does make me appreciate Python. The only major change is that you use the overload module to overload operators, and we use package instead of class.

Examples

$ ./ch-1.py 11 1
100

$ ./ch-1.py 101 1
110

$ ./ch-1.py 100 11
111

TASK #2 › Multiplication Table

Task

You are given 3 positive integers, $i, $j and $k.

Write a script to print the $k^th element in the sorted multiplication table of $i and $j.

My solutions

When doing these challenges, there usually is a point where you decide how much work do you want to do to achieve an optimal solution. This is one such task. There are two ways to tackle this, so I took different paths with each language.

For the Python code, I use brute force: Calculate all the products, sort the array, and display the appropriate number. This works, and works well.

However, if you start using really large numbers you can quite easily exhaust your RAM by storing such a large array. For my Perl code, I use a smarter solution, where the maximum size of the array is 2 * $k

The logic is as follows:

1) Iterate from 1 to $i using the variable $m
2) Work out the maximum number of products we need to find

• If the array size is already $k items, then the result of the last value divided by $m is the maximum.
• Otherwise we calculate the minimum of $k and $j 3) Push to the array the product of these numbers multiplied by $m 4) Sort the array and trim it.

This is much more efficient, and means calculating really big numbers is easy as. Probably overkill given the examples, but fun to do anyway.

Examples

$ ./ch-2.py 2 3 4
3

$ ./ch-2.py 3 3 6
4

$ ./ch-2.pl 2 3 4
3

$ ./ch-2.pl 3 3 6
4