text:
How many towers can you see?
This question is based on the number-placement puzzle Towers (also known as Skyscrapers), which you can play online. Your goal is to take a solution to the puzzle and determine the clues -- the numbers of towers visible along each row and column. This is code golf, so fewest bytes wins.
How Towers works
The solution to a Towers puzzle is a Latin square -- a n*n grid in which every row and column contains a permutation of the numbers 1 through n. An example for n=5 is:
4 3 5 2 1
5 4 1 3 2
1 5 2 4 3
2 1 3 5 4
3 2 4 1 5

Each row and column is labelled with a clue at each end like:
       2 3 1 4 5
       v v v v v

 2 >   4 3 5 2 1   < 3
 1 >   5 4 1 3 2   < 4
 2 >   1 5 2 4 3   < 3
 3 >   2 1 3 5 4   < 2
 3 >   3 2 4 1 5   < 1

       ^ ^ ^ ^ ^
       2 2 2 2 1

Each clue is a number from 1 to n that tells you how many towers you "see" looking along the row/column from that direction, if the numbers are treated as towers with that height. Each tower blocks shorter towers behind it. In other words, the towers you can see are the ones that are taller than any tower before them.

For example, let's look at the first row.
 2 >   4 3 5 2 1   < 3

It has a clue of 2 from the left because you can see the 4 and the 5. The 4 blocks the 3 from sight and the 5 blocks everything else. From the right, you can see 3 towers: 1, 2, and 5.
Program requirements
Write a program or function that takes in the grid of numbers and outputs or prints the clues, going clockwise from the top left.
Input
An n*n Latin-square with 2<=n<=9.
The format is flexible. You can use any data structure that represents a grid or list containing numbers or digit characters. You may require a separator between the rows or no separator at all. Some possibilities are a list, a list of lists, a matrix, a token-separated string like
43521 54132 15243 21354 32415,

or a string without spaces.
You're not given n as part of the input.
Output
Return or print the clues starting from the top left and going clockwise. So, first the upper clues reading rightwards, then the right clues reading downwards, then the lower clues reading leftwards, the the left clues reading upwards.
This would be 23145 34321 12222 33212 for the previous example
       2 3 1 4 5
       v v v v v

 2 >   4 3 5 2 1   < 3
 1 >   5 4 1 3 2   < 4
 2 >   1 5 2 4 3   < 3
 3 >   2 1 3 5 4   < 2
 3 >   3 2 4 1 5   < 1

       ^ ^ ^ ^ ^
       2 2 2 2 1

Just as for the input, you can use a list, string, or any ordered structure. The four "groups" can be separated or not, in a nested or a flat structure. But, the format must be the same for each group.
Example test cases:
(Your input/output format doesn't have to be the same as these.)
>> [[1 2] [2 1]]

[2 1]
[1 2]
[2 1]
[1 2]

>> [[3 1 2] [2 3 1] [1 2 3]]

[1 2 2]
[2 2 1]
[1 2 3]
[3 2 1]

>> [[4 3 5 2 1] [5 4 1 3 2] [1 5 2 4 3] [2 1 3 5 4] [3 2 4 1 5]]

[2 3 1 4 5]
[3 4 3 2 1]
[1 2 2 2 2]
[3 3 2 1 2]

>> [[2 6 4 1 3 7 5 8 9] [7 2 9 6 8 3 1 4 5] [5 9 7 4 6 1 8 2 3] [6 1 8 5 7 2 9 3 4] [1 5 3 9 2 6 4 7 8] [3 7 5 2 4 8 6 9 1] [8 3 1 7 9 4 2 5 6] [9 4 2 8 1 5 3 6 7] [4 8 6 3 5 9 7 1 2]]

[4 2 2 3 3 3 3 2 1]
[1 3 3 2 2 2 2 3 3]
[4 3 2 1 2 3 3 2 2]
[3 1 2 4 3 3 2 2 5]

For you convenience, here are the same test cases in a flat string format.
>> 1221

21
12
21
12

>> 312231123

122
221
123
321

>> 4352154132152432135432415

23145
34321
12222
33212

>> 264137589729683145597461823618572934153926478375248691831794256942815367486359712

422333321
133222233
432123322
312433225

APL 19
≢¨∪/⌈\(⍉⍪⌽⍪⊖∘⌽∘⍉⍪⊖)

(golfed a bit more after ngn's suggestion, thanks)
Explanation:
(⍉⍪⌽⍪⊖∘⌽∘⍉⍪⊖)  rotates matrix 4 times appending results
⌈\ gets maximums for each row up to current column (example: 4 2 3 5 1 gives 4 4 4 5 5)
≢¨∪/ counts unique elements for each row

Try it on tryapl.org

You can avoid adding 1: ≢¨∪¨↓⌈\(⍉⍪⌽⍪⍉∘⌽∘⊖⍪⊖)

@ngn you're right, thanks! I also applied ∪/ so 1 char less :)

Wow - this is the sort of challenge APL excels at.

Python 2, 115 bytes
def T(m):o=[];exec'm=zip(*m)[::-1]\nfor r in m[::-1]:\n n=k=0\n for x in r:k+=x>n;n=max(x,n)\n o+=[k]\n'*4;return o

There's an awful lot of list flipping going on in there.
Takes input as a nested list (e.g. call with T([[4,3,5,2,1],[5,4,1,3,2],[1,5,2,4,3],[2,1,3,5,4],[3,2,4,1,5]])). Output is a single flat list.
Ungolfed:
def T(m):
 o=[]
 for _ in [0]*4:
  m=zip(*m)[::-1]
  for r in m[::-1]:
   n=k=0
   for x in r:k+=x>n;n=max(x,n)
   o+=[k]
 return o

Alternative 115:
def T(m):o=[];exec'm=zip(*m)[::-1];o+=[len(set([max(r[:i+1])for i in range(len(r))]))for r in m[::-1]];'*4;return o

I have no idea why this works with a list comprehension, but chucks a NameError with a set comprehension...
A bit too long, but if anyone's interested — yes, it's possible to get this down to a lambda!
T=lambda m:[len({max(r[:i+1])for i in range(len(r))})for k in[1,2,3,4]for r in eval("zip(*"*k+"m"+")[::-1]"*k)[::-1]]

Pyth, 25 bytes
V4=Q_CQ~Yml{meS<dhkUd_Q)Y

Obligatory Pyth port.
Input the list via STDIN, e.g. [[4, 3, 5, 2, 1], [5, 4, 1, 3, 2], [1, 5, 2, 4, 3], [2, 1, 3, 5, 4], [3, 2, 4, 1, 5]].
Try it online... is what I would say but unfortunately, for security reasons, the online interpreter disallows the use of eval on nested brackets. Try the workaround code JcQ5V4=J_CJ~Yml{meS<dhkUd_J)Y instead, and input as a flattened list like [4, 3, 5, 2, 1, 5, 4, 1, 3, 2, 1, 5, 2, 4, 3, 2, 1, 3, 5, 4, 3, 2, 4, 1, 5].
(Thanks to @isaacg who helped golf out a few bytes)

A couple of Pyth golfs: < and > are the one sided slice operators, so :d0hk can be turned into <dhk. U on collection inputs is the same as Ul, so Uld can be turned into Ud.

@isaacg Thanks - looks like my Pyth needs updating. The doc I have is outdated.

CJam, 29 27 bytes
q~{z_{[{1$e>}*]_&,}%pW%}4*;

Input like
[[4 3 5 2 1] [5 4 1 3 2] [1 5 2 4 3] [2 1 3 5 4] [3 2 4 1 5]]

Output like
[2 3 1 4 5]
[3 4 3 2 1]
[1 2 2 2 2]
[3 3 2 1 2]

How it works
The basic idea is to have the code work along rows and rotate the grid counter-clockwise 4 times. To count the towers, I'm raising each tower as far as it doesn't make a "visual difference" (i.e., don't change it if it's visible, or pull it up to the same height of the tower in front of it), and then I'm counting distinct heights.
q~                          "Read and evaluate the input.";
  {                    }4*  "Four times...";
   z                        "Transpose the grid.";
    _                       "Duplicate.";
     {            }%        "Map this block onto each row.";
      [       ]             "Collect into an array.";
       {    }*              "Fold this block onto the row.";
        1$                  "Copy the second-to-topmost element.":
          e>                "Take the maximum of the top two stack elements.";
                            "This fold replaces each element in the row by the
                             maximum of the numbers up to that element. So e.g.
                             [2 1 3 5 4] becomes [2 2 3 5 5].";
               _&,          "Count unique elements. This is how many towers you see.";
                    p       "Print array of results.";
                     W%     "Reverse the rows for the next run. Together with the transpose at
                             the start this rotates the grid counter-clockwise.";
                          ; "Get rid of the grid so that it isn't printed at the end.";

APL, 44
{{+/~0∊¨↓(∘.>⍨⍵)≥∘.<⍨⍳⍴⍵}¨↓(⌽∘⍉⍪⊢⍪⊖∘⍉⍪⊖∘⌽)⍵}

Tested here.

J, 35 chars
(+/@((>./={:)\)"2@(|.@|:^:(<4)@|:))

Example:
   t=.4 3 5 2 1,. 5 4 1 3 2,. 1 5 2 4 3,. 2 1 3 5 4,. 3 2 4 1 5
   (+/@((>./={:)\)"2@(|.@|:^:(<4)@|:)) t
2 3 1 4 5
3 4 3 2 1
1 2 2 2 2
3 3 2 1 2

Try it here.

Haskell, 113
import Data.List
f(x:s)=1+f[r|r<-s,r>x]
f _=0
r=reverse
t=transpose
(?)=map
l s=[f?t s,(f.r)?s,r$(f.r)?t s,r$f?s]

Mathematica, 230,120,116,113 110 bytes
f=(t=Table;a=#;s=Length@a;t[v=t[c=m=0;t[h=a[[y,x]];If[h>m,c++;m=h],{y,s}];c,{x,s}];a=Thread@Reverse@a;v,{4}])&

Usage:
f[{
  {4, 3, 5, 2, 1},
  {5, 4, 1, 3, 2},
  {1, 5, 2, 4, 3},
  {2, 1, 3, 5, 4},
  {3, 2, 4, 1, 5}
}]

{{2, 3, 1, 4, 5}, {3, 4, 3, 2, 1}, {1, 2, 2, 2, 2}, {3, 3, 2, 1, 2}}

a[[y]][[x]] is a[[y,x]]. And using Array might be shorter than Table.

JavaScript, 335 264 256 213
T=I=>((n,O)=>(S=i=>i--&&O.push([])+S(i)+(R=(j,a,x)=>j--&&R(j,0,0)+(C=k=>k--&&((!(a>>(b=I[(F=[f=>n-k-1,f=>j,f=>k,f=>n-j-1])[i]()][F[i+1&3]()])))&&++x+(a=1<<b))+C(k))(n)+O[i].push(x))(n,0,0))(4)&&O)(I.length,[],[])

Evaluate in the browser's JavaScript console (I used Firefox 34.0, doesn't seem to work in Chrome 39??)  Test with:
JSON.stringify(T([[4, 3, 5, 2, 1], [5, 4, 1, 3, 2], [1, 5, 2, 4, 3], [2, 1, 3, 5, 4], [3, 2, 4, 1, 5]]));

Here's the current incarnation of the ungolfed code - it's getting harder to follow:
function countVisibleTowers(input) {
  return ((n, out) =>
      (sideRecurse = i =>
          i-- &&
          out.push([]) +
          sideRecurse(i) +
          (rowRecurse = (j, a, x) =>
              j-- &&
              rowRecurse(j, 0, 0) +
              (columnRecurse = k =>
                  k-- &&
                  ((!(a >> (b = input[
                                        (offsetFtn = [
                                            f => n - k - 1,   // col negative
                                            f => j,           // row positive
                                            f => k,           // col positive
                                            f => n - j - 1    // row negative
                                        ])[i]()
                                     ]
                                     [
                                        offsetFtn[i + 1 & 3]()
                                     ]))) &&
                  ++x +
                  (a = 1 << b)) +
                  columnRecurse(k)
              )(n) +
              out[i].push(x)
          )(n, 0, 0)
      )(4) && out
  )(input.length, [], [])
}

I intentionally didn't look at any of the other answers, I wanted to see if I could work something out myself.  My approach was to flatten the input arrays to a one-dimensional array and precompute offsets to the rows from all four directions.  Then I used shift right to test whether the next tower was falsy and if it was, then increment the counter for each row.
I am hoping there is lots of ways to improve this, perhaps not precalculate the offsets, but rather use some sort of overflow/modulo on the 1D input array?  And perhaps combine my loops, get more functional, deduplicate.
Any suggestions would be appreciated!
Update #1 : Progress, we have the technology!  I was able to get rid of the precalculated offsets and do them inline with ternary operators strung together.  Also was able to get rid of my if statement and convert the for loops into whiles.
Update #2 : This is pretty frustrating; no pizza party for me.  I figured going functional and using recursion would shave off many bytes, but my first few tries ended up being larger by as much as 100 characters!  In desperation, I went whole-hog on using ES6 fat arrow functions to really pare it down.  Then I took to replacing boolean operators with arithmetic ones and removing parens, semi-colons and spaces whereever I could.  I even quit declaring my vars and polluted the global namespace with my local symbols.  Dirty, dirty.  After all that effort, I beat my Update #1 score by a whopping 8 characters, down to 256.  Blargh!
If I applied the same ruthless optimizations and ES6 tricks to my Update #1 function, I'd beat this score by a mile.  I may do an Update #3 just to see what that would look like.
Update #3 : Turns out the fat arrow recursive approach had lots more life in it, I just needed to work with the 2 dimensional input directly rather than flattening it and get better about leveraging the closure scopes.  I rewrote the inner array offset calculations twice and got the same score, so this approach may be close to minned out!

Java, only 352 350 325 bytes...
class S{public static void main(String[]a){int n=a.length,i=0,j,k,b,c;int[][]d=new int[n][n];for(;i<n;i++)for(j=0;j<n;)d[i][j]=a[i].charAt(j++);for(i=0;i<4;i++){int[][]e=new int[n][n];for(k=0;k<n;k++)for(j=0;j<n;)e[n-j-1][k]=d[k][j++];d=e;for(j=n;j-->(k=c=b=0);System.out.print(c))for(;k<n;k++)b=d[j][k]>b?d[j][k]+0*c++:b;}}}

Input like 43521 54132 15243 21354 32415
Output like: 23145343211222233212
Indented:
class S{
    public static void main(String[]a){
        int n=a.length,i=0,j,k,b,c;
        int[][]d=new int[n][n];
        for(;i<n;i++)
            for(j=0;j<n;)d[i][j]=a[i].charAt(j++);
        for(i=0;i<4;i++){
            int[][]e=new int[n][n];
            for(k=0;k<n;k++)
                for(j=0;j<n;)e[n-j-1][k]=d[k][j++];
            d=e;
            for(j=n;j-->(k=c=b=0);System.out.print(c))
                for(;k<n;k++)b=d[j][k]>b?d[j][k]+0*c++:b;
        }
    }
}

Any tips would be greatly appreciated!

you have a few extra whitespaces between for loops

@proud haskeller Thank you!

You could change for(;i<n;i++) to for(;++i<n;) and initialize i to -1. Then use these to do stuff. You can do the same with the other loop too.

You can use a[i].charAt(j)-'0' instead of explicit parsing. This also doesn't require delimiters in the input (makes input format more like output format).

Also, in for-loops, you can always stuff something useful into the "loop increment" part. This makes code more obscure and removes one semicolon. For example: for(j=n;j-->0;System.out.print(c)).

Also, d.clone() is shorter than new int[n][n].

@anatolyg d.clone() is a shallow clone.

@proudhaskeller That would save 1 character for the cost of 1 character.

Python 2 - 204 bytes
def f(l):n=len(l);k=[l[c]for c in range(n)if l[c]>([0]+list(l))[c]];return f(k)if k!=l else n
r=lambda m:(l[::-1]for l in m)
m=input();z=zip(*m);n=0
for t in z,r(m),r(z),m:print map(f,t)[::1-(n>1)*2];n+=1

This is probably a really poor golf. I thought the problem was interesting, so I decided to tackle it without looking at anyone else's solution. As I type this sentence I have yet to look at the answers on this question. I wouldn't be surprised if someone else has already done a shorter Python program ;)
I/O Example
$ ./towers.py <<< '[[4,3,5,2,1],[5,4,1,3,2],[1,5,2,4,3],[2,1,3,5,4],[3,2,4,1,5]]'
[2, 3, 1, 4, 5]
[3, 4, 3, 2, 1]
[1, 2, 2, 2, 2]
[3, 3, 2, 1, 2]

You may optionally include whitespace in the input. Pretty much anywhere, honestly. So long as you can eval() it, it'll work.
Explanation
The only interesting part of this program is the first line. It defines a function f(l) that tells you how many towers can be seen in a row, and the rest of the program is just applying that function to every possible position.
When called, it finds the length of l and saves it in a variable n. Then it creates a new variable k with this pretty monstrous list comprehension:
[l[c]for c in range(n)if l[c]>([0]+list(l))[c]]

It's not too bad when you break it down. Since n==len(l), everything before the if just represents l. However, using if we can remove some elements from the list. We construct a list with ([0]+list(l)), which is just "l with a 0 added to the beginning" (ignore the call to list(), that's only there because sometimes l is a generator and we need to make sure it's actually a list here). l[c] is only put into the final list if it's greater than ([0]+list(l))[c]. This does two things:

Since there's a new element at the beginning of the list, the index of each l[c] becomes c+1. We're effectively comparing each element to the element to the left of it. If it's greater, it's visible. Otherwise it's hidden and removed from the list.
The first tower is always visible because there's nothing that can block it. Because we put 0 at the beginning, the first tower is always greater. (If we didn't do this [0]+ nonsense and just compared l[c] to l[c-1], Python would compare the first tower to the last one (you can index into a list from the end with -1, -2, etc.), so if the last tower was taller than the first one we'd get the wrong result.

When all is said and done, l contains some number of towers and k contains each one of those that isn't shorter than its immediate neighbour to the left. If none of them were (e.g. for f([1,2,3,4,5])), then l == k. We know there's nothing left to do and return n (the length of the list). If l != k, that means at least one of the towers was removed this time around and there may be more to do. So, we return f(k). God, I love recursion. Interestingly, f always recurses one level deeper than is strictly "necessary". When the list that will be returned is generated, the function has no way of knowing that at first.
When I started writing this explanation, this program was 223 bytes long. While explaining things I realized that there were ways to save characters, so I'm glad I typed this up! The biggest example is that f(l) was originally implemented as an infinite loop that was broken out of when the computation was done, before I realized recursion would work. It just goes to show that the first solution you think of won't always be the best. :)

Matlab, (123)(119)
function r=m(h);p=[h rot90(h) rot90(h,2) rot90(h,3)];for i=2:size(p) p(i,:)=max(p(i,:),p(i-1,:));end;r=sum(diff(p)>0)+1

used like this:
m([
 4     3     5     2     1;
 5     4     1     3     2;
 1     5     2     4     3;
 2     1     3     5     4;
 3     2     4     1     5])

 [2 3 1 4 5 3 4 3 2 1 1 2 2 2 2 3 3 2 1 2]

C#, down to 354...
Different approach than TheBestOne used.
using System;
using System.Linq;

class A
{
    static void Main(string[] h)
    {
        int m = (int)Math.Sqrt(h[0].Length),k=0;
        var x = h[0].Select(c => c - 48);
        var s = Enumerable.Range(0, m);
        for (; k < 4; k++)
        {
            (k%2 == 0 ? s : s.Reverse())
                .Select(j =>
                        (k > 0 && k < 3 ? x.Reverse() : x).Where((c, i) => (k % 2 == 0 ? i % m : i / m) == j)
                                                          .Aggregate(0, (p, c) =>
                                                                        c > p%10
                                                                            ? c + 10 + p/10*10
                                                                            : p, c => c/10))
                .ToList()
                .ForEach(Console.Write);
        }
    }
}

It seems you computer paste \n instead of newlines, I just replaced them by spaces, so the code runs right away when someone is copying it. And I allowed myself to delete the last end (that closes the function, which is not necessary) which saves additional 4 characters, I hope that was ok=)

It seems that matlab was not happy with the spaces so I changed them to semicolons. Good point about the trailing end though, thx :)

authors: حفیظ اللّه یوسفی


text:
Calculate the points in a "sjoelen"-game
Okay, so yesterday was 2nd Christmas day and my (grand)parents and me had a game of "sjoelen", as it is called in the Netherlands. The inner programmer came up in me, but just when I had the answer, I lost it. I want you to remake it.
The rules:
You have a wooden plank, a sjoelbak, with 4 boxes, each with their own number. When a schijf (A puck-like object) goes in one of the boxes you get the points above that box.

When there is a schijf in all 4 of the boxes, you don't get 10 but you get 20 points.
Example:
From left to right: 3 5 4 3
Each box has at least 3 schijven (Plural of schijf) so that is 20 * 3 = 60 points.
Resulting values: 0 2 1 0
0*2 + 2*3 + 1*4 + 0*1 = 10 points.
Which makes a total of 60+10 = 70 points.
The input:
The amount of schijven from left to right, ie "4 5 4 5", [4,5,4,5], "4\n5\n4\n5", whatever you like.
The output:
The amount of points, ie 84, as output, variable, return or on top of the stack, whatever you like.
As in each and every code golf, you can not use external scripts and the code with the least bytes wins.
PS: As you may have already noticed, I'm Dutch. Feel free to edit possible grammar mistakes.

Does output have to be stdout or can it be a function return or the remaining item left on the stack (for a stack based language)?

@globby Can be everything

I think sjoelen is leuk!

Is there a limit on the number of schijf in each box?

@BassetHound You get 30 schijven per round, so 30 in the 4 equals 120 points. It's possible, but not the best score (7 in all = 140, + 2 in 4 = 148)

CJam, 23 21 20 bytes
q~_$0=f+1m>{X):X*+}*

I might be able to golf a couple of bytes off this.
Input is like
[3 5 4 3]

Output is the score
70

How it works
q~                         "Read the input and evaluate into an array";
  _$0=                     "Copy the array, sort it and get the minimum number";
                           "This minimum is the number of common schijven";
      f+                   "Increment each of the schijven by the common schijven number";
        1m>                "Take 1 element from the end of the array and put";
                           "it in the beginning";
           {      }*       "Reduce the elements of the array based on this block";
            X):X           "Increment and update the value of X (initially 1)";
                *          "Multiply the number of schijven with X";
                 +         "Add it to current score";

Algorithm

Since I have right shifted the number of schijven, the score order now becomes [1 2 3 4].
Moreover, using the fact that 1 + 2 + 3 + 4 = 10, I simply add the minimum common schijven to each one to get the effect of bonus 10 score.
Now when I reduce, I get 2 elements initially on stack, the first one, which I ignore is the one with a score of 1 each, then I multiply the second one with 2 and add it to first. In the next iteration, I get the current sum and score 3 schijven. And so on.

Try it online here

Least bytes (so far), accepted. Thanks for the explanation.

@Charlie Why do you accept an answer so quickly? You better wait 1-2 weeks before accepting an answer.

APL (Dyalog Classic), 16 13 12 bytes
-3 thanks to @Adám
(+/+\)1⌽⌽+⌊/

Try it online!
⌽+⌊/ reverse(arg) + min(arg)
1⌽ rotate 1 to the left
+\ partial sums
+/ sum

Piet, 240 (30*8) codels, 138 containing actual code
Codel size 10, for better visibility

Test examples:
D:\codegolf\npiet-1.3a-win32>npiet sjoelen_point_count_cs10.png
? 3
? 5
? 4
? 3
70
D:\codegolf\npiet-1.3a-win32>npiet sjoelen_point_count_cs10.png
? 4
? 5
? 4
? 5
84

Flow display:
Using my own shorthand for easier handling and compact display.
It shows the general program flow, not the exact locations of the codels.
NOP ADD DIV GRT DUP INC END
 0   +   /   >   =   c   ~
PSH SUB MOD PTR ROL OUN
 X   -   %   #   @   N
POP MUL NOT SWI INN OUC
 ?   *   !   $   n   C

1X!nnnn=5X2X@=5X2X@=5X2X@=5X1X@**
       0                        *
       0       @+5X1X@1X-4X1X@  !
       0       -             0  !
       0       X1!X1X6+*==X40000#  <--pointer if top of stack=1 (all boxes full,
       0                     0  2      add 20 points, decrement count for all boxes)
       0000-X1@X1X2-X1@X1X3-X1  X  |  pointer if top of stack=0 (not all boxes full,
                                *  V   add 2a+3b+4c+d)
           ~N++++*X4@X2X3*X3@X1X2

Full explanation:
      (score=0)  a   b   c   d
      1 PSH NOT INN INN INN INN

      ..... sort and duplicate the numbers .....
**1** DUP 5 PSH 2 PSH ROL DUP 5 PSH 2 PSH ROL DUP 5 PSH 2 PSH ROL DUP 5 PSH 1 PSH ROL

      ( a*b*c*d ) (convert to boolean) 1 if all boxes are full, 0 if at least one box is empty
      MUL MUL MUL NOT NOT

      change direction if 1 (**2**)
      go straight ahead if 0 (**3**)
      PTR

      ( compress 20=4*4+4 )       (0-1=-1/ neg. roll) score+20
**2** 4 PSH DUP DUP MUL ADD 6 PSH 1 PSH NOT 1 PSH SUB ROL ADD

      (put score back to bottom of stack) ... a=a-1, b=b-1, c=c-1, d=d-1 ...
      5 PSH 1 PSH ROL 1 PSH SUB 4 PSH 1 PSH ROL 1 PSH SUB 3 PSH
      1 PSH ROL 1 PSH SUB 2 PSH 1 PSH ROL 1 PSH SUB

      loop to **1**

      (   a*2   )               (   b*3   )               (  c*4  )
**3** 2 PSH MUL 2 PSH 1 PSH ROL 3 PSH MUL 3 PSH 2 PSH ROL 4 PSH MUL

      +2a +3b +d +score
      ADD ADD ADD ADD

      output score
      OUN

Save the image and try it out in this online Piet interpreter:
PietDev online Piet interpreter

A Piet answer ^.^

Of course! I try to add Piet answers whenever manageable ;)

R, 41 40 chars
b=min(a<-scan());sum(5*b+(a-b)*c(2:4,1))

Usage:
> b=min(a<-scan());sum(5*b+(a-b)*c(2:4,1))
1: 4 5 4 5
5:
Read 4 items
[1] 84
> b=min(a<-scan());sum(5*b+(a-b)*c(2:4,1))
1: 3 5 4 3
5:
Read 4 items
[1] 70

In the last example, a is vector 3 5 4 3, a-b is 0 2 1 0, which we multiply with vector 2 3 4 1 thus giving 0 6 4 0 which we add with 5*b giving 15 21 19 15 (5*b being recycled for each member of the added vector, hence effectively adding 4*5*b), which we finally sum, thus giving 70.

40 bytes: b=min(a<-scan());sum(5*b+(a-b)*c(2:4,1))

Mathematica, 38 32 23 20 bytes
(#+Min@#).{2,3,4,1}&

(With help from swish)
Use by tacking the input on to the end:
(#+Min@#).{2,3,4,1}&@{3,5,4,3}

70

Alternate (36 bytes):
20*Min@#+Total[(#-Min@#)*{2,3,4,1}]&

Tr[(# + Min@#) {2, 3, 4, 1}] &

@swish So clever!

That's the whole function. You don't need to add 20*Min@#, you can get rid of it by replacing minus with plus, because conveniently 2+3+4+1==10.

@swish Oh! That's even better. But I can't wrap my head around why that works?

Actually you can do dot product here (# + Min@#).{2, 3, 4, 1}&

@swish Well, thanks for all the help, but you should have just posted your own answer. :D

When ported into TI-BASIC, it's 15 bytes: sum({2,3,4,1}(Ans+min(Ans

J, 23 22 chars
   (+/ .*&2 3 4 1@(+<./))

Example:
   test =. 3 5 4 3
   (+/ .*&2 3 4 1@(+<./)) test
70

Try it here.
(23 long explicit function definition: v=:3 :'+/+/\.3|.y+<./y')

Why not just +/2 3 4 1*(+<./)?

@swish I prefer writing complete functions although it wasn't a requirement here. Post/add it if you would like.

How about 2 3 4 1+/ .×]+<./?

JavaScript (ES6), 93 47 bytes
s=(a,b,c,d)=>10*Math.min(a,b,c,d)+a*2+b*3+c*4+d

Usage: s(1, 2, 3, 4)
How it works: the function looks for the smallest number in the arguments, and multiplies that by 10 (not with 20) and adds the rest of the score. It's not necessary to multiply by 20 and substract parts from the score to continue the calculation.
Thanks to edc65 for sharing improvements!
Un-golfed:
function score(a, b, c, d) {
    return 10 * Math.min(a, b, c, d) + a * 2 + b * 3 + c * 4 + d;
}

Use 10 with min, no need to subtract (function s(a,b,c,d){return 10Math.min(a,b,c,d)+a2+b3+c4+d;})

And in ES6: S=(a,b,c,d)=>10*Math.min(a,b,c,d)+a*2+b*3+c*4+d

@edc65 Awesome, thanks!

Pyth, 15
sm*hd+@QtdhSQUQ

Input should be given comma separated on STDIN, e.g.
3,5,4,3

This uses the same trick that many other solutions have used, of adding the minimum to each element to account for the bonus. The minimum is hSQ in the above code. To account for multiplying by 2, 3, 4, and 1, I map d over the list [0,1,2,3], and multiply the (d-l)th element of the input by d+1. Thus, the -1th element is multiplied by 1, the zeroth by 2, the first by 3 and the second by 4. Then I sum.

Ostrich v0.1.0, 48 41 characters (way too long)
.$0={}/:n;{n-}%)\+1:i;{i*i):i;}%{+}*20n*+

This is simply the same as the old version below, except that instead of using @ to rotate the whole stack, )\+ (right uncons) is used instead.
Old version:
.$0={}/:n;{n-}%{}/{4@}3*1:i;]{i*i):i;}%{+}*20n*+

I have actually discovered two bugs in my very newly implemented language, annotated in the description below. (The language is currently very, very similar to Golfscript, so if you know Golfscript it should be fairly easy to read.
.$0=   get min value (for the *20 thingy)
{}/    *actually* get min value (BUG: `array number =' returns a single-element array...)
:n;    store as n
{n-}%  subtract this value from all array elements
{}/    dump array onto stack
{4@}3* rotate stack so that instead of 2 3 4 1, multipliers are 1 2 3 4
       (BUG: negative rotations don't work)
1:i;   set i (the multiplier) to 1
]{i*   multiply each array element by i
i):i;  increment i
}%     (do the previous 2 lines over each array element)
{+}*   add up all the array elements
20n*+  add 20*n (the min value we got in line 1)

Expects input as an array on STDIN, because I'm a doorknob and forgot to implement I/O in v0.1.0.
Solving an actual problem in Ostrich is nice, because it shows me exactly how much more stuff I need to add to the language :D

Good luck with your language, it looks nice so far ;)

Python 2, 43 bytes
lambda i:i[1]-i[3]+2*(sum(i)+i[2]+5*min(i))

Inspired by @user2487951's answer.

Nice algorithm! For a full program, you need input and print statements also.

@user2487951 One of the allowable means of output was "return", so while this is not a full program, it is a valid answer.

Haskell, 40
g l@[a,b,c,d]=2*a+3*b+4*c+d+10*minimum l

instead of removing the minimum number from the rest and adding additional 20s, this adds additional 10 for the minimum number.

Nice solution. You did mix up the order though, it should be ..4*c+d..

Jagl Alpha 1.2 - 20 bytes
Input is in stdin in format (3 4 5 6), output is left on stack:
T~dqZ*S1 5r]%{U*}/b+

Waiting for a response from the original poster about the output format. Since input is specified as "whatever you like", I am going to assume that my input can be an array on the top of the stack. Now takes input on stdin.
Explanation:
T~                            Get input from stdin and evaluate
  dqZ*                      Duplicate, get minimum, and multiply that by 10
      S1 5r]                Swap (so array is on top), push range 1-5 exclusive, and rotate
            %{U*}/          Zip arrays together, and multiply each pair
                  b+P       Get the sum of that, add the common minimum, and print

First answer is accepted, edited post to make it clear

@Optimizer point taken. Edited.

Matlab, 27
Took me a while to understand that it is single player game. With the help of anonymous function
f=@(N)N*[2;3;4;1]+10*min(N)

which is invoked with row vector
f([3 5 4 3]) == 70
f([7 7 9 7]) == 148

I think it's generally accepted around these parts to drop the f= for 2 fewer bytes. The function gets stored in the ans variable instead.

[2:4,1] will shave off 2 bytes if the input is column vector.

Java, 84 bytes
int A(int[]a){int m=9;for(int i:a)m=i<m?i:m;return 10*m+a[3]+2*a[0]+3*a[1]+4*a[2];}

I have the idea this can be golfed any further, but this is it for now.
Call with A(new int[]{3,5,4,3}), output is returned as int (Because System.out.println() would double the bytes)
Ungolfed
int getScore(int[] input){
    int min=9;

    for(int x:input) {
        if(x<min){
            min=x;
        }
    }

    return 10*min + 2*input[0] + 3*input[1] + 4*input[2] + 1*input[3];
}

GolfScript, 22 bytes
~3,{1$>~;}%+$(11*+{+}*

Reads input from stdin, in the format [3 5 4 3].  Writes output to stdout.  (If taking the input as an array on the stack is allowed, the leading ~ may be omitted for a total of 21 bytes.)
This uses a somewhat different strategy than the CJam / Pyth / etc. solutions: I first build an array with 2 copies of the first input value, 3 of the second, 4 of the third and one of the fourth.  Then I sort this array, pull out the smallest element, multiply it by 11 and sum it with the other elements.

Python 2, 51
Uninspired, but short:
l=input()
print l[0]*2+l[1]*3+l[2]*4+l[3]+10*min(l)

More pythonic:
l=input()
print sum(map(lambda x,y:x*y,l,[2,3,4,1]))+10*min(l)

If the input is [3,5,4,3], will this return 70?

Yes, it does in both cases. And returns 84 for [4,5,4,5].

Julia, 48 35 characters
function p(m);sum([2 3 4 1].*m)+10minimum(m);end
in compact assignment form:
p(m)=sum([2 3 4 1].*m)+10minimum(m)

Example:
julia> p([3 5 4 3])
70

Javascript, 97 bytes
a=prompt().split(" "),b=Math.min.apply(1,a);alert(20*b+2*(a[0]-b)+3*(a[1]-b)+4*(a[2]-b)+(a[3]-b))

Javascript, ES6, 57
f=(a,b,c,d)=>a*b*c*d?20+f(--a,--b,--c,--d):a*2+b*3+c*4+d

I wanted to see how recursion would turn out, and while it is definitely not the shortest answer, I felt like it turned out well.
a*b*c*d: It takes the input values and finds the product of all of them, and evaluate that as a Boolean expression for an inline if statement. This will return false if one or more of the values is 0, and true for any other value.
20+f(--a,--b,--c,--d): If it returns true, the function returns 20 (for the schijven set) plus the recursive call of the function for all of the values minus one (To remove that schijven set). In this way it will recursively loop through until at least one of the boxes is empty.
a*2+b*3+c*4+d After at least one box it empty, the else part of the inline if statement will run. It just returns the points for the remaining schijven in the boxes.
Thus at the end all of the 20 point schijven sets, and the remanding points are summed up and returned from the function, producing the answer.

Haskell 42 chars
f l=10*minimum l+sum(zipWith(*)[2,3,4,1]l)

Code the sum expressly: f l@[a,b,c,d]=10*minimum l+2*a+3*b+4*c+d - saves 2 chars

HPPPL (HP Prime Programming Language), 58 57 bytes
The * between 10 and min isn’t necessary, so I removed it.
EXPORT s(m)
BEGIN
return sum([2,3,4,1].*m)+10min(m);
END;

HPPPL is the programming language for the HP Prime color graphing calculator/CAS.
Example runs:

If it doesn’t have to be a program, then it’s realizable in a 40 39 bytes one-liner:
m:=[3,5,4,3];sum([2,3,4,1].*m)+10min(m)

Staq, 72 characters
't't't't{aii*XX}$&iia$&ia$&a+XX+XX+|{mxx}{lxX}{k>?m!l}kkk&iiqi&ii*s*t|+:

Example run:
Executing D:\codegolf\Staq\sjoelen codegolf.txt

3
5
4
3
70

Execution complete.
>

Staq has two stacks, one active, one passive. The | command switches the active stack to passive and vice versa.
Everything between curly braces defines a function, the first letter after the opening brace is the function name, the rest until the closing brace is the function itself. Overriding functions, recursion and nested functions are possible. {aii} would define a function a that would increment the top of the stack twice. Every following instance of a in the code will be replaced by ii.
Comments inside Staq prorams:
& adds a zero on top of the stack, [ instructs the pointer to jump to the corresponding ] if the top of the stack is zero, x deletes the topmost value on the stack. So, comments can be written into the code in the form of &[here is a comment]x
Explanation (also executable):
'                                      &[input number]x
 t                                     &[copy top of active stack to passive stack]x
  t't't                                &[input next three numbers and copy them to the passive stack]x
       {aii*XX}                        &[define function a (increment twice, multiply the two topmost values, then delete the second value on the stack twice)]x
               $                       &[move top value to the bottom of the stack]x
                &ii                    &[put zero on top of the stack, incremment twice]x
                   a                   &[function a]x
                    $&ia$&a
                           +           &[put sum of the two topmost values on top of the stack]x
                            XX         &[delete second stack value, twice]x
                              +XX+
                                  |    &[switch active/passive stack]x
{mxx}                                  &[define function m: delete two topmost stack values]x
     {lxX}                             &[define function l: delete topmost stack value, then delete second value of remaining stack]x
          {k>?m!l}                     &[define function k: boolean top > second value? put result on top of the stack, if top>0 then execute m, if top = 0 then execute l]x
                  kkk&ii
                        q              &[put square of top value on top of the stack]x
                         i&ii
                             *         &[multiply two topmost values and put result on top of the stack]x
                              s        &[move bottom stack value to the top]x
                               *t|+
                                   :   &[output result]x

https://esolangs.org/wiki/Staq
The program uses one stack (initially active) to calculate 2a+3b+4c+d, and the second stack (initially passive) to calculate 10 times the minimum of the input values. Then both results are summed up and displayed.

PowerShell for Windows, 48 47 bytes
-1 byte thanks to mazzy
$args|%{$a+=++$i%4*$_+$_}
$a+10*($args|sort)[0]

Try it online!

Try it online!. Should we specify Powershell for Windows when we use the sort alias? see meta

@mazzy Yeah, probably should. I just forget about that because TIO is technically on linux but uses the windows aliases

source: Stack Exchange

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

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

sort: votes


text:
Time Travelling Stock Trader
Story
Long time ago Bobby created a Bitcoin wallet with 1 Satoshi (1e-8 BTC, smallest currency unit) and forgot about it. Like many others he later though "Damn, if only I invested more back then...".
Not stopping at daydreaming, he dedicates all of his time and money to building a time machine. He spends most of his time in his garage, unaware of worldly affairs and rumors circulating about him. He completes the prototype a day before his electricity is about to be turned off due to missed payments. Looking up from his workbench he sees a police van pulling up to his house, looks like the nosy neighbours thought he is running a meth lab in his garage and called the cops.
With no time to run tests he grabs a USB-stick with the exchange rate data of the past years, connects the Flux Capacitor to the Quantum Discombobulator and finds himself transported back  to the day when he created his wallet
Task
Given the exchange rate data, find out how much money Bobby can make. He follows a very simple rule: "Buy low - sell high" and since he starts out with an infinitesimally small capital, we assume that his actions will have no impact on the exchange rates from the future.
Input
A list of floats > 0, either as a string separated by a single character (newline, tab, space, semicolon, whatever you prefer) passed as command line argument to the program, read from a textfile or STDIN or passed as a parameter to a function. You can use numerical datatypes or arrays instead of a string because its basically just a string with brackets.
Output
The factor by which Bobbys capital multiplied by the end of trading.
Example
Input:  0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41

Exchange rate: 0.48 $/BTC, since it is about to drop we sell all Bitcoins for 4.8 nanodollar. Factor = 1
Exchange rate: 0.4, do nothing
Exchange rate: 0.24 $/BTC and rising: convert all $ to 2 Satoshis. Factor = 1 (the dollar value is still unchanged)
Exchange rate: 0.39 - 2.1 $/BTC: do nothing
Exchange rate: 2.24 $/BTC: sell everything before the drop. 44.8 nanodollar, factor = 9.33
Exchange rate: 2.07 $/BTC: buy 2.164 Satoshis, factor = 9.33
Exchange rate: 2.41 $/BTC: buy 52.15 nanodollar, factor = 10.86
Output: 10.86

Additional Details
You may ignore weird edge cases such as constant input, zero- or negative values, only one input number, etc.
Feel free to generate your own random numbers for testing or using actual stock charts. Here is a longer input for testing (Expected output approx. 321903884.638)
Briefly explain what your code does
Graphs are appreciated but not necessary

If we take the numbers via function argument, does it still have to be a string, or could we directly take an array?

@MartinBüttner I pondered about it for a while, whether the input is a string, a numerical array or a free choice, there are always some languages which get an advantage. There doesnt seem to be a general consensus on this, and writing two programs, one for a numerical- and one for string input and averaging both scores seems like overkill.

What about the Infinite Improbability Drive? :)

@DenDenDo I usually use a phrase along the lines of "you may take input in any convenient list or string format, as long as the input is not preprocessed". This allows all sorts of delimited strings, as well as arrays/lists/tuples, but it doesn't allow people to assume it's sorted or something. This way, everyone can use what's shortest in their language (because if you pick some subset, there's guaranteed to be some language, where that subset is really awkward to handle).

Getting back to the problem, do we need to round the BTC and/or $ values at a given precision, on every iteration? For example, in the real world one's BTC wallet must be rounded to the Satoshi. This makes a difference, because in your example, at 2.07 you can only buy 2s (not 2.164); then at 2.41 your 2s buy you 48.2 n$ (not 52.15) so the factor is 10.04 (not 10.86). Unless you keep a separate $ wallet with the change and need to add it back each time. What about dollars? Can anyone today claim to have a nanodollar? I believe the smallest amount one can hold is 1¢.

No rounding is necessary, we are already too far from reality to care about such things, just use regular float precision

The exchange rate data can become increasingly unreliable as he moves forward through time, selling and buying. He is modifying history by acquiring money (which wasn't his in the original timeline) so he must have an effect on the economy if he manages to get a large enough amount of money.

@vsz: This is bitcoin we are talking about =)  Bitcoin is known for having so many people trying to manipulate the currency that surely they wouldn't notice someone making a mere 300 million bit coins ;)

@CortAmmon: you're saying that BTC trading isn't chaotic? ;-)

Taking the daily data of the past two years from bitcoincharts.com results in a multiplier of 1307923. Looks really big, but starting with 1 Satoshi this turns into roughly 4$, so the infinitesimality assumption still holds

I think you're assuming no brokerage fees, and that he always ends with his assets in BTC. Is that correct? Are you also requiring the input to be $/BTC or can it be BTC/$?

I like the story! Upvote

APL, 16 chars
{×/1⌈÷/⊃⍵,¨¯1⌽⍵}

This version uses @Frxstrem's simpler algorithm and @xnor's max(r,1) idea.
It also assumes that the series is overall rising, that is, the first bitcoin value is smaller than the last one. This is consistent with the problem description. To get a more general formula, the first couple of rates must be dropped, adding 2 chars: {×/1⌈÷/⊃1↓⍵,¨¯1⌽⍵}
Example:
    {×/1⌈÷/⊃⍵,¨¯1⌽⍵}  0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41
10.86634461
    {×/1⌈÷/⊃⍵,¨¯1⌽⍵}  (the 1000 array from pastebin)
321903884.6

Explanation:
Start with the exchange rate data:
    A←0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41

Pair each number with the preceding one (the first will be paired with the last) and put them into a matrix:
    ⎕←M←⊃A,¨¯1⌽A
0.48 2.41
0.4  0.48
0.24 0.4
0.39 0.24
0.74 0.39
1.31 0.74
1.71 1.31
2.1  1.71
2.24 2.1
2.07 2.24
2.41 2.07

Reduce each row by division, keep those with ratio > 1, and combine the ratios by multiplication. This will eliminate any repeating factors in a row of successive rising rates, as well as the spurious ratio between the first and last exchange rates:
    ×/1⌈÷/M
10.86634461

Your assumption that you should always sell on the first position makes the longer input fail and returns a number less than 1 (which is obviously impossible).

@Frxstrem thanks, fixed. Now it gives the same result as your script. It would have been more helpful if the OP had given us a few test cases with results!

I love good APL solutions because, whenever I look at them, they trigger my "this is binary file gibberish" filter and I start looking for a file extension to figure out how to open it.

@CortAmmon that's not at all unfounded: APL employs many dozen graphic operators; on the surface they can remind you of the symbols from 8-bit DOS character sets. It is also a very terse language, meaning that a line of APL has very high information entropy. These two features combine to trigger the feeling of a binary file dumped into a DOS window. But it only lasts until you learn to appreciate the beauty of APL's symbols and syntax.

Python, 47
f=lambda t:2>len(t)or max(t[1]/t[0],1)*f(t[1:])

Example run on the test case.
Take a list of floats. Recursively multiplies on the profit factor from the first two elements until fewer than two elements remains. For the base case, gives True which equals 1.
Using pop gives the same number of chars.
f=lambda t:2>len(t)or max(t[1]/t.pop(0),1)*f(t)

So does going from the end of the list.
f=lambda t:2>len(t)or max(t.pop()/t[-1],1)*f(t)

For comparison, my iterative code in Python 2 is 49 chars, 2 chars longer
p=c=-1
for x in input():p*=max(x/c,1);c=x
print-p

Starting with c=-1 is a hack to make the imaginary first "move" never show a profit. Starting the product at -1 rather than 1 lets us assign both elements together, and we negative it back for free before printing.

The longer testcase exceeds the default recursion limit by 1. f(x[:999]) still gives the correct result though. For longer input you could split it in chunks ([n:(n+1)*500 + 1] for n in range(N_elem/500) ) and multiply the partial factors

The recursion limit is implementation dependent; you can use Stackless Python to avoid it.

Or just use sys.setrecursionlimit (in CPython)

Python, 79 81 76 77 bytes
f=lambda x:reduce(float.__mul__,(a/b for a,b in zip(x[1:],x[:-1]) if a>b),1.)

x is the input encoded as a list. The function returns the factor.

Maybe it's just my Python version, but I had to use 1. instead of 1 at the end of the function, otherwise I get TypeError: descriptor 'mul' requires a 'float' object but received a 'int'

BTW, smart algorithm!

You don't need that f= part.

CJam, 33 bytes
q~{X1$3$-:X*0>{\;}*}*](g\2/{~//}/

This can be golfed further.
Takes input from STDIN, like
[0.48 0.4 0.24 0.39 0.74 1.31 1.71 2.1 2.24 2.07 2.41]

and outputs the factor to STDOUT, like
10.866344605475046

Try it online here

Pyth, 18
u*GeS,1ceHhHC,QtQ1

Explanation:
u                 reduce, G is accumulator, H iterates over sequence
 *G               multiply G by
   eS             max(
     ,1               1,
       ceHhH            H[1]/H[0])
 C                H iterates over zip(
  ,QtQ                                Q,Q[1:])
 1                G is initialized to 1

max(H[1]/H[0],1) idea thanks to @xnor

C#, 333, 313
My first attempt. Could probably optimize it more but like I said first attempt so will get the hang of it!.
double a(double [] b){var c=0.0;var d=1;for(int i=0;i<b.Count();i++){c=(d==1)?(((i+1)<b.Count()&&b[i+1]<=b[i]&&d==1)?((c==0)?b[i]:b[i]*c):((i+1)>=b.Count()?(c*b[i])/b[0]:c)):((i+1)<b.Count()&&b[i+1]>b[i]&&d==0)?c/b[i]:c;d=((i+1)<b.Count()&&b[i+1]<b[i]&&d==1)?0:((i+1)<b.Count()&&b[i+1]>b[i]&&d==0)?1:d;}return c;}

Input
0.48, 0.4, 0.24, 0.39, 0.74, 1.31, 1.71, 2.1, 2.24, 2.07, 2.41

Output
10.86

Edit: Thanks to DenDenDo for suggesting not using math.floor to round and using int instead of bool to cut chars. Will remember that for future puzzles!

Heya, thanks for the tips. I updated as suggested.

Looks like you are rounding to two digits with Math.Floor(...) which is not required. Also, i don't know whether its possible in C#, but usually you can use 1 and 0 for true and false.

Sorry, thought rounding to 2 was required cause everyone was printing 10.86 and I was getting 10.866 and rounding up. You can for other c languages but not for C#. Though that did give me an idea so am now using 1 and 0 for my boolean checks. Reduced it a bit more. Thanks!

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


text:
Construct a graph
In this challenge, your task is to construct an undirected graph from a sequence of directives. There is one directive for each nonnegative integer, and each transforms a given graph into a new one.

Directive 0: Add a new disconnected node.
Directive 1: Add a new node, and connect it to every existing node.
Directive m > 1: Remove all nodes whose degree (number of neighbors) is divisible by m. Note that 0 is divisible by all m, so disconnected nodes are always removed.

The directives are applied one by one, from left to right, starting with the empty graph. For example, the sequence [0,1,0,1,0,1,3] is processed as follows, explained using awesome ASCII art. We start with the empty graph, and add a single vertex as directed by 0:
a

Then, add another vertex and connect it to the first, as directed by 1:
a--b

We add another disconnected vertex and then a connected one, as directed by 0 and 1:
a--b   c
 \  \ /
  `--d

We repeat this one more time, as directed by 0 and 1:
  ,--f--e
 /  /|\
a--b | c
 \  \|/
  `--d

Finally, we remove the degree-3 vertices a and b, as directed by 3:
f--e
|\
| c
|/
d

This is the graph defined by the sequence [0,1,0,1,0,1,3].
Input
A list of nonnegative integers, representing a sequence of directives.
Output
The number of nodes in the graph defined by the sequence.
Test cases
[] -> 0
[5] -> 0
[0,0,0,11] -> 0
[0,1,0,1,0,1,3] -> 4
[0,0,0,1,1,1] -> 6
[0,0,1,1,0,0,1,1,2,5,7,0,1] -> 6
[0,0,1,1,1,1,5,1,4,3,1,0,0,0,1,2] -> 6
[0,0,1,1,0,0,1,1,5,2,3,0,0,1,1,0,0,1,1,3,4,0,0,1,1,2,1,1] -> 8
[0,0,1,1,0,0,1,1,2,5,7,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,8] -> 14

Detailed rules
You can write a function or a full program. The shortest byte count wins. Standard loopholes are disallowed. Please explain your algorithm in your answer.

It's been a week, so I have accepted the shortest answer. If an even shorter one comes along later, I'll update my choice. An honorable mention goes to Peter Taylor's answer, on which several others were based on, including the winner.

As I read the question, thinking you have to actually draw the graph -  This is super tough, scrolls down - oh

@Optimizer Yeah, I wanted to pose the question so that the actual representation of the graph is not important, and the main difficulty would lie in implementing the directives. The number of nodes is just an easy way to check correctness.

I really like this challenge! It's like designing a data structure. You have to figure out how to represent the graph because the input and output formats aren't tied to it.

Pyth, 37 31
lu?+GH<H2m@Gdf%+*@GTtTs>GTHUGQY

This solution uses a reduce function (u) to build up a list, where each entry corresponds to a node remaining in the list, and the value of the entry corresponding to whether the node was originally added under directive 0 or 1.
G is the accumulator variable in the reduce function, and holds the aforementioned list. It is initialized to the empty list, Y.
H takes the value of each member of Q, the input, one by one. The result of the expression is assigned to G each time, and the next entry of Q is assigned to H, and the expression is rerun.
To update G properly, there are two possibilities, one for directive 0 or 1, and one for the other directives. These case are distinguished with the ternary ? ... <H2 ...
If H is 0 or 1, then all we need to do is append H to G. +GH accomplishes this.
Otherwise, the first thing that is need is to determine, for every node in the graph, how many neighbors it has. This is accomplished in two steps:
First, s>GT counts the number of nodes at or after the input node which are 1s. These are all connected to the input node, except that we will over count by 1 if the input node is a 1.
Second, we need the number of nodes earlier than the input node which are connected to it. This is 0 if the input node is a 0, and the index of the input node, T, if the input node is a 1. This value would be given by *@GTT. However, there is still the over count from the first section which needs to be corrected. Thus, we calculate *@GTtT instead, which is 1 less if the input node is a 1. These values are summed, to give the number of nodes connected to the input node.
% ... H will give 0 is that number is divisible by H, and thus should be removed, and will not give 0 otherwise.
f ... UG will thus give the indices of the input which should not be removed, since f is a filter, and 0 is falsy.
m@Gd converts these indices to the 0s and 1s of the corresponding nodes.
Finally, once the resultant list of nodes labeled 0 and 1 is found, its length is computed (l) and printed (implicit).
Broad idea thanks to @PeterTaylor.

GolfScript (53 bytes)
])~{:^1>{.-1:H)-,:T;{..H):H*T@-:T+^%!{;}*}%}{^+}if}/,

Online demo
I haven't actually golfed this yet, but I have discovered that it's not very easy to eliminate the H and T variables so this might be a local minimum.
Takes input on stdin in the format [0 1 2 3]. Leaves output on stdout.
Ungolfed:
])~{
  :^1>{
    # array of 0s and 1s
    # Each 0 has degree equal to the number of 1s after it
    # Each 1 has degree equal to the number of values before it plus the number of 1s after it
    .-1:H)-,:T;
    {
      # Stack: x
      # T' = T - x is the number of 1s after it
      # H' = H + 1 is the number of values before it
      # Degree is therefore H' * x + T' = H * x + T - x = (H-1)*x + T
      # Keep x unless degree % ^ == 0
      ..H):H*T@-:T+^%!{;}*
    }%
  }{^+}if
}/,

CJam, 129 75 73 68 61 46 42 bytes
Solution based on Peter's algorithm:
Lq~{I+I1>{0:U(<:L{LU<,*LU):U>1b+I%},}*}fI,

Code expansion to follow.

Previous solution (61 bytes):
Lq~{:N2<{U):UaN{f+U1$0f=+}*a+}{{:X,(N%_!{X0=L+:L;}*},Lf-}?}/,

Takes input from STDIN like:
[0 0 1 1 0 0 1 1 5 2 3 0 0 1 1 0 0 1 1 3 4 0 0 1 1 2 1 1]

Output is the number on STDOUT:
8

Algorithm:

Maintain an incrementing variable U which stores id of the node to be added.
Maintain a list of list in which , each list is a node with a unique id made up by the first element of the list and the remaining elements being the ids of connected nodes.
In each iteration (while reading the input directives),

If the directive is 0, add [U] to a list of list
If the directive is 1, add U to each list in the list of list and add another list comprised of first element of each of the list of list and U
For directive to remove, I filter out all lists of length - 1 divisible by m and keep noting the first element of those lists. After filtering, I remove all the removed id from remaining list of ids.

Code expansion:
Lq~{:N2<{U):UaN{f+U1$0f=+}*a+}{{:X,(N%_!{X0=L+:L;}*},Lf-}?}/,
L                                            "Put an empty array on stack";
 q~                                          "Evaluate the input";
   {                                }/       "For each directive";
    :N                                       "Store the directive in N";
      2<{     ...    }{    ...    }?         "If directive is 0 or 1, run the first";
                                             "block, else second";
{U):UaN{f+U1$0f=+}*a+}
 U):U                                        "Increment and update U (initially 0)";
     a                                       "Wrap it in an array";
      N{         }*                          "Run this block if directive is 1";
        f+                                   "Add U to each list in list of list";
          U1$                                "Put U and list of lists on stack";
             0f=                             "Get first element of each list";
                +                            "Prepend U to the above array";
                   a+                        "Wrap in array and append to list of list";
{{:X,(N%_!{X0=L+:L;}*},Lf-}
 {                   },                      "Filter the list of list on this block";
  :X,(                                       "Get number of connections of this node";
      N%_                                    "mod with directive and copy the result";
         !{        }*                        "If the mod is 0, run this block";
           X0=                               "Get the id of this node";
              L+:L;                          "Add to variable L and update L";
                       Lf-                   "Remove all the filtered out ids from the";
                                             "remaining nodes";
,                                            "After the whole process is completed for"
                                             "all directives, take length of remaining ";
                                             "nodes in the list of list";

Try it here

APL, 71 65 55 characters
{⍬≡⍺:≢⍵⋄r←1↓⍺⋄1<c←⊃⍺:r∇i⌿⍵/⍨i←0≠c|+/⍵⋄c:r∇∨⌿↑a(⍉a←⍵,1)⋄r∇0,0⍪⍵}∘(0 0⍴0)
{⍺←0 0⍴0⋄⍬≡⍵:≢⍺⋄(⍺{1<⍵:i⌿⍺/⍨i←×⍵|+/⍺⋄⍵:-⌿↑(1,1⍪⍺)1⋄0,0⍪⍺}⊃⍵)∇1↓⍵}
{g←0 0⍴0⋄(≢g)⊣{1<⍵:g⌿⍨←g/⍨←×⍵|+/g⋄(⊃g)-←g⍪⍨←g,⍨←⍵}¨2,⍵}
The graph is represented as a boolean adjacency matrix.
Rows/columns are added and removed as necessary.

Pyth, 88 80 75 characters
JYFHQI!H~Y]]lY)IqH1=Y+m+dlYY]UhlY)VYI&Hq%l@YNH1~J]N))=Ymf!}TJ@YkUlYY;-lYl{J

I'm done. Maybe someone else has some golfing tips.
Y is the adjacency list of the graph. For golfing reasons, I also keep a node in this list, even after the node got deleted (Otherwise I would have to update all indices). Each node has itself as neighbor. The list J keeps track of the deleted nodes.
I show the changes of the adjacency list on the example input [0,1,0,1,0,1,3]:

input 0: Y=[[0]]                                                         J=[]
input 1: Y=[[0,1],[0,1]] 0                                               J=[]
input 0: Y=[[0,1],[0,1],[2]]                                             J=[]
input 1: Y=[[0,1,3],[0,1,3],[2,3],[0,1,2,3]]                             J=[]
input 0: Y=[[0,1,3],[0,1,3],[2,3],[0,1,2,3],[4]]                         J=[]
input 1: Y=[[0,1,3,5],[0,1,3,5],[2,3,5],[0,1,2,3,5],[4,5],[0,1,2,3,4,5]] J=[]
input 3: Y=[[3,5],[3,5],[2,3,5],[2,3,5],[4,5],[2,3,4,5]]                 J=[0,1]

The algorithm then is pretty simple: Iterate over all inputs, if input==0: add a new node with itself as neighbour, if input==1: add a new node with all nodes as neighbors (also the deleted ones) and add this node to the adjacency list of all nodes, if input>1: determine the nodes with #neighbor-1%input==0 and add them to J, in each case, update the neighbors of each node using J. At the end print the length of Y minus the length of (the set of) J.
JYFHQI!H~Y]]lY)IqH1=Y+m+dlYY]UhlY)VYI&Hq%l@YNH1~J]N))=Ymf!}TJ@YkUlYY;-lYl{J
JY                      set J=[]
  FHQ                   for H in: input()
I!H      )                if H==0:
   ~Y]]lY                   Y.append([len(Y)])
IqH1              )       if H==1:
    =Y+                     Y=                 +
       m+dlYY                 old nodes updated
             ]UhlY                              new node with all neighbors
VY                )       for N in range(len(Q)):
  I&Hq%l@YNH1    )          if H>0 and len(Y[N])%H==1:
             ~J]N             J.append(N) //this node gets deleted
=Ym           Y           Y=[           for k in Y]
   f!}TJ@YkUlY               k-filtered  //all items of J are removed
;                       end input for loop
-lYl{J                  print len(Y) - len(set(J))

Usage
Just call the script and give as input [0,1,0,1,0,1,3] or some other test-case.

Python 2, 296
s=input();e=[];n=[];c=0
for t in s:
    if t<2:e=e+[[]]if t==0 else [x+[c]for x in e]+[n[:]];n+=[c];c+=1
    else:
        M=zip(*[(i,n[i])for i,x in enumerate(e)if not len(x)%t])
        if M:e=[list(set(z)-set(M[1]))for j,z in enumerate(e)if j not in M[0]];n=list(set(n)-set(M[1]))
print len(n)

Each node is given a unique id and the neighbor ids of each node are recorded. When the directive is 0, an empty neighbor list is added for the new node. When the directive is 1, the ids of all existing nodes become the neighbor list for the new node, and all other neighbor lists are updated to include the new node id. For m>1, nodes with neighbor lists that are a multiple of m are removed from the node list and all neighbor lists. Thanks to @Optimizer for catching a bug in an earlier version.

NetLogo, 160
to f[t]foreach t[if ? = 0[crt 1]if ? = 1[crt 1[create-links-with other turtles]]if ? > 1[ask turtles with[count my-links mod ? = 0][die]]]show count turtles
end

The implementation is straightforward, reading each symbol and doing the appropriate action.
to f[t]
  foreach t [
    if ? = 0 [
      crt 1
    ]
    if ? = 1 [
      crt 1 [create-links-with other turtles]
    ]
    if ? > 1 [
      ask turtles with [count my-links mod ? = 0] [die]
    ]
  ]
  show count turtles
end

You can run from the command line as f[0 0 1 1 0 0 1 1 2 5 7 0 1].

Ruby 159 157 (demo)
N=Struct.new:l
G=->c{n=[]
c.map{|m|m<1?n<<N.new([]):m<2?(w=N.new([])
n.map{|x|x.l<<w;w.l<<x}
n<<w):(n-=r=n.select{|x|x.l.size%m<1}
n.map{|x|x.l-=r})}
n.size}

This defines a function called G using stabby-lambda syntax. Use G[[0, 1]] to call it with commands 0 and 1.
The implementation is pretty straightforward: there is a Node structure (called N above) which holds references to all linked nodes via the l property. G creates nodes as needed and manipulates their links. A readable version is available here.

CJam, 99 97 bytes
Lal~{I2<{_0={{If+z}2*));0+a+}{;Iaa}?}{_0=!!{{{_:+I%+}%z}2*));1+a+{{W=},z}2*);z_{);}{a}?}*}?}fI0=,

There is still a lot to be golfed in this. The algorithm is based on keeping track of the adjacency matrix, but representing the empty matrix without having to treat it specially is giving me headaches.
Test it here.
Input is a CJam-style array:
[0 0 1 1 0 0 1 1 2 5 7 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 8]

You can use this test harness to run all tests:
"[]
[5]
[0,0,0,11]
[0,1,0,1,0,1,3]
[0,0,0,1,1,1]
[0,0,1,1,0,0,1,1,2,5,7,0,1]
[0,0,1,1,1,1,5,1,4,3,1,0,0,0,1,2]
[0,0,1,1,0,0,1,1,5,2,3,0,0,1,1,0,0,1,1,3,4,0,0,1,1,2,1,1]
[0,0,1,1,0,0,1,1,2,5,7,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,8]"

","SerN/{
La\~{I2<{_0={{If+z}2*));0+a+}{;Iaa}?}{_0=!!{{{_:+I%+}%z}2*));1+a+{{W=},z}2*);z_{);}{a}?}*}?}fI0=,
N}/

Python 2, 174
l=input()
g={}
n=0
for x in l:
 n+=1;g[n]=set()
 if x>1:h={i for i in g if len(g[i])%x};g={i:g[i]&h for i in set(g)&h}
 if x==1:
  for i in g:g[i]^={n};g[n]^={i}
print len(g)

This can probably still be golfed a lot.
I used a dictionary g to represent the graph. The nodes are labelled by numbers, and they map to the set of adjacent nodes. This means that each update of an edge needs to be executed at both of its endpoints.
Fresh node indices are created by counting up n. Each time, I create a new empty node n. For command 0, it just remains. For command 1, it's connected to each other node via g[i]^={n};g[n]^={i}; using xor make its so that the node isn't connected to itself. For commands >1, it's immediately deleted.
The filtering of nodes whose degree is a multiple is done by first finding nodes that the remain (h), then anding it with the list of nodes and the neighbors of each node.
Finally, the number of entries in the graph dictionary is the answer.

Mathematica, 223 bytes
Wow, this turned out longer than I expected.
f=(g={};t=Append;l=Length;m=ListQ;h=Flatten;k=Position;o=If;(d=#;o[d==0,g=g~t~{},o[d==1,g=o[m@#,t[#,l@g+1],#]&/@g;g=t[g,h@k[g,_?m,1]],g=o[l@#~Mod~d==0,0,#]&/@g;p=h@k[g,0];(c=#;g=#~DeleteCases~c&/@g)&/@p]])&/@#;g~Count~_?m)&

Usage:
f@{0, 1, 0, 1, 0, 1, 3}

Here are the results from the test cases:
f /@ {
  {},
  {5},
  {0, 0, 0, 11},
  {0, 1, 0, 1, 0, 1, 3},
  {0, 0, 0, 1, 1, 1},
  {0, 0, 1, 1, 0, 0, 1, 1, 2, 5, 7, 0, 1},
  {0, 0, 1, 1, 1, 1, 5, 1, 4, 3, 1, 0, 0, 0, 1, 2},
  {0, 0, 1, 1, 0, 0, 1, 1, 5, 2, 3, 0, 0, 1, 1, 0, 0, 1, 1, 3, 4, 0, 0, 1, 1, 2, 1, 1},
  {0, 0, 1, 1, 0, 0, 1, 1, 2, 5, 7, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 8}
}

Out: {0, 0, 0, 4, 6, 6, 6, 8, 14}

Less golfed:
f = (
   a = #;
   g = {};
   Table[
    If[a[[n]] == 0,
     AppendTo[g, {}],
     If[a[[n]] == 1,
      g = If[ListQ@#, Append[#, Length@g + 1], #] & /@ g;
      g = Append[g, Flatten@Position[g, _?ListQ, 1]],
      If[a[[n]] > 1,
       g = If[Mod[Length@#, a[[n]]] == 0, 0, #] & /@ g;
       p = Flatten@Position[g, 0];
       (c = #; g = DeleteCases[#, c] & /@ g) & /@ p
       ]
      ]
     ],
    {n, Length@a}];
   Count[g, _?ListQ]
   ) &

The way this works is by representing the graph as list of "lists of neighbors".
For the 0 directive, I just append an empty list.
For the 1 directive, I append a list of all the previous nodes, and add the new node to all the previous nodes.
For a directive >1, I removed the specified nodes and update the rest.

authors: главный инженер прамист


text:
Make any number by repeatedly adding 2 numbers
You are given a machine with two 16-bit registers, x and y. The registers are initialized x=1 and y=0. The only operation the machine can do is addition modulo 65536. That is:

x+=y - x is replaced by (x + y) mod 65536; y is unchanged
y+=x - similarly for y
x+=x - x is replaced by 2x mod 65536; legal only if x is even
y+=y - similarly for y

The goal is to get a predetermined number in one of the registers (either x or y).
Write a program or a subroutine that receives a number (in stdin, argv, function parameter, top of stack or any other conventional place), and outputs a program to get this number. The output should go to stdout, or (if your language has no stdout) to any other conventional output device.
The output program can be up to 100% plus 2 steps far from optimal. That is, if the shortest program to get the target number has n steps, your solution cannot be longer than 2n+2. This restriction is to avoid "too easy" solutions (e.g. counting 1, 2, 3, ...) but not require full optimization; I expect that the shortest program is easiest to find, but cannot be sure...
For example: Input = 25. Output:
y+=x
x+=y
x+=y
x+=x
x+=x
x+=x
y+=x

Another example: For any fibonacci number, the output has this alternating pattern. For Input = 21, output is
y+=x
x+=y
y+=x
x+=y
y+=x
x+=y
y+=x

Shortest code (measured in bytes) wins.
(this puzzle was inspired by some code for a 16-bit processor I had to generate recently)
P.S. I wonder - for which number the optimal program is longest?

Out of curiosity, why is x+=x legal only if x is even? Also for the shortest program I think something like BFS could work.

After arriving to the target, one might want to keep going to the next target number; to have the possiblity to get to any target, one of the numbers has to be odd. I didn't want to make an endless stream of targets to avoid unneeded complexity, but the spirit is to allow such a stream...

I have changed the restriction on number of steps, so for target number 0 or 1 the output program is not required to be empty.

if x+=x only works for even xs, how come the example for an input of 25 doubles 3?

CJam, 31
Like @Tobia's answer, my algorithm is also shamelessly stolen inspired by @CChak's answer. But, wielding the black magic that is CJam, I managed to make an even smaller implementation of the algorithm.
Try it here.
Golfed:
qi{_4%!:X)/X!-'xX+"
y+="@}h;]W%`

Ungolfed:
qi          "Read input and convert to integer.";
{           "Do...";
  _4%!:X    "Assign (value mod 4 == 0) to X.";
  )/X!-     "If X, divide value by 2. If not X, decrement value.";
  'xX+      "If X, put 'y' on the stack. If not X, put 'x' on the stack.";
  "
y+="        "Put '\ny+=' on the stack.";
  @         "Rotate top 3 elements of stack left so the value is on top.";
}h          "... while value is not zero.";
;           "Discard zero value on stack.";
]W%         "Collect stack into array and reverse.";

Please correct me if I'm wrong, but I believed that the modulo 65536 operation used in answers with a similar algorithm is unnecessary. I interpreted the question such that we can assume that the input will be a valid unsigned 16-bit integer, and any intermediate values or results of this algorithm will be as well.

An interesting point on the removal of mod 65536.  I think you make a good case that the "predetermined number" must be within 0-65535.

Perl 107 97
First post, so here goes.
sub h{($i)=@_;return if(($i%=65536)==0);($i%4==0)?do{h($i/2);say"y+=y";}:do{h($i-1);say"y+=x";}}

Which fits all of the register addition criteria, but I didn't run an exhaustive check to see if my answer was always within 2n+2 of the optimal number of steps.  It is well inside the limit for every Fibonacci number, though.
Here is a more detailed breakdown
sub h{                           # Declare the subroutine, it should be called referencing an integer value
   ($i)=@_;                      # Assign the i variable to the integer used in the call
   return if(($i%=65536)==0);    # Check for base condition of called by 0, and enforce modulo from the start.
   ($i%4==0) ?                   # If the value passed is even, and will result in an even number if we halve it
   do{h($i/2);say"y+=y";}        # Then do so and recurse
   :do{h($i-1);say"y+=x";}       # Otherwise "subtract one" and recurse
}                                # Note that the print statements get called in reverse order as we exit.

As I mentioned, this is my first attempt at golfing, so I'm sure this can be improved upon.  Also, I'm not sure if the initial subroutine call has to be counted in a recursive call or not, which could drive us up a few chars.
Interestingly we can reduce the code by 11 bytes* and improve our "efficiency" in terms of the number of register operations, by relaxing the requirement that only even values can be "doubled".  I've included that for fun here:
sub h{($i)=@_;return if(($i%=65536)==0);($i%2==0)?do{h($i/2);say"y+=y";}:do{h($i-1);say"y+=x";}}

Begin addendum:
Really liked this problem, and I've been fiddling with it off and on for the last couple weeks.  Thought I would post my results.
Some numbers:
Using a BFS algorithm to find an optimal solution, in the first 2^16 numbers there are only 18 numbers that require 23 steps.  They are: 58558, 59894, 60110, 61182, 61278, 62295, 62430, 62910, 63422, 63462, 63979, 64230, 64314, 4486, 64510, 64698, 64854, 65295.
Using the recursive algorithm described above, The "most difficult" number to reach is 65535, at 45 operations.  ( 65534 takes 44, and there are 14 numbers that take 43 steps)  65535 is also the largest departure from optimal, 45 vs 22.  The 23 step difference is 2n+1.  (Only three numbers hit 2n: 65534, 32767, 32751.)  Excepting the trivial (zero-step) cases, over the defined range, the recursive method averages approximately 1.4 times the optimal solution.
Bottom line: For the numbers 1-2^16, the recursive algorithm never crosses the defined threshold of 2n+2, so the answer is valid.  I suspect that it would begin to depart too far from the optimal solution for larger registers/more bits, however.
The code I used to create the BFS was sloppy, memory intensive, not commented, and quite deliberately not included.  So... you don't have to trust my results, but I'm pretty confident in them.

A non-BFS solution, great!

I think for even the most pathological cases you'll stay within a factor of 4, maybe better (since I only know of a lower bound for the optimal solution). Which is still pretty good.

Python 3, 202 bytes
def S(n):
 q=[(1,0,"")];k=65536
 while q:
  x,y,z=q.pop(0)
  if n in{x,y}:print(z);return
  q+=[((x+y)%k,y,z+"x+=y\n"),(x,(x+y)%k,z+"y+=x\n")]+[(2*x%k,y,z+"x+=x\n")]*(~x&1)+[(x,2*y%k,z+"y+=y\n")]*(~y&1)

(Thanks to @rationalis for a few bytes)
Here's an extremely basic solution. I wish I could golf the last line better, but I'm currently out of ideas. Call with S(25).
The program just does a simple BFS with no caching, so is very slow. Here is S(97), for some sample output:
y+=x
x+=y
x+=x
x+=x
x+=x
x+=x
y+=x
y+=x
x+=y

Dyalog APL, 49 chars / bytes*
{0=N←⍵|⍨2*16:⍬⋄0=4|N:⎕←'y+=y'⊣∇N÷2⋄⎕←'y+=x'⊣∇N-1}

Algorithm shamelessly inspired by @CChak's answer.
Example:
    {0=N←⍵|⍨2*16:⍬⋄0=4|N:⎕←'y+=y'⊣∇N÷2⋄⎕←'y+=x'⊣∇N-1} 25
y+=x
y+=x
y+=y
y+=x
y+=x
y+=y
y+=y
y+=x

Ungolfed:
{
    N←(2*16)|⍵                 # assign the argument modulo 65536 to N
    0=N: ⍬                     # if N = 0, return an empty value (that's a Zilde, not a 0)
    0=4|N: ⎕←'y+=y' ⊣ ∇N÷2     # if N mod 4 = 0, recurse with N÷2 and *then* print 'y+=y'
    ⎕←'y+=x' ⊣ ∇N-1            # otherwise, recurse with N-1 and *then* print 'y+=x'
}

* Dyalog APL supports a legacy charset which has the APL symbols mapped to the upper 128 byte values. Therefore an APL program that only uses ASCII characters and APL symbols can be considered to be bytes == chars.

Python, 183
def S(n):
 b,c,e=16,'x+=x\n','x+=y\n';s=d='y+=x\n';a=i=0
 if n<2:return
 while~n&1:n>>=1;a+=1
 while n:n>>=1;s+=[e,c][i]+d*(n&1);i=1;b-=1
 while a:s+=[c,c*b+e*2][i];i=0;a-=1
 print(s)

I can't guarantee this stays within 2x the optimal program for even numbers, but it is efficient. For all valid inputs 0 <= n < 65536, it's essentially instantaneous, and generates a program of at most 33 instructions. For an arbitrary register size n (after fixing that constant), it would take O(n) time with at most 2n+1 instructions.
Some Binary Logic
Any odd number n can be reached within 31 steps: do y+=x, getting x,y = 1,1, and then keep doubling x with x+=x (for the first doubling do x+=y, since x is odd to begin with). x will reach every power of 2 this way (it's just a left-shift), and so you can set any bit of y to be 1 by adding the corresponding power of 2. Since we're using 16-bit registers, and each bit except for the first takes one doubling to reach and one y+=x to set, we get a maximum of 31 ops.
Any even number n is just some power of 2, call it a, times an odd number, call it m; i.e. n = 2^a * m, or equivalently, n = m << a. Use the above process to get m, then reset x by left-shifting it until it's 0. Do a x+=y to set x = m, and then continue to double x, the first time using x+=y and subsequently using x+=x.
Whatever a is, it takes 16-a shifts of x to get y=m and an additional a shifts to reset x=0. Another a shifts of x will occur after x=m. So a total of 16+a shifts is used. There are up to 16-a bits that need to be set to get m, and each of those will take one y+=x. Finally we need an extra step when x=0 to set it to m, x+=y. So it takes at most 33 steps to get any even number.
You can, of course, generalize this to any size register, in which case it always takes at most 2n-1 and 2n+1 ops for odd and even n-bit integers, respectively.
Optimality
This algorithm produces a program that is near-optimal (i.e. within 2n+2 if n is the minimum number of steps) for odd numbers. For a given odd number n, if the mth bit is the leading 1, then any program takes at least m steps to get to x=n or y=n, since the operation which increases the registers' values fastest is x+=x or y+=y (i.e. doublings) and it takes m doublings to get to the mth bit from 1. Since this algorithm takes at most 2m steps (at most two per doubling, one for the shift and one y+=x), any odd number is represented near-optimally.
Even numbers are not quite so good, since it always uses 16 ops to reset x before anything else, and 8, for example, can be reached within 5 steps.
Interestingly, the above algorithm never uses y+=y at all, since y is always kept odd. In which case, it may actually find the shortest program for the restricted set of only 3 operations.
Testing
# Do an exhaustive breadth-first search to find the shortest program for
# each valid input
def bfs():
    d = {(0,1):0}
    k = 0xFFFF
    s = set(range(k+1))
    current = [(0,1)]
    nexts = []
    def add(pt, dist, n):
        if pt in d: return
        d[pt] = dist
        s.difference_update(pt)
        n.append(pt)
    i = 0
    while len(s) > 0:
        i += 1
        for p in current:
            x,y = p
            add((x,x+y&k), i, nexts)
            add((y,x+y&k), i, nexts)
            if y%2 == 0: add(tuple(sorted((x,y+y&k))), i, nexts)
            if x%2 == 0: add(tuple(sorted((x+x&k,y))), i, nexts)
        current = nexts
        nexts = []
        print(len(d),len(s))

# Mine (@rationalis)
def S(n):
    b,c,e=16,'x+=x\n','x+=y\n';s=d='y+=x\n';a=i=0
    if n<2:return ''
    while~n&1:n>>=1;a+=1
    while n:n>>=1;s+=[e,c][i]+d*(n&1);i=1;b-=1
    while a:s+=[c,c*b+e*2][i];i=0;a-=1
    return s

# @CChak's approach
def U(i):
    if i<1:return ''
    return U(i//2)+'y+=y\n' if i%4==0 else U(i-1)+'y+=x\n'

# Use mine on odd numbers and @CChak's on even numbers
def V(i):
    return S(i) if i % 2 == 1 else U(i)

# Simulate a program in the hypothetical machine language
def T(s):
    x,y = 1,0
    for l in s.split():
        if l == 'x+=x':
            if x % 2 == 1: return 1,0
            x += x
        elif l == 'y+=y':
            if y % 2 == 1: return 1,0
            y += y
        elif l == 'x+=y': x += y
        elif l == 'y+=x': y += x
        x %= 1<<16
        y %= 1<<16
    return x,y

# Test a solution on all values 0 to 65535 inclusive
# Max op limit only for my own solution
def test(f):
    max_ops = 33 if f==S else 1000
    for i in range(1<<16):
        s = f(i); t = T(s)
        if i not in t or len(s)//5 > max_ops:
            print(s,i,t)
            break

# Compare two solutions
def test2(f,g):
    lf = [len(f(i)) for i in range(2,1<<16)]
    lg = [len(g(i)) for i in range(2,1<<16)]
    l = [lf[i]/lg[i] for i in range(len(lf))]
    print(sum(l)/len(l))
    print(sum(lf)/sum(lg))

# Test by default if script is executed
def main():
    test()

if __name__ == '__main__':
    main()

I wrote a simple test to check that my solution indeed produces correct results, and never goes over 33 steps, for all valid inputs (0 <= n < 65536).
In addition, I attempted to do an empirical analysis to compare my solution's output against the optimal outputs -- however, it turns out that breadth-first search is too inefficient to obtain the minimum output length for every valid input n. For example, using BFS to find the output for n = 65535 does not terminate in a reasonable amount of time. Nonetheless I've left in bfs() and am open to suggestions.
I did, however, test my own solution against @CChak's (implemented in Python here as U). I expected mine would do worse, since it is drastically inefficient for smaller even numbers, but averaged across the whole range in two ways, mine produced output of length on average 10.8% to 12.3% shorter. I thought maybe this was due to better efficiency from my own solution on odd numbers, so V uses mine on odd numbers and @CChak's on even numbers, but V is in between (about 10% shorter than U, 3% longer than S).

Quite a lot of logic in 201 bytes!

@analtolyg What can I say, I like math and bit fiddling. I may investigate other approaches, since the even number solution has room for improvement.

Whoa, I didn't even realize x,y='xy' was possible until now. Unfortunately, I can't think of a way to rewrite c*b+e*2 concisely with % formatting.

Ah I didn't realise you used it somewhere else. Is it just me or is S(2)'s output really long?

Unfortunately, with my solution, every even number takes at least 19 steps (S(2) being the shortest one at 19). I don't keep track of x and y explicitly, so even though x reaches 2 after the second step, it nonetheless continues on to reset x to 0. I feel as though there must be a better solution, but as of yet I can't think of one.


text:
Recover the mutated source code
In a very unusual accident involving a small sample of radium, an electrocuted whale, and three gummy bears, some of The Management™'s source code has been mutated. Little does The Management™'s boss know, it was actually the Cops© who had been responsible, in an attempt to thwart The Management™'s "evil" plans. So the Robbers® have been hired in an attempt to retrieve the original code, because who doesn't like being evil sometimes?
note: This challenge was heavily inspired by Unscramble the Source Code.
Description
This is a cops-and-robbers challenge.

The cops will write a program (the mutated code) that performs Task #1 (and also write a program that performs Task #2, but is kept secret).
The robbers will attempt to reverse the "mutation" and change this original code into code that performs Task #2.

In this challenge, Task #1 will be to output the nth prime number, and Task #2 will be to output the nth Fibonacci number (which is somehow evil, according to the Cops© anyway). The Fibonacci sequence is defined as (n=1 → 1; n=2 → 1; n=3 → 2; ...), and the prime numbers are defined as (n=1 → 2; n=2 → 3; n=3 → 5; ...).
The cops' goal is to minimize the difference between the programs that complete Task #1 and Task #2, while preventing the robbers from recreating the code that completes Task #2.
Cop Rules
The cops will write two programs (one that completes Task #1, and one that completes Task #2), and make the following information public:

The first program (that outputs the nth prime number)
The Levenshtein edit distance between the first program and the second program
The programming language that both programs are written in (must be the same language for both programs)

The following restrictions apply to both programs:

They must be 128 characters in length or less.
They must only use printable ASCII (plus newlines, which are also allowed).
They must take less than 10 seconds to run for n=45, and they are not required to produce the correct output for any n>45.
They must not use any hashing or cryptographic functions.

Robber Rules
The robber will attempt to change the cop's program (which completes Task #1) into a program that completes Task #2 (not necessarily the original program written by the cop) in the edit distance specified by the cop.
An already-cracked submission cannot be cracked again (only the first robber who cracks a submission gets credit).
After cracking a submission, please do the following:

Post an answer to this challenge's accompanying question (link), providing the language, your solution, and a link to the original answer.
Leave a comment with the text "Cracked" that links to your posted answer.
Edit the cop's answer if you have edit privileges (if you do not, either wait until someone else with the required privileges does so for you or suggest an edit).

Scoring
If a cop's program remains uncracked for 1 week, the cop can post the original code that completes Task #2 (in the specified edit distance), and the submission is from then on considered "safe." The safe submission that has the smallest edit distance will win. In the event of a tie, the shortest program (the original that completes Task #1) wins. If two submissions are still tied, the one posted earlier wins.
If a robber successfully cracks a cop's submission, the robber's score goes up by the edit distance of that submission. For example, a robber that cracks a submission with an edit distance of 3 and one with a distance of 5 earns 8 points. The robber with the highest score wins. In the event of a tie, the robber who earned the score first wins.
Leaderboard

Ruby, 6 (histocrat)

A small tool to compute the Levenshtein distance

var f=document.getElementById("f"),g=document.getElementById("s"); function h(){var a=f.value,e=g.value;if(128<a.length)a="First program is too long!";else if(128<e.length)a="Second program is too long!";else{if(0===a.length)a=e.length;else if(0===e.length)a=a.length;else{var d=[],b;for(b=0;b<=e.length;b++)d[b]=[b];var c;for(c=0;c<=a.length;c++)d[0][c]=c;for(b=1;b<=e.length;b++)for(c=1;c<=a.length;c++)d[b][c]=e.charAt(b-1)===a.charAt(c-1)?d[b-1][c-1]:Math.min(d[b-1][c-1]+1,Math.min(d[b][c-1]+1,d[b-1][c]+ 1));a=d[e.length][a.length]}a="Distance = "+a+""}document.getElementById("d").innerHTML=a}f.onkeyup=h;g.onkeyup=h;

First program

<textarea id=f rows=7 cols=80 style="width:100%"></textarea>

Second program

<textarea id=s rows=7 cols=80 style="width:100%"></textarea>

What is the 1st Fibonacci number? 0 or 1? Or does it not matter

@kukac67 It's 1; I've edited the post.

What should the output of the programs be, in the case of overflow?

Must it be a full program or can it be a function? What about an anonymous function?

@es1024 Since n is limited to 45 or below, and the 45th Fibonacci number fits in an signed int, there shouldn't be an overflow.

@Tyilo It has to be a full program that prints the result to STDOUT.

@Doorknob冰 The J answer by FryAmTheEggman seems to be just a function definition, not a full program.

What counts as a "hashing or cryptographic function"? Can I base-convert stuff? Can I take large exponentials modulo large primes?

So not an arbitraty task, only primes and fibonacci?

There are no submissions yet? The leaderboard section should be updated.

When doing PHP, are the open tags required?

Python 2, distance = 8 [cracked]
from fractions import*
n=input()
k,=P=[2]
while n>len(P):k+=1;z=reduce(lambda x,y:x*y,P,1);P+=[k]*(gcd(z,k)<2)
print P[-1]

Finally got this one under the char limit. Shouldn't be too hard, but I thought the idea was interesting.

Intended solution:

 from fractions import*
 n=input()
 k,=P=[1]
 while n>len(P):k+=1;z=reduce(lambda x,y:x+y,P[:-1],1);P+=[z]*(gcd(z,k)<2)
 print P[-1]

The idea was to use that F(n+2) = 1 + (sum over F(k) from k = 1 to n), and the fact that consecutive Fibonacci numbers are coprime. The 1 in the reduce argument was supposed to provide the +1.
Looks like feersum found a different line of attack!

Cracked

J, distance = 5 [Cracked]
f=:3 :'{.p:|.i.y'

Usage:
> f 45
197

Cracked

Ruby, distance 6 [safe]
require'prime';p Prime.take(n=gets.to_i)[-1]
#p (((807462154311276410)**n/(5**0.5)).round)

Coming up with pairs of formulas with short edit distances is fun, but it seems like this approach might be more effective/annoying. You may understand exactly what I did, but that doesn't mean you can reverse it.
Solution:

require'prime';p=Prime.take(n=gets.to_i)[-1]
 p (((0742154311276/4e10)**n/(5**0.5)).round)

Explanation:

 The code generates the Golden Ratio to 11 decimal places and uses it to directly calculate the Fibbonaci sequence. It's just enough precision to get the required number of terms right. That part wasn't obfuscated at all, if you happen to know the formula. To make it harder to brute-force reverse my mutations and recover the constant, I used octal notation (the leading 0) and scientific notation (4e10). Dividing by 4e10 rather than 1e11 makes it look more like I'm dividing by something .0 to force float division, when actually anything in scientific notation is for some reason always a Float in Ruby, even when a Bignum might seem to make more sense. I thought I was being clever with the p= stuff, but the way I wrote it you can just delete the p. I could've reduced the distance by 1 and forced the p= solution by using p&& instead of # on the second line, but I didn't think of it.

Didn't think of trying inserting an e down there when doing brute force. Really sneaky solution. :)

Python 2 - LD = 13 Cracked
n=1;j=input();
while j>0:
    n+=1;j-=1;
    while~-all(n%i for i in range(2,n)):n+=1;
print n

A nice, easy (hopefully not too easy) one to start things off :)
Looks like it was too easy ;) I feel rather silly that I forgot you could use comments :/

Cracked.

Haskell, distance = 13
import Data.List
x=id=<<snd(mapAccumL(\m n->(,)=<<(++m)$[n|and[n`mod`m1/=0|m1<-m]])[1+1][3..])
main=print.(!!)(0:2:x)=<<readLn

This could be more readable, but the import ate too many bytes, so I had to golf it a bit.

Ruby, distance 14 (Cracked)
p [x=2,y=1,*(1..200).map{|i|y==(y*x**(i-1)+x%2).divmod(i)[x-1]?i:1}].-([x-1])[gets.to_i-1]

Cracked?

Hm, your Fibbonaci sequence starts with 0, where the rules say to start with 1. Otherwise checks out (although very different from my intended solution).

Ok, fixed. Nice use of Fermat's btw.

CJam, distance 10 (Cracked)
1l~{{)_mp!}g}*

Just put n on STDIN. Test it here.
For reference, the original solution used the rare j.
Original:

 T1]l~\{(_j\(j+}j

Cracked

J, distance = 4 [safe]
f =: 3 :  '{. (p:) (+) / 0 , y - 1x'

Solution:

f =: 3 :  '{. 2(x:) (+%) / 0 , y $ 1x'

Method:

Denominator {. 2(x:) of the continued fraction (+%) 1+1/(...(1+1/(1+1/(1+1/(1))))).

Python 3, distance = 14 [cracked]
n = int(input())
P = [2]
k = 2
while n > len(P):
 k += 1
 for x in P:
  if k%x == 0: break
 else: P += [k]
print(k)

I had some spare chars so I put some whitespace in for clarity :)

Cracked

JAGL Alpha 1.2 - Distance = 16 [Cracked]
T~2S]{]S1{D[dmn}wDS}wSP

Shouldn't be too hard, We will see what happens...

Cracked?

TI-BASIC, distance 38
Input N:{2>L1:For(A,3,E99:If min(1=gcd(A,seq(A,A,2,$(A:A>L1(1+dim(L1:End:L1(N

> represents the STO→ key and $ represents the square root symbol.

Some of these characters don't seem to be printable ASCII.

@feersum Thanks, corrected. Distance is still 38.

Python 2 – distance = 12 [Cracked]
I'm kinda happy with how this turned out.
f=lambda p,i:p if p[45:]else f(p+[i]if all(i%q for q in p[1:])else p,-~i)
print f([1,2,3],2)[input()]

Let's see how long it takes... I assume it'll still be cracked.
Edit: shortened code a tiny bit, no effect on operation/distance.
Intended solution
I tried to go for no comments or newline changes.

 f=lambda p,i:p if p[45:]else f(p+[p[i]+p[-2]]if all(i|q for q in p[1:])else p,-~i)
 print f([1,1,1],2)[input()]

Cracked

Python 3 - Distance = 14 [Cracked]

a,c,n=1,2,int(input())
while n-1:
 c+=1
 while 1!=list(map(c.__mod__,range(2,46))).count(0):
  c,a=a+c,a
 n-=1
print(c)

We'll see how long this lasts...

Cracked


text:
Recover the mutated source code (for robbers)
This is the companion thread to the main Recover the mutated source code (link) challenge. If you have successfully cracked a cop's answer, post your solution as an answer to this question.
As a reminder, here are the robber rules from the main challenge again:

The robber will attempt to change the cop's program (which completes
  Task #1) into a program that completes Task #2 (not necessarily the
  original program written by the cop) in the edit distance specified by
  the cop.
An already-cracked submission cannot be cracked again (only the first
  robber who cracks a submission gets credit).
After cracking a submission, please do the following:

Post an answer to this challenge's accompanying question (link), providing the language, your solution, and a link to the original answer.
Leave a comment with the text "Cracked" that links to your posted answer.
Edit the cop's answer if you have edit privileges (if you do not, either wait until someone else with the required privileges does
  so for you or suggest an edit).

And scoring:

If a robber successfully cracks a cop's submission, the robber's score goes up by the edit distance of that submission. For example, a robber that cracks a submission with an edit distance of 3 and one with a distance of 5 earns 8 points. The robber with the highest score wins. In the event of a tie, the robber who earned the score first wins.

Leaderboard
There are no cracked submissions yet.

Who is maintaining the leaderboard? And also, I think reader's score should go up more if the distance is less, since that would seem harder to me.

Python 2, FryAmTheEggman
x=n=1;j=input();
while j>2:
    x,n=n,x+n;j-=1;
    ##while~-all(n%i for i in range(2,n)):n+=1;
print n

Used 12 edits. Put in an extra # to make it 13.

You need to use all 13 edits, but that can easily be fixed by adding another character in the comment.

Dammit, I forgot comments were a thing :/ Originally I changed the range to start at 1 and removed the ~ ;P

@FryAmTheEggman If you want no comments, you can change the range to be from n to n, so that the all evaluates to True. But ~-True is False, so the while won't run.

I didn't "want" no comments, it just made this much easier than I thought it would be. Besides that, that is a much neater idea than what I came up with ;)

Python 2, Sp3000
from fractions import*
n=input()
k,=P=[1]
while n>len(P):k+=1;z=reduce(lambda x,y:x+y,P[~1:]);P+=[z]#*(gcd(z,k)<2)
print P[-1]

On closer inspection, this is slightly different to the approach I originally had. Interesting...

J, grc
   f=:3 :'{.+/(!|.)i.y'

   f 45
1134903170

Python 3, Sp3000
x=n= int(input())       # 3
P = [1,1]               #+2 = 5
k = 2
while n >=len(P):       #+1 = 6
 k += 1
 for x in P:
  if k%x ==~0: break    #+1 = 7
 else: P += [P[-2]+x]   #+7 = 14
print(x)

Python 3, matsjoyce
a,c,n=1,1,int(input())
while n-1:
 #c+=1
 ##########list(map(c.__mod__,range(2,46))).count(0):
 a,c=a+c,a
 n-=1
print(c)

The Fibonacci program was strangely already in there...only needed 5 edits to get it.

Yeah, I designed it from the wrong end (and posted it, until Sp3000 spotted it), so it looks a little weird.

JAGL, globby
T~2]d]2C{cSdc+c]}wSP

It might not be the most efficient approach, it it is almost definitely not the Cop's code, but it works, and its 12 away.

CJam by Martin Büttner
T1l~({_2$+}*p];

Takes input n from STDIN

Python 2, Pietu1998
f=lambda p,i:p if p[45:]else f(p+[i]#f all(i%q for q in p[1:])else
,p[-1]+i)
print f([1,1,1],2)[input('!')]

I used 9 edits to get a Fibonacci program.

@MartinBüttner I do have 12. See the pointless argument to input.

Well... I believe this would output the !. Still accepting this as valid, you could put any chars in the comment,

@Pietu1998 What's wrong with having a prompt on user input?

Nothing, but this is operationally different.

Ruby, histocrat
p [x=1,y=1,*(1..200).map{|i|z=y;y+=(y*x**(i-1)+x%2).divmod(i)[2-1]?x:1;x=z;y}].-([x-1])[gets.to_i-1]