# Question
Title: Given an integer, compute its Levenshtein code
<sup>*Disclaimer: Levenshtein coding is completely unrelated to the Levenshtein edit distance metric.*</sup>

\<Insert long story about why Levenshtein codes need to be calculated here.\>

# The code

Levenshtein coding is a system of assigning binary codes to nonnegative integers that retains some weird property in probability which isn't relevant for this challenge. We will denote this code as *L*(*n*). Wikipedia describes this as a five-step process:

1. Initialize the step count variable *C* to 1.
2. Write the binary representation of the number without the leading `1` to the beginning of the code.
3. Let *M* be the number of bits written in step 2.
4. If *M* is not 0, increment *C*, repeat from step 2 with *M* as the new number.
5. Write *C* `1` bits and a `0` to the beginning of the code.

However, the code can also be described recursively:

1. If the number is 0, then its code is `0`.
2. Write the binary representation of the number without the leading `1` to the beginning of the code.
3. Let *M* be the number of bits written in step 2.
4. Write *L*(*M*) to the beginning of the code.
5. Write a `1` bit to the beginning of the code.

For those who prefer examples, here is the recursive process for *L*(87654321), with denoting concatenation:

# The challenge

Write a program or function that, given a number *n*, outputs the bitstring *L*(*n*) in any reasonable format (this includes returning a number with said bits). Standard loopholes are, as always, disallowed.

# Examples

Input: `5`

Output: `1110001`

Input: `30`

Output: `111100001110`

Input: `87654321`

Output: `111110000101001001110010111111110110001`

Input: `0`

Output: `0`

# Answer
# Jelly, ~~13~~ 11 bytes

```
Ḣ;LÑ$;
BÇṀ¡

```

Try it online! or verify all test cases.

### How it works

The submission consists of a pair of mutually recursive links.

```
BÇṀ¡    Main link. Argument: n

B       Convert n to binary.
   ¡    Execute...
 Ç        the helper link...
  Ṁ       m times, where m is the maximum of n's binary digits.

Ḣ;LÑ$;  Helper link. Argument: A (array of binary digits)

Ḣ       Head; remove and return the first element of A.
    $   Combine the two links to the left into a monadic chain.
  L       Yield the length (l) of A without its first element.
   Ñ      Call the main link with argument l.
 ;      Concatenate the results to both sides.
     ;  Append the tail of A.

```
> 2 votes

# Answer
# Haskell, 70 bytes

```
b 0=[]
b n=b(div n 2)++[mod n 2]
f 0=[0]
f n|1:t<-b n=1:f(length t)++t

```

Defines a function `f : Int -> [Int]`. For example, `f 5 == [1,1,1,0,0,0,1]`.
> 8 votes

# Answer
# Python, 49 bytes

```
f=lambda n:n and'1%s'%f(len(bin(n))-3)+bin(n)[3:]

```

Test it on Ideone.
> 5 votes

# Answer
# Mathematica, 61 bytes

```
f@0={0};f@n_:=Join[{1},f@Length@#,#]&@Rest@IntegerDigits[n,2]

```
> 4 votes

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

```
f=n=>(s=n.toString(2)).replace(1,_=>1+f(s.length-1))
```

```
<input type=number oninput=o.textContent=f(+this.value)><pre id=o>
```

Edit: Saved 2 bytes thanks to @Arnauld.
> 3 votes

# Answer
# Pyth, 12 bytes

```
L&bX1.Bbyslb

```

Demonstration

(The `y` at the end is to run the resulting function on the input)

Explanation:

```
L&bX1.Bbyslb
L               def y(b):
 &b             If b is 0, return 0. This is returned as an int, but will be cast
                to a string later.
          lb    Take the log of b
         s      Floor
        y       Call y recursively
   X1           Insert at position 1 into
     .Bb        Convert b to binary.

```
> 2 votes

# Answer
# SQF, 110

Recursive function:

```
f={params[["i",0],["l",[]]];if(i<1)exitWith{[0]};while{i>1}do{l=[i%2]+l;i=floor(i/2)};[1]+([count l]call f)+l}

```

Call as: `[NUMBER] call f`

**Note this doesn't actually work for 87654321 or other large numbers due to a bug in the ArmA engine. Although it will probably be fixed soon, and should work according to spec.**

**(This Ticket Here)**
> 1 votes

# Answer
# PHP, 116 114 bytes

```
<?$f=function($i)use(&$f){$b=decbin($i);return!$b?0:preg_replace('/^1/',1 .$f(~~log10($b)),$b);};echo$f($argv[1]);

```

Provide the number as the first argument.

## Update:

* Saved a byte by replacing `strlen($b)-1` with `~~log10($b)` (finally understood why everybody else was using logarithm) and another by concatenating differently.
> 0 votes

# Answer
# Ruby, 38 bytes

Very similar to Neil's JavaScript answer.

```
f=->n{("%b"%n).sub(/1\K/){f[$'.size]}}

```

See it on repl.it: https://repl.it/CnhQ
> 0 votes

# Answer
# Java 8 (Full Program), ~~257~~ 249 bytes

```
interface M{static void main(String[]a)throws Exception{int i=0,j;while((j=System.in.read())>10)i=i*10+j-48;System.out.print(L(i));}static String L(int i){if(i==0)return "0";String s=Integer.toString(i,2);return "1"+L(s.length()-1)+s.substring(1);}}

```

Readable Version w/ Explanation (It's mostly just recursion):

```
interface M {
    static void main(String[]a) throws Exception { // Using Exception is unadvised in real coding, but this is Code Gold
        int i = 0, j; // i stores the input; j is a temporary variable
        while ((j = System.in.read()) > 10) // Read the input to j and stop if it is a newline. Technically this stops for tabulators as well, but we shouldn't encounter any of those...
            i = i * 10 + j - 48; // Looping this step eventually reads the whole number in from System.in without using a reader (those take up a lot of bytes)
        System.out.print(L(i)); // Make a method call
    }

    static String L(int i) { // This gets the actual Levenshtein Code
        if (i == 0)
            return "0"; // The program gets a StackOverflowException without this part
        String s = Integer.toString(i, 2); // Shorter than toBinaryString
        return "1" + L(s.length() - 1) + s.substring(1); // Write in the first character (which is always a one), followed by the next L-code, followed by the rest of the binary string
    }
}

```

**EDIT 1**: *Saved 8 bytes*: The first character of the binary string is *always* 1; therefore, rather than using `s.charAt(0)`, a better option is simply `"1"`.
> 0 votes

# Answer
# Husk, 14 bytes

```
?ö:1Ṡ+o₀LtḋΘøI

```

Try it online!

Uses a simple recursive approach. (Dennis's double recursion is insane.)
> 0 votes

---
Tags: code-golf, sequence, binary
---


title: Find The Least Common Characters

text:
# Question
Title: Find The Least Common Characters
Given a string, find the 10 least common alpha-numeric characters within that string.

Output should be formatted with numbers left-padded with spaces so they look like this:

```
e:      1
t:     16
c:     42
b:    400
z:  50000
a: 100000

```

Use this to test your program: here

Output for test case:

```
j:  2
x:  3
q:  9
k: 32
v: 67
c: 73
w: 79
f: 93
b: 94
p: 96

```

Shortest code wins. You can submit a program or a function.

# Answer
> 0 votes
# K, 60

```
{(-:|/#:'f)$f:10#$(!x)[i]!r i:<r:. x:#:'=_x@&x in,/.Q`a`A`n}

```

# Answer
> 1 votes
## Mathematica, ~~102~~ 93:

v2:

```
  Grid[SortBy[
             Tally@StringCases[ToLowerCase@#,x_?LetterQ:>x<>":"],
              Last@# &],
      Alignment->Right]&@s

```

v1:

```
TableForm[
         SortBy[Tally@StringCases[ToLowerCase@#, x_?LetterQ :> x <> ":"],
                #[[2]] &],
         TableAlignments -> Right] &

```

# Answer
> 1 votes
### Bash, 72

Assuming no single-letter-named files in the current directory; input from stdin:

```
grep -io [a-z]|sort -f|uniq -ci|sort|head|sed -E 's/(.*)([a-z])/\2:\1/'

```

Works on Linux, but for some reason, my mac's grep seems to ignore the `-i` when used with `-o` (bug or undocumented gotcha?), but the following (78) works:

```
tr A-Z a-z|grep -o [a-z]|sort|uniq -c|sort|head|sed -E 's/(.*)([a-z])/\2:\1/'

```

If the output were allowed to be reversed, the sed part could be dropped to save 30 characters in each of the previous solutions.

# Answer
> 1 votes
# APL (Dyalog Unicode), ~~45~~ 36 bytes

```
10↑⌷⍨∘⊂∘⍋∘⌽⍨{⍺':',≢⍵}⌸∊⎕(∊⊆⊣)⍥⎕C⎕D,⎕A

```

Try it online!

A full program which accepts a string as input. tio link uses polyfills for  and `⎕C`.

Shortened and tested with help from Bubbler.

-12 bytes from Adám.

~~Doesn't work on tio due to some problem with `⎕C`.~~(Now works, thanks to Adám's help)

## Explanation

```
10↑⌷⍨∘⊂∘⍋∘⌽⍨{⍺':',≢⍵}⌸∊⎕(∊⊆⊣)⍥⎕C⎕D,⎕A
                             ⍥⎕C      lowercase the following:
                                ⎕D,⎕A string of the alphabet and digits
                       ⎕              and the input
                        (∊⊆⊣)         filter out nonalphanumerics
                      ∊               flatten the string
            {⍺':',≢⍵}⌸                create a frequency table for each letter key
   ⌷⍨∘⊂∘⍋∘⌽⍨                          sort the table based on the last row
10↑                                   take the first 10 elements

```

# Answer
> 1 votes
## Java ~~452~~ ~~444~~ ~~433~~ 430

```
import java.util.*;
interface L{
static void main(String[]a){
Map<Character,Integer>m=new HashMap<>();
for(char c:a[0].toLowerCase().toCharArray())if(96<c&&c<123) m.merge(c,1,(j,i)->j+i);
int l=String.valueOf(m.values().stream().reduce(0,Integer::max)).length();
m.entrySet().stream().sorted((e,f)->e.getValue()-f.getValue())
.forEachOrdered(e->System.out.println(e.getKey()+"-"+String.format("%"+l+"s",e.getValue())));
}}

```

My first contribution. I know Java will never win this kind of challenges but until now it is at least the shortest java response :)

First argument is used as input. If it contains spaces, it has to be quoted(")

Explained:

```
// there is not a lot you get for free, so import you will
import java.util.*;
interface L{
static void main(String[]a) {                 // java main entry point
    Map<Character,Integer> m=new HashMap<>(); // key=character, value=number of occurances in input text
    for(char c:                               // for each character in
        a[0]                                  // take first argument from command line
        .toLowerCase()                        // convert all characters to lowercase
        .toCharArray())                       // convert to array so we can loop over it

      if(96<c&&c<123)                      // accept only a-z
        m.merge(c, 1, (j,i)->j+i);            // fill map, increase corresponding value

    int l=String.valueOf(                     // l: to store length of counter
            m.values().stream()               // loop over counter values
              .reduce(0,Integer::max))        // find max value
            .length();                        // count number of digits of max value

    m.entrySet().stream()                     // loop over the counter map
    .sorted((e,f)->e.getValue()-f.getValue()) // sort the map by value ascending
    .forEachOrdered(                          // loop over the ordered result
        e->System.out.println(                // print for every entry
            e.getKey()                        // - the key
            +"-"
            +String.format("%"+l+"s",         // - format using l
                 e.getValue())));             //   the value
}}

```

452 -\> 444 : removed spaces

444 -\> 433 : class-\> interface, ~~public~~

433 -\> 430: 96\<c&c\<123 (thanks @ceilingcat)

# Answer
> 0 votes
### Python, ~~206~~ ~~199~~ 195 characters

```
import sys
t=sys.stdin.read().lower()
f={}
for c in t:
 if c.isalnum():f[c]=f.get(c,0)+1
s=lambda x:x[1]
h=sorted(f.items(),key=s)[:10]
for n in h:print n[0]+': '+`n[1]`.rjust(len(`max(h,s)[1]`))

```

Undoubtedly there is a lot of room for improvement, but here's my first attempt. Produces identical output for the test case provided.

206 -\> 199: Removed unnecessary newline and keyword argument

199 -\> 195: ~~iter~~items()

# Answer
> 0 votes
## Javascript, 271 characters

I'm not sure whether this breaks the rules of not (it doesn't justify the numbers in the output, but here's my solution anyway:

```
c=[];t=128;while(t--)c[t]=[0,t];i=prompt().toLowerCase();for(n=0;n<i.length;x=i.charCodeAt(n++),c[x][0]+=x>96&&x<123);for(n=i=0,c=c.sort(function(a,b){return(a[0]-b[0])});n<10;i++)if(c[i][0]>0){console.log(String.fromCharCode(c[i][1])+": "+("  "+c[i][0]).slice(-2));n++}

```

I'm pretty sure it can be simplified (I won't win with this character count :P), but now I can't find anything.

Okay, so I completely forgot that the padding was actually a requirement :O Corrected that and fixed a bug. (250 -\> 271)

# Answer
> 0 votes
## Python, 144

```
import os
s=os.read(0,10000).lower()
n=s.count
a=sorted(filter(str.isalnum,set(s)),key=n)[:10]
for c in a:print c+': %%%ii'%len(`n(a[-1])`)%n(c)

```

# Answer
> 0 votes
## Haskell (229)

```
import Char
import Data.List
z=filter
t=show
l=length
k x=[(l$z(==m)x,m)|m<-x]
s z=[b:':':take(1+(maximum$map(l.t.fst)z)-l(t a))(repeat ' ')++t a++"\n"|(a,b)<-z]
main=interact$concat.s.take 10.sort.nub.k.map toLower.z isAlphaNum

```

# Answer
> 0 votes
## Perl, 86 chars

given string is in `$_`

```
s/[a-z]/$h{lc($&)}++/eig;printf"$_:%9d$/",$h{$_}for(sort{$h{$a}<=>$h{$b}}keys%h)[0..9]

```

# Answer
> 0 votes
# JavaScript 1.8 (ES6) 186

```
F=s=>(
  s.toLowerCase(n={}).replace(/[a-z0-9]/g,c=>n[c]=-~n[c]),
  s=Object.keys(n).sort((a,b)=>n[a]-n[b]),
  s.slice(0,10).map(x=>x+': '+('      '+n[x]).slice(-(n[s[9]]+'').length))
  .join('\n')
)

```

# Answer
> 0 votes
# Jelly, 22 bytes

```
Øa;ØD
ŒlċⱮ¢¢żPƇ0ị$Þḣ⁵G

```

Try it online!

Doesn't output with a `:` on each row, but given that isn't explicitly specified in the spec (compared to the left padding), I assumed this was OK. 26 bytes to require separating by `:`.

## How it works

```
Øa;ØD - Helper link. Yield a constant value "abc...xyz012...789"
Øa    - Yield "abc...xyz"
   ØD - Yield "0123456789"
  ;   - Concatenate

ŒlċⱮ¢¢żPƇ0ị$Þḣ⁵G - Main link. Takes a string S on the left
Œl               - Convert S to lowercase
    ¢            - Yield "abc...789"
   Ɱ             - For each character:
  ċ              -   Count occurrences in S
     ¢           - Yield "abc...789"
      ż          - Zip with occurrences
        Ƈ        - Keep characters where:
       P         -   There is at least 1 occurrence in S
           $Þ    - Sort by:
         0ị      -   Number of occurrences
             ḣ⁵  - Take the first 10
               G - Convert into a grid format

```

# Answer
> 0 votes
# Japt v2.0a0 `-R`, 28 bytes

Yet another old challenge hindered by an unnecessarily cumbersome output format.

```
r\W v ü ñÊ®Î¬pZÊÃ¯A yù ®q":

```

Try it (Note: I'm passing the input in the header here so it can be enclosed in backticks, allowing for the inclusion of both single & double quotes. Doing so, however, makes no difference to the code or byte count.)

```
r\W v ü ñÊ®Î¬pZÊÃ¯A yù ®q":      :Implicit input of string
r                                :Remove
 \W                              :  /[^A-Z0-9]/gi
    v                            :Lowercase
      ü                          :Group & sort
        ñ                        :Sort by
         Ê                       :  Length
          ®                      :Map each Z
           Î                     :  First character
            ¬                    :  Split
             p                   :  Push
              ZÊ                 :    Length of Z
                Ã                :End map
                 ¯               :Slice to
                  A              :  10th element
                    y            :Transpose
                     ù           :Left pad each sub array with spaces to the length of the longest and implicitly transpose back
                       ®         :Map
                        q":      :  Join with ": "
                                 :Implicit output joined with newlines

```

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


title: Remove digits, retaining greater number

text:
# Question
Title: Remove digits, retaining greater number
# Introduction

This challenge consists in finding the greatest number removing *y* digits from the original number *n* which has *x* digits.

Assuming `y=2 n=5263 x=4`, the possible numbers removing *y=2* digits are:

```
[52, 56, 53, 26, 23, 63]

```

So, the greatest number is `63` which must be the output for this example.

---

Another logic would be: *for each y, search from left to right the digit which right next digit is greater, then remove it, else when no match, remove the last y-digits*.

Using `y=3 n=76751432 x=8` to explain:

```
y=3
76751432
-^------ remove 6 because right next 7 is greater

y=2
7751432
---^--- remove 1 because right next 4 is greater

y=1
775432
-----^ the search failed, then remove last y digits

result = 77543

```

Both methods explained above works.. of course, you can use another method too :)

# Challenge

The number *n* won't have more than 8 digits, and *y* will always be greater than zero and lower than *x*.

To avoid strict input format, you can use the values: `y n x` the way you prefer: as parameters in function, raw input, or any other valid way. Just don't forget to say how you did that in your answer.

The output should be the result number.

This is , the shortest answer in bytes wins.

# Example Input and Output

### Again: you do not need to be too strict :)

```
4 1789823 7 -> 983
1 54132 5   -> 5432
3 69314 5   -> 94
2 51794 5   -> 794

```

# Edit

I changed the input order to reflect the fact that some of you may not need the *x* value to solve the problem. *x* is now an optional value.

# Answer
## A-Ray, ~~9~~ 7 bytes

My new language! According to meta, this is allowed, but if this is not accepted, then I will remove it.

```
pM:i-II

```

Explanation:

```
  :i-II       Gets all permutations possible for the given number converted to an array,
                      with the length of y-x, which is the -II part
 M            Gets the maximum of the result above
p             Prints the resulting array above, with no separators

```

Example input (number, x, y):

```
1736413 7 4

```

Output:

```
764

```

You can test this with the .jar file given in the github link.
> 3 votes

# Answer
# MATL, 10 bytes

```
-jowXncUX>

```

This uses version (9.2.1) of the language/compiler, which is earlier than this challenge.

It takes three inputs from stdin in this order: string length, number of removed characters, string.

### Example

```
>> matl
 > -jowXncUX>
 >
> 7
> 4
> 1789823
983

```

*EDIT*: **Try it online!** (the code in the link has `XN` instead of `Xn` to conform to changes in the language after this challenge; also, `o` is not needed anymore)

### Explanation

(This still costs 2 bytes more than it should due to Octave's and Matlab's `nchoosek` function behaving differently. Fixed in the next release of the compiler.)

```
-        % implicitly input two numbers, and subtract them
jo       % input string, and convert to ASCII codes
wXn      % swap inputs. Generate all combinations, each in a row
c        % convert to char array
U        % convert each row to a number
X>       % get maximum. Implicitly display

```

---

## Answer to original challenge (stricter input requirements): 16 bytes

```
jYbZ)b-wowXncUX>

```

Uses current version (9.2.1) of the language/compiler.

### Example

```
>> matl jYbZ)b-wowXncUX>
> 4 1789823 7
983

```

### Explanation

(This should have been 4 bytes less, but I need that `wow...c` because Octave's `nchoosek` function, unlike Matlab's, doesn't work with character input. Will be fixed for next release of the compiler.)

```
j              % input string
YbZ)           % split at spaces into strings
b-             % subtract first and third (1-digit) strings
wow            % convert middle string into ASCII codes
Xn             % get all combinations, each in a row
c              % convert to char array
U              % convert each row to a number
X>             % get maximum. Implicitly display

```
> 4 votes

# Answer
# Pyth - ~~11~~ ~~9~~ 8 bytes

```
eS.cz-QE

```

Test Suite.
> 3 votes

# Answer
# Julia, ~~128~~ 95 bytes

```
f(y,n,x)=maximum(i->parse(join(i)),filter(k->endof(k)==x-y,reduce(vcat,partitions(["$n"...]))))

```

This is a function that accepts the three values as parameters and returns an integer.

Ungolfed:

```
function f{T<:Integer}(y::T, n::T, x::T)
    # Get all ordered partitions of the digits of n
    p = reduce(vcat, partitions(["$n"...]))

    # Filter to groups of size x-y
    g = filter(k -> endof(k) == x - y, p)

    # Get the maximum resulting number
    return maximum(i -> parse(join(i)), g)
end

```
> 1 votes

# Answer
# Japt, 19 bytes

```
Vs ¬àW-U m¬mn n!- g

```

Try it online!

### How it works

```
        // Implicit: U = y, V = n, W = x
Vs ¬    // Convert V into a string, then split into an array of chars.
àW-U    // Generate all combinations of length W-U.
m¬mn    // Join each pair back into a string, then convert each string to a number.
n!-     // Sort by backwards subtraction (b-a instead of a-b; highest move to the front).
g       // Get the first item in this list.
        // Implicit: output last expression

```
> 1 votes

# Answer
# Brachylog, 30 bytes

```
,{,[N:Y].hs?lL,Nl-Y=L}?:1forh.

```

Since OP has relaxed the constraints on IO, this expects `[Number, NumberOfDigitsRemoved]` as input and returns the answer as output, e.g. `brachylog_main([1789823,4], Z).`.

### Explanation

```
,{                   }?:1f     § Declare sub-predicate 1 and find all inputs which satisfy
                               § this sub-predicate with output = Input of the main predicate
                               § (i.e. [Number, Number of digits to remove])

                               § -- Sub-predicate 1 --
  ,[N:Y].                      § Output = [N, Y]
         hs?                   § Input = a subset of N
            lL,Nl-Y=L          § Length of Input = Length of N - Y

                          orh. § Order the list of answers, reverse it an return the first
                               § element (i.e. the biggest number of the list)

```
> 1 votes

# Answer
## Python 3, 69 bytes

This defines an anonymous function accepting all three arguments. Taking full advantage of the rule that "you can use the values: `y n x` the way you prefer", I have chosen to accept `y` and `x` as integers and `n` as a string. The return value is a string.

```
from itertools import*
lambda y,n,x:''.join(max(combinations(n,x-y)))

```

Just in case anyone feels that this is stretching the rules too far, this version takes all inputs as integers and is 74 bytes.

```
from itertools import*
lambda y,n,x:''.join(max(combinations(str(n),x-y)))

```

And just for kicks, I also wrote a two-argument version, taking `y` and `n` from the command line and printing the result to `STDOUT`. It's 92 bytes.

```
import sys,itertools as i
_,y,n=sys.argv
print(*max(i.combinations(n,len(n)-int(y))),sep='')

```
> 1 votes

# Answer
## ES6, 70 bytes

```
r=(y,n)=>y?r(y-1,Math.max(...`${n}`.replace(/./g," $`$'").split` `)):n

```

Returns a numeric result unless `y` is falsy and `n` is a string. I've convinced myself that doing the recursion the wrong way around still works (my solution isn't applicable to doing the correct recursion).

Also my first code golf where I use all three quote signs (although not all as quotes), which prevented me from trivially calculating the length.
> 1 votes

# Answer
## Haskell, 64 bytes

```
import Data.List
y#x=maximum.filter((==x-y).length).subsequences

```

Usage example: `(4#7)"1789823"` -\> `"983"`.

The original number `n` is takes as a string. (Not sure if I'm overstressing the "no strict input format" rule, but string input was required(!) in the first version).

How it works: make a list of all subsequences of `n`, keep those with length `x-y` and pick the maximum.
> 1 votes

# Answer
# Ruby, 40 bytes

```
->y,n,x{n.chars.combination(x-y).max*''}

```

This is an anonymous function that takes `y` and `x` as integers and `n` as a string, and returns a string. You may call it for instance like this

```
->y,n,x{n.chars.combination(x-y).max*''}[2,"5263",4]

```

and it will return `"63"`.
> 1 votes

# Answer
# MATLAB 40 bytes

```
@(n,y)max(str2num(nchoosek(n,nnz(n)-y)))

```

Test:

```
ans('76751432',3)
ans = 77543

```
> 1 votes

# Answer
# Pyth, 45 bytes

```
=cz)Fk.P@z1-l@z1v@z0I:@z1j".*"k1I>vkZ=Zvk)))Z

```

try it here
> 0 votes

# Answer
# JavaScript (ES6), 78

A recursive function with 2 arguments y and d. `y` can be numeric or string, `d` must be a string.

```
r=(y,d)=>y?Math.max(...[...d].map((x,i)=>r(y-1,d.slice(0,i)+d.slice(i+1)))):+d

```

Before the challenge changed it was 107 - ... with all input/output oddities ...

```
x=>(r=(n,d)=>n?Math.max(...[...d].map((x,i)=> r(n-1,d.slice(0,i)+d.slice(i+1)))):+d)(...x.match(/\d+/g))+'\n'

```

**Test**

```
r=(y,d)=>y?Math.max(...[...d].map((x,i)=>r(y-1,d.slice(0,i)+d.slice(i+1)))):+d

function test() {
  [a,b]=I.value.match(/\d+/g)
  O.textContent=r(a,b)
}

test()
```

```
y,n: <input id=I value='4 1789823' oninput="test()">
<pre id=O></pre>
```
> 0 votes

# Answer
# Japt `-h`, 6 bytes

```
àVnW)ñ

```

Try it

```
àVnW)ñ     :Implicit input of string U=n and integers V=y & W=x
à          :Combinations of U of length
 VnW       :  V subtracted from W
    )      :End combinations
     ñ     :Sort
           :Implicit output of last element

```
> 0 votes

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


title: What can you see on a hexagonal spiral?

text:
# Question
Title: What can you see on a hexagonal spiral?
This challenge will have you computing OEIS sequence A300154.

> Consider a spiral on an infinite hexagonal grid. a(n) is the number of cells in the part of the spiral from 1st to n-th cell that are on the same \[row\*\] or diagonal (in any of three directions) as the n-th cell along the spiral, including that cell itself.

(\*I have very slightly changed the definition to match the orientation of the GIF below.)

The sequence begins

```
1, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 7, 6, 7, 7, 8, 7, 8, 9, 8, 9, 8, 9, 10, 9, 10, 11, 9, 10, 11, 10, 11, 12, 10, 11, 12, 13, 11, 12, 13, 11, 12, 13, 14, 12, 13, 14, 15, 12, 13, 14, 15, 13, 14, 15, 16, 13, 14, 15, 16, 17, 14

```

# Example

Below is an example of the first fifteen terms of the sequence. On a hexagonal tiling, go in a spiral, and after each step, count the number of cells that you can "see" from that position, including the cell itself.

# Challenge

The challenge is simple, write a program that takes a positive integer `n` and computes \\$A300154(n)\\$. Again, this is so shortest code wins.

*(Note: I will also award an additional bounty of 200 rep to the first person who completes this challenge in Hexagony.)*

# Answer
# Jelly, 14 bytes

A monadic link taking an integer as input; computes the first `n` terms of the sequence.

```
÷3Ḟ,ĊƊḶ+
ŻÇ€Fḣ

```

Try it online! This is a port of Bubbler's answer, so be sure to upvote him as well!

**How it works:**

```
ŻÇ€Fḣ      Main link: monad taking integer n as input
Ż          Create the range [0, ..., n]
 Ç€        Map the auxiliar link over the range.
   F       Flatten...
    ḣ      and take the first n elements of that.

÷3Ḟ,ĊƊḶ+   Auxiliar link: monad taking integer k as input
÷3         Divide by 3.
   , Ɗ     Create a pair (a, b)
  Ḟ Ċ      with the floor and ceiling of the division.
      Ḷ    Finally create the ranges [0, ..., a-1] and [0, ..., b-1]
       +   and add k to each number in each range.

```
> 1 votes

# Answer
# JavaScript (ES6),  ~~178 169~~  168 bytes

Returns the \\$n\\$ first terms as an array.

```
n=>(X=[1],Y=[L=1],d=5,j=x=y=0,g=a=>--n?g([...a,(X[x+=~-'210012'[d%=6]]=-~X[x])+(Y[y+=~-'1221'[j?d:d++]]=-~Y[y])+(Z[x+y]=-~Z[x+y])-2],++j%L?0:(j%=L*6)?d++:L++):a)(Z=[1])

```

Try it online!

### How?

This is a rather naive approach that actually computes the spiral with cube coordinates \\$(x,y,x+y)\\$ and keeps track of the number of cells on each row \\$Z\[x+y\]\\$, each diagonal \\$Y\[y\]\\$ and each anti-diagonal \\$X\[x\]\\$.

### Commented

```
n => (                            // n = input
  X = [1], Y = [L = 1],           // X[] = anti-diagonals, Y[] = diagonals, L = layer
  d = 5,                          // d = direction in [0..5]
  j =                             // j = cell index in the current layer
  x = y = 0,                      // (x, y) = coordinates
  g = a =>                        // g = main recursive function taking the output a[]
    --n ?                         // decrement n; if we haven't computed enough terms:
      g(                          //   recursive call:
        [ ...a,                   //     append the previous terms
          ( X[x +=                //     update x and increment X[x]
              ~-'210012'[d %= 6]  //       pick dx according to d
            ] = -~X[x]            //
          ) +                     //
          ( Y[y +=                //     update y and increment Y[y]
              ~-'1221'[j ? d      //       pick dy according to d
                         : d++]   //       increment d afterwards if j = 0
            ] = -~Y[y]            //       (i.e. this is the 1st cell of the layer)
          ) +                     //
          (Z[x + y] = -~Z[x + y]) //     increment Z[x + y]
          - 2                     //     subtract 2 from X[x] + Y[y] + Z[z] because
        ],                        //     the current cell is counted three times
        ++j                       //     increment j
        % L ?                     //     if it's not the last cell of this side:
          0                       //       do nothing
        :                         //     else:
          (j %= L * 6) ?          //       if it's not the last cell of the layer:
            d++                   //         increment d
          :                       //       else:
            L++                   //         increment L
      )                           //   end of recursive call
    :                             // else:
      a                           //   we're done: return a[]
)(Z = [1])                        // initial call to g with a[] = Z[] = [1]

```
> 10 votes

# Answer
# APL (Dyalog Unicode), 23 bytesSBCS

```
⊢↑∘(∊⊢+∘(⍳¨⌊,⌈)¨÷∘3)⍳,⊢

```

Try it online!

A tacit function that returns the first `n` terms of the sequence.

### Observation

```
n m | f(n,m): m consecutive integers starting at n
---------------
1 0 |
1 1 | 1
2 0 |
2 1 | 2
3 1 | 3
3 1 | 3
4 1 | 4
4 2 | 4 5
5 1 | 5
5 2 | 5 6
6 2 | 6 7
6 2 | 6 7
7 2 | 7 8
7 3 | 7 8 9
8 2 | 8 9
8 3 | 8 9 10
9 3 | 9 10 11
9 3 | 9 10 11
---------------
Flattened: 1 2 3 3 4 4 5 5 5 6 6 7 6 7 7 8 7 8 9 8 9 8 9 10 9 10 11 9 10 11

```

Though I don't have a rigorous argument that the pattern is mathematically correct, the test cases show that the first 3000 terms agree with Arnauld's JS answer.

### How it works: the code

Uses `⎕IO←0`, so `⍳ n` gives `0 1 2 .. n-1`.

```
⊢↑∘(∊⊢+∘(⍳¨⌊,⌈)¨÷∘3)⍳,⊢  ⍝ Input: n
                    ⍳,⊢  ⍝ Generate 0..n
   (               )     ⍝ For each number k...
                ÷∘3      ⍝ Divide k by 3
        (     )¨  ⍝ For each item of above,
           ⌊,⌈    ⍝ Collect its floor and ceil;
                  ⍝ (0 0)(0 1)(0 1)(1 1)(1 2)(1 2)(2 2)...
         ⍳¨       ⍝ For each number i, generate 0..i-1
                  ⍝ (2 3) -> ((0 1)(0 1 2))
     ⊢+∘  ⍝ Add k to each pair of ranges (results of f(n,m))
    ∊     ⍝ Enlist; collect all numbers into a vector
⊢↑∘       ⍝ Take first n numbers

```
> 4 votes

# Answer
# MATL, 48 bytes

```
0i:"J_Q@q:gJJq1_J_tQ5$h@Y"&h]YsG:)&Zjyy+vt0Z)=as

```

**Try it online!** Or **verify all test cases**.

### Explanation

This uses coordinate axes 60 degrees apart, so that cell coordinates are integer values. In addition, coordinates `(r,s)` are stored as a complex number `r+j*s`, where `j` is the imaginary unit.

The code first creates `n` layers of the spiral, which is enough (for most inputs, it is much more than enough). This is done by a loop that adds one layer in each iteration. The first cell is at the origin. For each new layer, the displacements from one cell to the next are defined (in the chosen system of complex coordinates): a displacement "outward" (to create room for the layer) and then several displacements "around" to complete a turn. Once all displacements for all layers have been specified, a cumulative sum produces the cell positions.

To see what is meant by "layer" and how the spiral is built, you can **graphically depict the spiral** with `n` layers. Note that the spiral is deformed because the plot uses orthogonal axes (real and imaginary), instead of axes with 60-degree separation.

Once the spiral has been created, the first `n` cells are kept. From these, the last cell is the reference. To detect which cells are in the same row/diagonal as the reference cell, the condition is that the candidate cell should have either the same value of the *first* coordinate as the reference cell, or the same value of the *second* coordinate, or the same value of the *sum* of coordinates.

```
0        % Push 0. This is the initial cell
i:"      % Input n. For each k in [1 2 ... n]
  J_Q    %   Push 1-j
  @q:g   %   Push [1 1 1 ... 1] (k-1 entries)
  J      %   Push j
  Jq     %   Push -1+j
  1_     %   Push -1
  J_     %   Push -j
  tQ     %   Duplicate, add 1: pushes 1-j
  5$h    %   Concatenate 5 elements into a row vector: [j -1+j -1 -j 1-j]
  @Y"    %   Repeat each entry k times
  &h     %   Concatenate everything into a row vector
]        % End
Ys       % Cumulative sum
G:)      % Keep first n entries. Gives a row vector of size n
&Zj      % Push real and imaginary parts. Gives two row vectors
yy+      % Duplicate top two elements in the stack, add
v        % Concatenate the three row vectors into a 3-row matrix
t        % Duplicate
0Z)      % Keep last column
=        % Equal? Element-wise with broadcast. Gives a true-false matrix
a        % Any: true for columns that contain at least one true entry
s        % Sum. Implicit display

```
> 3 votes

# Answer
# Husk, 15 bytes

```
↑ṁ₁N
†+¹ṁŀSe→÷3

```

Try it online!
> 1 votes

---
Tags: code-golf, sequence, combinatorics, hexagonal-grid
---


title: New Order #2: Turn My Way

text:
# Question
Title: New Order #2: Turn My Way
## Introduction *(may be ignored)*

Putting all positive numbers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive numbers. This is the second challenge in this series. The first challenge can be found here.

In this challenge, we use Gray codes to rearrage the natural numbers. A Gray code, or "reflected binary code" is a binary encoding in such a way that two successive values differ in only one bit. A practical application of this encoding is to use it in rotary encoders, hence my reference to *"Turn My Way"*.

Note that this encoding leaves some degree of freedom. For example, following binary 1100, there are four possible following codes: 1101, 1110, 1000 and 0100. This is why I will define \\$a(n)\\$ as the smallest, not previously used value that differs only one character in binary encoding. This sequence corresponds with A163252.

Since this is a "pure sequence" challenge, the task is to output \\$a(n)\\$ for a given \\$n\\$ as input, where \\$a(n)\\$ is A163252.

## Task

Given an integer input \\$n\\$, output \\$a(n)\\$ in integer format (*not* in binary format).

\\$a(n)\\$ is defined as the least positive integer not occurring earlier in the sequence such that \\$a(n-1)\\$ and \\$a(n)\\$ differ in only one bit when written in binary.

*Note: 1-based indexing is assumed here; you may use 0-based indexing, so \\$a(0) = 1; a(1) = 3\\$, etc. Please mention this in your answer if you choose to use this.*

## Test cases

```
Input | Output
--------------
1     | 1
5     | 4
20    | 18
50    | 48
123   | 121
1234  | 1333
3000  | 3030
9999  | 9997

```

## Rules

* Input and output are integers (your program should at least support input and output in the range of 1 up to 32767)
* Invalid input (0, floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour. In A163252, \\$a(0)\\$ is defined as 0. For this challenge, we will ignore this.
* Default I/O rules apply.
* Default loopholes are forbidden.
* This is , so the shortest answers in bytes wins

## Final note

See the following related (but not equal) PP&CG questions:

# Answer
# Stax, ~~19~~ 17 bytes

```
êÑ{╚α8è╙mc┼σ▀»É▲ü

```

Run and debug it

It stops working at some point after the specified domain due to the hardcoded bit index iteration. (32767)

Unpacked, ungolfed, and commented, it looks like this.

```
z0,         push an empty array, literal zero, and the input, in that order
             - the zero represents the last calculated value in the sequence
             - the array contains all the previous ones
D           repeat the rest of the program n times (from input)
  +         append the last calculated value to the array
  17r       [0 .. 16] (these are the bit indices necessary to cover the input range)
  {|2nH|^m  calculate candidate values; previous value with each of these bits toggled
  n-        remove all values previously calculated
  |m        keep the minimum candidate remaining

```

Run this one
> 2 votes

# Answer
# JavaScript (ES6), 65 bytes

1-indexed.

```
n=>{for(o=p=[k=1];o[k]|~-(i=p^k)&i?k++:k=o[p=k]=!!n--;);return p}

```

Try it online!

### Commented

```
n => {                  // n = index of requested term
  for(                  // for loop:
    o =                 //   o = storage object for the terms of the sequence
    p =                 //   p = last term found in the sequence
      [k = 1];          //   k = current term
    o[k] |              //   if k was already encountered
    ~-(i = p ^ k) & i ? //   or (p XOR k) has more than 1 bit set:
      k++               //     increment k
    :                   //   else:
      k = o[p = k]      //     set o[k], set p to k
        = !!n--;        //     stop if n is equal to 0 or set k to 1; decrement n
  );                    // end of for()
  return p              // return p
}                       // end

```
> 4 votes

# Answer
# Jelly, ~~26~~ 20 bytes

```
ṀBLŻ2*^1ị$ḟ⁸Ṃ;
0Ç⁸¡Ḣ

```

Try it online!

A full program that takes n as the single argument. Works for all test cases. Also note that, although not required, it handles n=0.

### Explanation

Helper link: find next term and prepend

```
Ṁ              | maximum of list so far
 B             | convert to binary
  L            | number of binary digits
   Ż           | 0..above number
    2*         | 2 to the power of each of the above
      ^        | exclusive or with...
       1ị$     | ... the most recent term in the list so far
          ḟ⁸   | filter out anything used already
            Ṃ  | find the minimum
             ; | prepend to existing list

```

Main link

```
0              | start with zero
 Ç             | call the above link
  ⁸¡           | and repeat n times
    Ḣ          | take the last term added

```
> 4 votes

# Answer
# Java (JDK), ~~142~~ ~~138~~ ~~124~~ ~~123~~ ~~132~~ ~~130~~ 98 bytes

```
n->{int s[]=new int[9*n],j,k=0;for(;n-->0;s[k=j]++)for(j=0;s[++j]>0|n.bitCount(j^k)>1;);return k;}

```

Try it online!
> 3 votes

# Answer
# Python 2, 81 bytes

1-based indexing

```
l=[0];p=0
exec"n=0\nwhile(p^n)&(p^n)-1or n in l:n+=1\np=n;l+=p,;"*input()
print p

```

Try it online!

---

# Python 2, 79 bytes

This takes a lot of time (9999 wasn't finished after running locally for 7 minutes)

```
l={0};p=0;n=input()
exec'p=min({p^2**k for k in range(n)}-l);l|={p};'*n
print p

```

Try it online!
> 2 votes

# Answer
# Husk, 21 bytes

```
!¡λḟ¤ȯεΣz≠ȯ↔Θḋ→¹`-N)ø

```

Try it online! `¡§ḟ¤ȯεΣz≠ȯ↔Θḋ→`-Nø` would work if not for type-inferencing issues.
> 2 votes

# Answer
# Wolfram Language (Mathematica), 74 bytes

```
Last@Nest[#~Join~{Min[BitXor[Last@#,2^Range[0,20]]~Complement~#]}&,{0},#]&

```

Try it online!
> 1 votes

# Answer
# APL (Dyalog Extended), 46 bytes

```
{⍵⌷2∘{(~⍺∊⍵)∧1=≢⍸≠⌿↑⌽∘⊤¨⍺,⊃⌽⍵:⍵,⍺⋄⍵∇⍨⍺+1}⍣⍵⊢1}

```

Try it online!
> 1 votes

# Answer
# Charcoal, 65 bytes

```
≔⁰θＦＮ«⊞υθ≔¹ηＷ¬‹θ⊗η≦⊗ηＷ∧›η¹∨¬＆θη№υ⁻θη≧÷²ηＷ№υ⁻｜θη＆θη≦⊗η≔⁻｜θη＆θηθ»Ｉθ

```

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

```
≔⁰θ

```

Initialise the result to 0.

```
ＦＮ«

```

Loop `n` times.

```
⊞υθ

```

Save the previous result so that we don't use it again.

```
≔¹ηＷ¬‹θ⊗η≦⊗η

```

Find the highest bit in the previous result.

```
Ｗ∧›η¹∨¬＆θη№υ⁻θη≧÷²η

```

While that bit is greater than 1, if the bit is set in the previous result, try subtracting that bit to see if the result is an unseen result. This ensures that the potential results are tried in ascending order of value.

```
Ｗ№υ⁻｜θη＆θη≦⊗η

```

Now try XORing that bit with the previous result, doubling the bit until an unseen result is found. This handles the cases when a bit needs to be set, again in ascending order of value, but also the case when the least significant bit needs to be toggled, which the previous loop doesn't bother to test (because it's golfier to test for that here). If the previous loop found an unseen result then this loop never runs; if it didn't then this loop will uselessly retest those results.

```
≔⁻｜θη＆θηθ

```

Update the result by actually XORing the bit with it.

```
»Ｉθ

```

Output the final result at the end of the loop.
> 1 votes

# Answer
# 05AB1E, ~~21~~ ~~20~~ 18 bytes

```
ÎFˆ∞.Δ¯θy^bSO¯yå_*

```

Pretty inefficient, so the larger the input, the longer it takes to get the result. Does work for input `0` as well, though.

Try it online or verify the first \\$n\\$ terms.

**Explanation:**

```
Î                # Push 0 and the input
 F               # Loop the input amount of times:
  ˆ              #  Pop the current number and add it to the global_array
  ∞.Δ            #  Inner loop starting at 1 to find the first number which is truthy for:
     ¯θy^        #   XOR the last number of the global_array with the loop-number `y`
         b       #   Convert it to binary
          SO     #   Sum it's binary digits
     ¯yå_        #   Check if the loop-number `y` is NOT in the global_array yet
            *    #   Multiply both (only if this is 1 (truthy), the inner loop will stop)
                 # (after the loops, output the top of the stack implicitly)

```
> 1 votes

# Answer
# Haskell, 101 bytes

```
import Data.Bits
(u!n)0=n
(u!n)m|q<-minimum[x|r<-[0..62],x<-[xor(2^r)n],notElem x u]=(n:u)!q$m-1
[]!0

```

Try it online!

It seems a shame to incur an import just for `xor`, but I haven't found a good work-around yet. I also wonder if there's a better way to express the loop.
> 1 votes

# Answer
# , 90 bytes

```
function(n){A=1
while(sum(A|1)<n)A=c(min((x=bitwXor(A[1],2^(0:30)))[x>0&!x%in%A]),A)
A[1]}

```

Try it online!
> 0 votes

---
Tags: code-golf, sequence
---


title: New Order #3: 5 8 6

text:
# Question
Title: New Order #3: 5 8 6
## Introduction *(may be ignored)*

Putting all positive numbers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive numbers. This is the third challenge in this series (links to the first and second challenges).

In this challenge, we will arrange the natural numbers in rows of increasing length in such a way that the sum of each row is a prime. What I find really amazing about this, is that every natural number has a place in this arrangement. No numbers are skipped!

This visualisation of this arrangement looks like this:

```
row             numbers             sum
1                  1                  1
2                2   3                5
3              4   5   8             17
4            6   7   9  15           37
5          10 11  12  13  21         67
6        14  16 17  18  19  23      107
etc.

```

We can read the elements from the rows in this triangle. The first 20 elements are: 1, 2, 3, 4, ***5, 8, 6***, 7, 9, 15, 10, 11, 12, 13, 21, 14, 16, 17, 18, 19 (*yes, there is a New Order song hidden in this sequence*).

Since this is a "pure sequence" challenge, the task is to output \\$a(n)\\$ for a given \\$n\\$ as input, where \\$a(n)\\$ is A162371.

## Task

Given an integer input \\$n\\$, output \\$a(n)\\$ in integer format.

\\$a(n)\\$ is defined as the \\$n\\$th element of the lexicographically earliest permutation of the natural numbers such that, when seen as a triangle read by rows, for n\>1 the sums of rows are prime numbers. Since the first lexicographical permutation of natural numbers starts with 1, \\$a(1)\\$ is 1. Note that by this definition \\$a(1) = 1\\$ and \\$a(1)\\$ is ***not*** required to be prime. This is OEIS sequence A162371.

*Note: 1-based indexing is assumed here; you may use 0-based indexing, so \\$a(0) = 1; a(1) = 2\\$, etc. Please mention this in your answer if you choose to use this.*

## Test cases

```
Input | Output
---------------
1     |  1
5     |  5
20    |  19
50    |  50
78    |  87
123   |  123
1234  |  1233
3000  |  3000
9999  |  9999
29890 |  29913

```

## Rules

* Input and output are integers (your program should at least support input and output in the range of 1 up to 32767)
* Invalid input (0, floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour.
* Default I/O rules apply.
* Default loopholes are forbidden.
* This is , so the shortest answers in bytes wins

# Answer
# Husk, 22 bytes

```
!¡§ḟ(ΛoṗΣtü¤≤LCN:)`-Nø

```

Try it online! I was honestly somewhat surprised that `CN` worked as intended here. Heavily inspired by Jo King's answer.

### Explanation

```
!¡λḟ(ΛoṗΣtü¤≤LCN:⁰)-⁰N)ø  (Expanded; let X denote the argument.)
!                         Take element X of
 ¡                         the list created by repeatedly applying this function
                           to the prior list and appending its output,
                       ø    starting with an empty list:
                   -⁰N      Take the list of natural numbers not contained in the
                            argument,
   ḟ                         and find the first element such that
     ΛoṗΣ                     all sums are prime of
                :⁰                the element appended to the argument,
              CN                 cut into lengths of 1, 2, 3, etc.,
          ü¤≤L                  filtered for increasing length,
         t                     with its first element dropped.

```
> 2 votes

# Answer
# Jelly, 32 bytes

```
;®»ṀƊSÆn_S
ẎṀ©+LRḟẎḣL;Ç$ṭ
1Ç¡Fị@

```

**Try it online!** \- very slow as it builds n rows first, for a faster version which doesn't, at 37 bytes, try this.
> 5 votes

# Answer
# Perl 6, ~~80~~ 77 bytes

```
{({$!=@_;+(1...{$_∉$!&&(|$!,$_).rotor(1..*).one.sum.is-prime-1})}...*)[$_]}

```

Try it online!

### Explanation:

```
{                                  }  # Anonymous code block
 (                        ...*)[$_]   # Index into the infinite sequence
  {                      }   # Where each element is
   $!=@_;  # Save the list of previous elements into $!
   +(1...{             })    # Return the first number that
          $_∉$!         # Has not appeared in the list so far
          &&            # And
          (|$!,$_)      # The new sequence
          .rotor(1..*)  # Split into rows of increasing length
                        # And ignoring incomplete rows
          .one          # Have exactly one row
          .sum          # Where the sum
          .is-prime-1   # Is not prime (i.e. just the first row)

```
> 3 votes

# Answer
# Haskell, ~~122~~ 120 bytes

```
import Data.Numbers.Primes
l%a|(p,q)<-splitAt l a,(s,k:t)<-span(not.isPrime.(+sum p))q=p++k:(l+1)%(s++t)
((1:1%[2..])!!)

```

Try it online! (has an extra 2 bytes for `f=`)

EDIT: Now uses 0-based indexing to save 2 bytes. Thanks @wastl for pointing that out, I must have missed it in the OP.

This was very fun to write! The helper function `%` takes a length `l` and a list of values it can use `a`. It returns an infinite list of values for the sequence. The length is one less than the length of the current triangle row and the list is infinite and pre-sorted. First we just yield the first `l` values from `a` and then look through the rest of a until we find the first (smallest) value that makes the sum prime. We break up the list around that value using `span` and some pattern matching. Now all we have to do is yield that new value and recur with the next line length `l+1` and the remaining values in `a`. For the final result we prepend 1 (special case for n=0) and index into it with `!!`.
> 3 votes

# Answer
# JavaScript (ES6),  ~~111~~  110 bytes

```
n=>{for(g=n=>{for(d=n;n%--d;);},i=l=0;i--||(k=s=0,i=l++),n--;g[k]=s+=r=k)for(;g[++k]|g(!i*++s)|d>1;);return r}

```

Try it online!
> 2 votes

# Answer
# Jelly, 46 bytes

```
S©‘æR®Ḥ‘¤_®ḟ;F¥Ṃ
FLḤRḟFḣ0ịLƊ;ç¥µW
1;Ç$⁸½Ḥ¤¡Fị@

```

Try it online!

Times out for large n on tio, but works there for all but the last two examples.
> 2 votes

# Answer
# Lua, ~~242~~ ~~228~~ ~~226~~ 211 bytes

```
s={}u={}i=0 n=0+...while i<n do
n=n-i
x,S=1,0
for j=1,i do
while u[x]do x=x+1 end
s[j]=x
S=S+x
u[x]=0
end
while u[x]or p do
x=x+1
d=S+x
p=F
for c=2,d-1 do
p=p or d%c<1
end
end
i=i+1
s[i]=x
u[x]=0
end
print(s[n])

```

Try it online!
> 0 votes

---
Tags: code-golf, sequence
---


title: Integer Keys and Duplicates

text:
# Question
Title: Integer Keys and Duplicates
Given a non-empty list/vector of positive integers, write a function to check the following conditions in as few bytes as possible.

1. Take the first integer (the key, or k1) and check that the next k1 values have no duplicate values, excluding instances of k1.
2. Take the last integer (the second key, or k2) and check that the k2 values before k2 have no duplicate values, excluding instances of k2.

Note that both keys, k1 and k2, are elements of the list/vector as either key could contain the other.

Also, k1 and/or k2 can be greater than the number of integers within the list, which means you should check every element of the list except for instances of the given key for duplicates.

If both steps return True, return True, else, return False.

**NOTE:** It should be rather intuitive that searching for duplicates within the first k1+1 elements excluding instances of k1 will exclude the first element, or k1. Some answers I've seen "pop" k1 off the list and do the test on the next k1 elements. Either method yields the same results. This is also true for k2 and it's test.

### Test Cases

```
[5,1,2,5,3,4,3] is TRUE because [k1=5][1,2,5,3,4] has no duplicates, nor does [5,3,4][k2=3] have any duplicates, excluding instances of k3.

[6,9,12,15,18,19,8,8,3] is FALSE because [k1=6][9,12,15,18,19,8] has no duplicates while [19,8,8][k2=3] has a duplicate.

[100,100,100,100,101,102,3] is TRUE because [k1=100][100,100,100,101,102,3] has no duplicates, and [100,101,102][k2=3] has no duplicates.

[100,100,100,100,101,102,4] is FALSE. [k1=100][100,100,100,101,102,4] has no duplicates, but [100,100,101,102][k2=4] has duplicates.

[6,6,6,6,6,6,6,3,3,3,3] is TRUE. [k1=6][6,6,6,6,6,6] has no duplicates, excluding instances of k1, and [3,3,3][k2=3] has no duplicates, excluding instances of k2.

[1,2] is TRUE (clearly)

[1] is TRUE (clearly)

```

# Answer
> 4 votes
# JavaScript (ES6),  ~~88 75 71~~  69 bytes

```
a=>(g=_=>!a.reverse().some(o=(v,i,[k])=>v-k&&o[v]&(o[v]=i<=k)))()&g()

```

Try it online!

### Commented

The function \\$g\\$ reverses the input array and performs the test with the resulting leading key.

```
g= _ =>               // g takes no explicit input
  !a.reverse()        // reverse the input array a[]
  .some(o =           // we use the object o to store encountered values
    (v, i,            // for each value v at position i in a[],
           [k]) =>    // with k = leading value:
      v - k &&        //   abort if v is equal to the key
      o[v] &          //   otherwise, test whether o[v] is already set
      (o[v] = i <= k) //   and i is less than or equal to the key,
                      //   in which case o[v] is set
  )                   // end of some()

```

The main function simply invokes \\$g\\$ twice.

```
a => g() & g()

```

# Answer
> 3 votes
# Jelly, 12 bytes

```
,Uḣ⁹ḟQƑʋḢ$€Ạ

```

Try it online!

A monadic link taking a list of integers and returning a Jelly Boolean (1 for True, 0 for False).

## Explanation

```
,U            | Pair with reversed list
       ʋḢ$€   | For each pair, do the following as a dyad using the popped head as the right argument y:
  ḣ⁹          | - First y integers
    ḟ         | - Filter out y
     QƑ       | - Check if invariant when uniquified
           Ạ  | All

```

# Answer
> 3 votes
# Python 2, ~~95~~ ~~88~~ ~~75~~ 74 bytes

```
lambda x:all(A[:A[0]+1].count(a)<2for A in[x,x[::-1]]for a in A if a-A[0])

```

Try it online!

7 bytes saved thx to Jo King; then 8 more thx to Value Ink; and then 5 more from Jo King; and 1 byte thx to mypetition pointing out an extra space.

Function taking a list of ints; returns `False/True`.

# Answer
> 2 votes
# Charcoal, 31 bytes

```
∨¬⮌θ⬤Ｅ⟦⮌θθ⟧✂⮌ι⁰⊟ι¹⬤ι∨⁼№ιλ¹⁼λ§ι⁰

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, which is `-` for true and nothing for false. Explanation:

```
∨¬⮌θ

```

If the reversed list is empty then the result is true. (Don't ask me why I need to reverse the list first... I think the implicit input uses a subtly different data type or something.)

```
⬤Ｅ⟦⮌θθ⟧

```

Check the list both backwards and forwards.

```
✂⮌ι⁰⊟ι¹

```

Slice the last `n` elements of the reversed list where `n` is the last element.

```
⬤ι∨⁼№ιλ¹⁼λ§ι⁰

```

Check that each element is either unique or equal to the first element.

# Answer
> 2 votes
# Ruby, ~~64~~ 56 bytes

Mimics the JavaScript answer in that it takes a helper function and checks the array and its reversed version, but the check for uniqueness is done by taking the subarray based on the key, removing all copies of the key, then checking if the (modified) subarray matches its deduplicated version.

-8 bytes by improving the empty list check, and golfing the deduplication code.

```
->a{g=->f=0,*a{a=a[0,f]-[f];a&a==a};g[*a]&g[*a.reverse]}

```

Try it online!

# Answer
> 2 votes
# Python 3.8 (pre-release), ~~138~~ \\$\cdots\\$ ~~102~~ 91 bytes

```
lambda x:all(len(set(t:=[e for e in l[1:l[0]+1]if e-l[0]]))==len(t)for l in[x,x[::-1]]if l)

```

Try it online!

Saved 11 bytes thanks to @JoKing!!!

# Answer
> 2 votes
# Perl 5 `-MList::Util=uniq,head -pF,`, ~~71~~ 66 bytes

```
sub b{(@_=grep$_-@_[0],head$_[0]+1,@_)==uniq@_}$_=b(reverse@F)*b@F

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 13 bytes

```
Â‚εć©£®KDÙQ}P

```

Port of *@NickKennedy*'s Jelly answer, so make sure to upvote him as well!

Try it online or verify all test cases.

**Explanation:**

```
Â            # Bifurcate the (implicit) input-string; short for Duplicate & Reverse copy
 ‚           # Pair this reversed input with the duplicated input
  ε          # Map over the inner lists of this pair:
   ć         #  Extract the head; pop and push remainder-list and first item
    ©        #  Store this head in variable `®` (without popping)
     £       #  Leave the first `®` items from the remainder-list
      ®K     #  Remove all `®` (if present)
        DÙ   #  Duplicate this list, and uniquifiy it
          Q  #  And check if it's still the same
  }P         # After the map, check if both were truthy
             # (which is output implicitly as result)

```

# Answer
> 1 votes
# , ~~36~~ 28 bytes

```
*&({.(-:~.)@-.~}.{.~{.<.#)|.

```

Try it online!

* `*&( )|.` Take the original input (implicit in the hook) and its reverse `|.`, and multiply the boolean values `*` produced by transforming them with the verb in parens `&( )`

Let's break down the verb in parens...

* `}.{.~{.<.#` From the beheaded `}.` input take `{.~` this many elements: The smaller of `<.` the first element `{.` and the length of the list `#`
* `{.( )@-.~` And from that remove all instances of `-.~` the first element of the list `{.` and `@` apply the inner verb in parens...
* `(-:~.)` Is the list identical to `-:` its uniq `~.`?

# Answer
> 1 votes
# , ~~72~~ ~~71~~ 70 bytes

```
`-`=function(l)!anyDuplicated(head(l,l[1]+1),l[1])
-(l=scan())&-rev(l)

```

Try it online!

Saved a byte thanks to Sumner18.

# Answer
> 1 votes
# Husk, 13 bytes

```
S¤&ΓȯS=uΣSx↑↔

```

Try it online! The function does the k1 test for the both the list and its reverse.

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


# Question
Title: Bookkeeping for the Sex Bob-ombs (check if a running sum ever gets too low)
Believe it or not, the Sex Bob-ombs have become a world famous band and are currently on world tour! As their bookkeeper you must oversee their day to day finances and provide regular reports.

Every few weeks you compile a list of their expenses (in whole USD) in the order they were incurred.

For example, the list

```
378
-95
2234

```

means that $378 was deposited to their account, and after that $95 was withdrawn, and after that $2234 was deposited.

You want to make sure that the running sum of these values never goes below some threshold value *T*. You decide to write a program to do this for you.

# Challenge

Write a program or function that takes in a single integer *T* and a list of integers. If the running sum of the list of integers is ever less than *T*, then print or return a falsy value, otherwise print or return a truthy value.

You may use any usual input methods (stdin, from file, command line, arguments to function).

* **At the start of the list the running sum is 0. So a positive *T* means the result is always falsy.**
* `+` will never be in front of positive integers.
* The list may contain 0.
* The list may be empty.

# Test Cases

*T* is -5 in all of these.

Falsy:

```
-6
```

```
1
2
3
-20
```

```
200
-300
1000
```

Truthy:

```
[empty list]
```

```
-5
```

```
4
-3
-6

```

# Scoring

The submission with the fewest bytes wins. Tiebreaker goes to earliest posted submission.

The regrettable comment that forced me to make this.

# Answer
> 2 votes
# gs2 \- 6 bytes

Assume the list is on top of the stack, and the threshold is in register A. In mnemonics:

```
inits
sum get-a lt filter3
not

```

In bytecode:

```
78 64 D0 70 F2 22

```

# Answer
> 11 votes
# Haskell, 22 bytes

```
f t=all(>=t).scanl(+)0

```

Usage: `f (-5) [4,-3,-6]` which outputs `True`.

Make a list of sub-totals and check if all elements are \>= t.

Edit: Bugfix for empty list and positive `t`s

# Answer
> 7 votes
# Python 2, 41

```
f=lambda a,t:t<=0<(a and f(a[1:],t-a[0]))

```

The first argument is the array; the second is the minimum running total.

# Answer
> 6 votes
# J, 11 bytes

```
   */@:<:0,+/\

```

Tests

```
   _5 (*/@:<:0,+/\)  1 2 3 _20
0
   _5 (*/@:<:0,+/\)  >a: NB. empty list
1

```

1-byte improvement thanks to FUZxxl.

Explanation for the original version `(*/@(<:0,+/\))`

* `+/\` creates a running sum (sum `+/` of prefixes `\`)
* `0,+/\` appends a 0 to the running sum
* `(<:0,+/\)` left side input smaller or equal `<:` than (elements of of the) result of `0,+/\` on the right side input
* `@` with the previous result
* `*/` product of all elements (1 if all elements are 1, 0 if an element is 0)

# Answer
> 6 votes
# APL, ~~8~~ 10

```
∧.≤∘(0,+\)

```

This is a function that takes `T` as its left argument and the list as its right argument.

* `0,+\`: running sum of right argument, appended to a 0
* `∧.≤`: left argument smaller or equal (≤) than all (∧) items in the right argument

# Answer
> 4 votes
# Mathematica, 34 bytes

```
FreeQ[Accumulate@{0,##2},n_/;n<#]&

```

This defines an unnamed variadic function which take `T` as the first parameter and the transactions as the remaining parameters, and returns a boolean:

```
FreeQ[Accumulate@{0,##2},n_/;n<#]&[-5, 1, 2, 3, -20]
(* False *)

```

I like this because I could make use of the rather rare `##2` which "splats" all arguments from the second into the list. For more details see the last section in this golfing tip.

# Answer
> 4 votes
# Prelude, ~~144~~ 136 bytes

This was... hard...

```
?
?(1- )v1+(1-
 ^    #       1) v #  -)1+(#
  v#         vv (##^v^+
   ^?+     v-(0## ^ #   01 #)(#)#
1         v#                  # )!

```

I think 6 voices is a new record for me, although I'm sure there's a way to reduce that and get rid of lots of that annoying whitespace. Checking the sign of a value (and therefore, checking whether one value is greater than another) is quite tricky in Prelude.

Input and output is given as byte values. When you use the Python interpreter, you can set `NUMERIC_OUTPUT = True`, so that you actually get an ASCII `0` or `1`. For numeric input, you'd have to add another `NUMERIC_INPUT` flag (I should probably publish my tweaked interpreter at some point).

Also note that Prelude cannot really distinguish the end of a list from a `0` within the list. So in order to allow zero transactions, I'm reading `T`, then the length `L` of the list, and then `L` transactions.

# Answer
> 4 votes
# k, 8 char

A dyadic verb taking the threshold as the first argument and the list as the second. Remarkably, this works in every version of k, including the open-source Kona.

```
&/~0<-\,

```

In k, composition of functions is just done by writing one and then the other, so we can break this up by functions. From right to left:

* `-\,` takes successive running sums and subtracts them from the threshold. (If `f` is dyadic, then `f\ (a; b; c; ...)` expands to `(a; a f b; (a f b) f c; ...)`. `,` just joins lists together.) Breaking even occurs when something is equal to 0, and overdrawing gives strictly positive values.
* `~0<` is Not 0 Less-Than. k doesn't really have a greater-than-or-equal-to `<=` operator, so we have to throw boolean NOT on a less-than, but this tests for whether the result is nonpositive. It automatically applies to each atom in the list.
* `&/` is the fold of logical AND over a list. (For `f` dyadic) So this tests whether every boolean in the list is True.

Examples:

```
  (&/~0<-\,)[-5; 1 2 3 -20]
0
  f:&/~0<-\,  /assign to a name
  f[-5; 4 -3 -6]
1

```

# Answer
> 3 votes
# CJam, 17 bytes

```
l~0\{1$+}%+\f<:+!

```

Takes input as an integer and a CJam-style array on STDIN:

```
-5 [1 2 3 -20]

```

Test it here.

# Answer
> 3 votes
# Pyth, ~~16~~ 15

```
!sm>vzs+0<QdhlQ

```

Try it online with the input

```
-5
[4, -3, 6]

```

## Explanation:

```
                   Implicit: z and Q read 2 line from input
                   z = "-5" (this is not evaluated, it's a string)
                   Q = [4, -3, 6] (this is a list though)
 m         hlQ     map each number d in [0, 1, 2, ..., len(Q)] to:
  >vz                 the boolean value of: evaluated z >
     s+0<Qd                                 the sum of the first d elements in Q
!s                  print the boolen value of: 1 > sum(...)

```

And again the stupid `s` function wastes two bytes. I think I'm gonna report this as a bug to the Pyth repo.

# edit: 13 (not valid)

Thanks to isaacg for one byte save (`>1` to `!`) and for changing the implementation of `s` in the Pyth repo. Now the following code is possible (but of course not valid for this challenge).

```
!sm>vzs<QdhlQ

```

# Answer
> 3 votes
# R, 35

```
function(t,l)all(cumsum(c(0,l))>=t)

```

Try it here

# Answer
> 3 votes
# Julia, 33 bytes

```
(T,l)->all(i->i>=T,cumsum([0,l]))

```

This creates an unnamed function that accepts two parameters, `T` and `l`, and returns a boolean.

The `all()` function does all of the heavy lifting here. It takes two arguments: a predicate and an iterable. For the predicate, we tell it that `i` represents the current value of the iterable using an unnamed function, specified by `i->`. Then at each iteration we compare `i` to `T` using `i>=T`.

To make sure that Julia doesn't freak out about using `cumsum()` on an empty list, we can tack a zero on there using `[0, l]`.

# Answer
> 2 votes
# Python 2.7 - 55 bytes

```
f=lambda T,l:all(T<=sum(l[:i])for i in range(len(l)+1))

```

Call like `print f(-5,[1,2,3,-20])`. Test it here.

Thanks to Jakube for helping.

# Answer
> 2 votes
# CJam, 18 bytes

Another approach in same bytes as the other one.

```
q~_,),\f<1fb:)f<:&

```

Takes input via STDIN in the form of `<threshold> <array of transactions>`

Try it online here

# Answer
> 2 votes
# JavaScript (ES6) 38 ~~33~~

**Edit** Fixed initial balance bug. Thx @martin & @rainbolt

```
F=(t,l)=>![r=0,...l].some(v=>(r+=v)<t)

```

**Test** In Firefox/FireBug console

```
console.log(F(-5,[-6]),F(-5,[1,2,3,-20]),F(-5,[200,-300,1000]))
console.log(F(-5,[]),F(-5,[-5]),F(-5,[4,-3,-6]))
console.log(F(5,[10]),F(5,[]))

```

> false false false
> true true true
> false false

# Answer
> 2 votes
# \>\<\>, 29 + 3 = 32 bytes

```
r0}&v >1n;n0<
&:&:<+^?=1l ^?(

```

Run like

```
py -3 fish.py bookkeep.fish -v -5 4 3 -6

```

where the threshold is the first number.

# Answer
> 1 votes
# Octave, 27

```
@(t,l)all(cumsum([0,l])>=t)

```

# Answer
> 1 votes
# Perl 6 (21 bytes)

```
{$^a>none [\+] 0,@^b}

```

It's a function taking initial argument, and list of elements. It works by checking if none (by using junctions) of elements are below the threshold. `[\+]` is used for generating running sum, for example `[\+] 1, 2, 3` gives `1, 3, 6`. `0,` to append `0` at beginning of list is needed because of requirement that positive threshold always should fail.

Pretty much the same thing as Haskell solution, just in Perl 6 syntax (Perl 6 took so many neat programming features from Haskell).

# Answer
> 0 votes
## Perl - 20

Take the list of numbers on `STDIN` seperated by newlines and take `T` with the `-i` flag.

```
die if$^I>($i+=$_)

```

+2 for `-i` and `-n` flags. The exit value is `255` for failures and `0` on success.

Run with:

```
echo -e "4\n3\n-6" | perl -i0 -ne'die if$^I>($i+=$_)'

```

# Answer
> 0 votes
# Clojure, 45

```
(fn[T t](every? #(<= T %)(reductions + 0 t)))

```

E.g.

```
((fn[T t](every? #(<= T %)(reductions + 0 t))) -5 [1 2 3 -20])
;; =>false

```

Or a lil' nicer;

```
(defn f[T t](every? #(<= T %)(reductions + 0 t)))

(testing
  (testing "tests from question"
    (is (false? (f -5 [-6])))
    (is (false? (f -5 [1 2 3 -20])))
    (is (false? (f -5 [200 -300 1000])))
    (is (true? (f -5 [-5])))
    (is (true? (f -5 [4 -3 -6])))
    (is (true? (f -5 []))))
  (testing "the start of the list the running sum is 0. So a positive T means the result is always falsy"
    (is (false? (f 5 [5])))
    (is (false? (f 5 [10])))
    (is (false? (f 5 [])))))

```

# Answer
> 0 votes
# Java 8 - 153 chars

Golfed function:

```
import java.util.stream.*;
boolean f(int t, IntStream s){int r=1;try{s.reduce(0,(a,b)->(a+b>=t)?(a+b):(a/(a-a)));}catch(Exception e){r=0;}return r==1;}

```

Ungolfed:

```
import java.util.stream.*;

boolean f(int t, IntStream s) {
    int r=1;
    try {
        s.reduce(0,(a,b) -> (a+b>=t) ? (a+b) : (a/(a-a)));
    } catch(Exception e) {
        r=0;
    }

    return r==1;
}

```

Driver program:

```
import java.util.stream.*;
import java.util.*;

public class A {
    // function f as above

    public static void main(String... args) {
        int t = -5;
        IntStream s = null;

        s = Arrays.asList(-6).stream().mapToInt(i->i);
        System.out.println(new A().f(t,s));

        s = Arrays.asList(1,2,3,-20).stream().mapToInt(i->i);
        System.out.println(new A().f(t,s));

        s = Arrays.asList(200,-300,1000).stream().mapToInt(i->i);
        System.out.println(new A().f(t,s));

        System.out.println("above false, below true");

        s = IntStream.empty();
        System.out.println(new A().f(t,s));

        s = Arrays.asList(4,-3,-6).stream().mapToInt(i->i);
        System.out.println(new A().f(t,s));

        s = Arrays.asList(-5).stream().mapToInt(i->i);
        System.out.println(new A().f(t,s));
}

```

}

Output:

```
bash-3.2$ javac A.java ; java A

false
false
false
above false, below true
true
true
true

```

# Answer
> 0 votes
# Jelly, 4 bytes

```
Ä<Ẹ¬

```

Try it online!

Outputs `0` for falsey and `1` for truthy. The final byte can be removed if the outputs can be flipped.

I decided to put this through a basic brute-forcer to try to get a 3 byte solution. Any such solution would have to be in the form `Ä<X`, where `X` is an unknown atom. This Jelly program iterates through all atoms (ones that lead to errors were removed), inserts them into the template above and tests whether the atom gives the desired results for the inputs. If it does, it should output `1`. The final number is the number of successes, which is unfortunately `0`. However, if we change the template to mirror the above program (4 bytes), we get 7 results:

```
Ä<S¬
Ä<Ḅ¬
Ä<Ḍ¬
Ä<Ẹ¬
Ä<Ṁ¬
Ä<§¬

```

I've excluded `Ä<V¬` due to the extra output it produces

## How it works

```
Ä<Ẹ¬ - Main link. Takes L on the left and T on the right
Ä    - Cumulative sum of L
 <   - Is each less than T?
       This yields all 0s for a truthy input and at least 1 1 otherwise
  Ẹ  - Is there a 1?
   ¬ - Logical NOT

```

# Answer
> 0 votes
# Japt, 6 bytes

```
å+ e¨V

```

Try it here

# Answer
> 0 votes
# Husk, 5 bytes

```
Λ>⁰∫²

```

Try it online!

Not sure how to remove the superscripts, but it should be possible.

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


# Question
Title: Counting cycles in a folding and squashing process
In chaos theory, the horseshoe map is an example of how chaos arises in a simple process of folding and squashing. It goes like this: take an imaginary piece of dough, fold it, and finally squash it to its original size. Chaos arises in the pattern of how the pieces of dough end up in the final arrangement after n iterations.

In our case, we'll take a look at how a simple binary pattern behaves when we fold and squash it. Here are the steps with an 8-bit example (the binary representation of 201 or `11001001`).

1. Cut the bits in two pieces of equal length (add a '0' at the beginning if there is an odd number of bits).

`1100 | 1001`
2. Fold the first half over the second half. Note that the order of the first half is reversed, as we rotate it while folding.

`0011`
`1001`
3. Squash to its original shape. While squashing, the upper bits are shifted left to the bits under their original position.

`01001011`

If we repeat this for this example, we can see that after 4 iterations, we are back to the original bitstring:

```
Start  bits: 11001001
Iteration 1: 01001011
Iteration 2: 01001101
Iteration 3: 01011001
Iteration 4: 11001001

```

So, for the decimal value of 201, the number of cycles is 4.

## The challenge

* Write a full program that takes a decimal number as input and outputs the number of cycles it takes to repeat in the above described binary squash-and-fold process.
* The (decimal) input must be taken from stdin (range: from 1 up to Googol or 10^100).
* The (decimal) output must be written to stdout.
* Your score is the number of bytes of your code.
* Your answer must begin with \[Programming language\] - \[Score in bytes\]
* Standard loopholes are not allowed.

## Examples

```
7 --> 3
43 --> 5
178 --> 4
255 --> 1
65534 --> 1
65537 --> 12
1915195950546866338219593388801304344938837974777392666909760090332935537657862595345445466245217915 --> 329

```

## Final note

What's interesting is that the number of cycles is related to the length of the binary representation, except for a few exceptions where the number of cycles is shorter because of the pattern in the bitstring (for example `111110` cycles after 1 iteration). This creates an interesting opportunity to optimize code length using the underlying pattern instead of calculating the number of cycles.

# Answer
# CJam, 34 bytes

```
q~2b_,2%,\+{__,2//~\W%.\_W$=!}g;],

```

Nothing fancy, it just applies the map until we get back to the input, and print the number of iterations that took.

Test it here.
> 4 votes

# Answer
# Python 2, ~~175~~ ~~154~~ 149 bytes

```
i=bin(input())[2:]
i=o='0'+i if len(i)%2 else i
c=0
j=len(i)/2
while i!=o or c==0:
 a=''
 for x,y in zip(i[:j][::-1],i[j:]):a+=x+y
 i,c=a,c+1
print c

```

Ideone link

Thanks to agtoever for 27 bytes!
> 3 votes

# Answer
# Pyth, 21 bytes

I'm typing this on my phone, so please make sure to notify me of any mistakes.

```
fqu.i_hc2Gec2GTJ.BQJ1

```

Try it online.
> 2 votes

# Answer
# APL (Dyalog Extended), 37 bytes

```
≢{⊃,/↓⍉⌽@1⊢2 ¯1⍴{2|≢⍵:0,⍵⋄⍵}⍵}⌂traj⊤⎕

```

Try it online!

A full program which takes a single number as input.

The `traj` function does a lot of heavy lifting here(thanks to Bubbler for suggesting it and helping ot golf this).

The `(,,⍤0)/` idiom from APLcart is used to interleave lists together, but instead this uses `,/↓⍉⌽` since it is a matrix.

## Explanation

```
≢{⊃,/↓⍉⌽@1⊢2 ¯1⍴{2|≢⍵:0,⍵⋄⍵}⍵}⌂traj⊤⎕
                                   ⊤⎕ convert input to base-2
 {                           }⌂traj   calculate trajectory when the following function is applied repeatedly:
                {2|≢⍵:0,⍵⋄⍵}⍵         prepend a 0 if there are an odd number of bits
           2 ¯1⍴                     cut into two rows
       ⌽@1⊢                          apply reverse to first row
   ,/↓⍉                              transpose, concatenate into a vector
  ⊃                                  unenclose
≢                                    get length of the resulting list

```
> 0 votes

---
Tags: code-golf, binary
---


title: Discrete Baker's Map

text:
# Question
Title: Discrete Baker's Map
# Introduction

The Baker's map is an important dynamical system that exhibits chaotic behavior. It is a function from the unit square to itself defined intuitively as follows.

* Cut the square vertically in half, resulting in two rectangles of size `0.5×1`.
* Stack the right half on top of the left, resulting in one rectangle of size `0.5×2`
* Compress the rectangle back into a `1×1` square.

In this challenge, you'll implement a discrete version of this transformation.

# Input and Output

Your input is a 2D array of printable ASCII characters and whitespace of size `2m×2n` for some `m, n > 0`. Your output is a similar array obtained as follows, using the `6×4` array

```
ABCDEF
GHIJKL
MNOPQR
STUVWX

```

as an example. First, stack the right half of the array on top of the left half:

```
DEF
JKL
PQR
VWX
ABC
GHI
MNO
STU

```

Then, split the columns into pairs of characters, and independently turn each pair 90 degrees clockwise, "compressing" the tall rectangle back to the original shape:

```
JDKELF
VPWQXR
GAHBIC
SMTNUO

```

This is the correct output for the above array.

# Rules

The input and output formats are flexible. You can use newline-delimited strings, lists of strings, or 2D arrays of characters. However, the input and output **must** have the exact same format: you must be able to iterate your submission an arbitrary number of times on any valid input.

You can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

# Test Cases

```
Input:
12
34

Output:
42
31

Input:
Hell
!  o
d  -
lroW

Output:
 lol
o W-
!H e
ldr

Input:
ABCDEF
GHIJKL
MNOPQR
STUVWX

Output:
JDKELF
VPWQXR
GAHBIC
SMTNUO

Input:
*___  ___  o
o|__) |__) *
*|    |    o
o __   __  *
*|    | _  o
o|__  |__| *

Output:
|_____)   *o
 |_ _     *o
||_ __|   *o
o*|_____)
o* |_ _
o*||_ _

```

# Answer
# Pyth, ~~25~~ ~~19~~ 18 bytes

```
msC_dcs_Cmck/lk2Q2

```

Online demonstration. It uses an 2D-array of chars.

Array of strings is one char longer (19 bytes). Online demonstration

### Explanation:

```
         m      Q    map each string k in input:
            /lk2        calculate half the line-length: len(k)/2
          ck/lk2        chop k into pieces of length len(k)/2
                        results in two pieces
        C            zip the resulting list
                     results in a tuple ([first half of strings], [second half of strings])
       _             invert the order ([second half of strings], [first half of strings])
      s              sum (combine the two lists to a big one
     c           2   chop them into tuples
m                          for each tuple of strings:
 sC_d                        invert, zip, and sum

```

The last part is a bit confusing at first. Let's assume we have the tuple `['DEF', 'JKL']` (I use the example from the OP).

```
    d  (('D', 'E', 'F'), ('J', 'K', 'L'))   just the pair of strings
   _d  (('J', 'K', 'L'), ('D', 'E', 'F'))   invert the order
  C_d  [('J', 'D'), ('K', 'E'), ('L', 'F')] zipped
 sC_d  ('J', 'D', 'K', 'E', 'L', 'F')       sum (combine tuples)

```
> 11 votes

# Answer
# Julia, 136 bytes

A very straightforward implementation. Not a particularly competitive entry, but it was fun!

```
A->(s=size(A);w=s[2];u=w÷2;C=vcat(A[:,u+1:w],A[:,1:u]);D=cell(s);j=1;for i=1:2:size(C,1) D[j,:]=vec(flipdim(C[i:i+1,:],1));j+=1end;D)

```

This creates a lambda function that accepts a 2-dimensional array as input and returns a transformed 2-dimensional array.

Ungolfed + explanation:

```
function f(A)

    # Determine bounds
    s = size(A)          # Store the array dimensions
    w = s[2]             # Get the number of columns
    u = w ÷ 2            # Integer division, equivalent to div(w, 2)

    # Stack the right half of A atop the left
    C = vcat(A[:, u+1:w], A[:, 1:u])

    # Initialize the output array with the appropriate dimensions
    D = cell(s)

    # Initialize a row counter for D
    j = 1

    # Loop through all pairs of rows in C
    for i = 1:2:size(C, 1)

        # Flip the rows so that each column is a flipped pair
        # Collapse columns into a vector and store in D
        D[j, :] = vec(flipdim(C[i:i+1, :], 1))

        j += 1
    end

    return D
end

```

To call it, give the function a name, e.g. `f=A->(...)`.

Example output:

```
julia> A = ["A" "B" "C" "D" "E" "F";
            "G" "H" "I" "J" "K" "L";
            "M" "N" "O" "P" "Q" "R";
            "S" "T" "U" "V" "W" "X"]
julia> f(A)

4x6 Array{Any,2}:
 "J"  "D"  "K"  "E"  "L"  "F"
 "V"  "P"  "W"  "Q"  "X"  "R"
 "G"  "A"  "H"  "B"  "I"  "C"
 "S"  "M"  "T"  "N"  "U"  "O"

julia> B = ["H" "e" "l" "l";
            "!" " " " " "o";
            "d" " " " " "-";
            "l" "r" "o" "W"]
julia> f(B)

4x4 Array{Any,2}:
 " "  "l"  "o"  "l"
 "o"  " "  "W"  "-"
 "!"  "H"  " "  "e"
 "l"  "d"  "r"  " "

```

And proof that it can be arbitrarily chained:

```
julia> f(f(B))

4x4 Array{Any,2}:
 "W"  "o"  "-"  "l"
 "r"  " "  " "  "e"
 "o"  " "  " "  "l"
 "l"  "!"  "d"  "H"

```

Suggestions are welcome as always, and I'll happy provide any further explanation.
> 9 votes

# Answer
# CJam, ~~25~~ 24 bytes

```
qN/_0=,2/f/z~\+2/Wf%:zN*

```

Straight forward spec implementation. Explanation:

```
qN/                       "Split input by rows";
   _0=,2/                 "Get half of length of each row";
         f/               "Divide each row into two parts";
           z              "Convert array of row parts to array of half columns parts";
            ~\+           "Put the second half of columns before the first half and join";
               2/         "Group adjacent rows";
                 Wf%      "Flip the row pairs to help in CW rotation";
                    :z    "Rotate pairwise column elements CW";
                      N*  "Join by new line";

```

Try it online here
> 8 votes

# Answer
# JavaScript (ES6), 104  ~~141~~

**Edit** Reviewing the spec, I found that the number of rows must be even (I missed this before). So it's not too complicated find the correct source position for each char in output in a single step.

```
F=a=>a.map((r,i)=>
  [...r].map((c,k)=>
     a[l=i+i]?a[(j=l+1)-k%2][(k+r.length)>>1]:a[l-j-k%2][k>>1]
  ).join('')
)

```

**Test** In Firefox/FireBug console

```
;[["ABCDEF","GHIJKL","MNOPQR","STUVWX"]
 ,["12","34"], ["Hell","!  o","d  -","lroW"]
 ,["*___  ___  o","o|__) |__) *","*|    |    o","o __   __  *","*|    | _  o","o|__  |__| *"]
].forEach(v=>console.log(v.join('\n')+'\n\n'+F(v).join('\n')))

```

*Output*

```
ABCDEF
GHIJKL
MNOPQR
STUVWX

JDKELF
VPWQXR
GAHBIC
SMTNUO

12
34

42
31

Hell
!  o
d  -
lroW

 lol
o W-
!H e
ldr

*___  ___  o
o|__) |__) *
*|    |    o
o __   __  *
*|    | _  o
o|__  |__| *

|_____)   *o
 |_ _     *o
||_ __|   *o
o*|_____)
o* |_ _
o*||_ _

```
> 7 votes

# Answer
# J, ~~45~~ 39 bytes

```
   $$[:,@;@|.@|:([:,:~2,2%~1{$)<@|:@|.;.3]

```

J has a tessellation function (cut `;.`) which helps a lot.

```
   ]input=.4 6$97}.a.
abcdef
ghijkl
mnopqr
stuvwx

   ($$[:,@;@|.@|:([:,:~2,2%~1{$)<@|:@|.;.3]) input
jdkelf
vpwqxr
gahbic
smtnuo

```
> 5 votes

# Answer
# Haskell, ~~128~~ 127 bytes

```
import Control.Monad
f=g.ap((++).map snd)(map fst).map(splitAt=<<(`div`2).length)
g(a:b:c)=(h=<<zip b a):g c
g x=x
h(a,b)=[a,b]

```

Usage: `f ["12", "34"]` -\> `["42","31"]`

How it works:

```
                                 input list:
                                   ["abcdef", "ghijkl", "mnopqr", "stuvwx"]
==========================================================================

map(splitAt=<<(`div`2).length)   split every line into pairs of halves:
                                   -> [("abc","def"),("ghi","jkl"),("mno","pqr"),("stu","vwx")]
ap((++).map snd)(map fst)        take all 2nd elements of the pairs and
                                 put it in front of the 1st elements:
                                   -> ["def","jkl","pqr","vwx","abc","ghi","mno","stu"]
(    zip b a) : g c              via g: take 2 elements from the list and
                                 zip it into pairs (reverse order),
                                 recur until the end of the list:
                                   -> [[('j','d'),('k','e'),('l','f')],[('v','p'),('w','q'),('x','r')],[('g','a'),('h','b'),('i','c')],[('s','m'),('t','n'),('u','o')]]
h=<<                             convert all pairs into a two element list
                                 and concatenate:
                                   -> ["jdkelf","vpwqxr","gahbic","smtnuo"]

```

Edit: @Zgarb found a byte to save.
> 4 votes

# Answer
## J, ~~33~~ 32 characters

A monadic verb.

```
0 2,.@|:_2|.\"1-:@#@{.(}.,.{.)|:

```

### Explanation

Let's begin by defining `Y` to be our sample input.

```
   ] Y =. a. {~ 65 + i. 4 6          NB. sample input
ABCDEF
GHIJKL
MNOPQR
STUVWX

```

The first part (`-:@#@{. (}. ,. {.) |:`) splits `Y` in half and appends then ends:

```
   # {. Y                            NB. number of columns in Y
6
   -: # {. Y                         NB. half of that
3
   |: Y                              NB. Y transposed
AGMS
BHNT
CIOU
DJPV
EKQW
FLRX
   3 {. |: Y                         NB. take three rows
AGMS
BHNT
CIOU
   3 }. |: Y                         NB. drop three rows
DJPV
EKQW
FLRX
   3 (}. ,. {.) |: Y                 NB. stitch take to drop
DJPVAGMS
EKQWBHNT
FLRXCIOU

```

In the second part (`_2 |.\"1`) we split this into pairs of two and reverse them:

```
   R =. (-:@#@{. (}. ,. {.) |:) Y    NB. previous result
   _2 <\"1 R                         NB. pairs put into boxes
┌──┬──┬──┬──┐
│DJ│PV│AG│MS│
├──┼──┼──┼──┤
│EK│QW│BH│NT│
├──┼──┼──┼──┤
│FL│RX│CI│OU│
└──┴──┴──┴──┘
   _2 <@|.\"1 R                      NB. reversed pairs
┌──┬──┬──┬──┐
│JD│VP│GA│SM│
├──┼──┼──┼──┤
│KE│WQ│HB│TN│
├──┼──┼──┼──┤
│LF│XR│IC│UO│
└──┴──┴──┴──┘

```

Finally (`0 2 ,.@|:`), we transpose the matrix as needed and discard the trailing axis:

```
   ] RR =. _2 |.\"1 R                NB. previous result
JD
VP
GA
SM

KE
WQ
HB
TN

LF
XR
IC
UO
   0 2 |: RR                         NB. transpose axes
JD
KE
LF

VP
WQ
XR

GA
HB
IC

SM
TN
UO
   ($ RR) ; ($ 0 2 |: RR)            NB. comparison of shapes
┌─────┬─────┐
│3 4 2│4 3 2│
└─────┴─────┘
   ,. 0 2 |: RR                      NB. discard trailing axis
JDKELF
VPWQXR
GAHBIC
SMTNUO

```

The whole expression with whitespace inserted:

```
0 2 ,.@|: _2 |.\"1 -:@#@{. (}. ,. {.) |:

```

And as an explicit verb:

```
3 : ',. 0 2 |: _2 |.\"1 (-: # {. y) (}. ,. {.) |: y'

```
> 3 votes

# Answer
# GNU sed -r, 179 bytes

Score includes +1 for the `-r` arg to sed.

It took me a while to figure out how to do this in `sed`, but I think I have it now:

```
# Insert : markers at start and end of each row
s/  /:  :/g
s/(^|$)/:/g
# Loop to find middle of each row
:a
# Move row start and end markers in, one char at a time
s/:([^  :])([^  :]*)([^ :]):/\1:\2:\3/g
ta
# Loop to move left half of each row to end of pattern buffer
:b
s/([^   :]+)::(.*)/\2   \1/
tb
# remove end marker
s/$/:/
# double loop to merge odd and even rows
:c
# move 1st char of rows 2 and 1 to end of pattern buffer
s/^([^  :])([^  ]*) ([^ ])(.*)/\2   \4\3\1/
tc
# end of row; remove leading tab and add trailing tab
s/^ +(.*)/\1    /
tc
# remove markers and trailing tab
s/(:|   $)//g

```

Note all the whitespace above should be single `tab` characters. Comments are not included in the golf score.

Note also that this makes extensive use of `:` marker characters. If the input stream contains `:`, then undefined behaviour will ensue. This can be mitigated by replacing all `:` with some non-printing character (e.g. BEL) at no cost to the golf score.

Input and output is a tab-separated list of strings:

```
$ echo 'Hell
!  o
d  -
lroW' | paste -s - | sed -rf baker.sed | tr '\t' '\n'
 lol
o W-
!H e
ldr
$

```
> 3 votes

# Answer
# Husk, 18 bytes

```
mΣmm↔TmC2T§+m→m←m½

```

Try it online!

Gaming
> 0 votes

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