Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

Examples:

[2, 2, 4, 4] -> [4, 8]
[2, 2, 2, 4, 4, 8] -> [2, 4, 8, 8]
[2, 2, 2, 2] -> [4, 4]

I am also very interested in solution using reduce :)

share|improve this question
1  
This is a very nice first challenge. Welcome to the site! – DJMcMayhem 4 hours ago
    
Related. Related. (There are several other 2048-based challenges, but the merging operation is most important in these two I think.) – Martin Ender 3 hours ago
1  
Will the input always be sorted? (It is in all of your examples.) – Martin Ender 3 hours ago
1  
What's the largest value that can be contained in the array? Will all elements be powers of 2? Can the list contain 0 or 1? Can the input array be empty? – mbomb007 3 hours ago
    
Can there be negative numbers in the array? – nimi 2 hours ago

10 Answers 10

Haskell, 47 bytes

e#(a:b)|e==a=2*a:b|1<2=e:a:b
e#_=[e]
foldr(#)[]

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

share|improve this answer
1  
This gives [4,2,2] -> [8], but it should give [4,4] if I understand the spec. – xnor 3 hours ago
    
@xnor: before I fix it, I need to know if there can be negative numbers in the array, so I want to wait until the OP answers my question... – nimi 2 hours ago

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]
share|improve this answer

Brain-Flak 158

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

Try it online!

Explanation:

1 Reverse the list (taken from the wiki)

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

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

<>
share|improve this answer

PHP, 124 Bytes

<?$c=count($a=$_GET[a]);while($c){if($a[--$c]==$a[$c-1]){$r[]=2*$a[$c];$c--;}else$r[]=$a[$c];}sort($r);echo json_encode($r);
share|improve this answer

Perl, 47 + 1 (-p) = 48 bytes

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/(\d+) \1/$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!

share|improve this answer

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.

share|improve this answer
    
Nice.. That right-to-left option to match is quite handy! Is it part of .Net regex or a Retina feature? – Dada 3 hours ago
    
I was just about to post mine at 26, using linefeed-separation as the input format: retina.tryitonline.net/… the main savings come from that and using transliteration to get rid of the second substitution. – Martin Ender 3 hours ago
    
@Dada It's a .NET feature (and it's used under the hood to enable arbitrary-length lookbehinds). Retina has no unique regex features yet (although it has some unique substitution features). – Martin Ender 3 hours ago
    
@MartinEnder Ok thanks! .NET regex's are really great! jealous perl coder spotted – Dada 3 hours ago
    
@MartinEnder I your solution is different enough to warrant another answer – Digital Trauma 3 hours ago

GNU sed 41 38

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

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

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

Try it online!

share|improve this answer
    
@DigitalTrauma Yep! I always forget about that. Thanks! – Riley 3 hours ago

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
share|improve this answer

JavaScript (ES6), 68 65 58 57 bytes

Waiting for the OP answers to fix it if necessary for cases such as [2N, N, N].

f=(a,l=[])=>(x=a.pop())-l?f(a,x).concat(l):x?f(a,2*x):[l]

console.log(f([2, 2, 4, 4]));
console.log(f([2, 2, 2, 4, 4, 8]));
console.log(f([2, 2, 2, 2]));

Alternate version, 72 bytes

More bullet-proof:

a=>a.reverse().join`+`.replace(/(.)\+\1/g,c=>eval(c)).split`+`.reverse()
share|improve this answer
1  
I was about to suggest the edit you just made :) – ETHproductions 2 hours ago

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.