title: Print ASCII Voxels

text:
# Question
Title: Print ASCII Voxels
Write a program that reads a \\$n\times n \times n\\$ array of binary values which represent an \\$n\times n \times n\\$ cube, that consists of \\$n^3\\$ smaller cubes. Each value says whether there is a voxel (small cube) present in the given position or not. The program must output the given array as an ASCII graphic (that means output through console or writing to a file).

### Examples

Let us consider the following \\$2\times 2\times 2\\$ arrays:

```
[
 [[0,0],
  [1,0]]
 [[1,1],
  [1,0]],
]

[
 [[0,0],
  [0,0]]
 [[1,1],
  [1,1]],
]

```

In this case the output should look like this (it does not look as good here as it does in code editors/consoles with less vertical space):

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

    +----+----+
   /         /|
  +         + |
 /         /  +
+----+----+  /
|         | +
|         |/
+----+----+

```

An example for a \\$12\times 12\times 12\\$ input string can be found here (pastebin). A new example for a \\$7\times 7\times 7\\$ input string can be found here.

### Specifications of the ASCII

Each corner of a voxel is represented by a `+` as long as there is any edge leading to it. The `+` are also drawn when there is a straight edge that is more than one unit long. There are three types of edges: The horizontal left to right `----`, the horizontal back to front `/` and the vertical

```
|
|

```

Each of those has to end in a `+` (as long visible). The edges will not be drawn when they subdivide one planar plane into two or more pieces (unlike the `+` in relation to the edges as stated above). Structures that are hidden behind others must not be drawn.

The 'drawing' is basically a parallel projection so only top, right and front sides are visible - always from the same angle.

### Details

The code must be working for inputs of size \\$n=1,2,\ldots,12\\$. Trailing spaces and unnecessary newlines before/after are allowed (so you *could* write a code that always basically outputs the \\$12\times 12\times 12\\$ grid even when the actual size of the drawing is only \\$3\times 3\times 3\\$ or so).

Input formatting and method is up to you, you can use csv, JSON or any other stuff, but it has to consist of \\$1\\$ and \\$0\\$ for the state of each voxel. The order must be as in the examples:

* 1st dimension: layer by layer from the uppermost to the lowermost
* 2nd dimension: row by row back (furthest away) to front (nearest)
* 3rd dimension: voxels in each row left to right

Whether you use console or reading files as input and output is up to you. **Please** tell us about your code / how you approached it.

### Judging

This is codegolf so the fewest number of bytes wins. This includes ONLY the part that actually does the work - when counting bytes you can consider the input already as parsed and saved in a variable and you have to have the output string saved to a variable, ready to be printed. The parsing and the output itself does not count.

(And I will upvote submissions with creative examples=)

This was inspired by Rob's Puzzle page.

# Answer
# Python ( 444 361 354 bytes)

*Edit:* I found another bug that would omit a corner cross in very special cases. A straight forward fix added 50 bytes to the code so I tried to golf it down a bit further. Now the bug is fixed and it's even 83 bytes shorter. It's becoming very hacky. I also wanted to get rid of the fivefold for loop but could not yet find a solution. Any ideas?

*Edit 2:* With a very long import I can save another 7 characters.

Neither very short nor very elegant, but then again it is a complex problem:

```
#input:
u=[[[1,1,1],[1,0,1],[1,1,1]],
   [[1,0,1],[0,0,0],[1,0,1]],
   [[1,1,1],[1,0,1],[1,1,1]]]

#actual code that counts:
r=range
n=len(u)
g=r(n)
a=([' ']*9*n+['\n'])*6*n
t='/|-+\n '
d=dict(zip(t+'%!=*',2*t))
for y,z,x,i,j in __import__('itertools').product(g,g,g[::-1],r(6),r(8)):
 if abs(i+j-6)<5*u[x][y][z]:a[(9*n+1)*(i+3*x+2*y)+j+5*z-2*y+2*n]+='./    %|+====* ||    ! *|    !/.*----+'[8*i+j-8]
o=''.join((d[x[-1]],' ')[x[-2:]in('%/','!|','=-')or x[-4:]=='*++*']for x in a)

#output:
print o

```

It first draws all the individual voxels with all lines on top of each other. Then it outputs only the topmost characters and gets rid of those lines and crosses on planar planes that should not be drawn according to the specs.

I guess it's possible to golf this down quite some more, but 444 is such a nice number. :)

Example 3x3x3 and 7x7x7 output (with some newlines removed):

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

                +----+----+----+    +----+----+----+
               /              /|   /              /|
              +    +----+    + |  +    +----+    + |
             /    /|   /    /  + /    /|   /    /  +
            +    + |  +    +  / +    + |  +    +  /
           /    /  +-/    /  + /    /  +-/    /  +
          +----+  /-+----+  /-+----+  /-+----+  /--+
          |    | +  |    | +  |    | +  |    | +  /|
        +----+ | |+----+ | |+----+ | |+----+ | | + |
       /    /| + /    /| + /    /| + /    /| + |/  +
      +    + | |+    + | |+    + | |+    + | | +   |
     /    /  + /    /  + /    /  + /    /  + |   + |
    +    +----+    +   |+    +----+    +   | +  /| +
   /              /  + /              /  + | | + | |
  +----+----+----+  /|+----+----+----+  /| + |/--+ |
  |              | + ||              | + | |-+  /  +
  |              |/--+|              |/--+ |   +  /
  +----+----+----+  / +----+----+----+  /  +  /  +
    +    +  / +    +--- +    +  /-+    +  /--+  /--+
   /    /  + /              /  + /    /  +   | +  /|
  +----+  / +----+----+----+  /-+----+  /--+ |/  + |
  |    | +  |              | +  |    | +  /|-+  /  +
  |    | |-+|              |/  +|    | | + |   +  /
  +    + |  +----+----+----+  /|+    + |/  +  /  +
  |    | +----+----+ | |+    + ||    | +  /--+  /
  |    |/         /| + /    /  +|    |   +   | +
  +    +----+----+ | |+----+  /-+    +  /--+ |/
  |              | + ||    | +  |    | +  /|-+
  |              | | +|    | | +|    |/  + |
  +----+----+    + | |+    + |/|+----+  /  +
    +    +--|    | + ||    | + |  +    +  /
   /        |    | |-+|    |   +-/    /  +
  +----+----+    + |  +    +  / +----+  /
  |              | +  |    | +  |    | +
  |              |/   |    |/   |    |/
  +----+----+----+    +----+    +----+

```
> 12 votes

# Answer
# Lua (1442 bytes)

**Bonus animations! :)**
*If you have any cool voxel art in the same format as the examples, link it in the comments and I'll make an animation out of it*
7x7x7
12x12x12
This is my first code golf, so its quite messy and I plan on improving it or porting it to a different language.
Here is what i have, right now at just under 2.5kB barely-golfed (just removed indentation whitespace at this point, I will continue more later)

Here is the now ~1.4kB golfed and minified version (note the "a" table on the first line is the placeholder for the voxel matrix):

```
local a={}
local b,c=table,string;local d,e,f,g,h,i=b.concat,#a,c.gsub,c.gmatch,ipairs,b.insert;local function j(k,l,m)return a[k]and a[k][l]and a[k][l][m]==1 end;local n={}for o=1,e*5+1 do n[o]={}for p=1,e*7+1 do n[o][p]=" "end end;local q=[[
__6hhhh7
_g    ij
1aaaa2 j
b    d 5
b    de_
3cccc4__
]]local function r(k,l,m)local s=q;if j(k,l,m)then local t,u,v,w,x,y,z,A=j(k-1,l,m),j(k+1,l,m),j(k,l,m-1),j(k,l,m+1),j(k,l-1,m),j(k+1,l+1,m),j(k+1,l,m+1)," "if t then s=f(s,"[ai]"," ")end;if u and not y then A=A.."c"end;if u and not z then A=A.."e"end;if v then A=A.."bg"end;if w then A=A.."di"end;if x then if not j(k,l-1,m+1)then A=A.."j"end;A=A.."h"end;if t then if w and j(k-1,l,m+1)then A=A.."2"end;if v and j(k-1,l,m-1)then A=A.."1"end end;if u then if w and j(k+1,l,m+1)then A=A.."4"end;if v and j(k+1,l,m-1)then A=A.."3"end end;if x then if w and j(k,l-1,m+1)then A=A.."7"end;if v and j(k,l-1,m-1)then A=A.."6"end;if u and j(k+1,l-1,m)then A=A.."5"end end;s=f(f(f(f(f(s,"["..A.."]"," "),"[ach]","-"),"[bdj]","|"),"[gie]","/"),"[1234567]","+")else s=nil end;return s end;local B,C;local D=e*2-1;local E=1;for k=e,1,-1 do for l=1,e do for m=1,e do B=(l-1)*-2+(m-1)*5+D;C=(l-1)*2+(k-1)*3+E;local s=r(k,l,m)if s then local F={}for G in s:gmatch("[^\n]+")do local H={}for I in G:gmatch(".")do i(H,I)end;i(F,H)end;for J,K in h(F)do for L,I in h(K)do if I~="_"then n[C+J-1][B+L-1]=I end end end end end end end;for o,a in h(n)do print(d(a))end

```

**Edit**: Here is the original (over 3kB) ungolfed version, including my edits for making the animation (if you are running it yourself and want the animation, change the `false` near the bottom of the code to `true`.

```
local v = {}
local depth = #v;

function voxel(y,z,x)
  return (v[y] and v[y][z] and v[y][z][x]==1)
end

local canvas = {}
print("Constructing canvas of depth",depth)
for i=1,depth*5+1 do
  canvas[i] = {}
  for j=1,depth*7+1 do
    canvas[i][j] = " "
  end
end

local voxelProto = [[
__6hhhh7
_g    ij
1aaaa2 j
b    d 5
b    de_
3cccc4__
]]

function renderVoxel(y,z,x)
  local vox = voxelProto
  if (voxel(y,z,x)) then
    local up = voxel(y-1,z,x)
    local down = voxel(y+1,z,x)
    local left = voxel(y,z,x-1)
    local right = voxel(y,z,x+1)
    local back = voxel(y,z-1,x)
    local downFront = voxel(y+1,z+1,x)
    local downRight = voxel(y+1,z,x+1)

    if (up) then
      vox = vox:gsub("[ai]"," ")
    end
    if (down and not downFront) then
      vox = vox:gsub("[c]"," ")
    end
    if (down and not downRight) then
      vox = vox:gsub("[e]"," ")
    end
    if (left) then
      vox = vox:gsub("[bg]"," ")
    end
    if (right) then
      vox = vox:gsub("[di]"," ")
    end
    if (back and not voxel(y,z-1,x+1)) then
      vox = vox:gsub("[j]"," ")
    end
    if (back or up) then
      vox = vox:gsub("[h]"," ")
    end
    if (up and right and voxel(y-1,z,x+1)) then
      vox = vox:gsub("[2]"," ")
    end
    if (up and left and voxel(y-1,z,x-1)) then
      vox = vox:gsub("[1]"," ")
    end
    if (down and right and voxel(y+1,z,x+1)) then
      vox = vox:gsub("[4]"," ")
    end
    if (down and left and voxel(y+1,z,x-1)) then
      vox = vox:gsub("[3]"," ")
    end
    if (back and right and voxel(y,z-1,x+1)) then
      vox = vox:gsub("[7]"," ")
    end
    if (back and left and voxel(y,z-1,x-1)) then
      vox = vox:gsub("[6]"," ")
    end
    if (back and down and voxel(y+1,z-1,x)) then
      vox = vox:gsub("[5]"," ")
    end

    vox = vox:gsub("[ach]","-")
    vox = vox:gsub("[bdj]","|")
    vox = vox:gsub("[gie]","/")
    vox = vox:gsub("[1234567]","+")
  else
    vox = nil
  end
  return vox
end
local xpos,ypos
local minx = depth*2-1
local miny = 1;

local pic = {}
function drawCanvas()
  for k,v in pairs(canvas) do
    pic[k] = table.concat(v)
  end
  return table.concat(pic,"\n")
end

local timeline = {}
print("Compositing voxels")
for y=depth,1,-1 do
  for z=1,depth do
    for x = 1,depth do
      xpos = (z-1)*-2 + (x-1)*5 + minx
      ypos = (z-1)*2 + (y-1)*3 + miny
      local vox = renderVoxel(y,z,x)
      if (vox) then
        local vt = {}
        for line in vox:gmatch("[^\n]+") do
          local vtl = {}
          for c in line:gmatch(".") do
            table.insert(vtl,c)
          end
         table.insert(vt,vtl)
        end
        for ly,chars in ipairs(vt) do
          for lx,c in ipairs(chars) do
            if (c ~= "_") then
              canvas[ypos+ly-1][xpos+lx-1] = c
            end
          end
        end
        table.insert(timeline,drawCanvas())
      end
    end
  end
end

if (false) then -- change to true if you want to see the animation!
  for i=1,#timeline do
    local t = os.clock() + 0.05
    io.write(timeline[i],'\n\n')
    io.flush()
    while (t > os.clock()) do end
  end
end
print(timeline[#timeline])

```

Here is a sample of code that will populate the voxel matrix from a string for a 3x3x3 voxel matrix. (It will take any string in a similar format, but make sure it is a cube or things will probably break.)
To use this, insert this chunk right after the first line `local v = {}`

```
local vs = [[
100
000
000

110
100
000

111
110
101
]]
for layer in vs:gmatch("[^a]+") do
 local a = {}
 for row in layer:gmatch("[^\n]+") do
 local b = {}
 for _vox in row:gmatch("[01]") do
 table.insert(b,(_vox=="1") and 1 or 0)
 end
 table.insert(a,b)
 end
 table.insert(v,a)
end

```

Here is the output from the given 12x12x12 voxel pattern: (and yes it does look better on a normal console/text viewing apparatus, there is a bit too much vertical spacing here)

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

```

Here is the output from the 7x7x7 example here

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

```
> 21 votes

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


title: Primality Testing in Manufactoria

text:
# Question
Title: Primality Testing in Manufactoria
## Background

Manufactoria is a game about programming. The player must use a form of two-dimensional programming language to complete tasks. If you've never heard of it, the easiest way to learn is to try out the first few levels of the game.

## Challenge

Your challenge is to create a program which tests the primality of a number.

The input will be a series of N blue markers in the queue. If N is prime, then your program should accept it (move the robot to the finish). If N is composite, then your program should reject it (drop it on the floor somewhere).

## Submission Options

Since this is a more complex challenge than the typical Manufactoria challenge, I have decided to allow more ways to submit your answers.

**Vanilla**

I have created a 13x13 custom level to build and test submissions. The custom testing level is as follows.

> 13x13 custom level

The game only allows 8 test cases on a custom level, but *your creation should be theoretically able to handle any natural number N, limited only by the available memory.* For informational purposes, the test cases provided in the custom level are as follows:

```
1 -> reject
2 -> accept
4 -> reject
5 -> accept
7 -> accept
9 -> reject
11-> accept
15-> reject

```

**Expanded Grid**

Some users may want more room than a 13x13 grid. Here is a link to an in-game 15x15 custom level, created by changing a number in the URL:

> 15x15 custom level

Sadly, larger custom levels don't work, as the additional cells are inaccessible.

**The Manufactoria Esolang**

There has been an adaption of Manufactoria into an ASCII-based language. If you want a different way to design/test your creation, or if you are unable to fit your final solution onto the game board, you can use this esolang. You can find information on this esolang here:

> Manufactoria esolang

There are a few discrepancies between the esolang and the actual game. For example, conveyor crossings are handled differently. Try to avoid taking advantage of these discrepancies.

## A Faster Way to Test

The game is very slow when it comes to programs which take several thousands of steps to complete. My proof-of-concept solution took 28042 steps to reject 15. Even at the 50x speedup in-game, that simply takes too long.

I found this very helpful website. Simply copy-paste the link to your answer, and you can test your answer with specific inputs. The 28042-step process took under a second.

One thing to note is that it will often say something like "incorrectly accepted" even if your machine worked properly. This is because the webpage only knows the test cases. For example, it would say that my solution "incorrectly accepted" the number 3, even though my machine was actually correct.

## How to Win

The scoring criteria is the number of parts (cells occupied). This is code golf, so the submission with the fewest parts wins.

For those interested, my benchmark solution has 96 parts and fits on the 13x13 grid. Finding a better algorithm could lead to colossal improvements, since I know I used a sub-optimal algorithm.

# Answer
> 11 votes
# 53 parts - 11x11 grid

I just learned to play Manufactoria 2 days ago, so it is probably not very golf-optimized, but at least it solves the problem. It implements trial division of course, via repeated subtraction. All divisors from 2 to N-1 are checked. The time complexity should be O(N^3), I believe.

Solution Link

I was very disappointed to have to use a conveyor belt :)

---
Tags: code-golf, math, primes, manufactoria
---


# Question
Title: Photomosaics or: How Many Programmers Does it Take to Replace a Light Bulb?
I've compiled a mosaic of 2025 headshots from the avatars of the top Stack Overflow users.
*(Click the image to view it full-size.)*

Your task is to write an algorithm that will create an accurate photomosaic of another image using the 48×48 pixel avatars from this 45×45 grid of them.

## Test Images

Here are the test images. The first is, of course, a light bulb!
*(They are not full-sized here. Click an image to view it at full-size. Half-sized versions are available for The Kiss, A Sunday Afternoon..., Steve Jobs, and the spheres.)*

Thanks to Wikipedia for all but the raytraced spheres.

At full-size these images all have dimensions divisible by 48. The larger ones had to be JPEGs so they could be compressed enough to upload.

## Scoring

This is a popularity contest. The submission with mosaics that most accurately depict the original images should be voted up. I will accept the highest voted answer in a week or two.

## Rules

* Your photomosaics must be entirely composed of **unaltered** 48×48 pixel avatars taken from the mosaic above, arranged in a grid.
* You may reuse an avatar in a mosaic. (Indeed for the larger test images you'll have to.)
* Show your output, but keep in mind that the test images are very large, and **StackExchange only allows posting of images up to 2MB**. So compress your images or host them somewhere else and put smaller versions here.
* To be confirmed the winner you must provide PNG versions of your light bulb or spheres mosaics. This is so I can validate them (see below) to ensure you are not adding extra colors to the avatars to make the mosaics look better.

## Validator

This Python script can be used to check whether a completed mosaic really uses unaltered avatars. Just set `toValidate` and `allTiles`. It is unlikely to work for JPEGs or other lossy formats since it compares things exactly, pixel-for-pixel.

```
from PIL import Image, ImageChops

toValidate = 'test.png' #test.png is the mosaic to validate
allTiles = 'avatars.png' #avatars.png is the grid of 2025 48x48 avatars

def equal(img1, img2):
    return ImageChops.difference(img1, img2).getbbox() is None

def getTiles(mosaic, (w, h)):
    tiles = {}
    for i in range(mosaic.size[0] / w):
        for j in range(mosaic.size[1] / h):
            x, y = i * w, j * h
            tiles[(i, j)] = mosaic.crop((x, y, x + w, y + h))
    return tiles

def validateMosaic(mosaic, allTiles, tileSize):
    w, h = tileSize
    if mosaic.size[0] % w != 0 or mosaic.size[1] % h != 0:
        print 'Tiles do not fit mosaic.'
    elif allTiles.size[0] % w != 0 or allTiles.size[1] % h != 0:
        print 'Tiles do not fit allTiles.'
    else:
        pool = getTiles(allTiles, tileSize)
        tiles = getTiles(mosaic, tileSize)
        matches = lambda tile: equal(tiles[pos], tile)
        success = True
        for pos in tiles:
            if not any(map(matches, pool.values())):
                print 'Tile in row %s, column %s was not found in allTiles.' % (pos[1] + 1, pos[0] + 1)
                success = False
        if success:
            print 'Mosaic is valid.'
            return
    print 'MOSAIC IS INVALID!'

validateMosaic(Image.open(toValidate).convert('RGB'), Image.open(allTiles).convert('RGB'), (48, 48))

```

Good luck everyone! I cant wait to see the results.

**Note:** I know photomosaic algorithms are easy to find online, but they aren't yet on this site. I'm really hoping we see something more interesting than the usual *"average each tile and each grid space and match them up"* algorithm.

# Answer
### Java, average distance

```
package photomosaic;

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import javax.imageio.ImageIO;

public class MainClass {

    static final String FILE_IMAGE = "45148_sunday.jpg";
    static final String FILE_AVATARS = "25745_avatars.png";
    static final String FILE_RESULT = "mosaic.png";

    static final int BLOCKSIZE = 48;

    static final int SCALING = 4;

    static final int RADIUS = 3;

    public static void main(String[] args) throws IOException {
        BufferedImage imageAvatars = ImageIO.read(new File(FILE_AVATARS));
        int[] avatars = deBlock(imageAvatars, BLOCKSIZE);

        BufferedImage image = ImageIO.read(new File(FILE_IMAGE));
        int[] data = deBlock(image, BLOCKSIZE);

        // perform the mosaic search on a downscaled version
        int[] avatarsScaled = scaleDown(avatars, BLOCKSIZE, SCALING);
        int[] dataScaled = scaleDown(data, BLOCKSIZE, SCALING);
        int[] bests = mosaicize(dataScaled, avatarsScaled, (BLOCKSIZE / SCALING) * (BLOCKSIZE / SCALING), image.getWidth() / BLOCKSIZE);

        // rebuild the image from the mosaic tiles
        reBuild(bests, data, avatars, BLOCKSIZE);

        reBlock(image, data, BLOCKSIZE);
        ImageIO.write(image, "png", new File(FILE_RESULT));
    }

    // a simple downscale function using simple averaging
    private static int[] scaleDown(int[] data, int size, int scale) {
        int newsize = size / scale;
        int newpixels = newsize * newsize;
        int[] result = new int[data.length / scale / scale];
        for (int r = 0; r < result.length; r += newpixels) {
            for (int y = 0; y < newsize; y++) {
                for (int x = 0; x < newsize; x++) {
                    int avgR = 0;
                    int avgG = 0;
                    int avgB = 0;
                    for (int sy = 0; sy < scale; sy++) {
                        for (int sx = 0; sx < scale; sx++) {
                            int dt = data[r * scale * scale + (y * scale + sy) * size + (x * scale + sx)];
                            avgR += (dt & 0xFF0000) >> 16;
                            avgG += (dt & 0xFF00) >> 8;
                            avgB += (dt & 0xFF) >> 0;
                        }
                    }
                    avgR /= scale * scale;
                    avgG /= scale * scale;
                    avgB /= scale * scale;
                    result[r + y * newsize + x] = 0xFF000000 + (avgR << 16) + (avgG << 8) + (avgB << 0);
                }
            }
        }
        return result;
    }

    // the mosaicize algorithm: take the avatar with least pixel-wise distance
    private static int[] mosaicize(int[] data, int[] avatars, int pixels, int tilesPerLine) {
        int tiles = data.length / pixels;

        // use random order for tile search
        List<Integer> ts = new ArrayList<Integer>();
        for (int t = 0; t < tiles; t++) {
            ts.add(t);
        }
        Collections.shuffle(ts);

        // result array
        int[] bests = new int[tiles];
        Arrays.fill(bests, -1);

        // make list of offsets to be ignored
        List<Integer> ignores = new ArrayList<Integer>();
        for (int sy = -RADIUS; sy <= RADIUS; sy++) {
            for (int sx = -RADIUS; sx <= RADIUS; sx++) {
                if (sx * sx + sy * sy <= RADIUS * RADIUS) {
                    ignores.add(sy * tilesPerLine + sx);
                }
            }
        }

        for (int t : ts) {
            int b = t * pixels;
            int bestsum = Integer.MAX_VALUE;
            for (int at = 0; at < avatars.length / pixels; at++) {
                int a = at * pixels;
                int sum = 0;
                for (int i = 0; i < pixels; i++) {
                    int r1 = (avatars[a + i] & 0xFF0000) >> 16;
                    int g1 = (avatars[a + i] & 0xFF00) >> 8;
                    int b1 = (avatars[a + i] & 0xFF) >> 0;

                    int r2 = (data[b + i] & 0xFF0000) >> 16;
                    int g2 = (data[b + i] & 0xFF00) >> 8;
                    int b2 = (data[b + i] & 0xFF) >> 0;

                    int dr = (r1 - r2) * 30;
                    int dg = (g1 - g2) * 59;
                    int db = (b1 - b2) * 11;

                    sum += Math.sqrt(dr * dr + dg * dg + db * db);
                }
                if (sum < bestsum) {
                    boolean ignore = false;
                    for (int io : ignores) {
                        if (t + io >= 0 && t + io < bests.length && bests[t + io] == at) {
                            ignore = true;
                            break;
                        }
                    }
                    if (!ignore) {
                        bestsum = sum;
                        bests[t] = at;
                    }
                }
            }
        }
        return bests;
    }

    // build image from avatar tiles
    private static void reBuild(int[] bests, int[] data, int[] avatars, int size) {
        for (int r = 0; r < bests.length; r++) {
            System.arraycopy(avatars, bests[r] * size * size, data, r * size * size, size * size);
        }
    }

    // splits the image into blocks and concatenates all the blocks
    private static int[] deBlock(BufferedImage image, int size) {
        int[] result = new int[image.getWidth() * image.getHeight()];
        int r = 0;
        for (int fy = 0; fy < image.getHeight(); fy += size) {
            for (int fx = 0; fx < image.getWidth(); fx += size) {
                for (int l = 0; l < size; l++) {
                    image.getRGB(fx, fy + l, size, 1, result, r * size * size + l * size, size);
                }
                r++;
            }
        }
        return result;
    }

    // unsplits the block version into the original image format
    private static void reBlock(BufferedImage image, int[] data, int size) {
        int r = 0;
        for (int fy = 0; fy < image.getHeight(); fy += size) {
            for (int fx = 0; fx < image.getWidth(); fx += size) {
                for (int l = 0; l < size; l++) {
                    image.setRGB(fx, fy + l, size, 1, data, r * size * size + l * size, size);
                }
                r++;
            }
        }
    }
}

```

The algorithm performs a search through all avatar tiles for each grid space separately. Due to the small sizes I didn't implement any sophisticated data structurs or search algorithms but simply brute-force the whole space.

This code does not do any modifications to the tiles (e.g. no adaption to destination colors).

### Results

*Click for full-size image.*

### Effect of radius

Using `radius` you can reduce the repetitiveness of the tiles in the result. Setting `radius=0` there is no effect. E.g. `radius=3` supresses the same tile within a radius of 3 tiles.

radius=0

radius=3

### Effect of scaling factor

Using the `scaling` factor we can determine how the matching tile is searched. `scaling=1` means searching for a pixel-perfect match while `scaling=48` does a average-tile search.

scaling=48

scaling=16

scaling=4

scaling=1
> 15 votes

# Answer
# Mathematica, with control for granularity

This uses the 48 x 48 pixel photos, as required. By default, it will swap those pixels for a corresponding 48x48 pixel square from the image to be approximated.

However, the size of the destination squares can be set to be smaller than 48 x 48, allowing for greater fidelity to detail. (see the examples below).

## Preprocessing the palette

`collage` is the image containing the photos to serve as the palette.

`picsColors`is a list of individual photos paired with their mean red, mean green, and mean blue values.

targetColorToPhoto\[\]\` takes the average color of the target swath and finds the photo from the palette that best matches it.

```
parts=Flatten[ImagePartition[collage,48],1];
picsColors={#,c=Mean[Flatten[ImageData[#],1]]}&/@parts;
nf=Nearest[picsColors[[All,2]]];

targetColorToPhoto[p_]:=Cases[picsColors,{pic_,nf[p,1][[1]]}:>pic][[1]]

```

**Example**

Let's find the photo that best matches RGBColor\[0.640, 0.134, 0.249\]:

---

## photoMosaic

```
photoMosaic[rawPic_, targetSwathSize_: 48] :=
 Module[{targetPic, data, dims, tiles, tileReplacements, gallery},
  targetPic = Image[data = ImageData[rawPic] /. {r_, g_, b_, _} :> {r, g, b}];
  dims = Dimensions[data];
  tiles = ImagePartition[targetPic, targetSwathSize];
  tileReplacements = targetColorToPhoto /@ (Mean[Flatten[ImageData[#], 1]] & /@Flatten[tiles, 1]);
  gallery = ArrayReshape[tileReplacements, {dims[[1]]/targetSwathSize,dims[[2]]/targetSwathSize}];
  ImageAssemble[gallery]]

```

\`photoMosaic takes as input the raw picture we will make a photo mosaic of.

`targetPic` will remove a fourth parameter (of PNGs and some JPGs), leaving only R, G, B.

`dims` are the dimensions of `targetPic`.

`tiles` are the little squares that together comprise the target picture.

`targetSwathSize is the granularity parameter; it defaults at 48 (x48).`

`tileReplacements` are the photos that match each tile, in proper order.

`gallery` is the set of tile-replacements (photos) with the proper dimensionality (i.e. the number of rows and columns that match the tiles).

`ImageAssembly` joins up the mosaic into a continuous output image.

---

**Examples**

This replaces each 12x12 square from the image, Sunday, with a corresponding 48 x 48 pixel photograph that best matches it for average color.

```
photoMosaic[sunday, 12]

```

---

Sunday (detail)

---

```
photoMosaic[lightbulb, 6]

```

---

```
photoMosaic[stevejobs, 24]

```

---

Detail, stevejobs.

---

```
photoMosaic[kiss, 24]

```

---

Detail of the Kiss:

---

```
photoMosaic[spheres, 24]

```
> 19 votes

# Answer
**JS**

Same as in previous golf: http://jsfiddle.net/eithe/J7jEk/ :D

(this time called with `unique: false, {pixel_2: {width: 48, height: 48}, pixel_1: {width: 48, height: 48}}`) (don't treat palette to use one pixel once, palette pixels are 48x48 swatches, shape pixels are 48x48 swatches).

Currently it searches through the avatars list to find the nearest matching by weight of selected algorithm, however it doesn't perform any color uniformity matching (something I need to take a look at.

*
*

Unfortunately I'm not able to play around with larger images, because my RAM runs out :D If possible I'd appreciate smaller output images. If using 1/2 of image size provided, here's Sunday Afternoon:

*
*
> 7 votes

# Answer
## GLSL

The difference between this challenge and the one at American Gothic in the palette of Mona Lisa: Rearrange the pixels interested me, because the mosaic tiles can be re-used, whereas the pixels couldn't. This means that it is possible to easily parallelize the algorithm, so I decided to attempt a massively parallel version. By "massively" I mean using the 1344 shader cores on my desktop's GTX670 all simultaneously, via GLSL.

## Method

The actual tile-matching is simple: I calculate the RGB distance between each pixel in a target area and the mosaic tile area, and choose the tile with the lowest difference (weighted by brightness values). The tile index is written out in the red and green color attributes of the fragment, then after all the fragments have been rendered I read the values back out of the framebuffer and build the output image from those indices. The actual implementation is quite a hack; instead of creating an FBO I just opened a window and rendered into it, but GLFW can't open windows at arbitrarily small resolutions, so I create the window bigger than required, then draw a small rectangle that is the correct size so that it has one fragment per tile that maps to the source image. The entire MSVC2013 solution is available at https://bitbucket.org/Gibgezr/mosaicmaker It requires GLFW/FreeImage/GLEW/GLM to compile, and OpenGL 3.3 or better drivers/video card to run.

## Fragment Shader Source

```
#version 330 core

uniform sampler2D sourceTexture;
uniform sampler2D mosaicTexture;

in vec2 v_texcoord;

out vec4 out_Color;

void main(void)
{
    ivec2 sourceSize = textureSize(sourceTexture, 0);
    ivec2 mosaicSize = textureSize(mosaicTexture, 0);

    float num_pixels = mosaicSize.x/45.f;
    vec4 myTexel;
    float difference = 0.f;

    //initialize smallest difference to a large value
    float smallest_difference = 255.0f*255.0f*255.0f;
    int closest_x = 0, closest_y = 0;

    vec2 pixel_size_src = vec2( 1.0f/sourceSize.x, 1.0f/sourceSize.y);
    vec2 pixel_size_mosaic = vec2( 1.0f/mosaicSize.x , 1.0f/mosaicSize.y);

    vec2 incoming_texcoord;
    //adjust incoming uv to bottom corner of the tile space
    incoming_texcoord.x =  v_texcoord.x - 1.0f/(sourceSize.x / num_pixels * 2.0f);
    incoming_texcoord.y =  v_texcoord.y - 1.0f/(sourceSize.y / num_pixels * 2.0f);

    vec2 texcoord_mosaic;
    vec2 pixelcoord_src, pixelcoord_mosaic;
    vec4 pixel_src, pixel_mosaic;

    //loop over all of the mosaic tiles
    for(int i = 0; i < 45; ++i)
    {
        for(int j = 0; j < 45; ++j)
        {
            difference = 0.f;
            texcoord_mosaic = vec2(j * pixel_size_mosaic.x * num_pixels, i * pixel_size_mosaic.y * num_pixels);

            //loop over all of the pixels in the images, adding to the difference
            for(int y = 0; y < num_pixels; ++y)
            {
                for(int x = 0; x < num_pixels; ++x)
                {
                    pixelcoord_src = vec2(incoming_texcoord.x + x * pixel_size_src.x, incoming_texcoord.y + y * pixel_size_src.y);
                    pixelcoord_mosaic = vec2(texcoord_mosaic.x + x * pixel_size_mosaic.x, texcoord_mosaic.y + y * pixel_size_mosaic.y);
                    pixel_src = texture(sourceTexture, pixelcoord_src);
                    pixel_mosaic = texture(mosaicTexture, pixelcoord_mosaic);

                    pixel_src *= 255.0f;
                    pixel_mosaic *= 255.0f;

                    difference += (pixel_src.x - pixel_mosaic.x) * (pixel_src.x - pixel_mosaic.x) * 0.5f+
                        (pixel_src.y - pixel_mosaic.y) * (pixel_src.y - pixel_mosaic.y) +
                        (pixel_src.z - pixel_mosaic.z) * (pixel_src.z - pixel_mosaic.z) * 0.17f;
                }

            }

            if(difference < smallest_difference)
            {
                smallest_difference = difference;
                closest_x = j;
                closest_y = i;
            }
        }
    }

    myTexel.x = float(closest_x)/255.f;
    myTexel.y = float(closest_y)/255.f;
    myTexel.z = 0.f;
    myTexel.w = 0.f;

    out_Color = myTexel;
}

```

## Results

The images render almost instantly, so the parallelization was a success. The downside is that I can't make the individual fragments rely on the output of any other fragments, so there is no way to get the significant quality increase you can get by not picking the same tile twice within a certain range. So, fast results, but limited quality due to massive repetitions of tiles. All in all, it was fun. https://i.stack.imgur.com/MO7NU.jpg for full-size versions.
> 5 votes

# Answer
# Python

Here goes for the first Python solution, using a mean approach. We can evolve from here. The rest of the images are here.

```
from PIL import Image
import numpy as np

def calcmean(b):
    meansum = 0
    for k in range(len(b)):
        meansum = meansum + (k+1)*b[k]
    return meansum/sum(b)

def gettiles(imageh,w,h):
    k = 0
    tiles = {}
    for x in range(0,imageh.size[0],w):
        for y in range(0,imageh.size[1],h):
            a=imageh.crop((x, y, x + w, y + h))
            b=a.resize([1,1], Image.ANTIALIAS)
            tiles[k] = [a,x,y,calcmean(b.histogram()[0:256]) \
                             ,calcmean(b.histogram()[256:256*2]) \
                             ,calcmean(b.histogram()[256*2:256*3])]
            k = k + 1
    return tiles

w = 48
h = 48

srch = Image.open('25745_avatars.png').convert('RGB')
files = ['21104_spheres.png', '45148_sunday.jpg', '47824_steve.jpg', '61555_kiss.jpg', '77388_lightbulb.png']
for f in range(len(files)):
    desh = Image.open(files[f]).convert('RGB')

    srctiles = gettiles(srch,w,h)
    destiles = gettiles(desh,w,h)

    #build proximity matrix
    pm = np.zeros((len(destiles),len(srctiles)))
    for d in range(len(destiles)):
        for s in range(len(srctiles)):
            pm[d,s] = (srctiles[s][3]-destiles[d][3])**2 + \
                      (srctiles[s][4]-destiles[d][4])**2 + \
                      (srctiles[s][5]-destiles[d][5])**2

    for k in range(len(destiles)):
        j = list(pm[k,:]).index(min(pm[k,:]))
        desh.paste(srctiles[j][0], (destiles[k][1], destiles[k][2]))

    desh.save(files[f].replace('.','_m'+'.'))

```
> 4 votes

# Answer
# Yet Another Python Solution - Average Based (RGB vs L*a*b\*)

## Results (There are some slightly differences)

**Bulb - RGB**

full view

**Bulb - Lab**

full view

**Steve - RGB**

full view

**Steve - Lab**

full view

**Spheres - RGB**

full view

**Spheres - Lab**

full view

**Sunday - RGB**

full view

**Sunday - Lab**

full view

**Kiss - RGB**

full view

**Kiss - Lab**

full view

## Code

requires python-colormath for Lab

```
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from PIL import Image
from colormath.color_objects import LabColor,sRGBColor
from colormath.color_conversions import convert_color
from colormath.color_diff import delta_e_cie1976

def build_photomosaic_ils(mosaic_im,target_im,block_width,block_height,colordiff,new_filename):

    mosaic_width=mosaic_im.size[0]              #dimensions of the target image
    mosaic_height=mosaic_im.size[1]

    target_width=target_im.size[0]              #dimensions of the target image
    target_height=target_im.size[1]

    target_grid_width,target_grid_height=get_grid_dimensions(target_width,target_height,block_width,block_height)       #dimensions of the target grid
    mosaic_grid_width,mosaic_grid_height=get_grid_dimensions(mosaic_width,mosaic_height,block_width,block_height)       #dimensions of the mosaic grid

    target_nboxes=target_grid_width*target_grid_height
    mosaic_nboxes=mosaic_grid_width*mosaic_grid_height

    print "Computing the average color of each photo in the mosaic..."
    mosaic_color_averages=compute_block_avg(mosaic_im,block_width,block_height)
    print "Computing the average color of each block in the target photo ..."
    target_color_averages=compute_block_avg(target_im,block_width,block_height)

    print "Computing photomosaic ..."
    photomosaic=[0]*target_nboxes
    for n in xrange(target_nboxes):
        print "%.2f " % (n/float(target_nboxes)*100)+"%"
        for z in xrange(mosaic_nboxes):
            current_diff=colordiff(target_color_averages[n],mosaic_color_averages[photomosaic[n]])
            candidate_diff=colordiff(target_color_averages[n],mosaic_color_averages[z])

            if(candidate_diff<current_diff):
                photomosaic[n]=z

    print "Building final image ..."
    build_final_solution(photomosaic,mosaic_im,target_nboxes,target_im,target_grid_width,block_height,block_width,new_filename)

def build_initial_solution(target_nboxes,mosaic_nboxes):
    candidate=[0]*target_nboxes

    for n in xrange(target_nboxes):
        candidate[n]=random.randint(0,mosaic_nboxes-1)

    return candidate

def build_final_solution(best,mosaic_im,target_nboxes,target_im,target_grid_width,block_height,block_width,new_filename):

    for n in xrange(target_nboxes):

        i=(n%target_grid_width)*block_width             #i,j -> upper left point of the target image
        j=(n/target_grid_width)*block_height

        box = (i,j,i+block_width,j+block_height)

        #get the best photo from the mosaic
        best_photo_im=get_block(mosaic_im,best[n],block_width,block_height)

        #paste the best photo found back into the image
        target_im.paste(best_photo_im,box)

    target_im.save(new_filename);

#get dimensions of the image grid
def get_grid_dimensions(im_width,im_height,block_width,block_height):
    grid_width=im_width/block_width     #dimensions of the target image grid
    grid_height=im_height/block_height
    return grid_width,grid_height

#compute the fitness of given candidate solution
def fitness(candidate,mosaic_color_averages,mosaic_nboxes,target_color_averages,target_nboxes):
    error=0.0
    for i in xrange(target_nboxes):
        error+=colordiff_rgb(mosaic_color_averages[candidate[i]],target_color_averages[i])
    return error

#get a list of color averages, i.e, the average color of each block in the given image
def compute_block_avg(im,block_height,block_width):

    width=im.size[0]
    height=im.size[1]

    grid_width_dim=width/block_width                    #dimension of the grid
    grid_height_dim=height/block_height

    nblocks=grid_width_dim*grid_height_dim              #number of blocks

    avg_colors=[]
    for i in xrange(nblocks):
        avg_colors+=[avg_color(get_block(im,i,block_width,block_height))]
    return avg_colors

#returns the average RGB color of a given image
def avg_color(im):
    avg_r=avg_g=avg_b=0.0
    pixels=im.getdata()
    size=len(pixels)
    for p in pixels:
        avg_r+=p[0]/float(size)
        avg_g+=p[1]/float(size)
        avg_b+=p[2]/float(size)

    return (avg_r,avg_g,avg_b)

#get the nth block of the image
def get_block(im,n,block_width,block_height):

    width=im.size[0]

    grid_width_dim=width/block_width                        #dimension of the grid

    i=(n%grid_width_dim)*block_width                        #i,j -> upper left point of the target block
    j=(n/grid_width_dim)*block_height

    box = (i,j,i+block_width,j+block_height)
    block_im = im.crop(box)
    return block_im

#calculate color difference of two pixels in the RGB space
#less is better
def colordiff_rgb(pixel1,pixel2):

    delta_red=pixel1[0]-pixel2[0]
    delta_green=pixel1[1]-pixel2[1]
    delta_blue=pixel1[2]-pixel2[2]

    fit=delta_red**2+delta_green**2+delta_blue**2
    return fit

#http://python-colormath.readthedocs.org/en/latest/index.html
#calculate color difference of two pixels in the L*ab space
#less is better
def colordiff_lab(pixel1,pixel2):

    #convert rgb values to L*ab values
    rgb_pixel_1=sRGBColor(pixel1[0],pixel1[1],pixel1[2],True)
    lab_1= convert_color(rgb_pixel_1, LabColor)

    rgb_pixel_2=sRGBColor(pixel2[0],pixel2[1],pixel2[2],True)
    lab_2= convert_color(rgb_pixel_2, LabColor)

    #calculate delta e
    delta_e = delta_e_cie1976(lab_1, lab_2)
    return delta_e

if __name__ == '__main__':
    mosaic="images/25745_avatars.png"
    targets=["images/lightbulb.png","images/steve.jpg","images/sunday.jpg","images/spheres.png","images/kiss.jpg"]
    target=targets[0]
    mosaic_im=Image.open(mosaic)
    target_im=Image.open(target)
    new_filename=target.split(".")[0]+"_photomosaic.png"
    colordiff=colordiff_rgb

    build_photomosaic_ils(mosaic_im,target_im,48,48,colordiff,new_filename)

```
> 1 votes

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


title: Validate Loopy Solutions

text:
# Question
Title: Validate Loopy Solutions
This is an additional challenge to the generate Loopy puzzles challenge. You might want to solve this challenge before attempting the harder challenge in the previous link.

The goal of this challenge is to validate the solution to a loopy puzzle. Please take all documentation on what a loopy puzzle is from the previous link. A solved loopy puzzle is formatted in a very similar way to the output of a valid submission to the “generate loopy puzzles” challenge and may look like this:

```
+-+-+ +-+ +-+ +
|   | | |2|3|
+-+ + + + + +-+
 2| | | |2|  3|
+ + +-+ + + +-+
 2|  2 1|3| |
+-+ +-+ +-+ +-+
|2  | |    1 2|
+ +-+ +-+ +-+ +
| |2 1 2|3|3| |
+ + +-+ +-+ +-+
| | |3|2   1
+ +-+ +-+-+-+-+
|        2 2  |
+-+-+-+-+-+-+-+

```

The path that makes up the solution is marked with `|` and `-` characters between the `+` characters.

## Input specification

Your program shall receive a loopy puzzle with a solution formatted like the example above as input. Your program shall infer the size of the puzzle from the input. You may make the following assumptions about the input:

* The puzzle has no less than 2 and no more than 99 cells in either direction
* Thus, each line has a maximum length of 199 characters not including the newline character(s)
* Thus, the input contains a maximum of 99 lines
* each line may end after the last printable character or may be padded with whitespace characters so it has a length of up to *2·y + 1* characters where *y* is the number of cells in horizontal direction
* each position with both *x* and *y* coordinates even contains a `+` character
* positions horizontally or vertically adjacent to positions containing `+` characters contain either a whitespace character, are behind the end of line or contain a `-` character if horizontally adjacent or a `|` character if vertically adjacent
* all other positions are either behind the end of line or contain one of the characters , `0`, `1`, `2`, or `3`
* all lines are terminated with your platforms default newline character(s)
* there is exactly one trailing newline

Input shall be received in one of the following ways:

* From standard input
* As the value of a parameter named `p` in an HTTP POST request
* As the content of an HTML form
* As the content of a file named `p` in an implementation-defined directory
* In an implementation defined way at runtime if the former four are not available
* Hard coded if your language provides no mean of receiving input

## Output specification

Your program shall terminate for all inputs matching the input specification and shall compute whether the solution to the puzzle is correct. Your program shall output the result of the computation as a boolean value in one of the following ways:

* As an exit status of either zero (solution is valid) or non-zero (solution is invalid)
* As the character `y` (solution is valid) or `n` (solution is invalid) followed by zero or more arbitrary characters output in an implementation defined way

The behaviour of your program is unspecified when encountering input not formatted according to the input specification.

## Scoring

The score of your program is the number of characters in its source except for omittable whitespace characters and omittable comments. You are encouraged to indent your submission so it's easier to read for the others and to comment your solution so its easier to follow.

Submissions that fail to follow the input or output specification or generate incorrect results are invalid.

# Answer
### GolfScript, 133 characters

```
'|':^4,{48+.(}%+^*1>.^/'-'*+2/:F;4{{~@@/*}2F//n%zip-1%n*}:X*.'+-'?.3+@/(-2<' 9'+\+'9-+  99|+  9'3/:F;.,4*{X}*.9`?@=\' +09
'-!&'ny'1/=

```

Expects the input from STDIN and prints `y` for a valid solution and `n` for an invalid one. Performs the task by using mostly string-replace on the grid or with rotated versions of the grid.

*Annotated code:*

```
# construct the string "|0|/|1|0|2|1|3|2-0-/-1-0-2-1-3-2"
# split into pieces of two and save to variable F
'|':^4,{48+.(}%+^*1>.^/'-'*+
2/:F;

# run the code block X 4 times
# with X: string-replace 1st item in F with 2nd, 3rd with 4th, ...
# i.e. '|0' with '|/', '|1' with '|0'
# and then rotate grid by 90 degrees
4{{~@@/*}2F//n%zip-1%n*}:X*

# for a valid grid all digits are now reduced to exactly '0'
# (i.e. no '1' or '2' or '3' or '/')

# now follow the loop along and remove it
# start: find the first occurence of '+-+' and replace with '+ 9'
# note: '9' is the marker for the current position
.'+-'?
.3+@/(-2<' 9'+\+

# string-replace '9-+' or '9|+' by '  9' (i.e. go one step along the loop)
# using block X enough times
'9-+  99|+  9'3/:F;
.,4*{X}*

# look for the marker '9' in the result and check if it is at the original
# position again
.9`?
@=

# the remaining grid must not contain any digits besides 0 and 9
# esp. no '|' or '-' may remain
\' +09
'-!

# check if both conditions are fulfilled and output corresponding character
&'ny'1/=

```
> 2 votes

# Answer
## C# ~~803~~ 579bytes

Complete program, reads from STDIN, should cope with any common new-line scheme as long as it has line feeds. Thanks to HackerCow for pointing out that I don't have to append a new line in a different question, prompting me to remove it here and save 4 bytes

Golfed code:

```
using C=System.Console;class P{static void Main(){var D=C.In.ReadToEnd().Replace("\r","").Split('\n');int w=D[0].Length+2,h=D.Length+1,i=0,j,c,T=0,O=1,o,z,R=0;var B=new int[w,h];var S=new int[w*h*9];for(;i++<w-2;)for(j=0;j<h-2;B[i,j]=c)if((c=(D[j++][i-1]-8)%10)>5){c=5;T++;S[0]=i+j*w;}for(i=0;++i<w-1;)for(j=0;++j<h-1;)R=(i%2+j%2>1&(o=B[i,j-1]%2+B[i-1,j]%2+B[i+1,j]%2+B[i,j+1]%2)>0&o!=2)|((c=B[i,j])<4&c!=o)?7:R;for(o=h=0;o<O;B[i,j]=0)if(B[i=(c=S[o++])%w,j=c/w]>4){h++;S[O++]=(S[O++]=c-w-1)+2;S[O++]=(S[O++]=c+w-1)+2;z=j%2<1?w*2:2;S[O++]=c-z;S[O++]=c+z;}C.Write(h-R<T?"n":"y");}}

```

The code performs 3 checks, first checking the number of lines around each number and that each junction has 0 or 2 lines leading from it, then that all the lines are joined together.

Formatted code:

```
using C=System.Console;

class P
{
    static void Main()
    {
        var D=C.In.ReadToEnd().Replace("\r","").Split('\n');
        int w=D[0].Length+2,h=D.Length+1,i=0,j,c,T=0,O=1,o,z,R=0;
        var B=new int[w,h]; // this is the grid
        var S=new int[w*h*9]; // this is a list of joined up lines (stored as x+y*w)

        for(;i++<w-2;)
            for(j=0;j<h-2;B[i,j]=c)
                if((c=(D[j++][i-1]-8)%10)>5)
                { // we are a line
                    c=5;
                    T++; // increment line counter
                    S[0]=i+j*w; // set start of loop
                }

        for(i=0;++i<w-1;) // this loop checks the numbers and that every + has 0 or 2 lines leading from it
            for(j=0;++j<h-1;)
                R=(i%2+j%2>1&(o=B[i,j-1]%2+B[i-1,j]%2+B[i+1,j]%2+B[i,j+1]%2)>0&o!=2)|((c=B[i,j])<4&c!=o)?7:R; // set R to 7 (no significance) if check fails

        for(o=h=0;o<O;B[i,j]=0) // this loops through the list of joined lines adding more until the whole loop has been seen
            if(B[i=(c=S[o++])%w,j=c/w]>4)
            {
                h++; // increment "seen" counter
                S[O++]=(S[O++]=c-w-1)+2;
                S[O++]=(S[O++]=c+w-1)+2;
                z=j%2<1?w*2:2; // special for | and -
                S[O++]=c-z;
                S[O++]=c+z;
            }

        C.Write(h-R<T?"n":"y"); // check if R is greater than 0 or h is less than T and output appropriately
    }
}

```
> 2 votes

# Answer
# Cobra - 514

```
class P
    def main
        t,m,g=[[1]][:0],nil,File.readAllLines('p')
        u,i=g[0].length,1
        for l in g.length,for c in u,if g[l][c]in'0123'
            n=0
            for j in-1:2:2,for r in[g[l+j][c],g[l][c+j]],if r in'-|',n+=1
            if'[n]'<>g[l][c],m?='n'
        else if g[l][c]in'-|',x,y,t,d=c,l,t+[[c,l]],g[l][c]
        while i
            i=z=6
            for f,b in[[-1,1],[1,1],[0,2],[-1,-1],[+1,-1],[0,-2]]
                if'-'==d,f,b=b,f
                for w in t.count,if z and t[w]==[x+f,y+b],t,x,y,d,z=t[:w]+t[w+1:],x+=f,y+=b,g[y][x],0
                i-=z//6
        print if(t.count,'n',m?'y')

```

Checks if every number has the right number of lines next to it, and then walks a path around the lines and checks if it missed any.
> 1 votes

---
Tags: code-golf
---


title: Domino Circuits

text:
# Question
Title: Domino Circuits
## Scoreboard

Here are the raw scores (i.e. domino counts) for VisualMelon's submission. I'll turn these into the normalised scores described below, when more answers come in. The existing solution can now solve all circuits in the benchmark:

```
 Author       Circuit:   1   2   3   4    5    6   7    8   9  10  11  12   13  14   15   16   17   18  19   20   21  22   23   24    25   26   27   28    29    30    31    32   33   34    35    36     37      38   39
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
VisualMelon             39  45  75  61  307  337  56  106  76  62  64  62  182  64  141  277  115  141  92  164  223  78  148  371  1482  232  107  782  4789  5035  1314  3213  200  172  1303  3732  97596  156889  857
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Legend:
  I - invalid circuit
  B - circuit too big
  W - circuit computes wrong function
  T - exceeded time limit

```

## The Challenge

It is possible to build simple logic gates from dominoes. Hence, by combining these or otherwise, arbitrary binary functions can be computed with dominoes.

But of course, everyone who has played with dominoes (except Robin Paul Weijers) has experienced the disappointment when running out of them. Hence, we want to use our dominoes as efficiently as possible, so we can do some really interesting computations with the material we have.

Note, that you cannot produce non-zero output from zero input per se, so we'll need to add a "power line", which falls along your setup, and which you can pull `1`s from at any time.

## Your task

Given a boolean function with `M` inputs and `N` outputs (`f: {0,1}^M --> {0,1}^N` for the mathematically inclined), produce a domino circuit with as few dominoes as possible which computes that function. You'll be using the symbols `|`, `-`, `/`, `\` to represent dominoes in various orientations.

### Input

You'll be given input via command-line arguments:

```
[command for your solver] M N f

```

where `M` and `N` are positive integers and `f` is the comma separated truth table in canonical order. That is, `f` will contain `2^M` values of length `N`. E.g. if `M = N = 2` and the first bit in the output was the AND function while the second bit was the OR function, `f` would read

```
00,01,01,11

```

### Output

Write to STDOUT an ASCII grid representing the domino setup. Your setup has to fit in the following framework

```
/////.../////
 ????...????
I????...????O
I????...????O
.............
.............
I????...????O
I????...????O
I????...????O

```
* The top row consists entirely of `/`, and the leftmost domino is guaranteed to be toppled over at the beginning - this is your power line.
* The leftmost column consists of your inputs. Each `I` may either be a space or a `|`, such that there are exactly `M` `|`s.
* The rightmost column consists of your outputs. Each `O` may either be a space or a `|`, such that there are exactly `N` `|`s.
* Note that there is at least one blank before the first `|` in the input or output.
* The `.` indicate that the grid can be arbitrarily large.
* You can fill `?` in any way you want.

Note that the bottom input is the fastest-varying while you go along the truth table, while the top input is the `0` for the first half of the outputs and `1` for the second half.

## Rules

Dominoes propagate as specified in Golfing for Domino Day. In short, if we represent the falling directions as letters

```
Q W E
A   D
Z X C

```

then these are all unique combinations which can propagate (as well as their rotations and reflections):

```
D|   ->    DD          D\   ->    DE          D/   ->    DC

C|   ->    CD          C/   ->    CC

C    ->    C           C    ->    C           C    ->    C
 |          D           -          X           /          C

```

All of the above rules are applied simultaneously at each time step. If two of those rules are in conflict (i.e. a tile is pushed into two *valid* opposite directions at the same time), the affected tile will *not* fall, and will effectively be locked into position for the rest of the simulation.

## Restrictions

* `M` and `N` will never exceed 6.
* Your solver must produce a circuit within ***N * 2M* seconds**.
* Your solver must not use more than **1 GB of memory**. This is a soft limit, as I will be monitoring this manually and kill your process if it significantly/continuously exceeds this limit.
* No circuit is permitted to contain more than **8,000,000 cells** or **1,000,000 dominoes**.
* Your submission must be **deterministic**. You are allowed to use pseudo-random number generators, but they must use a hardcoded seed (which you are free to optimise as much as you care to).

## Scoring

For each circuit, let `D` be total number of dominoes in your circuit and `B` the lowest number of dominoes this circuit has been solved with (by you or any other participant). Then your score for this circuit is given by `10,000 * B / D` rounded down. If you failed to solve the circuit, your score is 0. Your overall score will be the sum over a benchmark set of test cases. Circuits that have not yet been solved by anyone will not be included in the total score.

Each participant may add one test case to the benchmark (and all other submissions will be re-evaluated including that new test case).

The benchmark file can be found on GitHub.

## Examples

Here are some non-optimally solved examples.

**Constant 1**

```
1 1
1,1

///////
   /
|   |||

```

Domino count: 12

**OR gate**

```
2 1
0,1,1,1

///////////

|||||/
      |||||
|||||\

```

Domino count: 28

**AND gate**

```
2 1
0,0,0,1

///////////////////

       \-/
       - -
|||||/|\ /|||/
      /      -
       -    \-
      \-   \ -
|||||\ /  \  /
        |\    |||||

```

Domino count: 62

**Swap lanes**

```
2 2
00,10,01,11

////////////

||||/  \||||
     /\
     \/
||||\  /||||

```

Domino count: 36

## Additional Notes

The propagation rules are such, that diagonal lanes *can* cross using a diamond shape (see last example) even if one falls before the other (unlike with real dominoes).

As a starting point, you can use the (not minimised) logical gates in this gist and try combining as few of these as possible. For a simple (non-optimal) way to build arbitrary boolean functions from AND, OR and NOT gates, have a look at Conjunctive and Disjunctive Normal Forms.

There is a verifier this GitHub repository to test your code, which will also be used to score all submissions. This outputs the raw scores (domino counts) and saves them to a file to be processed by a separate scorer (also in that repository) to obtain the final scores.

General documentation can be found within the two Ruby files, but the `controller.rb` takes two command line switches before the benchmark file:

* `-v` gives you some more output, including the actual circuits produced by your solver.
* `-c` lets you select a subset of the benchmark you want to test. Provide the desired circuits as a comma-separated list of 1-based indices. You can also use Ruby ranges, so you could do something like `-c 1..5,10,15..20`.

Please include in your answer:

* Your code
* A command to (compile and) run your code. I'll ask you where to obtain the necessary compilers/interpreters if I don't have them.
* An additional truth table with a name, to be added as a test case to the benchmark. (This is optional, but strongly encouraged.)

I'll be testing all submissions on Windows 8.

# Answer
> 34 votes
## C# - Massive, Slow, and inefficient solution

*Confession: wrote this solution some time ago when the question was still in the sandbox, but it's not very good: **you can do better!***

*Edit: replaced the boring solving with a less boring, more flexible, and generally better method*

You run the program by compiling with `csc dominoPrinter.cs` and then passing arguments to the executable, for example (the 4-bit prime checker):

```
dominoPrinter.exe 4 1 0,0,1,1,0,1,0,1,0,0,0,1,0,1,1,1

```

Explanation:

The "Domino Printer" is a 3-stage program:

**Stage 1**: The "solver" generates an expression tree of "ifnot" and "or" binary operations with the given inputs, and a "1" from the powerline, there are 2ways this is done, depending on the number of inputs:

* If there are fewer than 4 inputs the program brutes a solution of the fewest number of operations
* If there are 4 or more inputs the program brutes each 8bit chunk of output and then combines the results to give the desired output. The bruted bits if flexible: the more bruted bits, the smaller the solution, but the longer the run-time.

The "solver" is what takes all the time (or at least it used to), and is also most of the code. I *believe* there is a well documented, fast, not so memory hungry, and probably optimal solution to this problem, but where would the fun be in looking it up?

The (bruted) expression tree for the 4-bit prime checker is

```
((2 or 1) ifnot (((0 ifnot 1) or ((1 ifnot 0) or (0 ifnot 2))) ifnot 3))

```

where the numbers are the indexes of the inputs.

**Stage 2**: The "organizer" takes the expression tree as input and assembles a "skeleton" layout, which precisely describes a domino layout made from some a set of 4x5 overlapping cells. Below is the skeleton for the bruted 4-bit prime checker (you'll need to change the `bruteBase` integer variable on line 473 to 4 (or larger) to get this result).

```
18 9
I ___ _ _______  O
 v _ X X ____  uu
I X X X u    UU/
 v X X v ___///
I X X \ u   //
 v X \ v __//
I_X \ \_u  /
   \ \ ___/
    \_U

```

This output is effectively made up to two parts, the "evaluator" on the right, which is created from the expression tree from stage 1, and the "switchboard" on the left, which swaps and splits the inputs so that they arrive in the right places for the "evaluator" to handle.

There is considerable scope for compacting the layout at this point, but the program currently does very little such work. The code for this stage is horrible, but pretty simple underneath (see the "orifnot" method). The output is passed to stage 3.

**Stage 3**: The "printer" takes the output from the "organizer" and prints the corresponding 4x5 overlapping "cells" along with the power line. Below is an animation of the bruted 4-bit prime checker checking whether 5 is prime.

Code *the lack of indenting is to avoid going over the SE 30k character limit which it would otherwise*:

```
using System;
using System.Collections.Generic;

namespace dominoPrinter
{
 class Program
 {
  static string bstring(bool[] barr)
  {
   string str = "";
   foreach (bool b in barr)
    str += b?1:0;
   return str;
  }

  public static void Main(string[] args)
  {

   int inputCount;
   val[] vals = resolveVals(args[0], args[1], args[2], out inputCount);

   System.IO.StringWriter sw = new System.IO.StringWriter();
   orifnot(inputCount, vals, sw);
   System.IO.StringReader sr = new System.IO.StringReader(sw.ToString());

   printDominoes(sr, Console.Out, args.Length > 3 && args[3] == "quite");
  }

  public abstract class val
  {
   public int size;
   public bool[] rs;
   public abstract string strness();
  }

  public class baseVal : val
  {
   public bool b;
   public int id;

   public baseVal(int idN)
   {
    id = idN;
    size = 1;
   }

   public override string strness()
   {
    return id.ToString();
   }
  }

  public abstract class biopVal : val
  {
   public val a, b;

   public biopVal(val aN, val bN)
   {
    a = aN;
    b = bN;
    size = a.size + b.size;
   }

   public bool buildCheckApply(nodev ntree)
   {
    nodev cur = ntree;
    rs = new bool[a.rs.Length];
    bool notOK = true;
    for (int i = 0; i < rs.Length; i++)
    {
     bool r = rs[i] = go(a.rs[i], b.rs[i]);
     if (notOK)
     {
      if (r)
      {
       if (cur.a == null)
        notOK = false;
       else
       {
        cur = cur.a;
        if (cur == nodev.full)
         return false;
       }
      }
      else
      {
       if (cur.b == null)
        notOK = false;
       else
       {
        cur = cur.b;
        if (cur == nodev.full)
         return false;
       }
      }
     }
    }

    ntree.apply(this, 0);
    return true;
   }

   public abstract bool go(bool a, bool b);
  }

  public class ifnotVal : biopVal
  {
   public override bool go(bool a, bool b)
   {
     return a ? false : b; // b IF NOT a, else FALSE
   }

   public ifnotVal(val aN, val bN) : base(aN, bN)
   {
   }

   public override string strness()
   {
    return "(" + b.strness() + " ifnot " + a.strness() + ")";
   }
  }

  public class orval : biopVal
  {
   public override bool go(bool a, bool b)
   {
    return a || b; // a OR b
   }

   public orval(val aN, val bN) : base(aN, bN)
   {
   }

   public override string strness()
   {
    return "(" + b.strness() + " or " + a.strness() + ")";
   }
  }

  static bool boolCompare(bool[] a, bool b)
  {
   for (int i = 0; i < a.Length; i++)
   {
    if (a[i] != b)
    {
     return false;
    }
   }
   return true;
  }

  static bool boolFlat(bool[] a)
  {
   bool p = a[0];
   for (int i = 1; i < a.Length; i++)
   {
    if (a[i] != p)
     return false;
   }
   return true;
  }

  static bool boolCompare(bool[] a, bool[] b)
  {
   if (a.Length != b.Length)
    return false; // let's do this proeprly
   for (int i = 0; i < a.Length; i++)
   {
    if (a[i] != b[i])
    {
     return false;
    }
   }
   return true;
  }

  // solver

  // these is something VERY WRONG with the naming in this code
  public class nodev
  {
   public static nodev full = new nodev();

   public nodev a, b;

   public nodev()
   {
    a = null;
    b = null;
   }

   public bool contains(bool[] rs)
   {
    nodev cur = this;
    if (cur == full)
     return true;

    for (int i = 0; i < rs.Length; i++)
    {
     if (rs[i])
     {
      if (cur.a == null)
       return false;
      cur = cur.a;
     }
     else
     {
      if (cur.b == null)
       return false;
      cur = cur.b;
     }

     if (cur == full)
      return true;
    }
    return true;
   }

   public bool contains(val v)
   {
    nodev cur = this;
    if (cur == full)
     return true;

    for (int i = 0; i < v.rs.Length; i++)
    {
     if (v.rs[i])
     {
      if (cur.a == null)
       return false;
      cur = cur.a;
     }
     else
     {
      if (cur.b == null)
       return false;
      cur = cur.b;
     }

     if (cur == full)
      return true;
    }
    return true;
   }

   // returns whether it's full or not
   public bool apply(val v, int idx)
   {
    if (v.rs[idx])
    {
     if (a == null)
     {
      if (idx == v.rs.Length - 1)
      { // end of the line, fellas
       a = full;
       if (b == full)
        return true;
       return false;
      }
      else
      {
       a = new nodev();
      }
     }
     if (a.apply(v, idx + 1))
      a = full;
     if (a == full && b == full)
      return true;
    }
    else
    {
     if (b == null)
     {
      if (idx == v.rs.Length - 1)
      { // end of the line, fellas
       b = full;
       if (a == full)
        return true;
       return false;
      }
      else
      {
       b = new nodev();
      }
     }
     if (b.apply(v, idx + 1))
      b = full;
     if (a == full && b == full)
      return true;
    }
    return false;
   }
  }

  public static void sortOutIVals(baseVal[] ivals, int rc)
  {
   for (int i = 0; i < ivals.Length; i++)
   {
    ivals[i].rs = new bool[rc];
    ivals[i].b = false;
   }

   int eri = 0;

   goto next;
  again:
   for (int i = ivals.Length - 1; i >= 0; i--)
   {
    if (ivals[i].b == false)
    {
     ivals[i].b = true;
     goto next;
    }
    ivals[i].b = false;
   }

   return;
  next:
   for (int i = ivals.Length - 1; i >= 0; i--)
   {
    ivals[i].rs[eri] = ivals[i].b;
   }

   eri++;
   goto again;
  }

  public static val[] resolve(int inputCount, int c, bool[][] erss, out baseVal[] inputs)
  {
   val[] res = new val[erss.Length];

   List<List<val>> bvals = new List<List<val>>();
   nodev ntree = new nodev();

   List<val> nvals = new List<val>();

   baseVal tval = new baseVal(-1);
   baseVal fval = new baseVal(-2);
   baseVal[] ivals = new baseVal[inputCount];
   inputs = new baseVal[inputCount + 2];

   for (int i = 0; i < inputCount; i++)
   {
    ivals[i] = new baseVal(i); // value will change anyway
    inputs[i] = ivals[i];
   }
   inputs[inputCount] = fval;
   inputs[inputCount + 1] = tval;

   sortOutIVals(ivals, c);

   for (int i = 0; i < inputCount; i++)
   {
    nvals.Add(ivals[i]);
   }

   tval.rs = new bool[c];
   fval.rs = new bool[c];
   for (int i = 0; i < c; i++)
   {
    tval.rs[i] = true;
    fval.rs[i] = false;
   }

   nvals.Add(tval);
   nvals.Add(fval); // ifnot and or do nothing with falses

   bvals.Add(new List<val>());

   foreach (val v in nvals)
   {
    ntree.apply(v, 0);
    if (!boolFlat(v.rs))
     bvals[0].Add(v); // I trust these are distinct..
   }

   Func<biopVal, bool> checkValb = (v) =>
   {
    if (!v.buildCheckApply(ntree))
    {
     return false;
    }
    bvals[v.size-1].Add(v);
    return true;
   };

   Action<biopVal, List<val>> checkVal = (v, li) =>
   {
    if (checkValb(v))
     li.Add(v);
   };

   int maxSize = 1;

  again:
   for (int i = 0; i < erss.Length; i++)
   {
    bool[] ers = erss[i];
    if (res[i] == null && ntree.contains(ers))
    {
     // there is a reason this is separate... I'm sure there is....
     foreach (val rv in nvals)
     {
      if (boolCompare(rv.rs, ers))
      {
       res[i] = rv;
       break;
      }
     }
    }
   }

   for (int i = 0; i < erss.Length; i++)
   {
    if (res[i] == null)
     goto notoveryet;
   }
   return res;

  notoveryet:

   maxSize++;
   bvals.Add(new List<val>()); // bvals[maxSize-1] always exists

   nvals.Clear();
   long cc = 0;

   List<val> sbvals = bvals[maxSize - 2];
   // NOTs have a habit of working out, get it checked first
   for (int i = sbvals.Count - 1; i >= 0; i--)
   { // also known as nvals, but let's ignore that
    val arv = sbvals[i];
    checkVal(new ifnotVal(arv, tval), nvals);
    cc += 1;
   }

   for (int s = 1; s < maxSize; s++)
   {
    List<val> abvals = bvals[s - 1];
    int t = maxSize - s;
    if (t < s)
     break;
    List<val> bbvals = bvals[t - 1];

    for (int i = abvals.Count - 1; i >= 0; i--)
    {
     val arv = abvals[i];

     int jt = t == s ? i : bbvals.Count - 1;
     for (int j = jt; j >= 0; j--)
     {
      val brv = bbvals[j];

      checkVal(new ifnotVal(brv, arv), nvals);
      checkVal(new ifnotVal(arv, brv), nvals);
      checkVal(new orval(brv, arv), nvals); // don't technically need ors, but they are good fun
      cc += 3;
     }
    }
   }

   int bc = 0;
   foreach (List<val> bv in bvals)
    bc += bv.Count;
   goto again;
  }

  public static val[] resolveVals(string mStr, string nStr, string erStr, out int inputCount)
  {
   int ic = int.Parse(mStr);
   int oc = int.Parse(nStr);
   inputCount = ic;
   int bruteBase = 3;
   if (inputCount <= bruteBase)
    return resolveVals(ic, oc, erStr);
   else
    return resolveValFours(bruteBase, ic, oc, erStr);
  }

  public static val joinVals(val low, val high, baseVal inp, baseVal tval, baseVal fval)
  {
   val lowCut = low == fval ? (val)fval : low == tval ? (val)new ifnotVal(inp, tval) : (val)new ifnotVal(inp, low);

   val highCut = high == fval ? (val)fval : high == tval ? (val)inp : (val)new ifnotVal(new ifnotVal(inp, tval), high);

   if (highCut == fval)
    return lowCut;
   if (lowCut == fval)
    return highCut;
   return new orval(highCut, lowCut);
  }

  public static val resolveValFour(int n, int m, int inputCount, bool[] ers)
  {
   // solves fours
   int fc = ers.Length / m;
   bool[][] fours = new bool[fc][];

   for (int i = 0; i < fc; i++)
   {
    fours[i] = new bool[m];
    for (int j = 0; j < m; j++)
    {
     fours[i][j] = ers[i*m+j];
    }
   }

   baseVal[] inputs;
   val[] fres = resolve(n, m, fours, out inputs);
   baseVal tval = inputs[inputs.Length - 1];
   baseVal fval = inputs[inputs.Length - 2];

   for (int i = 0; i < n; i++)
   {
    inputs[i].id += inputCount - n;
   }

   // assemble
   for (int i = 0, c = 1; c < fc; c *= 2, i++)
   {
    for (int j = 0; j + c < fc; j += c * 2)
    {
     fres[j] = joinVals(fres[j], fres[j+c], new baseVal((inputCount - n - 1) - i), tval, fval);
    }
   }

   return fres[0];
  }

  public static val[] resolveValFours(int n, int inputCount, int outputCount, string erStr)
  {
   int m = 1;
   for (int i = 0; i < n; i++)
    m *= 2;

   val[] res = new val[outputCount];

   string[] data = erStr.Split(',');
   for (int i = 0; i < outputCount; i++)
   {
    bool[] ers = new bool[data.Length];
    for (int j = 0; j < data.Length; j++)
     ers[j] = data[j][i] == '1';
    res[i] = resolveValFour(n, m, inputCount, ers);
   }

   return res;
  }

  public static val[] resolveVals(int inputCount, int outputCount, string erStr)
  {
   val[] res;

   string[] data = erStr.Split(',');
   bool[][] erss = new bool[outputCount][];
   for (int i = 0; i < outputCount; i++)
   {
    bool[] ers = new bool[data.Length];
    for (int j = 0; j < data.Length; j++)
     ers[j] = data[j][i] == '1';
    erss[i] = ers;
   }

   baseVal[] inputs; // no need
   res = resolve(inputCount, data.Length, erss, out inputs);

   return res;
  }

  // organiser
  public class vnode
  {
   private static vnode[] emptyVC = new vnode[0];
   public static vnode oneVN = new vnode('1');
   public static vnode noVN = new vnode(' ');
   public static vnode flatVN = new vnode('_');
   public static vnode moveUpVN = new vnode('/');
   public static vnode moveDownVN = new vnode('\\');
   public static vnode inputVN = new vnode('I');
   public static vnode outputVN = new vnode('O');
   public static vnode swapVN = new vnode('X');
   public static vnode splitDownVN = new vnode('v');

   public int size;
   public vnode[] children;
   public char c;
   public int id = -3;

   public vnode(char cN)
   {
    c = cN;
    children = emptyVC;
    size = 1;
   }

   public vnode(val v)
   {
    biopVal bv = v as biopVal;

    if (bv != null)
    {
     children = new vnode[2];
     children[0] = new vnode(bv.a);
     children[1] = new vnode(bv.b);
     size = children[0].size + children[1].size;

     if (bv is orval)
      c = 'U';
     if (bv is ifnotVal)
      c = 'u';
    }
    else
    {
     children = emptyVC;
     size = 1;
     c = 'I';
     id = ((baseVal)v).id;
    }
   }
  }

  public class nonArray<T>
  {
   public int w = 0, h = 0;
   Dictionary<int, Dictionary<int, T>> map;

   public nonArray()
   {
    map = new Dictionary<int, Dictionary<int, T>>();
   }

   public T this[int x, int y]
   {
    get
    {
     Dictionary<int, T> yd;
     if (map.TryGetValue(x, out yd))
     {
      T v;
      if (yd.TryGetValue(y, out v))
      {
       return v;
      }
     }
     return default(T);
    }
    set
    {
     if (x >= w)
      w = x + 1;
     if (y >= h)
      h = y + 1;
     Dictionary<int, T> yd;
     if (map.TryGetValue(x, out yd))
     {
      yd[y] = value;
     }
     else
     {
      map[x] = new Dictionary<int, T>();
      map[x][y] = value;
     }
    }
   }
  }

  public static int fillOutMap(nonArray<vnode> map, vnode rn, int y, int x)
  {
   if (rn.children.Length == 0)
   {
    map[y,x] = rn;
    return 1;
   }
   else
   {
    map[y+1,x] = rn;
    for (int i = 0; i < rn.children.Length; i++)
    {

     if (i == 0)
     {
      fillOutMap(map, rn.children[i], y, x + 1);
     }

     if (i == 1)
     {
      int ex = x + rn.children[0].size;
      for (int j = 1; j < ex - x; j++)
       map[y - j + 1,ex - j] = vnode.moveUpVN;
      fillOutMap(map, rn.children[i], y, ex);
     }

     y += rn.children[i].size;
    }
   }

   return rn.size;
  }

  public static void orifnot(int inputCount, val[] vals, System.IO.TextWriter writer)
  {
   // step one - build weird tree like thing of death
   nonArray<vnode> map = new nonArray<vnode>();

   int curY = 0;
   foreach (val v in vals)
   {
    vnode vnt = new vnode(v);
    map[curY, 0] = vnode.outputVN;
    curY += fillOutMap(map, vnt, curY, 1);
   }

   // step two - build the thing to get the values to where they need to be
   // find Is
   List<int> tis = new List<int>();
   for (int y = 0; y < map.w; y++)
   {
    for (int x = map.h - 1; x >= 0; x--)
    {
     vnode vn = map[y,x];
     if (vn != null && vn.c == 'I')
     {
      tis.Add(vn.id);
      if (vn.id > -2)
      {
       for (;x < map.h; x++)
       {
        map[y,x] = vnode.flatVN;
       }
      }
      goto next;
     }
    }
    tis.Add(-2);
   next:
    continue;
   }

   // I do not like this piece of code, it can be replaced further down for the better if you get round to thinking about it
   // add unused Is
   for (int z = 0; z < inputCount; z++)
   {
    if (!tis.Contains(z))
    {
     int midx = tis.IndexOf(-2);
     if (midx != -1)
     {
      tis[midx] = z;
      map[midx,map.h-1] = vnode.noVN;
     }
     else
     {
      tis.Add(z);
      map[map.w,map.h-1] = vnode.noVN;
     }
    }
   }

   int curX = map.h;

  MORE:
   for (int y = 0; y < map.w; y++)
   {
    if (y == map.w - 1)
    {
     if (tis[y] == -2)
      map[y,curX] = vnode.noVN;
     else
      map[y,curX] = vnode.flatVN;
    }
    else
    {
     int prev = tis[y];
     int cur = tis[y + 1];

     if (cur != -2 && (prev == -2 || cur < prev))
     { // swap 'em
      map[y,curX] = vnode.noVN;
      if (prev == -2)
       map[y+1,curX] = vnode.moveDownVN;
      else
       map[y+1,curX] = vnode.swapVN;
      int temp = tis[y];
      tis[y] = tis[y + 1];
      tis[y + 1] = temp;
      y++; // skip
     }
     else
     {
      if (/*thatThingThat'sAThing*/ prev == cur && cur != -2)
      {
       map[y,curX] = vnode.noVN;
       map[y+1,curX] = vnode.splitDownVN;
       int temp = tis[y];
       tis[y+1] = -2;
       y++; // skip
      }
      else
      {
       if (prev == -2)
        map[y,curX] = vnode.noVN;
       else
        map[y,curX] = vnode.flatVN;
      }
     }
    }
   }

   // check if sorted
   for (int y = 0; y < map.w - 1; y++)
   {
    int prev = tis[y];
    int cur = tis[y + 1];

    if (cur != -2 && (prev == -2 || cur < prev))
     goto NOTSORTED;
   }

   goto WHATNOW;

  NOTSORTED:
   curX++;
   goto MORE;

  WHATNOW:

   tis.Add(-2); // this is to avoid boud checking y+2
   // so... it's sorted now, so add the splits
  morePlease:
   curX++;
   for (int y = 0; y < map.w; y++)
   {
    if (y == map.w - 1)
    {
     if (tis[y] == -2)
      map[y,curX] = vnode.noVN;
     else
      map[y,curX] = vnode.flatVN;
    }
    else
    {
     int prev = tis[y];
     int cur = tis[y + 1];
     int next = tis[y + 2];

     if (cur != -2 && prev == cur && cur != next)
     { // split
      map[y,curX] = vnode.noVN;
      map[y+1,curX] = vnode.splitDownVN;
      tis[y + 1] = -2;
      y++; // skip
     }
     else
     {
      if (prev == -2)
       map[y,curX] = vnode.noVN;
      else
       map[y,curX] = vnode.flatVN;
     }
    }
   }

   // check if collapsed
   for (int y = 0; y < map.w - 1; y++)
   {
    int prev = tis[y];
    int cur = tis[y + 1];

    if (cur != -2 && prev == cur)
     goto morePlease;
   }

   // ok... now we put in the Is and 1
   curX++;
   map[0, curX] = vnode.oneVN;
   int eyeCount = 0;
   int ly = 0;
   for (int y = 0; y < map.w; y++)
   {
    if (tis[y] > -1)
    {
     map[y, curX] = vnode.inputVN;
     eyeCount++;
     ly = y;
    }
   }

   // step three - clean up if we can
   // push back _  esq things to  _
   //           _/               /
   // this /shouldn't/ be necessary if I compact the vals properlu
   for (int y = 0; y < map.w - 1; y++)
   {
    for (int x = 1; x < map.h; x++)
    {
     if (map[y, x] != null && map[y+1, x] != null && map[y+1, x-1] != null)
     {
      char uc = map[y+1, x-1].c;
      if (map[y, x].c == '_' && map[y+1, x].c == '_'
          && (uc == 'U' || uc == 'u'))
      {
       map[y, x] = vnode.noVN;
       map[y, x-1] = vnode.flatVN;
       map[y+1, x] = map[y+1, x-1];
       map[y+1, x-1] = vnode.noVN;
      }
     }
    }
   }

   // step four - write out map
   writer.WriteLine(map.h + " " + map.w);

   for (int y = 0; y < map.w; y++)
   {
    for (int x = map.h - 1; x >= 0; x--)
    {
     vnode vn = map[y,x];
     if (vn != null)
      writer.Write(vn.c);
     else
      writer.Write(' ');
    }
    writer.WriteLine();
   }
  }

  // printer
  static string up1 = @"      /     /     /     /";
  static string input = @"                    |||||";
  static string output = @"                    |    ";
  static string flat = @"            |/  \  /|\   ";
  static string splitDown = @"|//   / /\  |\/    /     ";
  static string splitUp = @"         \  |/\ \ \/|\\  ";
  static string moveDown = @"|//     /     /    /     ";
  static string moveUp = @"         \    \   \ |\\  ";
  static string swap = @"|/  |  /\   /\   \/ |\  |";
  static string orDown = @"|/    /     |/  \  /|\   ";
  static string orUp = @"|/    /  \  |\  \   |\   ";
  static string ifnotDown = @"|/     /     -   \/ |\  |";
  static string ifnotUp = @"|/  |  /\    -   \  |\   ";

  public static void printDominoes(System.IO.TextReader reader, System.IO.TextWriter writer, bool moreverbosemaybe)
  {
   string line;
   string[] data;

   line = reader.ReadLine();
   data = line.Split(' ');
   int w = int.Parse(data[0]);
   int h = int.Parse(data[1]);

   int ox = 0;
   int oy = 0;
   int cx = 5;
   int cy = 5;

   char[,] T = new char[ox + w * cx, oy + h * (cy - 1) + 1];

   Action<int, int, string> setBlock = (int x, int y, string str) =>
   {
    for (int i = 0; i < cx; i++)
    {
     for (int j = 0; j < cy; j++)
     {
      char c = str[i + j * cx];
      if (c != ' ')
       T[ox + x * cx + i, oy + y * (cy - 1) + j] = c;
     }
    }
   };

   // read and write
   for (int j = 0; j < h; j++)
   {
    line = reader.ReadLine();
    for (int i = 0; i < w; i++)
    {
     if (line[i] != ' ')
     {
      switch (line[i])
      {
       case '1':
        setBlock(i, j, up1);
        break;
       case '_':
        setBlock(i, j, flat);
        break;
       case '^':
        setBlock(i, j, splitUp);
        break;
       case 'v':
        setBlock(i, j, splitDown);
        break;
       case '/':
        setBlock(i, j, moveUp);
        break;
       case '\\':
        setBlock(i, j, moveDown);
        break;
       case 'X':
        setBlock(i, j, swap);
        break;
       case 'U':
        setBlock(i, j, orUp);
        break;
       case 'D':
        setBlock(i, j, orDown);
        break;
       case 'u':
        setBlock(i, j, ifnotUp);
        break;
       case 'd':
        setBlock(i, j, ifnotDown);
        break;
       case 'I':
        setBlock(i, j, input);
        break;
       case 'O':
        setBlock(i, j, output);
        break;
      }
     }
    }
   }

   // end
   for (int i = 0; i < T.GetLength(0); i++)
   {
    T[i, 0] = '/';
   }

   // writeout
   w = T.GetLength(0) - cx + 1;
   h = T.GetLength(1);
   if (moreverbosemaybe)
    writer.Write(w + " " + h + " ");
   for (int j = 0; j < T.GetLength(1); j++)
   {
    for (int i = 0; i < T.GetLength(0) - cx + 1; i++)
    {
     char c = T[i, j];
     writer.Write(c == 0 ? ' ' : c);
    }
    if (!moreverbosemaybe)
     writer.WriteLine();
   }
  }
 }
}

```

An additional test case:

```
4 1 0,0,0,1,0,0,1,1,0,0,0,1,1,1,1,1

```

This checks whether two adjacent (non-wrapping) bits are both 1s (e.g. true for 0110, but false for 0101 and 1001)

---
Tags: code-challenge, optimization, logic-gates, dominoes
---


title: Codegolf: Quine and Antiquine

text:
# Question
Title: Codegolf: Quine and Antiquine
This challenge is similar to Can you Meta Quine?

A quine is a program that produces itself on STDOUT. This challenge is to produce a program A which when run produces a program B on STDOUT. Program B when run produces program A on STDOUT. Programs A and B must be written in (and run in) the same language. The linked question constrained A != B. That looked too easy. So for this question, we insist A and B are antiquines, using the following rules:

1. Programs A and B may not use any of the same characters, save for whitespace and statement separators, and punctuation characters.
2. Programs A and B must each contain at least one character that is neither whitespace nor a statement separator, nor a punctuation character.
3. For the purpose of rules 1 and 2, the term 'whitespace' excludes any symbol or sequence of symbols which itself is a statement, operator or symbol that is interpreted (as opposed to a separator). Therefore in the Whitespace language, there is no whitespace.
4. A statement separator is a syntactic element conventionally used within the language to separate statements. This would include the newline in python, or the semicolon in Java, perl or C.
5. A punctuation character is an ASCII character which is neither whitespace nor in the POSIX word character class (i.e. an underscore is not punctuation for this purpose) - i.e `ispunct()` would return true, and it's not `_`.
6. Program A when run must produce a program (Program B) on its STDOUT, which when run in turn produces Program A.
7. Programs A and B must be in the same programming language.
8. The programming language used must actually be a programming language. Unless you make a good case otherwise, I'll suggest it must be Turing complete.
9. At least one of A and B must execute at least one statement within the language.

This is code golf, so the shortest answer wins, the score being the length of program A in bytes (i.e. the length of program B is not relevant).

# Answer
> 5 votes
# GolfScript, 13 bytes

```
1{\~\".~"}.~

```

The output is

```
-2{\~\".~"}.~

```

which generates the initial program.

The byte count include the trailing LF, since the output of the output will contain it.

Try it online.

### How it works

```
1       # Push 1.
{       # Start code block.
  \~\   # Apply logical NOT to the second topmost element of the stack.
  ".~"  # Push that string.
}       # End code block.
.~      # Duplicate the code block and execute the copy.

```

GolfScript prints the stack's contents upon termination.

# Answer
> 14 votes
## Pascal (731 characters)

Program A:

```
program s;{$h+}uses sysutils;const p='program s;{$h+}uses sysutils;const p=';a='a';aa=''';';aaa='a=''';aaaa='''';aaaaa='begin write(lowercase(p+aaaa+p+aa+aaa+a+aa+a+aaa+aaaa+aa+aa+a+a+aaa+aaa+aaaa+aa+a+a+a+aaa+aaaa+aaaa+aa+a+a+a+a+aaa+stringreplace(stringreplace(stringreplace(stringreplace(aaaaa,aaaa,aaaa+aaaa,[rfreplaceall]),''lower''+''c'',''tm''+''p'',[]),''up''+''c'',''lower''+''c'',[]),''tm''+''p'',''up''+''c'',[])+aa+aaaaa))end.';begin write(upcase(p+aaaa+p+aa+aaa+a+aa+a+aaa+aaaa+aa+aa+a+a+aaa+aaa+aaaa+aa+a+a+a+aaa+aaaa+aaaa+aa+a+a+a+a+aaa+stringreplace(stringreplace(stringreplace(stringreplace(aaaaa,aaaa,aaaa+aaaa,[rfreplaceall]),'lower'+'c','tm'+'p',[]),'up'+'c','lower'+'c',[]),'tm'+'p','up'+'c',[])+aa+aaaaa))end.

```

Outputs program B:

```
PROGRAM S;{$H+}USES SYSUTILS;CONST P='PROGRAM S;{$H+}USES SYSUTILS;CONST P=';A='A';AA=''';';AAA='A=''';AAAA='''';AAAAA='BEGIN WRITE(UPCASE(P+AAAA+P+AA+AAA+A+AA+A+AAA+AAAA+AA+AA+A+A+AAA+AAA+AAAA+AA+A+A+A+AAA+AAAA+AAAA+AA+A+A+A+A+AAA+STRINGREPLACE(STRINGREPLACE(STRINGREPLACE(STRINGREPLACE(AAAAA,AAAA,AAAA+AAAA,[RFREPLACEALL]),''LOWER''+''C'',''TM''+''P'',[]),''UP''+''C'',''LOWER''+''C'',[]),''TM''+''P'',''UP''+''C'',[])+AA+AAAAA))END.';BEGIN WRITE(LOWERCASE(P+AAAA+P+AA+AAA+A+AA+A+AAA+AAAA+AA+AA+A+A+AAA+AAA+AAAA+AA+A+A+A+AAA+AAAA+AAAA+AA+A+A+A+A+AAA+STRINGREPLACE(STRINGREPLACE(STRINGREPLACE(STRINGREPLACE(AAAAA,AAAA,AAAA+AAAA,[RFREPLACEALL]),'LOWER'+'C','TM'+'P',[]),'UP'+'C','LOWER'+'C',[]),'TM'+'P','UP'+'C',[])+AA+AAAAA))END.

```

Outputs program A.

# Answer
> 13 votes
# ROT13 (*not competing anymore after rule update*)

Not sure if this counts as a language, but I certainly didn't make it up for the challenge. Usually answers for certain utilities such as `sed` are accepted as well. However, it's a judgement call, so if it doesn't count I'll remove it (is there a meta discussion somewhere on what counts as a language? Edit: There is now)

```
A

```

Cycles between `A` and `N`:

```
~>> echo "A" | rot13
N
~>> echo "A" | rot13 | rot13
A

```

---
Tags: code-golf, quine
---