Загадка с цветными треугольниками - PullRequest
Новая
       48

Загадка с цветными треугольниками

0 голосов
/ 07 декабря 2018

Загадка, которую я надеюсь разгадать, может быть найдена в этом видео .

Если вам не удается просмотреть все видео, вот краткое описание загадки:

enter image description here

Короче говоря, мне нужно найти наименьшее количество точек, где гарантированно будет хотя бы один одноцветный треугольник из любого расположениякрасные и синие линии, соединяющие каждую пару точек.

Ниже приведена программа на Java, которую я написал для ее решения. 

public class RedBlueTimeTravelProblem {

    public static void main(String[] args) {
        int max = 3;
        boolean alltri = false;
        long start, end;
        double time;

        while (!alltri) {
            start = System.nanoTime();

            int edgecount = max * (max - 1) / 2;
            int combos = (int) Math.pow(2, edgecount);
            alltri = false;

            for (int i=1; i<=combos; i++) {
                int a = i-1;
                int[][] edge = new int[edgecount][3];

                for (int j=0; j<edgecount; j++) {
                    edge[j][2] = a % 2;
                    a = (a - a % 2) / 2;
                }

                int c2 = 0;
                for (int j=1; j<=max; j++) {
                    for (int k=j+1; k<=max; k++) {
                        edge[c2][0] = j;
                        edge[c2][1] = k;
                        c2++;
                    }
                }

                boolean tri = false;
                for (int j=0; j<edgecount-2; j++) {
                    for (int k=j+1; k<edgecount-1; k++) {
                        for (int m=k+1; m<edgecount; m++) {
                            if ((edge[j][0] == edge[k][0] && ((edge[j][1] == edge[m][0] && edge[k][1] == edge[m][1]) || (edge[j][1] == edge[m][1] && edge[k][1] == edge[m][0]))) ||
                                    (edge[j][0] == edge[k][1] && ((edge[j][1] == edge[m][0] && edge[k][0] == edge[m][1]) || (edge[j][1] == edge[m][1] && edge[k][0] == edge[m][0]))) ||
                                    (edge[j][0] == edge[m][0] && ((edge[j][1] == edge[k][0] && edge[k][1] == edge[m][1]) || (edge[j][1] == edge[k][1] && edge[k][0] == edge[m][1]))) ||
                                    (edge[j][0] == edge[m][1] && ((edge[j][1] == edge[k][0] && edge[k][1] == edge[m][0]) || (edge[j][1] == edge[k][1] && edge[k][0] == edge[m][0])))) {
                                tri = tri || (edge[j][2] == edge[k][2] && edge[k][2] == edge[m][2]);
                            }
                        }
                    }
                }
                alltri = alltri && tri;
            }
            end = System.nanoTime();
            time = (end - start) / 1000000000.0;
            System.out.println(max + ": " + time + " seconds");
            max++;
        }
        System.out.println("DONE");
    }

}

Кажется, что до сих пор работает проверка 3, затем 4, 5 и т. Д. Очки гарантируют один цветной треугольник, но его временная сложность смешна.Например, здесь время для 3-8 баллов:

3: 1,8475E-5 секунд

4: 2,59876E-4 секунды

5: 0,009313668 секунд

6: 0,192455789 секунд

7: 19,226652708 секунд

Исходя из тренда, 8 баллов займет от 30 минут до 1 часа, 9 баллов займет примерно несколько дней, 10займет более 6 месяцев, и хорошо ... никто не хочет ждать так долго.

Есть какие-либо предложения о том, как сделать мою программу более эффективной?

Редактировать: Очевидно, ответ был 6.Мало того, что мой код был неэффективен, это было просто неправильно.Также спасибо всем за предложения.

...