StreamFinder

Note

This project was accepted for the 6th CHECK24 GenDev scholarship. 🥳

StreamFinder is an iOS app that helps users find the best streaming packages to watch games of their favorite soccer teams. Users can select one or more teams or entire tournaments, and the app will compare available streaming packages based on the coverage of the selected team's matches. If no single package covers all games, the app computes the best combination of streaming services that maximize coverage at the lowest cost.

Table of Contents

• Features
• Best combination algorithms
  • Greedy Algorithm
  • ILP Algorithm
• Optimisations
• How to run locally

Features

• The app is optimized for iPhone and iPad.
• Onboarding screen:
  • A short explanation of the app.
• Selection screen:
  • The user can select one or more teams or entire tournaments and choose whether he wants to watch the games live or on-demand.
  • If no teams and no tournaments are selected, all teams and tournaments will be considered.
  • The user can also select which algorithm is used to find the best combination.
• Result screen:
  • A table view presents the best combination, and the remaining packages sorted by coverage and cost.
  • The availability of a tournament for live viewing or on-demand highlights is displayed with a checkmark/x mark.
  • By tapping the mark, the user can see the exact number of tournament games the streaming package covers.

Best combination algorithms

The main part of the project is to find the best combination of streaming packages that covers all games of the selected teams and tournaments for the lowest price. This is a form of the Set Cover Problem, where the universe is the set of games, the sets are the streaming packages, and the cost function is the price of each package. There are thirty-seven streaming packages in the dataset that need to be considered. A naive brute force algorithm would have to test $2^{37}$ combinations to find the best one. That is why smarter algorithms are used.

Greedy Algorithm

The first algorithm uses a greedy approach that does not guarantee the optimal solution but finds a near-optimal combination fast and locally on device.

The data from the CSV files is converted to Swift objects when the app is opened. All data is stored in the DataManager class in DataManager.swift The CompareManager class in CompareManager.swift ranks the packages and stores the results.

Summary of the core logic behind the greedy package selection:

1. Input:

• The algorithm starts with a set of teams, a set of tournaments, and a streaming type (whether the user wants live streams, on-demand highlights, either or both).

2. Filtered games:

• The relevant games are filtered based on the selection of teams and tournaments.
• They are stored as a set of game IDs for efficient contains checks.

3. Package coverage:

• A dictionary is created that maps every streaming package to the games it covers (a set of game IDs).
• The set of covered games only contains relevant games from the set from Step 2.

4. Sorting the packages:

• The packages are sorted by their coverage (how many relevant games they cover) and price.
• The result is stored in an array containing tuples of packages with their coverage.

5. Selection of the best combination:

• The uncovered games are tracked in a set that is initialized with the relevant games from Step 2.
• The algorithm iterates through the sorted array of streaming packages.
• For each package, it checks which games it covers that haven't already been covered by a previously selected package.
• If the package adds coverage, it is selected, and the covered games are removed from the set of uncovered games.
• The algorithm continues adding packages until all selected games are covered or there are no more packages that provide additional coverage.

6. Improvement of the algorithm:

• The greedy selection step 5 is performed multiple times with different starting packages to improve the accuracy of the result.
• The best selection with the highest coverage and lowest price is stored as the best combination, and the remaining packages are stored in the order of Step 4.

ILP Algorithm

To find the guaranteed optimal combination, another algorithm is implemented that uses integer linear programming (ILP). ILP is a mathematical optimization technique with the goal of maximizing or minimizing a linear objective function, subject to a set of linear constraints. The Python library PuLP is used for solving the ILP problem. Because it is far easier than embedding Python code in an iOS app, the Python code runs on a local server.

Steps of the ILP Algorithm:

1. Input:

• Similar to the greedy algorithm, the input consists of selected teams, tournaments, and the streaming type.

2. Filtered Games:

• The relevant games are filtered based on the selection of teams and tournaments.
• The relevant game IDs and the streaming type are sent to the server.

3. ILP Problem:

• A binary variable $x_i$ is created for each package $P_i$, indicating whether it is selected ($x_i = 1$) or not ($x_i = 0$).
• The goal is to minimize the objective function, the total cost of the selected packages: $\sum_{i = 1}^n (\text{cost}(P_i) \cdot x_i)$
• For every game, a constraint is added so that every game is covered by at least one selected package: $\sum_{i:g \in \text{games}(P_i)} x_i \geq 1, \forall g \in \text{relevant games}$

4. Response:

• The server sends back the selected package IDs (best combination) and the remaining package IDs sorted by the coverage and cost.
• The app then converts the arrays of IDs to arrays of StreamingPackage objects.

Optimizations

1. Tournament availability per package

Whether a package contains all, some, or none of the games of a tournament for live viewing or on-demand highlights is a computationally expensive question. The result screen contains a table with all packages and tournaments and displays this information for each. It would take too long to compute the availability every time the user reaches the result view, and it is unnecessary because it stays the same regardless of the user's selection. Therefore, the availability is precomputed. The file StreamFinder/Data/tournaments_live_availability.json contains a dictionary that maps each tournament to a dictionary of package IDs mapped to the live availability (all, some, none):

[tournament name: [package ID: availability]]

The file StreamFinder/Data/tournaments_highlights_availability.json is structured similarly but contains the availability of on-demand highlights.

The methods to create and load these files are contained in the DataManager.swift file.

2. Teams of a tournament

The selection screen displays the teams in sections of the tournaments/leagues they play in. That's why getting all teams in a specified tournament is necessary. This information is precomputed in the file StreamFinder/Data/tournaments_teams.json. It contains a dictionary mapping tournaments to their teams:

[tournament name: set of teams]

How to run locally

1. Clone the repository.
2. Set up the local Python server:
   • Navigate to the Server folder: cd Server
   • Install dependencies: pip install flask pulp
   • Run the server: python3 app.py
3. Open the top-level folder in Xcode.
4. Select an iPhone or iPad simulator in the top bar and press play.

Important

If you run the app on a physical iPhone or iPad, you need to change the IP address in CompareManager.swift from 127.0.0.1 to the local IP address of your Mac. Your device must be on the same Wi-Fi network as your Mac.