title: Build a small and balanced mobile

text:
# Question
Title: Build a small and balanced mobile
You are given a bunch of weights, and your task is to build a small balanced mobile using those weights.

The input is a list of integer weights in the range 1 through 9, inclusive. There may be duplicates.

The output is an ascii picture of a mobile that, when hung, would balance. Perhaps best shown by example:

**input**

```
3 8 9 7 5

```

**possible output**

```
         |
   +-----+---------+
   |               |
+--+-+        +----+------+
|    |        |           |
8   ++--+     7           5
    |   |
    9   3

```

You must use the ascii characters as shown. The horizontal and vertical segments may be of any length. No part of the mobile may touch (horizontally or vertically) another unconnected part of the mobile. All weights must be hung from a vertical segment of length at least 1, and there must be a vertical segment from which the whole mobile is hung.

The size of a mobile is the total number of `+`,`-`,and `|` characters required to build it. Lower sizes are better.

You may put as many connections on a segment as you would like. For example:

**input**

```
2 3 3 5 3 9

```

**possible output**

```
           |
   +---+---+-----------+
   |   |               |
+--+-+ 5               9
|  | |
2  | 3
   |
  +++
  | |
  3 3

```

The winning program is the one that can generate the lowest average of mobile sizes for a test set of inputs. The real test is super-secret to prevent hard-coding, but it will be something like this:

```
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 7
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 7 7
3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7

```

# Answer
Python 2.

I'm cheating a ~~little~~ bit:

* I only construct mobiles with one horizontal. ~~I have a feeling (but I haven't proven it) that the optimal mobile under the given conditions actually always *does* only have one horizontal.~~ **Edit:** Not always true; with `2 2 9 1` Nabb has found a counter-example in the comments below:

```
Size 18:                Size 16:
   |                        |
+-++--+-----+            +--++-+
| |   |     |            |   | |
2 9   2     1           -+-  9 1
                        | |
                        2 2

```
* I just do stupid brute-forcing:

1. The given weights are shuffled randomly.
    2. Two weights at a time are placed on the mobile in the best positions such that it stays balanced.
    3. If the resulting mobile is better than any that we had before, remember it.
    4. Rinse and repeat, until a pre-defined number of seconds is up.

My results for your sample inputs; each was run for 5 seconds (I'm aware that this is ridiculous for the small ones – just going through all possible permutations would be faster). Note that since there's a random element, subsequent runs may find better or worse results.

```
3 8 9 7 5
Tested 107887 mobiles, smallest size 20:
        |
+-+-----+-+--+
| |     | |  |
5 3     7 9  8

2 3 3 5 3 9
Tested 57915 mobiles, smallest size 23:
      |
+--+-++--+-+---+
|  | |   | |   |
3  5 9   3 3   2

8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 7
Tested 11992 mobiles, smallest size 50:
                |
+-+-+-+--+-+-+-+++-+-+--+-+-+-+-+
| | | |  | | | | | | |  | | | | |
8 8 8 8  8 8 8 8 8 8 8  7 8 8 8 8

1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 7 7
Tested 11119 mobiles, smallest size 62:
                    |
+-+-+-+-+-+--+-+-+-+++-+-+-+--+-+-+-+-+-+
| | | | | |  | | | | | | | |  | | | | | |
2 7 5 6 6 8  3 2 3 7 9 7 8 1  1 7 9 5 4 4

3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7
Tested 16301 mobiles, smallest size 51:
                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | |
4 6 5 7 7 4 6 5 3 5 6 4 7 6 7 5 4

```

The code (verbose, as this isn't code golf):

```
import time, random

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

class Mobile(object):
    def __init__(self):
        self.contents = [None];
        self.pivot = 0;

    def addWeights(self, w1, w2):
        g = gcd(w1, w2)
        m1 = w2 / g
        m2 = w1 / g
        mul = 0
        p1 = -1
        while True:
            if p1 < 0:
                mul += 1
                p1 = mul * m1
                p2 = -mul * m2
            else:
                p1 *= -1
                p2 *= -1
            if self.free(p1) and self.free(p2):
                self.add(w1, p1)
                self.add(w2, p2)
                return

    def add(self, w, pos):
        listindex = self.pivot - pos
        if listindex < 0:
            self.contents = [w] + (abs(listindex) - 1) * [None] + self.contents
            self.pivot += abs(listindex)
        elif listindex >= len(self.contents):
            self.contents += (listindex - len(self.contents)) * [None] + [w]
        else:
            self.contents[listindex] = w

    def at(self, pos):
        listindex = self.pivot - pos
        if 0 <= listindex < len(self.contents):
            return self.contents[listindex]
        return None

    def free(self, pos):
        return all(self.at(pos + d) is None for d in (-1, 0, 1))

    def score(self):
        return 1 + 2 * len(self.contents) - self.contents.count(None)

    def draw(self):
        print self.pivot * " " + "|"
        print "".join("+" if c is not None or i == self.pivot else "-" for i, c in enumerate(self.contents))
        print "".join("|" if c is not None else " " for c in self.contents)
        print "".join(str(c) if c is not None else " " for c in self.contents)

    def assertBalance(self):
        assert sum((i - self.pivot) * (c or 0) for i, c in enumerate(self.contents)) == 0

weights = map(int, raw_input().split())

best = None
count = 0

# change the 5 to the number of seconds that are acceptable
until = time.time() + 5

while time.time() < until:
    count += 1
    m = Mobile()

    # create a random permutation of the weights
    perm = list(weights)
    random.shuffle(perm)

    if len(perm) % 2:
        # uneven number of weights -- place one in the middle
        m.add(perm.pop(), 0)

    while perm:
        m.addWeights(perm.pop(), perm.pop())

    m.assertBalance() # just to prove the algorithm is correct :)
    s = m.score()
    if best is None or s < bestScore:
        best = m
        bestScore = s

print "Tested %d mobiles, smallest size %d:" % (count, best.score())
best.draw()

```
> 5 votes

# Answer
Here is a solution that brute forces the smallest single row solution. The code iterates over all permutations and compute the center of mass for each. If the center of mass has integer coordinates, we've found a solution.

After all permutations have been tried, we add a segment to the mix (equivalent to a weight of mass 0) in our current set of weights and retry.

To run the program, do `python balance.py 1 2 2 4`.

```
#!/usr/bin/env python3
import itertools, sys

# taken from http://stackoverflow.com/a/30558049/436792
def unique_permutations(elements):
    if len(elements) == 1:
        yield (elements[0],)
    else:
        unique_elements = set(elements)
        for first_element in unique_elements:
            remaining_elements = list(elements)
            remaining_elements.remove(first_element)
            for sub_permutation in unique_permutations(remaining_elements):
                yield (first_element,) + sub_permutation

def print_solution(cm, values):
    print(('  ' * cm) + '|')
    print('-'.join(['-' if v == 0 else '+'  for v in values]))
    print(' '.join([' ' if v == 0 else '|'  for v in values]))
    print(' '.join([' ' if v == 0 else str(v) for v in values]))

input = list(map(int, sys.argv[1:]))
mass = sum(input)
while True:
    n = len(input)
    permutations = filter(lambda p: p[0] != 0 and p[n-1] != 0, unique_permutations(input))
    for p in permutations:
        cm = 0
        for i in range(n):
            cm += p[i] * i;
        if (cm % mass == 0):
            print_solution(cm//mass, p)
            sys.exit(0)
    input.append(0)

```

which produces these best solutions :

```
    |
+-+-+-+-+
| | | | |
8 3 9 5 7

    |
+-+-+-+-+-+
| | | | | |
9 2 3 5 3 3

                |
+-+-+-+-+-+-+---+-+-+-+-+-+-+-+-+
| | | | | | |   | | | | | | | | |
8 8 8 8 8 8 8   8 8 8 8 8 8 8 8 7

                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | | | | |
1 1 2 2 3 3 4 4 8 8 5 5 6 6 7 7 7 7 9 9

                  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | |
3 4 4 4 4 5 5 5 5 6 7 6 7 7 7 6 6

```
> 1 votes

# Answer
Well this is an old question, but I just saw it appear in the top questions tab so here's my (optimal) solution:

```
#include <stdio.h>
#include <limits.h>
#include <math.h>
#include <stdlib.h>

int main(int argc, const char *const *argv) {
    if(argc < 2) {
        fprintf(stderr,
            "Balances weights on a hanging mobile\n\n"
            "Usage: %s <weight1> [<weight2> [...]]\n",
            argv[0]
        );
        return 1;
    }
    int total = argc - 1;
    int values[total];
    int maxval = 0;
    for(int n = 0; n < total; ++ n) {
        char *check = NULL;
        long v = strtol(argv[n+1], &check, 10);
        if(v <= 0 || v > INT_MAX || *check != '\0') {
            fprintf(stderr,
                "Weight #%d (%s) is not an integer within (0 %d]\n",
                n + 1, argv[n+1], INT_MAX
            );
            return 1;
        }
        values[n] = (int) v;
        if(values[n] > maxval) {
            maxval = values[n];
        }
    }
    int maxwidth = (int) log10(maxval) + 1;
    for(int n = 0; n < total; ++ n) {
        int width = (int) log10(values[n]) + 1;
        fprintf(stdout,
            "%*s\n%*d\n",
            (maxwidth + 1) / 2, "|",
            (maxwidth + width) / 2, values[n]
        );
    }
    return 0;
}

```

From looking at the rules I'm pretty sure it isn't cheating, although it feels like it is. This will just output all the given numbers in a vertical chain, for a total cost of 2\*number\_of\_inputs (which is the minimum possible because each number must have a bar above it no matter what the layout). Here's an example:

```
./mobile 3 8 9 7 5

```

Produces:

```
|
3
|
8
|
9
|
7
|
5

```

Which is of course in perfect balance.

---

I was originally going to try something more in the spirit of this challenge, but it quickly turned out that it just optimised away to this structure anyway
> 1 votes

# Answer
# Python 3

This does no worse than 1 more than optimal on any of the test cases, I believe, and does so in 5 seconds.

Basically, I use a single bar approach. I randomly order the input, then insert the weights onto the bar one at a time. Each element is either put in the position that minimizes the excess weight on either side, or the second best position from that perspective, using the former 75% of the time and the latter 25% of the time. Then, I check whether the mobile is balanced at the end, and is better than the best mobile found so far. I store the best one, then halt and print it out after 5 seconds of searching.

Results, in 5 second runs:

```
py mobile.py <<< '3 8 7 5 9'
Best mobile found, score 15:
    |
+-+-+-+-+
| | | | |
8 7 3 5 9
py mobile.py <<< '2 2 1 9'
Best mobile found, score 13:
   |
+-++-+-+
| |  | |
1 9  2 2
py mobile.py <<< '2 3 3 5 3 9'
Best mobile found, score 18:
      |
+-+-+-+-+-+
| | | | | |
2 3 3 5 9 3
py mobile.py <<< '8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 7'
Best mobile found, score 49:
                |
+-+--+-+-+-+-+-+++-+-+-+-+-+-+-+
| |  | | | | | | | | | | | | | |
7 8  8 8 8 8 8 8 8 8 8 8 8 8 8 8
\py mobile.py <<< '1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 7 7'
Best mobile found, score 61:
                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+
| | | | | | | | | | | | | | | | | | |  |
1 7 7 5 4 3 1 9 6 7 8 2 2 9 3 7 6 5 8  4
py mobile.py <<< '3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7'
Best mobile found, score 51:
                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | |
4 4 6 7 7 4 5 7 6 6 5 4 6 3 5 5 7

```

Code:

```
import random
import time

class Mobile:
    def __init__(self):
        self.contents = {}
        self.lean = 0

    def usable(self, loc):
        return not any(loc + k in self.contents for k in (-1,0,1))
    def choose_point(self, w):
        def goodness(loc):
            return abs(self.lean + w * loc)
        gl = sorted(list(filter(self.usable,range(min(self.contents.keys() or [0]) - 5,max(self.contents.keys() or [0]) + 6))), key=goodness)
        return random.choice((gl[0], gl[0], gl[0], gl[1]))

    def add(self, w, loc):
        self.contents[loc] = w
        self.lean += w*loc

    def __repr__(self):
        width = range(min(self.contents.keys()), max(self.contents.keys()) + 1)
        return '\n'.join((''.join(' ' if loc else '|' for loc in width),
                          ''.join('+' if loc in self.contents or loc == 0 else '-' for loc in width),
                          ''.join('|' if loc in self.contents else ' ' for loc in width),
                          ''.join(str(self.contents.get(loc, ' ')) for loc in width)))

    def score(self):
        return max(self.contents.keys()) - min(self.contents.keys()) + len(self.contents) + 2

    def my_score(self):
        return max(self.contents.keys()) - min(self.contents.keys()) + 1

best = 1000000
best_mob = None
in_weights = list(map(int,input().split()))
time.clock()
while time.clock() < 5:
    mob = Mobile()
    for insert in random.sample(in_weights, len(in_weights)):
        mob.add(insert, mob.choose_point(insert))
    if not mob.lean:
        if mob.score() < best:
            best = mob.score()
            best_mob = mob

print("Best mobile found, score %d:" % best_mob.score())
print(best_mob)

```

The only one of these solutions which I believe is suboptimal is the longest one, which has this solution, which I found after a 10 minute run:

```
Best mobile found, score 60:
                   |
+-+-+-+-+-+-+-+-+-+++-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | | | | |
3 2 9 4 7 8 1 6 9 8 7 1 6 2 4 5 7 3 5 7

```
> 0 votes

---
Tags: code-challenge, math, ascii-art
---


title: Find the right path

text:
# Question
Title: Find the right path
Given a list of paths, output the correct path.

Example of path:

```
    /\
----+/
    |

```
* `-` and `|` are horizontal and vertical paths.
* `/` and `\` are 90° turns.
* `+` is treated as a `-` or a `|` depending of the current direction.

Paths may go in any direction and a character may be used in multiple paths.

Input will be like this:

```
       /--\
A------+--+--#
B------/  \--:
C------------#
D------------#

```
* `A`, `B`, `C` and `D` are path starts
* `#` is a wall (the path is bad)
* `:` is the end (the path is correct)

So here the output will be `B`.

You can assume:

* `:` and `#` will always be reached from the left.
* The character at the right of the start of a path will always be `-`.
* Paths will always be well formed.
* `#` and `:` will always be in the same column.
* There will always be only one `:` and 4 paths.

## Test cases

```
A------#
B------#
C------#
D------:
=>
D

```

```
A-\ /---:
B-+-/ /-#
C-+---+-#
D-+---/
  \-----#
=>
B

```

```
  /-\
A-+\\---#
B-/\-\/-#
C----++-#
D----+/
     \--:
=>
A

```

```
A-\
B-+\
C-++\/----#
D-+++//---:
  \++-//--#
   \+--//-#
    \---/
=>
A

```

```
  /-\
A-+-/-\
B-+-+-\--#
C-+-/ |/-#
D-\---++-#
  \---+/
      \--:
=>
B

```

Since this is , the shortest answer win.

# Answer
> 14 votes
## Slip, 47 bytes

```
`a(?,[`-+]*((`/<|`\>)[`|+]*(`/>|`\<)[`-+]*)*`:)

```

Test it here.

Yay for undocumented features...

### Explanation

Slip is basically a two dimensional regex syntax and by default Slip programs print the subset of the input that they matched. In this case I'm simply matching a valid path. To prevent printing the entire path, I'm usng the undocumented `(?,...)` groups which simply indicate that the characters matched inside should be omitted from the output.

As for the regex, unfortunately, there's some duplication because `\` and `/` need to be treated differently depending on whether we're moving horizontally or vertically. On the plus side, since we know that the path starts and ends horizontally, we know that there's an even number of `\` or `/` in every path, so that we can match two of them at a time.

```
`a             # Match a letter.
(?,            # Match but don't include in output...
  [`-+]*       #   Match a horizontal piece of path, consisting of - or +.
  (            #   Match 0 or more vertical segments...
    (`/<|`\>)  #     Match a / and turn left, or a \ and turn right.
    [`|+]*     #     Match a vertical piece of path, consisting of | or +.
    (`/>|`\<)  #     Match a / and turn right, or a \ and turn left.
    [`-+]*     #     Match a horizontal piece of path, consisting of - or +.
  )*
  `:           #   Match a : to ensure that this is the correct path.
)

```

# Answer
> 6 votes
# Python, 221 bytes

```
def P(s,c=""):
 l=s.split("\n")
 v=[0,-1]
 p=[(i,l[i].index(":"))for i in range(len(l))if":"in l[i]][0]
 while c in"-:|+/\\":
    p=map(sum,zip(p,v))
    c=l[p[0]][p[1]]
    v=v[::1-(c=="\\")*2]
    if"/"==c:v=[-v[1],-v[0]]
 return c

```

The first indention is just one space, in the while loop it's a tab.

# Answer
> 2 votes
# Javascript (ES6), ~~117~~ 104 bytes

```
p=>(r=d=>(c="\\/ABCD".indexOf(p[x+=[-1,-w,w,1][d]])+1)>2?p[x]:r(d^c))(0,w=p.indexOf`
`+1,x=p.indexOf`:`)

```

Test cases:

```
let f =
p=>(r=d=>(c="\\/ABCD".indexOf(p[x+=[-1,-w,w,1][d]])+1)>2?p[x]:r(d^c))(0,w=p.indexOf`
`+1,x=p.indexOf`:`)

var p0 = 'A------#\nB------#\nC------#\nD------:',
    p1 = 'A-\\ /---:\nB-+-/ /-#\nC-+---+-#\nD-+---/  \n  \\-----#',
    p2 = '  /-\\    \nA-+\\\\---#\nB-/\\-\\/-#\nC----++-#\nD----+/  \n     \\--:',
    p3 = 'A-\\        \nB-+\\       \nC-++\\/----#\nD-+++//---:\n  \\++-//--#\n   \\+--//-#\n    \\---/  ',
    p4 = '  /-\\     \nA-+-/-\\   \nB-+-+-\\--#\nC-+-/ |/-#\nD-\\---++-#\n  \\---+/  \n      \\--:';

console.log(p0, '=>', f(p0));
console.log(p1, '=>', f(p1));
console.log(p2, '=>', f(p2));
console.log(p3, '=>', f(p3));
console.log(p4, '=>', f(p4));
```

# Answer
> 1 votes
# Ruby, 140 bytes

```
->s{(?A..?D).find{|l,c|x=h=1
v=0
y=s[/.*#{l}/m].count$/
(v,h=c==?/?[-h,-v]:c==?\\?[h,v]:[v,h]
y+=v
x+=h)until(c=s.lines[y][x])=~/(:)|#/
$1}}

```

Try it on repl.it: https://repl.it/CyJv

## Ungolfed

```
->s{
  (?A..?D).find {|l,c|
    x = h = 1
    v = 0
    y = s[/.*#{l}/m].count $/

    ( v, h = c == ?/ ? [-h,-v] : c == ?\\ ? [h,v] : [v,h]
      y += v
      x += h
    ) until (c = s.lines[y][x]) =~ /(:)|#/

    $1
  }
}

```

# Answer
> 0 votes
# Perl 211 Bytes

```
sub f{for($s=-1;++$s<~~@_;){if($_[$s][0]ne' '){$r=$s;$c=$m=0;$n=1;while($_[$r][$c]ne'#'){if($_[$r][$c]eq':'){return$_[$s][0];}($m,$n)=$_[$r][$c]eq'/'?(-$n,-$m):$_[$r][$c]eq'\\'?($n,$m):($m,$n);$r+=$m;$c+=$n;}}}}

```

Ungolfed:

```
sub q{
    for($start = -1; ++$start <~~@_;) {
        if($_[$start][0] ne ' ') {
            $row = $start;
            $col = $rowMove = 0;
            $colMove = 1;
            while($_[$row][$col] ne '#') {
                if($_[$row][$col] eq ':') {
                    return $_[$start][0];
                }
                ($rowMove, $colMove) =  $_[$row][$col] eq '/' ? (-$colMove,-$rowMove) :
                                        $_[$row][$col] eq '\\' ? ($colMove,$rowMove) :
                                        ($rowMove, $colMove);
                $row += $rowMove;
                $col += $colMove;
            }
        }
    }
}

```

This is my first Perl golf, so suggestions are welcome :)

---
Tags: code-golf, ascii-art, path-finding
---


# Question
Title: Write a program that outputs the number of times it has been run
In a programming language of your choice, write a full program that, when run, prints a positive integer N and then modifies its own source file such that the next time it is run it will print N+1.

For example, this (ungolfed) Python 3 program satisfies this behavior:

```
N = 1
print(N)
with open(__file__, 'r+') as f:
    N = int(f.readline()[4:]) + 1
    code = 'N = ' + str(N) + '\n' + f.read()
    f.seek(0)
    f.write(code)

```

Right away it declares and prints N, then it opens itself and rewrites its first line so the declared value of N is incremented. Then it copies the rest of its code verbatim and writes the new code to the same file, resulting in a program that will print N+1 when run again.

If the file were named `incr.py`, running it on the command line would look something like this:

```
C:\somepath> python incr.py
1
C:\somepath> python incr.py
2
C:\somepath> python incr.py
3
C:\somepath> python incr.py
4

```

At this point, `incr.py` would read:

```
N = 5
print(N)
with open(__file__, 'r+') as f:
    N = int(f.readline()[4:]) + 1
    code = 'N = ' + str(N) + '\n' + f.read()
    f.seek(0)
    f.write(code)

```

Your program should behave essentially the same as this Python example, though of course your program structure may be very different, even changing as N increases. (You don't need to define N as a plain integer on the first line, for example.)

Give the program that prints `1` in your answer. Programs for all higher N can then be inferred. **The shortest `1`-printing program in bytes wins.**

## Notes

* The output should be the sole number N in decimal (or your language's most natural base), followed optionally by a trailing newline.
* Your program must actually rewrite its own source code file, not simply output its modified source like a quine.
* The file name and/or path of the source file may be hardcoded into your program (e.g. `'incr.py'` could have replaced `__file__` in the Python example) but the program's behavior should not depend on them. If the file is moved or renamed it should be easy enough to rewrite the program accordingly.
* The source file's name and path should *not* change during execution.
* Temporary files may be made (to copy code to or whatever) but they should be removed before the main program ends. Specifically, the only side effects of running your program should be:

1. Printing N to stdout.
    2. Changing the source file so it will print N+1 when next run.

# Answer
# bash (+ wc \+ id), 16 bytes

```
wc -l<$0;id>>$0

```

Counts its lines, then appends a line of garbage to itself.

Needs a trailing newline.

Crashes on line 2 with a syntax error, which thankfully prints to STDERR and exits.

After three invocations, the script looks like this for me:

```
wc -l<$0;id>>$0
uid=1000(lynn) gid=1000(lynn) groups=1000(lynn),4(adm),24(cdrom),27(sudo),30(dip),46(plugdev),113(lpadmin),128(sambashare)
uid=1000(lynn) gid=1000(lynn) groups=1000(lynn),4(adm),24(cdrom),27(sudo),30(dip),46(plugdev),113(lpadmin),128(sambashare)
uid=1000(lynn) gid=1000(lynn) groups=1000(lynn),4(adm),24(cdrom),27(sudo),30(dip),46(plugdev),113(lpadmin),128(sambashare)

```
> 22 votes

# Answer
# Python 2, 31 bytes

```
open(*'aa').write('+1');print 1

```

Simply appends `+1` to the source file upon execution. This program assumes that the source file is named as `a`. It can be easily modified to work with an arbitrary filename at 38 bytes as follows:

```
open(__file__,'a').write('+1');print 1

```

Additionally, a 37 bytes alternative exists though it isn't valid due to the 'no temporary files' rule:

```
f=open(*'aa')
print>>f
print f.tell()

```

This program appends a newline to the file `a` which is assumed not to exist before the first execution of the program. Then, the program prints the file size of `a` which is simply `f.tell()` since the file object is now pointing to the end of the file after appending.
> 13 votes

# Answer
# Perl (+shell), 30 bytes

`self.pl`:

```
#!/usr/bin/perl
print 1;`$^X -pi -es/1/1+1/ $0`

```

Works as shown, but replace `^X` by the literal control byte for the claimed score. This does lead to a warning on recent perl versions though.

Because the filename is passed through the shell it should not contain any special characters.

A pure perl version weights in at 32 bytes (or 33 if you add a `-X` option to suppress the `-i` warning)

```
#!/usr/bin/perl -pi
INIT{print 1;@ARGV=$0}s/1/1+1/

```

If you don't mind calling with `perl -M5.010` in both version 2 more bytes can be removed by using `say` instead of `print`
> 6 votes

# Answer
# Pyth - 7 bytes

Very simple, save as `o.txt`.

```
.wk)l"1

```

(btw to change filename, replace the paren for the `.w` with a string, like: `.wk"file.pyth"l"1`
> 5 votes

# Answer
## QBasic (QB64), 47 bytes

```
OPEN"C:\p.bas"FOR APPEND AS 1:?LOF(1)\2-22:?#1,

```

Adjust the path and filename as desired. Note: you must create the file `C:\p.bas` with an external text-editor (I used Notepad++) and make sure it does **not** contain a trailing newline. The QB64 editor adds one when you save the file, which throws off the math and the bytecount. (I assume actual QBasic would do the same, not to mention the auto-formatting.)

Here's an ungolfed version (which *does* expect a trailing newline):

```
OPEN "C:\p.bas" FOR APPEND AS 1
PRINT LOF(1) \ 2 - 32
PRINT #1,

```

**How it works**

The program opens its own code file in `APPEND` mode. It then uses `LOF` to get the length of the current version in bytes. To begin with, this is 47, so we calculate `LOF(1)\2-22` (where `\` is integer division) and print the resulting `1`.

Finally, we want to write some no-op to the end of the file. The shortest way to do this turns out to be writing *nothing*, with a trailing newline automatically added. Since this is Windows (or DOS), the newline is `\r\n`, adding two bytes and necessitating the division by 2 earlier in the code.

(Always `CLOSE` your files when you're done with them, kids. Unless you're golfing.)
> 5 votes

# Answer
# , 15 bytes

```
:e z
jñ:wñck0

```

*Or*, this readable version:

```
:e <C-r>z
j<C-a>ñ:wñck0

```

This will not work on the online interpreter, since it disallows file access.

Here is a hexdump:

```
00000000: 3a65 2012 7a0a 6a01 f13a 77f1 636b 30    :e .z.j..:w.ck

```

Explanation:

```
:e                   "Edit the following file:
   <C-r>z            "Insert the full path to the source file
j                    "Move down a line
 <C-a>               "And increment the first number on this line
      ñ:wñ           "Save this file. Surrounding it with 'ñ' is a fun little hack that allows this to appear on the same line
          ck         "Change this line and the line above us
            0        "To '0' (or whatever number we're on)

```
> 3 votes

# Answer
# PowerShell, 69/60 57

Further golfed and regex corrected based on feedback from TimmyD and Matt

```
($a=1);$a++;(gc($b=$PSCommandPath))-replace"\d+",$a|sc $b

```

69 for completely path and filename agnostic

```
($a=1)|oh;$a++;$b=$PSCommandPath;((gc $b)-replace"\d",$a)|Out-File $b

```

60 bytes if I can specify a fixed filename

```
($a=1)|oh;$a++;(gc .\a.ps1)-replace"\d",$a)|Out-File .\a.ps1

```

Explanation:

Sets $a to 1, returns it. Then it increments the variable, finds its own invocation path, brings that into memory and uses regex to replace digits with the value in $a, then writes to disk.
> 3 votes

# Answer
# Javascript (Node.js), 92 bytes

```
s=require('fs')
f=s.readFileSync(l=__filename)
console.log(f.length-91)
s.writeFile(l,f+';')

```

Prints out the length of the file minus 91, and adds a semicolon (which is ignored by the interpreter) to the final line of the file each time it is run
> 3 votes

# Answer
# C#, 124 bytes

```
namespace System.IO{class C{static void Main(){Console.Write(File.ReadAllLines("p").Length);File.AppendAllText("p","\n");}}}

```

Usage: Source file needs to be called `p`. If using Visual Studio, make sure the Build Action is set to Compile (not default for non-cs files). Also, under project properties ensure the the Output Path is the current directory (ie- empty text box) (again not a default setting).

How it works: It opens the source file and outputs the line count. Then it appends an empty line to the source file.

Pretty print version:

```
namespace System.IO // Put in System.IO namespace so no usings needed.
{
    class C
    {
        static void Main()
        {
            Console.Write(File.ReadAllLines("p").Length); // Write line count/run count
            File.AppendAllText("p","\n"); // Increment line count/run count
        }
    }
}

```
> 2 votes

# Answer
# PHP, 38 bytes

There are so many ways in PHP to do that ... this one´s the shortest I could find:

```
<?=stat(n)[7]-37;fputs(fopen(n,a),1);#

```

print file size (initially 38) -37, append a character (`1` in this case) to the comment at the end.

* save with file name `n`, call with `php n`
* make sure that the file contains no trailing newline
* `fclose` is called implicitly when the script finishes.
* if you pick another filename, replace `37` with the new file size -1.
* if filename gets longer than 5 characters (including eventual quotation marks), use `$n=filename` for the first occurence, `$n` for the second.
* if filename gets longer than 7 characters, use `__FILE__` instead of the literal file name.
> 2 votes

# Answer
# Dyalog APL, 21 bytes

Define `f` as the following:

```
(⎕FX⊢2-⍨⍴)'⍝',⍨⎕NR'f'

```

`⎕NR'f'` the **N**ested **R**epresentation of `f`; on the first run, this is {`f`, `(⎕FX⊢2-⍨⍴)'⍝',⍨⎕NR'f'`}

`'⍝',⍨` append a comment symbol, giving {`f`, `(⎕FX⊢2-⍨⍴)'⍝',⍨⎕NR'f'`, }

`(`...`)` apply the following function:

`⎕FX` **F**i**x** definition of `f`

then

`2-⍨` subtract two from

the length of the argument (3 on the first run)

Example run:

```
      f
1
      f
2
      f
3

```
> 2 votes

# Answer
## Batch, ~~70~~ 55 bytes

```
@cmd/cset/a-1>>%0
@call:l
@echo %n:~1%
:l
@set/an=0

```

Ensure that the file does not end in a newline. Use the full file name to invoke the file (e.g. `incr.bat`). Works by appending `-1` (`cmd/cset/a` does not output a trailing newline) to the end of the file on each run (including the first!) so that `n` is the negation of the desired result, then just strips off the leading minus sign when printing `n`.

Edit: Saved 8 bytes by removing an `exit/b` which had no visible effect. Saved 7 bytes by switching from `@echo off` to `@` prefixes on each line.
> 2 votes

# Answer
# R, 45 bytes

```
f=function(){body(f)[[3]]<<-body(f)[[3]]+1;1}

```

Not sure if a function counts as a "full program" but calling `f()` will return 1,2,... within the same R session. It also satisfies the self-modifying criterion.

It is necessary to use the double-harpoon operator `<<-` or else `f` will just make a local copy of itself and modify that instead. `<<-` forces that to happen at the top level.
> 1 votes

# Answer
## JavaScript (browser) (ES6), 84 bytes

```
s=document.querySelector('script');f=_=>eval(s.innerHTML);n=0;s.innerHTML+='n++;n;';

```

Run by calling `f()`. Note that this is reset on page load.

I assume that modifying the `<script>` tag counts as rewriting the source code.
> 0 votes

# Answer
# PowerShell ~~55~~ ~~53~~ 31 Bytes

```
"$(gc($p='.\1.ps1'))+1"|sc $p;1

```

Read in the file then just add +1 to the end of the file. Powershell will evaluate that as addition so for the fifth pass the file would have `....;1+1+1+1+1` which evaluates to five!

Old version using saved integer in a variable.

```
($a=1);$a++;(gc .\1.ps1)-replace'=\d+',"=$a"|sc .\1.ps1

```

Since we can hardcode a name it saves spaces over the script determining its own name. Printer the current value of `$a`. Increase $a by one. Using regex, replace the digits that follow an equal sign with the now updated value. Then write back to the original file.

If I change the way I locate the first number I can get down to 53. Using a newline I change my regex to look for numbers at the end of a line. This is why I have to a semicolon to the last line to get that omitted.

```
$a=1
($a++);(gc .\1.ps1)-replace'\d+$',$a|sc .\1.ps1;

```
> 0 votes

---
Tags: code-golf, source-layout, file-system, integer
---


title: HexaRegex: A Tribute to Martin Ender

text:
# Question
Title: HexaRegex: A Tribute to Martin Ender
Martin Ender recently hit 100K, and has come up with some pretty awesome languages. We're going to have a bit of fun with one of them, Hexagony (and a bit of regex for Retina)

As a brief overview, you need to write a program that **inputs a Hexagony grid and determines if there is a path on that grid that matches a string of text**

## Generating

Hexagony generates hexagons from a string of text using the following steps:

1. Calculate the minimum hexagon size (take the length of the string and round up to the nearest hex number)
2. Wrapping the text into a hexagon of the above size
3. Filling the remaining locations with `.`.

For example, the string of text `abcdefghijklm` requires a hexagon of side-length 3, and therefore becomes:

```
   a b c
  d e f g
 h i j k l
  m . . .
   . . .

```

Now, notice that there are 6 possible directions you can travel in a hexagon. For example, in the above hexagon, `e` is adjacent to `abfjid`.

## Wrapping

Furthermore, in Hexagony, hexagons wrap:

```
   . . . .          . a . .          . . f .          . a . .
  a b c d e        . . b . .        . . g . .        . b . . f
 . . . . . .      g . . c . .      . . h . . a      . c . . g .
. . . . . . .    . h . . d . .    . . u . . b .    . d . . h . .
 f g h i j k      . i . . e .      . j . . c .      e . . i . .
  . . . . .        . j . . f        k . . d .        . . j . .
   . . . .          . k . .          . . e .          . k . .

```

If you look at the 2nd and 4th example, notice how `a` and `k` are in the same spots, despite the fact that you are wrapping in different directions. **Due to this fact, these spots are only adjacent to 5 other locations**.

To make this clearer:

```
   a b c d
  e f g h i
 j k l m n o
p q r s t u v
 w x y z A B
  C D E F G
   H I J K

```
1. Edges wrap to their opposite neighbor (`b->I` and `G->j`).
2. Top/bottom corners wrap to the opposite *center* corner and up/down (`d->K,p` and `H->a,v`).
3. Center corners wrap to both the top and bottom corners (`v->a,H`)

## Paths

A *path* to be a sequence of adjacent locations without returning to the same location.

```
   a b c
  d e f g
 h i f k l
  m . . .
   . . .

```

In the above hexagon, `aefkgm` is a valid path. However, `abfd` is not a valid path (`f` and `d` aren't adjacent), and `abea` isn't valid (returns to the `a` location).

**We can use these paths to match text (like regex)**. An alpha-numeric character matches itself (and only itself), and a `.` matches any character. For example, the path `aej..lgm` would match `aej..lgm`, `aejAAlgm`, `aeja.lgm`, or `aej^%gm`.

# Input/Output

Your program should take two strings (in any order). The first string will be nonempty, and consist of only alphanumeric characters `[a-zA-Z0-9]`. This will represent the hexagon you are operating on. The second string will consist of printable characters.

**You need to return a truthy value iff there is a path in the hexagon that matches the string of text given, otherwise a falsy value.**

# Test cases

Truthy:

```
"a","a"
"ab","a"
"ab","b"
"ab","ba"
"ab","aba"
"ab","&"
"ab","#7.J!"
"ab","aaaaaa"
"ab","bgjneta"
"ab","cebtmaa"
"abcdefg","dfabcg"
"AbCDeFG","GCbAeFD"
"aaaabbb","aaababb"
"abcdefghijklmnopqrs","alq"
"abcdefghijklmnopqrs","aqnmiedh"
"abcdefghijklmnopqrs","adhcgkorbefjimnqlps"
"11122233344455","12341345123245"
"abcdefgh","h%a"
"abcdefghijklm","a)(@#.*b"
"abcdefghijklm","a)(@#.*i"
"abcdefghij","ja"
"abcdefghijklmno","kgfeia"
"abcdefghijklmno","mmmmmiea"
"abcdefghijklmno","mmmmmlae"
"abcdefghijklmno","ja"
"abcdefghijklmnopqrs","eijfbadhmnokgcsrql"

```

Falsy:

```
"a","b"
"a","%"
"a","."
"a","aa"
"a","a."
"ab","#7.J!*"
"ab","aaaaaaa"
"ab","aaaabaaa"
"ab","123456"
"abcdefg","bfgedac"
"abcdefg","gecafdb"
"abcdefg","GCbaeFD"
"aaaabbb","aaaaabb"
"abcdefghijklmnopqrs","aqrcgf"
"abcdefghijklmnopqrs","adhlcgknbeifjm"
"abcdefghijklmnopqrs","ja"
"abcdefghijklm","a)(@#.*&"
"abcdefghijklmno","a)(@bfeijk"
"abcdefghijklmno","kgfeic"
"abcdefghijklmno","mmmmmmiea"

```

This is a , so make your answers as short as possible in your favorite language.

# Answer
> 18 votes
# Retina, 744 bytes

Sorry folks, no Hexagony this time...

*Byte count assumes ISO 8859-1 encoding.*

```
.+¶
$.'$*_¶$&
^_¶
¶
((^_|\2_)*)_\1{5}_+
$2_
^_*
$.&$*×_$&$&$.&$*×
M!&m`(?<=(?=×*(_)+)\A.*)(?<-1>.)+(?(1)!)|^.*$
O$`(_)|.(?=.*$)
$1
G-2`
T`d`À-É
m`\A(\D*)(?(_)\D*¶.|(.)\D*¶\2)((.)(?<=(?<4>_)\D+)?((?<=(?<1>\1.)\4\D*)|(?<=(?<1>\D*)\4(?<=\1)\D*)|(?<=\1(.(.)*¶\D*))((?<=(?<1>\D*)\4(?>(?<-7>.)*)¶.*\6)|(?<=(?<1>\D*)(?=\4)(?>(?<-7>.)+)¶.*\6))|(?<=(×)*¶.*)((?<=(?<1>\1.(?>(?<-9>¶.*)*))^\4\D*)|(?<=(?<1>\D*)\4(?>(?<-9>¶.*)*)(?<=\1)^\D*)|(?<=(?<1>\1\b.*(?(9)!)(?<-9>¶.*)*)\4×*¶\D*)|(?<=(?<1>\D*\b)\4.*(?(9)!)(?<-9>¶.*)*(?<=\1.)\b\D*))|(?<=(?<1>\1.(?>(?<-11>.)*)¶.*)\4(.)*¶\D*)|(?<=(?<1>\1(?>(?<-12>.)*)¶.*)\4(.)*¶\D*)|(?<=(?<1>\1.(?>(?<-13>.)*¶\D*))\4(\w)*\W+.+)|(?<=(?<1>.*)\4(?>(?<-14>.)*¶\D*)(?<=\1.)(\w)*\W+.+))(?<=\1(\D*).+)(?<!\1\15.*(?<-1>.)+))*\Z

```

Expects the target string on the first line and the hexagon on the second line of the input. Prints `0` or `1` accordingly.

Try it online! (The first line enables a test suite, where each line is a test case, using `¦` for separation instead of a linefeed.)

The proper way to solve this challenge is with a regex of course. ;) And if it wasn't for the fact that this challenge also involves the unfolding procedure of the hexagon, this answer would actually consist of nothing but a single ~600-byte long regex.

This isn't quite optimally golfed yet, but I'm quite happy with the result (my first working version, after removing named groups and other stuff required for sanity, was around 1000 bytes). I think I could save about 10 bytes by swapping the order of the string and the hexagon but it would require a complete rewrite of the regex at the end, which I'm not feeling up to right now. There's also a 2-byte saving by omitting the `G` stage, but it slows down the solution considerably, so I'll wait with making that change until I'm sure I've golfed this as well as I can.

### Explanation

The main part of this solution makes extensive use of balancing groups, so I recommend reading up on them, if you want to understand how this works in detail (I won't blame you if you don't...).

The first part of the solution (i.e. everything except the last two lines) is a modified version of my answer to Unfolding the Hexagony source code. It constructs the hexagon, while leaving the target string untouched (and it actually constructs the hexagon before the target string). I've made some changes to the previous code to save bytes:

* The background character is `×` instead of a space so that it doesn't conflict with potential spaces in the input.
* The no-op/wildcard character is `_` instead `.`, so that grid cells can be reliably identified as word characters.
* I don't insert any spaces or indentation after the hexagon is first constructed. That gives me a slanted hexagon, but that is actually much more convenient to work with and the adjacency rules are fairly simple.

Here is an example. For the following test case:

```
ja
abcdefghij

```

We get:

```
××abc
×defg
hij__
____×
___××
ja

```

Compare this with the usual layout of the hexagon:

```
  a b c
 d e f g
h i j _ _
 _ _ _ _
  _ _ _

```

We can see that the neighbours are now all of the usual 8 Moore-neighbours, except the north-west and south-east neighbours. So we need to check horizontal, vertical and south-west/north-east adjacency (well and then there are the wrapping edges). Using this more compact layout also has the bonus that we'll be able to use those `××` at the end to determine the size of the hexagon on the fly when we need it.

After this form has been constructed, we make one more change to the entire string:

```
T`d`À-É

```

This replaces the digits with the extended ASCII letters

```
ÀÁÂÃÄÅÆÇÈÉ

```

Since they are replaced both in the hexagon and in the target string this won't affect whether the string is matched or not. Also, since they are letters `\w` and `\b` still identify them as hexagon cells. The benefit of doing this substitution is that we can now use `\D` in the upcoming regex to match *any* character (specifically, linefeeds as well as non-linefeed characters). We can't use the `s` option to accomplish that, because we'll need `.` to match non-linefeed characters in several places.

Now the last bit: determining whether any path matches our given string. This is done with a single monstrous regex. You might ask yourself **why?!?!** Well, this is fundamentally a backtracking problem: you start somewhere and attempt a path as long as it matches the string, and once it doesn't you backtrack and try a different neighbour from the last character that worked. The *one thing* that you get for free when working with regex is backtracking. That's literally the only thing the regex engine does. So if we just find a way to describe a valid path (which is tricky enough for this kind of problem, but definitely possible with balancing groups), then the regex engine will sort out finding that path among all possible ones for us. It would certainly be possible to implement the search manually with multiple stages (and I've done so in the past), but I doubt it would be shorter in this particular case.

One issue with implementing this with a regex is that we can't arbitrarily weave the regex engine's cursor back and forth through the string during backtracking (which we'd need since the path might go up or down). So instead, we keep track of our own "cursor" in a capturing group and update that at every step (we can move to the position of the cursor temporarily with a lookaround). This also enables us to store all past positions which we'll use to check that we haven't visited the current position before.

So let's get to it. Here is a slightly saner version of the regex, with named groups, indentation, less random order of neighbours and some comments:

```
\A
# Store initial cursor position in <pos>
(?<pos>\D*)
(?(_)
  # If we start on a wildcard, just skip to the first character of the target.
  \D*¶.
|
  # Otherwise, make sure that the target starts with this character.
  (?<first>.)\D*¶\k<first>
)
(?:
  # Match 0 or more subsequent characters by moving the cursor along the path.
  # First, we store the character to be matched in <next>.
  (?<next>.)
  # Now we optionally push an underscore on top (if one exists in the string).
  # Depending on whether this done or not (both of which are attempted by
  # the engine's backtracking), either the exact character, or an underscore
  # will respond to the match. So when we now use the backreference \k<next>
  # further down, it will automatically handle wildcards correctly.
  (?<=(?<next>_)\D+)?
  # This alternation now simply covers all 6 possible neighbours as well as
  # all 6 possible wrapped edges.
  # Each option needs to go into a separate lookbehind, because otherwise
  # the engine would not backtrack through all possible neighbours once it
  # has found a valid one (lookarounds are atomic).
  # In any case, if the new character is found in the given direction, <pos>
  # will have been updated with the new cursor position.
  (?:
    # Try moving east.
    (?<=(?<pos>\k<pos>.)\k<next>\D*)
  |
    # Try moving west.
    (?<=(?<pos>\D*)\k<next>(?<=\k<pos>)\D*)
  |
    # Store the horizontal position of the cursor in <x> and remember where
    # it is (because we'll need this for the next two options).
    (?<=\k<pos>(?<skip>.(?<x>.)*¶\D*))
    (?:
      # Try moving north.
      (?<=(?<pos>\D*)\k<next>(?>(?<-x>.)*)¶.*\k<skip>)
    |
      # Try moving north-east.
      (?<=(?<pos>\D*)(?=\k<next>)(?>(?<-x>.)+)¶.*\k<skip>)
    )
  |
    # Try moving south.
    (?<=(?<pos>\k<pos>.(?>(?<-x>.)*)¶.*)\k<next>(?<x>.)*¶\D*)
  |
    # Try moving south-east.
    (?<=(?<pos>\k<pos>(?>(?<-x>.)*)¶.*)\k<next>(?<x>.)*¶\D*)
  |
    # Store the number of '×' at the end in <w>, which is one less than the
    # the side-length of the hexagon. This happens to be the number of lines
    # we need to skip when wrapping around certain edges.
    (?<=(?<w>×)*¶.*)
    (?:
      # Try wrapping around the east edge.
      (?<=(?<pos>\k<pos>.(?>(?<-w>¶.*)*))^\k<next>\D*)
    |
      # Try wrapping around the west edge.
      (?<=(?<pos>\D*)\k<next>(?>(?<-w>¶.*)*)(?<=\k<pos>)^\D*)
    |
      # Try wrapping around the south-east edge.
      (?<=(?<pos>\k<pos>\b.*(?(w)!)(?<-w>¶.*)*)\k<next>×*¶\D*)
    |
      # Try wrapping around the north-west edge.
      (?<=(?<pos>\D*\b)\k<next>.*(?(w)!)(?<-w>¶.*)*(?<=\k<pos>.)\b\D*)
    )
  |
    # Try wrapping around the south edge.
    (?<=(?<pos>\k<pos>.(?>(?<-x>.)*¶\D*))\k<next>(?<x>\w)*\W+.+)
  |
    # Try wrapping around the north edge.
    (?<=(?<pos>.*)\k<next>(?>(?<-x>.)*¶\D*)(?<=\k<pos>.)(?<x>\w)*\W+.+)
  )
  # Copy the current cursor position into <current>.
  (?<=\k<pos>(?<current>\D*).+)
  # Make sure that no matter how many strings we pop from our stack of previous
  # cursor positions, none are equal to the current one (to ensure that we use
  # each cell at most once).
  (?<!\k<pos>\k<current>.*(?<-pos>.)+)
)*
# Finally make sure that we've reached the end of the string, so that we've
# successfully matched all characters in the target string.
\Z

```

I hope that the general idea is roughly clear from this. As an example for how one of those movements along the path works, let's look at the bit that moves the cursor south:

```
(?<=(?<pos>\k<pos>.(?>(?<-x>.)*)¶.*)\k<next>(?<x>.)*¶\D*)

```

Remember that lookbehinds should be read from right to left (or bottom to top), because that's the order they are executed in:

```
(?<=
  (?<pos>
    \k<pos>       # Check that this is the old cursor position.
    .             # Match the character directly on top of the new one.
    (?>(?<-x>.)*) # Match the same amount of characters as before.
    ¶.*           # Skip to the next line (the line, the old cursor is on).
  )               # We will store everything left of here as the new
                  # cursor position.
  \k<next>        # ...up to a match of our current target character.
  (?<x>.)*        # Count how many characters there are...
  ¶\D*            # Skip to the end of some line (this will be the line below
                  # the current cursor, which the regex engine's backtracking
                  # will determine for us).
)

```

Note that it's not necessary to put an anchor in front of the `\k<pos>` to ensure that this actually reaches the beginning of the string. `<pos>` always starts with an amount of `×` that can't be found anywhere else, so this acts as an implicit anchor already.

I don't want to bloat this post more than necessary, so I won't go into the other 11 cases in detail, but in principle they all work similarly. We check that `<next>` can be found in some specific (admissible) direction from the old cursor position with the help of balancing groups, and then we store the string up to that match as the new cursor position in `<pos>`.

# Answer
> 13 votes
# Python 3, ~~990~~ ~~943~~ ~~770~~ 709 bytes

First answer, yay!

EDIT: Golfed adjacency list making. I now use a slightly different formula

EDIT 2: Removed unnecessary fluff, golfed a lot more.

EDIT 3: Shortened the code for conversion from index in list to coordinates, golfed a few more things.

The majority of the bytes relates to making the adjacency list (it has the most potential to be golfed). From then, it's a simple matter of brute-forcing the solution (which I might be able to do in less bytes).

### Golfed:

```
from math import*
b=abs
c=max
e=range
f=len
A=input()
B=input()
C=ceil(sqrt((f(A)-.25)/3)+.5)
D=3*C*~-C+1
E=2*C-1
F=C-1
A+='.'*(D-f(A))
G=[set()for x in e(D)]
I=lambda H:sum(E+.5-b(t-F+.5)for t in e(int(H+F)))
for x in e(D):
 r=sum([[J-F]*(E-b(J-F))for J in e(E)],[])[x];q=x-I(r);s=-q-r;a=lambda q,r:G[x].add(int(q+I(r)));m=c(map(b,[q,r,s]))
 if m==F:
  if q in(m,-m):a(-q,-s)
  if r in(m,-m):a(-s,-r)
  if s in(m,-m):a(-r,-q)
 for K,L in zip([1,0,-1,-1,0,1],[0,1,1,0,-1,-1]):
  M,H=q+K,r+L
  if c(map(b,[M,H,-M-H]))<C:a(M,H)
def N(i,O,P):
 Q=O and O[0]==A[i]or'.'==A[i];R=0
 if(2>f(O))*Q:R=1
 elif Q:R=c([(x not in P)*N(x,O[1:],P+[i])for x in G[i]]+[0])
 return R
print(c([N(x,B,[])for x in e(D)])*(f(B)<=D))

```

### Ungolfed w/ explanation:

```
from math import*

#Rundown of the formula:
# * Get data about the size of the hexagon
# * Create lookup tables for index <-> coordinate conversion
#   * q=0, r=0 is the center of the hexagon
#   * I chose to measure in a mix of cubic and axial coordinates,
#     as that allows for easy oob checks and easy retrevial
# * Create the adjacency list using the lookup tables, while
#   checking for wrapping
# * Brute-force check if a path in the hexagon matches the
#   expression

# shorten functions used a lot
b=abs
c=max
e=range

# Get input

prog=input()
expr=input()

# sdln = Side length
# hxln = Closest hexagonal number
# nmrw = Number of rows in the hexagon
# usdl = one less than the side length. I use it a lot later

sdln=ceil(sqrt((len(prog)-.25)/3)+.5)
hxln=3*sdln*~-sdln+1
nmrw=2*sdln-1
usdl=sdln-1

# Pad prog with dots

prog+='.'*(hxln-len(prog))

# nmbf = Number of elements before in each row
# in2q = index to collum
# in2r = index to row

nmbf=[0]*nmrw
in2q=[0]*hxln
in2r=[0]*hxln

#  4    5
#   \  /
# 3 -- -- 0
#   /  \
#  2    1

# dirs contains the q,r and s values needed to move a point
# in the direction refrenced by the index

qdir=[1,0,-1,-1,0,1]
rdir=[0,1,1,0,-1,-1]

# generate nmbf using a summation formula I made

for r in e(nmrw-1):
    nmbf[r+1]=int(nmbf[r]+nmrw+.5-b(r-sdln+1.5))

# generate in2q and in2r using more formulas
# cntr = running counter

cntr=0
for r in e(nmrw):
    bgnq=c(-r,1-sdln)
    for q in e(nmrw-b(r-sdln+1)):
        in2q[cntr]=bgnq+q
        in2r[cntr]=r-usdl
        cntr+=1

# adjn = Adjacency sets

adjn=[set()for x in e(hxln)]

# Generate adjacency sets

for x in e(hxln):
    #Get the q,r,s coords
    q,r=in2q[x],in2r[x]
    s=-q-r
    # a = function to add q,r to the adjacency list
    a=lambda q,r:adjn[x].add(q+nmbf[r+usdl])
    # m = absolute value distance away from the center
    m=c(map(b,[q,r,s]))
    # if we are on the edge (includes corners)...
    if m==usdl:
        # add the only other point it wraps to
        if q in(m,-m):
            a(-q,-s)
        if r in(m,-m):
            a(-s,-r)
        if s in(m,-m):
            a(-r,-q)
    # for all the directions...
    for d in e(6):
        # tmp{q,r,s} = moving in direction d from q,r,s
        tmpq,tmpr=q+qdir[d],r+rdir[d]
        # if the point we moved to is in bounds...
        if c(map(b,[tmpq,tmpr,-tmpq-tmpr]))<sdln:
            # add it
            a(tmpq,tmpr)

# Recursive path checking function
def mtch(i,mtst,past):
    # dmch = Does the place we are on in the hexagon match
    #        the place we are in the expression?
    # out = the value to return
    dmch=mtst and mtst[0]==prog[i]or'.'==prog[i]
    out=0
    # if we are at the end, and it matches...
    if(2>len(mtst))*dmch:
        out=1
    # otherwise...
    elif dmch:
        # Recur in all directions that we haven't visited yet
        # replace '*' with 'and' to speed up the recursion
        out=c([(x not in past)*mtch(x,mtst[1:],past+[i])for x in adjn[i]]+[0])
    return out

# Start function at all the locations in the hexagon
# Automatically return false if the expression is longer
# than the entire hexagon
print(c([mtch(x,expr,[])for x in e(hxln)])*(len(expr)<=hxln))

```

~~So close to Retina! :(~~ Yay, beat Retina!

# Answer
> 5 votes
## Javascript (ES6), ~~511~~ ~~500~~ 496 bytes

```
(H,N)=>{C=(x,y)=>(c[x]=c[x]||[])[y]=y;S=d=>(C(x,y=x+d),C(y,x),C(s-x,s-y),C(s-y,s-x));r=(x,p,v)=>{p<N.length?(v[x]=1,c[x].map(n=>!v[n]&&(H[n]==N[p]||H[n]=='.')&&r(n,p+1,v.slice()))):K=1};for(e=x=K=0;(s=3*e*++e)<(l=H.length)-1;);H+='.'.repeat(s+1-l);for(a=[],b=[],c=[[]],w=e;w<e*2;){a[w-e]=x;b[e*2-w-1]=s-x;for(p=w;p--;x++){w-e||S(s-e+1);w<e*2-1&&(S(w),S(w+1));p&&S(1)}a[w]=x-1;b[e*3-++w]=s-x+1}a.map((v,i)=>S(b[i]-(x=v)));[N[0],'.'].map(y=>{for(x=-1;(x=H.indexOf(y,x+1))>-1;r(x,1,[]));});return K}

```

### Ungolfed and commented

```
// Entry point
//   H = haystack (the string the hexagon is filled with)
//   N = needle (the substring we're looking for)
(H, N) => {
  // C(x, y) - Helper function to save a connection between two locations.
  //   x = source location
  //   y = target location
  C = (x, y) => (c[x] = c[x] || [])[y] = y;

  // S(d) - Helper function to save reciprocal connections between two locations
  //        and their symmetric counterparts.
  //   d = distance between source location (x) and target location
  S = d => (C(x, y = x + d), C(y, x), C(s - x, s - y), C(s - y, s - x));

  // r(x, p, v) - Recursive path search.
  //   x = current location in hexagon
  //   p = current position in needle
  //   v = array of visited locations
  r = (x, p, v) => {
    p < N.length ?
      (v[x] = 1, c[x].map(n => !v[n] && (H[n] == N[p] || H[n] == '.') &&
      r(n, p + 1, v.slice())))
    :
      K = 1
  };

  // Compute e = the minimum required edge width of the hexagon to store the haystack.
  // Also initialize:
  //   x = current location in hexagon
  //   l = length of haystack
  //   s = size of hexagon (number of locations - 1)
  //   K = fail/success flag
  for(e = x = K = 0; (s = 3 * e * ++e) < (l = H.length) - 1;);

  // Pad haystack with '.'
  H += '.'.repeat(s + 1 - l);

  // Build connections c[] between locations, using:
  //   x = current location
  //   w = width of current row
  //   p = position in current row
  // Also initialize:
  //   a[] = list of locations on top left and top right edges
  //   b[] = list of locations on bottom left and bottom right edges
  for(a = [], b = [], c = [[]], w = e; w < e * 2;) {
    a[w - e] = x;
    b[e * 2 - w - 1] = s - x;

    for(p = w; p--; x++) {
      // connection between top and bottom edges
      w - e || S(s - e + 1);
      // connections between current location and locations below it
      w < e * 2 - 1 && (S(w), S(w + 1));
      // connection between current location and next location
      p && S(1)
    }
    a[w] = x - 1;
    b[e * 3 - ++w] = s - x + 1
  }

  // Save connections between top left/right edges and bottom left/right edges.
  a.map((v, i) => S(b[i] - (x = v)));

  // Look for either the first character of the needle or a '.' in the haystack,
  // and use it as the starting point for the recursive search. All candidate
  // locations are tried out.
  [N[0], '.'].map(y => {
    for(x = -1; (x = H.indexOf(y, x + 1)) > -1; r(x, 1, []));
  });

  // Return fail/success flag.
  return K
}

```

### Test cases

The snippet below will walk through all truthy and falsy test cases.

```
let f =
(H,N)=>{C=(x,y)=>(c[x]=c[x]||[])[y]=y;S=d=>(C(x,y=x+d),C(y,x),C(s-x,s-y),C(s-y,s-x));r=(x,p,v)=>{p<N.length?(v[x]=1,c[x].map(n=>!v[n]&&(H[n]==N[p]||H[n]=='.')&&r(n,p+1,v.slice()))):K=1};for(e=x=K=0;(s=3*e*++e)<(l=H.length)-1;);H+='.'.repeat(s+1-l);for(a=[],b=[],c=[[]],w=e;w<e*2;){a[w-e]=x;b[e*2-w-1]=s-x;for(p=w;p--;x++){w-e||S(s-e+1);w<e*2-1&&(S(w),S(w+1));p&&S(1)}a[w]=x-1;b[e*3-++w]=s-x+1}a.map((v,i)=>S(b[i]-(x=v)));[N[0],'.'].map(y=>{for(x=-1;(x=H.indexOf(y,x+1))>-1;r(x,1,[]));});return K}

let truthy = [
  ["a","a"],
  ["ab","a"],
  ["ab","b"],
  ["ab","ba"],
  ["ab","aba"],
  ["ab","&"],
  ["ab","#7.J!"],
  ["ab","aaaaaa"],
  ["ab","bgjneta"],
  ["ab","cebtmaa"],
  ["abcdefg","dfabcg"],
  ["AbCDeFG","GCbAeFD"],
  ["aaaabbb","aaababb"],
  ["abcdefghijklmnopqrs","alq"],
  ["abcdefghijklmnopqrs","aqnmiedh"],
  ["abcdefghijklmnopqrs","adhcgkorbefjimnqlps"],
  ["11122233344455","12341345123245"],
  ["abcdefgh","h%a"],
  ["abcdefghijklm","a)(@#.*b"],
  ["abcdefghijklm","a)(@#.*i"],
  ["abcdefghij","ja"],
  ["abcdefghijklmno","kgfeia"],
  ["abcdefghijklmno","mmmmmiea"],
  ["abcdefghijklmno","mmmmmlae"],
  ["abcdefghijklmno","ja"],
  ["abcdefghijklmnopqrs","eijfbadhmnokgcsrql"]
];

let falsy = [
  ["a","b"],
  ["a","%"],
  ["a","."],
  ["a","aa"],
  ["a","a."],
  ["ab","#7.J!*"],
  ["ab","aaaaaaa"],
  ["ab","aaaabaaa"],
  ["ab","123456"],
  ["abcdefg","bfgedac"],
  ["abcdefg","gecafdb"],
  ["abcdefg","GCbaeFD"],
  ["aaaabbb","aaaaabb"],
  ["abcdefghijklmnopqrs","aqrcgf"],
  ["abcdefghijklmnopqrs","adhlcgknbeifjm"],
  ["abcdefghijklmnopqrs","ja"],
  ["abcdefghijklm","a)(@#.*&"],
  ["abcdefghijklmno","a)(@bfeijk"],
  ["abcdefghijklmno","kgfeic"],
  ["abcdefghijklmno","mmmmmmiea"]
];

console.log(
  'Testing truthy test cases:',
  truthy.every(v => f(v[0], v[1])) ? 'passed' : 'failed'
);
console.log(
  'Testing falsy test cases:',
  falsy.every(v => !f(v[0], v[1])) ? 'passed' : 'failed'
);
```

---
Tags: code-golf, regular-expression, hexagonal-grid
---


# Question
Title: Climbing binomial tree to find the option value
# Background:

In finance, the binomial options pricing model (BOPM) is the simplest technique used for option pricing. The mathematics behind the model is relatively easy to understand and (at least in their basic form) it is not difficult to implement. This model was first proposed by Cox, Ross, and Rubinstein in 1979. Quoting Wikipedia:

> The binomial pricing model traces the evolution of the option's key underlying variables in discrete-time. This is done by means of a binomial lattice (tree), for a number of time steps between the valuation and expiration dates. Each node in the lattice represents a possible price of the underlying at a given point in time.
>
> Valuation is performed iteratively, starting at each of the final nodes (those that may be reached at the time of expiration), and then working backwards through the tree towards the first node (valuation date). The value computed at each stage is the value of the option at that point in time.

For this challenge's sake, we will create a simple model to predict potential future prices of the option(s) by creating a lattice or a tree as shown below (a picture is worth a thousand words):

where ***S*** is the option price today, ***p*** is the probability of a price rise, and ***t*** is the period of time or number of steps.

# Challenge:

The challenge is to write either a program or a function which take ***S***, ***p*** (in percent), and ***t*** as the inputs and give the binomial tree as the output. The output of the program or the function **must** follow the format above, but the boxes and the arrow lines are optional. For example, if the program take inputs `S = 100`, `p = 10%`, and `t = 3`, then its output may be in the following simple form:

```
                        133.1
                121
        110             108.9
100              99
         90              89.1
                 81
                         72.9

```

# General rules:

* This is , so the shortest answer in bytes wins the challenge.
Don't let esolangs discourage you from posting an answer with regular languages. Enjoy this challenge by providing an answer as short as possible with your programming language. If you post a clever answer and a clear explanation, your answer will be appreciated (hence the upvotes) regardless of the programming language you use.
* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/ method with the proper parameters, full programs, etc. The choice is yours.
* Using a binomial tree built-in is forbidden.
* If possible, your program can properly handle a large number of steps. If not, that will just be fine.

# References:

1. Binomial options pricing model
2. Binomial tree option calculator

# Answer
# Python, ~~168~~ 167 bytes

```
q=lambda s,p,t:'\n'.join(''.join('%e'%(s*(1+p)**(c-(r+c-t)//2)*(1-p)**((r+c-t)//2))if(t-c<=r<=t+c)&(r%2^(c+~t%2)%2)else' '*12for c in range(t+1))for r in range(2*t+1))

```

Test case with anonymous function above assigned to `f` would be `print(f(100,0.1,3))`, yielding:

```
                                    1.331000e+02
                        1.210000e+02
            1.100000e+02            1.089000e+02
1.000000e+02            9.900000e+01
            9.000000e+01            8.910000e+01
                        8.100000e+01
                                    7.290000e+01

```

Extending the same to t=4 would be `print(f(100,0.1,3))`, yielding:

```
                                                1.464100e+02
                                    1.331000e+02
                        1.210000e+02            1.197900e+02
            1.100000e+02            1.089000e+02
1.000000e+02            9.900000e+01            9.801000e+01
            9.000000e+01            8.910000e+01
                        8.100000e+01            8.019000e+01
                                    7.290000e+01
                                                6.561000e+01

```

---

For the avoidance of scientific notation while keeping at least 3 significant figures we can use the following **211 byte** code instead:

```
lambda s,p,t:'\n'.join(''.join('%12s'%(v and(10**5>v>.0001and'%f'%v or'%e'%v)or'')for v in[(t-c<=r<=t+c)&(r%2^(c+~t%2)%2)and s*(1+p)**(c-(r+c-t)//2)*(1-p)**((r+c-t)//2)for c in range(t+1)])for r in range(2*t+1))

```

Test case, `print(f(100,0.1,3))` yields:

```
                                      133.100000
                          121.000000
              110.000000              108.900000
  100.000000               99.000000
               90.000000               89.100000
                           81.000000
                                       72.900000

```

then when numbers get too big or small, for example `print(f(9876.000123,0.99,6))`:

```
                                                                        6.133375e+05
                                                            3.082098e+05
                                                1.548793e+05             3082.098178
                                    77828.796693             1548.793054
                        39109.948087              778.287967               15.487931
            19653.240245              391.099481                7.782880
 9876.000123              196.532402                3.910995                0.077829
               98.760001                1.965324                0.039110
                            0.987600                0.019653                0.000391
                                        0.009876                0.000197
                                                9.876000e-05            1.965324e-06
                                                            9.876000e-07
                                                                        9.876000e-09

```
> 2 votes

# Answer
# Dyalog APL, ~~60~~ 56 bytes

Needs `⎕IO←0` which is default on many systems. Prompts for ***S*** then ***t*** then ***p***.

```
⍉{⍵⌽⍨-⌽⍳≢⍵}↑{⍵\⍨0 1⍴⍨2×≢⍵}¨⍕¨¨⎕{⍵,⊂∪∊(⊃⌽⍵)∘.×1+⍺,-⍺}⍣⎕⊢⎕

```

Over 50% of the code is to get the right display form.

TryAPL online! (`]Box off` for proper display – the default on installed systems – emulated here using .)

Example run:

```
                133.1
           121
      110       108.9
 100       99
      90        89.1
           81
                72.9

```
> 2 votes

# Answer
# R, 288 bytes

```
x=scan()
M=Map
U=rbind
noquote(t(do.call(U,M(function(x,y){r=rep;c(r(" ",x),rev(as.vector(U(y,r(" ",length(y))))),r(" ",x))},as.list(x[3]:0),M(function(x,y){sapply(y,function(y)(1-x[2])^y[1]*(1+x[2])^y[2]*x[1])},list(x),lapply(0:x[3],function(y)data.frame(do.call(U,list(y:0, 0:y)))))))))

```

Sometimes I feel like I'm not even golfing. The maximum t is limited by the amount of system memory. The readability of output is determined by the resolution of your screen/console size. If we write to file instead, the readability limitations can be bypassed. I was able to run t = 5000, 100, 0.1 on my 16GB ram system; the output is 400+ mb plain text file.

```
      [,1] [,2] [,3] [,4]  [,5]   [,6]    [,7]     [,8]      [,9]       [,10]            [,11]            [,12]
 [1,]
 [2,]                                                                                285.311670611
 [3,]                                                                                259.37424601
 [4,]                                                                   235.7947691                       233.436821409
 [5,]                                                        214.358881                  212.21529219
 [6,]                                              194.87171            192.9229929                       190.993762971
 [7,]                                     177.1561           175.384539                  173.63069361
 [8,]                             161.051          159.44049            157.8460851                       156.267624249
 [9,]                      146.41         144.9459           143.496441                  142.06147659
[10,]                133.1        131.769          130.45131            129.1467969                       127.855328931
[11,]           121        119.79         118.5921           117.406179                  116.23211721
[12,]      110       108.9        107.811          106.73289            105.6655611                       104.608905489
[13,] 100       99         98.01          97.0299            96.059601                   95.0990049900001
[14,]      90        89.1         88.209           87.32691             86.4536409000001                  85.5891044910001
[15,]           81         80.19          79.3881            78.594219                   77.80827681
[16,]                72.9         72.171           71.44929             70.7347971000001                  70.027449129
[17,]                      65.61          64.9539            64.304361                   63.66131739
[18,]                             59.049           58.45851             57.8739249                        57.295185651
[19,]                                     53.1441            52.612659                   52.08653241
[20,]                                              47.82969             47.3513931                        46.877879169
[21,]                                                        43.046721                   42.61625379
[22,]                                                                   38.7420489                        38.354628411
[23,]                                                                                34.86784401
[24,]                                                                                31.381059609

```

t = 5000;
> 2 votes

---
Tags: code-golf
---


title: Quixels - Quantum Pixels

text:
# Question
Title: Quixels - Quantum Pixels
## Introduction

A quixel is a quantum pixel. Similar to a classical pixel, it is represented with 3 integer values (Red, Green, Blue). However, quixels are in a super position of these 3 states instead of a combination. This super position only lasts until the quixel is observed at which point it collapses to one of three classical pixels; `RGB(255,0,0)`, `RGB(0,255,0)` and `RGB(0,0,255)`.

## Specification

* **Representation**
    + Each quixel is represented as an array of 3 integers between 0 and 255, `r`, `g` and `b` respectively.
* **Super Positions**
    + Each quixel is in a super position between the Red, Blue and Green states represented by `R`, `G` and `B` respectively.
* **Observation**
    + When each quixel is observed it collapses into one of the three states. The probability of each classical state is `R = (r + 1) / (r + g + b +3)`**,** `G = (g + 1) / (r + g + b + 3)` and `B = (b + 1) / (r + g + b + 3)`. This way each classical state always as a non-zero probability of showing up.
* **Input**
    + The function or program should take a image of quixels. How it does this is flexible. A filename, using a multi-dimensional array, etc are all acceptable.
* **Output**
    + The function or program should produce an image of classical pixels. The data structure for this produced image is also flexible. Note that all of the pixels should be one of these three: `RGB(255,0,0)`, `RGB(0,255,0)` and `RGB(0,0,255)`
    + The output should not be deterministic; these are *quantum* pixels! The same input should result in different outputs.
    + If your language has no way of generating a random number, you can take random bytes as input
* **Scoring**

---

## Images

**Mona Lisa** by **Leonardo da Vinci**

**Starry Night** by **Vincent van Gogh**

**Persistence of Memory** by **Salvador Dali**

**Teddy Roosevelt VS. Bigfoot** by **SharpWriter**

# Answer
# Dyalog APL, ~~23~~ ~~21~~ 19 bytes

Takes table of (R, G, B) triplets.

### Inspired by miles' algorithm

Returns table of indices into {(255, 0, 0), (0, 255, 0), (0, 0, 255)}. Horribly wasteful.

```
(?∘≢⊃⊢)¨(⊂⍳3)/¨⍨1+⊢

```

`(`
`?∘≢` random index
selects
from
each of

`(`
the entire
`⍳3` first three indices
`)/¨⍨` replicated by each of

`1+⊢` the incremented triplets

TryAPL!

---

### Old version

Returns table of 0-based indices into {(255, 0, 0), (0, 255, 0), (0, 0, 255)}

```
{+/(?0)≥+\(1+⍵)÷3++/⍵}¨

```

`{`...`}`¨ for each quixel in the table, find the:

`+/` the sum of (i.e. count of truths of)

`(?0)≥` a random 0 \< number \< 1 being greater than or equal to

`+\` the cumulative sum of

`(1+⍵)÷` the incremented RGB values divided by

`3+` three plus

`+/⍵` the sum of the quixel

Note: Dyalog APL lets you chose between the Lehmer linear congruential generator, the Mersenne Twister, and the Operating System's RNG .

For example, the image:

```
┌──────────┬──────────┬───────────┬───────────┬─────────┐
│52 241 198│148 111 45│197 165 180│9 137 120  │46 62 75 │
├──────────┼──────────┼───────────┼───────────┼─────────┤
│81 218 104│0 0 255   │0 255 0    │181 202 116│122 89 76│
├──────────┼──────────┼───────────┼───────────┼─────────┤
│181 61 34 │84 7 27   │233 220 249│39 184 160 │255 0 0  │
└──────────┴──────────┴───────────┴───────────┴─────────┘

```

can give

```
┌─┬─┬─┬─┬─┐
│1│0│2│2│1│
├─┼─┼─┼─┼─┤
│2│2│1│1│2│
├─┼─┼─┼─┼─┤
│0│2│1│2│0│
└─┴─┴─┴─┴─┘

```

Notice how the three "pure" quixels collapsed to their respective colors.

TryAPL online!
> 13 votes

# Answer
# Mathematica, 53 bytes

```
RandomChoice[255#+1->IdentityMatrix@3]&~ImageApply~#&

```

Anonymous function. Takes a Mathematica `Image` as input and returns an `Image` as output. Note that the input image must have an RGB color space.
> 8 votes

# Answer
## C#, ~~366~~ 243 bytes

Huge thanks to @TheLethalCoder for golfing this!

```
var r=new Random();c=>{double t=c.R+c.G+c.B+3,x=(c.R+1)/t,d=r.NextDouble();return d<=x?Color.Red:d<=x+(c.G+1)/t?Color.Lime:Color.Blue;};b=>{for(int x=0,y;x<b.Width;x++)for(y=0;y<b.Height;y++)b.SetPixel(x,y,g(b.GetPixel(x,y)));return b;};

```

Basic idea:

```
using System;
using System.Drawing;
static Random r = new Random();

static Image f(Bitmap a) {
    for (int x = 0; x < a.Width; x++) {
        for (int y = 0; y < a.Height; y++) {
            a.SetPixel(x, y, g(a.GetPixel(x, y)));
        }
    }
    return a;
}

static Color g(Color c) {
    int a = c.R;
    int g = c.G;
    double t = a + g + c.B + 3;
    var x = (a + 1) / t;
    var y = x + (g + 1) / t;
    var d = r.NextDouble();
    return d <= x ? Color.Red : d <= y ? Color.Lime : Color.Blue;
}

```

---

Examples:

Mona Lisa

Starry Night

Persistence of Memory

Teddy Roosevelt VS. Bigfoot

Here's an updated imgur album with a few more examples, to show that this is nondeterministic.
> 5 votes

# Answer
# Python 2, ~~172~~ ~~166~~ 162 bytes

The second and third indent levels are a raw tab and a raw tab plus a space, respectively; this plays *really* badly with Markdown, so the tabs have been replaced by two spaces.

```
from random import*
i=input()
E=enumerate
for a,y in E(i):
 for b,x in E(y):
  t=sum(x)+3.;n=random()
  for j,u in E(x):
   n-=-~u/t
   if n<0:i[a][b]=j;break
print i

```

Uses a similar input/output format to Adám's APL answer. Input is a 2D array of RGB tuples; output is a 2D array of `0`, `1`, or `2`, representing red, green, and blue respectively. For example:

```
$ echo "[[(181,61,34),(39,184,160),(255,0,0)],[(84,7,27),(123,97,5),(12,24,88)]]" | python quixel.py
[[2, 2, 0], [0, 0, 0]]

```

Below is my older Python 3 answer using PIL.

## Python 3 + PIL, ~~271~~ ~~250~~ ~~245~~ 243 bytes

```
import random as a,PIL.Image as q
i=q.open(input())
w,h=i.size
for k in range(w*h):
 m=k//h,k%h;c=i.getpixel(m);t=sum(c)+3;n=a.random()
 for j,u in enumerate(c):
  n-=-~u/t
  if n<0:z=[0]*3;z[j]=255;i.putpixel(m,tuple(z));break
i.save('o.png')

```

Iterates over every pixel and applies the quixel function to it. Takes the filename as input and saves its output in `o.png`.

Here are some results:

```
$ echo mona-lisa.jpg | python quixel.py

```

```
$ echo starry-night.jpg | python quixel.py

```

```
$ echo persistence-of-memory.jpg | python quixel.py

```

```
$ echo roosevelt-vs-bigfoot.jpg | python quixel.py

```
> 4 votes

# Answer
# J, ~~20~~ ~~18~~ 17 bytes

```
(>:({~?@#)@##\)"1

```

The image is input as an array with dimensions *h* x *w* x 3 representing the RGB values as integers in the range 0 - 255. The output is a table with dimensions *h* x *w* where 1 is an rgb value of (255, 0, 0), 2 is (0, 255, 0), and 3 is (0, 0, 255).

## Explanation

The `()"1` represents that this verb is to be applied to each array of rank 1 in the input, meaning that it will apply to each *pixel*.

```
>:({~?@#)@##\  Input: array [R G B]
>:             Increment each, gets [R+1, G+1, B+1]
           #\  Gets the length of each prefix of [R G B], forms [1 2 3]
          #    Make a new array with R+1 copies of 1, G+1 copies of 2,
               and B+1 copies of 3
  (     )@     Operate on that array
       #         Get the length of the array of copies, will be R+G+B+3
     ?@          Generate a random integer in the range [0, R+G+B+3)
   {~            Select the value at that index from the array of copies and return

```
> 4 votes

# Answer
# R, 58 bytes

```
mapply(function(r,g,b)rmultinom(1,1,c(r+1,g+1,b+1)),r,g,b)

```

Input consists of three numeric vectors held in `r`, `g` and `b` respectively.

We don't need to normalise the probabilities to sum to one, that happens automatically in `rmultinom`.

Output is of the form

```
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]    0    0    0    0    0    0    0    0    0     0
[2,]    0    0    0    1    0    0    1    1    1     0
[3,]    1    1    1    0    1    1    0    0    0     1

```

Where there is a single `1` in each column. The `1` is in the first row for "R" pixels, the second row for "G" and the third row for "B".
> 4 votes

# Answer
# Jelly, ~~8~~ 7 bytes

```
Jx‘Xµ€€

```

The input is a 3d list with dimensions *h* x *w* x 3. The output is a 2d list with dimensions *h* x *w* where 1 represents the rgb value (255, 0, 0), 2 is (0, 255, 0), and 3 is (0, 0, 255).

The sample input below is the top-left 4 x 4 region of the Mona Lisa image.

Try it online!

## Explanation

```
Jx‘Xµ€€  Input: The 3d list of rgb pixels
    µ    Begin a monadic chain (Will operate on each pixel, input: [R, G, B])
J          Enumerate indices to get [1, 2, 3]
  ‘        Increment each to get [R+1, G+1, B+1]
 x         Make R+1 copies of 1, G+1 copies of 2, B+1 copies of 3
   X       Select a random value from that list of copies and return
     €€  Apply that monadic chain for each list inside each list

```
> 4 votes

# Answer
# Pyth - ~~11~~ 10 bytes

Takes RGB 2d bitmap and outputs bitmap with indexed 3-bit color.

```
mLOs.emkbk

```

That level of nesting is hurting my head.

Try it online here.
> 4 votes

# Answer
# Python 3, 119 bytes

Where `m` is the input taken as a 2-d array of pixels where each pixel is a list of the form `[r,g,b]`. At each pixel's position, returns `0,1,2` to represent `(250,0,0), (0,250,0), and (0,0,250)` respectively.

```
import random
lambda m:[map(lambda x:x.index(sum((((i+1)*[i])for i in x),[])[random.randint(0,sum(x)+2)]),i)for i in m]

```
> 3 votes

---
Tags: code-golf, graphical-output, random, image-processing
---


title: Write an xkcd feed bot

text:
# Question
Title: Write an xkcd feed bot
The new xkcd feed bot room gave me an idea for a simple challenge.

Your code will have to monitor the xkcd website and output all the new comics to the user.

# Specs

* When first run it should just sit around waiting.
* Then, when randall posts a new comic, within a minute, it should display the new comic in any of our usual standards for images (display, save, etc.)
* If the comic is interactive and not a simple image, then print out the string `"interactive comic"`.
* This does not include the comics which are an image inside a link, those still have to be displayed normally.
* After displaying the image, it should go back to waiting around for the next update.
* Your program cannot access any sites except http://xkcd.com

This is , so shortest code in **bytes** wins!

# Answer
> 4 votes
## PowerShell v2+ & Default Browser, ~~215~~ 217 bytes

```
$l=date;for(){if(($x=([xml](iwr xkcd.com/rss.xml)).rss.channel.item[0]).pubdate-ge$l){if(($y=$x.description)-match'img src'){saps ($y-replace'<img src="'-replace'" .*')}else{echo "interactive comic"}}$l=date}

```

***WARNING:*** *Running this as-is will likely make Randall very mad at you, due to the high frequency of calls to the RSS feed ... **so, y'know, don't do that.** (See below for an alternate version that can be used in a one-off manner)*

Sets the `$l`ast time we displayed a comic to the result of `Get-Date`. Then, enter an infinite `for` loop.

Each iteration, we `iwr` (alias for `Invoke-WebRequest`) the RSS feed for the site. That's parsed as `[xml]` (yes, PowerShell can cast as XML), and the `.rss.channel.item[0]` thereof (i.e., the newest) is stored in `$x`. If the `.pubDate` is `-ge$l` (i.e., newer than the last comic we showed), we have a new comic to display.

So, we first check the `.description` field (saved in `$y`), to see if it matches `img src`. If so, we parse out the img from `$y`, and feed that to `saps` (alias for `Start-Process`). Since it's a URI, this relies on Windows' default behavior for "executing" a URI, that is, it opens the default browser to that location. (*If this is too cheaty, let me know and we can `iwr` down the actual image and save it.*)

Otherwise, we `echo` out that we've got an `interactive comic`.

In either case, we update our `$l` date to "now" since we just displayed a comic.

*Saved 7 bytes thanks to Matt for reminding me that `http://` can be implied*

---

### "Safe" version that executes just once and displays the latest comic

```
$l=(date).AddDays(-3);if(($x=([xml](iwr http://xkcd.com/rss.xml)).rss.channel.item[0]).pubdate-ge$l){if(($y=$x.description)-match'img src'){saps ($y-replace'<img src="'-replace'" .*')}else{echo "interactive comic"}}

```

You can run this one safely to see how the logic works. It'll only execute once and only display the latest comic.

---
Tags: code-golf, graphical-output, internet
---