title: Extract Strings from Text

text:
# Question
Title: Extract Strings from Text
In some languages, strings are started and ended with a quote mark (`'`). And quote itself is escaped by writing it twice sequentially. For example, empty string is written as `''`, and `I'm` is written as `'I''m'`.

This question is about find out all non-overlapping strings from left to right in such format from the given input, while ignoring anything between or around these string literals.

## Input / Output

You are given a string contains only printable ASCII. Quotes (`'`) in inputs are always paired. And you need to find out all non-overlapping quoted strings in it. Output these strings in the order they appeared.

You are free to choose any acceptable I/O format you want. However, **formats of strings for input and output MUST be the same**. Which means that you cannot take raw string as input, and claim that your output string are formatted in quotes, with quotes escaped by writing twice. As this may trivialize the challenge.

## Test Cases

All testcases here are written in JSON format.

```
Input           -> Output         # Comment (not a part of I/O)
"abc"           -> []             # text out side quotes are ignored
"''"            -> [""]           # '' is an empty string
"''''"          -> ["'"]          # two sequential quotes in string converted into a single one
"'abc'"         -> ["abc"]
"a'b'"          -> ["b"]
"'b'c"          -> ["b"]
"a'b'c"         -> ["b"]
"abc''def"      -> [""]
"'' ''"         -> ["", ""]       # there are 2 strings in this testcase
"'abc' 'def'"   -> ["abc", "def"]
"'abc'def'ghi'" -> ["abc", "ghi"] # separator between strings could be anything
"'abc''def'"    -> ["abc'def"]
"a'bc''de'f"    -> ["bc'de"]
"''''''"        -> ["''"]
"'''a'''"       -> ["'a'"]
"''''a''"       -> ["'", ""]
"''''''''"      -> ["'''"]
"'abc\"\"def'"  -> ["abc\"\"def"] # double quotes do not have special meanings
"'\\'\\''"      -> ["\\", ""]     # backslashes do not have special meanings
"'a'#48'b'"     -> ["a", "b"]     # hash signs do not have special meanings
"a,'a','a,''a''','a,''a'',''a,''''a'''''''" -> ["a", "a,'a'", "a,'a','a,''a'''"] # Testcase suggested by Command Master

```

And here are above testcases formatted with line breaks.

## Rules

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

```
=”'ŻḂ+¥\¬Ä×ḂƲḊƙŻḊ

```

Try it online!

Inspired by the prevalence of regex solutions, the core of the logic is a scan by the state transition table

|  | \\$0\\$ | \\$1\\$ | \\$2\\$ |
| --- | --- | --- | --- |
| a quote | \\$1\\$ | \\$2\\$ | \\$1\\$ |
| not a quote | \\$0\\$ | \\$1\\$ | \\$0\\$ |

which fortunately simplifies pretty nicely to `Ḃ+`. \\$0\\$ is anything non-string, \\$1\\$ is an opening quote or anything inside a string, and \\$2\\$ is a closing quote or the first quote of an escape pair.

```
=”'                  For each character, is it a quote?
   Ż                 Prepend a 0, then
    Ḃ+¥\             scan by the table.
              ƙ      Group the input
               Ż     with a 0 prepended
        ¬Ä           by the cumulative number of zeroes in the scan result
          ×ḂƲ        multiplied by the result mod 2,
             Ḋƙ      remove the opening quote from each group,
                Ḋ    and remove the 0 group (everything outside a string).

```

# Answer
> 6 votes
# Pip, 19 bytes

```
TMa@+`'.*?'`R"''"''

```

Try It Online!

-11 bytes thanks to DLosc.

<pre><code>  a@                # Match in input
    +`'.*?'`        # A regex
TM                  # Remove the first and last
            R"''"'' # Unescape '

```
</code></pre>

# Answer
> 5 votes
# Retina 0.8.2, 25 bytes

```
M!`('.*?')+
%`^'|'$

''
'

```

Try it online! Outputs each string on its own line but link wraps each test case in `[` and `]` to make it easier to tell where each output starts and ends. Explanation:

```
M!`('.*?')+

```

List all of the matched strings, still quoted.

```
%`^'|'$

```

Remove the leading and trailing quotes.

```
''
'

```

Deduplicate the interior quotes.

# Answer
> 4 votes
# , 83 bytes

```
\(x)gsub("''","'",substring(a,p<-el(gregexpr("'(''|[^'])*'",a))+1,p+attr(p,"m")-3))
```

Attempt This Online!

Same regex-based approach as emanresu A's answer.

# Answer
> 4 votes
# , 31 bytes

```
'''(''''|[^''])*'''".&.>@rxall]
```

Attempt This Online!

Mostly a port of emanresu A's answer.

The only difference is that after cutting out the quote pieces, we simply evaluate the resulting quoted string to handle the unescaping. This works because J is one of the languages described by this challenge, which also explains all the escaping in the regex.

# Answer
> 4 votes
# 05AB1E, ~~35~~ ~~29~~ ~~28~~ ~~21~~ ~~16~~ 15 bytes

```
''¡¦ι`õÊ0šÅ¡''ý

```

Try it online, or try all testcases

Outputs an empty string if there are no strings. If it has to be an empty array, it's +1 for placing `ε` before `''ý`

## Explanation

```
''¡   split on quotes the implicit input
      (e.g. ["a,", "a", ",", "a,", "", "a", "", "", ""], for a,'a','a,''a''')
¦     tail, remove the first part
      (e.g. ["a", ",", "a,", "", "a", "", "", ""])
ι     uninterleave
      (e.g. [["a", "a,", "a", ""], [",", "", "", ""]])
`     dump to stack
õ     push an empty string
Ê     for each odd-indexed part, check if it's not equal to it
      (e.g. [1, 0, 0, 0])
0š    prepend a zero
      (e.g. [0, 1, 0, 0, 0])
Å¡    split the even-indexed parts on indices
      the odd-indexed parts aren't empty
      (e.g. [["a"], ["a,", "a", ""]])
''ý   join each on a quote
      (e.g. ["a", "a,'a'"])

```

# Answer
> 3 votes
# C (gcc), ~~112~~ 95 bytes

* -5 thanks to ceilingcat
* -12 thanks to suggestions from tsh

Implements a simple state machine to determine whether the parser is inside a string.

```
#define P putchar(
t;f(char*s){for(t=0;*s;)t?*s-39?P*s++):*++s-39?t=0:P*s++):*s++-39||P t=10);}

```

Try it online!

Annotated:

```
t;f(char*s){
  for(t=0;*s;) // initialize state to search mode
    t? // is inside the string?
      *s-'\''? // found quote?
        putchar(*s++): // not quote, print it
        *++s-'\''? // double quote?
          t=0: // reset state to search
          putchar(*s++): // print quote
      *s++-'\''||  // found initial quote?
        putchar(t=10); // print newline, set state
}

```

# Answer
> 3 votes
# C (gcc), 71 bytes

```
t,n;f(char*s){n=*s==39^t;t=n?t&&putchar(n%2?*s:10),n%2:t+t;*s&&f(s+1);}

```

Try it online!

| State `t` | Input `*s` | Output | Next | `n` | `n%2` | `t+t` |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | quote | empty | 1 | 1 | 1 | - |
| 0 | others | empty | 0 | 0 | - | 0 |
| 1 | quote | empty | 2 | 0 | - | 2 |
| 1 | others | as-is | 1 | 1 | 1 | - |
| 2 | quote | as-is | 1 | 3 | 1 | - |
| 2 | others | line-break | 0 | 2 | 0 | - |

# Answer
> 3 votes
# BQN, 39 bytes

```
1⊸↓¨(-⟜1·2⊸|⊸×⟜(+`·»⊸<×)·2⊸|⊸+`=⟜''')⊸⊔

```

Try it at BQN online!

### Explanation

The core logic is taken from Unrelated String's Jelly answer:

```
2⊸|⊸+`=⟜'''
      =⟜'''  Compare each character with ' character (1 if equal, 0 if not equal)
     `       Scan left-to-right on this function:
   ⊸+        Add the current value to
2⊸|          the accumulated value mod 2

```

This results in a list where:

* 0 represents a character outside any of the strings
* 1 represents an opening quote or a regular character inside a string
* 2 represents a close quote or the first of a pair of quotes

Next,

```
-⟜1·2⊸|⊸×⟜(+`·»⊸<×)
                   ×   Get the sign of each number (0 -> 0; 1,2 -> 1)
                  <    Compare each item in that list with
                »⊸     the corresponding item in that list shifted to the right
                       This gives 1 at the beginning of each run of nonzeros, 0 elsewhere
            +`·        Cumulative sum
                       We now have a list of nondecreasing nonnegative numbers the same
                       length as the main list, such that the runs of nonzeros in the
                       main list are numbered 1, 2, 3, ...
        ⊸×⟜(      )   Multiply that list of numbers by
     2⊸|               the main list mod 2
                       This puts zeros at every index where the main list has 0 or 2
                       (i.e. characters outside of strings, close quotes, and one quote
                       out of every escaped pair)
-⟜1·                  Subtract 1 from each (zero becomes -1, and group numbers start at 0)

```

For example (`-` represents `-1`):

```
Input:  a'b''c'd''e'''f'
Result: -00-00--1--2-22-

```

Then:

```
1⊸↓¨(...)⊸⊔
         ⊸⊔  Group the string into buckets
    (...)     specified by the result of the above function
1⊸↓¨         Drop the first character (opening quote) from each bucket

```

# Answer
> 2 votes
# Charcoal, ~~27~~ 22 bytes

```
⪫Ｅ✂⪪Ｓ'¹±¹¦¹⎇﹪κ²⎇ι¶¦'ιω

```

Try it online! Link is to verbose version of code. Outputs a newline-separated list. Explanation: Now based on @CommandMaster's 05AB1E answer.

```
    Ｓ                   Input string
   ⪪ '                  Split on literal string `'`
  ✂   ¹±¹¦¹             Slice off first and last piece
 Ｅ                      Map over remaining pieces
             κ          Current index
            ﹪           Modulo
              ²         Literal integer `2`
           ⎇            If current index is odd
               ⎇ι       If current piece is not empty
                 ¶      Replace with newline
                   '    Else replace with literal string `'`
                    ι   Keep even pieces
⪫                    ω  Join together
                        Implicitly print

```

# Answer
> 1 votes
# Python, 82 bytes

```
lambda s:[re.sub("''","'",x[1:-1])for x in re.findall("(?:'[^']*')+",s)]
import re
```

Attempt This Online!

Similar but not exactly the same regex as all the other answers.

### Python, 80 bytes (using @Neil's non-greedy regex)

```
lambda s:[re.sub("''","'",x[1:-1])for x in re.findall("(?:'.*?')+",s)]
import re
```

Attempt This Online!

# Answer
> 1 votes
# Vyxal, 21 bytes

```
`(?:'€?')+`ẎƛḢṪ‛''\'V

```

Try it Online!

Regex in golflangs go brr

Uses @Neil's regex, go upvote that.

# Answer
> 1 votes
# Pip, ~~28~~ 31 bytes

This non-regex solution ended up considerably longer than the regex solution, but I thought it was still interesting enough to post.

```
YUW:a^''y@1WV(#_\?n''M H S@y)|u

```

Outputs each string on a separate line. Try It Online!

### Explanation

```
    a^''                         Split input string on single-quote character
 UW:                             Unweave into two sublists of every other item
Y                                Yank into y
                          @y     Take the first sublist (substrings "outside" the quotes)
                       H S       Remove the first and last elements
                     M           Map this function to the remaining elements:
              #_                   Length of substring
                \?                 is nonzero?
                  n                If so, newline
                   ''              If not, single-quote character
        y@1WV(              )    Weave the other sublist with that result
                             |u  If list is empty, use nil instead to suppress printing
                                 Join together and autoprint (implicit)

```

The idea here is to consider the quotes in pairs. When the end of one matched pair of quotes is immediately followed by the beginning of another pair, that represents an escaped quote (so we reintroduce a quote character); when there are some characters between the end of one pair and the beginning of the next, that represents two separate strings (so we introduce a newline).

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


title: Expected number of trailing zeros

text:
# Question
Title: Expected number of trailing zeros
# Input

A bound m \<= 4294967295.

# Output

Consider values sampled uniformly at random from integers in the range 0 to m, inclusive.

Your output should be the expected (average) number of trailing zeros in the binary representation of the sampled value. Your answer should be exact, for example given as a fraction.

# Example

* m = 0. The answer is 1. 0 will be sampled with prob 1.
* m = 1. The answer is 1/2. 0 with prob 1/2 and 1 with prob 1/2.
* m = 2. The answer is 2/3. 0 and 2 have one trailing zero.
* m = 3. The answer is 1/2. 0 and 2 have one trailing zero.

# Answer
> 11 votes
# Python, 36 bytes

```
lambda m:(m+1-bin(m).count('1'),m+1)

```

Try it online!

A formula!

$$ f(m) = 1 - \frac{\text{#ones in bin}(m)}{m+1} = \frac{m+1-\text{#ones in bin}(m)}{m+1}$$

# Answer
> 6 votes
# APL (Dyalog Unicode), 16 bytes

```
{1+⍵,+/⌊⍵÷2*⍳32}

```

Try it online!

\\$\frac{1+\sum\_{i=1}^{32}\left\lfloor\frac{m}{2^i}\right\rfloor}{1+m}\\$. returns denominator,numerator. uses `⎕io=1`.

# Answer
> 5 votes
# MATL, 14 bytes

```
:B!P&X>qtswnhQ

```

The code uses brute force: computes the binary expansion of all the numbers in the specified range and counts trailing zeros.

Output is numerator, then denominator.

Try it online!. You can also see the first outputs, or plot them to see some interesting trends (more on this below).

## How the code works

```
:    % Implicit input: m. Range [1 2 ... m]. Note that 0 is not included
B    % Convert to binary. Gives a matrix, with the binary expansion of each
     % number on a different row, left-padded with zeros if needed
!    % Transpose
P    % Flip vertically. Now each binary expansion if in a column, reversed
&X>  % Argmax of each column. This gives a vector with the position of the
     % first 1 (the last 1 in the non-reversed expansion) for each number
q    % Subtract 1, element-wise. This gives the number of trailing zeros
     % in the binary expansion of each number
t    % Duplicate
s    % Sum
w    % Swap
n    % Number of elements
h    % Concatenate both numbers horizontally
Q    % Add 1 to each number, to account for the fact that 0 has not been
     % considered. Implicit display

```

## Some interesting properties of the sequence

Let \\$a(m)\\$ denote the sequence. Then

1. \\$a(m) = m/(m+1)\\$ when \\$m\\$ is a power of \\$2\\$.
2. If \\$m\\$ is a power of \\$2\\$, \\$a(n) \< a(m)\\$ for all \\$n\ \< 2m, n \neq m\\$.
3. \\$\lim\sup\_{m \rightarrow \infty} a(m) = 1\\$.

### Proof of 1

Let \\$m\\$ be a power of \\$2\\$. Consider the set \\$\\{1,2,\ldots,m\\}\\$. In this set, \\$m/2\\$ members are multiples of \\$2\\$, and thus have at east a trailing zero. \\$m/4\\$ members are multiples of \\$4\\$, and contribute one additional trailing zero, etc. There is only one multiple of \\$m\\$. So the total number of trailing zeros is \\$m/2 + m/4 + \cdots + 1 = m-1\\$, and the fraction of trailing zeros in the set \\$\\{1,2,\ldots,m\\}\\$ is \\$(m-1)/m\\$. Therefore in the set \\$\\{0,1,2,\ldots,m\\}\\$ it is \\$m/(m+1)\\$.

### Proof of 2

The proof uses mathematical induction.

For \\$m=2\\$ the claimed property holds.

Let \\$m\\$ be an arbitrary power of \\$2\\$. Assume that the property holds for \\$m/2\\$. Combined with property 1 this implies that, for all \\$k\<m\\$, \\$a(k) \leq a(m/2) = m/(m+2) \< m/(m+1)\\$.

Consider the numbers \\$m+1, m+2, \ldots, 2m-1\\$. Their trailing zeros are the same as those of \\$1, 2, \ldots, m-1\\$ respectively (the binary expansions only differ in a leading string formed by a one and some zeros, which doesn't affect). For \\$k\<m\\$, using property 1 again the term \\$a(m+k)\\$ can be expressed as \\$(m+j)/(m+1+k)\\$, where \\$j\\$ is the total number of trailing zeros in \\$\\{m+1,\ldots,m+k\\}\\$, or equivalently in \\$\\{1,\ldots,k\\}\\$. Since \\$a(k) = j/k \< m/(m+1)\\$, it holds that \\$(m+j)/(m+1+k) \< m/(m+1)\\$.

Therefore the property is satisfied for \\$m\\$.

### Proof of 3

From proerties 1 and 2, \\$\lim\sup\_{n \rightarrow \infty} a(n) = \lim\_{m \rightarrow \infty} m/(m+1) = 1\\$.

# Answer
> 5 votes
# K (ngn/k), ~~13~~ 12 bytes

```
{1+x,x-/2\x}

```

Try it online!

like xnor's

`{` `}` function with argument `x`

`2\` binary digits

`x-/` reduction with minus, using `x` as initial value

`x,` prepend `x`

`1+` add 1 to both in the pair

# Answer
> 5 votes
# APL (Dyalog Extended), 9 bytes

```
-\1∘+,1⊥⊤

```

Try it online!

Yet another port of xnor's Python answer. A tacit function that takes `n` and returns `(denom, num)`.

### How it works

```
-\1∘+,1⊥⊤  ⍝ Input: n
      1⊥⊤  ⍝ Popcount(n)
  1∘+,     ⍝ Pair with n+1
-\         ⍝ Minus scan; convert (a,b) to (a,a-b)

```

# Answer
> 4 votes
# , 13 12 10 bytes

```
1-+/@#:%>:

```

Try it online!

*-12 bytes thanks to the forumula of xnor*

*-2 bytes thanks to Bubbler's idea of making the input extended precision rather than converting inside my verb*

## how

One minus `1-` the sum of `+/@` the binary representation of the input `#:` divided by `%` the input plus one `>:`.

# original

# , 24 bytes

```
(,1#.i.&1@|.@#:"0@i.)@>:

```

Try it online!

Outputs as (denominator, numerator)

# Answer
> 3 votes
# JavaScript (ES6),  ~~35~~  33 bytes

Outputs the fraction as `[numerator, denominator]`.

```
n=>[(g=k=>k?g(k&k-1)-1:++n)(n),n]

```

Try it online!

The recursive formula for the numerator was initially derived from A101925, which itself is defined as A005187(n) + 1:

```
(g=n=>n&&g(n>>1)+n)(n)-n+1

```

Once golfed some more, it turns out to be equivalent to @xnor's formula.

# Answer
> 3 votes
# 05AB1E, 7 bytes

```
!Ò2¢s‚>

```

Try it online!

The number of trailing zeros is the same as the multiplicity of \\$2\\$ in the prime factorization (for \\$n \ne 0\\$). This means we just need to count the number of times \\$2\\$ divides \\$m!\\$.

```
!        factorial
 Ò       prime factorization
  2¢     count 2's
    s‚   swap and pair (with input)
      >  increment both

```

If output as `[denominator, numerator]` is fine, `!Ò2¢‚>` works at 6 bytes.

---

# 05AB1E, 8 bytes

An implementation of xnor's formula.

```
b1¢(0‚>+

```

Try it online!

There may be a shorter way to count set bits than `b1¢`.

```
          implicit input  m

b         to binary       bin(m)
 1¢       count 1's       bin(m).count('1')
   (      negative        -bin(m).count('1')
    0‚    pair with 0     [-bin(m).count('1'), 0]
      >   increment       [1-bin(m).count('1'), 1]
       +  add input       [m+1-bin(m).count('1'), m+1]

          implicit output

```

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

```
1-DigitCount[#,2,1]/(#+1)&

```

Try it online!

# Answer
> 2 votes
# Python 3, ~~65~~ 64 bytes

```
lambda m:(sum(bin(i+1)[:1:-1].find('1')for i in range(m))+1,m+1)

```

Try it online!

Returns the fraction as tuple `(denominator, numerator)`.

# Answer
> 2 votes
# Pyth, 12 bytes

```
,KhQ-K/.BQ"1

```

Try it online!

Explanation:

```
,             // Print the following two evaluations as [X,Y]
 KhQ          // Denominator = input + 1 and store it in K
      /.BQ"1  // Convert input to binary and count 1's
    -K        // K(input + 1) - number of binary ones

```

Outputs `[denominator, numerator]`

# Answer
> 2 votes
# \>\<\>, 37 bytes

```
1&l:{:})?\:2%0=?v&!
  ;n,+1{&/,2&+1&<

```

Try it online!

No built-ins to deal with binary representations, so a costly mod`%` loop is necessary.

A trick used here is to just let the stack grow, since that makes a counter instantly available with only a single `l` command.

# Answer
> 2 votes
# PHP, 44 bytes

```
fn($m)=>[$m-substr_count(decbin($m++),1),$m]

```

Try it online!

It's @xnor's formula with a minor optimization.

# Answer
> 2 votes
# x86\_64 machine code, 15 bytes

```
f3 48 0f b8 c7    popcnt rax,rdi    # rax = number of 1's in m
48 ff c7          inc    rdi        # increment denominator
48 89 fe          mov    rsi,rdi    # rsi = rdi (m + 1)
48 29 c6          sub    rsi,rax    # rsi = rsi (m + 1) - rax (popcount of m)
c3                ret

```

Input: `m` in `rdi`, output: `[ rsi, rdi ]`. Works for values `m <= 4294967295`.

Try it online!

*Or original 16-bit version...*

# x86-16 machine code, ~~19~~ 17 bytes

Binary:

```
00000000: 8bd0 33db d1e8 7301 4375 f942 8bc2 2bc3  ..3...s.Cu.B..+.
00000010: c3                                       .

```

Listing:

```
8B D0       MOV  DX, AX         ; save m for denominator
33 DB       XOR  BX, BX         ; BX is bit count of 1's
        POP_COUNT:
D1 E8       SHR  AX, 1          ; shift LSb into CF
73 01       JNC  IS_ZERO        ; if a 0, don't increment count
43          INC  BX             ; increment count of 1 bits
        IS_ZERO:
75 F9       JNZ  POP_COUNT      ; if AX not 0, keep looping
42          INC  DX             ; increment denominator
8B C2       MOV  AX, DX         ; AX = DX (m + 1)
2B C3       SUB  AX, BX         ; AX = AX (m + 1) - BX (popcount of m)
C3          RET

```

Callable function, input `m` in `AX` output `[ AX, DX ]`. Works for values `m <= 65534` (platform max int).

Test program output:

# Answer
> 2 votes
# Jelly, 6 bytes

```
BS’ạ,‘

```

A monadic Link accepting an integer which yields a pair of integers, `[numerator, denominator]`.

**Try it online!** Or see 0-40 inclusive.

---

Or, also for 6:

```
!Ḥọ2,‘

```

# Answer
> 1 votes
# Python 3, 76 bytes

```
lambda m:(sum(len(bin(i))-len(bin(i).strip("0"))-1 for i in range(m+1)),m+1)

```

Fraction is returned as a tuple `(numerator,denominator)`

Non-golfed version:

```
def trailing_zeroes(m):
    #this is the running total for the total number of trailing zeroes
    total = 0
    #this loops through each the number in the range
    for i in range(m+1):
        #calculates number of trailing zeroes
        zeroes = len(bin(i))-len(bin(i).strip("0"))-1
        #adds the number of trailing zeroes to the running total
        total += zeroes
    #returns the numerator and the denominator as a tuple
    return (total, m+1)

```

Try it online!

# Answer
> 1 votes
# C (gcc), ~~52~~ 49 bytes

Saved 3 bytes thanks to Mukundan314!!!

```
f(int*m,int*n){*n=++*m-__builtin_popcount(*m-1);}

```

Try it online!

Port of xnor's Python answer.

# Answer
> 1 votes
# Charcoal, 11 bytes

```
Ｉ⟦⁻⊕θΣ⍘Ｎ²⊕θ

```

Try it online! Link is to verbose version of code. Port of @xnor's Python answer. Explanation:

```
    θ       Input `m` as a string
   ⊕        Cast to integer and increment
       Ｎ    Input `m` as an integer
      ⍘ ²   Convert to base 2 as a string
     Σ      Sum the digits
  ⁻         Subtract
          θ Input `m` as a string
         ⊕  Cast to integer and increment
 ⟦          Make into a list
Ｉ           Cast to string
            Implicitly print on separate lines

```

# Answer
> 1 votes
# Io, 55 bytes

```
method(I,list(I-I toBase(2)occurancesOfSeq("1")+1,I+1))

```

Try it online!

# Answer
> 1 votes
# Java 8, 27 bytes

```
n->-n.bitCount(n++)+n+"/"+n

```

Port of *@xnor*'s Python answer, so make sure to upvote him as well!

Try it online.

**Explanation:**

```
n->                 // Method with Integer as parameter and String return-type
  -                 //  Take the negative value of:
   n.bitCount(n++)  //   The amount of 1-bits in integer `n`
                    //   (and increase `n` by 1 afterwards with `n++`)
    +n              //  And add (the now incremented) `n` to this
  +"/"              //  Append a "/" String
  +n                //  And append `n`

```

# Answer
> 1 votes
# MathGolf, 7 bytes

```
âΣ~bα⌠+

```

Port of *@xnor*'s Python answer, so make sure to upvote him as well!

Try it online.

**Explanation:**

```
â        # Convert the (implicit) input-integer to a list of binary digits
 Σ       # Sum that list to get the amount of 1-bits
  ~      # Bitwise-NOT that (-n-1)
   b     # Push -1
    α    # Pair the two together
     ⌠   # Increment both values in the pair by 2
      +  # And add the (implicit) input-integer to both
         # (after which the entire stack joined together is output implicitly)

```

# Answer
> 1 votes
# Husk, 6 bytes

```
A:1↑İr

```

Try it online! This function just takes the average of the start of the ruler sequence.

# Answer
> 0 votes
# Japt, 10 bytes

Adapted from xnor's solution. Input is a single integer array, output is `[numerator, denominator]`.

```
ËÒ-¤è1Ãp°U

```

Try it

# Answer
> 0 votes
# APL, 17 bytes

```
{⍵+1-+⌿2⊥⍣¯1⊢⍵,0}

```

The solution is not as concise as the previous ones, but it has its merits. It does not depend on the APL dialect or on the index origin. In addition, it returns the result in the intuitively expected form: nominator, denominator.

---
Tags: code-golf
---


title: Where are my pennies?

text:
# Question
Title: Where are my pennies?
Given string `S` representing a dollar amount, make change for that amount of money use the least number of coins to make the change and record the amount of each coin in a list. Here are the coins available to use and their value.

```
Coin : Value
Dollar Coins : $1.00
Quarters: $0.25
Dimes: $0.10
Nickels: $0.05
Pennies: $0.01

```

## Input

String `S` that contains the dollar symbol `$` and the dollar amount.

## Output

List of coin numbers separated by a space character `" "`. The list must be in this order: Dollar coins, quarters, dimes, nickels, pennies.

## Constraints

* `$0.00 < S < $10.00`
* `S` is given to two decimal places.
* make change for that amount of money use the least number of coins

## Example Input

`$4.58`

`$9.99`

## Output

`4 2 0 1 3`

`9 3 2 0 4`

## Win Condition

shortest bytes win.

# Answer
# 05AB1E, ~~24~~ 17 bytes

~~¦'.¡`25‰`10‰`5‰`r5F?' ?}~~

```
¦'.¡`25‰`T‰`5‰`ðý

```

Try it online!

My first attempt at it. It's very verbose in my opinion and I'll look at further revising this answer. Maybe somebody better than me will figure it out.

**Explanation**

```
¦             # Remove '$' from input
'.¡           # Push '.' and split string on that. (dollar),(cents) is result
`25‰          # Push all items onto stack and mod top by 25
`T‰           # Push all items onto stack and mod top by 10
`5‰           # Push all items onto stack and mod top by 5
`r            # Push all items onto stack and reverse stack
ðý            # Loop through stack and print each element with space

```

-7 bytes thanks to Emigna
> 3 votes

# Answer
# Python 2, ~~79~~ ~~72~~ 71 bytes

```
s=input()
d=int(s[1]+s[3:])
for c in(100,25,10,5,1):print d/c,;d-=d/c*c

```

Try it online!

Saved 7 bytes thanks, in part, to Chas Brown

Saved a byte thanks to Jo King
> 5 votes

# Answer
# Hexagony, ~~35~~ ~~32~~ ~~28~~ 27 bytes

```
]{=?2'?!/@[1[5/P0;:!%'[01[5

```

Try it online!

There are no no-ops `.` now, ~~so it must be optimal~~.
> 5 votes

# Answer
# Octave, 106 bytes

```
@(n)[k=(f=@fix)(x=str2num(n(2:5))),m=f(4*(x-k)),t=f(10*(s=x-k-.25*m)),p=f(20*(s-.1*t)),100*(s-.1*t-.05*p)]

```

Try it online!

16 bytes is used simply to get rid of `$` and convert the string to a number. The rest is simply removing the as many coins as possible, one value at a time.
> 2 votes

# Answer
# Stax, ~~18~~ 17 bytes

```
ä┐¢6ⁿ≡♠₧ç7╦Δ╛XÄR│

```

Run and debug it
> 1 votes

# Answer
# , 81 bytes

```
x=as.double(substr(scan(,""),2,6));for(i in 1/c(1,4,10,20,100))x=x-i*print(x%/%i)

```

Try it online!

26 bytes ensuring the data are a `double` rather than a string, very nearly a third of the program! That's lame, to say the least.
> 1 votes

# Answer
# Ruby, 74 bytes

```
->s{n=s.delete("$.").to_i;["%s"]*5*" "%[n/100,n/25%4,(m=n/5%5)/2,m%2,n%5]}

```

Try it online!

Converts input to an integer containing number of pennies, then applies formulas in the `[]` at the end.

```
5 bytes standard Ruby boilerplate ->s{}
34 bytes on solving the problem
35 bytes on formatting

```
> 1 votes

# Answer
# Julia, ~~72~~ 71 bytes

```
!s=(x=parse(Int,filter(>('.'),s));[100,25,10,5,1].|>u->(t=x÷u;x%=u;t))
```

Attempt This Online!

* -1 byte: `x=x%u` -\> `x*=u` \- thanks to @MarcMush
> 1 votes

# Answer
# Java 8, 138 bytes

```
s->{long p=new Long(s.replaceAll("\\D","")),c,i=100;for(s="";i>0;s+=c+" ",i=i>25?25:i>10?10:i>5?5:i>1?1:0)for(c=0;p>=i;p-=i)c++;return s;}

```

**Explanation:**

Try it online.

```
s->{              // Method with String as both parameter and return-type
  long p=new Long(s.replaceAll("\\D","")),
                  //  Remove all non-digits, and convert it to a number
       c,         //  Count-integer
       i=100;     //  Amount integer, starting at 100
  for(s="";       //  Set the input to an empty String, because we no longer need it
      i>0         //  Loop as long as `i` is not 0
      ;           //    After every iteration:
       s+=c+" ",  //     Append the count and a space to `s`
       i=i>25?    //     If `i` is 100:
          25      //      Change it to 25
         :i>10?   //     Else-if `i` is 25:
          10      //      Change it to 10
         :i>5?    //     Else-if `i` is 10:
          5       //      Change it to 5
         :i>1?    //     Else-if `i` is 5:
          1       //      Change it to 1
         :        //     Else (`i` is 1)
          0)      //      Change it to 0
    for(c=0;      //   Reset the count `c` to 0
        p>=i;     //   Inner loop as long as `p` is larger than or equal to `i`
        p-=i)     //     After every iteration: subtract `i` from `p`
      c++;        //    Increase the count `c` by 1
  return s;}      //  Return the result

```
> 0 votes

---
Tags: code-golf
---


title: Write out the Thue-Morse sequence

text:
# Question
Title: Write out the Thue-Morse sequence
There's quite a few challenges on this site that ask you to print out a sequence, and this is no exception.

(The following explanation of the sequence for this challenge assumes the symbols in the sequence are `0` and `1`.)

The recursive definition of the Thue-Morse sequence is that

```
T_0 = 0
T_2n = T_n
T_2n+1 = 1 - T_n

```

A more direct definition is that the sequence from `0` to `2**m-1` and `2**m to 2**(m+1)-1` are binary complements. So `0` is followed by `1`, `01` is followed by `10`, `0110` is followed by `1001`, and, skipping ahead a bit, `0110100110010110` is followed by `1001011001101001`.

The challenge is to write a program or a function that prints out the Thue-Morse sequence for the first `n` elements, where `n` is any non-negative integer. The output can use any two symbols, as shown in the examples below.

**Examples**

```
>>> tm_01(20)
01101001100101101001
>>> tm_ab(42)
abbabaabbaababbabaababbaabbabaabbaababbaab
>>> tm_paren(37)
())()(())(()())()(()())(())()(())(()(
>>> tm_space_star(12)
 ** *  **  *
>>> tm_01(0)
                # to show that this is a valid input

```

**Rules**

* The input will be any non-negative integer. You can assume all inputs are valid.
* The output must be the first `n` elements of the Thue-Morse sequence, using any symbols that are convenient. If you like, you can also add a separator. In my examples, I have not. **Note:** This rule allows lists (like those of Python), as `,` is a valid separator and I don't mind leading or trailing characters, such as `[` and `]` in the output.
* This is code golf, so the smallest number of bytes wins.

As always, if the problem is unclear, please let me know. Good luck and good golfing!

## Catalogue

```
var QUESTION_ID=65549;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://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"http://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.toLowerCase(),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>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}
```

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

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="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
> 14 votes
# Pyth, 6 bytes

```
xMjR2Q

```

Try it online: Demonstration

Based on the solution from @ThomasKwa and a variation of @FryAmTheEggman.

It uses the following formular: the `i`-th digit in the Thue-Morse sequence is: `xor(digits of i in base 2)`.

### Explanation:

```
xMjR2Q   implicit: Q = input number
  jR2Q   convert each number in [0, 1, ..., Q-1] to its binary digits
xM       xor each binary list

```

# Answer
> 9 votes
## CJam, ~~17~~ 9 bytes

```
ri{2b:^}/

```

or

```
ri,2fb::^

```

Test it here.

### Explanation

This uses the alternative definition given on Wikipedia, based on the parity of the number of `1`s in the binary representation of the `n`.

```
ri   e# Read input and convert to integer n.
{    e# For each i from 0 to n-1...
  2b e#   Convert i to base 2.
  :^ e#   Fold XOR over the bits to compute the parity of the number of 1s.
}/

```

The alternative solution uses `,` to turn `n` explicitly into a range `[0 ... n-1]` before using infix operators to compute the binary representations and the XOR without needing a block.

### Bonus Solutions

Here are some solutions based on other definitions. If there are two solutions, the shorter one will blow up memory *very* quickly (because the precomputation generates `2^n` bits before truncating to `n`).

As an L-system with `0 --> 01` and `1 --> 10`:

```
ri_2mL2,\{2,aA+f=s:~}*<
ri_2,\{2,aA+f=s:~}*<

```

By negating and appending the previous part:

```
ri_2mL2,\{_:!+}*<
ri_2,\{_:!+}*<

```

Using the recurrence relation given in the challenge, using `divmod` and XOR to distinguish between the two recursive definitions:

```
ri{Ta{2md\j^}j}/

```

(Although, of course, this recurrence relation is just a different way to express the Thue-Morse sequence as the parity of the 1-bits in the binary representation of `n`.)

# Answer
> 8 votes
# LabVIEW, 15 LabVIEW Primitives

now as super fancy gif with a probe

# Answer
> 8 votes
## Dyalog APL, ~~8~~ 7 bytes

```
≠⌿⍴∘2⊤⍳

```

This is a monadic train that expects an index origin of 0 (`⎕IO←0`). The equivalent non-train function is `{≠⌿(⍵⍴2)⊤⍳⍵}`.

Explanation:

```
      ⍳      List of numbers from 0 to (input-1)
  ⍴∘2        (input) copies of 2
     ⊤       Convert all the elements in ⍳ to base 2 to (input) digits
≠⌿           Reduce over the first axis by not-equal

```

Output is a space-separated list of `0` and `1`. Try it here.

# Answer
> 8 votes
# Mathematica, ~~35~~ 21 bytes

Mathematica has a built-in for the Thue-Morse sequence!

```
Array[ThueMorse,#,0]&

```

---

Original answer:

```
#&@@@DigitCount[Range@#-1,2]~Mod~2&

```

# Answer
> 6 votes
## J, ~~12~~ 11 bytes

@MartinBüttner saved a byte.

```
~:/@#:"0@i.

```

This is a monadic (meaning unary) function, used as follows:

```
   f =: ~:/@#:"0@i.
   f 10
0 1 1 0 1 0 0 1 1 0

```

## Explanation

I'm using the alternative definition that Tn is the parity of the number of 1-bits in the binary representation of n.

```
~:/@#:"0@i.  Input is n.
~:/          Output is XOR folded over
   @#:       the binary representations of
      "0     each element of
        @i.  integers from 0 to n-1.

```

# Answer
> 4 votes
# Japt, ~~29~~ 11 bytes

```
Uo ®¤¬r@X^Y

```

Try it online!

Outputs directly as an array, which saves about 4 bytes.

### Ungolfed and explanation

```
Uo ®   ¤  ¬ r@  X^Y
Uo mZ{Zs2 q rXY{X^Y}}
        // Implicit: U = input number
Uo      // Create an array of integers in the range `[0, U)`.
mZ{Zs2  // Map each item Z in this range to Z.toString(2),
q rXY{  //  split into chars, and reduced by
X^Y}}   //   XORing.
        //  This returns (number of 1s in the binary string) % 2.
        // Implicit: output last expression

```

**Edit:** You can now use the following **8-byte** code (not valid; feature published after this challenge):

```
Uo ®¤¬r^

```

# Answer
> 4 votes
## Pyth, ~~11~~ 10 bytes

```
m%ssM.Bd2Q

```

Outputs as a Python-style list.

# Answer
> 4 votes
## Haskell, ~~39~~ ~~36~~ 35 bytes

```
take<*>(iterate([id,(1-)]<*>)[0]!!)

```

Try it online!

How it works: start with `[0]` and apply the `x ++ invert x`-function `n` times. Take the first `n` elements from the resulting list. Thanks to Haskell's laziness only the first `n` elements are actually calculated. Note: the first `<*>` is in function context, the second in list context.

With GHC v8.4 (which wasn't available at the the time of the challenge) there's a 34 byte solution:

```
take<*>(iterate(id<>map(1-))[0]!!)

```

Edit: -3 resp. -4 bytes thanks to @Laikoni. -1 byte thanks to @Ørjan Johansen.

# Answer
> 4 votes
# Pari/GP, 33 bytes

```
n->[sumdigits(x,2)%2|x<-[0..n-1]]

```

Try it online!

# Answer
> 3 votes
# K5, ~~27~~ 13 bytes

```
{x#((log x)%log 2){x,~x}/0}

```

Calculating the sequence is pretty easy, the problem is avoiding computing too much. We can recognize that the easy expansion of the sequence gives us a sequence of strings which are successive powers of two in length. Taking the log base 2 of the input and rounding up will give us enough to work with and then we can cut it down to the appropriate size:

```
  {x#((log x)%log 2){x,~x}/0}'(20 42 37 12 0)
(0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1
 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1
 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0
 0 1 1 0 1 0 0 1 1 0 0 1
 ())

```

## Edit:

A parity-based solution:

```
~=/'(64#2)\'!

```

In action:

```
  ~=/'(64#2)\'!20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

```

Note that since K5 doesn't have an arbitrary convert-to-binary primitive I have to specify, for example, a 64-bit decoding. K5 doesn't use arbitrary precision math, so there will be a limit to the size of inputs we can deal with in any case.

# Answer
> 3 votes
# Octave, ~~33~~ 31 bytes

Saved 2 bytes thanks to Thomas Kwa.

```
@(n)mod(sum(dec2bin(0:n-1)'),2)

```

# Answer
> 3 votes
## Haskell, 54 bytes

Less compact than nimi's solution, but I did not want to deny you this piece of functional code obfuscation. Works for any pair of objects; e.g. you can replace `(f 0.f 1)` by `(f 'A'.f 'B')`.

Based on the definition that the first 2n digits are followed by the same sequence of digits inverted. What we do is build up two lists side-by-side; one for the sequence, one for the inverse. Continuously we append increasingly long parts of one list to the other.

The implementation consists of three definitions:

```
t=(f 0.f 1)t
f c=flip take.(c:).g 1
g n l=l n++g(n+n)l

```

Function `t` accepts any number and returns the Thue-Morse sequence of that length. The other two functions are helpers.

* Function `f` represents either list; `f 0` is for the sequence, `f 1` for the inverse.
* Function `g` takes care of appending increasingly long repetitions of one list to the other.

Fiddle: http://goo.gl/wjk9S0

# Answer
> 3 votes
# MATL, 9 bytes

*This language was designed after the challenge*.

## Approach 1: 13 bytes

This builds the sequence by concatenating negated copies of increasing-size blocks.

```
itBFw"t~h]w:)

```

### Example

```
>> matl itBFw"t~h]w:)
> 20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

```

### Explanation

```
i           % input number, say "N"
tB          % duplicate and convert to binary. Produces a vector
F           % initialize sequence to "false"
w           % swap to bring vector to top
"           % for loop. There will be at least log2(N) iterations
  t~h       % duplicate, negate, concatenate
]           % end for
w           % swap
:)          % index with vector 1, 2, ..., N

```

## Approach 2: 9 bytes

This uses the same approach as Alephalpha's answer.

```
i:1-B!s2\

```

### Example

```
>> matl i:1-B!s2\
> 20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

```

### Explanation

```
i           % input "N"
:1-         % create vector 0, 1, ..., N-1
B           % convert to binary
!           % tranpose
s           % sum
2\          % modulo 2

```

# Answer
> 2 votes
## Burlesque, 21 bytes

```
{0}{J)n!_+}400E!jri.+

```

Examples:

```
blsq ) "20"{0}{J)n!_+}400E!jri.+
{0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1}
blsq ) "42"{0}{J)n!_+}400E!jri.+
{0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1}

```

Explanation:

```
{0}      -- setup
{J)n!_+} -- duplicate, map invert, concatenate
400E!    -- do 400 times (this will eventually run
            out of memory).
jri.+    -- take n elements

```

Without the `jri.+` part you will run out of memory (because it will compute the morse sequence of length *incredibly huge number*). But since Burlesque is lazy just asking for the first n-element will work anyway.

# Answer
> 2 votes
# , 11 chars / 23 bytes (non-competitive)

```
Ⓐïⓜ_ⓑⓢĊ⇀$^_

```

`Try it here (Firefox only).`

The circles are strong with this one.

# Answer
> 2 votes
# Perl 5, ~~62~~ 49 bytes

Yeah, not the best language for this one, but I still like the way it came out. Requires 5.14+ for `/r` and `say`.

```
sub{$_=0;$_.=y/01/10/r while$_[0]>length;say substr$_,0,$_[0]}

```

Using the parity definition, requires 5.12+ for `say`:

```
sub{say map{sprintf("%b",$_)=~y/1//%2}0..$_[0]-1}

```

# Answer
> 2 votes
# C, 88 83 bytes

Calculates the parity for each individual position.

```
i,j;main(int c,char**a){for(;i<atoi(a[1]);putchar(c))for(c=48,j=i++;j;j&=j-1)c^=1;}

```

Fiddle: http://goo.gl/znxmOk

# Answer
> 2 votes
## Retina, ~~70~~ 69 bytes

Using the definition as an L-system with initial word `0` and productions `0 --> 01` and `1 --> 10`.

```
^
0;
(T`d`ab`^(.)+;(?!(?<-1>.)+$)
a
01
)`b
10
!`^(?=.*;(.)+)(?<-1>.)+

```

Input is taken in unary.

You can run the code from a single file with the `-s` flag. Or just try it online.

### Explanation

```
^
0;

```

Prepends `0;` to the input, where `0` is the initial word and `;` is just a separator.

```
(T`d`ab`^(.)+;(?!(?<-1>.)+$)

```

The `(` indicates that this is the beginning of a loop (which repeats until the loop stops changing the string). This stage itself turns `0` and `1` into `a` and `b` respectively (because `d` expands to `0-9`). It does this as long as current word (whose length is measured with `(.)+` is shorter than the input (i.e. as long as we can't read the end of the string by matching as many `1`s as we have in the word).

```
a
01

```

Replace `a` (stand-in for `0`) with `01`.

```
)`b
10

```

Replace `b` (stand-in for `1`) with `10`. This is also the end of the loop. The loop terminates once the condition in the transliteration stage fails, because then all `0`s and `1`s will remain unchanged and the other two stages won't find anything to match.

```
!`^(?=.*;(.)+)(?<-1>.)+

```

The last step is to truncate the word to the length of the input. This time we measure the length of the input with `(.)+` in a lookahead. Then we match that many characters from the beginning of the string.

# Answer
> 2 votes
# Prolog (SWI), 115 bytes

**Code:**

```
N*X:-N>1,R is N//2,R*Y,X is(N mod 2)xor Y;X=N.
p(N):-M is N-1,findall(E,between(0,M,E),L),maplist(*,L,K),write(K).

```

**Explained:**

```
N*X:-                                 % Calculate Thue-Morse number at index N
     N>1,                             % Input is bigger than 1
     R is N//2,R*Y,X is(N mod 2)xor Y % Thue-Morse digit at index N is binary digits of N xor'ed
     ;X=N.                            % OR set X to N (end of recursion)
p(N):-
      M is N-1,                       % Get index of Nth number
      findall(E,between(0,M,E),L),    % Make a list of number 0->N-1
      maplist(*,L,K),                 % Map * on list L producing K
      write(K).                       % Print K

```

**Example:**

```
p(20).
[0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1]

```

Try it online here

# Answer
> 2 votes
# Ruby, 33

```
->n{n.times{|i|p ("%b"%i).sum%2}}

```

Call like this:

```
f=->n{n.times{|i|p ("%b"%i).sum%2}}
f[16]

```

Uses the fact that the parity of binary numbers forms the thue-morse sequence.

Separator character is newline. Converts number `i` to a binary string, then calculates the sum of all ASCII codes, modulo 2.

If newline is not an acceptable separator, the following has no separator for an additional 2 bytes:

```
->n{n.times{|i|$><<("%b"%i).sum%2}}

```

# Answer
> 2 votes
# Jelly, 4 bytes

```
ḶB§Ḃ

```

Note that this challenge is older than Jelly.

Try it online!

### How it works

```
ḶB§Ḃ  Main link. Argument: n (integer)

Ḷ     Unlength; yield [0, ..., n-1].
 B    Compute the binary representation of each integer in the range.
  §   Take the sum of each binary representation.
   Ḃ  Take the LSB of each sum.

```

# Answer
> 2 votes
# Common Lisp, 50 bytes

```
(lambda(n)(dotimes(i n)(princ(mod(logcount i)2))))

```

Try it online!

# Answer
> 2 votes
# V (vim), ~~35~~ 29 bytes

```
C0<esc>qqy$V!tr 01 10
P|q@-@q@-lD

```

Try it online!

-6 bytes from Leo.

Prints the first \\$n\\$ elements.

The sequence is basically a string replacement and append, so it does that \\$n\\$ times using `tr` and then truncates the sequence to \\$n\\$ digits.

# Answer
> 1 votes
# Matlab, 42

I am using the fact that it is the same as beginning with `0` and then repeating the step of appending the complement of the current series, `n` times.

```
t=0;for k=1:input('');t=[t;~t];end;disp(t)

```

# Answer
> 1 votes
# Arcyóu, ~~50~~ 55 bytes

*I had to add 5 bytes to get it to work correctly :(*

```
(f i(_(#(l)))(r b^(@(> i 0)(pg 0(% i 2)(: i(#/ i 2))))0

```

Explanation (with Pythonesque pseudocode along the side:

```
(f i (_ (# (l)))       ; For i in range(int(input())):
  (r b^                ; Reduce with binary xor
    (@ (> i 0)         ; While i > 0:
      (pg 0            ; Return first of its arguments
        (% i 2)        ; i mod 2
        (: i (#/ i 2)) ; i //= 2
      )
    )
    0                  ; Default reduce argument of 0 for the first bit in the sequence

```

# Answer
> 1 votes
## Bash, 71 66 bytes

Based on the definition that the first 2n digits are followed by the same sequence of digits inverted.

```
x=0;y=1;while((${#x}<$1));do z=$x;x=$x$y;y=$y$z;done;echo ${x::$1}

```

`$1` as a parameter is the desired number of digits.

Fiddle: http://goo.gl/RkDZIC

# Answer
> 1 votes
## Batch, 115 + 2 = 117 bytes

Based on the Bash answer.

```
@echo off
set x=0
set y=1
set z=0
:a
set x=!x!!y!
set y=!y!!z!
set z=!x:~0,%1!
if !z!==!x! goto a
echo !z!

```

Needs an extra `/V` in the invocation to allow the use of `!`s.

# Answer
> 1 votes
## ES6, 53 bytes

```
f=(i,x="0",y=1)=>x.length<i?f(i,x+y,y+x):x.slice(0,i)

```

Recursion seemed simpler than a loop.

# Answer
> 1 votes
# Par, 8 bytes

```
✶u[Σ_✶¨^

```

Explanation:

```
✶          parse implicit input number
 u         range [0..n-1]
  [        map:
   Σ           convert to binary
    _✶         get digit list
      ¨^       fold with xor

```

Outputs something like:

```
(0 1 1 0 1 0 0 1)

```

# Answer
> 1 votes
# Math++, 86 bytes

Uses `0.0\n` for 0 and `1.0\n` for 1

```
?>n
3*!!(n-m)>$
m>a
0>k
6+6*!a>$
9-2*!(a%2)>$
a/2>a
5>$
(a-1)/2>a
!k>k
5>$
k
m+1>m
2>$

```

# Answer
> 1 votes
# Husk, 6 bytes

```
moF≠ḋŀ

```

Try it online!

## Using infinite list:

```
↑¹!¡S+m¬;0

```

Try it online!

# Answer
> 0 votes
# Python 3, ~~84~~ ~~80~~ 60 bytes

Since nobody else was using characters other than `0` and `1`, I decided to write my own answer. Here, I use the characters `o` and `t`, but I was quite tempted to use `b` and `o`, or `p` and `o` :P

This is a parity checker in 60 bytes.

```
lambda n:''.join("ot"[bin(i).count("1")%2]for i in range(n))

```

This is a string rewriting algorithm in 109 bytes.

```
def t(n):
 r="o";s=""
 for i in range(len(bin(n))):
  for c in r:s+="otto"[c>"o"::2]
  r=s;s=""
 return r[:n]

```

# Answer
> 0 votes
# K (ngn/k), 16 bytes

```
{2!+/'(x#2)\'!x}

```

Try it online!

# Answer
> 0 votes
# Stax, 5 bytes

```
╩0ΔΔ(

```

Run and debug it at staxlang.xyz!

### Unpacked (6 bytes) and explanation:

```
mv:11I
mv        Map block over range [0,n):
  :1        Popcount
    1I      Is odd?
            Implicit print with newline

```

`1I` is bitwise and with 1. `2%` would work just as well, also packing to 5 bytes.

# Answer
> 0 votes
# Python, 43 bytes

```
def f(n):n>0==f(n-1);print(n.bit_count()%2)
```

Attempt This Online!

---
Tags: code-golf, math, sequence, binary
---


# Question
Title: Infinite Sequence of Unique Random Integers
Output an infinite sequence of positive integers, such that, for each element in the sequence, all positive integers that have not yet been output have a positive probability of being chosen, and no value is repeated.

For example, if the first integer is `3`, then `3` may not be output again, but all other positive integers have a positive probability of being chosen for the second integer.

## Acceptable output methods

* Writing to STDOUT, with a consistent, unambiguous separator between integers (such as a newline), with output prior to termination of the program
* A named or unnamed function which returns an infinite iterable (such as a Python generator)
* A named or unnamed function which outputs the sequence one integer at a time each time it is called within a single execution of the program
* A named or unnamed function or program which outputs the next integer in the sequence when called with the previous integer(s) as its sole argument(s) (the first call may either take no arguments or take a seed argument, which may be included in the arguments to later calls)

## Rules

* There will be no input except an optional seed value, which will be an infinite sequence of random bits.
* Submissions must be capable of producing different outputs given different initial conditions (outputting the same sequence every time is not acceptable).
* Each element of the sequence must be chosen randomly out of the valid elements (positive integers not already present in the sequence).
* You may assume that you have infinite memory available.
* You may assume that any real numbers returned by a PRNG are infinite-precision. In other words, if you have a function called `rand` that returns a random value in `[0, 1)`, you may assume every real value in that interval has a positive probability of being chosen, rather than just the subset of the reals that are representable with floats.
* Each integer must be output in a finite amount of time after the last integer (so you can't wait until program termination to output part of the sequence). The first integer must be output in a finite amount of time after the program is started or the function is called.

# Answer
# Python 3, ~~137~~ ~~127~~ ~~123~~ ~~138~~ ~~117~~ ~~99~~ 98 bytes

> A named or unnamed function which returns an infinite iterable (such as a Python generator)

```
from random import*
def f(x=[],y=1):
 while y in x or.5<random():y+=1
 yield y;yield from f(x+[y])

```
* -10 bytes by putting the conditional in one line (Thanks, @Dennis)
* -4 bytes by initializing `r` at the beginning of the loop
* +15 bytes by remembering numbers can contain zeroes...
* -21 bytes by renaming `randint`, and moving the condition in the head of the inner loop
* -18 bytes by switching to a functional paradigm
* -1 bytes by moving from `or ...>.5` to `.5<random()` (thanks, @JonathanAllan)
> 2 votes

# Answer
# Python 2, ~~93~~ 87 bytes

-3 bytes thanks to Uriel (move `r=1` to beginning of the loop to avoid initialisation)

```
from random import*
a=[]
while 1:
 r=1
 while r in a or.5<random():r+=1
 a+=[r];print r

```

**Try it online!**

Keeps adding one while the number is either unavailable or a coin flip comes up heads.
Low numbers have much more probabilistic weight than high numbers.
> 2 votes

# Answer
# MATL, 10 bytes

```
`x1r/XktGm

```

Try it online!

### Explanation

A candidate output, say **n**, is generated as `ceil(1/r)`, where `r` is uniformly distributed on the interval (0,1). This ensures that every positive integer has a positive probability of being chosen as **n** (assuming infinite precision for `r`).

If **n** coincides with any of the previous numbers (taken as input) the process is repeated.

```
`       % Do...while
  x     %   Delete. This deletes the candidate number from the preceding iteration.
        %   In the first iteration it takes input implicitly and deletes it.
  1     %   Push 1
  r     %   Push random number uniformly distributed on (0,1)
  /     %   Divide
  Xk    %   Round up (ceil). This is the candidate output. It will only be valid
        %   if it's not present in the input
  t     %   Duplicate
  G     %   Push input: forbidden numbers
  m     %   Ismember. This will be used as loop condition
        % End (implicit). If condition is true, next iteration
        % Display (implicit)

```
> 2 votes

# Answer
## JavaScript, 62 bytes

A full program that picks a single random value in **\[0 .. 1\]** and expressed it as a continued fraction, omitting elements that have been encountered before. This would produce a really infinite sequence if the initial value had an infinite precision. In practice, we are limited to what can be expressed in IEEE-854 format.

```
for(x=Math.random(),o=[];;)o[n=1/x|0,x=1/x-n,n]||alert(o[n]=n)

```

### Demo

Here is a demo limited to 50 values and writing to the console instead.

```
for(x=Math.random(),o=[],i=0;i<50;)o[n=1/x|0,x=1/x-n,n]||console.log(o[i++,n]=n)
```
> 1 votes

# Answer
# Aceto, ~~29~~ 21 bytes

> Writing to STDOUT, with a consistent, unambiguous separator between integers (such as a newline), with output prior to termination of the program

```
p<LL
 v`O
I?<\
0MLCnO

```
1. Push a zero, increment it and go in a random direction. Two of the directions lead back to the random direction field, one leads back to incrementation (so it is incremented a random amount of times).
2. When the fourth choice is made, we memorize and immediately load the value, then check whether it's contained in the stack already. If so, we jump to the origin and try again.
3. Otherwise, we load the value twice (once for printing, once for storage), print it and a newline and go back to the origin.

Massively favours low numbers, but there is a small chance for it to print any number at any point.
> 1 votes

# Answer
# Bash, 23 bytes

```
yes \ |nl|xargs shuf -e

```

Try it online!

`yes \` prints infinite spaces, `nl` numbers lines, `suff -e` shuffless lines without repetition.
> 1 votes

# Answer
# Python 2, 39 bytes

```
f=lambda l,s:sum({1/s//1}-l)or f(l,s/2)

```

Try it online!

Takes a list `l` of previous outputs (as a set) and a seed `s` that's a random real from 0 to 1.
> 0 votes

# Answer
# Japt, 17 bytes

```
aA=(1/Mr)c)<0?A:ß

```

Try it online!
> 0 votes

# Answer
## Haskell, ~~60~~ ~~59~~ 56 bytes

```
((a:b)#h)(n:r)|n=a:((h++b)#[])r|q<-a:h=(b#q)r
[1..]#[]

```

Takes the seed as an infinite list of `Bool`.

Usage example: `([1..]#[]) [True,False,False,True,True,False,True,True,False,True,False,True,True,False,False,False,False,False,False,True....]` -\> `[1,4,3,5,2,7,8,6,15,...]`.

Try it online!

Start with the list `[1..]`. If the next element from the seed is `False`, skip the next element of the list. If it's a `True`, output the current element, remove it from the list and start from the beginning. `h` keeps track of the skipped elements and is prepended (-\> `h++b`) to the list of available numbers in the `True` case.
> 0 votes

# Answer
## Clojure, ~~112 (or 119)~~ 114 bytes

Update, uses `1 / (rand)` to get an "infinite" range of bigints:

```
#(filter pos?(map first(reductions(fn[[v p]r](if(p r)[0 p][r(conj p r)]))[0#{}](for[i(range)](bigint(/(rand)))))))

```

Original:

```
#(filter pos?(map first(reductions(fn[[v p]r](if(p r)[0 p][r(conj p r)]))[0 #{}](for[i(range)](rand-int 2e9)))))

```

I'm hoping to see an alternative approach. Anyway, this will generate integers between 1 and 2e9, Java's integers are signed to the "real" maximum is 2147483647, which is 7 bytes longer expression (`Integer/MAX_VALUE` is even longer). `0` is used as an indication of a duplicate values and are filtered from the output sequence.
> 0 votes

# Answer
# Clojure, 100 bytes

```
(fn[](let[a(atom[])](filter #(if-not(some #{%}@a)(swap! a conj %))(repeatedly #(bigint(/(rand)))))))

```

This function returns an infinite sequence of integers. To get the `n`th number of this series:

```
(nth (fn[]...) n)

```

To get the first `n` terms of this series:

```
(take n (fn[]...))

```

***EDIT:*** *Golfed 11 bytes (Thanks @NikoNyrh!) and added 3 bytes (changed `int` to `bigint`, to improve accuracy).*
> 0 votes

# Answer
# Java 8, 136 bytes

```
import java.util.*;()->{Set s=new HashSet();for(int n;;s.add(n))System.out.print(!s.contains(n=new Random().nextInt(-1>>>1))?n+";":"");}

```

**Explanation:**

Try it here. (Wait 60 seconds for the TIO to time-out to see the result.)

```
import java.util.*;     // Required import for the Set, HashSet, and Random

()->{                   // Method without parameters nor return-type
  Set s=new HashSet();  //  Set to keep track of numbers we've already outputted
 for(int n;;            //  Loop infinitely
     s.add(n))          //   And every time we output a random number, add it to the Set
   System.out.print(    //   Output:
    !s.contains(        //    If we haven't outputted it yet:
     n=new Random().nextInt(-1>>>1))?n+";"
                        //     A random number (range of int: 0 - 2³²)
    :                   //    Else:
     "");               //     Output nothing
}                       // End of method

```
> 0 votes

# Answer
# JavaScript ES6, repeating call, 50 Bytes

```
c={0:9};f=_=>c[~~_]|Math.random()<.9?f(-~_):c[_]=_

```
> 0 votes

# Answer
# JavaScript REPL, 48 bytes

```
for(o=[];;)o[n=1/Math.random()|0]||alert(o[n]=n)

```
> 0 votes

# Answer
# APL, 33 bytes

```
∇P
S←⍬
→2/⍨S∊⍨X←⌊÷1-?0
S,←⎕←X
→2∇

```
> 0 votes

# Answer
## Mathematica, 83 bytes

```
s=5;l={};t=1;While[t<30,If[l~FreeQ~s,Print@s];l~AppendTo~s;s=RandomInteger@100;t++]

```

starting with 5

Try it online!
> -1 votes

---
Tags: code-golf, random, integer
---


# Question
Title: Are there N consecutive occurrences of a number in a row/column in a matrix?
Take a matrix **A** consisting positive integers, and a single positive integer **N** as input, and determine if there are at least **N** consecutive occurrences of the same number in any row or column in the matrix.

You need only test horizontally and vertically.

### Test cases

```
N = 1
A =
1
Result: True
----------------
N = 3
A =
1 1 1
2 2 3
Result: True
----------------
N = 4
A =
1 1 1
2 2 3
Result: False
----------------
N = 3
A =
3 2 3 4 2 1
4 1 4 2 4 2
4 2 3 3 4 1
1 1 2 2 3 4
3 2 3 1 3 1
1 1 2 2 3 4
Result: True
----------------
N = 1
A =
5 2 3 8
Result: True
----------------
N = 3
111   23  12    6
111   53   2    5
112  555   5  222
Result: False
----------------
N = 2
 4  2  6  2  1  5
 2  3  3  3  3  3
11 34  4  2  9  7
Result: True

```

Explanations are always a good thing :)

# Answer
> 7 votes
# Jelly, ~~9~~ 8 bytes

```
;ZjṡƓE€S

```

Takes the matrix as arguments and reads the integer from STDIN.

Try it online!

### How it works

```
;ZjṡƓE€S  Main link. Argument: M (matrix / row array)

 Z        Zip/transpose M.
;         Concatenate the row array with the column array.
  j       Join the rows and columns, separating by M.
    Ɠ     Read an integer n from STDIN.
   ṡ      Split the result to the left into overlapping slices of length 2.
     E€   Test the members of each resulting array for equality.
       S  Take the sum.

```

### Example run

```
;ZjṡƓE€S  Argument: [[1, 2], [3, 2]]. STDIN: 2

 Z        [[1, 3], [2, 2]]

;         [[1, 2], [3, 2], [1, 3], [2, 2]]

  j       [1, 2, [1, 2], [3, 2], 3, 2, [1, 2], [3, 2], 1, 3, [1, 2], [3, 2], 2, 2]

    Ɠ     2

   ṡ      [[1, 2],             [2, [1, 2]],        [[1, 2], [3, 2]],   [[3, 2], 3],
           [3, 2],             [2, [1, 2]],        [[1, 2], [3, 2]],   [[3, 2], 1],
           [1, 3],             [3, [1, 2]],        [[1, 2], [3, 2]],   [[3, 2], 2],
           [2, 2]                                                                 ]

     E€   [     0,                       0,                       0,             0,
                0,                       0,                       0,             0,
                0,                       0,                       0,             0,
                1                                                                 ]

       S  1

```

# Answer
> 7 votes
## Husk, 9 bytes

```
≤▲mLṁgS+T

```

Takes a 2D array and a number, returns `0` for falsy instances and a positive number for truthy instances. Try it online!

## Explanation

Husk is a functional language, so the program is just a composition of several functions.

```
≤▲mLṁgS+T
        T  Transpose the array
      S+   and concatenate with original.
           We get a list of the rows and columns of the input array.
    ṁ      Map and concatenate
     g     grouping of equal consecutive elements.
           This gives all consecutive runs on rows and columns.
  mL       Map length over the runs,
 ▲         take the maximum of the results
≤          and see if it's at least the second input.

```

# Answer
> 5 votes
# Dyalog APL, ~~27~~ ~~25~~ 23 bytes

```
{1∊∊⍷∘⍵¨(⊢,⍪¨)⍺/¨⍳⌈/∊⍵}

```

Try It Online!

Thanks to @MartinEnder and @Zgarb for -2 bytes each (composition removes the need to use `w` and pointless parens)

Alert me if there are any problems and/or bytes to golf. Left argument is **N**, right argument is **A**.

Explanation:

```
{1∊∊⍷∘⍵¨(⊢,⍪¨)⍺/¨⍳⌈/∊⍵}
                     ⍵    - Right argument
                    ∊     - Flatten the array
                 ⍳⌈/      - 1 ... the maximum (inclusive)
              ⍺/¨         - Repeat each item ⍺ (left argument) times.
        (⊢,⍪¨)            - Argument concatenated with their transposes.
    ⍷∘⍵¨                  - Do the patterns occur in ⍵?
   ∊                      - Flatten (since we have a vector of arrays)
 1∊                       - Is 1 a member?
{                     }   - Function brackets

```

# Answer
> 5 votes
# MATL, 12 bytes

```
t!YdY'wg)>~a

```

Try it online! Or verify all test cases.

### Explanation

A non-square matrix cannot be properly concatenated to its transpose, either vertically or horizontally. So the code concatenates them *diagonally*, by creating a block-diagonal matrix.

The resulting matrix is linearized in column-major order and run-length encoded. The zeros resulting from the block-diagonal concatenation serve to isolate the runs of actual values.

The results from run-length encoding are an array of values and an array of run-lengths. The run-lengths corresponding to non-zero values are kept. The output is `1` if some of those lengths is greater than or equal to the input number, and `0` otherwise.

Let's see the intermediate results to make it clearer. Consider inputs

```
[10 10 10;
 20 20 30]

```

and

```
3

```

The block diagonal matrix containing the input matrix and its transpose (code `t!Yd`) is:

```
10 10 10  0  0
20 20 30  0  0
 0  0  0 10 20
 0  0  0 10 20
 0  0  0 10 30

```

This matrix is implicit linearized in column-major order (down, then across):

```
10 20  0  0  0 10 20  0  0  0 10 30  0  0  0  0  0 10 10 10  0  0 20 20 30

```

Run-length encoding (code `Y'`) gives the following two vectors (shown here as row vectors; actually they are column vectors): vector with values

```
10 20  0 10 20  0 10 30  0 10  0 20 30

```

and vector with run lengths

```
1 1 3 1 1 3 1 1 5 3 2 2 1

```

Keeping only the lengths correspoinding to non-zero values (code `wg)`) gives

```
1 1 1 1 1 1 3 2 1

```

Comparing to see which lengths are greater than or equal to the input number (code `>~`) produces the vector

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

```

Finally, the output should be `true` (shown as `1`) if the above vector contains at least a `true` entry (code `a`). In this case the result is

```
1

```

# Answer
> 4 votes
# Octave, ~~77~~ 70 bytes

```
@(A,N)any(([x y]=runlength([(p=padarray(A,[1 1]))(:);p'(:)]))(!!y)>=N)

```

Try it online!

Explanation: Since tha matrix only contains non-zero integers we can add a border of 0s around the matrix and compute runlength encoding of the matrix(reshaped to a vector)

```
@(A,N)any(([x y]=runlength([(p=padarray(A,[1 1]))(:);p'(:)]))(!!y)>=N)
                             p=padarray(A,[1 1])                        % add a border of 0s around the matrix
                            (                   )(:)                    % reshape the matrix to a column vector
                                                     p'(:)              % transpose of the matrix reshaped to a column vector
                           [                        ;     ]             % concatenate two vectors vertically
           [x y]=runlength(                                )            % runlength encoding of the vector[x=count,y=value]
          (                                                 )           % take x,counts.
                                                             (!!y)      % extrect those counts that their valuse aren't 0
      any(                                                        >=N)  % if we have at least a count that is greater than or equal to N

```

# Answer
> 4 votes
# Perl 6, 60 bytes

```
{(@^m|[Z,] @^m).map(*.rotor($^n=>$^n-1).map({[==] $_}).any)}

```

Try it online!

* `@^m` is the input matrix (first argument) and `$^n` is the number of consecutive occurrences to check for (second argument).
* `[Z,] @^m` is the transpose of the input matrix.
* `(@^m | [Z,] @^m)` is an or-junction of the input matrix and its transpose. The following `map` evaluates to a truthy value if `$^n` consecutive equal values occur in any row of the invocant. Applied to the input matrix OR its transpose, it evaluates to a truthy value if either the input matrix or its transpose contain `$^n` consecutive equal values in any row; if the transpose meets that condition, that means the input matrix has `$^n` consecutive equal values in one of its columns.
* `*.rotor($^n => $^n - 1)` turns each row into a sequence of `$^n`-element slices. For example, if `$^n` is 3 and a row is `<1 2 2 2 3>`, this evaluates to `(<1 2 2>, <2 2 2>, <2 2 3>)`.
* `.map({ [==] $_ })` turns each slice into a boolean that indicates whether all elements of the slice are equal. Continuing the previous example, this becomes `(False, True, False)`.
* `.any` turns that sequence of booleans into an or-junction which is truthy if any of the booleans are true.

The output is a truthy or-junction value which is true if either the input matrix OR its transpose have ANY row where `$^n` consecutive values are equal.

# Answer
> 3 votes
# Python 3, 129 128 125 120 104 101 bytes

Huge thanks to @Zachary T, @Stewie Griffin, @Mr. Xcoder, @Rod, @totallyhuman for improving this by a lot.

```
def f(n,m):
 a=b=c=0;m+=zip(*m)
 for r in m:
  for i in r:b,a=[1,b+1][a==i],i;c=max(c,b)
 return n<=c

```

Try it online!

# Answer
> 3 votes
# Japt, ~~18~~ ~~15~~ 14 bytes

```
cUy)d_ò¦ d_Ê¨V

```

Test it

* 3 bytes saved with some help from ETHproductions.

---

## Explanation

```
    :Implicit input of 2D array U and integer V
c   :Append to U...
Uy  :U transposed.
d   :Check if any of the elements (sub-arrays) in U return true when...
_   :Passed through a function that...
ò   :Partitions the current element by...
¦   :Checking for inequality.
d   :Check if any of the partitions return true when...
_   :Passed through a function that checks if...
Ê   :The length of the current element...
¨V  :Is greater than or equal to V.
    :Implicit output of resulting boolean.

```

# Answer
> 3 votes
# Python 2, ~~60~~ ~~92~~ 91 bytes

```
def f(n,x):x=[map(str,i)for i in x];print any(`[i]*n`[1:-1]in`x+zip(*x)`for i in sum(x,[]))

```

Try it online!

Instead of counting, a list with size `n` (for each element in the matrix) is generated and checked if it's on the matrix

**Without strings, 94 bytes**

```
lambda n,x:any((e,)*n==l[i:i+n]for l in x+zip(*x)for i in range(len(l)-n+1)for e in sum(x,()))

```

Try it online!

# Answer
> 3 votes
# Octave, 59 bytes

```
@(A,N)any({[l,v]=runlength(blkdiag(A,A')(:)),l(v>=0)}{2}>=N)

```

Try it online! Or verify all test cases.

This uses the same approach as my MATL answer (see explanation there).

# Answer
> 2 votes
## CJam, 16 bytes

```
q~_z+N*e`:e>0=>!

```

Try it online!

### Explanation

```
q~    e# Read and eval input.
_z+   e# Append the matrix's transpose to itself.
N*    e# Join with linefeeds to flatten without causing runs across rows.
e`    e# Run-length encode.
:e>   e# Get maximum run (primarily sorted by length).
0=    e# Get its length.
>!    e# Check that it's not greater than the required maximum.

```

# Answer
> 2 votes
# 05AB1E, ~~16 14~~ 12 bytes

```
Døìvyγ€gM²‹_

```

Try it online!

```
Dø           # Duplicate the input and transpose one copy
  ì          # Combine the rows of both matrixes into one array
   vy        #   For each row...
     γ       #     Break into chunks of the same element
      €g     #     get the length of each chunk
        M    #     Get the largest length so far
         ²‹_ #     Check if that is equal to or longer than required

```

# Answer
> 1 votes
# Jelly, 18 bytes

```
ŒrFUm2<⁴$ÐḟL
ZÇo³Ç

```

Try it online!

```
ŒrFUm2<⁴$ÐḟL  Helper Link
Œr            Run-length encode
  F           Flatten the whole thing, giving the numbers in the odd indices and the lengths of the runs in the even indices
   U          Reverse
    m2        Take every other element (thus only keeping the run lengths)
         Ðḟ   Discard the elements that are
      <⁴$                                   less than the required run length
           L  And find the length
ZÇo³Ç         Main Link
Z             Zip the matrix
 Ç            Call the helper link on it
   ³Ç         Call the helper link on the original matrix
  o           Are either of these truthy?

```

Returns `0` for false and a non-zero integer for truthy.

Ew, this is bad. And very long. Golfing tips would be appreciated :)

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

Takes the matrix `m` and the expected number of occurrences `n` in currying syntax `(m)(n)`. Returns a boolean.

```
m=>n=>[',',`(.\\d+?){${m[0].length-1}}.`].some(s=>m.join`|`.match(`(\\b\\d+)(${s}\\1){${n-1}}\\b`))

```

### How?

This code is not particularly short, but I wanted to try an approach purely based on regular expressions.

**Conversion of the matrix to a string**

We use `m.join('|')` to transform the 2D-array into a string. This first causes an implicit coercion of the matrix rows to comma-separated strings.

For instance, this input:

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

```

will be transformed into:

```
"1,2,3|4,5,6"

```

**Row matching**

We look for consecutive occurrences in a row with:

```
/(\b\d+)(,\1){n-1}\b/

```

This is matching:

* `\b` a word boundary
* `\d+` followed by a number
* `(){n-1}` followed ***n-1*** times by:
    + `,` a comma
    + `\1` followed by our reference: a word boundary + the first number
* `\b` followed by a word boundary

**Column matching**

We look for consecutive occurrences in a column with:

```
/(\b\d+)((.\d+?){L-1}.\1){n-1}\b/

```

where `L` is the length of a row.

This is matching:

* `\b` a word boundary
* `\d+` followed by a number
* `(){n-1}` followed ***n-1*** times by:
    + `(){L-1}` ***L-1*** times:
        - `.` any character (in effect: either a comma or a pipe)
        - `\d+?` followed by a number (this one must be non-greedy)
    + `.` followed by any character (again: either a comma or a pipe)
    + `\1` followed by our reference: a word boundary + the first number
* `\b` followed by a word boundary

### Test cases

```
let f=

m=>n=>[',',`(.\\d+?){${m[0].length-1}}.`].some(s=>m.join`|`.match(`(\\b\\d+)(${s}\\1){${n-1}}\\b`))

console.log(f([
  [ 1 ]
])(1))

console.log(f([
  [ 1, 1, 1 ],
  [ 2, 2, 3 ]
])(3))

console.log(f([
  [ 1, 1, 1 ],
  [ 2, 2, 3 ]
])(4))

console.log(f([
  [ 3, 2, 3, 4, 2, 1 ],
  [ 4, 1, 4, 2, 4, 2 ],
  [ 4, 2, 3, 3, 4, 1 ],
  [ 1, 1, 2, 2, 3, 4 ],
  [ 3, 2, 3, 1, 3, 1 ],
  [ 1, 1, 2, 2, 3, 4 ]
])(3))

console.log(f([
  [ 5, 2, 3, 8 ]
])(1))

console.log(f([
  [ 111,  23,  12,   6 ],
  [ 111,  53,   2,   5 ],
  [ 112, 555,   5, 222 ]
])(3))

console.log(f([
  [  4,  2,  6,  2,  1,  5 ],
  [  2,  3,  3,  3,  3,  3 ],
  [ 11, 34,  4,  2,  9,  7 ]
])(2))
```

# Answer
> 1 votes
# Octave, 58 bytes

```
f=@(A)runlength([A;nan*A](:))
F=@(A,n)max([f(A),f(A')])>=n

```

Try it online!

# Answer
> 1 votes
# BQN, 21 bytes

```
-⊸≢1=⊣≠∘⍷˘∘↕˘⎊0¨⋈⟜⍉∘⊢

```

Anonymous tacit function; takes the number `n` as left argument and the 2D array `a` as right argument. Try it at BQN online!

### Explanation

So. Many. Modifiers. ○\_○

```
-⊸≢1=⊣≠∘⍷˘∘↕˘⎊0¨⋈⟜⍉∘⊢
                      ∘⊢  With the right argument (a),
                 ⋈⟜⍉     pair it with its transpose
                ¨         Apply this function to each of those arrays
     ⊣                    and the original left argument (n):
             ˘              Within each row of the array,
            ↕               get all sublists of length n
          ˘∘                Then, with each of those sublists,
       ≠∘⍷                  uniquify and get the length (1 iff all elements are equal)
              ⎊0           If that function errored because n is too big, use 0 instead
                          We now have a list of two elements, each of which is either
                          an array of integers or a 0
   1=                     Compare each integer to 1 (0 if not equal, 1 if equal)
 ⊸≢                      Is that nested list different from
-                         the same list with each integer negated?

```

If there are no sublists where all items are identical, we'll get a nested list containing only zeros, which remains the same under negation; thus,  will return 0. If there is at least one sublist with identical items, we'll get a nested list that contains a 1 somewhere, which changes under negation; thus,  will return 1.

# Answer
> 1 votes
# Vyxal, 9 bytes

```
:∩JvøĖ≤fa

```

Try it Online!

# Answer
> 0 votes
# Python 2, 64 bytes

```
lambda M,n:(', 0'*n)[5:]in`[map(cmp,l,l[1:])for l in M+zip(*M)]`

```

Try it online!

# Answer
> 0 votes
## Clojure, 77 bytes

```
#((set(for[I[%(apply map vector %)]i I p(partition %2 1 i)](count(set p))))1)

```

Creates all consecutive partitions `p` of length `N` (symbol `%2`) and counts how many distinct values it has. Then it forms the set of these lengths and returns `1` if it is found from the set and `nil` otherwise. `for` construct was the perfect fit for this, my original attempt used `flatten`, `concat` or something of that short.

# Answer
> 0 votes
# Julia, ~~90,84~~ 70 bytes

```
A\n=(~X=occursin("0"^(n-1),[X;0X[1,:]'][:]|>diff.|>sign|>join);~A|~A')
```

(A\>0 is exploited.)

Attempt This Online!

and a `StatsBase`-based vari:

### 16+54 bytes

```
using StatsBase
A\n=(~X=any(eachrow(X).|>x->any(rle(x)[2].≥n));~A|~A')

```

# Answer
> 0 votes
# 05AB1E, 8 bytes

```
Dø«δÅγ›ß

```

First input is the matrix \\$A\\$, second is the integer \\$N\\$.
Outputs an inverted boolean: `0` for truthy and `1` for falsey.

Try it online or verify all test cases.

**Explanation:**

```
D         # Duplicate the (implicit) input-matrix
 ø        # Zip/transpose its copy; swapping rows/columns
  «       # Merge it to the input-matrix
          # (we now have a list of all rows and all columns)
          #  e.g. input=[[1,1,1],[2,2,3]] → [[1,1,1],[2,2,3],[1,2],[1,2],[1,3]]
   δ      # Map† over each inner list:
    Åγ    #  Run-length encode it; pushing the list of items and list of lengths
          #  separately to the stack, only leaving the top list of lengths
          #   → [[3],[2,1],[1,1],[1,1],[1,1]]
       ›  # Check for each inner-most length if it's smaller than the second (implicit)
          # input-integer
        ß # Pop and push the flattened minimum to check if any was falsey
          # (after which the result is output implicitly)

```

`δ` is technically an 'apply double-vectorized', which also uses the second (implicit) input-integer as argument. It's usually used to create tables from two lists, or to apply a builtin that takes a single argument on each inner item of a list.
In this case, the implicit input-integer is simply ignored since builtin `Åγ` takes no arguments, and `δ` therefore acts as a map. We use this, because map `εÅγ}` is 1 byte longer and map `€Åγ` would also keep the lists of items (so the example above would become `[[3],[1],[2,1],[2,3],[1,1],[1,2],[1,1],[1,2],[1,1],[1,3]]` instead).

---
Tags: code-golf, number, decision-problem, matrix
---


title: Semidivisibility

text:
# Question
Title: Semidivisibility
**NOTE: Some terminology used in this challenge is fake.**

For two integers `n` and `k` both greater than or equal to 2 with `n > k`, `n` is *semidivisible* by `k` if and only if `n/k = r/10` for some integer `r`. However, `n` may not be divisible by `k`. Put more simply, the base 10 representation of `n/k` has exactly one digit after the decimal place. For example, 6 is semidivisible by 4 because 6/4=15/10, but 8 is not semidivisible by 4 because `8 % 4 == 0`.

Your task is to write a program which takes in two integers as input, in any convenient format, and outputs a truthy (respectively falsy) value if the first input is semidivisible by the second, and a falsey (respectively truthy) value otherwise. Standard loopholes are forbidden. You may assume that `n > k` and that both `n` and `k` are at least 2.

Test cases:

```
[8, 4] -> falsey
[8, 5] -> truthy
[9, 5] -> truthy
[7, 3] -> falsey

```

This question is therefore shortest answer in bytes wins.

# Answer
> 16 votes
# Python 2, 24 bytes

```
lambda n,k:n*10%k==0<n%k

```

Try it online!

Checks that \\$10n\\$ is a multiple of \\$k\\$, but \\$n\\$ itself is not.

**24 bytes**

```
lambda n,k:n%k>>n*10%k*n

```

Try it online!

The `*n` at the end can't be omitted, say for `n=19001, k=10000`.

# Answer
> 10 votes
# , 31 bytes

```
function(x,y)nchar((x/y)%%1)==3

```

Try it online!

Fractional part (`%%1`) of `x/y` must be 3 characters: so, `0.1`, `0.2` ... `0.9`, but not `0` or `0.3333`.

# Answer
> 10 votes
# Python 2, 23 bytes

Saves 1 byte from xnor's answer *(for the bounty)*. Notice that the chained comparison forces `n*10%k = 0` and `n%k > 0` to both be true.

```
lambda n,k:1>n*10%k<n%k

```

Try it online!

# Answer
> 8 votes
# APL (Dyalog Unicode), ~~12~~ 9 bytes

```
3=∘≢∘⍕1|÷

```

Try it online!

The previous, obvious method.

```
'.'=∘⊃¯2↑∘⍕÷

```

Try it online!

# Answer
> 6 votes
# Japt, 10 bytes

I think this is right; I'm quite drunk!

```
*A vV «UvV

```

Try it

# Answer
> 5 votes
# C (gcc), <sup>~~25~~ ~~24~~</sup> 23 bytes

Saved a byte thanks to AZTECCO!!!
Thanks to dingledooper who found and fixed a bug!!!

```
f(n,k){n=n%k>0>10*n%k;}

```

Try it online!

Inputs integers \\$n\\$ and \\$k\\$ and returns a truthy iff \\$10n\\$ is divisible by \\$k\\$ and \\$n\\$ isn't divisible by \\$k\\$.

# Answer
> 5 votes
# Husk, 8 bytes

```
€tḊ10/¹⌉

```

Try it online!

Uses a different approach from what I have seen in other answers, could be even shorter if I found a better way to check if a number is in \[2,5,10\]. (Any golfing language with a single-byte builtin for 10 could probably do it)

### Explanation

Taking 2 numbers \\$a\\$ and \\$b\\$, we compute: $$\frac{lcm(a,b)}{a}$$

This value will be equal to the smallest number you have to multiply \\$a\\$ by to make it divisible by \\$b\\$. Since we don't want \\$a\\$ to be divisible by \\$b\\$ we'll need this to be greater than 1, and since we want \\$10\*a\\$ to be divisible by \\$b\\$ we'll need this to be a divisor of 10. In the end we want the result to be one of \[2,5,10\].

```
€tḊ10/¹⌉
       ⌉    Least common multiplier of the two numbers
     /¹     divided by the first number
€           Find its position in the list: (returns 0 if missing)
  Ḋ10        divisors of ten: [1,2,5,10]
 t           except the first: [2,5,10]

```

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

```
n=>k=>n%k>0>10*n%k

```

Try it online!

-2 bytes thanks to iota

-1 byte indirectly from Neil or Noodle9 or dingledooper

# Answer
> 4 votes
# Haskell, 30 bytes

```
n#k=(10*n`mod`k<1)>(n`mod`k<1)

```

Try it online!

# Answer
> 4 votes
# Jelly, 6 bytes

```
×⁵ọ¹ȧ%

```

Try it online!

# Answer
> 3 votes
# Retina 0.8.2, ~~41~~ ~~40~~ 35 bytes

```
$
0
\d+
$*
^(1+),(?!(\1{10})+$)\1+$

```

Try it online! Takes inputs in reverse order, but header in link reverses the test suite for convenience. Explanation:

```
$
0

```

Multiply `n` by `10`.

```
\d+
$*

```

Convert `k` and `10n` to unary.

```
^(1+),

```

Match k, then ...

```
(?!(\1{10})+$)

```

... while ensuring `10k` doesn't divide `10n` (i.e `k` does not divide `n`), ...

```
\1+$

```

... ensure `k` divides `10n`.

# Answer
> 3 votes
# , 11 bytes

```
3=[#@":@%~|

```

Try it online!

Looks like I stumbled on almost exactly the same method as the APL answer.

* `[...%~|` The left input `[` floating point divided into `%~` the remainder when the left input is divided into the right input `|`.
* `#@":@` Format that result as a string and take its length.
* `3=` Does that equal 3? This will only be true for numbers of the form `0.n` where n is an element of the digits `1-9`.

# Answer
> 3 votes
# PowerShell, 36 bytes

```
param($n,$k)!((10*$n)%$k)-and($n%$k)

```

Try it online!

Inspired by @xnor method of checking if 10n is multiple of k but n itself not

# Answer
> 3 votes
# GolfScript, 15 bytes

```
.~@~%!!@10*@%!&

```

Try it online!

Unfortunately, as GolfScript lacks support for floating-point values, I couldn't use the strategy of looking for the decimal place. The program just checks if n % k is truthy and 10n % k is falsy.

Also of note is that I found it easier to take the input as a string containing two space-separated integers instead of taking it as two integers directly.

```
.~@~                  prepare two sets of n and k
    %!!               check if n % k > 0
       @10*           multiply n by 10
           @%!        check if 10n % k = 0
              &       AND both values

```

# Answer
> 3 votes
# , 28 bytes

```
function(x,y)!(x*10)%%y&x%%y

```

Try it online!

Test harness taken from Dominic's answer.

# Answer
> 3 votes
# Excel, ~~31~~ ~~29~~ 20 bytes

```
=LEN(MOD(A1/B1,1))=3

```

*-2 bytes thanks to @Dominic van Essen*

*-9 bytes porting Dominic's Answer*

Previous Answer

```
=MOD(A1,B1)*(MOD(A1*10,B1)=0)

```

# Answer
> 3 votes
# Vyxal v2.6.0+, 6 bytes

```
ġ/₀KḢc

```

Takes its input as \\$k\\$ followed by \\$n\\$.

Try it Online!

This uses the same algorithm as my regex answer, which is similar to the algorithm used by Leo's Husk answer. It asserts that $${k\over gcd(n,k)} ∈ \[2,5,10\]$$

It doesn't use floating point, and can thus handle arbitrarily large integers correctly.

```
ġ            Push gcd(n,k)
 /           Pop the above result, and push k divided by it
  ₀K         Push the divisors of 10, i.e. [1, 2, 5, 10]
    Ḣ        Head remove – drop first element, yielding [2, 5, 10]
     c       Is the above quotient contained in the above list?

```

## Vyxal v2.5.3ω, 7 bytes

```
ġ/₀Kḣ„c

```

Takes its input as \\$k\\$ followed by \\$n\\$.

Try it Online! \- v2.5.3ω
Try it Online! \- latest

The reason I didn't use the  head-remove element in the first place is that I was referring to outdated documentation – my clone of the git repo was pointed at master instead of main.

```
ġ             Push gcd(n,k)
 /            Pop the above result, and push k divided by it
  ₀K          Push the divisors of 10, i.e. [1, 2, 5, 10]
    ḣ         Head extract – split the above, yielding 1 and [2, 5, 10]
     „        Rotate stack left, such that a=the above quotient, and b=[2, 5, 10]
      c       Is a contained in b?

```

# Vyxal v2.5.3ω, 7 bytes

```
Ḋ⁰₀*¹Ḋ<

```

Takes its input as \\$k\\$ followed by \\$n\\$.

Try it Online! \- v2.5.3ω
Try it Online! \- latest

This uses the same logic as in xnor's Python answer and many subsequent answers, which is to assert that \\$n≢0\pmod k\ \land\ 10n≡0\pmod k\\$.

```
Ḋ             Push 1 if n is divisible by k, 0 otherwise
 ⁰            Push n
  ₀           Push 10
   *          Push n*10, popping both n and 10
    ¹         Push k
     Ḋ        Push 1 if n*10 is divisible by k, 0 otherwise (pop both)
      <       Is the top boolean less than the bottom boolean?

```

## Vyxal v2.5.3ω, 7 bytes, 6 elements

```
k≈↵*⁰Ḋ¯

```

Takes its input as \\$n\\$ followed by \\$k\\$.

Try it Online! \- v2.5.3ω
Try it Online! \- latest

```
k≈            Push [0, 1]
  ↵           Raise 10 to the power of the above: [1, 10]
   *          Multiply the above list by n
    ⁰         Push k
     Ḋ        Are the list items divisible by k? (Result is a list)
      ¯       Take deltas (consecutive differences) of the list. Iff the two
              elements of the list were different, this will be truthy.

```

Oddly, the behavior of `¯` was changed. It used to give \\$\[a\[0\]-a\[1\], a\[1\]-a\[2\], …\]\\$ but now gives \\$\[a\[1\]-a\[0\], a\[2\]-a\[1\], …\]\\$. This doesn't change the truthiness of the output, just the sign of the truthy result: `⟨-1⟩` in old, `⟨1⟩` in new.

# Answer
> 2 votes
# Charcoal, 9 bytes

```
⁼¹⌕⮌Ｉ∕ＮＮ.

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for semidivisble, nothing if not. Explanation:

```
      Ｎ     First input
     ∕      Divided by
       Ｎ    Second input
    Ｉ       Cast to string
   ⮌        Reversed
  ⌕         Index of
        .   Literal `.`
⁼           Equal to
 ¹          Literal 1
            Implicitly print

```

# Answer
> 2 votes
# Vyxal 2.0.0, 6 bytes

```
/Ṫt\.=

```

Try it Online!

Checks if the second last character is "."

# Answer
> 2 votes
# Husk, 9 bytes

```
&¬%³*10¹%

```

Try it online!

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

```
{>/~y!10 1*x}

```

Try it online!

Uses @xnor's approach. `n` is `x`, and `k` is `y`.

* `10 1*x` generate list of 10 times `x`, and `x`
* `y!` mod each of those by `y`
* `~` not them, i.e. check if `y` evenly divides `10*x` and `x`
* `>/` return true iif `y` evenly divides `10*x` but not `x`

# Answer
> 2 votes
# 05AB1E, ~~9~~ ~~8~~ ~~8~~ 6 bytes

-2 thanks to @Kevin Cruijssen

```
/`×'.å

```

Try it online!

Try more cases

# Answer
> 2 votes
# Regex (ECMAScript), ~~35~~ 33 bytes

```
^(?=(.+)\1*,\1+$)(\1\B|\1{5})\2?,

```

Takes its input in unary, as the length of two strings of `x`s delimited by a `,` specifying (\\$k,n\\$).

Try it online!

This uses a similar algorithm to Leo's Husk answer. We can't directly compute \\$lcm(n,k)\\$ since it can be larger than both the inputs, so instead we compute \\$k/gcd(n,k)\\$, which is conveniently equivalent to \\$lcm(n,k)/n\\$. All that remains is to assert that the result is in \\$\[2,5,10\]\\$.

```
^                   # tail = K
(?=
    (x+)\1*,\1+$    # \1 = greatest common factor of K and N
)

# Assert that K == \1*2, \1*5, or \1*10, i.e. that K/\1 == 2, 5, or 10
(                   # \2 = one of the below choices, \1 or \1*5
    \1              # tail -= \1
    \B              # Assert tail > 0; this prevents matching on K == \1
|                   # or
    \1{5}           # tail -= \1*5
)
\2?                 # optionally, tail -= \2; this option must be taken if
                    # \2 == \1, because in that choice, the assertion was made
                    # that K > \1
,                   # Assert tail == 0

```

# Regex (ECMAScript), 33 bytes

```
^(((x+)(\3{4})?)\2?),(?!\1+$)\3+$

```

Try it online!

By an interesting coincidence, there's another method that has the same length. It asserts that both:

* \\$k\\$ does not divide \\$n\\$
* At least one member of \\$\\{k, {k\over 2}, {k\over 5}, {k\over 10}\\}\\$ is an integer and divides \\$n\\$ (of course it's redundant to try to assert that for \\$k\\$, as it contradicts the previous assertion, but it results in a shorter regex)

```
^                    # tail = K
# Divide \3 = K, K/2, K/5, or K/10
(                    # \1 = tail == K
    (                # \2 = \3 or \3*5
        (x+)         # \3 = any positive number satisfying the assertions below
        (\3{4})?     # optionally add \3*4 to \2
    )                # tail -= \2
    \2?              # optionally, tail -= \2
)
,                    # Assert tail == 0;
                     # tail = N
(?!\1+$)             # Assert N is not divisible by K
\3+$                 # Assert N is divisible by \3

```

# Regex (Ruby), 31 bytes

```
^(((x+)\3{4}?)\2?),(?!\1+$)\3+$

```

Try it online!

This is a straight port of the above ECMAScript regex. Ruby allows multiple back-to-back quantifiers in situations where the meaning is unambiguous, so `(\3{4})?` can be done as `\3{4}?` instead. In other regex engines, the `?` in `\3{4}?` would be interpreted as modifying the quantifier to be lazy (non-greedy), even though on a constant quantifier that has no effect.

Note that `(A{N,M})?` *cannot* be changed to `A{N,M}?` in Ruby, because in that case the `?` does act as a lazy modifier to the quantifier.

### Regex (ECMAScript), ~~171~~ 151 bytes

Just for kicks, let's see if we can port the algorithm from xnor's Python answer and many subsequent answers, which is to assert that \\$n≢0\pmod k\ \land\ 10n≡0\pmod k\\$. The challenge here is that we can't directly compute \\$10n\\$, since regex can't operate on numbers larger than any of the inputs (of course, we could if \\$k\ge 10n\\$, but in most cases it won't). So we need to emulate the calculation of \\$10n\\$ modulo \\$k\\$.

`^(?=(x*),\1*(x*))(?=(?=\2\B(x*))(x*(?=\3\3)|\2\2))(?=((?=\4(x*))x*(?=\3\6)|\4\2))(?=((?=\5(x*))x*(?=\3\8)|\5\2))(?=((?=\7(x*))x*(?=\3\10)|\7\2))\9{2}\b`

Try it online!

```
^                      # tail = K
(?=(x*),\1*(x*))       # \1 = K; \2 = N % K
(?=
    (?=
        \2             # tail -= \2
        \B             # Assert 0 < \2 < K
        (x*)           # \3 = tail == K - \2 == also a tool to make tail = \2
    )
    (                  # \4 = (\2 + \2) % K == (N * 2) % K
        x*(?=\3\3)     # \4 = head = \2 - \3
    |                  # if above failed due to K - \2 > \2 then fall back on:
        \2\2           # \4 = \2 + \2
    )
)
(?=((?=\4(x*))x*(?=\3\6 )|\4\2))   # \5 = (\4 + \2) % K == (N * 3) % K
(?=((?=\5(x*))x*(?=\3\8 )|\5\2))   # \7 = (\5 + \2) % K == (N * 4) % K
(?=((?=\7(x*))x*(?=\3\10)|\7\2))   # \9 = (\7 + \2) % K == (N * 5) % K

\9{2}                  # tail = tail - \9*2 == K - \9*2
\b                     # Assert tail==K or tail==0, which is equivalent to
                       # asserting (N * 5 * 2) % K == 0

```

This could be shortened greatly in regex flavors with forward-declared backreferences, but it'd still be much longer than 33 bytes.

# Retina 0.8.2, ~~42~~ 40 bytes

```
\d+
$*
^(?=(.+)\1*,\1+$)(\1\B|\1{5})\2?,

```

Try it online!

# Answer
> 2 votes
# APL, 14 bytes

```
{0≠.=⍵|1 10×⍺}

```

Explanations. For example, ⍺ = 3 and ⍵ = 5

```
1 10×⍺ ⍝ Make two-element vector: 3 30
⍵|     ⍝ Remanders of division to 5: 3 0
0≠.=   ⍝ Check if they are zero: 0 1 (no yes)
       ⍝ Then check if answers are different

```

# Answer
> 1 votes
# JavaScript, 22 bytes

```
n=>k=>/\..$/.test(n/k)

```

Checks that there is exactly one decimal place after division.

Try it online!

# Answer
> 1 votes
# Raku, 16 bytes

```
*/(.1&none 1)%%*

```

Try it online!

This is an anonymous function where the asterisks represent the two arguments. The main expression is `* / X %% *`, which checks that the first argument divided by an expression X is divisible by the second argument. `X` here is an and-junction of the number `.1`, and the none-junction of the number `1`. Raku threads the expression over the junction, producing a truthy value if the first argument divided by `.1` is divisble by the second argument, AND the first argument divided by `1` is NOT divisible by the second argument.

The return value is a junction of boolean values, which collapses into a single value in a boolean context. Fortunately, this challenge did not stipulate that the return value must be one of two distinct values, or I'd have to add a `so` to collapse the junction to a regular boolean, for two more bytes.

Note that I used division instead of multiplication because an extra space would have been required to separate the first function argument from the multiplication operator: `* *(10&none 1)%%*`. `.1` is a rational number in Raku, not a floating-point number, so there's no danger of floating-point rounding error.

# Answer
> 1 votes
# Java, 35 bytes

```
n->k->(n/k+"").matches(".+\\.[^0]")

```

Port of my JavaScript answer.

Try it online!

# Java, 20 bytes

```
n->k->n*10%k<1&n%k>0

```

Port of xnor's answer.

Try it online!

# Answer
> 1 votes
# Scala, 20 bytes

```
n=>k=>n%k-n*10%k*k>0

```

Try it in Scastie

If `n` is divisible by `k` but not `n*10`, `n%k-n*10%k*k` is negative. If the both are divisible by `k`, it's 0. If only `n*10` is divisible by `k`, it's positive. If neither is divisible by `k`, it's still negative, because we're multiplying the second by `k` to make it bigger.

# Answer
> 1 votes
# Templates Considered Harmful, 51 bytes

```
Fun<If<Rem<Mul<I<10>,A<1>>,A<2>>,F,Rem<A<1>,A<2>>>>

```

Try it online!

Implementation of xnor's answer. Anonymous function that takes 2 arguments.

```
Fun<
    If<Rem<Mul<I<10>,A<1>>,A<2>>,  # if 10n%k > 0
       F,                          # false
       Rem<A<1>,A<2>>>>            # else n%k

```

# Answer
> 1 votes
## Kustom, 30 bytes

this one is really small for a language for making android widgets O.o

```
$tc(cut,gv(n)/gv(k),-2,1)=.$

```

28+2 extra bytes for global names

# Answer
> 1 votes
# Brachylog, 7 bytes

```
/ṫkt"."

```

Try it online!

### Explanation

```
/          Divide n by k
 ṫ         Cast to string
  kt"."    The penultimate character must be "."

```

# Answer
> 0 votes
# APL (Dyalog Unicode), 18 bytes

```
{≠/0=1|q,10×q←⍺÷⍵}

```

Not as clever as this solution, but whatcha gonna do... :shrug:

```
≠/ ⍝ fold by way of not equals (xor)
  0=1| ⍝ divisibility check
      q,10×q ⍝ concatenate
           q←⍺÷⍵ ⍝ assignment

```

Try it online!

# Answer
> 0 votes
# VBScript, 45 bytes

```
sub f(n,k)
msgbox 10*n mod k<>n mod k
end sub

```

Porting of @xnor's answer a little changed.

Check if 10n is multiple of k but n itself not by checking those conditions aren't equal with `<>`

# Answer
> 0 votes
# Piet \+ ascii-piet, 37 bytes (29×2=58 codels)

```
TABLiIiIAQJjJjJBDFjJBRLBiIIAQJAMVcRrr

```

Try Piet online!

As an image:

This is just rotated to make the ASCII encoding shorter. In ASCII, unminified, without being rotated:

```
tabliiaqjjjbdfjbrlbiiaqjamvcr
    ii   jj   j    i       rr

```

As an image:

Explanation generated by Bubbler's interpreter:

So basically input, duplicate, input, duplicate, push top value of stack three values down (producing b,a,a,b), multiply by 10, swap, modulo, logical not, push top value of stack two values down, modulo, multiply, logical not, logical not, output.

---
Tags: code-golf, math, division
---