title: Hot moo shuffle: milk an array

text:
# Question
Title: Hot moo shuffle: milk an array
## Background

*Milking the deck* is the name given to the following card shuffling method:

1. 'Pinch' the deck to remove the top and bottom cards simultaneously. (With lots of imagination, this action resembles milking a cow.) This pair of cards forms the base of a new pile.
2. Repeat, adding each pair of cards to the top of the new pile, until the whole deck has been used.

**Example**

Suppose we start with a deck of six cards, `[1, 2, 3, 4, 5, 6]` (lower-indexed elements are nearer to the top). Let's milk the deck:

0. `old = [1, 2, 3, 4, 5, 6]`, `new = []`
1. Remove `[1, 6]`: `old = [2, 3, 4, 5]`, `new = [1, 6]`
2. Remove `[2, 5]`: `old = [3, 4]`, `new = [2, 5, 1, 6]`
3. Remove `[3, 4]`: `old = []`, `new = [3, 4, 2, 5, 1, 6]`

After milking, the deck is therefore ordered `[3, 4, 2, 5, 1, 6]`.

## Challenge

Your task in this challenge is to implement the milking operation on a given array and output/return the result. The input array will contain only positive integers, not necessarily distinct. If the input array contains an odd number of elements, then the last milking step transfers only one element (the last one remaining) from the input to the output array.

## Test cases

Input -\> Output

```
[1, 2, 3, 4, 5, 6] -> [3, 4, 2, 5, 1, 6]
[1, 2, 3, 4, 5, 6, 7] -> [4, 3, 5, 2, 6, 1, 7]
[9, 7, 5, 3, 1, 2, 4, 6, 8, 10] -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 1, 2, 1, 2] -> [2, 1, 1, 1, 2]
[] -> []

```

# Answer
# , ~~53~~ ~~50~~ 48 bytes

```
f=function(x,y=rev(x))if(c(y,F))c(f(y[-1]),y[1])

```

Try it online!

Repeatedly takes the bottom card & flips the deck.
> 22 votes

# Answer
# , 36 bytes

```
function(x)rbind(rev(x),x)[-seq(!x)]

```

Try it online!

Takes `integer(0)` (a length 0 integer vector) for empty input.

Stacks the reversed array onto itself, giving something like:

```
     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    7    6    5    4    3    2    1
[2,]    1    2    3    4    5    6    7
```

And then removes the first `n=length(x)` elements, going down the columns, then across the rows.
> 20 votes

# Answer
# Haskell with `-XParallelListComp`, ~~52~~ 49 bytes

```
f l=drop(length l)$id=<<[[x,y]|x<-reverse l|y<-l]

```

Try it online!

# Explanation

This is for my old answer. The only difference is that the riffling has been golfed from a call to `zip` and a flattening step to a parallel list comprehension and a flattening step.

This works by taking two copies of the input deck. You reverse the first copy, then riffle it with the second. Then remove as many cards as there were in the input deck, leaving behind the answer. In the code,

```
f l=drop(length l)$(\(x,y)->[x,y])=<<zip(reverse l)l
                   (\(x,y)->[x,y])=<<zip(reverse l)l  riffling
                                     zip                riffle
                                         reverse l      the reversed deck
                                                   l    the deck
                   (\(x,y)->[x,y])=<<                 flattening
    drop(length l)                                    removing
    drop                                                discard (from top)
         length l                                       length of input

```

The `flattening` portion does as follows. When riffled, the deck looks like `[(6,1),(5,2),(4,3),(3,4),(2,5),(1,6)]` (list of tuples). We "flatten it" to look like `[6,1,5,2,4,3,3,4,2,5,1,6]`.

I remain convinced that this approach might be shorter than the port of Dominic van Essen's answer. I think the `(\(x,y)->[x,y])` function can be shortened or removed, as well as the annoying use of `length`.

# Pointfree Haskell, 61 bytes

Just for fun; I initially thought it would be shorter.

```
foldr(pure tail).((\(x,y)->[x,y])=<<).(zip.reverse<*>id)<*>id

```
> 9 votes

# Answer
# Haskell, ~~38~~, 33 bytes

```
g(x:y)=f y++[x]
g x=x
f=g.reverse

```

Try it online!

**-5 bytes thanks to @Zgarb.**

Very simple port of Dominic van Essen's solution. Go upvote theirs instead.

I was going to put this as a reference to compare to in my other answer, but figured it was more in the spirit of cgcc to submit twice.
> 9 votes

# Answer
# Perl 5 \+ `-p`, 33 bytes

```
$\=" $` $'".$\,$_=$1while/ (.+) /

```

Try it online!

## Explanation

This approach utilises `-p` which allows work on input implicitly, by putting it in `$_` for each line of STDIN and implicitly `print`ing `$_` at the end of the program. `$\` is used as this magic variable is automatically `print`ed after the contents passed to `print`. The main body is a `while` loop that checks if `$_` `m//`atches `(.+)` (a space followed by one or more characters followed by another space), while `$_` does march (`m//` implicitly checks `$_` when not called via `=~`) `$\` is set to a space, the remaining string after the match (`$'`) followed by another space and the preceding string contents before the match (`$`` ), concatenated with the existing contents of `$\`. `$_` is then set to the matched string (excluding the spaces) which is captured in `$1`. At the end of the script, this leaves the central characters (either one or two depending on whether the list has an even or odd number of entries) in `$_`, which is implicitly `print`ed, followed by the content of `$\`, which contains a leading space and the rest of the list "milked".
> 9 votes

# Answer
# 05AB1E, ~~9~~ ~~8~~ 7 bytes

```
Âsø˜2äθ

```

-1 byte thanks to *@Neil*

Try it online or verify all test cases.

Or alternatively, a port of *@DominicVanEssen*'s approach is **7 bytes** as well:

```
vRćˆ}¯R

```

Try it online or verify all test cases.

**Explanation:**

```
Â        # Bifurcate the (implicit) input-list (short for Duplicate & Reverse copy)
         #  i.e. [1,2,3,4,5,6,7] → [1,2,3,4,5,6,7] and [7,6,5,4,3,2,1]
 s       # Swap so the input-list is at the top again
         #  → [7,6,5,4,3,2,1] and [1,2,3,4,5,6,7]
  ø      # Zip/transpose the lists together to create pairs
         #  → [[7,1],[6,2],[5,3],[4,4],[3,5],[2,6],[1,7]]
   ˜     # Flatten it
         #  → [7,1,6,2,5,3,4,4,3,5,2,6,1,7]
    2ä   # Split it into 2 equal-sized parts
         #  → [[7,1,6,2,5,3,4],[4,3,5,2,6,1,7]]
      θ  # Pop and push just the last part
         #  → [4,3,5,2,6,1,7]
         # (after which it is output implicitly as result)

v        # Loop the (implicit) input-list amount of times:
         #   i.e. we'll loop 7 times for input [1,2,3,4,5,6,7]
 R       #  Reverse the list at the top of the stack,
         #  which will use the (implicit) input-list in the first iteration
         #   i.e. [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]
  ć      #  Extract head; pop and push remainder-list and first item separated
         #   → [6,5,4,3,2,1] and 7
   ˆ     #  Pop this first item, and add it to the global array
}¯       # After the loop: push the global array
         #  → [7,1,6,2,5,3,4]
  R      # Reverse it
         #  → [4,3,5,2,6,1,7]
         # (after which it is output implicitly as result)

```
> 8 votes

# Answer
# Python 3, 36 bytes

```
M=lambda a:a and M(a[-2::-1])+a[-1:]

```

Try it online!

Uses Dominic van Essen's approach: repeatedly takes the bottom card and recurses on the reverse of the rest of the deck.
> 8 votes

# Answer
# C (gcc), ~~65~~ ~~62~~ 60 bytes

```
i;f(c,z)int*c;{for(i=0;i||(i=z-=2)>0;)*c^=c[i--]^=*c^=c[i];}

```

Try it online!

The loop iterates backwards from the last - 1 element and swaps it with the first element. Then it restarts iteration two elements backwards until finished.

Saved 3 using loop reset in loop check instead of recursion.

Saved 2 more because `i>0` check is no more needed.

Example

```
1 2 3 4 5 6 7 8 => 4 5 3 6 2 7 1 8
7           1
6.        7
5.      6
4.    5
3.  4
2 3 4 5 6 7 1 8
6       2
5     6
4.  5
3 4 5 6 2 7 1 8
5   3
4 5

```
> 7 votes

# Answer
# Pyth, <sup>~~11~~</sup> 10 bytes

-1 byte thanks to @FryAmTheEggman

```
L&bay_Pbeb

```

port of Dominic van Essen's solution to Pyth.

Try it online!

## Explanation

```
L&bay_Pbeb
L              define function named y with argument b which returns
 &b            short circuiting and of b and
   a    eb     the last element of b appended to
    y          the return value of y when called on
     _         the reverse of
      Pb       b without its last element

```
> 6 votes

# Answer
# APL (Dyalog Classic), 7 bytes

-4 bytes thanks to Ada

-3 bytes thanks to Bubbler

-1 byte thanks to ngn!

```
≢↓∘∊⌽,⍪

```

Try it online!

Port of Kevin Cruijssen's 05AB1E answer and streetster's K solution \- don't forget to upvote them!
> 6 votes

# Answer
# Pyth, 6 bytes

```
ec2.i_

```

Try it online!

Looking through the Pyth documentation reminded me of the interleave function `.i`, which is extremely useful here.

How it works:

* `.i`: Interleave the following two lists:

+ `_`: The reversal of the input (implicit), and
    + The input (implicit).
* `c2`: Split the result in half.
* `e`: Output the second half.
> 6 votes

# Answer
# Python 3, 45 bytes

```
M=lambda a:a and M(a[1:-1])+a[::len(a)-1or 1]

```

Try it online!

Performs milking in the same procedure as specified.
> 5 votes

# Answer
# Brachylog, 10 bytes

Same approach as Dominic van Essen's answer, so upvote that.

```
Ė|tT&k↔↰,T

```

Try it online!

```
Ė|tT&k↔↰,T
Ė          input is an empty list
 |         or
  tT       save the input's last element as T
    &      and
     k     the input without the last element
      ↔    reverse it
       ↰   recursively call this predicate
        ,T and append T

```
> 5 votes

# Answer
# Charcoal, 14 bytes

```
Ｉ⮌Ｅθ§⎇﹪κ²θ⮌θ⊘κ

```

Try it online! Link is to verbose version of code. Works by calculating the reverse of the first half of the flattened zip of the reversed list with itself. Explanation:

```
   θ            Input array
  Ｅ             Map over elements
       κ        Current index
      ﹪ ²       Modulo literal 2
         θ      Input array
     ⎇          If index was odd otherwise
          ⮌     Reverse of
           θ    Input array
    §           Indexed by
             κ  Current index
            ⊘   Halved
 ⮌              Reverse the result
Ｉ               Cast to string
                Implicitly print

```
> 5 votes

# Answer
# K (oK), ~~16~~ 15 bytes

**Solution:**

```
{(#x)_,/|x,'|x}

```

Try it online!

Port of Kevin's solution.

**Explanation:**

```
{(#x)_,/|x,'|x} / the solution
{             } / lambda taking implicit x
            |x  / reverse x
         x,'    / join each with x
        |       / reverse
      ,/        / flatten
     _          / drop
 (  )           / do this together
  #x            / count x

```

**Extra:**

* **-1 byte** thanks to `@ngn`
> 5 votes

# Answer
# C (gcc), ~~88~~ ~~71~~ ~~62~~ ~~60~~ 59 bytes

Saved 9 bytes thanks to ceilingcat!!!

Saved a byte thanks to G. Sliepen!!!

```
t;i;f(l,n)int*l;{for(;n>1;l[n]=t)t=*l,wmemcpy(l,l+1,n-=2);}

```

Try it online!

Inputs a pointer to the array and its length and milks the array in place.

Code actually does the moo-shuffle: tucking the first element away, shifting all but the last down one, and putting the first one just in front of the last. This is repeated, shifting down 2 elements from the end each time, until there are only two elements left and we're done.
> 5 votes

# Answer
# Brainfuck, 64 Bytes

```
,[>,]<[[->>+<<]<[<]>[-<+>]<[->>[>]>+<<[<]<]>>[[-<+>]>]<<]>>>[.>]

```

Try it online!

```
,[>,] Read input array into memory
<[[->>+<<] Move last number of input to the right of the input array
<[<]>[-<+>] Move the first number of input to the left the input array
<[->>[>]>+<<[<]<] Move the number left of the input array to the left side of the number(s) to the right of the input array
>>[[-<+>]>]<<] Move the input array to the left to make some space, then repeat
>>>[.>] Print output array

```
> 5 votes

# Answer
# APL+WIN, 40 bytes

Prompts for input of a vector if indices:

```
(,⊖⍉(2,n)⍴(n↑(-n)↓m),⌽(-n←⌈.5×⍴m)↑m←⎕)~0

```

Try it online! Courtesy of Dyalog Classic

# A simpler approach, 26 bytes

```
m[(-⍴m)↑,⌽⍉n,[.1]⌽n←⍳⍴m←⎕]

```

Try it online! Courtesy of Dyalog Classic
> 4 votes

# Answer
# JavaScript (ES6), 43 bytes

Using a variant of Dominic van Essen's approach:

```
f=(a,x=a.pop())=>x?[...f(a.reverse()),x]:[]

```

Try it online!

---

# JavaScript (ES6),  ~~41~~  40 bytes

If we can take the length of the array as an extra parameter, the following non-recursive algorithm is shorter:

```
n=>a=>a.map((_,k)=>a[n+++n%2*(~k-k)>>1])

```

Try it online!
> 4 votes

# Answer
# GNU sed (`-E`), 54 bytes

```
:l;s/(\w+, )(.* )(\w+.*)\]/\2\]\1\3/;tl;s/\]//;s/$/\]/

```

This assumes the array is passed over stdin as text in exactly the same format as in the problem statement (in particular, whitespace is important).

## Explanation/Example

Let's consider the input `[1, 2, 3, 4, 5, 6]` and look at the script statement-by-statement.

1. `:l`: Create a label called `l` to branch to later.
2. `s/(\w+, )(.* )(\w+.*)\]/\2\]\1\3/`: `[1, 2, 3, 4, 5, 6]` -\> `[2, 3, 4, 5, ]1, 6`.
3. `tl`: did the last `s` command do something? Yes, so branch to `l`.
4. `s/(\w+, )(.* )(\w+.*)\]/\2\]\1\3/`: `[2, 3, 4, 5, ]1, 6` -\> `[3, 4, ]2, 5, 1, 6`.
5. `tl`: did the last `s` command do something? Yes, so branch to `l`.
6. `s/(\w+, )(.* )(\w+.*)\]/\2\]\1\3/`: pattern doesn't match!
7. `tl`: did the last `s` command do something? No, so don't branch.
8. `s/\]//`: `[3, 4, ]2, 5, 1, 6` -\> `[3, 4, 2, 5, 1, 6`.
9. `s/$/\]/`: `[3, 4, 2, 5, 1, 6` -\> `[3, 4, 2, 5, 1, 6]`.

Note that this works for arrays of text consisting of alphanumeric characters or underscores, not just positive integers.

Try it online!
> 4 votes

# Answer
# Japt, 6 bytes

Looking through the rest of the solutions after posting this, I feel like I must be missing something.

```
ÊÆÔvÃÔ

```

Try it or run all test cases

JavaScript "translation":

```
U=>[...Array(U.length)].map(_=>U.reverse().shift()).reverse()

```

```
ÊÆÔvÃÔ     :Implicit input of array U
Ê          :Length
 Æ         :Map range
  Ô        :  Reverse U
   v       :  Remove and return first element
    Ã      :End map
     Ô     :Reverse

```

Mapping the original array *would* be one byte shorter but, as both methods used in the map modify that array, it wouldn't work.
> 4 votes

# Answer
# x86-16 machine code, ~~21~~ 20 bytes

**Binary:**

```
00000000: 8bde 03f1 4e03 f94f fda4 e201 c38a 0743  ....N..O.......C
00000010: aae2 f6c3                                ....

```

**Listing:**

```
8B DE       MOV  BX, SI             ; BX = beginning of input array
03 F1       ADD  SI, CX             ; SI = end of input array
4E          DEC  SI                 ; adjust to last element
03 F9       ADD  DI, CX             ; DI = end of output array
4F          DEC  DI                 ; adjust to last element
FD          STD                     ; set direction flag to descend
        MILKLAST:
A4          MOVSB                   ; write end of input array value to output array
E2 01       LOOP MILKFIRST          ; if not end of array, move first value
C3          RET                     ; otherwise, return to caller
        MILKFIRST:
8A 07       MOV  AL, BYTE PTR[BX]   ; AL = start of input array value
43          INC  BX                 ; increment pointer
AA          STOSB                   ; write to output array
E2 F6       LOOP MILKLAST           ; loop until end of array
C3          RET                     ; return to caller

```

Callable function, input array in `[SI]`, length in `CX`. Output array to buffer at `[DI]`.

**Tests using DOS DEBUG:**
> 4 votes

# Answer
# Husk, 8 bytes

```
↓L¹Σze↔¹

```

Try it online!

```
↓L¹Σze↔¹
    z     Zip
      ↔¹  the list with its reverse
     e    into a list of 2 elements
   Σ      Flatten it
↓         Drop
 L¹       the first n elements

```
> 4 votes

# Answer
# Keg, 34 bytes

```
÷(!½;|")!2%[!1>[$]. ,]{!|$(2|. ,)'

```

Try it online!

+5 due to bug fix
> 3 votes

# Answer
# Io, 53 bytes

Port of @Neil's Charcoal answer.

```
method(x,x map(i,v,x at(if(i%2>0,i,-i-1)>>1))reverse)

```

Try it online!

# Io, 68 bytes

Port of @DominicvanEssen's answer.

```
f :=method(x,if(x size>0,list(x pop,f(x reverse))reverse flatten,x))

```

Try it online!
> 3 votes

# Answer
# Scala 3, ~~46~~ 45 bytes

It appears @cole already had the same answer in Haskell, so you should upvote that.

```
| =>(|reverse)zip|flatMap(Seq(_,_))drop|.size

```

Please forgive the name `|`. I did it to save a byte.

Try it online

# Scala 2, ~~57~~ ~~55~~ ~~54~~ 51 bytes

```
| =>(|reverse,|).zipped.flatMap(Seq(_,_))drop|.size

```

Same thing, but needed the parameter to be a single tuple instead of having 2 parameters.

Try it online

Ungolfed:

```
s => s.reverse.zip(s).flatMap{ case(a,b) => List(a,b) }.drop(s.size)

```

And a recursive solution, just because (71 bytes):

```
def*(l:List[Int]):List[Int]=if(l.size<2)l else*(l.init.reverse):+l.last

```

Try it online
> 3 votes

# Answer
# Dyalog APL, 28 bytes

```
{⍵≡⍬:⍬⋄0~⍨(∇¯1↓1↓⍵),¯2↑1⌽⌽⍵}

```

Try it online!
> 3 votes

# Answer
# C# (Visual C# Interactive Compiler), 102 bytes

```
IEnumerable<int>f(int[]o)=>o.Length==0?new int[0]:o.Length==1?o:f(o[1..^1]).Concat(new[]{o[0],o[^1]});

```

Try it online!
> 3 votes

# Answer
# Wolfram Language (Mathematica), 36 bytes

```
f@a___:=a
f[a_,b__,c_]:=##&[f@b,a,c]

```

Try it online!

Boring, but less boring approaches seem to be more verbose. Returns a `Sequence` containing the deck.
> 3 votes

# Answer
# Clojure, 40 bytes

```
#(drop(count %)(mapcat vector(rseq %)%))

```

Try it online!
> 3 votes

# Answer
# Brachylog, 7 bytes

```
↔;?zcḍt

```

Try it online!

### Explanation

Same idea as Kevin's 05AB1E answer (the first one). Suppose the input list is `[1,2,3,4,5]`:

```
↔        Reverse                      [5,4,3,2,1]
 ;?      Pair with the input again    [[5,4,3,2,1],[1,2,3,4,5]]
   z     Zip                          [[5,1],[4,2],[3,3],[2,4],[1,5]]
    c    Concatenate sublists         [5,1,4,2,3,3,2,4,1,5]
     ḍ   Split into two halves        [[5,1,4,2,3],[3,2,4,1,5]]
      t  Take the second half         [3,2,4,1,5]

```
> 3 votes

# Answer
# Jelly, 7 bytes

```
ṖṚ$ƬZṪ€

```

A monadic Link accepting a list which yields the shuffled list.

**Try it online!**

### How?

```
ṖṚ$ƬZṪ€ - Link: list, A
   Ƭ    - apply & collect while different - i.e. [A, f(A), f(f(A)), ..., []]
  $     -   last two links as a dyad:
Ṗ       -     remove the rightmost item
 Ṛ      -     reverse
    Z   - transpose the (ragged) result
     Ṫ€ - last item of each

```

---

A couple of alternative approaches which are longer:

1. sort the indices by their absolute difference from the centre and index back into the list: `JạÞL‘HƊị`
2. use the beauty of the factorial number system and its relation to the sort order of permutations: `J’:2ṚÆ¡‘œ?`
> 2 votes

# Answer
# , 15 bytes

```
#}.],/@|:@,:~|.

```

Try it online!

Port of Kevin Cruijssen's 05AB1E answer and streetster's K solution \- don't forget to upvote them!
> 2 votes

# Answer
# Ruby, ~~38~~ ~~37~~ bytes 34 bytes

```
f=->x{(b=x.pop)?f[x.reverse]<<b:x}

```

Try it online!

-3 bytes thanks to @Dingus

Uses Dominic van Essen's approach: repeatedly takes the bottom card and recurses on the reverse of the rest of the deck.
> 2 votes

# Answer
# T-SQL, 46 bytes

Input is a table variable

```
DECLARE @ table(v int,i int identity(1,2))
INSERT @ values(1),(2),(3),(4),(5),(6)

SELECT v
FROM @
ORDER BY abs(sum(1)over()-i),i

```

**Try it online**
> 2 votes

# Answer
# Vyxal, 7 bytes

```
(Ṙḣ)WṘ'

```

Try it Online!
> 2 votes

# Answer
# Red, 60 bytes

```
func[b][reverse collect[while[[]<> b][keep take reverse b]]]

```

Try it online!

Inspired by Dominic van Essen's R solution
> 1 votes

# Answer
# Japt `-Q -m`, ~~17~~ 16 bytes

```
[UoUÊ/2 ,U]Õcf w

```

Try it

```
[UoUÊ/2            take the last half elements( reversed )
        ,U]        and the remaining
           Õ       transpose
            cf      flatten after removing null
               w   reverse

```

Flags used for pretty output
> 1 votes

# Answer
# Thunno 2 `t`, 5 bytes

```
r$I2Ẇ

```

Try it online!

#### Explanation

```
r$I2Ẇ  # Implicit input
r      # Reverse the input
 $     # Push the input again
  I    # Interleave them
   2Ẇ  # Split into two
       # Leave only the last part
       # Implicit output

```
> 1 votes

---
Tags: code-golf, array
---


title: CahartcreS awppnig (Character Swapping)

text:
# Question
Title: CahartcreS awppnig (Character Swapping)
## Intro/Background

I was looking at "You Had One Job" pictures lately, and noticed an old favourite of mine:

And I said to myself: "I need a program that can generate text like that". So I devised a set of rules for character swapping and wrote a CGCC challenge!

## The Challenge

Given a single string as input, output a string with its inner characters swapped. This can be done by:

* Leaving the first letter as is
* Swapping each pair of characters thereafter
* Leaving the last letter as is. If the string is of an odd length (i.e. the length of the string mod 2 is 1), leave the last two letters as they are.

## Example Inputs/Outputs

```
School -> Shcool
Somebody -> Smobedoy
Character -> Cahartcer
CGCC -> CCGC
Stack Exchange! -> SatkcE cxahgne!
Never gonna give you up -> Nvereg noang vi eoy uup

```

Walkthrough on swapping

```
School (Length: 6)
S
 hc
   oo
     l
Shcool

Somebody (Length: 8)
S
 mo
   be
     do
       y
Smobedoy

Character (Length: 9)
C
 ah
   ar
     tc
       er
Cahartcer

Stack Exchange! (Length: 15)
S
 at
   kc
     E
       cx
         ah
           gn
             e!
SatkcE cxahgne!

```

## Rules

* Input/output can be taken/given in any convenient format
* The input will not contain newlines
* Minimum input length is 4
* Input will only contain printable ASCII characters

## Scoring

This is , so the answer with the lowest bytes wins.

*Sorry about the last test case everyone. It's fixed now*

# Answer
# Haskell, 31 bytes

```
f(a:b:c:d:e)=a:c:f(b:d:e)
f x=x

```

Try it online!

Avoids having to special-case omitting the first character by having extracting it be part of the recursive definition.
> 31 votes

# Answer
## brainfuck, 28 bytes

```
,.,[>,>,[<.[-]<.>>>]<<[.>]>]

```

Try it online!

First, we print the first character. Then we read the second character and enter the main loop. (`,.,[`)

When entering the main loop, we expect the first character of a pair to be in the current cell, and we read the next two into the next two cells (`>,>,`). The tape then looks like this:

```
[pair1] [pair2] [nextpair1] [0]
                     ^

```

Then, if `nextpair1` exists, we know there's going to be at least one character after the current pair, so we can output the two characters in this current pair in reverse (`[<.[-]<.>>>]`) – the triple `>` at the end moves us to the location after `nextpair1` to break out of the loop. Otherwise, we're at the end of the string, so we go back to `pair1` (`<<`) and print as many characters as we received in order (`[.>]`).

The main loop will end here if this was the end of the string (`>]`). If not, recall that we ended at the `[0]` in the diagram above after the check to see if `nextpair1` existed. So the `<<[.>]` would have brought the pointer to `pair2` (which was cleared) instead of `pair1`, and then `>]` restarts the main loop, but with the cursor pointing at `nextpair1`, which is exactly what we want.
> 29 votes

# Answer
# Retina, 12 bytes

```
V`^.|..(?=.)

```

Try it online! Link includes test cases. Explanation: `V` reverses each match. The first character is matched separately, then characters are matched in pairs as long as there is still one character left that is unreversed.
> 10 votes

# Answer
# Jelly, ~~8~~ 7 bytes

```
Ḣ,Ṫjṭ2/

```

Try it online!

A full program taking a string as its argument and printing the swapped string. Thanks to @JonathanAllan for saving a byte!

## Explanation

```
Ḣ       | Head
 ,Ṫ     | Paired with tail
   j    | Join with:
    ṭ2/ | The remainder, pair wise reduced by tacking the left item in the pair to the end of the right

```
> 10 votes

# Answer
# Python 2, 49 bytes

```
f=lambda s:s[3:]and s[:3:2]+f(s[1:5:2]+s[4:])or s

```

Try it online!

Based off my Haskell answer. I tried a more direct port using splatted input, but it was clunky:

**57 bytes**

```
f=lambda a,b,c,*d:d[1:]and a+c+f(b,*d)or a+b+c+''.join(d)

```

Try it online!
> 7 votes

# Answer
# APL (Dyalog Extended), ~~27~~ 20 bytesSBCS

Anonymous tacit prefix function. Requires `⎕IO←0`.

```
⊢⊇⍨∘⍋≢⌊1+⍳∘≢+2×2|⍳∘≢

```

Try it online!

Explanation and walk-through for `"Somebody"` and `"Character"`:

`⍳∘≢` the indices of the length; `[0,1,2,3,4,5,6,7]`, `[0,1,2,3,4,5,6,7,8]`

`2|` two-mod of that; `[0,1,0,1,0,1,0,1]`, `[0,1,0,1,0,1,0,1,0]`

twice that; `[0,2,0,2,0,2,0,2]`, `[0,2,0,2,0,2,0,2,0]`

`⍳∘≢+` add the indices of the length to that; `[0,3,2,5,4,7,6,9]`, `[0,3,2,5,4,7,6,9,8]`

`1+` increment that; `[1,4,3,6,5,8,7,10]`, `[1,4,3,6,5,8,7,10,9]`

`≢⌊` the minimum of the length and that; `[1,4,3,6,5,8,7,8]`, `[1,4,3,6,5,8,7,9,9]`

the grade (the indices that would sort it) of that; `[0,2,1,4,3,6,5,7]`, `[0,2,1,4,3,6,5,7,8]`

`⊢⊇⍨∘` use that to reorder the string; `"Smobedoy"`, `"Cahartcer"`
> 6 votes

# Answer
# Perl 6 `-p`, 26 bytes

```
s:g[^.||)>..$||..]=$/.flip

```

Try it online!
> 5 votes

# Answer
# Ruby, 42 bytes

```
f=->s{s[/(.)(.)(.)(.+)/]?$1+$3+f[$2+$4]:s}

```

Try it online!
> 4 votes

# Answer
# Brain-Flak, ~~48~~ 40 bytes

```
({}<{({}<({}<>)>)<>}<>{{({}<>)<>}{}}<>>)

```

Try it online!

This doesn't work for strings that contain null bytes (unless the null byte is the first byte of the string).

## Explanation

```
({}<...>) Store the first element for later
  {({}<({}<>)>)<>}... Move the stack over in twos (preserving the order of each pair moved)
    <>{...{}}<>
      {({}<>)<>} Move everything back in ones

```

The one complex part is the `<>{...{}}<>`. Since moving over in twos can pick up an extra zero from the bottom of the stack we need to removing when bringing things back. Conveniently our main loop will stop when it hits a zero, so when it hits a zero we destroy that zero and, if the next thing is not zero we try again.

This means we will only stop if there are two zeros in a row, which since the input cannot contain zeros, will only occur at the bottom of the stack. In the process we will get rid of any zeros that are present, which fixes our extra zero issue.

# Works for all inputs, ~~114~~ 112 bytes

```
({}<([](())){({}[()]<(()[{}])>)}({}{}<([]){{}({}<({}<>)>)<>([])}>{}<>){(<{}({}<{}>)>)}{}([]){{}({}<>)<>([])}<>>)

```

Try it online!

Nearly all of the code is devoted to making this work for even length inputs.
> 4 votes

# Answer
# C++ (clang), ~~117~~ ... ~~82~~ 80 bytes

```
#import<map>
#define f(s)for(int i=1;i<s.size()-2;)s[i++]^=s[i++]^=s[i+1]^=s[i];

```

Try it online!

Saved 11 bytes thanks to @AZTECCO!!!
Saved 2 bytes thanks to @ceilingcat!!!
> 4 votes

# Answer
# Haskell, 40 bytes

```
f(a:b:c:d)=b:a:f(c:d)
f x=x
g(a:b)=a:f b

```

Try it online!

xnor has a shorter version of this answer that combines `f` and `g` into a single function.
> 3 votes

# Answer
# Python 3, 62 bytes

```
lambda x:x[0]+re.sub("(.)(.)",r"\2\1",x[1:-1])+x[-1]
import re

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 14 bytes

```
¦¨2ô€RJ¹θ¹н.ÁJ

```

Try it online!

```
¦¨2ô€RJ¹θ¹н.ÁJ
¦¨             # Delete the first and last letter
  2ô           # Break into groups of 2
    €R         # Reverse each of them
      J        # Join it back together
       ¹θ¹н    # Push the last and first letter of the input
           .Á  # Rotate stack, so the first letter is first
             J # Join the items in the stack

```
> 3 votes

# Answer
# Japt, 11 bytes

```
h1Ué ¤ò mÔq

```

Try it

```
h1Ué ¤ò mÔq     :Implicit input of string U
h1              :Overwrite from the 1st (0-indexed) character on with
  Ué            :  Rotate U to the right
     ¤          :  Slice off the first 2 characters
      ò         :  Split into pairs
        m       :  Map
         Ô      :    Reverse
          q     :  Join

```
> 3 votes

# Answer
# Ruby -pl, 27 bytes

```
gsub /^.|..(?=.)/,&:reverse

```

Try it online!

**Alternate solution with the same bytecount, but a regex nobody else has used yet:**

```
gsub /(^|.)(.(?=.))/,'\2\1'

```

Try it online!
> 3 votes

# Answer
# , ~~24~~ 19 bytes

```
C.~[:}:_2<@|.\#\@}.

```

Try it online!

Creates the boxed indexes representing the cyclic form of the permutation we need (bookeeping), and then applies it `C.` to the input.
> 2 votes

# Answer
# JavaScript (Node.js), 40 bytes

```
f=s=>s[3]?s[0]+s[2]+f(s[1]+s.slice(3)):s

```

Try it online!

# JavaScript (Node.js), ~~41~~ 40 bytes

-1 bytes thanks to Arnauld

```
s=>s.replace(/(?!^)(.)(.)(?=.)/g,"$2$1")

```

Try it online!
> 2 votes

# Answer
# Gema, 15 characters

```
\A?=?
??\P?=$2?

```

The only interesting point here is the use of

> `\P` Position -- leave input stream here after the template matches

Sample run:

```
bash-5.0$ echo -n 'School' | gema '\A?=?;??\P?=$2?'
Shcool

```

Try it online! | Try all test cases online!
> 2 votes

# Answer
# C (clang), ~~51~~ 48 bytes

```
f(char*s,z){*++s^=*s^=s[1]^=*++s;z>5&&f(s,z-2);}

```

Try it online!

A recursive solution that modifies the original string

Saved 3 thanks to @ceilingcat suggestion to use `^=`
> 2 votes

# Answer
# Python 3, 57 bytes

```
def f(s):s[1:-2:2],s[2:-1:2]=s[2:-1:2],s[1:-2:2];return s

```

Try it online!

Accepts a list and returns a list.

The idea is to simply take the alternating slices and swap them.

Do let me know if the boilerplate stuff can be shortened in Python submissions.
> 2 votes

# Answer
# x86-16 machine code, 13 bytes

Unassembled listing:

```
 46         INC  SI         ; skip first char
 8B FE      MOV  DI, SI     ; point DI to string
 D1 E9      SHR  CX, 1      ; divide counter by 2 with round down
 49         DEC  CX         ; skip last char
        CLOOP:
 AD         LODSW           ; load next two chars
 86 E0      XCHG AH, AL     ; reverse chars
 AB         STOSW           ; store next two chars
 E2 FA      LOOP CLOOP      ; keep looping
 C3         RET             ; return to caller

```

Input/output string in `[SI]`, length in `CX`.

**PC-DOS test program output:**
> 2 votes

# Answer
# Burlesque, 17 bytes

```
rt2cog_j)<-++.+RT

```

Try it online!

```
rt  # Rotate the string left
2co # Split into chunks of 2
g_j # Take pair of first and last out
)<- # Reverse each chunk
++.+# Join everything back together
RT  # Rotate the string right

```

For even length input only you can shave a single character:

```
RT2col_)<-++.+RT

```
> 2 votes

# Answer
# Fortran (GFortran), 125 bytes

```
character(99)a,b(99)
read('(a)'),a
j=len_trim(a)
b=[a(1:1),(a(i+1:i+1),a(i:i),i=2,j-1,2),a(j:j)]
print*,(b(i)(1:1),i=1,j)
end

```

Try it online!

Shame string manipulation in Fortran is so wordy as every substring needs two references. The main magic is mapping a to a character array via:

```
[a(1:1),            ! Prepend first char
(a(i+1:i+1),a(i:i), ! Swap a(i+1) for a(i)
  i=2,j-1,2)        ! For i in 2..n-1
,a(j:j)]            ! Append last char

```
> 2 votes

# Answer
# , 48 bytes

Man, I love J

```
(1{.]),([:,[:(|."1)_2[\1}.]}.~_1-2|#),]{.~_1-2|#

```

Try it online!
> 2 votes

# Answer
# Zsh, ~~74~~ 71 bytes

Found a more idiomatic `Zsh` solution. Try it online!

```
w=$1;printf $w[1]${w[2,$#w-1]//(#m)(?)(?)/$MATCH[2]$MATCH[1]}${w:$#w-1}

```

74 bytes: `w=$1;printf $w[1];for i ({2..$[$#w-2]..2})printf $w[i+1]$w[i];<<<${w:$i+1}`
> 2 votes

# Answer
# SNOBOL4 (CSNOBOL4), 104 bytes

```
 P =LEN(1)
 INPUT P . F REM . S
S S P . X P . Y REM . S
 F =F Y X
 GT(SIZE(S),2) :S(S)
O OUTPUT =F S
END

```

Try it online!
> 1 votes

# Answer
# Charcoal, 20 bytes

```
§θ⁰Ｆ⪪✂θ¹±¹¦¦¦²⮌ι§θ±¹

```

Try it online! Link is to verbose version of code. Works with strings of at least 2 characters. Explanation:

```
§θ⁰

```

Print the first character of the string.

```
Ｆ⪪✂θ¹±¹¦¦¦²

```

Split the inner slice of the string into 2-character substrings.

```
⮌ι

```

Print each substring reversed.

```
§θ±¹

```

Print the last character of the string.
> 1 votes

# Answer
# Pip, ~~17~~ 15 bytes

```
a@-,2JWVRVUWTMa

```

Try it online!

~~Seems like there's gotta be a shorter way, but I haven't found it yet.~~ Well, this is a bit shorter. Also, I think it's the longest run of capital-letter builtins I've ever used. :^P

### Explanation

```
a@-,2JWVRVUWTMa
   ,2            Range(2): [0; 1]
  -              Negate: [0; -1]
a@               Use those values to index into the input string, giving a list
                 containing the first and last characters
     J           Join that list on the following expression:
              a  The input string
            TM   With first and last characters trimmed off
          UW     Unwoven into a list of two strings: the characters at even indices, and
                 the characters at odd indices
        RV       Reverse, putting the string of odd-indices characters first
      WV         Weave back together

```

Worked example with input `abcdefg`:

```
a                "abcdefg"
 @-,2            ["a" "g"]
            TMa  "bcdef"
          UW     ["bdf" "ce"]
        RV       ["ce" "bdf"]
      WV         "cbedf"
     J           "acbedfg"

```
> 1 votes

# Answer
# Red, ~~95~~ 76 bytes

```
func[s][prin take s t: take/last s
foreach[a b]s[prin any[b""]prin a]prin t]

```

Try it online!

Directly prin(t)s the characters instead of returning a string.
> 1 votes

# Answer
# Java (JDK), 43 bytes

```
s->s.replaceAll("(?<=.)(.)(.)(?=.)","$2$1")

```

Try it online!

# Without much API, 60 bytes

```
s->{for(int i=1;i<s.length-2;)s[i]^=s[++i]^(s[i]=s[i++-1]);}

```

Try it online!
> 1 votes

# Answer
# Keg, 16 bytes (SBCS)

The same program as below, with extra simplifying-ops added.

```
,(!½!2%¬-|$,,)(,

```

Try it online!

# Keg `-ir`, 18 bytes

You know, Jono's challenges are *definitely* easily doable in Keg.

```
,(!2/1!2%--|$,,)(,

```

Try it online!

## Explanation

```
                   # Take an input from STDIN
,                  # Step 1. Output the first item.
 (!2/              # Repeat half of the length-of-stack times
     1!2%--        # subtract by 1 if that's odd
           |$,,    # Swap & output the two items
               )(, # Output the remaining items

```
> 1 votes

# Answer
# Wren, 73 bytes

Did some simple optimizations

```
Fn.new{|x|x[0]+(1..x.count-3).map{|y|x[y%2==0?y-1:y+1]}.join()+x[-2..-1]}

```

Try it online!
> 1 votes

# Answer
# Emacs, 7 keystrokes

```
C-f <f3> C-f C-t M-0 <f4> C-/

```

or 9 keystrokes without fn-keys

```
C-f C-x ( C-f C-t M-0 C-x ) C-/

```

`C-f` move forward one character

`<f3>` start keyboard macro

`C-f`

`C-t` transpose the character under the cursor with the one before it

`M-0` call the next command with numeric argument 0

`<f4>` run this macro and end definition, with argument 0, this macro is run indefinitely until a break occurs, i.e. when `C-f` goes past the last character

`C-/` undo the last change, i.e. the last transpose, so that the end condition is fulfilled; this saves some keystrokes over vim because `u` undo after a recursive macro call undos all the runs of the macro instead of the last change
> 1 votes

# Answer
# Rust, 52 bytes

```
|s:&mut[u8]|for i in 1..s.len()/2{s.swap(2*i-1,2*i)}

```

Try it online!

An anonymous function, takes a mutable reference to a bytestring and mutates it in place.
> 1 votes

# Answer
# Brachylog, 12 bytes

```
~bġ₂↔ᵐ↔ᵗ↔ʰcb

```

Try it online!

Doesn’t feel like a very efficent use of bytes…

### Explanation

```
~b              Append an unknown character at the beginning of the input
  ġ₂            Split the input into groups of 2 characters
    ↔ᵐ          Reverse the order of the 2 characters for all groups
      ↔ᵗ        Reverse again only for the last one
        ↔ʰ      Reverse again only for the first one
          c     Concatenate into a string again
           b    Behead: remove the unknown character

```

The way `ġ₂` works is that it will construct groups of 2 consecutive characters from left to right, so we need to pair the first character with something random, to avoid it getting swapped with the second character. If the length of the string is even, then the last group will only have 1 character instead of 2 (since we added a random character), instead of having the predicate fail. The rest of the program ( etc.) works as expected on a group of only one character.
> 1 votes

# Answer
# Forth (gforth), 67 bytes

```
: f 2dup 1 -3 d+ bounds do i 1+ c@ i c@ i 1+ c! i c! 2 +loop type ;

```

Try it online!

Overwrites the input string

### Code Explanation

```
: f          \ start a new word definition
  2dup       \ make a copy of the string address and length
  1 -3 d+    \ add 1 to address and subtract 3 from length (skip first and last)
  bounds     \ get the starting and ending address of shortened string
  do         \ loop from addr+1 to addr+length-3
    i 1+ c@  \ get value at next char
    i c@     \ get value at current char
    i 1+ c!  \ write current char to next char
    i c!     \ write next char to current char
  2 +loop    \ end loop, move 2 chars ahead
  type       \ output string (using copied address & length)
;            \ end word definition

```
> 1 votes

# Answer
# Perl 5, 26 bytes

```
s/(?<=.)(.)(.)(?=.)/$2$1/g

```

Try it online!

Look-behind and look-ahead to the rescue.
> 1 votes

# Answer
# C# (Mono), 212 bytes

```
using System;class b{static void Main(string[] z){var s=z[0];Action<string>w=Console.Write;w(s[0].ToString());int i;var l=s.Length;for(i=2;i<=l-2;i+=2)w(new string(new char[]{s[i],s[i-1]}));w(s.Substring(i-1));}}

```

Try it online!

Because why not?
> 1 votes

# Answer
# Vyxal , 6 bytes

```
ḣ2ẇR÷Ṙ

```

Try it Online!

Note that the test suite simulates the  flag.

-3 thanks to lyxal
> 1 votes

# Answer
# Ly, 19 bytes

```
ispro[y,[pfo0]po]lo

```

Try it online!

```
ispro[y,[pfo0]po]lo
isp                  # Read input onto the stack, stash the last char and delete it
   ro                # Reverse the stack, print the first char
     [          ]    # Loops until the stack is empty
      y,             # Push the stack length and decrement by 1
        [p  0]p      # If-then, code runs if there's 2+ entries on the stack
          fo         # Flip the top two entries and print the top of stack
               o     # Print the top of the stack
                 lo  # Restore the "last char" from back cell and print

```
> 1 votes

# Answer
# Thunno 2 `j`, 7 bytes

```
Ṫsḣ²ṃ$h

```

Try it online!

#### Explanation

```
Ṫsḣ²ṃ$h  # Implicit input
Ṫs       # Extract the last character
  ḣ      # Remove the first character
   ²     # Break into pairs
    ṃ    # Reverse each inner pair
     $h  # Push the first character
         # of the input again
         # Join the stack into a string
         # Implicit output

```
> 1 votes

---
Tags: code-golf, string
---


title: Compute the Adler-32 checksum

text:
# Question
Title: Compute the Adler-32 checksum
### Background

Adler-32 is a 32-bit checksum invented by Mark Adler in 1995 which is part of the widely used zlib library (also developed by Adler). Adler-32 is not as reliable as a 32-bit cyclic redundancy check, but – at least in software – it is much faster and easier to implement.

### Definition

Let **B = \[b1, ⋯, bn\]** be a byte array.

The Adler-32 checksum of **B** is defined as the result of **low + 65536 × high**, where:

* **low := ((1 + b1 \+ ⋯ + bn) mod 65521)**
* **high := (((1 + b1) + (1 + b1 \+ b2) + ⋯ (1 + b1 \+ ⋯ + bn)) mod 65521)**

### Task

Given a byte array as input, compute and return its Adler-32 checksum, abiding to the following.

* You can take the input as an array of bytes or integers, or as a string.

In both cases, only bytes corresponding to printable ASCII characters will occur in the input.

You may assume that the length of the input will satisfy **0 \< length ≤ 4096**.
* If you choose to print the output, you may use any positive base up to and including 256.

If you choose unary, make sure interpreter can handle up to **232 \- 983056** bytes of output on a machine with 16 GiB of RAM.
* Built-ins that compute the Adler-32 checksum are forbidden.
* Standard rules apply.

### Test cases

```
String:     "Eagles are great!"
Byte array: [69, 97, 103, 108, 101, 115, 32, 97, 114, 101, 32, 103, 114, 101, 97, 116, 33]
Checksum:   918816254

String:     "Programming Puzzles & Code Golf"
Byte array: [80, 114, 111, 103, 114, 97, 109, 109, 105, 110, 103, 32, 80, 117, 122, 122, 108, 101, 115, 32, 38, 32, 67, 111, 100, 101, 32, 71, 111, 108, 102]
Checksum:   3133147946

String:     "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
Byte array: [126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126]
Checksum:   68095937

String:     <1040 question marks>
Byte array: <1040 copies of 63>
Checksum:   2181038080

```

# Answer
> 4 votes
# Jelly, ~~19~~ 17 bytes

```
+\,S‘S€%65521ḅ⁹²¤

```

Try it online!

```
+\,S‘S€%65521ḅ⁹²¤    Main monadic chain. Takes array as only argument.

                     The array is shown here as [b1 b2 ... bn].
+\                   Reduce by addition (+) while returning immediate results.
                         yields [b1 b1+b2 ... b1+b2+...+bn].

  ,                  Concatenate with...
   S                 the sum of the argument.
                         yields [[b1 b1+b2 ... b1+b2+...+bn] b1+b2+...+bn].

    ‘                Increment [each].
                         yields [[1+b1 1+b1+b2 ... 1+b1+b2+...+bn] 1+b1+b2+...+bn].

     S€              Sum each list.
                         yields [[1+b1+1+b1+b2+...+1+b1+b2+...+bn] 1+b1+b2+...+bn].

       %65521        Modulo [each] by 65521.

             ḅ⁹²¤    Convert from base    65536    to integer.
              ⁹                        256
               ²                           squared

```

# Answer
> 66 votes
# Mathematica, 46 bytes

```
{1,4^8}.Fold[##+{0,#&@@#}&,{1,0},#]~Mod~65521&

```

An anonymous function that takes an integer array and returns the Adler-32, with some improvements from miles and Martin (see comments).

miles' is also **46 bytes**, but faster:

```
{1,4^8}.{Tr@#+1,Tr[Accumulate@#+1]}~Mod~65521&

```

# Answer
> 13 votes
# Julia, ~~73~~ 46 bytes

```
x->[sum(x)+1;sum(cumsum(x)+1)]%65521⋅[1;4^8]

```

This is an anonymous function that accepts an array and returns an integer. To call it, assign it to a variable.

We combine `sum(x) + 1` and `sum(cumsum(x) + 1)` into an array, where `x` is the input array, and take each modulo 65521. We then compute the dot product with 1 and 48, which gives us `(sum(x) + 1) + 4^8 * sum(cumsum(x) + 1)`, which is exactly the Adler-32 formula.

Try it online! (Includes all test cases)

Saved 27 bytes thanks to Sp3000 and Dennis!

# Answer
> 11 votes
# x86-64 machine code function: ~~33~~ 32 bytes (or ~~31~~ 30 bytes with an `int[]` input instead of `char[]`)

# x86-32 machine code function: 31 bytes

**As a GNU C inline-asm code fragment: saves ~~2B~~ 1B (just the `ret` insn).**

## Commented source and test driver on github

The 64bit version is callable directly from C with the standard System V x86-64 ABI (using 2 dummy args to get args in the regs I want). Custom calling conventions are not uncommon for asm code, so this is a bonus feature.

32bit machine code saves 1B, because merging the high and low halves with `push16/push16 => pop32` only works in 32bit mode. A 32bit function would need a custom calling convention. We shouldn't hold that against it, but calling from C needs a wrapper function.

After processing 4096 `~` (ASCII 126) bytes, `high = 0x3f040000, low = 0x7e001`. So `high`'s most-significant bit isn't set yet. My code takes advantage of this, sign-extending `eax` into `edx:eax` with `cdq` as a way of zeroing `edx`.

```
# See the NASM source below
0000000000401120 <golfed_adler32_amd64>:
  401120:       31 c0                   xor    eax,eax
  401122:       99                      cdq
  401123:       8d 7a 01                lea    edi,[rdx+0x1]
0000000000401126 <golfed_adler32_amd64.byteloop>:
  401126:       ac                      lods   al,BYTE PTR ds:[rsi]
  401127:       01 c7                   add    edi,eax
  401129:       01 fa                   add    edx,edi
  40112b:       e2 f9                   loop   401126 <golfed_adler32_amd64.byteloop>
000000000040112d <golfed_adler32_amd64.end>:
  40112d:       66 b9 f1 ff             mov    cx,0xfff1
  401131:       92                      xchg   edx,eax
  401132:       99                      cdq
  401133:       f7 f1                   div    ecx
  401135:       52                      push   rdx
  401136:       97                      xchg   edi,eax
  401137:       99                      cdq
  401138:       f7 f1                   div    ecx
  40113a:       66 52                   push   dx      # this is the diff from last version: evil push/pop instead of shift/add
  40113c:       58                      pop    rax
  40113d:       66 5a                   pop    dx
  40113f:       c3                      ret
0000000000401140 <golfed_adler32_amd64_end>:

```

`0x40 - 0x20` = 32 bytes.

---

## Commented NASM source:

tricks:

* `xchg eax, r32` is one byte; cheaper than mov. 8086 needed data in ax for a lot more stuff than \>= 386, so they decided to spend a lot of opcode-space on the now-rarely-used `xchg ax, r16`.
* Mixing push64 and push16 for merging high and low into a single register saves reg-reg data movement instructions around two `div`s. The 32bit version of this trick works even better: `push16 / push16 / pop32` is only 5B total, not 6.

Since we push/pop, this isn't safe for inline asm in the SysV amd64 ABI (with a red zone).

```
golfed_adler32_amd64_v3:   ; (int dummy, const char *buf, int dummy, uint64_t len)

    ;; args: len in rcx,  const char *buf in rsi
    ;; Without dummy args, (unsigned len, const char *buf),  mov ecx, edi is the obvious solution, costing 2 bytes

    xor     eax,eax         ; scratch reg for loading bytes
    cdq                     ; edx: high=0
    lea     edi, [rdx+1]    ; edi: low=1
    ;jrcxz  .end            ; We don't handle len=0.  unlike rep, loop only checks rcx after decrementing
.byteloop:
    lodsb                   ; upper 24b of eax stays zeroed (no partial-register stall on Intel P6/SnB-family CPUs, thanks to the xor-zeroing)
    add     edi, eax        ; low += zero_extend(buf[i])
    add     edx, edi        ; high += low
    loop   .byteloop
.end:
    ;; exit when ecx = 0, eax = last byte of buf
    ;; lodsb at this point would load the terminating 0 byte, conveniently leaving eax=0

    mov     cx, 65521       ; ecx = m = adler32 magic constant.  (upper 16b of ecx is zero from the loop exit condition.  This saves 1B over mov r32,imm32)
    ;sub    cx, (65536 - 65521) ; the immediate is small enough to use the imm8 encoding.  No saving over mov, though, since this needs a mod/rm byte

    xchg    eax, edx        ; eax = high,  edx = buf[last_byte]
    cdq                     ; could be removed if we could arrange things so the loop ended with a load of the 0 byte

    div     ecx             ; div instead of idiv to fault instead of returning wrong answers if high has overflowed to negative.  (-1234 % m is negative)
    push    rdx             ; push high%m and 6B of zero padding

    xchg    eax, edi        ; eax=low
    cdq
    div     ecx             ; edx = low%m

    ;; concatenate the two 16bit halves of the result by putting them in contiguous memory
    push    dx              ; push low%m with no padding
    pop     rax             ; pop  high%m << 16 | low%m   (x86 is little-endian)

    pop     dx              ; add rsp, 2 to restore the stack pointer

    ;; outside of 16bit code, we can't justify returning the result in the dx:ax register pair
    ret
golfed_adler32_amd64_end_v3:

```

I also considered using `rcx` as an array index, instead of having two loop counters, but adler32(s) != adler32(reverse(s)). So we couldn't use `loop`. Counting from -len up towards zero and using `movzx r32, [rsi+rcx]` just uses way too many bytes.

If we want to consider incrementing the pointer ourself, 32bit code is probably the way to go. Even the x32 ABI (32bit pointers) isn't sufficient, because `inc esi` is 2B on amd64, but 1B on i386. It appears hard to beat `xor eax,eax` / `lodsb` / `loop`: 4B total to get each element in turn zero-extended into eax. `inc esi` / `movzx r32, byte [esi]` / `loop` is 5B.

`scas` is another option for incrementing a pointer with a 1B instruction in 64bit mode. (`rdi`/`edi` instead of `rsi`, so we'd take the pointer arg in `rdi`). We can't use the flag result from `scas` as a loop condition, though, because we don't want to keep eax zeroed. Different register allocation could maybe save a byte after the loop.

---

### `int[]` input

The full function taking `uint8_t[]` is the "main" answer, because it's a more interesting challenge. Unpacking to `int[]` is an unreasonable thing to ask our caller to do in this language, but it does save 2B.

If we take our input as an unpacked array of 32bit integers, we can save one byte easily (use `lodsd` and replace `xor eax,eax / cdq` with just `xor edx,edx`).

We can save another byte by zeroing edx with `lodsd`/`cdq`, and re-arranging the loop so it loads the terminating 0 element before exiting. (We're still assuming it exists, even though this is an array of `int`, not a string).

```
; untested: I didn't modify the test driver to unpack strings for this
golfed_adler32_int_array:
    ; xor   edx,edx
    lodsd                   ; first element. only the low byte non-zero
    cdq                     ; edx: high=0
    lea     edi, [rdx+1]    ; edi: low=1
    ;jrcxz  .end            ; handle len=0?  unlike rep, loop only checks rcx after decrementing
.intloop:
    add     edi, eax        ; low += buf[i]
    add     edx, edi        ; high += low
    lodsd                   ; load buf[i+1] for next iteration
    loop   .intloop
.end:
    ;; exit when ecx = 0, eax = terminating 0

    xchg    eax, edx
    ;cdq               ; edx=0 already, ready for div
    ; same as the char version

```

I also made an untested version that uses `scasd` (1B version of `add edi,4`) and `add eax, [rdi]` instead of `lodsd`, but it's also 30 bytes. The savings from having `high` in eax at the end of the loop are balanced out by larger code elsewhere. It has the advantage of not depending on a terminating `0` element in the input, though, which is maybe unreasonable for an unpacked array where we're also given the length explicitly.

---

## C++11 test driver

See the github link. This answer was getting too big, and the test driver got more features with bigger code.

# Answer
> 8 votes
# MATL, 22 bytes

```
tsQwYsQsh16W15-\l8Mh*s

```

Input can be an array of numbers or the corresponding ASCII string.

**Try it online!**

### Explanation

```
t       % Take array or string as input. Duplicate
sQ      % Sum all its values, and add 1
wYsQs   % Swap. Cumulative sum, add 1, sum
h       % Concatenate horizontally
16W     % 2^16: gives 65536
15-     % Subtract 15: gives 65521
\       % Element-wise modulo operation
l       % Push 1
8M      % Push 65536 again
h       % Concatenate horizontally: gives array [1, 65535]
*s      % Element-wise multiplication and sum. Display

```

# Answer
> 7 votes
## Actually, 36 bytes

```
;Σu@;╗lR`╜HΣu`MΣk`:65521@%`M1#84ⁿ@q*

```

Try it online!

Explanation:

```
;Σu@;╗lR`╜HΣu`MΣk`:65521@%`M1#84ⁿ@q*
;Σu                                   sum(input)+1
   @;╗lR                              push a copy of input to reg0, push range(1, len(input)+1)
        `╜HΣu`M                       map over range: sum(head(reg0,n))+1
               Σk                     sum, combine lower and upper into a list
                 `:65521@%`M          modulo each by 65521
                            1#84ⁿ@q*  dot product with [1,4**8]

```

# Answer
> 7 votes
# Java, 84 bytes

```
long a(int[]i){long a=1,b=0;for(int p:i)b=(b+(a=(a+p)%(p=65521)))%p;return b<<16|a;}

```

If Java solutions are always supposed to be complete compilable code please let me know.

### Ungolfed

```
long a(int[] i) {
    long a = 1, b = 0;
    for (int p : i) b = (b + (a = (a + p) % (p = 65521))) % p;
    return b << 16 | a;
}

```

### Note

You will have to convert the input `String` to `int[]` (`int[]` is one byte shorter than `byte[]` or `char[]`).

### Output

```
String:     "Eagles are great!"
Byte Array: [69, 97, 103, 108, 101, 115, 32, 97, 114, 101, 32, 103, 114, 101, 97, 116, 33]
Checksum:   918816254
Expected:   918816254

String:     "Programming Puzzles & Code Golf"
Byte Array: [80, 114, 111, 103, 114, 97, 109, 109, 105, 110, 103, 32, 80, 117, 122, 122, 108, 101, 115, 32, 38, 32, 67, 111, 100, 101, 32, 71, 111, 108, 102]
Checksum:   3133147946
Expected:   3133147946

String:     "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
Byte Array: [126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126]
Checksum:   68095937
Expected:   68095937

String:     "?????????...?"
Byte Array: [63, 63, 63, 63, 63, 63, 63, 63, 63, ...,63]
Checksum:   2181038080
Expected:   2181038080

```

# Answer
> 6 votes
# Piet, 120 Codels

With codelsize 20:

### Notes / How does it work?

* Since it is not possible to use an array or string as input, this program works by taking a series of integers (representing ascii characters) as inputs. I thought about using character inputs at first but struggled to find a nice solution for termination, so now it terminates when any numer smaller than 1 is entered. It was originally only negative values for termination, but I had to change the initialization after writing the program, so now I can't fit the required `2`, only a `1` (26/45 on the trace image). This doesn't matter though because as per the challenge rules, only printable ascii characters are allowed.
* Struggled for a long time with reentering the loop, though I found quite the elegant solution in the end. No `pointer` or `switch` operations, only the interpreter running into walls until it transitions back into the green codel to read the input (43-\>44 on the trace images).
* Loop termination is achived by first duplicating the input, adding 1 and then checking if it is bigger than 1. If it is, the codel chooser is triggered and execution continues on the lower path. If it is not, the program contines left (Bright yellow codels, 31/50 on the trace images).
* The supported input size is interpreter implementation dependent, though it would be possible to support an arbitrarily large input with the right interpreter (Say, for example, a Java interpreter that uses `BigInteger` as internal values)
* Just saw that the setup includes one unnecessary `DUP` and `CC` (7-\>8-\>9 in the trace images). No idea how that happened. This is effectively a noop though, it toggles the codel chooser 16 times which results in no change.

### Npiet trace images

Setup and first loop:

Loop termination, output and exit:

### Outputs

Forgive me if I only include one output, it just takes a long time to input :^)

```
String: "Eagles are great!"

PS B:\Marvin\Desktop\Piet> .\npiet.exe adler32.png
? 69
? 97
? 103
? 108
? 101
? 115
? 32
? 97
? 114
? 101
? 32
? 103
? 114
? 101
? 97
? 116
? 33
? -1
918816254

```

### Npiet trace for \[65, -1\]

```
trace: step 0  (0,0/r,l nR -> 1,0/r,l dR):
action: push, value 4
trace: stack (1 values): 4

trace: step 1  (1,0/r,l dR -> 2,0/r,l dB):
action: duplicate
trace: stack (2 values): 4 4

trace: step 2  (2,0/r,l dB -> 3,0/r,l nM):
action: multiply
trace: stack (1 values): 16

trace: step 3  (3,0/r,l nM -> 4,0/r,l nC):
action: duplicate
trace: stack (2 values): 16 16

trace: step 4  (4,0/r,l nC -> 5,0/r,l nY):
action: duplicate
trace: stack (3 values): 16 16 16

trace: step 5  (5,0/r,l nY -> 6,0/r,l nM):
action: duplicate
trace: stack (4 values): 16 16 16 16

trace: step 6  (6,0/r,l nM -> 7,0/r,l nC):
action: duplicate
trace: stack (5 values): 16 16 16 16 16

trace: step 7  (7,0/r,l nC -> 8,0/r,l nY):
action: duplicate
trace: stack (6 values): 16 16 16 16 16 16

trace: step 8  (8,0/r,l nY -> 9,0/r,l lB):
action: switch
trace: stack (5 values): 16 16 16 16 16
trace: stack (5 values): 16 16 16 16 16

trace: step 9  (9,0/r,l lB -> 10,0/r,l dM):
action: multiply
trace: stack (4 values): 256 16 16 16

trace: step 10  (10,0/r,l dM -> 11,0/r,l nR):
action: multiply
trace: stack (3 values): 4096 16 16

trace: step 11  (11,0/r,l nR -> 12,0/r,l lY):
action: multiply
trace: stack (2 values): 65536 16

trace: step 12  (12,0/r,l lY -> 13,0/r,l lM):
action: duplicate
trace: stack (3 values): 65536 65536 16

trace: step 13  (13,0/r,l lM -> 14,0/r,l nM):
action: push, value 3
trace: stack (4 values): 3 65536 65536 16

trace: step 14  (14,0/r,l nM -> 15,0/r,l dM):
action: push, value 2
trace: stack (5 values): 2 3 65536 65536 16

trace: step 15  (15,0/r,l dM -> 16,0/r,l lC):
action: roll
trace: stack (3 values): 16 65536 65536

trace: step 16  (16,0/r,l lC -> 17,0/r,l nB):
action: sub
trace: stack (2 values): 65520 65536

trace: step 17  (17,0/r,l nB -> 18,0/r,l dB):
action: push, value 1
trace: stack (3 values): 1 65520 65536

trace: step 18  (18,0/r,l dB -> 19,0/r,l dM):
action: add
trace: stack (2 values): 65521 65536

trace: step 19  (19,0/r,l dM -> 19,1/d,r dC):
action: duplicate
trace: stack (3 values): 65521 65521 65536

trace: step 20  (19,1/d,r dC -> 18,1/l,l lC):
action: push, value 1
trace: stack (4 values): 1 65521 65521 65536

trace: step 21  (18,1/l,l lC -> 17,1/l,l nC):
action: push, value 1
trace: stack (5 values): 1 1 65521 65521 65536

trace: step 22  (17,1/l,l nC -> 16,1/l,l dB):
action: sub
trace: stack (4 values): 0 65521 65521 65536

trace: step 23  (16,1/l,l dB -> 15,1/l,l lB):
action: push, value 1
trace: stack (5 values): 1 0 65521 65521 65536

trace: step 24  (15,1/l,l lB -> 13,2/l,l dG):
action: in(number)
? 65
trace: stack (6 values): 65 1 0 65521 65521 65536

trace: step 25  (13,2/l,l dG -> 12,2/l,l dR):
action: duplicate
trace: stack (7 values): 65 65 1 0 65521 65521 65536

trace: step 26  (12,2/l,l dR -> 11,2/l,l lR):
action: push, value 1
trace: stack (8 values): 1 65 65 1 0 65521 65521 65536

trace: step 27  (11,2/l,l lR -> 10,2/l,l lY):
action: add
trace: stack (7 values): 66 65 1 0 65521 65521 65536

trace: step 28  (10,2/l,l lY -> 9,2/l,l nY):
action: push, value 1
trace: stack (8 values): 1 66 65 1 0 65521 65521 65536

trace: step 29  (9,2/l,l nY -> 8,1/l,r nB):
action: greater
trace: stack (7 values): 1 65 1 0 65521 65521 65536

trace: step 30  (8,1/l,r nB -> 7,1/l,r lY):
action: switch
trace: stack (6 values): 65 1 0 65521 65521 65536
trace: stack (6 values): 65 1 0 65521 65521 65536

trace: step 31  (7,1/l,l lY -> 6,2/l,l nY):
action: push, value 2
trace: stack (7 values): 2 65 1 0 65521 65521 65536

trace: step 32  (6,2/l,l nY -> 5,3/l,l dB):
action: pointer
trace: stack (6 values): 65 1 0 65521 65521 65536

trace: step 33  (5,3/r,l dB -> 7,4/r,l dM):
action: add
trace: stack (5 values): 66 0 65521 65521 65536

trace: step 34  (7,4/r,l dM -> 8,4/r,l dC):
action: duplicate
trace: stack (6 values): 66 66 0 65521 65521 65536

trace: step 35  (8,4/r,l dC -> 9,3/r,l lC):
action: push, value 3
trace: stack (7 values): 3 66 66 0 65521 65521 65536

trace: step 36  (9,3/r,l lC -> 10,3/r,l nC):
action: push, value 2
trace: stack (8 values): 2 3 66 66 0 65521 65521 65536

trace: step 37  (10,3/r,l nC -> 11,3/r,l dY):
action: roll
trace: stack (6 values): 0 66 66 65521 65521 65536

trace: step 38  (11,3/r,l dY -> 12,3/r,l dG):
action: add
trace: stack (5 values): 66 66 65521 65521 65536

trace: step 39  (12,3/r,l dG -> 13,3/r,l lG):
action: push, value 2
trace: stack (6 values): 2 66 66 65521 65521 65536

trace: step 40  (13,3/r,l lG -> 14,3/r,l nG):
action: push, value 1
trace: stack (7 values): 1 2 66 66 65521 65521 65536

trace: step 41  (14,3/r,l nG -> 15,3/r,l dR):
action: roll
trace: stack (5 values): 66 66 65521 65521 65536
trace: white cell(s) crossed - continuing with no command at 17,3...

trace: step 42  (15,3/r,l dR -> 17,3/r,l lB):

trace: step 43  (17,3/r,l lB -> 13,2/l,l dG):
action: in(number)
? -1
trace: stack (6 values): -1 66 66 65521 65521 65536

trace: step 44  (13,2/l,l dG -> 12,2/l,l dR):
action: duplicate
trace: stack (7 values): -1 -1 66 66 65521 65521 65536

trace: step 45  (12,2/l,l dR -> 11,2/l,l lR):
action: push, value 1
trace: stack (8 values): 1 -1 -1 66 66 65521 65521 65536

trace: step 46  (11,2/l,l lR -> 10,2/l,l lY):
action: add
trace: stack (7 values): 0 -1 66 66 65521 65521 65536

trace: step 47  (10,2/l,l lY -> 9,2/l,l nY):
action: push, value 1
trace: stack (8 values): 1 0 -1 66 66 65521 65521 65536

trace: step 48  (9,2/l,l nY -> 8,1/l,r nB):
action: greater
trace: stack (7 values): 0 -1 66 66 65521 65521 65536

trace: step 49  (8,1/l,r nB -> 7,1/l,r lY):
action: switch
trace: stack (6 values): -1 66 66 65521 65521 65536
trace: stack (6 values): -1 66 66 65521 65521 65536

trace: step 50  (7,1/l,r lY -> 6,1/l,r dY):
action: pop
trace: stack (5 values): 66 66 65521 65521 65536

trace: step 51  (6,1/l,r dY -> 4,1/l,r lY):
action: push, value 3
trace: stack (6 values): 3 66 66 65521 65521 65536

trace: step 52  (4,1/l,r lY -> 3,1/l,r nY):
action: push, value 2
trace: stack (7 values): 2 3 66 66 65521 65521 65536

trace: step 53  (3,1/l,r nY -> 2,1/l,r nM):
action: duplicate
trace: stack (8 values): 2 2 3 66 66 65521 65521 65536

trace: step 54  (2,1/l,r nM -> 1,1/l,r dG):
action: pointer
trace: stack (7 values): 2 3 66 66 65521 65521 65536

trace: step 55  (1,1/r,r dG -> 2,2/r,r lR):
action: roll
trace: stack (5 values): 65521 66 66 65521 65536

trace: step 56  (2,2/r,r lR -> 2,3/d,l nR):
action: push, value 1
trace: stack (6 values): 1 65521 66 66 65521 65536

trace: step 57  (2,3/d,l nR -> 2,4/d,l lC):
action: switch
trace: stack (5 values): 65521 66 66 65521 65536
trace: stack (5 values): 65521 66 66 65521 65536

trace: step 58  (2,4/d,r lC -> 2,5/d,r nM):
action: mod
trace: stack (4 values): 66 66 65521 65536

trace: step 59  (2,5/d,r nM -> 4,5/r,r dM):
action: push, value 3
trace: stack (5 values): 3 66 66 65521 65536

trace: step 60  (4,5/r,r dM -> 6,5/r,r lM):
action: push, value 2
trace: stack (6 values): 2 3 66 66 65521 65536

trace: step 61  (6,5/r,r lM -> 7,5/r,r nC):
action: roll
trace: stack (4 values): 65521 66 66 65536

trace: step 62  (7,5/r,r nC -> 8,5/r,r dM):
action: mod
trace: stack (3 values): 66 66 65536

trace: step 63  (8,5/r,r dM -> 11,5/r,r lM):
action: push, value 3
trace: stack (4 values): 3 66 66 65536

trace: step 64  (11,5/r,r lM -> 12,5/r,r nM):
action: push, value 1
trace: stack (5 values): 1 3 66 66 65536

trace: step 65  (12,5/r,r nM -> 13,5/r,r dC):
action: roll
trace: stack (3 values): 66 65536 66

trace: step 66  (13,5/r,r dC -> 14,5/r,r nB):
action: multiply
trace: stack (2 values): 4325376 66

trace: step 67  (14,5/r,r nB -> 15,5/r,r nM):
action: add
trace: stack (1 values): 4325442

trace: step 68  (15,5/r,r nM -> 16,5/r,r dB):
action: out(number)
4325442
trace: stack is empty
trace: white cell(s) crossed - continuing with no command at 19,5...

trace: step 69  (16,5/r,r dB -> 19,5/r,r nM):

```

# Answer
> 5 votes
# C89, 70 bytes

```
h,l,m=65521;A(char*B){h=0;l=1;while(*B)h+=l+=*B++;return h%m<<16|l%m;}

```

To test (compile with `gcc -std=c89 -lm golf.c`):

```
#include <stdio.h>
int main(int argc, char** argv) {
    printf("%u\n", A("Eagles are great!"));
    printf("%u\n", A("Programming Puzzles & Code Golf"));
    printf("%u\n", A("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"));
    return 0;
}

```

# Answer
> 5 votes
## Labyrinth, ~~37~~ ~~36~~ ~~32~~ 31 bytes

```
}?"{655:}21:}%=}){%{{36*+!
:++)

```

Try it online!

Input as a list of integers. The program terminates with an error (whose error message goes to STDERR).

### Explanation

Labyrinth primer:

* Labyrinth has two stacks of arbitrary-precision integers, *main* and *aux*(iliary), which are initially filled with an (implicit) infinite amount of zeros.
* The source code resembles a maze, where the instruction pointer (IP) follows corridors when it can (even around corners). The code starts at the first valid character in reading order, i.e. in the top left corner in this case. When the IP comes to any form of junction (i.e. several adjacent cells in addition to the one it came from), it will pick a direction based on the top of the main stack. The basic rules are: turn left when negative, keep going ahead when zero, turn right when positive. And when one of these is not possible because there's a wall, then the IP will take the opposite direction. The IP also turns around when hitting dead ends.
* Digits are processed by multiplying the top of the main stack by 10 and then adding the digit. To start a new number, you can push a zero with `_`.

Although the code starts with a 4x2 "room", that is actually two separate two-by-two loops squeezed together. The IP just happens to stick to one loop at a time due to the stack values.

So the code starts with a 2x2 (clockwise) loop which reads input while computing prefix sums:

```
}   Move last prefix sum over to aux.
?   Read an integer from STDIN or push 0 on EOF, which exits the loop.
+   Add current value to prefix sum.
:   Duplicate this prefix sum.

```

Now we've got all the prefix sums on the *aux* stack, as well as a copy of the sum over all values and the `0` from EOF on *main*. With that, we enter another 2x2 (clockwise) loop which sums all the prefix sums to compute `HIGH`.

```
"   No-op. Does nothing.
{   Pull one prefix sum over from aux. When we're done, this fetches a 0,
    which exits the loop.
)   Increment prefix sum.
+   Add it to HIGH.

```

The main stack now has `LOW - 1` and `HIGH` and zero, except we haven't taken the modulo yet. The remainder of the code is completely linear:

```
655      Turn the zero into 655.
:}       Make a copy and shift it over to aux.
21       Turn the copy on main into 65521.
:}       Make a copy and shift it over to aux.
%        Take HIGH mod 65521.
=        Swap HIGH with the other copy of 65521 on aux.
}){      Move 65521 back to aux, increment LOW-1 to LOW,
         move 65521 back to main.
%        Take LOW mod 65521.
{        Move HIGH back to main.
{        Move the other copy of 655 back to main.
36       Turn it into 65536.
*        Multiply HIGH by that.
+        Add it to LOW.
!        Print it.

```

The IP now hits a dead end and turns around. The `+` and `*` are essentially no-ops, due to the zeros at the stack bottom. The `36` now turns the top of *main* into `63`, but the two `{{` pull two zeros from *aux* on top of it. Then `%` tries to divide by zero which terminates the program.

Note that Labyrinth uses arbitrary-precision integers so deferring the modulo until the end of the sum won't cause problems with integer overflow.

# Answer
> 5 votes
## Python 2, ~~60~~ 58 bytes

```
H=h=65521
l=1
for n in input():l+=n;h+=l
print h%H<<16|l%H

```

A pretty straightforward approach. This is a full program which takes a list of integers via STDIN, e.g. `[72, 105, 33]`.

*(Thanks to @xnor for the amazing aliasing/initialisation tip)*

# Answer
> 4 votes
# J, 30 bytes

```
+/(+65536&*)&(65521|+/)&:>:+/\

```

This could probably be condensed more with a different train.

## Usage

Here `x $ y` creates a list with `x` copies of `y`.

```
   f =: +/(+65536&*)&(65521|+/)&:>:+/\
   f 69 97 103 108 101 115 32 97 114 101 32 103 114 101 97 116 33
918816254
   f 80 114 111 103 114 97 109 109 105 110 103 32 80 117 122 122 108 101 115 32 38 32 67 111 100 101 32 71 111 108 102
3133147946
   f (32 $ 126)
68095937
   f (1040 $ 63)
2181038080
   f (4096 $ 255)
2170679522

```

## Explanation

```
+/(+65536&*)&(65521|+/)&:>:+/\
f (           g           ) h     Monad train (f g h) y = (f y) g (h y)
+/                                Sum the input list
                           +/\    Sum each prefix of the input, forms a list
x     f   &   g   &:   h    y     Composed verbs, makes (g (h x)) f (g (h y))
                         >:       Increment the sum and increment each prefix sum
               (m f g) y          Hook, makes m f (g y)
                    +/            Sum the prefix sums
              65521|              Take the sum and prefix total mod 65521
    (f g) y                       Hook again
    65536&*                       Multiply the prefix total by 65536
                                  This is a bonded verb, it will only multiply
                                  using a fixed value now
   +                              Add the sum and scaled prefix total

```

# Answer
> 4 votes
# Octave, ~~52~~ 50 bytes

Saved 2 bytes thanks to @LuisMendo

```
@(B)mod([sum(S=cumsum(B)+1),S(end)],65521)*[4^8;1]

```

Takes an array of integers as input.

**low** is taken from the last element of **high** (before summing) rather than calculating the sum explicitly, saving a grand total of... **1 byte**!

Sample run on ideone.

# Answer
> 3 votes
## JavaScript (ES7), ~~52~~ 50 bytes

```
a=>a.map(b=>h+=l+=b,h=0,l=1)&&l%65521+h%65521*4**8

```

ES6 takes 51 bytes (replace 4\**8 with 65536). If you want a string version, then for 69 bytes:

```
s=>[...s].map(c=>h+=l+=c.charCodeAt(),h=0,l=1)&&l%65521+h%65521*65536

```

Edit: Saved 2 bytes thanks to @user81655.

# Answer
> 3 votes
## Haskell, ~~54~~ 50 bytes

```
m=(`mod`65521).sum
g x=m(-1:scanl(+)1x)*4^8+m(1:x)

```

Usage example: `g [69,97,103,108,101,115,32,97,114,101,32,103,114,101,97,116,33]`-\> `918816254`.

`scanl` includes the starting value (-\> `1`) in the list (-\> `[1,1+b1,1+b1+b2,..]`), so the `sum` is off by `1`, which is fixed by prepending `-1` to the list before summing.

Edit: Thanks @xnor for 4 bytes.

# Answer
> 3 votes
## CJam, ~~30~~ 29 bytes

```
q~{1$+}*]:)_W>]1fb65521f%2G#b

```

Input as a list of integers.

Test it here.

### Explanation

```
q~       e# Read and evaluate input.
{        e# Fold this block over the list, computing prefix sums.
  1$+    e#   Copy the last prefix and add the current element.
}*
]        e# Wrap the prefix sums in an array.
:)       e# Increment each. This will sum to HIGH.
_W>      e# Copy the list and truncate to only the last element, i.e.
         e# the sum of the entire input plus 1. This is LOW.
]        e# Wrap both of those lists in an array.
1fb      e# Sum each, by treating it as base 1 digits.
65521f%  e# Take each modulo 65521.
2G#b     e# Treat the list as base 65536 digits, computing 65536*HIGH + LOW.

```

# Answer
> 3 votes
# Perl 6, 60 bytes

```
{(.sum+1)%65521+65536*((sum(1,*+.shift...->{!$_})-1)%65521)}

```

### Explanation:

```
{
  # $_ is the implicit parameter for this lambda because this block doesn't have
  # an explicit parameter, and @_ isn't seen inside of it.
  # ( @_ takes precedence over $_ when it is seen by the compiler )

  # .sum is short for $_.sum
  ( .sum + 1 ) % 65521 + 65536
  *
  (
    (
      sum(

        # generate a sequence:

        1,         # starting with 1
        * + .shift # lambda that adds previous result (*) with $_.shift
        ...        # generate until:
        -> { !$_ } # $_ is empty

        # ^ I used a pointy block with zero parameters
        # so that the block doesn't have an implicit parameter
        # like the surrounding block

        # this is so that $_ refers to the outer $_

      ) - 1        # remove starting value
    ) % 65521
  )
}

```

### Test:

```
#! /usr/bin/env perl6
use v6.c;
use Test;

# give the lambda a name
my &Adler32 = {(.sum+1)%65521+65536*((sum(1,*+.shift...->{!$_})-1)%65521)}

my @tests = (
  (  918816254,  'Eagles are great!'),
  ( 3133147946,  'Programming Puzzles & Code Golf'),
  (   68095937,  '~' x 32,     "'~' x 32"),
  ( 2181038080,  63 xx 1040,   "'?' x 1040"),
);

plan +@tests;

for @tests -> ($checksum, $input, $gist? ) {
  my @array := do given $input {
    when Str { .encode.Array }
    default { .Array }
  }

  is Adler32(@array), $checksum, $gist // $input.perl
}

```

```
1..4
ok 1 - "Eagles are great!"
ok 2 - "Programming Puzzles \& Code Golf"
ok 3 - '~' x 32
ok 4 - '?' x 1040

```

# Answer
> 3 votes
# Python 3 (79 bytes)

Based on R. Kap's solution.

```
lambda w,E=65521:(1+sum(w))%E+(sum(1+sum(w[:i+1])for i in range(len(w)))%E<<16)

```

I replaced the multiplication by a shift and removed a pair of brackets.

Because I can't post comments I made a new answer.

# Answer
> 3 votes
# Scheme, 195 bytes

```
(define(a b)(+(let L((b b)(s 1))(if(=(length b)0)s(L(cdr b)(modulo(+ s(car b))65521))))(* 65536(let H((b b)(s 1)(t 0))(if(=(length b)0)t(let((S(+ s(car b))))(H(cdr b)S(modulo(+ t S)65521))))))))

```

If it weren't for all those parentheses...

# Answer
> 3 votes
# ARM Thumb-2 function accepting `uint8_t[]`: 40 bytes (36B for non-standard ABI and `int[]`)

Features: non-deferred modulo, so arbitrary-size inputs are fine. Doesn't actually use the division instruction, so it's not slow. (err, at least not for that reason :P)

Savings from following less strict rules:

* -2B if we don't have to save registers before using them.
* -2B for requiring the caller to unpack bytes into a `uint32_t[]` array.

So, best-case is 36B.

```
// uint8_t *buf in r0,  uint32_t len in r1
00000000 <adler32arm_golf2>:
   0:   b570            push    {r4, r5, r6, lr} //
   2:   2201            movs    r2, #1          // low
   4:   2300            movs    r3, #0          // high
   6:   f64f 75f1       movw    r5, #65521      ; 0xfff1 = m
0000000a <adler32arm_golf2.byteloop>:
   a:   f810 4b01       ldrb.w  r4, [r0], #1    // post-increment byte-load
   e:   4422            add     r2, r4          // low += *B
  10:   4413            add     r3, r2          // high += low
  12:   42aa            cmp     r2, r5          // subtract if needed instead of deferred modulo
  14:   bf28            it      cs
  16:   1b52            subcs   r2, r2, r5
  18:   42ab            cmp     r3, r5
  1a:   bf28            it      cs              // Predication in thumb mode is still possible, but takes a separate instruction
  1c:   1b5b            subcs   r3, r3, r5
  1e:   3901            subs    r1, #1          // while(--len)
  20:   d1f3            bne.n   a <.byteloop2>
  22:   eac2 4003       pkhbt   r0, r2, r3, lsl #16   // other options are the same size: ORR or ADD.
  26:   bd70            pop     {r4, r5, r6, pc}  // ARM can return by popping the return address (from lr) into the pc; nifty
00000028 <adler32arm_end_golf2>:

```

**0x28 = 40 bytes**

---

## Notes:

Instead of `log%m` at the end, we do `if(low>=m) low-=m` inside the loop. If we do low before high, we know that neither can possibly exceed `2*m`, so modulo is just a matter of subtracting or not. A `cmp` and predicated `sub` is only 6B in Thumb2 mode. The standard idiom for `%` is 8B in Thumb2 mode:

```
UDIV R2, R0, R1         // R2 <- R0 / R1
MLS  R0, R1, R2, R0     // R0 <- R0 - (R1 * R2 )

```

---

The implicit-length `adler(char *)` version is the same code-size as the explicit length `adler(uint8_t[], uint32_t len)`. We can set flags for the loop-exit condition with a single 2B instruction either way.

The implicit-length version has the advantage of working correctly with the empty string, instead of trying to loop 2^32 times.

---

## assemble / compile with:

```
arm-linux-gnueabi-as --gen-debug -mimplicit-it=always -mfloat-abi=soft -mthumb adler32-arm.S

```

or

```
arm-linux-gnueabi-g++ -Wa,-mimplicit-it=always -g -static -std=gnu++14 -Wall -Wextra -Os -march=armv6t2 -mthumb -mfloat-abi=soft test-adler32.cpp -fverbose-asm adler32-arm.S -o test-adler32
qemu-arm ./test-adler32

```

Without `-static`, the process running under `qemu-arm` didn't find it's dynamic linker. (And yes, I install an ARM cross-devel setup just for this answer, because I thought my predicated-subtract idea was neat.) On amd64 Ubuntu, install `gcc-arm-linux-gnueabi`, `g++-arm-linux-gnueabi`. I found `gdb-arm-none-eabi` sort of barely worked connecting to `qemu-arm -g port`.

## Commented source:

```
// There's no directive to enable implicit-it=always

// gcc uses compiler uses these in its output
.syntax unified
.arch armv8-a
.fpu softvfp

.thumb      @ aka .code 16

.p2align 4
.globl adler32arm_golf    @ put this label on the one we want to test

.thumb_func
adler32arm_golf:
adler32arm_golf2:   @ (uint8_t buf[], uint32_t len)
        @ r0 = buf
        @ r1 = len
        push    {r4, r5, r6, lr}   @ even number of regs keeps the stack aligned.  Good style? since there's no code-size saving

        movs    r2, #1          @ r2: low
        movs    r3, #0          @ r3: high
                                @ r4 = tmp for loading bytes
        movw    r5, #65521      @ r5: modulo constant

adler32arm_golf2.byteloop2:
        ldrb    r4, [r0], #1    @ *(buf++) post-increment addressing.  4B encoding
        @ldrb    r4, [r0, r1]   @ 2B encoding, but unless we make the caller pass us buf+len and -len, it needs extra code somewhere else
        @ldmia   r0!, {r4}      @ int[] version:  r4 = [r0]; r0+=4;  post-increment addressing.  2B encoding.

        add     r2, r2, r4      @ low += tmp
        add     r3, r3, r2      @ high += low;   // I think it's safe to do this before the modulo range-reduction for low, but it would certainly work to put it after.

        cmp     r2, r5
        subhs   r2, r5          @ if(low>=m) low-=m;   @ 6B total for %.  predicated insns require an IT instruction in thumb2

        cmp     r3, r5
        subhs   r3, r5          @ if(high>=m) high-=m;  // equivalent to high %= m.

        @sub    r1, #1          @ 4B encoding: sub.w to not set flags with immediate
        subs    r1, #1          @ len-- and set flags.  2B encoding
        @cmp    r4, #0          @ null-termination check. 2B encoding
        bne     adler32arm_golf2.byteloop2

@        udiv    r0, r2, r5            @ normal way to do one of the modulos
@        mls     r2, r5, r0, r2         @ r2 = low % m.  8B total for %

        PKHBT   r0, r2, r3, lsl #16     @ 4B   r0 = [ high%m <<16  |   low%m  ]
        @orr     r0, r0, r4, lsl #16    @ 4B
        @orr     r0, r0, r4             @ 4B
        @add     r0, r2, r3, lsl #16    @ 4B
        @add     r0, r0, r4             @ 2B
        pop     {r4, r5, r6, pc}        @ ARM can return by popping the return address (saved from lr) into pc.  Nifty
adler32arm_end_golf2:

```

`test-adler32.cpp` has the same test-cases and `main()` as for my x86-64 answer, but starts this way:

```
#include <stdint.h>
uint32_t adler32_simple(const uint8_t *B) {
  const uint32_t m=65521;

  uint32_t h=0, l=1;
  do {
    l += *B++;        // Borrowed from orlp's answer, as a simple reference implementation
    h += l;
    l %= m; h %= m;   // with non-deferred modulo if this is uncommented
  } while(*B);

  return h%m<<16|l%m;
}

#include <stdio.h>
//#include <zlib.h>
#include <string.h>
#include <assert.h>
#include <string>   // useful for the memset-style constructors that repeat a character n times

extern "C" {
    unsigned golfed_adler32_amd64(int /*dummy1*/, const char *buf, int /*dummy2*/, unsigned len);
    unsigned adler32arm_golf(const char *buf, unsigned len);
}
#ifdef __amd64__
#define golfed_adler32(buf, len)   golfed_adler32_amd64(1234, buf, 1234, len)
#elif  __arm__
#define golfed_adler32(buf, len)   adler32arm_golf(buf, len)
#else
#error "no architecture"
#endif

static void test_adler(const char *str)
{
    unsigned len = strlen(str);
//    unsigned zlib = zlib_adler(len, str);
    unsigned reference = adler32_simple((const uint8_t*)str);
    unsigned golfed = golfed_adler32(str, len);

    printf("%s: c:%u asm:%u\n", str, reference, golfed);
    assert(reference == golfed);
}

// main() to call test_adler() unchanged from my amd64 answer, except that the comments about length limits don't apply

```

# Answer
> 3 votes
# x86 16bit machine code function: 32 bytes using a custom calling convention

Args in registers, and not preserving regs other than bp (and sp).

In 16bit code, we return a 32bit value in the `dx:ax` register pair. This means we don't have to spend any instructions merging `high` and `low` into `eax`. (This would save bytes in 32 and 64 bit code, too, but we can only justify offloading this work to the caller in 16bit code.)

### Commented source and test driver on github (for x86 16, 32, and 64bit, and ARM).

```
### const char *buf in SI,  uint16_t len in CX
## returns in dx:ax
## also clobbers bx and di.
00000100 <adler32_x16_v6>:
 100:   31 c0                   xor    ax,ax         # set up for lods
 102:   99                      cwd                  # dx= high=0
 103:   bf 01 00                mov    di,0x1        # di= low=0
 106:   bb f1 ff                mov    bx,0xfff1     # bx= m
00000109 <adler32_x16_v6.byteloop>:
 109:   ac                      lods
 10a:   01 c7                   add    di,ax         # low+=buf[i]. modulo-reduce on carry, or on low>=m
 10c:   72 04                   jc     112 <adler32_x16_v6.carry_low>
 10e:   39 df                   cmp    di,bx
 110:   72 02                   jb     114 <adler32_x16_v6.low_mod_m_done>
00000112 <adler32_x16_v6.carry_low>:
 112:   29 df                   sub    di,bx
00000114 <adler32_x16_v6.low_mod_m_done>:
 114:   01 fa                   add    dx,di         # high+=low
 116:   0f 92 d0                setb   al            # store the carry to set up a 32bit dividend.
 119:   92                      xchg   dx,ax
 11a:   f7 f3                   div    bx            # high (including carry) %= m, in dx.  ax=0 or 1 (so we're set for lods next iteration)
 11c:   e2 eb                   loop   109 <adler32_x16_v6.byteloop>
 11e:   97                      xchg   di,ax         #
 11f:   c3                      ret
00000120 <adler32_x16_v6_end>:

```

0x120 - 0x100 = 32 bytes

Tested by assembling the same code for 32bit mode, so I can call it (with a wrapper function) from C compiled with `-m32`. For me, 16bit mode is somewhat interesting, DOS system calls are not. All the instructions have explicit operands, except `loop` and `lodsb`, so assembling for 32bit mode uses operand-size prefixes. Same instruction, different encoding. But `lodsb` in 32bit mode will use `[esi]`, so this for-testing version works with 32bit pointers (because we don't do any address-math or pointer increment/compare).

No mismatches. My test harness prints a message if there is a mismatch.

```
$ yasm -felf32 -Worphan-labels -gdwarf2 adler32-x86-16.asm -o adler32-x86-16+32.o &&
   g++ -DTEST_16BIT -m32 -std=gnu++11 -O1 -g -Wall -Wextra -o test-adler32-x16  adler32-x86-16+32.o  test-adler32.cpp -lz &&
   ./test-adler32-x16
Eagles are great! (len=17): zlib:0x36c405fe  c:0x36c405fe golfed:0x36c405fe
Programming Puzzles & Code Golf (len=31): zlib:0xbac00b2a  c:0xbac00b2a golfed:0xbac00b2a
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=32): zlib:0x040f0fc1  c:0x040f0fc1 golfed:0x040f0fc1
?????????????????????????????????????????????????? (len=1040): zlib:0x82000000  c:0x82000000 golfed:0x82000000
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=4096): zlib:0xb169e06a  c:0xb169e06a golfed:0xb169e06a
(0xFF repeating) (len=4096): zlib:0x8161f0e2  c:0x8161f0e2 golfed:0x8161f0e2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=5837): zlib:0x5d2a398c  c:0x5d2a398c golfed:0x5d2a398c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=5838): zlib:0x97343a0a  c:0x97343a0a golfed:0x97343a0a
(0xFF repeating) (len=9999): zlib:0xcae9ea2c  c:0xcae9ea2c golfed:0xcae9ea2c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=65535): zlib:0x33bc06e5  c:0x33bc06e5 golfed:0x33bc06e5

```

---

With 16bit registers, we can't defer modulo reduction until after the loop. There's an interesting difference between 16bit and other operand-sizes: `m = 65521` (`0xFFF1`) is more than half 65536. Subtracting `m` on carry keeps the value below 2\*m, even if `high=0xFFF0 + 0xFFF0`. After the loop, a compare-and-subtract will do the trick, instead of a `div`.

I came up with a **novel technique for modulo-reducing a register after an add that can produce a carry**. Instead of zeroing the upper half of the input for `div`, use `setc dl` to create a 32bit dividend holding the non-truncated add result (`dh` is already zeroed). (`div` does 32b / 16b =\> 16bit division.)

`setcc` (3 bytes) was introduced with 386. To run this on 286 or earlier, the best I've come up with uses the undocumented `salc` instruction (set AL from carry). It's a one-byte opcode for `sbb al,al`, so we could use `salc` / `neg al` before doing the `xchg ax, dx` (which we need anyway). Without `salc`, there's a 4B sequence: `sbb dx,dx` / `neg dx`. We can't use 3B `sbb dx,dx` / `inc dx`, because that would emulate `setnc` rather than `setc`.

---

I tried **using 32bit operand-size** instead of handling carry, but it's not just the `add` instructions that need an operand-size prefix. Instructions setting up the constants and so on also need operand-size prefixes, so it ended up not being the smallest.

# Answer
> 2 votes
# Pyth, ~~25~~ ~~24~~ 23 bytes

*1 byte thanks to @Jakube.*

*1 more byte thanks to @Jakube.*

```
i%R65521sMeBhMsM._Q^4 8

```

Try it online!

Translation of my answer in Jelly.

# Answer
> 2 votes
# Perl 5, 43 bytes

42 bytes, plus 1 for `-aE` instead of `-e`

Input is as decimal integers, space-separated.

```
map$h+=$.+=$_,@F;say$.%65521+$h%65521*4**8

```

A tip of my hat to Sp3000, from whom I took ideas for this answer.

How it works:

1. Because of `-a`, `$.` starts at 1 and `@F` is the input array. `$h` starts at 0. `$_` is used by `map` as a placeholder for each element of an array.
2. `map$h+=$.+=$_,@F` means that for each element in `@F` we add that element to `$.` and then add `$.` to `$h`.
3. Then we do the modular arithmetic `$.%65521+$h%65521*4**8` (that is, `($. % 65521) + ( ($h % 65521) * (4**8) )` and `say` (print) the result.

# Answer
> 1 votes
# Python 3.5, 82 bytes:

(*-1 byte thanks to Neil!*)

(*-1 byte thanks to mathmandan!*)

(*-4 bytes thanks to Dennis!*)

```
lambda w:((1+sum(w))%65521)+4**8*(sum(1+sum(w[:i+1])for i in range(len(w)))%65521)

```

An anonymous `lambda` function. Accepts a byte array, applies the entire algorithm to the array, and outputs the result. Has successfully worked for all the test cases. You call this by assigning a variable to it, and then calling that variable just like you would call a normal function. If you are using the shell, then this should output without a print function. However, if you are not, then you must wrap the function call in the `print()` function to actually see the output.

Try it online! (Ideone)

# Answer
> 1 votes
# Factor, ~~112~~ ~~109~~ 103 bytes

**Now**, this is a literal translation of the algorithm in the question... now that I actually made it, y'know, correct.

```
[ [ sum 1 + ] [ [ dup length [1,b] reverse v. ] [ length ] bi + ] bi [ 65521 mod ] bi@ 16 shift bitor ]

```

Ungolfed:

```
: adler-32 ( seq -- n )
  [ sum 1 + ]
  [
    [ dup length [1,b] reverse v. ]
    [ length ] bi +
  ] bi
  [ 65521 mod ] bi@
  16 shift bitor
  ;

```

Expects any sequence of numbers or a string (not much difference, though they aren't technically the same).

I don't know how this will perform for the given limit on a version of Factor compiled with 32-bit word-size, but on my 6GB 64-bit 2.2GHz machine:

```
IN: scratchpad 1040 63 <array>

--- Data stack:
{ 63 63 63 63 63 63 63 63 63 63 63 63 63 63 ~1026 more~ }
IN: scratchpad [ adler-32 ] time
Running time: 7.326900000000001e-05 seconds

--- Data stack:
2181038080
IN: scratchpad 10,000 63 <array>

--- Data stack:
2181038080
{ 63 63 63 63 63 63 63 63 63 63 63 63 63 63 ~9986 more~ }
IN: scratchpad [ adler-32 ] time
Running time: 0.000531669 seconds

```

# Answer
> 1 votes
# Ruby, 91 bytes

```
->s{b=s.bytes;z=i=b.size
b.inject(1,:+)%65521+b.map{|e|e*(1+i-=1)}.inject(z,:+)%65521*4**8}

```

# Answer
> 1 votes
# Clojure, 109 bytes

Based on @Mark Adler's solution.

```
(fn f[s](->> s(reduce #(mapv + %(repeat %2)[0(first %)])[1 0])(map #(rem % 65521))(map *[1 65536])(apply +)))

```

### Ungolfed

```
(fn f [s]
  (->> s
       (reduce #(mapv + % (repeat %2) [0 (first %)]) [1 0])
       (map #(rem % 65521))
       (map * [1 65536])
       (apply +)))

```

## Usage

```
=> (def f (fn f[s](->> s(reduce #(mapv + %(repeat %2)[0(first %)])[1 0])(map #(rem % 65521))(map *[1 65536])(apply +))))
=> (f [69 97 103 108 101 115 32 97 114 101 32 103 114 101 97 116 33])
918816254
=> (f [80 114 111 103 114 97 109 109 105 110 103 32 80 117 122 122 108 101 115 32 38 32 67 111 100 101 32 71 111 108 102])
3133147946
=> (f (repeat 32 126))
68095937
=> (f (repeat 1040 63))
2181038080
=> (f (repeat 4096 255))
2170679522

```

# Answer
> 1 votes
### Javascript (130 Characters Golfed)

## Ungolfed

```
function a(b)
{
    c=1
    for(i=0;i<b.length;i++)
    {
        c+=b[i]
    }
    d=c%65521
    f=""
    e=0
    k=""
    for(j=0;j<b.length;j++)
    {
        k+= "+"+b[j]
        f+= "(1"+k+")"
        e= ((eval(f)))
        if(j!=b.length-1){f+="+"}
    }
    g=e%65521
    h=d+65536*g
    console.log(h)
}

```

## Golfed

```
a=b=>{for(c=1,k=f="",y=b.length,i=0;i<y;i++)c+=x=b[i],f+="(1"+(k+="+"+x)+")",i<y-1&&(f+="+");return z=65521,c%z+65536*(eval(f)%z)}

```

Paste into Developers Console and then give it an Array of Bytes EG:

##

```
[69, 97, 103, 108, 101, 115, 32, 97, 114, 101, 32, 103, 114, 101, 97, 116, 33]

```

And it will return the checksum to the console

# Answer
> 1 votes
# TMP, 55 bytes

`3a1.3b0.1;4+a>T8%a>xFFF14+b>a8%b>xFFF11~5<b>164|b>a2$b$`

Implementation in Lua can be found here: http://preview.ccode.gq/projects/TMP.lua

# Answer
> 1 votes
# Fission, 324 bytes

```
          /   M
       R_MZ  |S
      D ]    |S
 /?V?\} {}/  |S /    \
R{/A  Z$[/   |S/     {\
  } J{\      |S      ;_
 \^  /       |S   R'~++Y++~'L
 /    /      |S       }Y;
 \  \        ;^/
 /  /         +\+ R'~++A++~'L
 \  <Z________________/
    ;\X       //
              \Y/
               *

```

*Fair warning, the only implementation I've tested this on is my own port of the language to F#. It's not golfed, mainly because I found it easier to have a couple of long runs while my prime constant cooled along the bottom, so I may come back and tweak it.*

How does it work?

* The `R'~++Y++~'L` block fuses a 256 constant and launches it downwards, setting the mass multiplier of the reactor directly below it.
* The `R'~++A++~'A` block fuses another 256 and launches it up towards the reactor above, which fissions the particle into two mass multiples of `65536` mass each, launching them left and right (where the right particle is immediately destroyed by the terminator).
* The left particle hits another reactor and undergoes fission, splitting into two particles of equal mass heading up and down.
* The upward travelling power-of-two particle passes through a net-zero mass manipulation, reflects to the left, then sets the mass multiplier of the fusion reactor. This reactor will be how we multiply the H block.
* The downward travelling particle reflects to the left and sheds mass over the long run, ultimately reaching a mass of `65521` (our large prime).
* The rotational mirror (`Z`) at the end of the run causes the particle to duplicate the prime, sending one back to the right where it ultimately sets the stored mass of the fission reactor (`^`). This is how we'll be applying the modulus operator to the H block.
* The second copy is reflected back, where it performs an analogous function for the fission reactor (`<`) we'll be using for the L block.
* Now that our constants are in place, we engage in shenanigans in the upper left to read our input and generate our two lists. To be honest, I forget how those work, but for the empty string I had to slow down the H block summing particle, which explains the `|S` "cooling tower".
* `\Y/` fuses the L block (which comes in through the left channel) and the H block (which comes in through the right channel), then slams them into a terminator which sets the exit code to the fused mass.

# Answer
> 1 votes
# ABAP, 118 bytes

```
FORM a TABLES t USING l h.l = 1.LOOP AT t.ADD:t TO l,l TO h.ENDLOOP.l = l MOD 65521 + 65536 * ( h MOD 65521 ).ENDFORM.

```

Ungolfed

```
FORM a TABLES t USING l h.
  l = 1.
  LOOP AT t.
    ADD: t TO l,
         l TO h.
  ENDLOOP.
  l = l MOD 65521 + 65536 * ( h MOD 65521 ).
ENDFORM.

```

This is my first try at code golfing, if I did anything wrong please let me know! I used ABAP because that's my main programming language. Now for the explanation:

```
FORM a TABLES t USING l h.
  ...
ENDFORM.

```

This declares the function "a" with the inputs t, l and h. I defined t as a table of integers and filled it with the different numbers from the original post (for test purposes). l and h are defined as DEC variables with length 31 (highest it can go in ABAP). l is also used as the returning variable for the function so I don't have to use an additional variable.

```
  LOOP AT t.
    ...
  ENDLOOP.

```

This is a loop over the table t, which is defined as a table with header-line. This means that the table has a header-line which acts as a variable ("t") and it also has a table body ("t\[ \]") at the same time. So "LOOP AT t" reads the rows in the table t\[ \] (in order) into the header-line t. Header-lines are obsolete but they save quite a bit of bytes over the now used "LOOP AT table INTO variable.".

```
    ADD: t TO l,
         l TO h.

```

Within the loop I'm starting a slightly modified version (pretty much just rearranged) of the calculation that Dennis has in his original post. l = low, h = high. I'm adding the current value in the table to the variable l (which i define to start at 1 in the line "l = 1."). Each step in the loop I'm also adding l to h. I use "ADD" because ABAP doesn't have "l += t" and using the code above is shorter than:

```
l = l + t.
h = h + l.

```

After the loop we have the following:

* l = (1 + b1 \+ ⋯ + bn)
* h = ((1 + b1) + (1 + b1 \+ b2) + ⋯ (1 + b1 \+ ⋯ + bn))

At the end I'm doing the final calculation:

```
  l = l MOD 65521 + 65536 * ( h MOD 65521 ).

```

Sadly you need spaces between the operators and numbers/variables because ABAP uses the operators without spaces for different things. For example:

```
char+4 = 'A'.

```

This sets the 5th character (because the offset is set as "4") of the character variable "char" as 'A'. So if "char" was "BBBBB" before that line, it would be "BBBBA" after.

I hope this explanation isn't too long (which I think it is, since the code is really straight forward). ABAP doesn't have bitwise operations AFAIK so I couldn't use a shorter algorithm but I think 118 bytes is still pretty good.

Here's the full program in case anyone can and wants to test it:

```
REPORT z_adler_checksum.

DATA:
  lt_i TYPE TABLE OF i WITH HEADER LINE, "Input table
  l_l  TYPE zz, "Calculation and return variable
  l_h  TYPE zz. "Calculation variable

DO 1040 TIMES. "Filling the table for the last test case in the original post
  APPEND 63 TO lt_i.
ENDDO.

PERFORM a TABLES lt_i USING l_l l_h. "Calling the function

WRITE l_l. "Output of the result

FORM a TABLES t USING l h.
  l = 1.
  LOOP AT t.
    ADD: t TO l,
         l TO h.
  ENDLOOP.
  l = l MOD 65521 + 65536 * ( h MOD 65521 ).
ENDFORM.

```

# Answer
> 1 votes
# K (ngn/k), 32 bytes

```
{+/1 65536*65521!(*|x),+/x:1+\x}

```

Try it online!

# Answer
> 1 votes
# Husk, 22 bytes

```
+*□256₁m→∫¹₁:1
%65521Σ

```

Try it online!

May be shorter with a lambda.

## Explanation

```
%65521Σ Function ₁:
      Σ sum of elements of the argument
%65521Σ modulo 65521

+*□256₁m→∫¹₁:1 main program:
           ₁:1 prepend 1(to the input), apply Function ₁
+              plus
         ∫¹    cumulative sums of the input
       m→      increment each sum
      ₁        apply function 1
 *□256         multiply with 256² (65536)

```

# Answer
> 0 votes
## Scala, 94 Bytes

```
(s:String)=>{
val t=((1L,0L)/:s){(r,c)=>val a=(c+r._1)%65521
(a,(a+r._2)%65521)};t._1+(t._2<<16)
}

```

Performs Adler-32 Checksum on Strings, using the alternate for foldLeft, /:

# Answer
> 0 votes
# Postgresql, 164 bytes

```
SELECT t,((SUM(b)+1)%65521)+65536*(SUM(1+b*(LENGTH(t)-r+1))%65521)
FROM v,LATERAL generate_series(1,LENGTH(t))r
,LATERAL(SELECT ASCII(SUBSTRING(t,r,1))b)z GROUP BY t;

```

`**`SqlFiddleDemo`**`

Output:

```
╔═══════════════════════════════════╦════════════╗
║                t                  ║  ?column?  ║
╠═══════════════════════════════════╬════════════╣
║ PostgreSQL can handle it          ║ 1850149040 ║
║ ?(x1040)                          ║ 2181038080 ║
║ Programming Puzzles & Code Golf   ║ 3133147946 ║
║ Eagles are great!                 ║  918816254 ║
║ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  ║   68095937 ║
╚═══════════════════════════════════╩════════════╝

```

---

Version with parameter as subquery:

```
SELECT((SUM(b)+1)%65521)+65536*(SUM(1+b*(LENGTH(t)-r+1))%65521)
FROM(SELECT text'Eagles are great!'t)s,LATERAL generate_series(1,LENGTH(t))r
,LATERAL(SELECT ASCII(SUBSTRING(t,r,1))b)z;

```

`**`SqlFiddleDemo2`**`

# Answer
> 0 votes
# Forth (gforth), 117 bytes

```
: f 2dup bounds 1 -rot do i c@ + loop 65521 mod -rot dup 0 do i for over i + c@ + next loop 65521 mod nip 65536 * + ;

```

Try it online!

### Code explanation

```
: f                 \ start a new word definition
\ Calculate Low:
  2dup bounds       \ copy the string start address and length and get string end address
  1 -rot            \ start an accumulator to hold low (initialize to 1)
  do                \ loop from start address to end-address
    i c@ +          \ get ascii value for each char and add to accumulator
  loop              \ end loop
  65521 mod -rot    \ get value % 65521 to get Low and move off top of stack

\ Calculate High:
  dup 0 do          \ loop from 0 to string-length - 1
    i for           \ loop from outer-loop index to 0
      over i +      \ get address of current ascii char
      c@ +          \ get value of current char and add to total
    next            \ end inner loop
  loop              \ end outer loop
  65521 mod         \ get value % 65521 to get High
  nip               \ remove extraneous value from stack

\ Calculate Checksum
  65536 * +         \ multiply High by 65536 and add to Low
;                   \ end word definition

```

# Answer
> 0 votes
# Japt, 23 bytes

```
[UåÄ Up1]®x uFnG²²ÃìG²²

```

Try it

# Answer
> 0 votes
# Rockstar, 156 bytes

```
listen to N
T's1
C's0
while N
let T be+N-0
let C be+T
listen to N

X's65521
let M be C/X
turn down M
let C be-M*X
let M be T/X
turn down M
say T-M*X+C*65536

```

Try it here (Code will need to be pasted in, with input as newline separated codepoints)

# Answer
> 0 votes
# Thunno 2, 16 bytes

```
ṡ⁺S$S⁺,»¢¢ȯ»%ɠ²ḋ

```

Try it online!

Port of Leaky Nun's Jelly answer.

#### Explanation

```
ṡ⁺S$S⁺,»¢¢ȯ»%ɠ²ḋ  # Implicit input
ṡ⁺                # Cumulative sums, increment
  S               # Sum the resulting list
   $S⁺,           # Pair with sum(input) + 1
       »¢¢ȯ»%     # Mod by 65521
             ɠ²ḋ  # Convert from base 65536
                  # Implicit output

```

---
Tags: code-golf, math, arithmetic, checksum
---