title: Return the Closest Prime Number

text:
# Question
Title: Return the Closest Prime Number
# Challenge

This is a simple one: Given a positive integer up to 1,000,000, return the closest prime number.

If the number itself is prime, then you should return that number; if there are two primes equally close to the provided number, return the lower of the two.

Input is in the form of a single integer, and output should be in the form of an integer as well.

I don't care *how* you take in the input (function, STDIN, etc.) or display the output (function, STDOUT, etc.), as long as it works.

This is code golf, so standard rules apply—the program with the least bytes wins!

# Test Cases

```
Input  =>  Output
------    -------
80     =>      79
100    =>     101
5      =>       5
9      =>       7
532    =>     523
1      =>       2

```

# Answer
# Gaia, 3 bytes

```
ṅD⌡

```

Try it online!

Rather slow for large inputs, but works given enough memory/time.

I'm not sure why `D⌡` implicitly pushes `z` again, but it makes this a remarkably short answer!

```
ṅ	| implicit input z: push first z prime numbers, call it P
 D⌡	| take the absolute difference between P and (implicit) z,
	| returning the smallest value in P with the minimum absolute difference

```
> 9 votes

# Answer
# JavaScript (ES6), 53 bytes

```
n=>(g=(o,d=N=n+o)=>N%--d?g(o,d):d-1?g(o<0?-o:~o):N)``

```

Try it online!

### Commented

```
n => (            // n = input
  g = (           // g = recursive function taking:
    o,            //   o = offset
    d =           //   d = current divisor, initialized to N
    N = n + o     //   N = input + offset
  ) =>            //
    N % --d ?     // decrement d; if d is not a divisor of N:
      g(o, d)     //   do recursive calls until it is
    :             // else:
      d - 1 ?     //   if d is not equal to 1 (either N is composite or N = 1):
        g(        //     do a recursive call with the next offset:
          o < 0 ? //       if o is negative:
            -o    //         make it positive (e.g. -1 -> +1)
          :       //       else:
            ~o    //         use -(o + 1) (e.g. +1 -> -2)
        )         //     end of recursive call
      :           //   else (N is prime):
        N         //     stop recursion and return N
)``               // initial call to g with o = [''] (zero-ish)

```
> 14 votes

# Answer
# 05AB1E, 5 bytes

```
Åps.x

```

Try it online! or as a Test Suite

Inefficient for big numbers
> 10 votes

# Answer
# Octave, 40 bytes

```
@(n)p([~,k]=min(abs(n-(p=primes(2*n)))))

```

**Try it online!**

This uses the fact that there is always a prime between `n` and `2*n` (Bertrand–Chebyshev theorem).

### How it works

```
@(n)p([~,k]=min(abs(n-(p=primes(2*n)))))

@(n)                                      % Define anonymous function with input n
                       p=primes(2*n)      % Vector of primes up to 2*n. Assign to p
                abs(n-(             ))    % Absolute difference between n and each prime
      [~,k]=min(                      )   % Index of first minimum (assign to k; not used)
    p(                                 )  % Apply that index to p

```
> 8 votes

# Answer
# Japt, 5 bytes

```
_j}cU

```

Try it or run all test cases

```
_j}cU     :Implicit input of integer U
_         :Function taking an integer as an argument
 j        :  Test if integer is prime
  }       :End function
   cU     :Return the first integer in [U,U-1,U+1,U-2,...] that returns true

```
> 6 votes

# Answer
# Wolfram Language (Mathematica), 31 bytes

```
Nearest[Prime~Array~78499,#,1]&

```

Try it online!

```
                              & (*pure function*)
        Prime~Array~78499       (*among the (ascending) first 78499 primes*)
                            1   (*select one*)
Nearest[                 ,#, ]  (*which is nearest to the argument*)

```

1000003 is the 78499th prime. `Nearest` prioritizes values which appear earlier in the list (which are lower).
> 6 votes

# Answer
# Jelly, ~~9~~ 7 bytes

```
ḤÆRạÞµḢ

```

Try it online!

Slow for larger input, but works ok for the requested range. Thanks to @EriktheOutgolfer for saving 2 bytes!
> 5 votes

# Answer
# Python 2, 71 bytes

```
f=lambda n,k=1,p=1:k<n*3and min(k+n-p%k*2*n,f(n,k+1,p*k*k)-n,key=abs)+n

```

Try it online!

A recursive function that uses the Wilson's Theorem prime generator. The product `p` tracks \\$(k-1)!^2\\$, and `p%k` is 1 for primes and 0 for non-primes. To make it easy to compare `abs(k-n)` for different primes `k`, we store `k-n` and compare via `abs`, adding back `n` to get the result `k`.

The expression `k+n-p%k*2*n` is designed to give `k-n` on primes (where `p%k=1`), and otherwise a "bad" value of `k+n` that's always bigger in absolute value and so doesn't affect the minimum, so that non-primes are passed over.
> 5 votes

# Answer
# 05AB1E, 4 bytes

```
z-Ån

```

Try it online!
> 5 votes

# Answer
# Brachylog, ~~7~~ 5 bytes

```
;I≜-ṗ

```

Try it online!

Saved 2 bytes thanks to @DLosc.

### Explanation

```
;I≜      Label an unknown integer I (tries 0, then 1, then -1, then 2, etc.)
   -     Subtract I from the input
    ṗ    The result must be prime

```
> 5 votes

# Answer
# C (gcc), ~~87~~ ~~76~~ ~~74~~ 72 bytes

Optimization of innat3's C# (Visual C# Interactive Compiler), 100 bytes

```
f(n,i,t,r,m){for(t=0,m=n;r-2;t++)for(r=i=1,n+=n<m?t:-t;i<n;n%++i||r++);}

```

Try it online!
> 5 votes

# Answer
# Pyth, 10 bytes

```
haDQfP_TSy

```

Try it online here, or verify all the test cases at once here.

```
haDQfP_TSyQ   Implicit: Q=eval(input())
              Trailing Q inferred
         yQ   2 * Q
        S     Range from 1 to the above
    f         Filter keep the elements of the above, as T, where:
     P_T        Is T prime?
  D           Order the above by...
 a Q          ... absolute difference between each element and Q
                This is a stable sort, so smaller primes will be sorted before larger ones if difference is the same
h             Take the first element of the above, implicit print

```
> 4 votes

# Answer
# C, ~~122~~ ~~121~~ 104 bytes

```
p(a,i){for(i=1;++i<a;)if(a%i<1)return 0;return a>1;}c(a,b){for(b=a;;b++)if(p(--a)|p(b))return p(b)?b:a;}

```

Use it calling function `c()` and passing as argument the number; it should return the closest prime.

Thanks to Embodiment of Ignorance for ~~1 byte saved~~ a big improvement.

Try it online!
> 4 votes

# Answer
# Factor, 91 bytes

```
: p ( x -- x ) [ nprimes ] keep dupd [ - abs ] curry map swap zip natural-sort first last ;

```

Try it online!
> 4 votes

# Answer
# Perl 6, 35 bytes

```
{$_+=($*=-1)*$++until .is-prime;$_}

```

Try it online!

This uses Veitcel's technique for generating the list of `0, -1, 2, -3` but simplifies it greatly to `($*=-1)*$++` using the anonymous state variables available in P6 (I originally had `-1 ** $++ * $++`, but when golfed the negative loses precedence). There's a built in prime checker but unfortunately the `until` prevents the automagically returned value so there's an extra `$_` hanging around.
> 4 votes

# Answer
# Wolfram Language (Mathematica), 52 bytes

```
If[PrimeQ[s=#],s,#&@@Nearest[s~NextPrime~{-1,1},s]]&

```

Try it online!
> 3 votes

# Answer
# Python 2 (Cython), 96 bytes

```
l=lambda p:min(filter(lambda p:all(p%n for n in range(2,p)),range(2,p*3)),key=lambda x:abs(x-p))

```

Try it online!
> 3 votes

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

Tacit prefix function inspired by Galen Ivanov's J answer.

```
⊢(⊃⍋⍤|⍤-⊇⊢)¯2⍭⍳

```

Try it online!

**ɩ**ndices one through the argument.

`¯2⍭` nth primes of that

`⊢(``)` apply the following tacit function to that, with the original argument as left argument:

the primes

indexed by:

the ascending grade (indices which would sort ascending)
of
`|` the magnitude (absolute value)
of
`-` the differences

pick the first one (i.e. the one with smallest difference)
> 3 votes

# Answer
# Tidy, 43 bytes

```
{x:(prime↦splice(]x,-1,-∞],[x,∞]))@0}

```

Try it online!

## Explanation

This is a lambda with parameter `x`. This works by creating the following sequence:

```
[x - 1, x, x - 2, x + 1, x - 3, x + 2, x - 4, x + 3, ...]

```

This is splicing together the two sequences `]x, -1, -∞]` (left-closed, right-open) and `[x, ∞]` (both open).

For `x = 80`, this looks like:

```
[79, 80, 78, 81, 77, 82, 76, 83, 75, 84, 74, 85, ...]

```

Then, we use `f↦s` to select all elements from `s` satisfying `f`. In this case, we filter out all composite numbers, leaving only the prime ones. For the same `x`, this becomes:

```
[79, 83, 73, 71, 89, 67, 97, 61, 59, 101, 103, 53, ...]

```

Then, we use `(...)@0` to select the first member of this sequence. Since the lower of the two needs to be selected, the sequence which starts with `x - 1` is spliced in first.

Note: Only one of `x` and `x - 1` can be prime, so it is okay that the spliced sequence starts with `x - 1`. Though the sequence could be open on both sides (`[x,-1,-∞]`), this would needlessly include `x` twice in the sequence. So, for sake of "efficiency", I chose the left-closed version (also because I like to show off Tidy).
> 3 votes

# Answer
## C# (Visual C# Interactive Compiler), ~~104~~ 100 bytes

```
n=>{int r=0,t=0,m=n;while(r!=2){n+=(n<m)?t:-t;t++;r=0;for(int i=1;i<=n;i++)if(n%i==0)r++;}return n;}

```

Try it online!

**Explanation:**

```
int f(int n)
{
    int r = 0; //stores the amount of factors of "n"
    int t = 0; //increment used to cover all the integers surrounding "n"
    int m = n; //placeholder to toggle between adding or substracting "t" to "n"

    while (r != 2) //while the amount of factors found for "n" is different to 2 ("1" + itself)
    {
        n += (n < m) ? t : -t; //increment/decrement "n" by "t" (-0, -1, +2, -3, +4, -5,...)
        t++;
        r = 0;
        for (int i = 1; i <= n; i++) //foreach number between "1" and "n" increment "r" if the remainder of its division with "n" is 0 (thus being a factor)
            if (n % i == 0) r++;
    }
    return n;
}

Console.WriteLine(f(80)); //79

```
> 3 votes

# Answer
# VDM-SL, 161 bytes

```
f(i)==(lambda p:set of nat1&let z in set p be st forall m in set p&abs(m-i)>=abs(z-i)in z)({x|x in set{1,...,9**7}&forall y in set{2,...,1003}&y<>x=>x mod y<>0})

```

A full program to run might look like this - it's worth noting that the bounds of the set of primes used should probably be changed if you actually want to run this, since it will take a long time to run for 1 million:

```
functions
f:nat1+>nat1
f(i)==(lambda p:set of nat1&let z in set p be st forall m in set p&abs(m-i)>=abs(z-i)in z)({x|x in set{1,...,9**7}&forall y in set{2,...,1003}&y<>x=>x mod y<>0})

```

### Explanation:

```
f(i)==                                        /* f is a function which takes a nat1 (natural number not including 0)*/
(lambda p:set of nat1                         /* define a lambda which takes a set of nat1*/
&let z in set p be st                         /* which has an element z in the set such that */
forall m in set p                             /* for every element in the set*/
&abs(m-i)                                     /* the difference between the element m and the input*/
>=abs(z-i)                                    /* is greater than or equal to the difference between the element z and the input */
in z)                                         /* and return z from the lambda */
(                                             /* apply this lambda to... */
{                                             /* a set defined by comprehension as.. */
x|                                            /* all elements x such that.. */
x in set{1,...,9**7}                          /* x is between 1 and 9^7 */
&forall y in set{2,...,1003}                  /* and for all values between 2 and 1003*/
&y<>x=>x mod y<>0                             /* y is not x implies x is not divisible by y*/
}
)

```
> 2 votes

# Answer
# APL(NARS), 38 chars, 76 bytes

```
{⍵≤1:2⋄0π⍵:⍵⋄d←1π⍵⋄(d-⍵)≥⍵-s←¯1π⍵:s⋄d}

```

0π is the test for prime, ¯1π the prev prime, 1π is the next prime; test:

```
  f←{⍵≤1:2⋄0π⍵:⍵⋄d←1π⍵⋄(d-⍵)≥⍵-s←¯1π⍵:s⋄d}
  f¨80 100 5 9 532 1
79 101 5 7 523 2

```
> 2 votes

# Answer
# , ~~19~~ 15 bytes

```
(0{]/:|@-)p:@i.

```

Try it online!
> 2 votes

# Answer
# Perl 5, 57 bytes

```
$a=0;while((1x$_)=~/^.?$|^(..+?)\1+$/){$_+=(-1)**$a*++$a}

```

Try it online!

`/^.?$|^(..+?)\1+$/` is tricky regexp to check prime

`(-1)**$a*++$a` generate sequence 0,-1, 2,-3 ...
> 2 votes

# Answer
# MathGolf, 10 bytes

```
∞╒g¶áÅ-±├Þ

```

Try it online.

**Explanation:**

```
∞            # Double the (implicit) input-integer
 ╒           # Create a list in the range [1, 2*n]
  g¶         # Filter so only the prime numbers remain
    áÅ       # Sort this list using the next two character:
      -±     #  The absolute difference with the (implicit) input-integer
        ├    # Push the first item of the list
             # (unfortunately without popping the list itself, so:)
         Þ   # Discard everything from the stack except for the top
             # (which is output implicitly as result)

```
> 2 votes

# Answer
# Haskell, ~~79~~ 74 bytes (thanks to Laikoni)

72 bytes as annonymus function (the initial "f=" could be removed in this case).

```
f=(!)(-1);n!x|x>1,all((>0).mod x)[2..x-1]=x|y<-x+n=last(-n+1:[-n-1|n>0])!y

```

Try it online!

---

### original code:

```
f=(!)(-1);n!x|x>1&&all((>0).mod x)[2..x-1]=x|1>0=(last$(-n+1):[-n-1|n>0])!(x+n)

```

Try it online!

**Explanation:**

```
f x = (-1)!x

isPrime x = x > 1 && all (\k -> x `mod` k /= 0)[2..x-1]
n!x | isPrime x = x            -- return the first prime found
    | n>0       = (-n-1)!(x+n) -- x is no prime, continue with x+n where n takes the
    | otherwise = (-n+1)!(x+n) -- values -1,2,-3,4 .. in subsequent calls of (!)

```
> 2 votes

# Answer
# Java (JDK), 103 bytes

```
n->{int p=0,x=0,z=n,d;for(;p<1;p=p>0?z:0,z=z==n+x?n-++x:z+1)for(p=z/2,d=1;++d<z;)p=z%d<1?0:p;return p;}

```

Try it online!
> 2 votes

# Answer
# Java 8, ~~88~~ 87 bytes

```
n->{for(int c=0,s=0,d,N=n;c!=2;s++)for(c=d=1,n+=n<N?s:-s;d<n;)if(n%++d<1)c++;return n;}

```

Port of *@NaturalNumberGuy*'s (first) C answer, **so make sure to upvote him!!**
-1 byte thanks to *@OlivierGrégoire*.

Try it online.

**Explanation:**

```
n->{               // Method with integer as both parameter and return-type
  for(int c=0,     //  Counter-integer, starting at 0
          s=0,     //  Step-integer, starting at 0 as well
          d,       //  Divisor-integer, uninitialized
          N=n;     //  Copy of the input-integer
      c!=2;        //  Loop as long as the counter is not exactly 2 yet:
      s++)         //    After every iteration: increase the step-integer by 1
    for(c=d=1,     //   (Re)set both the counter and divisor to 1
        n+=n<N?    //   If the input is smaller than the input-copy:
            s      //    Increase the input by the step-integer
           :       //   Else:
            -s;    //    Decrease the input by the step-integer
        d<n;)      //   Inner loop as long as the divisor is smaller than the input
      if(n%++d     //    Increase the divisor by 1 first with `++d`
              <1)  //    And if the input is evenly divisible by the divisor:
        c++;       //     Increase the counter-integer by 1
  return n;}       //  Return the now modified input-integer as result

```
> 2 votes

# Answer
# MATL, 6 bytes

```
t:YqYk

```

Try it online!

List the first `n` primes and find the one closest to `n`.
> 2 votes

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

```
g=>Enumerable.Range(2,2<<20).Where(x=>Enumerable.Range(1,x).Count(y=>x%y<1)<3).OrderBy(x=>Math.Abs(x-g)).First()

```

Try it online!

Left shifts by 20 in submission but 10 in TIO so that TIO terminates for test cases.
> 1 votes

# Answer
**Swift, 186 bytes**

```
func p(a:Int){let b=q(a:a,b:-1),c=q(a:a,b:1);print(a-b<=c-a ? b:c)}
func q(a:Int,b:Int)->Int{var k=max(a,2),c=2;while k>c && c != a/2{if k%c==0{k+=b;c=2}else{c=c==2 ? c+1:c+2}};return k}

```

Try it online!
> 1 votes

# Answer
# Jelly, 14 bytes

```
ÆpæRÆnạÞƲ2>?2Ḣ

```

Try it online!
> 1 votes

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

```
n=>{int i=0;for(;n<2||Enumerable.Range(2,n-2).Any(x=>n%x<1);n+=++i%2<1?-i:i);return n;}

```

Try it online!
> 1 votes

# Answer
# Python 2, 93 bytes

```
lambda n:sorted(range(1,3*n),key=lambda x:abs(x-n)if all(x%k for k in range(2,x))else 2*n)[0]

```
> 1 votes

# Answer
# Zsh, ~~101 92 91~~ 90 bytes

*-9 by collapsing the body into the head of `p`'s loop, -1 from using `i=j` instead of `i=$1` in main loop, -1 by replacing a `&&` with a `,`.*

```
p(){for ((n=2;n<$1&&$1%n++;)):
(($1==n))&&<<<$1}
j=$1
for ((i=j;;++j,--i))p $i||p $j&&exit

```

~~Try it online!~~ ~~Try it online!~~ Try it online!

~~57~~ 48 bytes to the prime testing function, ~~43~~ 41 bytes to the main loop (1 byte to the newline between them):

```
p(){  # prime function: takes one input, outputs via return code
for (( n = 2; n < $1 && $1 % n++; ))   # divisibility check in loop header
    :                 # no-op loop body
(( $1 == n )) &&      # if we looped up to $1:
    <<< $1            #     echo out $1. Otherwise, this will return false
}

```

For the last condition, we can't use the shorter `(($1-n))||`, because we need to return false to the main loop if we didn't find a prime. We print in the function to avoid complexity in the main loop.

```
j=$1                          # set i = j = $1. Doing one in and one out is smallest
for (( i = j; ; ++j , --i )) # loop indefinitely, increment and decrement
    p $i || p $j && exit      # if either $i or $j was a prime, exit

```

Conditionals are left-associative, which we take advantage of here. We do test the starting number twice to make the decrement logic simpler.
> 1 votes

# Answer
# TSQL query, 155 bytes

```
USE master
DECLARE @ INT=1000000;

WITH C as(SELECT abs(number-500+@)r,abs(number)+2s
FROM spt_values)SELECT top 1r FROM c
WHERE 0not in(SELECT c.r%s FROM c d
WHERE c.r>s)ORDER BY abs(r-@),r

```

**Try it online**
> 1 votes

# Answer
# Ruby, 67 bytes

```
def p n;n.prime?;end;def a b,c=0;p(b-c)?b-c:p(b+c)?b+c:a(b,c+1);end

```

Try it online!
> 1 votes

# Answer
# C (gcc), ~~78~~ 65 bytes

```
f(n,i,j){for(i=j=0;j-1;i++)for(j=n+=i%2?-i:i;--j,n-1&&n%j;);i=n;}

```

Try it online!

```
f(n,i,j){
    for(i=j=0;j-1;i++)      //while j!=1
        for(j=n+=i%2?-i:i;  // step to next closest value to original input n
            --j,n-1&&n%j;); // find greatest factor which is less than j
    i=n;                    //return
}

```
> 1 votes

# Answer
# Ruby `-rprime`, 39 bytes

Relies on the idea that for any positive integer \\$n\\$, the \\$n\\$th prime is always larger than \\$n\\$.

```
->n{Prime.take(n).min_by{|i|(i-n).abs}}

```

Try it online!
> 1 votes

# Answer
# Wolfram Language (Mathematica), 22 bytes

```
RiemannR/*Round/*Prime

```

Try it online!

This is an approximate solution that by chance works for all of the given test cases, but gives a slightly wrong result for other inputs. The Riemann R function is an approximation of the prime-counting function, which we round to the nearest integer and then request the prime number of that index.
> 1 votes

# Answer
# TI-BASIC (TI-84+), 74 Bytes

```
Ans→A:{2,3→A:For(P,5,2A,2:If min(remainder(P,seq(X,X,3,1+√(P),2:P→∟A(1+dim(∟A:End:abs(A-∟A:∟A(1+sum(not(cumSum(Ans=min(Ans

```

**Hexdump:**
(Token hex-values found here.)

```
72 04 41 3E 08 32 2B 33 04 41 3E D3 50 2B 35 2B | Ans→A:{2,3→A:For(P,5,
32 41 2B 32 3E CE 1A EF 32 50 2B 23 58 2B 58 2B | 2A,2:If min(remainder(P,seq(X,X,
33 2B 31 70 BC 50 11 2B 32 3E 50 04 EB 41 10 31 | 3,1+√(P),2:P→∟A(1
70 B5 EB 41 3E D4 EE B2 41 71 EB 41 3E EB 41 10 | +dim(∟A:End:abs(A-∟A:∟A(
31 70 B6 B8 BB 29 72 6A 1A 72                   | 1+sum(not(cumSum(Ans=min(Ans

```

Input is an integer in `Ans`. Output is printed implicitly.
*Note:* due to limitations on how large lists can be, \\$A\\$ is limited to \\$0 \le A \le 3953\\$

**Explanation:**

```
Ans→A                                  ;store the input in a variable called "A"
{2,3→A                                 ;store the list {2 3} into a list called "A"
For(P,5,2A,2                           ;loop from 5 to two times the input using a step
                                       ; of 2
                   seq(X,X,3,1+√(P),2  ;generate a list of integers from 3 to 1 + the
                                       ; square root of the loop counter using a step of 2
                                       ; (e.g. P=21, list={3 5})
       remainder(P,                    ;then take the loop counter modulo each element
                                       ; (e.g. P=21, list={0 1})
If min(                                ;if all of the resulting elements are non-zero,
                                       ; then
P→∟A(1+dim(∟A                          ;add the loop counter's value to the list "A", the
                                       ; list of primes
End
abs(A-∟A                               ;subtract the input from the primes list and take
                                       ; the absolute value of each element (distance to
                                       ; each prime)
   1+sum(not(cumSum(Ans=min(Ans        ;find the first index of the minimum value
∟A(                                    ;then use that index to get the value in the primes
                                       ; list at that index
                                       ;implicit output

```

**Examples:**

```
100:prgmCDGF1F
             101
5:prgmCDGF1F
               5
80:prgmCDGF1F
              79

```
> 1 votes

# Answer
# Thunno 2 `h`, 4 bytes

```
Æpþṛ

```

Try it online!

#### Explanation

```
Æpþṛ  # Implicit input
Æp    # First n primes
  þṛ  # Sort by absolute difference
      # (Lower numbers will appear
      #  first in case of a tie)
      # Implicit output of first item

```
> 1 votes

# Answer
# Nekomata \+ `-1`, 3 bytes

```
Ž-Q

```

Attempt This Online!

```
Ž-Q
Ž       Find an integer (in the order of 0, 1, -1, 2, -2, 3, -3, ...)
 -      Input minus that integer
  Q     Check if the result is a prime

```

`-1` prints the first solution.
> 1 votes

---
Tags: code-golf, primes
---


# Question
Title: Construct a line graph / conjugate graph
# Introduction

Given an undirected graph G, we can construct a graph L(G) (called the line graph or conjugate graph) that represents the connections between edges in G. This is done by creating a new vertex in L(G) for every edge in G and connecting these vertices if the edges they represent have a vertex in common.

Here's an example from Wikipedia showing the construction of a line graph (in green).

As another example, take this graph G with vertices A, B, C, and D.

```
    A
    |
    |
B---C---D---E

```

We create a new vertex for each edge in G. In this case, the edge between A and C is represented by a new vertex called AC.

```
   AC

 BC  CD  DE

```

And connect vertices when the edges they represent have a vertex in common. In this case, the edges from A to C and from B to C have vertex C in common, so vertices AC and BC are connected.

```
   AC
  /  \
 BC--CD--DE

```

This new graph is the line graph of G!

See Wikipedia for more information.

# Challenge

Given the adjacency list for a graph G, your program should print or return the adjacency list for the line graph L(G). This is code-golf, so the answer with the fewest bytes wins!

### Input

A list of pairs of strings representing the the edges of G. Each pair describes the vertices that are connected by that edge.

* Each pair (X,Y) is guaranteed to be unique, meaning that that the list will not contain (Y,X) or a second (X,Y).

For example:

```
[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")]
[("D","E"),("C","D"),("B","C"),("A","C")]

```

### Output

A list of pairs of strings representing the the edges of L(G). Each pair describes the vertices that are connected by that edge.

* Each pair (X,Y) must be unique, meaning that that the list will not contain (Y,X) or a second (X,Y).
* For any edge (X,Y) in G, the vertex it creates in L(G) must be named XY (the names are concatenated together in same order that they're specified in the input).

For example:

```
[("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]
[("DE","CD"),("CD","CB"),("CD","CA"),("BC","AB")]

```

### Test Cases

```
[] -> []

[("0","1")] -> []

[("0","1"),("1","2")] -> [("01","12")]

[("a","b"),("b","c"),("c","a")] -> [("ab","bc"),("bc","ca"),("ca","ab")]

[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")] -> [("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]

```

# Answer
> 4 votes
# K (ngn/k), ~~45 39 33 29 30 35~~ *and five years later:* 31 bytes

```
(*'<:')#(3=#'?',/')#+{x@!2##x}@

```

Try it online!

`{` `}@` apply a function with implicit argument `x`

`#x` length

`2#` repeat twice

`!2##x` pairs of indices in `x` (the columns of a 2 by `#x` matrix)

`x@` index into `x`

`+` transpose

`(` `)#` filter

`(3=#'?',/')#` filter only those pairs whose concatenation (`,/`) has a count (`#`) of exactly 3 unique (`?`) elements

This removes edges like `("ab";"ab")` and `("ab";"cd")` from the list.

`(*'>:')#` filter only those pairs whose sort-descending permutation (`>`) starts with (`*`) a 1 (non-0 is boolean true)

In our case, the sort-descending permutation could be `0 1` or `1 0`.

# Answer
> 4 votes
# Brachylog, 13 bytes

```
{⊇Ċ.c¬≠∧}ᶠcᵐ²

```

Try it online!

With all test cases

*(-1 byte replacing `l₂` with `Ċ`, thanks to @Fatalize.)*

```
{⊇Ċ.c¬≠∧}ᶠcᵐ²   Full code
{       }ᶠ      Find all outputs of this predicate:
 ⊇Ċ.             A two-element subset of the input
    c            which when its subarrays are concatenated
     ¬≠          does not have all different elements
                 (i.e. some element is repeated)
       ∧         (no further constraint on output)
          cᵐ²   Join vertex names in each subsubarray in that result

```

# Answer
> 2 votes
## Ruby, 51 bytes

```
->a{a.combination(2){|x,y|p [x*'',y*'']if(x&y)[0]}}

```

Try it online!

For each combination of two edges, if they have a vertex in common (i.e. if the first element of their intersection is non-`nil`), print an array containing the two edges to STDOUT.

# Answer
> 2 votes
# Jelly, 5 bytes

```
Œcf/Ƈ

```

Try it online!

# Answer
> 2 votes
## JavaScript (Firefox 30-57), 77 bytes

```
a=>[for(x of a=a.map(x=>x.join``))for(y of a)if(x<y&&x.match(`[${y}]`))[x,y]]

```

Assumes all inputs are single letters (well, any single character other than `^` and `]`).

# Answer
> 1 votes
# C (gcc), 173 bytes

Input `i` and output `o` are flat, null-terminated arrays. Output names can be up to 998 characters long before this will break.

```
#define M(x)o[n]=malloc(999),sprintf(o[n++],"%s%s",x[0],x[1])
f(i,o,j,n,m)char**i,**j,**o;{for(n=0;*i;i+=2)for(j=i;*(j+=2);)for(m=4;m--;)strcmp(i[m/2],j[m%2])||(M(i),M(j));}

```

Try it online!

# Answer
> 1 votes
# MATL, 13 bytes

```
2XN!"@Y:X&n?@

```

Try it online!

Not as bad as I expected given cell array input. Basically the same idea as @Doorknob's Ruby answer.

```
2XN   % Get all combinations of 2 elements from the input
!     % Transpose
"     % Iterate over the columns (combinations)
@     % Push the current combination of edges
Y:    % Split it out as two separate vectors
X&n   % Get the number of intersecting elements between them
?@    % If that's non-zero, push the current combination on stack
      % Implicit loop end, valid combinations collect on the stack
      %  and are implicitly output at the end

```

# Answer
> 1 votes
# Mathematica 23 bytes

```
EdgeList[LineGraph[#]]&

```

Example: `g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 2 <-> 4 }]`

```
EdgeList@LineGraph[g]

```

(\*

{2 \<-\> 1, 3 \<-\> 2, 4 \<-\> 1, 4 \<-\> 2, 4 \<-\> 3}

\*)

# Answer
> 1 votes
# Python 2, 109 bytes

```
lambda a:[(s,t)for Q in[[''.join(p)for p in a if x in p]for x in set(sum(a,()))]for s in Q for t in Q if s<t]

```

Try it online!

For each node `x` (discovered by making a set from the flattened list of edges), make a list of the pairs `p` that have `x` as a member; then, for each of those lists `Q`, find the unique, distinct pairings within `Q` (uniqueness/distinction is enforced via `if s<t`).

# Answer
> 1 votes
# Scala, 145 bytes

Modified from @Doorknob's Ruby answer.

---

Golfed version. Try it online!

```
def f(a:Seq[Seq[String]])=a.combinations(2).foreach{case List(x,y)=>if(x.intersect(y).nonEmpty)println(s"[${x.mkString("")},${y.mkString("")}]")}

```

Ungolfed version. Try it online!

```
object Main {
  def main(args: Array[String]): Unit = {
    val f: List[List[String]] => Unit = (a: List[List[String]]) => {
      a.combinations(2).foreach { case List(x, y) =>
        if (x.intersect(y).nonEmpty) println(s"[${x.mkString("")}, ${y.mkString("")}]")
      }
    }

    val inputList: List[List[List[String]]] = List(
      List(),
      List(List("0", "1")),
      List(List("0", "1"), List("1", "2")),
      List(List("a", "b"), List("b", "c"), List("c", "a")),
      List(List("1", "2"), List("1", "3"), List("1", "4"), List("2", "5"), List("3", "4"), List("4", "5"))
    )

    inputList.foreach { arr =>
      println(s"Input: $arr")
      println("Output:")
      f(arr)
      println()
    }
  }
}

```

# Answer
> 1 votes
# Nekomata, 8 bytes

```
S:đ∩z¿ᵐj

```

Attempt This Online!

A port of @Sundar R's Brachylog answer

```
S:đ∩z¿ᵐj
S           Find a subset of the input
 :   ¿      Check that:
  đ             the subset has exactly two elements
   ∩            and the intersection of the two elements
    z           has exactly one element
      ᵐj    Join each element of the subset

```

Nekomata will find all solutions, which are all the edges of the edge graph.

# Answer
> 0 votes
# Wolfram Language ~~64~~ 53 bytes

```
""<>#&/@#&/@Select[#~Subsets~{2},IntersectingQ@@#&]&

```

Finds all the input list's `Subset`s of length 2, `Select` those in which the nodes of one pair intersect with the nodes of another pair (indicating that the pairs share a node), and `StringJoin` the nodes for all selected pairs.

The code is especially difficult to read because it employs 4 nested pure (*aka* "anonymous") functions.

The code uses braces, "{}", as list delimiters, as is customary in Wolfram Language.

1 byte saved thanks to Mr. Xcoder.

---

**Example**

```
""<>#&/@#&/@Select[#~Subsets~{2},IntersectingQ@@#&]&[{{"1","2"},{"1","3"},{"1","4"},{"2","5"},{"3","4"},{"4","5"}}]

(*{{"12", "13"}, {"12", "14"}, {"12", "25"}, {"13", "14"}, {"13", "34"}, {"14", "34"}, {"14", "45"}, {"25", "45"}, {"34", "45"}}*)

```

# Answer
> 0 votes
# Pyth, 7 bytes

```
@F#.cQ2

```

Try it here!

### If joining is necessary, 10 bytes

```
sMM@F#.cQ2

```

Try it here!

# Answer
> 0 votes
# C# 233 bytes

```
static void c(List<(string a,string b)>i,List<(string,string)>o){for(int m=0;m<i.Count;m++){for(int n=m+1;n<i.Count;n++){if((i[n].a+i[n].b).Contains(i[m].a)||(i[n].a+i[n].b).Contains(i[m].b)){o.Add((i[m].a+i[m].b,i[n].a+i[n].b));}}}}

```

## Example

```
using System;
using System.Collections.Generic;

namespace conjugateGraphGolf
{
    class Program
    {
        static void Main()
        {
            List<(string a, string b)>[] inputs = new List<(string, string)>[]
            {
                new List<(string, string)>(),
                new List<(string, string)>() {("0", "1")},
                new List<(string, string)>() {("0", "1"),("1", "2")},
                new List<(string, string)>() {("a","b"),("b","c"),("c","a")},
                new List<(string, string)>() {("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")}
            };

            List<(string, string)> output = new List<(string, string)>();

            for(int i = 0; i < inputs.Length; i++)
            {
                output.Clear();
                c(inputs[i], output);

                WriteList(inputs[i]);
                Console.Write(" -> ");
                WriteList(output);
                Console.Write("\r\n\r\n");
            }

            Console.ReadKey(true);
        }

        static void c(List<(string a,string b)>i,List<(string,string)>o){for(int m=0;m<i.Count;m++){for(int n=m+1;n<i.Count;n++){if((i[n].a+i[n].b).Contains(i[m].a)||(i[n].a+i[n].b).Contains(i[m].b)){o.Add((i[m].a+i[m].b,i[n].a+i[n].b));}}}}

        public static void WriteList(List<(string a, string b)> list)
        {
            Console.Write("[");
            for(int i = 0; i < list.Count; i++)
            {
                Console.Write($"(\"{list[i].a}\",\"{list[i].b}\"){(i == list.Count - 1 ? "" : ",")}");
            }
            Console.Write("]");
        }
    }
}

```

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


title: Round up my number

text:
# Question
Title: Round up my number
Sandbox

Given two positive integers a and b, return the smallest multiple of b that is greater than or equal to a.

## Examples

Definitions: `true` = `is a multiple of b`, `false` = `is not a multiple of b`.

* `f(1,3) = 3` because `1` is false, `1+1` is false, but `1+1+1` is true. Therefore `3` is returned.
* `f(5,3) = 6` because `5` is false, but `5+1` is true. Therefore `6` is returned.
* `f(9,3) = 9` because `9` is already a multiple of 3.
* `f(12,5) = 15` because `12` is false, `12+1` is false, `12+2` is false, but `12+3` is true. Therefore `15` is returned.

## Rules

* Input/output can be given by any convenient method.
* You can print it to STDOUT or return it as a function result.
* Either a full program or a function are acceptable.
* Any amount of extraneous whitespace is permitted, provided the characters line up appropriately.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

## The Catalogue

The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the snippet:

```
## [><>](https://esolangs.org/wiki/Fish), 121 bytes

```

```
/* Configuration */

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

/* App */

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

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

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

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

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

getAnswers();

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

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

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

function process() {
  var valid = [];

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

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

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

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

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

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();

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

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

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

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

}
```

```
body {
  text-align: left !important;
  display: block !important;
}

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

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

table thead {
  font-weight: bold;
}

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

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

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

# Answer
> 16 votes
# Python, 17 bytes

```
lambda a,b:a+-a%b

```

Try it online!

Since this doesn't use division, it works for both Python 2 and 3. Note that we can't cut out the `+` sign because `a-a%b` does `a-(a%b)`, whereas we want to do`(-a)%b` and add that to `a`. We could also write it as `-a%b+a`.

# Answer
> 9 votes
# Japt, 2 bytes

```
cV

```

Try it

```
cV     :Implicit input of integers U & V
cV     :Round U up to the nearest multiple of V

```

With input as an array:

```
rc

```

Try it

```
rc     :Implicit input of array
r      :Reduce by
 c     :Rounding the first element up to the nearest multiple of the second

```

## Less Trivial!, 6 bytes

```
_vV}aU

```

Try it

```
_vV}aU     :Implicit input of integers U & V
_          :Function taking an integer Z as input
 vV        :  Is Z divisible by V?
   }       :End function
    aU     :Starting from U, return the first integer that returns true when passed through that function

```

```
ôV ævV

```

Try it

```
ôV ævV     :Implicit input of integers U & V
ôV         :Range [U,U+V]
   æ       :Get first element
    vV     :  Divisible by V

```

# Answer
> 9 votes
## Intcode (day 5), ~~70~~ ~~66~~ 64 bytes

```
3,0,3,2,102,-1,2,4,1,0,4,0,1,1,8,1,7,9,0,5,5,5,14,2,1,2,0,4,0,99

```

Try it online!

Intcode is a programming language invented for Advent of Code 2019. It was first introduced on day 2, then further expanded upon on day 5, which is the version used here.

Since on PPCG, languages are defined by their interpreters, I am using the interpreter that I wrote for my day 5 solution (which was written before this challenge).

Explanation:

```
3,0,          store first input in cell 0
3,2,          store second input in cell 2
              (cell 1 is a counter, because it's already initialized to zero)
102,-1,2,4,   negate the second input and store in cell 4

              (begin loop)
1,0,4,0,      subtract the second input from the first input
1,1,8,1,      increment the counter (by adding cell 8)
7,9,0,5,      if the first input is greater than zero (cell 9)...
5,5,14,       ... jump to the beginning of the loop (reusing the cell 8 reference)

2,1,2,0,      multiply the counter by the second input
4,0,99        output and quit

```

# Answer
> 7 votes
# MATL, 4 bytes

```
:ien

```

Try it online!

### Explanation

Consider inputs `12`, `5`.

```
     % Implicit input
:    % Range
     % STACK: [1 2 3 4 5 6 7 8 9 10 11 12]
i    % Input
     % STACK: [1 2 3 4 5 6 7 8 9 10 11 12], 5
e    % Reshape as a matrix with that number of rows, padding with zeros
     % STACK: [1  6 11;
               2  7 12;
               3  8  0;
               4  9  0;
               5 10  0]
n    % Number of elements
     % STACK: 15
     % Implicit display

```

# Answer
> 7 votes
# x86 Machine Code, 7 bytes

Since x86 integer division instructions do only floor rounding, this uses the formula: `f(a,b) = floor((a+b-1)/b)*b` to accomplish ceiling rounding.

```
02 C3   ADD  AL, BL     ; a = a + b
48      DEC  AX         ; a = a - 1
F6 F3   DIV  BL         ; a = a / b
F6 E3   MUL  BL         ; a = a * b

```

Input is in `AL` and `BL`, output is `AL`.

**Testing**

Here is output from a test program for PC DOS that takes interactive input.

Download and test ROUNDMY.COM.

# Answer
> 6 votes
# Octave, 17 bytes

Same method as this JS answer:

```
@(a,b)ceil(a/b)*b

```

Try it online!

# Answer
> 5 votes
# JavaScript (Node.js), 17 bytes

```
a=>b=>a+(b-a%b)%b

```

Try it online!

# Answer
> 5 votes
# Python 2, ~~23~~ ~~20~~ 18 bytes

```
lambda a,b:-a/b*-b

```

Try it online!

2 bytes thanks to tsh

# Answer
> 5 votes
# Haskell, 14 bytes

```
a%b=a+mod(-a)b

```

Try it online!

# Answer
> 5 votes
# C++ (gcc), ~~43~~ ~~41~~ ~~40~~ ~~36~~ 25 bytes

```
#define f(a,b)(b-a%b)%b+a

```

Try it online!

Saved 4 bytes thanks to @Neil!!!

Saved 11 bytes thanks to @AZTECCO!!!

# Answer
> 4 votes
# Jelly, 3 bytes

```
÷Ċ×

```

Try it online!

Simply divide, ceiling, multiply.

# Answer
> 4 votes
# C (gcc), ~~47~~ ~~31~~ 25 bytes

```
f(a,b){a=a%b?f(++a,b):a;}

```

Try it online!

-16 bytes thanks to A̲̲ (forgot that return types and parameters would default to int if not defined, whoops!)

-6 thanks to AZTECCO for using a ternary and making the function recursive

# Answer
> 4 votes
# Wolfram Language (Mathematica), 7 bytes

```
Ceiling

```

Just pointing out that Mathematica's builtin, which is most commonly called with one argument, actually does exactly the desired operation when called with two arguments.

# Answer
> 4 votes
## Brainfuck, ~~52~~ 49 bytes

Thanks to Jo King for finding a bug, helping fix it with some extra golfing.

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

```

Input and output is in character codes.

Try it online!

**Explanation**

```
,>>,<<                     [>a, 0,     b,   0]
[>+>->+<[>]>[<+>-]<<[<]>-] [>0, a, b-a%b, a%b]
>>>[<[-<+>]>,]             If a%b is nonzero, add b-a%b to a, and clear a%b
<<.                        Output a+(b-a%b)

```

Modulus algorithm is straight from the esolang list of brainfuck algorithms.

# Answer
> 3 votes
# JavaScript (V8), 22 bytes

This is the function \\$(a,b) \mapsto \left\lceil \frac{a}{b} \right\rceil b\\$.

```
a=>b=>Math.ceil(a/b)*b

```

Try it online!

# Answer
> 3 votes
# , 20 bytes

```
function(a,b)a+-a%%b

```

Try it online!

# Answer
> 3 votes
# K (oK), 8 bytes

```
{x+y!-x}

```

Try it online!

Another port of xnor's Python answer.

# Answer
> 3 votes
# Vyxal, 3 bytes

```
/⌈*

```

Try it Online!

# Answer
> 2 votes
# Red, 31 bytes

```
func[a b][round/to/ceiling a b]

```

Try it online!

Just a built-in `round` with refinements `to`, which scales the first argument according to the second, and `ceiling`, which indicates the direction.

# Red, 25 bytes

```
func[a b][0 - a // b + a]

```

Try it online!

A port of xnor's Python answer. Don't forget to upvote his answer!

# Answer
> 2 votes
# Retina 0.8.2, 28 bytes

```
\d+
$*
r`1+(\2*) (1+)
$1$2
1

```

Try it online! Link includes test cases. Explanation:

```
\d+
$*

```

Convert the inputs to unary.

```
r`

```

Process this stage from right-to-left, so that `\2` gets to match \\$ b \\$ first, allowing us to refer to it when matching within \\$ a \\$.

```
1+(\2*) (1+)

```

Match \\$ b \\$ in `\2`, then as many copies of \\$ b \\$ as we can, without completely exhausting \\$ a \\$. `\1` thus matches \\$ b \lfloor \frac {a - 1} b \rfloor = b \lceil \frac {a - b} b \rceil \\$

```
$1$2

```

Add that to \\$ b \\$ to give \\$ b \lceil \frac a b \rceil \\$.

```
1

```

Convert to decimal.

# Answer
> 2 votes
# Ruby, 13 bytes

```
->a,b{-a%b+a}

```

Try it online!

# Answer
> 2 votes
# Prolog (SWI) \+ CLPFD, 30 bytes

```
f(R,X,Y):-R#=_*Y,R-Y#<X,R#>=X.

```

Try it online!

```
f(R,X,Y)

```

`f` is a predicate taking in a variable `R`, and two integers `X` and `Y`.

The CLPFD constraints are expressed using the `#`-prefixed operators. `,` means and, so `f` is true iff all these constraints are satisfied, i.e.,

1) `R#=_*Y` R is a multiple of Y `,` and

2) `R-Y#<X` R-Y \< X `,` and

3) `R#>=X` R \>= X `.`

# Answer
> 2 votes
# SimpleTemplate, 61 bytes

This was quite fun! Sadly, I had to do the dumb way :(

```
{@fn F A,B}{@whileA is notmultipleB}{@incA}{@/}{@returnA}{@/}

```

Creates a function that iterates until it finds a number that's multiple of the 2nd number.

This was actually way smaller than doing it without a function.

---

**Ungolfed:**

```
{@fn F numberA, numberB}
    {@while numberA is not multiple of numberB}
        {@inc by 1 numberA}
    {@/}
    {@return numberA}
{@/}

```

Should be mostly straightforward.

You can see it running on https://ideone.com/MR7t1E (golfed version only).

# Answer
> 2 votes
# Charcoal, 10 bytes

```
≔±ＮθＩ×θ÷Ｎθ

```

Try it online! Link is to verbose version of code. Takes \\$ b \\$ first and \\$ a \\$ second. Explanation:

```
≔±Ｎθ

```

Input \\$ b \\$, negate it, and save the result.

```
Ｉ×θ÷Ｎθ

```

Input \\$ a \\$ and compute \\$ -b \lfloor \frac a {-b} \rfloor \\$, then cast to string for implicit print.

# Answer
> 2 votes
# GolfScript, 6 bytes

```
.~)@%+

```

Try it online!

Function which consumes A and B from the stack, assuming B is below A.

### Explanation:

```
           #Example input: A = 12, B = 5          stack is  5  12
.~)        #Duplicate A and negate the duplicate  stack is  5  12 -12
   @       #Pull 3rd from top to top              stack is 12 -12   5
    %      #Second to top mod top                 stack is 12 3
     +     #Add remaining values                  stack is 15

```

# Answer
> 2 votes
# Javascript (ES6), 19 bytes

```
a=>b=>a%b?a-a%b+b:a

```

Naive attempt, pretty sure this can be golfed further.

# Answer
> 2 votes
# Java, 99 bytes

```
static int r(int a,int b){int t=a%b<1||b%a<1?a:r(a+1,b);return t;}

```

# Answer
> 2 votes
## JavaScript, 15 bytes

```
a=>b=>--a+b-a%b

```

More expressively, the answer is `a => b => a + b-((a-1)%b) - 1`, but by decrementing `a` we can handle both the "subtract one" steps at once, saving a couple of bytes. Then we just get lucky with operator presidencies.

# Answer
> 2 votes
# Java (JDK), 15 bytes

```
b->a->--a+b-a%b

```

Try it online!

# Answer
> 2 votes
## Perl 5, (111 bytes with footer) 52 bytes

`sub f{($a,$b)=@_;$c=$b;$c++until!($c%$b)&&$c>=$a;$c}`

Try it online!

Takes `a` and `b` as arguments to a subroutine named `f` and increases `$c` until it is both a multiple of `$b` and greater than or equal to `$a`. Then returns `$c` (the last value evaluated in a subroutine is the return value).

# Answer
> 2 votes
# Thunno 2, 3 bytes

```
/ṃ×

```

Try it online!

#### Explanation

```
/ṃ×  # Implicit input
/    # Divide
 ṃ   # Ceil
  ×  # Multiply
     # Implicit output

```

# Answer
> 1 votes
# , 6 bytes

```
]*>.@%

```

Try it online!

```
]         the right argument
 *        multiplied by
  >.@     the ceiling of
     %    the left argument dividided by the right one

```

If we can swap the order of the aruments:

# , 5 bytes

```
]+[|-

```

Try it online!

# Answer
> 1 votes
# Pyth, 8 bytes

```
AQ+G%_GH

```

Try it online!

Simple port of the Python answer from xnor so please give that answer an upvote.

Debugged:

```
==================================================
assign('Q',eval_input())
assign('[G,H]',Q)
imp_print(plus(G,mod(neg(G),H)))
==================================================

```

# Answer
> 1 votes
# Keg, `-hr`, ~~17~~ ~~9~~ 6 bytes

```
¿±¿%¿+

```

A port of my W answer which is a port of Xnor's python answer

## Answer History

### 9 bytes `-rR`

```
&¿{:⑻$%|⑹

```

### Explained

```
&¿{:⑻$%|⑹
&           #Store the implicit input (the number to round) in the register
 ¿          #Take the number to 'round by'
  {         #While:
   :⑻      #Duplicate the 'round by' and push the register without emptying it
     $%  #Swap the two and perform modulus, checking the result against 0
       |⑹  #    Increment the register

```

## Answer History

### 17 bytes

```
&¿{:&:&$%|&1+&}&

```

Try it online!

# Answer
> 1 votes
# APL+WIN, 8 bytes

Prompts for b followed by a:

```
b×⌈⎕÷b←⎕

```

Try it online! Courtesy of Dyalog Classic

# Answer
> 1 votes
# MathGolf, 3 bytes

```
/ü*

```

Similar approach as other answers: \\$\lceil\frac{a}{b}\rceil b\\$.
I/O as floats with `.0`, with the inputs in the order `a b`.

Try it online.

**Explanation:**

```
/    # Divide the second (implicit) input by the first (implicit) input
     #  i.e. 3.0 5.0 → 1.666...
 ü   # Ceil it
     #  → 2
  *  # Multiply it by the first (implicit) input
     #  → 6.0
     # (output the entire stack joined together implicitly as result)

```

# Answer
> 1 votes
# Runic Enchantments, 10 bytes

```
ii:},'cA*@

```

Try it online!

```
ii            Read a, read b
  :}          Dup b, rotate to bottom of stack
    ,         Divide
     'cA      Ceiling
        *     Multiply
         @    Output and terminate

```

# Answer
> 1 votes
# , ~~7~~ 4 bytes

```
_bm+

```

*-3 bytes thanks to @A*

## Answer History

```
0a-bma+

```

Yet *another* port of xnor's Python answer.

# Answer
> 1 votes
# Pyth, 5 bytes

```
+%_QE

```

Try it online!

Port of @xnor's answer

## How it works

```
+%_QE
+    (Q)- The sum of the implicit first input and...
  _Q    - The negative of the first input...
 %  E   - Modulo the second input

```

# Answer
> 1 votes
## TI BASIC, 8 bytes

```
-Bint(-A/B

```

"-" is the negative symbol here, distinct from the minus symbol on the calculator. TI BASIC doesn't have a token for a rounding up operation, we have to pick between iPart( and int( or take another route with fPart( or remainder( on OS 2.53+. int( rounds -2.5 down to -3 where iPart( would return -2, so we can use int( with negation to turn rounding down into rounding up.

Disp is implicit because the result is the final line, and the function can be a full program easily by adding Prompt A,B.

# Answer
> 1 votes
# Rockstar, ~~115~~ 109 bytes

```
F takes X
let M be X/D
turn up M
return M is X/D

listen to N
listen to D
until F taking N
let N be--1

say N

```

Try it here (Code will need to be pasted in, input on individual lines)

# Answer
> 1 votes
# Perl 5 `-p`, 10 bytes

```
$_+=-$_%<>

```

Try it online!

# Answer
> 1 votes
# Nekomata, 3 bytes

```
/K*

```

Attempt This Online!

`\div`, `\ceil`, `\mul`.

# Answer
> 0 votes
# ARBLE, 11 bytes

```
ceil(a/b)*b

```

Try it online!

---
Tags: code-golf, number, integer
---


title: Is it a valid Go type?

text:
# Question
Title: Is it a valid Go type?
Write the shortest program or function that will determine if an input is a valid Go type.

## Spec

This challenge will use the following simplified subset of Go types. For more information, see the Golang specification.

* "Primitive" types:
    + `bool`
    + `int`,`uint`,`float(32|64)`,`complex(64|128)`,`byte`,`rune`
    + `string`
* `*T` where `T` is any type
* `[]T`, a slice of `T`
* `[n]T`, an array of `T`, and `n` is some positive non-zero integer
* `map[K]V`, where `K` and `V` are any type
* `chan T` (note the required whitespace)
* `struct{...}`, where `...` is a list of 0 or more semicolon-separated types (such as `struct{int;float64;*struct{int;bool}}`).
* `func(args)return`, a function.
    + `args` is an optional comma-separated list of types.
    + `return` is optionally either a type, or a *non-empty* list of types in parentheses `(a,b,c)`.

All truthy inputs have characters in the set `[][a-z0-9(){},;* \t\n]`. It is not guaranteed that an input that matches this regex is truthy.

Whitespace is allowed everywhere within the type, as long as it does not break apart keywords (`struct`, `chan`, `map`, `func`) or primitive types.

## Test Cases

### Truthy

```
bool
int
complex128
*int
*********int
[]string
[][]int
[ 10 ] [ ][123] * [567] [ ] [890 ] *rune
map[int]string
map[ []int ] [] string
map[map[map[int]string]map[bool]chan map[int]int]struct{int;string;bool}
struct{ }
struct{int; float64; *struct{int;bool} }
struct{struct{bool;struct{int; *[]chan complex128}; *float64}; map[string]string}
func()
func(int,uint,int,bool)string
func(int,uint,int,bool)(string,string,string)
func(func(int) int) func(func([]map[string]int) int) func(int) int
chan chan chan chan chan chan int
map[func() func() func()]func() func() func()
chan []string
func(int)(int)

```

### Falsy

```
integer   // unknown primitive
float     // unknown primitive
imaginary // unknown primitive
int*      // * with no type
[]        // missing contained type
[]asdfghjkl // unknown type
[[]]int     // [] is invalid for array length
[-1]string  // negative ints are invalid for array length
[123.456]float64     // floats are invalid for array length
struct{int,float64}  // missing semicolon between member types
func(int)(int,string // missing closing paren
struct{func(int)map[int]string // missing closing brace
structfunc(int)map[int]string} // missing opening brace, unknown type
chanint      // missing required whitespace
chan[]string // missing space whitespace
func()()     // non-empty parenthesized return type only
[0]int       // positive non-zero integers only
func(int)(int)(iint) // dangling leftovers `(iint)` is not a type

```

# Answer
## Regex (PCRE), 241 bytes

```
^(bool|u?int|float(32|64)|complex(64|128)|byte|rune|string|&\s*(?1)|\*\s*(?1)|\[\s*\d*\s*\]\s*(?1)|map\s*\[\s*(?1)\s*\]\s*(?1)|chan (?1)|struct\s*\{\s*(|((?1);\s*)*\s*(?1)\s*;?\s*)\}|func\(\s*(((?1),\s*)*(?1),?\s*)?\)\s*(\s*(?1)|\((?6)\))?)$

```

Fixed to handle `func()()` case

Try it on regex 101
> 14 votes

# Answer
# BNFC \+ Haskell \+ Bash \+ coreutils, 175 + 96 = 271 bytes

```
bool"
int"
uint"
float32"
float64"
complex64"
complex128"
byte"
rune"
string"
*"T
[""]"T
["Integer"]"T
map""["T"]"T
chan "T
struct""{"[T]"}"
Q
QT
Q"("[T2]")"Z2","Z";";_.T2::=T

```

Compile with

```
sed 's/Q/func""("[T2]")"/g;s/Z/;separator T/g'|awk '{print"A"NR".T::=\""$0";"}'>g;bnfc -m g;make

```

Produces an executable named `TestG` which accepts input from `stdin` and exits with code `0` if the parse was successfull, `1` otherwise.

Possibly can be golfed more with a better use of sed and awk.

---

Script to test it:

```
cat truthy falsy | sed "s|//.*||" | xargs -d "\n" -I {} sh -c 'echo "{}" | ./TestG >/dev/null ; echo $? "{}"'

```
> 7 votes

# Answer
# Raku, ~~205~~ 193 bytes

```
*~~/^$(/:s \s*[bool|u?int|float[32|64]|complex[64|128]|byte|rune|string|\*<~~>|\[
\d* \]<~~>|map \[<~~>\]<~~>|chan\s+<~~>|struct \{ <~~>*%\; \}|func \(<~~>*%\,\)[<~~>|
\( <~~>*%\, \) ]?]\s*/)$/

```

Try it online!

This is an anonymous function that matches its argument against the giant regex following the leftmost `~~`. That regex is of the form

```
/^$(/.../)$/

```

It interpolates the inner regex `$(/.../)` into the outer one. The outer regex requires that the overall match be anchored at the beginning and end of the string.

The inner regex matches a Go type. It is recursive, calling itself using the expression `<~~>`.
> 5 votes

# Answer
# JavaScript (ES6), 250 bytes

*Thanks to @Bbrk24 and @Value Ink for reporting bugs*

Returns a Boolean value.

```
f=(s,t)=>s!=(s=s[R='replace'](T='T',t)[R](/chan |\[([1-9]\d*)?\]|map\[T\]/g,'*')[R](/\w \w/)[R](/ /,'')[R](/bool|u?int|float(32|64)|complex(64|128)|byte|rune|string|\*T|struct{(T(;T)*)?}|func\((T(,T)*)?\)(T|\(T(,T)*\)|(?=[,;})\]])|$)/,T))?f(s,T):s==T

```

Try it online!

### How?

At each iteration:

* If we find a `"T"` and this is the first iteration, we replace it with `"undefined"` to invalidate the input.
* We replace all occurrences of `/chan /`, `/\[([1-9]\d*)?\]/` and `/map\[T\]/` with `"*"`. They all boil down to a valid prefix of another type.
* If we find `/\w \w/`, we replace it with `"undefined"` to invalidate the input.
* If we find a space somewhere else, we remove it.
* We then look for the first valid type and replace it with `"T"`:

+ primitive types: `/bool|u?int|float(32|64)|complex(64|128)|byte|rune|string/`
    + a type preceded with `*`: `/\*T/`
    + a `struct` type: `/struct{(T(;T)*)?}/`
    + a `func` type: `/func\((T(,T)*)?\)(T|\(T(,T)*\)|(?=[,;})\]])|$)/`

The `func` type is the trickiest one because we must not ignore a *return* statement that is not yet fully simplified. That's why we make sure that `func(...)` is followed by either a valid *return* statement or the end of the line or one of `,;}]`.

This process is repeated recursively until there's nothing more to replace. If the input string is valid, we should end up with a single `"T"`.

### Example 1

```
func(int,uint,int,bool)(string,string,string)
func(T,uint,int,bool)(string,string,string)
func(T,T,int,bool)(string,string,string)
func(T,T,T,bool)(string,string,string)
func(T,T,T,T)(string,string,string)
func(T,T,T,T)(T,string,string)
func(T,T,T,T)(T,T,string)
func(T,T,T,T)(T,T,T)
T

```

### Example 2

```
map[map[map[int]string]map[bool]chan map[int]int]struct{int;string;bool}
map[map[map[T]string]map[bool]*map[int]int]struct{int;string;bool}
map[map[*T]map[bool]*map[int]int]struct{int;string;bool}
map[map[T]map[bool]*map[int]int]struct{int;string;bool}
map[*map[T]*map[int]int]struct{int;string;bool}
map[***map[T]int]struct{int;string;bool}
map[****T]struct{int;string;bool}
map[***T]struct{int;string;bool}
map[**T]struct{int;string;bool}
map[*T]struct{int;string;bool}
map[T]struct{int;string;bool}
*struct{T;string;bool}
*struct{T;T;bool}
*struct{T;T;T}
*T
T

```
> 5 votes

# Answer
# Go, ~~1279~~ 1277 bytes

```
import(."regexp";."strings";U"unicode")
func P(s string)(string,bool){S,M,C,t,Z:=U.IsSpace,MustCompile,CutPrefix,0,0<1
T,X:=func(){for len(s)>0&&S(rune(s[0])){s=TrimSpace(s[1:])}},!Z
N:=func(){T();s=s[1:];T()}
T()
if len(s)<1{return s,X}
if k:=M(`^(bool|u?int|float(32|64)|complex(64|128)|byte|rune|string)($|[]});,\s])`).FindStringIndex(s);k!=nil&&k[0]<1{s=s[k[1]-1:];T();return s,Z}
if s[0]=='*'{return P(s[1:])}
if s[0]=='['{N();k:=M("^[1-9][0-9]+").FindStringIndex(s);if k!=nil{s=s[k[1]:];N();return P(s)};N();return P(s)}
if r,o:=C(s,"map");o{s=r;N();s,o=P(s);if!o{return s,X};if s[0]==']'{N()};return P(s)}
if r,o:=C(s,"chan");o{s=r;if!S(rune(s[0])){return s,X};T();return P(s)}
if r,o:=C(s,"struct");o{s=r;T();if s[0]!='{'{return s,X};N();for s[0]!='}'{s,o=P(s);if!o{return s,X};if s[0]=='}'{break};if s[0]!=';'{return s,X};N()};N();return s,Z}
if r,o:=C(s,"func");o{s=r;T();if s[0]!='('{return s,X};N();for s[0]!=')'{s,o=P(s);if!o{return s,X};if s[0]==')'{break};if s[0]!=','{return s,X};N()};N();if len(s)<1||M(`^[]});,\s]`).MatchString(s){return s,Z}
if s[0]=='('{N();for s[0]!=')'{s,o=P(s);if!o{return s,X};t++;if s[0]==')'{break};if s[0]!=','{return s,X};N()};if t<1{return s,X};N()}
if M(`^[iufcmbrsc*[]`).MatchString(s){return P(s)};return s,len(s)<1}
return s,X}

```

Attempt This Online!

An *extremely* straight-forward recursive solution. The parser makes use of the fact that Go types are mainly right-recursive, with an unambiguous prefix determining the parser state.

Most definitely can be golfed down by using a different algorithm, or making it iterative.

(Fun fact: the builtin `go/parser` package fails some test cases due to the recursive anonymous `struct`s. It expects typenames or field names there. Though, in normal usage with gofmt, nested anonymous structs tends to not happen.)

* -2 bytes: account for "dangling" leftovers, move true/false into variables (@The Thonnu)

### Ungolfed

```
func parse(s string) (string, bool) {
    trimSpace := func() {
        for len(s) > 0 && unicode.IsSpace(rune(s[0])) {
            s = strings.TrimSpace(s[1:])
        }
    }
    nextChar := func() {
        trimSpace()
        s = s[1:]
        trimSpace()
    }
    trimSpace()
    // false on empty
    if len(s) == 0 {
        return s, false
    }
    // primitive types
    if k := regexp.MustCompile(`^(bool|u?int|float(32|64)|complex(64|128)|byte|rune|string)($|[]});,\s])`).FindStringIndex(s); k != nil && k[0] < 1 {
        s = s[k[1]-1:]
        trimSpace()
        return s, true
    }
    // pointer
    if s[0] == '*' {
        return parse(s[1:])
    }
    // slice/array
    if s[0] == '[' {
        nextChar()
        // look for a positive int
        k := regexp.MustCompile("^[1-9][0-9]+").FindStringIndex(s)
        if k != nil {
            s = s[k[1]:]
            nextChar()
            return parse(s)
        }
        nextChar()
        // contained type
        return parse(s)
    }
    // maps
    if rest, ok := strings.CutPrefix(s, "map"); ok {
        s = rest
        nextChar()
        // key
        s, ok = parse(s)
        if !ok {
            return s, false
        }
        // account for primitive
        if s[0] == ']' {
            nextChar()
        }
        // value
        return parse(s)

    }
    // chan
    if rest, ok := strings.CutPrefix(s, "chan"); ok {
        s = rest
        // required space
        if !unicode.IsSpace(rune(s[0])) {
            return s, false
        }
        trimSpace()
        // contained type
        return parse(s)
    }
    // struct
    if rest, ok := strings.CutPrefix(s, "struct"); ok {
        s = rest
        trimSpace()
        if s[0] != '{' {
            return s, false
        }
        nextChar()
        // semicolon-separated list of types
        for s[0] != '}' {
            // type
            s, ok = parse(s)
            if !ok {
                return s, false
            }
            // when 1 type, next is a '}'
            if s[0] == '}' {
                break
            }
            // semicolon
            if s[0] != ';' {
                return s, false
            }
            nextChar()
        }
        nextChar()
        return s, true
    }
    // func
    if rest, ok := strings.CutPrefix(s, "func"); ok {
        s = rest
        trimSpace()
        // comma-separated args
        if s[0] != '(' {
            return s, false
        }
        nextChar()
        for s[0] != ')' {
            // type
            s, ok = parse(s)
            if !ok {
                return s, false
            }
            // when 1 type, next is a ')'
            if s[0] == ')' {
                break
            }
            // comma
            if s[0] != ',' {
                return s, false
            }
            nextChar()
        }
        nextChar()
        // return type
        // can be nothing, 1 type, or parened comma-separated types
        // nothing
        if len(s) == 0 || regexp.MustCompile(`^[]});,\s]`).MatchString(s) {
            return s, true
        }
        // multiple types
        if s[0] == '(' {
            nextChar()
            typeCount := 0
            for s[0] != ')' {
                // type
                s, ok = parse(s)
                if !ok {
                    return s, false
                }
                typeCount++
                // when 1 type, next is a ')'
                if s[0] == ')' {
                    // nextChar()
                    break
                }
                // comma
                if s[0] != ',' {
                    return s, false
                }
                nextChar()
            }
            // no non-empty paren return type
            if typeCount == 0 {
                return s, false
            }
            nextChar()
        }
        // 1 type
        if regexp.MustCompile(`^[iufcmbrsc*[]`).MatchString(s) {
            return parse(s)
        }
        return s, len(s) == 0
    }
    return s, false
}

```
> 4 votes

# Answer
# Ruby `-nl`, ~~239~~ 234 bytes

Uses the replacement strategy from Arnauld's Javascript answer as a full program using the `-nl` flag to loop the code over each line of input. Since Ruby doesn't let you inject `undefined` by leaving out arguments, the relevant replacements to force disqualification use `X` instead.

I had a slightly different regex strategy for solving the `func` issue but it turns out using the regexes from that answer was shorter.

```
sub'T',?X
1until$_==(gsub /\[([1-9]\d*)?\]|map\[T\]|chan\s/,?*;sub /\w\s\w/,?X;sub /\s/,'';sub /bool|u?int|float(32|64)|complex(64|128)|byte|rune|string|\*T|struct{(T(;T)*)?}|func\((T(,T)*)?\)(T|\(T(,T)*\)|(?=[,;})\]])|$)/,?T)
p$_==?T

```

Attempt This Online!
> 2 votes

---
Tags: code-golf, decision-problem, parsing, syntax
---


title: Reverse engineer colors for a layout

text:
# Question
Title: Reverse engineer colors for a layout
*This challenge was originally posted on codidact.*

---

At my job we have to sometimes lay out materials. Materials come in large long rolls and are cut into smaller pieces when being laid out.

When we order the rolls we draw up a layout document which describes how we are going to cut them and layout the pieces. This tells the manufacturer how we are going to use the rolls so they can make all the right adjustments. We then use the document when actually laying the materials out.

In reality these documents are very complex and include a lot of information, however for this challenge I will simplify them. We will say pieces are placed in a 1-dimensional list with no gaps. The document indicates which pieces come from which rolls and the order in which they are cut.The document uses color to indicate which roll each piece comes from and numbers them in order. However sometimes things don't get printed in color, or colors get smudged. But usually you can still figure out which pieces come from which rolls based on the numbers alone, since there are some constraints on how things can be placed.

Here are the two constraints:

1. We lay out pieces from the same roll in order, so 1 is the first piece to be laid out, then 2 etc.
2. If the piece number is greater than 1 it must be placed adjacent to another piece from the same roll.

So if we look at the following layout:

```
1,2,1,3

```

We can see that there are two rolls, since there are two 1s. We can also see that one of the rolls has 3 pieces since there is a piece labeled 3. The 3 is next to a 1, so they must come from the same roll, thus the pieces come from the following rolls:

```
[1,2,1,3]
[0,1,1,1]

```

In this challenge you are going to write a program which determines the color information based on a colorless layout.

# Task

Take as input a list of positive integers representing a layout. Each integer is a piece number. Output a lists of integers representing the possible colorings of the layout.

Each coloring should be a list of integers with the same length as the input such that iff the pieces at two indices are from the same roll the same integer is at those indices in the coloring.

If there is no way to color the layout, output an empty list, if it is ambiguous output all the possible colorings.

If there is no layout just output an empty list.

This is code-golf, so the goal is to minimize the size of your source code as measured in bytes.

# Test cases

The output does not have to exactly match the ones given here, the possibilities can be given in any order, and the rolls can be assigned different numbers, so long as each roll is assigned a different number.

```
[1,2,1] -> [[0,0,1], [0,1,1]]
[2,1,3,2,1] -> [[0,0,0,1,1], [0,0,1,1,1]]
[1,2,1,2,1] -> [[0,0,1,1,2], [0,0,1,2,2], [0,1,1,2,2]]
[1,6] -> []
[4,2,3,1] -> []
[1] -> [[0]]
[1,2,3,4] -> [[0,0,0,0]]
[4,3,1,2] -> [[0,0,0,0]]
[3,1,2,4] -> [[0,0,0,0]]
[1,2,1,3] -> [[0,1,1,1]]
[1,2,3,1] -> [[0,0,0,1]]
[1,2,2,1] -> [[0,0,1,1]]

```

# Answer
> 4 votes
# Pyth, 31 bytes

```
ms.e.ekbdf.Am&SI._M.+dqSldSdT./

```

Try it online!

### Explanation

```
ms.e.ekbdf.Am&SI._M.+dqSldSdT./Q    # implicitly add Q
                                    # implicitly assign Q=eval(input())
                             ./Q    # list all partitions of Q
         f                          # filter these partitions on lambda T
          .A                        #   check if all are truthy
            m               T       #   T mapped over lambda d
                   .+d              #     the deltas of d
                ._M                 #     mapped to their signs
              SI                    #     is invariant under sorting
             &                      #     and
                          Sd        #     sorted(d)
                      q             #     equals
                       Sld          #     range(1,len(d)+1)
m                                   # map the remaining valid partitions over lambda d
 s                                  #   flatten
  .e.ekbd                           #   convert each element of each partition part to its index in the partition

```

# Answer
> 4 votes
# Jelly, 18 bytes

```
ŒṖtL$ƬL>LƲƇƑƇJxẈƊ€

```

A monadic Link that accepts a layout as a list of positive integers and yields all possible colourings using a prefix of the positive integers.

**Try it online!**

### How?

```
ŒṖtL$ƬL>LƲƇƑƇJxẈƊ€ - Link: list of positive integers, Layout
ŒṖ                 - all partitions of {Layout}
            Ƈ      - keep those {patitions} for which:
           Ƒ       -   {partition} is invariant under?:
          Ƈ        -     keep those {parts} for which:
         Ʋ         -       last four links as a monad:
     Ƭ             -         collect while distinct under:
    $              -           last two links as a monad:
   L               -             length
  t                -             trim all occurrences of {that} from both ends
      L            -         length of {that list of collected, trimmed parts}
        L          -         length {part}
       >           -         {collected count} greater than? {part length}
                 € - for each {valid partition}:
                Ɗ  -   last three links as a monad:
             J     -     indices {partition}
               Ẉ   -     length of each {partition}
              x    -     {indices} times {lengths}

```

# Answer
> 4 votes
# JavaScript (Node.js), 107 bytes

```
f=([v,...a],L=[],k=0,G,h)=>v?1&(h<v^G/2|G>>v)?'':f(a,L=[...L,k],k,G|=1<<v,v)+f(a,L,1+k,G&G+2&&1):G?'':L+`
`

```

Try it online!

# Answer
> 3 votes
# JavaScript (ES6), 168 bytes

Returns a string, using commas and linefeeds as separators.

```
f=([v,...a],p=[],c=p,b=[...p,c])=>v?f(a,p,[...c,v])+(c+c&&f(a,b,[v])):b.some(c=>c.some(d=m=p=v=>m==(m|=1<<v)|d^p<(d^=v<2,p=v))|m+1&m+2)?"":b.map((c,i)=>c.map(_=>i))+`
`

```

Try it online!

## Commented

### Recursive part

We build all partitions of the input array `a[]`.

```
f = (                  // f is a recursive function taking:
  [ v,                 // v = next piece number
       ...a ],         // a[] = array of remaining values
  p = [],              // p[] = current partition
  c = p,               // c[] = current piece cluster
  b = [...p, c]        // b[] = copy of p[] with c[] added
) =>                   //
v ?                    // if v is defined:
  f(a, p, [...c, v]) + //   do a recursive call with v added to c[]
  (                    //
    c + c &&           //   if c[] is not empty,
    f(a, b, [v])       //   do another recursive call with p[] = b[]
  )                    //   and c[] = [ v ]
:                      // else:
  ...                  //   final test (see below)

```

### Final test

We test whether the partition `b[]` is valid.

```
b.some(c =>            // for each cluster c[] in b[]:
  c.some(d = m = p =   //   initialize d, m and p to NaN'ish values
  v =>                 //   for each value v in c[]:
    m == (m |= 1 << v) //     set the bit at index v in m and make sure
                       //     that m is modified by doing so
    | d ^ p < (        //     make sure that p and v are in the expected
      d ^= v < 2,      //     order, update p to v
      p = v            //     and update the direction if v = 1
    )                  //
  )                    //   end of inner some()
  | m + 1 & m + 2      //   make sure that m consists of a sequence of
                       //   consecutive bits set to 1, followed by a
                       //   trailing 0
)                      // end of outer some()
?                      // if it failed:
  ""                   //   append nothing
:                      // else:
  b.map((c, i) =>      //   turn each value in each cluster c[] in b[]
    c.map(_ => i)      //   into a roll number
  ) +                  //   implicit coercion to a string
  `\n`                 //   append a linefeed

```

# Answer
> 2 votes
# Python3, 772 bytes:

```
E=enumerate
def f(l,I=[],r=[]):
 if len(I)==len(l):yield r;return
 for i,a in E(l):
  if a==1 and i not in I:
   j,k,Q,W=i,i,[],[]
   while(j:=j-1)>=0 and j not in I and l[j]!=1 and(Q==[]or Q[-1][0]<l[j]):Q+=[(l[j],j)]
   while(k:=k+1)<len(l)and k not in I and l[k]!=1 and(W==[]or W[-1][0]<l[k]):W+=[(l[k],k)]
   R=range(max(len(Q),len(W)))
   for x in R:
    for y in R:
     u=[Q[:x+1],W[:y+1]]
     for o,V in E(u):
      if V and V[0][0]==2:
       M=V+u[not o]
       if len(S:=[X for X,_ in M])==len({*S}):
        yield from f(l,I+[j for _,j in M]+[i],r+[M+[(a,i)]])
   yield from f(l,I+[i],r+[[(1,i)]])
def F(l):
 R=[]
 B={str(sorted(j))for j in f(l)}
 for i in map(eval,B):
  v=[-1]*len(l)
  for P,j in E(i):
   for _,I in j:v[I]=P
  R+=[v]
 return{*map(tuple,R)}

```

Try it online!

# Answer
> 2 votes
# Python 3.8, 230 bytes

```
r=range
p=lambda l:[[l]]+[q+[l[n:]]for n in r(1,len(l))for q in p(l[:n])]
f=lambda Q:[[k for k,g in enumerate(q)for h in g]for q in p(Q)if all(sorted(d:=[0<s[i+1]-s[i]for i in r(len(s)-1)])==d and{*s}=={*r(1,len(s)+1)}for s in q)]

```

Try it online!

Essentially a port of my Pyth answer.

# Answer
> 2 votes
# K (ngn/k), 66 bytes

thanks @doug for drawing my attention to this interesting challenge

```
{(,^x)(,/{@[y;z;:;]'(((x=1+/y=)')#y@-1 1+z;,1+|/y)1=x@:z}[x]')/<x}

```

Try it online!

The results are off by one compared to the examples (this is allowed).

# Answer
> 1 votes
# Charcoal, 77 bytes

```
⊞υ⟦…θ¹⟧ＦΦθκ«≔⟦⟧ηＦυ«⊞η⁺κ⟦⟦ι⟧⟧≔⊟κζ¿⁼№ζ¹›ι↨ζ⁰⊞η⁺κ⟦⁺ζ⟦ι⟧⟧»≔ηυ»ＥΦυ⬤ι⬤λ№λ⊕ξ⭆¹ΣＥιＥνξ

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
⊞υ⟦…θ¹⟧

```

Start with a partition of just the first piece in a roll.

```
ＦΦθκ«

```

Loop over the remaining pieces.

```
≔⟦⟧η

```

Collect new potential partitions.

```
Ｆυ«

```

Loop over the current partitions.

```
⊞η⁺κ⟦⟦ι⟧⟧

```

Maybe this piece starts a new roll.

```
≔⊟κζ

```

Remove the last roll.

```
¿⁼№ζ¹›ι↨ζ⁰

```

If this piece could be part of the last roll...

```
⊞η⁺κ⟦⁺ζ⟦ι⟧⟧

```

... add that as an alternative.

```
»≔ηυ

```

Save the potential partitions for the next pass.

```
»ＥΦυ⬤ι⬤λ№λ⊕ξ⭆¹ΣＥιＥνξ

```

Output only those partitions whose rolls all contain all of the values from `1` up to their length, mapping each value to the roll index and flattening.

# Answer
> 1 votes
# 05AB1E, 29 bytes

```
.œʒε1š1¡`R‚εD{Q}`y{āQP}P}εĀƶ˜

```

Port of *@CursorCoercer*'s Pyth answer.

1-based output.

Try it online or verify all test cases.

**Explanation:**

```
.œ              # Get all partitions of the (implicit) input-list
  ʒ             # Filter it by:
   ε            #  Map over each part of the current partition:
    1š          #   Prepend a 1 to the part
      1¡        #   Then split the part on 1s
        `       #   Pop and push all split-parts separated to the stack
         R      #   Reverse the top/last split-part
          ‚     #   Pair it back together with the list before it)
           ε    #   Map over this pair of lists:
            D{Q #    Check if the list is sorted from lowest to highest:
            D   #     Duplicate the list
             {  #     Sort the copy
              Q #     Pop both lists, and check if they're equal
           }`   #   After the map: pop and push the two checks to the stack again
    y           #   Push the current part-list again
     {          #   Sort it from lowest to highest
      ā         #   Push a list in the range [1,length] (without popping the list)
       Q        #   Check if the two lists are the same
             P  #   Get the product of all values on the stack to see if this part is
                #   truthy
   }P           #  After the inner map: check if all parts of this partition were truthy
  }ε            # After the filter: map over the remaining partitions:
    Ā           #  Convert each character to a 1 (with an !=0 check)
     ƶ          #  Convert each inner value by its 1-based list-index
      ˜         #  Flatten this partition of indices to a single list
                # (after which the list of lists of (1-based) indices is output
                # implicitly as result)

```

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

```
(),&'*+(?,/{$[#*y:,/-1 1,/:'&'&/'(x:(x;y))=/:{|'y}\(0,/:-1_')'1|:'\(x+1;~y)
  {(@[;+/y;+;1]'x)_\:*|y}[x]'y
  &/*|x;,x;()]}.')/,1(1=)\(),

```

Try it online!

A beast! First, turn input into a single list of a list of singletons. This forms the initial list of partitions. Recursively search all such lists for indices which contain a singleton with value \> 1 and whose neighbor to the right or left has a maximum value 1 less than the value of the singleton and either have length \> 1 or have length 1 and a value equal to 1. Merge each such singleton with each such neighbor to form the next set of partitions.

\[EDIT: same idea but only keep the length and the highest value of each sequence. These are always the same except for singletons with value \> 1. I.e. those values waiting to be merged.\]

# Answer
> 1 votes
# Perl 5, 183 bytes

```
sub f{my@a;(join'',map chr,@_)=~m~^((.+)(?(?{$_=$2;$i=s/\x1/\0/;1while$c=chr++$i,s/\x00\Q$c\E|\Q$c\E\0/\0/;/[^\0]/||!(local@b=(@b,(1+$b[-1])x--$i))})(*F)))+\z(?{push@a,\@b})(*F)~s;@a}

```

Try it online!

With newlines for readability:

```
sub f{
my@a;
(join'',map chr,@_)=~
m~^((.+)(?(?{
$_=$2;
$i=s/\x1/\0/;
1while$c=chr++$i,s/\x00\Q$c\E|\Q$c\E\0/\0/;
/[^\0]/||!(local@b=(@b,(1+$b[-1])x--$i))
})(*F)))+\z(?{
push@a,\@b
})(*F)~s;
@a
}

```

Regexen as solution to any problem, but this one turned out somewhat long, therefore just for sake of completeness. Kind of seed-fill problem in 1-D. Last minute improvement was to number rolls from 1, per recent comment to OP. Otherwise (to number from 0) it was plus a few bytes.

---
Tags: code-golf
---


title: Chunk + Enumerate a list of digits

text:
# Question
Title: Chunk + Enumerate a list of digits
I have a list of decimal digits:

`4, 4, 4, 7, 7, 9, 9, 9, 9, 2, 2, 2, 4, 4`

The list of decimal digits are known as items. We can form "chunks" from these items by grouping together identical and adjacent numbers. I want to assign each chunk a unique number, starting from 1, and increasing by 1 in the order the chunks appear in the original list. So, the output for the given example would look like this:

`1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5`

## Input format

A list of digits. (0-9) You may use your language built-ins to read this list however you want. Encoding: ASCII

# Output format

A series of decimal numbers, separated by a delimiter. Your program must always use the same delimiter. The delimiter must be longer than 0 bits. Encoding: ASCII

Standard loopholes apply.

# Answer
> 7 votes
# Python 3.8 (pre-release), 41 bytes

```
lambda l,n=0:[n:=n+(l!=(l:=x))for x in l]

```

Try it online!

Praise the magic walrus `:=` of assignment expressions.

---

# Python 2, 42 bytes

```
n=0
for x in input():n+=x!=id;id=x;print n

```

Try it online!

# Answer
> 6 votes
# Python 2, 44 bytes

```
l=input()
n=0
for i in l:n+=i!=l;l=i;print n

```

Try it online!

# Answer
> 5 votes
# APL (dzaima/APL), 7 bytesSBCS

Anonymous tacit prefix function. Prints space-separated.

```
+\1,2≠/

```

Try it online!

`2≠/` pair-wise inequality

`1,` prepend 1

`+\` cumulative sum

# Answer
> 4 votes
# Jelly, ~~6~~ 5 bytes

```
ŒɠµJx

```

Try it online!

Saved one byte thanks to UnrelatedString!

Inputs and outputs as array's (with opening/closing brackets)

## How it works

```
ŒɠµJx - Main link, takes one argument:                       [7, 7, 5, 5, 5, 1]
Œɠ    - Get the lengths of consecutive elements:             [2, 3, 1]
  µ   - Call these lengths A
   J  - range(length(A))                                     [1, 2, 3]
    x - Repeat each element by the corresponding value in A: [1, 1, 2, 2, 2, 3]

```

# Answer
> 3 votes
# Jelly, 4 bytes

```
ŒgƤẈ

```

**Try it online!**

### How?

```
ŒgƤẈ - Link: list of integers  e.g. [7,7,2,7,7]
  Ƥ  - for prefixes:     [7]   [7,7]   [7,7,2]      [7,7,2,7]        [7,7,2,7,7]
Œg   -   group runs      [[7]] [[7,7]] [[7,7],[2]]  [[7,7],[2],[7]]  [[7,7],[2],[7,7]]
   Ẉ - length of each    [1,   1,      2,           3,               3]

```

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

Takes input as an array of integers.

```
a=>a.map(p=n=>i+=p!=(p=n),i=0)

```

Try it online!

### Commented

```
a =>                // a[] = input array
  a.map(p =         // initialize p to a non-numeric value
  n =>              // for each value n in a[]:
    i +=            //   increment i if:
      p != (p = n), //     p is not equal to n; and update p to n
    i = 0           //   start with i = 0 (chunk counter)
  )                 // end of map()

```

# Answer
> 2 votes
# Octave / MATLAB, 25 bytes

```
@(x)cumsum([1 ~~diff(x)])

```

Try it online!

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

```
Join@@(i=1;0#+i++&/@Split@#)&

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 5 bytes

```
¥Ā.¥>

```

Try it online!

# Answer
> 2 votes
# Haskell, 40 bytes

```
f(a:t)=1:map(+sum[1|a/=t!!0])(f t)
f e=e

```

Try it online!

# Answer
> 2 votes
# Perl 6, 21 bytes

```
{+<<[\+] $,|$_ Zne$_}

```

Try it online!

Anonymous code block that takes a list and returns a list. This works by comparing whether each pair of adjacent elements are not equal, than taking the cumulative sum of the list.

# Answer
> 2 votes
# 05AB1E, 4 bytes

```
γdƶ˜

```

Try it online!

```
γ       # group adjacent equal digits together
 d      # replace all digits with 1
  ƶ     # multiply each group by its 1-based index
   ˜    # flatten

```

# Answer
> 2 votes
# , 33 bytes

```
function(x)cumsum(c(1,!!diff(x)))

```

Try it online!

Uses the same cumulative sum method as Luis Mendo and others.

# Answer
> 2 votes
# MATL, 8 bytes

```
Y'wn:wY"

```

Try it online!

Explanation:

```
    Y'      % run-length encoding
    w       % swap elements in stack
    n       % number of elements in array / size along each dimension
    :       % range; vector of equally spaced values
    w       % swap elements in stack
    Y"      % replicate elements of array
            % (implicit) convert to string and display

```

# Answer
> 2 votes
# Oracle SQL, 121 bytes

```
select m from t match_recognize(order by i measures match_number()m all rows per match pattern(p+)define p as x=first(x))

```

Test in SQL\*PLus.

```
SQL> with t(i,x) as (select rownum,value(v) from table(sys.odcinumberlist(4, 4, 4, 7, 7, 9, 9, 9, 9, 2, 2, 2, 4, 4))v)
  2  select m from t match_recognize(order by i measures match_number()m all rows per match pattern(p+)define p as x=first(x))
  3  /

         M
----------
         1
         1
         1
         2
         2
         3
         3
         3
         3
         4
         4
         4
         5
         5

14 rows selected.

```

# Answer
> 1 votes
# Stax, 10 bytes

```
▓ª2ªmD?Ä╧╖

```

Run and debug it

The output uses space as a delimiter. The input follows the precise specifications using commas as separators, and now enclosing braces.

# Answer
> 1 votes
# Perl 5, 27 bytes

```
s/\d/$i+=$&!=$p;$p=$&;$i/ge

```

Try it online!

The command line option `-p` makes perl read the input line from STDIN into the "default variable" `$_`. It then search-replaces all digits in `$_` with the counter `$i`. And `$i` is increased for each digit which is different than the previous digit, which it also is at the first digit so the counter starts at `1`. The previous digit is stored in `$p`.

# Answer
> 1 votes
# Jelly, 5 bytes

```
nƝÄŻ‘

```

Try it online!

I initially aimed for a 4-byter (the same program but without the `Ż`) but then quickly realized that a **1** had to be prepended every time due to an oversight... Even though there is another 5-byter in Jelly, I'll actually keep this because it uses a different method.

For each pair of neighbouring items of the input list \\$L\\$, test if \\$L\_i\ne L\_{i+1}, \forall 1\le i\<|L|\\$ and save these results in a list. Then take the cumulative sum of this list and increment them by **1** to match the chunk indexing system. **TL;DR.** Whenever we encounter different neighbouring items, we increment the chunk index by **1**.

# Answer
> 1 votes
# Haskell, ~~46~~ 43 bytes

```
scanl(+)1.map fromEnum.(zipWith(/=)=<<tail)

```

Try it online!

Anonymous pointfree function that takes a list and returns a list

# Answer
> 1 votes
# C (gcc), 62 61 bytes

This is one of the few entries I've done where a complete program is shorter than a function submission!

On the first pass, I don't care about the previous value, so I get to rely on the fact that `argv` is a pointer to somewhere and is extremely unlikely to be between \[0..9\]!

```
s;main(i,j){for(;~scanf("%d,",&i);j=i)printf("%d ",s+=j!=i);}

```

Try it online!

# Answer
> 1 votes
# , 12 bytes

```
1+/\@,2~:/\]

```

Try it online!

Similar to Adám's APL answer

```
      2~:/\]  - pair-wise inequality
1    ,        - prepend 1
    @         - and
+/\           - find the cumulative sum

```

# Answer
> 1 votes
# Pyth, ~~13~~ 11 bytes

```
s.e*]hkhbr8

```

Try it online!

```
         r8  # Run-length encode (implicit argument is the input) (-> [[frequency, char], ...]
 .e          # Enumerated map (current element is b, index is k) over rQ8
   *]hk      # [ k+1 ] *
       hb    #           b[0]
s            # Reduce list on + ([a]+[b] = [a,b])

```

-2 bytes thanks to Mr. Xcoder

# Answer
> 1 votes
# Scala, 114 bytes

```
s.split(", ").zipWithIndex.scan(s.head,0){(a,b)=>if(a._1==b._1)a else b._1->(a._2+1)}.tail.unzip._2.mkString(", ")

```

Try it online!

# Answer
> 1 votes
# Scala, 75 bytes

```
s=>s.scanLeft(("",0))((x,y)=>(y,x._2+(if(x._1!=y)1 else 0))).tail.map(_._2)

```

Try it online!

If input and output must be comma separated **String** (and not List) then 102 bytes.

```
s=>s.split(", ").scanLeft(("",0))((x,y)=>(y,x._2+(if(x._1!=y)1 else 0))).tail.map(_._2).mkString(", ")

```

# Answer
> 1 votes
# C (gcc), 62 bytes

```
f(_,l)int*_;{printf("%d ",l=--l?f(_,l)+(_[l]!=_[l-1]):1);_=l;}

```

Try it online!

A function that takes the list and its length as arguments.

---

~~C (gcc), 60 bytes
```
f(_,l)int*_;{_=printf("%*d",--l?f(_,l)+(_[l]!=_[l-1]):2,0);}

```
Try it online!
~~

~~Outputs in unary, delimited by `0`s~~

# Answer
> 1 votes
# PHP, 52 bytes

```
while(''<$d=$argv[++$x])echo$i+=$argv[$x-1]!=$d,' ';

```

Try it online!

Input via command line, output to `STDOUT`.

Thx to @Night2 for the pesky `'0' == 0` comparison bugfix!

# Answer
> 1 votes
# x86-16, 12 bytes

**Unassembled listing:**

```
        NUM_LOOP:
AC          LODSB                   ; load [SI] into AL, advance SI
3A C2       CMP  AL, DL             ; is this char same as last?
74 01       JZ   SAME               ; if so, same index
43          INC  BX                 ; otherwise increment index
        SAME:
92          XCHG AX, DX             ; save current char for next compare
8A C3       MOV  AL, BL             ; put index value in AL to store
AA          STOSB                   ; store AL into [DI], advance DI
E2 F4       LOOP NUM_LOOP           ; keep looping

```

Input is byte array at `SI`, length in `CX`. Output is byte array at `DI`. Of course, this is if default I/O rules apply now.

**Example:** `SI = 120H`, `DI = 130H`

# Answer
> 1 votes
# Ruby, 38 bytes

```
->a{i=0;a.map{|x,y|p i+=(a==a=x)?0:1}}

```

Try it online!

On the first iteration, `a` is equal to the input list, so we always increment the chunk count. On subsequent iterations it's equal to the previous element.

# Answer
> 1 votes
# Julia 1.0, 56 bytes

```
l->foldl(l,init=(0,0))do(p,i),c
println(i+=p!=c)
c,i
end

```

Try it online!

# Answer
> 1 votes
# , 37 bytes

```
function(x,r=rle(x)$l)rep(seq(a=r),r)

```

Try it online!

Not as golfy as this answer, but an alternative method using `rep`.

# Answer
> 1 votes
# Desmos, 65 bytes

```
L=join(1,1-0^{(l[2...]-l)^2})
f(l)=∑_{n=1}^{[1...L.length]}L[n]

```

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 1 votes
# Factor, 45 bytes

```
[ 0 f rot [ tuck = rot dup 1 + ? tuck ] map ]

```

Try it online!

# Answer
> 1 votes
# Ly, 29 bytes

```
1sp&nry[pluy,[',o!]p=!l+spy]p

```

Try it online!

This one keeps a counter with the chunk number in the backup cell. That's incremented anytime the current codepoint doesn't match the next one on the list. The only other trick is the code to conditionally add the `,` delimiter if there's at least one more codepoint on the stack.

```
1sp                           - init the chunk number to 1, pop from stack
   &nr                        - read in list of digits as codepoints
      y[p                 y]p - loop as long as the stack isn't empty
         lu                   - load/print the chunk counter
           y,[   !]p          - if/then, true if there's 2+ digits left
              ',o             - print a comma delimiter
                    =!        - push "1" if the top 2 entries are not equal
                      l+sp    - increment chunk counter is digits differ

```

# Answer
> 1 votes
# BQN, 7 bytesSBCS

```
+`⊢≠π⊸»

```

Run online!

# Answer
> 1 votes
# Arturo, 40 bytes

```
$[a][p:10i:0map a'x[if p<>x[i:i+1p:x]i]]

```

Try it

```
$[a][                  ; a function taking an argument a
    p: 10              ; assign 10 to p
    i: 0               ; assign 0 to i
    map a 'x [         ; map over a; assign current element to x
        if p <> x [    ; if p doesn't equal x...
            i: i + 1   ; increment i
            p: x       ; assign x to p
        ]              ; end if
        i              ; map the current element to i
    ]                  ; end map
]                      ; end function

```

# Answer
> 1 votes
# Zsh, 38 bytes

Hat-tip to @pxeger. Try it online!

```
n=1;>$1;for i {mv * $i&&((n++));<<<$n}

```

First we write a file, `>$1`. Then for every argument `$i`:
* attempt to rename that file to `$i`
* if the rename succeeds, increment the chunk number `$n`
* print `$n`

---

#### 50 bytes (old approach)

Compares arguments. Try it online! ~~53 bytes~~ ~~57 bytes~~

```
n=1;set $@ $@[#];for i;echo $[$2==$1?n:n++]&&shift

```

# Answer
> 1 votes
# Thunno 2, 4 bytes

```
ƒ€ġḷ

```

Try it online!

#### Explanation

```
ƒ€ġḷ  # Implicit input
ƒ     # Prefixes
 €    # To each:
  ġ   #  Group consecutive
   ḷ  # Length of each
      # Implicit output

```

# Answer
> 1 votes
# Nekomata, 4 bytes

```
pNĉ#

```

Attempt This Online!

```
pNĉ#
pN      Nonempty prefix
  ĉ     Chunks of identical characters
   #    Length

```

# Answer
> 0 votes
# Japt v2.0a0, 9 bytes

```
£T±A¦(A=X

```

Try it

# Answer
> 0 votes
# Add++, 23 bytes

```
D,f,@*,BGd€bL$bLRz€¦XBF

```

Try it online!

## How it works

```
D,f,@*,     - Define a function, f, that takes one argument:  [7 7 5 5 5 1]
       BG   - Group neighbouring elements together:           [[[7 7] [5 5 5] [1]]]
       d    - Duplicate:                                      [[[7 7] [5 5 5] [1]] [[7 7] [5 5 5] [1]]]
       €bL  - Get the length of each:                         [[[7 7] [5 5 5] [1]] [2 3 1]]
       $bLR - Length, then range of length:                   [[2 3 1] [1 2 3]]
       z    - Zip together:                                   [[2 1] [3 2] [1 3]]
       €¦X  - Reduce each by repetition:                      [[1 1] [2 2 2] [3]]
       BF   - Flatten:                                        [1 1 2 2 2 3]
            - Due to the * in the function definition,
                 return the whole stack:                      [1 1 2 2 2 3]

```

# Answer
> 0 votes
# Japt, ~~8~~ 7 bytes

```
ä¦Ug)åÄ

```

Try it

# Answer
> 0 votes
# Retina 0.8.2, 34 bytes

```
\b\d+\b(?<=(\b(\3|(\d+))\D*)*)
$#3

```

Try it online! Explanation:

```
\b\d+\b

```

Match each number in turn.

```
(?<=(...)*)

```

Start looking backwards for as many matches as possible. (The next entries will be in right-to-left order as that's how lookbehind works.)

```
\D*

```

Skip the separators.

```
(\3|(\d+))

```

Try to match the same number as last time, but failing that, just match any number, but remember that we had to match a new number.

```
\b

```

Ensure the whole number is matched.

```
$#3

```

Count the number of new numbers.

# Answer
> 0 votes
# Alice, 28 bytes

```
0wi.hn$@.?-..3&$!h0;./ O \K

```

Try it online!

Takes the input as a string with no separators, outputs a string separated by new line

## Explanations

```
0                             Initialise the counter at 0 on the stack
 wi.hn$@                  K   Main loop, while there are characters to read on the input
        .?-    $   ;          If the number read is the same as the number on the tape, discard it
           ..3& !h0           Otherwise, store the new number on the tape and increment the counter
                    ./ O \    Print the counter and a new line

```

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