title: Official Ruby Inspector

text:
# Question
Title: Official Ruby Inspector
Here is a simple ASCII art ruby:

```
  ___
 /\_/\
/_/ \_\
\ \_/ /
 \/_\/

```

As a jeweler for the ASCII Gemstone Corporation, your job is inspect the newly acquired rubies and leave a note about any defects that you find.

Luckily, only 12 types of defects are possible, **and your supplier guarantees that no ruby will have more than one defect.**

The 12 defects correspond to the replacement of one of the 12 inner `_`, `/`, or `\` characters of the ruby with a space character (). The outer perimeter of a ruby never has defects.

The defects are numbered according to which inner character has a space in its place:

So a ruby with defect 1 looks like this:

```
  ___
 /\_/\
/_/  _\
\ \_/ /
 \/_\/

```

A ruby with defect 11 looks like this:

```
  ___
 /\_/\
/_/ \_\
\ \_/ /
 \ _\/

```

It's the same idea for all other defects.

# Challenge

Write a program or function that takes in the string of a single, potentially defective ruby. The defect number should be printed or returned. The defect number is 0 if there is no defect.

Take input from a text file, stdin, or a string function argument. Return the defect number or print it to stdout.

You may assume that the ruby has a trailing newline. You may **not** assume that it has any trailing spaces or leading newlines.

The shortest code in bytes wins. (Handy byte counter.)

### Test Cases

The 13 exact types of rubies, followed directly by their expected output:

```
  ___
 /\_/\
/_/ \_\
\ \_/ /
 \/_\/
0
  ___
 /\_/\
/_/  _\
\ \_/ /
 \/_\/
1
  ___
 /\ /\
/_/ \_\
\ \_/ /
 \/_\/
2
  ___
 /\_/\
/_  \_\
\ \_/ /
 \/_\/
3
  ___
 /\_/\
/_/ \_\
\  _/ /
 \/_\/
4
  ___
 /\_/\
/_/ \_\
\ \ / /
 \/_\/
5
  ___
 /\_/\
/_/ \_\
\ \_  /
 \/_\/
6
  ___
 /\_/\
/_/ \ \
\ \_/ /
 \/_\/
7
  ___
 /\_ \
/_/ \_\
\ \_/ /
 \/_\/
8
  ___
 / _/\
/_/ \_\
\ \_/ /
 \/_\/
9
  ___
 /\_/\
/ / \_\
\ \_/ /
 \/_\/
10
  ___
 /\_/\
/_/ \_\
\ \_/ /
 \ _\/
11
  ___
 /\_/\
/_/ \_\
\ \_/ /
 \/_ /
12

```

# Answer
> 13 votes
# CJam, ~~27~~ 23 bytes

```
F7EC5ZV4DI8G6]qBb67%J%#

```

Convert base 11, take mod 67, take mod 19 of the result then find the index of what you have in the array

```
[15, 7, 14, 12, 5, 3, 0, 4, 13, 18, 8, 16, 6]

```

Magic!

Try it online.

# Answer
> 35 votes
## Ruby 2.0, 69 bytes

```
#!ruby -Kn0rdigest
p'×ñF<ìX‚É²Ÿ_'.index Digest::MD5.digest(gets)[0]

```

Hexdump (to faithfully show the binary data in the string):

```
00000000  23 21 72 75 62 79 20 2d  4b 6e 30 72 64 69 67 65  |#!ruby -Kn0rdige|
00000010  73 74 0a 70 27 d7 f1 46  3c 1f ec 58 82 c9 b2 9f  |st.p'..F<..X....|
00000020  5f 02 27 2e 69 6e 64 65  78 20 44 69 67 65 73 74  |_.'.index Digest|
00000030  3a 3a 4d 44 35 2e 64 69  67 65 73 74 28 67 65 74  |::MD5.digest(get|
00000040  73 29 5b 30 5d                                    |s)[0]|

```

Explanation:

1. The `-Kn` option reads the source file as `ASCII-8BIT` (binary).
2. The `-0` option allows `gets` to read in the whole input (and not just one line).
3. The `-rdigest` option loads the `digest` module, which provides `Digest::MD5`.
4. The code then does an MD5 of the input, takes the first byte of the digest, and gets its index in the given binary string.

# Answer
> 7 votes
# Julia, ~~90~~ 59 bytes

Definitely not the shortest, but the fair maiden Julia takes great care in the inspection of the royal rubies.

```
s->search(s[vec([18 10 16 24 25 26 19 11 9 15 32 34])],' ')

```

This creates a lambda function which accepts a string `s` and returns the corresponding ruby defect number. To call it, give it a name, e.g. `f=s->...`.

Ungolfed + explanation:

```
function f(s)
    # Strings can be indexed like arrays, so we can define d to
    # be a vector of indices corresponding to potential defect
    # locations

    d = vec([18 10 16 24 25 26 19 11 9 15 32 34])

    # Check the specified locations for defects, returning the
    # defect number as the index where a space was found and
    # was not expected. If no spaces are found, 0 is returned.

    search(s[d], ' ')
end

```

Examples:

```
julia> f("  ___
 /\\ /\\
/_/ \\_\\
\\ \\_/ \/
 \\/_\\/")
2

julia> f("  ___
 /\\_/\\
/_/ \\_\\
\\ \\_/ \/
 \\/_\\/")
0

```

Note that backslashes have to be escaped in the input. I confirmed with @Calvin'sHobbies that it's okay.

Let me know if you have any questions or suggestions!

---

**Edit:** Saved 31 bytes with help from Andrew Piliser!

# Answer
> 7 votes
# \>\<\> (Fish), 177 bytes

This is a long but unique solution. The program contains **no arithmetic or branching** apart from inserting input characters into fixed places in the code.

Notice that all the inspected ruby-building characters (`/ \ _`) can be "mirrors" in the \>\<\> code that change the direction of the instruction pointer (IP).

We can use these input characters to build a maze from them with the code-modifying instruction `p` and at every exit (which created by a missing mirror in the input) we can print the corresponding number.

```
iiiiiiiii19pi1cpi18piiii2bpi27pii28pi3apiiiii37pi49pi36piiiii00pi45pii46p

    ;
   ;n
  ;nb
 ;n6S    0n;
 n3SB   cn;
 8SB!  4n;
 SB!  1n;
>B! U9n;
 ! U5
  U7n
 Uan;
 2n;
 n;
 ;

```

The `S B U` letters are the ones changed to `/ \ _` respectively. If the input is a full ruby the final code becomes:

```
\iiiiiiii19pi1cpi18piiii2bpi27pii28pi3apiiiii37pi49pi36piiiii00pi45pii46p

    ;
   ;n
  ;nb
 ;n6/    0n;
 n3/\   cn;
 8/\!  4n;
 /\!  1n;
>\! _9n;
 ! _5
  _7n
 _an;
 2n;
 n;
 ;

```

You can try out the program with this great online visual interpreter. As you can't input newlines there you have to use some dummy characters instead so you can input a full ruby as e.g. `SS___LS/\_/\L/_/S\_\L\S\_/S/LS\/_\/`. (Spaces also changed to S's because of markdown.)

# Answer
> 5 votes
# CJam, ~~41 31 29~~ 28 bytes

```
"-RI)11a!"q103b1e3%A/c#

```

As usual, for non printable characters, follow this link.

Try it online here

Explanation soon

---

Previous approach:

Pretty sure this can be reduced by changing the digits/conversion logic. But here goes the first attempt:

```
"<KJ[]\"O=":iqN-"/\\_ "4,er4b1e3%A/#

```

As usual, use this link for unprintable characters.

The logic is pretty simple

* `"Hash for each defect":i` \- This gets me the hash per defect as the index
* `qN-"/\\_ "4,er` \- this converts the characters to numbers
* `4b1e3%A/` \- this is the unique number in the base converted number
* `#` Then I simply find the index of the unique number in the hash

Try it online here

# Answer
> 4 votes
# JavaScript (ES6), 67 ~~72~~

Simply looks for blanks in the given 12 locations

**Edit** Saved 5 bytes, thx @apsillers

```
F=b=>[..."0h9fnopia8evx"].map((v,i)=>b[parseInt(v,34)]>' '?0:d=i)|d

```

**Test** In Firefox / FireBug console

```
x='  ___\n /\\_/\\\n/_/ \\_\\\n\\ \\_/ /\n \\/_\\/' // no defects
;[...x].forEach((c,p,a)=>{
  a[p]=' ' // put a blank
  y=a.join('') // rebuild a string
  d=F(y) // check
  if (d) console.log('\n'+y+'\n'+d) // if defect, output
  a[p]=c // remove the blamk
})

```

*Output*

```
  ___
 / _/\
/_/ \_\
\ \_/ /
 \/_\/
9

  ___
 /\ /\
/_/ \_\
\ \_/ /
 \/_\/
2

  ___
 /\_ \
/_/ \_\
\ \_/ /
 \/_\/
8

  ___
 /\_/\
/ / \_\
\ \_/ /
 \/_\/
10

  ___
 /\_/\
/_  \_\
\ \_/ /
 \/_\/
3

  ___
 /\_/\
/_/  _\
\ \_/ /
 \/_\/
1

  ___
 /\_/\
/_/ \ \
\ \_/ /
 \/_\/
7

  ___
 /\_/\
/_/ \_\
\  _/ /
 \/_\/
4

  ___
 /\_/\
/_/ \_\
\ \ / /
 \/_\/
5

  ___
 /\_/\
/_/ \_\
\ \_  /
 \/_\/
6

  ___
 /\_/\
/_/ \_\
\ \_/ /
 \ _\/
11

  ___
 /\_/\
/_/ \_\
\ \_/ /
 \/_ /
12

```

# Answer
> 4 votes
# Slip, ~~123~~ 108 + 3 = 111 bytes

```
^6 (`\\`_.?<?.?[ _]?|`_(`\.?(<.?|>)|`/.?.?>.?.?).?)| `_(`\.?<.?>?.?.?|`/(.?>.?.?.?|<`_))| `/\`_.?(.<.?>?.?)?

```

Run with the `n` and `o` flags, i.e.

```
py -3 slip.py regex.txt input.txt no

```

Alternatively, try it online.

---

Slip is a regex-like language which was made as part of the 2D pattern matching challenge. Slip can detect the location of a defect with the `p` position flag via the following program:

```
^6? `_[/\]|( `/|^6 `\)\`_

```

which looks for one of the following patterns (here `S` denotes here the match starts):

```
S_/    S_\    /_S    \_S    S/      _
                              _      \S

```

Try it online — coordinates are outputted as an (x, y) pair. Everything reads like a normal regex, except that:

* ``` is used for escaping,
* `<>` turn the match pointer left/right respectively,
* `^6` sets the match pointer to face leftward, and
* `\` slips the match pointer orthogonally to the right (e.g. if the pointer's facing rightward then it goes down a row)

But unfortunately, what we need is a single number from 0 to 12 saying *which* defect was detected, not *where* it was detected. Slip only has one method of outputting a single number — the `n` flag which outputs the number of matches found.

So to do this we expand the above regex to match the correct number of times for each defect, with the help of the `o` overlapping match mode. Broken down, the components are:

```
1 11:    `_`\.?<.?>?.?.?
2 10:    `/\`_.?(.<.?>?.?)?
4 9:     `_`/(.?>.?.?.?|<`_)
3 12:   ^6 `_`/.?.?>.?.?.?
5 7:    ^6 `\\`_.?<?.?[ _]?
6 8:    ^6 `_`\.?(<.?|>).?

```

Yes, that's an exccessive use of `?` to get the numbers right :P

# Answer
> 2 votes
# Python 2, ~~146~~ ~~88~~ ~~86~~ 71 bytes

The function `f` tests each segment location and returns the index of the defect segment. A test on the first byte in the input string ensures that we return `0` if no defects are found.

We now pack the segment offsets into a compact string and use `ord()` to recover them:

```
f=lambda s:sum(n*(s[ord('ARJPXYZSKIO`b'[n])-65]<'!')for n in range(13))

```

Testing with a perfect ruby:

```
f('  ___\n /\\_/\\\n/_/ \\_\\\n\\ \\_/ /\n \\/_\\/')
0

```

Testing with segment 2 replaced by a space:

```
f('  ___\n /\\ /\\\n/_/ \\_\\\n\\ \\_/ /\n \\/_\\/')
2

```

*EDIT: Thanks to @xnor for the nice `sum(n*bool for n in...)` technique.*

*EDIT2: Thanks to @Sp3000 for extra golfing tips.*

# Answer
> 2 votes
# C, ~~98~~ 84 bytes

```
g(char*b){char*c="/'-5670(&,=?",*a=c;for(;*c&&!(*b=b[*c++-30]-32?0:c-a););return*b;}

```

UPDATE: A tad bit more clever about the string, and fixed an issue with non-defected rubies.

Unraveled:

```
g(char*b){
    char*c="/'-5670(&,=?",*a=c;
    for(;*c&&!(*b=b[*c++-30]-32?0:c-a);)
        ;
    return*b;
}

```

Quite straightforward, and *just* under 100 bytes.

For testing:

```
#include "stdio.h"
int main() {
    char b[100];
    scanf("%35c", b);
    printf("%d\n", g(b));
    return 0;
}

```

Input to STDIN.

# How it works

Each defect in the ruby is located at a different character. This list shows where each defect occurs in the input string:

```
Defect 1: 17
Defect 2: 9
Defect 3: 15
Defect 4: 23
Defect 5: 24
Defect 6: 25
Defect 7: 18
Defect 8: 10
Defect 9: 8
Defect 10: 14
Defect 11: 31
Defect 12: 33

```

Since making an array of `{17,9,15,23,24,25,18,10,8,14,31,33}` costs a lot of bytes, we find a shorter way to create this list. Observe that adding 30 to each number results in a list of integers that could be represented as printable ASCII characters. This list is as follows: `"/'-5670(&,=?"`. Thus, we can set a character array (in the code, `c`) to this string, and simply subtract 30 from every value we retrieve from this list to get our original array of integers. We define `a` to be equal to `c` for keeping track of how far along the list we have gotten. The only thing left in the code is the `for` loop. It checks to make sure we have not hit the end of `c` yet, and then checks if the character of `b` at the current `c` is a space(ASCII 32). If it is, we set the first, unused element of `b` to the defect number and return it.

# Answer
> 1 votes
# Pyth, 35 31 28 bytes

```
hx"*6#,54@"C%imCds.zT67

```

Requires a patched Pyth, the current latest version of Pyth has a bug in `.z` that strips off trailing characters.

This version doesn't use a hash function, it abuses the base conversion function in Pyth to compute a very stupid, but working hash. Then we convert that hash to a character and look its index up in a string.

The answer contains unprintable characters, use this Python3 code to generate the program accurately on your machine:

```
garbage = [42, 22, 54, 35, 44, 28, 31, 53, 52, 64, 16, 11]
prg = 'hx"' + "".join(chr(c) for c in garbage) +'"C%imCds.zT67'
open("golf_gen.pyth", "w").write(prg)
print(len(prg))

```

# Answer
> 1 votes
# Haskell, 73 bytes

```
f l=last[x|x<-[0..12],l!!([0,17,9,15,23,24,25,18,10,8,14,31,33]!!x)==' ']

```

Same strategy as many other solutions: looking for spaces at the given locations. The lookup returns a list of indices from which I take the last element, because there is always a hit for index 0.

# Answer
> 0 votes
# 05AB1E, 16 bytes

```
•W)Ì3ô;4(•₆вèðk>

```

Try it online or verify all test cases.

**Explanation:**

```
•W)Ì3ô;4(•        # Push compressed integer 2272064612422082397
          ₆в      # Converted to Base-36 as list: [17,9,15,23,24,25,18,10,8,14,31,33]
            è     # Index each into the (implicit) input-string
             ðk   # Get the 0-based index of the first space in the indexed characters
                  # (-1 if not found, which means the ruby had no defects)
               >  # And increase it by 1 (which is output implicitly as result)

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand why `•W)Ì3ô;4(•` is `2272064612422082397` and `•W)Ì3ô;4(•₆в` is `[17,9,15,23,24,25,18,10,8,14,31,33]`.

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


# Question
Title: The Partition Problem - Sorting Stacks of Boxes
Just last night I was reading a book which had a chapter on the Partition Problem; the Partition Problem is basically about splitting a set of numbers into two smaller sets of equal size.

To visualize it, the book contained the following picture:

It shows how, given an input of *k* boxes, each with height *n*, you can create two stacks of boxes, each stack with half the height of the original stack (well, in this diagram, pile.)

If you were to write a function to do this, it might look something like:

```
>>> k = [3,4,3,1,2,3,3,2,1]
[3,4,3,1,2,3,3,2,1]

>>> partitionSolve(k)
[ [3,3,2,3], [1,4,2,3,1] ]

>>> sum(partitionSolve(k)[0]) == sum(partitionSolve(k)[1])
True

```

But this only solves for two stacks! What if we wanted to split the input into three equal stacks? Then we'd have to write another function!

```
>>> partitionSolveThree([3,4,3,1,2,3,3,2])
[ [3,4], [3,1,3], [2,3,2] ]

```

In fact, I want to be able to solve for *N* stacks:

```
>>> partitionSolveN(3, [2,1,1,2,3,1,2])
[ [2,2], [1,1,2], [3,1] ]

>>> partitionSolveN(4, [2,1,1,2,3,1,2])
[ [2,1], [1,2], [3], [1,2] ]

```

But, I'm lazy, and I don't want to have to start some language's shell every time I want to use this function, so I decide to create a program to do it for me.

The problem is, I can't figure out an efficient way to do it!

# Your Task

Design a program which can solve the above problem, for any number *N*.

Your program should take input via stdin, and print its output to stdout.

Example:

```
C:\> echo 2343123321| solution.X
3323
14231

```

Input will be a single string of digits; the first specifying how many stacks the code should be broken into, and the rest represent the input stack. All numbers will be single digit, so you can think of it as a list delimited by empty strings (`''`).

The first character of input will be the *N* to solve for, so if the first character is a 6 your program will be expected to output 6 valid subsets, or an error. This number will always be between 1 and 9.

The rest of the input is the starting list, from which the sublists must be created. Each digit in here can be between 1 and 9, and they must all be used once and only once in the outputted sublists.

Output should then be a new-line delimited list of your output stacks, each stack should just be a sequence of the numbers within it.

Another few examples:

```
C:\> echo 334323321| solution.X
34
313
232

C:\> echo 3912743471352| solution.X
121372
97
4453

C:\> echo 92| solution.X
forty-two

```

If the given input has no solution, your program can print any error message it wants, as long as there are no digits in the error message.

Fewest number of bytes wins! Good luck!

# Answer
# Python 2, ~~321~~ ~~317~~ ~~321~~ 319

```
import itertools as l
t=raw_input();e=0;g=l.permutations(int(k)for k in t[1:])
try:
 while not e:
  a=list(g.next());c=[sum(a[:i+1])for i in range(len(a))];s=c[-1];d=int(t[0]);f=s/d;assert f*d==s;r=range(f,s,f);e=set(r)<=set(c);b=[`k`for k in a]
 for k in r[::-1]:b.insert(c.index(k)+1,'\n')
 print ''.join(b)
except:''

```

Some examples:

```
echo 43 | python part.py

echo 3912743471352 | python part.py
9124
7342
7135

echo 342137586 | python part.py
426
138
75

```

Thanks to theonlygusti for fixing the stdin input, and shaving off some chars and to Maltysen for pointing out a typo.
> 2 votes

# Answer
# Pyth - 73 69 bytes

**Updated to match Pyth 4.0**

Yay! Finally translated it. Likely huge room for golfing., but will be working on explanation. Finished explanation.

```
KmsdzJ.(KZFN*.pK.cUKtJ=km?:hNhdedgedZ>hNhdC,+]ZeN+eN]_1Iql{msdk1kB)EG

```

Uses brute force solution with a lot of help from itertools. Not really looking to golf any further because will be translating to Pyth.

```
from itertools import*
K=list(map(int,input()))
J=K.pop(0)
for N in product(permutations(K),combinations(range(len(K)),J-1)):
    k=[N[0][s:e]if e>=0 else N[0][s:]for s,e in zip((0,)+N[1],N[1]+(-1,))]
    d=list(map(sum,k))
    if d.count(d[0])==J:print(k);break
else:print()

```

It takes cartesian product to make all possible options of arrangements of input (uses perms) and all possible slices (uses combs). Then it checks and breaks on the first one and then prints.

```
K               K=
 m              Map
  sd            Convert to integer
  z             Over the input
J               J=
 .(             Pop from index
  K             K
  Z             Index zero
FN              For N in
 *              Cartesian Product
  .p            Permutations full length
   K            K
  .c            Combinations no replace
   UK           Of range(len(K))
   tJ           Length J-1
 =k             Set k=
  m             Map with d as loop var
   ?    gedZ    If d>=0 (hack to get around Pyth has no None slice index)
    :hN         Slice N[0]
     hd         From k[0]
     ed         Till k[-1]
    >hN         Else slice N[0]
     hd         From k[0] till end
   C,           Zip (This makes the partitioning index pairs)
    +]ZeN       [0]+N[-1]
    +en]_1      N[-1]+[-1] (Again, the -1 is for the hack)
  Iql{    1     If the set has len 1
      msdk      Map sum to k
   k            Implicitly print k
   B            Break and implicitly close out if
 )              Close out for loop
E               If we didn't break (Uses for-else construct in Python)
 G              Print alphabet as error message

```

Works on all the inputs, except it froze my computer on the really big one but should in theory.

**Note:** does not work on the online interpreter because it has a timeout.

Now the set thing give both a speed *and* bytes improvement so you can run it online: Try it here.
> 2 votes

# Answer
# Mathematica 154

```
f@n_:=Module[{g=IntegerDigits@n,d,a,r,s},d=First@g;a=Rest@g;
FirstCase[Subsets[Cases[Subsets@a,x_/;Tr@x==Tr@a/d],{d}],x_/;Sort[Join@@x]==Sort@a]];
f@Input[]

```

Standard input is entered by

```
f@Input[]

```

---

**Examples with predetermined inputs**:

```
f[334323321]

```

> {{3, 4}, {3, 3, 1}, {3, 2, 2}}

---

```
f[3912743471352]

```

> {{9, 7}, {7, 4, 5}, {1, 2, 4, 3, 1, 3, 2}}

---

```
f[342137586]

```

> {{4, 8}, {7, 5}, {2, 1, 3, 6}}

---

```
f[42112312]

```

> {{3}, {2, 1}, {2, 1}, {2, 1}}
> 1 votes

# Answer
# Pyth, 72 Bytes

Such a close byte count to the other Pyth, but a completely different approach.

```
KmvdzJ.(K0=H/sKJ=KSK=JlKWK=NK=G])Fd_NIgHs+dGaG.(KxKdIqHsGaYGB;?YqJsmldYb

```

Try it here.

It is roughly equal to the following program, which was made through rethinking and slimming down my last answer (my last program didn't guarantee an answer):

### Python 2, 242 Bytes

```
x=list(map(int,raw_input()))
y,S,b=x.pop(0),sum,[]
x.sort(reverse=1)
j,z,c=S(x)/y,len(x),0
while x:
 k,a=x[:],[]
 for i in k:
  if j>=S(a)+i:a.append(x.pop(x.index(i)))
 if S(a)==j:b.append(a);c+=len(a)
if c==z:
 for o in b:print o
else:print

```

---

### Basic idea for solving without using permutations

* Each stack must add up to `k = sum of all boxes / n`
* When the list of all boxes is sorted from greatest to least, you can iterate over that list, adding/popping boxes to a stack so that `k >= stack` remains true. Once `stack == k`, that stack is 'finished' and can be added to a list of the solutions. It is clear why this works when you examine the solution it produces:

```
input: 3912643473522
output: [[9, 7], [6, 5, 4, 1], [4, 3, 3, 2, 2, 2]]

```
* At the end, check if `# of boxes in all solution stacks == length of input - 1` to see if all boxes were used, if not the input has no solution.
> 0 votes

# Answer
# 05AB1E, 11 bytes

```
ć.Œʒ€SOË}н»

```

Try it online or verify all test cases.

**Explanation:**

```
ć            # Extract the head of the (implicit) input;
             # pushing remainder and head separately to the stack
             #  i.e. 2341 → 341 and 2
 .Œ          # Get all possible combinations of head amount of parts from the remainder
             #  → [[341,""],[34,1],[31,4],[3,41],[41,3],[4,31],[1,34],["",341]]
   ʒ         # Filter this list of parts by:
    €S       #  Convert the two parts to lists of digits
             #   i.e. [341,""] → [[3,4,1],[]]
             #   i.e. [31,4] → [[3,1],[4]]
      O      #  Take the sum of each digit-list
             #   → [8,0]
             #   → [4,4]
       Ë     #  Check if both are equal
             #   → 0 (falsey)
             #   → 1 (truthy)
        }н   # After the filter: leave the first result
             #  i.e. [[31,4],[4,31]] → [31,4]
          »  # Join it by newlines (which is output implicitly as result)
             #  → "31\n4"

```

If a list was allowed as output, it could have been **9 bytes** instead:

```
ć.Œ.Δ€SOË

```

Try it online or verify all test cases.

Where the  is a builtin for find\_first, (which could have been used in the original 11-byter as well for the same byte-count, but filter `ʒ` with leave first `н` apparently is slightly faster for the given test cases).
> 0 votes

---
Tags: code-golf, set-partitions
---


title: Randomised list, formatted nicely

text:
# Question
Title: Randomised list, formatted nicely
# Challenge

### Task

Given a number `N`, output 2 NxN squares; each line of each square is a random permutation of \[0, N); the squares are separated by a newline

### Rules

* Produce a randomised list of length `N`, separated by space
* Repeat this N\*2 times
* Separate each output with a newline, with 2 newlines at the midpoint
* The value of `n` must be "obvious", you can get it via stdin; argument; whatever, but there must be a distinct value somewhere, so the value of `n` can't just be scattered across your program.

### Example

Given `n = 4`, the output could be:

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

0 3 2 1
3 1 0 2
0 1 3 2
0 2 1 3

```

Lowest number of bytes wins

# Answer
# J, ~~9~~ 7 bytes

Thanks to @randomra for shaving off two characters:

```
?~2&,]

```

Previously I had:

```
?~($~2&,)

```

These are functions, you can apply them to an argument directly or store them in a variable and then use them:

```
   (?~2&,$]) 5
1 0 4 2 3
2 4 0 3 1
2 3 1 0 4
2 3 0 1 4
3 0 1 4 2

1 4 0 2 3
2 1 4 3 0
2 3 1 0 4
2 3 1 4 0
0 1 2 3 4

   f=.?~2&,$]
   f 5
4 2 3 0 1
3 4 1 0 2
3 4 0 2 1
1 2 4 3 0
2 0 4 1 3

2 1 3 0 4
1 3 4 2 0
2 4 1 3 0
3 2 1 0 4
3 0 4 2 1

```
> 9 votes

# Answer
# Pyth, 13

```
V2VQjdoOQUQ)k

```

Pretty simple program, I believe it follows the spec.

Try it online here

Explanation:

```
                   : Q = eval(input)
V2                 : Do the next part twice
  VQ       )       : Do the stuff before the ) Q times
    jd             : Join the resulting list on spaces
      oOQUQ        : order range(Q) by random_int( from 0 to Q )
            k      : print nothing (pyth auto-pads each print with a newline)

```
> 4 votes

# Answer
# R, ~~73~~ ~~71~~ ~~66~~ ~~62~~ 54

I feel there should be a better way, but at the moment

```
n=5;for(i in 1:(n*2))cat(sample(n)-1,rep('\n',1+!i-n))

```

Edit: Replace rank(runif(1:n))-1 with sample(1:n)-1. Used rep instead of if. Thanks to Alex A for a few more.

Test run

```
> n=5;for(i in 1:(n*2))cat(sample(n)-1,rep('\n',1+!i-n))
0 3 1 2 4
0 1 4 2 3
2 3 4 0 1
4 1 0 2 3
1 0 3 4 2

4 3 1 0 2
3 0 1 2 4
4 2 3 1 0
4 2 1 0 3
3 1 0 2 4

```
> 3 votes

# Answer
# CJam, 22 bytes

```
l~{_{_,mrS*N@}*N\}2*;;

```

Input via STDIN. I feel like there must be a much way to do this.

Test it here.
> 2 votes

# Answer
# Bash+coreutils, 61

Input as a command-line arg.

```
seq -f"((%g))&&echo \`seq 0 $[$1-1]|shuf\`||echo" -$1 $1|bash

```
> 2 votes

# Answer
# CJam, 20 19 bytes

```
ri_a*0+2*{,mrS*}%N*

```

Try it here (for Firefox).

Other solutions:

```
{T,mrS*N}_ri:T*N](T*
"T,mrS*N"ri:T*:F~NF~
LN]"T,mrS*N"ri:T*f{~}

```
> 2 votes

# Answer
# Java, ~~190~~ 187 bytes

```
void f(int n){int k=0,i,t,x,o[]=new int[n];for(;k<n;o[k]=k++);for(k=0;k++<n*2;)for(i=n;i>0;t=o[x*=Math.random()],o[x]=o[i],o[i]=t,System.out.print(o[i]+(i>0?" ":k==n?"\n\n":"\n")))x=i--;}

```

Clunky, but it does the job (that's Java's motto, right?). Pretty simplistic: it fills an array, then repeatedly uses my earlier Fisher-Yates to shuffle and print. I tried using `Collections.shuffle()` instead, but it was a touch longer once you add in the import.

Ah well, such is life.

With line breaks:

```
void f(int n){
    int k=0,i,t,x,o[]=new int[n];
    for(;k<n;o[k]=k++);
    for(k=0;k++<n*2;)
        for(i=n;
            i>0;
            t=o[x*=Math.random()],
            o[x]=o[i],
            o[i]=t,
            System.out.print(o[i]+(i>0?" ":k==n?"\n\n":"\n"))
        )
            x=i--;
}

```
> 2 votes

# Answer
## Clip, 29

```
[zjm[ Jm[ jkwRRzwS}Rz}R2:2N]n

```

Takes input from STDIN.

```
[z                         ]n  .- z is the numeric value of the input -.
  j                     :2N    .- join with two newlines              -.
   m[                }R2       .- do twice                            -.
      J                        .- join with a newline                 -.
       m[         }Rz          .- do z times                          -.
          j     wS             .- join with spaces                    -.
           kw                  .- wrap each number                    -.
             R                 .- shuffle                             -.
              Rz               .- list of the first z numbers         -.

```

Example run:

```
> java -jar clip4.jar random.clip
4
2 1 0 3
3 1 2 0
1 0 2 3
3 1 0 2

3 0 1 2
0 1 2 3
3 2 0 1
0 1 3 2

```
> 2 votes

# Answer
# Python 3, 90 bytes

```
from random import*
def f(n):S="*L,=range(n);shuffle(L);print(*L);"*n;exec(S+"print();"+S)

```

I'm sure there's a better method for handling the newline break in between, but I'm having trouble coming up with a way.
> 2 votes

# Answer
# Python - 139 138 bytes

```
import random as r
n=4
s=range
t=s(0,4)
print('\n\n'.join('\n'.join(' '.join('%d'%i for i in r.sample(t,n)) for j in t) for k in s(0,2)))

```

EDIT: Knocked off a byte
> 1 votes

# Answer
```
import static java.lang.System.out;public class A{public static void main(String[]a){int n=Integer.decode(a[0]);for(int x=0;x<2;x++){for(int i=0;i<n;i++){java.util.stream.IntStream.range(0,n).parallel().forEach(k->out.print(k+" "));out.println();}out.println();}}}

```

As short as I could manage in Java - 265 bytes.

It takes an ordered stream of n integers and concurrently prints them separated by a space, so the output order is non-deterministic and it does this per line.

EDIT:

If done as only a function:

```
void g(int n){for(int x=0,i=0;x<2;x++){for(;i<n;i++){java.util.stream.IntStream.range(0,10).parallel().forEach(k->out.print(k+" "));System.out.println();}System.out.println();}}}}}

```

This is 179 bytes; the ordering may not seem very random - but as far as I'm aware it is quite non-deterministic.
> 1 votes

# Answer
# PHP, 109

```
$n=4;$p=range(0,$n-1);for($k=0;$k<2;$k++){for($i=0;$i<$n;$i++){shuffle($p);echo join(' ',$p)."\n";}echo"\n";}

```

New implemented solution uses 1 more bytes. But now fulfill OP requirement.

Old solution which do not randomize permutation of line.

# PHP, 108

```
$n=4;for($k=0;$k<2;$k++){for($i=0;$i<$n;$i++){for($j=0;$j<$n;$j++)echo rand(0,$n-1)." ";echo"\n";}echo"\n";}

```
> 1 votes

# Answer
# Rebol - ~~76~~ 75

```
N: 4 do b:[loop N[print random collect[repeat i N[keep i - 1]]]]print""do b

```

Ungolfed:

```
N: 4

do b: [
    loop N [
        print random collect [
            repeat i N [keep i - 1]
        ]
    ]
]

print ""
do b

```
> 1 votes

# Answer
# PHP (106 bytes):

This one was quite unexpectedly hard.

But here is a somewhat large solution:

```
<?for(;3>$j++;$o='',$z=range(0,($i=$n=$_GET[n])-1)){for(;$i--;shuffle($z))$o.=join(' ',$z)."
";echo"$o
";}

```

This can be rewritten to Javascript quite 'easily'.

For this to work, you must access the file over an http server, with `?n=<number>` appended to the name.
> 0 votes

# Answer
# Ruby - 69

```
r=->(n){[0,0].map{(1..n).map{(0..n-1).to_a.shuffle*" "}*"\n"}*"\n\n"}

```

Sample output:

```
puts r[5]

```

yields:

```
3 0 2 1 4
0 4 1 3 2
2 1 0 4 3
0 4 2 1 3
4 1 2 3 0

4 0 3 2 1
3 1 0 2 4
3 4 0 2 1
0 2 3 4 1
3 2 4 0 1

```

and

```
puts r[7]

```

yields

```
5 4 0 6 1 3 2
6 3 1 2 4 0 5
5 2 1 0 6 4 3
4 0 5 2 3 1 6
0 6 3 1 4 5 2
6 3 0 2 5 1 4
2 4 1 0 6 5 3

0 1 4 3 6 5 2
3 5 4 2 6 1 0
2 3 5 1 4 6 0
3 0 5 2 1 4 6
4 6 5 0 2 3 1
6 5 3 2 0 4 1
3 4 6 1 0 5 2

```
> 0 votes

# Answer
# Scala, 105 98 95 84 bytes

```
(n:Int)=>{def s=0.until(n).permutations take n map(_ mkString " ") mkString "\n";s+"\n\n"+s}

```

### Ungolfed

```
def squares(n: Int): String = {
  def square(n: Int): String = 0.until(n).permutations.take(n).map(_.mkString(" ")).mkString("\n")
  square(n)+"\n\n"+square(n)
}

```
> 0 votes

# Answer
## C++ 201

```
void f(int n)
{
std::vector<int> v;int N=n;
while(n--)v.push_back(n);
for(int i=0;i<2*N+1;i++)
{
random_shuffle(v.begin(),v.end());
if(!(i==N))for(int j=0;j<N;j++)printf("%d ",v.at(j));
else puts("");
puts("");
}
}

```
> 0 votes

# Answer
# 05AB1E, 13 bytes

```
2FFL<.rðý,}¶?

```

Try it online.

Or alternatively:

```
·FIL<.r})»2ä»

```

Try it online.

**Explanation:**

```
2F          # Loop 2 times:
  F         #  Inner loop the (implicit) input amount of times:
   L<       #   Push a list in the range [0, (implicit) input-1]
     .r     #   Randomly shuffle it
       ðý   #   Join it by spaces
         ,  #   Pop and output it with trailing newline
  }¶?       #  After the inner-loop is done: print a newline

·           # Double the (implicit) input
 F          # Loop that many times:
  IL<       #  Push a list in the range [0, input-1]
     .r     #  Randomly shuffle it
 })         # After the loop: wrap everything on the stack into a list
   »        # Join each inner list by spaces, and then each string by newlines
    2ä      # Split it into a list of two equal-sized strings
      »     # And join those by newlines as well (which is output implicitly as result)

```

If a leading instead of trailing newline is allowed, the first version could be `2F¶?FL<.rðý,` instead, to save a byte on the `}`: Try it online.
> 0 votes

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


title: Roots of Arbitrary Numbers

text:
# Question
Title: Roots of Arbitrary Numbers
One day, when I was bored in maths class, I learned of a neat trick for solving the real cube root of a number!

Let's use the number \\$79,507\\$ as an example.

First, take digit in the one's place and compare it to this table:

\begin{array} {|r|r|} \hline \text{Extracted Digit} &\text{Resulting Digit} \\ \hline \text{1} &\text{1} \\ \text{2} &\text{8} \\ \text{3} &\text{7} \\ \text{4} &\text{4} \\ \text{5} &\text{5} \\ \text{6} &\text{6} \\ \text{7} &\text{3} \\ \text{8} &\text{2} \\ \text{9} &\text{9} \\ \text{0} &\text{0} \\ \hline \end{array}

In this example, the `Resulting Digit` will be \\$3\\$ since the extracted digit is \\$7\\$.

Next, remove all digits that are less than \\$10^3\\$:

$$ 79507 → 79 $$

Then, find the largest perfect cube that does not exceed the input:

$$ 64 \< 79 $$

\\$64=4^3\\$, thus the next digit needed is \\$4\\$.

Finally, multiply the digit found in the previous step by \\$10\\$ and add the `Resulting Digit` found in the first step:

$$ 10\*4+3=43 $$

Thus, the cube root of \\$79,507\\$ equals \\$43\\$.

***However***, there a neat quirk about this trick: it doesn't apply to *only* cubed numbers. In fact, it works with all \\$n\>1\\$ where \\$n\bmod2\ne0\\$.

The steps mentioned above can be summed up in this generalization for an \\$n\\$ power:

* Step 1) Take the digit in the one's place in the input. Compare it to the one's place digit of the \\$n\\$th powers of \\$1\\$ to \\$10\\$, then use the corresponding digit.
* Step 2) Remove all digits of the input less than \\$10^n\\$. Compare the resulting number to the perfect powers definied in *Step 1*. Use the \\$n\\$th root of the largest perfect power less than said number. (Largest perfect power can exceed \\$10^n\\$)
* Step 3) Multiply the number from *Step 2* by 10 then add the number from *Step 1*. This will be the final result.

# Task

Given two positive integers \\$n\\$ and \\$m\\$, return the \\$n\\$th root of \\$m\\$.

**Input:**

* Two positive integers \\$n\\$ and \\$m\\$.
* \\$m\\$ is guaranteed to be a perfect \\$n\\$th power of an integer.
* \\$n\\$ is guaranteed to be odd and greater than \\$2\\$. (This method doesn't work if \\$n\\$ is even.)

**Output:**

* The values calculated in steps 1 and 2.
* The \\$n\\$th root of \\$m\\$.
* Output can be on multiples lines or a list, whichever is more convenient.

**Rules:**

* This is , so the fewer bytes, the better!
* Standard I/O rules apply.
* The output ***must*** be calculated using the aforementioned method.
* No builtins allowed that already calculate this. A prime example being TI-BASIC's x√ command.

**Examples:**

```
Input      | Output
-------------------
3, 79507   | 3
           | 4
           | 43
3, 79507   | [3, 4, 43]
5, 4084101 | 1
           | 2
           | 21
5, 4084101 | [1, 2, 21]

```

# Answer
# 05AB1E, 18 bytes

Saved 1 byte thanks to *Kevin Cruijssen*

```
mθ=²¹°÷DÝ¹m@O<=ìï=

```

Try it online!
> 3 votes

# Answer
# JavaScript (ES7),  ~~58~~  56 bytes

*Saved ~~11~~ many bytes thanks to @Emigna*

Takes input as `(m)(n)`. Returns the 2 intermediate values and the final result as an array.

```
m=>g=(n,k)=>k**n>m/10**n?[u=m**n%10,--k,k*10+u]:g(n,-~k)

```

Try it online!

---

# JavaScript (Node.js), 62 bytes

This version uses BigInts as I/O to support larger inputs.

```
m=>g=(n,k=0n)=>k**n>m/10n**n?[u=m**n%10n,--k,k*10n+u]:g(n,++k)

```

Try it online!
> 2 votes

# Answer
# , 74 bytes

```
function(m,n)c(a<-match(m%%10,(1:9)^n%%10,0),b<-(m/10^n)^(1/n)%/%1,a+10*b)

```

Try it online!

`match(m%%10,(1:9)^n%%10,0)` compares the last digit of `m` to the reference table (and outputs `0` if no match is found), thus performing step 1.

`(m/10^n)^(1/n)%/%1` gives the output of step 2.
> 1 votes

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


title: 9erilous 9ermutations

text:
# Question
Title: 9erilous 9ermutations
Note: This is an attempt at recycling guest271314's permutation question(s)

There's an interesting pattern that forms when you find the differences between lexographically sorted permutations of base 10 numbers with ascending unique digits. For example, `123` has permutations:

```
123 132 213 231 312 321

```

When you find the differences between these, you get the sequence

```
9 81 18 81 9

```

Which are all divisible by nine (because of the digit sum of base 10 numbers), as well as being palindromic.

Notably, if we use the next number up, `1234`, we get the sequence

```
9 81 18 81 9 702 9 171 27 72 18 693 18 72 27 171 9 702 9 81 18 81 9

```

Which extends the previous sequence while remaining palindromic around \\$693\\$. This pattern always holds, even when you start using more that `10` numbers, though the length of the sequence is \\$n!-1\\$ for \\$n\\$ numbers. Note that to use numbers above `0 to 9`, we don't change to a different base, we just multiply the number by \\$10^x\\$, e.g. \\$ \[1,12,11\]\_{10} = 1\*10^2 + 12\*10^1 + 11\*10^0 = 231\\$.

Your goal is to implement this sequence, by returning each element as a multiple of nine. For example, the first 23 elements of this sequence are:

```
1 9 2 9 1 78 1 19 3 8 2 77 2 8 3 19 1 78 1 9 2 9 1

```

Some other test cases (0 indexed):

```
23     => 657
119    => 5336
719    => 41015
5039   => 286694
40319  => 1632373
362879 => 3978052
100    => 1
1000   => 4
10000  => 3
100000 => 3

```

### Rules:

* The submission can be any of:
    + A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.
    + A program/function that takes a number \\$n\\$ and returns up to the \\$n\\$th index, either 0 or 1 indexed.
    + A program/function that outputs/returns the sequence infinitely.
* The program should be capable of theoretically handling up to the \\$11!-1\\$th element and beyond, though I understand if time/memory constraints make this fail. In particular, this means you cannot concatenate the digits and evaluate as base 10, since something like \\$012345678910\\$ would be wrong.
* This is , so the shortest implementation for each language wins!

### Notes:

* This is OEIS A217626
* I am offering a bounty of 500 for a solution that works out the elements directly without calculating the actual permutations.
* The sequence works for any contiguous digits. For example, the differences between the permutations of \\$ \[1,2,3,4\]\_{10} \\$ are the same as for \\$\[-4,-3,-2,-1\]\_{10}\\$.

# Answer
# Jelly, 9 bytes

```
,‘œ?ŻḌI÷9

```

Try it online! (print the n'th element)

Try it online! (20 first elements)

Explanation:

```
      I÷9      Compute the difference divided by 9 between
 ‘             the (n+1)th
  œ?           permutation
,              and
               the (n)th
  œ?           permutation
    Ż          of [0,1,2,...n]
     Ḍ         converted to decimal.

```

(Jelly has the builtin `œ?` which computes the `n`th permutation of a list in approximately linear time. Quite useful.)
> 5 votes

# Answer
# Charcoal, 71 bytes

```
≔⟦Ｎ⊕θ⟧ηＷ⌈η≧÷Ｌ⊞ＯυＥη﹪κ⊕Ｌυη≔⁰δＦ²«≔Ｅυλζ≔⟦⟧ηＦ⮌Ｅυ§κι«⊞η§ζκ≔Φζ⁻μκζ»≦⁻↨ηχδ»Ｉ÷δ⁹

```

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

```
≔⟦Ｎ⊕θ⟧η

```

Get a list containing the input and one more than the input.

```
Ｗ⌈η

```

Repeat until both values are zero.

```
≧÷Ｌ⊞ＯυＥη﹪κ⊕Ｌυη

```

Perform factorial base conversion on both values. This is the first time I've actually used  on a list!

```
≔⁰δ

```

Clear the result.

```
Ｆ²«

```

Loop over each factorial base number.

```
≔Ｅυλζ

```

Make a list of the digits from 0 to length - 1.

```
≔⟦⟧η

```

Initialise the result to an empty list.

```
Ｆ⮌Ｅυ§κι«

```

Loop over the digits of the factorial base number.

```
⊞η§ζκ

```

Add the next permutation digit to the result.

```
≔Φζ⁻μκζ»

```

Remove that digit from the list.

```
≦⁻↨ηχδ»

```

Convert the permutation as a base 10 number and subtract the result so far from it.

```
Ｉ÷δ⁹

```

Divide the final result by 9 and cast to string.
> 4 votes

# Answer
# Perl 6, 82 bytes

*-2 bytes thanks to Jo King*

```
->\n{([-] map {$/=[^n];:10[map {|splice $/,$_,1},[R,] .polymod(1..n-2)]},n+1,n)/9}

```

Try it online!

0-indexed. Doesn't enumerate all permutations. Should theoretically work for all n, but bails out for n \> 65536 with "Too many arguments in flattening array".

The following **80 byte** version works for n up to 98!-2 and is a lot faster:

```
{([-] map {$/=[^99];:10[map {|splice $/,$_,1},[R,] .polymod(1..97)]},$_+1,$_)/9}

```

Try it online!

The following **53 byte** version should theoretically work for all n, but bails out for n \>= 20 with "refusing to permutate more than 20 elements".

```
{[-](map {:10[$_]},permutations(1..$_+1)[$_,$_-1])/9}

```

Try it online!
> 3 votes

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

```
n=>(F=_=>f>n?((G=(n,z=0,x=f,y=l,b=[...a])=>y?G(n%(x/=y),+b.splice(n/x,1)+z*10,x,y-1,b):z)(n--)-G(n))/9:F(a.push(++l),f*=l))(a=[l=f=1])

```

Try it online!

1-indexed.

@guest271314's opinion is right. Direct permutation computation is shorter...

### Explanation

```
n=>(                           // Function -
 F=_=>                         //  Helper func to calculate length needed
 f>n?                          //   If f > n (meaning the length is enough) -
  (
   (
    G=(                        //    Helper func to calculate permutation value -
     n,
     z=0,                      //     Initial values
     x=f,                      //     Made as copies because we need to alter
     y=l,                      //     these values and the function will be
     b=[...a]                  //     called twice
    )=>
    y?                         //     If still elements remaining -
     G(
      n%(x/=y),                //      Get next element
      +b.splice(n/x,1)+z*10,   //      And add to the temporary result
      x,
      y-1,                     //      Reduce length
      b                        //      Remaining elements
     )
    :z                         //     Otherwise return the permutation value
   )(n--)-G(n)                 //    Calculate G(n) - G(n - 1)
  )/9                          //    ... the whole divided by 9
 :F(
  a.push(++l),                 //   Otherwise l = l + 1, push l into the array
  f*=l                         //   ... and calculate l!
 )
)(
 a=[l=f=1]                     //  Initial values
)

```

## Original solution (159 bytes)

```
n=>(x=l=t=0n,P=(a,b=[])=>n?""+a?a.map(z=>P(a.filter(y=>y-z),[...b,z])):(v=b.reduce((u,y)=>u=u*10n+y),x?--n?0:t=v-x:0,x=v):0)([...Array(n+1))].map(_=>++l))&&t/9n

```

Try it online!

Link is to a longer version made for performance. `Array(n+1)` becomes `Array(Math.min(n+1,15))` in order to make demo work. Theoretically works up to infinity (up to stack limit in practice).

### Explanation

I mean there's too much to explain.

```
n=>(                             // Function
 x=l=t=0n,                       // Initialization
 P=(                             // Function to determine the permutation -
  a,                             //  remaining items
  b=[]                           //  storage
 )=>
 n?                              //  if we haven't reached the required permutation yet -
  ""+a?                          //   if we haven't the last layer of loop -
   a.map(                        //    loop over the entries -
    z=>
    P(                           //     recurse -
     a.filter(y=>y-z),           //      pick out the selected number
     [...b,z]                    //      append to next
    )
   )
  :(                             //   if we are at the last layer -
   v=b.reduce((u,y)=>u=u*10n+y), //    calculate the value of the permutation
   x?                            //    if not the first number -
    --n?                         //     if not the last -
     0                           //      do nothing
    :t=v-x                       //     else calculate difference
   :0,                           //    else do nothing
   x=v                           //    record ot anyway
  )
 :0                              //   else do nothing
)
(
 [...Array(n+1)].map(_=>++l)     // the list of numbers to permute
)&&t/9n                          // last difference divided by 9

```
> 2 votes

# Answer
# Pyth, ~~15~~ 14 bytes

```
.+m/i.PdSQT9,h

```

Returns the nth term. Try it here.

```
.+                     Find the differences between adjacent elements of
   m                   mapping lambda d:
      .PdSQ                the dth permutation of input,
     i     T               converted to base 10
    /       9              divided by 9
             ,         over [Q+1,Q]
               h Q
               Q

```
> 2 votes

# Answer
# , ~~44~~, 41 bytes

```
(9%~[:(2-~/\])i.(10#.1+A.)[:i.@>.!inv)@>:

```

Try it online!

Note: works even for 10! test case, but loses some precision there...

## original explanation

```
(9 %~ [: (2 -~&(10&#.)/\ ]) 1 + i. A. i.@>.@(!inv))@>:
(                                                 )@>: NB. add one to input
                                                       NB. since n-1 deltas
                                                       NB. gives n results
                                                       NB. call that "n"
(                               i.                )    NB. take the first n
(                                  A.             )    NB. lexicographically
                                                       NB. sorted items of
(                                     i.@         )    NB. 0 up to...
(                                        >.@      )    NB. the ceil of...
(                                           (!inv))    NB. the inverse of
                                                       NB. the factorial
(                           1 +                   )    NB. add 1 so our
                                                       NB. lists start at 1
                                                       NB. instead of 0
(     [: (                )                       )    NB. apply what's in
                                                       NB. parens to that
                                                       NB. list of lists
(        (2 -~        /\ ])                       )    NB. take successive
                                                       NB. differences BUT
(        (    &(10&#.)    )                       )    NB. convert each list
                                                       NB. to a base 10
                                                       NB. number first
(9 %~                                             )    NB. and divide every
                                                       NB. items of the
                                                       NB. result by 9

```
> 2 votes

# Answer
# JavaScript (ES6), 112 bytes

Very similar to Shieru Asakoto's algorithm.

```
n=>(g=N=>(h=a=>k>n?(F=r=>--i?F(+a.splice(N/(k/=i),1)+r*10,N%=k):r/9)``:h([i+1,...a],k*=i++))([i=k=1]))(n++)-g(n)

```

Try it online!
> 1 votes

---
Tags: code-golf, permutations
---


# Question
Title: Find the area of the smallest rectangle to contain squares of sizes up to n
This is a sequence question of the usual type, as applied to OEIS sequence A038666. That is, do either of the following:

* Accept no or any input, and output A038666 until the heat death of the universe.
* Accept a positive integer as input, and output the \\$n\\$th term of A038666 or its first \\$n\\$ terms. (If using \\$0\\$\- instead of \\$1\\$-indexing, then of course you also have to output `1` on `0` input.)

The \\$n\\$th term of A038666 is the least area among rectangles that contain non-overlapping squares of sizes \\$1\times1,2\times2,\dots n\times n\\$ if you're using \\$1\\$-indexing.

### Example:

The smallest-area rectangle which can contain non-overlapping squares of sizes \\$1\times1\\$ through \\$4\times4\\$ has dimensions \\$7\times5\\$:

```
4 4 4 4 3 3 3
4 4 4 4 3 3 3
4 4 4 4 3 3 3
4 4 4 4 2 2 1
x x x x 2 2 x

```

Therefore, \\$a(4)=7\times5=35\\$ (\\$1\\$-indexed).

Similarly, the least-area rectangle containing non-overlapping squares of sizes \\$1\times1\\$ through \\$17\times17\\$ has dimensions \\$39\times46\\$, so \\$a(17)=39\times46=1794\\$ (\\$1\\$-indexed).

# Answer
# JavaScript (ES6), 172 bytes

*Slower but shorter version suggestion suggested by @JonathanAllan (also saving 4 bytes in the original answer):*

```
f=(n,A,S=(n,c)=>n>=0?c(n)||S(n-1,c):0)=>S(A,w=>(F=(l,n)=>n?S(w-n,x=>S(A/w-n,y=>l.some(([X,Y,W])=>X<x+n&X+W>x&Y<y+n&Y+W>y)?0:F([...l,[x,y,n]],n-1))):A%w<1)([],n))?A:f(n,-~A)

```

Try it online!

---

# Original answer,  ~~209 183 178~~  174 bytes

Returns the \\$N\\$th term of the sequence, 1-indexed.

```
f=(n,A,S=(n,c)=>n>=0?c(n)||S(n-1,c):0)=>S(A,w=>A%w?0:(F=(l,n)=>n?S(w-n,x=>S(A/w-n,y=>l.some(([X,Y,W])=>X<x+n&X+W>x&Y<y+n&Y+W>y)?0:F([...l,[x,y,n]],n-1))):1)([],n))?A:f(n,-~A)

```

Try it online!

## Commented

### Helper function

We first define a helper function \\$S\\$ which invokes a callback function \\$c\\$ for \\$n\\$ to \\$0\\$ (both included) and stops as soon as a call returns a truthy value.

```
S = (n, c) =>               // n = integer, c = callback function
  n >= 0 ?                  // if n is greater than or equal to 0:
    c(n) ||                 //   invoke c with n; stop if it's truthy
    S(n - 1, c)             //   or go on with n - 1 if it's falsy
  :                         // else:
    0                       //   stop recursion and return 0

```

### Main function

We start with \\$A=1\\$.

For each pair \\$(w,h)\\$ such that \\$w\times h = A\\$, we try to insert all squares of size \\$1\times1\\$ to \\$n\times n\\$ (actually starting with the largest one) in the corresponding area, in such a way that they don't overlap with each other.

We keep track of the list of squares with their position \\$(X,Y)\\$ and their width \\$W\\$ in \\$l\[\text{ }\]\\$.

We either return \\$A\\$ if a valid arrangement was found, or try again with \\$A+1\\$.

```
f = ( n,                    // n = input
      A ) =>                // A = candidate area (initially undefined)
S(A, w =>                   // for w = A to w = 0:
  A % w ?                   //   if w is not a divisor of A:
    0                       //     do nothing
  : (                       //   else:
    F = (l, n) =>           //     F = recursive function taking a list l[] and a size n
      n ?                   //       if n is not equal to 0:
        S(w - n, x =>       //         for x = w - n to x = 0
          S(A / w - n, y => //           for y = A / w - n to y = 0:
            l.some(         //             for each square in l[]
            ([X, Y, W]) =>  //             located at (X, Y) and of width W:
              X < x + n &   //               test whether this square is overlapping
              X + W > x &   //               with the new square of width n that we're
              Y < y + n &   //               trying to insert at (x, y)
              Y + W > y     //
            ) ?             //             if some existing square does overlap:
              0             //               abort
            :               //             else:
              F([ ...l,     //               recursive call to F:
                  [x, y, n] //                 append the new square to l[]
                ],          //
                n - 1       //                 and decrement n
              )             //               end of recursive call
          )                 //           end of iteration over y
        )                   //         end of iteration over x
      :                     //       else (n = 0):
        1                   //         success: stop recursion and return 1
    )([], n)                //     initial call to F with an empty list of squares
) ?                         // end of iteration over w; if it was successful:
  A                         //   return A
:                           // else:
  f(n, -~A)                 //   try again with A + 1

```
> 10 votes

# Answer
# Python 2 (PyPy), ~~250~~ 236 bytes

-14 bytes thanks to msh210's suggestions.

Outputs the 1-indexed nth term of the sequence.

```
n=input()
r=range
k=n*-~n*(n-~n)/6
m=k*k
for Q in r(m):
 P={0}
 for X in r(n,0,-1):P|=([x for x in[{(x+a,y+b)for a in r(X)for b in r(X)}for x in r(Q%k-X+1)for y in r(Q/k-X+1)]if not x&P]+[{0}])[0]
 if len(P)>k:m=min(Q%k*(Q/k),m)
print m

```

Try it online! For n\>4, this takes lot of time. I have verified the result up to n=7 locally.
> 0 votes

---
Tags: code-golf, packing
---


title: Detecting loops in in in strings

text:
# Question
Title: Detecting loops in in in strings
Given a string, mark which parts in the string repeat in box brackets, and write how many times it does so before the box.

Example:`st st st Hello ThereThere`
`st`(with a space after) repeats 3 times, `There` repeats 2 times, and `l` repeats 2 times in `Hello`, so the output will be:
`3[st ]He2[l]o 2[There]`
There is no space between `[st ]` and `Hello` because the space in the string is being taken up by the repeating part. `[st ]`, 3 times with a `Hello` after it would be `st st st Hello`, which is what the string has.

Other examples:
`st Hello st st Bye` -\> `st He2[l]o 2[st ]Bye`
`Bookkeeper` -\> `B2[o]2[k]2[e]per`
`/\/\/\\\\\\\\/\/\/` -\> `3[/\]6[\]3[\/]`

Shortestest code wins.

EDIT: To clarify the choice of selections, choose the **largest possible** repeating section, and try and leave as little non-repeating characters as possible. Do not nest boxed-in sections.

# Answer
> 6 votes
## Perl, 36 bytes

```
#!perl -p
s!(.+)\1+!@{[$&=~/\Q$1/g]}."[$1]"!eg

```

Try it online!

---

## PHP 5.6, 68 bytes

Same code in PHP. Requires the command line option `-F`, and relies on deprecated `/e` modifier.

```
<?=preg_filter('/(.+)\1+/e','substr_count("\0","\1")."[\1]"',$argn);

```

# Answer
> 3 votes
## C, 224 205 203 199 195 193 chars

The string is given as program parameter. As usual, use double quotes if your string contains spaces, and for empty strings - calling the program without any parameter crashes, but calling with `""` works.

Output for test cases is:

```
st st st Hello ThereThere => 3[st ]He2[l]o 2[There]
Bookkeeper                => B2[o]2[k]2[e]per
/\/\/\\\\\\\\/\/\/        => 3[/\]2[\\\]3[\/]

```

which looks correct to me regarding "choose the largest possible repeating section".

Code:

```
l,r,f,i;char*c;main(a,b)char**b;{l=strlen(c=b[1]);for(;putchar(*c);c++)for(a=l;--a;f=0)for(r=a;!f;r+=a){for(i=0;i<a;)f|=r>l||c[i]-c[r+i++];if(f*r>a)c[a]=0,printf("\b%i[%s]",r/a,c),c+=r-1,a=1;}}

```

# Answer
> 3 votes
## scala, 102 chars

```
print("(?!\\s)(.+)\\1+".r.replaceAllIn(readLine,m=>m.matched.size/m.group(1).size+"["+m.group(1)+"]"))

```

**Output**

```
st st st Hello ThereThere ->    3[st ]He2[l]o 2[There]
st Hello st st Bye        ->    st He2[l]o 2[st ]Bye
Bookkeeper                ->    B2[o]2[k]2[e]per
/\/\/\\\\\\\\/\/\/        ->    3[/\]2[\\\]3[\/]

```

# Answer
> 1 votes
# Retina, ~~40~~ ~~37~~ 24 bytes

```
(.+)(\1)+
$.($#2*__)[$1]

```

-13 bytes thanks to *@Neil*.

Try it online or verify all test cases. (NOTE: Slightly different results for some test cases in comparison to the challenge description, but still the same as the accepted answer, so I assumed both are valid.)

**Explanation:**

```
(.+)(\1)+       # Look for the repeated sections (where the repeated string is captured in
                # group 1, and every time it's repeated in group 2)

```

Example: in the input `"st st st Hello ThereThere"` it will find the capture group 1 and 2 as: `"st "` & `["st ","st "]`; `"l"` & `["l"]`; and `"There"` & `["There"]` respectively.

```
   $#2          # Get the amount of times group 2 was repeated
      *_        # Converted to unary (that amount of '_')
        _       # + 1 (with an additional '_' added)
$.(      )      # Convert that unary back to a number again by taking the length
          [$1]  # And append the match of the first capture group between block-quotes
                # after the number

```

Example: `"st st st "` will become `"3[st ]"`; `"ll"` will becomes `"2[l]"`; and `"ThereThere"` will become `"2[There]"`. So `"st st st Hello ThereThere"` is now the intended result `"3[st ]He2[l]o 2[There]"` (which is output implicitly).

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

```
s|(.+)\1+|(length($&)/length$1)."[$1]"|ge

```

Try it online!

# Answer
> 0 votes
# PowerShell, 82 bytes

```
[regex]::Replace($args,'(.+)\1+',{$a,$g=$args|% gr*
"$($a.Length/$g.Length)[$g]"})

```

Try it online!

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


title: Factorize a Gaussian integer

text:
# Question
Title: Factorize a Gaussian integer
A Gaussian integer is a complex number whose real and imaginary parts are integers.

Gaussian integers, like ordinary integers, can be represented as a product of Gaussian primes, in a unique manner. The challenge here is to calculate the prime constituents of a given Gaussian integer.

Input: a Gaussian integer, which is not equal to 0 and is not a unit (i.e. 1, -1, i and -i can not be given as inputs). Use any sensible format, for example:

* 4-5i
* -5\*j+4
* (4,-5)

Output: a list of Gaussian integers, which are prime (i.e. no one of them can be represented as a product of two non-unit Gaussian integers), and whose product is equal to the input number. All numbers in the output list must be non-trivial, i.e. not 1, -1, i or -i. Any sensible output format can be used; it should not necessarily be the same as input format.

If the output list has more than 1 element, then several correct outputs are possible. For example, for input 9 the output can be \[3, 3\] or \[-3, -3\] or \[3i, -3i\] or \[-3i, 3i\].

Test cases, (taken from this table; 2 lines per test case)

```
2
1+i, 1-i

3i
3i

256
1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i

7+9i
1+i,2−i,3+2i

27+15i
1+i,3,7−2i

6840+585i
-1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i

```

Built-in functions for factoring Gaussian integers are not allowed. Factoring ordinary integers by built-in functions is allowed though.

# Answer
# Jelly, ~~61~~ ~~55~~ 50 bytes

```
ÆiḤp/-,1p`¤×€×1,ıFs2S€⁸÷ÆiḞƑ$ƇỊÐḟ1;Ṫð,÷@\ḟ1
Ç€F$ÐL

```

Try it online! (Header and Footer formats the output)

*-6 bytes thanks to @EricTheOutgolfer*

*-5 bytes thanks to @caird coinheringaahing*

**How it Works**

```
ÆiḤp/-,1p`¤×€×1,ıFs2S€⁸÷ÆiḞƑ$ƇỊÐḟ1;Ṫð,÷@\ḟ1 - helper: outputs a factor pair of the input
ÆiḤp/                    - creates a list of possible factors a+bi, a,b>=0
      -,1p`¤×€           - extend to the other three quadrants
              ×1,ıFs2S€  - convert to  actual complex numbers
⁸÷                       - get quotient with input complex number
  ÆiḞƑ$Ƈ                    - keep only Gaussian numbers (those unchanged when complex parts are floored)
     ỊÐḟ                 - remove units (i,-i,1,-1)
        1;               - append a 1 to deal with primes having no non-unit factors
          Ṫð,÷@\         - convert to a factor pair
                ḟ1       - remove 1s
Ç€F$ÐL
Ç€      - factor each number
   $    - and
  F     - flatten the list
    ÐL  - until factoring each number and flattening does not change the list

```
> 4 votes

# Answer
# Ruby, ~~258~~ ~~256~~ ~~249~~ 246+8 = ~~264~~ ~~257~~ 254 bytes

Uses the `-rprime` flag.

Geez, what a mess.

Uses this algorithm from stackoverflow.

```
->c{m=->x,y{x-y*eval("%d+%di"%(x/y).rect)};a=c.abs2.prime_division.flat_map{|b,e|b%4<2?(1..e).map{k=(2..d=b).find{|n|n**(~-b/2)%b==b-1}**(~-b/4)%b+1i;d,k=k,m[d,k]while k!=0;c/=d=m[c,d]==0?d:d.conj;d}:(c/=b<3?(b=1+1i)**e:b**e/=2;[b]*e)};a[0]*=c;a}

```

Try it online!
> 5 votes

# Answer
# Python 2, ~~250~~ ~~239~~ ~~223~~ 215 bytes

```
e,i,w=complex,int,abs
def f(*Z):
 if Z:
	z=Z[0];q=i(w(z));Q=4*q*q
	while Q>0:
 	 a=Q/q-q;b=Q%q-q;x=e(a,b)
 	 if w(x)>1:
		y=z/x
		if w(y)>1 and y==e(i(y.real),i(y.imag)):f(x,y);z=Q=0
 	 Q-=1
	if z:print z
	f(*Z[1:])

```

Try it online!

* -11 bytes when using *Multiple Function Arguments*
* -2²\*² bytes when using one variable to parse couples `(a,b)`
* -2³ bytes when mixing tabs and spaces: thanks to ovs

**Some explanation** recursively decompose a complex to two complexes until no decomposition is possible...
> 5 votes

# Answer
# Rust \- 212 bytes

```
use num::complex::Complex as C;fn f(a:&mut Vec<C<i64>>){for _ in 0..2{for x in -999..0{for y in 1..999{for i in 0..a.len(){let b=C::new(x,y);if(a[i]%b).norm_sqr()==0&&(a[i]/b).norm_sqr()>1{a[i]/=b;a.push(b)}}}}}}

```

I'm not 100% sure if this works 100% correct, but it seems to be correct for a large range of tests. This isn't smaller than Jelly, but at least it is smaller than the interpreted languages (so far). It also seems to be faster and can work through inputs of a billion magnitude in less than a second. For example 1234567890+3141592650i factors as (-9487+7990i)(-1+-1i)(-395+336i)(2+-1i)(1+1i)(3+0i)(3+0i)(4+1i)(-1+1i)(-1+2i), (click here to test on wolfram alpha)

This started out as the same idea as naive factoring of integers, to go through each number below the integer in question, see if it divides, repeat until done. Then, inspired by other answers, it morphed... it repeatedly factors items in a vector. It does this a good number of times, but not 'until' anything. The number of iterations has been chosen to cover a good chunk of reasonable inputs.

It still uses "(a mod b) == 0" to test whether one integer divides another (for Gaussians, we use builtin Rust gaussian modulo, and consider "0" as norm == 0), however the check for 'norm(a/b) != 1' prevents dividing "too much", basically allowing the resulting vector to be filled with only primes, but not taking any element of the vector down to unity (0-i,0+i,-1+0i,1+0i) (which is prohibited by the question).

The for-loop limits were found through experiment. y goes from 1 up to prevent divide-by-zero panics, and x can go from -999 to 0 thanks to the mirroring of Gaussians over the quadrants (I think?). As regarding the limitations, the original question did not indicate a valid range of input/output, so a "reasonable input size" is assumed... (Edit... however i am not exactly sure how to calculate at which number this will begin to "fail", i imagine there are Gaussian integers that are not divisible by anything below 999 but are still surprisingly small to me)

Try the somewhat ungolfed version on play.rust-lang.org
> 3 votes

# Answer
# Perl 6, ~~141~~ 124 bytes

*Thanks to Jo King for -17 bytes*

```
sub f($_){{$!=0+|sqrt .abs²-$^a²;{($!=$_/my \w=$^b+$a*i)==$!.floor&&.abs>w.abs>1>return f w&$!}for -$!..$!}for ^.abs;.say}

```

Try it online!
> 3 votes

# Answer
# Pyth, ~~54~~ ~~51~~ ~~45~~ ~~42~~ 36 bytes

```
 .W>H1cZ
h+.aDf!%cZT1>#1.jM^s_BM.aZ2

```

Try it online!

Accepts input in the form `1+2j` \- purely real or imaginary numbers can omit the other component (e.g. `9`, `2j`). Output is a newline-separated list of complex numbers, in the form `(1+2j)`, with purely imaginary numbers omitting the real part.

This uses simple trail division, generating all gaussian integers with magnitude greater than 1 and less than the current value, plus the value itself. These are filtered to keep those that are a factor of the value, and the smallest by magnitude is chosen as the next prime factor. This is output, and the value is divided by it to produce the value for the next iteration.

Also, Pyth beating Jelly (I don't expect it to last though)

```
 .W>H1cZ¶h+.aDf!%cZT1>#1.jM^s_BM.aZ2ZQ   Implicit: Q=eval(input())
                                         Newline replaced with ¶, trailing ZQ inferred
 .W                                  Q   While <condition>, execute <inner>, with starting value Q
   >H1                                   Condition function, input H
   >H1                                     Is magnitude of H > 1?
                                           This ensures loop continues until H is a unit, i.e. 1, -1, j, or -j)
      cZ¶h+.aDf!%cZT1>#1.jM^s_BM.aZ2Z    Inner function, input Z
                                .aZ        Take magnitude of Z

                             _BM           Pair each number in 0-indexed range with its negation
                            s              Flatten
                           ^       2       Cartesian product of the above with itself
                        .jM                Convert each pair to a complex number
                      #                    Filter the above to keep those element where...
                     > 1                   ... the magnitude is greater than 1 (removes units)
              f                            Filter the above, as T, to keep where:
                 cZT                         Divide Z by T
                %   1                        Mod real and imaginary parts by 1 separately
                                             If result of division is a gaussian integer, the mod will give (0+0j)
               !                             Logical NOT - maps (0+0j) to true, all else to false
                                           Result of filter are those gaussian integers which evenly divide Z
           .aD                             Sort the above by their magnitudes
          +                         Z      Append Z - if Z is ±1±1j, the filtered list will be empty
         h                                 Take first element, i.e. smallest factor
        ¶                                  Print with a newline
      cZ                                   Divide Z by that factor - this is new input for next iteration
                                         Output of the while loop is always 1 (or -1, j, or -j) - leading space suppesses output

```
> 2 votes

---
Tags: code-golf, number-theory, complex-numbers
---