text:
Generate Pyramid Scheme code
Pyramid Scheme is a language being developed by @ConorO'Brien. In Pyramid Scheme, the code that you write looks like this:
      ^         ^
     / \       /3\
    /   \      ---
   /  +  \
  ^-------^
 /9\     /3\
/123\    ---
-----

Now, that code has two obvious qualities: It's difficult to parse, and it's difficult to write. Conor has solved the first one, however it will be your job to solve that second issue.

The above code is processed by the PyramidScheme interpreter into a nested string array, like this:
[["+", ["9123", "3"]], "3"]

Your task is to write a program or function, which given a nested array of strings, outputs or returns the recreated PyramidScheme code. You may assume that the input array will always be valid.
A pyramid is an isosceles triangle. The top is ^, the sides slope diagonally away with / and \, and the bottom is -. The two bottom corners are either empty or contain the start of other pyramids, which are arguments. The middle is filled with the pyramid's name, ignoring line breaks.
Here's how the parser converts the code into a useable format. First, it scans for a top-level pyramid. If it takes no arguments, it represents it with a single string and moves on. Otherwise, it represents is as an array ["name",[arg1,arg2]] or ["name",[arg1]]. The arguments are the pyramids at the bottom left and bottom right of the pyramid, which may be either string or more arrays described as above. You may notice that this somewhat resembles Lisp, in which case you may also have noticed the awful pun that is the language name. After the pyramid is fully represented, the parser moves on to the next one.
This is code-golf, shortest code wins!
Test Cases: These are not the only valid outputs, these are example of valid outputs.
[["+", ["9123", "3"]], "3"]

      ^         ^
     / \       /3\
    /   \      ---
   /  +  \
  ^-------^
 /9\     /3\
/123\    ---
-----

[["out", [["chr", ["72"]], ["chr", ["101"]]]], ["out", [["chr", ["108"]]]], ["out", [["chr", ["108"]]]], ["out", [["chr", ["111"]]]]]

        ^      ^     ^     ^
       / \    / \   / \   / \
      /out\  /out\ /out\ /out\
     ^-----^ -----^----- -----^
    / \   / \    / \         / \
   /chr\ /chr\  /chr\       /chr\
  ^----- -----^ -----^     ^-----
 / \         / \    / \   / \
/72 \       /101\  /108\ /111\
-----       -----  ----- -----

[ ["+", [ ["asdfghjkl"], ["do", [ "1" ]] ]] ]

       ^
      / \
     / + \
    /     \
   ^-------^
  /a\     /d\
 /sdf\   /o  \
/ghjkl\ ^-----
-------/1\
       ---

Notice in the second test case, the second and third out pyramid both have a ["chr", ["108"]] as a parameter, which is collapsed into one pyramid stack shared by two top-level ones. This is a valid optimization your code may support, but it is completely optional; scoring is not based on the length of your output.
For the curious, the first case displays 9126 3 due to implicit printing of toplevel pyramids, the second one prints Hello, and the last one is a syntax error, included just because it has a neat structure.

You may assume that the input only contains printable ASCII, excluding spaces, ^, /, \, and -. The input will always be valid, and contain at least one pyramid. There is no limit on the size of the array or the input strings, however you may write your code as if your language's default integer type was infinite precision and that your computer has arbitrary memory. If taking input as a single string, you may use anything reasonable (comma, space, etc. as long as it's in printable ascii and not " or []) to delimit arrays. You do not have to include brackets surrounding the entire thing, and instead take multiple arrays separated by your delimiter.
Your output does not have to be golfed, you may insert extra space or make your pyramids larger than necessary. Toplevel pyramids should be on the first line. Output should be a string with newlines or a list of strings.
Anyone who does include a version of their code which optimally golfs the pyramids may receive some rep in the form of upvotes/bounties (but probably just upvotes).

Sierpinski would love this language.

Totally didn't post this challenge because I'm too lazy to format triangles properly...

@KodosJohnson Input can be a native array.

how can you have a function with more than two arguments?

@DestructibleWatermelon The input will never contain an array such that it will require passing two arguments to a pyramid, as this is impossible in Pyramid Scheme.

huh, so it is actually rather different than lisp aside from ascii art syntax.

@DestructibleWatermelon Not really, Lisp lists with more than two elements are actually stored internally as (a (b ( c (d)))), and Pyramid Lisp has a function which takes two args and returns them as a lsit iirc. (Everything I just said might be wrong)

This is a challenge that I will love to see some good answers for.

Just to recap: the top level array can have any number of elements, while the subarrays will only have 1 or 2. Right?

@edc65 correct.

Since you said that top-level pyramids should be on the first line, does that mean they don't have to be? I mean, could each pyramid be placed under the preceding pyramid?

@KodosJohnson No, they have to be on the first line.

@Pavel, I understand how linked lists work, you know. I think the function you refer to would be cons? If that were the case eval would also be needed I believe

@DestructibleWatermelon I know neither how normal Lisp works, nor how Pyramid Scheme works. I think PS has those functions, but there's not actually a documentation; everything I know comes from reading the interpreter's source.

How should it behave if a string is something like "["]"

@LliwTelracs No need to escape characters. If you want to, you may support that.

Common Lisp - 2524 1890 bytes
(defun f(i)(let((s(loop as r in i collect(g r)))(n())(output""))(loop until n do(setf n T)(loop as r in s do(if(cdr r)(progn(setf output(c output(e r))(cdr r)(cdr(cdr r)))(setf n()))(setf output(c output(b(car r))))))(setf output(c output(format()"~%"))))output))(defun g(r)(if(stringp r)(d(m(length r))r)(if(<(length r)2)(d(m(length(car r)))(car r))(if(=(length(e r))1)(let((h(g(car(e r))))(p(d(m(length(car r)))(car r))))(let((o(+ 1(position #\^(e h))))(parent_length(car p)))(if(<(-(car h)o)parent_length)(l(cons(+ o parent_length)())(loop as n in(butlast(cdr p))collect(c(b o)n))(cons(c(subseq(e h)0 o)(car(last p)))())(loop as n in(cdr(cdr h))collect(c n(b (- parent_length(-(car h)o))))))(let((i(-(- o 1)parent_length)))(l(cons(car h)())(loop as n in(butlast(cdr p))collect(c(b o)n(b i)))(cons(c(subseq(nth 1 h)0 o)(car(last p))(b i))())(cddr h))))))(let((l-h(g(car(e r))))(r-h(g(e(e r)))))(let((ll(position #\^(e l-h)))(rl(position #\^(e r-h))))(let((lr(-(car l-h)ll 1))(rr(-(car r-h)rl 1)))(let((p(d(max(m(length(car r)))(ceiling(+ lr rl)2))(car r))))(let((m-pad(if(>(car p)(+ lr rl))(-(car p)lr rl)0)))(l(cons(+ ll 1(car p)1 rr)())(loop as n in(butlast(cdr p))collect(c(b(+ 1 ll))n(b(+ 1 rr))))(cons(c(subseq(e l-h)0(+ 1 ll))(car(last p))(subseq(e r-h)rl))())(loop as y in(append(cddr l-h)(make-list(length l-h):initial-element(b(car l-h))))as z in(append(cdr(cdr r-h))(make-list(length r-h):initial-element(b(car r-h))))collect(c y(b m-pad)z))))))))))))(defun d(r n)(cons(+(* 2 r)1)(l(cons(c(b r)"^"(b r))())(loop as i from 1 to r collect(c(b(- r i))"/"(subseq(c n(b(expt i 2)))(expt(- i 1)2)(expt i 2))"\\"(b(- r i))))(cons(make-string(+ 1(* 2 r)):initial-element #\-)()))))(defun m(l)(+ 1(floor(sqrt l))))(defun b(n)(make-string n :initial-element #\space))(defun c(&rest a)(apply 'concatenate 'string a))(defun l(&rest a)(apply 'concatenate 'list a))(defun e(tree)(nth 1 tree))

Thanks to @coredump for a number of golfing tricks.  Sample output from the question:
> (f '(("out" (("chr" ("72")) ("chr" ("101")))) ("out" (("chr" ("108")))) ("out" (("chr" ("108")))) ("out" (("chr" ("111"))))))
          ^               ^          ^          ^
         /o\             /o\        /o\        /o\
        /ut \           /ut \      /ut \      /ut \
       /     \         ^-----     ^-----     ^-----
      /       \       /c\        /c\        /c\
     ^---------^     /hr \      /hr \      /hr \
    /c\       /c\   ^-----     ^-----     ^-----
   /hr \     /hr \ /1\        /1\        /1\
  ^-----    ^-----/08 \      /08 \      /11 \
 /7\       /1\    -----      -----      -----
/2  \     /01 \
-----     -----

> (f '( ("+" ( ("asdfghjkl") ("do" ( "1" )) )) ))
          ^
         /+\
        /   \
       /     \
      /       \
     /         \
    ^-----------^
   /a\         /d\
  /sdf\       /o  \
 /ghjkl\     ^-----
/       \   /1\
---------  /   \
           -----

> (f '(("+" ("9123" "3")) "3"))
       ^        ^
      /+\      /3\
     /   \    /   \
    /     \   -----
   ^-------^
  /9\     /3\
 /123\   /   \
/     \  -----
-------

Here is the original, (mostly) ungolfed version:
(defun f (input)
    (let ((trees (loop for tree in input collect (g tree)))
          (done nil)
          (output ""))
        (loop while (not done)
            do  (setf done T)
                (loop for tree in trees
                    do  (if (cdr tree)
                            (progn
                                (setf output (conStr output (car (cdr tree))))
                                (setf (cdr tree) (cdr (cdr tree)))
                                (setf done nil))
                            (setf output (conStr output (blank (car tree))))))
                (setf output (conStr output  (format nil "~%"))))
        output))

;creates a single tree
;output is a list, first element is the length of each line, the rest are the lines of text
(defun g (tree)
    (if (stringp tree)
        ;strings should be drawn as just the pyramid for the name
        (draw-body (min-rows (length tree)) tree)

        (if (< (length tree) 2)
            ;lists with no arguments should be drawn as just the pyramid for the name
            (draw-body (min-rows (length (car tree))) (car tree))
            (if (= (length (car (cdr tree))) 1)
                ;single child
                (let ((child (g (car (car (cdr tree))))) (parent (draw-body (min-rows (length (car tree))) (car tree))))
                    (let ((parent_offset (+ 1 (position #\^ (first-line child)))) (parent_length (car parent)))
                        (if (< (- (car child) parent_offset) parent_length)
                            (let ((child-fill (- parent_length (- (car child) parent_offset))))
                                (concatenate 'list
                                    (cons (+ parent_offset parent_length) nil)
                                    (loop for line in (butlast (cdr parent))
                                        collect (conStr (blank parent_offset) line))
                                    (cons (conStr (subseq (nth 1 child) 0 parent_offset) (car (last parent))) nil)
                                    (loop for line in (cdr (cdr child))
                                        collect (conStr line (blank child-fill)))))
                            (let ((parent-fill (- (- parent_offset 1) parent_length)))
                                (concatenate 'list
                                    (cons (car child) nil)
                                    (loop for line in (butlast (cdr parent))
                                        collect (conStr (blank parent_offset) line (blank parent-fill)))
                                    (cons (conStr (subseq (nth 1 child) 0 parent_offset) (car (last parent)) (blank parent-fill)) nil)
                                    (cdr (cdr child)))))))
                ;two children
                (let ((l-child (g (car (car (cdr tree))))) (r-child (g (car (cdr (car (cdr tree)))))))
                    (let ((lc-l-width (position #\^ (first-line l-child))) (rc-l-width (position #\^ (first-line r-child))))
                        (let ((lc-r-width (- (car l-child) lc-l-width 1)) (rc-r-width (- (car r-child) rc-l-width 1)))
                            (let ((parent (draw-body (max (min-rows (length (car tree))) (ceiling (+ lc-r-width rc-l-width) 2)) (car tree))))
                                (let ((m-pad (if (> (car parent) (+ lc-r-width rc-l-width))
                                            (- (car parent) lc-r-width rc-l-width)
                                            0)))
                                    (concatenate 'list
                                        (cons (+ lc-l-width 1 (car parent) 1 rc-r-width) nil)
                                        (loop for line in (butlast (cdr parent))
                                            collect (conStr (blank (+ 1 lc-l-width)) line (blank (+ 1 rc-r-width))))
                                        (cons (conStr (subseq (first-line l-child) 0 (+ 1 lc-l-width)) (car (last parent)) (subseq (first-line r-child) rc-l-width)) nil)
                                        (loop for left in (append (cdr (cdr l-child)) (make-list (length l-child) :initial-element (blank (car l-child))))
                                            for right in (append (cdr (cdr r-child)) (make-list (length r-child) :initial-element (blank (car r-child))))
                                            collect (conStr left (blank m-pad) right))))))))))))

;create a single pyramid
; output is a list, first element is the length of each line, the rest are the lines of text
(defun draw-body (rows name)
    (print rows)
    (print name)
    (cons (+ (* 2 rows) 1)
        (concatenate 'list (cons (conStr (blank rows) "^" (blank rows)) nil)
            (loop for i from 1 to rows
                collect (conStr (blank (- rows i)) "/" (subseq (conStr name (blank (expt i 2))) (expt (- i 1) 2) (expt i 2)) "\\" (blank (- rows i))))
            (cons (make-string (+ 1 (* 2 rows)) :initial-element #\-) nil))))

(defun min-rows (l)
    (+ 1 (floor (sqrt l))))

(defun blank (n)
    (make-string n :initial-element #\space))

(defun conStr (&rest args)
    (apply 'concatenate 'string args))

(defun first-line (tree)
    (car (cdr tree)))

Try it Online!

You should be able to golf off a lot of bytes by removing unnecessary spaces.

Welcome to PPCG and nice first answer!

Some tips for golfing CL: in loops, "for" can also be written "as"; you can remove spaces before and after parentheses and double-quotes; you can replace NIL by (); you can also use reader variables, sometimes

... loop while (not x) is loop until x, (cdr (cdr x)) is (cddr x), (setf a b c d) is shorter than (setf a b) followed by (setf c d), etc. But this is already a good answer

Azor1 holy cow! Nice job. If nobody answers then you will get a 50 rep bounty from me. Try and golf as much as you can!

I don't know common lisp, so maybe I'm doing it wrong, but it seems to be off a little: https://gist.github.com/pavelyay/dd7eea5c0dc8713b1327608ab9e780f7 (The link is in the gist, it's too long to fit in a comment)

try using (format t "~d" ___) instead of (print ___). I think print outputs the text as lisp code, so the quotes are present and the backslashes need escaping whereas format prints the actual content.

In addition to the +50 bounty, the fact that you posted this amazing answer will get another bounty from me.

@NoOneIsHere you being for real? If so that is pretty cool

@ChristopherPeart Depending on what happens the next 2 days, I was thinking +200-+300. This is a very challenging problem.

You wrote (cdr(cdr r)). Isn't (cddr r) same thing but shorter?

@NoOneIsHere yeah I took one look and started nopeing out. It is a cool problem and deserves a lot of rep.

@PrzemysławP yea it is, I must have missed it when I was golfing

@Azor1 congratz! +50 rep

A total bounty of 350 reputation is significant... but this answer deserves it. A Common Lisp answer to a question about constructing questions for a Lisp dialect... Wow.

This is kinda late, but I found three (cdr(cdr ...))s in your code.

@Qwerp-Derp They are present in the ungolfed code, but the golfed code uses cddr.

@Phoenix There are still (cdr(cdr t)) in the golfed code.

@Qwerp-Derp Huh, I'm blind then, I went threw it a couple times yesterday...

Python 3, ~41.3KB + tests and examples
So, I didn't realise this was a challenge, and I wrote a whole language which compiles into Pyramid scheme...  It's called psll, and you can find it here. It has a bunch of bells and whistles, syntactic sugar constructs: functions (kinda) and strings, compiler optimisation etc.
This is not exactly a competing answer, but I feel it's heavily relevant so I should post it here.


text:
Is this Sequence Graphic?
A graphic sequence is a sequence of positive integers each denoting the number of edges for a node in a simple graph.  For example the sequence 2 1 1 denotes a graph with 3 nodes one with 2 edges and 2 with one connection.
Not all sequences are graphic sequences. For example 2 1 is not a graphic sequence because there is no way to connect two nodes so that one of them has two edges.

Task
You will take a sequence of integers by any reasonable method.  This includes, but is not limited to, an array of integers and its size, a linked list of unsigned integers, and a vector of doubles.  You may assume that there will be no zeros in the input.  You may also assume the input is sorted from least to greatest or greatest to least.
You must output whether or not the sequence is a graphic sequence.  A truthy value if it is a falsy value otherwise.

Goal
This is code-golf the goal is to minimize the number of bytes in your program
Testcases
Sorted greatest to least
                  -> True
3 3 3 2 2 2 1 1 1 -> True
3 3 2 2 1 1       -> True
3 3 2             -> False
8 1 1 1 1 1 1 1 1 -> True
1 1 1 1           -> True
1 1 1             -> False
9 5 4             -> False

Can we assume that the input list will be non-empty?

@PeterTaylor If you want you can take a string of 0s for the empty sequence

Mathematica, 25 bytes
<<Combinatorica`
GraphicQ

Yeah, another builtin. (Takes the input as a list of positive integers.) Requires loading the Combinatorica package.

Python 2 (exit code), 53 bytes
l=input()
while any(l):l.sort();l[~l[-1]]-=1;l[-1]-=1

Try it online!
Outputs via exit code.
Uses a version of the Havel-Hakimi algorithm. Repeatedly decrements both the largest element k and the k'th largest element (not counting k itself), which corresponding to assigning an edge between the two vertices with those degrees. Terminates successfully when the list becomes all zeroes. Otherwise, if there's an index out of bounds, fails with error. Any negative values created also eventually lead to an out-of-bounds error.

CJam (20 bytes)
{{W%(Wa*.+$_0a<!}g!}

Online test suite including a couple of extra tests I added to catch bugs in some of my attempts.
This is an anonymous block (function) which takes an array of integers on the stack and leaves 0 or 1 on the stack. It assumes that the input is sorted ascending.
The input array may not be empty, but may contain zeroes, in accordance with OP's answer to my query on the subject of empty inputs.
Dissection
This follows OP's answer in implementing the Havel-Hakimi algorithm.
{          e# Define a block
  {        e#   Do-while loop (which is the reason the array must be non-empty)
           e#     NB At this point the array is assumed to be non-empty and sorted
    W%     e#     Reverse
    (Wa*.+ e#     Pop the first element and subtract 1 from that many subsequent
           e#     elements. If there aren't enough, it adds -1s to the end. That's
           e#     the reason for using W (i.e. -1) and .+ instead of 1 and .-
    $      e#     Sort, restoring that part of the invariant
    _0a<!  e#     Continue looping if array >= [0]
           e#     Equivalently, break out of the loop if it starts with a negative
           e#     number or is empty
  }g
  !        e#   Logical not, so that an empty array becomes truthy and an array
           e#   with a negative number becomes falsy
}

Haskell, 102 98 95 94 bytes
import Data.List
f(x:r)=length r>=x&&x>=0&&(f.reverse.sort$take x(pred<$>r)++drop x r)
f x=1<3

Try it online!
Usage: f [3,3,2,2,1,1], returns True or False. Assumes that the input contains no zeros and is sorted in descending order, as allowed in the challenge.
Explanation:
import Data.List          -- import needed for sort
f (x:r) =                 -- x is the first list element, r the rest list
  length r >= x           -- the rest list r must be longer or equal x
  && x >= 0               -- and x must not be negative
  && (f .                 -- and the recursive call of f
      reverse . sort $    --    with the descendingly sorted list
      take x(pred<$>r)    --    of the first x elements of r subtracted by 1
      ++ drop x r         --    and the rest of r
     )                    -- must be true
f [] = True               -- if the list is empty, return True

Edit: This seems to follow the Havel-Hakimi mentioned in other answers, though I did not know of this algorithm when writing the answer.

length r < x is not quite right as [1,0] will return true, but there is no simple graph with 2 nodes with one and zero edges.

@JonathanAllan You're right, but the challenge states "You may assume that there will be no zeros in the input."

Oh right, that seems like a strange decision as it does not fit with the definition.

@JonathanAllan I changed it to handle those cases as well, and even saved 4 bytes by doing so.

That's good! :D

Python 2, 108 bytes
Here is my implementation in Python.  I'm sure it can be beaten by a more experienced golfer or mathematician.  It implements the Havel-Hakimi algorithm.
def f(x):p=x[0]+1;x=sorted(x+[0]*p)[::-1];return~x[-1]and(p<2or f(sorted([a-1for a in x[1:p]]+x[p:])[::-1]))

Try it online!

[2,1,1] returns True but [1,1,2] returns 0 - EDIT: just saw that your spec said you can assume it's sorted (I had seen the test case 9 4 5).

Jelly, 12 bytes
ṢṚḢ-€+ƊƊƬ>-Ȧ

A monadic Link accepting a list which yields 1 if the answers are consistent otherwise  0.
Try it online! Or see the test-suite.
How?
ṢṚḢ-€+ƊƊƬ>-Ȧ - Link: list of integers
        Ƭ    - collect up while results change:
       Ɗ     -   last three links as a monad i.e. f(L):
Ṣ            -     sort                      [min(L),...,max(L)]
 Ṛ           -     reverse                   [max(L),...,min(L)]
      Ɗ      -     last three links as a monad i.e. f([a,b,c,...,x]):
  Ḣ          -       pop head                          a
   -€        -       -1 for each                       [-1,-1,...,-1] (length a)
     +       -       add to head result (vectorises)   [b-1,c-1,...,x-1,-1,-1,...]
         >-  - greater than -1? (vectorises)
           Ȧ - Any and all? (0 if empty or contains a 0 when flattened, else 1)

R, 20 bytes
igraph::is_graphical

Mathematica isn't the only language with built-ins! ;-)
The igraph package needs to be installed. Takes input as a vector of integers.

05AB1E, 26 25 bytes
D0*«¹v{R¬U¦X¹gn‚£`s<ì}0QP

Try it online!
Explanation
D0*«                       # extend the input list with as many zeroes as it has elements
    ¹v                     # len(input) times do:
      {R                   # sort in descending order
        ¬U¦X               # extract the first element of the list
            ¹gn‚           # pair it with len(input)^2
                £          # partition the list in 2 parts, the first the size of the
                           # extracted element, the second containing the rest of the list
                 `         # split these list to stack (the second on top)
                  s<       # decrement the elements of the first list by 1
                    ì      # prepend it to the rest of the list
                     }     # end loop
                      0Q   # compare each element in the resulting list with 0
                        P  # reduce list by multiplication

JavaScript (ES6), 82 80 76 bytes
f=([$,..._])=>1/$?_.length>=$&$>=0&f(_.map(a=>a-($-->0)).sort((a,b)=>b-a)):1

Thanks to ETHproductions for saving many bytes!
Usage
f=([$,..._])=>1/$?_.length>=$&$>=0&f(_.map(a=>a-($-->0)).sort((a,b)=>b-a)):1
f([3,3,3,2,2,2,1,1,1])

Output
1

You can replace map((a,b)=>b<$?a-1:a) with map(a=>a-($-->0)) to save 4 bytes.

Ruby, 90 bytes
Ported from this question which turned out to be a duplicate of this. Uses Havel-Hakimi since that was the one mentioned in that question.
->a{b=1;(a.sort_by!(&:-@);i=a.shift;a.map!{|e|i>0&&e>0?(i-=1;e-1):e};b&&=i<1)while[]!=a;b}

Try it online!

05AB1E, 19 bytes
[D{RćD1‹#Å0<0ζO})dW

Port of JonathanAllan's Jelly answer, so make sure to upvote him!!
Try it online or verify all test cases.
Explanation:
[            # Start an infinite loop:
 D           #  Duplicate the current list
             #  (which is the implicit input-list in the first iteration)
  {R         #  Sort it from highest to lowest
    ć        #  Extract the head; pop and push the remainder and head
     D1‹     #  If the head is 0 or negative:
        #    #   Stop the infinite loop
     Å0<     #  Create a list of the head amount of -1
        0ζ   #  Zip/transpose it with the remainder list, with 0 as filler
          O  #  Sum each pair
})           # After the loop: wrap everything on the stack into a list
  d          # Check for each value if it's non-negative (>= 0)
             # (resulting in 1/0 for truthy/falsey respectively)
   W         # Get the flattened minimum (so basically check if none are falsey)
             # (which is output implicitly as result)

Stax, 14 12 bytes
ε▼ü*æε<%)4‼♂

Run and debug it
This program handles empty and unsorted inputs.

source: Stack Exchange

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

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

sort: votes


text:
Alternating Power Fibonacci Sequence
Definition
The Alternating Power Fibonacci Sequence is formed as follows.

Start with the empty sequence and set n to 1.
Compute fn, the nth non-negative Fibonacci number, with repetitions.
0 is the first, 1 is the second and the third, 2 is the fourth. All others are obtained by summing the two previous numbers in the sequence, so 3 = 1 + 2 is the fifth, 5 = 2 + 3 is the sixth, etc.
If n is odd, change the sign of fn.
Append 2n-1 copies of fn to the sequence.
Increment n and go back to step 2.

These are the first one hundred terms of the APF sequence.
 0  1  1 -1 -1 -1 -1  2  2  2  2  2  2  2  2 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3
-3 -3 -3 -3 -3 -3  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
 5  5  5  5  5  5  5  5  5  5  5  5  5 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
-8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8

Task
Write a full program or a function that takes a positive integer n as input and prints or returns the nth term of the APF sequence.
If you prefer 0-based indexing, you can alternatively take a non-negative integer n and print or return the APF number at index n.
This is code-golf; may the shortest code in bytes win!
Test cases (1-based)
    1 ->    0
    2 ->    1
    3 ->    1
    4 ->   -1
    7 ->   -1
    8 ->    2
  100 ->   -8
  250 ->   13
  500 ->  -21
 1000 ->   34
11111 ->  233
22222 -> -377
33333 ->  610

Test cases (0-based)
    0 ->    0
    1 ->    1
    2 ->    1
    3 ->   -1
    6 ->   -1
    7 ->    2
   99 ->   -8
  249 ->   13
  499 ->  -21
  999 ->   34
11110 ->  233
22221 -> -377
33332 ->  610

Are there any constraints for n?

As long as your algorithm works for arbitrarily large values of n, you can assume that it fits into your data type.

Does this have an OEIS number?

@Mindwin It does not.

Jelly, 5 bytes
BLCÆḞ

Try it online!
How?
Extending the Fibonacci series back into negative indexes such that the relation f(i) = f(i-2) + f(i-1) still holds:
  i   ...   -8  -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   4   5 ...
f(i)  ...  -21  13  -8   5  -3   2  -1   1   0   1   1   2   3   5   8 ...

Going back from i=0 the numbers are those we need to repeat 2n-1 times, and Jelly's Fibonacci built-in, ÆḞ, will calculate these.
We can find the -i (a positive number) that we need by taking the bit-length of n and subtracting 1.
Since we want i (a negative number) we can instead perform 1-bitLength and Jelly has an atom for 1-x, C, the complement monad.
BLCÆḞ - Main link: n               e.g.  500
B     - convert n to a binary list      [1,1,1,1,1,0,1,0,0]
 L    - get the length                   9
  C   - complement                      -8
   ÆḞ - Fibonacci                       -21

I knew there was a shorter way but not by that much, thought it'd be 7 bytes with a way to remove µ and ⁸

Your repeated negation was clever though, I was looking at powers of minus one, which adds a couple of bytes, until I recalled about the negative Fibonacci values and tried plugging them into Jelly's monad.

Honestly, I'm surprised Jelly doesn't have a one-byte builtin to get the binary length of a number...

Python 2, 30 bytes
f=lambda n:n<1or f(n/4)-f(n/2)

Try it online!
One-indexed.
The sequence felt like a puzzle, something that Dennis generated by having a short way to express it. The power-of-two repetitions suggest recursing by bit-shifting (floor-dividing by 2). The alternating-sign Fibonacci recursion f(n)=f(n-2)-f(n-1) can be adapted to bitshift in place of decrementing. The base case works out nicely because everything funnels to n=0.

Mathematica, 43 36 24 bytes
Fibonacci@-Floor@Log2@#&

7 bytes saved thanks to @GregMartin, and a further 12 thanks to @JungHwanMin.

You can save a few bytes with Floor@Log2@#, and by writing Fibonacci[t=...] (and by removing the spaces in the last exponent).

-12 bytes: Fibonacci@-Floor@Log2@#& -- Fibonacci can take negative arguments too (takes care of the sign for you).

MATL, 19 17 16 11 bytes
lOiB"yy-]x&

Input is 1-based.
Try it online! Or verify all test cases.
How it works
For 1-based input n, let m be the number of digits in the binary expansion of n. The n-th term in the output sequence is the m-th term in the Fibonacci sequence, possibly with its sign changed.
One idea would be to iterate m times to compute terms of the Fibonacci sequence. This is easy with a for each loop using the array of binary digits. If the Fibonacci sequence were initiallized with 0, then 1 as usual, iterating m times would result in m+2 terms on the stack, so the top two numbers would have to be deleted. Instead, we initiallize with 1, then 0. That way the next generated terms are 1, 1, 2, ... and only one deletion is needed.
The sign could be dealt with by using another loop to change sign m times. But that's costly. It is better to integrate the two loops, which is done simply by subtracting instead of adding in the Fibonacci iteration.
l       % Push 1
O       % Push 0
iB      % Input converted to binary array
"       % For each
  yy    %   Duplicate top two elements
  -     %   Subtract. This computes the new Fibonacci term with the sign changes
]       % End
x       % Delete top number
&       % Specify that implicit display should take only one input
        % Implicitly display the top of the stack

Python 2, 83 82 79 bytes
def f(n,a=0,b=1):
 l=bin(n)[2:]
 for _ in l:a,b=b,a+b
 return a*-(len(l)%2or-1)

Try it online!

Whitespace not required at or -1.

JavaScript (ES6), 33 bytes
f=(n,p=1,c=0)=>n?-f(n>>1,c,p+c):p

1-indexed.
A port of xnor's answer would be 23:
f=n=>n<1||f(n/4)-f(n/2)

05AB1E, 11 10 bytes
Uses 1-based indexing
05AB1E's Fibonacci function returns positive fib numbers less than n, meaning we'd have to generate more than necessary, get the correct one by index and then calculate the sign. So I doubt any method based around that will be shorter than calculating the numbers iteratively.
Uses the realisation that we can initialize the stack with 1, 0 reversed to handle the case when n=1 as described in Luis Mendo's MATL answer.
XÎbgG‚D«`-

Try it online!
Explanation
X             # push 1
 Î            # push 0 and input
  b           # convert input to binary
   g          # get length of binary number
    G         # for N in [1...len(bin(input))-1] do:
     ‚        # pair the top 2 elements of the stack in a list
      D       # duplicate the list
       «      # concatenate the 2 lists together
        `     # split into separate elements on the stack
         -    # subtract the top 2 elements

Jelly, 9 bytes
BLµ’ÆḞN⁸¡

Uses one-based indexing.
Try it online!
Explanation
This method works if your Fibonacci function only supports non-negative arguments.
BLµ’ÆḞN⁸¡  Input: integer n
B          Binary digits of n
 L         Length. len(bin(2)) = floor(log2(n)))
  µ        Start new monadic chain on x = len(bin(2))
   ’       Decrement
    ÆḞ     Get Fibonacci(x-1)
       ⁸¡  Repeat x times on that
      N      Negate.
           Return Fibonacci(x-1) if x is even else -Fibonacci(x-1)

Japt, 6 bytes
Mg1-¢l

Test it online!
How it works
As mentioned in other answers, the nth term in the alternating-sign Fibonacci series is the same as the -nth term in the regular series. n can be found by taking the bit-length of the input and subtracting one; negating this results in 1 minus the bit-length.
Mg1-¢l
    ¢l  // Calculate the length of the input in binary.
  1-    // Subtract this from 1.
Mg      // Get the Fibonacci number at this index.

Perl 6, 53 bytes
{flat(((0,1,*+*...*)Z*|<-1 1>xx*)Zxx(1,2,4...*))[$_]}

Straightforward implementation of the sequence, the way it was described.
Zero-based.

Julia 0.5, 19 bytes
!n=n<1||!(n/=4)-!2n

Try it online!
How it works
This uses the same formula as @xnor's Python answer. The recurrence relation
g(n) = g(n-2) + g(n-1) generates the negative terms of the Fibonacci sequence, which equal the positive terms with alternating signs. From anywhere in a run of 2k repetitions of the same number, we can pick any repetition of the previous run of 2k-1 numbers and the run of 2k-2 numbers before those by dividing the index by 2 and 4.
Rather than the straightforward
f(n)=n<1||f(n÷4)-f(n÷2) # 25 bytes

we can redefine an operator for our purposes. Also, f will work just as fine with floats, so we get
!n=n<1||!(n/4)-!(n/2)   # 21 bytes

Finally, if we update n with a division by 4, wwe can write n/2 as 2n and omit a pair of parens, leading to the 19-byte function definition in this answer.

J, 18 bytes
(%>:-*:)t.@<:@#@#:

Uses one-based indexing. Takes an input integer n > 0 and computes floor(log2(n)) by finding the length of its binary representation and then decrements that value by one. It then finds the floor(log2(n))-1th coefficient of the generating function x/(1 + x - x2) which is the g.f for the negative-indexed Fibonacci values.
Try it online!
Explanation
(%>:-*:)t.@<:@#@#:  Input: integer n
                #:  Binary
              #@    Length
           <:@      Decrement
(      )            The generating function x/(1+x-x^2)
  >:                  Increment x
     *:               Square x
    -                 Subtract
 %                    Divide x by previous
        t.          Get series coefficient at the index given by previous value

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


text:
Hold'em or Fold'em?
Your friend invited you to a high-stakes poker game at the last minute and, as a computer scientist, you've decided to use your skills to gain an edge on the game. Your task will be, given 2 cards (your hand) and 0, 3, 4 or 5 cards (the dealt cards), you must decide what the best possible hand you can get will be. If all 7 cards are given as arguments, the answer is pretty clear. If given less, the problem becomes more complex. However, this isn't quite enough to give you the edge you're looking for, you must also calculate the best possible hand from the remaining cards to understand what your opponents could have as well.

Hold'em Refresher
If you don't know about hold'em, each player in the game starts with 2 cards as their 'hand'. Over the course of 3 'turns', additional cards are revealed to be shared between all players. The first turn, 3 cards are revealed. The second, 1 more, and the third time a final card is revealed. The two cards given first represent your hand, while the latter represents 0, 3, 4, or 5 cards given by the successive turns.

Possible Numbers:
[2,3,4,5,6,7,8,9,T(10),J,Q,K,A]

Possible Suits:
[S,C,H,D]

Full Deck:
[2S,3S,4S,5S,6S,7S,8S,9S,TS,JS,QS,KS,AS, # Spades.
 2C,3C,4C,5C,6C,7C,8C,9C,TC,JC,QC,KC,AC, # Clubs.
 2H,3H,4H,5H,6H,7H,8H,9H,TH,JH,QH,KH,AH, # Hearts.
 2D,3D,4D,5D,6D,7D,8D,9D,TD,JD,QD,KD,AD] # Diamonds.

Hand Rankings:
1:Royal Flush    (A-K-Q-J-10, all from the same suit).
2:Straight Flush (Sequential cards, all from the same suit).
3:Four-of-a-Kind (Self explanatory).
4:Full House     (3-of-a-kind and a 2-of-a-kind).
5:Flush          (All cards are from the same suit).
6:Straight       (Sequential Cards, any suits).
7:3-of-a-Kind    (Self explanatory).
8:2-Pair         (Double 2-of-a-Kind).
9:Pair           (2-of-a-Kind).
10:High Card     (You have absolutely nothing except a single card).

Lets take an example or two and walk through them:
The simple example:
[AS, AC],[AH,AD,9S,9C,9H] -> 3 (Four-of-a-Kind), 3 (Four-of-a-Kind)
The best possible hand you'll have in this setup is the four of a kind hand. The best possible hand your opponents could have is also a 4-of-a-Kind, as you cannot have a KQJ10 in their 2-card hands.

[5C,2C],[6C,4C,JH,JD] -> 2 (Straight Flush), 3 (4-of-a-Kind)
You're at risk for a straight flush, but because you have the 2/5C in your hand, nobody else is due to you holding both middle cards. The best they can hope for is having 2 pocket Jacks and getting a Jack on the flop.

[JS,JC],[] -> 1 (Royal Flush), 1 (Royal Flush)
No information you can use against them has been given, all you can tell at the moment is that they can only have a royal flush in diamonds/hearts, but it's just as possible that you get the royal flush as they do. In fact, all inputs where the flop has yet to happen should result in a 1-1 answer.

[2C,4S],[3C,7S,9D,AH,JD] -> 10 (High Card), 7 (3-of-a-Kind)
This is an example of where you're absolutely screwed, and there's no possibility of a straight or a flush given the river. Meaning the best hand here is pocket aces resulting in a 3-of-a-Kind.

I/O Requirements

Input must be separated between what is in your hand and what is public knowledge; it'll likely be easier this way regardless of implementation.

Cards can be tuples or strings, up to you.
The Hand and the Playing Field can be arrays or delimited strings.

Output must be two indexes from the list of hands I've provided (E.G. [2,1]).

It may be returned as part of a function, printed to console or output in a suitable manner.
There must be two distinct values, one for your best hand, another for the best possible.

10 may be represented as a T or as 10, whichever makes sense for you.
Standard loopholes are disallowed.

Winning Criteria

This is code-golf, lowest byte-count with a tie-breaker of post date.

It's superfluous, and I removed it. It doesn't really add anything, and most people comment below anyway.

Shouldn't there only be one of A and 1 in the possible allowed cards? Also I don't think there is really a compelling reason to require the face abbreviations over numeric values like 11.

Related: http://codegolf.stackexchange.com/q/25056/47022, http://codegolf.stackexchange.com/q/6494/47022 and http://stackoverflow.com/q/3364869/4748017

I've never seen a deck with an A and a 1. Everything else looks good.

For us non-Poker-players, please explain in the question that the second group of cards are shared between you and your opponent, whereas they have their own two cards that you can't see. A quick glossary defining the terms pocket, flop, and river would be helpful.

Also helpful: explaining the whole sequence of a round. (Each player starts with two cards known only to them, then three cards are dealt face-up, then a fourth, then a fifth, at which point each player forms a "hand" from any five cards out of the seven visible to them.) It might not be clear to someone why there are seven cards but a hand consists of five.

In your second example (i.e. [10H,10C],[AH,9C,JC]), shouldn't it output 2(Straight Flush), 2(Straight Flush) ? Imagine your opponent has [8C,7C] in his hand, then the flop might be [6C] and the river [5C], which would give him the following straight flush : [5C,6C,7C,8C,9C].

Fixed all of those problems, jeez... Thanks sandbox Obama.

The player can't have a Straight Flush anymore in your 2nd example. (Even with QC at the river, he will still need 8C or KC.)

@Arnauld man, I can't even do examples right, this problem will be hard to program haha.

[2C,4S],[3C,7S,9D,AH,JD] should be (10,6) since the other player can get a straight with an 8 and a 10

Haskell, 433 430 425 bytes
-5 bytes thanks to @Laikoni
import Data.List
q="23456789TJQKA"
e=elem
l=length
b=map
r p|z,elem 'A'u,elem 'K'u=1|z=2|e 4t=3|v<3=4|w=5|y=6|e 3t=7|v<4=8|v<5=9|1>0=10where u=[n!!0|n<-p];v=l$nub u;t=b(\n->l[x |x<-u,x==n])q;w=all(==(last$p!!0))[last s|s<-p];y=elem""[u\\s|s<-b(take 5.flip drop('A':q))[0..10]];z=y&&w
0%_=[[]]
n%(x:y)=b(x:)((n-1)%y)++n%y
_%_=[]
h#t|let p=h++t;c i=minimum$b r$concat$b(5%)$b(++i)((7-l i)%([n:[s]|n<-q,s<-"SCHD"]\\p))=(c p,c t)

Try it online!
Ungolfed (same idea, slightly different structure):
import Data.List -- for (\\)
numbers = "23456789TJQKA"

e=elem

rank_hand hand
    |royal_flush=1
    |straight_flush=2
    |four_of_a_kind=3
    |full_house=4
    |flush=5
    |straight=6
    |three_kind=7
    |two_pair=8
    |pair=9
    |1>0=10
    where nums = [head n | n<-hand]
          unique = length $ nub nums
          counts = map (\n->length [x | x<-nums, x==n]) numbers
          pair = unique < 5
          two_pair = unique < 4 -- could also be 3 of a kind, but that's ok
          three_kind = e 3 counts
          flush = all (==(last$hand!!0)) [last s|s<-hand]
          straight = elem "" [nums\\s | s <- map (take 5.flip drop ('A':numbers))[0..10]]
          full_house = unique < 3
          four_of_a_kind = e 4 counts
          straight_flush = straight && flush
          royal_flush = straight_flush && elem 'A' nums && elem 'K' nums

-- taken from https://codegolf.stackexchange.com/a/34496/66460
-- k%l finds combinations of size k from a list l
0%_=[[]]
n%(x:y)=map(x:)((n-1)%y)++n%y
_%_=[]

-- find every combination available to each player, and rank each one.
-- could be golfed a lot more.
h#t=let p=h++t
        a=[n:[s]|n<-numbers,s<-"SCHD"]\\p
        c i=minimum $ map rank_hand $ concat $ map (5%) $ map (++i) ((7-length i)%a)
    in(c p,c t)

Very slow, since there's no special casing at all (e.g. if no cards have been shown, a royal flush is always possible.) Most of my golfing effort went into the rank_hand function; # can be golfed a lot more by combining maps and such.
hand#table calculates the optimal scores for you and your opponent. Does no error checking.

I think you forgot to s/elem/e/g after defining e=elem, so that should save you 9ish bytes. I think you can also remove some spaces, particularly where identifiers follow numbers directly

@JulianWolf I'm still new to Haskell, but for some reason it looks like e=elem inferred type Int->Bool so it wasn't compiling when I used e for non-integer elem calls. I'm trying to figure out why what was. Thanks for the tip on the spaces!

Ah, you're right. Haskell has trouble inferring polymorphic types sometimes—not sure off the top of my head whether there's an easy fix, beyond adding the flexible types flag

h#t=let[...]in[...] can be shortened to h#t|let[...]=[...]. Also head n is n!!0. In a guard && can simply be ,.


text:
One 1, Two 1's, One 2 One 1
Challenge:
Create a program that takes input of a positive non-zero integer and outputs the 4 next numbers in the sequence described below.
Note: Checking if the input is actually a positive non-zero integer is not necessary
Sequence:
Every number in this sequence (apart from the first, which is the input) shall be composed of n digits, where n is an even number. If we split the number to n/2 pairs, for each pair, the first digit should be the amount of times the second digit appeared in the previous number
Visual explanation:
Consider this example "sequence starter" or input 6577
The next number in the sequence should look like this 161527
Because the input has 1 "6", 1 "5" and 2 "7"s.
If input has too many digits (more than 9 of a single digit) you wouldnt be able to get a correct output
Example: 111111111111 (12 1's)
Next number in sequence has to describe 12 1's. Thus we split it into 9 1's and 3 1's (sum 9+3 = 12)
Next number: 9131
You should iterate 4 times for the input, and output it (either return a list/array of 4 integers, or output it by seperating them with a space, newlines are also acceptable)
"The number can be written in a lot of ways, how do I write it?":
If you think about it, the example input 6577 can also be written as 271516 (two 7's, one 5, one six). However this is non-valid output. You should iterate the number left to right. Thus 161527. If it was 7657 you would iterate the amount of 7's, then amount of 6's then amount of 5's, thus valid output would be 271615
Example I/O:
Input:75
Output:1715 211715 12311715 4112131715
Input:1
Output:11 21 1211 3112
Input:111111111111 (12 1's)
Output:9131 192113 31191213 23411912

This is unlike the "Say what you see" question, because the sequences are different: https://oeis.org/A005150 <- This one returns numbers like this:
Input: 1211 Output: 111221
While the sequence I'm asking for would do
Input: 1211 Output: 3112
The two sequences are different and require different algorithms.
My asked sequence: https://oeis.org/A063850
"Possible duplicate" sequence: https://oeis.org/A005150

Important specification:
Since it wasnt clear enough for some people who tried to answer this question, the correct output for k chars where k > 9 is not "kc" (where c is char) but 9c(k-9)c etc. Thus correct output for 12 1's isn't 121 (12 1) but 9131(9 1's, (12-9) 1's and so on)
If in doubt, your code is wrong if it ever outputs a number with an odd amount of digits (like 121), it should have output of even digit numbers due to the nature of the sequence.

This is code-golf thus code with least bytes wins.

Proposed testcase: 1111111111111111111 (19 1's)

More closely related (still not dupe though).

Can we output as a comma-separated list of integers? Can the output start with the input integer (and thus have length 5)?

In your last test case, shouldn't the last number be 23411912 instead of 23411219?

@GregMartin Indeed. Thanks for pointing out. But no, you are not allowed to return a list of integers or output integers seperated with anything apart from newlines or spaces. And no, you shouldnt output the input

Input 1111112111111 do we output 913112 or 911231 (since the three 1s all appear after the 2)?

PowerShell, 111 104 bytes
$z=$args;1..4|%{($z=-join($z-split'\B'|group|%{for($c,$n=$_.Count,$_.Name;$c-gt9;$c-=9){"9$n"}"$c$n"}))}

Try it online!

Since you don't use $i in your loop, why not just loop directly like $z=$args;0..3|%{...

@AdmBorkBork I thought about it but felt it would be longer after having to assign $args (and I originally thought I would use $i). I was going to measure it but then the question got closed.

@AdmBorkBork ...aaaand edited (thanks)

Python 2, 116 bytes
x=input()
exec"x=''.join(x.count(n)/9*(`9`+n)+`x.count(n)%9`+n for i,n in enumerate(x)if n not in x[:i]);print x;"*4

Try it online!

Output for 19 ones 1111111111111111111 is incorrect. Should be 919111 but gives 919121

Output wrong for many values. Example: http://image.prntscr.com/image/ed4c523b105b41169e8aa8c46a95f963.png , With input 11 output should be 21 1211 3112 132112, I dont understand why it outputs 111 as the first iteration which causes the whole chain to go badly

@P.Ktinos the input format was wrong, it need to be a string (it must be the leftover of the tests that i was doing). Fixed the link

05AB1E, 30 23 21 bytes
4F©Ùv9y«®y¢9‰`U×XyJ}=

Try it online!
Explanation
4F                     # 4 times do:
  ©                    # store a copy of the current number in register
   Ùv                  # for each unique digit y in the number
     9y«               # concatenate 9 with y
        ®y¢            # count occurrences of y in current number
           9‰          # divmod by 9
             `U        # store the result of modulus in X
               ×       # repeat the number "9y" result_of_div times
                X      # push result of modulus
                 y     # push y
                  J    # join everything to one number
                   }   # end inner loop
                    =  # print the current number without popping

@MagicOctopusUrn: That won't work for number with more than 9 repetitions of a digit, like the example in my TIO link for example.

Ohhh... I got it now.

Mathematica, 117 bytes
Grid@{Rest@NestList[FromDigits[Join@@(Reverse/@Tally@IntegerDigits@#//.{a_,b_}/;a>9->{9,b}~Sequence~{a-9,b})]&,#,4]}&

Seems like it shouldn't need to be this long.

C# 246 bytes
namespace System{using Linq;using f=String;class p{static void Main(f[] s){f p=s[0];for(int i=0,n;i++<4;Console.Write(p+" "))p=f.Concat(p.GroupBy(c=>c).SelectMany(g=>new int[(n=g.Count())/9].Select(_ =>"9"+g.Key).Concat(new[]{n%9+""+g.Key})));}}}

Ungolfed:
namespace System
{
    using Linq;
    using f = String;
    class p
    {
        static void Main(f[] s)
        {
            f p = s[0];
            for (int i = 0, n; i++ < 4; Console.Write(p + " "))

                p = f.Concat(p.GroupBy(c => c).SelectMany(g =>
                    new int[(n = g.Count()) / 9].Select(_ => "9" + g.Key).Concat(new[] { n % 9 + "" + g.Key }
                )));
            Console.ReadKey();
        }
    }
}

Try it here (Type input into bottom frame once its compiled and hit ENTER)

Jelly, 27 bytes
L,Ḣ
D©®i$ÞŒgs9$€Ç€€FḌµ4µÐ¡Ḋ

Try it online!
The successive €s cannot be nested because chains cannot be nested.
Nesting with separate link: 27 bytes.
Print instead of cumulation: 27 bytes.
Explanation
L,Ḣ                     - helper function, does the look-and-say. Input is a list of digits
 ,                      - return 2-tuple of:
L                       -   length of input
  Ḣ                     -   first element of input

D©®i$ÞŒgs9$€Ç€€FḌµ4µÐ¡Ḋ - main link, takes input as integer
                 µ4µÐ¡  - repeat 4 times, saving the results of each iteration:
D                       -   convert integer to list of digits
 ©                      -   save into register, for later use
  ®i$Þ                  -   sort list's elements by first occurrence in list
      Œg                -   group runs of equal elements
        s9$€            -   split each run into sets which are at most 9 elements long
            Ç€€         -   do the look-and-say with helper function
               FḌ       -   flatten and convert back into integer for next iteration
                      Ḋ - remove the first element from the list since it includes the
                           initial element

PHP, 141 Bytes
for($a=$argn;$i++<4;$a=$o,print$a._,$o="")foreach(array_count_values(str_split($a))as$n=>$c)$o.=str_repeat("9$n",$c/9^0).($c%9?($c%9).$n:"");

Try it online!


text:
Is it within the Cantor set?
The Challenge
For this challenge, you are supposed to determine if a given number is in the Cantor set. So first, let's define the Cantor set.
First, start with the numbers between 0 and 1. Any numbers outside this range are not in the Cantor set. Now, let's divide the numbers into three equal parts: [0,1/3], [1/3,2/3], [2/3, 1]. Any numbers not inside the ranges of the first and last parts are not in the Cantor set. Now, you repeat this process for the segments [0,1/3] and [2/3, 1]. Then you repeat on what is leftover. You keep on doing this forever. In the end, all numbers that are remaining are in the Cantor set. Here is a diagram of the first six iterations:

Input
Two integer x and y.
0 < y < 2^15
0 <= x <= y
The greatest common denominator of x and y is 1, unless x == 0.

Output
Truthy if x/y is in the Cantor set.
Falsy if x/y is not in the Cantor set.

Examples
Now, let's see some examples of numbers that are in the Cantor set.

1/3 -> true

It is on a boundary, and boundaries are never removed.
1/4 -> true

1/4 is never in the middle third of a segment, though it is never on the boundary either. If you follow it's path, you will actually find that it alternates between being in the first and last thirds of a section.
1/13 -> true

1/13 alternates between the first, first, and last sections.
1/5 -> false

1/5 falls into the first empty block of the third row in the above diagram, between 1/9 and 2/9.
Other test cases:
0/4 -> true
3/10 -> true
3/4 -> true
10/13 -> true
1/1 -> true
12/19 -> false
5/17 -> false
3/5 -> false
1/7 -> false
1/2 -> false

You can try other numbers with this snippet:

function isCantor(t,r){var n=new Set;if(0>r)return isCantor(-t,-r);if(0==r)return!1;if(0>t||t>r)return!1;for(;;){if(t%r===0)return!0;if(1===Math.floor(t/r))return!1;if(n.has(t))return!0;n.add(t),t=t%r*3}}$("#test").click(function(){var t=parseInt($("#x").val()),r=parseInt($("#y").val());if(isNaN(t)||isNaN(r)||0==r)return void $("#result").text("Invalid input");var n=isCantor(t,r),i=(n?"I":"Not i")+"n the Cantor set.";$("#result").text(i)});
input{width:30px}button{margin-left:7px}
<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><input id=x>/<input id=y><button id=test>Test</button><p id=result>

Objective
The person with the least bytes wins.

Are we guaranteed that the input is not (0,0)? Is the fraction given in simplest form?

@xnor look at the range given for y. I'm going to say that the fraction is in simplest form unless x == 0

Some test cases where x!=1 would be good. Also, your snippet says 1/3 is not in the cantor set.

@xnor Added and fixed ;)

Can we take the input directly as a fraction x/y?

If i enter 1/13 in your test snipet i get a recursion error

@RomanGräf Odd, I don't have that problem.

@RomanGräf Tell me if you have that problem again. The snippet no longer uses recursion.

Cantor can it be found?

@mbomb007 Lol, that's pretty good.

Related: OEIS A054591

Not sure if "within" in the title is the best word considering that the Cantor set is meagre and its interior is empty. Maybe use "in" instead (as you do in the text)?

Mathematica, 54 bytes
If[Last@#===1,Most@#,#]&@RealDigits[#,3][[1]]~FreeQ~1&

Unnamed function taking a fraction x/y as input, where y > 0 and 0 ≤ x ≤ y, and returning True or False.
A real number between 0 and 1 is in the Cantor set precisely when none of the digits in its base-3 expansion equals 1; the exception is that a fraction whose denominator is a power of 3 (whose base-3 expansion therefore terminates) is allowed to end in a 1.
RealDigits[#,3][[1]] gives all of the digits in the base-3 expansion of the fractional input #, in a form like {1, 0, 2, {0, 1, 0, 2}}: the last list is the periodic part of the expansion, while the integers beforehand are the digits before the periodicity starts. If the base-3 expansion is periodic right away, the output is like {{0, 1, 0, 2}}; if the base-3 expansion terminates, the form is like {1, 0, 2}.
So we want to check, using ~FreeQ~1, whether the list is free of 1s or not. However, because of the terminating expansion thing, we want to delete the last element of the list if it equals 1; that's what If[Last@#===1,Most@#,#] accomplishes. (The === is needed to compare a potential list with 1: == alone remains unevaluated in that situation.)

Im surprised that Mathematica does not have IsCantorNumber but has a function to determine is something is a goat.

Well, I dunno, which come up more in real life: goats or fractals? ;)

FreeQ[RealDigits[#,3][[1]]/.{{x___,1}}:>{x},1]&

Such a rule would also strip off trailing 1s in the periodic part, which leads to incorrect answers. For example, the base-3 expansion of 7/8 is .21212121...., or {{2,1}}; but the suggested rule would change that to {{2}}, which is free of 1s but shouldn't be.

Touché. How about #==0||FreeQ[RealDigits[#,3]/.{{x___,1},_}:>{x},1]&? If it's terminating and nonzero RealDigits[#,3] will be of the form {{__Integer},-1} and if it's repeating it will be of the form {{___Integer,{__Integer}},-1}, right? I'm on mobile so it's hard to test right now. If this works, using infix notation for RealDigits might work as well.

C (gcc), 61 59 58 bytes
f(x,y,i){for(i=y;i--&&x<y;)x=(y-x<x?y-x:x)*3;return x<=y;}

Exploits the symmetry of the Cantor set. Breaks after y iterations to avoid an infinite loop.
Try it online!

Jelly, 22 17 16 15 bytes
,ạµ%⁹×3µÐĿ:⁹Ḅ3ḟ

Prints 3 for truthy, nothing for falsy.
Try it online!
Background
A well-known property of the Cantor set is that it contains precisely those numbers between 0 and 1 that can be written without 1's in their ternary expansion.
Note that some numbers – precisely the right edges of the closed intervals involved in the set's construction – can be written either with a single (trailing) 1 or with an infinite amount of trailing 2's. For example, 1 = 13 = 0.22222…3 and 1/3 = 0.13 = 0.022222…3, just as 0.510 = 0.499999…10.
To avoid special-casing the right edges, we can check for 1's is the shortest decimal expansion in both x/y and 1 - x/y = (y - x)/y, where x/y is a right edge iff (y - x)/y is a left edge. If at least one of them contains no 1's, x/y belongs to the Cantor set.
How it works
,ạµ%⁹×3µÐĿ:⁹Ḅ3ḟ  Main link. Left argument: x. Right argument: y

 ạ               Absolute difference; yield y - x.
,                Pair; yield [x, y - x].
       µ         Begin a new, monadic chain with argument [a, b] := [x, y - x].
  µ     ÐĿ       Repeatedly execute the links in between until the results are no
                 longer unique, updating a and b after each execution. Return the
                 array of all unique results.
   %⁹              Compute [a % y, b % y].
     ×3            Compute [3(a % y), 3(b % y)].
                 This yields all unique dividends of the long division of x by y in
                 base 3.
          :⁹     Divide all dividends by y to get the corresponding ternary digits.
            Ḅ    Unbinary; turn [1, 1] into 3, other pairs into other numbers.
             3ḟ  Remove all occurrences of the resulting numbers from [3], leaving
                 an empty array if and only if one pair [a, b] is equal to [1, 1].

3 is the true true +1.

JavaScript (ES6), 65 67
Edit 2 bytes saved thx @Luke
n=>d=>(z=>{for(q=0;~-q*n*!z[n];n=n%d*3)z[n]=1,q=n/d|0})([])|q!=1|!n

Less golfed
n=>d=>{
  z = []; // to check for repeating partial result -> periodic number
  for(q = 0; q != 1 && n != 0 && !z[n]; )
    z[n] = 1,
    q = n / d | 0,
    n = n % d * 3
  return q!=1 | n==0
}

Test

f=
n=>d=>(z=>{for(q=0;~-q*n*!z[n=n%d*3];q=n/d|0)z[n]=1})([])|q!=1|!n

console.log(
'Truthy: 1/3 1/4 1/13 0/4 3/10 3/4 10/13 1/1\nFalsey: 1/5 12/19 5/17 3/5 1/7 1/2'.replace(/(\d+).(\d+)/g,(a,x,y)=>a+':'+f(x)(y))
)

I think you can replace n=n%d*3 with q=n/d|0 and then replace z[n] with z[n=n%d*3]

JavaScript (ES6), 55 bytes
y=>f=(x,z,n=~y,q=x/y|0)=>n?!z|!q&&f(x%y*3,z|q==1,n+1):1

Use by currying in the denominator first and the numerator second. The standard form is a byte longer:
f=(x,y,z,n=~y,q=x/y|0)=>n?!z|!q&&f(x%y*3,y,z|q==1,n+1):1

Explanation
If a fraction is not in the Cantor set, it must fall into one of the middle sections at some point; therefore, its representation in base 3 must contain a 1 followed at some point by a non-zero digit. That's how this works:

z keeps track of whether we've found a 1.
q is the current digit in base 3.
!z|!q is true if z is false (we have not found a 1) or q is false (the current digit is 0).

If n runs down to zero before we find a non-zero digit somewhere after a 1, the fraction is in the Cantor set and we return 1.

Bash + GNU utilities, 62 bytes
dc -e3o9d$2^$1*$2/p|tr -cd 012|grep -P "1(?!(0{$2,}|2{$2,})$)"

Try it online!
Pass it two integer arguments with arg1 <= arg2 and 0 < arg2.
The output is returned in the exit code (0 for falsy, 1 for truthy), as allowed by PPCG I/O methods.
I suspect the regex can be golfed further, maybe even eliminating the tr command in favor of using grep -z, but this is the shortest I've been able to come up with.  (Unfortunately, grep -z is incompatible with grep -P, and the -P option to get perl-style regexes is required for the ?! syntax.)
Testbed program and output:
for x in '1 3' '1 4' '1 13' '1 5' '0 4' '3 10' '3 4' '10 13' '1 1' '12 19' '5 17' '3 5' '1 7' '1 2'
  do
    printf %-6s "$x "
    ./cantor $x >/dev/null && echo F || echo T
  done

1 3   T
1 4   T
1 13  T
1 5   F
0 4   T
3 10  T
3 4   T
10 13 T
1 1   T
12 19 F
5 17  F
3 5   F
1 7   F
1 2   F

Explanation
dc part (the arguments are x and y):
3o     Set output base to 3.
9      Push 9 on the stack.
d      Duplicate the top of the stack. (The extra 9 on the stack isn't actually used, but I need some delimiter in the code here so that the 9 doesn't run into the number coming up next.  If I used a space as a no-op, then I'd need to quote it for the shell, adding an extra character.)
$2^    Raise 9 to the y power. This number in base 3 is 1 followed by 2y 0's.
$1*$2/ Multiply the base-3 number 10....0 (with 2y 0's in it) by x and then divide by y (truncating). This computes 2y digits (after an implied ternary point) of x/y.  That's enough digits so that the repeating part of the rational number is there at least twice.
p      Print the result, piping it to tr.

tr and grep part:
A minor issue is that, although dc handles arbitrarily large integers, when dc prints a large number, it will break it up into 69-character lines, with each line except the last ending with a backslash, and with a newline after each line.
The tr command deletes any backslashes and newlines.  This leaves just a single line.
The grep command then uses a perl-style regex (-P option, which is a GNU extension). The regex matches if the line contains a 1 not followed by at least y 0's or at least y 2's which then end the string.
This is exactly what's needed to identify x/y as not being in the Cantor set, because the repeating part of the base-3 representation of the rational number x/y can be viewed as starting at digit #y+1 after the ternary point, and is at most y digits long.

CJam (19 bytes)
{_@3@#*\/3b0-W<1&!}

Online test suite
This is an anonymous block (function) which takes two arguments on the stack and leaves 0 or 1 on the stack. It works by base converting the fraction x/y into y base 3 digits and returning true iff they contain no 1 or the only 1 is part of a suffix 1 0 0 0 ....
{            e# Begin a block
  _@3@#*\/3b e#   Base conversion
   0-W<      e#   Remove all zeros and the final non-zero digit
   1&!       e#   True iff no 1s are left
}

Pyth, 14 bytes
gu*3hS,G-QGQE0

Based on my C solution. y on first input line, x on second.
                Q = y
 u         QE   G = x
                loop y times
  *3                x = 3 *
    hS,G                min(x,
        -QG                 y-x)
g            0  return x >= 0

If x/y is within the Cantor set, x stays between 0 and y. Otherwise, x becomes greater than y at one point, then diverges to negative infinity in the remaining iterations.
Try it online!

Batch, 91 bytes
@set/ai=%3+1,n=%1*3%%%2,f=%1*3/%2%%2,f^|=j=!((%2-i)*n)
@if %f%==0 %0 %n% %2 %i%
@echo %j%

Tests the first y-1 base 3 digits of x/y. i is the count of digits tested. n is the next value of x. j is true if n reaches zero (because the expansion terminates) or we have tested y-1 digits without finding a 1. f is true if j is true or if the next digit is a 1, at which point we stop looping and output j.


text:
Can you find the villain's password?
Background
You work for the police force as a programmer.
A villain has planted a bomb in the city, luckily the police force has captured both him and the bomb. The bomb is really complicated to disarm, however it has a password input to disarm it.
The villain, being cocky, has told you that there was no way you'd find the password as you'd take X time to brute force it. You notice that the keyboard can only input english letters (lower and upper case) and digits.
Task
Assuming you can try Y passwords per second, and that the brute force character order would be a-z A-Z 0-9, you are to create either a full program or a function that takes as input both X (in seconds) and Y (passwords/second) and outputs the villain's password.
X can be a float but Y will always be an integer.
(X*Y should always be an integer)
Your code has to solve the problem using math instead of relying on trying several options or creating huge arrays and simply indexing them with X*Y.
Example in JS
var c="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
var b=62;
function num(x){
    var n=0;
    while(x>=0){
        x-=Math.pow(b,++n);
    }
    return n;
}
function reduce(x, n){
    while(--n>0){
        x-=Math.pow(b,n);
    }
    return x;
}
function pass(x, y){
    x=x*y;
    x--;
    var p=[];
    var n=num(x);
    x = reduce(x, n);
    do{
        var t=x%b;
        x=(x-t)/b;
        p.unshift(t);
    }while(x>0);
    return ("a".repeat(n)+p.map(f=>c[f]).join``).substr(-n);
}

Assuming my code is correct here are some example outputs.
(If there are any errors please tell me so that I can correct them)
pass(0.000, 1000); // "" or anything that won't be mistaken for a password
pass(0.001, 1000); // "a"
pass(0.002, 1000); // "b"
pass(0.027, 1000); // "A"

//A password that would take a year to brute force at 1000 passwords/second
pass(3600*24*365, 1000) // "HzmZmr"

My code is awful and ungolfed but it's only to serve as an example. Since this is code-golf shortest answer in bytes wins.

"You cannot brute force" I'm not quite sure what that implies... does it mean we can't simply generate the next Y passwords each second and then output after X seconds?

Also, will X always be an integer, or can it be floating-point?

@ETHproductions Yes. You shouldn't just generate several passwords and choose one or anything similar. You should instead get there through math and logic. Also both X and Y should be integers. I'll specify that in the question.

I'm really not sure what you're expecting here... You haven't provided information about how we could guess the password without a brute force approach. Is there a valid timing attack against the bomb? Is the password hashed in the bomb's database/memory? Maybe it's a weak hashing algorithm? What logical path are you expecting us to follow?

Oh I think I get it... we know that X is the upper bound on time so we take the Y passwords/second and generate Z passwords where Z = XY? Then the Z'th password would be correct? If this is the case, what's the minimum length password that the bomb accepts?

@Poke I think we are supposed to output the (X*Y)th string from a, b, c,..., y, z, A, B,...,Y, Z, 0, 1, ..., 8, 9, aa, ab, ac, ad,.... I'm voting to close as unclear until that gets cleared up though.

@Riley Yea, but explaining it like that will just make people brute force passwords with a counter. And I was thinking about using math to get there.

I think the updates to the question are good but it's generally discouraged to ask Do X without Y questions. In this case I see what you're going for and some people may be able to golf it really nicely but brute force is a much simpler algorithm.

Maybe you could add restricted-complexity as tag, and require that the algorithm is better than linear in respect to X*Y.
Incidentally, could we assume that X*Y is always an integer?

@Leo I feel like that could possibly restrict more solutions, and X*Y will always be integer.

It's not totally clear what you mean by "brute-force" here

@LuisMendo Your code shouldn't loop over every password with a counter or generate huge arrays and index them with X*Y. Instead your code should get there directly with some math, like in my example.

Before posting your challenges, you could post on Sandbox first, there you can receive some feedback to improve your challenge.

This still needs an actual specification (making us reverse engineer it from a reference implementation doesn't count), but judging by the answers it would likely be close enough to http://codegolf.stackexchange.com/q/54105/194 to be closed as a dupe anyway.

Jelly, 9 bytes
×ḃ62ịØWŒs

Try it online!
How?
×ḃ62ịØWŒs - Main link: X, Y
×         - multiply X by Y
 ḃ62      - convert to bijective base 62 (uses modulo arithmetic under the hood)
    ị     - index into (1-based)
     ØW   - word yield -> "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_"
       Œs - swap case

Python 2, 121 bytes
x,y=input()
r=range;b=map(chr,r(97,123)+r(65,91)+r(48,58))
i=int(x*y)
p=b[i%62]
while i/62>0:i=i/62-1;p=b[i%62]+p
print p

Try it online!
This basically calculate the x*y in base 62
For a recursive solution at 125 bytes
x,y=input()
r=range;b=map(chr,r(97,123)+r(65,91)+r(48,58))
f=lambda i:(f(i/62)if~-i/62>0else'')+b[i%62-1]
print f(int(x*y)+1)

Try it online!


text:
Average distance of two points in unit n-dimensional hypercube
An easy way to understand the unit n-dimensional hypercube is to consider the region of space in n dimensions that you can get if every coordinate component lies in [0, 1]. So for one dimension it's the line segment from 0 to 1, for two dimensions it's the square with corners (0, 0) and (1, 1), etc.
Write a program or function that given n returns the average Euclidean distance of two points uniformly random selected from the unit n-dimension hypercube. Your answer must be within 10-6 of the actual value. It's ok if your answer overflows your language's native floating point type for big n.
Randomly selecting a 'big' number of points and calculating the average does not guarantee such accuracy.
Examples:

1 → 0.3333333333...
  2 → 0.5214054331...
  3 → 0.6617071822...
  4 → 0.7776656535...
  5 → 0.8785309152...
  6 → 0.9689420830...
  7 → 1.0515838734...
  8 → 1.1281653402...

Data acquired from MathWorld.
This is code-golf, lowest byte-count wins.

Reiterated winning criterion in an edit.

Just to be clear: distance refers to the Euclidean distance, yes?

@Dennis Yes, I will add that.

@orlp can you post the formula used? Or is there no generic formula? https://martin-thoma.com/average-distance-of-points/ Beta function here seems like what you want, but they only give pseudo code.

@carusocomputing What's the point of the challenge if you want me to solve it for you?

Is it OK to use a Monte Carlo method to have a failure probability of at most, say, 10^-10?

@xnor No. Your answer must be accurate to at least 5 decimals.

@orlp I consider that a strange interpretation, since it's easy to an indisinguishable random program with negligible failure chance. It's your challenge though, and you should make it extremely clear you're banning this method to make sure posters don't waste time trying it.

@orlp registering my objection to a challenge that is a math puzzle until someone figures out the math, then it becomes a programming puzzle when everyone copies the formula in different languages. I need to ask a meta question about this.

@Sparr There are dozens of various methods of evaluating integrals (oops, spoiler alert). I don't believe there's a known formula that you can just implement and everyone will copy it. Even if that were the case, I don't see the problem. There are multiple aspects to solving a challenge, and golfing the syntax is only one of those.

Is it OK if the algorithm has a ridiculous runtime if the final answer is guaranteed accurate?

@xnor Per default PPCG rules, yes.

When you say 5 digits of accuracy, do you mean to within 1e-5, or would an estimate of 1.500000000000001 be wrong when the output should be 1.499999999999999?

@xnor 5 digits should be accurate, after rounding. So 1.49999999999 rounds to 1.50000.

@orlp That still doesn't preclude an arbitrarily small error from giving different first 5 digits. Please give accuracy requirements in terms of a relative error.

@feersum Why relative error? I edited to absolute error within 10^-6.

Then the allowed relative errors goes to 0 as n -> infinity.

The result diverges as the number of dimensions approaches infinity, correct?

@mbomb007 I believe so, yes.

Mathematica, 68 bytes
NIntegrate[(1-((E^-u^2+u*Erf@u√π-1)/u^2)^#)/u^2,{u,0,∞}]/√π&

Implementation of the formula using NIntegrate to approximate its value.

Beat me by 58 seconds :(

Where did you find the formula?

@feersum It's formula (8) from Hypercube Line Picking. (10) is a typo and shouldn't have the double integral or du.

If you actually input this as text it parses u√π as one token, so you need a space between u and √.


text:
Entropic Quine!
Your task is to write a program or function which:

When run for the first time, outputs its source code.
On subsequent executions, it should output what it output previously, but with one random character change (defined below). It does not have to be a uniformly random change, but every possible change should have a nonzero chance of occurring.
After the first execution, your program will not necessarily be a quine anymore; the output will have changed (and the program is free to modify itself as well).

For example, if your quine was ABCD, repeatedly running it might print:
ABCD
A!CD
j!CD
j!CjD

Specifications

A character change is either:

The insertion of a random character,
The deletion of a random character, or
A replacement of a character with a new random character. Note that the new character is allowed to be the same as the one it replaces, in which case no change will be made.

Of course, deleting or replacing a character from an empty string is not a valid change.
Despite this being tagged quine, the rules against reading your source code do not apply.

You can use any character set as long as it includes the characters used in your source code.

What characters does each character refer to?

How often does this have to work? Clearly it can't be arbitrarily often or otherwise every possible program as longer or longer than the original one has to be a solution to the challenge.

So you run the same program ABCD 4 times and it outputs 4 different outputs?

Also, the program can change its own source code, but cannot read its source code? How is that defined?

@user202729 The program modifies itself such that running it again produces a different output. All different outputs are relative to how the program was the first time.

I see that j!CDJ has 3 character changes (have string edit distance of 3) from the original program (ABCD).

@user202729 Correction: All different outputs are relative to the previous output, with the exception of the first output, which should be the program's source code at the time.

Can the character be added anywhere, or just at the end?

@ConorO'Brien Anywhere.

Is the program only required to work the first iteration? If so posing the challenge as "write a program that prints itself with one random change" would be more clear

@dylnan No, it must work on subsequent iterations, where it outputs whatever it output last time with a random change. The program file itself is free to diverge arbitrarily from the output, as long as it produces the expected behavior on successive executions.

How many iterations does it have to work?

@dylnan Forever.

Is the source code changing? I'm not clear on whether the output of the first program will become the second program which then has to perform the same step as the first program

@dylnan The output of the first program becoming the second program etc. is inconsistent with the description, because you cannot then both have all possible random changes and have it keep working indefinitely.

@ØrjanJohansen I agree, I just think the challenge description is a bit ambiguous.

@dylnan No, it doesn't. The challenge was initially downvoted and closed because people didn't understand that. Is there anything you think could make that more clear?

@ØrjanJohansen The changes only are reflected in the output, not in the code. The program doesn't have to remain a quine, so the code and the output don't have to be the same after the first execution.

@EsolangingFruit Do we get bonus points if we don't read our source code? I at least assumed that for the first output, it has to be a proper quine without reading the source. That's easy enough. Personally, I think reading your source code should be disallowed entirely. It makes it more challenging, but still easily possible.

I'd recommend changing 'addition of a character' to 'insertion', and maybe adding a reference to Levenshtein distance being 1 between iterations (except when changing a character to itself)

Is no change a valid change?

@JoKing "Note that the new character is allowed to be the same as the one it replaces, in which case no change will be made."

So that's only for replacing? Can an empty string remain an empty string in the next iteration?

@JoKing No, it cannot.

Are we allowed to have a function instead of a program (in which case we store the last state in the outer program)? Otherwise you'll have to store the last source code with changed character either in a separated file or some OS settings in most languages.. (or modify the source code itself while still being able to run regardless of the change, which is close to impossible to do forever - since the program can potentially become empty..)

@KevinCruijssen Not necessarily, because you can store the code in a string literal or something to ...

@EsolangingFruit In most languages not.. Executing a program will reset all those string variables.. I can execute a function multiple times with a class-level string. But executing a program resets to default in most programming languages.. It does in Java, C#, C, C++, and most other OO languages at least.. (Which was my main reason for asking for a function instead of a program, which is usually the default anyway.)

@KevinCruijssen There are several solutions here that modify their source code. But you have a good point, so I'll allow functions as well.

Python 3, 288 270 224 212 195 196 194 180 178168 bytes
f=__file__
m=open(f).read()
x=m
print(end=x)
h=hash
k=h(f)
n=k%2
a=h(m)%-~len(x)
x=x[:a]+(not(k%3)*x)*chr(k%127)+x[a+n:]
open(f,'w').write(m.replace("\t",";x=%r\t"%x))

Try it online!
After printing the file source code on the first iteration, we append an extra line to set x to the new source code, rather than m.
Explanation:
f=__file__    #Open and read the source code
m=open(f).read()

x=m       #Set x to the source code for the first iteration
x="..."
...
x="..."   #Set x to the latest iteration
          #On the last iteration there's a tab character to mark progress
print(end=x)    #Print the previous iteration's text

#Modify the text
h=hash
k=h(f)            #Generate a random number to use
n=k%2             #Whether the character will be inserted or changed/deleted
a=h(m)%-~len(x) #The index of the change
                         #Add 1 to the range to append new characters, and to avoid mod by 0 in the case of an empty string
x=x[:a]+(not(k%3)*x)*chr(k%127)+x[a+n:]    #Make the change

open(f,'w').write(m.replace("\t",";x=%r\t"%x))   #Modify the source code, adding the new iteration of the source code

Assuming hash returns a uniformly random number, there is about 1/6 chance of inserting a new character, 1/6 chance of changing an existing character and 2/6 chance of deleting a character. What's the remaining 2/6 chance you ask? Why, it does nothing at all 2/6 of the time!
(Here's a validation program adapted from mbomb007's answer's. Try it online!)

I think f=__file__ would help in the first step too.

Python 2, 779 801 bytes
Though the challenge was edited to show that reading your source is allowed, I was already creating my solution without that. So, to show that it's possible, I finished it. No reading of the source file:
s='s=%r;print s%%s\nfrom random import*;L=4;f=open(__file__,"wa"[L>5]);R=randint\nf.write("\\n".join((s%%s).split("\\n")[1:5:2]).replace("4",`map(ord,s%%s)`))\nif L>5:exec\'b=[];h=%%d\\nwhile~-h:b+=[h%%%%1000];h/=1000\\nwhile b:r,p,n=b[-3:];b=b[:-3];L=[L[:p]+L[p+1:],L[:p]+[r]+L[p+n:]][n<2if L else 1]\\nprint"".join(map(chr,L))\'%%1\n\nn=R(0,2);p=R(0,len(L if L>5else s%%s));r=R(0,255);f.write("%%03d"*3%%(n,p,r))';print s%s
from random import*;L=4;f=open(__file__,"wa"[L>5]);R=randint
f.write("\n".join((s%s).split("\n")[1:5:2]).replace("4",`map(ord,s%s)`))
if L>5:exec'b=[];h=%d\nwhile~-h:b+=[h%%1000];h/=1000\nwhile b:r,p,n=b[-3:];b=b[:-3];L=[L[:p]+L[p+1:],L[:p]+[r]+L[p+n:]][n<2if L else 1]\nprint"".join(map(chr,L))'%1

n=R(0,2);p=R(0,len(L if L>5else s%s));r=R(0,255);f.write("%03d"*3%(n,p,r))

Try it online! (Note that this won't modify the source. You have to run it locally for that to work)
To show that the transformations work, here is a test program (currently set up to always pick 100 for r, and it prints the result for every combination of n and p for the initial list.)

Explanation:
s='s=%r;print s%%s...';print s%s...

The first line is your classic quine, but a lot longer to account for what comes after.
from random import*;L=4;f=open(__file__,"wa"[L>5]);R=randint

Import for random integers. L will become of list of ordinals of the source code, but initially it is an integer not used anywhere else in the source to allow for a string replacement. Open the file to write the new source. On later runs, it will open to append instead.
f.write("\n".join((s%s).split("\n")[1:5:2]).replace("4",`map(ord,s%s)`))

Remove the first and third lines of code. Replace the 4 above with the list of ordinals.
if L>5:exec'b=[];h=%d\nwhile~-h:b+=[h%%1000];h/=1000\nwhile b:r,p,n=b[-3:];b=b[:-3];L=[L[:p]+L[p+1:],L[:p]+[r]+L[p+n:]][n<2if L else 1]\nprint"".join(map(chr,L))'%1

n=R(0,2);p=R(0,len(L if L>5else s%s));r=R(0,255);f.write("%03d"*3%(n,p,r))

In pieces:

if L>5: - Skips this line on first execution. Later, L will be a list, and this will run. I'll explain the exec last, because it's not run the first time.
n - A random number 0-2. This determines which modification occurs (0 = insert, 1 = replace, 2 = delete).
p - A random position in the list that the modification will occur at.
r - A random number to insert or replace in the list
f.write("%03d"*3%(n,p,r)) - Append the 3 randoms to the end of the source file. Every run, this will be adding on to an integer that encodes all the changes to the initial source that have occurred.
exec'b=[];h=%d...'%1... - Get the random numbers (found after %1 on later runs), apply the changes to the list, and print.
while~-h:b+=[h%%1000];h/=1000 - Build a list of the randoms generated so far, accounting for the leading 1, which prevents problems with leading zeros.
while b:r,p,n=b[-3:];b=b[:-3] - Assign the randoms for this iteration.
L=[L[:p]+L[p+1:],L[:p]+[r]+L[p+n:]][n<2if L else 1] - (0 = insert, 1 = replace, 2 = delete)
print"".join(map(chr,L)) - Print the modified source.

Does this sometimes delete a non-existent character from the end of the string? Since p can be the length of the string. Also, what's the behaviour with an empty string?

@JoKing I added a test program. Every possible character change can happen. It just shows that every position may be selected for an insert, replace, or delete, and that it handles an empty list. https://tio.run/##LYoxDsMgDEVnOAUjCAZgRO0NuIHloUOaRIocy6JDT08dpdt/733@ju2kOufhnm4n/gwf7PsUR0oup5Jqs6ZrlBetiz@CNVfmK//VQr6HWIIejeiz5KyLZafhoENjjB04lobpJpDbUEMEelScM/8A

I don't think that no change is valid, though I've asked the OP. The question does say Of course, deleting or replacing a character from an empty string is not a valid change

I've asked Esolanging Fruit, and they say that no change is valid, but not for an empty string.

@JoKing Should be fixed.

Python 3, 205 195 bytes
s='print(end=x);h=hash;k=h(x);n=k%2;a=h(s)%-~len(x);x=x[:a]+(not(k%3)*x)*chr(k%127)+x[a+n:];open(__file__,"w").write("s=%r;x=%r;exec(s)"%(s,x))';x='s=%r;x=%r;x=x%%(s,x);exec(s)';x=x%(s,x);exec(s)

Try it online!
Wanted to try a version that doesn't read the source code. Turned out not a bad as I thought, and it's only 30 or so bytes behind the version that does. The explanation for how it works is mostly the same as the other answer, but it initialises x differently since it can't just read the source code.

Java 10, 370 bytes
String s;v->{if(s==null){s="String s;v->{if(s==null){s=%c%s%1$c;s=s.format(s,34,s);}else{int r=s.length();r*=Math.random();char c=127;c*=Math.random();s=s.substring(0,r)+(c%%3<2?c:%1$c%1$c)+s.substring(r+(c%%3>0?1:0));}}";s=s.format(s,34,s);}else{int r=s.length();r*=Math.random();char c=127;c*=Math.random();s=s.substring(0,r)+(c%3<2?c:"")+s.substring(r+(c%3>0?1:0));}}

Try it online.
Explanation:
String s;               // Class-level String variable to store the modifying source code
v->{                    // Method without parameter nor return-type
  if(s==null){          //  If this is the first execution of this function:
    s="String s;v->{if(s==null){s=%c%s%1$c;s=s.format(s,34,s);}else{int r=s.length();r*=Math.random();char c=127;c*=Math.random();s=s.substring(0,r)+(c%%3<2?c:%1$c%1$c)+s.substring(r+(c%%3>0?1:0));}}";
                        //   Set `s` to the unformatted source-code
    s=s.format(s,34,s);}//   And then to the formatted source-code
else{                   //  For any following executions of this function:
  int r=s.length();r*=Math.random();
                        //   Random index in range [0, length_of_modified_source_code)
  char c=127;c*=Math.random();
                        //   Random ASCII character in unicode range [0, 127)
  s=                    //   Replace the current String `s` with:
    s.substring(0,r)    //    The first [0, `r`) characters of the modified source code `s`
    +(c%3<2?            //    If the random option is 0 or 1:
           c:"")        //     Append the random character
        +s.substring(r  //    Append the rest of the modified source code `s`, but:
          +(c%3>0?      //     If the random option is 1 or 2:
             1:0));}}   //      Skip the first character of this second part

General explanation:
quine-part:

The String s contains the unformatted source code.
%s is used to input this String into itself with the s.format(...).
%c, %1$c and the 34 are used to format the double-quotes.
(%% is used to format the modulo-%).
s.format(s,34,s) puts it all together.

Here a basic Java quine program.
Challenge part:

String s; is the source code we'll modify on class-level.
int r=s.length();r*=Math.random(); is used to select a random index of the source code in the range [0, length_of_modified_source_code).
char c=127;c*=Math.random(); is used to select a random ASCII character (including unprintables) in the unicode range [0, 126].
c%3 is used to select a random option of either 0, 1 or 2. Option 0 will add the random character before index r; option 1 will replace the character at index r with the random character; and option 2 will remove the character at index r.

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


text:
Complete my palindrome
Create a function (preferably) or a program that takes an ordered collection and outputs the smallest possible palindrome that starts with the input.
For example:
>>> completePalindrome( [1, 2, 3] )
[1, 2, 3, 2, 1]

>>> completePalindrome( [1, 2, 3, 4, 5, 4, 3, 2] )
[1, 2, 3, 4, 5, 4, 3, 2, 1]

>>> completePalindrome( "race" )
"racecar"

You may choose to support as many of your language's data types as you want to.
Have fun!

Are we allowed to support just one datatype, eg a string or a list?

[1,2,3,4,5,3,2,1] isnt a palindrome.