Challenge

[eferoghenej]

can anyone help with this?

----------------------------------------------------------------------------------------------------------------------------------------

Today the Aristocracy is organizing a feast. We know the number of guests; your task is to seat everyone at the table.

However, some of the guests have given you a list of enemies with which they won’t sit.

The chairs are arranged so that the table has two edge seats with only one neighboring guest. In the other cases, there are two neighbors.

Determine if the guests can be seated in a way that makes everyone happy.

Input:

invited_list - the number of guests invited, 0<invited_list<10
dislike_list - string array of enemies, ["1-2,3"] - means that guest 1 won’t sit with guests 2 and 3
Output:

Boolean - is it possible to seat guests in a way that makes everyone happy
Example:

invited_list = 4
dislike_list = ["1-2", "3-4"]
getResult(invited_list, dislike_list) = True // [1, 4, 2, 3]

[Barand]

What have you tried so far?

[Barand]

19 minutes ago, eferoghenej said:

means that guest 1 won’t sit with guests 2 and 3

Do you really mean 2 and 3, or do you mean 2 or 3 ?

[eferoghenej]

I'm totally lost. I don't even know to begin. 

[ginerjm]

1 hour ago, eferoghenej said:

I'm totally lost. I don't even know to begin.

Then perhaps you shouldn't be doing this.  

Unless of course it is homework and you have to do it.  In that case, Do It.  Talk to your teacher.  Go to class more.  Read the textbook.  Don't simply ask us to do your homework.

[mac_gyver]

this wouldn't have been assigned without some instruction covering the fundamentals you are expected to use to solve it.

you would produce all combinations of seating arrangements, eliminating arrangements that violate the seating rules, leaving you with set(s) of arrangements that work.

Edited June 14, 2022 by mac_gyver

[eferoghenej]

it's not homework, it's a test from an interview that i already didn't get past. i would have expected some encouragement and maybe a few pointers. i'm not asking anyone to write the code for me.

[ginerjm]

mac_gyver gave you some food for thought.  Did you not try it?

[Wilpat]

Tried this in javascript but could not get 100% correctness

function getResult(guestCount, dislikeList) {
    const result = []
    let list = []
    for (let i = 1; i <= guestCount; i++) {
        list.push(i)
    }
    for (let i = 0; i < list.length - 1; i++) {
        if(!result.includes(list[i])) {
            const enemies = dislikeList.find(item => item.includes(list[i]) && item.includes(list[i+1]))
            if (!enemies) {
                result.push(list[i])
            } else {
                result.push(list[i + 1], list[i])
            }
        }
    }
    return Boolean(result.length)
}

 

[Barand]

Challenge accepted.

Instead of creating all combinations (3,628,800 fo 10 guests) then eliminating, I decided to attempt the construction of feasible combinations only.

First, create a useable array of the enemies of each gust and use that to place each guest, if possible.

<?php
$guests = 7;
$enemies = [ '1-2,4', '3-4,6', '2-5' ];

##########################################################
#                                                        #
# create a usable array ($e) of the enemies of eah guest #
#                                                        #
##########################################################
$e = array_fill_keys(range(1, $guests), []);
foreach ($enemies as $a) {
    list($b, $c) = explode('-', $a);
    foreach (explode(',', $c) as $d) {
        $e[$b][] = $d;
        $e[$d][] = $b;
    }
}
###############################################################
# sort the array so those with most ememies are seated first  #
###############################################################

uasort($e, fn($a, $b) => count($b)<=>count($a));

echo seatPlan($e);

function seatPlan(&$enemies)
{
    $passes = 0;
    $guests = array_keys($enemies);
    $plan = [array_shift($guests)];
    while(count($guests)) {                                            // loop until all guests seated
        $placed = 0;
        foreach ($guests as $k => $g) {
            $p = count($plan);                                        // if next guest is a friend, seat them
            if (!in_array($plan[$p-1], $enemies[$g])) {
                $plan[] = $g;
                unset($guests[$k]);
                $placed = 1;
            }
        }
        if (!$placed) {                                                // if we have an unseatable guest
            if ($passes >= count($enemies)) return 'Failed';
            ++$passes;
            $guests[] = array_shift($guests);                          // rotate array and try again
            $guests = array_keys($enemies);
            $plan = [array_shift($guests)];
        }
    }
    return join(', ', $plan);
}
?>

 

[Barand]

Correction to above - I screwed up the array rotation bit.

The if (!$placed) section should be

        if (!$placed) {                                                         // if we have an unseatable guest
            if ($passes >= count($enemies)) return 'Failed';
            ++$passes;
            $guests = array_keys($enemies);
            for ($p=0; $p<$passes; $p++) 
                $guests[] = array_shift($guests);                              // rotate array and try again
            $plan = [array_shift($guests)];
        }