Seam Carving

Seam Carving это способ поменять у картинки размеры, вырезая полоску пикселов с наименьшей значимостью.

https://goo.gl/8eebLi

И задали нам задачку, написать программу для этого дела

http://coursera.cs.princeton.edu/algs4/assignments/seamCarving.html

http://coursera.cs.princeton.edu/algs4/checklists/seamCarving.html

Это из курса

Algorithms, 4th Edition by Robert Sedgewick

Дело нехитрое, когда знаешь – как. Сел, написал. Отдаю на проверку.

А, кстати, проверяльщик автоматический у них довольно мощный, порядка сотни тестов да с разными комбинациями параметров. Но, ЧСХ для этого курса, студням код тестов недоступен, и это печалит неимоверно.

Проверил: два теста провалено, это около 2% итоговой оценки. С одной стороны хорошо: с первой попытки я изобразил корректную программу, тест фейлится на вспомогательном коде, где надо вернуть mutable картинку. То есть, по идее, я отдаю картинку и клиент может делать с ней что хочет, откуда следует, что отдавать я должен копию. Авотхуй.

Я, сцуко, три часа потратил на то, чтобы угадать, что этим блядским двум тестам надо.

Test 10a: Check that client can mutate the Picture object that is passed to the constructor
==> passed
Test 10b: Check that client can mutate the Picture object that is returned by picture()
==> passed

Два самых интересных варианта непрохождения тестов

Test 10a: Check that client can mutate the Picture object that is passed to the constructor
==> passed
Test 10b: Check that client can mutate the Picture object that is returned by picture()
     - repeated calls to picture() return reference to same Picture object
==> FAILED

Test 10a: Check that client can mutate the Picture object that is passed to the constructor
     - picture() return a Picture object that is not equal to argument Picture object
       even though no seams have been removed
==> FAILED
Test 10b: Check that client can mutate the Picture object that is returned by picture()
==> passed

Фактически, два взаимоисключающих условия: 1-- надо отдавать копию; 2-- не надо делать копию, если картинка не ресайзилась.

Сразу скажу, тесты проверяют не совсем то, что написано в сообщениях об ошибках.

Методом тыка я выяснил, что тесты проверяют: 1-- ты работаешь с копией входных данных; 2-- если в отданной тобой картинке клиент поменял хоть один пиксель, надо делать новую копию.

В итоге, вместо очевидного решения с кешированием результата, получается вот такое говно (зато 100% балл)

    public Picture picture() {
        if (cache == null) {
            cache = new Picture(currPic);
            return cache;
        }
        if (cache.height() != height || cache.width() != width) {
            cache = new Picture(currPic);
            return cache;
        }
        for (int row = 0; row < height; row++) {
            for (int col = 0; col < width; col++) {
                if (currPic.get(col, row) != cache.get(col, row)) {
                    cache = new Picture(currPic);
                    return cache;
                }
            }
        }
        return cache;
    }

Ну что тут сказать: Принстон, Принстон … учился я в этом вашем Принстоне. Ничего особенного, там тоже говны имеются.

P.S.

Лично меня в такой ситуации раздражают две вещи:

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

– вот такие вот два теста – что они, блиат, проверяют? Что я умею работать с картинкой в попиксельном режиме? Тема задачи была: Shortest path in directed acyclic graph. Я уж не говорю о том, что мутабельность/иммутабельность проверяют не так (не сравнением адресов).

А в целом, вот в такие моменты начинаешь особо ценить функциональный подход (иммутабельные типы данных).

original post http://vasnake.blogspot.com/2016/04/seam-carving.html