morfizm (morfizm) wrote,
morfizm
morfizm

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

Полгода назад 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 вариантами и не различали бы, что легче и что тяжелее, мы не могли бы так резво отбрасывать варианты, и не смогли бы сконструировать решение, исходя из вот этой идеи с отсечением вариантов.

С этой точки зрения, приём, который применён, это спецификация: добавить в задачу больше требований, чтобы исходую задачу проще было решить. В данном случае добавлено требование понять, фальшивая монетка легче или тяжелее.
Tags: 1, math, software development
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 12 comments