title: Look-and-say: Conway revisited

text:
# Question
Title: Look-and-say: Conway revisited
You should all be familiar with the Conway sequence (a.k.a. 'look-and-say'-sequence) by now:

```
     1
    11
    21
  1211
111221
312211
etc

```

You can also start by any arbitrary number as starting point. Let `f(s)` be the next element of the sequence. Now for every given `s`we can find `f(s)`. The reverse is not as trivial: it is not for every `y` possible to find the predecessor `s` such that `f(s) = y`. E.g. for `y = 1` we cannot find a predecessor. But if `y` has an *even* length you can divide it into pairs of digits which describe each one part of a predecessor:

```
513211 divides in 51,32,11
so: 51 comes from 11111
    32 comes from 222
    11 comes from 1
put together: 111112221

```

So this way there we can define an *unique* predecessor for every `y` of even length.

**Note**: The 'predecessor' `s` defined this way does generally NOT satisfy `f(s) = y`.

## Goal

Write a function / program snippet that accepts a string of digits as input that

* calculates the next element of the Conway sequence if the length of the input string is *odd*
* calculates the predecessor of the input string as defined above if the input string length is *even*.

Shortest code in bytes wins.

**Recent Questions based on the look-and-say sequences:**

# Answer
> 3 votes
# CJam, ~~46~~ ~~45~~ ~~44~~ ~~43~~ 42 bytes

```
l_,2%{0\{@)@@_2$=!{0\0}*;}*\)\}{2/{(~*}%}?

```

Test it here. It takes the number on STDIN and prints the result to STDOUT.

# Answer
> 5 votes
# Ruby, ~~125 120 119~~ 101 bytes

```
f=->n{c=n.chars;(n.size%2>0?c.chunk{|x|x}.map{|a,b|[b.size,a]}:c.each_slice(2).map{|a,b|b*a.hex})*''}

```

String input taken through function `f`:

```
f['111221']    # => "1211"
f['513211']    # => "111112221"
f['111112221'] # => "513211"

```

Expanded with notes:

```
# define lambda that takes one arg
f = -> (n) {
  # store digits in c
  c = n.chars

  # n is of odd length
  if n.size % 2 > 0
    # group identical numbers
    c.chunk{ |x| x }.map do |a, b|
      # array of [digit count, digit value]
      [b.size, a]
    end
  else
    # slice array into groups of two elements
    c.each_slice(2).map do |a, b|
      # repeat the second digit in a pair
      # the first digit-times.
      b * a.hex
    end
  end * '' # join array
}

```

# Answer
> 4 votes
## Prolog - 170 bytes

```
[]/[].
T/R:-0*_*T*R.
C*X*[X|T]*R:-(C+1)*X*T*R.
C*X*T*Y:-10*C+X+Y+R,T/R.
N+R+A:-N=:=0,A=R;D is N mod 10,N//10+R+[D|A].
F-C-R:-C/N,(N=F,R=C;F-N-R).
[1]-[1,1]. S-T:-S-[1]-T.

```

This snipped defines the function `(-)/2`. You can invoke it like

```
?- [1,1,1,3,2,1,3,2,1,1]-T.
T = [1, 3, 1, 1, 2, 2, 2, 1] .

?- [1]-T.
T = [1, 1] .

```

There seems to be only one lengths in this sequence with an odd parity: the initial `[1]`.

```
wr_len :- wr_len(1, [1]).
wr_len(N, Cur) :-
    length(Cur, Len),
    TrailingZeroes is lsb(Len),
    (TrailingZeroes > 0 -> Par = 'even'; Par = 'odd'),
    writef('%t\t%t\t%t\t%t\n', [N, Len, Par, TrailingZeroes]),
    get_next(Cur, Next),
    succ(N, O),
    !, wr_len(O, Next).

```

```
% index, length, parity of length, num of trailing 0 in bin presentation of length
?- wr_len.
1       1       odd     0
2       2       even    1
3       2       even    1
4       4       even    2
5       6       even    1
6       6       even    1
7       8       even    3
8       10      even    1
9       14      even    1
10      20      even    2
11      26      even    1
12      34      even    1
13      46      even    1
14      62      even    1
15      78      even    1
16      102     even    1
17      134     even    1
18      176     even    4
19      226     even    1
20      302     even    1
21      408     even    3
22      528     even    4
23      678     even    1
24      904     even    3
25      1182    even    1
26      1540    even    2
27      2012    even    2
28      2606    even    1
29      3410    even    1
30      4462    even    1
31      5808    even    4
32      7586    even    1
33      9898    even    1
34      12884   even    2
35      16774   even    1
36      21890   even    1
37      28528   even    4
38      37158   even    1
39      48410   even    1
40      63138   even    1
41      82350   even    1
42      107312  even    4
43      139984  even    4
44      182376  even    3
45      237746  even    1
46      310036  even    2
47      403966  even    1
48      526646  even    1
49      686646  even    1
50      894810  even    1
51      1166642 even    1
52      1520986 even    1
53      1982710 even    1
54      2584304 even    4
55      3369156 even    2
56      4391702 even    1
57      5724486 even    1
58      7462860 even    2
59      9727930 even    1
ERROR: Out of global stack
% I added a few "strategic" cuts (`!`) to get so far.

```

Readable:

```
get_next([], []).
get_next(Current, Next) :-
    get_next_sub(0, _, Current, Next).

get_next_sub(Length, Digit, [Digit|Tail], Result) :-
    get_next_sub(Length+1, Digit, Tail, Result).
get_next_sub(Length, Digit, Further, Result) :-
    number_to_list(10*Length+Digit, Result, ResultTail),
    get_next(Further, ResultTail).

number_to_list(Number, Result, Accumulator) :-
    0 is Number -> Result = Accumulator;
    Digit is Number mod 10,
    number_to_list(Number // 10, Result, [Digit|Accumulator]).

get_previous(Stop, Current, Result) :-
    get_next(Current, Next),
    (   Next = Stop
    ->  Result = Current
    ;   get_previous(Stop, Next, Result)
    ).

get_prev_or_next(Input, Result) :-
    length(Input, Length),
    (   1 is Length mod 2
    ->  get_next(Input, Result)
    ;   get_previous(Input, [1], Result)
    ).

```

# Answer
> 3 votes
# Python: 139 chars

```
import re
f=lambda s:''.join(['len(b)'+a for a,b in re.findall(r'((\d)\2*)',s)] if len(s)%2 else map(lambda a,b:b*int(a),s[::2],s[1::2]))

```

single test case

```
print f('1111122221111222112')
>>> 514241322112
print f('514241322112')
>>> 1111122221111222112

```

# Answer
> 3 votes
# Haskell, 134 128 115

```
n=length
l x=x#mod(n x)2
(a:b:c)#0=replicate(read[a])b++c#0
(a:b)#1=(\(c,d)->show(1+n c)++a:d#1)$span(==a)b
_#_=[]

```

If it needs to be from stdin/stdout, add `main=interact l` for 150 144 131 total chars. The function is called `l`.

```
*Main> putStr . unlines $ map (\x->x++":\t"++l x) ([replicate n '1'|n<-[5..10]]++map show [0,6..30]++map show [n*n+n|n<-[2..10]])
11111:  51
111111: 111
1111111:    71
11111111:   1111
111111111:  91
1111111111: 11111
0:  10
6:  16
12: 2
18: 8
24: 44
30: 000
6:  16
12: 2
20: 00
30: 000
42: 2222
56: 66666
72: 2222222
90: 000000000
110:    2110

```

# Answer
> 3 votes
# Perl - 98 bytes

The size of all these control statements bugs me, but I'm pretty happy with how the regexes worked out.

```
($_)=@ARGV;if(length()%2){$\=$&,s/^$&+//,print length$&while/^./}else{print$2x$1while s/^(.)(.)//}

```

Uncompressed:

```
($_)=@ARGV;
if(length()%2)
{
$\=$&, #Assigning the character to $\ causes it to be appended to the print (thanks, tips thread!)
s/^$&+//, #Extract the string of characters
print length$& #Print its length
while/^./ #Get next character into $&
}else{
print$2x$1
while s/^(.)(.)//
}

```

# Answer
> 2 votes
# **Java 7, Score = ~~252~~ 235 bytes**

Yep, it's java again; the worst golfing language in the world. This approach uses strings. Arbitrarily large integers are supported in java but would take much more room to code in.

Call with `f(intputString)`. Returns the corresponding string.

Golfed:

```
String f(String a){char[]b=a.toCharArray();a="";int i=0,j=0,d=0,e=b.length;if(e%2==0)for(;i<e;i+=2)for(j=0;j<b[i]-48;j++)a+=b[i+1];else{for(;i<e;i++)d=d==0?(j=b[i]-48)*0+1:b[i]-48!=j?(a+=d+""+j).length()*--i*0:d+1;a+=d;a+=j;}return a;}

```

Golfed Expanded with structure code:

```
public class LookAndSayExpandedGolfed{

    public static void main(String[] args){
        System.out.println(new LookAndSayExpandedGolfed().f(args[0]));
    }

    String f(String a){
        char[]b=a.toCharArray();
        a="";
        int i=0,j=0,d=0,e=b.length;
        if(e%2==0)
            for(;i<e;i+=2)
                for(j=0;j<b[i]-48;j++)
                    a+=b[i+1];
        else{
            for(;i<e;i++)
                d=d==0?(j=b[i]-48)*0+1:b[i]-48!=j?(a+=d+""+j).length()*--i*0:d+1;
            a+=d;
            a+=j;
        }
        return a;
    }

}

```

Partially Golfed:

```
public class LookAndSayPartiallyGolfed{

    public static void main(String[] args){
        System.out.println(new LookAndSayPartiallyGolfed().f(args[0]));
    }

    String f(String a){
        char[] number = a.toCharArray();
        String answer = "";
        int i, j, longestStreakLength = 0;
        if (number.length % 2 == 0){
            for (i = 0; i < number.length; i += 2)
                for (j = 0; j < number[i] - 48; j++)
                    answer += number[i+1];
        } else{
            j = 0;
            for (i = 0; i < number.length; i++)
                longestStreakLength = longestStreakLength == 0 ? (j = number[i] - 48) * 0 + 1 : number[i] - 48 != j ? (answer += longestStreakLength + "" + j).length()*--i*0 : longestStreakLength + 1;
            answer += longestStreakLength;
            answer += j;
        }
        return answer;
    }

}

```

Completely expanded:

```
public class LookAndSay{

    public static void main(String[] args){
        System.out.println(new LookAndSay().function(args[0]));
    }

    String function(String a){
        char[] number = a.toCharArray();
        if (number.length % 2 == 0){
            String answer = "";
            for (int i = 0; i < number.length; i += 2){
                for (int j = 0; j < number[i] - '0'; j++){
                    answer += number[i+1];
                }
            }
            return answer;
        }
        String answer = "";
        int longestStreakLength = 0;
        int longestStreakNum = 0;
        for (int i = 0; i < number.length; i++){
            if (longestStreakLength == 0){
                longestStreakNum = number[i] - '0';
                longestStreakLength = 1;
                continue;
            }
            if (number[i] - '0' != longestStreakNum){
                answer += longestStreakLength;
                answer += longestStreakNum;
                longestStreakLength = 0;
                i--;
            } else {
                longestStreakLength++;
            }
        }
        answer += longestStreakLength;
        answer += longestStreakNum;
        return answer;
    }

}

```

To run, first compile the second entry with: `javac LookAndSayExpandedGolfed.java`

Then run with: `java LookAndSayExpandedGolfed`

**Edit:** Fixed error.

# Answer
> 2 votes
# Erlang, 205

```
f(L)->g(L,L,[]).
g([A,B|T],L,C)->g(T,L,lists:duplicate(A-$0,B)++C);g([],_,R)->R;g(_,L,_)->i(L,[]).
h([A|T],A,N,B)->h(T,A,N+1,B);h(L,B,N,C)->i(L,integer_to_list(N)++[B|C]).
i([H|T],A)->h(T,H,1,A);i(_,R)->R.

```

Main function is f, taking the input as an Erlang string and returning the output as a string as well.

```
f("11"). % returns "1"
f("111"). % returns "31"
f("1111111111111"). % returns "131"

```

The function can be made 15 bytes shorter (190) by dropping the more than 9 identical characters case requirement. `f` calls `g` which computes the predecessor recursively, and if the number of characters is odd (found at when computation ends), it calls function `i` which, paired with `h`, computes the next element.

# Answer
> 2 votes
# Haskell, 105

```
import Data.List
l=length
c r|odd$l r=group r>>=(l>>=(.take 1).shows)|x:y:z<-r=[y|_<-['1'..x]]++c z|0<1=r

```

I think it's nice it turned out not using any helper functions :-).

# Answer
> 2 votes
## APL (45)

```
∊{2|⍴⍵:(⊃,⍨⍕∘⍴)¨⍵⊂⍨1,2≠/⍵⋄/⍨∘⍎/¨⌽¨⍵⊂⍨1 0⍴⍨⍴⍵}

```

Yes, that's a valid function definition, even with the  on the outside.

```
      ∊{2|⍴⍵:(⊃,⍨⍕∘⍴)¨⍵⊂⍨1,2≠/⍵⋄/⍨∘⍎/¨⌽¨⍵⊂⍨1 0⍴⍨⍴⍵}'513211'
111112221
      ∊{2|⍴⍵:(⊃,⍨⍕∘⍴)¨⍵⊂⍨1,2≠/⍵⋄/⍨∘⍎/¨⌽¨⍵⊂⍨1 0⍴⍨⍴⍵}'111112221'
513211
      f←∊{2|⍴⍵:(⊃,⍨⍕∘⍴)¨⍵⊂⍨1,2≠/⍵⋄/⍨∘⍎/¨⌽¨⍵⊂⍨1 0⍴⍨⍴⍵}
      f ¨ '513211' '111112221'
┌─────────┬──────┐
│111112221│513211│
└─────────┴──────┘

```

# Answer
> 1 votes
# Javascript (in-browser, ES5, IE8+), 152

```
var s=prompt(),r='',n=r,c=r,i=0;do{c!=s[i]?(r+=n+c,n=1,c=s[i]):n++;i++}while(c)n='';i=0;while(s[i]){n+=Array(1*s[i]+1).join(c=s[i+1]);i+=2}alert(c?n:r)

```

Can be shortened by 4 chars if you skip var, or a few more chars with other intermediate unvarred globals too, but let's pretend we are not bad programmers for a minute.

Switching to ES6 short-syntax function with argument and return value instead of using prompt, alert for IO can save more.

JSFiddle here: http://jsfiddle.net/86L1w6Lk/

# Answer
> 1 votes
# Python 3 - 159 bytes

```
import re;l=input();x=len;print(''.join([str(x(i))+j for i,j in re.findall('((.)\2*)',l)]if x(l)%2 else[j*int(i)for i,j in[l[i:i+2]for i in range(0,x(l),2)]]))

```

# Answer
> 1 votes
# Cobra - 217

(186 if I can assume a `use` statement for `System.Text.RegularExpressions` exists elsewhere)

```
do(s='')=if((l=s.length)%2,System.Text.RegularExpressions.Regex.replace(s,(for x in 10 get'[x]+|').join(''),do(m=Match())="['[m]'.length]"+'[m]'[:1]),(for x in 0:l:2get'[s[x+1]]'.repeat(int.parse('[s[x]]'))).join(''))

```

# Answer
> 1 votes
# JavaScript (ES6) 85

Using regular expression replace with function. Different regexp and different function depending on input length being even or odd.

```
F=s=>s.replace((i=s.length&1)?/(.)(\1*)/g:/../g,x=>i?x.length+x[0]:x[1].repeat(x[0]))

```

# Answer
> 0 votes
# Ruby, 78 bytes

```
->s{s.size%2<1?s.gsub(/(.)(.)/){$2*$1.to_i}:s.gsub(/(.)\1*/){$&.size.to_s+$1}}

```

Attempt This Online!

# Answer
> 0 votes
# 05AB1E, 18 (or 17?) bytes

```
S2ôø`s×IÅγs.ι‚JIgè

```

Try it online or verify some more test cases.

Since the challenge asks for a string input, which by default allows for a list of characters, it would be 1 byte less by removing the leading `S`:
Try it online or verify some more test cases.

**Explanation:**

```
S        # Convert the (implicit) input to a list of digits
 2ô      # Split it into parts of size 2
   ø     # Zip/transpose; swapping rows/columns
    `    # Pop and push both lists separately to the stack
     s   # Swap the two lists on the stack
         # (or swap it with the implicit input if the input was a single digit number)
      ×  # Repeat the digits the numbers amount of times (at the same positions of the
         # lists)
I        # Push the input again
 Åγ      # Run-length encode it, pushing the list of digits and list of lengths
         # separately to the stack
   s     # Swap those two lists on the stack
    .ι   # Interleave the two lists into one:
         #  [a,b,c,...] and [d,e,f,...] → [a,d,b,e,c,f,...]
‚        # Pair the two lists together
 J       # Join both inner lists to a number
  I      # Push the input yet again
   g     # Pop and push its length
    è    # Modular 0-based index it into the pair
         # (after which the result is output implicitly)

```

---
Tags: code-golf
---


title: Interlace strings

text:
# Question
Title: Interlace strings
Your challenge is to write a program or function that, when given two strings of equal length, swaps every other character and outputs/returns the resulting strings in either order.

## Examples

```
"Hello," "world!" --> "Hollo!" "werld,"
"code" "golf" --> "codf" "gole"
"happy" "angry" --> "hnpry" "aagpy"
"qwerty" "dvorak" --> "qvertk" "dworay"
"1, 2, 3" "a, b, c" --> "1, b, 3" "a, 2, c"
"3.141592653589" "2.718281828459" --> "3.111291623489" "2.748582858559"
"DJMcMayhem" "trichoplax" --> "DrMcMoylex" "tJichapham"
"Doorknob" "Downgoat" --> "Doonkoot" "Dowrgnab"
"Halloween" "Challenge" --> "Hhlloeegn" "Caallwnee"

```

## Rules

* The strings will only contain ASCII chars (32-126).
* The strings will always be the same length, and will never be empty.
* You may accept input in any suitable format: separate parameters, items in an array, separated by one or more newlines, even concatenated. The only restriction is that one string must come fully before the other (e.g. `a1\nb2\nc3` for `"abc", "123"` is invalid).
* The output may be **in either order** (i.e. you can start swapping from the first or the second char), and in any valid format mentioned above. (2-item array, separated by newline(s), concatenated, etc.)

## Scoring

This is , so **the shortest code in bytes for each language wins.**

# Answer
> 14 votes
## Haskell, 37 bytes

```
l=(,):flip(,):l
(unzip.).zipWith3($)l

```

Zips the two strings, alternately swapping the characters, then unzips them.

A 37-byte recursive alternative:

```
(a:b)?(c:d)=a:d?b
e?_=e
a%b=(a?b,b?a)

```

# Answer
> 10 votes
## Python, 42 bytes with I/O golfing

```
def f(a,b):a[1::2],b[1::2]=b[1::2],a[1::2]

```

Swaps every other character of the two lists. Takes as input two lists of characters, and outputs by modifying them.

```
l=list('cat')
m=list('dog')
print l,m

def f(a,b):a[1::2],b[1::2]=b[1::2],a[1::2]

f(l,m)
print l,m

```

gives

```
['c', 'a', 't'] ['d', 'o', 'g']
['c', 'o', 't'] ['d', 'a', 'g']

```

# Answer
> 8 votes
# Vim, ~~18~~, 17 bytes

```
qqyljvPkvPll@qq@q

```

Try it online!

This uses the V interpreter because of backwards compatibility. Input comes in this format:

```
string1
string2

```

Explanation:

```
 qq                 " Start recording in register 'q'
   yl               " Yank one letter
     j              " Move down a row
      vP            " Swap the yanked letter and the letter under the cursor
        k           " Move back up a row
         vP         " Swap the yanked letter and the letter under the cursor
           ll       " Move two letters to the right. This will throw an error once we're done
             @q     " Call macro 'q' recursively
               q    " Stop recording.
                @q  " Start the recursive loop

```

# Answer
> 6 votes
# 05AB1E, ~~11~~ 10 bytes

```
øvyNFÀ}})ø

```

Try it online!

**Explanation**

input = `["code", "golf"]` used as example.

```
ø             # zip strings into list of pairs
              # STACK: ['cg', 'oo', 'dl', 'ef']
 vy           # for each pair
   NFÀ        # rotate left index times
      }}      # end-if, end-loop
              # STACK: 'cg, 'oo', 'dl', 'fe'
        )ø    # wrap in list and zip
              # OUTPUT: ['codf', 'gole']

```

# Answer
> 6 votes
## Haskell, 41 bytes

```
(a:b)#(c:d)=(a,c):d#b
_#_=[]
(unzip.).(#)

```

Returns a pair with the strings. Usage example: `( (unzip.).(#) ) "Hello," "world!"`-\> `("Hollo!","werld,")`.

Simple recursive approach: take the first char of each string as a pair and append a recursive call with the (rest of the) strings swapped. `unzip` makes a pair of lists out of the list of pairs.

# Answer
> 5 votes
## Perl, 48 bytes

Bytecount includes 47 bytes of code and `-p` flag.

```
say<>=~s%.\K(.)%"s/.{$-[0]}\\K(.)/$1/;\$1"%geer

```

Run with `-p` and `-E` flag. Expect each string on a different line :

```
perl -pE 'say<>=~s%.\K(.)%"s/.{$-[0]}\\K(.)/$1/;\$1"%geer' <<< "Hello
World"

```

**Explanations** :

`-p` : capture input in `$_` and prints it at the end. (to get and print the first string)
`<>` : get a line of input. (to get the second string).
`=~` : apply a regex to `<>` : `s%%%geer`, where thanks to `r` the modified string is returned (and then printed thanks to `say`).
The regex :
`.\K(.)` finds two characters, and will replace the second one with the result of the evaluation of this code `"s/.{$-[0]}\\K(.)/$1/;\$1"` :
The first part, `s/.{$-[0]}\\K(.)/$1/` applies a regex to `$_` : `.{$-[0]}` skips the first characters to get to the same point as the outer regex (since `$-[0]` contains the index of the first capture group, so in that case the index of the characters to substitute), and then we capture a char with `(.)` and replace it with the character of the outer regex (`$1`). And then we add `$1` so the result of `"s/.{$-[0]}\\K(.)/$1/;\$1"` is the character we captured in the inner regex.
You may have noticed that `$1` refer to the character we want to replace in both strings (so two different characters), so we play with `/ee` modifier of the regex which evaluates the right side of the regex twice : the first one will substitute only the `$1` that isn't preceded by the `\`.

# Answer
> 5 votes
## Python, 55 bytes

```
lambda a,b:[(-~len(a)/2*s)[::len(a)+1]for s in a+b,b+a]

```

Slicing!

58 bytes:

```
def f(a,b):n=len(a);print[(s*n)[:n*n:n+1]for s in a+b,b+a]

```

---

**64 bytes:**

```
f=lambda a,b,s='',t='':a and f(b[1:],a[1:],s+a[0],t+b[0])or[s,t]

```

Recursively accumulates the characters of the two strings into `s` and `t`, and outputs the pair of them at the end. The alternation is done by switching the input strings each recursive call. Outputting a space-separated string was the same length:

```
lambda a,b,s='',t=' ':a and f(b[1:],a[1:],s+a[0],t+b[0])or s+t

```

This narrowly beat out a different recursive strategy of alternately taking characters from each string, with each of the two possible strings as the first one. (65 bytes)

```
g=lambda a,b:a and a[0]+g(b[1:],a[1:])
lambda a,b:(g(a,b),g(b,a))

```

# Answer
> 5 votes
# Jelly, 5 bytes

```
żṚż¥/

```

Input is as separate arguments, output is concatenated.

Try it online! or verify all test cases.

### How it works

```
żṚż¥/  Main link. Left argument: s (string). Right argument: t (string)

ż      Zipwith; yield the array of pairs of corresponding characters of s and t.
   ¥   Combine the two links to the left into a dyadic chain:
 Ṛ         Reverse the chain's left argument.
  ż        Zip the result with the chain's right argument.
    /  Reduce the return value of the initial ż by the quicklink Ṛż¥.

```

# Answer
> 4 votes
# MATL, ~~11~~ ~~10~~ ~~9~~ 8 bytes

*Thanks to ETHproductions for 1 byte off!*

```
"@X@YS&h

```

Input is a 2D array containing the two strings, such as: `['Halloween'; 'Challenge']`. The output strings are in reverse order.

Try it online!

### Explanation

```
        % Input 2D array implicitly
"       % For each column
  @     %   Push current column
  X@    %   Push iteration index, starting at 1
  YS    %   Circularly shift the column by that amount
  &h    %   Concatenate horizontally with (concatenated) previous columns
        % End implicitly
        % Display implicitly

```

---

## Old version: 9 bytes

```
tZyP:1&YS

```

### Explanation

```
        % Take input implicitly
t       % Duplicate
        % STACK: ['Halloween'; 'Challenge'], ['Halloween'; 'Challenge']
Zy      % Size
        % STACK: ['Halloween'; 'Challenge'], [2 9]
P       % Flip array
        % STACK: ['Halloween'; 'Challenge'], [9 2]
:       % Range. Uses first element of the array as input
        % STACK: ['Halloween'; 'Challenge'], [1 2 3 4 5 6 7 8 9]
1&YS    % Circularly shift each column by those amounts respectively
        % STACK: [Caallwnee';'Hhlloeegn']
        % Display implicitly

```

# Answer
> 4 votes
# Jelly, ~~9~~ ~~8~~ 6 bytes

Thanks to *Dennis* for saving 2 bytes!

```
Zṙ"J$Z

```

Uses the **Jelly** encoding.

Try it online!

# Answer
> 3 votes
# , 12 bytes

```
lòyljvPkvPll

```

Try it online!

Nothing too interesting, just a direct port of my vim answer so I can compete with (but not beat) 05AB1E.

# Answer
> 3 votes
## Pyke, 9 bytes

```
,Fo2%I_(,

```

Try it here!

```
          - o = 0
,         -   transpose(input)
 F     (  -  for i in ^:
  o2%     -    (o++ %2)
     I_   -   if ^: i = reverse(i)
        , - transpose(^)

```

# Answer
> 3 votes
# JavaScript (ES6), 51 ~~54~~

*Edit* 3 bytes saved thx @Neil

Function with array input/output

```
p=>p.map((w,i)=>w.replace(/./g,(c,j)=>p[i+j&1][j]))

```

I like this one more, but it's 55 (2 strings in input, array in output)

```
(a,b)=>[...a].reduce(([p,q],c,i)=>[q+c,p+b[i]],['',''])

```

**Test**

```
f=
p=>p.map((w,i)=>w.replace(/./g,(c,j)=>p[i+j&1][j]))

function go() {
  var a=A.value, b=B.value
  if (a.length == b.length)
    O.textContent = f([a,b]).join('\n')
  else
    O.textContent = '- different length -'

}

go()
```

```
<input id=A value='Hello,'><input id=B value='world!'>
<button onclick='go()'>go</button><pre id=O></pre>
```

# Answer
> 2 votes
# Pyth, 8 bytes

```
C.e_FbkC

```

Try it online: Demonstration

Transposes the words, reverses each pair of letters 'current index'-times, transpose again.

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

```
f=([c,...s],[d,...t],o="",p="")=>c?f(t,s,o+c,p+d):[o,p]

```

I wanted to do something clever with using regexp to replace alternate characters but that ended up taking ~~67~~ 57 bytes:

```
a=>a.map((s,i)=>a[+!i].replace(/.(.?)/g,(_,c,j)=>s[j]+c))

```

# Answer
> 2 votes
## Java, 132 103 100 bytes

*Thanks to Kevin Cruijssen for suggesting returning the array (among other improvements) and saving 29 bytes! Also Olivier Grégoire for 3 bytes!*

```
char[]c(char[]s,int l){for(int o=l;o-->0;)if(o%2>0){char t=s[o];s[o]=s[l+o+1];s[l+o+1]=t;}return s;}

```

Called like this:

```
public static void main(String[] args) {
    System.out.println(c("Hello,world!".toCharArray(), 5)); // 5 is the length of each "String"
}

```

Output:

`Hollo,werld!`

Takes advantage of the fact that input can basically be formatted in any way (in this case, a single char array of Strings that are delimited by a comma), and pretty lenient output rules as well.

# Answer
> 2 votes
# Perl, 40 bytes

Includes +1 for `-n`

Give strings as lines on STDIN

```
interlace.pl
hello
world
^D

```

`interlace.pl`

```
#!/usr/bin/perl -n
s/./${1&$.+pos}[pos]=$&/seg}{print@0,@1

```

# Answer
> 1 votes
## PowerShell v2+, 82 bytes

```
param($a,$b)$i=0;[char[]]$a|%{$c+=($_,$b[$i])[$i%2];$d+=($b[$i],$_)[$i++%2]};$c;$d

```

~~Still golfing...~~ Nope. Can't seem to golf this down any without using a regex like other answers (boo on copying algorithms).

So we take `$a` and `$b` as strings, set index `$i` to `0`, cast `$a` as a `char`-array, and send it through a loop `|%{...}`. Each iteration, we're string-concatenating onto `$c` and `$d` by indexing into an array-select (i.e., so it alternates back and forth). Then, we leave `$c` and `$d` on the pipeline, and output via implicit `Write-Output` happens at program completion.

# Answer
> 1 votes
# PHP, 79 Bytes

```
for(;$i<=strlen(($a=$argv)[1]);$y.=$a[2-$i%2][$i++])echo$a[1+$i%2][+$i]??" $y";

```

Previous Version PHP, 82 Bytes

```
for(;$i<strlen(($a=$argv)[1]);$y.=$a[2-$i%2][$i++])$x.=$a[1+$i%2][$i];echo"$x $y";

```

# Answer
> 1 votes
# C, 124 bytes

```
main(c,v)char**v;{char a[99],b[99];for(c=0;v[1][c]^0;++c){a[c]=v[1+c%2][c];b[c]=v[2-c%2][c];}a[c]=0;b[c]=0;puts(a);puts(b);}

```

Call with:

```
program.exe string1 string2

```

String length is limited to 98 characters.

# Answer
> 1 votes
# Octave, ~~64~~ 61 bytes

```
@(x)reshape(x((t=1:end)+(2*mod(t,2)-1).*(mod(t-1,4)>1)),2,[])

```

Anonymous function that inputs a 2D char array with each string in a row, and produces the output in the same format.

Try it at Ideone.

# Answer
> 1 votes
## Racket 208 bytes

```
(let((sl string->list)(ls list->string)(r reverse))(let p((s(sl s))(t(sl t))(u'())(v'())(g #t))(if(null? s)
(list(ls(r u))(ls(r v)))(p(cdr s)(cdr t)(cons(car(if g s t))u)(cons(car(if g t s))v)(if g #f #t)))))

```

Ungolfed:

```
(define (f s t)
  (let ((sl string->list)                ; create short names of fns
        (ls list->string)
        (r reverse))
    (let loop ((s (sl s))                ; convert string to lists
               (t (sl t))
               (u '())                   ; create empty new lists
               (v '())
               (g #t))                   ; a boolean flag
      (if (null? s)                      ; if done, return new lists converted back to strings
          (list (ls (r u))
                (ls (r v)))
          (loop (rest s)
                (rest t)                 ; keep adding chars to new lists alternately
                (cons (first (if g s t)) u)
                (cons (first (if g t s)) v)
                (if g #f #t))            ; alternate the boolean flag
          ))))

```

Testing:

```
(f "abcdef" "123456")

```

Output:

```
'("a2c4e6" "1b3d5f")

```

Above is recursive version.

Iterative version:

```
(let*((sl string->list)(ls list->string)(r reverse)(s(sl s))(t(sl t))(l'())(k'())(p(λ(a b g)(set! l(cons(if g a b)l))
(set! k(cons(if g b a)k)))))(for((i s)(j t)(n(in-naturals)))(p i j(if(= 0(modulo n 2)) #t #f)))(list(ls(r l))(ls(r k))))

```

Ungolfed:

```
(define (f s t)
  (let* ((sl string->list)              ; create short form of fn names
         (ls list->string)
         (r reverse)

         (s (sl s))                     ; convert strings to lists
         (t (sl t))

         (l '())                        ; create empty lists for new sequences
         (k '())

         (p (λ(a b g)                   ; fn to add chars to one or other list
              (set! l (cons (if g a b) l))
              (set! k (cons (if g b a) k)))))

    (for ((i s)(j t)(n (in-naturals)))  ; loop with both strings
          (p i j                        ; add to new lists alternately
             (if (= 0 (modulo n 2)) #t #f)))

    (list (ls (r l))                  ; convert reversed lists to strings
          (ls (r k)))))

```

# Answer
> 1 votes
# Lithp, 120 characters (+3 for -v1 flag)

Line split in 2 for readability:

```
#P::((invoke P "map" (js-bridge #W,I::(replace W (regex "." "g")
     (js-bridge #C,J::(index (index P (& (+ I J) 1)) J))))))

```

Requires the `-v1` flag to `run.js` as some functions are not yet part of the standard library.

Sample usage:

```
(
    (def f #P::((invoke P "map" (js-bridge #W,I::(replace W (regex "." "g")
                (js-bridge #C,J::(index (index P (& (+ I J) 1)) J)))))))
    (print (f (list "Hello," "world!")))
)

```

This sort of highlights that I haven't spent enough time on the standard library. Having to use `js-bridge/1` twice and the long regex form, as well as invoking map using `invoke/*` all contribute to this being much longer than it needs to be.

Time to work on my standard library more I think.

# Answer
> 1 votes
# C, ~~54~~ 52 bytes

```
f(char*a,char*b,char*c){while(*c++=*a++,*c++=*b++);}

```

Assumes output `c` has already the desired length.

Usage:

```
main(){
 char a[]="123456";
 char b[]="abcdef";
 char c[sizeof(a)+sizeof(b)-1];
 f(a,b,c);
 puts(c);

```

}

If you insist on creating the output, here is a **91 bytes** solution:

```
char*g(char*a,char*b){char*c=malloc(2*strlen(a)),*d=c;while(*c++=*a++,*c++=*b++);return d;}

```

Usage:

```
main(){
 char a[]="123456";
 char b[]="abcdef";
 puts(g(a,b));
}

```

# Answer
> 1 votes
# Japt, ~~8~~ 4 bytes

```
yÈéY

```

Try it

```
yÈéY     :Implicit input of array U
y        :Transpose
 È       :Map each element at 0-based index Y then transpose back
  éY     :  Rotate right Y times

```

# Answer
> 1 votes
# , 32 bytes

```
{?[;x;y]each(not\)count[x]#10b}.

```

# k, 24 bytes

```
{?[;x;y]'(~:\)(#x)#10b}.

```

# Answer
> 0 votes
# C, 150 bytes

I used the typical omissions of header files and `main()`'s return type and return statement. It throws a warning, but compiles without issue. I also used a GCC-specific trick that allows array declarations with variable expressions.

The program expects the strings from the command line, and as such, the program should be run with `./a.out string1 string2`.

```
main(int a,char**v){int x=strlen(v[1]);char s[x],t[x],c;strcpy(s,v[1]);strcpy(t,v[2]);for(a=0;a<x;++a)if(a%2)c=s[a],s[a]=t[a],t[a]=c;puts(s),puts(t);}

```

Or more legibly,

```
main(int a,char**v){
    int x=strlen(v[1]);
    char s[x],t[x],c;
    strcpy(s,v[1]);strcpy(t,v[2]);
    for(a=0;a<x;++a)
        if(a%2)c=s[a],s[a]=t[a],t[a]=c;
    puts(s),puts(t);
}

```

# Answer
> 0 votes
# Mathematica, 51 bytes

Takes input as an array of two arrays of characters, with output in the same format. The function simply constructs the new array using a (mod 2) operation.

```
Table[#[[Mod[j+i,2]+1,j]],{i,2},{j,Length@#[[1]]}]&

```

# Answer
> 0 votes
# QBasic 4.5, 172 bytes

Ouch, this one gets painful with the ol' QBasic...

```
DEFSTR A-D:INPUT A,B
IF LEN(A)MOD 2=1 THEN A=A+" ":B=B+" "
FOR x=1 TO LEN(A) STEP 2
C=C+MID$(A,x,1)+MID$(B,x+1,1):D=D+MID$(B,x,1)+MID$(A,x+1,1):NEXT:?RTRIM$(C),RTRIM$(D)

```

Fun fact: Using `DEFSTR` saved more bytes than it cost because now I could use `A` instead of `a$`.

# Answer
> 0 votes
# QBIC, 112 bytes

QBIC can streamline a lot of the QBasic boilerplate, but the main `MID$`engine still needs to be done in QBasic because QBIC lacks a substring-function. Still, saves me 60 bytes.

```
;;_LA|~a%2=1|A=A+@ | B=B+C][1,a,2|X=X+$MID$(A$,b,1)+MID$(B$,b+1,1):Y$=Y$+MID$(B$,b,1)+MID$(A$,b+1,1)|]?_tX|,_tY|

```

# Answer
> 0 votes
# Java, 68 bytes

```
(a,b)->{for(int i=a.length;--i>0;){char t=a[--i];a[i]=b[i];b[i]=t;}}

```

## Ungolfed and testing

```
import java.util.Arrays;
import java.util.Collection;
import java.util.function.BiConsumer;

public class Main {

  static BiConsumer<char[], char[]> func = (left, right) -> {
      for (int i = left.length; --i > 0;) {
        char temp = left[--i];
        left[i] = right[i];
        right[i] = temp;
      }
    };

  public static void main(String[] args) {
    test("Hello,","world!", "Hollo!", "werld,");
    test("code", "golf", "codf", "gole");
    test("happy", "angry", "hnpry", "aagpy");
  }

  private static void test(String left, String right, String x, String y) {
    char[] leftChars = left.toCharArray();
    char[] rightChars = right.toCharArray();
    func.accept(leftChars, rightChars);
    Collection mixed = Arrays.asList(new String(leftChars), new String(rightChars));
    if (mixed.containsAll(Arrays.asList(x, y))) {
      System.out.println("OK");
    } else {
      System.out.printf("NOK: %s, %s -> %s%n", left, right, mixed);
    }
  }
}

```

# Answer
> 0 votes
## APL, 12

```
{↓(⍳⍴⊃⍵)⊖↑⍵}

```

Explanation: {...} defines a function, ⍵ is the right argument. The take (↑) creates a matrix out of the two strings, then rotates each column (⊖) n times, where n is the part in parenthesis (⍳⍴⊃⍵). That's defined as the iota of the length of the first argument. (Ex: length=5 ==\> 1 2 3 4 5). So first column is rotated once, second twice (getting back to original positions), third column three times, etc...

Try it at tryapl.org

# Answer
> 0 votes
# Scala, 85 bytes

```
(_:String)zip(_:String)zip(Stream from 0)map{case(t,z)=>if(z%2==0)t else t.swap}unzip

```

take an anonymous string parameter, zip it with another string parameter, zip it with an stream of natural numbers, swap every second tuple of chars and unzip to get a tuple of sequences of chars

# Answer
> 0 votes
# Swift 3, ~~129~~ 107 bytes

```
func c(n:inout[String],b:inout[String]){
for(j,c)in n.enumerated(){
if j&1<1{n[j]=b[j];b[j]=c}}
print(n,b)}

```

**Original**

The function receives two arrays of strings as parameters assuming both have same length, as follows:

```
c(n:["c", "o", "d", "e"],b:["g", "o", "l", "f"])

```

Produces following output

```
codf gole

```

**Edit 1:**

Get rid of the internal tuple and change the parameters of the function to be `inout`. Instead of string concatenation manipulate the parameters directly.

Example input:

```
var a:Array<String> = ["c", "o", "d", "e"]
var b:Array<String> = ["g", "o", "l", "f"]

c(n:&a,b:&b)

```

Ouput changed to be array of strings as in:

`["g", "o", "l", "e"] ["c", "o", "d", "f"]`

# Answer
> 0 votes
# Husk, 7 bytes

```
Tz*İ_ze

```

Try it online!

Outputs are reversed.

# Answer
> 0 votes
# Ly, 11 bytes

```
ir>ir[<o>o]

```

Try it online!

This takes the two strings on separate input lines, and outputs the interlaced strings concatenated together. At a high level... It reads the two strings onto separate stacks, then just loops printing the top the each stack.

```
ir          - read first string onto the stack, reverse it
  >ir       - switch to new stack, read second string and reverse it
     [    ] - loop until the stack is empty
      <o    - switch to first stack and print a char
        >o  - switch to the second stack and print a char

```

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


title: All the single eights

text:
# Question
Title: All the single eights
Given a non-empty rectangular array of integers from `0` to `9`, output the amount of cells that are `8` and do not have a neighbour that is `8`. Neighbouring is here understood in the Moore sense, that is, including diagonals. So each cell has `8` neighbours, except for cells at the edges of the array.

For example, given the input

```
8 4 5 6 5
9 3 8 4 8
0 8 6 1 5
6 7 9 8 2
8 8 7 4 2

```

the output should be `3`. The three qualifying cells would be the following, marked with an asterisk (but only the amount of such entries should be output):

```
* 4 5 6 5
9 3 8 4 *
0 8 6 1 5
6 7 9 * 2
8 8 7 4 2

```

## Additional rules

## Test cases

1. Input:

```
8 4 5 6 5
9 3 8 4 8
0 8 6 1 5
6 7 9 8 2
8 8 7 4 2

```

Output: `3`
2. Input

```
8 8
2 3

```

Output: `0`
3. Input:

```
5 3 4
2 5 2

```

Output: `0`
4. Input:

```
5 8 3 8

```

Output: `2`
5. Input:

```
8
0
8

```

Output: `2`.
6. Input:

```
4 2 8 5
2 6 1 8
8 5 5 8

```

Output: `1`
7. Input:

```
4 5 4 3 8 1 8 2
8 2 7 7 8 3 9 3
9 8 7 8 5 4 2 8
4 5 0 2 1 8 6 9
1 5 4 3 4 5 6 1

```

Output `3`.
8. Input:

```
8

```

Output: `1`
9. Input:

```
8 5 8 1 6 8 7 7
9 9 2 8 2 7 8 3
2 8 4 9 7 3 2 7
9 2 9 7 1 9 5 6
6 9 8 7 3 1 5 2
1 9 9 7 1 8 8 2
3 5 6 8 1 4 7 5

```

Output: `4`.
10. Input:

```
8 1 8
2 5 7
8 0 1

```

Output: `3`.

Inputs in MATLAB format:

```
[8 4 5 6 5; 9 3 8 4 8; 0 8 6 1 5; 6 7 9 8 2; 8 8 7 4 2]
[8 8; 2 3]
[5 3 4; 2 5 2]
[5 8 3 8]
[8; 0; 8]
[4 2 8 5; 2 6 1 8; 8 5 5 8]
[4 5 4 3 8 1 8 2; 8 2 7 7 8 3 9 3; 9 8 7 8 5 4 2 8; 4 5 0 2 1 8 6 9; 1 5 4 3 4 5 6 1]
[8]
[8 5 8 1 6 8 7 7; 9 9 2 8 2 7 8 3; 2 8 4 9 7 3 2 7; 9 2 9 7 1 9 5 6; 6 9 8 7 3 1 5 2; 1 9 9 7 1 8 8 2; 3 5 6 8 1 4 7 5]
[8 1 8; 2 5 7; 8 0 1]

```

Inputs in Python format:

```
[[8, 4, 5, 6, 5], [9, 3, 8, 4, 8], [0, 8, 6, 1, 5], [6, 7, 9, 8, 2], [8, 8, 7, 4, 2]]
[[8, 8], [2, 3]]
[[5, 3, 4], [2, 5, 2]]
[[5, 8, 3, 8]]
[[8], [0], [8]]
[[4, 2, 8, 5], [2, 6, 1, 8], [8, 5, 5, 8]]
[[4, 5, 4, 3, 8, 1, 8, 2], [8, 2, 7, 7, 8, 3, 9, 3], [9, 8, 7, 8, 5, 4, 2, 8], [4, 5, 0, 2, 1, 8, 6, 9], [1, 5, 4, 3, 4, 5, 6, 1]]
[[8]]
[[8, 5, 8, 1, 6, 8, 7, 7], [9, 9, 2, 8, 2, 7, 8, 3], [2, 8, 4, 9, 7, 3, 2, 7], [9, 2, 9, 7, 1, 9, 5, 6], [6, 9, 8, 7, 3, 1, 5, 2], [1, 9, 9, 7, 1, 8, 8, 2], [3, 5, 6, 8, 1, 4, 7, 5]]
[[8, 1, 8], [2, 5, 7], [8, 0, 1]]

```

Outputs:

```
3, 0, 0, 2, 2, 1, 3, 1, 4, 3

```

# Answer
> 3 votes
# MATL, ~~21~~ ~~17~~ 10 bytes

```
8=t3Y6Z+>z

```

Try it online!

Thanks to Luis Mendo for help in chat, and for suggesting 2D convolution.

Explanation:

```
	#implicit input, m
8=	#equal to 8? matrix of 1 where m is 8, 0 otherwise
t	#duplicate
3Y6	#push [1 1 1; 1 0 1; 1 1 1], "neighbor cells" for convolution
Z+	#2D convolution; each element is replaced by the number of neighbors that are 8
>	#elementwise greater than -- matrix of 1s where an 8 is single, 0s otherwise
z	#number of nonzero elements -- number of single eights
	#implicit output

```

# Answer
> 9 votes
# , ~~117 63~~ 59 bytes

```
function(m)sum(colSums(as.matrix(dist(which(m==8,T)))<2)<2)

```

Try it online!

`dist` computes distances (default is Euclidean) among rows of a matrix. `which` with second argument `TRUE` returns the coordinates where the predicate is true.

Coordinates are neighbours if the distance between them is not more than the square root of 2, but the inner `<2` is good enough because the possible distance jumps from `sqrt(2)` ro `2`.

# Answer
> 7 votes
# APL (Dyalog Classic), ~~29~~ ~~28~~ 25 bytes

```
≢∘⍸16=2⊥¨3,⌿3,/8=(⍉0,⌽)⍣4

```

Try it online!

# Answer
> 5 votes
# Jelly, ~~18~~ 15 bytes

```
8=µ+Ż+ḊZµ⁺ỊṖḋµS

```

Try it online!

### How it works

```
8=µ+Ż+ḊZµ⁺ỊṖḋµS    Main link (monad). Input: digit matrix
8=              1) Convert elements by `x == 8`
  µ             2) New chain:
   +Ż+Ḋ              x + [0,*x] + x[1:] (missing elements are considered 0)
                     Effectively, vertical convolution with [1,1,1]
       Z             Transpose
        µ⁺      3) Start new chain, apply 2) again
          ỊṖ       Convert elements by `|x| <= 1` and remove last row
            ḋ      Row-wise dot product with result of 1)
             µS 4) Sum

```

# Previous solution, 18 bytes

```
æc7B¤ZḊṖ
8=µÇÇỊḋµS

```

Try it online!

Wanted to share another approach, though this is 1 byte longer than Jonathan Allan's solution.

### How it works

```
æc7B¤ZḊṖ    Auxiliary link (monad). Input: integer matrix
æc7B¤       Convolution with [1,1,1] on each row
     ZḊṖ    Zip (transpose), remove first and last elements

8=µÇÇỊḋµS    Main link (monad). Input: digit matrix
8=           Convert 8 to 1, anything else to 0 (*A)
  µÇÇ        Apply aux.link twice (effective convolution with [[1,1,1]]*3)
     Ịḋ      Convert to |x|<=1, then row-wise dot product with A
       µS    Sum the result

```

# Answer
> 4 votes
# Jelly, 17 bytes

```
=8ŒṪµŒcZIỊȦƲƇẎ⁸ḟL

```

**Try it online!** Or see the test-suite.

### How?

```
=8ŒṪµŒcZIỊȦƲƇẎ⁸ḟL - Link: list of lists of integers (digits)
=8                - equals 8?
  ŒṪ              - multidimensional truthy indices (pairs of row & column indices of 8s)
    µ             - start a new monadic chain
     Œc           - all pairs (of the index-pairs)
            Ƈ     - filter keep if:  (keep those that represent adjacent positions)
           Ʋ      -   last four links as a monad:
       Z          -     transpose
        I         -     incremental differences
         Ị        -     insignificant? (abs(x) <= 1)
          Ȧ       -     all?
             Ẏ    - tighten (to a list of all adjacent 8's index-pairs, at least once each)
              ⁸   - chain's left argument (all the index-pairs again)
               ḟ  - filter discard (remove those found to be adjacent to another)
                L - length (of the remaining pairs of indices of single 8s)

```

# Answer
> 4 votes
# JavaScript (Node.js), ~~88~~ 85 bytes

```
a=>g=(x,y=0,c=0)=>a.map(p=>p.map((q,j)=>c+=q-8?0:1/x?(x-j)**2+y*y<3:g(j,-y)<2)&--y)|c

```

Try it online!

Thank Arnauld for 2 bytes

# Answer
> 4 votes
# ,43, 40 37 bytes

-3 bytes thanks to Bubbler

```
1#.1#.3 3(16=8#.@:=,);._3(0|:@,|.)^:4

```

Try it online!

## Explanation:

The first part of the algorithm assures that we can apply a 3x3 sliding window to he input. This is achieved by prepending a row of zeroes and 90 degrees rotation, repeated 4 times.

```
1#.1#.3 3(16=8#.@:=,);._3(0|:@,|.)^:4
                         (       )^:4 - repeat 4 times
                          0|:@,|.     - reverse, prepend wit a row of 0 and transpose
                     ;._3             - cut the input (already outlined with zeroes)
      3 3                             - into matrices with size 3x3
         (          )                 - and for each matrix do
                   ,                  - ravel (flatten)
             8    =                   - check if each item equals 8
              #.@:                    - and convert the list of 1s and 0s to a decimal
          16=                         - is equal to 16?
   1#.                                - add (the result has the shape of the input)
1#.                                   - add again

```

# Answer
> 4 votes
# Java 8, ~~181~~ ~~157~~ ~~156~~ ~~149~~ 147 bytes

```
(M,R,C)->{int z=0,c,f,t;for(;R-->0;)for(c=C;c-->0;z+=f%9/8)for(f=t=9;M[R][c]==8&t-->0;)try{f-=M[R+t/3-1][c+t%3-1]%9/8;}finally{continue;}return z;}

```

-24 bytes thanks to *@OlivierGrégoire*
-2 bytes thanks to *@ceilingcat*.

Takes the dimensions as additional parameters `R` (amount of rows) and `C` (amount of columns).

The cells are checked pretty similar as I did in my *Fryer simulator* answer.

Try it online.

**Explanation:**

```
(M,R,C)->{                  // Method with integer-matrix as parameter & integer return
  int z=0,                  //  Result-counter, starting at 0
      c,f,t;                //  Temp-integers, starting uninitialized
  for(;R-->0;)              //  Loop over the rows:
    for(c=C;c-->0           //   Inner loop over the columns:
           ;                //     After every iteration:
            z+=f%9/8)       //      If the digit in this cell is 8:
                            //       Increase the result-counter by 1
                            //      Else: leave it the same
      for(f=t=9;            //    Reset the flag to 9
          M[R][c]==8&       //    If the current cell contains an 8:
            t-->0;)         //     Inner loop `t` in the range (9, 0]:
        try{f-=             //      Decrease the flag by:
               M[R+t/3-1]   //       If `t` is 0, 1, or 2: Look at the previous row
                            //       Else-if `t` is 3, 4, or 5: Look at the current row
                            //       Else (`t` is 6, 7, or 8): Look at the next row
                [c+t%3-1]   //       If `t` is 0, 3, or 6: Look at the previous column
                            //       Else-if `t` is 1, 4, or 7: Look at the current column
                            //       Else (`t` is 2, 5, or 8): Look at the next column
                %9/8;       //       And if the digit in this cell is 8:
                            //        Decrease the flag-integer by 1
                            //       Else: leave it the same
        }finally{continue;} //      Catch and ignore ArrayIndexOutOfBoundsExceptions
                            //      (try-finally saves bytes in comparison to if-checks)
  return z;}                //  And finally return the counter

```

# Answer
> 3 votes
# Retina 0.8.2, 84 bytes

```
.+
_$&_
m`(?<!(?(1).)^(?<-1>.)*.?.?8.*¶(.)*.|8)8(?!8|.(.)*¶.*8.?.?(?<-2>.)*$(?(2).))

```

Try it online! Explanation:

```
.+
_$&_

```

Wrap each line in non-`8` characters so that all `8`s have at least one character on each side.

```
m`

```

This is the last stage, so counting matches is implied. The `m` modifier makes the `^` and `$` characters match at the start or end of any line.

```
(?<!...|8)

```

Don't match a character directly after an 8, or...

```
(?(1).)^(?<-1>.)*.?.?8.*¶(.)*.

```

... a character below an 8; the `(?(1).)^(?<-1>.)*` matches the same column as the `¶(.)*` on the next line, but the `.?.?` allows the `8` to be 1 left or right of the character after the `.` on the next line.

```
8

```

Match `8`s.

```
(?!8|...)

```

Don't match an 8 immediately before an 8, or...

```
.(.)*¶.*8.?.?(?<-2>.)*$(?(2).)

```

... a character with an 8 in the line below; again, the `(?<-2>.)*$(?(2).)` matches the same column as the `(.)*¶` on the previous line, but the `.?.?` allows the `8` to be 1 left or right of the `8` before the `.` on the previous line.

# Answer
> 3 votes
# J, 42 bytes

```
[:+/@,8=]+[:+/(<:3 3#:4-.~i.9)|.!.0(_*8&=)

```

Try it online!

# explanation

The high-level approach here is similar to the one used in the classic APL solution to the game of life: https://www.youtube.com/watch?v=a9xAKttWgP4.

In that solution, we shift our matrix in the 8 possible neighbor directions, creating 8 duplicates of the input, stack them up, and then add the "planes" together to get our neighbor counts.

Here, we use a "multiply by infinity" trick to adapt the solution for this problem.

```
[: +/@, 8 = ] + [: +/ (neighbor deltas) (|.!.0) _ * 8&= NB.
                                                        NB.
[: +/@,                                                 NB. the sum after flattening
        8 =                                             NB. a 0 1 matrix created by
                                                        NB. elmwise testing if 8
                                                        NB. equals the matrix
            (the matrix to test for equality with 8   ) NB. defined by...
            ] +                                         NB. the original input plus
                [: +/                                   NB. the elmwise sum of 8
                                                        NB. matrices defined by
                                                _ *     NB. the elmwise product of
                                                        NB. infinity and
                                                    8&= NB. the matrix which is 1
                                                        NB. where the input is 8
                                                        NB. and 0 elsewhere, thus
                                                        NB. creating an infinity-0
                                                        NB. matrix
                                        (|.!.0)         NB. then 2d shifting that
                                                        NB. matrix in the 8 possible
                                                        NB. "neighbor" directions
                      (neighbor deltas)                 NB. defined by the "neighbor
                                                        NB. deltas" (see below)
                                                        NB. QED.
                                                        NB. ***********************
                                                        NB. The rest of the
                                                        NB. explanation merely
                                                        NB. breaks down the neighbor
                                                        NB. delta construction.

                      (neighbor deltas  )               NB. the neighbor deltas are
                                                        NB. merely the cross product
                                                        NB. of _1 0 1 with itself,
                                                        NB. minus "0 0"
                      (<: 3 3 #: 4 -.~ i.9)             NB. to create that...
                       <:                               NB. subtract one from
                          3 3 #:                        NB. the base 3 rep of
                                       i.9              NB. the numbers 0 - 8
                                 4 -.~                  NB. minus the number 4
                                                        NB.
                                                        NB. All of which produces
                                                        NB. the eight "neighbor"
                                                        NB. deltas:
                                                        NB.
                                                        NB.       _1 _1
                                                        NB.       _1  0
                                                        NB.       _1  1
                                                        NB.        0 _1
                                                        NB.        0  1
                                                        NB.        1 _1
                                                        NB.        1  0
                                                        NB.        1  1

```

# Answer
> 3 votes
# Jelly, 12 bytes

```
œẹ8ạṀ¥þ`’Ạ€S

```

Try it online!

### How it works

```
œẹ8ạṀ¥þ`’Ạ€S  Main link. Argument: M (matrix)

œẹ8           Find all multidimensional indices of 8, yielding an array A of pairs.
      þ`      Table self; for all pairs [i, j] and [k, l] in A, call the link to the
              left. Return the results as a matrix.
   ạ              Absolute difference; yield [|i - k|, |j - l|].
    Ṁ             Take the maximum.
        ’     Decrement all the maxmima, mapping 1 to 0.
         Ạ€   All each; yield 1 for each row that contains no zeroes.
           S  Take the sum.

```

# Answer
> 3 votes
# 05AB1E, 27 bytes

```
8Q2Fø0δ.ø}2Fø€ü3}˜9ôʒÅs}OΘO

```

Try it online or verify all test cases.

**Explanation:**

```
8Q       # Check for each inner value in the (implicit) input-matrix if it's an 8
         # (1 if 8; 0 if not)
2Fø0δ.ø} # Add a border of 0s around the matrix:
2F     } #  Loop 2 times:
  ø      #   Zip/transpose; swapping rows/columns
    δ    #   Map over each inner list:
   0 .ø  #    Surround it with a leading/trailing 0
2Fø€ü3}  # Then get all overlapping 3x3 blocks of this modified matrix:
2F    }  #  Loop 2 times again:
  ø      #   Zip/transpose again
   €     #   Map over each inner list again:
    ü3   #    Split it into overlapping triplets
˜        # Flatten the entire list of lists of lists of lists of integers
         # (aka the list of lists of 3x3 blocks)
 9ô      # Split it into parts of size 9
         # (so we now have a single list with flattened 3x3 blocks)
ʒÅs}     # Keep the (flattened) 3x3 blocks with a 1 in the center:
ʒ  }     # Filter over the list of flattened 3x3 blocks:
 Ås      #  Pop the list and push its center value
O        # Sum the inner lists of any remaining flattened 3x3 block
 Θ       # Check for each sum whether it's equal to 1 (1 if 1; 0 otherwise)
  O      # Sum those together again
         # (after which this sum is output implicitly as result)

```

# Answer
> 2 votes
# Python 2, 130 bytes

```
lambda a:sum(sum(u[~-c*(c>0):c+2].count(8)for u in a[~-r*(r>0):r+2])*8==8==a[r][c]for r in range(len(a))for c in range(len(a[0])))

```

Try it online!

# Answer
> 2 votes
# Powershell, 121 bytes

```
param($a)(($b='='*4*($l=($a|% Le*)[0]))+($a|%{"!$_!"})+$b|sls "(?<=[^8]{3}.{$l}[^8])8(?=[^8].{$l}[^8]{3})" -a|% m*).Count

```

Less golfed test script:

```
$f = {

param($a)

$length=($a|% Length)[0]
$border='='*4*$length
$pattern="(?<=[^8]{3}.{$length}[^8])8(?=[^8].{$length}[^8]{3})"
$matches=$border+($a|%{"!$_!"})+$border |sls $pattern -a|% Matches
$matches.count

}

@(

,(3,"84565","93848","08615","67982","88742")
,(0,"88","23")
,(0,"534","252")
,(2,"5838")
,(2,"8","0","8")
,(1,"4285","2618","8558")
,(3,"45438182","82778393","98785428","45021869","15434561")
,(1,"8")
,(4,"85816877","99282783","28497327","92971956","69873152","19971882","35681475")
,(3,"818","257","801")
,(0,"")

) | % {
    $expected,$a = $_
    $result = &$f $a
    "$($result-eq$expected): $result : $a"
}

```

Output:

```
True: 3 : 84565 93848 08615 67982 88742
True: 0 : 88 23
True: 0 : 534 252
True: 2 : 5838
True: 2 : 8 0 8
True: 1 : 4285 2618 8558
True: 3 : 45438182 82778393 98785428 45021869 15434561
True: 1 : 8
True: 4 : 85816877 99282783 28497327 92971956 69873152 19971882 35681475
True: 3 : 818 257 801
True: 0 :

```

Explanation:

First, the script calculates a length of the first string.

Second, it adds extra border to strings. Augmended ~~reality~~ string likes:

```
....=========!84565! !93848! !08615! !67982! !88742!===========....

```

represents the multiline string:

```
...=====
=======
!84565!
!93848!
!08615!
!67982!
!88742!
=======
========...

```

Note 1: the number of `=` is sufficient for a string of any length.

Note 2: a large number of `=` does not affect the search for eights.

Next, the regular expression `(?<=[^8]{3}.{$l}[^8])8(?=[^8].{$l}[^8]{3})` looks for the digit `8` with the preceding non-eights `(?<=[^8]{3}.{$l}[^8])` and the following non-eights `(?=[^8].{$l}[^8]{3})`:

```
.......
<<<....
<8>....
>>>....
.......

```

Finally, the number of matches is returned as a result.

# Answer
> 1 votes
# JavaScript (ES6), 106 bytes

```
a=>a.map((r,y)=>r.map((v,x)=>k+=v==8&[...'12221000'].every((d,i,v)=>(a[y+~-d]||0)[x+~-v[i+2&7]]^8)),k=0)|k

```

Try it online!

---

# Bitwise approach, 110 bytes

```
a=>a.map(r=>r.map(v=>x=x*2|v==8,x=k=0)|x).map((n,y,b)=>a[0].map((_,x)=>(n^1<<x|b[y-1]|b[y+1])*2>>x&7||k++))&&k

```

Try it online!

# Answer
> 1 votes
# Clojure, ~~227~~ 198 bytes

```
(fn[t w h](let[c #(for[y(range %3 %4)x(range % %2)][x y])e #(= 8(get-in t(reverse %)0))m(fn[[o p]](count(filter e(c(dec o)(+ o 2)(dec p)(+ p 2)))))](count(filter #(= 1(m %))(filter e(c 0 w 0 h))))))

```

Ouch. Definitely not the shortest here by any means. 54 bytes of parenthesis is killer. I'm still relatively happy with it though.

**-29 bytes** by creating a helper function that generates a range since I was doing that twice, changing the `reduce` to a `(count (filter` setup, and getting rid of the threading macro after golfing.

```
(defn count-single-eights [td-array width height]
  ; Define three helper functions. One generates a list of coords for a given range of dimensions, another checks if an eight is
  ; at the given coord, and the other counts how many neighbors around a coord are an eight
  (letfn [(coords [x-min x-max y-min y-max]
            (for [y (range y-min y-max)
                  x (range x-min x-max)]
              [x y]))
          (eight? [[x y]] (= 8 (get-in td-array [y x] 0)))
          (n-eights-around [[cx cy]]
            (count (filter eight?
                           (coords (dec cx) (+ cx 2), (dec cy) (+ cy 2)))))]

    ; Gen a list of each coord of the matrix
    (->> (coords 0 width, 0 height)

         ; Remove any coords that don't contain an eight
         (filter eight?)

         ; Then count how many "neighborhoods" only contain 1 eight
         (filter #(= 1 (n-eights-around %)))
         (count))))

(mapv #(count-single-eights % (count (% 0)) (count %))
      test-cases)
=> [3 0 0 2 2 1 3 1 4 3]

```

Where `test-cases` is an array holding all the "Python test cases"

Try it online!

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


# Question
Title: Transform a lattice polygon to minimum diameter by shearing
Given is a grid polygon by the list of its integer vertex coordinates arranged along the perimeter, in the form

\\$(x\_1,y\_1), (x\_2,y\_2), \cdots , (x\_n,y\_n)\\$ with \\$n \ge 3\\$.

The polygon is completed by connecting point \\$n\\$ to point \\$1\\$.

For simplicity, it may be assumed that the polygon is simple and does not have interior angles \\$\gt \pi\\$.

The **diameter D** is defined here as the largest Euclidean distance between any two points on the circumference of the polygon.

A polygon can be deformed by **applying shear** while the area remains the same. The area \\$A\\$ of a polygon can be calculated in a known way, but it is not needed for the task at hand, because the area will not be changed by any shear.

See Wikipedia Shear Mapping.

## Challenge

**Your task is to create a function that, given a polygon, finds an arbitrary sequence of such shears so that the diameter d of the transformed polygon becomes as small as possible.**

This is related to a question in mathoverflow and this challenge.

Only those shears should be considered that are parallel to the coordinate axes and that result in a polygon with integer coordinates, i.e., with integer, but potentially negative, \\$m\\$ in the transformation matrices

\\$ \\ \begin{pmatrix} x' \\ y' \end{pmatrix} = \begin{pmatrix} 1 & m \\ 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \hspace {3mm}or \hspace {3mm} \begin{pmatrix} x' \\ y' \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ m & 1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \\$

The program shall return the value of the minimum possible squared diameter \\$d^2\\$ and the transformed vertex coordinates, such that \\$min(x'\_i) = min(y'\_i) = 0\\$.

The coordinates can be passed to the function in whatever form seems most appropriate, e.g., as a matrix or as vectors or as a reference to a data structure. It is permissible to overwrite the input coordinates in the result.

If it is possible in the selected language with little effort, then a framework program should be made available that reads and outputs the results in the following format:

\\$(x\_1,y\_1),(x\_2,y\_2),\cdots,(x\_n,y\_n)\\$

The commas between \\$x\\$ and \\$y\\$ and between \\$),(\\$ are mandatory. The calculated squared diameter shall also be output.

A framework program must not perform any pre- or post-processing other than reading and displaying the data and conversion to/from the required form for the transformation function.

The program should be able to handle polygons with at least 40 vertices.

This is Code Golf, i.e., the shortest code (in bytes) able to solve the problem wins. **However, only the length of the transformation function is used for the Code Golf score.**

The described form of output is chosen in order to be able to be used as input for a visualization program, e.g., Markus Sigg's PolygonalAreasViewer

## Example

```
Input, a polygon with n=15 and D^2=2810:
(1,1),(3,2),(6,4),(16,11),(23,16),(34,24),(38,27),(43,31),(44,32),(42,31),(39,29),(32,24),(21,16),(6,5),(2,2)
First shear x' = x - y
d^2=1105: (0,1),(1,2),(2,4),( 5,11),( 7,16),(10,24),(11,27),(12,31),(12,32),(11,31),(10,29),( 8,24),( 5,16),(1,5),(0,2)
Second shear y' = y - 2*x'
d^2=193: (0,1),(1,0),(2,0),( 5, 1),( 7, 2),(10, 4),(11, 5),(12, 7),(12, 8),(11, 9),(10, 9),( 8, 8),( 5, 6),(1,3),(0,2)
Third shear: x'' = x' - y'
d^2=82: (-1,1),(1,0),(2,0),( 4, 1),( 5, 2),( 6, 4),( 6, 5),( 5, 7),( 4, 8),( 2, 9),( 1, 9),( 0, 8),(-1, 6),(-2,3),(-2,2)
No further reduction of diameter possible; normalize position x''' = x'' + 2, y''' = y'
Expected return value: 82 (=d^2) and coordinates printed:
 (1,1),(3,0),(4,0),(6,1),(7,2),(8,4),(8,5),(7,7),(6,8),(4,9),(3,9),(2,8),(1,6),(0,3),(0,2)

```

## Test Cases

```
n = 3
A=1/2, D^2=26: (0,0),(1,0),(5,1)
->     d^2= 2: (0,0),(1,0),(1,1)

A=1/2, D^2=74: (0,0),(3,2),(7,5)
->     d^2= 2: (0,0),(1,0),(1,1)

A=50, D^2=233: (-3,2),( 3,-2),(10,10)
->    d^2=169: ( 0,4),(10, 0),( 5,12)

n = 7
A=6.5, D^2=13: (1,0),(2,0),(3,1),(3,2),(1,3),(0,3),(0,2)
->     d^2=13: (1,0),(2,0),(3,1),(3,2),(1,3),(0,3),(0,2)
               (input unchanged)

n = 8
A=7, D^2=149: (0,0),(1,1),(-1,0),(-4,-2),(-8,-5),(-9,-6),(-7,-5),(-4,-3)
->   d^2= 10: (3,1),(3,2),( 2,3),( 1, 3),( 0, 2),( 0, 1),( 1, 0),( 2, 0)

n = 15
A=51.5, D^2=18853: (0,0),(13,9),(36,25),(46,32),(43,30),(21,15),(2,2),(-14,-9),(-27,-18),(-50,-34),(-60,-41),(-67,-46),(-64,-44),(-45,-31),(-29,-20)
->      d^2=   82: (9,4),( 9,5),( 8, 7),( 7, 8),( 6, 8),( 3, 7),(1,6),(  0, 5),(  0,  4),(  1,  2),(  2,  1),(  4,  0),(  5,  0),(  7,  1),(  8,  2)

n = 17
A=75.5, D^2=1361: (1,-13),(1,-14),(2,-14),(3,-13),(6,-9),(8,-6),(13,2),(16,7),(20,14),(21,16),(21,17),(20,16),(17,12),(12, 5),(10, 2),(5,-6),(2,-11)
->      d^2= 137: (0,  7),(1,  5),(3,  2),(4,  1),(6, 0),(7, 0),( 9,1),(10,2),(11, 4),(11, 5),(10, 7),( 9, 8),( 7, 9),( 4,10),( 3,10),(1, 9),(0,  8)

n = 19
A=106.5, D^2=11240: (1,1),(2,2),(7,6),(11,9),(26,20),(37,28),(44,33),(61,45),(71,52),(84,61),(87,63),(86,62),(82,59),(67,48),(56,40),(38,27),(31,22),(14,10),(4,3)
->       d^2=  202: (2,3),(1,5),(0,8),( 0,9),( 1,11),( 2,12),( 3,12),( 6,11),( 8,10),(11, 8),(12, 7),(13, 5),(13, 4),(12, 2),(11, 1),( 9, 0),( 8, 0),( 5, 1),(3,2)

n = 20:
A=121: D^2=394: ( 0,0),( 1,0),( 2,1),( 2,2),( 1, 5),( 0, 7),(-2,10),(-3,11),(-6,13),(-8,14),(-11,15),(-12,15),(-13,14),(-13,13),(-12,10),(-11,8),(-9,5),(-8,4),(-5,2),(-3,1)
->     d^2=241: (13,4),(14,5),(15,7),(15,8),(14,10),(13,11),(11,12),(10,12),( 7,11),( 5,10),(  2, 8),(  1, 7),(  0, 5),(  0, 4),(  1, 2),(  2,1),( 4,0),( 5,0),( 8,1),(10,2)

n = 24:
A=260, D^2=937: ( 0, 0),( 2, 3),( 2, 4),(1, 5),(-1, 6),(-2, 6),(-5, 5),(-7, 4),(-10, 2),(-14,-1),(-15,-2),(-18,-6),(-20,-9),(-21,-11),(-22,-14),(-22,-15),(-21,-16),(-19,-17),(-18,-17),(-15,-16),(-13,-15),(-9,-12),(-8,-11),(-5,-7)
->     d^2=578: (13,17),(12,20),(11,21),(9,22),( 6,23),( 5,23),( 3,22),( 2,21),(  1,19),(  0,16),(  0,15),(  1,11),(  2, 8),(  3,  6),(  5,  3),(  6,  2),(  8,  1),( 11,  0),( 12,  0),( 14,  1),( 15,  2),(16,  5),(16,  6),(15,10)

A=238.5, D^2=657: (6,1),(5,1),(3,2),(2,3),(1, 5),(1, 6),(2,10),(3,13),(4,15),(6,18),(9,22),(10,23),(13,25),(14,25),(15,24),(16,22),(17,19),(17,17),(16,13),(15,10),(14,8),(12,5),(11,4),(8,2)
->       d^2=409: (5,2),(4,3),(2,6),(1,8),(0,11),(0,12),(1,15),(2,17),(3,18),(5,19),(8,20),( 9,20),(12,19),(13,18),(14,16),(15,13),(16, 9),(16, 7),(15, 4),(14, 2),(13,1),(11,0),(10,0),(7,1)

n = 27:
A=343.5, D^2=1233: ( 0,0),( 1,0),( 4,1),( 5,2),( 5,3),( 4,5),( 2,8),( 1,9),(-2,11),(-4,12),(-9,14),(-12,15),(-16,16),(-21,17),(-22,17),(-25,16),(-27,15),(-28,14),(-28,13),(-27,10),(-26,8),(-25,7),(-23,6),(-18,4),(-15,3),(-11,2),(-6,1)
->       d^2= 788: (18,0),(19,0),(23,1),(25,2),(26,3),(27,5),(28,8),(28,9),(27,11),(26,12),(23,14),( 21,15),( 18,16),( 14,17),( 13,17),(  9,16),(  6,15),(  4,14),(  3,13),(  1,10),(  0,8),(  0,7),(  1,6),(  4,4),  (6,3),  (9,2),(13,1)

n = 38:
A=360, D^2=71444: (1,1),(11,9),(21,19),(31,29),(41,39),(51,49),(61,59),(71,69),(81,79),(91,89),(101,99),(111,109),(121,119),(131,129),(141,139),(151,149),(161,159),(171,169),(181,179),(191,189),(181,181),(171,171),(161,161),(151,151),(141,141),(131,131),(121,121),(111,111),(101,101),(91,91),(81,81),(71,71),(61,61),(51,51),(41,41),(31,31),(21,21),(11,11)
->     d^2=32404: (0,0),( 2,0),( 2,10),( 2,20),( 2,30),( 2,40),( 2,50),( 2,60),( 2,70),( 2,80),( 2, 90),(  2,100),(  2,110),(  2,120),(  2,130),(  2,140),(  2,150),(  2,160),(  2,170),(  2,180),(  0,180),(  0,170),(  0,160),(  0,150),(  0,140),(  0,130),(  0,120),(  0,110),(  0,100),( 0,90),( 0,80),( 0,70),( 0,60),( 0,50),( 0,40),( 0,30),( 0,20),( 0,10)

```

# Answer
> 1 votes
# , 143 bytes

```
f=\(x,`+`=\(y)max(dist(y)^2)){d=+x;for(i in 2:3)for(j in -1:1){h=0
while(+x>+{h=h-1;m=diag(2);m[i]=j*h;y=x%*%m})x=y}
`if`(d>+x,f(x),list(d,x))}

```

Attempt This Online!

Recursively searches for the next best shear until further reduction in diameter cannot be found. Diameter calculation function is overloaded as `+` operator. Input and output of coordinates is by `n x 2` matrix, transformation to required format is done in the footer. Note that output coordinates do not exactly match the provided test cases, but the diameters match and the shapes look the same.

# Answer
> 2 votes
# PARI/GP 290 bytes

```
d(x,y)=C=0;for(i=1,#x,for(j=1,i,C=max(C,(x[i]-x[j])^2+(y[i]-y[j])^2)));C
shear(x,y)=T=D=d(x,y);until(T==D,T=D;if((t=d(x,z=y-x))<D,,if((t=d(x,z=y+x))<D));if(t<T,D=t;y=z);if((t=d(z=x-y,y))<D,,if((t=d(z=x+y,y))<D));if(t<D,D=t;x=z));for(k=1,#x,print1("("x[k]-vecmin(x)","y[k]-vecmin(y)"),"));D

```

The function \\$shear(x,y)\\$ has the coordinates, stored in 2 separate vectors, as arguments. Its return value is the squared diameter \\$d^2\\$. The transformed coordinates are written to output in the suggested format. The function \\$d(x,y)\\$ calculates the squared diameter.

Without any significant efforts regarding "golfing"; only to demonstrate the feasibility.

## Auxiliary functions to read input

```
readc()={my(s="");
s=strjoin(strsplit(input(),"),("),";");
s=strjoin(strsplit(s,"("),"v=[");
s=strjoin(strsplit(s,")"),"]");
eval(s)};
inpgon()={my(mxy=readc());x=mxy[,1];y=mxy[,2];d(x,y)};

```

## Example

```
inpgon()  \\ expects coordinate input from terminal delimited by "..."
"(1,1),(3,2),(6,4),(16,11),(23,16),(34,24),(38,27),(43,31),(44,32),(42,31),(39,29),(32,24),(21,16),(6,5),(2,2)"
2810  \\ returns D^2 of input

shear(x,y)  \\ call of function, prints result and returns d^2
(1,1),(3,0),(4,0),(6,1),(7,2),(8,4),(8,5),(7,7),(6,8),(4,9),(3,9),(2,8),(1,6),(0,3),(0,2),
82

```

---
Tags: code-golf, math, grid, geometry
---


title: Decode a variable-length quantity

text:
# Question
Title: Decode a variable-length quantity
A variable-length quantity (also referred to as **VLQ** or `uintvar`) is a way to encode up to a 28 bit integer value using only as many bytes as necessary. This was used in MIDI file format as a way to minimize the size of certain event data.

The way it works is fairly simple. As a big-endian series of bytes, the most significant bit (MSB) of each byte is a `1` to indicate that another VLQ byte follows. The remaining 7 bits of each byte make up the decoded value.

**Example (from Wikipedia):**

`[ 0x86, 0xc3, 0x17 ] => 106903`

Additional references: Wikipedia.

**Challenge:**

Given a variable-length quantity, convert it to it's integer value.

**Input:**

A list of one to four bytes or a 32-bit value type representing a valid VLQ of an integer.

**Output:**

The integer value of the VLQ input.

**Rules and scoring:**

* This is code-golf, so shortest answer in bytes for *each language* wins.
* Standard rules and default I/O rules apply.
* Loopholes forbidden (of course).
* Please provide link with a test for your code (TIO.run, etc).
* A clear explanation for your answer is highly recommended.
* Built-ins that handle this conversion are not banned, however *not* using them is a lot more interesting.

**Test cases:**

```
Input (VLQ)                   Output (int)

[                   0x00 ] => 0
[                   0x07 ] => 7
[                   0x7f ] => 127
[             0x81, 0x00 ] => 128
[             0xC0, 0x00 ] => 8192
[             0xff, 0x7f ] => 16383
[       0x81, 0x80, 0x00 ] => 16384
[       0x86, 0xc3, 0x17 ] => 106903
[       0xbd, 0x84, 0x40 ] => 1000000
[       0xff, 0xff, 0x7f ] => 2097151
[ 0xC0, 0x80, 0x80, 0x00 ] => 134217728
[ 0xFF, 0xFF, 0xFF, 0x7F ] => 268435455

```

Note: you are not required to use hex literals to represent a byte as your input or output. You may use decimal literal (`[ 129, 128, 0 ]`), integer (`0x80818000`) or any other reasonable byte/octet representation if better suited to your platform. Format is flexible as long as it represents 1-4 byte/octets.

Golf away!

# Answer
# APL (dzaima/APL), 8 bytes

```
128(⊣⊥|)

```

Try it online!

### How:

```
128(⊣⊥|) ⍝ Anonymous function
128   |  ⍝ Input modulo 128
    ⊣⊥   ⍝ Decoded from base 128

```
> 12 votes

# Answer
# Pari/GP, 24 bytes

```
a->fromdigits(a%128,128)

```

Try it online!
> 5 votes

# Answer
# , 10 bytes

```
128#.128|]

```

Try it online!

Taking inspiration from J Salle's APL answer.

* `128|]` Remainder of the input numbers divided by 128
* `128#.` Interpreted as the digits of a base 128 number
> 5 votes

# Answer
# Wolfram Language (Mathematica), 25 bytes

```
Fold[128#+#2&,#~Mod~128]&

```

Try it online!

# Wolfram Language (Mathematica), 25 bytes

```
#~Mod~128~FromDigits~128&

```

Try it online!
> 4 votes

# Answer
# Jelly, 6 bytes

```
%Ø⁷ḅØ⁷

```

Try it online!

Equivalent to alephalpha's Pari/GP answer.

Method: Given \\$n\\$, output \\$n \mod 128\\$, converted from base \\$128\\$ to decimal.
> 3 votes

# Answer
# 05AB1E, 6 bytes

```
žy%žyβ

```

Try it online!

ಠ\_ಠ Why do both Jelly and 05AB1E have 2-byte constants for `128`? Well... It's \\$2^7\\$. But surely those bytes could be used for something better, right?
> 3 votes

# Answer
# Python 3, 58 49 bytes

*-9 bytes thanks to @Chas and @ar4093*

```
lambda x:int("".join(bin(a|128)[3:]for a in x),2)

```

Try it online!

or

```
lambda x:int("".join(f"{a%128:07b}"for a in x),2)

```

Try it online!

Input via list of integers.

Python's `bin` function adds "0b" to the beginning of the string, so those have to be taken off before they can be concatenated. It also doesn't keep leading zeros, so if there aren't any (aka the last byte) those have to be added back in. And if there is a leading one (aka all but the last byte) that must be removed as well. Thanks to @Chas for figuring out that by always setting the first bit, I can just remove the first three characters and be done.

Apparently (according to @ar4093) the `format` function allows not only not having the '0b' prefix, but also removing the first bit and padding to 7 characters all at the same time.
> 3 votes

# Answer
# Stax, 8 bytes

```
å→♂á╣>nt

```

Run and debug it

Algorithm:

* Convert each byte to fixed-width 7 bit array.
* Flatten bit arrays into one.
* Convert bit array back to number.
> 3 votes

# Answer
# JavaScript (ES6), 29 bytes

*-2 bytes thanks to @Shaggy*

Takes input as an array of bytes.

```
a=>a.map(p=c=>p=p<<7|c&127)|p

```

Try it online!
> 2 votes

# Answer
# APL+WIN, 22 bytes

Prompts for a vector of integers:

```
2⊥¯32↑,0 1↓⍉(8⍴2)⊤¯4↑⎕

```

Try it online! Courtesy of Dyalog Classic

Explanation:

```
¯4↑⎕ Pad the vector to 4 integers from the right.

⍉(8⍴2)⊤ Convert to a matrix of 8 bit values.

,0 1↓ drop the MSBs and flatten to a vector.

2⊥¯32↑ pad bit vector to 32 bits starting at LSB and convert back to integer.

```
> 2 votes

# Answer
# Stax, 12 bytes

```
ü╫ôà¡k2Wù}a☺

```

Run and debug it at staxlang.xyz!

### Unpacked (14 bytes) and explanation:

```
rk128%128i^#*+
r                 Reverse 'cuz big-endian
 k                Fold from the left using block:
  128%              Modulize by 128
      128i^#        Push 128 to the power of (one plus the iteration index)
            *       Multiply
             +      Add to the total
                  Implicit print

```

Stax has builtin base conversion, but it only works on strings. It *almost* works on lists of integers, though; the problem is in Stax's handling of `0`.

A string is a list of integers. When you're using such a list as a string, any zeroes are automatically converted to 32 as a nice shorthand for spaces. Since the builtin `|b` for base conversion treats its operand as a string rather than as a raw list of integers, any case with a zero will fail.

### 10 bytes, fails on zeroes

```
Ç┘_A♥∙QZ►╣
{128%m128|b    Unpacked
{128%m         Modulize each by 128
      128|b    Convert from base 128

```

Run and debug it at staxlang.xyz!
> 2 votes

# Answer
# C (gcc), 48 bytes

Takes an integer in big-endian order as input, which is the same order as a byte array.

```
f(i,j){for(j=0;j|=i&127,i&128;j<<=7,i>>=8);i=j;}

```

Try it online!

## C (gcc), 53 bytes

If a byte array is needed:

```
f(c,j)char*c;{for(j=0;j|=*c&127,*c++&128;j<<=7);c=j;}

```

Try it online!
> 2 votes

# Answer
# MathGolf, ~~14~~ 13 bytes

```
♣%hrx♣▬^mÅε*Σ

```

Input as a list of integers.

Try it online.

I have the feeling this can be shorter.. It's a bit annoying that MathGolf has a 1-byte builtin for the constant `128`, but no base-conversion (except for binary/hexadecimal).

**Explanation:**

```
♣%            # Take modulo-128 on each value in the (implicit) input-list
  h           # Push the length of the list (without popping the list itself)
   r          # Pop and push a list in the range [0, length)
    x         # Reverse the list to (length, 0]
     ♣▬       # Take 128 to the power of each value in this list
       ^      # Zip the two lists together to create pairs
        mÅ    # Map each pair to (using the following two commands):
          ε*  #  Reduce by multiplication (so basically the product of the pair)
            Σ # After multiplying each pair, take the total sum
              # (after which the entire stack joined together is output implicitly)

```
> 2 votes

# Answer
# Japt, ~~10~~ 8 bytes

Takes input as an array of integers.

```
muIÑ ìIÑ

```

Try it or run all test cases (header in both converts from input format used in challenge)

Saved 2 bytes by taking inspiration from alephalpha's solution.

```
muIÑ ìIÑ     :Implicit input of integer array
m            :Map
 u           :  Modulo
  I          :    64
   Ñ         :    Multiply by 2
     ì       :Convert to decimal
      IÑ     :  From base 64*2

```
> 1 votes

# Answer
# PHP, 42 bytes

```
foreach($argv as$a)$r=$r<<7|$a&127;echo$r;

```

Try it online! and verify all test cases.

Input via command line args, output to `STDOUT`.
> 1 votes

# Answer
# Charcoal, 11 bytes

```
Ｉ↨﹪θ¹²⁸¦¹²⁸

```

Try it online! Link is to verbose version of code. Takes input as an array. Explanation:

```
   θ        Input array
  ﹪ ¹²⁸    Elementwise modulo 128
 ↨      ¹²⁸ Convert from base 128
Ｉ          Cast to string for implicit print

```
> 1 votes

# Answer
# Python 2, 42 bytes

```
f=lambda a:a>[]and a[-1]%128+f(a[:-1])*128

```

Try it online!
> 1 votes

# Answer
## Windows Batch, 76 bytes

```
:a
@set/ax="%1&127",y=y*128+x
@if %2. neq . @shift&goto:a
@echo %y%
```

Pass parameters prefixed with "0x" and space between (e.g. 0xC0 0x80 0x80 0x00).
> 1 votes

# Answer
# ARM Thumb-2 machine code, 16 bytes

```
00 02 c0 01 04 c9 52 06 00 eb 52 60 f9 d2 70 47

```

Assembler source with pseudo-C:

```
    .syntax unified
    .arch armv7-a
    .globl vlq
    .thumb
    .thumb_func
    // Input: r1: array of **uint32_t** containing VLQ bytes
    // Output: r0
vlq:
    // initial accumulator
    movs    r0, #0                       @ acc = 0;
.Lloop:                                  @ do {
    // Shift accumulator for next value
    lsls    r0, r0, #7                   @    acc = acc << 7;
    // Load next vlq byte, advance ptr
    ldmia   r1!, {r2}                    @    tmp = *ptr++;
    // Shift left so the continuation
    // bit is in the carry
    lsls    r2, r2, #32 - 7              @    carry = tmp & 0x80;
                                         @    tmp = tmp << (32 - 7);
    // Insert it into the accumulator,
    // not affecting the flags (wide)
    add.w   r0, r0, r2, lsr #32 - 7      @    acc = acc + (tmp >> (32 - 7));
    // If there is no carry, loop again
    bcs     .Lloop                       @ } while (carry);
    // Return
    bx      lr                           @ return acc;

```

This function can be called from C with a dummy parameter to place `data` in `r1`.

```
uint32_t vlq(uint32_t dummy, const uint32_t *data);
// Note: uint32_t, not uint8_t
const uint32_t vlqs[] = { 0x86, 0xC3, 0x17 };
printf("%u\n", vlq(314159 /* dummy */, vlqs));

```
> 1 votes

# Answer
# Ruby, 40 bytes

```
->a{a.map{("%08b"%_1)[1..]}.join.to_i 2}

```

Attempt This Online!
> 1 votes

# Answer
# J-uby, 40 bytes

Port of my Ruby answer, just for fun.

```
:*&(:%&"%08b"|~:[]&(1..))|:join|~:to_i&2

```

Attempt This Online!

## Explanation

```
:* & (           # Map with…
  :% & "%08b" |  #   Format (%) as binary padded to 8 digits, then
  ~:[] & (1..)   #   take range of characters 1..end
) |              # then
:join |          # join, then
~:to_i & 2       # convert to int as base 2

```
> 1 votes

# Answer
# Nibbles, 5 bytes (10 nibbles)

```
`@;128.@%

```

```
`@;128.@%$@  # = program with implicit arguments added
`@           # convert from base
   128       # 128
  ;          # (and save that value)
       @     # the input values
      .      # each
        %$   # modulo
          @  # the saved value of 128

```
> 0 votes

---
Tags: code-golf, conversion, bitwise
---


# Question
Title: Convert JSON object of directories to list of paths
## Task

The input consists of a JSON object, where every value is an object (eventually empty), representing a directory structure. The output must be a list of the corresponding root-to-leaf paths.

Inspired by this comment on StackOverflow.

### Input specifications

* You can assume that that the input always contains a JSON object.
* The input can be a empty JSON object (`{}`); in this case the output must be a empty list.
* You can assume that the names/keys contain only printable ASCII characters, and they do not contain `\0`, `\`, `/`, `"`, `'`, nor ```.
* You can assume each JSON object does not contain duplicate names/keys.

### Input format

The input can be:

* a string;
* a dictionary or an associative array in a language of your choice;
* a list or array of tuples, where each tuples contains the name/key and the value (which is itself a list of tuples).

### Output specifications

* There is no need to escape any character.
* You can use as directory separator either `/` or `\`, but you cannot have a mixed use of both (e.g. `a/b/c` and `a\b\c` are both valid, but `a/b\c` and `a\b/c` are not).
* Each path *can* have a leading and/or trailing directory separator (e.g. `a/b`, `/a/b`, `a/b/`, and `/a/b/` are equally valid).
* If you output a newline-separated list, the output can have a trailing newline.
* ~~The paths must be in the same order of the input.~~

## Test cases

Input 1:

```
{
    "animal": {
        "cat": {"Persian": {}, "British_Shorthair": {}},
        "dog": {"Pug": {}, "Pitbull": {}}
    },
    "vehicle": {
        "car": {"Mercedes": {}, "BMW": {}}
    }
}

```

Output 1:

```
animal/cat/Persian
animal/cat/British_Shorthair
animal/dog/Pug
animal/dog/Pitbull
vehicle/car/Mercedes
vehicle/car/BMW

```

Input 2

```
{
    "bin": {
        "ls": {}
    },
    "home": {},
    "usr": {
        "bin": {
            "ls": {}
        },
        "include": {
            "sys": {}
        },
        "share": {}
    }
}

```

Output 2:

```
/bin/ls
/home
/usr/bin/ls
/usr/include/sys
/usr/share

```

Sandbox: https://codegolf.meta.stackexchange.com/a/24594/73593

# Answer
# jq, ~~42~~ 40 bytes (+11 penalty for "-r --stream" options)

```
select(.[1]=={})[0]|join("/")

```

Try it online!

The `--stream` option converts JSON to an alternate format where each leaf node is an element in a list. Those entries are also lists, with two fields, the first of which is a list of the keys representing the path. The second entry (for out test cases) is an empty dictionary.

So the code selects every list entry where the second entry is a an empty dictionary, them assembles the list of keys in the first entry into the output we want.

```
select(.[1]=={})[0]            - pick "leaf" node entries only (1st field only)
                   |join("/")  - join the list of string w/ a "/" separator

```
> 4 votes

# Answer
# JavaScript (V8), 55 bytes

*Thanks to @pxeger for suggesting to use `for(k in o)`*

Expects an object. Prints the results with a leading `/`.

```
f=(o,p,q)=>{for(k in o)f(o[q=k],[p]+'/'+k);q||print(p)}

```

Try it online!

---

# JavaScript (V8), 63 bytes

Expects an object. Prints the results with a leading `/`.

```
f=(o,p)=>Object.keys(o).map(k=>f(o[k],[p]+'/'+k))+''||~print(p)

```

Try it online!
> 3 votes

# Answer
# Perl 5, 67 bytes

```
map/}/?/{/&&say($s)..$s=~s|[^/]+/$||:($s.=s/"//gr."/"),/{?}|".+?"/g

```

Try it online!
> 3 votes

# Answer
# Python, 52 bytes

```
def f(d,s=""):[f(d[x],s+"/"+x)for x in d]or print(s)
```

Attempt This Online!

Takes input as a dictionary, and outputs to STDOUT.
> 2 votes

# Answer
# Jelly, 14 bytes

```
;”/;ⱮßW⁹?}ʋ/€Ẏ

```

A monadic Link that accepts a list of lists where each is a key-value pair where the key is a list of characters and the value is a, possibly empty, list of the same type\* and yields a list of lists of characters - the paths.

* i.e. uses the option *a list or array of tuples, where each tuples contains the name/key and the value (which is itself a list of tuples)*.

**Try it online!**

### How?

```
;”/;ⱮßW⁹?}ʋ/€Ẏ - (recursive) Link: list, J
            €  - for each key-value pair in J:
           /   -   reduce by:
          ʋ    -     last four links as a dyad - f(Key, Value)
 ”/            -       '/' character
;              -       (Key) concatenate ('/')
         }     -     use right argument, Value with:
        ?      -       if...
       ⁹       -       ...condition: chain's right argument, Value
     ß         -       ...then: call this recursive Link with that (non-empty) Value
      W        -       ...else: wrap that (empty) Value in a list -> [[]]
    Ɱ          -     map across the recursive call result (or the [[]]) with:
   ;           -       concatenate
             Ẏ - tighten

```
> 2 votes

# Answer
# Perl 5 \+ `-M5.10.0 -n0175`, 36 bytes

```
pop@;;push@;,/\w+/g;$,="/";/{/&&say@
```

Try it online!

## Explanation

A different approach to the other Perl answer. This uses the `-0175` command line flag to split the input on `}`. For each closing curly brace, `@;` is `pop`ped removing any previous path keys that aren't needed. Next all the keys (`/\w+/g` \- this might be too lenient?) are `push`ed onto `@;`. Finally `$,` (which is printed between records when a list - `@...` \- is `print`ed) is set to `"/"` and if `{` exists in the input, `say` is used to output `@;` (with `$,` printed between each index).
> 2 votes

# Answer
# Retina 0.8.2, 96 bytes

```
+1`"([^"]+)":{("[^"]+":{(({)|(?<-4>})|[^{}])*(?(4)^)},)*"(?!\1/)
$&$1/
M!`"[^"]+":{}
%`^.|....$

```

Try it online! Link includes test cases. Explanation:

```
+1`"([^"]+)":{("[^"]+":{(({)|(?<-4>})|[^{}])*(?(4)^)},)*"(?!\1/)
$&$1/

```

Replace each key in turn with its path.

```
M!`"[^"]+":{}

```

List the entries whose values are empty objects.

```
%`^.|....$

```

Keep just the keys.
> 1 votes

# Answer
# , ~~79~~ 73 bytes

```
f=function(L)"if"(length(L),unlist(Map(paste0,names(L),"/",Map(f,L))),"")

```

Try it online!

Takes input as a named R `list`, i.e., `list(name=value)`, and returns a `character` (string) vector of directories.

-3 bytes thanks to pajonk.
> 1 votes

# Answer
# PowerShell Core, ~~103~~ 88 bytes

```
function f($o,$p){($x=$o.keys|%{f $o.$_ $p/$_})
if(!$x){$p}}f($args|ConvertFrom-Json -a)

```

Try it online!

Takes a string as a parameter
Returns a list of string with a leading `/`

Thanks mazzy for shaving 15 bytes off!
> 1 votes

# Answer
# Kotlin 1.6.21, 118 bytes

```
{fun f(m:Map<*,*>,s:(Any?)->Any){for((k,v)in m)if((v as Map<*,*>).size==0)s(k)else f(v){s("$k/$it")}};f(it,::println)}

```

Try it online!

An anonymous function of type `(Map<*, *>) -> Unit` that takes in a recursive map of `String` to `Map<String, ...>` and prints the answer without leading or trailing slashes.

**Ungolfed code:**

```
{
    // Define function f that iterates a map recursively and
    // outputs its keys' paths to a sink function
    fun f(m: Map<*, *>, s: (Any?) -> Any) {
        for ((k, v) in m)
            // Note: .size==0 is 2 bytes shorter than .isEmpty()
            if ((v as Map<*,*>).size == 0)
                // For an empty map, call the sink with the key
                s(k)
            else
                // Call f again on the inner map with a wrapped sink that
                // that appends the current key + "/" to the input
                f(v) { s("$k/$it") }
    }

    // Run f for the input map, using ::println as the sink
    f(it, ::println)
}

```
> 0 votes

# Answer
# Pip 1.1.0-alpha `-xp`, 23 bytes

```
@_.{a@1?'/.(\fa@1)x}MFa

```

Takes a list of tuples (i.e. two-element lists) as a command-line argument. Outputs a list of strings.

Pip 1.1 (required for both `\f` and `MF`) is not on Attempt This Online at the time of writing, but you can try it on Replit. The easiest way is to exit out of the Pip REPL with `;quit` and then:

```
> ./pip.py -xpe "@_.{a@1?'/.(\fa@1)x}MFa" '[["bin"; [["ls"; []]]]; ["home"; []]; ["usr"; [["bin"; [["ls"; []]]]; ["include"; [["sys"; []]]]; ["share"; []]]]]'
["bin/ls";"home";"usr/bin/ls";"usr/include/sys";"usr/share"]

```

### Explanation

A recursive full program:

```
@_.{a@1?'/.(\fa@1)x}MFa
                      a  Program argument (a list of pairs)
                    MF   Map this function to each and flatten the results:
@_                         The first element of the pair
  .{               }       Concatenated (itemwise if necessary) to:
    a@1?                   Is the second element of the pair (a list) nonempty?
        '/.                If so, concatenate / (itemwise) to
           (\f   )         a recursive call of the main function
              a@1          with the second element of the pair as the argument
                  x        If it is empty, empty string

```
> 0 votes

# Answer
# Bash (sed + ShellShoccar-jpn/Parsrs parsrj.sh), ~~31~~ 29 bytes

Assumes parsrj.sh is on a directory specified by PATH environment variable. Tested with parsrj.sh `Version : 2020-05-06 22:42:19 JST`.

```
parsrj.sh -rt -kd/|sed s,/$,,

```

## Example runs on my Termux

## Explained

```
parsrj.sh -rt -kd/|
# default output for {"foo":{"bar":{}},"baz":{}}:
#   $.foo.bar.
#   $.baz.
# -rt to replace $ with ""
# -kd/ to replace . with /
# thus output is:
#   /foo/bar/
#   /baz/
sed s,/$,,
# trailing slash is removed

```
> 0 votes

---
Tags: code-golf, json
---


# Question
Title: Count the number of fields in each csv record
Imagine a text file where each csv record may have different numbers of fields. The task is to write code to output how many fields there are in each record of the file. You can assume there is no header line in the file and can read in from a file or standard input, as you choose.

You can assume a version of rfc4180 for the csv rules which I will explain below for the definition of each line of the file. Here is a lightly edited version of the relevant part of the spec:

**Definition of the CSV Format**

1. Each record is located on a separate line, delimited by a line break (CRLF). For example:

```
aaa,bbb,ccc CRLF

```

`zzz,yyy,xxx CRLF`

2. The last record in the file may or may not have an ending line break. For example:

```
aaa,bbb,ccc CRLF

```

`zzz,yyy,xxx`

(Rule 3. does not apply in this challenge)

4. Within each record, there may be one or more fields, separated by commas. Spaces are considered part of a field and should not be ignored.
5. Each field may or may not be enclosed in double quotes. If fields are not enclosed with double quotes, then double quotes may not appear inside the fields. For example:

```
"aaa","bbb","ccc" CRLF

```

`zzz,yyy,xxx`

6. Fields containing line breaks (CRLF), double quotes, and commas should be enclosed in double-quotes. For example:

```
"aaa","b CRLF

```

`bb","ccc" CRLF
zzz,yyy,xxx`

7. If double-quotes are used to enclose fields, then a double-quote appearing inside a field must be escaped by preceding it with another double quote. For example:

```
"aaa","b""bb","ccc"
```

## Example

Input:

```
,"Hello, World!"
"aaa","b""bb","ccc"
zzz,yyy,
"aaa","b
bb","ccc","fish",""

```

Should give the output:

```
2, 3, 3, 5

```

Your can give the output values in any way you find most convenient.

## Libraries

You can use any library you like.

---

Awesome answers so far but we are missing a command line/bash answer which would be particularly cool.

# Answer
> 5 votes
# Stax, ~~19~~ 12 bytes

```
èJ§3‼}vAà○L>

```

Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

```
_'"/    split *all* of standard input by double quote characters
2::     keep only the even numbered elements
|j      split on newlines (implicitly concatenates array of "strings")
m       for each line, execute the rest of the program and output
  ',#^  count the number of commas occurring as substrings, and increment

```

Run this one

# Answer
> 4 votes
# , 40 bytes

```
(x=count.fields(stdin(),","))[!is.na(x)]

```

Try it online!

Per the documentation of `count.fields`, fields with line breaks get a field count of NA for the initial line, so we filter them out.

# Answer
> 3 votes
# JavaScript (ES2018), ~~42~~ 59 bytes

```
s=>s.replace(/".+?"/sg).split`\n`.map(c=>c.split`,`.length)

```

```
f=
s=>s.replace(/".+?"/sg).split`\n`.map(c=>c.split`,`.length)

console.log(f(
`,"Hello, World!"
"aaa","b""bb","ccc"
zzz,yyy,
"aaa","b
bb","ccc","fish",""`))
```

# Answer
> 3 votes
# Jelly, 12 bytes

```
ṣ”"m2FỴ=”,§‘

```

A port of recursive's Stax answer \- go give credit!

**Try it online!**

### How?

```
ṣ”"m2FỴ=”,§‘ - Link: list of characters, V
 ”"          - a double quote character = '"'
ṣ            - split (V) at ('"')
   m2        - modulo slice with two (1st, 3rd, 5th, ... elements of that)
     F       - flatten list of lists to a list
      Ỵ      - split at newlines
        ”,   - comma character = ','
       =     - equal? (vectorises)
          §  - sum each
           ‘ - increment (vectorises)
             - (as a full program implicit print)

```

---

Maybe you prefer `ṣ”"m2ẎỴċ€”,‘` \-  is tighten and `ċ€` counts the commas in each.

# Answer
> 2 votes
# Perl 5.10.0, ~~55~~ 53 bytes

```
$_=shift;s/"(""|[^"])*"//g;s/^.*$/1+$&=~y:,::/gem;say

```

Try it online!

Explanation:

```
$_=shift;          # first command-line arg
s/"(""|[^"])*"//g; # remove quoted fields
s/^.*$/            # replace each line
  1+$&=~y:,::      # by the number of commas plus 1
/gem;
say                # print

```

# Answer
> 2 votes
# Python, 63 bytes

```
import csv
def f(s):return map(len,csv.reader(s.split("\n"))

```

Returns the output in an iterable `map` object.

# Answer
> 2 votes
# Wolfram Language (Mathematica), 30 bytes

```
Length/@ImportString[#,"CSV"]&

```

Try it online!

# Answer
> 2 votes
# Java 10, 101 bytes

```
s->{for(var p:s.replaceAll("\"[^\"]*\"","x").split("\n"))System.out.println(p.split(",",-1).length);}

```

Try it online.

**Explanation:**

```
s->{                                    // Method with String parameter and no return-type
  for(var p:s.replaceAll("\"[^\"]*\"","x")
                                        //  Replace all words within quotes with an "x"
             .split("\n"))              //  Then split by new-line and loop over them:
    System.out.println(p.split(",",-1)  //   Split the item by comma's
                        .length);}      //   And print the length of this array

```

# Answer
> 1 votes
# Jelly, 17 bytes

```
=”"ÄḂżṣ⁷Ż¤ṣ€0,”,Ẉ

```

Try it online!

-1 thanks to Jonathan Allan. *duh duh duh...*

# Answer
> 0 votes
# POSIX shell (ShellShoccar-jpn/Parsrs \+ usp-engineers-community/Open-usp-tukubai), 19 bytes

Dependencies are

```
parsrc.sh|count 1 1

```

## Output format

For each line, the following line is output:

```
<row number> <number of columns>

```

## How it works

`parsrc.sh` is a parser for CSV who converts such text into list of cells and their value. Open-usp-tukubai's `count` takes a range of field number from parameters and space-separated values to count in such range to summarize. Here are some comments:

```
# raw CSV
parsrc.sh |
# 1: row number 2: column number 3: value where LFs are represented as "\n" while real backslashes as "\\"
count 1 1
# 1: row number 2: number of columns in the row

```

## Example run on Termux

Because Termux is not a completely POSIX-compatible so `command -p getconf PATH` fails, I am dropping the boilerplate to set PATH environment variable so the shell calls completely POSIX-compatible utilities first. Also because I am lazy to prepare Python 2, I am doing with COMMANDS.SH/count.

---
Tags: code-golf
---