Wprowadzenie

Deszcz w końcu opadł. Większość ludzkości utonęła z powodu błędu w kodzie @ user12345 . Ocaleni są rozproszeni po całym archipelagu. Komunikacja radiowa jest uruchomiona, a ludzkość jest gotowa do ponownego rozwoju. Bez żadnego powodu piraci zombie zgromadzili się w Prime Meridian i zamiatają na zachód. Horda pożera wszystko.

Problem

Nasz scenariusz zagłady może być opisany przez 5 liczb całkowitych w jednym wierszu, które reprezentują zestaw współpracujących społeczności wyspiarskich. Są one uporządkowane od zachodu (skrajnie po lewej stronie) do wschodu (skrajnie po prawej stronie).

Począwszy od wyspy najbardziej na wschód, wyspiarze uciekają parami na następną najbliższą wyspę. Co ciekawe, dla każdej pary, która wyrusza, tylko jedna z nich przeżyje podróż. Wyspiarze podróżują tylko parami. Dziwne populacje wybierają jedynego mieszkańca, który pozostanie w tyle i zapewni najnowsze wiadomości radiowe na temat wybryków hordy piratów zombie. Populacje odmawiają podróży, dopóki wszystkie wyspy na wschód od nich nie zakończą migracji lub nie umrą. Kiedy ludność dotrze do ostatniej, najbardziej wysuniętej na zachód wyspy, podróż ustaje.

Kierownik operacyjny na końcu świata potrzebuje programu, który może wyprowadzić ostateczną liczbę mieszkańców każdej wioski.

Przykładowe dane wejściowe

3 8 6 0 2

Przykładowy wynik

8 1 0 1 0

Założenia

• Dane wejściowe mogą być dostarczane przez stdin, odczytane z dowolnego pliku lub zaakceptowane jako argument
• Dla każdej wyspy 0 <= populacja <= 1024
• Populacje nigdy nie opuszczają wyspy

Najkrótsza odpowiedź wygrywa!

APL, 16 znaków

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

Dane wejściowe są dostarczane jako ciąg do tego bloku:

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

lub jeden znak mniej, jeśli dane wejściowe podano jako argument do tego bloku:

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

Opiera się na idei Ilmari Karonen w tym komentarzu .

• 2⊥⍵ wykonuje podstawową konwersję 2 danych wejściowych.
• (1e9,4⍴2)⊤w ten sposób konwertuje tę liczbę z powrotem na bazę 2 (dla czterech ostatnich cyfr) i bazę 1e9 dla pierwszej, co wystarcza dla podanych wyżej zakresów wejściowych. ( 1e9,4⍴2buduje listę 1e9 2 2 2 2).

Zauważ, że ucieczka na zachód odbywa się automatycznie przez konwersję bazy podczas tego procesu.

GolfScript, 23 22 znaków

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

Podejście iteracyjne. Tablica jest kilkakrotnie iterowana i za każdym razem liczba par jest przenoszona z prawej do lewej. Wypróbuj przykład online .

Krótkie objaśnienie kodu:

~]       # 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

GolfScript (25 znaków)

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

Demo online

Całkiem proste rozwiązanie: istnieje bardziej interesujące podejście, które definiuje wartość wyjściową dla każdej wyspy jako funkcję wartości wejściowych, ale nie sądzę, że można ją zagrać w golfa tak dalece, jak faktycznie postępuje zgodnie z algorytmem redystrybucji opisanym w pytaniu.

Javascript / ES6 (69)

Gra z operatorami bitowymi:

• x&=1 zachowuje najniższy bit (1 jeśli nieparzysty, 0 jeśli parzysty)
• x>>1 to dzielenie przez 2 dla liczb całkowitych

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

Wersja bez ES6:

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

Przykłady:
f("3 8 6 0 2")zwraca [8, 1, 0, 1, 0]
f("0 997 998 999 1000")zwroty[935, 0, 1, 1, 0]

Python - 96 znaków

Pierwszy raz w golfa! Dane wejściowe ze standardowego wejścia.

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

J (26 znaków)

Oto moje rozwiązanie w 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

To ogólne rozwiązanie powinno działać z dowolną liczbą wysp.

Rubin, 97 90 74 72

Wersja online

Grałem w golfa nieco dalej, nie odwracając już tablicy ...

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

C - 121 znaków

Dane wejściowe są pobierane ze standardowego wejścia.

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;}

Python2 - 98 znaków

Dane wejściowe ze standardowego wejścia.

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 znaków

Dane wejściowe ze standardowego wejścia.

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

Python 2, 85 80 bajtów

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

X osób rozpoczynających na dowolnej wyspie odpowiada X * 2 osobom rozpoczynającym jedną wyspę po prawej stronie. Ten kod konwertuje wszystkich w konfiguracji początkowej na ich odpowiednik w skrajnie prawicowych wyspach, a następnie wykorzystuje binarną reprezentację wyniku, aby określić, ile osób kończy na każdej wyspie.

EDYCJA: Skrócono kod inicjując bdo 1 zamiast 0, umożliwiając użycie binzamiast ciągu formatu.

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

Przewijamy listę od tyłu do przodu i przesuwamy populacje zgodnie ze specyfikacją, a następnie drukujemy listę. Oto szybki 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

Mathematica 105

Powinno to działać z dowolną liczbą wysp.

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]]

Przykłady

5 wysp

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

{8, 1, 0, 1, 0}

25 wysp

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 }

Java - 647 533, ale liczę na punkty brownie dla strumieni Java 8.

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;}}

Nieskompresowana forma:

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);
}

Z pomocą:

// 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();
  }

}

Nieco zaniepokojony, że test @ DavidCarraher:

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

generuje

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

Java - 196 195

Powiedziałem sobie, że nie opublikuję tego, gdybym nie mógł dostać go poniżej 200 ... Szczerze mówiąc, nie sądzę, żebym mógł się pozbyć czegokolwiek innego, jest dość wąski jak na Javę.

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]+" "));}}

Podziały wierszy:

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]+" "));
    }
}

Przykładowe dane wejściowe:

$ 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

Java - 179 znaków

Sprężony:

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);}}

Normalna:

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);
    }
}

Przykładowe dane wyjściowe:

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

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

Emacs Lisp 144 znaków

Nie malutki, ale działa

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

awk - 44 znaki

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

Java - 116 znaków

Na przykład int[] i = {2, 33, 16, 5};(myślę, że te nie dodają się do liczby, ponieważ każda liczba może się różnić) wyszedł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] + " ");
}