I recently discovered, via reddit, a link to another programming-oriented blog. There, the Blogger indicates that they have created 5 problems, and, if anybody cannot solve all of them within an hour, then they should not be called a programmer.
Already this reeks of a “fizzbuzz” style test, but we get a nice dose of hubris as he prescribes that he has some authority to say when other people should or should not list themselves as programmers.
However, what really took the case was inevitable- in his series of blog posts- (which he cannot demononstrate as having written all within an hour, I might add) he provides an incorrect solution. Therefore, by his own definition, he should no longer call himself a programmer. The end result is basically like somebody saying “Only idiots have problems with they’re grammar”
In the interest of something coding related, let’s see what that problem… problem was, and try to create a C# solution. I won’t be arguing that anybody unable to solve it shouldn’t call themselves a programmer, mostly because I suspect I may make mistakes myself- and claims that require such perfection of me are likely to result in some well-placed “karma”.
Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.
I took a rather- brute force approach:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
class Program { static void Main(string[] args) { RunTests(); } private static int GetFullValue(IEnumerable<int> vals) { String strmake = String.Join("",from p in vals select p.ToString()); int tryresult = 0; if (int.TryParse(strmake,out tryresult)) return tryresult; return 0; } public static String ArrangeNumbers(IEnumerable<int> Numbers) { var getenumeration = Permutations<int>(Numbers).ToList(); var resultenum = (from p in getenumeration orderby GetFullValue(p) descending select p).ToList(); return String.Join("",resultenum.First()); } public static void RunTests() { int[] Test1 = new int[]{50,2,1,9}; int[] Test2 = new int[]{17,32,5,16,500}; int[] Test3 = new int[] { 420, 42, 423 }; foreach(int[] iterate in new int[][]{Test1,Test2,Test3}) { Console.WriteLine(String.Join(",",from p in iterate select p.ToString()) + "=" + ArrangeNumbers(iterate)); } Console.ReadKey(); } private static IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> Collection) { //Generate all permutations. We do this recursively by taking each element, and for each one //we will yield an enumeration consisting of that element followed by permutations of all the other elements. //The end case is of course when the enumeration contains only one element. var count = Collection.Count(); if (count == 1) yield return Collection; else for (int index = 0; index < count; index++) { foreach (var p in Permutations(Collection.Take(index).Concat(Collection.Skip(index + 1)))) { yield return Collection.Skip(index).Take(1).Concat(p); } } } } |
Basically it takes all the permutations of the list if elements returned and finds the permutation that results in the largest number when concatenated. No doubt this can be made more efficient. However…
Requirements
Having specific requirements is important. In this case, the academic exercise did not come with any requirements, and all the test cases provided are incredibly short. Therefore, it is reasonable to create an implementation that works best for short lists of items. It also doesn’t suggest that speed is important- it doesn’t say to make the method as fast as possible- it merely dictates the expected output. The method I wrote does it rather brutally but is IMO easier to reason about.
Or, that is what I would say- if it worked! What happens? Well, if we give it {17,32,5,16,500}, it tells us 1755003216, but the correct answer is 5500321716. How did the brute force algorithm go so wrong?
The answer is deceptively simple and is localized in our GetFullValue() function. The intent of this function is to take an enumeration of integers, slap them together into a string, and then parse them back into an integer. You can perhaps see where things go wrong. The “real” answer- 5500321716- is larger than the maximum size of an int. TryParse fails, and the function returns 0, which means the “correct” value gets sorted as 0.
The “Fix” is to replace the int with a decimal data type for that function, and the function works again. It should be noted that this is a less-than-performant solution by quite a margin- and in fact, it’s even longer than the alternative, which compares the concatenation of the first and second value with the concatenation of the second and first value and inverts the result. Here is a full implementation which uses/compares both versions, including timing:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
class Program { static void Main(string[] args) { RunTests(); } public static decimal GetFullValue(IEnumerable<int> vals) { String strmake = String.Join("",from p in vals select p.ToString()); decimal tryresult = 0; if (decimal.TryParse(strmake,out tryresult)) return tryresult; return 0; } public static String ArrangeNumbers(IEnumerable<int> Numbers) { var getenumeration = Permutations<int>(Numbers).ToList(); var resultenum = getenumeration.Max(u=>GetFullValue(u)); return String.Join("",resultenum); } public static String ArrangeNumbers2(IEnumerable<int> Numbers) { var compareinstance = new SetPowerComparer(); var resultenum = Numbers.OrderBy((x) => x, compareinstance); return String.Join("", resultenum); } public static void RunTests() { int[] Test1 = new int[]{50,2,1,9}; int[] Test2 = new int[]{17,32,5,16,500}; int[] Test3 = new int[] { 420, 42, 423 }; foreach (Func<IEnumerable<int>, String> func in new Func<IEnumerable<int>, String>[] { ArrangeNumbers, ArrangeNumbers2 }) { Stopwatch sw = new Stopwatch(); sw.Start(); foreach (int[] iterate in new int[][] { Test1, Test2, Test3 }) { for (int i = 0; i < 500;i++) { var result = func(iterate); } Console.WriteLine(String.Join(",", from p in iterate select p.ToString()) + "=" + func(iterate)); } sw.Stop(); Console.WriteLine("Elapsed:" + sw.ElapsedTicks); Console.WriteLine("----"); } Console.ReadKey(); } private static IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> Collection) { //Generate all permutations. We do this recursively by taking each element, and for each one //we will yield an enumeration consisting of that element followed by permutations of all the other elements. //The end case is of course when the enumeration contains only one element. var count = Collection.Count(); if (count == 1) yield return Collection; else for (int index = 0; index < count; index++) { foreach (var p in Permutations(Collection.Take(index).Concat(Collection.Skip(index + 1)))) { yield return Collection.Skip(index).Take(1).Concat(p); } } } } class SetPowerComparer:IComparer<int> { public int Compare(int x, int y) { String xs = x.ToString(); String ys = y.ToString(); return -(xs + ys).CompareTo(ys + xs); } } |
Overall, an interesting problem. I don’t think that being unable to solve it in an hour means a person needs to hand in their programming badge and gun, though. I like to think of such problems as “watertight” abstractions- this is in contrast to a leaky abstraction. When designing an algorithm, the implementation can be of importance. For example if an algorithm deals with Invoice numbers and we know that no invoice number can start with 1, than that can be applied to optimize any number of algorithms to save time. These sorts specifics tend to prevent the implementation and use of a “pure” academic implementation of any number of algorithms. That isn’t to suggest such exercises are futile, as it is often nice to simply attack a problem that doesn’t have annoying unknowns and require tracing through a 25-year history of ancient data schemas in order to properly reason about.
Have something to say about this post? Comment!