title: Maximally extend integer intervals

text:
# Question
Title: Maximally extend integer intervals
Suppose you are given a set of **non-intersecting** intervals of integers `[a1,b1],[a2,b2],[a3,b3],...,[aN,bN]`. (Where `[a,b]` is the set of integers greater than or equal to `a` and less than or equal to `b`.)

The interval at index `X` covers `bX - aX + 1` values. We'll call this number `cX`.

Given that each interval can either be...

* unchanged (stays as `[aX,bX]`),
* extended to the right towards the `+` side of number the line by `cX` (becoming `[aX,bX + cX]`),
* or extended to the left towards the `-` side of number the line by `cX` (becoming `[aX - cX,bX]`),

what is the maximum number of values that can be covered by the union of all the updated intervals, given that they are still all non-intersecting?

Write a function or program that takes a string of the form `[a1,b1],[a2,b2],[a3,b3],...,[aN,bN]` and computes this maximum. If writing a function, return the value. If writing a full program, use stdin for input and print the value to stdout (or use closest alternatives).

You may assume all values are well within normal signed 32-bit integer limits and that `aX` is less than or equal to `bX` for all indices `X`. The intervals may be in any order, they are not necessarily always increasing. They must be given as a string in the format above. The string may be empty, in which case the answer will be 0.

The shortest submission in bytes wins.

### Example

If the input were `[-3,0],[1,2],[4,9]` the output would be 22. The middle interval has no room to expand either way so it must remain unchanged. The left and right intervals can both be extended to `[-7,0]` and `[4,15]` respectively. The union of `[-7,0]` and `[1,2]` and `[4,15]` contains all the values from -7 to 15, except 3. That's 22 values.

# Answer
## Haskell, 145 bytes

```
import Data.List
x=maximum.map length.filter(nub>>=(==)).map concat.sequence.map(\[a,b]->[[2*a-b-1..b],[a..b],[a..2*b-a+1]]).read.('[':).(++"]")

```

Sample runs:

```
λ: x ""
0

λ: x "[5,6]"
4

λ: x "[-3,0],[1,2],[4,9]"
22

```
> 4 votes

# Answer
# R, ~~282~~ ~~278~~ ~~269~~ 247

This got big really quickly dealing with the string input. I suspect I can golf this better, but have run out of time at the moment.

```
f=function(s){i=matrix(strtoi(strsplit(gsub('[^0-9,-]','',s),',')[[1]]),nrow=2);l=0;if((a<-length(b<-order(i[1,])))>0){if(a>1)i=i[,b];l=diff(i[,1:a])+1;x=c(t(i));for(n in 1:a)if(n==1|n==a|x[n]-l[n]>x[n+a-1]|x[n+a]+l[n]<x[n+1])l[n]=l[n]*2;};sum(l)}

```

Essentially the idea is

* Take in the string and turn it into a 2 row matrix
* Make sure it is in the right order
* Work out the differences for each column
* Double the first and last differences
* Double the middle differences if they have a gap to the previous or next that is large enough
* Return the sum of the differences

Edit: realized I miscounted the chars originally, then rearranged a few things to shave a few.
> 1 votes

---
Tags: code-golf, set-theory
---


title: Crafting Canonically Cöcher Crosswords

text:
# Question
Title: Crafting Canonically Cöcher Crosswords
# The Setup

Most of us are familiar with crossword numbering, which follows three basic rules:

1. in a character grid consisting of blacks and whites (see below), any maximal contiguous horizontal or vertical chain of whites with length ≥ 2 is considered a word
2. any white at the leftmost end of a horizontal word and/or at the topmost end of a vertical word is called a "starter"
3. starters are assigned numbers (sequential integers starting with 1) scanning through the grid in standard English reading order (starting at the top left of the grid, scanning right-fast, down-slow to the bottom right of the grid)

A "crossword" generally refers to any *n*-by-*n* square grid of blacks and whites, with *n* ≥ 2, containing at least one black and at least one word, and containing no whites that do not belong to at least one word.

Some additional properties that a crossword may or may not possess:

* a crossword is called **singly connected** if every white in the grid can be connected to every other white in the grid by moving north, east, south, and west (not diagonally) along a path consisting entirely of whites
* a crossword is called **proper** if every white belongs to exactly two words (one horizontal, one vertical)
* a crossword is called **symmetric** if for all *x* = 1..*n*, *y* = 1..*n*, the grid cell at (*x*,*y*) is a white if and only if the grid cell at (*n*+1-*x*,*n*+1-*y*) is a white, given 1-based indexing

Most run-of-the-mill cryptic crosswords are singly-connected and symmetric, but not proper. Many newspaper crosswords are proper, singly-connected, and symmetric. The figure below also shows a proper, singly-connected, symmetric crossword.

```
                 Crossword
       w/o #s              w/ #s (mod 10)
  ##################    12##################
    #   ######  ####    3 45#678######90####
        #       ####    1   2   #34567  ####
      ###     ######    8     ###9    ######
##       ####   ####    ##0   123####456####
#   #    ##       ##    #7  #8   ##90   12##
   ##    ##  #          3  ##4   ##5 #6   78
  ####   #####          9 ####0  #####1
#   ##     ####   ##    #234##5  67####8  ##
#      #   ##    ###    #9  01 #2  ##34  ###
###    ##   #      #    ###5   ##6 7#8   90#
##   ####     ##   #    ##1  ####2  3 ##4  #
      #####   ####      56   7#####8  ####90
      #  ##    ##       1     #23##4  5##6
##       ##    #   #    ##7   8  ##9   #0  #
####   ####       ##    ####1  ####2   3  ##
######     ###          ######45678###9   01
####       #            ####23     #45
####  ######   #        ####6 ######7  #8
##################      ##################9

```

# The Problem

...other than finding a crossword puzzle challenge that hasn't already been done. :P

Recall the crossword numbering challenge from days of yore, which accepts a crossword as input and produces clue numbering as output. Here we consider its younger (and significantly harder) cousin by reversing input and output:

*Given a series of across/down clue numbers, generate a crossword puzzle whose numbering (per the canonical rules) yields these clue numbers.*

For example, consider the clue numbers as input:

**Across** `3,5,6,7,8,9` **Down** `1,2,3,4,5,A`

Two crosswords with compliant numbering are:

```
          A                           B
         6x6                         7x7
 w/o #s       w/ #s          w/o #s        w/ #s
 ______       ______        _______       _______
|## # #|     |##1#2#|      |#######|     |#######|
|#     |     |#3   4|      |# ## ##|     |#1##2##|
|  ##  |     |5 ##6 |      |# #  # |     |# #3 #4|
|  ##  |     |7 ##8 |      |  #  # |     |5 #6 # |
|     #|     |9  A #|      | #  #  |     | #7 #8 |
|# # ##|     |# # ##|      |  ## ##|     |9 ##A##|
 ¯¯¯¯¯¯       ¯¯¯¯¯¯       |#### ##|     |#### ##|
                            ¯¯¯¯¯¯¯       ¯¯¯¯¯¯¯

```

Solution **A** is singly-connected and symmetric, while **B** is neither. Solution **A** is also notably more compact, having only 14 blacks, while solution **B** has 29 blacks.

Note that you do not need to worry about what letters could/would go into any whites. This challenge is purely geometric in nature.

There are of course many trivial ways of generating compliant crosswords, which takes us to the interesting matter of...

# Scoring

This 600-textline file contains 300 sets of across/down clue numbers for crosswords in the format

> \[across clue numbers for set 1, separated by spaces\]
> \[down clue numbers for set 1, separated by spaces\]
> \[across clue numbers for set 2, separated by spaces\]
> \[down clue numbers for set 2, separated by spaces\]
>
> ...
>
> \[across clue numbers for set 300, separated by spaces\]
> \[down clue numbers for set 300, separated by spaces\]

Your objective is to write a program that generates a valid crossword for each set of across/down clue numbers and computes the resulting number of blacks.

The program should produce all 300 crosswords in 30 minutes or less running on a modern computer.

By setting a constant in the program or passing a command line argument, the program should be able to output the crossword grid (solution) for the *k*th input set given *k* ∈ 1..300, and you should display representative output (the black/white grid) for at least *k* = 1 and *k* = 300 along with your answer. The output can be text- or graphics-based, with or without clue numbers shown (preferably *with*, mod 36 for text-based graphics), and with any embellishments you desire. (This is simply for validation and showmanship.)

The output should also indicate whether the crossword is proper, singly-connected, and/or symmetric.

Your program's score is the sum total number of blacks over all 300 solutions. **The program that produces the lowest total number of blacks is the winner.**

## per-crossword Bonuses

For any of the 300 crosswords (solutions) generated by your program:

* if a crossword is **proper**, multiply its black count by **0.6**
* if a crossword is **singly connected**, multiply its black count by **0.85**
* if a crossword is **symmetric**, multiply its black count by **0.75**
* if **any two** of the above conditions apply for a crossword, multiply its black count by **0.4**
* if **all three** of the above conditions apply for a crossword, multiply its black count by **0.25**

You may only claim one bonus per crossword.

The score for each crossword should be rounded up to the nearest integer.

Note that all of the input sets in the problem correspond to randomly-generated small(ish) singly-connected, proper, symmetric crosswords, hence I guarantee the existence of at least one such a solution.

Feel free to raise any questions or concerns in the comments section.

Happy crosswording. :)

# Answer
> 2 votes
## Python, total score 127,634(!)

This was a good excercise in humility. The score claimed above is using a fairly naive construction algorithm. I also tried implementing a slightly optimized brute force search, but while this managed to solve a few of the smaller crosswords in the 1-100 range (13x13 or less) it struggled with most and had no chance with the larger ones.

## Crossword class

Nothing fancy here...

```
import itertools
import math
import copy
import sys

def read_crosswords(filename):
  crosswords = []
  with open(filename, 'r') as f:
    for across, down in zip(f, f):
      alist = list(map(int, across.rstrip().split()))
      dlist = list(map(int, down.rstrip().split()))
      crosswords.append(XWord(alist, dlist))
  return crosswords

def solve_crosswords(filename, solver, display=()):
  crosswords = read_crosswords(filename)
  total_score = 0
  for x, i in zip(crosswords, itertools.count(1)):
    print("Crossword {0}... ".format(i), end="")
    sys.stdout.flush()
    assert(solver(x))
    score = x.score(); details = ["score = {0}".format(score)]
    if x.is_symmetric(): details.append("symmetric")
    if x.is_proper(): details.append("proper")
    if x.is_connected(): details.append("connected")
    print("done! ({0})".format(", ".join(details)))
    if i in display: x.print_grid()
    total_score += score
  print("Total score: {0}".format(total_score))
  return crosswords

def flood_fill(grid, x, y, colorA, colorB):
  if grid[x][y] != colorA: return
  grid[x][y] = colorB
  flood_fill(grid, x-1, y, colorA, colorB)
  flood_fill(grid, x+1, y, colorA, colorB)
  flood_fill(grid, x, y-1, colorA, colorB)
  flood_fill(grid, x, y+1, colorA, colorB)

class XWord:

  B,W,U = range(3)

  def __init__(self, across, down):
    self.grid = []                                 # grid (2D array with black border)
    self.n = 0                                     # grid size (excluding border)
    self.num_clues = max(across + down)            # number of clues
    self.across = [(i+1) in across for i in range(self.num_clues)] # acrossness bool array
    self.down = [(i+1) in down for i in range(self.num_clues)]     # downness bool array

  def print_grid(self, numbers=True):
    """Print the grid."""
    i = 1
    for y in range(1,self.n+1):
      for x in range(1,self.n+1):
        if self.grid[x][y] == XWord.B: print("#",end="")
        elif self.grid[x][y] == XWord.W:
          across = (self.grid[x-1][y] == XWord.B) and (self.grid[x+1][y] == XWord.W)
          down = (self.grid[x][y-1] == XWord.B) and (self.grid[x][y+1] == XWord.W)
          if numbers and (across or down):
            print("{0}".format(i % 10), end="")
            i += 1
          else: print(" ", end="")
        else: print("?", end="")
      print()

  def is_symmetric(self):
    """Whether the grid is symmetric."""
    for y in range(1,self.n+1):
      for x in range(1,self.n+1):
        if self.grid[self.n+1-x][self.n+1-y] != self.grid[x][y]:
          return False
    return True

  def is_proper(self):
    """Whether the grid is proper."""
    for y in range(1,self.n+1):
      for x in range(1,self.n+1):
        if self.grid[x][y] == XWord.W:
          if not ((self.grid[x-1][y] == XWord.W or self.grid[x-1][y] == XWord.W) or
                  (self.grid[x][y-1] == XWord.W or self.grid[x][y+1] == XWord.W)):
            return False
    return True

  def is_connected(self):
    """Whether the grid is connected."""
    grid = copy.deepcopy(self.grid); filled = False
    for y in range(1,self.n+1):
      for x in range(1,self.n+1):
        if grid[x][y] == XWord.W:
          if not filled:
            flood_fill(grid, x, y, XWord.W, XWord.B)
            filled = True
          else:
            return False
    return True

  def score(self):
    """The grid score."""
    blacks = 0
    for y in range(1,self.n+1):
      for x in range(1,self.n+1):
        if self.grid[x][y] == XWord.U:
          raise Exception("Incomplete grid!")
        elif self.grid[x][y] == XWord.B:
          blacks += 1

    symmetric = self.is_symmetric()
    proper = self.is_proper()
    connected = self.is_connected()

    if (symmetric and proper and connected): multiplier = 0.25
    elif (symmetric and (proper or connected) or proper and connected): multiplier = 0.4
    elif proper: multiplier = 0.6
    elif symmetric: multiplier = 0.75
    elif connected: multiplier = 0.85
    else: multiplier = 1.0

    return int(math.ceil(float(blacks) * multiplier))

```

## Naive solver

This generates a height two sequence, splits it into sections and wraps it round to fill the smallest possible square. Across clues are extended as far as possible to minimize blacks, but other than that there's not much cleverness. The solutions are never connected or proper and in practice never symmetric.

```
class XWord:

  def simple_solver(self):
    """Naive solver. Converts to a height 2 sequence and wraps round."""

    # generate a string sequence that we'll expand later
    # a=start across, b=start both, c=continue across, d=start down, _=optional space,  =space
    seq = []
    for a,d in zip(self.across, self.down):
      if a:
        if len(seq) > 0:
          if seq[-1] in "ab": seq.append("c")
          seq.append(" ")
        seq.append("a" if not d else "b")
      else:
        if len(seq) > 0:
          if seq[-1] in "bd": seq.append("_")
        seq.append("d")
    if len(seq) > 0 and seq[-1] in "ab": seq.append("c")

    # fit sequence into a square with grid size 3n-1 for minimal n
    n = 0; rows = seq
    while len(rows) > n:
      n += 1; x = 0; rows = []
      while x < len(seq):
        if seq[x] in "_ ": x+=1
        y = min(x+3*n-1,len(seq))
        if seq[y-1] in "ab": y-= 1
        rows.append("".join(seq[x:y]).rstrip(" _"))
        x = y

    # generate grid
    self.n = 3*n-1
    self.grid = [[XWord.B for i in range(self.n+2)] for j in range(self.n+2)]
    y = 1
    for row in rows:
      x = 1; across = False
      for s in row:
        if s in "abcd" or across and s in "_": self.grid[x][y] = XWord.W
        if s in "bd": self.grid[x][y+1] = XWord.W
        if s in "ab": across = True
        x += 1
      for x in range(x,self.n+1):
        if across: self.grid[x][y] = XWord.W
      y += 3
    return True

```

This runs almost instantaneously and generates an amusingly high score.

```
>>> solve_crosswords('crossword.txt', XWord.simple_solver,[1,300])
Crossword 1... done! (score = 121)

1 2#3 4#5 6 7
 # # # # # # #
##############
8#9#01#2 #3
 # ## #### ###
##############
4 #56#7 #8 9 0
#### #### # #
##############
1#2#3 #4 #56
 # ######## ##
##############
7 8 9#0 #1 #2
 # # #########

Crossword 2... done! (score = 192)
Crossword 3... done! (score = 203)
...
Crossword 299... done! (score = 666)
Crossword 300... done! (score = 645)

1 2#3 4 5 6#7 8#90 1 2 3#45 6 7
 # # # # # # # ## # # # ## # # #
################################
8 9#0 1 2#34#5 #6 #7 #8 9#0 #1
 # # # # ## ########## # #### ##
################################
2 #34#56#7 #89 0 1#23#45#6 #7
#### ## ##### # # ## ## # ######
################################
89#0 #1 2#34#5 #6 #7 #8 9#0 #1 2
# #### # ## ########## # #### #
################################
3#4#56 7 8 9 0 1 2 3 4#56 7 8#9
 # ## # # # # # # # # ## # # ###
################################
0 #1 #2 #3 #4 #5 6#7 #8 9#0 1 2
############### # #### # # # # #
################################
3 4#5 6#78#90 1 2#3 #4 #5 #6 #7
 # # # ## ## # # ############# #
################################
8 9#0 1 2 3 4#5 #6 #78#9 0 1 2
 # # # # # # ######## # # # # ##
################################
3 #45#67#89#0 #12#34 5#6 #7 #8
 ### ## ## ##### ## # ##########
################################
9 #01 2 3 4#5 6#7 #8 #9 #0 #1 2
#### # # # # # #### ######## # #
################################
34 5#6 #7 #8
# # ############################

Total score: 127634

```

## Slow solver

The brute force solver traverses the grid square by square and decides at each point whether to start new clues, continue existing clues or block clues. Before continuing, it confirms that this choice is compatible with the current view of the grid. There are a number of other optimizations applied whenever we know that the grid is symmetricm, proper or connected.

* **Symmetric**: we apply all updates symmetrically and check halfway that half of the across clues and at least half of the overall clues have been processed.
* **Proper**: we check for properness whenver we update the grid.
* **Connected**: we disallow a completely black row.

Note that there's even a bit of overoptimisation: we currently disallow proper crosswords that begin with a black row, though strictly these are allowed (though I'm not sure they should be). Also, we allow the user to specify the maximum number of black squares to look for to speed up the search.

```
class XWord:

  def slow_solver(self, n, symmetric=False, proper=False, connected=False, max_blacks=None):
    """Brute force solver with some optimizations. Too slow for much more than 10x10."""

    def _slow_solve(x, y, alist, dlist, updates, all_black_row, max_blacks):
      found = True

      # Early exits
      if connected and x == 1:
        if all_black_row: return False
        else: all_black_row = True
      if symmetric and x == 1:
        if y == self.n // 2 + 1:
          self.across_halfway = self.across.count(True) - alist.count(True)
          if alist.count(True) < self.across_halfway: return False
        if y == (self.n + 1) // 2 + 1:
          if 2 * len(alist) > self.num_clues: return False
          if alist.count(True) != self.across_halfway: return False

      # Apply updates and detect more inconsistencies
      undo = []
      for (i,j,C) in updates:
        # update square
        if self.grid[i][j] == C:
          pass
        elif self.grid[i][j] == XWord.U:
          self.grid[i][j] = C
          if C == XWord.B: max_blacks -= 1
          undo.append((i,j))
        else:
          found = False # inconsistent
          break
        if proper and C == XWord.W:
          if self.grid[i-1][j] == XWord.B and self.grid[i+1][j] == XWord.B or \
             self.grid[i][j-1] == XWord.B and self.grid[i][j+1] == XWord.B:
             found = False
             break
        elif C == XWord.W:
          if self.grid[i-1][j] == XWord.B and self.grid[i+1][j] == XWord.B and \
             self.grid[i][j-1] == XWord.B and self.grid[i][j+1] == XWord.B:
             found = False # lone black square
             break
        # update mirror image
        if symmetric and (i != self.n+1-i or j != self.n+1-j):
          if self.grid[self.n+1-i][self.n+1-j] == C:
            pass
          elif self.grid[self.n+1-i][self.n+1-j] == XWord.U:
            self.grid[self.n+1-i][self.n+1-j] = C
            if C == XWord.B: max_blacks -= 1
            undo.append((self.n+1-i,self.n+1-j))
          else:
            found = False
            break

      # Are we finished?
      if found:
        if y > self.n and len(alist) == 0: return True
        elif y > self.n or max_blacks < 0: found = False

      # Select next square type and recurse
      if found:
        nextx = x + 1; nexty = y
        if nextx > self.n: nextx = 1; nexty += 1
        found = len(alist) > 0 and _slow_solve(nextx, nexty, alist[1:], dlist[1:], self._start_clue_updates(x, y, alist[0], dlist[0]), False, max_blacks)
        found |= _slow_solve(nextx, nexty, alist, dlist, self._continue_clue_updates(x, y), False, max_blacks)
        found |= _slow_solve(nextx, nexty, alist, dlist, self._block_clue_updates(x, y), all_black_row, max_blacks)

      # Undo updates on error
      if not found:
        for (i,j) in undo:
          self.grid[i][j] = XWord.U

      return found

    # in future, this should try a few values of n until we get one that works.
    self.n = n
    self.grid = [[XWord.U if (0<i<self.n+1) and (0<j<self.n+1) else XWord.B for j in range(self.n+2)] for i in range(self.n+2)]
    if max_blacks is None:
      max_blacks = self.n * self.n - 2 * max(self.across.count(True), self.down.count(True))
    found = _slow_solve(1, 1, self.across, self.down, [], False, max_blacks)
    return found

  def _start_clue_updates(self, x, y, across, down):
    updates=[(x, y, XWord.W)]
    if across:
      updates.insert(0,(x-1, y, XWord.B))
      updates.append((x+1, y, XWord.W))
    elif self.grid[x-1][y] == XWord.B:
      updates.insert(0,(x+1, y, XWord.B))
    if down:
      updates.insert(0,(x, y-1, XWord.B))
      updates.append((x, y+1, XWord.W))
    elif self.grid[x][y-1] == XWord.B:
      updates.insert(0,(x, y+1, XWord.B))
    return updates

  def _continue_clue_updates(self, x, y):
    updates=[(x, y, XWord.W)]
    if self.grid[x-1][y] == XWord.B:
      updates.insert(0,(x+1, y, XWord.B))
      updates.append((x, y-1, XWord.W))
    elif self.grid[x][y-1] == XWord.B:
      updates.insert(0,(x, y+1, XWord.B))
      updates.append((x-1, y, XWord.W))
    return updates

  def _block_clue_updates(self, x, y):
    updates=[(x, y, XWord.B)]
    return updates

```

Unfortunately this is too slow to solve all but a few of the smaller crosswords in the puzzle file.

```
>>> xs = read_crosswords('crossword.txt')
>>> xs[0].slow_solver(13,True,True,True)
True
>>> xs[0].print_grid()
#12##########
3  4#56789###
0   1     ###
##2      ####
#3    #4 ####
#5    6  ####
#####7  #####
####8   9012#
####3 #4    #
####5 6    ##
###7       89
###0    #1
##########2 #
>>> xs[0].score()
18

```

---
Tags: code-challenge, geometry, optimization, crossword
---


# Question
Title: "Useful" self-modifying script for financial firm
True Story: Several years ago while interviewing at an investment advisory firm that managed over a billion dollars in client funds, I was asked a collection of reasonable and bizarre questions by a partner in the firm. An example of a reasonable question would be "What can go wrong with a linear fit?".

But then, things devolved....

Interviewer: "Have you ever written code that modifies itself?"

Job Candidate: "No, can't say that I have"

Interviewer: "We have one guy who writes programs that modify themselves, I think he uses awk"

Job Candidate: "Wow. That's pretty incredible. AWK? "

Now it is your turn to be that one guy that financial houses would kill to hire...

Challenge: Write a self-modifying script of some kind that performs a "useful financial function".

Rules:

1. Use a scripting language, not a language requiring compilation such as C or Java. Perl, Python and the like that will work from a #! are OK. Of course, heroes use awk, but awk is not a requirement.
2. Self-modifying means that the script modifies its own source code. The script must be reusable after it has modified itself. The script might also generate useful user output to STDOUT or some other interface.
3. The definition of "useful financial function" is left to the voters and can be as intriguing or dysfunctional as you prefer. If you need examples for inspiration, here are a few ideas: stock picking, stock trading, prediction and/or fitting, future value of account, Ponzi scheme generator, risk analysis of Nigerian email deals, salary bonus calculator for partners vs employees, etc.
4. Most upvotes wins.

EDIT: I agree with one participant who notes that it is not obvious how to read the current gawk script from within gawk. Here is a solution for Linux-based systems and other O/S that have a /proc filesystem.

```
#!/usr/bin/gawk -f
BEGIN {
pid = PROCINFO["pid"]
commfile = "/proc/"pid"/comm"
print "I will look here for the script file name: " commfile
print "Here is what is in that file:"
getline scriptfilename < commfile
print scriptfilename
print "Here is my script:"
while (getline line < scriptfilename){
      print line
      }
}

```

# Answer
# Pseudocode

```
// Set up a cron job to run this script (only) once a day

yesterdays_stock_price = '46.48'

todays_stock_price = curl_google_finance('VTSMX')

print "Difference between yesterday's stock price and today's: "

print todays_stock_price

self = open('self.file')

self.replace( /yesterdays_stock_price = '[0-9\.]+'/, todays_stock_price)

self.save()

```
> 7 votes

# Answer
# gawk (1224 characters, as this is not code golf)

One of reasons why awk shouldn't be used for self-modifying scripts.

```
#!/usr/bin/gawk -f
function download(name,     url, service, host, old_rs, old_ors) {
    old_rs = RS
    old_ors = ORS
    RS = ORS = "\r\n"

    host = "download.finance.yahoo.com"
    url = "http://"host"/d/quotes.csv?s="name"&f=l1"
    service = "/inet/tcp/0/"host"/80"
    print "GET", url |& service
    service |& getline
    close(service)

    RS = old_rs
    ORS = old_ors

    return $0
}

function update(value,       file, self, result) {
    # Do complex stuff in order to find the program itself.
    file = "/proc/"PROCINFO["pid"]"/comm"
    if (getline < file <= 0) {
        print "/proc filesystem not supported." > "/dev/stderr"
        exit
    }
    close(file)
    if ($0 ~ /^g?awk$/) {
        print "You need to run program directly." > "/dev/stderr"
        exit
    }
    self = $0
    result = ""
    while (getline < self > 0) {
        # Avoid finding this line.
        if (/[y]esterday/) gsub(/[0-9]+(\.[0-9]+)?/, value)
        result = result $0"\n"
    }
    printf "%s", result > self
    close(self)
}

BEGIN {
    yesterday = 1120.71
    today = download("GOOG")
    update(today)
    print "Yesterday:", yesterday
    print "Today:", today
    print "Difference:", today - yesterday
}

```
> 3 votes

# Answer
Using @jawns317 psueudocode:

# BASH

```
#!/bin/bash
set -e;
google_price_last=1118.79;
current_google_price=`wget -qO- "http://finance.yahoo.com/d/quotes.csv?s=GOOG&f=l1"|tr -d "\r\n"`;
echo "Current Price: $current_google_price";
echo "Last Price: $google_price_last";
echo "Price change: "`echo $current_google_price - $google_price_last | bc -l`;
sed -ri 's/last=[0-9\.]+\;/last='"$current_google_price"';/g' $0;

```
> 2 votes

# Answer
Back at uni I *discovered* (ah-hem) a system which I though would prove fool-proof at the local casino. Bet on red on the roulette wheel, and if you lost double the bet, and so on ...See Martingale System

**VBS**

```
Dim objFSO
Dim objTF
Dim strFile
Dim lngBet

lngBet = 5
strFile = "boss.txt"
'spin roulette wheel
Randomize

'18 blacks, 18 reds, 1 green
intnumber = Int(36 * Rnd + 1)

'mofify code to double-down losing bets
Do While intnumber < 18
intnumber = Int(36 * Rnd + 1)
bfound = True
Set objFSO = CreateObject("scripting.filesystemobject")
Set objTF = objFSO.createtextfile(strFile, 2)
objTF.writeline "lngbet=lngbet*2"
objTF.Close
Set objTF = objFSO.opentextfile(strFile, 1)
Execute objTF.ReadAll()
objTF.Close
Loop

If bfound Then objFSO.deletefile (strFile)
wscript.echo "final bet was " & lngBet

```
> 2 votes

# Answer
I have some pseudo code for someone to develop. All it really needs are some functions built to do the text replacement. I feel the function names give a sufficient description that the actual code is probably trivial.

```
Write "You should really give him back his stapler."
Write "No one has noticed an account with $0 ."
Write "Your TPS reports are complete."
Write "You should throw that Piece of * out the window."

$event = Random 1..3
$fireStarter = Random 1..100
$fractions = Random 1..100

switch $event
    {
    1 - $stapler = $false
    2 - $TPSreports = $false
    3 - $printerJam = $true
    }

if ($stapler = false)
    { Write "I think you have my stapler"

           if ( ($times + $fireStarter ) -GreaterThan 100 ) { Function Burn }
    $times + 1
    $stapler = $true
    Function SelfModifyLine1
    Function SelfModifyTimes
    }

if ( $Fractions -LessThan 50 )
    { $account = $account + $fractions
    Function SelfModifyLine2 }

if ( $TPSreports = $false ) {  Function SelfModifyLine3  }

Function YellAtPrinter
Out-file $scriptPath

```
> 0 votes

---
Tags: popularity-contest, file-system
---


title: Warhol these pictures

text:
# Question
Title: Warhol these pictures
We've all seen the famous painting of Marilyn Monroe created by Andy Warhol.

Let's try to replicate that effect with the usual suspects.

Your task is to write a program/programs that do as many as possible of the following tasks:

1. With one image as the input, generate four color palettes from that image and print a 4x4 grid with different "Warhol'd" color variants of that image.
2. With two images as input, generate two color palettes from each image and print a Warhol'd grid of the first image.
3. With four images as input, generate one color palette from each image and print a Warhol'd grid of the first image.

Of course, it would be cheating to hardcode palettes you like the best, **so your program has to determine a set of colors that is both distinct and aesthetically pleasing.** Warhol used five distinct colors in each panel, so five is your goal as well.

Here are some photos that you could use to showcase your program:

Try to achieve a wide range of palette colorings and of course make them as aesthetically pleasing as possible.

This is a popularity contest, so the answer with the most net votes wins.

(Formatting largely copied from Paint by Numbers, which was a partial inspiration for this challenge as was American Gothic in the palette of Mona Lisa: Rearrange the pixels)

# Answer
# Mathematica

```
namedColors = {Red, Green, Blue, Black, White, Gray, Cyan, Magenta, Yellow, Brown, Orange, Pink, Purple};
    myRules =
      Table[Rule[namedColors[[i]], RandomChoice[namedColors]], {j, 4}, {i,
         Length[namedColors]}];

myImages = {--images here--};

Grid@Table[ColorQuantize[ColorReplace[myImages[[i]], myRules[[j]]],5],
{i, Length[myImages]}, {j, 4}]

```
> 5 votes

---
Tags: popularity-contest, graphical-output, image-processing
---


title: Image Battle of Colours

text:
# Question
Title: Image Battle of Colours
## CONGRATULATIONS to @kuroineko for the best entry and winning the 200 bounty from @TheBestOne (excellent sportsmanship!).

Write a program to colour as much of an image as possible before opposition programs do.

## Rules in brief

* Your program will be given an image, your colour, and integer N.
* Each turn you are sent pixel updates by other programs, and asked for your N updates.
* You can update any white pixel that is next to a pixel of your colour.
* The program that has added the most pixels wins.

## Rules in detail

Your program will be given a PNG image filename, home colour, and a number N. The number N is the maximum number of pixels your program may colour each turn.

Example: `MyProg arena.png (255,0,0) 30`

The input image will be a rectangle with sides between 20 and 1000 pixels long. It will consist of black, white, and colour pixels. Your program may choose a sequence of *white* pixels to colour as your own, with the condition that each new pixel must have at least one of its four neighbour pixels of your own colour. The image will initially have at least one pixel of your colour. It may also have pixels of colours that no program is assigned to. The alpha channel is not used.

Your goal is to block your opponents and write your colour into as many pixels as you can.

Each turn your program will accept 1 or more message lines on STDIN, and write a line consisting of pixel coordinates on STDOUT. Remember to assign STDOUT as unbuffered or flush the STDOUT buffer each turn.

The order of players called each turn will be randomly assigned. This means that an opponent (or your program) may have 2 turns in a row.

Your program will be sent `colour (N,N,N) chose X,Y X,Y ... X,Y` information messages that describe the pixels filled in by player programs. If a player makes no moves, or no valid moves, you will not be sent a message about that player's moves. Your program will also be sent a message about your own accepted moves (if you have specified at least one valid move). The pixel 0,0 is in the top left corner of the image.

On receiving `pick pixels`, your program will output `X,Y X,Y ... X,Y` up to N pixels (an empty string consisting of just a '\n' is allowed). The pixels must be in order of plotting. If a pixel is invalid, it will be ignored and not be in the report to players. Your program has 2 seconds to initialise after starting, but only 0.1 second to reply with an answer each turn or it will miss that turn. A pixel update sent after 0.1 second will record a fault. After 5 faults your program is suspended and will not be sent updates or `pick pixels` requests.

When the judge program receives an empty or invalid pixel choice from every non-suspended player program, the image will be considered *complete* and programs will be sent the message "exit". Programs must terminate after receiving "exit".

## Scoring

The judge will score points after the image is complete. Your score will be your number of pixels updated divided by the average pixel capture that round, expressed as a percentage.

The number of pixels added to the image by your player is A. The total number of pixels added by *all* P players is T. `avg = T/P` `score = 100*A/avg`

## Posting scores

A reference opponent "The Blob" is given. For each answer, title your bot with a name, language, and your score (average of arena 1 to 4) against the reference opponent. A picture or animation of one of your battles would be good too. The winner is the program with the highest score against the reference bot.

If The Blob proves too easy to beat, I may add a second round with a stronger reference opponent.

You may also like to experiment with 4 or more player programs. You could also test your bot against other bots posted as answers.

## The Judge

The judge program requires the common Python Imaging Library (PIL) and should be easy to install from your OS package manager on Linux. I have a report that PIL does not work with 64 bit Python on Windows 7, so please check if PIL will work for you before starting this challenge (updated 2015-01-29).

```
#!/usr/bin/env python
# Judge Program for Image Battle challenge on PPCG.
# Runs on Python 2.7 on Ubuntu Linux. May need edits for other platforms.
# V1.0 First release.
# V1.1 Added Java support
# V1.2 Added Java inner class support
# usage: judge cfg.py
import sys, re, random, os, shutil, subprocess, datetime, time, signal
from PIL import Image

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def place(loc, colour):
    # if valid, place colour at loc and return True, else False
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        if any(pix[p]==colour for p in plist if 0<=p[0]<W and 0<=p[1]<H):
            pix[loc] = colour
            return True
    return False

def updateimage(image, msg, bot):
    if not re.match(r'(\s*\d+,\d+)*\s*', msg):
        return []
    plist = [tuple(int(v) for v in pr.split(',')) for pr in msg.split()]
    plist = plist[:PIXELBATCH]
    return [p for p in plist if place(p, bot.colour)]

class Bot:
    botlist = []
    def __init__(self, name, interpreter=None, colour=None):
        self.prog = name
        self.botlist.append(self)
        callarg = re.sub(r'\.class$', '', name)  # Java fix
        self.call = [interpreter, callarg] if interpreter else [callarg]
        self.colour = colour
        self.colstr = str(colour).replace(' ', '')
        self.faults = 0
        self.env = 'env%u' % self.botlist.index(self)
        try: os.mkdir(self.env)
        except: pass
        if name.endswith('.class'): # Java inner class fix
            rootname = re.sub(r'\.class$', '', name)
            for fn in os.listdir('.'):
                if fn.startswith(rootname) and fn.endswith('.class'):
                    shutil.copy(fn, self.env)
        else:
            shutil.copy(self.prog, self.env)
        shutil.copy(imagename, self.env)
        os.chdir(self.env)
        args = self.call + [imagename, self.colstr, `PIXELBATCH`]
        self.proc = subprocess.Popen(args, stdin=subprocess.PIPE,
            stdout=subprocess.PIPE, stderr=subprocess.PIPE)
        os.chdir('..')
    def send(self, msg):
        if self.faults < FAULTLIMIT:
            self.proc.stdin.write(msg + '\n')
            self.proc.stdin.flush()
    def read(self, timelimit):
        if self.faults < FAULTLIMIT:
            start = time.time()
            inline = self.proc.stdout.readline()
            if time.time() - start > timelimit:
                self.faults += 1
                inline = ''
            return inline.strip()
    def exit(self):
        self.send('exit')

from cfg import *
for i, (prog, interp) in enumerate(botspec):
    Bot(prog, interp, colourspec[i])

image = Image.open(imagename)
pix = image.load()
W,H = image.size

time.sleep(INITTIME)
total = 0
for turn in range(1, MAXTURNS+1):
    random.shuffle(Bot.botlist)
    nullbots = 0
    for bot in Bot.botlist:
        bot.send('pick pixels')
        inmsg = bot.read(TIMELIMIT)
        newpixels = updateimage(image, inmsg, bot)
        total += len(newpixels)
        if newpixels:
            pixtext = ' '.join('%u,%u'%p for p in newpixels)
            msg = 'colour %s chose %s' % (bot.colstr, pixtext)
            for msgbot in Bot.botlist:
                msgbot.send(msg)
        else:
            nullbots += 1
    if nullbots == len(Bot.botlist):
        break
    if turn % 100 == 0: print 'Turn %s done %s pixels' % (turn, total)
for msgbot in Bot.botlist:
    msgbot.exit()

counts = dict((c,f) for f,c in image.getcolors(W*H))
avg = 1.0 * sum(counts.values()) / len(Bot.botlist)
for bot in Bot.botlist:
    score = 100 * counts[bot.colour] / avg
    print 'Bot %s with colour %s scored %s' % (bot.prog, bot.colour, score)
image.save(BATTLE+'.png')

```

## Example Config - cfg.py

```
BATTLE = 'Green Blob vs Red Blob'
MAXTURNS = 20000
PIXELBATCH = 10
INITTIME = 2.0
TIMELIMIT = 0.1
FAULTLIMIT = 5

imagename = 'arena1.png'

colourspec = (0,255,0), (255,0,0)

botspec = [
    ('blob.py', 'python'),
    ('blob.py', 'python'),
    ]

```

## The Blob - the reference opponent

```
# Blob v1.0 - A reference opponent for the Image Battle challenge on PPCG.
import sys, os
from PIL import Image

image = Image.open(sys.argv[1])
pix = image.load()
W,H = image.size
mycolour = eval(sys.argv[2])
pixbatch = int(sys.argv[3])

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def canchoose(loc, colour):
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        if any(pix[p]==colour for p in plist if 0<=p[0]<W and 0<=p[1]<H):
            return True
    return False

def near(loc):
    plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
    pboard = [p for p in plist if 0<=p[0]<W and 0<=p[1]<H]
    return [p for p in pboard if pix[p] == (255,255,255)]

def updateimage(image, msg):
    ctext, colourtext, chose, points = msg.split(None, 3)
    colour = eval(colourtext)
    plist = [tuple(int(v) for v in pr.split(',')) for pr in points.split()]
    for p in plist:
        pix[p] = colour
        skin.discard(p)
        if colour == mycolour:
            for np in near(p):
                skin.add(np)

board = [(x,y) for x in range(W) for y in range(H)]
skin = set(p for p in board if canchoose(p, mycolour))

while 1:
    msg = sys.stdin.readline()
    if msg.startswith('colour'):
        updateimage(image, msg.strip())
    if msg.startswith('pick'):
        plen = min(pixbatch, len(skin))
        moves = [skin.pop() for i in range(plen)]
        movetext = ' '.join('%u,%u'%p for p in moves)
        sys.stdout.write(movetext + '\n')
        sys.stdout.flush()
    if msg.startswith('exit'):
        break

image.save('blob.png')

```

## Arena 1

## Arena 2

## Arena 3

## Arena 4

## An Example Battle - Blob vs Blob

This battle had a predictable result:

```
Bot blob.py with colour (255, 0, 0) scored 89.2883333333
Bot blob.py with colour (0, 255, 0) scored 89.365

```

# Answer
> 18 votes
# ColorFighter - C++ - eats a couple of swallowers for breakfast

**EDIT**

* cleaned up the code
* added a simple but effective optimization
* added some GIF animations

## God I hate snakes (just pretend they are spiders, Indy)

Actually I love Python. I wish I were less of a lazy boy and started to learn it properly, that's all.

All this being said, I had to struggle with the 64 bits version of this snake to get the Judge working. Making PIL work with the 64 bits version of Python under Win7 requires more patience than I was ready to devote to this challenge, so in the end I switched (painfully) to the Win32 version.

Also, the Judge tends to crash badly when a bot is too slow to respond.
Being no Python savvy, I did not fix it, but it has to do with reading an empty answer after a timeout on stdin.

A minor improvement would be to put stderr output to a file for each bot. That would ease tracing for post-mortem debugging.

Except for these minor problems, I found the Judge very simple and pleasant to use.
Kudos for yet another inventive and fun challenge.

## The code

```
#define _CRT_SECURE_NO_WARNINGS // prevents Microsoft from croaking about the safety of scanf. Since every rabid Russian hacker and his dog are welcome to try and overflow my buffers, I could not care less.
#include "lodepng.h"
#include <vector>
#include <deque>
#include <iostream>
#include <sstream>
#include <cassert>   // paranoid android
#include <cstdint>   // fixed size types
#include <algorithm> // min max

using namespace std;

// ============================================================================
// The less painful way I found to teach C++ how to handle png images
// ============================================================================
typedef unsigned tRGB;
#define RGB(r,g,b) (((r) << 16) | ((g) << 8) | (b))
class tRawImage {
public:
    unsigned w, h;

    tRawImage(unsigned w=0, unsigned h=0) : w(w), h(h), data(w*h * 4, 0) {}
    void read(const char* filename) { unsigned res = lodepng::decode(data, w, h, filename); assert(!res);  }
    void write(const char * filename)
    {
        std::vector<unsigned char> png;
        unsigned res = lodepng::encode(png, data, w, h, LCT_RGBA); assert(!res);
        lodepng::save_file(png, filename);
    }
    tRGB get_pixel(int x, int y) const
    {
        size_t base = raw_index(x,y);
        return RGB(data[base], data[base + 1], data[base + 2]);
    }
    void set_pixel(int x, int y, tRGB color)
    {
        size_t base = raw_index(x, y);
        data[base+0] = (color >> 16) & 0xFF;
        data[base+1] = (color >>  8) & 0xFF;
        data[base+2] = (color >> 0) & 0xFF;
        data[base+3] = 0xFF; // alpha
    }
private:
    vector<unsigned char> data;
    void bound_check(unsigned x, unsigned y) const { assert(x < w && y < h); }
    size_t raw_index(unsigned x, unsigned y) const { bound_check(x, y); return 4 * (y * w + x); }
};

// ============================================================================
// coordinates
// ============================================================================
typedef int16_t tCoord;

struct tPoint {
    tCoord x, y;
    tPoint operator+  (const tPoint & p) const { return { x + p.x, y + p.y }; }
};

typedef deque<tPoint> tPointList;

// ============================================================================
// command line and input parsing
// (in a nice airtight bag to contain the stench of C++ string handling)
// ============================================================================
enum tCommand {
    c_quit,
    c_update,
    c_play,
};

class tParser {
public:
    tRGB color;
    tPointList points;

    tRGB read_color(const char * s)
    {
        int r, g, b;
        sscanf(s, "(%d,%d,%d)", &r, &g, &b);
        return RGB(r, g, b);
    }

    tCommand command(void)
    {
        string line;
        getline(cin, line);

        string cmd = get_token(line);
        points.clear();

        if (cmd == "exit") return c_quit;
        if (cmd == "pick") return c_play;

        // even more convoluted and ugly than the LEFT$s and RIGHT$s of Apple ][ basic...
        if (cmd != "colour")
        {
            cerr << "unknown command '" << cmd << "'\n";
            exit(0);
        }
        assert(cmd == "colour");
        color = read_color(get_token(line).c_str());
        get_token(line); // skip "chose"
        while (line != "")
        {
            string coords = get_token(line);
            int x = atoi(get_token(coords, ',').c_str());
            int y = atoi(coords.c_str());
            points.push_back({ x, y });
        }
        return c_update;
    }

private:
    // even more verbose and inefficient than setting up an ADA rendezvous...
    string get_token(string& s, char delimiter = ' ')
    {
        size_t pos = 0;
        string token;
        if ((pos = s.find(delimiter)) != string::npos)
        {
            token = s.substr(0, pos);
            s.erase(0, pos + 1);
            return token;
        }
        token = s; s.clear(); return token;
    }
};

// ============================================================================
// pathing
// ============================================================================
class tPather {

public:
    tPather(tRawImage image, tRGB own_color)
        : arena(image)
        , w(image.w)
        , h(image.h)
        , own_color(own_color)
        , enemy_threat(false)
    {
        // extract colored pixels and own color areas
        tPointList own_pixels;
        color_plane[neutral].resize(w*h, false);
        color_plane[enemies].resize(w*h, false);
        for (size_t x = 0; x != w; x++)
        for (size_t y = 0; y != h; y++)
        {
            tRGB color = image.get_pixel(x, y);
            if (color == col_white) continue;
            plane_set(neutral, x, y);
            if (color == own_color) own_pixels.push_back({ x, y }); // fill the frontier with all points of our color
        }

        // compute initial frontier
        for (tPoint pixel : own_pixels)
        for (tPoint n : neighbour)
        {
            tPoint pos = pixel + n;
            if (!in_picture(pos)) continue;
            if (image.get_pixel(pos.x, pos.y) == col_white)
            {
                frontier.push_back(pixel);
                break;
            }
        }
    }

    tPointList search(size_t pixels_required)
    {
        // flood fill the arena, starting from our current frontier
        tPointList result;
        tPlane closed;
        static tCandidate pool[max_size*max_size]; // fastest possible garbage collection
        size_t alloc;
        static tCandidate* border[max_size*max_size]; // a FIFO that beats a deque anytime
        size_t head, tail;
        static vector<tDistance>distance(w*h); // distance map to be flooded
        size_t filling_pixels = 0; // end of game  optimization

    get_more_results:

        // ready the distance map for filling
        distance.assign(w*h, distance_max);

        // seed our flood fill with the frontier
        alloc = head = tail = 0;
        for (tPoint pos : frontier)
        {
            border[tail++] = new (&pool[alloc++]) tCandidate (pos);
        }

        // set already explored points
        closed = color_plane[neutral]; // that's one huge copy

        // add current result
        for (tPoint pos : result)
        {
            border[tail++] = new (&pool[alloc++]) tCandidate(pos);
            closed[raw_index(pos)] = true;
        }

        // let's floooooood!!!!
        while (tail > head && pixels_required > filling_pixels)
        {
            tCandidate& candidate = *border[head++];
            tDistance  dist = candidate.distance;
            distance[raw_index(candidate.pos)] = dist++;
            for (tPoint n : neighbour)
            {
                tPoint pos = candidate.pos + n;
                if (!in_picture (pos)) continue;
                size_t index = raw_index(pos);
                if (closed[index]) continue;
                if (color_plane[enemies][index])
                {
                    if (dist == (distance_initial + 1)) continue; // already near an enemy pixel

                    // reached the nearest enemy pixel
                    static tPoint trail[max_size * max_size / 2]; // dimensioned as a 1 pixel wide spiral across the whole map
                    size_t trail_size = 0;

                    // walk back toward the frontier
                    tPoint walker = candidate.pos;
                    tDistance cur_d = dist;
                    while (cur_d > distance_initial)
                    {
                        trail[trail_size++] = walker;
                        tPoint next_n;
                        for (tPoint n : neighbour)
                        {
                            tPoint next = walker + n;
                            if (!in_picture(next)) continue;
                            tDistance prev_d = distance[raw_index(next)];
                            if (prev_d < cur_d)
                            {
                                cur_d = prev_d;
                                next_n = n;
                            }
                        }
                        walker = walker + next_n;
                    }

                    // collect our precious new pixels
                    if (trail_size > 0)
                    {
                        while (trail_size > 0)
                        {
                            if (pixels_required-- == 0) return result;       // ;!; <-- BRUTAL EXIT
                            tPoint pos = trail[--trail_size];
                            result.push_back (pos);
                        }
                        goto get_more_results; // I could have done a loop, but I did not bother to. Booooh!!!
                    }
                    continue;
                }

                // on to the next neighbour
                closed[index] = true;
                border[tail++] = new (&pool[alloc++]) tCandidate(pos, dist);
                if (!enemy_threat) filling_pixels++;
            }
        }

        // if all enemies have been surrounded, top up result with the first points of our flood fill
        if (enemy_threat) enemy_threat = pixels_required == 0;
        tPathIndex i = frontier.size() + result.size();
        while (pixels_required--) result.push_back(pool[i++].pos);
        return result;
    }

    // tidy up our map and frontier while other bots are thinking
    void validate(tPointList moves)
    {
        // report new points
        for (tPoint pos : moves)
        {
            frontier.push_back(pos);
            color_plane[neutral][raw_index(pos)] = true;
        }

        // remove surrounded points from frontier
        for (auto it = frontier.begin(); it != frontier.end();)
        {
            bool in_frontier = false;
            for (tPoint n : neighbour)
            {
                tPoint pos = *it + n;
                if (!in_picture(pos)) continue;
                if (!(color_plane[neutral][raw_index(pos)] || color_plane[enemies][raw_index(pos)]))
                {
                    in_frontier = true;
                    break;
                }
            }
            if (!in_frontier) it = frontier.erase(it); else ++it; // the magic way of deleting an element without wrecking your iterator
        }
    }

    // handle enemy move notifications
    void update(tRGB color, tPointList points)
    {
        assert(color != own_color);

        // plot enemy moves
        enemy_threat = true;
        for (tPoint p : points) plane_set(enemies, p);

        // important optimization here :
        /*
         * Stop 1 pixel away from the enemy to avoid wasting moves in dogfights.
         * Better let the enemy gain a few more pixels inside the surrounded region
         * and use our precious moves to get closer to the next threat.
         */
        for (tPoint p : points) for (tPoint n : neighbour) plane_set(enemies, p+n);

        // if a new enemy is detected, gather its initial pixels
        for (tRGB enemy : known_enemies) if (color == enemy) return;
        known_enemies.push_back(color);
        tPointList start_areas = scan_color(color);
        for (tPoint p : start_areas) plane_set(enemies, p);
    }

private:
    typedef uint16_t tPathIndex;

    typedef uint16_t tDistance;
    static const tDistance distance_max     = 0xFFFF;
    static const tDistance distance_initial = 0;

    struct tCandidate {
        tPoint pos;
        tDistance distance;
        tCandidate(){} // must avoid doing anything in this constructor, or pathing will slow to a crawl
        tCandidate(tPoint pos, tDistance distance = distance_initial) : pos(pos), distance(distance) {}
    };

    // neighbourhood of a pixel
    static const tPoint neighbour[4];

    // dimensions
    tCoord w, h;
    static const size_t max_size = 1000;

    // colors lookup
    const tRGB col_white = RGB(0xFF, 0xFF, 0xFF);
    const tRGB col_black = RGB(0x00, 0x00, 0x00);
    tRGB own_color;
    const tRawImage arena;
    tPointList scan_color(tRGB color)
    {
        tPointList res;
        for (size_t x = 0; x != w; x++)
        for (size_t y = 0; y != h; y++)
        {
            if (arena.get_pixel(x, y) == color) res.push_back({ x, y });
        }
        return res;
    }

    // color planes
    typedef vector<bool> tPlane;
    tPlane color_plane[2];
    const size_t neutral = 0;
    const size_t enemies = 1;
    bool plane_get(size_t player, tPoint p) { return plane_get(player, p.x, p.y); }
    bool plane_get(size_t player, size_t x, size_t y) { return in_picture(x, y) ? color_plane[player][raw_index(x, y)] : false; }
    void plane_set(size_t player, tPoint p) { plane_set(player, p.x, p.y); }
    void plane_set(size_t player, size_t x, size_t y) { if (in_picture(x, y)) color_plane[player][raw_index(x, y)] = true; }
    bool in_picture(tPoint p) { return in_picture(p.x, p.y); }
    bool in_picture(int x, int y) { return x >= 0 && x < w && y >= 0 && y < h; }
    size_t raw_index(tPoint p) { return raw_index(p.x, p.y); }
    size_t raw_index(size_t x, size_t y) { return y*w + x; }

    // frontier
    tPointList frontier;

    // register enemies when they show up
    vector<tRGB>known_enemies;

    // end of game optimization
    bool enemy_threat;
};

// small neighbourhood
const tPoint tPather::neighbour[4] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

// ============================================================================
// main class
// ============================================================================
class tGame {
public:
    tGame(tRawImage image, tRGB color, size_t num_pixels)
        : own_color(color)
        , response_len(num_pixels)
        , pather(image, color)
    {}

    void main_loop(void)
    {
        // grab an initial answer in case we're playing first
        tPointList moves = pather.search(response_len);
        for (;;)
        {
            ostringstream answer;
            size_t        num_points;
            tPointList    played;

            switch (parser.command())
            {
            case c_quit:
                return;

            case c_play:
                // play as many pixels as possible
                if (moves.size() < response_len) moves = pather.search(response_len);
                num_points = min(moves.size(), response_len);
                for (size_t i = 0; i != num_points; i++)
                {
                    answer << moves[0].x << ',' << moves[0].y;
                    if (i != num_points - 1) answer << ' '; // STL had more important things to do these last 30 years than implement an implode/explode feature, but you can write your own custom version with exception safety and in-place construction. It's a bit of work, but thanks to C++ inherent genericity you will be able to extend it to giraffes and hippos with a very manageable amount of code refactoring. It's not anyone's language, your C++, eh. Just try to implode hippos in Python. Hah!
                    played.push_back(moves[0]);
                    moves.pop_front();
                }
                cout << answer.str() << '\n';

                // now that we managed to print a list of points to stdout, we just need to cleanup the mess
                pather.validate(played);
                break;

            case c_update:
                if (parser.color == own_color) continue; // hopefully we kept track of these already
                pather.update(parser.color, parser.points);
                moves = pather.search(response_len); // get cracking
                break;
            }
        }
    }

private:
    tParser parser;
    tRGB    own_color;
    size_t  response_len;
    tPather pather;
};

void main(int argc, char * argv[])
{
    // process command line
    tRawImage raw_image; raw_image.read (argv[1]);
    tRGB my_color = tParser().read_color(argv[2]);
    int num_pixels               = atoi (argv[3]);

    // init and run
    tGame game (raw_image, my_color, num_pixels);
    game.main_loop();
}

```

## Building the executable

I used **LODEpng.cpp** and **LODEpng.h** to read png images.
About the easiest way I found to teach this retarded C++ language how to read a picture without having to build half a dozen libraries.
Just compile & link LODEpng.cpp along with the main and Bob's your uncle.

I compiled with MSVC2013, but since I used only a few STL basic containers (deque and vectors), it *might* work with gcc (if you're lucky).
If it doesn't, I *might* try a MinGW build, but frankly I'm getting tired of C++ portability issues.

I did quite a lot of portable C/C++ in my days (on exotic compilers for various 8 to 32 bits processors as well as SunOS, Windows from 3.11 up to Vista and Linux from its infancy to Ubuntu cooing zebra or whatever, so I think I have a pretty good idea of what portability means), but at the time it did not require to memorize (or discover) the innumerable discrepancies between the GNU and Microsoft interpretations of the cryptic and bloated specs of the STL monster.

## Results against Swallower

## How it works

At the core, this is a simple brute-force floodfill pathing.

The frontier of the player's color (i.e. the pixels that have at least one white neighbour) is used as a seed to perform the classic distance-flooding algorithm.

When a point reaches the vincinity of an enemy color, a backward path is computed to produce a string of pixels moving toward the nearest enemy spot.

The process is repeated until enough points have been gathered for a response of the desired length.

This repetition is obscenely expensive, especially when fighting near the enemy.
Each time a string of pixels leading from the frontier to an enemy pixel has been found (and we need more points to complete the answer), the flood fill is redone from start, with the new path added to the frontier. It means you could have to do 5 flood fills or more to get an 10 pixels answer.

If no more enemy pixels are reachable, arbitraty neighbours of the frontier pixels are selected.
The algorithm devolves to a rather inefficient flood fill, but this only happens after the outcome of the game has been decided (i.e. there is no more neutral territory to fight for).
I did optimize it so that the Judge do not spend ages filling up the map once the competition has been dealt with. In its current state, the execution time is neglectible compared with the Judge itself.

Since enemy colors are not known at start, the initial arena image is kept in store in order to copy the enemy's starting areas when it makes its first move.
If the code plays first, it will simply flood fill a few arbitrary pixels.

This makes the algorithm capable of fighting an arbitrary number of adversaries, and even possibly new adversaries arriving at a random point in time, or colors appearing without a starting area (though this has absolutely no practical use).

Enemy handling on a color-per-color basis would also allow to have two instances of the bot cooperate (using pixel coordinates to pass a secret recognition sign).
Sounds like fun, I'll probably try that :).

Computation-heavy pathing is done as soon as new data are available (after a move notification), and some optimizations (the frontier update) are done just after a response has been given (to do as much computation as possible during the other bots turns).

Here again, there could be ways of doing more subtle things if there were more than 1 adversary (like aborting a computation if new data become available), but at any rate I fail to see where multitasking is needed, as long as the algorithm is able to work on full load.

## Performance issues

All this cannot work without fast data access (and more computing power than the whole Appolo program, i.e. your average PC when used to do more than post a few tweets).

The speed is heavily compiler-dependent. Usually GNU beats Microsoft by a 30% margin (that's the magic number I noticed on 3 other pathing-related code challenges), but this mileage may vary of course.

The code in its current state barely breaks a sweat on arena 4. Windows perfmeter reports about 4 to 7 % CPU usage, so it should be able to cope with a 1000x1000 map within the 100ms response time limit.

At the heart of about every pathing algorithm lies a FIFO (possibly proritized, though not in that case), which in turn requires fast element allocation.

Since the OP obligingly set a limit to the arena size, I did some maths and saw that fixed data structures dimensioned to max (i.e. 1.000.000 pixels) would not consume more than a couple dozen megabytes, which your average PC eats for breakfast.
Indeed under Win7 and compiled with MSVC 2013, the code consumes about 14Mb on arena 4, while Swallower's two threads are using more than 20Mb.

I started with STL containers for easier prototyping, but STL made the code even less readable, since I had no desire to create a class to encapsulate each and every bit of data to hide the obfuscation away (whether that is due to my own inabilities to cope with the STL is left to the appreciation of the reader).
Regardless, the result was so atrociously slow that at first I thought I was building a debug version by mistake.

I reckon this is partly due to the incredibly poor Microsoft implementation of the STL (where, for instance, vectors and bitsets do bound checks or other crypic operations on operator\[\], in direct violation of the spec), and partly to the STL design itself.

I could cope with the atrocious syntax and portability (i.e. Microsoft vs GNU) issues if the performances were there, but this is certainly not the case.

For instance, `deque` is inherently slow, because it shuffles lots of bookkeeping data around waiting for the occasion to do its super smart resizing, about which I could not care less.
Sure I could have implemented a custom allocator and whaterver other custom template bits, but a custom allocator alone costs a few hundred lines of code and the better part of a day to test, what with the dozen of interfaces it has to implement, while a handmade equivalent structure is about zero lines of code (albeit more dangerous, but the algorithm would not have worked if I did not know - or think I knew - what I was doing anyway).

So eventually I kept the STL containers in non-critical parts of the code, and built my own brutal allocator and FIFO with two circa 1970 arrays and three unsigned shorts.

## Swallowing the swallower

As its author confirmed, the erratic patterns of the Swallower are caused by lag between enemy moves notifications and updates from the pathing thread.
The system perfmeter shows clearly the pathing thread consuming 100% CPU all the time, and the jagged patterns tend to appear when the focus of the fight shifts to a new area. This is also quite apparent with the animations.

## A simple but effective optimization

After looking at the epic dogfights between Swallower and my fighter, I remembered an old saying from the game of Go: defend close up, but attack from afar.

There is wisdom in that. If you try to stick to your adversary too much, you will waste precious moves trying to block each possible path. On the contrary, if you stay just one pixel away, you will likely avoid filling small gaps that would gain very little, and use your moves to counter more important threats.

To implement this idea, I simply extended the moves of an enemy (marking the 4 neighbours of each move as an enemy pixel).
This stops the pathing algorithm one pixel away from the enemy's border, allowing my fighter to work its way around an adversary without getting caught in too many dogfights.

You can see the improvement
(though all runs are not as successful, you can notice the much smoother outlines):

# Answer
> 22 votes
# Depth-first Blob vs. Blob

# Language = Python (3.2)

# Score = 111.475388276 153.34210035

Update : Now using a custom `Set` class to get the `pop()` method to produce a sort of grid pattern which drastically improves the area covered in the beginning cutting off large parts of the image from the enemy. Note : I am using a 12 x 12 grid for this which of a random sample of grid sizes seemed to give the best results for arena3 (the one that got the worst score before the update), however it is very likely that a more optimal grid size exists for the given selection of arenas.

I went for a simple modification to the reference bot to make it favor picking feasible points that are bordered by as few own-colored points as possible. An improvement might be to make it also favor picking feasible points that are bordered by as many enemy-colored points as possible.

dfblob.py:

```
import sys, os
from PIL import Image

class RoomyIntPairHashSet:
    def __init__(self, firstMax, secondMax):
        self.m1 = firstMax
        self.m2 = secondMax
        self.set = [set() for i in range((firstMax - 1) * (secondMax - 1) + 1)]
        self.len = 0

    def add(self, tup):
        subset = self.set[self.gettuphash(tup)]
        self.len -= len(subset)
        subset.add(tup)
        self.len += len(subset)

    def discard(self, tup):
        subset = self.set[self.gettuphash(tup)]
        self.len -= len(subset)
        subset.discard(tup)
        self.len += len(subset)

    def pop(self):
        for s in self.set:
            if len(s) > 0:
                self.len -= 1
                return s.pop()
        return self.set[0].pop()

    def gettuphash(self, tup):
        return (tup[0] % self.m1) * (tup[1] % self.m2)

    def __len__(self):
        return self.len

gridhashwidth = 12
gridhashheight = 12
image = Image.open(sys.argv[1])
pix = image.load()
W,H = image.size
mycolour = eval(sys.argv[2])
pixbatch = int(sys.argv[3])

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def canchoose(loc, virtualneighbors, colour, num_neighbors):
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        actual_num_neighbors = 0
        for p in plist:
            if 0<=p[0]<W and 0<=p[1]<H and pix[p]==colour or p in virtualneighbors:
                actual_num_neighbors += 1
        return num_neighbors == actual_num_neighbors
    return False

def near(loc, exclude):
    plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
    pboard = [p for p in plist if 0<=p[0]<W and 0<=p[1]<H]
    return [p for p in pboard if pix[p] == (255,255,255) and p not in exclude]

def updateimage(image, msg):
    ctext, colourtext, chose, points = msg.split(None, 3)
    colour = eval(colourtext)
    plist = [tuple(int(v) for v in pr.split(',')) for pr in points.split()]
    for p in plist:
        pix[p] = colour
        for i in range(len(skins)):
            skins[i].discard(p)
        if colour == mycolour:
            for np in near(p, []):
                for j in range(len(skins)):
                    skins[j].discard(np)
                    if canchoose(np, [], mycolour, j + 1):
                        skins[j].add(np)

board = [(x,y) for x in range(W) for y in range(H)]
skins = []
for i in range(1, 1 + len(ORTH)):
    skin = RoomyIntPairHashSet(gridhashwidth, gridhashheight)
    skins.append(skin)
    for p in board:
        if canchoose(p, [], mycolour, i):
            skin.add(p)

while 1:
    msg = sys.stdin.readline()
    print("got message "+ msg, file=sys.stderr)
    if msg.startswith('colour'):
        print("updating image", file=sys.stderr)
        updateimage(image, msg.strip())
        print("updated image", file=sys.stderr)
    if msg.startswith('pick'):
        moves = []
        print("picking moves", file=sys.stderr)
        virtualskins = [RoomyIntPairHashSet(gridhashwidth, gridhashheight) for i in range(len(skins))]
        for i in range(pixbatch):
            for j in range(len(skins)):
                if len(virtualskins[j]) > 0 or len(skins[j]) > 0:
                    move = None
                    if len(virtualskins[j]) > 0:
                        move = virtualskins[j].pop()
                    else:
                        move = skins[j].pop()
                    moves.append(move)
                    print("picking move (%u,%u) " % move, file=sys.stderr)
                    for p in near(move, moves):
                        for k in range(len(skins)):
                            virtualskins[k].discard(p)
                            if canchoose(p, moves, mycolour, k + 1):
                                virtualskins[k].add(p)
                    break
        movetext = ' '.join('%u,%u'%p for p in moves)
        print("picked %u moves" % (len(moves)), file=sys.stderr)
        sys.stdout.write(movetext + '\n')
        sys.stdout.flush()
    if msg.startswith('exit') or len(msg) < 1:
        break

image.save('dfblob.png')

```

The original judge has been modified slightly to work with Python 3.2 (and to add a crude logging functionality to the bots + save picture of arena periodically to make animation) :

```
import sys, re, random, os, shutil, subprocess, datetime, time, signal, io
from PIL import Image

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def place(loc, colour):
    # if valid, place colour at loc and return True, else False
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        if any(pix[p]==colour for p in plist if 0<=p[0]<W and 0<=p[1]<H):
            pix[loc] = colour
            return True
    return False

def updateimage(image, msg, bot):
    if not re.match(r'(\s*\d+,\d+)*\s*', msg):
        return []
    plist = [tuple(int(v) for v in pr.split(',')) for pr in msg.split()]
    plist = plist[:PIXELBATCH]
    return [p for p in plist if place(p, bot.colour)]

class Bot:
    botlist = []
    def __init__(self, name, interpreter=None, colour=None):
        self.prog = name
        self.botlist.append(self)
        callarg = re.sub(r'\.class$', '', name)
        self.call = [interpreter, callarg] if interpreter else [callarg]
        self.colour = colour
        self.colstr = str(colour).replace(' ', '')
        self.faults = 0
        self.env = 'env%u' % self.botlist.index(self)
        try: os.mkdir(self.env)
        except: pass
        shutil.copy(self.prog, self.env)
        shutil.copy(imagename, self.env)
        os.chdir(self.env)
        args = self.call + [imagename, self.colstr, str(PIXELBATCH)]
        errorfile = 'err.log'
        with io.open(errorfile, 'wb') as errorlog:
            self.proc = subprocess.Popen(args, stdin=subprocess.PIPE,
                stdout=subprocess.PIPE, stderr=errorlog)
        os.chdir('..')
    def send(self, msg):
        if self.faults < FAULTLIMIT:
            self.proc.stdin.write((msg+'\n').encode('utf-8'))
            self.proc.stdin.flush()
    def read(self, timelimit):
        if self.faults < FAULTLIMIT:
            start = time.time()
            inline = self.proc.stdout.readline().decode('utf-8')
            if time.time() - start > timelimit:
                self.faults += 1
                inline = ''
            return inline.strip()
    def exit(self):
        self.send('exit')

from cfg import *
for i, (prog, interp) in enumerate(botspec):
    Bot(prog, interp, colourspec[i])

image = Image.open(imagename)
pix = image.load()
W,H = image.size
os.mkdir('results')

time.sleep(INITTIME)
total = 0
for turn in range(1, MAXTURNS+1):
    random.shuffle(Bot.botlist)
    nullbots = 0
    for bot in Bot.botlist:
        bot.send('pick pixels')
        inmsg = bot.read(TIMELIMIT)
        newpixels = updateimage(image, inmsg, bot)
        total += len(newpixels)
        if newpixels:
            pixtext = ' '.join('%u,%u'%p for p in newpixels)
            msg = 'colour %s chose %s' % (bot.colstr, pixtext)
            for msgbot in Bot.botlist:
                msgbot.send(msg)
        else:
            nullbots += 1
    if nullbots == len(Bot.botlist):
        break
    if turn % 100 == 0:
        print('Turn %s done %s pixels' % (turn, total))
        image.save("results/"+BATTLE+str(turn//100).zfill(3)+'.png')
for msgbot in Bot.botlist:
    msgbot.exit()

counts = dict((c,f) for f,c in image.getcolors(W*H))
avg = 1.0 * sum(counts.values()) / len(Bot.botlist)
for bot in Bot.botlist:
    score = 100 * counts[bot.colour] / avg
    print('Bot %s with colour %s scored %s' % (bot.prog, bot.colour, score))
image.save(BATTLE+'.png')

```

The arena results follow. The dfblob bot was given the red color for all arenas.

## Arena 1 :

```
Bot dfblob.py with colour (255, 0, 0) scored 163.75666666666666
Bot blob.py with colour (0, 255, 0) scored 14.896666666666667

```

## Arena 2 :

```
Bot blob.py with colour (0, 255, 0) scored 17.65563547726219
Bot dfblob.py with colour (255, 0, 0) scored 149.57006774236964

```

## Arena 3 :

```
Bot blob.py with colour (0, 255, 0) scored 21.09758208782965
Bot dfblob.py with colour (255, 0, 0) scored 142.9732433108277

```

## Arena 4 :

```
Bot blob.py with colour (0, 255, 0) scored 34.443810082244205
Bot dfblob.py with colour (255, 0, 0) scored 157.0684236785121

```

# Answer
> 19 votes
# Swallower

# Language = Java

# Score = ~~162.3289512601408075~~ 169.4020975612382575

Seeks enemies out and surrounds. ~~You might have to give it a longer time limit. Could be improved quite a bit. Sometimes prints invalid pixels.~~

*Update:* Surrounds much faster. Uses another thread to update priorities. Always returns within .1 seconds. Score should be impossible to beat without increasing `MAX_TURNS`.

```
import javax.imageio.ImageIO;
import java.awt.*;
import java.awt.image.BufferedImage;
import java.io.BufferedReader;
import java.io.File;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.List;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.stream.Collectors;

public class Swallower {

    static final byte MY_TYPE = 1;
    static final byte BLANK_TYPE = 0;
    static final byte NEUTRAL_TYPE = 2;
    static final byte ENEMY_TYPE = 3;
    private static final int WHITE = Color.WHITE.getRGB();
    private static final int MAX_TIME = 50;
    private final int color;
    private final int N;
    private final int width;
    private final int height;
    private final BufferedReader in;
    Lock borderLock;
    private final PriorityBlockingQueue<Pixel> border;
    private final Set<Pixel> borderSet;
    private final Thread updater;

    Lock imageLock;
    volatile byte[][] image;
    Lock priorityLock;
    volatile int[][] priority;
    volatile boolean updating;
    volatile private boolean exit;

    class Pixel implements Comparable<Pixel> {

        int x;
        int y;

        public Pixel(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Pixel o) {
            return priority() - o.priority();
        }

        private int priority() {
            priorityLock.lock();
            int p = priority[x][y];
            priorityLock.unlock();
            return p;
        }

        public byte type() {
            imageLock.lock();
            byte i = image[x][y];
            imageLock.unlock();
            return i;
        }

        public boolean isBorder() {
            if (type() != BLANK_TYPE){
                return false;
            }
            for (Pixel p : pixelsAround()){
                if (p.type() == MY_TYPE){
                    return true;
                }
            }
            return false;
        }

        public void setType(byte newType) {
            imageLock.lock();
            image[x][y] = newType;
            imageLock.unlock();
        }

        public void setPriority(int newPriority) {
            borderLock.lock();
            boolean contains = borderSet.remove(this);
            if (contains){
                border.remove(this);
            }
            priorityLock.lock();
            priority[x][y] = newPriority;
            priorityLock.unlock();
            if (contains){
                border.add(this);
                borderSet.add(this);
            }
            borderLock.unlock();
        }

        public List<Pixel> pixelsAround() {
            List<Pixel> pixels = new ArrayList<>(4);
            if (x > 0){
                pixels.add(new Pixel(x - 1, y));
            }
            if (x < width - 1){
                pixels.add(new Pixel(x + 1, y));
            }
            if (y > 0){
                pixels.add(new Pixel(x, y - 1));
            }
            if (y < height - 1){
                pixels.add(new Pixel(x, y + 1));
            }
            return pixels;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pixel pixel = (Pixel) o;

            return x == pixel.x && y == pixel.y;

        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedImage image = ImageIO.read(new File(args[0]));
        int color = parseColorString(args[1]);
        int N = Integer.parseInt(args[2]);
        new Swallower(image, color, N).start();
    }

    private void start() throws IOException {
        updater.start();
        try {
            while (true) {
                String input = in.readLine();
                if (input.equals("exit")) {
                    exit = true;
                    if (!updating) {
                        updater.interrupt();
                    }
                    return;
                } else if (input.startsWith("colour")) {
                    updateImage(input);
                } else if (input.equals("pick pixels")) {
                    if (updating) {
                        try {
                            synchronized (Thread.currentThread()){
                                Thread.currentThread().wait(MAX_TIME);
                            }
                        } catch (InterruptedException ignored) {
                        }
                    }
                    for (int i = 0; i < N && !border.isEmpty(); i++) {
                        borderLock.lock();
                        Pixel p = border.poll();
                        borderSet.remove(p);
                        borderLock.unlock();
                        if (!p.isBorder()){
                            i--;
                            continue;
                        }
                        updateImage(MY_TYPE, p);
                        System.out.print(p.x + "," + p.y + " ");
                    }
                    System.out.println();
                }
            }
        } catch (Throwable e){
            exit = true;
            if (!updating){
                updater.interrupt();
            }
            throw e;
        }
    }

    private void updateImage(byte type, Pixel... pixels) {
        for (Pixel pixel : pixels){
            pixel.setType(type);
            if (type == MY_TYPE){
                pixel.setPriority(Integer.MAX_VALUE);
            } else {
                pixel.setPriority(0);
            }
        }
        for (Pixel pixel : pixels){
            for (Pixel p : pixel.pixelsAround()){
                if (p.type() == BLANK_TYPE){
                    addPixelToUpdate(p);
                }
                if (type == MY_TYPE && p.isBorder()){
                    borderLock.lock();
                    if (borderSet.add(p)){
                        border.add(p);
                    }
                    borderLock.unlock();
                }
            }
        }
    }

    private synchronized void addPixelToUpdate(Pixel p) {
        if (pixelsToUpdateSet.add(p)) {
            pixelsToUpdate.add(p);
            if (!updating){
                updater.interrupt();
            }
        }
    }

    Queue<Pixel> pixelsToUpdate;
    Set<Pixel> pixelsToUpdateSet;

    private void update(){
        while (true){
            if (exit){
                return;
            }
            if (pixelsToUpdate.isEmpty()){
                try {
                    updating = false;
                    while (!exit) {
                        synchronized (Thread.currentThread()) {
                            Thread.currentThread().wait();
                        }
                    }
                } catch (InterruptedException ignored){}
                continue;
            }
            updating = true;
            Pixel pixel = pixelsToUpdate.poll();
            if (pixel.type() != BLANK_TYPE){
                continue;
            }
            pixelsToUpdateSet.remove(pixel);
            updatePixel(pixel);
        }
    }

    private void updatePixel(Pixel pixel) {
        int originalPriority = pixel.priority();
        int minPriority = Integer.MAX_VALUE;
        List<Pixel> pixelsAround = pixel.pixelsAround();
        for (Pixel p : pixelsAround){
            int priority = p.priority();
            if (priority < minPriority){
                minPriority = priority;
            }
        }
        if (minPriority >= originalPriority){
            pixel.setPriority(Integer.MAX_VALUE);
            pixelsToUpdate.addAll(pixelsAround.stream().filter(p -> p.type() == 0 && p.priority() != Integer.MAX_VALUE).filter(pixelsToUpdateSet::add).collect(Collectors.toList()));
        } else {
            pixel.setPriority(minPriority + 1);
            for (Pixel p : pixelsAround){
                if (p.type() == 0 && p.priority() > minPriority + 2){
                    if (pixelsToUpdateSet.add(p)){
                        pixelsToUpdate.add(p);
                    }
                }
            }
        }

    }

    private void updateImage(String input) {
        String[] inputs = input.split("\\s");
        int color = parseColorString(inputs[1]);
        byte type;
        if (color == this.color){
            return;
        } else {
            type = ENEMY_TYPE;
        }
        Pixel[] pixels = new Pixel[inputs.length - 3];
        for (int i = 0; i < inputs.length - 3; i++){
            String[] coords = inputs[i + 3].split(",");
            pixels[i] = new Pixel(Integer.parseInt(coords[0]), Integer.parseInt(coords[1]));
        }
        updateImage(type, pixels);
    }

    private static int parseColorString(String input) {
        String[] colorString = input.split("[\\(\\),]");
        return new Color(Integer.parseInt(colorString[1]), Integer.parseInt(colorString[2]), Integer.parseInt(colorString[3])).getRGB();
    }

    private Swallower(BufferedImage image, int color, int N){
        this.color = color;
        this.N = N;
        this.width = image.getWidth();
        this.height = image.getHeight();
        this.image = new byte[width][height];
        this.priority = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                int pixelColor = image.getRGB(x,y);
                priority[x][y] = Integer.MAX_VALUE;
                if (pixelColor == WHITE){
                    this.image[x][y] = BLANK_TYPE;
                } else if (pixelColor == this.color){
                    this.image[x][y] = MY_TYPE;
                } else {
                    this.image[x][y] = NEUTRAL_TYPE;
                }
            }
        }
        border = new PriorityBlockingQueue<>();
        borderSet = Collections.synchronizedSet(new HashSet<>());
        borderLock = new ReentrantLock();
        priorityLock = new ReentrantLock();
        imageLock = new ReentrantLock();
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                Pixel pixel = new Pixel(x,y);
                if (pixel.type() == BLANK_TYPE){
                    if (pixel.isBorder()){
                        if (borderSet.add(pixel)){
                            border.add(pixel);
                        }
                    }
                }
            }
        }
        in = new BufferedReader(new InputStreamReader(System.in));
        updating = false;
        updater = new Thread(this::update);
        pixelsToUpdate = new ConcurrentLinkedQueue<>();
        pixelsToUpdateSet = Collections.synchronizedSet(new HashSet<>());
        exit = false;
    }

}

```

# How it works:

This bot maintains a priority queue of pixels it can add. The priority of an enemy pixel is 0. The priority of a blank pixel is 1 greater than the lowest priority around it. All other pixels have a priority of Integer.MAX\_VALUE. The updater thread is constantly updating the priorities of the pixels. Every turn the lowest N pixels are popped off the priority queue.

# Green Blob vs Red Swallower

# Blob's Score = 1.680553372583887225

# Swallower's Score = 169.4020975612382575

# Arena 1:

```
Bot Blob.py with colour (0, 255, 0) scored 1.2183333333333333
Bot Swallower.class with colour (255, 0, 0) scored 177.435

```

# Arena 2:

```
Bot Swallower.class with colour (255, 0, 0) scored 149.57829253338517
Bot Blob.py with colour (0, 255, 0) scored 0.5159187091564356

```

# Arena 3:

```
Bot Blob.py with colour (0, 255, 0) scored 0.727104853136361
Bot Swallower.class with colour (255, 0, 0) scored 163.343720545521

```

# Arena 4:

```
Bot Swallower.class with colour (255, 0, 0) scored 187.25137716604686
Bot Blob.py with colour (0, 255, 0) scored 4.260856594709419

```

# Green Swallower vs. Red Blob

# Blob's Score = 1.6852943642218457375

# Swallower's Score = 169.3923095387498625

# Arena 1:

```
Bot Blob.py with colour (255, 0, 0) scored 1.3166666666666667
Bot Swallower.class with colour (0, 255, 0) scored 177.33666666666667

```

# Arena 2:

```
Bot Swallower.class with colour (0, 255, 0) scored 149.57829253338517
Bot Blob.py with colour (255, 0, 0) scored 0.49573058575466195

```

# Arena 3:

```
Bot Swallower.class with colour (0, 255, 0) scored 163.14367053301788
Bot Blob.py with colour (255, 0, 0) scored 0.9271548656394868

```

# Arena 4:

```
Bot Swallower.class with colour (0, 255, 0) scored 187.51060842192973
Bot Blob.py with colour (255, 0, 0) scored 4.0016253388265675

```

# Red Swallower vs Green Depth First Blob

# Swallower's Score = 157.0749775233111925

# Depth First Blob's Score = 18.192783547939744

# Arena 1:

```
Bot Swallower.class with colour (255, 0, 0) scored 173.52166666666668
Bot dfblob.py with colour (0, 255, 0) scored 5.131666666666667

```

# Arena 2:

```
Bot dfblob.py with colour (0, 255, 0) scored 17.25635925887156
Bot Swallower.class with colour (255, 0, 0) scored 149.57829253338517

```

# Arena 3:

```
Bot Swallower.class with colour (255, 0, 0) scored 153.59801488833747
Bot dfblob.py with colour (0, 255, 0) scored 10.472810510319889

```

# Arena 4:

```
Bot dfblob.py with colour (0, 255, 0) scored 39.91029775590086
Bot Swallower.class with colour (255, 0, 0) scored 151.60193600485545

```

# Green Swallower vs Red Depth First Blob

# Swallower's Score = 154.3368355651281075

# Depth First Blob's Score = 18.84463249420435425

# Arena 1:

```
Bot Swallower.class with colour (0, 255, 0) scored 165.295
Bot dfblob.py with colour (255, 0, 0) scored 13.358333333333333

```

# Arena 2:

```
Bot dfblob.py with colour (255, 0, 0) scored 8.91118721119768
Bot Swallower.class with colour (0, 255, 0) scored 149.57829253338517

```

# Arena 3:

```
Bot Swallower.class with colour (0, 255, 0) scored 157.01136822667206
Bot dfblob.py with colour (255, 0, 0) scored 7.059457171985304

```

# Arena 4:

```
Bot dfblob.py with colour (255, 0, 0) scored 46.0495522603011
Bot Swallower.class with colour (0, 255, 0) scored 145.4626815004552

```

# Green Blob vs Red Depth First Blob vs Blue Swallower:

# Blob's Score = 6.347962032393275525

# Depth First Blob's Score = 27.34842554331698275

# Swallower's Score = 227.720728953415375

# Arena 1:

```
Bot Swallower.class with colour (0, 0, 255) scored 242.54
Bot Blob.py with colour (0, 255, 0) scored 1.21
Bot dfblob.py with colour (255, 0, 0) scored 24.3525

```

# Arena 2:

```
Bot dfblob.py with colour (255, 0, 0) scored 17.828356088588478
Bot Blob.py with colour (0, 255, 0) scored 0.9252889892479551
Bot Swallower.class with colour (0, 0, 255) scored 224.36743880007776

```

# Arena 3:

```
Bot dfblob.py with colour (255, 0, 0) scored 7.105141670032893
Bot Swallower.class with colour (0, 0, 255) scored 226.52057245080502
Bot Blob.py with colour (0, 255, 0) scored 12.621905476369092

```

# Arena 4:

```
Bot dfblob.py with colour (255, 0, 0) scored 60.10770441464656
Bot Blob.py with colour (0, 255, 0) scored 10.634653663956055
Bot Swallower.class with colour (0, 0, 255) scored 217.45490456277872

```

Here is Sam Yonnou's judge with a few changes so that you specify the files and the command separately:

```
import sys, re, random, os, shutil, subprocess, datetime, time, signal, io
from PIL import Image

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def place(loc, colour):
    # if valid, place colour at loc and return True, else False
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        if any(pix[p]==colour for p in plist if 0<=p[0]<W and 0<=p[1]<H):
            pix[loc] = colour
            return True
    return False

def updateimage(image, msg, bot):
    if not re.match(r'(\s*\d+,\d+)*\s*', msg):
        return []
    plist = [tuple(int(v) for v in pr.split(',')) for pr in msg.split()]
    plist = plist[:PIXELBATCH]
    return [p for p in plist if place(p, bot.colour)]

class Bot:
    botlist = []
    def __init__(self, progs, command=None, colour=None):
        self.prog = progs[0]
        self.botlist.append(self)
        self.colour = colour
        self.colstr = str(colour).replace(' ', '')
        self.faults = 0
        self.env = 'env%u' % self.botlist.index(self)
        try: os.mkdir(self.env)
        except: pass
        for prog in progs:
            shutil.copy(prog, self.env)
        shutil.copy(imagename, self.env)
        os.chdir(self.env)
        args = command + [imagename, self.colstr, str(PIXELBATCH)]
        errorfile = 'err.log'
        with io.open(errorfile, 'wb') as errorlog:
            self.proc = subprocess.Popen(args, stdin=subprocess.PIPE,
                stdout=subprocess.PIPE, stderr=errorlog)
        os.chdir('..')
    def send(self, msg):
        if self.faults < FAULTLIMIT:
            self.proc.stdin.write((msg+'\n').encode('utf-8'))
            self.proc.stdin.flush()
    def read(self, timelimit):
        if self.faults < FAULTLIMIT:
            start = time.time()
            inline = self.proc.stdout.readline().decode('utf-8')
            if time.time() - start > timelimit:
                self.faults += 1
                inline = ''
            return inline.strip()
    def exit(self):
        self.send('exit')

from cfg import *
for i, (progs, command) in enumerate(botspec):
    Bot(progs, command, colourspec[i])

image = Image.open(imagename)
pix = image.load()
W,H = image.size
resultdirectory = 'results of ' + BATTLE
os.mkdir(resultdirectory)

time.sleep(INITTIME)
total = 0
image.save(resultdirectory+'/'+'result000.png')
for turn in range(1, MAXTURNS+1):
    random.shuffle(Bot.botlist)
    nullbots = 0
    for bot in Bot.botlist:
        bot.send('pick pixels')
        inmsg = bot.read(TIMELIMIT)
        newpixels = updateimage(image, inmsg, bot)
        total += len(newpixels)
        if newpixels:
            pixtext = ' '.join('%u,%u'%p for p in newpixels)
            msg = 'colour %s chose %s' % (bot.colstr, pixtext)
            for msgbot in Bot.botlist:
                msgbot.send(msg)
        else:
            nullbots += 1
    if nullbots == len(Bot.botlist):
        break
    if turn % 100 == 0:
        print('Turn %s done %s pixels' % (turn, total))
        image.save(resultdirectory+'/result'+str(turn//100).zfill(3)+'.png')
image.save(resultdirectory+'/result999.png')
for msgbot in Bot.botlist:
    msgbot.exit()

resultfile = io.open(resultdirectory+'/result.txt','w')
counts = dict((c,f) for f,c in image.getcolors(W*H))
avg = 1.0 * sum(counts.values()) / len(Bot.botlist)
for bot in Bot.botlist:
    score = 100 * counts[bot.colour] / avg
    print('Bot %s with colour %s scored %s' % (bot.prog, bot.colour, score))
    print('Bot %s with colour %s scored %s' % (bot.prog, bot.colour, score), file=resultfile)
image.save(BATTLE+'.png')

```

Example cfg:

```
BATTLE = 'Green DepthFirstBlob vs Red Swallower @ arena1'
MAXTURNS = 20000
PIXELBATCH = 10
INITTIME = 2.0
TIMELIMIT = .1
FAULTLIMIT = 5

imagename = 'arena1.png'

colourspec = (0,255,0), (255,0,0)

botspec = [
    (['DepthFirstBlob.py'], ['python', 'DepthFirstBlob.py']),
    (['Swallower.class','Swallower$Pixel.class'], ['java', 'Swallower']),
    ]

```

*Note:* Anyone that manages to swallow the Swallower get's a bounty of 100 reputation. Please post in comments below if you succeed at this.

# Answer
> 6 votes
# Random, Language = java, Score = 0.43012126100275

This program randomly puts pixels on the screen. Some (if not all) of the pixels will not be valid. On a side note, it should be difficult to make a faster program than this one.

```
import javax.imageio.ImageIO;
import java.awt.image.BufferedImage;
import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;

public class Random {

    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    static int n;

    static int height;

    static int width;

    public static void main(String[] args) throws Exception{
        BufferedImage image = ImageIO.read(new File(args[0]));
        height = image.getHeight();
        width = image.getWidth();
        n = Integer.parseInt(args[2]);
        while (true){
            String input = in.readLine();
            if (input.equals("exit")){
                return;
            }
            if (!input.equals("pick pixels")){
                continue;
            }
            for (int i = 0; i < n; i++){
                System.out.print((int) (Math.random() * width) + ",");
                System.out.print((int) (Math.random() * height) + " ");
            }
            System.out.println();
        }
    }
}

```

Arena 1:

Arena 2:

Arena 3:

Arena 4:

---
Tags: code-challenge, graphical-output, image-processing
---