Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 11 12 13 14 15 16 17 [18] 19 20   вперед  Ctrl
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35696
Это утка. :)
7 окт 17, 21:23    [20851370]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35696
Вот вчера накрапал. Есть много TODO-s. Но в целом. Работает.
+
package mayton.chess;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import javax.annotation.Nonnull;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static java.lang.String.join;
import static java.lang.String.valueOf;
import static java.lang.System.out;

public class MtnQueensGenerator {

    static Logger logger = LoggerFactory.getLogger(MtnQueensGenerator.class);

    public static Integer tailElement(@Nonnull List<Integer> arg) {
        return arg.get(arg.size() - 1);
    }

    // TODO: Remove
    public static List<Integer> headElements(@Nonnull List<Integer> arg) {
        int n = arg.size();
        return arg.stream().limit(n - 1).collect(Collectors.toList());
    }
    public static List<Integer> subList(@Nonnull List<Integer> arg, int i) {
        if (arg == null) {
            throw new IllegalArgumentException("Array cannot be null!");
        }
        int n = arg.size();
        if (i < 0 || i >= n) {
            throw new IllegalArgumentException("Index is out of range");
        }
        if (i == 0) {
            if (n == 1) {
                return Collections.emptyList();
            } else {
                // TODO: Investigate for performance
                return arg.stream().skip(1).collect(Collectors.toList());
            }
        }
        if (i == n - 1) {
            // TODO: Investigate for performance
            return arg.stream().limit(n - 1).collect(Collectors.toList());
        }
        // TODO: Investigate for performance
        List<Integer> res = new ArrayList<>(arg.stream().limit(i).collect(Collectors.toList()));
        res.addAll(arg.stream().skip(i + 1).collect(Collectors.toList()));
        return res;
    }

    public static boolean isConsistent(@Nonnull List<Integer> q, int candidate) {
        int n = q.size();
        for (int i = 0; i < n; i++) {
            int qi = q.get(i);
            int deltai = n - i;
            int deltaRow = qi - candidate;
            if (Math.abs(deltaRow) == deltai) {
                return false;
            }
        }
        return true;
    }

    private static void printSolution(@Nonnull List<Integer> queens) {
        out.printf("Queens : %s\n", formatQueens(queens));
        out.printf("----------------\n");
        int n = queens.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                out.print(queens.get(i) == j ? "Q" : "*");
                out.print(" ");
            }
            out.println();
        }
        out.println();
    }

    // TODO: Replace with Guava or smth else
    static List<Integer> fromArray(@Nonnull int[] array) {
        List<Integer> res = new ArrayList<>(array.length);
        for (int elem : array) {
            res.add(elem);
        }
        return res;
    }


    public static String formatQueens(List<Integer> list) {
        StringBuilder sb = new StringBuilder("");
        sb.append(join(",", valueOf(list)));
        sb.append("");
        return sb.toString();
    }

    public static void process(int n, int level, @Nonnull List<Integer> candidates, @Nonnull List<Integer> selected) {
        if (selected.size() == n) {
            // TODO: Improove overloaded isConsistent
            if (isConsistent(headElements(selected), tailElement(selected))) {
                solutions++;
                printSolution(selected);
            }
        } else {
            for (int i = 0; i < candidates.size(); i++) {
                int newCandidate = candidates.get(i);
                if (isConsistent(selected, newCandidate)) {
                    List<Integer> newSelected = new ArrayList<>(selected);
                    newSelected.add(newCandidate);
                    process(n, level + 1, subList(candidates, i), newSelected);
                }
            }
        }
    }

    static int solutions = 0;

    public static void main(String[] args) {
        int n = 8;
        process(n, 0, fromArray(IntStream.range(0, n).toArray()), new ArrayList<>());
        out.printf("Solutions : %d", solutions);
    }

}
8 окт 17, 10:49    [20851869]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35696
Я думаю... форкну тему в Java в части оптимизации массивов. Здесь - будем обсуждать алгоритмизацию
а техники language-related - лучше отдельно.
8 окт 17, 14:52    [20852157]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
asutp2
Member

Откуда: Тюмень
Сообщений: 183
Модератор взял и поудалял мои сообщения, хотя в коде реализации обсуждаемого алгоритма есть явные ошибки.
Модератор: Надо указывать на ошибки, а не разводить холивар с переходом на личности
8 окт 17, 18:14    [20852531]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35696
asutp2, там нет major ошибок. Основной алгоритм-то работает? Работает.
8 окт 17, 18:17    [20852539]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
asutp2
Member

Откуда: Тюмень
Сообщений: 183
mayton,

хуже нет, когда правильный алгоритм реализован с ошибками в коде. И потом получается, что на тестовых данных все работает, выпускаем в продакшн, начинаются непонятки.
8 окт 17, 18:23    [20852567]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35696
asutp2, как вы определите какой алгоритм правильный а какой нет?

Шарахов реализовал расстановку ферзей. На тестовых данных она работает.

Я точно так-же поступаю. Супер-провидения насчет ошибок которых я не увидел
у меня нет. Модульные тесты + four eyes check. Вот на чем стоит весь ентерпрайз.
8 окт 17, 18:26    [20852576]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
asutp2
Member

Откуда: Тюмень
Сообщений: 183
И если говорить о реализации, не увидел использования распараллеливания.
8 окт 17, 18:27    [20852579]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35696
asutp2
И если говорить о реализации, не увидел использования распараллеливания.

А что он претендовал на это?
8 окт 17, 18:30    [20852595]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
asutp2
Member

Откуда: Тюмень
Сообщений: 183
mayton
asutp2, как вы определите какой алгоритм правильный а какой нет?

Шарахов реализовал расстановку ферзей. На тестовых данных она работает.

Я точно так-же поступаю. Супер-провидения насчет ошибок которых я не увидел
у меня нет. Модульные тесты + four eyes check. Вот на чем стоит весь ентерпрайз.
Я не знаю, правильный алгоритм или нет (не вникал). Но я вижу опубликованный код конкретной функции на delphi, содержащей явные ошибки. Мне кажется, этого вполне достаточно, чтобы судить о качестве реализации. И предполагаю, что если таким же образом написан весь остальной код алгоритма, то правильность его работы вызывает как минимум сомнение.
8 окт 17, 18:30    [20852596]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
Можно сказать короче: там нет ошибок.

Чтобы утверждать другое, необходимо привести хотя бы один пример, когда функция выдает неверный результат.
8 окт 17, 18:34    [20852612]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35696
Я сделал ему своё замечание касающееся стиля разработки. И коллаборации.

Кстати мой сорс опубликован здесь. Велкам.
8 окт 17, 18:34    [20852614]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35696
asutp2
Но я вижу опубликованный код конкретной функции на delphi, содержащей явные ошибки. Мне кажется, этого вполне достаточно, чтобы судить о качестве реализации.

Вы знаете. Функция которая складывает 2 числа типа integer УЖЕ содержит ошибки. Но они касаются
очень глубоких случаев behaviour когда переполняется разрядная сетка и надо принять решение.

Я уверен. Что ВЫ. Шарахов. И я. И все другие разработчики в 99.99% случаев не обращают
на это внимание. Хотя это баг, на который надо среагировать и покрыть это тестами хотя-бы
на уровне пограничных.

Но мы в энтерпрайзе обычно считаем что эти кейсов с переполнением нет и быть не может.
И именно поэтому мы НЕ считаем что функция с ошибкой. Мы просто считаем что ситуация
настолько маловероятна что не стоит с ней заморачиваться. Это как коллизия GUID. Она
теоретически есть но всем забить на нее болт ибо вероятнее вам по башке упадет метеорит.

Как то так.
8 окт 17, 18:39    [20852636]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
asutp2
Member

Откуда: Тюмень
Сообщений: 183
Aleksandr Sharahov
Попробовал на поле 50000х50000 в центральный квадрат 25000х25000 случайно ставить 12500 ферзей.
Завершение нашлось во всех 10 проведенных тестах.


поле 50000x50000 содержит 2.500.000.000 клеток. У Integer (в delphi) максимально возможное число 2.147.483.647. Как проводились тесты с наличием потенциальной ошибка переполнения из за используемых типов данных? И еще - для поля такого размера использовано всего 10 тестов?
8 окт 17, 18:45    [20852654]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
asutp2
Member

Откуда: Тюмень
Сообщений: 183
mayton
Но мы в энтерпрайзе обычно считаем что эти кейсов с переполнением нет и быть не может.
И именно поэтому мы НЕ считаем что функция с ошибкой. Мы просто считаем что ситуация
настолько маловероятна что не стоит с ней заморачиваться. Это как коллизия GUID. Она
теоретически есть но всем забить на нее болт ибо вероятнее вам по башке упадет метеорит.
Это вы за ВСЕХ в энтерпрайзе так говорите или только за себя?
8 окт 17, 18:48    [20852663]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
asutp2
Я не знаю, правильный алгоритм или нет (не вникал). Но я вижу опубликованный код конкретной функции на delphi, содержащей явные ошибки. Мне кажется, этого вполне достаточно, чтобы судить о качестве реализации. И предполагаю, что если таким же образом написан весь остальной код алгоритма, то правильность его работы вызывает как минимум сомнение.


Хватит пороть бред. От этого код не станет неверным.

Укажи конкретное место ошибки. Что должны получить и что получаем.
8 окт 17, 18:52    [20852674]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
asutp2
Aleksandr Sharahov
Попробовал на поле 50000х50000 в центральный квадрат 25000х25000 случайно ставить 12500 ферзей.
Завершение нашлось во всех 10 проведенных тестах.


поле 50000x50000 содержит 2.500.000.000 клеток. У Integer (в delphi) максимально возможное число 2.147.483.647.

И что? На твой взгляд, это имеет значение, когда мы ищем единственное завершение?


asutp2
Как проводились тесты с наличием потенциальной ошибка переполнения из за используемых типов данных?

Весь код доступен. Диапазон количества решений известен. Не увидеть тип int64 невозможно. Глаза есть?
Зато есть непоколебимая уверенность в наличии ошибки.


asutp2
И еще - для поля такого размера использовано всего 10 тестов?

Конечно, нет. Это была отладка.
8 окт 17, 19:01    [20852689]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Dima T
Member

Откуда:
Сообщений: 11465
Модератор: Не понимаю зачем тут приплетать энтерпрайз? Тут не курсы для джунов, не надо тут демагогию на эту тему устраивать.
Какой вообще может быть энтерпрайз по расстановке ферзей?

Прекращаем обсуждать подходы и стили написания кода, т.к. топик совсем не про это.
8 окт 17, 19:11    [20852701]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35696
asutp2
mayton
Но мы в энтерпрайзе обычно считаем что эти кейсов с переполнением нет и быть не может.
И именно поэтому мы НЕ считаем что функция с ошибкой. Мы просто считаем что ситуация
настолько маловероятна что не стоит с ней заморачиваться. Это как коллизия GUID. Она
теоретически есть но всем забить на нее болт ибо вероятнее вам по башке упадет метеорит.
Это вы за ВСЕХ в энтерпрайзе так говорите или только за себя?

Я говорю за себя и за то комьюнити которое меня окружает последние лет 10-15.
Ничего нового в оценке качества ПО не было придумано. Модульные тесты. UAT.
Акцептенс-тестинг. И всё. Никаких других магий не придумано для поиска ошибок.

И разумеется коде-ревью про которое я уже упоминал. И которое вообще ниочом
и просто гарантирует что коллега во время просмотра вашего кода ни разу не воскликнул
"Whats the fuck...".
8 окт 17, 19:27    [20852725]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
asutp2
Member

Откуда: Тюмень
Сообщений: 183
Aleksandr Sharahov
asutp2
Я не знаю, правильный алгоритм или нет (не вникал). Но я вижу опубликованный код конкретной функции на delphi, содержащей явные ошибки. Мне кажется, этого вполне достаточно, чтобы судить о качестве реализации. И предполагаю, что если таким же образом написан весь остальной код алгоритма, то правильность его работы вызывает как минимум сомнение.


Хватит пороть бред. От этого код не станет неверным.

Укажи конкретное место ошибки. Что должны получить и что получаем.


ок, укажу конкретное место ошибки в IsSolutionValid:

var
  i, r, c: integer;

помним, что I может принимать значения в диапазоне [-2147483648..2147483647]
теперь смотрим цикл
for i:=0 to BoardSize-1 do

и смотрим в цикле код
if (cardinal(c)>=BoardSize) or (cardinal(r)>=BoardSize) then exit;

последний участок кода говорит о том, что BoardSize имеет тип Cardinal. Что говорит дока делфи о Cardinal? Это беззнаковый тип, хранящий значения в диапазоне [0..4294967295].
Значит при I: Integer и BoardSize: Cardinal имеем ситуацию, что при достижении I=2147483647 цикл выполнится, а затем прервется и проверка в большем диапазоне значений не будет выполнена (т.е. когда > 2147483647). Это нормально?
8 окт 17, 20:18    [20852831]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
asutp2
Member

Откуда: Тюмень
Сообщений: 183
Aleksandr Sharahov
Весь код доступен
Доступен где? Ссылку плиз
8 окт 17, 20:22    [20852846]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
asutp2
ок, укажу конкретное место ошибки в IsSolutionValid:

var
  i, r, c: integer;

помним, что I может принимать значения в диапазоне [-2147483648..2147483647]
теперь смотрим цикл
for i:=0 to BoardSize-1 do

и смотрим в цикле код
if (cardinal(c)>=BoardSize) or (cardinal(r)>=BoardSize) then exit;

последний участок кода говорит о том, что BoardSize имеет тип Cardinal.


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



asutp2
Что говорит дока делфи о Cardinal? Это беззнаковый тип, хранящий значения в диапазоне [0..4294967295].
Значит при I: Integer и BoardSize: Cardinal имеем ситуацию, что при достижении I=2147483647 цикл выполнится, а затем прервется и проверка в большем диапазоне значений не будет выполнена (т.е. когда > 2147483647). Это нормально?

[/quot]
Опять же, если б ты учился на пятерки, то знал бы, что при установленном знаковом бите в значении BoardSize-1 цикл вообще не начнет выполняться. Опять двойка.

Это как раз тот случай, когда лучше молчать.




asutp2
Aleksandr Sharahov
Весь код доступен
Доступен где? Ссылку плиз


mayton, извини, придется ему отрыть тайну: http://guildalfa.ru/alsha/node/35
8 окт 17, 21:06    [20852958]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
asutp2
Member

Откуда: Тюмень
Сообщений: 183
Aleksandr Sharahov
if (cardinal(c)>=BoardSize) or (cardinal(r)>=BoardSize) then exit;

Aleksandr Sharahov
Последний участок кода говорит о том, что использовано явное приведение переменной c к типу cardinal

Aleksandr Sharahov
Переменная BoardSize имеет тип integer


Сравниваешь Integer с Integer, но первый Integer приводишь к Cardinal? Точно индусы курят нервно в стороне)))))
8 окт 17, 21:35    [20853011]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1361
asutp2
Aleksandr Sharahov
if (cardinal(c)>=BoardSize) or (cardinal(r)>=BoardSize) then exit;

Aleksandr Sharahov
Последний участок кода говорит о том, что использовано явное приведение переменной c к типу cardinal

Aleksandr Sharahov
Переменная BoardSize имеет тип integer


Сравниваешь Integer с Integer, но первый Integer приводишь к Cardinal? Точно индусы курят нервно в стороне)))))


Для переменных типа integer этот код эквивалентен такому
if (c>=BoardSize) or (c<0) or (r>=BoardSize) or (r<0) then exit;


Ты не выучил урок "Прямое попадание" отсюда http://guildalfa.ru/alsha/node/20
Третья двойка. Второгодник.

Достал уже. Иди лечи свои комплексы.
8 окт 17, 21:43    [20853019]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
asutp2
Member

Откуда: Тюмень
Сообщений: 183
Йоу, посмотрел код по ссылке. Жесть.

const
  MaxBoardSize= 100000;
  CountCol: array[0..MaxBoardSize-1] of byte;   
  CountRow: array[0..MaxBoardSize-1] of byte;  
  CountDiagP: array[0..2*MaxBoardSize-2] of byte;
реально что ли используются статические массивы такого размера?
begin;
што?
label
  NEXT1, NEXT2, NEXT3, PROC1, PROC2, PROC3, BACK1, BACK2, BACK3, FINISH;
на turbo pascal что ли пишешь?)

Не увидел по ссылке обсуждаемую выше функцию. Протухшая версия?
8 окт 17, 21:47    [20853023]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 11 12 13 14 15 16 17 [18] 19 20   вперед  Ctrl
Все форумы / Программирование Ответить