title: Can you perform swaps?

text:
# Question
Title: Can you perform swaps?
Today's problem is easy. You're given two strings A and B of equal length consisting of only the characters `(` and `)`. Check whether after any number of operations you can make both strings balanced or not. The only operation allowed is swapping A\[i\] and B\[i\], where i is an arbitrary index.

Here is the definition of a balanced string.

* An empty string is a balanced string.
* If s is a balanced string, `"(" + s + ")"` is a balanced string.
* If x and y are balanced, `x + y` is balanced.

Tests:

```
( ) -> false
() () -> true
((())) ()()() -> true
()())) ((()() -> true
)))((( ((())) -> false
)))))) )))))) -> false
))))))) ))))))) -> false
()))))) (((((() -> false

```

Shortest code wins.

# Answer
# Rust, <sup>~~204~~ ~~179~~ ~~147~~ ~~132~~ ~~123~~ ~~98~~ ~~90~~</sup> 80 bytes

```
|a,b|a.iter().zip(b).fold([0;3],|[c,d,f],(&e,g)|[c+e+g,d^e^g,f.min(c+d)])==[0;3]

```

Attempt This Online!

Radically new algorithm. We know the only possible failure case is if:

* We get 2 simultaneous closing parenthesis when the nesting level is 0
* We get 2 different closing parenthesis when the nesting level is 0

We use `d` to store if there currently is an odd or even number of unequal pairs. If the nesting level `c-d` is negative, we fail. If the nesting level is not 0 or the number of unequal pairs is not even at the end we fail.

`d^((e^!g)+1)/2` should be 1 if e=g and 0 otherwise.

Uses `1` to represent an opening parenthesis and `-1` for closing.
> 9 votes

# Answer
# JavaScript, ~~109~~ ~~107~~ ... 95 bytes

*Thanks to @Arnauld for saving 2 bytes*

```
b=(x,k=0n)=>k<0?0:x?b(x/4n,k+x%4n-2n):!k
f=(l,r,k=0n,x=k&(r^l))=>b(l^x)&b(r^x)||k<l&&f(l,r,++k)

```

returns `false` (for `false`) or `1` (for `true`).

Encodes expressions as base four numbers with `3` for `(` and `1` for `)`

Helper functions for converting strings to the corresponding base 4 numbers

```
e=(s)=>s?4n*e(s.slice(1))+(s[0]=='('?3n:1n):0n
h=(x,y)=>f(e(x),e(y))

h(")))(((","((()))") // -> false

```

Attempt This Online!

*I was unable to verify the last two Test-cases, as the function exceeded the maximum recursion depth (which as far as I known is allowed for code-golf)*

# Explanation

`b` checks if a the expression encoded by the given number is balanced, by counting the difference of `3` digits minus `1` digits and returning 0 if the intermediate count goes below zero, or if the final count is not exactly zero.

`f` checks for all binary numbers `k` less than `l` (swapping the outer brackets cannot balance the expression) if swapping the bits of the two inputs at the positions that are one in `k` will result in a pair of balanced strings. Swapping a bit has no effect if it is the low bit of a base 4 digit where both numbers have a `1` bit, if it is the high bit it will swap the characters that the given positions in the strings.

---

# JavaScript, 108 bytes

```
b=(x,k=0n)=>k<0?0:x?b(x/4n,k+x%4n-2n):!k
f=l=>r=>eval("for(v=0,k=0n;k<l;k++)v|=b(l^k&(r^l))&b(r^k&(r^l));v")

```

uses for-loop to prevent crash due to recursion limit

Attempt This Online!
> 6 votes

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

```
a=>b=>(h=u=>u<d|!a[i]?u|d:h(u+=p=a[i]+b[i++],d^=!p))(i=d=0)

```

Try it online!

Input arrays of numbers: `0.5` for `(`, `-0.5` for `)`. Output falsy (0) for "can be balanced", truthy (non-zero) for "cannot be balanced".

Construct a string `c` using inputs `a` and `b` by:

* if the i-th characters match, aka. `a[i]==b[i]`, then `c[i]=a[i]`
* Otherwise, they mismatch. For the k-th mismatch (1-indexed), `c[i]=')'` when k is odd, and `c[i]='('` when k is even.

Test if `c` is balanced and there are even number of mismatching.

In above code, `u-d` is how many unclosed "(" in string `c`. `d` is a boolean, truthy when next mismatch should be "(".

I’m *feeling* its correctness. Although I don’t have a mathematical proof to it. However, at least no testcase rejects it currently.
> 6 votes

# Answer
# Scala, ~~165~~ 136 bytes

Port of @mousetail's Rust answer in Scala.

---

Golfed version. Try it online!

Saved 29 bytes thanks to the comment of @corvus\_192

```
(a,b)=>(a zip b)./:(Seq((0,0))){case(c,(z,y))=>c.flatMap{case(f,v)=>Seq((f+z,v+y),(f+y,v+z))}filter(g=>g._1>=0&&g._2>=0)}exists((0,0)==)

```

Ungolfed version. Try it online!

```
object Main {
  def main(args: Array[String]): Unit = {
    val f: (Seq[Byte], Seq[Byte]) => Boolean = (a, b) => {
      a.zip(b).foldLeft(Seq[(Int, Int)]((0,0))) { (c, de) =>
        c.flatMap { f =>
          Seq((f._1 + de._1, f._2 + de._2), (f._1 + de._2, f._2 + de._1))
        }.filter(g => g._1 >= 0 && g._2 >= 0)
      }.exists(_ == (0, 0))
    }

    val testCases = Seq(
      (Seq(1.toByte), Seq((-1).toByte), false),
      (Seq(1.toByte, (-1).toByte), Seq(1.toByte, (-1).toByte), true),
      (Seq(1.toByte, 1.toByte, 1.toByte, (-1).toByte, (-1).toByte, (-1).toByte), Seq(1.toByte, (-1).toByte, 1.toByte, (-1).toByte, 1.toByte, (-1).toByte), true),
      (Seq(1.toByte, (-1).toByte, 1.toByte, (-1).toByte, (-1).toByte, (-1).toByte), Seq(1.toByte, 1.toByte, 1.toByte, (-1).toByte, 1.toByte, (-1).toByte), true),
      (Seq((-1).toByte, (-1).toByte, (-1).toByte, 1.toByte, 1.toByte, 1.toByte), Seq(1.toByte, 1.toByte, 1.toByte, (-1).toByte, (-1).toByte, (-1).toByte), false),
      (Seq.fill(6)((-1).toByte), Seq.fill(6)((-1).toByte), false),
      (Seq.fill(7)((-1).toByte), Seq.fill(7)((-1).toByte), false),
      (Seq(1.toByte) ++ Seq.fill(6)((-1).toByte), Seq.fill(6)(1.toByte) ++ Seq((-1).toByte), false)
    )

    for (testCase <- testCases) {
      println(s"${testCase._1} ${testCase._2} expected: ${testCase._3}, got: ${f(testCase._1, testCase._2)}")
    }
  }
}

```
> 5 votes

# Answer
Oops, this doesn't work. Currently being kept as a placeholder.

# C (gcc), ~~92~~ ~~91~~ 90 bytes

```
c;i;r;t(a,b,l)int*a,*b;{for(c=i=0,r=!(l&1);i<l;c+=a[i]+b[i++])r&=c>0|a[i]>0&b[i]>0;r&=!c;}

```

Try it online!

Returns in boolean r, takes the length and arrays where `(` is 1 and `)` is -1.

Less golfed variation:

```
int retFlag;
int test (int* a, int* b, int length) {
    int counter = 0;
    retFlag = !(length & 1);
    for (int i = 0; i < length; i++) {
        retFlag &= counter > 0 || (a[i] > 0 && b[i] > 0);
        counter += a[i] + b[i];
    }
    retFlag &= !counter;
}

```

# C (gcc), ~~73~~ 71 bytes by @c--

```
c;r;t(a,b,l)int*a,*b;{for(c=r=l&1;l--;c+=*b+++*a++)r|=c<-*b**a;r=r<!c;}

```

Try it online!

=======================

Operating hypothesis (WRONG): The strings can be swapped into both being balanced if and only if their length is even and both `F(A, B)` and `F(B, A)` are balanced, where `F(X, Y) := {X[0], Y[0], X[1], Y[1], X[2], Y[2], ...}`.

Reset edit: Previous program relied on caller manually setting internal variables. 3 bytes saved by @c--

Edit R+1: -1 byte from moving stuff into the conveniently empty for loop declaration.

Edit R+2: -1 byte from moving stuff into the empty for loop body. Thanks @c--

Edit R+3: c-- saved two bytes
> 5 votes

# Answer
# Jelly, 13 bytes

```
ZŒpÄṂȯṪƊ€oṚ$Ạ

```

A monadic Link that accepts a pair of lists of \\$\\{1,-1\\}\\$ representing `(` and `)` respectively and yields \\$0\\$ if balancable or \\$1\\$ if not (i.e. outputs the inverse).

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

### How?

```
ZŒpÄṂȯṪƊ€oṚ$Ạ - Link: pair of lists of -1 and 1 := ) and ( respectively
Z             - transpose
 Œp           - Cartesian product
   Ä          - cumulative sums (vectorises)
       Ɗ€     - for each: last three links as a monad:
      Ṫ       -   tail
    Ṃ         -   minimum (of the rest)
     ȯ        -   {minimum} logical OR {tail}
           $  - last two links as a monad:
          Ṛ   -   reverse
         o    -   logical OR (vectorises)
            Ạ - all?

```
> 3 votes

# Answer
## C89, ~~79~~ ~~77~~ 69 bytes

```
r,c;f(*a,*b){for(c=r=1;*a&0<c;++a)c+=*a^*b++?r=-r:*a;return c==1==r;}

```

Using `(int)1` as `'('` and `(int)-1` as `')'`

```
int diff;
int count;
int check(int *a, int *b)
{
    for ( c=1, r=1; *a!=0 && 0<c; ++a, ++b )
    {
        c += (*a != *b) ? (r=-r) : *a;
    }
    return (c==1) == r;
}

```

The logic is based on the consideration that if a solution exists, it will get a count on the nodes of different values lower than what it would get by alternating between `'('` and `')'`, so that would also be a solution
> 3 votes

# Answer
# Haskell, 139 bytes

```
g=(\c->all(>=0) c&&last c==0).scanl(+)0
o j k=any(\(d,e)->g d&&g e).foldr(\(x,y)h->concat[[(x:a,y:b),(y:a,x:b)]|(a,b)<-h])[([],[])]$zip j k

```

`foldr(\(x,y)h->concat[[(x:a,y:b),(y:a,x:b)]|(a,b)<-h])[([],[])]$zip j k` gives a list of all possible pairs. `o` then uses `g`, which determines if a string is balanced, to get the final result. Input is taken as a sequence, with 1 representing `'('` and −1 representing `')'`.

Attempt This Online!
> 2 votes

# Answer
# Haskell, ~~77~~ 73 bytes

```
o a b=all(<1)$scanr(%)0$3:zipWith(+)a b
3%c= -c
0%c=c+1-2*mod c 2
n%c=c+n

```

Attempt This Online!

The other Haskell entry sets the precedent that `(`=`1` and `)`=`-1`. The right-to-left running totals of `A` and `B` are to stay `<1` (and end `>-1`, as checked by `3%`). `A+B` has all information we need. Wlog the running total of `A-B` stays in `[0,2]`. `scanr(%)0` maps `A+B` to the running total of `A+B + (A-B)/2`.
> 2 votes

# Answer
# Nekomata \+ `-e`, 8 bytes

```
Ťᵐ↕∫Ɔž∑≤

```

Attempt This Online!

Takes input as a list of lists of `-1` and `1` representing `(` and `)` respectively. For example, `[[-1,1,1,1],[-1,-1,-1,1]]` represents `())) ((()`.

```
Ťᵐ↕∫Ɔž∑≤
Ť           Transpose
 ᵐ↕         Non-deterministically permute each inner list
   ∫        Cumulative sum
    Ɔ       Split into the last element and the rest
     ž      Check if the last element is all 0s
      ∑     Sum; since the last element is all 0s, this will be 0
       ≤    Is the rest less than or equal to this sum (0)?

```
> 2 votes

# Answer
# Retina 0.8.2, 144 bytes

```
 |^
$&#
+%`^(((\()|(?<-3>\)))*)#(.)(.* ((\()|(?<-7>\)))*)#(.)
$1$4#$5$8#$'¶$1$8#$5$4#
G`^((\()|(?<-2>\)))*(?(2)$)# ((\()|(?<-4>\)))*(?(4)$)#$
^.

```

Try it online! Link includes test cases. Explanation:

```
 |^
$&#

```

Place markers at the start of each string to determine progress through them.

```
^(((\()|(?<-3>\)))*)#(.)(.* ((\()|(?<-7>\)))*)#(.)
$1$4#$5$8#$'¶$1$8#$5$4#

```

If the current prefix of both strings is a validly balanced prefix, then progress through the string, generating results with and without a swap of the next character. Testing of balanced prefixes is unsurprisingly performed using .NET's balancing groups.

```
+%`

```

Repeat the above separately on each intermediate result until no new results can be obtained.

```
G`^((\()|(?<-2>\)))*(?(2)$)# ((\()|(?<-4>\)))*(?(4)$)#$

```

Keep only those results that progressed through the whole string and also are completely balanced rather than simply a balanced prefix (using conditional regex to enforce that the balancing group is now empty).

```
^.

```

Check that we had at least one result.
> 1 votes

# Answer
# Charcoal, 26 bytes

```
∧⁼№⁺θη(Ｌθ⬤θ›№⁺…θ⊕κ…η⊕κ(｜κ¹

```

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

```
    θ                       First input
   ⁺                        Concatenated with
     η                      Second input
  №                         Count of
      )                     Literal string `)`
 ⁼                          Equals
        θ                   First input
       Ｌ                    Length
∧                           Logical And
          θ                 First input
         ⬤                  All characters satisfy
               θ            First input
              …             Truncated to length
                 κ          Current index
                ⊕           Incremented
             ⁺              Concatenated with
                   η        Second input
                  …         Truncated to length
                     κ      Current index
                    ⊕       Incremented
            №               Count of
                      (     Literal string `(`
           ›                Is greater than
                        κ   Current index
                       ｜    Bitwise Or
                         ¹  Literal integer `1`

```

The idea here is that the strings can be balanced if the following two conditions hold:

1. Exactly half of all of the characters are `(`s.
2. For each prefix of both strings, there are more `(`s than the 0-indexed position of the last character of the prefix, plus 1 if that is even.

Examples:

```
1st  2nd  (s   Needed

```

Valid:

```
(    (    2    >1
()   ((   3    >1
())  (((  4    >3
())) ((() 4    >3

```

Invalid:

```
(    (    2    >1
((   ()   3    >1
(()  ())  3    >3
(()) ())( 4    >3

```
> 1 votes

# Answer
# Perl 5, 53 bytes

```
sub{y/(/#/for@_;((pop)&pop)=~/^(#((!?)(?1)*\3)\))+$/}

```

Try it online!

First (wrong) version is in editing history, this one seems to pass. Please tell if it fails some test.
> 1 votes

# Answer
# Ruby, 108 bytes

Brute forces all combinations of the two inputs until it finds one that is balanced. Input is an array containing two arrays of integers, where 1 represents `(` and -1 represents `)`.

```
->a{(v=0,1).product(*[v]*~-a[0].size).any?{i=-1;j=k=0;_1.all?{|n|(j+=a[n][i+=1])|(k+=a[1-n][i])>=0}&&j|k<1}}

```

Attempt This Online!
> 0 votes

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

Input: array, 2(`[`), -2(`]`)

Output: integer, 0(balanced), truthy(not)

```
a=>b=>a.some((v,i)=>0<(S=v-b[i]?S^1:S-v),S=0)|S

```

Try it online!

# JavaScript (Node.js), 52 bytes

```
a=>b=>!a.some((v,i)=>1<(S-=v-b[i]?j^=-2:v),S=j=1)==S

```

Try it online!

```
      1 if true
      0 if some ")" mismatched, in which case S>1 so S!=0
      |
a=>b=>!a.some((v,i)=>1<(S-=v-b[i]?j^=-2:v),S=j=1)==S
                     |
                     '-- If more ")" appeared

```
> 0 votes

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


title: Calculating Transitive Closure

text:
# Question
Title: Calculating Transitive Closure
First attempt at a question.

---

# Calculating Transitive Closure

According to Wikipedia, "the transitive closure \\$R^\*\\$ of a homogeneous binary relation \\$R\\$ on a set \\$X\\$ is the smallest relation on \\$X\\$ that contains \\$R\\$ and is transitive."

Also, "a relation \\$R\\$ on a set \\$X\\$ is transitive if, for all \\$x, y, z \in X\\$, whenever \\$x R y\\$ and \\$y R z\\$ then \\$x R z\\$."

If that jargon did not make much sense, just remember the transitive law:

> If \\$a = b\\$ and \\$b = c\\$, then \\$a = c\\$.

We can use this law for relations on sets.

Basically, transitive closure provides reachability information about a graph. If there is a path from \\$a\\$ to \\$b\\$ (\\$a\\$ "reaches" \\$b\\$), then in a transitively closed graph, \\$a\\$ would relate to \\$b\\$.

Here is another resource about transitive closure if you still do not fully understand the topic.

---

# Challenge

Given a 2D Array (representing the graph \\$R\\$) where each inner array contains only positive integers and represents a vertex, **determine the number of additional edges required to create the transitively closed graph \\$R^\*\\$.**

---

Here's an example (1-indexed):

```
[[2, 3], [3], [4], []]

```

And this would generate a graph that looks like this:

The first array is vertex `1`, and it relates to vertices `2` and `3`. Vertex `2` only relates to `3`. Vertex `3` only relates to `4`. Vertex `4` relates to nothing.

Let's take a look at the steps needed to make this graph transitively closed.

```
1R3 and 3R4, so 1R4       #You can reach 4 from 1, so 1 relates to 4
2R3 and 3R4, so 2R4       #Same goes for 2.

```

Thus, the correct answer to make this graph \\$R^\*\\$ is `2`.

This makes the graph look like this (it is transitively closed):

---

For completeness, here's what the transitively closed 2D array would look like (but this is not what your program should output):

```
[[2, 3, 4], [3, 4], [4], []]

```

---

*Notes:*

*1. There is an array for every vertex, but your code should be able to account for empty arrays (which means the vertex is originally not connected to any other vertex).
2. I don't know if this is important, but you can assume the vertices listed in each inner array will be listed in increasing order.
3. If vertex \\$a\\$ relates to vertex \\$b\\$ and vertex \\$b\\$ relates to vertex \\$a\\$, then vertex \\$a\\$ relates to vertex \\$a\\$ and vertex \\$b\\$ relates to vertex \\$b\\$ (Vertices can be related to themselves, it's called reflexive).*

Picture of reflexive vertex.

*4. If the graph is already transitive, the program should output 0.
5. You can use 1 or 0-indexing. Please just specify which.
6. Many algorithms exist for determining transitive closure. If you'd like an added challenge, attempt this question without researching existing algorithms.*

---

And yeah, that's pretty much it. Here are some test cases (1-indexed):

```
Input                                                           Output

[[], [], []]                                                    0
[[2], [1]]                                                      2
[[2], [1], []]                                                  2
[[2], [1, 3], []]                                               3
[[3], [], [2, 1], [3]]                                          5
[[2, 3, 4], [3, 4], [4], []]                                    0
[[2], [3], [4], [5], [6], [1]]                                  30

```

---

This question is tagged **code-golf**. Standard rules apply.

# Answer
# Itr, 11 bytes *(non competing)*

`#µÍ®ääe*¿<S`

Reads zero-indexed array from standard input, prints the solution to standard output

online interpreter

# Explanation

The solution is based on the observation that an entry `i,j` of the `k`-th power of the adjacency matrix of a graph taken is nonzero iff there is a walk of length `k` in the graph connecting the vertices `i` and `j`. So the adjacency matrix of the transitive closure has ones in all entries that are non-zero in at least one positive power of the adjacency matrix of the original graph.

```
#             ; read the array from standard input
 µÍ®          ; compute adjacency matrix of graph
 µ            ; apply to all elements
  Í           ; convert array to array with ones at the indices given by the values of the array
   ®          ; convert nested array to matrix
    ää        ; duplicate matrix twice
      e       ; compute matrix exponential (sum of all powers of matrix)
       *      ; multiply with original matrix (sum of all positive powers of matrix)
        ¿     ; replace all non-zero entries with one
         <    ; point-wise comparison keeps only the entries that appear in A*e^A but not in A
          S   ; sum up all entries (as all entries are zero or one, this give the number of nonzero entries)
              ; solution is implicitly printed

```

## Disclaimer

*This language was created after I saw the sandbox version of this challenge. While the general consensus seems to be that new languages without built-ins designed specifically for a challenge are allowed, I will still mark this solution as non-competing as this challenge heavily influenced the design process (for instance built-in matrix operations and the `Í` operator were introduced to simplify writing this solution)*

---

# Itr, 12 bytes (no floating point operations)

`#µÍ®äL¹^S¿<S`

`L¹^S` directly computes the sum of the first n powers

```
  ^  ; the matrix to the power of
L¹   ; the range from 1 to the number of rows (does not consume the array)
   S ; sum up all results (taking to the power of a vector will give a vector containing all the powers)

```
> 6 votes

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

```
āεFè]øε˜ÙINèK}˜g

```

0-based indexing.

Try it online or verify all test cases or see what it does step-by-step.

**Explanation:**

```
ā           # Push a list in the range [1, (implicit) input-length]
 ε          # Map over each value:
  F         #  Loop that many times:
   è        #   Index the inner-most values of the current list into the (implicit)
            #   input-list,
            #   which will use the (implicit) input-list in the first iteration
 ]          # Close both the loop and map
  ø         # Zip/transpose; swapping rows/columns
   ε        # Map over each inner nested list:
    ˜       #  Flatten it
     Ù      #  Uniquify its values
      INè   #  Push the map-index'th list of the input
         K  #  Remove those values from the current list
   }˜       # After the map: flatten it to get all additionally created connections
     g      # Pop and push the length
            # (after which this amount is output implicitly as result)

```

Initially I used `.Γè}` instead of `āεFè]`, and although it worked for the example test case, it didn't for any test cases that have reflexive vertices (like test case `[[1],[0]]` for example). Hence the use of `āεFè]` to loop a fixed amount of times based on the amount of input-vertices.
> 6 votes

# Answer
# JavaScript (ES6), 74 bytes

Uses 0-based indexing. Returns `false` for `0`.

```
f=a=>a.some(b=>b.some(i=>a[i].some(v=>!b.includes(v)&&b.push(v))))&&1+f(a)

```

Try it online!

### How?

We look for some sub-list `b` in the main list `a` and some `i` in `b` such that there's at least one value `v` in the sub-list `a[i]` that does not yet exist in `b`. If `v` is found, we add it to `b` and increment the final result. This process is repeated until there's nothing to update anymore.

### Commented

```
f =                  // f is a recursive function taking ...
a =>                 // ... the main list a[]
a.some(b =>          // for each sub-list b[] in a[]:
  b.some(i =>        //   for each value i in b[]:
    a[i].some(v =>   //     for each value v in a[i]:
      !b.includes(v) //       if v is not already in b[],
      && b.push(v)   //       append v to b[] and trigger all some()'s
    )                //     end of some()
  )                  //   end of some()
)                    // end of some()
&& 1 +               // if truthy, increment the final result
f(a)                 // and do a recursive call with the updated list

```
> 5 votes

# Answer
# Jelly, 13 bytes

```
;ịFQʋ€ÐLḟ"⁸FL

```

A monadic Link that accepts \\$R\\$ as a one-indexed adjacency list and yields the required number of edges to add to make a transitive closure, \\$R\*\\$, containing \\$R\\$.

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

### How?

Repeatedly add edges that do not yet exist for all traversable pairs of edges, then count the number of new edges.

```
;ịFQʋ€ÐLḟ"⁸FL - Link: adjacency list, A
      ÐL      - start with X=A and loop until a fixed point applying:
     €        -   for each {node in X}:
    ʋ         -     last four links as a dyad - F(node, X)
 ị            -       {node} index into {X} (vectorises)
;             -       {node} concatenate {that}
  F           -       flatten
   Q          -       deduplicate -> updated node
          ⁸   - chain's left argument -> A
         "    - zip with:
        ḟ     -   {final node} filter discard {original node from A}
           F  - flatten
            L - length

```

---

The end, `ḟ"⁸FL`, seems long, is there something better than this or `;ịFQʋ€ÐLn>0SS` etc.?
> 3 votes

# Answer
# Pyth, 12 bytes

```
ls-Vum{sam@G

```

Try it online!

Takes zero-indexed input.

### Explanation

This may be the most implicitly added variables I've ever had in a Pyth golf.

```
ls-Vum{sam@GkddGQQ    # implicitly add kddGQQ
                      # implicitly assign Q = eval(input())
    u           Q     # find fixed point, repeatedly apply lambda G, H to the previous value, iteration number until we get a result that has occurred before, begin with Q
     m         G      #   map lambda d over G
         m   d        #     map lambda k over d
          @Gk         #       value of G at index k
        a     d       #     append d
       s              #     flatten
      {               #     deduplicate
  -V             Q    # remove any elements originally present in Q, vectorized
 s                    # flatten
l                     # output the length

```
> 3 votes

# Answer
# Python 3.8, 110 bytes

```
f=lambda a,o=0,c=0:a!=(m:=[[*(s:={*sum([a[i]for i in n],n)},c:=c+len(s-{*n}))[0]]for n in a])and c+f(m,o or a)

```

A recursive function that accepts the adjacency list, `a`, and returns the number of required edges (with `False` quacking like `0`).

**Try it online!**
> 3 votes

# Answer
# Python3, 240 bytes:

```
E=enumerate
T=lambda K,g:[(v,l)for i,v in E(K)for _,l in E(K[i+1:])if l not in g[v-1]]
def e(g,n,c=[]):
 for i in g[n-1]:
  yield from T(c+[n,i],g)
  if i not in c:yield from e(g,i,c+[n])
f=lambda g:len({j for i,_ in E(g)for j in e(g,i+1)})

```

Try it online!
> 2 votes

# Answer
# Charcoal, 18 bytes

```
ＦθＦιＦ⁻§θκι«⊞ιλ→»Ｉⅈ

```

Try it online! Link is to verbose version of code. `0`-indexed. Explanation:

```
Ｆθ

```

Loop over each vertex.

```
Ｆι

```

Loop over the list of target indices for this vertex. Note that this list can be extended by the innermost loop in which case the additional indices will also be considered.

```
Ｆ⁻§θκι«

```

Loop over the list of target indices for the target vertex, but exclude indices already present in the list of target indices for the source vertex.

```
⊞ιλ

```

Add this index to the list of target indices for the source vertex.

Increment a counter.

```
»Ｉⅈ

```

Output the final count.

Bonus: Reflexive closure, 8 bytes:

```
ＩΣＥθ¬№ικ

```

Try it online! Link is to verbose version of code.

Bonus 2: Symmetric closure, 14 bytes:

```
ＩΣＥθ↨¹Ｅι¬№§θλκ

```

Try it online! Link is to verbose version of code.
> 2 votes

# Answer
# Python 3.8, 84 bytes

```
lambda a:sum(len((m:={*n},[m:=m|{*a[g]}for f in a for g in m])and m-{*n})for n in a)

```

Try it online!

Takes 0-indexed input. Essentially a port of my Pyth answer with some swapping of loop order.
> 2 votes

# Answer
# MATL, 18 bytes

```
Fi"TX@@g&(]tYezwz-

```

The input is a cell array of numerical vectors, 1-based. Try it online! Or verify all test cases.

### Explanation

The first 11 bytes are used for computing the adjacency matrix from the specified input format. The rest of the code is essentially comparing the matrix before and after matrix exponentiation.

```
F       % Push false, that is, a 1x1 logical matrix containing false
i       % Push input: cell array of numerical vectors
"       % For each entry in the cell array
  T     %   Push true (*)
  X@    %   Push current iteration index, starting at 1 (**)
  @g    %   Push current numerical vector (***)
  &(    %   Write true (*) at specified row (**) and column indieces (***)
        %   in the logical matrix. This may increase the matrix size
]       % End. The stack now contains the adjacency matrix
t       % Duplicate adjacency matrix
Ye      % Compute the logical version of the adjacency matrix of the power
        % of the graph with increasing exponent until the result no longer
        % This is the same as logical(M*expm(M)), where M is the original
        % adjacency matrix and expm is matrix exponeitial, but numerical
        % precision issues are avoided
z       % Number of nonzeros
w       % Swap. Moves copy of original adjacency matrix to top
z       % Number of nonzeros
-       % Subtract. Implicit display

```
> 2 votes

# Answer
# Nekomata \+ `-n`, 16 bytes

```
~ᵉ{$#ᵑ{ˣ@j,u}}∕~

```

Attempt This Online!
> 2 votes

# Answer
# Scala, 102 bytes

Port of @CursorCoercer's Python answer in Scala.

---

Golfed version. Try it online!

```
a=>{var(m,s)=(Set[Int](),0);for(n<-a){m=n.toSet;for(_<-a;g<-m){a(g).foreach(m+=_)};m--=n;s+=m.size};s}

```

Ungolfed version. Try it online!

```
object Main extends App {
  def f(a: List[List[Int]]): Int = {
    var m = Set[Int]()
    var s = 0
    for (n <- a) {
      m = n.toSet
      for (_ <- a; g <- m) {
        a(g).foreach(m += _)
      }
      m --= n
      s += m.size
    }
    s
  }

  val tests = List(
    List(List(), List(), List()),
    List(List(2), List(1)),
    List(List(2), List(1), List()),
    List(List(2), List(1, 3), List()),
    List(List(3), List(), List(2, 1), List(3)),
    List(List(2, 3, 4), List(3, 4), List(4), List()),
    List(List(2), List(3), List(4), List(5), List(6), List(1))
  )

  tests.foreach(test => {
    val test0 = test.map(n => n.map(_ - 1))
    println(s"$test => ${f(test0)}")
  })
}

```
> 2 votes

# Answer
# , 36 bytes

```
[:+/@,@((+/ .*+.])^:_~-])<@i.@#e.&>]

```

Try it online!

Uses 0 indexing.

* `<@i.@#e.&>]` Convert adjacency list to adjacency matrix
* `(+/ .*+.])^:_~` Take transitive closure of matrix multiplication, but any cell that becomes 1 also remains 1 `+.]`.
* `-]` Subtract original adj matrix
* `+/@,@` Count the ones
> 2 votes

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


title: Dither a Grayscale Image

text:
# Question
Title: Dither a Grayscale Image
Dither a grayscale image into pure black and white with your own algorithm.

Guidelines: You must come up with your own new algorithm. You cannot use pre-existing algorithms (ex. Floyd-Steinburg) but you can use the general technique. Your program must be able to read an image and produce an image the same size. This is a popularity contest, so whoever produces the best (closest to original) and most creative (determined by votes) wins. Bonus if the code is short, though this is not necessary.

You can use whatever grayscale image you want as input, it should be larger than 300x300. Any file format is fine.

Example input:

Example output:

This is a pretty good job, but there still are visible lines and patterns.

# Answer
# Fortran

Okay, I'm using an obscure image format called FITS which is used for astronomy. This means there is a Fortran library for reading and writing such images. Also, ImageMagick and Gimp can both read/write FITS images.

The algorithm I use is based on "Sierra Lite" dithering, but with two improvements:
a) I reduce the propagated error by a factor 4/5.
b) I introduce a random variation in the diffusion matrix while keeping its sum constant.
Together these almost completely elminiate the patterns seen in OPs example.

Assuming you have the CFITSIO library installed, compile with

> gfortran -lcfitsio dither.f90

The file names are hard-coded (couldn't be bothered to fix this).

Code:

```
program dither
  integer              :: status,unit,readwrite,blocksize,naxes(2),nfound
  integer              :: group,npixels,bitpix,naxis,i,j,fpixel,un
  real                 :: nullval,diff_mat(3,2),perr
  real, allocatable    :: image(:,:), error(:,:)
  integer, allocatable :: seed(:)
  logical              :: anynull,simple,extend
  character(len=80)    :: filename

  call random_seed(size=Nrand)
  allocate(seed(Nrand))
  open(newunit=un,file="/dev/urandom",access="stream",&
       form="unformatted",action="read",status="old")
  read(un) seed
  close(un)
  call random_seed(put=seed)
  deallocate(seed)

  status=0
  call ftgiou(unit,status)
  filename='PUPPY.FITS'
  readwrite=0
  call ftopen(unit,filename,readwrite,blocksize,status)
  call ftgknj(unit,'NAXIS',1,2,naxes,nfound,status)
  call ftgidt(unit,bitpix,status)
  npixels=naxes(1)*naxes(2)
  group=1
  nullval=-999
  allocate(image(naxes(1),naxes(2)))
  allocate(error(naxes(1)+1,naxes(2)+1))
  call ftgpve(unit,group,1,npixels,nullval,image,anynull,status)
  call ftclos(unit, status)
  call ftfiou(unit, status)

  diff_mat=0.0
  diff_mat(3,1) = 2.0
  diff_mat(1,2) = 1.0
  diff_mat(2,2) = 1.0
  diff_mat=diff_mat/5.0

  error=0.0
  perr=0
  do j=1,naxes(2)
    do i=1,naxes(1)
      p=max(min(image(i,j)+error(i,j),255.0),0.0)
      if (p < 127.0) then
        perr=p
        image(i,j)=0.0
      else
        perr=p-255.0
        image(i,j)=255.0
      endif
      call random_number(r)
      r=0.6*(r-0.5)
      error(i+1,j)=  error(i+1,j)  +perr*(diff_mat(3,1)+r)
      error(i-1,j+1)=error(i-1,j+1)+perr*diff_mat(1,2)
      error(i  ,j+1)=error(i ,j+1) +perr*(diff_mat(2,2)-r)
    end do
  end do

  call ftgiou(unit,status)
  blocksize=1
  filename='PUPPY-OUT.FITS'
  call ftinit(unit,filename,blocksize,status)
  simple=.true.
  naxis=2
  extend=.true.
  call ftphpr(unit,simple,bitpix,naxis,naxes,0,1,extend,status)
  group=1
  fpixel=1
  call ftppre(unit,group,fpixel,npixels,image,status)
  call ftclos(unit, status)
  call ftfiou(unit, status)

  deallocate(image)
  deallocate(error)
end program dither

```

Example output for the puppy image in OPs post:
OPs example output:
> 20 votes

# Answer
## GraphicsMagick/ImageMagick

## Ordered Dither:

```
magick B2DBy.jpg -gamma .45455 -ordered-dither [all] 4x4 ordered4x4g45.pbm

```

Before complaining about my using an "established algorithm" please read the ChangeLog for GraphicsMagick and ImageMagick for April 2003 where you'll see that I implemented the algorithm in those applications. Also, the combination of "-gamma .45455" with "-ordered-dither" is new.

The "-gamma .45455" takes care of the image being too light. The "all" parameter is only needed with GraphicsMagick.

There's banding because there are only 17 graylevels in a 4x4 ordered-dither image. The appearance of banding can be reduced by using an 8x8 ordered-dither which has 65 levels.

Here are the original image, the 4x4 and 8x8 ordered dithered output and the random-threshold output:

I prefer the ordered-dither version, but am including the random-threshold version for completeness.

```
magick B2DBy.jpg -gamma .6 -random-threshold 10x90% random-threshold.pbm

```

The "10x90%" means to render below 10 percent intensity pixels as pure black and above 90 percent as pure white, to avoid having a few lonely specks in those areas.

It's probably worth noting that both are as memory-efficient as they can possibly be. Neither does any diffusion, so they work one pixel at a time, even when writing ordered-dither blocks, and don't need to know anything about the neighboring pixels. ImageMagick and GraphicsMagick process a row at a time, but it's not necessary for these methods. The ordered-dither conversions take less than .04 second real time on my old x86\_64 computer.
> 36 votes

# Answer
I apologize for the code style, I threw this together using some libraries we just built in my java class, and it has a bad case of copy-paste and magic numbers. The algorithm picks random rectangles in the image, and checks if the average brightness is greater in the dithered image or the original image. It then turns a pixel on or off to bring the brightnesses closer in line, preferentially picking pixels that are more different from the original image. I think it does a better job bringing out thin details like the puppy's hair, but the image is noisier because it tries to bring out details even in areas with none.

```
public void dither(){
    int count = 0;
    ditheredFrame.suspendNotifications();
    while(count < 1000000){
        count ++;
        int widthw = 5+r.nextInt(5);
        int heightw = widthw;
        int minx = r.nextInt(width-widthw);
        int miny = r.nextInt(height-heightw);

            Frame targetCropped = targetFrame.crop(minx, miny, widthw, heightw);
            Frame ditherCropped = ditheredFrame.crop(minx, miny, widthw, heightw);

            if(targetCropped.getAverage().getBrightness() > ditherCropped.getAverage().getBrightness() ){
                int x = 0;
                int y = 0;
                double diff = 0;

                for(int i = 1; i < ditherCropped.getWidth()-1; i ++){
                    for(int j = 1; j < ditherCropped.getHeight()-1; j ++){
                        double d = targetCropped.getPixel(i,  j).getBrightness() - ditherCropped.getPixel(i, j).getBrightness();
                        d += .005* targetCropped.getPixel(i+1,  j).getBrightness() - .005*ditherCropped.getPixel(i+1, j).getBrightness();

                        d += .005* targetCropped.getPixel(i-1,  j).getBrightness() - .005*ditherCropped.getPixel(i-1, j).getBrightness();

                        d += .005* targetCropped.getPixel(i,  j+1).getBrightness() -.005* ditherCropped.getPixel(i, j+1).getBrightness();

                        d += .005* targetCropped.getPixel(i,  j-1).getBrightness() - .005*ditherCropped.getPixel(i, j-1).getBrightness();

                        if(d > diff){
                            diff = d;
                            x = i;
                            y = j;
                        }
                    }
                    ditherCropped.setPixel(x,  y,  WHITE);
                }

            } else {
                int x = 0;
                int y = 0;
                double diff = 0;

                for(int i = 1; i < ditherCropped.getWidth()-1; i ++){
                    for(int j = 1; j < ditherCropped.getHeight()-1; j ++){
                        double d =  ditherCropped.getPixel(i, j).getBrightness() -targetCropped.getPixel(i,  j).getBrightness();
                        d += -.005* targetCropped.getPixel(i+1,  j).getBrightness() +.005* ditherCropped.getPixel(i+1, j).getBrightness();

                        d += -.005* targetCropped.getPixel(i-1,  j).getBrightness() +.005* ditherCropped.getPixel(i+1, j).getBrightness();

                        d += -.005* targetCropped.getPixel(i,  j+1).getBrightness() + .005*ditherCropped.getPixel(i, j+1).getBrightness();

                        d += -.005* targetCropped.getPixel(i,  j-1).getBrightness() + .005*ditherCropped.getPixel(i, j-1).getBrightness();

                        if(d > diff){
                            diff = d;
                            x = i;
                            y = j;
                        }
                    }
                    ditherCropped.setPixel(x,  y,  BLACK);
                }
            }

    }
    ditheredFrame.resumeNotifications();
}

```
> 25 votes

# Answer
## Ghostscript (with little help of ImageMagick)

Far from being my 'own new algorithm', but, sorry, could not resist it.

```
convert puppy.jpg puppy.pdf && \
convert puppy.jpg -depth 8 -colorspace Gray -resize 20x20! -negate gray:- | \
gs -q -sDEVICE=ps2write -o- -c \
    '<</Thresholds (%stdin) (r) file 400 string readstring pop
       /HalftoneType 3 /Width 20 /Height 20
     >>sethalftone' \
    -f puppy.pdf | \
gs -q -sDEVICE=pngmono -o puppy.png -

```

Of course it works better without 'same size' restraint.
> 20 votes

# Answer
## JAVA

Here is my submission. Takes a JPG image, calculates pixel per pixel luminosity (thanks to Bonan in this SO question) and then check it against a random pattern for knowing if the resulting pixel will be black or white. Darkerst pixels will be always black and brightest pixels will be always white to preserve image details.

```
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;

import javax.imageio.ImageIO;

public class DitherGrayscale {

    private BufferedImage original;
    private double[] threshold = { 0.25, 0.26, 0.27, 0.28, 0.29, 0.3, 0.31,
            0.32, 0.33, 0.34, 0.35, 0.36, 0.37, 0.38, 0.39, 0.4, 0.41, 0.42,
            0.43, 0.44, 0.45, 0.46, 0.47, 0.48, 0.49, 0.5, 0.51, 0.52, 0.53,
            0.54, 0.55, 0.56, 0.57, 0.58, 0.59, 0.6, 0.61, 0.62, 0.63, 0.64,
            0.65, 0.66, 0.67, 0.68, 0.69 };

    public static void main(String[] args) {
        DitherGrayscale d = new DitherGrayscale();
        d.readOriginal();
        d.dither();

    }

    private void readOriginal() {
        File f = new File("original.jpg");
        try {
            original = ImageIO.read(f);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void dither() {
        BufferedImage imRes = new BufferedImage(original.getWidth(),
                original.getHeight(), BufferedImage.TYPE_INT_RGB);
        Random rn = new Random();
        for (int i = 0; i < original.getWidth(); i++) {
            for (int j = 0; j < original.getHeight(); j++) {

                int color = original.getRGB(i, j);

                int red = (color >>> 16) & 0xFF;
                int green = (color >>> 8) & 0xFF;
                int blue = (color >>> 0) & 0xFF;

                double lum = (red * 0.21f + green * 0.71f + blue * 0.07f) / 255;

                if (lum <= threshold[rn.nextInt(threshold.length)]) {
                    imRes.setRGB(i, j, 0x000000);
                } else {
                    imRes.setRGB(i, j, 0xFFFFFF);
                }

            }
        }
        try {
            ImageIO.write(imRes, "PNG", new File("result.png"));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

```

Other examples:

Also works with full color images:
> 11 votes

# Answer
# CJam

```
lNl_~:H;:W;Nl;1N[{[{ri}W*]{2/{:+}%}:P~}H*]z{P}%:A;H{W{I2/A=J2/=210/[0X9EF]=I2%2*J2%+m>2%N}fI}fJ

```

95 bytes :)
It uses the ASCII PGM (P2) format with no comment line, for both input and output.

The method is very basic: it adds up squares of 2\*2 pixels, converts to the 0..4 range, then uses a corresponding pattern of 4 bits to generate 2\*2 black-and-white pixels.
That also means that the width and height must be even.

Sample:

And a random algorithm in only 27 bytes:

```
lNl_~*:X;Nl;1N{ri256mr>N}X*

```

It uses the same file format.

Sample:

And finally a mixed approach: random dithering with a bias towards a checkerboard pattern; 44 bytes:

```
lNl_~:H;:W;Nl;1NH{W{ri128_mr\IJ+2%*+>N}fI}fJ

```

Sample:
> 9 votes

# Answer
# Python

The idea is following: The image gets divided in to `n x n` tiles. We calculate the average colour each of those tiles. Then we map the colour range `0 - 255` to the range `0 - n*n` which gives us a new value `v`. Then we colour all pixels from that tile black, and randomly colour `v` pixels within that tile white. It is far from optimal but still gives us recognizable results. Depending on the resolution, it works usually best at `n=2` or `n=3`. While in `n=2` you can already find artefacts from the 'simulated colour depth, in case `n=3` it can already get somewhat blurry. I assumed that the images should stay the same size, but you can of course also use this method and just double/triple the size of the generated image in order to get more details.

PS: I know that I am a bit late to the party, I remember that I did not have any ideas when the challenge started but now just had this brain wave=)

```
from PIL import Image
import random
im = Image.open("dog.jpg") #Can be many different formats.
new = im.copy()
pix = im.load()
newpix = new.load()
width,height=im.size
print([width,height])
print(pix[1,1])

window = 3 # input parameter 'n'

area = window*window
for i in range(width//window):     #loop over pixels
    for j in range(height//window):#loop over pixels
        avg = 0
        area_pix = []
        for k in range(window):
            for l in range(window):
                area_pix.append((k,l))#make a list of coordinates within the tile
                try:
                    avg += pix[window*i+k,window*j+l][0]
                    newpix[window*i+k,window*j+l] = (0,0,0) #set everything to black
                except IndexError:
                    avg += 255/2 #just an arbitrary mean value (when were outside of the image)
                                # this is just a dirty trick for coping with images that have
                                # sides that are not multiples of window
        avg = avg/area
        # val = v is the number of pixels within the tile that will be turned white
        val = round(avg/255 * (area+0.99) - 0.5)#0.99 due to rounding errors
        assert val<=area,'something went wrong with the val'
        print(val)
        random.shuffle(area_pix) #randomize pixel coordinates
        for m in range(val):
            rel_coords = area_pix.pop()#find random pixel within tile and turn it white
            newpix[window*i+rel_coords[0],window*j+rel_coords[1]] = (255,255,255)

new.save('dog_dithered'+str(window)+'.jpg')

```

## Results:

`n=2:`

`n=3:`
> 7 votes

# Answer
## Java (1.4+)

I am not sure as to whether I am re-inventing the wheel here but I think it may be unique...

With limited random sequences

Pure random dithering

City image from Averroes's answer

The algorithm uses the concept of localized luminosity energy and normalizing to retain features. The initial version then used a random jitter to produce a dithered look over areas of similar luminosity. However it was not that visually appealing. To counter this, a limited set of limited random sequences are mapped to raw input pixel luminosity and samples are used iteratively and repeatedly yielding dithered looking backgrounds.

```
import java.awt.image.BufferedImage;
import java.io.File;
import javax.imageio.ImageIO;

public class LocalisedEnergyDitherRepeatRandom {

    static private final float EIGHT_BIT_DIVISOR=1.0F/256;
    private static final int KERNEL_SIZE_DIV_2 =4;
    private static final double JITTER_MULTIPLIER=0.01;
    private static final double NO_VARIANCE_JITTER_MULTIPLIER=1.5;
    private static final int RANDOM_SEQUENCE_LENGTH=10;
    private static final int RANDOM_SEQUENCE_COUNT=20;
    private static final boolean USE_RANDOM_SEQUENCES=true;

    public static void main(String args[]) throws Exception
    {
        BufferedImage image = ImageIO.read(new File("data/dog.jpg"));
        final int width = image.getWidth();
        final int height = image.getHeight();
        float[][][] yuvImage =convertToYUVImage(image);
        float[][][] outputYUVImage = new float[width][height][3];
        double circularKernelLumaMean,sum,jitter,outputLuma,variance,inputLuma;
        int circularKernelPixelCount,y,x,kx,ky;
        double[][] randomSequences = new double[RANDOM_SEQUENCE_COUNT][RANDOM_SEQUENCE_LENGTH];
        int[] randomSequenceOffsets = new int[RANDOM_SEQUENCE_COUNT];

        // Generate random sequences
        for (y=0;y<RANDOM_SEQUENCE_COUNT;y++)
        {
            for (x=0;x<RANDOM_SEQUENCE_LENGTH;x++)
            {
                randomSequences[y][x]=Math.random();
            }
        }

        for (y=0;y<height;y++)
        {
            for (x=0;x<width;x++)
            {
                circularKernelLumaMean=0;
                sum=0;
                circularKernelPixelCount=0;

                /// calculate the mean of the localised surrounding pixels contained in
                /// the area of a circle surrounding the pixel.
                for (ky=y-KERNEL_SIZE_DIV_2;ky<y+KERNEL_SIZE_DIV_2;ky++)
                {
                    if (ky>=0 && ky<height)
                    {
                        for (kx=x-KERNEL_SIZE_DIV_2;kx<x+KERNEL_SIZE_DIV_2;kx++)
                        {
                            if (kx>=0 && kx<width)
                            {
                                double distance= Math.sqrt((x-kx)*(x-kx)+(y-ky)*(y-ky));

                                if (distance<=KERNEL_SIZE_DIV_2)
                                {
                                    sum+=yuvImage[kx][ky][0];
                                    circularKernelPixelCount++;
                                }
                            }
                        }
                    }
                }

                circularKernelLumaMean=sum/circularKernelPixelCount;

                /// calculate the variance of the localised surrounding pixels contained in
                /// the area of a circle surrounding the pixel.
                sum =0;

                for (ky=y-KERNEL_SIZE_DIV_2;ky<y+KERNEL_SIZE_DIV_2;ky++)
                {
                    if (ky>=0 && ky<height)
                    {
                        for (kx=x-KERNEL_SIZE_DIV_2;kx<x+KERNEL_SIZE_DIV_2;kx++)
                        {
                            if (kx>=0 && kx<width)
                            {
                                double distance= Math.sqrt((x-kx)*(x-kx)+(y-ky)*(y-ky));

                                if (distance<=KERNEL_SIZE_DIV_2)
                                {
                                    sum+=Math.abs(yuvImage[kx][ky][0]-circularKernelLumaMean);
                                }
                            }
                        }
                    }
                }

                variance = sum/(circularKernelPixelCount-1);

                if (variance==0)
                {
                    // apply some jitter to ensure there are no large blocks of single colour
                    inputLuma=yuvImage[x][y][0];
                    jitter = Math.random()*NO_VARIANCE_JITTER_MULTIPLIER;
                }
                else
                {
                    // normalise the pixel based on localised circular kernel
                    inputLuma = outputYUVImage[x][y][0]=(float) Math.min(1.0, Math.max(0,yuvImage[x][y][0]/(circularKernelLumaMean*2)));
                    jitter = Math.exp(variance)*JITTER_MULTIPLIER;
                }

                if (USE_RANDOM_SEQUENCES)
                {
                    int sequenceIndex =(int) (yuvImage[x][y][0]*RANDOM_SEQUENCE_COUNT);
                    int sequenceOffset = (randomSequenceOffsets[sequenceIndex]++)%RANDOM_SEQUENCE_LENGTH;
                    outputLuma=inputLuma+randomSequences[sequenceIndex][sequenceOffset]*jitter*2-jitter;
                }
                else
                {
                    outputLuma=inputLuma+Math.random()*jitter*2-jitter;
                }

                // convert 8bit luma to 2 bit luma
                outputYUVImage[x][y][0]=outputLuma<0.5?0:1.0f;
            }
        }

        renderYUV(image,outputYUVImage);
        ImageIO.write(image, "png", new File("data/dog.jpg.out.png"));
    }

      /**
       * Converts the given buffered image into a 3-dimensional array of YUV pixels
       * @param image the buffered image to convert
       * @return 3-dimensional array of YUV pixels
       */
      static private float[][][] convertToYUVImage(BufferedImage image)
      {
        final int width = image.getWidth();
        final int height = image.getHeight();
        float[][][] yuv = new float[width][height][3];
        for (int y=0;y<height;y++)
        {
          for (int x=0;x<width;x++)
          {
            int rgb = image.getRGB( x, y );
            yuv[x][y]=rgb2yuv(rgb);
          }
        }
        return yuv;
      }

      /**
       * Renders the given YUV image into the given buffered image.
       * @param image the buffered image to render to
       * @param pixels the YUV image to render.
       * @param dimension the
       */
      static private void renderYUV(BufferedImage image, float[][][] pixels)
      {
        final int height = image.getHeight();
        final int width = image.getWidth();
        int rgb;

        for (int y=0;y<height;y++)
        {
          for (int x=0;x<width;x++)
          {

            rgb = yuv2rgb( pixels[x][y] );
            image.setRGB( x, y,rgb );
          }
        }
      }

      /**
       * Converts a RGB pixel into a YUV pixel
       * @param rgb a pixel encoded as 24 bit RGB
       * @return array representing a pixel. Consisting of Y,U and V components
       */
      static float[] rgb2yuv(int rgb)
      {
        float red = EIGHT_BIT_DIVISOR*((rgb>>16)&0xFF);
        float green = EIGHT_BIT_DIVISOR*((rgb>>8)&0xFF);
        float blue = EIGHT_BIT_DIVISOR*(rgb&0xFF);

        float Y = 0.299F*red + 0.587F * green + 0.114F * blue;
        float U = (blue-Y)*0.565F;
        float V = (red-Y)*0.713F;

        return new float[]{Y,U,V};
      }

      /**
       * Converts a YUV pixel into a RGB pixel
       * @param yuv array representing a pixel. Consisting of Y,U and V components
       * @return a pixel encoded as 24 bit RGB
       */
      static int yuv2rgb(float[] yuv)
      {
        int red = (int) ((yuv[0]+1.403*yuv[2])*256);
        int green = (int) ((yuv[0]-0.344 *yuv[1]- 0.714*yuv[2])*256);
        int blue = (int) ((yuv[0]+1.77*yuv[1])*256);

        // clamp to 0-255 range
        red=red<0?0:red>255?255:red;
        green=green<0?0:green>255?255:green;
        blue=blue<0?0:blue>255?255:blue;

        return (red<<16) | (green<<8) | blue;
      }

}

```
> 7 votes

# Answer
# Dyalog APL

This is an implementation of ordered dither with a special dither array.

The input format is a restricted form of raster PGM while it is also the default style produced by Netpbm programs that requires no comment line, file header separated by newline character rather than arbitrary whitespace, and assumes "maxval" to be 255, so the file can be handled easily with APL's `⎕MAP` system function.

The output format satisfies raster PBM specification.

This program can dither images as large as 3000×2000 in very short time, however for larger image it needs more than default workspace size.

```
∇img←readpgm file;data;size
 data←83 ¯1 ⎕MAP file
⍝ drop magic
 data←(⊢↓⍨⍳∘10)data
 size←⌽⍎⎕UCS ¯1↓(⊢↑⍨⍳∘10)data
 img←size⍴256|(⊢↓⍨⍳∘10)⍣2⊢data
∇

∇img writepbm file;data;size;h;s;tie
 tie←file(⎕NCREATE⍠'IfExists' 'Error')0
 h←10,⍨⎕UCS'P4 ',⍕size←⌽⍴img
 tie ⎕ARBOUT h
 s←8×⌈8÷⍨⊃size
 data←,⍉s↑⍉img
 data←2⊥⍉data⍴⍨8,⍨8÷⍨≢data
 tie ⎕ARBOUT data
 ⎕NUNTIE tie
∇

da←1 8⍴51 25 61 10 45 57 8 16
da⍪←58 6 34 23 1 36 49 30
da⍪←44 32 29 14 41 62 20 12
da⍪←2 21 60 52 47 4 24 55
da⍪←50 9 18 7 38 28 15 40
da⍪←37 56 26 43 59 11 53 35
da⍪←46 13 31 3 48 22 5 63
da⍪←0 19 33 54 17 39 27 42

dither←{
    ⎕IO←0
    x y←⍴⍵
    a b←⍴⍺
    (63×⍵÷255)<(,⍺)[(x y⍴y⍴⍳b)+⍉y x⍴x⍴b×⍳a]
}

'out.pbm' writepbm⍨ da dither readpgm 'input.pgm'

```
> 5 votes

# Answer
> Any file format you want is fine.

Let's define a very compact, theoretical file format for this question as any of the existing file formats have too much overhead to write a quick answer for.

Let the first four bytes of the image file define the width and height of the image in pixels, respectively:

```
00000001 00101100 00000001 00101100
width: 300 px     height: 300 px

```

followed by `w * h` bytes of grayscale values from 0 to 255:

```
10000101 10100101 10111110 11000110 ... [89,996 more bytes]

```

Then, we can define a piece of code in Python (145 bytes) that will take this image and do:

```
import random
f=open("a","rb");g=open("b","wb");g.write(f.read(4))
for i in f.read():g.write('\xff' if ord(i)>random.randint(0,255) else '\x00')

```

which "dithers" by returning white or black with probability equal to the grayscale value of that pixel.

---

Applied on the sample image, it gives something like this:

It's not too pretty, but it does look very similar when scaled down in a preview, and for just 145 bytes of Python, I don't think you can get much better.
> 3 votes

# Answer
# Cobra

Takes a 24-bit or 32-bit PNG/BMP file (JPG produces output with some greys in it). It is also extensible to files containing color.

It uses speed-optimized ELA to dither the image into 3-bit color, which will return as black/white when given your test image.

Did I mention that it's really fast?

```
use System.Drawing
use System.Drawing.Imaging
use System.Runtime.InteropServices
use System.IO

class BW_Dither

    var path as String = Directory.getCurrentDirectory to !
    var rng = Random()

    def main
        file as String = Console.readLine to !
        image as Bitmap = Bitmap(.path+"\\"+file)
        image = .dither(image)
        image.save(.path+"\\test\\image.png")

    def dither(image as Bitmap) as Bitmap

        output as Bitmap = Bitmap(image)

        layers as Bitmap[] = @[ Bitmap(image), Bitmap(image), Bitmap(image),
                                Bitmap(image), Bitmap(image), Bitmap(image),
                                Bitmap(image)]

        layers[0].rotateFlip(RotateFlipType.RotateNoneFlipX)
        layers[1].rotateFlip(RotateFlipType.RotateNoneFlipY)
        layers[2].rotateFlip(RotateFlipType.Rotate90FlipX)
        layers[3].rotateFlip(RotateFlipType.Rotate90FlipY)
        layers[4].rotateFlip(RotateFlipType.Rotate90FlipNone)
        layers[5].rotateFlip(RotateFlipType.Rotate180FlipNone)
        layers[6].rotateFlip(RotateFlipType.Rotate270FlipNone)

        for i in layers.length, layers[i] = .dither_ela(layers[i])

        layers[0].rotateFlip(RotateFlipType.RotateNoneFlipX)
        layers[1].rotateFlip(RotateFlipType.RotateNoneFlipY)
        layers[2].rotateFlip(RotateFlipType.Rotate270FlipY)
        layers[3].rotateFlip(RotateFlipType.Rotate270FlipX)
        layers[4].rotateFlip(RotateFlipType.Rotate270FlipNone)
        layers[5].rotateFlip(RotateFlipType.Rotate180FlipNone)
        layers[6].rotateFlip(RotateFlipType.Rotate90FlipNone)

        vals = List<of List<of uint8[]>>()
        data as List<of uint8[]> = .getData(output)
        for l in layers, vals.add(.getData(l))
        for i in data.count, for c in 3
            x as int = 0
            for n in vals.count, if vals[n][i][c] == 255, x += 1
            if x > 3.5, data[i][c] = 255 to uint8
            if x < 3.5, data[i][c] = 0 to uint8

        .setData(output, data)
        return output

    def dither_ela(image as Bitmap) as Bitmap

        error as decimal[] = @[0d, 0d, 0d]
        rectangle as Rectangle = Rectangle(0, 0, image.width, image.height)
        image_data as BitmapData = image.lockBits(rectangle, ImageLockMode.ReadWrite, image.pixelFormat) to !
        pointer as IntPtr = image_data.scan0
        bytes as uint8[] = uint8[](image_data.stride * image.height)
        pfs as int = Image.getPixelFormatSize(image.pixelFormat) // 8
        Marshal.copy(pointer, bytes, 0, image_data.stride * image.height)

        for y as int in image.height, for x as int in image.width
            position as int = (y * image_data.stride) + (x * pfs)
            for i in 3
                error[i] -= bytes[position + i]
                if Math.abs(error[i] + 255 - bytes[position + i]) < Math.abs(error[i] - bytes[position + i])
                    bytes[position + i] = 255 to uint8
                    error[i] += 255
                else, bytes[position + i] = 0 to uint8

        Marshal.copy(bytes, 0, pointer, image_data.stride * image.height)
        image.unlockBits(image_data)
        return image

    def getData(image as Bitmap) as List<of uint8[]>

        rectangle as Rectangle = Rectangle(0, 0, image.width, image.height)
        image_data as BitmapData = image.lockBits(rectangle, ImageLockMode.ReadOnly, image.pixelFormat) to !
        pointer as IntPtr = image_data.scan0
        bytes as uint8[] = uint8[](image_data.stride * image.height)
        pixels as List<of uint8[]> = List<of uint8[]>()
        for i in image.width * image.height, pixels.add(nil)
        pfs as int = Image.getPixelFormatSize(image.pixelFormat) // 8
        Marshal.copy(pointer, bytes, 0, image_data.stride * image.height)

        count as int = 0
        for y as int in image.height, for x as int in image.width
            position as int = (y * image_data.stride) + (x * pfs)
            if pfs == 4, alpha as uint8 = bytes[position + 3]
            else, alpha as uint8 = 255
            pixels[count] = @[
                                bytes[position + 2], #red
                                bytes[position + 1], #green
                                bytes[position],     #blue
                                alpha]               #alpha
            count += 1

        image.unlockBits(image_data)
        return pixels

    def setData(image as Bitmap, pixels as List<of uint8[]>)
        if pixels.count <> image.width * image.height, throw Exception()
        rectangle as Rectangle = Rectangle(0, 0, image.width, image.height)
        image_data as BitmapData = image.lockBits(rectangle, ImageLockMode.ReadWrite, image.pixelFormat) to !
        pointer as IntPtr = image_data.scan0
        bytes as uint8[] = uint8[](image_data.stride * image.height)
        pfs as int = Image.getPixelFormatSize(image.pixelFormat) // 8
        Marshal.copy(pointer, bytes, 0, image_data.stride * image.height)

        count as int = 0
        for y as int in image.height, for x as int in image.width
            position as int = (y * image_data.stride) + (x * pfs)
            if pfs == 4, bytes[position + 3] = pixels[count][3] #alpha
            bytes[position + 2] = pixels[count][0]              #red
            bytes[position + 1] = pixels[count][1]              #green
            bytes[position] = pixels[count][2]                  #blue
            count += 1

        Marshal.copy(bytes, 0, pointer, image_data.stride * image.height)
        image.unlockBits(image_data)

```
> 3 votes

# Answer
## Java

Low level code, using PNGJ and a noise addition plus basic diffusion. This implementation requires a grayscale 8-bits PNG source.

```
import java.io.File;
import java.util.Random;

import ar.com.hjg.pngj.ImageInfo;
import ar.com.hjg.pngj.ImageLineInt;
import ar.com.hjg.pngj.PngReaderInt;
import ar.com.hjg.pngj.PngWriter;

public class Dither {

    private static void dither1(File file1, File file2) {
        PngReaderInt reader = new PngReaderInt(file1);
        ImageInfo info = reader.imgInfo;
        if( info.bitDepth != 8 && !info.greyscale ) throw new RuntimeException("only 8bits grayscale valid");
        PngWriter writer = new PngWriter(file2, reader.imgInfo);
        ImageLineInt line2 = new ImageLineInt(info);
        int[] y = line2.getScanline();
        int[] ye = new int[info.cols];
        int ex = 0;
        Random rand = new Random();
        while(reader.hasMoreRows()) {
            int[] x = reader.readRowInt().getScanline();
            for( int i = 0; i < info.cols; i++ ) {
                int t = x[i] + ex + ye[i];
                y[i] = t > rand.nextInt(256) ? 255 : 0;
                ex = (t - y[i]) / 2;
                ye[i] = ex / 2;
            }
            writer.writeRow(line2);
        }
        reader.end();
        writer.end();
    }

    public static void main(String[] args) {
        dither1(new File(args[0]), new File(args[1]));
        System.out.println("See output in " + args[1]);
    }

}

```

(Add this jar to your build path if you want to try it).

As a bonus: this is extremely efficient in memory usage (it only stores three rows) so it could be used for huge images.
> 2 votes

# Answer
# Python

The code is quite bad, so I'll try to explain the algorithm. For each pixel, it stores the brightness of the pixel in the variable `brightness`, and changes `brightness` based on the values of `x % 2` and `y % 2`, where `x` and `y` are coordinates of that pixel. This creates a typical two by two regular dithering pattern. Then, `brightness` is randomly changed by some amount to hide banding and strongly visible patterns created by the dithering algorithm.

Finally, `brightness` is changed by the difference between the average brightness of the current pixel and the average brightness of the pixel around it. This makes details and outlines more visible, since small groups of pixels that are very different from their surroundings are more likely to get a different color than their surroundings. The brightness is then rounded to 0 (black) or 1 (white).

The program has four parameters that can be changed to change the result: `dither_details`, which determines how likely pixels with a different brightness than their surroundings are to get a different color than their surroundings; `dither_regular`, which determines how strong the typical two by two dithering pattern is, `dither_random`, which determines the strength of the random dithering; and `s`, which determines how big an area of its surrounding the pixels are compared to.

When `dither_details` equals 999 and `s` equals 2, the program gives a result quite similar to @Moogie's submission (the rectangle-like patterns are likely a product of image compression):

```
import matplotlib.image as mplimg
import matplotlib as mpl
import matplotlib.pyplot as plt
import numpy

image = mplimg.imread("pup.png")

new_im = [
    [0 for x in range(len(image[0]))]
for y in range(len(image))]

def avg(x, y, f):
    sum_ = 0
    n = 0

    for x1 in range(x, x + f):
        for y1 in range(y, y + f):

            if x1 < 0 or x1 >= len(image[0]) or y1 < 0 or y1 >= len(image):
                continue

            n += 1
            sum_ += image[y1][x1]

    return sum_ / n

dither_details = 3.0
dither_regular = 0.15
dither_random = 0.03
s = 3

for x in range(len(image[0])):
    for y in range(len(image)):

        brightness = image[y][x]

        if x % 2 == 0 and y % 2 == 0:
            brightness += dither_regular
        elif x % 2 == 1 and y % 2 == 1:
            brightness += dither_regular / 2
        elif x % 2 == 0 and y % 2 == 1:
            brightness -= dither_regular
        elif x % 2 == 1 and y % 2 == 0:
            brightness -= dither_regular / 2

        brightness += numpy.random.normal(scale = dither_random)

        average_brightness = avg(x - s, y - s, s * 2 + 1)
        brightness += image[y][x] * dither_details - average_brightness * dither_details

        new_im[y][x] = 0 if brightness < 0.5 else 1

dpi = 16
mpl.rcParams['savefig.dpi'] = dpi * 16
plt.figure(figsize=(len(image[0]) / dpi, len(image) / dpi), dpi = dpi * 16)
plt.axis("off")
plt.imshow(new_im, cmap = "gray", interpolation = "nearest")
plt.savefig("dither.png", bbox_inches="tight")
plt.show()

```
> 2 votes

# Answer
# Java

Just a simple RNG-based algorithm, plus some logic for dealing with color images. Has probability *b* of setting any given pixel to white, sets it to black otherwise; where *b* is that pixel's original brightness.

```
import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;
import java.util.Scanner;

import javax.imageio.ImageIO;

public class Ditherizer {
    public static void main(String[]a) throws IOException{
        Scanner input=new Scanner(System.in);
        Random rand=new Random();
        BufferedImage img=ImageIO.read(new File(input.nextLine()));
        for(int x=0;x<img.getWidth();x++){
            for(int y=0;y<img.getHeight();y++){
                Color c=new Color(img.getRGB(x, y));
                int r=c.getRed(),g=c.getGreen(),b=c.getBlue();
                double bright=(r==g&&g==b)?r:Math.sqrt(0.299*r*r+0.587*g*g+0.114*b*b);
                img.setRGB(x,y,(rand.nextInt(256)>bright?Color.BLACK:Color.WHITE).getRGB());
            }
        }
        ImageIO.write(img,"jpg",new File(input.nextLine()));
        input.close();
    }
}

```

Here's a potential result for the dog image:
> 1 votes

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

```
x=>x.map(t=>t>Math.random())

```

Try it online!

Trying to golf one
> 0 votes

---
Tags: popularity-contest, image-processing
---


title: Print all Polynomials

text:
# Question
Title: Print all Polynomials
The set of all polynomials with **integer** coefficients is countable. This means that there is a sequence that contains each polynomial with integer coefficients exactly once.

Your goal is it to write a function or program that outputs such a sequence.

Example (you may use another sequence):

```
// list of integers [i -> Z(i)] : 0,1,-1,2,-2,...
// integer -> polynomial
// 1. factor index n=product_i p_i^k_i
// 2. return polynomial sum_i Z(k_i)*x^(i-1)
1 -> 0     // all powers 0 -> all summands 0
2 -> 1     // 2^1 -> 1*x^0
3 -> x     // 3^1 -> 1*x^1
4 -> -1    // 2^2 -> -1*x^0
5 -> x²    // 5^1 -> 1*x^2
6 -> x+1   // 2^1*3^1 -> 1*x^0+1*x^1
7 -> x³    // 7^1 -> 1*x^3
8 -> 2     // 2^3 -> 2*x^0
9 -> -x    // 3^2 -> -1*x^1
...

```

For ideas how to compute the sequence of all integers see here

Rules:

* Each integer polynomial has to (eventually) appear in the sequence generated by your program
* Polynomials are **not** allowed to appear more than once
* The standard sequence IO-rules apply
* You may output polynomials as lists of coefficients
* Using the empty string/list to represent zero is allowed
* You are allowed to output the coefficients in reverse order (constant coefficient on the left)
* This is the shortest program (per language) wins.

# Answer
> 11 votes
# Python, 56 bytes

```
P=[[0]]
for*t,h in P:print(P[-1]);P+=t+[h,0],t+[(h<1)-h]

```

Try it online!

Prints lists indefinitely as polynomials reversed. The idea is that every nonempty list of integers is generated uniquely by repeatedly applying one of two operations starting from the singleton `[0]`:

1. Append a `[0]`
2. Advance the last element `h` via the map `h -> (h<=0)-h`, which walks through the integers as `0, 1, -1, 2, -2, 3, -3, ...`.

We do a breadth-first walk on this infinite binary tree to generate all these lists. To do this, we keep a list `P` of nodes to explore starting with just the root `[0]`, iterate over it, and when we explore a node `l`, we append to `P` the two children of `l`.

Note that branch (1) creates the lists with a trailing 0 and branch (2) creates all those starting with any other value. So, outputting just the branch (2) nodes gives all nonzero polynomials represented without extra trailing zeroes. We do this by repeatedly printing the last element of `P` after doing the append which puts the branch (2) result last. By also doing this print at the start, we also output the zero polynomial at the root of `P`, which we'd otherwise miss.

*Thanks to loopy walt for -1 byte by flipping the order and Jonathan Allan for -1 from not using `<=`.*

# Answer
> 9 votes
# Python, 75 bytes

```
f=lambda s:s*[0]and[s%-2^r(s//4)]+f(r(s//2))
r=lambda s:s and s%2^2*r(s//4)

```

Attempt This Online!

^^^ Version without string intermediates.

# Python, 48 bytes

```
f=lambda n,i:n and(n>>2**i-1&1)-2*f(n>>2*2**i,i)

```

Attempt This Online!

^^^ This one may be illegal: It takes enumeration index and coefficient index and returns only that coefficient.

Uses @Bubbler's negabinaries instead of my previous method.

# Python, 107 bytes

```
lambda n:g(f"{n:b}"[::-1])or[0]
g=lambda s:"1"in s and[-(s[0]>"0")^int("0"+s[2::2][::-1],2)]+g(s[1::2])or[]

```

Attempt This Online!

If representing the 0 polynomial by the empty list is acceptable, we can save 5 as @JonathanAllan points out.

# Python, 102 bytes

```
lambda n:g(f"{n:b}"[::-1])
g=lambda s:"1"in s and[-(s[0]>"0")^int("0"+s[2::2][::-1],2)]+g(s[1::2])or[]

```

Attempt This Online!

Does not use prime factors. Expects a nonnegative integer and returns the coefficients lowest (constant) to highest.

## How?

Uses binary representation. Coefficient 0 encoded in bits (least significant to most) 1,3,5,7,9,... coefficient 1 encoded in bits 2,6,10,14,..., coefficient 2 encoded in bits 4,12,20,28,..., etc. The bits are simply read as a binary number except that the lsb encodes the sign (more precisely, the presence or absence of a tilde operator i.e. 0 \<-\> -1, 1 \<-\> -2, etc. Advantage over "naive" `-`: no redundancy at 0.)

# Answer
> 7 votes
# Nekomata, 10 bytes

```
Ňƒ$ƥ←2EƂ∙ŋ

```

Attempt This Online!

The zero polynomial is represented by `0`, and other polynomials are represented by an ascending list of coefficients. For example, `x^2 + 2x + 3` is represented by `[3, 2, 1]`.

```
Ňƒ$ƥ←2EƂ∙ŋ
Ň              Choose a natural number n
 ƒ$ƥ←2EƂ∙      Compute the array of exponents of n's prime factorization.
               This is basically Jelly's ÆE operator
         ŋ     Optionally negate each nonzero element

```

# Answer
> 6 votes
# Jelly,  ~~10~~  8 bytes

```
ÆENḂ¡€:2

```

A monadic Link that accepts a positive integer, \\$n\\$, and yields the \\$n^{\text{th}}\\$ integer polynomial as a list of coefficients for increasing powers of \\$x\\$ with no trailing zeros (i.e. `[0, 0, 2, 0, -5]` represents \\$-5x^4+2x^2\\$, and `[]` represents \\$0\\$)

**Try it online!**

### How?

```
ÆENḂ¡€:2 - Link: n
ÆE       - prime factor exponents e.g. n=3*3*7*7*7 -> [0,2,0,3]
     €   - for each {exponent value, e}:
    ¡    -   repeat...
   Ḃ     -   ...number of times: modulo 2 {e} -> 1 if e is odd else 0
  N      -   ...action: negate
      :2 - integer divide by two (vectorises)

```

This gives the same order as the example sequence, just with negated coefficients.

# Answer
> 6 votes
# , 11 bytes

```
_2#._#:@q:]

```

Attempt This Online!

The first half (using prime factorization exponents) is stolen from existing solutions, but the second half is new I guess. To convert "all integers \>= 0" to "all integers", I use the negabinary system. That is, convert each nonnegative integer to base 2 and then interpret the binary sequence as base -2. This is shorter in J than doing a "divmod 2".

# Jelly, 6 bytes

```
ÆEBḅ-2

```

Try it online!

# Answer
> 4 votes
# Thunno 2, 9 bytes

```
ḟıDu@×;2÷

```

Try it online! or verify a few more cases

Port of Jonathan Allan's Jelly answer.

*-1 thanks to @Neil*

#### Explanation

```
ḟıDu@×;2÷  # Implicit input
ḟ          # Prime factor exponents
 ı    ;    # Map over this list:
  D        #  Duplicate current number
   u@      #  -1 ** that
     ×     #  Multiply by the number
       2÷  # Floor divide each by 2
           # Implicit output

```

# Answer
> 3 votes
# Charcoal, ~~56~~ ~~53~~ ~~51~~ 31 bytes

```
≔ＩＥ⮌⍘Ｎ²ιθＷθ«≔Φι﹪λ²θ⟦Ｉ↨⮌Φι¬﹪λ²±²

```

Try it online! Link is to verbose version of code. Outputs the `0`-indexed `n`th polynomial (lowest degree first). Explanation:

```
≔ＩＥ⮌⍘Ｎ²ιθ

```

Input `n` and convert it to base `2`. (Note that if an empty output is acceptable for the zero polynomial, then `≔⮌↨Ｎ²θ` would suffice, saving 3 bytes.)

```
Ｗθ«

```

Repeat until there are no more terms of the polynomial.

```
≔Φι﹪λ²θ

```

Remove the current term from the value.

```
⟦Ｉ↨⮌Φι¬﹪λ²±²

```

Extract the current term from the previous value and convert it from negabinary for output.

~~114~~ ~~111~~ ~~109~~ 87 bytes to pretty-print the output:

```
≔⮌↨Ｎ²θＷθ«⊞υ↨⮌Φθ¬﹪λ²±²≔Φθ﹪λ²θ»∨Φ⪫⮌Ｅυ⎇ι⁺⎇∨¬κ⊖↔ι﹪%+dι§ +-ι⎇κ⁺x⎇⊖κ⍘κ”y⁰¹²³⁴⁵⁶⁷⁸⁹”ωωωω∨κ⁻+ι0

```

Try it online! Link is to verbose version of code. Pretty-prints the `0`-indexed `n`th polynomial. Explanation:

```
≔⮌↨Ｎ²θ

```

Input `n` and convert it to base `2`. (Note that if an empty output is acceptable for the zero polynomial, then `≔⮌↨Ｎ²θ` would suffice, saving 3 bytes.)

```
Ｗθ«

```

Repeat until there are no more terms of the polynomial.

```
⊞υ↨⮌Φθ¬﹪λ²±²

```

Extract the current term from the previous value and convert it from negabinary.

```
≔Φθ﹪λ²θ

```

Remove the current term from the value.

```
»∨Φ⪫⮌Ｅυ⎇ι⁺⎇∨¬κ⊖↔ι﹪%+dι§ +-ι⎇κ⁺x⎇⊖κ⍘κ”y⁰¹²³⁴⁵⁶⁷⁸⁹”ωωωω∨κ⁻+ι0

```

Pretty-print the polynomial. (And I think this must be the first time I've used 4 `ω`s in a row!)

Edit: Now uses @loopywalt's encoding and @Bubbler's negabinary trick.

# Answer
> 3 votes
# Regenerate `-a`, 35 bytes

```
|-?[1-9][0-9]*(,(0|-?[1-9][0-9]*))*

```

Generates polynomials infinitely, given as lists of coefficients from highest to lowest degree. E.g. `1,-2,3` represents \\$x^2-2x+3\\$. The first result is the empty string, representing \\$0\\$.

Attempt This Online!

### Explanation

Iterating over countable sets is basically Regenerate's whole thing, although since it's designed for generating strings, its number-handling is a bit primitive.

```
|-?[1-9][0-9]*(,(0|-?[1-9][0-9]*))*
|                                    Either the result is empty, or:
 -?[1-9][0-9]*                       Lead with a nonzero coefficient:
 -?                                   Possibly negative
   [1-9]                              Starts with a nonzero digit
        [0-9]*                        Continues with 0 or more additional digits
              (                  )*  Continue with zero or more further coefficients:
               ,                      Comma to separate from previous coefficient
                (0|             )     Either the coefficient is 0, or it's nonzero:
                   -?                  Possibly negative
                     [1-9]             Starts with a nonzero digit
                          [0-9]*       Continues with 0 or more additional digits

```

# Answer
> 2 votes
# Python3, 242 bytes:

```
def f(n):
 d,D={},{}
 while n>1:
  k=0
  for i in range(2,n+1):
   if all(i%j for j in range(2,i)if i!=j):
    k+=1;D[i]=k
    if 0==n%i:d[i]=d.get(i,0)+1;n//=i
 return'+'.join(f'{(abs(T:=d[j])//2+1*T%2)*[-1,1][T%2]}*x^{D[j]-1}'for j in d)

```

Returns a pretty-printed polynomial for \\$n\\$.

Try it online!

# Answer
> 2 votes
# Vyxal `r`, 36 bitsv2, 4.5 bytes

```
∆ǏÞnİ

```

Try it Online!

Ports jelly with a few vyxal specific things.

*-15 bits/-1.875 bytes from Bubbler pointing out that `Þn` exists*

## Explained

```
∆ǏÞnİ
∆Ǐ     # To each prime factor exponent from the input
    İ  # get the exponent-th item of
  Þn   # an infinite list of all the integers (positive and negative - 0, 1, -1, 2, -2, ...)

```

Created with the help of Luminespire.

# Answer
> 2 votes
# Scala, 260 bytes

Port of @loopy walt's Python answer in Scala.

---

Golfed version. Attempt This Online!

```
def D(a:Int,b:Int)=if((a>0&&b>0)||(a<0&&b<0))a/b else if(a%b==0)a/b else a/b-1
def M(a:Int,b:Int)=((a%b)+b)%b
def f(s:Int):List[Int]=s match{case 0=>Nil;case _=>(M(s,-2)^r(D(s,4)))::f(r(D(s,2)))}
def r(s:Int):Int=s match{case 0=>0;case _=>M(s,2)^(2*r(D(s,4)))}

```

Ungolfed version. Attempt This Online!

```
object Main {
  def pythonDiv(a: Int, b: Int): Int = {
    if ((a > 0 && b > 0) || (a < 0 && b < 0)) a / b
    else if (a % b == 0) a / b
    else a / b - 1
  }

  def pythonMod(a: Int, b: Int): Int = ((a % b) + b) % b

  def f(s: Int): List[Int] = s match {
    case 0 => Nil
    case _ => List(pythonMod(s, -2) ^ r(pythonDiv(s, 4))) ++ f(r(pythonDiv(s, 2)))
  }

  def r(s: Int): Int = s match {
    case 0 => 0
    case _ => pythonMod(s, 2) ^ (2 * r(pythonDiv(s, 4)))
  }

  def main(args: Array[String]): Unit = {
    for(n <- 0 until 40) println(f(n))
    val distinctLists = (0 until 10000).map(f).toSet
    println(distinctLists.size)
  }
}

```

# Answer
> 2 votes
# Haskell, 96 bytes

```
import Data.List
f=nub$(dropWhile(==0))<$>concatMap(\n->(iterate(map(:)[-n..n]<*>)[[]])!!n)[0..]

```

`iterate(map(:)[-n..n]<*>)[[]]!!n` gets us {−*n*, …, *n*}. Then we drop leading zeros and let `nub` do all the hard work.

Attempt This Online!

# Answer
> 1 votes
# JavaScript (Node.js), 49 bytes

```
f=(n,i=0)=>n?n&1?f(n/2,(i<1)-i):[i,...f(n>>1)]:[]

```

Try it online!

# JavaScript (Node.js), 52 bytes

```
f=(n,i=0)=>n?n&1?f(n/2,i+1):[n&2?~i:i,...f(n>>2)]:[]

```

Try it online!

Write index into binary and convert `x011111` into one coefficient

zero is expressed as `00` so needn't extra check of remaining

# Answer
> 0 votes
# BQN (CBQN), 55 bytes

```
{↑⍷∾{{⊑(=0)⊐0}⊸↓¨∾{⥊([⥊(↕)≍(-↕)])∾⌜⍟⋈⟨⟩}¨↕}¨↕+2}

```

This is a port of my Haskell answer. It's extremely slow.

Attempt This Online!

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