Week 1: Are you looking for a solution for the Experienced challenge that would work for ANY data instance?

Hello!

For the experienced challenge, are you expecting queries that would work for assigning ANY set of names in households in the 6 tables? n tables? OR is the solution good enough for the given csv file?

Lavanya

Hi!

Ideally that query should work on any dataset provided. Please don't hard code the answers (e.g. figuring out the answer on paper, then writing the corresponding query).

I hope that helps!

Cheers,

Lju

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

Hi Lavanya,

I'm really glad to hear you enjoyed the challenge! I like the approach of the above answer, it's not quite giving the right result, but I'll have a look into the above and see what we can adjust.

It is a very neat approach indeed!

Cheers,

Lju