# Question
Title: Remove the mininum sum seam from an array
The seam carving algorithm, or a more complex version of it, is used for content-aware image resizing in various graphics programs and libraries. Let's golf it!

Your input will be a rectangular two dimensional array of integers.

Your output will be the same array, one column narrower, with one entry removed from each row, those entries representing a path from top to bottom with the lowest sum of all such paths.

https://en.wikipedia.org/wiki/Seam\_carving

In the above illustration, each cell's value is shown in red. The black numbers are the sum of a cell's value and the lowest black number in one of the three cells above it (pointed to by the green arrows). The white highlighted paths are the two lowest sum paths, both with a sum of 5 (1+2+2 and 2+2+1).

In a case where there are two paths tied for the lowest sum, it does not matter which you remove.

Input should be taken from stdin or as a function parameter. It can be formatted in a manner convenient to your language of choice, including brackets and/or delimiters. Please specify in your answer how the input is expected.

Output should be to stdout in an unambiguously delimited format, or as a function return value in your language's equivalent to a 2d array (which might include nested lists, etc).

Examples:

```
Input:
1 4 3 5 2
3 2 5 2 3
5 2 4 2 1
Output:
4 3 5 2      1 4 3 5
3 5 2 3  or  3 2 5 3
5 4 2 1      5 2 4 2

Input:
1 2 3 4 5
Output:
2 3 4 5

Input:
1
2
3
Output:
(empty, null, a sentinel non-array value, a 0x3 array, or similar)

```

EDIT: The numbers will all be non-negative, and every possible seam will have a sum that fits in a signed 32 bit integer.

# Answer
# CJam, ~~51~~ 44 bytes

```
{_z,1$,m*{_1>.-W<2f/0-!},{1$.=:+}$0=.{WtW-}}

```

This is an anonymous function that pops a 2D array from the stack and pushes one in return.

Try the test cases online in the CJam interpreter.1

### Idea

This approach iterates over all possible combinations of row elements, filters out those that do not correspond to seams, sorts by the corresponding sum, select the minimum and removes the corresponding elements from the array.2

### Code

```
_z,   e# Get the length of the transposed array. Pushes the number of columns (m).
1$,   e# Get the length of the array itself. Pushes the number of rows (n).
m*    e# Cartesian power. Pushes the array of all n-tuples with elements in [0 ... m-1].
{     e# Filter:
  _1> e#     Push a copy of the tuple with first element removed.
  .-  e#     Vectorized difference.
  W<  e#     Discard last element.
  2f/ e#     Divide all by 2.
  0-  e#     Remove 0 from the results.
  !   e#     Push 1 if the remainder is empty and 0 otherwise.
},    e#     Keep only tuples which pushed a 1.

      e# The filtered array now contains only tuples that encode valid paths of indexes.

{     e# Sort by:
  1$  e#     Copy the input array.
  .=  e#     Retrieve the element of each row that corresponds to the index in the tuple.
  :+  e#     Add all elements.
}$    e#
0=    e# Retrieve the tuple of indexes with minimum sum.
.{    e# For each row in the array and the corresponding index in the tuple:
  Wt  e#     Replace the element at that index with -1.
  W-  e#     Remove -1 from the row.
}

```

---

1 Note that CJam cannot distinguish between empty arrays and empty strings, since strings are just arrays whose elements are characters. Thus, the string representation of both empty arrays and empty strings is `""`.

2 While the time complexity of the algorithm shown on the Wikipedia page should be of **O(nm)** for an **n×m** matrix, this one's is at least of **O(mn)**.
> 5 votes

# Answer
# Haskell, 187 bytes

```
l=length
f a@(b:c)=snd$maximum$(zip=<<map(sum.concat))$map(zipWith((uncurry((.drop 1).(++)).).flip splitAt)a)$iterate((\e@(f:_)->[f-1:e,f:e,min(f+1)(l b-1):e])=<<)[[y]|y<-[0..l b-1]]!!l c

```

Usage example:

```
*Main> f [[1,4,3,5,2],[3,2,5,2,3],[5,2,4,2,1]]
[[4,3,5,2],[3,5,2,3],[5,4,2,1]]

*Main> f [[1],[2],[3]]
[[],[],[]]

*Main> f [[1,2,3,4,5]]
[[2,3,4,5]]

```

How it works, short version: build a list of all paths (1), per path: remove corresponding elements (2) and sum all remaining elements (3). Take the rectangle with the largest sum (4).

Longer version:

```
Input parameters, assigned via pattern matching:
a = whole input, e.g. [[1,2,4],[2,5,6],[3,1,6]]
b = first line, e.g. [1,2,4]
c = all lines, except first, e.g. [[2,5,6],[3,1,6]]

Step (1), build all paths:

iterate((\e@(f:_)->[f-1:e,f:e,min(f+1)(l b-1):e])=<<)[[y]|y<-[0..l b-1]]!!l c

     [[y]|y<-[0..l b-1]]           # build a list of single element lists
                                   # for all numbers from 0 to length b - 1
                                   # e.g. [[0],[1],[2]] for a 3 column input.
                                   # These are all possible start points

     \e@(f:_)->[f-1:e,f:e,min(f+1)(l b-1):e]
                                   # expand a list of paths by replacing each
                                   # path with 3 new paths (up-left, up, up-right)

     (...)=<<                      # flatten the list of 3-new-path lists into
                                   # a single list

     iterate (...) [...] !! l c    # repeatedly apply the expand function to
                                   # the start list, all in all (length c) times.

Step (2), remove elements

map(zipWith((uncurry((.drop 1).(++)).).flip splitAt)a)

     (uncurry((.drop 1).(++)).).flip splitAt
                                   # point-free version of a function that removes
                                   # an element at index i from a list by
                                   # splitting it at index i, and joining the
                                   # first part with the tail of the second part

      map (zipWith (...) a) $ ...  # per path: zip the input list and the path with
                                   # the remove-at-index function. Now we have a list
                                   # of rectangles, each with a path removed

Step (3), sum remaining elements

zip=<<map(sum.concat)             # per rectangle: build a pair (s, rectangle)
                                  # where s is the sum of all elements

Step (4), take maximum

snd$maximum                      # find maximum and remove the sum part from the
                                 # pair, again.

```
> 5 votes

# Answer
# IDL 8.3, 307 bytes

Meh, I'm sure this won't win because it's long, but here's a straightforward solution:

```
pro s,a
z=size(a,/d)
if z[0]lt 2then return
e=a
d=a*0
u=max(a)+1
for i=0,z[1]-2 do begin
e[*,i+1]+=min([[u,e[0:-2,i]],[e[*,i]],[e[1:*,i],u]],l,d=2)
d[*,i]=l/z[0]-1
endfor
v=min(e[*,-1],l)
r=intarr(z[1])+l
for i=z[1]-2,0,-1 do r[0:i]+=d[r[i+1],i]
r+=[0:z[1]-1]*z[0]
remove,r,a
print,reform(a,z[0]-1,z[1])
end

```

Ungolfed:

```
pro seam, array
  z=size(array, /dimensions)
  if z[0] lt 2 then return
  energy = array
  ind = array * 0
  null = max(array) + 1
  for i=0, z[1]-2 do begin
    energy[*, i+1] += min([[null, energy[0:-2,i]], [energy[*,i]], [energy[1:*,i], null]], loc ,dimension=2)
    ind[*, i] = loc / z[0] - 1
  endfor
  void = min(energy[*,-1], loc)
  rem = intarr(z[1]) + loc
  for i=z[1]-2, 0, -1 do rem[0:i] += ind[rem[i+1], i]
  rem += [0:z[1]-1]*z[0]
  remove, rem, array
  print, reform(array, z[0]-1, z[1])
end

```

We iteratively create the energy array and track which direction the seam goes, then construct a removal list once we know the final position. Remove the seam via 1D indexing, then reform back into the array with the new dimensions.
> 3 votes

# Answer
# JavaScript (*ES6*) 197 ~~209 215~~

Step by step implementation of the wikipedia algorithm.

Probably can be shortened more.

Test running the snippet in Firefox.

```
// Golfed

F=a=>(u=>{for(r=[i=p.indexOf(Math.min(...p))];l--;i=u[l][i])(r[l]=[...a[l]]).splice(i,1)})
(a.map(r=>[r.map((v,i)=>(q[i]=v+~~p[j=p[i+1]<p[j=p[i-1]<p[i]?i-1:i]?i+1:j],j),q=[++l]),p=q][0],p=[l=0]))||r

// LESS GOLFED

U=a=>{
  p = []; // prev row
  u = a.map( r => { // in u the elaboration result, row by row
      q=[];
      t = r.map((v,i) => { // build a row for u from a row in a
        j = p[i-1] < p[i] ? i-1 : i; // find position of min in previous row
        j = p[i+1] < p[j] ? i+1 : j;
        q[i] = v + ~~p[j]; // values for current row
        // ~~ convert to number, as at first row all element in p are 'undefined'
        return j;//  position in u, row by row
      });
      p = q; // current row becomes previous row
      return t;
  });
  n = Math.min(...p) // minimum value in the last row
  i = p.indexOf(n); // position of minimum (first if there are more than one present)
  r = []; // result
  // scan u bottom to up to find the element to remove in the output row
  for(j = u.length; j--;)
  {
    r[j] = a[j].slice(); // copy row to output
    r[j].splice(i,1); // remove element
    i = u[j][i]; // position for next row
  }
  return r;
}

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

test=[
  [[1,4,3,5,2],[3,2,5,2,3],[5,2,4,2,1]],
  [[1,2,3,4,5]],
  [[1],[2],[3],[4]]
];

test.forEach(t=>{
  out('Test data:\n' + t.map(v=>'['+v+']').join('\n'));
  r=F(t);
  out('Golfed version:\n' + r.map(v=>'['+v+']').join('\n'))
  r=U(t);
  out('Ungolfed version:\n' + r.map(v=>'['+v+']').join('\n'))
})
```

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

# Answer
# Pip, 91 bytes

This won't win any prizes, but I had fun working on it. Whitespace is for cosmetic reasons only and is not included in the byte count.

```
{
 p:{(zaj-1+,3RMv)}
 z:a
 w:,#(a0)
 Fi,#a
  Fjw
   Ii
    z@i@j+:MN(pi-1)
 s:z@i
 Ti<0{
  j:s@?MNs
  a@i@:wRMj
  s:(p--i)
 }
 a
}

```

This code defines an anonymous function whose argument and return value are nested lists. It implements the algorithm from the Wikipedia page: `a` (the argument) is the red numbers, and `z` is the black numbers.

Here's a version with test harness:

```
f:{p:{(zaj-1+,3RMv)}z:aw:,#(a0)Fi,#aFjwIiz@i@j+:MN(pi-1)s:z@iTi<0{j:s@?MNsa@i@:wRMjs:(p--i)}a}
d:[
 [[1 4 3 5 2]
  [3 2 5 2 3]
  [5 2 4 2 1]]
 [[1 2 3 4 5]]
 [[1]
  [2]
  [3]]
 ]
Fld
 P(fl)

```

Results:

```
C:\> pip.py minSumSeam.pip -p
[[4;3;5;2];[3;5;2;3];[5;4;2;1]]
[[2;3;4;5]]
[[];[];[]]

```

And here's the rough equivalent in Python 3. If anyone wants a better explanation of the Pip code, just ask in the comments.

```
def f(a):
    z = [row.copy() for row in a]
    w = range(len(a[0]))

    for i in range(len(a)):
        for j in w:
            if i:
                z[i][j] += min(z[i-1][max(j-1,0):j+2])
    s = z[i]
    while i >= 0:
        j = s.index(min(s))
        del a[i][j]
        i -= 1
        s = z[i][max(j-1,0):j+2]
    return a

```
> 1 votes

---
Tags: code-golf, image-processing
---


title: Recursive Prime Factorization

text:
# Question
Title: Recursive Prime Factorization
Your job is to take the prime factors of a number taken from input (omitting any exponents equal to 1) then take the prime factors of all of the exponents, and so on, until no composite numbers remain; and then output the result.

To make what I'm asking slightly clearer, here's a javascript program that does it, but, at 782 bytes, it's not very well golfed yet:

```
var primes=[2,3];
function nextPrime(){
    var n=2;
    while(isAMultipleOfAKnownPrime(n)){n++}
    primes.push(n);
}
function isAKnownPrime(n){return primes.indexOf(n)!=-1};
function isAMultipleOfAKnownPrime(n){
    for(var i=0;i<primes.length;i++)if(n%primes[i]==0)return true;
    return false;
}
function primeFactorize(n){
    while(primes[primes.length-1]<n)nextPrime();
    if(isAKnownPrime(n)||n==1)return n;
    var q=[];while(q.length<=n)q.push(0);
    while(n!=1){
        for(var i=0;i<primes.length;i++){
            var x=primes[i];
            if(n%x==0){q[x]++;n/=x}
        }
    }
    var o="";
    for(var i=2;i<q.length;i++){
        if(q[i]){if(o)o+="x";o+=i;if(q[i]>1){o+="^("+primeFactorize(q[i])+")"}}
    }
    return o;
}
alert(primeFactorize(+prompt()));

```

You are required to make order of operations as clear as possible, and sort the prime factors in ascending order on each level.

You get a -50 byte bonus if you produce the output as formatted mathprint or valid latex code.

# Answer
# CJam, ~~32~~ ~~31~~ ~~29~~ ~~27~~ 25 - 50 = -25 bytes

*7 bytes saved by Dennis.*

Woooo, Dennis reduced this by an amazing seven bytes and managed to beat Pyth!

```
q~S2*{mF{~'^'{@j'}'*}/;}j

```

Test it here.

## Explanation

```
q~                           e# Read and eval input.
  S2*                        e# Push the string "  ". The second space will be our
                             e# memoised result for input 1. This way, 1-exponents become
                             e# ^{ } later which do not affect the rendered output of the
                             e# generated LaTeX.
     {                 }j    e# Initialise a recursion with the above base case.
      mF                     e# Compute prime factorisation as list of pairs.
        {           }/       e# For each pair...
         ~'^'{@              e# Unwrap the pair and put a '^' and a '{' in the middle.
               j             e# Recursively run the outer block on the exponent.
                '}'*         e# Push a '}' and a '*' character.
                      ;      e# Discard the last '*'.

```

All those stack contents will be printed automatically back-to-back at the end of the program.
> 7 votes

# Answer
# Pyth, 27 - 50 = -23 bytes

```
Lj\*m+ed?+\^jyhd`HthdkrPb8

```

This defines a recursive function `y`. Try it online: Demonstration

The output is valid LaTeX code, so I claim the bonus. The call `y66430125` returns the string `3^{2^{2}*3}*5^{3}`, which renders to

Quite proud for finding a way to print the curly brackets without using curly brackets in my code.

# Explanation:

```
L                            define a function y(b): return ...
                       Pb       prime factorization of b
                      r  8      run-length-encoded, gives pairs of (exponent, prime)
    m                           map each pair d (exponent, prime) to:
      ed                          prime
     +                            +
             yhd                    recursive call
            j   `H                  join repr(H) by ^
                                      H is preinitialized with an empty dictionary
                                      so the repr(H) gives the string "{}"
                                      and join inserts the prime-factorization
                                      of the exponent between the chars of "{}"

         +\^                        add "^" at the beginning
        ?         thd               if exponent - 1 != 0 else
                     k              "" (empty string)
 j\*                            join by "*"

```
> 14 votes

# Answer
# Pyth - ~~39~~ ~~34~~ ~~32~~ 28 bytes

Thanks Jakube

Defines a function `y` which takes an integer:

```
L?j\xm+ed+"^("+yhd\)rPb8tPbb

```

Explanation:

```
L                              define y(b): return
  j\x                              "x".join(
     m                                 map(lambda d:
      +ed+"^("+yhd\)                       d[1] + "^(" + y(d[0]) + ")",
                    rPb8                   tally(prime_factors(b))))
 ?                      tPb        if len(prime_factors(b)) != 1 else
                           b           b

```

If `^(1)` isn't allowed I have to use 33 bytes:

```
L?j\xm+ed?+"^("+yhd\)thdkrPb8tPbb

```
> 6 votes

# Answer
# Mathematica, ~~106~~ ~~102~~ 101 - 50 = 51 bytes

```
If[PrimeQ@#,#,(a=CenterDot)@@{b,c}~Function~If[c<2,b,b~Superscript~#0@c]@@@FactorInteger@#/.a@b_:>b]&

```

Formats as nested exponents with dot multiplication. Unicode representations of example input and output:

* `10``2 · 5`
* `120``2³ · 3 · 5`
* `16384``2²˙⁷`
> 4 votes

# Answer
# Bash + coreutils + bsdgames, 117 - 50 = 67

```
f()(factor $1|tr \  \\n|sed 1d|uniq -c|while read e m;do
((e>1))&&m+=^{`f $e`}
printf {$m}
done)
f $1|sed s/}{/}\*{/g

```

### Output

```
$ ./recprimefac.sh 2985984
{2^{{2^{{2}}}*{3}}}*{3^{{2}*{3}}} $
$

```

I'm claiming the -50 bonus, because this output is LaTeX formatted and with a tool like http://www.sciweavers.org/free-online-latex-equation-editor renders to:

Let me know if this is not acceptable.
> 3 votes

# Answer
# Clip, ~~36~~ 33

```
jm[z.y(z?()z{'^'(M)z')`]L]}qfnx"*

```

## Explanation

```
                            qfnx   .- Prime factors of the input, with exponents -.
  m[z                      }       .- For each factor z...               -.
     .y(z                          .- The prime number                   -.
         ?()z            L]        .- If the exponent is 1, nothing      -.
             {         `]          .- Otherwise, the following:          -.
                  M)z              .- Apply the main function to the exponent... -.
              '^'(   ')            .- ...inside ^(..)                    -.
 j                              "* .- Join the factors with "*"          -.

```
> 1 votes

# Answer
# Javascript, 388-50=338

```
l="length";function g(n){for(;m(++n););p.push(n)}function m(n){for(i=0;i<p[l];i++)if(n%p[i]==0)return 1;return 0}function f(n,x,q,o){while(p[p[l]-1]<n)g(2);if(p.indexOf(n)>=0||n==1)return n;q=[];while(q[l]<=n)q.push(0);for(i=0;i<p[l];i++){x=p[i];while(n%x==0){q[x]++;n/=x}}o="";for(i=2;i<q[l];i++)if(q[i]){if(o)o+="*";o+=i;if(q[i]>1){o+="^{"+f(q[i])+"}"}}return o}alert(f(+prompt(p=[2])))

```

Since LaTeX code is now eligible for the bonus, I decided to include the requisite modifications as part of the golfing for this. It can probably still be golfed further though.
> 1 votes

---
Tags: code-golf, primes
---


# Question
Title: Determine the Dimensions of a Rotated Rectangle
This Stack Snippet draws an aliased white rectangle on a black background given parameters for its dimensions, position, angle, and the grid dimensions:

```
<style>html *{font-family:Consolas,monospace}input{width:24pt;text-align:right;padding:1px}canvas{border:1px solid gray}</style><p>grid w:<input id='gw' type='text' value='60'> grid h:<input id='gh' type='text' value='34'> w:<input id='w' type='text' value='40'> h:<input id='h' type='text' value='24'> x:<input id='x' type='text' value='0'> y:<input id='y' type='text' value='0'> θ:<input id='t' type='text' value='12'>° <button type='button' onclick='go()'>Go</button></p>Image<br><canvas id='c'>Canvas not supported</canvas><br>Text<br><textarea id='o' rows='36' cols='128'></textarea><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><script>function toCart(t,a,n,r){return{x:t-n/2,y:r/2-a}}function vtx(t,a,n){return{x:n.x+t*Math.cos(a),y:n.y+t*Math.sin(a)}}function sub(t,a){return{x:t.x-a.x,y:t.y-a.y}}function dot(t,a){return t.x*a.x+t.y*a.y}function inRect(t,a,n,r){var e=sub(a,t),o=sub(a,n),l=sub(a,r),i=dot(e,o),v=dot(e,l);return i>0&&i<dot(o,o)&&v>0&&v<dot(l,l)}function go(){var t=parseInt($("#gw").val()),a=parseInt($("#gh").val()),n=parseFloat($("#w").val()),r=parseFloat($("#h").val()),e={x:parseFloat($("#x").val()),y:parseFloat($("#y").val())},o=Math.PI*parseFloat($("#t").val())/180,l=Math.sqrt(n*n+r*r)/2,i=Math.atan2(r,n),v=vtx(l,o+i,e),h=vtx(l,o+Math.PI-i,e),u=vtx(l,o-i,e),x=$("#c");x.width(t).height(a).prop({width:t,height:a}),x=x[0].getContext("2d");for(var s="",c=0;a>c;c++){for(var f=0;t>f;f++)inRect(toCart(f+.5,c+.5,t,a),v,h,u)?(s+="..",x.fillStyle="white",x.fillRect(f,c,1,1)):(s+="XX",x.fillStyle="black",x.fillRect(f,c,1,1));a-1>c&&(s+="\n")}$("#o").val(s)}$(go)</script>
```
(JSFiddle Version)

The text representation has `XX` wherever there is a black pixel in the image and `..` wherever there is a white pixel. (It looks squished if they are `X` and `.`.)

Write a program that takes the text representation of a rectangle produced by the Snippet and outputs the approximate width and height of the rectangle, **both to within ± 7% of the actual width and height**.

Your program should work for effectively all possible rectangles that can be drawn by the snippet, with the constraints that:

* The rectangle width and height are 24 at minimum.
* The grid width and height are 26 at minimum.
* The rectangle never touches nor goes out of the grid bounds.

So the input rectangle may have any rotation, position, and dimensions, and the grid may have any dimensions, as long as the three constraints above are met. Note that except for the grid dimensions, the Snippet parameters can be floats.

### Details

* Take the raw text rectangle as input or take the filename of a file that contains the raw text rectangle (via stdin or command line). You may assume the text rectangle has a trailing newline.
* You may assume the text rectangle is made from any two distinct printable ASCII characters other than `X` and `.` if desired. (Newlines must stay newlines.)
* Output the measured width and height as integers or floats to stdout in any order (since there's no way to determine which one actually went with which parameter). Any format that clearly shows the two dimensions is fine, e.g. `D1 D2`, `D1,D2`, `D1\nD2`, `(D1, D2)`, etc.
* Instead of a program, you may write a function that takes the text rectangle as a string or the filename to it and prints the result normally or returns it as a string or list/tuple with two elements.
* Remember that `XX` or `..` is one 'pixel' of the rectangle, not two.

# Examples

### Ex. 1

Parameters: `grid w:60 grid h:34 w:40 h:24 x:0 y:0 θ:12` (Snippet defaults)

**Input**

```
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....XXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX........................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....................................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..........................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..........................................................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX....................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX........................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX....XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

```

**Example Outputs**

* `40 24`
* `24 40`
* `[40.0, 24.0]`
* `42.8, 25.68` (+7%)
* `37.2, 22.32` (-7%)

### Ex. 2

Parameters: `grid w:55 grid h:40 w:24.5 h:24 x:-10.1 y:2 θ:38.5`

**Input**

```
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX..................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX......................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX............................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..............................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX......................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXX..................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXX......................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX................................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXX............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX......................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX....................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXX................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX......................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..........................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX......................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX..........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

```

**Example Outputs**

* `24.0 24.5`
* `25.68 26.215` (+7%)
* `22.32 22.785` (-7%)

# Scoring

The shortest code in bytes wins. Tiebreaker is highest voted post.

# Answer
> 7 votes
# Matlab, 226 bytes

The idea is simple: First I try to find out how much the rectangle was turned, then turn the image accordingly such that the rectangle is upright. Then I just 'sum' up all the pixels in the row columns sperately and try count how many of the sums are above than average (simple thresholding) for determining the width and height. This simple method works surprisingly reliably.

*How can I detect the angle?*

I just try each step (one degree each) and sum along the columns and get a vector of sums. When the rectangle is upright, I should ideally get only two sudden changes in this vector of sums. If the square is on the tip, the changes are very gradual. So I just use the first derivative, and try to minimize the number of 'jumps'. Here you can see a plot of the criterion we are trying to minimize. Notice that you can see the four minima which corresponds to the fours possible upright orientations.

Further thoughts: I am not sure how much it could be golfed as the exhausive angle search takes a lot of characters and I doubt you could achieve that so well with built in optimization methods, because as you can see there are a lot of local minima that we are not looking for. You can easily improve the accuracy (for big pictures) by choosing a smaller step size for the angle and only search 90° instead of 360° so you could replace `0:360` with `0:.1:90` or somehting like that. But anyways, for me the challenge was more finding a robust algorithm rather than golfing and I am sure the entries of the golfing languages will leave my submission far behind=)

PS: Someone should really derive a golfing language from Matlab/Octave.

### Outputs

Example 1:

```
 25    39

```

Example 2:

```
 25    24

```

### Code

Golfed:

```
s=input('');r=sum(s=='n');S=reshape(s',nnz(s)/r,r)';S=S(:,1:2:end-2)=='.';m=Inf;a=0;for d=0:360;v=sum(1-~diff(sum(imrotate(S,d))));if v<m;m=v;a=d;end;end;S=imrotate(S,a);x=sum(S);y=sum(S');disp([sum(x>mean(x)),sum(y>mean(y))])

```

Ungolfed:

```
s=input('');
r=sum(s=='n');
S=reshape(s',nnz(s)/r,r)';
S=S(:,1:2:end-2)=='.';
m=Inf;a=0;
for d=0:360;
    v=sum(1-~diff(sum(imrotate(S,d))));
    if v<m;
        m=v;a=d;
    end;
end;
S=imrotate(S,a);
x=sum(S);y=sum(S');
disp([sum(x>mean(x)),sum(y>mean(y))])

```

# Answer
> 7 votes
# CJam, ~~68 65~~ 64 bytes

This *can* be golfed a little more..

```
qN/2f%{{:QN*'.#Qz,)mdQ2$>2<".X"f#_~>@@0=?Qz}2*;@@-@@-mhSQWf%}2*;

```

**How it works**

The logic is pretty simple, if you think about it.

All we need from the input `X.` combinations is 3 coordinates of two adjacent sides. Here is how we get them:

### `First`

In any orientation of the rectangle, the first `.` in the whole of the input is going to be one of the corners. For example..

```
XXXXXXXXXXXXXX
XXXXXXX...XXXX
XXXX.......XXX
X............X
XX.........XXX
XXXX...XXXXXXX
XXXXXXXXXXXXXX

```

Here, the first `.` is in the 2nd line, 8th column.

But that's not it, we have to do some adjustment and add the width of the `.` run on that line to the coordinates to get the coordinate of the right end.

### `Second`

If we transpose the above rectangle (pivoted on newlines), then the bottom left corner takes the above step's place. But here, we do not compensate for the `.` run length as we would have wished to get the bottom left coordinate of the edge anyways (which in transposed form will still be the first encountered `.`)

### `Rest two`

For rest two coordinates, we simply flip horizontally, the rectangle and perform the above two steps. One of the corners here will be common from the first two.

After getting all 4, we simply do some simple math to get the distances.

Now this is not the most accurate method, but it works well within the error margin and well for all possible orientations of the rectangle.

**Code expansion** (bit outdated)

```
qN/2f%{{:QN*'.#Q0=,)md}:A~1$Q='.e=+QzA@@-@@-mhSQWf%}2*;
qN/2f%                               e# Read the input, split on newlines and squish it
      {   ...   }2*                  e# Run the code block two times, one for each side
{:QN*'.#Q0=,)md}:A~                  e# Store the code block in variable A and execute it
 :QN*                                e# Store the rows in Q variable and join by newlines
     '.#                             e# Get the location of the first '.'
        Q0=,)                        e# Get length + 1 of the first row
             md                      e# Take in X and Y and leave out X/Y and X%Y on stack
1$Q=                                 e# Get the row in which the first '.' appeared
    '.e=+                            e# Get number of '.' in that row and add it to X%Y
         QzA                         e# Transpose the rows and apply function A to get
                                     e# the second coordinate
            @@-@@-                   e# Subtract resp. x and y coordinates of the two corners
                  mh                 e# Calculate (diff_x**2 + diff_y**2)**0.5 to get 1 side
                    SQWF%            e# Put a space on stack and put the horizontally flipped
                                     e# version of the rows/rectangle all ready for next two
                                     e# coordinates and thus, the second side

```

Try it online here

# Answer
> 5 votes
# Python 3, ~~347~~ 337 bytes

This turned out harder than I expected. Work in progress...

```
def f(s):
 l=s.split('\n');r=range;v=sorted;w=len(l[0]);h=len(l);p=[[x,y]for x in r(w)for y in r(h)if'X'>l[y][x]];x,y=[sum(k)/w/h for k in zip(*p)];g=[[x/2,y]];d=lambda a:((a[0]/2-a[2]/2)**2+(a[1]-a[3])**2)**.5
 for i in r(3):g+=v(p,key=lambda c:~-(c in g)*sum(d(j+c)for j in g))[:1]
 print(v(map(d,[g[1]+g[2],g[2]+g[3],g[1]+g[3]]))[:2])

```

Try it online! Comes with a test harness that tries 100 random valid rectangles. **Note:** The test harness seems to produce some errors and prints the corresponding grids. It seems like these cases all have rather round corners - an issue which seems to be caused by the grid generation code, which I translated from the original snippet.

Defines a function `f` taking the string as an argument and printing the result to STDOUT.

# Pyth, ~~87~~ ~~84~~ ~~82~~ ~~81~~ ~~75~~ ~~72~~ ~~71~~ bytes (broken)

```
Km%2d.zJf<@@KeThTG*UhKUKPSm.adfqlT2ytu+G]ho*t}NGsm.a,kNGJ3]mccsklhKlKCJ

```

This seems to have been broken in 2015. Since then, something in Pyth has changed so that the old versions now crash and the new ones return `[0, 0]`. Right now I have neither the slightest idea what this monstrosity does nor the time to figure it out. I'm leaving it here as crossed-out for historical reasons.

~~~~Way~~ Still too long. Basically a port of the previous. Loving Pyth's `.a` Euclidean distance. Takes input via STDIN and gives output via STDOUT. Expects the non-rectangle character to be lower-case `x` (well, anything with ASCII value 98 or more).~~

## Algorithm

Both of these use the same algorithm. I basically start with an array containing the center of mass of the rectangle area. I then add three points to the array of all points in the rectangle, always choosing the one with maximum *sum of distances* to the points already in the array. The result is always three points in different corners of the rectangle. I then just calculate all the three distances between those three points and take the two shortest ones.

# Answer
> 0 votes
# Python 2, 342 bytes

```
import sys
r=[]
h=.0
for l in sys.stdin:w=len(l);r+=[[x*.5,h]for x in range(0,w,2)if l[x:x+2]=='..'];h+=1
x,y=.0,.0
for p in r:x+=p[0];y+=p[1]
n=len(r)
x/=n
y/=n
m=.0
for p in r:
 p[0]-=x;p[1]-=y;d=p[0]**2+p[1]**2
 if d>m:m=d;u,v=p
m=.0
for p in r:
 d=p[0]*v-p[1]*u
 if d>m:m=d;s,t=p
print ((u-s)**2+(v-t)**2)**.5+1,((u+s)**2+(v+t)**2)**.5+1

```

This took inspiration from @Pietu1998's algorithm. It takes the idea of determining one corner as the point farthest from the center, but differs from there:

* I determine the second corner as the point with the largest cross product with the vector from center to first corner. This gives the point with the largest distance from the line from center to first corner.
* There's no need to search for a third corner, since it's just the mirror image of the second corner relative to the center.

So the code follows this sequence:

* First loop is over the lines in the input, and builds a list `r` of rectangle points.
* Second loop calculates the average of all rectangle points, giving the center of the rectangle.
* Third loop finds the point farthest from the center. This is the first corner. At the same time, it subtracts the center from the points in the list, so that the point coordinates are relative to the center for the remaining calculation.
* Fourth loop finds the point with the largest cross product with the vector to the first corner. This is the second corner.
* Prints out the distance between first corner and second corner, and distance between first corner and mirror image of second corner.
* `1.0` is added to the distances because the original distance calculations use pixel indices. For example, if you have 5 pixels, the difference between the index of the last and first pixel was only 4, which needs compensation in the final result.

Precision is quite good. For the two examples:

```
$ cat rect1.txt | python Golf.py
24.5372045919 39.8329756779
$ cat rect2.txt | python Golf.py
23.803508502 24.5095563412

```

# Answer
> 0 votes
# Python 2, 272 bytes

Posting this as a separate answer since it's an entirely different algorithm than my previous one:

```
import sys,math
y,a,r=0,0,0
l,t=[1<<99]*2
for s in sys.stdin:
 c=s.count('..')
 if c:a+=c;x=s.find('.')/2;l=min(l,x);r=max(r,x+c);t=min(t,y);b=y+1
 y+=1
r-=l
b-=t
p=.0
w,h=r,b
while w*h>a:c=math.cos(p);s=math.sin(p);d=c*c-s*s;w=(r*c-b*s)/d;h=(b*c-r*s)/d;p+=.001
print w,h

```

This approach does not identify corners at all. It is based on the observation that the size (width and height) of the bounding box and the area of the rotated rectangle are sufficient to determine the width and height of the rectangle.

If you look at a sketch, it is fairly easy to calculate the width (`wb`) and height (`hb`) of the bounding box with `w`/`h` the size of the rectangle, and `p` the rotation angle:

```
wb = w * cos(p) + h * sin(p)
hb = w * sin(p) + h * cos(p)

```

`wb` and `hb` can be extracted directly from the image. We can also quickly extract the total area `a` of the rectangle by counting the number of `..` pixels. Since we're dealing with a rectangle, this gives us the additional equation:

```
a = w * h

```

So we have 3 equations with 3 unknowns (`w`, `h` and `p`), which is enough to determine the unknowns. The only bummer is that the equations contain trigonometric functions, and at least with my patience and math skills the system cannot easily be solved analytically.

What I implemented is a brute force search for the angle `p`. Once `p` is given, the first two equations above become a system of two linear equations, which can be resolved for `w` and `h`:

```
w = (wb * cos(p) - hb * sin(p)) / (cos(p) * cos(p) - sin(p) * sin(p))
h = (hb * cos(p) - wb * sin(p)) / (cos(p) * cos(p) - sin(p) * sin(p))

```

With these values, we can then compare `w * h` with the measured area of the rectangle. The two values would ideally be equal at some point. This is of course not going to happen in floating point math.

The value of `w * h` decreases as the angle increases. So we start at angle 0.0, and then increment the angle by small steps until the first time `w * h` is less than the measured area.

The code only has two main steps:

1. Extract size of bounding box and rectangle area from input.
2. Loop over candidate angles until termination criterion is reached.

The precision of the output is good for rectangles where the width and height are significantly different. It gets somewhat iffy with rectangles that are almost square and rotated close to 45 degrees, just barely clearing the 7% error hurdle for test example 2.

The bitmap for example 2 actually looks slightly odd. The left corner looks suspiciously dull. If I add one more pixel at the left corner, it both looks better (to me), and gives a lot better precision for this algorithm.

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


title: ASCII Art of the Day #2 - Flow Snakes

text:
# Question
Title: ASCII Art of the Day #2 - Flow Snakes
A Flow Snake, also known as a Gosper curve, is a fractal curve, growing exponentially in size with each order/iteration of a simple process. Below are the details about the construction and a few examples for various orders:

*Order 1 Flow Snake*:

```
____
\__ \
__/

```

*Order 2 Flow Snake*:

```
      ____
 ____ \__ \
 \__ \__/ / __
 __/ ____ \ \ \
/ __ \__ \ \/
\ \ \__/ / __
 \/ ____ \/ /
    \__ \__/
    __/

```

*Order 3 Flow Snake*:

```
                 ____
            ____ \__ \
            \__ \__/ / __
            __/ ____ \ \ \    ____
           / __ \__ \ \/ / __ \__ \
      ____ \ \ \__/ / __ \/ / __/ / __
 ____ \__ \ \/ ____ \/ / __/ / __ \ \ \
 \__ \__/ / __ \__ \__/ / __ \ \ \ \/
 __/ ____ \ \ \__/ ____ \ \ \ \/ / __
/ __ \__ \ \/ ____ \__ \ \/ / __ \/ /
\ \ \__/ / __ \__ \__/ / __ \ \ \__/
 \/ ____ \/ / __/ ____ \ \ \ \/ ____
    \__ \__/ / __ \__ \ \/ / __ \__ \
    __/ ____ \ \ \__/ / __ \/ / __/ / __
   / __ \__ \ \/ ____ \/ / __/ / __ \/ /
   \/ / __/ / __ \__ \__/ / __ \/ / __/
   __/ / __ \ \ \__/ ____ \ \ \__/ / __
  / __ \ \ \ \/ ____ \__ \ \/ ____ \/ /
  \ \ \ \/ / __ \__ \__/ / __ \__ \__/
   \/ / __ \/ / __/ ____ \ \ \__/
      \ \ \__/ / __ \__ \ \/
       \/      \ \ \__/ / __
                \/ ____ \/ /
                   \__ \__/
                   __/

```

# Construction

Consider the order 1 Flow Snake to be built of a path containing 7 edges and 8 vertices (labelled below. Enlarged for feasibility):

```
4____5____6
 \         \
 3\____2   7\
       /
0____1/

```

Now for each next order, you simply replace the edges with a rotated version of this original order 1 pattern. Use the following 3 rules for replacing the edges:

**1** For a horizontal edge, replace it with the original shape as is:

```
________
\       \
 \____   \
     /
____/

```

**2** For a `/` edge (`12` in the above construction), replace it with the following rotated version:

```
 /
/   ____
\  /   /
 \/   /
     /
____/

```

**3** For a `\` edge (`34`and `67` above), replace it with the following rotated version:

```
 /
/   ____
\   \   \
 \   \   \
  \  /
   \/

```

So for example, order 2 with vertices from order 1 labelled will look like

```
            ________
            \       \
  ________   \____   \6
  \       \      /   /
   \____   \5___/   /   ____
       /            \   \   \
  4___/   ________   \   \   \7
 /        \       \   \  /
/   ____   \____   \2  \/
\   \   \      /   /
 \   \   \3___/   /   ____
  \  /            \  /   /
   \/   ________   \/   /
        \       \      /
         \____   \1___/
             /
        0___/

```

Now for any higher order, you simply break up the current level into edges of lengths 1 `/`, 1 `\` or 2 `_` and repeat the process. Do note that even after replacing, the common vertices between any two consecutive edges are still coinciding.

# Challenge

* You have to write a function of a full program that receives a single integer `N` via STDIN/ARGV/function argument or the closest equivalent and prints the order `N` Flow Snake on STDOUT.
* The input integer is always greater than `0`.
* There should not be any leading spaces which are not part of the pattern.
* There should be either no trailing spaces or enough trailing spaces to pad the pattern to fill the minimum bounding rectangle completely.
* Trailing newline is optional.

# Fun Facts

* Flow Snakes is a word play of Snow Flakes, which this pattern resembles for order 2 and above
* The Flow and Snakes actually play a part in the pattern as the pattern is made up of a single path flowing throughout.
* If you notice carefully, the order 2 (and higher as well) pattern comprises of rotations of order 1 pattern pivoted on the common vertex of the current and the previous edge.
* There is a Non ASCII variant of Flow Snakes which can be found here and at several other locations.

This is so shortest code in bytes win!

---

# Leaderboard

**The first post of the series generates a leaderboard.**

To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

# Answer
> 4 votes
# CJam, 144 bytes

```
0_]0a{{_[0X3Y0_5]f+W@#%~}%}ri*{_[YXW0WW]3/If=WI6%2>#f*.+}fI]2ew{$_0=\1f=~-
"__1a /L \2,"S/=(@\+\~.+}%_2f<_:.e>\:.e<:M.-:)~S*a*\{M.-~3$3$=\tt}/zN*

```

Newline added to avoid scrolling. Try it online

The program works in several steps:

1. The initial fractal (order 1) is encoded as a sequence of 7 angles (conceptually, multiples of 60°) representing the direction of movement
2. The fractal is "applied" to a horizontal segment (order 0 fractal) N times to generate all the "movements" in the order N fractal
3. Starting from \[0 0\], the movements are translated into a sequence of points with \[x y\] coordinates
4. Each segment (pair of points) is converted to 1 or 2 \[x y c\] triplets, representing the character c at coordinates x, y
5. The bounding rectangle is determined, the coordinates are adjusted and a matrix of spaces is generated
6. For each triplet, the character c is placed at position x, y in the matrix, and the final matrix is adjusted for output

# Answer
> 16 votes
# Python 2, ~~428~~ ~~411~~ 388 bytes

This one was pretty tricky. The patterns don't retain their ratios after each step meaning its very difficult to procedurally produce an image from its predecessor. What this code does, though its pretty unreadable after some intense math golfing, is actually draw the line from start to finish using the recursively defined `D` function.

The size was also an issue, and I ended up just starting in the middle of a `5*3**n` sided square and cropping things afterward, though if I can think of better way to calculate the size I might change it.

```
n=input();s=5*3**n
r=[s*[" "]for i in[0]*s]
def D(n,x,y,t=0):
 if n<1:
    x-=t%2<1;y+=t%3>1;r[y][x]='_/\\'[t/2]
    if t<2:r[y][x+2*t-1]='_'
    return[-1,2,0,1,0,1][t]+x,y-(2<t<5)
 for c in[int(i)^t%2for i in"424050035512124224003"[t/2::3]][::(t^1)-t]:x,y=D(n-1,x,y,c)
 return x,y
D(n,s/2,s/2)
S=[''.join(c).rstrip()for c in r]
for l in[c[min(c.find('\\')%s for c in S):]for c in S if c]:print l

```

# Answer
> 12 votes
# JavaScript (*ES6*), 356 ~~362 370~~

That's a difficult one ...

Each shape is stored as a path. There are 6 basic building blocks (3 + 3 backward)

* `0` diagonal up left to bottom right (`4` backward)
* `1` diagonal bottom left to up right (`5` backward)
* `2` horizontal left to right (`6` backward)

For each one, there is a replacing step to be applied when increasing order:

* `0` --\> `0645001` (backward `4` --\> `5441024`)
* `1` --\> `2116501` (backward `5` --\> `5412556`)
* `2` --\> `2160224` (backward `6` --\> `0664256`)

values prefilled in the`h` array, even if the elements 4..6 can be obtained from 0..2 using

```
;[...h[n]].reverse().map(x=>x^4).join('')

```

To obtain the shape for the given order, the path is built in the p variable applying the substitutions repeatedly. Then the main loop iterates on the p variable and draw the shape inside the g\[\] array, where each element is a row.
Starting at position (0,0), each index can become negative (y index at high orders). I avoid negative y indexes shifting all the g array whenever I find a negative y value. I don't care if the x index becomes negative, as in JS negative indexes are allowed, just a little more difficult to manage.
In the last step, I scan the main array using .map, but for each row I need to use an explicit for(;;) loop using the `b` variable that holds the least x index reached (that will be \< 0).
In the `console.log` version there is a handy leading newline, that can be easily made a trailing newline swapping 2 rows, as in the snippet version.

```
f=o=>{
  g=[],x=y=b=0,
  h='064500192116501921602249954410249541255690664256'.split(9);
  for(p=h[2];--o;)p=p.replace(/./g,c=>h[c]);
  for(t of p)
    z='\\/_'[s=t&3],
    d=s-(s<1),
    t>3&&(x-=d,y+=s<2),
    y<0&&(y++,g=[,...g]),r=g[y]=g[y]||[],
    s?s>1?r[x]=r[x+1]=z:r[x]=z:r[x-1]=z,
    t<3&&(x+=d,y-=s<2),
    x<b?b=x:0;
  g.map(r=>
  {
    o+='\n';
    for(x=b;x<r.length;)o+=r[x++]||' '
  },o='');
  console.log(o)
}

```

Handy snippet to test (in Firefox) :

```
f=o=>{
  g=[],x=y=b=0,
  h='064500192116501921602249954410249541255690664256'.split(9);
  for(p=h[2];--o;)p=p.replace(/./g,c=>h[c]);
  for(t of p)
    z='\\/_'[s=t&3],
    d=s-(s<1),
    t>3&&(x-=d,y+=s<2),
    y<0&&(y++,g=[,...g]),r=g[y]=g[y]||[],
    s?s>1?r[x]=r[x+1]=z:r[x]=z:r[x-1]=z,
    t<3&&(x+=d,y-=s<2),
    x<b?b=x:0;
  g.map(r=>
  {
    for(x=b;x<r.length;)o+=r[x++]||' ';
    o+='\n'
  },o='');
  return o
}

// TEST

fs=9;
O.style.fontSize=fs+'px'

function zoom(d) {
  d += fs;
  if (d > 1 && d < 40)
    fs=d, O.style.fontSize=d+'px'
}
```

```
#O {
  font-size: 9px;
  line-height: 1em;
}
```

```
<input id=I value=3><button onclick='O.innerHTML=f(I.value)'>-></button>
<button onclick="zoom(2)">Zoom +</button><button onclick="zoom(-2)">Zoom -</button>
<br>
<pre id=O></pre>
```

# Answer
> 6 votes
# Haskell, 265 bytes

```
(?)=div
(%)=mod
t[a,b]=[3*a+b,2*b-a]
_#[0,0]=0
0#_=3
n#p=[352,6497,2466,-1]!!((n-1)#t[(s+3)?7|s<-p])?(4^p!!0%7)%4
0&_=0
n&p=(n-1)&t p+maximum(abs<$>sum p:p)
n!b=n&[1,-b]
f n=putStr$unlines[["__ \\/   "!!(2*n#t[a?2,-b]+a%2)|a<-[b-n!2+1..b+n!2+0^n?3]]|b<-[-n!0..n!0]]

```

(Note: on GHC before 7.10, you will need to add `import Control.Applicative` or replace `abs<$>` with `map abs$`.)

Run online at Ideone.com

`f n :: Int -> IO ()` draws the level `n` flowsnake. The drawing is computed in bitmap order rather than along the curve, which allows the algorithm to run in O(n) space (that is, logarithmic in the drawing size). Nearly half of my bytes are spent computing which rectangle to draw!

# Answer
> 5 votes
# Perl, ~~334 316~~ 309

```
$_=2;eval's/./(map{($_,"\1"x7^reverse)}2003140,2034225,4351440)[$&]/ge;'x($s=<>);
s/2|3/$&$&/g;$x=$y=3**$s-1;s!.!'$r{'.qw($y--,$x++ ++$y,--$x $y,$x++ $y,--$x
$y--,--$x ++$y,$x++)[$&]."}=$&+1"!eeg;y!1-6!//__\\!,s/^$x//,s/ *$/
/,print for
grep{/^ */;$x&=$&;$'}map{/^/;$x=join'',map$r{$',$_}||$",@f}@f=0..3**$s*2

```

Parameter taken on the standard input. Test me.

# Answer
> 5 votes
# Haskell, ~~469~~ ~~419~~ ~~390~~ ~~385~~ 365 bytes

the function f::Int-\>IO() takes an integer as input and print the flow snake

```
e 0=[0,0];e 5=[5,5];e x=[x]
f n=putStr.t$e=<<g n[0]
k=map$(53-).fromEnum
g 0=id
g n=g(n-1).(=<<)(k.(words"5402553 5440124 1334253 2031224 1345110 2003510"!!))
x=s$k"444666555666"
y=s$k"564645554545"
r l=[minimum l..maximum l]
s _[]=[];s w(x:y)=w!!(x+6):map(+w!!x)(s w y)
t w=unlines[["_/\\\\/_ "!!(last$6:[z|(c,d,z)<-zip3(x w)(y w)w,c==i&&d==j])|i<-r.x$w]|j<-r.y$w]

```

# Answer
> 4 votes
# Python 2, ~~523~~ ~~502~~ ~~475~~ ~~473~~ ~~467~~ ~~450~~ 437 bytes

```
l=[0]
for _ in l*input():l=sum([map(int,'004545112323312312531204045045050445212331'[t::6])for t in l],[])
p=[]
x=y=q=w=Q=W=0
for t in l:T=t|4==5;c=t in{2,4};C=t<3;q=min(q,x);Q=max(Q,x+C);w=min(w,y);W=max(W,y);a=C*2-1;a*=2-(t%3!=0);b=(1-T&c,-1)[T&1-c];x+=(a,0)[C];y+=(0,b)[c];p+=[(x,y)];x+=(0,a)[C];y+=(b,0)[c]
s=[[' ']*(Q-q)for _ in[0]*(W-w+1)]
for t,(x,y)in zip(l,p):x-=q;s[y-w][x:x+1+(t%3<1)]='_/\_'[t%3::3]
for S in s:print''.join(S)

```

Pffft, costed me a like 3 hours, but was fun to do!

The idea is to split the task in multiple steps:

1. Calculate all the edges (encoded as 0-5) in order of appearence (so from the beginning of the snake to the end)
2. Calculate the position for each of the edges (and save the min and max values for x and y)
3. Build the strings it consists of (and use the min values to offset, so that we don't get negative indices)
4. Print the strings

Here is the code in ungolfed form:

```
# The input
n = int(input())

# The idea:
# Use a series of types (_, /, \, %), and positions (x, y)
# Forwards:   0: __  1: /  2: \
# Backwards:  3: __  4: /  5: \

# The parts
pieces = [
    "0135002",
    "0113451",
    "4221502",
    "5332043",
    "4210443",
    "5324551"
]
# The final types list
types = [0]
for _ in range(n):
    old = types
    types = []
    for t in old:
        types.extend(map(int,pieces[t]))

# Calculate the list of positions (and store the mins and max')
pos = []
top = False
x = 0
y = 0
minX = 0
minY = 0
maxX = 0
maxY = 0
for t in types:
    # Calculate dx
    dx = 1 if t < 3 else -1
    if t%3==0:
        dx *= 2         # If it's an underscore, double the horizontal size
    # Calculate dy
    top = t in {1, 5}
    dy = 0
    if top and t in {0, 3, 1, 5}:
        dy = -1
    if not top and t in {2, 4}:
        dy = 1
    # If backwards, add dx before adding the position to the list
    if t>2:
        x += dx
    # If top to bottom, add dy before adding the position to the list
    if t in {2,4}:
        y += dy
    # Add the current position to the list
    pos += [(x, y)]
    # In the normal cases (going forward and up) modify the x and y after changing the position
    if t<3:
        x += dx
    if t not in {2, 4}:
        y += dy
    # Store the max and min vars
    minX = min(minX, x)
    maxX = max(maxX, x + (t<3)) # For forward chars, add one to the length (we never end with __'s)
    minY = min(minY, y)
    maxY = max(maxY, y)

# Create the string (a grid of charachters)
s = [[' '] * (maxX - minX) for _ in range(maxY - minY + 1)]
for k, (x, y) in enumerate(pos):
    x -= minX
    y -= minY
    t = types[k]
    char = '/'
    if t % 3 == 0:
        char = '__'
    if t % 3 == 2:
        char = '\\'
    s[y][x : x + len(char)] = char

# Print the string
for printString in s:
    print("".join(printString))

```

**Edit:** I changed the language to python 2, to be compatible with my answer for #3 (and it also saves 6 more bytes)

# Answer
> 4 votes
# C, ~~479~~ ~~474~~ ~~468~~ 427 bytes

There's no beating the Perl and Haskell guys I guess, but since there's no C submission here yet:

```
#define C char
C *q="053400121154012150223433102343124450553245";X,Y,K,L,M,N,i,c,x,y,o;F(C*p,
int l,C d){if(d){l*=7;C s[l];for(i=0;i<l;i++)s[i]=q[(p[i/7]%8)*7+i%7];return F
(s,l,d-1);}x=0;y=0;o=32;while(l--){c=*p++%8;for(i=!(c%3)+1;i--;) {K=x<K?x:K;L=
y<L?y:L;M=x>M?x:M;N=y>N?y:N;y+=c&&c<3;x-=c%5>1;if(x==X&y==Y)o="_\\/"[c%3];y-=c
>3;x+=c%5<2;}}return X<M?o:10;}main(l){F(q,7,l);for(Y=L;Y<N;Y++)for(X=K;X<=M;X
++)putchar(F(q,7,l));}

```

To save space on a atoi() call, the *number* of arguments passed to the program is used for the level.

The program runs in O(n^3) or worse; first the path is calculated once to find the min/max coordinates, then for each (x,y) pair it is calculated once to find the character on that specific location. Terribly slow, but saves on memory administration.

Example run at http://codepad.org/ZGc648Xi

# Answer
> 1 votes
# Pari/GP, 395

Looping over x,y character positions and calculating what char to print. Moderate attempts at minimizing, scored with whitespace and comments stripped.

```
k=3;
{
  S = quadgen(-12);  \\ sqrt(-3)
  w = (1 + S)/2;     \\ sixth root of unity
  b = 2 + w;         \\ base

  \\ base b low digit position under 2*Re+4*Im mod 7 index
  P = [0, w^2, 1, w, w^4, w^3, w^5];
  \\ rotation state table
  T = 7*[0,0,1,0,0,1,2, 1,2,1,0,1,1,2, 2,2,2,0,0,1,2];
  C = ["_","_",  " ","\\",  "/"," "];

  \\ extents
  X = 2*sum(i=0,k-1, vecmax(real(b^i*P)));
  Y = 2*sum(i=0,k-1, vecmax(imag(b^i*P)));

  for(y = -Y, Y,
     for(x = -X+!!k, X+(k<3),  \\ adjusted when endpoint is X limit
        z = (x- (o = (x+y)%2) - y*S)/2;
        v = vector(k,i,
                   z = (z - P[ d = (2*real(z) + 4*imag(z)) % 7 + 1 ])/b;
                   d);
        print1( C[if(z,3,
                     r = 0;
                     forstep(i=#v,1, -1, r = T[r+v[i]];);
                     r%5 + o + 1)]) );  \\ r=0,7,14 mod 5 is 0,2,4
     print())
}

```

Each char is the first or second of a hexagon cell. A cell location is a complex number z split into base b=2+w with digits 0, 1, w^2, ..., w^5, where w=e^(2pi/6) sixth root of unity. Those digits are kept just as a distinguishing 1 to 7 then taken high to low through a state table for net rotation. This is in the style of flowsnake code by Ed Shouten (`xytoi`) but only for net rotation, not making digits into an "N" index along the path. The extents are relative to an origin 0 at the centre of the shape. As long as the limit is not an endpoint these are the middle of a 2-character hexagon and only 1 of those chars is needed. But when the snake start and/or end are the X limit 2 chars are needed, which is k=0 start and k\<3 end. Pari has "quads" like sqrt(-3) builtin but the same can be done with real and imaginary parts separately.

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


title: Scale up a Diamond Tiling

text:
# Question
Title: Scale up a Diamond Tiling
Any regular hexagon can be tiled with diamonds, for instance like so:

```
   ______
  /_/_/\_\
 /_/\_\/\_\
/\_\/_/\/_/\
\/_/\_\/_/\/
 \_\/_/\_\/
  \_\_\/_/

```

We'll consider the above a tiling of size `1` (since the diamonds' sides are made of one `/` or `\` each). The same tiling of size `2` would look like:

```
      ____________
     /   /   /\   \
    /___/___/  \___\
   /   /\   \  /\   \
  /___/  \___\/  \___\
 /\   \  /   /\  /   /\
/  \___\/___/  \/___/  \
\  /   /\   \  /   /\  /
 \/___/  \___\/___/  \/
  \   \  /   /\   \  /
   \___\/___/  \___\/
    \   \   \  /   /
     \___\___\/___/

```

Your task is to receive such an ASCII art tiling (of size `1`) as input, along with a positive integer `N` (in decimal or unary), specifying the size of the desired output. You should then output a scaled-up version of the same tiling.

Note that the *hexagon* could be any size and as small as 1x1x1 (containing three diamonds).

Neither input nor output must contain any trailing spaces, nor more leading spaces than necessary to align the hexagon shape. Both input and output may optionally contain a single trailing newline (this choice does not have to be the same for input and output).

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

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

## Example Tilings

Here are a handful of input tilings you can use to test your submission.

```
 __
/_/\
\_\/

  ____
 /_/\_\
/\_\/_/\
\/_/\_\/
 \_\/_/

   ______
  /_/_/\_\
 /_/\_\/\_\
/\_\/_/\/_/\
\/_/\_\/_/\/
 \_\/_/\_\/
  \_\_\/_/

    ________
   /_/\_\_\_\
  /\_\/\_\_\_\
 /\/_/\/_/_/\_\
/\/\_\/_/_/\/\_\
\/\/_/\_\_\/\/_/
 \/\_\/_/\_\/_/
  \/\_\_\/_/_/
   \/_/_/_/_/

```

The following snippet contains the corresponding outputs for inputs `N = 1` through `N = 6`.

```
 __
/_/\
\_\/

  ____
 /   /\
/___/  \
\   \  /
 \___\/

   ______
  /     /\
 /     /  \
/_____/    \
\     \    /
 \     \  /
  \_____\/

    ________
   /       /\
  /       /  \
 /       /    \
/_______/      \
\       \      /
 \       \    /
  \       \  /
   \_______\/

     __________
    /         /\
   /         /  \
  /         /    \
 /         /      \
/_________/        \
\         \        /
 \         \      /
  \         \    /
   \         \  /
    \_________\/

      ____________
     /           /\
    /           /  \
   /           /    \
  /           /      \
 /           /        \
/___________/          \
\           \          /
 \           \        /
  \           \      /
   \           \    /
    \           \  /
     \___________\/

  ____
 /_/\_\
/\_\/_/\
\/_/\_\/
 \_\/_/

    ________
   /   /\   \
  /___/  \___\
 /\   \  /   /\
/  \___\/___/  \
\  /   /\   \  /
 \/___/  \___\/
  \   \  /   /
   \___\/___/

      ____________
     /     /\     \
    /     /  \     \
   /_____/    \_____\
  /\     \    /     /\
 /  \     \  /     /  \
/    \_____\/_____/    \
\    /     /\     \    /
 \  /     /  \     \  /
  \/_____/    \_____\/
   \     \    /     /
    \     \  /     /
     \_____\/_____/

        ________________
       /       /\       \
      /       /  \       \
     /       /    \       \
    /_______/      \_______\
   /\       \      /       /\
  /  \       \    /       /  \
 /    \       \  /       /    \
/      \_______\/_______/      \
\      /       /\       \      /
 \    /       /  \       \    /
  \  /       /    \       \  /
   \/_______/      \_______\/
    \       \      /       /
     \       \    /       /
      \       \  /       /
       \_______\/_______/

          ____________________
         /         /\         \
        /         /  \         \
       /         /    \         \
      /         /      \         \
     /_________/        \_________\
    /\         \        /         /\
   /  \         \      /         /  \
  /    \         \    /         /    \
 /      \         \  /         /      \
/        \_________\/_________/        \
\        /         /\         \        /
 \      /         /  \         \      /
  \    /         /    \         \    /
   \  /         /      \         \  /
    \/_________/        \_________\/
     \         \        /         /
      \         \      /         /
       \         \    /         /
        \         \  /         /
         \_________\/_________/

            ________________________
           /           /\           \
          /           /  \           \
         /           /    \           \
        /           /      \           \
       /           /        \           \
      /___________/          \___________\
     /\           \          /           /\
    /  \           \        /           /  \
   /    \           \      /           /    \
  /      \           \    /           /      \
 /        \           \  /           /        \
/          \___________\/___________/          \
\          /           /\           \          /
 \        /           /  \           \        /
  \      /           /    \           \      /
   \    /           /      \           \    /
    \  /           /        \           \  /
     \/___________/          \___________\/
      \           \          /           /
       \           \        /           /
        \           \      /           /
         \           \    /           /
          \           \  /           /
           \___________\/___________/

   ______
  /_/_/\_\
 /_/\_\/\_\
/\_\/_/\/_/\
\/_/\_\/_/\/
 \_\/_/\_\/
  \_\_\/_/

      ____________
     /   /   /\   \
    /___/___/  \___\
   /   /\   \  /\   \
  /___/  \___\/  \___\
 /\   \  /   /\  /   /\
/  \___\/___/  \/___/  \
\  /   /\   \  /   /\  /
 \/___/  \___\/___/  \/
  \   \  /   /\   \  /
   \___\/___/  \___\/
    \   \   \  /   /
     \___\___\/___/

         __________________
        /     /     /\     \
       /     /     /  \     \
      /_____/_____/    \_____\
     /     /\     \    /\     \
    /     /  \     \  /  \     \
   /_____/    \_____\/    \_____\
  /\     \    /     /\    /     /\
 /  \     \  /     /  \  /     /  \
/    \_____\/_____/    \/_____/    \
\    /     /\     \    /     /\    /
 \  /     /  \     \  /     /  \  /
  \/_____/    \_____\/_____/    \/
   \     \    /     /\     \    /
    \     \  /     /  \     \  /
     \_____\/_____/    \_____\/
      \     \     \    /     /
       \     \     \  /     /
        \_____\_____\/_____/

            ________________________
           /       /       /\       \
          /       /       /  \       \
         /       /       /    \       \
        /_______/_______/      \_______\
       /       /\       \      /\       \
      /       /  \       \    /  \       \
     /       /    \       \  /    \       \
    /_______/      \_______\/      \_______\
   /\       \      /       /\      /       /\
  /  \       \    /       /  \    /       /  \
 /    \       \  /       /    \  /       /    \
/      \_______\/_______/      \/_______/      \
\      /       /\       \      /       /\      /
 \    /       /  \       \    /       /  \    /
  \  /       /    \       \  /       /    \  /
   \/_______/      \_______\/_______/      \/
    \       \      /       /\       \      /
     \       \    /       /  \       \    /
      \       \  /       /    \       \  /
       \_______\/_______/      \_______\/
        \       \       \      /       /
         \       \       \    /       /
          \       \       \  /       /
           \_______\_______\/_______/

               ______________________________
              /         /         /\         \
             /         /         /  \         \
            /         /         /    \         \
           /         /         /      \         \
          /_________/_________/        \_________\
         /         /\         \        /\         \
        /         /  \         \      /  \         \
       /         /    \         \    /    \         \
      /         /      \         \  /      \         \
     /_________/        \_________\/        \_________\
    /\         \        /         /\        /         /\
   /  \         \      /         /  \      /         /  \
  /    \         \    /         /    \    /         /    \
 /      \         \  /         /      \  /         /      \
/        \_________\/_________/        \/_________/        \
\        /         /\         \        /         /\        /
 \      /         /  \         \      /         /  \      /
  \    /         /    \         \    /         /    \    /
   \  /         /      \         \  /         /      \  /
    \/_________/        \_________\/_________/        \/
     \         \        /         /\         \        /
      \         \      /         /  \         \      /
       \         \    /         /    \         \    /
        \         \  /         /      \         \  /
         \_________\/_________/        \_________\/
          \         \         \        /         /
           \         \         \      /         /
            \         \         \    /         /
             \         \         \  /         /
              \_________\_________\/_________/

                  ____________________________________
                 /           /           /\           \
                /           /           /  \           \
               /           /           /    \           \
              /           /           /      \           \
             /           /           /        \           \
            /___________/___________/          \___________\
           /           /\           \          /\           \
          /           /  \           \        /  \           \
         /           /    \           \      /    \           \
        /           /      \           \    /      \           \
       /           /        \           \  /        \           \
      /___________/          \___________\/          \___________\
     /\           \          /           /\          /           /\
    /  \           \        /           /  \        /           /  \
   /    \           \      /           /    \      /           /    \
  /      \           \    /           /      \    /           /      \
 /        \           \  /           /        \  /           /        \
/          \___________\/___________/          \/___________/          \
\          /           /\           \          /           /\          /
 \        /           /  \           \        /           /  \        /
  \      /           /    \           \      /           /    \      /
   \    /           /      \           \    /           /      \    /
    \  /           /        \           \  /           /        \  /
     \/___________/          \___________\/___________/          \/
      \           \          /           /\           \          /
       \           \        /           /  \           \        /
        \           \      /           /    \           \      /
         \           \    /           /      \           \    /
          \           \  /           /        \           \  /
           \___________\/___________/          \___________\/
            \           \           \          /           /
             \           \           \        /           /
              \           \           \      /           /
               \           \           \    /           /
                \           \           \  /           /
                 \___________\___________\/___________/

    ________
   /_/\_\_\_\
  /\_\/\_\_\_\
 /\/_/\/_/_/\_\
/\/\_\/_/_/\/\_\
\/\/_/\_\_\/\/_/
 \/\_\/_/\_\/_/
  \/\_\_\/_/_/
   \/_/_/_/_/

        ________________
       /   /\   \   \   \
      /___/  \___\___\___\
     /\   \  /\   \   \   \
    /  \___\/  \___\___\___\
   /\  /   /\  /   /   /\   \
  /  \/___/  \/___/___/  \___\
 /\  /\   \  /   /   /\  /\   \
/  \/  \___\/___/___/  \/  \___\
\  /\  /   /\   \   \  /\  /   /
 \/  \/___/  \___\___\/  \/___/
  \  /\   \  /   /\   \  /   /
   \/  \___\/___/  \___\/___/
    \  /\   \   \  /   /   /
     \/  \___\___\/___/___/
      \  /   /   /   /   /
       \/___/___/___/___/

            ________________________
           /     /\     \     \     \
          /     /  \     \     \     \
         /_____/    \_____\_____\_____\
        /\     \    /\     \     \     \
       /  \     \  /  \     \     \     \
      /    \_____\/    \_____\_____\_____\
     /\    /     /\    /     /     /\     \
    /  \  /     /  \  /     /     /  \     \
   /    \/_____/    \/_____/_____/    \_____\
  /\    /\     \    /     /     /\    /\     \
 /  \  /  \     \  /     /     /  \  /  \     \
/    \/    \_____\/_____/_____/    \/    \_____\
\    /\    /     /\     \     \    /\    /     /
 \  /  \  /     /  \     \     \  /  \  /     /
  \/    \/_____/    \_____\_____\/    \/_____/
   \    /\     \    /     /\     \    /     /
    \  /  \     \  /     /  \     \  /     /
     \/    \_____\/_____/    \_____\/_____/
      \    /\     \     \    /     /     /
       \  /  \     \     \  /     /     /
        \/    \_____\_____\/_____/_____/
         \    /     /     /     /     /
          \  /     /     /     /     /
           \/_____/_____/_____/_____/

                ________________________________
               /       /\       \       \       \
              /       /  \       \       \       \
             /       /    \       \       \       \
            /_______/      \_______\_______\_______\
           /\       \      /\       \       \       \
          /  \       \    /  \       \       \       \
         /    \       \  /    \       \       \       \
        /      \_______\/      \_______\_______\_______\
       /\      /       /\      /       /       /\       \
      /  \    /       /  \    /       /       /  \       \
     /    \  /       /    \  /       /       /    \       \
    /      \/_______/      \/_______/_______/      \_______\
   /\      /\       \      /       /       /\      /\       \
  /  \    /  \       \    /       /       /  \    /  \       \
 /    \  /    \       \  /       /       /    \  /    \       \
/      \/      \_______\/_______/_______/      \/      \_______\
\      /\      /       /\       \       \      /\      /       /
 \    /  \    /       /  \       \       \    /  \    /       /
  \  /    \  /       /    \       \       \  /    \  /       /
   \/      \/_______/      \_______\_______\/      \/_______/
    \      /\       \      /       /\       \      /       /
     \    /  \       \    /       /  \       \    /       /
      \  /    \       \  /       /    \       \  /       /
       \/      \_______\/_______/      \_______\/_______/
        \      /\       \       \      /       /       /
         \    /  \       \       \    /       /       /
          \  /    \       \       \  /       /       /
           \/      \_______\_______\/_______/_______/
            \      /       /       /       /       /
             \    /       /       /       /       /
              \  /       /       /       /       /
               \/_______/_______/_______/_______/

                    ________________________________________
                   /         /\         \         \         \
                  /         /  \         \         \         \
                 /         /    \         \         \         \
                /         /      \         \         \         \
               /_________/        \_________\_________\_________\
              /\         \        /\         \         \         \
             /  \         \      /  \         \         \         \
            /    \         \    /    \         \         \         \
           /      \         \  /      \         \         \         \
          /        \_________\/        \_________\_________\_________\
         /\        /         /\        /         /         /\         \
        /  \      /         /  \      /         /         /  \         \
       /    \    /         /    \    /         /         /    \         \
      /      \  /         /      \  /         /         /      \         \
     /        \/_________/        \/_________/_________/        \_________\
    /\        /\         \        /         /         /\        /\         \
   /  \      /  \         \      /         /         /  \      /  \         \
  /    \    /    \         \    /         /         /    \    /    \         \
 /      \  /      \         \  /         /         /      \  /      \         \
/        \/        \_________\/_________/_________/        \/        \_________\
\        /\        /         /\         \         \        /\        /         /
 \      /  \      /         /  \         \         \      /  \      /         /
  \    /    \    /         /    \         \         \    /    \    /         /
   \  /      \  /         /      \         \         \  /      \  /         /
    \/        \/_________/        \_________\_________\/        \/_________/
     \        /\         \        /         /\         \        /         /
      \      /  \         \      /         /  \         \      /         /
       \    /    \         \    /         /    \         \    /         /
        \  /      \         \  /         /      \         \  /         /
         \/        \_________\/_________/        \_________\/_________/
          \        /\         \         \        /         /         /
           \      /  \         \         \      /         /         /
            \    /    \         \         \    /         /         /
             \  /      \         \         \  /         /         /
              \/        \_________\_________\/_________/_________/
               \        /         /         /         /         /
                \      /         /         /         /         /
                 \    /         /         /         /         /
                  \  /         /         /         /         /
                   \/_________/_________/_________/_________/

                        ________________________________________________
                       /           /\           \           \           \
                      /           /  \           \           \           \
                     /           /    \           \           \           \
                    /           /      \           \           \           \
                   /           /        \           \           \           \
                  /___________/          \___________\___________\___________\
                 /\           \          /\           \           \           \
                /  \           \        /  \           \           \           \
               /    \           \      /    \           \           \           \
              /      \           \    /      \           \           \           \
             /        \           \  /        \           \           \           \
            /          \___________\/          \___________\___________\___________\
           /\          /           /\          /           /           /\           \
          /  \        /           /  \        /           /           /  \           \
         /    \      /           /    \      /           /           /    \           \
        /      \    /           /      \    /           /           /      \           \
       /        \  /           /        \  /           /           /        \           \
      /          \/___________/          \/___________/___________/          \___________\
     /\          /\           \          /           /           /\          /\           \
    /  \        /  \           \        /           /           /  \        /  \           \
   /    \      /    \           \      /           /           /    \      /    \           \
  /      \    /      \           \    /           /           /      \    /      \           \
 /        \  /        \           \  /           /           /        \  /        \           \
/          \/          \___________\/___________/___________/          \/          \___________\
\          /\          /           /\           \           \          /\          /           /
 \        /  \        /           /  \           \           \        /  \        /           /
  \      /    \      /           /    \           \           \      /    \      /           /
   \    /      \    /           /      \           \           \    /      \    /           /
    \  /        \  /           /        \           \           \  /        \  /           /
     \/          \/___________/          \___________\___________\/          \/___________/
      \          /\           \          /           /\           \          /           /
       \        /  \           \        /           /  \           \        /           /
        \      /    \           \      /           /    \           \      /           /
         \    /      \           \    /           /      \           \    /           /
          \  /        \           \  /           /        \           \  /           /
           \/          \___________\/___________/          \___________\/___________/
            \          /\           \           \          /           /           /
             \        /  \           \           \        /           /           /
              \      /    \           \           \      /           /           /
               \    /      \           \           \    /           /           /
                \  /        \           \           \  /           /           /
                 \/          \___________\___________\/___________/___________/
                  \          /           /           /           /           /
                   \        /           /           /           /           /
                    \      /           /           /           /           /
                     \    /           /           /           /           /
                      \  /           /           /           /           /
                       \/___________/___________/___________/___________/
```

# Answer
# CJam, 85 79 76 72 bytes

```
li:Tlf*NqN/T,f{ff{"_/"2$#_1<@+*~ST*@t}:+z{S+e`);e~{"_ "/"__"*W%}T2**N}/}

```

The size should be on the first line. And the diamond follows.

Not golfed very well... And half of the characters came from the details.

### Explanations (of previous version)

```
li:T            e# Read the size and save to T.
qN/             e# Read and split to lines.
\,fm*           e# Convert each character X to [X 0] [X 1]... [X T(]
{~              e# For each [X I] in each line:
    ST*         e# T spaces.
    \           e# I.
    "_\\"3$#    e# If X is '_, '\ or '/, return Y = 0, 1, -1 respectively.
    _W>@+       e# If it was '_ or '\, increase I by one.
    *(          e# I * Y - 1.
    @t          e# Set the character at that position to X.
}f%
:z:+            e# Make the returned lists from each iteration across T lines.
{S+e`);e~N+}%   e# Boring details to remove trailing spaces and append a newline.
T(>(\s          e# Boring details to extract the first line and only work on others.
{_{"_ "/"__"*W%}2*_@=!}g
                e# Boring details to make underlines expand left and right.

```
> 8 votes

# Answer
# Python 2, 164

```
def g(s,n,j=1):
 for W in s.split("\n"):exec"O=p='';d=0\nfor c in W:q=' _'[j*'_'in p+c];e=[n-j,j-1][c=='/'];O+=q*(e+d)+[c,q][c>'^'];p=c;d=n+~e\nprint O;j-=1;"*j;j=n

```

Output on test cases.

So, what's going on here?

The main idea is that each character in the original blows up into an `n*n` block. For example, for n=4, `/` might become

```
   /
  /
 /
/___

```

The original character appears once in each line, and there's padding to either side. Here, it's  on the left, and  and `_` on the right. Only the bottom row can be padded by `'_'`; the rest is always `' '`.

The main difficulty is that the padding on the right can depend on the upcoming symbol. Specifically, `'/ '` has different padding from `'/_'`, so we'd need some look-ahead. Moreover, to avoid trailing spaces, we'd have to note that we're at the last symbol and refrain from padding on the right.

We overcome both these issues by only padding to the left of the current character. When we do so, we also perform the right-padding from the previous character using the current padding symbol. So, we print the right-padding owed from the previous char, the left-padding from the current char, then the current char. We also store the amount of padding "debt" the next char will need to pay.

Now let's go over the code.

```
def g(s,n,j=1):
    for W in s.split("\n"):
        while j:
            O=p='';d=0
            for c in W:
                q=' _'[j*'_'in p+c]
                e=[n-j,j-1][c=='/']
                O+=q*(e+d)+[c,q][c>'^']
                p=c
                d=n+~e
            print O;j-=1;
        j=n

```

The input string is `s` and the scale-factor is `n`. We go line-by-line, printing `n` lines for each input line `W`, with the copies indexed `j=n,n-1,...,2,1`. The first line is only copied once, which we achieve this by initializing `j` to 1 but changing it to `n` each loop.

We iterate through the input line, accumulating the line to print in `O`. First, we figure out the appropriate padding character `q`, which is an underscore if we're on the bottom line and either the current or previous character is an underscore, and otherwise a space.

Then, we decide the amount of padding to put on the left (`e`). For `/`, it's `j-1` (decreasing with decreasing line-copy number), and the complementary `n-j` for `\`. We treat other characters the same way. For example, though `_` seems like it gives a row of `n` underscores, it actually gives a single underscore, padded by underscores on the left and right. This seems inefficient, but it lets us works with `_` and  in the same framework as `/` and `\` The position of the "central" underscore doesn't matter, so we lump it and  with `\`; this choice also makes the top row work out without special casing.

Next, we add to the output string. We've figured out the padding symbol `q`, and the current padding amount `e`, but we also need to remember the padding debt `d` from the previous symbol. So, we add `q*(e+d)`. Then, we add the current symbol `c`, except we need to avoid underscores in a non-bottom row, which we fix by converting underscores to the padding symbol.

Finally, we record the padding debt amount, which the complement `n+~d` of the current left-padding amount. We also record the current symbol in `p`, so that we will later know whether the previous symbol was `_`.
> 10 votes

# Answer
# JavaScript (*ES6*) 274 ~~281 289 338~~

```
// GOLFED
F=(b,n)=>{
b=b[R='replace'](/ |_/g,c=>c[T='repeat'](n))[R](/_(?=[\\\/])/g,'_'[T](n))[R](/\/\\/g,`/${'  '[T](n-1)}\\`)
.split('\n');
for(i=l=b.length*n-n+1;--i;)
b[i]=i%n?b[i+1][R](/_/g,' ')[R](/\/ ?/g,' /')[R](/ \\(.)?/g,'\\$1$1')
:' '[T](i>l/2?n-1:0)+b[i/n];
return b.join('\n')}

// UNGOLFED
U=(b,n)=>{
  b=b
  .replace(/ |_/g,c=>c.repeat(n))
  .replace(/_(?=[\/\\])/g,'_'.repeat(n))
  .replace(/\/\\/g,`/${'  '.repeat(n-1)}\\`)
  .split('\n');
  for(i=l=b.length*n-n+1;--i;)
  {
    if(i%n)
     b[i]=b[i+1]
     .replace(/_/g,' ')
     .replace(/\/ ?/g,' /')
     .replace(/ \\/g,'\\ ').replace(/ +$/,'')
     .replace(/ \\(.)?/g,'\\$1$1')
    else {
      b[i]=b[i/n]
      if(i>l/2)b[i]=' '.repeat(n-1)+b[i];
    }
  }
  return b.join('\n')
}

//TEST

test=[
' __\n/_/\\\n\\_\\/',
'  ____\n /_/\\_\\\n/\\_\\/_/\\\n\\/_/\\_\\/\n \\_\\/_/',
'   ______\n  /_/_/\\_\\\n /_/\\_\\/\\_\\\n/\\_\\/_/\\/_/\\\n\\/_/\\_\\/_/\\/\n \\_\\/_/\\_\\/\n  \\_\\_\\/_/',
'    ________\n   /_/\\_\\_\\_\\\n  /\\_\\/\\_\\_\\_\\\n /\\/_/\\/_/_/\\_\\\n/\\/\\_\\/_/_/\\/\\_\\\n\\/\\/_/\\_\\_\\/\\/_/\n \\/\\_\\/_/\\_\\/_/\n  \\/\\_\\_\\/_/_/\n   \\/_/_/_/_/'
]

test.forEach(t=>{
  var row = '<td>'+t+'<td>'
  for(rr=2;rr<5;rr++)
    row += '<td>'+F(t,rr)+'</td>'
  OUT.innerHTML += '<tr>'+row+'</tr>'
})
```

```
td {
  font-family: monospace;
  white-space: pre;
}
```

```
(better full page)
<table id=OUT></table>
```
> 3 votes

# Answer
# Python, ~~272~~ ~~238~~ ~~228~~ 243 bytes

Updated version, now takes a single string as input, instead of a string sequence. Also removes trailing whitespace that was present in earlier version. Unfortunately these changes increase the size.

```
s,u,f,b=' _/\\'
r=str.replace
def d(t,n,j=1):
 for p in t.split('\n'):
  for k in range(n-j,n):m,v=n+~k,'_ '[k<n-1];print r(r(r(r(r(r(r(r(p,f+u,'(_'),u+b,'_)'),s,s*n),u,v*n),f,s*m+f+s*k),'(',v*m+f+v*k),b,s*k+b+s*m),')',v*k+b+v*m).rstrip();j=n

```

Version with whitespace, and statements broken up into smaller units for readability:

```
s, u, f, b = ' ', '_', '/', '\\'
def d(t, n):
    j = n - 1
    for p in t:
        for k in range(j, n):
            m, v = n - 1 - k, '_ '[k < n - 1]
            q = p[:-1]
            q = q.replace(f + u, '(_')
            q = q.replace(u + b, '_)')
            q = q.replace(s, s * n)
            q = q.replace(u, v * n)
            q = q.replace(f, s * m + f + s * k)
            q = q.replace('(', v * m + f + v * k)
            q = q.replace(b, s * k + b + s * m)
            q = q.replace(')', v * k + b + v * m)
            print q
            j = 0

```

The basic approach here is:

1. Loop over all lines in input.
2. For each line, loop over the output size `N`, generating an output line in each loop iteration. There's a special case for the first line, where only the last output line is generated, to avoid generating empty lines at the start of the output.
3. Replace each character in the line by `N` characters, where:
    * Each space is replaced by `N` spaces.
    * Each underscore is replaced by `N` spaces for the first `N -1` loop iterations, and `N` underscores for the last loop iteration.
    * Slashes and backslashes are padded with `N - 1` spaces or underscores.

The most tricky part here is that the padding for slashes/backslashes uses spaces or underscores depending on the next (for slashes) or previous (for backslashes) input character. That did not seem to fit well with the string substitution strategy.

What I did to resolve this is that I first replace certain two character combinations with different characters, so that I can treat them differently during the actual substitution. For example, `/_` is replaced by `(_`. After this, `(` is effectively a "slash followed by underscore", which can then be substituted accordingly.

Main program used for testing the function:

```
import sys
import Golf

n = int(sys.argv[1])
t = ''.join(sys.stdin).rstrip()

Golf.d(t, n)

```
> 3 votes

# Answer
# Python 2, ~~217~~ ~~211~~ ~~195~~ ~~194~~ 190

```
b,f,s='\/ '
R=str.replace
def m(g,n,z=1):
 for d in g.split('\n'):
    for i in range(z):a=z+~i;print[i,a][d[-1]>f]*s+R(R(R(R(d,s,s*n),'_','_ '[i<z-1]*(z+n-1)),f+b,f+s*2*i+b),b+f,b+s*2*a+f);z=n

```

*6 bytes thanks to Sp3000.*

Call `m` with the first argument being the diamond as a string, and the second argument the repetition number.

This is based on a 3-step string replacement sequence:

* First, replace underscores with 2n-1 spaces or underscores, depending on the line.
* Second, replace `/\` with `/ \`, with the number of intervening spaces going from 2 to 2\*(n-1) over the lines.
* Third, replace `\/` with `\ /`, with the number of intervening spaces going from 2\*(n-1) to 2 over the lines.

Then, there's a variety of mucking about to get the leading spaces right, and to get the first line right.

Note that the final line of the program should be a tab, not 4 spaces. Markdown doesn't support tabs.
> 3 votes

# Answer
# Ruby 236 ~~237~~

```
->i,z{i.split(?\n).map{|l|z.times.map{|y|l.size.times.map{|i|z.times.map{|x|c=l[i]
z<y+2&&(l[i-1..i]=='_\\'||l[i..i+1]=='/_')&&o=?_
(c<?!||(x==y&&c==?\\)||(z==y+1&&c>?^)||(x+y+1==z&&c==?/))&&o=c
o||' '}.join}.join.rstrip}-['']}.join ?\n}

```

Online test: http://ideone.com/e6XakQ

This is the code before golfing:

```
-> diamond, zoom {
  diamond.split(?\n).map do |l|
    zoom.times.map do |y|
      l.size.times.map do |i|
        zoom.times.map do |x|
          out_char = crt_char = l[i]

          out_char = ' '

          # _ has to be continued under / or \
          if zoom == y+1 && l[i-1..i]=='_\\'
            out_char = ?_
          end
          if zoom == y+1 && l[i..i+1]=='/_'
            out_char = ?_
          end

          # logic to "zoom" \, / and _ characters
          out_char = crt_char if crt_char == ' '
          out_char = crt_char if x==y && crt_char == ?\\
          out_char = crt_char if zoom==y+1 && crt_char == ?_
          out_char = crt_char if x+y+1==zoom && crt_char == ?/

          out_char
        end.join
      end.join.rstrip
    end - ['']
  end.join ?\n
}

```
> 1 votes

# Answer
# Perl, 132

```
#!perl -p
INIT{$f=pop}s!.!$&x$f!ge;s! $!! while s!\\+\K\\|/(/)! $1!;
for$x(2..m!/!*$f){print y!_! !r;s!\\.?! \\!g;s!./(.)?!/$1$1!g;s!_ !__!g}

```

Combined STDIN and ARGV input. Example:

```
$ perl ~/hex.pl <~/hex.txt 3
         __________________
        /     /     /\     \
       /     /     /  \     \
      /_____/_____/    \_____\
     /     /\     \    /\     \
    /     /  \     \  /  \     \
   /_____/    \_____\/    \_____\
  /\     \    /     /\    /     /\
 /  \     \  /     /  \  /     /  \
/    \_____\/_____/    \/_____/    \
\    /     /\     \    /     /\    /
 \  /     /  \     \  /     /  \  /
  \/_____/    \_____\/_____/    \/
   \     \    /     /\     \    /
    \     \  /     /  \     \  /
     \_____\/_____/    \_____\/
      \     \     \    /     /
       \     \     \  /     /
        \_____\_____\/_____/

```
> 1 votes

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


title: Non-Palindromic Polyglot Boggle

text:
# Question
Title: Non-Palindromic Polyglot Boggle
## Introduction

The number 101 is a palindrome, since it reads the same backwards and forwards. The number 105 is not. However, 105 in base eight is written as 151, which *is* palindromic. On the other hand, 103 is not a palindrome in *any* base from 2 to 101. Hence, 103 is **strictly non-palindromic**.

The precise definition is: A nonnegative integer *n* is strictly non-palindromic if it is not a palindrome in any base between 2 and n-2, inclusive.

The first few strictly non-palindromic numbers are `0, 1, 2, 3, 4, 6, 11, 19, 47, 53, 79, 103, 137, 139, 149, 163, 167, 179, 223, 263, 269...` (A016038)

Write a full program that takes a number *x* from STDIN and prints the *x*th strictly non-palindromic number. For example, the input `5` would produce the output `4`.

## Challenge

The challenge is to write multiple (one or more) programs, each solving this task in a different language.

Then, you must put all of the programs in a rectangular grid of characters. The programs can be accessed Boggle-style. That is, go from one character to a neighboring character (including diagonally), never using the same character more than once.

For example, the following grid:

```
abc
bdc

```

includes the words `abc`, `ccd`, `bbad`, and `bcdb`, but not `ac`, `bdd`, `bcb`, or `cbbc`.

Each program must be found in the grid using these rules. However, you may use the same character in multiple programs.

## Score

Your score is the number of characters in the grid, divided by the number of programs. Lowest score wins!

## Rules

* Two languages are considered different if they usually go by different names, ignoring version numbers. For example, C and C++ are different, but Python 2 and Python 3 are the same.
* The characters in the grid must all be from printable ASCII, i.e., from  to `~`, code points `20` through `FE`.
* Each program must consist only of printable ASCII, plus newlines. When inserting a program into the grid, replace each newline with a space.
    + A space in the grid may represent a space in one program and a newline in another.
* The grid must be a rectangle.
* Not every character needs to be used in a program.

# Answer
# 19x2 = 38, 2 programs, Score: ~~26~~ ~~19.5~~ 19

Here is the board:

```
-:\~{.,><1\b_W%}}g}
1Wq{)_2W{$ase.=,do*

```

This contains the following programs:

# CJam (27 bytes)

```
Wq~{{)_,2>W<{1$\b_W%=},}g}*

```

Test it here.

These are the characters of the board used for this code:

```
   ~{ ,><1\b_W%}}g}
 Wq{)_2W{$    =,  *

```

# GolfScript (34 bytes)

```
-1:W\~{{).,2>W<{1$\base.W%=},}do}*

```

Test it here.

These are the characters of the board used for this code:

```
-:\~{.,><1\b W%}} }
1W {) 2W{$ase.=,do*

```
> 10 votes

---
Tags: code-challenge, sequence, palindrome, polyglot, boggle
---