Задача с перестановкой спичек?

Question

[be52]

Надо написать функцию которая проверяет могло ли быть получено новое число из старого перестановкой 2ух спичек.

Comments

[Александр Нестеров]

Надо написать функцию

Ну так напишите, в чем проблема?

[Lapita12]

def can_rearrange(old_num, new_num):
    old_str = str(old_num)
    new_str = str(new_num)
    if len(old_str) != len(new_str):
        return False
    diff_count = 0
    for i in range(len(old_str)):
        if old_str[i] != new_str[i]:
            diff_count += 1
    if diff_count != 2:
        return False
    return True

[Максим Припадчев]

В каком институте такое задают?

[be52]

Lapita12, print(can_rearrange(1576, 876)) -> False

[Lapita12]

be52, Что вы хотите этим сказать?

[be52]

Lapita12, что эта функция работает неправильно. если взять 2 спички из первой цифры и переставить во вторую то получится цифра 8 и в итоге получится 876. из 1576 можно получить цифру 876 переставив 2 спички. функция должна вернуть True

[Lapita12]

be52,

def can_rearrange(old_num, new_num):
    # Словарь с количеством спичек для каждой цифры
    matches = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 6}
    
    old_str = str(old_num)
    new_str = str(new_num)
    
    # Вычисляем разницу в количестве спичек между старым и новым числами
    diff = sum(matches[c] for c in old_str) - sum(matches[c] for c in new_str)
    
    # Проверяем, равна ли разница двум
    return diff == 2 or diff == -2

[be52]

Lapita12, print(can_rearrange(1576, 876)) -> False
я так понимаю ты пытаешься сжечь цепи у GPTChat? код выглядит очень похожим на тот что выдавал бинг бот перед смертью

[Lapita12]

be52, Хахахах, да мой тоже кстати умер

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

[Модератор]

На вопрос «как сделать» отвечает документация и поиск в интернет.

Тут отвечают на вопросы «почему я сделал, как в документации, а оно не работает. Поискал в интернет, вот запросы, в ответах не нашел. Что я делаю не так?»

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

Answer 1

[Vindicar]

Шаг 1. Опиши каждую цифру числа как бинарную строку, где каждому биту соответствует спичка в цифре. 1 - спичка есть, 0 - нет. Тебе понадобится 7 бит на цифру, можно округлить до 8 и считать 8й бит всегда 0. Это, по сути, семисегментный индикатор.
Шаг 2. Научись преобразовывать число из нескольких цифр в длинную бинарную строку. Если гарантируется, что число 4значное или меньше, то эта строка будет выражена как 4 байтовое беззнаковое целое.
Шаг 3. Если сделать XOR между двумя такими строками, то значение 1 примут только биты, соответствующие пропавшим/появившимся спичкам. Посчитать число единичных бит нетрудно.
Шаг 4. Перебирай числа по возрастанию, для очередного числа построй битовую строку. Если число единичных бит в строках равно (для их "записи" используется равное число спичек), а число единичных бит в XOR равно четырём (две спички переложили = две спички пропали + две появились), число подходит.

За скорость, правда, не ручаюсь. Но есть возможности по оптимизации подсчёта единичных бит, и по оптимизации перебора (перебирать не все числа, а только те, которые можно выразить тем же числом спичек).

Comments

[CBET_TbMbI]

Не всё так просто. В таких задачах часто есть подвохи.
Например, в данном примере, переложив 2 спички из единицы, можно получить "-976". И это только вариант сходу. Может и ещё что-то похитрее есть.

Как минимум на шаге 1 надо ещё уметь распознавать хотя бы основные математические знаки.

А так да: надо тупым перебором рассмотреть все возможные перестановки любых пар спичек. Из всех вариантов оставить только имеющие смысл (дающие цифры и знаки, а не абракадабру).

Если стоит речь об оптимизации, то можно сначала руками выписать то, что имеет смысл переставлять. Например, если разрешена перестановки одной, то из 5 можно забрать только одну спичку и то, только для превращения её в 3. А подставлять одну можно в любой из 2 мест. Если разрешено переставлять 2, то там вариантов уже намного больше. Честно говоря, замучаешься описывать все варианты заранее.

[be52]

CBET_TbMbI, вариантов всего 10000. минус пока не интересует. вариант с битовыми строками выглядит интересно. но перерисовывать цифры так противоествественно и неудобно...

[Vindicar]

be52, один раз сделай lookup таблицу, и всё.

[be52]

Vindicar, для этого приходится сидеть и рисовать Ж)

[Alexandroppolus]

мерзкая единица вообще разваливает всякую позиционность.

было 1576, стало 5761
тут, кажется, много битов поменяется в строке, если сравнивать.

или, например, из 5712 сделали 872

[Vindicar]

Alexandroppolus, ну вот это уже интересно. Смена позиции цифры в числе считается перекладыванием спичек или нет?
Если считается, то это можно забороть, добавив по пустому знакоместу до и после числа.

[be52]

вроде всё получилось

def can_rearrange(old_num, new_num):
  numbs = {"0":"01111110", "1":"00110000", "2":"01101101", "3":"01111001", "4":"00110011",
           "5":"01011011", "6":"01011111", "7":"01110000", "8":"01111111", "9":"01111011",
           " ":"00000000"
    }
  a = "".join([numbs[x] for x in old_num])
  b = "".join([numbs[x] for x in new_num])
  
  c = "".join([str(int(a[x]) ^ int(b[x])) for x in range(len(a))])

    
  return c.count("1") == 4
 
  
    
print(can_rearrange("1576", " 876")) #true
print(can_rearrange("1576", " 875")) #false
print(can_rearrange("1576", "1518")) #false
print(can_rearrange("1576", "1815")) #true

[Akina]

А чё везде 876-то? очевидно же, что решение, то есть минимальное число - 536...

[Vindicar]

Akina, а не написано, что отрицательные числа могут быть. =р

[be52]

Akina, картинка просто для иллюстрации. нужна функция, способ, для определения что новое число получено из старого путем перестановки 2 спичек