Solution to problem 4 from "5 Programming Problems, 1 Hour"

problem_4_of_5.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."
//  https://www.shiftedup.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour

//  This solution first finds the permutations of the integers in the given array. A string is made out of the digits of each permutation, the string is converted to an integer, and the maximum of all these integers is returned.
//  It is expensive! but it's short and guaranteed to work every time. 

//  I updated objc.io's permutation snippet to Swift 2.0 and used it in my solution
//  https://www.objc.io/blog/2014/12/08/functional-snippet-10-permutations/

//  Xcode 7.0, Swift 2.0

let list = [50, 2, 1, 9]
let largest = 95021

// Permutations

extension Array {
    func decompose() -> (Generator.Element, [Generator.Element])? {
        guard let x = first else { return nil }
        return (x, Array(self[1..<count]))
    }
}

func between<T>(x: T, _ ys: [T]) -> [[T]] {
    guard let (head, tail) = ys.decompose() else { return [[x]] }
    return [[x] + ys] + between(x, tail).map { [head] + $0 }
}


func permutations<T>(xs: [T]) -> [[T]] {
    guard let (head, tail) = xs.decompose() else { return [[]] }
    return permutations(tail).flatMap { between(head, $0) }
    
}

let p = permutations(list).flatMap { $0.reduce("") { $0 + String($1) } }.map { Int($0)! }

assert(largest == p.maxElement())