title: DropSort it like it's hot

text:
# Question
Title: DropSort it like it's hot
As described in this question:

> Dropsort, designed by David Morgan-Mar, is an example of a linear-time "sorting algorithm" that produces a list that is, in fact, sorted, but contains only some of the original elements. Any element that is not at least as large as the maximum of the elements preceding it is simply removed from the list and discarded.

To use one of their test cases, an input of `{1, 2, 5, 4, 3, 7}` yields `{1, 2, 5, 7}`, as `4` and `3` are both dropped for being smaller than the previously "sorted" value, `5`.

We don't want "sorting" algorithms, we want them to be the real deal. Therefore, I want you to write a program that, given a list of numbers, outputs a list of DropSorted lists (to be a complete sorting algorithm, we would need to merge these lists, but merging two sorted lists has been done before, and asking you to do it again is pretty much asking two questions, so this question is specifically the "splitting" step of our complete DropSort).

The arrangement and content of our lists is crucial, however. The output of your program must be equivalent to the output of a DropSort, followed by a DropSort of the discarded values, and so on until you have only have a list of sorted chains. Again, borrowing the existing test suite (and adding two more):

```
Input                  -> Output
{1, 2, 5, 4, 3, 7}     -> {{1, 2, 5, 7}, {4}, {3}}
{10, -1, 12}           -> {{10, 12}, {-1}}
{-7, -8, -5, 0, -1, 1} -> {{-7, -5, 0, 1}, {-8, -1}}
{9, 8, 7, 6, 5}        -> {{9}, {8}, {7}, {6}, {5}}
{10, 13, 17, 21}       -> {{10, 13, 17, 21}}
{10, 10, 10, 9, 10}    -> {{10, 10, 10, 10}, {9}}  //Note equivalent values aren't dropped
{5, 4, 3, 8, 7, 6}     -> {{5, 8}, {4, 7}, {3, 6}}
{0, 2, 5, 4, 0, 7}     -> {{0, 2, 5, 7}, {4}, {0}}

```

You may assume the input is non-empty.

This is , so standard rules apply!

# Answer
> 10 votes
# MATL, ~~15~~ ~~10~~ 9 bytes

*5 bytes off using @beaker's idea of cumulative maximum*

```
t"ttY>=&)

```

Input is a numeric row vector, in the format `[1, 2, 5, 4, 3, 7]` (commas are optional). The output contains lists separated by newlines, with the numbers in each list separated by spaces.

Try it online! Or verify all test cases.

### Explanation

Given an array, the code picks from it every entry that equals the cumulative maximum up to that entry.

For example, given

```
1 2 5 4 3 7

```

the code picks the first, second, third and sixth entries:

```
1 2 5     7

```

Then the process is repeated on the subarray formed by the remaining entries (in the original order):

```
      4 3

```

This needs to be done until the subarray of remaining entries is empty. An upper bound on the required number of iterations is the input size. The last iterations may not be needed. In that case they operate on an empty array, producing additional empty arrays.

At the end, the stack contains the required arrays and possibly several empty arrays, which are not displayed at all.

```
t        % Implicit input. Duplicate
"        % Do as many times as the input size
  tt     %   Duplicate twice
  Y>     %   Cumulative maximum
  =      %   Compare for equality. Will be used as logical index
  &)     %   Two-output indexing: pushes indexed subarray, and then
         %   a subarray with the remaining entries
         % End (implicit)
         % Display stack (implicit). Empty arrays are not displayed

```

# Answer
> 24 votes
# Haskell, ~~67 59~~ 58 bytes

```
(q:r)!x|x<last q=q:r!x|1<2=(q++[x]):r
_!x=[[x]]
foldl(!)[]

```

**Explanation:** Given a list of lists (that are already sorted) and a value `x`, the `!` operator will place `x` at the end of the first list whose last element is less than or equal to `x`. If no such list exists, the list `[x]` is placed at the end.

Try it online.

# Answer
> 14 votes
## Husk, 10 bytes

```
hUmü<¡Ṡ-ü<

```

Try it online!

This is a combination of my other Husk answer and xnor's Haskell answer. The duplicate `ü<` feels clunky, but I don't know how to get rid of it...

## Explanation

The function `ü<` translates to `nubBy(>)` in Haskell. It traverses a list from left to right, keeping those elements for which no previously kept element is strictly greater. In other words, it performs dropsort. The leftover elements are obtained by taking list difference of the original list and the result of `ü<`.

```
hUmü<¡Ṡ-ü<  Implicit input, say x = [2,3,5,4,4,2,7].
     ¡      Iterate
      Ṡ-    list difference between argument
        ü<  and its dropsort: [[2,3,5,4,4,2,7],[4,4,2],[2],[],[],[],...
  m         Map
   ü<       dropsort: [[2,3,5,7],[4,4],[2],[],[],[],...
 U          Prefix of unique elements: [[2,3,5,7],[4,4],[2],[]]
h           Drop last element: [[2,3,5,7],[4,4],[2]]

```

# Answer
> 11 votes
# Haskell, 50 bytes

```
import Data.List
f[]=[]
f l|r<-nubBy(>)l=r:f(l\\r)

```

Try it online!

# Answer
> 7 votes
## Husk, 16 bytes

```
hUm₁≤¡₁>
ṠfSz⁰G▲

```

Try it online!

## Explanation

This first line is the main function, and the second is a higher order helper function (it takes a function as argument and returns a new function). It's accessed by the subscript . The idea is that `₁≤` performs dropsort and `₁>` gives the leftover elements.

```
ṠfSz⁰G▲  Helper function, takes binary function p (as ⁰) and list x (implicit).
         For example, p = (≤) and x = [2,4,3,4,5,2].
     G▲  Left scan on x with maximum: [2,4,4,4,5,5].
  Sz     Zip with x
    ⁰    using the function p: [1,1,0,1,1,0].
Ṡf       Keep elements of x at truthy indices: [2,4,4,5].

```

In the main function, we iterate the leftovers function `₁>` and apply the dropsort function `₁≤` to the results.

```
hUm₁≤¡₁>  Main function, implicit list argument, say x = [2,4,3,4,5,2].
     ¡    Iterate
      ₁>  the leftovers function: [[2,4,3,4,5,2],[3,2],[2],[],[],[],...
  m       Map
   ₁≤     the dropsort function: [[2,4,4,5],[3],[2],[],[],[],...
 U        Prefix of unique elements: [[2,4,4,5],[3],[2],[]]
h         Drop last element (an empty list): [[2,4,4,5],[3],[2]]

```

# Answer
> 6 votes
# Python 3, ~~131 112 103~~ 95 bytes

*Thanks a lot @Mr. Xcoder for a smashing 19 bytes!!*

### ***Thanks a lot @ovs for an amazing 17 bytes!***

```
def f(x):
 a,*x=x or[0];m=[a];d=[]
 for i in x:[m,d][i<m[-1]]+=i,
 return[m]+(x and(d>[])*f(d))

```

Try it online!

## Explanation:

```
def f(x):               #recursive function taking list, returns list of lists
 if len(x)<2:return[x]  #for a single element return [element]
 m=[x[0]];d=[]          #initialize main and dropped lists
 for i in x[1:]:[m,d][i<m[-1]]+=[i]  #append elements from the argument list accordingly into main and dropped list
 return[m]+(d>[])*list(f(d)) #add main-list along with further evaluated dropped-list(recursived) into a list of lists

```

# Answer
> 6 votes
# Haskell, ~~113~~ ~~107~~ ~~102~~ 92 bytes

```
import Data.List
a!(b:c)|b<last a=a!c|1>0=a++[b]!c
a!b=a
g x@(b:c)|i<-[b]!c=i:g(x\\i)
g x=[]

```

Try it online!

This feels *really* long.

# Explanation

`!` performs the drop sort on a list, while `#` collects the trimmings. `g` then repeatedly applies `#` until the list is empty recording the results in a list.

# Answer
> 5 votes
# APL, 27 bytes

```
{⍵≡⍬:⍬⋄(⊂X/⍵),∇⍵/⍨~X←⍵≥⌈\⍵}

```

Explanation:

* `⍵≡⍬:⍬`: if the input is empty, return the empty list
* `X←⍵≥⌈\⍵`: all numbers greater or equal to the running maximum
* `(⊂X/⍵)`: the list of those numbers,
* `∇⍵/⍨~X`: followed by the result of running this function on the remaining numbers

# Answer
> 4 votes
# JavaScript (ES6), 64 bytes

```
f=(a,l,r=[])=>a+a&&[a.filter(e=>e<l?!r.push(e):(l=e,1)),...f(r)]

```

**Ungolfed:**

```
f=(a,l,r=[])=>
  a+a&&                                    //any elements left?
  [a.filter(                               //filter elements that are in order,
    e=>e<l?!r.push(e):(l=e,1)              //push unsorted elements to r
   ),                                      //push() returns the new length of the array,
                                           //... so !push() will always return false
   ...f(r)                                 //recurse on r
  ]

```

```
f=(a,l,r=[])=>a+a&&[a.filter(e=>e<l?!r.push(e):(l=e,1)),...f(r)]

console.log(JSON.stringify(f([1, 2, 5, 4, 3, 7])));     // [1, 2, 5, 7][4][3]
console.log(JSON.stringify(f([10, -1, 12])));           // [10, 12][-1]
console.log(JSON.stringify(f([-7, -8, -5, 0, -1, 1]))); // [-7, -5, 0, 1][-8, -1]
console.log(JSON.stringify(f([9, 8, 7, 6, 5])));        // [9][8][7][6][5]
console.log(JSON.stringify(f([10, 13, 17, 21])));       // [10, 13, 17, 21]
console.log(JSON.stringify(f([10, 10, 10, 9, 10])));    // [10, 10, 10, 10][9]
console.log(JSON.stringify(f([5, 4, 3, 8, 7, 6])));     // [5, 8][4, 7][3, 6]
console.log(JSON.stringify(f([0, 2, 5, 4, 0, 7])));     // [0,2,5,7],[4],[0]
```

# Answer
> 4 votes
# Java 8, ~~182~~ ~~179~~ 177 bytes

```
import java.util.*;l->{List r=new Stack(),t;for(int p,i,x;l.size()>0;)for(p=l.get(0),r.add(t=new Stack()),i=0;i<l.size();p=x)if((x=l.get(i++))>=p)t.add(l.remove(--i));return r;}

```

-3 bytes thanks to *@Nevay*.
-2 bytes by using `Stack` instead of `Vector`.

**Explanation:**

Try it here.

```
import java.util.*;            // Required import for List and Vector
l->{                           // Method with ArrayList<Integer> parameter and List return-type
  List r=new Stack(),          //  Return-List
       t;                      //  Temp-List
  for(int p,i,x;               //  Some temp integers
      l.size()>0;)             //  Loop (1) as long as there are still items left in the list
    for(p=l.get(0),            //   Set `p` to the first item of the list
        r.add(t=new Stack()),  //   Add a new inner List to the result-List
        i=0;i<l.size();        //   Inner loop (2) from 0 to the size of the list (exclusive)
         p=x)                  //     After every iteration, save the previous value in `p`
      if((x=l.get(i++))>=p)    //    If the current item is equal or larger than the previous:
        t.add(l.remove(--i));  //     Add it to the temp-List, and remove it from the input-List
                               //   End of inner loop (2) (implicit / single-line body)
                               //  End of loop (1) (implicit / single-line body)
  return r;                    //  Return result-List
}                              // End of method

```

# Answer
> 4 votes
# , 61 bytes

```
f=function(x)if(sum(x|1)){print(x[b<-x==cummax(x)]);f(x[!b])}

```

Try it online!

Recursive function. `sum(x|1)` is shorthand for `length(x)`, so this recursion will run untill `x` is empty. `cummax` takes the cumulative maximum of `x`, which is then compared to `x` again. This produces a boolean vector of length `x`, where all the TRUEs correspond to sorted values. We use that to take a subset of `x` and `print` it. The function is then called again on the remainder of `x`.

# Answer
> 3 votes
# C#, ~~188~~ 203 bytes

```
int[][]f(int[]a){int[]t=a.Where((n,i)=>i<1||n>=a[i-1]).ToArray(),m=a.Where((n,i)=>i>0&&n<a[i-1]).ToArray();var s=new int[][]{t}.ToList();if(m.Any())s.AddRange(f(m));return s.ToArray();}

```

The byte count includes +18 for:

```
using System.Linq;

```

Try it online!

# Answer
> 3 votes
# C++14, ~~118~~ 108 bytes

Using the algorithm from w0lf's Haskell answer.

As unnamed generic lambda. First parameter is a container of the values to dropsort (like `vector<int>`) and second parameter requires a compatible empty container of containers (like `vector<vector<int>>`) for the return value via reference.

In the first version of the program, there was `R.clear;()` as first statement, so that the container of containers didnt need to be empty. Peter Cordes thought this could into the specification, so dropping 10 byte for that.

```
[](auto A,auto&R){for(auto x:A){for(auto&D:R)if(D.back()<x){D.push_back(x);goto F;}R.emplace_back(1,x);F:;}}

```

Try it online!

Ungolfed:

```
[](auto A,auto&R){
 for(auto x:A){       //foreach item
  for(auto&D:R)       //foreach result list
   if(D.back()<x){    //x bigger than last element
    D.push_back(x);   //add x
    goto F;           //break and jump over the emplace
   }
  R.emplace_back(1,x);//create new list with this element
  F:;
 }
}

```

# Answer
> 2 votes
# Python 2, 88 bytes

-4 bytes thanks to Arnold Palmer

```
b,r=input(),[]
for i in b:
 for l in r:
	if l[-1]<=i:l+=[i];break
 else:r+=[[i]]
print r

```

Try it online!

Solution similar to @w0lf's haskell \[answer\]\[1\]

Rare use case for `for-else` construction

Iterate through sorted lists `for l in r` (empty at start).
If element(from input) `i` is larger than last element of list `l[-1]`, add element to list `l+=[i]`, break.
If no list was accepted, add new list with this elemens `r+=[[i]]`

# Answer
> 1 votes
# C (gcc), 176 175 173 bytes

```
#define P(x)printf("%d ",t=x);
l[2][99];t;x;i;j;w;main(a){while(scanf("%d",*l+w)>0)++w;while(i=w){P(l[a=!a][w=0])for(j=1;j<i;++j){x=l[a][j];x<t?l[!a][w++]=x:P(x)}puts("");}}

```

Try it online!

Somewhat readable version:

```
#define P(x)printf("%d ",t=x);
l[2][99];t;x;i;j;w;
main(a)
{
    while(scanf("%d",*l+w)>0)++w;
    while(i=w)
    {
        P(l[a=!a][w=0])
        for(j=1;j<i;++j)
        {
            x=l[a][j];
            x<t?l[!a][w++]=x:P(x)
        }
        puts("");
    }
}

```

# Answer
> 1 votes
# JavaScript (ES6), ~~71~~ ~~70~~ 68 bytes

```
a=>a.map(n=>(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n),o=[])&&o

```

Pretty simple, just iterates the array, looks for the first inner array whose last value is `<=` to the next value to drop, if none exists, append a new inner array with the next value to the output, otherwise append the next value to the first found inner array that matches the condition.

### Updates

Thanks to Neil, saved three bytes converting `(...,o)` to `...&&o` and re-organizing the callback to `map()` to be more compact.

```
f=a=>a.map(n=>(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n),o=[])&&o;[[1,2,5,4,3,7],[10,-1,12],[-7,-8,-5,0,-1,1],[9,8,7,6,5],[10,13,17,21],[10,10,10,9,10],[5,4,3,8,7,6],[0,2,5,4,0,7]].map(f).map(JSON.stringify).map(v=>console.log(v))
```

```
.as-console-wrapper{max-height:100%!important}
```

# Answer
> 1 votes
# Japt, 29 bytes

```
@lOpP)<1}a@=f_<VªOoV=Z+S}V=Ug

```

Test it online!

# Answer
> 1 votes
# PHP, ~~102 bytes~~, 98 bytes

```
<?php function s($i){static$s;foreach($i as$v)${$v<max($l)?f:l}[]=$v;$s[]=$l;!$f?:s($f);return$s;}

```

Try it online!

*-4 bytes, thanks to @Umbrella*

**Explanation**

```
<?php

```

The function takes the input list as an array.

```
function s($i) {

```

`$s`, which will become the finally returned list of lists, is declared static. This extends its scope to *all* calls of this function, allowing the function to be called recursively without having to pass this result list as an argument or to return it.

```
    static $s;

```

Loop through each value in the list.

```
    foreach ($i as $v)

```

Is it less than the biggest current list member?

```
        $v < max($l) ?

```

Yes, put it on list `$f` for further sorting.

```
                        $f[] = $v :

```

No, put it on list `$l`.

```
                        $l[] = $v;

```

Push list `$l` onto the list of lists.

```
    $s[] = $l;

```

If there's anything in list `$f`, send it round again for further sorting.

```
    !$f ?: s($f);

```

Return the list of lists.

```
    return $s;
}

```

# Answer
> 1 votes
# PHP, ~~91~~ ~~103~~ ~~96~~ 85 bytes

(Edited to add 12 chars of `print_r($r);` to meet requirement to output)
(Edited to remove 7 bytes when allowing PHP Errors)
(Edited to remove 11 bytes when golfing the assignment further)

```
while($a){$b=$d=[];foreach($a as$i)${max($b)>$i?d:b}[]=$i;$a=$d;$r[]=$b;}print_r($r);

```

Given input `$a`, it produces result `$r`

Pretty:

```
while ($a) {
    $b = $d = [];
    foreach ($a as $i) {
        ${max($b) > $i ? d : b}[] = $i;
    }
    $a   = $d;
    $r[] = $b;
}

```

The pseudo-recursive outer loop initializes the keep `$b` and discard `$d` arrays to empty, then does a basic drop sort loop, finally setting the discards as the new input and adding the keeps to the result `$r`

# Answer
> 0 votes
## Sage, 102 bytes

```
def f(w,a=[]):
 for x in w:
  q,c=exists(a,lambda b:b[-1]<=x)
  if q:c+=[x]
  else:a+=[[x]]
 return a

```

Very similar to @Dead Possum's answer.
Appends each member `x` of `w` to the first list in `a` {list of lists} with `x` greater than it's last element.
if none, appends `[x]` to `a`.

I would really like it if `exists` returned `a` if nothing was found! Also trying to apply @officialaimm's one-line idea ...

Question: If I removed my code from the function, I'd have to assign `w` to input right? So would it save bytes?

# Answer
> 0 votes
# APL, ~~100~~ ~~88~~ ~~83~~ ~~79~~ ~~78~~ ~~57~~ ~~56~~ ~~77~~ 76 bytes

```
{(E/⍵),⊂⍵/⍨~E←(⍬≢⍴)¨⍵}∘{⍵≡(S←¯1↓⍵),⊃⊃⌽⍵:⍵⋄∇S,⊃⌽⍵}{⍵≡X←⍵/⍨~V←⍵≠⌈\⍵:⍵⋄X(∇V/⍵)}

```

-0 bytes thanks to Kritixi Lithos...

Try it online!

There's got to be some better way to do this (There is). Any tips are very greatly appreciated and welcome.

## How?

(Note, some of this explanation might be wrong, as I forgot how this worked)

```
{⍵≡X←⍵/⍨~V←⍵≠⌈\⍵:⍵⋄X(∇V/⍵)} - separate the argument into nested drop-sorts
{⍵≡(S←¯1↓⍵),⊃⊃⌽⍵:⍵⋄∇S,⊃⌽⍵}  - un-nesting (passed the result of the above)
{(E/⍵),⊂⍵/⍨~E←(⍬≢⍴)¨⍵}∘     - fixing array mishaps (passed the result of the above)

```

# Answer
> 0 votes
# JavaScript (Node.js), ~~125~~ ~~109~~ 106 bytes

-~~16~~ 18 bytes from Zacharý

-1 by removing `{` and `}` by changing the incrementer to include the "set last to the current"

```
m=x=>{z=[[],[]];l=NaN;for(i=0;i<x.length;l=x[i++])if(l>x[i])z[1].push(x[i]);else z[0].push(x[i]);return z}

```

Basically, asks is the current item greater than the last item, add to the first list. Otherwise, add to the second.

Found out during this that comparing any number to `NaN` will always result `false`. Interesting!

Explanation:

```
m = x => {                         // Create function
  z = [[], []];                      // Initialize dropsort output
  l = NaN;                           // Initialize last element
  for (i = 0; i < x.length; l=x[i++])// For each item in input...
    if (l > x[i])                    // If current item is greater than previous
      z[1].push(x[i]);               // Then add it to the first part of output
    else                             // Elsewise
      z[0].push(x[i]);               // Add it to the nonordered part of the dropsort
                                     // Set last item to current item
  }                                  // Repeat
  return z                           // Return finished dropsort
}                                    // End function

```

Try it online!

# Answer
> 0 votes
# Ocaml, ~~69~~ 62 bytes

```
let rec d=function h::i::t when h>i->d(h::t)|h::t->h::d t|x->x

```

Explanation:

```
let rec d = function (* Implicitly take an list as a parameter *)
    (* If the list starts with two elements h and i and h is greater than i, drop i and sort the list starting with h and the rest t *)
    | h::i::t when h > i -> d (h::t)
    (* If h is not greater than i, make a new list starting with h and a tail containing the drop sorted rest *)
    | h::t -> h::d t
    (* If none of the cases apply, the list is empty. *)
    | x -> x

```

# Answer
> 0 votes
# Jelly, 26 bytes

```
<»\¬x@ðW;µ⁸Ñ
<»\x@µÑ
1Ŀ¹L?

```

This is the same method as marinus' APL answer.

Try it online!.

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


title: Rank Correlation Coefficient

text:
# Question
Title: Rank Correlation Coefficient
The usual correlation coefficient (in 2d) measures how well a set of points can be described by a line, and if yes, its sign tells us whether we have a positive or negative correlation. But this assumes that coordinates of the points can actually interpreted quantitatively for instance as measurements.

If you cannot do that but you can still *order* the coordinates, there is the *rank correlation coefficient*: It measures how well the points can be described by a *monotonic* function.

### Challenge

Given a list of 2d points, determine their *rank correlation coefficient*.

### Details

* You can assume the input to be positive integers (but you don't have to), or any other "sortable" values.
* The points can be taken as a list of points, or two lists for the x- and y-coordinates or a matrix or 2d array etc.
* The output must be a floating point or rational type, as it should represent a real number between 0 and 1.

### Definitions

**Rank:** Given a list of numbers `X=[x(1),...,x(n)]` we can assign a positive number `rx(i)` called *rank* to each entry `x(i)`. We do so by sorting the list and assigning the index of `x(i)` in the sorted list `rx(i)`. If two or more `x(i)` have the same value, then we just use the arithmetic mean of all the corresponding indices as rank. Example:

```
          List: [21, 10, 10, 25, 3]
Indices sorted: [4, 2, 3, 5, 1]

```

The number `10` appears twice here. In the sorted list it would occupy the indices `2` and `3`. The arithmetic mean of those is `2.5` so the ranks are

```
         Ranks: [4, 2.5, 2.5, 5, 1]

```

**Rank Correlation Coefficient**: Let `[(x(1),y(1)),(x(2),y(2)),...,(x(n),y(n))]` be the given points where each `x(i)` and `y(i)` is a real number (wlog. you can assume it is an integer) For each `i=1,...,n` we compute the *rank* `rx(i)` and `ry(i)` of `x(i)` and `y(i)` respectively.

Let `d(i) = rx(i)-ry(i)` be the *rank difference* and let `S` be the sum `S = d(1)^2 + d(2)^2 + ... + d(n)^2`. Then the *rank correlation coefficient* `rho` is given by

```
rho = 1 - 6 * S / (n * (n^2-1))

```

### Example

```
x   y   rx              ry   d      d^2
21  15  4               5   -1      1
10  6   2&3 -> 2.5      2    0.5    0.25
10  7   2&3 -> 2.5      3   -0.5    0.25
25  11  5               4    1      1
3   5   1               1    0      0

    rho = 1 - 6 * (1+0.25+0.25+1)/(5*(5^2-1)) = 0.875

```

# Answer
> 5 votes
# MATL, 33 bytes

```
,it7#utb,&S]2XQw)]-Us6*1GntUq*/_Q

```

Try it online!

### Explanation

```
,           % Do...twice
  it        %   Input a numeric vector. Duplicate
  7#u       %   Replace each element by a unique integer label (1, 2, ...)
  t         %   Duplicate
  b         %   Bubble up: moves original numeric vector to top
  ,         %   Do...twice
    &S      %     Sort and push the indices of the sorting
  ]         %   End
            %   The above do...twice loop gives the sorted indices (as
            %   explained in the challenge text) for the current input
  2XQ       %   Compute average for entries with the same integer label
  w         %   Swap: move vector of integer labels to top
  )         %   Index. This gives the rank vector for the current input
]           % End
-           % Subtract the two results. Gives d
Us          % Square each entry, sum of vector. S
6*          % Times 6. Gives 6*S
1G          % Push first input vector again
n           % Number of entries. Gives n
t           % Duplicate
Uq          % Square, minus 1. Gives n^2-1
*           % Times. Gives n*(n^2-1)
/           % Divide. Gives 6*S/(n*(n^2-1))
_Q          % Negate, plus 1. Gives 1-6*S/(n*(n^2-1))

```

# Answer
> 5 votes
# , ~~64~~ 60 bytes

```
function(x,y)1-6*sum((rank(x)-rank(y))^2)/((n=sum(x|1))^3-n)

```

Try it online!

`rank` in R is the builtin that computes the desired rank; the rest is just the math to do the rest of the job.

*Thanks to CriminallyVulgar for saving 4 bytes*

As mentioned in the comments, the stated definition of rank correlation coefficient doesn't correspond precisely to the Spearman correlation coefficient, else a valid answer would be 26 bytes:

```
function(x,y)cor(x,y,,"s")
```

# Answer
> 3 votes
# Python 3, 141 bytes

```
lambda X,Y,Q=lambda U,S=sorted:[S(U).index(y)+S(U).count(y)/2+.5for y in U]:1-6*sum((i[1]-i[0])**2for i in zip(Q(X),Q(Y)))/(len(X)**3-len(X))

```

This defines an anonymous function which takes input as two lists corresponding to the `x` and `y` values. Output is returned as a floating-point value.

Try it online!

# Answer
> 2 votes
# Mathematica, 89 bytes

```
(F[x_]:=Min@N@Mean@Position[Sort@x,#]&;1-6Tr[(F@#/@#-F@#2/@#2)^2]/((y=Length@#)(y^2-1)))&

```

Try it online! (in order to work on mathics, "Tr" is replaced with "Total")

---
Tags: code-golf, math, statistics
---


title: Solving Secret Swapping Sequences

text:
# Question
Title: Solving Secret Swapping Sequences
> This is a challenge, the cops thread can be found here.

This is the robbers thread, your job here is to take submissions on the cops thread and try to find the hidden sequences. If you find any sequence that can be substituted into the original code to compute that sequence that is a valid crack. Please notify the cops of your cracks as they happen so they can update their answers.

## Scoring

Your score will be the number of successful cracks you have made, with more cracks being better.

# Answer
> 5 votes
# Japt, Shaggy, A000290

```
p#A000290uCnG

```

Try it online!

# Answer
> 4 votes
# Python 3: Mr. Xcoder, A010709

```
n=int(input())
print(sum(1for i in"A010709"if i>"0")*-~n//-~n)

```

Try it online!

Additionally, here's a golfed version of the original. :P

```
lambda n:sum(1for i in"A017016"if i>"0")*-~n//-~n

```

# Answer
> 4 votes
# Python 3, pppery

> A018226

The original code put the sequence name in a comment. Since the comment probably can't affect the code I figured the hidden sequence had to be some sub-sequence of the original. A quick search of the first couple terms brought up A018226. Since it is a sub-sequence the code works for both. A018226 is even listed on the original sequence's page if you look back

> One way to generalize the magic number sequence in A018226.

# Answer
> 3 votes
# C#, TheLethalCoder

> A000578 (Cubes)

An easy one - it was also posted here.

# Answer
> 3 votes
# Python 2, Dead Possum

> A000244 (Powers of 3)

---

This no longer works, the OP updated the example after I posted this.

# Answer
> 3 votes
# Python 2, Dead Possum

> A000007: The characteristic function of 0: a(n) = 0^n.

# Answer
> 3 votes
# C#, TheLethalCoder, A000244

Also works with A000079 (powers of two).

# Answer
> 3 votes
# dc, Bruce Forte

Cracked with A027480.

# Answer
> 2 votes
# Python 2: officialaimm, A055642

```
lambda x:len(`x**(sum(map(int,'A055642'[1:]))==22)`)

```

Try it online!

It took me a while to find the sequence... Mostly 'cause OEIS search is *super* slow for me. o0

# Answer
> 2 votes
# Python 3, ppperry, A000027 -\> A004526

```
f=lambda a,n=((int("A004526",11)-0x103519a)%100%30+1)/2:a//(14-n)

```

**Try it online!** (prints first few terms of both. Note the two sequences have offsets of 1 and 0 respectively, so the first has a leading zero - it threw me a little!)

# Answer
> 2 votes
# MATL, Cinaski

Cracked with A055642.

# Answer
> 2 votes
# Python 3.6, RootTwo

Original is A005843
Cracked with A001107

Try it online

The eval'd code of the original (minus comments) is `n*2`, of the cracked version is `4*n*n-n*3`.

After filtering out syntax errors, undeclared variables, zero divisions, etc, it didn't take too long to run through the remaining list. There were a few false positives (like A004917) that I had to filter out by hand due to only checking the first few numbers, but it wasn't too common.

Also, A040489 tries to calculate `n**3436485154-n`, which slowed me down a bit. :P

# Answer
> 1 votes
# Chip, Phlarx

Cracked with A060843. On a hunch, guessed the sequence was going to be short!

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


title: Pascal's Alternating Triangle

text:
# Question
Title: Pascal's Alternating Triangle
Pascal's triangle is generated by starting with `1` and having each row formed from successive additions. Here, instead, we're going to form a triangle by alternating multiplication and addition.

We start row `1` with just a solitary `1`. Thereafter, addition is done on the odd rows, and multiplication is done on the even rows (1-indexed). When performing the addition step, assume the spaces outside of the triangle are filled with `0`s. When performing the multiplication step, assume that the outside is filled with `1`s.

Here's the full triangle down to 7 rows. The `*` or `+` on the left shows what step was performed to generate that row.

```
1                1
2 *            1   1
3 +          1   2   1
4 *        1   2   2   1
5 +      1   3   4   3   1
6 *    1   3  12  12   3   1
7 +  1   4  15  24  15   4   1

```

## Challenge

Given input `n`, output the `n`th row of this triangle.

## Rules

* You may choose to 0-index instead, but then please realize that the addition and multiplication rows must flip-flop, so that the exact same triangle is generated as above. Please state in your submission if you choose to do this.
* The input and output can be assumed to fit in your language's native integer type.
* The input and output can be given in any convenient format.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* If possible, please include a link to an online testing environment so other people can try out your code!
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

## Examples

Showing two possible examples of output out of many: a list, or a space separated string.

```
4
[1, 2, 2, 1]

8
"1 4 60 360 360 60 4 1"

```

# Answer
# Pascal, ~~249~~ ~~247~~ 233 bytes

*Well, this is **Pascal's** alternating triangle.*

*1 byte saved thanks to @Mr.Xcoder*

```
function f(n,k:integer):integer;begin if((k<1)or(k>n)or(n=1))then f:=n mod 2 else if n mod 2=0then f:=f(n-1,k-1)*f(n-1,k)else f:=f(n-1,k-1)+f(n-1,k)end;
procedure g(n:integer);var k:integer;begin for k:=1to n do write(f(n,k),' ')end;

```

Try it online!
> 16 votes

# Answer
# Python 2, ~~97~~ ~~93~~ ~~86~~ ~~81~~ 78 bytes

*-4 bytes thanks to Rod. -10 bytes thanks to Halvard Hummel.*

```
f=lambda n:n and[[i+j,i*j][n%2]for i,j in zip([n%2]+f(n-1),f(n-1)+[n%2])]or[1]

```

0-indexed.

Try it online!
> 7 votes

# Answer
# Python 2, ~~96 89~~ 87 bytes

```
s=a=[1]
for i in range(1,input()):a=s+[[k+l,k*l][i%2]for k,l in zip(a[1:],a)]+s
print a

```

Try it online!
> 5 votes

# Answer
# Jelly, ~~17~~ 12 bytes

```
µ×+LḂ$?Ḋ1;µ¡

```

This is a full program (or niladic link) that takes input from STDIN.

Try it online!

### How it works

```
µ×+LḂ$?Ḋ1;µ¡  Main link. No arguments. Implicit argument: 0

          µ¡  Start a monadic chain and apply the ntimes quick to the previous one.
              This reads an integer n from STDIN and executes the previous chain n
              times, with initial argument 0, returning the last result.
µ             Start a monadic chain. Argument: A (array or 0)
       Ḋ          Dequeue; yield A without its first element.
   LḂ$?           If the length of A is odd:
 ×                    Multiply A and dequeued A.
                  Else:
  +                   Add A and dequeued A.
        1;        Prepend a 1 to the result.

```
> 5 votes

# Answer
# CJam, 25 bytes

```
{1a\{2%!_2$+\{.*}{.+}?}/}

```

0-indexed.

Try it online!

### Explanation

This is an anonymous block that takes the number from the stack and leaves the result on the stack.

```
1a                        Push [1].
  \                       Bring the number to the top.
   {                 }/   For reach number 0 .. arg-1, do:
    2%!                    Push 0 if even, 1 if odd.
       _                   Copy that.
        2$+                Copy the list so far and prepend the 0 or 1 to it.
           \               Bring the 0 or 1 back to the top.
            {.*}{.+}?      If 1, element-wise multiplication. If 0, element-wise addition.

```
> 3 votes

# Answer
# Haskell, ~~76~~ 72 bytes

0-indexed solution:

```
(p!!)
p=[1]:[zipWith o(e:l)l++[1]|(l,(o,e))<-zip p$cycle[((*),1),((+),0)]]

```

Try it online!

### Explanation

`p` recursively defines the alternating triangle, the base case/first element of it is `[1]`

```
p=[1]:[                                                            ]

```

It then builds the triangle by taking the previous line (`l`). To know what to do with it we need to keep track of the correct operator (`o`) and the corresponding neutral element (`e`):

```
                           |(l,(o,e))<-zip p$cycle[((*),1),((+),0)]

```

From this build the new line by duplicating the line and for one copy we prepend the neutral element, zip them with the operator and append a 1:

```
       zipWith o(e:l)l++[1]

```
> 3 votes

# Answer
# Mathematica, 92 bytes

```
(s={i=1};While[i<#,s=Flatten@{1,{Tr/@#,Times@@@#}[[i~Mod~2+1]]&@Partition[s,2,1],1};i++];s)&

```

Try it online! (in order to work on mathics "Tr" is replaced with "Total")
> 3 votes

# Answer
## Husk, ~~17~~ 16 bytes

```
!G₅;1¢e*+
:1Sż⁰t

```

Try it online!

A 1-indexed solution.

## Explanation

The first line is the main function, which calls the helper function on the second line. The helper function is usually called with , but in this case I'm using the *overflowing labels* feature of Husk: if you refer to a line **N** in a program with **M \< N** lines, you get line **N mod M** with modifier function **M / N** applied to it. The second modifier function is `flip`, so I'm using  to flip the arguments of the helper function with no additional byte cost.

Here is the helper function.

```
:1Sż⁰t  Takes a function f and a list x.
   ż    Zip preserving elements of longer list
    ⁰   using function f
  S  t  x and its tail,
:1      then prepend 1.

```

Here is the main function.

```
!G₅;1¢e*+  Takes a number n.
      e*+  2-element list of the functions * and +
     ¢     repeated infinitely.
 G         Left scan this list
  ₅        using the flipped helper function
   ;1      with initial value [1].
!          Get n'th element.

```
> 3 votes

# Answer
# , ~~108~~ 98 bytes

*-10 bytes by replacing the actual multiply sign with a plus sign. Please forgive me.*

```
f=function(n){if(n<3)return(rep(1,n))else{v=f(n-1)};if(n%%2)`*`=`+`;return(c(1,v[3:n-2]*v[-1],1))}

```

Try it online!

Quite pleased with the general method (first time I've aliased a primitive) but I'm sure there's golfing to be done on it yet, especially with the awkward handling of cases where n\<3 which leads to a lot of boilerplate.
> 3 votes

# Answer
# C# (.NET Core), ~~143~~ ~~134~~ 128 bytes

*-4 bytes thanks to Phaeze*
*-5 bytes thanks to Zac Faragher*
*-6 bytes thanks to Kevin Cruijssen*

```
n=>{int[]b={1},c;for(int i=0,j;++i<n;b=c)for(c=new int[i+1],c[0]=c[i]=1,j=0;++j<i;)c[j]=i%2<1?b[j-1]+b[j]:b[j-1]*b[j];return b;}

```

Try it online!

Explanation:

```
n =>
{
    int[] b = { 1 }, c;               // Create first layer
    for(int i = 0, j; ++i < n; b = c) // Iterate for every layer, replace last layer with a new one
        for(c = new int[i+1],         // Create new layer
            c[0] = c[i] = 1,          // First and last elements are always 1
            j = 0;
            ++j < i; )                // Replace every element (besides 1st and last)...
                c[j] = i % 2 == 0 ?
                    b[j - 1] + b[j] : // ... with addition...
                    b[j - 1] * b[j];  // ... or multiplication of two from previous layers
    return b;                         // Return latest layer
};

```
> 1 votes

# Answer
# Python 2, 83 bytes

Give some love to `exec`
0-indexed

```
l=[1];exec"l[1:]=[[a+b,a*b][len(l)%2]for a,b in zip(l,l[1:])]+[1];"*input()
print l

```

Try it online!
> 1 votes

# Answer
# Pyth, 22 bytes

Saved tons of byte thanks to @FryAmTheEggman! The initial solution is below.

```
u++1@,+VGtG*VGtGlG1Q[1

```

**Full Test Suite (0-indexed).**

# Pyth, ~~40 38 36~~ 35 bytes

This feels ~~waaaaaaaay too~~ reasonably long. Suggestions are welcome.

```
K]1VStQ=K++]1m@,sd*hded%N2C,KtK]1;K

```

**Test Suite** or **Try it online!**
> 1 votes

# Answer
# , 32 bytes

```
[:(1,]{::(}.@,-.)(*;+)[)~/2|]-i.

```

Try it online!
> 1 votes

# Answer
# Perl 5, 111 + 2 (-na) = 113 bytes

```
sub t{($r,$c)=@_;!--$r||!$c||$c>=$r?1:eval"t($r,$c)".($r%2?"*":"+")."t($r,$c-1)"}say map{t($F[0],$_).$"}0..$_-1

```

Try it online!
> 1 votes

# Answer
# Mathematica, 70 bytes

```
Fold[#2@@@Partition[#,2,1,{-1,1},{}]&,{1},PadRight[{},#,{1##&,Plus}]]&

```

Try it at the Wolfram sandbox! It doesn't work in Mathics, unfortunately. It's 0-indexed.

Explanation: `Partition[#,2,1,{-1,1},{}]` takes a list and returns all the two-element sublists, plus 1-element lists for the start and end — e.g., `{1,2,3,4}` becomes `{{1}, {1,2}, {2,3}, {3,4}, {4}}`. `PadRight[{},#,{1##&,Plus}]` makes an alternating list of `1##&` (effectively `Times`) and `Plus`, whose length is the input number. Then `Fold` repeatedly applies the partition function with the `Plus`es and `Times`es applied to it, to make the rows of the triangle.
> 1 votes

# Answer
# Ruby, ~~83~~ 82 bytes

```
->n{a=[1];p=0;n.times{a=[p=1-p,*a,p].each_cons(2).map{|x|x.reduce([:+,:*][p])}};a}

```

Try it online!

This is 0-indexed.
> 0 votes

# Answer
# Racket, 116 bytes

```
(define(t n[i 1][r'(1)])(if(= n 1)r(t(- n 1)(- 1 i)(cons 1(append(map(if(> i 0)* +)(cdr r)(reverse(cdr r)))'(1))))))

```

Try it online!
> 0 votes

# Answer
# TI-Basic (TI-84 Plus CE), 100 bytes

```
Prompt X
{1→M
For(A,2,X
<sub>L</sub>M→L
A→dim(M
For(B,2,A–1
If A/2=int(A/2
Then
<sub>L</sub>L(B–1)<sub>L</sub>L(B→<sub>L</sub>M(B
Else
<sub>L</sub>L(B–1)+<sub>L</sub>L(B→<sub>L</sub>M(B
End
End
1→<sub>L</sub>M(dim(<sub>L</sub>M
End
<sub>L</sub>M

```

1-indexed, prompts user for input and prints a list containing the `n`th row of Pascal's Alternating Triangle.

While looping: LM is the current row, and LL is the previous row.

TI-Basic is a tokenized language. All tokens used here are one-byte tokens.

I think I can golf this further by modifying M in-place from the end.

Explanation:

```
Prompt X            # 3 bytes; get user input, store in X
{1→M                # 5 bytes, store the first row into <sub>L</sub>M
For(A,2,X           # 7 bytes, Loop X-1 times, with A as the counter, starting at 2
<sub>L</sub>M→L                # 5 bytes, copy list M into list L
A→dim(M             # 5 bytes, extend M by one
For(B,2,A–1         # 9 bytes, for each index B that isn't the first or last...
If A/2=int(A/2      # 10 bytes,    if A is even...
Then                # 2 bytes,     then...
<sub>L</sub>L(B–1)<sub>L</sub>L(B→<sub>L</sub>M(B     # 17 bytes,        the Bth item in this row is the Bth times the (B-1)th of the previous row
Else                # 2 bytes,     else...
<sub>L</sub>L(B–1)+<sub>L</sub>L(B→<sub>L</sub>M(B    # 18 bytes,        the Bth item in this row is the Bth plus the (B-1)th of the previous row
End                 # 2 bytes,     endif
End                 # 2 bytes,  endfor
1→<sub>L</sub>M(dim(<sub>L</sub>M         # 9 bytes, the last item is always 1
End                 # 2 bytes, endfor
<sub>L</sub>M                  # 2 bytes, Implicitly print the final row

```
> 0 votes

# Answer
# JavaScript (ES6), ~~71~~ ~~69~~ 66 bytes

```
f=n=>n?(p=f(n-1),[...p.map((v,i)=>i--?n%2?v*p[i]:v+p[i]:1),1]):[1]

```

Try it online!

0-indexed.
**-3 bytes** by @Arnauld

```
f=n=>n?(p=f(n-1),[...p.map((v,i)=>i--?n%2?v*p[i]:v+p[i]:1),1]):[1]

for (var i = 0; i < 10; ++i) {
  console.log(JSON.stringify(f(i)));
}
```
> 0 votes

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


title: Parallelogram a Number

text:
# Question
Title: Parallelogram a Number
Now that we know how to properly square and triangle a number, we are going to learn how to parallelogram one. To parallelogram a number, we first arrange it as a parallelogram by stacking it on top of itself a number of times equal to the number of digits it has, and adding spaces to make it a parallelogram. So `123` would form:

```
   123
  123
 123

```

Now we take each horizontal and vertical number and add them, `123+123+123+1+12+123+23+3`, which equals `531`, which is the parallelogram of `123`.

## Your Task:

Write a program or function that, when given a number as input, returns the parallelogram of the number.

## Input:

A non-negative integer, or a non-negative integer represented by a string.

## Output:

The parallelogram of the integer.

## Test Cases:

```
1234567 -> 10288049
123     -> 531
101     -> 417
12      -> 39

```

## Scoring:

This is , lowest score in bytes wins!

# Answer
> 9 votes
# MATL, 12 bytes

```
tnEXyPY+c!Us

```

Input is a string. **Try it online!**

### Explanation

Consider input `'123'` as an example.

The code duplicates the input (`t`) and builds an identity matrix (`Xy`) of size twice the input length (`nE`):

```
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1

```

then flips it upside down (`P`):

```
0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0
1 0 0 0 0 0

```

The input string, interpreted as ASCII codes of the digits, is equivalent to the numeric row vector

```
49 50 51

```

Full-size two-dimensional convolution (`Y+`) of the above vector and matrix gives

```
 0  0  0  0  0 49 50 51
 0  0  0  0 49 50 51  0
 0  0  0 49 50 51  0  0
 0  0 49 50 51  0  0  0
 0 49 50 51  0  0  0  0
49 50 51  0  0  0  0  0

```

Interpreting those numbers back as ASCII codes (`c`) gives the following char matrix, with char 0 represented as space:

```
     123
    123
   123
  123
 123
123

```

Transposition (`!`) transforms this into

```
     1
    12
   123
  123
 123
123
23
3

```

Interpreting each row as a number (`U`) gives the numeric column vector

```
  1
 12
123
123
123
123
 23
  3

```

and summing it (`s`) gives the final result, `531`.

# Answer
> 6 votes
# 05AB1E,  ~~12 11~~  8 bytes

I~~'m sure~~ knew this ~~can~~ could be golfed further - tips welcome!

-1 byte thanks to Erik the Outgolfer (avoid wraps but using a concatenation)
and then...
-3 more bytes thanks to Adnan (avoid multiplication by length-1 by vectorising addition and subtracting the input off at the end)

```
.s¹η++Oα

```

**Try it online!**

### How?

```
.s¹η++Oα - implicit input, say i      e.g.  123
.s       - suffixes                         [3,23,123]
  ¹      - push i                           123
   η     - prefixes                         [1,12,123]
    +    - addition of top two              [4,35,246]
     +   - addition (vectorises)            [127,158,369]
      O  - sum                              654
       α - absolute difference abs(123-654) 531
         - implicit print

```

# Answer
> 6 votes
# Retina, 22 bytes

```
.
$`;$&$';$_;
\d+
$*
1

```

Try it online! Link includes test cases. Explanation: The first stage splits the input number at each digit and includes all the exclusive prefixes and inclusive suffixes, giving the vertical numbers, plus also the original input number repeated for each digit, giving the horizontal numbers. The remaining stages then simply sum the resulting numbers.

# Answer
> 5 votes
# Husk, ~~13~~ 12 bytes

```
ṁit§+SRL§+ḣṫ

```

Try it online!

### Explanation

```
              -- implicit input, say "123"
   §+         -- concatenate the results of the following two functions
     SR       --  ¹repeat the input n times, where n is the result of the next function
       L      --   length                                                  ["123","123"]
        §+   --  ²concatenate the results of the following two functions
          ḣ  --     prefixes                                              ["","1","12","123"]
           ṫ --     suffixes                                              ["123","23","3",""]
              -- inner concatenation                                      ["","1","13","123","123","23","3",""]
              -- outer concatenation                                      ["123","123","","1","13","123","123","23","3",""]
  t           -- all but the first element                                ["123","","1","13","123","123","23","3",""]
ṁ             -- map then sum
 i            --   convert to integer (where "" converts to 0)

```

# Answer
> 5 votes
# Haskell, ~~90~~ ~~78~~ ~~76~~ ~~71~~ ~~64~~ ~~63~~ ~~59~~ 57 bytes

```
g x=sum[x+div x(10^a)+mod x(10^a)|(a,_)<-zip[1..]$show x]

```

Try it online!

# Answer
> 4 votes
# Python 3, 85 70 Bytes

```
f=lambda n,r=1,i=int:n[r:]and i(n[r:])+i(n[:r])+f(n,r+1)+i(n)or i(n)*2

```

For input 12345:

Sums up slices of input 1+2345+12345, 12+345+12345, 123+45+12345, 1234+5+12345, by using string indexing to index (r) = 1,2,3,4 before casting to integer, and adds to 12345\*2

Special Thanks to:

-14 Bytes @Jonathan Allen

-1 Byte @ovs

Try it online!

# Answer
> 4 votes
# Neim, 7 bytes

```
S

```

Beware. Contains snakes: `S`

Try it online!

# Answer
> 3 votes
# Japt, ~~31~~ 18 bytes

-13 bytes thanks to @ETHproductions

This approach doesn't work well using Japt. Justin's solution is much better.

```
[U*Ål U¬£tYÃUå+]xx

```

## Explanation:

```
[U*Ål U¬£tYÃUå+]xx
[              ]    // Create a new array
 U*Ål               // Push: Input * Input.slice(1).length()
                    // Push:
      U¬            //   Input, split into chars
        £tY         //   Map; At each char: .substr(Index)
            Uå+     // Push: Cumulative reduce Input; with addition
                xx  // Sum all the items, twice

```

Try it online!

# Answer
> 3 votes
# Japt, ~~15~~ 11 bytes

*-4 bytes thanks to @Shaggy.*

```
¬£iYç
cUz)x

```

Takes input as strings.

Try it online!

## Explanation

```
¬£

```

Split the input array to digits (`¬`) and map by (`£`) the following function, where Y is the index.
`["1", "2", "3"]`

```
iYç

```

The input value (implicit) with `Y` spaces (`ç`) inserted (`i`) at the beginning. This is assigned to `U`.
`["123", " 123", " 123"]`

```
cUz1)x

```

Concatenate that with itself rotated 90° right (`1` time). Then sum (`x`).
`["123", " 123", " 123", " 1", " 12", "123", "23 ", "1 "]` -\> `531`.

# Answer
> 2 votes
# JavaScript, ~~77~~ 74 bytes

*Saved 3 bytes thanks to Value Ink*

```
f=a=>[...a+a].map((_,b)=>a-=-z.substr((b-=n)>0?b:0,b+n),a*=n=(z=a).length)|a

console.log(f('123'));
console.log(f('101'));
console.log(f('12'));
console.log(f('1234567'));
console.log(f('102033'));
```

# Answer
> 2 votes
# Ruby, ~~61~~ 55+1 = 56 bytes

Uses the `-n` flag. Input from STDIN.

```
p (1..~/$/).sum{|i|[$_[i,~/$/],$_[0,i],$_].sum &:to_i}

```

Try it online!

# Answer
> 1 votes
# Pyth, ~~20~~ 19 bytes

My current prefix approach (will hopefully golf further).

```
+*tlQsQssM+_M.__Q._

```

**Test Suite** or try **an alternative approach with the same byte count.**

# Explanation

```
+*tlQsQssM+_M.__Q._  - Full program that reads a String from STDIN, with implicit input.

  tlQ                - Length of the input - 1.
     sQ              - The input converted to an integer.
 *                   - Product of the above two elements. We will call this P.
                 ._  - Prefixes of the input.
          +          - Concatenated with:
           _M.__Q    - The prefixes of the reversed input, reversed.
        sM           - Convert each to an integer.
       s             - Sum.
+                    - Addition of the product P and the sum above.

```

To understand the concept better, we shall take an example, say `"123"`.

* We first get the prefixes of the input. Those are `['1', '12', '123']`.
* Then, we get the prefixes of the reversed input, i.e: `['3', '32', '321']` and reverse each, hence we get `['3', '23', '123']`.
* We concatenate the two lists and convert each element to an integer, so we obtain `[3, 23, 123, 1, 12, 123]`.
* By summing the list, the result is `285`.
* The product `P` is the length of the input - 1 (i.e `2`) multiplied by the integer representation of it (`2 * 123 = 246`).
* In the end, we sum the two results: `285 + 246`, hence we obtain `531`, which is the correct result.

---

# Pyth, 20 bytes

```
+*hlQsQsm+s>Qds<QdtU

```

**Test Suite.**

# Explanation

~~Explanation to come after further golfing.~~ I didn't succeed to golf this further for now (I have ideas though).

```
+*hlQsQsm+s>Qds<QdtUQ  - Full program. Reads from STDIN. Q means input, and is implicit at the end.

  hlQ                  - Length of the input + 1.
     sQ                - The input converted to an integer.
 *                     - Multiply the above. We'll call the result P.
        m         tUQ  - Map over [1...length of the input)
          s>Qd         - input[currentItem:] casted to an integer.
              s<Qd     - input[:currentItem] casted to an integer.
         +             - Sum the above.
       s               - Sum the list.
+                      - Add the sum of the list and P.

```

# Answer
> 1 votes
# q/kdb+, 34 bytes

**Solution:**

```
{sum"J"$((c#c),c-(!)2*c:(#)x)#\:x}

```

**Examples:**

```
q){sum"J"$((c#c),c-(!)2*c:(#)x)#\:x}"1234567"
10288049
q){sum"J"$((c#c),c-(!)2*c:(#)x)#\:x}"123"
531
q){sum"J"$((c#c),c-(!)2*c:(#)x)#\:x}"101"
417
q){sum"J"$((c#c),c-(!)2*c:(#)x)#\:x}"12"
39

```

**Explanation:**

```
{sum"J"$((c#c),c-til 2*c:count x)#\:x} / ungolfed
{                                    } / lambda function
                                    x  / implicit input
                                 #\:   / apply take (#) to each-left element with the right element
        (                       )      / the left element
                       c:count x       / count length and save in variable c
                     2*                / multiply by 2 (e.g. 6)
                 til                   / range, so 0 1 2 3 4 5
               c-                      / vector subtraction, so 3 2 1 0 -1 -2
         (   )                         / do this together
          c#c                          / 3 take 3, so 3 3 3
              ,                        / join, so 3 3 3 3 2 1 0 - 1 -2
    "J"$                               / cast this "123", "123", "123" .. "23" to longs
 sum                                   / sum them up and return result

```

# Answer
> 1 votes
# Jelly, 18 bytes

```
DµṚ;\U;;\ṖVS+Ḍ×¥L$

```

Try it online!

# Answer
> 1 votes
# C (gcc), ~~95~~ ~~84~~ 81 bytes (78 + `-lm` compiler flag)

Hi! This is my first submission, I hope I didn't break any rule.

```
g,o,l;f(char*s){l=atoi(s);while(s[o++])g+=l/pow(10,o)+atoi(s+o);return g+l*o;}

```

Try it online!

## Ungolfed, without warnings:

```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int g,o,l;

int f(char *s){
  l = atoi(s);

  while(s[o++]) {
    g+=l/pow(10,o)+atoi(s+o);
  }

  return g+l*o;
}

int main(void){
  printf("%d\n",f("1234567"));
  return 0;
}

```

# Answer
> 1 votes
# Swift 3, 213 bytes

```
func f(n:String){print((n.characters.count-1)*Int(n)!+(0..<n.characters.count).map{r in Int(n[n.index(n.startIndex,offsetBy:r)..<n.endIndex])!+Int(n[n.startIndex..<n.index(n.endIndex,offsetBy:-r)])!}.reduce(0,+))}

```

Cannot be tested online, because it is slow and times out. You can try it in Swift Playgrounds if you wish to test it.

## Sample run

**Input:**

```
f(n:"123")
f(n:"101")
f(n:"1234567")

```

**Output:**

```
531
417
10288049

```

# Answer
> 1 votes
# Jelly, 12 bytes

```
LḶṚ⁶ẋ;€µ;ZVS

```

Try it online!

Takes input as a string. Creates the "parallelogram" as a matrix of characters, then evaluates each row and column to get the numbers to sum.

## Explanation

```
LḶṚ⁶ẋ;€µ;ZVS  Input: string S
L             Length
 Ḷ            Lowered range - [0, 1, ..., len(S)-1]
  Ṛ           Reverse
   ⁶          The char ' ' (space)
    ẋ         Create that many characters of each in the range
     ;€       Prepend each to S
       µ      Begin a new monadic chain
        ;     Concatenate with
         Z    Transpose
          V   Eval each string
           S  Sum

```

# Answer
> 1 votes
# , ~~168~~ ~~162~~ 103 bytes

*-6 bytes by not using c()*

*-59 bytes thanks to @Giuseppe*

```
function(n){k=nchar(n)
a=k*strtoi(n)
for(i in 1:k)for(j in i:k)a=a+(i==1|j==k)*strtoi(substr(n,i,j))
a}

```

Try it online!

Takes input as a string.

I'm absolutely certain there are improvements to be made, primarily in leveraging any of R's strengths... but in a challenge that's basically string manip, I'm struggling to see how.

Edit: Much better now that I'm not iterating on a bad idea!

# Answer
> 1 votes
# Java 8, ~~147~~ ~~137~~ ~~126~~ ~~116~~ 114 bytes

```
n->{Integer l=(n+"").length(),r=n*l,i=0;for(;++i<l*2;)r+=l.valueOf((n+"").substring(i>l?i-l:0,i<l?i:l));return r;}

```

-13 bytes (137 → 126 and 116 → 114) thanks to *@OlivierGrégoire*.

**Explanation:**

Try it here.

```
n->{                          // Method with integer as parameter and return-type
  Integer l=(n+"").length(),  //  Length of the input integer
      r=n*l,                  //  Result-integer (starting at `n*l`)
      i=0;                    //  Index-integer (starting at 0)
  for(;++i<l*2;               //  Loop from 0 through two times `l` (exclusive)
    r+=                       //   Add to the result-integer sum:
       l.valueOf((n+"").substring(
                              //    Substring of input, converted to integer:
        i>l?                  //     If `i` is larger than `l`:
         i-l                  //      Substring starting at `i-l`
        :                     //     Else:
         0,                   //      Substring starting at 0
        i<l?                  //     If `i` is smaller than `l`:
         i                    //      Substring ending at `i` (exclusive)
        :                     //     Else:
         l)                   //      Substring ending at `l` (exclusive)
  );                          //  End of loop
  return r;                   //  Return resulting sum
}                             // End of method

```

# Answer
> 0 votes
# Perl 5, 53 + 1 (-n) = 54 bytes

```
$r=$_*(@n=/./g);for$i(@n){$r+=$_+($t=(chop).$t)}say$r

```

Try it online!

# Answer
> 0 votes
# Mathematica, 77 bytes

```
(s=IntegerDigits@#;t=Length@s;Tr[FromDigits/@Table[s~Take~i,{i,-t,t}]]+t#-#)&

```

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


title: Count arrays of periods

text:
# Question
Title: Count arrays of periods
The `period` of a string is the shortest non-zero shift so that the string matches itself, ignoring any parts that overhang. So for example, `abcabcab` has period `3`. By convention we say that if there is no such shift then a string has period equal to its length. So the period of `abcde` is `5` and the period of `a` is `1`.

In more formal terms, the period of a string `S` is the minimum `i > 0` so that `S[1,n-i] == S[i+1,n]` (indexing from `1`).

For a given string S of power of two length, we will compute the period of all its prefixes of power of two length. For example, consider `S = abcabcab`. The periods we will compute are:

```
'a', 1
'ab', 2
'abca', 3
'abcabcab', 3

```

We will in fact just output the array of periods, that is `[1, 2, 3, 3]`.

For a given positive power of two `n`, consider all possible binary strings `S`. Recall that a binary string is simply a string of `1`s and `0`s so there are exactly `2^n` such strings (that is `2` to the power `n`). For each one we can compute this array of periods.

> The challenge is to write code that takes `n` (a power of two) as input and computes how many distinct such arrays there are.

The answers for `n = 1, 2, 4, 8, 16, 32, 64, 128` are:

```
1, 2, 6, 32, 320, 6025, 216854, 15128807

```

The full set of distinct period arrays for `n = 4` is:

```
1, 1, 1
1, 1, 3
1, 1, 4
1, 2, 2
1, 2, 3
1, 2, 4

```

**Score**

I will run your code on my computer running Ubuntu for 10 minutes. Your score is the largest `n` for which your code terminates in that time. In the case of a tie, the answer that completes the joint largest `n` fastest wins. In the case that there is a tie within 1 second on timings, the first answer posted wins.

**Languages and libraries**

You can use any available language and libraries you like. Please include a full explanation for how to run/compile your code in Linux if at all possible.\`

Your code should actually compute the answers and not, for example, just output precomputed values.

**Leading entries**

* **2 minutes and 21 seconds** for **n = 128** in **C#** by Peter Taylor
* **9 seconds** for **n = 32** in **Rust** by isaacg

# Answer
## C#, n=128 in about 2:40

```
using System;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox
{
    class PPCG137436
    {
        public static void Main(string[] args)
        {
            if (args.Length == 0) args = new string[] { "1", "2", "4", "8", "16", "32", "64", "128" };

            foreach (string arg in args)
            {
                Console.WriteLine(Count(new int[(int)(0.5 + Math.Log(int.Parse(arg)) / Math.Log(2))], 0));
            }
        }

        static int Count(int[] periods, int idx)
        {
            if (idx == periods.Length)
            {
                //Console.WriteLine(string.Join(", ", periods));
                return 1;
            }

            int count = 0;
            int p = idx == 0 ? 1 : periods[idx - 1];
            for (int q = p; q <= 1 << (idx + 1); q++)
            {
                periods[idx] = q;
                if (q == p || q > 1 << idx || p + q - Gcd(p, q) > 1 << idx && UnificationPasses(periods, idx, q)) count += Count(periods, idx + 1);
            }

            return count;
        }

        private static int Gcd(int a, int b)
        {
            while (a > 0) { int tmp = a; a = b % a; b = tmp; }
            return b;
        }

        private static bool UnificationPasses(int[] periods, int idx, int q)
        {
            UnionSet union = new UnionSet(1 << idx);
            for (int i = 0; i <= idx; i++)
            {
                for (int j = 0; j + periods[i] < Math.Min(2 << i, 1 << idx); j++) union.Unify(j, j + periods[i]);
            }

            IDictionary<int, long> rev = new Dictionary<int, long>();
            for (int k = 0; k < 1 << idx; k++) rev[union.Find(k)] = 0L;
            for (int k = 0; k < 1 << idx; k++) rev[union.Find(k)] |= 1L << k;

            long zeroes = rev[union.Find(0)]; // wlog the value at position 0 is 0

            ISet<int> onesIndex = new HashSet<int>();

            // This can be seen as the special case of the next loop where j == -1.
            for (int i = 0; i < idx; i++)
            {
                if (periods[i] == 2 << i) onesIndex.Add((2 << i) - 1);
            }
            for (int j = 0; j < idx - 1 && periods[j] == 2 << j; j++)
            {
                for (int i = j + 1; i < idx; i++)
                {
                    if (periods[i] == 2 << i)
                    {
                        for (int k = (1 << j) + 1; k <= 2 << j; k++) onesIndex.Add((2 << i) - k);
                    }
                }
            }

            for (int i = 1; i < idx; i++)
            {
                if (periods[i] == 1) continue;

                int d = (2 << i) - periods[i];
                long dmask = (1L << d) - 1;
                if (((zeroes >> 1) & (zeroes >> periods[i]) & dmask) == dmask) onesIndex.Add(periods[i] - 1);
            }

            long ones = 0L;
            foreach (var key in onesIndex) ones |= rev[union.Find(key)];

            if ((zeroes & ones) != 0) return false; // Definite contradiction!

            rev.Remove(union.Find(0));
            foreach (var key in onesIndex) rev.Remove(key);

            long[] masks = System.Linq.Enumerable.ToArray(rev.Values);

            int numFilteredMasks = 0;
            long set = 0;
            long M = 0;
            for (int i = 1; i <= idx; i++)
            {
                if (periods[i - 1] == 1) continue;

                // Sort the relevant masks to the start
                if (i == idx) numFilteredMasks = masks.Length; // Minor optimisation: skip the filter because we know we need all the masks
                long filter = (1L << (1 << i)) - 1;
                for (int j = numFilteredMasks; j < masks.Length; j++)
                {
                    if ((masks[j] & filter) != 0)
                    {
                        var tmp = masks[j];
                        masks[j] = masks[numFilteredMasks];
                        masks[numFilteredMasks++] = tmp;
                    }
                }

                // Search for a successful assignment, using the information from the previous search to skip a few initial values in this one.
                set |= (1L << numFilteredMasks) - 1 - M;
                M = (1L << numFilteredMasks) - 1;
                while (true)
                {
                    if (TestAssignment(periods, i, ones, masks, set)) break;
                    if (set == 0) return false; // No suitable assignment found

                    // Gosper's hack with variant to reduce the number of bits on overflow
                    long c = set & -set;
                    long r = set + c;
                    set = (((r ^ set) >> 2) / c) | (r & M);
                }
            }

            return true;
        }

        private static bool TestAssignment(int[] periods, int idx, long ones, long[] masks, long assignment)
        {
            for (int j = 0; j < masks.Length; j++, assignment >>= 1) ones |= masks[j] & -(assignment & 1);
            for (int i = idx - 1; i > 0; i--) // i == 0 is already handled in the unification process.
            {
                if (Period(ones, 2 << i, periods[i - 1]) < periods[i]) return false;
            }

            return true;
        }

        private static int Period(long arr, int n, int min)
        {
            for (int p = min; p <= n; p++)
            {
                // If the bottom n bits have period p then the bottom (n-p) bits equal the bottom (n-p) bits of the integer shifted right p
                long mask = (1L << (n - p)) - 1L;
                if ((arr & mask) == ((arr >> p) & mask)) return p;
            }

            throw new Exception("Unreachable");
        }

        class UnionSet
        {
            private int[] _Lookup;

            public UnionSet(int size)
            {
                _Lookup = new int[size];
                for (int k = 0; k < size; k++) _Lookup[k] = k;
            }

            public int Find(int key)
            {
                var l = _Lookup[key];
                if (l != key) _Lookup[key] = l = Find(l);
                return l;
            }

            public void Unify(int key1, int key2)
            {
                int root1 = Find(key1);
                int root2 = Find(key2);

                if (root1 < root2) _Lookup[root2] = root1;
                else _Lookup[root1] = root2;
            }
        }
    }
}

```

Extending to n=256 would require switching to `BigInteger` for the masks, which probably kills the performance too much for n=128 to pass without new ideas, let alone n=256.

Under Linux, compile with `mono-csc` and execute with `mono`.

### Basic explanation

I'm not going to do a line-by-line dissection, just an overview of the concepts.

As a rule of thumb, I'm happy to iterate through on the order of 250 elements in a brute-force combinatoric program. To get to n=128 it is therefore necessary to use an approach which doesn't analyse every bitstring. So rather than working forwards from bit strings to period sequences, I work backwards: given a period sequence, is there a bitstring which realises it? For n=2x there's an easy upper bound of 2x(x+1)/2 period sequences (vs 22x bitstrings).

Some of the arguments use the **string periodicity lemma**:

> Let `p` and `q` be two periods of a string of length `n`. If `p + q ≤ n + gcd(p, q)` then `gcd(p, q)` is also a period of the string.

Wlog I will assume that all of the bitstrings under consideration start with `0`.

Given a period sequence `[p<sub>1</sub> p<sub>2</sub> ... p<sub>k</sub>]` where `p<sub>i</sub>` is the period of the prefix of length 2i (`p<sub>0</sub> = 1` always), there are some easy observations about possible values of `p<sub>k+1</sub>`:

* `p<sub>k+1</sub> ≥ p<sub>k</sub>` since a period of a string `S` is also a period of any prefix of `S`.
* `p<sub>k+1</sub> = p<sub>k</sub>` is always a possible extension: just repeat the same primitive string for twice as many characters.
* `2<sup>k</sup> < p<sub>k+1</sub> ≤ 2<sup>k+1</sup>` is always a possible extension. It suffices to show this for `p<sub>k+1</sub> = 2<sup>k</sup>+1` because an aperiodic string of length `L` can be extended to an aperiodic string of length `L+1` by appending any letter which isn't its first letter.

Take a string `Sx` of length 2k whose period is `p<sub>k</sub>` and consider the string `SxyS` of length 2k+1. Clearly `SxyS` has *a* period 2k+1. Suppose its period `q` is smaller.

Then `2<sup>k</sup>+1 + q ≤ 2<sup>k+1</sup>+1 ≤ 2<sup>k+1</sup> + gcd(2<sup>k</sup>+1, q)` so by the periodicity lemma `gcd(2<sup>k</sup>+1, q)` is also a period of `SxyS`, and since the greatest divisor is less than or equal to its arguments and `q` is the smallest period, we require `q` to be a proper factor of 2k+1. Since its quotient cannot be 2, we have `q ≤ (2<sup>k</sup>+1)/3`.

Now, since `q ≤ 2<sup>k</sup>` is a period of `SxyS` it must be a period of `Sx`. But *the* period of `Sx` is `p<sub>k</sub>`. We have two cases:

1. `gcd(p<sub>k</sub>, q) = p<sub>k</sub>`, or equivalently `p<sub>k</sub>` divides exactly into `q`.
    2. `p<sub>k</sub> + q > 2<sup>k</sup> + gcd(p<sub>k</sub>, q)` so that the periodicity lemma doesn't force a smaller period.

Consider first the second case. `p<sub>k</sub> > 2<sup>k</sup> + gcd(p<sub>k</sub>, q) - q ≥ 2<sup>k</sup>+1 - q ≥ 2<sup>k</sup>+1 - (2<sup>k</sup>+1)/3 ≥ 2q`, contradicting the definition of `p<sub>k</sub>` as the period of `Sx`. Therefore we are forced into the conclusion that `p<sub>k</sub>` is a factor of `q`.

But since `q` is a period of `Sx` and `p<sub>k</sub>` is the period of `Sx`, the prefix of length `q` is just `q/p<sub>k</sub>` copies of the prefix of length `p<sub>k</sub>`, so we see that `p<sub>k</sub>` is also a period of `SxyS`.

Therefore the period of `SxyS` is either `p<sub>k</sub>` or 2k+1. But we have two options for `y`! At most one choice of `y` will give period `p<sub>k</sub>`, so at least one will give period 2k+1. QED.
* The periodicity lemma allows us to reject some of the remaining possible extensions.
* Any extension which hasn't passed a quick-accept or a quick-reject test needs to be tested constructively.

The construction of a bitstring given a period sequence is essentially a satisifiability problem, but it has a lot of structure. There are `2<sup>k</sup> - p<sub>k</sub>` simple equality constraints implied by each prefix period, so I use a union set data structure to combine bits into independent clusters. This was enough to tackle n=64, but for n=128 it was necessary to go further. I employ two useful lines of argument:

1. If the prefix of length `M` is `01<sup>M-1</sup>` and the prefix of length `L > M` has period `L` then the prefix of length `L` must end in `1<sup>M</sup>`. This is most powerful precisely in the cases which would otherwise have most independent clusters, which is convenient.
2. If the prefix of length `M` is `0<sup>M</sup>` and the prefix of length `L > M` has period `L - d` with `d < M` and ends in `0<sup>d</sup>` then it must in fact end in `10<sup>d</sup>`. This is most powerful at the opposite extreme, when the period sequence starts with a lot of ones.

If we don't get an immediate contradiction by forcing the cluster with the first bit (assumed to be zero) to be one then we brute force (with some micro-optimisations) over the possible values for the unforced clusters. Note that the order is in descending number of ones because if the `i`th bit is a one then the period cannot be `i` and we want to avoid periods which are shorter than the ones which are already enforced by the clustering. Going down increases the chances of finding a valid assignment early.
> 9 votes

# Answer
# Rust, 32, 10s ~~11s~~ ~~29s~~ on my laptop

Call it with the bitsize as the command line argument.

Clever techniques: represent bitstrings directly as numbers, use bittwiddling to check for cycles. Only search the first half of the bitstrings, those starting with 0, because the array of periods of a bitstring and its inverse (0s swapped for 1s) are identical. If every possibility for the final position has already occured, I don't search it.

More clever stuff:

To deduplicate each block (strings where the first half of the bits are the same) I use a bitvector, which is much faster than a hashset, since the final cycle lengths don't need hashing.

Also, I skip the first steps of the cycle checking, because I know that the final cycle can't be shorter than the second-to-last cycle.

After lots of profiling, I can now tell that almost all of the time is being used productively, so algorithmic improvements will be required to improve from here, I think. I also switched to 32 bit integers to save a little more time.

```
//extern crate cpuprofiler;
//use cpuprofiler::PROFILER;

extern crate bit_vec;
use bit_vec::BitVec;

use std::collections::HashSet;

fn cycle_len(num: u32, mask: u32, skip_steps: usize) -> usize {
    let mut left = num >> skip_steps;
    let mut mask = mask >> skip_steps;
    let mut steps = skip_steps;
    loop {
        left >>= 1;
        if left == (num & mask) {
            return steps;
        }
        mask >>= 1;
        steps += 1;
    }
}

fn all_cycles(size_log: usize) -> HashSet<Vec<usize>> {
    let mut set = HashSet::new();
    if size_log == 0 {
        set.insert(vec![]);
        return set;
    } else if size_log == 1 {
        set.insert(vec![0]);
        set.insert(vec![1]);
        return set;
    }
    let size: usize = 1 << size_log;
    let half_size: usize = 1 << size_log - 1;
    let shift_and_mask: Vec<(usize, u32)> = (1..size_log)
        .map(|subsize_log| {
            let subsize = 1 << subsize_log;
            (size - subsize, (1 << (subsize - 1)) - 1)
        })
        .collect();
    let size_mask = (1 << (size - 1)) - 1;
    for block in 0..(1 << (half_size - 1)) as u32 {
        let start: u32 = block << half_size;
        if block % 1024 == 0 {
            eprintln!(
                "{} ({:.2}%): {}",
                start,
                start as f64 / (1u64 << size - 1) as f64 * 100f64,
                set.len()
            );
        }
        let leader = {
            let mut cycles = Vec::new();
            for &(shift, mask) in &shift_and_mask {
                let subnum = start >> shift;
                cycles.push(cycle_len(subnum, mask, 0));
            }
            cycles
        };
        let &end = leader.last().unwrap();
        if (end..size).all(|count| {
            let mut new = leader.clone();
            new.push(count);
            set.contains(&new)
        })
        {
            continue;
        }
        let mut subset = BitVec::from_elem(size, false);
        for num in start..start + (1 << half_size) {
            subset.set(cycle_len(num, size_mask, end), true);
        }
        for (unique_cycle_len, _) in subset.into_iter().enumerate().filter(|x| x.1) {
            let mut new_l = leader.clone();
            new_l.push(unique_cycle_len);
            set.insert(new_l);
        }
    }
    set
}

fn main() {
    let size: f32 = std::env::args().nth(1).unwrap().parse().unwrap();
    let size_log = size.log2() as usize;
    //PROFILER.lock().unwrap().start("./my-prof.profile").unwrap();
    let cycles = all_cycles(size_log);
    //PROFILER.lock().unwrap().stop().unwrap();
    println!(
        "Number of distinct arrays of periods of bitstrings of length {} is {}",
        1 << size_log,
        cycles.len()
    );
}

```

Put `bit-vec = "0.4.4"` in your Cargo.toml

If you'd like to run this, clone this: github.com/isaacg1/cycle then `Cargo build --release` to build, then `Cargo run --release 32` to run.
> 7 votes

# Answer
# Rust, 16

```
use std::collections::HashSet;
use std::io;

fn main() {
	print!("Enter a pow of two:");
	let mut input_text = String::new();
    io::stdin()
        .read_line(&mut input_text)
        .expect("failed to read from stdin");

    let n_as_string = input_text.trim();
	match n_as_string.parse::<usize>() {
		Ok(n) => {
			let log2 = (n as f64).log(2_f64) as usize;
			if n != 1 << log2 {
				panic!("{} is not a power of two", n);
			}
			let count = compute_count_array(log2, n);
			println!("n = {} -> count = {}", n, count);
		}
		Err(_) => { panic!("{} is not a number", n_as_string); }
	}
}

fn compute_count_array(log2:usize, n: usize) -> usize {
	let mut z = HashSet::new();

	let mut s:Vec<bool> = vec!(false; n);
	loop {
		let mut y:Vec<usize> = vec!();
		for j in 0..log2+1 {
			let p = find_period(&s[0..1<<j]);
			y.push(p);
		}
		z.insert(y);
		if !next(&mut s) {
			break;
		}
	}
	z.len()
}

#[inline]
fn find_period(s: &[bool]) -> usize {
	let n=s.len();
	let mut j=1;
	while j<n {
		if s[0..n-j] == s[j..n] {
			return j;
		}
		j+=1;
    }
	n
}

#[inline]
fn next(s:&mut Vec<bool>) -> bool {
	if s[0] {
		s[0] = false;
		for i in 1..s.len() {
			if s[i] {
				s[i] = false;
			} else {
				s[i] = true;
				return true;
			}
		}
		return false
	} else {
		s[0] = true;
	}
	true
}

```

Try it online!

Compilation: `rustc -O <name>.rs`

The string is implemented as a Bool vector.

* The `next` function iterate through the combinations ;
* The `find_period` takes a Bool slice and returns the period ;
* The `compute_count_array` does the job for each "power of two" subsequence of each combinations of Bools.

Theoretically, no overflow is expected until `2^n` exceeds the u64 maximum value, ie `n > 64`. This limit could be outreached with an expensive test on s=\[true, true, ..., true\].

Bad news is: it returns 317 for n=16, but I don't know why. I don't know either if it will make it in ten minutes for n=32, since the `Vec<bool>` is not optimized for this kind of computation.

**EDIT**

1. I've managed to remove the limit of 64 for `n`. Now, it won't crash until `n` is greater than the max usize integer.
2. I found why the previous code returned 317 for `n=32`. I was counting *sets* of periods and not *arrays* of periods. There were three arrays with the same elements:

```
[1, 2, 3, 3, 8] -> {1, 2, 3, 8}
[1, 2, 3, 8, 8] -> {1, 2, 3, 8}
[1, 1, 3, 3, 7] -> {1, 3, 7}
[1, 1, 3, 7, 7] -> {1, 3, 7}
[1, 1, 3, 3, 8] -> {1, 3, 8}
[1, 1, 3, 8, 8] -> {1, 3, 8}

```

Now it works. It is still slow but it works.
> 4 votes

# Answer
# C - 16

It fails on values greater than 16 cuz of overflow.

I have no idea how fast this runs cuz im on a chromebook running it on repl.it.

Just implements the question as it reads, goes through all bit strings, calculates the period arrays, and checks if they have already been counted.

```
#include "stdio.h"
#include <stdbool.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

int per(int s[], int l) {
  int period = 0;
  while (1) {
    period++;

    bool check = 1;
    int i;
    for (i=0; i<l-period; i++) {
      if (s[i]!=s[i+period]) {
        check = 0;
        break;
      }
    }
    if (check) {
      return period;
    }
  }
}

bool perar(int* s, int l, int* b, int i) {
  int n = 1;
  int j=0;
  while (n<=l) {
    b[i*l+j] = per(s, n);
    n=n<<1;
    j++;
  }

  for (j=0;j<i;j++) {
    int k;
    bool check = 1;
    for(k=0; k<l; k++) {
      if (b[j*l+k] != b[i*l+k]) {
        check = 0;
        break;
      }
    }
    if (check) {
      return 0;
    }
  }
  return 1;
}

int main(int argc, char* argv[]) {
  int n;
  scanf("%d", &n);
  puts("Running...");
  int i;
  int c = 0;
  int* a = malloc(n*sizeof(int));
  int m=pow(2, n);
  int* b = malloc(m*n*sizeof(int));
  for (i=0; i<m; i++) {
    int j;
    for (j=0; j<n; j++) {
      a[j] = (i>>j)&1;
    }
    c+=perar(a, n, b, i);
  }
  printf("Answer: %d\n", c);
  return 0;
}

```

Just compile it with gcc, etc.
> 2 votes

# Answer
## Haskell

```
import qualified Data.Set as S
import Data.Bits

period :: Int -> Int -> Int
period num bits = go (bits-2) (div prefix 2) (clearBit prefix $ bits-1)
  where
  prefix = (2^bits-1) .&. num
  go p x y
    | x == y    = p
    | otherwise = go (p-1) (div x 2) (clearBit y p)

allPeriods :: Int ->  [[Int]]
allPeriods n = map periods [0..div(2^n)2-1]
  where
  periods num = map (period num) powers
  powers = takeWhile (<=n) $ iterate (*2) 2

main = readLn >>= print . S.size . S.fromList . allPeriods

```

Compile with `ghc -O2`. Try it online!

Runs in less than 0.1sec on my 6 year old laptop hardware for `n=16`. `n=32` takes ~~99~~ 92min, so I'm factor 9 or 10 off. I've tried caching the periods in a lookup table so I don't have to recalculate them over and over again, but this quickly runs out of memory on my 4GB machine.
> 2 votes

# Answer
# Python 2 (PyPy), 16

```
import sys
import math
def do(n):
 masks=[]
 for i in range(n):
  masks+=[(1<<((2<<i)-1))-1]
 s=set()
 bits=1<<n
 for i in xrange(1<<bits):
  r=[0,]*n
  for j in range(len(masks)):
   mask=masks[j]
   k,c=i>>bits-(2<<j),1
   d=k>>1
   while k&mask^d:
    d>>=1
    mask>>=1
    c+=1
   r[j]=c
  s|={tuple(r)}
 return len(s)
print do(int(math.log(int(sys.argv[1]),2)))

```
> 1 votes

# Answer
# \[C++\], 32, 4 minutes

```
#include <iostream>
#include <vector>

typedef unsigned int u;
template<typename T, typename U>
u Min(T a, U b) {
    return a < b ? a : b;
}

template<typename T, typename U>
u Max(T a, U b) {
    return a > b ? a : b;
}

u Mask(int n) {
    if (n < 0) n = 0;
    return ~((u)(-1) << n);
}
u MASKS[32];

inline u Rshift(u v, int n) {
    return n < 0 ? v >> (-1*n)
    : n > 0 ? v << n
    : n;
}

int GetNextPeriodId(u pattern, int pattern_width, int prior_id) {
    int period = (prior_id % (pattern_width>>1)) + 1;
    int retval = prior_id * pattern_width;

    for (; period < pattern_width; period+=1) {
        u shift = pattern >> period;
        int remainder = pattern_width-period;
        u mask = MASKS[period];

        for (;remainder >= period && !((pattern ^ shift) & mask);
             shift >>= period, remainder -= period);

        if (remainder > period) continue;
        if (remainder == 0 || !((pattern ^ shift) & MASKS[remainder])) {
            retval += (period-1);
            break;
        }
    }
    if (period == pattern_width) {
        retval += pattern_width-1;
    }
    return retval;
}

int ParseInput(int argc, char** argv) {
    if (argc > 1) {
        switch(atoi(argv[1])) {
            case 1:
                return 1;
            case 2:
                return 2;
            case 4:
                return 4;
            case 8:
                return 8;
            case 16:
                return 16;
            case 32:
                return 32;
            default:
                return 0;
        }
    }
    return 0;
}

void PrintId(u id, int patternWidth) {
    for(;patternWidth > 0; id /= patternWidth, patternWidth >>= 1) {
        std::cout << (id % patternWidth)+1 << ",";
    }
    std::cout << std::endl;
}

int TestAndSet(std::vector<bool>& v, int i) {
    int retval = v[i] ? 0 : 1;
    v[i] = true;
    return retval;
}

std::vector<bool> uniques(1<<15);
int uniqueCount = 0;

void FillUniques(u i, int id, int target_width, int final_width) {
    int half_size = target_width / 2;
    u end = 1u<<(half_size-1);
    u mask = MASKS[half_size];
    u lowers[] = { i, (~i)&mask };
    for (u j = 0ul; j < end; j++) {
        u upper = j << half_size;
        u patterns[] = { (upper|lowers[0]), (upper|lowers[1]) };
        for (int k=0; k < sizeof(patterns)/sizeof(patterns[0]); k+=1) {
            int fid = GetNextPeriodId(patterns[k], target_width, id);
            if (target_width != final_width) {
                FillUniques(patterns[k], fid, target_width*2, final_width);
            } else {
                if (TestAndSet(uniques, fid)) {
                    uniqueCount += 1;
                }
            }
        }
    }
}

int main(int argc, char** argv) {
    for (int i = 0; i < 32; i++) {
        MASKS[i] = Mask(i);
    }
    int target_width = 32; // ParseInput(argc, argv);
    if (!target_width) {
        std::cout << "Usage: " << argv[0] << " [1|2|4|8|16|32]" << std::endl;
        return 0;
    }
    if (target_width == 1) {
        std::cout << 1 << std::endl;
        return 0;
    }
    FillUniques(0, 0, 2, target_width);
    std::cout << uniqueCount << std::endl;
    return 0;
}

```
> 1 votes

---
Tags: array, fastest-code
---


title: Make a lost RNG

text:
# Question
Title: Make a lost RNG
Lost is a 2-D programming language where the start position and direction of the ip are entirely random.

This makes it very difficult to make deterministic Lost programs. However today we are not writing a deterministic program, we are writing an RNG.

Write a Lost program that takes no input and outputs a single digit (0,1,2,3,4,5,6,7,8, or 9), with all digits having an equal probability of being output. Since Lost's start location and direction is the only source of randomness, the only way to do this is to have every location in your source output a different number from 0 to 9 with an equal number outputting each digit.

You can calculate the probability of each digit by using the `-Q` flag and piping it into this python script

```
import sys
a=sys.stdin.read().split()[:-1]
for x in range(10):print x,':',a.count(`x`)
print[x for x in a if x not in list("1234567890")]

```

Try it online!

This is so answers will be scored in bytes with less bytes being better.

---

## An overview of Lost

Lost is a wrapping implicit IO 2D language taking much from the mold of Klein. Here is a quick cheatsheet of what lost commands do

* `\`,`/`,`|` Mirrors the ip
* `<`,`^`,`>`,`v` Points the ip in a direction
* `[` Reflects the ip if it is moving east; becomes `]` if the ip is moving horizontally
* `]` Reflects the ip if it is moving west; becomes `[` if the ip is moving horizontally
* `!` Skips the next operation
* `?` Pops off the top of the stack and jumps if not zero
* `:` Duplicates the top of the stack
* `$` Swaps the top two items of the stack
* `(` Pops from the stack and pushes to the scope
* `)` Pops from the scope and pushes to the stack
* `0`-`9` pushes n to the top of the stack
* `"` Starts and ends a string literal. During a string literal commands are not run and instead their character values are pushed to the stack.
* `+` Adds the top two numbers
* `*` Multiplies the top two numbers
* `-` Multiplies the top by -1
* `%` Turns the safety off
* `#` Turns the safety on
* `@` Ends execution if the safety is off (starts on)

# Answer
> 14 votes
# ~~81~~ 101 bytes

This might be golfable further ...

```
>%(0@>%(1@>%(2@>%(3@>%(4@>%(5@>%(6@>%(7@>%(8@>%(9@
^<<<<^<<<<^<<<<^<<<<^<<<<^<<<<^<<<<^<<<<^<<<<^<<<<

```

Try it online!

# Answer
> 13 votes
# Lost, 54 bytes

```
>%(0@>%(1@
@>%(2@>%(3
5@>%(4@>%(
(7@>%(6@>%
%(9@>%(8@>

```

Try it online!

Just copied from pppery's answer and do some random stuff. I know nothing about Lost language. And I even do not know what happening for above codes. Is this work? (I don't know)

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


title: Fallout Terminal Hacking

text:
# Question
Title: Fallout Terminal Hacking
Anyone here a die-hard Bethesda fan? Maybe you prefer Obsidian Entertainment? Well, if you're either of those things than the following picture should be relatively familiar to you.

I've taken the liberty of preparing a rather unique ASCII-Art challenge, so here's the first clue as to what I'm going to have you do:

```
  _____________________________________________________
 /                                                     \
|     _____________________________________________     |
|    |                                             |    |
|    | Welcome to ROBCO Industries (TM) Termlink   |    |
|    | Password Required                           |    |
|    | Attempts Remaining:                         |    |
|    |                                             |    |
|    | 0x01                 | 0x0D                 |    |
|    | 0x02                 | 0x0E                 |    |
|    | 0x03                 | 0x0F                 |    |
|    | 0x04                 | 0x10                 |    |
|    | 0x05                 | 0x11                 |    |
|    | 0x06                 | 0x12                 |    |
|    | 0x07                 | 0x13                 |    |
|    | 0x08                 | 0x14                 |    |
|    | 0x09                 | 0x15                 |    |
|    | 0x0A                 | 0x16                 |    |
|    | 0x0B                 | 0x17                 |    |
|    | 0x0C                 | 0x18                 |    |
|    |_____________________________________________|    |
|                                                       |
\_______________________________________________________/
       \_______________________________________/

```

This is a very basic (blank) template for the RobCo Fallout terminal design in pure ASCII, your job will be to:

* First, generate this template.
* Then, given a list of strings `l` and a number `0 <= n <= 4` to fill it up!

The two dynamic parts of a fallout hacking terminal are:

# The Number of Attempts

* The number of attempts you have remaining (indicated by space delimited boxes.
    + For the purpose of this challenge you will be using `X` instead of .

# The Passwords

* The passwords, defined by `l`, are interspersed with random printable ASCII symbols.
* The passwords, as you can tell by the example, can wrap multiple rows (`NAMES`).
* All passwords in the terminal screen should have an equal chance of being anywhere.
* All passwords can be expected to be of equal length, though this doesn't matter.
* The list of symbols usable to separate passwords are: `!"#$%&'()*+/:;<=>?@[\]^_{|}`.
* All passwords in `l` must be of equal length.
* PASSWORDS MUST HAVE THE POTENTIAL TO WRAP BETWEEN BOTH COLUMNS.
    + This also goes for rows, but only to a higher byte address (0x18-\>0x01 is invalid).
* The display space for passwords on either side is 15 wide (with a space on either side).
    + You may assume no words in `l` will be longer than this.
* Passwords are alphabetical only, meaning only letters.

---

Example:

`l = ["SMART","ENACT","SWORE","PITYS","SMELL","CARTS","RACES"]`, `n = 4`

```
  _____________________________________________________
 /                                                     \
|     _____________________________________________     |
|    |                                             |    |
|    | Welcome to ROBCO Industries (TM) Termlink   |    |
|    | Password Required                           |    |
|    | Attempts Remaining: X X X X                 |    | # N = 4 drives these X's.
|    |                                             |    |
|    | 0x01 $?_/%$ENACT||"} | 0x0D TYS"_'$\#|^%&{} |    |
|    | 0x02 }:!*@{/_<"[]#>; | 0x0E #{!"^&\]'|}_[$% |    |
|    | 0x03 $%&'()*+/:;<\_' | 0x0F }|[(%SMELL/_$@( |    |
|    | 0x04 ^SMART(!@$*'^_@ | 0x10 []_#!"{|}'%$\&^ |    |
|    | 0x05 (*@#%}*(!%)^(_! | 0x11 %$}[!\#'^&_]{|" |    |
|    | 0x06 $%&'()*+/:;<_@) | 0x12 \SWORE|%'_!}\^" |    |
|    | 0x07 "/')=*%!&>#<:$+ | 0x13 ^{['&$|!_]%\"#} |    |
|    | 0x08 ;'*$&"(<%!#)RAC | 0x14 ']!|^#[$"_\}&{% |    |
|    | 0x09 ES:($&';%#+"<*/ | 0x15 @)($!CARTS*!@$_ |    |
|    | 0x0A ;'*$&"(<%!#)/+: | 0x16 !#%${"'}&[]^|_\ |    |
|    | 0x0B |'_!}$\%["#^{&] | 0x17 ]"_#$&}^%[{|\'! |    |
|    | 0x0C #{!"^&\]'|}_[PI | 0x18 _![&#{$%\^'|}"] |    | # Notice how PITYS wrapped.
|    |_____________________________________________|    |
|                                                       |
\_______________________________________________________/
       \_______________________________________/

```

If `n = 2` on the same example:

```
  _____________________________________________________
 /                                                     \
|     _____________________________________________     |
|    |                                             |    |
|    | Welcome to ROBCO Industries (TM) Termlink   |    |
|    | Password Required                           |    |
|    | Attempts Remaining: X X                     |    | # N = 2 drives these X's.
|    |                                             |    |
|    | 0x01 $?_/%$ENACT||"} | 0x0D TYS"_'$\#|^%&{} |    |
|    | 0x02 }:!*@{/_<"[]#>; | 0x0E #{!"^&\]'|}_[$% |    |
|    | 0x03 $%&'()*+/:;<\_' | 0x0F }|[(%SMELL/_$@( |    |
|    | 0x04 ^SMART(!@$*'^_@ | 0x10 []_#!"{|}'%$\&^ |    |
|    | 0x05 (*@#%}*(!%)^(_! | 0x11 %$}[!\#'^&_]{|" |    |
|    | 0x06 $%&'()*+/:;<_@) | 0x12 \SWORE|%'_!}\^" |    |
|    | 0x07 "/')=*%!&>#<:$+ | 0x13 ^{['&$|!_]%\"#} |    |
|    | 0x08 ;'*$&"(<%!#)RAC | 0x14 ']!|^#[$"_\}&{% |    |
|    | 0x09 ES:($&';%#+"<*/ | 0x15 @)($!CARTS*!@$_ |    |
|    | 0x0A ;'*$&"(<%!#)/+: | 0x16 !#%${"'}&[]^|_\ |    |
|    | 0x0B |'_!}$\%["#^{&] | 0x17 ]"_#$&}^%[{|\'! |    |
|    | 0x0C #{!"^&\]'|}_[PI | 0x18 _![&#{$%\^'|}"] |    | # Notice how PITYS wrapped.
|    |_____________________________________________|    |
|                                                       |
\_______________________________________________________/
       \_______________________________________/

```

*These examples were manually crafted, so the distribution is not randomized, sorry.*

---

This is , lowest byte-count will be the accepted winner. I will bounty this after 3 days if no answers have been submitted for a total of 250 REP.

# Answer
> 6 votes
## JavaScript (ES8), ~~575~~ ~~568~~ 564 bytes

*Saved 3 bytes thanks to @Shaggy*

Takes input in currying syntax `(r)(a)`, where ***r*** is the number of remaining attempts and ***a*** is the array of passwords.

```
r=>a=>[...C=`!"#[]^$%&'*+;<{}=`].reduce((s,c)=>(x=s.split(c)).join(x.pop()),`  "%%__
 /;;# \\
[ "} $Welcome to ROBCO Industries (TM) Termlink'!Password Required#}'!Attempts Remaining:${" X".repeat(r).padEnd(9)};[$^1=^D<2=^E<3=^F<4*0<5*1<6*2<7*3<8*4<9*5<A*6<B*7<C*8='+"[|
|;;#'|
\\"{_/
}'\\&%/= ]]]]] | }' {%%%<='+ ^#}}}+|
[|*=0x1'   "{{{%___$+;#}} !^0x0]ZZZ[|}#;}"&{![+ `).replace(/Z/g,(c,i)=>a.join``[(i%58>>5?y++:x++)%L],x=(R=n=>Math.random()*n|0)(L=360),y=x+180,[...Array(L-(n=a.sort(_=>R(3)-1).length)*a[0].length)].map(_=>a[R(n)]+=(C+`>?@()/:\\_|`)[R(27)]))

```

*Syntax highlighter disabled on purpose. It has no clue what to do with that.*

### Demo

```
let f =

r=>a=>[...C=`!"#[]^$%&'*+;<{}=`].reduce((s,c)=>(x=s.split(c)).join(x.pop()),`  "%%__
 /;;# \\
[ "} $Welcome to ROBCO Industries (TM) Termlink'!Password Required#}'!Attempts Remaining:${" X".repeat(r).padEnd(9)};[$^1=^D<2=^E<3=^F<4*0<5*1<6*2<7*3<8*4<9*5<A*6<B*7<C*8='+"[|
|;;#'|
\\"{_/
}'\\&%/= ]]]]] | }' {%%%<='+ ^#}}}+|
[|*=0x1'   "{{{%___$+;#}} !^0x0]ZZZ[|}#;}"&{![+ `).replace(/Z/g,(c,i)=>a.join``[(i%58>>5?y++:x++)%L],x=(R=n=>Math.random()*n|0)(L=360),y=x+180,[...Array(L-(n=a.sort(_=>R(3)-1).length)*a[0].length)].map(_=>a[R(n)]+=(C+`>?@()/:\\_|`)[R(27)]))

O.innerText = f(3)(["SMART","ENACT","SWORE","PITYS","SMELL","CARTS","RACES"])
```

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

# Answer
> 4 votes
# Python 3, 585 bytes

```
from random import*
def f(l,n,r=range):
	u,c='_ ';a=[choice('!"#$%&\'()*+/:;<=>?@[\\]^_{|}')for i in c*360];L=len(l[0]);i={*r(360-len(l[0]))};p=lambda x:'0x%02X'%x+c+''.join(a[15*x:][:15])
	for q in l:s=choice([*i]);a[s:s+L]=q;i-={*r(s+~L,s+-~-~L)}
	return'''  %s
 /%s\\
|# %s #|
?%s?
? Welcome to ROBCO Industries (TM) Termlink   ?
? Password Required   ######?
? Attempts Remaining:%-25s?
?%s?
%%s?%s?
|%s|
\%s/
#   \%s/'''.replace('?','|#|').replace('#',c*4)%(u*53,c*53,u*45,c*45,' X'*n,c*45,u*45,c*55,u*55,u*39)%('|    | %s | %s |    |\n'*12)%sum([(p(x),p(x+12))for x in r(12)],())

```

Try it online!

-70 bytes thanks to Jonathan Allan
-9 bytes thanks to myself (finally!)
-72 bytes thanks to notjagan

# Answer
> 4 votes
# Perl 5, ~~588~~ 560 + 1 (-a) = ~~589~~ 561 bytes

*Cut 28 bytes with the suggestions Dom pointed out*

```
$,=$/;$_=" X"x pop@F;say"  "."_"x53," /".$"x53 ."\\",$q="|     ".'_'x45 ."     |",$e=($b="|    |").$"x45 .$b,"$b Welcome to ROBCO Industries (TM) Termlink   $b
$b Password Required".$"x27 .$b,"$b Attempts Remaining:$_".$"x(25-length).$b,$e;map{$s.=(grep/[^\w,.`-]|_/,map{chr}33..125)[rand 27]}1..360;($t=substr$s,$r=rand 360-($l=length),$l,$_)=~/[a-z]/i&&(substr$s,$r,$l,$t)&&push@F,$_ while$_=pop@F;@o=$s=~/.{15}/g;printf"$b 0x0%X %s | 0x%02X %s $b\n",$_,$o[$_-1],$_+12,$o[$_+11]for 1..12;say$b.'_'x45 .$b,$q=~y/_/ /r,$q=" \\"."_"x54 ."/",$"x6 .$q=~s/_{15}//r

```

Try it online!

*Previously:*

```
$,=$/;$_=" X"x pop@F;say"  "."_"x53," /".($"x53)."\\",$q="|     ".('_'x45)."     |",$e=($b="|    |").($"x45).$b,"$b Welcome to ROBCO Industries (TM) Termlink   $b
$b Password Required".($"x27).$b,"$b Attempts Remaining:$_".($"x(25-length)).$b,$e;$s=join'',map{(split//,'!"#$%&\'()*+/:;<=>?@[]^_{|}\\')[int rand 27]}1..360;while($_=pop@F){if(($t=substr$s,$r=rand 360-($l=length),$l,$_)=~/[a-z]/i){substr$s,$r,$l,$t;push@F,$_}}@o=$s=~/.{15}/g;printf"$b 0x0%X %s | 0x%02X %s $b\n",$_,$o[$_-1],$_+12,$o[$_+11]for 1..12;say$b.('_'x45).$b,$q=~y/_/ /r,$q=" \\".("_"x54)."/",($"x6).$q=~s/_{15}//r

```

Try it online!

Input is on one line, space separated: first the strings, then the number

**How?**

```
$,=$/;          # delimiter between fields is newline
$_=" X"x pop@F; # set number of attempts left
say             # output the header
"  "."_"x53,
" /".($"x53)."\\",
$q="|     ".('_'x45)."     |",
$e=($b="|    |").($"x45).$b,
"$b Welcome to ROBCO Industries (TM) Termlink   $b
$b Password Required".($"x27).$b,
"$b Attempts Remaining:$_".($"x(25-length)).$b,
$e;
$s=join'',map{(split//,'!"#$%&\'()*+/:;<=>?@[]^_{|}\\')[int rand 27]}1..360; # create random string long enough for entire screen
while($_=pop@F){  # for each given string
if(($t=substr$s,$r=rand 360-($l=length),$l,$_) # attempt to insert it
=~/[a-z]/i)                                    # but check if it overlaps another string
{substr$s,$r,$l,$t;                            # if it does, take it out
push@F,$_}}                                    # and put it back in line
@o=$s=~/.{15}/g;                               # split "memory dump" into chunks
printf"$b 0x0%X %s | 0x%02X %s $b\n",$_,$o[$_-1],$_+12,$o[$_+11]for 1..12; #output the grid
say                                            # output the footer
$b.('_'x45).$b,$q=~y/_/ /r,
$q=" \\".("_"x54)."/",
($"x6).$q=~s/_{15}//r

```

# Answer
> 4 votes
# SOGL V0.12, 225 bytes

```
R“EC"+w╗─║Z⁰2BΥø‘▓"▲╔⁸‘'²∙+"⅟Δλ≤LK⅟ΗΠ.JN║«⁸⅟‘▓+╬⁷"№D↓tι▲‛Q─Ρδν∙υ4Ρψ▲¦‽↑√Ε┐Ζ5↔‛⅟≤š▼¦⁾○ΔΡ%³‘ū91 tž85ž.ΖX Ο'⁹7žø]Xe@*c{leκψI1ž}_:@øŗ⁄c∑⁄≠}l{"T-)⅞↑°Χpjζ⅓īa0ε+Μ‛⁶ρ\=↔⅟¹‘ψ}¹K@Gŗ'¹nο²²Z+8«m«ο+I{@∑"0x0”Κ}¹6«n_'⁷1ž'⁵16«┐∙ž'⁸4 19∙ž89╬5

```

Try it Here!
Expects array input on the stack and the number input an an input, so `→"` is added in the online program for ease-of-use.

# Answer
> 2 votes
# JavaScript (ES8), 639 bytes

```
(w,n,r=i=>Math.random()*i|0,s=b=>{for(i=b[k];i;i--)[b[i-1],b[j]]=[b[j=r(i)],b[i-1]]},a=Array(360-w[k="length"]*--w[0][k]),m=[...a].map((j,i)=>~(j=d.slice(0,w[k]).indexOf(i))?w[j]:`!"#$%&'()*+/:;<=>?@[\\]^_{|}`[r(27)],s(w),s(d=[...a.keys()])).join``.match(/.{15}/g).map((v,i)=>"0x"+(i+1).toString(16).padStart(2,0)+" "+v))=>`  _53
 / 53\\
| 5_45 5|
${["","Welcome to ROBCO Industries (TM) Termlink","Password Required","Attempts Remaining:"+" X".repeat(n),"",...m.slice(0,12).map((x,i)=>x+" | "+m[i+12])].map(x=>"| 4| "+x.padEnd(43)+" | 4|").join`
`}
| 4|_45| 4|
| 55|
\\_55/
 7\\_39/`.replace(/[_ ]([1-9]+)/g,(m,n)=>m[0].repeat(n))

```

The hex labels are in lowercase; if uppercase was required, that would be an additional 14 bytes for `.toUpperCase()`.

## Test Snippet

Better viewed over on CodePen.

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