title: Refined Partitions

text:
# Question
Title: Refined Partitions
Consider an array of integers:

```
[1, 0, 9, 1, 3, 8]

```

There are a lot of ways to partition this list into consecutive sublists. Here are three:

```
A: [[1, 0, 9], [1, 3, 8]]
B: [[1], [0, 9], [1, 3], [8]]
C: [[1, 0], [9, 1], [3, 8]]

```

We will call a partition *Y* and refinement of another partition *X* if *X* can be obtained from *Y* by joining some of its sublists back together.

So `B` is a refinement of `A`: if we join the first two and the last two sublists back together, we obtain `A`. But `C` is *not* a refinement of `A`: we'd have to split up the `9` and the `1` in order to recover `A` from it. Also, any partition is trivially a refinement of itself.

Note that we're not allowed to rearrange any sublists or elements at any point.

## The Challenge

Given two partitions (lists of lists of integers) `X` and `Y`, determine whether `Y` is a refinement of `X`.

You may assume that the partitions will only contain integers from `0` to `9`, inclusive. You must not assume that `X` and `Y` are partitions of the same list (if they aren't, they also are not refinements of each other). `X` and/or `Y` may be empty but will never contain empty sublists.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input may be taken in any convenient string or list format. Since the elements will only be single-digit integers, you may choose to omit a delimiter within the sublists, but make sure that leading `0`s are possible. You may choose to take `X` and `Y` in opposite order.

Output should be truthy if `Y` is a refinement of `X` and falsy otherwise.

Your code must be able to solve each of the test cases below in 1 second on a reasonable desktop machine. (This is merely a sanity check to avoid simple brute force solutions.)

This is code golf, so the shortest answer (in bytes) wins.

## Test Cases

Each test case is on its own line, written as `X Y`. I'm using GolfScript/CJam-style array notation to save some horizontal space:

Truthy:

```
[] []
[[0]] [[0]]
[[1 0 9 1 3 8]] [[1 0 9] [1 3 8]]
[[1 0 9 1 3 8]] [[1 0 9 1 3] [8]]
[[1 0 9 1 3 8]] [[1] [0] [9] [1] [3] [8]]
[[1 0 9] [1 3 8]] [[1 0 9] [1 3 8]]
[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]
[[9 8 8 5 8 2 7] [5] [1 4] [2 0 0 6 0 8 4 2 6 4 2 3 7 8 7 3 9 5 7 9 8 2 9 5] [3 9 8] [7 1 4 9 7 4 5 9] [3 3 3] [9 0 7 8] [3 9 4 7 2 7 8 0 3 0] [8 2 2 7 3 9 3 2] [2 9 0 8 5 4 1 8 5 5 6 2 0 9 2 7 7 9 2 7] [3 6] [1 2 7 7 4 4 2 9]] [[9 8] [8] [5 8 2] [7] [5] [1 4] [2] [0 0 6] [0] [8 4 2] [6 4] [2] [3] [7 8] [7 3] [9] [5 7 9] [8 2] [9 5] [3] [9 8] [7 1 4] [9 7] [4 5 9] [3 3] [3] [9 0] [7 8] [3] [9] [4] [7 2] [7 8] [0] [3 0] [8 2] [2] [7 3] [9 3] [2] [2] [9] [0] [8 5 4] [1 8] [5 5] [6] [2 0] [9] [2] [7 7 9] [2 7] [3 6] [1 2] [7 7] [4 4 2] [9]]

```

Falsy:

```
[[0]] []
[[0]] [[1]]
[[1 0 9]] [[1 0 9] [1 3 8]]
[[1 0 9] [1 3 8]] [[1 0 9 1 3 8]]
[[1 0 9] [1 3 8]] [[1 0 9]]
[[1 0 9] [1 3 8]] [[1 0] [9]]
[[1 0 9] [1 3 8]] [[1 0] [9 1] [3 8]]
[[1] [0 9] [1 3] [8]] [[1 0 9] [1 3 8]]
[[9 8 8 5 8 2 7] [5] [1 4] [2 0 0 6 0 8 4 2 6 4 2 3 7 8 7 3 9 5 7 9 8 2 9 5] [3 9 8] [7 1 4 9 7 4 5 9] [3 3 3] [9 0 7 8] [3 9 4 7 2 7 8 0 3 0] [8 2 2 7 3 9 3 2] [2 9 0 8 5 4 1 8 5 5 6 2 0 9 2 7 7 9 2 7] [3 6] [1 2 7 7 4 4 2 9]] [[9 8] [8] [5 8 2] [7] [5 1] [4] [2] [0 0 6] [0] [8 4 2] [6 4] [2] [3] [7 8] [7 3] [9] [5 7 9] [8 2] [9 5] [3] [9 8] [7 1 4] [9 7] [4 5 9] [3 3] [3] [9 0] [7 8] [3] [9] [4] [7 2] [7 8] [0] [3 0] [8 2] [2] [7 3] [9 3] [2] [2] [9] [0] [8 5 4] [1 8] [5 5] [6] [2 0] [9] [2] [7 7 9] [2 7] [3 6] [1 2] [7 7] [4 4 2] [9]]

```

## Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

```
<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51719</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>
```

## Related Challenges

# Answer
> 8 votes
# CJam, ~~13~~ ~~10~~ 9 bytes

```
lr.-F-U-!

```

Try it online in the CJam interpreter.

*Thanks to @MartinBüttner for suggesting @edc65's ingenious input format.*

*Thanks to @jimmy23013 for improving the input format and golfing off 3 additonal bytes.*

### I/O

**Input**

Sublists are separated by `;` and from each other by `,`:

```
1;0;9,1;3;8
1,0;9,1;3,8

```

**Output**

```
1

```

### How it works

```
lr e# Read line and a whitespace-separated token from STDIN.
.- e# Vectorized difference. Pushes the differences of corresponding code points.
F- e# Remove all occurrences of 15 (';' - ',') from the array.
U- e# Remove all occurrences of 0 from the array.
!  e# Push 1 if the resulting array is empty and 0 if not.

```

For strings of different length, `.-` will leave characters in the array, which cannot be equal to the integers 0 or 15.

# Answer
> 9 votes
# Pyth, 19 bytes

```
&gF_m{.u+NYdYQqFsMQ

```

Try it online: Demonstration or Test harness

I'm using Pyth's tuple/list format as input. Simply replace the spaces of the test cases with commas.

### Explanation:

```
                     implicit: Q is the evaluated input
    m        Q       map each input list d to:
      .u   dY          reduce with intermediate states over d, initial value = []
        +NY              update initial value N with sum of N and Y (current element of d)
     {                 generate a set
   _                 invert
 gF                  check, if the first element is >= (superset) than the second
&                    and
                sMQ  check, if the joined lists of the input
              qF     are equal

```

Since the pseudo-code is still a little bit confusing, I'll demonstrate the algorithm using an example input.

```
Input: [[1,0,9],[1,3,8]],[[1],[0,9],[1,3],[8]]

```

The `.u+NYdY` part computes all continuous sublists, that contain the first element.

```
[[1,0,9],[1,3,8]]     => [[], [1,0,9], [1,0,9,1,3,8]]
[[1],[0,9],[1,3],[8]] => [[], [1], [1,0,9], [1,0,9,1,3], [1,0,9,1,3,8]]

```

`B` is a refinement of the `A`, iff each continuous sublist of `A` is also a continuous sublist of `B` (there's only one exception).

So I simply check, if the set of continuous sublists of `A` is a subset of the set of continuous sublists of `B` (`gF_m.u+NYdYQ`).

The only exception is, if the first input list contains less elements than the second input list. For instance `<Fm.u+YdYQ` would return `True` for the input `[[1]],[[1],[2]]`.

Therefore I also check if the joined lists are also equal `&...qFsMQ`.

# Answer
> 7 votes
# JavaScript (*ES6*), 67 ~~70~~

**Edit** 3 bytes saved thx @apsillers

Run the snippet below in Firefox to test

```
f=(a,b)=>a+''==b // same values in the lists ?
&![...a.join(' ')].some((c,p)=>c<','&b.join(c)[p]>c) // splits in a are present in b?

// TEST

out=x=>O.innerHTML += x+'\n';

OK=[
[[],[]],
[[[0]],[[0]]],
[[[1,0,9,1,3,8]],[[1,0,9],[1,3,8]]],
[[[1,0,9,1,3,8]],[[1,0,9,1,3],[8]]],
[[[1,0,9,1,3,8]],[[1],[0],[9],[1],[3],[8]]],
[[[1,0,9],[1,3,8]],[[1,0,9],[1,3,8]]],
[[[1,0,9],[1,3,8]],[[1],[0,9],[1,3],[8]]],
[[[9,8,8,5,8,2,7],[5],[1,4],[2,0,0,6,0,8,4,2,6,4,2,3,7,8,7,3,9,5,7,9,8,2,9,5],[3,9,8],[7,1,4,9,7,4,5,9],[3,3,3],[9,0,7,8],[3,9,4,7,2,7,8,0,3,0],[8,2,2,7,3,9,3,2],[2,9,0,8,5,4,1,8,5,5,6,2,0,9,2,7,7,9,2,7],[3,6],[1,2,7,7,4,4,2,9]],[[9,8],[8],[5,8,2],[7],[5],[1,4],[2],[0,0,6],[0],[8,4,2],[6,4],[2],[3],[7,8],[7,3],[9],[5,7,9],[8,2],[9,5],[3],[9,8],[7,1,4],[9,7],[4,5,9],[3,3],[3],[9,0],[7,8],[3],[9],[4],[7,2],[7,8],[0],[3,0],[8,2],[2],[7,3],[9,3],[2],[2],[9],[0],[8,5,4],[1,8],[5,5],[6],[2,0],[9],[2],[7,7,9],[2,7],[3,6],[1,2],[7,7],[4,4,2],[9]]]
];

KO=[
[[[0]],[]],
[[[0]],[[1]]],
[[[1,0,9]],[[1,0,9],[1,3,8]]],
[[[1,0,9],[1,3,8]],[[1,0,9,1,3,8]]],
[[[1,0,9],[1,3,8]],[[1,0,9]]],
[[[1,0,9],[1,3,8]],[[1,0],[9]]],
[[[1,0,9],[1,3,8]],[[1,0],[9,1],[3,8]]],
[[[1],[0,9],[1,3],[8]],[[1,0,9],[1,3,8]]],
[[[9,8,8,5,8,2,7],[5],[1,4],[2,0,0,6,0,8,4,2,6,4,2,3,7,8,7,3,9,5,7,9,8,2,9,5],[3,9,8],[7,1,4,9,7,4,5,9],[3,3,3],[9,0,7,8],[3,9,4,7,2,7,8,0,3,0],[8,2,2,7,3,9,3,2],[2,9,0,8,5,4,1,8,5,5,6,2,0,9,2,7,7,9,2,7],[3,6],[1,2,7,7,4,4,2,9]],[[9,8],[8],[5,8,2],[7],[5,1],[4],[2],[0,0,6],[0],[8,4,2],[6,4],[2],[3],[7,8],[7,3],[9],[5,7,9],[8,2],[9,5],[3],[9,8],[7,1,4],[9,7],[4,5,9],[3,3],[3],[9,0],[7,8],[3],[9],[4],[7,2],[7,8],[0],[3,0],[8,2],[2],[7,3],[9,3],[2],[2],[9],[0],[8,5,4],[1,8],[5,5],[6],[2,0],[9],[2],[7,7,9],[2,7],[3,6],[1,2],[7,7],[4,4,2],[9]]]
];

dump=l=>l.map(x=>'['+x+']').join(',');

out('YES');
OK.forEach(l=>out(f(l[0],l[1])+' a['+dump(l[0])+'] b['+dump(l[1])+']'));
out('NO');
KO.forEach(l=>out(f(l[0],l[1])+' a['+dump(l[0])+'] b['+dump(l[1])+']'));
```

```
<pre id=O></pre>
```

# Answer
> 7 votes
# C, 69 ~~75~~

A function with 2 string parameters, returning 0 or 1.

Parameter format: sublist separated with spaces (`' '`), list elements separated with commas.

Example: `"1,0,9 1,3,8"` `"1,0 9,1,3,8"`

```
f(char*a,char*b){for(;*a-44?*a&&*b==*a:*b<48;a++)b++;return!(*b|*a);}

```

*Less golfed*

```
int f(char *a, char *b)
{
    // expected in a,b: digit,separator,digit... with separator being ' ' or ','
    for(; *a; a++,b++)
       // ' ' or digit in a must be the same in b
       // comma in a must be comma or space in b
       if (*a != ',' ? *b != *a : *b > *a) return 0;
    return !*b; // must have a null in *b too
}

```

**Test** Ideone (outdated)

# Answer
> 6 votes
# Haskell, 76 bytes

```
[]#[]=1<2
[x]#[y]=x==y
x@(a:b)#(c:d:e)|a==c=b#(d:e)|1<2=x#((c++d):e)
_#_=2<1

```

Returns `True` or `False`. Example usage: `[[1,0,9],[1,3,8]] # [[1,0],[9]]` -\> `False`.

Simple recursive approach: if the first elements match, go on with the tails, else start over but concatenate the two elements at the front of the second list. Base cases are: both lists empty -\> `True`; both lists with a single element -\> compare them; only one list empty -\> `False`.

# Answer
> 6 votes
# CJam, 19 bytes

```
q~]{_,,\f>:sS.+}/-!

```

Try it online.

### I/O

Input

```
[[1 0 9] [1 3 8]] [[1] [0 9] [1 3] [8]]

```

Output

```
1

```

### Idea

Each partition can be uniquely identified by observing the following two properties:

* The list formed by concatenating all sublists.
* The "cutting points", including the extremes of the list.

We can combine both criteria into one by replacing each cutting point with the sublist of elements from the cutting point to the end of the list.

To verify that a given partition is finer than another, we only have to verify if the coarser partition, represented as above, is a subset of the finer one and that the largest lists of both partitions match.

### Code

```
q~]   e# Read from STDIN and evaluate.
{     e# For each array P from the input:
  _,, e#   Push [0 ... L], where L == length(P) - 1.
  \f> e#   Push [P[0:] ... P[L]].
  :s  e#   Stringify each P[k:] (flattens).
  S.+ e#   Vectorized concatenation. This appends a space to the first element.
}/    e#
-!    e# Push the logical NOT of the difference A-B to check if A is a subset of B.

```

For the input form the I/O example, the stack holds

```
["109138 " "138"] ["109138 " "09138" "138" "8"]

```

before executing `-!`.

Note that the first element of each array has a trailing space. This makes sure we compare the full list of the first input with the full list of the second.

# Answer
> 5 votes
# CJam, 24 bytes

```
l~L\{+_a2$1<={;1>L}&}/+!

```

**Algorithm**

Here we simply use a greedy algorithm to see if first `N` sub-lists of the second list can be merged together to form the first sub-list of the first list. Once such `N` is found, we remove the first `N` sub-lists from second list and the first sub-list from the first list and repeat the process.

Ideally, if the second list was a refinement of the first, we should be left with 2 empty lists on stack. We just check for that and print `1` if that is the case. In any other combination, after fully iterating over sub-lists of second list, we won't end up with 2 empty lists. Thus a `0` will be printed for such cases.

**Code expansion**

```
l~L\{+_a2$1<={;1>L}&}/+!
l~L\                       e# Read the line, evaluate the two lists and put an empty list
                           e# between them
    {               }/     e# Iterate over all sub-lists of the second list
     +                     e# Append the current sub-list to whatever is on stack. Originally
                           e# an empty array, but eventually the sum of first N sub-lists
      _a                   e# Copy this and wrap it in an array
        2$                 e# Copy the first list on top of stack
          1<               e# Get only its first element wrapped in an array. This approach
                           e# is exception safe in case the array was already 0 length
            ={    }&       e# If we have a match, remove both first sub-lists
              ;            e# Remove the first N sub-lists array
               1>          e# Remove the first element from the first array
                 L         e# Put an empty array on stack to repeat the process
                      +!   e# If we are left with two empty arrays, sum them and do logical
                           e# not to get 1. If any of the arrays is non-empty, logical not
                           e# gives 0

```

Try it online here or run the complete test suite here

# Answer
> 3 votes
# C, ~~120~~ 114 bytes

```
#define C(x),x+=(*x/93)*(1+!!x[1])|1
o;R(char*s,char*t){for(o=1;*s;o&=*s==t[2*(*t==93&&93>*s)]C(s)C(t));return o;}

```

I haven't golfed much recently, so I thought I'd try this one out.

We define a function `R(char* s, char* t)` which returns `1` if `t` is a refined partition of `s`, and `0` otherwise. `s` and `t` are expected to be in the format `[DDDD...][DDDD...]...` Where each `D` is another single-digit element.

Testing code:

```
#include "stdio.h"

int main(int argc, char** argv) {
    char* str1, *str2;
    str1 = "[109][138]";
    str2 = "[1][09][13][8]";
    printf("Input: %s, %s --> %d\n", str1, str2, R(str1, str2));

    str1 = "[109][138]";
    str2 = "[1][19][13][8]";
    printf("Input: %s, %s --> %d\n", str1, str2, R(str1, str2));

    str1 = "[109][138]";
    str2 = "[10][91][3][8]";
    printf("Input: %s, %s --> %d\n", str1, str2, R(str1, str2));
}

```

The above prints the following:

```
Input: [109][138], [1][09][13][8] --> 1
Input: [109][138], [1][19][13][8] --> 0
Input: [109][138], [10][91][3][8] --> 0

```

It seems to work, at least.

# Answer
> 3 votes
# Haskell, ~~52~~ ~~50~~ 53 bytes

```
x#y=and$zipWith(\a b->a==b||a==',')(x++"..")(y++"..")

```

Completely different from my other solution. Uses the same clever input format as @edc65's answer, i.e. elements are separated with `,` and lists with .

Usage example: `"1,0,9,1,3,8" # "1,0,9 1,3,8"` -\> `True`.

The second parameter is a refinement of the first, if they have either equal elements at every position or the first one is `,`. I have to append a unique end token (-\>`..`) to both parameters, because `zipWith` truncates the longer parameter and for example `"1,2,3" # "1,2"` would also be `True`.

# Answer
> 2 votes
# Python 2, ~~68~~ 51 bytes

Thanks to xnor for some considerable byte-savings!

Anonymous function that takes two strings of the form `"1,0,9 1,3,8"` (taken from edc65's C answer) and returns `True` or `False`. New version with `map(None)` no longer works in Python 3.

```
lambda a,b:all(i in[j,","]for i,j in map(None,a,b))

```

Test suite:

```
>>> def runTests(f):
    assert f("1,0,9 1,3,8","1 0,9 1,3 8")
    assert not f("1,0,9 1,3,8","1,0 9,1 3,8")
    assert f("1 0,9 1,3 8","1 0,9 1,3 8")
    assert not f("1 0,9 1,3 8","1,0,9 1,3,8")
    assert not f("1 0,9 1,3 8","1 0,9 1,3")
    assert not f("1 0,9 1,3,8","1 0,9 1,3")
    print("All tests pass.")

>>> runTests(lambda a,b:all(i in[j,","]for i,j in map(None,a,b)))
All tests pass.

```

Previous 92-byte solution that takes input as `"109 138"`:

```
def R(a,b):
 r=1
 for i in b.split():r&=a.find(i)==0;a=a[len(i):].strip()
 return r and""==a

```

# Answer
> 2 votes
# Mathematica, 65 bytes

```
f@__=1<0;{}~f~{}=1>0;{a_,b___}~f~{c__,d___}/;a==Join@c:={b}~f~{d}

```

# Answer
> 2 votes
Maths with regular expressions is fun!

# ES6 Javascript, 53 chars

```
(a,b)=>RegExp('^'+a.replace(/,/g,'[ ,]')+'$').test(b)

```

# Vintage Javascript, 70 chars

```
function f(a,b){return RegExp('^'+a.replace(/,/g,'[ ,]')+'$').test(b)

```

Uses the same input format as edc65's answer.

Full demo including all test cases here.

# Answer
> 2 votes
# Mathematica, 55 bytes

```
Equal@@Join@@@#&&SubsetQ@@(Accumulate[Length/@#]&)/@##&

```

This defines an unnamed function, taking the two partitions in a single list, in reverse order (i.e. `Y` first, `X` second).

## Explanation

```
Equal@@Join@@@#

```

This checks that both partitions are actually partitions of the same list.

```
SubsetQ@@(Accumulate[Length/@#]&)/@##

```

This is a golfed form of my approach in this question over on Mathematica.SE, which inspired this challenge. Basically, a partition is defined as a number of indices where splits are inserted, and this checks that all the splitting positions in `X` also appear in `Y` by accumulating the lengths of the sublists.

# Answer
> 1 votes
# Jelly, ~~7~~ 5 bytes

```
O_/²Ƒ

```

Try it online!

This implements Dennis' string-based algorithm, with a slight modification to the input format. Sublists are separated by `-` and from each other by `,` (e.g. `[[1], [0, 9], [1, 3], [8]] -> 1,0-9,1-3,8`). If this is too much of a stretch, Dennis' input format is 9 bytes

A pure array based method comes out at ~~10~~ 6 bytes.

```
ŒbF€€i

```

Try it online!

This takes inputs reversed (i.e. `X` on the right and `Y` on the left), and outputs a non-zero integer for truthy and zero for falsey. It's 2 bytes longer (`ŒbF€€iɗ@`) to take input the normal way around. This does time out on TIO for the 2 longest inputs however.

## How they work

The 5 byter is simply an adaptation of of Dennis' CJam answer into Jelly:

```
O_/²Ƒ - Main link. Take the pair [X, Y] on the left
O     - Convert everything to ordinals
 _/   - Element-wise subtraction
      - This results in:
      -   A list entirely containing 0s and 1s for truthy outputs
      -   A list consisting of at least one non-0 or 1 element for falsey outputs
   ²Ƒ - All elements are unchanged when squaring, i.e. all elements are 1 or 0

```

The 7 byter works as follows:

```
ŒbF€€i - Main link. Takes Y on the left and X on the right
Œb     - Generate all partitions of Y, yielding [[]] if Y is empty
    €  - Over each:
  F€   -   Flatten each sub-partition
       -  This has the effect of generating all possible concatenations of Y
     i  - Index of X in these concatenations, or 0 if not found

```

---
Tags: code-golf, array, decision-problem, set-partitions
---


title: Check if a matrix is a Toeplitz matrix

text:
# Question
Title: Check if a matrix is a Toeplitz matrix
You will be given a two-dimensional array and a number and you are asked to find whether the given matrix is Toeplitz or not. A matrix is a Toeplitz matrix if every descending diagonal, going from left to right, has only one distinct element. That is, it should be in the form:

## Input Format:

You will be given a function which will take `two-dimensional` matrix as argument.

## Output Format:

Return `1` from the function if the matrix is **Toeplitz**, else return `-1`.

## Constraints:

```
3 < n,m < 10,000,000

```

where `n` is the number of rows while `m` will be the number of columns.

## Sample Test Case:

```
Sample Input :
4
5
6 7 8 9 2
4 6 7 8 9
1 4 6 7 8
0 1 4 6 7

Sample Output :
1

```

### Scoring

This is , so the shortest answer in bytes wins.

# Answer
## Mathematica, 42 bytes

```
2Boole[#==ToeplitzMatrix[#&@@@#,#&@@#]]-1&

```

Mathematica doesn't have a built-in to check whether something is a Toeplitz matrix, but it does have a built-in to generate one. So we generate one from the first column (`#&@@@#`) and the first row (`#&@@#`) of the input and check whether it's equal to the input. To convert the `True`/`False` result to `1`/`-1` we use `Boole` (to give `1` or `0`) and then simply transform the result with `2x-1`.
> 7 votes

# Answer
# Octave, 30 bytes

I'm assuming I don't have to handle 1,000,000x1,000,000 matrices as it says in the challenge. This works for matrices that don't exceed the available memory (less than 1 TB in my case).

```
@(x)x==toeplitz(x(:,1),x(1,:))

```

Try it online!

This takes a matrix `x` as input and creates a Toeplitz matrix based on the values on the first column, and the first row. It will then check each element of the matrices for equality. IF all elements are equal then the input is a Toeplitz matrix.

The output will be a matrix of the same dimensions as the input. If there are any zeros in the output then that's considered falsy be Octave.

**Edit:**

Just noticed the strict output format:

This works for 41 bytes. It might be possible to golf off a byte or two from this version, but I hope the output rules will be relaxed a bit.

```
@(x)2*(0||(x==toeplitz(x(:,1),x(1,:))))-1

```
> 6 votes

# Answer
# Jelly, 5 bytes

```
ŒDE€Ạ

```

Try it online!

Following the definition here.

```
ŒDE€Ạ
ŒD     all diagonals
   €   for each diagonal ...
  E       all elements are equal
    Ạ  all diagonal return true

```
> 5 votes

# Answer
# 05AB1E, 11 bytes

```
Œ2ùvy`¦s¨QP

```

Try it online!

**Explanation**

```
Œ             # get all sublists of input
 2ù           # keep only those of length 2
   v          # for each such pair
    y`        # split to separate lists
      ¦       # remove the first element of the second list
       s¨     # remove the last element of the first list
         Q    # compare for equality
          P   # product of stack

```
> 5 votes

# Answer
# Haskell, 43 bytes

```
f(a:b:t)|init a==tail b=f$b:t|1>0= -1
f _=1

```

Try it online!
> 4 votes

# Answer
## Mathematica, 94 bytes

```
l=Length;If[l@Flatten[Union/@Table[#~Diagonal~k,{k,-l@#+1,l@#[[1]]-1}]]==l@#+l@#[[1]]-1,1,-1]&

```

input

> {{6, 7, 8, 9, 2}, {4, 6, 7, 8, 9}, {1, 4, 6, 7, 8}, {0, 1, 4, 6, 7}}

another one based on **Stewie Griffin**'s algorithm

## Mathematica, 44 bytes

```
If[#==#[[;;,1]]~ToeplitzMatrix~#[[1]],1,-1]&

```
> 3 votes

# Answer
# Java 7, ~~239~~ ~~233~~ ~~220~~ 113 bytes

```
int c(int[][]a){for(int i=a.length,j;i-->1;)for(j=a[0].length;j-->1;)if(a[i][j]!=a[i-1][j-1])return -1;return 1;}

```

-107 bytes after a tip of using a more efficient algorithm thanks to *@Neil*.

**Explanation:**

Try it here.

```
int c(int[][]a){                // Method with integer-matrix parameter and integer return-type
  for(int i=a.length,j;i-->1;)  //  Loop over the rows (excluding the first)
    for(j=a[0].length;j-->1;)   //   Loop over the columns (excluding the first)
      if(a[i][j]!=a[i-1][j-1])  //    If the current cell doesn't equal the one top-left of it:
        return -1;              //     Return -1
                                //   End of columns loop (implicit / single-line body)
                                //  End of rows loop (implicit / single-line body)
  return 1;                     //  Return 1
}                               // End of method

```
> 3 votes

# Answer
# Haskell, 51 bytes

`t` takes a list of lists of integers and returns an integer.

```
t m=1-sum[2|or$zipWith((.init).(/=).tail)=<<tail$m]

```

Try it online!

This could have been 39 or 38 bytes with truthy/falsy output.

The idea to use `init` was inspired by Emigna's 05AB1E answer, which uses a very similar method; before that I used a nested zipping.

# How it works

* `zipWith((.init).(/=).tail)=<<tail` is a point-free form of `\m->zipWith(\x y->tail x/=init y)(tail m)m`.
* This combines each consecutive pair of rows of `m`, checking if the first with first element removed is different from the second with second element removed.
* The `or` then combines the checks for all pairs of rows.
* `1-sum[2|...]` converts the output format.
> 3 votes

# Answer
# Husk, ~~6~~ 4 bytes

```
ΛE∂↔

```

Try it online!

-2 bytes from Zgarb.

My first Husk answer! (Language Of The Month)

Takes matrix as command line argument.

Returns length of longest diagonal for true, and 0 otherwise.

## Explanation

```
ΛE∂↔
   ↔ reverse the rows
  ∂  get antidiagonals
Λ    Check if all elements satisfy condition:
 E   Are all the elements equal?

```
> 3 votes

# Answer
## JavaScript (ES6), ~~65~~ 54 bytes

```
a=>a.some((b,i)=>i--&&b.some((c,j)=>c-a[i][j-1]))?-1:1

```
> 2 votes

# Answer
# Ruby, 54 bytes

```
->a,b,m{m.reduce{|x,y|x[0..-2]==y[1,b]?y:[]}.size<=>1}

```

Exactly as specified, can be golfed more if flexible input/output is accepted.

## Explanation:

Iterate on the matrix, and compare each line with the line above, shifted by one to the right. If they are different, use an empty array for the next iteration. At the end, return -1 if the final array is empty, or 1 if it's at least 2 elements (since the smallest possible matrix is 3x3, this is true if all comparisons return true)

Try it online!
> 2 votes

# Answer
# PHP, 70 bytes

```
<?=!preg_match('/\[([\d,]+?),\d+\],\[\d+,(?!\1)/',json_encode($_GET));

```
> 1 votes

# Answer
# Python, 108

```
r=range
f=lambda x,n,m:all([len(set([x[i][j] for i in r(n) for j in r(m) if j-i==k]))==1 for k in r(1-n,m)])

```

Not efficient at all since it touches every element `n+m` times while filtering for diagonals. Then checks if there are more than one unique element per diagonal.
> 1 votes

# Answer
# Axiom, 121 bytes

```
f(m)==(r:=nrows(m);c:=ncols(m);for i in 1..r-1 repeat for j in 1..c-1 repeat if m(i,j)~=m(i+1,j+1)then return false;true)

```

m has to be a Matrix of some element that allow ~=; ungolf it

```
f m ==
  r := nrows(m)
  c := ncols(m)
  for i in 1..(r - 1) repeat
    for j in 1..(c - 1) repeat
      if m(i,j)~=m(i + 1,j + 1)     then return(false)
  true

```
> 1 votes

# Answer
# , 48 bytes

```
pryr::f(all(x[-1,-1]==x[-nrow(x),-ncol(x)])*2-1)

```

Try it online!
> 1 votes

# Answer
# Retina, 148 bytes

```
m(1`\d+
$*#
1`#\n\d+\n
@
+`(#*)#@([^#\n]*(#*)\n)(.*)$
$1# $2$1@$4 #$3
@

+`##
# #
+(+s`^(\d+)\b(.*)^\1\b
$1$2#
s`.*^\d.*^\d.*
-1
)%`^[^- ]+ ?

\s+
1

```

Try it online!

An N×M input matrix

```
6 7 8 9 2 0
4 6 7 8 9 2
1 4 6 7 8 9
0 1 4 6 7 8

```

is first converted to an N×(N+M-1) matrix by aligning the diagonals this way:

```
# # # 6 7 8 9 2 0
# # 4 6 7 8 9 2 #
# 1 4 6 7 8 9 # #
0 1 4 6 7 8 # # #

```

and then the first column is repeatedly checked to contain a single unique number, and removed if this is so. The matrix is Toeplitz iff the output is blank.
> 1 votes

# Answer
# MATL, 11 bytes

```
T&Xd"@Xz&=v

```

Try it online!

The straightforward "construct a Toeplitz matrix and check against it" method, that the top few answers use, somehow felt boring to me (and it looks like that would be 1 byte longer anyway). So I went for the "check each diagonal only contains one unique value" method.

`T&Xd` \- Extract the diagonals of the input and create a new matrix with them as columns (padding with zeros as needed)

`"` \- iterate through the columns of that

`@Xz` \- push the iteration variable (the current column), and remove (padding) zeros from it

`&=` \- broadcast equality check \- this creates a matrix with all 1s (truthy) if all the remaining values are equal to one another, otherwise the matrix contains some 0s which is falsy

`v` \- concatenate result values together, to create one final result vector which is either truthy (all 1s) or falsey (some 0s)
> 1 votes

# Answer
# Japt, 9 bytes

I *think* this is right.

```
äÏÅeX¯JÃ×

```

Try it

```
äÏÅeX¯JÃ×     :Implicit input of 2D-array
ä             :Consecutive pairs
 Ï            :Reduced by
  Å           :  Slice the first element off the second array
   e          :  Check for equality with
    X         :    First array
     ¯J       :    Slice off the last element
       Ã      :End reduce
        ×     :Reduce by multiplication

```
> 1 votes

# Answer
## Clojure, 94 bytes

```
#(if(=(+ %2 %3 -1)(count(set(for[Z[zipmap][i r](Z(range)%)[j v](Z(range)r)][(- i j)v]))))1 -1)

```
> 0 votes

---
Tags: code-golf, grid, decision-problem, matrix
---


title: TTT: Turing Text Tape

text:
# Question
Title: TTT: Turing Text Tape
## Introduction

Ah, INTERCAL...
As much as I'd like encourage everyone to Try it Online, text output is just painful.
According to the docs it uses the "Turing Text Model". While an... *interesting* concept, using it is about as much fun as shooting yourself in the foot. And what do we do with a task like this? Automate it.

## The Turing Text Model

The characters INTERCAL knows are printed on a circular tape that can only be moved in the positive direction. Printing is done by passing tape head movement commands in an array to the `READ OUT` statement. Every ASCII character is written on the *inside* of that tape (The outside has the characters for the input on it, duh). This results in the characters' bytes being on the tape in reverse. Also the tape head moves backwards along the character list, because its positioning is based on the outside of the tape.
The head starts at position 0.

Now the magic starts. I'll be using Truttle1's explanation on how to achieve output.

1. Set up an array with the output length.
2. Fill the entries in the array with tape head movement values.
    1. Find the current character's ASCII value in binary
    2. Reverse it and convert back a number `n`.
    3. Subtract `n` from the current head postion and modulo by 256 if needed, resulting in a value `r`
    4. `r` is the value you need to store in the array
    5. The head is now at position `n`.
3. `DO READ OUT` the array.

## PLEASE NOTE

* Array is pre-initialized with `0`, first index is `1`
* INTERCAL uses extended 8-bit ASCII characters, hence the tape length of 256.
* Between 1/3rd and 1/5th of all lines have to start with `PLEASE`. Note that in that case you drop the `DO` for `GIVE UP` and `READ OUT`, but not for anything else, as seen in the examples.

## Challenge

Given an input string, output a valid INTERCAL program that prints that string and terminates.

## Examples

Prints "BUZZ"

```
DO ,1 <- #4
DO ,1 SUB #1 <- #190
DO ,1 SUB #2 <- #152
PLEASE DO ,1 SUB #3 <- #336
DO READ OUT ,1
PLEASE GIVE UP

```

Whitespace is optional. The following prints "FIZZ"

```
DO,1<-#4DO,1SUB#1<-#158DO,1SUB#2<-#208DO,1SUB#3<-#312PLEASEREADOUT,1PLEASEGIVEUP

```

(Examples shamelessly stolen from Truttle1's FizzBuzz program from the video.)

You can find an ungolfed reference implementation in python 3 here

## Rules

* No standard loopholes
* This is , shortest code wins.
* You can expect input \>= 1, ASCII characters only.
* The program may not throw any errors apart from `ICL774I RANDOM COMPILER BUG` and `ICL666I COMPILER HAS INDIGESTION`. First one happens at random, second one is C-Intercal running out of memory and circumventing that isn't part of the challenge

# Answer
# Python 3, 157 bytes

```
t=i=0
p=o='PLEASE'
for c in input():i+=1;k=int(f'{ord(c):08b}'[::-1],2);o+=i%4//3*p+f'DO,1SUB#{i}<-#{t-k&255}';t=k
print(f'DO,1<-#{i}{o}DOREADOUT,1DOGIVEUP')

```

Try it online!

This prints \\$n+3\\$ instructions, of which \\$\left\lfloor \frac{n+5}{4} \right\rfloor\\$ are polite. That ratio just barely fits in the \\$\[1/5, 1/3\]\\$ politeness interval for all \\$n \geq 1\\$.

-1 byte thanks to Neil.
> 8 votes

# Answer
# JavaScript (Node.js),  ~~156~~  148 bytes

```
s=>`DO,1<-#${Buffer(s).map(c=>o+=`${i++&&~i&3?'':'PLEASE'}DO,1SUB#${i}<-#`+(p-(g=k=>p=k--&&c>>k&1|g(k)*2)(8)&255),i=p=o=""),i+o}DOREADOUT,1DOGIVEUP`

```

Try it online!

Try the output in INTERCAL!

## How?

### Bit reversal

We use a recursive function to reverse the bits of the character **c**.

```
( g = k =>       // k = bit position counter
  k-- &&         // decrement k; if it was not 0:
    c >> k & 1   //   bring the k-th bit of c at position 0 and isolate it
    | g(k)       //   bitwise OR with a recursive call,
      * 2        //   whose result is doubled
)(8)             // initial call with k = 8

```

### Politeness

Starting with `i = 0`, we insert a polite statement whenever the following expression is falsy:

```
i++ && ~i & 3

```

This means that we insert a `PLEASE` for the first processed character, and then every 4 characters starting with the 3rd one.

Neither the leading instruction nor on the two trailing instructions are polite. They are marked as `L` and `TT` respectively in the following table.

```
 length | output structure   | politeness ratio
--------+--------------------+------------------
    1   | LPTT               |   1/ 4 = 0.250
    2   | LP-TT              |   1/ 5 = 0.200 <-- lower bound
    3   | LP-PTT             |   2/ 6 ≈ 0.333 <-- upper bound
    4   | LP-P-TT            |   2/ 7 ≈ 0.286
    5   | LP-P--TT           |   2/ 8 = 0.250
    6   | LP-P---TT          |   2/ 9 ≈ 0.222
    7   | LP-P---PTT         |   3/10 = 0.300
    8   | LP-P---P-TT        |   3/11 ≈ 0.273
    9   | LP-P---P--TT       |   3/12 = 0.250
   10   | LP-P---P---TT      |   3/13 ≈ 0.231
   11   | LP-P---P---PTT     |   4/14 ≈ 0.286
   12   | LP-P---P---P-TT    |   4/15 ≈ 0.267
   13   | LP-P---P---P--TT   |   4/16 = 0.250
   14   | LP-P---P---P---TT  |   4/17 ≈ 0.235
   15   | LP-P---P---P---PTT |   5/18 ≈ 0.278
   ..   | ...                |   1/5 < r < 1/3

```
> 5 votes

# Answer
# 05AB1E, ~~77~~ ~~74~~ 54 bytes

```
Ç₁+₁šbí€¨C¥(₁%€‘‚µ,1<-#1€·,1—¨#1<-#ÿ€·‚Ø€Ä,1‘J‘ÿ€·†¿€¾

```

-20 bytes by porting @UnrelatedString's Jelly answer, so make sure to upvote him!!

Outputs with spaces at `#1 DO,1 SUB#`,  `DO READ OUT`, and  `DO GIVE UP`.

Try it online or verify a few more test cases.

Try the output in INTERCAL.

**Explanation:**

```
Ç               # Convert the (implicit) input-string to a list of codepoint integers
 ₁+             # Add 256 to each value
   ₁š           # Prepend 256 at the front of the list
     b          # Convert each value to a binary string
      í         # Reverse each
       €¨       # Remove the last digit of each
         C      # Convert each from binary back to a base-10 integer
          ¥     # Take the forward differences (deltas) of this list
           (    # Negate each difference
            ₁%  # Take modulo-256 on each
€               # Map over each integer:
 ‘‚µ,1<-#1€·,1—¨#1<-#ÿ€·‚Ø€Ä,1‘
                #  Push dictionary string "PLEASE,1<-#1 DO,1 SUB#1<-#ÿ DO READ OUT",
                #  where the `ÿ` is automatically filled with the integer
   J            # Join this list of strings together
    ‘ÿ€·†¿€¾    # Push string "ÿ DO GIVE UP", where the `y` is filled with the string
                # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `‘‚µ,1<-#1€·,1—¨#1<-#ÿ€·‚Ø€Ä,1‘` is `"PLEASE,1<-#1 DO,1 SUB#1<-#ÿ DO READ OUT"` and `‘ÿ€·†¿€¾` is `"ÿ DO GIVE UP"`.
> 5 votes

# Answer
# Charcoal, ~~90~~ ~~89~~ 85 bytes

```
DO,1<-#ＩＬθ⊞υ⁰⭆θ⪫⟦×PLEASE⊖﹪κ³DO,1SUB#⊕κ<-#﹪⁻⊟υΣ⊞Ｏυ⍘⮌◧⍘℅ι !⁸ !²⁵⁶⟧ω”Z1∨？ＡE₂-πK↷Y:γüD0←✂

```

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

```
DO,1<-#ＩＬθ

```

Print the instruction to set the length of the output.

```
⊞υ⁰

```

Start with the head at position 0. The value is actually stored in the predefined empty list as we can modify the list's value later using the Pop and PushOperator functions rather than having to resort to a command.

```
⭆θ⪫⟦...⟧ω

```

Loop over the characters and print the concatenation of 5 expressions for each character. (This is slightly golfier as the concatenation automatically stringifies the two numeric values in the list).

```
×PLEASE⊖﹪κ³

```

Be polite every third character. There is also a `PLEASE` at the end, so that the politeness ratio is ¹⁄₄, ¹⁄₅, ²⁄₆, ²⁄₇, ²⁄₈, ³⁄₉, ³⁄₁₀, ³⁄₁₁ ... after which the politeness ratio tends towards ¹⁄₃.

```
DO,1SUB#⊕κ<-#

```

Print the 1-indexed index at the start of the instruction to output the character.

```
﹪⁻⊟υΣ⊞Ｏυ⍘⮌◧⍘℅ι !⁸ !²⁵⁶

```

Calculate the reversed binary of the current character, output the difference from the head, and update the head with the new reversed binary, all in one expression. The binary is encoded using space for `0` so that it can easily be padded to 8 bits, plus the use of strings avoids separators that would otherwise be necessary.

```
”Z1∨？ＡE₂-πK↷Y:γüD0←✂

```

Print the compressed trailing instructions to output the string and exit. The string compression means that I don't have to worry about optimising the number of times I output `PLEASE` any further.
> 4 votes

# Answer
# Python 3, 128 bytes

```
t=0
for c in input():n=int(f'{ord(c):08b}'[::-1],2);print(f'PLEASE,1<-#1DO,1SUB#1<-#{t-n&255}DOREADOUT,1');t=n
print('DOGIVEUP')

```

Try it online!

Produces similar output to my Jelly solution, but is just as much a modification of Lynn's Python solution.

Originally used Python 3.8's "walrus" operator, but it turned out shorter not to by 2 bytes.
> 3 votes

# Answer
# Jelly, ~~62~~ 59 bytes

```
OŻ+⁹BUṖ€Ḅ_Ɲ%⁹“!![ẓ,ȮFẈẋ⁹⁾V!ĖÐĊnß6ṛ»;;“Œ°þ[ṪȦṄ»Ʋ€;“©⁴Œ½OÐ»Œu

```

Try it online!

Uses an array length of 1 and prints repeatedly to save on indexing, and sets the length to one repeatedly to save on politeness logic: length-element-print forms a very convenient unit of 3.

Without string compression:

```
OŻ+⁹BUṖ€Ḅ_Ɲ%⁹“please,1<-#1do,1sub#1<-#”;;“doreadout,1”Ʋ€;“dogiveup”Œu

```

Try a result online!

```
O                                      Codepoints of input.
 Ż                                     Prepend zero,
  +⁹                                   add 256 to each,
    B                                  convert each to binary.
     U                                 Reverse each,
      Ṗ€                               remove last element from each,
        Ḅ                              convert from binary.
         _Ɲ                            Subtract all adjacent pairs,
           %⁹                          and modulo 256.
                         Ʋ€            Map:
                  ;                    prepend to the number
             “...»                     "please,1<-#1do,1sub#1<-#",
                   ;                   append to that
                    “...»              "doreadout,1".
                           ;“...»      Append "dogiveup" to the whole result
                                 Œu    and uppercase.

```
> 2 votes

---
Tags: code-golf, code-generation
---


title: Mountain range numbers

text:
# Question
Title: Mountain range numbers
# Mountain range number

A number is a mountain range number if the inequalities satisfied by their consecutive digits alternate. In a way, looking at the number's digits should exhibit a `/\/\/\...` or a `\/\/\/...` pattern.

More formally, if our number `n` has \\$k\\$ digits

$$n = d\_1d\_2d\_3\cdots d\_k$$

then `n` is a mountain range number if

$$\begin{cases}d\_1 \> d\_2 \\ d\_2 \< d\_3 \\ d\_3 \> d\_4 \\ \cdots \end{cases} \vee \begin{cases}d\_1 \< d\_2 \\ d\_2 \> d\_3 \\ d\_3 \< d\_4 \\ \cdots \end{cases}$$

# Your task

Given an integer with 3 or more digits, output a Truthy value if the number is a mountain range number or Falsy otherwise.

# Input

A positive integer `n` with 3 or more digits, in any reasonable format, e.g.

* Integer
* String
* List of digits

# Test cases

### Truthy

```
1324 -> Truthy
9191 -> Truthy
12121 -> Truthy
121212 -> Truthy
1212121 -> Truthy
19898 -> Truthy

```

### Falsy

(Added another Falsy test case as per the comments, some answers might not cover the 4422 test case)

```
123 -> Falsy
321 -> Falsy
4103 -> Falsy
2232 -> Falsy
1919199 -> Falsy
4422 -> Falsy

```

This is so shortest answer in bytes wins! Standard loopholes are forbidden.

# Answer
# , ~~44~~ 40 bytes

 crossed out 44 is still regular 44

-1 byte thanks to Giuseppe.

```
function(x,d=diff)all(d(sign(d(x)))^2>3)

```

Try it online!

Computes the differences of the signs of the differences of the input. These must all be equal to 2 or -2, i.e. the square must equal 4; checking that the square is \>3 is sufficient.

If two consecutive digits are equal, there will be a 0 in the signs of differences, leading to a difference of signs of differences equal to 1 or -1. If three consecutive digits are in ascending or descending order, then the corresponding differences will be of the same sign, leading to a difference of signs of differences equal to 0. If neither of these occurs, the number is a mountain range number.

---

Old version (included as it might be golfable):

# , ~~44~~ 43 bytes

-1 byte thanks to Giuseppe.

```
function(x)all(s<-sign(diff(x)),rle(s)$l<2)

```

Try it online!

Computes the signs of the differences of consecutive digits. Then verifies that

* none of the signs are 0s (would correspond to 2 equal consecutive digits);
* the runs of the signs are all equal to 1, i.e. no 2 consecutive signs are equal.
> 5 votes

# Answer
# 05AB1E, 6 bytes

```
¥ü*0‹P

```

Try it online!

With truthy and falsy reversed, this would be 5 bytes:

```
¥ü*dZ

```

TIO
> 5 votes

# Answer
# JavaScript (ES6),  ~~35~~  33 bytes

```
a=>!a.some(p=v=>a*(a=p-(p=v))>=0)

```

Try it online!

### Commented

```
a =>                // a[] = input list of digits,
                    //       re-used to store the last difference
  !a.some(          //
    p =             // initialize p to a non-numeric value
    v =>            // for each v in a[]:
      a * (         //   multiply a by
        a =         //     the new value of a defined as
          p -       //       the difference between p and
          (p = v)   //       the new value of p, which is v
      )             //
      >= 0          //   the test fails if this is non-negative
  )                 // end of some()

```
> 4 votes

# Answer
# Japt `-!`, 7 bytes

Takes input as a digit array.

```
äÎä* dÄ

```

Try it
> 3 votes

# Answer
# Jelly,  6 bytes

A benchmarking solution.

A monadic link taking as input the list of digits

```
I×Ɲ<0Ạ

```

You can try it online or verify all test cases.

```
I         Take the forward differences
  Ɲ       and for each pair,
 ×        multiply them together.
   <0     Check if those are below 0.
      Ạ   Check if this array of booleans only contains Truthy values.

```

*-1 byte* thanks to @79037662
> 3 votes

# Answer
# Haskell, ~~57~~ ~~55~~ ~~47~~ ~~44~~ 42 bytes

```
all(<0).z(*).z(-)
z f(x:s)=zipWith(f)s$x:s

```

Try it online!

Takes input as a list of digits.

* -2 by swapping the order of `s` and `x:s`
* -8 by using a different helper function
* -3 by using partial application and pointfree code
* -2 by excluding `f=` from the submission (which I didn't realize was allowed :P)

xnor improved my answer using `>>=`.
> 3 votes

# Answer
# APL+WIN, ~~17~~ ~~15~~ ~~12~~ 11 bytes

5 bytes saved thanks to Jo King & 1 byte thanks to Bubbler. Turning into a real team effort!

Prompts for list of digits:

```
×/0>2×/2-/⎕

```

Try it online! (Dyalog Classic)
> 3 votes

# Answer
# Python, 47 bytes

```
f=lambda a,b,*l:l==()or(a-b)*(b-l[0])*f(b,*l)<0

```

Try it online!

Takes input splatted like `f(1,2,3,4)`. Same idea as my second Haskell answer.
> 3 votes

# Answer
# Husk, 7 bytes

```
Λ<0Ẋ*Ẋ-

```

Try it online!

Algorithm taken from the APL answer.

## Explanation

```
Λ<0Ẋ*Ẋ-
     Ẋ- subtract pairs of consecutive elements
   Ẋ*   multiply pairs of consecutive elements
Λ       return truthy value if all elements are:
 <0     lesser than 0

```
> 3 votes

# Answer
# Jelly, (5?) 6 bytes

5 if we may invert the truthy/falsey output (strip the trailing `¬`).

```
IṠIỊẸ¬

```

**Try it online!**
> 2 votes

# Answer
# Bash, 147 144 bytes

```
M(){
a=${1:0:1}
d=x
i=1
while [ $i -lt ${#1} ]
do
b=${1:$i:1}
case $d$((a-b)) in
[ux]-*)d=d;;*0|u*|d-*)return 1;;*)d=u;;esac
a=$b
let i++
done
}

```

Try it online!

I seem to like trying shell submissions, and learned some bash-isms in golfing this one.

`$((a-b))` is equivalent to `$(( $a - $b ))` -- apparently you don't need the $ inside a $(( )) construct.

There is a ++ operator, works in $(( )) and in `let`

Subtracting letters is accepted, strangely. One of my samples in the TIO reads "xy", and apparently `$((a-b))` evaluates `a` to `x`, and then variable `x` to an empty string and the empty string as numeric zero, and comparable for b and y. If I set x and y in the environment, those values are used.

Edit: -3 bytes by not putting whitespace after ;;, thanks to S.S.Anne
> 2 votes

# Answer
# Haskell, 37 bytes

```
all(<0).g(*).g(-)
g=(=<<tail).zipWith

```

Try it online!

Takes the `zipWith`-based answer of 79037662 and generalizes out the pattern of

```
g(?) = \s->zipWith(?)(tail s)s

```

that applies the operator `(?)` to pairs of adjacent elements. This is shortened to the pointfree `g=(=<<tail).zipWith`.

We first apply `g(-)` to the input to take differences of consecutive elements, then `g(*)` to take products of those consecutive differences. Then, we check that these products are all negative, which means that consecutive differences must be opposite in sign.

---

# Haskell, 40 bytes

```
f(a:b:t)=t==[]||(a-b)*(b-t!!0)<0&&f(b:t)

```

Try it online!

The idea is a bit clearer to see in the slightly less-golfed form:

**42 bytes**

```
f(a:b:c:t)=(a-b)*(b-c)<0&&f(b:c:t)
f _=1>0

```

Try it online!

We check that the first three digits `(a,b,c)` have the `a->b` steps and `b->c` steps going opposite directions by checking that the differences `a-b` and `b-c` have opposite signs, that is, their product is negative. Then we recurse to the list without its first element until the list has fewer than 3 elements, where it's vacuously true.

An alternative to check suffixes directly turned out longer:

**43 bytes**

```
f l=and[(a-b)*(b-c)<0|a:b:c:t<-scanr(:)[]l]

```

Try it online!
> 2 votes

# Answer
# Python 2, ~~65~~ 58 bytes

```
lambda A:all((x-y)*(y-z)<0for x,y,z in zip(A,A[1:],A[2:]))

```

Try it online!
> 2 votes

# Answer
# Ruby `-nl`, ~~57~~ 41 bytes

Replaces each character in the input string with the `cmp` comparison (`<=>` in Ruby) between it and the next character `$'[0]` (if there is no next character, remove the character instead). Then, check if the resulting string consists entirely of alternating `1` and `-1`.

```
gsub(/./){$&<=>$'[0]}
p~/^1?(-11)*(-1)?$/

```

Try it online!

### Old Solution, 57 bytes

Check for duplicate consecutive numbers first by checking if the input string matches `/(.)\1/` and inverting it. If no such pairs are found, replace each character with `true` or `false` based on whether its `cmp` style comparisons (`<=>`) to the character before it `$`[-1]` and after it `$'[0]` are not equal. (If there is no character before or after it, the `<=>` returns `nil`, which is definitely not equal to whatever the other character comparison returns.) Finally, it checks if the result does *not* contain an `f` (meaning no falses were returned).

```
p ! ~/(.)\1/&&gsub(/./){($`[-1]<=>$&)!=($&<=>$'[0])}!~/f/

```

Try it online!
> 2 votes

# Answer
# Brachylog, 9 bytes

```
¬{s₃.o↙Ḋ}

```

Try it online!

Takes a list of digits as input.

### Explanation

```
¬{      }       It is impossible…
  s₃            …to find a subsequence of 3 elements…
    .o↙Ḋ        …which is already ordered

```

Slight subtility: `o↙Ḋ` is used to check whether the digits are increasing or decreasing. By default, `o` (which is the same as `o₀`) is for increasing order, and `o₁` is for decreasing order. By using `o↙Ḋ` ( being an integer between `0` and `9`), we check that the whole predicate is impossible for `o₀`, or `o₁`, or `o₂`, …, `o₉`. `o₂` to `o₉` are not implemented and thus will fail, which doesn’t impact the program as a whole.

If `true.` is an acceptable falsy value, and `false.` an acceptable truthy value (which I don’t think it should be), then you should be able to remove these 3 bytes: `¬{…}`.
> 2 votes

# Answer
# Excel (Insider build ver. 1912), 122 Bytes

```
A1 'Input
B1 =SEQUENCE(LEN(A1))
C1 =MID(A1,B1#,1)
D1 =SIGN(IF(NOT(B1#-1),C1-C2,C1#-INDEX(C1#,B1#-1)))
E1 =(SUM(D1#)=D1*ISODD(LEN(A1)))*PRODUCT(D1#) 'Output

```

Returns ±1 (truthy) or 0 (falsy)

Explanation (can add more detail if people are interested)

```
B1 =SEQUENCE(LEN(A1)) ' Generates a spill array from 1 to the length of the input
C1 =MID(A1,B1#,1) ' Splits characters into rows. Using each value in the spill array B1#
                  ' as a charcter index
D1 =SIGN(IF(NOT(B1#-1), ' Choose different value on the first cell
           C1-C2, ' Use the opposite of the first difference between digits
           C1#-INDEX(C1#,B1#-1))) ' get the difference between each digit and the previous
E1 =(SUM(D1#)=D1*ISODD(LEN(A1))) ' Sum the digit differences, if the
                                 ' input length is even check if 0, else check if equal to
                                 ' thefirst row of the differences
       *PRODUCT(D1#))            ' ensure there aren't any repeated digits

```

Tests
> 2 votes

# Answer
# , 15 bytes

```
[:*/0>2*/\2-/\]

```

Try it online!

*-7 bytes thanks to RGS's technique*
> 1 votes

# Answer
# Charcoal, ~~29~~ 27 bytes

```
ＵＭθ⁻ι§θ⊕κＵＭθ×ι§θ⊕κ›⁰⌈…θ⁻Ｌθ²

```

Try it online! Link is to verbose version of code. Takes input as a list of digits and outputs as a Charcoal boolean (`-` for a mountain range number, otherwise no output). Explanation:

```
ＵＭθ⁻ι§θ⊕κ

```

Take consecutive differences (cyclic, so includes difference between last and first digit).

```
ＵＭθ×ι§θ⊕κ

```

Take consecutive products (again, cyclic).

```
›⁰⌈…θ⁻Ｌθ²

```

All results bar the last two must be negative.
> 1 votes

# Answer
# Python 3, ~~101~~ \\$\cdots\\$ ~~103~~ 94 bytes

Added 13 bytes to fix error kindly pointed out by @ChasBrown.
Saved 9 bytes thanks to @ChasBrown!!!

```
def f(l):x=[a<b for a,b in zip(l[1:],l)];return all(a!=b for a,b in zip(x[1:]+l[1:],x[:-1]+l))

```

Try it online!
> 1 votes

# Answer
# Burlesque, 22 bytes

```
XX2COqcm^m2COPD{0.<}al

```

Try it online!

```
XX      # Explode into digits
2CO     # 2-grams ("abc"->{"ab" "bc"})
qcm^m   # Compare each via UFO operator
2CO     # 2-grams
PD      # Product
{0.<}al # All less than 0

```
> 1 votes

# Answer
# K (ngn/k), 14 bytes

```
&/0>2_*':-':$:

```

Try it online!

`$:` as string

`-':` subtract (as ascii codes) each prior; implicit 0 before first

`*':` multiply by each prior; implicit 1 before first

`2_` drop first 2 elements

`&/0>` all negative?
> 1 votes

# Answer
# Java (JDK), ~~95~~ 83 bytes

```
p->{int i=0,j=1;for(;p.length>-~++i;)j=(p[i-1]-p[i])*(p[i]-p[i+1])<0?j:0;return j;}

```

Try it online!

Thanks to all in the comments for improvements - especially bit-shifting which I never would have thought of!!
> 1 votes

# Answer
# C (gcc), 59 bytes

```
d;m(int*s){for(d=*s/s[1];s[1]&&s[1]/ *s-d;d^=1)s++;s=s[1];}

```

Takes as input a wide string of digits and returns zero if that number is a mountain range number.

*-12 bytes thanks to ceilingcat!*

Try it online!
> 1 votes

# Answer
# , 34 bytes

```
all((d=diff(scan()))[1]*d*.5:-1>0)

```

Try it online!

Alternately reverses signs of all differences, and then multiplies them all by first difference: mountain range sequences will all be positive

Would be 40 bytes if defined as a function instead, so apologies to Robin with whom this would tie without the `scan` for input.
> 1 votes

# Answer
# Scala, 63 bytes

```
_.sliding(3).forall(t=>t(0)<t(1)&t(1)>t(2)|t(0)>t(1)&t(1)<t(2))

```

Checks whether for all sliding triplets the center is strictly larger (or strictly smaller) than the previous element and the next element.

Try it online!
> 1 votes

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


# Question
Title: Bad matrix multiplication that gives the right answer
## Executive summary:

Print NxN matrices \\$A\\$ and \\$B\\$ where \\$ AB = 10A + B \\$. Largest N wins!

## Details:

Entrants in this challenge should choose an N. Submit a program that takes an input integer 'seed', and produces two full rank NxN matrices \\$A\\$ and \\$B\\$, where each element of \\$A\\$ and \\$B\\$ is an integer from 0 to 9, and \\$AB = 10A + B\\$. In addition, matrices A and B must have at least half of their elements nonzero. The output should always be the same for a given seed. Runtime of your program is not limited, however as evidence that it does finish you must post a sample seed, the output of your program given that seed, and the time taken to compute.

Input and output format is not restricted.

## Scoring:

First, largest N wins. Second, ties are broken by earliest submission.

## No hard coding:

In order to prevent hard coding, there must be at least 10 seeds that produce distinct outputs, where outputs are not distinct if they are equal after exchanging rows, exchanging columns, and or transposing the matrix. You don't need to worry about proving this for good faith solutions.

## Math Background / No Rules Below This Line

First of all, for a given candidate A, B is fixed: $$AB = 10A + B\\ A = 10AB^{-1} + I\\ I = 10B^{-1} + A^{-1}\\ B = 10(I - A^{-1})^{-1}\\ B = 10(I + (A - I)^{-1})$$

One approach is to take the eigendecomposition of A.

From before, $$ A = Q \Lambda\_A Q^{-1}\\ B = 10(I - A^{-1})^{-1}\\ B = 10(Q I Q^{-1} - Q \Lambda\_A^{-1} Q^{-1})^{-1}\\ B = Q(\frac{10}{(I - \Lambda\_A^{-1})})Q^{-1}\\\$$

This shows that A, B share eigenvectors Q, and their eigenvalues are assosciated by $$ \Lambda\_A \Lambda\_B = 10 \Lambda\_A + \Lambda\_B\\ $$

Interestingly, this proves that AB = BA, ie our matrices commute!

We can calculate the determinant of B as \\$10^N \frac{1}{\Pi\_i (1 - \frac{1}{\lambda\_{A,i}})}\\$ This is very suggestive, but doesn't immediately yield a way to pick a matrix A such that B is small positive integers.

Because A and B share eigenvectors, B can be written as a linear combination of \\$(I, A, A^2 ... ~ A^{N-1})\\$. For example,

$$A = \left(\begin{array}{rrr}1 & 2 & 4 \\1 & 1 & 3 \\1 & 1 & 1\end{array}\right), B = \left(\begin{array}{rrr}7 & 4 & 6 \\3 & 6 & 4 \\1 & 2 & 8\end{array}\right)$$

$$\Lambda\_A = \left(\begin{array}{rrr}-\sqrt{6} + 2 & 0 & 0 \\0 & \sqrt{6} + 2 & 0 \\0 & 0 & -1\end{array}\right), \Lambda\_B = \left(\begin{array}{rrr}-\sqrt{6} + 2 & 0 & 0 \\0 & \sqrt{6} + 2 & 0 \\0 & 0 & -1\end{array}\right)$$

We observe that \\$\Lambda\_B = \Lambda\_A^2 - 2 \Lambda\_A + 2I\\$, so \\$B = A^2 - 2A + 2\\$. In this case B is forced to be an integer matrix because it is possible to write B as an integer polynomial of A. If we can find large matrices where \\$10(I + (\Lambda\_A - I)^{-1})\\$ is an integer polynomial of \\$\Lambda\_A\\$, then that might provide an efficient solution.

Finally, if we write \\$A\\$ as \\$E + I\\$, then we can see some simplifications. \\$B = 10 * (E^{-1} + I)\\$, so B is an integer matrix as long as the determinant of E divides 10. With this E representation, our problem can become to find an integer matrix E such that $$ E + I \geq 0\\ E^{-1} + I \geq 0\\ |E| = \pm 10\\\$$

(Occasionally this will fail if an entry of \\$ E^{-1} + I \> 9\\$ )

This represents an improvement, because once we find a \[0-9\] matrix E with determinant \\$\pm 10 \\$ (such as by random search), then if there are only a small number of negative entries in \\$E^{-1}\\$ we can run determinant-preserving transformations on E such as permuting rows to move those negative entries onto the diagonal, where they are made positive by the \\$+I\\$

In addition, there is a name and wikipedia page for matrices like \\$E^{-1}\\$ where the off diagonal entries are all positive: A Metzler Matrix. Further literature search in that direction might bring up an efficient way to generate positive integer matrices with a determinant \\$\pm 10\\$ whose inverses are Metzler Matrices.

# Answer
> 7 votes
# Python, N = 7

Using variable neighborhood search over elementary row and column operations. Not every seed works quickly (or at all?), but seed 9 finds a solution for N = 7 in a few seconds.

```
$ time python3 search.py 7 9
[[0 3 6 6 1 6 6]
 [0 1 5 5 0 5 5]
 [1 3 1 2 1 8 1]
 [0 0 1 0 0 1 0]
 [1 7 9 9 0 9 9]
 [1 3 1 1 1 0 1]
 [0 0 1 1 0 1 1]]
[[5 5 1 1 0 4 0]
 [1 7 0 0 1 0 0]
 [0 0 9 4 0 1 5]
 [0 0 0 5 0 0 5]
 [2 2 1 1 7 4 0]
 [0 0 1 1 0 9 0]
 [0 2 0 0 0 0 0]]

real    0m4.909s
user    0m4.883s
sys     0m0.026s

```

### Code

```
import itertools
import sys

import numpy as np

def search(depth, C, D, best):
    A = C + I
    B = D + 10 * I
    x = np.r_[A, B].flatten()
    score = (
        np.maximum(0, np.maximum(x - 9, 1 - x)).sum()
        - min((A == 0).sum(), -(-n * n // 2))
        - min((B == 0).sum(), -(-n * n // 2))
        + 2 * n
        - np.linalg.matrix_rank(A)
        - np.linalg.matrix_rank(B)
    )
    if best is None or score < best:
        return C, D, score
    if depth == 0:
        return None

    tried = {}
    for i in reversed(range(n * (n - 1) * 5)):
        j = rng.integers(i + 1)
        mutation, tried[j] = tried.get(j, j), tried.get(i, i)
        p, mutation = divmod(mutation, (n - 1) * 5)
        q, mutation = divmod(mutation, 5)
        q = (p + q + 1) % n
        C1 = C.copy()
        D1 = D.copy()

        if mutation == 0:
            C1[p, :] += C1[q, :]
            D1[:, q] -= D1[:, p]
        elif mutation == 1:
            C1[p, :] -= C1[q, :]
            D1[:, q] += D1[:, p]
        elif mutation == 2:
            C1[:, p] += C1[:, q]
            D1[q, :] -= D1[p, :]
        elif mutation == 3:
            C1[:, p] -= C1[:, q]
            D1[q, :] += D1[p, :]
        elif p < q:
            C1[[p, q], :] = C1[[q, p], :]
            D1[:, [p, q]] = D1[:, [q, p]]
        else:
            C1[:, [p, q]] = C1[:, [q, p]]
            D1[[p, q], :] = D1[[q, p], :]

        ret = search(depth - 1, C1, D1, best)
        if ret is not None:
            return ret

    return None

n, seed = map(int, sys.argv[1:])
rng = np.random.default_rng(seed)
I = np.eye(n, dtype=int)
score = None
k = rng.integers(0, 8, n)
C = np.diag(np.array([-10, -5, -2, -1, 1, 2, 5, 10])[k])
D = np.diag(np.array([-1, -2, -5, -10, 10, 5, 2, 1])[k])
depth = 1

while score != 0:
    ret = search(depth, C, D, score)
    if ret is not None:
        C, D, score = ret
        depth = 0
    depth += 1

A = C + I
B = D + 10 * I
assert (A @ B == 10 * A + B).all()
print(A)
print(B)

```

# Answer
> 3 votes
**N = 2**

This is a naive brute force approach in R:

```
randomvalid <- function(N) {
  while (T) {
    X <- matrix(sample(10,N*N,T)-1,N)
    if (sum(X==0) < N*N/2 && qr(X)$rank == N)
      return(X)
  }
}

tryforever <- function(N) {
  i <- 1
  while (T) {
    i <- i + 1
    if (i %% 100000 == 0) print(sprintf("after %d tries...", i))
    A <- randomvalid(N)
    B <- randomvalid(N)
    if(all(A %*% B == 10*A + B)) {
      print(A)
      print(B)
      print(A %*% B)
    }
  }
}

# run tryforever(2) to find some solutions for N=2

```

Some solutions for N=2 are:

```
A  = [[ 3, 2],[ 6, 2]]
B  = [[ 9, 2],[ 6, 8]]
AB = [[39,22],[66,28]]

A  = [[ 6, 5],[ 3, 2]]
B  = [[ 9, 5],[ 3, 5]]
AB = [[69,55],[33,25]]

A  = [[ 6, 5],[ 9, 8]]
B  = [[ 3, 5],[ 9, 5]]
AB = [[63,55],[99,85]]

A  = [[ 3, 4],[ 8, 7]]
B  = [[ 7, 2],[ 4, 9]]
AB = [[37,42],[84,79]]

```

Valid solutions seem to be very rare, even for N=2 they pop up only once every few minutes. For N=3 I was not able to find any solution within hours by this approach.

So, let's see whether a mathematical or heuristical approach is able to beat my N=2 solution :)

# Answer
> 2 votes
# N = 4, Swi-Prolog

After all the math, my best result so far is a relatively naive solution in prolog.

```
:- use_module(library(clpfd)).

% N is the dot product of lists V1 and V2.
dot(V1, V2, N) :- maplist(product,V1,V2,P), my_sumlist(P,N).
product(N1,N2,N3) :- N3 #= N1*N2.

my_sumlist([], 0).
my_sumlist([H|T], N) :- my_sumlist(T, X), N #= X + H.

my_scamul(_, [], []).

my_scamul(K, [R|T], [R2|T2]):-
    my_rowmul(K, R, R2),
    my_scamul(K, T, T2).

my_rowmul(_, [], []).
my_rowmul(K, [V|T], [V2|T2]):-
    K * V #= V2,
    my_rowmul(K, T, T2).

addmat([], [], []).
addmat([HA|TA], [HB|TB], [HC|TC]):-
    addrow(HA, HB, HC),
    addmat(TA, TB, TC).

addrow([], [], []).
addrow([HA|TA], [HB|TB], [HC|TC]):-
    HA + HB #= HC,
    addrow(TA, TB, TC).

nn(NN) :-
    NN #= 4.

isMat([], 0).
isMat([H|T], N):-
    nn(NN),
    isRow(H, NN),
    isMat(T, Ns),
    Ns #= N - 1.

isRow([], 0).
isRow([H|T], N):-
    H in 1..9,
    isRow(T, Ns),
    Ns #= N - 1.

det([[E_0, E_1, E_2, E_3],
     [E_4, E_5, E_6, E_7],
     [E_8, E_9, E_10, E_11],
     [E_12, E_13, E_14, E_15]], 4, D):-
           D #= E_1*E_11*E_14*E_4 - E_1*E_10*E_15*E_4 - E_11*E_13*E_2*E_4 + E_10*E_13*E_3*E_4 - E_0*E_11*E_14*E_5 + E_0*E_10*E_15*E_5 + E_11*E_12*E_2*E_5 - E_10*E_12*E_3*E_5 - E_1*E_11*E_12*E_6 + E_0*E_11*E_13*E_6 + E_1*E_10*E_12*E_7 - E_0*E_10*E_13*E_7 - E_15*E_2*E_5*E_8 + E_14*E_3*E_5*E_8 + E_1*E_15*E_6*E_8 - E_13*E_3*E_6*E_8 - E_1*E_14*E_7*E_8 + E_13*E_2*E_7*E_8 + E_15*E_2*E_4*E_9 - E_14*E_3*E_4*E_9 - E_0*E_15*E_6*E_9 + E_12*E_3*E_6*E_9 + E_0*E_14*E_7*E_9 - E_12*E_2*E_7*E_9.

% Matrix multiplication with matrices represented
% as lists of lists. M3 is the product of M1 and M2
mmult(M1, M2, M3) :- transpose(M2,MT), maplist(mm_helper(MT), M1, M3).
mm_helper(M2, I1, M3) :- maplist(dot(I1), M2, M3).

problem(A, B, C, ABf):-
    nn(NN),
    isMat(A, NN),
    isMat(B, NN),
    my_scamul(10, A, AX),
    addmat(AX, B, C),
    mmult(A, B, C),
    append(A, B, AB),
    flatten(AB, ABf).

main(Seed):-
    problem(A, B, C, ABf),
    labeling([ff, random_value(Seed)], ABf),
    det(A, 4, Determinant),
    write_ln(A),
    write_ln(B),
    write_ln(C),
    write_ln(Determinant),
    Determinant #\= 0.

```

Sample Output with seed 20:

<pre><code>?- time(main(20))
|    .
[[8,8,3,6],[4,2,1,2],[5,3,1,2],[4,2,1,2]]
[[9,1,1,2],[1,5,1,2],[1,1,3,6],[1,5,1,2]]
[[89,81,31,62],[41,25,11,22],[51,31,13,26],[41,25,11,22]]
0
[[8,8,3,6],[4,2,1,2],[5,3,1,2],[4,3,1,1]]
[[9,2,1,1],[1,6,1,1],[1,4,3,3],[1,1,1,6]]
[[89,82,31,61],[41,26,11,21],[51,34,13,23],[41,31,11,16]]
-6
% 582,520,793 inferences, 33.623 CPU in 33.623 seconds (100% CPU, 17324911 Lips)
true
```
</code></pre>

# Answer
> 1 votes
# Julia, 9

I identify a class of full rank matrices for which the criterion `A*B = 10A + B` can be checked in constant time, `nxn`-matrices of the form

```
   a b b b . . . b
   b a b b       .
   b b a b       .
   b b b a       .
   .       .     .
   .         .   .
   .           a b
   b . . . . . b a

```

Then I do a random search for those matrices in this class fulfilling the criteria. As these are full, I can make block-matrices out of two random elements of the class get a half-filled larger solution.

```
using Random, LinearAlgebra
check(a1, a2, b1, b2, n, base) = a2 != 0 && a1*b1*n + a2*b1 + b2*a1 == base*a1 + b1 && a1*b1*n + a2*b1 + b2*a1 + a2*b2 == base*(a1 +a2) + b1 + b2

function generate(base=10)
    while true
        a1 = rand(1:base-1)
        b1 = rand(1:base-1)
        a2 = rand(-a1+1:base-1-a1)
        b2 = rand(-b1+1:base-1-b1)
        n = rand(1:10)
        if check(a1, a2, b1, b2, n, base)
            return a1*ones(Int, n, n) + a2*I, b1*ones(Int, n, n) + b2*I
        end
    end
end
nosp(A) = sum(A .== 0) <= size(A,1)*size(A,2)/2
fake(A, B) = rank(A) > 0 && rank(B) > 0 && nosp(A) && nosp(B) && A*B == 10*A + B

```

```
Random.seed!(333333333333); A1, B1 = generate()
A2, B2 = generate()
A = [A1 0I; 0I A2]
B =[B1 0I; 0I B2]
fake(A2, B2)

```

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

 6  1  1  1  1  1  0  0  0  0  0  0
 1  6  1  1  1  1  0  0  0  0  0  0
 1  1  6  1  1  1  0  0  0  0  0  0
 1  1  1  6  1  1  0  0  0  0  0  0
 1  1  1  1  6  1  0  0  0  0  0  0
 1  1  1  1  1  6  0  0  0  0  0  0
 0  0  0  0  0  0  6  1  1  1  1  1
 0  0  0  0  0  0  1  6  1  1  1  1
 0  0  0  0  0  0  1  1  6  1  1  1
 0  0  0  0  0  0  1  1  1  6  1  1
 0  0  0  0  0  0  1  1  1  1  6  1
 0  0  0  0  0  0  1  1  1  1  1  6

```

There are not too many valid pairs of them but there are ten distributed over the dimensions for base 10. It also produces only a single 12x12 solution therefore it was agreed to count the method at the level of the second largest solutions it produces, ie 9.

---
Tags: code-challenge, integer, linear-algebra
---


title: The longest period iterating quine

text:
# Question
Title: The longest period iterating quine
As we know, a quine is a program that outputs its own source code. However, it's also possible to write a program that outputs another, different program, that outputs the first program again. For example, the Python 2 program

```
x = '''x = {}
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3'''
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3

```

will, when run, output the following text:

```
print """x = '''x = {}
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3'''
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3"""

```

When run as a Python program, this will output the original code again. This is called an *iterating quine*. Because you have to run it twice to get the original code back, we say it has *period 2*. But of course, much higher periods are possible.

Your challenge is to write an iterating quine with as long a period as you can, in **100 bytes or less**, in the language of your choice. (Note that my example above doesn't fit this spec, as it's 119 bytes, including the trailing newline.)

Please note the following rules and clarifications:

* The usual quine rules apply, i.e. your program can't use language features that would let it access its own source code directly.
* The iterated outputs have to eventually loop back to exactly your original code, and you have to include a demonstration or proof that it will.
* You must also include an explanation of why the cycle is as long as you say it is. This doesn't have to be at the level of a mathematical proof, but it should be convincing to someone familiar with your language. (This rule is here because I expect some of the answers to involve very, very large numbers.)
* It's fine to say something like "at least 1,000,000 iterations" rather than giving the exact number, as long as you can prove that it is at least that long. In this case, your score would be 1,000,000. Otherwise, your score is the period of your quine.
* The 100 byte limit only applies to your initial program - the programs it outputs can be longer, though of course they'll eventually have to get back down to 100 bytes in order to output your original code.
* You can assume your machine has infinite RAM and infinite runtime, but you can't assume unlimited precision data types (such as integers) if your language doesn't have them. You *can* assume there is no limit to the length of input your parser can handle.
* The highest score wins.

Please note: there is an existing challenge called Quit Whining; Start Quining that also involves iterating quines. However, aside from being based on the same concept, these are completely different types of challenge. The other one is straight up code golf, whereas this one is (intentionally!) really a busy beaver problem in disguise. The techniques needed to produce a good answer to this question are likely to be very different from what's needed to answer the other question, and this is very much by design.

# Answer
> 10 votes
# PHP, period 2,100,000,000

Who would've thought that this is possible in PHP?! :-)

This is actually my first ever quine and it's 99 bytes long:

```
<?$i=1;$i*=21e8>$i;printf($a='<?$i=%d;$i*=21e8>$i;printf($a=%c%s%c,++$i,39,$a,39);',++$i,39,$a,39);

```

Although PHP supports bigger numbers than `2 * 10^8` by switching from `integer` to `double`, the increment no longer works (leads to an infinite loop) and I haven't found another solution which fits into the 100 bytes. Yet.

Proof is fairly simple, since it's just counting up on each iteration until it reaches the reset point at 2.1 billion.

Credits to dave, who posted the approach in pseudo code in the comments and to Bob Twells, from whom I copied the code for a minimal PHP quine.

Test program (sloooooow):

```
<?php
$o = file_get_contents('quine.php');
for ($i = 0; $i < 22e8; $i++) {
    if ($i%2==0) exec('php q > p'); else exec('php p > q');
    $a = file_get_contents(($i%2==0) ? 'p' : 'q');
    echo "\r" . str_pad($i,6,' ') . ":\t$a";
    if ($a == $o) {
        die;
    }
}

```

Well, at least I'm the first one to answer.

# Answer
> 8 votes
# Mathematica, period ~~E8.5678#3~~ ~~E2.1923#4~~ ~E6.2695#3#2

```
Print[ToString[#0, InputForm], "[", #1 - 1 /. 0 -> "Nest[#!,9,9^9^99!]", "]"] & [Nest[#!,9,9^9^99!]]

```

Note that the scores are described in Hyper-E notation. The iterations replace the final `Nest[#!,9,9^9^99!]` with the decimal expansions of `Nest[#!,9,9^9^99!]` \- 1, `Nest[#!,9,9^9^99!]` \- 2, `Nest[#!,9,9^9^99!]` \- 3, ..., 3, 2, 1, and back to `Nest[#!,9,9^9^99!]`.

# Answer
> 5 votes
# R, random period with expectation 2^19936-0.5

```
f=function(){
    options(scipen=50)
    body(f)[[4]]<<-sum(runif(623))
    0
    cat("f=")
    print(f)
}

```

R's default random number generator has a period of 2^19937-1 and equidistribution in 623 consecutive dimensions. Thus, somewhere (but only once) in its period will be a 623-long vector of zeroes. When we get there (and are aligned with the start of the sequence) the sum of the next 623 random U\[0,1\] numbers will be zero and we return to our original program.

Note that the program will with very high probability pass through the same non-zero state several times before returning to zero. For instance, the sum 311.5 is the most likely, and there are a great many ways that can happen, but the RNG allows the period for 0 to be longer than the period for 311.5.

# Answer
> 2 votes
# Python 2

**Period:** \\$9\uparrow((99\uparrow\uparrow(9\uparrow((99\uparrow\uparrow(9\uparrow((99\uparrow\uparrow(9\uparrow\uparrow5-1))\uparrow9)-1))\uparrow9)-1))\uparrow9)+1\\$

Thanks to @Bubbler for increasing period from \\$9\uparrow9\uparrow(99\uparrow\uparrow12)+1\\$ to now

```
b=0;s="print'b=%d;s=%r;exec s'%(-~b%eval('9**9'*eval('9**9'*eval('9**9'*9**9**9**9**9))),s)";exec s

```

Try it online!

In the code the `b=0` changes to `b=1` then `b=2` and so on until it reaches `b=decimal expansion of the period` then resets back to `b=0`

# Answer
> 1 votes
# JavaScript, period 9,007,199,254,700,000

Not going to win, but it was fun working with JavaScript on this challenge:

```
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),1-1||90071992547e5)

```

Follows the following cycle:

```
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),1-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),9007199254700000-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),9007199254699999-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),9007199254699998-1||90071992547e5)
// etc...
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),3-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),2-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),1-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),9007199254700000-1||90071992547e5)
// and so on

```

Note: You can make it 18 bytes shorter, while only removing only ~0.08% of the score, like so:

```
a="a=%s;console.log(a,uneval(a),%.0f-1||9e15)";console.log(a,uneval(a),1-1||9e15)

```

# Answer
> 1 votes
# C, period 2,100,000,000

```
unsigned long long i;main(a){i=1;i*=21e8>i;printf(a="ungisned long long i;main(a){i=%d;i*=21e8>i;printf(a=%c%s%2$c,++i,34,a);}",++i,34,a);}

```

Based off the PHP answer (obviously). Will update with explanation when I have time.

# Answer
> 1 votes
# C (gcc), 66 bytes, period 2^64

```
f(s){printf(s="f(s){printf(s=%c%s%1$c,34,s,%lu+1L);}",34,s,0+1L);}

```

Try it online!

2^64 numbers are available in a `unsigned long` integer. Therefore, a period of 2^64.

# Answer
> 1 votes
# GolfScript, period \\$f\_{\epsilon\_0+1}(126^{126})\\$

```
0".{(}{;]{{x):x;)[.]){+[]\\{[).{f]}{;]x*}if+}:f~~}{;}if.}do{]}x*~}).?:x*`,}if"":n;:c~c`n`":n;:c~c`n`

```

Try it online!

```
0"foo"":n;:c~c`n`":n;:c~c`n`
0"foo"":n;:c~c`n`"            # Push this number and these two strings
                  :n;         # Assign the second string to n and remove it from the stack
                     :c~      # Assign the first string to c and execute it
                        c`n`  # Push both strings with "" around
                              # n is automatically printed at the end of the program

```

Every time this code is executed it prints itsef but replaces the `0` by what `foo` does to it.

What `foo` does:

```
.{(}{;bar}if
.{ }{    }if    # Make a copy of the number and compare it to 0
  (             # If it is not 0, decrement
     ;bar       # If it is 0, replace it by a big number

```

Here is a version of this code with period 10, so we can see it working:

```
0".{(}{;9}if"":n;:c~c`n`":n;:c~c`n`

```

Try it online!

The other 66 bytes compute \\$Hydra(Hydra(Hydra(...)))\\$, where there are \\$126^{126}\\$ hydras.

```
]{{x):x;)[.]){+[]\{[).{f]}{;]x*}if+}:f~~}{;}if.}do{]}x*~}).?:x*`,
]                                                                   # Start with [""], which is equivalent to [[]]
 {                                                     ~})          # The ~}) becomes }126
                                                          .?:x*     # Assign 126^126 to x and execute the block that many times
  {                                           .}do{]}x*             # While the string is not [], redo everything but with a tree with x pairs of []
   x):x;                                                            # Increment x
        )[.])                                                       # Separate the last element and make a copy of it
             {                          }{ }if                      # If it is an empty array
                                          ;                         # False: delete it
              +[]\{[).{f]}{;]x*}if+}:f~~                            # True: execute this function that finds and cuts a head
              +[]\                                                  # Push an empty array under the top of the stack, this will be the outermost pair's parent
                  {                }:f~                             # Assign this function to f and execute it
                   [).                                              # Start a new array and get the last element of the previous array
                      {  }{    }if                                  # If it is an empty array
                       f]                                           # False: keep searching and after that close the array
                           ;]x*                                     # True: delete it, close the array and make x copies of it
                                  +                                 # Put it back in the parent array
                                       ~                            # Remove the outermost pair, which was the [] we added earlier
                                                               `,   # Parse it to a string and get the number of bytes

```

This is not exactly \\$Hydra(x)\\$, this never resets `x` and therefore \\$Hydra(x)\\$ is a lower bound.

Here is an example of it that takes a tree as input and outputs \\$Hydra(tree)+1\\$, this confirms it is working.

```
~1:x;{x):x;)[.]){+[]\{[).{f]}{;]x*}if+}:f~~}{;}if.}do x

```

Try it online!

\\$Hydra(n)\>f\_{\omega^{\omega^{...^{\omega^{\omega2+4}}}}}(5)\\$ with `n-3` copies of \\$\omega\\$. Because of the `n-3` and it starting with 5, this program's lower bound should actually be \\$f\_{\epsilon\_0+1}(126^{126}-k)\\$, where `k` is a small number, but that makes it uglier and I doubt it will have more impact on the answer than not resetting `x`.

# Answer
> 0 votes
# Gol\>\<\>, 70 bytes, period 325883196621297064957600206175719056476804879488288708188003274919860959534770101079512433396348062803055739640225395758790852315876868469390603793729639715908136196505908165227136154287969475839017544811926036808089596209081885772040898530121921794489026069641113281250

Other wise known as really big (3.25E270)

```
":1=l8:*6+=S&Q~:'~'=Q~~'H#'||lPffXfX=?1:1=Q$~$~|:1)lPffXfX(Q?:|r2ssH##

```

This is actually the an altered version of the answer I put on the 500 byte iterator

```
":1=l8:*6+=S&Q~:'~'=Q~~'H#'||//if last is equal to 1 and length is 71, delete the delete char, if the last char is '~', delete and push 'H#', which will later return to 'H##', completing the cycle!
lPffXfX=?1:1=Q$~$~|          //if length is equal to 15^15^15, then start delete process(append ascii one)
:1)lPffXfX(Q?:|              //if the last character is not 1 (the delete checker), and length is less than 15^15^15, duplicate the last value and append
r2ssH##                      //push the " to the front and output the whole thing

```

Hopefully I got the score right, and there are no bugs. There is no real way to *actually* calculate this value, it is theoretical. But man, that is a huge number!!!

Try it online!

---
Tags: code-challenge, quine, busy-beaver
---


title: Is it a Chen prime?

text:
# Question
Title: Is it a Chen prime?
A number is a Chen prime if it satisfies two conditions:

* It is prime itself
* Itself plus two is either a prime or a semi-prime.

A prime is a number where it has exactly two divisors and those divisors consist of itself and one.

A semi-prime is a number which is the product of two primes. (Note that 12 = 2\*2\*3 is not semi-prime, but 25 = 5\*5 is).

Your task is to determine if a number is a Chen prime. You should output any truthy value for yes and any falsy value for no.

The input will be any integer greater than or equal to one. It may also be taken as a string, character array, or an array or digits.

## Examples:

```
101 -> truthy
223 -> falsy
233 -> truthy
1 -> falsy

```

This is OEIS A109611.

This is, in part, inspired by Am I a Sophie Germain prime? which, unfortunately, got closed as a duplicate, so I'm posting a somewhat related challenge which isn't a duplicate.

# Answer
# Brachylog, 7 bytes

```
ṗ+₂ḋl≤2

```

Try it online!

### Explanation

```
ṗ         Input is prime
   ḋ      The prime factorization of…
 +₂       … Input + 2…
    l≤2   … has 2 or less elements

```
> 12 votes

# Answer
# 05AB1E, 8 bytes

```
p¹ÌÒg3‹*

```

Try it online!

### Explanation

```
p¹ÌÒg3‹*   Argument n
p          Push isPrime(n)
 ¹ÌÒ       Push list of prime factors of (n+2)
    g3‹    Length of list is lower than 3
       *   Multiplication of boolean values, 0 if either is 0 (false)

```
> 11 votes

# Answer
# Pyth, 10 bytes

```
&P_Q>3lP+2

```

Try it online!

**How?**

```
&P_Q>3lP+2  # input: Q
        +2  # Q + 2
       P    # prime factors
    >3l     # length lower than 3?
 P_Q        # Q is prime?
&           # and both results

```
> 6 votes

# Answer
# ArnoldC, 1339 bytes

```
LISTEN TO ME VERY CAREFULLY q
I NEED YOUR CLOTHES YOUR BOOTS AND YOUR MOTORCYCLE p
GIVE THESE PEOPLE AIR
HEY CHRISTMAS TREE c
YOU SET US UP 0
HEY CHRISTMAS TREE d
YOU SET US UP 0
HEY CHRISTMAS TREE l
YOU SET US UP p
STICK AROUND l
GET TO THE CHOPPER d
HERE IS MY INVITATION p
I LET HIM GO l
ENOUGH TALK
BECAUSE I'M GOING TO SAY PLEASE d
BULLSHIT
GET TO THE CHOPPER c
HERE IS MY INVITATION c
GET UP 1
ENOUGH TALK
YOU HAVE NO RESPECT FOR LOGIC
GET TO THE CHOPPER l
HERE IS MY INVITATION l
GET DOWN 1
ENOUGH TALK
CHILL
I'LL BE BACK c
HASTA LA VISTA, BABY
IT'S SHOWTIME
HEY CHRISTMAS TREE p
YOU SET US UP 0
GET YOUR ASS TO MARS p
DO IT NOW
I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY
HEY CHRISTMAS TREE n
YOU SET US UP 0
GET YOUR ASS TO MARS n
DO IT NOW q p
HEY CHRISTMAS TREE g
YOU SET US UP 42
GET TO THE CHOPPER g
HERE IS MY INVITATION n
YOU ARE NOT YOU YOU ARE ME 2
ENOUGH TALK
BECAUSE I'M GOING TO SAY PLEASE g
GET TO THE CHOPPER p
HERE IS MY INVITATION p
GET UP 2
ENOUGH TALK
GET YOUR ASS TO MARS n
DO IT NOW q p
GET TO THE CHOPPER g
HERE IS MY INVITATION 5
LET OFF SOME STEAM BENNET n
ENOUGH TALK
BECAUSE I'M GOING TO SAY PLEASE g
TALK TO THE HAND "t"
BULLSHIT
TALK TO THE HAND "f"
YOU HAVE NO RESPECT FOR LOGIC
BULLSHIT
TALK TO THE HAND "f"
YOU HAVE NO RESPECT FOR LOGIC
YOU HAVE BEEN TERMINATED

```

Try it online!

(This is my first post on codegolf.SE, please let me know if this is formatted incorrectly. I realize this byte count is not competitive, this is just for fun.)
> 6 votes

# Answer
# Jelly, 10 bytes

```
+2ÆfL<3aÆP

```

Try it online!
> 5 votes

# Answer
# Pari/GP, 29 bytes

The `3*isprime(n)` trick is stolen from Jonathan Allan 's answer.

```
n->bigomega(n+2)<3*isprime(n)

```

Try it online!
> 3 votes

# Answer
# Python with sympy,  ~~69~~  56 bytes

-13 bytes thanks to alephalpha (by upgrading to sympy 1.1 and using `primeomega(n+2)` to replace `sum(factorint(n+2).values())`)

*...taking over from Gryphon's deleted submission.*

```
from sympy import*
lambda n:primeomega(n+2)<3*isprime(n)

```

An unnamed function returning `True` for Chen primes and `False` otherwise.

Counts the factors of `n+2` by summing its prime factor's multiplicities.

Note that `3` is multiplied by `isprime(n)` before the `<` comparison is made, so for non-prime `n` the code tests if `n+2` has less than `0` factors (always yielding `False`), while for prime `n` it checks whether `n+2` is prime or semi-prime.
> 3 votes

# Answer
# Java 8, ~~85~~ ~~84~~ 83 bytes

```
n->{int a=n+2,b=0,c=0,i=1;for(;i++<n;b+=n%i<1?1:0)c+=a%i<1?1:0;return n>1&b<2&c<3;}

```

-1 bytes thanks to *@OlivierGrégoire* by using an iterative approach instead of recursive.

**Explanation:**

Try it here.

```
n->{            // Method with integer parameter and boolean return-type
  int a=n+2,    //  Start `a` at the input + 2
      b=0,c=0,  //  Start `b` and `c` at 0
      i=1;      //  Start `i` at 1
  for(;i++<n;   //  Loop from 1 to `n` (and raise `i` immediately by 1)
    b+=n%i<1?   //   If the input is divisible by `i`
        1       //    Raise `b` by 1
       :        //   Else:
        0)      //    Leave `b` as is
    c+=a%i<1?   //   If the input + 2 is divisible by `i`:
        1       //    Raise `c` by 1
       :        //   Else:
        0;      //    Leave `c` as is
                //  End of loop (implicit / single-line body)
  return n>1    //  Return if the input is larger than 1
         &b<2   //   And `b` is now smaller than 2
         &c<3;  //   And `c` is now smaller than 3
}               // End of method

```
> 3 votes

# Answer
# JavaScript (ES6), ~~63~~ 61 bytes

```
g=(e,i=e)=>i--<3?1:e%i?g(e,i):g(i)+1
f=e=>e>1&g(e)<2&g(e+2)<3
```

```
Test cases:<br><textarea id=i rows=6 oninput="go()">101
223
233
1</textarea><br><pre id=q></pre><script>window.onload=function go(){document.getElementById('q').innerHTML=document.getElementById('i').value.split('\n').map(e=>e+' -> '+f(+e)).join('\n')}</script>
```

Defines a function `f` that takes `n` as argument and returns the result. Im very happy with how `g` turned out; it counts the number of prime factors in a number.

*2 bytes saves thanks to Kevin Cruijssen's `&` trick.*

### Ungolfed

```
Ω = (n,          // Ω(n) = number of n's prime factors, n > 1.
    i = n) =>    // Start iterating from i = n - 1. Since we'll immediately
                 // decrement i, n is used here.
    --i          // Immediately decrement i.

    < 2          // If i = 0 or i = 1, n is a prime at this point.
    ? 1 :        // Therefore Ω(n) = 1.

    n % i != 0 ? // If n is not divisible by i,
    Ω(n, i)      // try again with i := i - 1 (immediately decremented, so use i).

    : Ω(i) + 1   // n is divisible by i. Since we're counting down from n - 1
                 // and i is the first such number, i is n's largest non-trivial
                 // divisor, and thus n/i is a prime.
                 // Therefore Ω(n) = Ω(i) + Ω(n/i) = Ω(i) + 1.

is_chen = n =>     // An integer n ≥ 1 is a Chen prime if and only if:
    n > 1          // n > 1,
    & Ω(n) < 2     // Ω(n) = 1 < 2, i.e. n is a prime, and
    & Ω(n + 2) < 3 // Ω(n + 2) < 3, i.e. n + 2 is a prime or a semiprime.

```
> 2 votes

# Answer
# Japt, ~~22~~ ~~20~~ ~~19~~ ~~13~~ 12 bytes

```
U°j ©2¨°Uk l

```
* 6 bytes saved thanks to obarakon's suggestion of a different method.

Test it
> 2 votes

# Answer
# Mathematica, 28 bytes

```
PrimeQ@#&&PrimeOmega[#+2]<3&

```
> 2 votes

# Answer
# PHP, 64 bytes

```
for($i=$n=$argn+2;--$i;$argn%$i?:$q++)$n%$i?:++$p;echo$p<4^--$q;

```

prints `0` for truthy, other integers for falsy. Run as pipe with `-nR` or try it online.

**breakdown**

```
for($i=$n=$argn+2;--$i; # loop $i from N+1 to 1
    $argn%$i?:$q++)         # if $i divides N, increment $q
    $n%$i?:++$p;            # if $i divides N+2, increment $p
echo$p<4                # $p is 1 for a prime, 3 for a semiprime
    ^--$q;              # $q is 2 for prime; so this is 1^1 (==0) for a Chen Prime

```

**consistent falsy value, 65 bytes:**

```
for($i=$n=2+$k=$argn;--$i;$k%$i?:$q++)$n%$i?:++$p;echo$p<4&$q==2;

```

prints `1` for truthy and `0` for falsy.
> 2 votes

# Answer
# Regex (ECMAScript), 31 bytes

```
^(?!((xx+)(\2(xx))*)(\1\4)+$)xx

```

Try it online! (showing all Chen primes ≤ 1000)

Given a string of **n** `x`s this regex will match if and only if **n** is a Chen prime.

It asserts that **n** is greater than 2 and that the string is not of the form `((xx+)(\2(xx))*)(\1\4)+`
This regex has two meanings, depending on how many times `(\2(xx))` is repeated.
When it is repeated 0 times, the regex can be simplified to `(xx+)\1+`, which matches composite numbers.
When it is repeated a positive number of times, the regex is equivalent to `((xx+)(\2xx)+)(\1xx)+`

That regex requires some explanation, however, I will provide little insight.
If you go through the algebra you find that `((xx+)(\2xx)+)(\1xx)+` matches numbers of the form `a*b*c-2` where `a≥4,b≥2,c≥2`.
So it will match (almost) whenever **n**+2 has more than 2 prime factors. (i.e neither prime nor semi-prime)
Note that it doesn't match 6, 10, 16 or 25, but that this doesn't matter, because they are all composite.

So `(?!((xx+)(\2(xx))*)(\1\4)+$)` will match as long as **n** is not composite, and **n**+2 is either prime or semi-prime.
Unfortunately this includes 1 (and 0), so we then check that **n** is at least 2 with `xx`

A couple of different "31-byters" are:

```
^xx(?!((x*)(\2xx)+)\1?(\1xx)*$)
^(?!(xx((x*)(\3xx)+))\2?\1*$)xx

```
> 2 votes

# Answer
# Python 3 with SymPy, ~~73~~ 71 bytes

```
lambda n:(sum(factorint(n+2).values())<3)&isprime(n)
from sympy import*

```

Try it online!

---

This is a more-golfed version of an answer posted here earlier, but it seems to have been deleted.

---

Thanks to @JonathanAllan for saving 2 bytes!
> 1 votes

# Answer
# PHP, 87 bytes

```
for($b=($a=$argn)+$i=2;2<$a+$b;)$a%$i?$b%$i?$i++:++$d*$b/=$i:++$c*$a/=$i;echo$c<2&$d<3;

```

Try it online!

# PHP, 87 bytes

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

```

Try it online!
> 1 votes

# Answer
# APL NARS, 23 chars

```
{1≥⍵:0⋄(1=⍴π⍵)∧3>⍴π⍵+2}

```

Here π⍵ return the array of factors of ⍵ different from 1; some test:

```
  f←{1≥⍵:0⋄(1=⍴π⍵)∧3>⍴π⍵+2}
  f 101
1
  f 223
0
  f 233
1
  f 1
0
  f ¯10
0

```
> 1 votes

# Answer
# Ruby, ~~49~~ 41 bytes

```
->n{/^(.?|((..+)\3+))(\2+|..)$/!~?l*n+=2}

```

Try it online!

Thanks H.PWiz for -8 bytes

### How?

First thing, get a string of `'l'` repeated n+2 times. Then apply a regex to check if:

* Length is 2 or 3 `(.?)(..)`
* Length is a composite number plus 2 `((..+)\1)(..)`
* Length is a product of at least 3 numbers `((..+)\2)\1+`

The 2 regex parts generate a fourth case which doesn't make sense and is safe to ignore: `(.?)\2+`, that resolves to empty string or a single character because `\2` is empty.
> 1 votes

# Answer
# Husk, 9 bytes

```
&<3Lp+2¹ṗ

```

Try it online!

## Explanation

```
&<3Lp+2¹ṗ
        ṗ input is prime?
&         and
   L      Length of
    p     prime factorization of
     +2¹  input + 2
 <3       less than 3?

```
> 1 votes

# Answer
# Julia, 59 bytes

```
x->((0∉x%(2:x-1))&(length(find(x->x==0,(x+2)%(2:x)))<=2))

```
> 0 votes

# Answer
# Pyt, 11 bytes

3\*isprime(x) stolen from Jonathan Allan's answer

```
←Đṗ3*⇹2+ḋŁ>

```
> 0 votes

# Answer
# Haskell, 163 bytes

```
p k=last$(not$elem 0(map(mod k)[2..k-1])):[1>2|k<=1]
r=round
s n=p(r n)||any(\(a,b)->p(r a)&&p(r b))[(n/x,x)|x<-[2..n],n/x==(fromIntegral.r)n/x]
c n=p(r n)&&s(n+2)

```

Try it online!
> 0 votes

---
Tags: code-golf, number, number-theory, decision-problem, primes
---


title: Find all the Anagrams!

text:
# Question
Title: Find all the Anagrams!
Despite having 17 questions tagged , we still don't have this question, so here it is.

## Your Task

You must write a program or function that, when receiving a string, prints out all possible anagrams of it. For the purposes of this question, an anagram is a string that contains the same character as the original string, but is not an exact copy of the original string. An anagram does not have to be or contain actual words.

## Input

You may accept the string, which may be of any length \> 0, by any standard input method. It may contain any ASCII characters.

## Output

You may output all of the possible anagrams of the inputted string in any standard way. You must not output the same string twice, or output a string equal to the input.

## Other Rules

Standard Loopholes are disallowed

## Scoring

This is , least bytes wins.

# Answer
# 05AB1E, 3 bytes

```
œÙ¦

```

A function that leaves the stack with a list of the anagrams on top (and as its only item). As a full program prints a representation of that list.

**Try it online!**

### How?

```
    - push input
œ   - pop and push a list of all permutations (input appears at the head)
 Ù  - pop and push a list of unique items (sorted by first appearance)
  ¦ - pop and push a dequeued list (removes the occurrence of the input)
    - As a full program: implicit print of the top of the stack

```
> 10 votes

# Answer
# Ruby, 45 bytes

```
->x{(x.chars.permutation.map(&:join)-[x])|[]}

```

Try it online!

Despite having a built-in, the word "permutation" is really long :(
> 4 votes

# Answer
# pyth, 8 4

```
-{.p

```

Online test.

```
  .pQ     # all permutations of the (implicit) input string
 {        # de-duplicate
-    Q    # subtract (implicit) input

```
> 3 votes

# Answer
# Japt, 6 bytes

```
á â kU

```

Try it online!

### Explanation

```
 á â kU
Uá â kU   // Ungolfed
          // Implicit: U = input string
Uá        // Take all permutations of U.
   â      // Remove duplicates.
     kU   // Remove U itself from the result.
          // Implicit: output resulting array, separated by commas

```
> 3 votes

# Answer
# MATL, 7 bytes

```
tY@1&X~

```

Try it online!

### Explanation

```
t     % Implicitly input a string, say of length n. Duplicate
Y@    % All permutations. May contain duplicates. Gives a 2D char array of
      % size n!×n with each permutation in a row
1&X~  % Set symmetric difference, row-wise. Automatically removes duplicates.
      % This takes the n!×n char array and the input string (1×n char array)
      % and produces an m×n char array containing the rows that are present
      % in exactly one of the two arrays
      % Implicitly display

```
> 3 votes

# Answer
# Haskell, ~~48~~ 40 bytes

```
import Data.List
a=tail.nub.permutations

```

Try it online!

*Saved 8 bytes thanks to Leo's `tail` tip.*
> 3 votes

# Answer
# CJam, 8 bytes

```
l_e!\a-p

```

Try it online!

### Explanation

```
l    e# Read string from input
_    e# Duplicate
e!   e# Unique permutations. Gives a list of strings
\    e# Swap
a    e# Wrap in a singleton array
-    e# Set difference. This removes the input string
p    e# Pretty print the list

```
> 2 votes

# Answer
# Jelly, 4 bytes

```
Œ!QḊ

```

A monadic link taking a list of characters and returning a list of lists of characters - all distinct anagrams that are not equal to the input.

**Try it online!** (the footer forms a program that joins the list by newlines and prints to avoid the otherwise smashed representation).

### How?

```
Œ!QḊ - Link: list of characters     e.g. "text"
Œ!   - all permutations of the list      ["text","tetx","txet","txte","ttex","ttxe","etxt","ettx","extt","extt","ettx","etxt","xtet","xtte","xett","xett","xtte","xtet","ttex","ttxe","tetx","text","txte","txet"]
  Q  - de-duplicate                      ["text","tetx","txet","txte","ttex","ttxe","etxt","ettx","extt","xtet","xtte","xett"]
   Ḋ - dequeue (the first one = input)          ["tetx","txet","txte","ttex","ttxe","etxt","ettx","extt","xtet","xtte","xett"]

```
> 2 votes

# Answer
# Mathematica, 47 bytes

```
Drop[StringJoin/@Permutations[Characters@#],1]&

```
> 2 votes

# Answer
## Python 3, 85 76 63 bytes

As a function, and returning strings as list of characters (thanks to @pizzapants184 for telling me it is allowed):

```
from itertools import*
lambda z:set(permutations(z))-{tuple(z)}

```

As a function:

```
from itertools import*
lambda z:map("".join,set(permutations(z))-{tuple(z)})

```

85 bytes as a full program:

```
from itertools import*
z=input()
print(*map("".join,set(permutations(z))-{tuple(z)}))

```

Could be reduced a bit if outputting strings as ('a', 'b', 'c') is allowed (I am not sure it is).
> 2 votes

# Answer
# Java 8, ~~245~~ ~~239~~ ~~236~~ 232 bytes

```
import java.util.*;s->{Set l=new HashSet();p("",s,l);l.remove(s);l.forEach(System.out::println);}void p(String p,String s,Set l){int n=s.length(),i=0;if(n<1)l.add(p);for(;i<n;)p(p+s.charAt(i),s.substring(0,i)+s.substring(++i,n),l);}

```

-6 bytes thanks to *@OlivierGrégoire*
-4 bytes thanks to *@ceilingcat*

Typical verbose Java.. I see a lot of \<10 byte answers, and here I am with 200+ bytes.. XD

**Explanation:**

Try it here.

```
import java.util.*;         // Required import for the Set and HashSet

s->{                        // Method with String parameter and no return-type
  Set l=new HashSet();      //  Set to save all permutations in (without duplicates)
  p("",s);                  //  Determine all permutations, and save them in the Set
  l.remove(s);              //  Remove the input from the Set
  l.forEach(                //  Loop over the Set
    System.out::println);}  //   And print all the items

// This method will determine all permutations, and save them in the Set:
void p(String p,String s,Set l){
  int n=s.length(),         //  Length of the first input String
      i=0;                  //  Index-integer `i`, starting at 0
  if(n<1)                   //  If the length is 0:
    l.add(p);               //   Add the permutation input-String to the Set
                            //  Else:
    for(;i<n;               //   Loop `i` in the range [0,length):
      p(                    //    And do a recursive-call with:
        p+s.charAt(i),      //     Permutation + `i`'th character
        s.substring(0,i)+s.substring(++i,n),l);}
                            //     Everything except this character

```
> 2 votes

# Answer
# K (oK), 13 bytes

**Solution:**

```
1_?x@prm@!#x:

```

Try it online!

**Explanation:**

Evaluation is performed right-to-left.

```
1_?x@prm@!#x: / the solution
           x: / store input in variable x
          #   / count length of x, #"abc" => 3
         !    / range, !3 => 0 1 2
     prm@     / apply (@) function permutations (prm) to range
   x@         / apply (@) these pumuted indixes back to original input
  ?           / return distinct values
1_            / drop the first one (ie the original input)

```
> 2 votes

# Answer
# Perl 6,  ~~39~~  38 bytes

```
*.comb.permutations».join.unique[1..*]

```

Try it

```
*.comb.permutations».join.unique.skip

```

Try it

## Expanded

```
*               # WhateverCode lambda (this is the parameter)
.comb           # split into graphemes
.permutations\  # get all of the permutations
».join          # join each of them with a hyper method call
.unique         # make sure they are unique
.skip           # start after the first value (the input)

```
> 1 votes

# Answer
# C++, 142 bytes

```
#include<algorithm>
void p(std::string s){auto b=s;sort(begin(s),end(s));do if(s!=b)puts(s.data());while(next_permutation(begin(s),end(s)));}

```

ungolfed

```
#include <algorithm>

void p(std::string s)
{
    auto b = s;                    // use auto to avoid std::string
    sort(begin(s), end(s));        // start at first permutation
    do
      if (s != b)                  // only print permutation different than given string
        puts(s.data());
    while (next_permutation(begin(s), end(s))); // move to next permutation
}

```
> 1 votes

# Answer
# JavaScript (ES6), 101 bytes

Adopted from a past answer of mine.

```
S=>(R=new Set,p=(s,m='')=>s[0]?s.map((_,i)=>p(a=[...s],m+a.splice(i,1))):R.add(m),_=p([...S]),[...R])

```

```
f=
S=>(R=new Set,p=(s,m='')=>s[0]?s.map((_,i)=>p(a=[...s],m+a.splice(i,1))):R.add(m),_=p([...S]),[...R])

console.log(
  f('ABC'),
  f('ABCD'),
  f('ABCC'),
  f('AABBC')
)
```
> 1 votes

# Answer
# Perl 5, 89 + 2 (`-F`) = 91 bytes

```
$,=$_;$"=",";map{say if!$k{$_}++&&$,ne$_&&(join"",sort@F)eq join"",sort/./g}glob"{@F}"x@F

```

Try it online!
> 0 votes

# Answer
# Husk, 3 bytes

Look ma, no Unicode!

```
tuP

```

Try it online!

05AB1E, but reversed, and cooler, cause it's ASCII only.
> 0 votes

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