title: Compute cumulative means efficiently

text:
# Question
Title: Compute cumulative means efficiently
Consider a sorted array of positive floating point numbers such as:

```
input = [0.22, 2.88, 6.35, 7.17, 9.15]

```

For each integer \\$i\\$ from 1 up to the last value in input rounded up, output the mean of all values less than \\$i\\$.

In this case the output should be:

```
[0.22 0.22 1.55 1.55 1.55 1.55 3.15 4.155 4.155 5.154 ]

```

If there is no value in the input less than \\$i\\$ you don't need to add anything to the output.

More examples: (output rounded to three decimal places)

```
input = [2.37, 4.15, 5.47, 6.64, 7.01, 8.87, 9.37]

output = [2.37 2.37 3.26 3.997 4.657 5.128 5.752 6.269]

input =  [2.22, 2.66]

output = [2.44]

input = [0.09, 0.09, 2.21, 3.64, 7.26, 7.58, 9]

output = [0.09, 0.09, 0.797, 1.508, 1.508, 1.508, 1.508, 3.478, 3.478]

input = [0.35, 2, 2.45, 3.71, 5.13, 9.0, 9.66]

output = [0.35, 0.35, 1.6, 2.128, 2.128, 2.728, 2.728, 2.728, 2.728, 4.614]

```

You can round your output to three decimals places or not as you choose.

Your code should run in linear time in the length of the output plus the length of the input

# Answer
# APL(Dyalog Unicode), ~~19~~ 20 bytes SBCS

Added 1 byte to fix handling of trailing integers.

```
(⌈¯2-/⌊,⊢/)⊢⍤/+\÷⍳⍤≢

```

Try it on APLgolf!

```
                       ⍝ n←≢input, m←≢output
              +\÷⍳⍤≢   ⍝ Cumulative averages
                 ⍳⍤≢   ⍝ Numbers from 1 to n    - O(n)
              +\       ⍝ Cumulative sums        - O(n)
                ÷      ⍝ Elementwise division   - O(n)
 ⌈¯2-/⌊,⊢/             ⍝ Repeat counts
        ⊢/             ⍝ Last value             - O(1)
      ⌊                ⍝ Floor of each number   - O(n)
       ,               ⍝ Concatenate            - O(n)
  ¯2-/                 ⍝ Adjacent differences   - O(n)
 ⌈                     ⍝ Ceil (last difference) - O(n)
           ⊢⍤/         ⍝ Repeat cumulative averages by
                       ⍝ counts on the left     - O(m+n)

```

I'm pretty sure I can replace `⍳⍤≢` by the grading (sorting indices) primitive  because sorting a sorted list will always be O(n), but I can't really prove that.
> 8 votes

# Answer
# C (gcc), ~~91 100~~ 95 bytes

```
i;n;f(a,l,s)float*a,s;{for(i=n=s=0;i<a[l-1]+1;n<l&&a[n]<i?s+=a[n++]:++i*n&&printf("%f ",s/n));}

```

Try it online!

## Explanation

\\$i \le \lceil x \rceil \iff i \lt x + 1 \qquad \forall \quad i \in \mathbb{Z} \quad \textrm{and} \quad x \in \mathbb{R}\\$
> 7 votes

# Answer
# Jelly, 11 bytes

```
ĊṪṭḞIx@Ä÷JƊ

```

A monadic Link that accepts a sorted list of positive floats and yields a sorted list of floats - the cumulative averages without any leading zeros.

**Try it online!**

### How?

```
ĊṪṭḞIx@Ä÷JƊ - Link: sorted list of positive floats, A = [a,b,...,z]
                      (length(A)=n, ceil(A[n])-ceil(A[0])+1=m)
Ċ           - ceiling  - O(n) -> [ceil(a),ceil(b),...,ceil(z)]
 Ṫ          - tail     - O(1) -> [ceil(z)]
  ṭ         - tack     - O(1) -> [a,b,...,z,ceil(z)]
   Ḟ        - floor    - O(n) -> [floor(a),...,floor(z),floor(ceil(z))]
    I       - deltas   - O(n) -> [floor(b)-floor(a),...,floor(z)-floor(y),floor(ceil(z))-floor(z)]
          Ɗ - last three links as a monad - f(A):
       Ä    -   sums   - O(n) -> [a,a+b,...,sum(A)]
         J  -   range  - O(n) -> [1..n]
        ÷   -   divide - O(n) -> [a,(a+b)/2,(a+b+c)/3,...]
      @     - with swapped arguments:
     x      -   repeat - O(n+m) -> [a,..a,(a+b)/2,...,(a+b)/2,...,...,Total/N]

```
> 6 votes

# Answer
# OCaml, 290 bytes

290 bytes, it can be golfed much more. Any suggestion would be appreciated.

Golfed version. Try it online!

```
let mean_lt_i arr=let max=ceil(List.hd(List.rev arr))in let rec helper arr sum count i=if i>max then[]else match arr with |[]->(sum/.count)::(helper[]sum count(i+.1.0))|h::t->if h<i then helper t(sum+.h)(count+.1.0)i else(sum/.count)::(helper arr sum count(i+.1.0))in helper arr 0.0 0.0 1.0

```

Ungolfed version. Try it online!

```
let mean_lt_i arr =
    let max = ceil (List.hd (List.rev arr)) in
    let rec helper arr sum count i =
        if i > max then []
        else match arr with
            | [] -> (sum /. count)::(helper [] sum count (i +. 1.0))
            | h::t -> if h < i then helper t (sum +. h) (count +. 1.0) i
                      else (sum /. count)::(helper arr sum count (i +. 1.0))
    in helper arr 0.0 0.0 1.0

let _ =
    let arr = [0.22; 2.88; 6.35; 7.17; 9.15] in
    mean_lt_i arr |> List.iter (Printf.printf "%.3f ");
    Printf.printf("\n");
    let arr = [2.37; 4.15; 5.47; 6.64; 7.01; 8.87; 9.37] in
    mean_lt_i arr |> List.iter (Printf.printf "%.3f ");

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 71 or 110 bytes

```
Reap[Do[t=Select[#,#<i&];If[t!={},Sow@Mean@t],{i,⌈Max@#⌉}]][[2,1]]&

```

Try it online!

I had doubts about the time linearity, but the tests show that it is linear:

Try it online!

And for this code, the linearity of time can be algorithmically proven:

```
(c=1;m=0;Reap[Do[If[#[[c]]<i,m=Mean@#[[;;c++]];Sow@m,If[m>0,Sow@m,c=Min[Length@#,c+1]]],{i,⌈Max@#⌉}]][[2,1]])&

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 18 bytes

```
Å»+}ā/I¤îªï¥øε`и}˜

```

Port of @JonathanAllan's Jelly answer (but without the convenient \\$O(n)\\$ builtins..), so make sure to upvote him as well!

Try it online or verify all test cases.

**Explanation:**

```
Å» }      # O(n)   Cumulative left-reduce the (implicit) input-list by:
  +       # O(1)    Adding items together
    ā     # O(1)   Push a list in the range [1,length] (without popping)
     /    # O(n)   Divide the values at the same positions in the lists
I         # O(1)   Push the input-list again
 ¤        # O(1)   Push its last/maximum value (without popping the list)
  î       # O(1)   Ceil that last value
   ª      # O(1)   Append it to the list
    ï     # O(n)   Floor each value in the list
     ¥    # O(n)   Get the forward differences of this list
ø         # O(n)   Pair the values of the two lists together
 ε        # O(n)   Map over each value:
  `       # O(1)    Pop and push the values of the pair to the stack
   и      # O(n+m)  Repeat the value the count amount of times as list
 }˜       # O(n)   After the map: flatten the list of lists
          # O(1)   (after which the result is output implicitly)

```

Unfortunately 05AB1E lacks vectorized repeat and/or zip-with builtins, hence the use of `øε`и}` (zip, map, and repeat separately). `δиÅ\` would be 1 byte shorter for this snippet, but would make it quadratic instead of linear.

**Without the , it could have been 10 bytes:**

```
¤îLε‹ÏÅA}˜

```

Try it online or verify all test cases.

**Explanation:**

```
¤         # Get the last/maximum value of the (implicit) input-list
 î        # Ceil it
  L       # Pop and push a list in the range [1, ceil(max)]
   ε      # Map over each value:
    ‹     #  Check for each value in the (implicit) input-list whether it's smaller than
          #  this value
     Ï    #  Only keep the values of the (implicit) input-list where this is truthy
      ÅA  #  Get the arithmetic mean of these remaining values
   }˜     # After the map: flatten the list of lists
          # (after which the result is output implicitly)

```
> 3 votes

# Answer
# Awk, 81 79 66 62 bytes:

`{for(;g<int($1);g++)if(n)print(m);m+=($1-m)/++n}END{print(m)}`

Try it here: https://www.jdoodle.com/ia/I4A

Takes as input (and outputs) a contiguous newline-separated list of numbers. Will take input with gaps if an initial regex is added to only accept lines with numbers. 2 bytes reduced with canny substitution for `NR`. 17 bytes reduced by squashing *everything* (updating `g`) into a loop with all unnecessary variables trimmed, giving a healthy side effect of reducing punctuation.

---

Degolfed:

```
# implicit init: n=0, m=0, g=0
{for(;             # golfy blank init
    g<int($1);     # bring old floor up to new (no-op if equal):
    g++)           # print the current cumulative mean
                   # conveniently the right number of times
 if(n)             # just don't print on first entry
  print(m)         # print cumulative mean
   ;               # we can chain functions without semicolons?? how very golfy
m+=($1-m)/++n}     # increment n and inline cumulative mean
END{print(m)}      # one last time, with feeling

```

Code is transparently linear in input size, taking advantage of the sorted-ness of the array.
> 3 votes

# Answer
# , ~~67~~ 57 bytes

```
\(i)c(na.omit(sapply(1:-(-max(i)%/%1),\(x)mean(i[i<x]))))

```

Attempt This Online!

(shaved off 10 thanks to @dominic-van-essen)
> 3 votes

# Answer
# Wolfram Language(Mathematica), ~~196~~ ~~187~~ 179 bytes

\\$\color{red}{\text{The code doesn't output correct results. Any help would be appreciated.}}\\$

---

Saved 17 bytes thanks to the comment of @erfink

Golfed version. Try it online!

```
Module[{s=0,n=0,o={},i=1,j=1,l=Length,a=AppendTo},While[j<=l@p&&i<=Ceiling@Last@p,If[p[[j]]<i,s+=p[[j]];n++;j++;o~a~N[s/n],If[l@o!=0,o~a~Last@o];i++];If[j<=l@p&&p[[j]]>=i,i++]];o]

```

Ungolfed version. Try it online!

```
calculateMeans[input_List] :=
 Module[{max = Ceiling[Last[input]], sum = 0, n = 0, output = {}, i = 1, j = 1},
  While[j <= Length[input] && i <= max,
   If[input[[j]] < i,
    sum += input[[j]];
    n++;
    j++;
    AppendTo[output, N[sum/n]];
    ,
    If[Length@output!=0,AppendTo[output, Last[output]]];
    i++;
   ];
   If[j <= Length[input] && input[[j]] >= i,
    i++;
   ];
  ];
  output
 ]

input = {0.22, 2.88, 6.35, 7.17, 9.15};
calculateMeans[input] //Print

input = {2.37, 4.15, 5.47, 6.64, 7.01, 8.87, 9.37};
calculateMeans[input] //Print

```
> 2 votes

# Answer
# Python 3, 121 bytes

```
def f(a):
 i=n=s=0
 while i<a[-1]+1:
  if n<len(a)and a[n]<i:s+=a[n];n+=1
  else:i+=1;n>0and print(s/n, end=' ')
 print()

```

Try it online!

This is just a python version of c--'s C solution.
> 2 votes

# Answer
# Haskell, 102 bytes

```
y x=y x 0.0 1.0 0where y(x:z)s i n|x<i=y z(s+x)i(n+1)|0<1=y[]s i n++y(x:z)s(i+1.0)n;y[]s i n=[s/n|n>0]

```

Try it online!

# Haskell, 179 bytes, sorted input ≥0, O(n)

```
import Data.List
c v=d$map last$groupBy((.fst).(==).fst)$zip(floor<$>v)$zipWith(/)(scanl1(+)v)[1.0..]
d w=concat$zipWith replicate((\z->zipWith(-)(tail z)z++[1])$fst<$>w)(snd<$>w)

```

Try it online!
> 1 votes

# Answer
# SAS

Input data in SAS can be passed as a SAS data set (standard SAS data transporting structure) or as macrovariable (a text string).

Solution 1) is based on input in SAS data set. Solution 2) is based on input passed as a text string. Though the solution 2) is 3 bytes shorter, it is the 1) which probably is more "SAS way".

---

**Solution 1)**

# 122 bytes

*Input:* Input is a SAS dataset `i` containing variable `x`:

```
data i;
infile cards dsd;
input x @@;
cards;
0.22, 2.88, 6.35, 7.17, 9.15
;
run;

```

Code:

```
data a;merge i i(rename=(x=y) firstobs=2);s+x;a=s/_N_;do j=j to coalesce(y,ceil(x));if j>x then output;end;retain j 1;run;

```

Human readable code:

```
data a;
  merge
    i
    i(rename=(x=y) firstobs=2);

  s+x;
  a=s/_N_;

  do j=j to coalesce(y,ceil(x));
    if j>x then output;
  end;
retain j 1;
run;

```

The solution utilise `merge` statement which reads dataset `i` and data set `i` starting from the second observation with variable `x` renamed to `y`. Effectively for each value of `x` the `y` variable contains the next value. Only for the last value of `x` value of `y` is missing.

Dataset `a` contains cumulative average in variable `a` (alongside source data).

---

**Solution 2)**

# 119 bytes

*Input:* Input is a text string passed by a macrovariable `x`:

```
%let x=0.22, 2.88, 6.35, 7.17, 9.15;

```

Code:

```
data;array d[999](&x);do i=1to ceil(max(of d:));do while(-d[j+1]>-i);j+1;s+d[j];end;a=s/(j<>1);if a then put a;end;run;

```

Human readable code:

```
data;
  array d[999] (&x);

  do i=1 to ceil(max(of d:));
    do while(-d[j+1]>-i);
      j + 1;
      s + d[j];
    end;
    a = s/(j<>1);

    if a then put a;
  end;
run;

```

Result of the processing is printed out in the SAS log with `put a;` statement.

If text string in macrovariable `&x` contains more than 999 elements this part: `d[999]` has to be properly adjusted (what extends length). But, up to 999999, it still is not worse than 1).

The `array` statement in SAS data step (in this context) should not be confused with arrays which are available for example in C. In this context the `array d[999] (&x)` means "create 999 variables named `d1`, `d2`, ..., `d999` initiated with values from text string passed by macrovariable `&x`.

---
> 1 votes

# Answer
# Charcoal, 31 bytes

```
⊞θ⌈⌈θ≔⁰η≔⁰ζＦθ«≦⊕η≧⁺ιζＩＥ…ι§θη∕ζη

```

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

```
⊞θ⌈⌈θ

```

Push the ceiling of the largest element of the list to the list.

```
≔⁰η≔⁰ζ

```

Start with no elements so far with a running total of zero.

```
Ｆθ«

```

Loop over the elements.

```
≦⊕η≧⁺ιζ

```

Update the count and sum.

```
ＩＥ…ι§θη∕ζη

```

Output the current average for each new integer before the next value.

19 bytes for quadratic complexity:

```
ＩＥΦＥ⊕⌈⌈θΦθ‹λιι∕ΣιＬι

```

Try it online! Link is to verbose version of code.
> 1 votes

# Answer
# Excel, 49 bytes

```
=TOCOL(AVERAGEIF(A:A,"<"&SEQUENCE(1+MAX(A:A))),2)

```

Input is vertical array beginning in cell `A1`.
> 0 votes

# Answer
# Elixir, 138 bytes

Golfed version. Try it online!

```
def y([],s,_,n),do: if n>0,do: [s/n],else: []
def y([x|z]=list,s,i,n)do if x<i do y(z,s+x,i,n+1)else y([],s,i,n)++y(list,s,i+1.0,n)end end

```

Ungolfed version. Try it online!

```
defmodule Main do
  def y([], s, _, n), do: if n > 0, do: [s/n], else: []
  def y([x | z] = list, s, i, n) do
    if x < i do
      y(z, s + x, i, n + 1)
    else
      y([], s, i, n) ++ y(list, s, i + 1.0, n)
    end
  end

  def main do
    IO.inspect y([2.37, 4.15, 5.47, 6.64, 7.01, 8.87, 9.37], 0.0, 1.0, 0)
  end
end

Main.main()

```
> 0 votes

# Answer
# Erlang(escript), 127 bytes

Golfed version. Try it online!

```
y([],S,_,N)when N>0->[S/N];y([],_,_,_)->[];y([X|Z]=List,S,I,N)->if X<I->y(Z,S+X,I,N+1);true->y([],S,I,N)++y(List,S,I+1.0,N)end.

```

Ungolfed version. Try it online!

```
-module(main).
-export([y/4, main/1]).

y([], S, _, N) when N > 0 -> [S / N];
y([], _, _, _) -> [];
y([X | Z] = List, S, I, N) ->
    if X < I ->
        y(Z, S + X, I, N + 1);
    true ->
        y([], S, I, N) ++ y(List, S, I + 1.0, N)
    end.

main(_) ->
    io:fwrite("~p~n", [y([0.35, 2, 2.45, 3.71, 5.13, 9.0, 9.66], 0.0, 1.0, 0)]).

```
> 0 votes

# Answer
# Racket, 204 bytes

Golfed version. Try it online!

```
(define (y lst s i n) (cond [(empty? lst) (if (> n 0) (list (/ s n)) '())] [else (let ([x (first lst)] [z (rest lst)]) (if (< x i) (y z (+ s x) i (+ n 1)) (append (y '() s i n) (y lst s (+ i 1.0) n))))]))

```

Ungolfed version. Try it online!

```
#lang racket

(define (y lst s i n)
  (cond
    [(empty? lst) (if (> n 0) (list (/ s n)) '())]
    [else
     (let ([x (first lst)]
           [z (rest lst)])
       (if (< x i)
           (y z (+ s x) i (+ n 1))
           (append (y '() s i n) (y lst s (+ i 1.0) n))))]))

(define (main)
  (displayln (y '(0.35 2 2.45 3.71 5.13 9.0 9.66) 0.0 1.0 0)))

(main)

```
> 0 votes

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


title: Build an RSA encoder

text:
# Question
Title: Build an RSA encoder
Your task is to build a function in any language that takes a message `m`, an encryption `e`, and a modulus `k` (all positive integers), and takes `m` to the power of `e` modulo `k`. Your solution must not be a theoretical one, but one that would work on a reasonable computer such as your own, for RSA keys of currently used sizes such as 2048 bits.

Shortest code wins.

# Answer
> 6 votes
# Python – 5

Python 3 built-in function pow have third parameter. So Python 3 already have built-in RSA encoder

```
r=pow

```

# Answer
> 1 votes
Here's my first attempt at actually golfing something here:

# Python – ~~69~~ ~~61~~ 55

```
r=lambda m,e,k:1 if e==0 else m**(e%2)*r(m*m%k,e/2,k)%k

```

This is a simple exponentiation by squaring algorithm.

---

**02/15 13:17 – 61:** Used lambda notation.
**02/22 15:44 – 55:** Removed some brackets as per grc's suggestions.

# Answer
> 0 votes
## java (83 chars)

if input is of BigInteger type:

```
public BigInteger r(BigInteger m,BigInteger e,BigInteger k){return m.modPow(e,k);}

```

# Answer
> 0 votes
# Husk, 7 bytes

```
!¡o%⁰*³

```

Try it online!

Function that takes arguments: arg1=m (message), arg2=k (key/modulus), arg3=e (exponent/encryption).

Encoding takes about 10 seconds on \[Try it online!\] with a message of `12345678910`, a 2048-bit key/modulus of `17335246217810680499565282364130282347913694411139706552337646969996795185310539972695213589521948877888710148108314183322475193115466538523720272848165926667358225384343389288464059692412384746831929390686202279817642231618920311152771862965772849228722380926373552800043250590230507345247504584516585217552163181827225685419709962073929610117852078754818132187957128758451536498778247147713136878727238232838512570562685513074673965992921930197584545660069134797478016576085619884280636191861425890311213983668804147423192923778212236303196414996652277121672303217925415867248268691221399027188630076689585126618899`, and exponent/encryption of `65537`.

Decoding is significantly longer when (as is usual) the decryption exponent d is much larger than the encryption exponent e. But we can check that it works using small values: m=`123`, k=`257` and e=`7` (for which the decryption exponent d=`55`):
Try encoding
Try decoding

# Answer
> 0 votes
# Nibbles, 4 bytes (8 nibbles)

```
=_`.@%*_

```

```
=_`.@%*_        # full program
=_`.@%*_$@      # with implicit args added
  `.            # repeatedly apply (while results are unique)
    @           # starting with arg2:
      *_$       #   multiply arg2 by result-so-far
     %   @      #   and modulo by arg1
=_              # finally, return result at index given by arg3

```

Full program that takes arguments: arg1=k (key/modulus), arg2=m (message), arg3=e (exponent/encryption).

Encoding is fast (screenshot below shows a message of 12345678910, a 2048-bit key/modulus, and exponent/encryption of 65537).
Decoding is significantly longer when (as is usual) the decryption exponent d is much larger than the encryption exponent e. But we can check that it works using small values: m=123, k=257 and e=7 (for which the decryption exponent d=55).

---
Tags: code-golf, cryptography
---


title: Averages of Angles

text:
# Question
Title: Averages of Angles
## Story, *or why we are doing this.*

None. This exercise is completely pointless ... unless you are Stephen Hawking.

# The Challenge

Given a list of angles, find the average of those angles. For example the average of 91 degrees and -91 degrees is 180 degrees. You can use a program or function to do this.

# Input

A list of degree values representing angle measures. You may assume that they will be integers. They can be inputted in any convenient format or provided as function arguments.

# Output

The average of the inputted values. If there are more than one value found for the average, only one should be outputted. The average is defined as the value for which

is minimized. The output must be within the range of (-180, 180\] and be accurate to at least two places behind the decimal point.

**Examples:**

```
> 1 3
2
> 90 -90
0 or 180
> 0 -120 120
0 or -120 or 120
> 0 810
45
> 1 3 3
2.33
> 180 60 -60
180 or 60 or -60
> 0 15 45 460
40
> 91 -91
180
> -89 89
0

```

As usual with , the submission with the least bytes wins.

## Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

```
var QUESTION_ID=60538,OVERRIDE_USER=32700;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+)(?=[^\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>
```

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the leaderboard snippet:

```
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

Here is a chatroom for any questions about the problem: http://chat.stackexchange.com/rooms/30175/room-for-average-of-angles

# Answer
# Python 3, 129 bytes

```
lambda l:min([sum(((b-a)%360)**2for b in l)*len(l)-s*s,180-(180-a-s/len(l))%360]for a in l for s in[sum((b-a)%360for b in l)])[1]

```

This problem seems to have generated quite a lot of confusion. Intuitively, the idea is to cut the circle of angles at some point, unwrap the circle to a line, compute the arithmetic mean on that line, and then wrap the result back to the circle. But there are many different points where you could choose to cut the circle. It is not enough to arbitrarily pick one, such as 0° or 180°. You need to try them all and see which one results in the smallest sum of squared distances. If your solution is significantly less complicated than this, it is probably wrong.
> 7 votes

# Answer
## Python 3, 85 bytes

```
lambda l:180-min(range(72000),key=lambda x:sum((180-(x/200+i)%360)**2for i in l))/200

```

Takes advantage of the the answer only needing to be accurate to two decimal points by trying all possible angles with increments of `1/200` of a degree. This takes less than a second on my machine.

Because Python doesn't let us conveniently list arithmetic progressions of floats, we represent the possible angles as whole number `[0,72000)`, which convert to an angle as `(-180,180]` as `x -> 180 - x/200`. We find the one of these that gives the minimum sum of squared angular differences.

For two angles with an angular displacement of `d`, the squared angular distance is found by transforming to an equivalent angle in `(-180,180]` as `180-(d+180)%360`, then squaring. Conveniently, the angle given by `x/200` is already offset by `180` degrees.
> 4 votes

# Answer
# Octave, ~~97~~ 95 bytes

```
p=pi;x=p:-1e-5:-p;z=@(L)sum((p-abs(abs(x-mod(L,360)*p/180)-p)).^2);@(L)x(z(L)==min(z(L)))*180/p

```

This produces an anonymous function that just searches the minimum of the given function on a grid that is just fine enough. As input the function accepts column vectors, e.g. `[180; 60; -60]`. For testing you need to give the function a name. So you could e.g. run the code above and then use `ans([180, 60; -60])`.
> 3 votes

# Answer
# Javascript ES6, 87 bytes

```
with(Math)f=(...n)=>(t=>180/PI*atan(t(sin)/t(cos)))(f=>n.reduce((p,c)=>p+=f(c*PI/180)))

```

Example runs (Tested in Firefox):

```
f(-91,91)     // -0
f(-90,90)     // 0
f(0,-120,120) // 0
f(0,810)      // 44.999999999999936

```

***Work in progress***

This version takes a slightly different approach than the average-everything-then-do-modular-math. Rather, the angles are converted to vectors, the vectors are added and the angle of the resulting vector is then computed. Unfortunately, this version is **very** unstable with the trig and I'll be working on a modular-math version.
> 2 votes

# Answer
# CJam,  ~~44~~  40 bytes

```
Ie3_2*,f-:e-2{ea:~f{-P*180/mcmC2#}:+}$0=

```

Try it online in the CJam interpreter.

### Test cases

```
$ for i in 1\ 3 90\ -90 0\ -120\ 120 0\ 810 1\ 3\ 3 180\ 60\ -60 0\ 15\ 45\ 460 91\ -91 -89\ 89
> do cjam <(echo 'Ie3_2*,f-:e-2{ea:~f{-P*180/mcmC2#}:+}$0=') $i
> echo
> done
2.0
180.0
0.0
45.0
2.33
60.0
40.0
180.0
0.0

```

### Idea

We compute the deviation for all potential averages from **-179.99** to **180.00** with steps of size **0.01**, and select the one with the lowest deviation.

For this purpose, it doesn't matter if we take the angular distances degrees or radians. Rather than mapping the differences **δ** of angles from input and potential averages in **\[0,360°)** and conditionally subtracting the result from **180°**, we can simply calculate **arccos(cos(πδ÷180°))**, since **cos** is both periodic and even, and **arccos** always yields a value in **\[0,π)**.

### Code

```
Ie3        e# Push 18e3 = 18,000.
_2*        e# Copy and multiply by 2. Pushes 36,000.
,          e# Push the range [0 ... 35,999].
f-         e# Subtract each element from 18,000. Pushes [18,000 ... -17,999].
:e-2       e# Divide each element by 100. Pushes [180.00 ... -179.99].
{          e# Sort; for each element A of that array:
  ea:~     e#   Push and evaluate the array of command-line arguments.
  f{       e#   For each input angle, push A and the angle; then:
    -      e#     Subtract the angle from A.
    P*180/ e#     Convert from degrees to radians.
    mcmC   e#     Apply cos, then arccos to the result.
    2#     e#     Square.
  }        e#
  :+       e#   Add the squares. This calculates the deviation.
}$         e# A's with lower deviations come first.
0=         e# Select the first element of the sorted array.

```
> 2 votes

# Answer
# Scala, 96 bytes

Modified from @Roman Czyborra's answer.

---

Golfed version. Try it online!

```
x=>(-179 to 180).minBy(a=>x.map(i=>pow((a-i%360)match{case x if x>180=>x-360;case y=>y},2)).sum)

```

Ungolfed version. Try it online!

```
import scala.math._

object Main {
  def main(args: Array[String]): Unit = {
    println(a(List(0, 15, 45, 460)))
  }

  def a(x: List[Int]): Int = {
    (-179 to 180).minBy(a => x.map(i => pow((a - i % 360) match {
      case x if x > 180 => x - 360
      case y => y
    }, 2)).sum)
  }
}

```
> 2 votes

# Answer
# MATLAB, 151

```
p=360;n=mod(input(''),p);a=0:0.01:p;m=[];for b=a e=b-n;f=mod([e;-e],p);c=min(f);d=c.^2;m=[m sum(d)];end;[~,i]=min(m);a=a(i);if a>180 a=a-p;end;disp(a);

```

Ok, so until I can actually understand what the methodology is, this is what I have come up with. It is a little bit of a hack, but as the question states that the answer must be correct to 2.d.p it should work.

I basically check every angle between 0 and 360 (in 0.01 increments) and then solve the formula in the question for each of those angles. Then the angle with the smallest sum is picked and converted into -180 to 180 range.

---

The code should with **Octave**. You can try it with the online interpreter
> 1 votes

# Answer
# JavaScript (ES6) 138

Not having the faintest idea of an algorithm, this tries all possibile values with 2 digits precision (-179.99 to 180.00). Quite fast with the test cases anyway.

Test running the snippet below in an EcmaScript 6 compliant browser (implementing arrow functions and default parameters - AFAIK Firefox)

```
A=l=>(D=(a,b,z=a>b?a-b:b-a)=>z>180?360-z:z,m=>{for(i=-18000;i++<18000;)l.some(v=>(t+=(d=D(v%360,i/100))*d)>m,t=0)||(m=t,r=i)})(1/0)||r/100

// Test
console.log=x=>O.innerHTML+=x+'\n'

;[[1,3],[89,-89],[90,-90],[91,-91],[0,120,-120],[0,810],[1,3,3],[180,60,-60],[0,15,45,460],[1,183]]
.forEach(t=>console.log(t+' -> '+A(t)))

// Less golfed

A=l=>{
  D=(a,b,z=a>b?a-b:b-a) => z>180?360-z:z; // angular distance
  m=1/0;
  for(i=-18000;i++<18000;) // try all from -179.99 to 180
  {
    t = 0;
    if (!l.some(v => (t+=(d=D(v%360,i/100))*d) > m))
    {
      m = t;
      r = i;
    }
  }
  return r/100;
}
```

```
<pre id=O></pre>
```
> 1 votes

# Answer
# Haskell, 134 bytes, with fractional precision

```
a x=(/100)$fromIntegral$snd$minimum$map(\a->(sum$map((^2).(\x->last$x:[x-36000|x>18000]).(`mod`36000).(a-).(100*))x,a))[-17999..18000]

```

Try it online!

# Haskell, 97 bytes, with integer precision

```
a x=snd$minimum$map(\a->(sum$map((^2).(\x->last$x:[x-360|x>180]).(`mod`360).(a-))x,a))[-179..180]

```

Try it online!
> 1 votes

# Answer
# julia, 101 bytes

This version works to machine precision.

The idea is that If each entry of the input vector \\$x\in \mathbf{R}^n\\$ satisfies \\$x\_i \in (0, 360\]\\$, and if \\$x\\$ is sorted in ascending order, then the angle average is the arithmetic mean of $$ x^{(k)} :=x + (\overbrace{360, \dotsc, 360}^{k\text{ entries}}, 0, \dotsc, 0) $$ for some \\$k \in \\{1, \dotsc, n\\}\\$

Hence, the problem reduces to finding $$ k^\* = \underset{k=1, \dotsc, n}{\mathrm{argmin}} \sum\_{i=1}^n (x\_i^{(k)} - \bar{x}^{(k)})^2. $$

The corresponding arithmetic mean is then $$ \bar{x}^{(k^\*)} = \bar{x} + k^\* \cdot \frac{360}{n} $$

Finally, we put everything on the \\$(-180, 180\]\\$ scale by adding \\$180\\$ to the input, computing everything mod \\$360\\$ and subtracting \\$180\\$ at the end.

---

Expects a `Vector{Float64}` and returns a `Float64`.

```
y->(| =mod1;~=sum;s=360;x=sort(y.+.5s.|s);n=~y.^0;~x+argmin(k->(x[k]+=s;~(x.-~x/n).^2),1:n)s)/n|s-.5s

```

Attempt This Online!
> 1 votes

# Answer
# Julia 1.7, 61 bytes

```
p=180
!y=argmin(i->sum(j->((i-j%2p+p)%2p-p)^2,y),.01-p:.01:p)

```

Attempt This Online!

`argmin(f, itr)` needs julia 1.7 or later
> 0 votes

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


title: Euclidean distance on projective plane

text:
# Question
Title: Euclidean distance on projective plane
Motivated by this challenge

### Background

Let we have a square sheet of flexible material. Roughly speaking, we may close it on itself four ways:

Here the color marks the edges that connect and the vectors indicate the direction. The sphere and torus are obtained without flipping the sides, Klein bottle — with one flipping edge, and projective plane with both.

Surprisingly torus, not a sphere, in many senses is the simplest construct. For example, you can't comb a hairy ball flat without creating a cowlick (but torus can).
This is why torus is often used in games, puzzles and research.

### Specific info

This is a separate picture for fundamental polygon (or closing rule) of projective plane (for `1..N` notation):

Neighborhood of `[1, 1]` cell for `N x N` lattice:

Example how to find distance for points `(2, 4)` and `(5, 3)` in `5 x 5` projective plane:
Green paths are shortest, so it is the distance.

### Task

For given two points and size of lattice,
find euclidean distance between points on the projective plane.

### I/O

Flexible, in any suitable formats

### Test cases

For `1..N` notation
`N, p1, p2 → distance` For a better understanding, also indicated distance on torus (for same points and size):

```
5, [1, 1], [1, 1] → 0.0 (0.0)
5, [2, 4], [5, 3] → 2.24 (2.24)
5, [2, 4], [4, 1] → 2.0   (1.41)
10, [2, 2], [8, 8] → 4.12 (5.66)
10, [1, 1], [10, 10]  → 1.0 (1.41)
10, [4, 4], [6, 6]  → 2.83 (2.83)

```

# Answer
> 4 votes
# julia, ~~104~~ 97 bytes

This solution uses the quotient space metric. For the projective plane, if \\$\sim\\$ is the equivalence relation induced by the edge identification (i.e. \\$(p, 0) \sim (N-p, N); (0, p) \sim (N, N-p)\\$) and \\$d\\$ is the Euclidean metric, then the projective plane metric is $$ d'(a, b) = \min\_{w \sim w'} \[d(a, w) + d(b, w')\]. $$

To implement this, we create two grids \\$x\\$ and \\$y\\$ spanning \\$\[0, N\]^2\\$ such that \\$x\_{ij} \sim y\_{ij}\\$ and compute \\$d(a, x\_{ij}) + d(b, y\_{ij})\\$ for each corresponding pair of grid entries.

We make the vertical spacing between grid points \\$0.005\\$ to make sure that the result is correct to two decimal places.

```
u&v=((h=u-v.-.5)'h)^.5
g(N,a,b)=minimum(w->a&w+b&((N.-2w)any(w.%N.==0)+w),vcat.((r=0:.005:N)',r))

```

Attempt This Online!

Thanks to MarcMush for a 7-byte improvement!

### How?

```
# u&v is the distance between u-0.5 (centre of cell u) and v.
u&v = ((h = u - v .- .5)'h)^.5

# Minimise the function w -> d(a, w) + d(b, w')
g(N, a, b) = minimum(

    # (N .- 2w)any(w .% N .== 0) + w is N-w on the edges of x and w otherwise.
    w -> a&w + b&((N .- 2w)any(w .% N .== 0) + w),

    # Map over a grid of pairs [x1, x2] spanning [0, N]^2.
    vcat.((r = 0:.005:N)', r)
)

```

# Answer
> 3 votes
# Jelly, 20 bytes

```
_~jUŒHƲ€N⁹ṭ"_þ/ẎÆḊ€Ṃ

```

A dyadic Link that accepts the size on the left and a pair of pairs (the points) on the right and yields the Euclidean distance of the projective plane.

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

### How?

```
_~jUŒHƲ€N⁹ṭ"_þ/ẎÆḊ€Ṃ - Link: Size = S; Points = [[x1, y1], [x2, y2]]
_                    - {Size} subtract {Points} -> [[S-x1, S-y1], [S-x2, S-y2]]
       €             - for each of these pairs, [a, b]:
      Ʋ              -   last four links as a monad:
 ~                   -     bitwise NOT (vectorises) -> [-1-a, -1-b]
   U                 -     upend -> [b,a]
  j                  -     join  -> [-1-a, b, a, -1-b]
    ŒH               -     halve -> [[-1-a, b], [a, -1-b]]
        N            - negate    -> [[a+1, -b], [-a, b+1]]
         ⁹           - chain's right argument -> [[x1, y1], [x2, y2]]
           "         - zip with:
          ṭ          -   tack -> [[[S-x1+1, y1-S], [x1-S, S-y1+1], [x1, y1]],
                                  [[S-x2+1, y2-S], [x2-S, S-y2+1], [x2, y2]],
                                 ]
              /      - reduce by:
             þ       -   table with:
            _        -     subtraction
               Ẏ     - tighten
                ÆḊ€  - vector norm of each
                   Ṃ - minimum

```

# Answer
> 2 votes
# Python, 83 bytes (-35 thanks to @xnor)

```
lambda N,A,B:min(map(abs,(B-A,C:=B-1j*N-~N-2*B.real-A,D:=1+1j-C-2*A,C+2j*N,D+2*N)))

```

Attempt This Online!

### Obsolete Python, 118 bytes

```
lambda N,A,B,o=.5+.5j:min(map(lambda x:abs(A-o-x),[B:=B-o,C:=N/o+B-2*B.real,-B,2*N-B,2j*N-B,4*N*o-B,-C,C+2j*N,2*N-C]))

```

Attempt This Online!

Expects input coordinates as complex numbers.

# Answer
> 2 votes
# Python 3, 94 bytes

```
lambda n,X,Y,x,y:min(abs(X-a+(Y-b)*1j)for k in[-n,n]for a,b in[(x,y),(n+1-x,y+k),(x+k,n+1-y)])

```

Try it online!

Easier to understand as:

```
lambda n,X,Y,x,y:min(abs(X-a+(Y-b)*1j)for a,b in[(x,y),(n+1-x,y-n),(n+1-x,y+n),(x-n,n+1-y),(x+n,n+1-y)])

```

Try it online!

Fixes one point in place, and picks the closest version of the other point out of 5 options -- the original and the four reflections across the edges of the square. There's no need to consider diagonally-adjacent copies because they're always further from the fixed point than the original.

# Answer
> 1 votes
# Python3, 458 bytes

```
R=range
E=enumerate
def T(d,x,y,X,Y):
 if y%2:d=[[(*a,W+Y*len(d),k)for k,(*a,_,_)in E(i[::-1])]for W,i in E(d)]
 if x%2:d=[[(*a,W,k+X*len(i))for k,(*a,_,_)in E(i)]for W,i in E(d[::-1])]
 return[j for k in d for j in k]
def f(n,p,P):
 d=[[(i,j,i-1,j-1)for j in R(1,n+1)]for i in R(1,n+1)];O=[*T(d,0,0,0,0),*T(d,0,1,0,-1),*T(d,1,0,1,0),*T(d,0,1,0,1),*T(d,1,0,-1,0)]
 return min(((X-x)**2+(Y-y)**2)**0.5 for a,b,x,y in O for A,B,X,Y in O if[a,b]==p and[A,B]==P)

```

Try it online!

# Answer
> 1 votes
# JavaScript (ES6), 104 bytes

*Saved 9 bytes by refactoring in a way similar to what xnor did*

Expects `(N,x1,y1,x2,y2)`.

```
(N,x,y,X,Y)=>Math.min(...(g=q=>[x,x+q,N-x].map((v,i)=>Math.hypot(X-v,Y-[y,N-y,y+q][i])))(N++),...g(1-N))

```

Try it online!

# Answer
> 1 votes
# Charcoal, 41 bytes

```
⊞υηＦ⟦θ±θ⟧Ｆ²⊞υＥη⎇⁼κμ⁻⊕θλ⁺λιＩ₂⌊ＥυΣＸＥι⁻λ§ζμ²

```

Try it online! Link is to verbose version of code. Takes the size and the two points as input. Explanation:

```
⊞υη

```

Push the first point to the predefined empty list.

```
Ｆ⟦θ±θ⟧Ｆ²

```

Loop over each orthogonal direction.

```
⊞υＥη⎇⁼κμ⁻⊕θλ⁺λι

```

Push the transform of the point in that direction to the list.

```
Ｉ₂⌊ＥυΣＸＥι⁻λ§ζμ²

```

Output the minimum Euclidean distance from the second point to any of the five points inthe list.

I tried writing it as a single expression but it still came out to 41 bytes:

```
Ｉ₂⌊Ｅ⊞ＯＥ⁴Ｅη⎇﹪⁺ιμ²⁻⊕θλ⎇÷ι²⁺λθ⁻λθηΣＸＥι⁻λ§ζμ²

```

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

# Answer
> 0 votes
# Scala, 168 bytes

Golfed version. Try it online!

```
def f(N:Int,x:Int,y:Int,X:Int,Y:Int)={val(a,b)=(x-X,Y+y-N-1);(Seq(a,a-N,X+x-N-1,X+x-N-1,X+x-N-1,a+N)zip Seq(y-Y,b,y-Y-N,N-b,y-Y+N,b)).map{case(i,j)=>sqrt(i*i+j*j)}.min}

```

Ungolfed version. Try it online!

```
import scala.math.{sqrt, min}

object Main {
  def f(N: Int, x: Int, y: Int, X: Int, Y: Int): Double = {
    val a = Array(x - X, x - X - N, X + x - N - 1, X + x - N - 1, X + x - N - 1, x - X + N)
    val b = Array(y - Y, Y + y - N - 1, y - Y - N, N - (Y + y - N - 1), y - Y + N, Y + y - N - 1)
    val distances = (a zip b).map{ case (i, j) => sqrt(i*i + j*j) }
    distances.min
  }

  def main(args: Array[String]): Unit = {
    println(f(5, 1, 1, 1, 1)) // 0.0
    println(f(5, 2, 4, 5, 3)) // 2.24
    println(f(5, 2, 4, 4, 1)) // 2.0
    println(f(10, 2, 2, 8, 8)) // 4.12
    println(f(10, 1, 1, 10, 10)) // 1.0
    println(f(10, 4, 4, 6, 6)) // 2.83
  }
}

```

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


title: Cube calendar numbers

text:
# Question
Title: Cube calendar numbers
Credit: Marco Verch CC BY 2.0

A two-cube calendar, as shown in the picture, uses two cubes with digits painted on the faces to display the date. For dates in the range 1-9, a leading zero is used ("01", "02", ..., "09").

Now, if you do the math, you might come to the conclusion that these calendars should be impossible. After all, the numbers "0","1" and "2" must appear on both cubes (proof left to the reader). This means that there are only six faces remaining for the other seven numbers.

Two-cube calendars use a trick where the face with a "6" can be rotated upside down to look like a "9". For example, one cube may have faces "012345" and the other one "012678" where the "6" can also be a nine. For the purposes of this challenge these kind of font-dependent tricks are banned.

With these restrictions we can only display the numbers from 0 to 21 for a total of 22 numbers. We can display some other numbers too, but we are only interested in the longest possible sequence of numbers displayable (no gaps), starting from 0.

If, instead of using base 10, we would have used base 6, we could display \\$0-55\_6\\$ for a total of 36 numbers. (\\$55\_6=35\_{10}\\$)

If, instead of using cubes, we would have used octahedrons (8 faces), we could display 0-65 (using base 10).

And finally, with three cubes we can get 0-76 for a total of 77 numbers (using base 10).

The maximal amount of numbers we can get in the initial range is called the cube calendar number. It depends on the number of faces, on the number of dice ("cubes") and on the base of the numbers.

# Task

Given a base `b`, the number of faces `f` and the number of dice `d`, return the cube calendar number for those parameters.

`b`, `f` and `d` are natural numbers guaranteed to satisfy:

\\$b\ge 2\\$

\\$b\ge f \ge 1\\$

\\$d\ge 1\\$

# Test cases

```
d f b result
1 1 2 1
1 1 3 1
1 1 4 1
1 2 2 2
1 2 3 2
1 2 4 2
1 3 3 3
1 3 4 3
1 4 4 4
2 1 2 1
2 1 3 1
2 1 4 1
2 2 2 4
2 2 3 4
2 2 4 3
2 3 3 9
2 3 4 10
2 4 4 16
3 1 2 1
3 1 3 1
3 1 4 1
3 2 2 8
3 2 3 8
3 2 4 5
3 3 3 27
3 3 4 21
3 4 4 64
4 1 2 1
4 1 3 1
4 1 4 1
4 2 2 16
4 2 3 13
4 2 4 10
4 3 3 81
4 3 4 63
4 4 4 256
2 6 10 22
2 6 6 36
2 8 10 66
3 6 10 77

```

# Answer
# Python, 57 bytes (-8 thanks to @xnor)

```
lambda D,F,B:B**(D*~-F//~-B+1)//(B-(F<B>2))*(1+D*~-F%~-B)

```

Attempt This Online!

#### Previous Python, 65 bytes

```
lambda D,F,B:F//B*B**D or(B**(D*~-F//~-B+1)-1)//~-B*(1+D*~-F%~-B)

```

Attempt This Online!

#### Obsolete Python, 69 bytes

```
lambda D,F,B:(B**-(D*~-F//-~-B)-1)//~-B*((x:=B+D*~-F%-~-B)-F//B)+x//B

```

Attempt This Online!

# How?

Given D,F,B a best set of dice has a zero on every die because 0 (with leading zeros) must be representable. The remaining D(F-1) faces should evenly split between the B-1 non-zero digits. Indeed, if we write

\\$(1)\qquad M:=\lfloor D(F-1)/(B-1)\rfloor\\$

then to get up to at least \\$10\_{(B)}^M\\$ we need \\$11..11\_{(B)}, 22..22\_{(B)}, 33..33\_{(B)}\\$ etc. (M digits each).

How much farther can we go? If the division in (1) splits cleanly (no remainder) then we top out at \\$11..110\_{(B)}\\$ (M+1 digits). This also shows that if the split was not clean then the first excess face should be a 1. If that is the only excess face it will carry us up to \\$22..221\_{(B)}\\$. The next excess face if it exists should therefore be a 2. Etc. Since we start at 0, the corresponding cube calendar numbers are \\$11..11\_{(B)}=(10\_{(B)}^{M+1}-1)/(B-1),22..22\_{(B)},...\\$

It remains to special case B=F and that's it.
> 5 votes

# Answer
# Charcoal, 36 bytes

```
ＮθＮηＮζＩ×⊕﹪×θ⊖η⊖ζ÷Ｘζ⊕÷×θ⊖η⊖ζ⁻ζ∧‹ηζ›ζ²

```

Try it online! Link is to verbose version of code. Explanation: Now uses @xnor's correction `F<B>2` (my previous correction `F<B` didn't work in some cases) which is still a byte golfier than special-casing `F=B`; this now makes my answer equivalent to a port of his golf to @loopywalt's answer.

```
Ｎθ                                      Input `d` as a number
  Ｎη                                    Input `f` as a number
    Ｎζ                                  Input `b` as a number
                  ζ                     Input `b`
                 Ｘ                      Raised to power
                      θ                 Input `d`
                     ×                  Multiplied by
                        η               Input `f`
                       ⊖                Decremented
                    ÷                   Integer divided by
                          ζ             Input `b`
                         ⊖              Decremented
                   ⊕                    Incremented
                ÷                       Integer divided by
                            ζ           Input `b`
                           ⁻            Subtract
                               η        Input `f`
                              ‹         Is less than
                                ζ       Input `b`
                             ∧          Logical And
                                  ζ     Input `b`
                                 ›      Is greater than
                                   ²    Literal integer `2`
       ×                                Multiplied by
           θ                            Input `d`
          ×                             Multiplied by
             η                          Input `f`
            ⊖                           Decremented
         ﹪                              Modulo
               ζ                        Input `b`
              ⊖                         Decremented
        ⊕                               Incremented
      Ｉ                                 Cast to string
                                        Implicitly print

```
> 2 votes

# Answer
# JavaScript (ES7), 54 bytes

A port of loopy walt's xnor-optimized answer.

```
(d,f,b)=>~~(b**-~(d*--f/--b)/(b+(b<=f|b<2)))*(d*f%b+1)

```

Try it online!

---

# JavaScript (ES11), 50 bytes

An alternate version taking Bigints as input.

We have to use a ternary operator because we can't add a Boolean to a Bigint. This is however an opportunity to invert the sign of the division which allows to save one byte on the multiplication by just using `~`. And more importantly, we don't have to round the result of the division anymore.

```
(d,f,b)=>b**-~(d*--f/--b)/(b>f&b>1?-b:~b)*~(d*f%b)

```

Try it online!
> 2 votes

# Answer
# Haskell, 235 bytes

```
import Data.Bits
import Data.List
import Data.List.Ordered
o=0::Int
c d f b=length$fst$span(>[])$tail$scanl(\p n->nubSort$filter(all$(f>=).popCount)[sort$zipWith(.|.)q$bit<$>m|m<-permutations n,q<-p])[repeat o]$mapM id$[o..b-1]<$[1..d]

```

Try it online!

# Haskell, 251 bytes

```
import Data.Bits
import Data.List
import Data.List.Ordered
o=0::Int
c d f b=length$fst$break null$tail$scanl(\p n->nubSort$map sort$filter(all$(f>=).popCount)[zipWith(.|.)m q|m<-map(map bit)$permutations n,q<-p])[repeat o]$sequence$replicate d[o..b-1]

```

Try it online!
> 1 votes

# Answer
# Python3, 877 bytes

```
from numpy import*
from itertools import*
U=lambda D:[''.join(j)for k in permutations(D,len(D))for j in product(*k)]
I=lambda P,n,b:sorted({int(i,b)for i in P})[:n+1]==[*range(n+1)]
def F(d,f,b):
 q,R,S=[([['0']],0,[])],[0],[]
 while q:
  D,n,C=q.pop(0)
  if len(D)==d and all([f==len(i)for i in D]):R+=[n]
  N=base_repr(n+1,base=b).zfill(len(D))
  if N in C:q+=[(D,n+1,C)]
  else:
   if len(N)>len(D)and len(D)<d:D+=[['E']]
   p=U(D)
   for P in p:
    if P!=N and(P[:-1]==N[:-1]or P[1:]==N[1:]):
     V=N[0]if P[1:]==N[1:]else N[-1]
     D=[[j for j in i if j!='E']for i in D]
     if len(D[-1])<f:
      if(Y:=[*D[:-1],D[-1]+[V]])not in S and I(u:=U(Y),n+1,b):q+=[(Y,n+1,u)];S+=[Y]
     elif len(D)<d:
      if f>1 and(Y:=D+[['0',V]])not in S and I(u:=U(Y),n+1,b):q+=[(Y,n+1,u)];S+=[Y]
      if(Y:=D+[[V]])not in S and I(u:=U(Y),n+1,b):q+=[(Y,n+1,u)];S+=[Y]
 return max(R)+1

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 19 bytes

```
<*I<‰>`ŠmID¹2‚›P-÷*

```

Inputs in the order \\$f,d,b\\$.

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

Try it online or verify all test cases.

**Explanation:**

Formula: `(d*(f-1)%(b-1)+1)*((b**(d*(f-1)//(b-1)+1))//(b-(b>f)*(b>2)))`

```
<                   # Decrease the first (implicit) input `f` by 1
                    #  STACK: f-1
 *                  # Multiply it to the second (implicit) input `d`
                    #  STACK: d*(f-1)
    ‰               # Divmod it by
  I<                # the third input `b` minus 1
                    #  STACK: [d*(f-1)//(b-1), d*(f-1)%(b-1)]
     >              # Increase both values in the pair by 1 (let's call them [A,B])
                    #  STACK: [d*(f-1)//(b-1)+1, d*(f-1)%(b-1)+1]
      `             # Pop and push them separated to the stack
                    #  STACK: d*(f-1)//(b-1)+1, d*(f-1)%(b-1)+1
       Š            # Tripleswap the stack using the implicit third input `b`
                    #  STACK: d*(f-1)%(b-1)+1, b, d*(f-1)//(b-1)+1
        m           # Take `b` to the power `A`
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1)
         I          # Push the third input `b` again
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1), b
          D         # And again
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1), b, b
           ¹2‚      # Push pair [f,2]
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1), b, b, [f,2]
              ›     # Pop the copy of `b`, and check [b>f, b>2]
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1), b, [b>f,b>2]
               P    # Check if both are truthy by taking the product
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1), b, (b>f)*(b>2)
                -   # Decrease the other `b` by this 0 or 1
                    #  STACK: d*(f-1)%(b-1)+1, b**(d*(f-1)//(b-1)+1), b-(b>f)*(b>2)
                 ÷  # Integer-divide `b to the power A` by this
                    #  STACK: d*(f-1)%(b-1)+1, (b**(d*(f-1)//(b-1)+1))//(b-(b>f)*(b>2))
                  * # Multiply it to `B`
                    #  STACK: (d*(f-1)%(b-1)+1)*((b**(d*(f-1)//(b-1)+1))//(b-(b>f)*(b>2)))
                    # (after which the result is output implicitly)

```
> 0 votes

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


title: Is this a cube?

text:
# Question
Title: Is this a cube?
This challenge is a riff on Dion's challenge "Is this a rectangle?". The goal of this challenge is to write a program to decide whether or not some collection of tuples of integers represents a hypercube of some dimension.

### Background

A hypercube is a generalization of a square.

* A \\$0\\$-cube is a single point.
* A \\$1\\$-cube is a line segment.
* A \\$2\\$-cube is a square.
* A \\$3\\$-cube is an ordinary cube.
* An \\$n\\$-cube is a connected geometric object consisting of pairs of parallel line segments, perpendicular to each other and of the same length.

## Example

For example, if you are given the input \\$\\{(0, 4, 0, 9), (2, 2, -4, 9), (-2, 0, -6, 9), (-4, 2, -2, 9)\\}\\$, then you should return a truthy value because these four points define a \\$2\\$-cube (a square).

You are allowed to input the data in any reasonable format—but the computation needs to work regardless of the input order of the points.

An \\$n\\$ cube has \\$2^n\\$ vertices, so if the list of numbers does not contain \\$2^n\\$ numbers, you must return a falsey value.

## Challenge

This is a challenge, so shortest code wins.

## Test data

Cubes:

```
[(1,9,7,7)]
[(1),(2)]
[(9,1,9),(1,2,9)]
[(0,0,5),(0,1,5),(1,0,5),(1,1,5)]
[(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)]
[(0,0,0),(0,3,4),(0,-4,3),(0,-1,7),(5,0,0),(5,3,4),(5,-4,3),(5,-1,7)]

```

Non-cubes:

```
[(1,0,0),(0,1,0),(0,0,1),(1,1,1)]
[(0,0,0),(0,0,1),(0,1,0),(1,0,0)]
[(1,0,0),(0,1,0),(0,0,1)]
[(1,0,0,0,0),(0,1,0,0,0),(0,0,1,0,0),(0,0,1,1,1)]

```

If you'd like more test data, or if you'd like to *suggest* more test data, let me know.

# Answer
# APL (Dyalog Unicode), 44 bytes

```
{≡/((÷∘⊃⍨1↓⍋⌷¨⊂)⍤1∘.(+.×⍨-)⍨)¨⍵(,⍳2⍴⍨⌊2⍟≢⍵)}

```

Try it online!

the argument  is a vector of coordinate vectors

`,⍳2⍴⍨⌊2⍟≢⍵` build a hypercube as the cartesian product \\$\\{0,1\\}^{\left\lfloor \log\_2\left|\omega\right|\right\rfloor}\\$

`≡/(`*f*`)¨⍵(`..`)` evaluate *f* for  and the 01 hypercube, and test if they match

`∘.(+.×⍨-)⍨` matrix of pairwise distances

`(÷∘⊃⍨1↓⍋⌷¨⊂)⍤1` sort each row and divide by its second element
> 5 votes

# Answer
# Python, ~~262~~ \\$\cdots\\$ ~~305~~ 303 bytes

Saved a whopping 19 bytes thanks to dingledooper!!!

Added 118 bytes to fix a bug kindly pointed out by xnor, Peter Kagey and l4m2.

```
lambda l,R=range,L=len:(n:=L(l))<2or(d:=L(bin(n))-3)and(p:=sorted([sum((x-y)**2for x,y in zip(i,j))for i in l for j in l]))==[i*p[n]for i in R(d+2)for _ in R(2**d*math.comb(d,i))]and(K:=R(L(l[0])))and L({sum(([sum(l[i][j]for i in R(n))for j in K][j]-n*l[i][j])**2for j in K)for i in R(n)})<2
import math

```

Try it online!

Inputs a list of points and returns `True`/`False`.

**How**

Calculates the square of the distances between all possible pairs of points (including self-pairs and both \\$(p\_i,p\_j)\\$ and \\$(p\_j,p\_i)\\$ for all points \\$p\_j\\$ and \\$p\_i\\$ where \\$i\neq j\\$) and normalises them by the smallest non-zero square distance. For an \\$n\\$-cube we should then see a pattern of integers \\$i = 0,1,\dots, n\\$ each occurring \\$2^{n}{n\choose i}\\$ times. This corresponds with the \\$0\\$s for all the self-pairs, and the square of the lengths of all the sides being \\$a^2\\$, and the square of the lengths of all the diagonals being \\$2a^2, 3a^2,\dots, na^2\\$.

**Correction**

Also checks that the given vertices are all equidistant from the centre of mass.
> 4 votes

# Answer
# Python 3, 339 338

```
lambda P:1==L(P)or P in map(g,permutations(P))
from itertools import*
L=len
Z=zip
D=lambda a,b:sum(x*y for x,y in Z(a,b))
def g(Q):B=[[x-y for x,y in Z(p,Q[0])]for p in Q[3-L(bin(L(Q))):]];return any(D(a,b)or D(a,a)-D(b,b)for a,b in combinations(B,2))or{tuple(x+sum(y)for x,y in Z(Q[0],Z(*C)))for C in product(*[(p,(0,)*L(p))for p in B])}

```

Try it online!

Takes a `set` of points as input.

Pseudocode explanation:

```
def f(points):
    let n = log_2(|points|)
    for each permutation Q of the points:
        let q be the first point in Q
        let B be the following n points, with q subtracted from each
        if all pairs of points in B are orthogonal and have equal magnitude:
            let S be the set of points which can be obtained by summing q and any subset of B
            if S == points: return True
    return False

```

Can definitely be golfed further but it's bedtime.
> 2 votes

# Answer
# JavaScript (Node.js), 182 bytes

```
x=>(g=(q=(x,z)=>x.flatMap(a=>x.flatMap(c=>x.map(b=>z*a.reduce((s,v,i)=>s+(v-b[i])**2+(v-c[i])**2,0)))).sort((a,b)=>a-b))(x,K=x.length))+''==q(x.map(_=>[...(K++).toString(2)]),g[K]|0)

```

Try it online!

Check sums of length squares of A-B-C, where A,B,C can be same
> 1 votes

# Answer
# JavaScript (Node.js), 258 bytes

```
x=>(q=(x,z)=>g=x.flatMap(a=>x.map(b=>z*a.reduce((s,v,i)=>s+(v-b[i])**2,0))).sort((a,b)=>b-a))([...x,x[0].map((_,i)=>x.reduce((s,v)=>s+v[i],P=0)/(K=x.length))],K)+''==q([x.slice(D=~Math.log2(K)).map(_=>!P++||.5),...x.map(_=>[...(K++).toString(2)])],g[0]/~D|0)

```

Try it online!

Similar to Noodle9's answer, but generate another square to compare rather than use formula and add midpoint like normal ones
> 1 votes

# Answer
# Haskell, 139 bytes

```
import Data.List
import Data.List.Ordered
c p=has[(2^n,n*2^n)|n<-[0..]](length p,length$group(sort[sum$(^2)<$>zipWith(-)x y|x<-p,y<-p])!!1)

```

Try it online!
> 1 votes

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


title: Iterate your way to a fraction

text:
# Question
Title: Iterate your way to a fraction
I recently learned from a comment by MathOverflow user pregunton that it is possible to enumerate all rational numbers using iterated maps of the form \\$f(x) = x+1\\$ or \\$\displaystyle g(x) = -\frac 1x\\$, starting from \\$0\\$.

For example, $$0 \overset{f}{\mapsto} 1 \overset{f}{\mapsto} 2 \overset{g}{\mapsto} -\frac12 \overset{f}{\mapsto} \frac12 \overset{f}{\mapsto} \frac 32 \overset{g}{\mapsto} -\frac23 \overset{f}{\mapsto} \frac 13.$$

That is, $$ \frac13 = f(g(f(f(g(f(f(0))))))) = f\circ g\circ f\circ f\circ g\circ f\circ f(0).$$ This is an example of a *shortest path of iterated maps* to reach \\$\frac13\\$; every path from \\$0\\$ to \\$\frac13\\$ requires at least seven steps.

---

## Challenge

Your challenge is to take two integers, `n` and `d`, and return a string of `f`'s and `g`'s that represents a shortest path of iterated maps from \\$0\\$ to \\$\displaystyle\frac nd\\$.

This is a , so shortest code wins.

#### Example

```
  n |  d | sequence of maps
----+----+-----------------
  1 |  3 | fgffgff
  3 |  1 | fff
  8 |  2 | ffff
  1 | -3 | gfff
  2 |  3 | fgfff
  0 |  9 | [empty string]
  1 |  1 | f
  2 |  1 | ff
  1 | -2 | gff
 -1 | -2 | fgff
  6 |  4 | ffgff
 -2 |  3 | gffgff
  8 |  9 | fgfffffffff

```

# Answer
# Nibbles, 15.5 bytes

```
`.~$@?*@$~-@__*~@$$=`$*@$"fg "

```

That's 31 nibbles at half a byte each in the binary form.

This is based on the python answer although I found an iterative solution shorter. It felt kind of awkward still though.

```
`. ~$@      Iterate while unique, starting with the tuple $ @ (which is the input arguments)
  ? *@$     if product of values > 0
    ~-@_ _  then ($-@, @) since true clause has condition's value put in $ (unused here though)
    *~@ $   else (-1*@, $)
  $         the second value of the tuple from the if (tuple's aren't returned as first class things but splat into the context and must be reconstructed, normally very concise but here a bit awkward

```

The above code computes the sequences of numerators and denominators, now we just need to convert it to f and g. Note that it has a few extra terms since it didn't stop being unique until after the solution was found. Luckily n\*d is 0 in that case so we can use that to map it to a space. The below code is implicitly done via a map.

```
= `$ *@$   subscript using signum of n*d
  "fg "    into this list (0 is the last since 1 based).

```

Call it like `nibbles filename.nbl 1 3` (Nibbles isn't on TIO yet).

Note that this will also output 4 spaces after the answer, you could remove it by doing a filter, this would add two nibbles or 1 byte.
> 5 votes

# Answer
# Python, 54 bytes (-1 @Jonathan Allan, -1 me)

```
f=lambda n,d:n and'gf'[p:=n*d>0]+f(p*n-d,[n,d][p])or''
```

Attempt This Online!

#### Old Python, 56 bytes (@tsh)

```
f=lambda n,d:n*d<0and'g'+f(-d,n)or n and'f'+f(n-d,d)or''
```

Attempt This Online!

#### Old Python, 57 bytes

```
f=lambda n,d:n//d<0and'g'+f(-d,n)or n and'f'+f(n-d,d)or''
```

Attempt This Online!

Not 100% sure this is correct. Works on all test cases, though. It's kind of a Euclidean algorithm with overshoot.

#### Towards a proof of correctness

The group of transformations generated by f and g is called the Modular group. There is quite a bit of interesting theory but the one thing that seems relevant to us is that gg and gfgfgf are a "complete set of relations" and that the modular group is the "free product of the cyclic groups generated by g and h:=gf". This means that any element of the modular group can be uniquely written as g's alternating with either h or hh. Transforming back to f's and g's gh becomes f and ghh becomes fgf, so except for the left end which can be h or hh, i.e. gf or gfgf all valid representations are exactly the words with g's separated by at least 2 f's. And we can check that the algorithm indeed produces such words.

So, are we done? I'm not sure. What's missing is that I don't know how exactly the rationals and the modular group are related. It may well be that two distinct group elements move 0 to the same rational which would send us back quite a bit if not all the way to square 1.
> 13 votes

# Answer
# JavaScript (Node.js), 53 bytes

```
f=(n,d,p='',...e)=>n?f(...e,-d,n,p+'g',n-d,d,p+'f'):p

```

Try it online!

Stackoverflow on last testcase.
> 7 votes

# Answer
# Ruby, 45 bytes

```
f=->n,d{n==0?"":n/d<0??g+f[-d,n]:?f+f[n-d,d]}

```

Try it online!

Use as `f[n,d]`

basically a port of loopy walt's python answer
> 6 votes

# Answer
# Haskell,  ~~44~~  42 bytes

```
0#d=[]
n#d|n*d<0='g':(-d)#n|m<-n-d='f':m#d

```

adaption of the python solution, using guards. Ungolfing barely changes it, just adding whitespace:

```
0#d          = []
n#d | n*d<0  = 'g':(-d)#n
    | m<-n-d = 'f':m#d

```

Try it online!

-2 Bytes thanks to xnor, TIO link also thanks to xnor
> 5 votes

# Answer
# JavaScript (ES6), 90 bytes

A naive algorithm trying all sequences of length \\$k\\$, starting with \\$k=0\\$ and incrementing \\$k\\$ until a solution is found.

Expects `(n)(d)`. Returns an empty array instead of an empty string.

```
n=>F=(d,k)=>(g=(k,o=[],N=n,D=d)=>k--?g(k,o+'f',N-D,D)||g(k,o+'g',-D,N):!N&&o)(k)||F(d,-~k)

```

Try it online!

---

# JavaScript (ES6), 44 bytes

Assuming loopy walt's method is valid (and it most probably is).

Expects `(n,d)`.

```
f=(n,d)=>n*d<0?'g'+f(-d,n):n?'f'+f(n-d,d):''

```

Try it online!
> 4 votes

# Answer
# Pari/GP, 52 bytes

```
t(n,d)=if(n/d>0,Str(f,t(n-d,d)),n,Str(g,t(-d,n)),"")

```

Try it online!

A port of @loopy walt's Python answer.

Shorter (46 bytes) if we can take a rational number as input:

```
t(r)=if(r>0,Str(f,t(r-1)),r,Str(g,t(-1/r)),"")

```

Try it online!
> 4 votes

# Answer
# C (gcc), 104 bytes

```
n=1;d=3;o;main(){if(d<0){n=-n;d=-d;}while(n){if(n<0){o=d;d=-n;n=o;printf("g");}else{n-=d;printf("f");}}}

```

Try it online!
> 4 votes

# Answer
# Charcoal, ~~65~~ ~~62~~ ~~52~~ 48 bytes

```
ＮθＮη¿θＷφ«≔θφ≔ηζ⊞υωＰ←⍘ＬυgfＦ⮌↨Ｌυ²¿κ≧⁻ζφ«≔ζε≔φζ≔±εφ

```

Try it online! Link is to verbose version of code. Feels like it should be a bit shorter. Explanation:

```
ＮθＮη

```

Input `n` and `d`.

```
¿θＷφ«

```

Do nothing if `n=0`, otherwise loop until a reverse path to zero is found. (This loop uses the variable `f` which is predefined to `1000`, thus ensuring the loop happens at least once; it saves a byte over saving `n` and using `while (n)`.)

```
≔θφ≔ηζ

```

Make new copies of `n` and `d`.

```
⊞υω

```

Increment the length of the predefined empty list.

```
Ｐ←⍘Ｌυgf

```

Replace the canvas with the length interpreted as a base 2 string of `f`s and `g`s (with `f=1` and `g=0`). The string is reversed so that the last letter is always `f`.

```
Ｆ⮌↨Ｌυ²

```

Loop over the base 2 digits in reverse.

```
¿κ≧⁻ζφ

```

For `1`s undo the `f` step.

```
«≔ζε≔φζ≔±εφ

```

Otherwise undo the `g` step.

Switching to undoing steps saved me 10 bytes. It's possible that deciding whether to undo an `f` or `g` step based on the sign of the current fraction suffices to produce a minimal result. If that's true then the solution would only be 31 bytes:

```
ＮθＮηＷθ¿›×θη⁰«f≧⁻ηθ»«g≔ηζ≔θη≔±ζθ

```

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

```
ＮθＮη

```

Input `n` and `d`.

```
Ｗθ

```

Repeat until `n=0`.

```
¿›×θη⁰«

```

If `n/d` is positive, then...

```
f≧⁻ηθ

```

... output an `f` and subtract `d` from `n`.

```
»«

```

Otherwise...

```
g≔ηζ≔θη≔±ζθ

```

... output a `g`, switch `n` and `d`, and negate `n`.
> 3 votes

# Answer
# 05AB1E, 33 bytes

```
∞ε„fg©sã}˜õš.Δ®'>„z(‚‡0s.VI`/α₄z‹

```

Naive brute-force approach. Outputs in reversed order. If this is not allowed, a trailing `}R` will have to be added and it would be 35 bytes instead, making the approach below 1 byte shorter.

Try it online or verify all test cases.

A port of *@loopyWalt*'s second Python answer is **34 bytes**, but it outputs in the correct order:

```
"ÐPdi¬ĀiÆ0ǝ®.V'fìëõë`s(‚®.V'gì"©.V

```

Try it online or verify all test cases.

**Explanation:**

```
∞                     # Push an infinite positive list: [1,2,3,...]
 ε                    # Map over each integer:
  „fg                 #  Push string "fg"
     ©                #  Store it in variable `®` (without popping)
      s               #  Swap so the current integer is at the top
       ã              #  Get the cartesian product
  }˜                  # After the map: flatten the list of lists
    õš                # Prepend an empty string
.Δ                    # Then find the first value which is truthy for:
  ®                   #  Push "fg" from variable `®`
   '>                '#  Push string ">"
     „z(              #  Push string "z("
        ‚             #  Pair them together: [">","z("]
         ‡            #  Transliterate all "f" to ">" and "g" to "z("
          0           #  Push 0
           s          #  Swap so the string is at the top again
            .V        #  Evaluate as 05AB1E code:
                      #   `>`: Increase the value by 1
                      #   `z(`: `z` will push 1/value, `(` will negate it
              I       #  Push the input-pair: [n,d]
               `      #  Pop and push `n` and `d` separated to the stack
                /     #  Divide `n` by `d`
                 α    #  Get the absolute difference between the two values
                    ‹ #  Check if this is smaller than
                  ₄z  #  1/1000
                      #  (`α₄z‹` can't be `Q` due to floating point inaccuracies)
                      # (after which the result is output implicitly)

```

```
"..."                 # Push the recursive string defined below
     ©                # Store this string in variable `®` (without popping)
      .V              # Evaluate it as 05AB1E code

Ð                     # Triplicate the current pair [n,d]
                      # (which will be the implicit input in the first call)
   i                  # If
 P                    # n*d (product of the pair)
  d                   # is >= 0:
      i               #  If
    ¬                 #  n (without popping the pair)
     Ā                #  is not 0:
       Æ              #   Push n-d (reduce by subtracting)
         ǝ            #   And insert this n-d back into the pair
        0             #   at index 0: [n-d,d]
          ®.V         #   Then do a recursive call
             'fì     '#   And prepend "f" to that
      ë               #  Else:
       õ              #   Push an empty string ""
   ë                  # Else:
    `                 #  Pop and push `n` and `d` separated to the stack
     s                #  Swap the two values on the stack
      (               #  Negate `n`
       ‚              #  Pair them back together: [d,-n]
        ®.V           #  Then do a recursive call
           'gì       '#  And prepend "g" to that
                      # (after which the result is output implicitly)

```
> 3 votes

# Answer
# Stax, ~~18~~ 16 bytes

```
ÿ☺╨K▼▓¡s'↓♫[╣♥╬╩

```

Run and debug it

Pretty convenient with the rational type.
> 3 votes

# Answer
# Python3, 192 bytes:

```
lambda n,d:f([(0,n/float(d),'')])
f=lambda d:r[0][-1]if(r:=[i for i in d if round(i[0],4)==round(i[1],4)])else f([j for a,b,c in d for j in[(a+1,b,'f'+c)]+([(-1/(1.0*a),b,'g'+c)]if a else[])])

```

Try it online!
> 2 votes

# Answer
# APL (Dyalog Extended), 48 bytes

Basic bruteforce approach, expects index origin 0.

```
f←-⍨\⍢⌽
g←-@0⌽
⌽o⊣1+⍣{0=⊃⍎⍕t,⍨↓⍪o∘←'gf'[⊤⍵]}⍱t←⎕

```

Try it online!
> 2 votes

# Answer
# C (clang), <sup>~~59~~ \\$\cdots\\$ ~~53~~</sup> 52 bytes

```
z;f(n,d){z=n*d>=0;n&&f(z*n-d,z?d:n,putchar(103-z));}

```

Try it online!

*Port of loopy walt's Python answer.*
*Saved ~~5~~ 6 bytes thanks to ceilingcat!!!*
*Saved a byte thanks to dingledooper!!!*

Inputs integers \\$n\\$ and \\$d\\$.
Outputs string of `f`'s and `g`'s that represents a shortest path of iterated maps from \\$0\\$ to \\$\frac{n}{d}\\$.
> 2 votes

# Answer
# Wolfram Language (Mathematica), 139 bytes

```
(m=1;f=If[#3<m,If[#1!=0,Do[#0[{#1-1,-1/#1}[[k]],Append[#2,k],#3+1],{k,2}],Throw@#2]]&;While[(r=Catch[f[#1/#2,{},1]])==Null&&#1!=0,m+=1];r)&

```

Try it online!

Reverse recursive approach.
We start with given fraction and recursively apply reverse operations until we reach `0`.
Output is array with `1` for \\$f\\$ and `2` for \\$g\\$ or `Null` if `n==0`.

The code is not optimal (the same results are used several times), but optimization will increase the length of the code.
I'll try golfing it more, sure it's possible.

Ungolfed version self-explained:

```
Clear[recurse, main];
recurse[x_, arr_, i_, max_] :=
  If[i < max,
   If[x != 0,
    Do[recurse[{x - 1, -1/x}[[k]], Append[arr, k], i + 1, max],
     {k, 2}],
    Throw@arr
    ]];

main[n_, d_] := Module[{max = 1, res = Null},
   While[res == Null && n != 0,
    res = Catch[recurse[n/d, {}, 1, max]];
    max += 1
    ]; res];

```
> 1 votes

# Answer
# Scala, ~~83~~ 78 bytes

Saved 5 bytes thanks to the comment of @ceilingcat

---

Golfed version. Try it online!

```
def c(n:Int,d:Int):String=if(n*d<0)'g'+c(-d,n)else if(n*d<1)""else'f'+c(n-d,d)

```

Ungolfed version. Try it online!

```
object Main extends App {
  def calc(n: Int, d: Int): String = {
    if (n == 0 || d == 0) ""
    else {
      (n * d) match {
        case x if x < 0 => 'g' + calc(-d, n)
        case _ => {
          val m = n - d
          'f' + calc(m, d)
        }
      }
    }
  }

  println(calc(9, 7))
}

```
> 1 votes

# Answer
# SAS 101,

"*Generating Ratinal Numbers in SAS 4GL - 101*" :-D

Inspired by loopy walt answer I decided to make SAS 4GL version.

The code:

```
data;set;do while(n);t=d;if(n*d<0)then do;put"g"@;d=n;n=-t;end;else do;put"f"@;n=n-d;end;end;put;run;

```

SAS is quite "talkative" by all those `if`s, `then`s, `do`s, `end`s and `else`s so, even tough I did my best to "boil" bytes down, I ended up on 101.

Explanation:

I don't like stack overflows so instead recursion I went with iterative approach.

It is SAS 4GL so the the standard input in form of a SAS dataset is expected (I added some extra test cases):

```
data i;
input n d;
cards;
1     3
3     1
16    4
8     2
4     1
1    -3
2     3
0     9
0     3
0     1
1     1
2     1
1    -2
-1    -2
6     4
-2     3
8     9
17    42
17   -42
17    303
42    303
99    100
990   1000
999   1002
999  -1002
1 11111
1 2
2 4
4 8
;
run;

```

Human readable code:

```
data _null_; /* 0) */
  set i; /* expect input data set 1) */
  put n= d= @; /* added just for printing */

  do while(n); /* while numerator is not 0 */
    x=d;
    if (n*d<0)
      then /* for negative print "g", then negate and flip fraction  */
        do;
          put "g" @;
          d = n;
          n = -x;
        end;
      else /* for positive print "f", then substract 1 from fraction  */
        do;
          put "f" @;
          n = n-d;
        end;
  end;
  put; /* add new line character at the end of printout 2) */
run;

```

*Footnotes:*

*0) turn of production of output dataset*

*1) the `set` statement takes as input the last created data set, so code generating dataset `i` has to be executed just before.*

*2) the last `put;` can be skipped if the input dataset has only 1 observation what reduces length by 4 bytes to 97.*

Log output:

```
n=1 d=3 fgffgff
n=3 d=1 fff
n=16 d=4 ffff
n=8 d=2 ffff
n=4 d=1 ffff
n=1 d=-3 gfff
n=2 d=3 fgfff
n=0 d=9
n=0 d=3
n=0 d=1
n=1 d=1 f
n=2 d=1 ff
n=1 d=-2 gff
n=-1 d=-2 fgff
n=6 d=4 ffgff
n=-2 d=3 gffgff
n=8 d=9 fgfffffffff
n=17 d=42 fgffgffffgffgffgffgffgffgffgff
n=17 d=-42 gfffgffgfffffffff
n=17 d=303 fgffgffgffgffgffgffgffgffgffgffgffgffgffgffgffgffgfffgffgffgffgfffgff
n=42 d=303 fgffgffgffgffgffgffgffffffgfff
n=99 d=100 fgffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
n=990 d=1000 fgffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
n=999 d=1002 fgf[ 332 "f" hidden for readability ]f
n=999 d=-1002 gff[ 331 "gff" hidden for readability ]gff
n=1 d=11111 f[ 11109 "gff" hidden for readability ]gff
n=1 d=2 fgff
n=2 d=4 fgff
n=4 d=8 fgff
NOTE: There were 29 observations read from the data set WORK.I.
NOTE: DATA statement used (Total process time):
      real time           0.02 seconds
      cpu time            0.03 seconds

```

*A small comment at the end:*

We are in a group of functions with composition.

Function: \\$ z(x) = g(f(g(f(g(x))))) = x{-}1 \\$ is an inverse of \\$f\\$ (\\$f(z(x))=x\\$, \\$z(f(x))=x\\$) and \\$g\\$ is inverse of itself (\\$g(g(x))=x\\$)

So a path from \\$0\\$ to \\$\frac{n}{d}\\$ (assuming frac is reduced) of the form:

$$ \frac13 = f(g(f(f(g(f(f(0))))))) $$

can be "walked back" using inverses of \\$f\\$ and \\$g\\$

$$ 0 = z(z(g(z(z(g(z(\frac13))))))) $$

Which is "base" for the algorithm: "*1) take a fraction, 2) if the fraction is negative "flip it"(negate and inverse) else subtract 1 from it, 4) if fraction is 0 stop else got to 1)*"
> 0 votes

---
Tags: code-golf, math, combinatorics, rational-numbers
---


# Question
Title: Convert a decimal to a fraction, approximately
Take the decimal number \\$0.70710678\\$. As a fraction, it'd be \\$\frac{70710678}{100000000}\\$, which simplifies to \\$\frac{35355339}{50000000}\\$. If you were to make the denominator \\$1\\$, the closest fraction is \\$\frac{1}{1}\\$. With \\$2\\$, it'd be \\$\frac{1}{2}\\$, and with \\$3\\$ it's \\$\frac{2}{3}\\$. Because \\$0.\bar{6}\\$ is closer to \\$0.70710678\\$ than \\$\frac{3}{4}\\$ or \\$\frac{4}{5}\\$, it would still be the closest with a maximum denominator up to (and including) \\$6\\$.

### Task

There are two inputs: a decimal, and a maximum denominator.

The first input consists of a number \\$n\\$ as input, where \\$0\le n\<1\\$, and the fractional part is represented with a decimal (although not necessarily using base 10). This can be represented as a floating point number, an integer representing a multiple of \\$10^{-8}\\$ (or some other sufficiently smaller number), a string representation of the number, or any other reasonable format.

The second input is an integer \\$n\ge1\\$, also taken in any reasonable format.

The output should be a fraction, with a denominator \\$d\le n\\$, where \\$n\\$ is the second input. This should be the closest fraction to the inputted decimal that is possible with the restrictions placed on the denominator. If there are multiple which are equally close (or equal to the inputted number), the one with the smallest denominator should be chosen. If there are two with the same denominator which are equidistant, either are acceptable.

The outputted fraction can be represented in any reasonable format, as long as it consists of a numerator and denominator, both being natural numbers.

### Test cases

```
0.7         4   ->   2 / 3
0.25285     15  ->   1 / 4
0.1         10  ->   1 / 10
0.1         5   ->   0 / 1
0.68888889  60  ->  31 / 45
0.68888889  30  ->  20 / 29
0.0         2   ->   0 / 1
0.99999999  99  ->   1 / 1

```

### Other

This is , shortest answer in bytes per language wins!

# Answer
# Scratch 3.0, 45 blocks/254 bytes

As SB Syntax:

```
define(n)(d)
set[A v]to(0
set[D v]to(d
set[i v]to(0
repeat((n)+(1
set[j v]to(0
repeat((n)+(1
set[r v]to((i)/(j
if<(D)>([abs v]of((r)-(D)))>then
set[A v]to(join(i)(join(/)(j
set[D v]to([abs v]of((r)-(D
end
set[j v]to((j)+(1
end
set[i v]to((i)+(1
end
say(A

```

Try it on Scratch!

Just wouldn't be right if I didn't do this in Scratch.

## Explained

```
define(n)(d) // Define an empty name function with parameters `n` (the denominator) and `d` (the decimal to fractionify)
set[D v]to(d // This will store the current absolute difference between potential fraction and actual decimal
set[i v]to(0 // outer-cartesian-loop variable
repeat((n)+(1
set[j v]to(0 // inner-cartesian-loop variable
repeat((n)+(1 // simulate cartesian product of range(0, n+1) and range(0, n+1)
set[r v]to((i)/(j // divide i / j
if<(D)>([abs v]of((r)-(D)))>then // if the difference between (i/j) and d is smaller than the current smallest difference
set[A v]to(join(i)(join(/)(j // update answer and difference
set[D v]to([abs v]of((r)-(D
end
set[j v]to((j)+(1
end
set[i v]to((i)+(1
end
say(A // output answer

```
> 10 votes

# Answer
# Husk, ~~12~~ 10 bytes

```
◄oa-⁰´×/ŀ→

```

Try it online!

is absolute difference, but doesn't seem to work for floats. So `oa-` is used.

-2 bytes from Leo.

## Explanation

```
◄oa-⁰´×/ŀ→ Inputs: decimal → ⁰, max denominator → implicit
        ŀ→ range 0..denominator
     ´×/   convert all possible pairs to fractions
◄o         min by
  a-⁰      absolute difference with the decimal

```
> 8 votes

# Answer
# 05AB1E, 10 bytes

```
ÝD¦âΣ`/α}¬

```

Try it online!

## Explanation

```
Ý          # [0 .. input]
 D         # Duplicate
  ¦        # Tail -> [1 .. input]
   â       # Cartesian product
    Σ   }  # Sort by
       α   # Absolute difference between
           # Input 2
     `/    # and numerator / denominator
         ¬ # Head

```
> 6 votes

# Answer
# Python 3, ~~97~~ 90 bytes

```
def f(n,k,a=[1]):
 while k:p=round(n*k);j=abs(p/k-n);a=[a,(j,p,k)][j<=a[0]];k-=1
 return a

```

Try it online!

`round(n*k)` gets the closest numerator for a given denominator `k`. `abs(p/k-n)` calculates the absolute value between this fraction and the input fraction `n`. If this is the best option so far, then update the answer accordingly.

Outputs three values: the absolute difference, the numerator and the denominator respectively.

*thanks to Noodle9 for -7 bytes*
> 5 votes

# Answer
# , 21 bytes

```
(0{]/:&,|@-)%/~@i.@>:

```

Try it online!

Takes float as left input, max denominator as right input.

* `%/~@i.@>:` Creates "division table" for all pairs 0 to max denominator.
* `|@-` Elementwise differences between those table values and the target float.
* `]/:&,` Sort the table `/:` according to those differences after flattening both `&,`.
* `0{` Return the first item in the sorted list.
> 5 votes

# Answer
# JavaScript (ES7), 64 bytes

Expects `(value)(max_denominator)`. Returns `[numerator, denominator]`.

```
v=>g=(d,e)=>d?g(d-1,(E=((q=v*d+.5|0)/d-v)**2)>e?e:(r=[q,d],E)):r

```

Try it online!

### Commented

```
v =>                     // outer function taking the float value v
g = (d, e) =>            // inner recursive function taking the maximum denominator d
                         // and the current minimum error e, initially undefined
  d ?                    // if d is not equal to 0:
    g(                   //   do a recursive call:
      d - 1, (           //     decrement d
        E = (            //     compute the new error E = (q / d - v)²
          (q = v * d     //     where q is round(v * d)
               + .5 | 0) //
          / d - v        //
        ) ** 2           //     it's shorter to square than to use Math.abs()
      )                  //
      > e ?              //     if E is greater than e (always false if e is still
                         //     undefined):
        e                //       pass e unchanged
      :                  //     else:
        (r = [q, d], E)  //       save the new result [q, d] in r and pass E
    )                    //   end of recursive call
  :                      // else:
    r                    //   return the final result

```
> 5 votes

# Answer
# Jelly, 9 bytes

```
Żpḷ÷/ạ¥ÞḢ

```

Try it online!

Verify all test cases

Note that this selects the fraction with the smallest *numerator*, and I'm not completely sure if it's always also the one with the smallest denominator.

Takes the maximum denominator as the first argument and the float as the second argument.

## Explanation

```
Żpḷ÷/ạ¥ÞḢ   Main dyadic link, taking m and x
Ż           Range [0..m]
 p          Cartesian product with
  ḷ         m, implicitly converted to the range [1..m]
       Þ    Sort by
      ¥     (
   ÷/         Divide the two numbers
     ạ        Absolute difference with x
      ¥     )
        Ḣ   Head

```
> 5 votes

# Answer
# Wolfram Language, ~~62~~ 57 bytes

-3 bytes thanks to J42161217.

```
MinimalBy[Join@@Array[Divide,{#,#}+1,0],a|->Abs[a-#2],1]&

```

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

Does the brute-force method of generating every possible fraction and taking the one closest to the given number. I previously had a solution using Convergents, but it failed for inputs like `0.1` where, because of the language accounting for inexact numbers, the closest fraction wouldn't appear in the list.
> 4 votes

# Answer
# Vyxal, 69 bitsv2, 8.625 bytes

```
ʁ:ḢẊµƒ/⁰ε;h

```

Try it Online!

A port of the 05AB1E answer updated to 2.6+ and vyncoded.

## Explained

```
ʁ:ḢẊµƒ/⁰ε;h
ʁ:         # Push two copies of the range [0, input)
  Ḣ        # on one of those copies, remove the first element
   Ẋ       # Take the cartesian product of these two lists
    µ...;  # And sort this by:
     ƒ/⁰ε  # the absolute difference between the second input and the item reduced by division
         h # output the first item

```
> 4 votes

# Answer
# PowerShell, 83 bytes

```
param($n,$d)1..$d|%{0..($x=$_)|%{@{n=$_;d=$x}}}|sort{[Math]::Abs($_.n/$_.d-$n)}-t 1

```

Try it online!
> 4 votes

# Answer
# Excel, 72 bytes

```
=LET(a,SEQUENCE(B1),x,ROUND(A1*a,),INDEX(SORTBY(x&"/"&a,ABS(x/a-A1)),1))

```
> 4 votes

# Answer
# JavaScript (V8), 81 bytes

```
n=>k=>eval('for(a=0,b=M=1;b<=k;(m=a/b<n?n-a++/b:a/b++-n)<M&&[R=P,M=m])P=[a,b];R')

```

Try it online!

Maybe there are edge cases which failed due to floating point errors. But it at least pass all testcases given by OP.
> 3 votes

# Answer
# Charcoal, 27 bytes

```
ＮθＦＮＦ⁺²ι⊞υ⟦↔⁻∕κ⊕ιθκ⊕ι⟧Ｉ✂⌊υ¹

```

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

```
Ｎθ

```

Input `n`.

```
ＦＮ

```

Input the maximum denominator and loop up to it. (The actual denominator is 1 more than the loop index.)

```
Ｆ⁺²ι

```

Loop over the possible numerators.

```
⊞υ⟦↔⁻∕κ⊕ιθκ⊕ι⟧

```

Calculate the error and save the numerator and denominator with it.

```
Ｉ✂⌊υ¹

```

Output the numerator and denominator with the smallest error (in the case of a tie, the smallest numerator wins).
> 3 votes

# Answer
# JavaScript (ES6), 63 bytes

```
c=>f=(d,M)=>d?f(d-1,M>(N=(.5-d*c%1)**2)?M:(s=d,N)):[c*s+.5|0,s]

```

Like this answer, expects `(value)(max_denominator)`, and returns `[numerator, denominator]`.

Here's how it works:

```
c=>                          // the decimal - this will not change
  f=(                        // the inner recursive function
    d,                       // the max denominator. We will decrement this to loop
    M                        // the "error" (with a twist)
  )=>
    d?                       // if d is nonzero, we're still recursing
      f(d-1,                 // call f with the new denominator we're testing
        M>                   // the bigger M is, the closer d*c is to an integer
          (N=                // we'll test the error and save it in N in case we need it
            (.5-d*c%1)**2    // the error (with the twist); the closer d*c to an integer, the
                             // closer d*c%1 to 0 or 1, the closer .5-d*c%1 to .5, the bigger
                             // (.5-d*c%1)**2 is. This means; bigger "error" is better
          )
          ?M                 // if M is bigger than the newly checked error, continue with M
          :(                 // otherwise,
            s=d,             // save that denominator in s,
            N                // continue with the new error (that we saved in N)
          )
        )
    :                        // if d is zero, we've checked all denominators so we're done
    [c*s+.5|0,               // return the numerator (which is just c*s rounded to the nearest integer)
    s]                       // and the denominator, which we saved in s

```
> 3 votes

# Answer
# , 61 bytes

```
function(n,d,a=round(n*1:d))c(a[i<-which.min((a/1:d-n)^2)],i)

```

Try it online!
> 3 votes

# Answer
# JavaScript (V8), 93 bytes

```
(d,m)=>eval("for(i=1,b=m;i<=m;i++)n=Math.round(d*i),w=Math.abs(d-n/i),w<b?[b=w,x=[n,i]]:0;x")

```

Try it online!

**Explanation:**

Fairly straighforward approach. Most of the work is done by a `for` loop, wrapped in an `eval` statement. This saves bytes, as it's shorter than wrapping it in `{}` (which requires `return`).

During the `for` loop (all iterations are denominators from `1` to `m`), four things happen:

* `n` is set to the closest numerator
* `w` is set to the distance between the fraction and the `d` (the first number)
* `w` is compared with the previous best, `b` (initially `Infinity`)
* If `w` is less than `b`, `b` takes `w`'s value and `x` (the output) becomes the outputted fraction
> 2 votes

# Answer
# Haskell, 100 bytes

```
u=10^8
a#b|b!!0<a!!0=b|1>0=a
n!m=tail$foldl1(#)[[min o$u-o,div(n*d+o)u,d]|d<-[1..m],let o=n*d`mod`u]

```

Try it online!

* input as 8 digits of the decimal part of n.
* output a \[ numerator, denominator \] list.

a#b selects a or b (which are \[distance to closest 10^8 multiple, numerator , denominator\] ) based on minimum distance.

n!m computes every \[dist, num, den\] from 1 to m ,
then finds closest fraction folding by # and return only \[num,den\]
> 2 votes

# Answer
# Julia 1.7, 37 bytes

```
x|n=argmin(y->(x-y)^2,(0:n).//(1:n)')

```

Attempt This Online!

`argmin(f, domain)` needs julia 1.7 or later
> 2 votes

# Answer
# Thunno 2 `h`, 10 bytes

```
LDḣṖÞẸ/¹-A

```

Attempt This Online!

Port of user100947's 05AB1E answer.

#### Explanation

```
LDḣṖÞẸ/¹-A  # Implicit input
LD          # Push [0..input) and duplicate
  ḣṖ        # Cartesian product of [0..input) with [1..input)
    Þ       # Sort by:
     Ẹ/     #  Dump and divide
       ¹-A  #  Absolute difference with second input
            # Implicit output of first item

```
> 2 votes

---
Tags: code-golf, math, rational-numbers
---