text:
Equality in the sum of digits
Introduction
Let's take the number 180. This is an interesting number because the sum of digits of this number is equal to:
1 + 8 + 0 = 9

And the squared version of this number, or:
180² = 32400 > 3 + 2 + 4 + 0 + 0 = 9

These are both 9. The sum of digits of the original number and the squared number are the same. Of course, this is also found at OEIS: A058369.
Task
Given a non-negative integer n, output the nth positive number with this condition.
Test cases (zero-indexed)
Input > Output

0 > 1
1 > 9
2 > 10
3 > 18
4 > 19
5 > 45
6 > 46
7 > 55
8 > 90
9 > 99
10 > 100
11 > 145
12 > 180
13 > 189
14 > 190
15 > 198
16 > 199
17 > 289
18 > 351
19 > 361

The input can also be 1-indexed if that fits you better.
This is code-golf, so the submission with the least amount of bytes wins!

In case nobody has spotted it yet, only numbers which are equivalent to 0 or 1 (mod 9) can appear in the list.

@MamaFunRoll Um... no. Sorry. Numbers with digital roots of 5 have squares whose digital root is 7.

@Neil owait nvm

I wrote a Brachylog predicate to determine whether or not the input is a term of this sequence, but couldn't get the find-nth boilerplate working, so I'll just leave it in a comment: ^₂;?{ẹ+}ᵛ

Can we use standard [tag:sequence] rules and have the option to output the entire sequence or the first n elements of it?

Jelly, 13 bytes
,²DS€=/
1Ç³#Ṫ

Input is 1-indexed. Try it online!
How it works
1Ç³#Ṫ    Main link. Argument: n (index)

1        Set the return value to 1.
   #     Execute ... until ... matches have been found.
 Ç         the helper link
  ³        n
    Ṫ    Extract the last match.

,²DS€=/  Helper link. Argument: k (integer)

,²       Pair k with k².
  D      Convert each to decimal.
   S€    Compute the sum of each list of base 10 digits.
     =/  Reduce by equality.

05AB1E, 10 9 8 bytes
µNÐn‚1öË

1-indexed.
-1 byte thanks to @Emigna by removing the implicit ½ (increase counter_variable after every iteration) at the end
-1 byte thanks to @Grimy removing the duplicated SO by using ‚1ö
Try it online.
Explanation:
µ         # Loop while the counter_variable is not equal to the (implicit) input yet:
 NÐ       #  Push the 0-based loop index three times
   n      #  Take the square of this index
          #   i.e. 180 → 32400
    ‚     #  Pair it with the index
          #   i.e. 180 and 32400 → [180,32400]
     1ö   #  Convert both numbers from base-1 to base-10, which basically sums the digits
          #   i.e. [180,32400] → [9,9]
       Ë  #  Check if both sums are equal
          #   i.e. [9,9] → 1 (truthy)
          #  (if they are: implicitly increase the counter_variable by 1)
          # (after the loop: implicitly print the top of the stack, which is the remaining
          #  copy of the index from the triplicate we've used)

You don't need ½ here as it's implicit

-1: µNDn‚1öË. 1ö is like SO but vectorizes, which lets us avoid code duplication.

@Grimy Thanks again. I've also added that as a tip to my Small tips post. :)

Perl 6, 47 46 bytes
{(grep {$_.comb.sum==$_².comb.sum},1..*)[$_]}

Mathematica, 64 bytes
a=Tr@*IntegerDigits;Nest[NestWhile[#+1&,#+1,a@#!=a[#^2]&]&,1,#]&

Simple anonymous function. Zero-indexed.

Haskell, 54 bytes
s=sum.map(read.pure).show
([x|x<-[1..],s x==s(x^2)]!!)

Usage example: ([x|x<-[1..],s x==s(x^2)]!!)  17 -> 289.
s calculates the digit sum:

                    show     -- turn number into a string
     map(read.pure)          -- turn every character (the digits) in to a
                             -- one element string and convert back to integer
sum                          -- sum those integers

main function:

[x|x<-[1..]            ]     -- make a list of all x starting from 1
           ,s x==s(x^2)      -- where s x == s (x^2)
                        !!   -- pick nth element from that list

Pyth, 15
e.fqsjZTsj^Z2TQ

1 byte thanks to DenkerAffe!
Try it here or run a Test Suite.
Uses the 1-indexed option.
Naive implementation using .f which gets the first n numbers that match the given condition.

You can save one byte by removing h if you use 1-indexing which is explicitly allowed.

@DenkerAffe Oh, thanks I should read more closely :P

JavaScript (ES6), 76 73 72 bytes
n=>eval("for(q=s=>eval([...s+''].join`+`),i=1;q(i)!=q(i*i)||n--;i++);i")

I spent 30 minutes trying to get this to work until I realized I was outputting the wrong variable :|
This is zero-indexed.

I feel like turning this into a recursive function would shorten this up a lot...

Vyxal, 8 bytes
↵'²"Ṡ≈;i

Try it Online!
Insights scraped from the MathGolf answer and the 05AB1E answer.
↵'²"Ṡ≈;i # Takes the number as input and returns the n-th number in the series, 0-indexed
↵        # 10**input
 '    ;  # Filter the implicit range [0..n]
  ²      # Square the input
   "     # Pair the square with the input
    Ṡ    # Vectorised sum
     ≈   # All equal?
       i # Index into the resulting list

MATL, 24 23 bytes
x`@2:^"@V!Us]=?@]NG<]1$

Uses 1-based input.
Try it online!
x        % take inpout and delete it (gets copied into clipboard G)
`        %   do...while
  @      %   push loop iteration index: candidate number, n
  2:^    %   array [n n^2]
  "      %   for each element of that array
    @    %     push that element
    V!U  %     get its digits (to string, transpose, to number)
    Xs   %     compute their sum
  ]      %   end for each
  =      %   are the two sums equal?
  ?      %   if so
    @    %     the candidate number is valid: push it
  ]      %   end if
  NG<    %   is number of elements in stack less than input?
]        % if so, proceed with next iteration. End do...while.
1$       % specify 1 input for implicit display: only top of stack

very nice that MATL is finally listed among distant compilers there !.

PARI/GP 46 bytes
s=sumdigits;k=0;while(n,n-=!(s(k++)-s(k^2)));k

1-indexed

Nice to see you here in CGCC!

Retina, 103 bytes
\d+
$*1 x
{`x+
$.0$*x¶$.0$*a¶$.0$*b
%`b
$_
a+|b+
$.0
\d
$*
+`1¶1
¶
1(.*)¶¶$|¶[^d]+
$1x
}`^ ?x

x

Definitely golfable.
Uses the new Retina feature % for squaring (hence not working with the online version yet).

Mathematica, 63 60 61 59 bytes
Select[Range[9^#],Equal@@Tr/@IntegerDigits/@{#,#^2}&][[#]]&

While making this the other answer popped up but I'm beating them by a single byte and I'm posting this before that one gets golfed. One indexed.

Fails for input >2457. Simply increasing your Range won't help, because A058369[n]/n doesn't seem to converge.

Better? filler+

10^# would be shorter than 2^#*9. Of course it becomes too slow after n is bigger than about 6...

Why not 9^#?fil

Do you have a proof that f(n) <= 9^n? (10 is obvious because 10^n is always a solution).

Convex 0.2, 36 35 bytes
Convex is a new language that I am developing that is heavily based on CJam and Golfscript. The interpreter and IDE can be found here. Input is an integer into the command line arguments. Indexes are one-based. Uses the CP-1252 encoding.
1\{\__2#¶{s:~:+}%:={\(\)\}{)\}?}h;(

Julia, 79 66 bytes
f(n,x=0,i=1,s=c->sum(digits(c)))=x<n?f(n,x+(s(i)==s(i^2)),i+1):i-1

This is a recursive function that accepts an integer and returns an integer. It uses 1-based indexing.
We store a few things as function arguments:

n : The input
x : A counter for how many numbers with this condition we've found
i : A number to check for the condition
s : A function to compute the sum of the digits of its input

While x is less than the input, we recurse, incrementing x if i meets the condition and incrementing i. Once x == n, we return i, but we have to subtract 1 because it will have been incremented one too many times.

Mathcad, 70 50 bytes
Mathcad has no built in functions to convert a number to its digit string, so the user function d(a) does this job.   A program then iterates through the positive integers, testing for equality of sums, until it has accumulated n numbers in the vector v.  The program is evaluated using the = operator, which displays the result vector.  (Note that the whole program appears exactly as displayed below on the Mathcad worksheet)
Updated program:
Assumes default initialization of a to zero and makes use of fact that Mathcad returns the value of the last evaluated statement in a program.
Makes use of evaluation order of expressions to increment variable a in the first summation (and which is then available for use in the sum of square)

Original program:
Returns a vector of all numbers up to n.

Ruby, 85 bytes
->n,*a{[*(1..).lazy.filter_map{_1 if _1.digits.sum==(_1**2).digits.sum}.take(n)][-1]}

Attempt This Online!

60 but it can only compute up to the 7th term on ATO. Wasn't sure if this warranted a separate post, but since they're identical except for laziness I'm leaving a comment

Pip, 22 21 20 bytes
($=$+*[_SQ_]FI,EE3a)

-2 Bytes thanks to DLosc!
1-Indexed
Currently operates with a limited range for efficiency, replace 3 with a for infinite range
Try It Online!
How?
($=$+*[_SQ_]FI,EE3a)
                EE3    - 10 to the power of 3
               ,       - Range 0 to n
             FI        - Filter: keep items which return truthy
      [     ]          - Pair
       _               - Identity function
         SQ_           - Identity function squared
   $+*                 - Sum, vectorized at a depth of 1
 $=                    - Are they equivalent?
                   a   - Value at index Input

The construction of the filtering function is quite creative, but unfortunately a more straightforward approach is shorter: $+_=$+SQ_. Also, instead of (...)@a, you can just use (...a) (an important feature which I probably need to document better).

@DLosc thanks for your help, also feel free to post your better answer independently, I wont be changing mine to it due to how different the approaches are :)

IMO it's not really a different approach, but suit yourself. :) If you're not going to change it, then you can golf another byte by removing the space between _ and SQ_.

@DLosc It's different enough, and largely your work, so I wouldn't feel comfortable taking it tbh, but thank you for your suggestions!

Fig, \$10\log_{256}(96)\approx\$ 8.231 bytes
iFmN'=SxS*

Try it online!
Could be ~7.4 bytes under normal sequence rules
Explained
iFmN'=SxS*
 FmN'       # From an infinite list of natural numbers, keep only those where
      Sx    #   the digital sum of the number
     =      #   equals
        S*  #   the digital sum of the square of the number
i           # get the inputh item of the list

Java 8, 113 bytes
n->{int r=0;for(;n>=0;)if((++r+"").chars().map(c->c-48).sum()==(r*r+"").chars().map(c->c-48).sum())n--;return r;}

0-indexed
Explanation:
Try it online.
n->{           // Method with integer as both parameter and return-type
  int r=0;     //  Result-integer, starting at 0
  for(;n>=0;)  //  Loop as long as `n` is zero or positive
    if((++r    //   Increase `r` by 1 first
       +"").chars().map(c->c-48).sum()
               //   And if the sum of its digits
       ==(r*r+"").chars().map(c->c-48).sum())
               //   equals the sum of the digit of its square
      n--;     //    Decrease `n` by 1
  return r;}   //  Return the result

Perl 5 -p, 53 bytes
Includes +1 for -p
1 based
#!/usr/bin/perl -p
$.++while$_-=!eval+("-($.) ".$.**2)=~s/\B/+/gr;$_=$.

Try it online!

TI-BASIC 66 62 bytes
Ans→N:While X<N:IS>(A,A::A:prgmA:Ans→B:A²:prgmA:If B=Ans:IS>(X,N:End:A
sum(int(10fPart(Ans₁₀^(seq(⁻X-1,X,0,log(Ans

Input is \$n\$ in Ans.
Output is the 1-indexed \$n\$th term in the sequence.
Helper function generates the sum of the digits of the value in Ans.
Examples:
3:prgmCDGF1E
             10
5:prgmCDGF1E
             19
8:prgmCDGF1E
             55
10:prgmCDGF1E
             99

Explanation:
Ans→N:While X<N:IS>(A,A::A:prgmA:Ans→B:A²:prgmA:If B=Ans:IS>(X,N:End:A ;prgmCDGF1E

Ans→N            ;store the input in N
While X<N        ;loop until the Nth term has been reached
IS>(A,A:         ;add 1 to A
                 ; (Increment A and skip the next statement if A>A)
A                ;leave A in Ans
prgmA            ;call the helper program below
Ans→B            ;store the result of the helper program in B
A²               ;square A and leave the result in Ans
prgmA            ;call the helper program below
                 ; (result is in Ans)
If B=Ans         ;if the two results are equal
IS>(X,N          ;add 1 to X
                 ; (Increment X and skip the next statement if X>N)
End
A                ;leave A in Ans
                 ;implicit print of Ans

sum(int(10fPart(Ans₁₀^(seq(⁻X-1,X,0,log(Ans   ;prgmA

                      seq(⁻X-1,X,0,log(Ans    ;generate a list...
                                              ; using X as the variable,
                                              ; starting at 0,
                                              ; ending at the log of Ans,
                                              ; and evaluating "⁻X-1" for each element
                                              ; (implicit increment of 1)
                   ₁₀^(                       ;raise 10 to the power of each element
                Ans                           ;multiply each element by the input
          fPart(                              ;remove the integer part from each element
        10                                    ;multiply each element by 10
    int(                                      ;round each element to the nearest integer
sum(                                          ;then sum the resulting list

Note:  TI-BASIC is a tokenized language.  Character count does not equal byte count.

Japt, 15 12 bytes
1-indexed
Èìx ¶X²ìx}iU

Try it
Èìx ¶X²ìx}iU     :Implicit input of integer U
È                :Function taking an integer as argument X
 ì               :  To digit array
  x              :  Reduce by addition
    ¶            :  Is equal to
     X²ìx        :  Digit sum of X squared
         }       :End function
          iU     :Get the Uth integer that returns true

J, 62 bytes
[:{:({.@](>:@[,],[#~(=&(1#."."0@":)*:)@[)}.@])^:(#@]<1+[)^:_&1

Try it online!
1 indexed.  J once again not performing well on these "nth of" tasks, because of the excessive bookeeping mechanics.

APL(NARS), 49 chars, 98 bytes
r←h w;c
c←r←0
→2×⍳∼=/+/¨(⍎¨⍕)¨r,r×r+←1⋄→2×⍳w>c+←1

1-indexed, test:
  h¨⍳20
1 9 10 18 19 45 46 55 90 99 100 145 180 189 190 198 199 289 351 361

MathGolf, 10 bytes
♪╒gÆ‼Σ²Σ=§

Try it online!
Explanation
To make this usable, I chose to present a version which calculates every number with this property below 1000, and fetches the correct item from that list. To have a solution which would work for any input size, the first byte could be replaced by ú (push 10**TOS). Since the n:th term in the sequence is always less than \$10^n\$, the script would always succeed. However, this puts a practical limit on calculation that's very low.
♪            push 1000
 ╒           range(1,n+1)
  gÆ         filter list using the next 5 operators
    ‼        apply next two commands to TOS
     Σ       sum(list), digit sum(int)
      ²      pop a : push(a*a) (square)
       Σ     sum(list), digit sum(int) (pushes the digit sum of the square)
        =    pop(a, b), push(a==b) (compares the two)
         §   get from array (returns the <input>th item from the filtered list

Maybe I should just create a chat for MathGolf.. Anyway, I have a question: are there any builtins for replace, split by, and such for strings? I have the feeling compression might save bytes here, but not sure if the builtins exist to accomplish it.

There is a closed MathGolf chat. I tried keeping it alive, but lately I've been swamped with work, and it kept getting closed. I don't want to bother the mods every time. To answer your question, MathGolf wasn't really meant to handle string operations, but I've implemented functionality for string handling to handle some basic challenges. As you've noticed, there's still a lot to desire. If I add anything, it'll probably be something similar to what 05AB1E has, but I haven't really gotten any spare time for MathGolf development these last months.

Python 3, 125 124 bytes
def f(x,i=1,a=()):
 while len(a)!=x:
  if sum(int(j)for j in str(i))==sum(int(j)for j in str(i**2)):a+=i,
  i+=1
 print(i-1)

Try it online!
1-indexed

124 bytes

JavaScript, 67 66 bytes
I feel very rusty golfing in JS so I'm sure there's something I'm missing here.
1-indexed
n=>(g=x=>(h=y=>eval([...y+``].join`+`))(++x)-h(x*x)||--n?g(x):x)``

Try it online!

Factor + benchmark.ant lists.lazy, 56 bytes
[ 1 lfrom [ dup sq [ sum-digits ] same? ] lfilter lnth ]

Try it online!

1 lfrom Infinite lazy list of the positive integers
[ ... ] lfilter Take the ones where...
dup sq [ sum-digits ] same? ...the digit sum of the number and its square are the same
lnth Take the nth one

JavaScript, 60 bytes
n=>(g=x=>(s=x=>x&&x%10+s(x/10|0))(++x)-s(x*x)||n--?g(x):x)``

An alternate approach for the sum of digits. 0-indexed.

C (gcc), 66 65 bytes
-1 bytes thanks to @ceilingcat
i;s(n){n=n?n%10+s(n/10):0;}f(n){for(i=0;n-=s(++i)==s(i*i););n=i;}

Try it online!

Vyxal, 8 bytes
₌∑²∑=)ȯt

Try it Online!
Alternate 8 byter that uses a more obvious approach, 1-indexed.
Explained
₌∑²∑=)ȯt
     )ȯ  # first n numbers where:
₌∑       #  the sum of the number
₌ ²∑     #  and the sum of the square of the number
    =    #  are equal
       t # last item


text:
Draw the rainbow
The challenge is simple: Draw a rainbow in as few bytes as possible
The specs for the rainbow are as follows:

The figure must be exactly 400 pixels wide and 200 pixels high (optionally 401x201 if you want a single center pixel)
The red ring should touch all borders of the figure (outer radius = 200 pixels)
All rings shall have the same width (10 pixels)

The violet ring shall have an inner radius of 130 pixels

The bow should be the upper half of a perfect circle
The background shall be white (transparent is also accepted)
The figure shall not have borders, (exception is made if the border can't be suppressed)
Builtin rainbow making functions are not allowed!

The following colors are to be used in the rainbow:

This is code golf, so the shortest code in bytes win!
Example:

Related, but different!

Builtin rainbow making functions are not allowed As I'm sure Mathematica has one

How imperfect may the rainbow be? From not anti-aliased to tearing? Consider the images in this answer

@aross: it should look like the sample rainbow (some pixels may vary due to inaccurate calculations). The two last rainbows are too "messy", while the first one looks ok. I don't have a perfect rule, so use you best judgement :-)

@StewieGriffin Reason I'm asking is because apparently PHP graphics is pretty buggy, while the solution is correct in theory. Well, the second one is, the third one would be with anti-aliasing (which also doesn't work well)

Are vector graphics not allowed? edit: never mind—I see that there's already a TikZ answer, so I gather they are.

MATL, 107 95 92 87 84 83 bytes
-200:200 0:200!PYyq10/k12-t8<*t0>*Q7B.561FTh.295Oh.51h4BPFTF6Bl.5hOh4B8$v255*k5M/YG

This works in current release (14.0.0) of the language/compiler.
EDIT (July 6, 2017): You can try it at MATL Online!.
To check that the colors are correct, remove the last five characters (you need to wait for a few seconds and scroll down to the end of the output).

Explanation
The code has three main steps:
Step 1: Generate a 201x401 matrix with numbers from 1 to 8. Pixels with value 1 are background (white), pixels with values 2, ..., 8 represent each band of the rainbow.
Horizontal coordinates range from -200 to 200 left to right, and vertical coordinates range from 0 to 200 bottom to top. So the origin (0,0) is bottom center, the upper left corner is (-200,200), etc.
The different bands of the rainbow are generated by computing the distance from each pixel to the origin and quantizing in steps of 10 pixels.
Step 2: Generate an 8x3 matrix defining the colormap. Each row is one of the necessary colors (white and the seven colors of the rainbow). Each value of the previous 201x401 matrix will be interpreted as an index to a row of this colormap.
We generate the colormap matrix using values between 0 and 1 for each color component, and then multiplying by 255 and rounding down. This way most values are initially 0 and 1, which will later become 0 and 255. Intermediate values are coded as values between 0 and 1 with 2 or 3 decimals, chosen so that when multiplied and rounded give the exact desired value.
Step 3: Display the image with that colormap.
               % STEP 1: CREATE MATRIX DEFINING THE RAINBOW BANDS
-200:200       % row vector [-200, -199, ..., 200]
0:200          % row vector [0, 1, ..., 200]
!P             % transpose and flip: convert into column vector [200; 199; ...; 0]
Yy             % hypotenuse function with broadcast: distance from each point to (0,0)
q10/k          % subtract 1, divide by 10, floor (round down). Gives 20 circular bands
               % 10 pixels wide, with values from 0 to 19
12-            % subtract 12
t8<*           % values larger than 7 are set to 0
t0>*           % values less than 0 are set to 0. We now have 7 bands with values
               % 1, ..., 7, and the white background with value 0
Q              % add 1: white becomes 1, bands become 2, ..., 8

               % STEP 2: CREATE MATRIX DEFINING THE COLORMAP
7B             % first row: [1 1 1] (7 converted to binary: color white)
.561FTh        % second row (light purple)
.295Oh.51h     % third row (dark purple)
4BP            % fourth row: [0 0 1] (4 converted to binary and flipped: blue)
FTF            % fifth row (green)
6B             % sixth row: [1 1 0] (6 converted to binary: yellow)
l.5hOh         % seventh row: orange
4B             % eigth row: [1 0 0] (4 converted to binary: red)
8$v            % vertically concatenate the 8 eight rows
255*k          % multiply by 255 and round down. Gives exact color values
5M/            % push 255 again and divide. This is needed because colors in MATL are
               % defined between 0 and 1, not between 0 and 255

               % STEP 3: DISPLAY
YG             % display image with that colormap

Piet, 838 codels, several thousand pixels
Someone had to do it:

If you save this image you can try it online!
The actual Piet program is only the top ~125 pixels, which I created using a Python program I wrote.
Editing this afterwards really hurt my vision, I'll be tripping for days!
This outputs the image in an SVG format, because SVG really is (in my opinion) the simplest way to do this. I shamelessly stole Doorknob's SVG code. Outputs:

well, this really:
<svg viewBox='0 0 400 200'><circle cx='200' cy='200' r='200' fill='red'/><circle cx='200' cy='200' r='190' fill='#ff7f00'/><circle cx='200' cy='200' r='180' fill='yellow'/><circle cx='200' cy='200' r='170' fill='lime'/><circle cx='200' cy='200' r='160' fill='blue'/><circle cx='200' cy='200' r='150' fill='indigo'/><circle cx='200' cy='200' r='140' fill='#8f00ff'/><circle cx='200' cy='200' r='130' fill='white'/></svg>

Good luck beating this answer, non-Esolang users!

Is this python script public? I'm asking for a friend, who is very lazy....

Erm, it takes literally ~2 minutes to implement xD You can find an old version here and adjust it if necessary: http://www.mediafire.com/download/0isocsb81n7r2cv/piet.py (note: I made this when I was 10, the code is embarrassing to say the least) - it needs PyPNG installed.

Minecraft 1.10 (almost), 2677 characters one-command, 868 blytes
Well I sure picked a verbose language.
summon FallingSand ~ ~1 ~ {Block:log,Time:1,Passengers:[{id:FallingSand,Block:redstone_block,Time:1,Passengers:[{id:FallingSand,Block:activator_rail,Time:1,Passengers:[{id:MinecartCommandBlock,Command:"summon ArmorStand ~ ~ ~ {Tags:[\"b\"]}"},{id:MinecartCommandBlock,Command:"summon Pig ~ ~ ~ {NoAI:1b}"},{id:MinecartCommandBlock,Command:setblock ~-1 ~-2 ~6 chain_command_block 3 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=200] ~ ~ ~ tp @e[c=1] ~ -99 ~"}},{id:MinecartCommandBlock,Command:setblock ~-1 ~-2 ~5 chain_command_block 3 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=190,r=200] ~ ~ ~ setblock ~ ~ ~ wool 14"}},{id:MinecartCommandBlock,Command:setblock ~-1 ~-2 ~4 chain_command_block 3 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=180,r=190] ~ ~ ~ setblock ~ ~ ~ wool 1"}},{id:MinecartCommandBlock,Command:setblock ~ ~-2 ~4 chain_command_block 4 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=170,r=180] ~ ~ ~ setblock ~ ~ ~ wool 4"}},{id:MinecartCommandBlock,Command:setblock ~ ~-2 ~5 chain_command_block 2 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=160,r=170] ~ ~ ~ setblock ~ ~ ~ wool 13"}},{id:MinecartCommandBlock,Command:setblock ~ ~-2 ~6 chain_command_block 2 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=150,r=160] ~ ~ ~ setblock ~ ~ ~ wool 11"}},{id:MinecartCommandBlock,Command:setblock ~ ~-2 ~7 chain_command_block 2 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=140,r=150] ~ ~ ~ setblock ~ ~ ~ wool 10"}},{id:MinecartCommandBlock,Command:setblock ~ ~-2 ~8 chain_command_block 2 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=130,r=140] ~ ~ ~ setblock ~ ~ ~ wool 2"}},{id:MinecartCommandBlock,Command:setblock ~1 ~-2 ~8 chain_command_block 4 replace {auto:1,Command:"tp @e[type=Cow] ~1 ~ ~"}},{id:MinecartCommandBlock,Command:setblock ~1 ~-2 ~7 chain_command_block 3 replace {auto:1,Command:"tp @e[type=Bat] ~-1 ~ ~"}},{id:MinecartCommandBlock,Command:setblock ~1 ~-2 ~6 chain_command_block 3 replace {auto:1,Command:"execute @e[type=Pig] ~ ~ ~ summon Bat ~ ~ ~ {NoAI:1b}"}},{id:MinecartCommandBlock,Command:setblock ~1 ~-2 ~5 chain_command_block 3 replace {auto:1,Command:"execute @e[type=Pig] ~ ~ ~ summon Cow ~ ~ ~ {NoAI:1b}"}},{id:MinecartCommandBlock,Command:setblock ~1 ~-2 ~4 repeating_command_block 3 replace {auto:1,Command:"tp @e[type=Pig] ~ ~1 ~"}},{id:MinecartCommandBlock,Command:setblock ~ ~ ~1 command_block 0 replace {Command:fill ~ ~-3 ~-1 ~ ~ ~ air}},{id:MinecartCommandBlock,Command:setblock ~ ~-1 ~1 redstone_block},{id:MinecartCommandBlock,Command:kill @e[type=MinecartCommandBlock,r=1]}]}]}]}

Make a new Superflat world, paste that mess into an Impulse command block, set your render distance fairly high, and run it. Break the armor stand when your computer stops lagging.
The result is 400 blocks across and 200 blocks tall, as requested.
I used MrGarretto's one command generator to pack everything together, and then modified the result of that a little bit to save a couple more bytes. Here's the input to it:
INIT:summon ArmorStand ~ ~ ~ {Tags:["b"]}
INIT:summon Pig ~ ~ ~ {NoAI:1b}
tp @e[type=Pig] ~ ~1 ~
execute @e[type=Pig] ~ ~ ~ summon Cow ~ ~ ~ {NoAI:1b}
execute @e[type=Pig] ~ ~ ~ summon Bat ~ ~ ~ {NoAI:1b}
tp @e[type=Bat] ~-1 ~ ~
tp @e[type=Cow] ~1 ~ ~
execute @e[tag=b] ~ ~ ~ execute @e[rm=130,r=140] ~ ~ ~ setblock ~ ~ ~ wool 2
execute @e[tag=b] ~ ~ ~ execute @e[rm=140,r=150] ~ ~ ~ setblock ~ ~ ~ wool 10
execute @e[tag=b] ~ ~ ~ execute @e[rm=150,r=160] ~ ~ ~ setblock ~ ~ ~ wool 11
execute @e[tag=b] ~ ~ ~ execute @e[rm=160,r=170] ~ ~ ~ setblock ~ ~ ~ wool 13
execute @e[tag=b] ~ ~ ~ execute @e[rm=170,r=180] ~ ~ ~ setblock ~ ~ ~ wool 4
execute @e[tag=b] ~ ~ ~ execute @e[rm=180,r=190] ~ ~ ~ setblock ~ ~ ~ wool 1
execute @e[tag=b] ~ ~ ~ execute @e[rm=190,r=200] ~ ~ ~ setblock ~ ~ ~ wool 14
execute @e[tag=b] ~ ~ ~ execute @e[rm=200] ~ ~ ~ tp @e[c=1] ~ -99 ~

That's a total of 15 1.9+ command blocks, and 838 bytes, so 15*2 + 838 = 868 blytes.
Here's the (almost) part, it's missing a corner and edge. It logically shouldn't - Minecraft bug? Would be exactly 400x200 blocks if it wasn't for that. Not much I can do.

Yay, a pig based rainbow generator ! +1

If it's 2677 characters how can it be only 868 "blytes"? From how I understand that page the actual blytes should be 2677 + 4

It's 868 if you build it in the world, 2677 if you use fallingsand to create it (which has a lot of overhead)

Pyth, 150 149 128 bytes
"<svg viewBox=0,0,400,200>"V8s["<circle cx=200 cy=200 r="-200*TN" fill="@c"red #ff7f00 #ff0 #0f0 #00f indigo #8f00ff #fff"dN" />

Outputs in SVG:
<svg viewBox=0,0,400,200>
<circle cx=200 cy=200 r=200 fill=red />
<circle cx=200 cy=200 r=190 fill=#ff7f00 />
<circle cx=200 cy=200 r=180 fill=#ff0 />
<circle cx=200 cy=200 r=170 fill=#0f0 />
<circle cx=200 cy=200 r=160 fill=#00f />
<circle cx=200 cy=200 r=150 fill=indigo />
<circle cx=200 cy=200 r=140 fill=#8f00ff />
<circle cx=200 cy=200 r=130 fill=#fff />

Thanks to @MamaFunRoll for 16 bytes and @PatrickRoberts for 6 more!

You could probably save a lot of bytes by packing the strings.

@AquaTart All that does is add bytes. O_o

I don't think you need any of the quotes, ending slashes, or the last ending </svg> tag.

Two suggestions: red #ff7f00 #ff0 #0f0 #00f #8f00ff #fff for the color list and take single quotes off all parameter values that don't have spaces in them (cx, cy, r and fill) but make sure to leave a space between the value of fill and the / so the color doesn't get misinterpreted. Also remove the </svg> as suggested above.

Sorry, I meant red #ff7f00 #ff0 #0f0 #00f indigo #8f00ff #fff. Also if you replace the spaces with commas in the viewBox you can remove the single quotes for that parameter as well.

I think this is the longest Pyth program I've ever seen - probably due to the fact that almost none of it is actually Pyth code - it's almost all just the SVG output...

Just for the record, here is a link to a compressed version of the code. It may look like the characters are more than one byte, but it fits inside a one byte encoding.

Mathematica 152 144 126 bytes
Graphics@MapIndexed[{#,Disk[{0,0},4-#/5&@@#2,{Pi,0}]}&,RGBColor/@TextWords@"#f00 #ff7f00 #ff0 #0f0 #00f #4b0082 #8f00ff #fff"]

Thanks @CatsAreFluffy for shaving off 8 bytes & @njpipeorgan for a further 18 :)

Use # vs #[[1]], #2 vs #[[2]], and @@@ vs /@.

Also, Thread works instead of Transpose.

Graphics@MapIndexed[{#,Disk[{0,0},4-#/5&@@#2,{Pi,0}]}&,RGBColor/@TextWords@"#f00 #ff7f00 #ff0 #0f0 #00f #4b0082 #8f00ff #fff"] saves another 18 bytes, but the idea is the same.

Just curious... is there a "rainbow builtin"?

@mbomb007 not that i'm aware of!

@mbomb007 There's something like 113 built-in colour palettes, but I don't think one of them happens to match the colours required in this challenge.

HTML+SVG+ES6, 169

<svg width=400 viewBox=0,0,40,20 onload="this.innerHTML=`f00
ff7f00
ff0
0f0
00f
4b0082
8f00ff
fff`.replace(/.+/g,c=>`<circle cx=20 cy=20 r=${--r} fill=#${c} />`,r=21)"/>

use height=200 and cx=200 cy=200 r=${--r}0 instead of viewBox='0 0 40 20'. That should save 7 bytes.

I hope it's okay that I borrowed your idea with the .replace method...

@PatrickRoberts of course it's ok, I borrowed some of yours

I surely didn't expect to see r-=1 in code golf...

@Neil bah! it was -=10 in some iteration before the final release

@PatrickRoberts I prefer not to use your idea of width and height, just to keep some difference between out answers

vim, 165 142 139
i<svg viewBox=0,0,400,200><cr><circle cx=2<C-n> cy=2<C-n> r=2<C-n> fill=red<cr>#ff7f00<cr>#ff0<cr>#0f0<cr>#00f<cr>indigo<cr>#8f00ff<cr>#fff<esc>2Gqq0y4f=jPBB10<C-x>@qq@qV2G:norm A /><cr>

Yeesh, this is clunky. There's got to be improvements that can be made.
Outputs as SVG, like my Pyth answer.
Thanks to @MyHamDJ for shaving off 3 bytes!

You could shave off 2 bytes (or keystrokes) if you replace your last ex command with kv3G:norm A'/><cr>

You could also take 3 more off if you enter the <circle cx... string on line 2 the first time through, rather then typing all of the colors then entering it afterwards.

JavaScript (ES6), 171 158 bytes
document.write`<svg width=400 height=200>${`f00
ff7f00
ff0
0f0
00f
4b0082
8f00ff
fff`.replace(/.+/g,c=>`<circle cx=200 cy=200 r=${i--}0 fill=#${c} />`,i=20)}`

Credit to @edc65 for the idea to convert
`[...].map((c,i)=>...)`

to
`...`.replace(/.+/g,c=>...,i=20)

It may look longer but the amount of bytes saved in compressing the array to a string is well worth the conversion. (It saves 13 bytes in this case)
Demo

document.write`<svg width=400 height=200>${`f00
ff7f00
ff0
0f0
00f
4b0082
8f00ff
fff`.replace(/.+/g,c=>`<circle cx=200 cy=200 r=${i--}0 fill=#${c} />`,i=20)}`

Ruby with Shoes, 155 bytes
Shoes.app(width:400,height:200){background'fff'
8.times{|i|stroke fill %w{f00 ff7f00 ff0 0f0 00f 4b0082 8f00ff fff}[i]
oval left:i*=10,top:i,radius:200-i}}

Sample output:

HTML (162) + CSS (146)

body{height:200px;width:400px}div{height:100%;box-sizing:border-box;border-radius:50% 50% 0 0/100% 100% 0 0;border:solid;border-width:10px 10px 0}

HTML (224) + CSS (128)

body{height:200px;width:400px}div{height:100%;box-sizing:border-box;border-radius:50% 50% 0 0/100% 100% 0 0;padding:10px 10px 0}

LaTeX, 290 bytes
\documentclass{proc}\input tikz\begin{document}\def\z#1!#2!#3!#4!{\definecolor{t}{rgb}{#1,#2,#3}\fill[color=t](200pt,0)circle(#4pt);}\tikz{\clip(0,0)rectangle(400pt,200pt);\z1!0!0!200!\z1!.5!0!190!\z1!1!0!180!\z0!1!0!170!\z0!0!1!160!\z.29!0!.51!150!\z.56!0!1!140!\z1!1!1!130!}\end{document}

Try it here.
Explanations
\documentclass{proc}
\input tikz
\begin{document}

    %Define macro "\z" with 4 arguments.
    % The first 3 arguments are rgb values for the color
    % Last argument is the radius in pt that we draw a full circle with

    \def\z#1!#2!#3!#4!
        {\definecolor{t}{rgb}{#1,#2,#3}
         \fill[color=t](200pt,0)circle(#4pt);}

    % Start a Tikz figure

    \tikz{

        % We only draw the top half of the circle

        \clip(0,0)rectangle(400pt,200pt);

        % Draw each circle from biggest to smallest

        \z1!0!0!200!
        \z1!.5!0!190!
        \z1!1!0!180!
        \z0!1!0!170!
        \z0!0!1!160!
        \z.29!0!.51!150!
        \z.56!0!1!140!

        % Draw a white circle last

        \z1!1!1!130!
    }
\end{document}

SpecBAS - 318 254 bytes
If we're drawing rainbows, then it seems like a good place to use the successor to ZX Spectrum BASIC.
1 p,k=20,x1=0,x2=400,y=200
2 FOR EACH s IN [16711680,16744192,16776960,65280,255,4915330,9371903]: PALETTE p,s: INC p: NEXT s
3 CLS 15: DRAW 0,200 TO 70,200: DRAW 330,200 TO 400,200
4 FOR i=1 TO 7
5 INK k: DRAW x1,y TO x2,y,-PI: DRAW x1+10,y TO x2-10,y,-PI: FILL x1+5,190
6 x1+=10,x2-=10,k+=1
7 NEXT i

Line 2 sets up the palette for the specific RGB values needed (and is probably not helping the byte count) as standard Spectrum colours didn't match up.
The DRAW command can take an extra parameter which makes it turn through a number of degrees radians between x1,y1 and x2,y2. Finally it finds a gap in the semicircles just drawn and flood fills with the current colour.

Tcl/Tk, 263 bytes
canvas .c -bg #FFF -bo 0 -highlightt 0;pack .c -e 1 -f both;wm ge . 400x200;foreach {r c} {200 #FF0000 190 #FF7F00 180 #FFFF00 170 #00FF00 160 #0000FF 150 #4B0082 140 #8F00FF 130 #FFF} {.c cr o -$r -$r $r $r -outline $c -f $c};after 100 {.c x s -5 u;.c y s -10 u}

Alas, this kind of question always favors some esoteric languages...
That said, Tcl/Tk really makes graphics operations all of: easy, short, and readable.
That said, I've sacrificed readability to crunch options down to as few characters as possible. I don't imagine crunching the list of colors will help much compared to code to unpack it...
For comparison, here's the uncrunched code (380 bytes):
canvas .c -bg #FFF -borderwidth 0 -highlightthickness 0
pack .c -expand yes -fill both
wm geometry . 400x200
foreach {r c} {
  200 #FF0000
  190 #FF7F00
  180 #FFFF00
  170 #00FF00
  160 #0000FF
  150 #4B0082
  140 #8F00FF
  130 #FFFFFF
} {
  .c create arc -$r -$r $r $r -extent 180 -outline $c -fill $c
}
after 100 {
  .c xview scroll -5 units
  .c yview scroll -10 units
}

The after command was unfortunately necessary since no scrolling (of the canvas's coordinate origin) can be done before the window is mapped to the screen.
Also, the crunched code actually draws a full rainbow (using a circle instead of an arc) and just relies on window clipping...
Anyway, I hope y'all enjoy. :O)

You can use lmap instead of foreach to shorten.

And you can put the first line inside the second like : pack [canvas .c -bg #FFF -bo 0 -highlightt 0] -e 1 -f both

There is an incoherence between the two versions of you code. Golfed does create oval; ungolfed does create arc. Can you please explain?

Thanks for the comment. The ungolfed version is for readability, not exactness in implementation. And, alas, I am not going to go back and fix all my foreach-->lmap; that can be left for the reader... :O)

Java, 354 bytes
public void r() throws IOException{BufferedImage i=new BufferedImage(400,200,2);Graphics2D g=i.createGraphics();g.setStroke(new BasicStroke(10));int[]c={0xFF0000,0xFF7F00,0xFFFF00,0xFF00,255,0x4B0082,0x8F00FF};for(int v=0;v<7;v ++){g.setColor(new Color(c[v]));g.drawArc(v*10+5,v*10+5,390-v*20,390-v*20,0,360);}ImageIO.write(i,"PNG",new File("a.png"));}}

Just uses the Graphics2D class to draw 7 arcs, with an array to store the colors. I'm sure it can be improved further.
Ungolfed code:
public void ungolfed() throws IOException {
        BufferedImage i = new BufferedImage(400, 200, 2); // 2 is TYPE_INT_ARGB
        Graphics2D g = i.createGraphics();
        g.setStroke(new BasicStroke(10));
        int[] c = {0xFF0000, 0xFF7F00, 0xFFFF00, 0x00FF00, 0x0000FF, 0x4B0082, 0x8F00FF};
        for(int v = 0; v < 7; v ++) {
            g.setColor(new Color(c[v]));
            g.drawArc(v * 10 + 5, v * 10 + 5, 390 - v * 20, 390 - v * 20, 0, 360);
        }
        ImageIO.write(i, "PNG", new File("a.png"));
    }

Your 0x0000ff could be just 0xff or even just 255, same with 0x00ff00 being 0xff00. 0xff0000 could be 255<<16 to save another byte. Your loop could be to save a few more bytes. You can save one more byte by adding a ,q to your int declaration. You'd have to make it int c[]= instead of int[] c so q is an int and not an int[]. Doing that lets you add a q=390-v*20; to your loop. and replace the 390-v*20 with a q. It's a lot of work for one byte, but a byte is a byte, right?!

You can save two more bytes by just throwing Exception instead of IOException.

I also wonder if you can use drawOval and just render the top half of the image... might be a little more expensive though...

I know it's been about 1.5 year, but you can golf quite a bit.. void r()throws Exception{BufferedImage i=new BufferedImage(400,200,2);Graphics2D g=i.createGraphics();g.setStroke(new BasicStroke(10));for(int c[]={255<<16,16744192,16776960,65280,255,4915330,9371903},v=0,t;v<7;g.drawArc(t=v*10+5,t,t=390-v++*20,t,0,360))g.setColor(new Color(c[v]));ImageIO.write(i,"PNG",new File("a.png"));}} (325 bytes)

CSS, 244 242 240 bytes
body{width:400px;height:200px;background-image:radial-gradient(500px at bottom,#FFF 26%,#8F00FF 26%,#8F00FF 28%,#4B0082 28%,#4B0082 30%,#00F 30%,#00F 32%,#0F0 32%,#0F0 34%,#FF0 34%,#FF0 36%,#FF7F00 36%,#FF7F00 38%,red 38%,red 40%,#FFF 40%)}

Edit: Saved 2 bytes by working around a bug in Chrome. Saved a further 2 bytes thanks to @TrangOul.
Note: the snippet uses a
 due to limitations of Stack Snippets.

div {
    width: 400px;
    height: 200px;
    background-image: radial-gradient(500px at bottom,
        #FFF 26%,
        #8F00FF 26%, #8F00FF 28%,
        #4B0082 28%, #4B0082 30%,
        #00F 30%, #00F 32%,
        #0F0 32%, #0F0 34%,
        #FF0 34%, #FF0 36%,
        #FF7F00 36%, #FF7F00 38%,
        red 38%, red 40%,
        #FFF 40%);
}

It looks like the background on the outside of the rainbow is red (at least on my phone).

@StewieGriffin Works fine for me in Firefox for Android. (I couldn't work out how to enable Stack Snippets in my phone's default browser.)

Ok, a bit strange :-) i'm using chrome 49.0.2623.91 on galaxy s6 edge btw.

@StewieGriffin Looks like it's broken in Chrome for Windows too.

@StewieGriffin OK I think I have a workaround, and it saves two bytes too!

You can save two bytes by using red color instead of #F00.

C, 220 217 213 bytes
#define X printf("%c",s<169|s/401?y:s
i=8e4,t,y=255;main(s){for(puts("P6 400 200 255");i--;X/288?y:s<195?143:s<225?75:0),X<256|s/360?0:s/323?127:y),X<225&s/195?130:s<256?y:0))s=i/400,t=i%400-200,s=(s*s+t*t)/100;}

Output is PPM (the binary kind).
Edit: Saved a couple bytes thanks to @tucuxi.
Edit 2: Rearranged code to save even more.

you can shave a byte with i;s;t;main() -> s;t;main(i), and another one by placing part of your for loop body within the for: ;)code1,code2; -> ;code2)code1; (saved a comma!).

JavaScript 271 251

c=document.body.appendChild(document.createElement('canvas'))
x=c.getContext('2d')
c.width=400
r=c.height=200
for(i=0;i<8;x.beginPath(),x.arc(r,r,r-i*10,0,7),x.fillStyle="#"+"FF0000FF7F00FFFF0000FF000000FF4B00828F00FFFFFFFF".substr(i++*6,6),x.fill());

Thanks @StewieGriffin I've made the change for 10.  Been trying to get the count down but still a ways from doorknobs pyth answer!

You can move everything between the for's { ... } to inside the last for section, seperated by ,. e.g. for(i=0;i<8;x.beginPath(),x.arg(...etc...)). You can probably also use slice/splice of substr if I'm not mistaken. It might also be shorter to make the  using .innerHTML. Or even a HTML+JS answer and give the  and id of c and then it should automatically be added as a JS global variable

@Downgoat substr has the advantage here in that its second parameter is a length, not an offset. As for golfing, document.body would seem to provide a considerable saving.

Bubblegum, 139 119 bytes
Hexdump:
00000000: b329 2e4b 5728 cb4c 2d77 caaf b035 d031  .).KW(.L-w...5.1
00000010: d031 3130 d031 3230 b0e3 b249 ce2c 4ace  .110.120...I.,J.
00000020: 4955 48ae b005 f215 922b c154 1198 4ccb  IUH......+.T..L.
00000030: ccc9 b12d 4a4d 51d0 c7ad ced0 12aa 4e39  ...-JMQ.......N9
00000040: 2dcd 3c0d 2884 4fad 0542 2d7e 85e6 3085  -.<.(.O..B-~..0.
00000050: 0604 149a c115 1aa4 e155 680a 5598 9997  .........Uh.U...
00000060: 9299 9e8f 57a9 09cc 4c0b a07f d2f0 1b6b  ....W...L......k
00000070: 8cf0 1148 2100 0a                        ...H!..

Sadly, this is shorter than my Pyth answer. :(
Generates the same SVG file.

Google Blockly, 48 blocks, 75 bytes

Click the gif below to navigate to the solution, where you can get a closer look at how it works.
As for an explanation, I think an image is worth a thousand words, and thus a gif is worth a thousand images.
link to big readable gif

Note: I'm unsure how to count in Blockly, so I counted every block as 1 byte, and every variable the regular way, so that 0 == 1 byte, 530 == 3 bytes, Arial == 5 bytes and bold == 4 bytes.
I counted the special character I used to cut off the rainbow as 2 bytes.
Please report any mistakes or suggestions of the byte count in the comments

Postscript (87 bytes)
Hex dump:
00000000: 3188 0131 2030 2e35 3631 8800 3120 302e  1..1 0.561..1 0.
00000010: 3237 3888 0030 2e35 3188 0030 8801 3088  278..0.51..0..0.
00000020: 0130 8801 3188 0031 2030 2e35 8800 3188  .0..1..1 0.5..1.
00000030: 0030 87c8 0038 7b34 2031 9287 929d 87c8  .0...8{4 1......
00000040: 0030 2032 9258 3087 b400 9205 9216 9242  .0 2.X0........B
00000050: 880a 92a9 7d92 83                        ....}..

Output:

Processing, 196 186 181 179 169 163 bytes
int d=400,i=0;size(d,d/2);background(-1);int[]c={-65536,-33024,-256,#00ff00,#0000ff,#4b0082,#8f00ff,-1};for(noStroke();i<8;ellipse(200,200,d,d),d-=20)fill(c[i++]);

Saved 10 bytes thanks to Kritixi Lithos
... and another 6 bytes thanks to dzaima

Can shave off one more byte by changing for(int i=0;i<8;i++) into for(int i=0;i++<8;) or similar

I don't think you can use variables while calling size()

@KritixiLithos What do you mean?

When I call size with variables as parameters, it gives me an error (before running) that I cannot use variables to set the dimensions on the screen

background(-1) is one byte shorter than background(255), and you can change the 255 in array c to -1 to save another byte

You can do int d=400,i=0; so that you can remove the int i=0 in the for-loop. Furthermore I think you can do fill(c[i++]) to remove the i++ in the third statement of the for-loop

@KritixiLithos Thanks again

You should be able to move the d-=20 into the third statement of the for-loop and delete the space in int[] c :)

@KritixiLithos Alright, alright! Jeez! Updated the answer :)

Last one, I haven't tested this, but the last for-loop might be able to be changed into for(;i<8;ellipse(200,200,d,d),d-=20)fill(c[i++]); now that you've updated your answer :)

@KritixiLithos Works. But that had better be the last one! :)

You can move the noStroke(); in the for loops start, saving one byte

And you can replace the color array to {-65536,-33024,-256,#00ff00,#0000ff,#4b0082,#8f00ff,-1}

@dzaima Thanks - updated

HTML + CSS, 310 307 bytes

source: Stack Exchange

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

sort: votes


text:
Minimum Scalar Product
Minimum Scalar Product
The inspiration for this code golf problem is from Google's code jam competition. The premise behind the problem is, given the input of two vectors of varying lengths, find the minimum possible scalar. A scalar can be found using the following formula:
x1 * y1 + x2 * y2 + ... + xn * yn

The problem, however, is that multiple values for the scalar can be found depending on the order of the numerals in the input case (seen below). Your goal is to determine the minimum possible scalar integer solution by plugging in the input case numbers into the equation and solving for it. You may use every number in the input only once, and must use all of the numbers.
Allow me to provide an example with the following vectors.
Input
3
1 3 -5
-2 4 1

Output
-25

The first integer on the line represents the number of numbers, n, in each vector. In this case, we have three numbers in each vector.
The number n may vary with each test case, but there will always be two vectors.
In the example input, the minimum scalar product would be -25.
(-5 * 4) + (1 * 1) + (3 * -2) = 25

Rules

You may only use each integer in both vectors once.
You must use all integers in the vectors.
Your output must only include the final product
I'll select the solution with the least amount of code, which follows all of the specifications listed above, in any language!

 Hint: You don't need to brute force this problem, unless it makes your code shorter. There is a specific method involved in finding the minimum spanning scalar :).

I really don't want to spoil for anybody, so don't open this unless you already know the answer. this is so well-known it's funny. https://en.m.wikipedia.org/wiki/Rearrangement_inequality

Jelly, 6 bytes
ṢṚ×Ṣ}S

Try it online!
Using brute force is equally short:
Œ!×S€Ṃ

How it works
ṢṚ×Ṣ}S  Main link. Arguments: u (vector), v (vector)

Ṣ       Sort the components of u.
 Ṛ      Reverse.
   Ṣ}   Sort the components of v.
  ×     Multiply the results, element by element.
     S  Compute the sum of the products.

Seriously, 6 bytes
,SR,S*

Try it online!
Explanation:
,SR,S*
,SR     input first vector, sort, reverse
   ,S   input second vector, sort
     *  dot product

APL, 15 bytes
{+/⍺[⍒⍺]×⍵[⍋⍵]}

This is a dyadic function that accepts arrays on the left and right and returns an integer. It uses the same approach as my Julia answer: dot product of the sorted arrays, one descending and one ascending.
Try it here

MATL, 6 bytes
Code:
SiSP*s

My first MATL answer :)
Explanation:
S       # Sort the first array
 iS     # Take the second array and sort it
   P    # Flip the array
    *   # Multiply both arrays with each other
     s  # Sum of the result

Try it online!

I'm glad to see this! :-)

Mathematica, 30 17 bytes
-13 bytes by murphy
Sort@#.-Sort@-#2&

Function, input is vector1(list),vector2(list)
Several revisions:
Plus@@(Sort@#*Reverse@Sort@#2)&(*me*)
Total[Sort@#*Reverse@Sort@#2]&
Sort@#.Reverse@Sort@#2&        (*alephalpha*)
Sort@#.Sort[#2,#>#2&]&         (*murphy*)
Sort@#.SortBy[#2,-#&]          (*me*)
Sort@#.-Sort@-#2&              (*murphy*)

clever solution!

Sort@#.Reverse@Sort@#2&

Sort@#.Sort[#2,#>#2&]&

Sort@#.-Sort@-#2&

Or for your solution 1, Sort@#.SortBy[#2,-#&]

Julia, 32 25 bytes
x->y->-sort(-x)⋅sort(y)

This is an anonymous function that accepts two arrays and returns an integer. To call it, assign it to a variable and do f(x)(y).
For inputs x and y, we simply compute the dot product of x sorted in reverse order with y sorted. We get x in reverse sorted order by negating all values, sorting, then negating again.
Saved 7 bytes thanks to Dennis!

Pyth - 14 8 bytes
I think I figured out the trick.
s*VSQ_SE

Try it online here.

Perl 6, 33 30 bytes
{sum @^a.sort Z*@^b.sort.reverse}

Why not {sum @^a.sort Z*[R,] @^b.sort}((1,3,-5),(-2,4,1)).say

Javascript ES6, 69 bytes
a=>b=>a.sort((x,y)=>x-y).map((x,y)=>i+=b.sort((x,y)=>y-x)[y]*x,i=0)|i

Wow, this is way too long.

I think trying to reuse the sort function is costing you 3 bytes.

I did more golfing. Better?

You can probably save a byte with |i instead of &&i

Thx @ETHproductions

Yes, that's what I was thinking of.

CJam, 11 Bytes
q~$\$W%.*:+

Try it online!

Python, 139 bytes
def mdp(n, a, b):
    a = list(reversed(sorted(a)))
    b = sorted(b)
    res = sum([a[i] * b[i] for i in range(len(a))])
    return res

You can save a few bytes by removing spaces next to equals, for instance b = sorted(b) turns into b=sorted(b) (2 bytes saved). You can additionally put multiple statements on the same line by separating them with a semicolon, for instance a=list(reversed(sorted(a)));b=sorted(b);res=0

@charredgrass I'm new here. What's the need to save every possible byte? I was trying to make it readable.

Welcome to PPCG then! This question is a [tag:code-golf] competition where the goal is to write code to complete the challenge in the fewest bytes possible, which usually means less readable code.

@charredgrass got it!

Much shorter: lambda a,b,s=sorted:sum(x*y for x,y in zip(s(a)[::-1],s(b))). We don't require function submissions to be named (so an unnamed lambda is valid), and the n parameter is unnecessary (many other submissions omit it entirely).

C++, 124 bytes
#include<algorithm>
int m(int*a,int*b,int n){std::sort(a,a+n);std::sort(b,b+n);int r=0;while(--n>=0)r+=a[n]**b++;return r;}

ungolfed:
#include<algorithm>
int m(int*a,int*b,int n){
 std::sort(a,a+n);
 std::sort(b,b+n);
 int r=0;
 while(--n>=0)
  r+=a[n]*(*b++);
return r;
}

At first i used std::greater<int>() for the sort in b but just reversing the order in the summation is easier.

Haskell, 59 bytes
import Data.List
v?u=sum$zipWith(*)(sort v)$reverse$sort u

RETURN, 29 bytes
[{␆␃}\{␆}␄␅[¤¥][×␌]#}␁[¤][+]#]

Try it here.
Replace any ␆␃␄␇ with their unprintable counterparts.
Anonymous lambda that leaves result on stack2. Usage:
""{1 3 0 5-}""{0 2- 4 1}[{␆␃}\{␆}␄␅[¤¥][×␌]#}␁[¤][+]#]!

Explanation
[                                 ]  lambda
 {␆␃}                              sort and reverse first stack
       \{␆}                         sort second stack
            ␄␅                     transpose and flatten
               [  ][  ]#             while loop
                ¤¥                     check if 2 items exist in stack
                    ×                  if so, multiply top 2 items
                     ␌                 and push to stack2
                        }␁          switch to stack2
                           [¤][+]#   sum stack2

J, 14 bytes
+/@(*|.)&(/:~)

Uses the same principle as the others.
Explanation
+/@(*|.)&(/:~)  Input: x on LHS and y on RHS
        &(/:~)  Sort both x and y
     |.         Reverse the sorted y
    *           Multiply the sorted x and reversed sorted y elementwise
+/@             Reduce the products using addition and return

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


text:
JSF**k with only 5 symbols?
This is not a challenge but a question, I figured it was on topic because of

Non-challenge questions that are related to solving programming puzzles or a particular type of challenge are also on topic.

Now on to the question:
Is it possible to write any JavaScript code with only 5 letters? JSFuck already does this with 6 symbols !+[]() but I wonder if the ! character is needed.
JSFuck works with a combination of casting to string (by adding an empty array), casting to number (by writing a + in front) and casting to boolean by negating.
For example:
[]        \\ Empty array
+[]       \\ Cast to number -> 0
!+[]      \\ Negate -> true
!+[]+[]   \\ Cast to string -> "true"

From this string we can extract all it's letters using the square brackets with a number inside, and any number can be made by adding true together that many times.
Like this a lot of letters can be found and can be concatenated to strings. The most important string to be able to create is "constructor" because it can be used to get the Function from any function, and this object can be used to execute strings as JavaScript:
[]["find"]                          \\ the function Array.prototype.find
[]["find"]["constructor"]           \\ the Function object
[]["find"]["constructor"](string)() \\ same as eval(string)

As you can see, ! has 2 uses here:

Creating numbers to select letters from strings.
Casting to boolean to get "true" and "false".

The first one of these 2 can also be done using the ++ incrementor, not directly on 0, but it can be used on elements inside an array:
+[]          \\ 0
[+[]]        \\ [0]
[+[]][+[]]   \\ [0][0] -> 0
++[+[]][+[]] \\ ++[0][0]-> 1
++[[]][+[]]  \\ also works because ++ casts to number

So all numbers can be created without !.
The second one is more difficult. The importance of "true" and "false" lays in the letters "r" and "s", which both appear in "constructor". I have already found all the other letters of "constructor" by means of "undefined", "Infinity", "NaN" and by casting functions to strings.
So the ultimate question: (How) can you create booleans, or the letters "r" and "s" in JavaScript by only using +[]() ?
The letter "l" might also help. It can be obtained form null but I havent been able to get that value with those 5 symbols. It can for example be used to get booleans if we already have "s":
[]["includes"]()       \\ false
[+[]]["includes"](+[]) \\ true

The letter "l" and "k" together would give access to "r":
([]+[])["link"]() \\ ""

Any way to get a boolean, null or any of the letters r s l k would be very useful!
A library of what we have:

Array.prototype.find: [][(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[++[[]][+[]]])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])])]

Infinity: +((++[[]][+[]]+[])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(++[[]][+[]]+[])+(+[])+(+[])+(+[]))

NaN: +[][[]]

undefined: [][[]]

0: +[]

1: ++[[]][+[]]

2: (++[[]][+[]])+(++[[]][+[]])

3: (++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])

4: (++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])

5: (++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])

6: (++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])

7: (++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])

8: (++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])

9: (++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])

a: (+[][[]]+[])[++[[]][+[]]]

c: ([][(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[++[[]][+[]]])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])])]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])]

d: ([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])]

e: ([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])]

f: ([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])]

i: ([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])]

n: ([][[]]+[])[++[[]][+[]]]

o: ([][(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[++[[]][+[]]])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])])]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])]

t: (+((++[[]][+[]]+[])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(++[[]][+[]]+[])+(+[])+(+[])+(+[]))+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])]

u: ([][[]]+[])[+[]]

v: ([][(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[++[[]][+[]]])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])])]+[])[(++[[]][+[]])+(++[[]][+[]])+[]+((++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]]))]

y: (+((++[[]][+[]]+[])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(++[[]][+[]]+[])+(+[])+(+[])+(+[]))+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])]

I: (+((++[[]][+[]]+[])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(++[[]][+[]]+[])+(+[])+(+[])+(+[]))+[])[+[]]

N: (+[][[]]+[])[+[]]

" ": ([][(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[++[[]][+[]]])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])])]+[])[+(++[[]][+[]]+[]+((++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])))]

(: ([][(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[++[[]][+[]]])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])])]+[])[+(++[[]][+[]]+[]+((++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])))]

): ([][(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[++[[]][+[]]])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])])]+[])[+(++[[]][+[]]+[]+((++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])))]

{: ([][(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[++[[]][+[]]])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])])]+[])[+(++[[]][+[]]+[]+((++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])))]

}: ([][(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[++[[]][+[]]])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])])]+[])[+((++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+[]+((++[[]][+[]])+(++[[]][+[]])))]

.: (+(++[[]][+[]]+[]+(++[[]][+[]])+([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])]+(++[[]][+[]]+[]+(+[])+(+[])))+[])[++[[]][+[]]]

,: [[]][([][(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[++[[]][+[]]])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])])]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])]+([][(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[++[[]][+[]]])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])])]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])]+([][[]]+[])[++[[]][+[]]]+([][(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(([][[]]+[])[++[[]][+[]]])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])])]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])]+(+[][[]]+[])[++[[]][+[]]]+(+((++[[]][+[]]+[])+(([][[]]+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])])+(++[[]][+[]]+[])+(+[])+(+[])+(+[]))+[])[(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])+(++[[]][+[]])]]([[]])+[]

This is very closely related to http://codegolf.stackexchange.com/q/11690/194 , and if that question had a JS answer I would have voted to close. As it is, an answer to this question is likely to translate directly into an answer to the earlier question, but the difference makes it sufficiently borderline that I don't want to close unilaterally.

I would really like an answer to this question and I'm not going to get that from the other question, so thanks for not closing. And indeed, I will add v :)

Very nice question. I'm absolutely in favour of question about esoteric programming and unconventional computational models, but be prepared for some people close voting, because currently this doesn't quite fit the scope people agree on on meta. I'd love for this to set a precedent for such questions though. :)

Comments are not for extended discussion; this conversation has been moved to chat.

Questions like this make me wish there was a feature to give a bounty to a question.

I got eval in 2453 chars with window allowed.

Side note: You can almost do JSF*** without parentheses by replacing bounding parentheses (xyz) with [xyz][+[]], but that removes function calls, making many things impossible.

"[]+x gets us a string representation of x in general.": counter example: x=!+[]+!+[] evaluates to x=2, but []+x evaluates to "truetrue". This statement should be rephrased using x+[], so that left-to-right evaluation will effectively result in a faithful string representation of x.

After brainstorming, the result seems to be that, on modern browsers at least, there’s no way to do this.
I’ll try to summarize the entire process, adding some reasoning about why we’ve exhausted our options in any given domain before moving on. Then, barring some kind of amazing new insight (like, a corner case of JavaScript syntax everyone is forgetting about) it’ll be pretty clear that there’s no way to get the remaining letters.
Literals
The only immediate literals you can make with +()[] are the nested empty arrays [], [[]], [[[]]], etc. From there, we can start casting values using +:

+[] gets zero, which Jens’s trick expands to arbitrary positive integers using ++.
[]+[] is "". In fact, []+x gets us a string representation of x in general.

[]’s next use is indexing. Indexing an object out-of-bounds ([][[]]) gets you undefined. Casting that to a string and indexing the result gets you the letters d e f i n u; casting it to an integer first using + gets you NaN, from which the letters a N follow.
Using the ++ trick on any non-integer value reached so far either gives NaN or an error. Also, none of the objects we can create are callable (yet), so () doesn’t help (except for grouping).
The remaining tricks up our sleeve are casting and indexing. So the question is: which strings can we create using the characters 0123456789adefinuN that either

are number literals we can round-trip cast to integer to get new strings, or
are property names of objects we can already reach?

Number literals
As an example of the second option, we can make the string "1e1000", and then get Infinity from +"1e1000", and casting that back to string gets us the letters y and I.
Also, we can make "11e100", cast to number and back to string, to get "1.1e+101", from which we extract . and +.
Using that ., in turn, we can make the string ".0000001", cast it to number and back, to get "1e-7", winning us -.
That’s basically all floats will get you: there aren’t any more interesting values other than Infinity and NaN, and there aren’t any more characters used in their usual string representations other than -+.0123456789e.
Properties
So we have the letters -+.0123456789adefinuyIN. Which properties can we reach? Let’s ask JavaScript.
>>> R = /^[-+.0123456789adefinuyIN]+$/
>>> [Array, Object, String, Number].reduce((h, f) => {
        h[f.name] = Object.getOwnPropertyNames(f.prototype).filter(x => x.match(R));
        return h }, {})

{ Array: [ 'find' ], Object: [], String: [], Number: [] }

Only [].find, which Jens already found. Let’s cast that to a string, reap all of its letters, and try again. The string representation is a bit different across browsers. On Chrome and Edge, "function find() { [native code] }" contains acdefinotuv()[]{} and a space; our full alphabet is now +-.()[]{}0123456789INacdefinotuvy. On Firefox, there are more spaces and newlines, but the letters are the same.
We repeat our search:
>>> R = /^[+-.()\[\]{}0123456789INacdefinotuvy]+$/
>>> [Array, Object, String, Number, Function].reduce((h, f) => {
        h[f.name] = Object.getOwnPropertyNames(f.prototype).filter(x => x.match(R));
        return h }, {})

{ Array: [ 'concat', 'find' ],
  Object: [],
  String: [ 'concat' ],
  Number: [],
  Function: [] }

String.prototype.concat is deprecated: it does exactly what + does, which we can already do. So we got Array.prototype.concat and Array.prototype.find. What can we do with them?
Functions
concat() lets us create, for the first time, longer arrays. [[]].concat([[]]) is [[], []], and casting that to a string gets us ",". (This doesn’t help us find new properties.) But .concat doesn’t modify our values, and it can never return null or anything like that.
Calling find() doesn’t help us either: the MDN documentation says

The find() method returns a value in the array, if an element in the array satisfies the provided testing function. Otherwise undefined is returned.

Both of those we can already do using indexing.

And from here, there’s nowhere else to go. If you doubt anything I’ve written, let me know in the comments.

My personal approaches I've worked with in the past hours alone have yielded all the feasible null returning functions: String.prototype.match, RegExp.exec, and Array.prototype.includes. Finding all of these impossible to form, unless there is an odd way to form a regex I do not know about, I have also concluded that there is no possible way to do this.

Nice analysis! This is probably the correct answer but i'm still hoping for some trick... probably false hope though :)

If we could get the letters for catch and throw, could we get the letters of the error?  That is 'hwr'.

Even if we construct the strings "catch" and "throw", which we currently can’t, we’d need something eval-like to use those as keywords, which is our goal in the first place.

Negative numbers are possible using - and number casting, but that's not very helpful.

Firefox also gives a string representation of find, although it's function find() {\n<four spaces>[native code]\n}.

@ETHproductions I already use this

The 3 functions in Lynn's answer weren't that useless. But the strict mode in ECMAScript 5 foiled my plan.
There is a quirk in the older versions of JavaScript / ECMAScript. If a method is called without an object, the global object window is assumed. So we can do this:
a = {f:function(){return this}};
a.f();                            // Returns a.
g = a.f;
g();                              // Returns window.
window.g();                       // Also returns window.

This is still true for modern browsers, but only if the function isn't defined in strict mode. And all built-in functions (with native code) seemed to be in strict mode. In older browsers when there isn't the strict mode yet, this also works for built-in functions.
Assume we are using older browsers. Then if we want window, we have to find a built-in function that returns something containing this. Within the only choices we had, there is the function Array.prototype.concat doing exactly that. We can test it like this:
Number.prototype.concat = Array.prototype.concat;
1..concat(2);                     // Returns [1, 2]
concat = Array.prototype.concat;
window.concat(2);                 // Returns [window, 2]
concat(2)                         // TypeError in modern browsers while
                                  //   returning the same thing in older ones.
concat.bind(window)(2)            // A workaround in modern browsers.

So basically it doesn't care whether the object it is called upon is an array (but it must be an object for the least). It just wraps it in an array if not.
If we had window, firstly we can get the string [object Window] by casting it to a string. With the new character b, we can get r and s using the following two lines respectively, and every character we didn't have in constructor:
window["atob"]("cuaa")[0]
window["atob"]("cyaa")[0]

But the other problem is to remove the object reference from [].concat. Wrapping it in an array and extracting doesn't work, because [].concat already means []["concat"]. The only way I know which could possibly be constructed using +[]() is to return it from a function. Array.prototype.find seemed to be able to do that:
[[]["concat"]]["find"](x=>1)      // Returns Array.prototype.concat, where x=>1 can
                                  //   be replaced with any always truthy function.

We had always truthy functions. Array.prototype.concat and String.prototype.concat both return truthy if the object is window. If we use the later one, we made use of all of the three available functions.
But, unfortunately, Array.prototype.find doesn't exist in the old browser we are using. At least I didn't find one that works. And I didn't find another way removing the object reference.
The complete code that is testable in modern browsers that returns r and s, with the .bind(window) workaround:
[[]["concat"]]["find"](""["concat"].bind(window)).bind(window)()[0]["ato"+([]+[[]["concat"]]["find"](""["concat"].bind(window)).bind(window)()[0])[2]]("cuaa")[0];
[[]["concat"]]["find"](""["concat"].bind(window)).bind(window)()[0]["ato"+([]+[[]["concat"]]["find"](""["concat"].bind(window)).bind(window)()[0])[2]]("cyaa")[0]

Cool info. What browsers have you tried?

@Lynn Not many. Mostly Firefox 3.6.0 and 25.0. I read from here and here that find came much later than strict mode so finding something working is unlikely. I asked about Edge because I thought it may have a chance preferring backward compatibility to following the standard. I also tried Konqueror for the same reason. And some command line browsers, but none of them even support JavaScript.

I tried Safari 7.1 and 8, and some random supposedly default browsers on phones on a browser screenshot website. None works so far.

@jimmy23013 Try Safari 5.0 or 5.1. According to Can I use, Partial support in older Safari refers to strict mode still accepting a lot of JS that should be considered invalid. Though find wasn't implemented yet, maybe it was partially?... If only it was in their list...


text:
Find the longest path, avoiding obstacles in a 2D plane
The Scenario
You are given a matrix of size m x n (width x height) with m*n spots where there are a few obstacles. Spots with obstacles are marked as 1, and those without are marked as 0. You can move vertically or horizontally, but can visit each spot only once. The goal is to cover as much area/spots as possible, avoiding obstacles.
Input
A 2D Matrix consisting of 0s and 1s and the coordinates of starting point.
Example Matrix1:
0(0,0) 1(0,1) 0(0,2)
0(1,0) 0(1,1) 0(1,2)
1(2,0) 0(2,1) 0(2,2)

Example Matrix2:
0(0,0) 0(0,1) 1(0,2) 0(0,3) 0(0,4)
0(1,0) 1(1,1) 0(1,2) 0(1,3) 0(1,4)
0(2,0) 0(2,1) 0(2,2) 1(2,3) 0(2,4)
0(3,0) 1(3,1) 0(3,2) 0(3,3) 0(3,4)
0(4,0) 0(4,1) 1(4,2) 0(4,3) 0(4,4)

The coordinates shown above, next to matrix elements is for explanation only. They are nothing but array indices. Actual input would just be the matrix. for example1 the input is just,
0 1 0
0 0 0
1 0 0

Input for example2,
0 0 1 0 0
0 1 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 1 0 0

Starting Point (0,0).
Output
Output should be a line containing comma separated moves. A move is a space separated direction (n,s,e,w) and number of units of movement in the direction (range 1-1000).
Example output for the matrix in example1 would be,
s 1,e 1,s 1,e 1,n 2

(0,0) --> (1,0) --> (1,1) --> (2,1) --> (2,2) --> (1,2) --> (0,2)

and for the matrix in example2 would be,
s 2,e 2,n 1,e 1,n 1,e 1,s 4,w 1,n 1,w 1

(0,0) --> (1,0) --> (2,0) --> (2,1) --> (2,2) --> (1,2) --> (1,3) --> (0,3) --> (0,4) --> (1,4) --> (2,4) --> (3,4) --> (4,4) --> (4,3) --> (3,3) --> (3,2)

which is the longest path, visiting each coordinate only once and avoiding those coordinates with obstacles.
Objective Winning Criteria
Should compute the distance efficiently(efficient: performance wise, fast program basically) for huge matrices (Of order say, 500x500). One which computes the fastest wins (All submissions run on my machine, for fairness). No restrictions on number of bytes!
Here is a 20x20 matrix which can be used to get some idea of the performace, for tuning purposes.
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0

Welcome to Programming Puzzles & Code Golf. Every challenge here needs an objective winning criterion, so its possible to determine a winner. In your case you should go with code-golf, so the solution with the fewest bytes of code wins. For future posts please check out the sandbox to get feedback first, before you post your challenge.

Edited. Thanks. Sorry! This was my first time here.

If you want this to be reopened, you need to improve the spec a bit as well. Firstly you should add more testcases, one is not enough. Also you shold format them in a way that makes it easy to copy-paste them (the matrix could just be a 2D array. Furthermore you need to specify the expected output more. I guess `s,e,w,n' are used to indicate north, west, ... but you need to make it clear. Also it is generally discouraged to require a specific I/O format. Just let everyone choose the most convenient input format that fits the used language best.

@xnor Really? I think limiting it to only orthogonal moves (and not allowing moves from any point to any other) should make this one a bit different?

@MartinBüttner Oh, I totally misunderstood that challenge, my bad.

I think this would be more interesting if output format was more flexible, for example sesenn. As it stands, a significant part of the efffort is formatting the output

@DonMuesli Yes, you are right. Output can be as you said. It can even just be coordinates/array indices of points to be visited.

If the winning criterion is running speed, you should remove the "code golf" tag. And you should define precisely how speed will be measured. For example, some answer may be the fastest for small matrices, and some other for large matrices. Which one wins then?

Also posted on CS.SE.
Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.  Also, where did you encounter this problem? Please make sure to attribute your sources. Thank you!

@DonMuesli I have already mentioned this in the winning criteria, but going to reiterate the one which computes the path for large matrices (largest being of the order 1000x1000) wins!

@D.W. My intention of posting it here was just to share this problem since I felt it is interesting and fun to solve! Wanted this problem to reach out to as many people as possible. The intention of posting it on CS.SE was purely for learning purposes. I wanted some advice on best algorithms to use for solving this. The problem might be the same but the intent with which it was posted was entirely different. Thats why different SE sites exist? Each with a different purpose?

@xor I don't see how fastest for large matrix is fair - whoever has the biggest mainframe wins...  what if I can't afford a mainframe?  Shouldn't it be fastest on some specific computer (maybe yours)?  That way the fastest algorithm wins instead of the most expensive computer.

Are the outputs for the given test cases canonical?  i.e. where (in case 2) there is an equivalent option, if the algorithm happens to choose a different but equally-covering route (that differs from the output in the question) is this valid?  Or must the algorithm always be bias a certain way under equivalency choices?  (and obviously, if so, how does this bias work/which way/etc?)

Also, just out of interest... Is: s 2,e 1,w 2,s 3,n 2,e 1,s 2,s 1,s 3,s 1,s 3,n 2,n 3,s 2,n 7,e 1,n 5,e 1,s 4,s 3,n 1,e 1,s 3,s 1,e 1,w 2,s 1,s 1,s 2,e 3,w 2,e 3,n 1,s 2,s 1,w 1,e 2,e 2,w 1,n 2,n 1,n 2,w 1,w 3,e 2,w 1,s 1,n 1,n 1,n 1,n 1,n 1,n 1,n 3,w 1,n 5,e 1,e 2,e 5,w 3,w 2,s 2,s 1,s 1,e 1,n 2,s 1,s 1,s 1,s 1,e 1,e 2,e 1,w 1,e 2,s 1,w 1,e 4,s 1,e 1,n 2,e 1,n 5,e 2,w 2,n 3,e 2,w 2,e 2,e 1,w 1,s 1,s 3,w 1,w 1,e 1,w 2,s 2,s 2,n 1,s 1,s 3,w 4,n 1 the correct path for the 20x20 matrix? ;P

@Tersosauros. Please, correct me if I'm wrong. I've summed up those values and it gave me 193. I did also a very simple algorithm (without any strategy for selecting directions) and the highest value was 219 check here. I think the output for the 20x20 matriz in the example should be some path with steps around 300... :/

@Washington Guedes
Your 219 move solution skips 22 accessible cells/nodes - see this diagram of your solution's path.
"some path with steps around 300..." It is true that there are 301 unblocked nodes.  However, 43 of these are inaccessible (i.e. any [near-]optimum solution cannot traverse them).
The largest path I've been able to find in the 20x20 matrix is 258.  Obviously, the 193 node path I suggest above is not optimum, as you have pointed out.

Python 3, 2619 bytes (90 LOC), ~6 seconds (20x20)

#!/usr/bin/env python

import networkx as nx

class input(object):
    def __init__(self,world_string):
        rows=world_string.split("\n")
        column_count=len(rows[0])
        blocked_cells=[]
        x=0
        y=-1
        for row in rows:
            if len(row)>column_count:
                column_count=len(row)
            y+=1
            for column in row:
                if column=='1':
                    blocked_cells.append((y,x))
                x+=1
            x=0
        self.matrix=world(len(rows),column_count)
        self.block_graph(blocked_cells)
        self.matrix.add_sink()

    def block_graph(self,block_list):
        for cell in block_list:
            self.matrix.block_cell(cell)

class world(object):
    SINK="END"

    def __init__(self, rows=3, columns=3):
        self.graph=nx.grid_2d_graph(rows, columns)
        for e in self.graph.edges():
            self.graph[e[0]][e[1]]["weight"]=-1.0

    def block_cell(self,node):
        neighbours=list(self.graph[node].keys())
        for linked_node in neighbours:
            self.graph.remove_edge(node,linked_node)

    def add_sink(self):
        matrix=self.graph.nodes()[:]
        self.graph.add_node(world.SINK)
        for source_cell in matrix:
            self.graph.add_edge(source_cell, world.SINK, weight=1.0)

class algorithm(object):
    SOURCE=(0,0)
    def find_path(graph):
        def _heuristic(current, target):
            if current==target:return 0.0
            cost=nx.astar_path(graph, algorithm.SOURCE,current,lambda x,y:1)
            return -1 * len(cost)
        path=nx.astar_path(graph, algorithm.SOURCE, world.SINK, _heuristic)
        return path[:-1]

class output(object):
    directions={
        ( 1,  0)  : "n",
        (-1,  0)  : "s",
        ( 0,  1)  : "w",
        ( 0, -1)  : "e"
    }

    def edge_to_direction(source_node, dest_node):
        row_delta=source_node[0]-dest_node[0]
        column_delta=source_node[1]-dest_node[1]
        return output.directions[(row_delta, column_delta)]

    def path_to_directions(path):
        result=""
        for step in range(len(path)-1):
            result+=output.edge_to_direction(path[step],path[step+1])
        return result

    def simplify_directions(directions):
        directions+="\0"
        count=0
        result=""
        last=""
        for d in directions:
            if d!=last or d is "\0":
                result+="{} {},".format(last, count)
                count=0
                last=""
            if count==0:
                last=d
                count=1
                continue
            if d==last:
                count+=1
        return result[3:-1]

if __name__=='__main__':
    contents="010\n000\n100"    #read from file?

    data=input(contents).matrix.graph
    result_path=algorithm.find_path(data)
    directions=output.path_to_directions(result_path)
    directions=output.simplify_directions(directions)
    print(directions+"\n")
    print(str(result_path)[1:-1].replace('), (',') --> (').replace(', ',','))

Performance
I ran this solution (on my old Core i3 laptop) on the 20x20 'performance' example input and it ran in around ~6 seconds (of course, YMMV).  I am SURE there are ways to do this faster, probably by orders of magnitude.  However, I didn't feel like re-writing my own A* algorithm in assembly and renting some time slices on a super computer!
About this Code
The Idea
The idea for this approach comes from my answer over here in Code Review.  You can also read a little bit more about it and the end of my answer here.
Dependencies
As you may have notice by the (rather prominent) line import networkx as nx - this code relies upon the Python NetworkX module to function.  So do >pip install networkx if you get import errors when running.
Breakdown of Solution Elements by Lines of Code
I also thought it would be interesting (and it was), after Don Muesli's comment (particularly the part "a significant part of the efffort[sic] is formatting the output"), to examine how much of the code is for various things.
      Breakdown:

39 lines (or 43.33%) of the lines of code in the program are concerned with parsing the input and constructing/weighting the graph data structure.
37 lines (approx. 41%) directly relate solely to displaying and formatting the desired output!
5 lines (5.5%) are 'other' stuff, which relates to running the program (shebang line, imports, the if __name__=="__main__"..., etc).
And 9 (yes.. nine) lines of code (or just 10%) actually relates to the algorithm usage.

      Obligatory Pie Chart:

About the Approach
As I mentioned above, most of the idea for this approach comes from my answer over on Code Review regarding this problem.
The process itself is relatively straightforward:

Transform the given matrix into an undirected graph data structure
Annotate (i.e. add weights) the edges of that graph
Add a "sink" node - to be used as a search target
Add (weighted) edges between all nodes and the sink node
Use a Graph Search Algorithm (in this case A*)

So, taking the 3x3 matrix from the question for example.  The transformation into a graph would yield something like the following:

(Note: the 'blocked' nodes do not have any edges)
Step 2; imagine each green line in the above picture has a weight of -1.
Next, for step 3 and 4 together (I didn't want to have to make another picture), take a look at the following graph:

And again imagine the edges are weighted, only red lines are weighted +1.
We can then apply the A-star algorithm from the NetworkX library to this graph, using the custom heuristic function.
This makes the search algorithm score paths in an inverse manner (longest path rather than shortest).  And the longest path will be the one that visits the most cells of the problem matrix!

Welcome to Programming Puzzles & Code Golf! Amazing first answer!

This fails to find the longest path even on the smallest 3×3 example case: it finds a path through 6 nodes instead of 7. I don’t particularly blame you for that, because even the question author doesn’t seem to realize that this problem is NP-complete, but you could have at least mentioned it. There is no way A-star can produce optimal solutions, no matter what heuristic you give it, because it will never revisit a vertex that it previously found on a different path.

Clingo, 202 seconds for 20×20
This problem is NP-complete, even if you were to guarantee that all 0s are used, so your dreams of a program that runs efficiently for 500×500 may be a little bit unrealistic.
(The other answer using A* search doesn’t find the optimal solution, even on the 3×3 example case, because A* never revisits a node that was previously found on a different path.)
#script (python)

import clingo
import itertools
import sys

def main(prg):
    matrix = [list(line.split()) for line in sys.stdin]

    def data():
        for i, row in enumerate(matrix):
            for j, cell in enumerate(row):
                if cell == '0':
                    yield f'cell(({i}, {j})).\n'

    def on_model(model):
        step = {}
        for atom in prg.symbolic_atoms:
            if atom.symbol.name == 'step' and model.contains(atom.symbol):
                a, d, b = atom.symbol.arguments
                step[a] = d, b
        moves = []
        a = clingo.Tuple((0, 0))
        while step[a][1] != clingo.Tuple((0, 0)):
            d, a = step[a]
            moves.append(d)
        print(len(moves) + 1)
        print(','.join(f'{d} {len(list(g))}' for d, g in itertools.groupby(moves)))

    prg.add('data', [], ''.join(data()))
    prg.ground([('base', []), ('data', [])])
    prg.solve(on_model=on_model)

#end.

#program base.

dir(s, (1, 0); e, (0, 1); n, (-1, 0); w, (0, -1)).
adj((X, Y), D, (X+DX, Y+DY)) :- cell((X, Y)), dir(D, (DX, DY)), cell((X+DX, Y+DY)).
adj(A, end, (0, 0)) :- cell(A).
{step(A, D, B) : adj(A, D, B)} = 1 :- visit(A).
:- visit(B), {step(A, D, B) : adj(A, D, B)} != 1.
visit((0, 0)).
visit(B) :- step(A, D, B).
:~ visit(A). [-1, A]

#show step/3.

Demo
$ clingo -q longest.lp < 20x20.in
clingo version 5.2.2
Reading from longest.lp
Solving...
1

2
s 1
3
s 2
4
s 3
5
e 3,s 1
6
e 3,s 2
7
e 3,s 3
9
e 3,s 5
…
264
s 4,e 1,n 4,e 2,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,w 1,n 1,w 1,s 3,e 1,n 1,e 1,s 12,e 1,n 13,e 2,s 1,e 2,n 7,e 1,s 2,e 2,n 1,w 1,n 1,e 4,s 5,w 1,s 1,e 1,s 1,w 2,s 1,e 2,s 1,w 1,s 1,e 1,s 1,w 2,s 1,w 1,s 2,w 1,n 3,e 1,n 1,e 1,n 1,w 1,n 3,e 1,n 1,w 1,n 1,e 2,n 3,w 1,s 2,w 3,s 1,e 1,s 1,w 1,s 1,e 1,s 4,w 1,n 2,w 1,s 3,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 3,s 1,e 1,n 3,e 1,n 1,e 1,s 2,w 1,s 1,e 1,s 1,w 1,s 2,w 1,n 1,w 2,n 1,w 2,s 1,e 1,s 1,w 1,s 1,e 2,n 1,e 1,s 1,e 3,n 2,e 2,n 1,e 2,s 3,e 1,n 1,e 1,n 6,w 1,n 1,e 1,n 9,w 1,n 1,e 1,n 1,w 2,s 3,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 3,e 1,s 1,w 1,s 1,e 1,s 2
265
s 4,e 1,n 4,e 2,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,w 1,n 1,w 1,s 3,e 1,n 1,e 1,s 12,e 1,n 13,e 2,s 1,e 2,n 7,e 1,s 2,e 2,n 1,w 1,n 1,e 4,s 5,w 1,s 1,e 1,s 1,w 2,s 1,e 2,s 1,w 1,s 1,e 1,s 1,w 2,s 1,w 1,s 2,w 1,n 3,e 1,n 1,e 1,n 1,w 1,n 3,e 1,n 1,w 1,n 1,e 2,n 3,w 1,s 2,w 3,s 1,e 1,s 1,w 1,s 1,e 1,s 4,w 1,n 2,w 1,s 3,e 1,s 1,w 1,s 1,e 1,s 1,w 1,s 1,e 3,s 1,e 1,n 3,e 1,n 1,e 1,s 2,w 1,s 1,e 1,s 1,w 1,s 2,w 1,n 1,w 2,n 1,w 2,s 1,e 1,s 1,w 1,s 1,e 2,n 1,e 1,s 1,e 3,n 2,e 2,n 1,e 2,s 1,e 1,s 1,w 1,s 1,e 2,n 3,w 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 1,n 1,w 1,n 1,e 2,s 15
OPTIMUM FOUND

Models       : 99
  Optimum    : yes
Optimization : -265
Calls        : 1
Time         : 201.664s (Solving: 201.56s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 201.602s

The final output line (above OPTIMUM FOUND) corresponds to the following path through 265 nodes:
• ┌───┐ 1 0 1 ┌─┐ ┌───────┐ 1 0 1 ┌───┐
│ │ ┌─┘ 1 0 1 │ │ └─┐ ┌─┐ │ 1 0 1 └─┐ │
│ │ └─┐ 1 0 1 │ └───┘ │ │ │ 1 0 1 ┌─┘ │
│ │ ┌─┘ 1 0 1 │ ┌─────┘ │ │ 1 0 1 └─┐ │
└─┘ └─┐ 1 0 1 │ └─┐ ┌───┘ │ 1 0 1 ┌─┘ │
┌─┐ ┌─┘ 1 0 1 │ ┌─┘ └─┐ ┌─┘ 1 0 1 └─┐ │
│ └─┘ ┌───┐ 1 │ └─┐ ┌─┘ └─┐ 1 0 1 ┌─┘ │
│ ┌─┐ │ 1 └───┘ 1 │ │ ┌───┘ 1 0 1 └─┐ │
└─┘ │ │ 1 0 1 ┌─┐ │ │ └───┐ 1 0 1 ┌─┘ │
0 1 │ │ 1 1 1 │ │ │ └─┐ ┌─┘ 1 0 1 └─┐ │
0 1 │ │ 1 1 1 │ └─┘ ┌─┘ └─┐ 1 0 1 ┌─┘ │
0 1 │ │ 1 1 1 └─┐ ┌─┘ ┌───┘ 1 0 1 └─┐ │
0 1 │ │ 1 1 1 ┌─┘ │ ┌─┘ ┌─┐ 1 0 1 ┌─┘ │
0 1 │ │ 1 1 1 └─┐ │ │ ┌─┘ │ 1 0 1 └─┐ │
0 1 │ │ 1 1 1 ┌─┘ └─┘ │ ┌─┘ 1 0 1 ┌─┘ │
0 1 │ │ 1 1 1 └─────┐ │ └─┐ 1 0 1 └─┐ •
0 1 │ │ 1 1 1 ┌───┐ └─┘ ┌─┘ 1 ┌───┐ └─┐
0 1 │ │ 1 1 1 └─┐ └───┐ │ ┌───┘ 1 └─┐ │
0 1 │ │ 1 1 1 ┌─┘ ┌─┐ └─┘ │ 1 0 1 ┌─┘ │
0 1 └─┘ 1 1 1 └───┘ └─────┘ 1 0 1 └───┘

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


text:
Iterated Moving Average
If we have a list, say the list [9, 2,  4,  4,  5,  5,  7], we can do a moving average across it.
Taking a window of say, 3 elements, each element is replaced by a window like such: [[9], [9, 2], [9, 2, 4], [2, 4, 4], [4, 4, 5], [4, 5, 5], [5, 5, 7]], and then taking averages, we get [9.0, 5.5, 5.0, 3.3333333333333335, 4.333333333333333, 4.666666666666667, 5.666666666666667].
Pretty simple so far. But one thing you can notice about this is that taking a moving average "smooths out" the list. So this begs the question: how many times does one have to take a moving average to make the list "smooth enough"?
Your task
Given a list of floats, an integer window size, and a float, output how many times one has to take the moving average to get the standard deviation less than that float. For those that don't know, standard deviation measures how un-smooth a set of data is and can be calculated by the following formula:

For example, using our earlier list and a max stddev of .5, we get 8 iterations that look like this:
[9.0, 5.5, 5.0, 3.3333333333333335, 4.333333333333333, 4.666666666666667, 5.666666666666667]
[9.0, 7.25, 6.5, 4.6111111111111116, 4.2222222222222223, 4.1111111111111107, 4.8888888888888893]
[9.0, 8.125, 7.583333333333333, 6.1203703703703702, 5.1111111111111107, 4.3148148148148149, 4.4074074074074074]
[9.0, 8.5625, 8.2361111111111107, 7.2762345679012341, 6.2716049382716044, 5.1820987654320989, 4.6111111111111107]
[9.0, 8.78125, 8.5995370370370363, 8.024948559670781, 7.2613168724279831, 6.2433127572016458, 5.3549382716049374]
[9.0, 8.890625, 8.7935956790123466, 8.4685785322359397, 7.9619341563786001, 7.1765260631001366, 6.2865226337448554]
[9.0, 8.9453125, 8.8947402263374489, 8.7175997370827627, 8.4080361225422955, 7.8690129172382264, 7.141660951074531]
[9.0, 8.97265625, 8.9466842421124824, 8.8525508211400705, 8.6734586953208357, 8.3315495922877609, 7.8062366636183507]

and end with a stdev of 0.40872556490459366. You just output 8.
But there's a catch:
The answer does not have to be nonnegative! If the initial list already satisfies the maximum stddev, you have to see how many iterations you can "go backwards" and undo the moving average and still have the list satisfy the max stddev. Since we are truncating the windows for the initial n data points and not dropping those, there is enough data to reverse a moving average.
For example, if we start with the list [9.0, 8.99658203125, 8.9932148677634256, 8.9802599114806494, 8.9515728374598496, 8.8857883675880771, 8.7558358356689627] (taken from our earlier example with 3 more moving averages done to it) and the same window size and max stddev, you will output -3 because you can reverse the moving average at most 3 times.
Any reasonable I/O format is fine.
This is code-golf so shortest code in bytes wins!
Test Cases
[9, 2,  4,  4,  5,  5,  7], 3, .5 -> 8
[9, 2,  4,  4,  5,  5,  7], 3, .25 -> 9
[9.0, 8.99658203125, 8.9932148677634256, 8.9802599114806494, 8.9515728374598496, 8.8857883675880771, 8.7558358356689627], 3, .5 -> -3
[1000, 2,  4,  4,  5,  5,  7], 7, .25 -> 13
[1000.0, 999.98477172851563, 999.96956668760447, 999.95438464397, 999.90890377378616, 999.83353739825293, 999.69923168916694], 4, 7 -> -6

Related.

Also related.

Wolfram - 236
Pretty clunky right now, but at least it works.
f[x_,w_,c_]:=Module[{l=Length,d=Sqrt@CentralMoment[#,2]&,n,a,b,t,r},n=Length@x;a=Normalize/@LowerTriangularize@Array[Boole[Abs[#1-#2]<w]&,{n,n}]^2;{b,t,r}=If[d@x>c,{a,d@#>c&,l@#-1&},{Inverse@a,d@#<c&,-l@#+2&}];r@NestWhileList[b.#&,x,t]]

236 bytes, f[x_,w_,c_]:=Module[{l=Length,d=Sqrt@CentralMoment[#,2]&,n,a,b,t,r},n=Length@x;a=Normalize/@LowerTriangularize@Array[Boole[Abs[#1-#2]<w]&,{n,n}]^2;{b,t,r}=If[d@x>c,{a,d@#>c&,l@#-1&},{Inverse@a,d@#<c&,-l@#+2&}];r@NestWhileList[b.#&,x,t]]


text:
Draw Spiral Words
The Scenario
Given an input of ASCII lowercase letters and spaces, draw a spiral of characters that traces the original input of characters excluding spaces.
The Rules
1) The characters shall spiral counterclockwise to the left in an outwardly fashion.  If a left turn is not possible, then move straight.
Given: abcdefg
Output:
  g
baf
cde

2) The characters can spiral into previous characters so long as rule #1 is not violated.  Also, if that character is spiraled into, then that character is uppercased.  Once a character is uppercased, it will stay uppercased regardless of the number of times it is reused.
Given: apples appeal
Output:
PAs
PLe
ea

So if the word keeps into the spiral but violates the next character then the program stops?

I think what makes this a good challenge is you would have to "rewind the stack" so to speak and resume at a point that makes rule #1 always work.

The current wording makes rule 2 seem entirely optional. If it should be compulsory then I think a much more comprehensive test suite is necessary.

What should the output be for input abcdefghab?

JavaScript, 225 221 212 bytes
-9 bytes thanks to Conor O'Brien
Please note that your text cases conflict with each other. Your first test case starts in the middle of the spiral. Your second test case starts in the top middle of the spiral. I went with your first test case, because it was the first one I saw. You haven't edited your question in over a year, so sorry for the presumption.
First Test Case:
9<-8<-7
|     |
2<-1  6
|     |
3->4->5

Second Test Case:
2<-1<-6
|     |
3->4->5
|     |
7->8->9

Without any further adieu, here is the golfed code. I am 100% sure that if the community chips it this could be cut significantly. This returns a multiline array.
s=>eval("s=[...s.replace(/ /g,'')];i=0;k=j=1;a=[[],[],[]];b='00122210';c=b*100+'';for(;;){for(l=0;l<8;l++){if(!s[i])break;if(a[k][j]==s[i])s[i]=s[i].toUpperCase();a[k][j]=s[i];k=b[l];j=c[l];i++}if(!s[i])break}a")

Prettification snippet (prints a multiline string to console). Please note the different in my test case #2 and OP's test case #2 (see above if you have not already):
(if someone with more experience with snippets wants to fix this into HTML input feel free to edit this, I need to go to bed).

f=
s=>eval("s=[...s.replace(/ /g,'')];i=0;k=j=1;a=[[],[],[]];b='00122210';c=b*100+'';for(;;){for(l=0;l<8;l++){if(!s[i])break;if(a[k][j]==s[i])s[i]=s[i].toUpperCase();a[k][j]=s[i];k=b[l];j=c[l];i++;g(a)}if(!s[i])break}a")

//replace argument here to change output
var arr = f("apples appeal");

function g(ar) {
  var str = "";

  for (x = 0; x < 3; x++) {
    for (y = 0; y < 3; y++) {
      str += ar[y][x] || " ";
    }
    str += "\n";
  }
  console.log(str);
}

Ungolfed and Explanation
f=(input)=>{
    //remove spaces
    input = input.replace(/ /g, "");

    //convert to array (so I can uppercase individual letters)
    input = input.split("");

    //position in input
    var pos = 0;

    //positions inside output
    var xPos = 1;
    var yPos = 1;

    //output container (3 rows, 3 columns)
    var arr = [[],[],[]];

    //counterclockwise indexes for x
    var xOrder = "00122210";

    //counterclockwise indexes for y
    //var yOrder = "12221000"
    var yOrder = xOrder * 100 + "";

    //loop infinitely (breaks when input[pos] is undefined)
    for (;;) {
        //loop around circle
        for (var i = 0; i < 8; i++) {
            if (!input[pos]) {
                break;
            }

            //if item already in array equal next item in input, set next item in input to caps before
            if (arr[xPos][yPos] == input[pos]) {
                input[pos] = input[pos].toUpperCase();
            }

            //write or overwrite in array with current from input
            arr[xPos][yPos] = input[pos];

            //increment last because we do not prime our loops
            xPos = xOrder[i];
            yPos = yOrder[i];
            pos++;
        }
        if(!input[pos]) {
            break;
        }
    }
    return arr;
}

a.split("") is equivalent to [...a]; s=>{...;return a;} is equivalent to s=>eval("...;a") (and the ; is optional in the less golfed version); all semicolons followed by a } are optional

@ConorO'Brien thank you :)

What output do you get for the test case apples appeal? I'm seeing ppa eas aLe, which is definitely not correct because there's no l next to the ps.

@PeterTaylor the output is correct, according to the spiral order of the first test case, which I based my program on. The second test case uses a different spiral order (starts on the top). I added a log for each iteration of the snippet. Look at that - it might make more sense.

By the logic of the first test case the output would be eppa apas lple s.

@PeterTaylor you don't spiral out more than 3x3. You replace words already in the 3x3, and capitalize them if they are the same. Re-read OP, #2 rule.

Either you ignore rule 2 entirely, in which case you get the output from my previous comment, or you get the output from the question. Fwiw your interpretation of it is wildly different to mine: I understood it to permit retreading cells which contain the same letter. But because that's not clear I've voted to close.

@PeterTaylor I'm ignoring test case two, not rule two. You're correct that it is unclear, I probably mangled it completely.