title: Variable length Fibonacci word

text:
# Question
Title: Variable length Fibonacci word
# Challenge

For any two non-empty strings A and B, we define the following sequence :

```
F(0) = A
F(1) = B
F(n) = F(n-1) + F(n-2)

```

Where `+` denotates the standard string concatenation.

The sequence for strings "A" and "B" starts with the following terms: A, B, BA, BAB, BABBA, ...

Create a function or program that, when given two strings `A` and `B`, and a positive integer `I` returns the `I`-th character of `F(∞)`.

You may choose to use 0-indexing or 1-indexing for `I`, just specify it in your answer.

You may assume the strings contain only uppercase (or lowercase) letters.

This is a variation of Project Euler's Problem 230, where the two strings were strings of digits of equal length, which trivialize the problem.

# Input/Output

You may choose any format for the input. The output should only contain the desired character, with trailing spaces/newlines allowed.

# Test Cases

```
ABC, DEF, 1234567890 → A
ACBB, DEFGH, 45865 → B
A, B, 3 → B
ABC, DEF, 10 → E

```

This is , so the lowest byte count for each language wins!

# Answer
# Haskell, 15 bytes

```
a#b=b++b#(a++b)

```

Try it online!

Takes strings `a` and `b` as input, returns the whole infinite Fibonacci word, as is usually allowed in challenges.

## How?

Not much to say. This answer relies on the identity $$ F(a,b)=b+F(b,a+b), $$ where \\$F(a,b)\\$ is the infinite Fibonacci word with starting words \\$a\\$ and \\$b\\$.
> 11 votes

# Answer
# Jelly, ~~6~~ 5 bytes

```
⁹;¡⁵ị

```

Try it online!

Uses 1 indexing

-1 byte thanks to Jonathan Allan, noticing that we could avoid  becoming the right argument to  by forcing  into a nilad-dyad pair with !

Dyadic `¡` is essentially Jelly's generalised Fibonacci operator

## How it works

```
⁹;¡⁵ị - Main link. Takes A on the left, B on the right and I as the third argument
⁹     - Set the return value to B
  ¡   - I times do the following, swapping the updated arguments each time:
 ;    -   Concatenate the arguments
   ⁵ị - Yield the i'th character of the result

```

When  is run with 2 arguments, it does the following (calling the initial left argument `B` and the initial right argument `A`, as  essentially "swaps" the order of the arguments. We'll do 3 iterations):

* Iteration 1: `;` concatenates `B` and `A`, yielding `BA`. We then move `B` to the right and take `BA` as our left argument for the next iteration
* Iteration 2: `;` concatenates `BA` and `B`, yielding `BAB`. Our arguments become `BAB` on the left and `BA` on the right
* Iteration 3: `;` concatenates `BAB` and `BA`, yielding `BABBA`. This is the last iteration, so we return `BABBA`
> 10 votes

# Answer
# Python 3, 36 bytes

```
f=lambda a,b,i:b[i:i+1]or f(b,b+a,i)

```

Try it online!

-8 bytes thanks to dingledooper

~~Not a particularly creative approach. In fact, basically this is just what l4m2 did but Python will error when accessing out of bounds instead of returning `undefined`.~~ Using `b[i:i+1]` returns `b[i]` (for strings) if it's in range, but doesn't error and instead gives `""` if it's out of range. Thanks to dingledooper for that.

Go upvote this answer too. This isn't really intentionally a port because I thought of the same idea but it's an identical approach.
> 9 votes

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

```
n=>g=a=>b=>b[n]||g(b)(b+a)

```

Try it online!

Thank tsh for -1 Byte
> 7 votes

# Answer
# Husk, 5 bytes

A rip-off of Delfad0r's beautiful Haskell answer. Go upvote that!

```
S+S₀+

```

Try it online!

Returns the entire infinite string/list.

`S+S₀+ a b` is `(S+) ((S₀) (+a)) b`, which expands to `(+b) ((S₀ (+a)) b)` (where  is a self-reference to the main function) and then to `(+b) (₀ b (+a b))`, which is basically `b + F(b, a + b)`.

### Safer answer, 8 bytes

```
!₁
S+S₁+

```

Try it online!

This one gets the Ith character, at the cost of 3 bytes.
> 5 votes

# Answer
# 05AB1E, ~~6~~ 5 bytes

-1 byte by assuming the input words consist only of letters (`è` implicitly swaps arguments if the first one doesn't look like a number)

Takes inputs `[A, B]` and `n`.

```
λèì}è

```

Try it online!

**Commented**:

```
λè }    # get the nth element of the sequence generated by:
  ì     #   prepending the current string to the last string
        # that starts with [A, B]
     è  # index with n into the nth element of the sequence

```
> 3 votes

# Answer
# , ~~96~~ ~~92~~ 84 bytes

```
function(A,B,I,`!`=function(k)"if"(k,"if"(k>1,paste0(!k-1,!k-2),B),A))substr(!I,I,I)

```

Try it online!

Takes `I` 1-indexed.

*-8 bytes thanks to @Dominic*
> 3 votes

# Answer
# Charcoal, 42 bytes

```
≔⁻ＮＬζθ≔⁰εＷ¬‹θ⁰«Ｆ¬＆ε⊗ε≧⁻⁺Ｌζ∧﹪ε²Ｌηθ≦⊕ε»§⁺ηζθ

```

Try it online! Link is to verbose version of code. Takes the index as the first input. Explanation: I wanted to avoid building up a humunguous string but the code is still slow because I don't know a good way of calculating Fibbinary numbers.

```
≔⁻ＮＬζθ

```

Subtract the length of `B` from `n`.

```
≔⁰ε

```

Start enumerating Fibbinary numbers.

```
Ｗ¬‹θ⁰«

```

Repeat until `n` is negative.

```
Ｆ¬＆ε⊗ε

```

Is the current index a Fibbinary number?

```
≧⁻⁺Ｌζ∧﹪ε²Ｌηθ

```

If so then subtract the length of either `B` or `BA` from `n` depending on whether the current index is even or odd.

```
≦⊕ε

```

Increment the index.

```
»§⁺ηζθ

```

Output the `n`th character of `AB` (since `n` is negative here, Charcoal counts back from the end).
> 2 votes

# Answer
# , ~~76~~ 66 bytes

*Edit: -10 bytes thanks to Giuseppe*

```
f=function(b,a,n)`if`(nchar(b)>n,substr(b,n,n),f(paste0(b,a),b,n))

```

Try it online!

Recursive function: input the starting strings `b` and `a` (note reversed order), and the 1-based index to output.

Could be a bit shorter (53 bytes) if inputs are vectors of characters instead of strings.

---

# , 48 bytes

```
function(a,b)repeat{c=b;cat(b<-paste0(b,a));a=c}

```

Try it online!

Prints the infinite string.
> 2 votes

# Answer
# PowerShell, 63 bytes

```
param($x,$y,$n)$a=$x,$y
1..$n|%{$a+=$a[$_]+$a[$_-1]}
$a[-1][$n]

```

Try it online!

-11 bytes thanks to julian
> 1 votes

# Answer
# Java (JDK), 70 bytes

```
(a,b,n)->{for(var t=a;b.length()<=n;a=b,b=t)t=b+a;return b.charAt(n);}

```

Try it online!
> 1 votes

---
Tags: code-golf, string, sequence, fibonacci
---


title: Equalize the array

text:
# Question
Title: Equalize the array
# Challenge

You are given an array \\$a\\$ of integers. With a ***move*** you can **increase or decrease** an element of the array **by 1**. Your task is to ***equalize*** the array, that is make all the elements of the array equal by performing some *moves*. But that's not enough! You also want to make **as few *moves* as possible**.

## Input

* A non-empty **array** \\$a\\$ of integers
* Optionally, the **length** of \\$a\\$.

## Output

* The **minimum number of *moves*** needed to *equalize* the array \\$a\\$.

# Rules

* **Standard rules** for valid submissions, I/O, loopholes apply.
* This is , so **shortest solution** (in bytes) wins. As usual, don't let ridiculously short solutions in golfy languages discourage you from posting a longer answer in your language of choice.
* This is not a rule, but your answer will be better received if it includes a link to test the solution and an explanation of how it works.

# Examples

```
Input                       --> Output

[10]                        --> 0
[-1, 0, 1]                  --> 2
[4, 7]                      --> 3
[6, 2, 3, 8]                --> 9
[5, 8, 12, 3, 2, 8, 4, 5]   --> 19
[1,10,100]                  --> 99

```

# Answer
# Wolfram Language (Mathematica), 19 bytes

```
Tr@Abs[#-Median@#]&

```

Try it online!

For 1D integer array, `Tr` works the same way as `Total`.

## How?

Simple application of triangle inequality.

...

I originally intended to write the proof here, but then decide to look up https://math.stackexchange.com instead and found The Median Minimizes the Sum of Absolute Deviations (The \\$ {L}\_{1} \\$ Norm).

By knowing the name of the operator, this is an alternative 19-byte solution:

```
Norm[#-Median@#,1]&

```
> 10 votes

# Answer
# JavaScript (Node.js), ~~50~~ 48 bytes

Saved 2 bytes thanks to Arnauld

```
a=>a.sort((x,y)=>x-y,r=0).map(n=>r+=a.pop()-n)|r

```

Try it online!

Sort the array ascending then sum:

```
  a[last]   -a[0] // moves to equalise this pair
+ a[last-1] -a[1] // + moves to equalise this pair
+ ...etc

```
> 10 votes

# Answer
# Perl 6, ~~29~~ 28 bytes

*-1 byte thanks to nwellnhof*

```
{sum (.sort[*/2]X-$_)>>.abs}

```

Try it online!

### Explanation

```
{                          }  # Anonymous code block
      .sort[*/2]              # Get the median of the input array
                X-$_          # Subtract all elements from the median
     (              )>>.abs   # Get the absolute of each value
 sum                          # Sum the values

```
> 7 votes

# Answer
# 05AB1E, 4 bytes

```
ÅmαO

```

Try it online!

**Explanation**

```
Åm     # push median of input
  α    # absolute difference with each in input
   O   # sum

```
> 6 votes

# Answer
# Japt `-g`, ~~7~~ 6 bytes

```
£xaXÃÍ

```

Try it

```
£xaXÃÍ     :Implicit input of array U
£          :Map each X
 x         :  Reduce by U by addition after applying
  aX       :    Absolute difference with X
    Ã      :End map
     Í     :Sort
           :Implicit output of first element

```
> 6 votes

# Answer
# JavaScript (ES6), ~~60~~ ~~56~~ 55 bytes

*Saved 1 byte thanks to @Shaggy*

```
a=>a.map(r=k=>r=a.map(n=>m+=n>k?n-k:k-n,m=0)|m>r?r:m)|r

```

Try it online!

### How?

Unless there's some trick that I'm missing, computing the median in JS turns out to be longer. Probably around **65 bytes** because of the required callback for `sort()` to circumvent the default lexicographical sort and the rather lengthy `Math.abs()`:

```
a=>a.sort((a,b)=>b-a).map(n=>s+=Math.abs(n-a[a.length>>1]),s=0)|s

```

Instead of that, we try all values in the original array as the *equalizing* value.
> 5 votes

# Answer
# Haskell, 34 bytes

```
f l=minimum[sum$abs.(m-)<$>l|m<-l]

```

Try it online!

Finds the total distance of all elements to the median, testing each element in the list as the potential median and taking the smallest result.
> 5 votes

# Answer
# Jelly, 4 bytes

```
ạÆṁS

```

Try it online!

### How it works

```
ạÆṁS – Full program. Takes an array A of integers as input from argument 1.
 Æṁ  – Median. For odd-length A, middle element of S. For even-length A, the
       arithmetic mean of the two middle elements of S. Where S = A sorted.
ạ    – Absolute difference of each element with the median.
   S – Sum.

```
> 4 votes

# Answer
# Python 2, 46 bytes

```
lambda l,n:sum(l[-~n/2:l.sort()])-sum(l[:n/2])

```

Try it online!

Takes the list length `n` as an argument. Computes the top-half sum minus the bottom-half sum by slicing the sorted list into the first `n/2` and last `n/2` elements.

The expression `l[-~n/2:l.sort()]` is equivalent to computing `l.sort()`, which modifies the list in place, then doing `l[-~n/2:None]`, where the list slicing ignores upper bound of `None` that `l.sort()` produced. It might seem like the list was sorted too late to be sliced right, but Python seems to evaluate the slice arguments before "locking in" the list to be sliced.

---

**Python 2, 47 bytes**

```
lambda l,n:sum(abs(x-sorted(l)[n/2])for x in l)

```

Try it online!

The boring method of summing the distance of each value from the median. Takes the length `n` as an argument.

---

**Python, 51 bytes**

```
f=lambda l:l>l[l.sort():1]and l[-1]-l[0]+f(l[1:-1])

```

Try it online!

Sorts the list in place, then repeatedly adds the last (highest remaining) entry minus the first (lowest remaining) entry, and recurses on the list without these elements until only 0 or 1 remain. Usings `pop`'s gets the same length: `l.pop()-l.pop(0)+f(l)`.

The `l.sort()` is stuck in a place where the `None` it returns has no effect. The slice `l[None:1]` is the same as `l[:1]` because `None`s in slices are ignored.

---

**Python, 54 bytes**

```
lambda l:sum(l.pop()-l.pop(0)for _ in l[1:l.sort():2])

```

Try it online!

A cute list comprehension that ignores the argument iterated over and modifies the list in place by repeatedly popping the first and last elements. We ensure that the list comprehension is done `len(l)//2` times by iterating over every other element of `l` skipping the first, done with `l[1::2]`. The `l.sort()` producing `None` can be stuck in the unused slice end argument.
> 4 votes

# Answer
# TI-Basic, ~~18~~ 6 bytes

```
sum(abs(Ans-median(Ans
```

-12 bytes from Misha Lavrov (I haven't used TI-Basic in a while and I forgot it's lists can do that)

TI-Basic is a tokenized language. All tokens used in this answer are one byte.

Takes input as `{1,2,3,4}:prgmNAME`

Basically the same idea as most other answers: subtract through by the median, then take the sum.

Explanation:

```
sum(abs(Ans-median(Ans
sum(                    # 1 byte, Add up:
    abs(                # 1 byte, the absolute values of
        Ans-median(Ans  # 4 bytes, the differences between each element and the list's median

```
> 4 votes

# Answer
# APL(Dyalog), 12 bytes

```
{⌊/+/|⍵∘.-⍵}

```

Brute forces by testing each number as the equalizer. Not sure if tacit is shorter, but I can't figure it out.

TIO
> 4 votes

# Answer
# Röda, 33 bytes

```
{|a|a|abs _-[sort(a)][#a//2]|sum}

```

Try it online!

Explanation:

```
{|a| /* Anonymous function with parameter a */
  a|         /* Push items in a to the stream */
             /* For each _ in the stream: */
  abs        /*   Abstract value of */\
  _-         /*   the value from stream minus */\
  [sort(a)][ /*     the value in the sorted version of a at index */
    #a//2    /*       length of a / 2 (the median) */
  ]|
  sum        /* Sum of all values in the stream */
}

```
> 3 votes

# Answer
# C (gcc), ~~100~~ 93 bytes

```
e(q,u,a,l,i,z)int*q;{i=1<<31-1;for(a=u;a--;i=z<i?z:i)for(l=z=0;l<u;)z+=abs(q[l++]-q[a]);q=i;}

```

Brute-force solution, tries to equalize with each element. Try it online here.

Thanks to ceilingcat for golfing 7 bytes.

Ungolfed:

```
e(q, u, a, l, i, z) int *q; { // function taking an array of int and its length; returns an int (extra parameters are variables and don't have to be passed when calling e())
    i = 1 << 31 - 1; // construt the maximum value of a signed 4-byte integer
    for(a = u; a--; i = z < i ? z : i) // loop through the array, testing each element as the equalizer; if the number of moves is smaller than the current minimum, set it as the new minimum
        for(l = z = 0; l < u; ) // loop through the array ...
            z += abs(q[l++] - q[a]); // ... and sum the number of moves it takes to equalize each element
    q = i; // return the minimum number of moves
}

```
> 3 votes

# Answer
# , 29 bytes

```
sum(abs(median(a<-scan())-a))

```

Try it online!
> 2 votes

# Answer
# PHP, 69 bytes

```
function($a,$c){for(sort($a);$c-->$d;)$s+=$a[$c]-$a[+$d++];return$s;}

```

anonymous function. Try it online.
> 2 votes

# Answer
# Java 8, 116 bytes

With `java.util.List<Integer>` as parameter, which has a short sort-builtin, but is longer to retrieve a value at a given index:

```
L->{L.sort(null);int r=0,l=L.size(),k=l;for(;k-->0;)r+=Math.abs(L.get(k)-(L.get(l/2+~l%2)+L.get(l/2)>>1));return r;}

```

Try it online.

With `int[]` (integer-array) as parameter, which has a long sort-builtin, but is shorter to retrieve a value at a given index:

```
a->{java.util.Arrays.sort(a);int r=0,l=a.length,k=l;for(;k-->0;)r+=Math.abs(a[k]-(a[l/2+~l%2]+a[l/2]>>1));return r;}

```

Try it online.

**Code explanation (of the array answer):**

```
a->{                               // Method with integer-array as parameter and integer return-type
  java.util.Arrays.sort(a);        //  Sort the input-array
  int r=0,                         //  Result-sum, starting at 0
      l=a.length,                  //  The length of the input-array
  k=l;for(;k-->0;)                 //  Loop `k` in the range (length, 0]:
    r+=                            //   Increase the result-sum by:
       Math.abs(a[k]-              //    The absolute difference of the `k`'th value of the array,
        (a[l/2+~l%2]+a[l/2]>>1));  //    and the median of the array
  return r;}                       //  And then return this result-sum

```

**General explanation:**

1. Sorts the input-list
2. Calculate the \\$median\\$
3. Calculate the absolute difference of each value with this \\$median\\$
4. Sum those

The median of the array \\$a\\$ is calculated by:
1) Taking the sorted values at the (0-based) indices \\$i\\$ and \\$j\\$, which are calculated like this (using the `l/2+~l%2` instead of `l/2-(l+1)%2` trick to save bytes):
\\$j=\left\lfloor\frac{1/2}l\right\rfloor\\$
\\$i=\left\lfloor\frac{1/2}l\right\rfloor - ((l+1) \bmod 2)\\$
Note that \\$i=j\\$ for odd-sized arrays.

2) And then adding these together, and integer-dividing them by 2 (using the `i+j>>1` instead of `(i+j)/2` trick to save bytes):
\\$median = \left\lfloor\frac{a\[i\]+a\[j\]}{2}\right\rfloor\\$

After which we can use this \\$median\\$ to calculate the absolute difference with the current item, which we can use to calculate the total sum:
\\$\sum\limits\_{k=0}^{l} = \left\lvert a\[k\] - median\right\rvert\\$
with \\$l\\$ being the length of the array \\$a\\$, and \\$k\\$ being the (0-based) index.
> 2 votes

# Answer
# 05AB1E, 4 bytes

```
δαOß

```

I know there is already an existing 4-bytes 05AB1E answer using the median builtin `Åm`, but I decided to post this alternative 4-byter without this builtin.

Try it online or verify all test cases.

**Explanation:**

```
δ     # Apply the following command double-vectorized on the given two arguments,
      # which will use the input-list twice implicitly, since the stack is empty:
 α    #  Absolute difference
      #  i.e. [1,10,100] → [[0,9,99],[9,0,90],[99,90,0]]
  O   # Sum each of these inner lists
      #  → [108,99,189]
   ß  # Pop and push the minimum of this list
      #  → 99
      # (after which this is output implicitly as result)

```
> 2 votes

# Answer
# Charcoal, ~~16~~ 11 bytes

```
Ｉ⌊ＥθΣＥθ↔⁻ιλ

```

Try it online! Link is to verbose version of code. Edit: Saved 5 bytes thanks to @Arnauld. Explanation:

```
  Ｅθ        Map over input array
     Ｅθ     Map over input array
         ι  Outer value
          λ Inner value
        ⁻   Difference
       ↔    Absolute value
    Σ       Sum
 ⌊          Minimum
Ｉ           Cast to string
            Implicitly print

```
> 1 votes

# Answer
# Attache, 18 bytes

```
Sum##Abs@`-#Median

```

Try it online!

## Explanation

```
Sum##Abs@`-#Median
            Median    take the median of the input list
     Abs@`-#          absolute difference with the original list
Sum##                 sum of all elements

```
> 1 votes

# Answer
# , 15 bytes

```
[:<./1#.|@-/~"{

```

Essentially the same as Shaggy's Japt solution.

Try it online!

## How it works?

`|@-/~"{` \- creates a table `/~` of absolute differences `|@-` of each number to all others `"{`

```
   |@-/~"{ 6 2 3 8
0 4 3 2
4 0 1 6
3 1 0 5
2 6 5 0

```

`1#.` sums each row

```
   1#.|@-/~"{ 6 2 3 8
9 11 9 13

```

`[:<./` finds the smallest item (reduce by minimum)

```
   ([:<./1#.|@-/~"{) 6 2 3 8
9

```
> 1 votes

# Answer
## Visual C#, 138 bytes

```
int s=0;foreach(string i in a)s+=int.Parse(i);int x=s/a.Length;int o=0;foreach(string i in a)o+=Math.Abs(int.Parse(i)-x);Console.Write(o);

```

ungolfed:

```
int s = 0;                    // Takes a string array of arguments a as input
foreach (string i in a)
     s += int.Parse(i);       // s as sum of the array elements
int x = s / a.Length;         // calculating the target value of all elements
int o = 0;                    // o as minimum number of moves
foreach (string i in a)
     o += Math.Abs(int.Parse(i) - x);    // summing up the moves to the target value
Console.Write(o);

```

Try it online!
> 1 votes

# Answer
# PHP, 78 bytes

Sorts the array, then loop through a copy, popping elements off the original and summing the absolute difference, that needs to be halved for the return.

```
function m($n){sort($n);foreach($n as$i)$r+=abs(array_pop($n)-$i);return$r/2;}

var_dump(
    m([10]),
    m([-1, 0, 1]),
    m([4, 7]),
    m([6, 2, 3, 8]),
    m([5, 8, 12, 3, 2, 8, 4, 5]),
    m([1,10,100])
);

```

Output:

```
int(0)
int(2)
int(3)
int(9)
int(19)
int(99)

```
> 1 votes

# Answer
# Ruby, 38 bytes

```
->a{a.map{|x|a.sum{|y|(y-x).abs}}.min}

```

Try it online!
> 1 votes

# Answer
# C++ (gcc), 94 bytes

```
#import<regex>
int f(int c,int*a){int s=0,d=0;for(std::sort(a,a+c);c-->d;)s+=a[c]-a[d++];c=s;}

```

Port of the PHP solution. Kudos to Titus!

Input size of the array and a non-`const` mutable array. Output the minimum number of moves required to equalize the array.

*-4 bytes thanks to ceilingcat!*

Try it online!
> 1 votes

# Answer
# V (vim), 84 bytes

```
:sort
Go<c-r>=(line('$')-1)/2
<esc>dd@"kk0vg_"ayGqq0C<c-r>=abs(<c-r>"-<c-r>a)
<esc>k@qq@q:%s/\n/+
$x0C<c-r>=<c-r>"
<esc>

```

Try it online!

`<c-r>` is very helpful in finding the median and the whole calculation in general.
> 1 votes

# Answer
# PowerShell, 107 bytes

```
$f={param($i)$m=($i|sort)[[int](($i.count-1)/2)];($j+=$i.foreach({([math]::abs($m-$_))})|measure -sum).Sum}

```

Try it online!

# PowerShell, 115 bytes

```
function f($i){$m=($i|sort)[[int](($i.Count-1)/2)];return($j+=$i.ForEach({([math]::Abs($m-$_))})|measure -Sum).Sum}

```

Try it online!
> 0 votes

# Answer
# PowerShell, 52 bytes

```
($a=$args|sort)|%{$_-$a[--$i]}|%{$s-=$_*($_-lt0)}
$s

```

Try it online!
> 0 votes

# Answer
# Perl 5 `-ap`, 39 bytes

```
map$\+=abs$_-(sort{$a-$b}@F)[@F/2],@F}{

```

Try it online!
> 0 votes

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

```
f=a=>(v=a.sort((x,y)=>x-y).pop()-a.shift())?v+f(a):0

```

Try it online!
> -1 votes

# Answer
**Kotlin Android, 200 bytes**

```
fun m(a:IntArray){var d=0;var s=0;var p=a.max()!!.times(a.size);var x =0;for(i in a.indices){x=a[i];d=0;s=0;while(d<a.size){if(x-a[d]<0)s=((x-a[d])*-1)+s;else s=((x-a[d]))+s;d++};if(p>s)p=s};print(p)}

```

Try Online
> -1 votes

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


title: Generate all 4-perfect numbers

text:
# Question
Title: Generate all 4-perfect numbers
Your program or function should output all the 36 4-perfect numbers in increasing order separated by newlines.

An `n` positive integer is a `k`-perfect number (multiply perfect number) if the sum of its divisors including itself (i.e. the sigma function of `n`) equals `k*n`.

For example `120` is a `3`-perfect number because `1 + 2 + 3 + 4 + 5 + 6 + 8 + 10 + 12 + 15 + 20 + 24 + 30 + 40 + 60 + 120 = 360 = 3*120`.

### Details

* Your entry should actually produce the output and terminate on your machine before you submit your answer. (i.e. the program should terminate in a reasonable time)
* Hardcoding is allowed.
* Built-in functions or data closely related to the problem (e.g. sigma function) are disallowed.
* This is code-golf but as the task is non-trivial without major hardcoding non-golfed entries are welcomed too.

(This is a great detailed page about the history of all multiply perfect numbers.)

# Answer
> 3 votes
# CJam, 377 bytes

All the characters are part of extended ASCII, so I'm counting this as a single byte per character

```
"Ò|+^ø¥©~öôxõÕÊïB.X}Ã+ç
âà©¥;ØÓé@ä¦qØH®üzGOwCàæ/Â$ªh#þ>üJNDÂTR{^ÌýÂ±OáÉÚ6ï®I?Çvqf³e1é^¶[Y½5ãþ#_-__xF'IMØ*¬È6Vô+§mâ?µTJÉ9$·Ùöµ¨±Dac&¼'h,q÷ZwÎE^§Å{åÁûà\µ;óÛ¤{n'ÜGÐÓR!³¥èè>(~\"NbU*ötmù¦ªUe|Rñ¾!a9TYÇ&êë½ôâ··¨JÆ#Ù&îCÎÍð4q<ÌÏïj;Åd*òz(x    ?ßâ%d8Æ¬ÔUÎ=¶îÖÀ+mHH9â\"=PÊ±edèËU·  /þr<ÆGR;|úÀè¶¡õrì@öÆ"255bBbAa/N*

```

I'm sure Stack Exchange will have swallowed some of the characters, so you might want to copy the code from this pastebin.

Test it here.

This solution is purely hardcoded. It interprets the code points of the characters as the digits of a base-255 number, gets the base-11 digits of that, splits on the digit `10` and joins the resulting arrays by newlines.

# Answer
> 5 votes
# Prime factorization (Ruby ,~~570~~ 542 bytes)

**Rev 0**

Below is a table of the prime factorizations of the 36 required numbers (copied from Wolfram, hopefully with no errors.) Only 31 prime factors are involved if I have counted correctly, and some of these always occur together, for example 137\*547\*1093 and 683\*2731\*8191.

It should be possible to condense the information in the table, or perhaps even employ a search strategy. This should beat simply compressing the numbers.

Unfortunately the numbers are too big even for a 128-bit integer, which means I can't use C. Ruby and Python do support arbitrary precision integers. I have put the table in valid Ruby syntax, which makes it my first ever Ruby program!

```
puts 2**5  *3**3  *5    *7
puts 2**3  *3**2  *5    *7           *13
puts 2**2  *3**2  *5    *7**2        *13      *19
puts 2**9  *3**3  *5          *11                         *31
puts 2**7  *3**3  *5**2                  *17              *31
puts 2**9  *3**2        *7    *11    *13                  *31
puts 2**8  *3     *5    *7                    *19             *37       *73
puts 2**10 *3**3  *5**2                               *23 *31                 *89
puts 2**13 *3**3  *5          *11                                 *43                 *127
puts 2**14 *3     *5    *7                    *19         *31                                   *151
puts 2**13 *3**2        *7    *11    *13                          *43                 *127
puts 2**5  *3**4        *7**2 *11**2          *19**2                                  *127
puts 2**8  *3**2        *7**2        *13      *19**2          *37       *73           *127
puts 2**7  *3**10 *5                     *17          *23                        *107                                               *3851
puts 2**7  *3**6  *5                     *17          *23                                  *137           *547           *1093
puts 2**14 *3**2        *7**2        *13      *19**2      *31                         *127      *151
puts 2**5  *3**4        *7**2 *11**2          *19**4                                            *151                *911
puts 2**9  *3**4        *7    *11**3                      *31**2     *61    *83                      *331
puts 2**8  *3**2        *7**2        *13      *19**4            *37     *73                     *151                *911
puts 2**25 *3**3  *5**2                       *19         *31                                                  *683            *2731       *8191
puts 2**17 *3**10       *7                    *19**2  *23       *37     *73      *107 *127                                           *3851
puts 2**17 *3**6        *7                    *19**2  *23       *37     *73           *127 *137           *547           *1093
puts 2**25 *3**4        *7    *11**2          *19**2                                  *127                     *683            *2731       *8191
puts 2**25 *3**5        *7**2        *13      *19**2                                  *127                     *683            *2731       *8191
puts 2**17 *3**10       *7                    *19**4  *23       *37     *73      *107           *151                *911             *3851
puts 2**25 *3**10 *5                          *19     *23                        *107                          *683            *2731 *3851 *8191
puts 2**17 *3**6        *7                    *19**4  *23       *37     *73                *137 *151      *547      *911 *1093
puts 2**25 *3**6  *5                          *19     *23                                  *137           *547 *683      *1093 *2731       *8191
puts 2**25 *3**4        *7    *11**2          *19**4                                            *151           *683 *911       *2731       *8191
puts 2**25 *3**5        *7**2        *13      *19**4                                            *151           *683 *911       *2731       *8191
puts 2**33 *3**4        *7    *11**3                      *31        *61    *83                      *331                                        *43691 *131071
puts 2**33 *3**10       *7    *11                     *23                   *83  *107                *331                      *3851             *43691 *131071
puts 2**33 *3**6        *7    *11                     *23                   *83            *137      *331 *547           *1093                   *43691 *131071
puts 2**37 *3**4        *7    *11**3                      *31        *61    *83                      *331                                        *43691        *174763*524287
puts 2**37 *3**10       *7    *11                     *23                   *83  *107                *331                      *3851             *43691        *174763*524287
puts 2**37 *3**6        *7    *11                     *23                   *83            *137      *331 *547           *1093                   *43691        *174763*524287

```

**Rev 1** Just starting to gather some terms.

```
#683*2731*8191=15278451143, 137*547*1093=81908327, 107*3851=412057, 174763*524287=91625968981, 19**2*151*911=49659521, 83*331=27473, 11**3*31*61=2516921,37*73=2701,19*19=361

puts 2**5  *3**3  *5       *7
puts 2**3  *3**2  *5       *7           *13
puts 2**2  *3**2  *5       *7**2        *13      *19
puts 2**9  *3**3  *5             *11                         *31
puts 2**7  *3**3  *5**2                     *17              *31
puts 2**9  *3**2           *7    *11    *13                  *31
puts 2**8  *3     *5       *7                    *19                *2701
puts 2**10 *3**3  *5**2                                  *23 *31                 *89
puts 2**13 *3**3  *5             *11                                 *43                 *127
puts 2**14 *3     *5       *7                    *19         *31                               *151
puts 2**13 *3**2           *7    *11    *13                          *43                 *127
puts 2**5  *3**4           *7**2 *11**2          *19**2                                  *127
puts 2**8  *3**2           *7**2        *13      *19**2            *2701                 *127
puts 2**7  *3**10 *5                        *17          *23                                                                           *412057
puts 2**7  *3**6  *5                        *17          *23                                                                *81908327
puts 2**14 *3**2           *7**2        *13      *19**2      *31                         *127  *151
puts 2**5  *3**4           *7**2 *11**2          *19**2                                            *49659521
puts 2**9  *3**4           *7                                *31    *2516921  *27473
puts 2**8  *3**2           *7**2        *13      *19**2            *2701                           *49659521
puts 2**25 *3**3  *5**2                          *19         *31                                                            *15278451143
puts 2**17 *3**10          *7                    *19**2  *23       *2701                 *127                                           *412057
puts 2**17 *3**6           *7                    *19**2  *23       *2701                 *127                               *81908327
puts 2**25 *3**4           *7    *11**2          *19**2                                  *127                                                   *15278451143
puts 2**25 *3**5           *7**2        *13      *19**2                                  *127                                                   *15278451143
puts 2**17 *3**10          *7                    *19**2  *23       *2701                           *49659521                            *412057
puts 2**25 *3**10 *5                             *19     *23                                                                            *412057 *15278451143
puts 2**17 *3**6           *7                    *19**2  *23       *2701                           *49659521                *81908327
puts 2**25 *3**6  *5                             *19     *23                                                                *81908327           *15278451143
puts 2**25 *3**4           *7    *11**2          *19**2                                            *49659521                                    *15278451143
puts 2**25 *3**5           *7**2        *13      *19**2                                            *49659521                                    *15278451143
puts 2**33 *3**4           *7                                       *2516921   *27473                                                               *43691 *131071
puts 2**33 *3**10          *7    *11                     *23                   *27473                                             *412057           *43691 *131071
puts 2**33 *3**6           *7    *11                     *23                   *27473                                       *81908327               *43691 *131071
puts 2**37 *3**4           *7                                       *2516921   *27473                                                               *43691        *91625968981
puts 2**37 *3**10          *7    *11                     *23                   *27473                                             *412057           *43691        *91625968981
puts 2**37 *3**6           *7    *11                     *23                   *27473                                       *81908327               *43691        *91625968981

```

**Rev 2, ~~570~~  542 bytes (thanks to Martin for the improvement)**

As this is my first Ruby program, I just stuck with the simple approach of continuing to gather terms. Compression of the numbers would be great if anyone knows how to do that.

I could save a few more bytes by evaluating some of the literal-only expressions in the variable assignment part, but I decided to leave them for clarity.

```
e=361
f=e*e*137561
g=27473
h=2516921
j=2701
k=81908327*729
m=412057*59049
n=15278451143*2**25
p=g*43691*2**33*7
q=131071
r=91625968981*16
s=127
t=1024
w=250240
x=1467648
y=7439488
puts [30240,32760,2178540,23569920,45532800,142990848,510720*j,t*42833475,t*510840*s,t*149417520,t*3099096*s,15367968*e*s,x*e*j*s,w*m,w*k,t*429378768*e*s,15367968*f,8999424*g*h,x*j*f,n*397575,t*m*y*j*s,t*k*y*j*s,n*68607*e*s,n*154791*e*s,t*20608*j*f*m,2185*n*m,t*20608*j*f*k,2185*k*n,68607*f*n,154791*f*n,81*h*p*q,253*p*m*q,253*p*k*q,81*h*p*r,253*p*m*r,253*p*k*r]

```

# Answer
> 3 votes
# JavaScript, 572 (?) bytes

```
_=>`@r>=V6R=bWn3s*Ch=%{Fg>QNM'|c6SMH>wF=*
IElopM2Mw=?-,Knb7bW{\\=\rH3j=N9.3l*jm6Y(.wJP|
tFR7vmvt/))*D.F)  . n}Hk18KTn0a{E6
w1z0]\\o.jV"ytga25d+~VNP{0v:zq[d)  |.]d,t6P5:;:*?9m[8sI>\\R"'
wG*<#[^L/HFzAISvBDnmuy;+JNQj_n{[*d6DH#HtsLt}\`T+DX3T6/17
guv,\\d8G!\\9;Wug[78\\Iw]5"
r!~ZqN96Y\\99-gCoT_w.3SHF:p||;j*uwm+
1mSXJ<bE1UT]\r:(QEJ3LGPM$8Le3WXCoU;3*jW.7:"5m7f"0S3k9Eko`.replace(/./gs,p=>p.charCodeAt().toString(2).padStart(7,0).slice(-7)).replace(/00|01.|1...|111$/g,d=>`0 12
3456789
`[parseInt(d,2)])

```

Potentially slightly more than 572, but without TIO I'm not sure if a different interpreter I used is counting a few `0x80` bytes (two bytes in UTF-8) correctly.

**Explanation:**

Uses huffman coding, where between two and four bits map to each digit:

```
0   00
1   010
2   011
3   1000
4   1001
5   1010
6   1011
7   1100
8   1101
9   1110
\n  1111 or 111

```

Each character is ASCII, so I get seven bits per byte. Some, like ``` and `\` need two bytes, and `\0` (null) is represented with `0x80`.

# Answer
> 3 votes
# Scratch, 327 bytes (Illegitimate)

Try it online!

I was really excited to submit this answer, but then I read the first rule, stating that my program must generate all 36 numbers before I can submit. However, this rule makes hard-coding the only viable option, which is not optimal. I decided to circumvent the several millennia necessary to satisfy this rule, and submitted an answer anyway! To make up for this heinous act, I will be explaining the code in depth here, in addition to on Scratch.

## Full code

```
when gf clicked
delete all of[4 v
delete all of[f v
set[N v]to(
forever
change[N v]by(1
set[F v]to(
repeat until<(F)=(N
change[F v]by(1
repeat until<((N)/(F))=(round((N)/(F
change[F v]by(1
end
add(F)to[f v
end
set[S v]to(
repeat(length of[f v
set[S v]to((S)+(item(1)of[f v
delete(1)of[f v
end
if<(S)=((N)*(4))>then
add(N)to[4 v

```

## Setup

```
when gf clicked       Initiates the code
delete all of[4 v     Clears the list of 4-perfect numbers
delete all of[f v     Clears any residual factors from a previous run of the code
set[N v]to(           Sets the number that will be checked for 4-perfection to 0
forever               Run the following code an infinite amount of times

```

## Factorization

```
change[N v]by(1                       Increments the number to be tested for 4-perfection
set[F v]to(                           Resets the factor that will be tested on the number
repeat until<(F)=(N                   Runs the following code when there is still a factor to be checked for
change[F v]by(1                       Increments the factor that will be tested on the number
repeat until<((N)/(F))=(round((N)/(F  Loops code until a valid factor is found
change[F v]by(1                       Increments the factor that will be tested on the number
end                                   Marks the end of the code that needs to loop
add(F)to[f v                          Adds the valid factor to the list of factors
end                                   Marks the end of the code that needs to loop

```

## Summation

```
set[S v]to(                       Resets the sum of the factors
repeat(length of[f v              Loops code for each factor in the list
set[S v]to((S)+(item(1)of[f v     Adds item 1 of the factor list to itself
delete(1)of[f v                   Deletes the obsolete 1st item in the list, making the 2nd item the new 1st item
end                               Marks the end of the code that needs to loop

```

## 4-Perfection Check

```
if<(S)=((N)*(4))>then     Runs code if the sum of factors is 4 times the original value
add(N)to[4 v              Adds the 4-perfect value to the list
                   NB: "if", "repeat", and "forever", blocks don't need an "end" statement when they're at the end of a script.
                   NB: Groupings ([], (), <>) don't need to be closed if they're at the end of a line.

```

Please understand that I have no intentions of undermining the integrity of the challenge, but I wanted to demonstrate the potential of non hard-coded programs. Scratch is a moderately verbose language- imagine how small a more golf-friendly language could be!

# Answer
> 2 votes
# Deadfish~, 3758 bytes

```
{iiiii}icdddciiciicddddc{dddd}iic{iiii}icdciiiiicdcddddddc{dddd}iic{iiii}cdciiiiiicicdddcdcddddc{dddd}iic{iiii}ciciiciciiicc{d}iiicddc{dddd}iic{iiii}iiciccddcdciiiiiic{d}iicc{dddd}iic{iiii}dciiicddc{i}dddcc{d}ic{i}ddcddddciiiic{dddd}ddddddc{iiii}dciiciiiiciicdddddcicdciiicdddddcddc{dddd}iic{iiii}iicdciiiiicddcdddddciiiciiicicddddcddddcc{dddd}iic{iiii}iiiiccddcdcciiiicdddddcddciiicdcddc{dddd}iic{iiii}dciiiicddcdddcciiiciicdcddddciiiiciiiic{d}iic{dddd}iic{iiii}iicddddciiicdddciiicddciciciiiccddddddc{i}ddc{dddd}ddddddc{iiii}iiiiic{d}iiiciiiiciciicddcdddcciiiiiiccicdddc{dddd}ddddc{iiii}dc{i}dddc{d}iiiciiiiiicdddcddciiiiiiccdddddciciiciiic{d}iciiiiicic{dddd}ddddc{iiii}iiiicddddddc{i}ddccdcdddddciiiiiic{d}iiciicdcciiiiicddddddciiicdcddc{dddd}iic{iiii}dciiiciiiiicdddddcddcdcicicdciiiiicdccddcdddc{i}ddc{d}iiicddc{dddd}iic{iiii}cddciciiiiciiic{d}iiic{i}dddcdddciiicdddciicddcddcddc{i}ddc{d}iciiiic{dddd}ddc{iiii}ciiiiicddccdddddciic{i}dddc{d}icciiiiiciiiicdddddcddddciicdciiicddddc{i}ddc{dddd}ddddddc{iiii}iiiicddddccciiiiiicddcdcdddddciiiiiiciic{d}iiicciiiicddddciiiicddciiiiiic{d}iiic{dddd}c{iiii}iiiiicddddddcdciiiiiicdcdddddc{i}dddcddcddddcdciiiicdddc{i}ddc{d}icc{i}dddcddddcdddc{i}ddcc{dddd}ddddddc{iiii}cddciiiciiiiicddddddcddc{i}dddc{d}iiiccc{i}ddcdddddciiicdddcicddciiicdciicddcdcdcddcc{dddd}iic{iiii}iiiicdddciiciiicdddddcdddciicddciciiiiicccddddddciic{i}dddcdddddcdcddc{i}ddcdcdcicicdddcdddcdc{dddd}c{iiii}dciiiicicddddddciiiciiicicdddciiiicicdddddcciiicddddciiiiiic{d}iciciiiiiicdddciciiiic{d}iicdciiiiiciiciic{d}iiic{dddd}c{iiii}dciiiiicdddddciciiicddcdciiiiiicddcddddddcc{i}dcddciicddddddcdciiiiciicddddddciciiiiicddcicddddciicddddcdciiiic{dddd}ddc{iiii}iciiicdddciiiiic{d}iiic{i}ddcddddddciiiiiicddcddddciiicddddddc{i}dcddddddciiiiicdddcddcdddc{i}ddc{d}iiic{i}ddcdddddciiiicddcdcddddciiiicdddc{dddd}c{iiii}ciiciiiicddcddddcccicdddciiiccddciciiciiicdddcddc{i}dddcdddcddcdddcccdciiicdddc{i}dddcdddciiicddddddciiciiic{dddd}ddddc{iiii}ciiiiicdddddciiiccdddciiiiicddddddcdc{i}dcdccicdddddcdciiicicdcicddddcciiiiicicddddcdddddcciiiccicddddc{i}ddc{d}iic{dddd}iic{iiii}iiiicdddddcdciciiciciiccddddcciiiiiicddddddc{i}dddc{d}iicic{i}dddccdc{d}iiic{i}ddc{d}iiciicdciiicdddciiicddciciiciic{d}iiiciiiiic{dddd}ddddc{iiii}iiiicciiccddcdddddciiiiciicddddciiiiicdddcdddddciiicdddciiiiiicddcddddcciiiciiiiiic{d}iicdc{i}dcddddddcdddc{i}dddciic{d}iiiciicciiiic{d}iic{dddd}iic{iiii}iiiicdddcdddciiiiicddcdciciiciiccddddddcdciiiicddcddcc{i}dddciicddddcdddddc{i}ddcddddcddciiiiiicdddddciiicddddciciicdddddciiiiiciiiic{d}iiic{dddd}c{iiii}dciiicddcciiiicddddddciiiiiicddddddciiiiiicdddcdciiiicddcddddcciiiiicicdddcciiiiiicddddddcdcciciiiiiic{d}iic{i}ddcddcc{d}iiiccc{i}dcdddc{dddd}ddddc{iiii}dc{i}ddc{d}iiiciiiiiicddcddddccicdddcciiciciiicdddcddc{i}dddc{d}iiciiiiciiiiicc{d}iiiciiiiiicddddddciiiciiic{d}iiiciiccddciiiiicddcddddciiicdc{dddd}c{iiii}iiiciiicddddddciciciiiicddddciiiciic{d}iicciiiiciiicdddciicdddcdciiicdddciiiiiic{d}iic{i}ddc{d}iicciiiicdddddciiciiiciiicdciic{d}iic{i}ddc{d}ic{i}dddcddddcdciiiiiic{dddd}ddddddc{iiii}dciiicddc{i}dddc{d}iicc{i}ddccdddcdddcdddc{i}dcddciicdddddciiicddddcciiiiciicdddcdddcdc{i}dddc{d}iiic{i}dddc{d}ic{i}dcddciicdddddciiciic{d}iiicciiiiciiiicdddciic{dddd}ddddddc{iiii}cdciiiiciicddddddciiicdciiiiiicdcdddcdddciiiicddddddcicciiciiiiiicdddddcddciiiicic{d}iiic{i}dddciic{d}iciiiiicdddddciiiiiciicdddddcdciiiiicdddddciiicddciiicdddddc{i}ddc{d}iiciiicdc{dddd}c{iiii}iiiicdcddddciiciicdddddc{i}dddcddddddciiiiiicddcdddddciiciicciiiccddddciiiiiic{d}iiiciiiiiic{d}iiicdcicicdciiicddddciicicicccdddcciiiiiicddddddciiciiiiciicdddciicdddddccdciiiiiic{dddd}ddddddc{iiii}dciiiiciiiicdcddddcicciiic{d}iiiciiiiciiiicdddcddciiccdcddddcdciiiiciciiiicdcddddddcciiciiicccddddcicdcddciiiciicddddddc{i}dddcddcdddcdc{i}dddcdccddddddc{i}ddcdddciic

```

It had to be done.

# Answer
> 1 votes
# Perl, 629 bytes

(Not counting one line break added for legibility)

```
use bignum;$_="762K7FF8G213DECG167A6O2B6C68K885DEO5238CFOA36590COF77C22S239FB8CS5DD688ASA40BF4CBEKA54B500277O15A1AA76D5D18K3515C82E18268K479DC3635ACS3D2C86DAC7F142K8A2CE47EB04E2O3DA39DD49D1B489O2B29246D35B6E2_34983A6E0D56A03116W8112111C1388B007CAW535DB1D8191384C3E_BC1718A816B9CA38E_139CE2CE0C2A6520D7D64EAW1580287D7C721FC8E0EFE_30219245E63381BDAD34236W34C38D4A316E11A76BA62_1F166FEDE2AA3B8DEE71C2_4623D01AD5164B207D6A72_5F16A2BFB16257500DB6g2BCF9FAD6C4DE65CA22F8C6Eg6B83D96C6A0809DCDEC5BFF2g3F648C3210B25B8737B940492k1D3523B8D99B8761B6AFBE903D97Ak47AD5F744AA0CC4A843901F8DEAA6k";
s#(\w+?)([G-z])#print hex($1)<<(ord($2)-71),$/#ge

```

The numbers are hard-coded in hexadecimal with a bit of compression applied to the trailing zeroes.

Try it out here.

---
Tags: code-golf, math, number, kolmogorov-complexity, number-theory
---


title: Negative Space Graphs

text:
# Question
Title: Negative Space Graphs
# Task

You will be given a positive integer and you must output a "self-complementary graph" with that many nodes. If you don't know what a self-complementary graph is the wikipedia article wont help you much so below are two explanations, a technical and a non-technical one.

## Non-Technical

A graph is a set of nodes that are connected by lines. Each pair of points can be connected by one line or none. The "complement" of a graph is the result of taking a graph and connecting all the nodes that are not connected and disconnecting all the nodes that are.

A self-complementary graph is a graph whose complement can be rearranged into the shape of the original. Below is an example of a self-complementary graph and a demonstration of how.

Here is a graph with 5 nodes:

We will highlight the all the places where connections could go with red dotted lines:

Now we will find the complement of the graph by swapping the red and black edges:

This does not look like the original graph but if we move the nodes around like so (each step swaps two nodes):

We get the original graph! The graph and its complement are the same graph

## Technical

A self-complementary graph is a graph that is isomorphic to its complement.

# Specifications

You will receive an positive integer via whatever method suits you best. And you will output a graph in whatever method you deem appropriate, this includes but is not limited to Adjacency Matrix Form, Adjacency List Form, and of course pictures! The outputted graph must be its own complement and have as many nodes as the integer input. If no such graph exists you must output a falsy value.

This is and you should aim to minimize your byte count.

# Test Cases

Below are pictures of possible outputs for several n

## 4

## 5

## 9

# Answer
# Haskell, 72 bytes

```
f n=[(a,b)|b<-[1..n],a<-[1..b-1],mod n 4<2,mod(a+b+sum[b|odd n,a<2])4<2]

```

Try it online!

A belated improvement inspired by ideas from kops. Takes vertex `1` to the the special vertex in the \\$n=1 \bmod 4\\$ case, rather than vertex `n`.

---

# Haskell, 77 bytes

```
f n=[(a,b)|b<-[1..n],a<-[1..b-1],mod n 4<2,mod(a+(last$b:[a|odd n,n==b]))4<2]

```

Try it online!

This uses an easy-to-compute explicit criterion to decide whether an edge `(a,b)` belongs in the graph. Instantiates this algorithm, with the permutation cycling among the values modulo 4

```
4*m -> 4*m+1 -> 4*m+2 -> 4*m+3 -> 4*m

```

We include edges whose two endpoint vertices add to 0 or 1 modulo 4. Note that cycling vertices as per this permutation adds 2 modulo 4 to the vertex sum on each each, and so swaps edges and non-edges. This gives a permutation of vertices that complements the edges.

If the graph has an extra node beyond a multiple of 4, it is put in a cycle alone. We include edges with it when then other vertex is even. Permuting the vertices flips the parity, and so the graph remains self-complementary.

If the number of vertices isn't 0 or 1 modulo 4, no self-complementary graph is possible because there's an odd number of edges in the complete graph

Overall, here are the conditions:

* If the input n isn't 0 or 1 modulo 4, output an empty list
* Otherwise if n is even, include all edges `(a,b)` with `a<b` and `a+b` equal to 0 or 1 modulo 4.
* Otherwise if n is odd, do the same, but instead include edges of the form `(a,n)` when a is even.

The code combines the second and third cases by replacing the condition `mod(a+b)4<2` with `mod(a+a)4<2` when both `odd n` and `b==n`.
> 9 votes

# Answer
# Brachylog 2, 24 bytes

```
{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧

```

Try it online!

This is a *function* that returns a pair consisting of two adjacency lists: one for the graph, one for the complement graph. (In the Brachylog interpreter on TIO, you can ask it to evaluate a function, rather than a full program, via giving `Z` as a command line argument.) For example, the output for input `5` is:

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

```

Here's what that looks like as an image (showing the two graphs):

As is common in Prolog-based languages, the function supports more than one call pattern. Notably, if you try to use it as a generator, it will output all possible self-complementary graphs with the given number of vertices (although I didn't take any effort to make this case usable, and notably it'll output each of the graphs many times each).

## Explanation

This is basically just a description of the problem, leaving the Prolog implementation to find the best method of solving it. (However, I doubt it will use an algorithm any better than brute force in this particular case, so it's likely fairly inefficient, and testing seems to confirm this, showing the performance getting much worse the larger the graph is.)

```
{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧
 ⟦₁                       The range [1, 2, …, ?], where ? is the input
   ⊇                      A subset of that range…
    Ċ                     …which has exactly two elements
{    }ᶠ                   A list of everything that fits the above description
{⟦₁⊇Ċ}ᶠ                   All edges that could exist in a ?-element graph
       p                  Find a permutation of these…
        ḍ                 …so that splitting it into two equal parts…
          (       ∨   )   …either:
               dl?          produces ? distinct elements
           \                after transposing it
            \ᵐ              and transposing its elements
              c             and flattening one level;
                          or:
                   ?<2      ? was less than 2
         .             ∧  Once you've found it, . specifies what to output

```

Incidentally, I ended up having to spend a whole 6 bytes (¼ of the program, the characters `(∨?<2)`) dealing with the special cases of 0 and 1. Frustrating, but that's the nature of special cases.

The `\\ᵐcdl?` section is a little hard to understand, so here's a worked example. Its purpose is to check whether something is a graph and its complement, with corresponding edges in the graph and complement being in the same order within the lists. The graph/complement pair becomes the eventual output of the program. Here's an example case:

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

```

Transposing this gives us a list of pairs of corresponding edges between the graph and the complement:

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

```

Next, we transpose inside the list elements and flatten one level; that gives us a list of pairs of corresponding elements between the graph and the complement:

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

```

Clearly, what we want here is for there to be no more than 1 pair starting from each element (thus proving that the elements of the graph and the complement are in 1-to-1 correspondence). We can almost verify that just by stating that the list has at exactly `?` distinct elements (i.e. a number of distinct elements equal to the number of vertices). In this case, the test succeeds; the distinct elements are:

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

```

However, this leaves room for a potential problem; if a vertex is entirely disconnected in the original graph, its correspondence won't be mentioned, leaving room for a duplicate correspondence from some other vertex. If this is the case, the complement graph must have an edge between that vertex (without loss of generality, let's say it's `1`), and every other vertex, and so the list of correspondences will contain `[1,2]`, `[1,3]`, …, `[1, ?]`. When `?` is large, this will lead to more correspondences total than we'd have otherwise, so there's no problem. The only issue happens when `?` is 3 or lower, in which case we only end up adding one extra correspondence (whilst removing one from `1` not appearing in the input); however, this is not a problem in practice, because there are 3 possible edges on a 3-element graph, which is an odd number (likewise, 1 possible edge on a 2-element graph is also an odd number), and thus the test will fail at the `\` step (you can't transpose a ragged list, i.e. ones whose elements have different lengths).
> 5 votes

# Answer
# BBC BASIC, 161 bytes

Tokenised filesize 140 bytes

Download interpreter at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

```
I.m:IF2ANDm ORm<4P.0:END
r=400n=-2A.m:t=2*PI/n:F.i=1TOn*n:a=i DIVn:b=i MODn:c=b:IFa+b A.2a*=t:b*=t:L.r+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1A.m A.c DRAWr*3,0
N.

```

**Ungolfed code**

```
  INPUTm                           :REM get input
  IF2ANDm ORm<4PRINT0:END          :REM if m=4x+2 or 4x+3 or less than 4, print 0 and exit
  r=400                            :REM radius of diagram
  n=-2ANDm                         :REM n = m truncated to an even number
  t=2*PI/n                         :REM t = 1/n turns
  FORi=1TOn*n                      :REM for each combination of vertices
    a=i DIVn                       :REM extract a and b
    b=i MODn                       :REM make a copy of c
    c=b                            :REM if a+b MOD 4 = 2 or 3, convert a and b to angles and draw edge.
    IFa+b AND2 a*=t:b*=t:LINEr+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1ANDm ANDc DRAWr*3,0
  NEXT                             :REM if m is odd and c is odd, draw a line to the additional vertex for m=4x+1 input.

```

**Explanation**

This uses the same algorithm as Xnor, but produces a diagrammatic output.

Where `n` is of the form `4x+2` or `4x+3` there is no solution as the number of edges is odd.

Where `n` is of the form 4x we arrange all the vertices in a circle and draw those edges where `(a+b) mod 4`is 2 or 3 (not 0 or 1 as in Xnor's case, for golfing reasons. This is therefore the complement of the solution given by Xnor.)

To see this in a more pictoral sense, we take every second vertex and draw the edges to the vertices 1 and 2 places away in anticlockwise direction. This defines `n` parallel directions, half of the total. Then we add in all the other edges parallel to these.

The complement can be found by adding 1 to both a and b in each edge specification, or pictorally by rotating the diagram by a `1/n` turn.

Where `n` is of the form 4x+1 we add another vertex, which is linked to every second vertex of the 4x graph. If it was placed at the centre the symmetry of the diagram would be preserved, but I chose to place it outside the main circle of points for clarity.

**Output**

The following are the first few cases for 4x+1. the 4x cases can be seen by deleting the vertex at bottom right and its associated edges.
> 2 votes

# Answer
# Haskell, 75 bytes

```
f n=[(a,b)|b<-[1..n],a<-[1..b-1],n#0,a#sum(b:[a|n#3,n==b])]
x#y=mod(x+y)4<2

```

Try it online!

This is a direct golf of @xnor's solution posted as a separate answer for the bounty

There are two 1 byte saves here, one by replacing `last` with `sum` since in the case where we are checking whether `a` is even via `2*a mod 4 < 2`, `b` happens to be known to be `1 mod 4` so adding it as well (producing `2*a+b`) is harmless.

The second is by creating the hammer of `x#y=mod(x+y)4<2` and aggressively finding a bunch of nails to hit with it, which just barely comes out to 1 byte shorter.
> 2 votes

# Answer
# JavaScript (ES6), 191 bytes

```
f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a

```

This function returns an adjacency list. It uses two algorithms, and differentiates between empty complementary graphs and non-outputs by returning `0` instead of `[]` when none exists. The first algorithm is based on Rado Graphs constructed using the BIT predicate, and creates valid 0-, 1-, 4- and 5-order complementary graphs. The other algorithm, found by our friends at mathematics, constructs a valid V+4 vertex complementary graph by applying a 4-path addition to a valid V vertex complementary graph.

It begins by validating the input to confirm the existence of a valid complementary graph (using `n*~-n/4%1`), and if that fails, returns `0`. It then checks if `n>5` and recurses to the `n-4` case to construct a valid lower order solution, then applies the 4-addition to the returned adjacency list on the way back up the recursion chain. Lastly, if `n>5` is not true, it iterates from `0` to `n-1` for `x` and `y`, and checks if the `(y>>x)&1` is true. If so, then those nodes are paired.

Here is a more readable format of the function, with ternary operators expanded to if-else statements and `eval()`s inlined:

```
// precalculate amount of required vertices in v
f = (n, a = [], v = n*~-n / 4) => {
  // if amount is non-integer
  if (v % 1) {
    // no valid complementary graph
    return 0;
  } else {
    if (n > 5) {
      // generate valid (n-4)-order complementary graph
      f(n -= 4, a);
      // apply 4-path addition
      for (i = 0; i < n;)
        a.push([i, n+1],[i++, n+2]);
      a.push([n, ++n], [n, ++n], [n, ++n]);
    } else {
      // construct Rado graph using BIT predicate
      for(l = x = 0; x < n; x++)
        for(y = x; y < n; y++)
          // if amount of pairs is less than required and xth bit of y is high
          if (l < v && (y>>x & 1))
            // vertices x and y should be paired
            a.push([x,y]);
    }
    return a;
  }
};

```

### Demo

```
f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a
```

```
<input type="number" onchange="o.textContent=JSON.stringify(f(this.value))"><pre id="o"></pre>
```
> 1 votes

---
Tags: code-golf, graph-theory
---


title: Tips for golfing in vim

text:
# Question
Title: Tips for golfing in vim
I've recently realized how vim works great for golfing, especially for . Also, according to meta vim is a perfectly acceptable 'programming language' at least, for the scope of this site, that is.

What general tips do you have for golfing in Vim? I'm looking for ideas which can be applied to code-golf problems and which are also at least somewhat specific to Vim (e.g. "remove comments" is not an answer).

Please post one tip per answer.

# Answer
Be aware of the uppercase variants of common commands. This can trivially save one keystroke in a lot of contexts. For example:

```
A = $a
C = c$
D = d$
I = ^i
S = cc
X = dh
Y = yy

```

Another one is to use `G` instead of `gg`, but only if you use a count! For example, without a count, `gg` moves to the beginning, and `G` moves to the end. However, with a count, they both move to the line you specify, so `5G` is shorter than but equivalent to `5gg` .

Another one, is to use `H` in place of `gg`, but it's important to note that this only works if you can guarantee that any input will not take up more than the default number of rows (I believe this is 24, but it may vary).
> 20 votes

# Answer
Anytime a command fails, it will make a ding noise, which will cancel the current macro. You can (ab)use this to create a crude form of loop. For example, if you want to repeat the keystrokes `<foobar>` until your buffer has less than 3 lines in it. You can do

```
qq<foobar>3G``@qq

```

which means:

```
qq                 'Start recording in register q
  <foobar>         'Keystrokes
          3G       'Go to line 3. If line 3 doesn't exist, this is effectively a "break" statement.
            ``     'Jump back to previous cursor location
              @q   'Call macro q
                q  'Stop recording

```

It's important to note that if you are testing this in a vim session, the `@q` might have unintended side effects, since macros are loaded from `.vim_profile`. You can get around this a couple different ways. Probably the best workaround is to launch vim with

```
vim -i NONE

```

You could also delete your `.viminfo`.

If you have already launched vim, you can type

```
qqq

```

at the beginning to zero the macro out.

Other conditions you can replace the 3G with are

```
f<char>    'Jump to first occurence of <char>. Also see F, t and T

```

or

```
<number>|  'Go to the <number>'th character on the current line.

```
> 13 votes

# Answer
# The alphabet in 10 keystrokes

All credit for this technique goes to Lynn, who first used it in this answer. I'm writing it up here for posterity.

Use the following ten keystrokes to yank the lowercase alphabet:

```
:h<_␍jjYZZ

```

(Where  is a carriage return, i.e. the Enter key.)

## Explanation

`:h<_␍` opens the help section `v_b_<_example` (an example of visual blockwise selection), which happens to contain the text `abcdefghijklmnopqrstuvwyxz`. `jjY` moves down to that line and yanks it, then `ZZ` closes the help window.
> 11 votes

# Answer
```
:%s/\n//g

```

is *always* equivalent to

```
:%s/\n//

```

which happens to also be equivalent to

```
:%s/\n

```

surprisingly enough. (In general, without any flags, the last slash in a `:s` expression is never necessary.)
> 8 votes

# Answer
There are more shortened versions of ex commands that you think. For example, you probably already knew that `:global` can be shortened to `:g`, but did you know that `:nnoremap` is equivalent to `:nn`?

It's a good idea to run `:h :foo` on all the ex commands you're using in your answer to see if there's a shorter version.
> 8 votes

# Answer
Let's say you're in insert mode, and you want to make a single normal mode command. You might write that like this:

```
isome_text<esc><foobar>gisome_more_text

```

Don't do it that way. Instead, use `<C-o>`, which executes a single normal command then immediately returns to insert mode.

```
isome_text<C-o><foobar>some_more_text

```
> 7 votes

# Answer
# Golfier movements

Frequently if you're working with a block of text (especially in challenges), you'll need to move to the first or last character in the buffer. `G` and `gg` are pretty good, but there are some annoying things. For example, to get the last character, you need `G$` and `gg` will not necessarily put you on the first column if there's leading whitespace. Here are some nicer movements, although note that they only work if your text doesn't have empty lines in the middle of it:

* First character of the buffer: `{` is better than `gg0`. If there are empty lines in the middle of the text, you can also use `go` which brings you to the first character in the buffer no matter what.
* Last character of the buffer: `}` is better than `G$`

These also work as an argument to an operator, but note that they are character-wise movements, not line-wise movements!
> 6 votes

# Answer
This came up in chat earlier, so I thought I might as well post it as a full tip.

`<C-a>` and `<C-x>` increment and decrement the next number on the line. This is an extremely useful feature for some simple math, but it also allows for a neat little hack.

Let's say you need to jump to the next number. For example, we need to change

```
I need 2 spell better

```

to

```
I need to spell better

```

The obvious way is to jump to the 2, then do:

```
sto                "Synonymous with 'clto'

```

Since this is shorter than

```
:s/2/to<cr>

```

There are many different ways to jump to the 2. For example,

```
/2<cr>
ww
2w
ee
2e
8|
f2

```

As well as many other ways.

These are all 2 (or more) keystrokes. However, since `<C-a>` and `<C-x>` not only increment/decrement numbers, but also jump to the next number, we can take a byte off with

```
<C-a>sto

```
> 5 votes

# Answer
There are three "change case" operators,

```
gu    "Convert to lowercase
gU    "Convert to uppercase
g~    "Toggle case

```

Since these are operators, they take a motion, so to convert the current character to lowercase you would use

```
gul

```

Here's where the fun trick comes in. :) If you want to change the case of a single character or the current line, it's a byte shorter in visual mode. For example `gul` is equivalent to

```
vu

```

And `gu_` (\_ is current line) is equivalent to

```
Vu

```

This trick does *not* work for toggling, because `v?` triggers a backwards search in visual mode, (just like `v/` but moving in the opposite direction) so you need `vg?` instead. However, here's where you can use the `~` operator, to save even more bytes! (Thanks @Doorknob for pointing this out)

You can see this trick in action on my vim answer here, and on the equivalent V answer on the and post.
> 5 votes

# Answer
# Know your registers

Yanking or deleting text into a specific register (e.g. `"aY`) to use it later isn't always necessary. Vim has several registers that are automatically populated with the subjects of various commands. Type `:help registers` to see them all, but here's a few of particular note:

* Unnamed register: `""` \- The last text that was yanked or deleted.
* Numbered register `"0` \- The last text that was yanked.
* Numbered registers `"1``"9` \- The last text that was deleted unless it was less than one line. Each time `"1` is filled its previous contents are shifted to `"2` and so on.
* Small delete register: `"-` \- The last text shorter than one line that was deleted.
* Last inserted text: `".`

In particular, the `"-` and `"1` registers can be useful together, enabling you to delete some text with e.g. `dd` into the `"1` register and delete some other text with `D` into the `"-` (of course, the semantics aren't identical, but often they don't need to be).

All of the registers can be a little tough to keep track of, but you can see the contents of all of your registers at any time by typing `:registers`.
> 5 votes

# Answer
# Do calculations with the expression register

You can do calculations in both normal mode and insert mode.

## Normal mode

In normal mode, if you type `@=` your cursor will move to the command line, where you can enter any expression. When you press enter, the result of the expression will be executed as normal mode commands.

For example, suppose you want to go to the middle column of the current line. The function call `col('$')` returns the number of columns in the line, so we can accomplish what by typing the following:

```
@=col('$')/2<CR>|

```

When you press enter, the cursor returns to the buffer and vim waits for an operator (like `|`) as though you had just entered a number. Alternatively, you could have entered this:

```
@=col('$')/2.'|'

```

...but of course that's more bytes.

## Insert mode

You can use the expression register in insert mode, too, by pressing `<Ctrl-r>=` instead of `@=`. It works the same in normal mode, except the result of the expression you enter will be executed in insert mode. For example, if you typed `<Ctrl-r>=col('$')<CR>`, the number of columns in the current line would be inserted at the cursor as though you had typed it.

For more information on the expression register, type `:help "=`.

## Reusing expressions

The last expression you used is stored in the expression register, `"=`. Typing `@=<CR>` in normal mode or `<Ctrl-r>=<CR>` in insert mode will evaluate the expression again, allowing you to use them much like macros.

# Do calculations in substitutions

You can evaluate expressions when doing regular expression substitutions, too. All you have to do is begin your substitution with `\=`. For example, suppose you wanted to number the lines in this file:

```
foo
bar
baz

```

The function call `line('.')` returns the current line number, so the job is easy. Entering this:

```
:s/^/\=line('.').' '/g<CR>

```

...yields the desired result:

```
1 foo
2 bar
3 baz

```

To use captured groups in such an expression you can use the `submatch()` function, where e.g. `submatch(0)` is equivalent to `\0` in an ordinary substitution, `submatch(1)` is equivalent to `\1`, etc. This eats up a lot of keystrokes, unfortunately.

For more information on expression substitution, type `:help sub-replace-expression`.
> 3 votes

# Answer
# Rotate your loops

Rotating loops is a golfing trick in many languages but I've found it to be more frequently useful in vim, largely due to the fact that loops usually exit by failure. This allows you to determine a *subset* of code to be executed on the first and/or last iteration.

Thus, when you have code like `<init>qq<loop>@qq@q<finalize>`, try to see if you can rotate the loop in order to overlap with either the init code or the finalize code so that they can be merged. Here's an example I used in a recent golf.

A straightforward 16 byte solution might look like this:

```
x$pqqF xp@qq@qZZ

```

This moves the first character to the end, and then in the loop moves backwards to the previous space character and swaps it with the letter that follows it, once it reaches the first space character. One can check that this algorithm solves the challenge in general.

The observation we can make here is that we wrote `p` twice: once just before the loop and once just at the end of it. It turns out we can merge them together like so:

```
x$qqpF x@qq@qZZ

```

Notice how we managed to save a character by only writing `p` once: we rotated the loop by one character and had the first iteration of the loop do us the favor of finishing up the `init` work of pasting the first character at the end of the string. Note that the total execution pattern of this solution is exactly the same as the previous one, since we will still exit the loop on failure of the final `F`  command.

(Technical NB: there's some added subtleties on the Anarchy Golf server since macro definitions are saved between test cases, and because of this the solution above won't work on the 2nd and 3rd test cases when `q` is already defined. My linked solution is roughly equivalent but loses a bit of generality to get around this.)
> 2 votes

# Answer
You can directly modify the text of a macro, which can be significantly shorter than a convoluted conditional. For example, let's say you want to paste something *n* times, where *n* is user input. I first tried to do this:

```
qq/[1-9]<enter><c-x>``p@qq@q

```

Explanation:

```
qq                             #Start Recording
  /[1-9]<enter>                #Search for a number that isn't 0.
                <c-x>          #Decrement that number
                     ``p       #jump back to your previous location and paste.
                        @q     #Recursive call to macro 'q'
                          q@q  #Stop recording, and run the macro

```

This is 18 keystrokes, and a really ugly way to do it. Instead, go to the location of that number, and do this:

```
Ap<esc>"qdd@q

```

Explanation:

```
Ap<esc>                 #Append a 'p' to the end of the current line.
       "qdd             #Delete the current line into register q
           @q           #Run macro q.

```

This is 9 keystrokes, a huge improvement.

## Edit:

Even shorter is to run the macro for your number, and then type your command. For example:

```
"qdd@qp

```

Explanation:

```
"qdd         #Delete the current line into register q
    @q       #Run register q
      p      #Paste

```

7 keytstrokes.
> 1 votes

---
Tags: code-golf, tips, vim
---


title: Divide a string

text:
# Question
Title: Divide a string
# Challenge

Given a string and a number, divide the string into *that many* equal-sized parts. For example, if the number is 3, you should divide the string into 3 pieces no matter how long the string is.

If the length of the string does not divide evenly into the number provided, you should round down the size of each piece and return a "remainder" string. For example, if the length of the input string is 13, and the number is 4, you should return four strings each of size 3, plus a remainder string of size 1.

If there is no remainder, you may simply not return one, or return the empty string.

The provided number is guaranteed to be less than or equal to the length of the string. For example, the input `"PPCG", 7` will not occur because `"PPCG"` cannot be divided into 7 strings. (I suppose the proper result would be `(["", "", "", "", "", "", ""], "PPCG")`. It's easier to simply disallow this as input.)

As usual, I/O is flexible. You may return a pair of the strings and the remainder string, or one list of strings with the remainder at the end.

# Test cases

```
"Hello, world!", 4 -> (["Hel", "lo,", " wo", "rld"], "!") ("!" is the remainder)
"Hello, world!", 5 -> (["He", "ll", "o,", " w", "or"], "ld!")
"ABCDEFGH", 2 -> (["ABCD", "EFGH"], "") (no remainder; optional "")
"123456789", 5 -> (["1", "2", "3", "4", "5"], "6789")
"ALABAMA", 3 -> (["AL", "AB", "AM"], "A")
"1234567", 4 -> (["1", "2", "3", "4"], "567")

```

# Scoring

This is , so the shortest answer in each language wins.

Bonus points (not really ) for making your solution actually use your language's division operator.

# Answer
# Python 2, ~~63~~ 59 bytes

```
s,n=input()
b=len(s)/n
exec'print s[:b];s=s[b:];'*n
print s

```

Try it online!
> 7 votes

# Answer
# PHP\>=7.1, 75 bytes

```
[,$s,$d]=$argv;print_r(preg_split('/.{'.(strlen($s)/$d^0).'}\K/',$s,$d+1));

```

Testcases

# PHP\>=7.1, 52 bytes

print only the remainder

```
[,$s,$d]=$argv;echo substr($s,(strlen($s)/$d^0)*$d);

```

Test Cases
> 5 votes

# Answer
# Haskell, 62 bytes

`#` is an operator taking a `String` and an `Int`, and returning a list of `String`s.

Use as `"Hello, world!"#4`.

```
s#n|d<-length s`div`n=[take(d+n*0^(n-i))$drop(i*d)s|i<-[0..n]]

```

Try it online!

# How it works

* `s` is the input string and `n` is the number of non-remainder pieces.
* `d` is the length of each "normal" piece. `div` is integer division.
* The list comprehension constructs `n+1` pieces, with the last being the remainder.
    + `i` iterates from `0` to `n`, inclusive.
    + For each piece, first the right amount (`i*d`) of initial characters are `drop`ped from the beginning of `s`, then an initial substring is `take`n from the result.
    + The substring length taken should be `d`, except for the remainder piece.
        - The actual remainder must be shorter than `n`, as otherwise the normal pieces would be lengthened instead.
        - `take` returns the whole string if the length given is too large, so we can use any number `>=n-1` for the remainder piece.
        - The expression `d+n*0^(n-i)` gives `d` if `i<n` and `d+n` if `i==n`. It uses that `0^x` is `1` when `x==0`, but `0` if `x>0`.
> 5 votes

# Answer
# Pip, 21 bytes

20 bytes of code, +1 for `-n` flag.

```
a~C(#a//b*XX)XbP$$$'

```

Takes inputs as command-line arguments; outputs strings and remainder newline-separated. Try it online!

### Explanation

Fun with regex operations!

Let's take `abcdefg` as our string and `3` as our number. We construct the regex `(.{2})(.{2})(.{2})`, which matches three runs of two characters and stores them in three capture groups. Then, using Pip's regex match variables, we can print 1) the list of capture groups `["ab";"cd";"ef"]`, and 2) the remainder of the string that wasn't matched `"g"`.

```
                      a,b are cmdline args; XX is the regex `.` (match any one character)
    #a//b             Len(a) int-divided by b: the length of each chunk
         *XX          Apply regex repetition by that number to `.`, resulting in something
                        that looks like `.{n}`
  C(        )         Wrap that regex in a capturing group
             Xb       Repeat the whole thing b times
a~                    Match the regex against a
               P$$    Print $$, the list of all capture groups (newline separated via -n)
                  $'  Print $', the portion of the string after the match

```
> 5 votes

# Answer
# Python 2, ~~68 67~~ 65 bytes

* @musicman123 saved 2 bytes:output without enclosing with `[]`
* Thanks to @Chas Brown for 1 Byte: `x[p*i:p+p*i]` as `x[p*i][:p]`

```
def f(x,n):p=len(x)/n;print[x[p*i:][:p]for i in range(n)],x[p*n:]

```

Try it online!
> 4 votes

# Answer
# C++14, ~~209~~ 180 bytes

That's a bit too long, but uses the division operator:

```
#include<bits/stdc++.h>
using q=std::string;using z=std::vector<q>;z operator/(q s,int d){int p=s.length()/d,i=0;z a;for(;i<d+1;){a.push_back(s.substr(i++*p,i^d?p:-1));}return a;}

```

Usage:

```
vector<string> result = string("abc")/3;

```

Online version: http://ideone.com/hbBW9u
> 4 votes

# Answer
# Pyth, 9 bytes

```
cz*L/lzQS

```

Try it online

### How it works

First `Q` is autoinitialized to `eval(input())` and `z` is autoinitialized to `input()`.

```
cz*L/lzQSQ
     lz      length of z
    /  Q     integer division by Q
  *L         times every element of
        SQ       [1, 2, …, Q]
cz           chop z at those locations

```
> 4 votes

# Answer
# Jelly, 11 bytes

```
Ld⁹x,1$}R⁸ṁ

```

Try it online!
> 3 votes

# Answer
# Rust, 107 bytes

```
fn f(s:&str,n:usize)->(Vec<&str>,&str){let c=s.len()/n;((0..n).map(|i|&s[i*c..i*c+c]).collect(),&s[c*n..])}

```

Try it online!

Formatted:

```
fn q129259(s: &str, n: usize) -> (Vec<&str>, &str) {
    let c = s.len() / n;
    ((0..n).map(|i| &s[i * c..i * c + c]).collect(), &s[c * n..])
}

```

This simply `map`s indices onto the correct slices of the source `str` (`collect`ing into a `Vec`) and slices out the remainder.

Unfortunately, I cannot make this a closure (74 bytes):

```
|s,n|{let c=s.len()/n;((0..n).map(|i|&s[i*c..i*c+c]).collect(),&s[c*n..])}

```

as the compiler fails with

```
error: the type of this value must be known in this context
 --> src\q129259.rs:5:18
  |
5 |          let c = s.len() / n;
  |                  ^^^^^^^

```

and if I provide the type of `s:&str`, the lifetimes are wrong:

```
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
 --> src\q129259.rs:6:27
  |
6 |          ((0..n).map(|i| &s[i * c..i * c + c]).collect(), &s[c * n..])
  |                           ^^^^^^^^^^^^^^^^^^^
  |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the body at 4:18...
 --> src\q129259.rs:4:19
  |
4 |       (|s: &str, n| {
  |  ___________________^
5 | |          let c = s.len() / n;
6 | |          ((0..n).map(|i| &s[i * c..i * c + c]).collect(), &s[c * n..])
7 | |      })(s, n)
  | |______^
note: ...so that reference does not outlive borrowed content
 --> src\q129259.rs:6:27
  |
6 |          ((0..n).map(|i| &s[i * c..i * c + c]).collect(), &s[c * n..])
  |                           ^
note: but, the lifetime must be valid for the lifetime 'a as defined on the body at 3:58...
 --> src\q129259.rs:3:59
  |
3 |   fn q129259<'a>(s: &'a str, n: usize) -> (Vec<&str>, &str) {
  |  ___________________________________________________________^
4 | |     (|s: &str, n| {
5 | |          let c = s.len() / n;
6 | |          ((0..n).map(|i| &s[i * c..i * c + c]).collect(), &s[c * n..])
7 | |      })(s, n)
8 | | }
  | |_^
note: ...so that expression is assignable (expected (std::vec::Vec<&'a str>, &'a str), found (std::vec::Vec<&str>, &str))
 --> src\q129259.rs:4:5
  |
4 | /     (|s: &str, n| {
5 | |          let c = s.len() / n;
6 | |          ((0..n).map(|i| &s[i * c..i * c + c]).collect(), &s[c * n..])
7 | |      })(s, n)
  | |_____________^

```
> 3 votes

# Answer
# Retina, 92 bytes

```
(.+)¶(.+)
$2$*1¶$.1$*1¶$1
(1+)¶(\1)+
$1¶$#2$*1¶
\G1(?=1*¶(1+))
$1¶
¶¶1+

O^$`.

¶1+$

O^$`.

```

Try it online! Explanation: The first stage converts the number of parts to unary and also takes the length of the string. The second stage then divides the length by the number of parts, leaving any remainder. The third stage multiplies the result by the number of parts again. This gives us the correct number of strings of the correct length, but they don't have the content yet. The number of parts can now be deleted by the fourth stage. The fifth stage reverses all of the characters. This has the effect of switching the original content with the placeholder strings, but although it's now in the right place, it's in reverse order. The placeholders have served their purpose and are deleted by the sixth stage. Finally the seventh stage reverses the characters back into their original order.
> 3 votes

# Answer
# Perl 6, 36 bytes

```
{$^a.comb.rotor($a.comb/$^b xx$b,*)}

```

Try it online!

Returns a list of lists of strings, where the last element is the remainder (if there is one).

### Explanation:

```
{                                  }  # Anonymous code block
 $^a.comb                             # Split the string into a list of chars
         .rotor(                  )   # And split into
                            xx$b      # N lists
                $a.comb/$^b           # With string length/n size
                                ,*    # And whatever is left over

```
> 3 votes

# Answer
# Python, ~~82~~ ~~76~~ 74 bytes

```
def G(h,n):l=len(h);r=l/n;print[h[i:i+r]for i in range(0,n*r,r)],h[l-l%n:]

```

Well, looks like this qualifies for the bonus points.  May I please receive a cookie instead? Oh wait, they aren't real? Darn...

Try It Online!
> 2 votes

# Answer
# JavaScript (ES6), 77 bytes

```
(s,d,n=s.length)=>[s.match(eval(`/.{${n/d|0}}/g`)).slice(0,d),s.slice(n-n%d)]

```

Returns an array of two elements: the divided string parts and the remainder part.

## Test Snippet

```
f=
(s,d,n=s.length)=>[s.match(eval(`/.{${n/d|0}}/g`)).slice(0,d),s.slice(n-n%d)]
```

```
<div oninput="O.innerHTML=I.value&&J.value?JSON.stringify(f(I.value,+J.value)):''">String: <input id=I> Number: <input id=J size=3></div>
<pre id=O>
```
> 2 votes

# Answer
# Japt, 18 bytes

```
¯W=Ul fV)òW/V pUsW

```

Test it online! (uses `-Q` flag to visualize the output)

### Explanation

```
¯W=Ul fV)òW/V pUsW  : Implicit: U = input string, V = input integer
   Ul fV            : Floor U.length to a multiple of V.
 W=                 : Assign this value to variable W.
¯       )           : Take the first W characters of U (everything but the remainder).
         òW/V       : Partition this into runs of length W / V, giving V runs.
              pUsW  : Push the part of U past index W (the remainder) to the resulting array.
                    : Implicit: output result of last expression

```
> 2 votes

# Answer
## Python, ~~95, 87, 76~~ 73 Bytes

```
def f(s,n):
 a=[];i=len(s)/n
 while n:a+=s[:i],;s=s[i:];n-=1
 print a+[s]

```

Try it online!
> 2 votes

# Answer
# 05AB1E, 12 bytes

```
²g¹‰`s¹.D)R£

```

Try it online!

### Explanation

```
²g¹‰`s¹.D)R£
²g           # Push length of string
  ¹          # Push amount of pieces
   ‰         # divmod of the two
    `s       # Flatten the resulting array and flip it around
      ¹.D    # Repeat the resulting length of the pieces amount of pieces times(wow that sounds weird)
         )   # Wrap stack to array
          R  # Reverse (so the remainder is at the end)
           £ # Split the input string into pieces defined by the array

```
> 2 votes

# Answer
# Brachylog, 16 bytes

```
kʰ↙Xḍ₎Ylᵛ&ht↙X;Y

```

Try it online!

Takes input as a list `[string, number]` and outputs as a list `[remainder, parts]`. (Commas were replaced with semicolons in the "Hello, world!" test cases for clarity, since the string fragments don't get printed with quotes.)

```
                    The input
 ʰ                  with its first element
k ↙X                having the last X elements removed
    ḍ               and being cut into a number of pieces
     ₎              where that number is the last element of the input
      Y             is Y
       lᵛ           the elements of which all have the same length,
         &          and the input
          h         's first element
           t↙X      's last X elements
              ;     paired with
               Y    Y
                    are the output.

```

(I also replaced a comma in the code with a semicolon for a consistent output format. With the comma, cases with no remainder would just output the parts without an empty remainder, and as nice as that is for some purposes, I don't actually know why it works that way...)

After this came out to be a whole 16 bytes, I tried to make something based on `+₁ᵗ⟨ġl⟩` work, but as the fixes got longer and longer I decided that I would just stick with my original solution for now.
> 2 votes

# Answer
## C(gcc), 72 bytes

```
d;f(s,n)char*s;{for(d=strlen(s)/n;n--;puts(""))s+=write(1,s,d);puts(s);}

```

Try It Online
> 2 votes

# Answer
# Excel Formula, ~~185~~ ~~173~~ ~~165~~ ~~161~~ 149 bytes

The following should be entered as an array formula (`Ctrl`+`Shift`+`Enter`):

```
=MID(A1,(ROW(OFFSET(A1,,,B1+1))-1)*INT(LEN(A1)/B1)+1,INT(LEN(A1)/B1)*ROW(OFFSET(A1,,,B1+1))/IF(ROW(OFFSET(A1,,,B1+1))=B1+1,1,ROW(OFFSET(A1,,,B1+1))))

```

Where `A1` contains your input (e.g. `12345678`) and `B1` contains the divisor. This also uses Excel's division operator for a bonus.

After entering the formula as an array formula, highlight it in the formula bar and evaluate it using `F9` to return the result, for example:

**-12 bytes:** replace each `INDIRECT("1:"&B1+1)` with `OFFSET(A1,,,B1+1)` to save 2 bytes per occurence, plus some tidying removing redundant brackets.

**-8 bytes:** remove redundant `INDEX` function.

**-4 bytes:** rework "remainder" handling.

**-12 bytes:** remove redundant `INT(LEN(A1)/B1)` by offsetting array generated by `ROW(OFFSET(A1,,,B1+1))` by -1.
> 2 votes

# Answer
# V (vim), 62 bytes

```
YpC<c-r>=strlen('<c-r>"')
<esc>jYp<c-x>"aDkk:s:\n:/
C<c-r>=<c-r>"
<esc>"bDkkqq@blha
<esc>q@a@q

```

Try it online!

takes input as 2 lines, returns the divisions on separate lines.

`a` is useful here to append a newline after the current character.
> 2 votes

# Answer
# Python 2, ~~77~~ 76 bytes

*-1 byte thanks to musicman523.*

```
def f(s,n):l=len(s);print[s[i:i+l/n]for i in range(0,l-n+1,l/n)]+[s[l-l%n:]]

```

Try it online!
> 1 votes

# Answer
# Ruby, 53 bytes

```
->s,n{a=s.scan(/.{,#{s.size/n}}/);[a[0,n],a[n,n]*'']}

```

Try it online!
> 1 votes

# Answer
# Haskell, ~~120~~ 88 bytes (thanks to Ørjan Johansen!)

Does `div` count as the division operator?

I am curious how I could cut this down, I haven't learned all the tricks yet.

```
q=splitAt;x!s|n<-div(length s)x,let g""=[];g s|(f,r)<-q n s=f:g r,(a,b)<-q(n*x)s=(g a,b)

```
> 1 votes

# Answer
# Mathematica, 58 bytes

```
{#~Partition~a,#2}&@@TakeDrop[#,(a=Floor[Length@#/#2])#2]&

```

Pure function taking a list of characters and a positive integer as input. For example, the last test case is called by

```
{#~Partition~a,#2}&@@TakeDrop[#,(a=Floor[Length@#/#2])#2]&[{"1","2","3","4","5","6","7"},4]

```

and returns:

```
{{{"1"}, {"2"}, {"3"}, {"4"}}, {"5", "6", "7"}}

```
> 1 votes

# Answer
## Ohm, 3 bytes (non-competing?)

```
lvσ

```

Non competing because the built-in isn't implemented yet in TIO and i have no PC handy to test whether it works in the latest pull in the repo.

~~Built-in ¯\\\\_(ツ)\_/¯. I used the wrong built-in... But hey there is still an other one laying around.~~ Now I used the wrong built-in two times (or one built-in works wrong with remainders).

Do I get bonus points because `v` is (floor) division?
> 1 votes

# Answer
# CJam, 16 bytes

```
{_,2$//_2$<@@>s}

```

Anonymous block expecting the arguments on the stack and leaves the result on the stack after.

Try it online!

### Explanation

Expects arguments as `number "string"`.

```
_,              e# Copy the string and get its length.
  2$            e# Copy the number.
    /           e# Integer divide the length by the number.
     /          e# Split the string into slices of that size.
      _         e# Copy the resulting array.
       2$       e# Copy the number.
         <      e# Slice the array, keeping only the first <number> elements.
          @@    e# Bring the number and original array to the top.
            >   e# Slice away the first <number> elements,
             s  e# and join the remaining elements into a string.

```
> 1 votes

# Answer
# , 26 bytes

```
(]$~[,(<.@%~#));]{.~0-(|#)

```

Apart from elminating spaces and intermediate steps, this hasn't been golfed. I expect that I've taken the long way somehow, what with my parentheses and argument references (`[` and `]`).

See Jupyter notebook for test cases, such as the following:

```
   5 chunk test2
┌──┬───┐
│He│ld!│
│ll│   │
│o,│   │
│ w│   │
│or│   │
└──┴───┘

```
> 1 votes

# Answer
# , ~~79~~ 63 bytes

*-16 from Giuseppe fixing the indexing*

```
function(s,n,k=nchar(s),l=k%/%n)substring(s,0:n*l+1,c(1:n*l,k))

```

Try it online!

Built around giving vector inputs to `substring()`
> 1 votes

# Answer
## JavaScript, 49 bytes

```
d=(s,n)=>s.match(eval(`/.{1,${0|s.length/n}}/g`))

```

Try It Online

```
d=(s,n)=>s.match(eval(`/.{1,${0|s.length/n}}/g`))

var ret = d("######.######..#####..########..##.##..##.##.....##.....######.######.##.....##..#####.....##.....##.....##...####.....##......####...######", 5);
for (var r in ret)
    console.log(ret[r]);
```
> 1 votes

# Answer
# Stax, 12 bytes

```
î╩╘30¥♂┴ÿ&╕¡

```

Run and debug it
> 1 votes

# Answer
# Japt `-P`, 8 bytes

```
òUÊzV)sV

```

Try it

```
òUÊzV)sV     :Implicit input of string U & integer V
ò            :Partitions of U of length
 UÊ          :  Length of U
   zV        :  Floor divided by V
     )       :End partition
      sV     :Slice off the first V elements
             :Implicitly join and output

```
> 1 votes

# Answer
# PowerShell v3+, 72, 80 bytes

Assumes `$s` contains the input string; `$n` contains the number of characters per "piece". This also assumes that "StrictMode" is off. Otherwise, an error would be returned because of indexing further into an array than actually exists (i.e. if array has 4 elements and i call the non-existent 5th element). With StrictMode off, PS doesn't care and it'll ignore the error.

```
for($i = 0;$i -le $s.Length;$i+=$n+1){-join($s|% ToCharA*)[$i..($i+$n)]}

```

Using notation `($s|% ToCharA*)` i was able to save 1 character compared to `$s.ToCharArray()` : )

## Update:

Updated code to actually satisfy challenges requirements. Again assumes `$s` contains the input string; however, this time `$n` contains the number of "pieces". The remainder is printed out last. And i used PowerShell's division operator

```
0..($n-1)|%{$p=[math]::Floor($s.length/$n)}{$s|% Su*($_*$p) $p}{$s|% Su*($n*$p)}

```

Try it online!
> 0 votes

# Answer
# PHP, 152 bytes

Thanks @JörgHülsermann (brackets tip!)

```
$c=$s=explode('|',readline());
while($s[1]--)$s[0]=preg_replace('/^'.($l[]=substr($s[0],0,strlen($c[0])/$c[1])).'/','',$s[0]);
$l[r]=$s[0];
print_r($l);

```

Try it online!
> 0 votes

# Answer
# Python 3, 94 bytes

```
i=input().split('|')
s,n=i[0],int(i[1])
c=len(s)//n
while n:print(s[:c]);s=s[c:];n-=1
print(s)

```

Try it online!
> 0 votes

# Answer
# Python 2, 57 bytes

```
def f(s,n):k=len(s)/n;print zip(*[iter(s)]*k)[:n],s[k*n:]

```

Try it online!
> 0 votes

# Answer
# Perl 5 `-pF`, 43 bytes

```
$p=@F/($q=<>);say substr$_,0,$p,''while$q--

```

Try it online!
> 0 votes

# Answer
# Forth (gforth), 64 bytes

```
: f >r i /mod rot r> 0 do over 2dup cr type + loop rot cr type ;

```

Try it online!

Ended up printing the strings newline-separated, since Forth doesn't have a native list format and newlines are cheaper than spaces

### Code Explanation

```
: f               \ start a new word definition
  >r              \ stick the divisor on the return stack (to get it out of the way)
  i /mod          \ get the quotient and remainder of dividing length by divisor
  rot             \ move the string starting-address to the top of the stack
  r> 0            \ move the divisor off the return stack and setup loop parameters
  do              \ loop from 0 to divisor  - 1
    over          \ copy the calculated substring-length to the top of the stack
    2dup          \ duplicate both address and substring-length
    cr            \ output a newline
    type          \ print a string of substring-length characters from the given address
    +             \ add the substring length to the current address
  loop            \ end the loop definition
  rot             \ move the remainder to the top of the stack
  cr type         \ output a newline and print the remaining remainder characters in the  string
;                 \ end the word definition

```
> 0 votes

# Answer
# Runic Enchantments, 32 bytes

```
:l͍i:},,r[\>i
/?)1l$,'$L
\]$ak@

```

Try it online!

Note that inputs are automatically coerced to the most appropriate value type (i.e. numbers will be cast to numerical values, which will not 'divide' correctly) and that inputs are separated by spaces. If you wish to include an input string that *contains* a space, it (and newlines) will need to be escaped (e.g. `Hello\ World!`)

Output is the groupings separated by `,`, followed by a new line, then the remainder (if any). As such, `,` and newlines in the input are not recommended (but will definitely display correctly).

## Explanation

The first line handles reading and parsing the inputs (reordered for legibility):

```
>              Entry point
 i:            Read string input, duplicate it
   l͍           Get its length
    i:         Get integer input, duplicate it
      ,,       Divide length by input, divide input string by grouping size (collect the bonus)
        r      Reverse the stack
         [     Pop the top N values to a new virtual stack (this value is the numerical input value)
          \    Enter output loop

          L    Top of the loop, sends IP to the left
         $     Print top of the stack (first substring)
      $,'      Push a , and print it
   )1l         Check if the length of the stack is >1
  ?            If true, skip next instruction (go top top of loop)
 /             If false, bounce to the last line

 \             Reflect IP to the right
  ]            Pop the virutal stack back to the top of the original stack
   $           Print the last substring
    ak         Push a newline
      @        Dump rest of the stack and terminate

```
> 0 votes

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


# Question
Title: Golf your finger-strokes in Flow Free: Warps
## Background

*Flow Free* is a series of puzzle games whose objective is to connect all the same-colored pairs of dots on the grid. *Flow Free: Warps* introduces the "warping" mechanic: a line connecting two dots can go through the border of the grid, which makes it re-enter through the opposite side of the grid (torus topology).

The following is an in-game screenshot of an initial grid and its complete solution, so that the readers can get some feel of the game.

Due to the warping nature, many of the lines should be drawn in multiple finger strokes. As in the screenshots, the game shows one-cell-wide extra border around the main grid whose cells act as "shadow" of the actual cells on the opposite side. The player can make any kind of moves on the shadow cells just like on the cells on the main grid.

The following shows the relationships between the shadow cells and their corresponding main cells on a 5x5 grid. Note that the shadow corner cells are also functional.

```
E5 | E1 E2 **E3 E4 E5** | **E1**
---+----------------+---
A5 | A1 A2 **A3** A4 A5 | A1
B5 | **B1 B2 B3**    B5 | B1
C5 | C1          C5 | C1
D5 | D1          D5 | D1
E5 | E1 E2 E3 E4 E5 | E1
---+----------------+---
A5 | A1 A2 A3 A4 A5 | A1
```

For example, the path `B1 B2 B3 A3 E3 E4 E5 E1` can be drawn in one finger stroke by starting at main B1 and going `>>^^>>>`, finishing at the top right corner shadow E1.

Additionally, the game has a convenience feature: if you drop your finger at the cell (orthogonally) adjacent to the destination cell, the line is auto-connected with it. For example, if the destination of the above path is D1 instead, drawing the line through B1 to E1 is enough to complete the line, so the path still takes one finger stroke. But this feature only works between two cells adjacent *when only the main cells are considered*, e.g. dropping your finger at B5 (either main or shadow) won't auto-connect to B1.

Under these mechanisms, every single line shown in the above screenshot takes just one finger stroke. Note that you can start at either side of the line, and you can start or extend the line at any equivalent cell (out of the main and shadow cells).

To be precise, the player can do one of the following actions in one finger stroke:

* First stroke: Start drawing a line from one of the two dots, and draw it as far as possible, and release.
* Second and subsequent strokes: start drawing at the cell (or any of its shadows) where the last stroke stopped, and extend the line as far as possible, and release.

## Challenge

Given the description of a line on a grid of *Flow Free: Warps*, determine how many finger strokes will be needed to complete the line.

The line can be taken as input in a suitable, clear format. If the input is `B4 - B1 - B2 - A2 - D2` on a 4x4 grid, the following (and the respective equivalents according to Default I/O) are allowed:

* An ordered list of coordinates: `[(2, 4), (2, 1), (2, 2), (1, 2), (4, 2)]`
* A 2D grid where the path is marked with successive integers: `[[0, 4, 0, 0], [2, 3, 0, 1], [0, 0, 0, 0], [0, 5, 0, 0]]`

If you want to use a different input format, please ask in comments.

The line will always be valid in the following sense:

* It has a well-defined start cell and an end cell.
* Each adjacent pair of cells within the path are orthogonally adjacent on the grid, potentially through the border.

You can further assume the grid is rectangular and has at least 4 rows and 4 columns. The grid may be non-square.

You are *not* allowed to assume that the path does not touch itself. Many levels in the game contain some thin walls, which make some paths touch themselves by going through both sides of such walls.

Standard rules apply. The shortest code in bytes wins.

## Test cases

Since a line on a grid can be represented in multiple different ways, the test cases are presented in a visually clear style.

```
Input:
[[ 1, 2, 3, 4 ],
 [ 8, 7, 6, 5 ],
 [ 0, 0, 0, 0 ],
 [ 0, 0, 0, 0 ]]
Output: 1

Input:
[[ 1, 2, 0, 0 ],
 [ 0, 0, 0, 0 ],
 [ 7, 8, 5, 6 ],
 [ 0, 3, 4, 0 ]]
Output: 1 (start at bottom shadow of 1 and release finger at shadow 7)

Input:
[[ 0, 0, 0, 0 ],
 [ 3, 4, 1, 2 ],
 [ 6, 5, 8, 7 ],
 [ 0, 0, 0, 0 ]]
Output: 2

Input:
[[ 0, 0, 0, 0 ],
 [ 3, 4, 1, 2 ],
 [ 6, 5, 0, 7 ],
 [ 0, 0, 0, 0 ]]
Output: 1 (start at shadow 7 and release finger at shadow 2)

Input:
[[ 7, 8, 9, 0, 0, 0 ],
 [ 0, 0, 0, 1, 2, 3 ],
 [ 5, 0, 0, 0, 0, 4 ],
 [ 6, 0, 0, 0, 0, 0 ]]
Output: 2 (first stroke can only go to 1..7 or 9..3)

Input:
[[ 0, 0, 4, 5,  0,  9 ],
 [ 0, 0, 0, 6,  7,  8 ],
 [ 0, 1, 0, 0,  0,  0 ],
 [ 0, 2, 3, 0, 11, 10 ]]
Output: 1 (start at shadow 11 and release at shadow 2)

Input:
[[ 0, 0, 5, 0, 9, 0,15, 0,19 ],
 [24,25, 6, 7, 8, 0,16,17,18 ],
 [23, 1, 0, 0, 0, 0, 0, 0, 0 ],
 [22, 2, 3, 0,11,12,13, 0,21 ],
 [ 0, 0, 4, 0,10, 0,14, 0,20 ]]
Output: 5

```

# Answer
# JavaScript (ES7), 194 bytes

Expects `(list, width, height)`, where `list` is an ordered list of 0-indexed coordinates.

```
(p,w,h)=>(m=g=([c,...p],N,X=-3,Y=X)=>1/X/Y?c?[0,1,2,3].map(k=>g(p,(X-([x,y]=c,P=k&1?x?~x+w?g:-1:w:x))**2<2&(Y-(Q=k&2?y?~y+h?g:-1:h:y))**2<2|!(p+p||k)?N:-~N,P,Q)):N>m?0:m=N:0)(p)|g(p.reverse())|m

```

Try it online!

### How?

As illustrated below, there are up to 4 distinct ways of selecting some cells in the grid: the original position **P** and 3 shadow positions **S**.

```
 . | . . . | .
---+-------+---
 . | P . . | S
 . | . . . | .
 . | . . . | .
---+-------+---
 . | S . . | S

```

The loop `[0,1,2,3].map(k=>...)` attempts to do one recursive call per possibility. However, if a given shadow is invalid, at least one of the coordinates will be set to a non-numeric value, causing the search to be aborted early thanks to the test `1/X/Y`.

We keep track of the current number of strokes in `N` and the minimum number of strokes in `m`.

If the last position used is not a shadow, the corresponding stroke is never counted, even if it's not adjacent to the penultimate position. The test is `|!(p+p||k)`.

Two searches are executed: from first to last point and from last to first point.
> 3 votes

---
Tags: code-golf, grid
---