title: Worst Case Manhattan Exclusion

text:
# Question
Title: Worst Case Manhattan Exclusion
Imagine a ***W*** by ***H*** grid of squares that wraps toroidally. Items are placed onto the grid as follows.

The first item can be placed on any square, but subsequent items must not be within a Manhattan distance ***R*** of any previous item (also known as a Von Neumann neighbourhood of range ***R***). Carefully choosing the positions allows fitting a large number of items onto the grid before there are no more valid positions. However, instead consider the opposite aim: What is the lowest number of items that can be placed and leave no further valid positions?

Here is a radius 5 exclusion zone:

Here is another radius 5 exclusion zone, this time near the edges so the wrapping behaviour is apparent:

### Input

Three integers:

* ***W***: width of grid *(positive integer)*
* ***H***: height of grid *(positive integer)*
* ***R***: radius of exclusion zone *(non-negative integer)*

### Output

An integer ***N***, which is the smallest number of items that can be placed preventing any further valid placements.

### Details

* A radius of zero gives an exclusion zone of 1 square (the one the item was placed on).
* A radius of N excludes the zone that can be reached in N orthogonal steps (remember the edges wrap toroidally).

Your code must work for the trivial case of ***R*** = 0, but does not need to work for ***W*** = 0 or ***H*** = 0.

Your code must also deal with the case where ***R*** \> ***W*** or ***R*** \> ***H***.

# Time limit and test cases

Your code must be able to deal with all of the test cases, and each test case must complete within 5 minutes. This should be easy (the example JavaScript solution takes a few seconds for each test case). The time limit is mainly to exclude the extreme brute force approach. The example approach is still fairly brute force.

If your code completes within 5 minutes on one machine but not on another that will be close enough.

**Test cases** in the form inputs: output as `W H R : N`

```
5 4 4 : 1
5 4 3 : 2
5 4 2 : 2
5 4 1 : 5

7 5 5 : 1
7 5 4 : 2
7 5 3 : 2
7 5 2 : 4

8 8 8 : 1
8 8 7 : 2
8 8 6 : 2
8 8 5 : 2
8 8 4 : 2
8 8 3 : 4

 7  6  4 : 2
 7  6  2 : 4
11  7  4 : 3
11  9  4 : 4
13 13  6 : 3
11 11  5 : 3
15 14  7 : 2
16 16  8 : 2

```

# Snippet to help visualise and play around with ideas

```
canvas = document.getElementById('gridCanvas');ctx = canvas.getContext('2d');widthSelector = document.getElementById('width');heightSelector = document.getElementById('height');radiusSelector = document.getElementById('radius');itemCount = document.getElementById('itemCount');canvasMaxWidth = canvas.width;canvasMaxHeight = canvas.height;gridlineColour = '#888';emptyColour = '#ddd';itemColour = '#420';hoverCellColour = '#840';exclusionColour = '#d22';validColour = '#8f7';invalidColour = '#fbb';overlapColour = '#600';resetGrid();x = -1;y = -1;function resetGrid() {gridWidth = widthSelector.value;gridHeight = heightSelector.value;radius = radiusSelector.value;numberOfItems = 0;itemCount.value = numberOfItems + ' items placed.';cells = [gridWidth * gridHeight];for (i=0; i<gridWidth*gridHeight; i++) {cells[i] = '#ddd';}cellSize = Math.min(Math.floor(canvasMaxWidth/gridWidth), Math.floor(canvasMaxHeight/gridHeight));pixelWidth = gridWidth * cellSize + 1;canvas.width = pixelWidth;pixelHeight = gridHeight * cellSize + 1;canvas.height = pixelHeight;leaveCanvas();}function checkPosition(event) {bound = canvas.getBoundingClientRect();canvasX = event.clientX - bound.left;canvasY = event.clientY - bound.top;newX = Math.min(Math.floor(canvasX / cellSize), gridWidth-1);newY = Math.min(Math.floor(canvasY / cellSize), gridHeight-1);if (newX != x || newY != y) {x = newX;y = newY;drawGrid();}}function leaveCanvas() {x = -1;y = -1;drawGrid();}function drawGrid() {ctx.fillStyle = gridlineColour;ctx.fillRect(0, 0, pixelWidth, pixelHeight);cellColour = cells[x + gridWidth * y];if (cellColour == itemColour || cellColour == exclusionColour) {zoneColour = invalidColour;} else {zoneColour = validColour;}for (gridX=0; gridX<gridWidth; gridX++) {for (gridY=0; gridY<gridHeight; gridY++) {colour = (cells[gridX + gridWidth * gridY]);if (x >= 0 && y >= 0) {if (x == gridX && y == gridY) {colour = hoverCellColour;} else if (manhattanDistance(x, y, gridX, gridY) <= radius) {if (colour == exclusionColour) {colour = overlapColour;} else if (colour != itemColour) {colour = zoneColour;}}}ctx.fillStyle = colour;ctx.fillRect(gridX * cellSize + 1, gridY * cellSize + 1, cellSize - 1, cellSize - 1);}}}function manhattanDistance(a, b, c, d) {horizontal = Math.min(Math.abs((gridWidth + c - a) % gridWidth), Math.abs((gridWidth + a - c) % gridWidth));vertical = Math.min(Math.abs((gridHeight + d - b) % gridHeight), Math.abs((gridHeight + b - d) % gridHeight));return vertical + horizontal;}function placeItem(event) {bound = canvas.getBoundingClientRect();canvasX = event.clientX - bound.left;canvasY = event.clientY - bound.top;attemptX = Math.min(Math.floor(canvasX / cellSize), gridWidth-1);attemptY = Math.min(Math.floor(canvasY / cellSize), gridHeight-1);colour = cells[attemptX + gridWidth * attemptY];if (colour != itemColour && colour != exclusionColour) {for (a=0; a<gridWidth; a++) {for (b=0; b<gridHeight; b++) {if (manhattanDistance(a, b, attemptX, attemptY) <= radius) {cells[a + gridWidth * b] = exclusionColour;}}}cells[attemptX + gridWidth * attemptY] = itemColour;drawGrid();numberOfItems++;itemCount.value = numberOfItems + ' items placed.';}}
```

```
<canvas id='gridCanvas' width='500' height='300' style='border:none' onmousemove='checkPosition(event)' onmouseleave='leaveCanvas()' onclick='placeItem(event)'></canvas><br><textarea id='itemCount' readonly></textarea><br><button id='reset' onclick='resetGrid()'>Reset</button> with the following values:<br>Width:<input id='width' type='number' value='20' min='1' max='50' maxlength='2' step='1'><br>Height:<input id='height' type='number' value='13' min='1' max='30' maxlength='2' step='1'><br>Radius:<input id='radius' type='number' value='5' min='0' max='60' maxlength='2' step='1'>
```

# Example (ungolfed) solution

*Just an example for small outputs (resulting from radius not much smaller than the width and height). Can handle any of the test cases but will time out and give up for most larger cases.*

```
itemCount = document.getElementById('itemCount')
calculateButton = document.getElementById('calculate')
widthSelector = document.getElementById('width')
heightSelector = document.getElementById('height')
radiusSelector = document.getElementById('radius')

function calculate() {
    calculateButton.disabled = true
    widthSelector.disabled = true
    heightSelector.disabled = true
    radiusSelector.disabled = true
    itemCount.value = 'Calculating...'
    setTimeout(delayedCalculate, 100)
}

function delayedCalculate() {
    gridWidth = widthSelector.value
    gridHeight = heightSelector.value
    radius = radiusSelector.value
    startingMin = gridWidth*gridHeight + 1
    var cells = [gridWidth * gridHeight]
    for (i=0; i<gridWidth*gridHeight; i++) {
        cells[i] = 0
    }
    var gridState = gridWithItemAdded(cells, 0, 0)
    var minimum = minFromHere(gridState) + 1
    itemCount.value = 'Minimum ' + minimum + ' items required.'
    calculateButton.disabled = false
    widthSelector.disabled = false
    heightSelector.disabled = false
    radiusSelector.disabled = false
}

function minFromHere(gridState) {
    var x
    var y
    var newGridState
    var noCells = true
    var min = startingMin
    for (x=0; x<gridWidth; x++) {
        for (y=0; y<gridHeight; y++) {
            if (gridState[x + gridWidth * y] == 0) {
                noCells = false
                newGridState = gridWithItemAdded(gridState, x, y)
                m = minFromHere(newGridState)
                if (m < min) {
                    min = m
                }
            }
        }
    }
    if (noCells) return 0
    return min + 1
}

function gridWithItemAdded(gridState, x, y) {
    var a
    var b
    var grid = gridState.slice()
    for (a=0; a<gridWidth; a++) {
        for (b=0; b<gridHeight; b++) {
            if (manhattanDistance(a, b, x, y) <= radius) {
                grid[a + gridWidth * b] = 1
            }
        }
    }
    return grid
}

function manhattanDistance(a, b, c, d) {
    horizontal = Math.min(Math.abs((gridWidth + c - a) % gridWidth), Math.abs((gridWidth + a - c) % gridWidth))
    vertical = Math.min(Math.abs((gridHeight + d - b) % gridHeight), Math.abs((gridHeight + b - d) % gridHeight))
    return vertical + horizontal
}
```

```
<textarea id='itemCount' readonly></textarea>
<br>
<button id='calculate' onclick='calculate()'>Calculate</button> with the following values:
<br>
Width:<input id='width' type='number' value='5' min='1' max='50' maxlength='2' step='1'>
<br>
Height:<input id='height' type='number' value='4' min='1' max='30' maxlength='2' step='1'>
<br>
Radius:<input id='radius' type='number' value='1' min='0' max='60' maxlength='2' step='1'>
```

# Answer
# Python 2, ~~216~~ 182 bytes

```
def f(W,H,R):L={(i%W,i/W)for i in range(W*H)};M={(x,y)for x,y in L if min(x,W-x)+min(y,H-y)>R};g=lambda s:min([1+g(s-{((a+x)%W,(b+y)%H)for x,y in L-M})for a,b in s]or[1]);return g(M)

```

Input like `f(16,16,8)`. Uses pretty much the same algorithm as @trichoplax's sample, but with sets. Initially I didn't place the first item at `(0, 0)`, but this made it choke on the last few cases.

All cases above complete within 10 seconds, well under the limit. In fact, the cases are small enough that I had a little room to be less efficient, allowing me to remove a check which checked for duplicate states.

*(Thanks to @trichoplax for golfing help)*

**Expanded:**

```
def f(W,H,R):
  # All cells
  L={(i%W,i/W)for i in range(W*H)}

  # Mask: Complement of exclusion zone around (0, 0)
  M={(x,y)for x,y in L if min(x,W-x)+min(y,H-y)>R}

  # Place recursively
  g=lambda s:min([1+g(s-{((a+x)%W,(b+y)%H)for x,y in L-M})for a,b in s]or[1])
  return g(M)

```
> 5 votes

# Answer
# Python 3, ~~270~~ ~~262~~ ~~260~~ ~~251~~ ~~246~~ 226

*(Thanks to Sp3000 for:*

* `-~` *instead of* `+1`, *which lets me lose a space after* `return` *on the last line.*
* *losing superfluous parentheses around* `W*H`.
* *lambdas...*
* *putting everything on one line.*
* *python modulo `%` gives positive result for negative numbers, to save another 20 bytes)*

This is the JavaScript example answer from the question ported into Python 3.

To avoid having to pass so many function arguments around, I've moved the two supporting functions inside the calculate function so that they share its scope. I've also condensed each of these functions into a single line to avoid the cost of indentation.

### Explanation

This fairly brute force approach places the first item at (0, 0), and then marks all the excluded squares. It then recursively places an item at all remaining valid squares until all squares are excluded, and returns the minimum number of items required.

### Golfed code:

```
def C(W,H,R):r=range;M=lambda g:min([M(G(g,x,y))for x in r(W)for y in r(H)if g[x+W*y]]or[-1])+1;G=lambda g,x,y:[g[a+W*b]if min((x-a)%W,(a-x)%W)+min((y-b)%H,(b-y)%H)>R else 0for b in r(H)for a in r(W)];return-~M(G([1]*W*H,0,0))

```

### Ungolfed code:

```
def calculate(W, H, R):
    starting_min = W * H + 1
    cells = [0] * (W * H)
    grid_state = grid_with_item_added(cells, 0, 0, W, H, R)
    return min_from_here(grid_state, starting_min, W, H, R) + 1

def min_from_here(grid_state, starting_min, W, H, R):
    no_cells = True
    min = starting_min
    for x in range(W):
        for y in range(H):
            if grid_state[x + W * y] == 0:
                no_cells = False
                new_grid_state = grid_with_item_added(grid_state, x, y, W, H, R)
                m = min_from_here(new_grid_state, starting_min, W, H, R)
                if m < min:
                    min = m

    if no_cells:
        return 0
    else:
        return min + 1

def grid_with_item_added(grid_state, x, y, W, H, R):
    grid = grid_state[:]
    for a in range(W):
        for b in range(H):
            if manhattan_distance(a, b, x, y, W, H) <= R:
                grid[a + W * b] = 1

    return grid

def manhattan_distance(a, b, c, d, W, H):
    horizontal = min(abs(W + c - a) % W, abs(W + a - c) % W)
    vertical = min(abs(H + d - b) % H, abs(H + b - d) % H)
    return horizontal + vertical

if __name__ == '__main__':
    import sys
    arguments = sys.argv[1:]
    if len(arguments) < 3:
        print('3 arguments required: width, height and radius')
    else:
        print(calculate(int(arguments[0]), int(arguments[1]), int(arguments[2])))

```

The ungolfed code defines a function and also includes code to allow it to be called from the command line. The golfed code just defines the function, which is sufficient for standard code golf questions.

If you would like to test the golfed code from the command line, here it is with the command line handling included (but not golfed):

### Command line testable golfed code

```
def C(W,H,R):r=range;M=lambda g:min([M(G(g,x,y))for x in r(W)for y in r(H)if g[x+W*y]]or[-1])+1;G=lambda g,x,y:[g[a+W*b]if min((x-a)%W,(a-x)%W)+min((y-b)%H,(b-y)%H)>R else 0for b in r(H)for a in r(W)];return-~M(G([1]*W*H,0,0))

if __name__ == '__main__':
    import sys
    arguments = sys.argv[1:]
    if len(arguments) < 3:
        print('3 arguments required: width, height and radius')
    else:
        print(C(int(arguments[0]), int(arguments[1]), int(arguments[2])))

```
> 2 votes

---
Tags: code-golf, geometry, grid, packing
---


title: Bitstring Physics

text:
# Question
Title: Bitstring Physics
# Background

Yes, bitstring physics is a real thing. The idea is to construct a new theory of physics using only strings of bits that evolve under a probabilistic rule... or something. Despite reading a couple of papers about it, I'm still pretty confused. However, the bitstring universe makes for a nice little code golf.

# Program Universe

Bitstring physics takes place in a so-called *program universe*. At each step of the evolution of the universe, there is a finite list `L` of bitstrings of some length `k`, starting with the two-element list `[10,11]` where `k = 2`. One timestep is processed as follows (in Python-like pseudocode).

```
A := random element of L
B := random element of L
if A == B:
    for each C in L:
        append a random bit to C
else:
    append the bitwise XOR of A and B to L

```

All random choices are uniformly random and independent of each other.

# Example

An example evolution of 4 steps might look like the following. Start with the initial list `L`:

```
10
11

```

We randomly choose `A := 10` and `B := 10`, which are the same row, which means we need to extend each string in `L` with a random bit:

```
101
110

```

Next, we choose `A := 101` and `B := 110`, and since they are not equal, we add their XOR to `L`:

```
101
110
011

```

Then, we choose `A := 011` and `B := 110`, and again append their XOR:

```
101
110
011
101

```

Finally, we choose `A := 101` (last row) and `B := 101` (first row), which are equal, so we extend with random bits:

```
1010
1100
0111
1010

```

# The Task

Your task is to take a nonnegative integer `t` as input, simulate the program universe for `t` timesteps, and return or print the resulting list `L`. Note that `t = 0` results in the initial list `[10,11]`. You can output `L` as a list of lists of integers, list of lists of boolean values or a list of strings; if output goes to STDOUT, you may also print the bitstrings one per line in some reasonable format. The order of the bitstrings is significant; in particular, the initial list cannot be `[11,10]`, `[01,11]` or anything like that. Both functions and full programs are acceptable, standard loopholes are disallowed, and the lowest byte count wins.

# Answer
> 7 votes
# Pyth, ~~27~~ 26 bytes

```
u?+RO2GqFKmOG2aGxVFKQ*]1U2

```

Try it online: Demonstration

### Explanation:

```
                              implicit: Q = input number
                     *]1U2    the initial list [[1,0], [1,1]]
u                   Q         reduce, apply the following expression Q times to G = ^
          mOG2                  take two random elements of G
         K                      store in K
       qF                       check if they are equal
 ?                              if they are equal:
  +RO2G                           append randomly a 0 or 1 to each element of G
                                else:
              aG                  append to G
                xVFK              the xor of the elements in K

```

# Answer
> 11 votes
# CJam, ~~42~~ ~~40~~ ~~38~~ 37 bytes

*1 byte saved by Sp3000.*

```
B2b2/q~{:L_]:mR_~#L@~.^a+L{2mr+}%?}*p

```

## Explanation

Create the initial state as a base-2 number:

```
B2b e# Push the the binary representation of 11: [1 0 1 1]
2/  e# Split into chunks of 2 to get [[1 0] [1 1]]

```

And then perform the main loop and pretty-print the result at the end:

```
q~       e# Read and eval input t.
{        e# Run this block t times.
  :L     e#   Store the current universe in L.
  _]     e#   Copy it and wrap both copies in an array.
  :mR    e#   Pick a random element from each copy.
  _~     e#   Duplicate those two elements, and unwrap them.
  #      e#   Find the second element in the first. If they are equal, it will be found at
         e#   index 0, being falsy. If they are unequal, it will not be found, giving
         e#   -1, which is truthy.

         e#   We'll now compute both possible universes for the next step and then select
         e#   the right one based on this index. First, we'll build the one where they were
         e#   not equal.

  L@~    e#   Push L, pull up the other copy of the selected elements and unwrap it.
  .^     e#   Take the bitwise XOR.
  a+     e#   Append this element to L.

  L      e#   Push L again.
  {      e#   Map this block onto the elements in L.
    2mr+ e#     Append 0 or 1 at random.
  }%
  ?      e#   Select the correct follow-up universe.
}*
p        e# Pretty-print the final universe.

```

Test it here.

# Answer
> 6 votes
# Julia, ~~141~~ 129 bytes

```
t->(L=Any[[1,0],[1,1]];for i=1:t r=1:length(L);A=L[rand(r)];B=L[rand(r)];A==B?for j=r L[j]=[L[j],rand(0:1)]end:push!(L,A$B)end;L)

```

Nothing clever. Creates an unnamed function that accepts an integer as input and returns an array of arrays. To call it, give it a name, e.g. `f=t->...`.

Ungolfed + explanation:

```
function f(t)
    # Start with L0
    L = Any[[1,0], [1,1]]

    # Repeat for t steps
    for i = 1:t
        # Store the range of the indices of L
        r = 1:length(L)

        # Select 2 random elements
        A = L[rand(r)]
        B = L[rand(r)]

        if A == B
            # Append a random bit to each element of L
            for j = r
                L[j] = [L[j], rand(0:1)]
            end
        else
            # Append the XOR of A and B to L
            push!(L, A $ B)
        end
    end

    # Return the updated list
    L
end

```

Examples:

```
julia> f(4)
4-element Array{Any,1}:
 [1,0,1,0]
 [1,1,1,1]
 [0,1,1,0]
 [0,1,0,0]

julia> f(3)
3-element Array{Any,1}:
 [1,0,1,1]
 [1,1,1,0]
 [0,1,0,1]

```

Saved 12 bytes thanks to M L!

# Answer
> 4 votes
# Python 2, 141

I tried a few different methods, but the best I could get was relatively straightforward. Thanks to @Sp3000 for 15 chars or so (and for teaching me about the existence of `int.__xor__`).

```
from random import*
L=[[1,0],[1,1]];C=choice
exec"A=C(L);B=C(L);L=[L+[map(int.__xor__,A,B)],[x+[C([1,0])]for x in L]][A==B];"*input()
print L

```

# Answer
> 3 votes
# Pyth, 34

```
u?+RO`TGqJOGKOG+Gsm`s!dqVJKQ[`T`11

```

Uses reduce to apply each iteration. I'll explain when I'm done golfing.

Try it here

# Answer
> 2 votes
# K, 46 53 46 bytes

```
{x{:[~/t:2?x;{x,*1?2}'x;x,,,/~=/t]}/(1 0;1 1)}

```

A good chunk of the size (about 7 bytes) of this is do to the fact that K has no `xor` operator, so I had to implement one myself. Originally, I used a list of strings, followed by realizing that was insanely stupid. So now I cut off the 7 bytes again!

Before:

```
{x{:[~/t:2?x;{x,*$1?2}'x;x,,,/$~=/(0$')'t]}/$:'10 11}

```

@JohnE pointed out in the comments that the initial state was supposed to be hardcoded, which cost 7 extra bytes. :/

# Answer
> 2 votes
# JavaScript (*ES6*) 152

A function, using strings (with numbers it should be shorter, but in javascript bit operations are limited to 32 bit integers).

Test in Firefox using the snippet below.

```
F=(t,L=['10','11'],l=2,R=n=>Math.random()*n|0,a=L[R(l)],b=L[R(l)])=>
   t--?a==b
     ?F(t,L.map(x=>x+R(2)),l)
     :F(t,L,L.push([...a].map((x,p)=>x^b[p]).join('')))
  :L

test=_=>O.innerHTML=F(+I.value).join('\n')
```

```
#I{width:3em}
```

```
<input id=I value=10><button onclick=test()>-></button><pre id=O></pre>
```

# Answer
> 1 votes
# Javascript, ~~241~~ 233 bytes

That's kind of long.

```
a=[[1,0],[1,1]];for(b=prompt();b--;)if(c=a.length,d=a[c*Math.random()|0],e=a[c*Math.random()|0],d+""==e+"")for(f=0;f<c;f++)a[f].push(2*Math.random()|0);else{g=[];for(h=0;h<d.length;h++)g.push(d[h]^e[h]);a.push(g)}alert(a.join("\n"));

```

# Answer
> 1 votes
# K, ~~45~~ ~~41~~ 38 bytes

```
{x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}

```

The structure of my answer is quite similar to that of @kirbyfan64sos, but instead of strings I used 1/0 vectors and I avoid the need for a conditional (`:[ ; ; ]`) by instead indexing into a list.

A few runs:

```
  {x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}3
(1 0 0 0
 1 1 1 1
 0 1 1 1)

  {x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}3
(1 0 0
 1 1 0
 0 1 0
 1 0 0)

  {x{(x,,~=/t;{x,1?2}'x)@~/t:2?x}/1,'!2}3
(1 0 0
 1 1 0
 0 1 0
 1 1 0)

```

## Edit:

Saved four bytes with a more compact way to build the initial universe:

```
1,'!2     / new
(1 0;1 1) / old

```

## Edit2:

I forgot that "choose" can take a list as its right argument:

```
  2?"abcd"
"dc"
  2?"abcd"
"cc"
  2?"abcd"
"ca"

```

So I can simplify part of this. Credit where it's due, Kirby got this trick before I did.

```
2?x    / new
x@2?#x / old

```

# Answer
> 1 votes
# T-SQL (2012+), 1019

I'm really sorry this is nowhere near competitive, but to be honest I didn't think I could get this to work and had to post it once I did. I did try to golf it a bit :)

To handle the binary/integer conversions I had to create a couple of scalar functions (513 of the bytes). `A` goes from integer to a bit string. `B` does the reverse.

```
CREATE FUNCTION A(@ BIGINT)RETURNS VARCHAR(MAX)AS
BEGIN
DECLARE @S VARCHAR(MAX);
WITH R AS(SELECT @/2D,CAST(@%2 AS VARCHAR(MAX))M
UNION ALL
SELECT D/2,CAST(D%2 AS VARCHAR(MAX))+M
FROM R
WHERE D>0)SELECT @S=M FROM R WHERE D=0
RETURN @S
END
CREATE FUNCTION B(@ VARCHAR(MAX))RETURNS BIGINT AS
BEGIN
DECLARE @I BIGINT;
WITH R AS(SELECT CAST(RIGHT(@,1)AS BIGINT)I,1N,LEFT(@,LEN(@)-1)S
UNION ALL
SELECT CAST(RIGHT(S,1)AS BIGINT)*POWER(2,N),N+1,LEFT(S,LEN(S)-1)
FROM R
WHERE S<>''
)SELECT @I=SUM(I)FROM R
RETURN @I
END

```

Then there is the procedure. `@C` is the number of steps

```
DECLARE @C INT=9
DECLARE @ TABLE(S VARCHAR(MAX))
DECLARE @R VARCHAR(MAX)
INSERT @ VALUES('10'),('11')
WHILE(@C>=0)
BEGIN
SET @C-=1
SELECT @R=CASE WHEN MAX(S)=MIN(S)THEN''ELSE RIGHT(REPLICATE('0',99)+dbo.A(dbo.B(MAX(S))^dbo.B(MIN(S))),LEN(MAX(S)))END
FROM(SELECT TOP 2S,ROW_NUMBER()OVER(ORDER BY(SELECT\))N FROM @,(VALUES(1),(1),(1))D(D)ORDER BY RAND(CAST(NEWID()AS VARBINARY(50))))A
IF @R=''UPDATE @ SET S=CONCAT(S,ROUND(RAND(CAST(NEWID() AS VARBINARY(50))),0))
ELSE INSERT @ VALUES(@R)
END
SELECT * FROM @

```

Ten thousand iterations took around 2 minutes and returned 9991 rows

```
1001001100110
1101001001110
0111100100101
1111100001011
1111001010011
0110101001101
...
1110101000100
1111011101100
1100001100010
0110010001001
1110100010100

```

# Answer
> 0 votes
# Pyth - 37 bytes

Obvious, just follows psuedocode. Probably can golf a lot.

```
KPP^,1Z2VQ=K?m+dO1KqFJ,OKOKaKxVhJeJ;K

```

Try it here online.

# Answer
> 0 votes
# Mathematica, 106 bytes

```
Nest[If[Equal@@#,Map[#~Append~RandomInteger[]&],Append[BitXor@@#]]&[#~RandomChoice~2]@#&,{{1,0},{1,1}},#]&

```

# Answer
> 0 votes
# Perl, 102

```
#!perl -p
@l=qw(10 11);$_=$l[rand@l]^$l[rand@l],$_|=y//0/cr,@l=/1/?(@l,$_):map{$_.~~rand 2}@l for 1..$_;$_="@l"

```

Try me.

# Answer
> 0 votes
## R, 186

```
L=list(0:1,c(1,1))
if(t>0)for(t in 1:t){A=sample(L,1)[[1]]
B=sample(L,1)[[1]]
if(all(A==B)){L=lapply(L,append,sample(0:1, 1))}else{L=c(L,list(as.numeric(xor(A,B))))}}
L

```

Nothing magical here. Enter the value for `t` in the R console and run the script. It's hard to "golf" R code but here's a more readable version:

```
L <- list(0:1, c(1, 1))
if(t > 0) {
  for(t in 1:t) {
    A <- sample(L, 1)[[1]]
    B <- sample(L, 1)[[1]]
    if (all(A == B)) {
      L <- lapply(L, append, sample(0:1, 1))
    } else {
      L <- c(L,list(as.numeric(xor(A, B))))
    }
  }
}
L

```

# Answer
> 0 votes
# Ruby, 82

Pretty much straight-forward. Compared with other non-golfing languages, ruby seems to do well with its large standard library.

```
->t{l=[2,3]
t.times{a,b=l.sample 2
a.equal?(b)?l.map!{|x|x*2+rand(2)}:l<<(a^b)}
l}

```

Sample output for t=101010 :

```
[9, 15, 6, 13, 5, 12, 10, 11, 5, 4, 15, 13, 2, 7, 11, 9, 3, 3, 8, 6, 3, 13, 13, 12, 10, 9, 2, 4, 14, 9, 9, 14, 15, 7, 10, 4, 10, 14, 13, 7, 15, 7]

```

---
Tags: code-golf, array, random
---


title: King of the Hill - Liar's Dice

text:
# Question
Title: King of the Hill - Liar's Dice
**Liar's Dice** is a fairly simple dice game. I've seen a few different variations of the rules, but here is the version I'm most familiar with:

* Each player starts with 5d6
* Except when tallying the dice at the end of a round, each player may see their own dice, but not those of any opponent
* At the start of any given round, all players roll whatever dice they currently have
* Then, one player (usually, this is either the winner of the previous round OR the player to the left of the player who started last time; we'll be using the former for this KotH; with a random player starting the first round) makes a guess about how many of a particular number are on the table **(ONES ARE WILD)**
* Bidding continues to the right, going higher each time (for instance; 3 fives, 3 sixes and 4 twos are all higher than 3 fours, but 3 threes is not; 4 ones is also higher but bidding on ones will probably put you at a disadvantage); until any player calls the player preceding them a liar
* At this point, all players reveal their dice and count the number of the last number bid on on the table altogether
* If the total is lower than the bid, the player who made the bid must give a die to the player who called them a liar, otherwise, the player who called the bidder a liar must give a die to the bidder (so the bidder wins if their are *at least* as many of that number as he had bid, there don't have to be the exact number)
* When you run out of dice, you lose
* The last player standing wins

For example:

```
Player one has 1,1,2,4,6
Player two has 1,2,2,3,5
Player three has 1,3,3,4,6
Player one: three sixes.
Player two: four twos.
Player three: four threes.
Player one: five twos.
Player two: six twos.
Player three: six threes.
Player one: six fours.
Player two: Liar!
They reveal their dice and count up the ones (because ones are wild) and the fours.
It turns out that there are, in fact, exactly six fours.
So player two gives player one a die.
They reroll and player one starts the next round.

```

You must write a bot to play this game. It must implement the following abstract java class:

```
public abstract class Player {
    public Player() {}
    public String toString() {
        return this.getClass().getSimpleName();
    }
    public abstract String bid(int yourId, int[] diceEachPlayerHas, int[] yourDice, String[] bids);
}

```
* You must implement the bid method
    + The first argument is your bot's current position in the turn order, the second is an array showing how many dice each player (including yourself) currently has, the third is an array showing the values currently shown on your own dice, and the fourth is an array of all bids made since the start of the current round - will have length 0 if you are making the first bid of the round
    + The output should be either a string of the form "number face", or the string "Liar!" to call the previous bidder a liar.
    + If your output is formatted illegally, you will be eliminated.
* You may override the toString method, but are not required to. However, you may not edit it in any way that interferes with the readability of the controller's output.
* You are permitted to call any other public methods of the controller, but *not* its main method.
* You may read and edit only files in the running directory prefixed with your bot's own name
* You are not permitted to take input from any other source
* Instance variables are reset at the start of each new game, but static variables are not.

**Scoring**

* One set of 1,000 games, with 3-5 players in each, will be simulated each time a bot is added (as soon as three or more bots have been submitted), scored as shown in the controller source (in any given game, you get 1 at the start of each of your turns, 10 each time you capture a die, and 1,000 bonus if you win); enforcing a limit of 5,000 TURNS (not rounds) each game.
* Your bot will be scored by its score from the latest set of games; plus ten times its vote score, if nonnegative. (The latter is unlikely to have a significant effect on the score)

The controller source can be found here.

# Scores as of 2015-06-19:

```
Badnomial: 434,924 + 6x10 = 424,984
Nobody: 282,329 + 6x10 = 282,389
StraightShooter: 265,205 + 5x10 = 265,255
MostlyHonestAbe: 158,958 + 4x10 = 158,998
The Pirate: 157,005 + 1x10 = 157,015
Statistician: 144,012 + 2x10 = 144,032
Fidelio: 49,973 + 2x10 = 49,993
Absurd Bot: 6,831
DrHouse: 2,638 + 3x10 = 2,668

```

# Answer
# Nobody

Tries to guess the dice from other players. Calls other bots liars if it doesn't know what to do.

**Edit:** Fixed a problem where Nobody would bid forever, never calling Liar.

```
public class Nobody extends Player{

    @Override
    public String bid(int myId, int[] diceEachPlayerHas, int[] myDice,
            String[] bids) {
        if (bids.length == 0)
            return "1 2";
        int wilds = 0;
        int players = Controller.numPlayers();
        double myKnowledge = (double)diceEachPlayerHas[myId]/Controller.diceInPlay();
        double previousKnowledge = (double)diceEachPlayerHas[(myId-1+players)%players] / Controller.diceInPlay();
        int[] dice = new int[5];
        for (int i = 0; i < myDice.length; i++) {
            if (myDice[i] == 1) {
                wilds++;
            } else {
                dice[myDice[i]-2]++;
            }
        }
        wilds = (int) (1/myKnowledge+wilds-1)+1;
        for (int i = 2; i <= 6; i++) {
            dice[i-2] += wilds;
        }
        String best = "0 0";
        for (int i = 2; i <= 6; i++) {
            if (Controller.isGreaterThan(dice[i-2] + " " + i, best)) {
                best = dice[i-2] + " " + i;
            }
        }
        if (Controller.isGreaterThan(best, bids[bids.length - 1])) {
            return best;
        }
        if (previousKnowledge > 0.4) {
            int prev = Integer.valueOf(bids[bids.length - 1].split(" ")[0]);
            int prevFace = Integer.valueOf(bids[bids.length - 1].split(" ")[1]);
            if (dice[prevFace - 2] +2 >= prev)
                return (prev+1) + " " + bids[bids.length - 1].split(" ")[1];
        }
        return "Liar!";
    }
}

```
> 6 votes

# Answer
**Badnomial, the bot that makes bad decisions based on binomial distributions:** Edit: Fixed a stupid mistake in the probability calculations, now accounts for next Bidder as well as previous.

```
    public class Badnomial extends Player{
    public String toString() {return "Badnomial";}

  public String bid(int myId, int[] diceEachPlayerHas, int[] myDice, String[] bids) {
  int[] dieCounts = new int[7];
  for(int i:myDice)
   dieCounts[i]++;
  for(int i=2; i<7; i++)
   dieCounts[i] += dieCounts[1];

  if(bids.length > 0)
  {
   String[] lastBid = bids[bids.length - 1].split(" ");
   int bidCount = Integer.valueOf(lastBid[0]);
   int bidDie = Integer.valueOf(lastBid[1]);
   // Check if I hold a better bid
   boolean betterBid = false;
   int myBidDie;
   int myBidCount;
   int myHighestCount = 0;
   int myHighDie = bidDie +1;

   for(int i = 2; i < 7; i++) {
    if(dieCounts[i] >= myHighestCount) {
     myHighestCount = dieCounts[i];
     myHighDie = i;
    }
   }
    if((myHighestCount > bidCount) || ((myHighestCount == bidCount) && (myHighDie > bidDie))) {
     betterBid = true;
     myBidDie = myHighDie;
     myBidCount = myHighestCount;
     }

   if(betterBid == false) {
    int unknownDice = Controller.diceInPlay() - myDice.length;
    int myDiceNeeded = bidCount - myHighestCount;
 if(myHighDie <= bidDie)
  myDiceNeeded++;
    int previousBidder = myId - 1;
    if(previousBidder < 0)
     previousBidder = Controller.numPlayers() -1;
    int bidderDiceNeeded = bidCount - dieCounts[bidDie] - (int)(diceEachPlayerHas[previousBidder]/3 +1);
    int bidderUnknown = Controller.diceInPlay() - diceEachPlayerHas[previousBidder] -myDice.length;
 int nextBidder = myId + 1;
 if(nextBidder == Controller.numPlayers())
  nextBidder = 0;
 int nbDiceNeeded = myDiceNeeded - (int)(diceEachPlayerHas[nextBidder]/3 +1);
    int nbUnknown = Controller.diceInPlay() - diceEachPlayerHas[nextBidder];
    //float myChances = (unknownDice/3 - myDiceNeeded)/((float)unknownDice/9);
    //float bidderChances = (bidderUnknown/3 - bidderDiceNeeded)/((float)bidderUnknown/9);
    double myChances = 1 - cumBinomialProbability(unknownDice, myDiceNeeded -1);
    double bidderChances;
    if(bidderDiceNeeded > 0)
     bidderChances = 1- cumBinomialProbability(bidderUnknown, bidderDiceNeeded -1);
    else bidderChances = 1.0;
    double nbChances;
    if(nbDiceNeeded > 0)
      nbChances = 1- cumBinomialProbability(nbUnknown, nbDiceNeeded -1 );
    else nbChances = 1.0;
    if(((myChances < .5) && (nbChances <.5)) || (bidderChances < .2))
     return "Liar!";
   }

   return (bidCount+1) + " " + myHighDie;
  }

  return 2 + " " + 2;
 }

 private double cumBinomialProbability(int n, int k) {
   double sum = 0;
   for(int i = 0; i <=k; i++)
     sum += binomialProbability(n, i);
   return sum;
 }

 private double binomialProbability(int n, int k) {
   double nfact = 1;
   double dfact = 1;
   int greater;
   int lesser;
   if((n-k) > k) {
     greater = n - k;
     lesser = k;
   }
   else {
     greater = k;
     lesser = n-k;
   }
   for(int i = greater+1; i <= n; i++)
     nfact = nfact * i;
   for(int i = 2; i <= lesser; i++)
     dfact = dfact * i;
   return (nfact/dfact)*(Math.pow((1.0/3), k))*Math.pow(2.0/3, (n-k));
 }

}

```

It tries to determine whether it should bluff or call Liar based on estimated cumulative binomial distributions for itself and the previous and next bidders' chances of having their needed dice present.

Basically, it calls Liar if the previous Bidder is very likely to be a Liar or if it feels it that both it and the next Bidder are more likely lying than not.
> 6 votes

# Answer
# Straight Shooter

He plays it straight and doesn't bluff. He's also naive enough to think that others do, too, so he never calls liar unless the bid goes over the total number of dice in play (minus his own dice that don't match the bid).

To be a bit more conservative than the exact expected number for each die, he doesn't count his own wilds, but assumes others have a uniform distribution. With the current four players, either he or MostlyHonestAbe came up first each time, with fairly close scores.

I'm assuming the minimum bid is `2 2`. If a bid of one die (or bidding ones) is allowed, let me know so I can make that change.

```
public class StraightShooter extends Player{
    public String toString(){return "Straight Shooter";}
    public String bid(int me, int[] numDices, int[] dice, String[] bids){
        int[] counts = new int[7];
        double[] expected = new double[7];
        int unknown = Controller.diceInPlay() - dice.length;
        for(int i:dice)
            counts[i]++;
        for(int i=2;i<7;i++)
            expected[i] = counts[i] + unknown / 3d;
        int bidCount = 2;
        int bidDie = 2;
        if(bids.length > 0){
            String[] lastBid = bids[bids.length-1].split(" ");
            bidCount = Integer.valueOf(lastBid[0]);
            bidDie = Integer.valueOf(lastBid[1])+1;
            int possible = Controller.diceInPlay();
            for(int i=2;i<7;i++)
                if(i != bidDie)
                    possible -= counts[i];
            if(bidCount > possible)
                return "Liar!";

            if(bidDie > 6){
                bidDie = 2;
                bidCount++;
            }
        }
        double best = Double.MAX_VALUE;
        int bestCount = bidCount;
        int bestDie = bidDie;
        for(int count=bidCount;count<=Controller.diceInPlay();count++){
            for(int die=bidDie;die<7;die++){
                double score = Math.abs(expected[die]-bidCount);
                if(score < best){
                    best = score;
                    bestCount = count;
                    bestDie = die;
                }
            }
            bidDie = 2;
        }
        return bestCount + " " + bestDie;
    }
}

```
> 5 votes

# Answer
## MostlyHonestAbe

Abe makes conservative guesses about the rest of opponents die, and then then stays honest until he doesn't think there are enough dice to beat the current bid. At this point he bluffs once, then calls liar the next time.

```
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;

public class MostlyHonestAbe extends Player{

    final boolean debug = false;
    boolean bluffedOnce = false;
    PrintStream out;
    @Override
    public String bid(int myId, int[] diceEachPlayerHas, int[] myDice, String[] bids) {
        try {
            File f = new File("abe.log.txt");
            out = new PrintStream(f);
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            //e.printStackTrace();
        }
        if(debug){
            out = System.out;
        }

        //reset bluff counter on the first round
        if(bids.length < diceEachPlayerHas.length){
            bluffedOnce = false;
        }

        //Is it the first bid?
        if(bids.length == 0){
            out.println("I go first");
            return lowestViableBid(1,1, myDice, diceEachPlayerHas, true);
        }

        out.println("Last bid = " + bids[bids.length - 1]);
        out.print("My Dice = ");
        for(int d : myDice){
            out.print(d + ", ");
        }
        out.println();

        //What was the last bid?
        String[] lastBid = bids[bids.length -1].split(" ");
        return lowestViableBid(Integer.parseInt(lastBid[1]), Integer.parseInt(lastBid[0]), myDice, diceEachPlayerHas, false);

    }

    //Lowest honest bid, or liar
    private String lowestViableBid(int highestVal, int highestCount, int[] myDice, int[] otherDice, boolean firstTurn){

        //Make a better array for the dice
        //Include what the other players probably have
        int wilds = numDie(1, myDice);
        int[] diceCount = new int[6];
        diceCount[0] = wilds;
        int otherPlayerExpectedValue = 0;
        for(int d : otherDice){
            otherPlayerExpectedValue += d;
        }
        otherPlayerExpectedValue -= myDice.length;
        out.println("Number of other dice = " + otherPlayerExpectedValue);
        otherPlayerExpectedValue = otherPlayerExpectedValue / 4;
        //Note: Other player expected value is biased low, counting wilds the number should be divided by 3.

        out.println("playerExpectedVal = " + otherPlayerExpectedValue);
        for(int i = 1; i < 6; i++){
            diceCount[i] = numDie(i + 1, myDice) + wilds + otherPlayerExpectedValue;
        }

        //What's my array look like?
        for(int i = 0; i < diceCount.length; i++){
            out.println("diceVal = " + (i + 1) + ", diceCount = " + diceCount[i]);
        }

        //Can I bid the same number, but higher dice val?
        for(int diceVal = highestVal + 1; diceVal <= 6; diceVal++){
            if(diceCount[diceVal - 1] >= highestCount){
                out.println("1.Returning " + highestCount + " " + diceVal);
                return highestCount + " " + diceVal; }
        }

        //What about more dice?
        for(int diceNum = highestCount + 1; diceNum <= myDice.length; diceNum++){
            for(int diceVal = highestVal + 1; diceVal <= 6; diceVal++){
                if(diceCount[diceVal - 1] == diceNum){
                    out.println("2.Returning " + (diceNum) + " " + diceVal);
                    return (diceNum) + " " + diceVal; }
            }
        }

        if(firstTurn){ return "1 2"; }
        //If this is the first time I'm out of my league, bluff a round before calling liar.
        if(!bluffedOnce){
            out.println("bluffing " + (highestCount + 1) + " " + highestVal);
            bluffedOnce = true;
            return (highestCount + 1) + " " + highestVal;
        }
        out.println("Returning Liar!");
        //Well, wouldn't want to lie
        return "Liar!";
    }

    private int numDie(int i, int[] myDice){
        int result = 0;
        for(int j : myDice){
            if(i == j){ result++; }
        }
        return result;
    }
}

```
> 4 votes

# Answer
# Dr. House

Everybody Lies!

```
public class DrHouse extends Player
{
  public String bid(int yourId, int[] diceEachPlayerHas, int[] yourDice, String[] bids)
  {
    return "Liar!";
  }
}

```
> 4 votes

# Answer
# Statistician

You have 1/3 chance of having any number other than aces. One guy once tell me that not checking your dices and juste knowing the odds can make you win this game. EDIT : It was bidding too high. But it doesn't improve the score a lot.

```
public class Statistician extends Player{
    public String toString(){return "Statistician";}
    public String bid(int me, int[] numDices, int[] dice, String[] bids){
        int totalDices = 0;
        int currentBid, max;
        for (int i : numDices)
            totalDices += i;
        max = totalDices/3;
        if(bids.length>0){
            currentBid = Integer.valueOf(bids[bids.length-1].split(" ")[0]);
            if(currentBid>max)
                return "Liar!";
        }
        return max+" 6";
    }
}

```
> 2 votes

# Answer
# Fidelio

This bot know that only his most recurrent value will lead him to victory, so he stick with it. He assume there's a portion of everyone's dice that is the same as his, if anyone bid more than that portion, he assume he's a liar.

```
public class Fidelio extends Player
{
    final String LIAR ="Liar!";
    @Override
    public String bid(int yourId,
            int[] diceEachPlayerHas,
            int[] yourDice,
            String[] bids)
    {
        int[] myDices = new int[6];
        int valueToBid=1;
        for(int i : yourDice)
            myDices[i-1]++;
        for(int i=2;i<myDices.length;i++)
            if(myDices[i]>=myDices[valueToBid])
                valueToBid=i;
        if(bids.length==0)
            return 2+" "+valueToBid;
        int sum=0;
        String[] lastBidString=bids[bids.length-1].split(" ");
        int[] lastBid = new int[2];
        lastBid[0] = Integer.parseInt(lastBidString[0]);
        lastBid[1] = Integer.parseInt(lastBidString[1])-1;
        for(int i : diceEachPlayerHas)
            sum+=i;
        sum-=yourDice.length;
        if(lastBid[0]>sum/3+myDices[lastBid[1]]+myDices[0])
            return LIAR;
        if(lastBid[1]>= valueToBid)
        {
            if(lastBid[0]>=myDices[0]+myDices[valueToBid]+sum*2/5)
                return LIAR;
            return (lastBid[0]+1)+" "+myDices[valueToBid];
        }
        return lastBid[0]+" "+valueToBid;
    }
}

```

I hope he will do some good work :).
> 2 votes

# Answer
# The Pirate

I made a few simple bots while testing the controller, and this is the only one that's really any good.

Will likely be improved upon later.

```
import java.util.Arrays;
import java.util.Scanner;

public class Pirate extends Player{
    public Pirate() {
    }
    public String toString(){
        return "The Pirate";
    }
    private String bid(int[] t,int tol){
        int[]z=t.clone();
        Arrays.sort(z);
        int j=0;
        for(int i=0;i<6;i++){
            if(t[i]==z[5]){j=i;break ;}
        }
        return (tol+t[j])+" "+(j+1);
    }
    @Override
    public String bid(int yourId, int[] diceEachPlayerHas, int[] yourDice,
            String[] bids) {
        int[] t=new int[6];
        for(int i=0;i<yourDice.length;i++){
            t[yourDice[i]-1]++;
        }
        for(int i=1;i<t.length;i++)t[i]+=t[0];
        int tol=(Controller.diceInPlay()-yourDice.length)/4;
        if(bids.length==0)return bid(t,1);
        Scanner i=new Scanner(bids[bids.length-1]);
        int x=i.nextInt(),y=i.nextInt();
        i.close();
        if(t[y-1]>x)return (t[y-1]+2)+" "+y;
        int nd=Controller.diceInPlay();
        if(x>nd+t[y-1]-yourDice.length)return "Liar!";
        if(Controller.isGreaterThan(bid(t,tol), bids[bids.length-1])){
            int z=Controller.valueOf(bids[bids.length-1]);
            for(int j=1;j<=tol;j++)if(Controller.valueOf(bid(t,j))>z)return bid(t,j);
        }
        return "Liar!";
    }
}

```
> 1 votes

# Answer
# Absurd Bot

Makes the claim that all of the dice are 6's unless it can't. If the bot can't do that, it means that this is an impossible situation or nearly impossible situation. Because of this, it calls liar. I am curious as to how effective this bot will be.

```
public class AbsurdBot extends Player {
    @Override
    public String bid(int yourId, int[] diceEachPlayerHas,int[] yourDice,String[] bids)
    {
        String[] lastbid;
        int a, b, d;
        d = 0;
        for (int dice : diceEachPlayerHas)
            d += dice;
        if (bids.length != 0)
            {
                lastbid = bids[bids.length-1].split(" ");
                a = Integer.parseInt(lastbid[0]);
                b = Integer.parseInt(lastbid[1]);
                if (a > d || a == d && b == 6)
                    return "Liar!";
            }
        return d + " 6";
    }
}

```
> 1 votes

---
Tags: popularity-contest, king-of-the-hill, java
---


title: ASCII Triangle Ripple

text:
# Question
Title: ASCII Triangle Ripple
Ok, my first golf question. Please be gentle :) I know there's way too many ascii puzzles :P but here we go.

The task is simple, use your favorite programming language to print a triangle ripple. The input should be the size of the ripple.

Each triangle is evenly spaced out. Basically, you keep adding the triangles until there is not enough space for the smallest triangle.

You are allowed white spaces anywhere you want as long as the ripples are the same as the example with the correct size.

# Example

```
q)g 1
__
\/
q)g 2
____
\  /
 \/
q)g 3
______
\    /
 \  /
  \/
q)g 4
________
\  __  /
 \ \/ /
  \  /
   \/
q)g 5
__________
\  ____  /
 \ \  / /
  \ \/ /
   \  /
    \/
q)g 6
____________
\  ______  /
 \ \    / /
  \ \  / /
   \ \/ /
    \  /
     \/
q)g 7
______________
\  ________  /
 \ \  __  / /
  \ \ \/ / /
   \ \  / /
    \ \/ /
     \  /
      \/
q)g 8
________________
\  __________  /
 \ \  ____  / /
  \ \ \  / / /
   \ \ \/ / /
    \ \  / /
     \ \/ /
      \  /
       \/

```

As usual, shortest code wins :)

# Answer
> 5 votes
# Pyth, 31 bytes

```
VhQ+J<t+++*Nd*N"\ "d*Q\_Q_XJ"\/

```

Demonstration.

Explanation:

```
VhQ+J<t+++*Nd*N"\ "d*Q\_Q_XJ"\/
                                   Implicit: Q = eval(input()), d = ' '
VhQ                                for N in range(Q + 1):
                                   Concatenate:
          *Nd                      N spaces
         +   *N"\ "                N of the string "\ "
        +          d               another space
       +            *Q\_           Q of the string "_"
                                   If N = 2 and Q = 7, the string so far is:
                                   "  \ \  _______" and we want
                                   " \ \  _" as the left half.
      t                            Remove the first character.
     <                  Q          Take the first Q characters remaining.
                                   This is the left half of the triangle ripple.
    J                              Store it in J.
                          XJ"\/    Translate \ to / in J.
                         _         Reverse it.
   +                               Concatenate the left and right halves and print.

```

# Answer
> 7 votes
# GNU sed -nr, 210

A start:

```
s/1/__/g
p
s#_(.*)_#\\\1/#
s#\\__#\\  #
s#__/#  /#
ta
:a
p
s#(.*) _{6}(_*) # \1\\  \2  /#;ta
s#(.*)  (  )# \1\2#;
s#(.*) _(_*)_ # \1\\\2/#
y/_/ /
Tc
:b
p
:c
s#(.*)((\\)  ( *)(/)|()()()\\/)# \1\3\4\5#;tb

```

Input is a positive unary integer via STDIN, as per this meta-question.

### Output:

```
$ for i in 1 11 111 1111 11111 111111 1111111; do sed -rnf triripple.sed <<< $i; done
__
\/

____
\  /
 \/

______
\    /
 \  /
  \/

________
\  __  /
 \ \/ /
  \  /
   \/

__________
\  ____  /
 \ \  / /
  \ \/ /
   \  /
    \/

____________
\  ______  /
 \ \    / /
  \ \  / /
   \ \/ /
    \  /
     \/

______________
\  ________  /
 \ \  __  / /
  \ \ \/ / /
   \ \  / /
    \ \/ /
     \  /
      \/

$

```

# Answer
> 5 votes
# C, 165 bytes

```
n,x,y,b,c;main(c,v)char**v;{for(n=atoi(v[1]);y<=n;++y){for(x=-n;x<n;++x){b=2*n-abs(2*x+1);c=b-2*y+2;b-=6*y;putchar(b>0?95:b<-4&c>0&c%4==1?"/\\"[x<0]:32);}puts("");}}

```

Before the golfing steps that destroy readability:

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

int main(int c, char** v) {
    int n = atoi(v[1]);
    for (int y = 0; y <= n; ++y) {
        for (int x = -n; x < n; ++x) {
            int b = 2 * n - abs(2 * x + 1);
            int c = b - 2 * y + 2;
            b -= 6 * y;
            putchar(b > 0 ? 95 :
                    b < -4 && c > 0 && c % 4 == 1 ? "/\\"[x<0] : 32);
        }
        puts("");
    }
}

```

This loops over all characters in the rectangle containing the figure, and evaluates the line equations that separate the inside of the triangle from the outside, as well as the ones that separate the different parts of the triangle.

# Answer
> 4 votes
# Retina, 182 bytes

```
1
_
^
#$_
((`#([^#]*?)( ?)_(_*)_( ?)([^#]*?)$
$0# $1\$3/$5
+)`\\( ?)_(_*)_( ?)/(?=[^#]*$)
\ $1$2$3 /
#( *(\\ )*\\ *)  ( *(/ )*/)$
$0# $1$3
)`#( *(\\ )*)\\/(( /)*)$
$0# $1$3
#
#
^#
<empty line>

```

Takes input as unary.

Each line should go to its own file and `#` should be changed to newline in the files. This is impractical but you can run the code as is as one file with the `-s` flag, keeping the `#` markers. You can change the `#`'s to newlines in the output for readability if you wish. E.g.:

```
> echo -n 1111|retina -s triangle|tr # '\n'
________
\  __  /
 \ \/ /
  \  /
   \/

```

The code isn't too well golfed (yet).

# Answer
> 2 votes
**C — 206 bytes**

`i,j,m,k,a,b;main(i,v)char**v;{m=atoi(v[1])*2;while(k<m*(m/2+1)){i=k/m;j=k%m;a=i*3,b=(i+j)%2;putchar("_\\/ "[j>=a&&j<m-a?0:j>i-2&&b&&j<i*3-1&&j<m/2?1:j<=m-i&&!b&&j>m-a&&j>=m/2?2:3]);if(j==m-1)puts("");k++;};}`

```
 x,m,i,j,a,b;
int main(x,v)char**v;{
    m=atoi(v[1])*2;
    for(i=0;i<m/2+1;i++){
        for(j=0;j<m;j++){
            a=i*3,b=(i+j)%2;
            j>=a&&j<m-a?a=0:j>=i-1&&b&&j<i*3-1&&j<m/2?a=1:j<=m-i&&!b&&j>m-a&&j>=m/2?a=2:(a=3);putchar("_\\/ \n"[a]);
        }
        puts("");
    }
}

```

**Example output**

```
Pauls-iMac:ppcg pvons$ for i in $(seq 1 7); do ./a.out $i; done
__
\/
____
\  /
 \/
______
\    /
 \  /
  \/
________
\  __  /
 \ \/ /
  \  /
   \/
__________
\  ____  /
 \ \  / /
  \ \/ /
   \  /
    \/
____________
\  ______  /
 \ \    / /
  \ \  / /
   \ \/ /
    \  /
     \/
______________
\  ________  /
 \ \  __  / /
  \ \ \/ / /
   \ \  / /
    \ \/ /
     \  /
      \/

```

# Answer
> 1 votes
# JavaScript (*ES6*) 165 ~~180 204~~

Run snippet in Firefox to test. If returning the string is not enough, using alert for output is 2 chars more.

```
// 165 - return the string
F=n=>
  (i=>{
    for(r='__'[R='repeat'](m=n);i<n;)
      r+=`\n`+' '[R](i)
       +('\\ '[R](t=-~(m>3?i:~-n/3))+' ').slice(0,n-i)
       +'__'[R](m>3?m-=3:0)
       +(' '+' /'[R](t)).slice(i++-n)
  })(0)||r

// 167 - output the string
A=n=>{
  for(i=0,r='__'[R='repeat'](m=n);i<n;)
    r+=`\n`+' '[R](i)
     +('\\ '[R](t=-~(m>3?i:~-n/3))+' ').slice(0,n-i)
     +'__'[R](m>3?m-=3:0)
     +(' '+' /'[R](t)).slice(i++-n);
  alert(r)
}

// TEST
out=x=>O.innerHTML += x+'\n'

for(k=1;k<13;k++)out(k+'\n'+F(k))
```

```
<pre id=O></pre>
```

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


title: Turn over a new leaf

text:
# Question
Title: Turn over a new leaf
You're given a tree, which in computer science tradition, has the *root* at the top and *leaves* at the bottom. The leaf nodes are labelled with numbers. Your goal is to take the special leaf marked `-1` and move it up to be the new root.

`[3, [[16], -1], [4]] --> [[[[4], 3], [16]]]`

You can imagine rotating the special leaf to the top and letting the rest of tree hang off of it. Keeping the tree in the plane while rotating it to get the correct left-to-right order of all the branches.

The new tree has all the leaves of the original tree except for `-1`.

**Input:**

A tree whose leaves are distinct positive integers, except for one leaf of `-1`. The root of the tree will have at least two branches coming off.

The input is given as a nested list like `[3, [[16], -1], [[4]]]` or its string representation. Delimiters are optional and up to you, but adjacent numbers need to be separated.

**Output:**

Output or print the flipped tree in the same format as your input. The order of the list entries must be correct. In-place modification is fine.

If your input/output is a data type, it must be one that prints in the required format by default. Built-ins that basically do the task for you are not allowed.

**Test cases:**

```
>> [3, [[16], -1], [4]]
[[[[4], 3], [16]]]

>> [2, -1]
[[2]]

>> [44, -1, 12]
[[12, 44]]

>> [[[[-1]]], [[[[4]]]]]
[[[[[[[[[4]]]]]]]]]

>> [[1, 2, 3], [4, -1, 6], [7, 8, 9]]
[[6, [[7, 8, 9], [1, 2, 3]], 4]]

>> [9, [8, [7, [6, -1, 4], 3], 2], 1]
[[4, [3, [2, [1, 9], 8], 7], 6]]

```

# Answer
# CJam, 24 24 22 bytes

```
l~{):T]{s$}$(+T1+}gW<p

```

Try it online.

Thanks Dennis for removing 2 bytes.

### Explanation

```
l~          e# Read the input.
{           e# Do:
    ):T     e# Save the last item to T.
    ]       e# Wrap everything else (as an array) and the last item into an array,
    {s$}$   e#   where the one with -1 (having "-" if stringified) is the first item.
    (+      e# Insert the second array into the first array as the first item,
            e#   or just move the -1 to the end if the first item is already -1.
    T1+     e# Check if the array before this iteration ended with -1.
}g          e# Continue the loop if it did't.
W<p         e# Remove the -1 and print.

```
> 7 votes

# Answer
# Pyth, ~~26~~ ~~25~~ ~~24~~ 23 bytes

```
L?y.>b1}\-`Jtb.xyahbJ]J

```

Demonstration. Test Harness.

This defines a function, `y`, which takes a nested Pyth list as input.

There are three cases to explore in this recursive function, due to the ternary, `?`, and the try - except function, `.x`. In the function, the input is `b`.

The first case occurs when `}\-`Jtb` is truthy. This tests whether there is a `-` in the string representation of `tb`, the "tail" of `b`, which is all of `b` except its first element. `tb` is also stored in `J`. Since all labels are positive except for `-1`, this will be true if and only if the `-1` is not in the first element of the list.

In this case, we cyclically right shift `b` by 1 with `.>b1`, and then call the function recursively. This ensures that we will progress to the next step with the element containing `-1` as the head (first element) of the list.

In the next two cases, the above is falsy, so `-1` is in the head of the list.

In the second case, `ahbJ` does not throw an error. An error will be thrown if and only if `hb` is an integer. If this is not the case, then `hb` is a list, and we need to rotate the tree so that the `-1` leaf is nearer the root. `ahbJ` accomplishes this by appending `J` as a single element at the end of `hb`, which effectively moves the root of the tree from `b` to `hb`.

In the third and final case, an error is thrown. Thus, `hb` is a single element. Because of the test in the first case, `hb` must be `-1`. Thus, we can return the rest of `b`, namely `J`, wrapped in a list, namely `]J`.
> 6 votes

---
Tags: code-golf, data-structures
---


title: Generate boxes!

text:
# Question
Title: Generate boxes!
Your task is to generate boxes using any one ASCII character with respect to the inputs given.

# Test Cases

```
1 1   --> =====
          =   =
          =====

1 2   --> =========
          =   =   =
          =========

2 1   --> =====
          =   =
          =====
          =   =
          =====

2 2   --> =========
          =   =   =
          =========
          =   =   =
          =========

2 5   --> =====================
          =   =   =   =   =   =
          =====================
          =   =   =   =   =   =
          =====================

```

# Input

* Input can be taken from one of the following

+ `stdin`
    + Command-line arguments
    + Function arguments (2 arguments, one for each number)
* Input, if taken from `stdin` or command line arguments, will contain two positive integers, seperated by a space.
* The two numbers denote the number of boxes in each column and row

# Output

* Boxes must be outputted in `stdout` (or closest equivalent)
* Each box should have three horizontal spaces in them

# Rules

* Both the numbers will be greater than 0, but will not go beyond 1000
* Any visible character can be used for outputting the boxes. (as long as they aren't too harsh on the eye!)
* You are permitted to write a full program or a function.
* There should be no unnecessary characters except an optional trailing newline character.

# Scoring

This is , so the shortest submission (in bytes) wins.

# Answer
> 10 votes
# Pyth, 23 bytes

```
Mjbmsm@"= "&%k4dh*4HhyG

```

Defines the function `g` which works as desired.

Demonstration.

# Answer
> 10 votes
# Retina, 57 bytes

```
1(?=.* (1*))
$1#$1#

1(?=(1*#1*#)*$)
=
1
====
#
=#

```

Takes input in unary with a trailing newline.

Each line should go to its own file and `#` should be changed to newline in the files. This is impractical but you can run the code as is as one file with the `-s` flag, keeping the `#` markers (and changing the trailing newline to `#` in the input too). You can change the `#`'s back to newlines in the output for readability if you wish. E.g.:

```
> echo -n 11 111#|retina -s boxes|tr # '\n'
=============
=   =   =   =
=============
=   =   =   =
=============

```

Method: 5 single substitution steps. The first two (first 4 lines) creates an `2*N+1` by `M` grid of ones and the next 3 steps (6 lines) format it into the desired output.

The intermediate strings (delimited by `-`'s):

```
11 111
------------------
111
111
111
111
 111
------------------
111
111
111
111
111
------------------
111
=   =   =
111
=   =   =
111
------------------
============
=   =   =
============
=   =   =
============
------------------
=============
=   =   =   =
=============
=   =   =   =
=============

```

# Answer
> 8 votes
# JavaScript (*ES6*), 83

A function with parameters rows and columns. Using template strings, there are 2 embedded newlines that are significant and counted.

Output via `alert` (popup). As `alert` use a proportional font, we get a better result using a letter with a width similar to the space instead of `=`.

Test in Firefox using the console to have the real `alert` output, or run the snippet below.

```
f=(r,c)=>{for(x=y="|";c--;)x+="||||",y+="   |";for(o=x;r--;)o+=`
${y}
`+x;alert(o)}

// TEST

// redefine alert to avoid that annoying popup during test
alert=x=>O.innerHTML=x

test=_=>([a,b]=I.value.match(/\d+/g),f(a,b))

test()
```

```
<input id=I value='2 3'><button onclick="test()">-></button>
<pre id=O></pre>
```

# Answer
> 7 votes
# JavaScript (ES6), ~~75~~ 73

Using copious `repeat` calls, we repeat `|`, then repeat `|` with trailing spaces, and repeat both of those repeats to make rows:

```
f=(y,x)=>alert(((s="|"[r="repeat"](x*4)+`|
`)+"|   "[r](x)+`|
`)[r](y)+s)

```

(Newlines are significant, per edc65's suggestion to use template strings.)

Snippet:

```
<input id="x" type="range" max="10" min="1" step="1" value="3"><input id="y" type="range" max="10" min="1" step="1" value="2"><pre id="o"></pre><script>function f(y,x){return ((s="|"[r="repeat"](x*4)+"|\n")+"|   "[r](x)+"|\n")[r](y)+s};function redraw(){document.getElementById("o").innerHTML=f(document.getElementById("y").value,document.getElementById("x").value)};document.getElementById("x").onchange=redraw;document.getElementById("y").onchange=redraw;document.getElementById("x").oninput=redraw;document.getElementById("y").oninput=redraw;redraw();</script>
```

Without template strings, without method-name reuse, and with added whitespace:

```
f=(y,x)=>alert(
    (
      (s="|".repeat(x*4)+"|\n") +
      "|   ".repeat(x)+"|\n"
    ).repeat(y)+s
)

```

(Using edc65's recommendation to use `|` for better visual spacing.)

# Answer
> 7 votes
# Pip, ~~29~~ 24 = 23 + 1 bytes

Requires the `-n` flag. Takes the height and width as command-line args and builds boxes of of `1`s.

```
([1X4m]XbRLa+1)@<v.1R0s

```

Explanation:

```
                         a,b are cmdline args; m is 1000; v is -1; s is " " (implicit)
 [1X4m]                  List containing 1111 and 1000
       Xb                String repetition of each element b times
         RLa+1           Repeat the list a+1 times
(             )@<v       Now we have one row too many at the end, so take everything
                         but the last item (equiv to Python x[:-1])
                  .1     Concatenate a 1 to the end of each row
                    R0s  Replace 0 with space
                         Print, joining list on newlines (implicit, -n flag)

```

This program takes heavy advantage of the fact that strings are numbers and numbers are strings in Pip. (And the three spaces in those boxes happened to be just right to take advantage of the built-in `m` variable!)

Here's how the list gets built with the input `2 3`:

```
[1111;1000]
[111111111111;100010001000]
[111111111111;100010001000;111111111111;100010001000;111111111111;100010001000]
[111111111111;100010001000;111111111111;100010001000;111111111111]
[1111111111111;1000100010001;1111111111111;1000100010001;1111111111111]
[1111111111111;"1   1   1   1";1111111111111;"1   1   1   1";1111111111111]

```

And the final output:

```
C:\> pip.py 2 3 -ne "([1X4m]XbRLa+1)@<v.1R0s"
1111111111111
1   1   1   1
1111111111111
1   1   1   1
1111111111111

```

More on Pip

# Answer
> 6 votes
## Perl, ~~72~~ ~~63~~ ~~52~~ 50 bytes

My shortest version yet uses `$/` to get a newline char more compactly:

```
$ perl -e 'print((($,="="."   ="x pop.$/)=~s/./=/gr)x(1+pop))' 2 5
=====================
=   =   =   =   =   =
=====================
=   =   =   =   =   =
=====================

```

The previous update puts the mostly empty lines in the output record separator `$,`, and prints a list of continuous lines.

```
$ perl -e 'print((($,="="."   ="x pop."\n")=~s/./=/gr)x(1+pop))' 2 5

```

The previous version might be a bit clearer for the casual reader:

```
$ perl -E 'say($y=($x="="."   ="x pop)=~s/./=/gr);for(1..pop){say$x;say$y}' 2 5

```

The first version used `@ARGV` instead of `pop`:

```
$ perl -E 'say($y=($x="="."   ="x$ARGV[1])=~s/./=/gr);for(1..$ARGV[0]){say$x;say$y}' 2 5

```

# Answer
> 5 votes
# Python 2, ~~58~~ 57 Bytes

Fairly straightforward implementation.

```
def f(x,y):a="="*(4*y+1);print(a+"\n="+"   ="*y+"\n")*x+a

```

Check it out here.

*Thanks to Sp3000 for saving one byte.*

# Answer
> 5 votes
# GNU sed -r, 160

Sigh, I thought this would be smaller, but here it is anyway. Unfortunately sed regexes don't have any lookaround capability.

```
:
s/(.*)1$/   =\1/;t
s/([= ]+)/\1\n\1/
:b
s/   (.*\n)/===\1/;tb
s/(1*)1 $/\n\1/
:c
s/([^\n]*\n[^\n]*\n)(1*)1$/\1\1\2/;tc
s/(=+)(.*)/\1\2\1/
s/(^|\n)(.)/\1=\2/g

```

Taking input as unary from STDIN:

```
$ sed -rf boxes.sed <<< "11 111"
=============
=   =   =   =
=============
=   =   =   =
=============
$

```

# Answer
> 4 votes
# CJam, 25 bytes

```
q~)S3*'=5*+4/f*3f>\)*1>N*

```

Try it online in the CJam interpreter.

### How it works

```
q~                        e# Read H and W from STDIN.
   S3*'=5*+               e# Push "   =====".
           4/             e# Chop into ["   =" "===="].
  )          f*           e# Repeat each string W+1 times.
               3f>        e# Cut off the first three characters.
                  \)*     e# Repeat the resulting array H+1 times.
                     1>   e# Remove the first string.
                       N* e# Join the lines.

```

# Answer
> 4 votes
# Marbelous, 168 bytes

This answer only works up to 255x255, not 1000x1000, due to limitations of the Marbelous language. I'm working on a 32-bit library, but it's not going to be ready any time soon.

Input is provided as two command line parameters or function parameters to the main board.

```
@2@3}1@0
SLEL//>0\/
@3@1}0--
}1&0@0/\&0
@1/\@2}1\/
:SL
..}0@0
&0/\>0&0
EN..--\/
{0@0/\ES
:EL
..@0
..>0EN
}0--\/
@0/\EX
:EX
}0
\/3D3D3D3D
:ES
}0
\/3D202020
:EN
}0
{03D0A

```

Pseudocode:

```
MB(H,W):
    EL(W)
    for 1..H:
        SL(W)
        EL(W)
EL(W):
    for 1..W:
        EX()
    EN()
SL(W):
    for 1..W:
        ES()
    EN()
EX():
    print "===="
ES():
    print "=   "
EN():
    print "=\n"

```

# Answer
> 3 votes
# Python ~~3~~ 2, ~~160~~ ~~87~~ ~~85~~ 79 bytes

I know this can be golfed a ***lot*** more, I would like some suggestions as this is my first try at golfing.

```
def d(x,y):
    for i in[1]*x:print'='*(4*y+1)+'\n'+'=   '*(y+1)
    print'='*(4*y+1)

```

Thanks to @Cool Guy and @Sp3000's tips, I narrowed the size down to just ~~above~~ below half.

Eg: d(3,3)

```
=============
=   =   =   =
=============
=   =   =   =
=============
=   =   =   =
=============

```

Try it out here.

Excuse the trailing whitespaces.

# Answer
> 3 votes
# CJam ~~52~~ ~~51~~ ~~46~~ 41 bytes

```
l~:B;:A;'=:U{{U4*}B*N}:V~{U{SZ*U}B*NUV}A*

```

Thanks to Sp3000 for -5 chars

Thanks to Martin Büttner♦ for another 5 chars

Try it

# Answer
> 3 votes
# c function, 81

```
x,y;f(h,w){for(;y<=h*2;y++)for(x=0;x<w*4+2;x++)putchar(x>w*4?10:x&3&&y&1?32:61);}

```

### Test program:

```
x,y;f(h,w){for(;y<=h*2;y++)for(x=0;x<w*4+2;x++)putchar(x>w*4?10:x&3&&y&1?32:61);}

int main (int argc, char **argv)
{
  f(2, 3);
}

```

# Answer
> 3 votes
# PHP4.1, ~~76~~ ~~71~~ 69 bytes

This is as golfed as I can get.

```
$R=str_repeat;echo$R(($T=$R('-',4*$H+1))."
|{$R('   |',$H)}
",$V),$T;

```

This expects the key `H` to have the number of lines and `V` the number of boxes per line.

I'm using `-` and `|` just so the boxes actually look like boxes. If required, I can change it to `=`. It doesn't matter the char that is used.
Leaving `-` and `|` also helps to understand the mess that's going on.

---

Old method, 76 bytes:

```
for($R=str_repeat;$H--;)echo$T=$R('-',($V*4)+1),"
|{$R('   |',$V)}
";echo$T;

```

---

Example of output:

```
http://localhost/file.php?H=2&V=3

-------------
|   |   |   |
-------------
|   |   |   |
-------------

```

# Answer
> 3 votes
# Julia, 59 bytes

```
(n,m)->(l="="^(4m+1)*"\n";print(l*("="*"   ="^m*"\n"*l)^n))

```

This creates an unnamed function that accepts two integers as input and prints the result to STDOUT. To call it, give it a name, e.g. `f=(n,m)->...`.

Ungolfed + explanation:

```
function f(n, m)
    # Store the solid row
    l = "="^(4m + 1) * "\n"

    # Print all rows by repeating a pattern n times
    print(l * ("=" * "   ="^m * "\n" * l)^n)
end

```

Examples:

```
julia> f(2, 3)
=============
=   =   =   =
=============
=   =   =   =
=============

julia> f(1, 5)
=====================
=   =   =   =   =   =
=====================

```

Any suggestions are welcome.

# Answer
> 3 votes
# R, ~~83~~ 81

As an unnamed function taking h and w as parameters. Builds the 1st and second lines into a vector for each row and replicates it `h` times. Appends a vector for the bottom line and `cat`s out the vector using `fill` to restrict the length of the lines. Now takes advantage of the any visible character rule.

```
function(h,w)cat(rep(c(A<-rep(1,w*4+2),rep('   1',w)),h),A[-1],fill=w*4+1,sep='')

```

Test run

```
> f=function(h,w)cat(rep(c(A<-rep(1,w*4+2),rep('   1',w)),h),A[-1],fill=w*4+1,sep='')
> f(4,2)
111111111
1   1   1
111111111
1   1   1
111111111
1   1   1
111111111
1   1   1
111111111
>

```

# Answer
> 3 votes
# bash + coreutils, 57

```
dc -e"2do$2 4*1+^1-pd8*F/1+$1si[fli1-dsi0<c]dscx"|tr 0 \

```

This uses `dc` to print binary numbers that have `1`s for the box edges and `0`s for the spaces.

* the all-ones number **X** is calculated by `2 ^ (width * 4 + 1) - 1`, then pushed and printed
* the `10001...0001` number is calculated by **`X`**`* 8 / 15 + 1`, then pushed
* the stack is then dumped `height` times

The `tr` then converts the `0`s to space characters.

### Output

```
$ ./boxes.sh 2 4
11111111111111111
1   1   1   1   1
11111111111111111
1   1   1   1   1
11111111111111111
$

```

# Answer
> 2 votes
# JavaScript, ~~92~~ 85 bytes

I had hoped this would be shorter than the other JS answer (nice work as always, edc65), but oh well. I have a feeling the math here can be further golfed.

```
f=(r,c)=>(x=>{for(i=s='';(y=i++/x)<r-~r;)s+=i%x?' *'[-~y%2|!(-~i%4)]:'\n'})(4*c+2)||s

```

# Answer
> 2 votes
# KDB(Q), 37 bytes

```
{(3+2*x-1)#(5+4*y-1)#'(4#"=";"=   ")}

```

# Explanation

```
                      (4#"=";"=   ")     / box shape
           (5+4*y-1)#'                   / extend y axis
 (3+2*x-1)#                              / extend x axis
{                                   }    / lambda

```

# Test

```
q){(3+2*x-1)#(5+4*y-1)#'(4#"=";"=   ")}[2;5]
"====================="
"=   =   =   =   =   ="
"====================="
"=   =   =   =   =   ="
"====================="

```

# Answer
> 2 votes
# Octave, ~~69~~ ~~65~~ 64

```
y=ones([2,4].*input()+1);y(1:2:end,:)=y(:,1:4:end)=4;char(y+31)

```

Thanks to DLosc for pointing out issues that led to -1

Takes input as `[1 1]` and outputs:

```
#####
#   #
#####

```

You can also just input '1' and get 1x1. If the input really needs to be `1 1`, the size goes up to **~~88~~ ~~85~~ 84**:

```
y=ones([2,4].*eval(['[',input(0,'s'),']'])+1);y(1:2:end,:)=y(:,1:4:end)=4;char(y+31)

```

Note: Matlab doesn't allow Octave's chaining or input(integer), but here is the Matlab version (**67**):

```
y=ones([2,4].*input('')+1);y(1:2:end,:)=4;y(:,1:4:end)=4;char(y+31)

```

# Answer
> 2 votes
# C, 76 bytes

```
w,n;f(r,c){for(w=c*4+2,n=w*r*2+w;n--;)putchar(n%w?n/w%2&&n%w%4-1?32:61:10);}

```

Invoked as a function with number of rows and columns as arguments. For example:

```
f(5, 2)

```

# Answer
> 2 votes
# CJam, ~~30~~ 29 bytes

New version with redundant `+` at the end removed (thanks, Dennis):

```
l~_4*)'=*N+:F\'=S3*+*'=+N++*F

```

I know that Dennis already posted a CJam solution that beats this by miles. But this is my very first attempt at CJam, so it's a miracle that it works at all. :)

Fairly brute force. Builds the first line from `4 * H + 1` `=` signs, then the second line from `=` repeated `H` times, with another `=` added. Then concatenates the two lines, repeats the whole thing `V` times, and then adds another copy of the first line.

It feels like I have way too many stack manipulations, and even ended up storing the first line in a variable because I had to shuffle stuff around on the stack even more otherwise.

Not very elegant overall, but you have to start somewhere... and I wanted to try a simple problem first.

# Answer
> 2 votes
# CJam, 23

```
q~[F8]f{2b*1+' f+N}*_0=

```

Try it online

**Explanation:**

```
q~        read and evaluate the input (height width)
[F8]      make an array [15 8] - 1111 and 1000 in base 2
f{…}      for width and each of [15 8]
  2b      convert the number to base 2
  *       repeat the digits "width" times
  1+      append a 1 to the array of digits (right edge)
  ' f+    add the space character to each digit (0->' ', 1->'!')
  N       push a newline
*         repeat the resulting array "height" times
_0=       copy the first line (bottom edge)

```

# Answer
> 1 votes
## Java, 181

I hope that according to

> You are permitted to write a full program or a function.

it is compliant to the rules to count the bytes of the *function*, which is 181 in this case

```
import static java.lang.System.*;
public class Boxes
{
    public static void main(String[] args)
    {
        Boxes b=new Boxes();
        System.out.println("1,1:");
        b.b(1,1);
        System.out.println("1,2:");
        b.b(1,2);
        System.out.println("2,1:");
        b.b(2,1);
        System.out.println("2,2:");
        b.b(2,2);
        System.out.println("2,5:");
        b.b(2,5);
    }

    void b(int R, int C){String s="",e=s,x,y,z=s,a="====",n="=\n";int r,c;for(r=R;r-->0;){x=y=e;for(c=C;c-->0;){x+=a;y+="=   ";}s+=x+n+y+n;}for(c=C;c-->0;){z+=a;}s+=z+n;out.println(s);}
}

```

# Answer
> 1 votes
# C#, ~~153~~ ~~151~~ 150

This can't really compete but here it is just for fun:

```
(h,w)=>{string s="=",e="\n",a="====",b="   =",m=a,o;int i=0,j;for(;i++<=h*2;){o=s;for(j=0;j++<w+1;o=m)System.Console.Write(o);m=m==a?b:a;s=e+s;e="";}}

```

How to run:

```
public class Program
{
    public static void Main()
    {
        new System.Action<int, int>((h,w)=>{string s="=",e="\n",a="====",b="   =",m=a,o;int i=0,j;for(;i++<=h*2;){o=s;for(j=0;j++<w+1;o=m)System.Console.Write(o);m=m==a?b:a;s=e+s;e="";}})(3, 4);
    }
}

```

Open for improvements.

# Answer
> 1 votes
# Dart, 57

```
b(y,x,{z:'='}){z+=z*4*x;print('$z\n=${'   ='*x}\n'*y+z);}

```

Try it at: https://dartpad.dartlang.org/36ed632613395303ef51

# Answer
> 1 votes
## Ruby, ~~57~~ ~~48~~ 45

```
f=->h,w{l=?=*w*4+?=;(l+$/+'=   '*w+"=
")*h+l}

```

Usage:

```
print f[2,5]

```

Thanks to manatwork for saving 3 bytes.

# Answer
> 1 votes
## Brainfuck, ~~157~~ ~~156~~ 152 (~~123~~ ~~120~~ ~~118~~ 117 with unary)

This works with Alex Pankratov's bff (brainfuck interpreter used on SPOJ and ideone) and Thomas Cort's BFI (used on Anarchy Golf).

The input must contain a single pair of integers (in decimal) separated by a space, without a trailing newline.

Demonstration on ideone.

```
,+
[
  >++++++[<-[------->>] >[->>] <<-]
  <
  [
    -
    <[>++++++++++<-]
    <
  ]
  >>[<+>-]
  ,+
]
+++++++++++[>+++>+++>+<<<-]
<<<+
[
  >>
  [<+> >>>.<...<<-]
  >+>+>.>-.+
  [<]
  <
  [
    <->
    >>>--<,<
  ]
  <[>+<-]
  <
]

```

**Brief explanation:**

At the end of first loop we are left with

`r 0 c [0]`

We then change this to

`[r+1] 0 c 0 33 33 11 0`

and begin the main loop. In that loop, the tricky part is alternating between `33` (exclamation mark) and `32` (space), and alternating between decrementing and not decrementing the number of rows. This is done with a flag using the cell to the right of `c`.

**Update:**

I had not considered unary input until reading some other answers. Here is a unary version:

```
+
[
  ->++++[<-------->-]
  <[<+<]
  >>,+
]
+++++++++++[>+++>+++>+<<<-]
<<<
[
  >>
  [<+> >>>.<...<<-]
  >+>+>.>-.+
  [<]
  <
  [
    <->
    >>>--<,<
  ]
  <[>+<-]
  <
]

```

# Answer
> 1 votes
# Lua, ~~95~~ ~~93~~ 85 bytes.

Works with command-line arguments.

Gotta love those string methods

```
a=arg[2]c="="l=c:rep(a*2+1)print((l.."\n"..(("= ")):rep(a)..c.."\n"):rep(arg[1])..l)

```

# Answer
> 1 votes
# Python 2.7, 66 bytes.

I know there are already better solutions in python, but that's the best I came up with.

```
def f(x,y):a,b,c="="*4,"   =","\n=";print "="+a*y+(c+b*y+c+a*y)*x

```

Example:

```
f(3,4)

=================
=   =   =   =   =
=================
=   =   =   =   =
=================
=   =   =   =   =
=================

```

# Answer
> 1 votes
# SAS, 117 119

```
macro a array a[0:1]$4('#   ' '####');do x=1 to 2+2*&x-1;t=repeat(a[mod(x,2)],&y-1);put t $char%%eval(&y*3). '#';end;%

```

Example:

```
%let x=4;
%let y=4;
data;a;run;

```

Result:

```
#############
#   #   #   #
#############
#   #   #   #
#############
#   #   #   #
#############
#   #   #   #
#############

```

# Answer
> 1 votes
# Java, ~~123~~ 119 bytes

```
void p(int h,int w){String b="=",d="\n=";for(;w-->0;d+="   =")b+="====";for(d+="\n"+b;h-->0;b+=d);System.out.print(b);}

```

Abusing the input parameters as counters greatly helped in decreasing code size.

Thanks to Cool Guy for suggesting the abuse of for syntax.

# Answer
> 1 votes
# GolfScript, 48 bytes

```
2 5:b;:a;0`:z;{4b*1+z*n+}:r~{{z' '3*}b*z+n+r}a*

```

Takes the size as the first two inputs (here the first two digits).

Demonstration

```
000000000000000000000
0   0   0   0   0   0
000000000000000000000
0   0   0   0   0   0
000000000000000000000

```

# Answer
> 1 votes
# Haskell, 153

At least it's beating Java!

```
s r c
 |r==1=a c
 |otherwise=s (r-1)c++(take 2$tail(a c))
 where
 a 1=[f,"=   =",f]
 a n=map(\x->x++((take 4.tail)x))(a(n-1))
 f="====="

p r=unlines.s r

```

Works in ghci, although ghci doesn't take a new line on \n.

Here is the ungolfed version:

```
import System.Environment

xsquare :: Int -> [String]
xsquare 1 = ["=====","=   =","====="]
xsquare n = map (\x -> x++((take 4 . tail) x)) (xsquare (n-1))

ysquare :: Int -> [String] -> [String]
ysquare 1 x = x
ysquare n x = ysquare (n-1) (x ++ (take 2 $ tail x))

squares :: Int -> Int -> [String]
squares x y = ysquare y (xsquare x)

main = do
  a <- getArgs
  let [x,y] = (map read . take 2) a
  putStrLn $ unlines $ squares y x

```

It calculates the horizontal shape first, then finds the vertical shape by adding the last two lines of the horizontal shape the appropriate number of times. The main function is so I could test it properly with command line arguments and proper newline behaviour.

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