Posts

Completing the time and levelling the letters

Completing the time We are given a time, such as 12:34, with one of the digits replaced by '?'. We are asked what digit when substituted for the '?' results in the maximum valid time. There are six cases to consider: The first digit is ? and the second is [0123] - the answer is 2 The first digit is ? and the second is [456789] - the answer is 1 The second digit is ? and the first is 1 - the answer is 9 The second digit is ? and the first is 2 - the answer is 3 The third digit is ? - the answer is 5 The fourth digit is ? - the answer is 9 This is a rather messy set of conditions. The easiest - and perhaps clearest - way of performing the task is just a set of if/elsif clauses using the above logic, and that's what I submitted. I used split to put the characters into in array to make my conditions easy to read - for example  $chars[0] eq '?' - but it could equally be done using regular expressions - for example $string =~ m|^...\?| is true if the 4th characte

All the binaries and find the odd man out

All the binaries We are asked to find all the binary numbers 'of length $n'. The examples show that 'length $n' means 'containing n digits' and that the desired solution includes those with leading zeroes. These numbers are simply all the integers from 0 to 2^$n - 1, and we can simply loop over that range, outputting the numbers in binary format using sprintf's binary option.  It looks a little odd: sprintf("%0${n}b", $_) but if, say $n == 4, that amounts to  sprintf("%04b", $_) which means 4 binary digits with leading zeroes. Find the odd man out We are given a list of strings, such as: "adc", "wzy", "abc" From each of these strings we are to form a 'difference array', which contains the alphabetical distance of each letter in the string from the preceding one. So for "adc" the difference array is (3, -1) because 'd' is 3 letters after 'a' in the alphabet, and c is 1 letter

Flipping easy and distributing fairly

Flipping binary numbers Our first task this week is to take a positive integer, render it in binary, swap the zeroes for ones and vice versa, and output the result in decimal. It's tempting to use the Perl bitwise not operator (~) to flip the bits, but inspection of the examples shows that's not quite what's wanted. The reason is that while we normally express 4, for example, as 100 in binary, the computer consider it to be 0000000000000100. Applying the not operator to that gives us 1111111111111011, which isn't the desired answer. Now there are various ways around that, but note that the supplied number will always start with a 1 in its simple binary representation, so its flipped value will start with 0. And in its 16 (or whatever) bit representation, that will be preceded by a lot of 1s. So as it's just a string, we can safely just strip off all the leading 1s using s|^1+||, and the algorithm boils down to just two lines: $flip = sprintf('%b', ~ $test); 

The twice largest and number of cuties

The twice largest We are given a list of integers and asked to write a script to find out whether the largest item in the list  is at least twice as large as each of the other items. The simplest way to do this is to reverse-sort the list, and then the condition is simply whether the first item in the sorted list is no less than double the second. Given a modern computer this will complete in milliseconds in even quite a long list. But when I started programming over 50 years ago sorting was something to be avoided as it took so long, especially if the list of items to be sorted was more than would fit in memory.  Back then, 128 kB was a large computer, so sorting things like a payroll took hours, with numerous stops to change tapes (about 40cm in diameter) on tape drives which had to be cleaned every hour with cotton buds and isopropanol. So a better algorithm - for 1970 - would be to make a single pass through the list, checking each value to see if is the largest seen so far, and al

Capital test and ambiguous encoding

Proper capitalisation Task 1 this week gives us a string comprising capital and lower case letters and asks us to determine whether it follows one of these patterns of capitalisation: Challenge, challenge, CHALLENGE. Generally I steer clear of hard-to-follow one-liners, but this one is fairly simple: $test =~ m/^[A-Z]?([a-z]*|[A-Z]*)$/ ? 1 : 0; In words, the string follows the rule if: it starts with zero or one capital letter, and it continues with either zero or more capital letters, or zero or more lower case letters.  So that wasn't too hard, was it? A strange encoding Task 2 gives us a string of digits and asks us to decode it left to right, assuming 1 means A, 2 means B down to 26 means Z. Of course this is ambiguous, because 11 could mean AA or it could be the 11th letter, which is L. So we are to find all the possible decodings and present them in alphabetical order. If we start at the beginning of the string, the first digit must be 1-9, and that could correspond to A-I. B

The smallest greater and the shortest slice

The smallest greater Our first task this week is as follows: You are given an array of characters (a..z) and a target character. Write a script to find out the smallest character in the given array lexicographically greater than the target character. The best way to approach this seems to me to sort the array, and then look for the first character in the sorted array that follows the target character alphabetically. As the array is sorted this is bound to be the smallest such character. This works for all of Mohammad's examples except the last, where the array is 't, g, a, l' and the target character is 'v'.  So I would say there is no answer, though Mohammad's example says the answer is 'v', which isn't in the array. And the shortest slice The second task says that we are given an array of two or more non-negative integers and are asked to write a script to find out the smallest slice of the array having the same degree as the array itself. We are t

Divisible pairs and reduce to nothing

Divisible pairs Task 1 supplies us with a list of integers and asks us to count the pairs selected from the list whose sums are divisible by a supplied integer. The obvious way to do this is to generate all the pairs and check their divisibility by the given divisor. All the examples given include only unique positive integers. The task is not significantly different if zero and negative integers are included, but if the same integer appears more than once (eg list = 1, 2, 3, 3, divisor = 4) do we count distinct pairings (1 and the first 3, 1 and the second 3)  or merely distinct pairs (just 1 and 3). Reduce to nothing Task 2 as stated is impossible. Applying the supplied rules to any pair of starting x and y will never result in both x and y reaching zero, because: Each operation reduces either x and y and leaves the other unchanged So the values before the last operation would have to be (0, n) or (n, 0) where n > 0 But that isn't possible because subtracting 0 from n cannot