title: Strategy: The cunning cousin witch

text:
# Question
Title: Strategy: The cunning cousin witch
The wizard has a cunning cousin who is a witch. She looks down on the wizard, regarding him and his puzzles as mathematically naive. On reading his latest puzzle, she scorned him for always asking discrete problems with what she (unfairly) characterises as simple solutions, where the real, proper question should be continuous. To prove her point she poses the following version of the wizard's puzzle. (He reluctantly permits the partial plagiarism.)

Consider the following setup. A cunning witch has a real number line stretching from 0 to 10 which is hidden from you. Also hidden from you she chooses a random integer \\$x \in \\{0, \dots, 10\\}\\$ and places that many points onto the number line uniformly at random. To be more precise, she places each of the \\$x\\$ points independently and uniformly at random onto the number line. Your task is to prove that \\$x = 10\\$ and if you do the witch will grant you what she promises is a much better wish than what her cousin can provide.

In this game, you can at each step choose a floating point number \\$y\\$ and the witch will tell you the number of points on the number line with value less than or equal to \\$y\\$.

However the witch, being at least as evil as her cousin, will not let you choose a number larger than \\$9\\$. This might still be OK as you might still find 10 points and in fact the only way to be granted the wish is to have found all 10 points with values 9 or less.

The cost for choosing a floating point number \\$y\\$ is \\$2^{y}\\$ dollars. At any point, you can choose to give up on this set of points and get her to start the whole process again (with a new random \\$x\\$). Of course, if you choose the number 9 and you still have not found 10 points you have no choice but to give up and start again. But you might want to give up after having chosen a number smaller than 9. Sadly you never get any money back so your costs just carry on building.

Your goal is to devise a strategy that will get you the wish at the minimum expected cost. You should report your mean cost.

# Testing

Once you have chosen your strategy, you should run it until you get the wish 10,000 times and report the mean cost. If two answers have the same strategy, the one posted first wins. If two strategies have similar mean costs you may need to test it 100,000 or even more times to tell the difference. Of course if you can directly compute the expected cost, all the better.

# Input and output

There is no external input in this challenge. The output is just the mean cost to get a wish. To test your code you will need to implement both the witch and your strategy.

# What's a naive score?

If you just choose 9 each time then it will take you \\$\frac{1}{\frac{1}{11} \cdot \frac{9}{10}^{10}} \approx 31.5\\$ tries to find 10 points. This will cost you approximately \\$16152.4\\$ dollars. How much better can you do?

# Notes

You can assume that floating numbers are precise mathematical real numbers when evaluating your code and that the random number generator from your favourite library is perfect (except please don't use the default rand() in C which is truly terrible).

# Answer
> 4 votes
# R / Rcpp: 2641.844 ± 1.132

Evaluated on 15 million simulated games. Bounds are a 95% bootstrap confidence interval with 10,000 iterations.

Posting on behalf of my cousin who looks down on reinforcement learning, as in my solution to the Wizard's puzzle. "Reward shaping? If it's any good you've already solved the problem." To prove her point she poses the following heuristic solution to the witch's puzzle.

## Method

The policy was learned using a genetic algorithm with an initial population of 500 chromosomes. Fitness for each chromosome was calculated by evaluating its corresponding policy over 50,000 games.

All chromosomes with fitness above the median (the half of the chromosomes with the lowest mean evaluated cost) were selected at random to reproduce, and the remaining chromosomes were discarded. Reproduction continued until the population returned to its original size.

The crossover operator was a uniform heuristic crossover with an expected crossover rate of 50%, and an expected scaling coefficient of 0.5. Because my crossover operator chooses uniform random values for the crossover rate and scaling coefficient every time it is called, I chose to only produce one offspring per operation to increase offspring randomness / exploration.

The mutation operator was defined to replace target genes with uniform random values, and the mutation rate was set to 0.001.

## Policy Representation

My goal was to do as well as possible with a minimalist policy representation, so each chromosome is a numeric vector length 20. For a chromosome notated \\$\[p\_{0}, p\_{1}, ... , p\_{10}, p\_{11}, ... , p\_{19}\]\\$, its corresponding policy is calculated as:

$$ \begin{bmatrix} 0 & p\_{11}\\ p\_{0} + p\_{1} & p\_{12}\\ p\_{0} + ... + p\_{2} & p\_{13}\\ . & .\\ . & .\\ . & .\\ p\_{0}+...+p\_{10} & p\_{19}\\ \end{bmatrix} $$

The zero-indexed policy matrix, \\$p\\$, is interpreted as follows: Let \\$\lambda\\$ be the length of the number line searched, starting at zero. For \\$n\\$, the number of points found, if \\$\lambda \leq p(n, 0)\\$ then \\$\lambda = lambda + p(n, 1)\\$, otherwise reset.

In other words, the policy describes a distinct rate at which the line should be searched, \\$p(n, 1)\\$, given it has found \\$n\\$ points before having searched \\$p(n, 0)\\$ of the line.

## Learned Policy

After 200 generations, I selected the chromosome with the highest fitness, whose policy is approximately:

$$ \begin{bmatrix} 0.00 & 1.07\\ 0.90 & 0.00\\ 1.74 & 2.46\\ 2.52 & 2.65\\ 3.25 & 4.11\\ 4.66 & 1.65\\ 4.66 & 2.91\\ 5.67 & 9.00\\ 9.00 & 5.58\\ 9.00 & 2.78\\ \end{bmatrix} $$

This policy slowly searches the first half of the line until it finds enough points that it is worth searching the remainder of the line. At that point, it searches large chunks of the line to minimize cost. If it doesn't find enough points early on, it will reset (even though it may have been possible to find all 10 points).

For a more intuitive understanding of why the policy works and how it defined good step sizes, suppose we calculate the cost of searching some amount of the number line given we have already searched \\$\lambda\\$ as

$$ \text{Line per Cost} = \frac{p(n, 1)}{2^{p(n, 1) + \lambda}} $$

From the formula we can see that as \\$\lambda\\$ increases, the cost of searching the additional \\$p(n, 1)\\$ also increases.

To understand this policy, consider when \\$\lambda = p(n,0)\\$, which corresponds to the worst scenario for which the policy will continue to search the line. Plotting the line per cost vs. the number of points found gives the below black points.

The blue points are \\$\frac{1}{2^{n+1}}\\$, which corresponds to the line per cost given by searching the number line in units of one if you expect to find one point in each unit.

So from the plot we can see that the learned policy has worst case preferences that nearly match what you get if you expect to find a point every time you search one unit of the number line. Note: Though the learned policy does not match \\$\frac{1}{2^{n+1}}\\$ for the \\$n = 1\\$ case, repeated testing shows that skipping over the case where only one point has been found tends to improve the policy's score.

## Convergence Rate

I chose learning parameters to provide a smooth descent towards an optimal solution, and in the plot of the learning curve below that the population appears to find local minimums around the 20th and 30th generations before setting into the learned policy area somewhere between generations 100 and 150.

## Code

**Rcpp Code to Define the Genetic Algorithm**

```
#include <Rcpp.h>
using namespace Rcpp;

//* Generate Points
// [[Rcpp::export]]
NumericVector setPoints() {

  //Sample number of points
  NumericVector pointSet = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  int numPts = Rcpp::sample(pointSet, 1)[0];

  //Return
  return(Rcpp::runif(numPts, 0.0, 10.0));

}

//* Generate Chromosome
// [[Rcpp::export]]
NumericVector generateChromosome() {
  return(Rcpp::runif(20, 0.0, 2.0));
}

//* Crossover
// [[Rcpp::export]]
NumericVector crossover(
  NumericVector x,
  NumericVector y
) {

  //Parameters
  NumericVector params = Rcpp::runif(2, 0.0, 1.0);
  NumericVector randVals = Rcpp::runif(x.length(), 0.0, 1.0);
  LogicalVector doCross = (randVals <= params[0]);

  //Apply crossover
  NumericVector offspring = clone(x);
  for(int i = 0; i < x.length(); i++){
    if(doCross[i]){
      NumericVector v = {params[1] * (x[i] - y[i]) + x[i]};
      v = Rcpp::clamp(0.0, v, 9.0);
      offspring[i] = v[0];
    }
  }

  //Return
  return(offspring);

}

//* Mutate
// [[Rcpp::export]]
NumericVector mutate(NumericVector x, double rate) {
  NumericVector x_new = clone(x);
  NumericVector randVals = Rcpp::runif(x.length(), 0.0, 1.0);
  LogicalVector doMutate = (randVals <= rate);
  for(int i = 0; i < x.length(); i++){
    if(doMutate[i]){
      x_new[i] = Rcpp::runif(1, 0.0, 9.0)[0];
    }
  }
  return(x_new);
}

//* Chromosome to Policy
// [[Rcpp::export]]
NumericMatrix chromToPolicy(NumericVector x) {
  NumericVector policy = clone(x);
  double sumVal = 0;
  for(int i = 0; i < 10; i++){
    sumVal += x[i];
    if(sumVal > 9){
      sumVal = 9;
    }
    policy[i] = sumVal;
  }
  policy[0] = 0.0;
  policy.attr("dim") = Dimension(10, 2);
  return(as<NumericMatrix>(policy));
}

//* Evaluate
// [[Rcpp::export]]
NumericVector evaluatePolicy(
    NumericVector x,
    int iters,
    int maxCost = -1
) {

  //Convert chromosome to policy
  NumericMatrix policy = chromToPolicy(x);

  //Run episodes
  NumericVector out (iters, 0.0);
  bool earlyStop = false;
  for(int i = 0; i < iters; i++){

    //Initialize values
    NumericVector points = setPoints();
    double lineSearched = 0;
    int ptsFound = 0;

    //Begin episode
    bool done = false;
    while(!done) {

      //Step forward if in policy
      if(policy(ptsFound, 0) >= lineSearched){
        lineSearched += policy(ptsFound, 1);
        if(lineSearched > 9){
          lineSearched = 9;
        }
        out[i] += pow(2, lineSearched);
        ptsFound = sum(points <= lineSearched);

      } else {

      //Otherwise, reset
        points = setPoints();
        lineSearched = 0;
        ptsFound = 0;
      }

      //Reset when line searched but fewer than 10 points found
      if(lineSearched == 9 & ptsFound < 10){
        points = setPoints();
        lineSearched = 0;
        ptsFound = 0;
      }

      //Exit conditions
      if(ptsFound == 10){
        done = true;
      }

      //Early stop condition
      if((maxCost >= 0 & out[i] >= maxCost)){
        out[i] = NA_REAL;
        earlyStop = true;
        done = true;
      }

    }
    if(earlyStop){
      break;
    }
  }
  return(out);
}

```

**R Code to Run the Algorithm**

```

#----- Initialize Population -----

#Generate seed population
#Because random chromosomes are often slow to evaluate
#Seed with random chromosome s.t. max(cost) < 50,000
size <- 500
population <- t(sapply(1:size, function(c){
  generateChromosome()
}))

#Calculate fitness
fitness <- sapply(1:nrow(population), function(i){
  mean(evaluatePolicy(population[i,], 50000, 50000))
})

#Increase yield
population <- population[!is.na(fitness),]
while(TRUE){

  #New population
  newPopulation <- t(sapply(1:size, function(c){
    generateChromosome()
  }))
  newFitness = sapply(1:nrow(newPopulation), function(i){
    mean(evaluatePolicy(newPopulation[i,], 50000, 50000))
  })
  population <- rbind(population, newPopulation[!is.na(newFitness),])

  #End
  if(nrow(population) >= size){
    rm(newFitness, newPopulation)
    break
  }

}

#----- Evolve -----

#Parameters
rounds <- 200

#Iterate over generations
for(i in 1:rounds){

  #Calculate fitness
  fitness <- sapply(1:nrow(population), function(i){
    mean(evaluatePolicy(population[i,], 50000, 100000))
  })

  #Subset population
  population <- population[which(fitness <= median(fitness, na.rm = TRUE)),]

  #Crossover
  population <- rbind(population, t(sapply(1:(size - nrow(population)), function(i){
    inds = sample(1:nrow(population), 2, FALSE)
    crossover(population[inds[1],], population[inds[2],])
  })))

  #Mutate
  population <- t(sapply(1:nrow(population), function(i){
    mutate(population[i,], rate = 0.001)
  }))

}

```

# Answer
> 3 votes
# Python, score = 2610.6431 (2610.5938 with 400 guess values)

Finds the optimal policy over a discrete set of equally spaced possible guesses (200 by default).

Here's a plot of new guess vs old guess for each number of found points; a guess of 0 means resetting. Make of it what you will.

```
import itertools
import random

import matplotlib.pyplot as plt
import numpy as np
from scipy.stats import binom

bound = 16153
samples = 200

g = np.linspace(0, 9, samples)

def logsumexp(x):
    m = x.max()
    return np.log(np.sum(np.exp(x - m))) + m

def init_trans(samples):
    print("computing transition matrix...\n")
    trans = np.full((samples, 10, samples, 11), float('-inf'))
    g = np.linspace(0, 9, samples)
    for i0 in range(samples - 1):
        print(f"computing row {i0} of {samples}", end='\r', flush=True)
        g0 = g[i0]
        for n in range(10):
            k = np.arange(n, 11)
            u = np.zeros(k.shape) if i0 == 0 else binom(k, g0 / 10).logpmf(n)
            for i1 in range(i0 + 1, samples):
                g1 = g[i1]
                d = binom(k - n, (g1 - g0) / (10 - g0))
                for m in range(n, 11):
                    v = d.logpmf(m - n)
                    trans[i0,n,i1,m] = logsumexp(u + v)
    print()
    trans -= trans.max(axis=-1, keepdims=True)
    trans = np.exp(trans)
    trans /= trans.sum(axis=-1, keepdims=True)
    return trans

trans_file= f'trans_{samples}.npy'
try:
    trans = np.load(trans_file)
except FileNotFoundError:
    trans = init_trans(samples)
    np.save(trans_file, trans)

def get_policy(trans):

    print("estimating policy...")
    values_file = f"values_{samples}.npy"
    policy_file = f"values_{samples}.npy"
    grad = np.zeros((samples, 11))
    values = np.zeros((samples, 11))
    policy = np.zeros((samples, 11), dtype=np.int64)
    x = bound
    while True:
        values[-1,:-1] = x
        grad[-1,:-1] = 1
        for i0 in range(samples - 2, -1, -1):
            for n in range(10):
                g1 = g[i0+1:]
                v1 = 2 ** g1 + np.einsum('ij, ij -> i', trans[i0,n,i0+1:,n:], values[i0+1:,n:])
                di = np.argmin(v1)
                i1 = i0 + di + 1
                if v1[di] <= x:
                    values[i0,n] = v1[di]
                    grad[i0,n] = np.sum(trans[i0,n,i1,n:] * grad[i1,n:])
                    policy[i0,n] = i1
                else:
                    values[i0,n] = x
                    grad[i0,n] = 1
                    policy[i0,n] = 0
        if values[0,0] >= x:
            break
        x += (values[0,0] - x) / (1 - grad[0,0])
    print(f"computed cost = {x}")
    return values, policy

values_file = f"values_{samples}.npy"
policy_file = f"policy_{samples}.npy"
try:
    values, policy = np.load(values_file), np.load(policy_file)
except FileNotFoundError:
    values, policy = get_policy(trans)
    np.save(values_file, values)
    np.save(policy_file, policy)

for i in range(10):
    plt.subplot(2, 5, i + 1)
    plt.plot(np.linspace(0, 1, samples), policy[:,i], color='blue')
plt.show()

print('running simulations...')

mean_cost = 0
cost_m2 = 0
for t in itertools.count():

    cost = 0

    while True:
        n = random.randrange(11)
        p = [10 * random.random() for _ in range(n)]
        i0 = 0
        f0 = 0
        done = False
        while True:
            i1 = int(policy[i0,f0])
            if i1 == 0:
                break
            g1 = g[i1]
            assert (0 <= g1 <= 9)
            cost += 2 ** g1
            f1 = sum(1 for x in p if x <= g1)
            if f1 == 10:
                done = True
                break
            if i1 == len(g) - 1:
                break
            i0 = i1
            f0 = f1
        if done:
            break

    mean_cost1 = mean_cost + (cost - mean_cost) / (t + 1.)
    cost_m2 += (cost - mean_cost) * (cost - mean_cost1)
    mean_cost = mean_cost1
    if t % 1000 == 0:
        print(f"{t} trials run, cost = {mean_cost} ± {np.sqrt(cost_m2 / (t + 1) ** 2):.3f}")

```

# Answer
> 1 votes
# Rust, score= ~6,081.9

Guesses each number 1-9. Aborts if the number found is less than 0.8 * number.

Anyone is free to copy this answer and further optimize the parameters (0.8 abort limit and 1.0 step size) or of course modify anything else.

```
use rand;
use rand::{Rng, RngCore};

struct Which {
    rng: rand::rngs::ThreadRng,
    numbers: Vec<f32>,
    score: f32
}

impl Which {
    fn new(rng: rand::rngs::ThreadRng) -> Which {
        return Which{rng: rng, numbers: vec![], score: 0.0};
    }

    fn regenerate(&mut self) {
        let number = self.rng.next_u32()%11;
        self.numbers = (0..number).map(|i|self.rng.gen::<f32>()*10.0).collect();
    }

    fn guess(&mut self, n: f32) -> usize {
        self.score += 2.0_f32.powf(n);
        self.numbers.iter().filter(|i|**i<n).count()
    }
}

fn algo(which: &mut Which) {
    which.regenerate();

    loop {
        let mut guess = 1;
        while guess<=9 {
            let number = which.guess(guess as f32);
            if number >= 10 {
                return;
            }
            if (number as f32) < (guess as f32) * 0.8 {
                break
            }
            guess+=1;
        }
        which.regenerate();
    }

}

fn main() {

    let mut total_score:f64 = 0.;
    for _ in 0..10_000 {
        let mut which = Which::new(rand::thread_rng());

        algo(&mut which);
        total_score+=which.score as f64;
    }

    println!("total score: {:?}", total_score/ 10_000.);

}

```

Basic starter answer, probably not even close to optimal.

# Answer
> 0 votes
# Javascript, average cost = $~4975

Is that how the scoring works? I don't have time to test this another 50 million times or so rn haha

Not the best score so far, but just something I wanted to try. I do have one other idea I want to try that uses a new strategy but I'll only post it if it performs decently :P

This code checks if there are at least 5 points below 5. If there are, it goes all in and checks below 9. Either way, after that it gives up.

```
cheater=_=>cheater()
//this crashes the program if i try to check higher than 9 :P

witch=_=>{ //witch takes no input
  let z=Math.floor(Math.random()*11)
  //selects an integer from 0 to 10
  let points=[]
  for(let i=0;i<z;i++){
    points.push(Math.random()*10)
    //plots that many points on the line from 0 to 10

  }
  return x=>x>9?cheater():points.filter(w=>w<x).length
  //and returns a function which takes n as input and outputs how many points exist below n (or crashes if n>9)
}

solver=_=>{
  let current=witch()
  //calling witch generates a new set of points, which i can check with current
  let cost=0
  while(1){
    cost+=2**5
    //i pre-emptively add the cost of each inspection on the line
    if(current(5)==10){
      return cost
    }else if(current(5)>4){
    //i think its ok to use the same inspection twice at no cost, because theres no new information, and its just easier and nicer looking than storing the result in a variable or something
      cost+=2**9
      if(current(9)==10){
        return cost
      }
    }
    current=witch()
    //this is the "give up" part
  }
}

tester=(m)=>{
  //m is the number of iterations to test
  let costlist=[]
  for(let i=0;i<m;i++){
    costlist.push(solver())
  }
  return costlist.reduce((a,b)=>a+b,0)/costlist.length
  //returns the average cost
  //i ran tester(10000000) thrice and got 4972.0177856, 4972.7681056, and 4974.2599296.
}

```

---
Tags: code-challenge
---


title: Make a long type signature

text:
# Question
Title: Make a long type signature
# Challenge

Find an expression, at most 100 bytes long, with the longest type signature.

# Rules

* Any statically typed language with type inference is allowed
* The type must be non-ambiguous, but otherwise may include types without defined instances. For example `Num [a]` and `Eq [a]` are allowed, even without a defined instance
* No imports other than the minimum required to compile a program with STDIN/STDOUT
* Infinite types are not allowed
* If an answer has more than one expression, only one may contribute to the score. For example, although the type signature of composition is `(.) :: (b -> c) -> (a -> b) -> a -> c`, having a score of 20, the answer with 25 copies of `(.)\n` would have a score of 20, not 500
* The expression must be, at most, 100 bytes
* The score is the number of characters in the type signature, excluding the name of the function and any whitespace. For example, `f :: (a -> b) -> a -> b` would have a score of 12
* The highest score wins!

# Examples

Although other languages are allowed, the following examples are in Haskell:

```
Score: 112
map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map
f :: (a -> b)
 -> [[[[[[[[[[[[[[[[[[[[[[[[[a]]]]]]]]]]]]]]]]]]]]]]]]]
 -> [[[[[[[[[[[[[[[[[[[[[[[[[b]]]]]]]]]]]]]]]]]]]]]]]]]

Score: 240
(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.)
f :: (b->c)->(a->a1->a2->a3->a4->a5->a6->a7->a8->a9->a10->a11->a12->a13->a14->a15->a16->a17->a18->a19->a20->a21->a22->a23->a24->b)->a1->a2->a3->a4->a5->a6->a7->a8->a9->a10->a11->a12->a13->a14->a15->a16->a17->a18->a19->a20->a21->a22->a23->a24->c

Score: 313
foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl(.)
f :: (Foldable t, Foldable t1, Foldable t2, Foldable t3, Foldable t4,
  Foldable t5, Foldable t6, Foldable t7, Foldable t8, Foldable t9,
  Foldable t10, Foldable t11, Foldable t12, Foldable t13,
  Foldable t14, Foldable t15) =>
 (b -> c)
 -> t (t1 (t2 (t3 (t4 (t5 (t6 (t7 (t8 (t9 (t10 (t11 (t12 (t13 (t14 (t15 (b
 -> b))))))))))))))))
 -> b
 -> c

Score: 538
lex.show.foldl1.mapM.traverse.sum.mapM.sum.traverse.(.).mapM.scanl.zipWith3((.traverse).(.traverse))
 (Num
    (a -> ([[c]] -> t3 [[a1 -> f b]]) -> [[c]] -> t3 [[a1 -> f b]]),
  Num
    (([[c]] -> t3 [[a1 -> f b]])
     -> t1 (t2 ([[c]] -> t3 [[a1 -> f b]]))
     -> [[c]]
     -> t3 [[a1 -> f b]]),
  Show
    (t (t1 (t2 ([[c]] -> t3 [[a1 -> f b]])))
     -> t1 (t2 ([[c]] -> t3 [[a1 -> f b]]))),
  Applicative f, Foldable t,
  Foldable ((->) (t1 (t2 ([[c]] -> t3 [[a1 -> f b]])) -> a)),
  Foldable
    ((->) (([[c]] -> t3 [[a1 -> f b]]) -> a -> t3 [a1 -> f b])),
  Traversable t1, Traversable t2, Traversable t3, Traversable t4,
  Traversable t5,
  Traversable ((->) (t1 (t2 ([[c]] -> t3 [[a1 -> f b]])))),
  Traversable ((->) ([[c]] -> t3 [[a1 -> f b]]))) =>
 [(t5 (t4 a1) -> f (t5 (t4 b))) -> c -> a1 -> f b]
 -> [(String, String)]

```

# Answer
> 19 votes
## Haskell, ~2^(2^18)

```
f x=(x,x)
g=f.f.f.f
h=g.g.g.g
i=h.h.h.h
j=i.i.i.i
k=j.j.j.j
l=k.k.k.k
m=l.l.l.l
n=m.m.m.m
n.n.n.n$0

```

Each application of `f` roughly double the type signature by transforming the type signature `T` to `(T,T)`. For example, the fourfold composition `f.f.f.f$0` has type

```
Num a => ((((a, a), (a, a)), ((a, a), (a, a))), (((a, a), (a, a)), ((a, a), (a, a))))

```

Each line quadraples the number of applications of `f`, giving `4^9 = 2^18` at the end. So, the type signature has size of the order of `2^(2^18)`.

# Answer
> 13 votes
# Haskell with extensions, \\$\ggg A(A(A(A(220,0),0),0),0)\\$

```
Z::Z#Z#Z#Z#Z#Z#Z#Z#Z?Z
data a?b=Z|S(a?b)
type family m#n where Z#n=S n;S m#Z=m#S m;S m#S n=m#(S m#n)

```

Try it online!

Requires `-XDataKinds`, `-XPolyKinds`, `-XTypeOperators`, `-XUndecidableInstances`, and `-XTypeFamilies`.

Many thanks to Ørjan Johansen, who realized that making the natural number constructor infix and building the arguments a bit differently saved two bytes, making just enough room for another iteration of `#`.

Obviously, the type checker will give up trying to check this program. To get a general sense of what the signature would look like (if it were small enough to fit in the observable universe), try the much smaller

```
Z::S(S Z)#Z?Z

```

## Explanation

The `#` type family is closely related the Ackermann–Péter function, commonly written \\$A\\$, but `#` grows faster. The Ackermann–Péter function is defined

> \\$A(0,n)=n+1\\$
>
> \\$A(m,0)=A(m-1,1)\\$ when \\$m \> 0\\$
>
> \\$A(m,n)=A(m-1, A(m, n-1))\\$ when \\$ m, n \> 0 \\$

`#`, on the other hand, we can call \\$B\\$, and write

> \\$B(0,n)=n+1\\$
>
> \\$B(m,0)=B(m-1,m)\\$ when \\$m \> 0\\$
>
> \\$B(m,n)=B(m-1, B(m, n-1))\\$ when \\$m,n \> 0\\$

Only the second case is different. The termination proof is identical to the standard one for \\$A\\$, and it should be clear that \\$B(m,n) \ge A(m,n)\\$ for all \\$m\\$ and \\$n\\$.

Here we calculate a unary representation of

> \\$r = B(B(B(B(B(B(B(B(0,0),0),0),0),0),0),0),0) \\$

By direct calculation, \\$B(B(B(B(0,0),0),0),0)=220\\$, so

> \\$r = B(B(B(B(220,0),0),0),0)\\$.

Note that \\$A(A(A(A(0,0),0),0),0)\\$ is only \\$5\\$, so we've bumped things up a good bit to start out. I don't have a very clear sense of just how much faster \\$B\\$ grows than \\$A\\$, but considering how the calculation proceeds, it seems likely to grow quite a lot faster.

The number of digits in even \\$A(6,0)\\$ is too large to express practically in decimal, so this is ... rather ridiculously large.

The definition of the natural numbers, `(?)`, is a bit non-standard. To save space, we use `(?)` as both a natural number type (at the type level) and a proxy type (at the term level).

I believe that either `TypeFamilies` or (more verbosely and obfuscatedly) `FunctionalDependencies` are necessary to get the type-level computation required to reach truly large types. `UndecidableInstances` is needed to work around Haskell's very primitive termination checking. The other extensions are only needed to compress the code into the small available space.

# Answer
> 11 votes
# Java, score 17301488

Requires the method `<T>java.util.Map<T,T>f(T t){return null;}`, which has been counted towards the 100-byte limit.

`f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(1)))))))))))))))))))`

The compile-time type signature of this should match this.

# Answer
> 11 votes
# Haskell, 9·2663552 − 3 (≈ 1.02·10199750)

A small (“small”) improvement over xnor’s 5⋅2262144 \+ 5. This is 99 bytes.

```
f=(:).(:)
g=f.f.f.f
h=g.g.g.g
i=h.h.h.h
j=i.i.i.i
k=j.j.j.j
l=k.k.k.k
m=l.l.l
n=m.m.m
o=n.n.n
o.o.o

```

### How it works

We have

```
(:)         :: a -> [a] -> [a]
(:).(:)     :: a -> [[a] -> [a]] -> [[a] -> [a]]
(:).(:).(:) :: a -> [[[a] -> [a]] -> [[a] -> [a]]] -> [[[a] -> [a]] -> [[a] -> [a]]]

```

and so on, with the length roughly doubling for each `(:)`. The given expression `o.o.o` works out to `(:).(:).(:).….(:)` with 2·46·34 = 663552 copies of `(:)`.

# Haskell with `FlexibleContexts` and `NoMonomorphismRestriction`, (200·4331776 \+ 75·331776 + 16)/9 ≈ 2.53·10199750

A small improvement over Bubbler’s 12·2663552 \+ 9·663552 − 4 ≈ 1.36·10199750, which also relies on these extensions. The wording of the challenge sort of suggests it might be okay to rely on them (“For example `Num [a]` and `Eq [a]` are allowed, even without a defined instance”); I’m not sure. This is 100 bytes.

```
f=(/).(:)
g=f.f.f.f
h=g.g.g.g
i=h.h.h.h
j=i.i.i.i
k=j.j.j.j
l=k.k.k.k
m=l.l.l
n=m.m.m
o=n.n.n
-o.o.o

```

### How it works

We have

```
-(/).(:) :: (Fractional ([a] -> [a]), Num (a -> ([a] -> [a]) -> [a] -> [a])) => a -> ([a] -> [a]) -> [a] -> [a]
-(/).(:).(/).(:) :: (Fractional ([a] -> [a]), Fractional ([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]), Num (a -> ([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]])) => a -> ([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]
-(/).(:).(/).(:).(/).(:) :: (Fractional ([a] -> [a]), Fractional ([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]), Fractional ([([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]] -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]]), Num (a -> ([([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]] -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]]) -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]] -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]])) => a -> ([([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]] -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]]) -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]] -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]]

```

and so on, with the length roughly quadrupling for each `(/).(:)`. The given expression `-o.o.o` works out to `-(/).(:).(/).(:).….(/).(:)` with 46·34 = 331776 copies of `(/).(:)`.

# Answer
> 8 votes
# Haskell, 12·2663552 \+ 9·663552 - 4

Yet another small improvement over Anders Kaseorg's answer.

```
f=(/).(/)
g=f.f.f.f
h=g.g.g.g
i=h.h.h.h
j=i.i.i.i
k=j.j.j.j
l=k.k.k.k
m=l.l.l
n=m.m.m
o=n.n.n
o.o.o

```

### How it works

```
(/) -- score 27
   :: Fractional a => a -> a -> a
(/).(/) -- score 62
   :: (Fractional a, Fractional (a -> a)) => a -> (a -> a) -> a -> a
(/).(/).(/) -- score 119
   :: (Fractional a, Fractional (a -> a), Fractional ((a -> a) -> a -> a)) =>
      a -> ((a -> a) -> a -> a) -> (a -> a) -> a -> a
(/).(/).(/).(/) -- score 224
   :: (Fractional a, Fractional (a -> a),
       Fractional ((a -> a) -> a -> a),
       Fractional (((a -> a) -> a -> a) -> (a -> a) -> a -> a)) =>
      a
      -> (((a -> a) -> a -> a) -> (a -> a) -> a -> a)
      -> ((a -> a) -> a -> a)
      -> (a -> a)
      -> a
      -> a

```

Just changed function composition `(.)` to fractional division `(/)`. The `Fractional x` part in the function signature explodes along with the main part, giving slightly higher constant multiplier.

# Answer
> 6 votes
# C, 979

```
#define a int,int,int
#define b a,a,a,a
#define c b,b,b
#define d c,c,c
#define e d,d,d
int(*f)(e);

```

`f` has the signature:

```
int(*)(int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int)

```

# Answer
> 5 votes
# Idris, \>hyper(hyper(hyper(hyper(999999999, 99, 99), 99,99),99,99),99,99)

```
f:Nat->Type
f Z=()
f(S n)=hyper n n n~=~f n
the$f$hyper(hyper(hyper(hyper 999999999 9 9) 9 9)9 9)9 9

```

## Explanation:

We're defining a function f, computing a type f(0) is just the unit type, while f(S(n)) computes to the equality type applied to the function argument "hypered" by itself and to f applied to n. The last line basically is a function expecting a value of a type like (27 = (4 = (2 = (1 = ()))))) (for n=4).

# Simple Example

```
f 3 = (27 = (4 = (2 = (1 = ()))))

```

# Answer
> 4 votes
# C#, 363

Expression:

```
new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=""}}}}}}}}}}}}}}

```

Type signature:

```
<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[System.String]]]]]]]]]]]]]]

```

Try it online!

# Answer
> 2 votes
# Go 1.0 without `reflect`, 98

Go 1.x types are statically defined. Here is my first try:

```
[][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][]string{}

```

On the Go playground:

```
package main;import "fmt"
func main() {

    x := [][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][]string{}

    fmt.Printf("%d %T\n", len(fmt.Sprintf("%T", x)), x)
}

```

# Go 1.9 using type aliases, 2389

```
type(I=interface{f();g()};S=struct{p,q,r,s,t,u,v,w,x,y,z I});map[S]map[S]map[S]map[S]map[S]map[S]S{}

```

On the Go playground:

```
package main;import("fmt";"strings")
func main() {

    type(I=interface{f();g()};S=struct{p,q,r,s,t,u,v,w,x,y,z I});x:=map[S]map[S]map[S]map[S]map[S]map[S]S{}

    fmt.Printf("%d %T\n", len(strings.Replace(fmt.Sprintf("%T", x), " ", "", -1)), x)
}

```

Result:

```
2389 map[struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }]map[struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }]map[struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }]map[struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }]map[struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }]map[struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }]struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }

```

# Go 1 using `reflect`, 65532

There is a limit in package `reflect` on the length of type names: `len(name) <= 1<<16-1`

I've been able to reach a type name of 65532 bytes so far with this block:

```
t:=reflect.TypeOf(0);u:=t;for i:=0;i<8191;i++{t=reflect.MapOf(u,t)};reflect.New(t).Interface()

```

Full code on the Go playground:

```
package main;import("fmt";"reflect")
func main() {

    t:=reflect.TypeOf(0);u:=t;for i:=0;i<8191;i++{t=reflect.MapOf(u,t)};x:=reflect.New(t).Interface()

    fmt.Printf("%d %T\n", len(fmt.Sprintf("%T", x)), x)
}

```

---

Notes: `x:=` is never counted.

# Answer
> 2 votes
# Rust, 99 bytes, score=46,137,336

```
fn b<T>(a:T)->Result<T,T>{Ok(a)}b(b(b(b(b(b(b(b(b(b(b(b(b(b(b(b(b(b(b(b(b(b(0))))))))))))))))))))))

```

Attempt This Online!

# Answer
> 2 votes
# Rust, 100 bytes, Score \\$\approx 2.22128\times 10^{78}\\$

The score is \\$8+\underbrace{6\times(6\times(\cdots(6\times2+7)\cdots)+7)+7}\_{100 \text{ levels}}=\\$ `2221283319900241080728746908337396589826288615608046563246444685656290281023085`.

The type is `Option<((...(u8,u8,u8,u8,u8,u8),...))>`, with 100 levels of nested tuples, where each tuple contains 6 identical items.

```
type A<T>=(T,T,T,T,T,T);type B<T>=A<A<A<A<A<T>>>>>;type C<T>=B<B<B<B<B<T>>>>>;None::<C<C<C<C<u8>>>>>

```

# Answer
> 2 votes
# C#, 100 bytes, score = \\$3.7996944224×10^{21}\\$

```
class X<A,B,C,D,E,F,G>{class Y:X<Y,Y,Y,Y,Y,Y,Y>{Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y.Y y;}}

```

---

Solution inspired by this answer.

There are two variables that contribute to the length of the type signature of the variable `y`: the number of generic type arguments on `X` and the number of nested class accesses in `Y`.

The following formula represents the length of the generated type signature not counting whitespace:

\\$ L\ =\ \frac{x^{y}\cdot((x-1)(2x^{2}+5x+4)+x+4)-(x+4)}{(x-1)} \\$

where `x` is the number of generic type arguments on `X` (e.g. for `X<A,B,C,D>`, `x = 4`) and `y` is the number of `.Y`s

Using Desmos and trial and error, I found the maximum length value where `x` and `y` would fit in 100 bytes was at `x=7` `y=23`.

Try it online!

# Answer
> 1 votes
# Ceylon, 38843546786070481 (~ 4·1016)

```
[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]

```

This are 49 nested one-tuples, with an empty tuple innermost. The short name of this type is actually the same as the value in this case, but the fully expanded name is much longer.

The Ceylon compiler is working forever when trying to compile this (The compiler was still running after 180 minutes) – I'll have to try calculating the theoretical type length.

The problem here is that a one-element-tuple type `[X]` is actually represented in Ceylon's type system as `Tuple<X, X, []>` (first parameter is a supertype for all element types, second is the type of the first element, and third the type of all except the first elements, which is here an empty tuple (the `empty` object, the single instance satisfying the interface `Empty`)).

So `[]` is `empty`, `[[]]` is `Tuple<[], [], []>` = `Tuple<empty, empty, empty>`, `[[[]]]` is `Tuple<[[]], [[]], []>` = `Tuple<Tuple<[], [], []>, Tuple<[], [], []>, []>`. And the full name includes the package names, so we have actually `ceylon.language::Tuple<ceylon.language::Tuple<ceylon.language::empty, ceylon.language::empty, ceylon.language::empty>, ceylon.language::Tuple<ceylon.language::empty, ceylon.language::empty, ceylon.language::empty>, ceylon.language::empty>` just for three levels. And we want to go to 50.

As `ceylon.language::empty` is 22 characters long, and each `ceylon.language::Tuple<?,?,ceylon.language::empty>` adds 47 to twice the result from the previous step, we get `f(1) = 22`, and `f(n) = 2 · f(n-1) + 47`. This simplifies to `f(n) = 69 · 2^(n - 1) - 47`, and entering 50 gives us 38843546786070481. Of course, this is much larger than what would fit in the memory of my computer (8·109 bytes).

Of course, the compiler could be smart and not try to have the whole type name in memory until its name is requested.

Here is the full program trying to print the type:

```
import ceylon.language.meta {
    type
}
"Run the module `codegolf.signature71797`."
shared void run() {
    value x = [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]];
    print(type(x));
}

```

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), 99 bytes, Score 841

```
(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,1,1))))))))))))))))))))))))

```

Try it online!

Outputs

```
System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`3[System.Int32,System.Int32,System.Int32]]]]]]]]]]]]]]]]]]]]]]]]

```

# Answer
> 0 votes
# Haskell, 782

Expression:

```
sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum

```

Type signature:

```
:: (Num [[[[[[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[c]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[c]]]]]]]]]]]]]], Num [[[[[[[[[[[[[c]]]]]]]]]]]]], Num [[[[[[[[[[[[c]]]]]]]]]]]], Num [[[[[[[[[[[c]]]]]]]]]]], Num [[[[[[[[[[c]]]]]]]]]], Num [[[[[[[[[c]]]]]]]]], Num [[[[[[[[c]]]]]]]], Num [[[[[[[c]]]]]]], Num [[[[[[c]]]]]], Num [[[[[c]]]]], Num [[[[c]]]], Num [[[c]]], Num [[c]], Num [c], Num c) => [[[[[[[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]]]]]]] -> c

```

---
Tags: code-challenge, busy-beaver, functional-programming
---


# Question
Title: Find the GCD and LCM of a list of numbers
Note: most of the questions that are already in existence about this topic only deal with two numbers as inputs. This question deals with any number (\>1) of inputs.

## GCD

The GCD (greatest common divisor) of a list of integers is the largest integer which divides all of the numbers in the list.

For example:

* \\$gcd(9, 12, 15) = 3\\$
* \\$gcd(25, 75, 95) = 5\\$
* \\$gcd(5, 7, 9) = 1\\$

## LCM

The LCM (lowest common multiple) of a list of integers is the smallest integer which can be divided by all of the numbers in the list.

For example:

* \\$lcm(2, 3, 4) = 12\\$
* \\$lcm(5, 7, 9) = 315\\$
* \\$lcm(10, 15, 21) = 210\\$

## Your task

You need to find the GCD and LCM of a list of integers which you will take as input from the user.

As this is a challenge, you can take the input in any format, and output in any format.

Here are some test cases:

```
Input                 Output
1 2 3 4               1 12
10 20 30 40           10 120
7 9 11 13             1 9009
2 3 5 7 11 13 17 19   1 9699690
2 4 6 8 10            2 120

```

# Answer
# Ruby, 35 bytes

```
->l{[:gcd,:lcm].map{|x|l.reduce x}}

```

Try it online!
> 1 votes

# Answer
# Numlang, 8 bytes

### Code

```
$;Gy;OCy

```

### Explanation

```
$;Gy;OCy
$;          // Take input from user (implicitly store in y)
  Gy;       // Get the GCD of y (implicitly store in l)
     O      // Output the last used variable (l)
      Cy    // Get the LCM of y (implicitly store in l)
            // Implicitly output the last used variable (l)

```
> 0 votes

# Answer
# Python 3.9, 44 bytes

```
lambda l:(gcd(*l),lcm(*l))
from math import*

```

In Python 3.8 and lower, `gcd` and `lcm` only accept 2 arguments. This was changed in 3.9, so this answer only works on 3.9+. Try it online does not have the needed version, so I could not post a link to it.
> 0 votes

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


title: First Number to Contain Each Letter

text:
# Question
Title: First Number to Contain Each Letter
Given a single letter from A to Z (except J and K) as input, output the smallest non-negative integer containing that letter in its written form. Assume numbers never contain the word "and", so `101` is "one hundred one", not "one hundred and one". Assume American (short-scale) counting, so one million is `10^6` and one billion is `10^9`.

```
a 1000                           one thousand
b 1000000000                     one billion
c 1000000000000000000000000000   one octillion
d 100                            one hundred
e 0                              zero
f 4                              four
g 8                              eight
h 3                              three
i 5                              five
j
k
l 11                             eleven
m 1000000                        one million
n 1                              one
o 0                              zero
p 1000000000000000000000000      one septillion
q 1000000000000000               one quadrillion
r 0                              zero
s 6                              six
t 2                              two
u 4                              four
v 5                              five
w 2                              two
x 6                              six
y 20                             twenty
z 0                              zero

```

J and K are not part of the input specification, so your behavior is undefined for them. Given one of the above letters, output the (decimal) number next to it. You can take input in lowercase or uppercase, but you cannot require that some inputs are lowercase and others uppercase.

This is , so the shortest answer in bytes wins.

# Answer
# JavaScript (Node.js),  ~~78 75 74~~  73 bytes

```
c=>(n=([x]=Buffer(c+'8>P7 $(#%  +;! MD &"$%"&4 '))[x-96]-53)<0?n+21:10**n

```

Try it online!

### How?

Each value is encoded with a single printable character. We use the ASCII range \\$\[32..52\]\\$ to encode \\$n-32\\$ and the range \\$\[53..80\]\\$ to encode \\$10^{n-53}\\$.

### Commented

```
c =>                                   // c = input character
  ( n =                                //
    ( [x] =                            // let x be the 1st byte of the
        Buffer(                        // buffer made of:
          c +                          //   c followed by
          '8>P7 $(#%  +;! MD &"$%"&4 ' //   the encoded values
        )                              //
    )[x - 96]                          // let n be the encoded value corresponding to c
    - 53                               // minus 53
  ) < 0 ?                              // if n is negative:
    n + 21                             //   return n + 21
  :                                    // else:
    10 ** n                            //   return 10 ** n

```
> 16 votes

# Answer
# Ruby, 65 bytes

```
->n{i="CI[B?;7<:??4F>?XO?9=;:=9+?"[n.ord-65].ord-64;i>0?10**i:~i}

```

Try it online!

Improvements inspired by GB's comment.

# Ruby, 70 bytes

```
->n{i="ci}b@DHCE@@KfA@xo@FBDEBFT@"[n.ord-65].ord;i>96?10**(i-96):i-64}

```

Try it online!
> 7 votes

# Answer
# Stax, 33 bytes

```
º░¡µ?Äz*B╥╪╩ΓoΣ4ù↓|♂5%⌡ÿΩ²┼h{☻4O└

```

Run and debug it

### Procedure:

1. Extract codepoint from input.
2. Index into constant array `[3, 5, 7, 9, 11, -6, 1, 0, -24, -15, 0, 6, 2, 4, 5, 2, 6, 20, 0, -3, -9, -27, -2, 0, 4, 8]` using codepoint. (with wrap-around)
3. If the result is negative, negate and raise `10` to that power, otherwise leave as-is.
> 7 votes

# Answer
# ///, 125 bytes

```
/:/\/\///T/000:d/100:a/d0:m/aT:b/aTT:q/bTT:p/qTTT:c/pT:e/0:f/4:g/8:h/3:i/5:l/11:n/1:o/0:r/0:s/6:t/2:u/4:v/5:w/2:x/6:y/20:z/0/

```

Try it online!

Input is appended to the end of the code, as per I/O meta. The footer in the above TIO link tests all letters simultaneously, as a single newline-delimited string, but the code also works just fine when inputting a single character.
> 6 votes

# Answer
# Wolfram Language (Mathematica), 50 bytes

Letters b, c, m, p and q are skipped for performance reasons when testing on TIO.

```
(i=0;While[1>StringCount[IntegerName@i,#],i++];i)&

```

Try it online!
> 6 votes

# Answer
# Excel, 85 bytes

```
=CHOOSE(CODE(A1)-96,1E3,1E9,1E27,100,,4,8,3,5,,,11,1E6,1,,1E24,1E15,,6,2,4,5,2,6,20,)

```

2 Golfy bits:

* Using exponents (e.g. `1E15`) saves `26 bytes`.
* Default of `CHOOSE` when nothing is provided is `0`, saves `4 bytes`
> 6 votes

# Answer
# 05AB1E, 36 bytes

```
•—ÃÅ¸usδtθ}™-5„©‘öæH•57в₆-sÇ`èD0‹iÄ°

```

Port of *@recursive*'s Stax answer.
Input in lowercase.

Try it online or verify all test cases.

**Explanation:**

```
•—ÃÅ¸usδtθ}™-5„©‘öæH• # Push compressed integer 3133432551338094772548436198140408157771728287
 57в                  # Converted to base-57 as list: [39,41,43,45,47,30,37,36,12,21,36,42,38,40,41,38,42,56,36,33,27,9,34,36,40,44]
    ₆-                # Subtract 36 from each: [3,5,7,9,11,-6,1,0,-24,-15,0,6,2,4,5,2,6,20,0,-3,-9,-27,-2,0,4,8]
      sÇ`             # Swap to take the input, and convert it to its unicode value
         è            # Index it into the list (with automatic wraparound)
          D0‹i        # Create a copy, and if this is negative:
              Ä       #  Take the absolute value
               °      #  And then take 10 the power this value
                      # (implicitly output the top of the stack as result)

```

See this 05AB1E tip of mine (section *How to compress large integers?* and *How to compress integer lists?*) to understand why `•—ÃÅ¸usδtθ}™-5„©‘öæH•` is `3133432551338094772548436198140408157771728287` and `•—ÃÅ¸usδtθ}™-5„©‘öæH•57в` is `[39,41,43,45,47,30,37,36,12,21,36,42,38,40,41,38,42,56,36,33,27,9,34,36,40,44]`.
> 4 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~77~~ ~~74~~ 68 bytes

```
x=>((x="1‘Ʊ!  aƁñ"[x-65])&15)*Math.Pow(10,x>>4)

```

Encodes each letter's output as \\$a \times 10^b\\$, where \\$a\\$ is represented by the lowest 4 bits of the character, while \\$b\\$ is represented by the next five bits after that. Uses capital letters.

**Commented**

```
x=>                                                 //Lambda taking in a char
  (x=                                         )     //Re-assign x to
     "1‘Ʊ!   aƁñ"[x-65]      //The character's value at index x-65
 (                                             &15) //Bitwise AND by 15
  * Math.Pow(10,x>>4)                               // Multiplied by 10**(floor(x/16))

```

Try it online!
> 3 votes

# Answer
# Perl 5 `-p`, 84 bytes

```
$_=(1e3,1e9,1e27,100,0,4,8,3,5,1,1,11,1e6,1,0,1e24,1e15,0,6,2,4,5,2,6,20,0)[-65+ord]

```

Try it online!
> 3 votes

# Answer
# Python 3, 103 bytes

```
lambda x:(1000,10**9,10**27,100,0,4,8,3,5,0,0,11,10**6,1,0,10**24,10**15,0,6,2,4,5,2,6,20,0)[ord(x)-97]

```

Try it online!
> 3 votes

# Answer
# Perl 6, 67 bytes

```
{/\-/??10**-$_!!$_}o{'`ZHacgkfhccn]dcKTciegheiwc'.ords[.ord-97]-99}

```

Try it online!

Uses a lookup table where a negative number means that is the negative of the exponent, otherwise it is the number itself.
> 2 votes

# Answer
# 05AB1E, 32 bytes

```
•н“вüQ;æ¡ζæÀÛß%aÜ×₃t•56вsCè2‰`i°

```

Try it online!

```
•н“вüQ;æ¡ζæÀÛß%aÜ×₃t•56в  # compressed list:
# [31, 0, 12, 4, 8, 10, 4, 12, 40, 0, 7, 19, 55, 5, 0, 8, 16, 6, 10, 1, 1, 22, 13, 2, 0, 49]

s                         # swap so the input is at the top
 C                        # parse input as "binary" (a -> 36, b -> 37, ...)
  è                       # index (wraps around)
   2‰                     # divmod 2: [n / 2, n % 2]
     `                    # dump both on the stack
      i                   # if the modulo is 1:
       °                  #  10 ** the quotient
                          # implicit output

```
> 2 votes

# Answer
# Bash, ~~129~~ 100 bytes

```
A=xDVw04835zzbA10SJ0624526k0
c=$[64#${A:$[64#$1-10]:1}]
[ $c -gt 30 ]&&printf 1%0$[c-30].0f||echo $c

```

Try it online!

~~Try it online!~~

### How it works:

```
A=xDVw04835zzbA10SJ0624526k0

```

$A: Base64 encoded "a"-"z": numbers less than 100 are stored directly. Larger numbers are encoded as the number of zeros +30. (ex: 1,000 = 33, 100 = 32, etc.)

```
c=$[64#${A:$[64#$1-10]:1}]

```

Extract one letter from $A at position specified in argument $1 (base64 decoded, -10 to account for offset of 'a'). Base64 decode that character and store in c.

```
[ $c -gt 30 ]&&printf 1%0$[c-30].0f||echo $c

```

If $c is greater than 30, print "1" padded with $c-30 zeros. Else, print $c.
> 2 votes

# Answer
# Sledgehammer, 17 bytes

Technically, this is 133 bits long, but that doesn't really make this 16.625 bytes, as the compressor claims.

```
⣜⢍⢞⢹⡱⡋⣽⡱⡆⢺⢦⡽⡐⡌⢗⠈⣵

```

This probably decodes to

```
x1 = Input[]; x2 = 0; While[StringFreeQ[IntegerName[x2], x1], x2++]; Print[x2]

```

(approximately the same as my Mathematica answer), although I barely got it encoded (it appears as though my PC has compatibility issues with everything), so good luck decoding it again to check. I might have made some mistakes while using the encoder, so be careful.
> 2 votes

# Answer
# Vyxal, 11 bytes

```
λ∆ċ‛λ¬-?c;ṅ

```

Try it Online!

Very literal implementation of the title.

## Explained

```
λ∆ċ‛λ¬-?c;ṅ
λ        ;ṅ  # The first number
 ∆ċ‛λ¬-      #   (converted to words, with any "and"s removed)
       ?c    # to contain the input

```
> 2 votes

# Answer
# Jelly, 36 bytes

```
Oị“[@ịẆþĊ`o&÷ḲḞṘḂỊP¥t’b48¤_⁹⁵*ɗ¹>?20

```

Try it online!

A monadic link taking a lower case letter as its argument and returning an integer. Returns `0` for `j` and `k`.

## Explanation

```
O                       | Convert to code point
 ị          ¤           | Index into following as a nilad (wraps around):
  “[...t’               | - Integer 5370441668223940717846370165240010583188867 (stored base 250)
         b48            | - Convert to base 48
                 ɗ >?20 | If >20, following as a dyad using 20 as right argument:
             _⁹         | - Subtract right argument (20)
               ⁵*       | - 10 to the power of this
                  ¹     | Else: leave unchanged (identity function)

```
> 1 votes

# Answer
# Retina 0.8.2, 89 bytes

```
^
$'
T`l`111104835__111011062452620`^.
T`abcm\pq`139285
\d$
$*0$&$*0$&$*0
d
00
T`\lyl`10_

```

Try it online! Link includes test cases. Explanation:

```
^
$'

```

Duplicate the input.

```
T`l`111104835__111011062452620`^.

```

Change the first copy to the (first) digit of the relevant result.

```
T`abcm\pq`139285

```

If the number has a multiple of 3 trailing zeros, get that multiple now.

```
\d$
$*0$&$*0$&$*0

```

And actually convert it into the relevant number of trailing zeros. (Note that this would simplify to `*3*0` in Retina 1.)

```
d
00

```

Fix up `d`.

```
T`\lyl`10_

```

Fix up `l` and `y` and remove any remaining letters.
> 1 votes

# Answer
# PHP, 104 bytes

```
<?=A<($a='^FX]0483500GC10UL0624526P0'[ord($argn)-97])?20==($b=ord($a)%30)||11==$b?$b:str_pad(1,$b,0):$a;

```

Try it online!

I have a string `^FX]0483500GC10UL0624526P0` which holds a single character for every input letter from "a" to "z". I extract this character based on input and store it in `$a`. If the character is not a digit, its ASCII code mod 30 will be stored in `$b`.

If `$a` is a digit, same digit is printed, this is used for any input that needs an output between 0 and 9 (like "e", "f", etc).

Else if `$b` is 20 or 11, same number is printed, this is used for "l" and "y".

Else, digit "1" padded to `$b` with "0"s is printed. For example for input of "a", the character is "^" which has an ASCII code of 94. `94 % 30 = 4` and "1" padded to 4 with "0"s will be "1000".
> 1 votes

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


title: Words that Contain Digits

text:
# Question
Title: Words that Contain Digits
A digit word is a word where, after possibly removing some letters, you are left with one of the single digits: ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT or NINE (not ZERO).

For example, BOUNCE and ANNOUNCE are digit words, since they contain the digit one.

ENCODE is not a digit word, even though it contains an O, N and E, since they are not in order.

Write a program/function which takes a single (uppercase or lowercase -- you choose) word as input or a parameter and determines if it is a digit word. Make the code as short as possible.

If the word is not a digit word, you should return 'NO', 0 or any 'falsey' value (this may vary based on your language). If the word is a digit word, you should output the digit it contains, as a number.

You can assume that no words contain more than one digit, so you won't have anything like ONFIVE.

***Test Cases***

```
BOUNCE
1

ENCODE
NO

EIGHT
8

BLACKJACK
NO

FABULOUS
NO

EXERCISE
NO

DRIFTWOOD
2

SERVICEMAN
7

INSIGNIFICANCE
9

THROWDOWN
2

ZERO
NO

OZNERO
1

```

*This challenge is taken from (and is a very slight modification of) Question 1 from BIO 2009. Most of the test cases are taken from the mark scheme.*

# Answer
# Javascript (ES6), 101 99 bytes

```
f=
s=>-~'ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE'.split` `.findIndex(x=>s.match([...x].join`.*`))
```

```
<!-- snippet demo: -->
<input list=l oninput=console.log(f(this.value))>
<datalist id=l><option value=BOUNCE>
<option value=ENCODE>
<option value=EIGHT>
<option value=BLACKJACK>
<option value=FABULOUS>
<option value=EXERCISE>
<option value=DRIFTWOOD>
<option value=SERVICEMAN>
<option value=INSIGNIFICANCE>
<option value=THROWDOWN>
<option value=ZERO>
<option value=OZNERO>
```
> 10 votes

# Answer
# PHP\>=7.0, 87 Bytes

```
<?for(;$i++<9;)levenshtein(IntlChar::charName("$i"),"DIGIT $argn",0,1,1)?:die("$i")?>NO

```

If only insertions of chars from one digit as word to the input is done exit the program with the digit. Or change the order to `levenshtein("DIGIT $argn",IntlChar::charName("$i"),1,1,0)` to count not the deletions of chars

levenshtein

IntlChar::charName

# PHP\>=7.0, 112 Bytes

```
for(;$i<9;)$r+=++$i*preg_match("#".chunk_split(substr(IntlChar::charName("$i"),6),1,".*")."#",$argn);echo$r?:NO;

```

IntlChar::charName

# PHP, 128 Bytes

```
foreach([ONE,TWO,THREE,FOUR,FIVE,SIX,SEVEN,EIGHT,NINE]as$v)$r+=++$k*preg_match("#".chunk_split($v,1,".*")."#",$argn);echo$r?:NO;

```

Try it online!

143 Bytes for more then 1 digit

```
foreach([ONE,TWO,THREE,FOUR,FIVE,SIX,SEVEN,EIGHT,NINE]as$v)$r.=++$k*preg_match("#".chunk_split($v,1,".*")."#",$argn);echo+$r?strtr($r,[""]):NO;

```

Try it online!
> 8 votes

# Answer
# Mathematica, 83 bytes (WindowsANSI encoding)

```
±w_:=Rest@Position[Subsets@w~Cases~#&/@Characters@*IntegerName~Array~9,Except@{},1]

```

Defines a unary function `±` that takes a list of lowercase characters as input and returns either a digit, in a form like `{{7}}`, or else an empty list `{}`. I don't feel like I did a ton of golfy things here, except that `Characters@*IntegerName~Array~9` generates the number-name matches to look for without hard-coding them.

Example usage:

```
±{"i", "n", "s", "i", "g", "n", "i", "f", "i", "c", "a", "n", "c", "e"}

```

yields `{{9}}`.
> 6 votes

# Answer
# Python 3, 150 bytes

```
from itertools import*;lambda x:([i for i in range(10)if(*' OTTFFSSENNWHOIIEIIEORUVXVGN  ERE EHE  E   NT '[i::9],)in[*combinations(x+'  ',5)]]+[0])[0]

```

`combinations` returns all the combinations of things in order. It would be simpler to have a set number for the second parameter of `combinations`, so spaces are added onto the end of the original string that is a parameter of my lambda. That's a simple description of how my entry works. Ask if you would like any more clarification.
> 5 votes

# Answer
# Jelly, ~~31~~ 28 bytes

-2 bytes now that lowercase input is acceptable

```
“¡¦ẇṆb~ṇjṚØ%ĖġṘḥḞṾṇJḌ»Ḳe€ŒPT

```

A full program that expects lowercase input and prints the result, using `0` for the falsey case.

As a monadic link taking a list of characters it actually returns a list of integers which contains a single `0` in the falsey case, a single integer between `1` and `9` inclusive in the expected use cases and multiple such entries in cases where more than one number exists in the word.

**Try it online!**

### How?

```
“¡¦ẇṆb~ṇjṚØ%ĖġṘḥḞṾṇJḌ»Ḳe€ŒPT - Main link: list of characters, s
“¡¦ẇṆb~ṇjṚØ%ĖġṘḥḞṾṇJḌ»       - dictionary lookup of "one two three four five six seven eight nine"
                      Ḳ      - split on spaces
                         ŒP  - partitions of s
                       e€    - exists in? for €ach
                           T - truthy indexes

```
> 5 votes

# Answer
# Ruby + to\_words: ~~49~~ 48+12 = ~~61~~ 60 bytes

Uses the flags `-rto_words -n`. Takes lowercase words. Returns `nil` if no "digit" found.

-1 byte now that lowercase input is allowed, allowing for the removal of the `i` flag on the regex.

```
p (1..9).find{|i|$_=~/#{i.to_words.chars*".*"}/}

```

For a more pure Ruby answer without external gems, 91+1 = 92 bytes:

```
p (1..9).find{|i|$_=~/#{%w"0 ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE"[i].chars*".*"}/}

```
> 5 votes

# Answer
# Python, 148 bytes

```
from itertools import*
lambda s:[tuple(w)in combinations(s,len(w))for w in("x ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE "+s).split()].index(1)%10

```

An unnamed function taking an uppercase only word and returning the integer (`1` to `9`), or `0` for `NO`.

**Try it online!**

### How?

For an input string `s` the function traverses through a list of the strings: `"x"`, `"ONE"`, `"TWO"`, `"THREE"`, `"FOUR"`, `"FIVE"`, `"SIX"`, `"SEVEN"`, `"EIGHT"` , `"NINE"`, and `s` itself looking for any matches.\*

The comparison used is whether this string, `w`, is one that may be formed from a combination of letters in order from the input. The function `combinations` gets these for us (and only the ones of the required length using `len(w)`), but they are in the form of tuples, so the strings are cast to tuples for the comparison.

Of the eleven results the one for `"x"` will always be `False`, while the one for `s` itself will always be `True`. The `"x"` is there to ensure the index of a match with `ONE` through `NINE` are the values required (since Python lists are 0-indexed), the `s` is there to ensure the call to `index(1)` (synonymous with `index(True)`) wont fail when no digit word was found, whereupon the resulting `10` is converted to a `0` with a modulo of ten using `%10`.

* If `s` contains spaces for some reason, the list of `w`s will be longer, but the process will still work since the digit word matches will work the same way, and if none match the first space-split substring from `s` will match, once again giving `10` and returning `0`.

If multiple digit words exist the function will return the minimal one.
> 4 votes

# Answer
# 05AB1E, 26 bytes

The falsy value here is **0**.

```
æ‘€µ‚•„í†ìˆÈŒšï¿Ÿ¯¥Š‘#å1k>

```

Explanation:

```
æ                           # Compute the powerset of the input
 ‘€µ‚•„í†ìˆÈŒšï¿Ÿ¯¥Š‘       # Push "ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE"
                     #      # Break on spaces
                      å     # Check each for membership
                       1k   # Get the index of 1 in the array (-1 if not found)
                         >  # Increment by one

```

Uses the **05AB1E** encoding. Try it online! or Verify all test cases!
> 3 votes

# Answer
# Retina, ~~160~~ ~~126~~ 120 bytes

```
O.*N.*E
1
T.*W.*O
2
T.*H.*R.*E.*E
3
F.*O.*U.*R
4
F.*I.*V.*E
5
S.*I.*X
6
S.*E.*V.*E.*N
7
E.*I.*G.*H.*T
8
N.*I.*N.*E
9
\D

```

Try it online!

Returns an empty string if the input does not contain a digit.

-6 bytes thanks to @CalculatorFeline.
> 3 votes

# Answer
# Japt, 52 bytes

```
1+`e two È(e fŒr five £x  v eight ÍÂ`¸a@v fX¬q".*

```

Try it online!
> 3 votes

# Answer
## Haskell, ~~113~~ 111 bytes

```
import Data.List
last.((`elemIndices`([]:words"ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE"))=<<).subsequences

```

Try it online!

Returns `0` if no digit is found.

Find all subsequences of the input word in the list of digits. Prepend an empty string `[]` at index 0 which is part of every subsequence. `elemIndices` returns a list of indices and `=<<` flattens them into a single list. Pick the last index.
> 2 votes

# Answer
## JavaScript (ES6), 121 bytes

```
f=
s=>[...s].map(c=>a=a.map(s=>s.slice(s[0]==c)),a=`ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE`.split` `)&&1+a.indexOf(``)
```

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

Returns the lowest detected digit or `0` if no digit was detected (+6 if `NO` is required).
> 2 votes

# Answer
# Java (JDK), 150 bytes

```
s->{for(var i=0;i<9;)if(s.matches("."+"ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE".split(" ")[i++].replaceAll(".","*$0.")+"*"))return i;return"NO";}

```

Try it online!

## Saves

* 167 -\> 153: various optimization thanks to @KevinCruijssen
> 2 votes

# Answer
# Bash, 163 bytes

```
a=NO;case $1 in *O*N*E*)a=1;;*T*W*O*)a=2;;*T*H*R*E*E*)a=3;;*F*O*U*R*)a=4;;*F*I*V*E*)a=5;;*S*I*X*)a=6;;*S*E*V*E*N*)a=7;;*E*I*G*H*T*)a=8;;*N*I*N*E*)a=9;;esac;echo $a

```

Try it online!

```
a=NO;
case $1 in
 *O*N*E*)a=1;;
 *T*W*O*)a=2;;
 *T*H*R*E*E*)a=3;;
 *F*O*U*R*)a=4;;
 *F*I*V*E*)a=5;;
 *S*I*X*)a=6;;
 *S*E*V*E*N*)a=7;;
 *E*I*G*H*T*)a=8;;
 *N*I*N*E*)a=9;;
esac;
echo $a

```

Don't know RETINA but seems a straight port of that answer.
> 2 votes

# Answer
# Brachylog, 57 bytes

```
∧"ONE
TWO
THREE
FOUR
FIVE
SIX
SEVEN
EIGHT
NINE"ṇi₁Ph⊆?∧Pt

```

Try it online!

### Explanation

I think this could be shorter if `i` were reversible, but it doesn't appear to be.

```
∧"..."ṇi₁Ph⊆?∧Pt
∧                  Break unification with input
 "..."             String containing words ONE through NINE, newline-separated
      ṇ            Split on newlines
       i₁          [item, index] pair for some item in that list (1-based index)
         P         Call that pair P
          h        Its first element (the word)
           ⊆       is a non-contiguous substring of
            ?      the input
             ∧     And
               Pt  P's last element (the index) is the output

```
> 2 votes

# Answer
# Python, ~~125~~ 123 bytes

```
f=lambda b,x=9,i=0:x and f(b,x-1)+x*all(i:=b.find(c,i)+1for c in"NINE EIGHT SEVEN SIX FIVE FOUR THREE TWO ONE".split()[-x])

```

Attempt This Online!

-2 bytes from @xnor, also fixing a misalignment with the spec
> 2 votes

# Answer
# Factor \+ `math.combinatorics math.text.english`, 53 bytes

```
[ all-subsets 9 [1,b] [ number>text ] map disjoint? ]

```

Try it online!

Returns `f` for 'is a digit word' and `t` for 'is *not* a digit word.'

* `all-subsets` Get all the subsets of the input.
* `9 [1,b] [ number>text ] map` A shorter way to write `{ "one" "two" "three" "four" "five" "six" "seven" "eight" "nine" }`.
* `disjoint?` Do the sets not overlap? (This is 2 bytes shorter than saying `intersects?`.)
> 2 votes

# Answer
# PHP, ~~134 132~~ 128 bytes

```
<?=preg_match(strtr(chunk_split("#(ONE0TWO0THREE0FOUR0FIVE0SIX0SEVEN0EIGHT0NINE",1,".*"),[")|("]).")#",$argn,$m)?count($m)-1:NO;

```

run as pipe with `-nF` or try it online.

Creates a regex with the words in parentheses; i.e. each word `N` is in the `N`th sub-expression.
If a word is found, the matched string will be in `$m[0]` and in the the `N`th element, with the elements between them empty and no empty string behind; i.e. `$m` has `N+1` elements.
> 1 votes

# Answer
## Javascript, 121 bytes

```
(s,a=0)=>'ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE'.split``.map((p,i)=>RegExp(p.split``.join`.*`).exec(s)?a=i+1:0)&&a

```

or 116

```
(s,a=0)=>' ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE'.split` `.map((p,i)=>a|=~s.search(p.split``.join`.*`)&&i)&&a

```

But just recycling material at this point.
> 1 votes

# Answer
# Pyth, ~~-44-~~ 41 bytes

```
+1xm}dyQc."EX%~)Û#lº,îQÓCe¯4Aô4"\P1

```

Takes a quoted string, outputs 0 for NO.

Try it!

### explanation

```
+1xm}dyQc."EX%~)Û#lº,îQÓCe¯4Aô4"\P1
         ."EX%~)Û#lº,îQÓCe¯4Aô4"      # Compressed string: "ONEPTWOPTHREEPFOURPFIVEPSIXPSEVENPEIGHTPNINE" (P is close to the other letters, makes the compression better)
        c                       \P    # split on P: ['ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT', 'NINE']
   m                                  # map over this list (variable: d)
    }dyQ                              # is d a (ordered) subset of the input (Q)? (= element of the powerset)
  x                                1  # get the index of the first true
+1                                    # add one, because the list was indexed at 0 and conveniently -1 (not found) becomes 0

```
> 1 votes

# Answer
# Java, 254 bytes

```
int g(String a,String b){int i=0,p=0;for(char c:a.toCharArray()){p=i;i=b.indexOf(c);if(i<=p)return 0;}return 1;}
String f(String a){String[]T={"ONE","TWO","THREE","FOUR","FIVE","SIX","SEVEN","EIGHT","NINE"};for(String t:T)if(g(t,a)>0)return t;return"NO";}

```

**Try Online**

```
boolean g(String a,String b)
{
    int i = 0, p = 0;
    for(char c:a.toCharArray())
    {
        p = i;
        i = b.indexOf(c);
        if(i <= p) return false;
    }
    return true;
}

String f(String a)
{
    String[]T={"ONE","TWO","THREE","FOUR","FIVE","SIX","SEVEN","EIGHT","NINE"};
    for(String t:T)if(g(t,a))return t;
    return"NO";
}

```
> 1 votes

# Answer
# C, 198 bytes

**Try Online**

```
char*T[]={"ONE","TWO","THREE","FOUR","FIVE","SIX","SEVEN","EIGHT","NINE"};
g(char*a,char*b){while(*a&*b)a+=(*b++==*a);return!*a;}
i;char*f(char*b){for(i=0;i<9;i++)if(g(T[i],b))return T[i];return"NO";}

```
> 1 votes

# Answer
# Python 2, 155 bytes

```
import re;lambda k:next((i for i,j in enumerate([re.search('.*'.join(list(s)),k)for s in'ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE'.split()])if j),-1)+1

```

An anonymous function searching for regex group. Not the best solution here in Python but an alternative way.
> 1 votes

# Answer
# Vyxal, ~~9~~ 8 bytes

```
9'∆ċ?ṗṠc

```

Try it Online!

-1 thanks to EmanresuA

9 bytes but faster:

```
9'∆ċ:?Þ∩=

```

Try it Online!

The joys of having number to word built-ins!

## Explained

```
9'∆ċ:?Þ∩=
9'        # From the range [1, 9], keep only items n where:
  ∆ċ      #   n as a word
     ?Þ∩  #   under multiset intersection with the input
    :   = #   is the same.

```
> 1 votes

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


title: Does there exist a synchronizing word?

text:
# Question
Title: Does there exist a synchronizing word?
A complete deterministic finite automaton is a machine, with some states. Each state in the automaton has, for each character in the alphabet, a pointer to a state (not necessarily a different one). The automaton starts at some state, and then reads a string, character by character. For each character, the automaton moves to the pointer of its current state for the character.

For a given automaton, a synchronizing word is a string which will bring the automaton to the same state, regardless of which state it started in.

For example, the following automaton:

Has `0100` as a synchronizing word, which synchronizes all states to 2.

Not all automata have a synchronizing word. For example, the following automaton:

Doesn't have any synchronizing word - if the length of the string is even then 0 will stay in 0 and 1 will stay in 1, and if it's odd they will swap - in any case, they won't go into the same state.

Your challenge is to write the shortest program you can that checks, given a complete automaton over an alphabet with two characters, if there exists a synchronizing word for it.

# Test cases

Using a 0-indexed, 2Xn array.

```
[[0, 1], [0, 1]] -> true
[[1, 1], [0, 0]] -> false
[[0, 0], [1, 1]] -> false
[[4, 1], [0, 3], [0, 0], [0, 1], [4, 3]] -> true
[[2, 1], [3, 4], [0, 4], [2, 1], [0, 3]] -> true
[[4, 4], [0, 4], [2, 1], [0, 3], [0, 0]] -> false
[[8, 5], [0, 8], [0, 0], [8, 2], [2, 6], [5, 2], [3, 8], [7, 3], [8, 4], [3, 0]] -> true
[[9, 2], [8, 4], [2, 5], [6, 9], [8, 9], [9, 5], [4, 0], [4, 2], [0, 7], [2, 1]] -> true
[[5, 0], [3, 7], [9, 2], [9, 0], [1, 8], [8, 4], [6, 5], [7, 1], [2, 4], [3, 6]] -> true
[[5, 1], [4, 9], [8, 1], [8, 6], [2, 3], [7, 0], [2, 3], [5, 6], [4, 9], [7, 0]] -> false
[[6, 3], [1, 1], [7, 5], [7, 1], [4, 5], [6, 6], [4, 6], [5, 1], [3, 4], [2, 4]] -> false

```

# Rules

* You can use any reasonable I/O format. In particular, any of the following input methods are allowed:
    + A map, multidimensional array, or array of maps, denoting, for each state and character, to which state the automaton transitions. The states can be either 0-indexed or 1-indexed.
    + Any builtin directed graph object which can support multiedges, self-loops, and labeled edges.
    + Any builtin DFA object.
    + You can choose any two characters to be the alphabet.
* You can output any two distinct values, or a truthy/falsey (or reversed) value in your language.
* You may **not** assume Černý's conjecture (which states that if there exists a synchronizing word, there must be one of length \\$(n-1)^2\\$).
* Standard loopholes are disallowed.

# Answer
# Python, ~~92~~ 91 bytes

```
f=lambda a,s,n=0:n<len(s)**3and any(f(a,[a[t][d]for t in s],n+1)for d in"01")or len({*s})<2

```

Attempt This Online!

Takes in an automaton `a` which is a dictionary of dictionaries where `a[x][c]` describes the state to travel to from state `x` given character `c`, and an array `s` which contains all of the states of the automaton. The characters in the alphabet are the strings `0` and `1`.

This code does a very inefficient brute force iteration over all possible words with length less than \\$n^3\\$ (where \\$n\\$ is number of states).

---

-1 byte from @Steffan

# Python, 87 bytes

```
f=lambda a,s,q,n=0:n<q**3and any(f(a,{a[t][d]for t in s},q,n+1)for d in"01")or len(s)<2

```

Attempt This Online!

Same as above, except it also takes in a parameter `q` which describes the number of states in the automaton.
> 4 votes

# Answer
# Python3, 471 bytes:

```
E=enumerate
def f(n,m,c=[]):
 yield c,n
 for i,(I,a)in E(m[n]):M=eval(str(m));del M[n][i];yield from f(a,M,c+[(a,I)])
def M(m,B,p):
 if''==p:return B
 return M(m,dict(m[B])[int(p[0])],p[1:])
def F(m):
 r={}
 for i,_ in E(m):
  for c,n in f(i,m,[(i,-1)]):
   if c[-1][-1]!=-1 or c[-1][1]:r[n]=r.get(n,[])+[(i,c)]
 for n in r:
  if not(V:={i for i,_ in E(m)})-{a for a,_ in r[n]}:
   if any(all(M(m,B,''.join(str(K)for _,K in c[1:]))==n for B in V)for _,c in r[n]):return 1

```

Try it online!

A little longer than the other solutions, but solves all the test cases pretty quickly. Returns `1` when a synchronizing word exists and `None` when one does not exist.
> 1 votes

# Answer
# Haskell, 73 bytes

```
r!w|let[_]%_=1>0;s%y=all(/=s)y&&or[[u|u<-w,elem u$k<$>s]%(s:y)|k<-r]=w%[]

```

Try it online!

Takes input as a list of states, and a list of transitions as functions between states.

Not complicated, does a depth first search.
> 1 votes

# Answer
# Ruby, ~~100~~ 91 bytes

```
->s{a,*k=r=s.transpose;r|=k|=a.map{|i|s[i]}.transpose-r while a=k.pop;r.any?{|x|!(x|x)[1]}}

```

Try it online!
> 0 votes

# Answer
# Jelly, 21 bytes

```
WZ€ị®ẎƊ⁸©L*3¤Ð¡ẎZ€ẎEƇ

```

A monadic Link that accepts a 1-indexed list of nodes, each of which is a pair of positive integers identifying the nodes pointed to by each of the two transition characters (i.e. like the test cases in the question but incremented by one) and yields an empty list (falsey) if no synchronising word exists or a non-empty list (truthy) if one does.

**Try it online!**
...Too slow for the length 5 and greater tests, but since all of those that do have synchronising words are much shorter this, which searches only up to length \\$n+2\\$ gives the correct output for all test cases.

### How?

Full brute force - generates the list of nodes (by starting node) pointed to by all words from length one up to length \\$n^3+1\\$ (more than the current known upper bound) and keeps any that are all equal.

```
WZ€ị®ẎƊ⁸©L*3¤Ð¡ẎZ€ẎEƇ - Link: list of pairs of integers, A
W                     - wrap A in a list
             Ð¡       - collect and repeat... (includes the original wrapped A)
            ¤         - ...number of times: nilad followed by links as a nilad:
       ⁸              -                       chain's left argument = A
        ©             -                       (copy to the register)
         L            -                       length
          *3          -                       to the third power
      Ɗ               - ...action: last three links as a monad:
 Z€                   -              transpose each
   ị®                 -              index into the register
     Ẏ                -              tighten
               Ẏ      - tighten
                Z€    - transpose each
                  Ẏ   - tighten
                    Ƈ - keep those for which:
                   E  -   all equal? (i.e. all point to the same node)

```

---

**20 bytes** if a full program can output nothing if no synchronising word exists or a (not consistent) list representation if one does - uses the same method:

```
WZ€ị³ẎƊ³L*3¤Ð¡ẎZ€ẎEƇ

```
> 0 votes

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


title: Sort spelled-out serial numbers

text:
# Question
Title: Sort spelled-out serial numbers
Given a list of two or more spelled-out serial numbers of equal length greater than two, e.g.

```
[[ "three" , "one"  , "four"  ],
 [ "one"   , "five" , "nine"  ],
 [ "two"   , "six"  , "five"  ],
 [ "three" , "five" , "eight" ]]

```

sort the list by the numbers that the words represent:

```
[[ "one"   , "five" , "nine"  ],
 [ "two"   , "six"  , "five"  ],
 [ "three" , "one"  , "four"  ],
 [ "three" , "five" , "eight" ]]

```

You may require the numbers to be spelled in lower or upper, but not mixed, case.

### Test cases

`[["three","one","four"],["one","five","nine"],["two","six","five"],["three","five","eight"]]`
gives
`[["one","five","nine"],["two","six","five"],["three","one","four"],["three","five","eight"]]`

`[["two","seven"],["one","eight"],["two","eight"],["one","eight"],["two","eight"],["four","five"]]`
gives
`[["one","eight"],["one","eight"],["two","seven"],["two","eight"],["two","eight"],["four","five"]]`

`[["one","four","one","four","two"],["one","three","five","six","two"],["three","seven","three","zero","nine"]]`
gives
`[["one","three","five","six","two"],["one","four","one","four","two"],["three","seven","three","zero","nine"]]`

`[["zero","six","one"],["eight","zero","three"],["three","nine","eight"],["eight","seven","four"],["nine","eight","nine"],["four","eight","four"]]`
gives
`[["zero","six","one"],["three","nine","eight"],["four","eight","four"],["eight","zero","three"],["eight","seven","four"],["nine","eight","nine"]]`

# Answer
> 15 votes
# Husk, ~~9~~ 8 bytes

```
Ö†€¨tfṡn

```

Try it online!

Algorithm "inspired" by recursive's Stax answer (I've just changed the lookup string a bit), go upvote him!

The trick is mapping each letter to its position in the string `tfsen` (compressed at the end of this program). Husks lists are 1-based, and missing items return 0, so we get this mapping:

```
"one"        [0,5,4]
"two"        [1,0,0]
"three"      [1,0,0,4,4]
"four"       [2,0,0,0]
"five"       [2,0,0,4]
"six"        [3,0,0]
"seven"      [3,4,0,4,5]
"eight"      [4,0,0,0,1]
"nine"       [5,0,5,4]

```

As you can see, the lists are perfectly ordered.

---

In order to be clear, here's how list comparison works in Husk (and in many other languages):

1. If one of the two lists is empty, that's the smaller one.
2. If the first elements of the two lists are different, the one with the smaller first element is the smaller list.
3. Otherwise, discard the first element from both lists and go back to point 1.

# Answer
> 10 votes
# Stax, ~~24~~ ~~22~~ ~~17~~ ~~16~~ 14 bytes

```
▄Ωφ▐╧Kìg▄↕ñ▼!█

```

Run and debug it

This program takes arrays of lowercase spelled digits for input. The output is newline-separated like so.

```
one five nine
two six five
three one four
three five eight

```

This program sorts the inputs using the ordering obtained under a specific transformation. Each character in each word is replaced by its index in the string `"wo thif sen"`. The original arrays are sorted by this ordering. Then the results are printed after joining with a space.

The spaces serve no purpose, but actually allow greater compression in the string literal.

# Answer
> 7 votes
# Python, 62 bytes

```
lambda m:sorted(m,key=lambda r:[int(s,36)%6779%531for s in r])

```

**Try it online!** ...or see the test-suite

Note:

```
lambda m:sorted(m,key=lambda r:[map("trfsen".find,s)for s in r])

```

which works in Python 2 (but not 3) is longer by two bytes.

# Answer
> 6 votes
# Jelly, 12 bytes

```
OḌ%⁽Ð¢%147µÞ

```

A monadic link.

**Try it online!** ...or see the test-suite

### How?

Converting the digits to ordinals and then from base 10 then taking modulos by 4752 then 147 gives an ascending order:

```
 zero            , one         , two         , three               , four
[122,101,114,111],[111,110,101],[116,119,111],[116,104,114,101,101],[102,111,117,114]
 133351          , 12301       , 12901       , 1276511             , 114384
 295             , 2797        , 3397        , 2975                , 336
 1               , 4           , 16          , 35                  , 42

 five            , six         , seven               , eight               , nine
[102,105,118,101],[115,105,120],[115,101,118,101,110],[101,105,103,104,116],[110,105,110,101]
 113781          , 12670       , 1263920             , 1126456             , 121701
 4485            , 3166        , 4640                , 232                 , 2901
 75              , 79          , 83                  , 85                  , 108

```

This can then be used as a key function by which to sort:

```
OḌ%⁽Ð¢%147µÞ - Link: list of lists of lists of characters
          µÞ - sort (Þ) by the mondadic chain to the left (µ):
O            -   ordinals of the characters
 Ḍ           -   convert from base 10
   ⁽Ð¢       -   literal 4752
  %          -   modulo
      %147   -   modulo by 147

```

# Answer
> 6 votes
# APL (Dyalog Classic), 12 bytes

```
'nesft'∘⍒⌷¨⊂

```

Try it online!

This is how I found a suitable left argument for dyadic  (I tried  and length 6 first):

```
A←⊖a←↑'zero' 'one' 'two' 'three' 'four' 'five' 'six' 'seven' 'eight' 'nine'
{(a≡a[⍵⍒a;])∧A≡a[⍵⍒A;]:⎕←⍵}¨,⊃∘.,/5⍴⊂∪∊a

```

# Answer
> 5 votes
# Ruby, 48 bytes

```
->x{x.sort_by{|y|y.map{|s|s.to_i(35)**2%47394}}}

```

Abuses the fact that `"zero".to_i(35)` is 0 (since 'z' isn't a valid digit in base 35), so it's that much easier to brute-force a formula for the other nine digits.

# Answer
> 4 votes
# Ruby, 47 bytes

```
->x{x.sort_by{|y|y.map{|s|s.to_i(32)%774%538}}}

```

**Try it online!**

Utilises the fact that using a base less than the maximum digit yields a result of zero (as pointed out by histocrat in their answer)

# Answer
> 4 votes
# K (ngn/k), ~~14~~ 18 bytes

```
{x@<"tfsen"?/:/:x}

```

Try it online!

# Answer
> 3 votes
# Python 2, ~~85~~ ~~81~~ 80 bytes

Simply uses the first two letters of each word to determine the number, then sorts each list using that indexing function as the key.

```
lambda _:sorted(_,key=lambda L:['zeontwthfofisiseeini'.find(s[:2])/2for s in L])

```

**Try it online!**

*Saved 4 bytes, thanks to Jonathan Allan*

# Answer
> 3 votes
# Perl 6, 37 bytes

```
*.sort:{('digit 'X~$_)».parse-names}

```

Try it

## Expanded:

```
*\     # WhateverCode lambda (this is the parameter)
.sort:
{  # block with implicit parameter ｢$_｣
  (
    'digit ' X~ $_  # concatenate 'digit ' to each named digit
  )».parse-names    # call .parse-names on each
}

```

The code block will take a value of the form `("three","one","four")` and translate it to `("3","1","4")` which is a value that `.sort` can easily use.

# Answer
> 3 votes
# APL (Dyalog), 38 bytes

```
{⍵[⍋(531∘⊥⍤1)(531|6779|36⊥9+⎕A⍳⊢)¨↑⍵]}

```

Try it online!

Based of Jonathan Allan's awesome solution.

# Answer
> 2 votes
# JavaScript (Node.js), 70 bytes

```
a=>a.sort((a,b)=>(g=a=>a.map(c=>99+parseInt(2+c,34)%607%292))(a)>g(b))

```

Try it online!

# Answer
> 2 votes
# Ruby, 49 bytes

```
->x{x.sort_by{|y|y.map{|s|s.to_i(36)**4%463595}}}

```

Try it online!

# Answer
> 2 votes
# Haskell, 133 122 109 107 106 bytes

```
import Data.List
sortOn$abs.read.(>>=show.head.(`elemIndices`words"ze on tw th fo fi si se ei ni").take 2)

```

Ungolfed:

```
import Data.List

nums = ["ze","on","tw","th","fo","fi","si","se","ei","ni"]

lookup' :: Eq a => a -> [a] -> Int
lookup' v = head . elemIndices v

wordToInt :: String -> Int
wordToInt (x:y:_) = lookup' [x,y] nums

wordsToInt :: [String] -> Int
wordsToInt = read . concatMap (show . wordToInt)

sortN :: [[String]] -> [[String]]
sortN = sortOn wordsToInt

```

# Answer
> 2 votes
# 05AB1E, 27 bytes

```
Σ“¡×€µ‚•„í†ìˆÈŒšï¿Ÿ¯¥Š“#skJ

```

Try it online!

---

```
Σ                           # Sort input by...
 “¡×€µ‚•„í†ìˆÈŒšï¿Ÿ¯¥Š“     # "zero one two three four five size seven eight nine"
                       #    # Split on spaces.
                        sk  # Find index of each input...
                          J # Join up.

```

# Answer
> 2 votes
# Python 2, 59 bytes

```
lambda m:sorted(m,key=lambda r:[hash(s)%2249518for s in r])

```

Try it online!

Riffing on Jonathan Allan's Python 3 solution...

# Answer
> 2 votes
# Java (JDK 10), 132 bytes

```
l->{l.sort((a,b)->s(a)-s(b));}
int s(String[]a){int v=0;for(var s:a)v=v*99+"zeontwthfofisiseini".indexOf(s.substring(0,2));return v;}

```

Try it online!

# Answer
> 1 votes
# Jelly, ~~30~~ ~~28~~ 27 bytes

```
w@€“¡¦ẇṆb~ṇjṚØ%ĖġṘḥḞṾṇJḌ»µÞ

```

Try it online!

-1 thanks to Jonathan Allan.

Finds the index of each digit in the string ‘onetwo...nine’ then sorts using this as a key function with `Þ`. Don't need to include `'zero'` at the beginning because the search for the first two characters of `'zero'` will fail and `0` will be returned instead of an index, making `'zero'` lexicographically "early".

# Answer
> 1 votes
# Perl 5, 103 bytes

```
sub c{pop=~s%(..)\w+\s*%zeontwthfofisiseeini=~/$1/;$`=~y///c/2%ger}say s/\R//gr for sort{c($a)<=>c$b}<>

```

Try it online!

# Answer
> 1 votes
# Retina 0.8.2, 38 bytes

```
T`z\o\wit\hfsen`d
O`
T`d`z\o\wit\hfsen

```

Try it online! Link includes test suite. Works by temporarily replacing the letters `zowithfsen` with their position in that string, which allows the numbers to be sorted lexically.

# Answer
> 1 votes
# Python 3, 141 bytes

```
print(sorted(eval(input()),key=lambda l:int(''.join([str("zero one two three four five six seven eight nine".split().index(i))for i in l]))))

```

Try it online!

# Answer
> 1 votes
# C (clang), 229 bytes

```
y,j,k,t[9];char *s="zeontwthfofisiseeini";r(char **x){for(j=y=k=0;k+1<strlen(*x);k+=j,y=y*10+(strstr(s,t)-s)/2)sscanf(*x+k,"%2[^,]%*[^,]%*[,]%n",t,&j);return y;}c(*x,*y){return r(x)-r(y);}f(*x[],l){qsort(&x[0],l,sizeof(x[0]),c);}

```

Try it online!

There is no straightforward way of sending array of array of strings to C functions, so in spirit of code-golf, I have taken a minor liberty in input format.

`f()` accepts an array of pointers to strings, where each string is a number, represented by comma separated spelled-out-digits in lower-case. Additionally, it needs number of strings in array in second parameter. I hope this is acceptable.

`f()` replaces the pointers in place in sorted order using `qsort()`.
`r()` reads input number from comma-separated number string. It only compares first two characters to identify number.
`c()` is comparison function

# Answer
> 0 votes
# Ruby, 64 bytes

```
->a{a.sort_by{|b|b.map{|n|"zeontwthfofisiseeini".index n[0,2]}}}

```

Try it online!

A lambda accepting a 2D array of strings and returning a 2D array of strings.

Piggybacking off of mbomb007's Python 2 answer for -26 bytes off of what I was about to post.

# Answer
> 0 votes
# Vyxal, 10 bytes

```
µ→λf∆ċ←⁼;Ṅ

```

Try it Online!

Can be a little bit slow for serial numbers that represent larger decimal numbers, as the explanation will show. Who needs lookup strings anyway?

## Explained

```
µ→λf∆ċ←⁼;Ṅ
µ          # Sort the input by:
 →         #  putting the item into a temporary variable (needed for scoping purposes)
  λ     ;Ṅ #  and getting the first non-negative integer where:
   f∆ċ     #    converting each of the digits in the number to words
      ←⁼   #    equals the list being considered.

```

---
Tags: code-golf, string, array, sorting, natural-language
---


title: The "Fly straight, dammit" sequence

text:
# Question
Title: The "Fly straight, dammit" sequence
## Background

"Fly straight, dammit" (OEIS A133058) is a sequence of integers, which has these rules:

* \\$a\_0 = a\_1 = 1\\$
* \\$a\_n = a\_{n-1}+n+1\\$ *if* \\$gcd(a\_{n-1}, n) = 1\\$
* *Otherwise,* \\$a\_n = \frac{a\_{n-1}}{gcd(a\_{n-1}, n)}\\$

In pseudocode:

```
a[0] = a[1] = 1
if gcd(a[n-1], n) == 1 then
    a[n] = a[n-1] + n + 1
else
    a[n] = a[n-1] / gcd(a[n-1], n)

```

(GCD stands for "Greatest Common Divisor". For example, `GCD(8, 12)` = 4.)

The graph for this function looks like this:

After n=638, it goes into four straight lines (\\$y=1\\$ and \\$y=2\\$ are indistinguishable in this picture, but they are separate lines).

> 'Whenever I look at this sequence I am reminded of the great "Fly straight, dammit" scene in the movie "Avatar".' - N. J. A. Sloane

## Your task

You have to:

* accept an input, n, from the user (it will be a positive integer)
* calculate \\$a\_n\\$ and output (this is so any output is fine)

This is so shortest answer in bytes wins!

# Answer
# 05AB1E, 12 bytes

```
1‚λDN¿DiNOë÷

```

Outputs the infinite sequence.

Try it online.

**Explanation:**

```
1           # Push 1
 ‚          # Pair the top two values together. Since there is only one value on the
            # stack and there is no input, it implicitly uses the last value that was
            # on the stack, resulting in [1,1]

  λ         # Start a recursive environment,
            # to output the infinite sequence
            # (which is output implicitly afterwards)
1‚          # Start with a(0)=a(1)=1
            # Where every following a(n) is calculated as:
            #  (implicitly push a(n-1) to the stack)
   D        #  Duplicate a(n-1)
    N       #  Push n
     ¿      #  Pop one a(n-1) and n, and calculate their GCD
      D     #  Duplicate this gcd(a(n-1),n)
       i    #  If it's 1:
        N   #   Push n again
         O  #   Sum the three values on the stack: a(n-1)+gcd(a(n-1),n)+n,
            #   where gcd(a(n-1) is always 1 in this case
       ë    #  Else:
        ÷   #   Integer-divide a(n-1) by gcd(a(n-1),n)

```
> 7 votes

# Answer
# C (GCC), 65 bytes

```
t,r;h(a,b){r=b?h(b,a%b):a;}c(n){n=n<2?:h(t=c(n-1),n)<2?t-~n:t/r;}

```

Attempt This Online!

This is based on py3programmer's answer; I'm posting this mostly for their benefit since they say they didn't fully understand the golfing suggestions I gave.

Here's their current version:

```
h(a,b){if(b){return h(b,a%b);}else{return a;}}c(n){if(n<2){return 1;}if(h(c(n-1),n)<2){return c(n-1)+n+1;}else{return c(n-1)/h(c(n-1),n);}}

```

The first thing I did was convert the `if`/`else` statements into `?`/`:` conditional expressions. You can read `x?y:z` as "if x then y, otherwise z".

```
h(a,b){return b?h(b,a%b):a;}c(n){return n<2?1:h(c(n-1),n)<2?c(n-1)+n+1:c(n-1)/h(c(n-1),n);}

```

GCC has a non-standard extension to C that lets you use `x?:z` to mean "if x, then x, otherwise z":

```
h(a,b){return b?h(b,a%b):a;}c(n){return n<2?:h(c(n-1),n)<2?c(n-1)+n+1:c(n-1)/h(c(n-1),n);}

```

Another quirk of GCC, when used in `-O0` optimisation mode (which is the default), is that the CPU register used for the return value of a function is the same as the one used for its first parameter. As a result, we can replace `return`  statements with assignments to the first parameter for both functions:

```
h(a,b){a=b?h(b,a%b):a;}c(n){n=n<2?:h(c(n-1),n)<2?c(n-1)+n+1:c(n-1)/h(c(n-1),n);}

```

Then I noticed that the value `c(n-1)` is reused quite a lot, so I extracted it into a temporary variable:

```
t;h(a,b){a=b?h(b,a%b):a;}c(n){n=n<2?:h(t=c(n-1),n)<2?t+n+1:t/h(t,n);}

```

I declared it as a global variable, because that doesn't require a type in the declaration, but it makes no difference in functionality.

Then I made use of this tip which states that `x+y+1` can be shortened to `x-~y` (because `~y` is equivalent to `-y - 1`)

```
t;h(a,b){a=b?h(b,a%b):a;}c(n){n=n<2?:h(t=c(n-1),n)<2?t-~n:t/h(t,n);}

```

I also noticed that `h(t,n)` is reused, so I modified `h` to store its result in a global variable `r` as well as providing it as a return value. We can then use `r` instead of calling `h` again:

```
t,r;h(a,b){r=a=b?h(b,a%b):a;}c(n){n=n<2?:h(t=c(n-1),n)<2?t-~n:t/r;}

```

As pointed out by Kevin Cruijssen in a comment, the `a=` assignment turns out to be unnecessary. Why, exactly, is beyond me, but it seems GCC just stores the value in the return register by happenstance.

```
t,r;h(a,b){r=b?h(b,a%b):a;}c(n){n=n<2?:h(t=c(n-1),n)<2?t-~n:t/r;}

```
> 7 votes

# Answer
# Prolog (SWI), ~~68~~ 56 bytes

*-12 bytes thanks to @Steffan*

```
N+X:-N>1,N-1+B,C=gcd(B,N),(C<2,X is B+N+1;X is B/C);X=1.

```

Try it online!
> 4 votes

# Answer
# C (gcc), 234 210 143 139 bytes

Thanks to pxeger for removing a few bytes. Check out his improved answer.

```
h(a,b){if(b){return h(b,a%b);}else{return a;}}c(n){if(n<2){return 1;}if(h(c(n-1),n)<2){return c(n-1)+n+1;}else{return c(n-1)/h(c(n-1),n);}}

```
> 3 votes

# Answer
# JavaScript (ES6),  ~~55~~  53 bytes

```
f=(n,a=n,b=q=n>1?f(n-1):-1)=>b?f(n,b,a%b):q/a-~n*!~-a

```

Try it online!

### Commented

```
f = (                // f is a recursive function taking:
  n,                 //   n = input
  a = n,             //   a = 1st argument of the GCD, initialized to n
  b = q =            //   b = 2nd argument of the GCD, initialized to ...
    n > 1 ? f(n - 1) //       q = f(n - 1) if n > 1
          : -1       //       q = -1 if n ≤ 1 (which will force the GCD
) =>                 //           to be evaluated as -1 as well)
  b ?                // if b is not equal to 0:
    f(n, b, a % b)   //   keep computing the GCD with a recursive call
  :                  // else:
                     //   the GCD is now loaded in a
    q / a -          //   return q / a
    ~n * !~-a        //   add n + 1 if a = 1
                     //   (if q was set to -1, we get -1/-1-~n*0 = 1)

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 47 bytes

```
If[#<2,1,If[(s=GCD[#,d=#0[#-1]])<2,d+#+1,d/s]]&

```

Try it online!

-4 bytes from alephalpha
> 3 votes

# Answer
# Python, 68 bytes

```
import math
f=lambda n:n<2or(a:=f(n-1))//(q:=math.gcd(a,n))-~n*(q<2)

```

Attempt This Online!
> 2 votes

# Answer
# Ruby, ~~59 ...~~ 48 bytes

```
->n{k=z=1;3.upto(n){|v|z=v.gcd k=z>1?k/z:k+v};k}

```

Try it online!
> 2 votes

# Answer
# Python 3, <sup>~~115~~</sup> 109 bytes

```
from math import*
def f(n):
 l=1
 for i in range(2,n+1):
  g=gcd(l,i)
  if g==1:l+=i+1
  else:l//=g
 print(l)

```

Try it online!

Ungolfed:

```
from math import gcd                               # Function for getting gcd of two numbers
def fsd_sequence(n):                               # Define function to get the nth value of the sequence
    prev = 1                                       # The previous value (a[n-1])
    for i in range(2, n + 1):                      # Iterate through numbers from 2 to n+1
        greatest_common_divisor = gcd(prev, i)     # GCD of previous value and i
        if greatest_common_divisor == 1:           # If GCD equals 1,
            prev = prev + i + 1                    # Increment the previous value by i+1
        else:                                      # Otherwise
            prev = prev // greatest_common_divisor # Set the previous value to itself divided by the GCD
    return l                                       # Return the last value

```
> 1 votes

# Answer
# Vyxal, 15 bytes

```
λ1>[‹x~ġ:ċ[ḭ|++

```

Try it Online!
> 1 votes

# Answer
# PARI/GP, 44 bytes

```
f(n)=if(n<2,1,2>s=gcd(n,d=f(n-1)),d+n+1,d/s)

```

Attempt This Online!
> 1 votes

# Answer
# Raku, 46 bytes

```
1,1,{$_/($!=(++$+1)gcd$_)+(++$+2)*($!==1)}...*

```

Try it online!

This is an expression for the infinite sequence.
> 1 votes

# Answer
# Japt, 17 bytes

Outputs the first `n` terms. I feel like I'm missing a trick here to save a byte or 2.

```
ÈjY ?XÒY:X/yY}hBì

```

Try it

```
ÈjY ?XÒY:X/yY}hBì     :Implicit input of integer U
È                     :Function taking an integer X and an index Y as arguments
 jY                   :  Are X & Y co-prime?
    ?                 :  If so then return
     XÒY              :    X-~Y = X+Y+1
        :             :  Else return
         X/           :    X divided by
           yY         :    GCD of X & Y
             }        :End function
              h       :Repeatedly take the last element of the following array, pass it through the function and push it back to the array until it reaches length U
               B      :  11
                ì     :  To digit array
                      :Implicit output of resulting array

```
> 0 votes

# Answer
# PowerShell Core, 111 bytes

```
for($i=$r=1;$i-lt"$args"){for($a,$b=++$i,$r;$b){if($a-gt$b){$b,$a=$a,$b}$b%=$a}$r=(($r/$a),($r+$i+1))[!--$a]}$r

```

Try it online!

Outputs the \\$n^{th}\\$ term of the sequence

All the terms for 102 bytes
> 0 votes

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