title: Generate a parity bit

text:
# Question
Title: Generate a parity bit
A parity bit, is one of the simplest forms of a checksum. First, you have to pick the parity, even or odd. Let's say we pick even. Now, we need a message to transmit. Let's say our message is "Foo". This is written in binary as:

```
01000110 01101111 01101111

```

Now, we count the total number of `1`'s in there, which is 15. Since 15 is an odd number, we must add one extra bit to the end of our message, and we will now have an even number of 'on' bits. This last added bit is known as the "parity bit". If we had picked an odd parity for our checksum, we would have to add an extra '0' so that the number of on bits remains odd.

# The challenge:

You must write a program or function that determines what the correct parity bit for a string is. Your program must take two inputs:

* A string, `s`. This is the message that the checksum will be calculated on. This will be restricted to the 95 printable ASCII characters.
* A character or single character string `p`, that will either be `e` for even parity, or `o` for odd parity.

and produce a truthy-falsey value representing the correct parity bit. Truthy if it's a `1`, and falsey if it's a `0`.

Builtins that count the number of "on" bits in a string or character are not allowed. For example, a function `f` that does this: `f('a') == 3` or `f('foo') == 16` is banned. Anything else, such as base conversion, is fair game.

# Test IO:

```
(without the quotes)
s: "0"
p: 'e'
output: 0

s: "Foo"
p: 'e'
output: 1

s: "Hello World!"
p: 'o'
output: 0

s: "Alex is right"
p: 'e'
output: 1

s: "Programming Puzzles and Code-Golf"
p: 'e'
output: 0

s: "Programming Puzzles and Code-Golf"
p: 'o'
output: 1

```

This is codegolf, so standard loopholes apply, and the shortest answer in bytes wins.

# Leaderboard

```
var QUESTION_ID=78569,OVERRIDE_USER=31716;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
# MATL, ~~8~~ 7 bytes

```
8\hBz2\

```

Try it online! Or verify all test cases at once.

```
8\    % Implicitly take first input ('e' or 'o'), and compute modulo 8. Inputs 'e' and 'o'
      % give 5 or 7 respectively, which have an even or odd number of `1` bits resp.
h     % Implicitly take second input, and concatenate
B     % Convert to binary. Gives 2D array, with one row for each original entry
z     % Number of nonzero values in that 2D array
2\    % Modulo 2, i.e. compute parity

```
> 9 votes

# Answer
## Java, 97 bytes

Because, ya know, Java.

```
(s,c)->{boolean e=1>0;for(int i:s.getBytes())while(i>0){if(i%2==1)e=!e;i/=2;}return c=='o'?e:!e;}

```

This is a lambda for a `BiFunction<String, Character, Boolean>`.

`e` and `o` appear to be reversed in the return statement because apparently my logic was backwards.
> 9 votes

# Answer
# C, 62 bytes

* 12 bytes saved thanks to @LevelRiverSt and @TonHospel.

XOR has the nice property that it can be used to reduce strings down to one char, while preserving parity.

```
f(s,p)char*s;{for(p/=8;*s;)p^=*s>>4^*s++;p^=p/4;return p%4%3;}

```

Ideone.
> 5 votes

# Answer
## Python 2, 51 bytes

```
lambda s,p:`map(bin,map(ord,p+s))`[9:].count('1')%2

```

This is based on an idea of Sp3000 to count 1's in the string representation of the list of character codes in binary rather than summing for each character.

The new trick is to handle `e` and `o` in this as well. If `e` was odd and `o` even, we could just prepend the parity bit to the string before doing the count (flipping them because '1' is Truthy). Unfortunately, they are not. But, if we remove all but their last two bits, it's now true.

```
e 0b11001|01
o 0b11011|11

```

This is done by removing the first `9` character of the string representation.

```
['0b11001|01',

```
> 5 votes

# Answer
# Python, 58 57 bytes

```
lambda s,p:sum(bin(ord(c)).count("1")for c in s)&1!=p>'e'

```
> 4 votes

# Answer
## Jelly, ~~9~~ 8 bytes

```
OBFSḂ⁼V}

```

Try it online!

```
O         convert each character in argument 1 (left arg) to its codepoint (ord)
 B        convert to binary (list of 0s and 1s)
  F       flatten
   S      sum the entire list, giving the number of 1s in the entire string
    Ḃ     mod 2 (take the last bit)
       }  now, with the second (right) argument...
      V   eval with no arguments. This returns...
            1 for e because it expands to 0e0 (i.e., does 0 exist in [0])
            0 for o because it expands to 0o0 (0 OR 0, false OR false, false)
     ⁼    test equality between the two results

```

Thanks to Dennis for a byte!
> 4 votes

# Answer
## Pyth, 12 bytes

```
q@"oe"sjCz2w

```

Test suite.

```
         z    take a line of input
        C     convert to int
       j  2   convert to base 2, array-wise (so, array of 0s and 1s)
      s       sum (count the number of ones)
 @"oe"        modular index into the string to get either "o" or "e"
q          w  test equality to second line of input

```
> 3 votes

# Answer
## JavaScript (ES6), ~~84~~ 72 bytes

```
(s,p)=>(t=p>'e',[...s].map(c=>t^=c.charCodeAt()),t^=t/16,t^=t/4,t^t/2)&1

```

Bit twiddling turned out to be shorter than converting to base 2 and counting `1`s.
> 3 votes

# Answer
# IA-32 machine code, 15 bytes

Hexdump:

```
0f b6 c2 40 32 01 0f 9b c0 3a 21 41 72 f6 c3

```

Assembly code:

```
    movzx eax, dl;
    inc eax;
repeat:
    xor al, [ecx];
    setpo al;
    cmp ah, [ecx];
    inc ecx;
    jb repeat;
    ret;

```

This is a function that receives its first argument (string) in `ecx` and second argument (char) in `dl`. It returns the result in `eax`, so it's compatible with the `fastcall` calling convention.

This code bends the rules when it uses the `setpo` instruction:

> Builtins that count the number of "on" bits in a string or character are not allowed

This instruction sets `al` to the parity bit calculated by the previous instruction - so I have these two nitpicks on the rules:

* It doesn't count the number of "on" bits - it calculates the parity bit directly!
* Technically, it's the previous instruction (`xor`) that calculates the parity bit. The `setpo` instruction only moves it to the `al` register.

These semantic details out of the way, here is the explanation on what the code does.

The representations of the characters are:

```
'e' = 01100101
'o' = 01101111

```

If we add 1 to them, they happen to have just the right parity:

```
'e' + 1 = 01100110 (odd parity)
'o' + 1 = 01110000 (even parity)

```

So we `XOR` all the characters of the string, initializing `al` to these values, which gives the answer.

---

The first instruction is `movzx eax, dl` instead of the more obvious (and shorter) `mov al, dl`, because I want to have the number 0 in a register (`ah` in this case) in order to be able to compare it in the right order (`0, [ecx]` rather than `[ecx], 0`).
> 3 votes

# Answer
## Perl, 29 bytes

Includes +2 for `-p`

Run with the input on STDIN as parity character space string, e.g.

```
parity.pl <<< "p Programming Puzzles and Code-Golf"

```

`parity.pl`

```
#!/usr/bin/perl -p
$_=unpack"B*",$_|b;$_=1&y;1;

```
> 2 votes

# Answer
# J, 27 bytes

```
'oe'&i.@[=[:~:/^:2@#:3&u:@]

```

## Usage

```
   f =: 'oe'&i.@[=[:~:/^:2@#:3&u:@]
   'e' f '0'
0
   'e' f 'Foo'
1
   'o' f 'Hello World!'
0
   'e' f 'Alex is right'
1
   'e' f 'Programming Puzzles and Code-Golf'
0
   'o' f 'Programming Puzzles and Code-Golf'
1

```
> 2 votes

# Answer
# JavaScript (ES6), 69 bytes

```
(s,p)=>[...s].map(c=>{for(n=c.charCodeAt();n;n>>=1)r^=n&1},r=p>"e")|r

```
> 1 votes

# Answer
# Julia, ~~58~~ ~~47~~ ~~45~~ 40 bytes

```
f(s,p)=(p>'e')$endof(prod(bin,s)∩49)&1

```

This is a function that accepts a string and a character and returns an integer.

To get the number of ones in the binary representation, we first apply the `bin` function to each character in the string, which gives us an array of binary strings. Then reduce them into one using `prod` (since `*` is string concatenation in Julia) and take the set intersection of that string and the character code for `1`, which gives us a string of ones. The last index of that string is the number of ones. We XOR this with 1 if the provided character is *o* and 0 otherwise, then get the parity using bitwise AND 1.

Try it online! (includes all test cases)

Saved 18 bytes thanks to Dennis!
> 1 votes

# Answer
## PowerShell v2+, 91 bytes

<sub>*/me cries in a corner*</sub>

```
param([char[]]$a,$b)$b-eq'o'-xor(-join($a|%{[convert]::toString(+$_,2)})-replace0).length%2

```

Yeah ... so, base conversion is not a strong suit for PowerShell. The conversion from input string to binary representation `$a|%{[convert]::toString(+$_,2)}` is 32 bytes in and of itself ...

Takes input `$a` and `$b`, explicitly casting `$a` as a char-array in the process. We then check whether `$b` is `-eq`ual to `o`, and `-xor` that with the other half of the program. For that part, we take the input string `$a`, pipe it through a loop to convert each letter to binary, `-join` all those together to form one solid string, and `-replace` all the `0`s with nothing. We then count the `.length` of that string and take it mod-2 to determine if it's even or odd, which will conveniently be either `0` or `1`, perfect for the `-xor`.

Will return `True` or `False` accordingly. See test cases below:

```
PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "0" e
False

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Foo" e
True

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Hello World!" o
False

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Alex is right" e
True

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Programming Puzzles and Code-Golf" e
False

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Programming Puzzles and Code-Golf" o
True

```
> 1 votes

# Answer
# Factor, 85 bytes

For some reason I couldn't wrap my head around this one until a few minutes ago, when I simplified (and maybe shortened?) the code.

```
[ "e" = [ even? ] [ odd? ] ? [ [ >bin ] { } map-as concat [ 49 = ] count ] dip call ]

```

`?` is like a ternary operator: it tests the truthiness of the third stack item, and either selects the `true` value or the `false` value.

It's roughly equivalent to the following C-like pseduocode:

```
void* parity_tester_function = strcmp(p, "e") ? (void *) even?  // it's a function pointer (I think)
                                              : (void *) odd? ;

```

The rest of the code is pretty simple:

```
[                       ! to count a string's set bits:
    [ >bin ] { } map-as ! get the binary of each character, and map as an array, because you can't have stringy data nested in another string (that's called a type error)
    concat              ! { "a" "B" } concat -> "aB"
    [ 49 = ] count      ! count items in the resulting string which match this condition (in this case, the condition we're testing is whether the character has the same code point as "1")
] dip                   ! take the above function pointer off the stack, apply this anonymous function to the now-top of the stack, then restore the value after the quotation finishes.
                        ! in other words, apply this quotation to the second-to-top item on the stack
call                    ! remember that conditionally chosen function pointer? it's on the top of the stack, and the number of sets bits is second.
                        ! we're gonna call either odd? or even? on the number of set bits, and return the same thing it does.

```
> 1 votes

# Answer
## 05AB1E, ~~15~~, 13 bytes

**Code:**

```
€ÇbSOÈ„oe²k<^

```

**Example Input:**

```
Programming Puzzles and Code-Golf
o

```

**Example Output:**

```
1

```

**Explanation:**

```
€                 # for each char in string
 Ç                # get ascii value
  b               # convert to binary
   S              # split to single chars (ex: '1101' to '1','1','0','1')
    O             # sum
     È            # check if even
      „oe         # push string "oe"
         ²        # push 2nd input (p)
          k       # get 1-based index of p in "oe"
           <      # decrease (to get either 0-based index)
            ^     # xor with result of È

```

Thanks to Adnan for saving 2 bytes.
> 1 votes

# Answer
**Bash and unix tools (72 bytes)**

```
f(){ bc<<<"$(xxd -b<<<"$2$1"|cut -b9-64|tail -c +7|tr -dc 1|wc -c)%2" }

```

Excepts `s` as the first and `p` as the second argument. Fortunately the last 3 bits of `o` and `e` has odd and even parity respectively.

```
xxd -b        print the concatenation of `p` and `s` in binary
cut -b9-64    parse xxd output
tail -c +7    keep only the last 3 bits of `p`
tr -dc 1      keep only the `1`s
wc -c         count them
bc ...%2      modulo two

```

Supplying the input via `<<<` adds a line feed character, but the parity of `\n` is even, so it is not a problem.
> 1 votes

# Answer
# Ruby, 57 bytes

If `0` was falsey in Ruby, the `==` could probably be switched to just `-`, or there could be other optimizations, but it isn't.

```
->s,b{s.gsub(/./){$&.ord.to_s 2}.count(?1)%2==(b>?i?0:1)}

```
> 0 votes

# Answer
# Retina, 102 bytes

Takes the string on the first line, and the letter on the second line. Uses ISO 8859-1 encoding.

```
[12478abdghkmnpsuvyzCEFIJLOQRTWX#%&)*,/;=>@[\]^| ](?=.*¶)
1
[^1](?=.*¶)
0
^(0|10*1)*¶o|^0*1(0|10*1)*¶e

```

**Try it online**

The character class on the first line matches any character with an odd number of ones in the binary representation.

Description of how even/odd detection with regex works here.
> 0 votes

# Answer
# Octave, 56 bytes

```
f=@(s,p) mod(sum((i=bitunpack([s p]))(1:length(i)-5)),2)

```

The `bitunpack` function, for ASCII characters, returns them in little-endian order. So by putting the parity flag at the end of our string, unpacking the whole thing, and dropping the last 5 bits, we can then sum up the whole thing mod 2 for our ultimate answer.

Usage:

```
octave:137> f('Hello World!', 'o')
ans = 0
octave:138> f('Hello World!', 'e')
ans =  1

```
> 0 votes

# Answer
## Common Lisp, 87

```
(lambda(s p)(=(mod(reduce'+(mapcar'logcount(map'list'char-code s)))2)(position p"oe")))

```
* Sum the logcount of char-codes of `s`.
* The remainder of this, when divided by 2, is compared to the position of the parity argument `p` in the string `"oe"` (either 0 or 1). For example, if there are 4 ones, the remainder is zero. If p is `o`, then no additional bit should be added, and the test return false.

### Pretty-printed

```
(lambda (s p)
  (= (mod (reduce '+ (mapcar 'logcount (map 'list 'char-code s))) 2)
     (position p "oe")))

```
> 0 votes

# Answer
# Java, 91 bytes

```
(s,c)->{s+=c%8;int e=1;for(int i:s.getBytes())while(i>0){if(i%2==1)e^=1;i/=2;}return e==0;}

```

I did the same as @CAT97, but stripped some characters by using the modulo 8 and concatenate of @Luis Mendo and the use of int instead of boolean.

This is a lambda for a `BiFunction<String, Character, Boolean>`.
> 0 votes

# Answer
## Matlab, 49 bytes

```
f=@(x,p)mod(sum(sum(dec2bin(x)-'0'))+(p-'e'>0),2)

```

where:

* x is the input string;
* p is 'e' for even parity and 'o' for the odd one.

For example:

```
>> f('Programming Puzzles and Code-Golf','e')

ans =

     0

```
> 0 votes

---
Tags: code-golf, string, bitwise, checksum
---


title: Symme-Try This Triangle Trial

text:
# Question
Title: Symme-Try This Triangle Trial
A string whose length is a positive triangular number (1, 3, 6, 10, 15...) can be arranged into an "equilateral text triangle" by adding some spaces and newlines (and keeping it in the same reading order).

For example, the length 10 string `ABCDEFGHIJ` becomes:

```
   A
  B C
 D E F
G H I J

```

Write a program or function that takes in such a string, except it will only contains the characters `0` and `1`. (You may assume the input is valid.)

For the resulting "equilateral text triangle", output (print or return) one of four numbers that denotes the type of symmetry exhibited:

* Output `2` if the triangle has bilateral symmetry. i.e. it has a line of symmetry from any one corner to the opposite side's midpoint.

Examples:

```
 0
1 1

 1
0 1

  0
 0 1
0 1 0

   1
  1 1
 1 0 1
0 1 1 1

```
* Output `3` if the triangle has rotational symmetry. i.e. it could be rotated 120° with no visual change.

Examples:

```
   0
  1 0
 0 1 1
0 1 0 0

   0
  0 1
 1 0 0
0 0 1 0

    1
   0 1
  1 1 1
 1 1 1 0
1 0 1 1 1

     1
    0 1
   0 0 1
  1 0 0 0
 1 0 0 0 0
1 0 0 1 1 1

```
* Output `6` if the triangle has **both** bilateral and rotational symmetry. i.e. it matches the conditions for outputting both `2` and `3`.

Examples:

```
0

1

 0
0 0

  1
 0 0
1 0 1

   0
  0 0
 0 1 0
0 0 0 0

```
* Output `1` if the triangle has neither bilateral nor rotational symmetry.

Examples:

```
  1
 1 0
0 0 0

  0
 0 1
1 0 1

   1
  1 0
 1 1 1
1 1 1 1

    1
   1 1
  1 1 1
 0 0 0 1
1 1 1 1 1

```

**The shortest code in bytes wins. Tiebreaker is earlier answer.**

Aside from an optional trailing newline, the input string may not have space/newline padding or structure - it should be plain `0`'s and `1`'s.

If desired you may use any two distinct printable ASCII characters in place of `0` and `1`.

# Test Cases

Taken direct from examples.

```
011 -> 2
101 -> 2
001010 -> 2
1111010111 -> 2
0100110100 -> 3
0011000010 -> 3
101111111010111 -> 3
101001100010000100111 -> 3
0 -> 6
1 -> 6
000 -> 6
100101 -> 6
0000100000 -> 6
110000 -> 1
001101 -> 1
1101111111 -> 1
111111000111111 -> 1

```

"Rotating" any input by 120° will of course result in the same output.

# Answer
## CJam, ~~37~~ ~~29~~ ~~28~~ 27 bytes

*Thanks to Sp3000 for saving 3 bytes.*

```
q{T):T/(\s}h]{z_Wf%_}3*])e=

```

Test suite.

This reuses some triangle rotation tricks from this challenge.

This also works for the same byte count:

```
q{T):T/(\s}h]3{;z_Wf%_}%)e=

```

### Explanation

First, a quick recap from the triangle post I linked to above. We represent a triangle as a 2D (ragged) list, e.g.

```
[[0 1 1]
 [0 0]
 [0]]

```

The symmetry group of the triangle has 6 elements. There are cycles of length 3 by rotating the triangle and cycles of 2 by mirroring it along some axis. Conveniently, the rotations correspond to perform to two different reflections. We will use the following reflections to do this:

1. Transpose the list means reflecting it along the main diagonal, so we'd get:

```
[[0 0 0]
 [1 0]
 [1]]

```
2. Reversing each row represents a reflection which swaps the top two corners. Applying this to the result of the transposition we get:

```
[[0 0 0]
 [0 1]
 [1]]

```

Using these two transformations, and keeping the intermediate result, we can generate all six symmetries of the input.

A further point of note is the behaviour of transposition on a list like this:

```
[[0]
 [1 0]
 [1 0 0]
 []]

```

Because that's what we'll end up with after splitting up the input. Conveniently, after transposing, CJam flushes all lines to the left, which means this actually gets rid of the extraneous `[]` and brings it into a form that's useful for the above two transformations (all without changing the actual layout of the triangle beyond reflectional symmetry):

```
[[0 1 1]
 [0 0]
 [0]]

```

With that out of the way, here's the code:

```
q       e# Read input.
{       e# While the input string isn't empty yet...
  T):T  e#   Increment T (initially 0) and store it back in T.
  /     e#   Split input into chunks of that size.
  (     e#   Pull off the first chunk.
  \s    e#   Swap with remaining chunks and join them back together
        e#   into a single string.
}h
]       e# The stack now has chunks of increasing length and an empty string
        e# as I mentioned above. Wrap all of that in an array.
{       e# Execute this block 3 times...
  z_    e#   Transpose and duplicate. Remember that on the first iteration
        e#   this gets us a triangle of the desired form and on subsequent
        e#   iterations it adds one additional symmetry to the stack.
  Wf%_  e#   Reverse each row and duplicate.
}3*
        e# The stack now has all 6 symmetries as well as a copy of the
        e# last symmetry.
]       e# Wrap all of them in a list.
)       e# Pull off the copy of the last symmetry.
e=      e# Count how often it appears in the list of symmetries.

```
> 10 votes

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


title: QWERTY Quine Creation

text:
# Question
Title: QWERTY Quine Creation
### Challenge

Create a quine, that instead of outputting it's source, output's it's source QWERTY-sorted.

### What is QWERTY sorting?

QWERTY sorting is sorting code by the QWERTY keyboard. Anything higher or more left is greater (`q` \> `Q`, `\` \> `/`) with presedence on higher. To check, find the locations of the two characters to compare. Find which character occurs first in the following table (left to right, up to down). The first character is the smaller one.

```
qwertyuiop[]\
asdfghjkl;'
zxcvbnm,./
QWERTYUIOP{}|
ASDFGHJKL:"
ZXCVBNM<>?
1234567890-=!@#$%^&*()_+~`

```

(there is a trailing space and linefeed)

Examples:

```
Code Golf -> eoodflGC
Programming -> rroiagnmmP

```

(note trailing space on `Code Golf`)

### Specifications

* Only characters in the above list are allowed in the source code!
* This is .
* Only Proper Quines are allowed (adapted to QWERTY sort).
* Output must be in *increasing* QWERTY order.

# Answer
> 3 votes
# CJam, ~~25~~ 23 bytes

```
{`"_~"+{"#$_+~`"`#}$}_~

```

*Thanks to @MartinBüttner for golfing off 2 bytes!*

Try it online!

### How it works

{                   }_~  Define, copy and execute a code block.

   `                       Create a string representation of the code block.
  "_~"+                    Append that string.
       {          }$       Sort the characters by the following:
        "#$_+~`"`#           Compute the 0-based index of the character in that
                             string. Returns -1 if not found.
                           Since `$' is stable, all characters with tied index -1
                           will appear at the beginning, in their original order.
                           This places {{}} at the beginning, followed by
                           """"##$$___++~~~```.

---
Tags: code-golf, string, restricted-source, quine, sorting
---


title: Correct using a Parity Block

text:
# Question
Title: Correct using a Parity Block
For more information on Parity: Wikipedia

# Challenge

Write a program that takes an input (stdin, argv, ect) of four nibbles and two parity nibbles. Your program should then test to see whether the 'block' is valid, using **even parity**; if it is then output `1`. Then try to make any corrections, if correction is possible output the corrected block. If you cannot correct the block output `-1`. You can assume **the parity nibbles are never corrupt**.

To re-cap and clarify:

* If the input is valid output `1`.
* If the input is invalid and fixable output the fixed block.
* If the input is invalid and cannot be fixed output `-1`.
* You can only edit bits if their respective row and column in the parity bit is incorrect.

Input Format:

```
<NIBBLE> <NIBBLE> <NIBBLE> <NIBBLE> <PARITY-Y> <PARITY-X>

```

So `1010 0111 1101 1011 1011 0111` Would look like:

# Winning

This is : Smallest program wins.

# Input and Output Examples

Input `1010 0111 1101 1011 1011 0111`
Output `1`
The Input is Valid

Input `1010 0011 1101 1011 1011 0111`
Output `1010 0111 1101 1011`
The Input was Invalid, but correctable

Input `1010 0001 1101 1011 1011 0111`
Output `-1` The Input was Invalid, and not correctable

# Answer
> 3 votes
# Python 2, 387

I feel it's kinda long though. Do suggest improvements or any fixes...

```
i=raw_input()
z="""#h(a?(a&1)^h(a/2)~a@0
#y(i,m,l,c=0?h(i&m)|y(i>>l,m,l,c+1)*2~c<4@0
#p(i?y(i,4369,1)*16+y(i,15,4)
k=i.replace(" ","")
m=int(k[:16],2)
c=int(k[-8:],2)
#s(i?s(i>>4)+" "+bin(i&15^16)[3:]~i@""
#q(j=16):d=m^1<<j;!s(d)[1:]~p(d)==c@q(j-1)~j@-1
#f(?1~p(m)==c@q()"""
for k,l in("?","):!"),("!","return "),("@"," else "),("#","def "),("~","if "):z=z.replace(k,l)
exec z
print f()

```

Slightly ungolfed...

```
def y(i,m,l,c=0):
    h=lambda a:(a&1)^h(a/2)if a else 0 # Calculate how many set bits in i
    return h(i&m)|y(i>>l,m,l,c+1)*2if c<4 else 0 # Sets the parity bits accordingly recursively

p=lambda i:y(i,4369,1)*16+y(i,15,4) # Returns the y and x parity together

i="1010 0111 1101 1011 1011 0111"

k=i.replace(" ","") # Remove all spaces
m=int(k[:16],2)     # Extracts the matrix
c=int(k[-8:],2)     # Extracts the parities

s=lambda i:s(i>>4)+" "+bin(i&15^16)[3:]if i else""
# Converts from int to space separated hexas in binary

def f(i):
    if p(m)==c:return 1 # If calculated parities matches the test
    for i in range(16): # Else, for each of the 16 bits in the matrix
        d=m^1<<i        # xor it
        if p(d)==c:return s(d)[1:] # return the matrix if its parities matches the test
    return -1 # If all else fails, return -1

print f(i)

```

# Answer
> 0 votes
## JavaScript (ES6), 234 bytes

```
s=>(a=s.split` `,[...a.pop()].map((c,i)=>a[i]+=c),x=y=0,[...a].map((s,i)=>[...s].map((c,j)=>{x^=c<<i;y^=c<<j})),x&=15,y&=15,a.pop(),x|y?x-(x&-x)|y-(y&-y)?-1:[...a].map((s,i)=>s.slice(0,4).replace(/./g,(c,j)=>c^x>>i&y>>j&1)).join` `:1)

```

Save 21 bytes if an array of strings is an acceptable I/O format, or 46 bytes if a two-dimensional array of bits is acceptable. Explanation: The original string is split into blocks and then rearranged into an almost square formation:

```
DDDDX
DDEDX
DDDDX
DDDDX
YYYY

```

The row and column parities are then calculated, each setting the appropriate bit in the `x` and `y` variables, so for instance if the error was in the bit marked `E` it would set `x` to 2 and `y` to 4. (If the parity of the parity blocks was also provided, then it could also be checked, and an error in the parity blocks or indeed the parity bit itself could be detected. The two parity blocks should have the same parity, of course.)

```
s=>(                    String parameter
 a=s.split` `,          Split it into blocks
 [...a.pop()]           Remove the X parity block and loop over it
  .map((c,i)=>a[i]+=c), Append the X parity bits to the data blocks
 x=y=0,                 Initialise the X and Y parity
 [...a].map((s,i)=>     Loop over rows
  [...s].map((c,j)=>     and columns
   {x^=c<<i;y^=c<<j})),   updating the parity
 x&=15,y&=15,           Only bits 0-3 are important
 a.pop(),               Remove the Y parity block
 x|y?                   If there were parity errors
  x-(x&-x)|y-(y&-y)?-1:  If there were several errors then return -1
   [...a].map((s,i)=>     If there was one error then loop over blocks
    s.slice(0,4)           Removing the X parity bit
     .replace(/./g,(c,j)=>  Loop over bits
      c^x>>i&y>>j&1))        Flip the bit if it was the incorrect bit
    .join` `:              Join the blocks together
   1)                    Return 1 if there were no parity errors

```

---
Tags: code-golf, error-correction
---


title: ECHO! Echo! echo. (echo)

text:
# Question
Title: ECHO! Echo! echo. (echo)
Your challenge, should you choose to accept it, is simple:

Implement RFC 862, also known as the Echo Protocol:

## The Echo protocol

An echo service simply sends back to the originating source any data it receives.

### TCP Based Echo Service

One echo service is defined as a connection based application on TCP. A server listens for TCP connections on TCP port 7. Once a connection is established any data received is sent back. This continues until the calling user terminates the connection.

### UDP Based Echo Service

Another echo service is defined as a datagram based application on UDP. A server listens for UDP datagrams on UDP port 7. When a datagram is received, the data from it is sent back in an answering datagram.

### Scoring

* The score is one point for every byte of code as encoded in UTF-8 or a language-specific code page, whichever is smaller.
* If the program incompletely implements RFC 862 by providing only UDP or only TCP, the score is doubled.
* If the program incorrectly implements RFC 862 by either using a port other than 7 or by dropping or transforming certain bytes due to language limitations or corner cutting, the score is quadrupled. (This stacks with the preceding point if applicable.)
* If the program is invalid, the score is .

### Rules

A valid program:

* Does not use standard loopholes.
* Per connection:
    + Accepts connections and receive incoming data.
    + Sends outgoing data in an amount that is always less than or equal to the amount of data received.
* Does not invoke programs external to itself. (Spawning children to deal with multiple connections is fine, spinning up `inetd` or its local equivalent is not.)
* Does not use library functions specifically designed to start and maintain an echo service.

This is code golf, so lowest score wins.

# Answer
> 3 votes
# JavaScript (Node.js) 102 Bytes (51 * 2)

```
require("net").createServer(s=>s.pipe(s)).listen(7)

```

You can add UDP for a total of **132 bytes**, as seen below:

```
require("net").createServer(s=>s.pipe(s)).listen(7),(u=require("dgram").createSocket("udp4")).on("message",msg=>u.send(msg)).bind(7)

```

Was tested on node.js v5.2.0

Make sure to run with `sudo` on Unix descendants (OS X, Linux, etc.)

# Answer
> 4 votes
# Python, ~~299~~ ~~295~~ ~~265~~ 263

```
from threading import*
from socket import*
a='',7;S=socket
u=S(2,2);u.bind(a)
def U():
 while 1:u.sendto(*u.recvfrom(4**8))
Thread(None,U).start()
def C(c,x):
 while c.send(c.recv(1)):1
s=S(2,1);s.bind(a);s.listen(1)
while 1:Thread(None,C,args=s.accept()).start()

```

handles both udp and tcp.

@MorganThrapp helped saving 33 (!) chars

# Answer
> 3 votes
# Racket, 231

```
(thread(λ()(do([l(tcp-listen 7)])(#f)(let-values([(i o)(tcp-accept l)])(copy-port i o)))))((λ(s b)(udp-bind! s #f 7)(do()(#f)(let-values([(n h p)(udp-receive! s b)])(udp-send-to s h p b 0 n))))(udp-open-socket)(make-bytes 65535))

```

TCP and UDP.

The TCP echo server uses a handy Racket procedure named `copy-port` that copies ports in the background, managed by Racket, instead of by the programmer. That also means I don't have to spin off a thread for each client, only for the listener (so I can start the UDP listener on the main thread).

---
Tags: code-golf, networking
---


title: Swap Pairs or Remove

text:
# Question
Title: Swap Pairs or Remove
## Specification

For this challenge you will:

* Take an array of positive integers.
* For each overlapping pair in the array, calculate the difference of it's integers. If the difference is a common divisor of the integers (they are both divisible by their difference), swap their positions in the array. The values of the next pair are affected by this swap. No integer is divisible by `0`.
* If an integer was not divisible by the difference of any of it's pairs, remove it from the array.
* Repeat the previous two steps until the length of the array will not decrease any further.
* Output the length of the resulting array.

## Example

* Input = `[ 4, 5, 2, 4 ]`.
* Difference of first pair `[ ( 4, 5, ) 2, 4 ]` = `1`, (common divisor of `4` and `5`)
    + Swap the pair and the array becomes `[ 5, 4, 2, 4 ]`.
* Difference of second pair `[ 5, ( 4, 2, ) 4 ]` = `2` (common divisor of `4` and `2`)
    + Swap the pair so the array becomes `[ 5, 2, 4, 4 ]`.
* Difference of third pair `[ 5, 2, ( 4, 4 ) ]` = `0` (not a divisor of any integer)
    + Do not swap the pair so the array remains the same.
* The final `4` was never swapped, remove it so the array becomes `[ 5, 2, 4 ]`.
* Repeat.
* Difference of first pair `[ ( 5, 2, ) 4 ]` = `3`
    + Do not swap the pair so the array remains the same.
* Difference of second pair `[ 5, ( 2, 4 ) ]` = `2`
    + Swap the pair so the array becomes `[ 5, 4, 2 ]`.
* The `5` was never swapped, remove it so the array becomes `[ 4, 2 ]`
* Repeat.
* From here the array will endlessly switch between `[ 4, 2 ]` and `[ 2, 4 ]`, so output the resulting length of `2`.

## Rules

* Input array will always have a length between 2 and 9 inclusive.
* Integers will always be between 1 and 999 inclusive.
* Input can optionally be in the form of a string delimited by a specific character.
* This is so shortest code in bytes wins.

## Test Cases

Format: `[ input array ] = result (steps to get result, do not output this)`

```
[ 1, 1 ] = 0                        ([])
[ 1, 2 ] = 2                        ([ 2, 1 ] -> [ 1, 2 ] -> ...)
[ 1, 2, 3 ] = 2                     ([ 2, 1 ] -> [ 1, 2 ] -> ...)
[ 4, 6, 8 ] = 3                     ([ 6, 8, 4 ] -> [ 8, 4, 6 ] -> [ 4, 6, 8 ] -> ...)
[ 99, 1, 3 ] = 0                    ([])
[ 4, 5, 2, 4 ] = 2                  ([ 5, 2, 4 ] -> [ 4, 2 ] -> [ 2, 4 ] -> ...)
[ 12, 4, 6, 3 ] = 3                 ([ 6, 4, 3 ] -> [ 4, 3, 6 ] -> [ 3, 6, 4 ] -> ...)
[ 9, 6, 10, 18 ] = 2                ([ 6, 10, 18, 9 ] -> [ 9, 18 ] -> [ 18, 9 ] -> ...)
[ 55, 218, 654, 703, 948, 960 ] = 2
[ 954, 973, 925, 913, 924, 996, 927, 981, 905 ] = 2

```

# Answer
# JavaScript (ES6), 133

Recursive function.

```
F=(m,k=[])=>(k[m]=m,f=m.map((x,i)=>x%(w=x-(y=m[i+1]))==0&y%w==0?m[m[i]=y,i+1]=x:0),k[m=m.filter((x,i)=>f[i-1]|f[i])]?m.length:F(m,k))

```

*Less golfed and not recursive*

```
F=m=>{
  for(k=[];!k[m];) // use k to find a repeated state and exit the loop
  {
    k[m]=1
    console.log(m)
    // loop for swap and mark swap position in array f
    f=m.map((x,i)=>(
      y=m[i+1], // next element
      w=x-y,    // difference
      x%w==0&y%w==0 // if common divisor ...
        ?m[m[i+1]=x,i]=y // swap elements,mark with nonzero
        :0 // no swap, mark with 0
    ))
    m=m.filter((x,i)=>f[i-1]|f[i]) // remove elements not swapped
  }
  return m.length
}

```

**Test**

```
F=(m,k=[])=>(k[m]=m,f=m.map((x,i)=>x%(w=x-(y=m[i+1]))==0&y%w==0?m[m[i]=y,i+1]=x:0),k[m=m.filter((x,i)=>f[i-1]|f[i])]?m.length:F(m,k))

console.log=x=>O.textContent+=x+'\n'

;[[1,1],[1,2],[1,2,3],[4,6,8],[99,1,3],[4,5,2,4],[12,4,6,3],[9,6,10,18]
,[ 55, 218, 654, 703, 948, 960 ],[ 954, 973, 925, 913, 924, 996, 927, 981, 905 ]]
.forEach(t=>console.log(t+' -> '+F(t)))
```

```
<pre id=O></pre>
```
> 2 votes

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


# Question
Title: Calculate the Kronecker sum of two matrices
In the examples below, `A` and `B` will be 2-by-2 matrices, and the matrices are one-indexed.

A Kronecker *product* has the following properties:

```
A⊗B =  A(1,1)*B   A(1,2)*B
        A(2,1)*B   A(2,2)*B

     =  A(1,1)*B(1,1)   A(1,1)*B(1,2)   A(1,2)*B(1,1)   A(1,2)*B(1,2)
        A(1,1)*B(2,1)   A(1,1)*B(2,2)   A(1,2)*B(2,1)   A(1,2)*B(2,2)
        A(2,1)*B(1,1)   A(2,1)*B(1,2)   A(2,2)*B(1,1)   A(2,2)*B(1,2)
        A(2,2)*B(2,1)   A(2,2)*B(1,2)   A(2,2)*B(2,1)   A(2,2)*B(2,2)

```

A Kronecker sum has the following properties:

```
A⊕B = A⊗Ib + Ia⊗B

```

`Ia` and `Ib` are the identity matrices with the dimensions of `A` and `B` respectively. `A` and `B` are square matrices. Note that `A` and `B` can be of different sizes.

```
A⊕B =  A(1,1)+B(1,1)  B(1,2)         A(1,2)         0
        B(2,1)         A(1,1)+B(2,2)  0              A(1,2)
        A(2,1)         0              A(2,2)+B(1,1)  B(1,2)
        0              A(2,1)         B(2,1)         A(2,2)+B(2,2)

```

**Given two square matrices, `A` and `B`, calculate the Kronecker sum of the two matrices.**

* The size of the matrices will be at least `2-by-2`. The maximum size will be whatever your computer / language can handle by default, but minimum `5-by-5` input (5 MB output).
* All input values will be non-negative integers
* Builtin functions that calculate the Kronecker sum or Kronecker products are not allowed
* In general: Standard rules regarding I/O format, program & functions, loopholes etc.

**Test cases:**

```
A =
     1     2
     3     4
B =
     5    10
     7     9

A⊕B =
     6    10     2     0
     7    10     0     2
     3     0     9    10
     0     3     7    13

----

A =
    28    83    96
     5    70     4
    10    32    44
B =
    39    19    65
    77    49    71
    80    45    76

A⊕B =
    67    19    65    83     0     0    96     0     0
    77    77    71     0    83     0     0    96     0
    80    45   104     0     0    83     0     0    96
     5     0     0   109    19    65     4     0     0
     0     5     0    77   119    71     0     4     0
     0     0     5    80    45   146     0     0     4
    10     0     0    32     0     0    83    19    65
     0    10     0     0    32     0    77    93    71
     0     0    10     0     0    32    80    45   120

----

A =
    76    57    54
    76     8    78
    39     6    94
B =
    59    92
    55    29

A⊕B =
   135    92    57     0    54     0
    55   105     0    57     0    54
    76     0    67    92    78     0
     0    76    55    37     0    78
    39     0     6     0   153    92
     0    39     0     6    55   123

```

# Answer
> 2 votes
# Jelly, ~~26~~ ~~21~~ ~~20~~ 19 bytes

```
æ*9Bs2¤×€€/€S;"/€;/

```

Input is a list of two 2D lists, output is a single 2D list. Try it online! or verify all test cases.

### How it works

```
æ*9Bs2¤×€€/€S;"/€;/  Main link.
                     Argument: [A, B] (matrices of dimensions n×n and m×m)

      ¤              Evaluate the four links to the left as a niladic chain.
  9B                 Convert 9 to base 2, yielding [1, 0, 0, 1].
    s2               Split into sublists of length 2, yielding [[1, 0], [0, 1]].
æ*                   Vectorized matrix power.
                     This yields [[A¹, B⁰], [A⁰, B¹]], where B⁰ and A⁰ are the
                     identity matrices of dimensions m×m and n×n.
          /€         Reduce each pair by the following:
        €€             For each entry of the first matrix:
       ×                 Multiply the second matrix by that entry.
            S        Sum the two results, element by element.
                     This yields the Kronecker sum, in form of a n×n matrix of
                     m×m matrices.
               /€    Reduce each row of the outer matrix...
             ;"        by zipwith-concatenation.
                     This concatenates the columns of the matrices in each row,
                     yielding a list of length n of n×nm matrices.
                 ;/  Concatenate the lists, yielding a single nm×nm matrix.

```

# Answer
> 5 votes
## CJam, ~~40~~ ~~39~~ 38 bytes

```
9Yb2/q~f{.{_,,_ff=?}:ffff*::.+:~}:..+p

```

Input format is a list containing `A` and `B` as 2D lists, e.g.

```
[[[1 2] [3 4]] [[5 10] [7 9]]]

```

Output format is a single CJam-style 2D list.

Test suite. (With more readable output format.)

### Explanation

This code is an exercise in compound (or infix) operators. These are generally useful for array manipulation, but this challenge exacerbated the need for them. Here is a quick overview:

* `f` expects a list and something else on the stack and maps the following *binary* operator over the list, passing in the other element as the second argument. E.g. `[1 2 3] 2 f*` and `2 [1 2 3] f*` both give `[2 4 6]`. If both elements are lists, the first one is mapped over and the second one is used to curry the binary operator.
* `:` has two uses: if the operator following it is unary, this is a simple map. E.g. `[1 0 -1 4 -3] :z` is `[1 0 1 4 3]`, where `z` gets the modulus of a number. If the operator following it is binary, this will *fold* the operator instead. E.g. `[1 2 3 4] :+` is `10`.
* `.` vectorises a binary operator. It expects two lists as arguments and applies the operator to corresponding pairs. E.g. `[1 2 3] [5 7 11] .*` gives `[5 14 33]`.

Note that `:` itself is always a unary operator, whereas `f` and `.` themselves are always binary operators. These can be arbitrarily nested (provided they have the right arities). And that's what we'll do...

```
9Yb      e# Push the binary representation of 9, i.e. [1 0 0 1].
2/       e# Split into pairs, i.e. [[1 0] [0 1]]. We'll use these to indicate
         e# which of the two inputs we turn into an identity matrix.
q~       e# Read and evaluate input, [A B].
f{       e# This block is mapped over the [[1 0] [0 1]] list, also pushing
         e# [A B] onto the stack for each iteration.
  .{     e#   The stack has either [1 0] [A B] or [0 1] [A B]. We apply this
         e#   block to corresponding pairs, e.g. 1 A and 0 B.
    _,   e#     Duplicate the matrix and get its length/height N.
    ,_   e#     Turn into a range [0 1 ... N-1] and duplicate it.
    ff=  e#     Double f on two lists is an interesting idiom to compute an
         e#     outer product: the first f means that we map over the first list
         e#     with the second list as an additional parameter. That means for
         e#     the remaining operator the two arguments are a single integer
         e#     and a list. The second f then maps over the second list, passing
         e#     in the the number from the outer map as the first parameter.
         e#     That means the operator following ff is applied to every possible
         e#     pair of values in the two lists, neatly laid out in a 2D list.
         e#     The operator we're applying is an equality check, which is 1
         e#     only along the diagonal and 0 everywhere else. That is, we've
         e#     created an NxN identity matrix.
    ?    e#     Depending on whether the integer we've got along with the matrix
         e#     is 0 or 1, either pick the original matrix or the identity.
  }
         e#   At this point, the stack contains either [A Ib] or [Ia B].
         e#   Note that A, B, Ia and Ib are all 2D matrices.
         e#   We now want to compute the Kronecker product of this pair.
  :ffff* e#   The ffff* is the important step for the Kronecker product (but
         e#   not the whole story). It's an operator which takes two matrices
         e#   and replaces each cell of the first matrix with the second matrix
         e#   multiplied by that cell (so yeah, we'll end up with a 4D list of
         e#   matrices nested inside a matrix).
         e#   The leading : is a fold operation, but it's a bit of a degenerate
         e#   fold operation that is only used to apply the following binary operator
         e#   to the two elements of a list.
         e#   Now the ffff* works essentially the same as the ff= above, but
         e#   we have to deal with two more dimensions now. The first ff maps
         e#   over the cells of the first matrix, passing in the second matrix
         e#   as an additional argument. The second ff then maps over the second
         e#   matrix, passing in the cell from the outer map. We multiply them
         e#   with *.
         e#   Just to recap, we've essentially got the Kronecker product on the
         e#   stack now, but it's still a 4D list not a 2D list.
         e#   The four dimensions are:
         e#     1. Columns of the outer matrix.
         e#     2. Rows of the outer matrix.
         e#     3. Columns of the submatrices.
         e#     4. Rows of the submatrices.
         e#   We need to unravel that into a plain 2D matrix.
  ::.+   e#   This joins the rows of submatrices across columns of the outer matrix.
         e#   It might be easiest to read this from the right:
         e#     +    Takes two rows and concatenates them.
         e#     .+   Takes two matrices and concatenates corresponding rows.
         e#     :.+  Takes a list of matrices and folds .+ over them, thereby
         e#          concatenating the corresponding rows of all matrices.
         e#     ::.+ Maps this fold operation over the rows of the outer matrix.
         e#   We're almost done now, we just need to flatten the outer-most level
         e#   in order to get rid of the distinction of rows of the outer matrix.
  :~     e#   We do this by mapping ~ over those rows, which simply unwraps them.
}
         e# Phew: we've now got a list containing the two Kronecker products
         e# on the stack. The rest is easy, just perform pairwise addition.
:..+     e# Again, the : is a degenerate fold which is used to apply a binary
         e# operation to the two list elements. The ..+ then simply vectorises
         e# addition twice, such that we add corresponding cells of the 2D matrices.
p        e# All done, just pretty-print the matrix.

```

# Answer
> 4 votes
# J - ~~38~~ ~~33~~ 31 bytes

```
i=:=@i.@#
[:,./^:2(*/i)+(*/~i)~

```

## Usage

```
   f =: [:,./^:2(*/i)+(*/~i)~
   (2 2 $ 1 2 3 4) f (2 2 $ 5 10 7 9)
6 10 2  0
7 10 0  2
3  0 9 10
0  3 7 13
   (3 3 $ 28 83 96 5 70 4 10 32 44) f (3 3 $ 39 19 65 77 49 71 80 45 76)
67 19  65  83   0   0 96  0   0
77 77  71   0  83   0  0 96   0
80 45 104   0   0  83  0  0  96
 5  0   0 109  19  65  4  0   0
 0  5   0  77 119  71  0  4   0
 0  0   5  80  45 146  0  0   4
10  0   0  32   0   0 83 19  65
 0 10   0   0  32   0 77 93  71
 0  0  10   0   0  32 80 45 120
   (3 3 $ 76 57 54 76 8 78 39 6 94) f (2 2 $ 59 92 55 29)
135  92 57  0  54   0
 55 105  0 57   0  54
 76   0 67 92  78   0
  0  76 55 37   0  78
 39   0  6  0 153  92
  0  39  0  6  55 123

```

# Answer
> 2 votes
# Julia, ~~60~~ ~~59~~ ~~58~~ 56 bytes

```
A%B=hvcat(sum(A^0),sum(i->map(a->a*B^i,A'^-~-i),0:1)...)

```

Try it online!

### How it works

* For matrices **A** and **B**, `map(a->a*B,A')` computes the Kronecker product **A⊗B**.

The result is a vector of matrix blocks with the dimensions of **B**.

We have to transpose **A** (with `'`) since matrices are stored in column-major order.
* Since bitwise NOT with two's complement satisfies the identity **~n = -(n + 1)** for all integers **n**, we have that **-~-n = -(~(-n)) = --((-n) + 1) = 1 - n**, so **-~-0 = 1** and **-~-1 = 0**.

This way the anonymous function `i->map(a->a*B^i,A'^-~-i)` applies the above map to **B⁰** (the identity matrix with **B**'s dimensions) and **A¹ = A** when **i = 0**, and to  and **A⁰** when **i = 1**.
* `sum(i->map(a->a*B^i,A'^-~-i),0:1)` sums over **{0,1}** with the above anonymous function, computing the Kronecker sum **A⊕B** as **A¹⊗B⁰ + A⁰⊗B¹**.

The result is a vector of matrix blocks with the dimensions of **B**.
* `sum(A^0)` computes the sum of all entries of the identity matrix of **A**'s dimensions. For an **n×n** matrix **A**, this yields **n**.
* Finally, `hvcat(sum(A^0),sum(i->map(a->a*B^i,A'^-~-i),0:1)...)` concatenates the matrix blocks that form **A⊕B**.

With first argument **n**, `hvcat` concatenates **n** matrix blocks horizontally, and the resulting (larger) blocks vertically.

# Answer
> 0 votes
# Ruby, 102

```
->a,b{r=0..-1+a.size*q=b.size
r.map{|i|r.map{|j|(i/q==j/q ?b[i%q][j%q]:0)+(i%q==j%q ?a[i/q][j/q]:0)}}}

```

**In test program**

```
f=->a,b{r=0..-1+a.size*q=b.size
r.map{|i|r.map{|j|(i/q==j/q ?b[i%q][j%q]:0)+(i%q==j%q ?a[i/q][j/q]:0)}}}

aa =[[1,2],[3,4]]
bb =[[5,10],[7,9]]
f[aa,bb].each{|e|p e}
puts

aa =[[28,83,96],[5,70,4],[10,32,44]]
bb =[[39,19,65],[77,49,71],[80,45,76]]
f[aa,bb].each{|e|p e}
puts

aa =[[76,57,54],[76,8,78],[39,6,94]]
bb =[[59,92],[55,29]]
f[aa,bb].each{|e|p e}
puts

```

Requires two 2D arrays as input and returns a 2D array.

There are probably better ways of doing this: using a function to avoid repetition; using a single loop and printing the output. Will look into them later.

# Answer
> 0 votes
# JavaScript (ES6), 109

Built upon the answer to the other challenge

```
(a,b)=>a.map((a,k)=>b.map((b,i)=>a.map((y,l)=>b.map((x,j)=>r.push(y*(i==j)+x*(k==l))),t.push(r=[]))),t=[])&&t

```

**Test**

```
f=(a,b)=>a.map((a,k)=>b.map((b,i)=>a.map((y,l)=>b.map((x,j)=>r.push(y*(i==j)+x*(k==l))),t.push(r=[]))),t=[])&&t

console.log=x=>O.textContent+=x+'\n'

function show(label, mat)
{
  console.log(label)
  console.log(mat.join`\n`)
}

;[
  {a:[[1,2],[3,4]], b:[[5,10],[7,9]]},
  {a:[[28,83,96],[5,70,4],[10,32,44]], b:[[39,19,65],[77,49,71],[80,45,76]]},
  {a:[[76,57,54],[76,8,78],[39,6,94]], b:[[59,92],[55,29]]}
].forEach(t=>{
  show('A',t.a)
  show('B',t.b)
  show('A⊕B',f(t.a,t.b))
  show('B⊕A',f(t.b,t.a))
  console.log('-----------------')
})
```

```
<pre id=O></pre>
```

---
Tags: code-golf, arithmetic, linear-algebra, matrix
---


title: How compatible are my strings?

text:
# Question
Title: How compatible are my strings?
## Introduction

Consider two strings **A** and **B** of the same length **L**, and an integer **K ≥ 0**. For the purposes of this challenge, we say that the strings are **K**-compatible, if there exists a string **C** of length **K** such that **A** is a contiguous substring of the concatenation **BCB**. Note that **A** is a substring of **BAB**, so **A** and **B** are always **L**-compatible (but may also be **K**-compatible for some other **K \< L**).

## Input

Your inputs are two strings of the same positive length, consisting of upper- and lowercase ASCII letters.

## Output

Your output shall be the lowest non-negative integer **K** such that the inputs are **K**-compatible.

## Example

Consider the inputs

```
A = HHHHHH
B = HHttHH

```

They are not 0-compatible, because **A** is not a substring of `HHttHHHHttHH`. They are also not 1-compatible, because **A** is not a substring of `HHttHH#HHttHH` no matter which letter is placed on the `#`. However, **A** *is* a substring of `HHttHHHHHHttHH`, where **C** is the two-letter string `HH`. Thus the inputs are 2-compatible, and the correct output is `2`.

## Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

## Test cases

The compatibility condition is symmetric, so swapping the two inputs should not change the output.

```
E G -> 1
E E -> 0
aB Bc -> 1
YY tY -> 1
abcd bcda -> 0
abcXd bxcda -> 4
Hello Hello -> 0
Hello olHel -> 1
aBaXYa aXYaBa -> 1
aXYaBa aBaXYa -> 1
HHHHHH HHttHH -> 2
abcdab cdabcd -> 2
XRRXXXXR XRXXRXXR -> 4
evveeetev tetevevev -> 7
vzzvzJvJJz vJJvzJJvJz -> 10
JJfcfJJcfJfb JcfJfbbJJJfJ -> 5
GhhaaHHbbhGGH HHaaHHbbGGGhh -> 9
OyDGqyDGDOGOGyG yDGqOGqDyyyyOyD -> 12
ffKKBBpGfGKpfGpbKb fGpbKbpBBBffbbbffK -> 9
UZuPPZuPdVdtuDdDiuddUPtUidtVVV dtUPtUidtVVVtDZbZZPuiUZuPPZuPd -> 21

```

## Leaderboard

Here's a Stack Snippet to generate a leaderboard and list of winners by language. To make sure your answer shows up, start it with a header of the form

```
## Language, N bytes

```

You can keep old scores in the header by using the strikethrough tags: `<s>57</s>` will appear as ~~57~~.

```
/* Configuration */

var QUESTION_ID = 78736; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 32014; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(-?\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });

  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    if (! /<a/.test(lang)) lang = '<i>' + lang + '</i>';
    lang = jQuery(lang).text().toLowerCase();

    languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link, uniq: lang};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.uniq > b.uniq) return 1;
    if (a.uniq < b.uniq) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
```

```
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/Sites/codegolf/all.css?v=617d0685f6f3">
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<div id="language-list">
  <h2>Winners by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr>
  </tbody>
</table>
```

# Answer
> 8 votes
# Pyth, 16

```
lhf}QjT,vzvz+k.:

```

Find the shortest substring of A that when inserted between two copies of B results in a string that contains A.

This could be two bytes shorter if the second line didn't have quotes, but that feels weird?

Test Suite

# Answer
> 4 votes
# Python 3, ~~155~~ ~~168~~ 157 bytes

Total is the length of `A`. Compare the beginning of `A` to the end of `B` and subtract that from total. Compare the beginning of `B` to the end of `A` and subtract that from total. Return the absolute value of total unless total is equal to the length, in which case return 0.

```
def f(A,B):
    T=L=len(A)
    C=D=1
    for i in range(L,0,-1):
        if A[:i]==B[-i:]and C:
            T,C=T-i,0
        if A[-i:]==B[:i]and D:
            T,D=T-i,0
    return (0,abs(T))[T!=-L]

```

**Edit:** Handle the `f("abcdab","cdabcd")==2` case

# Answer
> 3 votes
## Retina, 49 bytes

```
.*?(?<=^(?=(.*)(?<4-3>.)*(.*) \2.*\1$)(.)*).+
$#4

```

Try it online! (Slightly modified to run all tests at once.)

The trick is that we need to backtrack over the part of `A` that we *don't* find in `B`, and so far I haven't found a way to do this without rather annoying lookarounds and balancing groups.

# Answer
> 3 votes
# Jolf, 40 Bytes

```
Wά)Ζ0W<ζli)? h++i]Iζ+ζniIoά0nΖhζ}onhn}wn

```

Try it!

I'm quite new to Jolf, learned a lot while figuring this out. Seems a bit awkward, still could probably could be golfed down further. Even knocked off 2 bytes while writing this explanation.

Explanation:

```
  Wά)                                      While ά (initialized to 16)
     Ζ0                                    Set ζ to 0
       W<ζli)                              While ζ < length(A)
             ? h++i]Iζ+ζniIoά0n            Set ά to 0 if (A + a substring from B of length n + A) contains B
                               Ζhζ         Increment ζ
                                  }onhn    Increment n (initialize to 0
                                       }wn Decrement n and print

```

# Answer
> 2 votes
# 05AB1E, 20 bytes

Code:

```
õ)²Œ«v¹y¹««²åiyg}})ß

```

Uses **CP-1252** encoding. Try it online!.

# Answer
> 2 votes
## JavaScript (ES6), 110 bytes

```
(a,b)=>{for(i=0;;i++)for(j=i;j<=a.length;j++)if(b.startsWith(a.slice(j))&&b.endsWith(a.slice(0,j-i)))return i}

```

Works by slicing ever longer pieces out of the middle of `a` until they match the two ends of `b`. The loop is not infinite as it will stop on or before `i == a.length`.

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


title: Calculating (3 + sqrt(5))^n exactly

text:
# Question
Title: Calculating (3 + sqrt(5))^n exactly
Today your goal is to find integers *a* and *b* given non-negative integer *n* such that:

You should write a program or a function that takes parameter *n* and outputs *a* and *b* in a format of your choice.

Standard loopholes apply. Additionally, it's intended that you implement the above problem using basic arithmetic yourself. So you may not use built-in exact algebra functionality, rationals, or functions implementing non-trivial mathematical constructs (for example the Lucas sequence).

**Shortest code in bytes wins.**

---

Example input/output:

> 0 → 1, 0
> 1 → 3, 1
> 2 → 14, 6
> 3 → 72, 32
> 4 → 376, 168
> 5 → 1968, 880
> 6 → 10304, 4608
> 7 → 53952, 24128
> 8 → 282496, 126336
> 9 → 1479168, 661504

# Answer
> 3 votes
## Dyalog APL, 18 bytes

```
((3∘×+5 1×⌽)⍣⎕)1 0

```

This is a program that takes input through .

```
 (         )         Monadic train:
  3∘×                3 times argument
     +               Plus
      5 1×⌽          (5 1) times the reverse
(           ⍣⎕)      Apply that function (input) times
               1 0   starting with (1 0)

```

The features used here were implemented well before April 2015, making this answer valid.

Try it here. Note that tryapl.org is a limited subset of Dyalog and does not support .

# Answer
> 16 votes
# Octave, 26 bytes

```
[3 5;1 3]**input('')*[1;0]

```

Because (**a**+*b*\*sqrt(5)) * (3+sqrt(5)) = (**3a+5b**) + (*a+3b*) * sqrt(5),

multiplying input vector

```
| 1 |    /* a = 1 */
| 0 |    /* b = 0 */

```

which stands for 1 = (3+sqrt(5))^0 by matrix

```
| 3 5 |
| 1 3 |

```

seems natural. Instead of looping `n` times, we rather raise the matrix to the power of `n` and then multiply it by input vector.

# Answer
> 14 votes
# Python 2, 50

```
a=1;b=0
exec"a,b=3*a+5*b,3*b+a;"*input()
print a,b

```

Multiplies by `3+sqrt(5)` repeatedly by its action on the pair `(a,b)` representing `a+b*sqrt(5)`. Equivalent to starting with the column vector `[1,0]` and left-multiplying `n` times by the matrix `[[3,5],[1,3]]`.

# Answer
> 12 votes
# Julia, ~~22~~ 20 bytes

```
n->[3 5;1 3]^n*[1;0]

```

This creates a lambda function which takes a single integer as input and returns a 2-element vector of integers corresponding to the solution \[a, b\]. To call it, give it a name, e.g. `f=n->...`.

Start by multiplying

We can then translate the right hand side of this equation into a 2-column matrix, where the first corresponds to the coefficient of *a* and the second to the coefficient of *b*:

Multiply this matrix by itself *n* times, then right multiply by the column vector (1, 0), and POOF! Out pops the solution vector.

Examples:

```
julia> println(f(0))
[1,0]

julia> println(f(5))
[1968,880]

```

# Answer
> 8 votes
# J, 20 bytes

```
+/@:*(3 5,.1 3&)&1 0

```

Multiplicate the vector `[1 0]` with the matrix `[[3 5] [1 3]]` `n` times.

2 bytes saved thanks to @algorithmshark.

Usage and test:

```
   (+/@:*(3 5,.1 3&)&1 0) 5
1968 880

   (+/@:*(3 5,.1 3&)&1 0) every i.6
   1   0
   3   1
  14   6
  72  32
 376 168
1968 880

```

# Answer
> 7 votes
# Pyth, 20 bytes

```
u,+*3sGyeG+sGyeGQ,1Z

```

`u` which is reduce in general, is used here as an apply repeatedly loop. The updating function is `G` -\> `,+*3sGyeG+sGyeG`, where `G` is a 2 tuple. That function translates to `3*sum(G) + 2*G[1], sum(G) + 2*G[1]`. `s` is `sum`, `y` is `*2`.

# Answer
> 5 votes
# APL (22)

```
{⍵+.×⍨2 2⍴3 5 1}⍣⎕⍨2↑1

```

Explanation:

* `{`...`}⍣⎕⍨2↑1`: read a number, and run the following function that many times, using `[1,0]` as the initial input.
    + `2 2⍴3 5 1`: the matrix `[[3,5],[1,3]]`
    + `⍵+.×⍨`: multiply the first number in ⍵ by 3, the second by 5, and sum them, this is the new first number; then multiply the first number in ⍵ by 1, the second by 3, and sum those, that is the new second number.

# Answer
> 5 votes
# Jelly, 13 bytes

```
5W×U++Ḥ
2BÇ³¡

```

Try it online!

### How it works

```
5W×U++Ḥ    Helper link. Argument: [a, b]

5W         Yield [5].
  ×U       Multiply it by the reverse of [a, b]. This yields [5b, a].
    +      Hook; add the argument to the result. This yields [a + 5b, a + b].
     +Ḥ    Fork; add the doubled argument ([2a, 2b]) to the result.
           This yields [3a + 5b, a + 3b].

2BÇ³¡      Main link. Argument: n

2B         Convert 2 to binary, yielding [1, 0].
    ¡      Repeat:
  Ç            Apply the helper link...
   ³           n times.

```

# Answer
> 3 votes
# Javascript, ~~63~~ 61 bytes

I am using a recursive evaluation of the binomial: (x+y)^n = (x+y)(x+y)^{n-1}

New(thanks to @edc65)

```
F=n=>{for(i=y=0,x=1;i++<n;)[x,y]=[3*x+5*y,x+3*y];return[x,y]}

```

Old

```
F=n=>{for(i=y=0,x=1;i<n;i++)[x,y]=[3*x+5*y,x+3*y];return [x,y]}

```

# Answer
> 3 votes
# Mathematica, 31

```
Nest[{{3,5},{1,3}}.#&,{1,0},#]&

```

# Answer
> 3 votes
# CJam, 21 bytes

```
0X{_2$3*+@5*@3*+}li*p

```

Try it online.

### How it works

```
0X       " Stack: [ 0 1 ]                                ";
li{      " Do int(input()) times:                        ";
  _2$    " Stack: [ a b ] -> [ a b b a ]                 ";
  3*+    " Stack: [ a b b a ] -> [ a b (b+3a) ]          ";
  @5*@3* " Stack: [ a b (b+3a) ] -> [ (b+3a) 5a 3b ]     ";
  +      " Stack: [ (b+3a) 5a 3b ] -> [ (b+3a) (5a+3b) ] ";
}*       "                                               ";
p        " Print topmost stack item plus linefeed.       ";
         " Print remaining stack item (implicit).        ";

```

# Answer
> 2 votes
# C, 114 bytes

```
g(n){int i,a[2]={1,0},b[2];for(i=0;i<n;i++)*b=*a*3+5*a[1],b[1]=*a+3*b[1],*a=*b,a[1]=b[1];printf("%d,%d",*a,a[1]);}

```

This implements matrix multiplication the boring way. For a more fun (quote: "awesomely horrific") 238 byte solution, look no further!

```
f(n){int p[2][n+3],i,j,k=0,a[2]={0};for(j=0;j<n+3;j++)p[0][j]=0;*p[1]=0;(*p)[1]=1;for(j=0;j<n;j++,k=!k)for(i=1;i<n+3;i++)p[!k][i]=p[k][i-1]+p[k][i];for(i=1;i<n+2;i++)a[!(i%2)]+=p[k][i]*pow(3,n+1-i)*pow(5,(i-1)/2);printf("%d,%d",*a,a[1]);}

```

Unraveled:

```
g(n){
    int i,a[2]={1,0},b[2];
    for(i=0;i<n;i++)
        *b=3**a+5*a[1],b[1]=*a+3*b[1],*a=*b,a[1]=b[1];
    printf("%d,%d",*a,a[1]);
}

```

This could probably be shortened a bit. Try a test program online!

# Answer
> 2 votes
# k2 - 22 char

Function taking one argument.

```
_mul[(3 5;1 3)]/[;1 0]

```

`_mul` is matrix multiplication so we curry it with the matrix `(3 5;1 3)` and then hit it with the functional power adverb: `f/[n;x]` applies `f` to `x`, `n` times. Again we curry it, this time with the starting vector `1 0`.

```
  _mul[2 2#3 5 1]/[;1 0] 5
1968 880
  f:_mul[2 2#3 5 1]/[;1 0]
  f'!8  /each result from 0 to 7 inclusive
(1 0
 3 1
 14 6
 72 32
 376 168
 1968 880
 10304 4608
 53952 24128)

```

This will not work in Kona, because for some reason `f/[n;x]` isn't implemented correctly. Only the `n f/x` syntax works, so the shortest fix is `{x _mul[(3 5;1 3)]/1 0}` at 23 char.

# Answer
> 2 votes
# ised, 25 bytes (20 characters)

```
({:{2,4}·x±Σx:}$1)∘1

```

I hoped for better, but there are just too many braces needed in ised to make it competent, the operator precedence is not optimal for golfing.

It expects the input to be in $1 memory slot, so this works:

```
ised '@1{9};' '({:{2,4}·x±Σx:}$1)∘1'

```

For n=0, the zero is skipped (outputs 1, instead of 1 0). If that's an issue, replace the final `1` with `~[2]`.

# Answer
> 2 votes
## Seriously, 32 bytes, non-competing

```
,╗43/12`╜";)@4*≈(6*-"£n.X4ì±0`n

```

Hex Dump:

```
2cbb34332f313260bd223b2940342af728362a2d229c6e2e58348df130606e7f

```

Try It Onlline

Obviously not a contender for shortest, but at least the method is original. (Noting that such a problem necessarily indicates a Lucas sequence, as mentioned in the description, this program generates successive terms of the sequences using the recurrence relation

a\_n = 6\*a\_{n-1} - 4\*a\_{n-2}.)

# Answer
> 1 votes
# Haskell, 41 bytes

```
(iterate(\(a,b)->(3*a+5*b,a+3*b))(1,0)!!)

```

Usage example: `(iterate(\(a,b)->(3*a+5*b,a+3*b))(1,0)!!) 8` -\> `(282496,126336)`.

# Answer
> 1 votes
**C/C++ 89 bytes**

```
void g(int n,long&a,long&b){if(n){long j,k;g(n-1,j,k);a=3*j+5*k;b=j+3*k;}else{a=1;b=0;}}

```

Formatted:

```
    void g(int n, long&a, long&b) {
if (n) {
    long j, k;
    g(n - 1, j, k);
    a = 3 * j + 5 * k;
    b = j + 3 * k;
} else {
    a = 1;
    b = 0;
}}

```

Same concept:

```
void get(int n, long &a, long& b) {
    if (n == 0) {
        a = 1;
        b = 0;
        return;
    }
    long j, k;
    get(n - 1, j, k);
    a = 3 * j + 5 * k;
    b = j + 3 * k;
}

```

The test bench:

```
#include <iostream>
using namespace std;
int main() {
    long a, b;
    for (int i = 0; i < 55; i++) {
        g(i, a, b);
        cout << i << "-> " << a << ' ' << b << endl;
    }
    return 0;
}

```

The output:

```
0-> 1 0
1-> 3 1
2-> 14 6
3-> 72 32
4-> 376 168
5-> 1968 880
6-> 10304 4608
7-> 53952 24128
8-> 282496 126336
9-> 1479168 661504
10-> 7745024 3463680
11-> 40553472 18136064
12-> 212340736 94961664
13-> 1111830528 497225728
14-> 5821620224 2603507712
15-> 30482399232 13632143360
16-> 159607914496 71378829312
17-> 835717890048 373744402432
18-> 4375875682304 1956951097344
19-> 22912382533632 10246728974336
20-> 119970792472576 53652569456640
21-> 628175224700928 280928500842496
22-> 3289168178315264 1470960727228416
23-> 17222308171087872 7702050360000512
24-> 90177176313266176 40328459251089408
25-> 472173825195245568 211162554066534400
26-> 2472334245918408704 1105661487394848768

```

# Answer
> 1 votes
# Jelly, 10 bytes

```
31,53Dæ*³Ḣ

```

Try it online!

Uses matrix. Computes (\[\[3,1\],\[5,3\]\]\**input())\[0\].

# Answer
> 0 votes
# K, 37 bytes

```
f:{:[x;*(1;0)*_mul/x#,2 2#3 1 5;1 0]}

```

or

```
f:{:[x;*(1;0)*_mul/x#,(3 1;5 3);1 0]}

```

They're both the same thing.

# Answer
> 0 votes
# Python 3, 49 bytes

```
w=5**0.5;a=(3+w)**int(input())//2+1;print(a,a//w)

```

although on my machine, this only gives the correct answer for inputs in the range `0 <= n <= 18`.

This implements the closed form formula

```
w = 5 ** 0.5
u = 3 + w
v = 3 - w
a = (u ** n + v ** n) / 2
b = (u ** n - v ** n) / (2 * w)

```

and takes advantage of the fact that the `v ** n` part is small, and can be computed by rounding rather than direct calculation.

# Answer
> 0 votes
# Scheme, 97 bytes

```
(define(r n)(let s([n n][a 1][b 0])(if(= 0 n)(cons a b)(s(- n 1)(+(* a 3)(* b 5))(+ a(* b 3))))))

```

# Answer
> 0 votes
**C 71 bytes (60 with pre-initialised variables)**

Scope for golfing yet but just to prove that C does not have to be "awesomely horrific".

```
f(int n,int*a){for(*a=1,a[1]=0;n--;a[1]=*a+3*a[1],*a=(5*a[1]+4**a)/3);}

```

If the values in a are initialised to {1,0}, we do better.

```
f(int n,int*a){for(;n--;a[1]=*a+3*a[1],*a=(5*a[1]+4**a)/3);}

```

This is iteratively using the mappings a-\>3a+5b, b-\>a+3b but avoiding a temporary variable by calculating a from the new value of b instead.

---
Tags: code-golf, arithmetic
---


title: Addition in base -1+i

text:
# Question
Title: Addition in base -1+i
Gaussian integers are complex numbers of the form `a+bi` where `a` and `b` are both integers. In base -1+i, all Gaussian integers can be uniquely represented using the digits `0` and `1`, without the need for a symbol to denote sign.

For instance, `1100` in base -1+i represents the decimal number 2, since

```
1*(-1+i)^3 + 1*(-1+i)^2 + 0*(-1+i)^1 + 0*(-1+i)^0
= (2+2i) + (-2i) + 0 + 0
= 2

```

Input will be two Gaussian integers in base -1+i represented using the digits `01`. This can take one of the following forms:

* Two separate digit strings,
* Two decimal integers consisting of `01` representing the base -1+i numbers (e.g. `1100` for 2 in base -1+i),
* Two binary integers representing the base -1+i numbers (e.g. decimal `12` or `0b1100` for 2 in base -1+i)
* A single string separating two digit strings/binary integers by a single non-alphanumeric separator (e.g. `1100 1100` or `12,12` for 2+2)

Output the sum of the two Gaussian integers, also in base -1+i and represented using the digits `01` (in one of the formats allowed as input, not necessarily the same choice). The output is allowed to contain a finite number of leading zeroes.

**Your function or program must terminate within 2 seconds for inputs of at most 30 digits each.**

## Additional clarifications

* You may assume that the input contains no extraneous leading zeroes. For the special case of 0, you may choose either `0` or the empty string as the representation.

## Test cases

```
0, 0 => 0                                      # 0 + 0 = 0
0, 1 => 1                                      # 0 + 1 = 1
1, 1 => 1100                                   # 1 + 1 = 2
1100, 1100 => 111010000                        # 2 + 2 = 4
1101, 1101 => 111011100                        # 3 + 3 = 6
110111001100, 1110011011100 => 0               # 42 + (-42) = 0
11, 111 => 0                                   # i + (-i) = 0
11, 110 => 11101                               # i + (-1-i) = -1
10101, 11011 => 10010                          # (-3-2i) + (-2+3i) = (-5+i)
1010100101, 111101 => 1110100000100            # (-19+2i) + (3-4i) = (-16-2i)

```

Longer test cases:

```
11011011010110101110010001001, 111100010100101001001010010101 => 0
111111111111111111111111111111, 111111111111111111111111111111 => 100100100100100100100100100100
101101110111011101110111011101, 101101110111011101110111011101 => 11101001010001000100010001000100011100
100100010101001101010110101010, 100010011101001011111110101000 => 110000110010101100001100111100010

```

# Answer
> 42 votes
# Python 2, ~~98~~ ~~97~~ ~~91~~ 84 bytes

```
s=input();L=1
for _ in`s`*8:s+=1098*int(str(s).translate('0011'*64));L*=10
print s%L

```

This does I/O in decimal. The integers have to be separated by the non-alphanumeric character `+`.

*Thanks to @xnor for golfing off 2 bytes!*

Try it on Ideone.

### How it works

In Arithmetic in Complex Bases, the author shows how to add and multiply complex numbers in bases of the form **-n + i**.

For base **-1 + i**, addition is done similarly to regular, binary addition with carry, with two differences:

* Instead of carrying **1** to the next higher position, we carry **110** to the next three.
* Carry digits can propagate indefinitely. However, without leading zeroes, the sum **a + b** has at most eight digits more than the maximum of **a** and **b**.

We proceed as follows.

1. First, we add **a** and **b** as if their digits were decimal digits.

For **a = 10101** and **b = 11011**, this gives **21112**.
2. Next, we form a new number by replacing the digits larger than **1** with a **1**, others with a **0**.1

For the sum **21112**, this gives **10001**.
3. For each digit larger than **1**, we have to subtract **2** from that digit and carry **110** to the next three higher positions. Since **1098 = 10 * 110 - 2**, we can achieve this by multiplying the result from step 2 by **1098**, then adding that product to the sum.2

For the sum **21112**, this gives **21112 + 1098 * 10001 = 21112 + 10981098 = 11002210**.
4. We repeat steps **2** and **3** a total of **d * 8** times, where **d** is the number of digits of **a + b**. 3

For the initial sum **21112**, the results are

```
                      11002210
                      12210010
                    1220010010
                  122000010010
                12200000010010
              1220000000010010
            122000000000010010
          12200000000000010010
        1220000000000000010010
      122000000000000000010010
    12200000000000000000010010
  1220000000000000000000010010
122000000000000000000000010010
                             .
                             .
                             .

```
5. We take the final sum modulo **10d + 8**, discarding all but the last **d + 8** digits.

For the initial sum **21112**, the final result is **10010**.

---

1 This is achieved with *translate*. Repeating the string **0011** 64 times makes one repetition line up with the sequence of ASCII characters **0123**, achieving the desired replacement.

2 Note that the digits of this sum cannot exceed **3** (initial value **1** plus two **1**'s from carries).

3 This happens to work for **d = 1**, and **d * 8 \> d + 8** otherwise. The code may repeat the steps **(d + 1) * 8** times, since **s** has a trailing **L** if **s** is a *long* integer.

# Answer
> 16 votes
# Pyth, 34 bytes

```
_shM.u,%J/eMeN\12-+PMeNm.B6/J2k,kQ

```

Try it online: Demonstration or Test Suite (takes quite a while). It should satisfy the time restriction though easily, since the online compiler is quite slow in comparison with the normal (offline) compiler.

### Explanation:

My algorithm is basically an implementation of addition with carrying. But instead of carrying `1`, I have to carry `110` (`1100` in base `-1+i` is the same as `2` in base `-1+i`). This works mostly fine, but you can get stuck in an infinite loop printing zeros. For instance if you are adding `1` with `11` and currently have the carry `110`. So I basically add until I get stuck in a loop and then stop. I think that a loop that a loop will always print zeros and therefore this should be fine.

```
_shM.u,%J/eMeN\12-+PMeNm.B6/J2k,kQ   implicit: Q = input list of strings
                               ,kQ   create the pair ["", Q]
    .u                               modify the pair N (^) until loop:
      ,                                replace N with a new pair containing:
            eN                           N[1] (the remaining summand)
          eM                             take the last digits of each summand
         /    \1                         count the ones
        J                                store the count in J
       %J       2                        J % 2 (this is the first element of the new pair)
                   PMeN                  remove the last digit of each summand
                  +    m   /J2           and add J / 2 new summand:
                        .B6                 with the value "110" (binary of 6)
                 -            k          remove empty summand
    .u                               returns all intermediate results
  hM                                 extract the digits
 s                                   sum them up to a long string
_                                    reverse

```

# Answer
> 13 votes
# Jelly, ~~29~~ ~~28~~ ~~26~~ ~~24~~ ~~21~~ 20 bytes

```
DBḅ1100ḌµDL+8µ¡Dṣ2ṪḌ

```

This does I/O in decimal. The integers have to be separated by the non-alphanumeric character `+`.

Try it online! or verify all test cases.

### Background

In Arithmetic in Complex Bases, the author shows how to add and multiply complex numbers in bases of the form **-n + i**.

For base **-1 + i**, addition is done similarly to regular, binary addition with carry, with two differences:

* Instead of carrying **1** to the next higher position, we carry **110** to the next three.
* Carry digits can propagate indefinitely. However, without leading zeroes, the sum **a + b** has at most eight digits more than the maximum of **a** and **b**.

We proceed as follows.

1. First, we add **a** and **b** as if their digits were decimal digits.

For **a = 10101** and **b = 11011**, this gives **21112**.
2. For each digit larger than **1**, we have to subtract **2** from that digit and carry **110** to the next three higher positions. We can achieve this by converting each decimal digit to binary, the resulting binary arrays from base **1100** to integer, and interpret the resulting list of **0**'s, **1**'s, **1100**'s and **1101**'s as a non-canonical base **10** number.1

For the sum **21112**, this gives **21112 + 1098 * 10001 = 21112 + 10981098 = 11002210**.
3. We repeat steps **2** a total of **d + 8** times, where **d** is the number of digits of **a + b**.

For the initial sum **21112**, the results are

```
                      11002210
                      12210010
                    1220010010
                  122000010010
                12200000010010
              1220000000010010
            122000000000010010
          12200000000000010010
        1220000000000000010010
      122000000000000000010010
    12200000000000000000010010
  1220000000000000000000010010
122000000000000000000000010010

```
4. We discard all but the last **d + 8** digits from the final result. This is achieved by discarding everything after the last **2**.2

For the initial sum **21112**, the final result is **10010**.

### How it works

```
DBḅ1100ḌµDL+8µ¡Dṣ2ṪḌ  Main link. Argument: a + b (implicit sum)

        µ    µ¡       Execute the chain before the first µ n times, where n is
                      the result of executing the chain before the second µ.
         D            Convert a + b to base 10.
          L           Length; count the decimal digits.
           +8         Add 8 to the number of digits.
D                     Convert the initial/previous sum to base 10.
 B                    Convert each digit (0 - 3) to binary.
  ḅ1100               Convert each binary array from base 1100 to integer.
       Ḍ              Interpret the resulting list as a base 10 number.
               D      Convert the final sum to base 10.
                ṣ2    Split at occurrences of 2.
                  Ṫ   Select the last chunk.
                   Ḍ  Convert from base 10 to integer.

```

---

1 Note that the digits of this sum cannot exceed **3** (initial value **1** plus two **1**'s from carries).

2 This works because the last digit that will cancel out cannot be a **3**.

# Answer
> 13 votes
# Python 2, ~~69~~ 67 bytes

```
f=lambda a,b:a*a+b*b^58and 2*f(a*b%2*6,f(a/2,b/2))|a+b&1if a else b

```

I/O is done with base 2 integers.

-2 thanks @Dennis.

# Answer
> 12 votes
## Retina, 100 bytes

```
r+`(.*)(\d|(?!\4))( .*)(.?)
$2$4:$1$3
T` 0
+`1:11(1*:1*)11
:$1
^:*
:::
}`:(1*:1*:)11
1:1$1
(1)*:
$#1

```

This takes the input separated with a comma. The output always starts with three leading zeroes.

Try it online!

I really wonder if there's a shorter solution for the first stage...

# Answer
> 6 votes
## Python 3, 289 bytes

This performs digitwise addition from least to most significant digit (in other words, the exact same algorithm you were taught in primary school). The differences are that (a) it's in binary, not decimal, so you carry whenever a digit is 2 or more, and (b) `1 + 1 = 1100`, not `10`.

Actually, it's also necessary to note that `11 + 111 = 0`, or else sums that should become zero will never terminate.

```
from collections import*
def a(*s,p=0):
 r=defaultdict(int,{0:0})
 for S in s:
  n=0
  for d in S[::-1]:r[n]+=d=='1';n+=1
 while p<=max(r):
  while r[p]>1:
   r[p]-=2
   if r[p+1]>1<=r[p+2]:r[p+1]-=2;r[p+2]-=1
   else:r[p+2]+=1;r[p+3]+=1
  p+=1
 return str([*map(r.get,sorted(r))])[-2::-3]

```

More golfing is surely possible.

# Answer
> 2 votes
## JavaScript (ES6), ~~146~~ 126 bytes

```
r=n=>n&&n%2-r(n>>=1)-i(n)
i=n=>n&&r(n>>=1)-i(n)
g=(x,y,b=(x^y)&1)=>x|y&&b+2*g(b-x+y>>1,b-x-y>>1)
(x,y)=>g(r(x)+r(y),i(x)+i(y))

```

`g` converts a Gaussian integer (real and imaginary parts) into base `i-1`, while `r` and `i` converts a base `i-1` integer into a Gaussian integer (real and imaginary parts respectively). Once the conversions are in place, I just have to do the arithmetic.

Edit: Saved 20 bytes by calculating the real and imaginary parts separately.

# Answer
> 2 votes
C++ 416 bytes, plus `#include <vector>\n#include <algorithm>\n` (another 40)

```
using I=int;using v=std::vector<I>;void r(v&x){v r{rbegin(x),rend(x)};x=r;}v a(v L,v R){r(L);r(R);L.resize(std::max(L.size(),R.size()));for(int&r:R)L[&r-R.data()]+=r;while(1){L.resize(L.size()+3);auto it=find(rbegin(L),rend(L),2);if(it==rend(L))break;I i=-1+it.base()-begin(L);i&&L[i+1]&&L[i-1]/2?L[i+1]=L[i]=L[i-1]=0:(++L[i+2],++L[i+3],L[i]=0);}L.erase( std::find(rbegin(L),rend(L),1).base(),end(L));r(L);return L;}

```

or, with more whitespace:

```
using I=int;
using v=std::vector<I>;

void r(v&x){v r{rbegin(x),rend(x)};x=r;}
v a(v L,v R) {
  r(L);r(R);
  L.resize(std::max(L.size(),R.size()));
  for(int&r:R)
    L[&r-R.data()]+=r;
  while(1) {
    L.resize(L.size()+3);
    auto it=find(rbegin(L), rend(L), 2);
    if(it==rend(L)) break;
    I i=-1+it.base()-begin(L);
    i&&L[i+1]&&L[i-1]/2?
      L[i+1]=L[i]=L[i-1]=0
    :
      (++L[i+2],++L[i+3],L[i]=0);
  }
  L.erase( std::find(rbegin(L),rend(L),1).base(), end(L));
  r(L);
  return L;
}

```

Barely golfed. It takes input as a vector of ints, and returns a vector of ints.

Live example.

# Answer
> 2 votes
# Retina, ~~157~~ ~~151~~ ~~134~~ ~~133~~ ~~124~~ 123 bytes

*1 byte off thanks to Martin Büttner.*

```
(.+),(.+)
$.1$*0$2,$.2$*0$1,
1
0x
+`(0x*)(,.*)0(x*),
$2,$1$3
{`,

(^|0x0xx0xx)
000
(0x*)(0x*)(0x*0)xx
$1x$2x$3
)`^0+
0
0x
1

```

Try it online!

Converts to unary, and then repeat the following replacements (shown here in decimal):

```
122 -> 000
0002 -> 1100 (this can also be 0012 -> 1110 and 1112 -> 2210 or even 2222 -> 3320 or even 3333 -> 4431)

```

Basically, when larger than two: take away two, add nothing in the previous digit, add one to the previous digit, then add one to the previous digit.

In pseudocode:

```
if(a[n]>2):
    a[n] -= 2;
    a[n-2] += 1;
    a[n-3] += 1;

```

### Unary implementation:

Each digit (e.g. `3`) is shown as the number of `x`s (e.g. `xxx`) and then prefixed with `0`.

For example, `1234` would be expressed as `0x0xx0xxx0xxxx`.

This leaves `0` unchanged, as `101` would be expressed by `0x00x`.

Since initially and finally, there is only `0` and `1`, the conversion could be easily done by `1->0x` and `0x->1`.

Click here to see every step.

---
Tags: code-golf, arithmetic, restricted-time, complex-numbers
---


title: Transform a matrix

text:
# Question
Title: Transform a matrix
Write a program or function where a matrix A (maximum value of dimensions of the matrix is 100) is transformed to a new matrix B. Each element of the new matrix B is the sum of the positive neighbors of the corresponding element of the matrix A.

Only neighbors in the four orthogonal directions are considered, and the edges do not wrap around.

Example input:

```
 1  2  3
 4 -1 -2
-3 -4 10
 1  2 10

```

Output:

```
 6  4  2
 1  6 13
 5 12 10
 2 11 12

```

Rules:

* As input use integers.
* This is a , so the shortest code in bytes wins.

# Answer
# MATL, 9 bytes

```
t0>*1Y6Z+

```

Try it online!

### Explanation

The input matrix is multplied by an appropriate mask to make negative values equal to 0. Then a 2D convolution is applied to compute the sum of neighbours of each entry.

```
t     % Take input implicitly: 2D array. Duplicate
0>    % Is each entry positive? This gives a mask of positive values
*     % Multiply: set negative values of input array to zero
1Y6   % Predefined literal: [0 1 0; 1 0 1; 0 1 0]
Z+    % 2D convolution preserving size. Implicitly display

```
> 10 votes

# Answer
# Octave, ~~46~~ ~~44~~ 40 bytes

~~Saved 2 bytes thanks to @flawr~~
@LuisMendo's kernel was 4 bytes shorter than @flawr's.

```
@(M)conv2(M.*(M>0),(x='aba')~=x','same')

```

Just like @LuisMendo's answer! Only less... golfy.

You can see it here on ideone.
> 7 votes

# Answer
## JavaScript (ES6), ~~99~~ 94 bytes

```
a=>a.map((b,i)=>b.map((_,j)=>(g=(c=j,k=j)=>c[k]>0&&c[k])(a[i-1])+g(a[i+1])+g(b,j-1)+g(b,j+1)))

```

Accepts and returns a two-dimensional array.

Edit: Completely rewritten when I discovered that default arguments work when you pass an explicitly undefined value, such as when you index off the end of an array.
> 2 votes

# Answer
# JavaScript (ES6), ~~95~~ 93 bytes

```
document.write("<pre>"+(

m=>m.map((a,r)=>a.map((_,c)=>(s=(x,y=0)=>(n=(m[r+y]||0)[c+x])>0&&n)(1)+s(-1)+s(0,1)+s(0,-1)))

)([[  1,  2,  3 ],
   [  4, -1, -2 ],
   [ -3, -4, 10 ],
   [  1,  2, 10 ]])

.join`\n`)
```
> 2 votes

# Answer
## Python with SciPy, 127 bytes

```
from scipy.signal import*
lambda A,r=range(3):convolve2d([[x*(x>0)for x in y]for y in A],[[0,1,0],[1,0,1],[0,1,0]],mode='same')

```

This computes the result using Luis Mendo's method.

Try it online
> 1 votes

# Answer
## Mathcad, bytes

Uses standard 2D convolution of the filtered array with a 3x3 kernel. Variants with negative element sums and diagonal kernel also added as part compensation for the program not being in the running for least bytes.

---

No byte count entered as Mathcad scoring has yet to be determined. However, using keyboard equivalence, it is the region of 28 bytes assuming that matrix input doesn't count towards the total.

Note that what you see in the image above is exactly how the solutionn is entered and displayed in Mathcad.
> 0 votes

# Answer
# Jelly, ~~23~~ ~~20~~ 18 bytes

```
0;+ḊṖ
ZÇ€Z+Ç€
+AHÇ

```

Try it online!

## Algorithm

Let's say there is only one row: \[1,2,3,4\].

Let's say A is the result of prepending a zero, i.e. \[0,1,2,3,4\].

B is the result of removing the first item, i.e. \[2,3,4\].

Then the final result is simply A+B vectorized, then removing the last item.

Now, the algorithm is to apply this to every row as well as every column, then find their vectorized sum.

### To each column?! I thought Jelly does not support this...

You're right. Therefore, I transposed it, applied to each row, then transposed it again.

### Algorithm for removing negative numbers

Here, you just add to each number their absolute. It effectively eliminates negative numbers while doubling each positive number. Then, just halve the whole matrix.
> 0 votes

# Answer
# Pyth, 36 bytes

```
Lm+Vt+d0+0dbJmm/+.akk2dQ.b+VNYyJCyCJ

```

Try it online!

Direct translation of my answer in Jelly.
> 0 votes

---
Tags: code-golf, math, matrix
---