Ubt

ubt.txt

// These are the tests that I used to make sure my problem worked for circular references.  It also describes the problem
// that I was trying to solve.

import Quick
import Nimble

@testable import AlgorithmsAndDataStructuresInSwift

// Problem: Write a method that takes a "Movie" object and integer value n
//          The method should return an array of the highest ranking movies no larger than n.
//          Move object
//          class Movie {
//              rating: Int
//              similiar: [Movie]
//          ex: input movie (see below), n = 2
//          Movie(rating: 5, similiar: [Movie(rating: 6, similar:[Movie(rating: 7, similiar: []])])]
//              -> [Movie(rating: 7, similar: []]), Movie(raiting: 6, similar:[Movie(rating: 7, similiar: []])])]

class MovieRatingObtainerSpec: QuickSpec {
    override func spec() {
        var subject: MovieRatingObtainer!
        
        beforeEach {
            subject = MovieRatingObtainer()
        }
        
        describe("#obtainHighestSimilarMovies(movie:numberOfHighestRatedMovies:)") {
            var inputMovie: Movie!
            var highestSimilarMovies: [Movie]!
            
            describe("when the movies don't have circular references (movie has similar movies that reference itself)") {
                beforeEach {
                    inputMovie = Movie(id: 0, rating: 5, similiarMovies: [Movie(id: 1, rating: 6, similiarMovies: [Movie(id: 2, rating: 7)])])
                    
                    highestSimilarMovies = subject.obtainHighestSimiliarMovies(movie: inputMovie, numberOfHighestRatedMovies: 2)
                }
                
                it("returns the correct [Movie] array") {
                    let expectedHighestSimilarMoviesArray = [Movie(id: 2, rating: 7),
                                                             Movie(id: 1, rating: 6, similiarMovies: [Movie(id: 2, rating: 7)])]
                    
                    expect(highestSimilarMovies).to(equal(expectedHighestSimilarMoviesArray))
                }
            }
            
            describe("when the movies do have circular references") {
                var movie1: Movie!
                var movie2: Movie!
                
                beforeEach {
                    movie1 = Movie(id: 55, rating: 9)
                    movie2 = Movie(id: 66, rating: 2, similiarMovies: [movie1])
                    
                    inputMovie = Movie(id: 0, rating: 5, similiarMovies: [movie1, movie2])
                    
                    highestSimilarMovies = subject.obtainHighestSimiliarMovies(movie: inputMovie, numberOfHighestRatedMovies: 2)
                }
                
                it("returns the correct [Movie] array") {
                    let expectedHighestSimilarMoviesArray = [Movie(id: 55, rating: 9, similiarMovies: []),
                                                             Movie(id: 0, rating: 5, similiarMovies: [movie1, movie2])]
                    
                    expect(highestSimilarMovies).to(equal(expectedHighestSimilarMoviesArray))
                }
            }
        }
    }
}

// Here is the solution that I came up with:

import UIKit

class Movie: Equatable, Comparable, Hashable, CustomStringConvertible {
    // MARK: - Public Properties

    var id = 0 // This was to make debugging easier
    var rating = 0
    var similiarMovies: [Movie] = []
    
    // MARK: - <CustomStringConvertible>
    
    var description: String {
        return "{id: \(id), rating: \(rating)}"
    }
    
    // MARK: - <Hashable>
    // Hashable is required to add Movie object to a set
    
    var hashValue: Int {
        return id.hashValue ^ rating.hashValue ^ similiarMovies.count
    }
    
    // MARK: - Init Method
    
    init(id: Int, rating: Int, similiarMovies: [Movie] = []) {
        self.id = id
        self.rating = rating
        self.similiarMovies = similiarMovies
    }
    
    // MARK: - <Equatable>
    
    static func == (lhs: Movie, rhs: Movie) -> Bool {
        return lhs.id == rhs.id &&
               lhs.rating == rhs.rating
    }
    
    // MARK: - <Comparable>
    
    static func < (lhs: Movie, rhs: Movie) -> Bool {
        return lhs.rating < rhs.rating
    }
}

class MovieRatingObtainer {
    // MARK: - Public Methods
    
    func obtainHighestSimiliarMovies(movie: Movie, numberOfHighestRatedMovies: Int) -> [Movie] {
        // First, we want to fill up a set of all the movies since it won't allow duplicates
        
        var movieSet: Set<Movie> = Set<Movie>()
        movieSet.insert(movie)
        
        // Recursively fill up the set with all movies
        
        obtainHighestSimiliarMovies(movie: movie, movieSet: &movieSet)
        
        // Once we have an set of all the movies, lets convert to an array and then sort them in descending order
               
        var allMoviesArray = Array(movieSet)
        
        allMoviesArray.sort { lhs, rhs in
            return rhs < lhs
        }
        
        // Now that the array is in descending order, let's only return the elements from 0 upto numberOfHighestRatedMovies (n) [0..<numberOfHighestRatedMovies]
        
        return Array(allMoviesArray[0..<numberOfHighestRatedMovies])
    }
    
    // MARK: - Private Methods
    
    func obtainHighestSimiliarMovies(movie: Movie, movieSet: inout Set<Movie>) {
        // kick out when movie doesn't have any similiar movies
        
        if movie.similiarMovies == [] {
            return
        }
        
        // Iterate through all movies to add to movieSet, and then recursively do this
        // with all of that movies similiar movies
        
        movie.similiarMovies.forEach { movie in
            movieSet.insert(movie)
            
            obtainHighestSimiliarMovies(movie: movie, movieSet: &movieSet)
        }
    }
}