Решить головоломку

17

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

В этом вопросе мы будем рассматривать только целые числа, представленные в 7-сегментном формате отображения. Вот все 10 цифр в этом формате:

 __          __   __          __    __    __    __    __
|  |     |   __|  __|  |__|  |__   |__      |  |__|  |__|
|__|     |  |__   __|     |   __|  |__|     |  |__|   __|    

Каждый сегмент дисплея представляет собой одну «спичку», которую можно перемещать независимо от остальной части номера. Спички неразделимы и неразрушимы, их нельзя сломать или удалить никакими средствами.

Обычная головоломка - взять число, указанное в базе 10, и попытаться сделать наибольшее возможное число за данное количество ходов. Ход считается одним движением спички из любого занятого слота в любой другой незанятый слот. Вам вполне разрешено делать новые цифры по обе стороны от номера, например, 0 можно сделать из 77 за 3 хода

 __      __  __      __   __      __   __
|  |    |  |        |  |    |       |    |
|__| ,   __|     ,     |      ,     |    |

Однако вы не можете сделать один слот на 2 или создать новые слоты между существующими, например, превратить 4 в 11 в середине числа или вставить новые цифры между существующими. Каждое движение не должно составлять правильное число, но конечный результат должен быть правильным числом в основном 10-сегментном дисплее. Вам не нужно использовать каждый ход, если вы не хотите. В отличие от головоломок, это [тег: закрытый вопрос], вы не можете использовать какие-либо операторы (умножение, возведение в степень и т. Д.) Или математические константы (число Пи, число Грэма и т. Д.) В своих ответах.

задача

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

Это вопрос поэтому ответы будут оцениваться в байтах, причем меньше байтов будет лучше.

Тестовые случаи

n, moves -> max
0, 1     -> 9
0, 3     -> 77
0, 4     -> 111
8, 3     -> 74
220, 1   -> 320
220, 2   -> 520
220, 3   -> 7227
220, 4   -> 22111
220, 5   -> 32111
747, 1   -> 747
747, 2   -> 7171
747, 3   -> 7711

Связанный

Пост Рок Гарф Хантер
источник
5
Я ... на самом деле не спал прошлой ночью, размышляя о расстоянии Левенштейна между различными цифрами спичек ... Какое странное совпадение: P
ETHproductions
1
Могут ли пустые слоты, образованные в середине, игнорироваться в конце? Например919, 2 -> 991
DanTheMan
Мастер пшеницы, какая сетка используется?
Tuskiomi
@tuskiomi «Однако вы не можете сделать один слот на 2 или сделать новые слоты между существующими»
Post Rock

Ответы:

7

JavaScript (ES6), 297 286 279 267 байт

Принимает ввод в синтаксисе карри (s)(k), где s - массив цифровых символов, а k - количество ходов (целое число).

s=>k=>(B=(n,b=0)=>n?B(n^n&-n,b+1):b,b=[...p='u"[k,iy#}m'].map(c=>c.charCodeAt()+2),r=[],g=(n,d='')=>n?n>0&&b.map((v,i)=>g(n-B(v),d+i)):r.push(d))(s.reduce((s,c)=>s+B(b[c]),M=0))&&b.map((_,j)=>r.map(n=>M=[...n+p].reduce((t,d,i)=>t+B(b[d]^b[s[i-j]]),0)>k*2|+n<M?M:n))|M

Контрольные примеры


Как?

Данные формы и вспомогательная функция

  • Массив b описывает формы цифр как 7-битные целые числа, где каждый бит является сегментом:

    7-сегментный

    Например, форма "7" имеет вид 0b0100101 = 37.

  • Вспомогательная функция B () возвращает число единиц в двоичном представлении данного числа:

    B = (n, b = 0) => n ? B(n ^ n & -n, b + 1) : b

Шаг 1

Сначала мы посчитаем количество спичек, использованных во входном номере:

s.reduce((s, c) => s + B(b[c]), 0)

Шаг 2

Мы передаем это значение рекурсивной функции g () , которая заполняет список r всеми числами, которые могут быть построены именно с таким количеством спичек:

g = (n, d = '') =>
  n ?
    n > 0 &&
    b.map((v, i) => g(n - B(v), d + i))
  :
    r.push(d)

Например, g (5) загрузится [ '17', '2', '3', '5', '71' ]в r .

Шаг 3

Теперь нам нужно выбрать наибольшее число M в r, которое может быть фактически получено из входного числа, в пределах разрешенного количества ходов k .

Поскольку каждое число n в r использует столько же спичек, сколько и входное число s , количество ходов, необходимых для преобразования s в n, равно половине числа различий сегментов между каждой из их цифр.

Количество различий в сегментах между двумя цифрами x и y определяется числом единиц в двоичном представлении b [x] XOR b [y] .

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

Arnauld
источник
1

Математика, 188 197 200 203 170 174 байтов

ПРИМЕЧАНИЕ . Код по-прежнему содержит ошибки. Я работаю над этим.

+30 байт за ошибку

(p=PadLeft;q=IntegerDigits;g=Join@@(#~q~2~p~7&/@ToCharacterCode["w$]m.k{% o"][[1+q@#]])&;h=(v=g@#2~#~96-g@i~#~96;Tr@v==0&&Tr@Abs@v<=2#3)&;For[i=10^Tr@g@#,!h[p,##]&&!h[PadRight,##],--i];i)&

Символ между %и oдолжен быть, 0x7Fно SE не допустит этого. Вы можете нажать на ссылку для вставки оригинального кода.

Код занимает много времени, когда есть более 6-7 стиков. (Вы можете изменить начальное значение iна меньшее число, чтобы проверить его)

объяснение

gявляется вспомогательной функцией, преобразующей цифры в список представления флешки (согласно здесь ), например, {1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1}для 220.

h является вспомогательной функцией для работы с левым и правым отступом между двумя числами.

fвыполняет итерацию от 10^Tr@g@#(верхнего предела) до 1поиска целого числа, представление палки которого имеет такое же количество 1 -> 0и 0 -> 1по сравнению с исходным числом, а количество меньше или равно второму аргументу.

Кейу Ган
источник
Я дал вам +1, потому что я никогда не видел, чтобы победивший ответ имел такой низкий балл, чем другой ответ. Я предполагаю, что это потому, что это отсутствие вариантов онлайн-тестирования. Может быть, некоторые люди, у которых есть Mathematica, могли бы проверить его и убедиться, что он работает хорошо, чтобы вы могли получить еще больше голосов. Или, может быть, кто-то может преобразовать его в Octave, если это возможно.
геокавель