Best of prey problem
The problem:
There are a number of animal species in the forest. Each species has one or more predator that may be direct or indirect. Species X is said to be a predator of species Y if at least or of the following is true:
- Species X is a direct predator of species Y
- If species X is a direct predator of species Z, and Z is a direct predator of Y, then spec is an indirect predator of species Y.
Indirect predation is transitive through any numb of levels. Each species has a maximum of 1 direct predator. No two species will ever be mutual predators, and no species is a predator of itself. Your task is to determine the minimum number of groups that must be formed to so that no species is grouped with its predators, direct or indirect. As an example, consider an array where each position represents a species and each element represents a predator of that species or-1 if there are none. The array is a [-1, 8, 6, 0, 7, 3, 8, 9, -1, 6, 1] and we’ll use zero indexing.
0 8
\ / \
3 1 6
\ / / \
5 10 2 9
\
7
\
4
These are the trees created based on the given array.
The groups will be: [0,8], [3,1,6], [5,10,2,9], [7], [4]
We can notice that the asked number of groups without predators is, in fact, the depth of the longers tree branch. Let’s move on directly to the solutions:
Good will hunting
Today was a sunny day, the one that makes you thrive for a beer, mint lemonade or an intergalactic crash, just like the one ending von Trier’s Melancholy. And in the middle of the heat, meditating like Kirsten Dunst on a green meadow, something just struck me. An idea.
Maybe partly it was caused by the third episode of the new Black Mirror season I’ve seen last night. It wasn’t really up to the standard the viewers were used to, myself included. Frankly, the plot was dry as a salt lake, the distance in quality from San Junipero should be expressed in light years, and it was night and night even compared to Hang the DJ. Just a teenage flick about bloodsucking business which creeps everywhere where big money is put at stake. To make thing interesting it gravitated around Miley Cyrus’ career…
How to sort an array of objects by a property value with priority in JavaScript?
User case: data should be sorted by custom values, which don’t make logical order. Look at the following data:
const list = [
{ category: 'tv', price: 1400 },
{ category: 'smartphones', price: 590 },
{ category: 'notebooks', price: 1500 },
{ category: 'smartphones', price: 350 }
]
We would like to sort the objects in the following order: smartphones, notebooks, anything else and have no control over the order data is fetched. First, we need to create an object with that is going to hold priorities:
let sortingOrder = {
'smartphones': 1,
'notebooks': 2
}
We are going to use standard array sorting method from the prototype, but need to write a comparison function. Let’s make it take the property name and sorting order as parameters, so it can be reused.
function compare(key, order = 'asc') {
return function (a, b) {
if (!a.hasOwnProperty(key) || !b.hasOwnProperty(key))
return 0;
const first = (a[key].toLowerCase() in sortingOrder) ? sortingOrder[a[key]] : Number.MAX_SAFE_INTEGER;
const second = (b[key].toLowerCase() in sortingOrder) ? sortingOrder[b[key]] : Number.MAX_SAFE_INTEGER;
let result = 0;
if (first < second)
result = -1;
else if (first > second)
result = 1;
return (order === 'desc') ? ~result : result
};
}
We use the comparator function to determine the order from keys. Number.MAX_SAFE_INTEGER is used to be sure note specified elements are always last in undetermined order and we are free to extend sortingOrder object. Finally, (order === ‘desc’) ? ~result : result inverts the comparison result for descending order. Lastly, we sort the array as follows:
list.sort(compare('category'));
// OR
list.sort(compare('category', 'desc'));
SQL ordered insert from bulk
Bulk insert is one of the best SQL features whenever performance is needed. It’s simple and straightforward, the order of data in a table is retained from the file. However, what if we have already defined import files and would like to feed data from the bulk table in an ordered manner, without modifying files’ structure? To be sure that the ordered will be kept we need to somehow introduce a sorting column.
Io and behold, 3 simple ways to import from temp table and keep entries’ order.
Bulk insert to a view
One way to do this is to modify the original bulk table by adding a primary key. We should always add it in the first position – for two reasons: clarity and ability to extend table columns without dropping whole table.
Note: We’re going to use the simplest example as possible for readability.
First, we create/alter the import table by adding a primary key, which later will be used to determine the order of the insert.
CREATE TABLE ImportTemp(
iId int IDENTITY(1,1),
[City] nvarchar(30)
)
Then we create a view that contains all columns except identity.
CREATE VIEW ImportTempView
AS
SELECT
city
FROM ImportTemp
Finally simply perform the bulk insert to the view, results will be automatically inserted to the table on which view is based on.
BULK INSERT ImportTempView
FROM 'Q:\cities.txt';
iId | City |
1 | Toronto |
2 | New York |
3 | Cracow |
4 | Warsaw |
Disadvantages?
It requires diving into the code base and adjusting the table, which is targeted during the import. Also, we add an additional abstraction layer plus performance overhead with the view itself.
SqlBulkCopyOptions
We’re going to use the .NET SqlBulkCopyOptions to specify the way import feeds identification data. However, it requires modification of the import files, which can disqualify this solution (no access to the import files, too many templates, etc.).
Example:
public SqlBulkCopyAssistant CreateBulkCopy(string strDestinationTable)
{
return CreateBulkCopy(strDestinationTable, SqlBulkCopyOptions.KeepIdentity);
}
The SqlBulkCopyOptions.KeepIdentity option when turned on will allow feeding IDs from the import file. However, the import file needs to include ID values. If this option is disabled (bear in mind the SqlOptions use bitwise options), import file STILL needs to has the ID column specified, although it can be empty (letters in bold are just a header):
id, city
,toronto
DataTable and DataColumn
The third and final method is based on .NET methods involving operations on DataView and DataTables.
using (var dataView = _csvDataReader.ReadDataWithHeaders(localFilePath))
{
var dataTable = dataView.ToTable();
dataTable.Columns.Add("iId", typeof(int)).SetOrdinal(0);
var dataReader = dataTable.CreateDataReader();
_bulkUploadService.Upload(ProcessImport.LoadTempTableName, dataReader);
}
Please focus on dataTable.Columns.Add(“iId”, typeof(int)).SetOrdinal(0); line, which is responsible for adding an empty column to the import table in the first position (0). This way we’re going to add a temporary dummy column on the fly and keep import clean without touching import files.
Whichever method you choose, you’ll end up having a temp table with identity column, which is both trivial and efficient to sort.