Python 2, 79

n=input()
L=range(1,2**n)
for r in L:r+=r<2;map(L.remove,L[r-1::r])
print L[:n]

The magic of iterating over a list as the loop modifies it!

The list L starts with all the integers 1 to a sufficiently high value. The code iterates over each element r of L, taking the sublist of every r'th element, and removing each of those values. As a result, the removed values aren't iterated over. At the end, print the first n elements.

The expression map(A.remove,B) is a trick I've been waiting a long time to use. It calls A.remove for each element of B, which causes all the elements of B to removed from A. Effectively, it takes the list difference, though it requires B to be a sublist of A. It requires Python 2, since Python 3 wouldn't actually evaluate the map.

The first loop needs to be special-cased to convert r from 1 to 2, as r+=r<2.

The sufficiently high upper bound of 2**n makes the program very slow for large values of n. Using n*n+1 suffices, but costs a character. Note that n*n doesn't work for n=1.


Find a sequence in the binary digits of π

JavaScript (Node.js),  167  165 bytes
This is long and slow ... but it should work for any input in theory.

s=>{for(k=t=1n,l=q=2n,n=0n,r=6n,o='#';!~(i=o.search(s));)n=4n*q+t*~n<r?(o+=n,q+(q+=q)-r)/t-n<<(r+=r+t*n*2n)/r:(q*7n*k+2n-r*++l)/(r=(r-q-q)*l,q*=k++,t*=l++);return i}

Try it online!
This is derived from the C# entry on this Rosetta Code page.
The C# code is derived from Java, which is derived from Icon, which is derived from PicoLisp, which is derived from Haskell, which is based on this paper. :-p


Return the last color of the input in Manufactoria


Python 3 - 506 479 bytes

q=range
def p(n):
 for d in q(2,n//2+1):
  if n%d==0:return 0
 return 1
w=int(input());m=w**2;z=len(str(m))
def k(n):
 if n==1:return'-'*(z-1)+'>'
 if p(n):return str(n).zfill(z)
 return'.'*z
l=[k(n+1)for n in q(m)];s=[[0for n in q(w)]for n in q(w)];x=y=w//2;t=[n//2for n in q(2,w*w)];c=[[1,0],[0,-1],[-1,0],[0,1]];j=p=0
for r in t:
 d=c[p%4];p+=1;i=0
 while i<r and j<m:
  s[y][x]=l[j]+' ';x+=d[0];y+=d[1];i+=1;j+=1
s=[''.join(l)for l in s]
for l in s:print(l)

I am not sure if the byte count is correct.
Also, this can most likely be made shorter (I'm new to Python).

Right now I'm just substituting all non-primes with periods. You can change this to any character.

Note: You should only enter odd numbers as input, as otherwise the program breaks.

Furthermore, my function to determine whether a number is prime is the most primitive it can be, for the sake of less characters, so it is not efficient. Though it ran just fine on my computer with input values less than 100 in just under a second.

Note: Input values above 25 or 30 won't display correctly unless you have a ridiculously wide screen.


JavaScript (ES6) / C#, 21 bytes

(v,V,q,Q)=>V-Q-v+q>>1

Try it online! (JS)
Try it online! (C#)


Implement lazy lists, preferably in a language you don't know well

C

I am a total beginner in C, this code is actually the first real thing I coded in C. It compiles without any warnings and runs fine on my system.

How to build

First, get the tarball from my server. It includes a makefile, so just run make to build it and then make run to run it. The program then prints a list of the first 93 fibonacci numbers. (After number 94, an unsigned 64 bit integer overflows)

Explanation

The programs core is the file lazy-list.c. In the corresponding header file, I define a struct list, that is our lazy list. It looks like this:

enum cell_kind {
  NIL,
  CONS,
  THUNK
};

typedef enum cell_kind cell_kind;

typedef long int content_t;

struct list {
  cell_kind kind;
  union {
    struct {
      content_t* head;
      struct list* tail;
    } cons;
    struct {
      struct list* (*thunk)(void*);
      /* If you want to give arguments to the thunk, put them in here */
      void* args;
    } thunk;
  } content;
};

The member kind is kind of a tag. It marks, whether we reched the lists end (NIL), a cell that is already evaluated (CONS) or a thunk (THUNK). Then, there follows a union. It is

either an already evaluated cell with a value and a tail
or a thunk, featuring a function-pointer and a struct, that may contain some arguments to the function, if needed.

The content of the union is asserted by the tag. If the tag is NIL, the content of the union is undefined.

By defining the helper functions mentioned in the specification above, one can usually abstract the lists definition from it's usage, eg. you can simply call nil() to get an empty list instead of creating one by yourself.

The three most interesting functions are zipWith, take and fibonaccis. But I don't want to explain take, since it is very similar to zipWith. All functions, that operate lazily, have three components:

A wrapper, that creates a thunk
A worker, that performs the calculations for one cell
A struct, that keeps the arguments

In case of zipWith, these are zipWith, __zipWith and __zipArgs. I just show them here without any further explanation, there function should be quite clear:

struct __zipArgs {
  content_t* (*f)(content_t*,content_t*);
  list* listA;
  list* listB;
};

static list* __zipWith(void* args_) {
  struct __zipArgs* args = args_;
  list* listA = args->listA;
  list* listB = args->listB;
  list* listC;

  content_t* (*f)(content_t*,content_t*) = args->f;
  content_t* headA = head(listA);
  content_t* headB = head(listB);
  content_t* headC;

  if (NULL == headA || NULL == headB) {
    free(args);
    return nil();
  } else {
    headC = f(headA, headB);
    args->listA = tail(listA);
    args->listB = tail(listB);
    listC = thunk(__zipWith,args);
    return cons(headC,listC);
  }
}

list* zipWith(content_t* (*f)(content_t*,content_t*),list* listA, list* listB) {
  struct __zipArgs* args = malloc(sizeof(struct __zipArgs));
  args->f = f;
  args->listA = listA;
  args->listB = listB;
  return thunk(__zipWith,args);
}

The other interesting function is fibonaccis(). The problem is, that we need to pass a pointer of the first and second cell to the thunk of the third, but in order to create those cells we also need a pointer to the thunk. To solve that problem, I filled the pointer to the thunk with a NULL first and changed it into the thunk, after it was created. Here is the listening:

static content_t* __add(content_t* a,content_t* b) {
  content_t* result = malloc(sizeof(content_t));
  *result = *a + *b;
  return result;
}

list* fibonaccis() {
  static content_t one_ = 1;
  static content_t zero_ = 0;
  list* one  = cons(&one_,NULL);
  list* two  = cons(&zero_,one);
  list* core = zipWith(__add,one,two);
  one->content.cons.tail = core;
  return two;

Possible improvements

My solution does not use polymorphism. Although possibly possible, my C skills are not sufficient to know how to use it. Instead, I used a type content_t, that one can change to whatever fits.
One could extract the thunk out of the list's defintion and using it only abstractly, but doing so would make the code more complicated.
One could improve the parts of my code that aren't good C.


Rust, 11 (hopefully correct) terms

use ::std::ops::{Add, Sub, Mul};
use ::std::rc::Rc;
use ::std::hash::{Hash, Hasher};
use ::std::collections::HashSet;
use ::std::iter;
use ::std::fmt::{self, Formatter, Display};
use ::std::time::Instant;

type Coord = i128;

#[derive(Copy, Clone, PartialEq, Eq, Debug)]
struct Vec3([Coord; 3]);

impl Vec3 {
    fn dot(self, other: Vec3) -> Coord {
        self.0.iter().zip(other.0.iter()).map(|(a, b)| a * b).sum()
    }
}

impl Display for Vec3 {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(f, "({}, {}, {})", self.0[0], self.0[1], self.0[2])
    }
}

impl Mul<Vec3> for Coord {
    type Output = Vec3;

    fn mul(self, mut vec: Vec3) -> Vec3 {
        for i in &mut vec.0 {
            *i *= self;
        }
        vec
    }
}

impl Add for Vec3 {
    type Output = Vec3;

    fn add(mut self, other: Vec3) -> Vec3 {
        for (i, n) in self.0.iter_mut().enumerate() {
            *n += other.0[i];
        }
        self
    }
}

impl Sub for Vec3 {
    type Output = Vec3;

    fn sub(self, other: Vec3) -> Vec3 {
        self + (-1 * other)
    }
}

#[derive(Clone, Debug)]
struct Tetrahedron([Vec3; 4]);

impl Default for Tetrahedron {
    fn default() -> Tetrahedron {
        Tetrahedron([
            Vec3([-1, -1, -1]),
            Vec3([-1,  1,  1]),
            Vec3([ 1, -1,  1]),
            Vec3([ 1,  1, -1]),
        ])
    }
}

impl Display for Tetrahedron {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(f, "Tetrahedron({}, {}, {}, {})", self.0[0], self.0[1], self.0[2], self.0[3])
    }
}

impl Tetrahedron {
    fn collides(&self, other: &Tetrahedron) -> bool {
        let mut othervecs = [3 * self.0[1], 3 * self.0[2], 3 * self.0[3]];
        let sum = self.0[0] + self.0[1] + self.0[2] + self.0[3];
        let mut same = 0;

        for (i, &vec) in self.0.iter().enumerate() {
            let sum = sum - vec;
            let vec = 3 * vec;
            let through = vec - sum;
            for (j, &u) in other.0.iter().enumerate() {
                let u = 3 * u;
                if u == vec { same += 1 }
                let up = (sum - u).dot(through);
                for &v in &other.0[j+1..] {
                    let v = 3 * v;
                    let edge = v - u;
                    let ep = edge.dot(through);

                    if up.signum() != ep.signum() || up.abs() >= ep.abs() {
                        continue
                    }

                    let intersection = ep * u + up * edge;
                    if othervecs.iter().enumerate().all(|(i, &ov)| {
                        let mid = othervecs[(i+1)%3] + othervecs[(i+2)%3];
                        let ov = 2 * ov - mid;
                        (2 * intersection - ep * mid).dot(ep * ov) > 0
                    }) {
                        return true
                    }
                }
            }

            if i != 3 { othervecs[i] = vec; }
        }
        if same == 4 { panic!("EQUAL TETRAHEDRA IN .collides()"); }
        false
    }

    // Mirroring also scales by 3
    fn mirror(&self, i: usize) -> Tetrahedron {
        let mut sum = Vec3([0; 3]);
        for (j, &vec) in self.0.iter().enumerate() {
            if j != i { sum = sum + vec; }
        }

        let mut copy = self.clone();
        copy.scale();

        copy.0[i] = 2 * sum - copy.0[i];
        copy.swap(i, 3);
        copy.rotate_left(i);

        copy
    }

    fn scale(&mut self) {
        for vec in self.0.iter_mut() {
            *vec = 3 * *vec;
        }
    }

    fn rotate_left(&mut self, n: usize) {
        self.0[..3].rotate_left(n)
    }

    fn swap(&mut self, a: usize, b: usize) {
        self.0.swap(a, b)
    }

    fn reverse(&mut self) {
        self.0.reverse()
    }
}

type EndpointIter<'a> = Box<dyn Iterator<Item = Endpoint> + 'a>;

#[derive(Debug, Clone)]
struct Endpoint {
    tree: Rc<TetraTree>,
    hedron: Rc<Tetrahedron>,
}

impl Endpoint {
    fn iter_endpoints(&self) -> EndpointIter {
        let mut hedron = Rc::clone(&self.hedron);
        //Rc::make_mut(&mut hedron).swap(0, 3);
        Rc::make_mut(&mut hedron).reverse();

        Box::new(self.clone().into_iter_directions()
            .chain(self.tree.iter_endpoints(
                Rc::new(TetraTree {
                    subtrees: [None, None, None],
                    hedron,
                })
            ))
        )
    }

    fn into_iter_directions(self) -> EndpointIter<'static> {
        Box::new(iter::successors(Some(self), |this| {
            let mut this = this.clone();
            Rc::make_mut(&mut this.tree).rotate_left(1);
            Rc::make_mut(&mut this.hedron).0[1..].rotate_left(1);
            Some(this)
        }).take(3))
    }

    fn iter_extensions(&self) -> EndpointIter {
        let mut tree = self.tree.as_ref().clone();
        tree.scale();

        let mut hedron = self.hedron.as_ref().clone();
        //hedron.swap(0, 3);
        hedron.reverse();
        hedron.scale();

        Box::new(Endpoint {
            tree: Rc::new(tree),
            hedron: Rc::clone(&self.hedron),
        }.into_iter_directions().filter_map(|endpoint| {
            let mut new = endpoint.hedron.mirror(3);
            new.swap(0, 3);
            if endpoint.tree.collides(&new) {
                None
            } else {
                let mut hedron = endpoint.hedron;
                Rc::make_mut(&mut hedron).scale();

                Some(Endpoint {
                    tree: Rc::new(TetraTree {
                        subtrees: [Some(endpoint.tree), None, None],
                        hedron,
                    }),
                    hedron: Rc::new(new),
                })
            }
        }).chain(self.tree.iter_extensions(Rc::new(TetraTree {
            subtrees: [None, None, None],
            hedron: Rc::new(hedron),
        }))))
    }

    fn iter_tetrahedra<'a>(&'a self)
      -> Box<dyn Iterator<Item = &Tetrahedron> + 'a> {
        Box::new(
          iter::once(self.hedron.as_ref()).chain(self.tree.iter_tetrahedra())
        )
    }
}

impl Default for Endpoint {
    fn default() -> Endpoint {
        Endpoint::from(Tetrahedron::default())
    }
}

impl From<Tetrahedron> for Endpoint {
    fn from(mut hedron: Tetrahedron) -> Endpoint {
        let mirrored = hedron.mirror(0);
        hedron.scale();

        Endpoint {
            tree: Rc::new(TetraTree {
                subtrees: [None, None, None],
                hedron: Rc::new(mirrored),
            }),
            hedron: Rc::new(hedron),
        }
    }
}

impl Hash for Endpoint {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        let mut stuff: Vec<_> = self.tree.hash_helper(1).collect();
        stuff.push(self.tree.len());
        stuff.sort();
        stuff.hash(hasher);
    }
}

impl PartialEq for Endpoint {
    fn eq(&self, other: &Endpoint) -> bool {
        self.iter_endpoints().any(|ep| ep.tree == other.tree)
    }
}

impl Eq for Endpoint {}

#[derive(Debug, Clone)]
struct TetraTree {
    subtrees: [Option<Rc<TetraTree>>; 3],
    hedron: Rc<Tetrahedron>,
}

impl TetraTree {
    fn iter_endpoints<'x>(&'x self, behind: Rc<TetraTree>) -> EndpointIter<'x> {
        let mut iterator = self.subtrees.iter().enumerate()
          .filter_map(|(i, opt)| opt.as_ref().map(|some| (i, some)));

        if let Some(first) = iterator.next() {
            let closure = move |(i, subtree): (usize, &'x Rc<TetraTree>)| -> EndpointIter<'x> {
                let mut behind = behind.as_ref().clone();
                behind.rotate_left(3-i);

                let mut this = self.clone();
                this.rotate_left(i);

                Rc::make_mut(&mut this.hedron).reverse();

                this.subtrees.swap(1, 2);
                this.subtrees[0] = Some(Rc::new(behind));

                for (j, subtree) in this.subtrees.iter_mut().enumerate().skip(1)
                  .filter_map(|(j, s)| s.as_mut().map(|s| (j, s))) {
                    Rc::make_mut(subtree).rotate_left(j);
                }

                subtree.iter_endpoints(Rc::new(this))
            };
            Box::new(closure(first).chain(iterator.flat_map(closure)))
        } else {
            let mut hedron = self.hedron.as_ref().clone();
            //hedron.swap(0, 3);
            hedron.reverse();
            Endpoint {
                tree: Rc::clone(&behind),
                hedron: Rc::new(hedron),
            }.into_iter_directions()
        }
    }

    fn rotate_left(&mut self, i: usize) {
        self.subtrees.rotate_left(i);
        Rc::make_mut(&mut self.hedron).rotate_left(i);
    }

    fn collides(&self, hedron: &Tetrahedron) -> bool {
        self.hedron.collides(hedron) ||
          self.subtrees.iter()
            .filter_map(Option::as_ref)
            .any(|subtree| subtree.collides(hedron))
    }

    fn scale(&mut self) {
        for subtree in self.subtrees.iter_mut().filter_map(Option::as_mut) {
            Rc::make_mut(subtree).scale();
        }
        Rc::make_mut(&mut self.hedron).scale();
    }

    fn iter_extensions(&self, behind: Rc<TetraTree>) -> EndpointIter {
        Box::new(self.subtrees.iter().enumerate().flat_map(move |(i, next)| {
            let mut behind = behind.as_ref().clone();
            behind.rotate_left(3-i);

            let mut this = self.clone();
            this.rotate_left(i);

            let hedron = Rc::make_mut(&mut this.hedron);
            hedron.reverse();

            this.subtrees.swap(1, 2);
            this.subtrees[0] = Some(Rc::new(behind));

            for (j, subtree) in this.subtrees.iter_mut().enumerate().skip(1)
              .filter_map(|(j, s)| s.as_mut().map(|s| (j, s))) {
                let subtree = Rc::make_mut(subtree);
                subtree.scale();
                subtree.rotate_left(j);
            }

            if let Some(next) = next {
                hedron.scale();
                next.iter_extensions(Rc::new(this))
            } else {
                let mut mirrored = hedron.mirror(3);
                mirrored.swap(0, 3);
                hedron.scale();

                if this.collides(&mirrored) {
                    Box::new(iter::empty()) as EndpointIter
                } else {
                    Box::new(iter::once(Endpoint {
                        tree: Rc::new(this),
                        hedron: Rc::new(mirrored),
                    }))
                }
            }
        }))
    }

    fn iter_tetrahedra<'a>(&'a self)
      -> Box<dyn Iterator<Item = &Tetrahedron> + 'a> {
        Box::new(iter::once(self.hedron.as_ref()).chain(
          self.subtrees.iter()
            .filter_map(Option::as_deref)
            .flat_map(TetraTree::iter_tetrahedra)
        ))
    }

    fn len(&self) -> usize {
        1usize + self.subtrees.iter()
              .filter_map(Option::as_deref).map(TetraTree::len).sum::<usize>()
    }

    fn hash_helper<'a>(&'a self, behind: usize)
      -> Box<dyn Iterator<Item = usize> + 'a> {
        let sub: Vec<_> = self.subtrees.iter().filter_map(Option::as_deref)
          .map(|a| (a, a.len())).collect();
        let sum = sub.iter()
          .map(|&(_, len)| len).sum::<usize>() + behind + 1;
        Box::new(iter::once(behind).chain(
            sub.into_iter().flat_map(move |(sub, len)|
                        iter::once(len).chain(sub.hash_helper(sum - len)))
        ))
    }
}

impl PartialEq for TetraTree {
    fn eq(&self, rhs: &TetraTree) -> bool {
        self.subtrees == rhs.subtrees
    }
}

impl Eq for TetraTree {}

fn main() {
    let verbose = std::env::args().skip(1).any(|arg| arg == "-v");
    let begin = Instant::now();

    println!("1: 1 [{}ms]", begin.elapsed().as_millis());
    if verbose {
        println!("{}\n--", Tetrahedron::default());
    }

    let mut polytets = HashSet::new();
    polytets.insert(Endpoint::default());

    for i in 2.. {
        println!("{}: {} [{}ms]", i, polytets.len(), begin.elapsed().as_millis());

        if verbose {
            for polytet in &polytets {
                for hedron in polytet.iter_tetrahedra() {
                    println!("{}", hedron);
                }
                println!("--");
            }
        }

        polytets = polytets.iter()
          .flat_map(Endpoint::iter_extensions)
          .collect();
    }
}

Try it online! The footer contains some compatability implementations because TIO's Rust is a little old. (This has already been reported and added to the list.)
Output:
1: 1 [0ms]
2: 1 [0ms]
3: 1 [2ms]
4: 4 [8ms]
5: 10 [35ms]
6: 39 [139ms]
7: 164 [738ms]
8: 767 [4328ms]
9: 3656 [31298ms]
10: 18186 [287871ms]
11: 91532 [3154716ms]

As you can see, it also reports how long it took. (These are cumulated times.) You can use the -v option to list all tetrahedra for each polytet.
I don't really have a good way of verifying the results beyond A267272(5). I hope it works, but I'm not sure.
The idea is that we store the polytet as a tree of tetrahedra that also encodes orientation. But for collision detection we need actual tetrahedra. We start with the tetrahedron with vertices (-1, -1, -1), (-1, 1, 1), (1, -1, 1), (1, 1, -1) and scale all tetrahedra by 3 for every term. This avoids the need for fractions.
Can probably be made faster, but I don't know how.


Haskell, 75 68 63 bytes

f(q:p:x)|p^q>p,x>[]=f$q-1:f(q:p-1:x):x|1<2=f$p^q:x
f[x]=x
f _=1

Try it online!

Takes input as a list in reversed order, since in Haskell it's easier to deal with the beginning of a list than with the end of it.

Now shorter and uglier!

Rules 3,4,5,6 are combined in the first line. The most important trick is realizing that p^q==p iff p==1||q==1 (where ^ is exponentiation and we're dealing with strictly positive numbers). We check the conditions to apply rule 6 (p and q greater than 1, at least three elements in the input) and if they are valid we do so recursively. If these conditions fail we know that either there is a 1 in the first two elements or there are just two elements in total: for both of this cases f(p^q:x) can solve the task.

The last two lines deal with inputs with less than two elements. They could be rewritten as a single line f x=last$1:x but the score would not change.

Below the original solution, no golfing tricks, just beautiful Haskell code:

f[]=1
f[p]=p
f[q,p]=p^q
f(1:x)=f x
f(_:1:x)=f x
f(q:p:x)=f$q-1:f(q:p-1:x):x

Try it online!


C using Saunderson's parameterisation and Berggren's tree

In 1740, Saunderson found the parameterisation that if (a, b, c) is a Pythagorean triple (i.e. a^2 + b^2 = c^2) then (a(2b-c)(2b+c), b(2a-c)(2a+c), 4abc) is a rational cuboid (this was before Euler studied them) with diagonals (c^3, a(5b^2+a^2), b(5a^2+b^2)). This doesn't generate all Euler bricks. Note that if the brick is primitive iff the Pythagorean triple is primitive.

If (x, y, z) is an Euler brick then so is (xy, xz, yz). Applying this once to a Saunderson brick creates a new brick which isn't Saunderson and which can be made primitive with division by ab. Applying the same transformation a second time gives the non-primitive xyz(x, y, z).

In 1934, Berggren discovered that the primitive Pythagorean triples form a ternary tree rooted at (3, 4, 5) which can be generated by a simple matrix multiplication and which contains each triple precisely once.

This implementation generates primitive Pythagorean triples and stores them in a stack, limiting the memory usage to 1.5GB. An earlier version used a circular buffer, but the stack gives much better results. This is probably a combination of fewer values being discarded and better cache locality.

Thanks to Steve Verrill for pointing out some bugs and for suggesting the use of a stack instead of a circular buffer. I've also followed him in removing the conjugate bricks for speed: previously the search space (minus the discarded branches) was exhausted within the two minutes, and there was value in spending time to get a few conjugates. But the new version can easily run for 5 minutes (as I discovered in the process of learning the value of the volatile keyword!), and most of the conjugates overflow, so on average the tests are wasted time.

#include <stdlib.h>
#include <inttypes.h>
#include <stdio.h>
#include <signal.h>
#include <string.h>

// Stack size. This is 1.5GB of memory.
#define N 33554432

typedef unsigned __int128 scalar;

typedef struct {
    scalar a, b, c;
} triple;

// Stack operations
#define take(st) st[--stp];
#define offer(A,B,C) if (stp < N) { st[stp].a=(A); st[stp].b=(B); st[stp].c=(C); stp++; }

volatile sig_atomic_t stop;

void handler(int sig, siginfo_t *siginfo, void *context) {
    stop = 1;
}

int main(int argc, char **argv) {
    // Register interrupt handler
    stop = 0;
    struct sigaction act;
    memset(&act, 0, sizeof(act));
    act.sa_sigaction = &handler;
    act.sa_flags = SA_SIGINFO;
    if (sigaction(SIGINT, &act, NULL) < 0) return 1;

    // L = 10^30
    const scalar L = ((scalar)0xc9f2c9cd0UL << 64) + 0x4674edea40000000UL;
    const scalar T = (scalar)1 << 64;   // used in an anti-overflow test

    // To avoid the optimiser removing the calculation of the bricks.
    int writeToStdOut = argc > 1;

    triple *st = (triple *)malloc(N * sizeof(triple));
    if (!st) return 2;

    uint32_t stp = 1; // Index of first empty space in stack
    st[0].a = 3; st[0].b = 4; st[0].c = 5;
    uint64_t count = 0;

    while (stp > 0) {
        if (stop) break;
        triple t = take(st);

        // Extend queue of Pythagorean triples
        offer(t.a + ((t.c - t.b) << 1), ((t.a + t.c) << 1) - t.b, ((t.a - t.b + t.c) << 1) + t.c)
        offer(t.a + ((t.c + t.b) << 1), ((t.a + t.c) << 1) + t.b, ((t.a + t.b + t.c) << 1) + t.c)
        offer(-t.a + ((t.c + t.b) << 1), ((-t.a + t.c) << 1) + t.b, ((-t.a + t.b + t.c) << 1) + t.c)

        // Saunderson brick
        scalar x = t.b * ( ((t.a << 1) >= t.c) ? ((t.a << 1) - t.c) : (t.c - (t.a << 1)) ) * ((t.a << 1) + t.c);
        scalar y = t.a * ((t.b << 1) - t.c) * ((t.b << 1) + t.c);
        scalar z = t.a * t.b * t.c << 2;
        scalar u = t.c * t.c * t.c;
        scalar v = t.b * (t.b * t.b + 5 * t.a * t.a);
        scalar w = t.a * (t.a * t.a + 5 * t.b * t.b);
        count++;
        if (writeToStdOut) {
            printf("Sides: 0x%016"PRIx64"%016"PRIx64, (uint64_t)(x >> 64), (uint64_t)x);
            printf(", 0x%016"PRIx64"%016"PRIx64, (uint64_t)(y >> 64), (uint64_t)y);
            printf(", 0x%016"PRIx64"%016"PRIx64, (uint64_t)(z >> 64), (uint64_t)z);
            printf("; diags 0x%016"PRIx64"%016"PRIx64, (uint64_t)(u >> 64), (uint64_t)u);
            printf(", 0x%016"PRIx64"%016"PRIx64, (uint64_t)(v >> 64), (uint64_t)v);
            printf(", 0x%016"PRIx64"%016"PRIx64"\n", (uint64_t)(w >> 64), (uint64_t)w);
        }
    }

    printf("%ld\n", count);

    return 0;
}

Compiles with gcc -O3 euler_brick.c -o euler_brick and handles SIGINT (Ctrl-C).  On my computer the earlier circular buffer version ran out of usably small Pythagorean triples after 85 seconds having found 843035517 (0.843 thousand million) Euler bricks. The new version runs to the two minutes (tested with timeout -sINT 2m ./euler_brick) and finds about 9.1 thousand million bricks. Exact numbers vary from run to run; the highest I've observed is 9113459216.

Note that this is single-threaded code. The process is embarrassingly parallel - just start each thread going down a different branch of the tree - and so the limitation to scaling it to multicore would be the shared memory bus.


05AB1E, 2 bytes
Code:
œß

Same algorithm as the Jelly answer. Computes all permutations of the input and pops out the smallest one.
Try it online!

A more efficient method is:
E[ß,Ž

Performs selection sort. Uses CP-1252 encoding.
Try it online!


Haskell, 11 bytes

zipWith max

Try it online!

Nothing much to explain.


Ration your integers and feed the people

Ruby, 100003 days/points (~274 years), 5 days before someone dies

  For every day your city goes without anyone dying, you get one point.

I shall abuse this rule as much as possible!

  Make sure you output how many days your city lasted before someone died.

Ok, I did. You didn't say anything about that affecting your score.

#input = STDIN.read
input = "1000x90
2500x80
3000x150
2500x200" # temporary debugging tool

food = 100000

input = input.split.map{|x| x.split('x').map &:to_i }
onlyPersonToFeedWeight = input.sort_by! {|a|
  a[1] # weight of person
}.first[1] # find the lightest weighing person
foodForOnePerson =  ((onlyPersonToFeedWeight - 1) / 20.0 + 1).ceil # EAT = (WEIGHT - 1) / 20 + 1

# you can see where this is going

daysNobodyDied = 0
daysSomeoneDied = 0

# first kill off all these overweight people
daysNobodyDied += 4
food -= foodForOnePerson
daysSomeoneDied += 1 # it's only all but one person in the city, don't worry

# I have a good feeling about this now
# ... I'm evil

loop {
  daysNobodyDied += 4
  food -= foodForOnePerson
  if food >= 0
    daysNobodyDied += 1
  else
    daysSomeoneDied += 1
    break
  end
}

puts "Survived for #{daysNobodyDied} days"
puts "There were #{daysSomeoneDied} days in which someone died"
puts "The first person died on day 5"

Output:

Survived for 100003 days
There were 2 days in which someone died
The first person died on day 5

I suggest you read the comments in the code first; they're quite amusing. ;) (Code is intentionally verbose.)

The strategy is simple:

On the first five days, only feed the lightest person (on the fifth day). Then everyone else dies so you don't have to worry about them.
Continue to starve this poor man with no friends or family by only feeding him once every five days until you run out of food.
The man will probably die before you run out of food since it will now last 274 years.

Does this make me evil or something?

Oh, and by the way, if he was lying down the whole time, he'd have a better than even chance that a bird would poop in his mouth. (Assuming the birds didn't starve.) Thanks for the... interesting fact, @Synthetica :-P


Retina, 71 bytes

/[\d.,]+/_/\d/&/\..*\./^&(`,

^0+

^\B
0
'.&`\.?0+$

/^\d+/_r`\B...
,$&

Try it online! Link includes test cases. Explanation:

/[\d.,]+/_

Find all runs of digits, .s and ,s.

/\d/&

Ignore those with no digits.

/\..*\./^&

Ignore those with two .s.

(`

Process the rest of the script on each remaining match.

,

Delete all commas.

^0+

Delete all leading zeros.

^\B
0

Insert a leading zero if the number does not begin with a digit.

'.&`

If the number contains a ....

\.?0+$

... delete trailing zeros and any preceding ..

/^\d+/_

On the part of the number before the ....

r`\B...
,$&

Match groups of three starting from the end, but leave at least one digit at the beginning, and insert commas before each match.


Golfscript, 27 22 bytes

{.9>{.10/\10%2*-f}*}:f

You can use it this way:

1000f

Explanation

{.9>{.10/\10%2*-f}*}:f
{                  }:f    # Define block 'f' (similar to a function)
 .                        # Duplicate the first value of the stack
  9>{            }*       # If the value on top of the stack is greater than 9 then the block is executed
     .10/\10%2*-          # Same as nb/10 - (nb%10 * 2) with some stack manipulations '.' to duplicate the top of the stack and '\' to swap the the first and second element of the stack
                f         # Execute block 'f'

5 bytes saved thanks to Dennis !


Fewest disk writes to defrag multiple files

Python 3, 295 bytes

S,F=eval(input());d=[0]*S;E=enumerate
for n,P in F:
 for j,p in E(P):d[int(p)]=n,j
Z=[(d,())]
while Z:d,p=Z.pop(0);any(e and(e[0],e[1]+1)in d and(S<j+2or(e[0],e[1]+1)!=d[j+1])for j,e in E(d))or print(p).q;{d[j]or exec("D=d[:];D[j]=e;D[k]=0;Z+=(D,p+(e,j)),")for j,_ in E(d)for k,e in E(d)if d[k]}

Try it online!

Another test case
Input:
   7 ALEF=6,4,0 BET=5,1 GIMEL=3

Initial disk state:
   A2 B1 __ G0 A1 B0 A0

Solution:
   ALEF:2>2
   ALEF:0>0
   BET:1>6
   ALEF:1>1

Visualized solution:
   A2 B1 __ G0 A1 B0 A0
   __ B1 A2 G0 A1 B0 A0
   A0 B1 A2 G0 A1 B0 __
   A0 __ A2 G0 A1 B0 B1
   A0 A1 A2 G0 __ B0 B1

Ungolfed version.


Pyth, 15 bytes

s*VSsM^^LTUQ2SQ

Demonstration. Test harness.

Note: Input in any python sequence format, such as a,b,c, or [a, b, c]. Fails on a.

This will be an explanation for the example input 5,8,6,8.

^LTUQ: This is a list of powers of 10, out to the length of Q. [1, 10, 100, 1000].

^ ... 2: Then, we take pairs of powers of 10. [[1, 1], [1, 10], ....

sM: Then, we sum those pairs. [2, 11, 101, ... Each number repesents the value of a grid location. The value of the bottom right corner is 2, because the digit placed there is in the ones place of the two numbers it is in. Note that 16 values were generated, even though we only need 4. This will be handled shortly.

S: Sort the value in increasing order. [2, 11, 11, 20, 101, .... Note that the only values which are relevant for this input are the first 4, because this square will not have hundreds or thousands places.

SQ: Sort the input in ascending order. [5, 6, 8, 8]

*V: Vectorized multiplication over the two lists. Pyth's vectorized multiplication truncates the longer input, so this performs [5*2, 6*11, 8*11, 8*20], equivalent to filling in the grid, smallest to largest, bottom right to top left.

s: Sum the results, 324. Printing is implicit.


Parentheses sequences in lexicographical order

Perl 6, 36 bytes

{grep {try !.EVAL},[X~] <[ ]>xx$_*2}

Try it online!

Finds all lexographically sorted combinations of \$2n\$ []s and filters the ones that EVAL correctly. Note that all valid combinations (even stuff like [][]) evaluate to [] (which is falsey, but we not it (!) to distinguish from try returning Nil)

Explanation:

{                                  }  # Anonymous code block
                        <[ ]>         # Create a list of ("[", "]")
                             xx$_*2   # Duplicate this 2n times
                   [X~]               # Find all possible combinations
 grep {          },                   # Filter from these
            .EVAL                     # The EVAL'd strings
       try !                          # That do not throw an error


Implementing bool() without any conditionals

Python - 122 chars - 50*13 types = -528

def b(x=False):
 try:return[False][x]
 except IndexError:return True
 except:
  try:return b(len(x))
  except:return True

Works for the following built-in types (as listed in §3.2 The standard type hierarchy)

NotImplemented
Ellipsis
int
long
bool
string
unicode
tuple
list
bytearray
set
frozenset
dict


Java, 122 121 98 97 bytes

int c(int n){int a=0,b=0,c=n;for(;n-->0;c+=a=((--b+"").indexOf(55)&b%7)>>31);return a<0?-b:c(c);}

-23 bytes thanks to @Nevay.
-1 byte thanks to @Neil.
Explanation:
Try it here.
int c(int n){                            // Method with integer as parameter and return-type
  int a=0,                               //  Flag integer
      b=0,                               //  Regular counter
      c=n;                               //  7-counter
  for(;n-->0;                            //  Loop over the input
    c+=                                  //   Append `c` with:
       a=                                //    Set `a` to:
         ((--b+"").indexOf(55)&b&7)      //     If `b` is divisible by or contains 7:
                                         //     (and decrease `b` by 1 in the process)
                                   >>31  //      Bitwise right shift so `a` is either `-1` or `0`
  );                                     //  End of loop
  return a<0?                            //  If `a` is now -1:
    -b                                   //   Return the regular counter `b` (as positive)
   :                                     //  Else:
    c(c);                                //   Recursive call with 7-counter `c` as input
}                                        // End of method


Retina 0.8.2, 44 bytes

i`(\bnot?\W+|n't\b)(.*?)(\bnot?\W+|n't\b)
$2

Try it online! Link includes test cases.


Python 2, 167 129 bytes

-36 bytes mostly* from using Maltysen's idea of catching ctrl-c using an exception - go give credit!
-4 bytes thanks to DLosc (init n and b to 0 rather than f())
-1 byte thanks to FlipTack (use p^=1 rather than p=1-p)
-2 bytes thanks to Felipe Nardi Batista (remove precision specifiers)

import time
f=time.time
n=b=p=0
while 1:
 try:n=[n,f()][p];t=n-b;print'\r%02d:%02d'%(t/60%60,t%60),
 except:b=[b-n+f(),b][p];p^=1

Works the same as my original, below, but with the control key sequence of ctrl+c.
(Tested by me with Python 2.7.8 on Windows 7, 64bit;
Tested by Brian Minton with Python 2.7.13 on linux, 64bit)

* also collapsed if statement to a list lookup in order to get the try as a one-liner.

My original:

import time,msvcrt as m
f=time.time
n=b=p=0
while 1:
 if m.kbhit()and m.getch()==b'p':b=[b-n+f(),b][p];p^=1
 if p:n=f()
 t=n-b;print'\r%0.2d:%0.2d'%(t/60%60,t%60),

(Tested by me with Python 2.7.8 on Windows 7, 64bit - this code, however, is Windows specific due to the use of the msvcrt library)

The control key is 'p'.

n and b are initialised to the same value at start-up, giving an "offset" of 0; p is initialised to 0, indicating a paused state.

Whenever the control key is pressed the value of p is switched. When switching from a paused state to an active state b is updated to a new value keeping any current offset from the previous active state(s) with b-n.

During an active state n is repeatedly updated to the current time by calling time.time().

The difference between n and b, t, is then the total number of seconds (including a fractional part) elapsed during active state(s).

The minutes elapsed are then t/60 and each of the minutes and seconds are displayed mod 60 with (t/60%60,t%60). Leading zeros are prepended for each using string formatting of the integer part with '...%0.2d...'. Printing a tuple (the trailing ,) where the first item has a leading carriage return (the \r) causes the previously printed text to be overwritten.


MATL, 19 bytes

!3#f!Dx0Gg!XsYshDq!

Input uses ; as row separator.

Try it online! Or verify all test cases: 1, 2, 3, 4, 5.

Explanation

!     % Implicit input. Transpose
3#f   % 3-output version of find: it takes all nonzero values and pushes
      % their column indices, row indices, and values, as column vectors
!     % Transpose into a row vector
D     % Display (and pop) vector of values
x     % Delete vector of row values
0     % Push 0
G     % Push input
g     % Convert to logical: nonzeros become 1
!     % Transpose
Xs    % Sum of columns. Gives a row vector
Ys    % Cumulative sum
h     % Prepend the 0 that's below on the stack
D     % Display (and pop) that vector
q     % Subtract 1 from the vector of row indices
!     % Transpose into a row vector. Implicitly display


Python 2, 45 bytes

-3 bytes thanks to Rod. -2 bytes thanks to ovs.

lambda s:len(s)<81*s.isalnum()<'VEVO'==s[-4:]

Try it online!

A regex solution turns out to be longer.

lambda s:re.match('^[^\W_]{0,76}VEVO$',s)
import re


J, 28 characters
((C.!.2=_1^i.&0)&.".&.stdin''

The input order is row-major with rows read alternatingly left to right and right to left in a single path across the table. Assumes the zero belongs to the top left corner.
Usage on Windows:
<nul set /p="0 1 2 3 7 6 5 4 8 9 10 11 15 14 13 12" | jconsole c:\...\15.jhs

Explanation:

<nul set /p= is used to prevent a newline in the input, that echo produces that ". doesn't like. Of course, Unix supports echo /n.
v&.".&.stdin'' reads "v under parse under stdin" meaning "input, then parse the input, then do v, then undo parse (= format), then undo input (=output)". 1!:1]3 is one character shorter, but it does not have a defined inverse.
C.!.2 means "permutation parity". It returns either 1 (even parity) or _1 (odd parity). That is, _1^inversions
_1^i.&0 means "-1 to the power of index of 0".
thus, C.!.2=_1^i.&0 means "does the permutation parity equal the hole position parity?"

This works for a 4x4 board, but if the desired end position is row-major left-to-right, then the permutation for the solved position has an odd number of inversions, and thus odd parity. Also, the parity is reversed (for any input order) when the desired hole position moves from upper left to bottom right. In both cases, the fix is one character: add - after = to reverse the expected parity.
Proof of correctness:
After each move, the zero exchanges a position with some number, flipping the permutation parity. The zero also alternates between white and black checkerboard positions, indicated by odd and even positions in the input ordering. Thus, this condition is neccessary. It is also sufficient by the counting argument: it is common knowledge that exactly half of the positions is solvable. This condition filters out exactly half of the possible positions.


C++, 97 95 93 91 86 83 82 81 79 characters

  NNWSWNNSENESESWSSWNSEENWWNWSSEWWNENWEENWSWNWSSENENWNWNESENESESWNWSESEWWNENWNEES

My strategy is fairly simple - an evolution algorithm that can grow, shrink, swap elements of and mutate valid sequences. My evolution logic is now nearly the same as @Sp3000's, as his was an improvement over mine.

However, my implementation of the maze logic is rather nifty. This allows me to check if strings are valid at blistering speed. Try to figure it out by looking at the comment, do_move and the Maze constructor.

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <iostream>
#include <random>
#include <set>
#include <vector>

/*
    Positions:

        8, 10, 12
        16, 18, 20
        24, 26, 28

    By defining as enum respectively N, W, E, S as 0, 1, 2, 3 we get:

        N: -8, E: 2, S: 8, W: -2
        0: -8, 1: -2, 2: 2, 3: 8

    To get the indices for the walls, average the numbers of the positions it
    would be blocking. This gives the following indices:

        9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27

    We'll construct a wall mask with a 1 bit for every position that does not
    have a wall. Then if a 1 shifted by the average of the positions AND'd with
    the wall mask is zero, we have hit a wall.
*/

enum { N = -8, W = -2, E = 2, S = 8 };
static const int encoded_pos[] = {8, 10, 12, 16, 18, 20, 24, 26, 28};
static const int wall_idx[] = {9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27};
static const int move_offsets[] = { N, W, E, S };

int do_move(uint32_t walls, int pos, int move) {
    int idx = pos + move / 2;
    return walls & (1ull << idx) ? pos + move : pos;
}

struct Maze {
    uint32_t walls;
    int start, end;

    Maze(uint32_t maze_id, int start, int end) {
        walls = 0;
        for (int i = 0; i < 12; ++i) {
            if (maze_id & (1 << i)) walls |= 1 << wall_idx[i];
        }
        this->start = encoded_pos[start];
        this->end = encoded_pos[end];
    }

    uint32_t reachable() {
        if (start == end) return false;

        uint32_t reached = 0;
        std::vector<int> fill; fill.reserve(8); fill.push_back(start);
        while (fill.size()) {
            int pos = fill.back(); fill.pop_back();
            if (reached & (1 << pos)) continue;
            reached |= 1 << pos;
            for (int m : move_offsets) fill.push_back(do_move(walls, pos, m));
        }

        return reached;
    }

    bool interesting() {
        uint32_t reached = reachable();
        if (!(reached & (1 << end))) return false;
        if (std::bitset<32>(reached).count() <= 4) return false;

        int max_deg = 0;
        uint32_t ends = 0;
        for (int p = 0; p < 9; ++p) {
            int pos = encoded_pos[p];
            if (reached & (1 << pos)) {
                int deg = 0;
                for (int m : move_offsets) {
                    if (pos != do_move(walls, pos, m)) ++deg;
                }
                if (deg == 1) ends |= 1 << pos;
                max_deg = std::max(deg, max_deg);
            }
        }

        if (max_deg <= 2 && ends != ((1u << start) | (1u << end))) return false;

        return true;
    }
};

std::vector<Maze> gen_valid_mazes() {
    std::vector<Maze> mazes;
    for (int maze_id = 0; maze_id < (1 << 12); maze_id++) {
        for (int points = 0; points < 9*9; ++points) {
            Maze maze(maze_id, points % 9, points / 9);
            if (!maze.interesting()) continue;
            mazes.push_back(maze);
        }
    }

    return mazes;
}

bool is_solution(const std::vector<int>& moves, Maze maze) {
    int pos = maze.start;
    for (auto move : moves) {
        pos = do_move(maze.walls, pos, move);
        if (pos == maze.end) return true;
    }

    return false;
}

std::vector<int> str_to_moves(std::string str) {
    std::vector<int> moves;
    for (auto c : str) {
        switch (c) {
        case 'N': moves.push_back(N); break;
        case 'E': moves.push_back(E); break;
        case 'S': moves.push_back(S); break;
        case 'W': moves.push_back(W); break;
        }
    }

    return moves;
}

std::string moves_to_str(const std::vector<int>& moves) {
    std::string result;
    for (auto move : moves) {
             if (move == N) result += "N";
        else if (move == E) result += "E";
        else if (move == S) result += "S";
        else if (move == W) result += "W";
    }
    return result;
}

bool solves_all(const std::vector<int>& moves, std::vector<Maze>& mazes) {
    for (size_t i = 0; i < mazes.size(); ++i) {
        if (!is_solution(moves, mazes[i])) {
            // Bring failing maze closer to begin.
            std::swap(mazes[i], mazes[i / 2]);
            return false;
        }
    }
    return true;
}

template<class Gen>
int randint(int lo, int hi, Gen& gen) {
    return std::uniform_int_distribution<int>(lo, hi)(gen);
}

template<class Gen>
int randmove(Gen& gen) { return move_offsets[randint(0, 3, gen)]; }

constexpr double mutation_p = 0.35; // Chance to mutate.
constexpr double grow_p = 0.1; // Chance to grow.
constexpr double swap_p = 0.2; // Chance to swap.

int main(int argc, char** argv) {
    std::random_device rnd;
    std::mt19937 rng(rnd());
    std::uniform_real_distribution<double> real;
    std::exponential_distribution<double> exp_big(0.5);
    std::exponential_distribution<double> exp_small(2);

    std::vector<Maze> mazes = gen_valid_mazes();

    std::vector<int> moves;
    while (!solves_all(moves, mazes)) {
        moves.clear();
        for (int m = 0; m < 500; m++) moves.push_back(randmove(rng));
    }

    size_t best_seen = moves.size();
    std::set<std::vector<int>> printed;
    while (true) {
        std::vector<int> new_moves(moves);
        double p = real(rng);

        if (p < grow_p && moves.size() < best_seen + 10) {
            int idx = randint(0, new_moves.size() - 1, rng);
            new_moves.insert(new_moves.begin() + idx, randmove(rng));
        } else if (p < swap_p) {
            int num_swap = std::min<int>(1 + exp_big(rng), new_moves.size()/2);
            for (int i = 0; i < num_swap; ++i) {
                int a = randint(0, new_moves.size() - 1, rng);
                int b = randint(0, new_moves.size() - 1, rng);
                std::swap(new_moves[a], new_moves[b]);
            }
        } else if (p < mutation_p) {
            int num_mut = std::min<int>(1 + exp_big(rng), new_moves.size());
            for (int i = 0; i < num_mut; ++i) {
                int idx = randint(0, new_moves.size() - 1, rng);
                new_moves[idx] = randmove(rng);
            }
        } else {
            int num_shrink = std::min<int>(1 + exp_small(rng), new_moves.size());
            for (int i = 0; i < num_shrink; ++i) {
                int idx = randint(0, new_moves.size() - 1, rng);
                new_moves.erase(new_moves.begin() + idx);
            }
        }

        if (solves_all(new_moves, mazes)) {
            moves = new_moves;

            if (moves.size() <= best_seen && !printed.count(moves)) {
                std::cout << moves.size() << " " << moves_to_str(moves) << "\n";
                if (moves.size() < best_seen) {
                    printed.clear(); best_seen = moves.size();
                }
                printed.insert(moves);
            }
        }
    }

    return 0;
}


Retina 0.8.2, 66 bytes

.+
$*
1
RL
^(.+)RL\1$
$1R¶L$1
^(.+)\1$
$1
(.)(..?)(?!.\b)
$1$.2$*.

Try it online! Link includes test cases. Explanation:

.+
$*

Convert the input to unary.

1
RL

Alternate between hands.

^(.+)RL\1$
$1R¶L$1

If there are an odd number of beats then divide the output in the middle.

^(.+)\1$
$1

But if there are an even number of beats then just use one copy.

(.)(..?)(?!.\b)
$1$.2$*.

Try to match groups of three beats, but without leaving a lone beat at the end, and replace the offbeats with .s.


Python 3, 70 bytes

from time import*
lambda s:strftime("%b%y",strptime(s,"%Y%m")).upper()

This uses the built-in strftime and strptime functions.

For 1 byte more, here's a version which parses the string manually:

lambda s:" JFMAMJJASONDAEAPAUUUECOENBRRYNLGPTVC"[int(s[4:])::12]+s[2:4]

This encodes the month names in an interesting way (thanks to Henry Gomersall for saving a byte).


Write a program to fabricate elaborate acronyms

Jelly, 8 bytes

ŒtḟŒlp”.

Explanation:

ŒtḟŒlp”.
Œt       # Convert the string to Title Case (lowercases then uppercase beginnings of word)
   Œl    # And on the other side, convert the string to lowercase
  ḟ      # filter: remove the elements from the right side (lowercase) from the left side (Title Cased). Only leaves the initials
     p”. # Cartesian product with a dot.

Golfed down under the Pyth one, thanks Dennis and Fry!


Mathematica : 49

Plot[Sin[x+a],{x,0,9},Axes->None]~Animate~{a,0,2Pi}

The flickering is a GIF-produced artifact. Runs smoothly on the screen.


Jelly, 15 bytes

⁹R2*‘ṡ5ḟ@€µEÐfQ

TryItOnline
All test cases also at TryItOnline

Returns a list containing one list containing the odd one out.

How?

⁹R2*‘ṡ5ḟ@€µEÐfQ - Main link, a (list)
⁹               - literal 256 (saving a byte over literal 30)
 R              - range, [1,2,3,...]
  2*            - 2 ** x, [2,4,8,...]
    ‘           - increment, [3,5,9,...]
     ṡ5         - all contiguous slices of length 5
       ḟ@€      - filter with reversed arguments for each
          µ     - monadic chain separation
            Ðf  - filter on condition:
           E    - all equal (those previously filtered lists with only one value)
              Q - unique (there can be two, but both will have the same odd-one-out)


Python 3.8, 56 bytes
lambda a,b:(x:=a[:b].split(' '))and[len(x[-1]),len(x)-1]

Try it online!


Pyth, 6 bytes

suaV+e

Test suite

This program is very suave. 0 (falsy) means all zeroes, anything else (truthy) means not all zeroes.

How it works:

suaV+e
suaV+eGGGQ    Variable introduction.
 u       Q    Apply the following function repeatedly to its previous result,
              starting with the input. Stop when a value occurs which has
              occurred before.
  aV          Take the absolute differences between elements at the same indices of
        G     The previous list and
    +eGG      The previous list with its last element prepended.
s             The repeated value is returned. Sum its entries. This is zero (falsy)
              if and only if the entries are all zero.


Java (OpenJDK 8), 164 110 bytes

a->{int i=0;for(;!(i+"").matches("2{"+a+"}.*")|new String(new char[i]).matches(".?|(..+)\\1+");i++);return i;}

Thanks to @FryAmTheEggman for a bunch of bytes!

Try it online!


Count balanced binary strings matching any of a set of masks

ruby, pretty fast, but it depends upon the input

Now speed-up by a factor of 2~2.5 by switching from strings to integers.

Usage:

cat <input> | ruby this.script.rb

Eg.

mad_gaksha@madlab ~/tmp $ ruby c50138.rb < c50138.inp2
number of matches: 298208861472
took 0.05726237 s

The number of matches for a single mask a readily calculated by the binomial coefficient. So for example 122020 needs 3 2s filled, 1 0 and 2 1. Thus there are nCr(3,2)=nCr(3,1)=3!/(2!*1!)=3 different binary strings matching this mask.

An intersection between n masks m_1, m_2, ... m_n is a mask q, such that a binary string s matches q only iff it matches all masks m_i.

If we take two masks m_1 and m_2, its intersection is easily computed. Just set m_1[i]=m_2[i] if m_1[i]==2. The intersection between 122020 and 111222 is 111020:

122020 (matched by 3 strings, 111000 110010 101010)
111222 (matched by 1 string, 111000)
111020 (matched by 1 string, 111000)

The two individual masks are matched by 3+1=4 strings, the interesection mask is matched by one string, thus there are 3+1-1=3 unique strings matching one or both masks.

I'll call N(m_1,m_2,...) the number of strings matched all m_i. Applying the same logic as above, we can compute the number of unique strings matched by at least one mask, given by the inclusion exclusion principle and see below as well, like this:

N(m_1) + N(m_2) + ... + N(m_n) - N(m_1,m_2) - ... - N(m_n-1,m_n) + N(m_1,m_2,m_3) + N(m_1,m_2,m_4) + ... N(m_n-2,m_n-1,m_n) - N(m_1,m_2,m_3,m_4) -+ ...

There are many, many, many combinations of taking, say 30 masks out of 200.

So this solution makes the assumption that not many high-order intersections of the input masks exist, ie. most n-tuples of n>2 masks will not have any common matches.

Use the code here, the code at ideone may be out-dated.

Test case 1: number of matches: 6
Test case 2: number of matches: 184756
Test case 3: number of matches: 298208861472
Test case 4: number of matches: 5

I added a function remove_duplicates that can be used to pre-process the input and delete masks m_i such that all strings that match it also match another mask m_j.,For the current input, this actually takes longer as there are no such masks (or not many), so the function isn't applied to the data yet in the code below.

Code:

# factorial table
FAC = [1]
def gen_fac(n)
  n.times do |i|
    FAC << FAC[i]*(i+1)
  end
end

# generates a mask such that it is matched by each string that matches m and n
def diff_mask(m,n)
  (0..m.size-1).map do |i|
    c1 = m[i]
    c2 = n[i]
    c1^c2==1 ? break : c1&c2
  end
end

# counts the number of possible balanced strings matching the mask
def count_mask(m)
  n = m.size/2
  c0 = n-m.count(0)
  c1 = n-m.count(1)
  if c0<0 || c1<0
    0
  else
    FAC[c0+c1]/(FAC[c0]*FAC[c1])
  end
end

# removes masks contained in another
def remove_duplicates(m)
  m.each do |x|
    s = x.join
    m.delete_if do |y|
      r = /\A#{s.gsub(?3,?.)}\Z/
      (!x.equal?(y) && y =~ r) ? true : false
    end
  end
end

#intersection masks of cn masks from m.size masks
def mask_diff_combinations(m,n=1,s=m.size,diff1=[3]*m[0].size,j=-1,&b)
  (j+1..s-1).each do |i|
    diff2 = diff_mask(diff1,m[i])
    if diff2
      mask_diff_combinations(m,n+1,s,diff2,i,&b) if n<s
      yield diff2,n
    end
  end
end

# counts the number of balanced strings matched by at least one mask
def count_n_masks(m)
  sum = 0
  mask_diff_combinations(m) do |mask,i|
    sum += i%2==1 ? count_mask(mask) : -count_mask(mask)
  end
  sum
end

time = Time.now

# parse input
d = STDIN.each_line.map do |line|
  line.chomp.strip.gsub('2','3')
end
d.delete_if(&:empty?)
d.shift
d.map!{|x|x.chars.map(&:to_i)}

# generate factorial table
gen_fac([d.size,d[0].size].max+1)

# count masks
puts "number of matches: #{count_n_masks(d)}"
puts "took #{Time.now-time} s"

This is called the inclusion exclusion principle, but before somebody had pointed me to it I had my own proof, so here it goes. Doing something yourself feels great though.

Let us consider the case of 2 masks, call then 0 and 1, first. We take every balanced binary string and classify it according to which mask(s) it matches. c0 is the number of those that match only mask 0, c1 the nunber of those that match only 1, c01 those that match mask 0 and 1.

Let s0 be the number sum of the number of matches for each mask (they may overlap). Let s1 be the sum of the number of matches for each pair (2-combination) of masks. Let s_i be the sum of the number of matches for each (i+1) combination of masks. The number of matches of n-masks is the number of binary strings matching all masks.

If there are n masks, the desired output is the sum of all c's, ie. c = c0+...+cn+c01+c02+...+c(n-2)(n-1)+c012+...+c(n-3)(n-2)(n-1)+...+c0123...(n-2)(n-1). What the program computes is the alternating sum of all s's, ie. s = s_0-s_1+s_2-+...+-s_(n-1). We wish to proof that s==c.

n=1 is obvious. Consider n=2. Counting all matches of mask 0 gives c0+c01 (the number of strings matching only 0 + those matching both 0 and 1), counting all matches of 1 gives c1+c02. We can illustrate this as follows:

0: c0 c01
1: c1 c10

By definition, s0 = c0 + c1 + c12. s1 is the sum number of matches of each 2-combination of [0,1], ie. all uniqye c_ijs. Keep in mind that c01=c10.

s0 = c0 + c1 + 2 c01
s1 = c01
s = s0 - s1 = c0 + c1 + c01 = c

Thus s=c for n=2.

Now consider n=3.

0  : c0 + c01 + c02 + c012
1  : c1 + c01 + c12 + c012
2  : c2 + c12 + c02 + c012
01 : c01 + c012
02 : c02 + c012
12 : c12 + c012
012: c012

s0 = c0 + c1 + c2 + 2 (c01+c02+c03) + 3 c012
s1 = c01 + c02 + c12 + 3 c012
s2 = c012

s0 = c__0 + 2 c__1 + 3 c__2
s1 =          c__1 + 3 c__2
s2 =                   c__2

s = s0 - s1 + s2 = ... = c0 + c1 + c2 + c01 + c02 + c03 + c012 = c__0 + c__1 + c__2 = c

Thus s=c for n=3. c__i represents the of all cs with (i+1) indices, eg c__1 = c01 for n=2 and c__1 = c01 + c02 + c12 for n==3.

For n=4, a pattern starts to emerge:

0:   c0 + c01 + c02 + c03 + c012 + c013 + c023 + c0123
1:   c1 + c01 + c12 + c13 + c102 + c103 + c123 + c0123
2:   c2 + c02 + c12 + c23 + c201 + c203 + c213 + c0123
3:   c3 + c03 + c13 + c23 + c301 + c302 + c312 + c0123

01:  c01 + c012 + c013 + c0123
02:  c02 + c012 + c023 + c0123
03:  c03 + c013 + c023 + c0123
12:  c11 + c012 + c123 + c0123
13:  c13 + c013 + c123 + c0123
23:  c23 + c023 + c123 + c0123

012:  c012 + c0123
013:  c013 + c0123
023:  c023 + c0123
123:  c123 + c0123

0123: c0123

s0 = c__0 + 2 c__1 + 3 c__2 + 4 c__3
s1 =          c__1 + 3 c__2 + 6 c__3
s2 =                   c__2 + 4 c__3
s3 =                            c__3

s = s0 - s1 + s2 - s3 = c__0 + c__1 + c__2 + c__3 = c

Thus s==c for n=4.

In general, we get binomial coefficients like this (↓ is i, → is j):

   0  1  2  3  4  5  6  .  .  .

0  1  2  3  4  5  6  7  .  .  .
1     1  3  6  10 15 21 .  .  .
2        1  4  10 20 35 .  .  .
3           1  5  15 35 .  .  .
4              1  6  21 .  .  .
5                 1  7  .  .  .
6                    1  .  .  .
.                       .
.                          .
.                             .

To see this, consider that for some i and j, there are:

x = ncr(n,i+1): combinations C for the intersection of (i+1) mask out of n
y = ncr(n-i-1,j-i): for each combination C above, there are y different combinations for the intersection of (j+2) masks out of those containing C
z = ncr(n,j+1): different combinations for the intersection of (j+1) masks out of n

As that may sound confusing, here's the defintion applied to an example. For i=1, j=2, n=4, it looks like this (cf. above):

01:  c01 + c012 + c013 + c0123
02:  c02 + c012 + c023 + c0123
03:  c03 + c013 + c023 + c0123
12:  c11 + c012 + c123 + c0123
13:  c13 + c013 + c123 + c0123
23:  c23 + c023 + c123 + c0123

So here x=6 (01, 02, 03, 12, 13, 23), y=2 (two c's with three indices for each combination), z=4 (c012, c013, c023, c123).

In total, there are x*y coefficients c with (j+1) indices, and there are z different ones, so each occurs x*y/z times, which we call the coefficient k_ij. By simple algebra, we get k_ij = ncr(n,i+1) ncr(n-i-1,j-i) / ncr(n,j+1) = ncr(j+1,i+1).

So the index is given by k_ij = nCr(j+1,i+1) If you recall all the defintions, all we need to show is that the alternating sum of each column gives 1.

The alternating sum s0 - s1 + s2 - s3 +- ... +- s(n-1) can thus be expressed as:

s_j = c__j * ∑［(-1)^(i+j) k_ij］ for i=0..n-1
     = c__j * ∑［(-1)^(i+j) nCr(j+1,i+1)］ for i=0..n-1
     = c__j * ∑［(-1)^(i+j) nCr(j+1,i)］｛i=0..n｝ - (-1)^0 nCr(j+1,0)
     = (-1)^j c__j

s   = ∑［(-1)^j  s_j］ for j = 0..n-1
    = ∑［(-1)^j (-1)^j c__j)］ for j=0..n-1
    = ∑［c__j］ for j=0..n-1
    = c

Thus s=c for all n=1,2,3,...


Find a binary needle in a decimal haystack

05AB1E, 10 8 bytes

Takes the needle in binary to save 1 byte.

-2 bytes thanks to Emigna

œJÙʒbŒIå

Try it online!

œJÙʒbŒIå   Arguments: a, n
œJÙ        Get all unique permutations of a
   ʒ       Filter: Keep if following code returns true
    b      Convert to binary
     Œ     Get all substrings
      Iå   Check if substrings contain n
           Implicit output of filtered list


Jelly, 28 23 22 bytes

1 byte thanks to Dennis.

26RØAṙ;U$;Œl$
;Zẇ@þ¢FS

Try it online!

Takes an array of strings.


Python 3.8, 81, 79, 75 bytes

Using the walrus operator :=:

lambda k,l:[i for j,i in sorted((v,k)for k,v in enumerate(l))if(k:=k-j)>=0]

Try it online!

-2 bytes thanks to @JoKing

-4 bytes thanks to @justhalf

Python 3, 158, 137, 136, 130, 127, 117, 103, 95 bytes

def f(k,l):
 q=[]
 for j,i in sorted((v,k)for k,v in enumerate(l)):k-=j;q+=[i]*(k>=0)
 print(q)

Try it online!

-21 bytes thanks to @79037662 by limiting indentation to 1-space.

-14 bytes thanks to @ mypetlion

-8 bytes thanks to @justhalf

Both solutions ignore N parameter.


APL (Dyalog), 4 bytes

*⍣≡⍨

Try it online!

* power

⍣ until

≡ stable

⍨ selfie


Brachylog, 10 bytes

=ᵍbᵐbᵐlᵍ=l

Try it online!

Explanation

=ᵍ                Group all equal elements together
  bᵐbᵐ            Remove the first element of each group twice. This fails if
                  there are fewer than 2 elements
      lᵍ          Group elements together that have the same length
        =         Are all elements of that list equal? This only succeeds if the
                  list has one element
         l        Length. This will always succeed


Reconstruct an integer from its prime exponents

Python 2, 61 bytes
Wilson's theroem FTW!

f=lambda p,a=1,b=1:p==[]or b**(a%b*p[0])*f(p[a%b:],a*b*b,b+1)

Try it online!
Python 2, 62 bytes

f=lambda p,a=1,b=1:p==[]or(a%b<1or b**p.pop(0))*f(p,a*b*b,b+1)

Try it online!


Jelly, 10 9 8 bytes
Œg+2/€UF

TryItOnline or run all test cases
How?
Œg+2/€UF - Main link: a                 e.g. [2,2,2,4,4,8]
Œg       - group runs of equal elements      [[2,2,2],[4,4],[8]]
   2/€   - pairwise reduce for each with
  +      -     addition                      [[4,2],[8],[8]]
      U  - reverse (vectorises)              [[2,4],[8],[8]]
       F - flatten list                      [2,4,8,8]


APL (Dyalog Extended), 9 8 bytesSBCS

(⍳12)√○1

Try it online! (⎕PP←34 is Print Precision: 34 digits; ⎕FR←1287 is Float Representation: 128-bit decimal)

○1 \$π×1\$

(…)√ take the following roots of that:

 ⍳12 ɩndices 1 through 12


MATL, 16 14 bytes

-1 byte thanks to @Giuseppe

-1 byte thanks to @LuisMendo

SY'ts/i-|tX<=)

Explanation:

        % implicit input
S       % sort
Y'      % run-length encoding
ts      % duplicate elements and sum (get number of elements)
/       % array right division (get array of probability for each answer)
i-|     % get absolute difference with second input
tX<     % duplicate and get minimum value
=)      % get each answer that match with the minimum value
        % (implicit) convert to string and display

Try it online! or verify all test cases


Perl - 63 bytes

#!perl -l
map{1while$l=length++$_,$_**2=~/.{$l}$/,$`+$&^$_;print}($_)x<>

Counting the shebang as one byte. Input is taken from stdin.

This has an acceptable runtime for n ≤ 50, after that it gets a bit slow.

Sample usage:

$ echo 20 | perl kaprekar.pl
1
9
45
55
99
297
703
999
2223
2728
4950
5050
7272
7777
9999
17344
22222
77778
82656
95121


Codegolf Rainbow : Sorting Colors with Reflection

Brachylog, 18 17 16 bytes

ġ₎↔ḍ↔{izo₎ᵐ↔}ᶠcc

Try it online!

-1 byte thanks to @sundar

Expects input as [<integer list>, n]. Note that negative integers are
represented with _, Brachylog's "low minus". Output variable is R.

First time attempting Brachylog, so I imagine it's sub-optimal and ripe for
reducing in bytes.

Explanation

Partition, bifurcate, sort based on index (0: asc, 1: desc), flatten.

ġ₎               | split head of input into groups of length n (last of list)
  ↔              | reverse so that...
   ḍ             | dichotomize splits in two, attaching any additional element to the second list
    ↔            | reverse so first half of partitions corresponds to the 0 index
     {      }    | apply
      i          | : append index
       z         | : zip each sublist with the index of its parent
        o₎ᵐ      | : map over sublists, ordering by the zipped index
           ↔     | : undo earlier reverse
             ᶠ   | find all outputs
              cc | flatten two levels


Find the minimum cost matching between arrays of integers

Jelly, 15 14 12 11 bytes

Œ!ż€IASƊÞḢṁ

Try it online!

-1 byte thanks to Jonathan Allan
-1 byte thanks to Mr. Xcoder
-2 bytes thanks to an anonymous editor

Brute force. Takes input as \$Y\$ then \$X\$.

Œ!ż€IASƊÞḢṁ
Œ!                 All permutations of Y.
  ż€               Zip each of the permutations with X.

       ƊÞ          Sort by:
    I              Difference of each pair.
     A             Absolute value.
      S            Sum.
         Ḣ         Take the first matching.
          ṁ        Mold the result like X. Keeps only values up to the length
                   of X which removes unpaired values from Y.


HTML5 and JavaScript, 12.72 + 50 + 50 + 50 = 162.72 points

Hi, this is my very first code golf, but I think, the following code works quite well (it's a full HTML page, 3848 bytes).

<meta charset="utf-8"><title>Hex</title><canvas style="position:absolute;top:0px;left:20px" width="850" height="600" id="o"></canvas>
<input type="button" onClick="I()" value="New game">

Multiplayer: <input id="mp" type="checkbox" onClick="Mp()">
<input type="button" onClick="U()" value="Undo">

Expanded

    <meta charset="utf-8">
    <title>Hex</title>

    <canvas style="position:absolute; top:0px; left:20px" width="850" height="600" id="output">Canvas not supported...</canvas>

<input type="button" onClick="init()" value="New game">

Multiplayer: <input id="mp" type="checkbox" onClick="chgMP()">
<input type="button" onClick="undo()" value="Undo">

Explanation

The code uses the HTML5's canvas-tag to display the game (14x14 board). You can undo the last step and play against another player (enable Multiplayer) or the computer, but its AI is still very weak (it just uses a random position to place the next field). The entire graphical design is based on your screenshot.


APL (143)

0{⍵≢T←'METHINKS IT IS LIKE A WEASEL':c∇⍨1+⍺⊣⎕←(⍕⍺),':'c'-- score:',s⊣c←⊃c/⍨G=s←⌈/G←{+/⍵=T}¨c←{⍵{⍵:⍺⋄C[?27]}¨9≠?28/20}¨100⍴⊂⍵}⊃∘(C←27↑⎕A)¨?28/27

Explanation:

0{...}⊃∘(C←27↑⎕A)¨?28/27: set C to the first 27 capital letters. There are only 26, so the 27th element will be a space. Select 28 random items from C. This will be the first ⍵. The first ⍺ (generation) will be 0.
⍵≢T←'METHINKS IT IS LIKE A WEASEL: set T to the string 'METHINKS IT IS LIKE A WEASEL'. As long as ⍵ is not equal to T:

{...}¨100⍴⊂⍵: Make 100 copies of ⍵. For each of these...

9≠?28/20: select 28 random numbers from 1 to 20. Make a bitmask where each 1 means that the random number was not equal to 9. (This means 5% chance of a 0).
⍵{⍵:⍺⋄C[?27]}¨: for each letter in ⍵, if the corresponding bit was 1, keep that letter, otherwise replace it with a randomly chosen element from C.

c←: store the 100 mutated strings in c.
G←{+/⍵=T}¨c: for each element in c, calculate the score (amount of characters that match T) and store the scores in G.
s←⌈/G: find the maximum score and store that in s.
c←⊃c/⍨G=s: select the first item from c whose score is equal to s (the maximum), and store it in c again.
⎕←(⍕⍺),':'c'-- score:',s: print the generation in the given format (⍺ is current generation, c is current best string, s is score)
c∇⍨1+⍺: Increment the generation and run the mutation again using the current best string (c) as input.


Mathematica, 85 bytes

FromDigits/@DeleteDuplicatesBy[Join@@Subsets/@Split@RealDigits[Pi,10,#][[1]],Length]&

Anonymous function. Takes n as input, and returns the elements of the sequence in the first n digits of π. Output is in the form of {0, 3, 33, 111, ...}.


Singly lossy integers: Concatenated sequences missing a single element

APL (Dyalog Unicode), 62 bytesSBCS

Infinite printing full program, 63 bytes

s←⍎' '~⍨⍕
{⎕←s⊢a←⊃⍵⋄b←1+a⋄t←∪(b,⍨⊃a)(a,⊃⌽b)b,1↓⍵⋄t[⍋s¨t]}⍣≡⊂1 3

Try it online!

This one is pretty fast. Theoretically can be made faster using a min heap, but the challenge is code golf after all.

How it works: the concept

If we denote each item in the sequence as a list of integers ([1,3] for 13, [1,2,4] for 124, and so on), observe that subsequent items can be derived from an existing item x in three ways:

Add 1 to all numbers in x
Add 1 to all numbers in x, and then prepend the first element of x
Append 1 plus the last element of x to x

Therefore, the algorithm is to start with the single known value and infinitely run the following:

Extract the smallest item and print it
Derive three larger values from it and add them to the list of next candidate items

How it works: the code

s←⍎' '~⍨⍕  ⍝ Helper function: concat a list of numbers
        ⍕  ⍝   Stringify entire array, which will contain blanks between items
   ' '~⍨   ⍝   Remove blanks
  ⍎        ⍝   Eval
s←         ⍝   Store the function to s

⍝ Main program: print all items in the sequence infinitely
{⎕←s⊢a←⊃⍵⋄b←1+a⋄t←∪(b,⍨⊃a)(a,⊃⌽b)b,1↓⍵⋄t[⍋s¨t]}⍣≡,⊂1 3
{...}⍣≡⊂1 3  ⍝ Specify starting item and infinite loop
       ⊂1 3  ⍝   singleton array containing [1 3]
{...}⍣≡      ⍝   Pass it to the infinite looping function

⎕←s⊢a←⊃⍵⋄b←1+a⋄t←∪(b,⍨⊃a)(a,⊃⌽b)b,1↓⍵⋄t[⍋s¨t]  ⍝ Single iteration
       ⍵  ⍝ Sorted candidate items
    a←⊃⍵  ⍝ Take the first element and store to a
⎕←s⊢a     ⍝ Concat and print it

b←1+a  ⍝ Add 1 to all items of a and store to b

t←∪(b,⍨⊃a)(a,⊃⌽b)b,1↓⍵  ⍝ Add next candidates
                   1↓⍵  ⍝ Remove the first item (already printed)
   (b,⍨⊃a)(a,⊃⌽b)b,     ⍝ Prepend three candidates:
                 b      ⍝   1+a
          (a,⊃⌽b)       ⍝   append 1+last element of a to a
   (b,⍨⊃a)              ⍝   prepend first element of a to 1+a
t←∪                     ⍝ Uniquify and store to t

t[⍋s¨t]  ⍝ t sorted with the key function s (concat'ed value)

Function returning first n values, 62 bytes

⎕CY'dfns'
⊢↑∘{(⍋⊃¨⊂)⍵{a b c←⍵-1 0⍺⋄⍎dab⍕c↓a↓b~⍨⍳⍺}¨↓3cmat⍵}2+⊢

Try it online!

Slower, but still can handle 100 items in around 5 seconds.

How it works: the concept

This solution uses a systematic way to generate all possible singly lossy integers from the list 1..n. It is equivalent to selecting three members from 1..n:

Select three distinct integers a < b < c from 1..n.
Take the inclusive range a..c and discard b.

Original list: 1 2 3 4 5 6 7 8 9
Selection:       ^ ^       ^
                 a b       c
Take a..c:       2 3 4 5 6 7
Discard b:       2   4 5 6 7
Result: 24567

I use dfns.cmat to generate all 3-combinations, generate all singly lossy numbers, sort them and take first n elements. We need length n+2 for the combinations because lower numbers won't give enough number of items.

How it works: the code

⎕CY'dfns'  ⍝ Import dfns library, so that we can use cmat

⍝ Inner function: generate enough singly lossy integers
{(⍋⊃¨⊂)⍵{a b c←⍵-1 0⍺⋄⍎dab⍕c↓a↓b~⍨⍳⍺}¨↓3cmat⍵}  ⍝ Input: 2+n

⍵{...}¨↓3cmat⍵  ⍝ Generate all 3-combinations, and get singly lossy integers
        3cmat⍵  ⍝ 3-combinations of 1..2+n
⍵{   }¨↓        ⍝ Map the inner function to each row of above, with left arg 2+n

a b c←⍵-1 0⍺⋄⍎' '~⍨⍕c↓a↓b~⍨⍳⍺  ⍝ From 3-combination to a singly lossy integer
a b c←⍵-1 0⍺  ⍝ Setup the numbers so that
              ⍝ "remove b, drop first a and last c elements" gives desired value
⍎dab⍕c↓a↓b~⍨⍳⍺  ⍝ Compute the target number
     c↓a↓b~⍨⍳⍺  ⍝ Remove b, drop first a and last c elements from 1..2+n
⍎dab⍕           ⍝ Concat the numbers (dab stands for Delete All Blanks)

(⍋⊃¨⊂)  ⍝ APL idiom for sorting

⊢↑∘{...}2+⊢  ⍝ Outer function; input: n
  ∘{...}2+⊢  ⍝   Pass 2+n to the inner function
⊢↑           ⍝   Take first n elements from the result

APL (Dyalog Extended), 49 bytesSBCS

⊢↑∘{∧⍵{a b c←⍵-1 0⍺⋄⍎⌂dab⍕c↓a↓b~⍨⍳⍺}¨↓3⌂cmat⍵}2+⊢

Try it online!

Simply uses extra built-ins provided in Extended version (dfns library pre-loaded as ⌂ functions, ∧ for ascending sort).


Python 2, 198 bytes
a,b,c,d=input()
H=(a+d)/2
D=(H*H-a*d+b*c)**.5
X,Y=H+D,H-D
p,q,r,s=[[1,0,0,1],[b,X-a,b,Y-a],[X-d,c,Y-d,c]][2*(c!=0)or(b!=0)]
A=abs
V=A(A(p)+A(q)*1j)
W=A(A(r)+A(s)*1j)
print[X,Y],[[p/V,q/V],[r/W,s/W]]

Input is a flat list of 4 complex numbers via STDIN, e.g.
[0.0+0j, 0.4+0j, -0.1+0j, -0.4+0j]

Note that Python uses j instead of i for complex numbers.
Output is two lists, the first containing the eigenvalues and the second containing the eigenvectors, e.g.
[(-0.2+0j), (-0.2+0j)]
[[(0.8944271909999159+0j), (-0.4472135954999579+0j)], [(0.8944271909999159+0j), (-0.4472135954999579+0j)]]

(newline inserted for clarity)


Java - 2,726 2,634 - 200 = 2434 characters

Improved from 3800 ish bytes

Thanks to all for your suggestions (especially pseudonym117), here is the new version.

I added a class P which is the point class and a class L which extends ArrayList

I also added some minor logic changes.

Here is the main class (not golfed):

import java.awt.*;
import java.awt.geom.*;

import javax.swing.*;
public class Polygons2 extends JPanel{
    public static void main(String[] args) throws InterruptedException{new Polygons2(args);}
    double q=Math.PI*2;
    int d=1;
    public Polygons2(String[] args) throws InterruptedException{
        double revolutions=Double.valueOf(args[0])*q;
        double stationaryRadius = Double.valueOf(args[1]);
        double rollingRadius = Double.valueOf(args[2]);
        int stationarySides = Integer.valueOf(args[3]);
        int rollingSides = Integer.valueOf(args[4]);
        double dist = stationaryRadius+rollingRadius+70;
        P sp = new P(dist,dist);
        P rp = new P(sp.x,sp.y-rollingRadius-stationaryRadius);
        //get points for rolling polygon and stationary polygon
        int key=0;
        for(double stationaryAngle=-q/4;stationaryAngle<q-q/4;stationaryAngle+=q/stationarySides){
            P p=new P(Math.cos(stationaryAngle)*stationaryRadius+sp.x,Math.sin(stationaryAngle)*stationaryRadius+sp.y);
            p.k=key;key++;
            stationaryPoints.add(p);
        }
        for(double rollingAngle=q/4;rollingAngle<q+q/4;rollingAngle+=q/rollingSides){
            P p=new P(Math.cos(rollingAngle)*rollingRadius+rp.x,Math.sin(rollingAngle)*rollingRadius + rp.y);
            p.k=key;key++;
            rollingPoints.add(p);
        }
        double g=(q/2)-((q/2-(q/rollingSides))/2) - ((q/2-(q/stationarySides))/2)-.05;
        for(P p:rollingPoints){p.r(getPoint(0), g);}
        //set up JFrame
        JFrame f = new JFrame();
        f.add(this);
        f.setSize((int)dist*2+60,(int)dist*2+60);
        f.setVisible(true);
        int[] pKeys= new int[]{stationaryPoints.get(0).k,rollingPoints.get(0).k};
        int index=1;
        P rc = rollingPoints.c();
        P sc =stationaryPoints.c();
        double currentRadian=Math.atan2(rc.y-sc.y,rc.x-sc.x);
        double totalRadian = 0;
        while(Math.abs(totalRadian)<revolutions){
            P rc2 = rollingPoints.c();
            P sc2 =stationaryPoints.c();
            double angle = Math.atan2(rc2.y-sc2.y,rc2.x-sc2.x);
            if(currentRadian-angle<2){totalRadian+=(angle-currentRadian);}
            currentRadian=angle;
            L clone=(L)path.clone();
            clone.add(new P(rollingPoints.get(1).x,rollingPoints.get(1).y));
            path = clone;
            for(P p:rollingPoints){
                p.r(getPoint(pKeys[index]),.01);
                int size = stationaryPoints.size();
                for(int i=0;i<size;i++){
                    P stationaryPointAtI = stationaryPoints.get(i);
                    P nextPoint=null;
                    if(i==size-1){nextPoint=stationaryPoints.get(0);}
                    else{nextPoint=stationaryPoints.get(i+1);}
                    if(p.b(stationaryPointAtI, nextPoint)==1&&containsKey(pKeys,p.k)==0){
                        //rolling point is between 2 stationary points
                        if(index==1){index=0;}else{index=1;}
                        pKeys[index]=p.k;
                    }
                    int size2=rollingPoints.size();
                    for(int h=0;h<size2;h++){
                        P nextPoint2=null;
                        if(h==size2-1){nextPoint2=rollingPoints.get(0);}
                        else{nextPoint2=rollingPoints.get(h+1);}
                        if(stationaryPointAtI.b(rollingPoints.get(h), nextPoint2)==1&&containsKey(pKeys,stationaryPointAtI.k)==0){
                            //stationary point is between 2 rolling points
                            if(index==1){index=0;}else{index=1;}
                            pKeys[index]=stationaryPointAtI.k;
                        }
                    }
                }
            }
            repaint();
            Thread.sleep(5);
        }
    }
    volatile L path = new L();
    L rollingPoints = new L();
    L stationaryPoints = new L();
    P getPoint(int key){
        for(P p:rollingPoints){if(p.k==key){return p;}}
        for(P p:stationaryPoints){if(p.k==key){return p;}}
        return null;
    }
    int containsKey(int[] keys,int key){
        for(int i:keys){if(key==i){return 1;}}
        return 0;
    }
    @Override
    public void paintComponent(Graphics g){
        Path2D.Double sPath = new Path2D.Double();
        sPath.moveTo(stationaryPoints.get(0).x, stationaryPoints.get(0).y);
        for(P p:stationaryPoints){
            sPath.lineTo(p.x, p.y);
        }
        sPath.closePath();
        Path2D.Double rPath = new Path2D.Double();
        rPath.moveTo(rollingPoints.get(0).x, rollingPoints.get(0).y);
        for(P p:rollingPoints){
            rPath.lineTo(p.x, p.y);
        }
        rPath.closePath();
        g.setColor(Color.white);
        g.fillRect(0,0,getWidth(),getHeight());
        Graphics2D t = (Graphics2D)g;
        if(d==1){
        t.setColor(Color.black);
        t.draw(sPath);
        t.setColor(Color.blue);
        t.draw(rPath);
        }
        g.setColor(Color.green);
        for(P p:path){g.fillOval((int)p.x-1, (int)p.y-1, 2, 2);}
    }
}

And the golfed version:

import java.awt.*;import java.awt.geom.*;import javax.swing.*;import static java.lang.Math.*;class Polygons2Golfed extends JPanel{public static void main(String[]a)throws Exception{new Polygons2Golfed(a);}double q=PI*2;int d=1;public Polygons2Golfed(String[]a)throws Exception{double b,c,f;b=Double.valueOf(a[1]);c=Double.valueOf(a[2]);int d,e;d=Integer.valueOf(a[3]);e=Integer.valueOf(a[4]);f=b+c+100;P o=new P(f,f);P r=new P(o.x,o.y-c-b);int s=0;for(double u=-q/4;u<q-q/4;u+=q/d){P p=new P(cos(u)*b+o.x,sin(u)*b+o.y);p.k=s;s++;l.add(p);}for(double u=q/4;u<q+q/4;u+=q/e){P p=new P(cos(u)*c+r.x,sin(u)*c+r.y);p.k=s;s++;k.add(p);}double g=q/e/2+q/d/2-.05;for(P p:k){p.r(v(0),g);}JFrame j=new JFrame();j.add(this);j.setSize((int)f*2+60,(int)f*2+60);j.setVisible(true);m=new int[]{l.get(0).k,k.get(0).k};int ad=1;P rc=k.c();P sc=l.c();double ab,ac;ab=atan2(rc.y-sc.y,rc.x-sc.x);ac=0;while(abs(ac)<Double.valueOf(a[0])*q){P rc2=k.c();P sc2=l.c();double ah=atan2(rc2.y-sc2.y,rc2.x-sc2.x);if(ab-ah<2)ac+=(ah-ab);ab=ah;L ag=(L)n.clone();ag.add(new P(k.get(1).x,k.get(1).y));n=ag;for(P p:k){p.r(v(m[ad]),.01);int af=l.size();for(int i=0;i<af;i++){P aa=l.get(i);P w=null;if(i==af-1){w=l.get(0);}else{w=l.get(i+1);}if(p.b(aa, w)==1&&w(p.k)==0){if(ad==1)ad=0;else ad=1;m[ad]=p.k;}int ae=k.size();for(int h=0;h<ae;h++){P u=null;if(h==ae-1)u=k.get(0);else u=k.get(h+1);if(aa.b(k.get(h),u)==1&&w(aa.k)==0){if(ad==1)ad=0;else ad=1;m[ad]=aa.k;}}}}repaint();Thread.sleep(5);}}L n=new L();L k=new L();L l=new L();P v(int key){for(P p:k){if(p.k==key)return p;}for(P p:l){if(p.k==key)return p;}return null;}int[]m;int w(int key){for(int i:m){if(key==i)return 1;}return 0;}@Override public void paintComponent(Graphics g){Path2D.Double aq=new Path2D.Double();aq.moveTo(l.get(0).x,l.get(0).y);for(P p:l){aq.lineTo(p.x, p.y);}aq.closePath();Path2D.Double aw=new Path2D.Double();aw.moveTo(k.get(0).x, k.get(0).y);for(P p:k){aw.lineTo(p.x, p.y);}aw.closePath();g.setColor(Color.white);g.fillRect(0,0,getWidth(),getHeight());Graphics2D t=(Graphics2D)g;if(d==1){t.setColor(Color.black);t.draw(aq);t.setColor(Color.blue);t.draw(aw);}g.setColor(Color.green);for(P p:n){g.fillOval((int)p.x-1,(int)p.y-1,2,2);}}}

As well as classes P:

import java.awt.geom.*;class P{double x,y;public P(double a,double b){x=a;y=b;}int k;void r(P c,double g){double a,r;a=Math.atan2(y-c.y,x-c.x)+g;r=Math.sqrt((c.x-x)*(c.x-x)+(c.y-y)*(c.y-y));x=Math.cos(a)*r+c.x;y=Math.sin(a)*r+c.y;}public int b(P a,P b){if(Line2D.ptSegDist(a.x,a.y,b.x,b.y,x,y)<.5)return 1;return 0;}}

And L:

import java.util.*;public class L extends ArrayList<P>{public P c(){double x,y;x=0;y=0;for(P p:this){x+=p.x;y+=p.y;}return new P(x/size(),y/size());}}

Change int d to 0 or 1 to show polygons

arguments - 1 100 50 5 2

args - 1.5 100 100 7 3

args - 2 40 100 3 7


This Haskell program encodes a tree of n nodes in n Integers. The trick is that it encodes the node's data doubled, and then uses the lower-order bit to indicate if this is a leaf node, or an interior node.

Technically, the Parser monad here is over-kill, since there is only one parser created, decoder and I could have put the parser chaining logic directly there. But this way the decoder is very clear, and the Parser despite it's small size, is a reasonable simple parsing framework.

import Control.Monad (ap)

data Tree = Leaf Integer | Node Integer Tree Tree
  deriving (Eq, Show)

encode :: Tree -> [Integer]
encode (Leaf n)     = [n*2]
encode (Node n t u) = (n*2+1) : encode t ++ encode u

decode :: [Integer] -> Maybe Tree
decode = fullyParse decoder
  where
    decoder :: Parser Integer Tree
    decoder = do
      i <- next
      let n = i `div` 2
      if even i
        then return (Leaf n)
        else return (Node n) `ap` decoder `ap` decoder

-- A simple Parsing Monad
data Parser a b = P { runParser :: [a] -> Maybe (b, [a]) }

instance Monad (Parser a) where
  return a = P ( \ts -> Just (a, ts) )
  p >>= q  = P ( \ts -> runParser p ts >>= (\(v,ts') -> runParser (q v) ts') )
  fail _   = P ( const Nothing )

next :: Parser a a
next = P n
 where n (t:ts) = Just (t,ts)
       n _      = Nothing

fullyParse :: Parser a b -> [a] -> Maybe b
fullyParse p ts = runParser p ts >>= consumedResult
  where
    consumedResult (v,[]) = Just v
    consumedResult _      = Nothing

-- Example
main :: IO ()
main = do
    putStrLn $ "example:  " ++ show ex
    putStrLn $ "encoding: " ++ show encEx
    putStrLn $ "decoding: " ++ show decEx
    putStrLn $ "worked?   " ++ show worked
  where
    ex = Node 5
          (Leaf 3)
          (Node 2
            (Node 2
              (Leaf 9)
              (Leaf 9)
            )
            (Leaf 1)
          )
    encEx = encode ex
    decEx = decode encEx
    worked = maybe False (ex ==) decEx

Running this gets you:

> runhaskell TreeEncoding.hs
example:  Node 5 (Leaf 3) (Node 2 (Node 2 (Leaf 9) (Leaf 9)) (Leaf 1))
encoding: [11,6,5,5,18,18,2]
decoding: Just (Node 5 (Leaf 3) (Node 2 (Node 2 (Leaf 9) (Leaf 9)) (Leaf 1)))
worked?   True


Bijective mapping from integers to a variable number of trits

Pyth, 6 bytes

tjyhQ3

Explanation:

    Q    Input number.
   h     Add 1.
  y      Multiply by 2.
 j   3   Convert to base 3 as a list.
t        Remove the first element.

Test suite

Inverse function: Pyth, 14 bytes

t/i+-2%sQ2Q3 2

Explanation:

        Q        Input list.
       s         Sum.
      %  2       Modulo 2.
    -2           Subtract from 2.
   +      Q      Prepend to input list.
  i        3     Convert from base 3.
 /           2   Divide by 2.
t                Subtract 1.

Test suite

The bijection looks like this:

0: []
1: [1]
2: [0]
3: [2]
4: [0, 1]
5: [1, 0]
6: [1, 2]
7: [2, 1]
8: [0, 0]
9: [0, 2]
10: [1, 1]
11: [2, 0]
12: [2, 2]
13: [0, 0, 1]
14: [0, 1, 0]
15: [0, 1, 2]
16: [0, 2, 1]
17: [1, 0, 0]
18: [1, 0, 2]
19: [1, 1, 1]
⋮

General base

To make this work in any base b, simply replace 3 with b, 2 with (b − 1), and y with *(b − 1).


ASCII Art of the Day #3 - Chinese Shrines


MATL, 32 bytes
JQ6*`G5thYay&Zj3$)wyJ2@-^*+8M]b&

Try it online! Or verify all test cases.
How it works
The input matrix is padded with a frame of five zeros, so for example
3 2 3 2 7
3 1 4 1 6
2 5 3 1 1
4 4 3 2 4
1 1 1 1 1

becomes
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 2 3 2 7 0 0 0 0 0
0 0 0 0 0 3 1 4 1 6 0 0 0 0 0
0 0 0 0 0 2 5 3 1 1 0 0 0 0 0
0 0 0 0 0 4 4 3 2 4 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

The frame of zeros is used to detect when the arsonist bee has exited the matrix. The extension with five zeros ensures that a modular displacement of length up to 9 in any direction from any of the nonzero entries will correctly land in a zero without wrapping around to some non-zero entry.
In matrix coordinates, the bee starts at entry (6,6) of the extended matrix. It reads that entry, and updates the coordinates as required, applying a (modular) displacement of the read length in the corresponding direction. This is repeated in a loop until the read value is 0. The entry that was read before that one (i.e. the last non-zero entry) is the output.
The coordinates are actually stored as a complex number, so for example (6,6) becomes 6+6j. This way the four cyclic directions can be realized as powers of the imaginary unit. The corresponding power (j, 1, -j or -1) is multiplied by the read entry to obtain the complex displacement which is used for updating the coordinates.
The successively read values are kept on the stack. When the loop is exited, the stack contains all non-zero read values in order, then the last read value which is 0, then the latest complex coordinates. So the third-top element is the required output.


Fastest algorithm for decomposing a perfect power

Python, 207 chars

This takes O(log2 N) bigint ops.  O(log N) different exponents to try, and O(log N) binary search to find each base.

import sys
for N in map(int,sys.stdin.readlines()):
 p,s=2,''
 while 1<<p<=N:
  i,j=2,N
  while j>i+1:
   m=(i+j)/2
   if m**p>N:j=m
   else:i=m
  if i**p==N:s+=' %d^%d'%(i,p)
  p+=1
 if s:print N,'=',s[1:]


MATL, 60 56 53 bytes
:"@qXJx[HKCbO]"7Z"'  |-|  'v'o'@('--|-|--  '  JVhXxXD

The animation with the above code runs very fast. The following version includes a pause to make the animation slower and thus easier to see (not required by the challenge), at the cost of 4 more bytes:
:"@qXJx[HKCbO]"7Z"'  |-|  'v'o'@('--|-|--  '  JVhXxXD.2Y.

Try it at MATL Online! The interpreter is a beta; refresh the page if it doesn't work.
Or see a recording from the offline compiler:

Explanation
:"              % Input N implicitly. Repeat N times
  @q            %   Push iteration index minus 1, that is, from 0 to N-1. This
                %   are the numbers of sheep
  XJx           %   Copy into clipboard J and delete
  [HKCbO]       %   Push array [2 4 7 -2 0]
  "             %   For each value in that array. This loops generates the 5
                %   frames for each number of sheep
    7Z"         %     Push string of 7 spaces
    '  |-|  '   %     Push this string
    v           %     Concatenate vertically. This gives a 2x7 char array
                %     with the upper part of the frame, except the 'o',
                %     which will be now placed in a varying position
    'o'         %     Push string 'o'
    @           %     Push loop variable, that is, 2, 4, 7, -2 or 0
    (           %     Write 'o' into that position of the 2x7 char array.
                %     The position is interpreated linearly, that is, a single
                %     number is used as index into the 2D array in column-major
                %     order (down, then across). So index 2 is lower-left corner,
                %     index 4 is to the right of that etc. Indexing is
                %     semi-modular (modular for non-positive values). So 0 is
                %     the lower-right corner, and -2 is to the left of that
    '--|-|--  ' %     Push this string
    JV          %     Push current number of sheep converted to string
    h           %     Concatenate horizontally
    Xx          %     Clear screen
    XD          %     Display all stack contents
    .2Y.        %     Pause for 0.2 seconds (optional)
                %   End implicitly
                % End implicitly


Mathematica 30-(10+50)= -30
Shortened by 4 chars thanks to ybeltukov.
Range@n returns the numbers from 1 through n.
Integerdigits@n breaks up each of those numbers into its digits.
Total[n,2] sums the digits.  The 2 is to allow summing across different levels, i.e. lists of lists.
IntegerDigits@Range@#~Total~2&

Testing
IntegerDigits@Range@#~Total~2&[12]

51

IntegerDigits@Range@#~Total~2 &[1000000]

27000001

Expressions
IntegerDigits@Range@#~Total~2 &[55*96 - 12]

55*96 - 12

81393
5268

IntegerDigits@Range@#~Total~2 &[5268]

81393

IntegerDigits@Range@#~Total~2 &[55*96^2 - 12]
55*96^2 - 12

12396621
506868

IntegerDigits@Range@#~Total~2 &[506868]

12396621


COBOL (GnuCOBOL), 191 + 17 = 208 bytes

I "learned" COBOL for this answer, so it's probably not fully golfed.

This is a full program, taking input on what I presume to be standard input and writing to what I presume to be standard output. Perhaps one day I'll return to this and (1) determine whether COBOL has functions and, if so, (2) see whether a function solution would be shorter.

Byte count includes program and compiler flags (-free and -frelax-syntax).

program-id.c.select i assign keyboard line sequential.fd i. 1 l pic X(80). 88 e value 0.open input i perform until e read i end set e to true end-read if not e and l(7:1)<>'*'display l(8:73).

Try It Online

Ungolfed program

program-id. c.

select i assign to keyboard organization line sequential.

fd i.
    1 l pic X(80).
    88 e value 0.

open input i
perform until e
    read i
        end set e to true
    end-read
    if not e and l(7:1) <> '*'
        display l(8:73).

Limitations

The output is, technically speaking, not correct. From my cursory research, it seems the only practical way to store a string in COBOL is in a fixed-size buffer. I have chosen a buffer size of 80 characters, since this is the line length limit for fixed-format programs. This presents two limitations:

Lines longer than 80 characters are truncated.
Lines shorter than 80 characters are right-padded with spaces.

I'm guessing this is acceptable since, well, it's COBOL. If not, I'd be willing to look into alternatives.

Acknowledgments

-166 bytes thanks to Edward H
-2 bytes thanks to hornj


Python 2, 21 bytes

lambda s:`s`[:len(s)]

Try it online!

Takes the string representation of the input string and truncates it to the length of the input string. For a typical string, this puts it in ' quotes and chops off the end:

abc  ->   'abc'  ->  'ab
     rep        chop

Note that the new string starts with '. Let's show that the output always differs from the input.

If the input has no ', then the output starts with ' and the input does not.
If the input contains a ' and but no ", then Python will use " for the outer quotes, giving a first character " that's not in the input string.
If the input has both ' and ", then the outer quotes are ' and each ' is escaped as \'. Wherever the first " appears in the input, it's shifted right by the initial ' in the output and by any possible escaping. This means it cannot match with a " in the corresponding position in the output.

Finally, note that quoting the input and possibly escaping characters always increases the number of characters, so truncating the output makes it the same length as the input.

Note that it was crucial that Python adaptively switches to " in the second case. If it didn't do so, it would fail on the three-character input '\'. Or, any longer prefix of the fix show string using '. So, this method won't work for most languages.


Vectorization with Arrays

Whenever a function takes an array as an argument instead of a singleton, That function will also output an array with the result value to the corresponding indecies.

Example:
=LEN(A1)+LEN(B2)+LEN(C3)
could be replaced with
=SUM(LEN({A1,B2,C3}))


Haskell, 310 bytes

Defining reverse (as I did: r) is one byte shorter than importing Data.List and using it just once
Defining z=0:z and (!)=(!!).(++z) is the shortest way yet that I've found to return 0 for out of bounds
I've checked and quickChecked the take4s function, but it still feels like magic to me

Here's the code:

l=lines"    \n--__\n__--\n\\//\\\n/\\\\/\n~~~~\n||||\n^^vv\nvv^^\n][]["
d x|x<1=[]|1<2=mod x 10:d(div x 10)
(&)=(!!)
z=(0::Int):z
(!)=(&).(++z)
t a=[[a!q|q<-[p..p+3]]|p<-[0,4..length a-1]]
g[c,d,b,a]=[[l&b&1,'|',l&a&0,' '],[l&d&3,'|',l&c&2,' ']]
r[]=[]
r(x:y)=r y++[x]
f=unlines.foldl1(zipWith(++)).map g.r.t.d

Less golfed:

import Data.List (reverse)

dict = lines "    \n--__\n__--\n\\//\\\n/\\\\/\n~~~~\n||||\n^^vv\nvv^^\n][]["

-- Note that (digits x) returns the digits of x in little-endian order
digits x  | x < 1     = []
          | otherwise = mod x 10 : digits (div x 10)

-- Note: zeros needs the type signature, because otherwise it won't match [Int] (inferred from (!!))
zeros = (0::Int) : zeros

-- list ! position gives the element at the position, or 0 for out of bounds
(!) = (!!) . (++zeros)

-- This partitions the digits into groups of four, padded right
take4s a = [[a!q | q <-[p..p+3]] | p <- [0,4..length a - 1]]

convertOne[c,d,b,a] = [[dict !! b !! 1, '|', dict !! a !! 0, ' '], [dict !! d !! 3, '|', dict !! c !! 2, ' ']]

f = unlines . foldl1(zipWith (++)) . map convertOne . reverse . take4s . digits

Tests (escape characters removed):

mapM_ print $ lines $ f 1510
-|
_|~

mapM_ print $ lines $ f 1511
-|-
_|~

mapM_ print $ lines $ f 1471
^|-
_|\

mapM_ print $ lines $ f 1486
v||
_|\

mapM_ print $ lines $ f 3421
_|-
\|\

mapM_ print $ lines $ f 1234567891011121314
_|\ ||^ -|  -|_ -|/
 |_ /|~ ^|] _|_ _|/

mapM_ print $ lines $ f 1024628340621757567
 |_ _|v  || ^|~ ||^
 |_ /|| \|\ -|_ v|~


Python 2, 35 bytes

lambda a,b:(a^b)&-(a^b)in[a^b or[]]

Try it online!

Uses the power-of-two check n&-n==n, eliminating the n==0 false positive.

For reference, these are the pairs of one-char binary operators that are one bit apart, making them hard to use:

+ /
- /
* +
% -
< |
< >

Fortunately, & and ^ are not among these.

Also note that == can become <=, and + can become the comment character #.

Python 2, 41 bytes

lambda a,b:bin(a^b).count(`+True`)is+True

Try it online!

Taking TFeld's lambda a,b:bin(a^b).count('1')==1 and making it pristine by changing the 1's to +True and == to is. Thanks to Jo King for 1 byte.


Write the whole of the holed using the unholed

GolfScript, 37 36 characters
[":=<?)-/! YX[]VIHKx{}|~vih"{25^}/]+

Try the code here.
The string contains the forbidden characters xor'ed with 25. Fortunately all characters are mapped to valid ones.


Java, 1091 1039 bytes
Probably not very good, but I'll give it a try. (Formatting worse will give less Bytes, but for now, let's leave it)
edit 1: used names for Vars to make comment shorter.
public class t {
public static void main(String[] V){
    StringBuilder w = new StringBuilder("SOURCECODE");
    X(w);
    for(int Y=0; Y<6; Y++){
        w.deleteCharAt(4);
        w.setCharAt(0,(char)(w.charAt(0)+1));
        X(w);
    }
    w.deleteCharAt(0);
    for(int o=0;o<2;o++){
        w.setCharAt(2,(char)(w.charAt(2)+1));
        w.append('A');
        w.append('A');
        X(w);}
    for(int O=0;O<20;O++){
        if (O<15) w.setCharAt(3,(char)(w.charAt(3)+1));
        w.setCharAt(4,(char)(w.charAt(4)+1));
        if (O<19) w.setCharAt(5,(char)(w.charAt(5)+1));
        X(w);}
    w.deleteCharAt(6);
    X(w);//o
    for(int O=0;O<6;O++){
        if (O<5) w.setCharAt(0,(char)(w.charAt(0)+1));
        w.setCharAt(1,(char)(w.charAt(1)-1));
        X(w);}
    for(int O=1;O<4;O++){
    w.deleteCharAt(2);//o
    if (O<3) w.insert(4, 'A');
    X(w);}
    for(int O=0;O<5;O++){
        if (O<3) w.setCharAt(2,(char)(w.charAt(2)+1));
        w.setCharAt(4,(char)(w.charAt(4)+1));
        X(w);}
    //OOOOPQRsTTTTTTTTTT
    //yxwVuTTtTTTTtTTAAAAAaAAAAAAAAAAAAaAAREEEEEEE
}
static void X(StringBuilder b){System.out.println(b.toString());}}

outputs:
SOURCECODE
TOURECODE
UOURCODE
VOURODE
WOURDE
XOURE
YOUR
OUSAA
OUTAAAA
OUTBBBA
OUTCCCA
OUTDDDA
OUTEEEA
OUTFFFA
OUTGGGA
OUTHHHA
OUTIIIA
OUTJJJA
OUTKKKA
OUTLLLA
OUTMMMA
OUTNNNA
OUTOOOA
OUTPPPA
OUTPQQA
OUTPRRA
OUTPSSA
OUTPTTA
OUTPUTA
OUTPUT
PTTPUT
QSTPUT
RRTPUT
SQTPUT
TPTPUT
TOTPUT
TOPUAT
TOUAAT
TOAAT
TOBAU
TOCAV
TODAW
TODAX
TODAY


Fuzzy Octo Guacamole, 13 12 11 10 bytes
9+ddpp![g]

Explanation:
9+ddpp![g]
9+           # push 9 and increment, giving 10
  dd         # duplicate, twice. now you have [10,10,10]
    pp       # raise a 10 to the 10th power, then raise that to the 10th again. That ends up being 10^100.
      ![ ]   # for loop, `!` sets the counter to the top of stack
        g    # prints an ASCII art goat.

Sample of the goat printed:
                  ___.
                 //  \\
                ((   ""
                 \\__,
                /6 (%)\,
               (__/:";,;\--____----_
                ;; :";,:";`;,";,;";`,`_
                  ;:,;;";";,;":,";";,-Y\
                   ;,;,;";";,;":;";"; Z/
                   / ;,";";,;";,;";;"
                  / / |";/~~~~~\";;"
                 ( K  | |      || |
                  \_\ | |      || |
                   \Z | |      || |
                      L_|      LL_|
                      LW/      LLW/


Write an interpreter for my new programming language

Python 3 2, 200 187 149 146 136 bytes
-9bytes thanks to Cyoce
def f(n,a=[0]*256,x=0,z=0):
 while 1:y=a[z];exec'a[z]^=~1 z+=1 z-=1 print-y/2 if~y:x+=1 if~~y:x-=3'.split()["wlipdy".find(n[x][3])];x+=1

Input as list, exits by error. Bonus feature: you can specify start array, start IP, and start DP in that very exact order.


Print the previous answer in reverse - with a catch

3 - Python 2
419/64+57 -> SCORE: 63.546875

This is one masterpiece of hackery. Edited to comply with rule 1. chr uses lowercase h, not uppercase. Will edit when I have time to find a substitute.

Update 9/25/2020: Yeah I'm not coming back to this, question is closed anyway.

This is assuming the first answer is Python 3
e=ord
o=e("o")
a=e("a")
n=e("\n")
t=e(")")
b=e("(")
i=e("i")
W=e(" ")
p=o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+o+a+n+n
o=chr
H=o(W+t)
d=o(p+n)
p=o(p)
l=o(a+e(",")+n+n+n)
r=o(i+t+t)
c=o(b+b+b+n+W)
print(o(b+W+n)+r+l+p+")c("+p+p+c+d+p+H+p+""""!" + b + " ," + a = c"""+p+H+p+""""dlroW" = b"""+p+p+""""olleH" = a"""+p)

TIO


Python 3, pperry

İ

Try it online!

The lower case variant i̇ of this character is created by a an i and a ċȯṁḃi̇̇ṅi̇̇ṅġ ḋȯṫ which results in a length of 2.


MATL, 3 bytes
1r/

Try it online! Or estimate the resulting probabilities by running it 10000 times.
Explanation
1    % Push 1
r    % Push random number uniformly distributed on the open interval (0,1)
/    % Divide. Implicitly display