package com.javarush.task.task36.task3611;
import java.util.HashSet;
import java.util.Set;
/*
СколÑко Ñ Ñеловека поÑенÑиалÑнÑÑ
дÑÑзей?
Ð¡ÐµÐ³Ð¾Ð´Ð½Ñ ÑаÑÑмоÑÑим ÑаÑÑÑ ÑÑнкÑионала ÑоÑиалÑнÑÑ
ÑеÑей. ÐÑкÑда ÑеÑÑ Ð·Ð½Ð°ÐµÑ, какиÑ
лÑдей пÑедлагаÑÑ Ñебе в дÑÑзÑÑ, коÑоÑÑÑ
ÑÑ Ð¼Ð¾Ð¶ÐµÑÑ Ð·Ð½Ð°ÑÑ?
ÐÑÑ Ð·Ð°Ð´Ð°ÑÑ Ð»ÐµÐ³ÐºÐ¾ ÑеÑиÑÑ Ñ Ð¿Ð¾Ð¼Ð¾ÑÑÑ Ð³ÑаÑов.
Ð¢Ð²Ð¾Ñ Ð·Ð°Ð´Ð°Ñа ÑеализоваÑÑ Ð¼ÐµÑод Set getAllFriendsAndPotentialFriends(int index, int deep), коÑоÑÑй возвÑаÑÐ°ÐµÑ Ð¸Ð½Ð´ÐµÐºÑÑ Ð»Ñдей,
коÑоÑÑе Ñ ÑÐµÐ±Ñ Ð² дÑÑзÑÑÑ
Ñже еÑÑÑ Ð¸ коÑоÑÑÑ
ÑÑ Ð¼Ð¾Ð¶ÐµÑÑ Ð·Ð½Ð°ÑÑ. ÐоÑле ÑÑого оÑÑабоÑÐ°ÐµÑ Ð¼ÐµÑод removeFriendsFromSet,
и ÑезÑлÑÑÐ°Ñ ÑÑого меÑода â ÑÑо вÑе поÑенÑиалÑнÑе дÑÑзÑÑ Ñеловека Ñ Ð¸Ð½Ð´ÐµÐºÑом index и глÑбиной поиÑка deep.
ÐÐ»Ñ ÑпÑоÑÐµÐ½Ð¸Ñ Ð±Ñдем ÑаÑÑмаÑÑиваÑÑ ÑвÑзи вÑеÑ
лÑдей как двÑмеÑнÑй маÑÑив humansRelationships (ÑмоÑÑи пÑÐ¸Ð¼ÐµÑ Ð¼Ð°ÑÑива
в меÑоде generateRelationships). Ðо главной диагонали вÑе ÑлеменÑÑ true, Ñак как ÑÑо один и ÑÐ¾Ñ Ð¶Ðµ Ñеловек.
ÐеÑеÑеÑение ÑÑолбÑа и ÑÑолбика ÑказÑваеÑ, Ð´Ð¾Ð±Ð°Ð²Ð»ÐµÐ½Ñ Ð»Ð¸ лÑди дÑÑг Ñ Ð´ÑÑга в дÑÑзÑÑ (еÑли true â Ñо лÑди еÑÑÑ Ð´ÑÑг Ñ Ð´ÑÑга в дÑÑзÑÑÑ
).
ÐÑли Ñеловек Ñ Ð¸Ð½Ð´ÐµÐºÑом k добавлен в дÑÑзÑÑ Ðº ÑÐµÐ»Ð¾Ð²ÐµÐºÑ Ñ Ð¸Ð½Ð´ÐµÐºÑом p, ÑÑо ознаÑаеÑ, ÑÑо Ñ Ñеловека Ñ Ð¸Ð½Ð´ÐµÐºÑом p в дÑÑзÑÑÑ
еÑÑÑ
Ñеловек Ñ Ð¸Ð½Ð´ÐµÐºÑом k.
РмеÑод пеÑедаеÑÑÑ Ð´Ð²Ð° аÑгÑменÑа:
int index â ÑÑо Ð¸Ð½Ð´ÐµÐºÑ Ñеловека в маÑÑиве (наÑÐ¸Ð½Ð°Ñ Ñ Ð½ÑлÑ);
int deep â глÑбина поиÑка дÑÑзей. ÐÑли ÐаÑа в дÑÑзÑÑÑ
Ñ ÐаÑаÑи и Ñ ÐаÑи в дÑÑзÑÑÑ
еÑÑÑ ÐлÑ, пÑи глÑбине поиÑка = 1,
Ð´Ð»Ñ ÐаÑаÑи нÑжно добавиÑÑ Ð² ÑезÑлÑÑиÑÑÑÑее множеÑÑво ÐаÑÑ Ð¸ как поÑенÑиалÑного дÑÑга ÐлÑ. ÐÑли глÑбина поиÑка = 2,
в ÑÑо же множеÑÑво нÑжно добавиÑÑ ÐµÑе и вÑеÑ
, Ñ ÐºÐµÐ¼ дÑÑÐ¶Ð¸Ñ ÐлÑ.
СмоÑÑи пÑÐ¸Ð¼ÐµÑ Ð² меÑоде main.
РмножеÑÑве, коÑоÑое возвÑаÑÐ°ÐµÑ Ð¼ÐµÑод getAllFriendsAndPotentialFriends не должно бÑÑÑ Ð¸Ð½Ð´ÐµÐºÑа index.
ТÑебованиÑ:
1.âРклаÑÑе Solution должен ÑÑÑеÑÑвоваÑÑ Ð¿ÑблиÑнÑй меÑод Set getAllFriendsAndPotentialFriends(int index, int deep).
2.âРклаÑÑе Solution должно бÑÑÑ Ð¾Ð±ÑÑвлено пÑиваÑное поле boolean[][] humansRelationships.
3.âРмножеÑÑве, коÑоÑое возвÑаÑÐ°ÐµÑ Ð¼ÐµÑод getAllFriendsAndPotentialFriends не должно бÑÑÑ Ð¸Ð½Ð´ÐµÐºÑа index.
4.âÐеÑод getAllFriendsAndPotentialFriends должен бÑÑÑ Ñеализован ÑоглаÑно ÑÑловиÑ.*/
public class Solution {
private boolean[][] humansRelationships;
public static void main(String[] args) {
Solution solution = new Solution();
solution.humansRelationships = generateRelationships();
Set allFriendsAndPotentialFriends = solution.getAllFriendsAndPotentialFriends(4, 2);
System.out.println(allFriendsAndPotentialFriends); //expected: [0, 1, 2, 3, 5, 7]
Set potentialFriends = solution.removeFriendsFromSet(allFriendsAndPotentialFriends, 4);
System.out.println(potentialFriends); //expected: [2, 5, 7]
}
public Set getAllFriendsAndPotentialFriends(int index, int deep) {
Set result = new HashSet<>();
if (deep == 0) return result;
for (int i = 0; i < humansRelationships.length; i++) {
if (i < index) {
if (humansRelationships[index][i]) {
result.add(i);
result.addAll(getAllFriendsAndPotentialFriends(i, deep - 1));
}
} else {
if (humansRelationships[i][index]) {
result.add(i);
result.addAll(getAllFriendsAndPotentialFriends(i, deep - 1));
}
}
}
result.remove(index);
return result;
}
//remove people from set, with which you have already had relationship
public Set removeFriendsFromSet(Set set, int index) {
for (int i = 0; i < humansRelationships.length; i++) {
if ((i < index) && (index < humansRelationships.length) && humansRelationships[index][i]) {
set.remove(i);
} else if ((i > index) && humansRelationships[i][index]) {
set.remove(i);
}
}
return set;
}
//return test data
private static boolean[][] generateRelationships() {
return new boolean[][]{
{true}, //0
{true, true}, //1
{false, true, true}, //2
{false, false, false, true}, //3
{true, true, false, true, true}, //4
{true, false, true, false, false, true}, //5
{false, false, false, false, false, true, true}, //6
{false, false, false, true, false, false, false, true} //7
};
}
}