28
\$\begingroup\$

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!

\$\endgroup\$
6
  • \$\begingroup\$ When you say argument, do you mean as an argument to a function or as a command-line argument to the program? \$\endgroup\$ Mar 10, 2014 at 15:27
  • \$\begingroup\$ @AleksiTorhamo Command-line arg, so it wouldn't count toward your total. \$\endgroup\$
    – Rainbolt
    Mar 10, 2014 at 15:30
  • 29
    \$\begingroup\$ I love this multi-question-spanning doomsday story. \$\endgroup\$ Mar 10, 2014 at 16:23
  • \$\begingroup\$ re: "populations never skip an island" - your example does show population moving multiple islands in a row. Is there another meaning I'm missing? \$\endgroup\$ Mar 12, 2014 at 22:13
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Rainbolt
    Mar 12, 2014 at 22:16

18 Answers 18

26
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ This is genius. \$\endgroup\$
    – Gareth
    Mar 11, 2014 at 11:15
  • 7
    \$\begingroup\$ APL should be illegal... \$\endgroup\$
    – Kiwy
    Mar 11, 2014 at 12:47
  • 1
    \$\begingroup\$ @Kiwy I don't understand your comment. Why should APL be declared illegal? Feel free to submit your APL solution as well. \$\endgroup\$
    – Howard
    Mar 11, 2014 at 16:34
  • 4
    \$\begingroup\$ @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! \$\endgroup\$
    – Claudiu
    Mar 11, 2014 at 17:00
13
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ +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... \$\endgroup\$ Mar 10, 2014 at 19:44
  • \$\begingroup\$ @IlmariKaronen Choose the right language (see the APL solution) and the pesky rule becomes fine. \$\endgroup\$
    – Howard
    Mar 11, 2014 at 8:04
8
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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]

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Mar 10, 2014 at 16:32
  • \$\begingroup\$ @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. \$\endgroup\$
    – Rainbolt
    Mar 10, 2014 at 16:39
  • \$\begingroup\$ OK, edited. Should the output be joined also or the array format is ok ? \$\endgroup\$
    – Michael M.
    Mar 10, 2014 at 16:42
  • \$\begingroup\$ 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. \$\endgroup\$
    – MT0
    Mar 10, 2014 at 18:15
6
\$\begingroup\$

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))
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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 :) \$\endgroup\$ Mar 10, 2014 at 20:20
  • \$\begingroup\$ @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. \$\endgroup\$
    – Rainbolt
    Mar 10, 2014 at 20:54
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Mar 10, 2014 at 21:04
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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

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;}
\$\endgroup\$
1
  • \$\begingroup\$ Is this hard-coded for only 5 islands? \$\endgroup\$
    – Geobits
    Mar 12, 2014 at 0:51
4
\$\begingroup\$

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)
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Using the binary representation is ingenius! Lettercount.com gave you an 85. Did you overcount, or is lettercount a bad tool to use? \$\endgroup\$
    – Rainbolt
    Mar 11, 2014 at 13:01
  • \$\begingroup\$ @Rusher: My tool was using CRLF line endings. Counting it with Unix line endings, it's 85. \$\endgroup\$ Mar 11, 2014 at 14:47
3
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Crashed when provided with input that follows the format provided in the example. \$\endgroup\$
    – Rainbolt
    Mar 10, 2014 at 15:20
  • \$\begingroup\$ @Rusher I updated the answer to work with the exact format used in the question. \$\endgroup\$
    – arshajii
    Mar 10, 2014 at 15:26
  • \$\begingroup\$ 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. \$\endgroup\$
    – Rainbolt
    Mar 10, 2014 at 15:27
2
\$\begingroup\$

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}

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ Mar 11, 2014 at 23:38
  • \$\begingroup\$ Strange, given how it works. I'll take a look tomorrow at the case. \$\endgroup\$
    – DavidC
    Mar 12, 2014 at 1:10
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

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))
\$\endgroup\$
1
  • \$\begingroup\$ You might add a header like #Java - 123 Characters \$\endgroup\$
    – Rainbolt
    Mar 12, 2014 at 14:25
0
\$\begingroup\$

awk - 44 Characters

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

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] + " ");
}
\$\endgroup\$
1
  • 4
    \$\begingroup\$ 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. \$\endgroup\$
    – Rainbolt
    Mar 11, 2014 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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