text:
MarGolf Meets Langton's Anthill
This is Markov.
Markov's golf ball rolls around randomly.
Markov's ball will hole however he strikes it.
Markov is smart.
Be like Markov.

And this:

is an anthill in Langton's backyard.
The anthill is big enough to hold Markov's golfball, MarGolf. However, the anthill moves and changes direction depending on the surrounding terrain.
The Task
Take an input of a 10x20 field:

* MarGolf
O Lanton's Anthill
, Anthill turns 90 degrees clockwise
. Anthill turns 90 degrees counterclockwise
0 MarGolf in Langton's Anthill

A field looks like this:
,...,.,,..,...,.,,..
..,.,,,..,...,..,.,.
.,,*.,....,.,,,.,,,.
,.,,.,...,,.,.,,,,,.
.,..,....,,.....,,.,
,.,.,...,..,.,,,,..,
....,,,,,,,,,.......
........,,.,...,...,
,,,,,,,,,,,,....,O.,
,.,.,.,.....,,.,,,,,

Game rules:
The configuration of the input field is called tick 0. Your program needs to evaluate and print out the configuration of the next tick, in which both MarGolf and Langton's Anthill will move to another cell. The the item in the current cell will become the item currently in the target cell. If both MarGolf and the anthill move to the same cell in the next tick, the game ends.
Movement rules:

MarGolf moves randomly. All nine cells in the 3x3 area around MarGolf has equal chance of being selected. This becomes a choice among 6 cells at an edge of the field, and 4 cells at a corner.
Langton's Anthill needs to remember its movement direction of either up, down, left, or right (NSEW or whatever equivalent). It moves one cell in its direction each tick, and the original content of the cell changes its direction clockwise or anti-clockwise, as specified above. Initial direction at tick 0 is random, each direction has an equal chance of being the initial.

Notes

The program needs to print the configuration of each tick, until the game ends.
The tick number precedes the field configuration of each tick.
You may assume the input is always valid.
The shortest program is bytes wins.

Update: forgot to mention anthill reverses direction before moving if it would otherwise go off the field. Credit to user81655 for reminding.

Could anyone point where the "be like  meme originated?

@proudhaskeller I guess from the Be Like Bill facebook page, there's an article on Wikipedia you might want to read. https://en.wikipedia.org/wiki/Be_like_Bill

@proudhaskeller http://knowyourmeme.com/memes/be-like-bill-se-como-jose

How do we know whether the tile "under" the * and the O is a , or a .?

@Doorknob If I understand the challenge correctly, there is no tile under them. When you move one of them it swaps with the tile they move onto, and that tile determines the Os direction for the next step.

@MartinButtner yes that is mostly correct. I avoided the term "swap" for one corner case, but the term is otherwise truthy.

Shouldn't the sentence "All nine cells in the 3x3 area around MarGolf has equal chance of being selected. This becomes a choice among 6 cells at an edge of the field, and 4 cells at a corner." be "All eight cells in the 3x3 area around MarGolf has equal chance of being selected. This becomes a choice among 4 cells at an edge of the field, and 4 cells at a corner." instead? Or is it possible for MarGolf to stay at its current position?

"If both MarGolf and the anthill move to the same cell in the next tick, the game ends." So the final tick is the tick before MarGolf ends up in the anthill? If so, why is "0 MarGolf in Langton's Anthill" specified? And if we indeed need to print the final tick as well with 0 being MarGolf in Langton's Anthill, what character need to be placed at the swap (since we swap ./, with *, and then * with O (transforming O into 0), but which character does the * become?

Java 10, 611 609 607 593 591 bytes
m->{int x=0,y=0,X=0,Y=0,r=10,c,d=4,e;for(d*=Math.random();r-->0;)for(c=20;c-->0;){if(m[r][c]<43){x=r;y=c;}if(m[r][c]>48){X=r;Y=c;}}for(;;d=m[r][c]<45?d<2?d+2:d<3?1:0:d>1?d-2:d>0?2:3){p(m);for(e=4;e==4;e*=Math.random())e=9;m[r=x][c=y]=m[x+=e/3<1?x>0?-1:1:e/3>1?x<9?1:-1:0][y+=e%3<1?y>0?-1:1:e%3>1?y<19?1:-1:0];if(m[x][y]>48){m[x][y]=48;m[r][c]=0;p(m);e/=0;}m[x][y]=42;m[r=X][c=Y]=m[X+=d<1?X<9?1:-1:d==1?X>0?-1:1:0][Y+=d==2?Y<19?1:-1:d>2?Y>0?-1:1:0];if(m[X][Y]<43){m[r][c]=48;m[X][Y]=0;p(m);e/=0;}m[X][Y]=79;}}void p(char[][]m){var p="";for(var a:m)p+=p.valueOf(a)+"\n";System.out.println(p);}

-4 bytes thanks to @ceilingcat.
Assumes the final swap of * and O will empty the cell where * is coming from.
Explanation:
Try it online.
m->{                        // Method with character-matrix parameter and no return-type
  int x=0,y=0,              //  [x,y] coordinates of MarGolf
      X=0,Y=0,              //  [X,Y] coordinates of Langton's Anthill
      r=10,c,               //  Temp [x,y] coordinates
      d=4,                  //  Direction Langton's Anthill
      e;                    //  Direction MarGolf
  for(d*=Math.random();     //  Set the direction Langton's Anthill randomly [0,3]
      r-->0;)               //  Loop over the rows:
    for(c=20;c-->0;){       //   Inner loop over the columns:
      if(m[r][c]<43){       //    If '*' is found:
        x=r;y=c;}           //     Set MarGolf's [x,y] coordinates
      if(m[r][c]>48){       //    If 'O' is found:
        X=r;Y=c;}}          //     Set Langton's Anthill's [X,Y] coordinates
  for(;                     //  Loop indefinitely:
       ;                    //    After every iteration:
        d=                  //     Change the direction of Langton's Anthill:
          m[r][c]<45?       //      If the swapped cell contained a comma:
           d<2?d+2:d<3?1:0  //       Change the direction clockwise
          :                 //      Else (the swapped cell contained a dot):
           d>1?d-2:d>0?2:3){//       Change the direction counterclockwise
  p(m);                     //  Pretty-print the matrix
  for(e=4;e==4;e*=Math.random())e=9;
                            //  Change direction MarGolf randomly [0-9] (excluding 4)
  m[r=x][c=y]               //  Save the current MarGolf coordinates
   =m[x+=e/3<1?x>0?-1:1:e/3>1?x<9?1:-1:0]
     [y+=e%3<1?y>0?-1:1:e%3>1?y<19?1:-1:0];
                            //  And change that cell to the content in direction `e`
                            //  0 to 9 (excl. 4) is NW,N,NE,W,n/a,E,SW,S,SE respectively
                            //  If `e` would go out of bounds, it moves opposite instead
  if(m[x][y]>48){           //  If MarGolf reached Langton's Anthill:
    m[x][y]=48;             //   Set that cell to '0'
    m[r][c]=0;              //   And empty the swapped cell
    p(m);                   //   Print the final status of the matrix
    e/=0;}                  //   And stop the loop with an error to exit the program
  m[x][y]=42;               //  Change the cell in the new coordinate to '*'
  m[r=X][c=Y]               //  Save the current Langton's Anthill coordinates
   =m[X+=d<1?X<9?1:-1:d==1?X>0?-1:1:0]
      [Y+=d==2?Y<19?1:-1:d>2?Y>0?-1:1:0];
                            //  And change that cell to the content in direction `d`
                            //  0 to 3 is E,W,S,N respectively
                            //  If `d` would be out of bounds, it moves opposite instead
  if(m[X][Y]<43){           //  If MarGolf reached Langton's Anthill:
    m[r][c]=48;             //   Set that cell to '0'
    m[X][Y]=0;              //   And empty the swapped cell
    p(m);                   //   Print the final status of the matrix
    e/=0;}                  //   And stop the loop with an error to exit the method
  m[X][Y]=79;}}             //  Change the cell in the new coordinate to 'O'

void p(char[][]m){          // Separated method to print the given matrix
  var p="";                 //  String to print, starting empty
  for(var a:m){             //  Loop over the rows:
    p+=p.valueOf(a)         //   Convert the character-array to a String line and append,
                     +"\n"; //   including a trailing newline
  System.out.println(p);}   //  Print the String with trailing newline as separator


text:
Bouncing in an array
Introduction
Arrays can also be seen as a field for a bouncing ball. This of course sounds very vague, so here is an example of an input:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

The challenge is to output the bounced arrays. These are made from diagonal patterns which bounce at the edges of the field. This path is pointed upwards. The path for the first bounced array (in which the path is directly bounced off the egde), is:
[1, -, -, -, 5, -, -, -, 9]
[-, 8, -, 6, -, 4, -, 2, -]
[-, -, 3, -, -, -, 7, -, -]

From left to right, this would result in [1, 8, 3, 6, 5, 4, 7, 2, 9]. This is our first bounced array. The path for the second bounced array:
[-, 2, -, -, -, 6, -, -, -]
[9, -, 7, -, 5, -, 3, -, 1]
[-, -, -, 4, -, -, -, 8, -]

This results in [9, 2, 7, 4, 5, 6, 3, 8, 1]. The path for the third bounced array is:
[-, -, 3, -, -, -, 7, -, -]
[-, 8, -, 6, -, 4, -, 2, -]
[1, -, -, -, 5, -, -, -, 9]

This results in [1, 8, 3, 6, 5, 4, 7, 2, 9]. So the three bounced arrays are:
[1, 8, 3, 6, 5, 4, 7, 2, 9]
[9, 2, 7, 4, 5, 6, 3, 8, 1]
[1, 8, 3, 6, 5, 4, 7, 2, 9]

Task
Given at least 1 array containing only non-negative integers, with all the arrays having the same length, output all the bounced arrays.
Test cases
Test case 1:
Input:                       Output:
[1, 2, 3, 4, 5]              [1, 7, 3, 9, 5]
[6, 7, 8, 9, 0]              [6, 2, 8, 4, 0]

Input:                       Output:
[1, 2, 3, 4, 5]              [1, 2, 3, 4, 5]

Input:                       Output:
[0, 0, 0, 0, 0, 0, 0, 0]     [0, 9, 0, 9, 0, 9, 0, 100]
[9, 9, 9, 9, 9, 9, 9, 100]   [9, 0, 9, 0, 9, 0, 9, 0]
[0, 0, 0, 0, 0, 0, 0, 0]     [0, 9, 0, 9, 0, 9, 0, 100]

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

Input:                       Output:
[0, 0, 0, 0, 0, 0]           [0, 2, 2, 6, 2, 6]
[1, 2, 3, 4, 5, 6]           [1, 0, 3, 2, 5, 2]
[2, 2, 2, 2, 2, 2]           [2, 2, 0, 4, 2, 4]
[9, 8, 7, 6, 5, 4]           [9, 2, 3, 0, 5, 2]

This is code-golf, so the submission with the least amount of bytes wins!

Jelly wins this.

Can you please add a three-array testcase where the last array is different then the first, and a four-array testcase?

I can't find the problem description. Can anyone tell me where it is?

Yes. I can't find a description of the task.

I don't have any idea what a "bounced array" is.

It took me a few reads, but it's actually there. The bounced arrays are things you read from the input in the three examples that have the _ in them. Basically, for each cell on the left there's a bounced array that you get by starting to reading along the north-east diagonal and reflecting off the top and bottom. (This could definitely be clearer though.)

What do you mean "the path is pointed upwards"? Where does the path start from? If it's from left, why some paths go up and other go down? The challenge sounds interesting but please explain

Got it. Thanks @Martin and thanks to the examples

@LuisMendo let's check if I really got it. The path goes left to right and starts going up, except when the start is at line 0. In that case the path immediately "bounce" down

@edc65 Maye so... but "except when the start is at line 0" is a weird rule, isn't it?

@LuisMendo it's the only way to bounce, at line 0 it can't go up more

@edc65 Got it. You could think it always goes up, but at line 0 it has to immediately bounce down. Thanks!

Consider adding "zig-zag" or something similar, maybe a few (animated?) images of the ball following its path; I had to read the entire post to figure out what you meant.

Pyth, 17 bytes
>lQC.e.>bkC+_PtQQ

Explanation:
                      implicit: Q=input
>                     First
  l Q                   len(Q) elements of the
  C .e                  Transpose of enumerated map lambda b,k:
       .>                 Rotate the kth element rightwards by
          b
          k               k.
       C +              Transpose of: Q concatenated to
           _ P t Q        itself reversed without first and last elements.
           Q

Try it here.

JavaScript (ES6), 70
a=>a.map((r,k)=>r.map((e,j)=>(a[k-=d]||a[d=-d,k-=d+d]||r)[j],d=1,++k))

TEST

F = a=>a.map((r,k)=>r.map((e,j)=>(a[k-=d]||a[d=-d,k-=d+d]||r)[j],d=1,++k))

test = [{
  I: [
    [1, 2, 3, 4, 5],
    [6, 7, 8, 9, 0]
  ],
  O: [
    [1, 7, 3, 9, 5],
    [6, 2, 8, 4, 0]
  ]
}, {
  I: [
    [1, 2, 3, 4, 5]
  ],
  O: [
    [1, 2, 3, 4, 5]
  ]
}, {
  I: [
    [0, 0, 0, 0, 0, 0, 0, 0],
    [9, 9, 9, 9, 9, 9, 9, 100],
    [0, 0, 0, 0, 0, 0, 0, 0]
  ],
  O: [
    [0, 9, 0, 9, 0, 9, 0, 100],
    [9, 0, 9, 0, 9, 0, 9, 0],
    [0, 9, 0, 9, 0, 9, 0, 100]
  ]
}, {
  I: [
    [0, 1, 2, 3, 4, 5],
    [6, 7, 8, 9, 10, 11],
    [12, 13, 14, 15, 16, 17]
  ],
  O: [
    [0, 7, 14, 9, 4, 11],
    [6, 1, 8, 15, 10, 5],
    [12, 7, 2, 9, 16, 11]
  ]
}, {
  I: [
    [0, 0, 0, 0, 0, 0],
    [1, 2, 3, 4, 5, 6],
    [2, 2, 2, 2, 2, 2],
    [9, 8, 7, 6, 5, 4]
  ],
  O: [
    [0, 2, 2, 6, 2, 6],
    [1, 0, 3, 2, 5, 2],
    [2, 2, 0, 4, 2, 4],
    [9, 2, 3, 0, 5, 2]
  ]
}];

console.log = x => O.textContent += x + '\n';

test.forEach(t => {
  var r = F(t.I),
    ok = r.join `\n` == t.O.join `\n`
  console.log((ok ? 'OK' : 'KO') + '\nInput\n' + t.I.join `\n` + '\nOutput\n' + r.join `\n` + '\n')
})

CJam, 31 30 bytes
q~__W%1>W<+_z,_@*<zee::m>z\,<p

Input and output as a list of CJam-style arrays.
Test it here.
Most definitely golfable...

Jelly, 29 25 24 bytes
ṖḊm-³;Z
,ZL€R_€/‘ż€Çị/€€

Thanks for @Sp3000 for helping me golf off 5 bytes!
Try it online!

Japt, 55 49 41 39 bytes
Wow, that was both really tricky and insanely fun.
C=2*Nl -2Nw £YoY+Ul)£NgLmX%CC-X%C)gY} ·

Test it online!
Outputs in reverse order to the examples. This will break slightly on inputs of more than 100 arrays; hopefully this doesn't make too much difference.
           // Implicit: N = array of input arrays, U = first input array, J = -1, L = 100
           // Let's use the first example. 3 input arrays, each of length 9.
C=2*Nl -2  // Set variable C to 2*N.length - 2. In the example, C is 4.
Nw      }  // Reverse N and map each index Y to:
YoY+Ul)    //  Create the range [Y...U.length+Y).
           //  The first time through (Y=0), we have   [0, 1, 2, 3, 4, 5, 6, 7, 8]
£       }  //  Map each item X and index Y to:
X%C        //   Take X mod C.                          [0, 1, 2, 3, 0, 1, 2, 3, 0]
C-X%C      //   Take C - (X mod C).                    [4, 3, 2, 1, 4, 3, 2, 1, 4]
Lm         //   Take the minimum of these and 100.     [0, 1, 2, 1, 0, 1, 2, 1, 0]
Ng         //   Get the array at the resulting index.
gY         //   Get the item at index Y in this array. [1, 8, 3, 6, 5, 4, 2, 7, 9]
·          // Join the result with newlines. I guess this isn't necessary, but it helps with readability.

Non-competing version, 36 bytes
C=J+Nl)òC±C ®óUl)£NgLmX%CC-X%C)gY} ·

I had implemented these two number functions prior to the challenge:

ò - same as o, but returns [X..Y] instead of [X..Y)
ó - same as o, but returns [X..X+Y) instead of [X..Y)

But due to a misplaced 0, they were buggy and always returned empty arrays. This has now been fixed.
Test it online!

Ruby (2.2.2p95), 124 bytes
->*a{b=a.length;b<2?a:b.times.map{|i|d=i>0?-1:1;c=i;a[0].length.times.map{|j|r=a[c][j];c+=d;d*=-1if c==0||c==a.length-1;r}}}

This could probably be a lot better. I'll figure out how later!

Python 2, 107 106 108 105 104 bytes
(Dropped some extra parens) (Wrong starting location (ب_ب) ) (already had a list of that length)
def b(a):
 r,e=len(a)-1,enumerate
 print[[a[abs((i-o-r)%(r*2or 1)-r)][i]for i,_ in e(q)]for o,q in e(a)]

It's legal to have the input as an argument to a function, right? This is my first time submitting my code golf answer.

Yes it is legal :)

APL, 33 chars
{(⍳≢⍵){0⌷(⍺-⍳≢⍉⍵)⊖⍵⍪1↓¯1↓⊖⍵}¨⊂↑⍵}

Assume ⎕IO←0.
The idea is that the bouncing movement can be obtained by simple shift upward of a matrix, if the original matrix is augmented along the first dimension with the matrix reversed with its first and last row shaved.
Graphically:
1 - - - - - 1 - - - -
- 2 - - - 2 - 2 - - -
- - 3 - 3 - - - 3 - 3
- - - 4 - - - - - 4 -

from
1 - - - - - 1 - - - -
- 2 - - - - - 2 - - -
- - 3 - - - - - 3 - -
- - - 4 - - - - - 4 -
- - - - 3 - - - - - 3
- - - - - 2 - - - - -

In APL reverse and upward rotate are the same symbol: ⊖.

USE THE FIRST STEFANO. ⊃ instead of 0⌷.

I am afraid "first" and "0⌷" give two very different results when applied to a nested array. Try it for yourself. First vs. 0⌷

Clojure, 125 bytes
Wow, this accumulated characters quite fast.
(fn[v](let[H(count v)r range R(r H)](for[i R](map #((v %2)%)(r(count(v 0)))(drop i(cycle(concat R(reverse(r 1(dec H))))))))))

Just trying to save bytes by let-defining frequently used values.

Jelly*, 15 bytes
JṚŒḄṖṙ’Ʋị⁸Jị"$€

Try it online!
* Newer version

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:
Help me fill my wallet!
A while ago I purchased a new wallet which is able to hold 8 cards (4 on both side). However, I seem to have way more cards than that and I need to make choices on which ones I want to carry with me. Some cards I use more often than others, but the cards I prefer to carry with me are not necessarily the ones I use most.
The challenge
Given a stack of cards, return the layout of my wallet in the best way possible w.r.t. my preferences and restrictions. The layout should be as follows:
__ __ (row 1)
__ __ (row 2)
__ __ (row 3)
__ __ (row 4)

Currently I posess the following cards - stacks will always consist of a selection from these:

1 identity card (ID)
1 driver's license (DL)
2 credit cards (CC)
5 debit cards (DC)
1 public transport card (PC)
1 gym access card (GC)
9 membership cards from random stores and warehouses (MC)

I have some preferences and restrictions:

Cards sorted by priority: ID, DL, CC, DC, PC, GC, MC
Cards sorted by usage frequency: CC, DC, PC, GC, MC, ID, DL
For safety reasons, the total number of debit cards and credit cards in my wallet can be at most 1 more than the sum of all other cards that will go in my wallet ( NDC+NCC ≤ NID+NDL+NPC+NGC+NMC+1 ).
If present, my identity card and driver's licence should always go in row 1. This does not mean that other cards may not occupy spots in row 1.
The most frequently used cards from the stack should always go in row 4.

Rules

No 2 cards can occupy the same spot.
Higher priority cards are always prefered over lower priority ones, unless the DC/CC restriction kicks in.
ID/DL at row 1 overrules the frequency rule: if only ID is provided, it will go in row 1 and row 4 will be empty!
Input formatting can be done in any way you like, as long as the order of the input stack is retained. e.g. ID,CC,PC,MC,MC,MC,DL may also be supplied as e.g. 1ID 1CC 1PC 3MC 1DL 0DC 0GC or ID CC PC MC MC MC DL.
Output formatting does have a few restrictions: rows must all start at a new line, columns must be delimited in some way. Empty spots may be presented any way you like, as long as it does not mess up the 4x2 layout.
There can be more than one solution/order, it's up to you which one you provide as output.
You may assume that cards of the same type will always be grouped at input.
Apart from the above, standard code-golf rules and loopholes apply.

Bonus
You are allowed to remove 15% of your bytecount if you also return any cards that did not go in the wallet. Print "It fits!" in case of no remaining cards. This additional output should be clearly separated from the returend layout.
Examples
Input:
ID, DL, CC, GC, MC

2 possible outputs:
ID DL      DL ID
__ __  or  __ MC
MC __      __ __
CC GC      GC CC

optional: It fits!

Input:
ID, CC, DC, PC, GC, MC, MC, MC, MC, MC

2 possible outputs:
ID MC      GC ID
MC MC  or  MC PC
PC GC      MC MC
CC DC      DC CC

optional: e.g. (MC, MC)  or  (2MC)

Input:
DC, DC, CC, CC, GC, DL

2 possible outputs:
DL __      GC DL
__ __  or  DC __
GC DC      __ __
CC CC      CC CC

optional: e.g. (DC)  or  (1DC)

Input:
CC, DC, DC, DC

2 possible outputs:
__ __      __ __
__ __  or  __ __
__ __      __ __
CC __      __ CC

optional: e.g. (DC, DC, DC)  or  (3DC)

Input:
CC, CC, MC, MC, MC, MC, MC, MC, PC, DC, DC, DC, DC, DC, GC

2 possible outputs:
MC MC      MC DC
PC GC  or  DC GC
DC DC      PC MC
CC CC      CC CC

optional: e.g. (DC, DC, DC, MC, MC, MC, MC)  or  (3DC, 4MC)

Input:
MC, MC, MC, MC, MC, MC, MC

2 possible outputs:
__ MC      MC MC
MC MC  or  MC MC
MC MC      MC __
MC MC      MC MC

optional: It fits!

Input:
ID, CC

2 possible outputs:
ID __      __ ID
__ __  or  __ __
__ __      __ __
CC __      CC __

optional: It fits!

This is code-golf, so the shortest code (in bytes) wins.

You forgot some important cards. ;)

Java 10, 385 384 382 381 bytes
C->{String[]R=new String[8],F={"CC","DC","PC","GC","MC"};int c=C.size(),i=1,s=0;c=c>8?8:c;for(var q:C)if("DCC".contains(q))s++;for(;s+--s>c;c=(c=C.size())>8?8:c)i=C.remove(F[i])?i:0;for(c=0,i=8;i>0&c<5;c++)for(;i>0&C.remove(F[c]);)R[--i]=F[c];if(C.remove("ID"))R[c=0]="ID";if(C.remove("DL"))R[c<1?1:0]="DL";for(i=0;i<8;)System.out.print((R[i]!=null?R[i]:"__")+(i++%2>0?"\n":" "));}

Although it wasn't too difficult, I can see why it was unanswered. Especially that rule regarding \$N_{DC}+N_{CC}\leq N_{ID}+N_{DL}+N_{GC}+N_{MC}+1\$ costs quite a lot of bytes at the moment..
And since it's been about 2.5 year since this challenge has been posted, OP might have got another wallet by now anyway.. ;p
-1 byte thanks to @Jakob
-1 byte thanks to @ceilingcat
Try it online.
Explanation:
C->{                        // Method with String-List parameter and String return-type
  String[]R=new String[8],  //  String-array of size 8
          F={"CC","DC","PC","GC","MC"};
                            //  Frequency-order String-array
  int c=C.size(),           //  Size of the input-List
      i=1,                  //  Index integer, starting at 1
      s=0;                  //  Count-integer, starting at 0
  c=c>8?8:c;                //  If the size is larger than 8, set it to 8
  for(var q:C)              //  Loop over the cards of the input-List:
    if("DCC".contains(q))   //   If the card is a DC or CC:
      s++;                  //    Increase the counter by 1
  for(;s+--s>c;             //  Loop as long as the amount of DC/CC is larger than the
                            //  other amount of cards + 1:
      c=(c=C.size())>8?8:c) //    Recalculate the size after every iteration
    i=C.remove(F[i])?i:0;   //   If the List still contains a DC, remove it
                            //   Else: remove a CC instead
  for(c=0,                  //  Reset `c` to 0
      i=8;i>0               //  Loop as long as there is still room in the wallet,
      &c<5;                 //  and we still have cards left:
      c++)                  //    Go to the next card-type after every iteration
    for(;i>0                //   Inner loop as long as there is still room in the wallet,
        &C.remove(F[c]);)   //   and we still have a card of the current type left:
      R[i--]=F[c];          //    Put a card of the current type in the wallet
  if(C.remove("ID"))R[c=0]="ID";
                            //  Add the 'ID' card to the first row if present
  if(C.remove("DL"))R[c<1?1:0]="DL";
                            //  Add the 'DL' card to the first row if present
  for(i=0;i<8;)             //  Loop over the wallet:
    System.out.print(       //   Print:
      (R[i]!=null?          //    If the current slot contains a card:
        R[i]                //     Append this card
       :                    //    Else:
        "__")               //     Append an empty slot ("__")
      +(i++%2>0?"\n":" "));}//    Append the correct delimiter (space or new-line)

Java 10, 390.15 389.3 (458 bytes - 15% bonus)
C->{String r="",R[]=new String[8],F[]={"CC","DC","PC","GC","MC"},t=r;int c=C.size(),i=1,s=0;for(var q:C)if("DCC".contains(q))s++;for(;s+--s>(c>8?8:c);c=C.size())if(C.remove(F[i]))t+=F[i]+",";else i=0;for(c=0,i=8;i>0&c<5;c++)for(;i>0&&C.remove(F[c]);)R[--i]=F[c];if(C.remove("ID")){t+=R[0]+",";R[c=0]="ID";};if(C.remove("DL")){t+=R[c=c<1?1:0]+",";R[c]="DL";}for(i=0;i<8;)r+=(R[i]!=null?R[i]:"__")+(i++%2>0?"\n":" ");return r+"\n"+(C.size()>0?t+C:"It fits!");}

Try it online.

You can save one byte by initializing F with {"CC","DC","PC","GC","MC"}.

@Jakob Ah, didn't realize that was shorter. Thanks!

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


text:
Triangular Ulam spiral
We've had a couple of challenges about the Ulam spiral. But that's not enough.
In this challenge we will plot a triangular Ulam spiral (as opposed to the usual, square Ulam spiral). Here's a sketch of what the spiral looks like.

As we know, the Ulam spiral arranges all natural numbers in an outward spiral, and marks only those that are prime. So in the above sketch only the numbers that appear in black (the primes) would be shown.
The challenge
Accept a number N as input and display the triangular Ulam spiral up to that number.

Input can be stdin or function argument.
The spiral should turn in the positive direction (that is, counter-clockwise), as in the above figure.
Any of the 120-degree turns of the above figure would be valid, and the turn may be different for different inputs. But the lowest side of the implied triangles should be horizontal, as the only allowed turns are (multiples of) 120 degrees.
The code should run theoretically (given enough time and memory) for any N up to what is allowed by any intermediate calculations you do with your default data type. double is enough; no need for large integer types.
All built-in functions allowed.
I won't accept my own answer (not that I think it would be the shortest anyway...).

Output formats
Choose any of the following.

Display a graph with a marker (dot, circle, cross, whatever you prefer) at prime numbers, and nothing at non-prime numbers. Scale need not be the same for the two axes. That is, the implied triangles need not be equilateral. Axes, grid lines and axis labels are optional. Only the markers at the prime numbers are required.
An example output for N = 12 would be as follows (compare with the above sketch). The second plot is a more interesting example, corresponding to N = 10000.

Produce an image file with the above, in any well known image format (such as png, tiff, bmp).
Display the spiral as ASCII art, using a single character of your choice for primes and blank space for non-primes, with a blank space to separate number positions in the same row. Leading or trailing spaces or newlines are allowed. For example, the N = 12 case using o as character would be
             o
            · ·
           · o ·
            o · ·
           · o · o

where of course only the o mark at primes would actually be displayed. The · at non-primes is shown here for reference only.

Winning criterion
The actual reward is seeing for yourself those amazing patterns Code golf, shortest code wins.

In the future I'd recommend choosing only one of [graphical-output] and [ascii-art] as it makes the submissions less comparable. But nice challenge anyway. :)

@AlexA. Thanks! I'll take that into account. So... will there be a Julia answer? ;-)

Wow, thanks for the bounty, but you should accept your own answer. It is the shortest. :)

It is well deserved! As for accepting an answer, one of the challenge rules was "I won't accept my own answer". When I thought this challenge I inevitably had MATL in mind, with its complex-number and graphical functions, so it was a bit like cheating :-)

CJam, 49 42 bytes
Lri{)mp0S?}%{1$,)/(a@Wf%z+\L*}h;eeSff*W%N*

Input as a single integer in STDIN. Output as an ASCII grid with 0 for primes. The rotation of the spiral is not consistent: the largest number of the spiral will always be on the bottom row.
Test it here.
Explanation
The basic idea is to represent the triangle as a ragged 2D array while doing the computation. You get this array by reversing the lines and aligning all rows to the left:
   4
  5 3
 6 1 2
7 8 9 A

Would be represented as
[[7 8 9 A]
 [6 1 2]
 [5 3]
 [4]]

Since we've mirrored the line, we want to roll up the spiral in a clockwise manner. That's convenient, because all we need to do is rotate the triangle counter-clockwise and prepend the next sublist in order. We can rotate the ragged array by reversing all lines and transposing it:
                                                           [[B C D E F]
[[7 8 9 A]         [[A 9 8 7]           [[A 2 3 4]          [A 2 3 4]
 [6 1 2]   reverse  [2 1 6]   transpose  [9 1 5]   prepend  [9 1 5]
 [5 3]      ---->   [3 5]      ------>   [8 6]      ---->   [8 6]
 [4]]               [4]]                 [7]]               [7]]

So here is the code. One detail I'd like to draw attention to is the last bit that creates the triangular layout. I think that's rather nifty. :)
L     e# Push an empty array. This will become the spiral.
ri    e# Read input and convert to integer N.
{     e# Map this block over 0 to N-1...
  )   e#   Increment to get 1 to N.
  mp  e#   Test for primality.
  0S? e#   Select 0 or a space correspondingly.
}%
{     e# While the list we just created is not empty yet...
  1$  e#   Copy the spiral so far.
  ,)  e#   Get the number of lines and increment.
  /   e#   Split the list into chunks of that size.
  (a@ e#   Pull off the first chunk, wrap it in an array, pull up the spiral.
  Wf% e#   Reverse the lines of the spiral.
  z   e#   Transpose the spiral.
  +   e#   Prepend the new line.
  \L* e#   Swap with the remaining chunks and join them back together into a single list.
}h
;     e# Discard the empty list that's left on the stack.
ee    e# Enumerate the spiral. This turns each line into a pair of 0-based index
      e# and the line itself.
Sff*  e# Multiply each element of each pair with a space. For the enumeration index i,
      e# this produces a string of i spaces - the required indentation (keeping in
      e# mind that our spiral is still upside down). For the line itself, this
      e# riffles the cells with spaces, creating the required gaps between the cells.
      e# All of this works because we always end the spiral on the bottom edge.
      e# This ensures that the left edge is always complete, so we don't need
      e# different indentation such as in the N=12 example in the challenge.
W%    e# Reverse the lines to make the spiral point upwards.
N*    e# Join the lines with linefeeds.

I knew you'd be the first!

@LuisMendo I was actually going to skip this one, because I thought the computation of the grid indices would be tedious, but then I realised I could just rotate the entire triangle while appending lines.

I always love your explanations of CJam programs because I can understand them, and I'm amazed at how complex, yet short, these programs can be.

MATL, 48 36 bytes
:1-H*X^.5+Y[2j3/*YP*ZeYsG:Zp)'.'2$XG

Uses current release (9.3.0).
Try it online! No idea how the online compiler manages to translate graphic output to ASCII, but it does This produces an approximate ASCII plot thanks to an Octave feature that is supported by the online compiler!
Edit (April 4, 2016): the function Y[ has been renamed to k since release 13.0.0. The link to the online compiler incorporates this change, so that the code can be tested.
Example
>> matl
 > :1-H*X^.5+Y[2j3/*YP*ZeYsG:Zp)'.'2$XG
 >
> 20000

produces the graphical output (MATLAB version shown):

Explanation
The code uses complex numbers to trace the path followed by the spiral. As can be seen from the first figure in the challenge, each straight leg of the spiral is a segment with increasing length 1, 2, 3, 4 ... and cyclically increasing orientation 120 degrees, 240 degrees, 0 degress, 120 degress...
The code first generates the individual complex displacements from each integer number to the next. These complex displacements have magnitude 1 and angle 2*pi/3, 4*pi/3 or 0 (in radians). Thus they can be easily generated as imaginary exponentials. For that, the integer sequence 0,1,2,2,3,3,3,4,4,4,4... is used first.
This integer sequence is almost like the "n appears n times" sequence (OEIS A002024), and can be obtained as floor(sqrt(2*n)+.5) where n is 0,1,2,3,... . Multiplying by 2j*pi/3,  where j is the imaginary unit, produces the desired complex displacements.
The displacements are accumulated to compute the positions corresponding to the integer numbers in the spiral. The first integer number in the spiral, which is 1, is arbitrarily located at position 1 in the complex plane.
Finally, the positions corresponding to non-prime numbers are discarded, and the rest are plotted in the complex plane.
:1-H*X^.5+Y[     % floor(sqrt(2*n)+.5) for n from 0 to N-1, where N is implicit input
2j3/*YP*Ze       % exp(2j*pi/3* ... )
Ys               % cumulative sum. Produces complex positions
G:               % vector 1,2...,N, where N is previous input
Zp               % logical index to select only prime numbers
)                % use that index to keep only complex positions of primes
'.'2$XG          % plot using marker '.'

What O.o  I need to read this further

Does Try It Online! support graphical output for MATL?

I thought TIO didn't support graphical output? If it does, I can easily have MATL automatically dump images to a .png file to be shown by the web page @AlexA

Hey! I did I simple test (plot(1:5)) and it does produce text-graphic output!! http://matl.tryitonline.net/#code=NTpYRw&input= @AlexA. How's this??

WHOA! That's awesome!

This seems to be the explanation: with Octave you get ASCII plots if there's no graphic display http://stackoverflow.com/questions/13745987/character-mode-shell-plots-with-matlab-octave/13747962#13747962

Drawing should be done with
LaTeX / PGF, 527 594 bytes
\documentclass{standalone}\usepackage{pgf}\let\z\let\z\e\advance\z\f\ifnum\z\h\the\z\a\newcount\a\i\a\j\a\l\a\x\a\y\a\p\a\q\a\n\i=1\l=1\p=-1\q=1\def\m#1{\e\i by1\e\j by1\e\x by\h\p\e\y by\h\q\pgfmathparse{isprime(\h\i)}\f\pgfmathresult=1\pgfpathcircle{\pgfpoint{\h\x cm}{\h\y cm}}3pt\fi\f\j=\l\e\l by1\j=0\f\p=1\p=-1\q=1\else\f\p=-1\p=0\q=-1\else\p=1\q=0\fi\fi\fi\f#1>0\e#1by-1\m#1\fi}\begin{document}\begin{pgfpicture}\pgftransformcm10{cos(60)}{sin(60)}\pgfpointorigin\n=4000\m\n\pgfusepath{fill}\end{pgfpicture}\end{document}

527 bytes is the full document as above, i.e. including preamble and parameter (here 4000, so ~523 without parameter). Produces a PDF file.
Basic idea: well, just draw. Uses a matrix transformation for a triangular grid. Only problem is that also the dots are affected (and stretched) out by the transformation. So I choose for ellipse markers :) what I mean by that is clear in the second image (n=250, 5pt).
Another caveat: can only handle up to a bit less than 5000 because of TeX's maximum stack size. The first image is for n=4000. Apparently it is possible to increase the stack size, I didn't try it.
Uses PGF's isprime().

Ungolfed:
\documentclass[border=10cm]{standalone}

\usepackage{pgf}

\newcount\ulami
\newcount\ulamj
\newcount\ulamlen

\newcount\ulamx
\newcount\ulamy
\newcount\ulamdx
\newcount\ulamdy

\ulami=1 %
\ulamj=0 %
\ulamlen=1 %
\ulamdx=-1 %
\ulamdy=1 %
\ulamx=0 %
\ulamy=0 %

\def\ulamplot#1{%
  \advance\ulami by 1 %
  \advance\ulamj by 1 %

  \advance\ulamx by \the\ulamdx %
  \advance\ulamy by \the\ulamdy %

  \pgfpathmoveto{\pgfpoint{\the\ulamx cm}{\the\ulamy cm}}

  \pgfmathparse{isprime(\the\ulami)}
  \let\r=\pgfmathresult
  \ifnum\r=1
    \pgfpathcircle{\pgfpoint{\the\ulamx cm}{\the\ulamy cm}}{5pt}
  \fi

  \ifnum\ulamj=\the\ulamlen %
    \advance\ulamlen by 1 %
    \ulamj=0 %
    \ifnum\ulamdx=1 %
      \ulamdx=-1 %
      \ulamdy=1 %
    \else%
      \ifnum\ulamdx=-1 %
        \ulamdx=0 %
        \ulamdy=-1 %
      \else%
        \ulamdx=1 %
        \ulamdy=0 %
      \fi
    \fi
  \fi

  \ifnum#1>0 %
    \advance#1 by -1 %
    \ulamplot{#1}%
  \fi
}

\begin{document}

\begin{pgfpicture}
  \pgfmathsetmacro{\x}{cos(60)}
  \pgfmathsetmacro{\y}{sin(60)}
  \pgftransformcm{1}{0}{\x}{\y}{\pgfpointorigin}

  \pgfpathmoveto{\pgfpointorigin}
  \color{blue}
  \newcount\ulamn
  \ulamn=400
  \ulamplot{\ulamn}
  \pgfusepath{stroke,fill}
\end{pgfpicture}

\end{document}

Wow. It would have never occurred to me to do this in LaTeX

Using lualatex or some other dynamically allocating compiler should let you bypass the stack size, if I understand your corresponding comment correctly. So it's not a limitation of your answer, just of most of the implementations where you'd run it.

Sorry, I've checked and the input stack size limit is unrelated to memory allocation which I addressed in my previous comment:(

@AndrasDeak that's okay, thanks for looking it up. I found a method that apparently does increase the stack size, but didn't try it myself (yet).

@CamilStaps thanks, I've found other similar posts, but I didn't try them either. Anyway, I take Christian Feuersänger's posts as canon:)

Python, 263 bytes
Being new to Python, there is surely room for improvement :)
from matplotlib.pyplot import*
from math import*
def f(m):
 s=[];X=[];Y=[];i=x=y=0
 while len(s)<m:i+=1;s+=[i%3*pi*2/3]*i
 for i in range(m):
  x+=cos(s[i]);y+=sin(s[i]);j=i+2
  if all(map(lambda a:j%a>=1,range(2,int(j**.5+1)))):X+=[x];Y+=[y]
 scatter(X,Y);show()

Example:
f(100000)

You can shorten s=[];X=[];Y=[];i=1;x=0;y=0 to s=X=Y=[];i=1;x=y=0;

Ignore that extra semicolon at the end. It should spare you 8 bytes.

@rp.beltran. This does not work. I think it is related to the fact the objects share the same values. Could only add x=y=0.

My bad, you are right. I forgot that Python passes lists by reference. Numbers are immutable and so it is safe to do with integers.

Mathematica, 94 bytes
ListPlot@Accumulate[Join@@Table[ReIm@Exp[2i Pi/3I],{i,2#^.5},{i}]][[Prime@Range@PrimePi@#-1]]&

Result
%[10000]

R, 137 bytes
Uses only built-in functions, even for prime numbers. Given its vectorized approach instead of iterative, it is fast, but cannot handle huge numbers.
Golfed:
g=function(m){M=1:m;s=rep(M,M)[M]%%3*pi*2/3;k=cumsum;j=sapply(seq(s)+1,function(n)n<4|all(n%%2:n^.5>=1));plot(k(cos(s))[j],k(sin(s))[j])}

Ungolfed:
g=function(m) {
  M = 1:m
  s = rep(M,M)[M] %% 3 * pi * 2/3
  k=cumsum
  j=sapply(seq(s)+1,function(n)n<4|all(n%%2:n^.5>=1)) # primes
  plot(k(cos(s))[j],k(sin(s))[j])    # cumulated coordinates
}

Example:
g(10000)

Can you add an example result?

@LuisMendo. Sure. I had only to figure out how to add a plot.


text:
Calculate the Number, Divisors Edition
Inspired by this question over on Math.
Let the prime factorization of a number, n, be represented as: \$P(n) = 2^a\times3^b\times5^c\times\cdots\$. Then the number of divisors of n can be represented as \$D(n) = (a+1)\times(b+1)\times(c+1)\times\cdots\$. Thus, we can easily say that the number of divisors of \$2n\$ is \$D(2n) =  (a+2)\times(b+1)\times(c+1)\times\cdots\$,
the number of divisors of \$3n\$ is \$D(3n) =  (a+1)\times(b+2)\times(c+1)\times\cdots\$,
and so on.
Challenge
Write a program or function that uses these properties to calculate \$n\$, given certain divisor inputs.
Input
A set of integers, let's call them \$w, x, y, z\$, with all of the following definitions:

all inputs are greater than 1 -- \$w, x, y, z > 1\$
\$x\$ and \$z\$ are distinct -- \$x\ne z\$
\$x\$ and \$z\$ are prime -- \$P(x)=x, D(x)=2, P(z)=z \text{ and } D(z)=2\$
\$w\$ is the number of divisors of \$xn\$ -- \$D(xn)=w\$
\$y\$ is the number of divisors of \$zn\$ -- \$D(zn)=y\$

For the problem given in the linked question, an input example could be \$(28, 2, 30, 3)\$. This translates to \$D(2n)=28\$ and \$D(3n)=30\$, with \$n=864\$.
Output
A single integer, \$n\$, that satisfies the above definitions and input restrictions.  If multiple numbers fit the definitions, output the smallest. If no such integer is possible, output a falsey value.
Examples:
(w, x, y, z) => output

(28, 2, 30, 3) => 864
(4, 2, 4, 5) => 3
(12, 5, 12, 23) => 12
(14, 3, 20, 7) => 0 (or some other falsey value)
(45, 13, 60, 11) => 1872
(45, 29, 60, 53) => 4176

Rules:

Standard code-golf rules and loophole restrictions apply.
Standard input/output rules apply.
Input numbers can be in any order - please specify in your answer which order you're using.
Input numbers can be in any suitable format: space-separated, an array, separate function or command-line arguments, etc. - your choice.
Similarly, if output to STDOUT, surrounding whitespace, trailing newline, etc. are all optional.
Input parsing and output formatting are not the interesting features of this challenge.
In the interests of sane complexity and integer overflows, the challenge number \$n\$ will have restrictions such that \$1 < n < 100000\$ -- i.e., you don't need to worry about possible answers outside this range.

Related

Count the divisors of a number
Give the smallest number that has N divisors
Divisor sum from prime-power factorization

So, if the smallest solution is larger than 100,000, I can choose to return either a solution or zero?

@Dennis If it makes your code shorter, sure. Either would be acceptable.

Jelly, 17 16 bytes
×€ȷ5R¤ÆDL€€Z=Ḅi3

This is a brute force solution that tries all possible values up to 100,000. Try it online!
Non-competing version
The latest version of Jelly has a bug fix that allows to golf down the above code to 15 bytes.
ȷ5R×€³ÆDL€€=Ḅi3

Try it online!
How it works
×€ȷ5R¤ÆDL€€Z=Ḅi3  Main link. Left input: x,z. Right input: w,y

     ¤            Combine the two atoms to the left into a niladic chain.
  ȷ5              Yield 100,000 (1e5).
    R             Apply range. Yields [1, ..., 100,000].
x€                Multiply each r in the range by x and z.
                  This yields [[x, ..., 100,000x], [z, ..., 100,000z]].
      ÆD          Compute the divisors of each resulting integer.
        L€€       Apply length to each list of divisors.
                  This counts the divisors of each integer in the 2D array.
           Z      Zip; group the divisors of kx and kz in pairs.
            =     Compare each [divisors(kx), divisors(kz)] with [w, y].
                  This yields a pair of Booleans.
             Ḅ    Convert each Boolean pair from binary to integer.
              i3  Find the first index of 3. Yields 0 for not found.

Congrats, you win by default! :D

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


text:
Build a Nonographic Magnitude Optimizer™
A nonogram is a Japanese puzzle game in which the goal is to draw a black-and-white picture according to a list of contiguous regions, like so:

Define the nonographic magnitude of a row or column to be the number of contiguous black regions in that row or column. For example, the top row has a nonographic magnitude of 1, because there is one region of 2 squares in that row. The 8th row has a nonographic magnitude of 3 because it has 2, 2, 1.
An empty row or column has a nonographic magnitude of 0.

Your task is to write a program that takes a solution grid for a nonogram, and produces a solution grid with as few filled-in squares as possible where every row and column has the same nonographic magnutide as the given solution grid.
For example, a nonogram grid with all the squares filled in has a nonographic magnitude of 1 on every row or column:

The same nonographic magnitude could be achieved just by having a diagonal stripe through the grid, reducing the number of filled-in squares dramatically:

Your program will receive an input consisting of 50,000 lines from this file (1.32 MB tar.gz text file; 2.15 MB unzipped), each representing a single 16×16 nonogram solution grid with randomly (80% black) filled-in squares, and output another 50,000 lines, each containing the optimized solution grid for the corresponding input grid.
Each grid is represented as a base64 string with 43 characters (encoding squares from left to right, then top to bottom), and your program will need to return its output in the same format. For example, the first grid in the file is E/lu/+7/f/3rp//f799xn/9//2mv//nvj/bt/yc9/40=, and renders as:

The grid starts with E which maps to 000100, so the first six cells in the top row are all white except the fourth one. The next character is / which maps to 111111, so the next 6 cells are all black — and so on.

Your program must actually return a solution grid with the correct nonographic magnitudes for each of the 50,000 test cases. It is allowed to return the same grid as the input if nothing better was found.
The program to return the fewest total filled-in squares (in any language) is the winner, with shorter code being the tiebreaker.

Current scoreboard:

3,637,260 — Sleafar, Java
7,270,894 — flawr, Matlab
10,239,288 — Joe Z., Bash

I do not really see the point of the base 64 encoding and working with that is a real pain. Wouldn't it be easier to just make lines of ones and zeros? Or encode the whole thing as a bitmap?

@flawr: It reduces the filesize, mainly (by a factor of 6 compared to just 1's and 0's). Also, bitmaps would be even harder to work with.

You could just make a black and white image, easy to read/write and same size as b64 encoding.

Could you please post e.g. the first example as an image, such that we can see if our base 64 implementation does work correctly?

@flawr Alright, done.

also not a fan of the b64 encoding, for input and/or output. why not just let the i/o be in any convenient format?

@Sparr: I could relax the requirement on output, but the input file is what it is — you'd have to re-encode the input for your program yourself.

Can you confirm that these are the correct magnitudes for the given inputs (each pair of lines is 16 numbers for the 16 row magnitudes and then 16 numbers for the 16 column magnitudes): https://drive.google.com/file/d/0B-0NVE9E8UJiNFdmYlk1aV9aYzQ/view?usp=sharing

@quintopia: The first one is correct. Let me check the second one by generating it...

Assuming it is, I should have an optimal solution by this time tomorrow.

Python 2 & PuLP — 2,644,688 squares (optimally minimized); 10,753,553 squares (optimally maximized)
Minimally golfed to 1152 bytes
from pulp import*
x=0
f=open("c","r")
g=open("s","w")
for k,m in enumerate(f):
 if k%2:
    b=map(int,m.split())
    p=LpProblem("Nn",LpMinimize)
    q=map(str,range(18))
    ir=q[1:18]
    e=LpVariable.dicts("c",(q,q),0,1,LpInteger)
    rs=LpVariable.dicts("rs",(ir,ir),0,1,LpInteger)
    cs=LpVariable.dicts("cs",(ir,ir),0,1,LpInteger)
    p+=sum(e[r][c] for r in q for c in q),""
    for i in q:p+=e["0"][i]==0,"";p+=e[i]["0"]==0,"";p+=e["17"][i]==0,"";p+=e[i]["17"]==0,""
    for o in range(289):i=o/17+1;j=o%17+1;si=str(i);sj=str(j);l=e[si][str(j-1)];ls=rs[si][sj];p+=e[si][sj]<=l+ls,"";p+=e[si][sj]>=l-ls,"";p+=e[si][sj]>=ls-l,"";p+=e[si][sj]<=2-ls-l,"";l=e[str(i-1)][sj];ls=cs[si][sj];p+=e[si][sj]<=l+ls,"";p+=e[si][sj]>=l-ls,"";p+=e[si][sj]>=ls-l,"";p+=e[si][sj]<=2-ls-l,""
    for r,z in enumerate(a):p+=lpSum([rs[str(r+1)][c] for c in ir])==2*z,""
    for c,z in enumerate(b):p+=lpSum([cs[r][str(c+1)] for r in ir])==2*z,""
    p.solve()
    for r in ir:
     for c in ir:g.write(str(int(e[r][c].value()))+" ")
     g.write('\n')
    g.write('%d:%d\n\n'%(-~k/2,value(p.objective)))
    x+=value(p.objective)
 else:a=map(int,m.split())
print x

(NB: the heavily indented lines start with tabs, not spaces.)
Example output: https://drive.google.com/file/d/0B-0NVE9E8UJiX3IyQkJZVk82Vkk/view?usp=sharing
It turns out that problems like are readily convertible to Integer Linear Programs, and I needed a basic problem to learn how to use PuLP—a python interface for a variety of LP solvers—for a project of my own. It also turns out that PuLP is extremely easy to use, and the ungolfed LP builder worked perfectly the first time I tried it.
The two nice things about employing a branch-and-bound IP solver to do the hard work of solving this for me (other than not having to implement a branch and bound solver) are that

Purpose-built solvers are really fast. This program solves all 50000 problems in about 17 hours on my relatively low-end home PC. Each instance took from 1-1.5 seconds to solve.
They produce guaranteed optimal solutions (or tell you that they failed to do so). Thus, I can be confident that no one will beat my score in squares (although someone might tie it and beat me on the golfing part).

How to use this program
First, you'll need to install PuLP. pip install pulp should do the trick if you have pip installed.
Then, you'll need to put the following in a file called "c": https://drive.google.com/file/d/0B-0NVE9E8UJiNFdmYlk1aV9aYzQ/view?usp=sharing
Then, run this program in any late Python 2 build from the same directory. In less than a day, you'll have a file called "s" which contains 50,000 solved nonogram grids (in readable format), each with the total number of filled squares listed below it.
If you'd like to maximize the number of filled squares instead, change the LpMinimize on line 8 to LpMaximize instead. You will get output very much like this: https://drive.google.com/file/d/0B-0NVE9E8UJiYjJ2bzlvZ0RXcUU/view?usp=sharing
Input format
This program uses a modified input format, since Joe Z. said that we would be allowed to re-encode the input format if we like in a comment on the OP. Click the link above to see what it looks like. It consists of 10000 lines, each containing 16 numbers. The even numbered lines are the magnitudes for the rows of a given instance, while the odd numbered lines are the magnitudes for the columns of the same instance as the line above them. This file was generated by the following program:
from bitqueue import *

with open("nonograms_b64.txt","r") as f:
    with open("nonogram_clues.txt","w") as g:
        for line in f:
            q = BitQueue(line.decode('base64'))
            nonogram = []
            for i in range(256):
                if not i%16: row = []
                row.append(q.nextBit())
                if not -~i%16: nonogram.append(row)
            s=""
            for row in nonogram:
                blocks=0                         #magnitude counter
                for i in range(16):
                    if row[i]==1 and (i==0 or row[i-1]==0): blocks+=1
                s+=str(blocks)+" "
            print >>g, s
            nonogram = map(list, zip(*nonogram)) #transpose the array to make columns rows
            s=""
            for row in nonogram:
                blocks=0
                for i in range(16):
                    if row[i]==1 and (i==0 or row[i-1]==0): blocks+=1
                s+=str(blocks)+" "
            print >>g, s

(This re-encoding program also gave me an extra opportunity to test my custom BitQueue class I created for the same project mentioned above. It is simply a queue to which data can be pushed as sequences of bits OR bytes, and from which data can be popped either a bit or a byte at a time. In this instance, it worked perfectly.)
I re-encoded the input for the specific reason that to build an ILP, the extra information about the grids that were used to generate the magnitudes is perfectly useless. The magnitudes are the only constraints, and so the magnitudes are all I needed access to.
Ungolfed ILP builder
from pulp import *
total = 0
with open("nonogram_clues.txt","r") as f:
    with open("solutions.txt","w") as g:
        for k,line in enumerate(f):
            if k%2:
                colclues=map(int,line.split())
                prob = LpProblem("Nonogram",LpMinimize)
                seq = map(str,range(18))
                rows = seq
                cols = seq
                irows = seq[1:18]
                icols = seq[1:18]
                cells = LpVariable.dicts("cell",(rows,cols),0,1,LpInteger)
                rowseps = LpVariable.dicts("rowsep",(irows,icols),0,1,LpInteger)
                colseps = LpVariable.dicts("colsep",(irows,icols),0,1,LpInteger)
                prob += sum(cells[r][c] for r in rows for c in cols),""
                for i in rows:
                    prob += cells["0"][i] == 0,""
                    prob += cells[i]["0"] == 0,""
                    prob += cells["17"][i] == 0,""
                    prob += cells[i]["17"] == 0,""
                for i in range(1,18):
                    for j in range(1,18):
                        si = str(i); sj = str(j)
                        l = cells[si][str(j-1)]; ls = rowseps[si][sj]
                        prob += cells[si][sj] <= l + ls,""
                        prob += cells[si][sj] >= l - ls,""
                        prob += cells[si][sj] >= ls - l,""
                        prob += cells[si][sj] <= 2 - ls - l,""
                        l = cells[str(i-1)][sj]; ls = colseps[si][sj]
                        prob += cells[si][sj] <= l + ls,""
                        prob += cells[si][sj] >= l - ls,""
                        prob += cells[si][sj] >= ls - l,""
                        prob += cells[si][sj] <= 2 - ls - l,""
                for r,clue in enumerate(rowclues):
                    prob += lpSum([rowseps[str(r+1)][c] for c in icols]) == 2 * clue,""
                for c,clue in enumerate(colclues):
                    prob += lpSum([colseps[r][str(c+1)] for r in irows]) == 2 * clue,""
                prob.solve()
                print "Status for problem %d: "%(-~k/2),LpStatus[prob.status]
                for r in rows[1:18]:
                    for c in cols[1:18]:
                        g.write(str(int(cells[r][c].value()))+" ")
                    g.write('\n')
                g.write('Filled squares for %d: %d\n\n'%(-~k/2,value(prob.objective)))
                total += value(prob.objective)
            else:
                rowclues=map(int,line.split())
print "Total number of filled squares: %d"%total

This is the program that actually produced the "example output" linked above. Hence the extra long strings at the end of each grid, which I truncated when golfing it. (The golfed version should produce identical output, minus the words "Filled squares for ")
How it Works
cells = LpVariable.dicts("cell",(rows,cols),0,1,LpInteger)
rowseps = LpVariable.dicts("rowsep",(irows,icols),0,1,LpInteger)
colseps = LpVariable.dicts("colsep",(irows,icols),0,1,LpInteger)

I use an 18x18 grid, with the center 16x16 part being the actual puzzle solution. cells is this grid. The first line creates 324 binary variables: "cell_0_0", "cell_0_1", and so on. I also create grids of the "spaces" between and around the cells in the solution part of the grid. rowseps points to the 289 variables which symbolize the spaces that separate cells horizontally, while colseps similarly points to variables that mark the spaces that separate cells vertically. Here's a unicode diagram:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

The 0s and □s are the binary values tracked by the cell variables, the |s are the binary values tracked by the rowsep variables, and the -s are the binary values tracked by the colsep variables.
prob += sum(cells[r][c] for r in rows for c in cols),""

This is the objective function. Just the sum of all the cell variables. Since these are binary variables, this is just exactly the number of filled squares in the solution.
for i in rows:
    prob += cells["0"][i] == 0,""
    prob += cells[i]["0"] == 0,""
    prob += cells["17"][i] == 0,""
    prob += cells[i]["17"] == 0,""

This just sets the cells around the outer edge of the grid to zero (which is why I represented them as zeroes above). This is the most expedient way to track how many "blocks" of cells are filled, since it ensures that every change from unfilled to filled (moving across a column or row) is matched by a corresponding change from filled to unfilled (and vice versa), even if the first or last cell in the row is filled. This is the sole reason for using an 18x18 grid in the first place. It's not the only way to count blocks, but I think it is the simplest.
for i in range(1,18):
    for j in range(1,18):
        si = str(i); sj = str(j)
        l = cells[si][str(j-1)]; ls = rowseps[si][sj]
        prob += cells[si][sj] <= l + ls,""
        prob += cells[si][sj] >= l - ls,""
        prob += cells[si][sj] >= ls - l,""
        prob += cells[si][sj] <= 2 - ls - l,""
        l = cells[str(i-1)][sj]; ls = colseps[si][sj]
        prob += cells[si][sj] <= l + ls,""
        prob += cells[si][sj] >= l - ls,""
        prob += cells[si][sj] >= ls - l,""
        prob += cells[si][sj] <= 2 - ls - l,""

This is the real meat of the logic of the ILP. Basically it requires that each cell (other than those in the first row and column) be the logical xor of the cell and separator directly to its left in its row and directly above it in its column. I got the constraints that simulate an xor within a {0,1} integer program from this wonderful answer: https://cs.stackexchange.com/a/12118/44289
To explain a bit more: this xor constraint makes it so that the separators can be 1 if and only if they lie between cells which are 0 and 1 (marking a change from unfilled to filled or vice versa). Thus, there will be exactly twice as many 1-valued separators in a row or column as the number of blocks in that row or column. In other words, the sum of the separators on a given row or column is exactly twice the magnitude of that row/column. Hence the following constraints:
for r,clue in enumerate(rowclues):
    prob += lpSum([rowseps[str(r+1)][c] for c in icols]) == 2 * clue,""
for c,clue in enumerate(colclues):
    prob += lpSum([colseps[r][str(c+1)] for r in irows]) == 2 * clue,""

And that's pretty much it. The rest just asks the default solver to solve the ILP, then formats the resulting solution as it writes it to the file.

Really good answer. Make me wanna learn about LP solvers. Do you think it could be used to solve flood it puzzle (link) for a 19x19, 6 colors board (regarding time to compute a solution) ? I have already answered that contest (and won it) however my method (A* search algorithm) only give non optimal solutions.

@tigrou Thanks. I'm not sure the flood problem is linear enough to admit such a solution. I certainly can't see how to model it this way.

It seems somebody already tried it : https://kunigami.blog/2012/09/16/flood-it-an-exact-approach/ However they couldn't optimal solutions in feasible time for a 14x14 board.

Java, 6,093,092 4,332,656 3,637,260 squares (minimized), 10,567,550 10,567,691 10,568,746 squares (maximized)
Both variants of the program repeatedly perform operations on the source grid, without changing the magnitude.
Minimizer
shrink()

If a black square has 2 white neighbors and 2 black neighbors in a 90° angle, it can be replaced by a white square.
moveLine()

In configurations like above the black line can be moved to the right. This is done repeatedly for all 4 line directions clockwise and counterclockwise, to open up new shrink possibilities.
Maximizer
Uncomment the line in main() and comment out the line above it for this version.
grow()

If a white square has 2 white neighbors and 2 black neighbors in a 90° angle, it can be replaced by a black square.
moveLine()
Same as in Minimizer.
Source
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.Arrays;
import java.util.Base64;
import java.util.function.Function;

public class Main {
    private static final int SIZE = 16;
    private static final int SIZE_4 = SIZE + 4;
    private static final int E = 0;
    private static final int N = 1;
    private static final int W = 2;
    private static final int S = 3;

    private static final Base64.Decoder decoder = Base64.getMimeDecoder();
    private static final Base64.Encoder encoder = Base64.getMimeEncoder();
    private static int sourceBlack = 0;
    private static int targetBlack = 0;

    private static class Nonogram {
        private final boolean[] cells = new boolean[SIZE_4 * SIZE_4];
        private final int[] magnitudes;

        public Nonogram(String encoded) {
            super();
            byte[] decoded = decoder.decode(encoded);
            for (int i = 0; i < decoded.length; ++ i) {
                for (int j = 0; j < 8; ++ j) {
                    if ((decoded[i] & (1 << (7 - j))) != 0) {
                        int k = i * 8 + j;
                        cells[getPos(k / SIZE, k % SIZE)] = true;
                        ++ sourceBlack;
                    }
                }
            }
            magnitudes = calcMagnitudes();
        }

        private int getPos(int row, int col) {
            return (row + 2) * SIZE_4 + col + 2;
        }

        private int move(int pos, int dir, int count) {
            switch (dir) {
                case E: return pos + count;
                case N: return pos - count * SIZE_4;
                case W: return pos - count;
                case S: return pos + count * SIZE_4;
                default: return pos;
            }
        }

        private int move(int pos, int dir) {
            return move(pos, dir, 1);
        }

        private int[] calcMagnitudes() {
            int[] result = new int[SIZE * 2];
            for (int row = 0; row < SIZE; ++ row) {
                for (int col = 0; col < SIZE; ++ col) {
                    int pos = getPos(row, col);
                    if (cells[pos]) {
                        if (!cells[move(pos, W)]) {
                            ++ result[row + SIZE];
                        }
                        if (!cells[move(pos, N)]) {
                            ++ result[col];
                        }
                    }
                }
            }
            return result;
        }

        private boolean isBlack(int pos) {
            return cells[pos];
        }

        private boolean isWhite(int pos) {
            return !cells[pos];
        }

        private boolean allBlack(int pos, int dir, int count) {
            int p = pos;
            for (int i = 0; i < count; ++ i) {
                if (isWhite(p)) {
                    return false;
                }
                p = move(p, dir);
            }
            return true;
        }

        private boolean allWhite(int pos, int dir, int count) {
            int p = pos;
            for (int i = 0; i < count; ++ i) {
                if (isBlack(p)) {
                    return false;
                }
                p = move(p, dir);
            }
            return true;
        }

        private int findWhite(int pos, int dir) {
            int count = 0;
            int p = pos;
            while (cells[p]) {
                ++ count;
                p = move(p, dir);
            }
            return count;
        }

        @SafeVarargs
        private final void forEach(Function<Integer, Boolean>... processors) {
            outer:
            for (;;) {
                for (Function<Integer, Boolean> processor : processors) {
                    for (int row = 0; row < SIZE; ++ row) {
                        for (int col = 0; col < SIZE; ++ col) {
                            if (processor.apply(getPos(row, col))) {
                                continue outer;
                            }
                        }
                    }
                }
                return;
            }
        }

        private boolean shrink(int pos) {
            if (cells[pos] && cells[move(pos, W)] != cells[move(pos, E)] &&
                    cells[move(pos, N)] != cells[move(pos, S)]) {
                cells[pos] = false;
                return true;
            }
            return false;
        }

        private boolean grow(int pos) {
            if (!cells[pos] && cells[move(pos, W)] != cells[move(pos, E)] &&
                    cells[move(pos, N)] != cells[move(pos, S)]) {
                cells[pos] = true;
                return true;
            }
            return false;
        }

        private boolean moveLine(boolean clockwise, int dir, int sourcePos) {
            int from = (dir + (clockwise ? 1 : 3)) % 4;
            int to = (dir + (clockwise ? 3 : 1)) % 4;
            int opp = (dir + 2) % 4;
            if (isBlack(sourcePos) && isWhite(move(sourcePos, from)) && isWhite(move(sourcePos, dir))) {
                int toCount = findWhite(move(move(sourcePos, dir), to), to) + 1;
                if (allWhite(move(sourcePos, to), to, toCount + 1)) {
                    int lineCount = 1;
                    int tmpPos = move(sourcePos, opp);
                    while (isBlack(tmpPos) && isWhite(move(tmpPos, from)) && allWhite(move(tmpPos, to),  to, toCount + 1)) {
                        ++ lineCount;
                        tmpPos = move(tmpPos, opp);
                    }
                    if (allBlack(tmpPos, to, toCount + 1)) {
                        tmpPos = sourcePos;
                        for (int j = 0; j < lineCount; ++ j) {
                            cells[tmpPos] = false;
                            cells[move(tmpPos, to, toCount)] = true;
                            tmpPos = move(tmpPos, opp);
                        }
                        return true;
                    }
                }
            }
            return false;
        }

        public Nonogram minimize() {
            for (int i = 0; i < 5; ++ i) {
                forEach(pos -> shrink(pos), pos -> moveLine(true, E, pos), pos -> moveLine(true, N, pos),
                        pos -> moveLine(true, W, pos), pos -> moveLine(true, S, pos));
                forEach(pos -> shrink(pos), pos -> moveLine(false, E, pos), pos -> moveLine(false, N, pos),
                        pos -> moveLine(false, W, pos), pos -> moveLine(false, S, pos));
            }
            return this;
        }

        public Nonogram maximize() {
            for (int i = 0; i < 5; ++ i) {
                forEach(pos -> grow(pos), pos -> moveLine(true, E, pos), pos -> moveLine(true, N, pos),
                        pos -> moveLine(true, W, pos), pos -> moveLine(true, S, pos));
                forEach(pos -> grow(pos), pos -> moveLine(false, E, pos), pos -> moveLine(false, N, pos),
                        pos -> moveLine(false, W, pos), pos -> moveLine(false, S, pos));
            }
            return this;
        }

        public String toBase64() {
            if (!Arrays.equals(magnitudes, calcMagnitudes())) {
                throw new RuntimeException("Something went wrong!");
            }
            byte[] decoded = new byte[SIZE * SIZE / 8];
            for (int i = 0; i < decoded.length; ++ i) {
                for (int j = 0; j < 8; ++ j) {
                    int k = i * 8 + j;
                    if (cells[getPos(k / SIZE, k % SIZE)]) {
                        decoded[i] |= 1 << (7 - j);
                        ++ targetBlack;
                    }
                }
            }
            return encoder.encodeToString(decoded);
        }

        @Override
        public String toString() {
            StringBuilder b = new StringBuilder();
            for (int row = 0; row < SIZE; ++ row) {
                for (int col = 0; col < SIZE; ++ col) {
                    b.append(cells[getPos(row, col)] ? '#' : ' ');
                }
                b.append('\n');
            }
            return b.toString();
        }
    }

    public static void main(String[] args) throws Exception {
        try (BufferedWriter writer = new BufferedWriter(new FileWriter("solutions_b64.txt"));
                BufferedReader reader = new BufferedReader(new FileReader("nonograms_b64.txt"))) {
            String line;
            while ((line = reader.readLine()) != null) {
                writer.write(new Nonogram(line).minimize().toBase64() + "\n");
                //writer.write(new Nonogram(line).maximize().toBase64() + "\n");
            }
        }
        System.out.printf("%d -> %d", sourceBlack, targetBlack);
    }
}

Bash — 10,239,288 squares
As a last-place reference solution:
cp nonograms_b64.txt solutions_b64.txt

Since your program is allowed to return the same grid if it can't find a better solution, printing out the whole file verbatim is also valid.
There are a total of 10,239,288 black squares in the test file, which is pretty close to the 10,240,000 you'd expect from 80% of squares filled in out of 50,000 grids with 256 squares each. As usual with my test-battery questions, I've selected the number of test cases with the expectation that the optimal scores will be around the 2-million range, although I suspect the scores will be closer to 4 or 5 million this time around.

If anyone can create a solution that maximizes the black squares rather than minimizing them and manages to get over 10,240,000, I might consider giving it a bounty.

Matlab, 7,270,894 squares (~71% of original)
Idea is a simple repeated greedy search: For every black square, try if you can set it to white without changing the nonographic magnitudes. Repeat this twice. (You could achieve way better results with more repetitions, but not for free: It results in an correspondingly longer runtime. Now it was about 80 minutes. I would do that, if we would not have to compute all 50k testcases...)
Here the code (each function in a separate file, as usual.)
function D = b64decode(E)
% accepts a string of base 64 encoded data, and returns a array of zeros
% and ones
F = E;
assert( mod(numel(E),4)==0 && 0 <= sum(E=='=') && sum(E=='=') <= 2,'flawed base 64 code')

F('A' <= E & E<= 'Z') = F('A' <= E & E<= 'Z') -'A';       %upper case
F('a' <= E & E<= 'z') = F('a' <= E & E<= 'z') -'a' + 26;  %lower case
F('0'<= E & E <= '9') = F('0'<= E & E <= '9') -'0' + 52;  %digits
F( E == '+') = 62;
F( E == '/') = 63;
F( E == '=') = 0;

D=zeros(1,numel(E)*3*8/4);

for k=1:numel(E);
    D(6*(k-1)+1 + (0:5)) = dec2bin(F(k),6)-'0';
end

if E(end) == '=';
    D(end-7:end) = [];
    if E(end-1) == '=';
        D(end-7:end) = [];
    end
end
end

function E = b64encode(D)
assert(mod(numel(D),8)==0,'flawed byte code');
N=0;
while mod(numel(D),6) ~= 0;
    D = [D,zeros(1,8)];
    N = N+1;
end
dict = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';

E=zeros(1,numel(D)/6)+'=';
for k=0:numel(E)-N-1;
    E(k+1) = dict(bin2dec( [D(6*k+(1:6))+'0',''] ) + 1);
end

E = [E,''];
end

function [B,T,O] = reduce_greedy(N)
% reduce greedily
NM = nomographic_magnitude(N);
B = N; %current best
M = N;
T = nnz(N); %current number of filled squares
O = T;

for r=1:2;  %how many repetitions
    I = find(B);
    for k=1:numel(I);
        M = B;
        M( I(k) ) = 0;
        %check whether we have a valid solution
        if all(NM == nomographic_magnitude(M))
            if T > nnz(M); %did we actually reduce the number of filled squares?
                B = M;
                T = nnz(M);
            end
        end
    end
end

%% main file
string_in = fileread('nonograms_b64.txt');
string_out = string_in;
tic
total_new = 0;  %total number of black squares
total_old = 0;
M = 50000;
for k=1:M;
    disp(k/M); %display the progress
    line = string_in(45*(k-1)+(1:44));
    decoded = b64decode(line);
    nonogram = reshape(decoded,16,[]) ;%store nonogram as a matrix
    [B,T,O] = reduce_greedy(nonogram);
    disp([nnz(B),nnz(nonogram)])
    total_new = total_new + T;
    total_old = total_old + O;
    string_in(45*(k-1)+(1:44)) = b64encode(B(:).');
end
toc
F = fopen('nonograms_b64_out.txt','w');
fprintf(F,string_out);
%%
disp([total_new,total_old])


text:
Find the syncopation
Given an input of a string consisting entirely of qs representing quarter
notes and es representing eighth notes, output the indices of the quarter
notes that are syncopated.
Syncopation is complex, but for
the purposes of this challenge, our definition of "syncopated" will be very
simple: a quarter note that starts on the "off-beat"—that is, the beats counted
as "and" in n/4 time.
This may alternatively be defined as any quarter note that is preceded by an
odd number of eighth notes. For example, the notes marked with * below are considered syncopated, and their indices are also shown:
eqqeqqeqqe
 **    **
 12    78
Output: 1 2 7 8

The input will always consist of a whole number of measures in 4/4 time (a
quarter note is a quarter of a measure, and an eighth note is an eighth of a
measure). (The input will also never be empty.) Output can either be a single string with elements separated by any delimiter that does not contain numbers or an array/list/etc. The output may be 1-based (i.e. the first index is 1 instead of 0) if you wish, and it may also be in any numeric base (unary, decimal, etc.).
Since this is code-golf, the shortest code in bytes wins.
Test cases:
In                        Out
-----------------------------------------------
eqqqe                     1 2 3
qeqeq                     2
qqqeqqeeeeqeqeqeqqeqqeqq  4 5 10 14 19 20
eeeeeqeeqeeqqqqeqeqeeqe   5 8 11 12 13 14 18 21
qqqq                      <none>
eeeeeeee                  <none>

Can output be 1-based?

Could you do a worked example to show how the indices work?

@LuisMendo Sure, if it makes your code shorter.

@PeterTaylor Okay, is something like that what you were thinking of?

Can the input be a string including the quote signs? 'eqqqe' instead of eqqqe

@LuisMendo No, it has to be exactly the strings specified in the test cases.

Ah, so it's index in the string and not in the score.

Jelly, 12 9 bytes
=“e”µ<^\O

As a program, the above code requires quotes around the input. Since that is not allowed, this is a function submission. The output is 1-based. Try it online!
How it works
=“e”µ<^\O    Monadic link. Argument: s (string)

=“e”         Check each character for equality with 'e'. Yields a Boolean array.
    µ        Start a new, monadic chain.
      ^\     Compute the array of partial reductions by XOR, i. e., the parities
             of all prefixes of the Boolean array.
     <       Check if the Booleans are strictly smaller than the parities.
             A truthy outcome indicates an off-beat quarter note.
        O    Yield all indices of 1's.

Update
The above code doesn't work anymore in the latest version of Jelly, since we need a character e, but “e” yields a string. Fixing that saves a byte, for a total of 8 bytes.
=”eµ<^\O

This works as a full program. Try it online!

Ruby, 46
i=e=0
gets.bytes{|n|e^=n
e&4|n>114&&p(i)
i+=1}

Input to stdin. Output to stdout, newline separated.
Commented
i=e=0               #i keeps index, e keeps track of 8ths.
gets.bytes{|n|      #iterate through bytes in the input
e^=n                #xor e with input. We're interested in the 4's bit, which is only affected by ascii e, not ascii q
e&4|n>114&&p(i)     #e&4 evaluates to 4 or 0. OR with n and if the value is greater than ascii code for q, print index
i+=1}               #increment index

JavaScript ES7, 50 48 bytes
Pretty short for JS, if you ask me. [for...of] syntax, basically combined map and filter, comes in handy for this challenge.
s=>[for(c of(i=f=0,s))if(++i&&c>'e'?f%2:f++&0)i]

Defines an anonymous function that outputs a 1-indexed array.
Test snippet
This uses an ungolfed, un-ES7'd version of the code.

a = function(s) {   // Create a function a that takes in a parameter s and does these things:
  var r = [],       // Set variable r to an empty array,
  i = 0, f = 0;     // i to 0, and f to 0.
  for(c of s) {     // For each character c in s:
    i++;            //  Increment i by 1.
    if(             //  If
      c == 'q' ?    //   if c == 'q',
      f%2 === 1 :   //    f is even; otherwise,
      f++ && false) //    increment f and don't execute this:
      r.push(i);    //   Add i to the end of r.
  } return r;       // Return r.
}
<input type="text" value="eqqqe" id=O />
<button onclick="P.innerHTML='['+a(O.value)+']'">Try it</button>

Very good explanation! And also a great example of how to use ES7's new [For...of]

So, do we need a new question, "Tips for Golfing in ECMAScript 7"?

@Neil I tried updating the ES6 post to ES6/7, but the OP rolled back the edit. In the meantime, there is this: http://codegolf.stackexchange.com/a/61489/42545

MATL, 12 14 16 bytes
j101=tYs2\<f

Thanks to Dennis for removing 2 bytes (and for hosting MATL in his awesome online platform!)
This uses current version (9.3.0) of the language/compiler.
Input and output are through stdin and stdout. The result is 1-based.
Example:
>> matl j101=tYs2\<f
> eeeeeqeeqeeqqqqeqeqeeqe
6  9 12 13 14 15 19 22

Or try it online!
Explanation
j             % input string
101=          % vector that equals 1 at 'e' characters and 0 otherwise
t             % duplicate
Ys2\          % cumulative sum modulo 2
<             % detect where first vector is 0 and second is 1
f             % find (1-based) indices of nonzero values

J, 20 19 17 bytes
=&'e'(I.@:<~:/\@)

Thanks to randomra for saving a byte, and to Dennis for saving two.
This is an unnamed monadic verb, used as follows:
  f =: =&'e'(I.@:<~:/\@)
  f 'eqqqe'
1 2 3

Try it here.
Explanation
=&'e'(I.@:<~:/\@)
=&'e'               Replace every 'e' with 1, other chars with 0
     (         @)   Apply the verb in parentheses to the resulting 0-1 vector
           ~:/\     Cumulative reduce with XOR (parity of 'e'-chars to the left)
          <         Element-wise less-than with original vector
      I.@:          Positions of 1s in that vector

GNU grep, 3+17=20 3 + 15 = 18 bytes
The program requires the options boP.
The code is
q(?!(q|eq*e)*$)

Save it as synco, then run as grep -boPf synco.
The output separator is :q followed by a newline. E.g. the output for eqqqe is
1:q
2:q
3:q

The meanings of the flags are:

P: Use PCRE regexes.
o: This means to print only the part of the line that matches the regular expression, but that's not why it's important. o is used because it has the effect of allowing multiple matches per line.
b: Print the offset in bytes of the beginning of each match from the beginning of the file.

The pattern checks that there is not an even number of eighth notes after a quarter note.

Does grep qualify as a language in its own right?  Regardless, +1 for a great answer

@DigitalTrauma I don't see why not... It can use PCRE regexes, so it should be Turing-complete at least, and can execute code from a file as shown here.

I was under the impression that PCRE is not proven to be Turing complete.  Regardless, your expression meets the requirement, so I'm OK with it, but there may be others with complaints on theoretical grounds.

@DigitalTrauma Huh, seems I was deluded about the Turing-completeness thing.

Python 2, 94 85 79 75 66 bytes
EDIT: Thanks Doorknob and Alex A.
EDIT: Thanks Alex A.
EDIT: Now using input() so the input must be a string with the quotes.
EDIT: Thanks Zgarb for recommending me to use enumerate.
Simply counts number of e's and if q, check if e count is odd, then print index.
e=0
for j,k in enumerate(input()):
 if"q">k:e+=1
 elif e%2:print j

Try it here

You can replace the second if ... with just an else to save 8 bytes.

You can also remove the space after print for 1 byte

I think you can change the else: if e%2: to just elif e%2:.

You can save one more byte by checking i[j]<"q" rather than i[j]=="e".

@feersum yes, unless you put the input as a string with quotes. Please see the ideone link.

@TanMath I asked Doorknob because it would save me 2 bytes to take an input with quotes. But it can't be done

Haskell, 58 51 bytes
f x=[i|(i,'q')<-zip[0..]x,odd$sum[1|'e'<-take i x]]

Usage example: f "eeeeeqeeqeeqqqqeqeqeeqe" -> [5,8,11,12,13,14,18,21].
Go through the list and output the current index i for every char 'q' if there's an odd number of 'e's before it.

APL (Dyalog Classic), 12 bytes
(⍸~×≠\)'e'∘=

Try it online!
Outputs 1-indexed.
Explanation:
       'e'∘=    ⍝ Map each element to whether it is equal to 'e'
(     )         ⍝ Then apply the train
  ~             ⍝ Not the array into indexes of 'p'
   ×            ⍝ Multiply this by
    ≠\          ⍝ The cumulative reduction by inequality
 ⍸              ⍝ And get the indexes of the ones in the array

It's generally recommended to use Unicode/Extended over Classic.

Python 3, 109 95 80 90 88 76 68 67 66 64 bytes
Counts the number of qs and es and adds the index of the current q if the number of preceding es is odd.
Edit: Now it prints a list of the indices of s that are q and have an odd number of es preceding them. Eight bytes saved thanks to Doorknob and two more thanks to feersum.
lambda s:[x for x,m in enumerate(s)if("e"<m)*s[:x].count("e")%2]

Ungolfed:
def f(s):
    c = []
    for index, item in enumerate(s):
        if item == "q":
            if s[:index].count("e")%2 == 1:
                c.append(index)
    return c

Couldn't you make this a lambda to make the input and print statements unnecessary?

It should be shorter to use enumerate rather than range(len(....

JavaScript ES6, 63 60 58 bytes
x=>[...x].map((e,i)=>e>'e'?n%2&&a.push(i):n++,a=[],n=0)&&a

Anonymous function that outputs an array. Thanks to user81655 for saving two bytes. Here is an ungolfed version that uses better supported syntax.

f=function(x) {
  a=[] // Indeces of syncopated notes
  n=0 // Number of e's encountered so far
  x.split('').map(function(e,i) { // For each letter...
    e>'e'? // If the letter is q...
      n%2&& // ...and the number of e's is odd...
        a.push(i): // ...add the current index to the array
      n++ // Otherwise, it is e so increment the counter
  })
  return a
}

run=function(){document.getElementById('output').textContent=f(document.getElementById('input').value)};document.getElementById('run').onclick=run;run()
<input type="text" id="input" value="qqqeqqeeeeqeqeqeqqeqqeqq" /><button id="run">Run</button>

<samp id="output"></samp>

Minkolang 0.15, 28 bytes
(o"q"=7&z1+$z8!z2%,2&iN$I$).

Try it here.
Explanation
(                        Open while loop
 o                       Read in character from input
  "q"                    Push the character "q"
     =                   1 if the top two items on stack are equal, 0 otherwise
      7&                 Pop and jump 7 spaces if truthy

        z                Push register value on stack
         1+              Add one
           $z            Pop top of stack and store in register
             8!          Jump eight spaces

        z                Push register value on stack
         2%              Modulo by 2
           ,             boolean not
            2&           Pop and jump two spaces if truthy
              i          Push loop counter
               N         Output as number

                $I       Push length of input
                  $).    Close while loop when top of stack is 0 and stop.

C (function), 65
Thanks to @Dennis for the extra golfing!
i,n;f(char*m){for(i=n=0;*m;i++)*m++&4?++n:n%2?printf("%d ",i):0;}

I think i,n;f(char*m){for(i=n=0;*m;m++,i++)*m&4?++n:n%2?printf("%d ",i):0;} should work.

Mathematica, 76 bytes
Flatten[Range[#+1,#2-1]&@@@StringPosition[#,"e"~~"q"..~~"e",Overlaps->1<0]]&

Something interesting I noticed. All of the syncopated parts are of form eqqq..qqe, so I just detect those and give the indices of the qs.

Japt, 29 23 21 bytes
Not non-competing anymore!
0+U ¬®¥'e} å^ ä© m© f

Try it online!
How it works
         // Implicit: U = input string, e.g.    "eqqeqeq"
0+U      // Add a 0 to the beginning.           "0eqqeqeq"
¬        // Split into chars.                   ['0,'e,'q,'q,'e,'q,'e,'q]
®¥'e}    // Map each item X to (X == 'e).       [F, T, F, F, T, F, T, F]
å^       // Cumulative reduce by XOR'ing.       [0, 1, 1, 1, 0, 0, 1, 1]
ä©       // Map each consecutive pair with &&.  [0, 1, 1, 0, 0, 0, 1]
m©       // Map each item with &&. This performs (item && index):
         //                                     [0, 1, 2, 0, 0, 0, 6]
f        // Filter out the falsy items.         [   1, 2,          6]
         // Implicit output                     [1,2,6]

Non-competing version, 18 bytes
U¬m¥'e å^ ä©0 m© f

Try it online!

Befunge, 43 bytes
:~:0\`#@_5%2/:99p1++\>2%#<9#\9#.g#:*#\_\1+\

Try it online!
Explanation
We start with two implicit zeros on the stack: the note number, and a beat count.
:               Make a duplicate of the beat count.
~               Read a character from stdin.
:0\`#@_         Exit if it's less than zero (i.e. end-of-file).
5%2/            Take the ASCII value mod 5, div 2, translating q to 1 and e to 0.
:99p            Save a copy in memory for later use.
1+              Add 1, so q maps to 2 and e to 1.
+               Then add that number to our beat count.
\               Get the original beat count that we duplicated at the start.
2%              Mod 2 to check if it's an off-beat.
99g*            Multiply with the previously saved note number (1 for q, 0 for e).
_               Essentially testing if it's a quarter note on an off-beat.
       \.:\     If true, we go turn back left, get the beat count, and output it.
         >2     Then push 2 onto the stack, and turn right again.
2%              That 2 modulo 2 is just zero.
99g*            Then multiplied by the saved note number is still zero.
_               And thus we branch right on the second pass.
\1+\            Finally we increment the note number and wrap around to the start again.

Japt, 11 bytes
ðÈø¬?Tu:!°T

Try it


text:
Generate Programs in Increasing size
In this challenge, you will write a program which outputs a program which is the double the length of the original program. The outputted program should output a new program a program double its length.
Examples
If my program is a:
< a
> aa

< aa
> aaaa

< aaaa
> aaaaaaaa

Rules

No quine built-ins
The original program must be at least one byte
The sequence should theoretically work infinitely
Your program is not allowed to read from anything (file, stdio)

Your score is the size of the original program.

How about accessing the file by reading itself/accessing the place where the code is contained?

@CᴏɴᴏʀO'Bʀɪᴇɴ that's not allowed as that would violate  rules I believe.

It's not a quine built-in. e.g. document.getElementById("code") or something.

@CᴏɴᴏʀO'Bʀɪᴇɴ oh whoops, I left out a few words :| I meant to say "that would violate our quine rules, I believe"

Oh, I see. I didn't think this was a quine challenge.

@Doᴡɴɢᴏᴀᴛ the quine rules are recommended by the tag wiki but don't apply automatically

I accidentally wrote a program that did this while working on the growing quine challenge

Related: http://codegolf.stackexchange.com/questions/21831/program-that-creates-larger-versions-of-itself-quine-variant

Related. Related. Related.

CJam, 10 bytes
{"_~"+_}_~

Test it here.
Explanation
{"_~" e# Generalised quine framework, leaves the block and the string "_~"
      e# on the stack.
+     e# Prepend the block to the string.
_     e# Duplicate the resulting array.
}_~

GolfScript isn't dead! Ilmari has an answer to a similar question that does this in exactly 10 bytes.

JavaScript, 62 61 37 bytes

Thanks to @Doᴡɴɢᴏᴀᴛ for the help!

Original [37 bytes]:
f=_=>'f='+'_'.repeat((10+f).length)+f

Child [74 bytes]:
f=______________________________________=>'f='+'_'.repeat((10+f).length)+f

Grandchild [148 bytes]:
f=________________________________________________________________________________________________________________=>'f='+'_'.repeat((10+f).length)+f

Alternate (with printing to console, and as a full program):
Original [61 bytes]:
f=_=>console.log(`f=${'_'.repeat((0+f).length+5)+f};f()`);f()

Child [122 bytes]:
f=______________________________________________________________=>console.log(`f=${'_'.repeat((0+f).length+5)+f};f()`);f()

Grandchild [244 bytes]:
f=________________________________________________________________________________________________________________________________________________________________________________________=>console.log(`f=${'_'.repeat((0+f).length+5)+f};f()`);f()

How it works!
1.   f=_=>   Define function f as console.log(...)
2.   ;f()   Run function f.
3.   (in function f)

console.log(...)   Print the following:

f=   literal text "f="
${'_'.repeat((0+f).length+5)   "_" repeated for the length of f, altered to account for characters not included in the stringification of f
+f}   The stringification of function f
;f()   literal text ";f()"

Notes

console.log is necessary instead of alert because alert doesn't seem to play well with really long strings (at least on my machine/browser configuration)
The _'s are inserted into the name of the (unused) parameter of function f, to ensure that they are included in the stringification of f.
Main improvement (aside from getting rid of the console.log) of the first solution over the second: adding 10 to the function instead of 0 to cast it to string makes it one byte longer, eliminating the need to add 1 to the length afterwards, saving a byte.

0+f should also work to cast the function to a string

48 bytes: (f=_=>\(f=${'_'.repeat((0+f).length+5)+f})()`)()`

@Doᴡɴɢᴏᴀᴛ Forgot that returning the result is usually acceptable. Will update.

@Doᴡɴɢᴏᴀᴛ Actually, since writing answers as functions is generally accepted, does the solution even have to call the function?

sure, you could do

Actually, I'm pretty sure the solution has to call the function because the quine function can't output anything by itself (without the call).

Minkolang 0.15, 19 14 bytes
"66*2-rIDdr$O.

Original, child, grandchild.
Explanation
"66*2-      $O.    Standard quine formulation

      r            Reverse stack
       I           Push length of stack
        D          Pop n and duplicate top of stack n times
         d         Duplicate top of stack
          r        Reverse stack

What the bit in between rs does is duplicate the ending period enough times to fulfill the doubling criterion. . is the "stop program" character, so the many periods at the end do nothing except be there.

CJam, 12 bytes
{"_~"1$1$}_~

When run, this will print
{"_~"1$1$}_~{"_~"1$1$}_~

which, in turn, will print
{"_~"1$1$}_~{"_~"1$1$}_~{"_~"1$1$}_~{"_~"1$1$}_~

and so on.
Try it online!

Python 3, 51 bytes
x=r"print('x=r\"'+x+'\"'+';exec(x*2)');";exec(x*2)

This includes a trailing newline.
Which outputs:
x=r"print('x=r\"'+x+'\"'+';exec(x*2)');";exec(x*2)
x=r"print('x=r\"'+x+'\"'+';exec(x*2)');";exec(x*2)

GolfScript, 11 bytes
{: ".~"]}.~

Try it online!
How the source code works
{: ".~"]}.~

{       }    Define and push a code block.
         .~  Push a copy and execute it.
 :           Save the code block in the space character.
             Every subsequent space will now execute the code block.
   ".~"      Push that string.
       ]     Wrap the entire stack in an array.

If the above source code is executed once, the stack will end up as
["" {: ".~"]} ".~"]

where the empty string at the beginning corresponds to the initial state of the stack (empty input).
Two copies of the source code would leave a final state of
[["" {: ".~"]} ".~"] {: ".~"]} ".~"]

and so on.
What happens next
After executing the source code, the interpreter does the following:

It wraps the entire stack in an array, and pushes that array on the stack.
For a single copy of the source code, the stack now contains
["" {: ".~"]} ".~"] [["" {: ".~"]} ".~"]]

It executed puts with the intention of printing the wrapped stack, followed by a linefeed.
puts is defined as {print n print}, so it does the following.

print prints the wrapped up copy of the stack without inspecting it (i.e., without converting it to its string representation). This sends
{: ".~"]}.~

to STDOUT and pops the stack copy from the top of the stack.
The stack now contains
["" {: ".~"]} ".~"]

 executes the code block we defined previously.
: begins by saving ["" {: ".~"]} ".~"] in the space character, then ".~" pushes itself and ] wraps the stack in an array.
n pushes a string consisting of a single linefeed.
The stack now contains
[["" {: ".~"]} ".~"] ".~"] "\n"

 is executed once more. However, it was redefined when we called it for the first time and now contains an array, not a code block.
In fact, it pushes ["" {: ".~"]} ".~"], leaving the stack as
[["" {: ".~"]} ".~"] ".~"] "\n" ["" {: ".~"]} ".~"]

Finally, print prints the topmost stack item without inspecting it, sending
{: ".~"]}.~

to STDOUT.

, 26 chars / 36 bytes
⟮ô`\u27ee⦃ᶈ0}\u27ef
`ď2)⟯

Try it here (Firefox only).
Note that there is a trailing newline.
Explanation
Standard quine: ⟮ⒸⅩ222+ᶈ0
Modifications:

Use ô function to output the quines all results instead last result (as done using implicit output)
Use \u27ee⦃ᶈ0}\u27ef\n and close copy block to prevent conflicts with later copy blocks.
Use ď2 to repeat string twice.