title: Calculate Coefficient of Inbreeding

text:
# Question
Title: Calculate Coefficient of Inbreeding
Your task is, given a family tree, to calculate the Coefficient of Inbreeding for a given person in it.

## Definition

The Coefficient of Inbreeding is equal to the Coefficient of Relationship of the parents. The Coefficient of Relationship between two people is defined as weighed sum over all common ancestry as follows:

*Each* simple path P (meaning it visits no node more than once) which goes upwards to a common ancestor from A and then down to B adds \\$(\frac{1}{2})^{length(P)}\\$ to the Coefficient. Also, if A is an ancestor of B (or vice versa), each simple path linking them also adds \\$(\frac{1}{2})^{length(P)}\\$ to the Coefficient.

## Challenge Rules

* **Input** consists of a directed graph representing the family tree and a single identifier for a node of the graph. As usual, any convenient method is valid.
* The graph can be input in any convenient representation. Used below is a csv style in which each line represents a marriage between the first two entries, with the offspring being all following entries. Other representations, like a list of parent-child pairs, or a connectivity matrix, are also allowed.
* Similarly, the node identifier can be in any format working for that graph representation, like a string for the format used here, or an index for a connectivity matrix.
* **Output** is either (in any convenient method):
    + A single rational number between 0 and 1, representing the Coefficient of Inbreeding for the identified node in the graph.
    + Two integers, the second of which is a power of two such that the first number divided by the second is the Coefficient of Inbreeding (you do not need to reduce the fraction).
* In either case, make sure you have enough bits available to handle the given test cases (11 bits for the Charles II case) with full accuracy.
* Standard Loopholes are of course not allowed.
* You can assume the input graph to be well-formed as family tree, meaning you are allowed to fail in any way you want for the following cases:
    + The graph being cyclic
    + The node not being in the graph
    + The node in question not having exactly 2 parent nodes
    + The chosen input format not being followed
* This is . Shortest code for each language wins.

## Test cases

**1** In:

```
F;M;S;D
S;D;C
F;D;I

```

`C`

Out: `0.5`

There are two paths of length 2: S-F-D and S-M-D, thus the total is \\$(\frac{1}{2})^{2}+(\frac{1}{2})^{2}=0.5\\$

**2** In:

```
F;M;S;D
S;D;C
F;D;I

```

`S`

Out: `0`

F and M have no common ancestors.

**3** In:

```
F;M;S;D
S;D;C
F;D;I

```

`I`

Out: `0.5`

F is direct ancestor of D with path length 1, thus the Coefficient is \\$(\frac{1}{2})^{1}=0.5\\$

**4** In:

```
F;M1;S1;S2
F;M2;D1;D2
S1;D1;C1
S2;D2;C2
C1;C2;I

```

`I`

Out: `0.375`

There are 6 paths of length 4: Two go over M1 and M2 as C1-S1-M1-S2-C2 and C1-D1-M2-D2-C2. The remaining four all are distinct ways to connect over F: C1-S1-F-S2-C2, C1-S1-F-D2-C2, C1-D1-F-S2-C2 and C1-D1-F-D2-C2

Thus the Coefficient is \\$6 \cdot (\frac{1}{2})^{4}=0.375\\$

**5** In:

```
F;M;C1;C2;C3
F;C1;N1
C2;N1;N2
C3;N2;I

```

`I`

Out: `0.5`

There are 5 contributing paths, 3 over F and 2 over M. Two paths for F have length 3: N2-N1-F-C3 and N2-C2-F-C3, and one has length 4: N2-N1-C1-F-C3. One path to M has length 3: N2-C2-M-C3 and one length 4: N2-N1-C1-M-C3

Thus the Coefficient is \\$3 \cdot (\frac{1}{2})^{3}+2 \cdot (\frac{1}{2})^{4}=0.5\\$

**6** In:

```
Ptolemy V;Cleopatra I;Ptolemy VI;Cleopatra II;Ptolemy VIII
Ptolemy VI;Cleopatra II;Cleopatra III
Ptolemy VIII;Cleopatra III;Cleopatra IV;Ptolemy IX;Cleopatra Selene;Ptolemy X
Ptolemy IX;Cleopatra IV;Ptolemy XII
Ptolemy IX;Cleopatra Selene;Berenice III
Ptolemy X;Berenice III;Cleopatra V
Ptolemy XII;Cleopatra V;Cleopatra VII

```

`Cleopatra VII`

Out: `0.78125` or `200/256`

There are 51 contributing paths, with lengths from 3 to 8. A full list can be found here.

**7** In:

```
Philip I;Joanna;Charles V;Ferdinand I;Isabella 2
Isabella 1;Charles V;Maria;Philip II
Ferdinand I;Anna 1;Maximillian II;Charles IIa;Anna 2
Isabella 2;Christian II;Christina
Maria;Maximillian II;Anna 3
Anna 2;Albert V;Maria Anna 1;William V
Christina;Francis I;Renata
Philip II;Anna 3;Philip III
Charles IIa;Maria Anna 1;Margaret;Ferdinand II
William V;Renata;Maria Anna 2
Philip III;Margaret;Philip IV;Maria Anna 3
Ferdinand II;Maria Anna 2;Ferdinand III
Maria Anna 3;Ferdinand III;Mariana
Philip IV;Mariana;Charles IIb

```

`Charles IIb`

Out: `0.4267578125` or `874/2048`

There are 64 contributing paths with lengths between 3 and 11. A full list can be found here.

# Answer
> 3 votes
# Jelly, ~~43~~ 33 bytes

```
ịW€;Ɱ0ịịɗ¥€Ẏ¥ƬẎ¥€ŒpṪ€E$ƇF€QƑƇẈ.*S

```

Try it online!

A dyadic link taking the individual as the left argument and the pedigree as the right. The pedigree is a list of lists where each (possibly empty) list represents the parents of the person at that index. Returns a floating point number.

## Explanation

```
ị                                 | Index into pedigree to find parents of desired individual
 W€                               | Wrap each in a list
               ¥€                 | For each parent:
            ¥Ƭ                    | - Do the following as a dyad, keeping intermediate results:
         ¥€                       |   - Do the following as a dyad for each member of the list
   ;Ɱ   ɗ                         |     - Concatenate the following (as a dyad) to the end of the list:
     0ị                           |       - Last member of the list
       ị                          |       - Indexed into pedigree to find parents
           Ẏ                      |   - Remove one level of lists (concatenating outer sublists together)
              Ẏ                   | - Remove one level of lists (concatenating outer sublists together)
                 Œp               | Cartesian product of the two lists of possible chains of ancestors for each parent
                      $Ƈ          | Keep those where:
                   Ṫ€             | - The tail of each chain (removing from the chain in the process)
                     E            | - Is equal
                        F€        | Flatten each
                            Ƈ     | Keep those where:
                           Ƒ      | - The list is invariant when:
                          Q       |   - Uniquified
                             Ẉ    | Lengths of each list
                              .*  | 0.5 to the power of the lengths
                                S | Sum

```

# Answer
> 1 votes
# Python 2, ~~304~~ ~~294~~ ~~293~~ 278 bytes

Takes as input: list of lists of relatives; name of person to calculate coefficient.

```
P={}
I,Z=input()
for R in I:
 for r in R[:2]:P[r]=P.get(r,[])+R[2:]
l=lambda c,p,X:c==Z and X.append(p)or c in P and[l(z,p*1+[z],X)for z in P[c]]and X
print sum(pow(.5,len(a+b)-2)for k in P for a in l(k,[],[])for b in l(k,[],[])if~-len(a+b)==len(set(a+b))if a>b if a[-2]!=b[-2])

```

Try it online!

---

# Python 2, 274 bytes

If input is allowed as single list of lists, where last list contains name of person to calculate coefficient, some bytes can be saves, using leaked variable from for loop.

```
P={}
for Z in input():
 for r in Z[:2]:P[r]=P.get(r,[])+Z[2:]
l=lambda c,p,X:c==Z[0]and X.append(p)or c in P and[l(z,p*1+[z],X)for z in P[c]]and X
print sum(pow(.5,len(a+b)-2)for k in P for a in l(k,[],[])for b in l(k,[],[])if~-len(a+b)==len(set(a+b))if a>b if a[-2]!=b[-2])

```

Try it online!

---

Some explanation

```
# Converts input lists into dictionary, where keys - each parent
# and values - list of its children
# In this task we don't care about direct relations between any parents
P={}
for R in I:
 # for parents in cells [0] and [1] add cells [2:]
 for r in R[:2]:
  P[r] = P.get(r, []) + R[2:]

# Lambda collects all paths from node c to the person of interest
# It's recursive function, which stores all paths in argument X and then returns it
# Each paths is guarantied to have person of interest as last element
# and one of its parents as previous to last element
l=lambda c,p,X: c==Z and X.append(p) or c in P and [l(z, p*1+[z], X) for z in P[c]] and X

# For each node with children:
# calculate all paths to person of interest
# get all pairs of this paths
for k in P
 for a in l(k,[],[])for b in l(k,[],[])
# filters out dublicates
  if a>b

# if paths from pair have unique items
# (except only 1 same item, that each path have - person of interest)
# and if previous to last elements are different
# (i.e. paths through different parents)
  if ~-len(a+b)==len(set(a+b)) and a[-2]!=b[-2]

# This pair of paths forms simple inbreed path, so add up to result
   sum(pow(.5,len(a+b)-2) .. )

```

Note, that algorithm also covers cases when one of parents is ancestor to other one, as node of elder parent will produce similar paths, that will add up to result sum.

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


title: Compute the multinomial coefficient

text:
# Question
Title: Compute the multinomial coefficient
Time for another easy challenge in which all can participate!

The multinomial theorem states:

$$(x\_1 + x\_2 + \cdots + x\_m)^n = \sum\_{k\_1 + k\_2 + \cdots + k\_m = n} \binom n {k\_1, k\_2, \dots, k\_m} \prod\_{1 \le t \le m} x\_t^{k\_t}.$$

The expression in parentheses is the multinomial coefficient, defined as:

$$\binom n {k\_1, k\_2, \dots, k\_m} = \frac {n!} {k\_1!k\_2!\cdots k\_m!}$$

Allowing the terms \\$k\_i\\$ to range over all integer partitions of \\$n\\$ gives the \\$n\\$-th level of Pascal's \\$m\\$-simplex. Your task is to compute this coefficient.

## Task

Write a program or function which takes \\$m\\$ numbers, \\$n, k\_{1}, k\_{2}, \dots, k\_{m-1}\\$, and outputs or returns the corresponding multinomial coefficient. Your program may optionally take \\$m\\$ as an additional argument if need be. Note that **\\$k\_m\\$ is not in the input.**

* These numbers may be input in any format one likes, for instance grouped into lists or encoded in unary, or anything else, as long as the actual computation of the multinomial coefficient is performed by your code, and not the encoding process.
* Output format is similarly flexible.
* All code should run in less than one minute for \\$n\\$ and \\$m\\$ up to 1000.
* Do not worry about integer overflow.
* Built-ins designed to compute the multinomial coefficient are not allowed.
* Standard loopholes apply.

## Scoring

This is code golf: Shortest solution in bytes wins.

## Test cases

```
Input: 3, [2, 0]
Output: 3

Input: 3, [1, 1]
Output: 6

Input: 11, [1, 4, 4]
Output: 34650

Input: 4, [1,2]
Output: 12

Input: 15, [5,4,3,2]
Output: 37837800

Input: 95, [65,4,4]
Output: 1934550571913396675776550070308250

Input: 32, [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
Output: 4015057936610313875842560000000

Input: 15, [3,3,3,3]
Output: 168168000

Input: 1000, [10,10,10,10,10,10,10,10,10,10,100,100,100,100,100,100,100,100]
Output: 1892260836114766064839886173072628322819837473493540916521650371620708316292211493005889278395285403318471457333959691477413845818795311980925098433545057962732816261282589926581281484274178579110373517415585990780259179555579119249444675675971136703240347768185200859583936041679096016595989605569764359198616300820217344233610087468418992008471158382363562679752612394898708988062100932765563185864346460326847538659268068471585720069159997090290904151003744735224635733011050421493330583941651019570222984959183118891461330718594645532241449810403071583062752945668937388999711726969103987467123014208575736645381474142475995771446030088717454857668814925642941036383273459178373839445456712918381796599882439216894107889251444932486362309407245949950539480089149687317762667940531452670088934094510294534762190299611806466111882595667632800995865129329156425174586491525505695534290243513946995156554997365435062121633281021210807821617604582625046557789259061566742237246102255343862644466345335421894369143319723958653232683916869615649006682399919540931573841920000000000000

Input: 33, [17]
Output: 1166803110

Input: 55, [28]
Output: 3824345300380220

```

# Answer
> 23 votes
# Jelly, ~~7~~ 6 bytes

```
;_/!:/

```

Look ma, no Unicode! This program takes a single list as input, with **n** at its first index.

Try it online! or verify all test cases at once.

### How it works

```
;_/!:/ Input: A (list)

 _/    Reduce A by subtraction. This subtracts all other elements from the first.
;      Concatenate A with the result to the right.
   !   Apply factorial to all numbers in the resulting list.
    :/ Reduce the result by division. This divides the first element by the others.

```

# Answer
> 9 votes
## CJam, 11 bytes

```
l~_:-+:m!:/

```

Input as a single list with `n` first:

```
[95 65 4 4]

```

This handles inputs up to `n` and `m` 1000 pretty much instantly.

Test it here.

### Explanation

```
l~  e# Read a line of input and evaluate it.
_   e# Duplicate.
:-  e# Fold subtraction over the list. A fold is essentially a foreach loop that starts
    e# from the second element. Hence, this subtracts all the k_i from n, giving k_m.
+   e# Append k_m to the list.
:m! e# Compute the factorial of each element in the list.
:/  e# Fold division over the list. Again, this divides n! by each of the k_i!.

```

# Answer
> 4 votes
# MATL, 21 ~~15~~ bytes

Let's put the log-gamma function to good use. This avoids internal overflowing by working with logarithms of factorials, not with factorials themselves.

```
1+ZgiO$Gs-h1+Zgs-ZeYo

```

This works in current version (9.2.2) of the language/compiler, which is earlier than this challenge.

Inputs are: first a number, then a numeric vector. The result is produced as a `double`, which limits maximum output to somewhere around `2^52`.

### Example

```
>> matl 1+ZgiO$Gs-h1+Zgs-ZeYo
> 15
> [5 4 3 2]
37837800

```

### Explanation

```
1+       % implicit input (number). Add 1
Zg       % log-gamma function
i        % input (numeric vector).
0$G      % push both inputs
s-       % sum the second input (vector) and subtract from first
h1+      % append to vector. Add 1
Zg       % log-gamma function, element-wise on extended vector
s        % sum of results
-        % subtract from previous result of log-gamma
Ze       % exponential
Yo       % round. Implicit display

```

# Answer
> 4 votes
## PowerShell, ~~91~~ 74 bytes

Woo! My 100th answer on PPCG!

```
param($n,$k)(1..$n-join'*'|iex)/(($k|%{$n-=$_;1..$_})+(1..$n)-join'*'|iex)

```

Whew. Not going to win shortest-code, that's for sure. Uses a couple neat tricks with ranges, though. And this is probably complete gibberish to anyone not familiar with PowerShell.

### Explanation

First we take input with `param($n,$k)` and expect `$k` to be an array, e.g. `.\compute-the-multinomial-coefficient.ps1 11 @(1,4,4)`.

We'll start with the numerator (everything to the left of `/`). That's simply a range from `1..$n` that has been `-join`ed together with `*` and then evaluated with `iex` to compute the factorial (i.e., `1*2*3*...*$n`).

Next, we loop over `$k|%{...}` and each iteration we subtract the current value `$_` from `$n` (which we don't care about anymore) to formulate `$k_m` later. Additionally, we generate the range `1..$k_i` each iteration, which gets left on the pipeline. Those pipeline objects get array-concatenated with the second expression, range `1..$n` (which is `$k_m` at this point). All of that is finally `-join`ed together with `*` and evaluated with `iex`, similar to the numerator (this works because `x! * y! = 1*2*3*...*x * 1*2*3*...*y`, so we don't care about individual ordering).

Finally, the `/` happens, the numerator is divided by the denominator, and output.

Handles output correctly for larger numbers, since we're not explicitly casting any variables as any particular datatypes, so PowerShell will silently re-cast as different datatypes on the fly as needed. For the larger numbers, outputs via scientific notation to best preserve significant figures as the datatypes get re-cast. For example, `.\compute-the-multinomial-coefficient.ps1 55 @(28)` will output `3.82434530038022E+15`. I'm presuming this to be OK given *"Output format is similarly flexible"* is specified in the challenge and quintopia's comments *"If the final result can fit within the natively supported integer types, then the result must be accurate. If it cannot, there is no restriction on what may be output."*

---

### Alternatively

Depending upon output formatting decisions, the following at **92 bytes**

```
param($n,$k)((1..$n-join'*'|iex)/(($k|%{$n-=$_;1..$_})+(1..$n)-join'*'|iex)).ToString('G17')

```

Which is the same as the above, just uses explicit output formatting with `.ToString('G17')` to achieve the desired number of digits. For `55 @(28)` this will output `3824345300380220.5`

---

Edit1 -- Saved 17 bytes by getting rid of `$d` and just calculating it directly, and getting rid of the calculation for `$k_m` by stringing it along while we loop `$k`
Edit2 -- Added alternate version with explicit formatting

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

```
×/2!/+\⍛,

```

Try it online!

Using the idea from my APL answer on another challenge that involves multinomials.

A tacit function whose left argument is the list of k's, and right argument is n. The test cases check if it agrees with Adam's solution with left and right arguments flipped.

### How it works

```
×/2!/+\⍛,
     +\    ⍝ Cumulative sum of k's (up to m-1'th element)
       ⍛,  ⍝ Append n (sum of k_1 to k_m)
  2!/      ⍝ Binomial of consecutive pairs
×/         ⍝ Product

```

$$ \frac{(k\_1 + k\_2 + \cdots + k\_m)!}{k\_1! k\_2! \cdots k\_m!} = \frac{(k\_1 + k\_2)!}{k\_1! k\_2!} \times \frac{(k\_1 + k\_2 + \cdots + k\_m)!}{(k\_1 + k\_2)! k\_3! \cdots k\_m!} $$

$$ = \frac{(k\_1 + k\_2)!}{k\_1! k\_2!} \times \frac{(k\_1 + k\_2 + k\_3)!}{(k\_1 + k\_2)! k\_3!} \times \frac{(k\_1 + k\_2 + \cdots + k\_m)!}{(k\_1 + k\_2 + k\_3)! \cdots k\_m!} $$

$$ = \cdots = \binom{k\_1 + k\_2}{k\_1} \binom{k\_1 + k\_2 + k\_3}{k\_1 + k\_2} \cdots \binom{k\_1 + \cdots + k\_m}{k\_1 + \cdots + k\_{m-1}} $$

# Answer
> 2 votes
# Python 3, ~~93~~ 91

Thanks to Dennis and FryAmTheEggman.

```
f=lambda x:0**x or x*f(x-1)
def g(n,k):
    r=f(n)
    for i in k:r//=f(i)
    return r//f(n-sum(k))

```

`n` as integer, `k` as iterable.

Ungolfed:

```
import functools #cache

@functools.lru_cache(maxsize=None) #cache results to speed up calculations
def factorial(x):
    if x <= 1: return 1
    else: return x * factorial(x-1)

def multinomial(n, k):
    ret = factorial(n)
    for i in k: ret //= factorial(i)
    km = n - sum(k)
    return ret//factorial(km)

```

# Answer
> 2 votes
# Mathematica, 26 bytes

```
#!/Times@@({#-+##2,##2}!)&

```

Example:

```
In[1]:= #!/Times@@({#-+##2,##2}!)&[95,65,4,4]

Out[1]= 1934550571913396675776550070308250

```

# Answer
> 2 votes
# APL (Dyalog Unicode), 16 bytesSBCS

Entirely based on the mathematical skill of my colleague Marshall.

Anonymous infix function. Takes *k* as right argument and *n* as left argument.

```
{×/⍵!⍺-+\¯1↓0,⍵}

```

Try it online!

`{``}` anonymous lambda;  is left argument (*n*) and  is right argument (*k*)

`0,⍵` prepend a zero to *k*

`¯1↓` drop the last item from that

`+\` cumulative sum of that

`⍺-` subtract that from *n*

`⍵!` (*k*) that

`×/` product of that

# Answer
> 1 votes
## PARI/GP, 43 bytes

Pretty straightforward; aside from formatting, the ungolfed version might well be identical.

```
m(n,v)=n!/prod(i=1,#v,v[i]!)/(n-vecsum(v))!

```

# Answer
> 1 votes
# Matlab 48 bytes

You need to set `format` to `long` in advance to get the higher precision. Then, it's quite straightforward:

```
@(n,k)factorial(n)/prod(factorial([k,n-sum(k)]))

ans(95, [65,4,4])
ans =

 1.934550571913395e+33

```

# Answer
> 1 votes
# Pyth, 10 bytes

```
/F.!MaQ-FQ

```

Try it online: Demonstration

### Explanation:

```
/F.!MaQ-FQ   implicit: Q = input list
       -FQ   reduce Q by subtraction
     aQ      append the result to Q
  .!M        compute the factorial for each number
/F           reduce by division

```

# Answer
> 1 votes
# J, 16 bytes

```
[(%*/)&:!],(-+/)

```

## Usage

For larger values, a suffix of `x` is used to denote extended precision integers.

```
   f =: [(%*/)&:!],(-+/)
   11 f 1 4 4
34650
   15x f 5 4 3 2
37837800

```

## Explanation

```
[(%*/)&:!],(-+/)  Input: n on LHS, A on RHS
             +/   Reduce A using addition
            -     Subtract that sum from n, this is the missing term
         ]        Get A
          ,       Append the missing term to A to make A'
[                 Get n
      &:!         Take the factorial of n and each value in A'
   */             Reduce using multiplication the factorials of A'
  %               Divide n! by that product and return

```

# Answer
> 1 votes
# Haskell, ~~59~~ 58 bytes

```
f n=product[1..n]
n#k=foldl((.f).div)(f n)k`div`f(n-sum k)

```

Try it online!

Thanks to BMO for saving 1 byte!

# Answer
> 1 votes
# 05AB1E, 8 bytes

```
Æ¸«!R.«÷

```

Try it online! Explanation:

```
Æ           Subtract all the elements from the first
 ¸«         Append to the original list
   !        Take the factorial of all the elements
    R.«÷    Reduce by integer division

```

I can't seem to find better ways of performing step 2 or step 4.

# Answer
> 1 votes
# APL (Dyalog Unicode), 17 bytes

```
⊢∘!÷(×/∘!⊣,⊢-1⊥⊣)

```

Try it online!

Infix tacit function (Thanks to @Adám for the 2 bytes it saves.)

---

# APL (Dyalog Unicode), 19 bytes

```
{(!⍺)÷×/!(⍺-+/⍵),⍵}

```

Try it online!

Infix Dfn.

Both functions above compute the given formula.

# Answer
> 0 votes
# Clojure, 70 bytes

```
#(let[a apply](a /(map(fn[x](a *(map inc(range x))))(conj %(a - %)))))

```

Creates an anonymous function taking all of the arguments as a single list, with `n` first.

30 characters are "wasted" just defining the damn factorial function. Oh well.

# Answer
> 0 votes
# Perl 6,  ~~52~~  50 bytes

```
->\n,\k{[*](1..n)div[*] ([*] 1..$_ for |k,[-] n,|k)}

```

Test it

```
->\n,\k{[*](1..n)/[*] ([*] 1..$_ for |k,[-] n,|k)}

```

Test it (result is a Rational with denominator of 1)

## Expanded:

```
->     # pointy block lambda
  \n,
  \k
{
    [*]( 1 .. n )   # factorial of ｢n｣

  /                 # divide (produces Rational)

    [*]             # reduce the following using &infix:«*»

      (
          [*] 1..$_ # the factorial of

        for         # each of the following

          |k,       # the values of ｢k｣ (slipped into list)
          [-] n,|k  # ｢n｣ minus the values in ｢k｣
      )
}

```

---
Tags: code-golf, math, combinatorics, restricted-time
---


title: Fermat's Last Theorem, mod n

text:
# Question
Title: Fermat's Last Theorem, mod n
# Fermat's Last Theorem, mod n

It is a well known fact that for all integers \\$p\>2\\$, there exist no integers \\$x, y, z\>0\\$ such that \\$x^p+y^p=z^p\\$. However, this statement is not true in general if we consider the integers modulo \\$n\\$.

You will be given \\$n\\$ and \\$p\\$, which are two positive integers with \\$n\>1\\$. Your task will be to write a function or program to compute all positive integers \\$x, y, z\<n\\$ such that \\$(x^p+y^p)\\$ and \\$z^p\\$ give the same remainder when divided by \\$n\\$.

# Input

Any reasonable method of input is allowed. E.g. two separate user inputs, ordered pair, two function parameters, etc.

# Output

Any reasonable method of output is valid, it may be produced by a function or output to the screen. The order the triples are listed does not matter. Triples such as `(1, 2, 3)` and `(2, 1, 3)` are considered distinct, and all distinct triples should be listed exactly once. No invalid/trivial triples such as `(0, 0, 0)` should be output.

The numbers \\$x, y, z\\$ may have any ordering within each of the triples, but that order should be consistent. For example if \\$2^p+2^p\\$ and \\$3^p\\$ have the same remainder when divided by \\$n\\$, you may list this triple as `(2, 2, 3)` or `(3, 2, 2)`.

# Examples

```
n p -> Possible Output
----------------------------------------------------------------
2 3 -> []
3 3 -> [(1,1,2),(2,2,1)]
3 4 -> []
4 3 -> [(1,2,1),(1,3,2),(2,1,1),(2,2,2),(2,3,3),(3,1,2),(3,2,3)]

```

# Scoring

Shortest code in bytes with no standard loopholes wins.

# Answer
> 8 votes
# Julia 1.0, 61 bytes

```
f(n,p,q=1:n-1)=[(x,y,z) for x=q,y=q,z=q if(x^p+y^p)%n==z^p%n]

```

-1 thanks to Glen O

Try it online!

# Answer
> 7 votes
# 05AB1E, ~~15~~ 10 bytes

-2 bytes by Kevin Cruijssen
-3 bytes by Grimmy

```
<L3ãʒImÆ¹Ö

```

Try it online!

Returns a triples in the format `[z,y,x]`.

**Explanation**:

```
<L                | Push the interval [1,n)
  3ã              | Push the triple cartesian product [1,n) x [1,n) x [1,n)
                  | E.g. with n = 3, the list begins as follows:
                  | [[1, 1, 2], [1, 2, 1], [2, 1, 3], ...]
    ʒ             | Filter the list:
     Im           | Take the p-th power of each input
                  | E.g. [1, 1, 2] --> [1^p, 1^p, 2^p]
       Æ          | Reduce by subtraction
                  | E.g. [1^p, 1^p, 2^p] -->  1^p - 1^p - 2^p
        ¹Ö        | Check if 1^p - 1^p - 2^p = 0 (mod n), and filter out if not.

```

# Answer
> 7 votes
# APL (Dyalog Unicode), 19 bytes

```
{⍸0=⍵|-/¨⍺*⍨⍳3⍴⍵-1}

```

The triples are returned in the format `x z y`. Try it online!

### Explanation

```
{⍸0=⍵|-/¨⍺*⍨⍳3⍴⍵-1} ⍝ n is our right argument, ⍵, and p is our left, ⍺.

             3⍴⍵-1  ⍝ First, we get a triple of (n-1, n-1, n-1).
            ⍳       ⍝ Then we get the Cartesian product of three range[1, n-1).
                    ⍝ As you will see, this gives a list of (x z y) triples.
         ⍺*⍨        ⍝ We take each element of each triple to the power of p.
      -/¨           ⍝ Here we subtract over each triple, using (element - rest)
                    ⍝ This gives us (x^p - (z^p - y^p)) = x^p + y^p - z^p.
    0=              ⍝ Then we check which (x^p + y^p - z^p) equals 0.
   ⍸                ⍝ And use these results, a Boolean array,
                    ⍝ to find get the indices of the correct triples,
                    ⍝ which are our (x z y)s.

```

# Answer
> 6 votes
# Jelly, 13 bytes

```
*ŒH§%³E
Ṗṗ3çƇ

```

A full program accepting command line arguments `n p` which prints a list representation of the results (Do note that the empty list is represented as no output).

**Try it online!**

### How?

```
*ŒH§%³E - Link 1: evaluate a triple: [x, y, z], p
*       - exponentiate               [x^p, y^p, z^p]
 ŒH     - split into halves          [[x^p, y^p], [z^p]]
   §    - sums                       [x^p+y^p, z^p]
     ³  - program's 1st argument     n
    %   - modulo                     [(x^p+y^p)%n, (z^p)%n]
      E - all equal?                 (x^p+y^p)%n == (z^p)%n

Ṗṗ3çƇ - Main Link: n, p
Ṗ     - pop (implicit range of n)    [1,2,3,...,n-1]
  3   - literal three                3
 ṗ    - Cartesian power              [[1,1,1],[1,1,2],...,[n-1,n-1,n-1]]
    Ƈ - filter keep those for which:
   ç  -   last Link (1) as a dyad    Link 1([[1,1,1],[1,1,2],...,[n-1,n-1,n-1]], p)
      - implicit print

```

# Answer
> 4 votes
## GAP, 63 bytes

```
Filtered(Tuples([1..n-1],3),i->(i[1]^p+i[2]^p-i[3]^p) mod n=0);

```

For example:

```
gap> n:=4; p:=3;
4
3
gap> Filtered(Tuples([1..n-1],3),i->(i[1]^p+i[2]^p-i[3]^p) mod n=0);
[ [ 1, 2, 1 ], [ 1, 3, 2 ], [ 2, 1, 1 ], [ 2, 2, 2 ], [ 2, 3, 3 ],
  [ 3, 1, 2 ], [ 3, 2, 3 ] ]

```

# Answer
> 3 votes
# Octave, ~~74~~ 72 bytes

*2 bytes saved thanks to @79037662*

```
@(n,p){[c,b,a]=ndgrid(1:n-1) [a(k=~mod(a.^p+b.^p-c.^p,n)) b(k) c(k)]}{2}

```

Try it online!

# Answer
> 3 votes
# JavaScript (ES7), 104 bytes

Takes input as `(n)(p)`.

```
n=>p=>[...Array(n**3)].map((_,i)=>[i/n/n|0,i/n%n|0,i%n]).filter(([x,y,z])=>x*y*z&&(x**p+y**p)%n==z**p%n)

```

Try it online!

# Answer
> 3 votes
# , 67 bytes

```
function(n,p,m=t(expand.grid(a<-2:n-1,a,a)))m[,!c(1,1,-1)%*%m^p%%n]

```

Try it online!

`expand.grid` creates all possible triplets of numbers. Annoyingly, the output of `expand.grid` is a data frame and not a matrix, so I transpose it to coerce to a matrix `m`. Take the matrix product of `[1,1,-1]` with `m^p` to get \\$x^p+y^p-z^p\\$, then keep only the rows for which we get \\$ 0 \mod n\\$.

# Answer
> 3 votes
# , 65 bytes

3 btye's saved from my original idea by @robin-ryder by using subtraction, applying modulo the result.

```
function(n,p,q=(2:n-1)^p)which(!outer(outer(q,q,'+'),q,'-')%%n,T)

```

Try it online!

Makes use of `outer` to build a 3d array of the addition, then the subtraction. If the remainder of n is 0 output the array indices using `which`.

# Answer
> 3 votes
# Wolfram Language (Mathematica), 54 bytes

```
n_~f~p_:=Select[Range[n-1]~Tuples~3,n|{1,1,-1}.#^p&]

```

Named function taking the two inputs, like `f[4,3]`. The `|` symbol typed above needs to be replaced by the 3-byte character representing the "divides" relation; `\[Divides]` works as well, and is used in the TIO example.

Works by testing every possible triple `{x,y,z}`. The only detail of note is that the dot product `{1,1,-1}.#^p&`, when applied to `{x,y,z}`, calculates `x^p+y^p-z^p`.

Try it online!

# Answer
> 2 votes
# Jelly, 13 bytes

```
*+_ƭ/³ḍ
Ṗṗ3çƇ

```

Try it online!

-2 bytes thanks to caird coinheringaahing
-1 byte borrowing a clever trick from Jonathan Allan

# Explanation

```
*+_ƭ/³ḍ  Helper Link - given (x, y, z), determine if x^p + y^p = z^p (mod n)
*        (x^p, y^p, z^p)
    /    Reduce over
 +_ƭ     Tied operator: cycle between + and - (x^p + y^p - z^p)
     ³ḍ  Divisibility check by n (if x^p + y^p - z^p is divisible by n then x^p + y^p is congruent to z^p mod n)
Ṗṗ3çƇ    Main Link
Ṗ        Pop (remove last element) - on an integer, implicit range (1 to n-1)
 ṗ3      Cartesian power ^ 3
   çƇ    Filter: keep triples that are valid by the helper link

```

# Answer
> 2 votes
# Ruby, ~~67~~ 66 bytes

```
->n,p{w=*1...n;w.product(w,w).select{|a,b,c|(a**p+b**p-c**p)%n<1}}

```

Try it online!

Thanks Chas Brown for -1 byte.

# Answer
> 1 votes
# Python 2, 94 bytes

```
n,p=input()
R=range(1,n)
print[(x,y,z)for x in R for y in R for z in R if(x**p+y**p-z**p)%n<1]

```

Try it online!

Pretty basic.

# Answer
> 1 votes
# Icon, 95 bytes

```
procedure f(n,p)
x:=1to(t:=n-1)&y:=1to t&z:=1to t&(x^p+y^p-z^p)%n=0&write(x," ",y," ",z)&\q
end

```

Try it online!

# Answer
> 1 votes
# K (oK), ~~30~~ 23 bytes

-7 bytes thanks to ngn!

```
{(~x!-/*/y#)#+1+!3#x-1}

```

Try it online!

# Answer
> 1 votes
# APL(NARS), chars 129, bytes 258

```
r←f w;n;p;a;v;i;j;b
(n p)←w⋄a←n∣p*⍨v←⍳n-1⋄r←⍬
:for i :in v⋄:for j :in v
:if a∊⍨b←n∣a[i]+a[j]⋄r←r,⊂i,j,a⍳b⋄:endif
:endfor⋄:endfor

```

test:

```
  ⎕fmt f 2 3
┌0─┐
│ 0│
└~─┘
  ⎕fmt f 3 3
┌2────────────────┐
│┌3─────┐ ┌3─────┐│
││ 1 1 2│ │ 2 2 1││
│└~─────┘ └~─────┘2
└∊────────────────┘
  ⎕fmt f 3 4
┌0─┐
│ 0│
└~─┘
  ⎕fmt f 4 3
┌7─────────────────────────────────────────────────────────────┐
│┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐│
││ 1 2 1│ │ 1 3 2│ │ 2 1 1│ │ 2 2 2│ │ 2 3 3│ │ 3 1 2│ │ 3 2 3││
│└~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘2
└∊─────────────────────────────────────────────────────────────┘

```

# Answer
> 0 votes
# Zsh, 90 bytes

```
l=({1..$[$1-1]}\ )
for x y z (${=${:-$^l$^l$^l}})(((x**$2+y**$2-z**$2)%$1))||<<<"$x $y $z"

```

Try it online!

Creates the list `l=('1 ' '2 ' '3 ' ... '(n-1) ' )`, then `${=${:-$^l$^l$^l}` gets the Cartesian product and splits on spaces.

# Answer
> 0 votes
# Pyth, 17 bytes

```
AQf!%-F^RHTG^StG3

```

Try it online!

Displays a list of triplets, each as \\$(z, x, y)\\$.

```
AQ                 # Q = eval(input()), G = Q[0] (=n), H = Q[1] (=p)
            ^StG3  # Get the following: range(1, n) ^ 3 -> List of (z,x,y) tuples
  f                # filter that on the following condition: lambda T:
       ^RHT        # map(lambda x: x^H, T)  --> (z^p, x^p, y^p)
     -F            # reduce by subtraction -> z^p - x^p - y^p = z^p - (x^p + y^p)
    %      G       # modulo n  --> (z^p - (x^p + y^p)) mod n
   !               # not (check if == 0) --> z^p == x^p + y^p mod n

```

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


title: Decorate Pascal's Triangle

text:
# Question
Title: Decorate Pascal's Triangle
Although what is a Pascal's triangle is well-known and we already can generate it, the task is now different:
**Output** \\$n\\$ first lines of the Pascal's triangle as colored bricks.
Color number is computed as maximal power of \\$d\\$, that divides the needed-to-color element or \\$7\\$ if power is more than \\$7\\$.
Numbered colors are (\\$0\\$-based): default, red, green, yellow, blue, magenta, cyan, white (default color is 0th, red is 1st, .. white is 7th).

* Any space-filling (I mean not `.`,`'` or `"` or smth small) character
can be used for bricks, even `'\u2588'`.
* Whitespace before or after the bricks are optional.
* Brick horizontal length (\\$1\\$ or \\$2\\$) is your choice.
* You may choose any convenient output method -- ansi text or graphics or HTML or whatever
* If you choose output letters or color numbers instead of coloring the triangle itself, you should specify in the text of your answer which character corresponds to which color, but output wouldn't look so nice)

**Input** Integers \\$n\\$ and \\$d\>1\\$ in any convenient method.
This is code-golf, the shortest code in each language wins.

# Answer
> 9 votes
# C (gcc),  ~~157 153 143 139~~  135 bytes

*Saved several bytes thanks to @AlexeyBurdin*
*Saved  ~~4~~  8 more bytes thanks to @ceilingcat*

Outputs with ANSI colors.

```
long p,a,s,c,L;f(n,d){for(a=0;c=a++-n;puts(""))for(;p=c<a;printf(c<0?" ":"\e[3%dm@@",L),s=++c<1?1:s*a/c-s)for(L=0;p*=d,L<7&s%p<1;L++);}

```

Try it online! (no colors on TIO)

### Example output for \\$f(40,2)\\$

### Formula

At row \\$r\\$ and column \\$c-1\\$, we have:

$$P\_{r,c-1}={r\choose c-1}=\frac{r!}{(c-1)!(r-c+1)!}$$

On the same row and the next column \\$c\\$, we have:

$$\begin{align}P\_{r,c}={r\choose c}&=\frac{r!}{c!(r-c)!}\\ &=\frac{r-c+1}{c}\times\frac{r!}{(c-1)!(r-c+1)!}\\ &=\frac{r-c+1}{c}\times P\_{r,c-1}\\ &=\frac{r+1}{c}P\_{r,c-1}-P\_{r,c-1}\end{align}$$

which is translated as `s = s * a / c - s` in the C code (with \\$a=r+1\\$).

### Commented

```
long p, a, s, c, L;               // declare a few 64-bit integers
f(n, d) {                         // n = number of rows, d = colorization parameter
  for(a = 0; a++ < n; puts(""))   // for a = 1 to n, with a linefeed added after each
    for(                          // iteration:
      c = a + ~n;                 //   for c = a - n - 1 to a - 1:
      p = c < a;                  //
      printf(                     //     update the output after each iteration:
        c < 0 ?                   //       if c is negative:
          " "                     //         just append a space
        :                         //       else:
          "\e[3%dm@@",            //         append the ANSI color code, followed by '@@'
        L                         //       set the 2nd digit of the color code
      ),                          //
      s = ++c < 1 ? 1             //     increment c; set s to 1 while c is less than 1
                  : s * a / c - s //     then, update s to s * a / c - s
    )                             //
      for(                        //       compute the color L:
        L = 0;                    //         start with L = 0
        p *= d,                   //         multiply p by d
        L < 7 & s % p < 1;        //         stop if L = 7 or p does not divide s
        L++                       //         increment L
      );                          //
}                                 //

```

# Answer
> 3 votes
# Python 2, ~~158~~ ~~134~~ 132 bytes

```
n,d=input()
o=r=[1]
exec"print''.join([`i`for i in range(8)if c%d**i<1][-1]*2for c in r).center(2*n);r=o+map(sum,zip(r,r[1:]))+o;"*n

```

Try it online!

22 bytes from tips by Jonathan Allan.

Uses `01234567` as the 8 characters instead of 8 colors.

# Answer
> 3 votes
# 05AB1E, ~~17~~ 16 bytes

```
ÝεyÝcI7LmδÖO}».c

```

Try it online!

```
Ý                 # range 0..input
 ε          }     # for each number y in that range:
  yÝ              #  range 0..y
    c             #  binomial coefficient (yields a row of the triangle)
     I            #  second input
      7L          #  range 1..7
        m         #  power (yields [input, input², ..., input**7])
         δÖ       #  double-vectorized divisible-by
           O      #  sum each inner list
»                 # join by newlines, joining sublists by spaces
 .c               # center

```

### 05AB1E, 22 bytes, no binomial coefficient built-in

```
1λ£0ªDÁ+}εI7LmδÖOºJ}.c

```

Try it online!

# Answer
> 2 votes
# Jelly, 23 bytes

```
1Ø0j+ƝƊ⁸Ð¡Ṗọ«7ịØaḤz⁶ZṚ€

```

Try it online!

A full program taking the number of rows as its first argument and the power as its second. Outputs the triangle to STDOUT. Colours are represented by `z` for 0/default and `a` to `g` for 1 to 7+.

# Answer
> 2 votes
# Japt, ~~41~~ ~~36~~ ~~32~~ ~~29~~ 25 bytes

```
_p1 ä+T}h[]à)m£_XuVpZa7}f

```

Try it

```
      h   )  // run input times
       []à   // starting with empty 2d array (permutations of [])

_    }       // function that:
 p1          // appends 1
    T        // and prepends 0
  ä+         // sums consecutive elements

m            // for each line
 £           // for each element
           f // find first number (starting at 0) that return false this function:
  _       }  // f(Z)
   Xu        // triangle element modulo
     Vp      // 2nd input raised to
       Za8   // absolute difference

```

Uses numbers \[7...0\] as colors Footer inverts colors to \[0...7\] for simpler output

Saved a lot thanks to @Shaggy

# Answer
> 2 votes
# 05AB1E, ~~24~~ 21 bytes

```
FNNÝcεU7ÝR.ΔmXsÖ])».c

```

First input is the amount of rows `n`, second input the power-base `d`.
Outputs `[0,7]` instead of the colors, and only outputs a single digit for the bricks (with spaces).

Try it online.

**Explanation:**

```
F                # Loop in the range [0, (implicit) input n):
 NN              #  Push the current loop-index twice
   Ý             #  Pop the top one, and create a list in the range [0, index]
    c            #  Calculate the binomial coefficient of the index and this ranged list
                 #   i.e. 10 choose [0,1,2,3,4,5,6,7,8,9,10]
                 #    → [1,9,36,84,126,126,84,36,9,1]
    ε            #  Map each value to:
     U           #   Pop and store the current value in variable `X`
      7Ý         #   Push a list in the range [0,7]
        R        #   Reverse it to make the range [7,0]
         .Δ      #   Find the first digit which is truthy for:
           m     #    Take the (implicit) input d to the power of the current digit
            Xs   #    Push variable `X` and swap the two values
              Ö  #    Check if `X` is divisible by this digit ** `d`
]                # Close the find_first; map; and loop
 )               # Wrap all lists into a list
  »              # Join each inner list by spaces, and then each string by newlines
   .c            # Centralize the lines by padding leading spaces
                 # (after which the result is output implicitly)

```

# Answer
> 1 votes
# Charcoal, 36 bytes

```
Ｎθ⊞υ¹ＦＮ«Ｐ⭆υ×¹¹ΣＥ⁸¬﹪κＸθμ↙⊞υ⁰ＵＭυ⁺κ§υ⊖λ

```

Try it online! Link is to verbose version of code. Takes the number of rows as the second input. Output uses digits `1-8` to represent the colours (`1` = default). Explanation:

```
Ｎθ

```

Input the base.

```
⊞υ¹

```

Start the first row with a single `1`.

```
ＦＮ«

```

Loop over each row.

```
Ｐ⭆υ×¹¹ΣＥ⁸¬﹪κＸθμ↙

```

For each cell, determine its divisibility by the first 8 powers of the base, and take the sum. Then multiply by 11 to duplicate the digit. (Alternatively, casting to string and then duplicating the digit also works.) Don't move the cursor while printing, instead finish by moving the cursor down and left.

```
⊞υ⁰ＵＭυ⁺κ§υ⊖λ

```

Add another column to the row and calculate each row as the sum of the two cells above.

# Answer
> 0 votes
# Ruby, 123 bytes

```
->n,d{(0..n).map{|w|' '*(n-w)+(0..w).map{|i|"\e[#{30+(b=[*1..w].combination(i).size).downto(0).find{|w|b%d**w<1}}m##"}*''}}

```

Try it online!

---
Tags: code-golf, math, combinatorics, color
---


title: Transformers in Disguise (Cops' Thread)

text:
# Question
Title: Transformers in Disguise (Cops' Thread)
The robber's thread is here

The cops task is to write a function or program that, when given an input of itself, outputs a finite deterministic string. If the program is given a different input, it should return a different output.

## Rules:

* Submissions consist of
    + Language name
        - If any flags are used, they should be revealed.
    + Byte count of program
    + Byte count of output
    + Output
        - If it is particularly long, please provide a pastebin or something similar
        - If it contains unprintables, please provide a hexdump.
        - Trailing newlines and whitespace should be included in the output
    + Where the input is coming from (STDIN, command line, etc.)
* If applicable, you may assume that the byte representing EOF is not present in the input, unless you use that byte in your program.
* If your program is cracked, add a link to the corresponding answer in the robber's thread in your title.
* Your program is not safe until a week has passed and you mark it so.
* I disapprove of techniques like seeding random with the input or cryptographic hash functions. I can't stop them, but **I will not be accepting a solution that utilises either of these**. Also note that some of these techniques might have collisions, where a different string produces the same output.
* Your goal is to have the shortest output. The shortest safe solution posted within three weeks of posting this question wins!

The robber's task is to find a program of size equal to or less than the original, which also obeys the above rules.

If a robber cracks your program with a different solution than intended, then you have the opportunity to 'uncrack' it by proving that the robber's solution is incorrect. You can do this by finding an input to the robber's program that will produce the same output.

## Example Submission:

### brainfuck, 10 bytes, Score: 10

```
]<.[<],>[,

```

This solution is ,\[\>,\]\<\[.\<\] which simply reverses the input

Good luck!

# Answer
# , 31 characters, score 30, safe but possibly broken?

A 7 program is normally just a number, but it can contain whitespace, splitting it into multiple numbers. This submission therefore consists of two numbers (which are implicitly concatenated by the 7 interpreter), and the program likewise takes two numbers as input, via standard input. (The "31 characters" in the header is the total length of the two numbers, plus one separating whitespace character; the digits that make up the numbers are interpreted as octal when used as a program, but decimal when used as an input, and it's the digits that are the same in the two cases, not the actual numbers. Note that it's irrelevant either when treated as a program, or when treated as an input, whether you separate them with a space or a newline; I hope that doesn't invalidate the submission.)

The expected output is the following number (expressed here in decimal, as that's the output format that the 7 interpreter uses):

```
238363505302130098723162537059

```

Note that the 7 interpreter linked from the Esolang wiki internally stores numbers in unary, meaning you're unlikely to have enough memory to actually run the program on itself to see what it does. I verified the program via working out its behaviour manually, and testing it on small inputs to verify that it did what I expected it to do. An alternative approach would be to write an interpreter that uses a more efficient method of storing numbers.

Avoiding cracks here was something of a pain, but I'm finally now satisfied that no two numbers other than those in the program itself are capable of producing 238363505302130098723162537059 as output. (*EDIT 1 week later: I may have been wrong, depending on how you interpret the question; see below.*)

## Solution

The original program was:

> ```
> 711170237403706
> 111723603700633
> ```
> This program takes two numbers \\$x\\$ and \\$y\\$, and calculates the result of the expression \\$3xy-y-2\\$ (i.e. \\$y(3x-1)-2\\$). If we perform this calculation at \\$x=711170237403706\\$ and \\$y=111723603700633\\$, we get a result of \\$238363505302130098723162537059\\$ as required.

It was intended that no other input will give the desired result because:

> The input must be chosen such that \\$y(3x-1)-2=238363505302130098723162537059\\$, i.e. \\$y(3x-1)=238363505302130098723162537061\\$ (adding 2 to both sides). This number is a semiprime, with only two factors: \\$111723603700633\\$ and \\$2133510712211117\\$. Only one of these numbers, \\$2133510712211117\\$, can be expressed in the form \\$3x-1\\$ (giving \\$(3 \times 711170237403706)-1=2133510712211117\\$). So we can uniquely identify which number is \\$x\\$ and which is \\$y\\$, meaning that only one input works.

However, depending on how you interpret the question, there may be a second input that produces the desired output (thus invalidating this solution):

> Unfortunately, there are two multiplicative partitions of a semiprime into two factors: one is to divide it into the two prime factors, but the other is the trivial partition consisting of \\$1\\$ and the number itself. \\$1\\$ cannot be written in the form \\$3x-1\\$ with integer \\$x\\$, but the desired output can be; thus a potential meta-crack involves giving the input as \\$79454501767376699574387512354\\$ and \\$1\\$. However, the first number here involves characters (\\$8\\$ and \\$9\\$) which are not in the character set for 7 programs. So if input is restricted to being in the same character set as the program, this solution is valid; but if input containing characters from outside the program's character set is allowed, this solution is invalid.

## Explanation

Here's how the intended solution functions:

> ```
> 711170237403706 111723603700633
> 7   7   7                         Stack element separators
>  111 023 403706 111723603700633   Initial stack elements
>  111                              Number 3, in unary
>      023                          I/O DSL for "input a number"
>          403706 111723603700633   Main program
> (Implicit: execute a *copy* of the main program element, preserving the original)
>          40                       Swap {023} above {program}, escaping it
>            3                      Do I/O using {023}; pop {program}
>      0                            I/O: numeric
>       23                          Input a number, copying {111} that many times
>             706                   Append "6" to the number (decrementing it)
>                 11                Push two empty stack elements
>                   17236           Push a stack element "23" (unescaped)
>                        0          Escape {23}, consuming an empty element
>                         3         Do I/O using {23}; pop {the element below}
>                     23            Copy the top of stack *input* many times
>                          7006     Append "66" (i.e. subtract 2)
>                              3    Output {as a number}
>                               3   Exit the program (due to low stack)
> ```
> The leading 7 and trailing 3 aren't necessary for the program's functionality, they're just there to get the prime factors of the output right. It helps to follow this program if you understand the numeric format; numbers are stored in a unary variant in which `1` and `7` increase the value by 1, and `0` and `6` decrease the value by 1 (thus appending `66` decreases the value by 2, repeating the number multiplies it, and so on). Input's done by repeating a stack element (thus if the stack element is `12345` and the input is \\$3\\$, the new stack element will be \\$123451234512345\\$).
> 4 votes

# Answer
# Node.js v10.9.0, 40 bytes, Score: 40, Cracked

### Input

This is a function taking exactly one parameter.

### Output

```
&`nij.9=j.,)r31n=+(=ooj`[o.o.)1.s](>=6>t

```
> 3 votes

# Answer
# A Pear Tree, 46 bytes of ASCII, score 0, Cracked

Input is taken from standard input. The expected output (on standard output) is an empty string (i.e. when the program is given itself as argument, no output should be printed).

In other words, the challenge here is to write an A Pear Tree program that does not output anything on standard output when given itself on standard input, and which does output something on standard output when given something other than itself on standard input, using no more than 46 bytes. (I've managed to do this while holding the program to printable ASCII, too, despite A Pear Tree frequently using non-ASCII and unprintable characters.) This is effectively the task of writing a self-identifying program, with a specific output format (i.e. null string when self-identification succeeds); however, A Pear Tree has at least two twists that make the task somewhat more difficult than it looks when done in this specific language (which is why I chose it for my cop submission).

## My solution

My solution is a bit different from the crack:

```
eval(k=q(print$\=$_="eval(k=q($k))"ne$_;MZpa))

```

Try it online!

Instead of using `exit`, I instead set `$_` (implicit output) and `$\` (newline after output, including implicit output) to the null string if there's a match (and to `1` if there's no match). A `print` is still required because implicit output is only enabled if there's at least one byte of input (thus, we need to explicitly print something if we're given an empty string as input, which is distinct from the program).

Every A Pear Tree program needs to contain a checksum somewhere (that's the `MZpa` in this solution). Both my solution and the crack pick variable names (and vary other minor details of the code) in order to make the checksum consist entirely of ASCII letters.
> 3 votes

# Answer
# Perl 5 `-p0777`, 10 bytes, score 10, safe

```
W)9r46<(k

```

The last character here is "shift out", character code 14 (decimal) / 0E (hex). All the others are printable ASCII.

Because we're using Perl's implicit I/O argument `-p0777`, the input is coming from standard input, and the output going to standard output.

## Solution

The program does the following:

> NUL-pads the input to at least 10 characters, then XORs with the string `svgOUT_TOP`

which means that the program itself, the only input producing the desired output, is:

> ```
> $_^=abc|$^
> ```

Try it online!

### Explanation

> Perl has a number of special-purpose variables. For example, when using `-p0777` for implicit I/O, `$_` is input at the start of the program and output at the end of the program.
>
> Most of these variables have a very simple default value. However, the default value of `$^`, the currently selected top-of-page format, is the much longer string `STDOUT_TOP`. As such, we can use this as a very terse obfuscation method via XORing `$^` with the value we want to obfuscate (in this case, the program).
>
> In order to hide the telltale `_TOP` at the end, I padded the program itself out to 10 characters via adding in an `abc|`, meaning that all the characters of `STDOUT_TOP` would be XORed with something; the choice of `abc|` at the start was an easy way to keep the output mostly printable (and to make it harder to spot that I was XORing with a string made mostly of capital letters, because in ASCII, lowercase XOR uppercase is lowercase).
> 3 votes

# Answer
# Python 3, 50 bytes cracked

Input and output from/to stdin/-out. Output is different for each and every different input. Unique output when given the source code:

```
218216195196222130136136132192197195196130241204136209197216206130201131244155157154215136138204197216138201138195196138195196218223222130131247131131

```

(That’s 150 digits)

Good luck!
> 3 votes

# Answer
# 05AB1E, 35 bytes, Score: 7

**Input:**
From `stdin`

**Output:**
`QÕ
Ƿe`
> 2 votes

# Answer
# Cubix, 18 bytes, Score 18, safe

It's a shame that this challenge didn't get more attention, but that's the way it goes sometimes. I was going to leave this unsafe, but decided to post the solution before I forgot about it.

This should be quite easy to crack.

**Input** from `stdin`

**Output**

```
$`*2aJPJ#74(o);89

```

**Edit:** I should mention that this expects the source in it's shortened form ... and now I've noticed that there is a missing byte (unprintable) from the result that I broke when I posted. Should copy out now. The hex values are `24 60 2a 13 32 61 4a 50 4a 23 37 34 28 6f 29 3b 38 39`

The concept was to remove print the first character and then remove the inverse index from the character, eg \[chars\]-\[0,len(\[chars\])..2\]

The code is

```
$r;#AoW\U-@</u.?;;

```

which maps onto the following cube

```
    $ r
    ; #
A o W \ U - @ <
/ u . ? ; ; . .
    . .
    . .

```

Try it here
> 2 votes

# Answer
# Jelly, 14 bytes, Score: 21, Safe

Both the program and output size are counted using Jelly codepage.

### Input

First command-line argument.

### Output

```
-§ḋẇ"*YdĖDƘ>Ẉed€Ç+æạɦ

```

---

### Solution

```
ØJiⱮÄÆNPḃØ⁵ịØJ

```

Try it online!
> 2 votes

# Answer
# JavaScript Firefox, \<10 bytes, Score: 52, from function argument input, Cracked

```
ZnVuY3Rpb24gYnRvYSgpIHsKICAgIFtuYXRpdmUgY29kZV0KfQ==

btoa

```

`btoa(btoa)` encodes the following string:

```
function btoa() {
    [native code]
}

```

which gives:

```
"ZnVuY3Rpb24gYnRvYSgpIHsKICAgIFtuYXRpdmUgY29kZV0KfQ=="

```

just copied
> 1 votes

# Answer
# , 26 bytes, Score: 52, Safe

The program is not a REPL, but a full script that accepts `stdin` and explicitly prints to `stdout`.

### Input

Standard input.

### Output

```
6fc42353c98217ef5a2908a3c63d090aa9a55b2558b61294e06a

```

No, it's not an encryption method.

---

### Solution

```
echo]hfd]257x#.3&u:stdin''
                   stdin'' Take the whole input
               3&u:        Convert to codepoints
         257x#.     Convert base 257 to integer
     hfd]           "Hex from Decimal"
echo]               Print to stdout

```

Try it online!
> 1 votes

# Answer
# GCC 61-\>61 bytes

```
70 4F 92 73 08 D4 03 E7 65 DC D6 89 B5 AD BA 90
97 26 31 10 F6 FA 0A 30 8F 24 69 0A A7 8B 59 9E
A2 42 D5 67 B8 12 3A 1E 9D 25 80 F9 6B 25 32 C2
EE 46 3F 8D 7E 0C 73 0F F0 93 C6 68 50

```

Full program, take input from stdin and output to stdout
> 1 votes

# Answer
# Perl 6, 43 bytes, Score: 15, from stdin

```
49671296789805

```
> 1 votes

# Answer
# Pepe, 23 bytes, score: 23, cracked by MickyT

**Input:**

standard

**Output:**

```
RDCbn@?K]<[G98765TSR^PO

```
> 1 votes

# Answer
# Keg, 6 bytes, Score: 6

**Input**

From `stdin`, using `?`

**Output**

```
5\x1c"\x1c"9

```

Mind you that those are escape sequences for unprintable bytes. Replace the escapes with the literal chars. Raw text available here

Good luck with this one! See y'all next week!
> 1 votes

# Answer
# Perl 6, 31 bytes, Score: 39, from stdin - Cracked

**Cracked here**

```
().1111111111112222235abcegijkmnorstvy

```

Crude solution. Might survive.
> 0 votes

---
Tags: code-challenge, cops-and-robbers
---