Daniel_Maclise_-_Caxton_Showing_the_First_Specimen_of_His_Printing_to_King_Edward_IV_at_the_Almonry,_Westminster

Five programming problems blah, blah, blah…

A couple of days ago, this blog post hit the front page of /r/programming. Apparently, every software engineer should be able to solve the five problems – in under an hour. (in fact, according to the author, if you can’t “you need to stop calling yourself a ‘Software Engineer'”)

Fantastic fun was had in the comments: egos clashed, tribes were formed, OP’s honour came into question. Most people seemed to agree that the problems, especially 4 and 5, were too difficult. The next morning, however, OP emerged from the shadows, and brashly rebuffed his critics, posting his own solutions to problems 4 and 5 on his blog.

Problem 4, in particular was tricky: it seemed easy at first, but several solutions (including OP’s original solution) didn’t work for some edge cases. I tried my hand at it in Swift.

Problem 4

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.

This problem was far more difficult than I first thought. I got stuck down several dead-ends with ideas for solutions, and made the same mistake as OP.

The first way to look at it is to consider single digits, say [3, 4, 5]. What you want to do is to have the largest digit multiplied by the largest number – as in, have the largest digit furthest to the left. Here, we’ve got 5. Put that to the left, and it’s 500. Bigger than any of the other available digits (which would make 400 and 300). So the answer, for single digits, is to sort in descending order. (543)

9030For numbers bigger than ten, you could start out with the same idea – sort in descending order. Except it doesn’t work. for [30, 9], say, 930 is obviously bigger than 309. The next idea is to pad out the digits – you’re really most interested in the first digit, so pad with zeroes to the right, and then compare. (this was OP’s first solution) So [9, 30] becomes [90, 30], sort in descending order, remove the padding, 930’s your answer.

But there are edge cases. Oh, so many edge cases. Take [51, 5] for instance. Pad them out, [51, 50], sort them, [51, 50], unpad and combine: 515. Wrong. 551 is what it should be.

Right. No problem. We’re all grown-ups here: let’s take a look at what’s going wrong. What you should really be comparing is the two options – 515 vs 551. A little examination, and it looks like the thing we should be comparing on isn’t the number padded with zeroes, it’s the number padded with itself. As in, 5 doesn’t go to 50, it goes to 55.

jojo.001Does it work? You bet it does: [51, 5] -> [51, 55] -> [55, 51] -> [5, 51] -> 551. Nice. Gosh, I’m clever. OP didn’t even spot that edge case.

Nope, still wrong. (a pattern’s beginning to emerge here…) Look at [513, 51]. Here we go: [513, 51] -> [513, 511] -> [513, 511] -> [513, 51] -> 51351. Smaller than 51513. Great.

Around now I began to realise this padding business looked like a dead-end. OP had posted a newer solution that no-one had found edge cases for, and I considered just trying that approach. It wasn’t very elegant, though, and I felt like I was very close to a fix for this method. So I tried again.

jojojo.001Looking back at the [513, 51] example, it’s clear why it’s incorrect: when you’re comparing the extended versions, you’re comparing 513 and 511, but in the actual number created, the digit following 51 isn’t another one. It’s the first digit of the next number. So… what if we padded with the digits of the next number? Is that it? Is that the answer? Let’s try: [513, 51] -> [513, 515] -> [515, 513] -> [51, 513] -> 51513.

Obviously not. That solution was reached through logic and some experimentation. No way is it going to be correct. Here we go, let’s take [31, 313]. [31, 313] -> [313, 313] -> [313, 313] -> [31, 313] -> 31313. Smaller than 31331. Yeah, padding is a dead-end.

What was OP’s new method? He took both numbers, converted them to strings, and added those strings together, in the two different orders. (left-hand-side + right-hand-side vs right-hand-side + left-hand-side) He then compared those two strings, and used Java’s sort function to give him his answer. I probably wasn’t fair earlier: it actually is elegant. Especially compared to what I had come up with. Here’s what it looks like in Swift:

func largestNum(nums: [Int]) -> Int {

  return nums
    .map() {"\($0)"}
    .sorted() {lexicographicalCompare($1 + $0, $0 + $1)}
    .reduce("") {$0 + $1}
    .toInt()!

}

let answer = largestNum([31, 313]) //31331

I didn’t like it, though. Converting to strings and back again? Nah… I like my numbers kept as numbers, thank you very much. It’s how I was raised. So, if we wanted to stay in numberland and do this concatenation thing, what would that look like? As in, if we wanted to do something to 5 and 6 to get 56, what would it be? Take the left-hand number and multiply it be ten, add it back to the right. Right, that’s our first step. What about, say 5 and 67? Left hand number, multiply by 100 this time. Ok, where does 100 come from? We can’t round to the nearest integer, can’t round to the nearest 10, we really need the next highest power of ten. log10 it is, then. log10 gives you back a smallish number, get the ceiling of that. Right, now put ten back to that power. Perfect! There’s your 100, or 10, or whatever. Here it is in Swift, as an infix operator:

infix operator |+ {associativity left precedence 160}

func |+(lhs: Int, rhs: Int) -> Int {

  return lhs * Int(pow(10,(ceil(log10(Double(rhs)))))) + rhs

}

let fiveSix = 5 |+ 6         //56
let fiveSixtySeven = 5 |+ 67 //567

Doesn’t that just look lovely? Nice little infix operator, reasonably short function. Putting it into the largestNum function:

func largestNum(nums: [Int]) -> Int {

  return nums
    .sorted() {($0 |+ $1) > ($1 |+ $0)}
    .reduce(0) {$0 |+ $1}

}
let ans = largestNum([1, 2, 3, 4, 63, 636]) //636634321

Great! Looks reasonably clean, get to use the standard library sorted() function, all that. Even better, since Swift’s string handling is so slow, this version is about 5 times as fast as the string version, even though there are so many operations.

class NumConcTests: XCTestCase {

  func testMethodOne() {
    self.measureBlock() {
      for nums in numsList {
        largestNumString(nums)            2.810 sec, 3% STDEV
      }
    }
  }

  func testMethodTwo() {
    self.measureBlock() {
      for nums in numsList {
        largestNumLog(nums)               0.572 sec, 2% STDEV
      }
    }
  }

}

At this stage, I had a pretty decent testing system set up, comparing the string version to mine, and seeing if there were any cases where the string version’s concatenated number was larger. I had even written a function that took every possible combination of the numbers it was given, and returned the largest concatenation. I was running a few thousand random numbers through, testing away.

Yeah, you probably see what’s coming. On the third run he rose again, ascended into the console, and completely ruined my fun. A stupid, smug edge case. I nearly didn’t fix it. I had wasted time, a better solution existed, there was something new on reddit. But I looked again. When the right-hand side number was itself a power of ten, the left-hand side was getting multiplied by a number ten times to small. It was maybe the easiest fix out of all of the fixes (add one to the right-hand-side number), but it took the most out of me. Here it is, then: my amateurish, overcomplicated, probably-still-wrong solution to problem 4:

infix operator |+ {associativity left precedence 160}

func |+(lhs: Int, rhs: Int) -> Int {

  return lhs * Int(pow(10,(ceil(log10(Double(rhs + 1)))))) + rhs

}

func largestNum(nums: [Int]) -> Int {

  return nums
    .sorted() {($0 |+ $1) > ($1 |+ $0)}
    .reduce(0) {$0 |+ $1}

}

(By the way, it doesn’t work with zeroes. But I’m not counting that as an edge case. I don’t think I could take it.)

Advertisements

3 comments

  1. Pingback: Brute Force? What Brute Force? | Big O Note-Taking
  2. galinha pintadinha completo · January 1, 2016

    Para animar e incentivar os pequenos corredores, a própria Galinha Pintadinha estará no
    nearby.

    Like

  3. Attractive component of content. I just stumbled
    upon your weblog and in accession capital to
    assert that I get actually enjoyed account your weblog posts.
    Any way I will be subscribing in your augment or
    even I achievement you get entry to persistently rapidly.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s