title: Automate the OEIS

text:
# Question
Title: Automate the OEIS
We see a lot of challenges here asking for a function to create a sequence from the OEIS. While these challenges are fun, as a programmer I see an opportunity for automation.

Your challenge is to make a program that takes the index of a sequence (e.g. A172141) and some integer n (e.g. 7), and pulls the appropriate value from the appropriate webpage.

## I/O

As mentioned, your program should take a sequence index and some value n as input and output the nth term in that sequence. You accept any index in the sequence's B-files. If the index is greater than the largest index listed in the B-files you may throw an exception or output whatever you choose (these are not in the test cases). Standard methods of input and output are permitted.

## Restrictions on web use

You should not access any websites other than https://oeis.org and http://oeis.org. This includes url shorteners, your own personal website, and this question itself. If you would like to access some other website and you believe that it is not unfair to allow you to do so, you can leave a comment and I will arbitrate.

## Scoring

This is a code golf challenge so the program with the least bytes used in its source code wins. Standard loopholes are disallowed.

## Test Cases

Assuming that your machine has proper internet connection and the OEIS servers are up and running the following inputs and outputs should correspond.

```
A172141, 7   -> 980
A173429, 4   -> 276
A190394, 6   -> 16
A002911, 11  -> 960
A052170, 3   -> 24
A060296, 8   -> 3
A178732, 5   -> 27
A000001, 1   -> 1
A000796, 314 -> 3
A001622, 162 -> 8
A002206, -1  -> 1

```

## Tip

* When accessing the B-files `http://oeis.org/b<A-number>.txt` will redirect to the proper B-file.

# Answer
> 11 votes
# Bash + coreutils + w3m, ~~51~~ ~~45~~ 42 bytes

```
w3m oeis.org/b${1:1}.txt|sed "s/^$2 //p;d"

```

*Thanks to @EamonOlive for golfing off 3 bytes!*

### Example run

```
$ bash oeis.sh A172141 7
980

```

### How it works

*w3m* is a text-based web browser, which displays both HTML and plain text in readable format. Unlike *curl*, it follows redirects by default (this is required, since `oeis.org/bxxxxxx.txt` redirects to `oeis.org/Axxxxxx/bxxxxxx.txt`), doesn't produce any stray output to STDERR, and has a three-byte name.

The command

```
w3m oeis.org/b${1:1}.txt

```

the desired URL, where `${1:1}` is the first command-line argument without its first character.

The output is piped to the command

```
sed "s/^$2 //p;d"

```

which extracts the desired output. `s/^$2 //p` attempts to replace `^$2` (start of line, followed by the second command-line argument, followed by a space) with the empty string. If the substitution is successful, `p` prints its result. Afterwards, `d` unconditionally deletes the pattern to prevent *sed* from printing the entire input.

# Answer
> 4 votes
# Mathematica + OEIS.m, 31

```
(OEISFunction@ToString@#;#@#2)&

```

example usage: `%[A172141,36]`

---

# Mathematica, 85

```
#2/.Rule@@@Import["http://oeis.org/b"<>#~StringDrop~1<>".txt","Data"]~DeleteCases~{}&

```

example usage: `%["A002206",-1]`

# Answer
> 3 votes
## Perl, 59 bytes

```
($_,$v)=@ARGV;/./;say`curl oeis.org/$_/b$'.txt`=~/$v (.*)/m

```

Needs `-M5.010` or `-E` to run. For instance :

```
$ cat oeis.pl
($_,$v)=@ARGV;/./;say`curl oeis.org/$_/b$'.txt`=~/$v (.*)/m
$ perl -M5.010 oeis.pl A178932 5 2>&-
27

```

*Saved 8 bytes thanks to @Dennis answer, by removing `http://`, as he did.*

# Answer
> 2 votes
# Python 3, ~~153~~ ~~146~~ 135 bytes

**7 bytes thanks to FryAmTheEggman.**

**6 bytes thanks to Eamon Olive.**

**5 bytes thanks to Rod.**

```
from urllib.request import*
def f(a,n):
 for l in urlopen("http://oeis.org/b%s.txt"%a[1:]):
  p,q=l.split()
  if n==p.decode():return q

```

Call it like this:

```
print(f("A000796","314"))

```

Run on a machine where the default is utf-8.

# Answer
> 2 votes
# Python 2, ~~125~~ ~~118~~ 113 bytes

***~~7~~ 12 bytes saved thanks to Lynn***

```
import re,urllib2 as u;lambda x,y:re.findall("(?<=%d ).*"%y,u.urlopen("http://oeis.org/b%s.txt"%x[1:]).read())[0]

```

Well heres my go at my own problem. It is likely suboptimal but I think I did a pretty decent job. It creates an anonymous function that takes a string and integer as arguments and returns a string as the result or throws an error if the index is out of range.

This can be made into a 124 bytes full program.

```
import re,urllib2 as u;print re.findall("(?<=%d ).*"%input(),u.urlopen("http://oeis.org/b%s.txt"%raw_input()[1:]).read())[0]

```

This prompts the user for the input. First asking for the index and then the A-number of the sequence.

# Answer
> 2 votes
# CJam, 36 bytes

```
"oeis.org/b"r1>+".txt"+gN%Sf%z~\ra#=

```

### Example run

```
$ cjam oeis.cjam <<< 'A172141 7'
980

```

# Answer
> 2 votes
## R, ~~94~~ 89 bytes

```
t=read.table(paste0("http://oeis.org/b",substring(scan(,""),2),".txt"));t[t$V1==scan(),2]

```

Using `sprintf` instead of `paste0` results in the same bytecount:

```
t=read.table(sprintf("http://oeis.org/b%s.txt",substring(scan(,""),2)));t[t$V1==scan(),2]

```

*Five bytes saved thanks to plannapus.*

# Answer
> 2 votes
# PHP 5.6, ~~93~~ 92 bytes

```
function f($i,$l){echo explode(' ',file('http://oeis.org/b'.substr($i,1).'.txt')[--$l])[1];}

```

This one is pretty straight forward. Pull the page with `file()`, get the line at `$line - 1` (0-index), explode on the space and print out the second array element from that.

# Answer
> 2 votes
# Nim, ~~123~~ ~~115~~ 113 bytes

```
import httpclient,nre,future
(a,n)=>get getContent("http://oeis.org/b"&a[1..^0]&".txt").find re "(?<="&n&r" )\d+"

```

This is a lambda expression; to use it, it must be passed as an argument to a testing procedure. A complete program that can be used for testing is given here:

```
import httpclient,nre,future
proc test(x: (string, string) -> RegexMatch) = echo x("A172141", "7") # Your input here
test((a,n)=>get getContent("http://oeis.org/b"&a[1..^0]&".txt").find re "(?<="&n&r" )\d+")

```

Expects input as two strings. Example usage:

```
$ nim c oeis.nim
$ ./oeis
980

```

We use `httpclient`'s `getContent` proc to get the OEIS b-file, then use a regex to `find` the line with the index. `find` returns an `Option[RegexMatch]`, so we use `get` to retrieve the value from the `Option`. `echo` automatically stringifies, so we leave stringification out.

# Answer
> 1 votes
## Clojure, 103

```
#(read-string((re-find(re-pattern(str %2" (\\d+)"))(slurp(str"http://oeis.org/b"(subs % 1)".txt")))1)))

```

`re-find` finds a vector of first matche's regex groups, it is used as a function and `1` gets the string at position `1`. `read-string` converts string to int. I'm not 100% sure if this regex always finds the correct row.

# Answer
> 1 votes
# R, 87 bytes

```
f=function(A,n)(R<-read.table(gsub("A(\\d+)","http://oeis.org/b\\1.txt",A)))[R$V1==n,2]

```

Build the URL string with regexes instead of `paste` or `sprintf`.

# Answer
> 0 votes
# Node.js + `request`, 109 bytes

```
x=>n=>require('request')(`http://oeis.org/b${x.slice(1)}.txt`,(a,b)=>console.log(b.body.match(n+` (.+)`)[1]))

```

Takes the sequence ID and a number.

# Answer
> 0 votes
# Julia, 88 bytes

```
x\y=match(Regex("$y (.*)"),readall(Requests.get("http://oeis.org/b$(x[2:end]).txt")))[1]

```

*Golfed with some help from @Dennis!*

Make sure you have `Requests.jl` installed before running.

# Answer
> 0 votes
## ListSharp, 266 bytes

```
STRG a=READ[<here>+"\\a.txt"]
ROWS x=ROWSPLIT a BY [","]
STRG a=GETRANGE x[0] FROM [2] TO [a LENGTH]
NUMB y=<c#int.Parse(x[1])c#>
STRG a=DOWNLOAD["http://oeis.org/b"+a+".txt"]
ROWS x=ROWSPLIT a BY [<newline>]
STRG a=GETLINE x [y]
ROWS x=ROWSPLIT a BY [" "]
SHOW=x[1]

```

Its sad when a language made for web scraping needs so many lines because nesting statements in ListSharp is *taboo*

# Answer
> 0 votes
# 05AB1E, 29 bytes

```
¦’ÏÁ€ˆ.µÔ/bÿ.í¼t’.w¶¡€#˜DIk>è

```

Beats all other answers.

```
¦’...’.w¶¡€#˜DIk>è  # trimmed program
                 è  # 0-based...
               k    # 0-based index of...
              I     # input...
               k    # in...
            ˜D      # flattened list of...
      .w            # content of response from url...
                    # (implicit) "http://" concatenated with...
 ’...’              # "oeis.org/bÿ.txt"...
                    # (implicit) with ÿ replaced by...
                    # implicit input...
¦                   # excluding the first character...
         ¡          # split by...
        ¶           # newlines...
          €         # with each element...
           #        # split by spaces...
                >   # plus 1...
                 è  # th element in...
            ˜       # flattened list of...
      .w            # content of response from url...
                    # (implicit) "http://" concatenated with...
 ’...’              # "oeis.org/bÿ.txt"...
                    # (implicit) with ÿ replaced by...
                    # implicit input...
¦                   # excluding the first character...
         ¡          # split by...
        ¶           # newlines...
          €         # with each element...
           #        # split by spaces

```

---
Tags: code-golf, sequence, internet, search
---


title: How many Faro shuffles for a cycle?

text:
# Question
Title: How many Faro shuffles for a cycle?
## Background

*Inspired by this video by Matt Parker*

A Faro shuffle is a perfect riffle shuffle where the deck is exactly interleaved with its other half. This is how to perform one:

* the deck of 52 cards is split into two piles of 26 cards each
* the two piles are interleaved. In the case of an "in" shuffle, the bottom card of the top pile ends up on the bottom, and the top card of the bottom pile ends up on the top (the outer cards move inwards). In the case of an "out" shuffle, the top card of the top pile ends up on top and vice versa (the outer cards stay on the outside).

For example, with a demonstration deck of only 6 cards, the steps are as follows:

* Start: `[1, 2, 3, 4, 5, 6]`
* Split: `[1, 2, 3] [4, 5, 6]`
* For an "in" shuffle, interleave like this: `[4, 1, 5, 2, 6, 3]` (zip the second half with the first half)
* For an "out" shuffle, interleave like this: `[1, 4, 2, 5, 3, 6]` (zip the first half with the second half)

## Challenge

Given a list of values representing "in" and "out" Faro Shuffles, determine the minimum number of times that list needs to repeat such that a deck of 52 distinct cards will return to its starting arrangement. *Note that this is not the same value shown in Matt's video; it is divided by the length of the input*.

If the deck returns to the starting arrangement part way through the list (for example, `[0, 0, 0, 0, 0, 0]` (6 out shuffles) would finish after 1 full set of 6 and then 2 more shuffles), it doesn't count as having finished the cycle because it wasn't completed at the end of the list (so the output for that example would be `LCM(6, 8) / 6 = 4`).

## Example

Input: `[0, 1, 1, 0, 1, 1, 1]` (using `0` for "out" shuffles and `1` for "in" shuffles, and representing the starting deck is `[0, 1, 2, 3, ... 48, 49, 50, 51]`)

* First, we perform the shuffles as they are specified in the input: out, in, in, out, in, in, in. This gives the output:

```
[0, 26, 1, 27, 2, 28, 3, 29, 4, 30, 5, 31, 6, 32, 7, 33, 8, 34, 9, 35, 10, 36, 11, 37, 12, 38, 13, 39, 14, 40, 15, 41, 16, 42, 17, 43, 18, 44, 19, 45, 20, 46, 21, 47, 22, 48, 23, 49, 24, 50, 25, 51]

```
* Now, we check if that has caused the list to return to its exact original arrangement
* Repeat these steps, and output the number of times we've looped. In this case, it takes 1260 repetitions of `[0, 1, 1, 0, 1, 1, 1]`, so our output is 1260

## Test cases

Using `0` for "out" shuffles and `1` for "in" shuffles.

```
[0] 8
[1] 52
[0, 1] 252
[0, 0, 1] 20
[0, 1, 0] 20
[1, 0, 0] 20
[0, 1, 1, 0, 1, 1, 1] 1260
[0, 0, 0, 0, 0, 0, 0, 1] 2
[0, 0, 0, 0, 0, 0] 4
[0, 0, 0, 0, 0, 0, 0, 0, 0] 8
[0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1] 144
[1, 0, 1, 1, 1, 0, 1, 1, 1] 60
[0, 1, 1, 0] 44
[1, 1, 1, 1, 0, 1, 0, 1, 0] 306
[1, 1, 0, 1, 1, 0, 0, 1, 1, 0] 210
[1, 0, 0, 0, 0, 0, 0, 1] 2
[0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1] 168
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1] 228
[1, 0, 1, 0, 1] 60
[1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1] 66
[0, 0, 0, 0, 1, 0] 252

```

## Rules

* The values that represent "in" and "out" in the input list can be any two distinct values, within reason. For example, `0` and `1` is allowed, but `code_to_do_an_in_shuffle()` and `code_to_do_an_out_shuffle()` are not
* Standard loopholes are forbidden
* You may use any sensible I/O method
* This is , so the shortest code in bytes wins

# Answer
> 4 votes
# Pyth, ~~63~~ 53 bytes

```
J26AcU*J2JW=Y?@Q%ZlQ.iHG.iGH=+Z1AcYJI&qYSY!%ZlQB;/ZlQ

```

Try it online!

```
J26          # Set J to 26.
AcU*J2J      # Assign G and H to range(0, 26) and range(26, 52) respectively.
W            # While
?@Q%ZlK      # If the current element of Q (input list)
.iHG         # is 1, then interleave H and G
.iGH         # Otherwise, interleave G and H
=Y           # Assign that value to Y
=+Z1         # Increment Z by 1
AcYJ         # Now reassign G and H to the first and last 26 elements of Y respectively
I&qYSY!%ZlQB # If Y is already sorted and we are at the end of input list, then break
;/ZlQ        # Print Z divided by length of input list

```

# Answer
> 4 votes
# , 45 40 36 bytes

```
3 :'*./#&>C.{/|.y{(,:&,&|:|.)i.2 26'

```

Try it online!

-4 thanks to xash

Rather than use a while loop, the solution constructs the permutation, changes it to cyclic form `C.`, and then takes the LCM `*./` of the cycle lengths.

# Answer
> 4 votes
# Python 3.8, ~~88~~ 84 bytes

```
*r,=range(52)
f=lambda k,s=r:[s:=s[x::2]+s[1-x::2]for x in k[::-1]]!=s==r or-~f(k,s)

```

Try it online!

Uses @l4m2's neat idea (on @hyper-neutrino's answer) to reverse the shuffles instead of execute them forwards.

-4 bytes thanks to @dingledooper

# Answer
> 3 votes
# Ruby, ~~86 80~~ 77 bytes

```
->s{r=k=[*0..51];1.step.find{s.map{|c|r=k.map{|v|r[(v/2+26*v+=c)%52]}};r==k}}

```

Try it online!

# Answer
> 3 votes
# Python 2, 100 bytes

```
def f(k):
 s=t=range(52);q=1
 while 1:
	for x in k[::-1]:s=s[x::2]+s[1-x::2]
	if s==t:return q
	q+=1

```

Try it online!

-10 bytes thanks to pxeger
-4 bytes thanks to Neil
-11 bytes thanks to l4m2
-6 bytes thanks to dingledooper

# Answer
> 3 votes
# Charcoal, ~~47~~ 35 bytes

```
Ｗ¬⁼ω⁺αβ«⊞υωＦ⮌θ≔⭆²Φ∨ω⁺αβ﹪⁺κ⁺λξ²ω»ＩＬυ

```

Try it online! Link is to verbose version of code. Edit: Saved 12 bytes thanks to @l4m2 by performing in-sorts and out-sorts instead, but the input values are now `0` for an in-shuffle and `1` for an out-shuffle. Explanation:

```
Ｗ¬⁼ω⁺αβ«

```

Repeat until the shuffle reaches the initial pack, represented here by the concatenation of the upper and lower case letters.

```
⊞υω

```

Keep track of the number of cycles.

```
Ｆ⮌θ

```

Loop over each type of shuffle in reverse, since we're performing inverse shuffles.

```
≔⭆²Φ∨ω⁺αβ﹪⁺κ⁺λξ²ω

```

Take alternating cards from the pack (initialising it on the first pass). Whether odd or even cards are taken first depends on the type of shuffle. The remaining cards are then concatenated, completing the in-sort or out-sort.

```
»ＩＬυ

```

Output the number of shuffles needed.

# Answer
> 3 votes
# Husk, 13 bytes

```
Γ€GFöΣT*½ḣ52∞

```

Try it online! or Verify all tests

15 bytes, 16 bytes, 16 bytes

input taken as `1` instead of `0` and `-1` instead of `1`.

-2 bytes from Leo.

This could be another 15 bytes, but times out.

## Explanation

```
Γ€GFöΣT*½ḣ52∞
            ∞ infinite list of repetitions of the input
  G           scan from left with:
         ḣ52  1..52 as the start value
   Fö          fold the repeated list with
               the current value as start
               and do the following:
        ½       split in two halves
       *        multiply by the list number
      T         transpose
     Σ          flatten
Γ              take first element and:
 €             find its index in the remaining list

```

# Answer
> 2 votes
# JavaScript (Node.js), ~~102~~ ~~99~~ ~~98~~ 95 bytes

```
f=s=>s.map(v=>L=L.map((_,i)=>L[i+52*(i%2^v)>>1]))|L+[]==G||1+f(s);L=G=[...Array(52)].map(Array)

```

Try it online!

# Answer
> 2 votes
# Wolfram Language, 97 bytes

```
s|->Length@NestWhileList[Fold[Riffle@@#~TakeDrop~26~RotateLeft~#2&,#,s]&,Range[52],UnsameQ,All]-1

```

Try it online! (uses \\\[Function\] rather than `|->`, as TIO doesn't have the most recent version of the language)

# Answer
> 2 votes
# PowerShell 7, 87 84 bytes

```
for(;"$c"-ne0..51;$x++){$args|%{$s=$_
$c=$c ??0..51|%{(2*$_+($s,!$s)[$_/51])%52}}}$x

```

Try it online! (Link is to a TIO-compatible version with 4 additional bytes; PowerShell 6 and below do not support the null-coalescing operator `??`)

# Answer
> 2 votes
# , 80 bytes

```
o=scan();e=d=0:51;while({for(s in o)d=t(matrix(d,26,3)[,1:2+s]);sd(d-e)})T=T+1;T

```

Try it online!

Implements riffle shuffle by re-arranging the deck into a matrix with 26 rows, and transposing.
An 'in' shuffle first reverses the columns, which is achieved in  by making a 3-column matrix (which gets filled by recycling elements), and then selecting columns 2,3.

```
e=d=0:51                # set e,d to the initial order of the deck
while({                 # while loop:
  for(s in o)           #  first cycle through the shuffle-types in o
    d=                  #  reordering d each time
      t(                #  as the transpose of
        matrix(d,26,    #  a matrix with 26 rows
        3)              #  and 3 columns (so the third column is the first one again)
          [,1:2+s])     #  selecting columns 1:2 if o==0,
                        #  or columns 2:3 (same as 2:1) if o==1;
  sd(d-e)}              #  then repeat until standard deviation of d-e is non-zero
                        #  (d & e are both permutations of the deck,
                        #  so sum(d-e) must be zero, and sd(d-e) can only
  )                     #  be zero if d==e)
  T=T+1                 # increment T (from initial value of 1) each loop
T                       # and finally output the value of T

```

# Answer
> 2 votes
# Jelly, 15 bytes

```
ØẠŒHṚ⁹¡ż/Fʋƒ@ƬL

```

A monadic Link accepting a list of `1`s (in) and `0`s (outs) which yields a positive integer (number of repetitions of the described procedure required to reset the deck of 52 cards).

**Try it online!**

### How?

Just repeatedly executes the instructions list until reset has occured...

```
ØẠŒHṚ⁹¡ż/Fʋƒ@ƬL - Link: list, shuffles
ØẠ              - "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" ...26*2=52 :)
             Ƭ  - collect up starting with that "deck" until a repetition occurs using:
            @   -   with reversed arguments - f(shuffles,deck)
           ƒ    -     reduce using (X) as the initial value with:
          ʋ     -       last four links as a dyad - f(current_deck, current_shuffle):
  ŒH            -         split (current_deck) into two halves
      ¡         -         repeat...
     ⁹          -           ...number of times: right argument = current_shuffle
    Ṛ           -           ...action: reverse
        /       -         reduce using:
       ż        -           zip together
         F      -         flatten
              L - length

```

# Answer
> 1 votes
# Python 3, 136 bytes

-5 thanks to OP

Can definitely be golfed more, but I'm too tired.

```
def f(s):
 o=l=[*range(52)];c=0
 while 1:
  for i in s:l=[(l[:26],l[26:])[j%2-i][j//2]for j in range(52)]
  c+=1
  if l==o:return c

```

Try it online!

# Answer
> 1 votes
# Haskell, 91 bytes

```
f l=[r|r<-[1..],and[foldl(\x i->mod(2*x+mod(div x 26+i)2)52)y([1..r]>>l)==y|y<-[0..51]]]!!0

```

Try it online!

`f` takes `l` as a list of `0`s and `1`s, with the format described in the statement.

# Answer
> 1 votes
# C (gcc), ~~194~~ \\$\cdots\\$ ~~180~~ 174 bytes

Saved 6 bytes thanks to ceilingcat!!!

```
w=52;n;c;i;j;a[156];f(s,l)int*s;{for(c=i=0;i<w*3;)a[n=i++]=i%w;for(;n;++c)for(j=0;j<l;++j)for(i=!wmemcpy(a+w,a,w);i<w;n=wmemcmp(a,a+2*w,w))a[i++]=a[w+(s[j]+i&1)*26+i/2];n=c;}

```

Try it online!

Inputs a pointer to the shuffle array and its length (since pointers in C carry no length info).

### Explanation (before some golfs)

```
w=52;n;c;i;j;                              // declare needed vars
f(s,l)int*s;{                              // main function
    char a[w],b[w],e[w];                   // declare arrays for shuffling
    for(c=i=0;i<w;)a[i++]=e[i]=i;          // init a and e to 0..51
    for(n=1;n;++c)                         // loop until array a is back
                                           // to its original order (n == 0)
                                           // c counts iterations
        for(j=0;j<l;++j)                   // loop over shuffle array
            for(i=!memcpy(b,a,w);          // copy a over to b (returns !0)
                                 i<w;      // loop over a and b
                          n=memcmp(a,e,w)) // here's a good place to calc n
              a[i++]=                      // set each element in a to
                     b[                   ]// an element in b depending on
                       ((s[j]+i)%2)*26+i/2 // our current shuffle and i
    n=c;                                   // return count
}

```

---
Tags: code-golf, array, card-games
---


title: Compute the uncomputable ... sort of

text:
# Question
Title: Compute the uncomputable ... sort of
Implement a function \\$f\\$ (as a function or complete program), such that

\\$ \displaystyle\lim\_{n\rightarrow \infty} f(n) \\$

converges to a number which is *not* a computable number.

Answers will be scored in bytes with fewer bytes being better.

# IO formats

Your answer may be in any of the following formats

* A program or function that takes \\$n\\$ as input and outputs \\$f(n)\\$.
* A program or function that takes \\$n\\$ as input and outputs all \\$f(m)\\$ where \\$m \leq n\\$.
* A program or function that outputs successive members of the sequence indefinitely.

Numeric output can be given as any of the following

* An arbitrary precision rational type.
* A pair of arbitrary precision integers representing a numerator and denominator. e.g. \\$(2334, 888)\\$
* A string representing a rational expressed as a fraction. e.g. `2334/888`
* A string representing a rational expressed as a decimal expansion. e.g. `3.141592`

Use of fixed precision floating point numbers is unfortunately not accepted. They end up being messy when dealing with limits, I hope the options permitted allow the majority of languages to compete in this challenge relatively unencumbered.

Neither of the fractional outputs are required to be in reduced form.

# Examples

Here are some numbers which are not computable, but are computable in the limit. That is any of the following numbers are potential limits for valid solutions to the challenge. This list is obviously not exhaustive.

* The real whose binary expansion encodes the halting problem.
* The real whose binary expansion encodes the busy beaver numbers.
* The real whose binary expansion encodes the truth set of first order logic.
* Chaitin's constant

### Example algorithm

The following is an example algorithm which solves the problem by converging to the first example.

Take a positive integer \\$n\\$ as input. Take the first \\$n\\$ Turing machines and run each of them for \\$n\\$ steps. Output

\\$ \displaystyle\sum\_{m=0}^n \begin{cases}2^{-m}& \text{if machine }m\text{ halted before }n\text{ steps}\\0 & \text{otherwise}\end{cases} \\$

That is to say we start at zero and add \\$1/2^m\\$ for each machine \\$m\\$ that halts in our simulation.

Now since computing a Turing machine for \\$n\\$ steps is computable, and adding rational numbers certainly is computable, this algorithm is as a whole computable. However if we take the limit, we get a string that exactly encodes the solutions halting problem. The limit is:

\\$ \displaystyle\sum\_{m=0}^\infty \begin{cases}2^{-m}& \text{if machine }m\text{ halts}\\0 & \text{otherwise}\end{cases} \\$

I think it is intuitive that this sort of thing is not something that can be computed. But more concretely if we were able to compute this number then we could use it to solve the halting problem, which is not possible.

# Answer
# 05AB1E, ~~25~~ 24 bytes

```
LεÅγιøIãʒηεøJË}à}gĀ}'.šJ

```

Try it online!

-1 thanks to @ovs

f(n) is a decimal number such that it's xth digit is 1 iff x\<=n and when you run length encode x and convert it to matching pairs, it has a solution to PCP with a length of at most n pairs.

outputs as `.digits after the dot`. In case the 0 is needed, it's +1 to replace `'.` with `„0.`

Code explaination:

```
L      all numbers from 1 to N
ε      map each to
 Åγ    run length encode
 ι     uninterleave to two lists
 ø     tranpose
 Iã    cartesian power N, all choices of N such pairs
 ʒ     only keep those such that
  η    its prefixes
  ε    map each to
   ø   itself transposed
   J   joined
   Ë   both elements are equal
  }
  à    maximum - if any of those are 1
 }
 gĀ    the length of the filtered list isn't 0
}
'.š    prepend .
J      join, and implicitly print

```

We can show a reduction from PCP with two symbols (which is known to be undecidable):

given an instance of PCP with two symbols, 1 and 2 (for example \[2,1\], \[11,2\], \[2212,111\]), unflatten the pairs (which would give \[2,1,11,2,2212,111\] in the example) and run length decode with alternating 1, 0. That number would be x. The solution to the PCP instance is 1 iff the xth digit of the limit of this function is 1.
> 6 votes

# Answer
# Vyxal, ~~34~~ 32 bytes

```
ƛ0€y"ÞT:£⁰(¥J)ṖƛKƛÞTƛṅ;≈;a;a;\.p

```

-2 thanks to @Aaron Miller

Try it Online!

This is a port of my 05AB1E answer, with seperating by 0 instead of run length decoding required, and a different behavior when the length of it isn't even. Also, instead of up to N pieces, it's up to N uses of each piece, but all of that shouldn't matter to the limit's uncomputablity. This is my first time golfing in vyxal, so any improvements would be helpful.

```
ƛ         map each in range to
 0€       split by 0
 y"ÞT     uninterleave and transpose
 :£       save in register
 ⁰(¥J)    merge with itself input times
 Ṗ        take all permutations
 ƛ        and map each to
  K       its prefixes
  ƛ       map each to
   ÞT     it transpose
   ƛṅ;    join each
   ≈      all are equal?
   ;
   a      are any of those 1?
  ;
  a       are any of those 1?
;
\.p       prepend .
implicitly output as a string

```
> 2 votes

# Answer
# Python 2, ~~189~~ ~~188~~ 186 bytes

-2 thanks to @Wheat Wizard

```
from itertools import*
j=input()
s='.'
for x in range(j):d=`x`.split('0');s+='X10'[min(len(set(map(''.join,zip(*l))))for l in product(*[[d[i:i+2]for i in range(0,len(d),2)]]*j))]
print s

```

Try it online!

A port of my 05AB1E answer to python, using a 0 seperator instead of run length encoding.
> 2 votes

---
Tags: code-golf, number, sequence, open-ended-function
---


# Question
Title: Shortest total non-primitive recursive function
Natural numbers ≡ \\$\mathbb{N}≡\\{0,1,2,...\\}\\$

The submission can be either a program or a function, both cases will henceforth be referred to as "function".

The task is to golf the shortest function \\$\mathbb{N}^n→\mathbb{N}\\$, i.e. a function that maps \\$n\\$ natural numbers (with \\$n\>0\\$ being a number of your choosing) to a natural number, such that the function is not primitive recursive, that is, a function that is not composable from only the following functions (each variable being a natural number):

(from https://en.wikipedia.org/wiki/Primitive\_recursive\_function)

Zero $$Z()=0$$

Successor $$S(x)=x+1$$

Projection $$P\_i^n(x\_0,x\_1,\dots,x\_{n-1})=x\_i$$

Composition $$h(x\_0,x\_1,\dots,x\_m)=f(g\_1(x\_0,x\_1,\dots,x\_m),\dots,g\_k(x\_0,x\_1,\dots,x\_m))$$

Primitive recursion

$$\begin{align}h(0,x\_0,\dots,x\_k)&=f(x\_0,\dots,x\_k)\\h(S(y),x\_0,\dots,x\_k)&=g(y,h(y,x\_0,\dots,x\_k),x\_0,\dots,x\_k)\end{align}$$

---

From the above five functions/operations, we can get many functions like the constant function, addition, multiplication, exponentiation, factorial, primality test, etc.

A (total) function that is not primitive recursive could be one that grows faster than any primitive recursive function, like the Ackermann function. Its proof of not being primitive recursive is on Wikipedia.

Or a function could be non primitive recursive due to contradictions that would arise otherwise; examples are provided in the answers to this Math Stack Exchange question as pointed out by Bubbler.

---

The submissions are free to use any radix as long as the same radix is used for each of the input and output numbers.

Your submission can take input as a list of numbers, a list of strings representing numbers, a string containing (constant) delimiter-separated numbers, or the like. In the case of using a string or equivalent, your submissions are free to use any character to represent each digit of the radix chosen, as long the choice is consistent throughout all inputs and output.

The function will always be called with the same number of inputs.

The submission should always terminate and return a result, that is, it cannot loop indefinitely.

The function should always give deterministic output.

The submission should theoretically work for any input, including those outside of the used numeric data types.

A proof accompanying your answer is appreciated, but not required.

---

This challenge was drafted thanks to the helpful commenters at its Sandbox.

# Answer
# Haskell, 29 bytes

```
(+1)?(2?)
z?f=(iterate f z!!)

```

Try it online!

An Ackermann-like function. Starting the base numerical value at `2` makes for a simple base case. An annoying number of bytes are spent converting the arguments order for "apply `f` `n` times starting from `z`" from `iterate f z!!n` to `(?) z f n` which can be curried nicely.

Same thing written more explicitly for 2 bytes longer:

**31 bytes**

```
0%n=n+1
m%n=iterate((m-1)%)2!!n

```

Try it online!

Another alternative to the original is to flip the two arguments to `?`, allowing it to be defined in a point-free way for the same byte count.

**29 bytes**

```
(?2)?(+1)
(?)=((!!).).iterate

```

Try it online!

**29 bytes**

```
(?2)?(+1)
(?)f=(!!).iterate f

```

Try it online!

**31 bytes**

```
n?0=n+1
0?m=2
n?m=(n-1)?m?(m-1)

```

Try it online!
> 6 votes

# Answer
# C (gcc) -lm, ~~268~~ ~~197~~ 194 bytes

```
x[9];e(n,c){int w=sqrt(n/6*8+1)/2-.5,b=n/6+w*~w/2,*z=x+b;for(n%=6;c--;)n-2?n-3?n-4?n-5?x[w-b]=n?*z:b:e(w-b,*z):e(w-b,1,e(b,1)):*z&&--*z:++*z;}main(n){e(x[1]=n,scanf("%d",&n));printf("%d",1+*x);}

```

Try it online!

*Now 3 more bytes off thanks to @ceilingcat again (saving a pointer `z` to `x[b]`, and then using `*z` instead of `x[b]` throughout).*

*Thanks to C golfing expert @ceilingcat for reducing this by an amazing 71 bytes!*

---

I decided to write an answer that works completely differently from the other solutions posted so far. This uses diagonalization of the primitive recursive functions (it's not a function that grows faster than any primitive recursive function, the way the Ackermann and Sudan functions do).

I don't think there's any way to golf this to be as short as the Ackermann or Sudan programs, but it has two advantages: (1) It's easy to understand the proof that it's not primitive recursive, and (2) you can actually run it on reasonably sized inputs without running out of time or getting stack overflows!

---

The basic idea behind this function \\$F\\$ is first to enumerate all programs to compute primitive recursive functions of one variable. Let \\$P\_0, P\_1, ...\\$ be this enumeration. Then, for any input \\$n,\\$ here's how to compute \\$F(n)\\$: First supply \\$n\\$ as input to the program \\$P\_n\\$ and run that. When \\$P\_n\\$ halts with an integer as output (as it's guaranteed to do, because it's computing a primitive recursive function), add \\$1\\$ to that output. That's \\$F(n).\\$

\\$F\\$ is clearly total.

Now,

* \\$F\\$ is not the function computed by \\$P\_0\\$ because \\$F(0)\\$ is one higher than the output of \\$P\_0\\$ on input \\$0,\\$
* \\$F\\$ is not the function computed by \\$P\_1\\$ because \\$F(1)\\$ is one higher than the output of \\$P\_1\\$ on input \\$1,\\$
* \\$F\\$ is not the function computed by \\$P\_2\\$ because \\$F(2)\\$ is one higher than the output of \\$P\_2\\$ on input \\$2,\\$

etc. In general, \\$F\\$ isn't the function computed by \\$P\_n,\\$ because \\$F(n)\\$ is one higher than the output of \\$P\_n\\$ on input \\$n.\\$

So \\$F\\$ isn't the same as the function computed by any of the programs \\$P\_n.\\$ But those are all the primitive recursive functions. So \\$F\\$ isn't primitive recursive.

---

The way I enumerate all the primitive recursive functions is by implementing a variant of Uwe Schöning's programming language LOOP. It is known that the functions computable by a LOOP program are precisely the primitive recursive functions. (These programs actually cover all primitive recursive functions, not just the primitive recursive functions of one variable, even though that's ultimately all we would need.)

My variant miniLOOP is even simpler than the original language. Just as in LOOP, there are variables \\$x\_0, x\_1, x\_2, \dots\\$; each of these variables can hold a natural number (a non-negative integer). To use a miniLOOP program to compute a function of \\$k\\$ variables, you store the values of the \\$k\\$ arguments in \\$x\_1, \dots, x\_k,\\$ and then run the program. The output is the value of \\$x\_0\\$ at the end.

Here are the basic programming statements available in miniLOOP (all variables are restricted to the natural numbers):

* \\$x\_n=m,\\$
* \\$x\_n=x\_m,\\$
* \\$x\_n\\$++ (increment),
* \\$x\_n\\$-- (decrement except that if \\$x\_n\\$ is equal to 0, its value is left unchanged, because we don't allow negative numbers).

Statements can also be constructed from other statements using the following two constructs:

* \\$P;Q\\$ where \\$P\\$ and \\$Q\\$ are statements; this means to execute \\$P\\$ first and then \\$Q.\\$
* \\$\text{LOOP } x\_n \text{ DO } P \text{ END},\\$ which means to execute \\$P\\$ repeatedly, \\$x\_n\\$ times in a row. (Repeating it 0 times means not doing it at all, of course.) Note that the number of repetitions is the value that \\$x\_n\\$ has when the loop starts. Even if the body of the loop changes the value of \\$x\_n,\\$ the number of repetitions won't change. This is the key thing that makes this an implementation of primitive recursion.

---

For example, the following program doubles its input:

```
LOOP x1 DO x1++ END
x0 = x1

```

(Recall that a function of one variable takes its input in \\$x\_1\\$ and leaves its output in \\$x\_0.\\$)

---

You can check that even though miniLOOP is a bit simpler than the LOOP language defined in the Wikipedia article, you can simulate all the LOOP constructs with miniLOOP programs. So miniLOOP also computes precisely the primitive recursive functions.

---

Every miniLOOP program is assigned a number; that is how we enumerate them. This enumeration uses the Cantor pairing function

$$\pi(x,y)=\frac{(x+y)(x+y+1)}{2}+y.$$

Here is the numerical assignment:

* \\$x\_n=c\\$ is assigned the number \\$6 \pi(n,c).\\$
* \\$x\_n=x\_m\\$ is assigned the number \\$6 \pi(n,m)+1.\\$
* \\$x\_m\\$++ is assigned all the numbers \\$6 \pi(n,m)+2\\$ for any \\$n\\$ (it doesn't matter that one program can be included multiple times in the enumeration).
* \\$x\_m\\$-- is assigned all the numbers \\$6 \pi(n,m)+3\\$ for any \\$n.\\$
* \\$P;Q\\$ is assigned all the numbers \\$6 \pi(q,p)+4\\$, where \\$p\\$ is assigned to \\$P\\$ and \\$q\\$ is assigned to \\$Q.\\$ (\\$q\\$ and \\$p\\$ are "backwards" in this formula only because this is code golf and I ended up saving a few bytes by doing it that way.)
* \\$\text{LOOP } x\_n \text{ DO } P \text{ END}\\$ is assigned the numbers \\$6 \pi(p,n)+5,\\$ where \\$p\\$ is a number assigned to \\$P.\\$

Note that every number is assigned to a unique program. (A program can have more than one number assigned to it, but a number is associated with exactly one program.) And it's easy to take a number and figure out what program it's assigned to.

For example, you can check that the program above that doubles its input is assigned 1667230. This is computed as \\$6 \pi(13,731)+4,\\$ where \\$13 =6\pi(0,1)+1\\$ and \\$731=6\pi(14,1)+5.\\$ In that last formula, \\$14=6\pi(0,1)+2.\\$

---

In the C program, \\$x\\$ is a global array holding all the variables needed for what you're running. I've only declared it to hold 9 variables, since that's plenty for demonstrating it, but in practice you would really want to allow that to grow using `malloc` as needed.

The function `e` takes an input `n` and runs the miniLOOP program assigned to `n`. It assumes that `x[1], ..., x[k]` have already been set up as desired for the input, and it leaves the output in `x[0]`.

The main program simply takes its input `n`, stores it in `x[1]`, and calls `e(n)` to run the miniLOOP program assigned to `n`. It then adds `1` to the output and prints that as the output of the main program.

As described in the outline at the beginning, this program halts on every input. But it's not primitive recursive, since it disagrees with miniLOOP program number `n` (at input `n`), and those miniLOOP programs compute all the primitive recursive functions.

The TIO link shows what this program does with input `1667230`. Recall that `1667230` is assigned to a miniLOOP program that doubles its input, and you can see that the output of the main program here is `3334461` (which is not equal to double 1667230, being one higher, as intended).
> 6 votes

# Answer
# Haskell, (Ackermann-like) 31 bytes

*Inspiration from this answer.*

```
0%x=x+1
n%x=iterate((n-1)%)x!!x

```

Try it online!

Or if \\$g^n\\$ is \\$n\\$ compositions of \\$g\\$ then

\\$ f\_0(x)=x+1 \\ f\_n(x)=f\_{n-1}^x(x) \\$

This function appears here with a proof that it is not primitive recursive.

# Haskell, (Ackermann) 39 bytes

```
0%n=n+1
m%0=(m-1)%1
m%n=(m-1)%(m%(n-1))

```

Try it online!

# Haskell, (Sudan) 45 bytes

```
(n#x)y|n<1=x+y|y<1=x|q<-n#x$y-1=(n-1)#q$q+y+1

```

Try it online!
> 5 votes

# Answer
# dc, 76 bytes

```
?sysxsn[lx+q]sp[lydln*0=ply1-sylFxdSxly1+dsy+Syln1-snlFxln1+snLxsDLysD]dsFxp

```

Try it online!

This implements Sudan's function, which I believe was the first computable but non-primitive-recursive function discovered. It grows faster than any primitive recursive function.

Three space-separated arguments \\$n, x,\\$ and \\$y\\$ are read from stdin, and the output \\$F(n, x, y)\\$ is written to stdout.

The function grows so quickly that you need something like dc that supports arbitrarily large integers to have a chance at computing any interesting examples at all.

I'll post an explanation later (dc is a pain to document), but the TIO link shows how large its outputs get: \\$F(2,11,2)\\$ is 16,031 digits long! This appears to be the largest example I can compute on TIO without overflowing the stack (due to the heavy use of recursive calls).

The Wikipedia link above has a table of sample outputs. You can run my program at TIO and see that it matches the ones that Wikipedia shows.

There's a proof that it's not primitive recursive in Theories of Computational Complexity, by Cristian Calude.
> 4 votes

# Answer
# Zpr'(h, 81 bytes

```
(a () .n)|>(S n)
(a (S .k) ())|>(a k (S ()))
(a (S .k) (S .n))|>(a k (a (S k) n))

```

```
<| constants.zpr
main |> (a 3 4)

```

# Execution

```
stdlib % ../Zprh --de-peano above.zpr
125

```

# Explanation

```
; implementation of the Ackermann-Peter function in Zpr'(h

; base case for k = 0
(ackermann-peter () .n)         |> (S n)

; base case for n = 0
(ackermann-peter (S .k) ())     |> (ackermann-peter k (S ()))

; general case for k, n > 0
(ackermann-peter (S .k) (S .n)) |> (ackermann-peter k (ackermann-peter (S k) n))

; include integer constants
<| constants.zpr

; test the implementation
main |> (ackermann-peter 3 4)

```
> 3 votes

# Answer
# Python Ackermann, ~~78~~ \\$\cdots\\$ ~~59~~ 45 bytes

Save 2 bytes (in pre production) thanks to user41805!!!

```
A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n

```

Try it online!

Going with FryAmTheEggman's most excellent advice and implementing the Ackermann function.
> 2 votes

# Answer
# C (gcc) Ackermann, ~~37~~ 36 bytes

```
A(m,n){m=m?A(m-1,n?A(m,n-1):1):n+1;}

```

Try it online!
> 2 votes

# Answer
# JavaScript (Node.js),  ~~81~~  76 bytes

An inefficient but non-recursive1 implementation of the Ackermann function, accepting either Numbers or BigInts.

Given enough time and memory, this should work in theory for any pair \\$(m,n)\\$.

Takes input as `([m])(n)`.

```
s=>n=>eval("for(;s+s;){(m=s.pop())?s.push(~-m)&&n?s.push(n--&&m):n++:n++}n")

```

Try it online!

---

*1: By 'non-recursive', I mean that there's no recursive function call. Therefore, the code does not depend on the size of the call stack, which is always bounded regardless of the total amount of available memory. Instead, it's using its own stack `s[]`.*
> 1 votes

# Answer
# Retina 0.8.2, 51 bytes

```
\d+
$*
{`((1*)1,1*)1$
$2,$1
1,$
,1
}`\B,(1*)$
1$1
1

```

Try it online! An implementation of the Ackermann function in unary arithmetic, so don't try to compute anything larger than `A(4, 1)` on TIO. Explanation:

```
\d+
$*

```

Convert to unary.

```
{`
}`

```

Repeat the steps until there is only one value left on the stack.

```
((1*)1,1*)1$
$2,$1

```

If the top of the stack is `m+1, n+1` then decrement the latter to `n` and push a copy of `m` below `m+1` so the stack is now `m, m+1, n`.

```
1,$
,1

```

If the top of the stack is `m+1, 0` then decrement the former to `m` and increment the latter to `1`.

```
\B,(1*)$
1$1

```

If the top of the stack is `0, n` then remove the `0` and increment `n`.

```
1

```

Convert to decimal.
> 1 votes

# Answer
# APL (Dyalog Unicode), 16 bytes

```
{×⍺:∇⍣⍵⍨⍺-1⋄2+⍵}

```

Try it online!

This function \\$ f(\alpha,\omega) \\$ is a variation of the commonly-known Ackermann function, which turns out as follows:

$$ \begin{align} f(0,\omega)&= 2+\omega \\ f(1,\omega)&= 2\times\omega \\ f(2,\omega)&= 2^\omega \\ \end{align} $$

But the pattern doesn't extend for \\$ \alpha \ge 3 \\$.

### How it works

```
{×⍺:∇⍣⍵⍨⍺-1⋄2+⍵}
{×⍺:           }   ⍝ If ⍺ is nonzero,
    ∇⍣⍵⍨⍺-1        ⍝ Compute this expression, which expands to...
    (⍺-1)(∇⍣⍵)⍺-1  ⍝   Recursively call self with left arg ⍺-1, ⍵ times
                   ⍝   on the starting value of ⍺-1
           ⋄2+⍵    ⍝ Otherwise, return 2+⍵

```
> 1 votes

# Answer
# MMIX, Ackermann, 60 bytes (15 instrs)

(jxd)

```
00000000: 5a000003 23000101 f8010000 5a010004  Z¡¡¤#¡¢¢ẏ¢¡¡Z¢¡¥
00000010: e3010001 27000001 f1fffffa c1040000  ẉ¢¡¢'¡¡¢ȯ””«Ḋ¥¡¡
00000020: 27050101 fe020004 f303fff6 f6040002  '¦¢¢“£¡¥ṙ¤”ẇẇ¥¡£
00000030: c1010300 27000001 f1fffff2           Ḋ¢¤¡'¡¡¢ȯ””ṗ

```

Disassembly and explanation:

```
ack PBNZ  $0,0F     // if(!m)
    ADDU  $0,$1,1
    POP   1,0       // return n + 1
0H  PBNZ  $1,0F     // if(!n)
    SETL  $1,1
    SUBU  $0,$0,1
    JMP   ack       // return ack(m - 1, 1)
0H  SET   $4,$0
    SUBU  $5,$1,1
    GET   $2,rJ
    PUSHJ $3,ack
    PUT   rJ,$2
    SET   $1,$3     // n = ack(m, n - 1)
    SUBU  $0,$0,1   // m--
    JMP   ack       // return ack(m,n)

```
> 0 votes

---
Tags: code-golf, math, open-ended-function
---


title: Base-ically Guard

text:
# Question
Title: Base-ically Guard
Base: part 1

This is part 2, Strongly suggest you go try out the first one if you haven't tried it.

## Story

As one of the solvers, You've managed to get to the door of the base heaven. In front of the door stands the base guard @lyxal, they were angry that you all just left the encoded text on the ground, they demand that you clean (decode) the ground before joining the party, those who are irresponsible get no ticket!

## Task

You will get 2 inputs

* First being `X` which is a non-negative integer in base of base list.
* Second being base which is a list of bases.
* bases range from 1 ~ 10
* The base will contain at least one not `1` base
* answer should be in the base 10

Example:

```
X, [bases] -> answer
110 ,[2] -> 6
30 ,[2,4] -> 6
2100 ,[2,3] -> 30
0 ,[any bases] -> 0
You may want to look at part 1 for more detail

```

# Rule

* No loopholes
* Input/Output in any convenient, reasonable format is accepted.

Satisfy Lyxal with the shortest code, because a long code indicates that you are lazy and not doing your best!

# Answer
> 8 votes
# APL(Dyalog Unicode), 6 bytes SBCS

```
⍴⍨∘≢⊥⊢

```

Try it on APLgolf!

An anonymous tacit infix function taking the base in reverse as left argument and `X` as a list of digits as right argument.

X

evaluated in base…

`⍴⍨∘≢` base cyclically reshaped to the length of `X`

# Answer
> 7 votes
# Jelly, 7 bytes

Takes the bases in reverse order as the first argument and the digits as the second argument.

```
ṁżṛḅ@ƒ0

```

Try it online!

## Explanation

```
ṁżṛḅ@ƒ0   Main dyadic link
ṁ         Reshape the list of bases like the list of digits
 ż        Zip with
  ṛ         the list of digits
     ƒ0   Reduce with initial value 0 under:
   ḅ        Convert from base
    @         [with swapped arguments]

```

# Answer
> 6 votes
# Jelly, 7 bytes

```
ṁḊ1;×\ḋ

```

Try it online!

-1 byte thanks to Jonathan Allan

```
ṁ        Mold bases to the shape/length of the digits, repeating if necessary
 Ḋ       Drop the first base
  1;     and prepend 1 in its place
    ×\   Cumulatively reduce the bases by multiplication
      ḋ  Dot product with the digits

```

# Answer
> 5 votes
# Pyth, 16 bytes

```
JEs*L*F<t*JlQ~hZ

```

Test suite

Inspired quite heavily by hyper-neutrino's Jelly answer.

Takes reversed list of digits of X on line 1 and reversed list of bases on line 2 of input.

Explanation:
```
JEs*L*F<t*JlQ~hZ  | Full program
JEs*L*F<t*JlQ~hZQ | with implicit variables
------------------+-------------------------------------------------------------------
                  | Call the first line of input Q (implicit)
JE                | Call the second line of input J
    L           Q | Map the following over each d in Q:
     *F           |  Find the product of
       <     ~hZ  |   the first Z (starts at 0, increments with each pass) elements of
         *JlQ     |    J, repeated the length of Q times
        t         |   with the first element removed (product of an empty list is 1)
   *L             |  and multiply it with d
  s               | Sum the resulting list
                  | Print (implicit)

```

# Answer
> 5 votes
# Vyxal `s`, 8 bytes

```
•Ḣ1p⁽*r*

```

Try it Online!

```
•Ḣ1p⁽*r*  Full Program
•         Mold bases like digits
 Ḣ        Pop first base off
  1p      Prepend 1
      r   Cumulative reduce over
    ⁽*    Multiplication
       *  Vectorized multiplication with digits

s (flag)  Sum

```

# Answer
> 5 votes
# Haskell, 32 bytes

```
(x:y)?(h:t)=x+h*y?(t++[h])
_?_=0

```

Try it online!

The relevant function is `(?)`, which takes as input `X` as a list of digits (least significant first) and the list of bases.

# Haskell, 35 bytes

```
(foldr(\(i,d)n->d+i*n)0.).zip.cycle

```

Try it online!

Same algorithm in point-free style. Takes the list of digits first and then `X`.

# Answer
> 4 votes
# Husk, 9 8 bytes

```
δṁ*G*1t¢

```

Try it online!

Same idea as hyper-neutrino's answer.

-1 byte from Leo.

# Answer
> 3 votes
# JavaScript (V8), ~~60~~ ~~55~~ 52 bytes

```
n=>b=>(g=r=>x in n?g(n[x]+r*b[++x%b.length]):r)(x=0)

```

Try it online!

# Answer
> 3 votes
# Retina, 90 bytes

```
$
;
+`(\d+,)(.*,)?(\d+)(\d);
$2$1$3;$4
+`(.*,)?(\d+,)(\d+);(\d)
$2$1$.($2*$3*_$4*);
.*,|;

```

Try it online! Link includes test cases. Takes `X` as the last argument. Explanation:

```
$
;

```

Append a marker to keep track of the current digit.

```
+`(\d+,)(.*,)?(\d+)(\d);
$2$1$3;$4

```

Cyclically rotate the list of bases according to the number of digits.

```
+`(.*,)?(\d+,)(\d+);(\d)
$2$1$.($2*$3*_$4*);

```

Cyclically rotate the list of bases back again as each digit is converted from the next base.

```
.*,|;

```

Remove the list of bases and the marker.

# Answer
> 3 votes
# Charcoal, 13 bytes

```
ＩΣＥ⮌θΠ⊞Ｏ…ηκＩι

```

Try it online! Link is to verbose version of code. Takes `X` as a string. Explanation:

```
    θ           First input (X)
   ⮌            Reversed
  Ｅ             Map over characters
            ι   Current character
           Ｉ    Cast to integer
      ⊞Ｏ        Push to list
         η      Second input (list of bases)
        …       Cyclically chopped to length
          κ     Current index
     Π          Take the product
 Σ              Take the sum
Ｉ               Cast to string
                Implicitly print

```

Although it only takes 1 byte to multiply the current character by the product of the list Charcoal's product returns None for an empty list and it would cost 2 bytes to correct this, so it's easier to push the value to the list so that the product is always defined.

# Answer
> 2 votes
# JavaScript (V8), 45 bytes

```
(b,i)=>g=X=>X&&X%10+b[i=b[++i]?i:0]*g(X/10|0)

```

Try it online!

# Answer
> 2 votes
# C (gcc), 70 bytes

```
a;i;r;f(x,b,l)int*b;{for(a=1,r=i=0;x;x/=10)r+=x%10*a,a*=b[i++%l];x=r;}

```

Try it online!

Inputs a non-negative integer in base 10, a pointer to the array of bases, and the array's length (since C pointers don't carry any length info).

---
Tags: code-golf, number, base-conversion
---


title: Base-ically god

text:
# Question
Title: Base-ically god
## Story

The god of base is opening heaven’s gate for mortals to join the base party. You, as one of the believers, want to follow their steps to ascend to heaven.

But not everyone can get in.

The god posts this question to let you prove you are worthy of their party.

## Task

You will get 2 inputs

* First being `X` which is a non-negative integer in base 10.
* Second being `base` which is a list of bases to iterate over.
* **bases will always be positive integers which in range of 1~10**
* The base will contain at least one not `1` base

You will need to present(print) `X` in the form of iterating bases.

Example:

```
X ,[base] -> ans

6 ,[2] -> 110
It has only 1 base in base list, thus it converts number into base2

6 ,[2,4] -> 30
First base is 2, so 6%2=0 is the first digit and (6-0)/2 =3 is forwarded to next base.
Second base is 4, so 3%4=3 is the second digit and there is no remaining.

30 ,[2,3] -> 2100
First two digits come from 30%2=0, 15%3=0, with 15/3=5 is passed to next base,
which loops back to 2 => 5%2 = 1,pass 2=> 2%3 = 2

10 ,[9,2] -> 11
20 ,[3,4,5] -> 122
0 ,[any bases] -> 0

```

## Rules

* No standard loopholes
* Input, output in any reasonable, convenient format is accepted.

The god requires short code—they will give access to the shortest code in each language. Fulfill their task to ascend!

# Answer
# APL(Dyalog Unicode), 8 bytes SBCS

A re-implementation of Jonah's answer.

```
10⊥⌽⍤⍴⊤⊣

```

Try it on APLgolf!

An anonymous tacit infix function taking `base` on the right and `X` on the left.

the value `X`

represented in base…

`⌽⍤⍴` reversed `base` cyclically-repeated until length `X`

`10⊥` evaluated as base-10
> 6 votes

# Answer
# Stax, ~~13 11~~ 10 bytes

```
╨¬ª₧}ÄM☻☻.

```

Run and debug it

Having another stack based language to compete with gave some golfing motivation.

## Explanation

```
n^*{|%mr$A|b
n^*               repeat bases X+1 times
   {  m           map to
    |%            divmod(puts quotient on stack for next iteration)
       r          reverse
        $         join to string
         A|b      interpret as base 10

```
> 4 votes

# Answer
# , 12 11 bytes

```
10#.|.@$#:[

```

Try it online!

-1 after reading Adam's APL answer and realizing I could get rid of the `~`. Other than that, we both found the exact same answer.

J has a mixed base primitive that does the heavy lifting `#:`.

* `|.@$~` Repeat the base as man times as the number we're converting, and then reverse. Extra left digits will become 0, and this ensures we always have enough digits.
* `#:]` Using the previous result, convert the input using mixed base.
* `10#.` Convert back to a base 10 number to remove the extra zeros.
> 4 votes

# Answer
# Python 3, 41 bytes

A massive improvement from my previous solution, based on a clever observation by @att, to use the fact that bases are \\$ \le 10 \\$.

```
f=lambda x,y,*b:x and 10*f(x//y,*b,y)+x%y

```

Try it online!

### Python 3, 48 bytes

Outputs the number as a list of digits. A couple of bytes are needed to handle the edge cases where \\$ X = 0 \\$.

```
f=lambda x,y,*b:x//y and f(x//y,*b,y)+[x%y]or[x]

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 11 bytes

```
sиvy‰`s}JRï

```

I have the feeling this can be shorter, but I'm a bit rusty on code-golfing.

Takes the list of bases as first input and integer \\$X\\$ as second input.

Try it online or verify all test cases.

**Explanation:**

```
s        # Swap the two (implicit) inputs, so the stack is bases-list, integer X
 и       # Repeat the bases-list X amount of times
  v      # Loop over each value `y` in this list:
   y‰    #  Divmod `y` ([v//y, v%y]), which will use the second (implicit) input-integer
         #  X as value in the very first iteration
     `   #  Pop this list, and push both separated to the stack
      s  #  Swap their order, so the v//y is at the top, as value for the next iteration
  }J     # After the loop: join all integers on the stack together
    R    # Reverse it
     ï   # And cast it to an integer to remove any leading 0s
         # (after which the result is output implicitly)

```
> 3 votes

# Answer
# Python 3, 57 bytes

```
f=lambda x,a,*b,j=0:x and f(x//a,*b[1:],a,j=[])+[x%a]or j

```

Try it online!

-5 bytes borrowing the idea from Arnauld to use splat.
> 2 votes

# Answer
# JavaScript (ES6), 43 bytes

```
f=(n,[b,...a])=>n&&+f(n/b|0,[...a,b])+[n%b]

```

Try it online!
> 2 votes

# Answer
# Haskell, 41 bytes

```
0?_=0
n?(h:t)=mod n h+10*div n h?(t++[h])

```

Try it online!
> 2 votes

# Answer
# MathGolf, 15 bytes

```
ê├Ä_]─k\É‼%/]xy

```

First input is \\$X\\$, all other inputs are the values in the bases-list.

Try it online.

**Explanation:**

```
ê         # Push all inputs as an integer-list
 ├        # Pop its first item (the integer X), and push it to the stack
  Ä       # Loop that many times, using a single character as inner code-block:
   _      #  Duplicate the list at the top of the stack
  ]       # After the loop, wrap all list on the stack into a list
   ─      # Flatten this list of lists of integers
    k     # Push the first integer-input X again
     \    # Swap, so the list we created earlier is at the top of the stack
      É   # For-each over this list, using three characters as inner code-block:
       ‼  #  Apply the following two commands separated on the top value:
        % #   Modulo
        / #   Integer-divide
      ]   # After the loop, wrap all values on the stack into a list
       x  # Reverse this list
        y # Join it together, and convert it to an integer, removing leading 0s
          # (after which the entire stack joined together is output implicitly as result)

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), ~~38~~ 39 bytes

```
#>=#2&&#0[⌊#/#2⌋,##3,#2]||#~Mod~#2&

```

Try it online!

Input `[X, bases..]`. Returns an `Or` of digits.

`MixedRadix` exists and would perform the task easily (in conjunction with `IntegerDigits`), but it isn't cyclic.
> 2 votes

# Answer
# Pyth, 23 bytes

```
M|&J/GhHagJ.<H1%GhH]GgF

```

Test suite

Direct translation of dingledooper's Python 3 answer.

## Pyth, 25 bytes

```
AQWG=+k%G@HZ~/G@H~hZ)|_k0

```

Test suite

Naïve solution. Surprised it's only 2 bytes longer...
> 1 votes

# Answer
# , ~~66~~ ~~59~~ ~~58~~ 55 bytes

*Edit: -7 bytes thanks to att's comment on dingledooper's answer: previous version uselessly worried about handling bases \>10*

```
f=function(n,b)`if`(n,10*f(n%/%b,c(b[-1],b))+n%%b,0)[1]

```

Try it online!
> 1 votes

# Answer
# C (gcc), 82 bytes

```
a;c;i;r;f(x,b,l)int*b;{for(a=1,r=i=0;x;x/=c)c=b[i++%l],r+=x%c*a,a*=10,x-=x%c;x=r;}

```

Try it online!

Inputs a non-negative integer in base \\$10\\$, a pointer to the array of bases, and the array's length (since C pointers don't carry any length info).
> 1 votes

# Answer
# Retina 0.8.2, 65 bytes

```
\d+
$*_
+`^(_+),(?>(.*,)?)(\1)+(_*)
$2$1,$#3$*_$.4
(_+,)+(_*)
$.2

```

Try it online! Link includes test cases. Takes `X` as the last argument. Explanation:

```
\d+
$*_

```

Convert to unary.

```
+`^(_+),(?>(.*,)?)(\1)+(_*)

```

Repeat until `X` is less than the first base, divmod `X` by that, and...

```
$2$1,$#3$*_$.4

```

... move the first base to the end, then append the quotient in unary and the remainder in decimal (ironically Retina gives me the quotient in decimal and the remainder in unary...).

```
(_+,)+(_*)
$.2

```

Convert the final digit to decimal. This also handles the `0` case.
> 1 votes

# Answer
# Pari/GP, 68 bytes

Solved via recursion: we keep storing the modulo, dividing by the base, and drilling down until we hit zero. Then we print each digit on the way back up.

```
f(n,v)=my(m=n%v[1]);n\=v[1];n&&f(n,vector(#v,i,v[i%#v+1]));print1(m)

```

Try it online!
> 1 votes

# Answer
# Python 3, 77 bytes

Returns in list.

```
def f(x,b,s=[],n=0):
 while x:s,x,n=[x%b[n]]+s,x//b[n],(n+1)%len(b)
 return s

```

Try it online!

```
while x:

```

Keeps self-updating while **X** is larger than the selected element in **\[base\]**.
> 1 votes

# Answer
# Charcoal, 20 bytes

```
Ｆ¬θ0ＷθＦη¿θ«←Ｉ﹪θκ≧÷κθ

```

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

```
Ｆ¬θ0

```

Special-case an input of `0`.

```
ＷθＦη¿θ«

```

While the input is non-zero, loop over all the bases while the input is non-zero.

```
←Ｉ﹪θκ

```

Output the next digit in reverse order.

```
≧÷κθ

```

Divide by the base.
> 0 votes

---
Tags: code-golf, number, base-conversion
---


title: Inverse Ax+B/Cx+D sized function

text:
# Question
Title: Inverse Ax+B/Cx+D sized function
Let's assume that

$$ f(x) = \frac{Ax+B}{Cx+D} $$

Where, \\$x\\$ is a variable and \\$A\\$,\\$B\\$,\\$C\\$,\\$D\\$ are constants.

Now we have to find out the inverse function of \\$f(x)\\$, mathematically \\$f^{-1}(x)\\$, To do this first we assume,

$$ y = f(x) \\\rightarrow y=\frac{Ax+B}{Cx+D} \\\rightarrow Cxy+Dy=Ax+B \\\rightarrow Cxy-Ax=-Dy+B \\\rightarrow x(Cy-A)=-Dy+B \\\rightarrow x=\frac{-Dy+B}{Cy-A} $$

Then, we know that

$$ y=f(x) \\\rightarrow f^{-1}(y)=x \\\rightarrow f^{-1}(y)=\frac{-Dy+B}{Cy-A} ..... (i) $$

And from \\$(i)\\$ equation, we can write \\$x\\$ instead of \\$y\\$

$$ \\\rightarrow f^{-1}(x)=\frac{-Dx+B}{Cx-A} $$

So, \\$\frac{-Dx+B}{Cx-A}\\$ is the inverse function of \\$f(x)\\$

This is a very long official mathematical solution, but we have a "cool" shortcut to do this:

1. Swap the position of the first and last constant diagonally, in this example \\$A\\$ and \\$D\\$ will be swapped, so it becomes:

$$ \frac{Dx+B}{Cx+A} $$

2. Reverse the sign of the replaced constants, in this example \\$A\\$ is positive (\\$+A\\$) so it will be negative \\$-A\\$, \\$D\\$ is positive (\\$+D\\$) so it will be negative \\$-D\\$

$$ \frac{-Dx+B}{Cx-A} $$

And VOILA!! We got the inverse function \\$\frac{Ax+B}{Cx+D}\\$ in just two steps!!

---

# Challenge

**(Input of \\$\frac{Ax+B}{Cx+D}\\$ is given like `Ax+B/Cx+D`)**

Now, let's go back to the challenge.

Input of a string representation of a function of \\$\frac{Ax+B}{Cx+D}\\$ size, and output its inverse function in string representation.

I have just shown two ways to that (Second one will be easier for programs), there may be other ways to do this, good luck!

# Test cases

**(Input of \\$\frac{Ax+B}{Cx+D}\\$ is given like `Ax+B/Cx+D`)**

```
4x+6/8x+7 -> -7x+6/8x-4
2x+3/2x-1 -> x+3/2x-2
-4x+6/8x+7 -> -7x+6/8x+4
2x+3/2x+1 -> x+3/2x+2

```

**Or you can give it using list of A,B,C,D**

```
4,6,8,7 -> -7x+6/8x-4

```

Or you can output `-7,6,8,-4`

# Rules

* **Input is always in \\$\frac{Ax+B}{Cx+D}\\$ size, and is guaranteed to be valid.**
* Standard loopholes are forbidden.
* Trailing/Leading whitespace in output is allowed.
* If possible, please link to an online interpreter (e.g. TIO) to run your program on.
* Please explain your answer. This is not necessary, but it makes it easier for others to understand.
* Languages newer than the question are allowed. This means you could create your own language where the empty program calculates this number, but don't expect any upvotes.
* This is , so shortest code in bytes wins!

(Some terminology might be incorrect, feel free ask me if you have problems)

# Answer
> 4 votes
# Perl 5, 27 bytes

```
sub{@_[0,3]=map-$_,@_[3,0]}

```

Try it online!

# Answer
> 4 votes
# Retina 0.8.2, 48 bytes

```
^-
+
^\d
-$&
(.\d+)(.*)([-+].+)
$3$2$1
^-

^\+
-

```

Try it online! Link includes test cases. Assumes that `1x` is always written as such. Explanation:

```
^-
+
^\d
-$&

```

Negate and enforce the sign on `A`.

```
(.\d+)(.*)([-+].+)
$3$2$1

```

Swap `A` and `D`.

```
^-

^\+
-

```

Negate `D`, removing the sign if it was negative.

# Answer
> 4 votes
# Vyxal, 9 bytes

```
÷↭⫙'N^N^W

```

Try it Online!

## Explained

```
÷↭⫙'N^N^W
÷          # Push every item of the input onto the stack
 ↭        # And rotate the top three items: [a, b, c, d] → [a, d, b, c]
   ⫙'      # Rotate the entire stack left
     N^N^W # Negate the top and bottom of the stack and wrap into a list

```

# Answer
> 4 votes
# brainfuck, ~~31~~ 29 bytes

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

```

Commented:

```
,            #input A into cell 0
[-<->]       #decrement cells 0 and -1 until cell 0 contains 0 and cell -1 contains -A
,>,>,        #input B,C,D into cells 0,1,2
[->-<]       #decrement cells 2 and 3 until cell 2 contains 0 and cell 3 contains -D
>.<<<.>.<<.  #output -D,B,C and -A

```

Try it online!

Very rarely, a challenge comes along where Brainfuck is somewhat competitive.

Takes 4 bytes as input, gives 4 bytes as output.

The normal form of interface for Brainfuck is an ASCII terminal, so the input `ABCD` in the TIO link is intrepreted as `[65,66,67,68]`. Outputs are per the table below. Note that signed negative numbers are treated as their unsigned 8 bit counterparts, and give extended ASCII output in the range 128-255, in accordance with https://en.wikipedia.org/wiki/Extended\_ASCII#/media/File:Table\_ascii\_extended.png

```
Input             Signed Output    Unsigned equivalent ASCII output
A=65              -65              191                  ¿
B=66               66               66                  B
C=67               67               67                  C
D=68              -68              188                  ¼

```

After swapping A and D, we arrive at the required output `[-68,66,67,-65]`, which in ASCII looks like `¼BC¿`

# Answer
> 4 votes
# Keg, ~~7~~ 6 bytes (SBCS)

Input as a list. Outputs by values on the stack.

Footer outputs entire stack joined by newlines.

```
÷±'±$"

```

Try it online!

## Explanation

```
        # Input as a list    (e.g. [4, 6, 8, 7])
÷       # Dump it onto stack (Stack = [ 4, 6, 8, 7])
 ±      # Negate TOS         (Stack = [ 4, 6, 8,-7])
  '     # Shift left         (Stack = [ 6, 8,-7, 4])
   ±    # Negate TOS         (Stack = [ 6, 8,-7,-4])
    $   # Exchange TOS       (Stack = [ 6, 8,-4,-7])
     "  # Shift right        (Stack = [-7, 6, 8,-4])

```

### Footer explanation

```
^        # Reverse the stack (So that the first item of TOS is outputted first)
 ∑       # Apply to entire stack:
  .      # Output TOS as integer
   19+,  # Print a trailing newline

```

## Credits

* Saved 1 byte thanks to @Lyxal

# Answer
> 4 votes
# PowerShell, 43 bytes

Takes input as and outputs as an array.

```
$n=$args;-1,1,2,-4|%{$n[$_]*(2*($_-gt0)-1)}

```

Try it online!

### Less Fun PowerShell, 31 bytes

```
param($a,$b,$c,$d)-$d,$b,$c,-$a

```

Try it online!

### Most Unfun PowerShell, 30 bytes

```
-$args[3],$args[1,2],-$args[0]

```

Try it online!

### Least Useful PowerShell, 26 bytes

```
"-{3},{1},{2},-{0}"-f$args

```

Try it online!

# Answer
> 3 votes
# Dash, 23 bytes

```
$((-$4)) $2 $3 $((-$1))

```

Try it online!

## Usage

Requires positional parameters for each of A, B, C, and D. Before evaluating the command. Also the code evaluates to just four strings, so run `echo` command with those code (may not portable when D is originally positive, as hyphen-parameter may be treated as an option).

## How it works

* dollar-double-parentheses is arithmetic expansion.

---

# Polyglot for Bash, OSH, bosh, Dash, ksh, yash, and Zsh, 25 bytes

```
$((- $4)) $2 $3 $((- $1))

```

Try it online!

## Differences

* A space between hyphen and dollar. This is a workaround for negative values; if one of them was expanded to `$((--1))`, for example, Dash, OSH and Bash parse as minus of minus one, but other four don't; they parse to decrement a variable named one, although one is a constant.

---

# Polyglots for Bash and OSH, 19 bytes

Thanks, 2x-1!

```
$[-$4] $2 $3 $[-$1]

```

Try it online!

## What the heck

`$[ ... ]` is historically equivalent to `$(( ... ))`, which is not adopted for POSIX.

OBTW adding a space betwee hyphen and dollar (which is +2 bytes), the code would be polyglot for Zsh, too.

# Answer
> 3 votes
# APL(Dyalog Unicode), ~~9~~ 7 bytes SBCS

```
-∘⌽@1 4

```

Try it on APLgolf!

A function submission which accepts an array.

-2 bytes from rak1507.

# Answer
> 3 votes
# 05AB1E, 7 bytes

```
À`(s()Á

```

Try it online!

```
         # implicit input                [A, B, C, D]
À        # rotate the input left         [B, C, D, A]
 `       # dump all values on the stack  B, C, D, A
  (      # negate top of stack           B, C, D, -A
   s     # swap top two values           B, C, -A, D
    (    # negate top of stack           B, C, -A, -D
     )   # collect all values in a list  [B, C, -A, -D]
      Á  # rotate the list right         [-D, B, C, -A]

```

# Answer
> 3 votes
# Ruby, 26 bytes

```
->n{a,b,c,d=n
[-d,b,c,-a]}

```

Try it online!

Shorter than my brainfuck answer by a few bytes, but not as interesting.

# Answer
> 3 votes
# jq, 22 bytes

```
[-.[3],.[1:3][],-.[0]]

```

Try it online!

# Answer
> 3 votes
# Java, 31 bytes

```
(a,b,c,d)->new int[]{-d,b,c,-a}

```

Try it online!

# Answer
> 3 votes
# JavaScript (Node.js), 22 bytes

```
(a,b,c,d)=>[-d,b,c,-a]

```

Try it online!

# Answer
> 2 votes
# convey, 16 + 6 = 22 or 53 bytes

Version 1: 16 (but takes extra input)

```
{?>>>>*}
 >>>>>^

```

After the four numbers, also input -1 1 1 -1 (+6 bytes). I can't figure out how to do it shortly any other way. Try it online!

Version 2, 53 bytes

```
{?>*}v<0
 v ^<<^-1
 ?>>*}
v<  ^v<1
v 0>^v
v1-^<<
>>*}

```

It's complicated. Multiplies the first and last numbers by -1. I'm a noob at convey and wait was crashing the program. Try it online!

# Answer
> 2 votes
# dc, 19 bytes

```
0?0r-sbscsd-lcldlbf

```

Try it online!

## Explanation

```
                     # Say the input is 4 6 8 7.
                     # Effect:
0                    # [0]
 ?                   # [0, 4, 6, 8, 7]
  0r-                # [0, 4, 6, 8,-7]
     sbscsd          # [0, 4] (B=-7, C=8, D=4)
           -         # [-4]   (B=-7, C=8, D=4)
            lcldlb   # [-4, 8, 4, -7]
                  f  # Output in reverse (i.e. -7 6 8 -4)

```

# Answer
> 0 votes
# MMIX, 44 bytes (11 instrs)

Inverts `mobius *a` into `mobius *b`. This is with `typedef double mobius[4];`.

Note that NaNs and zeroes have the sign negated; to not do so would cost an extra instruction (zeroing out `$2` at start and replacing `INCL $255,#8000` with `FSUB $255,$2,$255`).

(jxd)

```
00000000: 8fff0018 e4ff8000 afff0100 8fff0010  Ɓ”¡ðỵ”⁰¡Ḥ”¢¡Ɓ”¡Ñ
00000010: afff0108 8fff0008 afff0110 8fff0000  Ḥ”¢®Ɓ”¡®Ḥ”¢ÑƁ”¡¡
00000020: e4ff8000 afff0118 f8000000           ỵ”⁰¡Ḥ”¢ðẏ¡¡¡

```

Disassembled:

```
invmob  LDOU $255,$0,24
        INCH $255,#8000
        STOU $255,$1
        LDOU $255,$0,16
        STOU $255,$1,8
        LDOU $255,$0,8
        STOU $255,$1,16
        LDOU $255,$0
        INCH $255,#8000
        STOU $255,$1,24
        POP  0,0

```

# Answer
> 0 votes
# Python 3, 26 bytes

```
lambda a,b,c,d:[-d,b,c,-a]

```

Try it online!

4 input. Output is list.

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


title: CGCC sings a song together

text:
# Question
Title: CGCC sings a song together
This is a challenge, where the answers will aim to, together, output the lyrics to this beloved 80s song.

This is the full lyrics of the song, line by line. The first answer will contain a program that will output the first line of the song (`We're no strangers to love`). The second will do the same, but for the second line (`You know the rules and so do I`) and so on. Some answers (the 7th, 14th, 22nd, 29th, 36th, 45th, 51st, 54th, 61st and 68th) will output a blank line.

Each answers' program, however, must be **irreducible**, meaning that it must not output the correct line if any non-zero number of characters (not necessarily consecutive) are removed.

* `print("We're no strangers to love")` is an irreducible Answer 1 in Python 3
* `if 1: print("We're no strangers to love")` is not, as we can remove `if 1:`  and it'll still output the first line
* `print("We're no str" + "angers t" + "o love")` is also not, as the two `" + "`s can be removed, and it'll still produce the correct output.

---

Let \\$\bar x\_i\\$ be the arithmetic mean of the lengths of the first \\$i\\$ lines, to 1 decimal place. This sequence begins \\$26, 28, 32, 34, 34.6, 33\\$ and converges to \\$\bar x\_{74} = 24.3\\$ by the end of the song. Each answer has a score, which will eventually determine the overall winner. The score for the \\$i\\$th answer is defined as:

> If the \\$i\\$th answer is \\$n\\$ bytes long, its score is \\$|n - \bar x\_i|\\$

So, if the first answer is 10 bytes long, its score is \\$16\\$, and if the 72nd answer is 2 bytes long, its score is \\$|2 - 24.2| = 22.2\\$. A user's overall score is the arithmetic mean of the scores of all their answers. The user with the lowest overall score wins.

The full sequence of \\$\bar x\_i\\$; the left column is \\$i\\$, the right is \\$\bar x\_i\\$. Collapse the "Arguments" element for easier viewing.

---

### Rules

* You may either:

+ Output the line to STDOUT, or your language's closest alternative; or,
    + Return the line from a function
* You should take no input, aside from an optional empty input
* Each language may only be used once. This includes different versions of a language, such as Python 2 and Python 3. Generally, if two languages are considered versions of each other, such as Seriously and Actually, then only one is allowed to be used.
* You may not post 2 answers in a row
* You must wait 1 hour between answers
* The challenge will end when the 74th answer is posted, at which point I will accept an answer of the winner's choice

---

Please format your answer as the following:

```
# [Num]. [Lang], score [score]

    code

[Try it online!]

[Everything else]

```

# Answer
> 7 votes
# 4. Husk, score 0

```
¨You wouldn't get this fromȦ?ØoĠÜy

```

Try it online!

Just wanted to use Husk before someone else could steal it. Simply a (partially) compressed string.

# Answer
> 5 votes
# 7. Subleq, 28 bytes (7 32-bit words), score 0.3

```
6 3 3
0 0 3
4

```

Subleq Emulator

I am new to Subleq so hopefully this is right. The first line changes the 3 in address 5 to -1 which makes the second line exit producing no output. Deleting a word causes an infinite loop. For example, 0 0 0 goes to 0.

# Answer
> 4 votes
# 1. Jelly, score 0

```
“ŒßỤẸ:IŀėṪƝƓɠi?ṅRṭḄṁ3Ġ»ḣ26

```

Try it online!

```
“ŒßỤẸ:IŀėṪƝƓɠi?ṅRṭḄṁ3Ġ»     We're no strangers to love abcd
                       ḣ26  first 26 chars

```

# Answer
> 4 votes
# 2. 05AB1E, score 0

```
“Youƒ€ the rules and so do I

```

Try it online!

```
“...  # trimmed program
“...  # push "You know the rules and so do I"
      # implicit output

```

I accidentally opened Settings (Win+I) while typing this explanation.

# Answer
> 4 votes
# 3. Vyxal, score 0

```
`A ƛ‡ commitment's w∷⟇ I'm ʀ¨ of

```

Try it Online!

# Answer
> 4 votes
# 5. Labyrinth, 131 bytes, score 96.4

```
73.32.106.117.115.116.32.119.97.110:..97.32.116.101.108:..32.121.111.117.32.104.111.119.32.73.39.109.32.102.101:..108.105.110.103.@

```

Try it online!

Here goes a suboptimal language choice, as it can't win against those zero scores anyway.

It is hard to reuse a number in Labyrinth (except for adjacent ones) because each digit command alters the current top of the stack, rather than pushing a new number.

# Answer
> 4 votes
# 10. Japt, 29 bytes, score 0.8

```
`Nev€ gna run ÂÐ˜ „d Ürt yŒ

```

Try it online!

Just compressed the string, outputs `Never gonna run around and desert you`

Somehow the compressor is very nice and fits my need, exactly 28 bytes of string while compressed and adding a leading backtick to decompress gives 29 bytes, then leading to a nice optimal score

Though I think the HTML trick was better

# Answer
> 3 votes
# 9.  version \>= 4.1, Score 1.8

```
\()"Never gonna let you down"

```

A function taking no arguments and returning a string. No TIO link because R 4.1 isn’t yet on TIO.

Apologies for getting the wrong line initially!

# Answer
> 3 votes
# 12. HTML, score 1.7909090909090892

```
Never gonna say goodby&#101

```

I deleted my older HTML answer 1 hour ago so posting this now

# Answer
> 3 votes
# Line 14, `" "`

# Python 3, 0 bytes, score 26

```
[nothing here]

```

Try it online!

Gotta get Python in here somewhere.

# Answer
> 2 votes
# 6. JavaScript (Node.js), score 0

```
_=>'Gotta make you '+"understand"

```

Try it online!

```
_=>'...'+"..."  # trimmed program
_=>             # return function taking an optional argument _ that returns...
   '...'        # literal...
        +       # concatenated with...
         "..."  # literal

```

# Answer
> 2 votes
# 8. Splinter, Score 18.4

```
\N\e\v\e\r\ \g\o\n\n\a\ \g\i\v\e\ \y\o\u\ \u\p

```

Try it online!

Note: Apologies for the edit, I thought we were aiming for a higher score.

**this** outputs `Never gonna give you up`

# Answer
> 2 votes
# 11. Unary, 25247105318448659498226527583287720106787200954491263487845422435915430598123234439645367425137855414888675036 bytes - Score very close to that

Since it's impossible to beat those 0-pointers...

Compiles to `+[>>>-[-->+<<+<]<<+]>+++.<<<<+++.>.<.<<.>------.>++.<<---.-..>>------.<.>++++++.++.>.<----.<.>>+++.<<<+.++++++.>.<.-----.` in brainfrick - Try it online!

# Answer
> 2 votes
# 15. Stax, score 0.5

```
üy ♫ε╖nÖG°∟2♦½►±ç╧∟X)÷A•σ←

```

Run and debug it

Prints “We've known each other for so long”.

# Answer
> 2 votes
# 19. Grok, 50 bytes, score 22.1

```
hqj`ti yalp annog er'ew dna emag eht wonk eWi
W{lY

```

Try it Online!

Explanation:

```
h                                              # Start the IP moving left
   `ti yalp annog er'ew dna emag eht wonk eWi  # Push the string 'We know the game and we're gonna play it' to the stack.
  j                                            # Change the IP to move down
  l                                            # Change the IP to move right
   Y                                           # Duplicate the top of the stack to the register
W                                              # Print the value in the register as a character
 {                                             # If the top of the stack is 0, rotate IP direction clockwise
 q                                             # Terminate program

```

# Answer
> 2 votes
# 20. Bubblegum, score 1.1

```
00000000: e54c 1a26 90b8 f59b c710 0b14 f216 4647  .L.&..........FG
00000010: e7b7 bf31 1a85 6a0a 7a05 e8              ...1..j.z..

```

Try it online!

Uses the BB96 encoding to encode "And if you ask me how I'm feeling"

# Answer
> 2 votes
## 24. Excel, Score ~~0~~ 3

```
Never gonna let you down

```

*+3 score due to reducibility error*

# Answer
> 1 votes
# 13. DOG, Score 15

```
bark "Never gonna tell a lie and hurt you "

```

I can't figure out how to adapt the interpreter to TIO, so you'll have to download it.

# Answer
> 1 votes
# 16. PHP, 34 bytes, Score 7.4

```
<?="Your heart's been aching but";

```

Try it online!

PHP was of course needed here, for this very difficult line, and it has not enough pride left to care so much about its score anymore!

# Answer
> 1 votes
# 17. Underload, score 0.5

```
(You're too shy to say it)S

```

Try it online!

Fairly simple.

```
(You're too shy to say it)S

(You're too shy to say it)   Push this string to the top of the stack.
                          S  Print the top of the stack.

```

# Answer
> 1 votes
# 21. COW, Score 4474.4

```
OOOMoOMoOMoOMoOMoOMoOMoOMoOMMMmoOMMMMMMmoOMMMMOOMOomOoMoOmoOmoomOoMMMmoOMMMMMMmoOMMMMOOMOomOoMoOmoOmoomOoMMMmoOMMMMMMmoOMMMMOOMOomOoMoOmoOmooOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomOomOomOoMMMmoOmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoomOoOOOmoOOOOmOomOoMMMmoOMMMMOOMOomoOMoOmOomoomOomOoMMMmoOmoOMMMMOOMOomoOMoOmOomoomoOMoOMoOMoOMoOMoOMoomOo

```

Try it online(program will need to be pasted in)

Outputs `Don't tell me you're too blind to see`

# Answer
> 1 votes
# 22. C# (.NET Core), score 1.7

```
class P{static void Main(){}}

```

Try it online!

A minimal C# program that does nothing. I think any less than this and there’s no valid entry point.

# Answer
> 1 votes
# 25. Quarterstaff, score 98.6

```
111>o101>a110>b114>r78!a!118!a!r!32!103!o!b!b!97!32!r!117!b!32!97!r!o!117!b!100!32!97!b!100!32!100!a!115!a!r!116!32!121!o!117!

```

Try it online!

# Answer
> 0 votes
# 18. Deadfish~, 291.8 score

```
{{i}ddd}iiic{iiii}dddciiiiic{d}cdddddcic{{d}iii}ic{{i}d}dddc{dd}iic{{d}iii}ic{iiiiii}iiiiiic{i}iiiciiiiic{d}ddc{{d}iii}ddc{{i}ddd}iiiiiciiicic{i}ddc{{d}i}iiic{{i}d}dddc{d}dddddc{d}iiic{ii}dc{{d}ii}iiic{{i}ddd}iiiiiic{{d}ii}dddc{iiiiii}iiiiiiciiicc{i}dc{{d}ii}iic{{i}ddd}ic{i}ddcddddddciiiiic{d}iiic{{d}iii}dc{{i}dd}dcdc

```

Try it online!

# Answer
> 0 votes
# 23. Brain-Flak,Score 4370.9

```
(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())

```

Try it online!

Sorry about the mess. I have no idea how to efficiently get large numbers in Brain-flak.

Outputs `Never gonna give you up`

---
Tags: kolmogorov-complexity, answer-chaining, code-shuffleboard
---


title: Radio station hopping

text:
# Question
Title: Radio station hopping
# Introduction

You are listening to a car radio. You are pressing seek up/down, moving you to the next frequency some radio station broadcasts on, to avoid all this pointless music and listen to all the ads, or vice versa. If you try to go below the lowest frequency radio can handle, it jumps to the highest (and vice versa). Possible frequency range of a car radio is about 80-110 MHz with 2 decimals of precision.

But there is a tendency of these broadcasts to have your radio jump to another frequency, where signal of that radio station is stronger. So, suppose this radio station A broadcasts at 99, 100 and 101 MHz with 100 MHz having the strongest signal at your place. The moment you reach 101 MHz, radio will jump to 100 MHz.

Because of that, you can get trapped. Suppose there is one extra radio station B, broadcasting only at 102 MHz. The moment you are stuck at the station A, you can never listen to station B again - if you try going with frequency down, you will hit 99 and jump to 100, if you go up you reach 101 and jump to 100 again... never escaping that trap and radio station.

But if there is yet another station C at 99.5 and 98.5 MHz with latter being the strongest, you can listen to all 3 radios again - starting from B you get down to A, then down to C, then pressing down loops you back again to the highest frequency and station B.

So, you start wondering - given a list of radio stations, can I listen to all radio stations at least once if I start at the correct frequency? And will I be able to endlessly cycle through all of them, or listen to all just once before getting cut off some stations?

# Your task:

Get a list of radio stations, along with a designation of which has the strongest signal, in any reasonable format (1). Return one of three options to distinguish whether you can cycle through all stations indefinitely, you can cycle through all stations once or you cannot reach all stations from any starting point. Again in any reasonable format (2). Standard loophole rules apply.

(1) Test cases have different radio stations separated by semicolon. For each radio station, the strongest broadcast for the station is first, other entries separated by comma. You can pick anything else as your input format, along with any reasonable extra information you would like - for example number of radio stations, number of channels each station broadcasts at etc. Two stations won't share frequency. Frequencies can be assumed to be in typical car-like frequency range of say 80.00 to 110.00 MHz (or 8000 to 11000 if you prefer working with integers).

(2) Test cases have output as 1 - cycle all, 2 - cycle once, 3 - cannot reach all stations even once. You can return anything reasonable to distinguish these three options, as long as you return/print the value. For example, another possible output might be `T` meaning cycle all is true, `FT` meaning cycle all is false, cycle once is true, and `FF` meaning cycle all and cycle once are both false (= you can't reach all stations even once). Limitation: You must return everything in the same way, eg if your code outputs "cycle all" by crashing due to recursion depth, your "cycle once" and "cannot cycle" must also output by crashing.

# Test cases:

input: 102; 100, 99, 101 output: 2

input: 102; 100, 99, 101; 98.5, 99.5 output: 1

input: 100, 99, 101; 103, 102, 104 output: 3

input: 100, 99, 101; 103, 102, 104; 101.5, 99.5, 103.5 output: 1

input: 100, 99; 99.5, 100.5; 102, 103; 102.5, 101.5 output: 3

May the shortest code win.

# Answer
> 4 votes
# Jelly, ~~58~~ 36 bytes

```
;þ`Ḣ)ẎṢṪ€i@€FṢ$µṙⱮØ-Zị@QċþQæ*LẠ€Ạ;ẸƊ

```

Try it online!

A monadic link that takes as it’s argument a list of lists and returns `[0,0]` if it’s not possible to reach every station, `[0, 1]` if each can be reached once and `[1, 1]` if they can be cycled through indefinitely.

## Explanation

```
    )                                  | For each radio station:
;þ`                                    | - Concatenate each frequency to each of the other frequencies, as a list of lists
   Ḣ                                   | - Head - i.e. each frequency paired with the main frequency for the station
     Ẏ                                 | Join lists together
      Ṣ                                | Sort (so now in frequency order)
       Ṫ€                              | Tail of each (i.e. just the main frequency)
         i@€  $                        | For each, index of the station in the list generated by taking the original input and:
            F                          | - Flattening it and
             Ṣ                         | - Sorting it
               µ                       | Start a new monadic chain
                ṙⱮØ-                   | Rotate by each if -1 and 1
                    Z                  | Transpose
                     ị@                | Take only the main stations (which are
                       Q               | - The unique values)
                        ċþQ            | Generate an adjacency matrix
                           æ*L         | Matrix to the power of the length(number of stations)
                              Ạ€       | Check wherher rows are all true
                                   Ɗ   | Following as a monad:
                                Ạ      | - All
                                 ;     | - Concatenated to
                                  Ẹ    |- Any

```

# Answer
> 6 votes
# JavaScript (ES10),  ~~179~~  155 bytes

Expects an array of arrays of frequencies, with the strongest broadcast in first position for each station.

Returns \\$1\\$ for *cycle once*, \\$0\\$ for *cycle all*, or \\$3\\$ if there's no solution at all.

```
a=>a.some(h=A=>a[(g=([x],C=q=>a.find(d=>d.includes(b[(b.indexOf(x)+q)%n])))=>!g[x]&&g(C(g[x]=1))-~g(C(n-1)))(A)],b=a.flat().sort(),n=b.length)|2*a.every(h)

```

Try it online!

### How?

We first create an array `b[]` holding all frequencies sorted in lexicographical order. It means that the 80-99Mhz range will be put after the 100-110MHz range. But because the frequencies are wrapping around anyway, it doesn't matter. We also put the total number of frequencies in `n`.

```
b = a.flat().sort(), n = b.length

```

The helper function `C` takes a direction `q` and returns the sub-list corresponding to the station that is reached by moving towards `q` from the current leading frequency `x`.

```
C = q => a.find(d => d.includes(b[(b.indexOf(x) + q) % n]))

```

The callback function `h` takes the sub-list `A` of a station and walks through all connected stations, keeping track of the count (let's call it `N`). We use `q = 1` to seek up and `q = n - 1` to seek down. We eventually test `a[N]` to figure out whether all stations were reached.

```
h = A => a[(g = ([x], C = ...) => !g[x] && g(C(g[x] = 1)) - ~g(C(n - 1)))(A)]

```

This uses the helper function `C` described above and another recursive function `g` whose underlying object is also used to keep track of the stations that were already reached, using the leading frequency as the key.

We invoke `h` twice: once within a `some()` to detect *cycle once* and once within an `every()` to detect *cycle all*.

# Answer
> 3 votes
# , 85 81 78 bytes

```
[:~.#=[:+/@((]+.+./ .*)^:_"_ 1[:=#\)>+./@e."1/~/:~@;(]/:~e.#[:|:_1 1|."{[){.&>

```

Try it online!

## the idea

Let `n` be the number of the stations.

* Create an adjacency matrix representing connections between stations.
* For each starting station create an `n` item vector with a single `1` in the starting station's position, and 0 elsewhere, to encode the starting position as a vector.
* For each starting vector, iteratively multiply by the adjacency matrix `n` times, collecting intermediate results. The final vector represents which stations you can visit from the starting vector.
* Sum that final vector. This is the *number* of stations you can visit from that starting station.
* Check if that sum is equal to `n`. If it is, all stations can be visited.
* Now we have `n` final sums, each of which will be `0` (you can't visit all stations from that starting station) or `1` (you can). Uniquify that 0-1 list. Then note:
    + A single 1 means every starting station returned 1, meaning any station can be visited (via some number of hops) from any other. This is case 1.
    + A single 0 means you cannot visit all stations from any starting point. Case 3.
    + Both a 0 and 1 means it's possible to visit all stations from some starting point, but not from all. Case 2.

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