# Question
Title: Find the largest N digit number in a W by H grid of digits
Write a program or function that takes in a positive integer \\$N\\$ and a grid of decimal digits (\\$0\\$ to \\$9\\$) with width \\$W\\$ and height \\$H\\$ (which are also positive integers). You can assume that \\$N\\$ will be less than or equal to the larger of \\$W\\$ and \\$H\\$ (\\$N \le \max(W,H)\\$).

Print or return the largest contiguous \\$N\\$-digit number that appears horizontally or vertically in the grid, written in normal reading order or in reverse.

* Diagonal lines of digits are not considered.
* The grid does not wrap around, i.e. it does not have periodic boundary conditions.

For example, the \\$3\times3\\$ grid

```
928
313
049

```

would have `9` as the output for \\$N = 1\\$, `94` as the output for \\$N = 2\\$, and `940` as the output for \\$N = 3\\$.

The \\$4\times3\\$ grid

```
7423
1531
6810

```

would have `8` as the output for \\$N = 1\\$, `86` for \\$N = 2\\$, `854` for \\$N = 3\\$, and `7423` for \\$N = 4\\$.

The \\$3\times3\\$ grid

```
000
010
000

```

would have output `1` for \\$N = 1\\$, and `10` for N = 2 and N = 3 (`010` is also valid for N = 3).

The \\$1\times1\\$ grid

```
0

```

would have output `0` for \\$N = 1\\$.

You can take the input in any convenient reasonable format. e.g. the grid could be a newline separated string of digits, or a multidimensional array, or a list of lists of digits, etc. Leading zeros are allowed in the output if they were part of the grid.

This is , so the shortest code in bytes wins, but I'll also award brownie points (i.e. more likely upvotes) for answers that can show that their algorithm is computationally efficient.

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

*3 bytes thanks to Jakube.*

```
seSs.:RQ.n,L_MdCB.z

```

Try it online.

If we are allowed to print leading zeroes, the code is 18 bytes:

```
eSs.:RQ.n,L_MdCB.z

```

# Answer
> 9 votes
## CJam, ~~39~~ ~~36~~ ~~35~~ 34 bytes

```
qN/)i\[{zW%_}4*]ff{_,@e<ew:i}e_:e>

```

Just quickly, before @Dennis wakes up :P

Try it online.

### Explanation

The basic algorithm is to take all four rotations of the grid and split each row into chunks of length `N` (or the row length, whichever's smaller). Then convert the chunks to ints and take the largest.

```
qN/             Split input by newlines, giving an array of lines
)i\             Drop N from the array and put at bottom
[        ]      Wrap in array...
 {    }4*         Perform 4 times...
  zW%_              Rotate grid anticlockwise and push a copy
                Note that this gives an array of 5 grids [CCW1 CCW2 CCW3 CCW4 CCW4]
ff{         }   For each grid row, mapping with N as an extra parameter...
   _,             Push length of row
     @e<          Take min with N
        ew        Split into chunks
          :i      Convert to ints
e_              Flatten that array
:e>             Take cumulative max

```

# Answer
> 1 votes
# Jelly, 12 bytes

```
ZU$4Ð¡Ẏṡ€ḌFṀ

```

Try it online!

This takes the grid as an \\$W\times H\\$ matrix of single digits.

The TIO Footer simply takes each input list and generates the outputs for each \\$N = 1, 2, ...\\$ up to either \\$W\\$ or \\$H\\$, depending on which is larger

## How it works

```
ZU$4Ð¡Ẏṡ€ḌFṀ - Main link. Takes the matrix M on the left and N on the right
  $          - Group the previous 2 links together as a monad f(M):
Z            -   Transpose
 U           -   Reverse
   4Ð¡       - 4 times, run f(M) on M, updating M each time, and return all 4 results
               This yields M, Mᵀ with rows reversed, Mᵀ and M with rows reversed
      Ẏ      - Tighten into a list of lists
        €    - Over each:
       ṡ     -   Yield all overlapping sublists of length N
         Ḍ   - Convert back to integers
          F  - Flatten
           Ṁ - Maximum

```

# Answer
> 1 votes
# 05AB1E, 13 bytes

```
DÅ|«€ÂJ€Œ˜sùà

```

Try it online! Explanation:

```
D                 # duplicate matrix
 Å|               # get column vectors
   «              # join matrix with its column vectors
    €Â            # append reversed elements
      J           # join arrays into numbers
       €Œ˜        # Get all substrings
          sù      # Keep only those of required length
            à     # Get the largest value

```

# Answer
> 0 votes
# Japt `-h`, ~~13~~ 12 bytes

Takes the matrix as an array of lines. Includes leading `0`s in the output, where applicable.

```
4Æ=z)mãVÃc ñ

```

Try it

```
4Æ=z)mãVÃc ñ    :Implicit input of array U & integer V
4Æ              :Map the range [0,4)
  =             :  Reassign to U
   z            :  Rotate 90° clockwise
    )           :  End reassignment
     m          :  Map
      ãV        :    Substrings of length V
        Ã       :End map
         c      :Flatten
           ñ    :Sort
                :Implicit output of last element

```

# Answer
> 0 votes
# Husk, 13 bytes

```
▲ṁX⁰Σ↑4¡om↔T²

```

Try it online!

The arguments are a bit finicky here.

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


title: How to golf wrap-around assignments?

text:
# Question
Title: How to golf wrap-around assignments?
This is a relatively simple question. I'm trying to golf a Snake game I've written, and I'm trying to work out if there's a way to golf the following conditional assignments which control x and y coordinates of the snake ensuring a wrap around of the play area:

```
if (P<0) {
  P = T-1;
}
if (P>T-1) {
  P = 0;
}
if (Q<0) {
  Q = T-1;
}
if (Q>T-1) {
  Q = 0;
}

```

Is there a simpler way of expressing these, regardless of the value of T?

# Answer
Try the following, it ensures `x` to be inside `[0, n]` (say `n = 5`), only when `x > -n` and `x < 2n`.

```
x = (5 + x) % 5

```

Thanks to ovs!

Try it online!

---

As mentioned by xash in the comments, if you want to make it work for any `x`, then do

```
x = ((x % 5) + 5) % 5

```

Try it online!
> 7 votes

---
Tags: code-golf, tips, javascript
---


title: Happy birthday, Raffaele Cecco!

text:
# Question
Title: Happy birthday, Raffaele Cecco!
Raffaele Cecco is a programmer who produced some of the best video games for the ZX Spectrum computer in the late eighties. Among others, he developed the highly acclaimed Cybernoid and Exolon.

Raffaele is turning 50 on May 10, 2017. This challenge is a small tribute to him, for the happy hours that many of us spent playing those terrific games, and for the motivation they brought.

# The challenge

The purpose is to produce a rectangular marquee inspired by that seen in Cybernoid's main menu screen, but in ASCII art.

Specifically, the string `"Happy birthday Raffaele Cecco "` (note the final space) will be shown rotating along the edges of an 12×5 rectangle, with a constant pause time between snapshots.

For example, assuming the text is displayed clockwise and rotated counter-clockwise (see options below), here are three consecutive snapshots of the rectangular marquee:

```
Happy birthd
           a
o          y
c
ceC eleaffaR

```

then

```
appy birthda
H          y

o          R
cceC eleaffa

```

then

```
ppy birthday
a
H          R
           a
occeC eleaff

```

and so on.

# Rules

No input will be taken. Output will be through STDOUT or equivalent, or in a graphical window.

The output should actually depict the text rotating; that is, each new snapshot should *overwrite* the previous one to give the impression of movement. This can be done by any means, for example, by writing the appropriate number of newlines to effectively clear the screen. It's acceptable if this is valid only for a given screen size; just specify it in the answer.

The following options are accepted:

* Text can be displayed clockwise or counter-clockwise, and can be rotated clockwise or counter-clockwise (the example snapshots above assume clockwise displaying and counter-clockwise rotating).
* Rotation should go on cyclically in an infinite loop (until the program is stopped), and can start at any phase.
* Pause time between snapshots should be approximately constant, but can be freely chosen between 0.1 and 1 s. An initial pause before displaying the first snapshot is acceptable.
* Letters can be upper-case, lower-case or mixed case (as in the example above).
* Leading or trailing blank space is allowed.

Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.

If possible, please provide a gif file showing the output, or a link to test the program.

Shortest code in bytes wins.

# Answer
> 10 votes
# Jelly, ~~74~~  65 bytes

```
“ÆÇÐÑ÷øœ‘Ṭœṗ⁸ṙ©-¤4421œ?U0¦;"⁷,⁶ẋ⁵¤¤ṁ9¤ȮœS.®ß
“9ɲcḟ#%⁴1t(ŀȷUCOw⁾»Ç

```

Windows version running in a 6 line high cp-65001 console.
There is a half a second (plus evaluation) pause between iterations:

### How?

```
“9ɲcḟ#%⁴1t(ŀȷUCOw⁾»Ç - Main link: no arguments
“9ɲcḟ#%⁴1t(ŀȷUCOw⁾»  - compression of [d( Happy)+d( birthday)+d( Raff)+s(aele)+d( Ce)+d(cc)+s(o)] - d=dictionaryLookup, s=stringEncode.
                     -              = " Happy birthday Raffaele Cecco"
                   Ç - call last link (1) as a monad

“ÆÇÐÑ÷øœ‘Ṭœṗ⁸ṙ©-¤4421œ?U0¦;"⁷,⁶ẋ⁵¤¤ṁ9¤ȮœS.®ß - Link 1, rotate, print, recurse: string s
                ¤                            - nilad followed by link(s) as a nilad:
            ⁸                                -   link's left argument (initially s)
               -                             -   literal -1
             ṙ                               -   rotate left -1 (e.g. "blah" -> "hbla")
              ©                              -   copy to register and yield
“ÆÇÐÑ÷øœ‘                                    - literal: [13,14,15,16,28,29,30]
         Ṭ                                   - untruth: [0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1]
          œṗ                                 - partition right at truthy indexes of left
                                             -   chops up the rotated string into 8
                                             -   e.g. [" Happy birth",'d','a','y'," Raffaele Ce",'c','c','o'])
             4421œ?                          - get the 4421st permutation of those items
                                             -   e.g. [" Happy birth",'o','d','c','a','c','y'," Raffaele Ce"]
                         ¦                   - apply to indexes:
                        0                    -   0 (right most)
                       U                     -   upend  (e.g. " Raffaele Ce" -> "eC eleaffaR ")
                                     ¤       - nilad followed by link(s) as a nilad:
                                  ¤          -   nilad followed by link(s) as a nilad:
                                 ¤           -     nilad followed by link(s) as a nilad:
                              ⁶              -       literal space
                                ⁵            -       literal 10
                               ẋ             -       repeat: "          "
                            ⁷                -     literal new line
                             ,               -     pair: ['\n',"          "]
                                     9       -   literal 9
                                    ṁ        -   mould like: ['\n',"          ",'\n',"          ",'\n',"          ",'\n',"          ",'\n']
                           "                 - zip with:
                          ;                  -   concatenation
                                             -     e.g. [" Happy birth\n","o          ","d\n","c          ","a\n","c          ","y\n","eC eleaffaR           ","\n"])
                                      Ȯ      - print and yield
                                         .   - literal 0.5
                                       œS    - after sleeping right seconds yield left
                                          ®  - recall value from register (s rotated by 1)
                                           ß - call this link (1) with the same arity (as a monad)

```

# Answer
> 17 votes
## HTML + ES6, 200 bytes

```
<pre id=o><script>setInterval(_=>o.innerHTML=(f=k=>k--?f(k)+(k<11?s[k]:k>47?s[74-k]:k%12?++k%12?' ':s[10+k/12]+`
`:s[30-k/12]):'')(60,s=s.slice(1)+s[0]),99,s="Happy birthday Raffaele Cecco ")</script>
```

# Answer
> 11 votes
# ZX Spectrum BASIC, 187 bytes

Annoyed that Philip beat me to it by a couple of minutes :-) Numbers like `\{15}` are unprintable control codes - compile with zmakebas if you want to tinker. Note that the full rectangle isn't printed immediately, but it falls into place after the first few frames.

```
1 let a$=" Happy birthday Raffaele Cecco":dim b$(code"\{15}"):dim c$(pi*pi)
3 let b$=a$(sgn pi)+b$:let a$=a$(val"2" to)+a$(sgn pi):print "\{0x16}\{0}\{0}";a$(to code"\{12}")'b$(sgn pi);c$;a$(val"13")'b$(val"2");c$;a$(code"\{14}")'b$(pi);c$;a$(len b$)'b$(val"4" to):go to pi

```

Try it here (online JS-emulated version, press enter to start)... http://jsspeccy.zxdemo.org/cecco/

You can also save four bytes by clearing the screen between frames instead of doing a PRINT AT, but it's too flickery to be worth it...

```
1 let a$=" Happy birthday Raffaele Cecco":dim b$(code"\{15}"):dim c$(pi*pi)
3 let b$=a$(sgn pi)+b$:let a$=a$(val"2" to)+a$(sgn pi):cls:print a$(to code"\{12}")'b$(sgn pi);c$;a$(val"13")'b$(val"2");c$;a$(code"\{14}")'b$(pi);c$;a$(len b$)'b$(val"4" to):go to pi

```

# Answer
> 10 votes
# V, ~~75~~ ~~71~~ 70 bytes

*4 bytes saved thanks to @DJMcMayhem*

```
iHappy birthd
±± a
o±° y
c±±
ceC eleaffaR6ògÓÉ {dêjP2Ljjx1Lp5LxkpGd

```

Here is a TIO link, but note that this will not work on TIO because the program loops infinitely. Try it online!

Since this code contains unprintables, here is a hexdump.

```
00000000: 6948 6170 7079 2062 6972 7468 640a b1b1  iHappy birthd...
00000010: 2061 0a6f b1b0 2079 0a63 b1b1 200a 6365   a.o.. y.c.. .ce
00000020: 4320 656c 6561 6666 6152 1b36 f267 d3c9  C eleaffaR.6.g..
00000030: 207b 64ea 6a50 324c 166a 6a78 314c 7035   {d.jP2L.jjx1Lp5
00000040: 4c78 6b70 4764                           LxkpGd

```

The sleep time is 500 milliseconds.

# Answer
> 9 votes
## SVG(HTML5), 267 bytes

```
<svg width=200 height=90><defs><path id=p d=M40,20h120v50h-120v-50h120v50h-120v-50></defs><text font-size="19" font-family="monospace"><textPath xlink:href=#p>Happy birthday Raffaele Cecco<animate attributeName=startOffset from=340 to=0 dur=5s repeatCount=indefinite>
```

Well, it *is* rectangular, and it *is* a marquee, and it *is* ASCII text...

# Answer
> 9 votes
# ZX Spectrum BASIC, 274 bytes

Well, someone had to do it. Pedants may wish to disqualify this for being too slow and not having a pause between animations, but I'm claiming a special case here :-)

```
10 LET m$=" Happy birthday Raffaele Cecco": LET o=0: LET l=LEN m$: LET f=4: LET t=12: LET a=t+f: LET b=27
20 FOR j=SGN PI TO l: LET i=j+o: IF i>l THEN LET i=i-l
40 LET x=(i-SGN PI AND i<=t)+(11 AND i>t AND i<=a)+(b-i AND i>a AND i<=b)
50 LET y=(i-t AND i>t AND i<=a)+(f AND i>a AND i<=b)+(b+f-i AND i>b): PRINT AT y,x;m$(j): NEXT j
80 LET o=o+SGN PI: IF o>=l THEN LET o=o-l
90 GO TO t

```

Not very golfed either. 274 bytes is the number of bytes saved by the Spectrum to tape when saving this program.

# Answer
> 7 votes
# PHP, 184 bytes

```
for($r=" ";++$i;sleep(print chunk_split(str_pad($r,96,"
",0),12)),$r=$k="0")for(;$c="ABCDEFGHIJKWco{zyxwvutsrqpdXL@"[$k];)$r[ord($c)-64]="Happy Birthday Raffaele Cecco "[($i+$k++)%30];

```

prints 39 newlines to clear the screen; run with `-nr`.
The actual pause is 1 second; but I sped up the gif.

**ungolfed**

```
$p = "ABCDEFGHIJKWco{zyxwvutsrqpdXL@";  # (positions for characters)+64 to ASCII
$t = "Happy Birthday Raffaele Cecco ";  # string to rotate
for($r=" ";                     # init result to string
    ++$i;                       # infinite loop
    $r=$k="0")                      # 6. reset $r and $k
{
    for(;$c=$p[$k];)                # 1. loop through positions
        $r[ord($c)-64]=                 # set position in result
        $t[($i+$k++)%30];               # to character in string
    sleep(                          # 5. wait 1 second
        print                       # 4. print
            chunk_split(
            str_pad($r,96,"\n",0)   # 2. pad to 96 chars (prepend 36 newlines)
            ,12)                    # 3. insert newline every 12 characters
        );
}

```

# Answer
> 6 votes
# Python 2, ~~230~~ 184 bytes

```
import time
s='Happy birthday Raffaele Cecco '*2
i=0
while[time.sleep(1)]:print'\n'*30+'\n'.join([s[i:i+12]]+[s[i-n]+' '*10+s[i+11+n]for n in 1,2,3]+[s[(i+15)%30:][11::-1]]);i+=1;i%=30

```

---

Try it at repl.it

# Answer
> 5 votes
# Python 2, 218 200 190 181 176 bytes

```
import time;f='Happy birthday Raffaele Cecco '
while[time.sleep(1)]:v=f[::-1];print'\n'*90,f[:12],''.join('\n'+a+' '*10+b for a,b in zip(v[:3],f[12:16])),'\n',v[3:15];f=f[1:]+f[0]

```

-18 bytes by removing `str` formatting

-10 bytes, thanks to @Uriel and @ElPedro suggestions

-9 bytes by removing negative indexing

-5 bytes by storing reversed `f` as `v` and `while` condition

repl.it

# Answer
> 5 votes
# Python 3, 160 bytes

```
import time;s="Happy_birthday_Raffaele_Cecco_"
while[time.sleep(1)]:print(s[:12]+'\n%s%%11s'*3%(*s[:-4:-1],)%(*s[12:15],)+'\n'+s[-4:14:-1]+'\n'*30);s=s[1:]+s[0]

```

Try it online! (No animation)

# Answer
> 4 votes
# 05AB1E, 43 bytes

```
[Ž-∊13в.•:=r}ƒyp$γ•™“ŽØ¢© ÿ“.ªN._Ž9¦S.Λ,т.W

```

What better time to answer a birthday related challenge than on your own birthday. ;)

Outputs and rotates in a similar matter as the challenge description; sleeps for 100 ms in between iterations (could alternatively sleep for 255 ms, 256 ms, or 1 second for the same byte-count by replacing the `т` with , , or  respectively). Prints each iteration as a loose output (so without clearing the console and overwriting).

Try the first \\$n\\$ iterations online (without sleep).
Or as gif in my local console:

**Explanation:**

```
[                        # Loop indefinitely:
 Ž-∊                     #  Push compressed integer 27370
    13в                  #  Convert it to base-13 as list: [12,5,12,5]
 .•:=r}ƒyp$γ•            #  Push compressed string "raffaele cecco "
             ™           #  Titlecase the words: "Raffaele Cecco "
              “ŽØ¢© ÿ“   #  Push compressed string "happy birthday ÿ",
                         #  where `ÿ` is automatically filled with the top of the stack:
                         #   "happy birthday Raffaele Cecco "
                      .ª #  Sentence capitalize it, leaving existing caps intact:
                         #   "Happy birthday Raffaele Cecco "
  N._                    #  Rotate the characters in this string the 0-based loop-index
                         #  amount of times towards the left
 Ž9¦                     #  Push compressed integer 2460
    S                    #  Convert it to a list of digits: [2,4,6,0]
 .Λ                      #  Use the Canvas builtin with these three options
   ,                     #  Pop and print it with trailing newline
 т.W                     #  Sleep for 100 milliseconds

```

See this 05AB1E tip of mine to understand why `“ŽØ¢© ÿ“` is `"happy birthday ÿ"`; `.•:=r}ƒyp$γ•` is `"raffaele cecco "`; `Ž-∊` is `27370`; `Ž9¦` is `2460`; and `Ž-∊13в` is `[12,5,12,5]`.

As for the Canvas builtin: it takes three arguments to draw a shape:

* Character/string to draw: the potentially rotated `"Happy birthday Raffaele Cecco "` in this case
* Length of the lines we'll draw: the list `[12,5,12,5]`
* The direction to draw in: `[2,4,6,0]`. The digits in the range \[0,7\] each represent a certain direction:

```
7   0   1
  ↖ ↑ ↗
6 ← X → 2
  ↙ ↓ ↘
5   4   3

```

So the `[2,4,6,0]` in this case translates to the directions \\$\[→,↓,←,↑\]\\$.

here a step-by-step explanation of the output for the initial state:

Step 1: Draw 12 characters (`"Happy birthd"`) in direction `2→`:

```
Happy birthd

```

Step 2: Draw 5-1 characters (`"ay R"`) in direction `4↓`:

```
Happy birthd
           a
           y

           R

```

Step 3: Draw 12-1 characters (`"ceC eleaffa"`) in direction `6←`:

```
Happy birthd
           a
           y

ceC eleaffaR

```

Step 4: Draw 5-1 characters (`"co H"`) in direction `0↑`:

```
Happy birthd
           a
o          y
c
ceC eleaffaR

```

See this 05AB1E tip of mine for an in-depth explanation of the Canvas builtin.

# Answer
> 3 votes
# Python 2, ~~182~~ ~~179~~ ~~173~~ 160 bytes

```
i="Happy birthday Raffaele Cecco "
while[s for s in i*18**4]:print'\n'*99,'\n'.join([i[:12]]+[i[-z]+' '*10+i[11+z]for z in 1,2,3]+[i[15:-3][::-1]]);i=i[1:]+i[0]

```

Try it at repl.it

Doesn't work on TIO so my first attempt at using repl.it

**Edit** Using a "time-wasting" loop to count to 1000000 gives a consistent delay of *between 0.1 and 1s* on my machine and on repl.it and saves importing `time`. I guess if you ran it on an old 286 computer with 64MB RAM it may go over the 1 second but I'm pretty sure that's not going to happen. If it does then simply reduce the 1000000 and save me a couple of bytes :-)

**Edit 2** -6 for remembering that list comprehensions in Python 2 leak the last value of `s` so I can use it later and also remembering that pretty well anything other than 0 and "" is truthy. Bugs or features? Don't care. It's saved me 6 bytes :-)

**Edit 3** Another 13 by revering the rotation and by using a list comprehension for the middle rows inside the join and changing `3000000` to `40**4`. Thanks to @FelixDombek for the last one. Had to lose my list comprehension trick though.

# Answer
> 3 votes
# Ruby + GNU Core Utils, 136 bytes

```
s='Happy birthday Raffaele Cecco '
loop{puts`clear`+s[0,12],(0..2).map{|i|s[~i]+' '*10+s[12+i]},s[15,12].reverse
s=s[1,29]+s[0];sleep 1}

```

# Answer
> 2 votes
## ZX81 Z80 machine code, ~~158~~ 130 bytes

OK so it has a lot of bytes until it is assembled but then it drops to 130 bytes. Not sure if that breaks any rules? Its my first post and only as a guest.

The program uses 'brute force' to display the message rather than clever function use as can be seen from the way it has separate code chunks for the top line, the right hand vertical, the bottom line and the left hand vertical. The animation is achieved by rotating the contents of the message and then just displaying it after a short delay which should be pretty much exactly 0.2 seconds as it waits for 10 frames out of a rate of 50 (for UK spec Zeddys anyway).

I have to credit kmurta for the concept of rotating the message to get the animation - that saved 28 bytes!!!

```
main
  ld hl,happyBirthday           ;load the address of the message
  ld de,(D_FILE)                ;load the base of screen memory
  inc de                        ;increase it by one to bypass the $76
  ld bc,12                  ;ready for 12 loops
  ldir                      ;transfer HL to DE 12 times and increase both accordingly
  ex de,hl                  ;put HL into DE (HL was the message position)
  ld b,4                        ;prepare to loop 4 times
  dec hl                        ;decrease HL (screen location) by 1
rightVertical
  push de                       ;save the character position
  ld de,13                  ;load 13 (for the next line)
  add hl,de                 ;add to HL
  pop de                        ;get the message position back
  ld a,(de)                 ;load the character into A
  ld (hl),a                 ;save it to HL
  inc de                        ;increase the character position
  djnz rightVertical            ;repeat until B = 0
  dec hl                        ;decrease HL (screen location) by 1 to step back from the $76 char
  ld b,11                       ;prepare for 11 loops
lastLine
  ld a,(de)                 ;load the current character into A
  ld (hl),a                 ;save to the screen
  dec hl                        ;decrease the screen position (as we are going backwards)
  inc de                        ;increase character position
  djnz lastLine             ;repeat until B = 0
  ld b,3                        ;get ready for the left vertical
  inc hl                        ;increase the screen position by 1 as we have gone 1 too far to the left and wrapped to the line above
leftVertical
  push de                       ;save the character position
  ld de,13                  ;load 13 (for the next line)
  sbc hl,de                 ;subtract it to move up a line in memory
  pop de                        ;get the character pos back
  ld a,(de)                 ;load the character
  ld (hl),a                 ;save it to the screen
  inc de                        ;next character
  djnz leftVertical         ;repeat until B = 0
delayCode
  ld   hl,FRAMES                ;fetch timer
  ld   a,(hl)                 ;load into A
  sub  10                       ;wait 10 full frames (0.2 of a second)
delayLoop
  cp  (hl)                  ;compare HL to 0
  jr   nz,delayLoop         ;if not 0 then repeat until it is
shuffleMessage
  ld a, (happyBirthday)     ;load the first character of the message
  push af                       ;save the first character of the message
  ld hl, happyBirthday      ;load the address of the message
  inc hl                        ;increase by one to get the second char
  ld de, happyBirthday      ;load the start of the message
  ld bc, 29                 ;number of times to loop
  ldir                      ;load HL (char 2) into DE (char 1) and repeat
  pop af                        ;get char 1 back
  ld (de),a                 ;out it at the end of the string
  jr main                       ;repeat
happyBirthday
    DEFB    _H,_A,_P,_P,_Y,__,_B,_I,_R,_T,_H,_D,_A,_Y,__,_R,_A,_F,_F,_A,_E,_L,_E,__,_C,_E,_C,_C,_O,__

```

Sorry I can't post a link to it running as it is a compiled program in the .P format for EightyOne (or other emulators) or an actual Zeddy if you have a ZXPand or similar to load it.

The .P can be downloaded at http://www.sinclairzxworld.com/viewtopic.php?f=11&t=2376&p=24988#p24988

---
Tags: code-golf, string, ascii-art
---


title: Area of the triangle

text:
# Question
Title: Area of the triangle
Another easy challenge for you.

## Your task

Write a program or function that takes the input, which contains 3 pairs of x- and y-coordinates and calculates the area of the triangle formed inside them. For those who can't remember how to calculate it, you can find it here.

### Example:

```
1,2,4,2,3,7       # input as x1,y1,x2,y2,x3,y3
7.5               # output

```

See it at Wolfram Alpha

Some considerations:

* The input will be six base 10 positive integers.
* You may assume the input is **in any reasonable format**.
* The points will always form a valid triangle.
* You can assume the input is already stored in a variable such as `t`.
* The shortest code in bytes wins!

**Edit: To avoid any confusion I've simplificated how the input should be dealt without jeopardizing any of the current codes.**

**Remember that the your program/function must output a valid area, so it can't give a negative number as output**

# Answer
> 15 votes
# CJam, ~~18~~ 16 bytes

```
T(f.-~(+.*:-z.5*

```

Try it online in the CJam interpreter.

### Idea

As mentioned on Wikipedia, the area of the triangle `[[0 0] [x y] [z w]]` can be calculated as `|det([[x y] [z w]])| / 2 = |xw-yz| / 2`.

For a generic triangle `[[a b] [c d] [e f]]`, we can translate its first vertex to the origin, thus obtaining the triangle `[[0 0] [c-a d-b] [e-a f-b]]`, whose area can be calculated by the above formula.

### Code

```
T                  e# Push T.
                   e# [[a b] [c d] [e f]]
   (               e# Shift out the first pair.
                   e# [[c d] [e f]] [a b]
    f.-            e# For [c d] and [e f], perform vectorized
                   e# subtraction with [a b].
                   e# [[c-a d-b] [e-a f-b]]
       ~           e# Dump the array on the stack.
                   e# [c-a d-b] [e-a f-b]
        (+         e# Shift and append. Rotates the second array.
                   e# [c-a d-b] [f-b e-a]
          .*       e# Vectorized product.
                   e# [(c-a)(f-b) (d-b)(e-a)]
            :-     e# Reduce by subtraction.
                   e# (c-a)(f-b) - (d-b)(e-a)
              z    e# Apply absolute value.
                   e# |(c-a)(f-b) - (d-b)(e-a)|
               .5* e# Multiply by 0.5.
                   e# |(c-a)(f-b) - (d-b)(e-a)| / 2

```

# Answer
> 10 votes
# JavaScript (ES6) 42 ~~.44.~~

**Edit** Input format changed, I can save 2 bytes

An anonymous function that take the array as a parameter and returns the calculated value.

```
(a,b,c,d,e,f)=>(a*(d-f)+c*(f-b)+e*(b-d))/2

```

Test running the snippet below in an EcmaScript 6 compliant browser.

```
f=(a,b,c,d,e,f)=>(a*(d-f)+c*(f-b)+e*(b-d))/2

function test()
{
  var v=I.value.match(/\d+/g)
  I.value = v
  R.innerHTML=f(...v)
}
```

```
<input id=I onchange="test()"><button onclick="test()">-></button><span id=R></span>
```

# Answer
> 10 votes
# Mathematica, 27 bytes

```
Area@Polygon@Partition[t,2]

```

# Answer
> 8 votes
# Julia, 32 bytes

```
abs(det(t[1:2].-t[[3 5;4 6]]))/2

```

Constructs a matrix of the appropriate terms of a cross product, uses `det` to get the resulting value, takes absolute value to deal with negatives, and then divides by 2 because it's a triangle and not a parallelogram.

# Answer
> 7 votes
# Matlab/Octave, 26 bytes

I did not know about this built in so far=)

```
polyarea(t(1:2:5),t(2:2:6))

```

# Answer
> 6 votes
# Java, ~~79~~ 88 bytes

```
float f(int[]a){return Math.abs(a[0]*(a[3]-a[5])+a[2]*(a[5]-a[1])+a[4]*(a[1]-a[3]))/2f;}

```

Just uses the basic formula, nothing special.

Edit: Forgot to take the absolute value :(

# Answer
> 5 votes
## Minkolang 0.8, 34 bytes

```
ndndn0g-n1g-n0g-n0g-1R*1R*-$~2$:N.

```

Anyone want some egg-`n0g`?

### Explanation

Very straightforward. Uses the formula `|(x2-x1)(y3-y1) - (x3-x1)(y2-y1)|/2`.

```
nd      x1, x1
nd      x1, x1, y1, y1
n0g-    x1, y1, y1, x2-x1
n1g-    x1, y1, x2-x1, y2-y1
n0g-    y1, x2-x1, y2-y1, x3-x1
n0g-    x2-x1, y2-y1, x3-x1, y3-y1
1R*     y3-y1, x2-x1, (y2-y1)(x3-x1)
1R*     (y2-y1)(x3-x1), (y3-y1)(x2-x1)
-       (y2-y1)(x3-x1) - (y3-y1)(x2-x1)
$~      |(y2-y1)(x3-x1) - (y3-y1)(x2-x1)|
2$:     |(y2-y1)(x3-x1) - (y3-y1)(x2-x1)|/2 (float division)
N.      Output as integer and quit.

```

# Answer
> 3 votes
# PHP – 68 ~~88~~ ~~89~~ bytes

Thanks to Martjin for some great pointers!

```
<?=.5*abs(($t[1]-$t[5])*($t[4]-$t[2])-($t[1]-$t[3])*($t[6]-$t[2]))?>

```

To use it, create a file `area.php` with this content, the extra line meets the *assume the data is saved in a variable `t`* part of the specs, and the ␍ at the end adds a carriage return so the output is nice and separated:

```
<?php $t = $argv; ?>
<?=.5*abs(($t[1]-$t[5])*($t[4]-$t[2])-($t[1]-$t[3])*($t[6]-$t[2]))?>
␍

```

Then provide the coordinates on the command line as `x₁ y₁ x₂ y₂ x₃ y₃`, e.g.

```
$ php area.php 1 2 4 2 3 7
7.5

```

# Answer
> 3 votes
# JayScript, 58 bytes

Declares an anonymous function:

```
function(a,b,c,d,e,f){return (a*(d-f)+c*(f-b)+e*(b-d))/2};

```

Example:

```
var nFunct = function(a,b,c,d,e,f){return (a*(d-f)+c*(f-b)+e*(b-d))/2};
print(nFunct(1,2,4,2,3,7));

```

# Answer
> 3 votes
# Ruby, 45

```
->a,b,p,q,x,y{((a-x)*(q-y)-(p-x)*(b-y)).abs/2}

```

# Answer
> 2 votes
# Pyth, ~~34~~ 30 bytes

```
KCcQ2c.asm*@hKd-@eKhd@eKtdU3 2

```

Try it online.

Works by calculating abs(a\*(d-f) + c\*(f-b) + e\*(b-d))/2 from input a,b,c,d,e,f.

# Answer
> 2 votes
# AWK – 51 ~~42~~ bytes

AWK has no built-in `abs` so using `sqrt(x^2)` to substitute.

```
{print sqrt((($1-$5)*($4-$2)-($1-$3)*($6-$2))^2)/2}

```

Save as `area.awk` and use as `echo x₁ y₁ x₂ y₂ x₃ y₃ | awk -f area.awk`, e.g.

```
$ echo 1 2 4 2 3 7 | awk -f area.awk
7.5

```

# Answer
> 2 votes
# Python 2, ~~48~~ ~~47~~ 50 bytes

Very simple; follows the standard equation:

```
lambda a,b,c,d,e,f:abs(a*(d-f)+c*(f-b)+e*(b-d))/2.

```

The other, similarly simple approaches are longer:

```
def a(a,b,c,d,e,f):return abs(a*(d-f)+c*(f-b)+e*(b-d))/2. # 57
lambda t:abs(t[0]*(t[3]-t[5])+t[2]*(t[5]-t[1])+t[4]*(t[1]-t[3]))/2. # 67
def a(t):return abs(t[0]*(t[3]-t[5])+t[2]*(t[5]-t[1])+t[4]*(t[1]-t[3]))/2. # 74

```

Python's access to a determinate function is through numpy.

Thanks to muddyfish for 1 byte and xnor for catching an error.

# Answer
> 2 votes
## PHP, 77

Based on @Yimin Rong's answer, I felt I could improve upon it by a few bytes by using `list()` rather than straight `$argv` to abbreviate some variables. Also `echo` doesn't need a space if there is delimiter between echo and the thing being echoed.

`echo$variable;`, `echo(4+2);`, and `echo'some string';` are equally valid whereas `echofunction($variable)` confuses PHP.

On the other hand, I also added `abs()` to be mathematically accurate, since some combinations of vertices yielded "negative area"

```
list($t,$a,$b,$c,$d,$e,$f)=$argv;echo.5*abs(($a-$e)*($d-$b)-($a-$c)*($f-$b));

```

You can run it via CLI

```
php -r "list($t,$a,$b,$c,$d,$e,$f)=$argv;echo.5*abs(($a-$e)*($d-$b)-($a-$c)*($f-$b));" 1 2 4 2 3 7
7.5

```

# Answer
> 2 votes
# R, 37 bytes

```
cat(abs(det(rbind(matrix(t,2),1))/2))

```

Converts the vector of coordinates into a matrix and tacks on a row of 1's.
Calculates the determinant and divides by 2.
Returns the absolute result. If the order was always clockwise the `abs` would not be required.

```
> t = c(1,2,4,2,3,7)
> cat(det(rbind(matrix(t,2),1))/2)
7.5

```

# Answer
> 1 votes
# PowerShell, 70 Bytes

```
[math]::Abs(($t[0]-$t[4])*($t[3]-$t[1])-($t[0]-$t[2])*($t[5]-$t[1]))/2

```

Uses the same standard formula as other solutions. Per the question, assumes the array is pre-populated, e.g. `$t=(1,2,4,2,3,7)`. But *ooof*, does the `$` and `[]` syntax kill this one...

# Answer
> 1 votes
## dc, 52 bytes

Assumes the input is in register `t` as: `x1 y1 x2 y2 x3 y3` with `x1` at the top of `t`'s stack.

```
1kLtLtsaLtsbLtdscLtltrlalclbltla-*sd-*se-*leld++2/p

```

`1 2 4 2 3 7stStStStStSt #puts coordinates into register t (closest thing dc has to variables)
1kLtLtsaLtsbLtdscLtltrlalclbltla-*sd-*se-*leld++2/p
7.5`

This uses the following formula for area:

`(x1(y2-y3) + x2(y3-y1) + x3(y1 - y2))/2`

And for a quick breakdown of the process:

* `1k Lt Lt sa Lt sb Lt d sc Lt lt r`: set decimal precision to 1 place, move parts of the stack in `t` to the main stack and move various parts of the main stack to other registers for storage (`d` duplicates the top of main stack, `r` reverses the top two elements of main stack, `L/l` move/copy from the given register to main, `s` moves top of main stack to the given register)

Main: `y3 x3 y2 x1`

a: `y1`, b: `x2`, c: `y2`, t: `y3`
* `la lc lb lt la`: copy the top of the stacks in registers `a`, `c`, `b`, `t`, and `a` to the main stack in that order

Main: `y1 y3 x2 y2 y1 y3 x3 y2 x1`

a: `y1`, b: `x2`, c: `y2`, t: `y3`
* `- * sd`: calculate `((y3-y1)*x2)` and put result in `d` (registers `a`, `b`, `c`, and `t` are no longer used so I'll drop them from the list of stacks now)

Main: `y2 y1 y3 x3 y2 x1`

d:`((y3-y1)*x2)`
* `- * se - *`: compute `((y1-y2)*y3)` and `((y2-x3)*x1)`; store the former in `e` and leave the latter on the main stack

Main: `((y2-x3)*x1)`

d:`((y3-y1)*x2)`, e:`((y1-y2)*y3)`
* `le ld + +`: copy top of register `e` and `d` to the main stack, calculate sum of top 2 stack values (pushing result back to main stack) twice

Main: `(((y3-y1)*x2)+((y1-y2)*y3)+((y2-x3)*x1))`

d:`((y3-y1)*x2)`, e:`((y1-y2)*y3)`
* `2 /`: push 2 onto main stack, divide 2nd values on stack by the 1st (`d` and `e` are no longer used, dropping them from list of stacks)

Main: `(((y3-y1)*x2)+((y1-y2)*y3)+((y2-x3)*x1))/2`

Rearranging the value on the stack we can see it's equivalent to the formula at the top of this explanation: `(x1(y2-y3) + x2(y3-y1) + x3(y1 - y2))/2`

* `p`: Print top of main stack to output.

# Answer
> 0 votes
# Jelly, 6 bytes

```
_ḢÆḊHA

```

Try it online!

Takes input as 3 pairs `[a,b],[c,d],[e,f]` as Jelly has no concept of variables

## How it works

This implements the method outlined on Wikipedia that Dennis' answer uses, in that, the area of a triangle \\$(0,0), (x,y), (v,w)\\$ is

$$\frac12\left|\det\left\[\begin{matrix} x & y \\ v & w \end{matrix}\right\]\right|$$

and that, for an arbitrary triple of points \\$(a,b),(c,d),(e,f)\\$, we can translate them to form a triangle with a corner on the origin: \\$(0,0),(c-a,d-b),(e-a,f-b)\\$, so the area is

$$\frac12\left|\det\left\[\begin{matrix} c-a & d-b \\ e-a & f-b \end{matrix}\right\]\right|$$

```
_ḢÆḊHA - Main link. Takes [[a, b], [c, d], [e, f]] on the left
 Ḣ     - Remove [a,b] and yield it
_      - Vectorised subtraction from each of [[c, d], [e, f]] which yields
         [[c-a, d-b], [e-a, f-b]]
  ÆḊ   - Determinant
    H  - Halve
     A - Absolute value

```

---
Tags: code-golf, geometry
---


title: Rearrangement Inequality

text:
# Question
Title: Rearrangement Inequality
## Background

The **Rearrangement Inequality** is an inequality that is based on rearranging numbers. If I have two lists of numbers of the same length, x0, x1, x2...xn-1 and y0, y1, y2...yn-1 of the same length, where I am allowed to rearrange the numbers in the list, a way to maximize the sum x0y0+x1y1+x2y2+...+xn-1yn-1 is to sort the 2 lists in non-decreasing order.

Read the Wikipedia article here.

## Task

You would write a program that takes input from STDIN or a function that accepts 2 arrays (or related containers) of numbers (which are of the same length).

Assuming you write a function which accepts 2 arrays (a and b), you are going to find the number of ways you can rearrange the numbers in the second array (b) to maximize:

```
a[0]*b[0]+a[1]*b[1]+a[2]*b[2]+...+a[n-1]*b[n-1]

```

In this case, if the array b is \[10, 21, 22, 33, 34\] (indices for clarity),

\[10, 21, 22, 33, 34\],

\[10, 21, 22, 34, 33\], (swap the two 3's)

\[10, 22, 21, 33, 34\] (swap the two 2's)

\[10, 22, 21, 34, 33\] (swap the two 3's and swap the two 2's)

are considered different arrangements. The original array, itself, also counts as a possible rearrangement if it also maximizes the sum.

For STDIN input, you may assume that the length of the arrays is provided before the arrays (please state so that you use it), or that the arrays are provided on different lines (also please state).

Here are the 4 possible inputs (for convenience):

```
5 1 1 2 2 2 1 2 2 3 3 (length before arrays)

1 1 2 2 2 1 2 2 3 3 (the 2 arrays, concatenated)

1 1 2 2 2
1 2 2 3 3 (the 2 arrays on different lines)

5
1 1 2 2 2
1 2 2 3 3 (length before arrays and the 2 arrays on different lines)

```

For output, you are allowed to return the answer (if you write a function) or print the answer to STDOUT. You may choose to output the answer mod 109+7 (from 0 to 109+6) if it is more convenient.

## Test Cases (and explanation):

```
[1 1 2 2 2] [1 2 2 3 3] => 24

```

The first 2 entries have to be 1 and 2. The last 3 entries are 2, 3 and 3. There are 2 ways to arrange the 2's between the first 2 entries and the last 2 entries. Among the first 2 entries, there are 2 ways to rearrange them. Among the last 2 entries, there are 6 ways to rearrange them.

```
[1 2 3 4 5] [6 7 8 9 10] => 1

```

There is only 1 way, which is the arrangement given in the arrays.

```
[1 1 ... 1 1] [1 1 ... 1 1] (10000 numbers) => 10000! or 531950728

```

Every possible permutation of the second array is valid.

Dennis' Testcase: Pastebin =\> 583159312 (mod 1000000007)

## Scoring:

This is code-golf, so shortest answer wins.

In case of tie, ties will be broken by time of submission, favouring the earlier submission.

## Take note:

The containers may be unsorted.

The integers in the containers may be zero or negative.

The program has to run fast enough (at most an hour) for modestly sized arrays (around 10000 in length).

Inspired by this question on Mathematics Stack Exchange.

# Answer
> 4 votes
# CJam, ~~30~~ 26 bytes

```
q~](/:$_za+{e`0f=:m!:*}//*

```

Try it online in the CJam interpreter.

It completes this test case in less than a second:

```
$ time cjam <(echo 'q~](/:$_za+{e`0f=:m!:*}%)\:*\/N') < test-large.in | md5sum
5801bbf8ed0f4e43284f7ec2206fd3ff  -

real    0m0.308s
user    0m0.667s
sys     0m0.044s

```

Running it in the online interpreter should take less than 10 seconds.

### Algorithm

The result does not depend on the order of **A**, so we can assume it to be sorted. This means that **B** must also be sorted to attain the maximal dot product.

Now, if **r1, … rn** are the length of the runs of the sorted **A**, there are **∏rk!** different rearrangements of the elements of **A** that still result in ascending order.

Likewise, if **s1, … sn** are the length of the runs of the sorted **B**, there are **∏sk!** different rearrangements of the elements of **B** that still result in ascending order.

However, this counts all pairings multiple times. If we take the pairs of of the corresponding elements of sorted **A** and sorted **B** and define **t1, … tn** as the length of the runs of the resulting array, **∏tk!** is the aforementioned multiplier.

Thus, the desired result is **(∏rk!) × (∏sk!) ÷ (∏tk!)**.

### Code

```
 q~                          Read and evaluate all input.
   ]                         Wrap the resulting integers in an array.
    (                        Shift out the first (length).
     /                       Split the remainder into chunks of that length.
      :$                     Sort each chunk.
        _z                   Push a copy and transpose rows with columns.
                             This pushes the array of corresponding pairs.
          a+                 Wrap in array and concatenate (append).
            {          }/    For A, B, and zip(A,B):
             e`                Perform run-length encoding.
               0f=             Select the runs.
                  :m!          Apply factorial to each.
                     :*        Reduce by multiplication.
                         /   Divide the second result by the third.
                          *  Multiply the quotient with the first result.

```

# Answer
> 6 votes
# Pyth, ~~29~~ 28 bytes

```
M/*FPJm*F.!MhMrd8aFCB,SGSHeJ

```

Try it online in the Pyth Compiler.

### Algorithm

The result does not depend on the order of **A**, so we can assume it to be sorted. This means that **B** must also be sorted to attain the maximal dot product.

Now, if **r1, … rn** are the length of the runs of the sorted **A**, there are **∏rk!** different rearrangements of the elements of **A** that still result in ascending order.

Likewise, if **s1, … sn** are the length of the runs of the sorted **B**, there are **∏sk!** different rearrangements of the elements of **B** that still result in ascending order.

However, this counts all pairings multiple times. If we take the pairs of of the corresponding elements of sorted **A** and sorted **B** and define **t1, … tn** as the length of the runs of the resulting array, **∏tk!** is the aforementioned multiplier.

Thus, the desired result is **(∏rk!) × (∏sk!) ÷ (∏tk!)**.

### Code

```
M/*FPJm*F.!MhMrd8aFCB,SGSHeJ

M                             Define g(G,H):
                      SGSH      Sort G and H.
                     ,          For the pair of the results.
                   CB           Bifurcated zip (C).
                                This returns [[SG, SH], zip([SG, SH])].
                 aF             Reduce by appending.
                                This returns [SG, SH, zip([SG, SH])].
      m                         Map; for each d in the resulting array:
              rd8                 Perform run-length encoding on d.
            hM                    Mapped "head". This returns the lengths.
         .!M                      Mapped factorial.
       *F                         Reduce by multiplication.
     J                          Save the result in J.
    P                           Discard the last element.
  *F                            Reduce by multiplication.
 /
                          eJ    Divide the product by the last element of J.
                                Return the result of the division.

```

### Verification

I've pseudo-randomly generated 100 test cases of length 6, which I've solved with the above code and this brute-force approach:

```
Ml.Ms*VGZ.pH

M             Define g(G,H) (or n(G,H) on second use):
         .pH    Compute all permutations of H.
  .M            Filter .pH on the maximal value of the following;
                 for each Z in .pH:
     *VGZ         Compute the vectorized product of G and Z.
    s             Add the products.
                  This computes the dot product of G and Z.
 l              Return the length of the resulting array.

```

These were the results:

```
$ cat test.in
6,9,4,6,8,4,5,6,5,0,8,2
0,7,7,6,1,6,1,7,3,3,8,0
3,6,0,0,6,3,8,2,8,3,1,1
2,3,0,4,0,6,3,4,5,8,2,4
9,1,1,2,2,8,8,1,7,4,9,8
8,3,1,1,9,0,2,8,3,4,9,5
2,0,0,7,7,8,9,2,0,6,7,7
0,7,4,2,2,8,6,5,0,5,4,9
2,7,7,5,5,6,8,8,0,5,6,3
1,7,2,7,7,9,9,2,9,2,9,8
7,2,8,9,9,0,7,4,6,2,5,3
0,1,9,2,9,2,9,5,7,4,5,6
8,4,2,8,8,8,9,2,5,4,6,7
5,2,8,1,9,7,4,4,3,3,0,0
9,3,6,2,5,5,2,4,6,8,9,3
4,2,0,6,2,3,5,3,6,3,1,4
4,8,5,2,5,0,5,1,2,5,9,5
6,8,4,4,9,5,9,5,4,2,8,7
8,9,8,1,2,2,9,0,5,6,4,9
4,7,6,8,0,3,7,7,3,9,8,6
7,5,5,6,3,9,3,8,8,4,8,0
3,8,1,8,5,6,6,7,2,8,5,3
0,9,8,0,8,3,0,3,5,9,5,6
4,2,7,7,5,8,4,2,6,4,9,4
3,5,0,8,2,5,8,7,3,4,5,5
7,7,7,0,8,0,9,8,1,4,8,6
3,9,7,7,4,9,2,5,9,7,9,4
4,5,5,5,0,7,3,4,0,1,8,2
7,4,4,2,5,1,7,4,7,1,9,1
0,6,2,5,4,5,1,8,0,8,9,9
3,8,5,3,2,1,1,2,2,2,8,4
6,1,9,1,8,7,5,6,9,2,8,8
6,2,6,6,6,0,2,7,8,6,8,2
0,7,1,4,5,5,3,4,4,0,0,2
6,0,1,5,5,4,8,5,5,2,1,6
2,6,3,0,7,4,3,6,0,5,4,9
1,4,8,0,5,1,3,2,9,2,6,5
2,7,9,9,5,0,1,5,6,8,4,6
4,0,1,3,4,3,6,9,1,2,7,1
6,5,4,7,8,8,6,2,3,4,1,2
0,3,6,3,4,0,1,4,5,5,5,7
5,4,7,0,1,3,3,0,2,1,0,8
8,6,6,1,6,6,2,2,8,3,2,2
7,1,3,9,7,4,6,6,3,1,5,8
4,8,3,3,9,1,3,4,1,3,0,6
1,4,0,7,4,9,8,4,2,1,0,3
0,4,1,6,4,4,4,7,5,1,4,2
0,0,4,4,9,6,7,2,7,7,5,4
9,0,5,5,0,8,8,9,5,9,5,5
5,7,0,4,2,7,6,1,1,1,9,1
3,1,7,5,0,3,1,4,0,9,0,3
4,4,5,7,9,5,0,3,7,4,7,5
7,9,7,3,0,8,4,0,0,3,1,0
2,4,4,3,1,2,5,2,9,0,8,5
4,8,7,3,0,0,9,3,7,3,0,6
8,9,1,0,7,7,6,0,3,1,8,9
8,3,1,7,3,3,6,1,1,7,6,5
6,5,6,3,3,0,0,5,5,0,6,7
2,4,3,9,7,6,7,6,5,6,2,0
4,8,5,1,8,4,4,3,4,5,2,5
7,5,0,4,6,9,5,0,5,7,5,5
4,8,9,5,5,2,3,1,9,7,7,4
1,5,3,0,3,7,3,8,5,5,3,3
7,7,2,6,1,6,6,1,3,5,4,9
9,7,6,0,1,4,0,4,4,1,4,0
3,5,1,4,4,0,7,1,8,9,9,1
1,9,8,7,4,9,5,2,2,1,2,9
8,1,2,2,7,7,6,8,2,3,9,7
3,5,2,1,3,5,2,2,4,7,0,7
9,6,8,8,3,5,2,9,8,7,4,7
8,8,4,5,5,1,5,6,5,1,3,3
2,6,3,5,0,5,0,3,4,4,0,5
2,2,7,6,3,7,1,4,0,3,8,3
4,8,4,2,6,8,5,6,2,5,0,1
7,2,4,3,8,4,4,6,5,3,9,4
4,6,1,0,6,0,2,6,7,4,9,5
6,3,3,4,6,1,0,8,6,1,7,5
8,3,4,2,8,3,0,1,8,9,1,5
9,6,1,9,1,1,8,8,8,9,1,4
3,6,1,6,1,4,5,1,0,1,9,1
6,4,3,9,3,0,5,0,5,3,2,4
5,2,4,6,1,2,6,0,1,8,4,0
3,5,7,6,3,6,4,5,2,8,1,5
6,3,6,8,4,2,7,1,5,3,0,6
9,1,5,9,9,1,1,4,5,7,3,0
1,6,7,3,5,8,6,5,5,2,6,0
2,8,8,6,5,5,2,3,8,1,9,8
0,4,5,3,7,6,2,5,4,3,2,5
5,1,2,3,0,3,4,9,4,9,4,9
5,8,2,2,0,2,4,1,1,7,0,3
0,6,0,0,3,6,3,6,2,2,2,9
2,4,8,1,9,4,0,8,8,0,4,7
3,9,1,0,5,6,8,8,2,5,2,6
5,3,8,9,1,6,5,9,7,7,6,1
8,6,9,6,1,1,6,7,7,3,2,2
7,2,1,9,8,8,5,3,6,3,3,6
9,9,4,8,7,9,8,6,6,0,3,1
8,3,0,9,1,7,4,8,0,1,6,2
8,2,6,2,4,0,2,8,9,6,3,7
1,0,8,5,3,2,3,7,1,7,8,2
$ while read; do
> pyth -c 'M/*FPJm*F.!MhMrd8aFCB,SGSHeJMl.Ms*VGZ.pHAc2Q,gGHnGH' <<< "$REPLY"
> done < test.in
[4, 4]
[4, 4]
[8, 8]
[4, 4]
[8, 8]
[2, 2]
[4, 4]
[4, 4]
[4, 4]
[36, 36]
[2, 2]
[8, 8]
[24, 24]
[8, 8]
[2, 2]
[2, 2]
[6, 6]
[2, 2]
[8, 8]
[2, 2]
[12, 12]
[2, 2]
[8, 8]
[12, 12]
[4, 4]
[12, 12]
[4, 4]
[6, 6]
[8, 8]
[8, 8]
[6, 6]
[4, 4]
[48, 48]
[8, 8]
[4, 4]
[1, 1]
[4, 4]
[4, 4]
[8, 8]
[4, 4]
[12, 12]
[2, 2]
[96, 96]
[2, 2]
[4, 4]
[2, 2]
[6, 6]
[24, 24]
[24, 24]
[48, 48]
[4, 4]
[8, 8]
[12, 12]
[8, 8]
[4, 4]
[2, 2]
[24, 24]
[16, 16]
[2, 2]
[8, 8]
[24, 24]
[4, 4]
[24, 24]
[4, 4]
[12, 12]
[8, 8]
[12, 12]
[4, 4]
[8, 8]
[4, 4]
[16, 16]
[4, 4]
[8, 8]
[8, 8]
[4, 4]
[4, 4]
[4, 4]
[4, 4]
[72, 72]
[24, 24]
[4, 4]
[4, 4]
[4, 4]
[2, 2]
[12, 12]
[4, 4]
[8, 8]
[4, 4]
[36, 36]
[6, 6]
[12, 12]
[8, 8]
[4, 4]
[2, 2]
[8, 8]
[24, 24]
[6, 6]
[1, 1]
[2, 2]
[2, 2]

```

To verify my submission satisfies the speed requirement, I've ran it with this test case.

```
$ time pyth -c 'M/*FPJm*F.!MhMrd8aFCB,SGSHeJAc2QgGH' < test-large.in | md5sum
5801bbf8ed0f4e43284f7ec2206fd3ff  -

real    0m0.233s
user    0m0.215s
sys     0m0.019s

```

# Answer
> 2 votes
## Matlab, 230 bytes

> Edit: Many things fixed to match dennis' test cases, and nnz is replaced by numel due to nil values.

```
f=1;t=-1;q=1;a=sort(input(''));b=sort(input(''));for i=unique(a)c=b(find(a==i));r=numel(c(c==t));f=f*factorial(numel(c))*sum(arrayfun(@(u)nchoosek(max(q,r),u),0:min(q,r)));z=c(end);y=numel(c(c==z));q=(t==z)*(q+r)+(t~=z)*y;t=z;end,f

```

---

## Execution

```
[2 2 1 2 1]
[3 2 3 2 1]

f =

    24

```

## Dennis' Testcase:

```
   A = importdata('f:\a.csv'); for i=1:100,a=sort(A(i,1:6));b=sort(A(i,7:12));
   f=1;t=-1;q=1;for i=unique(a)c=b(find(a==i));r=numel(c(c==t));f=f*factorial(numel(c))*sum(arrayfun(@(u)nchoosek(max(q,r),u),0:min(q,r)));z=c(end);y=numel(c(c==z));q=(t==z)*(q+r)+(t~=z)*y;t=z;end;
   disp(f);end

```

**Outputs:**

```
 4

 4

 8

 4

 8

 2

 4

 4

 4

36

 2

 8

24

 8

 2

 2

 6

 2

 8

 2

12

 2

 8

12

 4

12

 4

 6

 8

 8

 6

 4

48

 8

 4

 1

 4

 4

 8

 4

12

 2

96

 2

 4

 2

 6

24

24

48

 4

 8

12

 8

 4

 2

24

16

 2

 8

24

 4

24

 4

12

 8

12

 4

 8

 4

16

 4

 8

 8

 4

 4

 4

 4

72

24

 4

 4

 4

 2

12

 4

 8

 4

36

 6

12

 8

 4

 2

 8

24

 6

 1

 2

 2

```

# Answer
> 1 votes
## C++, 503 bytes

(just for fun, a non-golfing language)

```
#import<iostream>
#import<algorithm>
#define U 12345
#define l long long
using namespace std;int N,X=1,Y=1,Z=1,x[U],y[U],i=1;l p=1,M=1000000007,f[U];l e(l x,int y){return y?y%2?(x*e(x,y-1))%M:e((x*x)%M,y/2):1;}main(){for(f[0]=1;i<U;i++)f[i]=(f[i-1]*i)%M;cin>>N;for(i=0;i<N;i++)cin>>x[i];for(i=0;i<N;i++)cin>>y[i];sort(x,x+N);sort(y,y+N);for(i=1;i<N;i++)x[i]^x[i-1]?p=p*f[X]%M,X=1:X++,y[i]^y[i-1]?p=p*f[Y]%M,Y=1:Y++,x[i]^x[i-1]|y[i]^y[i-1]?p=p*e(f[Z],M-2)%M,Z=1:Z++;cout<<p*f[X]%M*f[Y]%M*e(f[Z],M-2)%M;}

```

Ungolfed version:

```
#include <cstdio>
#include <algorithm>
#define MOD 1000000007
using namespace std;
int N; // number of integers
int x[1000010]; // the 2 arrays of integers
int y[1000010];
long long product = 1;
long long factorial[1000010]; // storing factorials mod 1000000007
long long factorialInv[1000010]; // storing the inverse mod 1000000007
long long pow(long long x, int y) {
    if (y == 0) return 1;
    if (y == 1) return x;
    if (y%2 == 1) return (x*pow(x, y-1))%MOD;
    return pow((x*x)%MOD, y/2);
}
int main(void) {
    //freopen("in.txt", "r", stdin); // used for faster testing
    //precomputation
    factorial[0] = factorial[1] = 1;
    for (int i=2;i<=1000000;i++) {
        factorial[i] = (factorial[i-1]*i)%MOD;
        factorialInv[i] = pow(factorial[i], MOD-2);
    }
    // input
    scanf("%d", &N);
    for (int i=0;i<N;i++) {
        scanf("%d", &x[i]);
    }
    for (int i=0;i<N;i++) {
        scanf("%d", &y[i]);
    }
    // sort the 2 arrays
    sort(x, x+N);
    sort(y, y+N);
    int sameX = 1;
    int sameY = 1;
    int sameXY = 1;
    for (int i=1;i<N;i++) {
        if (x[i]==x[i-1]) {
            sameX++;
        } else {
            product *= factorial[sameX];
            product %= MOD;
            sameX = 1;
        }
        if (y[i]==y[i-1]) {
            sameY++;
        } else {
            product *= factorial[sameY];
            product %= MOD;
            sameY = 1;
        }
        if (x[i]==x[i-1] && y[i]==y[i-1]) {
            sameXY++;
        } else {
            product *= factorialInv[sameXY];
            product %= MOD;
            sameXY = 1;
        }
    }
    product *= factorial[sameX];
    product %= MOD;
    product *= factorial[sameY];
    product %= MOD;
    product *= factorialInv[sameXY];
    product %= MOD;
    printf("%lld\n", product);
    return 0;
}

```

# Answer
> 1 votes
# Jelly, 14 bytes

```
Ṣ€ZṭµŒɠ!P)×:ƭ/

```

Try it online!

Implements Dennis' method. Ignoring time requirements leads to an **8** byte solution:

```
Œ!ḋÐṀ¥@L

```

Try it online!

which can be **6** bytes if we take input in reverse order:

```
Œ!ḋÐṀL

```

Try it online!

## How they work

```
Ṣ€ZṭµŒɠ!P)×:ƭ/ - Main link. Takes a pair of lists [A, B]
Ṣ€             - Sort each
  Z            - Transpose to get all pairs
   ṭ           - Append that to [A, B], yielding [A, B, zip(A, B)]
    µ          - Call that triple T and start a new link with T as the argument
         )     - Over each element in T:
     Œɠ        -   Lengths of runs
       !       -   Factorial of each
        P      -   Product
             / - Reduce the triple:
            ƭ  -   Tie 2 dyads and cycle them:
          ×    -     Multiplication
           :   -     Integer division
                 For the triple [r, s, t], this yields (r×s):t

```

The 8 byte solution works in the following way:

```
Œ!ḋÐṀ¥@L - Main link. Takes A on the left and B on the right
     ¥   - Group the previous 2 links into a dyad f(B, A):
Œ!       -   All permutations of B
   ÐṀ    -   Keep those which yield a maximal value under:
  ḋ      -     Dot product with A
      @  - Run f(B, A)
       L - Length

```

The `¥@` is simply to compensate for inputs being in the wrong order. Of course, the **8** and **6** byte versions have complexity proportional to \\$\text{length}(B)!\\$, which grows very fast.

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


title: The RATS sequence

text:
# Question
Title: The RATS sequence
Your task is to generate the nth term of the RATS sequence, where n is the input. The RATS sequence is also known as the Reverse Add Then Sort sequence. This sequence can also be found here: http://oeis.org/A004000.

test cases:

```
0 > 1
1 > 2
2 > 4
3 > 8
4 > 16
5 > 77
6 > 145
7 > 668

```

For example, the output for 5 is 77 because 16 + 61 = 77. After this the 77 is sorted.

Shortest submission wins. This is my first challenge so i hope this is not a duplicate or something.

# Answer
# MATL, 11 ~~12~~ bytes

```
1i"tVPU+VSU

```

Input is a *string* (with single quotes) representing an integer in *unary*. String input is allowed by the challenge, and unary is a valid format.

**Try it online!**

### Explanation

```
1      % push number 1 to the stack
i      % input. Will be a string of "n" ones
"      % for loop: repeat n times (consumes string)
  t    %   duplicate
  V    %   convert to string
  P    %   reverse
  U    %   convert to number
  +    %   add
  V    %   convert to string
  S    %   sort
  U    %   convert to number
       % loop is implicitly ended
       % stack content is implicitly displayed

```
> 12 votes

# Answer
# 05AB1E, 6 bytes

Code:

```
$FDR+{

```

Explanation:

```
$       # Push 1 and input
 F      # For N in range(0, input)
  D     # Duplicate top of the stack
   R    # Reverse top of the stack
    +   # Add top two items
     {  # Sort top of the stack
        # Implicitly print top of the stack

```

This also works with a **0 byte** program.
> 10 votes

# Answer
## Pyth, ~~17~~ ~~13~~ 12 bytes

```
uS`+vGv_GQ\1

```

```
u        Q\1    reduce range(input()) on base case of "1" (string)
   +vG          eval the string (to get a number), and add...
      v_G       the same number, reversed first and then eval'd
 S`             convert back to string and sort

```

Try it on the online interpreter.
> 9 votes

# Answer
## CJam, 15 bytes

```
1ri{_sW%i+s$i}*

```

Test it here.

### Explanation

```
1     e# Push 1 as the start of the sequence.
ri    e# Read input and convert to integer N.
{     e# Run this block N times...
  _s  e#   Duplicate and convert to string.
  W%  e#   Reverse string.
  i+  e#   Convert back to integer and add to previous value.
  s$  e#   Convert to string and sort.
  i   e#   Convert back to integer for the next iteration.
}*

```
> 8 votes

# Answer
# JavaScript ES6, 70 bytes

*Saved 1 byte thanks to @user81655*

```
f=n=>n?+[...+[...''+(b=f(n-1))].reverse().join``+b+''].sort().join``:1

```

*sigh* JavaScript is really verbose. A **lot** (\> 50%) of the code is just case to string + array function + join + cast to int. I've tried reduce, eval, and all sorts of stuff but this seems to be the shortest.

Try it online (All browsers work)
> 6 votes

# Answer
# Python 2, 72

```
f=lambda x,n=1:x and f(x-1,int(''.join(sorted(`n+int(`n`[::-1])`))))or n

```

Recursive function, makes use of the Python 2 shorthand for `__repr__`, which will break once the function reaches very large values (an `L` will be appended to the number's string), I'm not certain from the spec if there is a place where we can stop, but if not changing to `str()` only adds 6 bytes, but then it becomes slightly shorter to output as a string, at 75 bytes:

```
f=lambda x,n='1':x and f(x-1,''.join(sorted(str(int(n)+int(n[::-1])))))or n

```

1 byte saved thanks to trichoplax on this version
> 6 votes

# Answer
# Brachylog, 19 bytes

```
0,1 .|-1=:0&Rr+R=o.

```

### Explanation

```
0,1 .               § If Input is 0, unify the Output with 1
     |              § Else
      -1=:0&R       § unify R with the output of this main predicate, with input = Input - 1
             r+R=o. § Reverse R, add it to itself and order it, then unify with the Output.

```
> 5 votes

# Answer
## Haskell, 67 bytes

```
import Data.List
g i=i:g(sort$show$read i+read(reverse i))
(g"1"!!)

```

Usage example: `(g"1"!!) 7`-\> `"668"`.

It's a direct implementation of the definition: starting with `"1"`, repeatedly append the reverse-add-sort result of the current element. The main function `(g"1"!!)` picks the `i`th element.
> 4 votes

# Answer
# Julia, 77 bytes

```
n->(x=1;for _=1:n x=(p=parse)(join(sort(["$(x+p(reverse("$x")))"...])))end;x)

```

This is a lambda function that accepts an integer and returns an integer. To call it, assign it to a variable.

Ungolfed:

```
function f(n::Int)
    # Begin x at 1
    x = 1

    # Repeat this process n times
    for _ = 1:n
        # Add x to itself with reversed digits
        s = x + parse(reverse("$x"))

        # Refine x as this number with the digits sorted
        x = parse(join(sort(["$s"...])))
    end

    # Return x after the process (will be 1 if n was 0)
    return x
end

```
> 4 votes

# Answer
# Jelly, ~~13~~ 12 bytes

I'm sure this can probably be golfed, as this is my first answer in Jelly/in a tacit language.

```
DUḌ+ðDṢḌ Performs RATS
1Ç¡      Loops

D        Converts integer to decimal
 U       Reverses
  Ḍ      Converts back to integer
   +     Adds original and reversed
    ð    Starts new chain
     D   Converts back to decimal
      Ṣ  Sorts
       Ḍ Back to integer again

1        Uses 1 instead of input
 Ḍ       Uses line above
  ¡      For loop

```

EDIT: Saved 1 byte, thanks to Dennis
> 4 votes

# Answer
# Perl 6, 40 bytes

```
{(1,{[~] ($_+.flip).comb.sort}...*)[$_]} # 40

```

( If you want it to return an Int put a `+` right before `[~]` )

### Usage:

```
# give it a lexical name
my &RATS = {…}

say RATS 5; # 77

# This implementation also accepts a list of indexes

# the first 10 of the sequence
say RATS ^10; # (1 2 4 8 16 77 145 668 1345 6677)

```
> 3 votes

# Answer
# Lua, ~~179~~ 156 Bytes

~~I can't see how I could golf it more, but I'm sure there's a way.~~ Thanks to @LeakyNun I took the time to come down on this and golf it the proper way, I could maybe still win some bytes by using another approach.

```
k=0z=table
for i=0,io.read()do
t={}(""..k+(""..k):reverse()):gsub("%d",function(d)t[#t+1]=d
end)z.sort(t)k=k<1 and 1or tonumber(z.concat(t,""))
end
print(k)

```

### Ungolfed and explanations

```
k=0
z=table                              -- z is a pointer on the table named table
                                     -- it allows me to use its functions
                                     -- while saving 4 bytes/use

for i=0,io.read()                    -- Iterate n times for the nth element
do
  t={}
  (""..a+(""..a):reverse())          -- we add k with its "reversed" value
                                     -- and convert the whole thing to a string
    :gsub(".",function(d)            -- for each character in it, use an anonymous fucntion
       t[#t+1]=d end)                -- which insert them in the array t
  z.sort(t)
  a=a<1 and 1 or                     -- if i==0, k=1
     tonumber(z.concat(t,""))        -- else we concat t in a string and convert it to number
end
print(k)

```
> 3 votes

# Answer
## Java 1.8, 251 bytes

```
interface R{static void main(String[]a){int i,r,n=1,c=0,t=Byte.valueOf(a[0]);while(++c<=t){i=n;for(r=0;i!=0;i/=10){r=r*10+i%10;}n+=r;a[0]=n+"";char[]f=a[0].toCharArray();java.util.Arrays.sort(f);n=Integer.valueOf(new String(f));}System.out.print(n);}}

```

### Expanded

```
interface R{
static void main(String[]args){
    int input,reversed,nextValue=1,count=0,target=Byte.valueOf(args[0]);
    while(++count<=target){
        input=nextValue;
        for(reversed=0;input!=0;input/=10){reversed=reversed*10+input%10;}
        nextValue+=reversed;
        args[0]=nextValue+"";
        char[]sortMe=args[0].toCharArray();
        java.util.Arrays.sort(sortMe);
        nextValue=Integer.valueOf(new String(sortMe));
    }
    System.out.print(nextValue);
}
}

```
> 3 votes

# Answer
## Seriously, 17 bytes

```
1,`;$R≈+$S≈`n

```

Try it online!

Explanation:

```
1,`;$R≈+$S≈`n
1              push 1
 ,`       `n   do the following n times:
   ;$R≈        reverse
       +       add
        $S≈    sort

```
> 3 votes

# Answer
# Python 2, ~~70~~ 66 bytes

```
f=lambda n,a=1:n<1or int(''.join(sorted(`f(n-1)+f(n-1,-1)`))[::a])

```

Try it online!
> 3 votes

# Answer
# Brachylog 2, 11 bytes, language postdates challenge

```
;1{↔;?+o}ⁱ⁽

```

Try it online!

## Explanation

```
;1{↔;?+o}ⁱ⁽
  {     }ⁱ  Repeatedly apply the following,
 1            starting at 1,
;         ⁽   a number of times equal to the input:
   ↔            reverse,
    ;?+         add the original input,
       o        then sort the resulting number

```

I'm not quite clear on what this does with zero digits, but the question doesn't state any particular handling, and they probably don't appear in the sequence anyway.
> 3 votes

# Answer
# Husk, 10 bytes

```
!¡ödOdS+↔1

```

Try it online!

1-indexed.
> 3 votes

# Answer
## ES6, 79 bytes

```
n=>eval("r=1;while(n--)r=+[...+[...r+''].reverse().join``+r+''].sort().join``")

```

82 bytes without `eval`:

```
n=>[...Array(n)].reduce(r=>+[...+[...r+''].reverse().join``+r+''].sort().join``,1)

```

All those conversions are painful.

@edc65 I actually saved 4 bytes by switching from `map` to `reduce` this time... no doubt you'll prove me wrong again though.
> 2 votes

# Answer
## Python 2, 91 Bytes

Input as Integer, result is printed to the screen.

```
def f(n):
 t=1
 for i in range(n):t=int("".join(sorted(str(int(str(t)[::-1])+t))))
 print t

```

This could be a lot shorter with some recursion magic I guess, but I cant wrap my head around it yet. Gonna have a fresh look later and hopefully improve this one.
> 2 votes

# Answer
## Python 2, 83 bytes

```
def f(n):
 v='1'
 for _ in v*n:v=''.join(sorted(str(int(v)+int(v[::-1]))))
 print v

```
> 2 votes

# Answer
# Mathematica 10.3, ~~66~~ 61 bytes

```
Nest[FromDigits@Sort@IntegerDigits[#+IntegerReverse@#]&,1,#]&

```

Quite simple.
> 2 votes

# Answer
# Java, ~~171~~ ~~167~~ ~~163~~ 160 bytes

```
int f(int n){int a=n>0?f(n-1):0,x=10,b[]=new int[x],c=a,d=0;for(;c>0;c/=x)d=d*x+c%x;for(a+=d;a>0;a/=x)b[a%x]++;for(;a<x;c=b[a++]-->0?c*x+--a:c);return n>0?c:1;}

```

Try it online!

Not the longest entry! \o/
> 2 votes

# Answer
# PHP, 102 Bytes

```
$r=[1];$i++<$argn;sort($v),$r[]=join($v))$v=str_split(bcadd(strrev($e=end($r)),$e));echo$r[$argn];

```

Online Version

## PHP, 95 Bytes

n \<= 39

```
for($r=[1];$i++<$argn;sort($v),$r[]=join($v))$v=str_split(strrev($e=end($r))+$e);echo$r[$argn];

```
> 2 votes

# Answer
# K (oK), 20 bytes

```
{x{.o@<o:$x+.|$x}/1}

```

Try it online!
> 2 votes

# Answer
# Scala, 56 bytes

```
Stream.iterate("1"){p=>p.toInt+p.reverse.toInt+""sorted}

```

Try it online!

An infinite stream.
> 2 votes

# Answer
# cQuents, 9 bytes

```
=1:sZ+\rZ

```

Try it online!

1-indexed.

## Explanation

```
=1            first term is 1
  :           sequence mode
              each term equals
   s                           sort(                                   )
    Z                                previous
     +                                        plus
      \r                                           reverse(          )
        Z                                                   previous

```
> 2 votes

# Answer
# PowerShell Core, ~~91~~ ~~89~~ ~~87~~ 76 bytes

```
$ofs=''
for($c="1";$args[0]--){$c="$("$(+$c+"$($c[20..0])")"|% t*y|sort)"}$c

```

Try it online!

PowerShell converts strings to `long` by default. The maximum length would always be 19 chars.

Cool challenge! -2 bytes thanks to Mazzy!
> 2 votes

# Answer
# Vyxal, ~~7~~ 5 bytes

```
1?(ms

```

Try it Online!

## Explained

```
1?(ms

1?          # Push 1 followed by the input
  (         # for n in range(0, input):
    m       #   push tos + tos[::-1] (palindromize on integers doesn't make it a palindrome)
     +s     #   add and sort the result

```

It's a shame how in order to remain competitive, one has to port other answers. Why do I say this? Because I have a nifty 21 byte function that accomplishes the same task:

```
@f:1|0=[1|n⨪@f;:ŉ+]s;

```

Example usage:

```
6 @f; , # Single number
0 11 r °f; z # Provide a test case unit kinda display

```
> 2 votes

# Answer
# Perl 5 `-a`, 51 bytes

```
$.=join'',sort(($.+reverse$.)=~/./g)while$_--;say$.

```

Try it online!
> 2 votes

# Answer
# Axiom, 146 bytes

```
c(r:String):NNI==reduce(+,[(ord(r.i)-48)*10^(#r-i) for i in 1..#r]);f(n:INT):NNI==(n<1=>1;v:=f(n-1);v:=v+c(reverse(v::String));c(sort(v::String)))

```

test and results \[RATS sequence\]

```
(3) -> [[i, f(i)] for i in 0..20]
   (3)
   [[0,1], [1,2], [2,4], [3,8], [4,16], [5,77], [6,145], [7,668], [8,1345],
    [9,6677], [10,13444], [11,55778], [12,133345], [13,666677], [14,1333444],
    [15,5567777], [16,12333445], [17,66666677], [18,133333444], [19,556667777],
    [20,1233334444]]

```
> 1 votes

# Answer
# Tcl, 91 bytes

```
proc R n {join [lsort [split [expr {$n?[set v [R [expr $n-1]]]+[string rev $v]:1}] ""]] ""}

```

Try it online!
> 1 votes

# Answer
# Japt, 9 bytes

1-indexed.

```
_+ìw)ìñ}g

```

Try it

```
_+ìw)ìñ}g     :Implicit input of integer U
_             :Function taking an integer Z as input
 +            :  Add
  ì           :    Convert Z to digit array
   w          :   Reverse and convert back
    )         :  End add
     ì        :  Convert result to digit array
      ñ       :  Sort and convert back
       }      :End function
        g     :Starting with 1, do that U times

```
> 1 votes

# Answer
# Arn, ~~13~~ 8 bytes

Ignore that it was previously 13 bytes, I never realized sorting doesn't cast back to strings when needed, so I fixed that.

```
'▀ƒʠBÀ½Ó

```

Try it!

# Explained

Unpacked: `&.{:>+.<}1`

```
&.            Mutate X N times via block B
  {           B has key of `_`
    :>        Sort ascending
        _     Implied
      +       Plus
          _   Implied
        .<    Reversed
  }           End block
1             and X is the number one
_             and N is STDIN; implied

```
> 1 votes

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


title: Find me a Tinder date!

text:
# Question
Title: Find me a Tinder date!
Ah, Tinder . . . the app that takes the code golf approach to online dating. With just a few well-chosen right swipes and a bit of luck (or a cute puppy pic), you too could have more matches than /(?!)/.

This challenge involves Tinder dates of a very different kind. Given a Tinder version number as input, hook me up with the date on which that version was released. You may use any convenient formats for input and output (e.g. string, list of integers, date object). Refer to this table\*:

```
+-------------+--------------+
| **Version no.** | **Release date** |
+-------------+--------------+
|   11.19.0   |  2020-07-10  |
|   11.18.0   |  2020-06-18  |
|   11.17.0   |  2020-06-04  |
|   11.16.0   |  2020-05-26  |
|   11.15.0   |  2020-05-11  |
|   11.14.0   |  2020-04-27  |
|   11.13.0   |  2020-04-13  |
|   11.12.0   |  2020-03-27  |
|   11.11.1   |  2020-03-21  |
|   11.11.0   |  2020-03-20  |
|   11.10.4   |  2020-03-06  |
|   11.10.3   |  2020-03-02  |
|   11.10.2   |  2020-02-29  |
|   11.10.1   |  2020-02-28  |
|   11.9.0    |  2020-02-13  |
|   11.8.0    |  2020-01-30  |
|   11.7.2    |  2020-01-24  |
|   11.7.1    |  2020-01-20  |
|   11.7.0    |  2020-01-19  |
|   11.6.1    |  2020-01-04  |
|   11.6.0    |  2019-12-16  |
|   11.5.0    |  2019-12-06  |
|   11.4.0    |  2019-11-22  |
|   11.3.0    |  2019-11-10  |
|   11.2.1    |  2019-11-01  |
|   11.1.1    |  2019-10-16  |
|   11.1.0    |  2019-10-11  |
|   11.0.2    |  2019-10-09  |
|   11.0.1    |  2019-09-27  |
|   11.0.0    |  2019-09-20  |
|   10.20.0   |  2019-09-10  |
|   10.19.1   |  2019-09-03  |
|   10.19.0   |  2019-08-28  |
|   10.18.0   |  2019-08-15  |
|   10.17.0   |  2019-07-24  |
|   10.16.0   |  2019-06-24  |
|   10.15.1   |  2019-06-08  |
|   10.15.0   |  2019-06-05  |
|   10.14.0   |  2019-06-04  |
|   10.13.0   |  2019-05-16  |
|   10.12.1   |  2019-05-02  |
|   10.12.0   |  2019-04-28  |
|   10.11.0   |  2019-04-13  |
|   10.10.1   |  2019-04-10  |
|   10.10.0   |  2019-04-02  |
|   10.9.1    |  2019-03-23  |
|   10.9.0    |  2019-03-18  |
|   10.8.1    |  2019-03-15  |
|   10.8.0    |  2019-03-06  |
|   10.7.0    |  2019-02-16  |
|   10.6.0    |  2019-02-12  |
|   10.5.0    |  2019-01-22  |
|   10.4.1    |  2019-01-08  |
|   10.4.0    |  2018-12-17  |
|   10.3.0    |  2018-11-29  |
|   10.2.1    |  2018-11-20  |
|   10.2.0    |  2018-11-15  |
|   10.1.1    |  2018-11-02  |
|   10.1.0    |  2018-10-31  |
|   10.0.2    |  2018-10-25  |
|   10.0.1    |  2018-10-19  |
|   10.0.0    |  2018-10-17  |
|    9.9.2    |  2018-10-12  |
|    9.9.1    |  2018-10-11  |
|    9.9.0    |  2018-10-09  |
|    9.8.1    |  2018-10-03  |
|    9.8.0    |  2018-09-21  |
|    9.7.2    |  2018-09-14  |
|    9.7.1    |  2018-09-06  |
|    9.7.0    |  2018-08-29  |
|    9.6.1    |  2018-08-23  |
|    9.6.0    |  2018-08-21  |
|    9.5.0    |  2018-08-06  |
|    9.4.1    |  2018-08-03  |
|    9.4.0    |  2018-07-24  |
|    9.3.0    |  2018-06-22  |
|    9.2.0    |  2018-06-11  |
|    9.1.0    |  2018-05-29  |
|    9.0.1    |  2018-05-17  |
|    9.0.0    |  2018-05-14  |
|    8.13.0   |  2018-05-03  |
|    8.12.1   |  2018-04-28  |
|    8.12.0   |  2018-04-26  |
|    8.11.0   |  2018-04-12  |
|    8.10.0   |  2018-04-05  |
|    8.9.0    |  2018-03-15  |
|    8.8.0    |  2018-02-28  |
|    8.7.0    |  2018-02-16  |
|    8.6.0    |  2018-02-05  |
|    8.5.0    |  2018-01-22  |
|    8.4.1    |  2018-01-02  |
|    8.4.0    |  2017-12-15  |
|    8.3.1    |  2017-12-08  |
|    8.3.0    |  2017-11-29  |
|    8.2.0    |  2017-11-03  |
|    8.1.0    |  2017-10-17  |
|    8.0.1    |  2017-10-09  |
|    8.0.0    |  2017-09-25  |
|    7.8.1    |  2017-09-08  |
|    7.8.0    |  2017-09-05  |
|    7.7.2    |  2017-08-23  |
|    7.7.1    |  2017-08-15  |
|    7.7.0    |  2017-08-14  |
|    7.6.1    |  2017-07-24  |
|    7.6.0    |  2017-07-14  |
|    7.5.3    |  2017-06-22  |
|    7.5.2    |  2017-06-09  |
|    7.5.1    |  2017-06-02  |
|    7.5.0    |  2017-05-30  |
|    7.4.1    |  2017-05-17  |
|    7.4.0    |  2017-05-09  |
|    7.3.1    |  2017-04-19  |
|    7.3.0    |  2017-04-13  |
|    7.2.2    |  2017-04-03  |
|    7.2.1    |  2017-04-01  |
|    7.2.0    |  2017-03-30  |
|    7.1.1    |  2017-03-16  |
|    7.1.0    |  2017-03-06  |
|    7.0.1    |  2017-02-19  |
|    7.0.0    |  2017-02-16  |
|    6.9.4    |  2017-02-06  |
|    6.9.3    |  2017-01-27  |
|    6.9.2    |  2017-01-25  |
|    6.9.1    |  2017-01-17  |
|    6.9.0    |  2017-01-12  |
|    6.8.1    |  2017-01-03  |
|    6.8.0    |  2016-12-19  |
|    6.7.0    |  2016-11-30  |
|    6.6.1    |  2016-11-18  |
|    6.6.0    |  2016-11-16  |
|    6.5.0    |  2016-11-07  |
|    6.4.1    |  2016-11-01  |
|    6.4.0    |  2016-10-26  |
|    6.3.2    |  2016-10-19  |
|    6.3.1    |  2016-10-12  |
|    6.3.0    |  2016-10-04  |
|    6.2.0    |  2016-09-27  |
|    6.1.0    |  2016-09-20  |
|    5.5.3    |  2016-09-12  |
|    5.5.2    |  2016-09-08  |
|    5.5.1    |  2016-09-03  |
|    5.5.0    |  2016-08-31  |
|    5.4.1    |  2016-08-25  |
|    5.4.0    |  2016-08-18  |
|    5.3.2    |  2016-07-29  |
|    5.3.1    |  2016-07-21  |
|    5.3.0    |  2016-07-19  |
|    5.2.0    |  2016-06-27  |
|    5.1.1    |  2016-06-07  |
|    5.1.0    |  2016-06-06  |
|    5.0.2    |  2016-05-13  |
|    5.0.1    |  2016-04-29  |
|    5.0.0    |  2016-04-21  |
|    4.8.2    |  2016-03-02  |
|    4.8.1    |  2016-01-30  |
|    4.8.0    |  2016-01-27  |
|    4.7.2    |  2015-12-17  |
|    4.7.1    |  2015-11-13  |
|    4.7.0    |  2015-11-11  |
|    4.6.1    |  2015-09-23  |
|    4.6.0    |  2015-09-04  |
|    4.5.0    |  2015-07-07  |
|    4.4.6    |  2015-05-18  |
|    4.4.5    |  2015-05-12  |
|    4.4.4    |  2015-05-05  |
|    4.4.3    |  2015-04-28  |
|    4.4.1    |  2015-04-16  |
|    4.4.0    |  2015-04-15  |
|    4.3.0    |  2015-03-02  |
|    4.1.4    |  2015-02-13  |
|    4.1.3    |  2015-02-06  |
|    4.1.1    |  2015-02-02  |
|    4.0.9    |  2014-10-09  |
|    4.0.8    |  2014-09-27  |
|    4.0.7    |  2014-09-19  |
|    4.0.6    |  2014-09-18  |
|    4.0.4    |  2014-07-17  |
|    4.0.3    |  2014-06-26  |
|    4.0.2    |  2014-06-17  |
|    4.0.1    |  2014-06-06  |
|    4.0.0    |  2014-06-05  |
|    3.0.4    |  2014-03-12  |
|    3.0.3    |  2014-02-26  |
|    3.0.2    |  2013-12-19  |
|    3.0.1    |  2013-11-28  |
|    3.0.0    |  2013-11-21  |
|    2.2.3    |  2013-11-20  |
|    2.2.2    |  2013-09-25  |
|    2.2.1    |  2013-09-24  |
|    2.2.0    |  2013-09-14  |
|    2.1.1    |  2013-06-07  |
|    2.1.0    |  2013-05-23  |
|    2.0.3    |  2013-04-01  |
|    2.0.2    |  2013-03-29  |
|    2.0.1    |  2013-03-28  |
|    1.1.4    |  2013-02-08  |
|    1.1.3    |  2013-02-06  |
|    1.1.2    |  2013-01-21  |
|    1.1.1    |  2013-01-11  |
|    1.1.0    |  2013-01-08  |
|    1.0.6    |  2012-11-24  |
|    1.0.5    |  2012-11-16  |
|    1.0.4    |  2012-11-06  |
|    1.0.3    |  2012-09-20  |
|    1.0.2    |  2012-08-29  |
|    1.0.1    |  2012-08-15  |
|    1.0.0    |  2012-08-03  |
+-------------+--------------+

```

<sup> *Source, with four modifications to unify the version number format (1.03 → 1.0.3, 4.3 → 4.3.0, 4.4 → 4.4.0, iOS 8.4.0 → 8.4.0).</sup>

# Answer
# JavaScript (Node.js),  ~~527 ... 498~~  493 bytes

Expects the version in the format described in the challenge. Returns a stringified Date object.

```
v=>"W302o288qB$87LB38R8gXL7x3egzBX9wW*2ec62od1X<H2eX8wX$30iiXL*Y398dXX<**Z7dab1u7jR6g67L447b$2o4lX2l29R$2l*[L`1o!++$*+Z[IR311v3eI`$RBAL3fB2pRRCZ2l$2vL*2u29B2fX$2vL252o%2755H+202l2p=313f2f+2pR1j;L312v=45BM3fR[$$+30[RX_RZ[R2v`I21282p2f1p21HM`C$M3f1o2p1vYL393l292vZ+A*30S`36I312pC1u3fX1o[2p3cXR1o2pX[272p2p3fI2p29".replace(/[\da-z]?./g,s=>(n=(s[1]?parseInt(s,36):Buffer(s)[0]-32-10*(s>'9'))^46,d-=~(n/6),n%=6,y=++n&4?z=++x-x:y,z=(n&2?!++y:z)+n%2,v==x+`.${y}.`+z?new Date(d*864e5):''),x=0,d=15554)

```

Try it online!

### How?

Each version is stored as a number \\$d\\$ of days elapsed since the previous version and a 3-bit value \\$m\\$ describing how the version numbers `x.y.z` are updated. The final value is:

$$n=\big(6\times(d-1)+(m-1)\big)\operatorname{XOR}46$$

The purpose of the XOR is to maximize the number of small values.

Numbers \\$0\\$ to \\$15\\$ are encoded with a single character in the ASCII range `32-47`.

Numbers \\$16\\$ to \\$54\\$ are encoded with a single character in the ASCII range `58-96`.

All other numbers are encoded as a 2-digit number in base 36, using digits and lower case letters (ASCII ranges `48-57` and `97-122` respectively).

We use the regular expression `/[\da-z]?./g` to match either a 2-digit number in base-36 or a single character in the other ASCII ranges.
> 12 votes

# Answer
# Python 3.8, 519 517 493 bytes

```
lambda x,e=enumerate:((y:=sum(ord(i)-35for i in"/1:U-+Ó&-4%W#$'Y3\x8a-$^$*:ê5|$.,:#d$+1Ĝ##'*8#P$#/,*)X`6W%GÍ&GV+3<$7;%+8*)'('+#*,+***),%/8³,(+%.-&6-1&%-)9+0'*0;-9$+1&43+5=.*¶72./69*1%*.&/1.E.&2%),+*1)%$(%))&0(,7º19'9,&(.+&2)17$&3C:0**-*1%(4#,/3-·2$')22#$('1$)5132-1;#"[:[(n,m,k)for n,i in e('1p 7o 5 6fp23 2aqc 2jno0l mzkii f1qqnj2p 4r96mr srha04m2ix5d 3lfbiojllc95'.split(),1)for m,j in e('a'*(n==4)+oct(int(i,36))[2:])for k in range(int(j,16))].index(x)])+1030403)>>9,(y>>5)&15,y&31)

```

Try it online!

Compressor+ungolfed:

```
import re
import time
import calendar
import base64
import math
with open('207234.txt','rt') as f:
    s=f.read()
matcher=re.compile(
    re.sub(r'\d+',lambda m:r'(\d+)',
    re.sub(r'(?:\\\ )+',lambda m:r'\s*',
    re.escape((x:=s.split('\n'))[0])
           )
           )
    )
assert len(x_:=matcher.findall(s))==sum(1 for i in x if i)
x_=[[int(j) for j in i] for i in x_][::-1]
v_=[tuple(i[:3]) for i in x_]
#for v in [(2, 0, 1),(11, 2, 1)][::-1]:
#    i=v_.index(v)
#    a,b,c,d,e,f=x_[i]
#    x_=x_[:i]+[[a,b,c-1,d,e,f]]+x_[i:]
for n,v in (v_add:=[(1,(2, 0, 1)),
            (0,(4, 0, 4)),
            (1,(4, 1, 1)),
            (0,(4, 1, 1)),
            (2,(4, 3, 0)),
            (0,(4, 4, 1)),
            (2,(6, 1, 0)),
            (1,(11, 2, 1)),
            (1,(11, 10, 1))])[::-1]:
    i=v_.index(v)
    a,b,c,d,e,f=x_[i]
    plus_i,plus_c,plus_b=[(1,1,0),(0,-1,0),(0,0,-1)][n]
    x_=x_[:i+plus_i]+[[a,b+plus_b,c+plus_c,d,e,f]]+x_[i+plus_i:]
x=[[0]]
old_a,old_b,old_c=1,0,0
for a,b,c,d,e,f in x_:
    if old_c!=c:
        if old_a==a and old_b==b:
            assert c==old_c+1# or (old_a,old_b,old_c) in [
                #(4, 0, 4),(4, 1, 1),(4, 4, 1)]
        x[-1][-1]+=(c-old_c>=0 and c-old_c or 1)
    if old_b!=b:
        if old_c==c:
            assert c==0# or (a,b,c) in [(11, 2, 1)]
            x[-1][-1]=1
        x[-1].append(0)
    if old_a!=a:
        if old_b==b:
            x[-1].append(0)
        x.append([0])
    old_a,old_b,old_c=a,b,c
x[-1][-1]+=1
v__=[(n,m,k) for n,i in enumerate(x,1)
     for m,j in enumerate(i)
     for k in range(j)]
assert set(v_)-set(v__)==set()
assert len(set(v__)-set(v_))==len(v_add)
versions=x
x=[d*512+e*32+f
    for a,b,c,d,e,f in x_
    ]
x2=[i-j for i,j in zip(x[1:],x)]
ls2,d2,s2=min((len(repr(
        s:=''.join(chr(k+l) for k in x2+[0])
        ).encode('utf-8')),l,s) for l in range(32,128))
print(ls2,d2)
s0=''.join(''.join(((str(j) if j else ' ') if j0 and base_n(x//n,n)+chr(48+x%n+(97-48-10)*(x%n>=10)) or ''
s0_=' '.join(base_n(int(i,8),36) for i in s0.split())
assert (s0==
    ' '.join(
        #('a'*(n==4)+
        oct(int(i,36))[2:]
        #)
        for n,i in enumerate(s0_.split(),1))
        )
print(len(s0_))
f=(
#print(len(r'''
lambda x,e=enumerate:((
    y:=sum(ord(i)-35 for i in s2[
        :[(n,m,k)
          for n,i in e(s0_.split(),1)
          for m,j in e('a'*(n==4)+oct(int(i,36))[2:])
          for k in range(int(j,16))].index(x)
        ])+1030403
    )>>9,(y>>5)&15,y&31)
#''')-8-4*(7+5)-3)
)
assert all(f((a,b,c))==(d,e,f_) for a,b,c,d,e,f_ in x_)

```
> 8 votes

# Answer
# Javascript - 862 bytes

```
r=(v=>{for(p=[1,0,0],s=0,d="0cc0ec16c2fc0ac08c2db03c0ac10c02c30a00c01c03c34b0fc63b0ac01c38c01a07c15c45c0ec55a01c0bc09c15c3fc00c01c08c0cc74b00c04c00c07c11b00b2cb01c0cc00c07c07c06c32b3bb13c31b02c22c29b03c20c32a08c0ec18b01c14b16b02c08c14b07c06b03c05c04c08a00b07b07b08c07c07b06c06b09b02c0cb13b0fc09b05c08c02c0ac0aa03c0fb0ac0eb02c02c0ab06c14b08c0db03c07c0dc16b0ac15b01c08c0db03c11a0ec08b11b1ab09c07b12c14b0eb0bb0cb0fb15b07b0eb02c05b0ba03c0cb0db0bb20b0ac03b0fb02c06b08c08c07b0cc06b02c01c05a02c06c06b02c0db05c09b12b16c0eb15b04b12b09c03b05c0ab08c03b0fb04c0eb13b01b03c10b1eb16b0db06c07b0aa07c0cc02b05c10b00c09b0cb0eb0ab13c0fb01c04c06b0eb0fb00c01c02c04c0eb01c06b11b0eb0eb0fb09b0eb16b00c",i=0;;i+=3){if(p.join(".")==v)return new Date(1343952e6+864e5*s).toISOString().substr(0,10);s+=parseInt(d[i]+d[i+1],16),l=d[i+2],[a,b,c]=p,p='b'>l?[a+1,0,0]:'c'>l?[a,b+1,0]:[a,b,c+1]}})

```

## Explanation

The release dates are encoded as a difference of days. Each diff is represented by 3 characters in `d`. The first 2 characters indicate the number of days to the next version. The last character uses 'a','b', or 'c' to represent which part of the version changed, if the version number is considered as a.b.c .

As some versions skip over numbers (such as 11.1.1 to 11.2.1), missing releases were added, costing only 3 bytes each.

There's probably some additional compression possible with the data string but I wanted to keep it strictly ASCII.

```
const version_dates = {
    '11.19.0':'2020-07-10',
    '11.18.0':'2020-06-18',
    '11.17.0':'2020-06-04',
    '11.16.0':'2020-05-26',
    '11.15.0':'2020-05-11',
    '11.14.0':'2020-04-27',
    '11.13.0':'2020-04-13',
    '11.12.0':'2020-03-27',
    '11.11.1':'2020-03-21',
    '11.11.0':'2020-03-20',
    '11.10.4':'2020-03-06',
    '11.10.3':'2020-03-02',
    '11.10.2':'2020-02-29',
    '11.10.1':'2020-02-28',
    '11.10.0':'2020-02-28',
    '11.9.0':'2020-02-13',
    '11.8.0':'2020-01-30',
    '11.7.2':'2020-01-24',
    '11.7.1':'2020-01-20',
    '11.7.0':'2020-01-19',
    '11.6.1':'2020-01-04',
    '11.6.0':'2019-12-16',
    '11.5.0':'2019-12-06',
    '11.4.0':'2019-11-22',
    '11.3.0':'2019-11-10',
    '11.2.1':'2019-11-01',
    '11.2.0':'2019-11-01',
    '11.1.1':'2019-10-16',
    '11.1.0':'2019-10-11',
    '11.0.2':'2019-10-09',
    '11.0.1':'2019-09-27',
    '11.0.0':'2019-09-20',
    '10.20.0':'2019-09-10',
    '10.19.1':'2019-09-03',
    '10.19.0':'2019-08-28',
    '10.18.0':'2019-08-15',
    '10.17.0':'2019-07-24',
    '10.16.0':'2019-06-24',
    '10.15.1':'2019-06-08',
    '10.15.0':'2019-06-05',
    '10.14.0':'2019-06-04',
    '10.13.0':'2019-05-16',
    '10.12.1':'2019-05-02',
    '10.12.0':'2019-04-28',
    '10.11.0':'2019-04-13',
    '10.10.1':'2019-04-10',
    '10.10.0':'2019-04-02',
    '10.9.1':'2019-03-23',
    '10.9.0':'2019-03-18',
    '10.8.1':'2019-03-15',
    '10.8.0':'2019-03-06',
    '10.7.0':'2019-02-16',
    '10.6.0':'2019-02-12',
    '10.5.0':'2019-01-22',
    '10.4.1':'2019-01-08',
    '10.4.0':'2018-12-17',
    '10.3.0':'2018-11-29',
    '10.2.1':'2018-11-20',
    '10.2.0':'2018-11-15',
    '10.1.1':'2018-11-02',
    '10.1.0':'2018-10-31',
    '10.0.2':'2018-10-25',
    '10.0.1':'2018-10-19',
    '10.0.0':'2018-10-17',
    '9.9.2':'2018-10-12',
    '9.9.1':'2018-10-11',
    '9.9.0':'2018-10-09',
    '9.8.1':'2018-10-03',
    '9.8.0':'2018-09-21',
    '9.7.2':'2018-09-14',
    '9.7.1':'2018-09-06',
    '9.7.0':'2018-08-29',
    '9.6.1':'2018-08-23',
    '9.6.0':'2018-08-21',
    '9.5.0':'2018-08-06',
    '9.4.1':'2018-08-03',
    '9.4.0':'2018-07-24',
    '9.3.0':'2018-06-22',
    '9.2.0':'2018-06-11',
    '9.1.0':'2018-05-29',
    '9.0.1':'2018-05-17',
    '9.0.0':'2018-05-14',
    '8.13.0':'2018-05-03',
    '8.12.1':'2018-04-28',
    '8.12.0':'2018-04-26',
    '8.11.0':'2018-04-12',
    '8.10.0':'2018-04-05',
    '8.9.0':'2018-03-15',
    '8.8.0':'2018-02-28',
    '8.7.0':'2018-02-16',
    '8.6.0':'2018-02-05',
    '8.5.0':'2018-01-22',
    '8.4.1':'2018-01-02',
    '8.4.0':'2017-12-15',
    '8.3.1':'2017-12-08',
    '8.3.0':'2017-11-29',
    '8.2.0':'2017-11-03',
    '8.1.0':'2017-10-17',
    '8.0.1':'2017-10-09',
    '8.0.0':'2017-09-25',
    '7.8.1':'2017-09-08',
    '7.8.0':'2017-09-05',
    '7.7.2':'2017-08-23',
    '7.7.1':'2017-08-15',
    '7.7.0':'2017-08-14',
    '7.6.1':'2017-07-24',
    '7.6.0':'2017-07-14',
    '7.5.3':'2017-06-22',
    '7.5.2':'2017-06-09',
    '7.5.1':'2017-06-02',
    '7.5.0':'2017-05-30',
    '7.4.1':'2017-05-17',
    '7.4.0':'2017-05-09',
    '7.3.1':'2017-04-19',
    '7.3.0':'2017-04-13',
    '7.2.2':'2017-04-03',
    '7.2.1':'2017-04-01',
    '7.2.0':'2017-03-30',
    '7.1.1':'2017-03-16',
    '7.1.0':'2017-03-06',
    '7.0.1':'2017-02-19',
    '7.0.0':'2017-02-16',
    '6.9.4':'2017-02-06',
    '6.9.3':'2017-01-27',
    '6.9.2':'2017-01-25',
    '6.9.1':'2017-01-17',
    '6.9.0':'2017-01-12',
    '6.8.1':'2017-01-03',
    '6.8.0':'2016-12-19',
    '6.7.0':'2016-11-30',
    '6.6.1':'2016-11-18',
    '6.6.0':'2016-11-16',
    '6.5.0':'2016-11-07',
    '6.4.1':'2016-11-01',
    '6.4.0':'2016-10-26',
    '6.3.2':'2016-10-19',
    '6.3.1':'2016-10-12',
    '6.3.0':'2016-10-04',
    '6.2.0':'2016-09-27',
    '6.1.0':'2016-09-20',
    '6.0.0':'2016-09-20',
    '5.5.3':'2016-09-12',
    '5.5.2':'2016-09-08',
    '5.5.1':'2016-09-03',
    '5.5.0':'2016-08-31',
    '5.4.1':'2016-08-25',
    '5.4.0':'2016-08-18',
    '5.3.2':'2016-07-29',
    '5.3.1':'2016-07-21',
    '5.3.0':'2016-07-19',
    '5.2.0':'2016-06-27',
    '5.1.1':'2016-06-07',
    '5.1.0':'2016-06-06',
    '5.0.2':'2016-05-13',
    '5.0.1':'2016-04-29',
    '5.0.0':'2016-04-21',
    '4.8.2':'2016-03-02',
    '4.8.1':'2016-01-30',
    '4.8.0':'2016-01-27',
    '4.7.2':'2015-12-17',
    '4.7.1':'2015-11-13',
    '4.7.0':'2015-11-11',
    '4.6.1':'2015-09-23',
    '4.6.0':'2015-09-04',
    '4.5.0':'2015-07-07',
    '4.4.6':'2015-05-18',
    '4.4.5':'2015-05-12',
    '4.4.4':'2015-05-05',
    '4.4.3':'2015-04-28',
    '4.4.2':'2015-04-28',
    '4.4.1':'2015-04-16',
    '4.4.0':'2015-04-15',
    '4.3.0':'2015-03-02',
    '4.2.0':'2015-03-02',
    '4.1.4':'2015-02-13',
    '4.1.3':'2015-02-06',
    '4.1.2':'2015-02-06',
    '4.1.1':'2015-02-02',
    '4.1.0':'2015-02-02',
    '4.0.9':'2014-10-09',
    '4.0.8':'2014-09-27',
    '4.0.7':'2014-09-19',
    '4.0.6':'2014-09-18',
    '4.0.5':'2014-09-18',
    '4.0.4':'2014-07-17',
    '4.0.3':'2014-06-26',
    '4.0.2':'2014-06-17',
    '4.0.1':'2014-06-06',
    '4.0.0':'2014-06-05',
    '3.0.4':'2014-03-12',
    '3.0.3':'2014-02-26',
    '3.0.2':'2013-12-19',
    '3.0.1':'2013-11-28',
    '3.0.0':'2013-11-21',
    '2.2.3':'2013-11-20',
    '2.2.2':'2013-09-25',
    '2.2.1':'2013-09-24',
    '2.2.0':'2013-09-14',
    '2.1.1':'2013-06-07',
    '2.1.0':'2013-05-23',
    '2.0.3':'2013-04-01',
    '2.0.2':'2013-03-29',
    '2.0.1':'2013-03-28',
    '2.0.0':'2013-03-28',
    '1.1.4':'2013-02-08',
    '1.1.3':'2013-02-06',
    '1.1.2':'2013-01-21',
    '1.1.1':'2013-01-11',
    '1.1.0':'2013-01-08',
    '1.0.6':'2012-11-24',
    '1.0.5':'2012-11-16',
    '1.0.4':'2012-11-06',
    '1.0.3':'2012-09-20',
    '1.0.2':'2012-08-29',
    '1.0.1':'2012-08-15',
    '1.0.0':'2012-08-03'
}

r=(v=>{for(p=[1,0,0],s=0,d="0cc0ec16c2fc0ac08c2db03c0ac10c02c30a00c01c03c34b0fc63b0ac01c38c01a07c15c45c0ec55a01c0bc09c15c3fc00c01c08c0cc74b00c04c00c07c11b00b2cb01c0cc00c07c07c06c32b3bb13c31b02c22c29b03c20c32a08c0ec18b01c14b16b02c08c14b07c06b03c05c04c08a00b07b07b08c07c07b06c06b09b02c0cb13b0fc09b05c08c02c0ac0aa03c0fb0ac0eb02c02c0ab06c14b08c0db03c07c0dc16b0ac15b01c08c0db03c11a0ec08b11b1ab09c07b12c14b0eb0bb0cb0fb15b07b0eb02c05b0ba03c0cb0db0bb20b0ac03b0fb02c06b08c08c07b0cc06b02c01c05a02c06c06b02c0db05c09b12b16c0eb15b04b12b09c03b05c0ab08c03b0fb04c0eb13b01b03c10b1eb16b0db06c07b0aa07c0cc02b05c10b00c09b0cb0eb0ab13c0fb01c04c06b0eb0fb00c01c02c04c0eb01c06b11b0eb0eb0fb09b0eb16b00c",i=0;;i+=3){if(p.join(".")==v)return new Date(1343952e6+864e5*s).toISOString().substr(0,10);s+=parseInt(d[i]+d[i+1],16),l=d[i+2],[a,b,c]=p,p='b'>l?[a+1,0,0]:'c'>l?[a,b+1,0]:[a,b,c+1]}})

const test_passed = Object.keys(version_dates).every(version=>
    version_dates[version]===r(version)
);
console.log(test_passed ? 'TEST PASSED' : 'TEST_FAILED')
```
> 4 votes

# Answer
# PowerShell, ~~513~~ 508 bytes

Inspired by Arnauld's answer. It's nice code.

```
param($t)$v=,0*5;$d='2012-8'|date
'Ba2a4b2d7a0hT5ca0a6b@d8acU2a5Y9a0ae6Agb1f9a4H5aa1ib1`f3aha2Pa16`dgPQ7T4a`a2ggfU0U9a9T9bc4T1cc2E0ha4R4aR0R2bhR0gVced@XWWhgWfVYbQ2Q9a5Yehba0A0cQ5a0Q4bbQ0fR0hQ3cga3R2a0R1ahQ3cA7a4XQ7R6iWa8R0Q4Q1Q2Q5R1WQ4bUA1cQ2Q3Q1S2a0SQ5bVhhWa2VbaEbfVbQ3eYQ8b2Q4R1TQ8iSeQ0hSQ5dQ4Q9QcQ6S0R2Q3fWA0ga2RePa6YQ2Q4Q0a9Q5adVQ4Pa5abdQ4aVQ7Q4Q4Q5YQ4R2'-split'(?=\D)'|%{$d=$d|% *ys($a=[char]($_[0]-($i=($_[0]-48)-shr4)*16)+$_[1]+$_[2])
$v[$i-1]++;$v[$i]=$v[$i+1]=0;if(+$a-and$v[0..2]-join'.'-eq$t){$d}}

```

Try it online!

Some versions of the Tinder are missing from the list. They're added as test cases.

The script starts with version `0.0.0` and the date of `August 1, 2012`.

Then the script iterates through the data string. Each substring contains the number of days since the previous release and the descriptor in the first character ASCII code. The descriptor is one of `16`,`32`,`48`:

* `16` \- increment the major version by 1
* `32` \- increment the middle version by 1
* `48` \- increment the minor version by 1

The script excludes versions for which the number of days is zero, but makes an increment for the version. Thus, the script works correctly with the missed versions of the Tinder.
> 3 votes

# Answer
# Jelly, 333 332 bytes

```
“3ĖẎ⁺Ḣµ3bṄ9HĊ:%:ḞŻHuƤƊ²ⱮĠJėḷȧ!°ọṫọẠIÆGƙĿĠR%ėȦqȷSḂṘ^ṡ¬’BC2“®(0>FZ\`j‘¦3“"4‘¦s2;"“€żḍḋF=ẎhƘẎƁy7ẉr¶$qɦṁI>Ḥ⁾s÷,Ṇ~ʋƊt¦c@ɓḥḤ~ÐqHṀ °8{yþẒ⁺¬4ɠz DOṇĠƓK?Ọj!⁽>3'nẏmẹœƭUÑʠæƥæk¹Ð§©ḲŒmPɦġRXɓµọạṢṘỤzḍ⁻s¡+ç¿¹ḋ-^ɼRċIsẸƑñ*½Nı’b29¤[“¬¿“¬“£’];
“eÄneøỌC<½weƙBƤʠĠċUṅKȮCıẈ-ɱ¥*øṬḊ⁹®gṫ¥ɗɱɦɦN⁶ÐẈGṖƭƇ¶ȦĿ⁸ịỵ9ḟŒḥɱ=ṭcỴʠßɓḷ@ḳⱮsṪɠḞ.ṣ?9’B2“`ot~‘¦s3,¢¹×TṂ>3Ḷ¤Ʋ}+ʋ\€yW

```

Try it online!

Input and output are a list of three integers. (The output is actually wrapped in a singleton list, but that's not visible.)

## Explanation

The version numbers are stored as increments from the last version, except if the minor version is increased, then the patch version is automatically reset, etc. For example: \[7,8,9\] + \[0,1,2\] = \[7,9,2\]. It turns out that most increments are made of 0's and 1's, so I concatenated them (starting with the initial version \[1,0,0\], replaced 2's with 0's and represented the huge binary number with a base-250 literal, then added code to set the specific indices to 2.

For dates, the same incrementing logic is used, but this time the day increments are much bigger (up to 28), so I stored them separately as a base 29 number. (Since there are no 0's, I tried using base 28 and incrementing, but it wasn't worth it.) Years and months are stored analogously to version numbers, except:

* The initial date is added separately
* The number had leading zeros, so I had to invert it
* There were some 3's, which I dealt with the same way as with 2's.

Merging this all together creates the table, which I simply pass to the `y` (translate) command to look up the input.
> 2 votes

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


title: Count the Collatz survivors mod 2^n

text:
# Question
Title: Count the Collatz survivors mod 2^n
### Introduction

We have 22 Collatz conjecture-related challenges as of October 2020, but none of which cares about the restrictions on counter-examples, if any exists, to the conjecture.

Considering a variant of the operation defined in the conjecture:

$$f(x)= \cases{ \frac{x}{2}&for even x \cr \frac{3x+1}{2}&for odd x }$$

The Wikipedia article suggests that a modular restriction can be easily calculated and used to speed up the search for the first counter-example. For a pair of \\$k\\$ and \\$b\\$ where \\$0\le b\lt2^k\\$, if it is possible to prove that \\$f^k(2^ka+b)\<2^ka+b\\$ for all sufficiently large non-negative integers \\$a\\$, the pair can be discarded. This is because if the inequality holds for the counter-example, we can find a smaller counter-example from that, contradicting the assumption that the counter-example is the first one.

For example, \\$b=0, k=1\\$ is discarded because \\$f(2a)=a\<2a\\$, while \\$b=3, k=2\\$ is not because \\$f^2(4a+3)=9a+8\>4a+3\\$. Indeed, for \\$k=1\\$ we only have \\$b=1\\$ and for \\$k=2\\$, \\$b=3\\$, to remain (survive) after the sieving process. When \\$k=5\\$, though, we have 4 survivors, namely 7, 15, 27 and 31.

~~However, there are still 12,771,274 residues mod \\$2^{30}\\$ surviving, so just still about a 100x boost even at this level~~

### Challenge

Write a program or function, given a natural number \\$k\\$ as input, count the number of moduli mod \\$2^k\\$ that survives the sieving process with the operation applied \\$k\\$ times. The algorithm used must in theory generalize for arbitrary size of input.

The sequence is indeed A076227.

### Examples

```
Input > Output
1     > 1
2     > 1
3     > 2
4     > 3
5     > 4
6     > 8
7     > 13
8     > 19
9     > 38
10    > 64
15    > 1295
20    > 27328
30    > 12771274

```

### Winning criteria

This is a code-golf challenge, so the shortest submission of each language wins. Standard loopholes are forbidden.

# Answer
# APL (Dyalog Unicode), 18 bytes

```
+/∧/¨1<×\¨.5+,⍳⎕/2

```

Try it online!

A full program. Fails to compute the answer for \\$k\>15\\$ due to system limitations (rank of intermediate array).

### How it works

If we call the \\$\frac{x}{2}\\$ the \\$D\\$-step and \\$\frac{3x+1}{2}\\$ as the \\$U\\$-step, it is known that each residue class \\$0 \dots 2^k-1\\$ modulo \\$2^k\\$ corresponds to exactly one \\$UD\\$-sequence of length \\$k\\$.

In the original formula, the coefficient of \\$a\\$ is multiplied by \\$\frac32\\$ for the \\$U\\$-step, and \\$\frac12\\$ for the \\$D\\$-step, and it suffices to count the \\$UD\\$-sequences where the coefficient never drops under 1.

The program computes this by generating all length-\\$k\\$ sequences of 0.5 and 1.5 (skipping the \\$UD\\$ part), and counts the ones where the multiplicative scan `×\` gives all numbers greater than 1.

```
+/∧/¨1<×\¨.5+,⍳⎕/2  ⍝ Full program; input: k
               ⎕/2  ⍝ k copies of 2
             ,⍳     ⍝ indices in an array of shape 2 2 ... 2
                    ⍝ which generates all binary sequences of length k
          .5+  ⍝ Add 0.5 to get all sequences of 0.5 and 1.5
       ×\¨     ⍝ Product scan
     1<        ⍝ Test if each number is greater than 1
  ∧/¨          ⍝ ... for all numbers in each sequence
+/             ⍝ Count ones

```
> 21 votes

# Answer
# Python 3, 154 bytes

```
lambda k:sum(min(g(2**k,b,q+1)for q in range(k))>=(2**k,b)for b in range(2**k))
g=lambda x,y,z:z and g(*(x+y)%2and(3/2*x,(3*y+1)/2)or(x/2,y/2),z-1)or(x,y)

```

Try it online!
> 5 votes

# Answer
# Python 3 (PyPy), 49 bytes

Port of Bubbler's APL answer.

```
f=lambda n,p=1:n<1or(p>2)*f(n-1,p/2)+f(n-1,p*3/2)

```

Try it online!

---

# Python 2 (PyPy), ~~138~~ ~~136~~ 134 bytes

A (slow) golf of the C implementation given on the OEIS page.

```
f=lambda k,r=0,m=1,w=1,q=0:f(k,r+r%2*-~r>>1,r%2*2*m+m>>1,w,q)if(w<=m)>m&1else m>=w and(q==k or sum(f(k,x,m*2,w*2,q+1)for x in(r,r+m)))

```

Try it online!

PyPy is used here because this is just annoyingly slow in CPython.
> 4 votes

# Answer
# Jelly, 12 bytes

```
Ø.ṗ+.×\€ḞẠ€S

```

Try it online!

Port of Bubbler's approach, which is really clever and seems to be unbeatable with a straightforward approach lol. Make sure you upvote that answer!

## Explanation

```
Ø.ṗ+.×\€ḞẠ€S  Main Link
Ø.            [0, 1]
  ṗ           Cartesian product; gives all k-length binary sequences
   +.         Add 0.5
       €      For each sequence of 0.5, 1.5
     ×\       Take the cumulative products
        Ḟ     Floor (if it's less than 1, this returns 0; otherwise, it returns a positive/truthy value; 1 isn't a possible product at least for k up to a billion)
          €   For each sequence
         Ạ    1 if they're all truthy (so all are greater than 1), 0 otherwise
           S  Sum (counts the number of truthy results)

```

-1 byte thanks to Jonathan Allan with the observation that 1 is not a possible product (in practice up to like a billion, at least), so checking \>=1 and \>1 are the same, and you can do the former with floor, saving a byte.
> 4 votes

# Answer
# 05AB1E, 13 bytes

```
13S;Iã€ηP1›PO

```

Port of *@Bubbler*'s APL answer, so make sure to upvote him!
(This results in `0` for \\$k=0\\$.)

Try it online or verify all test cases \\$n\leq15\\$.

**Explanation:**

```
13S            # Push 13 as a list of digits: [1,3]
   ;           # Halve each: [0.5,1.5]
    Iã         # Take the cartesian product of this pair with the input-integer
      €        # Map over each inner list:
       η       #  And get all its prefixes
        P      # Take the product of each inner-most prefix
         1›    # Check for each value if it's larger than 1 (1 if truthy; 0 if falsey)
           P   # Check if an entire inner-most list is truthy by taking the product
            O  # Sum the list, to get the total amount of truthy values
               # (after which this sum is output implicitly as result)

```

Some equal-bytes alternatives for `13S;` could be `3ÅÉ;`; `₂€;;`; `₂S4/`; etc.
> 3 votes

# Answer
# C (gcc), ~~72~~ \\$\cdots\\$ ~~66~~ 65 bytes

Saved ~~3~~ ~~6~~ 7 bytes thanks to ceilingcat!!!

```
f(n){n=s(n,1.);}s(n,p)float p;{n=n--?(p>2)*s(n,p/=2)+s(n,p*3):1;}

```

Try it online!

Using Bubbler's method from his APL answer.

# C (gcc), ~~175~~ \\$\cdots\\$ ~~138~~ 135 bytes

Saved a whopping 29 bytes thanks to ovs!!!
Saved ~~4~~ 7 bytes thanks to ceilingcat!!!

```
f(n){n=s(1,0,1,0,n);}s(m,r,l,p,q)long m;{for(;~m&m>0;)r-=r&1?m+=m/2,~r/2:(m/=2,r/2);m=m<l?0:p-q?s(m+=m,r+m,l+=l,++p,q)+s(m,r,l,p,q):1;}

```

Try it online!

Golf of Phil Carmody's C code on the OEIS A076227 page.
> 2 votes

# Answer
# Haskell, 45 bytes

```
(!1)
n!p|p<1=0|n<1=1|d<-n-1=d!(p/2)+d!(p*1.5)

```

Try it online!

À la Bubbler.
> 2 votes

# Answer
# Husk, ~~15 14 13~~ 12 bytes

```
#ȯΛ⌊G*m+.πḋ2

```

Try it online!

-1 byte from Dominic van Essen.

-1 more byte from Dominic van Essen.

-1 more more byte from Dominic van Essen(Or is it?).

Same method as Bubbler's answer.
> 1 votes

# Answer
# Forth (gforth), 107 bytes

```
: s ?dup if 1- fdup 2e f> abs fdup f2/ over recurse * swap 1.5e f* recurse + else fdrop 1 then ;
: f 1e s ;

```

Try it online!

ovs and Noodle9 transformed the APL solution into a nice recursive function, so here is a translation of those into Forth.

```
\ recursive helper function
: s ( n f:p -- cnt )
  ?dup if                    \ if n is nonzero ( n f:p )
    1-                       \ ( n-1 f:p )
    fdup 2e f> abs fdup f2/  \ ( n-1 p>2 ) ( f: p p/2 )
    over recurse *           \ ( n-1 p>2*cnt1 ) ( f: p ) *0.5 branch
    swap 1.5e f* recurse     \ ( p>2*cnt1 cnt2 ) *1.5 branch
    +                        \ ( cnt )
  else        \ otherwise ( f:p )
    fdrop 1   \ remove p and push 1
  then
;
: f ( n -- cnt ) 1e s ;  \ main function; call s with p=1

```
> 1 votes

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