Facebook puzzles - do they work?

[crypto5]

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

Понимаете, в чем дело. Во-первых, задача паззлов - решить паззл эффективно, а не сделать программу простой. Во-вторых, нагенерить конечные состояния - не очень сложно, когда знаешь, что в каждом состоянии должен быть минимум один сосуд, который либо до краев, либо пуст. И, наконец, в третьих и в самых главных - "то же самое" не получится. Перебор будет значительно проще. Почему вам это не очевидно, я не знаю.

Пора таки попросить показать "великий код"!

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

А вы меня интервьюировали? Извините не заметил, сейчас быстр побегу все переписывать с конца и оптимально!

[crypto5]

На самом деле там есть одно важное место для оптимизации: в текущей программе я копирую полностью path при каждом вызове функции, этого можно избежать, но я поленился.

А вот это как раз пофигу. Понятно, что можно там чуть улучшить или здесь, нет никакого смысла до этого докапываться и лень тут уместна. А вот неэффективный алгоритм... ну, скажем, я такие на интервью когда пишу от отсутствия лучших идей, сразу оговариваюсь, что это the most obvious and str8forward approach, there must be something better

Я пока что не вижу никаких причин считать что это неэффективный алгоритм.

[АццкоМото]

Пора таки попросить показать "великий код"!

Просите, чо. Пока что я знаю, как сделать лучше, а у вас есть код плохого решения. Меня устраивает status quo

А вы меня интервьюировали? Извините не заметил, сейчас быстр побегу все переписывать с конца и оптимально!

Не надо только передергивать. Не я вас просил выложить "великий код". И уж тем более не я заставил вас под видом "великого кода" выставлять тривиальное, неинтересное и неэффективное решение

[crypto5]

На самом деле там есть одно важное место для оптимизации: в текущей программе я копирую полностью path при каждом вызове функции, этого можно избежать, но я поленился.

А вот это как раз пофигу. Понятно, что можно там чуть улучшить или здесь, нет никакого смысла до этого докапываться и лень тут уместна. А вот неэффективный алгоритм... ну, скажем, я такие на интервью когда пишу от отсутствия лучших идей, сразу оговариваюсь, что это the most obvious and str8forward approach, there must be something better

Я пока что не вижу никаких причин считать что это неэффективный алгоритм.

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

[АццкоМото]

Я пока что не вижу никаких причин считать что это неэффективный алгоритм.

Ну началось... ну возьмите ручку, бумажку и нарисуйте дерево перебора на 5 шагов в глубину для перебора вашим алгоритмом и, назовем его так: алгоритмом Reds. Т.е. перебором "с конца"
Я не знаю как разжевать. Если вы это сделаете, все станет очевидно

[crypto5]

Я пока что не вижу никаких причин считать что это неэффективный алгоритм.

Ну началось... ну возьмите ручку, бумажку и нарисуйте дерево перебора на 5 шагов в глубину для перебора вашим алгоритмом и, назовем его так: алгоритмом Reds. Т.е. перебором "с конца"
Я не знаю как разжевать. Если вы это сделаете, все станет очевидно

У меня не получается.

[АццкоМото]

У меня не получается.

это шутка?

[crypto5]

Не надо только передергивать. Не я вас просил выложить "великий код". И уж тем более не я заставил вас под видом "великого кода" выставлять тривиальное, неинтересное и неэффективное решение

Я не передергиваю. Мне почему то кажется что Комисар меня тоже здесь интервьюировать не собирался.

[crypto5]

У меня не получается.

это шутка?

Та нет, для меня так и не стало очевидно что "с конца" как то оптимальнее.

[АццкоМото]

У меня не получается.

это шутка?

Та нет, для меня так и не стало очевидно что "с конца" как то оптимальнее.

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

[crypto5]

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

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

Кстати для абстрактных чисел это не факт.

[crypto5]

У меня не получается.

это шутка?

Та нет, для меня так и не стало очевидно что "с конца" как то оптимальнее.

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

Мне кажется это в общем случае не правда. Если у вас есть одно конечное состояние и одно начальное то задача может быть перевернута, и сводится к поиску кратчайшего пути на неориентированном графе где вершины - это состояния, и абсольютно все равно с какого конца решать. В данном конкретном случае с числами 5,8,12 и 6 возможно вы и правы.

[crypto5]

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

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

Кстати для абстрактных чисел это не факт.

Хотя, нет, вы правы, факт.

[АццкоМото]

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

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

Кстати для абстрактных чисел это не факт.

Что, простите, именно не факт для абстрактных чисел? На каждом шаге мы по определению из какого-то сосуда выливаем в другой либо всю воду, либо столько, сколько влезет. В первом случае мы получаем гарантированно пустой сосуд, во втором - полный до краев. Третьего не дано.

Если вам кажется, что для произвольных емкостей может быть трудно нагенерить все конечные состояния, то это тоже не верно. Нам нужно получить какое-то количество воды, отличное от емкости любого из сосудов. Максимум три варианта, где оно может получиться. Для каждого из них - либо в одном из двух сосудов пусто, а вся остальная вода в другом, либо в одном из сосудов - до краев. 12 вариантов по максимуму, часть из них отсеивается из-за невозможности

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

[valchkou]

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

Code: Select all

#Python
# Класс представляет сосуд
class Sosud():
    # это такой конструктор в питоне
    def __init__(self, capacity, contains):
        self.capacity = capacity
        self.contains = contains    
    
    # сколько еще можно залить
    def available(self):        
        return self.capacity - self.contains

    # можно ли залить вообще
    def canTake(self):        
        return self.capacity > self.contains

# запускаем переливалку
def main():    
    cnt = 0
    # инициализирую 3 сосуда
    s12 = Sosud(12, 12)
    s8 = Sosud(8, 0)
    s5 = Sosud(5, 0)
    lst = [s12, s8, s5]

    # буду переливать пока не увижу 6 литров
    while s12.contains != 6 or s8.contains != 6:            
        sFrom = choice(lst) # случайно выбираю сосуд откуда выливать
        sTo = choice(lst) # случайно выбираю сосуд куда заливать
        # если сосуды разные и места хватает, тогда льем
        if sFrom != sTo and sTo.canTake():                    
            cnt+=1   
            if sTo.available()>=sFrom.contains:              
                sTo.contains += sFrom.contains
                sFrom.contains = 0
            else:    
                sFrom.contains -= sTo.available()
                sTo.contains = sTo.capacity
    
    print cnt

[АццкоМото]

Хотя, нет, вы правы, факт.

Ну вот, а я уже всю клавиатуру истоптал

[crypto5]

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

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

Кстати для абстрактных чисел это не факт.

Что, простите, именно не факт для абстрактных чисел? На каждом шаге мы по определению из какого-то сосуда выливаем в другой либо всю воду, либо столько, сколько влезет. В первом случае мы получаем гарантированно пустой сосуд, во втором - полный до краев. Третьего не дано.

Да, здесь я согласен.

Если вам кажется, что для произвольных емкостей может быть трудно нагенерить все конечные состояния, то это тоже не верно. Нам нужно получить какое-то количество воды, отличное от емкости любого из сосудов. Максимум три варианта, где оно может получиться. Для каждого из них - либо в одном из двух сосудов пусто, а вся остальная вода в другом, либо в одном из сосудов - до краев. 12 вариантов по максимуму, часть из них отсеивается из-за невозможности

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

[АццкоМото]

Програмно задача решается проще, чем на живых сосудах

На живых сосудах задача вообще не решается: в этом сезоне приветовцы льют исключительно Джек Дениэлс, а 12+8+5 литров - это серьезно!
К тому же не масштабируемо: а если вдруг литры заметить на галлоны?

[АццкоМото]

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

Перебор - на то и перебор, чтобы были лишние ветви, хотя бы в теории. А по факту Reds решил за 3 минуты, а прямым перебором получилось только у тех, кто воду на пол выливал. Ну и вообще, если 10 минут на листике деревья переборов порисовать, все становится очевидным

[crypto5]

хужший сценарий пока что 70 тыс переливаний

Это потому что ваша программа имеет склонность к зацикливанию.

[valchkou]

хужший сценарий пока что 70 тыс переливаний

Это потому что ваша программа имеет склонность к зацикливанию.

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

[agrippina]

Видишь ли, народ обсуждал школы вокруг фейсбука.

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

Кровати оставить односпальными, но в период гона уплотнять их индусками.

А инженегры столько смогут выпить?

[Cabron]

А инженегры столько смогут выпить?

Если ежедневно будут решать задачу Пуассона со спиртом, то может вскоре и смогут.

[Zorkus]

ФБ старается нанимать умных, инициативных и продуктивных сотрудников. ...

читал стоя...

Если бы я хоть раз раз прочитал объявление вида:

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

Я бы тотчас позвонил им. Ну просто пообщаться с оригинальными людьми.

[fruit6]

ФБ старается нанимать умных, инициативных и продуктивных сотрудников. ...

читал стоя...

Если бы я хоть раз раз прочитал объявление вида:

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

Я бы тотчас позвонил им. Ну просто пообщаться с оригинальными людьми.

функция языка в современном мире свелась к одному: врать.