text:
Exponentiation to multiplication to addition
Multiplication between 2 integers can be reduced into a series of addition like so
3 * 5 = 3 + 3 + 3 + 3 + 3 = 5 + 5 + 5

Exponentiation (raising a to the power b) can also be reduced into a series of multiplications:
5 ^ 3 = 5 * 5 * 5

Therefore, exponentiation can be reduced into a series of additions, by creating a multiplication expression, then into a series of additions. For example, 5 ^ 3 (5 cubed) can be rewritten as
5 ^ 3 = 5 * 5 * 5
      = (5 + 5 + 5 + 5 + 5) * 5
      = (5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5 + 5)
      = 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5

Your task is, given expressions added together consisting of exponentiation, multiplication and addition, reduce it to the shortest series of additions. The "shortest" expression is defined as the expression with the fewest number of + symbols, still using only one of the two numbers in the original expression. For example, the shortest expression of 10 * 2 is 10 + 10.
The numbers involved in the input will all be positive integers, and the expression will consist of only + (addition), * (multiplication) and ^ (exponentiation), along with integers and brackets (()) to indicate precedence.
The output should consist of positive integers and + symbols only. You shouldn't output the individual steps of the reductions, just the final output. The output may not consist of any numbers that don't appear in the input. However, you may use any 3 distinct symbols instead of +*^, but please say what symbols they are
The spaces  separating inputs and outputs may or may not be used in your programs, i.e. 3 * 5 can be outputted as either 5 + 5 + 5 or 5+5+5.
Note that in most cases, addition is not actually performed. The only case where addition is to be performed is when you have something like 5 ^ (1 + 2), in which case, addition is necessary to continue -> 5 ^ 3 -> 5 * 5 * 5 -> .... See test case #4.
Your code does not need to handle inputs that arrive at an ambiguous expression. For example, (2 + 2) * (4 + 1). Because of the rules set forth so far, the goal is not to calculate the answer, the goal is to simplify to additions. So the result could be different depending on the order that expressions are resolved or commuted (which additions to simplify, which to leave?). Another invalid example: ((3 + 2) ^ 2) ^ 3 -> ((3 + 2) * (3 + 2)) ^ 3 -> ???.
This is code-golf so shortest code wins
Test cases
Input => output

5 ^ 3 + 4 * 1 ^ 5 => 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 4
2 ^ 1 * 2 + 3 + 9 => 2 + 2 + 3 + 9
2 ^ 1 * (2 + 3) + 9 => 2 + 3 + 2 + 3 + 9
2 ^ (1 * (2 + 3)) + 9 => 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 9
10 + 3 * 2 + 33 ^ 2 => 10 + 3 + 3 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33
100 * 3 => 100 + 100 + 100
2 ^ 1 + 2 ^ 1 + 2 ^ 2 + 8 ^ 1 => 2 + 2 + 2 + 2 + 8
(1 + 2 + 5 * 8 + 2 ^ 4) * 2 => 1 + 2 + 8 + 8 + 8 + 8 + 8 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 1 + 2 + 8 + 8 + 8 + 8 + 8 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2

May we use ** instead of ^?

@EriktheOutgolfer yeah, that seems fair.

Related.

I'm still confused as to what constitutes valid output.  In the question you say using only one of the two numbers in the original expression. but the original expression can have more than two numbers.  I don't get why 8 + 8 is not a valid output for 2 ^ 1 + 2 ^ 1 + 2 ^ 2 + 8 ^ 1.  This question is still pretty unclear to me.

Retina, 302 bytes
I'm sure this can be golfed, but at this point, I'm just glad it works. The exponentiation and multiplication sections are both very similar, but since order of operations is important, I don't know how to combine them.
y - Exponentiation
x - Multiplication
p - Addition
\d+
$*
{1`(\(\w+\)|1+)y(\(\w+\)|1+)
>$0<
(?<=>(\(\w+\)|1+)y1*)1
$1x
>(\(\w+\)|1+)y
(
x<
)
\((1+(x1+)*)\)(?!y)
$1
(?<!1)(1+)x(\(\w+\)|1+\1)(?!1)
$2x$1
1`(\(\w+\)|1+)x1+
>$0<
(?<=>(\(\w+\)|1+)x1*)1
$1p
>(\(\w+\)|1+)x
(
p<
)
(?<!x|y)\((1+(p1+)*)\)(?!x|y)
$1
y\((1+)p([1p]*\))
y($1$2
}`y\((1+)\)
y$1
1+
$.0

Try it online - all test cases
Test case converter
Explanation
\d+                             Convert to unary
$*
{1`(\(\w+\)|1+)y(\(\w+\)|1+)    Begin loop: Delimit current exponentiation group
>$0<
(?<=>(\(\w+\)|1+)y1*)1          Replace exponentiation with multiplication
$1x
>(\(\w+\)|1+)y                  Replace garbage with parentheses
(
x<
)
\((1+(x1+)*)\)(?!y)             Remove unnecessary parentheses around multiplication
$1
(?<!1)(1+)x(\(\w+\)|1+\1)(?!1)  Maybe swap order of multiplicands
$2x$1
1`(\(\w+\)|1+)x1+               Delimit current multiplication group
>$0<
(?<=>(\(\w+\)|1+)x1*)1          Replace multiplication with addition
$1p
>(\(\w+\)|1+)x                  Replace garbage with parentheses
(
p<
)
(?<!x|y)\((1+(p1+)*)\)(?!x|y)   Remove unnecessary parentheses around addition
$1
y\((1+)p([1p]*\))               Handle the 4th test case by adding if necessary
y($1$2
}`y\((1+)\)                     End of loop
y$1
1+                              Convert unary back to decimal
$.0

You may also notice that the most commonly used group is (\(\w+\)|1+). This matches an inner expression with parentheses, or an integer. I chose to use the symbols I did so that I could use \w rather than a character class. I'm not sure if it would be better to use non-word symbols and replace some lookarounds with word borders (\b).

Mathematica, 250 218 183 170 bytes
f~(s=SetAttributes)~HoldAll;{a,t}~s~Flat;f@n_:=Infix[Hold@n//.{a_~Power~b_:>t@@Hold@a~Table~b,Times->t,Plus->a,Hold->Dot}/.t->(a@@Table[#,1##2]&@@Reverse@Sort@{##}&),"+"]

It works! Finally!
Defines the function in f.
The input is a plain math expression. (i.e. 1 + 2 not "1 + 2").
Try it Online!
Note that the TIO link has a slightly different code, as TIO (which, I presume, uses Mathematica kernel) doesn't like Infix. I used Riffle instead to get the same appearance as Mathematica REPL.
Ungolfed
f~(s = SetAttributes)~HoldAll;  (* make f not evaluate its inputs *)

{a, t}~s~Flat;  (* make a and t flat, so that a[a[1,a[3]]] == a[1,3] *)

f@n_ :=  (* define f, input n *)

 Infix[

  Hold@n  (* hold the evaluation of n for replacement *)

    //. {  (* expand exponents *)

     (* change a^b to t[a,a,...,a] (with b a's) *)
     a_~Power~b_ :> t @@ Hold@a~Table~b,

     (* Replace Times and Plus with t and a, respectively *)
     Times -> t,
     Plus -> a,

     (* Replace the Hold function with the identity, since we don't need
         to hold anymore (Times and Plus are replaced) *)
     Hold -> Dot

     } /.  (* Replace; expand all t (= `Times`) to a (= `Plus`) *)

        (* Take an expression wrapped in t. *)
        (* First, sort the arguments in reverse. This puts the term
            wrapped in `a` (if none, the largest number) in the front *)
        (* Next, repeat the term found above by <product of rest
            of the arguments> times *)
        (* Finally, wrap the entire thing in `a` *)
        (* This will throw errors when there are multiple elements wrapped
           in `a` (i.e. multiplying two parenthesized elements) *)
        t -> (a @@ Table[#, 1 ##2] & @@
               Reverse@Sort@{##} &),

  "+"]  (* place "+" between each term *)

Ok, I'm happy I created a challenge that Mathematica doesn't have a built in for :P

Mathematica, 405 406 bytes
f~SetAttributes~HoldAll;p=(v=Inactive)@Plus;t=v@Times;w=v@Power;f@x_:=First@MinimalBy[Inactivate@{x}//.{w[a___,b_List,c___]:>(w[a,#,c]&/@b),t[a___,b_List,c___]:>(t[a,#,c]&/@b),p[a___,b_List,c___]:>(p[a,#,c]&/@b),p[a_]:>a,w[a_,b_]:>t@@Table[a,{Activate@b}],t[a___,t[b__],c___]:>t[a,b,c],p[a___,p[b__],c___]:>p[a,b,c],{a___,{b__},c___}:>{a,b,c},t[a__]:>Table[p@@Table[i,{Activate[t@a/i]}],{i,{a}}]},Length];f

Ungolfed and explained
SetAttributes[f, HoldAll]
p = Inactive[Plus]; t = Inactive[Times]; w = Inactive[Power];
f[x_] := First@MinimalBy[
   Inactivate[{x}] //. {
     w[a___, b_List, c___] :> (w[a, #, c] & /@ b),
     t[a___, b_List, c___] :> (t[a, #, c] & /@ b),
     p[a___, b_List, c___] :> (p[a, #, c] & /@ b),
     (* distribute lists of potential expansions over all operations *)
     p[a_] :> a,
     (* addition of a single term is just that term *)
     w[a_, b_] :> t @@ Table[a, {Activate@b}],
     (* a^b simplifies to a*a*...*a b times no matter what b is *)
     t[a___, t[b__], c___] :> t[a, b, c],
     p[a___, p[b__], c___] :> p[a, b, c],
     {a___, {b__}, c___} :> {a, b, c},
     (* operations are associative *)
     t[a__] :> Table[p @@ Table[i, {Activate[t@a/i]}], {i, {a}}]
     (* for a product, generate a list of potential expansions *)}
   , Length]
f

I went to a great deal of trouble to get the following effect: this function takes as input a standard Mathematica expression, with the usual +, *, and ^ operations (and parentheses) in it, and outputs what looks like a standard Mathematica expression (but with "deactivated" plus signs) as the answer.
The function above begins by deactivating all operations in the input. Then, it applies expansion rules repeatedly until nothing can be simplified anymore. Whenever it encounters a product such as 2 * 3 * 4, which can be expanded in multiple ways, it makes a list of possible expansions, and keeps going. At the end, we get a list of possible final answers, and the shortest is picked.


text:
A Euro-iginal Sequence
Given a positive integer n output the n-th number of the euro-iginal sequence.
Calculating the Sequence
This sequence is equal to OEIS A242491.
A number is part of said sequence if the number can be made up by using as many different euro coins or notes, but only one of each. Note that you don't have to consider cents.
Example:
6 would be in the sequence, as it can consist of a 1-euro coin and a 5-euro-note.
4 would NOT be in the sequence, as it can't be formed with the given requirements.
To give everyone an overview, heres a list with euro values you have to consider:

1€, 2€, 5€, 10€, 20€, 50€, 100€, 200€, 500€

Note that this sequence only ranges from 0 (yes, 0 is included!) to 888.

Here are the first 15 elements of this sequence:
0, 1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, ...
Test Cases
Input -> Output
2 -> 1
6 -> 6
21 -> 25
33 -> 50

What is the largest possible input? Can we have some larger test cases?

May we index as a(1)=1 like the oeis table?

Can we assune N<=512?

@xnor If it still returns 0 for n=0 it's fine.

Can we output the 0-indexed results instead of 1-indexed? So 0->0; 1->1; 5->6; 20->25; 32->50; 511->888 instead of 1->0; 2->1; 6->6; 21->25; 33->50; 512->888.

@KevinCruijssen Sure, since that is basically what the OEIS sequence is.

Jelly, 7 bytes
b8d4ḅ5Ḍ

Try it online!
How it works
b8d4ḅ5Ḍ  Main link. Argument: n (integer)

b8       Convert n from integer to base 8.
  d4     Divmod each base-8 digit by 4, mapping the digit d to [d / 4, d % 4].
    ḅ5   Convert the quotient-remainder pairs from base 5 to integer, mapping
         [d / 4, d % 4] to (d / 4 * 5 + d % 4).
         The last two steps establish the following mapping for octal digits.
             0 -> [0, 0] -> 0
             1 -> [0, 1] -> 1
             2 -> [0, 2] -> 2
             3 -> [0, 3] -> 3
             4 -> [1, 0] -> 5
             5 -> [1, 1] -> 6
             6 -> [1, 2] -> 7
             7 -> [1, 3] -> 8
      Ḍ  Convert the resulting array of digits from decimal to integer.

Python 2, 32 bytes
lambda n:n+n/4+n/32*10+n/256*100

Try it online!

Python 2, 34 bytes
f=lambda n:n and 10*f(n/8)+n%8*5/4

Try it online!

I keep looking at your math trying to figure out how you got to your solution. How did you find that solution?

Husk, 8 7 5 bytes
Σ!Ṗİ€

Try it online! Edit: -3 bytes thanks to Zgarb!
   İ€   build-in infinite sequence [1,2,5,10,20,50,100,...]
  Ṗ     power set [[],[1],[2],[1,2],[5],[1,5],[2,5],[1,2,5],...]
 !      index into the list with given input, e.g. 4 yields [1,2]
Σ       take the sum of that list

I heard that it is planned to change İ€ to the finite sequence [0.01,0.02,0.05,0.1,0.2,0.5,1,2,5,10,...,500] in the future. Once that is implemented, the following code should work a byte count of 7:
Σ!Ṗ↓6İ€

where ↓6 drops the first six elements of the sequence.
Try it online!

Is it intended that the program adds 2 0s to the output?

Σ!Ṗ↑9İ€ should save a byte.

@IanH. The first program produces the correct output. The second TIO link will only work after the implementation of İ€ has been changed. That it is currently returning 2500 instead of 25 is merely a coincidence.

@Zgarb Thanks a lot!

I think you can also remove ↑9, since the challenge text doesn't mention what should happen for inputs beyond 512.

Perl 5, 29 bytes
28 bytes code + 1 for -p.
Uses 0 based indexing.
$_=sprintf"%o",$_;y/4-7/5-8/

Try it online!

should be sprintf"%o",$_-1, because of sequence indexed from 1 for example 2 -> 1, altough OEIS sequence starts with 1

This uses 0 indexing as allowed by the question (or at least, OPs comments under the question). I did have the -1 until OP clarified!

Jelly, 11 bytes
0Df9,4Ṇ$$#Ṫ

Try it online!
Thanks a lot to @Erik the Outgolfer for a lot of help in chat!
Explanation

0Df9,4Ṇ$$#Ṫ  - Monadic link.

0        #   - Collect first N matches, starting from 0.
 D           - Digits.
  f9,4       - Filter-Keep the digits that are either 9 or 4. Yields [] when there are none.
      Ṇ      - Logical NOT. [] -> 1 (truthy), non-empty list -> 0 (falsy).
          Ṫ  - Pop and return the last element.

Mathematica, 47 bytes
(FromDigits/@0~Range~8~Drop~{5}~Tuples~3)[[#]]&

Mathematica, 48 bytes
Sort[Tr/@Subsets@Join[x={1,2,5},10x,100x]][[#]]&

-6 bytes from Martin Ender

Join[x={1,2,5},10x,100x] and Subsets@.

Java 8, 28 26 bytes
0-indexed:
n->n+n/4+n/32*10+n/256*100

Port of @xnor's Python 2 answer (which used to be deleted, hence the original 1-indexed answer below).
Try it here.

Old 1-indexed answer (28 bytes):
n->--n+n/4+n/32*10+n/256*100

Port of @Tfeld's Python 2 answer before he made his last edit. Instead of using ~- a bunch of times, it uses --n to decrease n by 1 right after entering the lambda function.
Try it here.

05AB1E, 7 bytes
0-indexed.
Port of Mr. Xcoder's Jelly answer
µN7nÃg_

Try it online!
Explanation
µ          # loop over increasing N until input matches are found
      _    # the logical negation of
     g     # the length of
 N         # N
  7nÃ      # with only 4s and 9s kept

Nice, seems like 05AB1E is the best tool for my algorithm :-). Dennis' arithmagic approach would get you 9 (maybe golfable) bytes: 8в4‰ε5β}J (0-indexed)

@Mr.Xcoder: I had 8в4‰J5öJ for 8 with Dennis' trick. Yours was better suited for 05AB1E indeed :)

Python 2, 40 38 36 bytes
Inspired by xnor's answer, but uses 1-indexing.
lambda n:~-n*5/4+~-n/32*10+n/257*100

Try it online!
Python 2, 78 65 62 61 58 56 bytes
lambda i,n=0:f(i+~-('4'in`n`or'9'in`n`),n+1)if i else~-n

Try it online!

36 bytes

Is there a reason @xnor deleted his answer, because it seems completely valid to me.. :S

@KevinCruijssen I've undeleted it now that the asker answered that shifting the indexing to a(1)=1 is allowed.

Octave, 59 bytes
@(n)unique((dec2bin(0:511)-48)*kron([1 2 5],10.^(0:2))')(n)

Try it online!
Explanation
The code creates the full sequence and then indexes into it.
First, the binary expressions of the numbers 0, 1, ... 511 are generated as a 512×9 matrix:

dec2bin(0:511)-48

(the -48 part is needed because the result of dec2bin is characters, not numbers). This gives
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1
...
1 1 1 1 1 1 1 1 1

Then the Kronecker product of [1 2 5] and [1 10 100] is computed

kron([1 2 5],10.^(0:2))

and transposed

'

which gives the nine possible euro values as a 9×1 vector:
1
2
5
10
20
50
100
200
500

Matrix-multiplying the above matrix and vector

*

gives a 512×1 vector containing all possible numbers in the sequence, with repetitions and unsorted:
  0
500
 50
...
388
888

Deduplicating and sorting

unique(...)

gives the full sequence:
  0
  1
  2
...
887
888

Finally, the input is used to index into this sequence

(n)

to produce the output.

Jelly, 15 bytes
0-indexed.
æ»“£¦®‘×“¢½d‘S+

Try it online!
Explanation
This is based off of xnor's Python solution, where the algorithm is n + n/4 + n/32*10 + n/256*100.
lambda n: sum(i * j for i, j in zip([n / i for i in [1, 4, 32, 256]], [1, 1, 10, 100]]))

Since the first n is unmodified, this is the same as:
lambda n: sum(i * j for i, j in zip([n / i for i in [4, 32, 256]], [1, 10, 100]])) + n

Since 4, 32, and 256 are all powers of two, they can be translated into bit shifts.
lambda n: sum(i * j for i, j in zip([n >> i for i in [2, 5, 8]], [1, 10, 100]])) + n

The golfiness doesn't translate well in Python, but turning the lists into Jelly strings of code page indices reduces Jelly's byte count.
lambda n: sum(i * j for i, j in zip([n >> i for i in map(jelly_codepage.index, '£¦®')], map(jelly_codepage.index, '¢½d'))) + n

Jelly, 24 bytes
“¡¿ɼcÞµ³Ṡf2ż’bȷ3ŒPS€Ṣ
ị¢

Try it online!

+1 for having € in your code. :) But -1 because this is the first time ever a Jelly answer is longer than my Java answer. XD Shame on you (and gl & hf golfing it further). ;)

@KevinCruijssen This is going to wreak havoc on the Elo ratings.

@KevinCrujissen A bit better now? :P

@icrieverytim You made a typo in my name, so I didn't get the summon. But yes, a lot better. :) +1 from me.

Ruby, 28 27 bytes
->x{("%o"%x).tr"4-7","5-8"}

Try it online!
Explanation
Output octal string, replace digits 4..7 with 5..8

I think you can remove the space after .tr for -1

Bash + GNU utilities, 20
dc -e8o?p|tr 4-7 5-8

Reads a zero-indexed index from STDIN.
Try it online.

05AB1E, 20 bytes
9LD3%n>s3/óTsm*æO{sè

Try it online!

1-indexed, using the formula of [(n%3)^2 + 1]*10^floor(n/3) to generate the first 10 terms, then using powerset to calculate all possible combinations... Then I sort it and pull a[b].

See it in action below:
Full program: 9LD3%n>s3/óTsm*æO{sè
current >> 9  ||  stack: []
current >> L  ||  stack: ['9']
current >> D  ||  stack: [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
current >> 3  ||  stack: [[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 2, 3, 4, 5, 6, 7, 8, 9]]
current >> %  ||  stack: [[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 2, 3, 4, 5, 6, 7, 8, 9], '3']
current >> n  ||  stack: [[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 2, 0, 1, 2, 0, 1, 2, 0]]
current >> >  ||  stack: [[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 4, 0, 1, 4, 0, 1, 4, 0]]
current >> s  ||  stack: [[1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 1, 2, 5, 1, 2, 5, 1]]
current >> 3  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], [1, 2, 3, 4, 5, 6, 7, 8, 9]]
current >> /  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], [1, 2, 3, 4, 5, 6, 7, 8, 9], '3']
current >> ó  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], [0.3333333333333333, 0.6666666666666666, 1.0, 1.3333333333333333, 1.6666666666666667, 2.0, 2.3333333333333335, 2.6666666666666665, 3.0]]
current >> T  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], [0, 0, 0, 1, 1, 1, 2, 2, 2]]
current >> s  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], [0, 0, 0, 1, 1, 1, 2, 2, 2], 10]
current >> m  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], 10, [0, 0, 0, 1, 1, 1, 2, 2, 2]]
current >> *  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], [1, 1, 1, 10, 10, 10, 100, 100, 100]]
current >> æ  ||  stack: [[2, 5, 1, 20, 50, 10, 200, 500, 100]]
current >> O  ||  stack: < OMITTED, THE RESULT OF POWERSET IS HUGE >
current >> {  ||  stack: [[0, 2, 5, 1, 20, 50, 10, 200, 500, 100, 7, 3, 22, 52, 12, 202, 502, 102, 6, 25, 55, 15, 205, 505, 105, 21, 51, 11, 201, 501, 101, 70, 30, 220, 520, 120, 60, 250, 550, 150, 210, 510, 110, 700, 300, 600, 8, 27, 57, 17, 207, 507, 107, 23, 53, 13, 203, 503, 103, 72, 32, 222, 522, 122, 62, 252, 552, 152, 212, 512, 112, 702, 302, 602, 26, 56, 16, 206, 506, 106, 75, 35, 225, 525, 125, 65, 255, 555, 155, 215, 515, 115, 705, 305, 605, 71, 31, 221, 521, 121, 61, 251, 551, 151, 211, 511, 111, 701, 301, 601, 80, 270, 570, 170, 230, 530, 130, 720, 320, 620, 260, 560, 160, 750, 350, 650, 710, 310, 610, 800, 28, 58, 18, 208, 508, 108, 77, 37, 227, 527, 127, 67, 257, 557, 157, 217, 517, 117, 707, 307, 607, 73, 33, 223, 523, 123, 63, 253, 553, 153, 213, 513, 113, 703, 303, 603, 82, 272, 572, 172, 232, 532, 132, 722, 322, 622, 262, 562, 162, 752, 352, 652, 712, 312, 612, 802, 76, 36, 226, 526, 126, 66, 256, 556, 156, 216, 516, 116, 706, 306, 606, 85, 275, 575, 175, 235, 535, 135, 725, 325, 625, 265, 565, 165, 755, 355, 655, 715, 315, 615, 805, 81, 271, 571, 171, 231, 531, 131, 721, 321, 621, 261, 561, 161, 751, 351, 651, 711, 311, 611, 801, 280, 580, 180, 770, 370, 670, 730, 330, 630, 820, 760, 360, 660, 850, 810, 78, 38, 228, 528, 128, 68, 258, 558, 158, 218, 518, 118, 708, 308, 608, 87, 277, 577, 177, 237, 537, 137, 727, 327, 627, 267, 567, 167, 757, 357, 657, 717, 317, 617, 807, 83, 273, 573, 173, 233, 533, 133, 723, 323, 623, 263, 563, 163, 753, 353, 653, 713, 313, 613, 803, 282, 582, 182, 772, 372, 672, 732, 332, 632, 822, 762, 362, 662, 852, 812, 86, 276, 576, 176, 236, 536, 136, 726, 326, 626, 266, 566, 166, 756, 356, 656, 716, 316, 616, 806, 285, 585, 185, 775, 375, 675, 735, 335, 635, 825, 765, 365, 665, 855, 815, 281, 581, 181, 771, 371, 671, 731, 331, 631, 821, 761, 361, 661, 851, 811, 780, 380, 680, 870, 830, 860, 88, 278, 578, 178, 238, 538, 138, 728, 328, 628, 268, 568, 168, 758, 358, 658, 718, 318, 618, 808, 287, 587, 187, 777, 377, 677, 737, 337, 637, 827, 767, 367, 667, 857, 817, 283, 583, 183, 773, 373, 673, 733, 333, 633, 823, 763, 363, 663, 853, 813, 782, 382, 682, 872, 832, 862, 286, 586, 186, 776, 376, 676, 736, 336, 636, 826, 766, 366, 666, 856, 816, 785, 385, 685, 875, 835, 865, 781, 381, 681, 871, 831, 861, 880, 288, 588, 188, 778, 378, 678, 738, 338, 638, 828, 768, 368, 668, 858, 818, 787, 387, 687, 877, 837, 867, 783, 383, 683, 873, 833, 863, 882, 786, 386, 686, 876, 836, 866, 885, 881, 788, 388, 688, 878, 838, 868, 887, 883, 886, 888]]
current >> s  ||  stack: [[0, 1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22, 23, 25, 26, 27, 28, 30, 31, 32, 33, 35, 36, 37, 38, 50, 51, 52, 53, 55, 56, 57, 58, 60, 61, 62, 63, 65, 66, 67, 68, 70, 71, 72, 73, 75, 76, 77, 78, 80, 81, 82, 83, 85, 86, 87, 88, 100, 101, 102, 103, 105, 106, 107, 108, 110, 111, 112, 113, 115, 116, 117, 118, 120, 121, 122, 123, 125, 126, 127, 128, 130, 131, 132, 133, 135, 136, 137, 138, 150, 151, 152, 153, 155, 156, 157, 158, 160, 161, 162, 163, 165, 166, 167, 168, 170, 171, 172, 173, 175, 176, 177, 178, 180, 181, 182, 183, 185, 186, 187, 188, 200, 201, 202, 203, 205, 206, 207, 208, 210, 211, 212, 213, 215, 216, 217, 218, 220, 221, 222, 223, 225, 226, 227, 228, 230, 231, 232, 233, 235, 236, 237, 238, 250, 251, 252, 253, 255, 256, 257, 258, 260, 261, 262, 263, 265, 266, 267, 268, 270, 271, 272, 273, 275, 276, 277, 278, 280, 281, 282, 283, 285, 286, 287, 288, 300, 301, 302, 303, 305, 306, 307, 308, 310, 311, 312, 313, 315, 316, 317, 318, 320, 321, 322, 323, 325, 326, 327, 328, 330, 331, 332, 333, 335, 336, 337, 338, 350, 351, 352, 353, 355, 356, 357, 358, 360, 361, 362, 363, 365, 366, 367, 368, 370, 371, 372, 373, 375, 376, 377, 378, 380, 381, 382, 383, 385, 386, 387, 388, 500, 501, 502, 503, 505, 506, 507, 508, 510, 511, 512, 513, 515, 516, 517, 518, 520, 521, 522, 523, 525, 526, 527, 528, 530, 531, 532, 533, 535, 536, 537, 538, 550, 551, 552, 553, 555, 556, 557, 558, 560, 561, 562, 563, 565, 566, 567, 568, 570, 571, 572, 573, 575, 576, 577, 578, 580, 581, 582, 583, 585, 586, 587, 588, 600, 601, 602, 603, 605, 606, 607, 608, 610, 611, 612, 613, 615, 616, 617, 618, 620, 621, 622, 623, 625, 626, 627, 628, 630, 631, 632, 633, 635, 636, 637, 638, 650, 651, 652, 653, 655, 656, 657, 658, 660, 661, 662, 663, 665, 666, 667, 668, 670, 671, 672, 673, 675, 676, 677, 678, 680, 681, 682, 683, 685, 686, 687, 688, 700, 701, 702, 703, 705, 706, 707, 708, 710, 711, 712, 713, 715, 716, 717, 718, 720, 721, 722, 723, 725, 726, 727, 728, 730, 731, 732, 733, 735, 736, 737, 738, 750, 751, 752, 753, 755, 756, 757, 758, 760, 761, 762, 763, 765, 766, 767, 768, 770, 771, 772, 773, 775, 776, 777, 778, 780, 781, 782, 783, 785, 786, 787, 788, 800, 801, 802, 803, 805, 806, 807, 808, 810, 811, 812, 813, 815, 816, 817, 818, 820, 821, 822, 823, 825, 826, 827, 828, 830, 831, 832, 833, 835, 836, 837, 838, 850, 851, 852, 853, 855, 856, 857, 858, 860, 861, 862, 863, 865, 866, 867, 868, 870, 871, 872, 873, 875, 876, 877, 878, 880, 881, 882, 883, 885, 886, 887, 888]]
current >> è  ||  stack: [[0, 1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22, 23, 25, 26, 27, 28, 30, 31, 32, 33, 35, 36, 37, 38, 50, 51, 52, 53, 55, 56, 57, 58, 60, 61, 62, 63, 65, 66, 67, 68, 70, 71, 72, 73, 75, 76, 77, 78, 80, 81, 82, 83, 85, 86, 87, 88, 100, 101, 102, 103, 105, 106, 107, 108, 110, 111, 112, 113, 115, 116, 117, 118, 120, 121, 122, 123, 125, 126, 127, 128, 130, 131, 132, 133, 135, 136, 137, 138, 150, 151, 152, 153, 155, 156, 157, 158, 160, 161, 162, 163, 165, 166, 167, 168, 170, 171, 172, 173, 175, 176, 177, 178, 180, 181, 182, 183, 185, 186, 187, 188, 200, 201, 202, 203, 205, 206, 207, 208, 210, 211, 212, 213, 215, 216, 217, 218, 220, 221, 222, 223, 225, 226, 227, 228, 230, 231, 232, 233, 235, 236, 237, 238, 250, 251, 252, 253, 255, 256, 257, 258, 260, 261, 262, 263, 265, 266, 267, 268, 270, 271, 272, 273, 275, 276, 277, 278, 280, 281, 282, 283, 285, 286, 287, 288, 300, 301, 302, 303, 305, 306, 307, 308, 310, 311, 312, 313, 315, 316, 317, 318, 320, 321, 322, 323, 325, 326, 327, 328, 330, 331, 332, 333, 335, 336, 337, 338, 350, 351, 352, 353, 355, 356, 357, 358, 360, 361, 362, 363, 365, 366, 367, 368, 370, 371, 372, 373, 375, 376, 377, 378, 380, 381, 382, 383, 385, 386, 387, 388, 500, 501, 502, 503, 505, 506, 507, 508, 510, 511, 512, 513, 515, 516, 517, 518, 520, 521, 522, 523, 525, 526, 527, 528, 530, 531, 532, 533, 535, 536, 537, 538, 550, 551, 552, 553, 555, 556, 557, 558, 560, 561, 562, 563, 565, 566, 567, 568, 570, 571, 572, 573, 575, 576, 577, 578, 580, 581, 582, 583, 585, 586, 587, 588, 600, 601, 602, 603, 605, 606, 607, 608, 610, 611, 612, 613, 615, 616, 617, 618, 620, 621, 622, 623, 625, 626, 627, 628, 630, 631, 632, 633, 635, 636, 637, 638, 650, 651, 652, 653, 655, 656, 657, 658, 660, 661, 662, 663, 665, 666, 667, 668, 670, 671, 672, 673, 675, 676, 677, 678, 680, 681, 682, 683, 685, 686, 687, 688, 700, 701, 702, 703, 705, 706, 707, 708, 710, 711, 712, 713, 715, 716, 717, 718, 720, 721, 722, 723, 725, 726, 727, 728, 730, 731, 732, 733, 735, 736, 737, 738, 750, 751, 752, 753, 755, 756, 757, 758, 760, 761, 762, 763, 765, 766, 767, 768, 770, 771, 772, 773, 775, 776, 777, 778, 780, 781, 782, 783, 785, 786, 787, 788, 800, 801, 802, 803, 805, 806, 807, 808, 810, 811, 812, 813, 815, 816, 817, 818, 820, 821, 822, 823, 825, 826, 827, 828, 830, 831, 832, 833, 835, 836, 837, 838, 850, 851, 852, 853, 855, 856, 857, 858, 860, 861, 862, 863, 865, 866, 867, 868, 870, 871, 872, 873, 875, 876, 877, 878, 880, 881, 882, 883, 885, 886, 887, 888], '32']
50
stack > [50]

JavaScript (ES6), 34 bytes
n=>--n+(n>>2)+(n>>5)*10+(n>>8)*100

Or 32 bytes using the correct 0-indexing:

f=
n=>n+(n>>2)+(n>>5)*10+(n>>8)*100
<input type=number min=0 max=511 value=0 oninput=o.textContent=f(+this.value)><pre id=o>0

Shouldn't n=1 give 0?

Pyth, 12 bytes
Uses Dennis' witchcraft.
jkiR5.DR4jQ8

Try it here.
Pyth,  16 15  13 bytes
e.f!@,9 4jZTt

Verify all the test cases.
Thanks to Erik the Outgofer for some ideas.

Jelly, 20 bytes
53b6×þ“¢½d‘FŒPS€Ṣị@‘

Try it online!
I know this is longer than the existing answer but I think this approach is golfable from here :P
-2 bytes thanks to Erik the Outgolfer

1,10,ȷ2 -> “¢½d‘

@EriktheOutgolfer Oh thanks!

Retina, 42 bytes
.+
$*1;
+`(1+)\1{7}
$1;
1111
1$&
(1*);
$.1

Try it online! Link includes test cases. 0-indexed. Explanation:
.+
$*1;

Convert from decimal to unary, with a ; suffix.
+`(1+)\1{7}
$1;

Convert to octal, but still using unary representation of the digits with ; after each unary value.
1111
1$&

Add 1 to the values 4-7.
(1*);
$.1

Convert each value plus its suffix to decimal.

C, 67 bytes
main(n){scanf("%d",&n);printf("%d",n+(n>>2)+(n>>5)*10+(n>>8)*100);}

A direct port from Neil's JavaScript answer, but I thought this should be added for completeness.

Tested on GCC version 6.3.0. It will throw some warnings, but compile anyway.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
I don't like change!
Input:
Two strings without newlines or whitespaces.
Output:
Both input strings on separate lines, with spaces where necessary† for one of the two strings. And a third line with the characters A, R, M and , representing added, removed, modified, and unchanged.
† We add spaces to either the top or bottom input string (if we have to). The goal of this challenge is to output with the least amount of changes (ARM) possible, also known as the Levenshtein distance.
Example:
Let's say the input strings are ABCDEF and AFBECD, then the output would be this:
A B CDEF
AFBECD
 A A  RR

Here are some other possible invalid outputs as example (and there are a lot more):
ABCDEF
AFBECD
 MMMMM

A BCDEF
AFBECD
 A MMMR

AB CDEF
AFBECD
 MAMMMR

ABC DEF
AFBECD
 MMAMMR

ABC  DEF
AFBECD
 MMAA RR

ABCDEF
AFB ECD
 MMR MA

 AB CDEF   // This doesn't make much sense,
AFBECD     // but it's to show leading spaces are also allowed
AM A  RR

None of these have only four changes however, so only A B CDEF\nAFBECD  \n A A  RR is a valid output for this challenge.
Challenge rules:

You can assume the input strings won't contain any new-lines or spaces.
The two input strings can be of different lengths.
One of the two input strings should remain as is, except for optional leading/trailing spaces.
If your languages doesn't support anything besides ASCII, you can assume the input will only contain printable ASCII characters.
The input and output format are flexible. You can have three separate Strings, a String array, a single String with new-lines, 2D character array, etc.
You are allowed to use something else instead of ARM, but state what you've used (i.e. 123, or abc., etc.)
If more than one valid output is possible with the same amount of changes (ARM), you can choose whether to output one of the possible outputs or all of them.
Leading and trailing spaces are optional:
A B CDEF
AFBECD
 A A  RR

or
"A B CDEF\nAFBECD\n A A  RR"
                 ^
                 Note there are no spaces here

General rules:

This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code.
Also, please add an explanation if necessary.

Test cases:
In: "ABCDEF" & "AFBECD"

Output (4 changes):
A B CDEF
AFBECD
 A A  RR

In: "This_is_an_example_text" & "This_is_a_test_as_example"

Possible output (13 changes):
This_is_an       _example_text
This_is_a_test_as_example
         MAAAAAAA        RRRRR

In: "AaAaABBbBBcCcCc" & "abcABCabcABC"

Possible output (10 changes):
AaAaABBbBBcCcCc
 abcABCab cABC
R MM  MMMR MM R

In: "intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}" & "intf(){intr=(int)(Math.random()*10);returnr>0?r%2:2;}"

Possible output (60 changes):
intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}
intf(){i ntr=(      i    n      t)(M  ath.r   andom        ()*         10          );returnr>0?r%2:2;}
       MR M  MRRRRRR RRRR RRRRRR MMMRR MMMMRRR     RRRRRRRR  MRRRRRRRRR  RRRRRRRRRR

In: "ABCDEF" & "XABCDF"

Output (2 changes):
 ABCDEF
XABCD F
A    R

In: "abC" & "ABC"

Output (2 changes):
abC
ABC
MM

Related

If there are multiple arrangements that are the same distance, is it OK to only output one of them?

@AdmBorkBork Yes, just one of the possible outputs is indeed the intended output (although outputting all available options is also fine). I'll clarify this in the challenge rules.

@Arnauld I've removed the rule about leading spaces, so leading and trailing spaces are both optional and valid on the unmodified line. (Which means the last test case in your answer is completely valid.)

Can we use lowercase instead of uppercase?

Do we need to compare byte, characters, code points, or graphene clusters? (when dealing with a language that supports unicode)

@StanStrum "You are allowed to use something else instead of ARM, but state what you've used (i.e. 123, or abc., etc.)"

@Laikoni "The input and output format are flexible. You can have three separate Strings, a String array, a single String with new-lines, 2D character array, etc."

@Ferrybig Hmm.. characters I guess. Aren't these all unique when you use a single encoding? Could you give an example of where a character could be different in character, but still might be equal in code points, graphene clusters, and/or bytes in the same encoding?

@KevinCruijssen स्ते this string is 1 graphene cluster, consisting of 4 code points and 4 characters, and is 12 bytes when represented on disk using UTF-8, or 10  bytes on disk using UTF-16 . Unicode support is harder than most people realise, and while you probably meant to support graphene clusters for this challenge, most answers probably won't support it. You might be interesting to read the exact difference here: http://utf8everywhere.org/#characters (no affiliation)

@Ferrybig Ah ok, thanks for the explanation. But as for this challenge, just supporting printable ASCII is actually already enough. If you want to support more, be my guest. But as long as it works for the test cases given I'm ok with undefined behavior for graphene clusters consisting of more than 1 character like that. :)

Haskell, 192 181 174 161 158 150 147 143 1581 bytes
e@(a:r)&f@(b:s)=snd$maximum[([1|' '<-s!!2],s)|s<-z(z(:))[a:" R",' ':b:"A",a:b:last("M":[" "|a==b])][r&f,e&s,r&s]]
x&y=[x,y,"RA"!!(0^length x)<$x++y]
z=zipWith

Try it online! Example usage: "ABCDEF" & "AFBECD". Returns a list of three strings. This is an extension of my recursive solution to the ordinary Levenshtein distance question.
Explanation:
To compute the minimal modifications to get from "xyz" to "yw", we focus on the first character of both strings. There are three possibilities:

Remove: Drop x from the first string and recursively compute the modifications to get from "yz" to "yw". This yields the three lines ["yz","yw"," M"]. Add x to the first one, a space to the second one and R to the third one. We get xyz
yw
R M
Add: Drop y from the second string and compute "xyz" & "w", which returns the result ["xyz","w","MRR"]. We need to add a space on the first line, y to the second and A to the third line:  xyz
yw
AMRR
Modified/Unchanged: We can combine those two cases because both require to drop the first character of both strings and compute the minimal modifications between the remaining strings: "yz" & "w". To the result ["yz","w","MR"], we add x on he first and y on the second line. Only for the last line we need to differentiate whether the initial characters are the same. If they are the same, a space is added to the third line, otherwise (as in this case because x \= y) an M is added: xyz
yw
MMR

From those three candidates, we need to find the one with the fewest modifications. This is equivalent to having the most spaces on the third line. Therefore we convert each candidate s (a list of three strings) to a tuple ([1|' '<-s!!2],s), where s appears as second component and the first component is a list with as many elements as there are spaces in the third line of s (s!!2 because of 0-indexing). As list element 1 is used, but the actual element is irrelevant as long as it is the same for all candidates.
Altogether, this yields the list of tuples [([1],["xyz"," yw","R M"]),([],[" xyz","yw","AMRR"]),([],["xyz","yw","MMR"])]
The build-in maximum selects the largest element of this list, where tuples are compared lexicographically, that is component-wise from left to right. As [1] is larger than [], the first tuple is selected, and snd returns the second of component, that is the list of lines, of the tuple.

1 +15 bytes to fix a bug where A-changes at the end of a string would be displayed as R-changes

lol this makes the userscript think that this is 1 byte

JavaScript (ES6), 413 ... 343 342 bytes
Saved 5 bytes by tweaking the loop indices, as suggested by @KevinCruijssen
Takes input as 2 strings in currying syntax. Returns an array of 3 strings.
b=>a=>{m=[];x=a.length;y=b.length;for(i=j=0,c=d='';i<=y;c+=R='R')m[i]=[[c,i++]];for(;j++<x;)m[i=0][j]=[d+=A='A',j];for(;i<y;i++)for(j=0;j<x;)[C]=m[[X,S]=m[i][j],[Y,I]=m[i+1][j],[Z,D]=m[i][++j],Q=[Z+R,D+1],i+1][j]=b[i]==a[j-1]?[X+' ',S]:S<I?D<S?Q:[X+'M',S+1]:D<I?Q:[Y+A,I+1];return[(g=s=>C.replace(/./g,c=>c==s?' ':b[i++],i=0))(A),g(R,b=a),C]}

Test cases

let f =

b=>a=>{m=[];x=a.length;y=b.length;for(i=j=0,c=d='';i<=y;c+=R='R')m[i]=[[c,i++]];for(;j++<x;)m[i=0][j]=[d+=A='A',j];for(;i<y;i++)for(j=0;j<x;)[C]=m[[X,S]=m[i][j],[Y,I]=m[i+1][j],[Z,D]=m[i][++j],Q=[Z+R,D+1],i+1][j]=b[i]==a[j-1]?[X+' ',S]:S<I?D<S?Q:[X+'M',S+1]:D<I?Q:[Y+A,I+1];return[(g=s=>C.replace(/./g,c=>c==s?' ':b[i++],i=0))(A),g(R,b=a),C]}

console.log(f('ABCDEF')('AFBECD').join`\n`);
console.log(f('This_is_an       _example_text')('This_is_a_test_as_example').join`\n`);
console.log(f('AaAaABBbBBcCcCc')('abcABCabcABC').join`\n`);
console.log(f("intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}")("intf(){intr=(int)(Math.random()*10);returnr>0?r%2:2;}").join`\n`);
console.log(f('ABCDEF')('XABCDF').join`\n`);

Less golfed
b => a => {
  m = []; x = a.length; y = b.length;

  // initialize the leftmost column and the topmost row
  for(i = j = 0, c = d = ''; i <= y; c += R = 'R')
    m[i] = [[c, i++]];
  for(; j++ < x;)
    m[i = 0][j] = [d += A = 'A', j];

  // walk through the Levenshtein matrix
  for(; i < y; i++)
    for(j = 0; j < x;)
      [C] = m[                                // C = current string, once updated
        [X, S] = m[i][j],                     // substitution
        [Y, I] = m[i + 1][j],                 // insertion
        [Z, D] = m[i][++j],                   // deletion
        Q = [Z + R, D + 1],                   // precomputed update for deletion
        i + 1
      ][j] =
        b[i] == a[j - 1] ?
          [X + ' ', S]                        // unchanged character
        :
          S < I ?
            D < S ? Q : [X + 'M', S + 1]      // deletion or substitution
          :
            D < I ? Q : [Y + A, I + 1];       // deletion or insertion

  return [
    // g = helper function to format the output strings by inserting spaces
    (g = s => C.replace(/./g, c => c == s ? ' ' : b[i++], i = 0))(A),
    g(R, b = a),

    // final modification string, picked from the last visited cell
    C
  ]
}

Example
Below is the initial matrix for b = "foo" and a = "ok":
//                     'o'           'k'
[ [ [ '',    0 ], [ 'A',   1 ], [ 'AA',  2 ] ],
  [ [ 'R',   1 ],  (undefined),  (undefined) ],  // 'f'
  [ [ 'RR',  2 ],  (undefined),  (undefined) ],  // 'o'
  [ [ 'RRR', 3 ],  (undefined),  (undefined) ] ] // 'o'

and here is the final matrix after all iterations:
//                     'o'           'k'
[ [ [ '',    0 ], [ 'A',   1 ], [ 'AA',  2 ] ],
  [ [ 'R',   1 ], [ 'M',   1 ], [ 'MA',  2 ] ],  // 'f'
  [ [ 'RR',  2 ], [ 'R ',  1 ], [ 'R A', 2 ] ],  // 'o'
  [ [ 'RRR', 3 ], [ 'RR ', 2 ], [ 'R M', 2 ] ] ] // 'o'

The final modification string along with the Levenshtein distance are stored in the bottom-right cell.

Same change I suggested to save 1 byte regarding -1/+1 of j and x still applies to your latest edit: b=>a=>{m=[];x=a.length;y=b.length+1;for(i=y;i--;)m[i]=[[i,'R'.repeat(i)]];for(j=x+1;j--;)m[i=0][j]=[j,'A'.repeat(j)];for(;++i<y;)for(j=-1;++j<x;)R=m[S=(X=m[i-1][j])[0],I=(Y=m[i][j])[0],D=(Z=m[i-1][j+1])[0],Q=[D+1,Z[1]+'R'],i][j+1]=b[i-1]==a[j]?[S,X[1]+' ']:S<I?D<S?Q:[S+1,X[1]+'M']:D<I?Q:[I+1,Y[1]+'A'];return[(g=s=>R[1].replace(/./g,c=>c==s?' ':b[i++],i=0))('A'),g('R',b=a),R[1]]} :)

@KevinCruijssen I saved 5 bytes by taking your idea a step further. Thanks!

Python 2, 548 536 484 5001 488 447 3812 373 371 357 350 bytes
s,t=input()
n,m=len(s),len(t)
r=range
L=[[(j,'RA'[i<1]*j)for j in r(i,m-~i)]for i in r(n+1)]
for i in r(n):
 for j in r(m):M,R=L[i][j:j+2];A=L[i+1][j];v,V=min(A,R,M);x=('AR'[v in R],'M_'[s[i]==t[j]])[v in M];_=M;X=eval(x)[1]+x;L[i+1][j+1]=v+(x<'_'),X
for i in r(len(X)):s=s[:i]+' '*('B'>X[i])+s[i:];t=t[:i]+' '*('R'==X[i])+t[i:]
print s+'\n'+t+'\n'+X

Try it online!
Uses 'ARM_' instead of 'ARM '
Works by building up the Levenshtein matrix, and then traversing backwards to find the operations. Now builds the operation-string at the same time as the Levenshtein matrix, as in Arnauld's JS answer
1: More bytes, as it did not work if the first string was a single character.
2: Switched to building the combinations in the Levenshtein matrix.

+1 for taking less than 60 seconds for 6 character words like my initial (failed) attempt lol

Nice answer! +1 from me. Since I never program in Python I can't really help you with the golfing, except for one thing: m+i+1 can be m-~i.

You can use a tab instead of double spaces on line 7.

You can get to 463 bytes by reducing the wile loop to one line: while i+j<n+m:v,A=(L[i]+[m,m])[j:j+2];R,M=(L[i+1]+[m,m])[j:j+2];d=min(A,R,M);q=M==d or(R==d)*2;r+=' '*(d==v==M)or'AMR'[q];i+=q>0;j+=q<2

D, 351 345 bytes
-6 bytes thanx to KevinCruijssen
string f(string a,string b){import std.algorithm;string x,y,z;size_t i,j,k;foreach(c;levenshteinDistanceAndPath(a,b)[1]){final switch(c)with(EditOp){case none:x~=a[i++];y~=b[j++];z~=" ";break;case substitute:x~=a[i++];y~=b[j++];z~="M";break;case insert:x~=" ";y~=b[j++];z~="A";break;case remove:x~=a[i++];y~=" ";z~="R";}}return x~"\n"~y~"\n"~z;}

Try it online!

You can golf six bytes by removing the last break;. +1 though, first time I'm seeing the programming language D.

Mathematica, 250 256 259 384 bytes
~0.00035 seconds for the java code case.
(i=o=p="";a=Array;r=StringLength;If[Length@#>0,g=#&@@#;h=#[[2]];u=r@g;v=r@h;i=i<>g;o=o<>h;w=Abs[v-u];k=a[" "&,w];If[u<v,i=i<>k,o=o<>k];p=p<>a["M"&,u~Min~v];p=p<>a[If[u>v,"R","A"]&,w],i=i<>#;o=o<>#;p=p<>a[" "&,r@#]]&/@SequenceAlignment[#,#2];{i,o,p})&

Usage: f["ABCDE", "ABCDF"]
Try it online!
The code is based on a fact that SequenceAlignment works by default on

With the default setting SimilarityRules->Automatic, each match
  between two elements contributes 1 to the total similarity score,
  while each mismatch, insertion, or deletion contributes -1.

Namely, the scoring is calculated by M, A and R, accordingly.
Example:

Hmm, I've never programmed in Mathemetica, but isn't it possible to change i="";o="";p=""; to i="";o=i;p=i; to reduce 2 bytes?

What about i=o=p=""?

@DavidC Yes I had realized that and changed it already. thank you anyway

Python 2, 310 bytes
from difflib import*
a,b=input()
U,j=[],' '
for g,s,t,x,y in SequenceMatcher(0,a,b).get_opcodes():
	g,Y,T=g[0],y-x,t-s
	z,A,B=Y-T,a[s:t],b[x:y]
	if'q'<g:U+=[A+z*j,B+j*-z,'M'*min(T,Y)+'A'*z+'R'*-z]
	if'e'==g:U+=[A,B,j*Y]
	if'i'==g:U+=[j*Y,B,'A'*Y]
	if'e'>g:U+=[A,j*T,'R'*T]
for e in[0,1,2]:print''.join(U[e::3])

Try it online!
Using difflib.SequenceMatcher that computes an alignment between two strings

This seems to give some incorrect results for some of the other test cases. More particular: "This_is_an_example_text","This_is_a_test_as_example"

@KevinCruijssen thanx ,I just fixed it ^_^

Nice, gj! But umm.. the third test case (and fourth as well) is also incorrect unfortunately. One of the two lines should be unmodified (except for leading/trailing spaces). Both lines currently contain spaces in the middle.

@KevinCruijssen thanx again, I’m fixing it

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
How many unique primes?
One way to represent a natural number is by multiplying exponents of prime numbers.  For example, 6 can be represented by 2^1*3^1, and 50 can be represented by 2^1*5^2 (where ^ indicates exponention).  The number of primes in this representation can help determine whether it is shorter to use this method of representation, compared to other methods.  But because I don't want to calculate these by hand, I need a program to do it for me.  However, because I'll have to remember the program until I get home, it needs to be as short as possible.
Your Task:
Write a program or function to determine how many distinct primes there are in this representation of a number.
Input:
An integer n such that 1 < n < 10^12, taken by any normal method.
Output:
The number of distinct primes that are required to represent the input, as outlined in the introduction.
Test Cases:
24      -> 2 (2^3*3^1)
126     -> 3 (2^1*3^2*7^1)
1538493 -> 4 (3^1*11^1*23^1*2027^1)
123456  -> 3 (2^6*3^1*643^1)

This is OEIS A001221.
Scoring:
This is code-golf, lowest score in bytes wins!

So many prime questions recently! I love it.

Would the downvoter please explain why they downvoted?  I would love to fix any issues.

Related

The reason behind the downvote might be its triviality. As far as I could see, there are 3 situations when it comes to golfing languages : 1. built-in 2. chain of two built-ins 3. chain of 3 built-ins (I personally have three 2-byte answers); I don't know if that is a solid reason for a downvote, but it is a possible cause

Could be, but I would appreciate if one of the three downvoters would have commented telling me that.  While it is trivial in golfing languages, there are a few interesting solutions in non golfing languages, which are the ones I wanted to see when I posted this challenge.  After all, there are many challenges on the site which are trivial for golflangs, but produce interesting non-golflang solutions.

It would beneficial to include a prime in the test cases. Also, some languages/approaches are hard to test for large numbers. A few smaller test cases would be nice.

In case anyone is wondering, the highest possible result given the input range is 12.

MATL, 4 3 bytes
-1 byte thanks to Luis Mendo
YFz

Try it online!
YF         Exponents of prime factors
  z        Number of nonzeros

Original answer:
Yfun

Try it online!
A verYfun answer.
          (Implicit input)
Yf         Prime factorization
  u        Unique
   n       Numel
           (Implicit output)

Why fun? -- ;-)

Crossed out 4 is still regular 4

05AB1E, 2 bytes
another pretty boring answer...
fg

A full program accepting a numeric input and printing the result
Try it online!
How?
fg - implicitly take input
f  - get the prime factors with no duplicates
 g - get the length
   - implicit print

Mathematica, 7 bytes
PrimeNu

Yup, there's a built-in.
Mathematica, 21 bytes
Length@*FactorInteger

The long way around.

What's the reason for the asterisk? Isn't Length@FactorInteger the same?

Length@*FactorInteger produces a pure function: the composition of Length and FactorInteger. I can define fun=Length@*FactorInteger and then call fun[1001]. On the other hand, Length@FactorInteger would mean Length[FactorInteger] and evaluate to 0.

Gaia, 2 bytes
Yet another pretty boring answer... --- J. Allan
ḋl

Try it online!

ḋ - Prime factorization as [prime, exponent] pairs.
l - Length.

Bash + GNU utilities, 33

1 byte saved thanks to @Dennis

factor|grep -Po ' \d+'|uniq|wc -l

Try it online.
Explanation
factor|                            # Split input into prime factors
       grep -Po ' \d+'|            # group factors onto lines
                       uniq|       # remove duplicates
                            wc -l  # count the lines

grep -Po ' \d+' saves a byte over tr \  \\n|sed 1d.

Unfortunately, grep -Po '( \d+)\1*' fails for input 46.

@Dennis thanks - I fixed it using your original suggestion

Python 2, 56 bytes
f=lambda n,p=2,k=1:n/p and[f(n,p+1),k+f(n/p,p,0)][n%p<1]

Is this a port of Dennis' answer here perchance?

@JonathanAllan Yes, modified to count unique prime factors instead.

Retina, 31 30 bytes
&`(?!(11+)\1+$)(11+)$(?<=^\2+)

Input is in unary.
Thanks to @MartinEnder for golfing of 1 byte!
Try it online! (includes decimal-to-unary converter)
How it works
Since the program consists of a single regex with the & modifier, Retina simply counts the amount of overlapping matches. The input is assumed to consist of n repetitions of 1 and nothing else.
The negative lookahead
(?!(11+)\1+$)

matches at locations between 1's that are not followed by two or more 1's (11+), followed by one or more repetitions of the same amount of 1's (\1+), followed by the end of input ($).
Any composite number ab with a, b > 1 can be written as b repetitions of a repetitions of 1, so the lookahead matches only locations followed by p repetitions of 1, where p = 1 or p is prime.
The regex
(11+)$

makes sure p > 1 by requiring at least two 1's (11+) and stores the tail of 1's in the second capture group (\2).
Finally, the positive lookbehind
(?<=^\2+)

verifies that the entire input consists of kp occurrences (k ≥ 1) of 1, verifying that p divides the input.
Thus, each match corresponds to a unique prime divisor p.

Jelly, 3 bytes
a pretty boring answer...
ÆFL

A monadic link taking a number and returning a number
Try it online!
How?
ÆFL - Link: number, n
ÆF  - prime factorisation as a list of prime, exponent pairs
  L - length

How did you miss Æv?

It was easy - I've never had a use for it and didn't search the list on the wiki.

How do you type jelly characters without atoms list and quicks list?

Æ is alt code 0198. 2. You can set up a keyboard  (I have not). 3. The code page.

CJam, 7 5 bytes
Thanks to Martin Ender for 2 bytes off!
{mF,}

Anonymous block (function) that expects the input number on the stack and replaces it by the output number.
Try it online! Or verify all test cases.
Explanation
{   }   e# Define block
 mF     e# List of (prime, exponent) pairs
   ,    e# Length

Ohm v2, 2 bytes
ml

Try it online!
The two built-ins are right next to each other in the documentation lol.

Jelly, 2 bytes
Yet another pretty boring answer... --- J. Allan
Æv

Try it online!
A built-in.

Alice, 10 bytes
/o
\i@/Dcd

Try it online!
Explanation
/o
\i@/...

This is just the standard framework for linear arithmetic-heavy programs that need decimal I/O. The actual program itself is then just:
Dcd

Which does:
D    Deduplicate prime factors. Does what it sounds like: for every p^k which
     is a divisor n, this divides n by p^(k-1).
c    Push the individual prime factors of n. Since we've deduplicated them
     first, the number of factors is equal to the value we're looking for.
d    Push the stack depth, i.e. the number of unique prime factors.

JavaScript 45 bytes
*For @SEJPM request an explanation :
what im doing here is this- im going from 2 - n (which changes, and eventually will be the biggest prime factor)- now if the current number divide n i want to count it only once(even though it can be a factor of 2*2*2*3 - 2 is counted once)- so the "j" comes to the picture, when j is not specified in the call of the funcion - j will receive the value of "undefined" , and when n%i == 0 then i call the function with j=1 in the next call) - and then i only add 1 when j equals undefined which is !j + Function(n/i,i,(j=1 or just 1)). i dont change i in this matter becuase it may still be divisible by i again(2*2*3) but then j will equal 1 and it will not count as a factor.
hope i explained it well enough.

P=(n,i=2,j)=>i>n?0:n%i?P(n,i+1):!j+P(n/i,i,1)

console.log(P(1538493)==4);
console.log(P(24)==2);
console.log(P(126)==3);
console.log(P(123456)==3);

if the last prime is very big than it will have max call stack- if its an issue i can make an iterative one

Would you mind writing an explanation for this answer? It seems to use an usual approach from the rest of the answers.

@SEJPM i added some explanation there

FYI we may assume infinite call stacks / infinite resources for the majority of code-golf challenges (basically unless the question states otherwise).

Brachylog, 3 bytes
ḋdl

Try it online!
Explanation
ḋ      Prime decomposition
 d     Remove duplicates
  l    Length

Python 3, 68 67 bytes
1 byte removed thanks to @Mr.Xcoder
lambda n:sum(n%k<all(k%j for j in range(2,k))for k in range(2,n+1))

This times out for the largest test cases. Try it online!

67 bytes

Pyth, 3 bytes
l{P

Test suite
Length (l) of set ({) of prime factors (P) of the input.

Husk, 3 bytes
Lup

Try it online!
Explanation
  p  -- prime factors
 u   -- unique elements
L    -- length

Actually, 2 bytes
Yet another pretty boring answer... --- J. Allan
yl

Try it online!
The first character can be replaced by w.

That's enough, dude... :P

@icrieverytim I promise this is my last golfing-language answer (I only have 4 :P)

Pyke, 3 bytes
P}l

Try it here!

R + numbers, 30 14 bytes
16 bytes removed thanks to @Giuseppe
numbers::omega

Also, here is the Try it online!! link per @Giuseppe.

You may omit the f=function(x) and the (x) as numbers::omega is a function already. However, as numbers is not standard for R, you should make your answer "R + numbers". Also, you should include a TIO link. Still, +1, very nice.

@Giuseppe, you are too nice. Thanks for your help. BTW, in addition to some of your insightful answers, I checked out Tips for golfing in R, as you suggested.  There are some real gems there.  Anywho, I will update my answer with your recommendations.  Also, your MATL solution is very nice (+1 yesterday).

NP, feel free to ping me in chat or comment on an answer of mine if you have questions.

@Giuseppe is there a meta consensus on needing to explicitly state "R + numbers"? It seems like if we state the additional package then we should be able to save the bytes of explicitly calling it with numbers::. Otherwise, to me it's the same as using an import in any other language.

(scrolls down and sees a python example of this...) I guess I'm wondering about a broader meta consensus, then. It just sort of seems silly to me.

@BLT yeah, something like this. I do think it's fair since you have to assume that a package like numbers is installed on the system at the very least.

@BLT I agree with Giuseppe. Otherwise the code isn't self contained (IMO it feels sneaky if you don't). Also, I'm not sure about how other languages work, but with R as long as the package is installed, library or require (the analogue of import) isn't necessary.

@Giuseppe Thank you, that link is perfect. @JosephWood That's true, but you still have to invoke the library with foo::, which costs a few bytes.

Convex, 3 bytes
mF,

Try it online!

Japt, 5 4 bytes
â èj

Try it
Get the divisors (â) and count (è) the primes (j).

Haskell, 58 bytes
-4 bytes thanks to @Laikoni
f n=sum[1|x<-[2..n],gcd x n>1,all((>)2.gcd x)[2..x-1]]

Try it online!
Explanation
Essentially generates all primes at most as large as n and filters them for being a factor of n and then takes the length of the result.
f n=                                                   -- main function
    sum[                                             ] -- output the length of the list
        1|x<-[2..n],                                   -- consider all potential primes <=n
                                                       -- and insert 1 into the list if predicates are satisfied
                    gcd x n>1,                         -- which are a factor of n
                              all(          )[2..x-1]  -- and for which all smaller numbers satisfy
                                  (>)2.                -- 2 being larger than
                                       gcd x           -- the gcd of x with the current smaller number

You can use sum[1|x<- ... ] instead of length.

Pari/GP, 5 bytes
I don't know why it is called nu in Mathematica but omega in Pari/GP.
omega

Try it online!

ARBLE, 28 bytes
len(unique(primefactors(n)))

Try it online!
This is a very literal solution

I was looking at this and going "Hey, wait a minute, this is a snippet!" And then I see... is this supposed to be a non-esoteric language with implicit IO?!

@icrieverytim Congratulations, you have discovered one of the main reasons this language exists.

Python 2,  63  55 bytes
A much more interesting answer...
-8 bytes thanks to Jonathan Frech (use an argument with a default for the post-adjustment of the result of primes from 0 to 1 -- much better than a wrapping lambda!!)
f=lambda n,o=1:sum(n%i+f(i,0)<1for i in range(2,n))or o

A recursive function taking a positive integer, n, and returning a positive integer, the count.
Try it online! Really inefficient, don't even bother with the other test cases.

55 bytes.

@JonathanFrech Thanks, that is much cleaner.

Dyalog APL, 17 bytes
⎕CY'dfns'
≢∪3pco⎕

Try it online!

J, 12 bytes
{:@$@(__&q:)

q: is J's prime exponents function, giving it the argument __ produces a matrix whose first row is all nonzero prime factors and whose 2nd row is their exponents.
We take the shape $ of that matrix -- rows by columns -- the number of columns is the answer we seek.
{: gives us the last item of this two items (num rows, num columns) list, and hence the answer.
Try it online!

Java (OpenJDK 9), 67 bytes
n->{int c=0,p=1;for(;p<n;)if(n%++p<1)for(c++;n%p<1;n/=p);return c;}

Try it online!

Javascript ES6, 56 chars
n=>eval(`for(q=2,r=0;q<=n;++q)n%q||(n/=q,r+=!!(n%q--))`)

Test:

f=n=>eval(`for(q=2,r=0;q<=n;++q)n%q||(n/=q,r+=!!(n%q--))`)
console.log([24,126,1538493,123456].map(f)=="2,3,4,3")

Python 3 + primefac, 50 bytes
from primefac import*
lambda n:len({*primefac(n)})

Python 2 + primefac, 52 bytes
from primefac import*
lambda n:len(set(primefac(n)))

Try it online

Python 2, 50 bytes
f=lambda n,k=2,p=1:n/k and(n%k<p%k)+f(n,k+1,p*k*k)

Try it online!

import sys

X=int(sys.argv[1])
print X
b=2
a=0

while(b<X or b==X):
        if(X%b == 0):
                a=a+1;
                while(X%b==0):
                        X=X/b;
                b=b+1;
        else:
                b=b+1;

print a;

Welcome to PPCG! Could you specify language and bytecount?

Looks like Python 2.


text:
Who's Going? Can you help me?
If Abe goes, then Beth and Diana go. If Beth goes, then Catherine goes. If Catherine goes, then Diana goes. If Diana goes, then Ezra goes. Only three people go. Who goes?
Challenge
Given a list of several pairings of people, such that in each pairing the second person goes if the first person goes, and a positive integer number of people who go, determine one or all possibilities of who goes. You may output either, as long as the output is consistent.
The example above may be represented in input by [(A,B),(A,D),(B,C),(C,D),(D,E)],3, which can be represented as a graph visually as:
A -> B -> C -> D -> E
⤷-------------⤴

If A goes, then everyone must go, so at least 5 people go, which cannot be 3 people.
If B goes, then C, D, and E must go, so at least 4 people go, which cannot be 3 people.
Thus we are left with C, D, and E going, yielding a final output of [C,D,E].
The input [(0,1),(0,3),(1,2),(2,3),(3,4)],3 represents the same situation and is the format given in the test cases (with output [2,3,4]).
We assume that no people other than the people in at least one pairing should be considered. For example, there is no person 5 or F in this example.
I/O
Your program/function must input g, the list of pairings which represents a directed graph, and n, the number of people who will go. Input g may be taken in any format (such as an adjacency matrix) which does not encode additional information and can encode at least 25 people to consider (the example considered 5 people).
You may also (optionally) input p, the list of people, and/or c, the number of people to consider. List of people p given g (sorted). (append L to end to get number of people c).
Your program/function does not have to handle if:

the integer input is greater than the number of people considered.
the integer input is not positive
repeat pairings
reflexive pairings (e.g. (A,A) or (0,0))
impossible situations (e.g. [(A,B),(B,A)],1)

The output should be in any format which can represent a list from 1 to 24 people.
Test Cases
If the output of a test case has an OR in it, your program may return any one or all of the choices.

[(0,1),(1,2),(2,3),(2,5),(5,6),(6,3),(6,7),(7,4)], 1 => [3] OR [4]
[(0,1),(1,2)], 1 => [2]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 1 => [7]
[(1,2),(2,3)], 2 => [2,3]
[(1,2),(3,4)], 2 => [1,2] OR [3,4] OR [2,4]
[(0,1),(1,2),(1,8),(2,3),(3,4),(4,11),(5,4),(5,6),(6,13),(13,20),(13,12),(12,19),(20,19),(4,19),(19,18),(11,10),(10,3),(10,2),(10,9),(9,8),(8,1),(8,7),(18,17),(18,24),(17,24),(24,23),(17,16),(16,23),(24,18),(16,15),(23,22),(22,15),(22,21),(21,14),(14,15)], 1 => [7] OR [15]
[(0,1),(1,0),(0,2),(1,3)], 1 => [2] OR [3]
[(0,1),(1,0),(0,2),(1,3)], 2 => [2,3]
[(0,1),(1,2)], 3 => [0,1,2]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 4 => [8,9,4,7]
[(0,1),(1,0),(0,2),(1,3)], 4 => [0,1,2,3]
[(0,1),(1,2),(2,3),(2,5),(5,6),(6,3),(6,7),(7,4)], 5 => [3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 5 => [4,5,7,8,9]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 6 => [2,3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 7 => [1,2,3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 7 => [3,4,5,6,7,8,9]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 8 => [2,3,4,5,6,7,8,9]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 9 => [1,2,3,4,5,6,7,8,9]
[(0,1),(1,2),(1,8),(2,3),(3,4),(4,11),(5,4),(5,6),(6,13),(13,20),(13,12),(12,19),(20,19),(4,19),(19,18),(11,10),(10,3),(10,2),(10,9),(9,8),(8,1),(8,7),(18,17),(18,24),(17,24),(24,23),(17,16),(16,23),(24,18),(16,15),(23,22),(22,15),(22,21),(21,14),(14,15)], 9 => [14,15,16,17,18,21,22,23,24]

"determine one all possibilities of who goes." So which is it, one or all?

[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,0)], 1 => [7] can't be true because if 7 goes 0 goes as well.

Can the input be the graph matrix?

@orlp fixed that test case and checked/fixed all others.

@LuisMendo Yes, that is what is meant by "any format which does not encode additional information".

Would it be possible to assume that 0 is always a person? Right now there's two test cases that violate this but there's no real reason for it.

If Abe goes then Abe goes. So the graph matrix should always have ones on its diagonal. Correct?

@LuisMendo Yes.

@orlp Renaming people is acceptable if your program requires it. (e.g. letters may be used instead of numbers; this represents the same graph).

Can [(1,2),(2,3)], 2 give [0,3]? This may be related to what olrp asked. Or should it be considered that non-mentioned people (like 0 here) are non-existing?

@Luis Mendo Non-mentioned people don't exist. This was stated in "We assume that no people other than the people in at least one pairing should be considered. "

I think the challenge would have been more interesting if the numbers describing people were consecutive. Non-existing people complicate the challenge unnecessarily in my opinion (the graph is the same)

Husk, 14 10 bytes
~f`öΠFf†€Ṗ

Takes three inputs: number of people to go, 2-row matrix of the constraints, and list of all people involved, in this order.
Returns all possible lists of people who go.
If you want to output only one list, replace the leftmost f by ḟ.
Try it online!
Explanation
The idea is to loop over the size-n subsets of p and keep those that satisfy the condition imposed by g: if the first person in a pair goes, then the second person must go too.
~f`öΠFf†€Ṗ  Implicit inputs, say n=3, g=[[1,3,3],[4,1,4]] and p=[1,2,3,4]
         Ṗ  All n-element subsets of p: [[1,2,3],[2,3,4],[1,3,4],[1,2,4]]
~f          Keep those subsets (say q=[1,2,4]) for which
  `ö        this function gives a truthy (nonzero) result:
       †     Deep map over g:
        €    index in q, or 0 if doesn't occur: [[1,0,0],[3,1,3]]
     Ff      Fold by select (filter second row by truthiness on first row): [3]
    Π        Product: 3

This program is one of those where it's really hard to explain how the program arguments are passed to the correct functions, but I'll try.
First, n is the first argument, so it can be given to Ṗ directly, making it a function that takes a list and returns its n-subsets.
The next two inputs are g and p, and the program's shape at this point is ~(f)(`öΠFf†€)(Ṗn) with parentheses added for clarity.
The operator ~ gives g to `öΠFf†€ and p to Ṗn, and combines the results with f.
Ṗnp is just the n-subsets of p, so that's simple.
The operator ` causes öΠFf†€ to take its arguments in the reverse order, so g is actually the second argument of this function.
The first argument is an element q of Ṗnp, which is extracted by f (filter).
We give q as an argument to €, which becomes a function for testing membership in q, and deep map that over the second argument, which is g.
Then ΠFf are applied to the result.
The role of ö is just to compose ΠFf†€ into one function, which we can then pass on to ` and ~f.

Python 2, 100 98 bytes
g,n=input()
v=k=0
while bin(v).count("1")^n:k=v=k+1;exec"for a,b in g:v|=(v>>a&1)<<b\n"*25
print v

I assume that the people are numbered from 0 to n. g is a list of pairs just like in the question. The output is a number where the ith bit is set if the ith person goes.

Python 3, 97 95 bytes
lambda g,n,c:[k for k in range(2**c)if-1<bin(k).count("1")-n<all(k>>s&1for f,s in g if k>>f&1)]

Try it online!
Takes g as a list of pairs, as in the question, and additionally takes the number of people c. Returns all solutions in form n where bit i of n corresponds to whether or not person i attends.

Wolfram Language (Mathematica), 62 55 bytes
Select[g=#;#2~Subsets~{#3},#==g~VertexOutComponent~#&]&

Try it online!
I/O
Takes as input the following three arguments:

list of she-goes-I-go pairs, as rules (x->y). The first example in the question would be encoded as {A->B,A->D,B->C,C->D,D->E}. Can also take a Mathematica Graph object.
list of people involved. E.g., {A,B,C,D,E}.
number of people we want to go. E.g., 3.

The output is a list of all subsets of people of the right size who could go.
How it works
The older version was fancier, and contained the expression #|##&@@# which I'm very proud of, but this one just uses a built-in. VertexOutComponent computes the set of everyone else who must go, given a group of people who are going; we just Select the Subsets of the given size whose VertexOutcomponent is the same set and no bigger.
-7 bytes: the built-in.


text:
Fuzzy distances to coordinates
This challenge is similar to my previous one, but has a twist that makes it significantly more difficult.
There are n people on a 2D plane. Using distances between them we're going to find their positions. You may make four assumptions:

There are at least 3 people.
The first person is at position (0, 0).
The second person is at position (x, 0) for some x > 0.
The third person is at position (x, y) for some y > 0.

However, all distances are floored to integers! For example, if the actual distance between two people is 4.7 units, your program will see the distance 4 as input instead.
So your challenge is to write a program or function that given a 2D array of floored distances (where D[i][j] gives the distance between person i and j) returns a list of their coordinates.
The challenge here is that you have incomplete information, and must try to extract as much precision as possible. Therefore this challenge is not a code golf, instead it's a code challenge, and the winner is the answer that returns the most accurate results.

Scoring
I will provide a series of arrays of coordinates. It is up to you to turn these arrays into 2D distance matrices and flooring each element in these matrices (if I were to do that here this question would get way too large).
For a certain input use your answer to predict the coordinates of each person. Then, for each person calculate the squared distance between the prediction and actual position. Sum all these and divide by the number of people in the input. That is your score for this input.
The total score of your answer is the average score you get for all of the following inputs:
[(0, 0), (0.046884, 0), (-4.063964, 0.922728), (-3.44831, -6.726776), (-0.284375, -0.971985)]
[(0, 0), (0.357352, 0), (-1.109721, 1.796241), (-7.894467, -3.086608), (-3.74066, -1.528463)]
[(0, 0), (6.817717, 0), (-6.465707, 0.705209), (-2.120166, 3.220972), (-2.510131, 8.401557)]
[(0, 0), (0.394603, 0), (-4.097489, 0.957254), (-5.992811, 1.485941), (-2.724543, -3.925886)]
[(0, 0), (6.686748, 0), (6.088099, 0.22948), (8.211626, -4.577765), (-1.98268, -4.764555)]
[(0, 0), (2.054625, 0), (0.75308, 0.497376), (6.987932, -5.184446), (0.727676, -5.065224)]
[(0, 0), (6.283741, 0), (-1.70798, 5.929428), (2.520053, 6.841456), (-2.694771, -1.816297)]
[(0, 0), (1.458847, 0), (5.565238, 7.756939), (-4.500271, 4.443), (-0.906575, 3.654772)]
[(0, 0), (0.638051, 0), (-2.37332, 0.436265), (-8.169133, -0.758258), (-7.202891, -2.804207)]
[(0, 0), (1.101044, 0), (-1.575317, 6.717197), (-2.411958, -7.856072), (-4.395595, 2.884473)]
[(0, 0), (7.87312, 0), (-0.320791, 2.746919), (-1.4003, 0.709397), (-0.530837, -0.220055), (-3.492505, -7.278485), (2.401834, 2.493873), (0.911075, -5.916763), (4.086665, -5.915226), (2.801287, 5.409761)]
[(0, 0), (0.304707, 0), (-1.709252, 0.767977), (-0.00985, -0.356194), (-2.119593, 3.353015), (1.283703, 9.272182), (6.239, -0.455217), (7.462604, 1.819545), (0.080977, -0.026535), (-0.282707, 6.55089)]
[(0, 0), (3.767785, 0), (0.133478, 0.19855), (-0.185253, -5.208567), (-6.03274, 6.938198), (5.142727, -1.586088), (0.384785, 0.532957), (3.479238, -1.472018), (3.569602, 8.153945), (-0.172081, 2.282675)]
[(0, 0), (0.445479, 0), (-3.3118, 8.585734), (0.071695, -0.079365), (2.418543, 6.537769), (1.953448, 0.511852), (-1.662483, -5.669063), (0.01342, 0.097704), (0.919935, 1.697316), (2.740839, -0.041325)]
[(0, 0), (3.281082, 0), (-6.796642, 5.883912), (-3.579981, -2.851333), (-1.478553, 6.720389), (3.434607, -9.042404), (7.107112, 2.763575), (-4.571583, 1.100622), (-1.629668, 1.235487), (-3.199134, 0.813572)]
[(0, 0), (5.278497, 0), (-4.995894, 3.517335), (-0.012135, 3.444023), (0.364605, -0.49414), (1.73539, 1.265443), (-7.289383, -3.305504), (-7.921606, 5.089785), (-1.002743, -0.554163), (-8.99757, -3.572637)]
[(0, 0), (2.331494, 0), (1.83036, 2.947165), (-5.520626, 1.519332), (5.021139, -4.880601), (-0.318216, -0.063634), (-5.204892, -5.395327), (-0.92475, -0.090911), (-0.19149, -2.188813), (-0.035878, 0.614552)]
[(0, 0), (2.981835, 0), (-3.909667, 2.656816), (-0.261224, -2.507234), (-7.35511, -3.65201), (1.198829, 5.328221), (-5.139482, -4.320811), (-3.253523, 2.367497), (6.254513, 1.565134), (3.13451, 4.595651)]
[(0, 0), (1.059838, 0), (-0.849461, 7.87286), (2.108681, 0.717389), (-0.065587, -0.007163), (2.818824, 5.529878), (2.413443, 4.102863), (-3.050506, -2.541446), (-1.215169, -4.818011), (-1.671743, 2.539397)]
[(0, 0), (5.036602, 0), (-1.627921, 1.813918), (-9.285855, 1.277063), (2.271804, -0.51118), (-7.070704, 2.252381), (6.125956, -4.278879), (1.000949, -1.38177), (-0.67657, -2.747887), (2.820677, -5.718695)]
[(0, 0), (0.733516, 0), (6.619559, 1.368964), (-0.047351, 0.545139), (-4.518243, -7.506885), (3.31011, -4.329671), (3.885474, -1.535834), (-3.952488, -1.94899), (1.402441, 7.538954), (2.385809, 4.042365), (-6.403547, 3.623895), (3.742502, 0.025475), (1.944868, -2.972475), (-0.514566, -1.015531), (-0.08634, 5.140751)]
[(0, 0), (2.374024, 0), (-1.016305, 1.31073), (2.176473, -1.357629), (0.181825, 2.107476), (-0.978214, -3.436398), (0.828254, -0.39516), (2.981311, -6.761157), (1.517599, 5.009197), (8.063442, 0.930487), (4.628231, 7.749696), (3.810604, 4.671208), (1.158015, 2.914197), (-9.230353, -0.473591), (-9.031469, -4.206725)]
[(0, 0), (5.733822, 0), (1.394054, 1.432354), (1.556614, 5.691443), (3.665168, 7.199478), (-0.670337, 0.396217), (4.144468, 2.959243), (-6.129783, -7.048069), (-3.230162, 3.116924), (-6.365913, 3.727042), (-0.174385, 0.253418), (-0.454495, -4.415929), (5.815488, 1.443031), (-4.288448, 0.619174), (1.957015, 0.784202)]
[(0, 0), (6.550779, 0), (-8.592692, 1.728506), (-6.460692, 2.344509), (8.359129, 4.578714), (3.593451, -4.172634), (8.697976, -2.379752), (4.27242, 5.296418), (2.920394, -4.520174), (0.662004, 2.171769), (1.879771, -1.873537), (0.769374, 3.570321), (-3.438699, -3.255416), (3.23342, -3.220256), (-0.002136, -5.646753)]
[(0, 0), (5.013665, 0), (-0.543516, 9.981648), (8.378266, 5.33164), (4.759961, -2.007708), (2.88554, 1.069445), (-6.110542, -6.253516), (0.292062, -0.052982), (-4.869896, -1.251445), (1.61841, 7.980471), (-0.313257, 0.515709), (8.673848, -2.269644), (-0.446207, -0.568228), (3.015721, -2.819861), (1.160386, -5.897356)]
[(0, 0), (0.437257, 0), (-3.127834, 8.941175), (0.785858, 1.99155), (2.005894, -6.723433), (1.332636, -6.214795), (3.149412, 7.17296), (-5.350834, -5.106189), (1.447561, 0.910621), (3.032259, -7.977927), (1.520669, 5.121877), (-1.075969, 0.098313), (1.015673, -5.244922), (3.575391, 5.270148), (-9.160492, 2.943283)]
[(0, 0), (3.63663, 0), (5.448045, 8.287277), (1.314494, -0.164441), (-1.941398, 4.223086), (5.025181, 0.495811), (-8.466786, -2.933392), (-0.139755, 0.730451), (-0.098497, -0.587856), (-3.337111, -1.238969), (2.142947, 2.521078), (0.352537, 5.4194), (-4.49191, 5.261929), (2.198984, -3.781113), (3.525393, 1.150581)]
[(0, 0), (4.540155, 0), (-7.248917, 2.368607), (2.434071, 1.763899), (3.990914, 1.135211), (-5.422214, -5.785259), (0.526037, -0.888364), (-0.370255, 8.515669), (0.77125, 4.48859), (3.9838, -2.3101), (-2.993973, -0.775446), (-1.731491, -1.028441), (-0.184254, 0.281876), (0.048732, 0.222435), (0.108646, -0.344878)]
[(0, 0), (4.934251, 0), (7.472259, 4.693888), (0.057108, -0.038881), (-0.276457, -0.157808), (-6.745232, -0.357168), (5.979037, -0.653591), (-3.969328, -6.050715), (4.19821, -1.883165), (-4.294607, -0.407446), (-6.11544, 0.480539), (1.193587, -1.028919), (-0.387421, 2.036394), (5.78394, 1.333821), (4.178077, 4.286095)]
[(0, 0), (7.547164, 0), (0.989783, 1.074185), (0.192979, 0.210046), (6.528904, 0.400088), (5.602168, 5.791553), (4.058506, 3.995028), (-1.033977, -5.44405), (5.767663, -6.702417), (4.401684, -3.097193), (-0.821263, 4.624133), (6.031465, 6.544092), (7.188866, 1.599597), (5.327328, 3.51571), (1.305662, 7.488827)]
[(0, 0), (0.638053, 0), (7.279348, 5.416438), (-6.495944, -1.385692), (5.348119, 6.89312), (-5.145817, -5.640294), (2.909321, -3.139983), (7.052144, 3.902919), (2.467506, 1.362787), (3.469895, -7.977336), (7.598683, -5.947955), (-0.679492, 9.140908), (-3.310304, 3.134427), (-0.83399, 5.797306), (4.08935, 0.830119), (-7.764758, -4.403114), (5.183087, -8.528744), (-0.75072, 6.163092), (-0.692329, -0.225665), (2.0628, -2.008365)]
[(0, 0), (9.468635, 0), (2.005581, 2.669352), (3.416536, 6.9941), (-3.293394, 0.864229), (-1.044833, 2.243219), (6.011018, 4.014313), (-0.959567, 9.620265), (-1.855409, 1.890371), (-0.629015, -1.383614), (4.087875, -2.203917), (3.286183, -7.748879), (-7.781181, -5.295325), (3.28653, -0.930535), (3.973893, -1.784441), (-7.7541, 4.355823), (1.522453, -1.960952), (5.085025, -1.511887), (8.401342, -2.139507), (-1.727888, 0.7952)]
[(0, 0), (8.617779, 0), (-7.012573, 5.883927), (-3.508725, -6.838323), (6.676063, 6.884947), (8.297052, -0.134775), (7.416737, 5.915766), (-5.10108, -7.183776), (-4.651823, 5.434926), (-1.099239, -0.238062), (-0.313045, 0.354853), (-7.592061, 5.408053), (0.566482, 0.652099), (-3.551817, -3.365006), (8.514655, 4.653756), (-4.249357, -2.130864), (1.181348, -1.22839), (2.469081, 1.110794), (1.831897, -1.552467), (-5.892299, -1.919411)]
[(0, 0), (2.407206, 0), (-6.771008, 0.810524), (-3.840048, -0.152269), (7.109171, -5.609477), (-7.391481, 5.639112), (-8.670299, 2.742321), (0.586435, 4.542551), (-0.442438, 0.107817), (4.31145, -1.409808), (-4.534678, -1.504437), (4.680038, -3.080315), (-4.973063, 5.638478), (6.127056, -7.491446), (2.291953, -2.357609), (3.510856, -9.171005), (3.971143, -8.515823), (0.049413, -5.842664), (1.058161, -0.21883), (7.093364, -3.604422)]
[(0, 0), (6.969461, 0), (4.338403, 5.197497), (0.369553, -0.770371), (8.882643, 1.450294), (2.124852, -1.210185), (-3.046623, -4.395661), (7.716904, 4.60951), (-0.83271, -0.854575), (-2.333383, -0.308884), (-6.347966, 3.124373), (0.832848, -1.892136), (1.446553, 1.613845), (-2.241092, -6.53878), (5.004282, 5.401177), (3.31202, 0.432188), (0.164548, 1.23087), (9.860844, -0.125136), (0.133559, -0.202543), (2.686551, 1.013555)]
[(0, 0), (9.107655, 0), (5.455882, 3.54979), (-0.681513, 2.950275), (7.369848, 4.050426), (5.320211, -8.288623), (-5.315311, 4.632769), (-2.801207, -3.00623), (2.502035, -2.085464), (-0.645319, -4.854856), (3.639806, -8.669185), (-0.732853, 2.379454), (-8.722855, 2.483643), (-0.03048, 1.845021), (-6.904949, -2.596416), (0.685437, 1.042775), (-5.182001, -2.617796), (1.595501, 0.885512), (-8.567463, -0.607195), (-5.456613, 5.81163)]
[(0, 0), (1.669656, 0), (-3.385149, 6.655961), (-1.501983, -0.746686), (1.962876, -0.780073), (0.51437, -4.130592), (1.825567, 0.531272), (-4.188001, 0.514048), (-5.894689, 1.726502), (-1.429067, -3.558197), (4.605078, 2.060605), (1.670708, -8.99749), (5.44004, -5.315796), (-0.619392, 1.785159), (-2.854087, 1.696694), (4.974886, 6.291052), (-0.699939, -5.930564), (-2.35508, -0.057436), (-0.804635, -0.687497), (2.289458, 1.946817)]
[(0, 0), (3.626795, 0), (5.048495, 1.581758), (0.154465, 3.132534), (-4.862419, 7.051311), (3.927243, -0.408956), (-7.41798, -0.313768), (1.987639, -7.957834), (-1.100923, -1.442563), (1.949075, -0.382901), (5.696638, 3.400352), (-1.121574, 1.315934), (-4.37434, 4.937007), (-1.244524, -7.36647), (9.138938, 4.035956), (-0.207342, -4.257523), (-1.298235, 5.950812), (2.17008, 1.116468), (-1.410162, 4.861598), (4.69532, 2.076335)]
[(0, 0), (9.787264, 0), (-4.65872, 0.957699), (-2.813155, -1.174551), (-0.445703, 0.362518), (2.920405, 0.914672), (-1.63431, 0.048213), (-0.534393, -2.389697), (-0.105639, -1.589822), (-0.100723, 8.648806), (-6.894891, 4.8257), (7.417014, 2.868825), (-0.84031, -0.322606), (-0.802219, 1.209803), (7.808668, 1.700949), (-3.270161, -3.463587), (-1.118415, 0.713057), (4.130249, 0.824635), (4.664258, 5.993324), (2.575522, -1.031243)]
[(0, 0), (6.514721, 0), (-2.2931, 3.6007), (3.388059, 1.102576), (-1.777694, -2.809783), (3.431761, 6.534511), (-8.13158, -2.940151), (-4.856169, 2.834183), (-0.706068, -0.93294), (-0.393184, -4.989653), (4.480243, -4.107001), (1.681165, 0.611419), (4.442544, -0.536704), (4.90654, -7.356498), (-8.722645, 1.203365), (-2.067292, -4.134382), (-3.002458, 7.891842), (1.398419, -1.279873), (0.237866, 0.010691), (6.879955, -2.882286)]
[(0, 0), (1.421587, 0), (-0.615169, 0.286873), (0.848122, -2.730297), (0.220832, 0.89274), (4.588547, 8.497067), (-5.079677, -8.428552), (-3.170092, 2.418608), (1.309388, -3.658275), (1.639533, -2.364448), (-1.327656, 1.006565), (-0.475542, 0.298309), (5.430131, -8.343581), (8.430933, 4.118178), (-2.090712, -0.470172), (1.146227, -6.664852), (-0.542811, 1.909997), (0.439509, 6.112737), (0.343281, 0.630898), (-3.673348, 5.101854), (-0.072445, 5.784645), (4.895027, -7.960275), (-9.633185, -1.688371), (8.059592, -5.178718), (-2.334299, 1.217686)]
[(0, 0), (5.456611, 0), (0.181969, 2.084064), (0.89351, -2.507042), (1.570701, 1.202458), (0.814632, 1.883803), (2.790854, 5.8582), (0.699228, 2.377369), (-0.463356, 5.162464), (1.166769, 4.739348), (-4.652182, 5.553297), (-1.123396, 4.186443), (-0.327375, 0.45977), (-0.395646, -4.122381), (0.652084, -0.696313), (0.716396, 2.005553), (0.73846, -7.361414), (-1.912492, 3.937217), (-0.162445, -2.681668), (-0.133005, -0.910646), (2.194447, -4.169833), (-3.132339, -3.079166), (-3.078943, -1.410719), (-1.365236, -4.103878), (2.044671, -0.831881)]
[(0, 0), (1.382529, 0), (5.031547, 7.747151), (-0.49526, 0.019819), (-7.918566, -1.919355), (1.046601, -4.397131), (3.113731, 8.325339), (-1.700401, 1.511139), (-2.699135, -5.052298), (3.434862, -2.609676), (-4.506703, -0.424842), (0.154899, 3.782215), (1.373067, 4.412563), (4.548762, 2.096691), (-0.0275, -2.604761), (4.462809, 1.533662), (-2.016089, -3.481723), (7.024583, 6.980284), (0.254207, -7.964855), (-2.055224, -1.374547), (-3.185323, -3.753214), (-0.479636, -7.476727), (2.208698, -6.374003), (0.24381, -0.620774), (-0.551312, -3.796487)]
[(0, 0), (3.442359, 0), (-5.045461, 1.685484), (0.072923, 1.158112), (-1.347292, 2.626515), (1.982477, 4.374474), (-3.188879, -4.020849), (-0.430788, 0.118491), (0.725544, 1.992762), (-2.893352, -4.311321), (-6.871016, -2.359638), (1.406456, 1.734539), (2.029903, 6.151807), (7.565244, 1.948656), (-6.420158, 0.698035), (-4.873019, 3.593625), (9.548917, -0.45405), (-8.701737, -1.872887), (-7.941202, -1.4121), (-5.995713, 0.555241), (-5.704163, -2.868896), (-2.677936, -1.924243), (-3.460593, -8.679839), (0.631064, -0.433745), (1.18902, -1.496815)]
[(0, 0), (6.537782, 0), (-6.75348, 0.404049), (-5.348818, 5.082766), (-3.738518, -7.824984), (4.513721, -7.740162), (-7.707575, 3.393118), (-0.11626, 0.439479), (0.12586, -2.885467), (4.952966, 5.673672), (2.56597, -0.333544), (-4.60141, 2.716012), (-1.865207, 1.826155), (3.234169, -0.966176), (-5.977172, 1.660029), (-7.968728, 0.889721), (-0.028198, 0.153274), (-5.427989, 8.150441), (-3.708225, -0.777001), (3.513778, 0.529579), (6.309027, 0.399666), (0.542878, 1.900558), (-0.633748, -4.971474), (5.340487, -2.474143), (-0.805431, -8.633636)]
[(0, 0), (0.211756, 0), (3.03609, 1.381372), (1.472087, 3.505701), (-0.198393, -0.284868), (4.290257, -7.630449), (-0.120326, -0.047739), (3.167345, -1.144179), (7.791272, 6.043579), (6.125765, -6.3722), (-0.178091, 9.313027), (-4.177894, -0.704969), (-2.950708, 1.716094), (-0.016133, -0.105582), (-5.962467, 6.088385), (0.901462, 0.58075), (2.063274, -0.221478), (-0.430464, 0.9548), (4.824813, -4.037669), (0.863528, 8.321907), (2.693996, -0.380075), (0.879924, 4.243756), (-7.759599, -2.81635), (2.58409, -2.225758), (5.515442, -7.445861)]
[(0, 0), (0.958126, 0), (-0.566246, 3.074569), (2.666409, -4.784584), (-5.490386, 1.820646), (0.505378, 0.261745), (-0.122648, -9.791207), (0.569961, 1.044212), (-8.917451, -1.667965), (-7.374214, -1.193314), (-4.559765, -2.486695), (2.367622, 1.707526), (0.762113, -5.553413), (-9.62438, -2.077561), (-0.072526, -0.072188), (-2.051266, -5.410767), (-6.656983, -1.824092), (1.170361, 2.019313), (2.689391, -3.998207), (1.814094, 1.782214), (0.498034, -9.437937), (0.87507, 0.670687), (-8.114628, 4.823256), (2.693849, 6.952855), (-0.005543, -0.01139)]
[(0, 0), (1.703854, 0), (1.091391, 2.171906), (5.559313, -0.310439), (-0.396107, -0.771272), (-5.136147, 7.769235), (8.969736, 0.885092), (3.541436, -6.530927), (-0.461503, -5.877802), (-6.108795, -5.163834), (3.698654, 3.749293), (8.049228, 2.056624), (-6.022241, -0.657227), (-8.701763, 4.803845), (1.225822, -2.070325), (2.099514, 5.191076), (0.500653, -0.104261), (-0.581698, -5.755634), (-5.150133, -8.269633), (2.559925, 6.839805), (-0.149545, 4.456742), (1.43855, 1.865402), (3.439778, -4.954683), (-4.18711, 7.244959), (0.640683, 0.907557)]
[(0, 0), (6.577004, 0), (0.042196, 0.025522), (8.61361, -0.689878), (5.407545, 1.709241), (-4.724503, 3.123675), (4.329227, -5.283993), (-1.238506, -1.104368), (-0.758244, 1.882281), (3.851691, -0.571509), (-0.229269, 7.452942), (2.833834, -6.742377), (-8.49992, 1.912219), (3.102788, -9.456966), (-0.420271, 2.449342), (4.123196, -0.512152), (5.893872, -3.689055), (-3.801056, -3.486555), (-3.576364, 3.448325), (-0.397213, -0.010559), (-4.519186, 4.525627), (2.720825, 6.0414), (0.918962, -0.430301), (2.217531, -3.056907), (0.912148, -1.487924)]
[(0, 0), (0.170063, 0), (1.088807, 2.795493), (5.884358, -1.914274), (9.333625, -0.111168), (7.168328, 4.042127), (2.558513, -0.146732), (-8.011882, -2.358709), (-0.374469, -6.591334), (2.495474, 1.011467), (0.094949, -0.351228), (7.0753, 1.26426), (6.614842, 4.664073), (-2.777323, 7.287667), (3.280189, -6.811248), (-7.254853, -1.472779), (7.147915, 1.932636), (-3.431701, 3.030416), (-0.863222, -1.177363), (0.512901, -0.258635), (-5.614965, 0.462802), (3.452843, -6.869839), (7.475845, -0.353582), (0.067355, 0.298013), (4.39831, -8.5387)]

It's not allowed to optimize specifically for this set of inputs. I may change these inputs to any others at my discretion.
Lowest score wins.

Problem: If the program result produce the exact same distance matrix as the test case, it is impossible to determine whether the result is correct. I suggest calculate the difference between the distance matrices instead.

@user202729 I don't understand. Can you elaborate?

Assume that the program find coordinates A, and the input coordinates is B (B is different from A), which happens to have the same floored distance matrix. In that case I think the program should not be punished because "guessed" the input coordinates wrongly.

@user202729 Well, I disagree. The whole point of this challenge is to make an algorithm that figures out the best possible guess for the input coordinates with limited information. The fact that there are potential 'false positives' changes nothing about this, in fact it makes the problem more complicated and interesting.

You means, the program have to find the position that minimize the maximize possible error? Like, if the (floored) matrix is [[0,4],[4,0]], the program should return [[0,0],[4.5,0]] so that in the worst case it only wrong for 0.5^2, instead of [[0,0],[4,0]] or [[0,0],[5,0]] where in the worst case it wrong for 1.

@user202729 If your answer would be optimal, yes it would account for that.

I have the feeling that even with the constraints on the position of the first three people, when the input are only pairwise distances, the solution may be correct up to a rotation transformation.
How should we account for that?

@NofP The fact that the second person is guaranteed to be at (x, 0) for some x > 0 eliminates all rotational symmetry.

R, score = 4.708859
require(vegan)
solve_mmds<-function(dpf,noise=0,wgs=rep(1,nrow(dpf))){
  #MMDS
  v = wcmdscale(dpf+noise,2,add=TRUE,w=wgs)

  #center on first point
  v = sweep(v,2,v[1,])

  #rotate to adjust second point
  alpha = atan2(v[,2],v[,1])
  alpha_rot = alpha - alpha[2]
  radius = sqrt(apply(v^2,1,sum))
  v = cbind(cos(alpha_rot), sin(alpha_rot))*radius

  #flip to adjust third point
  if(v[3,2]<0){
    v[,2]=-v[,2]
  }

  #return
  v
}

N_input = length(input_data)
err_runs = rep(0,N_input)

for(i_input in c(1:N_input)){

  p = matrix(input_data[[i_input]],ncol=2,byrow=TRUE)
  n = nrow(p)

  dp = as.matrix(dist(p,upper=TRUE,diag=TRUE))
  dpf = floor(dp)

  v = solve_mmds(dpf)
  err_runs[i_input] = mean(apply( (p-v)^2, 1, sum))

  cat("test #", i_input," MSE:", err_runs[i_input],"\n")
}

cat("Average error: ", mean(err_runs)," \n")

Try it online
The core of the program is based on the Metric Multi-Dimensional Scaling (MDS) approach, which solves precisely the problem described by the OP. The idea is to start from a collection of dissimilarities between entities and infer the coordinates of the system. Some post-processing is required to rotate, translate and flip the solution.
There are at least three functions available in R to perform MDS. There is also one in sklearn in Python, in case. In the code above I settled for the weighted mds variant (function wcmdscale), mostly due to the possibility to add weights and to a slightly better performing correction for negative eigenvalues. There is a core function in R, called cmdscale, which could be used instead, and would result in a score of 5.77.
The code provided is predisposed to accept weights, as well as noise in the floored distance matrix. After testing, it seemed best to not use any of these options.
Sadly, the package "vegan" is not available on TIO. So, no live demonstration: my apologies for this inconvenience. Works on TIO like a charm.
Interestingly, the program significantly underperforms on the last two examples. Adding noise can help, but it worsens the performance on every other test case. It would be interesting to find out what makes these two test cases particularly difficult.

So what is the score for each tests? Also you can ask Dennis to add language / language feature to TIO at talk.tryitonline.net .

TIO works now. The sample code prints out the scores for each test.

C++ (gcc), score = 5.94258
#ifndef _GLIBCXX_DEBUG
#define NDEBUG
#endif // _GLIBCXX_DEBUG

#include <iostream> //{ and more includes
#include <vector>
#include <string>
#include <sstream>
#include <array>
#include <cstdio>
#include <cmath>
#include <random>
#include <cassert>
#include <limits>
//}

template <typename T>
struct point { //{
    T x, y;
    point () {};
    point (T x1, T y1) : x (x1), y (y1) {};
    point operator+(point p) const { return point(x+p.x, y+p.y); }
    void operator+=(point p)       { x+=p.x; y+=p.y; }
    point operator-(point p) const { return point(x-p.x, y-p.y); }
    void operator-=(point p)       { x-=p.x; y-=p.y; }
    point operator*(T a)     const { return point(x*a, y*a);}
    void operator*=(T a)           { x *= a; y *= a; }
    T norm()                 const { return x * x + y * y; }
    T dot  (point p)         const { return x*p.x + y*p.y; }
    T cross(point p)         const { return x*p.y - y*p.x; }
    bool operator==(point<T> p1) const { return x==p1.x && y==p1.y;}
    bool operator!=(point<T> p1) const { return ! (*this == p1);}
    bool operator<(point<T> p1)  const {
        if (x != p1.x) return x < p1.x;
        return y < p1.y;
    }
    template <typename T1>
    operator point<T1> () const {
        return point<T1>(x, y);
    }
};

template <typename T>
std::istream& operator>> (std::istream& str, point<T>& pt) {
    str >> pt.x >> pt.y;
    return str;
}

template <typename T>
std::ostream& operator<< (std::ostream& str, point<T> pt) {
    str << "(" << pt.x << ", " << pt.y << ")";
    return str;
}//}

typedef point<double> pt;

//{ Additional functions, for point<real_type> only (specialize for double here)
double angle(pt p) {
	return std::atan2(p.y, p.x);
}

pt rotate(pt p, double angle) {
	double sin = std::sin(angle), cos = std::cos(angle);
	return pt(p.x * cos - p.y * sin, p.x * sin + p.y * cos);
}

pt normalize(pt p) {
	return p * (1/std::sqrt(p.norm()));
}
//}

std::array<bool, 0x80> const valid_double_start = [](){
	std::array<bool, 0x80> valid_double_start;
	for (size_t i = 0; i < valid_double_start.size(); ++i)
		valid_double_start[i] = false;
	for (char c = '0'; c <= '9'; ++c)
		valid_double_start[c] = true;
	valid_double_start['-'] = valid_double_start['.'] = true;
	// there are also 'e' and probably 'p' but they are not at
	// the begin of a double value string representation
	return valid_double_start;
}();

double score(std::vector<pt>const& pts1, std::vector<pt>const& pts2) {
	double result = 0;
	for (size_t i = 0; i < pts1.size(); ++i)
		result += (pts1[i] - pts2[i]).norm();
	return (result / pts1.size());
}

std::vector<std::vector<double>> distmatrix (std::vector<pt>const& pts) {
	std::vector<std::vector<double>> result (pts.size(), std::vector<double>(pts.size()));
	for (size_t i = 0; i < pts.size(); ++i) {
		for (size_t j = 0; j < i; ++j)
			result[i][j] = result[j][i] =
			std::floor(std::sqrt((pts[i] - pts[j]).norm()));
//		result[i][i] = 0; // implicit when initialize 'result' vector
	}
	return result;
}

std::vector<pt> normalize (std::vector<pt> pts) {
	for (size_t i = 1; i < pts.size(); ++i) pts[i] -= pts[0];
	pts[0] = {0, 0};
	double angle = - ::angle(pts[1]);
	for (size_t i = 1; i < pts.size(); ++i) pts[i] = rotate(pts[i], angle);
	pts[1].y = 0;
	if (pts[2].y < 0)
		for (size_t i = 2; i < pts.size(); ++i) pts[i].y = -pts[i].y;
	return pts;
}

unsigned nDiff (std::vector<std::vector<double>> mat1, std::vector<std::vector<double>> mat2, double eps = 1e-10) {
	unsigned result = 0;
	assert(mat1.size() == mat2.size());
	for (size_t i = 1; i < mat1.size(); ++i)
		for (size_t j = 0; j < i; ++j)
			result += std::abs(mat1[i][j] - mat2[i][j]) > eps;
	return result;
}

std::vector<pt> pts; // use global variable to print progress

int constexpr n_iteration = 200;
std::vector<pt> solve_with_seed (
	std::vector<std::vector<double>>const& distmatrix, int seed
) {

	std::mt19937 engine (seed);
	std::vector<pt> result; result.reserve(distmatrix.size());
	std::uniform_real_distribution<double> dist (-100, 100);
	for (size_t i = 0; i < distmatrix.size(); ++i)
		result.emplace_back(dist(engine), dist(engine));

	for (int iteration = 0; iteration < n_iteration; ++iteration) {
		#ifndef NDEBUG
		if (iteration % 10 == 0) {
			auto norm_result = normalize(result);
			std::clog << "Iteration " << iteration << "; "
			<< "score = " << score(norm_result, pts) << '\n';
			std::clog << "[";
			for (pt p : norm_result) std::clog << p << ", ";
			std::clog << "\b\b]";

			std::clog << " (nDiff = " << nDiff(distmatrix, ::distmatrix(norm_result)) << ")\n";
		}
		#endif
		for (size_t i = 1; i < pts.size(); ++i)
			for (size_t j = 0; j < i; ++j) {
				pt vec_IJ = result[j] - result[i];
				double dist = std::sqrt(vec_IJ.norm()),
				floor_expected = distmatrix[i][j];
				double ndist = (dist + (floor_expected + .5)) / 2;
				ndist = std::max(floor_expected, ndist);
				ndist = std::min(floor_expected + 1, ndist);

				double delta_dist = (dist - ndist) / 2;
				vec_IJ = normalize(vec_IJ) * delta_dist;
				result[i] += vec_IJ;
				result[j] -= vec_IJ;

//				std::clog << "Numerical error = " << std::sqrt((result[i] - result[j]).norm()) - ndist << '\n';
			}
	}
	return normalize(result);
}

std::vector<pt> solve (
	std::vector<std::vector<double>>const& distmatrix
) {
	// just going to try some random values of seed.
	std::vector<pt> result; int minDiff = std::numeric_limits<int>::max();
	for (int seed : {123456789,987654321,69850,68942,4162,12012}) {
		std::vector<pt> r = solve_with_seed(distmatrix, seed);
		int d = nDiff(distmatrix, ::distmatrix(r));
		if (d < minDiff) {
			minDiff = d;
			result = r;
		}
	}
	return result;
}

int main() {
	std::string str;
	double sumscore = 0; unsigned ntest = 0;
	while (std::getline(std::cin, str)) {
		if (str.empty()) break;
		std::stringstream sst (str);
		std::vector<double> values;
		while (true) {
			int c = sst.peek();
			while (c != EOF && !valid_double_start[c]) {
				sst.get();
				c = sst.peek();
			}
			if (c == EOF ) break;
			double val;
			if (!(sst >> val)) {
				std::clog << "Invalid input. Stop reading.\n";
				break;
			}
			values.push_back(val);
		}
		if (values.size() % 2 != 0) {
			std::clog << "Number of double values is odd: " << values.size()
			<< ". Assuming the last value (" << values.back() << ") is redundant.\n";
			values.pop_back();
		}

		pts.resize(values.size() / 2);
		for (size_t i = 0; i < pts.size(); ++i) {
			pts[i].x = values[2*i];
			pts[i].y = values[2*i+1];
		}

		if (pts.size() < 3) {
			std::clog << "Need at least 3 points. Ignore input.\n";
			continue;
		}

		auto distmatrix = ::distmatrix(pts);

		std::vector<pt> result_pts = solve(distmatrix);

		double score = ::score(pts, result_pts);
		std::cout << "Test #" << ++ntest << " score: " << score << ", "
		<< "number of difference in distance matrix: " << nDiff(distmatrix, ::distmatrix(result_pts)) << '\n';
		sumscore += score;
	}

	std::cout << "Final score = " << (sumscore / ntest) << '\n';
}

Try it online!
The main part of the code is the solve function, which is given a floored distance matrix (as a 2D vector of double) and output a vector of point<double>. The rest of the code are score-calculator.
Idea: Start with a (seeded) random set of points, loop n_iteration = 200 times the operation: For each pairs of point, get their current distance and expected distance (which is estimated to be equal to the distance in the floored input matrix + 0.5), and then change the position of those two points to an appropriate position nearer to the expected distance.
For this program, the new length is calculated as min(max((old_length + expected_length) / 2, expected_length + 0.5), expected_length - 0.5, which is twice closer to the expected_length if the old_length is sufficiently close, and force it to change such that the absolute difference between new length and expected_length is no more than 1 if old_length is more than 2 units apart from the expected_length.
It also tries multiple seeds, and then pick the seed which gives least error in the resulting distance matrix.