Hi @lju Thanks for organizing these challenges! I thoroughly enjoyed solving the week 1 challenges so far. Especially the experienced challenge - I think there is a simple analytic solution that can be extended to any number of tables and any number of duplicates from household which are allowed in the tables. The solution uses a set of conditions which are both necessary and sufficient. Sharing the solution below in the form of queries. Also, the solution does not use APOC 🙂
// create bipartite graph with partitions household_group and names
LOAD CSV WITH HEADERS FROM
'https://raw.githubusercontent.com/summer-of-nodes/2020/master/week1/bbq_households.csv' AS line
WITH line.`Household Group` AS g, line.`Name` AS n
MERGE (g_node:Household_Group {group: g})
MERGE (n_node:Name {name: n})
MERGE (g_node) <-[:BELONGS_TO]-(n_node);
// create 6 tables
CREATE (: Table {number: 1}),
(: Table {number: 2}),
(: Table {number: 3}),
(: Table {number: 4}),
(: Table {number: 5}),
(: Table {number: 6});
// Query to declare whether assignment with rules specified is possible
// 1. Number of names in each household is not more than 2 * number of tables
// 2. The total number of names is atleast 2 * number of tables and atmost 6 * number of tables
// In order to have a solution the above two conditions (check_1 and check_2 below) are necessary
MATCH (t:Table) WITH SIZE(collect(t)) AS number_of_tables
MATCH (n:Name) WITH SIZE(COLLECT(n)) AS total_guests, number_of_tables
WITH 2*number_of_tables <= total_guests <= 6*number_of_tables AS check_2, number_of_tables
MATCH (n:Name) -[:BELONGS_TO]-> (g:Household_Group)
WITH g, collect(n) as names_in_household, number_of_tables, check_2
RETURN all (x in collect(size(names_in_household)) where x <= 2*number_of_tables) AS check_1, check_2;
// Query to assign names to tables
// The above two conditions 1 and 2 are actually sufficient if the names are ordered by households and the list of guests are assigned sequencially from tables 1 through 6 and rotated back to 1 through 6 until the sequence is exhausted.
// Rigourous math proof can be written using proof-by-contradiction
MATCH (n:Name) -[:BELONGS_TO]-> (g:Household_Group)
WITH n ORDER BY g.group
WITH collect(n) as names
WITH names, RANGE(0,SIZE(names) - 1) AS names_index
WITH names_index, names, [n in names_index| n % 6] as names_mod6
WITH names_index, names, names_mod6
UNWIND names_index as name_index
WITH name_index, names[name_index] AS name, names_mod6[name_index] AS name_mod6
MATCH (t:Table) WHERE t.number = name_mod6 + 1
WITH t, name
MERGE (t) <-[:sits]- (name)
WITH name
MATCH p=(h:Household_Group)<--(name)-[r:sits]->(t:Table)
RETURN name.name AS Guest , h.group AS household, t.number AS tableNumber ORDER BY t.number;
Best,
Lavanya
