82
\$\begingroup\$

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 :)

\$\endgroup\$
  • 11
    \$\begingroup\$ This is a very nice first challenge. Welcome to the site! \$\endgroup\$ – James Oct 5 '16 at 20:12
  • 1
    \$\begingroup\$ Input is not necessarily sorted and numbers are greater than zero, that is the only restriction on numbers. We may let largest value fit in standard int32 bounds i think. Empty array gives empty array as a result. Thanks for the participation, appreciate that :) \$\endgroup\$ – greenwolf Oct 6 '16 at 1:52
  • 3
    \$\begingroup\$ To those still voting to close as unclear, the challenge essentially boils down to this: Assume you have an array of positive integers. Walk through it from end to start. If the current element is equal to the next, replace it with the sum of both and move to the element after the replacement, then perform this check again for that element and the next. Repeat until the beginning of the array is reached. \$\endgroup\$ – user2428118 Oct 6 '16 at 9:49
  • 1
    \$\begingroup\$ @Titus "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]." \$\endgroup\$ – Martin Ender Oct 6 '16 at 10:38
  • 1
    \$\begingroup\$ The ruling on empty arrays is unfortunate; it has invalidated a few answers, including my own. \$\endgroup\$ – Dennis Oct 6 '16 at 14:31

43 Answers 43

1
2
0
\$\begingroup\$

Perl6, 92 bytes

{my @b;loop ($_=@^a-1;$_>=0;--$_) {@b.unshift($_&&@a[$_]==@a[$_-1]??2*@a[$_--]!!@a[$_])};@b}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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-1v=v*2 i=i-1.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 113 bytes through some rearranging \$\endgroup\$ – Jo King Jan 12 '19 at 11:49
  • \$\begingroup\$ Excellent! Updated post. \$\endgroup\$ – cyclaminist Jan 12 '19 at 21:01
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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;
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ why not this \$\endgroup\$ – ASCII-only Jan 14 '19 at 7:09
  • \$\begingroup\$ I see... You are forcing the type to be a proper List vs IList. It seemed a little strange to be mangling the input and returning the same object, but I guess that doesn't matter as much w/ code golf :) Almost seems like you'd want to use Action<List> and don't return anything? \$\endgroup\$ – dana Jan 14 '19 at 7:19
  • \$\begingroup\$ Well... they do say "returns a shifted array". Plus, solutions of many languages are modifying the array simply because it is so insanely expensive to duplicate it \$\endgroup\$ – ASCII-only Jan 14 '19 at 7:22
  • \$\begingroup\$ @ASCIIOnly - looks like modifying the input might suffice. codegolf.meta.stackexchange.com/a/4942/8340 \$\endgroup\$ – dana Jan 14 '19 at 7:42
  • \$\begingroup\$ Oh, huh, TIL. I guess it's just that it's not too often that modifying input is shorter \$\endgroup\$ – ASCII-only Jan 14 '19 at 7:52
0
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
-1
\$\begingroup\$

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());
}
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Hi, you can golf it some more like this: 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]);...} Also, Arrays#reverse doesn't exist?.. :S Collections#reverse does, but Arrays not a.f.a.i.k. (And if it did exist, you'd need java.util. in front of it.) \$\endgroup\$ – Kevin Cruijssen Oct 6 '16 at 8:08
  • 1
    \$\begingroup\$ This code is not fully representational of the full code required to run it, nor is it capable of running as-is. \$\endgroup\$ – Addison Crump Oct 6 '16 at 11:05
  • \$\begingroup\$ I wrote Snipet not full programm and this declares a function object as the OP said: The task is to write a function [...] \$\endgroup\$ – Roman Gräf Oct 6 '16 at 12:28
  • 1
    \$\begingroup\$ I can't get either version of your code to compile in Java 8. Additionally, it looks to me like your golfed code returns an array of the original size, not the newly modified size. \$\endgroup\$ – Geobits Oct 6 '16 at 16:34
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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