Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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!

share|improve this question
    
When you say argument, do you mean as an argument to a function or as a command-line argument to the program? –  Aleksi Torhamo Mar 10 at 15:27
    
@AleksiTorhamo Command-line arg, so it wouldn't count toward your total. –  Rainbolt Mar 10 at 15:30
28  
I love this multi-question-spanning doomsday story. –  mikhailcazi Mar 10 at 16:23
    
re: "populations never skip an island" - your example does show population moving multiple islands in a row. Is there another meaning I'm missing? –  Allen Gould Mar 12 at 22:13
    
@AllenGould The populations did indeed move across multiple islands, but they never skipped one. If there were 32 people on the far right island, they would die like 16, 8, 4, and finally 2 would reach the leftmost island. –  Rainbolt Mar 12 at 22:16

18 Answers 18

up vote 25 down vote accepted

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.

share|improve this answer
    
This is genius. –  Gareth Mar 11 at 11:15
7  
APL should be illegal... –  Kiwy Mar 11 at 12:47
1  
@Kiwy I don't understand your comment. Why should APL be declared illegal? Feel free to submit your APL solution as well. –  Howard Mar 11 at 16:34
2  
@Kiwy: This is more than just using APL... it's also a very clever approach to the solution, which happens to fit very neatly into an APL program. This is what golf is all about! –  Claudiu Mar 11 at 17:00

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
share|improve this answer
1  
+1, this is shorten than anything I could find. Now, if it only weren't for that pesky "stop on westernmost island" rule, ~]{2base}2*' '* would do the trick... –  Ilmari Karonen Mar 10 at 19:44
    
@IlmariKaronen Choose the right language (see the APL solution) and the pesky rule becomes fine. –  Howard Mar 11 at 8:04

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.

share|improve this answer

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]

share|improve this answer
1  
See Rusher's comments on one of the Python answers; the input should be a string following the format given in the example, not a list. –  Aleksi Torhamo Mar 10 at 16:32
    
@AleksiTorhamo is right. Allowing a comma separated list would put your code at a distinct advantage over those who followed the format provided in the example. In the future, I'll try to be clearer that the format provided in the example is the format. Sorry about that. –  Rainbolt Mar 10 at 16:39
    
OK, edited. Should the output be joined also or the array format is ok ? –  Michael Mar 10 at 16:42
    
I came up with more-or-less the same: f=a=>{a=a.split(' ');for(x=5;--x;a[x]&=1)a[x-1]-=-a[x]/2|0;return a} which is 68 characters. –  MT0 Mar 10 at 18:15

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.

share|improve this answer

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))
share|improve this answer
1  
You can get it down to 100 if you compress the while down to one line by using semicolons instead of newlines and indentation, and remove the space directly after print :) –  Aleksi Torhamo Mar 10 at 20:20
    
@AleksiTorhamo Thanks. I also learned that integer division in whatever version of Python I used requires only a single slash, so I knocked it below 100. –  Rainbolt Mar 10 at 20:54
1  
Ah, true! I also just realized you can also omit the ' ' from the split, bringing it down to 96 and beating the other python2 solutions. –  Aleksi Torhamo Mar 10 at 21:04

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}
share|improve this answer
    
You must not reverse the string before splitting but after. Otherwise your solution may yield wrong results for multi-digit numbers in the input. –  Howard Mar 10 at 16:55
    
I even considered both "possibilities" - albeit not being aware of numbers with more than one digit... :D Thanks! –  David Herrmann Mar 10 at 18:07

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

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.

share|improve this answer
    
Using the binary representation is ingenius! Lettercount.com gave you an 85. Did you overcount, or is lettercount a bad tool to use? –  Rainbolt Mar 11 at 13:01
    
@Rusher: My tool was using CRLF line endings. Counting it with Unix line endings, it's 85. –  user2357112 Mar 11 at 14:47

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;}
share|improve this answer
    
Is this hard-coded for only 5 islands? –  Geobits Mar 12 at 0:51

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
share|improve this answer
    
Crashed when provided with input that follows the format provided in the example. –  Rainbolt Mar 10 at 15:20
    
@Rusher I updated the answer to work with the exact format used in the question. –  arshajii Mar 10 at 15:26
    
Others may be at a disadvantage if special exceptions are allowed for Python coders. Sorry, and thanks for updating your answer. I'll try to be more clear in the future that the example input is the required format. –  Rainbolt Mar 10 at 15:27

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}

share|improve this answer
    
My solution produces 270, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0 for your long test data. I think I have confirmed that I am correct. –  OldCurmudgeon Mar 11 at 23:38
    
Strange, given how it works. I'll take a look tomorrow at the case. –  David Carraher Mar 12 at 1:10

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

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

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

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))
share|improve this answer
    
You might add a header like #Java - 123 Characters –  Rainbolt Mar 12 at 14:25
    
Thanks, I've added the header –  Jordon Biondo Mar 12 at 15:39

awk - 44 Characters

{for(i=NF;i>1;){n=int($i/2);$i%=2;$--i+=n}}1
share|improve this answer

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] + " ");
}
share|improve this answer
4  
Can you provide a compiler that will run this code? Also, the format and the possible sources for the input were provided in the question. Molding the input to a Java array gives you an unfair advantage over others. –  Rainbolt Mar 11 at 13:22

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.