text:
Significant Whitespace: Robbers
This is part of a Cops and Robbers challenge. Go here for the cops' part.
For the purpose of this challenge, we'll define whitespace as only linefeeds (0x0A) and spaces (0x20). Note that most languages and regex flavours consider many other characters as whitespace as well, both inside and outside the ASCII range so you might not be able to make use of the corresponding built-ins.
The Robbers' Challenge
A cop's answer can be cracked by transforming it into a valid program or function (in the chosen language), which performs the task of removing whitespace from an input string, by inserting whitespace into the code. For example if you received the following input:
H e l l o,
 W o r l  d!

The program should output
Hello,World!

After inserting whitespace, the byte count of the solution must not exceed the byte count stated in the cop's answer. You don't have to find the exact same solution as the cop intended, as long as yours is valid by the above constraints.
If you manage this, post an answer with the solution, linking to the cop's answer, and leave a comment on the cop's answer linking back to yours.
The robber who cracks the most cop answers wins. Ties are broken by the sum of sizes of the cracked cop answers (in favour of the robber who cracks longer submissions).
Each cop answer can only be cracked once, and of course, you're not allowed to crack your own answer. If the cop's answer turns out to be invalid before or after being cracked, it is not counted towards the robber's score.

Haskell, 100 bytes, by Laikoni
main=interact$id doid lines id words
doid oi d o id=do
 iddoid<-do oi id
 oid<-do o iddoid
 do d oid

><>, 40 bytes, by DanTheMan
v <<
i/\
:=
:
:a?
0/>/
1?o
-=
="
?
;"
>^

Really fun to work out.
Try it on ><>language

Good job! I'm glad you enjoyed cracking it.

JavaScript ES6, 199 bytes by Arnauld
s=>eval(atob`ISYgJiAtOkI8Qk97BRBeaxZFShoUZSsiOGkMenNy`.replace(/./g,(c,i)=>String.fromCharCode(c.charCodeAt()^(k+="     S    e c  r   e t     C    o   d  e   ".split(/\w/)[i%11].length)),k=0)).join``

I realized the splitting "SecretCode" meant I was looking for 11 numbers that summed to (I assumed) 33. This is a stars and bars problem where the number of spaces are the stars and the letters in "SecretCode" were the bars. I did the math to see how many combintations there were to try (1,917,334,783 combinations) and decided to just brute force it, took all day.
There's probably a smarter way to have gone about it, for instance noticing that k has to be 33 and 66 for index 10 and 21 respectively, but I'm lazy.

Hey, well done! ;-)

$/**/=/[ \n]/;s['sp'+'lit']($)... oh, that's dirty.

In case anyone was curious about my brute force attempt, it was http://pastebin.com/aN9Z1jVM

C, 475 bytes by rexroni
#include<unistd.h>
#define a char
#define b *
#define c write
#define d stdin
#define e stdout
#define f read
#define g (
#define h )
#define i while
#define j if
#define k 0
#define l &
#define m ,
#define n =
#define o ;
#define p 1
#define gpml ml h
#define abo
#define ml d m p
#define jg d o abo
#define lb abo d
#define gf h abo c
#define jgm b e n
#define pml f g
#define gpm lb
int main(){a jg a jgm l jg i g pml k m l gpml h j g d!=' '&&gpm!='\n'gf g p m l gpml o}

I might start using some of these defines :)
After the pre-processor the code looks something like this:
int main(){
    char stdin;
    char *stdout = &stdin;
    while(read(0, &stdin, 1))
        if(stdin !='' && stdin!='\n')
            write(1, &stdin, 1);
}

Wow! Good work.  I was even having trouble reading it by the end, and I wrote it.

@rexroni #defineabo threw me off for a while. At first I thought it had to be #define ab o which would just add some extra ;s, but that didn't work near the end.

yes, that was specifically chosen to make it harder :)

Ruby, 86 bytes + 1 flag = 87 by histocrat
eval"( T $ }{(! // ; : 67 8 ? 32. && )".gsub(/ |(.)/){$1&&$&.ord.^($'.count(' ')).chr}

This was really fun, each character in the string passed to eval is replaced with the character code (ord) XORed ^(...) against the number of remaining spaces in the string. The resultant code is:
$_.tr!(''<<32<<10,'')

RprogN, by Ataco
This appears to do the trick
' ' ` R
"
" ` R

I accidentally golfed it while cracking haha, down to 14 bytes

I'm really curious how you golfed it.

@ATaco the program is just 14 bytes. Did you count a trailing linefeed or something?

Looks like 15 bytes to me

@ATaco I was wrong, I couldn't test newlines on the compiler online, which in turn caused me to think it was working but I had removed the lf literal

V, 37 bytes, by DJMcMayhem
O     VrS200@"kIi|D@"A üî|D@"

Unprintables:
O     <esc>Vr<C-a>S200<esc>@"kIi<C-v><C-v><esc>|D@"<esc>A üî<esc>|D@"

TryItOnline
The ü really threw me for a loop, I kept expecting both it and î to be commands.
O                 # Insert 5 spaces above this line
Vr<C-a>           # Change them all to <C-a>
S200<esc>         # Replace the line with 200
@"                # Play back the 5 <C-a>'s, 200 -> 205
k                 # ????
Ii<C-v><C-v><esc> # insert "i<C-v>" so our line is now "i<C-v>205"
|D@"<esc>         # Delete the line and then run it, which inserts "Í" (ASCII 205)
A üî<esc>         # Append " üî" so our line is "Í üî"
|D@"              # Delete the line and run it

Í üî in V translates to :%s/ \|\n//g in vim, which globally removes all whitespace.  The Í command is on the wiki, and the ü and î are | and n respectively with their high bit set

Good job! That's the exact solution I had. :)

C, 140 bytes by betseg
#include<stdio.h>
int main(){int a=getchar();while(a!=EOF){//\a=getchar();
if(a!=10&&a!=32)//\\putchar(a^10^32);
putchar(a);a=getchar();}}

(I also hope I'm doing this right.)

Ninja'd me by one minute!

@KritixiLithos Same, was just about to submit when this anwer popped up ^^

MATL, 22 bytes by Luis Mendo
Though I can't be sure why, this seems to work
t' @ * 'dm1e5%M
dw%Y
(

I'll have to see if I can work out what it's doing.  I figured that the comments had to have line feeds after them and then it was just a matter of getting the spaces in the correct spots.

Nice, +1 I added a partial explanation in my answer :)

@StewieGriffin, thanks for the explanation.  I was trying to work why it worked, but it was going slowly.  Very comprehensive docs Luis:)

@MickyT You mean verbose like Java :-P Nice cracking work!

MATL, 22 21 bytes by Luis Mendo.
Finally... MickyT cracked it while I was writing an explanation, so his answer is the "valid" one. I posted this anyway, in accordance with this meta post.

M and Y are unnecessary and are commented out. It's enough to add 4 whitespace characters, not 5.
t' @ *'dm1e5%M
dw%Y
(

This is equivalent to the more compact:
t' @ *'dm7dw(

Partial explanation:
         % Implicit input
t        % Duplicate input
' @ *'   % String with ASCII-values [32   64   32   42]
d        % diff, giving [32  -32   10], 32 is space, 10 is newline
m        % ismember, checking if the character is 32 or 10
1e5      % 10000, but could just as well be 7
d        % Taking the diff of the scalar 1e5, returning an empty matrix []
w        % Swap stack in order to use ( below
(        % Equivalent to x(y)=[], where x is the input string, and y is the logical
         % vector found using ismember (m)
         % Implicit output

Nice cracking work!

Thanks :) I knew nothing about MATL before I started... I guess my explanation is not entirely correct (but should be fairly close?). It took me a long time, since the 1e5 either printed 100000, or 1e was a call to reshape, but then what was 5? (I see now that the % is in the end of the line, so it would be 5M, not a five and an M. Also, I thought I had to have Y( on one line. All in all, a very nice MATL tutorial :)

The explanation is totally correct :-) Yes, it's a good (if only a little hard) way  to start with a language

Whitespace, 68 bytes, by Ephphatha

68 bytes, 21 tabs: LSSLSSTLSLSTLTSTTTSSSTSTSLTSSTSLSLTSLSSSTSTTSLTSSTLTSLSSLTTTTLSSLSLL
71 bytes, 21 tabs: LSSLSSLTLTSSSLTTTSSSTSTSLTSSTLTSLSSLTTTSSSTSSSSSLTSSTLTSLSSLTTTTLSSLSLL
72 bytes, 21 tabs: LSSLSSSTTTTTTLSLSTLTSTTTSLSSSSTSTSLTSSTLTSLSLSSSSTSSSSSLTSSTLTSLTLSSLSLL
65 bytes, 15 tabs (too short): LSSLSSLSLSTLTSTTTSLSSSSTSTSLTSSTLTSLSLSSSSTSSSSSLTSSTLTSLTLSSLSLL

Since Whitespace only consists of space, tab, and LF characters (here annotated
as S, T, and L), the entire program needs to be reconstructed, with the
only constraint being that it have exactly 21 tabs to match the cops submission.
I start with a working program, but it's too short and needs 6 more tabs. It
beats the target by 9 bytes, so I could have submitted this as another cop
program, but I don't think it's interesting enough to warrant a second
Whitespace answer.
# 65 bytes, 15 tabs
loop:                        # LSSL
    0 dup readc retrieve     # SSL SLS TLTS TTT
    dup 10 - jz loop         # SLS SSSTSTSL TSST LTSL
    dup 32 - jz loop         # SLS SSSTSSSSSL TSST LTSL
    printc                   # TLSS
    jmp loop                 # LSLL

The simplest way to add more tabs would be to use 63 (STTTTTT) as the address
for reading characters instead of 0 (empty).
# 72 bytes, 21 tabs
loop:                        # LSSL
    63 dup readc retrieve    # SSSTTTTTTL SLS TLTS TTT
    …

That only adds bytes, though. If we retrieve before every usage, we can
eliminate three dups, which have no tabs (SLS). (This is also the only of
these versions without a stack memory leak.)
# 71 bytes, 21 tabs
loop:                        # LSSL
    0 readc                  # SSL TLTS
    0 retrieve 10 - jz loop  # SSL TTT SSSTSTSL TSST LTSL
    0 retrieve 32 - jz loop  # SSL TTT SSSTSSSSSL TSST LTSL
    0 retrieve printc        # SSL TTT TLSS
    jmp loop                 # LSLL

We can do better. If we compound the subtractions, 32 (STSSSSS) can be replaced
with 22 (STSTTS), which gains 2 tabs and saves 1 byte. Then, the second branch
doesn't dup and the print would obtain an unmodified value with 0 retrieve,
which gains 3 tabs and adds 3 bytes. For the last tab, a negative sign is added
to one of the zeros.
# 68 bytes, 21 tabs
loop:                        # LSSL
    -0 dup readc retrieve    # SSTL SLS TLTS TTT
    10 - dup jz loop         # SSSTSTSL TSST SLS LTSL
    22 - jz loop             # SSSTSTTSL TSST LTSL
    0 retrieve printc        # SSL TTT TLSS
    jmp loop                 # LSLL

These programs require an implementation, that allows the sign to be omitted for
zero, so will not work with the reference interpreter, which TIO uses.
For this solution and others in Whitespace, see ws-challenges.

The final version only needs an added sign byte to be acceptable for the reference implementation, nicely done :) https://tio.run/##LYtRCoAwDEO/m1PUC@wc/nsC2QoOyioq7Pi105GSkEfTj/rIfe5Z3MEcRwgnEBMRRw1FGT4SP5psAsQrfWvAfRVV426XlgWbZGuFtTZJKb0

C#6, 201 bytes, by milk
using System.Linq;
_=>string./**/
#if trueJoin
(/*"*//*/""/**//*/"*/",
#else
Concat(//*/,
#endif
from m in" "let p=$@"{@"
"[1]}"from i in(_.Replace(p,@""))where!new[]{p[0]^32^10}.Contains(i)select@i);

repl.it demo
trueJoin is not defined, so only string.Concat() remains.
p is "\n". p[0]^32^10 is space. It would have been (a bit) more difficult if it's p[0]^42 or other similar constants.

As commented on milks answer this needs C# 6+, if they change it can you too?

Befunge-98, 65 bytes by ninjalj
~v       >#@
 >::':'0--\'[';--!8v1+!
*1+j  !j,v         >#@

Try it online!
This was a lot of fun. I deduced that since there are few direction-changing commands and no ^<[]?x or similar, it has to use wrapping. I then wrote a Python script to help with getting the spacing right for the j's.
The code works by taking input (~) and duplicating it twice (::). It then subtracts 10 (':'0 or ord(':') - ord('0')) and 32 ('['; or ord('[') - ord(';')). Then, the second result is logically negated (1 if was space, 0 otherwise) and an 8 is pushed.
Now comes the part that needed figuring out what to skip. The 1+! is skipped by continuing to the next line. # skips the @. The logically negated result (0 or 1) is multiplied by the 8, and 1 is added.
The code then jumps that many (i.e. 1 or 9) spaces plus one extra as the IP moves. If the character wasn't a space it ends up at the !. The character code minus 10 is logically negated (1 if was newline, 0 otherwise). j then skips nothing, and the print (,) is called and the loop resumes by wrapping vertically.
If the character was a space, the bottom line loops again with 32, 22 as the bottom of stack. The first j jumps 705 spaces. Then the line loops a third time. If there are more than two 10's left on the stack (the code only leaves those), the first j jumps 100 spaces and the loop repeats. Otherwise, the first j jumps to the !, a zero is negated, the second j jumps over the print and the program continues.
I managed to golf it down to 59 bytes.

Listing the number of the cop in your header is fine (since the tiebreaker rewards larger sizes anyway).

reticular, 43 bytes, by Conor O'Brien
ISBqv<>>$$4j
E :d/v$v?
c+91d/ v?E
;!?l$/o $

Try it online!
This was more difficult for me than it should have been because I was too stupid to find the documentation and ended up having to guess how some of the commands worked. So some of this explanation may not be entirely accurate, but this was my basic understanding of the code.
I               Push all the input on to the stack as a string
 S              Convert it into a character array.
  B             Turns that array into individual characters on the stack.
   q            Reverse the stack so the first letter is on top.
    v           Move down...
    /           ...and turn left.
E :d            Duplicate the value and test if equal to space.

       v?       If it is a space we move down until we wrap to the top.
       >$$      Drop the test result and the space.
          4j    Jump over the next 4 commands (having wrapped to the start).
    v           Bringing us back to the first down arrow, ready to test the next char.

     v$         If it wasn't a space, drop the test result and move down.
c+91d/          Turn left and push a newline (char 10) on to the stack.
       v?E      If equal, we go down, following the same path as with the space.

     /          If not equal, turn down.
   l$/          Then turn left, drop the test result, and push the stack size.
;!?             If zero (the stack is empty) we terminate.
        o$      Otherwise wrap around, drop the stack size, and output the char.
     /          Then turn down wrapping around to the top of the program.
    v<          Then turn left and down to start the process from the beginning again.

There's docs on the github wiki.

good idea! And impressive that you did this without the wiki :D

Vyxal 3, 12 bytes cracks Alan Breadel
#?“" "₉r""₉r

Try it Online!
Alan didn’t say how much white space was needed, so I took a wild guess and added one to the string literal and it worked

Yes, I was quite surprised that you didn't need to add in a newline as well.

@LarryBagel Late reply but - in Vyxal 3 comments start with ## , not just a single #.

Vyxal, 18 bytes cracks emanresu
#ȧ
‛  (#
FṘ₴#
Ṙ‛

Try it Online!

Minkolang v0.15, 88 bytes by Kritixi Lithos
$oI[dd" "=$r'10'=1J,? 1R]r$O3.14
$$$
Cdollars             >
$$$
Ceverywhere           >x

Explanation
                               # Layer 1
$o                             # input chars onto stack
  I                            # stack length pushed to stack
   [                    ]      # loop popped TOS times (length of string)
    dd                         # duplicate, duplicate
      " "                      # push space to stack
         =                     # equality check
          $r                   # swap
            '10'               # number 10 to stack (LF char)
                =              # equality
                 1J            # or
                   ,           # not
                    ?          # if true jump next
                               # drop to layer 2
                      1R       # rotates the stack 1 time
                         r     # reverse the stack
                          $O   # output the stack
                             . # stop
$$$                            # Layer 2
                     >         # shift right and then drop to layer 3
$$$                            # Layer 3
                      >x       # shift right, pop char off stack and drop to Layer 1 (end loop)

Well done in cracking it! I was hoping the Comments would be confusing, but nice job nevertheless!

@KritixiLithos to be honest once I split the layers and realised that most of the work was done in the top layer, it became easier.  I learnt a bit about the language doing this, so thanks :)

C#, 159 bytes by LethalCoder
using System.Linq;s=>string.Join("",string.Join("",s.Split(@"
".Replace(new string((char)0x0D,1),"").ToCharArray())).Select(c=>c+""!=""?c+"":"").ToArray());

repl.it
The string at the end of line 1 is " \n" (space+newline).
/*Func<string, string> Lambda =*/ s =>
    string.Join("",                                                           // No-op
    string.Join("",                                                           // Join (without whitespace)
        s.Split(@" \n".Replace(new string((char)0x0D,1),"").ToCharArray())    // Split on whitespace
    ).Select(c=>c+""!=""?c+"":"").ToArray());                                 // No-op


text:
Labyrinth Polyglot
Create a program that can create a randomly arranged maze (The path of the maze changes each time) with exactly 1 exit and one enterance and a minimum size of 8x4 and max size of 32x32, with the exact dimensions x and y as input
Submissions can be original code, but to score higher add onto a submission with another language (polyglot)
Writing code in labyrinth gives brownie points as suggested by Mistah Figgins :)

Example Case (8x4):
__   _____
| | | __ |
|_____|  |
|  |  _| |
|____|   |

Non-Examples:
__
|_|
Too Small
__   _____
| | | __ |
|___|_|  |
|  |  _| |
|____|   |
No Solution

Apologies if challenge is confusing or cumbersome, this is my first PCG and after reading up on the meta I still had some blurry regions.

Could you elaborate on what within the same function(s)/file(s) means? Also, we need an answer in Labyrinth

You should have posted on the Sandbox first, to have gotten feedback.

@Pavel Will fix right now, thank you! I guess I got too caught up in the theatrics

Can you provide an example valid labyrinth?

randomly What does that mean? Someone can have two possible labyrinths and randomly choose among those two. On the other extreme, you may require that all possible labyrinths are produced with the same probability, or at least with nonzero probability. What's the spec here?

What exactly is the bonus for polyglotness?

C and C++, 603 bytes
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define Y x+1+rand()%(y/2-1)*2
#define C(n,i) if(j n&&M[i])c[b++]=i;
typedef int I;I m;I main(I argc, char**argv){srand(time(0));I x=atoi(argv[1]),y=atoi(argv[2]),*L=(I*)malloc(2*x*y*sizeof(I)),j=Y;char*M=(char*)malloc(x*y);memset(M,1,x*y);M[j]=0;for(;;){I b=0,c[4];C(%x>1,j-2)C(>2*x,j-2*x)C(%x<x-3,j+2)C(/x<y-3,j+2*x)if(b){I z=c[rand()%b];M[z]=M[z+j>>1]=0;L[m++]=j=z;}else if(m)j=L[--m];else break;}for(;;){I j=Y;if(!M[j]){M[j-x]=0;break;}}for(j=0;j<y;++j){for(m=0;m<x;++m)putchar(M[j*x+m]?88:32);puts("");}free(M);free(L);}

Edit: this was written before the prompt was revised. This program just outputs X for the walls and places only one door.

482 bytes

source: Stack Exchange

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

sort: votes


text:
Ways of specifying random generation in challenges

Note: As per consensus on Meta, challenge-writing questions are on topic here.

In light of this "thing to avoid when writing challenges", I started to think about challenges involving random generation of certain kinds of objects.
It sometimes happens that I want to post a code-golf challenge that involves randomly generating a foo, where

it's very easy to check whether a given thing is a foo, and
it's a little harder to quickly generate a "good-quality" random foo.

As an example, a foo might be a binary matrix where there are no segments of 4 equal bits in any direction.
It's easy to check whether a given binary matrix is a foo, but generating a random foo with a nicely spread distribution seems to require a backtracking algorithm or something similar.
Anyway, now I'll need to objectively specify what qualifies as a random foo, and I'd like it to be "unpredictable" in the intuitive sense that when I run the program several times, the results always look different.
The most restrictive approach is to require that the output is uniformly random: all valid foos have the same probability of being generated.
This is usually too restrictive, because I have no idea how to do it save for generating all valid foos, removing duplicates and choosing one, which is boring and slow.
My next idea is to require that all valid foos have a positive probability of being generated.
However, this means that the following approach is valid: generate a random foo-like thing (in our example, a random binary matrix), if it's a foo then return it, otherwise return a hard-coded foo (say, the identity matrix).
This is also somewhat boring, since it's basically just a recognizer of foos tacked to a random matrix generator.
Could there be a nice general definition for an unpredictably random foo?
TL;DR
Is there a good way for specifying an "unpredictable" randomly generated object that doesn't fix the distribution but discourages hard-coding?

We have a standard definition for random on meta that would ban hard-coding, but not restrict it so far as perfectly uniform.

Great question. I've found in the past that specifying randomness is hard. Especially for the scenario you describe, there's also the issue that you can just generate random candidates and redo if they're invalid. That even gives you a uniform distribution, but non-deterministic runtime. When specifying uniform distribution there's also the issue that real solutions are never perfectly uniform. This is a very subtle issue. +1

@MartinEnder Right, I forgot that approach. I can disallow it and the other slow algorithm with time bounds, but they still allow the "one hard-coded foo" solution.

seems like you could specify K3/K4 CPRNG, most languages will have a library https://en.wikipedia.org/wiki/Pseudorandom_number_generator

@Zgarb a big problem with disallowing "Generate and redo" is that the majority of language's RNG libraries do just that.

A possible way to disallow "generate and redo" (rejection sampling) in certain challenges is to limit running time to something reasonable. For many problems rejection sampling is unfeasibly long because the target region is a small subset of the whole space

@NathanMerrill I don't want to explicitly disallow any technique. My goal is to implicitly disallow "dumb" rejection sampling that takes forever to run, and other boring solutions. Rejection sampling is sometimes fast and can be used as part of interesting algorithms.

Return a thousand different foos
This makes it impossible to return hardcoded values and have a half decent golf. However, a legit foo generator does have a small chance of outputting duplicate foos unless it is actually checking them. To remove the burden of checking, an empirically tested failure rate, say 10%, could be specified as acceptable.
Be aware of the birthday paradox, that the probability of duplicates may be higher than you think. If there are only a million possible foos, a thousand random foos will have a probability of about 0.6 that there is a duplicate in there somewhere, and that's assuming that foo generation is completely uniform. If this could be an issue, require say 900 unique foos for every 1000 generated, which is far more generous for a genuine foo generator but still impractical for hardcoding.
This also allows you to repeatedly generate foo-like things and check fooness until you get foos. I think this is a valid solution myself, but if you don't like it:
Do it quickly
The chances of a completely random foo-like thing being foo are probably quite low, so specifying a time limit is likely to force a genuine attempt at foo generation.
To accomodate the speed differences between different languages, you may want to have different time limits depending on the language like Hackerrank: https://www.hackerrank.com/environment . However if you specify large enough foos the probability of random foo-like things being foo might be really low, so a "before the heat death of the Universe" rule might be sufficient.

I think you're onto something here. "Running the program N times will produce no duplicates at least 90% of the time" is concrete and pretty easy to test, and it can be combined with a time bound to prevent brute forcing and simple rejection sampling too.

I don't claim to have the ultimate solution to the problem (or that this list is exhaustive), but I want to outline some possible approaches that come to mind and why they would or wouldn't work. I also won't address tangential issues like whether using the current timestamp as a source of randomness is sufficiently "unpredictable" and how to enforce certain properties of the probability distribution — I'll just focus on avoiding solutions that use hardcoding.
Not a solution: disallow hard-coding explicitly
This is a bad idea. It's a non-observable requirement (which means you can't determine whether it's satisfied just by running the program), which is strongly discouraged on PPCG and may be outright impossible if running the program on any other platform, where submissions are verified in an automated manner. The problem with a requirement like this is that you'd have to start by finding an objective definition for "hard-coding". In general, if you try this, you're only going to make things worse.
Make hard-coding infeasible
If you can't disallow it completely, but you don't want people to use it, then you can try to design the challenge such that hard-coding is simply not a competitive approach. This is possible if the objects that should be generated are sufficiently large and incompressible that putting one example into the code would require a lot more bytes than writing an algorithm that generates valid solutions randomly. In your specific example, that's not the case of course, because identity matrices are valid and are generally easy to generate, but for other problems, that might not be the case. If the target objects are sufficiently irregular, just require them to be of a large size, which probably won't affect the byte count of an actual algorithm but will blow up the hard-coded part.
Parameterise the output
Often, these problems come with one or more natural parameter, like the size of the matrix in your example. If so, making that parameter an input can be sufficient to make hard-coding impossible or at least impractical. In some cases, it might be easy to hard-code one specific solution for a given parameter value that has been found manually or via extensive search, but maybe there is no simple closed form for an instance of these solution in general, so it's not possible to generate a default value for arbitrary inputs easily. Again, this is not the case for the example you mention, because the identity matrix works at any size, but an optimal solution for this related problem is usually highly irregular, so it's not possible to have default value without actively searching for valid values anyway. You can combine this with a time-limit to avoid a brute force search for a default value.
Put some restriction on the probability distribution
If you're willing to give up a completely unrestricted probability distribution, you can put some constraints on it, that still give answerers a lot of freedom in choosing their distribution but which make hard-coding a difficult or impossible:

The simplest constraint that comes to mind is to require the difference between minimum and maximum probability for any possible output to be below a certain threshold. A hard-coded approach will likely have almost-zero probabilities for almost all outputs and a probability close to 1 for the default value. If you require the maximum difference to be below 0.1 say, there would need to be 10 (randomly chosen) default values to make the approach an option. Similarly you could also just require a minimum probability for each possible output, e.g. 1/(2*N*), where N is the number of possible outputs.
Alternatively, you can require that there are no (likelihood) gaps in the distribution, so that there is no interval of size δ (chosen by you) such that both higher and lower probabilities exist. That means there can't be any outliers in terms of likelihood, which are likely generated by a hard-coding approach.

The main issue with these approaches is that they're a lot harder to reason about, proving correctness of answers is difficult, and experimentally verifying the correctness can be impossible for large output spaces. Still, they provide a principally observable requirement for the program which can make hardcoding impossible.
These approaches may also need a time limit, because one way to increase the probability of the non-default values would be to attempt finding a random foo multiple times before falling back to the default value.

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


text:
Bridges are metaphors for everything in ASCII Art
(with apologies to Jim West for the title, and randomly inspired by Cisco's textual representation of their logo: .:|:.:|:. for the concept)
Given an input integer 1 <= n <= 255, output an ASCII art representation of a suspension bridge of distance n following the below construction rules:

The start and end of the bridge (not counted in the n distance) are always -| and |-, so the bridge can appropriately connect to the highways next to it.
The bridge doesn't extend downward (the roadway level, composed of the - row, is the bottom row).
There can be at most two roadway pieces -- in a row, any longer span requires suspension cables for support.
The suspension cables \ extend from the roadway up to the towers | in straight lines.
The towers | must be tall enough to support the adjacent suspension cables, but no taller.
The bridge must be balanced left-to-right about the middle point, favoring the center sections whenever possible.
All of the above should result in a minimization of the cables, but just to be clear, the number of suspension cables must be minimized while still following the above rules.

To provide a visual representation, here are the expected outputs for n = 1, 2, 3, ... 15 --
1
-|-|-

2
-|--|-

3
-|\-/|-

4
-|\--/|-

5
 |\   /|
-|-\-/-|-

6
 |\    /|
-|-\--/-|-

7
 |\     /|
 | \   / |
-|--\-/--|-

8
 |\      /|
 | \    / |
-|--\--/--|-

9
 |\       /|
 | \     / |
 |  \   /  |
-|\--\-/--/|-

10
 |\        /|
 | \      / |
 |  \    /  |
-|\--\--/--/|-

11
 |\         /|
 | \       / |
 |  \     /  |
 |\  \   /  /|
-|-\--\-/--/-|-

12
 |\          /|
 | \        / |
 |  \      /  |
 |\  \    /  /|
-|-\--\--/--/-|-

13
 |\           /|
 | \         / |
 |  \       /  |
 |\  \     /  /|
 | \  \   /  / |
-|--\--\-/--/--|-

14
 |\            /|
 | \          / |
 |  \        /  |
 |\  \      /  /|
 | \  \    /  / |
-|--\--\--/--/--|-

15
 |\             /|
 | \           / |
 |  \         /  |
 |\  \       /  /|
 | \  \     /  / |
 |  \  \   /  /  |
-|\--\--\-/--/--/|-

Input
A single positive integer in any convenient format, n > 9.
Output
The ASCII-art bridge following the above construction technique.
Rules

Leading or trailing newlines or whitespace are all optional, so long as the bridge characters themselves line up correctly.
Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
If possible, please include a link to an online testing environment so people can try out your code!
Standard loopholes are forbidden.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

#RageQuit (http://05ab1e.tryitonline.net/#code=RDTigLppMy0yw7ciICBcInPDl8OALnPCpi5CdnlEwrnDiWnCqH1S4oCeXC_igJ4vXOKAocKrJ3wuw7gnIC7DuH0nICct4oChwrt9wrkxUWkiLXwtfC0ifcK5MlFpIi18LS18LSJ9wrkzUWkiLXxcLS98LSJ9wrk0UWkiLXxcLS0vfC0ifQ)

@carusocomputing Hah, don't give up! :D

I didn't give up, just had to go somewhere else and didn't want to lose my progress ;).

@carusocomputing Aha. So, more like #RageTemporarilyWalkAway.

05AB1E, 79 59 58 bytes
"\  "×¹<;£R.sð«¹3‹ið}.BvyD¹Éi¨}R„\/„/\‡«'|.øð.ø}ð'-‡¹2›i»}

Try it online!.
Explanation:
"\  "×                                                     # Push n copies of "\  ".
      ¹<;£                                                 # Push a[0:(n-1)/2]
          R.s                                              # Reverse, get substrings.
             ð«                                            # Append a space.
               ¹3‹ið}                                      # If n < 3, push a space.
                     .B                                    # Boxify.
                       vy                      }           # For each...
                         D¹Éi¨}R                           # Dupe, if n is odd, a[0:-1].
                                „\/„/\‡                    # Reverse the slashes.
                                       «'|.øð.ø            # Surround with | and a space.
                                                ð'-‡       # Replace spaces with "-".
                                                    ¹2›i } # If it's more than 2...
                                                        »  # Join stack by newlines.

Found the better solution, the key was to return the following arrays for each number as follows:
1=[" "]
2=["  "]
3=["\"]
4=["\ "]
5=["\"," \"]
6=["\"," \ "]
7=["\"," \","  \"]
8=["\"," \","  \ "]
Etc...

Python 2 , 173 bytes
i=input()
f=lambda b:'-|'+b[::-1].replace('/','\\')+-~(~i%2)*'-'+b+'|-'
b=(i*'/--')[:~-i/2]
for x in range(1,~-i/2):print f((len(b)-x)*'-'+b[:x]).replace('-',' ')
print f(b)

Mirror the value of b and add the central "-"
f=lambda b:'-|'+b[::-1].replace('/','\\')+-~(~i%2)*'-'+b+'|-'
Base pattern (right half of the bottom line)
b=(i*'/--')[:~-i/2]
Loop for non-bottom layers
for x in range(1,~-i/2):
Get the first x characters of the base pattern and complete with "-"
(len(b)-x)*'-'+b[:x]
Replace all - with spaces to print all the layers (except bottom)
print f().replace('-',' ')
Print bottom layer
print f(b)

You should include the raw version (without any comments) in your post

Befunge, 150 bytes
45&3+:00p4+2/:10p`-v
*\00g1-\`*2*+\1-!+v>1+:20p55+00g>::::00g1--!\:20g+00g-:0`\3%!
`1\*!%3\`0:-\g02:\<^_@#-g01<:,$_^#`\0:-1,g3+**4!-g01g02!:+*3*
 |\/-

Try it online!
I've also provided an ungolfed version of the code which better demonstrates the architecture used in the construction of the bridge.
        >4                                         5v
        v+3                                       <&<
        >:00                                     p4+v
        v-`p0                                   1:/2<
*+\1-!+v>1+:20p55+00g>::::00g1--!\:20g+00g-:0`\3%!*\00g1-\`*2
-\g02:\<^_@#-g01<:,$_^#`\0:-1,g6+7+**4!-g01g02!:>#+<v*!%3\`0:
        |\/->3#*                             *#`^#1\<

Try it online!
The towers handle the input and parameter initialisation. The deck is made up two loops calculating the parts of the bridge that need to be output for each x,y coordinate. And the foundation holds the character table for the those bridge parts, as well as some other completely unrelated code.
Detailed Explanation
We start by calculating the width and height of the output area that will need to be iterated in order to render the bridge.
w  = n + 3                (stored at 0,0)
h  = (w + 4)/2            (stored at 1,0)

Note that the y range is not zero-based. The initial value is 5 - (h<5) and is iterated up to h (the current value is stored at 2,0). The x value is iterated from w down to 0 and is stored on the stack.
The inner loop is just a series of boolean conditions determining whether a particular x,y coordinate matches any of the locations that require a non-space character. These calculations are based on two sliding offsets that follow the path of the suspension cables.
loff = y + x - w
roff = y - x

The various conditions are then determined as follows:
left_tower       = (x == w-1)
left_suspension  = (loff > 0) and (loff%3 == 0) and (x < w-1)
right_tower      = (x == 1)
right_suspension = (roff > 0) and (roff%3 == 0) and (x > 1)
bridge_deck      = (y == h)

To translate these conditions into the correct character offset, we just need to multiply each of them by an appropriate offset and sum the result. This calculation is performed as the conditions are evaluated. So it looks something like this:
char_offset =  left_tower
char_offset += left_suspension * 2
char_offset += right_tower
char_offset += right_suspension * 3
char_offset += !char_offset * bridge_deck * 4

Note that the bridge_deck value is merged in based on whether any of the other conditions have been met, since a suspension or tower character will take precedence over the deck.
The end result is an offset into the character table on the last line of the playfield. We simply output that character and repeat the loop.

Care to provide an explanation? with all those gets and puts, its hard to follow

You're the only one to post after I added the bounty, if nobody else beats you I'll award you the 100.

@carusocomputing I know you were hoping for better than this, but there's still plenty of time, and it should get more notice once it's closer to the top of the featured list.

This is a cool answer in and of itself, it already has more up votes than mine; better is definitely not the right word.

Batch, 241 bytes
@echo off
set t=set s=
%t%
for /l %%i in (1,1,%1)do call %t% %%s%%
%t% !%s%!
for /l %%i in (5,2,%1)do call:l 0
:l
%t%%s:\ = \%
%t%%s: /=/ %
%t%%s:!   =!\  %
%t%%s:   !=  /!%
%t%%s:\  !=\ /!%
if %1 gtr 0 %t%%s: =-%
echo %s:!=^|%

Note: Trailing space on line 5. Starts by building up a row of spaces, then adding cables as necessary, repeating to build towers to the desired height, ending by replacing any remaining spaces with road.

WinDbg, 312 bytes
r$t4=@$t0+4;.block{j3>@$t0'r$t5=1';r$t5=(@$t0-1)/2};f8<<16 L@$t4*@$t5 2d;f8<<16 L@$t4*(@$t5-1) 20;.for(r$t1=0;@$t1<@$t5;r$t1=@$t1+1){eb2000001+@$t4*@$t1 7c;e1fffffe+@$t4*(1+@$t1) 7c;j2<@$t0'.for(r$t2=@$t1;@$t2>=0;r$t2=@$t2-3){e2000002+@$t4*@$t1+@$t2 5c;e1fffffd+@$t4*(1+@$t1)-@$t2 2f}'};da/c@$t4 8<<16 L@$t4*@$t5

Input is done by setting the pseudo-register $t0.
I feel like there should be a way to combine the two for loops into one... maybe some other golfing opportunities too...
This one works by filling the entire area with road, then replacing all but the last row with space, and finally building the columns and cables.
r$t4 = @$t0+4;                                * Set width to input+4
.block                                        * Code block, needed for some reason...
{                                             * and .block+j is shorter than .if/.else
    j 3>@$t0                                  * If input is less than 3...
    '
        r$t5 = 1                              * ...set height to 1
    ';                                        * Implicit else...
        r$t5 = (@$t0-1)/2                     * ...set height to (input-1)/2
};
f 8<<16 L@$t4*@$t5 2d;                        * Fill area with -
f 8<<16 L@$t4*(@$t5-1) 20;                    * Fill all but last row with space
.for(r$t1=0; @$t1<@$t5; r$t1=@$t1+1)          * For each row
{
    eb 2000001+@$t4*@$t1 7c;                  * Build the left column with |
    e 1fffffe+@$t4*(1+@$t1) 7c;               * Build the right column (e is the same as last e* call, ie- eb)
    j 2<@$t0                                  * If input is more than 2...
    '
        .for(r$t2=@$t1; @$t2>=0; r$t2=@$t2-3) * ...Enumerate from counter back to 0
        {
            e 2000002+@$t4*@$t1+@$t2 5c;      * Build left cables with \
            e 1fffffd+@$t4*(1+@$t1)-@$t2 2f   * Build right cables with /
        }
    '
};
da /c@$t4 8<<16 L@$t4*@$t5                    * Print the string in lines of length width

Sample output of 1-15:
0:000> .for(r$t0=1;@$t0<10;r$t0=@$t0+1){.printf"%d\n",@$t0;r$t4=@$t0+4;.block{j3>@$t0'r$t5=1';r$t5=(@$t0-1)/2};f8<<16 L@$t4*@$t5 2d;f8<<16 L@$t4*(@$t5-1) 20;.for(r$t1=0;@$t1<@$t5;r$t1=@$t1+1){eb2000001+@$t4*@$t1 7c;e1fffffe+@$t4*(1+@$t1) 7c;j2<@$t0'.for(r$t2=@$t1;@$t2>=0;r$t2=@$t2-3){e2000002+@$t4*@$t1+@$t2 5c;e1fffffd+@$t4*(1+@$t1)-@$t2 2f}'};da/c@$t4 8<<16 L@$t4*@$t5}
1
Filled 0x5 bytes
Filled 0x0 bytes
02000000  "-|-|-"
2
Filled 0x6 bytes
Filled 0x0 bytes
02000000  "-|--|-"
3
Filled 0x7 bytes
Filled 0x0 bytes
02000000  "-|\-/|-"
4
Filled 0x8 bytes
Filled 0x0 bytes
02000000  "-|\--/|-"
5
Filled 0x12 bytes
Filled 0x9 bytes
02000000  " |\   /| "
02000009  "-|-\-/-|-"
6
Filled 0x14 bytes
Filled 0xa bytes
02000000  " |\    /| "
0200000a  "-|-\--/-|-"
7
Filled 0x21 bytes
Filled 0x16 bytes
02000000  " |\     /| "
0200000b  " | \   / | "
02000016  "-|--\-/--|-"
8
Filled 0x24 bytes
Filled 0x18 bytes
02000000  " |\      /| "
0200000c  " | \    / | "
02000018  "-|--\--/--|-"
9
Filled 0x34 bytes
Filled 0x27 bytes
02000000  " |\       /| "
0200000d  " | \     / | "
0200001a  " |  \   /  | "
02000027  "-|\--\-/--/|-"
10
Filled 0x38 bytes
Filled 0x2a bytes
02000000  " |\        /| "
0200000e  " | \      / | "
0200001c  " |  \    /  | "
0200002a  "-|\--\--/--/|-"
11
Filled 0x4b bytes
Filled 0x3c bytes
02000000  " |\         /| "
0200000f  " | \       / | "
0200001e  " |  \     /  | "
0200002d  " |\  \   /  /| "
0200003c  "-|-\--\-/--/-|-"
12
Filled 0x50 bytes
Filled 0x40 bytes
02000000  " |\          /| "
02000010  " | \        / | "
02000020  " |  \      /  | "
02000030  " |\  \    /  /| "
02000040  "-|-\--\--/--/-|-"
13
Filled 0x66 bytes
Filled 0x55 bytes
02000000  " |\           /| "
02000011  " | \         / | "
02000022  " |  \       /  | "
02000033  " |\  \     /  /| "
02000044  " | \  \   /  / | "
02000055  "-|--\--\-/--/--|-"
14
Filled 0x6c bytes
Filled 0x5a bytes
02000000  " |\            /| "
02000012  " | \          / | "
02000024  " |  \        /  | "
02000036  " |\  \      /  /| "
02000048  " | \  \    /  / | "
0200005a  "-|--\--\--/--/--|-"
15
Filled 0x85 bytes
Filled 0x72 bytes
02000000  " |\             /| "
02000013  " | \           / | "
02000026  " |  \         /  | "
02000039  " |\  \       /  /| "
0200004c  " | \  \     /  / | "
0200005f  " |  \  \   /  /  | "
02000072  "-|\--\--\-/--/--/|-"

Java 8, 423, 412 bytes
11 bytes saved thanks to Kritixi Lithos
golfed:
void f(int n){int i,j,k,t=n/2+n%2,u=t-2,q;char v=45;char[][]a=new char[t-1][n+4];for(char[]c:a)Arrays.fill(c,' ');a[u][0]=v;a[u][n+3]=v;for(q=0;q<t-1;q++){a[q][1]='|';a[q][n+2]='|';}for(i=t+1;i>1;i--){if((t-i)%3==0){k=u;for(j=i;j>1;j--)a[k--][j]='\\';}else a[u][i]=v;}for(i=n/2+2;i<n+2;i++){if((i-n/2-3)%3==0){k=u;for(j=i;j<n+2;j++)a[k--][j]='/';}else a[u][i]=v;}for(char[]w:a)System.out.println(new String(w));}

ungolfed:
void f(int n){
    int i,j,k,t=n/2+n%2,u=t-2;
    char v=45;
    char[][] a=new char[t-1][n+4];
    for (char[]c : a) Arrays.fill(c,' ');
    a[u][0]=v;
    a[u][n+3]=v;

    // left and right columns
    for (int q=0;q<t-1;q++){
        a[q][1]='|';
        a[q][n+2]='|';
    }
    // left part of base
    for (i=t+1;i>1;i--){
        if ((t-i)%3==0){
            k=u;
            for (j=i;j>1;j--)
                a[k--][j]='\\';
        }
        else a[u][i]=v;
    }
    // right part of base
    for (i=n/2+2;i<n+2;i++){
        if ((i-n/2-3)%3==0){
            k=u;
            for (j=i;j<n+2;j++)
                a[k--][j]='/';
        }
        else a[u][i]=v;
    }
    for (char[]w : a) System.out.println(new String(w));
}

You can golf this answer in many ways, first, you can have all your int declarations in one statement, something like int i,j,k,t=n/2+n%2,u=t-2,q=0 and instead of having char v="-"; you can use char v=45; and you can change the abc%xyz==0s to abc%xyz<1 (haven't tested it)

@KritixiLithos thx! edited the first 2 the last one didn't work


text:
The Essential™ (comment-free) Convenient Palindromic Quine Golf
A program is "conveniently palindromic" if

it is equal to the string derived when its reverse has all its parentheses (()), brackets ([]), and braces ({}) flipped. No other characters are special and require flipping. (<> are sometimes paired but often not so they are left out.)
copied from this challenge.

Write a conveniently palindromic program that prints its own source.
You must be able to prove that it is impossible to remove one or more byte from the program so that the resulting program, when executed in the same language:

prints the original source, or
prints the new modified source

Note that the resulting program won't necessarily be a convenient palindrome. It also means that you cannot use comments or equivalent structures.
Rules

Program must be longer than one character
Reading you own source code (from the file or any other resource) is forbidden.
Your program must be a proper quine.

Let us continue this discussion in chat.

Is it OK to submit a proper quine from which characters can be deleted to make an improper quine?

@ais523 Yes, you can.

Is it OK if the program exits via crashing after it's produced the appropriate quine output? Or does it have to exit the "normal way"?

@ais523 Yes, it can crash.

This would be a pretty hard challenge for most non-esoteric/non-golfing languages; moreover, it would be impossible to verify programs over, say, 40 bytes, which is 2^40 = 1e+12 subsets. I suppose you could remove some of the trivial subsets, but still....

Jelly, 17 bytes
ðṛṾṖṚŒḄø“øḄŒṚṖṾṛð

Try it online!
Verfication
A string of length 17 has only 217 = 131,072 subsequences, so this can be done by brute force.
$ # Generate all 131,072 subsequences of the source code.
$ jelly eun '“ðṛṾṖṚŒḄø“øḄŒṚṖṾṛð”ṾḊṖŒPY' > subsequences
$ wc -l subsequences
131072 subsequences
$ cat verify.py
import jelly

# Discard extraneous output to STDOUT (just a bunch of 0's and [0]'s).

jelly.print = lambda _, end: None

for line in open('subsequences').readlines():
        line = line.strip()
        try:
                output = jelly.stringify(jelly.jelly_eval(line, []))
        except:
                output = ''
        if output == line or output == 'ðṛṾṖṚŒḄø“øḄŒṚṖṾṛð':
                print(repr(line))

$ time python3 verify.py
'ðṛṾṖṚŒḄø“øḄŒṚṖṾṛð'

real    0m9.678s
user    0m9.653s
sys     0m0.028s

How it works
ðṛṾṖṚŒḄø“øḄŒṚṖṾṛð  Main link. No arguments. Implicit left argument: 0

       ø           Make the chain to the right niladic.
        “øḄŒṚṖṾṛð  Yield the string 'øḄŒṚṖṾṛð'.
ð                  Make the chain to the right and up to ø dyadic.
                   The main link is now a monadic 2,0-chain, so the dyadic chain
                   is called with the implicit left argument 0 and right argument
                   'øḄŒṚṖṾṛð'.
 ṛ                 Yield the right argument, i.e., 'øḄŒṚṖṾṛð'.
  Ṿ                Uneval; yield the string representation of the right argument,
                   i.e., '“øḄŒṚṖṾṛð”'.
   Ṗ               Pop; remove the last character, yielding '“øḄŒṚṖṾṛð'.
    Ṛ              Reverse, yielding 'ðṛṾṖṚŒḄø“'.
     ŒḄ            Bounce, yielding 'ðṛṾṖṚŒḄø“øḄŒṚṖṾṛð'.
                   (implicit) Print the last return value.

7, 12 bytes
The program is in binary. Here's an xxd dump:
00000000: 47b6 1818 b647 47b6 1818 b647            G....GG....G

This is rather more readable in the alternative octal notation (which isn't a valid answer to the question because changing the encoding changes the boundaries between bits):
2173303006133107217330300613310

Try it online!
Here's how the octal encoding of one half of the program corresponds to the packed encoding. (The other half is identical, except that it doesn't have a trailing 7 command because trailing 1 bits are treated like trailing whitespace, and ignored.) This is the form in which I actually worked on the problem, because trying to ensure that a program makes sense when viewed as three-bit chunks, but is palindromic when viewed as eight-bit chunks, is really unintuitive.
 2  1  7  3  3  0  3  0  0  6  1  3  3  1  0  7
...'''...'''...'''...'''...'''...'''...'''...'''
010001111011011000011000000110001011011001000111
........''''''''........''''''''........''''''''
   47      b6      18      18      b6      47

Like most golfed 7 quines, this program consists of two halves, each of which prints the other. Each half is originally passive on the stack, but an active copy is made and executed when the program runs out of commands to run, in reverse order from right to left. Here's how the active copy works (I'm using the escaped representation here because the unescaped representation contains some commands that don't have names, and thus are hard to talk about):
2          Copy the top of the stack
173303006  Push "330300" onto the stack
13         Pop the top of the stack
3          Output the copy of the top of the stack, and discard the original
10         Append nothing to the top of stack

In other words, each half of the program prints itself (because it's still at the top of the stack; the original wasn't removed when the copy was made), and then throws itself away. So this is effectively just the standard 7 quine 23723 written in a particularly verbose way, to make it palindromic at the byte level.
There's quite a lot of junk code here that doesn't do anything useful, and it could easily be deleted if deletions were at the command level. (As a result, I suspect this can be golfed substantially smaller, but I can't see how.) This might seem to violate the specification; however, the problem defines comment-freedom via deletion at the byte level (which makes about as little sense for 7 as requiring the program to be a palindrome at the byte level does), and doing that will typically throw off the boundaries between commands, making the program quite different. The rest of this post, therefore, talks about how I ensured that no deletions could lead to a proper quine.
Verification
I used the following Perl program to find all 7 quines, and all 7 programs printing the original program, that could be produced via deleting from the existing code (plus the original code itself, as it was easier to disregard that by hand than to write code to ignore it):
use 5.010;
use IPC::Run qw/run timeout/;
undef $/;
$| = 1;

my %seen = ();
my $original = <>;
sub check_program {
    my $unprocessed = shift;
    my $processed = shift;
    if ($unprocessed eq '') {
        my ($out, $err);
        $seen{$processed} and return;
        $seen{$processed}++;
        my $binary = unpack "B*", $processed;
        $binary =~ s/1+$//;
        $binary .= 1 while (length $binary) % 3;
        my $program = "";
        $program .= oct "0b$&" while $binary =~ s/^...//;
        print "$program          \r";
        my $ok = "t";
        eval {
            $ok = run [$^X, '7.pl'], '<', \$processed, '>', \$out, '2>', \$err, timeout(1);
            $ok = $ok ? "x" : "e";
        };
        if ($out eq $processed || $out eq $original) {
            $out eq $original and $ok .= "o";
            print "$program $ok\n";
        }
    } else {
        $unprocessed =~ s/^.//;
        check_program($unprocessed, $&.$processed);
        check_program($unprocessed, $processed);
    }
}

check_program($original, "");

The program produces quite a bit of output, because there are a number of 7 quines that can be produced like this. However, none are proper quines. They fall into three groups, listed here in octal to make it easier to verify that they aren't proper quines:
Programs which print themselves plus 21, but crash before it can be output
2161403021733030061
2161403055414030555
2161403055414030
2161403055443430555
2161403055443430
2161403055443507061
2161403055533030555
2161403055533030
21614030555
21614030

These programs each consist of the escaped representation of a single stack element that starts 721614030. (Where did the initial 7 come from? Each program starts with two empty elements on the stack, which is equivalent to two implicit 7s.) When it gets unescaped at runtime, its behaviour breaks down like this:
7216    Append "21" to the top of stack
14      Push two empty stack elements beneath the top of stack
0       Escape the top of stack, then append it to the element beneath
3       Output the top of stack, delete the second stack element
0       Crash due to insufficient stack

Now, when producing the first output in 7, you have to specify an output format. If the output is in need of escaping, that automatically escapes it and prepends a 7, and the first character output (in this case a 7) selects the format; most 7 quines rely on this. These programs, however, do the escaping manually, meaning that there's no implicitly prepended 7. Rather, the 7 at the start of the escaped representation (72161403021, etc.) ends up selecting the format, so it doesn't get escaped explicitly. In other words, the program prints itself plus an appended 21, then crashes.
The problem, of course, is that we're using packed, not octal, representation, so 21 is only six bits long, i.e. not a byte. As such, it can't (with programs of the lengths shown here) be output immediately, because more bits are needed to determine which byte to output. The 21 would be padded up to a full byte with 1 bits if the program exited normally, but it never gets a chance; it crashes before anything more can be output. When the crash occurs, the interpreter just exits immediately, and never gets the chance to print the incomplete byte.
Of course, this is an improper quine because all the output that's actually produced was produced via literally printing the corresponding characters of the original program.
Programs that print themself literally
Programs that crash:
2173303006133107061
217330300613310721614030555
217330300613310721614030

Programs that exit normally:
2173303006133030555
2173303006133030
2173303006133107061333
217330300613310
21733030061333
21733030554434300613310
2173303055443430061333
21733030555330300613310
2173303055533030061333

These all follow the same basic principle as the original program, but only have one stack element (either because the 7 that would normally separate stack elements got deleted, or because it's matched by a 6 later in the program, combining the element into one large element). The stack element prints itself literally first, for the same reason that the two elements in the original program each print the other, and then runs some random commands that don't produce output. Because the entire program is basically just a literal that prints itself, this doesn't count as a proper quine
The null quine
Yes, the null program is a quine in 7, and yes, you can produce it via deleting from the original program. This clearly isn't a proper quine, though.

RProgN, 3 Bytes.
1
1

Good luck out golfing this one.
This is a valid quine, as each 1 prints the opposite 1, which can be proven by the code
1
2

which prints
2
1

As for removing characters, 11 prints 11, although is not a valid quine, as it's a constant. The other options, 1_ and _1 (where _ is a newline) are also not valid, as they are only constants, and they are missing the white space.
Try it online!

Where are the newlines in the input? I believe 1\n1 prints 1\n1\n, thus isn't a quine; and although 1\n1\n is a quine, it isn't palindromic.

Actually, 1\n1 now does, and has for a while, printed 1\n1, due to uh, 'popular demand'.

Much like how 11 was not a valid Quine, neither is just a single 1, which the OP confirmed was valid in the comments

Befunge-98, 55 or 57 bytes
<#0289+*00#p>$$$>:#,_652**,@,**256_,#:>$$$>p#00*+9820#<

Try it online!
This solution is dependent on the behaviour of wraparound strings. Most Befunge-98 implementations will push a space onto the stack whenever a string wraps across the edge of the playfield, while the FBBI interpreter (which is what is used by TIO) will not. If you want to test this on other interpreters, you'll most likely need to include an additional $ (drop) command to get rid of that extra space:
<#0289+*00#p>$$$$>:#,_652**,@,**256_,#:>$$$$>p#00*+9820#<

In theory it should be possible to make a more portable solution that would work on all interpreters (possibly even Befunge-93), but that would require a good deal more code.
Proof of validity
While there are characters in the code that aren't actually executed, they are all used in the construction of the output, and removing any of those characters will result in output that neither matches the original source or the modified source. This is because the output string is built up in reverse, and it is thus imperative that the source be palindromic for the output to match. If you can remove a character and still have it work, you'll just have created a better solution.
Explanation
<                  Reverse the direction of execution, wrapping to the end of the line.
           0#<     Jump over the zero.
      *+982        Push 34 (a double quote character) onto the stack.
    00             Push two zeros - the coordinates of the first character in the source.
 >p#               Turn around and 'put' the double quote into the source at 0,0.
    00*+982        In reverse, this just pushes some numbers that will be ignored.
           0       This zero will serve as the string terminator though.
            #<     Jump over the left arrow so we can wrap around back to the start.

"#0289+*00...      At this point the first character has been updated to a quote, so
                     we're now going to switch to string mode and push the entire source
                     onto the stack in reverse order. When the end of the line is reached,
                     the string will wrap around to the start and terminate when it
                     encounters the quote again.

#0289+*00#p        Again we've got a sequence pushing values that we don't actually want.
           >$$$    This time we need to get rid of them, with a few drop operations.

>:#,_              A standard output routine, writing out the source from the stack.
     652**,        The last '<' character has to be output manually though.
           @       Then finally we can exit.


text:
McCarthy's LISP
McCarthy's 1959 LISP
In early 1959, John McCarthy wrote a groundbreaking paper defining just nine primitive functions that when put together still form the basis for all LISP-like languages today. The paper is available digitized here:
http://www-formal.stanford.edu/jmc/recursive.pdf
Your job is to fully implement a parser and interpreter for McCarthy's LISP exactly as described in the 1960 paper: That is, the functions QUOTE, ATOM, EQ, CAR, CDR, CONS, COND, LAMBDA, and LABEL should all be functional. The paper will take precedence over this challenge text when considering the correctness of answers, but I've tried to summarize the nine functions below. Note that the language will be in ALL CAPS and no error checking is necessary, all input should be presumed to be valid.
Types

There are only two types in McCarthy's LISP: An atom, and a linked list, which is recursively defined as a head, which may be a list or an atom, and a list that the head is attached to (tail). NIL has the special property of being both an atom and a list.
As per the paper, atom names will only consist of capital letters, numbers, and the space character, though strings of consecutive spaces should be considered as just one space and all leading and trailing space characters should be removed. Example equivalent atom names (replace underscore with space character): ___ATOM__1__ = ATOM_1. Example not equivalent atom names: A_TOM_1 != ATOM_1
Lists are denoted by parentheses, and an implied NIL is at the end of every list. Elements in a list are separated by commas and not whitespace like in most modern Lisps. So the list (ATOM 1, (ATOM 2)) would be {[ATOM 1] -> {[ATOM 2] -> NIL} -> NIL}.

QUOTE:

Takes one argument which may be either an atom (single element) or a linked list. Returns the argument exactly.
Test cases:
(QUOTE, ATOM 1) -> ATOM 1
(QUOTE, (ATOM 1, ATOM 2)) -> (ATOM 1, ATOM 2)

ATOM:

Takes one argument which may be either an atom (single element) or a linked list. Returns T (true) if the argument is an atom, or NIL (false) if the argument is not an atom.
Test cases:
(ATOM, (QUOTE, ATOM 1)) -> T
(ATOM, (QUOTE, (ATOM 1, ATOM 2))) -> NIL

EQ:

Takes two arguments which must be atoms (behavior is undefined if either of the arguments are not atoms). Returns T (true) if the two atoms are equivalent, or NIL (false) if they are not.
Test cases:
(EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 1)) -> T
(EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 2)) -> NIL

CAR:

Takes one argument which must be a list (behavior is undefined if it is not a list). Returns the first atom (head) of that list.
Test cases:
(CAR, (QUOTE, (ATOM 1, ATOM 2))) -> ATOM 1

CDR:

Takes one argument which must be a list (behavior is undefined if it is not a list). Returns every atom but the first atom of the list, i.e. the tail. Note that every list ends in an implied NIL, so running CDR on a list that appears to just have one element will return NIL.
Test cases:
(CDR, (QUOTE, (ATOM 1, ATOM 2))) -> (ATOM 2)
(CDR, (QUOTE, (ATOM 1))) -> NIL

CONS:

Takes two arguments. The first may be an atom or a list but the second must be a list or NIL. Prepends the first argument to the second argument and returns the newly-created list.
Test cases:
(CONS, (QUOTE, ATOM 1), (QUOTE, NIL)) -> (ATOM 1)
(CONS, (QUOTE, ATOM 1), (CONS, (QUOTE, ATOM 2), (QUOTE, NIL))) -> (ATOM 1, ATOM 2)

COND:

This is LISP's "if-else" statement of sorts. Takes a variable-length amount of arguments, each of which must be a list of length exactly 2. For each argument list in order, evaluate the first term and if it is true (T), return the associated second term and exit the function. If the first term is not true, move on to the next argument and test its condition, and so on until the first true condition is reached. At least one of the argument conditions can be assumed to be true -- if they are all false, this is undefined behavior. See page 4 for a good example of the behavior of this function.
Test cases:
(COND, ((ATOM, (QUOTE, ATOM 1)), (QUOTE, 1)), ((ATOM, (QUOTE, (ATOM 1, ATOM 2))), (QUOTE, 2))) -> 1
(COND, ((ATOM, (QUOTE, (ATOM 1, ATOM 2))), (QUOTE, 2)), ((ATOM, (QUOTE, ATOM 1)), (QUOTE, 1))) -> 1

LAMBDA:

Defines an anonymous function. Takes two arguments, the first being a list of atoms which represent the arguments to the function and the second being any S-expression (the function body), which would typically use the arguments.
Test cases:
Defining and using an anonymous "isNull" function:
((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> T
((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, ATOM 1)) -> NIL

LABEL:

Gives a name to an anonymous LAMBDA function, which also allows that function to be called recursively in the body of the LAMBDA. Takes two arguments, the first being a label and the second being the LAMBDA function to which the label should be bound. Returns the name supplied. The scope of all LABEL names is global, and redefining a LABEL is undefined behavior.
Fun fact, LABEL is not actually necessary to create recursive functions as we now know LAMBDA can be used with a 'Y-Combinator' to accomplish this task, but McCarthy wasn't aware of this method when writing the original paper. It makes programs much easier to write anyways.
Test cases:
(LABEL, SUBST, (LAMBDA, (X, Y, Z), (COND, ((ATOM, Z), (COND, ((EQ, Y, Z), X), ((QUOTE, T), Z))), ((QUOTE, T), (CONS, (SUBST, X, Y, (CAR, Z)), (SUBST, X, Y, (CDR, Z))))))) -> SUBST
(after running the above) (SUBST, (QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C))) -> (A, A, C)

To help visualize the SUBST function above, it could be represented as this Python-like pseudocode:
def substitute(x, y, z): # substitute all instances of y (an atom) with x (any sexp) in z
    if isAtom(z):
        if y == z:
            return x
        elif True:
            return z
    elif True:
        return substitute(x,y,z[0]) + substitute(x,y,z[1:])

FINAL TEST CASE:
If I have transcribed it correctly, your interpreter should be able to interpret EVAL with this code:
(LABEL, CAAR, (LAMBDA, (X), (CAR, (CAR, X))))
(LABEL, CDDR, (LAMBDA, (X), (CDR, (CDR, X))))
(LABEL, CADR, (LAMBDA, (X), (CAR, (CDR, X))))
(LABEL, CDAR, (LAMBDA, (X), (CDR, (CAR, X))))
(LABEL, CADAR, (LAMBDA, (X), (CAR, (CDR, (CAR, X)))))
(LABEL, CADDR, (LAMBDA, (X), (CAR, (CDR, (CDR, X)))))
(LABEL, CADDAR, (LAMBDA, (X), (CAR, (CDR, (CDR, (CAR, X))))))

(LABEL, ASSOC, (LAMBDA, (X, Y), (COND, ((EQ, (CAAR, Y), X), (CADAR, Y)), ((QUOTE, T), (ASSOC, X, (CDR, Y))))))

(LABEL, AND, (LAMBDA, (X, Y), (COND, (X, (COND, (Y, (QUOTE, T)), ((QUOTE, T), (QUOTE, NIL)))), ((QUOTE, T), (QUOTE, NIL)))))
(LABEL, NOT, (LAMBDA, (X), (COND, (X, (QUOTE, NIL)), ((QUOTE, T), (QUOTE, T)))))

(LABEL, NULL, (LAMBDA, (X), (AND, (ATOM, X), (EQ, X, (QUOTE, NIL)))))

(LABEL, APPEND, (LAMBDA, (X, Y), (COND, ((NULL, X), Y), ((QUOTE, T), (CONS, (CAR, X), (APPEND, (CDR, X), Y))))))

(LABEL, LIST, (LAMBDA, (X, Y), (CONS, X, (CONS, Y, (QUOTE, NIL)))))

(LABEL, PAIR, (LAMBDA, (X, Y), (COND, ((AND, (NULL, X), (NULL, Y)), (QUOTE, NIL)), ((AND, (NOT, (ATOM, X)), (NOT, (ATOM, Y))), (CONS, (LIST, (CAR, X), (CAR, Y)), (PAIR, (CDR, X), (CDR, Y)))))))

(LABEL, EVAL, (LAMBDA, (E, A), (COND, ((ATOM, E), (ASSOC, E, A)), ((ATOM, (CAR, E)), (COND, ((EQ, (CAR, E), (QUOTE, QUOTE)), (CADR, E)), ((EQ, (CAR, E), (QUOTE, ATOM)), (ATOM, (EVAL, ((CADR, E), A)))), ((EQ, (CAR, E), (QUOTE, EQ)), (EQ, (EVAL, (CADR, E, A)), (EVAL, (CADDR, E, A)))), ((EQ, (CAR, E), (QUOTE, COND)), (EVCON, (CDR, E), A)), ((EQ, (CAR, E), (QUOTE, CAR)), (CAR, (EVAL, (CADR, E), A))), ((EQ, (CAR, E), (QUOTE, CDR)), (CDR, (EVAL, (CADR, E), A))), ((EQ, (CAR, E), (QUOTE, CONS)), (CONS, (EVAL, (CADR, E), A), (EVAL, (CADDR, E), A))), ((QUOTE, T), (EVAL, (CONS, (ASSOC, (CAR, E), A), (EVLIS, (CDR, E), A)), A)))), ((EQ, (CAAR, E), (QUOTE, LABEL)), (EVAL, (CONS, (CADDAR, E), (CDR, E)), (CONS, (CONS, (CADAR, E), (CONS, (CAR, E), (CONS, A, (QUOTE, NIL))))))), ((EQ, (CAAR, E), (QUOTE, LAMBDA)), (EVAL, (CADDAR, E), (APPEND, (PAIR, (CADAR, E), (EVLIS, (CDR, E), A)), A))))))

(LABEL, EVCON, (LAMBDA, (C, A), (COND, ((EVAL, (CAAR, C), A), (EVAL, (CADAR, C), A)), ((QUOTE, T), (EVCON, (CDR, C), A)))))

(LABEL, EVLIS, (LAMBDA, (M, A), (COND, ((NULL, M), (QUOTE, NIL)), ((QUOTE, T), (CONS, (EVAL, (CAR, M), A), (EVLIS, (CDR, M), A))))))

After running that behemoth, this line should return (A, B, C):
(EVAL, (QUOTE, (CONS, X, (QUOTE, (B, C)))), (QUOTE, ((X, A), (Y, B))))

However, to quote John McCarthy himself on page 16, it seems like he was running out of characters on his computer:

If more characters were available on the computer, it could be improved considerably ...

Therefore, this challenge is tagged code-golf and the shortest answer in characters will be the winner. Standard loopholes apply. Good luck!
Note on String Evals: I understand that some think it may be possible to win this challenge by using a Lisp and modifying the syntax to fit the host language and then using a string (eval). I'm not particularly convinced that this approach will necessarily win especially with the identifier naming rules, and even if it did I think banning string evals in all languages would be a subjective and slippery slope. But I don't want to punish people for doing this challenge the 'right' way, so I may allow two winners for this challenge, one in a Lisp-like language and one in a non-Lispy language, if this becomes a problem.

You have a Lambda example defining an "IsNull" function, but it looks like the Nil return Nil, when it seems to me like it should return T?

@nmjcman101 Sorry, forgot to add quotes to that lambda, but fixed now. It looks correct to me -- if the input ATOM 1 is NIL, then EQ will return T so the lambda will return T.

You have ((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> NIL Where the (QUOTE NIL) at the end is the input, so this should return T?

@nmjcman101 Yes, the (QUOTE NIL) at the end is the argument being applied the anonymous function. So because nil is null, EQ and thus the whole expression will return T.

Right, but you've written -> NIL

@nmjcman101 Oh, haha, my mistake, you're 100% right. Fixed now.

In your description for CONS you say "Appends the first argument to the second argument and returns the newly-created list," but the test cases show the second argument  being appended to the first. Which is correct?

@Jordan, you are right, I fixed the challenge text to say "prepends" and added another test case to be more clear. It acts similarly to the cons operator in Common Lisp, and remember that in the case of inconsistencies in my summary the original paper is the first authority. Would love for you to take this challenge up!

I'm basing my implementation on kjetilvalle's lisp tutorial, and the syntax is slightly different. Lowercase is used and no commas are present. Could I simply run a lowercase transformation and remove commas from the input string so that it conforms more or less to the above interpreter's design? I'm pretty new to Lisp, but wanted to explore this challenge in my own language. So far I have the parser implemented. (My language looks like Lisp, but is implemented in Node.js)

@Andrakis As long as it is a correct interpreter of the LISP in the original paper and passes the test cases, I have no control over how you are supposed to get there. kjetilvalle's tutorial is good, but he does note that there are some specific differences between his version and McCarthy's original version, so you'll need to make sure you bridge the gap between those differences. Thanks for working on this!

In your description for CONS you say, "the second [argument] must be a list or NIL," but in the first test case, (CONS, (QUOTE, ATOM 1), (QUOTE, ATOM 2)), doesn't the second argument evaluate to ATOM 2, which isn't a list? The same for the nested CONS in the third test case.

@Jordan You're right, I fixed the test cases.

You're missing a comma after LAMBDA in (LABEL, NOT, (LAMBDA (X), (COND, (X, (QUOTE, NIL)), ((QUOTE, T), (QUOTE, T))))).

@orlp Thank you, fixed. Wish I had caught all these errors when it was in the sandbox, haha.

Shouldn't (SUBST, ((QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C)))) in the example be (SUBST, (QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C)))? SUBST takes 3 arguments, but in the example it's given a single list of 3 elements as argument.

Also, in the SUBST definition, you have written (CAR Z) instead of (CAR, Z). I'm sorry, but have you tested the examples at all?

You have QUOTE NIL in the final test case, another missing comma.

@orlp 1. You are right, fixed. 2. Looks like Mr. McCarthy also had some trouble writing in his own language, because that same typo was in the original paper as well (page 16). Fixed though. 3. Fixed. As for whether I have tested the examples, the answer is no, because I am not aware of any implementation that follows the original syntax yet. I did put this question in the Sandbox for a few days before putting it here and it attracted a few comments there which I fixed, but I guess I didn't expect this many errors to remain and I apologize for that but it should be fixed now.

@Harry SUBST is still broken. (COND, (EQ, Y, Z), X) this is not how COND operates.

@orlp You are right, that was also in the original paper but I believe I have fixed it now to match the pseudocode I wrote for that function.

@Harry I updated SUBST with a fixed version.

APL (Dyalog Unicode), 523...451 447 bytes
Saved 12 bytes thanks to @Bubbler!
Saved 1 byte thanks to @Adám (and 7 more thanks to this comment on another answer)
s←⎕SE.Dyalog.Utils.repObj
z←'NIL'
p←{')'=⊃⍵:(⊂z)(1↓⍵)⋄v r←{'('=⊃⍵:p⍵⋄⍵(↑,Ö⊂↓)⍨⊃⍸⍵∊',)'}1↓⍵⋄n r←∇r⋄(n,⍨⊂v)r}
e←{1=≡⍵:((⊃⍺)⍳⊂⍵)⊃(1⊃⍺),⊂⍵⋄⍺(⍎⍺e⊃⍵)1↓⍵}
b←⊃∘z'T'
CAR←⊃x←e∘⊃
CDR←1↓x
QUOTE←⊃⊢
CONS←{(⊂⍺x⍵),⊆⍺e 1⊃⍵}
EQ←{b≡/⍺∘e¨¯1↓⍵}
ATOM←b 1=∘≡x
COND←{z≢⍺x⊃⍵:⍺e 1⊃⊃⍵⋄⍺∇1↓⍵}
LAMBDA←{⍕'{((('(s⊃⍵)'),⊃⍺)((⍺∘e¨⍵),1⊃⍺))e'(s 1⊃⍵)'}'}
LABEL←{u←⍎⍕'#.'(⊃⍵)'←',⍺e 1⊃⍵⋄⊃⍵}

To execute a line of LISP:
{{1=≢⍵:⍵⋄1=≡⍵:'_'⎕R' '⊢⍵⋄⍕1⌽')(',∇¨¯1↓⍵}⍬⍬e⊃p'(?<=\(|,) *(?=\d)| +' ' *([(),]) *'⎕R'_' '\1'⊢⍵}

Try it online!
Unfortunately, this doesn't work in TIO dzaima (and Adám) got ⎕SE.Dyalog.Utils.repObj working! Requires ⎕IO←0 now.
Formatting the input
First ⎕R is used to format the input. It accepts a bunch of regex on the left and the strings to replace them with on the right. In this case, we're replacing areas before atom names starting with digits ((?<=\(|,) *(?=\d)) or multiple spaces ( +) with a single underscore because in APL, identifiers cannot contain spaces or start with digits.
At the same time,  *([(),]) * captures parentheses or commas along with spaces around them, but only keeps the parentheses and commas, dropping leading or trailing spaces by doing so. Thus, ( QUOTE, (1, ATOM 2)) would become (QUOTE,(_1,ATOM_2)).
Creating an AST
p creates an AST from this formatted string. Every atom is represented by a string, and every s-expression is simply an array of atoms or other s-expressions, with the string NIL at the end. Thus, (QUOTE,(ATOM_1,ATOM_2)) would become ('QUOTE' ('ATOM_1' 'ATOM_2' 'NIL') 'NIL').
Executing the AST
e takes such an AST as its right argument and evaluates it. The left argument is a context that gives the variables in scope. It's an array whose first elements is a list of strings denoting the names of atoms, while the second element is a list of the same length with those variables' values. For example, given a lisp expression ((LAMBDA, (X, Y), (CONS, Y, X)), (QUOTE, (ATOM 1)), (QUOTE, ATOM 2)), the context would look like this (the NILs are an unfortunate side effect of how the ASTs are structured, but they're harmless):
       'X'     |    'Y'   | 'NIL'
'ATOM_1' 'NIL' | 'ATOM_2' | 'NIL'

If the right argument to e is a single string (an atom), it looks up the atom in the context and gets back the corresponding value. If the atom is not found in the context, it just gives back the same string. So in the example above, if ⍵ (the right argument) were X, we would get back ATOM_1, but if it were CAR, we would get back CAR again.
Otherwise, it's a function call, so it calls e on the first element of that tree with the same context on the left. The first element of the AST is either a label name or one of the nine "builtin" functions, or a lambda expression. If it's the former, we'll just get back the name of the function again. In that case, we can execute the string with ⍎ (APL's equivalent of eval) to get another dyadic function. We give it the same context on the left and apply it to the rest of ⍵, the right argument.
Otherwise, if it's a lambda expression, applying the function LAMBDA (the one I've defined) returns a string containing a function, so again, we can execute it and apply it to the rest of ⍵.
The initial left argument is ⍬⍬ (⍬ is an empty array), because we don't have any variables defined yet.
Printing the result
{1=≢⍵:⍵⋄1=≡⍵:'_'⎕R' '⊢⍵⋄⍕'('(∇¨¯1↓⍵)')'} is a recursive function that turns arrays into strings. 1=≢⍵ checks if the argument is a string (with depth 1). If so, it turns underscores back into spaces with '_'⎕R' '. Otherwise, it drops the last element (always NIL) using ¯1↓⍵, then calls itself on each element using ∇¨. That is put into an array with parentheses, and ⍕ is used to turn that array into a string (with extra spaces).
LAMBDA
This function returns a string representing another function. For example, (LAMBDA, (X, Y), (CONS, X, Y)) becomes
{((('X' 'Y' 'NIL'),⊃⍺)((⍺∘e¨⍵),1⊃⍺))e'CONS' 'X' 'Y' 'NIL'}

While the definition of LAMBDA itself may look messy, there is nothing complicated about it. On the right is simply the body given to the lambda; only the context has changed. Like the Python answer, I used dynamic scoping, so the new context adds to the context given at the call site, not where the lambda is defined. The first element is just the names lambda's parameters prepended to the the old context's names. The second is the result of evaluating all the arguments (with the same context), prepended to the old context's values. repObj (assigned to s because it is used multiple times) finds the string representation of the parameters and lambda body.
LABEL
This is why we had to add underscores before. LABEL constructs a string that looks like #.name ← lambda, given the arguments name lambda 'NIL', executes it, adding a function called name to the root namespace #, so it is global. Like LAMBDA, it ignores the context given to it, because of dynamic scoping.

Shorten the regexes and remove unnecessary parens to get under 500 bytes.

@Bubbler Thanks! I'll need some time to analyze it and incorporate the changes into my answer, since I just changed it.

This is very good work and a great writeup, thanks for sharing!

Python 3, 770 bytes
This is a REPL on stdin/stdout. Expects every line to be a full statement or empty. eval is used to shorten the implementation, but is otherwise not necessary for logic.
import re,sys;S=re.sub
P=lambda l:eval(S("([A-Z0-9][A-Z0-9 ]*)",r"' '.join('\1'.strip().split())",S("NIL","()",S("\)",",)",l))))
d={"QUOTE":'(v,L[1])[1]',"EQ":'[(),"T"][E(L[1],v)==E(L[2],v)]',
"CDR":'E(L[1],v)[1:]',"CONS":'(E(L[1],v),)+E(L[2],v)',"CAR":'E(L[1],v)[0]',
"LAMBDA":'("#",)+L[1:]',"LABEL":'[v.update({L[1]:E(L[2],v)}),L[1]][1]'}
def E(L,v):
 if L*0=="":return v[L]
 elif L[0]in d:return eval(d[L[0]])
 elif L[0]=="COND":return next(E(l[1],v)for l in L[1:]if E(l[0],v)=="T")
 elif L[0]=="ATOM":o=E(L[1],v);return[(),"T"][o*0in["",o]]
 else:l=E(L[0],v);n=v.copy();n.update({a:E(p,v)for a,p in zip(l[1],L[1:])});return E(l[2],n)
R=lambda o:o==()and"NIL"or 0*o==()and"(%s)"%", ".join(R(e)for e in o)or o
g={}
for l in sys.stdin:
 if l.strip():print(R(E(P(l),g)))

Thank you for completing this! I really appreciate the effort and it looks good. However if I run it for me it doesn't pass these test cases: 1. (CONS, (QUOTE, ATOM 1), (QUOTE, NIL)) -> (ATOM 1) 2. (CONS, (QUOTE, ATOM 1), (CONS, (QUOTE, ATOM 2), (QUOTE, NIL))) -> (ATOM 1, ATOM 2) 3. (SUBST, (QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C))) -> (A, A, C) (I haven't tried it on the EVAL test case yet). I understand that there have been errors in the tests, but I think these tests are correct and it would need to pass these to get the bounty

@Harry The first two test cases work after fixing a small bug that I introduced in the final touches.  The eval works flawlessly. But the SUBST example is still broken (to my knowledge) as a testcase. One of the CONDs reaches the end before finding a T.

Thank you for fixing that! This is very impressive! It works for me on all testcases now, including EVAL (so pleasantly surprised I got that one right on the first try!) I'm going to award you the bounty and the accepted answer now!

Also I love the R(E(P(l) setup ;-)

@Harry I kid you not that was an accident! R = repr, E = eval, P = parse, l = line.

Just wanted to let you know, I wrote an article mentioning your implementation here!

In Python 3.9 you can create the new environment with v|{a:E(p,v)for a,p in zip(l[1],L[1:])}, saving 21 bytes. (In 3.5 through 3.8 you can write {**v,**{a:E(p,v)for a,p in zip(l[1],L[1:])}} which saves 15 bytes instead.)

In Python 3.8+ you can save another 35 bytes with E=lambda L,v:v[L]if L*0==""else eval(d[L[0]])if L[0]in d else next(E(l[1],v)for l in L[1:]if E(l[0],v)=="T")if L[0]=="COND"else[(),"T"][(o:=E(L[1],v))*0in["",o]]if L[0]=="ATOM"else E((l:=E(L[0],v))[2],v|{a:E(p,v)for a,p in zip(l[1],L[1:])}) or the 3.8 equivalent of the dict update. In 3.5 through 3.7 you can save 18 bytes instead by using (lambda v:...v...v...)(e) instead of ...(v:=e)...v....

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


text:
Un-de-duplicating strings
Introduction
Let's observe the following string:
AABBCCDDEFFGG

You can see that every letter has been duplicated, except for the letter E. That means that the letter E has been de-duplicated. So, the only thing we need to do here is to reverse that process, which gives us the following un-de-duplicated string:
AABBCCDDEEFFGG

Let's take a harder example:
AAAABBBCCCCDD

You can see that there is an uneven number of consecutive B's, so that means that one of the BB was de-duplicated from the original string. We only need to un-de-duplicate this letter, which gives us:
AAAABBBBCCCCDD

The challenge
Given a non-empty de-duplicated string, consisting of only alphabetic characters (either only uppercase or only lowercase), return the un-de-duplicated string. You can assume that there will always be at least one de-duplicated character in the string.

Test cases
AAABBBCCCCDDDD    -->    AAAABBBBCCCCDDDD
HEY               -->    HHEEYY
AAAAAAA           -->    AAAAAAAA
N                 -->    NN
OOQQO             -->    OOQQOO
ABBB              -->    AABBBB
ABBA              -->    AABBAA

This is code-golf, so the shortest valid submission in bytes wins!

@mbomb007 Yes, that would result into AABBBB.

@mbomb007 Ah, I was not aware of that. Thanks!

I'm not sure I understand the challenge. Why does ABBB map to AABBBB, not AABBBBBB?

@Dennis If you seperate each group of characters into groups of 2, you would get the following: A BB B. The characters that aren't paired (and therefore not duplicated) need to be duplicated, resulting in AA BB BB, which is the un-de-duplicated string.

So: Ensure that every run of characters has an even number of elements by adding at most one element to the run?

@MadPhysicist Yes, that is correct

MATL, 7 bytes
Y'to+Y"

Try it online! Or verify all test cases.
Let's take 'ABBA' as example input.
Y'   % Implicit input. Run-length decoding
     % STACK: 'ABA', [1 2 1]
t    % Duplicate top of the stack
     % STACK: 'ABA', [1 2 1], [1 2 1]
o    % Modulo 2
     % STACK: 'ABA', [1 2 1], [1 0 1]
+    % Add, element-wise
     % STACK: 'ABA', [2 2 2]
Y"   % Run-length encoding. Implicit display
     % STACK: 'AABBAA'

Retina, 11 bytes
(.)\1?
$1$1

Try it online - contains all test cases

I expected Retina to win.

@Adám Yeah, it's pretty short, but that MATL answer is great. All the golfing languages ended up with shorter solutions.

Haskell, 36 bytes
u(a:b:c)=a:a:u([b|a/=b]++c)
u x=x++x

Usage example: u "OOQQO" -> "OOQQOO".
If the string has at least 2 elements, take two copies of the first and append a recursive call with

the second element an the rest if the first two elements differ or
just the rest

If there are less than two elements (one or zero), take two copies of the list.

Perl, 16 bytes
15 bytes of code + -p flag.
s/(.)\1?/$1$1/g

To run it:
perl -pe 's/(.)\1?/$1$1/g' <<< 'HEY'

Brachylog, 17 bytes
@b:{~b#=.l#e,|}ac

Try it online!
Explanation
Example input: "ABBB"

@b                  Blocks: Split into ["A", "BBB"]
  :{          }a    Apply the predicate below to each element of the list: ["AA", "BBBB"]
                c   Concatenate: "AABBBB"

    ~b#=.             Output is the input with an additional element at the beginning, and
                        all elements of the output are the same (e.g. append a leading "B")
        .l#e,         The length of the Output is an even number
             |        Or: Input = Output (i.e. do nothing)

JavaScript (ES6), 37 30 bytes
Saved 7 bytes by using the much more efficient '$1$1' like [other] [answers] did
s=>s.replace(/(.)\1?/g,'$1$1')

Test cases

let f =

s=>s.replace(/(.)\1?/g,'$1$1')

console.log(f("AAABBBCCCCDDDD"));   //  -->  AAAABBBBCCCCDDDD
console.log(f("HEY"));              //  -->  HHEEYY
console.log(f("AAAAAAA"));          //  -->  AAAAAAAA
console.log(f("N"));                //  -->  NN
console.log(f("OOQQO"));            //  -->  OOQQOO
console.log(f("ABBB"));             //  -->  AABBBB
console.log(f("ABBA"));             //  -->  AABBAA

Ruby, 21 bytes
20 bytes plus the -p flag.
gsub(/(.)\1?/){$1*2}

Mathematica, 41 bytes
s=StringReplace;s[s[#,a_~~a_->a],b_->b~~b]&

Unnamed function that inputs a string and outputs a string. Completely deduplicate then completely undeduplicate. Not real short, but I couldn't do better for now.

Befunge 98, 24 bytes
#@~#;:::#@,~-:!j;$,;-\,;

Try it Online!
$ can be easily replaced with -, and the 2nd @ with ;.
I think this can be golfed further due to the - at the beginning of both -, (or $, above) and -\,.
How?
Stack notation:  bottom [A, B, C, D] top

#@~     Pushes the first character onto the stack (C henceforth) and ends if EOF
#;      No-op to be used later
:::     Now stack is [C, C, C, C]

#@,~    Prints C, and if EOF is next (odd consecutive Cs), prints again and ends
        Lets call the next character D

-       Now stack is [C, C, C-D]
:!j;    If C == D, go to "$," Else, go to "-\,"

===(C == D)===

$,      C == D (i.e. a pair of Cs) so we discard top and print C (Stack is now [C])
;-\,;   Skipped, IP wraps, and loop starts again

===(C != D)===

-       Stack is [C, C-(C-D)]  By expanding: [C, C - C + D] or just [C, D]
\,      Prints C (Stack is now [D])

;#@~#;  This is skipped, because we already read the first character of a set of Ds,
        and this algorithm works by checking the odd character in a set of
        consecutive similar characters. We already read D, so we don't
        need to read another character.

Java 7, 58 bytes
String c(String s){return s.replaceAll("(.)\\1?","$1$1");}

Ungolfed:
String c(String s){
  return s.replaceAll("(.)\\1?", "$1$1");
}

Test code:
Try it here.
class M{
  static String c(String s){return s.replaceAll("(.)\\1?","$1$1");}

  public static void main(String[] a){
    System.out.println(c("AABBCCDDEFFGG"));
    System.out.println(c("AAAABBBCCCCDD"));
    System.out.println(c("AAABBBCCCCDDDD"));
    System.out.println(c("HEY"));
    System.out.println(c("AAAAAAA"));
    System.out.println(c("N"));
    System.out.println(c("OOQQO"));
    System.out.println(c("ABBB"));
    System.out.println(c("ABBA"));
  }
}

Output:
AABBCCDDEEFFGG
AAAABBBBCCCCDD
AAAABBBBCCCCDDDD
HHEEYY
AAAAAAAA
NN
OOQQOO
AABBBB
AABBAA

Brain-Flak 69 Bytes
Includes +3 for -c
{((({}<>))<>[({})]<(())>){((<{}{}>))}{}{(<{}{}>)}{}}<>{({}<>)<>}<>

Try it Online!
Explanation:
Part 1:
{((({}<>))<>[({})]<(())>){((<{}{}>))}{}{(<{}{}>)}{}}<>

{                                                  }   # loop through all letters
 (   {}     [ {} ]<(())>){((<{}{}>))}{}                # equals from the wiki
                                                       # but first:
  ((  <>))<>                                           # push the top letter on the other
                                                       # stack twice
             (  )                                      # push the second letter back on
                                       {        }      # if they were equal:
                                        (<    >)       # push a 0 to exit this loop
                                          {}{}         # after popping the 1 from the
                                                       # comparison and the next letter
                                                       # (the duplicate)
                                                 {}    # pop the extra 0
                                                    <> # switch stacks

Part 2 (at this point, everything is duplicated in reverse order):
{({}<>)<>}<>

{        }   # for every letter:
 ({}<>)      # move the top letter to the other stack
       <>    # and switch back
          <> # Finally switch stacks and implicitly print

brainfuck, 22 bytes
,
[
  [>->+<<-]
  >[>..<<]
  >,
]

Try it online.
Prints the current character twice, unless it's equal to a character that was just printed twice.

PHP, 65 bytes, no regex
while(""<$c=($s=$argv[1])[$i])if($c!=$s[++$i]||!$k=!$k)echo$c.$c;

takes input from command line argument. Run with -r.
regex?
In PHP, the regex used by most answers duplicates every character. would be 44 bytes:
<?=preg_replace("#(.)\1?#","$1$1",$argv[1]);

Pyth, 15 bytes
Vrz8p*+hN%hN2eN

Verify all test cases here.
Thanks to Luis Mendo for the methodology.
Explanation
Vrz8p*+hN%hN2eN    z autoinitializes to the input
 rz8               run-length encode the input, returned as list of tuples (A -> [[1,"A"]])
V                  for every element N in this list
      +hN          add the head element of N (the number in the tuple)
         %hN2      to the head element of N mod 2
     *       eN    repeat the tail element of N that many times (the letter in the tuple)
    p              print repeated character without trailing newline

As is often the case, I feel like this could be shorter. I think there should be a better way to extract elements from the list than what I am using here.

PowerShell, 28 bytes
$args-replace'(.)\1?','$1$1'

Try it online! (includes all test cases)
Port of the Retina answer. The only points of note are we've got $args instead of the usual $args[0] (since the -replace will iterate over each item in the input array, we can golf off the index), and the '$1$1' needs to be single quotes so they're replaced with the regex variables rather than being treated as PowerShell variables (which would happen if they were double-quote).

 C, 67 bytes
i;f(char*s,char*d){i=*s++;*d++=i;*d++=i;*s?f(i-*s?s:++s,d):(*d=0);}

Call with:
int main()
{
    char *in="AAABBBCCCCDDDD";
    char out[128];
    f(in,out);
    puts(out);
}

Jelly, 9 bytes
Œgs€2ṁ€€2

Try it online!

Racket 261 bytes
(let((l(string->list s))(r reverse)(c cons)(e even?)(t rest)(i first))(let p((l(t l))(ol(c(i l)'())))
(cond[(empty? l)(list->string(if(e(length ol))(r ol)(r(c(i ol)ol))))][(or(equal?(i ol)(i l))(e(length ol)))
(p(t l)(c(i l)ol))][(p(t l)(c(i l)(c(i ol)ol)))])))

Ungolfed:
(define (f s)
  (let ((l (string->list s)))
    (let loop ((l (rest l))
               (ol (cons (first l) '())))
      (cond
        [(empty? l)
         (list->string(if (even? (length ol))
                          (reverse ol)
                          (reverse (cons (first ol) ol))))]
        [(or (equal? (first ol) (first l))
             (even? (length ol)))
         (loop (rest l) (cons (first l) ol))]
        [else
         (loop (rest l) (cons (first l) (cons (first ol) ol)))] ))))

Testing:
(f "ABBBCDDEFFGGG")

Output:
"AABBBBCCDDEEFFGGGG"

V 10 bytes
Í¨.©±½/±±

TryItOnline
Just a find and replace regex like all of the rest in the thread.  The only difference is that I can replace anything that would require a \ in front of it with the character with the same ascii value, but the high bit set. (So (, 00101000 becomes ¨, 10101000)

Perl 6, 17 bytes
s:g/(.)$0?/$0$0/

with -p command-line switch
Example:
$ perl6 -pe 's:g/(.)$0?/$0$0/' <<< 'AAABBBCCCCDDDD
> HEY
> AAAAAAA
> N
> OOQQO
> ABBB
> ABBA'
AAAABBBBCCCCDDDD
HHEEYY
AAAAAAAA
NN
OOQQOO
AABBBB
AABBAA

Python3, 102 94 bytes
from collections import*
lambda s:"".join(c*(s.count(c)+1&-2)for c in OrderedDict.fromkeys(s))

Thanks to xnor for saving 8 bytes! -> bithack.

This doesn't keep the letters in the right order.

@xnor Thanks for mentioning! Fixed.

Looks good. You can write the expression x+x%2 as x&-2.

@xnor I tried s.count(c)&-2 and it returned an empty string... :/ Any thoughts?

It's working for me. Did you put it out it in parens?

@xnor Here is what I tried. What did I do wrong?

Oh, you're right and I made a mistake. I think x+1&-2 should do it. Evens go to themselves and odds round up to evens.

dict preserves order in 3.6 and above. https://docs.python.org/3.6/whatsnew/3.6.html#new-dict-implementation

05AB1E, 10 bytes
.¡vy¬ygÉ×J

Try it online!
Explanation
.¡           # split string into groups of the same char
  v          # for each group
   y         # push the group
    ¬        # push the char the group consists of
     yg      # push the length of the group
       É     # check if the length of the group is odd
        ×    # repeat the char is-odd times (0 or 1)
         J   # join to string

R, 81 bytes
r=rle(el(strsplit(scan(,""),"")));cat(do.call("rep",list(r$v,r$l+r$l%%2)),sep="")

Reads a string from stdin, splin into vector of characters and perform run-length encoding (rle). Subsequently repeat the each values from the rle, the sum of the lengths and the lengths mod 2.
If we can read input separated by space (implicitly as a vector/array of characters) then we can skip the splitting part and the program reduces to 64 bytes:
r=rle(scan(,""));cat(do.call("rep",list(r$v,r$l+r$l%%2)),sep="")

><> (Fish) 39 bytes
0v ;oo:~/:@@:@=?!voo
 >i:1+?!\|o !:  !<

Pretty sure this can be golfed a lot using a different technique.
It takes an input and compares against the current stack item, if it's different it'll print the first stack item twice, if the same it prints them both.
The stack when empty gets supplied with a 0 which prints nothing so can be appended on whenever.