The Floating Horde

Question

Introduction

The rain finally subsided. Most of humanity drowned due to a bug in @user12345's code. Survivors are scattered across a worldwide archipelago. Radio communication is up, and humanity is poised to thrive once more. For no reason whatsoever, zombie pirates have gathered at the Prime Meridian, and are sweeping westward. The horde devours all.

Problem

Our doomsday scenario can be described by 5 integers on a single line which represent a set of cooperating island communities. They are ordered from west (leftmost integer) to east (rightmost integer).

Beginning with the island farthest east, islanders flee in pairs to the next closest island. Curiously, for each pair that embarks, only one of them ever survives the trip. Islanders only travel in pairs. Odd populations elect a sole inhabitant to stay behind and provide the latest radio updates on the antics of the zombie pirate horde. Populations refuse to travel until all islands to the east of them have completed their migrations or died. When the population reaches the final, westernmost island, travel ceases.

The operations manager at the end of the world needs a program that can output the final population counts of each village.

Example Input

3 8 6 0 2

Example Output

8 1 0 1 0

Assumptions

• Input may be provided via stdin, read from an arbitrarily named file, or accepted as an argument
• For each island, 0 <= population <= 1024
• Populations never skip an island

Shortest answer wins!

Answer 1

APL, 16 characters

{(1e9,4⍴2)⊤2⊥⍎⍵}

The input is provided as string to this block:

{(1e9,4⍴2)⊤2⊥⍵} "3 8 6 0 2"
8 1 0 1 0

or one char less if the input is provided as argument to this block:

{(1e9,4⍴2)⊤2⊥⍵} 3 8 6 0 2
8 1 0 1 0

It is based on the idea of Ilmari Karonen in this comment.

• 2⊥⍵ does a base 2 conversion of the input.
• (1e9,4⍴2)⊤ thus converts this number back into base 2 (for the four last digits) and base 1e9 for the first, which is enough for the input ranges given above. (1e9,4⍴2 builds the list 1e9 2 2 2 2.)

Note that the fleeing west is done automatically by the base conversion during this process.

Answer 2

GolfScript, 23 22 characters

~]{{.2/@+\2%}*]}4*' '*

An iterative approach. The array is iterated several times and each time a number of pairs is transferred from right to left. Try the example online.

Short explanation of the code:

~]       # convert input to an integer
{        # loop 4 times (enough for a 5-elements input)
  {      # inject this block into the array
    .    # duplicate (l r r)
    2/   # determine surviving people (l r r%2)
    @+\  # add to the left (l+r/2 r)
    2%   # determine remaining people (l+r/2 r%2)
  }*
  ]      # make array again of the results
}4*
' '*     # format output

Answer 3

GolfScript (25 chars)

~]-1%{\.1&\2/@+}*]-1%' '*

Online demo

Pretty straightforward solution: there's a more interesting approach which defines the output value for each island as a function of the input values, but I don't think it can be golfed nearly as far as actually following the redistribution algorithm described in the question.

Answer 4

Javascript/ES6 (69)

Playing with bitwise operators :

• x&=1 keeps the lowest bit (1 if odd, 0 if even)
• x>>1 is division by 2 for integers

f=a=>{a=a.split(' ');for(i=5;--i;a[i]&=1)a[i-1]-=-(a[i]>>1);return a}

Version without ES6 :

function f(a){a=a.split(' ');for(i=5;--i;a[i]&=1)a[i-1]-=-(a[i]>>1);return a}

Examples :
f("3 8 6 0 2") returns [8, 1, 0, 1, 0]
f("0 997 998 999 1000") returns [935, 0, 1, 1, 0]

Answer 5

Python - 96 Characters

First time golfing! Input from stdin.

n=map(int,raw_input().split())
x=4
while x:n[x-1]+=n[x]/2;n[x]%=2;x-=1
print' '.join(map(str,n))

Answer 6

Ruby, 97 90 74 72

Online version

Golfed it a bit further, not reversing the array anymore...

f=->i{i=i.split.map(&:to_i);(1..4).each{|n|i[-n-1]+=i[-n]/2;i[-n]%=2};i}

Answer 7

J (26 characters)

Here is my solution in J: ((<.@-:@}.,0:)+{.,2|}.)^:_

   islands1 =: 3 8 6 0 2
   islands2 =: 3 8 6 3 2
   ((<.@-:@}.,0:)+{.,2|}.)^:_ islands1
8 1 0 1 0
   ((<.@-:@}.,0:)+{.,2|}.)^:_ islands2
9 0 0 0 0

This general solution should work with any number of islands.

Answer 8

C - 121 characters

Input is taken from stdin.

a[5];main(i){b(i=0,0);while(i++<5)printf("%i ",a[i-1]);}b(i,j){scanf("%i",&i);return j<5?i+=
b(i,j+1)/2,a[j]=j?i&1:i,i:0;}

Answer 9

Python2 - 98 characters

Input from stdin.

s=[0]
for v in raw_input().split()[::-1]:s=[int(v)+s[0]/2,s[0]%2]+s[1:4]
print' '.join(map(str,s))

Python3 - 79 characters

Input from stdin.

s=[0]
for v in input().split()[::-1]:s=[int(v)+s[0]//2,s[0]%2]+s[1:4]
print(*s)

Answer 10

Python 2, 85 80 bytes

b=1
for x in raw_input().split():b=2*b+int(x)
print b/16-2,' '.join(bin(b)[-4:])

X people starting on any island are equivalent to X*2 people starting one island to the right. This code converts everyone in the starting configuration to their equivalent in far-right-islanders, then uses the binary representation of the result to determine how many people end up on each island.

EDIT: Shortened the code by initializing b to 1 instead of 0, allowing the use of bin instead of a format string.

Answer 11

Python (101)

l=map(int,raw_input().split())
for i in range(4):l[3-i]+=l[4-i]/2;l[4-i]%=2
print' '.join(map(str,l))

We loop through the list from back to front and move the populations around according to the specification, then print the list. Here's a quick test:

>>> l=map(int,raw_input().split())
3 8 6 0 2
>>> for i in range(4):l[3-i]+=l[4-i]/2;l[4-i]%=2
... 
>>> print' '.join(map(str,l))
8 1 0 1 0

Answer 12

Mathematica 105

This should work with any number of islands.

f[w_,n_:1]:=
If[n==Length@w,w,
f[w~ReplacePart~{-n-> Mod[z=w[[-n]],2],-(n+1)->(w[[-(n+1)]]+ z~Quotient~2)},n+1]]

Examples

5 islands

f[{3, 8, 6, 0, 2}]

{8, 1, 0, 1, 0}

---

25 islands

f[{145, 144, 144, 59, 35, 129, 109, 99, 200, 24, 219, 96, 12, 121, 75,20, 153, 124, 131, 178, 228, 120, 63, 207, 228}]

{270, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0}

Answer 13

Java - 647 533 but hoping for some brownie points for Java 8 Streams.

class I{int p;I e;I(int p,I e){this.p=p;this.e=e;}void x(){if(e!=null){int r=p&1;e.p+=(p-r)/2;p=r;}}public String toString(){return ""+p;}}Deque<I>B(String d){H<I>e=new H<>();return Arrays.stream(d.split(" ")).map(s->Integer.valueOf(s)).map(p->e.hold(new I(p,e.held()))).collect(Collectors.toCollection(LinkedList::new));}void x(Deque<I>is){is.descendingIterator().forEachRemaining((I i)->{i.x();});}void t(String s){Deque<I> a=B(s);x(a);System.out.println(a);}class H<T>{T h=null;H(){}T hold(T t){return (h=t);}T held(){return h;}}

The uncompressed form:

private static class Island {
  int population;
  final Island eastwardIsland;

  Island(int population, Island eastwardIsland) {
    this.population = population;
    this.eastwardIsland = eastwardIsland;
  }

  private void exodus() {
    if (eastwardIsland != null) {
      // How many remain.
      int remain = population & 1;
      // How many leave.
      int leave = population - remain;
      // Account for 50% death rate.
      int arrive = leave / 2;
      // Modify the eastward island population.
      eastwardIsland.population += arrive;
      // Change my population.
      population = remain;
    }
  }

  @Override
  public String toString() {
    return String.valueOf(population);
  }

}

private Deque<Island> buildIslands(String data) {
  // Holds the island to the east as we traverse.
  final Holder<Island> eastward = new Holder<>();
  // Build my list of islands - assumes order is retained.
  return Arrays.stream(data.split(" "))
          // Convert to int.
          .map(s -> Integer.valueOf(s))
          // Build the island in a chain.
          .map(p -> eastward.hold(new Island(p, eastward.held())))
          // Roll them into a linked list.
          .collect(Collectors.toCollection(LinkedList::new));
}

private void exodus(Deque<Island> islands) {
  // Walk backwards.
  islands.descendingIterator()
          // Perform all exodus.
          .forEachRemaining((Island i) -> {
            i.exodus();
          });
}

private void test(String data) {
  Deque<Island> archipelago = buildIslands(data);
  // Initiate the exodus.
  exodus(archipelago);
  // Print them.
  System.out.println(archipelago);
}

With an assist of:

// Mutable final.
private static class Holder<T> {
  private T held = null;

  public Holder() {
  }

  public Holder(T it) {
    held = it;
  }

  public T hold(T it) {
    return (held = it);
  }

  public T held() {
    return held;
  }

  @Override
  public String toString() {
    return held == null ? "null" : held.toString();
  }

}

Slightly concerned that @DavidCarraher's test:

145 144 144 59 35 129 109 99 200 24 219 96 12 121 7520 153 124 131 178 228 120 63 207 228

generates

270, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0

Answer 14

Java - 196 195

I told myself I wouldn't post it if I couldn't get it under 200... I honestly don't think I can get rid of anything else, it's pretty slim for Java.

class H{public static void main(String[]a){int l=a.length,p[]=new int[l],i=l;for(;i-->0;){p[i]=Integer.valueOf(a[i]);if(l-i>1){p[i]+=p[i+1]/2;p[i+1]%=2;}}for(;++i<l;System.out.print(p[i]+" "));}}

Line breaks:

class H{
    public static void main(String[]a){
        int l=a.length,p[]=new int[l],i=l;
        for(;i-->0;){
            p[i]=Integer.valueOf(a[i]);
            if(l-i>1){
                p[i]+=p[i+1]/2;
                p[i+1]%=2;
            }
        }
        for(;++i<l;System.out.print(p[i]+" "));
    }
}

Sample input output:

$ java H 3 8 6 0 2
8 1 0 1 0

$ java H 0 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 0 1 0 0

$java H 235 897 158 693
809 1 0 1

Answer 15

Java - 179 characters

Compressed:

class F{public static void main(String[] a){int l=0,x,s,i=a.length-1;String z="";for(;0<=i;i--){x=Integer.valueOf(a[i])+l;s=i>0?x%2:x;l=(x-x%2)/2;z=s+" "+z;}System.out.print(z);}}

Normal:

public class FloatingHorde {

    public static void main(String[] a) {
        int leave = 0;
        String outputStr = "";
        for (int i = a.length - 1; 0 <= i ; i--) {
            int x = Integer.valueOf(a[i]) + leave;
            int stays = i > 0 ? x % 2 : x;
            leave = (x - x % 2) / 2;
            outputStr = stays + " " + outputStr;
        }
        System.out.print(outputStr);
    }
}

Sample output:

$ java F 3 8 6 0 2
8 1 0 1 0

$ java F 7 6 5 4 3
11 1 1 1 1

Answer 16

Emacs Lisp 144 chars

Not tiny, but it works

(lambda (d)
   (setq x d)(while(cdr x)
           (setcar(cdr x)(+(/(-(car x)(%(car x)2))2)(cadr x)))
           (setcar x (-(car x)(*(/(car x)2)2)))
       (pop x))
   (reverse d))

Answer 17

awk - 44 Characters

{for(i=NF;i>1;){n=int($i/2);$i%=2;$--i+=n}}1

Answer 18

Java - 116 Characters

For example int[] i = {2, 33, 16, 5}; (I guess those don't add to the count, since each number can vary) would output 23 0 0 1

for(int j = i.length-1; j > 0; j--) {       
    while(i[j] > 1) {
        i[j] -= 2;
        i[j-1]++;
    }       
}
for(int j = 0; j < i.length; j++) {     
    System.out.print(i[j] + " ");
}