title: Let's decrease the monotony

text:
# Question
Title: Let's decrease the monotony
### ...but hey, no need to be strict.

Given a non-empty array of strictly positive integers, determine if it is:

1. *Monotone strictly decreasing*. This means that each entry is strictly less than the previous one.
2. *Monotone non-increasing, but not strictly decreasing*. This means that each entry is less than or equal to the preceding, and the array does not fall in the above category.
3. *None of the above*.

Note the following corner cases:

* An array with a single number is monotone strictly decreasing (vacuously so).
* An array with the same number repeated is monotone non-increasing, but not strictly decreasing.

# Rules

You may provide a program or a function

Input can be taken in any reasonable format: array, list, string with numbers separated by spaces, ...

You can choose any three consistent outputs for the three categories respectively. For example, outputs can be numbers `0`, `1`, `2`; or strings `1 1`, `1 0`, empty string.

Shortest code in bytes wins

# Test cases

Monotone strictly decreasing:

```
7 5 4 3 1
42 41
5

```

Monotone non-increasing, but not strictly decreasing:

```
27 19 19 10 3
6 4 2 2 2
9 9 9 9

```

None of the above:

```
1 2 3 2
10 9 8 7 12
4 6 4 4 2

```

# Answer
> 10 votes
# Jelly, ~~10 9~~ 5 bytes

-Method found by DrMcMoylex, go give some credit!

```
;0IṠṀ

```

**TryItOnline!** or run all tests

Returns :`-1`=monotone strictly decreasing; `0`=monotone non-increasing; `1`=other.

### How?

```
;0IṠṀ - Main link: list
;0    - concatenate with a zero
  I   - incremental differences
   Ṡ  - sign
    Ṁ - maximum

```

# Answer
> 22 votes
# Perl 6, 17 bytes

```
{[>](@_)+[>=] @_}

```
* Monotone strictly decreasing: `2`
* Monotone non-increasing: `1`
* Other: `0`

## Expanded:

```
{            # bare block lambda with implicit parameter list ｢@_｣
  [>]( @_ )  # reduce using ｢&infix:« > »｣
  +
  [>=] @_    # reduce using ｢&infix:« >= »｣
}

```

# Answer
> 14 votes
# MATL, ~~10~~, 7 bytes

```
0hdX>ZS

```

Try it online! or verify all test cases!

*3 bytes saved, thanks to @LuisMendo!*

The outputs are

* Strictly decreasing: -1
* Non-increasing: 0
* Other: 1

Explanation:

```
0           % Push a '0'
 h          % Join the 0 to the end of the input array.
  d         % Get consecutive differences
   X>       % Get the largest difference
     ZS     % Get its sign
            % Implicitly print it

```

# Answer
> 9 votes
# Mathematica, 22 bytes

```
Sign@*Max@*Differences

```

Unnamed function taking a list of numbers as input. Returns `-1` if the list is strictly decreasing, `0` if it's nonincreasing but not strictly decreasing, and `1` if it's neither.

Pretty simple algorithm: take the differences of consecutive pairs, take the largest one, and take the sign of that largest one.

(I feel like there must exist some language in which this algorithm is 3 bytes....)

Regarding an array with a single entry: `Differences` yields an empty list; `Max` of an empty list gives `-∞` (!); and `Sign[-∞]` evaluates to `-1` (!!). So it actually works on this corner case. Gotta love Mathematica sometimes. (Indeed, the function also correctly labels an empty list as strictly decreasing.)

# Answer
> 7 votes
## Haskell, ~~40~~ ~~38~~ 37 bytes

```
foldl min GT.(zipWith compare<*>tail)

```

Returns

* `GT` for Monotone strictly decreasing
* `EQ` for Monotone non-increasing
* `LT` else

`compare` compares two numbers and returns `GT` (`EQ`, `LT`) if the first number is greater than (equal to, less than) the second number. `zipWith compare<*>tail` compares neighbor elements. `foldl min GT` reduces the list of the comparison results with the min function starting with GT (note: `LT` \< `EQ` \< `GT`).

Edit: @xnor found ~~2~~ 3 bytes. Thanks!

# Answer
> 6 votes
## Common Lisp, ~~43~~ 40 bytes

```
(defun f(x)`(,(apply'> x),(apply'>= x)))

```

This takes input as a Lisp list, and returns `(T T)`, `(NIL T)` and `(NIL NIL)` to distinguish the 3 categories. Here it is running on the provided test cases:

```
CL-USER> (mapcar #'f '((7 5 4 3 1)
                       (42 41)
                       (5)
                       (27 19 19 10 3)
                       (6 4 2 2 2)
                       (9 9 9 9)
                       (1 2 3 2)
                       (10 9 8 7 12)
                       (4 6 4 4 2)))
((T T) (T T) (T T) (NIL T) (NIL T) (NIL T) (NIL NIL) (NIL NIL) (NIL NIL))

```

# Answer
> 6 votes
## Python 2, 30 bytes

```
lambda l:max(map(cmp,l[1:],l))

```

`-1` for strictly decreasing, `0` for weakly decreasing, `+1` for non-decreasing

Using `cmp` to compare consecutive elements, and takes the maximum. This is done by removing the first element of one copy of the list, then mapping `cmp` . For example, `l=[2,2,1]` gives

```
l[1:]  2   1   None
l      2   2   1
cmp    0  -1   -1

```

which has `max` 0 because an equality exists.

The shorter list is automatically extended with `None`, which is less than all numbers and so harmless. This phantom element also insulates against taking the `min` of an empty list when the input has length 1.

# Answer
> 5 votes
# Brachylog, 7 bytes

```
>,1|>=,

```

Try it online!

This prints `1` for strictly decreasing, `0` for non-increasing and `false.` otherwise.

### Explanation

```
  (?)>              Input is a strictly decreasing list
      ,1(.)         Output = 1
|                 Or
  (?)>=             Input is a non-increasing list
       ,(.)         Output is a free variable; gets automatically labeled as an integer at
                      the end of execution. Since its domain is [-inf, +inf], the first
                      value it takes is 0
                  Or
                    No other possibility, thus this main predicate is false.

```

### Other 7 bytes solutions

```
>=!>,;1           Returns 0 for strictly decreasing, false. for non-increasing, 1 otherwise.

>=!>,1|           Returns 1 for strictly decreasing, false. for non-increasing, 0 otherwise.

```

# Answer
> 4 votes
## R, 44 bytes

```
d=diff(scan());c(any(!d)&all(d<=0),all(d<0))

```

Reads input from stdin and prints the following depending on the input:

**Output:**

`[1] FALSE TRUE`: Monotone non-increasing

`[1] TRUE FALSE`: Monotone strictly decreasing

`[1] FALSE FALSE`: None of the above

# Answer
> 3 votes
## JavaScript (ES6), 51 bytes

```
a=>a.some((e,i)=>e>a[i-1])+a.some((e,i)=>e>=a[i-1])

```

Returns 0 for strict decreasing, 1 for non-increasing, 2 otherwise.

# Answer
> 3 votes
# 05AB1E, ~~5~~ 8 bytes

Bug fixed by Emigna, thanks! It uses the same method as DrMcMoylex's.

```
®¸ì¥Z0.S

®¸ì   Implicitly take input and appends -1 to it
¥     Yield deltas
 Z    Take the largest delta
  0.S Take its sign and implicitly display it

```

Try it online!

Output is:

```
-1 if strictly decreasing sequence
 0 if non-strictly decreasing sequence
 1 otherwise

```

# Answer
> 3 votes
# Ruby, 37 bytes

```
->l{[d=l==l.sort.reverse,d&&l|[]==l]}

```

Output:`[true,true]`, `[true,false]` or `[false,false]`

# Answer
> 3 votes
# Haskell, 34 bytes

```
maximum.(zipWith compare<*>(1/0:))

```

Try it online!

Outputs `LT`,`EQ`,`GT` for strictly monotonic, non-increasing, and otherwise, respectively. Thanks to @xnor for pointing out that my previous version failed on singleton lists and suggesting this alternative.

Takes the maximum of the sighn of the differences between adjacent pairs, prepending with `inf`. (`zipWith compare<*>(1/0:)` applied to `l` computes `compare l inf:l` elementwise).

This is competitive with the existing Haskell answers and ekes out ahead by being pointfree and anonymous.

# Answer
> 2 votes
# Racket, 44 bytes

```
(λ(x)(map(λ(p)(apply p`(,@x 0)))`(,>,>=)))

```

Invoked:

```
(map (λ(x)(map(λ(p)(apply p`(,@x 0)))`(,>,>=)))
 '((7 5 4 3 1)
   (42 41)
   (5)
   (27 19 19 10 3)
   (6 4 2 2 2)
   (9 9 9 9)
   (1 2 3 2)
   (10 9 8 7 12)
   (4 6 4 4 2)))

```

Result:

```
'((#t #t)
 (#t #t)
 (#t #t)
 (#f #t)
 (#f #t)
 (#f #t)
 (#f #f)
 (#f #f)
 (#f #f))

```

# Answer
> 2 votes
## Mathematica, ~~15~~ 11 bytes

```
##>0|##>=0&

```

This is a variadic function, taking all input integers as separate arguments.

* Strictly decreasing: `True | True`
* Non-increasing: `False | True`
* Neither: `False | False`

Note that `|` is not `Or` but `Alternatives`, which is part of pattern matching syntax, which explains why these expressions don't get evaluated to `True`, `True`, `False`, respectively.

The code itself is mostly an application of this tip. For example `##>0` is `Greater[##, 0]` but then `##` expands to all the input values so we get something like `Greater[5, 3, 2, 0]`, which itself means `5>3>2>0`.

# Answer
> 2 votes
# Python 3, 81 52 bytes (Thanks to FryAmTheEggMan)

```
e=sorted
lambda a:(a==e(a)[::-1])+(e({*a})[::-1]==a)

```

Try it online !

# Answer
> 2 votes
# C++14, 85 bytes

```
int f(int x){return 3;}int f(int x,int y,auto...p){return((x>=y)+2*(x>y))&f(y,p...);}

```

Returns 3 (0b11) for strict decreasing, 1 (0b01) for non-increasing and 0 otherwise.

Ungolfed:

```
int f(int x) {return 3;}
int f(int x,int y,auto...p){
  return ((x>=y)+2*(x>y)) & f(y,p...);
}

```

I thought this was a perfect problem for C++17's folding expressions:

```
int g(auto...x){return(x>...)+(x>=...);}

```

Unfortunately it does not chain the relational operators but does

```
((x1>x2)>x3)>x4)...

```

which is not was wanted.

# Answer
> 2 votes
# Python 2, ~~61~~ 74 bytes

+13 bytes for the single number input

```
x=map(str,input())
print[2,eval(">".join(x))+eval(">=".join(x))][len(x)>1]

```

Requires input in bracket list form like `[3,2,1]`. Returns 2 for strict decreasing, 1 for non-increasing and 0 otherwise.

Old solution:

```
print eval(">".join(x))+eval(">=".join(x))

```

# Answer
> 2 votes
# Befunge, 50 bytes

```
&: >~1+#^_v>:0`|
1\:^  @.$$<-@.2_
-: ^    >& ^   >

```

Try it online!

Accepts input as a sequence of int separated by spaces, and returns 0 if strictly decreasing, 1 if non-strictly decreasing, 2 otherwise.

Since reading befunge is kind of impossible if you don't know the language, this is the algorithm in pseudocode:

```
push(input())

while( getchar()!=EOF ){
  push(input())
  subtract()
  duplicate()
  if(pop()>0){
    subtract() //we are doing a-(a-b), so b is now on top
    duplicate()
  }
  else{
    if(pop()==0){
      push(1) //the sequence is not strictly decreasing
      swap()
      duplicate()
    }
    else{
      push(2) //the sequence has just increased
      output(pop)
      return
    }
  }
}
pop()
pop()
output(pop())

```

\*in befunge memory is a stack which starts with an infinite amount of 0 on it. pop(), push(x), input() and output(x) are self-explainatory, the other pseudofunctions i used work like this:

```
function duplicate(){
  a=pop()
  push(a)
  push(a)
}

function subtract(){
  a=pop()
  b=pop()
  push(b-a)
}

function swap(){
  a=pop()
  b=pop()
  push(a)
  push(b)
}

```

Funge!

---

Previous version, just 41 bytes but invalid since it requires a 0 to terminate the input sequence (or using an interpreter like this)

```
&:  >&:|>:0`|
1\v@.$_<-@.2_
- >:v  >^   >

```

Try it online!

# Answer
> 2 votes
## Haskell, 36 bytes

```
f l=[scanl1(min.(+x))l==l|x<-[0,-1]]

```

`(+x)` is because haskell mis-interprets `(-x)` as a value instead of a section. I wonder if the whole expression can be profitably made pointfree.

# Answer
> 2 votes
# J, 14 bytes

Monadic verb taking the list on the right, returning `1` for strictly decreasing, `0` for weakly decreasing, and `_1` otherwise.

```
*@([:<./2-/\])

```

Takes the sign `*` of the minimum `<./` of consecutive differences `2-/\` of the list. J doesn't swap the order of the differences when taking them so e.g. the sequence is strictly decreasing if these are all positive. Notably, `<./` returns positive infinity on zero-element lists.

In use at the REPL:

```
   *@([:<./2-/\]) 3
1
   *@([:<./2-/\]) 3 2
1
   *@([:<./2-/\]) 3 2 2
0
   *@([:<./2-/\]) 3 2 2 3
_1

```

# Answer
> 2 votes
# C, ~~68~~ 67 Bytes

A function `f`, which is passed an array of ints (`l`) preceded by its length (`n`, also an int). Returns 3 if monotone strictly decreasing, 1 if monotone non-increasing, but not strictly decreasing, 0 otherwise.

```
f(int n,int*l){return n<2?3:((l[0]>l[1])*2|l[0]>=l[1])&f(n-1,l+1);}

```

Un-golfed slightly for readability:

```
int f_semiungolfed(int n, int* l) {
    return (n < 2) ? 3 : ((l[0] > l[1]) * 2 | l[0] >= l[1]) & f(n - 1, l + 1);
}

```

Rearranged and commented to show logic:

```
int f_ungolfed(int n, int* l) {
    int case1 = 0, case2 = 0, recursion = 0;
    if (n < 2) { // Analogous to the ternary conditional I used - n < 2 means we have a single-element/empty list
        return 3; // Handles the vacuous-truth scenario for single lists
    } else {
        case1 = l[0] > l[1]; // The first case - are the two numbers in the list strictly decreasing? (case1 is 1 if so)
        case2 = l[0] >= l[1]; // The second case - are the two numbers strictly non-increasing (case2 is 1 if so)
        recursion = f_ungolfed(n - 1, l + 1); // Recursively call ourselves on the "rest" of the list (that is, everything other than the first element). Consider that comparison is transitive, and that we already have a vacuous-truth scenario covered.
        case1 *= 2; // Shift case1's value over to the left by one bit by multiplying by 2. If case1 was 1 (0b01), it's now 2 (0b10) - otherwise it's still 0 (0b00)
        return (case1 | case2) & recursion;
        // The bitwise OR operator (|) will combine any 1-bits from case1's value (either 0b10 or 0b00) or case2's value (either 0b01 or 0b00) into either 3, 2, 1, or 0 (0b11, 0b10, 0b01, or 0b00 respectively).
        // The bitwise AND operator (&) will combine only matching 1-bits from (case1|case2) and the return value of the recursive call - if recursion = 0b11 and case1|case2 = 0b01, then the return value will be 0b01.
    }
}

```

Test cases (courtesy IDEOne):

```
{7, 5, 4, 3, 1}: 3
{42, 41}: 3
{5}: 3
{27, 19, 19, 10, 3}: 1
{6, 4, 2, 2, 2}: 1
{9, 9, 9, 9}: 1
{1, 2, 3, 2}: 0
{10, 9, 8, 7, 12}: 0
{4, 6, 4, 4, 2}: 0

```

# Answer
> 2 votes
## Retina, 41 bytes

```
\d+
$*
A`\b(1+) 1\1
S`\b$
\b(1+) \1\b.*|$

```

Try it online! (The first line enables a linefeed-separated test suite.)

* Strictly decreasing: `2`
* Non-increasing: `3`
* Neither: `1`

### Explanation

```
\d+
$*

```

Converts the input unary.

```
A`\b(1+) 1\1

```

The regex here matches an increasing pair of consecutive numbers. If this is the case, the input can clearly not be non-increasing. The `A` denotes it as an "anti-grep" stage which means that the input line is discarded and replaced with the empty string if the regex matches.

```
S`\b$

```

This is a split stage which is used to append a linefeed to the input *only* if the input wasn't discarded. So we've got two possible outcomes so far: non-increasing inputs get a linefeed at the end and others are still empty.

```
\b(1+) \1\b.*|$

```

Finally, we count the number of matches of this regex. The regex either matches to identical numbers (and then everything to the end of the string to avoid multiple matches of this kind for inputs like `1 1 1 1`), or the "end of the input". Let's go through the three types of inputs:

* Strictly decreasing: the first part of the regex can't match because all values are unique, but the `$` matches. Now `$` isn't *exactly* "the end of the string". It can also match in front of a trailing linefeed. So we'll actually get two matches from it, one at the end of the input, and one after the linefeed we inserted.
* Non-increasing: now the first part of the regex also provides a match, and we end up with three matches.
* Neither: remember that we took care to turn the input into an empty string, so now `$` matches only once.

# Answer
> 2 votes
# Vim, 69 bytes

```
V}JYu:sor!n
V}JP:%s/^\(.*\)\n\1/m\r\1
:%s/\vm\n.*<(.+) \1.*/n
:g/\d/d

```

Try it online!

This is vanilla vim (TIO supports V (vim), which is backwards compatible). Takes input as a list of integers, one per line. Outputs `m` for strictly monotonic, `n` for non-increasing, and empty string otherwise.

```
V}              " select everything
  J             " space-join it all into one line
   Y            " yank that
    u           " undo back to one per line
     :sor!n     " reverse sort (the whole file, by line) numerically
V}J             " space join again
   P            " paste the previously yanked original list
                " now we have the list on line 1 and a sorted copy on line 2

```

Next we have two regexes.

```
:%s/^\(.*\)\n\1/m\r\1

```

Matches two copies of the same line and replaces the first with "m".

```
:%s/\vm\n.*<(\d+) \1.*/n

```

Matches that "m" followed by a line containing `<(.+) \1`, i.e. a word boundary followed by `<foo> <foo>`, and if found replaces everything with `n`. The `\v` at the start says "all characters are special" so we don't have to escape any of `<()+`.

There's a bit of careful cleverness here: we don't need a word boundary after the `\1` because the first number can't be a prefix of the second in a reverse sorted list. Furthermore, even though `(.+)` can match several numbers (as opposed to `(\d+)` which would match only one for an extra byte), this won't result in any false positives for the same reason: we can't have a repeated string of multiple numbers in a reverse sorted list unless they're all the same, in which case we want to match them anyway.

The state after all this is one of:

```
monotonic     non-increasing      other
---------     --------------      -----
m             n                   3 1 2
3 2 1                             3 2 1

```

So, to collapse these states, we just delete any line which still has a digit: `:g/\d/d`, resulting in the desired output.

I do wonder whether the regexes can be golfed some (maybe avoiding some cross-line stuff?) but the corner cases can be a bit tricky.

# Answer
> 1 votes
# Axiom, 114 bytes

```
m(c:List(INT)):INT==(i:=r:=1;repeat(~index?(i+1,c)=>break;c.i<c.(i+1)=>return 0;if c.i=c.(i+1)then r:=2;i:=i+1);r)

```

**Ungolfed**

```
-- if [a,b,..n] decrescente ritorna 1
--          non crescente   ritorna 2
--          altrimenti      ritorna 0
m(c:List(INT)):INT==
   i:=r:=1
   repeat
      ~index?(i+1,c)=>break
      c.i<c.(i+1)   =>return 0
      if c.i=c.(i+1) then r:=2
      i:=i+1
   r

```

**Results**

```
(x) -> m([3,1])=1, m([1,1])=2, m([])=1, m([1])=1, m([1,3])=0
   (x)  [1= 1,2= 2,1= 1,1= 1,0= 0]

```

# Answer
> 1 votes
# APL, 16 bytes

```
(a≡a[⍒a])×1+a≡∪a

```

Note: enter one element array as eg `a←1⍴3` otherwise: `a←4 3 2 1`

Interpreting output:

```
2 Monotone strictly decreasing
1 Monotone non-increasing, but not strictly decreasing
0 None of the above

```

Idea: test for monotonicity by comparing original to sorted array, check for non-increasing by comparing to array with removed duplications.

(And I think it can be improved...)

# Answer
> 1 votes
# LabVIEW, 12 nodes, 18 wires ==\> 48 bytes by convention

No functions hidden in the other case frames, just a single wire across.

# Answer
> 1 votes
# Ceylon, 86 bytes

```
Object m(Integer+l)=>let(c=l.paired.map(([x,y])=>x<=>y))[if(!smaller in c)equal in c];

```

The function takes the input as its parameters, and returns a tuple of zero or one booleans – `[false]` for *Monotone strictly decreasing*, `[true]` for *Monotone non-increasing, but not strictly decreasing*, and `[]` for *None of the above*.

It can be used like this:

```
shared void run() {
    print("Monotone strictly decreasing:");
    print(m(7, 5, 4, 3, 1));
    print(m(42, 41));
    print(m(5));

    print("Monotone non-increasing, but not strictly decreasing:");
    print(m(27, 19, 19, 10, 3));
    print(m(6, 4, 2, 2, 2));
    print(m(9, 9, 9, 9));

    print("None of the above:");
    print(m(1, 2, 3, 2));
    print(m(10, 9, 8, 7, 12));
    print(m(4, 6, 4, 4, 2));
}

```

Output:

```
Monotone strictly decreasing:
[false]
[false]
[false]
Monotone non-increasing, but not strictly decreasing:
[true]
[true]
[true]
None of the above:
[]
[]
[]

```

An ungolfed and commented version:

```
// Let's decrease the monotony!
//
// Question:  http://codegolf.stackexchange.com/q/101036/2338
// My Answer: http://codegolf.stackexchange.com/a/101309/2338

// Define a function which takes a non-empty list `l` of Integers)
// (which arrive as a tuple) and returns an Object (actually
// a `[Boolean*]`, but that is longer.)
Object m(Integer+ l) =>
        // the let-clause declares a variable c, which is created by taking
        // pairs of consecutive elements in the input, and then comparing
        // them. This results in lists like those (for the example inputs):
        // { larger, larger, larger, larger }
        // { larger }
        // {}
        // { larger, equal, larger, larger }
        // { larger, larger, equal, equal }
        // { equal, equal, equal }
        // { smaller, smaller, larger }
        // { larger, larger, larger, smaller }
        // { smaller, larger, equal, larger }
        let (c = l.paired.map( ([x,y]) => x<=>y) )
            // now we analyze c ...
            // If it contains `smaller`, we have an non-decreasing sequence.
            // We return `[]` in this case (an empty tuple).
            // Otherwise we check whether `equal` is in the list, returning
            // `[true]` (a non-strictly decreasing sequence) if so,
            // and `[false]` (a strictly decreasing sequence) otherwise.
            [if(!smaller in c) equal in c];

```

# Answer
> 1 votes
# Actually, ~~9~~ 8 bytes

This answer is based on Jonathan Allan's excellent Jelly answer, and returns -1 for a strictly decreasing array, 0 for a non-increasing array, and 1 for none of the above. Golfing suggestions welcome! Try it online!

```
;\♀-dXMs

```

**Ungolfing**

```
     Implicit input a.
;\   Duplicate a and rotate that duplicate left by 1.
♀-   Vectorized subtract the two duplicates.
dX   Discard the last element, leaving only the first differences of a.
M    Get the maximum first difference.
s    Push the sign of the maximum first difference, returning -1, 0, or 1 as described above.
     Implicit return.

```

# Answer
> 1 votes
**Clojure, 34 bytes**

```
#(if(apply > %)1(if(apply >= %)2))

```

Very straight-forward, returns `1` for if strictly decreasing, `2` if non-increasin and `nil` otherwise.

Also tried avoiding `apply` with macro's `~@` but it is just longer at 43 chars (this results in `[1 2 nil]`):

```
(defmacro f[& i]`(if(> ~@i)1(if(>= ~@i)2)))

[(f 7 5 4 3 1)
 (f 27 19 19 10 3)
 (f 1 2 3 2)]

```

# Answer
> 1 votes
# Pip, 8 bytes

```
O$>g$>=g

```

Full program. Takes the input list as command-line arguments. Outputs `11` for strictly decreasing, `01` for non-increasing, `00` for neither.

Try it online!

### Explanation

This approach works because Pip's comparison operators, like Python's, chain together: `4>3>2` is true, rather than being `(4>3)>2` (false) as in C. And the same behavior holds when the comparison operators are modified with the `$` fold meta-operator.

```
          g is list of command-line args (implicit)
 $>g      Fold g on >
O         Output without newline
    $>=g  Fold g on >=
          Print (implicit)

```

# Answer
> 1 votes
# Japt, ~~9~~ ~~8~~ 7 bytes

Outputs `-1` for "monotone strictly decreasing", `0` for "monotone non-incresing" and `1` otherwise.

```
än rw g

```

Try it

1 byte saved thank to Oliver.

# Answer
> 1 votes
# , 34 bytes

```
function(x)max(sign(diff(c(x,0))))

```

Try it online!

Ports DJ's MATL answer.

# , 43 bytes

```
function(x)all(diff(x)<0)+all(x==cummin(x))

```

Try it online!

Returns `2` for strictly decreasing, `1` for non-increasing, and `0` otherwise.

`all(x==cummin(x))` is `TRUE` (converts to `1` when used in arithmetic) if and only if `f` is non-increasing, including the strict case.

`all(diff(x)<0)` is `TRUE` only when `f` is strictly decreasing.

# Answer
> 1 votes
# Pyth, 8 bytes

```
._eS.+aZ

```

Try it online!

Literal translation of James's MATL answer.

# Answer
> 1 votes
# Thunno 2 `G`, 5 bytes

```
0aṢ€ʂ

```

Try it online!

Port of DJMcMayhem's MATL answer. Gives `-1` for strictly deceasing, `0` for non-increasing, and `1` for none of the above.

#### Explanation

```
0aṢ€ʂ  # Implicit input
0a     # Append a 0
  Ṣ    # Deltas of the list
   €ʂ  # Sign of each
       # Take the maximum
       # Implicit output

```

# Answer
> 0 votes
# Python 3, 113 bytes

```
def f(L):
 z=0
 for i in range(0,len(L)-1):
  if L[i]-L[i+1]<0:
   return 2
  if L[i]-L[i+1]==0:
   z=1
 return z

```

Try it online!

Could be shorter if there were a sign function. This outputs 0 for strictly decreasing, 1 for weakly decreasing and 2 for none of the above.

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


title: The cat ate your input again!

text:
# Question
Title: The cat ate your input again!
Create a cat program, a.k.a a program that takes an input and prints it.

...Except, the program will randomly take characters away from your input and print that instead.

Each character in the input should have generally equal odds to be removed with the program, though, as it is hard to make that, the odds for each character can vary by 10% at most.

Your program should take the input, then randomly remove characters from the input, then print that version again. (You can print with trailing newlines or other characters in case your language has to print newlines.)

If the input was `BOOOWL`, it shouldn't remove all Os with an equal chance: each character (not unique) should be considered, so instead of every O combined having a 1/5 chance (for example), each O should have a 1/5 chance, so, instead of there being a 1/5 chance of `BWL`, there should be a 1/5 chance of `BOWL`, `BOOWL`.

Input is restricted to STDIN or closest equivalent.

Each character *must* have a minimum of 10% and a maximum of 30% chance to be removed.

Each character's odds should be calculated individually.

You can use any component of your language supporting random actions, be it functions or something other.

Output must be through STDOUT or the closest equivalent. If your language does have STDOUT, do not output in any other way. If your language cannot output strings as text, use closest equivalent (C's character array output's OK here).

This is code golf. Shortest program wins.

# Answer
# Japt `-f`, 2 bytes

The `-f` flag "runs the program on each element in the first input, outputting an array of those that return a truthy value."  returns a random number between 0(inclusive) and 5(exclusive). Like JavaScript, 0 is falsy in Japt.

Try it
> 10 votes

# Answer
# Python 3, 63 bytes

```
from random import*
for c in input():print(end=c[random()<.2:])

```

Try it online!

# Python 2, ~~67~~ 65 bytes

```
from random import*
print''.join(c for c in input()if.8>random())

```

Try it online!

Each character has a 20% chance of beeing dropped.

Different approach, same length:

```
from random import*
print''.join(c[random()<.2:]for c in input())

```

Try it online!
> 9 votes

# Answer
# Charcoal, 4 bytes

```
ΦＳ‽⁵

```

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

```
 Ｓ      Input a string
Φ       Filter where nonzero
  ‽⁵    Random number 0..4
        Implicitly print

```

You can use any number from `4` to `10` to get chances of `25%` to `10%` respectively.
> 8 votes

# Answer
# Befunge-98 (PyFunge), 11 bytes

```
>#@~3j4???,

```

Try it online!

Each character has a 25% chance of being removed. This decision is made at the three `?` instructions.

`?` sets the program counter to one of the four directions, with equal probability. In this case, up & down wrap back around to the same instruction, so we can ignore those as options.

There are two ways out of the forest of `?`s: to the right (output) and to the left (no output). This situation is symmetric, so if starting from the middle `?`, there is a \\$p\_2 = 1/2\\$ chance of outputting. The chance of outputting if starting from the right `?` is \\$p\_3 = 1/2 * 1 + 1/2 * p\_2 = 3/4\\$. Therefore, after reading a character, we jump to the rightmost `?` to determine whether or not to output.
> 7 votes

# Answer
# Octave, 23 bytes

Generates an array of the same size as the input (strings in Octave are character arrays), checks each of the random numbers whether it is greater than `0.2` and then uses logical indexing to extract the characters at the corresponding positions.

```
@(s)s(rand(size(s))>.2)

```

Try it online!
> 5 votes

# Answer
# Pyth, ~~8~~ 5 bytes

```
sfO4Q

```

Try it online!

```
sfO4Q   Implicit: Q=eval(input())
 f  Q   Filter characters of Q where the following is truthy:
  O4      Random number in the range [0-4)
          Any non-zero value is truthy, so this will drop characters 25% of the time
s       Concatenate into string, implicit print

```

---

Previous version, 8 bytes:

```
s*Vm!!O4

```

Try it online!

```
s*Vm!!O4QQ   Implicit: Q=eval(input())
             Trailing QQ inferred
   m    Q    Map each character in Q using:
      O4       Choose random integer in [0-4)
    !!         Logical NOT twice - maps 0 to 0, anything else to 1
             The result is a list of 0s and 1s, with 0 having 25% chance to appear
 *V      Q   Vectorised multiplication of the above with Q
s            Concatenate into string, implicit print

```
> 5 votes

# Answer
# Jelly, ~~9~~ 5 bytes

```
5X’µƇ

```

Try it online!

A monad which takes a Jelly string as its argument and returns the processed Jelly string. When used as a full program implicitly prints the output. Each character has a 20% chance of being removed.

## Explanation

```
   µƇ | Filter using the following as a monad for each character:
5X    | - Random number between 1 and 5
  ’   | - Decreased by 1

```
> 5 votes

# Answer
# Japt, 3 bytes

Each character has a 1 in 5 chance of being removed. The `5` can be changed to anything between `4` & `9`, inclusive, or `A` for `10` to change the odds.

```
Æ5ö

```

Try it

```
Æ5ö     :Implicit input of string
Æ       :Filter by
 5ö     :  Random integer in the range [0,5), with 0 being falsey

```
> 5 votes

# Answer
# Wolfram Language (Mathematica), 24 bytes

```
Select[RandomReal[]>.2&]

```

Try it online!

Takes a list of characters as input. Each character has a `.2` chance to be removed.
> 5 votes

# Answer
# 05AB1E, ~~5~~ 4 bytes

```
ʒ₄Ω≠

```

-1 byte thanks to *@Grimy*.

Try it online or run the same program 10 times.

Each character has a 25% change of being dropped.

**Explanation:**

```
ʒ     # Filter the characters of the (implicit) input-string by:
 ₄    #  Push 1000
  Ω   #  Pop and push a random digit from it
   ≠  #  And check that it's NOT 1 (!=1)
      # (after which the result is output implicitly)

```

could also be `_` (`==0`).
> 5 votes

# Answer
# MATL, 9 bytes

```
t&n&r.2>)

```

Exaplanation:

```
t         implicitly take input and duplicate it
 &n       compute the size of the input and...
   &r     generate a random array of that size
     .2>  check which entries of that array are greater than 0.2
        ) and use the result using logical indices to extract certain characters of the input

```

Try it online!
> 4 votes

# Answer
# Cubix, 20 bytes

```
u$w\A|UDw@?;...>o._U

```

Try it online!

Longer than I had hoped as I had a number of no-ops that I can't seem to get rid of. The chance to drop a character is 25%. I assume this is okay.

```
    u $
    w \
A | U D w @ ? ;
. . . > o . _ U
    . .
    . .

```

Watch it run

Brief explanation:

* `A|A` this initialises the the stack, Input all, reflect back, Input all (just an EOI -1)
* `;?` pop to of stack, test for EOI (-1).
* `_?@` if negative, reflect back into test and end on halt
* `$D` jump the `\` into the random direction setter.
    + from the direction setter, 3 direction lead to the `o` for output then back into the loop, one misses the `o` in it's path and goes straight to the loop.
> 4 votes

# Answer
# APL (dzaima/APL), ~~10~~ 9 bytesSBCS

Anonymous tacit prefix function. Each character has exactly 20% chance of being removed.

```
⊢⌿⍨4≥∘?5¨

```

Try it online!

zero for each character

`?` random integer range 1–5 for each character

`4≥` Boolean mask for those integers that are less than or equal to 4

`⊢⌿⍨` filter the argument using that mask
> 3 votes

# Answer
# Retina, 15 bytes

```
/./_?(`.

```

Try it online! Explanation:

```
/./_

```

Process each character individually.

```
?(`

```

Perform a substitution at random. The first substitution deletes the character, while the other three leave it unchanged, thus giving a `25%` chance of deleting the character. This can be decreased as necessary by appending additional pairs of newlines.
> 3 votes

# Answer
# , ~~32~~ 23 bytes

```
function(x)x[rt(x,3)<1]

```

Try it online!

A function taking a character vector as input and returning a processed character vector. Each character has a 20% chance of being removed.

Thanks to @Roland and @Giueseppe for helping save 7 bytes, and @JDL for a further 2!
> 3 votes

# Answer
# T-SQL 2012, 83 bytes

Looping through the input from right to left removing 0 or 1 character.

25% chance for each character getting removed.

```
DECLARE @i varchar(max)='The cat ate my homework'

DECLARE @ int=len(@i)WHILE @>0SELECT
@i=stuff(@i,@,str(rand()*2)/2,''),@-=1PRINT @i

```

Explanation:

> `rand()*2` returns a float, which can't be used in the `stuff` command.
>
> The `str` converts this into a varchar after rounding to nearest whole number. The float is being converted to a varchar(which isn't allowed as third parameter in `stuff` either).
>
> This varchar has a 25% chance of being '2', 50% chance of being '1', 25% chance of being '0'. Dividing by 2, there is a 25% chance of result being 1. This division converts the varchar to an integer.
>
> Integer is the expected third parameter in `stuff` function.

**Try it online**
> 3 votes

# Answer
# PHP, ~~43~~ 42 bytes

```
for(;''<$l=$argn[$i++];rand()%5&&print$l);

```

Try it online!

Each character has 20% of chance to be removed.
> 2 votes

# Answer
# , 10 bytes

```
#~5>6?@$~#

```

Try it online!

Similar to Adam's APL answer, though I actually wrote it before looking at his.

* `6.. $~ #` Take the length of input `#` and shape `$~` the number 6 into a list that long.
* `?@` Treat each six in that list as a die and roll `?` it.
* `>5` Is the die less than 5 (possible values are 0..5)? Use that boolean result to create a bit mask.
* `#~` Filter the input with that mask.
> 2 votes

# Answer
# C# (Visual C# Interactive Compiler), 71 bytes

```
var y=new Random();foreach(var k in ReadLine())if(y.Next(5)<4)Write(k);

```

Try it online!
> 2 votes

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

```
s/./.2<rand&&$&/ge

```

Try it online!

Each character has a 20% chance of being dropped.
> 2 votes

# Answer
# Javascript,  ~~46~~   ~~44~~  51 bytes

```
i=>alert([...i].filter(c=>Math.random()>.2).join``)

```

+7 bytes because of the added STDOUT requirement

-2 bytes thank to Birjolaxew

---

original answer: 44 bytes without the STDOUT requirement

```
i=>[...i].filter(c=>Math.random()>.2).join``

```
> 2 votes

# Answer
# Scala, ~~51~~ ~~46~~ 30 bytes

```
s=>s.flatMap(x=>if(math.random>.2)Some(x)else None)

```

Try it online!

PS. Like in many other solutions, the probability of dropping char is 20%.

# Update:

-5 bytes by using String instead of Option\[String\] in flatMap

```
s=>s.flatMap(x=>if(math.random>.2)x+""else "")

```

30 bytes by using filter

```
s=>s.filter(x=>math.random>.2)

```
> 2 votes

# Answer
# C (gcc), 50 bytes

This program has a 20% chance of dropping a letter. Unfortunately the random number generator isn't seeded so you get the same sequence on each run. Basically the only trick is inverting the input character to halt the loop on EOF.

```
main(c){for(;c=~getchar();rand()%5&&putchar(~c));}

```

Try it online!

## C (gcc), 64 59 bytes

Thanks to ceilingcat for the -5 bytes.

If you want the RNG seeded on each run.

```
main(c){for(srand(&c);c=~getchar();rand()%5&&putchar(~c));}

```

Try it online!
> 1 votes

# Answer
# Zsh, ~~53~~ ~~41~~ 40 bytes

Try it Online!

```
for c (${(s::)1})((RANDOM%4))&&printf $c

```

Converts the input to an array of characters, then tries to print each element `c`, unless it's eaten by the `((RANDOM%4))` evaluating to false!

*~~53 bytes~~, Original* *
~~41 bytes~~, thanks to @GammaFunction*
> 1 votes

# Answer
# Lua, ~~69~~ 68 bytes

```
for c in io.lines(nil,1)do io.write(math.random()>.2 and c or '')end

```

Try it online!

Kinda straightforward, but seems to be shortest version: iterate over stdin char by char (with `io.lines`… that name is misleading), then based on random value either print one or empty string (e.g. nothing).
> 1 votes

# Answer
# Java

Non-terminating: 82 bytes

```
v->{for(int i;;i=System.in.read(),System.out.print(Math.random()<.2?"":(char)i));}

```

Terminating (TIO): 105 bytes

```
v->{var n=System.in;for(int i;n.available()>0;i=n.read(),System.out.print(Math.random()<.2?"":(char)i));}

```
> 1 votes

# Answer
# Zsh, 50 bytes

```
for c (${(s::)"$(<&0)"})
((RANDOM%5))&&echo -nE $c

```

Try it online!

Similar to RobLogic's answer, but following the input requirements more closely, and works for inputs with backslashes.

`"$(<&0)"` instead of `"<&0"` or `$(<&0)` because the first doesn't work in substitutions, and the second eats newlines. The `-nE` flags are necessary to prevent backslashes from being parsed as escape sequences, and to prevent newlines being inserted.

`echo -nE`
> 1 votes

# Answer
# MathGolf, 5 bytes

```
æƒ√∞*

```

Try it online!

## Explanation

```
æ       foreach character...
 ƒ      random float in range [0,1)
  √     take square root (making P(x < 0.5) = 0.25)
   ∞    pop a, push 2*a
    *   repeat character int(x) times

```

Each character will be repeated 0 or 1 times, depending on the random value. Since the expected value after the square root is shifted, there is a 25% probability that each character is removed.

### Alternative 5-byter

```
gÉ;4w

```

Filter the characters by a random number in \[0, 4\]. Due to how filtering works, I have to discard the actual character within the filter loop, which adds 1 byte.
> 1 votes

# Answer
# GFortran, 120 bytes

Not too bad, if we use the deprecated `RAN()` function, which is **pseudo**-random, i.e. you get the same sequence each time. The proper way to generate random numbers in GFortran is with `CALL RANDOM_SEED()` and `CALL RANDOM_NUMBER(R)` but that's a lot of bytes!

```
character(99)S;read(*,'(A)')S;do i=1,len_trim(S)
if(ran(0)*5.gt.1)then;write(*,'(A)',advance="no")S(i:i)
endif;enddo;end

```

Try it online!
> 0 votes

# Answer
# Oracle SQL, 133 bytes

```
select listagg(decode(sign(dbms_random.value-0.2),1,substr(x,level,1)))within group(order by level)from t connect by level<=length(x)

```

It works with an assumption that input data is stored in a table t(x), e.g.

```
with t(x) as (select 'The cat ate my homework' from dual)

```
> 0 votes

# Answer
# Gaia, 10 bytes

```
⟨w8&Ø+ṛ⟩¦$

```

Try it online!

Has a 1/9th (11%) chance of removing any given character. This abuses the fact that the meta `¦` treats a string as a list, much as Python does.

```
 ⟨	⟩¦	| for each character do:
  w8&		| wrap as list and duplicate 8 times
     Ø+		| add empty string to that list
       ṛ	| select element at random
	  $	| and join with no separator
		| implicitly print top of stack

```
> 0 votes

# Answer
# Python3, 61 bytes

Does this count? I guess if you consider execution across seconds of time "random"

```
import time
for c in input():print(end=c[time.time()%5<1:])

```
> 0 votes

# Answer
# Pepe, 61 bytes

```
REEerEERREeeeeEeEeREEeEerEEEEErrEEReReEeRRERRErEereereReReree

```

Try it online!

There is **11.11%** or \\$\frac{1}9\\$ chance of characters being deleted.

**Explanation:**

`... # some-command -> (stack) // some-explanation`

```
REEe # Input (str) -> (R)
rEE # Create label 0 -> (r) // main loop begins
  RREeeeeEeEe # Push 10 -> (R) // this is for the randomiser
              # R flag: place it in the beginning
  REEeEe # Random number from 1 to 10 -> (R)
  rEEEEE # Increment -> (r) // 0 > 1, for the next command
  rrEE # Create label 1 -> (r) // without previous command, the existing label 0 is replaced
       # r flag: Skip until rEe (return)
    Re # Pop -> (R) // removes the random number
    ReEe # Output as char & pop it -> (R)
    RRERRE # Push 0 2 times -> (R) // these are popped to fix the pos of R stack
  rEe # Return to where goto was called
  ree # Goto 1 if 1 != random from 1 to 10 // The whole rrEE ... rEe ree is an if..then
  re # Pop -> (r)
  ReRe # Pop 2 times -> (R)
ree # Loop while char of (R) != 0

```
> 0 votes

# Answer
# Ruby `-p`, 27 bytes

The `-p` flag takes each line of input as the global variable `$_` and runs it through the code block and then prints its contents. `gsub` modifies `$_` by replacing characters that match the given regex (only works if `-p` or `-n` is present).

```
gsub(/.|\n/){$&if rand>0.2}

```

Try it online!
> 0 votes

# Answer
# Vyxal `s`, 4 bytes

```
'₀ʁ℅

```

Try it Online!

Each char has 10% chance to be removed.

```
'    # Filter by...
   ℅ # Random choice from
 ₀ʁ  # 0...10

```
> 0 votes

# Answer
# Thunno 2, 4 bytes

```
æ5Lɼ

```

Try it online!

#### Explanation

```
æ5Lɼ  # Implicit input
æ     # Filter it by:
   ɼ  #  Random number from
 5L   #  [0, 1, 2, 3, 4]
      #  (×, ✓, ✓, ✓, ✓)
      # Implicit output

```
> 0 votes

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


title: What base is this number in?

text:
# Question
Title: What base is this number in?
Here's a nice easy challenge:

> Given a string that represents a number in an unknown base, determine the lowest possible base that number might be in. The string will only contain `0-9, a-z`. If you like, you may choose to take uppercase letters instead of lowercase, but please specify this. You must output this lowest possible base in decimal.

Here is a more concrete example. If the input string was "01234", it is impossible for this number to be in binary, since 2, 3, and 4 are all undefined in binary. Similarly, this number cannot be in base 3, or base 4. Therefore, this number *must* be in base-5, or a higher base, so you should output '5'.

Your code must work for any base between base 1 (unary, all '0's) and base 36 ('0-9' and 'a-z').

You may take input and provide output in any reasonable format. Base-conversion builtins are allowed. As usual, standard loopholes apply, and the shortest answer in bytes is the winner!

# Test IO:

```
#Input          #Output
00000       --> 1
123456      --> 7
ff          --> 16
4815162342  --> 9
42          --> 5
codegolf    --> 25
0123456789abcdefghijklmnopqrstuvwxyz    --> 36

```

# Answer
# Jelly, 4 bytes

```
ṀØBi

```

Requires uppercase. Try it online! or verify all test cases.

### How it works

```
ṀØBi  Main link. Arguments: s (string)

Ṁ     Yield the maximum of s.
 ØB   Yield "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".
   i  Find the 1-based index of the maximum in that string.

```
> 17 votes

# Answer
# Python, ~~27~~ 22 bytes

```
lambda s:(max(s)-8)%39

```

This requires the input to be a bytestring (Python 3) or a bytearray (Python 2 and 3).

*Thanks to @AleksiTorhamo for golfing off 5 bytes!*

Test it on Ideone.

### How it works

We begin by taking the maximum of the string. This the code points of letters are higher than the code points of digits, this maximal character is also the maximal base 36 digit.

The code point of **'0' – '9'** are **48 – 57**, so we must subtract **48** from their code points to compute the corresponding digits, or **47** to compute the lowest possible base. Similarly, the code points of the letters **'a' – 'z'** are **97 – 122**. Since **'a'** represents the digit with value **10**, we must subtract **87** from their code points to compute the corresponding digits, or **86** to compute the lowest possible base. One way to achieve this is as follows.

The difference between **97** and **58** (**':'**, the character after **'9'**) is **39**, so taking the code points modulo **39** can achieve the subtraction. Since **48 % 39 = 9**, and the desired result for the character **'0'** is **1**, we first subtract **8** before taking the result modulo **39**. Subtracting first is necessary since otherwise **'u' % 39 = 117 % 39 = 0**.

```
c    n    n-8    (n-8)%39
0    48    40     1
1    49    41     2
2    50    42     3
3    51    43     4
4    52    44     5
5    53    45     6
6    54    46     7
7    55    47     8
8    56    48     9
9    57    49    10
a    97    89    11
b    98    90    12
c    99    91    13
d   100    92    14
e   101    93    15
f   102    94    16
g   103    95    17
h   104    96    18
i   105    97    19
j   106    98    20
k   107    99    21
l   108   100    22
m   109   101    23
n   110   102    24
o   111   103    25
p   112   104    26
q   113   105    27
r   114   106    28
s   115   107    29
t   116   108    30
u   117   109    31
v   118   110    32
w   119   111    33
x   120   112    34
y   121   113    35
z   122   114    36

```
> 27 votes

# Answer
# Python, 25 bytes

```
lambda x:int(max(x),36)+1

```

Defines a lambda that takes the string `x`. Finds the largest digit in the string (sorted with letters above digits, by python's default), and converts to base 36. Adds 1, because `8` is not in base 8.
> 22 votes

# Answer
## Haskell, 34 bytes

```
f s=length['\t'..maximum s]`mod`39

```

Uses the `mod(ord(c)-8,39)` idea from Dennis.

**41 bytes**

```
g '0'=1
g 'W'=1
g x=1+g(pred x)
g.maximum

```

---

**45 bytes:**

```
(`elemIndex`(['/'..'9']++['a'..'z'])).maximum

```

Outputs like `Just 3`.
> 11 votes

# Answer
# Cheddar, ~~34~~ ~~29~~ 21 bytes

*Saved 8 bytes thanks to Dennis!!!*

```
s->(s.bytes.max-8)%39

```

Uses lowercase letters

Try it online

## Explanation

```
s -> (      // Input is `s`
  s.bytes    // Returns array of char codes
   .max      // Get maximum item in array
) % 39      // Modulus 39

```
> 6 votes

# Answer
# 05AB1E, 6 bytes

```
{¤36ö>

```

Takes letters in upper case.

**Explanation**

```
{       # sort
 ¤      # take last
  36ö   # convert from base 36 to base 10
     >  # increment

```

Try it online
> 6 votes

# Answer
# Julia, 22 bytes

```
!s=(maximum(s)-'')%39

```

There's a BS character (0x08) between the quotes. Try it online!
> 5 votes

# Answer
# Actually, 6 bytes

```
M6²@¿u

```

Try it online!
> 5 votes

# Answer
## JavaScript (ES6), ~~41~~ 37 bytes

```
s=>parseInt([...s].sort().pop(),36)+1

```

Edit: Saved 4 bytes thanks to @edc65.
> 4 votes

# Answer
## Haskell, ~~55~~ 40 bytes

```
f=(\y->mod(y-8)39).Data.Char.ord.maximum

```

Thanks @Dennis for his approach. (take that, @xnor ;))
> 3 votes

# Answer
# Perl 6: 18 bytes

```
{:36(.comb.max)+1}

```

Defines a lambda that takes a single string argument, and returns an integer. It splits the string into characters, finds the "highest" one, converts it to base 36, adds 1.

```
{(.ords.max-8)%39}

```

This one uses the modulo approach from Dennis. Same length.
> 3 votes

# Answer
## Retina, 28 bytes

```
O`.
.\B

{2`
$`
}T01`dl`_o
.

```

Try it online! (The first line enables a linefeed-separated test suite.)

### Explanation

```
O`.

```

This sorts the characters of the input.

```
.\B

```

This removes all characters except the last, so the first two stages find the maximum character.

```
{2`
$`
}T01`dl`_o

```

These are two stages which form a loop. The first one duplicates the first character and the second one "decrements" it (replacing e.g. `x` with `w`, `a` with `9` and `1` with `0`). The latter stage encounters a zero as the first character, it removes it instead. This is a standard technique for generating a range of characters, given the upper end. Hence, this generates all "digits" from `0` to the maximum digit.

```
.

```

Finally, we simply count the number of digits, which gives us the base.
> 2 votes

# Answer
# R, ~~99~~ ~~89~~ 85 bytes

Look ! Less than 100 bytes !
Look ! *10* bytes off !
Look ! *4* bytes off !

```
ifelse((m=max(strsplit(scan(,''),"")[[1]]))%in%(l=letters),match(m,l)+10,strtoi(m)+1)

```

**Ungolfed :**

```
l=letters                  #R's built-in vector of lowercase letters

n=scan(what=characters())  #Takes an input from STDIN and convert it to characters

m=max(strsplit(n,"")[[1]]) #Splits the input and takes to max.
                           #`letters` are considered > to numbers (i.e. a>1)

ifelse(m%in%l,match(m,l)+10,strtoi(m)+1) #If the max is in `letters`,
                                             #outputs the matching position of `m`in `letters` + 10 (because of [0-9]).
                                             #Else, outputs `m` (as a number) + 1.

```

As often, this answer makes use of the `ifelse` function : `ifelse(Condition, WhatToDoIfTrue, WhatToDoElse)`
> 2 votes

# Answer
# Scala, 25 bytes

`print((args(0).max-8)%39)`

Run it like:

`$ scala whatbase.scala 0123456789abcdefghijklmnopqrstuvwxyz`
> 2 votes

# Answer
# Mathematica, ~~34~~ 32 bytes

*saved 2 bytes thanks to Martin Ender*

```
Max@BaseForm[Characters@#,36]+1&

```

Defines a pure function that takes a string as input.

Splits the input into characters, converts them to base 36 numbers, and returns the maximum +1.
> 1 votes

# Answer
# Mathematica, ~~34~~ 32 bytes

*2 bytes saved thanks to Martin Ender*

```
Max@Mod[ToCharacterCode@#-8,39]&

```

I decided the different method deserved a new answer.

method ~~stolen~~ inspired by Dennis' solution
> 1 votes

# Answer
# PHP, ~~51~~ 38 bytes

(From Dennis) ^^

```
<?=(ord(max(str_split($argv[1])))-8)%39;

```

Other proposal without Dennis' trick

```
<?=($a=max(str_split($argv[1])))<a?$a+1:ord($a)-86;

```
* Takes input as argument $argv\[1\];
* Take max character (using ASCII) values
* If it is a number (inferior to \< 'a' ascii value) then output number+1
* Else output ascii value -86 (97 for 'a' in ascii, -11 for 'a' is 11th base-digit)
> 1 votes

# Answer
# Octave, 20 bytes

```
@(a)mod(max(a)-8,39)

```
> 1 votes

# Answer
## Pyke, 6 bytes

```
Seb36h

```

Try it here!

```
Se     -   sorted(input)[-1]
  b36  -  base(^, 36)
     h - ^ + 1

```
> 1 votes

# Answer
# Java 7, ~~67~~ 61 bytes

```
int c(char[]i){int m=0;for(int c:i)m=m>c?m:c;return(m-8)%39;}

```

`(m-8)%39` is thanks to *@Dennis*' amazing answer.

**Ungolfed & test code:**

Try it here.

```
class Main{
  static int c(char[] i){
    int m = 0;
    for(int c : i){
      m = m > c
           ? m
           : c;
    }
    return (m-8) % 39;
  }

  public static void main(String[] a){
    System.out.println(c("00000".toCharArray()));
    System.out.println(c("123456".toCharArray()));
    System.out.println(c("ff".toCharArray()));
    System.out.println(c("4815162342".toCharArray()));
    System.out.println(c("42".toCharArray()));
    System.out.println(c("codegolf".toCharArray()));
    System.out.println(c("0123456789abcdefghijklmnopqrstuvwxyz".toCharArray()));
  }
}

```

**Output:**

```
1
7
16
9
5
25
36

```
> 1 votes

# Answer
## R, ~~62~~ 54 bytes

```
max(match(strsplit(scan(,''),"")[[1]],c(0:9,letters)))

```

Ungolfed:

```
max(
  match( # 2: Finds the respective positions of these characters
    strsplit(scan(,''),"")[[1]], # 1: Breaks the input into characters
                                c(0:9,letters)) # 3: In the vector "0123...yz"
                                                )

```

Update: shaved off 8 bytes due to the redundancy of `na.rm=T` under the assumption of input validity.

A 39% improvement in size compared to Frédéric's answer. Besides that, it runs a wee bit faster: 0.86 seconds for 100000 replications versus 1.09 seconds for the competing answer. So the one of mine is both smaller and more efficient.
> 1 votes

# Answer
## CJam, 10 bytes

*Thanks to Martin Ender for saving me a few bytes!*

Uses Dennis's formula

```
q:e>8-i39%

```

Try it online

## CJam, ~~18~~ 16 btyes

Alternative solution:

```
A,s'{,97>+q:e>#)

```

Try it online

```
A,s'{,97>+       e# Push the string "0123456789abcdefghijklmnopqrstuvwxyz"
          q      e# Get the input
           :e>   e# Find the highest character in the input
              #  e# Find the index of that character in the string
               ) e# Increment

```
> 1 votes

# Answer
## C89, ~~55~~ ~~53~~ ~~52~~ 50 bytes

```
f(s,b)char*s;{return*s?f(s+1,*s>b?*s:b):(b-8)%39;}

```

*`-8%39` shamelessly stolen from Dennis*

### Test

```
test(const char* input)
{
    printf("%36s -> %u\n", input, f((char*)input,0));
}

main()
{
    test("00000");
    test("123456");
    test("ff");
    test("4815162342");
    test("42");
    test("codegolf");
    test("0123456789abcdefghijklmnopqrstuvwxyz");
}

```

### Output

```
                               00000 -> 1
                              123456 -> 7
                                  ff -> 16
                          4815162342 -> 9
                                  42 -> 5
                            codegolf -> 25
0123456789abcdefghijklmnopqrstuvwxyz -> 36

```

*Saved 2 bytes thanks to Toby Speight*

*Saved 2 bytes thanks to Kevin Cruijssen*
> 1 votes

# Answer
# C, 55 bytes

This answer assumes that the input is in ASCII (or identical in the numbers and letters, e.g. ISO-8859 or UTF-8):

```
m;f(char*s){for(m=0;*s;++s)m=m>*s?m:*s;return(m-8)%39;}

```

We simply iterate along the string, remembering the largest value seen, then use the well-known modulo-39 conversion from base-{11..36}.

# Test program

```
int printf(char*,...);
int main(int c,char **v){while(*++v)printf("%s -> ",*v),printf("%d\n",f(*v));}

```

# Test results

```
00000 -> 1
123456 -> 7
ff -> 16
4815162342 -> 9
42 -> 5
codegolf -> 25
0123456789abcdefghijklmnopqrstuvwxyz -> 36

```
> 1 votes

# Answer
## C# REPL, 17 bytes

```
x=>(x.Max()-8)%39

```

Just ported @Dennis's answer to C#.
> 1 votes

# Answer
# Vyxal, 6 bytes

```
kr$Gḟ›

```

Try it Online!
> 1 votes

# Answer
# JavaScript, ~~57~~ ~~50~~ 48 bytes

*7 bytes saved thnks to @kamaroso97* *2 bytes saved thanks to @Neil*

```
n=>Math.max(...[...n].map(a=>parseInt(a,36))+1)

```

Original answer:

```
n=>n.split``.map(a=>parseInt(a,36)).sort((a,b)=>b-a)[0]+1

```
> 0 votes

# Answer
# Dyalog APL, 10 bytes

Prompts for uppercase input.

```
⌈/⍞⍳⍨⎕D,⎕A

```

`⌈/` maximum

characters of input

`⍳⍨` 1-indexed into

`⎕D,` all digits followed by

`⎕A` all characters

TryAPL online!
> 0 votes

# Answer
# Perl, ~~30~~ 27 bytes

Includes +1 for `-p`

Run with the input on STDIN, e.g.

```
base.pl <<< codegolf

```

`base.pl`:

```
#!/usr/bin/perl -p
\@F[unpack"W*"];$_=@F%39-9

```
> 0 votes

# Answer
# BASH 70

```
grep -o .|sort -r|head -c1|od -An -tuC|sed s/$/-86/|bc|sed s/-/39-/|bc

```

Input letters are lowercase.
> 0 votes

# Answer
# R, 59 57 bytes

Thanks to @Andreï-Kostyrka for two bytes.

```
max(which(c(0:9,letters)%in%strsplit(scan(,""),"")[[1]]))

```

`scan(,'')` takes the input and coerces it to a string. Then `strsplit` divides it into its individual characters. `[[1]]` is because that returns a list. `%in%` then checks which of the vector `0,1,2,...,8,9,a,b,c,...,x,y,z` is in the input. which tells us the place in that vector of items in the input -- and `max` finds the biggest place -- which corresponds to the base.
> 0 votes

# Answer
## Powershell, 62 bytes

```
function t($s){(($s[0..$s.Length]|measure -Max).Maximum-8)%39}

```

%39 @Dennis, of course :)
> 0 votes

# Answer
## LiveScript, 32 bytes

```
->1+parseInt (it/'')sort!pop!,36

```

A port of this answer in my favorite language that compile to JavaScript. If `base~number` operator worked with variables I could write `->1+36~(it/'')sort!pop!` (23 bytes), but it conflicts with the function bind operator :/
> 0 votes

# Answer
# PowerShell full program, 56 62 bytes

lowercase letters required.

```
([int]((read-host).ToCharArray()|sort|select -l 1)-8)%39

```
> 0 votes

# Answer
# 05AB1E, 3 bytes

```
Hà>

```

Try it online or validate all test cases.

Explanation:

```
          # implicit input
H         # convert each digit to decimal
 à        # maximum
  >       # add 1
          # implicit output

```
> 0 votes

# Answer
# Thunno 2 `G`, 4 bytes

```
36b⁺

```

Try it online!

Takes input in uppercase.

#### Explanation

```
36b⁺  # Implicit input
36b   # Convert each character from base-36
   ⁺  # Increment each integer
      # Implicit output of maximum

```
> 0 votes

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


title: Theoretically output Graham's number

text:
# Question
Title: Theoretically output Graham's number
Graham's number \\$G\\$ is defined in this way:

\begin{align\*} u(3,n,1) & = 3^n \\ u(3,1,m) & = 3 \\ u(3,n,m) & = u(3,u(3,n-1,m),m-1) \end{align\*}

Then,

\begin{align\*} g\_1 & = u(3,3,4) \\ g\_2 & = u(3,3,g\_1) \\ g\_3 & = u(3,3,g\_2) \\ & \vdots \\ G & = u(3,3,g\_{63}) \end{align\*}

You are given that \\$u(3,3,2)=7625597484987\\$ to check your code.

Your task is to write a program/function that will output the value of \\$G\\$ deterministically, given enough integer size and enough time.

# References

# Leaderboard

```
var QUESTION_ID=83873,OVERRIDE_USER=48934;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+(?:\.\d+)?)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 50 votes
# Binary lambda calculus, 114 bits = 14.25 bytes

Hexdump:

```
00000000: 4457 42b0 2d88 1f9d 740e 5ed0 39ce 80    DWB.-...t.^.9..

```

Binary:

```
010001000101011101000010101100000010110110001000000111111001110101110100000011100101111011010000001110011100111010

```

### Explanation

```
01 00                                           (λx.
│    01 00                                        (λy.
│    │    01 01 01 110                              x
│    │    │  │  └─ 10                               y
│    │    │  └─ 00                                  (λm.
│    │    │       01 01 01 10                         m
│    │    │       │  │  └─ 00                         (λg.
│    │    │       │  │       00                         λn.
│    │    │       │  │         01 01 10                  n
│    │    │       │  │         │  └─ 110                 g
│    │    │       │  │         └─ 00                     (λz.
│    │    │       │  │              10                     z))
│    │    │       │  └─ 00                            (λn.
│    │    │       │       00                            λf.
│    │    │       │         01 111110                    x
│    │    │       │         └─ 01 110                    (n
│    │    │       │            └─ 10                      f))
│    │    │       └─ 1110                             x)
│    │    └─ 10                                     y)
│    └─ 00                                        (λf.
│         00                                        λz.
│           01 110                                   f
│           └─ 01 01 1110                            (x
│              │  └─ 110                              f
│              └─ 10                                  z)))
└─ 00                                           (λf.
     00                                           λz.
       01 110                                      f
       └─ 01 110                                   (f
          └─ 01 110                                 (f
             └─ 10                                   z)))

```

This is (λ*x*. (λ*y*. *x* *y**m*. *m**g*. λ*n*. *n* *g* 1) (λ*n*. λ*f*. *x* (*n* *f*)) *x*) *y*) (λ*f*. λ*z*. *f* (*x* *f* *z*))) 3, where all numbers are represented as Church numerals. Church numerals are the standard lambda calculus representation of natural numbers, and they are well suited to this problem because a Church number is defined by function iteration: *n* *g* is the *n*th iterate of the function *g*.

For example, if *g* is the function λ*n*. λ*f*. 3 (*n* *f*) that multiplies 3 by a Church numeral, then λ*n*. *n* *g* 1 is the function that takes 3 to the power of a Church numeral. Iterating this operation *m* times gives

*m**g*. λ*n*. *n* *g* 1) (λ*n*. λ*f*. 3 (*n* *f*)) *n* = *u*(3, *n*, *m*).

(We use multiplication *u*(–, –, 0) rather than exponentiation *u*(–, –, 1) as the base case, because subtracting 1 from a Church numeral is unpleasant.)

Substitute *n* = 3:

*m**g*. λ*n*. *n* *g* 1) (λ*n*. λ*f*. 3 (*n* *f*)) 3 = *u*(3, 3, *m*).

Iterating that operation 64 times, starting at *m* = 4, gives

64 (λ*m*. *m**g*. λ*n*. *n* *g* 1) (λ*n*. λ*f*. 3 (*n* *f*)) 3) 4 = *G*.

To optimize this expression, substitute 64 = 4^3 = 3 4:

3 4 (λ*m*. *m**g*. λ*n*. *n* *g* 1) (λ*n*. λ*f*. 3 (*n* *f*)) 3) 4 = *G*.

Remember 4 = succ 3 = λ*f*. λ*z*. *f* (3 *f* *z*) as a lambda argument:

*y*. 3 *y**m*. *m**g*. λ*n*. *n* *g* 1) (λ*n*. λ*f*. 3 (*n* *f*)) 3) *y*) (λ*f*. λ*z*. *f* (3 *f* *z*)) = *G*.

Finally, remember 3 = λ*f*. λ*z*. *f* (*f* (*f* *z*)) as a lambda argument:

*x*. (λ*y*. *x* *y**m*. *m**g*. λ*n*. *n* *g* 1) (λ*n*. λ*f*. *x* (*n* *f*)) *x*) *y*) (λ*f*. λ*z*. *f* (*x* *f* *z*))) 3 = *G*.

# Answer
> 41 votes
# Haskell, 41 bytes

```
i=((!!).).iterate
i(($3).i(`i`1)(*3))4 64

```

Explanation:

`(`i`1)f n` = `i f 1 n` computes the `n`th iterate of the function `f` starting at `1`. In particular, `(`i`1)(*3)n` = 3^*n*, and iterating this construction *m* times gives `i(`i`1)(*3)m n` = *u*(3, *n*, *m*). We can rewrite that as `(($n).i(`i`1)(*3))m` = *u*(3, *n*, *m*), and iterate this construction *k* times to get `i(($3).i(`i`1)(*3))4 k` = *g*_*k*.

# Answer
> 17 votes
## Haskell, 43 bytes

```
q=((!!).).iterate
g=q(`q`1)(3*)
q(`g`3)4$64

```

There has be a better way to flip `g` inline.

**46 bytes:**

```
i=iterate
n%0=3*n
n%m=i(%(m-1))1!!n
i(3%)4!!64

```

---

**48 bytes:**

```
n%1=3^n
1%m=3
n%m=(n-1)%m%(m-1)
iterate(3%)4!!64

```

Just writing down the definitions.

The base cases are a bit cleaner backed up to 0, though it saves no bytes. Perhaps it will make it easier to write an alternate definition.

```
n%0=3*n
0%m=1
n%m=(n-1)%m%(m-1)
z=iterate(3%)2!!1

```

# Answer
> 10 votes
# Pyth, 25 bytes

```
M?H.UgbtH*G]3^3Gug3tG64 4

```

The first part `M?H.UgbtH*G]3^3G` defines a method `g(G,H) = u(3,G,H+1)`.

To test the first part, check that `7625597484987=u(3,3,2)=g(3,1)`: `g3 1`.

The second part `ug3tG64 4` starts from `r0 = 4` and then compute `rn = u(3,3,r(n-1)) = g(3,r(n-1))` 64 times, outputting the final value (`r` is chosen instead of `g` to avoid confusion).

To test this part, start from `r0=2` and then compute `r1`: `ug3tG1 2`.

# Answer
> 7 votes
## JavaScript (ES7), 63 bytes

```
u=(n,m)=>n>1&m>1?u(u(n-1,m),m-1):3**n
g=n=>n?u(3,g(n-1)):4
g(64)

```

# Answer
> 7 votes
# Sesos, 30 bytes

```
0000000: 286997 2449f0 6f5d10 07f83a 06fffa f941bb ee1f33  (i.$I.o]...:....A...3
0000015: 065333 07dd3e 769c7b                              .S3..>v.{

```

### Disassembled

```
set numout
add 4
rwd 2
add 64
jmp
    sub 1
    fwd 3
    add 3
    rwd 1
    add 1
    jmp
        sub 1
        jmp
            fwd 1
            jmp
                jmp
                    sub 1
                    fwd 1
                    add 1
                    rwd 1
                jnz
                rwd 1
                jmp
                    sub 1
                    fwd 3
                    add 1
                    rwd 3
                jnz
                fwd 3
                jmp
                    sub 1
                    rwd 2
                    add 1
                    rwd 1
                    add 1
                    fwd 3
                jnz
                rwd 1
                sub 1
            jnz
            rwd 1
            jmp
                sub 1
            jnz
            add 1
            rwd 1
            sub 1
        jnz
        fwd 1
        jmp
            sub 1
            rwd 1
            add 3
            fwd 1
        jnz
        rwd 2
    jnz
    rwd 1
jnz
fwd 2
put

```

Or in Brainfuck notation:

```
++++<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
[->>>+++<+[-[>[[->+<]<[->>>+<<<]>>>[-<<+<+>>>]<-]<[-]+<-]>[-<+++>]<<]<]>>.

```

### Testing

To compute *u*(3, *n*, *u*(3, *n*, … *u*(3, *n*, *m*) … )) with *k* nested calls to *u*, replace the first three `add` instructions `add 4`, `add 64`, `add 3` with `add m`, `add k`, `add n`, respectively. Because Sesos can’t build numbers faster than in linear time, you’re practically limited to small values like *u*(3, 2, 2) = 27, *u*(3, 5, 1) = 243, and *u*(3, 1, *u*(3, 1, … *u*(3, 1, *m*) … )) = 3.

# Answer
> 6 votes
# Brachylog, 57 bytes

```
4:64:1iw
:3{[1:N],3:N^.|t1,3.|hM:1-X,?t:1-:Mr:2&:Xr:2&.}.

```

Expects no Input nor Output and writes the result to `STDOUT`. This will produce a stack overflow at one point.

To check that this works for small values (e.g `u(3,3,2)`) you can replace the `4` with the value of `m` and `64` with `1`.

### Explanation

This is basically a straightforward implementation of the explained way of computing the number.

* Main predicate:

```
4:64:1i                    Call Predicate 1 64 times with 4 as initial input (the second
                           call takes the output of the first as input, etc. 64 times).
       w                   Write the final output to STDOUT

```
* Predicate 1:

```
:3{...}.                   Call predicate 2 with input [Input, 3]. Its output is the
                           output of predicate 1.

```
* Predicate 2:

```
[1:N],                     M = 1
      3:N^.                Output = 3^N
|                          Or
t1,                        N = 1
   3.                      Output = 3
|                          Or
hM:1-X,                    X is M - 1
       ?t:1-:Mr:2&         Unify an implicit variable with u(3,N-1,M)
                  :Xr:2&.  Unify Output with u(3,u(3,N-1,M),X)

```

# Answer
> 6 votes
# Caramel, 38 bytes

```
(64 ((f->(f,1)),(n f->(3 (n f))),3) 4)

```

This is syntactic sugar for the lambda calculus expression 64 (λ*m*. *m**f*. λ*n*. *n* *f* 1) (λ*n*. λ*f*. 3 (*n* *f*)) 3) 4, where all numbers are represented as Church numerals.

# Answer
> 3 votes
# Mathematica, 59 bytes

```
n_ ±1:=3^n
1 ±m_:=3
n_ ±m_:=((n-1)±m)±(m-1)
Nest[3±#&,4,64]

```

Uses an undefined infix operator `±` which requires only 1 byte when encoded in ISO 8859-1. See @Martin's post for more info. Mathematica functions support pattern matching for their arguments, such that the two base cases can be defined separately.

# Answer
> 3 votes
# Prolog (SWIPL), 129 / 137 bytes

```
g(1,R):-u(3,4,R).
g(L,R):-M is L-1,g(M,P),u(3,P,R).
u(N,1,R):-R is 3**N.
u(1,_,3).
u(N,M,R):-K is N-1,L is M-1,u(K,M,Y),u(Y,L,R).

```

To output Graham's number, query for `g(64,G).` (if the 8 bytes of this query are to be counted, the length is 137 bytes):

```
?- g(64, G).
ERROR: Out of local stack

```

But as can be expected, this runs out of stack.

## Test

```
?- u(3, 2, X).
X = 7625597484987

```

Backtracking causes it to run out of stack:

```
?- u(3, 2, X).
X = 7625597484987 ;
ERROR: Out of local stack

```

## Ungolfed

The ungolfed version adds the general up-arrow notation, not just for 3, and uses cuts and checks to avoid backtracking and undefined situations.

```
% up-arrow notation
u(X, 1, _M, X) :- !.
u(X, N, 1, R) :-
    R is X**N, !.
u(X, N, M, R) :-
    N > 1,
    M > 1,
    N1 is N - 1,
    M1 is M - 1,
    u(X, N1, M, R1),
    u(X, R1, M1, R).

% graham's number
g(1,R) :- u(3, 3, 4, R), !.
g(L,R) :-
    L > 1,
    L1 is L - 1,
    g(L1,G1),
    u(3, G1, R).

```

# Answer
> 3 votes
# C, 161 bytes

```
u(int a, int b){if(a==1)return 3;if(b==1)return pow(3,a);return u(u(a-1,b),b-1);}
g(int a){if(a==1)return u(3,4);return u(3,g(a-1));}
main(){printf("%d",g(64));}

```

EDIT: saved 11 bytes by removing tabs and newlines. EDIT: thx auhmann saved another byte and fixed my program

# Answer
> 2 votes
# C, ~~114~~ 109 bytes

Based on the answer by @thepiercingarrow (link) I golfed the answer down quite a bit. Most savings are due to the abuse of default typing of arguments when doing K&R style functions and replacement of if statements with ternary operators. Added optional newlines between functions for readability.

Improved to 109 thanks to @LeakyNun.

```
u(a,b){return a<2?3:b<2?pow(3,a):u(u(a-1,b),b-1);}
g(a){return u(3,a<2?4:g(a-1));}
main(){printf("%d",g(64));}

```

# Answer
> 1 votes
## Python, 85 bytes

```
v=lambda n,m:n*m and v(v(n-1,m)-1,m-1)or 3**-~n
g=lambda n=63:v(2,n and g(n-1)-1or 3)

```

The `v` function defines the same function as the one found in Dennis's answer: `v(n,m) = u(3,n+1,m+1)`. The `g` function is a zero-indexed version of the traditional iteration: `g(0) = v(2,3), g(n) = v(2,g(n-1))`. Thus, `g(63)` is Graham's number. By setting the default value of the `n` parameter of the `g` function to `63`, the required output can be obtained by calling `g()` (with no parameters), thus meeting our requirements for a function submission which takes no input.

Verify the `v(2,1) = u(3,3,2)` and `v(4,0) = u(3,5,1)` test cases online: Python 2, Python 3

# Answer
> 1 votes
## Dyalog APL, 41 bytes

```
u←{1=⍺:3⋄1=⍵:3*⍺⋄(⍵∇⍨⍺-1)∇⍵-1}
3u 3u⍣64⊣4

```

Test case:

```
      3u 2
7625597484987

```

# Answer
> 1 votes
# Ruby, 64 bytes

Borrowing from Theoretical algorithm to compute Graham's number.

```
def f(a,b=3)b<2?3:a<1?3*b:f(a-1,f(a,b-1))end;a=4;64.times{a=f a};p a

```

Simply put, `f a = u(3,3,a)` and it applies this 64 times.

# Answer
> 1 votes
# Jelly, 22 bytes

```
’ß’ß’}ð‘3*ða?
4’2çƊ64¡

```

Try it online!

I believe this is close to identical to Dennis' deleted Jelly answer but was developed independently and uses a language feature that wasn't available at the time of his answer.

The first line defines a function \\$v(n, m) = u(3, n+1, m+1)\\$ and the TIO footer demonstrates this for \\$u(3, 3, 2)\\$, \\$u(3, 5, 1)\\$ and \\$u(3, 1, 5)\\$.

With our defined \\$v\\$, we then have the recurrence relation

\begin{align\*} g\_1 & = v(2, 3) \\ g\_{i+1} & = v(2, g\_i - 1) \\ G = g\_{64} & = v(2, g\_{63} - 1) \end{align\*}

A more standard approach, which defines \\$w(n, m) = u(3, n, m)\\$ and then uses

\begin{align\*} g\_1 & = w(3, 4) \\ g\_{i+1} & = w(3, g\_i) \\ G = g\_{64} & = w(3, g\_{63}) \end{align\*}

comes out at 23 bytes:

```
3*ð’ßṛß’}ð«Ị¥?
4 3ç$64¡

```

Try it online!

## How they work

### \\$v(n, m)\\$

```
’ß’ß’}ð‘3*ða? - Helper link, v(n, m). Takes n on left, m on right
            ? - If:
           a  -   n and m are both non-zero
      ð       - Then:
’             -   n-1
 ß            -   v(n-1, m)
  ’           -   v(n-1, m)-1
    ’}        -   m-1
   ß          -   v(v(n-1, m)-1, m)
          ð   - Else:
       ‘      -   n+1
        3*    -   3^(n+1)

4’2çƊ64¡ - Main link. No arguments
4        - Set the return value and left argument to 4
    Ɗ    - Last 3 links as a monad f(x):
 ’       -   x-1
  2ç     -   v(2, x-1)
     64¡ - Starting with x = 4, iterate f(x) 64 times

```

### \\$w(n, m)\\$

```
3*ð’ßṛß’}ð«Ị¥? - Helper link, w(n, m). Takes n on left, m on right
            ¥? - If:
          «    -   min(n, m)
           Ị   -   is insignificant (abs(x) ≤ 1)
  ð            - Then:
3*             -   3^n
         ð     - Else:
   ’           -   n-1
     ṛ         -   m
    ß          -   w(n-1, m)
       ’}      -   m-1
      ß        -   w(w(n-1, m), m-1)

4 3ç$64¡ - Main link. No arguments
4        - Set the return value and left argument to 4
    $    - Last two links as a monad g(x):
  3ç     -  w(3, x)
     64¡ - Starting with x = 4, iterate g(x) 64 times

```

# Answer
> 0 votes
# J, 107 bytes

```
u=:4 :0
if.y=1 do.3^x
elseif.x=1 do.3
elseif.1 do.x:(y u~<:x)u<:y
end.
)
(g=:(3 u 4[[)`(3 u$:@<:)@.(1&<))64

```

I'm working on converting `u` to an agenda, but for now it'll do.

# Answer
> 0 votes
# F#, ~~111~~ 108 bytes

### Edit

This is using the function below to calulcate Graham's number

```
let rec u=function|b,1->int<|3I**b|1,c->3|b,c->u(u(b-1,c),c-1)
and g=function|1->u(3.,4.)|a->u(3.,g (a-1))
g 63

```

Here's my previous answer which, well, didnt:

Pretty straightforward. Just a definition of the `u` function.

```
let rec u=function|a,b,1->a**b|a,1.,c->a|a,b,c->u(a,u(a,b-1.,c),c-1)

```

Usage:

```
u(3.,3.,2)
val it : float = 7.625597485e+12

```

If I assumed 3 as the value for a, I could cut it to 60:

```
let rec u=function|b,1->3.**b|1.,c->3.|b,c->u(u(b-1.,c),c-1)

```

Usage:

```
u(3.,2)
val it : float = 7.625597485e+12

```

# Answer
> 0 votes
## R, ~~154~~ ~~142~~ ~~128~~ ~~126~~ 118 bytes

```
u=function(n,b)return(if(n&!b)1 else if(n)u(n-1,u(n,b-1))else 3*b)
g=function(x)return(u(if(x-1)g(x-1)else 4,3))
g(64)

```

I used the Wikipedia definition of this recursive function because for some odd reason the suggested one did not work... or I just suck at R golfing.

UPD: shaved off 12+14=26 bytes thanks to a tip from Leaky Nun. The prior version used the bulky and less efficient

```
u=function(n,b)if(n==0)return(3*b)else if(n>0&b==0)return(1)else return(u(n-1,u(n,b-1)))
g=function(x)if(x==1)return(u(4,3))else return(u(g(x-1),3))

```

UPD: shaved off 2+6+2 more bytes (again, kudos to Leaky Nun) owing to an ingenious replacement with “if(x)” instead of “if(x==0)” because x\<0 is never fed into the function... right?

# Answer
> 0 votes
# PHP, 114 bytes

ignore the line breaks; they are for readability only.

```
function u($n,$m){return$m>1&$n>1?u(u($n-1,$m),$m-1):3**$n;}
function g($x){return u(3,$x>1?g($x-1):4);}
echo g(63);

```

It is possible to integrate the second case into the first one: for `n=1`, `3^n` equals `3`.
This will save a few bytes on - as far as I can see - all existing answers; saved two bytes on my

**previous version, 62+43+11=116 bytes**

```
function u($n,$m){return$m>1?$n>1?u(u($n-1,$m),$m-1):3:3**$n;}

```

PHP´s left associativity of the ternary requires parentheses ... or a specific order of tests.
This saved two bytes on the parenthesized expression.

---

There is probably an iterative approach, which *may* allow further golfing ...
but I can´t take the time for it now.

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