Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Java [игнор отключен] [закрыт для гостей] / В какую сторону двигаться? / 11 сообщений из 11, страница 1 из 1
24.02.2018, 23:56
    #39606876
Tsyklop
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
В какую сторону двигаться?
Есть такое задание:
https://drive.google.com/file/d/1xoOlk_b9t3kCp1GLJtt2BDVTxZsme29T/view?usp=sharing

Считывание файла сделано.

Вот теперь встал в тупик перед тем как реализовать саму сортировку. Может у кого идеи есть. Я не прошу кода, а мысли, варианты как можно сделать.

Спасибо.
...
Рейтинг: 0 / 0
25.02.2018, 00:41
    #39606887
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
В какую сторону двигаться?
1. Пишем проверку подходит ли конкретная расстановка под требования.
2. Запускаем полный перебор выполня проверку для каждой комбинации.
3. Оптимизируем, отсекая комбинации, которые не подходят не досчитывая их до конца.
...
Рейтинг: 0 / 0
25.02.2018, 09:44
    #39606906
Nixic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
В какую сторону двигаться?
TsyklopСчитывание файла сделано.

Куда считывается?
Просто я посмотрел на задачу и думаю, что просто записывать значению куда-то вот сюда:
private List<List<Integer>> lists = new ArrayList<>();
private List<Integer> list = new ArrayList<>();
Не совсем будет правильно, потому как есть у углов соседи и каждому углу бы надо задать свойство, хотя бы простым int, т.е. если он один, то это 1, если у него есть сосед, то их уже 2 и значит значение 2 и т.д.

Т.е. нужно правильно построить объекты после чтения данных из файла.
Но! У меня есть подозрение, что здесь можно использовать что-то математическое, что мне неизвестно, потому как, если считать соседей у каждого элемента, то можно заметить, что дойдя до 6-го кубика, у него углы по количеству соседей начинают отзеркаливаться.
т.е. у первого кубика
1,2,3,4
у последнего:
4,3,2,1

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

Кошмар какой)))
...
Рейтинг: 0 / 0
25.02.2018, 16:27
    #39606979
Nixic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
В какую сторону двигаться?
Понравилась мне эта задачка, думал найду решение в инете, аннет, нашел только саму задачу, видимо оттуда и пришла она ТС'у :)
https://www.edss.ee/test_eng.html
Если выдал тайну, извиняйте :)

На данный момент у меня есть только алгоритм поиска соседей у каждой ячейки.
Если кратко, то сначала надо работать с полным квадратом из квадратов, т.е. как будто у нас 4 на 4, т.е. 16 ячеек.
Пишем алгоритм поиска соседей, включая тех что по диагонали, собираем их индексы в отдельные массивчики.
Затем из массива вычитаем массив ненужных интов и получаем у каждого только тех соседей которые есть в задаче.
Код: java
1.
2.
3.
        List<Integer> integerList = kubiki2.findAllNeighbors(currentIndex);
        Integer[] removedInts = {0, 3, 12, 15};
        integerList.removeAll(Arrays.asList(removedInts));



Дальше делаем что-то типа хешМапы, чтобы установить каждому кубику по его индексу "вес" его углов, как писал ранее, это кол-во углов других кубиков с которыми угол конкретного кубика граничит
Код: java
1.
HashMap<Integer, Integer[]> anglesWightMap = new HashMap<>();

ключ это индекс кубика, массив внутри это 4 числа обозначающих кол-во граничащих углов.

Получается что-то вроде вот такого, как на скриншоте. Но пока я не придумал как бы сделать так, чтобы вес углов сам считался у кубика.
А вообще надо подумать, нужен ли этот самый вес или использовать что-то другое...

И да, индексация у меня идёт как по кубику 4x4, то есть два кубика в верхнем ряду из задачи у меня с индексами 1 и 2, а нижние 2 с 13 и 14. Потому что индексация не прервана на углах, надеюсь, более менее понятно что к чему :)

Если не учитывать "вес углов" и хотя бы просто сложить и получить результаты, то... а вот до сюда я пока не дошел. Если не надоест, допилю попозже :)
...
Рейтинг: 0 / 0
25.02.2018, 19:16
    #39607012
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
В какую сторону двигаться?
Nixic,

Массив Integer-ов - нечитабельно (:
Для начала введем спец. структуру Square:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
public static class Square {
    
    public int upperLeft;
    public int upperRight;
    public int bottomLeft;
    public int bottomRight;

    public static final Square EMPTY = new Square(-1, -1, -1, -1);
    
    public Square(String line) {
        Integer[] values = 
            Stream
                .of(line.split("\\d+"))
                .map(Integer::valueOf)
                .toArray(sz -> new Integer[sz]);
        
        upperLeft = values[0];
        upperRight = values[1];
        bottomLeft = values[2];
        bottomRight = values[3];
    }
    
    public Square(int ul, int ur, int bl, int br) {
        upperLeft = ul;
        upperRight = ur;
        bottomLeft = bl;
        bottomRight = br;
    }
    
    @Override
    public String toString() {
        return 
            String.format
                ("%d %d %d %d", 
                    upperLeft, upperRight, bottomLeft, bottomRight);
    }
}
...
Рейтинг: 0 / 0
25.02.2018, 21:02
    #39607026
Nixic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
В какую сторону двигаться?
Usman,
я тоже сразу это добавил, правда назвал как-то странно)) Cube, ну типа кубик же, правда плоский)
Cube
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
class Cube {

    private Integer orderNum; // номер кубика по порядку
    private Angle angleA;
    private Angle angleB;
    private Angle angleC;
    private Angle angleD;

    public Cube(Integer orderNum, Angle angleA, Angle angleB, Angle angleC, Angle angleD) {
        this.orderNum = orderNum;
        this.angleA = angleA;
        this.angleB = angleB;
        this.angleC = angleC;
        this.angleD = angleD;
    }

    public Angle getAngleA() {
        return angleA;
    }

    public Angle getAngleB() {
        return angleB;
    }

    public Angle getAngleC() {
        return angleC;
    }

    public Angle getAngleD() {
        return angleD;
    }
}



Ну и еще угол, как отдельный объект:
Код: java
1.
2.
3.
4.
5.
6.
7.
class Angle {
    private Integer parentNumber; // номер кубика, которому принадлежит угол
    private Integer number; // номер угла по порядку, с левого вправо, затем с левого нижнего вправо, т.е. буквой Z.
    private Integer neighbors; // тип угла куба по количеству соседних углов, 1 - один тип угла, без соседей, 
// 2 - значит есть один сосед, 3 - значит есть еще два соседа, 4 - значит 3 соседа, т.е. вместе 4 угла соприкасаются
    private Integer value; // значение цифры в угле.
....



Но, насколько бы это было бы всё наглядно, оно всё добавляет такиие портянки.
Есть над чем подумать, в общем.
Я за отход от ООП в данном случае. А в качестве визуальной схемы выступают ячейки в открытом рядом экселе с индексацией кубиков :)
...
Рейтинг: 0 / 0
25.02.2018, 21:59
    #39607039
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
В какую сторону двигаться?
Usman
Код: java
1.
line.split("\\d+")

Код: java
1.
line.split("\\s+")
...
Рейтинг: 0 / 0
25.02.2018, 22:00
    #39607040
Tsyklop
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
В какую сторону двигаться?
То что есть у меня:

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
import java.io.File;
import java.io.IOException;
import java.nio.file.Files;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        try {

            File inputTxt = new File("input.txt");

            ArrayList<Square> squares = new ArrayList<>();

            List<String> lines = Files.readAllLines(inputTxt.toPath());

            int index = 1;
            for(String line: lines) {
                String[] arr = line.split(" ");
                squares.add(new Square(index, Integer.parseInt(arr[0]), Integer.parseInt(arr[1]), Integer.parseInt(arr[2]), Integer.parseInt(arr[3])));
                index++;
            }

            for(Square square: squares){
                System.out.println("======");
                System.out.println(square);
            }

        } catch (IOException e) {
            e.printStackTrace();
        }

    }

}



Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
public class Square {

    private int index;

    private int topLeft;
    private int topRight;
    private int bottomLeft;
    private int bottomRight;

    public Square(int index, int topLeft, int topRight, int bottomLeft, int bottomRight) {
        this.index = index;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }

    public int getIndex() {
        return index;
    }

    public int getTopLeft() {
        return topLeft;
    }

    public int getTopRight() {
        return topRight;
    }

    public int getBottomLeft() {
        return bottomLeft;
    }

    public int getBottomRight() {
        return bottomRight;
    }

    @Override
    public String toString() {
        return topLeft+"    "+topRight+"\n\n"+bottomLeft+"    "+bottomRight;
    }
}
...
Рейтинг: 0 / 0
25.02.2018, 22:02
    #39607041
Tsyklop
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
В какую сторону двигаться?
Nixic,

Хорошая мысль с соседями)
...
Рейтинг: 0 / 0
25.02.2018, 22:14
    #39607043
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
В какую сторону двигаться?
Tsyklop,

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
import java.util.Scanner;
...

public static final Integer SIZE = 4; // размер матрицы с квадратами
...

Square[][] matrix = new Square[SIZE][SIZE];

// пустые ячейки (квадраты)
matrix[0][0] = Square.EMPTY;
matrix[0][SIZE - 1] = Square.EMPTY;
matrix[SIZE - 1][0] = Square.EMPTY;
matrix[SIZE - 1][SIZE - 1] = Square.EMPTY;

// считываем из входного потока (не файла)
try (Scanner scan = new Scanner(System.in)) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (matrix[i][j] != Square.EMPTY) {
                if (scan.hasNextLine()) { // только здесь не учтено для случая с несколькими столбцами
                    String line = scan.nextLine();
                    matrix[i][j] = new Square(line);
                }
            }
        }
    }
}
...
Рейтинг: 0 / 0
26.02.2018, 08:16
    #39607094
Nixic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
В какую сторону двигаться?
Комбинаций может быть 12 факториал, то есть дофигища!
Поэтому при первом же несовпадении в одной комбинации нужно делать перестановку, чтобы не тратить время и ресурсы.
Вот только мне уже некогда сегодня до вечера думать/гуглить как делать перестановки, какой алгоритм, а он наверняка гуглится на раз-два.
...
Рейтинг: 0 / 0
Форумы / Java [игнор отключен] [закрыт для гостей] / В какую сторону двигаться? / 11 сообщений из 11, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]