title: Naming non-cyclic carbon chains

text:
# Question
Title: Naming non-cyclic carbon chains
(I'm not a chemist! I might be wrong at some stuff, I'm writing what I've learned in high-school)

Carbon atoms have a special attribute: They can bind to 4 other atoms (which is not that special) and they stay stable even in long chains, which is very unique. Because they can be chained and combined in a lot of different ways, we need some kind of naming convention to name them.

This is the smallest molecule we can make:

```
CH4

```

It's called methane. It consists of only one carbon and 4 hydrogen atoms. The next one is:

```
CH3 - CH3

```

This is called ethane. It's made up of 2 carbon and 6 hydrogen atoms.

The next 2 are:

```
CH3 - CH2 - CH3
CH3 - CH2 - CH2 - CH3

```

They are propane and butane. The problems start with the chains with 4 carbon atoms, as it can be built in 2 different ways. One is shown above and the other is:

```
CH3 - CH - CH3
       |
      CH3

```

This is obviously not the same as the other. The number of atoms and the bindings are different. Of course just folding bindings and rotating the molecule won't make it a different one! So this:

```
CH3 - CH2 - CH2 - CH3

```

And this:

```
CH3 - CH2
       |
CH3 - CH2

```

Are the same (If you are into graph theory, you may say that if there is isomorphism between 2 molecules; they are the same). From now on I won't write out hydrogen atoms as they are not essential for this challenge.

As you hate organic chemistry and you have a lot of different carbon atoms to name, you decide to write a program that does this for you. You don't have too much space on your hard-drive tho, so the program must be as small as possible.

# The challenge

Write a program that takes in a multi-line text as input (a carbon chain) and outputs the name of the carbon chain. The input will only contain spaces, uppercase 'c' characters and '|' and '-' which represents a binding. The input chain will never contain cycles! Example:

Input:

```
C-C-C-C-C-C
  |   |
  C   C-C

```

Output:

> 4-ethyl-2-methylhexane

Any output is acceptable as long as it's human-readable and essentially the same (so you can use different separators for example if you wish).

**The naming convention:**

(See: IUPAC rules)

1. Identify the longest carbon chain. This chain is called the parent chain.
2. Identify all of the substituents (groups appending from the parent chain).
3. Number the carbons of the parent chain from the end that gives the substituents the lowest numbers. When comparing a series of numbers, the series that is the "lowest" is the one which contains the lowest number at the occasion of the first difference. If two or more side chains are in equivalent positions, assign the lowest number to the one which will come first in the name.
4. If the same substituent occurs more than once, the location of each point on which the substituent occurs is given. In addition, the number of times the substituent group occurs is indicated by a prefix (di, tri, tetra, etc.).
5. If there are two or more different substituents they are listed in alphabetical order using the base name (ignore the prefixes). The only prefix which is used when putting the substituents in alphabetical order is iso as in isopropyl or isobutyl. The prefixes sec- and tert- are not used in determining alphabetical order except when compared with each other.
6. If chains of equal length are competing for selection as the parent chain, then the choice goes in series to:

* the chain which has the greatest number of side chains.
    * the chain whose substituents have the lowest- numbers.
    * the chain having the greatest number of carbon atoms in the smallest side chain.
    * the chain having the least branched side chains (a graph having the least number of leaves).

For the parent chain, the naming is:

```
Number of carbons   Name
1                  methane
2                  ethane
3                  propane
4                  butane
5                  pentane
6                  hexane
7                  heptane
8                  octane
9                  nonane
10                 decane
11                 undecane
12                 dodecane

```

No chains will be longer than 12, so this will be enough. For the sub-chains it's the same but instead of 'ane' at the end we have 'yl'.

You can assume that the `C`s are in the odd columns and the bindings (`|` and `-` characters) are 1 long between carbon atoms.

# Test cases:

Input:

```
C-C-C-C

```

Output:

> butane

Input:

```
C-C-C
  |
  C

```

Output:

> 2-methylpropane

Input:

```
C-C-C-C
  |
  C
  |
  C-C

```

Output:

> 3-methylhexane

Input:

```
C-C-C-C-C
  |
  C
  |
  C

```

Output:

> 3-methylhexane

Input:

```
    C
    |
    C
    |
C-C-C-C
  |
  C-C-C
  |
  C-C

```

Output:

> 3,4-dimethyl-5-ethylheptane

Edit: Sorry for the wrong examples. I wasn't a good student :( . They should be fixed now.

# Answer
# Python 2, ~~1876~~ ~~1871~~ ~~1870~~ ~~1859~~ ~~1846~~ ~~1830~~ ~~1826~~ ~~1900~~ ~~1932~~ ~~1913~~ ~~1847~~ ~~1833~~ ~~1635~~ ~~1613~~ 1596 bytes

```
s=input().split('\n')
W=enumerate
J=len
Y=sorted
l=J(s[0])
s=''.join(s)
S=set
M=max
A=min
p=map
f=lambda k:[(x/l,x%l)for x,V in W(s)if V==k]
g=lambda x,i,h=lambda x,i,j:x[:i]+(x[i]+j,)+x[i+1:]:[(h(q,i,-1),h(q,i,1))for q in x]
v=f('C');e=g(f('-'),1)+g(f('|'),0)
E=[V for V in v if sum(e,()).count(V)==1]
o=lambda v:[E[~E.index(v)]for E in e if v in E]
T=lambda a:lambda b:z((a,b))
Z=lambda a:p(T(a[0]),a[1])
n=lambda R:'mepbphhondudetrueeeco nothotnxptn ddh p t t'[R-1::12].strip()+(R>9)*'ec'
G=lambda K:[H[i]for i,V in W(K)if V==A(K)]
q=lambda x:[`k[0]`for k in H if k[1]==x]
B='-'.join
def z(n,c=[]):k=[x for x in S(o(n[0]))-S(c)];p=[z((j,n[1]),c+k)for j in k];return 1-~-(n[0]==n[1])*(p and A(p)or J(v))
C=[(a,b)for a in E for b in E]
a=p(z,C)
s=[(k,[E for E in v if~-z((k[0],E))+z((k[1],E))==z((k[0],k[1]))])for k in[C[x]for x,V in W(a)if V==M(a)]]
H=[]
R=0
for k,_ in s:R=M(J(_),R);_.sort(key=T(k[0]));a=sum([list(S(o(k))-S(_))for k in _],[]);H+=zip(p(lambda a:Z((a,_)).index(2),a),p(Z,[(O,[x for x in S(v)-S(_)if z((x,O),_)<J(v)])for O in a])),
X=n(R)
U=any(H)
if U:H=G([[h[0]for h in Q]for Q in H if J(Q)==M(p(J,H))]);K=[[J(Q[1])for Q in j]for j in H];H=[H[i]for i,V in W(K)if A(V)==A(sum(K,[]))];K=[J([Q[1]for Q in j if J(S(Q[1]))-J(Q[1])])for j in H];H=[[p[0]+1,n(M(p[1]))+[['isopropyl','butyl-tert','butyl-sec','isobutyl'][J(p[1])+p[1].count(3)-3],'yl'][Y(p[1])==range(1,1+M(p[1]))]]for p in G(K)[0]]
print(U and B([','.join(q(x))+'-'+'dttphhondireeeecoe itnxptnc  rtataaa  aa a '[J(q(x))-2::9].strip()+B(x.split('-')[::-1])for x in Y(list(S(zip(*H)[1])))])+X or[X,'meth']['t'==X])+'ane'

```

Try it online!

Well there you go. Certainly not the golfiest but it works (I hope) :D

Took me about 10 hours, maybe? Probably my longest golf in both size and time, and that's saying something considering I used to use Java D:

Logic:

1. Convert from the ASCII representation to graph representation with each carbon atom as a node and each bond as an edge represented in adjacency form.
2. Find all leaves; that is, nodes with only one bond. The longest chain is guaranteed to be from one of these to another.
3. Find the dyadic product of the leaves; that is, all pairs of edge nodes. Then, take the length of all of these chains.
4. For each chain, find its subchains.
5. Do stuff to pick the right chain. If there are ties, then it doesn't really matter. Fun fact: There will always be a tie because each chain is counted twice, once in reverse.
6. Print it properly.

**EDIT**: Fixed bug where it used to cause errors if there were no side chains.

**EDIT**: Thanks to MD XF for noticing a few extra spaces (indentation for the for loop).

**EDIT**: I completely forgot about the prefix for having the same substituent.

**NOTE**: Each line needs to be the same width for this to work. That is, trailing spaces are required.

Fun fact: most cyclic hydrocarbons will be determined as "methane"

Fun fact: If you do `C-C-...-C-C` with 13 Cs, it will give `ethane`, then `thane` for 14, `ropane` for 15, etc.

-79 bytes thanks to Jonathan Frech
-119 bytes thanks to NieDzejkob
-17 bytes thanks to ovs
> 22 votes

---
Tags: code-golf, chemistry
---


title: Rooting for Trees With the Right Nodes

text:
# Question
Title: Rooting for Trees With the Right Nodes
# Background

A rooted tree is an acyclic graph such that there is exactly one path from one node, called the root, to each other node. A node `v` is called the *parent* of another node `u` if and only if the path from the root to `u` goes through `v` and there is an edge connecting `u` and `v`. If node `v` is the parent of node `u`, node `u` is a *child* of node `v`.

# Task

Write a program or function that, given a positive integer number of nodes and a set of non-negative integer numbers of children each parent has, outputs the number of possible rooted trees with that number of nodes (including the root) and each vertex having a number of children in the set, not counting those trees isomorphic to trees already found.

Two trees are isomorphic if one can be transformed into another by renaming the nodes, or in other words look the same when the nodes are unlabelled.

# Examples

We shall represent trees as a 0-indexed list of children per index where 0 represents the root, for example `[[1],[2],[]]` represents that the root `0` has `1` as a child, node `1` has node `2` as a child, and node `2` has no children.

Inputs `n=3` and set = `[0,1,2]`. This is equal to binary trees with three nodes. The two possible trees are: `[[1],[2],[]]` and `[[1,2],[],[]]`. Because they are identical in structure to the two trees, we count neither `[[2],[],[1]]` nor `[[2,1],[],[]]`. There are two trees, so the output is `2` or equivalent.

Here is a visualization:  You can see that the second set of two trees are identical in structure to the first set of two and are thus not counted. Both sets are composed of two trees which have one of the following two structures (the root is the node at the top):

---

Inputs `n=5` and set=`[0,2]`. The only possible tree is `[[1,2],[3,4],[],[],[]]`. Note that, for example, `[[1,2],[],[3,4],[],[]]` and `[[1,3],[],[],[2,4],[]]` are not counted again because they are isomorphic to the sole tree which is counted. The output is `1` or equivalent.

Here is another visualization:

Clearly, all of the trees are isomorphic, so only one is counted. Here is what the trees look like unlabeled:

---

Input `n=4`, set=`[0,2]`. There are no possible trees because each time children are generated from a node, there are either `0` or `2` more nodes. Clearly, 4 nodes cannot be produced by adding `2` or `0` successively to `1` node, the root. Output: `0` or falsey.

# Input/Output

Input and output should be taken in a reasonable format.

Input is a positive integer representing `n` and a list of non-negative integers representing the set of valid numbers of children.

The output is a non-negative integer corresponding to how many trees can be formed.

# Test cases

```
n ; set ; output
3 ; [0,1,2] ; 2
5 ; [0,2] ; 1
4 ; [0,2] ; 0
3 ; [0,1] ; 1
3 ; [0] ; 0
1 ; [0] ; 1
6 ; [0,2,3] ; 2
7 ; [0,2,3] ; 3

```

# Rules

* The set of numbers of children will always include zero.
* The root node always counts as a node, even if it has no children (see the `1; [0]` test case)
* This is , so shortest code wins.

# Answer
> 3 votes
# Haskell, 120 bytes

```
_#0=1
i#j=div(i#(j-1)*(i+j-1))j
s!n|let(0?1)0=1;(0?_)_=0;(m?n)c=sum[s!m#j*((m-1)?(n-j*m)$c-j)|j<-[0..c]]=sum$(n-1)?n<$>s

```

Try it online!

### How it works

`i#j` is `i` multichoose `j`.

`(m?n)c` is the number of `n`-node trees with `c` children at the root, each of which has a subtree of at most `m` nodes. It’s computed by summation over `j`, the number of these subtrees that have exactly `m` nodes.

`s!n` is the number of `n`-node trees. It’s computed by summation over `c``s`, the number of children at the root.

# Answer
> 1 votes
# Pyth, 47 bytes

```
.N?Nsm*/.P+tyNdd.!d:tN-T*dN-YdhY!|tTYLs:LtbbQyE

```

Try it online

A port of my Haskell answer, but it’s much faster in Pyth thanks to Pyth’s free automatic memoization. I had to work around a bug in Pyth’s binomial coefficient builtin, though.

# Answer
> 0 votes
# Python, 127 bytes

```
lambda*x:len(g(*x))
g=lambda n,s,d=0:[[]][n-1:d in s]or[[t]+u for c in range(1,n)for t in g(c,s)for u in g(n-c,s,d+1)if[t]+u>u]

```

Try it online!

The function `g` enumerates trees, and the main function counts them.

Each tree is recursively generated by splitting the requiring number of nodes `n` between `c` nodes in the first branch `t`, and `n-c` nodes in the remaining tree `u`. For a canonical form up to isomorphism, we require the branches to be sorted in decreasing order, so `t` must be at most the first element of `u` is `u` is non-empty. This is enforced as `[t]+u>u`.

We count the number of children `d` so far of the current node. When only one node `n=1` is left, is must be the current node and there's no more node for children. If the current number of children `d` is valid, this level can be finished successfully, so we output a singleton of the one-node tree. Otherwise, we've failed and output the empty list.

---
Tags: code-golf, combinatorics, graph-theory, tree-traversal
---


# Question
Title: List of first n prime numbers most efficiently and in shortest code
Rules are simple:

* **First n primes** (not primes below **n**), should be printed to standard output separated by newlines (primes should be generated within the code)
* primes **cannot be generated by an inbuilt function or through a library**, i.e. use of a inbuilt or library function such as, prime = get\_nth\_prime(n), is\_a\_prime(number), or factorlist = list\_all\_factors(number) won't be very creative.
* Scoring - Say, we define **Score** = *f*(\[number of chars in the code\]), **O**(*f*(n)) being the complexity of your algorithm where n is the number of primes it finds. So for example, if you have a 300 char code with **O**(n^2) complexity, score is 300^2 = **90000**, for 300 chars with **O**(n\*ln(n)), score becomes 300\*5.7 = **1711.13** (let's assume all logs to be natural logs for simplicity)
* Use any existing programming language, lowest score wins

**Edit:** Problem has been changed from finding 'first 1000000 primes' to 'first n primes' because of a confusion about what 'n' in O(f(n)) is, **n** is the number of primes you find (finding primes is the problem here and so complexity of the problem depends on the number of primes found)

**Note:** to clarify some confusions on complexity, if 'n' is the number of primes you find and 'N' is the nth prime found, complexity in terms of n is and N are not equivalent i.e. **O(f(n)) != O(f(N))** as , f(N) != constant * f(n) and N != constant * n, because we know that nth prime function is not linear, I though since we were finding 'n' primes complexity should be easily expressible in terms of 'n'.

As pointed out by Kibbee, you can visit this site to verify your solutions (here, is the old google docs list)

Please Include these in your solution -

* what complexity your program has (include basic analysis if not trivial)
* character length of code
* the final calculated score

This is my first CodeGolf Question so, if there is a mistake or loophole in above rules please do point them out.

# Answer
## Python (129 chars, O(n\*log log n), score of 203.948)

I'd say the Sieve of Eratosthenes is the way to go. Very simple and relatively fast.

```
N=15485864
a=[1]*N
x=xrange
for i in x(2,3936):
 if a[i]:
  for j in x(i*i,N,i):a[j]=0
print [i for i in x(len(a))if a[i]==1][2:]

```

Improved code from before.

## Python (~~191 156~~ 152 chars, O(n\*log log n)(?), score of 252.620(?))

I cannot at all calculate complexity, this is the best approximation I can give.

```
from math import log as l
n=input()
N=n*int(l(n)+l(l(n)))
a=range(2,N)
for i in range(int(n**.5)+1):
 a=filter(lambda x:x%a[i] or x==a[i],a)
print a[:n]

```

`n*int(l(n)+l(l(n)))` is the top boundary of the `n`th prime number.
> 15 votes

# Answer
## Haskell, n^1.1 empirical growth rate, 89 chars, score 139 (?)

The following works at GHCi prompt when the general library that it uses have been previously loaded. Print *n*-th prime, 1-based:

`let s=3:minus[5,7..](unionAll[[p*p,p*p+2*p..]|p<-s])in getLine>>=(print.((0:2:s)!!).read)`

This is unbounded sieve of Eratosthenes, using a general-use library for ordered lists. Empirical complexity between 100,000 and 200,000 primes `O(n^1.1)`. Fits to `O(n*log(n)*log(log n))`.

## About complexity estimation

I measured run time for 100k and 200k primes, then calculated `logBase 2 (t2/t1)`, which produced `n^1.09`. Defining `g n = n*log n*log(log n)`, calculating `logBase 2 (g 200000 / g 100000)` gives `n^1.12`.

Then, `89**1.1 = 139`, although `g(89) = 600`. --- **(?)**

It seems that for scoring the estimated growth rate should be used instead of complexity function itself. For example, `g2 n = n*((log n)**2)*log(log n)` is much better than `n**1.5`, but for 100 chars the two produce score of `3239` and `1000`, respectively. This can't be right. Estimation on 200k/100k range gives `logBase 2 (g2 200000 / g2 100000) = 1.2` and thus score of `100**1.2 = 251`.

Also, I don't attempt to print out all primes, just the *n*-th prime instead.

## No imports, 240 chars. n^1.15 empirical growth rate, score 546.

```
main=getLine>>=(print.s.read)
s n=let s=3:g 5(a[[p*p,p*p+2*p..]|p<-s])in(0:2:s)!!n
a((x:s):t)=x:u s(a$p t)
p((x:s):r:t)=(x:u s r):p t
g k s@(x:t)|k<x=k:g(k+2)s|True=g(k+2)t
u a@(x:r)b@(y:t)=case(compare x y)of LT->x:u r b;EQ->x:u r t;GT->y:u a t

```
> 8 votes

# Answer
This is so easy even my text editor can do this!

# Vim: 143 keystrokes (115 actions): O(n^2\*log(n)): Score: 101485.21

## Submission:

```
qpqqdqA^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"ddmpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qqpmp"aywgg@dqgg@p

```

Input: N should be on the first line of a blank document. After this is finished, each prime from 2 to N will be a separate line.

## Running the Commands:

First, note that any commands with a caret in front of them mean you need to hold Ctrl and type the next letter (e.g. ^V is `Ctrl-v` and ^R is `Ctrl-r`).

This will overwrite anything in your @a, @b, @d, and @p registers.

Because this uses `q` commands, it can't just be placed in a macro. However, here are some tips for running it.

* `qpqqdq` just clears registers
* `A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"dd` will create a list of numbers 2 to N+1. This is a break between the two main parts, so once this is done, you shouldn't need to do it again
* `mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0qqpmp"aywgg@dqgg@p` does need to be typed in one go. Try to avoid backspace as it may screw something up.
    + If you make a mistake, type `qdqqpq` then try this line again.

For large N, this is *very* slow. It took around 27 minutes to run N=5000; consider yourself warned.

## Algorithm:

This uses a basic recursive algorithm for finding primes. Given a list of all primes between 1 and A, A+1 is prime if it not divisible by any of the numbers in the list of primes. Start at A = 2 and add primes to the list as they are found. After N recursions, the list will contain all the primes up to N.

## Complexity

This algorithm has a complexity of O(nN), where N is the input number and n is the number of primes up to N. Each recursion tests n numbers, and N recursions are performed, giving O(nN).

However, N ~ n\*log(n), giving the final complexity as O(n2\*log(n))(https://en.wikipedia.org/wiki/Prime\_number\_theorem#Approximations\_for\_the\_nth\_prime\_number)

## Explanation

It's not easy to discern the program flow from the vim commands, so I rewrote it in Python following the same flow. Like the Vim code, the python code will error out when it reaches the end. Python doesn't like too much recursion; if you try this code with N \> 150 or so, it will reach the max recursion depth

```
N = 20
primes = range(2, N+1)

# Python needs these defined.
mark_p = b = a = -1

# Check new number for factors.
# This macro could be wrapped up in @d, but it saves space to leave it separate.
def p():
    global mark_d, mark_p, primes, a
    mark_d = 0
    print(primes)
    a = primes[mark_p]
    d()

# Checks factor and determine what to do next
def d():
    global mark_d, mark_p, a, b, primes
    b = primes[mark_d]
    if(a == b): # Number is prime, check the next number
        mark_p += 1
        p()
    else:
        if(a%b == 0): # Number is not prime, delete it and check next number
            del(primes[mark_p])
            p()
        else: # Number might be prime, try next possible factor
            mark_d += 1
            d()

mark_p = 0 #Start at first number
p()

```

Now, to break down the actual keystrokes!

* `qpqqdq` Clears out the @d and @p registers. This will ensure nothing runs when setting up these recursive macros.
* `A^V^Ayyp<Esc>3h"aC@a<Esc>0C1<Esc>@"dd` Turns the input into a list of numbers from 2 to N+1. The N+1 entry is deleted as a side effect of setting up the @d macro.

+ Specifically, writes a macro that increments a number, then copies it on the next line, then it writes a 1 and executes this macro N times.
* `mpqdmd"bywo^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>0*w*wyiWdd@0q` writes the @d macro, which implements the d() function above. "If" statements are interesting to implement in Vim. By using the search operator \*, it's possible to choose a certain path to follow. Breaking the command down further we get

+ `mpqd` Set the p mark here and start recording the @d macro. The p mark needs to be set so there is a known point to jump to as this runs
    + `o^Ra ^Rb 0 0 `pj@p ^Ra 0 ^R=@a%@b<Enter> `pdd@p 0 `dj@d<Esc>` Writes the if/else statement text
    + `0*w*wyiWdd@0` actually executes the if statement.
    + Before executing this command, the line will contain `@a @b 0 0 `pj@p @a 0 (@a%@b) `pdd@p 0 `dj@d`
    + `0` moves the cursor to the beginning of the line
    + `*w*w` Moves the cursor to the code to execute next

    1. if @a == @b, that is ``pj@p`, which moves to the next number for @a and runs @p on it.
        2. if @a != @b and @a%@b == 0, that is ``pdd@p`, which deletes the current number @a, then runs @p on the next one.
        3. if @a != @b and @a%%b != 0, that is ``dj@d`, which checks the next number for @b to see if it is a factor of @a
    + `yiWdd@0` yanks the command into the 0 register, deletes the line and runs the command
    + `q` ends the recording of the @d macro
* When this is first run, the ``pdd@p` command is run, deleting the N+1 line.
* `qpmp"aywgg@dq` writes the @p macro, which saves the number under the cursor, then goes to the first entry and runs @d on that.
* `gg@p` actually executes @p so that it will iterate over the whole file.
> 7 votes

# Answer
## Haskell, ~~72~~ 89 chars, O(n^2), Score 7921

Highest score per char count wins right? Modified for first N. Also I apparently can't use a calculator, so my score is not as abysmally bad as I thought. (using the complexity for basic trial division as found in the source below).

As per **Will Ness** the below is not a full Haskell program (it actually relies on the REPL). The following is a more complete program with a pseudo-sieve (the imports actually save a char, but I dislike imports in code golf).

```
main=getLine>>= \x->print.take(read x).(let s(x:y)=x:s(filter((>0).(`mod`x))y)in s)$[2..]

```

This version is undoubtedly (n^2). The algorithm is just a golf version of the naive \`\`sieve'', as seen here Old ghci 1 liner

```
getLine>>= \x->print.take(read x)$Data.List.nubBy(\x y->x`mod`y==0)[2..]

```

Leaving up the old, cheating answer because the library it links to is pretty nice.

```
print$take(10^6)Data.Numbers.Primes.primes

```

See here for an implementation and the links for the time complexity. Unfortunately wheels have a log(n) lookup time, slowing us down by a factor.
> 6 votes

# Answer
## C#, 447 Characters, Bytes 452, Score ?

```
using System;namespace PrimeNumbers{class C{static void GN(ulong n){ulong primes=0;for (ulong i=0;i<(n*3);i++){if(IP(i)==true){primes++;if(primes==n){Console.WriteLine(i);}}}}static bool IP(ulong n){if(n<=3){return n>1;}else if (n%2==0||n%3==0){return false;}for(ulong i=5;i*i<=n;i+=6){if(n%i==0||n%(i+2)==0){return false;}}return true;}static void Main(string[] args){ulong n=Convert.ToUInt64(Console.ReadLine());for(ulong i=0;i<n;i++){GN(i);}}}}

```

## scriptcs Variant, 381 Characters, 385 Bytes, Score ?

```
using System;static void GetN(ulong n){ulong primes=0;for (ulong i=0;i<(n*500);i++){if(IsPrime(i)==true){primes++;if(primes==n){Console.WriteLine(i);}}}}public static bool IsPrime(ulong n){if(n<=3){return n>1;}else if (n%2==0||n%3==0){return false;}for(ulong i=5;i*i<=n;i+=6){if(n%i==0||n%(i+2)==0){return false;}}return true;}ulong n=Convert.ToUInt64(Console.ReadLine());for(ulong i=0;i<n;i++){GetN(i);}

```

If you install scriptcs then you can run it.

*P.S. I wrote this in Vim* `:D`
> 5 votes

# Answer
### Scala 263 characters

Updated to fit to the new requirements. 25% of the code deal with finding a reasonable upper bound to calculate primes below.

```
object P extends App{
def c(M:Int)={
val p=collection.mutable.BitSet(M+1)
p(2)=true
(3 to M+1 by 2).map(p(_)=true)
for(i<-p){
var j=2*i;
while(j<M){
if(p(j))p(j)=false
j+=i}
}
p
}
val i=args(0).toInt
println(c(((math.log(i)*i*1.3)toInt)).take(i).mkString("\n"))
}

```

I got a sieve too.

Here is an empirical test of the calculation costs, ungolfed for analysis:

```
object PrimesTo extends App{
    var cnt=0
    def c(M:Int)={
        val p=(false::false::true::List.range(3,M+1).map(_%2!=0)).toArray
        for (i <- List.range (3, M, 2)
            if (p (i))) {
                var j=2*i;
                while (j < M) {
                    cnt+=1
                    if (p (j))
                        p(j)=false
                    j+=i}
            }
        (1 to M).filter (x => p (x))
    }
    val i = args(0).toInt
    /*
        To get the number x with i primes below, it is nearly ln(x)*x. For small numbers
        we need a correction factor 1.13, and to avoid a bigger factor for very small
        numbers we add 666 as an upper bound.
    */
    val x = (math.log(i)*i*1.13).toInt+666
    println (c(x).take (i).mkString("\n"))
    System.err.println (x + "\tcount: " + cnt)
}
for n in {1..5} ; do i=$((10**$n)); scala -J-Xmx768M P $i ; done

```

leads to following counts:

```
List (960, 1766, 15127, 217099, 2988966)

```

I'm not sure how to calculate the score. Is it worth to write 5 more characters?

```
scala> List(4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534).map(x=>(math.log(x)*x*1.13).toInt+666)
res42: List[Int] = List(672, 756, 1638, 10545, 100045, 1000419, 10068909, 101346800, 1019549994)

scala> List(4, 25, 168, 1229, 9592, 78498, 664579, 5761455, 50847534).map(x=>(math.log(x)*x*1.3)toInt)
res43: List[Int] = List(7, 104, 1119, 11365, 114329, 1150158, 11582935, 116592898, 1172932855)

```

For bigger n it reduces the calculations by about 16% in that range, but afaik for the score formula, we don't consider constant factors?

### new Big-O considerations:

To find 1 000, 10 000, 100 000 primes and so on, I use a formula about the density of primes x=\>(math.log(x)\*x\*1.3 which determines the outer loop I'm running.

So for values i in 1 to 6=\> NPrimes (10^i) runs 9399, 133768 ... times the outer loop.

I found this O-function iteratively with help from the comment of Peter Taylor, who suggested a much higher value for exponentiation, instead of 1.01 he suggested 1.5:

```
def O(n:Int) = (math.pow((n * math.log (n)), 1.01)).toLong

```

O: (n: Int)Long

```
val ns = List(10, 100, 1000, 10000, 100000, 1000*1000).map(x=>(math.log(x)*x*1.3)toInt).map(O)

```

ns: List\[Long\] = List(102, 4152, 91532, 1612894, 25192460, 364664351)

```
 That's the list of upper values, to find primes below (since my algorithm has to know this value before it has to estimate it), send through the O-function, to find similar quotients for moving from 100 to 1000 to 10000 primes and so on:

(ns.head /: ns.tail)((a, b) => {println (b*1.0/a); b})
40.705882352941174
22.045279383429673
17.62109426211598
15.619414543051187
14.47513863274964
13.73425213148954

```

This are the quotients, if I use 1.01 as exponent. Here is what the counter finds empirically:

```
ns: Array[Int] = Array(1628, 2929, 23583, 321898, 4291625, 54289190, 660847317)

(ns.head /: ns.tail)((a, b) => {println (b*1.0/a); b})
1.799140049140049
8.051553431205189
13.649578085909342
13.332251210010625
12.65003116535112
12.172723833234572

```

The first two values are outliers, because I have make a constant correction for my estimation formular for small values (up to 1000).

With Peter Taylors suggestion of 1.5 it would look like:

```
245.2396265560166
98.8566987153728
70.8831374743478
59.26104390040363
52.92941829568069
48.956394784317816

```

Now with my value I get to:

```
O(263)
res85: Long = 1576

```

But I'm unsure, how close I can come with my O-function to the observed values.
> 4 votes

# Answer
## GolfScript (45 chars, score claimed ~7708)

```
~[]2{..3${1$\%!}?={.@\+\}{;}if)1$,3$<}do;\;n*

```

This does simple trial division by primes. If near the cutting edge of Ruby (i.e. using 1.9.3.0) the arithmetic uses Toom-Cook 3 multiplication, so a trial division is O(n^1.465) and the overall cost of the divisions is `O((n ln n)^1.5 ln (n ln n)^0.465) = O(n^1.5 (ln n)^1.965)`†. However, in GolfScript adding an element to an array requires copying the array. I've optimised this to copy the list of primes only when it finds a new prime, so only `n` times in total. Each copy operation is `O(n)` items of size `O(ln(n ln n)) = O(ln n)`†, giving `O(n^2 ln n)`.

And this, boys and girls, is why GolfScript is used for golfing rather than for serious programming.

`O(ln (n ln n)) = O(ln n + ln ln n) = O(ln n)`. I should have spotted this before commenting on various posts...
> 4 votes

# Answer
**QBASIC, 98 Chars, Complexity N Sqrt(N), Score 970**

```
I=1
A:I=I+2
FOR J=2 TO I^.5
    IF I MOD J=0 THEN GOTO A
NEXT
?I
K=K+1
IF K=1e6 THEN GOTO B
GOTO A
B:

```
> 3 votes

# Answer
**Ruby 66 chars, O(n^2) Score - 4356**

`lazy` is available since Ruby 2.0, and `1.0/0` is a cool trick to get an infinite range:

```
(2..(1.0/0)).lazy.select{|i|!(2...i).any?{|j|i%j==0}}.take(n).to_a

```
> 3 votes

# Answer
# Ruby, 84 chars, 84 bytes, score?

This one is probably a little too novice for these parts, but I had a fun time doing it. It simply loops until `f` (primes found) is equal to `n`, the desired number of primes to be found.

The fun part is that for each loop it creates an array from 2 to one less than the number being inspected. Then it maps each element in the array to be the modulus of the original number and the element, and checks to see if any of the results are zero.

Also, I have no idea how to score it.

## Update

Code compacted and included a (totally arbitrary) value for `n`

```
n,f,i=5**5,0,2
until f==n;f+=1;p i if !(2...i).to_a.map{|j|i%j}.include?(0);i+=1;end

```

## Original

```
f, i = 0, 2
until f == n
  (f += 1; p i) if !(2...i).to_a.map{|j| i % j}.include?(0)
  i += 1
end

```

The `i += 1` bit and `until` loop are sort of jumping out at me as areas for improvement, but on this track I'm sort of stuck. Anyway, it was fun to think about.
> 2 votes

# Answer
## Perl - 94 characters, O(n log(n)) - Score: 427

```
perl -wle '$n=1;$t=1;while($n<$ARGV[0]){$t++;if((1x$t)!~/^1?$|^(11+?)\1+$/){print $t;$n++;}}'

```

## Python - 113 characters

```
import re
z = int(input())
n=1
t=1
while n<z:
    t+=1
    if not re.match(r'^1?$|^(11+?)\1+$',"1"*t):
        print t
        n+=1

```
> 2 votes

# Answer
## Scala, 124 characters

```
object Q extends App{Stream.from(2).filter(p=>(2 to p)takeWhile(i=>i*i<=p)forall{p%_!= 0})take(args(0)toInt)foreach println}

```

Simple trial division up to square root. Complexity therefore should be O(n^(1.5+epsilon))

124^1.5 \< 1381, so that would be my score i guess?
> 2 votes

# Answer
# AWK, ~~96~~ 86 bytes

*Subtitle: Look Mom! Only adding and some bookkeeping!*

File `fsoe3.awk`:

```
{for(n=2;l<$1;){if(n in L)p=L[n]
else{print p=n;l++}
for(N=p+n++;N in L;)N+=p
L[N]=p}}

```

Run:

```
$ awk -f fsoe3.awk <<< 5
2
3
5
7
11
$ awk -f fsoe3.awk <<< 1000 | wc -l
1000

```

---

# BASH, 133 bytes

File `x.bash`:

```
a=2
while((l<$1));do if((b[a]))
then((c=b[a]));else((c=a,l++));echo $a;fi;((d=a+c))
while((b[d]));do((d+=c));done
((b[d]=c,a++));done

```

Run:

```
$ bash x.bash 5
2
3
5
7
11
$ bash x.bash 1000 | wc -l
1000

```

---

Primes get calculated by letting the already found primes jump on the "tape of positive integers". Basically it is a serialised Sieve Of Eratosthenes.

```
from time import time as t

L = {}
n = 2
l = 0

t0=t()

while l<1000000:

        if n in L:
                P = L[n]
        else:
                P = n
                l += 1
                print t()-t0

        m = n+P
        while m in L:
                m += P
        L[m] = P

        n += 1

```

...is the same algorithm in Python and prints out the time when the `l`-th prime was found instead of the prime itself.

The output plotted with `gnuplot` yields the following:

The jumps probably have something to do with file i/o delays due to writing buffered data to disk...

Using much larger numbers of primes to find, will bring additional system dependent delays into the game, e.g. the array representing the "tape of positive integers" grows continuously and sooner or later will make every computer cry for more RAM (or later swap).

...so getting an idea of the complexity by looking at the experimental data does not really help a lot... :-(

---

Now counting the additions needed to find `n` primes:

```
cells = {}
current = 2
found = 0

additons = 0

while found < 10000000:

        if current in cells:
                candidate = cells[current]
                del cells[current] # the seen part is irrelevant
        else:
                candidate = current
                found += 1 ; additons += 1
                print additons

        destination = current + candidate ; additons += 1
        while destination in cells:
                destination += candidate ; additons += 1
        cells[destination] = candidate

        current += 1 ; additons += 1

```
> 1 votes

# Answer
**awk 45 (complexity N^2)**

another `awk`, for primes up to 100 use like this

```
awk '{for(i=2;i<=sqrt(NR);i++) if(!(NR%i)) next} NR>1' <(seq 100)

```

code golf counted part is

```
{for(i=2;i<=sqrt(NR);i++)if(!(NR%i))next}NR>1

```

which can be put in a script file and run as `awk -f prime.awk <(seq 100)`
> 1 votes

# Answer
## Scala 121 (99 without the Main class boilerplate)

```
object Q extends App{Stream.from(2).filter{a=>Range(2,a).filter(a%_==0).isEmpty}.take(readLine().toInt).foreach(println)}

```
> 0 votes

# Answer
# Python 3, ~~117~~ 106 bytes

This solution is slightly trivial, as it outputs 0 where a number is not prime, but I'll post it anyway:

```
r=range
for i in[2]+[i*(not 0 in[i%j for j in r(3,int(i**0.5)+1,2)])for i in r(3,int(input()),2)]:print(i)

```

Also, I'm not sure how to work out the complexity of an algorithm. Please don't downvote because of this. Instead, be nice and comment how I could work it out. Also, tell me how I could shorten this.
> 0 votes

# Answer
# Haskell (52²=2704)

```
52`take`Data.List.nubBy(((1<).).gcd)[2..]`forM_`print

```
> 0 votes

# Answer
## Perl 6, 152 bytes, O(n log n log (n log n) log (log (n log n))) (?), 9594.79 points

According to this page, the bit complexity of finding all primes up to n is O(n log n log log n); the complexity above uses the fact that the nth prime is proportional to n log n.

```
my \N=+slurp;my \P=N*(N.log+N.log.log);my @a=1 xx P;for 2..P.sqrt ->$i {if @a[$i] {@a[$_*$i]=0 for $i..P/$i}};say $_[1] for (@a Z ^P).grep(*[0])[2..N+1]

```
> 0 votes

# Answer
# Groovy (50 Bytes) - O(n\*sqrt(n)) - Score 353.553390593

```
{[1,2]+(1..it).findAll{x->(2..x**0.5).every{x%it}}}

```

Takes in n and outputs all numbers from 1 to n which are prime.

The algorithm I chose only outputs primes n \> 2, so adding 1,2 at the beginning is required.

## Breakdown

`x%it` \- Implicit truthy if it is not divisible, falsy if it is.

`(2..x**0.5).every{...}` \- For all the values between 2 and sqrt(x) ensure that they are not divisible, for this to return true, must return true for *every*.

`(1..it).findAll{x->...}` \- For all values between 1 and n, find all that fit the criteria of being non-divisible between 2 and sqrt(n).

`{[1,2]+...}` \- Add 1 and 2, because they are always prime and never covered by algorithm.
> 0 votes

# Answer
## Racket 155 bytes

```
(let p((o'(2))(c 3))(cond[(>=(length o)n)(reverse o)][(ormap(λ(x)(= 0(modulo c x)))
(filter(λ(x)(<= x(sqrt c)))o))(p o(add1 c))][(p(cons c o)(add1 c))]))

```

It keeps a list of prime numbers found and checks divisibility of each next number by primes already found. Moreover, it checks only upto the square root of number being tested since that is enough.

Ungolfed:

```
(define(nprimes n)
  (let loop ((outl '(2))                   ; outlist having primes being created
             (current 3))                  ; current number being tested
  (cond
    [(>= (length outl) n) (reverse outl)]  ; if n primes found, print outlist.
    [(ormap (λ(x) (= 0 (modulo current x))) ; test if divisible by any previously found prime
            (filter                         ; filter outlist till sqrt of current number
             (λ(x) (<= x (sqrt current)))
             outl))
     (loop outl (add1 current)) ]           ; goto next number without adding to prime list
    [else (loop (cons current outl) (add1 current))] ; add to prime list and go to next number
    )))

```

Testing:

```
(nprimes 35)

```

Output:

```
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149)

```
> 0 votes

# Answer
## **Javascript, 61 chars**

```
f=(n,p=2,i=2)=>p%i?f(n,p,++i):i==p&&n--&alert(p)||n&&f(n,++p)

```

A bit worse than O(n^2), will run out of stack space for large n.
> 0 votes

---
Tags: code-challenge, primes
---


title: Rate my sorting

text:
# Question
Title: Rate my sorting
# Introduction

So my boss is making me do some manual labor...urgh...I have to take a part out a box of parts, process it and put it back in the box. To make this more interesting I try to sort the parts as I do this, as each part has a unique alphanumeric serial number.

Unfortunately, I only have room to have four parts out the box at a time and I'm not taking each part out of the box more than once (that'd be even more work!) so my sorting capabilities are limited.

# Challenge

Your challenge is to write a full program or function that rates my sorting of a given box of parts.

# The Sorting Process

1. Take 4 parts out of the box
2. Take the part that comes first by serial number
3. Process the part
4. Put the part back in the box
5. Take another part out of the box (if there are any left)
6. Repeat steps 2-6 until all parts are processed (moved only once).

# Input

A set of serial numbers in the format `[A-Z][A-Z][0-9][0-9][0-9]` Input can be an array/list or deliminated string, python example...

```
['DT064', 'SW938', 'LB439', 'KG338', 'ZW753', 'FL170', 'QW374', 'GJ697', 'CX284', 'YW017']

```

# Output:

The score of the sorted/processed box (see scoring below)

# Scoring

For each part note how far away it is from where it would be in a perfectly sorted box. The score is the total of this value for all parts in the box.

# Examples/Test cases

```
input          ['AA111', 'AA222', 'AA333', 'AA444', 'AA000', 'AA555']
my sorted list ['AA111', 'AA000', 'AA222', 'AA333', 'AA444', 'AA555'] (no need to output)
perfect sort   ['AA000', 'AA111', 'AA222', 'AA333', 'AA444', 'AA555'] (no need to output)
output         2 (because first two elements are out of sequence by 1 position each)

input          ['GF836', 'DL482', 'XZ908', 'KG103', 'PY897', 'EY613', 'JX087', 'XA056', 'HR936', 'LK200']
my sorted list ['DL482', 'GF836', 'EY613', 'JX087', 'KG103', 'HR936', 'LK200', 'PY897', 'XA056', 'XZ908']
perfect sort   ['DL482', 'EY613', 'GF836', 'HR936', 'JX087', 'KG103', 'LK200', 'PY897', 'XA056', 'XZ908']
output         6

input  ['UL963', 'PJ134', 'AY976', 'RG701', 'AU214', 'HM923', 'TE820', 'RP893', 'CC037', 'VK701']
output 8

input  ['DE578', 'BA476', 'TP241', 'RU293', 'NQ369', 'YE849', 'KS028', 'KX960', 'OU752', 'OQ570']
output 6

input  ['BZ606', 'LJ644', 'VJ078', 'IK737', 'JR979', 'TY181', 'RJ990', 'ZQ302', 'AH702', 'EL539']
output 18

```

# Answer
# 05AB1E, ~~28~~ ~~25~~ ~~24~~ 23 bytes

**-5** bytes thanks to **Emigna**

```
gÍG4ôć{ćˆì˜}¯ì©{vXykNαO

```

Try it online!

### Explanation

```
gÍG4ôć{ćˆì˜}¯ì©{vXykNαO   Argument l
gÍG        }              len(l)-3 times do:
   4ô                       Split into pieces of 4
     ć                      Extract head
      {                     Sort
       ćˆ                   Extract head and add to global array
         ì˜                 Put rest of array back together
            ¯ì            Prepend global array to leftover elements
              ©           Store in register_c without popping
               {          Sort
                v         For y in sorted array, do:
                 ®yk        Index of y in register_c
                    Nα      Absolute difference with iteration index
                      O     Total sum of index differences

```
> 3 votes

# Answer
## JavaScript (ES6), 104 bytes

```
a=>a.reduce(p=>(j=i-[...a].sort().indexOf(a[a.splice(i,4,...a.slice(i,i+4).sort()),i++]))>0?p+j:p-j,i=0)

```

### Test cases

```
let f =

a=>a.reduce(p=>(j=i-[...a].sort().indexOf(a[a.splice(i,4,...a.slice(i,i+4).sort()),i++]))>0?p+j:p-j,i=0)

console.log(f(['AA111', 'AA222', 'AA333', 'AA444', 'AA000', 'AA555']))
console.log(f(['GF836', 'DL482', 'XZ908', 'KG103', 'PY897', 'EY613', 'JX087', 'XA056', 'HR936', 'LK200']))
console.log(f(['UL963', 'PJ134', 'AY976', 'RG701', 'AU214', 'HM923', 'TE820', 'RP893', 'CC037', 'VK701']))
console.log(f(['DE578', 'BA476', 'TP241', 'RU293', 'NQ369', 'YE849', 'KS028', 'KX960', 'OU752', 'OQ570']))
console.log(f(['BZ606', 'LJ644', 'VJ078', 'IK737', 'JR979', 'TY181', 'RJ990', 'ZQ302', 'AH702', 'EL539']))
```
> 2 votes

# Answer
## JavaScript (ES6), ~~115~~ 113 bytes

```
a=>a.reduce((r,_,i)=>r+=(i-=[...a].sort().indexOf((b=b.splice(0,4).sort().concat(b)).shift()))<0?-i:i,0,b=[...a])

```
> 1 votes

# Answer
# PHP, 132 bytes

```
<?for($d=4+count($p=$g=$_GET),sort($p);--$d;rsort($n),$i<4?:$r+=abs($k++-array_flip($p)[array_pop($n)]))$d<4?:$n[]=$g[+$i++];echo$r;

```

Try it online!

# PHP, 136 bytes

```
<?for($n=array_slice($p=$g=$_GET,0,$i=3),sort($p);$n;rsort($n),$r+=abs($k++-array_flip($p)[array_pop($n)]))$g[$i]&&$n[]=$g[$i++];echo$r;

```

Try it online!
> 1 votes

# Answer
# Mathematica, 173 bytes

```
A={};(V=Sort[S=#];While[Length@S>4,T=Take[Sort@S[[;;4]],1][[1]];A~AppendTo~T;S=S~DeleteCases~T];Tr@Table[Abs[i-Flatten[Position[Join[A,Sort@S],V[[i]]]][[1]]],{i,Length@V}])&

```

**input**

> \[{BZ606, LJ644, VJ078, IK737, JR979, TY181, RJ990, ZQ302, AH702, EL539}\]

**output**

> 18
> 0 votes

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


# Question
Title: Regex that matches everything but itself
You must make a regex that matches everything except itself. For example, `PPCG` must not match `PPCG`, but must match everything else, like `something`, `PPC`, and `PPCG!`.

Surrounding slashes are **not** considered part of the regex in flavors where they are usually part of the syntax. The same is true of all delimiters.

The regex needs to match the entire string, not just a substring.

You may choose your flavor, but you can't use a flavor newer than this challenge. Please pick a flavor that is easily tested.

Shortest regex in bytes wins.

(Sandbox (deleted))

# Answer
> 6 votes
## PCRE flavour, 45 bytes

```
^(?!\^()(?R){2}\z)|\1\Q(?!\^()(?R){2}\z)|\1\Q

```

Try it at regex101.

This is a simple modification of jimmy23013's brilliant solution to the opposite challenge. We just need to make two changes:

* In this challenges, the delimiters shouldn't be matched so we drop them from the regex as well. However, that could lead to infinite recursion, because then no characters would be matched before the `(?R)` call. To fix this, we match the `^` explicitly with `\^` to have one character before we enter the recursion.
* We need to negate the result which is as simple as wrapping everything after the `^` in a negative lookahead to ensure that the input *isn't* equal to the string.

For the details of this quining approach, see jimmy's amazing answer.

---
Tags: code-golf, decision-problem, regular-expression
---


title: Maximal mutually co-prime factorization

text:
# Question
Title: Maximal mutually co-prime factorization
# Definitions

* Two numbers are **co-prime** if their only positive common divisor is `1`.
* A list of numbers is **mutually co-prime** if every pair of numbers within that list are co-prime with each other.
* A factorization of number `n` is a list of numbers whose product is `n`.

# Task

Given a positive number `n`, output the mutually co-prime factorization of `n` with the maximum length that does not include `1`.

# Example

For `n=60`, the answer is `[3,4,5]`, because `3*4*5=60` and no other mutually co-prime factorization without `1` has length greater than or equal to `3`, the length of the factorization.

# Rules and freedoms

* You can use any reasonable input/output format.
* The entries in the output list do not need to be sorted.

# Testcases

```
n   output
1   []
2   [2]
3   [3]
4   [4]
5   [5]
6   [2, 3]
7   [7]
8   [8]
9   [9]
10  [2, 5]
11  [11]
12  [3, 4]
13  [13]
14  [2, 7]
15  [3, 5]
16  [16]
17  [17]
18  [2, 9]
19  [19]
20  [4, 5]
21  [3, 7]
22  [2, 11]
23  [23]
24  [3, 8]
25  [25]
26  [2, 13]
27  [27]
28  [4, 7]
29  [29]
30  [2, 3, 5]
31  [31]
32  [32]
33  [3, 11]
34  [2, 17]
35  [5, 7]
36  [4, 9]
37  [37]
38  [2, 19]
39  [3, 13]
40  [5, 8]
41  [41]
42  [2, 3, 7]
43  [43]
44  [4, 11]
45  [5, 9]
46  [2, 23]
47  [47]
48  [3, 16]
49  [49]
50  [2, 25]
51  [3, 17]
52  [4, 13]
53  [53]
54  [2, 27]
55  [5, 11]
56  [7, 8]
57  [3, 19]
58  [2, 29]
59  [59]
60  [3, 4, 5]
61  [61]
62  [2, 31]
63  [7, 9]
64  [64]
65  [5, 13]
66  [2, 3, 11]
67  [67]
68  [4, 17]
69  [3, 23]
70  [2, 5, 7]
71  [71]
72  [8, 9]
73  [73]
74  [2, 37]
75  [3, 25]
76  [4, 19]
77  [7, 11]
78  [2, 3, 13]
79  [79]
80  [5, 16]
81  [81]
82  [2, 41]
83  [83]
84  [3, 4, 7]
85  [5, 17]
86  [2, 43]
87  [3, 29]
88  [8, 11]
89  [89]
90  [2, 5, 9]
91  [7, 13]
92  [4, 23]
93  [3, 31]
94  [2, 47]
95  [5, 19]
96  [3, 32]
97  [97]
98  [2, 49]
99  [9, 11]

```

# Scoring

This is . Shortest answer in bytes wins.

# Answer
> 10 votes
## Mathics, 24 bytes

```
#^#2&@@@FactorInteger@#&

```

Try it online!

# Answer
> 9 votes
# Brachylog, 4 bytes

```
ḋḅ×ᵐ

```

Try it online!

**Explanation**

```
       # output is the list of
  ×ᵐ   # products of each
 ḅ     # block of consecutive equal elements
ḋ      # of the prime factors
       # of the input

```

# Answer
> 5 votes
# 05AB1E, ~~3~~ 5 bytes

+2 bytes to fix the edge case of `1`. Thanks to Riley for the patch (and for the test suite, my 05ab1e is not that strong!)

```
ÒγP1K

```

Test suite at **Try it online!**

### How?

```
Ò     - prime factorisation, with duplicates
 γ    - split into chunks of consecutive equal elements
  P   - product of each list
   1  - literal one
    K - removed instances of top from previous
      - implicitly display top of stack

```

# Answer
> 3 votes
# MATL, 7 bytes

```
&YF^1X-

```

Try it online! Or verify all test cases.

### Explanation

Consider input `80` as an example.

```
&YF    % Implicit input. Push array of unique prime factors and array of exponents
       % STACK: [2 3 5], [4 0 1]
^      % Power, element-wise
       % STACK: [16 1 5]
1      % Push 1
       % STACK: [16 1 5], 1
X-     % Set difference, keeping order. Implicitly display
       % STACK: [16 5]

```

---

*EDIT (June 9, 2017): `YF` with two outputs has been modified in release 20.1.0: non-factor primes and their (zero) exponents are skipped. This doesn't affect the above code, which works without requiring any changes (but `1X-` could be removed).*

# Answer
> 3 votes
## CJam, 9 bytes

```
{mF::#1-}

```

Try it online!

Simply separates the input into its constituent prime powers and removes `1`s (only necessary for input `1`).

# Answer
> 3 votes
# Haskell, 51 bytes

`(2#)` is an anonymous function taking an integer and returning a list.

Use as `(2#) 99`.

```
m#n|m>n=[]|x<-gcd(m^n)n=[x|x>1]++(m+1)#div n x
(2#)

```

Try it online!

Inspired by the power trick some people used in the recent squarefree number challenge.

* `m#n` generates factors of `n`, starting with `m`.
* If `m>n`, we stop, concluding we've already found all factors.
* `x=gcd(m^n)n` is the largest factor of `n` whose prime factors are all in `m`. Note that because smaller `m` are tested first, this will be `1` unless `m` is prime.
* We include `x` in the resulting list if it's not 1, and then recurse with the next `m`, dividing `n` by `x`. Note that `x` and `div n x` cannot have common factors.
* `(2#)` takes a number and starts finding its factors from `2`.

# Answer
> 2 votes
# Jelly, 5 bytes

```
ÆF*/€

```

Test suite at **Try it online!**

### How?

```
ÆF*/€ - Main link: n
ÆF    - prime factors as [prime, exponent] pairs
   /€ - reduce €ach with:
  *   - exponentiation

```

# Answer
> 2 votes
## Alice, 10 bytes

```
Ifw.n$@EOK

```

Try it online!

Unfortunately, this uses code points as integer I/O again. The test case in the TIO link is input **191808** which decomposes into **64**, **81** and **37**. Note that this solution prints the prime powers in order from largest to smallest prime, so we get the output `%Q@`.

For convenience, here is a 16-byte solution with decimal I/O which uses the same core algorithm:

```
/O/\K
\i>fw.n$@E

```

Try it online!

### Explanation

As the other answers, this decomposes the input into prime powers.

```
I      Read a code point as input.
f      Compute its prime factorisation a prime/exponent pairs and push them
       to the stack in order from smallest to largest prime.
w      Remember the current IP position on the return address stack. This
       starts a loop.
  .      Duplicate the current exponent. This will be zero once all primes
         have been processed.
  n$@    Terminate the program if this was zero.
  E      Raise the prime to its corresponding power.
  O      Output the result as a character.
K      Return to the w to run the next loop iteration.

```

# Answer
> 2 votes
## mathematica 46 bytes

```
#[[1]]^#[[2]]&/@If[#==1,#={},FactorInteger@#]&

```

Try it online!

# Answer
> 1 votes
# Pari/GP, 28 bytes

```
n->[x[1]^x[2]|x<-factor(n)~]

```

Try it online!

# Answer
> 1 votes
# PHP, 62 Bytes

prints a associative array with the prime as key and how often the prime is use as value and nothing for input `1`

```
for($i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!++$r[$i];print_r($r);

```

Try it online!

Output for `60`

```
Array
(
    [2] => 2
    [3] => 1
    [5] => 1
)

```

# PHP, 82 Bytes

```
for($i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!($r[$i]=$r[$i]?$r[$i]*$i:$i);print_r($r);

```

Try it online!

prints nothing for input `1` if you wish a empty array instead and a sorted array it will be a little longer

```
for($r=[],$i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!($r[$i]=$r[$i]?$r[$i]*$i:$i);sort($r);print_r($r);

```

# Answer
> 1 votes
# Actually, 6 bytes

```
w⌠iⁿ⌡M

```

Try it online!

Explanation:

```
w⌠iⁿ⌡M
w       factor into [prime, exponent] pairs
 ⌠iⁿ⌡M  for each pair:
  i       flatten
   ⁿ      prime**exponent

```

# Answer
> 0 votes
# miniML, 47 bytes

Challenges involving prime factorization are terribly over-represented here, so we are all sadly forced to have factorization in the standard library.

```
fun n->map(fun p->ipow(fst p)(snd p))(factor n)

```

Note that the 'mini' in miniml refers to the size of the feature set, not the size of source code written in it.

# Answer
> 0 votes
# Ruby, 61 bytes

```
require 'prime'
->n{(2..n).select{|e|n/e.to_f%1==0&&e.prime?}}

```

I'm really disappointed after looking 6-7 byte solutions -))

# Answer
> 0 votes
# Mathematica, 24 bytes

```
Power@@@FactorInteger@#&

```

Too bad `@@@*` is not a thing. Also, I'd like `/@*`, `@@*`, and in fact, change `@@@` to `/@@`, `//@` to `@@@` or whatever and add the infinite family of `//@`, `///@`, ...

---
Tags: code-golf, number-theory, primes, division
---


title: The weird and wild bean game

text:
# Question
Title: The weird and wild bean game
Maybe some of you already know this game: you have a collection of jelly beans of different colors. For every color, the bean can have different tastes, some are good and some are bad, and you cannot tell them apart. You have to pick a bean of a given color, and pray you have select a good one.

So, write the shortest program that receives a color of your choice (from a given list), and randomly returns the taste selected. The taste has to be picked from a built-in list. The possible list of inputs and outputs are:

```
Input      Output choices [only one from the list]
--------------------------------------------------
green      lawn clippings, lime, mucus, pear
yellow     rotten eggs, buttered popcorn
blue       toothpaste, blue berry
orange     vomit, peach
brown      canned dog food, chocolate
white      stinky socks, tutti-frutti, baby diapers, coconut

```

Rules:

* You can assume that the input is going to be always a color from the input choices.
* Case and trailing spaces and/or newlines do not matter.
* Output must be uniformly random: succesive program executions must yield different results, and the chances of getting a given taste must be the same for all tastes in a list.

This is , so may the shortest program win!

# Answer
# C#, ~~418~~ ~~313~~ ~~305~~ 271 bytes

```
s=>{var a="lawn clippings,lime,mucus,pear|rotten eggs,buttered popcorn|toothpaste,blue berry|vomit,peach|canned dog food,chocolate|stinky socks,tutti-frutti,baby diapers,coconut".Split('|')["eluaoi".IndexOf(s[2])].Split(',');return a[new System.Random().Next(a.Length)];}

```

Too long even for C# but I can't see how to get it any shorter.

Full/Formatted version:

```
using System;

class P
{
    static void Main()
    {
        Func<string, string> f = s =>
        {
            var a = "lawn clippings,lime,mucus,pear|rotten eggs,buttered popcorn|toothpaste,blue berry|vomit,peach|canned dog food,chocolate|stinky socks,tutti-frutti,baby diapers,coconut"
                    .Split('|')["eluaoi".IndexOf(s[2])].Split(',');

            return a[new System.Random().Next(a.Length)];
        };

        Console.WriteLine(f("green"));
        Console.WriteLine(f("yellow"));
        Console.WriteLine(f("blue"));
        Console.WriteLine(f("orange"));
        Console.WriteLine(f("brown"));
        Console.WriteLine(f("white"));

        Console.ReadLine();
    }
}

```
> 7 votes

# Answer
# JavaScript (ES6), 235 bytes

I need to figure out how to compress strings in JS!

```
c=>(a="lawn clippings,lime,mucus,pear|rotten eggs,buttered popcorn|toothpaste,blue berry|vomit,peach|canned dog food,chocolate|stinky socks,tutti-frutti,baby diapers,coconut".split`|`["eluaoi".search(c[2])].split`,`)[new Date%a.length]

```

If that's not "random enough" for your tastes then add 7 bytes replacing `new Date` with `Math.random()`.

```
c=>(a="lawn clippings,lime,mucus,pear|rotten eggs,buttered popcorn|toothpaste,blue berry|vomit,peach|canned dog food,chocolate|stinky socks,tutti-frutti,baby diapers,coconut".split`|`["eluaoi".search(c[2])].split`,`)[Math.random()*a.length|0]

```

---

## Try it

```
f=
c=>(a="lawn clippings,lime,mucus,pear|rotten eggs,buttered popcorn|toothpaste,blue berry|vomit,peach|canned dog food,chocolate|stinky socks,tutti-frutti,baby diapers,coconut".split`|`["eluaoi".search(c[2])].split`,`)[Math.random()*a.length|0]

r=(d=document).createElement("input");r.name="i";r.type="radio";l=d.createElement("label");j="Kiwi,sour_lemon,berryBlue,OrangeSherbet,rootBeer,Coconut".split`,`;for(s in e="green,yellow,blue,orange,brown,white".split`,`){r=r.cloneNode();l=l.cloneNode();l.setAttribute("for",r.id=r.value=e[s]);l.style.backgroundImage=`url(https://cdn-tp1.mozu.com/9046-11441/cms//files/${j[s]}.jpg)`;g.prepend(r,l);}onchange=_=>o.innerText=(v=(i=d.querySelector(":checked")).value)+": "+f(v,i.checked=0)
```

```
body{align-items:center;background:#eee;display:flex;flex-wrap:wrap;height:100vh;justify-content:center;margin:0;text-align:center;}#g{background:#fff;box-shadow:5px 5px 5px #ccc;padding:10px;}input{display:none;}label{background-repeat:no-repeat;background-size:contain;cursor:pointer;display:inline-block;height:64px;margin:10px;width:75px;}#o{font-family:monospace;font-size:18px;margin:10px auto;text-align:center;width:100%;}
```

```
<div id=g><pre id=o>click a jelly bean</pre></div>
```
> 5 votes

# Answer
# 05AB1E, 126 bytes

```
¨¤.•4Õ!Õ•.•QCQΓ^ïTÁÕ#HвΘÊÓΘñ…~çÌùY$J*shÉÉk‹Ú&žвZÍζö<^'¢βŽÚq¡eζd`Ãó¨₅γ!i"v_Ym¤ÓδVË5¥vÅ¼QÐ‰øΣγ9∞\L‰,ǝ¦8VÜUт:x+sм•'x'-:'q¡'j¡€.R‡

```

Explanation:

```
¨¤                              Get the second to last character of the string
  .•4Õ!Õ•                       Compressed string: "eougwt"
         .• .. •                Compressed base-27 string
                'x'-:           Replace "x" with "-" (for tutti-frutti)
                     'q¡        Split on 'q'
                        'j¡     Split each on 'j'
                           €    For each...
                             .R  Select a random element
                               ‡ Transliterate

```

If anyone's wondering, here's the uncompressed string:

```
lawn clippingsjlimejmucusjpearqrotten eggsjbuttered popcornqtoothpastejblue berryqvomitjpeachqcanned dog foodjchocolateqstinky socksjtuttixfruttijbaby diapersjcoconut

```

I can probably compress it more using some clever tricks and the dictionary, though.

Try it online!
> 5 votes

# Answer
# Jelly, ~~101~~ 100 bytes

```
3ị“©ȷ#Ȧ-»iị“'æLṬẏeṃɼẹ-N0ṁH)A“¬ɗ-ṃȥḞ“I$aṇṾjð4“£Ʋṛ÷pḶƥƑL]p“÷Hnøgİỵ£@ḥEḶƑƤi÷Ḃ\oŻẆ#ụqU½b“ḥĠḄĿĖṇ⁻Œḳ-¬"»ỴX

```

Try it online!
> 4 votes

# Answer
# Python 2, ~~301~~ 258 bytes

```
lambda x:choice({'e':'lawn clippings,lime,mucus,pear','l':'rotten eggs,buttered popcorn','u':'toothpaste,blue berry','a':'vomit,peach','o':'canned dog food,chocolate','i':'stinky socks,tutti-frutti,baby diapers,coconut'}[x[2]].split(','))
from random import*

```

Try it online!

Saved very many bytes by shortening the keys to use the 2nd index of the input, as suggested by @TheLethalCoder, and by splitting on commas instead of using a direct list.
> 3 votes

# Answer
# Japt, 148 146 bytes

```
`È}hpÂŠ1½ue ¼rry
lawn c¦ppÄ1Ò˜1muc«1pe‡
vÇ1pea®
ÐXky socks1ÉÍi-frÔk1baby ¹ap€s1¬¬n©
¯nšd ºg food1®o¬ÓŠ
Î eggs1ç˜ª pop¬rn`·g`uÁ4`âUg2¹q1 ö

```

Try it online!

Saved 6 bytes thanks to Shaggy and ETHproductions
> 3 votes

# Answer
# Jelly,  ~~95~~  94 bytes

```
OḄị“÷Hnøgİỵ£@ḥEḶƑƤi÷Ḃ\oŻẆ#ụqU½b““¬ɗ-ṃȥḞ“'æLṬẏeṃɼẹ-N0ṁH)A“ḥĠḄĿĖṇ⁻Œḳ-¬"““I$aṇṾjð4“£Ʋṛ÷pḶƥƑL]p»ỴX

```

A monadic link accepting a list of (lowercase) characters and returning a list of characters.

**Try it online!** or eat a packet of 48.

### How?

Eighty-nine of the ninety-four bytes are a compressed list of eight strings. Two of these are empty strings and the other six are each newline separated flavours for one of the colours:

```
“...““...“...“...““...“...»
“...““...“...“...““...“...»
“                         » - a compression of dictionary words & or strings
    ““   “   “   ““   “     - list separations
    ^            ^          - the two empty lists of characters
 ...^ ... ... ...^ ... ...  - bytes used to encode the data
 wht  org grn ylw^ blu brn  - with the colours indicated. For example:
  1 2  3   4   5 6  7   0   -   “ḥĠḄĿĖṇ⁻Œḳ-¬"» is a compression of:
                            -     word     + word   + string + word       + word
                             -     "rotten" + " egg" + "s\n"  + "buttered" + " popcorn"
                             - and is at the fifth index, relating to "yellow"

```

The rest of the program parses the input to decide which list to use, splits the chosen list by newlines and picks a random element:

```
OḄị“...»ỴX - Main link:s e.g.: "blue"           "yellow"                  "brown"              "white"               "orange"                 "green"
O          - cast to ordinals  [98,108,117,101] [121,101,108,108,111,119] [98,114,111,119,110] [119,104,105,116,101] [111,114,97,110,103,101] [103,114,101,101,110]
 Ḅ         - from binary       3276             7125                      1151                 6899                  3272                     3489
  ị        - index into - 1 based and modular with 8 items so...
           -          indexes: 3276%8=4         7125%8=5                  1151%8=7             6899%8=3              3272%8=0                 3489%8=1
        Ỵ  - split at newlines (gets the list of flavours for the chosen colour)
         X - random choice (gets one of those flavours at random)

```
> 3 votes

# Answer
# Java, 288 bytes

```
s->{String[]a="lawn clippings,lime,mucus,pear#rotten eggs,buttered popcorn#toothpaste,blue berry#vomit,peach#canned dog food,chocolate#stinky socks,tutti-frutti,baby diapers,coconut".split("#")["eluaoi".indexOf(s.charAt(2))].split(",");return a[new java.util.Random().nextInt(a.length)];}

```

Test it yourself!

Could be golfed by using a `char[]`.

However the random part can't be "uniformly distributed" without the explicit use of `Random.nextInt(int)`. Even `(int)(Math.random()*a.length)` isn't uniformly distributed.
> 2 votes

# Answer
# T-SQL, ~~432 423 375 367 336~~ 295 bytes

Finally, a set-based operation!!

```
SELECT TOP 1 SUBSTRING(value,2,99)
FROM t,STRING_SPLIT('elawn clippings-elime-emucus-epear-lrotten eggs-lbuttered popcorn-utoothpaste-ublue berry-avomit-apeach-ocanned dog food-ochocolate-istinky socks-itutti-frutti-ibaby diapers-icoconut','-')
WHERE SUBSTRING(c,3,1)=LEFT(value,1)
ORDER BY NEWID()

```

(Line breaks are for display and are not counted in total.)

Input is via column **c** in named table **t**, per our guidelines.

I'm simply joining our input table to a table full of the valid color/flavor combinations, then selecting a random row. `ORDER BY NEWID()` is a common way to randomize sort order in SQL. Depending on how strict you are, you might not consider it perfectly uniformly random, but it should be sufficiently random for jelly bean selection.

**EDIT 1:** Saved 9 bytes by using only the 3rd character of the color, inspired by other answers.

**EDIT 2:** Saved **48** bytes by putting the color flag and flavor in a single column. Lots of characters saved in the INSERT.

**EDIT 3:** Saved 8 bytes by replacing `INSERT INTO b(o)` with `INSERT b`

**EDIT 4:** Saved 31 more bytes by joining straight to the virtual table of `VALUES` and therefore eliminating the `CREATE TABLE` and `INSERT`.

**EDIT 5:** Save 41 bytes by upgrading to SQL 2016-only `STRING_SPLIT` function, which allows me to eliminate the variable and dynamic SQL execution.
> 1 votes

# Answer
## \>\<\>, 311 bytes

```
</"y"/\_  _
v\i-?\x"sgge nettor"
v/"l"/\"nrocpop derettub"
v\i-?\x"etsaphtoot"
v/"o"/\"yrreb eulb"
v\i-?\x"etalocohc"
v/"n"/\"doof god dennac"
v\i-?\x"timov"
v/"n"/\"hcaep"
v\i-?\>x\/~~"srepaid ybab"
v"lime" x"sgnippilc nwal"
v"pear"x  _"sucum"
v    \~__>x\
v"coconut" x"skcos yknits"
>l?!;/\  \x_"itturf-ittut"

```

Try it online, or watch it at the fish playground

Featuring SK cosy knits and Doof God Dennac!

Explanation: The fish's first task is to figure out what the input word is by zig-zagging down the left hand side. The fish can only read one letter at a time, and it takes fewer bytes to do this destructively. First, the fish reads the first letter and asks if it's `"y"` — if it is, the word is "yellow", otherwise it moves on. It then reads the second letter — if it's `"l"`, the word is "blue", otherwise it moves on; and so on. If it reads five letters and they don't match `"y"` (**Y**ellow), `"l"` (b**L**ue), `"o"` (br**O**wn), `"n"` (ora**N**ge) or `"n"` (gree**N**) respectively, then the colour must have been "white".

Next comes the random bit. For the colours with two possible outputs, this is pretty straightforward — for yellow, for example, the fish enters the following code at the `x`:

```
/\
\x"sgge nettor"
 \"nrocpop derettub"

```

The `x` sets the direction randomly: if it's up or left, the fish swirls around the mirrors back to the `x`, but if it's right or down, it reads "rotten eggs" or "buttered popcorn" (in reverse).

The four-way splits (for white and green) are messier, but they follow the same general principal — the first is:

```
     >x\
"lime" x"sgnippilc nwal"
"pear"x   "sucum"
      __

```

Note that if the fish swims up from the first `x`, it passes through eight `"`s, which toggle string mode on and off four times, then it hits a mirror and swims back down.

To get to the last four-way split, the fish has to swim through the `e` and `r` of "lime" and "pear", which add `e = 14` to the stack (and reverse it), so we first have to delete that with `~`. One of the four branches also involves swimming through a junk string, `"> "`, which we delete with `~~`.

```
    \   /~~"srepaid ybab"
    e   "
    r    _
    \~  >x\
"coconut" x"skcos yknits"
        \x_"itturf-ittut"
         _

```

Finally, after adding one of the bean flavours to the stack, the fish reaches the stream of `v`s in the leftmost column, which sends it to

```
v    \
v    o
>l?!;/

```

which prints characters (using one of the `o`s in "coconut") until there are none left.
> 1 votes

# Answer
# PHP, 242 bytes

```
<?=($a=explode(_,[e=>'lawn clippings_lime_mucus_pear',l=>'rotten eggs_buttered popcorn',u=>'toothpaste_blue berry',a=>vomit_peach,o=>'canned dog food_chocolate',i=>'stinky socks_tutti-frutti_baby diapers_coconut'][$argn[2]]))[array_rand($a)];

```

Try it online!
> 0 votes

# Answer
# Mathematica, 247 bytes

```
R=RandomChoice
green=R@{lawn clippings,lime,mucus,pear}
yellow=R@{rotten eggs,buttered popcorn}
blue=R@{toothpaste,"blue berry"}
orange=R@{vomit,peach}
brown=R@{canned dog food,chocolate}
white=R@{stinky socks,tutti-frutti,baby diapers,coconut}
#&

```

**Input** form

> \[green\]
> 0 votes

# Answer
# Clojure, 231 bytes

```
#(rand-nth({\e["lawn clippings""lime""mucus""pear"]\l["rotten eggs""buttered popcorn"]\u["toothpaste""blue berry"]\a["vomit""peach"]\o["canned dog food""chocolate"]\i["stinky socks""tutti-frutti""baby diapers""coconut"]}(get % 2)))

```

Same idea as the others, I can just save some space compared to other languages. Compressing strings seems like a lost cause.
> 0 votes

---
Tags: code-golf, random, game, compression
---


# Question
Title: Golf a bijection within the natural numbers which map the primes to a proper subset of the primes
## Definitions

* A **bijection** from a set `S` to a set `T` is a function from `S` to `T` such that one element in `T` is mapped by exactly one element in `S`.
* A **bijection within a set** `S` is a bijection from `S` to `S`.
* The **natural numbers** are the integers which are greater than or equal to `0`.
* A **subset** of a set `S` is a set such that every element in the set is also in `S`.
* A **proper subset** of a set `S` is a set that is a subset of `S` which is not equal to `S`.

## Task

Write a program/function that takes a natural number as input and outputs a natural number. It must be a bijection, and the image of the primes under the program/function, `{f(p) : p ∈ ℙ}`, must be a proper subset of , where  is the prime numbers.

## Scoring

This is . Shortest answer in bytes wins. Standard loopholes apply.

# Answer
> 17 votes
## Mathematica, ~~54~~ 48 bytes

```
±(t=x_?PrimeQ)=NextPrime@x
±n_:=Abs[n-1]/.t:>x-1

```

Defines the following bijection:

```
 n  0, 1, 2, 3, 4, 5, 6,  7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...
±n  1, 0, 3, 5, 2, 7, 4, 11, 6, 8,  9, 13, 10, 17, 12, 14, 15, 19, ...

```

The basic idea is to map each prime to the next, to ensure that they are mapped to a proper subset. This results in a "gap" at **2**. To fill that gap, we want to map **4** to **2** and then each other composite number to the previous composite number, to "bubble up" the gap. Since **2** and **3** are the only two adjacent primes, we can express both of those mappings as "**n-1** or if that's a prime then **n-2**". Finally, this mapping ends up sending **1** to **0** and we make it send **0** back to **1** by taking the absolute value of **n-1**.

# Answer
> 8 votes
# MATL, 21 bytes

*Thanks to Emigna for spotting a mistake, now corrected*

```
tZp?_Yq}q:Zp~fX>sG~E+

```

Try it online!

This implements the following bijection. Write the primes in a row and the non-primes below:

```
2  3  5  7 11 13 17 ...
0  1  4  6  8  9 10 ...

```

Then the output is obtained by following the arrow from the input:

```
2 > 3 > 5 > 7 > 11 > 13 > 17 ...
^
0 < 1 < 4 < 6 <  8 <  9 < 10 ...

```

### Explained code

```
t       % Implicit input. Duplicate
Zp      % Is it a prime? Gives true / false
?       % If so
  _Yq   %   Next prime
}       % Else
  q     %   Subtract 1
  :     %   Range from 1 to that
  Zp~   %   Is each entry not a prime? Gives an array of true / false
  f     %   Find non-zero entries, i.e. non-primes. Will be empty for input 1
  X>    %   Maximum. This gives the greatest non-prime less than the input.
        %   Will be empty for input 1
  s     %   Sum. This is to transform empty into 0
  G~E   %   Push input, negate, times 2. This gives 2 for input 0, or 0 otherwise
  E     %   Add. This handles the case of input 0, so that it outputs 2
        % End (implicit). Display (implicit)

```

# Answer
> 4 votes
# Jelly, 14 bytes

```
Æn’’ÆP¿$ÆP?2¹?

```

Try it online!

Uses Luis's algorithm.

# Answer
> 3 votes
## JavaScript (ES6), ~~82~~ ~~77~~ 75 bytes

Implements the same logic as Luis Mendo's answer.

```
f=(n,i=(P=(n,x=n)=>n%--x?P(n,x):x==1||-1)(x=n))=>x?x==n|P(n)-i?f(n+i,i):n:2

```

### Formatted and commented

```
f = (                   // given:
  n,                    // - n = input
  i =                   // - i = 'direction' to move towards
    (P = (n, x = n) =>  // - P = function that returns:
      n % --x ?         //   - 1 when given a prime
        P(n, x)         //   - -1 when given a composite number
      :                 //
        x == 1 || -1    //
    )(x = n)            // - x = copy of the original input
) =>                    //
  x ?                   // if the input is not zero:
    x == n | P(n) - i ? //   if n equals the input or doesn't match its primality:
      f(n + i, i)       //     do a recursive call in the chosen direction
    :                   //   else:
      n                 //     return n
  :                     // else:
    2                   //   return 2

```

### Demo

```
f=(n,i=(P=(n,x=n)=>n%--x?P(n,x):x==1||-1)(x=n))=>x?x==n|P(n)-i?f(n+i,i):n:2

for(n = 0; n < 50; n++) {
  console.log(n, '->', f(n));
}
```

# Answer
> 2 votes
# Jelly, 12 bytes

```
Æn_ḍ@¡ÆP?2»0

```

Try it online!

### How it works

```
Æn_ḍ@¡ÆP?2»0  Main link. Argument: n (non-negative integer)

      ÆP?     If the input is prime:
Æn                Compute the next prime after n.
              Else:
   ḍ@¡   2        Do once if n is divisible by 2, zero times if not.
  _      2        Subtract 2.
              So far, we've mapped all primes to the next prime, all even integers
              (except 2) to the previous even integer, and all composite, odd,
              positive integers to themselves. In particular, 0 -> 2, but 0 doesn't
              have a preimage, so we need 0 -> 0.
          »0  Take the maximum of the result and 0, mapping 0 -> max(-2, 0) = 0.

```

---
Tags: code-golf, number, primes, set-theory, open-ended-function
---


# Question
Title: Find patterns in numbers based on the similarity of characters?
## Task

The task is to write a script that accepts a number from 1 to 20 inclusive. It will then check if the number has a character that is found in every number that was entered before it. If the number has a character in common it will ask for another number. However if the number does not have a character in common with any of the previous numbers the program will halt

You are given the following array which is named as numbers

```
{"one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twenty"}

```

### Example runs

Say the following number is given

```
1

```

There are no previous numbers so it shares a character will every previous number. So the program will ask for another number, let the following number be given

```
3

```

one and three both share the character "e" so this is a valid number. So we given another number, let the following number be given

```
4

```

four does not share the "e" common to both one and three so this breaks the pattern so the program now stops

Here is another run with just the output of the program shown

```
5
15
17
3
7
8
2

```

This script also had the pattern of numbers with the letter "e" which caused "two" to break the pattern

# Answer
# Python 2, ~~48~~ 46 bytes

Saved two bytes thanks to @ovs!

```
s=set(''.join(l))
while s:s&=set(l[input()-1])

```

Try it online!

Renamed `numbers` to `l`. If that's not okay then add 10 bytes for `l=numbers`.
> 2 votes

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


title: Lazy Click and Drag

text:
# Question
Title: Lazy Click and Drag
Your task is to write a program or function which, given two nonzero integers `x` and `y`, returns a truthy value if the image at coordinates `x` east and `y` north of xkcd's click and drag comic is mostly white and a falsey value otherwise.

# Specifications

* The image should be retrieved from imgs.xkcd.com/clickdrag/\[y\]n\[x\]e.png, where `[y]` and `[x]` are replaced with the *absolute values* of the input `y` and `x` values.
* If `x` is negative, `e` should be changed to a `w`. If `y` is negative, `n` should be changed to a `s`.
* If a 404 error is returned, assume the image is mostly white (output truthy) if `y` is positive and mostly black otherwise. This is because (as far as I can tell) xkcd stores neither completely white regions of the sky nor completely black regions of the ground, leading to less data in their servers and these 404s you must handle. This error handling is not intended to deal with the images not being available.
* "white" is defined as rgb #FFFFFF. You may assume that the images are only white(#FFFFFF) and black(#000000), without gray or other colors. "Mostly white" is defined as at least 2097153 pixels of the image are white (because the png the program should retrieve from img.xkcd.com is always 2048x2048 pixels).
* The program may have any behavior when dealing with pixels that are not exactly #FFFFFF nor #000000 but must produce the same output as expected for the test cases.

# Example

The image at `x=2`, `y=9` should be retrieved from `imgs.xkcd.com/clickdrag/9n2e.png` and appears as follows (formatted as quote to show border):

>

It is mostly white, so the program should return a truthy value.

# Input / Output

Input should be two integers or a list of two integers representing `x` and `y`.

Output should be a truthy or falsy value corresponding to if the image is mostly white.

Input and output should be through any standard I/O method.

# Test Cases

### Truthy (as (x,y))

```
2,9
7,-17
9, 5
3, 2
-5, 1
1, 3

```

### Falsy (as (x,y))

```
3, 1
3, -1
7, -16
2, 1
5, 1
17, -1

```

# Answer
# MATLAB, 144 bytes

```
function r=f(x,y);n=@num2str;r=1;try;r=nnz(imread(['http://imgs.xkcd.com/clickdrag/',n(y),'n'+5*(y<0),n(x),'e'+18*(x<0),'.png'],'png'))>2^21;end

```

This function takes two arguments `x,y`. `imread` reads the image at the given path. In this case we get a black and white image where each pixel (= entry in a matrix) contains the number `0` or `255`. To count the white (`255`) pixels, `nnz` is used (which conts the number of nonzero entries). To account for possible eerrors, we wrap this call in `try/end` and predefine the return value to `1` (nonzero numbers are truthy in MATLAB). The change of e.g. `n` and `s` depending on the sign of `y` is done via character arithmetic.
> 3 votes

# Answer
## bash, ~~172~~ ~~164~~ 158 bytes

```
t=tr\ \\-0-9
curl imgs.xkcd.com/clickdrag/${2#-}$($t sn<<<${2::1})${1#-}$($t we<<<${1::1}).png|convert - a.pgm
echo $[$??$2>0:`grep -ao ÿ a.pgm|wc -l`>2**21]

```

This won't work on TIO due to the requirement for internet access.

There's an `\xFF` byte in the code, which is likely to be mangled due to encodings, so here's a script you can use to run all the test cases locally:

```
#!/bin/bash

xxd -r >clickdrag.sh <<'end'
00000000: 743d 7472 5c20 5c5c 2d30 2d39 0a63 7572  t=tr\ \\-0-9.cur
00000010: 6c20 696d 6773 2e78 6b63 642e 636f 6d2f  l imgs.xkcd.com/
00000020: 636c 6963 6b64 7261 672f 247b 3223 2d7d  clickdrag/${2#-}
00000030: 2428 2474 2073 6e3c 3c3c 247b 323a 3a31  $($t sn<<<${2::1
00000040: 7d29 247b 3123 2d7d 2428 2474 2077 653c  })${1#-}$($t we<
00000050: 3c3c 247b 313a 3a31 7d29 2e70 6e67 7c63  <<${1::1}).png|c
00000060: 6f6e 7665 7274 202d 2061 2e70 676d 0a65  onvert - a.pgm.e
00000070: 6368 6f20 245b 243f 3f24 323e 303a 6067  cho $[$??$2>0:`g
00000080: 7265 7020 2d61 6f20 ff20 612e 7067 6d7c  rep -ao . a.pgm|
00000090: 7763 202d 6c60 3e32 2a2a 3231 5d         wc -l`>2**21]
end

for x in '2 9' '7 -17' '9 5' '3 2' '-5 1' '1 3' '3 1' '3 -1' '7 -16' '2 1' '5 1' '17 -1'
do
    bash clickdrag.sh $x 2>/dev/null
done

rm clickdrag.sh

```

### Explanation

First, an explanation of how the URL is built:

```
imgs.xkcd.com/clickdrag/${2#-}$($t sn<<<${2::1})${1#-}$($t we<<<${1::1}).png

```

Here, `${2#-}` removes a leading negative sign from the second command line argument, and `${1#-}` does the same for the first. The `n`/`s` and `e`/`w` are generated, respectively, with the snippets (after expanding `$t`)

```
tr '\-0-9' sn<<<${2::1}
tr '\-0-9' we<<<${1::1}

```

The `${_::1}`s take the first character of the appropriate command line argument (which will be `-` if it is negative and a digit otherwise). The `tr` command then turns `-` into `s`/`w` and digits into `n`/`e`.

The URL is then passed to `curl`, which retrieves the image:

```
curl URL|convert - a.pgm

```

The `convert` command from ImageMagick turns the difficult PNG format into the much easier PGM, which uses one byte per pixel. It writes to the file `a.pgm`.

If the URL 404s, the `convert` command will fail to find an image and exit with a nonzero status code. Thus, we can effectively use `$?` (exit code of the last command) as an indicator of whether the URL returned a 404. This comprises the remainder of the code:

```
echo $[$??

```

If the exit code was nonzero (link was a 404), we simply check whether the y coordinate is positive:

```
$2>0

```

Otherwise, we count the number of `\xFF` bytes (white) in the image and test to see whether it's greater than 221:

```
:`grep -ao ÿ a.pgm|wc -l`>2**21]

```
> 2 votes

# Answer
## Javascript (ES6), 317 bytes

```
f=(x,y)=>{l=console.log;c=document.createElement`canvas`.getContext`2d`;i=new Image;i.onload=_=>{c.drawImage(i,0,0,1,1);l(!!c.getImageData(0,0,1,1).data[0])};i.onerror=e=>l(y>=0);i.crossOrigin='anonymous';i.src=`https://crossorigin.me/https://imgs.xkcd.com/clickdrag/${(y<0?y*-1+'s':y+'n')+(x<0?x*-1+'w':x+'e')}.png`}

```

This works by shrinking the image to an 1\*1 pixel, and checking whether the red channel of this pixel is `0` or not (if white it would be `255`).

Note that it has a *somehow* big margin of error for 50 white/50 black cases : on my computer, if there are less than between 50% - 1024px and 50%, it will report as gray, and hence white. But, as long as there is no proof that there is an image in the list with less than 1024 px of difference between black and white, I guess it's still valid.

Ungolfed :

```
f=(x,y)=>{
  l=console.log; // output in the console since the function is async
  c=document.createElement`canvas`.getContext`2d`;
  i=new Image;
  i.onload=_=>{
    c.drawImage(i,0,0,1,1); // draw resized at 1px*1px
    // is the first red value of the pixel '0' ?
    l(!!c.getImageData(0,0,1,1).data[0])
    };
   // handle 404
  i.onerror= e=> l(y>=0);
  // 56 bytes only for cross-origins...
  i.crossOrigin="anonymous";
  i.src= `https://crossorigin.me/https://imgs.xkcd.com/clickdrag/${
    // there could probably be some out-golfing to do here
    (y<0?y*-1+'s':y+'n') + (x<0?x*-1+'w':x+'e')
    }.png`;
}

```

Here is a 319 bytes Promise based live version, for better logging of the outputs, since all this is async :

```
f=(x,y)=>new Promise(l=>{c=document.createElement`canvas`.getContext`2d`;i=new Image;i.onload=_=>{c.drawImage(i,0,0,1,1);l(!!c.getImageData(0,0,1,1).data[0])};i.onerror=e=>l(y>=0);i.crossOrigin='anonymous';i.src=`https://crossorigin.me/https://imgs.xkcd.com/clickdrag/${(y<0?y*-1+'s':y+'n')+(x<0?x*-1+'w':x+'e')}.png`})

var pos = [
// truthy
  {x:2,y:9},
  {x:7,y:-17},
  {x:9,y:5},
  {x:3,y:2},
  {x:-5,y:1},
  {x:1,y:3},
// falsy
  {x:3,y:1},
  {x:3,y:-1},
  {x:7,y:-16},
  {x:2,y:1},
  {x:5,y:1},
  {x:17,y:-1}
  ];
function test(i){
  let p = pos[i];
  let prom = f(p.x, p.y)
  prom.then(r=>{
    console.log(p.x, p.y, ': ', r);
    if(i < pos.length)
      test(++i);
    });
  }
test(0);
```

And if ever someone find an image with less than 1024px of difference between whites and blacks, here is a 378 bytes version which handles it :

```
f=(x,y)=>{l=console.log;o=document.createElement`canvas`;w=o.width=o.height=2048;i=new Image;i.onload=_=>{c=o.getContext`2d`;c.drawImage(i,0,0);l(c.getImageData(0,0,w,w).data.reduce((a,v,i)=>(i%4&&v?++a:a),0)/4>w*w/2)};i.onerror=e=>l(y>=0);i.crossOrigin='anonymous';i.src=`https://crossorigin.me/https://imgs.xkcd.com/clickdrag/${(y<0?y*-1+'s':y+'n')+(x<0?x*-1+'w':x+'e')}.png`}

```
> 1 votes

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


title: Prime Factor Random Numbers!

text:
# Question
Title: Prime Factor Random Numbers!
### Task:

Given two positive integers, generate a random integer between them (inclusive) and then output all its prime factors.

### Examples:

```
Input:   Random Number:     Output:
1,2      2                  [2]
12,46    18                 [2,9]
142,17   40                 [2,2,2,5]

```

### Scoring:

This is so the least bytes wins!

# Answer
# 05AB1E, 4 bytes

```
Ÿ.RÒ

```

Explanation:

```
Ÿ       Create a list [a .. b]
 .R     Pick a random element
   Ò    Prime factors.

```

Try it online!
> 5 votes

# Answer
# Jelly, ~~5~~  4 bytes

```
rXÆf

```

Try it online!

**How it works**

```
rXÆf
r     inclusive range
 X    random element's
  Æf  prime factorization

```

*-1 byte thanks to @LeakyNun*
> 4 votes

# Answer
## Mathematica, 38 bytes

```
#&@@@FactorInteger@RandomInteger@{##}&

```
> 3 votes

# Answer
# Pyth, 4 bytes

```
PO}F

```

Test suite.
> 2 votes

# Answer
# Pyffman 1, ~~90~~ 80 bytes

This is a joke language that was published today (but before the challenge!). It is based on compressing Python using a pre-made Huffman code based on a corpus of golfed Python. Since the code doesn't really consist of bytes (it's bit-based, due to its huffmannness), I give you here the hexdump obtained using `xxd`.

```
00000000: 9c23 9c8f f5fe 9e1d 744a 4ac4 860f 2fcb  .#......tJJ.../.
00000010: 1218 3cbf 70d5 9577 b8cb 4059 44a4 2dbf  ..<.p..w..@YD.-.
00000020: fbaa 9763 4a75 bbbb 90e1 7ac8 410f fbba  ...cJu....z.A...
00000030: 0c91 a0d8 528d dde3 8fd9 0e19 0c56 2ca6  ....R........V,.
00000040: c699 893b 9e1b bc47 fb29 b1a6 624e 79e8  ...;...G.)..bNy.

```

(The original Python code this is based on is ~~164~~ 158 bytes.)
> 1 votes

# Answer
# PHP, 79 bytes

```
for($a=rand($argv[1],$argv[$i=2]);1<$a;)$a%$i?$i++:$a/=$i+!$r[]=$i;print_r($r);

```

Try it online!
> 1 votes

# Answer
# MATL, 5 bytes

```
SYrYf

```

Try it at MATL Online

**Explanation**

```
        % Implicitly grab input as a 1 x 2 array
S       % Sort the input such that the lower end of the range comes first
Yr      % Generate a random integer in this range
Yf      % Compute it's prime factors
        % Implicitly display the result

```
> 1 votes

# Answer
# CJam, 13 bytes

```
{$~),\,-mRmf}

```

Anonymous block that expects an array of two numbers in the stack and replaces it by an array with the output.

Try it online!

### Explanation

```
{       e# Begin block
  $     e# Sort array
  ~     e# Split into the two numbers, a and b, where b is greater
  )     e# Increment b
  ,     e# Range from 0 to b
  \     e# Swap
  ,     e# Range from 0 to a-1
  -     e# Set difference: range from a to b
  mR    e# Random choice
  mf    e# Array of prime factors
}       e# End block

```
> 1 votes

# Answer
# Japt, 7 6 bytes

```
óV ö k

```

Try it online!

Explanation

```
oVÄ ö k
oVÄ        range of integers between first input and second input + 1
    ö      get a random item from the array
      k    return all prime factors

```

Saved a byte thanks to ETHproductions
> 1 votes

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


title: Implode the Box

text:
# Question
Title: Implode the Box
ASCII boxes look like this:

```
++    +---+    +------+    +---+    +---+
++    |   |    |      |    |   |    |   |
      |   |    |      |    |   |    |   |
+-+   |   |    |      |    |   |    |   |
+-+   |   |    |      |    |   |    +---+
      +---+    |      |    |   |
+--+           |      |    |   |    ++
|  |           |      |    |   |    ||
|  |           +------+    |   |    ||
+--+                       |   |    ||
                           +---+    ||
                                    ||
                  +-----+           ||
+------------+    |     |           ++
|            |    |     |
|            |    |     |
+------------+    +-----+

```

Here are some examples of the same ASCII boxes, imploded:

```
++    +- -+    +-    -+    +- -+    +- -+
++    | - |    | -  - |    | - |    | - |
       | |      | -- |      | |      | |
+-+    | |       |  |        "      | - |
+-+   | - |       ||        | |     +- -+
      +- -+      |  |      |   |
+--+            | -- |      | |     ++
|  |           | -  - |      "      ||
|  |           +-    -+     | |     ||
+--+                       | - |   |  |
                           +- -+   |  |
      --                            ||
     -  -         +-   -+           ||
+-  -    -  -+    | - - |           ++
| --      -- |     | = |
| --      -- |    | - - |
+-  -    -  -+    +-   -+
     -  -
      --

```

Here is a link to all of these test case boxes in an easier-to-copy format. The order is all inputs followed by all outputs in the same order.

Your goal is to take an ASCII box as input, and return the imploded box. The rules of implosion are:

1. "+" never changes; neither do "-" or "|" directly adjacent to "+"
2. Starting from the corners, the "-" and "|" move inward by one space more than the same character closer to the corner did. If a "-" and "|" would ever move to the same spot, neither moves.
3. If a "-" and "-" move to the same spot, put a "=" in that spot. If a "|" and "|" move to the same spot, put a " in that spot. These count as two of their respective characters in the same spot moving in opposite directions.
4. Two "-" or two "|" can move past each other, as seen in the bottom left example.
5. If the box is skinny enough, it will start expanding outwards in the same way, always moving away from the side it started out part of.
6. The result should be symmetric across the center line in both the x and y directions (ignoring newlines); this includes spaces, so the result may need to be padded with spaces to satisfy that.

**Rule Details:**

1. This is code-golf, so shortest program in bytes wins.
2. Standard loopholes apply.
3. You can assume each line ends in a newline character.
4. The only characters in the input string will be "+", "-", "|", " ", and "\n" (newline), and your output string should follow the same rules, with the addition of "=" and " as possible characters.
5. You may optionally have a single trailing newline at the end of the last line.
6. The smallest ASCII box you need to handle is the top-left example. Every ASCII box will have exactly 4 "+"s, exactly at its corners.
7. You will need to handle boxes of size `m x n` for any integers `m,n` such that `2<=m,n<256` (largest possible string size of `255*(255+1)`)
8. You can assume you will always get a single valid ASCII box as input.

# Answer
> 14 votes
# Python 2, ~~591~~ ~~555~~ ~~545~~ ~~527~~ ~~525~~ ~~496~~ ~~436~~ ~~351~~ ~~334~~ ~~333~~ 303 bytes

```
s=input()
w=len(s[0])
h=len(s)
V=max(0,w/2-h)
H=max(0,h/2-w)
p=[[' ']*w]*V
q=[' ']*H
s=[q+k+q for k in p+s+p]
d,c=' -=',' |"'
exec"c,d,V,H,w,h=d,c,H,V,h,w;s=map(list,zip(*s))[::-1]\nfor j in range(h-4):q=s[V+j+2];q[H]=c[q[H]==c[2]];r=H+min(j+1,h-4-j);q[r]=c[1+(q[r]>' ')]\n"*4
for x in s:print''.join(x)

```

Try it online!

**EDIT**: My old method first imploded the top and bottom, and then the left and right. Instead, we can implode the top, rotate 90 degrees, and do that 4 times. Also, I was using the user-friendly code, this one requires input be in the form `[['+', '-', '-', '-', '-', '-', '+'], ['|', ' ', ' ', ' ', ' ', ' ', '|'], ['|', ' ', ' ', ' ', ' ', ' ', '|'], ['|', ' ', ' ', ' ', ' ', ' ', '|'], ['+', '-', '-', '-', '-', '-', '+']]` which is ugly but shorter for the program :P (Thanks to Phoenix for catching that)

Credits to Leaky Nun for the header code in the TIO link used for converting human-readable input into computer-readable input.

-85 bytes thanks to Leaky Nun!
-17 bytes by switching from top-implosion to left-implosion which allows the entire row to be stored into a variable and modified. Thanks to Leaky Nun for the suggestion!
-1 byte by switching things around to remove a space.
-30 bytes thanks to Leaky Nun!

# Answer
> 1 votes
# C (clang), 693 bytes

New lines added for readability. The first two are required but the rest are not.

```
#define P B[i][l]
#define m malloc(8)
I(B,h,V,S,J,Z,i,j,l,n,H,W,c,C,a,z,_,L,G,u,N,M)char**B,**Z;char*L,*G,*u;{
V=strlen(B[0]);
S=J=0;
Z=m;
for(i=0,j=h-1;i<h/2+h%2;i++,j--){
for(l=0,n=V-1;l<V/2+V%2;l++,n--){
if(P!=43&&((B[i][l-1]!=43&&i<1)||(B[i-1][l]!=43&&l<1))){
H=P==45;
W=P=='|';
P=B[j][l]=B[i][n]=B[j][n]=32;
if(H){
c=(N=i+l-1)==(M=j-l+1)?61:45;
if(M<0)L=m,sprintf(L,"%*s",V,""),L[l]=L[n]=c,Z[J]=L,J++;
else B[N][l]=B[N][n]=B[M][l]=B[M][n]=c;
}
if(W){
c=(N=l+i-1)==(M=n-i+1)?34:'|';
if(M<0)G=m,sprintf(G,"|%*s%s%*s|",i-n-2,"",B[i],i-n-2,""),B[i]=B[j]=G,S++;
else B[i][N]=B[j][N]=B[i][M]=B[j][M]=c;
}
}
}
}
for(a=-J+1;a<=h+J;u=a<1?Z[-a]:a<=h?B[a-1]:Z[a-h-1],C=S+1-strlen(u)/2,printf("%*s%s\n",C>0?C:0,"",u),a++);
}

```

Thanks for the great challenge! It was quite tricky but I still had a lot of fun.

This takes the input as command-line arguments and outputs to STDOUT a multi-line string of the imploded box. As always, golfing tips are very much appreciated.

Try it online!

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


# Question
Title: I text the correct combo of ones and zeros
I recently listed to the song I'm a Textpert about texting while driving and one particular line in the song inspired this challenge.

> I never stoop so low as to text photos / Instead I text the correct combo of ones and zeros

Now obviously, this would be an almost impossible thing to do in ones head and so you should help textperts world wide by coding a program to do the same thing.

Your job is to take the name of an image file with the dimensions `500x500` pixels and output the file as binary. You may also take an image as input, if you language supports it.

You may use image files with the extensions

* `.jpg`
* `.png`
* `.gif`
* `.bmp`
* `.svg`

Allow me to demonstrate how to convert an image into binary, for those who don't understand what I mean.

**Step 1**

Take the first pixel in the file and retrieve its RGB value as 3 decimal numbers: R, G and B. Let's assume, for example, that the first pixel is `255,0,0` (red).

**Step 2**

Convert each number into its 8-bit binary representation and concatenate into a single 24-bit number. For the example, this yields `111111110000000000000000`

**Step 3**

Add this 24-bit number to the final output. Therefore, the final output should be `6000000` digits long and should consist of entirely `1` and `0`

This is a so shortest code wins!

# Answer
> 4 votes
# Pyth, ~~14~~ 13 bytes

*-1 byte thanks to Erik the Outgolfer (`z` can be removed for implicit input).*

```
sm.[\08.Bd.n'

```

**Explanations**

```
sm.[\08.Bd.n'

            '    # Open the path/URL given as implicit input. Return list of color triples for color images: [(255, 125, 23), ...]
          .n     # Flatten the list
 m     .Bd       # For each element of the list, convert to binary
  .[\08          # Pad with zeros on the left up to 8 characters
s                # Concatenate the list of bytes

```

Unfortunately, because of safety reasons, that cannot be tested with the online interpreter; you will have to clone Pyth to test it on your own computer.

# Answer
> 4 votes
# MATL, ~~13~~ 12 bytes

```
YiH&!8&YB!1e

```

Accepts a filename as a string as input. The output 24-bit numbers are displayed in row-major order.

Unfortunately this doesn't work in the online interpreters for security reasons. Here is a screenshot of it working on my local machine

Here is a slightly modified version in which I manually create a 2 x 2 x 3 image and then use (almost) the same code to process it.

**Explanation**

```
        % Implicitly grab input as a string
Yi      % Read in as an M x N x 3 image
H&!     % Permute the dimensions of the image to be 3 x N x M
8&YB    % Convert to a binary string using 8 bits for each element
!       % Transpose the result
1e      % Reshape to a row vector
        % Implicitly display the result

```

# Answer
> 2 votes
# Mathematica, 103 bytes

```
F=Flatten;Export["x.txt",FromDigits@F[IntegerDigits[#,2,8]&/@F[ImageData[Import["x.bmp"],"Byte"],1],2]]

```

takes an image x.bmp (or any other) and converts it to x.txt file

# Answer
> 2 votes
# C#, 309 bytes

My second code golf, if you can't tell. Takes an image **x.jpg...**

```
using System;using System.Drawing;using System.Linq;class Program{static void Main(string[]a){Bitmap b=(Bitmap)Image.FromFile("x.jpg");Console.WriteLine(string.Join("",from i in Enumerable.Range(0,250000)select Convert.ToString(Convert.ToInt32(b.GetPixel((int)Math.Floor((double)i/500),i%500).Name,16),2)));}}

```

# Answer
> 1 votes
# Octave, 46 bytes

```
@(x)dec2bin(permute(imread(x),[3,1,2]),8)'(:)'

```

Creates an anonymous function named `ans` that can be called with either a filename (`ans('file.png')`) or a URL (`ans('http://image.png')`)

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