Научный подход: Что лучше подтверждать многократно или опровергнуть 1 раз?

Такой вот диалог состоялся сегодня. С позволения коллеги опубликую его часть. Спасибо собеседнику за чудный диалог!

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

Q: ... это гипотеза, и она может стать самоисполняющимся пророчеством, если ее попробовать подтверждать, а не не опровергнуть. Знаешь этот баяс?

A: давай)

Q: Есть загадка. Есть некоторая закономерность. Вот ее три числа из нее: 2 4 8.
Твоя задача:
1) или сказать мне какая закономерность мной задумана
2) или предложить 3 другие цифры ряда чтобы проверить подходит или нет
Я могу только так делиться с тобой инфой
на 1) вопрос "да, это загаданная мной закономерность" или "нет, это не та закономерность что я загадал"
и на второй вопрос "да, эти числа подходят под загаданную закономмерность" или "нет, не подходят"

A: арифметичская прогрессия ?)

Q: нет

A: цифры на numpad в виде ромбика?

Q: нет

A: 16 32 64

Q: подходит под мою закономерность что я загадал

A: чет я изначально подумал там 2 4 6 8, а оказся просто степени двойки)

Q: нет не степень двойки

A: ну я угадал 2 часть? нужно теперь закономерность? просто каждое число это предыдущие 2 помноженные, забыл как называется)

Q: нет это не то что загадано

A: типа фибоначчи только перемноженные. а нет, не подходит

Q: нет не чиса фибоначчи загаданы

A: 32 256 8192

Q: 32 256 8192 - подходит

A: может это просто любые четные числа?

Q: нет, не эту закономерность я загадал

A: я сдаюсь)

Q: я сейчас умничаю чуть, но так же было не просто. потом ты сможешь сделать то же с другими ребятами

A: алгоритмы не мой конёк)

Q: смотри один момент.
можно докзывать гипотезу, пытаться подтвердить ее тестами, которые сразу зеленые.
а можно попробовать опровергнуть гипотезу, и попытаться найти тест, который будет красный

A: то есть мне следовало сначала попробовать неверную комбинацию?

Q: у тебя есть идея, например степень двойки
и вместо того, чтобы ее подтвержать
2 4 8
16 32 64
128 256 512
что все будет да да да, напиши один тест, который опровергнет ее и посмотри что будет

A: а ты как среагируешь - скажешь что подходит?

Q: давай проверим - зависсит от того что я загадал

A: 9 6 3

Q: это не подходит
идея в том, что 1 фейл тест сразу отсекает гипотезу, но 10000 саксес тестов не делают того же

A: ага

Q: а баяс в том, что люди и их метод познания мира заточен by default под подтверждение - сразу выдвинуть гипотезу, посмотреть что она работает и погнали, а она объясняет только часть модели мира, и то очень поверхностно

A: есть вроде какой-то вид тестирования, в основе которого такой принцип

Q: Test Driven Development с его fail first

A: нет, я про сначала все опровержения, т.е. негативные кейсы)
то есть у тебя реальная закономерность

Q: да

A: ну мне только брутфорсом остаётся)
0 2 4

Q: подходит

A: 4 8 3

Q: 16 32 64 - true
32 256 8192 - true
9 6 3 - false
0 2 4 - true
4 8 3 - false

A: нечётные - падают

Q: а попробуй опровергни эту гипотезу?
она рабочая у тебя - и сразу могу сказать что это не то что я загадал, но попробуй это тестом покажи

A: опровергнуть гипотезу что все четные - true?)

Q: да, какой тест может ее опровергнуть, ну или набор тестов - ты не ограничен в попытках

A: можно ограничиться 2 тестами
1 1 1
2 2 2
первое упадет второе пройдет

Q: 16 32 64 - true
32 256 8192 - true
9 6 3 - false
0 2 4 - true
4 8 3 - false
1 1 1 - false
2 2 2 - false

A: хм
значит и порядок важен?
пробуем 2 3 4

Q: и это тоже гипотеза, опровергни ее
16 32 64 - true
32 256 8192 - true
9 6 3 - false
0 2 4 - true
4 8 3 - false
1 1 1 - false
2 2 2 - false
2 3 4 - true

A: 2 4 3

Q: 16 32 64 - true
32 256 8192 - true
9 6 3 - false
0 2 4 - true
4 8 3 - false
1 1 1 - false
2 2 2 - false
2 3 4 - true
2 4 3 - false

A: значит не связано с чётностью, а только порядок важен

Q: это гипотеза
или тест, или закономерность
я смогу провалидировать
даешь больше fail тестов!

A: 0 0 1
будет много тестов)

Q: 16 32 64 - true
32 256 8192 - true
9 6 3 - false
0 2 4 - true
4 8 3 - false
1 1 1 - false
2 2 2 - false
2 3 4 - true
2 4 3 - false
0 0 1 - false

A: 0 1 0

Q: отлично
16 32 64 - true
32 256 8192 - true
9 6 3 - false
0 2 4 - true
4 8 3 - false
1 1 1 - false
2 2 2 - false
2 3 4 - true
2 4 3 - false
0 0 1 - false
0 1 0 - false

A: надо проверять каждую позицию
1 0 0

Q: 16 32 64 - true
32 256 8192 - true
9 6 3 - false
0 2 4 - true
4 8 3 - false
1 1 1 - false
2 2 2 - false
2 3 4 - true
2 4 3 - false
0 0 1 - false
0 1 0 - false
1 0 0 - false

A: 1 2 0

Q: 16 32 64 - true
32 256 8192 - true
9 6 3 - false
0 2 4 - true
4 8 3 - false
1 1 1 - false
2 2 2 - false
2 3 4 - true
2 4 3 - false
0 0 1 - false
0 1 0 - false
1 0 0 - false
1 2 0 - false

A: 9 2 3

Q: ...
9 2 3 - false

A: 1 2 3

Q: 1 2 3 - true

A: ну всё я уверен
есть закономерность
каждое число больше предыдущего
я проверил все 3 позиции

Q: верно!
смотри что интересно, когда ты начинаешь генерить тесты которые будут false по твоему ты можешь получить diff между я думал А (false), а на самом деле Б (true)
вот так отсеиваются гипотезы
в этом суть научного подхода
если ты генеришь тесты которые true - то скорее всего ты будешь получать подтверждения гипотезы, что не доказывает ее правдивость
хоть 10000000 раз подтверди

A: ну это примерно как проверяют вакцины
согласен, проще сначала опровергнуть

Q: все потому что одно может включать другое просто

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

A: и вроде у всех всё сходится, и у каждого своя правда

Q: так и живем
одними и теми же словами описывая разный опыт
потому что у Homo Sapiens есть баясы
их много вообще

Q: А про научный подход есть видео хорошее, очень рекомендую

Если думаешь что что-то правда изо всех сил старайся это опровергнуть, если это не получится как ты не старайся - вероятно ты подобрался/алась близко к истине.

TDD что он может?

На прошлом Bomberman Cdenjoy всплыла задачка makeBricks из codingbat.com. Вопрос был в том, как бы я решал эту задачу ТДД. Ну, начал бы с самого простого кейса, а там по ситуации. Лучший способ демонстрации - парное программирование, потому мы с Виталиком сели в пару за комп и начали. Первый наш код получился таким.

public class Main {
    @Test
    public void test1() {
        assertBricks(true, 0, 1, 5);
        assertBricks(true, 1, 0, 1);
        assertBricks(false, 1, 0, 2);
    }

    public boolean makeBricks(int small, int big, int goal) {
        return small + big * 5 == goal;
    }

    private void assertBricks(boolean expected, int c1, int c5, int l) {
        boolean actual = makeBricks(c1, c5, l);
        assertEquals(String.format("C1 = %s, C5 = %s, L = %s, Actual = %s, But expected = True", c1, c5, l, actual, expected),
                expected, actual);
    }
}

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

public class Main {
    private static final int HHHHH = 5;
    private static final int H = 1;
    public static final boolean NO = false;
    public static final boolean YES = true;

    @Test
    public void test1() {
        YES(5, HHHHH);
        YES(1, H);
        NO(2, H);
    }

    public boolean makeBricks(int small, int big, int goal) {
        return small + big * 5 >= goal;
    }


    private void YES(int l, int... bricks) {
        assertBricks(YES, l, bricks);
    }

    private void NO(int l, int... bricks) {
        assertBricks(NO, l, bricks);
    }

    private void assertBricks(boolean expected, int l, int... bricks) {
        int c1 = 0;
        int c5 = 0;
        for (int i : bricks) {
            if (i == H) {
                c1++;
            }
            if (i == HHHHH) {
                c5++;
            }
        }
        assertL(expected, c1, c5, l);
    }

    private void assertBricks(boolean expected, int c1, int c5, int l) {
        boolean actual = makeBricks(c1, c5, l);
        assertEquals(String.format("C1 = %s, C5 = %s, L = %s, Actual = %s, But expected = True", c1, c5, l, actual, expected),
                expected, actual);
    }
}

Работа пошла быстрее! В следующие пару минут мы написали еще пачку тестов

    @Test
    public void test1() {
        YES(5, HHHHH);
        YES(1, H);
        NO(2, H);
        YES(7, HHHHH, H, H, H);
        YES(14, HHHHH, HHHHH, H, H, H, H);
        NO(14, HHHHH, HHHHH,  H, H, H);
        YES(5, HHHHH, HHHHH);
        YES(6, HHHHH, H, H, H);
        NO(9, HHHHH, H, H, H);
    }

Реализация совсем немного изменилась, чтобы соответствовать тестам.

    public boolean makeBricks(int small, int big, int goal) {
        return small + big * 5 >= goal;
    }

И тут началось самое интересное. Мы больше не могли добавить ни одного красного теста. И так и сяк. Зависли. Но в то же время http://codingbat.com/prob/p183562 сказал нам, что мы забыли как минимум один кейс.

    @Test
    public void test2() {
        NO(9, HHHHH, HHHHH, H, H, H); 
    }

И тут возник заслуженный вопрос. Какова роль ТДД тут? Почему он не помогает решить эту задачу - найти еще один красный кейс? Ответ был таким - ТДД помогает убедиться в том что, что все кейсы которые ты придумал работают (более вероятно, чем если бы ты писал без тестов). ТДД помагает в поиске новых кейсов только тем, что сразу же сигнализирует о твоих ошибках, что со временем приводит к осознанию, что "я ошибаюсь часто", "я что-то недопроверил" - а этот скепсис по направлению к своему коду, помогает задуматься над поиском дополнительных кейсов. А вот как их искать, нам подсказал уже Лёня. Комментарий Виталика был такой (и я с ним полностью согласен)

Цікаво шо ці всі викрутаси можна почати тільки від одного "чувстуетсья что что-то не то", в тому випадку у нас були тести які явно показали, якшо їх нема, то може або провтикатись, або "почувствоваться", це з досвідом приходить, професійна подозрітєльность на такі штуки. Да і рішення в тих варіантах які запропоновано в основному інтуітивні, або направлені на то шоб допомогти інтуіції прийти до червоного кейса.

Только вот хотелось бы какой-то более конкретный математический аппарат для поиска красных кейсов. Уверен, что опытные тестировщики уладеют такими инструментами. На этом пока все. Пока буду искать ответ. Как появится - опишу его тут.... Спасибо Леня, Виталик! P.S. Вот та причина, почему я люблю блог. Описал в нем проблему, отложил ее в сторону и мозг твой сгенерил решение. Мой мне напомнил про то, что есть такая чудная библиотека, которая называется Approvals (кстати в прошлом месяце вышла новая версия). Что я с ней сделал? Ну кроме того, что скачал ее отсюда. А потом прописал maven dependency

<dependency>
 <groupId>net.sourceforge.approvaltests</groupId>
 <artifactId>approvaltests</artifactId>
 <version>0.1.3</version>
 <scope>system</scope>
 <systemPath>${project.basedir}/lib/ApprovalTests-0.1.3/ApprovalTests.jar</systemPath>
</dependency>

Я написал вот такой вот несложный тест

import org.approvaltests.legacycode.LegacyApprovals;
import org.approvaltests.legacycode.Range;
...
public class Main {
...
    @Test
    public void testApprovals() throws Exception {
        LegacyApprovals.LockDown(this, "approveMakeBricks", Range.get(0, 10), Range.get(0, 10), Range.get(0, 100));
    }

    public boolean approveMakeBricks(Integer small, Integer big, Integer goal) {
        return makeBricks(small, big, goal);
    }

Запустив его я увидел что возвращает метод во всех комбинациях входных параметров. Я стал критиковать эти результаты, и уже на 133 строчке (через минуту беглого просмотра) я первую увидел неточность.

[0, 0, 0] = true 
[1, 0, 0] = true 
[2, 0, 0] = true 
[3, 0, 0] = true 
[4, 0, 0] = true 
[5, 0, 0] = true 
[6, 0, 0] = true 
...
[6, 10, 0] = true 
[7, 10, 0] = true 
[8, 10, 0] = true 
[9, 10, 0] = true 
[10, 10, 0] = true // Все что выше всегда тру, это и ежу понятно - длину 0 мы составим из элементов любого набора
[0, 0, 1] = false // тут ок потому, как материала не хватает 
[1, 0, 1] = true // все что ниже тоже ок, потому как имея хоть одну H мы сможем составить длину 1 всегда 
[2, 0, 1] = true 
[3, 0, 1] = true 
[4, 0, 1] = true 
[5, 0, 1] = true 
[6, 0, 1] = true 
[7, 0, 1] = true 
[8, 0, 1] = true 
[9, 0, 1] = true 
[10, 0, 1] = true 
[0, 1, 1] = true // а вот тут интересно! Мой алгоритм считает, что можно взять HHHHH и c нее составить L=1, что не ок. 
[1, 1, 1] = true 
...

Вот вам и красный тест

    @Test
    public void test2() {
        NO(1, HHHHH); 
    }

Главная фишка аппрувалса - пусть каждый делает то, что ему свойственно: комп пусть считает комбинации, а человек пусть оценивает правильность результата. Решилось это как-то так

    public boolean makeBricks(int small, int big, int goal) {
        if (goal == 0) {
            return true;
        }
        if (small == 0) {
            return goal % 5 == 0 && goal / 5 <= big;
        }
        return small + big * 5 >= goal;
    }

И главное теперь тест написанный на аппрувалсе тоже стал говорить!
 Поехали дальше...

...
[0, 0, 2] = false // не хватает материала
[1, 0, 2] = false // не хватает материала
[2, 0, 2] = true  // тут и дальше все хватает
[3, 0, 2] = true 
[4, 0, 2] = true 
[5, 0, 2] = true 
[6, 0, 2] = true 
[7, 0, 2] = true 
[8, 0, 2] = true 
[9, 0, 2] = true 
[10, 0, 2] = true 
[0, 1, 2] = false // снова не хватает материала
[1, 1, 2] = true  // а тут интересно! Опять пытаемся поделить пятерку чтобы сделать из нее что-то... Прошлый фикс не совершенен!
[2, 1, 2] = true 
[3, 1, 2] = true 
[4, 1, 2] = true  
...

Итого красный тест таков. Я сразу добавил однотипные кейсы, потому что чувствую мощь!

    @Test
    public void test3() {
        NO(1, HHHHH);
        NO(2, HHHHH, H);
        NO(3, HHHHH, H, H);
        NO(4, HHHHH, H, H, H);
    }

Получилось как-то так

    public boolean makeBricks(int small, int big, int goal) {
        if (goal == 0) {
            return true;
        }
        return (goal - small) / 5 <= big && (goal - small) % 5 == 0 || (goal - big*5) <= small && goal >= big*5;
    }

Не спрашивай как я пришел к этому. Просто как-то уивделось такое решение. Кроме того оно не оптимальное, так как я поломал старое (то что засек approvals но не засекли мои тестики) потому я решил добавить в свой набор тестов этот кейс.

    @Test
    public void test4() {
        YES(1, HHHHH, H, H);
    }

Этот тест проверяет, что у меня и больших и маленьких в избытке.

    public boolean makeBricks(int small, int big, int goal) {
        if (goal == 0) {
            return true;
        }
        return (goal - small) / 5 <= big && (goal - small) % 5 == 0 
                || (goal - big*5) <= small && goal >= big*5 
                || goal < small; // фикс простой как двери
    }

А как на счет этого теста?

    YES(6, HHHHH, HHHHH, H, H);

Потом мне приспичило в туалет. А возвращался я уже с этой идеей

    public boolean makeBricks(int small, int big, int goal) {
        return goal / 5 <= big && goal % 5 <= small;
    }

И как я до этого сразу не додумался? Но это еще не все. Просмотр таблицы результатов остановила меня возле теста

    YES(11, HHHHH, H, H, H, H, H, H);

Блин! Так все идеально было :) Решение вот

    public boolean makeBricks(int small, int big, int goal) {
        return goal / 5 <= (big + small / 5) && goal % 5 <= small % 5;
    }

Но тест (судя по изменениям - я уже не так просматриваю таблицу, как слежу за diff)
 Напишем такой тестик

    YES(1, H, H, H, H, H);

Нате! Родил

    public boolean makeBricks(int small, int big, int goal) {
        return goal / 5 <= (big + small / 5) && goal % 5 <= ((((goal / 5 - big - small / 5) == 0) && (small / 5 != 0)) ? (small % 5) : small);
    }

Ну и задачка :) Я че сюда полез, потому что мне сказали что ее можно решить без циклов :) Я не нашел проблем в approvals тесте - обратился к codingbat.com и там тоже получил аппрув
 Теперь осталось заапрувить все в аппрувалс тесте и провести рефакторинг....

      public boolean makeBricks(int small, int big, int goal) {
        int needBig = goal / 5;
        int needSmall = goal % 5;
        int smallAsBig = small / 5;
        int smallWithoutBigGroups = small % 5;
        int stillNeedBig = needBig - big - smallAsBig;

        boolean usedSmallAsBig = stillNeedBig == 0 && smallAsBig != 0;

        boolean enoughSmall = needSmall <= (usedSmallAsBig ? smallWithoutBigGroups : small);
        boolean enoughBig = stillNeedBig <= 0;

        return enoughBig && enoughSmall;
    }

Как-то так...

Но если посмотреть на решение, которое предлагает сам автор, становится понятно, что изначально выбрали не тот путь...

Попробуем проанализировать. Если в моем способе решения задачи я цеплялся за самый простой кейс, то в подходе предложенным Автором стоило бы первым фиксом отсечь как можно большее количество вариантов, а потом повторить то же с остатком. Интересно...