Nick Jones

This problem was asked by Twitter:

Started 11:53

"Given a list of numbers, create an algorithm that arranges them in order to form the largest possible integer

For example, given [10, 7, 76, 415], you should return 77641510"

So first thing's first let's set up a super basic testable version of all of this before we start even thinking about the solution just so we have it out of the way:

let integerList = [10, 7, 76, 415]
func integerMasher(with list: [Int]) -> Int {0} 
let isValid = integerMasher(with: integerList) == 77641510

So this gives us a way to know if what we're doing works which is great

Initial thoughts

So as we're dealing with an array we'll have to iterate at least once no matter what. Swift language buit in functions like reduce, map, etc loop under the hood so there's no escaping this

Initially my thoughts were that the first digit in a given number is the most important in terms of where it 'ranks' irrelevant of how big the number 'actually' is"

What I mean by this is even though 899 is clearly bigger than 9 in terms of normal integers; with just these two numbers in our given scenario a result of 9899 is larger than 8999 when combining 899 and 9 in the available combinations for these two integers

This is interesting because does it mean that the shorter the number in terms of digits the 'greater' it is in terms of where it should sit in the final number?

Not always now that I think of it because what really matters is the "up-front" digits

I wonder if an 'easy' solution would be to 'fill' any numbers with less than three digits with 9s and then sort by those numbers

i.e. with our original numbers 7 would become 799 and 76 would become 769.

We could then just store both the original number and the 'modified' number, sort by the 'modified' number and then combine all of the 'original' numbers together

For fun though we can implement this first and maybe it'll give us some hints as to a better approach along the way!

func masher(with list: [Int]) -> Int {
    guard let longestNumber = list.sorted(by: {
        String($0).count > String($1).count 
    }).first else { return 0 }

    let longestNumberLength = String(longestNumber)
    return 0
}

Now that I've started implementing this I've realised how much 'overhead' is really required to get this solution working

Not only do we have to sort our array but we have to convert every value to a String only to then get the first element out, convert it to a String and then from there start converting every value in the array

Whilst the solution will 'work' it feels janky even as a 'working' solution so let's drop it temporarily and approach it differentl

With just raw integers themselves I don't think there's a way of sorting these as the larger numbers will always break any logic we have, that is to say that 111 is far greater than 9 and there's no esacping that

It would be great to be able to get the length of these numbers without having to cast them to strings

If we could do that then we could start making some real progress!

Next steps

I started checking online for a mathematical based approach and came across the fact that the log10 of a number gives you the length of the number in digits like in this situation:

let singleDigitNumber: CGFloat = 1
print(log10(singleDigitNumber))
0

let tripleDigitNumber: CGFloat = 100
print(log10(tripleDigitNumber))
2

This is great as it helps out with our solution!

For now though we can use this to come up with a solution

It's an interesting problem because the longer the number the less 'likely' it is that it'll be near the front of our end number, 9999998 comes after 9 for example, but we can't just filter by 'length' because 9999998 still comes before 8 🤔

Maybe our original masher solution is the best way to start this off in the end!

Despite looping back round to our original idea we do now have a much nicer way of getting the 'longest' number as well as the length of it because of log10 so let's go again

Because we want to make use of log10 (which is a function of CGFloat) a lot we'll start by first recasting our array of Integers so that we're not constantly recasting the same values unnecessarily

func masher(with list: [Int]) -> Int {
    let floatArray = list.compactMap { CGFloat($0) }
}

Now we want to get the longest number in terms of digits and from that get its length so we can use this to pad out our other numbers to match its length

guard let longestNumber = floatArray.sorted(by: { 
    log10($0) > log10($1) 
}).first else { return 0 }
let longestNumberLength = log10(longestNumber)

Now that we've got the greatest length we can start building our our custom list with both properties

We'll make a Struct to store these numbers as it's a bit more 'swifty'

struct NumberBox {
    let originalNumber: Int
    let modifiedNumber: Int
}

So with our new Struct to store our values and our initial approach let's go ahead and start looping over our new `floatArray`

var numberBoxes = [NumberBox]()
for float in floatArray {
  //All of the following logic will take place in here 
}

The first thing we'll want to do is if a number is already at the 'max' length or the same length as the longest number in the array then we'll just leave it as i and create a NumberBox object with both values the same

guard log10(float) != longestNumberLength else {
    numberBoxes.append(NumberBox(
        originalNumber: Int(float),
        modifiedNumber: Int(float)
    ))
    continue
}

Next we want to turn each float into a String so that we can then start "padding" it with 9s

We can achieve this padding by using the aptly named padding function available through Swift's String built-in struct!

This function needs three things; a desired length of String, i.e. how long you want the final string to be, what string the function should use to fill out or pad your string with and lastly an index of where the function should start inserting said string

let numberAsString = String(Int(float))

let modifiedNumber = numberAsString.padding(
    toLength: Int(longestNumberLength),
    withPad: "9",
    startingAt: numberAsString.count
)

In our case here we always want each string (A string represenation of our "Number" that is) to have the same length as the largest number that we could find in our array.

We then want to always pad the number with 9s as that was the key to our solution as we figured out earlier

And then most importantly we want the function to start adding these 9s to the end of our string / number

Once we have this padded out number we can then add it to our growing list of NumberBox objects!

if let paddingStringAsInt = Int(modifiedNumber) {
    numberBoxes.append(NumberBox(
        originalNumber: Int(float),
        modifiedNumber: paddingStringAsInt
    ))
}

So now we have all of our numbers and we can sort by their 'modified' values!

let sortedNumbers = numberBoxes.sorted(by: { 
    $0.modifiedNumber > $1.modifiedNumber 
})

And then finally we can take our sorted array, compactMap our original numbers into an array of strings by casting each one, joining then via Swift's built-in joined() function and then recasting that large number back into an integer

return Int(sortedNumbers.compactMap {
    String($0.originalNumber)
}.joined()) ?? 0

Putting it all together we have something like this

var numberBoxes = [NumberBox]()
    for float in floatArray {
        guard log10(float) != longestNumberLength else {
            numberBoxes.append(NumberBox(
                originalNumber: Int(float),
                modifiedNumber: Int(float)
            ))
            continue
        }

        let numberAsString = String(Int(float))

        let modifiedNumber = numberAsString.padding(
            toLength: Int(longestNumberLength),
            withPad: "9",
            startingAt: numberAsString.count
        )

        if let paddingStringAsInt = Int(modifiedNumber) {
            numberBoxes.append(NumberBox(
                originalNumber: Int(float),
                modifiedNumber: paddingStringAsInt
            ))
        }
    }

let sortedNumbers = numberBoxes.sorted(by: { 
    $0.modifiedNumber > $1.modifiedNumber 
})

return Int(sortedNumbers.compactMap {
    String($0.originalNumber)
}.joined()) ?? 0
            

Ok let's give it a spin and see what we get!

masher(with: integerList) == 77641510

💥 Uh oh it's crashing!

If we take a lot our crash logs we'll see that we're getting back the following

Terminating app due to uncaught exception 
  'NSInvalidArgumentException', reason: '*** 
-[NSTaggedPointerString 
stringByPaddingToLength:withString:startingAtIndex:]: 
out of range padIndex'

Luckily for us in this case reading the error explains the error clearly

Here we're clearly being informed that the index we're passing to the padding function is out of bounds in exactly the same way as if were to try and reference an object in array using an index greater than the size of the array

let someString = "ohYoureApproachingMe"
let firstChar = someString[firstCharacter.startIndex]

Back to our crash though and we need to add some safety barriers around what we pass into the padding function to prevent it blowing up in our face

So let's add some catches for this so that if the starting index is less than 0 we'll just use 0

let startingIndex = min(numberAsString.count - 1, 0)

Great our crash is all gone!

But our primitive test still isn't passing

Let's debug this either by our preferred method whether that be sticking a breakpoint at a relative point, printing out some of our values throughout the function or seeing the values of these variables via the results sidebar in Playgrounds

I used Playgrounds for all of my coding challenges as it's the most lightweight way to get to us executing Swift code

With that in mind when I take a look at our results I can see that our sortedNumbers array consists of a three digit number (415) as our largest number in terms of digit length but that our smaller numbers such as 7 are only being bumped up to 79 rather than the expected 799

If we take a look at our padding code again with this knowledge the problem becomes apparent!

let startingIndex = min(numberAsString.count - 1, 0)
let modifiedNumber = numberAsString.padding(
    toLength: Int(longestNumberLength),
    withPad: "9",
    startingAt: startingIndex
)

Here we're asking the padding function to pad our string to a certain length which is non-zero indexed as it's a count but when we're passing it our desired length we're passing it a zero-index value through longestNumberLength

To keep things simple we can simply offset this with something like this

let startingIndex = min(numberAsString.count - 1, 0)
let modifiedNumber = numberAsString.padding(
    toLength: Int(longestNumberLength) + 1,
    withPad: "9",
    startingAt: startingIndex
)

Now let's run our code again

Success!

This is great so let's add some more test scenarios to make sure that it still works with varying lengths of digits as well as smaller array sizes

let normalSet = [1, 2, 9, 899, 991]
let bigCombine = [999, 998, 99, 9]
let twoDigits = [98, 9, 12]
let fourDigits = [9878, 56, 99, 1]
let bigDigits = [999998, 9]

masher(with: normalSet) == 999189921 ✅
masher(with: bigCombine) == 999999998 ✅
masher(with: twoDigits) == 99812 ✅
masher(with: fourDigits) == 999878561 ✅
masher(with: bigDigits) == 9999998 ✅

Looks like our tests are all running A-ok and that, overall, it works

It's not very efficient mind you but it's a first working solution

Normally without any outside help, where we can come to a working initial solution within a reasonable amount of time, we should do so!

Tidying up

Whilst keeping our same solution there are plenty of things we can do to not only improve the efficiency of our code but also the legibility

Let's start with this part first

return Int(sortedNumbers.compactMap {
    String($0.originalNumber)
}.joined()) ?? 0

Whilst it seems innocuous at first (Fancy word I know) it's something that we can easily improve upon to make our code more efficient

Previously we had the following code:

let numberAsString = String(Int(float))

let modifiedNumber = numberAsString.padding(
    toLength: Int(longestNumberLength),
    withPad: "9",
    startingAt: numberAsString.count
)

Later on however we're then adding an integer representation of our number when creating our NumberBox object

if let paddingStringAsInt = Int(modifiedNumber) {
    numberBoxes.append(NumberBox(
        originalNumber: Int(float),
        modifiedNumber: paddingStringAsInt
    ))
}

But then later on re-casting this Int into a String whenever we're doing this

return Int(sortedNumbers.compactMap {
    String($0.originalNumber)
}.joined()) ?? 0

Alternatively let's just store our originalNumber as a String

struct NumberBox {
    let originalNumber: String
    let modifiedNumber: Int
}

And now we no longer recast for every object in our array!

return Int(sortedNumbers.compactMap {
    $0.originalNumber
}.joined()) ?? 0

This is our next prime target:

var numberBoxes = [NumberBox]()

Where possible we should avoid mutability and prefer constants and immutability

Immutable code creates a more concrete codebase and reduces the chance that we'll run into issues where we modify the properties of an object in one place only to modify again elsewhere giving us unpredictable software

One initial thought might be to tackle it with closure initialisation

let numberBoxes: [NumberBox] = {
    //Generate some boxes here
}()

Whilst this is a step in the right direction we still can't escape our mutability issue as we'll need a way of storing our NumberBox objects as we iterate through our floats

let numberBoxes: [NumberBox] = {
    var boxesToBuild = [NumberBox]()
    for float in floatArray {
        //Create a NumberBox
        //Add it to our boxesToBuild
    }
    return boxesToBuild
}()

What we really need is to create a function that will give us a NumberBox when we pass it both an original number and a maximum length of digits

func numberBox(forFloat float: CGFloat, 
          withMaxLength length: Double) -> NumberBox? {

    let floatAsInt = Int(float)
    guard log10(float) != longestNumberLength else {
        return NumberBox(
            originalNumber: String(floatAsInt),
            modifiedNumber: floatAsInt
        )
    }
    
    let numberAsString = String(floatAsInt)
    let modifiedNumber = numberAsString.padding(
        toLength: Int(longestNumberLength) + 1,
        withPad: "9",
        startingAt: min(numberAsString.count - 1, 0)
    )
            
    guard let paddingStringAsInt = Int(modifiedNumber) else { 
       return nil
    }
    return NumberBox(
        originalNumber: numberAsString,
        modifiedNumber: paddingStringAsInt
    )
}

This is the exact code we were using before except instead of appending our NumberBox objects to mutable array we're just returning a NumberBox object

We can then take this function and plug it into a compact map to generate our array of NumberBox objects!

let numberBoxes = floatArray.compactMap {
    numberBox(forFloat: $0, withMaxLength: longestNumber)
}

For our last final touch let's fix this "not so pretty" sorted function

let sortedNumbers = numberBoxes.sorted(by: {
    $0.modifiedNumber > $1.modifiedNumber }
)

By taking our existing NumberBox object we can simply update it to conform to the Comparable protocol

When we conform to the Comparable protocol we need to provide both implementations for the lesser than function as well as the equals function

For our NumberBox object however all of our properties are already Equatable (String / Int) and so Swift can infer whether two NumberBox objects are equal by default

We still need to tell Swift how it should deal with lesser than for our object however:

struct NumberBox: Comparable {
    static func < (lhs: NumberBox, rhs: NumberBox) -> Bool {
        lhs.modifiedNumber > rhs.modifiedNumber
    }
    
    let originalNumber: String
    let modifiedNumber: Int
}

Lucky for us Swift can also infer greater than for us also since it's just the exact opposite of what we're explicitly defined!

End result

And with that here's our end result!

func intMasher(with list: [Int]) -> Int {
    
  let floatArray = list.compactMap { CGFloat($0) }
  
  guard let longestNumber = floatArray.sorted(by: { 
    log10($0) > log10($1) 
  }).first else { return 0 }
  let longestNumberLength = log10(longestNumber)
  
  struct NumberBox: Comparable {
    static func < (lhs: NumberBox, rhs: NumberBox) -> Bool {
        lhs.modifiedNumber > rhs.modifiedNumber
    }
      
    let originalNumber: String
    let modifiedNumber: Int
  }
  
  func numberBox(forFloat float: CGFloat,
              withMaxLength length: Double) -> NumberBox? {
      let floatAsInt = Int(float)
      guard log10(float) != longestNumberLength else {
          return NumberBox(
              originalNumber: String(floatAsInt),
              modifiedNumber: floatAsInt
          )
      }
      
      let numberAsString = String(floatAsInt)
      let modifiedNumber = numberAsString.padding(
          toLength: Int(longestNumberLength) + 1,
          withPad: "9",
          startingAt: min(numberAsString.count - 1, 0)
      )
              
      guard let asInt = Int(modifiedNumber) else { 
        return nil
      }
      return NumberBox(
          originalNumber: numberAsString,
          modifiedNumber: asInt
      )
  }
  
  let numberBoxes = floatArray.compactMap {
     numberBox(forFloat: $0, withMaxLength: longestNumber)
  }
  
  let sortedNumbers = numberBoxes.sorted()

  return Int(sortedNumbers.compactMap {
      $0.originalNumber
  }.joined()) ?? 0
}

let integerList = [10, 7, 76, 415]
let normalSet = [1, 2, 9, 899, 991]
let bigCombine = [999, 998, 99, 9]
let twoDigitOnly = [98, 9, 12]
let fourDigit = [9878, 56, 99, 1]
let bigDigits = [999998, 9]

intMasher(with: integerList) == 77641510
intMasher(with: normalSet) == 999189921
intMasher(with: bigCombine) == 999999998
intMasher(with: twoDigitOnly) == 99812
intMasher(with: fourDigit) == 999878561
intMasher(with: bigDigits) == 9999998

(As a heads up I've reduced some of the indentation to prevent having to horizontally scroll to read the code)

Whilst we might not necessarily want to settle with this solution in the real world, if we had no one else to help us figure out how to do this "properly" initially, getting something working gives us not only a good base from where to start with improvements but also a better understanding of the problem, which more often than not, can help lead us to a better solution

Finished 13:54

Total time 2:01

Post solution deep dive 🤿

One of the things we wanted to test out was Int overflows; that is, if we give the function a huge array of numbers the Int will just become too big for Swift to handle

What happens currently with our function?

let hugeNumbers = [999, 999, 999, 999, 999, 999]
masher(with: hugeNumbers) == 999999999999999999

And it still works

this is becuse the biggest number supported by Int in Swift on a 64 bit machine is a whopping 9223372036854775807

But why this particular number?

The maximum number that can be stored by a given integer is determined by the given system you are running your code on

If you're running your code on an 8 bit system then, as the name suggests, the maximum integer value is defined by exactly that, the number of bits available to the processor

A bit is either 1 or 0, on or off and so with this in mind we can calculate the maximum size of an int on a given system by 2^x where x is the number of bits available minus 1

So with all of that in mind

"what happens if I go above or below these numbers?"

In general (Not in Swift by default) going above or below a system's minimum or maximum range causes what's referred to as an "overflow"

When you overflow "positively" on, say, an 8 bit system where the largest number is 127; if we were to add 1 to our number we would then have -128

The reverse is also true when we "negatively" overflow. So if we minus 1 from -128 we'll be given 127

In fact this exacty problem has been the root of a number of different video game glitches in the past with one of the more famous ones being the Final Fantasy damage overload glitch!

In swift however by default overflows are handled as errors when using our traditional methods of addition, subtraction or multiplication

For example if we were to create a variable with the maximum integer value and try to increase it:

var reallyBigInt = 9223372036854775807
reallyBigInt += 1

At runtime what we'll run into is a crash with the following error

* thread #1, queue = 'com.apple.main-thread', 
  stop reason = Swift runtime failure: arithmetic overflow

Taking this even further, if we statically try to set an integer to something that would overflow Swift won't even let us compile!

For example the following:

let reallyBigInt = 9223372036854775808

Gives us this error when trying to compile:

Integer literal '9223372036854775808' 
  overflows when stored into 'Int'

let reallyBigInt = 9223372036854775807

let reallyBig32BitInt: Int32 = 2147483647

let tooBig32BitInt: Int32 = 9223372036854775808

Integer literal '9223372036854775807' 
  overflows when stored into 'Int32'

Going back to Swift and its default overflow behaviour is it even possible for us to overflow in Swift without a crash?

And the answer is yes!

Whilst our default methods of addition, subtraction and multiplication in Swift will cause crashes such as in the following example:

let biggest32BitInt: Int32 = 2147483647
let smallest32BitInt: Int32 = -2147483648

let additionOverflow = biggest32BitInt + 1         //💥
let subtractionOverflow = smallest32BitInt - 1     //💥
let multiplicationOverflow = biggest32BitInt * 2   //💥

There is a way to make use of the overflow concept in Swift and that's through the built-in overflow operators!

let biggest32BitInt: Int32 = 2147483647
let smallest32BitInt: Int32 = -2147483648

let additionOverflow = biggest32BitInt &+ 1       
// result: -2,147,483,648

let subtractionOverflow = smallest32BitInt &- 1  
// result: 2,147,483,647

let multiplicationOverflow = biggest32BitInt &* 2
// result: -2

Now that we have all of this figured out the final piece of the puzzle is the concept of unsigned integers!

Unsigned integers at the most basic level are simply integers that are always non-negative

We can see this in action by trying to create a negative unsigned 32 bit integer

let negative32BitUInt32: UInt32 = -1

Which when we try and compile will cause us to be greeted with a lovely error

Negative integer '-1' 
  overflows when stored into unsigned type 'UInt32'

Similar to our scenario from before, when we try and overflow an unsigned integer using Swift's default operators such as in this scenario:

let negative32BitUInt32: UInt32 = 0
let subtractionOverflow = negative32BitUInt32 - 1

We run yet again into our previous error

* thread #1, queue = 'com.apple.main-thread', 
  stop reason = Swift runtime failure: arithmetic overflow

What makes unsigned integers powerful in the right hands however is that they are able to store a larger positive value for the tradeoff of not being able to hold negative values

In fact as you might have guessed you're able to store both the sum of the positive and negative "amounts" in an unsigned integer as we can see here

let max32BitInt = Int32.max
// result: 2,147,483,647

let max32BitUInt = UInt32.max
// result: 4,294,967,295

As unsigned integers can't store negative values if we apply our overflow operator like we did before and attempt to reach a negative value we'll overflow to the maximum value of the unsigned integer; and if we were to do the same at the upper bounds we'd end up back at 1

let negative32BitUInt32: UInt32 = 0
let subtractionOverflow = negative32BitUInt32 &- 1
// result: 4,294,967,295

let positive32BitUInt32: UInt32 = 4294967295
let additionOverflow = negative32BitUInt32 &+ 1
// result: 1

With this in mind it's easy to see how when used in the wrong place you could easily run into issues with unsigned integers whereby something may be reduced to be less than 0 and suddenly you end up with a huge unexpected number!

This potentially unexpected behaviour is the main reason why overflowing isn't supported by Swift's default operators and instead exists as an "opt-in" feature

Despite being a surface level explanation of Integers and overflows I hope this was at least either somewhat interesting or insightful and at best only the first part of your own deep dive into Integers!