Как сильно я могу раздавить мой массив?

30

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

[5,2,2,3]
 ^
[5,2,2,3]
   ^
[5,2,2,3]
     ^
[5,4,3]
   ^
[5,4,3]
     ^

Один и тот же элемент может быть свернут несколько раз, например [1,1,2]становится [4]при раздавливании.

Мы назовем массив нерушимым, когда процесс его уничтожения не изменится. Например [1,2,3], все еще [1,2,3]после того, как раздавлен.

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

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

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

[1] -> 0
[1,1] -> 1
[2,1,1] -> 2
[4,2,1,1] -> 3
[2,2,2,1,1] -> 3
[0,0,0,0] -> 1
[4,0,0,0,4] -> 1
[4,0,0,0,0,4] -> 1
[] -> 0
code-golf array-manipulation Мастер пшеницы
источник
5
Должен [1,1,2,4,8]вернуть 1 или 4?
MooseBoys
2
@ThePirateBay Хорошо, я понизлю это. Но для протокола я думаю, что Javascript довольно тупой в том, как он обрабатывает целые.
Пшеничный волшебник
2
Если бы вы попытались сокрушить [1 1 1 2], вы бы получили [2 1 2], если бы вы следовали спецификации точно так, как написано, но вы могли бы получить [1 4], если бы вы делали это более разумно. Что должно привести к [1 1 1 2]?
latias1290
4
@ latias1290. «В раздавленном состоянии мы читаем массив слева направо».
11
Может быть, это только я, но мне потребовалась секунда, чтобы понять, почему 0,0,0,0только 1. Это может быть идея явно упомянуть где-то, что мы подсчитываем количество раз, которое мы должны циклически проходить по массиву, чтобы полностью его раздавить, а не , как я изначально думал, общее количество раз, когда мы раздавливаем 2 числа вместе.
Лохматый

Ответы:

12

сборка x86 (64-битная), 66 65 байт

31 c0 57 59 56 51 56 5f 4d 31 c0 48 83 c6 08 48
83 e9 01 76 1b fc f2 48 a7 75 15 48 d1 67 f8 51
56 57 f3 48 a5 5f 5e 59 fd 48 a7 49 ff c0 eb e5
59 5e 4c 29 c1 48 ff c2 4d 85 c0 75 c7 48 ff c8
c3

Строковые инструкции были полезны. Необходимость исправления отдельных ошибок в 64-разрядной среде не была.

Полностью комментируемый исходный код:

.globl crush
crush:
/* return value */
xor %eax, %eax
/* save our length in rcx */
push %rdi
pop %rcx
pass:
/* save the start of the string and the length */
push %rsi
push %rcx
/* this is the loop */
/* first copy source to dest */
push %rsi
pop %rdi
/* and zero a variable to record the number of squashes we make this pass */
xor %r8, %r8
/* increment source, and decrement ecx */
add $8,%rsi
sub $1,%rcx
/* if ecx is zero or -1, we're done (we can't depend on the code to take care of this
automatically since dec will leave the zero flag set and cmpsq won't change it) */
jbe endpass
compare:
/* make sure we're going forward */
cld
/* compare our two values until we find two that are the same */
repne cmpsq
/* if we reach here, we either found the end of the string, or
we found two values that are the same. check the zero flag to
find out which */
jne endpass
/* okay, so we found two values that are the same. what we need
to do is double the previous value of the destination, and then
shift everything leftwards once */
shlq $1, -8(%rdi)
/* easiest way to shift leftwards is rep movsq, especially since
our ecx is already right. we just need to save it and the rsi/rdi */
push %rcx
push %rsi
push %rdi
rep movsq
pop %rdi
pop %rsi
pop %rcx
/* problem: edi and esi are now one farther than they should be,
since we can squash this dest with a different source. consequently
we need to put them back where they were. */
std
cmpsq
/* we don't need to put ecx back since the list is now one shorter
than it was. */
/* finally, mark that we made a squash */
inc %r8
/* okay, once we've reached this point, we should have:
 edi and esi: next two values to compare
 ecx: number of comparisons left
so we just jump back to our comparison operation */
jmp compare
endpass:
/* we reached the end of the string. retrieve our old ecx and esi */
pop %rcx
pop %rsi
/* rsi is accurate, but rcx is not. we need to subtract the number of squashes
that we made this pass. */
sub %r8, %rcx
/* record that we performed a pass */
inc %rax
/* if we did make any squashes, we need to perform another pass */
test %r8, %r8
jnz pass
/* we reached the end; we've made as many passes as we can.
decrement our pass counter since we counted one too many */
dec %rax
/* and finally return it */
ret

Я могу попробовать сделать это в 32-битной версии, хотя бы для развлечения, так как эти префиксы REX действительно убили меня.

Редактировать: сбрил один байт, заменив lodsq на add,% rdx на% rax и свернув два cld в один.

ObsequiousNewt
источник
9

Pyth , 22 байта

tl.uu?&GqeGH+PGyH+GHN[

Проверьте все тестовые случаи.

Дрянная Монахиня
источник
Jeebus! Вы сначала используете транспортер, а затем редактируете его вручную, или вы действительно пишете Pyth с самого начала?
oligofren
2
@oligofren последний.
Утренняя монахиня
6

Haskell , 66 байт

f(a:b:x)|a==b=f$a+a:x|1>0=a:f(b:x)
f x=x
g x|f x==x=0|1>0=1+g(f x)

Попробуйте онлайн!

объяснение

fэто функция, которая разбивает список Он выполняет раздавить, как описано в вопросе. gэто функция, которая считает количество давлений Если f x==x, в g x=0противном случае g x=1+g(f x).

Мастер пшеницы
источник
1
Сбрить байт, изменив g(f x)наg$f x
ApproachingDarknessFish
3
@ApproachingDarknessFish Это не работает, потому что +имеет более высокий приоритет, чем$
Wheat Wizard
Ах, мой плохой. Забавно, что я никогда не сталкивался с этой ошибкой раньше.
Приближается к
5

Paradoc (v0.2.10), 16 байт (CP-1252)

{—1\ε=k+x}]»}IL(

Попробуйте онлайн! / с верхним / нижним колонтитулом, который проверяет все контрольные примеры

Принимает список в стеке и приводит к числу в стеке.

Довольно простая реализация, если честно. Разбивает список, начиная с часового -1, просматривая список, нажимая на каждый элемент и добавляя его к элементу под ним, если они равны. В конце мы обрезаем -1. Мы только сжимаем равные числа вместе, и все числа задачи неотрицательны, так что часовой -1 не повлияет на процесс дробления. С реализованным дроблением, это всего лишь вопрос подсчета итераций до фиксированной точки.

Объяснение:

{            }I  .. Iterate this block: repeatedly apply it until a fixed
                 .. point is reached, and collect all intermediate results
 —1              ..   Push -1 (note that that's an em dash)
   \             ..   Swap it under the current list of numbers
    ε    }       ..   Execute this block for each element in the list:
     =           ..     Check if it's equal to the next element on the stack...
      k          ..       ... while keeping (i.e. not popping either of) them
       +         ..     Add the top two elements of the stack...
        x        ..       ... that many times (so, do add them if they were
                 ..       equal, and don't add them if they weren't)
          ]      ..   Collect all elements pushed inside the block that
                 ..     we're iterating into a list
           »     ..   Tail: take all but the first element (gets rid of the -1)
              L  .. Compute the length of the number of intermediate results
               ( .. Subtract 1

Если бы мы могли предположить, что входные данные были непустыми, нам не понадобился бы часовой и мы могли бы сбрить 2 байта: {(\ε=k+x}]}IL(

Еще один забавный факт: мы теряем только 2 байта, если заставляем себя использовать только ASCII: {1m\{=k+x}e]1>}IL(

betaveros
источник
4

JavaScript (ES6), 86 байт

f=a=>a.length>eval("for(i=0;a[i]>-1;)a[i]==a[++i]&&a.splice(--i,2,a[i]*2);i")?1+f(a):0

Неуправляемый и объясненный

f=a=>                           // function taking array a
    a.length > eval("           // if a.length > the result of the following...
        for(i=0; a[i]>-1;)      //   loop from 0 until the current value is undefined (which is not > -1)
            a[i] == a[++i] &&   //     if the current value equals the next one...
                a.splice(--i,   //       splice the array at the first index of the pair...
                    2,          //       by replacing 2 items...
                    a[i]*2);    //       with the current item * 2
                                //       this also decrements the counter, which means the current value is now the next
    i")                         //   return the counter, which is new a.length
        ? 1+f(a)                // if that was true, the array was crushed. add 1 and recur with the new array
        : 0                     // otherwise just return 0

тесты

Показать фрагмент кода

Джастин Маринер
источник
a.length>nтак же, как a[n]!=[]._. В этом случае (поскольку все элементы в массиве являются числами, большими чем -1), это то же самое, что и a[n]>-1. Кроме того, так a[i]==a[++i]&&xже, как a[i]-a[++i]||x.
Люк
Я думаю, что 1/a[i]также работает, чтобы сохранить еще один байт.
Нил
4

JavaScript, 67 байт

f=a=>a.map(a=>k[k[d-1]!=a?d++:(a*=z=2,d-1)]=a,k=d=[z=0])&&z&&f(k)+1

Попробуйте онлайн!


источник
Ницца! Я думал, что играл в гольф как можно ниже.
Рик Хичкок
3

Brain-Flak , 144 байта

([])({<{}>(<(([][()]){[{}]<({}[({})]<(())>){({}<{}>({})<>)((<>))}>{}{{}(<(({}){})>)}{}([][()])})>{()(<{}>)}{}{}<><([]){{}({}<>)<>([])}>{}<>)}<>)

Попробуйте онлайн!

объяснение

([])                                                                 Push stack height (starts main loop if list nonempty)
     {                                                       }       Do while the last iteration involved at least one crush:
      <{}>                                                           Remove crush indicator
           <(...)>                                                   Do a crush iteration
                  {()(<{}>)}                                         Evaluate to 1 if list was changed
                            {}{}                                     Remove zeroes
                                <>                        <>         On other stack:
                                  <([]){{}        ([])}>{}           Do while stack is nonempty:
                                          ({}<>)<>                   Move to first stack
          (                                                 )        Push 1 if crush worked, 0 otherwise
    (                                                         <>)    Push sum of results on other stack and implicitly print

Функция дробления оценивает количество пар предметов, которые были раздроблены вместе:

([][()]){[{}]                                                            ([][()])}    Do while stack height isn't 1:
              ({}[({})]      )                                                        Calculate difference between top two elements
                       <(())>                                                         Push a 1 below difference
                              {                    }                                  If difference was nonzero (don't crush this pair)
                               ({}    ({})<>)                                         Reconstruct top element and place on other stack
                                  <{}>       ((<>))                                   Push zeros to exit this conditional and skip next
             <                                      >{}                               Evaluate as zero
                                                       {              }{}             If difference was zero (crush this pair):
                                                        {}                            Evaluate as previously pushed 1
                                                          (<(({}){})>)                Double top of stack
Nitrodon
источник
3

Java 8, 120 байт

Лямбда из List<Long>в Integer. Входной список должен реализовывать remove(int)(например ArrayList). Присвоить Function<List<Long>, Integer>.

l->{int c=-1,i,f=1;for(;f>0;c++)for(f=i=0;++i<l.size();)if(l.get(i)-l.get(i-1)==0)l.set(i-=f=1,2*l.remove(i));return c;}

Попробуйте онлайн

Неуправляемая лямбда

l -> {
    int
        c = -1,
        i,
        f = 1
    ;
    for (; f > 0; c++)
        for (f = i = 0; ++i < l.size(); )
            if (l.get(i) - l.get(i - 1) == 0)
                l.set(i -= f = 1, 2 * l.remove(i));
    return c;
}

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

Подтверждения

  • Исправлено благодаря Оливье Грегуару: тест на равенство в штучной упаковке
Jakob
источник
Не работает, когда длинные не попадают в valueOfкеш. Пример: {128L, 128L}. Это из-за того l.get(i)==l.get(i-1), что следует заменить на l.get(i).equals(l.get(i-1)).
Оливье Грегуар
Ух ты, стыдно ... к счастью l.get(i)-l.get(i-1)==0сработает. Благодарность!
Якоб
2

JavaScript (ES6), 70 байт

f=(a,j=m=0,t=[])=>a.map(e=>t[e==t[j-1]?(e*=m=2,j-1):j++]=e)&&m&&1+f(t)

Объяснение:

f=(
  a,                  //the input
  j=m=0,              //j is the index into t; m starts out falsey
  t=[]                //t will hold the crushed array
)=>
  a.map(e=>           //for each element in the array
    t[e==t[j-1] ?     //if the element repeats:
      (e*=m=2,        //... multiply it by two, set m to truthy,
       j-1) :         //... and index the previous element of t.
      j++             //else append to t, and increment its index.
    ]=e               //set this index of t to the current value of e
  ) &&                //map is always truthy
  m &&                //if m is falsey, return 0
  1+f(t)              //else return 1 plus the recurse on t

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

Показать фрагмент кода

Рик Хичкок
источник
1
Хм ... Похоже, мы придумали почти такую ​​же идею :). После игры в гольф мой ответ, я понял, что он очень похож на ваш.
2

Python 2 , 112 110 108 107 105 100 байт

Редактировать: сохранено 2 байта путем удаления orв операторе возврата

Редактировать: сохранил 2 байта, имея iв качестве индекса второго из двух элементов, к которым осуществляется доступ

Редактировать: сохранено 1 байт благодаря @ Mr.Xcoder

Редактировать: 7 байтов сохранено благодаря @jferard

def f(x):
 i=e=1
 while x[i:]:
	if x[~-i]==x[i]:del x[i];i-=1;x[i]*=2;e=2
	i+=1
 return~-e and-~f(x)

Попробуйте онлайн!

Халвард Хаммель
источник
2

JavaScript (ES6), 83 байта

f=([x,y,...a],b=[],c)=>1/x?x==y?f([x+y,...a],b,1):f([y,...a],[...b,x],c):c?1+f(b):0

Объяснение: элементы рекурсивно извлекаются из исходного массива и к ним добавляются уникальные значения, в bто время cкак флаг указывает, был ли массив успешно разбит.

Нил
источник
1

J 54 байта

[:<:@#[:".@":@(,`(+:@[,}.@])@.({.@]=[))/^:a:@".@":_,|.

Попробуйте онлайн!

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

объяснение

crush =. ,`(+:@[ , }.@])@.({.@] = [)/
times =. <:@# [: ".@":@crush^:a:@".@": _ , |.

раздавить

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

,`(+:@[ , }.@])@.({.@] = [)/
                           /  Fold/reduce from the right
                  {.@] = [    Head of the running array equals the left argument?
   +:@[ ,                     If so, prepend double the argument to 
          }.@]                the array minus its head
,                             Else, prepend the left argument.

раз

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

Во-первых, когда дробление сводится к одному элементу, этот элемент фактически находится в списке из одного элемента (то есть он неатомарный), поэтому функция применяется снова, что приводит к перерасчету. Чтобы исправить это, я использовал хак, который придумал, чтобы уменьшить список из одного элемента до атома, который есть ".@":(преобразовать в строку, а затем вычислить).

Во-вторых, crushошибки в пустом списке. Я думаю, что вы можете определить, как должна вести себя функция при получении пустого ввода с помощью insert ( /), но я не смог ничего найти после беглого просмотра, поэтому я использую другой обходной путь. Этот обходной путь заключается в добавлении _(бесконечности) к списку, поскольку он никогда не повлияет на число раз, когда массив будет раздавлен ( _ > 2^64). Однако , это приводит в одном списке элементов , состоящий из _когда дается пустой список, так что нам нужно преобразовать к атому снова перед дроблением.

<:@# [: ".@":@crush^:a:@".@": _ , |.
                                  |.  Reverse input
                              _ ,     Prepend infinity
                        ".@":         Convert single-element list to atom
              crush                   Crush the list and after
        ".@":                         Convert single-element list to atom 
                   ^:a:               until it converges, storing each 
                                      iteration in an array
<:@#                                  Length of the resulting list minus 1
капуста
источник
0

R , 142 байта

f=function(l,r=l,k=0,T=1)"if"(sum(l|1)<2,k,{while(T<sum(r|1))"if"(r[T]-r[T+1],T<-T+1,{r<-r[-T]
r[T]<-2*r[T]})
"if"(all(r==l),k,f(r,r,k+1,1))})

Ужасно, я уверен, что есть более умный путь.

R целые числа на самом деле все самое большее 2^31-1.

Попробуйте онлайн!

Giuseppe
источник