title: Algebraic curve plotter

text:
# Question
Title: Algebraic curve plotter
An algebraic curve is a certain "1D subset" of the "2D-plane" that can be described as set of zeros `{(x,y) in R^2 : f(x,y)=0 }`of a polynomial `f`. Here we consider the 2D-plane as the real plane `R^2` such that we can easily imagine what such a curve could look like, basically a thing you can draw with a pencil.

Examples:

* `0 = x^2 + y^2 -1` a circle of radius 1
* `0 = x^2 + 2y^2 -1` an ellipse
* `0 = xy` a *cross* shape, basically the union of the x-axis and the y-axis
* `0 = y^2 - x` a parabola
* `0 = y^2 - (x^3 - x + 1)` an elliptic curve
* `0 = x^3 + y^3 - 3xy` the folium of Descartes
* `0 = x^4 - (x^2 - y^2)` a lemniscate
* `0 = (x^2 + y^2)^2 - (x^3 - 3xy^2)` a trifolium
* `0 = (x^2 + y^2 - 1)^3 + 27x^2y^2` an astroid

### Task

Given a polynomial `f` (as defined below), and the x/y-ranges, output an black and white image of at least 100x100 pixels that shows the curve as black line on a white background.

### Details

**Color**: You can use any two other colours of your choice, it should just be easy to tell them apart.

**Plot**: Instead of a pixel image you can also output this image as ascii-art, where the background "pixels" should be space/underline or an other character that "looks empty" and the line can be made of a character that looks "full" like `M` or `X` or `#`.

You do not have to worry about aliasing.

You only need to plot lines where the sign of the polynomial changes from one side of the line to the other (that means you could e.g. use the marching square algorithm), you do not have to correctly plot "pathological cases like `0 = x^2` where the sign does *not* change when going from one side of the line to the other. But the line should be continuous and separating the regions of the different signs of `f(x,y)`.

**Polynomial**: The polynomial is given as a `(m+1) x (n+1)` matrix/list of lists of (real) coefficients, in the example below the terms of the coefficients are given in their position:

```
[   1 * 1,   1 * x,   1 * x^2,   1 * x^3,  ... , 1 * x^n ]
[   y * 1,   y * x,   y * x^2,   y * x^4,  ... , y * x^n ]
[   ...  ,   ...   ,   ...   ,    ...   ,  ... ,   ...   ]
[ y^m * 1, y^m * x, y^m * x^2, y^m * x^3 , ..., y^m * x^n]

```

If you prefer, you can assume the matrix to be square (which can always be done with the necessary zero-padding), and if you want, you can also assume that the size of the matrix is given as aditional inputs.

In the following, the examples from above are represented as a matrix defined like this:

```
Circle:       Ellipse:      Parabola:  Cross:    Elliptic Curve: e.t.c
[-1, 0, 1]    [-1, 0, 1]    [ 0,-1]    [ 0, 0]   [-1, 1, 0,-1]
[ 0, 0, 0]    [ 0, 0, 0]    [ 0, 0]    [ 0, 1]   [ 0, 0, 0, 0]
[ 1, 0, 0]    [ 2, 0, 0]    [ 1, 0]              [ 1, 0, 0, 0]

```

Test cases with x-range / y-range:

(In a not so readable but better copy-paste-able format available here on pastebin.)

```
Circle:
[-1, 0, 1]   [-2,2]   [-2,2]
[ 0, 0, 0]
[ 1, 0, 0]

Ellipse:
[-1, 0, 1]   [-2,2]   [-1,1]
[ 0, 0, 0]
[ 2, 0, 0]

Cross:
[ 0, 0]      [-1,2]   [-2,1]
[ 0, 1]

Parabola:
[ 0,-1]      [-1,3]   [-2,2]
[ 0, 0]
[ 1, 0]

Elliptic Curve:
[-1, 1, 0,-1]    [-2,2]   [-3,3]
[ 0, 0, 0, 0]
[ 1, 0, 0, 0]

Folium of Descartes:
[  0,  0,  0,  1]    [-3,3]   [-3,3]
[  0, -3,  0,  0]
[  0,  0,  0,  0]
[  1,  0,  0,  0]

Lemniscate:
[  0,  0, -1,  0,  1]    [-2,2]   [-1,1]
[  0,  0,  0,  0,  0]
[  1,  0,  0,  0,  0]

Trifolium:
[ 0, 0, 0,-1, 1]    [-1,1]   [-1,1]
[ 0, 0, 0, 0, 0]
[ 0, 3, 2, 0, 0]
[ 0, 0, 0, 0, 0]
[ 1, 0, 0, 0, 0]

Astroid:
[ -1,  0,  3,  0, -3,  0,  1]    [-1,1]   [-1,1]
[  0,  0,  0,  0,  0,  0,  0]
[  3,  0, 21,  0,  3,  0,  0]
[  0,  0,  0,  0,  0,  0,  0]
[ -3,  0,  3,  0,  0,  0,  0]
[  0,  0,  0,  0,  0,  0,  0]
[  1,  0,  0,  0,  0,  0,  0]

```

I've got the inspiration for some curves from this pdf.

# Answer
# Haskell, ~~283~~ 275 bytes

The function `g` should be called with the matrix and the two ranges as arguments. The matrix is just a list of lists, the ranges each a two element list.

```
import Data.List
t=transpose
u=tail
z=zipWith
l%x=sum$z(*)l$iterate(*x)1                                   --generate powers and multiply with coefficients
e m y x=[l%x|l<-m]%y                                         --evaluate the encoded polynomial
a#b=[a,a+(b-a)/102..b]                                       --create a range
g m[u,w][i,j]=unlines$v[map((0<).e m y)$u#w|y<-i#j]          --evaluate the function on the grid, get the sign
f g=u[u$u$map fst$scanl(\(r,l)c->(c==l,c))(1<0,1<0) l|l<-g]  --find +- or -+ transitions within lines
a&b|a&&b=' '|0<1='#'                                         --helper function for creating the string
v g=z(z(&))(f g)(t$f$t g)                                    --create the string

```

Here the outputs for the more interesting cases: Note that I had to downsize the resultion from 100x100 to about 40x40 such that it sill fits in the console (just change the hardcoded 102 to a smaller number). Also note that the y-axis is pointing downwards.
> 11 votes

# Answer
# Matlab, ~~114~~ ~~100~~ 92 bytes

The right tool for the job? I use the interesting way Matlab does `printf` to generate a polynomial as a string. This polynomial can be provided to `ezplot` which plots the implicit curve on the specified domain. For readability the code is presented with newlines after ; which isn't needed and isn't counted towards the size.

```
function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%.0f*y^%d',[A(:)';t/h;rem(t,h)]),[W,H])

```

---

## Golfing progress as expandable snippet.

```
Iteration 1, clean arguments, 114 bytes
---------------------------------------
function P(A,W,H)
h=size(A,1);
t=0:numel(A)-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';floor(t/h);rem(t,h)]),[W,H])

Iteration 1.5, historical revisionism (thanks @flawr), 111 bytes
--------------------------------------------------------------
function P(A,W,H)
[h,w]=size(A);
t=0:h*w-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';floor(t/h);rem(t,h)]),[W,H])

Iteration 2, playing dirty, 100 bytes
-------------------------------------
The code can be golfed further if I use that taking matrix sizes as inputs are
fair game, but it feels sad to ruin such neat input arguments. However,
this is code golf and I'll abuse anything I can and I end up at a nice 100 bytes:

function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';floor(t/h);rem(t,h)]),[W,H]);

Iteration 2.5, fix your code (thanks @LuisMendo), 98 bytes
----------------------------------------------------------
function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';fix(t/h);rem(t,h)]),[W,H]);

Iteration 3, more power to printf, 92 bytes [current best]
----------------------------------------------------------
Use `%.0f` instead of `fix`/`floor`.

function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%.0f*y^%d',[A(:)';t/h;rem(t,h)]),[W,H])
```

---

Output of the test cases (click for full view):
> 6 votes

# Answer
# Python 2, 261 bytes

```
E=enumerate
M,[a,c],[b,d]=input()
e=(c-a)/199.
I=200
J=-int((b-d)/e-1)
print'P2',I,J,255
i=I*J
while i:i-=1;x,y=c-i%I*e,b+i/I*e;u,v,w=map(sum,zip(*((z*p/x,z*q/y,z)for q,R in E(M)for p,t in E(R)for z in[t*x**p*y**q])));print int(255*min(1,(w*w/(u*u+v*v))**.5/e))

```

Input format: `matrix,xbounds,ybounds` (e.g. `[[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2]`). Output format: plain PGM.

This estimates the distance from every pixel center to the curve using the first-order approximation *d*(*x*, *y*) = |*p*(*x*, *y*)| / |∇*p*(*x*, *y*)|, where ∇*p* is the gradient of the polynomial *p*. (This is the distance from (*x*, *y*) to the intersection of the tangent plane at (*x*, *y*, *p*(*x*, *y*)) with the *xy*–plane.) Then the pixels where *d*(*x*, *y*) is less than one pixel width of the curve proportionally to *d*(*x*, *y*), resulting in nice antialiased lines (even though that isn’t a requirement).

Here are the same graphs with the distance function divided by 16 to make it visible.
> 6 votes

# Answer
# Python 3.5 + MatPlotLib + Numpy, 352 bytes:

```
from matplotlib.pyplot import*;from numpy import*
def R(M,S,U,r=range):N=linspace;E='+'.join([str(y)+'*'+m for y,m in[q for i,g in zip(M,[[i+'*'+p for p in['1']+['x^%d'%p for p in r(1,len(M[0]))]]for i in['1']+['y^%d'%i for i in r(1,len(M))]])for q in zip(i,g)if q[0]]]);x,y=meshgrid(N(*S,200),N(*U,200));contour(x,y,eval(E.replace('^','**')),0);show()

```

A named function. Pretty long, but hey, I'm just happy I was able to accomplish the task. Takes 3 inputs, which are the `m by n` matrix, the `x`-range, and `y`-range, which should all be in arrays (for example, `[[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2]`). Outputs the completed graph in a new, graphical, interactive window. Will golf this down more of time when I can, but for now, I'm happy with it.

**Final Outputs for the Test Cases:**
> 5 votes

# Answer
# MATL, ~~67~~ 61 bytes

```
8Wt:qwq/t2:"wid*2M1)+i:q!^]!2&!w[1IK2]&!**ss&eZS5Y62&Y+|4=0YG

```

This code runs in release 18.5.0 of the language, which precedes the challenge. Input uses the optional `m`, `n` parameters. The matrix has semicolons as row separators. The exact input format (using the parabola as an example) is

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

```

The code produces an **image** with size 255×255. This can be tested using @Suever's **MATL Online** compiler, which, among other very interesting features, includes graphical output. See for example

This compiler is still in an experimental stage. Please report any issues to @Suever in the MATL chatroom. If the "Run" button doesn't work, try refreshing the page and clicking again.

If you prefer **ASCII output**, the code needs to be modified a little (the changes only affect the first two and last four characters of the code above):

```
101t:qwq/t2:"wid*2M1)+i:q!^]!2&!w[1IK2]&!**ss&eZS5Y62&Y+|4<42*c

```

This produces a 100×100 ASCII grid which uses character `*` to represent the curve. You can also test this with @Dennis' **Try it online!** platform:

Note that the aspect ratio of ASCII output is altered because the characters are slightly higher than are wide.

### Explanation

The code first computes the two-variable polynomial on an *x*-*y* grid. This makes heavy use of broadcasting, computing an intermediate 4D array where each dimension represents *x* values, *y* values, *x* exponents, *y* exponents respectively.

From that function, the zero level line is computed. Since the challenge specifes that only sign changes need to be detected, the code applies 2D convolution with a 2×2 block of ones, and marks a pixel as belonging to the line if not the four values of the block have the same sign.

```
8W      % Push 2^8, that is, 256. (The ASCII-output version pushes 101 instead)
t:q     % Duplicate. Push range [0 1 ... 255]
wq      % Swap. Subtract 1 to obtain 255
/       % Divide. Gives normalized range [0 1/255 2/255... 1]
t       % Duplicate
2:"     % For loop: do this twice
  w     %   Swap top two elements in the stack
  i     %   Input two-number array defining x range (resp. y in second iteration)
  d     %   Difference of the two entries
  *     %   Multiply by normalized range
  2M1)  %   Push the array again and get its first entry
  +     %   Add. This gives the range for x values (resp. y)
  i     %   Input m (n in second iteration)
  :q    %   Range [0 1 ...m-1] (resp. [0 1 ...n-1])
  !     %   Convert to column array
  ^     %   Power, element-wise with broadcast. This gives a matrix of size m×256
        %   (resp. n×256) of powers of x (resp. y) for the range of values computed
        %   previously
]       % End for loop
!       % Transpose. This transforms the n×256 matrix of powers of y into 256×n
2       % Push 2
&!      % Permute dimensions 1 and 3: transforms the 256×n matrix into a 4D array
        % of size 1×n×256×1
w       % Swap top two elements in the stack: bring 256×m matrix to top
[1IK2]  % Push vector [1 3 4 2]
&!      % Permute dimensions as indicated by the vector: transforms the m×256 matrix
        % into a 4D array of size m×1×1×256
*       % Multiply element-wise with broadcast: gives 4D array of size m×n×256×256
        % with mixed powers of x and y for at the grid of x, y values
*       % Implicitly input m×n matrix. Multiply element-wise with broadcast: gives
        % 4D array of size m×n×256×256
ss      % Sum along first two dimensions: gives 4D array of size 1×1×256×256
&e      % Squeeze singleton dimensions: gives matrix of size 256×256. This is the
        % two-variable polynomial evaluated at the x, y grid.
        % Now we need to find the zero level curve of this function. We do this by
        % detecting when the sign of the function changes along any of the two axes
ZS      % Matrix of sign values (1, 0 or -1)
5Y6     % Predefined literal: matrix [1 1; 1 1]
2&Y+    % Compute 2D convolution, keeping only the valid (central) part
|4=     % True if absolute value of result is 4, which indicates no sign changes.
        % (The ASCII version computes a negated version of this, for better display)
0YG     % Display as image. (The ASCII-output version does the following instead:
        % multiply by 42 and convert to char. 42 is ASCII for '*', and character 0
        % is shown as space. The 2D char array is then implicitly displayed)

```

### All test cases

Here are all inputs in the appropriate format, in case you want to try:

```
Circle:
[-2,2]
3
[-2,2]
3
[-1, 0, 1; 0, 0, 0; 1, 0, 0]

Ellipse:
[-2,2]
3
[-1,1]
3
[-1, 0, 1; 0, 0, 0; 2, 0, 0]

Cross:
[-1,2]
2
[-2,1]
2
[0, 0; 0, 1]

Parabola:
[-1,3]
3
[-2,2]
2
[0,-1; 0, 0; 1, 0]

Elliptic Curve:
[-2,2]
3
[-3,3]
4
[-1, 1, 0,-1; 0, 0, 0, 0; 1, 0, 0, 0]

Folium of Descartes:
[-3,3]
4
[-3,3]
4
[0,  0,  0,  1; 0, -3,  0,  0; 0,  0,  0,  0; 1,  0,  0,  0]

Lemniscate:
[-2,2]
3
[-1,1]
5
[0,  0, -1,  0,  1; 0,  0,  0,  0,  0; 1,  0,  0,  0,  0]

Trifolium:
[-1,1]
5
[-1,1]
5
[0, 0, 0,-1, 1; 0, 0, 0, 0, 0; 0, 3, 2, 0, 0; 0, 0, 0, 0, 0; 1, 0, 0, 0, 0]

Astroid
[-1,1]
7
[-1,1]
7
[-1,  0,  3,  0, -3,  0,  1; 0,  0,  0,  0,  0,  0,  0; 3,  0, 21,  0,  3,  0,  0; 0,  0,  0,  0,  0,  0,  0; -3,  0,  3,  0,  0,  0,  0; 0,  0,  0,  0,  0,  0,  0; 1,  0,  0,  0,  0,  0,  0]

```
> 5 votes

---
Tags: code-golf, ascii-art, graphical-output, abstract-algebra, polynomials
---


title: Linear combination of two vectors

text:
# Question
Title: Linear combination of two vectors
# Executive summary

Given input representing two vectors and their respective "weights", produce output that also represents the weighted sum of those vectors.

# Challenge

The input will consist of one or more lines of the following characters:

* exactly one occurrence of the digit 0, which represents the origin in a two-dimensional plane;
* exactly two other digits (1-9; may or may not be the same digit), whose positions relative to the origin represent vectors, and whose values represent the weights attached to thse vectors;
* some number of "background characters". The solver may choose a specific background character; for example, I will choose "." (mostly for human readability). Alternately, the background characters can be anything that look like blank space.

(The solver can choose whether the input is a single multi-line string or an array of one-line strings.)

For example, the input

```
....2
.0...
...3.

```

represents a vector at coordinates (3,1) with weight 2, and a vector at coordinates (2,-1) with weight 3.

The output should be almost the same as the input, with the following changes:

* a "result character", chosen by the solver, to be added at the position specified by weighted sum of the input vectors (equivalently, at the position that is the appropriate linear combination of the input vectors);
* as many background characters as are needed to fit the origin, the two input vectors, and the output vector in the same picture. Extra background characters can be included if desired; the only constraint is that, if the background character is a visible character, then the entire output must be rectangular in shape and every character not representing a vector must be the background character. (If blank space is used as background characters, then these constraints don't need to be enforced.)

(In general, if we have one vector (v,w) with weight a and second vector (x,y) with weight b, their weighted sum is a(v,w)+b(x,y) = (av+bx,aw+by).)

In the previous example, the appropriate linear combination is 2\*(3,1) + 3\*(2,-1) = (12,-1). If we use "X" as the result character, then the output could look like

```
....2.........
.0............
...3.........X

```

or

```
................
...2............
0...............
..3.........X...
................
................

```

Usual scoring: the shortest answer, in bytes, wins.

# Example input and output

If blank space is used, the above input would look like

```
    2
 0
   3

```

and the output would look like

```
    2
 0
   3         X

```

Leading/trailing whitespace characters/lines are irrelevant; if they're invisible to the reader, it's fine. (That being said, for the rest of the examples I'll go back to using "." for the background character, to make it easier to read.)

If both vectors have weight 1, then the result will look like a parallelogram: the input

```
.1.
...
1.0

```

leads to the output

```
X.1.
....
.1.0

```

Note this parallelogram can be degenerate if the input vectors are collinear: the input

```
0.1..1

```

leads to the output

```
0.1..1.X

```

It is possible for the result vector to equal one of the input vectors or the origin; in this case, it simply overwrites the input character. For example, the input

```
..2.0.1...

```

yields the output

```
..X.0.1...

```

(where in input and/or output, the leading and trailing periods could be deleted). The input

```
.....3
......
...0..
......
......
2.....

```

yields the output

```
.....3
......
...X..
......
......
2.....

```

Finally, the input

```
90
.8

```

yields the output

```
........90
.........8
..........
..........
..........
..........
..........
..........
X.........

```

# Answer
> 7 votes
# MATL, 48 bytes

```
tZyyX:UX>*Yat48-tt0>*3#fbbhb~2#fh-*s7M+'X'wZ}4$(

```

The background character is space. Input is a 2D char array with rows separated by semicolons. So the tests cases have respective inputs:

```
['    2'; ' 0   '; '   3 ']
[' 1 '; '   '; '1 0']
['0 1  1']
['  2 0 1   ']
['     3'; '      '; '   0  '; '      '; '      '; '2     ']
['90'; ' 8']

```

The output includes a significant amount of padding whitespace.

**Try it online!**

# Answer
> 2 votes
# Python 3, ~~374~~ 355 bytes

Not too refined python solution that is very generous with padding (uses maximum chessboard distance). Input is a single line where rows are separated with pipes | (although the algorithm can easily use anything not alphanumerical that isn't a newline or a EOF). Anything non alphanumeric or | works for input padding, output padding uses periods. Feedback and improvement from more seasoned python golfers is appreciated.

*Edit: Some improvements thanks to @TheBikingViking. Also added even more margins since I wasn't quite generous enough with padding.*

```
s=input()
l=[len(s),1+s.find('|')]['|'in s]
P=sorted([int(c),i%l,i//l]for i,c in enumerate(s)if c.isalnum())
L=X=Y=0
P[0][0]=-sum(p[0]for p in P)
for w,x,y in P:L=max(abs(x),abs(y),L);X+=x*w;Y+=y*w
P+=[['X',P[0][1]+X,P[0][2]+Y]]
P[0][0]=0
L=2*max(abs(X),abs(Y),L)
S=[2*L*["."]for _ in[0]*2*L]
for w,x,y in P:S[L+y][L+x]=str(w)
for s in S:print(''.join(s))

```

# Answer
> 2 votes
# JavaScript, 534 528 502 bytes

```
n="indexOf"
J="join"
B=X=>X.split(O)
O='\n'
w=i[n](O)+1
h=B(i).length
Z=(X,Y,R)=>{C[R]+=X-1;return Array(X)[J](Y)}
C=[0,0,0]
G=(X,E,T,U,R)=>X>0&E>=0?Z(X+E+1+T,U,R):""
o=i[n]("0")
L=X=>Math.floor(X/(w-1))
l=L(o)
c=o%w
x=y=0
j=i
for(z="1";z<="9";z++){while(p=~j[n](z)){j=j.replace(z," ")
x+=~p%w-l
y+=L(~p)-c}}
I=B(i).map(X=>G(-x,-l,0," ",0)+X+G(x,l-w+2,0," ",2))
N=Z(I[0].length+1," ",2)
A=B(G(-y,-c,0,N+O,1)+I[J](O)+G(y,c-h,1,O+N,2))
M=y+c+C[1]
O=""
m=B(A[M])
m[x+l+C[0]/h]="x"
A[M]=m[J]("")
A[J]("\n")

```

Note that the padding is optimal. This program assumes that i contains the raw string, with the lines separated by `\n` characters. The padding is done with spaces, and the result character is a lowercase `x`.

This is my first attempt at code-golfing.

Technical stuff: \- The program's size roughly doubled (and its complexity went up dramatically) to just take into account the result character, mostly because JavaScript strings are immutable.

---

Line by line explanation:

```
n="indexOf"
J="join"
B=X=>X.split(O)

```

I use those a lot, so storing them in strings saved me some space. You can see below that for the `split` function, I have simply created an alias; this is because I only needed one argument, the other one being constant. For `indexOf` and `join`, it would however have been longer.

```
O='\n'
w=i[n](O)+1
h=B(i).length

```

Nothing complicated here, I'm reading the width and height of the initial array. Note the use of `i[n]` to access `indexOf`, while `split` is handled differently.

```
Z=(X,Y,R)=>{C[R]+=X-1;return Array(X)[J](Y)}

```

This is getting interesting. This function basically creates concatenates J-1 times the string X and returns it. This is used to generate strings of spaces for the padding.

```
C=[0,0,0]

```

This array will contain the number of lines and columns added by the padding (off by a factor h in the first case). The last cell is a junk one, and prevents me from having an additional argument in the function below.

```
G=(X,E,T,U,R)=>X>0&E>=0?Z(X+E+1+T,U,R):""

```

This function alone handles the padding (both lines and columns); it determines, based on a coordinate of the result vector (X), and the number of lines/columns to generate (E), whether it is necessary to create one. the `X+E+1+T` is just a trick to save some space, `U` is the filling string (a space for columns, and an entire line for lines), and we'll come back to `R`. This function basically returns, in the case of a line, the padding required at the beginning or the end of said line, and, in the case of a column, it returns the padding lines required either before or after the original lines.

```
o=i[n]("0")
L=X=>Math.floor(X/(w-1))
l=L(o)
c=o%w

```

Here we read the position of the origin, and we retrieve its coordinates. L is a function to convert an index into a line number.

```
x=y=0
j=i
for(z="1";z<="9";z++){
    while(p=~j[n](z)){
        j=j.replace(z," ")
        x+=~p%w-l
        y+=L(~p)-c
    }
}

```

I added some whitespace to make this easier to read. What happens here is that for each possible number, we keep looking for it in the original string. The `~` trick is relatively common in Javascript; it is the bitwise NOT operator, but all that matters here is that `~-1==0`, which allows me to test for the end of the loop. I then erase the character in the string (which is why I made a copy), this allowing me to continue the search as long as needed. I then add the coordinates of the vector to `(x, y)`, using a simple substraction.

```
I=B(i).map(X=>G(-x,-l,0," ",0)+X+G(x,l-w+2,0," ",2))

```

I here split the original string into lines, and for each line, I call `G` which will generate the padding before and after the lines. The `l-w+2` and so on come from a simple index calculation which allows me to test whether I need to add padding or not. For example, if `x>0` and `x+l-w+1>0`, then `(x+l-w+1)+1` spaces must be added after the line. The `+x` is being removed due to it being the first parameter, and the `X+E+1+T` used in the definition of `G`.

A similar thing is done for the first characters, and then for the columns. There is a lot of factorization here allowing me to use only one function. Note the last parameter; in the first case, I want to write to `C[0]` to be able to know later how many columns I added at the beginning of each line; this allows me to retrieve the final position of the result character. I do however not care about the columns added after the original line, which is why the second call to `G` writes to the junk cell `C[2]` which is unused.

```
N=Z(I[0].length+1," ",2)

```

Here I simply read the new length of the lines, and create a line of spaces from it. This will be used to create the vertical padding.

```
A=B(G(-y,-c,0,N+O,1)+I[J](O)+G(y,c-h,1,O+N,2))

```

This is exactly the same as two lines above. The only difference is writing to `C[1]` this time, and using the separators `N+O` and `O+N`. Remember that `O` is a newline, and `N` is a line of spaces. I then apply `B` on the result to split it again (I need to retrieve the line containing the result character to edit it).

```
M=y+c+C[1]

```

This is the vertical index of the resulting character.

```
O=""
m=B(A[M])
m[x+l+C[0]/h]="x"

```

Here I am forced to modify `O` to be able to split the appropriate line into an array of characters. This is because JavaScript strings are immutable; the only way to edit a string is to convert it into an array (which is what I'm doing here), edit at the right position, and join the string again. Also note the `h` factor, which is because the `G` function was called once per initial line.

```
A[M]=m[J]("")
A[J]("\n")

```

I finally replace the new string in the array, and join it again into a string. Woohoo!

---
Tags: code-golf, math, ascii-art
---


title: "Break" a number

text:
# Question
Title: "Break" a number
# Origins

**tl;dw (too lazy, didn't write):** thought of it right before I fell asleep

# Challenge

**Breaking** a number is defined as the following steps:

* Take a number or a parseable data type as input in any allowed way.
* Duplicate the first digit (64 -\> 664)
* Subtract 4 from the last digit (664 -\> 660)
* If the subtraction gets a negative last digit, move the negative sign (-) to the front of the number (73 -\> 773 -\> -771)
* If the original number was negative, and the last digit becomes negative, remove all negative signs entirely. (-44441 -\> 444443)
* Output the number in any allowed way.

Here are a few test cases:

```
64 -> 660
73 -> -771
thisisnotanumber -> (handle the situation)
432188 -> 4432184
-83213 -> 883211 (two negative signs turn into a positive)
0 -> -4 (0 -> 00 -> 0-4 -> -04 -> -4)

```

# Clarifications

Standard loopholes are disallowed.

By "parseable data type", I mean any data type (String, Float, etc) that can be converted into the number type your program/function uses (Integer, Number, etc).

Your answer can be a function or a program. In both cases, provide an explanation of the code.

If it is a function, give a usage of it.

Test cases (or online interpreter) would be a nice plus to your answer.

Preceding 0s (-04) aren't allowed.

Behavior should be exactly replicated from the test cases above.

# Answer
> 2 votes
## Batch, 105 bytes

```
@set/an=%1,n*=s=n^>^>31^|1
@set n=%n:~0,1%%n%
@cmd/cset/ad=n%%10,e=d-4,t=e^^^>^^^>31^^^|1,(n-d+e*t)*s*t

```

Alternatively the first line can be `@set/as=%1^>^>31^|1,n=%1*s`, also for 105 bytes. Explanation (without quoting metacharacters):

```
set /a n = %1               Get parameter
set /a s = n >> 31 | 1      Get sign of parameter
set /a n *= s               Get absolute value of parameter
set n=%n:~0,1%%n%           Duplicate the first digit
cmd /c                      Cause the final result to be printed
set /a d = n % 10           Get last digit
set /a e = d - 4            Calculate new last digit
set /a t = e >> 31 | 1      Get sign of new last digit
set /a e *= t               Get absolute value of new last digit
set /a (n - d + e) * s * t  Replace last digit and correct sign of result

```

# Answer
> 2 votes
# Ruby, ~~88~~ 87 + 3 (`-n` flag) = 90 bytes

Regex approach that reads lines from STDIN. Probably better solved with Perl if it's just regex like this?

Returns a nonsense `NoMethodError` if the input is not a number, which costs 14 bytes. If there's no need to worry about invalid inputs like that (the spec implied it needed handling) then the first line of the code can be removed.

*-2 bytes from @Dada*

```
+(~/^-?\d+$/)
sub(/\d/){$&*2}
sub(/.$/){$&.to_i-4}
p sub(/(-)?(.+)-/){$1?$2:?-+$2}.to_i

```

# Answer
> 0 votes
# Pyth, 31 bytes

```
*i++hJja0QTPJa0K-eJ4T^_1x<K0<Q0

```

Naive implementation of the question.

Test suite.

# Answer
> 0 votes
# Python, ~~79~~ 78 Bytes

```
lambda x:"+-"[(int(x)<0)!=(int(x[-1])-4<0)]+x[1]+x[1:-1]+str(int(x[-1])-4)[-1]

```

anonymous lambda function, does all of the four parts, then adds them together. Expects input as a string with explicit sign e.g. "+64", output is of the same form. Throws ValueError if the string cannot be converted to an int.

# Answer
> 0 votes
# C, 191 bytes

```
f(char*n){if(!isdigit(*n)&!isdigit(n[1]))return 0;char*m;strcpy(m+1,n);*m=m[1];if(*n==45)m[1]=m[2];int a=strlen(n);if(m[a]<52)m[a]=100-m[a],m--,*m=45;else m[a]-=4;return atoi(m[1]^45?m:m+2);}

```

Ungolfed with explanations:

```
f(char*n){
    if(!isdigit(*n)&!isdigit(n[1])) /* if first two chars aren't digits
                                     * if it was only the first one, negative numbers wouldn't pass
                                     * if it was only the second one, 0 wouldn't pass */
        return 0;        // handling
    char*m;
    strcpy(m+1,n);        // copy leaving space for doubling the number
    *m=m[1];              // double the first digit or the minus sign
    if(*n==45)            // if negative
        m[1]=m[2];        // double the first digit
    int a=strlen(n);      /* length of the nunber
                           * it doesn't let me save 2 bytes, i dunno why. */
    if(m[a]<52)           // if the last digit is less than 4
        m[a]=100-m[a],    // subtract 4
        m--,              // leave space for minus sign
        *m=45;            // put minus sign
    else
        m[a]-=4;          // subtract 4 from the last digit
    return atoi(m[1]^45?m:m+2); /* if there are two minus signs, skip them,
                                 * turn the string into an integer, and return */
}

```

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


# Question
Title: Go to opposite corner of rectangle in all directions - Harder
This is essentially the same thing as this question, except harder. You are again to write a program that gets from the lower-left corner of a rectangle to the upper-right corner. **However, this time diagonal moves are allowed.**

The program will accept an ordered pair `(width, height)`, and use these as the dimensions for a rectangle. Your program will then create an ASCII-art of the solution (use `.` for an empty square, `#` for part of the solution, and `X` for starting square) and count the number of moves it takes to reach the endpoint.

**Example**

Input: `(5, 6)`

Output:

```
....#
....#
...#.
..#..
.#...
X....
Move count: 5

```

Shortest answer in bytes wins!

# Answer
> 1 votes
# MATL, 38 bytes

```
'.#X'!iSPXytf0)Jh1w(tzqDQI1()Gd0<?!]XP

```

**Try it online!**

### Explanation

Let `m` and `n` be the sorted inputs, such that `m` is greater than or equal to `n`. The code initially builds an `m`x`n` matrix as follows:

* Value 2 along the main diagonal, and on the lower part of the last column. This corresponds to character `#`. The number of these entries minus 1 is the move count.
* Value 3 at entry (1,1), corresponding to the `X`.
* The remaining entries contain 1, corresponding to character `.`

If needed, the matrix is now transposed so that it has the desired shape. Note that the first dimension of a matrix is its height, not width, so it corresponds to the second input.

The matrix is then flipped upside down so that `X` appears at the bottom of the first column, and its entries are used as indices into the string `'.#X'` to produce the desired 2D char array.

```
'.#X'    % push this string
!        % transpose into a column
i        % input array
SP       % sort it in non-increasing order
Xy       % identity matrix with that size: fill diagonal with 1, rest entries are 0
tf0)     % linear index of last 1
Jh       % append 1j (imaginary unit): linear index of lowest part of last column
1w(      % fill those entries with 1
tzq      % duplicate. Number of nonzero entries minus 1: this is the move count
D        % display move count (and remove it from the stack)
Q        % add 1. Matrix now contains values 1 and 2
I1(      % set first entry (in linear order) to value 3
)        % use matrix as index into the initial string. Gives 2D char array
Gd0<     % push input array again. Is it decreasing?
?        % if so
  !      %   transpose char array
]        % end
XP       % flip upside down. Implicitly display

```

# Answer
> 5 votes
## Pyth, ~~46~~ ~~45~~ 44 bytes

```
eSKtMQjsM_mm?sJ,kd?q#J.umtWbbNeSKK\#\.\XhQeQ

```

Try it here.

Explanation:

```
move-count-printing:

  K     assign K to...
     Q  the input, a 2-length array...
   tM   with each element decremented
eS      take the max and output it (this is the number of moves)

main path-finding logic:

    mm                     hQeQ  map over x-values and y-values...
        J,kd                     assign J to [x,y]
      ?s                         if both x and y are NOT zero (sum is truthy)...
            ?q#J[...]              if [x,y] is present in [...] (see below)...
                     \#            ... put a # at this position in the output
                       \.          ... else, put a . at this position
                         \X      ... else, put the X here (at [0,0])
jsM_                             reverse and output in the proper format

the [...] part in the code above, which finds positions where #s go:

.u      eSKK  cumulative reduce on <number of moves> elements, starting at K,
                which is [max_x, max_y] as assigned at the beginning
  m    N      map over x and y...
   tWbb       decrement, only if the value is > 0

```

# Answer
> 2 votes
# JavaScript (ES6), 132

*Edit* 2 bytes saved thx @Neil

```
(w,h)=>[...Array(--h)].map((_,i)=>R(w-i)+'#'+R(i),--w,R=(n,c='.')=>c.repeat(n>w?w:n>0&&n)).join`
`+`
x${R(w-h,'#')+R(h)}
`+(h>w?h:w)

```

**Test**

```
f=(w,h)=>[...Array(--h)].map((_,i)=>R(w-i)+'#'+R(i),--w,R=(n,c='.')=>c.repeat(n>w?w:n>0&&n)).join`
`+`
x${R(w-h,'#')+R(h)}
`+(h>w?h:w)

function test() {
  var w,h
  [w,h]=I.value.match(/\d+/g)
  O.textContent=f(w,h)
}

test()
```

```
Test <input id=I value="4 5"><button onclick="test()">-></button>
<pre id=O></pre>
```

# Answer
> 0 votes
# Python 3, ~~161~~ 156 bytes

```
def f(w,h):
 x=[['.']*w for i in[0]*h];i=0
 while i<w or i<h:x[~min(i,h-1)][min(i,w-1)]=['#','X'][i<1];i+=1
 for i in x:print(''.join(i))
 print(max(w,h)-1)

```

A function that takes input via argument and prints the ascii-art, followed by the move count, to STDOUT.

**How it works**

The program first creates a list of lists, where each list represents one row of the grid and each element of the component lists is `.`. Each element that should be `#` has the property that if the output grid was square, the ordinates representing its location would be equal; hence, looping over some index `i` and inserting `#` at location `(i, i)` would give the desired output. However, the grid is not always square, and thus the indices are clamped to the grid by taking the minimum of the index and width/height (decremented due to zero-indexing) as required. If the index is zero, the current position must be the bottom-left entry, and thus `X` is instead inserted. Next, the elements in each line are concatenated, and each line is printed to STDOUT. The number of moves is the maximum of the width/height decremented; this is also printed.

Try it on Ideone

# Answer
> 0 votes
## Javascript (using external library) (235 bytes)

Jeez this was hard! Well...my library wasn't really the right task for this haha. But I liked the challenge

```
(x,y)=>{r=x-1;s=y-1;m=Math.max(r,s);n=Math.min(r,s);l=_.RangeDown(s,y).WriteLine(z=>_.Range(0,x).Write("",w=>z==0&&w==0?"X":(z==w||(z==s&&w>=n)||(w==r&&z>=n))?"#":"."));return l+"\r\nMove count: "+(l.length-l.split("#").join("").length)}

```

Link to lib: https://github.com/mvegh1/Enumerable

Code explanation: Create function of 2 variables. Store x-1 and y-1 into variables. Store max and min of those into variables. Create a vertically descending range of numbers from (y-1) for a count of y. For each element on the vertical range, write a line for the current element, according to the complex predicate. That predicate creates an ascending range of integers from 0, for a count of x. For each element in that range, concatenate into 1 string according to a complex predicate. That predicate checks if on bottom left, else checks if on diagonal, else checks we're at X or Y border. Finally, all of that was stored in a variable. Then to get the move count, we basically just count the #'s. Then concatenate that to the stored variable, and return the result

That was a mouthful haha. The screenshot has the wrong bytecount because I found a way to save 4 bytes while posting this

EDIT: I see other answers aren't putting "Move count: " in their output, but mine is. If that isn't a requirement, that shaves a bunch of bytes...

---
Tags: code-golf, ascii-art, grid, counting
---


title: Randomly Assign People to Tasks

text:
# Question
Title: Randomly Assign People to Tasks
The challenge is to assign people to tasks randomly~. From stdin you get 2 lines. Line one is a comma-separated list of names. Line 2 is a comma-separated list of jobs. The output required is one line per task person combo. The line should be formatted as Name:task. If there are not enough people for jobs or vice verse then they will not be output.

~ Randomly is defined as each run with the same input has a reasonably different output.

Example Input:

```
Bob,John,Susan,Josie,Kim,Tom
Bins,Floor,Windows

```

Example Output:

```
Bob:Windows
Susan:Bins
Kim:Floor

```

# Answer
> 3 votes
## 05AB1E, 7 bytes

**Code:**

```
.r².r)ø

```

Try it online

**Following the input/output spec strictly (16 bytes):**

```
.r².r)øvy`r?':?,

```

**Explained:**

```
.r                # radomize first input
  ².r             # randomize second input
     )ø           # merge the lists to an array of pairs cutting out extras
       vy`r?':?,  # format output

```

Try it online

# Answer
> 2 votes
# Java 7, ~~240~~ ~~239~~ 238 bytes

```
import java.util.*;class M{public static void main(String[]a){String[]p=a[0].split(",");List j=new ArrayList(Arrays.asList(a[1].split(",")));for(int i=0;j.size()>0;)System.out.println(p[i++]+":"+j.remove((int)(Math.random()*j.size())));}}

```

Can most likely be golfed more with some arrays magic, instead of `List j=new ArrayList(Arrays.asList(a[1].split(",")));`..

**Ungolfed:**

Try it here

```
import java.util.*;

class M{
    public static void main(String[] a){
        String[] p = a[0].split(",");
        List j = new ArrayList(Arrays.asList(a[1].split(",")));
        for(int i = 0; j.size() > 0;){
            System.out.println(p[i++] + ":" + j.remove((int)(Math.random() * j.size())));
        }
    }
}

```

# Answer
> 1 votes
# Pyth, 6 bytes

```
CmO.pd

```

Try it online!

### How it works:

```
CmO.pd
        (implicitly) takes the evaluated input
 m   d  for each "line":
   .p       generate all permutations
  O         choose one randomly
C       truncating transpose

```

# Following strictly the input/output format:

(16 bytes)

```
jjL\:CmO.pcd\,.z

```

Try it online!

### How it works:

```
jjL\:CmO.pcd\,.z
              .z  takes all lines
      m    d      for each line:
          c \,        split by ","
        .p            generate all permutations
       O              choose one randomly
     C            truncating transpose
 jL\:             join every pair by ":"
j                 join all pairs by newlines

```

# Answer
> 1 votes
# Jelly, 13 bytes

```
Œ!€X€ZL’$ÐfŒṘ

```

Try it online!

# Answer
> 1 votes
# Mathcad, \[tbd\] bytes

csort(M,n) sorts matrix M on column n. augment joins two arrays columnwise. runif(n,a,b) returns a vector of n uniformly-distributed numbers over the range a..b. concat(a,b) concatenates strings a and b.

With due apologies to Messrs Gilbert and Sullivan.

---

Mathcad scoring system yet to be determined (must get round to posting something on Meta ...). However, this solution clearly wouldn't be a contender for anything other than a Programming Language specific leaderboard. Taking a rough keyboard equivalence, and noting that Mathcad uses keyboard shortcuts for entering programming and some other operators, it takes around 100 "bytes".

# Answer
> 0 votes
## JavaScript (Firefox 30-57), 82 bytes

```
(a,b,s=a=>a.sort(_=>Math.random()-.5),c=s(b))=>[for(x of s(a))if(c[0])[x,c.pop()]]

```

Uses bogus sort to shuffle. Version which accepts two string parameters of comma-separated names and returns lines of colon-separated matchups for 110 bytes, where `\n` represents the literal newline character:

```
(a,b,s=a=>a.sort(_=>Math.random()-.5),c=s(b.split`,`))=>[for(x of s(a.split`,`))if(c[0])x+':'+c.pop()].join`\n`

```

# Answer
> 0 votes
## Q, 38 Bytes

```
t:{$[n:&/#:'x:{(-#x)?x}'x;+n#/:x;0N]}

```

NOTE.- input and output format not exactly as proposed (see test)

**Test**

```
."\\S ",$7h$.z.t    /To accomplish a random output we mofify seed based on internal clock
t(`Bob`John`Susan`Josie`Kim`Tom; `Bins`Floor`Windows)
/generates (`Susan`Windows;`Kim`Bins;`John`Floor) (a different result each run)

```

**Explanation**

`(-seqLen)?seq` Shuffles the sequence

`x:{(-#x)?x}'x` shuffles each sequence of x (argument with sequence of names and sequence of works) and reassign to x

`n:&/#:'x` Assigns to n the minimum over (&/) each sequence lengths (#:'x)

`$[n;+n#/:x;0N]` If n (if n is not 0), executes flip n take of each seq, Else returns null

# Answer
> 0 votes
# Ruby, 69 bytes

```
n=gets.split(/,|\n/).shuffle;puts gets.split(',').map{|j|n.pop+':'+j}

```

**Ungolfed:**

```
names = gets.split(/,|\n/).shuffle
jobs = gets.split(',')
jobs.each do |job|
    name = names.pop
    puts "#{name}:#{job}"
end

```

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


title: Draw a Fibonacci Network!

text:
# Question
Title: Draw a Fibonacci Network!
# What are Fibonacci networks?

> In 1202, an Italian mathematician known as Fibonacci posed the following problem:
>
> "A male and a female rabbit are born at the beginning of the year. We assume the following conditions:
>
> 1.After reaching the age of two months, each pair produces a mixed pair, (one male, one female), and then another mixed pair each month thereafter.
>
> 2.No deaths occur during the year."
>
> How many rabbits will there be at the end of the year?

Sources for graph and problem statement

# Challenge

Your challenge is to write a program/function to draw an ASCII art to output or a text file, or a graphical picture to a file/screen of a graph with following settings:

1. At 0th tick, there is one newly-born node.
2. Every newly born node creates a normal node after one tick after being born and gets deactivated.
3. A normal node creates a normal node and a newly-born node one tick after its birth and gets deactivated.

Your program will get the non-negative value `n` as input, and will draw the graph at the `n`th tick. Note that your program can draw newly-born nodes and normal nodes differently, but this is not necessary.

# Rules

* You must not use any built-in Fibonacci sequence function or mathematical constants or similar.
* If your program outputs to a file, it must be either a text file in a suitable and viewable format and encoding, or an image file in a suitable and viewable format with recognizable colors (for example, an image format that can be uploaded to SE).
* Your program can draw graph in any size, any shape and any alignment but the nodes and connections must be recognizable. Tree-shaped graphs (like the graph in "What are Fibonacci networks?" section) are recommended, but not necessary.
* Common code golf rules apply to this challenge.

# Examples

```
Input: 2
Possible Output:
*
|
*
| \
* *

Input: 0
Possible Output:
*

```

> Input: 5
>
> Possible Graphical Output:

This is a . Shortest code wins. Good luck!

# Answer
> 7 votes
# Pyth, 31 bytes

```
Ms+0m+Wd+J+G"| "+G1+\-gJtd_UHgb

```

Try it online

### How it works

```
M                                  def g(G, H):
    m                     _UH        map for d in [H - 1, …, 0]:
         J+G"| "                       assign J = G + "| "
        +       +G1                    J + G + 1
     +Wd                               conditional +, if d is truthy (nonzero):
                   +\-gJtd               "-" + g(J, d - 1)
  +0                                 prepend 0
 s                                   concatenate
                             gbQ   g("\n", input)

```

### Output for 6

```
0
|
1-0
| |
| 1-0
| | |
| | 1-0
| | |
| | 1
| |
| 1-0
| | |
| | 1
| |
| 1-0
| |
| 1
|
1-0
| |
| 1-0
| | |
| | 1
| |
| 1-0
| |
| 1
|
1-0
| |
| 1-0
| |
| 1
|
1-0
| |
| 1
|
1-0
|
1

```

# Pyth, 43 bytes

```
Mc+WH`G++WG\-+j"
| "g0tH"
`-"j"
  "g1tHbjg0

```

Try it online

### Output for 6

```
0-1-0-1-0-1-0
  |   |   `-1
  |   `-1-0-1
  |     `-1-0
  |       `-1
  `-1-0-1-0-1
    |   `-1-0
    |     `-1
    `-1-0-1-0
      |   `-1
      `-1-0-1
        `-1-0
          `-1

```

# Answer
> 5 votes
# HTML5/JavaScript, 1262 bytes

This is my code which displays a Fibonacci network. You can just paste it into a file with a name like `index.html` and run it in your favourite browser (I only tested Chrome and Firefox though). When you launch it, it asks you for the desired number of generations. It uses the HTML5 `<canvas>` tag to display the image.

```
<script>let t,p,o,c=[],q=50,r=20,s=25;function d(o){return JSON.parse(JSON.stringify(o));}function e(a,x,y){o.beginPath();o.fillStyle=a?"red":"#000";o.arc(x*q+s,y*q+s,r,0,2*3.14159);o.fill();}function f(a,b,c,d){o.beginPath();o.strokeStyle="blue";o.lineWidth=3;o.moveTo(a*q+s,b*q+s);o.lineTo(c*q+s,d*q+s);o.stroke();}function g(i){return c[i].a+c[i].c;}function h(i){return c[i].b+c[i].d;}function k(j,e,f,b,n,x,y,z){f=j;b=0;while(1){if(!e){f.t=g(t);f.u=0;f.v=f.t;f.w=f.b;}else{n=t-b+1;x=t-b;z=e.b%2?(g(n)+g(x)+1):(-(g(n)+h(x)+1));f.t=e.v+z;f.u=e.w+1;f.v=f.t;f.w=f.u+f.b;}if(!f.a)break;b+=f.b+1;e=f;f=f.z;}return {a:f.b==0,x:f.v,y:f.w};}function l(j,c,b){b=k(j);f(b.x,b.y,c.x,c.y);e(b.a,b.x,b.y);return b;}function m(j){while(j.a)j=j.z;return j;}function n(j,o,p,q,r,s){if(o>t)return;q=l(j,p);r=d(j);m(r).b++;n(r,o+1,q);if(m(j).b>0){r=d(j);s=m(r);s.a=!0;s.z={a:!1,b:0};n(r,o+1,q);}}function b(i,z,y){t=parseInt(prompt());if(isNaN(t)||t<0)t=0;p=document.getElementById("o");c.push({a:0,b:0,c:0,d:0,e:1});for(i=1;i<t+1;i++){z=c[c.length-1];y={a:(i>1?i%2:0)+z.c,b:(i>1?1-i%2:0)+z.d,c:z.a+z.c,d:z.b+z.d};y.e=y.a+y.b+y.c+y.d;c.push(y);}p.width=q*(c[c.length-1].e+1);p.height=q*(t+1);o=p.getContext("2d");n({a:!1,b:0},0,0);}</script><body onload="b()"><canvas id="o">

```

An example for 6 generations would be this one:

As you can see, newly born nodes are colored in red, the others are black.

For reference, this is my ungolfed, development code that does exactly the same:

```
<html>
 <head>
  <meta charset="utf-8">
  <title>Fibonacci Graph</title>
  <script type="text/javascript">
   let totalGenerations;
   let canvas, ctx;
   let individualCount = [];
   let individualDrawSize = 50, individualDrawRadius = 20, individualDrawOffset = 25;

   function generateIndividualCount()
   {
    individualCount.push(
    {
     babiesL: 0,   //number of babies on the left side of the main individual
     babiesR: 0,
     adultsL: 0,
     adultsR: 0,
     total: 1   //total number of individuals (sum of all other members+1, because the main individual counts as well)
    });

    for(let i=1; i<totalGenerations+1; i++)
    {
     let last = individualCount[individualCount.length - 1];
     let next =
     {
      //make an adult alternate between having a baby at the left and the right side (right side first)
      babiesL: (i>1 ? i%2 : 0) + last.adultsL,
      babiesR: (i>1 ? 1-i%2 : 0) + last.adultsR,
      adultsL: last.babiesL + last.adultsL,
      adultsR: last.babiesR + last.adultsR
     };
     next.total = next.babiesL + next.babiesR + next.adultsL + next.adultsR;
     individualCount.push(next);
    }
   }

   function setupContext()
   {
    canvas.width = individualDrawSize * (individualCount[individualCount.length - 1].total + 1);
    canvas.height = individualDrawSize * (totalGenerations + 1);
    ctx = canvas.getContext("2d");
   }

   function deepCopy(obj)
   {
    return JSON.parse(JSON.stringify(obj));
   }

   function drawIndividual(isBaby, x, y)
   {
    ctx.beginPath();
    ctx.fillStyle = isBaby ? "red" : "black";
    ctx.arc(x*individualDrawSize + individualDrawOffset, y*individualDrawSize + individualDrawOffset, individualDrawRadius, 0, 2*Math.PI);
    ctx.fill();
   }

   function drawLine(x1, y1, x2, y2)
   {
    ctx.beginPath();
    ctx.strokeStyle = "blue";
    ctx.lineWidth = 3;
    ctx.moveTo(x1*individualDrawSize + individualDrawOffset, y1*individualDrawSize + individualDrawOffset);
    ctx.lineTo(x2*individualDrawSize + individualDrawOffset, y2*individualDrawSize + individualDrawOffset);
    ctx.stroke();
   }

   function getIndividualCountLeft(i)  //left like in "the opposite of right"
   {
    return individualCount[i].babiesL + individualCount[i].adultsL;
   }

   function getIndividualCountRight(i)
   {
    return individualCount[i].babiesR + individualCount[i].adultsR;
   }

   function getPosition(ancestorInformation)
   {
    let prevInfo;
    let tempInfo = ancestorInformation;
    let currDepth = 0;

    while(1)
    {
     if(prevInfo == undefined)
     {
      tempInfo.birthX = getIndividualCountLeft(totalGenerations);
      tempInfo.birthY = 0;

      tempInfo.givingBirthX = tempInfo.birthX;
      tempInfo.givingBirthY = tempInfo.ageAtGivingBirth;
     }
     else
     {
      let generationsLeftForParent = totalGenerations - (currDepth-1);
      let generationsLeftForChild = totalGenerations - currDepth;    //left like in "to go" or "There are 42 cookies left"
      let isLeftBranch = (prevInfo.ageAtGivingBirth % 2 == 0);
      let distanceToParent;

      if(isLeftBranch)
       distanceToParent = -(getIndividualCountLeft(generationsLeftForParent) + getIndividualCountRight(generationsLeftForChild) + 1);
      else
       //some of these directions may seem odd, but because the parent subtree begins with a left branch (and individualCount only contains data for trees beginning with a right branch), it needs to be inversed
       //if individualCount would have been generated for trees beginning with a left node, all of the getIndividualCountLeft/getIndividualCountRight function would need to be inversed
       //or, when individualCount would have been generated for both cases, functions like getIndividualCountRight_LeftBegin and getIndividualCountLeft_RightBegin could be used
       distanceToParent = getIndividualCountLeft(generationsLeftForParent) + getIndividualCountLeft(generationsLeftForChild) + 1;  //+1, because the previous value of distanceToParent is just the number of empty fields (on the x axis) between the parent and the child

      tempInfo.birthX = prevInfo.givingBirthX + distanceToParent;
      tempInfo.birthY = prevInfo.givingBirthY + 1;

      tempInfo.givingBirthX = tempInfo.birthX;
      tempInfo.givingBirthY = tempInfo.birthY + tempInfo.ageAtGivingBirth;
     }
     if(!tempInfo.isParent)
      break;
     currDepth += tempInfo.ageAtGivingBirth + 1;
     prevInfo = tempInfo;
     tempInfo = tempInfo.child;
    }

    return { isBaby: tempInfo.ageAtGivingBirth==0, x: tempInfo.givingBirthX, y: tempInfo.givingBirthY };
   }

   function draw(ancestorInformation, parentPos)
   {
    let pos = getPosition(ancestorInformation);
    drawLine(pos.x, pos.y, parentPos.x, parentPos.y);
    drawIndividual(pos.isBaby, pos.x, pos.y);
    return pos;
   }

   function getDeepestChild(ancestorInformation)
   {
    while(ancestorInformation.isParent)
     ancestorInformation = ancestorInformation.child;
    return ancestorInformation;
   }

   function drawAll(ancestorInformation, depth, parentPos)
   {
    if(depth > totalGenerations)
     return;

    let pos = draw(ancestorInformation, parentPos);
    let newAncestorInformation = deepCopy(ancestorInformation);
    getDeepestChild(newAncestorInformation).ageAtGivingBirth++;
    drawAll(newAncestorInformation, depth + 1, pos);

    if(getDeepestChild(ancestorInformation).ageAtGivingBirth > 0)
    {
     newAncestorInformation = deepCopy(ancestorInformation);
     let deepestChild = getDeepestChild(newAncestorInformation);
     deepestChild.isParent = true;
     deepestChild.child = { isParent: false, ageAtGivingBirth: 0 };
     drawAll(newAncestorInformation, depth + 1, pos);
    }
   }

   function load()
   {
    totalGenerations = parseInt(prompt("Number of generations?"));
    if(isNaN(totalGenerations)  ||  totalGenerations < 0)
     totalGenerations = 0;
    canvas = document.getElementById("output");
    generateIndividualCount();
    setupContext();
    drawAll({ isParent: false, ageAtGivingBirth: 0 }, 0, 0);     //although this individual does not really give birth after it has been born, it still has an attribute called "ageAtGivingBirth" (like its parents) to achieve a similar effect
   }
  </script>
 </head>
 <body onload="load()">
  <canvas id="output" style="position:absolute; top:10px; left:10px" width="1200" height="600">Canvas not supported...</canvas>
 </body>
</html>
```

---
Tags: code-golf, ascii-art, kolmogorov-complexity, graphical-output, fibonacci
---


title: "Add one" to every color in an image

text:
# Question
Title: "Add one" to every color in an image
You would simply take this image and make every color added one to every hexadecimal digit. For example, `#49de5f` would become `#5aef60` (with the `9` looping to an `a`, and the `f` looping to a `0`.)

This would also mean that all white (`#ffffff`) would become black (`#000000`) because all `f` loops back to `0`, but all black will become a lighter shade of black (`#111111`).

Scoring is based on the least number of bytes used, as this is a question.

Use the below image as the input image for your code, and put the output image of your code into your answer.

If you want to, you can also use this other rainbow image:

# Answer
> 5 votes
## Pyke, ~~17~~ 13 bytes

```
.Fh16j%ijcjs 8{

```

Try it here!

```
.F            - for i in deep_for(input):
  h16%        -    (i+1)%16
          +   -   ^+V
      i16+    -    (i+16)
           8{ -  unset_bit(8, ^)

```

Takes input as a 3d integer array of pixels and outputs in the same format

# Answer
> 7 votes
## Mathematica, 78 bytes

```
Image@Apply[16#+#2&,Mod[IntegerDigits[#~ImageData~"Byte",16,2]+1,16]/255,{3}]&

```

Takes and returns an image object (to create an image object, just paste the image into Mathematica).

Result for the test case:

Taking input and returning output as a 3D array of integer channel values, this reduces to **51 bytes**:

```
Apply[16#+#2&,Mod[IntegerDigits[#,16,2]+1,16],{3}]&

```

But those meta posts don't have an overwhelming amount of support yet, so I'm going with the 78-byte version for now.

# Answer
> 4 votes
## Python, 226 bytes

Now, it's valid !

Use the Pillow library.

```
from PIL import Image
m=Image.open(input()).convert("RGB")
for y in range(m.size[1]):
 for x in range(m.size[0]):
    t=m.getpixel((x,y))
    h=t[0]+(t[1]<<8)+(t[2]<<16)+1118481
    m.putpixel((x,y),(h&255,h>>8&255,h>>16&255))
m.show()

```

Output:

Thanks to @TuukkaX for saving 9 bytes !
Thanks to @mbomb007 for saving 18 bytes !

# Answer
> 4 votes
# Verilog, 220 bytes:

> * Programs may take input as an array of RGB pixel values with dimensions
> * Programs may output via an array of RGB pixel values with dimensions

It's currently not clear as to how the dimensions are to be provided and if the array is to be streamed or provided all at once. I'm going to stream it 8 bits at a time using a clock signal (with a valid-data flag that goes low after the entire image has been processed) and input/output the dimensions as 32-bit integers:

```
module a(input[31:0]w,input[31:0]h,input[7:0]d,input c,output[31:0]W,output[31:0]H,output reg[7:0]D,output reg v=0);assign W=w;assign H=h;reg[65:0]p=1;always@(posedge c) begin v<=(p<3*w*h); p<=p+v; D<=d+17; end endmodule

```

# Answer
> 1 votes
# Dyalog APL, ~~21~~ 15 bytes

> Programs may output as a matrix of RGB pixel values

I assume output may be in the same format.

### New solution takes matrix of values \[\[*r*,*g*,*b*,*r*,*g*,*b*\],\[*r*,*g*,*b*,…

```
16⊥16|1+16 16⊤⎕

```

**Explanation**

get numeric input
`16 16⊤` convert to 2-digit base 16
`1+` add 1, i.e. 0 → 1, 1 → 2, 15 → 16
`16|` modulus 16, i.e. 16 → 0
`16⊥` convert from base 16

**Example**

```
      ⊢m←2 6⍴90 239 96 255 255 255 0 0 0 239 239 239
90 239 96 255 255 255
 0   0  0 239 239 239
      16⊥16|1+⎕⊤⍨2/16
⎕:
      m
107 240 113   0   0   0
 17  17  17 240 240 240

```

---

### Old 21 byte solution takes matrix of \[\["RRGGBB","RRGGBB"\],\["RRGGBB",…

```
{n[16|1+⍵⍳⍨n←⎕D,⎕A]}¨

```

Needs `⎕IO←0`, which is default on many systems.

**Explanation**

`{` for each RGB 6-char string, represent it as  and do:
`n←⎕D,⎕A` assign "0…9A…Z" to *n*
`⍵⍳⍨` find indices of the individual characters in *n*
`1+` add one to the index, i.e. 0 → 1, 1 → 2, 15 → 16
`16|` modulus 16, i.e. 16 → 0
`n[``]` use that to index into *n*

**Example**

```
      f←{n[16|1+⍵⍳⍨n←⎕D,⎕A]}¨
      ⊢p←2 2⍴'5AEF60' 'FFFFFF' '000000' 'EFEFEF'
┌──────┬──────┐
│5AEF60│FFFFFF│
├──────┼──────┤
│000000│EFEFEF│
└──────┴──────┘
      f p
┌──────┬──────┐
│6BF071│000000│
├──────┼──────┤
│111111│F0F0F0│
└──────┴──────┘

```

# Answer
> 1 votes
# C - ~~114~~ ~~113~~ ~~70~~ ~~66~~ ~~61~~ ~~72~~ 67 bytes

Here's the code (with support for **Martin Ender**'s test case (without it's 60b)):

```
main(c,b){for(;~(b=getchar());putchar(c++<54?b:b+16&240|b+1&15));}

```

And here is less obfuscated version:

```
main( c, b ) //Defaults to int
{
    //Get characters until EOF occurs
    //Copy first 54 bytes of header, later add 1 to each hexadecimal digit
    for ( ; ~( b = getchar( ) ); putchar( c++ < 54 ? b: b + 16 & 240 | b + 1 & 15 ) );
}

```

Compile and run with `gcc -o color colorgolf.c && cat a.bmp | ./color > b.bmp`

This code supports works with **bitmaps**. To convert `png` files to `bmp`, I used following command: `convert -flatten -alpha off png.png a.bmp`

Code assumes, that `bmp` header is 54 bytes long - in this case it works, but I'm not sure if I'm not discreetly breaking something.

Also, this is the rainbow:

# Answer
> 1 votes
# Java 142 bytes

```
public BufferedImage translateColor(BufferedImage image){
  for(int i=-1;++i<image.getWidth();)
    for(int j=-1;++<image.getHeight();)
      image.setRGB(i,j,image.getRGB(i,j)+1118481);
  return image;
}

```

Golfed:

```
BufferedImage t(BufferedImage i){for(int x=-1;++x<i.getWidth();)for(int y=-1;++y<i.getHeight();)i.setRGB(x,y,i.getRGB(x,y)+1118481);return i;}

```

# Answer
> 0 votes
# R, 302 bytes

Far from perfect, but here goes:

```
a<-as.raster(imager::load.image(file.choose()));l=letters;n=as.numeric;d=a;f=function(x){if(suppressWarnings(is.na(n(x)))){if(x=="F")"0" else{l[match(x,toupper(l))+1]}}else{if(x==9)"A" else as.character(n(x)+1)}};for(o in 1:90){for(g in 1:200){for(h in 2:7){substr(d[o,g],h,h)<-f(substr(a[o,g],h,h))}}}

```

Explanation:

```
a<-as.raster(imager::load.image(file.choose()));  //chooses file
l=letters;n=as.numeric;d=a;                      //shortens some names and creates
                                                   duplicate variable to modify

f=function(x){                                //creates a function that takes in a
   if(suppressWarnings(is.na(n(x)))){            character type and checks whether it is
      if(x=="F")"0"                              a number or letter.
      else{l[match(x,toupper(l))+1]}}            Returns the converted letter or number.
   else{
      if(x==9)"A"
      else as.character(n(x)+1)}
};

for(o in 1:90){                       //loops through every single hex digit and applies
   for(g in 1:200){                     the converting function, modifying the duplicate
      for(h in 2:7){                    variable. Now you have 2 images =D

         substr(d[o,g],h,h)<-f(substr(a[o,g],h,h))

      }
   }
}

```

---
Tags: code-golf, image-processing, hexadecimal
---


# Question
Title: Determine the position of a non-negative number in the infinite spiral
# Definition

The infinite spiral used in this question has `0` on the position `(0,0)`, and continues like this:

```
16-15-14-13-12
 |           |
17  4--3--2 11
 |  |     |  |
18  5  0--1 10
 |  |        |
19  6--7--8--9
 |
20--21...

```

It is to be interpreted as a Cartesian plane.

For example, `1` is on the position `(1,0)`, and `2` is on the position `(1,1)`.

# Task

Given a non-negative integer, output its position in the spiral.

# Specs

* Your spiral can start with `1` instead of `0`. If it starts with `1`, please indicate so in your answer.
* Output the two numbers in any sensible format.

# Testcases

The testcases are 0-indexed but you can use 1-indexed as well.

```
input output
0     (0,0)
1     (1,0)
2     (1,1)
3     (0,1)
4     (-1,1)
5     (-1,0)
6     (-1,-1)
7     (0,-1)
8     (1,-1)
9     (2,-1)
100   (-5,5)

```

# Answer
> 9 votes
## Python, 46 bytes

```
f=lambda n:n and 1j**int((4*n-3)**.5-1)+f(n-1)

```

Dennis's answer suggested the idea of summing a list of complex numbers representing the unit steps. The question is how to find the number of quarter turns taken by step `i`.

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

```

These are generated by `int((4*k-n)**.5-1)`, and then converted to a direction unit vector via the complex exponent `1j**_`.

# Answer
> 6 votes
# Python, 53 bytes

```
lambda n:sum(1j**int((4*i+1)**.5-1)for i in range(n))

```

# Answer
> 3 votes
# Jelly, ~~22~~ ~~16~~ 10 bytes

```
Ḷ×4‘Æ½’ı*S

```

This uses the quarter-turn approach from @xnor's/@orlp's answer.

Indexing is 0-based, output is a complex number. Try it online! or verify all test cases.

### How it works

```
Ḷ×4‘Æ½’ı*S  Main link. Argument: n (integer)

Ḷ           Unlength; create the range [0, ..., n - 1].
 ×4         Multiply all integers in the range by 4.
   ‘        Increment the results.
    Æ½      Take the integer square root of each resulting integer.
      ’     Decrement the roots.
       ı*   Elevate the imaginary unit to the resulting powers.
         S  Add the results.

```

# Answer
> 2 votes
# Python 2, ~~72~~ 62 bytes

```
n=2;x=[]
exec'x+=n/2*[1j**n];n+=1;'*input()
print-sum(x[:n-2])

```

*Thanks to @xnor for suggesting and implementing the quarter-turn idea, which saved 10 bytes.*

Indexing is 0-based, output is a complex number. Test it on Ideone.

# Answer
> 2 votes
# Ruby, ~~57~~ 55 bytes

This is a simple implementation based on Dennis's Python answer. Thanks to Doorknob for his help in debugging this answer. Golfing suggestions welcome.

```
->t{(1...t).flat_map{|n|[1i**n]*(n/2)}[0,t].reduce(:+)}

```

**Ungolfed:**

```
def spiral(t)
  x = []
  (1...t).each do |n|
    x+=[1i**n]*(n/2)
  end
  return x[0,t].reduce(:t)
end

```

# Answer
> 2 votes
## JavaScript (ES7), 75 bytes

```
n=>[0,0].map(_=>((a+2>>2)-a%2*n)*(a--&2?1:-1),a=(n*4+1)**.5|0,n-=a*a>>2)

```

Who needs complex arithmetic? Note: returns `-0` instead of `0` in some cases.

# Answer
> 1 votes
## Batch, 135 bytes

```
@set/an=%1,x=y=f=l=d=0,e=-1
:l
@set/ac=-e,e=d,d=c,n-=l+=f^^=1,x+=d*l,y+=e*l
@if %n% gtr 0 goto l
@set/ax+=d*n,y+=e*n
@echo %x%,%y%

```

Explanation: Follows the spiral out from the centre. Each pass through the loop rotates the current direction `d,e` by 90° anticlockwise, then the length of the arm `l` is incremented on alternate passes via the flag `f` and the next corner is calculated in `x,y`, until we overshoot the total length `n`, at which point we backtrack and print the resulting co-ordinates.

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


title: Which finite abelian group is this?

text:
# Question
Title: Which finite abelian group is this?
## Description

Write a function `f(m, G)` that accepts as its arguments a mapping `m`, and a set/list of distinct, non-negative integers `G`.

`m` should map pairs of integers in `G` to new integers in `G`. (`G`, `m`) is guaranteed to form a finite abelian group, but any element of `G` may be the identity.

There is an important theorem that says:

> \[Each finite abelian group\] is isomorphic to a direct product of cyclic groups of prime power order.

`f` must return a list of prime powers `[p1, ... pn]` in ascending order such that

## Examples

* `f((a, b) → (a+b) mod 4, [0, 1, 2, 3])` should return `[4]`, as the parameters describe the group **Z4**.
* `f((a, b) → a xor b, [0, 1, 2, 3])` should return `[2, 2]`, as the parameters describe a group isomorphic to **Z2 × Z2**.
* `f((a, b) → a, [9])` should return `[]`, as the parameters describe the trivial group; i.e., the product of zero cyclic groups.
* Define `m` as follows:

```
(a, b) → (a mod 3 + b mod 3) mod 3
       + ((floor(a / 3) + floor(b / 3)) mod 3) * 3
       + ((floor(a / 9) + floor(b / 9)) mod 9) * 9

```

Then `f(m, [0, 1, ..., 80])` should return `[3, 3, 9]`, as this group is isomorphic to **Z3 × Z3 × Z9**

## Rules

* `m` may either be a function (or function pointer to some function) `Int × Int → Int`, or a dictionary mapping pairs in `G × G` to new elements of `G`.
* `f` may take its parameters in the opposite order, i.e. you may also implement `f(G, m)`.
* Your implementation should *theoretically* work for arbitrarily large inputs, but need not actually be efficient.
* There is no limitation on using built-ins of any kind.
* Standard rules apply. Shortest code in bytes wins.

## Leaderboard

For your score to appear on the board, it should be in this format:

```
# Language, Bytes

```

```
var QUESTION_ID=67252,OVERRIDE_USER=3852;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#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="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><div id="language-list"> <h2>Winners 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><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
> 5 votes
# Matlab, 326 bytes

With some group theory the idea is quite simple: Here the TL;DR Calculate all possible orders of elements of the group. Then find the biggest subgroup of a certain prime power order and "factorize" it out of the group, rinse, repeat.

```
function r=c(h,l)

                            %factorize group order
N=numel(L);
f=factor(N);
P=unique(f);                %prime factors
for k=1:numel(P);
    E(k)=sum(f==P(k));    %exponents of unique factors
end;

                            %calculate the order O of each element
O=L*0-1;
l=L;
for k=2:N+1;

    l=h(l,L);

    O(l==L & O<0)=k-1
end;

%%

O=unique(O);               % (optional, just for speedupt)
R=[];
                           % for each prime,find the highest power that
                           % divides any of the orders of the element, and
                           % each time substract that from the remaining
                           % exponent in the prime factorization of the
                           % group order
for p=1:nnz(P);                          % loop over primes
    while E(p)>1;                        % loop over remaining exponent
        for e=E(p):-1:1;                 % find the highest exponent
            B=mod(O,P(p)^e)==0;
            if any(B)
                R=[R,P(p)^e];            % if found, add to list
                O(B)=O(B)/(P(p)^e);
                E(p)=E(p)-e;
                break;
            end;
        end;
    end;
    if E(p)==1;
        R=[R,P(p)];
    end;
end;
r=sort(R)

```

Example inputs:

```
L = 0:3;
h=@(a,b)mod(a+b,4);
h=@(a,b)bitxor(a,b);
L = 0:80;
h=@(a,b)mod(mod(a,3)+mod(b,3),3)+mod(floor(a/3)+floor(b/3),3)*3+ mod(floor(a/9)+floor(b/9),9)*9;

```

Golfed version:

```
function r=c(h,l);N=numel(L);f=factor(N);P=unique(f);for k=1:numel(P);E(k)=sum(f==P(k));end;O=L*0-1;l=L;for k=2:N+1;l=h(l,L);O(l==L&O<0)=k-1;end;R=[];for p=1:nnz(P);while E(p)>1;for e=E(p):-1:1;B=mod(O,P(p)^e)==0; if any(B);R=[R,P(p)^e]; O(B)=O(B)/(P(p)^e);E(p)=E(p)-e;break;end;end;end;if E(p)==1;R=[R,P(p)];end;end;r=sort(R)

```

# Answer
> 1 votes
## GAP, ~~159~~ 111 bytes

GAP allows us to simply construct a group by a multiplication table and compute its abelian invariants:

```
ai:=    # the golfed version states the function w/o assigning it
function(m,G)
  local t;
  t:=List(G,a->List(G,b->Position(G,m(a,b))));
  # t is inlined in the golfed version
  return AbelianInvariants(GroupByMultiplicationTable(t));
end;

```

# The old version

The finitely presented group with generators G and relations a\*b=m(a,b) (for all a, b from G) is the group (G,m) we started with. We can create it and compute its abelian invariants with GAP:

```
ai:=    # the golfed version states the function w/o assigning it
function(m,G)
  local F,n,rels;
  n:=Size(G);
  F:=FreeGroup(n);
  rels:=Union(Set([1..n],i->
                Set([1..n],j->
                  F.(i)*F.(j)/F.(Position(G,m(G[i],G[j]))) ) ));
  # rels is inlined in the golfed version
  return AbelianInvariants(F/rels);
end;

```

# Examples

```
m1:=function(a,b) return (a+b) mod 4; end;
# I don't feel like implementing xor
m3:=function(a,b) return 9; end;
m4:=function(a,b)
  return (a+b) mod 3 # no need for inner mod
         + ((QuoInt(a,3)+QuoInt(b,3)) mod 3) * 3
         + ((QuoInt(a,9)+QuoInt(b,9)) mod 9) * 9;
  end;

```

Now we can do:

```
gap> ai(m1,[0..3]);
[ 4 ]

```

Actually, we are not restricted to using lists of integers. Using the correct domain, we can just use the general plus:

```
ai(\+,List(Integers mod 4));
[ 4 ]

```

So I can essentially do the second example using that its group is isomorphic to the additive group of the 2 dimensional vector space over the field with 2 elements:

```
gap> ai(\+,List(GF(2)^2));
[ 2, 2 ]

```

And the remaining examples:

```
gap> ai(m3,[9]);
[  ]
gap> ai(m4,[0..80]);
[ 3, 3, 9 ]

```

# Additional remarks

In the old version, m did not need to define a group composition for G. If m(a,b)=m(a,c), that just says that b=c. So we could do `ai(m1,[0..5])` and `ai(m3,[5..15])`. The new version will fail horrible in these cases, as will both versions if m returns values that are not in G.

If (G,m) is not abelian, we get a description of the abelianized version of it, that is its biggest abelian factor group:

```
gap> ai(\*,List(SymmetricGroup(4)));
[ 2 ]

```

This is what `AbelianInvariants` is usually used for, we would normally just call `AbelianInvariants(SymmetricGroup(4))`.

# The golfed version

```
function(m,G)return AbelianInvariants(GroupByMultiplicationTable(List(G,a->List(G,b->Position(G,m(a,b))))));end

```

---
Tags: code-golf, math, abstract-algebra
---


title: Number of cycles of a permutation

text:
# Question
Title: Number of cycles of a permutation
Consider a **permutation** of the integers `1`, ..., `n`, such as this one for `n = 6`:

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

```

If you view the permutation as a mapping from `[1,2,3,4,5,6]` to `[5,2,4,3,6,1]`, the permutation can be decomponsed into disjoint **cycles**. A cycle is a subset of elements that map to each other. For example, `1` gets mapped to `5`, which gets mapped to `6`, which gets mapped back to `1`. So one cycle is `[1,5,6]`. The other cycles are `[2]` and `[3,4]`. Thus the **number of cycles** for this permutation is `3`.

In general, the cycles of a permutation are unique (up to order), and the number of cycles for a permutation of size `n` varies from `1` to `n`.

# The challenge

Given a non-empty permutation, output its number of cycles.

Input is an array formed by the `n` integers `1`, `2`, ..., `n`, where `n > 0`. Each integer occurs exactly once. The order in which they appear defines the permutation, as in the example above.

Instead of an array you can use a list, a string with a separator between the numbers, a separate input for each number, or anything that's reasonable.

For a permutation of size `n`, instead of the 1-based set of integers `1`, ..., `n` you can consistently use the 0-based set `0`, ..., `n-1`. If so, please indicate it in your answer.

The code should work for `n` up to `20` in a reasonable time, say less than one minute.

Code golf. All builtins allowed.

# Test cases

This assumes 1-based, array input.

```
 [1] -> 1
 [3,2,1] -> 2
 [2,3,4,5,1] -> 1
 [5,2,4,3,6,1] -> 3
 [8,6,4,5,2,1,7,3] -> 2
 [4,5,11,12,7,1,3,9,10,6,8,2] -> 1
 [4,2,5,11,12,7,1,3,9,10,6,8] -> 5
 [5,8,6,18,16,9,14,10,11,12,4,20,15,19,2,17,1,13,7,3] -> 3
 [14,5,17,15,10,18,1,3,4,13,11,16,2,12,9,7,20,6,19,8] -> 7

```

# Related

This related challenge asks for the actual cycles of the permutation, not the number of them. Requiring only the number of cycles can lead to shorter algorithms that sidestep generating the actual cycles.

# Answer
# J, 4 bytes

```
#@C.

```

This assumes that the permutation is 0-based. It uses the builtin `C.` which given a list representing a direct permutation outputs a list of cycles. Then `#` composed `@` on that returns the number of cycles in that list.

Try it here.
> 12 votes

# Answer
# JavaScript, ~~99~~ 98 bytes

This solution assumes the array and its values are zero-indexed (e.g. `[2, 1, 0]`).

```
f=a=>{h={},i=c=0;while(i<a.length){s=i;while(!h[i]){h[i]=1;i=a[i]}c++;i=s;while(h[++i]);}return c}

```

**Explanation**

```
// assumes the array is valid and zero-indexed
var findCycles = (array) => {
    var hash = {};  // remembers visited nodes
    var index = 0;  // current node
    var count = 0;  // number of cycles
    var start;      // starting node of cycle

    // loop until all nodes visited
    while(index < array.length) {
        start = index;  // cache starting node

        // loop until found previously visited node
        while(!hash[index]) {
            hash[index] = 1;    // mark node as visited
            index = array[index];   // get next node
        }
        count++;    // increment number of cycles

        index = start + 1;  // assume next node is right after

        // loop until found unvisited node
        while(hash[index]) {
            index++;    // get next node
        }
    }

    return count;   // return number of cycles
};

```
> 7 votes

# Answer
# Python, 77 69 67 bytes

```
f=lambda p,i=1:i and0 **p[i-1]+f(p[:i-1]+[0]+p[i:],p[i-1]or max(p))

```
> 6 votes

# Answer
# Mathematica, 45 bytes

```
Length@ConnectedComponents@Thread[Sort@#->#]&

```

It generates a graph and counts its connected components.
> 6 votes

# Answer
# Mathematica, ~~37~~ ~~28~~ 27 bytes

```
#~PermutationCycles~Length&

```

Thanks @alephalpha for saving 9 bytes, and @miles for 1 more byte.
> 6 votes

# Answer
## Python, 64 bytes

```
l=input()
for _ in l:l=[min(x,l[x])for x in l]
print len(set(l))

```

This golfed code happens to be idiomatic and readable. Uses 0-indexing.

Each value looks at what it points to and what the pointed value points to, and points to the smaller of the two. After enough repetitions, each element points to the smallest element of its cycle. The number of distinct elements pointed to is then the number of cycles.

It suffices to do `n` iterations. Alternatively, we could iterate until the list no longer changes. This strategy gave me a recursive function of the same length, 64 bytes:

```
f=lambda l,p=0:len(set(l*(l==p)))or f([min(x,l[x])for x in l],l)

```

Reducing was 65 bytes

```
lambda l:len(set(reduce(lambda l,_:[min(x,l[x])for x in l],l,l)))

```

The `set(_)` conversions can be shortened to `{*_}` in Python 3.5, saving 2 bytes.
> 6 votes

# Answer
# Jelly, ~~12~~ ~~10~~ 9 bytes

```
ị³$ÐĿ«/QL

```

Saved 1 byte thanks to @Dennis.

This uses 1-based permutations. It works by applying the permutation repeatedly until it reaches a previous permutation while also keeping its previous values. By keeping track of the changes, it will create the orbit for every value along the columns of that table. Then, by finding either the minimum or maximum of each column, a label for that cycle can be created. Then deduplicate that list of labels and get the length of it which will be the number of disjoint cycles.

Try it here.

## Explanation

```
ị³$ÐĿ«/QL  Input: permutation p
  $        Chain (ị³) as a monad
 ³           The input p
ị            For each value x, get the value at index x in p
   ÐĿ      Invoke it on p initially, and repeat it on its next value until it returns
           to a previous value and keep track of the results
           This will create a table where each column is the orbit of each value
     «/    Get the minimum value along each column of that table
       Q   Deduplicate
        L  Get the length and return

```
> 5 votes

# Answer
## Haskell, 111 bytes

```
l!i|l!!i<0=l|1<2=(take i l++[-1]++drop(i+1)l)!(l!!i)
f(x:y)|x>=0=0|1<2=1+f y
c l|l==[-1|x<-l]=0|1<2=1+c(l!f l)

```

Uses 0-based indexing
> 4 votes

# Answer
# Pyth, 9 bytes

```
l{mS.u@QN

```

Uses 0-based indexes. Try it online.

### How it works

```
  m         map for d in input:
    .u        cumulative fixed-point: starting at N=d, repeatedly replace N with
      @QN       input[N]
              until a duplicate is found, and return all intermediate results
   S          sort
 {          deduplicate
l           length

```
> 4 votes

# Answer
## JavaScript (ES6), 49 bytes

```
a=>a.reduce(g=(c,e,i)=>e<i?g(c,a[e],i):c+=e==i,0)

```

Uses zero-based indexing. Explanation: `reduce` is used to invoke the inner function `g` on each element of the array. `c` is the count of cycles, `e` is the array element, `i` is the array index. If the element is less than the index, then it's a potential cycle - the element is used to index into the array to find the next element in the cycle recursively. If we started out or end up with the original index then this is a new cycle and we increment the cycle count. If at any point we find a value larger than the index then we'll count that cycle later.
> 3 votes

# Answer
# C, 90 bytes

Call `f()` with a mutable `int` array, 1 based indexing. The second parameter is the size of the array. The function returns the number of cycles.

```
i,j,c;f(a,n)int*a;{for(c=i=0;i<n;++i)for(j=0,c+=!!a[i];a[i];a[i]=0,i=j-1)j=a[i];return c;}

```

Try it on ideone.

The algorithm:

```
For each index
    If index is non-zero
        Increment counter
        Traverse the cycle, replacing each index in it with 0.

```
> 2 votes

# Answer
## GAP, 30 bytes

Straightforward, the second argument to `Cycles` gives the set on which the permutation should act:

```
l->Size(Cycles(PermList(l),l))

```
> 2 votes

---
Tags: code-golf, math, number, combinatorics, permutations
---


title: Polynomial Interpolation

text:
# Question
Title: Polynomial Interpolation
Write a program that performs *Polynomial Interpolation* using true arbitrary precision rational numbers. The input looks like this:

```
f(1) = 2/3
f(2) = 4/5
f(3) = 6/7
...

```

You may assume that there's exactly one whitespace before and after the `=` sign, all the numbers are either fractions or integers. You may also assume, that all fraction in the input are already irreducible.

No error checking is needed, you may assume, that the input is valid and no x is doubled in the f(x).

The output should be in a LaTeX compatible form, the emitted LaTeX code should yield the same graphical representation as the output given here.

```
f(x) = 123x^2 + \frac{45}{2}x + \frac{7}{4}

```

The fraction must be reduced as much as possible, eg. something like `\frac{2}{4}` is not allowed. If the number is integer, don't use a fraction.

## Special rules:

Your program should...

* work for polynomials up to degree 12
* complete in less then 1 minute for reasonable input
* not use any functions that do the whole calculation for you
* output the polynomial of smallest possible degree

## Testcases:

The given testcases are just for clarification. Your program should yield correct result for all correct inputs.

### Input

```
f(1) = 2/3
f(2) = 4/5
f(3) = 6/7

```

### Output

```
f(x) = - \frac{4}{105}x^2
       + \frac{26}{105}x
       + \frac{16}{35}

```

### Input

```
f(-12) = 13/2
f(5/3) = 3/5
f(13) = -6
f(1/5) = -3/4

```

### Output

```
f(x) = - \frac{2186133}{239455744}x^3
       + \frac{2741731}{149659840}x^2
       + \frac{26720517}{29201920}x
       - \frac{279464297}{299319680}

```

### Input

```
f(4/3) = 617/81
f(2) = 20/3
f(-8/3) = 6749/81
f(-5) = 7367/12
f(0) = 23/3

```

### Output

```
f(x) = \frac{1}{2}x^4
     - 2x^3
     + \frac{7}{4}x^2
     + \frac{23}{3}

```

### Input

```
f(0) = 5
f(1) = 7
f(2) = 9
f(3) = 11
f(4) = 13

```

### Output

```
f(x) = 2x
     + 5

```

### Input

```
f(1/2) = -1/2
f(-25) = -1/2
f(-54/12) = -1/2

```

### Output

```
f(x) = -\frac{1}{2}

```

# Answer
> 3 votes
## J + sh

**J script:**

```
i=:0".(1!:1)3
i=:((-:#i),2)$i
c=:|.(%.(x:((i.#i)^~])"0({."1 i)))(+/ .*)(|:{:"1 i)
(":(-.0=c)#(c,.i.-#c))(1!:2)2

```

**sh script:**

```
echo -n 'f(x) = '
tr -d 'f()=' | tr /\\n- r' '_  | ./polyint.ijs | sed -e 's/^/+/;s/_/-/;s/\([0-9]*\)r\([0-9]*\)/\\frac{\1}{\2}/;s/ \([0-9]*$\)/x^\1/;s/\^1//;s/x^0//;s/+\(.*-.*\)/\1/'

```

Run the sh script:

```
./pol-int.sh
f(1/2) = -1/2
f(-25) = -1/2
f(-54/12) = -1/2

f(x) = -\frac{1}{2}

```

.

```
./pol-int.sh
f(4/3) = 617/8
f(2) = 20/3
f(-8/3) = 6749/81
f(-5) = 7367/12
f(0) = 23/3

f(x) = -\frac{37745}{14592}x^4
       -\frac{853249}{43776}x^3
     +  \frac{57809}{7296}x^2
     + \frac{225205}{2736}x
     +  \frac{23}{3}

```

# Answer
> 3 votes
# Perl (569 characters)

```
use Math'BigInt;sub r{($u,$v)=@_;$v?r($v,$u%$v):$u}sub c{new Math'BigInt$_[0]}$a=@c=<>;for(@c){m!(-?\d+)/?(\d*). = (-?\d+)/?(\d*)!;$j{$_,$i}=$1**c$_,$k{$_,$i|=0}=($2||1)**c$_ for 0..$a;$j{$a,$i}=c$3;$k{$a,$i++}=c$4||1}for$p(0..$a-1){for$y(0..$p-1,$p+1..$a-1){$n=$j{$p,$y}*$k{$p,$p};$o=$k{$p,$y}*$j{$p,$p};$j{$_,$y}=$j{$_,$y}*$k{$_,$p}*$o-$k{$_,$y}*$j{$_,$p}*$n,$k{$_,$y}*=$k{$_,$p}*$o for 0..$a}}print"f(x)=";for(1..$a){$s=r$t=$j{$a,$p=$a-$_}*$k{$p,$p},$w=$k{$a,$p}*$j{$p,$p};$u=abs$t,print$t>0?"$z":'-',($z='+',$w/=$s)-1?"\\frac{$u}{$w}":$u,$p>1?"x^$p":x x$p if$t/=$s}

```

### Detailed explanation:

```
use Math'BigInt;

# Subroutine to calculate gcd of two numbers
sub r{($u,$v)=@_;$v?r($v,$u%$v):$u}

# Subroutine to create BigInts
sub c{new Math'BigInt$_[0]}

# Read input
# Throughout, $a is the number of equations.
$a=@c=<>;

# Initialises the $a+1 × $a matrix with all the values.
# $j{$x,$y} contains the numerator, $k{$x,$y} the denominator.
for(@c)
{
    m!(-?\d+)/?(\d*). = (-?\d+)/?(\d*)!;

    # Puzzle for the reader: why is $i|=0 in the second one,
    # not the first one? Answer at the bottom!
    $j{$_,$i}=$1**c$_,$k{$_,$i|=0}=($2||1)**c$_ for 0..$a;
    $j{$a,$i}=c$3;
    $k{$a,$i++}=c$4||1
}

# Generates the matrix echelon form.
# Basically, it works like this:
for$p(0..$a-1)
{
    # For each element along the diagonal {$p,$p}, set all the values above and
    # below it to 0 by adding a multiple of row $p to each of the other rows.
    for$y(0..$p-1,$p+1..$a-1)
    {
        # So we need to multiply the row $p by the value of {$p,$y}/{$p,$p}
        # (stored in $n/$o) and then subtract that from row $y.
        $n=$j{$p,$y}*$k{$p,$p};
        $o=$k{$p,$y}*$j{$p,$p};
            $j{$_,$y}=$j{$_,$y}*$k{$_,$p}*$o-$k{$_,$y}*$j{$_,$p}*$n,
            $k{$_,$y}*=$k{$_,$p}*$o
        for 0..$a
    }
}

# Outputs the result
print"f(x)=";
for(1..$a)
{
    # Note this sets $p = $a-$_. $p is the power of x.
    # We need to divide {$a,$p} by {$p,$p}. Store the result in $t/$w.
    # We also need to put the fraction in lowest terms, so calculate the gcd.
    $s=r$t=$j{$a,$p=$a-$_}*$k{$p,$p},$w=$k{$a,$p}*$j{$p,$p};

    # Output this term only if the numerator ($t) is non-zero.
    # Output a plus sign only if this isn’t the first term.
    # Output a fraction only if the denomator ($w) isn’t 1.
        $u=abs$t,print$t>0?"$z":'-',
        ($z='+',$w/=$s)-1?"\\frac{$u}{$w}":$u,$p>1?"x^$p":x x$p
    if$t/=$s
}

# Answer to the puzzle buried in the code above:
# It’s because the second part is passed as a second argument to c,
# hence it is evaluated before the first part.

```

### Comments

* I am sure there is a module for matrix manipulation that provides a function for echelon form. I specifically didn’t use that (didn’t even search for one) because I assume it is the point of this contest to do it yourself. It is more interesting that way, too. Of course the same could be said about BigInt, but then I suspect nobody will attempt this challenge...

### Edits

* **(630 → 585)** Realised I can do the echelon form in one loop instead of two. Add explanation as comments in code.
* **(585 → 583)** Just discovered the package syntax that lets me use `'` instead of `::`.
* **(583 → 573)** Some more microgolfing
* **(573 → 569)** Shorter regular expression to parse input

# Answer
> 2 votes
# Lagrange Method, Python, 199 236 202 bytes

A little late, but...

```
def lagrange(dp):
    l = lambda i: lambda x: (prod([(x - dp[j][0]) / (dp[i][0] - dp[j][0]) for j in range(len(dp)) if i != j]))
    return lambda x: sum([l(i)(x) * dp[i][1] for i in range(len(dp))])

```

Edit: To adhere to general rules, we have to remove references to non-builtin functions (at least without importing them). I have rewritten it to only use standard library modules and also included the imports (thanks to @TheFifthMarshal & @Tech-Freak), while deleting extraneous whitespace, bumping it up to 208 bytes. To elaborate, the input `d` takes the form of a 2D iterable (an `nx2` matrix), where each row is a measurement, the first column is \\$t\\$ and the second column is \\$x\\$. The output is an anonymous function which can take any floating point or integer number and give the approximate result.

```
from functools import*
mul=lambda a,b:a*b
def l(d):
 l=lambda i,x:reduce(mul,[(x-d[j][0])/(d[i][0]-d[j][0])for j in range(len(d))if i!=j],1)
 return lambda x:sum([l(i,x)*d[i][1]for i in range(len(d))])

```

### Usage Example:

```
>>> t = np.arange(0, 5, 0.5)
>>> t2 = np.arange(0, 5, 0.01)
>>> x = t**3
>>> dp = np.vstack((t, x)).T
>>> poly = l(dp)
>>> plt.plot(t2, np.vectorize(poly)(t2), label="output")
>>> plt.scatter(t, x, label="input")
>>> plt.legend()

```

---
Tags: code-golf, math, rational-numbers, restricted-time, polynomials
---