2048-like array shift

Question

Assume we want to shift an array like it is done in the 2048 game: if we have two equal consecutive elements in array, merge them into twice the value element. Shift must return a new array, where every pair of consecutive equal elements is replaced with their sum, and pairs should not intersect. Shifting is performed only once, so we don't need to merge resulting values again. Notice that if we have 3 consecutive equal elements, we have to sum rightmost ones, so for example, [2, 2, 2] should become [2, 4], not [4, 2].

The task is to write shortest function which takes an array and returns a shifted array.

You may assume that all integers will be strictly positive.

Examples:

[] -> []
[2, 2, 4, 4] -> [4, 8]
[2, 2, 2, 4, 4, 8] -> [2, 4, 8, 8]
[2, 2, 2, 2] -> [4, 4]
[4, 4, 2, 8, 8, 2] -> [8, 2, 16, 2]
[1024, 1024, 512, 512, 256, 256] -> [2048, 1024, 512]
[3, 3, 3, 1, 1, 7, 5, 5, 5, 5] -> [3, 6, 2, 7, 10, 10]

I am also very interested in solution using reduce :)

Answer 1

Jelly, 10 9 8 bytes

Œg+2/€UF

TryItOnline or run all test cases

How?

Œg+2/€UF - Main link: a                 e.g. [2,2,2,4,4,8]
Œg       - group runs of equal elements      [[2,2,2],[4,4],[8]]
   2/€   - pairwise reduce for each with
  +      -     addition                      [[4,2],[8],[8]]
      U  - reverse (vectorises)              [[2,4],[8],[8]]
       F - flatten list                      [2,4,8,8]

Answer 2

Haskell, 47 57 50 bytes

e#l|a:b<-l,e==a= -2*a:b|1<2=e:l
map abs.foldr(#)[]

Uses reduce (or fold as it is called in Haskell, here a right-fold foldr). Usage example: map abs.foldr(#)[] $ [2,2,2,4,4,8] -> [2,4,8,8].

Edit: +10 bytes to make it work for unsorted arrays, too. Merged numbers are inserted as negative values to prevent a second merge. They are corrected by a final map abs.

Answer 3

Brain-Flak, 158 96

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

Try it online!

Explanation:

1 Reverse the list (moving everything to the other stack, but that doesn't matter)

{({}<>)<>}<>
{        }   #keep moving numbers until you hit the 0s from an empty stack
 ({}<>)      #pop a number and push it on the other stack
       <>    #go back to the original stack
          <> #after everything has moved, switch stacks

2 Do steps 3-6 until there is nothing left on this stack:

{                                                                                         }

3 Duplicate the top two elements (2 3 -> 2 3 2 3)

(({}<>)<><(({})<<>({}<>)>)>)

(({}<>)<>                   #put the top number on the other stack and back on the very top
         <(({})             #put the next number on top after:
               <<>({}<>)>   #copying the original top number back to the first stack
                         )>)

4 Put a 1 on top if the top two are equal, a 0 otherwise (from the wiki)

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

5 If the top two were equal (non-zero on the top) add the next two and push the result

{{}(<({}{})>)}{}
{            }   #skip this if there is a 0 on top
 {}              #pop the 1
   (<      >)    #push a 0 after:
     ({}{})      #pop 2 numbers, add them together and push them back on 
              {} #pop off the 0

6 Move the top element to the other stack

({}<>)<>

7 Switch to the other stack and print implicitly

<>

Answer 4

PHP, 116 Bytes

<?$r=[];for($c=count($a=$_GET[a]);$c-=$x;)array_unshift($r,(1+($x=$a[--$c]==$a[$c-1]))*$a[$c]);echo json_encode($r);

or

<?$r=[];for($c=count($a=$_GET[a]);$c--;)$r[]=$a[$c]==$a[$c-1]?2*$a[$c--]:$a[$c];echo json_encode(array_reverse($r));

-4 Bytes if the output can be an array print_r instead of 'json_encode`

176 Bytes to solve this with a Regex

echo preg_replace_callback("#(\d+)(,\\1)+#",function($m){if(($c=substr_count($m[0],$m[1]))%2)$r=$m[1];$r.=str_repeat(",".$m[1]*2,$c/2);return trim($r,",");},join(",",$_GET[a]));

Answer 5

GNU sed, 41 38 37

Includes +1 for -r
-3 Thanks to Digital Trauma
-1 Thanks to seshoumara

:
s,(.*)(1+) \2\b,\1!\2\2!,
t
y,!, ,

Input and output are space separated strings in unary (based on this consensus).

Try it online!

Answer 6

Python, 61 bytes

def f(l):b=l[-2:-1]==l[-1:];return l and f(l[:~b])+[l[-1]<<b]

The Boolean b checks whether the last two elements should collapse by checking that they are equal in a way that's safe for lists of length 1 or 0. The last element if then appended with a multiplier of 1 for equal or 2 for unequal. It's appended to the recursive result on the list with that many elements chopped off the end. Thanks to Dennis for 1 byte!

Answer 7

Retina, 32

\d+
$*
r`\b\1 (1+)\b
$1$1
1+
$.&

r on line 3 activates right-to-left regex matching. And this means that the \1 reference needs to come before the (1+) capturing group that it references.

Try it online.

Answer 8

Perl, 41 bytes

Includes +1 for -p

Give input sequence on STDIN:

shift2048.pl <<< "2 2 2 4 4 8 2"

shift2048.pl:

#!/usr/bin/perl -p
s/.*\K\b(\d+) \1\b/2*$1.A/e&&redo;y/A//d

Answer 9

JavaScript (ES6), 68 bytes

f=a=>a.reduceRight((p,c)=>(t=p[0],p.splice(0,c==t,c==t?c+t:c),p),[])
    
console.log([
  [],
  [2, 2, 4, 4],
  [2, 2, 2, 4, 4, 8],
  [2, 2, 2, 2],
  [4, 4, 2, 8, 8, 2],
  [1024, 1024, 512, 512, 256, 256],
  [3, 3, 3, 1, 1, 7, 5, 5, 5, 5],
].map(f))

Answer 10

Perl, 43 + 1 (-p) = 44 bytes

Ton Hospel came up with 41 bytes answer, check it out!

-4 thanks to @Ton Hospel!

Edit : added \b, as without it it was failing on input like 24 4 on which the output would have been 28.

$_=reverse reverse=~s/(\b\d+) \1\b/$1*2/rge

Run with -p flag :

perl -pe '$_=reverse reverse=~s/(\b\d+) \1\b/$1*2/rge' <<< "2 2 2 4 4"

I don't see another way than using reverse twice to right-fold (as just s/(\d+) \1/$1*2/ge would left-fold, i.e 2 2 2 would become 4 2 instead of 2 4). So 14 bytes lost thanks to reverse... Still I think there must be another (better) way (it's perl after all!), let me know if you find it!

Answer 11

JavaScript (ES6),  68...64  58 bytes

a=>(g=p=>(x=a.pop())|p?p?[...g(p^x?x:!(p*=2)),p]:g(x):a)()

Try it online!

Commented

a => (                  // a[] = input array
  g = p =>              // g is a recursive function taking p = previous value
    (x = a.pop())       //   extract the last entry x from a[]
    | p ?               //   if either x or p is a positive integer:
      p ?               //     if p is a positive integer:
        [               //       update the output:
          ...g(         //         do a recursive call:
            p ^ x ?     //           if p is not equal to x:
              x         //             set new_p = x
            :           //           else:
              !(p *= 2) //             double p and set new_p = false
          ),            //         end of recursive call
          p             //         append p
        ]               //       end of output update
      :                 //     else:
        g(x)            //       do a simple recursive call with new_p = x
    :                   //   else:
      a                 //     stop recursion and return a[], which is guaranteed
                        //     to be an empty array at this point
)()                     // initial call to g with p undefined

Answer 12

Perl 5.10, 61 50 bytes (49 + 1 for flag)

Thanks to Ton Hospel for saving 11 bytes!

Regex-free solution, with -a flag:

@a=($F[-1]-$b?$b:2*pop@F,@a)while$b=pop@F;say"@a"

Try here!

Answer 13

05AB1E, 26 bytes

D¥__X¸«DgL*ê¥X¸«£vy2ôO})í˜

Try it online!

Generalized steps

1. Reduce by subtraction to find where consecutive elements differ
2. Reduce by subtraction over the indices of those places to find the length of consecutive elements
3. Split input into chunks of those lengths
4. Split chunks into pairs
5. Sum each pair
6. Reverse each summed chunk
7. Flatten to 1-dimensional list

Answer 14

Mathematica, 53 bytes

Join@@(Reverse[Plus@@@#~Partition~UpTo@2]&/@Split@#)&

Explanation

Split@#

Split the input into sublists consisting of runs of identical elements. i.e. {2, 2, 2, 4, 8, 8} becomes {{2, 2, 2}, {4}, {8, 8}}.

#~Partition~UpTo@2

Partition each of the sublist into partitions length at most 2. i.e. {{2, 2, 2}, {4}, {8, 8}} becomes {{{2, 2}, {2}}, {{4}}, {{8, 8}}}.

Plus@@@

Total each partition. i.e. {{{2, 2}, {2}}, {{4}}, {{8, 8}}} becomes {{4, 2}, {4}, {16}}.

Reverse

Reverse the results because Mathematica's Partition command goes from left to right, but we want the partitions to be in other direction. i.e. {{4, 2}, {4}, {16}} becomes {{2, 4}, {4}, {16}}.

Join@@

Flatten the result. i.e. {{2, 4}, {4}, {16}} becomes {2, 4, 4, 16}.

Answer 15

Java 7, 133 bytes

Object f(java.util.ArrayList<Long>a){for(int i=a.size();i-->1;)if(a.get(i)==a.get(i-1)){a.remove(i--);a.set(i,a.get(i)*2);}return a;}

Input is an ArrayList, and it just loops backwards, removing and doubling where necessary.

Object f(java.util.ArrayList<Long>a){
    for(int i=a.size();i-->1;)
        if(a.get(i)==a.get(i-1)){
            a.remove(i--);
            a.set(i,a.get(i)*2);
        }
    return a;
}

Answer 16

Perl, 37 bytes

Includes +4 for -0n

Run with the input as separate lines on STDIN:

perl -M5.010 shift2048.pl
2
2
2
4
4
8
2
^D

shift2048.pl:

#!/usr/bin/perl -0n
s/\b(\d+
)(\1|)$//&&do$0|say$1+$2

Answer 17

Haskell, 56 bytes

g(a:b:r)|a==b=a+b:g r|l<-b:r=a:g l
g x=x
r=reverse
r.g.r

Answer 18

PHP, 86 100 99 94 bytes

for($r=[];$v=+($p=array_pop)($a=&$argv);)array_unshift($r,end($a)-$v?$v:2*$p($a));print_r($r);

requires PHP 7.0; takes values from command line arguments.

Run with -nr or try it online.

Answer 19

Brain-Flak, 60 bytes

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

Try it online!

Explanation:

{({}<>)<>}<>   Reverse stack

{   While input exists
  (
    ({}<>)   Push copy of last element to the other stack
    <>[({})] And subtract a copy of the next element
  )   Push the difference
  {   If the difference is not 0
    ((<{}>)) Push two zeroes
  }{}  Pop a zero
  {   If the next element is not zero, i.e the identical element
    ({}<>{})  Add the element to the copy of the previous element
    (<>)      Push a zero
  }{}    Pop the zero
}<>  End loop and switch to output stack

Answer 20

Julia 205 bytes

t(x)=Val{x}
s(x)=t(x)()
f^::t(1)=f
^{y}(f,::t(y))=x->f(((f^s(y-1))(x)))
g()=[]
g{a}(::t(a))=[a]
g{a}(::t(a),B...)=[a;g(B...)]
g{a}(::t(a),::t(a),B...)=[2a;g(B...)]
K(A)=g(s.(A)...)
H(A)=(K^s(length(A)))(A)

Function to be called is H

eg H([1,2,2,4,8,2,])

This is in no way the shortest way do this in julia. But it is so cool, that I wanted to share it anyway.

• t(a) is a value-type, representing the value (a).
• s(a) is an instance of that value type
• g is a function that dispatches on the difference values (using the value types) and numbers of its parameters. And that is cool
• K just wraps g so that

Extra cool part:

f^::t(1)=f
^{y}(f,::t(y))=x->f(((f^s(y-1))(x)))

This defines the ^ operator to apply to functions. So that K^s(2)(X) is same as K(K(X)) so H is just calling K on K a bunch of times -- enough times to certainly collapse any nested case

This can be done much much shorter, but this way is just so fun.

Answer 21

PowerShell v2+, 81 bytes

param($n)($b=$n[$n.count..0]-join','-replace'(\d+),\1','($1*2)'|iex)[$b.count..0]

Takes input as an explicit array $n, reverses it $n[$n.count..0], -joins the elements together with a comma, then regex -replaces a matching digit pair with the first element, a *2, and surrounded in parens. Pipes that result (which for input @(2,2,4,4) will look like (4*2),(2*2)) over to iex (short for Invoke-Expression and similar to eval), which converts the multiplication into actual numbers. Stores the resulting array into $b, encapsulates that in parens to place it on the pipeline, then reverses $b with [$b.count..0]. Leaves the resulting elements on the pipeline, and output is implicit.

---

Test Cases

NB-- In PowerShell, the concept of "returning" an empty array is meaningless -- it's converted to $null as soon as it leaves scope -- and so it is the equivalent of returning nothing, which is what is done here in the first example (after some wickedly verbose errors). Additionally, the output here is space-separated, as that's the default separator for stringified arrays.

PS C:\Tools\Scripts\golfing> @(),@(2,2,4,4),@(2,2,2,4,4,8),@(2,2,2,2),@(4,4,2,8,8,2),@(1024,1024,512,512,256,256),@(3,3,3,1,1,7,5,5,5,5)|%{"$_ --> "+(.\2048-like-array-shift.ps1 $_)}
Invoke-Expression : Cannot bind argument to parameter 'Command' because it is an empty string.
At C:\Tools\Scripts\golfing\2048-like-array-shift.ps1:7 char:67
+   param($n)($b=$n[$n.count..0]-join','-replace'(\d+),\1','($1*2)'|iex)[$b.count. ...
+                                                                   ~~~
    + CategoryInfo          : InvalidData: (:String) [Invoke-Expression], ParameterBindingValidationException
    + FullyQualifiedErrorId : ParameterArgumentValidationErrorEmptyStringNotAllowed,Microsoft.PowerShell.Commands.InvokeExpressionCommand

Cannot index into a null array.
At C:\Tools\Scripts\golfing\2048-like-array-shift.ps1:7 char:13
+   param($n)($b=$n[$n.count..0]-join','-replace'(\d+),\1','($1*2)'|iex)[$b.count. ...
+             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    + CategoryInfo          : InvalidOperation: (:) [], RuntimeException
    + FullyQualifiedErrorId : NullArray

 --> 
2 2 4 4 --> 4 8
2 2 2 4 4 8 --> 2 4 8 8
2 2 2 2 --> 4 4
4 4 2 8 8 2 --> 8 2 16 2
1024 1024 512 512 256 256 --> 2048 1024 512
3 3 3 1 1 7 5 5 5 5 --> 3 6 2 7 10 10

Answer 22

Javascript - 103 bytes

v=a=>{l=a.length-1;for(i=0;i<l;i++)a[l-i]==a[l-1-i]?(a[l-i-1]=a[l-i]*2,a.splice(l-i,1)):a=a;return a}

Answer 23

APL (Dyalog Unicode), 20 bytes

⌽1⊥¨⌽⊂⍨2|⌽(⊥⍨=)¨,\∘⌽

Try it online!

Fully tacit version of the previous solution, thanks to Adám.

How it works

⌽1⊥¨⌽⊂⍨2|⌽(⊥⍨=)¨,\∘⌽  ⍝ Right argument: V, vector to reduce by 2048 rules
                   ⌽  ⍝ Reverse V to get RV
                ,\∘   ⍝ Prefixes of RV
         ⌽(  =)¨      ⍝ For each prefix, test if each element equals last element
           ⊥⍨         ⍝   and count trailing ones
                      ⍝   (one-based index of each item within runs)
       2|             ⍝ Modulo 2
    ⌽⊂⍨               ⍝ Partition RV at ones of the above
 1⊥¨                  ⍝ Sum of each chunk
⌽                     ⍝ Reverse back

---

APL (Dyalog Unicode), 26 bytes

⌽+/¨{⍵⊂⍨2|{⊥⍨⍵=⊃⌽⍵}¨,\⍵}⌽⎕

Try it online!

A full program. Link is to function version for easier testing.

How it works

⌽+/¨{⍵⊂⍨2|{⊥⍨⍵=⊃⌽⍵}¨,\⍵}⌽⎕
                         ⎕  ⍝ Take input
                        ⌽   ⍝ Reverse
    {                  }    ⍝ Apply the anonymous function...
                    ,\⍵     ⍝   Prefixes
          {       }¨        ⍝   For each prefix,
             ⍵=⊃⌽⍵          ⍝     Evaluate if each element is equal to last
           ⊥⍨               ⍝     and count trailing ones
                            ⍝     (one-based index of each item within runs)
        2|                  ⍝   Take modulo 2
     ⍵⊂⍨                    ⍝   Partition the input array at 1's of the above
 +/¨                        ⍝ Sum each group
⌽                           ⍝ Reverse back

Answer 24

Python 2, 94 bytes

def f(a,r=[]):
 while a:
    if len(a)>1and a[-1]==a[-2]:a.pop();a[-1]*=2
    r=[a.pop()]+r
 print r

Try it online

Answer 25

Julia, 73 82 Bytes

f(l)=l==[]?[]:foldr((x,y)->y[]==x?vcat(2x,y[2:end]):vcat(x,y),[l[end]],l[1:end-1])

Use right fold to build list from back to front (one could also use fold left and reverse the list at the beginning and end).

If the head of the current list is not equal to the next element to prepend, then just prepend it.

Else remove the head of the list (sounds kind of cruel) and prepend the element times 2.

Example

f([3,3,3,1,1,7,5,5,5,5]) 
returns a new list:
[3,6,2,7,10,10]

Answer 26

Racket 166 bytes

(λ(l)(let g((l(reverse l))(o '()))(cond[(null? l)o][(=(length l)1)(cons(car l)o)]
[(=(car l)(second l))(g(drop l 2)(cons(* 2(car l))o))][(g(cdr l)(cons(car l)o))])))

Ungolfed:

(define f
  (λ (lst)
    (let loop ((lst (reverse lst)) 
               (nl '()))
      (cond                            ; conditions: 
        [(null? lst)                   ; original list empty, return new list;
               nl]
        [(= (length lst) 1)            ; single item left, add it to new list
              (cons (first lst) nl)]
        [(= (first lst) (second lst))  ; first & second items equal, add double to new list
              (loop (drop lst 2) 
                    (cons (* 2 (first lst)) nl))]
        [else                          ; else just move first item to new list
              (loop (drop lst 1) 
                    (cons (first lst) nl))]  
        ))))

Testing:

(f '[])
(f '[2 2 4 4]) 
(f '[2 2 2 4 4 8]) 
(f '[2 2 2 2]) 
(f '[4 4 2 8 8 2])
(f '[1024 1024 512 512 256 256]) 
(f '[3 3 3 1 1 7 5 5 5 5])
(f '[3 3 3 1 1 7 5 5 5 5 5])

Output:

'()
'(4 8)
'(2 4 8 8)
'(4 4)
'(8 2 16 2)
'(2048 1024 512)
'(3 6 2 7 10 10)
'(3 6 2 7 5 10 10)

Answer 27

Japt, 12 bytes

ò¦ ®ò2n)mxÃc

Try it online!

Unpacked & How it works

Uò!= mZ{Zò2n)mx} c

Uò!=    Partition the input array where two adjacent values are different
        i.e. Split into arrays of equal values
mZ{     Map the following function...
Zò2n)     Split into arrays of length 2, counting from the end
          e.g. [2,2,2,2,2] => [[2], [2,2], [2,2]]
mx        Map `Array.sum` over it
}
c       Flatten the result

Got some idea from Jonathan Allan's Jelly solution.

Answer 28

APL (Dyalog Unicode), 34 bytes^SBCS

Anonymous prefix lambda.

{∊((⊃⍴⍨2|≢),+⍨⍴⍨∘⌊2÷⍨≢)¨⍵⊂⍨2≠/0,⍵}

Try it online!

{…} dfn; ⍵ is right argument

 0,⍵ prepend a zero to the argument

 2≠/ pairwise inequality mask

 ⍵⊂⍨ use that to partition (true means begin new partition here) the argument

 (…)¨ apply the following tacit function to each run of equal numbers:

  ≢ the length of the run

  2÷⍨ let 2 divide that

  ⌊ floor that

  ∘ then

  ⍴⍨ use it to reshape…

  +⍨ the doubled (lit. addition selfie) run

  (…), append that to the following:

   ≢ the length of the run

   2| division remainder when divided by two (1 for odd length runs, 0 for even length runs)

   ⊃⍴⍨ use that to reshape the first element of the run

 ∊ enlist (flatten)

Answer 29

Prolog (SWI), 97 87 bytes

[N,N|T]+[O|Q]:-O is N*2,T+Q.
[N|T]+[N|Q]:-T+Q.
R+R.
L-R:-reverse(L,M),M+Q,reverse(Q,R).

Try it online!

Answer 30

Ruby, 55 bytes

->a{c=[];c=[(b=a.pop)==a[-1]?a.pop*2:b]+c while a[0];c}

Try it online!

So long and still no Ruby answer? It can't be.

More golfing will follow.

Answer 31

C (GCC), 87 bytes

I'm not very familiar with the allowed I/O methods for C, but I think this is valid. The function takes an input array a (int *) and length l and two empty parameters r and w (int). The output is stored to the right portion of the input array, and the new length is returned.

f(a,l,r,w)int*a;{for(r=w=l;r--;)a[--w]=r<1|a[r]-a[r-1]?a[r]:a[r--]*2;return!!~l*~w-~l;}

Try It Online

The program may read at index -1 in the input array, which seems to work fine in my test program. Valgrind reports this access in some cases, but I was unable to get this to crash the program with global, automatic, or malloced input arrays on my system.

Acknowledgments

• -6 bytes thanks to ceilingcat

Answer 32

Common Lisp, 143 bytes

(defun e(l)(if(<(length l)1)'()(if(eq(car l)(cadr l))(cons(*(car l)2)(e(cddr l)))(cons(car l)(e(cdr l))))))
(defun f(l)(reverse(e(reverse l))))

Try it online!

Answer 33

Powershell, 73 71 bytes

for($r=@();$z=$args[--$i]){$i-=$e=$z-eq$args[$i-1]
$r=,($z+$z*$e)+$r}$r

Less golfed test script:

$f = {

$r=@()                      # result
for(;$z=$args[--$i]){       # all elements from end to start
    $e=$z-eq$args[$i-1]     # current is $equal to previous
    $i-=$e                  # shift if need 
    $r=,($z+$z*$e)+$r       # insert to start
}
$r                          # output result

}

@(
    ,( @()  ,  @() )
    ,( (2, 2, 4, 4)  , (4, 8) )
    ,( (2, 2, 2, 4, 4, 8)  , (2, 4, 8, 8) )
    ,( (2, 2, 2, 2)  , (4, 4) )
    ,( (4, 4, 2, 8, 8, 2)  , (8, 2, 16, 2) )
    ,( (1024, 1024, 512, 512, 256, 256)  , (2048, 1024, 512) )
    ,( (3, 3, 3, 1, 1, 7, 5, 5, 5, 5)  , (3, 6, 2, 7, 10, 10) )
) | % {
    $arr,$expected = $_
    $result = &$f @arr     # splatting
    "$("$result"-eq"$expected"): $result"
}

Output:

True:
True: 4 8
True: 2 4 8 8
True: 4 4
True: 8 2 16 2
True: 2048 1024 512
True: 3 6 2 7 10 10

Answer 34

Python 3, 100 73 bytes

Thanks to @jo-king -27 bytes!!!

n=lambda l:l[1:]and[*n(l[:~(l[-1]==l[-2])]),l[-1]*(1+(l[-1]==l[-2]))]or l

Try it online!

Answer 35

Pushy, 18 bytes

$L1=?v;2d=?+;v;O@_

Try it online!

$                     \ While there are items left on input stack:
 L1=?                 \  if len(input) == 1:
     v;               \    move the final remaining item to output stack
                      \  else:
       2d             \    copy the last two items
         =?           \    if equal:
           +;         \      add together
             v;       \    move the last item on stack to output stack
               O@_    \ Print the output stack (reversed)

Answer 36

Lua 5.3, 117 113 bytes

function f(t)i,o=#t,{}while i>0 do v=t[i]if v==t[i-1]then v=v*2i=i-1 end i=i-1table.insert(o,1,v)end return o end

Try it online!

I think Lua 5.1 would require an extra byte because a number has to be separated from an identifier: v=v*2i=i-1 → v=v*2 i=i-1.

Answer 37

C# (Visual C# Interactive Compiler), 72 bytes

x=>{for(int i=x.Count-1;i>0;)if(x[i--]==x[i]){x.RemoveAt(i);x[i--]*=2;}}

Try it online!

This function outputs by modifying an argument.

Credit to @ASCIIOnly for suggesting that I not create a new list. That suggestion led me to discover the above referenced rule. Total savings of 22 bytes without creating a new list and by removing the return statement :)

Less golfed...

// x is an input List
x=>{
  // iterate from back to front
  for(int i=x.Count-1;i>0;)
    // check for consecutive elements
    if(x[i--]==x[i]){
      // remove the first occurrence
      x.RemoveAt(i);
      // double the second occurrence
      // which has been shifted
      x[i--]*=2;
    }
}

Answer 38

F# (.NET Core), 87 bytes

fun x->(List.foldBack(fun e (h::t)->if h=e then 0::e*2::t.Tail else e::e::t)x [0]).Tail

Try it online!

Uses the List.foldBack function to process the input from back to front. The head of the working list contains an element that can be merged, or a 0 to indicate the previous element cannot be merged

Answer 39

05AB1E, 8 bytes

γε2ôOR}˜

Try it online or verify all test cases.

Explanation:

γ          # Split the (implicit) input into chunks of equal adjacent values
           #  i.e. [4,4,2,8,8,8,2] → [[4,4],[2],[8,8,8],[2]]
 ε    }    # Map each to:
  2ô       #  Split it into parts of size 2
           #   i.e. [8,8,8] → [[8,8],[8]]
    O      #  Take the sum of each
           #   i.e. [[8,8],[8]] → [16,8]
     R     #  Reverse the entire list of sums
           #   i.e. [16,8] → [8,16]
       ˜   # After the map, flatten everything (and output the result implicitly)
           #  i.e. [[8],[2],[8,16],[2]] → [8,2,8,16,2]

Answer 40

Mathematica, 51 bytes

Abs[#//.{Longest@a___,x_/;x>0,x_,b___}:>{a,-2x,b}]&

---

{Longest@a___,x_/;x>0,x_,b___} matches a list containing two consecutive identical positive numbers and transform these two numbers into -2x. Longest forces the matches to happen as late as possible.

The process is illustrated step by step:

   {3, 3, 3, 1, 1, 7, 5, 5, 5, 5}
-> {3, 3, 3, 1, 1, 7, 5, 5, -10}
-> {3, 3, 3, 1, 1, 7, -10, -10}
-> {3, 3, 3, -2, 7, -10, -10}
-> {3, -6, -2, 7, -10, -10}
-> {3, 6, 2, 7, 10, 10}

Answer 41

Vim, 28 bytes

G@='?\v(\d+)\n\1<C-@>DJ@"<C-A>-@=<C-@>'<CR>

A macro that regex searches backward for matching consecutive numbers, and adds them together.

The input array needs to be one number per line. This format saves me strokes, which is nice, but the real reason is to work around overlapping regex matches. Given the string 222, if you /22 you'll match only the first pair, not the overlapping second pair. The overlap rules are different when the two pairs start on different lines. In this challenge [2, 2, 2] becomes [2, 4], so matching the overlapping pair is critical.

NOTE: The challenge asked for only a single pass. For that reason, you need to have :set nowrapscan. With :set wrapscan I could make a version that finishes the job on multiple passes, though this solution as written won't always do that.

• <C-@>: Normally, in a command line, to type a literal <CR> without running the command you'd have to escape it with <C-V>. But you can type <C-@> unescaped and it will be treated as a <C-J>/<NL>, which will be like <CR> when you run the macro but not when you're typing. Try reading :help NL-used-for-Nul.
• @=: I can't use a recorded macro easily this time because there's a possibility the input might have no matching pairs. If that happens while running a macro, the unsuccessful search will fail the macro. But if it happens during the (implicit first) recording pass, the rest of the normal mode commands will run, damaging the file. The downside of @= is I lose a byte on the recursive call; sometimes you can use @@ as a recursive call, but that would run @" from 4 bytes earlier in this case.
• DJ@"<C-A>-: DJ deletes the line and puts the number (no newline) in a register, so I can run it as a macro for a number argument to <C-A>. I have to - afterward so I don't get a second match in cases like [4, 2, 2].

Answer 42

Perl6, 92 bytes

{my @b;loop ($_=@^a-1;$_>=0;--$_) {@b.unshift($_&&@a[$_]==@a[$_-1]??2*@a[$_--]!!@a[$_])};@b}

Answer 43

Java 8, 130 114 bytes

Edit:

• -16 bytes off. Thanks to @Kevin Cruijssen.

Snipet:

s->{int j=0,i=s.length,l[]=new int[i];for(;--i>-1;[j++]=s[i]==s[i-1]?s[i--]*2:s[i]);return Collection.reverse(l);}

Code:

public static int[] shift(int[]a){
  List<int> out = new ArrayList<>();
  for(int i = s.length-1; i>-1;i--){
    if(s[i]==s[i-1]){
      out.add(s[i]*2);
      i--;
    }else{
      out.add(s[i]);
    }
  }
  return Arrays.reverse(out.toArray());
}