text:
Implement Lazy Drop Sort
This challenge already describes dropsort. However, I'm kinda lazy and I really only need my array to be a bit more sorted than before, it doesn't need to be sorted all the way.
In Drop Sort, we drop every element less than any element before it. In Lazy Drop Sort, we drop every element less than the one strictly preceding it.
Here's an example. Consider the following array:
8 6 9 9 7 2 3 8 1 3

Let's mark every element less than the one before it.
8 6 9 9 7 2 3 8 1 3
  ^     ^ ^     ^

Notice how neither 3 was marked, nor the last 8. They are all larger than the single element to the left of them.
Completing the algorithm, removing the marked elements, we get:
8 9 9 3 8 3

That basically looks more sorted. Kinda. I'm lazy.
Your task, as you may have already deduced, is to implement this algorithm.
Input is an array of at least 1 positive integer between 1 and 9, so you can take a string of digits as well.
This is code-golf, fewest bytes wins!
Additional test cases:
1
1

1 2 3
1 2 3

5 3 1
5

1 2 3 2 1
1 2 3

1 1 1 9 9 9 1 1 1 9 9 9 1 1 1
1 1 1 9 9 9 1 1 9 9 9 1 1

9 9
9 9

5 2 4 2 3
5 4 3

Can it be a function or it must be a complete program?

@rafa11111 Either is fine

In the case it is a function, can the input array be hardcoded in the main program? And can the length of the array be passed as input to the function?

@rafa11111 The input can't be hardcoded in the function itself. It doens't matter how the function gets this input in your test program. You can take an array length only if you're using C/C++ or another language where that's the only way to determine an array's length.

Husk, 4 bytes
m←ġ<

Try it online!
Explanation
m←ġ<
  ġ<    Group the numbers into decreasing sequences
m←      Keep the first element of each sequence

JavaScript (ES6), 28 25 bytes
Saved 3 bytes thanks to @Shaggy
a=>a.filter(n=>~-a<(a=n))

Try it online!

n=>p<=n would have looked awesome ;-)

@ETHproductions For +4 bytes, (n=p)=>p<=(p=n) works fine ;)

this answer is blowing my mind, why doesn't this explode when trying to access p for the first time, when it's not defined yet?

@BrianH. p=0 is a evaluated as a (meaningless) parameter of map() before the loop begins. So p is actually initialized.

@BrianH. And of course I meant a parameter of filter() O_o

Would a=>a.filter(n=>~~a<=(a=n)) work for 26 bytes?

@Shaggy That looks safe. Will update when I'm back in front of a computer. Thanks!

Why ~-a and not just a-1?

@Pavel a is initially set to the input array and a-1 would result in NaN (unless it contains a single integer, in which case it is coerced to this integer).

R, 27 bytes
(l=scan())[c(T,diff(l)>=0)]

Try it online!

MATL, 9 8 bytes
Saved one byte thanks to Giuseppe.
0yd0<h~)

Try it online!

Explanation:
0                 % Push a zero
 y                % Implicitly grab the input and duplicate it.
                  % Stack: [8 6 9 9 7 2 3 8 1 3], 0, [8 6 9 9 7 2 3 8 1 3]
  d               % The difference between each number of the last element:
                  % Stack: [8 6 9 9 7 2 3 8 1 3], 0, [-2, 3, 0, -2, -5, 1, 5, -7, 2]
   0<             % Which are negative?
                  % Stack: [8 6 9 9 7 2 3 8 1 3], 0, [1 0 0 1 1 0 0 1 0]
     h            % Concatenate. Stack: [8 6 9 9 7 2 3 8 1 3], [0 1 0 0 1 1 0 0 1 0]
      ~           % Negate. Stack: [8 6 9 9 7 2 3 8 1 3], [1 0 1 1 0 0 1 1 0 1]
       )          % Index. Stack: [8 9 9 3 8 3]

Perl 5.10.0 + -nl, 16 bytes
$f>$_||say;$f=$_

Try it online!

Translation to Perl 6 perl6 -ne '$/>$_||.say;$/=$_'

@Brad perl6 is a different language (it's not even backwards-compatible) Post it!

I wrote one that was more idiomatic Perl 6, but it was longer. Also one of the reasons I post here is to show off the language, and to explain it. Posting that translation does nothing but show that it is a slightly more verbose version of Perl. Basically it satisfies none of the reasons why I post on this site.

Haskell, 29 bytes
f s=[b|(a,b)<-zip(0:s)s,a<=b]

just a simple list comprehension.

Japt, 8 7 bytes
Saved 1 byte thanks to @Oliver
k@>(U=X

Test it online!
Alternatives:
f@T§(T=X
k@ä>0 gY
i0 ò> mÅ c

Came up with the exact same solution :)

Java 8, 66 55 48 bytes
l->{for(int i=0;;)if(i>(i=l.next()))l.remove();}

-11 bytes after a tip from @OlivierGrégoire.
-7 more bytes thanks to @OlivierGrégoire.
Explanation:
Try it online.
l->{                     // Method with Integer-ListIterator parameter and no return-type
  for(int i=0;;)         //  Loop over all items
    if(i>(i=l.next()))   //   If the current item is larger than the next
      l.remove();}       //    Remove this next item

Why does everyone start using ~0 when it's basically -1. Personally I would choose the more intuitive solution if the byte-count is the same length (except for while(...) vs for(;...;), in which case I prefer the for. Thanks for another -7 bytes, though. :)

It's because I'm bad with 2-complement... I'm so bad I wanted to mean Integer.MIN_VALUE (which is then 1<<31, I guess...) ;-)

Stax, 5 bytes
âÿ╠╦░

Run and debug this online
Unpacking, ungolfing, and commenting the code, we get this.
Z   Push a zero under the input
f   Use the rest of the program as a filter on the input.  Output passing elements.
>   Current element is greater than previous?
_~  Push current element to the input stack; when the main stack is empty, pops fall back to this
!   Logical not; applies to the result of the greater-than

Run this one
The ordering of the instructions is awkward but there's a reason for it.  Stax source code packing doesn't always yield the same size output for the same size input.  Basically, you have a chance to save a byte if the last character of source has a lower character code.  Well, ! has one of the lowest codes you can get for a printable character. (33 specifically)  Many 6 byte ASCII stax programs can't pack any smaller.  But if they end with a !, then they can.  So the reason for this particular ordering of instructions is to ensure that the logical not ends up at the end of the program.

J, 12 Bytes
#~1,2&(<:/\)

Explanation:
#~1,2&(<:/\)    | Whole function, executed as a hook
       <:/      | Distribute <: (greater or equal) over an array
    2&(   \)    | Apply to each sub array of length 2
  1,            | Append a 1 to the front
#~              | Choose elements from the original array

Examples:
    2&(<:/\) 8 6 9 9 7 2 3 8 1 3
0 1 1 0 0 1 1 0 1
    1,2&(<:/\) 8 6 9 9 7 2 3 8 1 3
1 0 1 1 0 0 1 1 0 1
    (1 0 1 1 0 0 1 1 0 1) # 8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3
    f =: #~1,2&(<:/\)
    f 8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3

Try it online!

Nice solution! I added a TIO link for your code.

Jelly, 6 bytes
>Ɲ0;¬×

I/O is on strings.
Try it online!

I'm curious, why operate on strings and not arrays? I was told Jelly is bad at strings.

It is. × shouldn't work for character repetition, but it does.

Octave, 21 bytes
@(x)x(~[0,diff(x)<0])

Try it online!
Explanation:
Take a vector x as input, and create a vector [0, diff(x)<0], where diff(x) is a vector with the difference between all adjacent elements. Keep only those that are negative by comparing it to zero, giving us a list of all the elements we want to drop.
We then select the elements from the input vector that we want to keep.

V, 25 bytes
òjälá k$yl+@"òç-/d
ç /dw

Try it online!
Hexdump:
00000000: f26a e46c e120 6b24 796c 2b40 2218 f2e7  .j.l. k$yl+@"...
00000010: 2d2f 640a e720 2f64 77                   -/d.. /dw

Worst language for the job. But I did it for a dare.

Side note: ojalá is Spanish for hopefully.

@dennis That's cool. What is k$yl+@"òç-/d Spanish for?

k$yl+@"òç-/d might be liberally translated as Ouch, who the hell left that cupboard door open?

SWI-Prolog, 44 bytes
[A,B|C]-[A|E]:-B<A,[B|C]-[B|E];[B|C]-E. L-L.

Usage: Call "List-X" where List is a bracket-enclosed, comma-separated list e.g. [1,4,5,1,11,6,7].

Welcome to the site! :)

Python 2, 52 46 45 42 bytes
lambda a:[v for v,w in zip(a,[1]+a)if v/w]

Try it online!

Saved:

-3 bytes, thanks to Rod

Triangularity, 71 bytes
.....).....
....IEL....
...)rFD)...
..2+)IE)w..
.+h)2_stDO.
={M)IEm}...

Try it online!
How it works?

)IEL)rFD)2+)IE)w+h)2_stDO={M)IEm} – Full program.
)IE                               – Get the 0th input I and evaluate it.
   L)r                            – And push the range [0 ... length of I).
      F                   {       – Filter the integers in this range which satisfy:
       D)2+)IE)w+h)2_stDO=        – This condition. Runs each element E on a separate
                                    stack and discard those that don't meet the criteria.
       D)2+                       – Duplicate and add 2 to the second copy.
           )IE                    – Retrieve I again.
              )                   – Push a 0 onto the stack.
               w                  – Wrap the 0 in a list. [0]
                +                 – Prepend it to I.
                 h                – Head. Trim the elements after index E+2.
                  )2_             – Literal -2.
                     st           – Tail.
                       DO=        – Check whether the result is invariant over sorting.
                           M)IEm} – Last part: indexing into the input.
                           M    } – For each index that satisfies the conditions:
                            )IEm  – Retrieve the element of I at that position.

Out of curiosity (since you are the creator of Triangularity): why not do something similar as Hexagony / Cubically, where a piece of code is automatically filled with the no-op dots? So this program would be )IEL)rFD)2+)IE)w+h)2_stDO={M)IEm} which would expand to your current answer?

@KevinCruijssen Because I was actually planning to make Triangularity a 2D esolang, but I gave up on the idea so I just sticked to my previous template. I think I'll make some major changes soon, when I release Triangularity v2. (Also it's kinda fun to golf in it in its current form, because a simple 1-byte save inline might instead save you 20 :D... It also applies retroactively when fixing stuff though :C)

Well, even if you do plan on releasing it as a 2D esolang, my comment still stands (somewhat). )IEL)rFD)2+)IE)w+h)2_stDO={M)IEm} would be your code, it would expand to your current template, and then do the 2D commands on that expanded template. EDIT: .....).....\n....IEL....\n...)rFD)...\n..2+)IE)w..\n.+h)2_stDO.\n={M)IEm}... and .....).........IEL.......)rFD).....2+)IE)w...+h)2_stDO.={M)IEm}... and )IEL)rFD)2+)IE)w+h)2_stDO={M)IEm} would all three be the exact same program.

Wonder, 27 bytes
-> ':1.!> 'sS#<=.cns2.++[0]

Usage example:
(-> ':1.!> 'sS#<=.cns2.++[0])[8 6 9 9 7 2 3 8 1 3]

Explanation
Ungolfed version:
(map get 1).(fltr sS <=).(cns 2).(++ [0])

Prepend 0, get list of consecutive pairs, keep list items where first number <= second number, get second number of each pair.

Python, 40 bytes
f=lambda h,*t:t and h+f(*t)[h>t[0]:]or h

Try it online!
Input as tuple of characters.

Python 3, 41 bytes
p=''
for x in input():x<p or print(x);p=x

Try it online!
String input.

Python 2, 41 bytes
for x in input():
 if x>=id:print x
 id=x

Try it online!
String input, just because strings are greater than id but numbers are smaller.

Wolfram Language (Mathematica), 33 bytes
Pick[#,Arg[#-{0}~Join~Most@#],0]&

Try it online!
How it works
The code # - {0}~Join~Most@# turns an array {a,b,c,d,e,f} into {a,b-a,c-b,d-c,e-d,f-e}. Applying Arg to this sets negative numbers to Pi and nonnegative numbers to 0.
Pick[#, ..., 0]& picks out the entries of # where ... has a 0: in our case, exactly the elements that yield a nonnegative number when you subtract the previous element. In other words, these are exactly the entries we want to keep when lazydropsorting.

Wolfram Language (Mathematica), 20 bytes
#&@@@Split[#,##>0&]&
(* or *)
Max/@Split[#,##>0&]&

Try it online!
Explanation
Input = {8, 6, 9, 9, 7, 2, 3, 8, 1, 3}
Split[#,##>0&]

Group consecutive elements that are strictly decresasing: {{8, 6}, {9}, {9, 7, 2}, {3}, {8, 1}, {3}}
#&@@@

Take the first element of each: {8, 9, 9, 3, 8, 3}

##>0 is fancy and everything, but it doesn't really save anything over #>#2 here ;) (which would make your program work with arbitrary integers, not that that's required though).

APL+WIN, 14 bytes
Prompts for screen input of a vector of integers.
(1,1>2-/v)/v←⎕

05AB1E, 6 bytes
ĆÁü›_Ï

Try it online!
Explanation
Ć        # append the head of the list
 Á       # rotate right
  ü›     # apply pair-wise greater-than
    _    # logical negate each
     Ï   # keep elements of input that are true in this list

C# (.NET Core), 33 + 18 = 51bytes
x=>x.Where((a,n)=>n<1||x[n-1]<=a)

Try it online!
basically the statement is where x is the first int in the array, or is greater than or equal to the previous number, keep it. Else drop it.

You can return an IEnumerable. No ToArray() needed.

@Pavel I would need to add an extra reference System.Collections, and that would negate all the bytes saved for removing the ToArray().

No, since you won't be referencing IEnumerable in the answer, just using it as the return type.

@Pavel okay thanks, sometimes I'm a bit unsure when to count the bytes or not... sorry

Kotlin, 39 bytes
a->a.filterIndexed{i,v->i<1||v>=a[i-1]}

Try it online!
Filter items that are either the first item (index==0, or even shorter index<1) OR the current Value is greater than or equal to the previous item (a[i-1]).

APL (Dyalog Unicode), 11 bytes
{⍵⌿⍨1⍪2≤⌿⍵}

Try it online!
This is actually pretty similar to Graham's answer, but in Dyalog, and independently developed. Also, more symmetric.

K4, 10 bytes
Solution:
x_/|&<':x:

Example:
q)k)x_/|&<':x:8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3

Explanation:
Find indices where element is less than preceding, remove these indices from the input
x_/|&<':x: / the solution
        x: / store input as x
     <':   / less-than each-previous
    &      / indices where true
   |       / reverse
 _/        / drop-over
x          / the input

Attache, 24 bytes
{Mask[1'(Delta!_>=0),_]}

Try it online!
Explanation
Mask selects all elements from its second argument which correspond to truthy elements in its first argument. 1'(Delta!_>=0) calculates the indices which correspond to elements that are supposed to be in the final array.
Other attempts
28 bytes (pointfree): ~Mask#(1&`'##Delta#`>=#C[0])
32 bytes: {Mask[1'(&`<= =>Slices[_,2]),_]}

Jelly, 9 bytes
0;>ƝżµḢÐṂ

Try it online!
This feels pretty bulky, wouldn't be that surprised if there is a better way.
0;>ƝżµḢÐṂ
   Ɲ       For each adjacent pair in the input...
  >        ...is the first element greater than the second? (yields a list of 0/1)
0;         prepend a zero to this list (always keep the first element)
    ż      zip with the input
     µ     new monadic link
       ÐṂ  keep elements of the list with minimal value of... (Ðḟ would have worked here and been slightly more clear but I'll leave it as it is)
      Ḣ    ...their first element

Swift 4, 56 55 bytes
{var l=0;print($0.filter{($0>=l,l=$0).0})}as([Int])->()

Try it online!
Explanation
{var l=0;           // Declare variable l
print($0.filter{(   // Print every element e in the input
  $0>=l,            //   where e >= l
  l=$0).0})         //   And set l to e
}as([Int])->()      // Set the input type to integer array

Brain-Flak, 136, 120 bytes
((())){{}([{}]({}))([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}{{}(({})<>)(())(<>)}{}([][()])}{}{}<>{{}({}<>)<>}<>

Here it is formatted and "readable".
((()))
{
    {}

    ([{}]({}))

    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

    {
        {}(({})<>)(())(<>)
    }

    {}

    ([][()])

}{}{}<>

{
    {}
    ({}<>)<>
}<>

Try it online!

SHELL ( 45 Bytes)
Solution 1 : output on 1 line ( 57 Bytes)
L(){ for i in $*;do(($i>=$o))&&echo $i;o=$i;done|xargs;}

Test :
>L 8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3

Solution 2 : output 1 element / line ( 51 Bytes)
L(){ for i in $*;do(($i>=$o))&&echo $i;o=$i;done;}

Test :
>L 8 6 9 9 7 2 3 8 1 3
8
9
9
3
8

Solution 3 : with bc ( 51 Bytes)
 L(){ for i in $*;do bc<<<"if($i>$o)$i";o=$i;done;}

Solution 4 :  optimisation ( suppression in $*, thanks user17752 ) ( 45 Bytes)
 L(){ for i;do bc<<<"if($i>$o)$i";o=$i;done;}

I don't think you need the space after L, or xargs.

Also, which shell is this? I get a syntax error in Bash:

for i in $* can be shortened to for i

Tested on Cygwin ( CYGWIN_NT-10.0  2.3.1(0.291/5/3) )

Python 2, 50 49 bytes
f=lambda s:s and f(s[:-1])+s[-1]*(s[-2:]<s[-1]*3)

I/O is on strings.
Try it online!

Retina 0.8.2, 32 31 bytes
\d
$*
r`(?<=1\1) (1+)\b

1+
$.&

Try it online! Link includes test cases. Explanation: The first and last stages are simply unary conversion. The middle stage deletes the numbers that are preceded by a larger number. A right-to-left match is used so that the lookbehind can be placed at the start of the regex, saving 1 byte.

Fortran (GFortran), 74 bytes
SUBROUTINE D(I,J)
INTEGER I(J)
DO1 K=1,J
1 IF(I(K)>=I(K-1))PRINT*,I(K)
END

This is my entry in this lovely language. It simply prints the "sorted" array, doesn't return it. I is the array to be "sorted" and J is its length. The TIO link below shows a complete program (with 160 bytes) using the subroutine. The input array is hardcoded in the main program.
Actually, I think that there might be some way to get an unknown length array as input, even from STDIN, using allocatable arrays, but it would be a really ugly program. Anyway, it seems fair to be lazy while implementing a lazy algorithm in a aged (and, therefore, tired) programming language :).
Conclusion: Fortran is an awesome language for arrays, as far as you know their lengths.
Try it online!

C, 82 bytes
f(a,c,i,j)int*a;{for(i=-1;++i<c;j=a[i])printf("%d "+3*(i&&j>a[i]),a[i]);puts("");}

Try it online!
I used the usual tricks (using K&R-style functions, indexing into a constant string, etc.) and because I don't like ending output on the same line as the next program added a newline. To make sure that the 1-element arrays were handled correctly, I special-cased it.

C (clang), 53 bytes
x,c;f(char *s){for(x=0;c=*s++;x=c)c>=x?putchar(c):0;}

Try it online!
Takes input as string of digits, For all digits, prints it if greater than previous.

Suggest c<x||putchar(c); instead of c>=x?putchar(c):0;


text:
Matrix trace for any matrix through... Bresenham’s line rasterisation
Inspired by this.
Agatha Stephendale, a sophomore who is really into raster graphics, has taken a course in linear algebra. Now she imagines matrices as rectangles, but in her artistic mind, she attaches diagonal lines to those rectangles and tries to compute traces along them. In fact, she wants to compute traces of all matrices, not just square ones.
Since Agatha is an artist, she knows how to draw lines in her favourite image editor, and the latter uses Bresenham’s algorithm to plot lines. She even checked Wikipedia and found the pseudocode:

 function line(x0, y0, x1, y1)
     real deltax := x1 - x0
     real deltay := y1 - y0
     real deltaerr := abs(deltay / deltax)    // Assume deltax != 0 (line is not vertical),
           // note that this division needs to be done in a way that preserves the fractional part
     real error := 0.0 // No error at start
     int y := y0
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         while error ≥ 0.5 then
             y := y + sign(deltay) * 1
             error := error - 1.0

(Note that this pseudocode works only for slopes less than 1; for tall grids, a similar treatment should be done, but with a loop over y. See this section for the two cases.)
Agatha imagines a matrix as a rectangle, draws a diagonal line in it, and Bresenham’s algorithm determines which elements of a matrix belong to the diagonal. Then she takes their sum, and this is what she wants to implement in as few bytes as possible because she is a poor student and cannot afford large-capacity HDDs to store her code.
Task
Given a matrix A, return the sum of the elements that lie on the rasterised main diagonal (from top left to bottom right), where the latter is determined by Bresenham’s line algorithm. That is, assuming that the matrix represents a m×n grid, draw a line on that grid from A[1, 1] to A[m, n] using Bresenham’s algorithm, and take the sum of all elements on the line. Note that for 1×N and N×1 matrices, the entire matrix becomes its own diagonal (because this is how one would draw a line from the first element of the first row to the last element of the last row).
Input: a real matrix (may be a 1×1 matrix, a row matrix, a column matrix, or a rectangular matrix).
Output: a number.
Note that some sources (e. g. the Wikipedia’s pseudocode above) use the condition check error≥0.5, while other sources use error>0.5. You should use the originally posted one (error≥0.5), but if the alternative error>0.5 is shorter in your code, then you are allowed to implement it (since this is code golf), but mention it explicitly. See test case 4.
Challenge rules

I/O formats are flexible. A matrix can be several lines of space-delimited numbers separated by newlines, or an array of row vectors, or an array of column vectors etc.
This is code-golf, so shortest answer in bytes wins.
Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs.
Default loopholes are forbidden.

Test cases

[[1,2,3],[4,5,6],[7,8,9]] → 1+5+9 → output: 15.

[[1,2,3,4],[5,6,7,8]] → 1+2+7+8 → output: 18.

[[1,2,3,4,5,6],[7,8,9,10,11,12],[13,14,15,16,17,18],[19,20,21,22,23,24]] → 1+8+9+16+17+24 → output: 75.

[[1,2,3,4,5],[6,7,8,9,10]] → 1+2+8+9+10 (using the ≥ error condition) → output: 30.

However, if it would be shorter to use the strict inequality > in your code, then the allowed output is 1+2+3+9+10=25, but you should mention it separately.

[[1,2,3],[4,5,6],[7,8,9],[10,11,12]] → 1+5+8+12 → output: 26.

[[-0.3,0.5]] → output: 0.2.
[[3.1],[2.9]] → output: 6.
[[-5]] → output: -5.

More information on Bresenham’s algorithm

http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm — a collection of algorithms for different languages;
https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html — a nice explanation featuring different cases for slopes;
https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm;

Requested test case: [[1,2,3,4,5],[6,7,8,9,10]].

@user202729 Added it to resolve ambiguity.

Can we get a test case that's taller than it is wide? Like [[1,2],[3,4],[5,6],[7,8],[9,10]]

@Giuseppe Catch. See case 5 now. For your example, the answer should be 28 (with ≥, the expected implementation) or 27 (with >, the optional implementation.)

Can the program only support matrices up to a fixed size (say, 500×500)?

@user202729 If your language has some limitations, well, there is nothing you can do to circumvent it, so 500×500 seems a reasonable limit. Go with it!

Jelly, 25 bytes
ZXL>LƲ¡µLḶ÷’Ɗ×XL’Ɗær0ị"OS

Try it online!

If Jelly had 1 or 2-byte round to nearest integer built-in, this answer would be 23 or 24 bytes.

SmileBASIC, 101 99 bytes
DEF D A,W,H
GCLS
GTRI.,0,0,0,W-1,H-1FOR I=0TO W*H-1=I MOD W
S=S+A[I/W,M]*!!GSPOIT(M,I/W)NEXT?S
END

I originally thought of using the GLINE function to draw a line, but it doesn't appear to use the correct algorithm. However, GTRI does seem to work,
Test case 4 outputs 30.
Input is a 2D array in [Y,X] form, along with the width/height (there's no way to check the dimensions of an array, only the total number of elements).

JavaScript (ES6), 110 103 bytes
Outputs 25 for the 4th test case.
a=>(X=a[x=y=0].length-1,Y=1-a.length,g=e=>a[y][x]+(x-X|y+Y&&g(e+(e*2>Y&&++x&&Y)+(e*2<X&&++y&&X))))(X+Y)

Try it online!
Or 88 bytes if taking the dimensions of the matrix as input is allowed.

Python 3.X, 269 bytes
With input as comma-delimited rows of space-delimited numbers.
import math;c=math.ceil;a=[[float(k)for k in q.split(" ")]for q in input().split(",")];_=len;m=lambda f,t,x,y,e,d:sum(x[0]for x in a)if 2>_(a[0])else m(*[0]*4,*[(_(a)-1)/(_(a[0])-1)]*2)if f else m(f,t+a[y][x],x+1,y+c(e-0.5),e+d-c(e-0.5),d)if x<_(a[0])else t;m(1,*[0]*5)
Pre-golfing:
def line(a):
   if len(a[0])<2: return sum([x[0] for x in a])
   e = d = abs((len(a)-1)/(len(a[0])-1))
   y=t=0
   for x in range(len(a[0])):
       t += a[y][x]
       f = ceil(e-0.5)
       y += f
       e += d-f
   return t

It looks like that the c=math.ceil make the program longer...

Also, you don't need the [] between the sum(..). a if c else b can often be c and a or b.

input("") can be input().

Also... what is the input/output format? Print to screen?

FMSLogo, 136 bytes
make 1 rl
setxy -1+count :1 -1+count last :1
pu home
make 9 0
foreach :1[foreach ?[if
0=last pixel[make 9 :9+?]fd 1]setxy xcor+1 0]pr :9

Full program, prompt the user for input (dialog box popup) and then print the output to the screen.
Just draw a line on the screen and calculate the output. Use strict inequality.

This only supports matrix size up to FMSLogo's canvas size (about 500×500)
Ungolfed code:
Make "input ReadList
SetXY (-1+Count :input) (-1+Count Last :input)
PenUp
Home
Make "sum 0
ForEach :input[
    ForEach ?[
        If 0=Last Pixel[
            Make "sum :sum+?
        ]
        Forward 1
    ]
    SetXY XCor+1 0
]
Print :sum

source: Stack Exchange

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

sort: votes


text:
Eiffel Towers: Create a large "A" from "A"s
Create a function which given a number of lines n, makes a bigA.

The horizontal bar of bigA must be at the middle row, or the lower of the two if n is even
Assume a monospace font for output

Output should be a string (or similar, eg character array) with clear linebreaks to break up the lines, and with correct whitespace for left-padding (you can assume \t to be 4 spaces). There can be any whitespace on the right.
Examples
n = 1
A
n = 2
 A
AAA

n = 3
  A
 AAA
A   A

n = 4
   A
  A A
 AAAAA
A     A

n = 5
    A
   A A
  AAAAA
 A     A
A       A

This is inspired by Create an "H" from smaller "H"s

May I add whitespace to the right side? Also, is trailing newline allowed?

@Bubbler, Any whitespace on the right side is fine, no trailing newline though

Are we allowed to return 2D character arrays instead of strings? (hint: it's usually recommended to allow any kind of output)

@OlivierGrégoire Sure, as long as there is a clear break for the lines (eg an "\n" element, nested arrays)

Is an array of strings representing lines ok? Also, can I print directly to stdout?

Yes, output is flexible as long as spacing and newlines are clearly represented somehow

Can we use another content character than "A" ? in particular, is lowercase "a" allowed ?

@TonHospel, No, that really defeats the purporse of this

Can ____A\bA____ be used instead of ____A____ ? \b stands for ASCII backspace character.

05AB1E, 13 bytes
Code:
Ð;î¹)'A1376SΛ

Uses the 05AB1E encoding. Try it online!
Explanation:
Ð                  # Triplicate the input.
 ;î                # Compute ceiling(n / 2).
   ¹               # Push the first input again.
    )              # Wrap into an array. For input 7, this would result in:
                     [7, 7, 4, 7].
     'A            # Push the character 'A'
       1376S       # Push the array [1, 3, 7, 6]. These are the directions of the canvas.
                     This essentially translates to [↗, ↘, ↖, ←].
            Λ      # Write to canvas using the previous three parameters.

Canvas
I should probably document the canvas a little bit more (and a lot of other functions), but this basically sums it up. The canvas has different 'modes' based on the parameter types given. The canvas command has three parameters: <length> <string> <direction>.
Since the length and direction parameters are lists, it 'zips' these lists to create a set of instructions to be executed. The string parameter is just the letter A, so this is the fill character used by all instructions. The canvas interprets this as the following set of instructions (for input 7):

Draw a line of length 7 with the string A in direction ↗
Draw a line of length 7 with the string A in direction ↘
Draw a line of length 4 with the string A in direction ↖
Draw a line of length 7 with the string A in direction ←

The directions are translated in the following manner:
7   0   1
  ↖ ↑ ↗
6 ← X → 2
  ↙ ↓ ↘
5   4   3

If nothing has been outputted, 05AB1E automatically outputs the canvas result.

Thank you very much for the canvas explanation, that's a brilliant feature :-)

TIL triplicate is a word

@thecoder16 quadruplicate, quintuplicate, ..., decuplicate

Wow. I was doubtful of nonuplicate, but it exists as all the others do. Of course we have such useless words in English xD

1376 can be Ž5' now. (Thanks for adding Ž, very useful!) Btw, the docs for the Canvas are still missing. ;) It's one of the few features for which I still have to look at the Elixir source code in order to fully see its capabilities. Especially since crosses are also possible with + or ×. PS: Would like to see a box single-char as well. And it would be useful if multiple characters could be mixed somehow, like - and |, or \ and /, or a box with + at the corners, etc. But that's perhaps something for later.

If you don't have time, let me know. Then I will add it to the 05AB1E tip page for now. I see it can also be used cyclic, as you've done in this answer to create a spiral. Didn't knew Canvas could even be used like that!

@KevinCruijssen Hey, apologies for all the late replies, it's been incredibly busy for me the last couple of weeks (I only managed to get 8 hours of sleep the last 72 hours haha) so I don't think I'm able to do anything right now, but feel free to add it to the tip page if you'd like.

@Adnan Created the tip. If you see anything incorrect or something else worth mentioning, let me know. :)

Charcoal, 17 15 bytes
ＮθＰ×θAＭ⊘θ↗Ｐ^×θA

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

Input n.
Ｐ×θA

Print the horizontal bar of the big A. (For even numbers, the n+1th overlaps the right side anyway.)
Ｍ⊘θ↗

Move to the top of the big A.
Ｐ^×θA

Print both sides of the big A.

Python 2, 80 bytes
lambda n:'\n'.join(' '*(n+~i)+('A'+' A'[i==n/2]*n*2)[:i*2]+'A'for i in range(n))

Try it online!
Divide the desired output into the left whitespace, left A plus middle whitespace or As, and the right A. Compute the middle part using slicing on a fixed string. This allows to use the same way to generate the first line.

Stax, 15 bytes
┴3╬*ôP^x'┌_╓J²♫

Run and debug it
Unpacked, ungolfed, and commented, the program looks like this.
m       map over [1 .. input] using rest of the program, output each result
'A      "A" literal
xhi=    is the iteration index equal to (integer) half the input?
65*     multiply by 65 (character code of "A")
]i*     repeat that character (" " or  "A") i times
+       concat to initial "A"
x)      left pad to the original input
|p      palindromize (concatenate the reverse minus the last character)

Run this one

JavaScript (ES6), 77 bytes
This source code has a rectangle shape! Oh wait ... wrong challenge :-/
f=(n,k=n>>1,p='A')=>--n?f(n,k,' '+p)+`
${p}${(k-n?' ':'A').repeat(n*2-1)}A`:p

Try it online!

Python 3.6, 79 bytes or 73 bytes
Using f-strings to align horizontal parts of the letter:

lambda n:'\n'.join(f"{'A'+' A'[i==n//2]*2*i:>{n+i}}"[:-1]+'A'for i in range(n))

With \b used to delete one A (possibly cheating):
lambda n:'\n'.join(f"{'A'+' A'[i==n//2]*2*i:>{n+i}}\bA"for i in range(n))

Java (JDK), 121 bytes
n->{var a=new char[n][n+n-1];for(int c=n*n,r,q;c-->0;a[r=c%n][q=c/n]=a[r][n+n-q-2]+=r==n/2&q>=r|r==n+~q?65:32);return a;}

Try it online!
Credits

-3 bytes thanks to ceilingcat

J, 65 bytes
f=:3 :''' A''{~1(([:(<@;]+i.@+:)<.@-:)y)}([:(}:@|."1,.])=/~@i.)y'

Try it online!
It can be reduced by approx. 12 bytes by simply making the verb tacit, but I have problems doing it.
Explanation:
3 : '...' denotes an explicit one-liner verb
y is the argument
=/~@i. creates an identity matrix with size the argument
    =/~@i. 4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

([:(}:@|."1,.]) prepends the identity matrix with its mirror copy with last elements of each row dropped.
    ]a =. ([:(}:@|."1,.])=/~@i.) 4
0 0 0 1 0 0 0
0 0 1 0 1 0 0
0 1 0 0 0 1 0
1 0 0 0 0 0 1

1(...)}(...) changes to 1 the positions in its right argument, selected by the left one
([:(<@;]+i.@+:)<.@-:) - prepares the selection by doing the following:
               <.@-: - halves the argument and finds the floor (finds the row number)
    <@;              - box the row, followed by a list of columns:
        ]+i.@+:      - a list form the argumnt to the doubled row number

    ([:(<@;]+i.@+:)<.@-:) 4
┌───────────┐
│┌─┬───────┐│
││2│2 3 4 5││
│└─┴───────┘│
└───────────┘

    1(([:(<@;]+i.@+:)<.@-:) 4)}a
0 0 0 1 0 0 0
0 0 1 0 1 0 0
0 1 1 1 1 1 0
1 0 0 0 0 0 1

' A'{~ renders a space in the places of 0 and 'A' where there is 1
    ' A'{~1(([:(<@;]+i.@+:)<.@-:) 4)}a
   A
  A A
 AAAAA
A     A

Canvas, 17 13 bytes
A×／╶½A×╶»╵：╋│

Try it here!
-4 bytes thanks to dzaima!

Japt -R, 20 19 bytes
Çç" A"gZ¶Uz¹i'A êÃû

Try it

Explanation
                        :Implicit input of integer U
Ç                       :Create the range [0,U) and pass each Z through a function
         Uz             :  Floor divide U by 2
       Z¶               :  Test for equality with Z (true=1, false=0)
  " A"g                 :  Get the character in the string " A" at that index
 ç                      :  Repeat Z times
           ¹            :  (Closes a few nested methods)
            i'A         :  Prepend an "A"
                ê       :  Palindromise
                 Ã      :End function
                  û     :Centre pad each element to the length of the longest element
                        :Implicitly join with newlines and output

Alternative
(In the hope that it might help me spot some savings!)
Æ'AúXÄ" A"gX¶Uz¹êÃû

Another alternate that's a byte longer: ç h'AUz)¬íp ®i'A êÃû

@ETHproductions Replace p with ² and it's also 19 bytes.

+1 way better than my monstrosity.

SOGL V0.12, 12 bytes
 A*:╚╥≤.»I:ž

Try it Here!
Explanation:
 A*           repeat "A" input times
   :          duplicate it
    ╚         create a "/" diagonal of one of the copies of As
     ╥        palindromize it horizontally
      ≤       get the other copy of the "A"s on top
       .»I:   push floor(input/2)+1 twice
           ž  and at those coordinates in the palindromized diagonals place in the row of As

Ruby, 66 bytes
->n{(0...n).map{|i|(s=(i==n/2??A:?\s)*2*i+?A)[0]=?A;?\s*(n+~i)+s}}

Try it online!
Returns as array of lines

Jelly, 23 20 19 18 bytes
=þ`o\L‘HĊƲ¦UŒBị⁾A

Try it online!
=þ` creates an identity matrix of size n.
L‘HĊƲ finds the row index of the horizontal bar with ¦ picking that row out and applying o\ to it which creates the bar.
U reverses each row so we don't have an upside down "A" and ŒB (palindromize; vectorizes) makes the second half of the "A".
ị⁾A (with a space that is getting trimmed in the formatting) replaces 0s with spaces and 1s with As.

Javascript, 124 bytes
A fairly naive solution, gave it a shot to practice js skills.
for(i=-1,p=" ".repeat(n-1)+"A ";++i<n;console.log(i-~~(n/2)?p:p.slice(0,i)+"A".repeat(n)),p=p.slice(1,n)+" "+p.slice(n-1)){}
Unpacked
for(
 //create the first line
 i=-1, p=" ".repeat(n-1)+"A ";
 ++i<n;
 console.log(
 //if we are not at the bar
      i-~~(n/2)?
 //otherwise, use the modified previous line
      p
 //slice the start of the previous line and add As
      :p.slice(0,i)+"A".repeat(n)),
 //add a space in between the previous line and remove padding on each side
 p=p.slice(1,n)+" "+p.slice(n-1)){}

Ruby, 73 bytes
->n{(0...n).map{|i|(?A.ljust(i*2,i==n/2??A:' ')+(i>0??A:'')).center n*2}}

Try it online!

T-SQL, 182 177 bytes
DECLARE @n INT=5DECLARE @ INT=0a:DECLARE @s VARCHAR(9)=STR(POWER(10,@),@n)PRINT REPLACE(REPLACE(@s+REVERSE(LEFT(@s,@n-1)),'1','A'),'0',IIF(@=@n/2,'A',' '))SET @+=1IF @<@n GOTO a

First version (with 182 bytes):
DECLARE @n INT=5DECLARE @ INT=0WHILE @<@n BEGIN DECLARE @s VARCHAR(9)=STR(POWER(10,@),@n)PRINT REPLACE(REPLACE(@s+REVERSE(LEFT(@s,@n-1)),'1','A'),'0',IIF(@=@n/2,'A',' '))SET @+=1 END

The version above works up to @n=9.
Here is another version, which works up to @n=23, but has 2 extra bytes:
DECLARE @n INT=5DECLARE @ INT=0WHILE @<@n BEGIN DECLARE @s VARCHAR(23)=STR(POWER(10.,@),@n)PRINT REPLACE(REPLACE(@s+REVERSE(LEFT(@s,@n-1)),'1','A'),'0',IIF(@=@n/2,'A',' '))SET @+=1 END

Ungolfed:
DECLARE @n INT=5

DECLARE @i INT=0
WHILE @i<@n BEGIN
    DECLARE @s VARCHAR(9)=STR(POWER(10,@i),@n)
    PRINT REPLACE(REPLACE(@s+REVERSE(LEFT(@s,@n-1)),'1','A'),'0',IIF(@i=@n/2,'A',' '))
    SET @i+=1
END

Haskell, 98 97 95 bytes and 109 bytes
Two very different approaches. First (95 bytes):
c!n=([1..n]>>c)++"A"
f n=unlines[" "!(n-x)++drop 3([" "!(abs$n`div`2-x+1)!!0]!(2*x))|x<-[1..n]]

and second (109 bytes):
m True='A'
m _=' '
g n=unlines[[m(abs(n-j)==l||l==q&&elem j[q+1..q+n])|j<-[1..2*n]]|l<-[0..n-1],q<-[n`div`2]]

Try them here!; Try modified version here!
Try third version here!

Welcome to PPCG! You can save a byte on your first approach by defining l as infix operator.

m True='A' an be shortened to m b|b='A'.

It turned out that even two bytes could be saved. Thanks! :)

Python 2, 70 bytes or 65 bytes
List of strings is acceptable result, as @Budd stated in comments.
lambda n:['%*sA\n'%(n+i,('A'+i*2*' A'[i==n/2])[:-1])for i in range(n)]

Try it online!

Seemingly cheaty solution, using \b. It looks funky in TIO, in console it does the job.
lambda n:['%*s\bA\n'%(n+i,'A'+i*2*' A'[i==n/2])for i in range(n)]

Try it online!

Python 3, 93, 88 bytes
lambda n:'\n'.join(f"{'A'+(x>0)*('A '[x!=n//2]*(x*2-1)+'A'):^{n*2-1}}"for x in range(n))

Try it online!
-3 by @ovs using f-string

Perl 5 -n, 57 bytes
#!/usr/bin/perl -n
say$"x-$_.uc(A x($n+$_&-2?1:$n*2)|$"x2x$n++.A)for 1-$_..0

Try it online!

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

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


text:
Shape Identifying Program
Your task is to build a program that identifies the shape of the input. The shapes to be identified can be any of the following:
Square
To be identified as a square, the source must have lines of all equal length, and the same number of lines as characters per line (newline characters excluded). An optional trailing newline is acceptable.
$_='
$_="
$_"'
;say

Rectangle
To be identified as a rectangle, the source must have lines of all equal length, but the number of lines does not match the number of characters per line (newline characters excluded). An optional trailing newline is acceptable. This can be either horizontal or vertical.
$_=
"no
t a
squ
are
";#

$_="but it
is still a
consistent
shape!";##

Triangle
To be identified as a triangle, the source must either start with one character, and each subsequent line must have one additional character (including the last), or after the first line, each subsequent line should have one character fewer until the last, which has only one.
$
_=
"So
this
"."".
shape;

$_="or
even,
this
way
!!
"

Mess
Anything that doesn't follow a consistent format as per the above, must be identified as a mess.
Rules

You may return any four consistent printable values to identify each shape.
Your source code must also adhere to one of the above shapes (no, not a mess).
A single trailing newline in your source is acceptable.
You can assume input does not contain any blank lines (including trailing newlines), is not empty, and does not consist only of newlines.
All shapes must have a height and width of >= 2, otherwise this is defined as a mess.
Standard loopholes are forbidden.
The shortest solution in bytes, in each language, wins.

"Your source code must also adhere to one of the above shapes" does it mean one liner is just fine?

@ tsh All shapes must have a height and width of >= 2.

Is leading / trailing space count to the line length? What about tab?

@tsh Yes, trailing spaces do indeed count towards the length, tab is one character as if the source was in a file.

Do we have to confirm that a rectangle, say, has length and width at least 2, or is that just a restriction on our code?

@xnor Yes, you are correct that should be validated, otherwise it's a mess. I haven't actually tested that against these answers though...

When you say our code doesn't have to cater for trailing newlines, can we assume the input does not have one, or do we have to call it a mess? Might there be blank lines? Could the input be completely blank, or only consist of newlines?

@xnor You can assume input does not contain trailing newlines, blank lines, is empty, or consists only of newlines. Updating the question.

You might want to change the sentence "All shapes must have a height and width of >= 2." to "All shapes must have a height and width of >= 2, otherwise it counts as a Mess as well.". Or maybe explicitly add "Single character inputs should result in a Mess."

The input can be an array? for example, a square ['abc','cfd','fgh']?

@LuisfelipeDejesusMunoz I think an array for strings might be standard input, but I can't find a meta post to confirm it. I think until I find a relevant meta, if that is the default in your language, that's fine.

Is prepending using System.Linq; to the beginning of the otherwise triangular source code fine?

IMO there are some confusing nested negatives.  I'd suggest rewording to "You can assume input does not contain any blank lines (including trailing newlines), is not empty, and does not consist only of newlines."

@someone I want to say yes, just so there is more triangular code, but other answers wouldn't be able to validate your code as triangular. If there's a command-line option to provide that using argument, you can say C# with Linq, but a quick search doesn't show anything like that :(

@recursive updated, thank you!

What if the input is like the two triangle examples next to each other vertically? That is still triangle-shaped.

@mbomb007 Not for the purposes of this challenge though... but a good point!

You are telling me my source code can't be a mess? why not?!?!

Can we take input as a list of lines?

@cairdcoinheringaahing Absolutely, no problem with that.

Jelly, 35 bytes
L€ṀR,Ṛ$ċƲȧ3
L€,;¥LE€S+Ç
ỴµZL«L>1ȧÇ

Try it online!
0 = Mess
1 = Rectangle
2 = Square
3 = Triangle

Is the space on your last line used by your code? Or is that just padding to meet the "rectangle" criteria?

@BradC The latter. I should probably add an explanation.

Java 10, 231 221 219 217 213 211 207 203 bytes
s->{var a=s.split("\n");int r=a.length,l=a[0].length(),R=0,i=1,L,D;if(r>1){for(L=a[1].length(),D=L-l;
++i<r;R=L-a[i-1].length()!=D?1:R)L=a[i].length();R=R<1?D==0?r==l?1:2:D*D>1|l>1&L>1?0:3:0;}return R;};

Function is a rectangle itself.
1 = Squares; 2 = Rectangles; 3 = Triangles; 0 = Mess.
-14 bytes thanks to @OlivierGrégoire
-4 bytes thanks to @ceilingcat
Explanation:
Try it online.
s->{                        // Method with String parameter and integer return-type
  var a=s.split("\n");      //  Input split by new-lines
  int r=a.length,           //  Amount of lines
      l=a[0].length(),      //  Length of the first line
      R=0,                  //  Result-integer, initially 0
      i=1,                  //  Index integer, starting at 1
      L,D;                  //  Temp integers
  if(r>1){                  //  If there are at least two lines:
    for(L=a[1].length(),    //   Set `L` to the length of the second line
        D=L-l;              //   And set `D` to the difference between the first two lines
        ++i<r;              //   Loop over the array
        ;                   //     After every iteration:
         R=L-a[i-1].length()//     If the difference between this and the previous line
          !=D?              //     is not equal to the difference of the first two lines:
           1                //      Set `R` to 1
          :                 //     Else:
           R)               //      Leave `R` the same
      L=a[i].length();      //    Set `L` to the length of the current line
  R=R<1?                    //   If `R` is still 0:
     D==0?                  //    And if `D` is also 0:
      r==l?                 //     And the amount of lines and length of each line is equal:
       1                    //      It's a square, so set `R` to 1
      :                     //     Else:
       2                    //      It's a rectangle, so set `R` to 2
     :D*D>1&                //    Else-if `D` is NOT 1 nor -1,
      l>1&L>1?              //    and neither `l` nor `L` is 1:
       0                    //     Set `R` to 0, since it's a mess
      :                     //    Else (`D` is 1 or -1, and `l` or `L` is 1):
       3                    //     It's a triangle, so set `R` to 3
    :0;}                    //   In all other cases it's a mess, so set `R` to 0
  return R;}                //  Return the result `R`
;                           // No-op to make the method a rectangle

Fixed for 221 bytes: s->{var  a=s.split("\n");int S=a.length,l=a[0].length(),L,D,b=0,i=1;if(S<2)return 0;for(L=a[1].length(),D=L-l; b<1&++i<S;)if((L=a[i].length())-a[i-1].length()!=D)b=1;return b<1?D==0?S==l?1:2:D==-1|D==1?l==1|L==1?3:0:0:0;} (double space after var, line break after D=L-l;.

@OlivierGrégoire Thanks. And I golfed two more bytes by changing D==-1|D==1 to D>-2|D<2. That one and the l==1|L==1 might be more golfable with some bitwise operations, but that's not really my expertise.

207 bytes: s->{var a=s.split("\n");int r=a.length,l=a[0].length(),L,D,b=0,i=1;if(r>1){for(L=a[1].length(),D=L-l;++ i<r;b=L-a[i-1].length()!=D?1:b)L=a[i].length();b=b<1?D==0?r==l?1:2:D>-2&D<2&(l<2|L<2)?3:0:0;}return b;} (break after D=L-l;++). Still golfable by merging the loop and the statement afterwards in one, but I don't see how right now.

Brachylog, 45 bytes
lᵐ{≥₁|≤₁}o{l>1&t>1&}↰₃
lg,?=∧1w|=∧2w|t⟦₁≡?∧3w

Try it online!
Code is a rectangle (despite the way it renders on my screen). Outputs: 1 for square, 2 for rectangle, 3 for triangle, and nothing for mess

Explanation:
lᵐ{≥₁|≤₁}o{l>1&t>1&}↰₃
lg,?=∧1w|=∧2w|t⟦₁≡?∧3w

lᵐ                        Get the length of each string
  {     }                 Verify
   ≥₁                     The list is non-increasing
     |                    or...
      ≤₁                  The list is non-decreasing
         o                Sort it to be non-decreasing
          {        }      Verify
           l>1            The number of lines is greater than 1
              &           and...
               t>1&       The longest line is longer than 1 character
                    ↰₃    Call the following

lg,?                      Join the number of lines with the line lengths
    =∧1w                  If they are all equal, print 1 (Square)
         |=∧2w            Or if just the line lengths are equal, print 2 (Rectangle)
              |t⟦₁         Or if the range [1, 2, ... <longest line length>]
                  ≡?       Is the list of lengths
                    ∧3w    Print 3 (triangle)
                           Otherwise print nothing (mess)

Jelly, 32 27 bytes
,U⁼€JẸ,E;SÆ²$
ZL«L’aL€Ç$æAƝ

Try it online!
Now taking input at a list of lines and switched >1× with ’a and using SÆ² after L€  instead of FLÆ²Ɗ. These allowed me to condense into two lines and I saved 5 bytes in total. The following values are the same as before.
[0.0, 0.0]=Mess
[0.0, 1.5707963267948966]=Rectangle
[0.0, 0.7853981633974483]=Square
[1.5707963267948966, 0.0]=Triangle

ZL«L gets the minimum of height and width and ’ subtracts 1 from it.  Ç calls the second link and at the end if the input is a single line the result of Ç gets logical ANDed with the previous number if there is only a single line the output will be [0.0, 0.0].
In the second link: ,U yields a list of line lengths paired with it's reverse. J is range(number of lines) and ⁼€ checks whether each of them are equal to the result of J. Ẹ (Any) yields 1 if the input is a triangle.
E checks if all line lengths are equal (rectangle/square).
SÆ² with a $ to group them into a single monad checks whether the total number of characters is a square number.
So at the end of the second link we have [[a,b],c] where each number is 0 or 1 indicating whether the input is a triangle, rectangular, and has square number of characters respectively.
However a square number of elements doesn't imply the input is a square since an messy input like
a3.
4

has a square number of elements but isn't a square.
This is where æA (arctan2) comes in. 0æA0 == 0æA1 == 0. In other words, if the input has square number of elements but is not a rectangle, then it is not a square. There are certainly more clear ways to do this but what does that matter when we have bytes to think about and we are allowed consistent arbitrary output.
Note I was previously using æA/ instead of æAƝ (and a , instead of a ; in the second link) but the former method distinguishes between triangles that have square number of elements and those that don't but they should obviously be counted as the same thing.

I was looking at the numbers thinking, they seem vaguely familiar...

@DomHastings Haha. I was having trouble distinguishing squares from square-number-of-element messes and arctan2 was exactly what I needed.

Funny that I don't think this would be any shorter if there was no source restriction

... Are you sure this is valid? As newline in Jelly is 0x7F, not 0x0A.

@DomHastings Is this valid? (see reason above)

@user202729 That's an interesting point. I think it is valid. The wording pertains to characters rather than bytes, so whilst jelly codepage is used for counting bytes, it's representation is still UTF-8 in browser. But that might well be a consideration for future challenges. Thank you!

Python 2, 129 114 109 107 113 bytes
l=map(len,input().split('\n'));m=len(
l);r=range(1,m+1);print[[1],0,r,r[::-
1],[m]*m,0,[max(l)]*m,l].index(l)%7/2

Try it online!

Prints

0 = Mess
1 = Triangle
2 = Square
3 = Rectangle

Java 10, 274 323 298 229 bytes
First triangle submission.
s
->
{
var
a=s.
split
("\n");
int i,l=
a.length,
c,f=a[0].
length(),r=
l<2||f<2&a[1
].length()<2?
0:f==l?7:5;var
b=f==1;for(i=1;
i<l;){c=a[i++].
length();r&=c!=f?
4:7;r&=(b&c!=f+1)|
(!b&c!=f-1)?3:7;f=c
;}return r;}

0 Mess
1 Rectangle
3 Square
4 Triangle
Try it online here.
Edited multiple times to golf it a bit more.
Of course I could save a lot of bytes by turning this into a rectangle as well (281 267 259 200 bytes, see here).
The result of the identification is manipulated using bitwise AND, yielding a bitmask as follows:
1        1      1
triangle square rectangle

Ungolfed version:
s -> {
    var lines = s.split("\n"); // split input into individual lines
    int i, // counter for the for loop
    numLines = lines.length, // number of lines
    current, // length of the current line
    previous = lines[0].length(), // length of the previous line
    result = numLines < 2 // result of the identification process; if there are less than two lines
    || previous < 2 & lines[1].length() < 2 // or the first two lines are both shorter than 2
    ? 0 : previous == numLines ? 7 : 5; // it's a mess, otherwise it might be a square if the length of the first line matches the number of lines
    var ascending = previous == 1; // determines whether a triangle is in ascending or descending order
    for(i = 1; i < numLines; ) { // iterate over all lines
         current = lines[i++].length(); // store the current line's length
        result &= current != previous ? 4 : 7; // check if it's not a rectangle or a square
        result &= (ascending & current != previous+1)|(!ascending & current != previous-1) ? 3 : 7; // if the current line is not one longer (ascending) or shorter (descending) than the previous line, it's not a triangle
        previous = current; // move to the next line
    }
    return result; // return the result
}

Welcome to PPCG!

Hooray for triangles! Thanks!

Hi, welcome to PPCG! Great first answer. I tried making my answer a triangle before as well, but it would cost too many bytes in comparison to rectangle, and some key-words were a bit too long in my initial answer as well. :) Great answer though, +1 from me. And I took the liberty to edit your post to add highlighting to the entire post, so the comments in your ungolfed version are easier to read. Enjoy your stay!

@KevinCruijssen Thanks for the upvote and edit, it looks much better now. My answer could be shortened by turning it into a rectangle as well, 281 bytes. But where's the fun in that?

Jelly, 15 bytes
Jm0w,ET
ỴẈµLe|Ç

Try it online!
Returns [1] for triangles, [2] for rectangles, [3] for squares and [] for messes
How it works
ỴẈµLe|Ç - Main link. Takes a string S on the left
Ỵ       - Split S into a list of lines
 Ẉ      - Take the length of each line
  µ     - Use this list of lengths W as the left and right argument:
   L    - Length of W
    e   - This length is in W?

          This returns 1 for triangles and squares and for messes with
          one (or more) lines of a length of the number of lines in the mess

      Ç - Call the helper link on W
     |  - Logical OR

Jm0w,ET - Helper link. Takes a list of lengths W on the left
J       - Replace W with it's indices ([1, 2, ..., len(W)])
 m0     - Reflect; [1, 2, ..., len(W), len(W), ..., 2, 1]
   w    - Index of W as a sublist in this array, or 0
          This returns a non-zero number for triangles
     E  - Are all elements of W equal?
          This returns 1 for squares and rectangles
    ,   - Pair
      T - Return the indices of non-zero elements

          This yields:
            - [1] for triangles
            - [2] for rectangles/squares
            - []  for messes

Taking the logical or between these results yields:

1 | [1] = [1 | 1] = [1] for triangles
0 | [2] = [0 | 2] = [2] for rectangles
1 | [2] = [1 | 2] = [3] for squares
1 | [] = [] or 0 | [] = [] for messes

PHP, 195 205 bytes
<?$a=$argv[1];$r=substr($a,-2,1)=="\n"?strrev($a):$a;foreach(explode("\n",$r)as$l){$s=strlen($l);$x[$s
]=++$i;$m=$i==$s?T:M;}$z=count($x);echo$i*$z>2?$z==1&&key($x)==$i?S:($z==1&&$i>2?R:($i==$z?$m:M)):M;?>

The upside down triangle adds an expensive 56 bytes to this!
Outputs are S,R,T,M
Saved a few bytes thanks to Dom Hastings.
Try it online!
Fixed a few issues now... Test runs produce this.
$_="
$_="
$_""
;say

RESULT:S
=============
$_=
"no
t a
squ
are
";#

RESULT:R
=============
$
_=
"So
this
"."".
shape;

RESULT:T
=============
$_="or
even,
this
way
!!
"

RESULT:T
=============
as
smiley
asd
A

RESULT:M
=============
X

RESULT:M
=============
XX

RESULT:M
=============
cccc
a
aa
cccc

RESULT:M
=============

Omit ?> should just be fine

This seems to return T for cccc\na\naa\ncccc Try it online!

Perl 5 -p, 83 bytes

Mess: nothing
Square: 0
Triangle: 1
Rectangle: 2

($z)=grep++$$_{"@+"-$_*~-$.}==$.,0,/$/,-1
}{$.<2or$_=$$z{$z>0||$.}?$z%2:@F>1&&2x!$z

Try it online!

Javascript 125 bytes
_=>(g=(l=_.split('\n').map(a=>a.length)).
length)<3?0:(r=l.reduce((a,b)=>a==b?a:0))
?r==g?2:1:l.reduce((a,b)=>++a==b?a:0)?3:0

0 = Mess
1 = Rectangle
2 = Square
3 = Triangle

fa=_=>(g=(l=_.split('\n').map(a=>a.length)).length)<3?0:(r=l.reduce((a,b)=>a==b?a:0))?r==g?2:1:l.reduce((a,b)=>++a==b?a:0)?3:0

var square = `asd
asd
asd`

var rectangle = `asd
asd
asd
asd
asd
asd`

var triangle = `asd
asdf
asdfg
asdfgh`

var mess = `asd
dasdasd
sd
dasasd`

console.log(fa(square), fa(rectangle), fa(triangle), fa(mess))

The byte count is 125 (including the newlines)

Triangle should go to a 1? not a 3456

@l4m2 what do you mean?

triangle should always start at 1?

I think what @l4m2 is pointing out is that a triangle must have only one character on its first or last line, otherwise it's a "mess".

Width 1 unhandled

05AB1E, 35 29 27 bytes
Saved 8 bytes thanks to Magic Octopus Urn
DgV€g©ZU¥ÄP®Y
QP®ËJCXY‚1›P*

Try it online!
0 = Mess
4 = Triangle
1 = Rectangle
3 = Square

This looks to fail on some messy code: Try it online!

@DomHastings: Thanks for catching that. I thought that golf was a bit iffy. Should be okay now.

Try it online! - 19 bytes - 1 (Rectangle), 2 (Triangle), 5 (Square) and 0 (Mess) [Using binary numbers]. Possibly not acceptable lol. gs€g©QP®¥ ÄP®1å&®ËJC can add a space char and a C for 21 though.

@MagicOctopusUrn: It still needs to check for length/height>=2, but it should still save bytes. Clever trick building the output numbers from binary!

@MagicOctopusUrn: I used your delta and binary tricks to save some bytes on my original version. Could probably save a few more rewriting it a bit more.

length/height>=2... and there's the tidbit I missed when reading.

Try it online! - if list input is allowed.

@MagicOctopusUrn: Oh yeah, forgot to switch to list input. Thanks again :)

Stax, 39 bytes
L{%m~;:-c:u{hJchC;
|mb1=-C;%a\sI^^P}M0

Run and debug online!
Shortest ASCII-only answer so far.

0 - Mess
1 - Rectangle
2 - Square
3 - Triangle

Explanation
The solution makes use of the following fact: If something is explicitly printed in the execution of the program, no implicit output is generated. Otherwise, the top of stack at the end of the execution is implicitly output.
L{%m~;:-c:u{hJchC;|mb1=-C;%a\sI^^P}M0
L                                        Collect all lines in an array
 {%m                                     Convert each line to its length
    ~;                                   Make a copy of the length array, put it on the input stack for later use
      :-                                 Difference between consecutive elements.
                                         If the original array has only one line, this will be an empty array
        c:u                              Are all elements in the array the same?
                                         Empty array returns false
           {                      }M0    If last test result is true, execute block
                                         If the block is not executed, or is cancelled in the middle, implicitly output 0
            hJ                           The first element of the difference array squared (*)
              chC                        Cancel if it is not 0 or 1
                 ;|m1=                   Shortest line length (**) is 1
                      -                  Test whether this is the same as (*)
                                         Includes two cases:
                                             a. (*) is 1, and (**) is 1, in which case it is a triangle
                                             b. (*) is 0, and (**) is not 1, in which case it is a square or a rectangle
                        C                Cancel if last test fails
                         ;%              Number of lines
                           a\            [Nr. of lines, (*)]
                             I           Get the 0-based index of (**) in the array
                                         0-> Square, 1->Triangle -1(not found) -> Rectangle
                              ^^P        Add 2 and print

Perl 6, 81 bytes
{.lines>>.chars.&{($_==.[0],3)[2*(2>.max
)+($_ Z- .skip).&{.[0].abs+.Set*2+^2}]}}

Try it online!
Returns True for square, False for rectangle, 3 for triangle, Nil for mess.

Very good, would you mind unpacking it a bit, in particular $_ Z- .skip?

Haskell, 113 107 103 101 bytes
((#)=<<k).map k.lines;k=length;1#x=0;l#x|x==[1..l]
  ||x==[l,l-1..1]=3;l#x=k[1|z<-[l,x!!0],all(==z)x]

Try it online!
Returns 0, 1, 2 and 3 for mess, rectangle, square and triangle, respectively.
Edit: -2 bytes thanks to Lynn!

R, 101 bytes
"if"(var(z<-nchar(y<-scan(,"",,,"
","")))==0,"if"(length(y)==z,1,2
),"if"(all(abs(diff(z))==1),3,4))

1=Square
  2=Rectangle
  3=Triangle
  4=Random

Code cannot deal with 'NEGATIVE ACKNOWLEDGE' (U+0015) or the square in the code above. This byte can be switched to something different if the input requires contains this byte.
Try it online!

maybe you could use readLines() instead of scan()?

@Giuseppe Can't/too noob to get readLines to work

Hmm, looks like you have to specify file("stdin") to get it to read from console (rather than the next lines of code). That means it'll probably be less golfy. ah well.

Snails, 29 bytes
ada7A
.2,lr
?!(t.
rw~)z
.+~o~

Output key:

0 - Mess
3 - Triangle
6 - Rectangle
7 - Square

It would be 23 bytes without source layout:
zA
.2,dun!(t.rf~)z.+~o~

I've always been keen to play with this language since reading the question that spawned it!

Wolfram Language (Mathematica), 119 bytes
(x=StringLength/@#~StringSplit~"\n")/.{{1}->3,s~(t=Table)~{
s=Tr[1^x]}:>0,x[[1]]~t~s:>1,(r=Range@s)|Reverse@r:>2,_->3}&

Using Replace /. and pattern matching on the character count by line. Replace will kick out the first RHS of a rule that is matched, so the ordering is to test for the 1 character input, then squares, rectangles, triangles, and a fall-through for messes.
square=0,rectangle=1,triangle=2,mess=3
Try it online!

@DomHastings, it's fixed.

Ruby, 115 111 bytes
->s{m=s.split(?\n).map &:size;r=*1..s=m.size;s<2?4:(m|[
]).size<2?m[0]<2?4:s==m[0]?1:2:r==m.reverse||r==m ?3:4}

Try it online!
Anonymous lambda. Outputs:

Square
Rectangle
Triangle
Mess

This looks to fail on some that should be flagged as mess: Try it online!

Ouch, I guess this will have to go as a quick fix. Probably will need to try golfing it a bit more...

Red, 209 bytes
func[s][c: copy[]foreach a split s"^/"[append c length? a]d: unique c
r: 0 if 1 < l: length? c[if 1 = length? d[r: 2 if(do d)= l[r: 1]]n: 0
v: copy[]loop l[append v n: n + 1]if(v = c)or(v = reverse c)[r: 3]]r]

Try it online!
0 Mess
1 Square
2 Rectangle
3 Triangle

AWK, 119 bytes
{p=l;l=L[NR]=length($0)
D=d}{d=p-l;x=x?x:NR>2?\
d!=D:0}END{print x==1?\
3:d*d==1?(L[NR]+L[1]==\
NR+1)?2:3:p!=NR}#######

Try it online!
Output:
0 = Square
1 = Rectangle
2 = Triangle
3 = Mess

C (gcc), 125 123 bytes
Thanks to ceilingcat for -2 bytes.
f(L,n)int**L;{int i,l,c,F=strlen(*L),s=-F;for(l=i=0;i<n;l=c)c
=strlen(L[i++]),s+=c-l;s=n>1?s||F<2?~abs(s)+n?0:3:n^F?2:1:0;}

Try it online!


text:
Compile Quarterstaff to BF
Quarterstaff repo here with additional quarterbf interpreter: rather bereft of documentation, however, but it does contain the two interpreters
you can go to https://tio.run/#quarterstaff to run quarterstaff programs online. however, the TIO BF implementation seems to have limited cells, according to the documentation

The title is rather descriptive, except that it doesn't describe what Quarterstaff and BF are. For this challenge, I have created two languages: Quarterstaff, and a dialect of BF that probably already existed in its exact form, but I wanted to be certain, especially with the I/O format, that it would work, called QuarterBF. In this challenge, you will compile a program written Quarterstaff to QuarterBF (but the underlying conversion should work for any generic BF dialect with byte cells and an infinite tape and such).
I have created interpreters for both of these. However, should you find the spec for one of them here conflicts with the interpreter, the spec is prioritised for the challenge (the interpreters should just be helping you out here)
First, the QuarterBF spec, since it will be easier to explain some of the Quarterstaff concepts afterwards (I cribbed some of this from the esolangs page for Brainf***):
BF spec
Brainfuck operates on an array of memory cells, also referred to as the tape, each initially set to zero. These memory cells can each hold an integer between 0 and 255, inclusive, and the tape extends infinitely to the right (some implementations will use a limited number of cells, hence I made my own to be sure / make an appropriate interpreter easy to find). There is a pointer, initially pointing to the first memory cell. There are no cells to the left of the first memory cell, and attempting to move further left is undefined behaviour. The commands are:
> : move the pointer to the right
< : move the pointer to the left
+ : increment the cell under the pointer, unless the cell is 255, in which case set cell to 0
- : decrement the cell under the pointer, unless the cell is 0, in which case set cell to 255
, : input a character code into the cell under the pointer (described more below)
. : output the character that the integer in the cell under the pointer represents
[ : Jump past the matching ] if the cell under the pointer is 0
] : Jump back to the matching [ if the cell under the pointer is nonzero

In QuarterBF input is interactive. The exact mechanism this works by could be gleaned by reading the source if you wanted, but it's not totally necessary. The important points: it sets a cell to the character code of an input character, sets to 0 on EOF, and to 10 for end of line newlines (which is the newline charcode)
Either way, you don't have to worry so much about how input works, because the values of ? and ! translate essentially perfectly to the values , and . anyway.
Quarterstaff spec:
Quarterstaff's memory consists of registers. one of these registers is called "value", and the others are named variables. variables are case sensitive. Variables can be referenced before assignment and are initially zero (alternately, referencing a variable before assignment does nothing, because if it hasn't been assigned yet, it means it has a value of zero, therefore adding zero has no effect).
[a string of digits] : add the number those digits represent to the value
[a string of letters not preceded by >] : add the variable that the name represents to value
[a string of letters preceded by >] : set the variable to the current value, set value to 0
. : set value to zero
- : multiply value by -1
? : add to value the amount that the underlying bf implementation would set a cell to when , is executed
! : output the character with the charcode corresponding to value.
[ : Jump past the matching ] if value is 0
] : Jump back to the matching [ if value is nonzero
([...] is a while loop)
{ : Jump past the matching } if value is nonzero
} : Jump back to the matching { if value is 0
({...} is a while-not loop)
(, |, ): part of an if else construct...
[any characters not mentioned here] separator between commands; doesn't execute anything, but separates variables or numbers

Explanation of if:
if-style 1:
when coming to this paren, check if value is zero or not
v
(...)
  ^  if value was nonzero, execute the commands within

either way, then continue execution after the )

if-style 2:
when coming to this paren, check if value is zero or not
v
(...|...)
  A   B
if the value is nonzero, execute the subprogram designated A. else execute the one designated B.
then, continue execution after the closing )

(...) is equivalent to (...|)
The challenge
Taking a quarterstaff program as input, compile it to BF; output a program which functions the same, but in BF.
i.e.

it halts if and only if the inputted program halts
outputs the exact same text as it.
if it doesn't halt, it should print the text that the original program prints in finite time, in finite time (it shouldn't put output into a buffer and then print it when it stops executing or something)

Allowances and some restrictions:

you may assume that input to the outputted program is always in printable ASCII and ASCII whitespace (and EOF. Basically, no need to worry about any characters >255 overflowing or whatever), and that the quarterstaff program will never try to output anything other than printable ASCII and ASCII whitespace.
you may assume the inputted program is only ascii printables and ascii whitespace
you may not assume that the variables and values only go up to 255. you need to implement infinite variables and accumulator
basically, you don't get to limit anything (except possible i/o characters). your bf spec has infinite cells, you can use them!
you may assume that the Quarterstaff program has fully matched brackets, and does not invoke undefined behaviour (e.g. trying to output non-ASCII like I mentioned earlier)
you should not invoke undefined behaviour in your outputted bf program. just because I included an interpreter doesn't mean you get to exploit any bugs or lack of exceptions for undefined behaviour. When the spec in this question and implementation differ, follow the question spec. This includes when the interpreter technically could suffer from recursing too deep. doesn't mean you get to assume that a program never recurses that much.

Scoring is by the length of the program, shorter is better; code-golf (this is not metagolf, the length of your bf programs does not matter, as long as they work)
test cases:
prime tester (slightly different from my answer on the prime challenge; a space was replaced with a newline):
10-?[-38a a a a a a a a a a>a10-?]a>b
b[>b>d a>c c[1>c1d>d b d(.>e|>d1>e)c]e f>f1b]2-f(.|1)48!

cat (prints each line after you input it, then exits on EOF)
?[!?]

prints a newline
10!

also prints a newline
5 5!

truth machine:
49-?{49!}49!

I think you forgot to mention that ! resets the value to 0.

Python 3.8 (pre-release), 769 bytes
import base64,zlib
exec(zlib.decompress(base64.b85decode('c$|e(O>dkq5WVv&NG^sQ59(GuRK#}Fdv=dG)b#;{MMCnD$WWA)xWB#6EcrN8>cx!5<2TRq9{u_0F--aRYn0)X-RUJ}NBuc_(1O`p??iUc`>fZ(TQ;OzP-HE8guxkB&RDAgS--{(feY*i#mIVtV^(BvOJt)Kq%1RAA_5p7)CPe{;BX-10FW+u3dSkV4A4M;_<vo>uMN==IgxdbA%B*$9OOCghdi9Bt{>XQ`$81vwk&MJzrXQ!N99ZLqfM)IHZH|WS>0Z-D}}^Zs&Q)jp$ey_Ey}Xa^1jRG`l!#%b8(b=D&|_>RpV)DPhIoVPsJ>cWm(?L@?HxicC!=)>rJC)>V)OxK7#!+M<?k1rq!JYc4?xqYUv}=lnU5kyj%8?N^e3|;i1bIFUlk;&-Df|N6Ri1VzjS!oB_%|4=~YpjG;cP&pF7U*8MOQ1Ng77OTQbU1<1#i=ep787@UHXD@-ty#%}E@Dq{~_p%Bzk7vh0jD%eza$i3<01$tQk;y4jbpI3TP1jWW08<M3Q-oHABlXH?2E)Y0O^P-diDbU*b(AEcAmvB`wp8@s<7csy4$ir*tl6z}j880LTVI*oG5cqx=hipi=w+Ptp@%k$OA{iXS2pkfF4fs-I)5cj*@zt$c;!7!3gBIt~W%&c?HhT(5j!u~6I?(m*5D^$cbd1YG6x9@(Vf4*(Dwh4HuQmTU?%+AO-+#HpM#QrG3m~&3+y')))

Try it online! Test suite (also executes brainfuck)
OK, so this is a version following the specifications, but the rules seem to be missing that ! resets the value to 0. So, at a cost of two bytes, here is a fixed version:
Python 3.8 (pre-release), 771 bytes
import base64,zlib
exec(zlib.decompress(base64.b85decode('c$|e(O>dkq5WVv&NG^sQ59(GuRK#}Fdv=dG)b#;{MMCnD$WWA)xWB#6EcrN8>cx!5<2TRq9{u_0F--aRYn0)X-RUJ}NBuc_(1O`p??iUc`>fZ(TQ;OzP-HE8guxkB&RDAgS--{(feY*i#mIVtV^(BvOJt)Kq%1RAA_5p7)CPe{;BX-10FW+u3dSkV4A4M;_<vo>uMN==IgxdbA%B*$9OOCghdi9Bt{>XQ`$81vwk&MJzrXQ!N99ZLqfM)IHZH|WS>0Z-D}}^Zs&Q)jp$ey_Ey}Xa^1jRG`l!#%b8(b=D&|_>RpV)DPhIoVPsJ>cWm(?L@?HxicC!=)>rJC)>V)OxK7#!+M<?k1rq!JYc4?xqYUv}=lnU5kyj%8?N^e3|;i1bIFUlk;&-Df|N6Ri1VzjS!oB_%|4=~YpjG;cP&pF7U*8MOQ1Ng77OTQbU1<1#i=ep787@UHXD@-ty#%}E@Dq{~_p%Bzk7vh0jD%eza$i3<01$tQk;y4jbpI3TP1jWW08<M3Q-oHABlXH?2E)Y0O^P-diDbU*b(AEcAmvB`wp8@s<7csy4$ir*tl6z}jB~D&Q%)&^NK_gK9FcI01aBmUd-{bXf07~*WxDjY15*zlV$fk|6qT;Jtx5SrHtR5}SrOWaM(rxw>k|Lcj%XOgZ-60|{gy<NThbXEkG{fkd=~OKHPhV^PbKJppa=-s_iH(S5nf(R5Kqbo')))

Try it online! Test suite (also executes brainfuck)


text:
Finite Field Multiplication
Overview
Given the integer representation of three elements in GF(2^64), give the product of the first two elements over GF(2^64) with the reducing polynomial defined as the polynomial m such that m(x) = x^64 + n(x), where n is the polynomial representation of the third element.
You want me to what?
A finite field GF(p^q), where p is a prime and q is a natural number, contains p^q elements. (GF stands for Galois Field, which is another name for a finite field.) The elements of this finite field can be given many interpretations, but the two most common are as the integers between 0 and p^q-1, and as the polynomials with term coefficients between 0 and p-1 and degree less than q. There is a one-to-one correspondence between the base-p integer interpretations and the polynomial interpretations, from a one-to-one mapping between digits and term coefficients:
Integer interpretation (binary) | Polynomial interpretation (given x)
--------------------------------+------------------------------------
0                               | 0
1                               | 1
10                              | x
11                              | x + 1
100                             | x^2
101                             | x^2 + 1
1101                            | x^3 + x^2 + 1

Finite field arithmetic makes the most intuitive sense under the polynomial interpretation, but for brevity, the integer interpretation is used, and operations are described according to the integer representations of the finite field elements involved.
Addition in GF(p^q), like polynomial addition, operates with no carryover. Each digit in the sum is equal to the sum of digits in the addends, mod p. Likewise, subtraction in GF(p^q), like polynomial subtraction, is borrowless, with each digit in the difference being the difference in the corresponding digit in the minuend and subtrahend, mod p. If p = 2, both carryless addition and borrowless subtraction are equivalent to a bitwise XOR.
Multiplication in GF(p^q) relies on (but is not) polynomial multiplication, but with each term coefficient reduced mod p. If the factors are interpreted as integers rather than as polynomials, the operation can be implemented like long multiplication, but with summation of intermediate terms done without carry, as with finite field addition:
     1111
   * 1101
   ------
     1111
   1111
^ 1111
---------
  1001011

Multiplication in GF(p^q) also relies on a reducing polynomial, an irreducible polynomial with term coefficients in the set of integers between 0 and p-1, degree q, and leading coefficient 1 (and thus corresponding to an element in GF(p^(q+1))). Irreducible, in this context, means that it is not equal to any reduced polynomial product, as described above, of any other polynomials with term coefficients in the set of integers between 0 and p-1.
Last, multiplication in GF(p^q) relies on polynomial division, but with each term coefficient reduced mod p. Like reduced polynomial multiplication, this operation can be done directly on the integer representation by doing long division, but with borrowless subtraction rather than subtraction with borrow:
            1100
       ,--------
11111 / 10001001
      ^ 11111
      -------
         11100
       ^ 11111
       -------
            1101

Now, for the actual description of multiplication in GF(p^q).
First, the carryless product of the factors is calculated, as described above, keeping all digits in the product. Then, the remainder of the carryless division of this carryless product and the reducing polynomial (as interpreted as the integer interpretation of an element of GF(p^(q+1))) is taken. This remainder is the final product.
Task
Given 3 64-bit words A, B, and C, return pmod(pmul(A, B), C+1<<64)), where pmul is the carryless multiplication operation as described above, and pmod is the remainder of the carryless division operation as described above. C + 1<<64 can be assumed to correspond to an element in GF(2^65) that in turn represents an irreducible polynomial.
As with most code golf challenges, standard loopholes apply, and shortest program wins.
Test cases
Each test case is represented in four hexadecimal numbers, with the first three being the three arguments A, B, and C, as described above, and the fourth being the expected return value. (All values were calculated by Nemo, an open-source package for Julia that provides support for finite fields, among other things.)
0x0000000000000000 0x0000000000000000 0x000000000000001B 0x0000000000000000
0x0000000080000000 0x0000000080000000 0x000000000000001B 0x4000000000000000
0x0000000100000000 0x0000000100000000 0x000000000000001B 0x000000000000001B
0x0000000200000000 0x0000000200000000 0x000000000000001B 0x000000000000006C
0x0000000000000001 0x0000000000000001 0x702414004010004F 0x0000000000000002
0x0000000080000000 0x0000000100000000 0x702414004010004F 0x8000000000000000
0x0000000F00000000 0x0000000F00000000 0x702414004010004F 0x686D881284A01126
0x0000208000000000 0x0080000000000002 0x702414004010004F 0x870AF102748F8A93

Leaderboards
Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language, copied from here:

var QUESTION_ID=160069,OVERRIDE_USER=8478;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

I think I'll have to read this four or five times to fully understand it, but one question that immediately popped into my mind: In the Task you mention "Given 3 64-bit words", but in the test cases you use "four hexadecimal numbers". What would be alternative appropriate input format/type besides the hexadecimal one you give in the Test cases? I'm a bit confused by the term "words".

"Word" in this context means the unit of information a computer is able to process at once, which, for computers of this generation, is 8 bytes. The test cases are in hexadecimal because that's how most programming languages represent numbers which are intended to be interpreted bitwise. The challenge itself is written to be agnostic to input form, so you can just use a 64-bit integer type, or use arrays or structs of ints.

So the immediate question is: can we use length 64 strings of 0s and 1s as input

Go ahead if you want to. As I said, it's agnostic to input form.

Related.

For input 0x0000000F00000000 0x0000000F00000000 0x702414004010004F I get 0x686d881284a01126, not 0x686D881284A01125.

@orlp Good catch, corrected.

For input 0x0000208000000000 0x0080000000000002 0x702414004010004F I get 0x870af102748f8a93, not 0x870A3202748F8A93

@Tom Hospel Good catch. Corrected.

For input 0x0000000000000001 0x0000000000000001 0x702414004010004F I get 0x0000000000000001. not 0x0000000000000002.

APL (Dyalog Unicode), 39 36 bytesSBCS
{×≢⍵:(⍺×⊃⌽⍵)≠((⍺⍺×⊃⍺)≠1↓⍺,0)∇¯1↓⍵⋄0}

Try it online!
-3 bytes thanks to @ngn.
A recursive inline operator (dop). You can assign it to f and use it as a(m f)b.
A port of orlp's Python answer, but using bit arrays instead of integers. Dyalog APL has neither 64-bit integers nor bitwise ops, but can simulate them pretty well using array ops.
How it works
{×≢⍵:(⍺×⊃⌽⍵)≠((⍺⍺×⊃⍺)≠1↓⍺,0)∇¯1↓⍵⋄0}  ⍝ ⍺←A, ⍵←B, ⍺⍺←M
{×≢⍵:                            ⋄ }  ⍝ If B has at least one bit,
                            ∇         ⍝   Recursive call with M fixed with...
                      1↓⍺,0           ⍝     A shifted left once
                     ≠                ⍝     XORed with
              (⍺⍺×⊃⍺)                 ⍝     M × highest bit of A
             (             )          ⍝     as left arg, and
                             ¯1↓⍵     ⍝     B shifted right once as right arg
     (⍺×⊃⌽⍵)≠                         ⍝   XOR the result with A × LSB of B
                                  0   ⍝ Otherwise, return a zero,
                                      ⍝ which is equivalent to 64 zero bits

The single zero is returned only on recursion. Then it becomes the right arg of (⍺×⊃⌽⍵)≠, and it acts exactly like a vector of 64 zeros (since (⍺×⊃⌽⍵) evaluates to a 64-length vector).

Perl 5 -p, 51 bytes
$\=$'*($\>>63)^$\<<1^$`*($&<<$_&1)for-63..!/ .* /}{

Try it online!
I originally thought this would be hard for perl, but this isn't too bad. All the $s of course still hurt for arithmetic challenges..

Python 2, 57 bytes
f=lambda a,b,m:a*b and b%2*a^f(a*2%2**64^(a>>63)*m,b/2,m)

I really tried to golf this in Rust, but the language is just not suitable for golfing. So here it is in Python.

Jelly, 22 bytes
Bæc/ḣ-64æcB}ʋƬUSḣ64UḂḄ

Try it online!
Works either as a function or a full program. This takes two arguments: a 2-element list [A,B] for the numbers to multiply; and the argument C that specifies the polynomial. The TIO link contains a footer that prints the result in hexadecimal, making it easier to verify the test case.
Algorithm
The calculation is done by representing each finite field element that we're working on as a list of bits that represent the coefficients of the polynomial. (For working on finite fields with this representation, we'd really want them to be little-endian, but Jelly's base conversion operators are big-endian, and thus the program ends up swapping endianness a couple of times.) Converting A and B to this form, then convolving them (which is the same operation as polynomial multiplication), gives us a polynomial (not necessarily a normalised one) representing the result.
We then need to normalize it (i.e. reduce it to degree at most 63) by doing the polynomial long division, i.e. taking the result modulo x64+C (where C is interpreted as a polynomial). This is the same as taking the result modulo x64−C because addition and subtraction are equivalent in binary finite fields. If we right-shift the result polynomial by 64 degrees, then multiply by C and add back the parts of the polynomial that fell off during the shift, this doesn't change the value modulo x64−C (because some multiple of x64 got subtracted from the result and the same multiple of C got added, thus reducing the result by a multiple of x64−C and thus not changing the remainder upon dividing by x64−C). Additionally, because C has degree at most 63 (it's a "64-bit word" interpreted as a polynomial), the shift-multiply-add sequence must reduce the degree of the resulting polynomial unless it's already 63 or lower, i.e. it's already normalized. It's therefore possible to repeat the shift-multiply-add (with polynomial addition and multiplication in GF(2), i.e. pointwise XOR and XOR-convolution) until we reach a value that remains unchanged, which must be the normalized result.
This algorithm is tweaked a little to be terser in Jelly. There are only two major changes. One is that we don't bother using only 0 and 1 as coefficients in the polynomials; in GF(2), 0 and 2 are the same number (all that matters is oddness versus evenness), so we just use regular pointwise addition (which doesn't carry from one coefficient into the next) instead of pointwise XOR and regular convolution instead of XOR-convolution (this saves lots of bytes during the program and requires only a Ḃ to fix the coefficients back to the 0-or-1 representation near the end). The other is that instead of immediately adding back the coefficients that got shifted off, they're remembered in a list and added back at the end (which is clearly equivalent because if we added them back immediately, they would just get shifted off again on the next iteration of the shift-multiply-add loop). (We actually remember the whole polynomial, but just take the least significant 64 coefficients for summing purposes.)
In order for the sum to work correctly, we need to use a little-endian representation (so that the coefficients that are added to each other when summing, i.e. the ones that are the same distance from the left end of the list, correspond to the same power of x0). It's possible to do the sum and the cut down to 64 coefficients either way round, and doing the sum first saves on the need for an extra quick to specify which array rank we want to work on. Then we convert the polynomial back to a big-endian representation, and then to a number, as the program's output.
Explanation
Bæc/ḣ-64æcB}ʋƬUSḣ64UḂḄ
B                        Convert {[A,B]} to big-endian binary
 æc                      Take the convolution of
   /                       the converted version of A with that of B
             Ƭ           Repeatedly loop, until nothing changes:
            ʋ              (grouping/bracketing mark, sets the Ƭ's scope)
    ḣ                      take the prefix
     -                       that omits
      64                     the last 64 elements
        æc                 and take its convolution with
          B                  the big-endian binary representation of
           }                   the second argument
              U          Reverse {the result of} each {iteration}
               S         Sum corresponding elements {of the reversed results}
                ḣ64      Take the first 64 elements of the sum
                   U     Reverse back
                    Ḃ    Replace each element with its value mod 2
                     Ḅ   Convert from big-endian binary to decimal

The Us mark where the program changes from big-endian to little-endian notation for its polynomial, and where it changes back again.

MMIX, 36 bytes (9 instrs)
00000000: e3030000 76040100 3f010101 70ff0003  ẉ¤¡¡v¥¢¡?¢¢¢p”¡¤
00000010: 3b000001 c6030304 c60000ff 5b01fffa  ;¡¡¢İ¤¤¥İ¡¡”[¢”«
00000020: f8040000                             ẏ¥¡¡

Disassembled and commented
ffm SET  $3,0           // r = 0
0H  ZSOD $4,$1,$0       // loop: t0 = B & 1? A : 0
    SRU  $1,$1,1        // B >>= 1
    ZSN  $255,$0,$3     // t1 = A >> 63? C : 0
    SLU  $0,$0,1        // A <<= 1
    XOR  $3,$3,$4       // r ^= t0
    XOR  $0,$0,$255     // A ^= t1
    PBNZ $1,0B          // if(B) goto loop
    POP  4,0            // return r

Russian peasant multiplication. Surprisingly simple! I think this is the first time MMIX has tied for shortest.

PARI/GP, 69 bytes
f(a,b,c)=lift(g(a)*g(b)%(x^64+g(c)))%(x-2)
g(n)=Pol(Mod(binary(n),2))
Attempt This Online!