?

Log in

No account? Create an account
   Journal    Friends    Archive    Profile    Memories
 

Очередная задачка на взвешивания монеток - morfizm


Jul. 27th, 2014 02:36 pm Очередная задачка на взвешивания монеток

Полгода назад goliafffff выложил задачку на взвешивание монеток.
Вот условие: "Среди 12 монет найти фальшивую за 3 взвешивания на весах-чашках. Легче или тяжелее монетка - не известно."

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

Решение в общих чертах:
Жадный алгоритм даёт рашение за 3 взвешивания, причём ещё и определяет, какого именно типа фальшивая монетка (легче или тяжелее). Сортируем все потенциальные варианты (24), сортируем все возможные разбиения для взвешивания, выбираем лексикографически первое разбиение, которое в наибольшей степени уменьшит число потенциальных вариантов в худшем случае по всем трём исходам взвешивания (=, <, >), и т.п. рекурсивно.



Код, CoinWeighting.py
import itertools

N = 12

def gen_all():
    normal = [0]*N
    for i in range(N):
        lighter_i = list(normal)
        lighter_i[i] = -1
        yield lighter_i
        heavier_i = list(normal)
        heavier_i[i] = +1
        yield heavier_i

def get_all_splits():
    maxK = N//2
    first = [set(x) for x in itertools.chain.from_iterable(itertools.combinations(range(N), K) for K in range(1, 1+maxK))]
    pairs = []
    for f in first:
        K = len(f)
        minI = min(f)+1
        select_second = [i for i in range(N) if (not i in f) and (i > minI)]
        pairs.extend((f, set(x)) for x in itertools.combinations(select_second, K))
    return pairs

def get_satisfies(variants, weightings):
    satisfactory = []
    for v in variants:
        good = True
        for (first, second, outcome) in weightings:
            first_weight = sum(v[i] for i in first)
            second_weight = sum(v[i] for i in second)
            if ((outcome == 0) and (first_weight != second_weight)
                    or (outcome > 0) and (first_weight <= second_weight)
                    or (outcome < 0) and (first_weight >= second_weight)):
                good = False
                break                    
        if good:
            satisfactory.append(v)
    return satisfactory

def num_satisfies(variants, weightings):
    return len(get_satisfies(variants, weightings))

def get_potential(variants, weightings, first, second):
    return max([
        num_satisfies(variants, weightings + [(first, second, 0)]),
        num_satisfies(variants, weightings + [(first, second, -1)]),
        num_satisfies(variants, weightings + [(first, second, +1)]),
        ])

def get_best_split(variants, weightings):
    splits = get_all_splits()
    best_first = None
    best_second = None
    best_potential = len(variants)+1
    for first, second in splits:
        cur_potential = get_potential(variants, weightings, first, second)
        if cur_potential < best_potential:
            best_potential = cur_potential
            best_first = first
            best_second = second
    return (best_first, best_second, best_potential)
            
def get_index_value(variant):
    try:
        pos = variant.index(1)
    except: 
        pos = variant.index(-1)
    return pos, variant[pos]

def explore(indent, variants, weightings):
    #print 'len(variants) = ', len(variants)
    #if len(variants)<=4: print variants
    print '# %sNum possible variants: %d' % (' '*indent, len(variants))
    if len(variants) == 0:
        print '# %sThis cannot happen' % (' '*indent)
    elif len(variants) == 1:
        index, value = get_index_value(variants[0])
        print '# %s Answer: %d at position #%d' % (' '*indent, value, index)
    else:
        (best_first, best_second, best_potential) = get_best_split(variants, weightings)
        print '# %s%s' % (' '*indent, str((sorted(best_first), sorted(best_second), best_potential)))
        print '# %s=' % (' '*indent)
        new_weightings = weightings + [(best_first, best_second, 0)]
        explore(indent + 4, get_satisfies(variants, new_weightings), new_weightings)
        print '# %s<' % (' '*indent)
        new_weightings = weightings + [(best_first, best_second, -1)]
        explore(indent + 4, get_satisfies(variants, new_weightings), new_weightings)
        print '# %s>' % (' '*indent)
        new_weightings = weightings + [(best_first, best_second, 1)]
        explore(indent + 4, get_satisfies(variants, new_weightings), new_weightings)

explore(0, list(gen_all()), [])



Результат, CoinWeighting.txt
# Num possible variants: 24
# ([0, 1, 2, 3], [4, 5, 6, 7], 8)
# =
#     Num possible variants: 8
#     ([0, 8], [9, 10], 3)
#     =
#         Num possible variants: 2
#         ([0], [11], 1)
#         =
#             Num possible variants: 0
#             This cannot happen
#         <
#             Num possible variants: 1
#              Answer: 1 at position #11
#         >
#             Num possible variants: 1
#              Answer: -1 at position #11
#     <
#         Num possible variants: 3
#         ([0, 1], [8, 9], 1)
#         =
#             Num possible variants: 1
#              Answer: 1 at position #10
#         <
#             Num possible variants: 1
#              Answer: 1 at position #9
#         >
#             Num possible variants: 1
#              Answer: -1 at position #8
#     >
#         Num possible variants: 3
#         ([0, 1], [8, 9], 1)
#         =
#             Num possible variants: 1
#              Answer: -1 at position #10
#         <
#             Num possible variants: 1
#              Answer: 1 at position #8
#         >
#             Num possible variants: 1
#              Answer: -1 at position #9
# <
#     Num possible variants: 8
#     ([0, 1, 4], [2, 3, 5], 3)
#     =
#         Num possible variants: 2
#         ([0], [6], 1)
#         =
#             Num possible variants: 1
#              Answer: 1 at position #7
#         <
#             Num possible variants: 1
#              Answer: 1 at position #6
#         >
#             Num possible variants: 0
#             This cannot happen
#     <
#         Num possible variants: 3
#         ([0, 5], [2, 3], 1)
#         =
#             Num possible variants: 1
#              Answer: -1 at position #1
#         <
#             Num possible variants: 1
#              Answer: -1 at position #0
#         >
#             Num possible variants: 1
#              Answer: 1 at position #5
#     >
#         Num possible variants: 3
#         ([0, 1], [2, 4], 1)
#         =
#             Num possible variants: 1
#              Answer: -1 at position #3
#         <
#             Num possible variants: 1
#              Answer: 1 at position #4
#         >
#             Num possible variants: 1
#              Answer: -1 at position #2
# >
#     Num possible variants: 8
#     ([0, 1, 4], [2, 3, 5], 3)
#     =
#         Num possible variants: 2
#         ([0], [6], 1)
#         =
#             Num possible variants: 1
#              Answer: -1 at position #7
#         <
#             Num possible variants: 0
#             This cannot happen
#         >
#             Num possible variants: 1
#              Answer: -1 at position #6
#     <
#         Num possible variants: 3
#         ([0, 1], [2, 4], 1)
#         =
#             Num possible variants: 1
#              Answer: 1 at position #3
#         <
#             Num possible variants: 1
#              Answer: 1 at position #2
#         >
#             Num possible variants: 1
#              Answer: -1 at position #4
#     >
#         Num possible variants: 3
#         ([0, 5], [2, 3], 1)
#         =
#             Num possible variants: 1
#              Answer: 1 at position #1
#         <
#             Num possible variants: 1
#              Answer: -1 at position #5
#         >
#             Num possible variants: 1
#              Answer: 1 at position #0

(Syntax highligher used: http://tohtml.com/python/)


Комментарии к решению

Третье число во взвешивании означает "хорошесть", выражающуюся в максимальном количество вариантов, оставшихся после отсечения, по всем трём исходам. Нужно использовать шрифт фиксированной ширины (напр courier new)

Несколько идей:

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

2. Можно "откладывать" монетки. Напр., разобъём на 3 кучки по 4, взвесим первые две, если левая меньше правой, то третью кучу уже сразу можно "отложить" как эталонные монеты, гарантированно не фальшивые, и они могут *пригодиться* в будущем.

В решении, сгенерированном моей программкой, конкретно эти монетки не пригождаются, но пригождаются отложенные после второго взвешивания на третьем, именно в качестве эталона:
напр., если [0, 1, 2, 3] < [4, 5, 6, 7], следующее взвешивание будет [0, 1, 4] (две монетки слева и одну справа) и [2, 3, 5] (другие две слева и ещё одну справа). Если эти две группы оказались равны, это сразу гарантирует, что все монеты между собой не фальшивы, т.е. не фальшивы [0, 1, 2, 3, 4, 5] (ну и также отложенные ранее [8, 9, 10, 11]). Остались только [6, 7]. Но! Программа не предлагает их взвешивать между собой (хотя так тоже можно было), она предлагает взвесить [6] с эталоном [0]. Это сразу даёт ответы на все вопросы, т.к. если [6] == [0], [7] автоматически будет не только фальшивой монеткой, а ещё и, известно что, более тяжёлой (из-за первого взвешивания).

Основной принип, по которому я строил алгоритм, это выбирать "наилучшие" взвешивания, где "хорошесть" определяется тем, настолько много вариантов отсекаются. Скажем, вначале вариантов у нас 24 (фальшивая монетка может быть на любой позиции, от 0 до 11, причём она может быть тяжелее или легче других - т.е. по 2 варианта на позицию).
Если мы взвесим [0, 1, 2, 3] и [4, 5, 6, 7], у нас есть три исхода:
1) когда равны, фальшивая монетка в [8, 9, 10, 11], но не известно, она легче или тяжелее, т.е. осталось 8 вариантов.
2) когда слева легче, есть два под-варианта: либо фальшивая монетка слева (одна из 4), и известно, что она легче, либо фальшивая монетка справа (тоже одна из 4), но известно, что она тяжелее. Суммарное количество варианто будет тоже 8 (4+4).
3) аналогично, когда слева тяжелее.
Итого, у нас во всех случаях остаётся по 8 вариантов, т.е. даже в самом худшем случае число вариантов сократится с 24 до 8. Уменьшение вариантов в 3 раза это наилучший исход для взвешивания, мы используем максимум информации (т.к. взвешивание имеет 3 исхода, т.е. даёт ровно точь в точь необходимую информацию, чтобы уменьшить число вариантов втрое).

Если же мы взвесим первым взвешиванием, например, [0] и [1], то когда они неравны, останется по 2 варианта, а когда они равны, останется 20 (10*2). Получается, худший случай это уменьшение с 24 до 20, что есть довольно таки расточительно. Кстати, как только после первого взвешивания получилось больше 9 вариантов, уже можно доказать, что двумя взвешиваниями не обойтись*, чтобы завершить (два взвешивания дают 9 вариантов исхода, 3*3, и это информация, которой хватит, чтобы выбрать 1 из 9. В случае более, чем 9 вариантов, будут по крайней мере два, которых информация, полученная после двух взвешиваний, не сможет отличить - понадобится третье взвешивание).

Аналогичные размышления: после двух взвешиваний должно оставаться не более 3 вариантов, иначе одного взвешивания не хватит, чтобы завершить. Это размышление может помочь отбросить неэффективные взвешивания на этапе перебора.

Понятно, что мой алгоритм не идеален, т.к. я на каждом шаге выбираю строго "локальный максимум" (отсюда и название "жадный алгоритм"), а не перебираю разные возможности, но в данном случае, так уж повезло, что жадный алгоритм дал оптимальное решение. Так частенько бывает. "Вручную" надо всегда пробовать сначала жадным алгоритмом, а потом уже пробовать перебирать "умнее", если жадным не получается.

Дополнение к (*):
Это правда, только если мы исходим из того, что изначальных вариантов 24, т.е. нам важно, фальшивая монетка легче или тяжелее.

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

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

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

12 comments - Leave a commentPrevious Entry Share Next Entry

Comments:

From:archaicos
Date:July 27th, 2014 09:50 pm (UTC)
(Link)
Классическая мозгоёбская задача, коих масса, но которые на практике встречаются достаточно редко, если только ты не участвуешь во всяких олимпиадах или соревнованиях по мозгоебическому программированию.
From:morfizm
Date:July 27th, 2014 10:08 pm (UTC)
(Link)
Надо и мозги ебать, и тело. Я люблю секс во всех его проявлениях.
From:archaicos
Date:July 27th, 2014 10:11 pm (UTC)
(Link)
Но тут ты отказался от мозгоёбства и решил ебать перебором процессор. :)
From:morfizm
Date:July 28th, 2014 12:18 am (UTC)
(Link)
Ну, я чуть-чуть трахнул мозг, попробовав решить в уме, потом ещё чуть-чуть трахнул мозг, написав перебор, а дальше уже ебать перебором процессор - святое дело :) Процессору ж тоже нужен секс :)
From:andreyvo
Date:July 28th, 2014 11:31 am (UTC)
(Link)
Лето, жара, потные солдаты-танкисты чинят танк - гусеницу слетевшую натягивают. Тут мимо пролетает фея. Вся такая сексуальная в неглиже.
- Что, мальчики, ебётесь?
- Ага...
- А хотите по-настоящему?
- Ага!!!!
Фея взмахивает волшебной палочкой, и у танка отваливается башня.
From:morfizm
Date:July 28th, 2014 05:22 pm (UTC)
(Link)
:)
From:metaller
Date:July 28th, 2014 01:40 am (UTC)
(Link)
+1
From:raindog_2
Date:July 27th, 2014 09:52 pm (UTC)
(Link)
А почему только 12 монет? Если не требуется определить, легче фальшивая монетка или тяжелее, то можно и для 13 решить, если не ошибаюсь.
From:morfizm
Date:July 27th, 2014 09:53 pm (UTC)
(Link)
Интересный вариант, надо будет подумать.
From:morfizm
Date:July 27th, 2014 09:53 pm (UTC)
(Link)
И, кстати, боюсь, для такой задачки уже перебор нужно будет делать поинтереснее.
From:outputlogic
Date:November 26th, 2014 10:45 pm (UTC)
(Link)
Пытаюсь разобраться с вашим решением, ну и просто интересно покопаться в питоновском коде.
Начну с вопроса откуда взялось 24 потенциальных варианта.
Ведь в жадном алгоритме всё возможно, например в последующих взвешиваниях могут использоваться разные монетки.
Или это то что нашла программа.
From:morfizm
Date:November 27th, 2014 01:30 am (UTC)
(Link)
Читайте внимательно комментарии под катом, там объясняется.

"Скажем, вначале вариантов у нас 24 (фальшивая монетка может быть на любой позиции, от 0 до 11, причём она может быть тяжелее или легче других - т.е. по 2 варианта на позицию)."

Это варианты расположения фальшивой монетки, а не варианты разбиений для взвешиваний.