title: Can you fold a hexomino into a cube?

text:
# Question
Title: Can you fold a hexomino into a cube?
One of my kid's favorite toys is a set like this. Actually its one of my favorite toys - I've been playing with it and its been giving me some PPCG challenge ideas. Here's one:

Write a program or function that takes an ASCII line drawing as input and decides whether or not it folds into a cube.

### Input

Input will consist of exactly one hexomino built from squares like this:

```
+-+
| |
+-+

```

For example a valid input heximino is:

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

```

### Output

* A truthy value if the hexomino can be folded into a cube, or
* A falsey value otherwise.

To save us a bit of work, wikipedia has nice graphics of:

* All 35 hexominoes:

* All 11 hexominoes that fold into cubes:

### Notes

* Input hexominoes may have any rotation or reflection, not just those shown in the images above
* Input hexominoes may have leading spaces, but will be correctly aligned with respect to themselves
* Input hexominoes may have trailing space at the end of lines and trailing newlines at the end of input

# Answer
# PMA/Snails, 130

```
.!(z\ |o{c..!(z\ }3){w=(..!(z\ )|b..!(z\ )o{..!(z\ }2|c{..!(z\ }1,2w..!(z\ )|w{..!(z\ }1,2c..!(z\ }4o..!(z\ )(..!(z\ )|n..!(z\ )`2

```

or more "readably",

```
?
.!(z\  | o{c..!(z\ }3  )
{w =( ..!(z\ ) | b ..!(z\ ) o {..!(z\ }2  | c {..!(z\ }1,2w..!(z\ ) | w {..!(z\ }1,2c..!(z\  }4
o  ..!(z\ ) ( ..!(z\ ) | n ..!(z\ ) `2

```

Unusually, a problem came along that can be handled by the limited amount of features implemented so far. The `!(z\ )` pattern determines that the current position is at the space in the middle of a square using a negative assertion that there is a space in some "octilinear" direction. The general idea is to check for a pattern that places a square at each of the 5 necessary locations relative to the square that the match starts on. Also, it needs to check that it is not in a 2x2 block of squares. Before the program would work, I had to fix a bug with the parsing of parentheses.

If the hexomino does not map a cube, `0` is printed. If it does, some positive integer is printed (number of matches).

I adapted this polyomino generator to create all possible test cases:

```
n=input()
r=range
T=lambda P:set(p-min(p.real for p in P)-min(p.imag for p in P)*1j for p in P)
A=[]
for i in r(1<<18):
 P=[k%3+k/3*1j for k in r(18)if i>>k&1]
 C=set(P[:1])
 for x in P:[any(p+1j**k in C for k in r(4))and C.add(p)for p in P]
 P=T(P)
 if not(C^P or P in A or len(P)-n):
  #for y in r(4):print''.join(' *'[y+x*1j in P] for x in r(6))
  o = [ [' ']*13 for _ in r(9)]
  for y in r(4):
   for x in r(6):
    if y+x*1j in P: X=2*x;Y=2*y; o[Y][X]=o[Y+2][X]=o[Y][X+2]=o[Y+2][X+2]='+'; o[Y][X+1]=o[Y+2][X+1]='-';o[Y+1][X+2]=o[Y+1][X]='|'
  print '\n'.join(map(''.join,o))
  A+=[T([p*1j**k for p in P])for k in r(4)]

```
> 7 votes

# Answer
# Ruby, ~~173 148 145~~ 143 bytes

```
h=->b,c{[c.count(c.max),c.count(c.min),3].max*2<b.max-b.min}
->s{x=[];y=[];i=j=0
s.bytes{|e|e==43&&x<<i|y<<j;i=e<32?0*j+=1:i+1}
h[x,y]||h[y,x]}

```

Latest change: `/2` on right side of `<` replaced by `*2`on left side. Allows elimination of one set of`()`

**Explanation**

The code is in two parts: a main unnamed function that does the parsing, and an auxiliary unnamed function assigned to the variable `h` that does the checking.

The main function scans bytewise through the string, adding the x and y coordinates `i,j` of all `+` symbols found to `x[]` and `y[]`. It then calls `h` twice. The first time it assumes the hexomino is horizontal (`x[]` contains the lengths and `y[]` the widths) and the second time it assumes it is vertical.

**The function `h` takes the lengthwise coordinates in array `b` then the widthwise coordinates in array `c`.** It calculates the length (in squares) by the expression `(b.max.b.min)/2`. If this is less than or equal to 3, the hexomino should be evaluated in the other direction so `h` returns `false`.

Inspection of the hexominos will show that if the length is 4, **those hexominos that will fold into a cube have no more than 2 squares (3 `+` symbols) in the first and last row**. Most of the squares are concentrated on the middle row, which will become the equator of the cube. This condition turns out to be necessary and sufficient for a hexomino of length 4 that will fold into a cube.

There is only one hexomino of length 5 that will fold into a cube. It has 3 squares (4 `+` symbols) in its first and last rows. All other hexominos of length 5 have 5 or more `+` symbols in either the first or last row.

There is only one hexomino of length 6. It has 7 `+` symbols on each row.

**Putting all this together, it is sufficient to check that the length of the hexomino is greater than 3, and the number of `+` symbols on the first and last rows (whichever is higher) is less than the length.**

**Ungolfed in test program**

```
#checking function as explained in text
h=->b,c{[c.count(c.max),c.count(c.min),3].max<(b.max-b.min)/2}

#main function for parsing
f=->s{
  x=[]                 #separate assignments required,
  y=[]                 #otherwise we get 2 pointers to the same array
  i=j=0                #start coordinates 0,0
  s.bytes{|e|          #scan string bytewise
    e==43&&x<<i|y<<j     #if byte is a + symbol (ascii 43) add the coordinates to arrays x and y
    i=e<32?0*j+=1:i+1    #if byte is before ascii 32 assume newline, increment j and zero i. Otherwise increment i
  }
  h[x,y]||h[y,x]       #call h twice, with x and y in each possible order
}

#VALID INPUTS
puts f["
+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
| |
+-+"]

puts f["
+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
  | |
  +-+"]

puts f["
+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
    | |
    +-+"]
puts f["
+-+
| |
+-+-+-+
| | | |
+-+-+-+-+
    | | |
    +-+-+"]

puts f["
+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
      | |
      +-+"]

puts f["
    +-+
    | |
+-+-+-+-+
| | | | |
+-+-+-+-+
    | |
    +-+"]
puts f["
    +-+
    | |
+-+-+-+
| | | |
+-+-+-+-+
    | | |
    +-+-+"]

puts f["
  +-+
  | |
+-+-+-+-+
| | | | |
+-+-+-+-+
    | |
    +-+"]
puts f["
  +-+
  | |
+-+-+-+
| | | |
+-+-+-+-+
    | | |
    +-+-+"]
puts f["
+-+-+
| | |
+-+-+-+
  | | |
  +-+-+-+
    | | |
    +-+-+"]

puts f["
  +-+-+-+
  | | | |
  +-+-+-+-+-+
      | | | |
      +-+-+-+
"]

#INVALID INPUTS

puts f["
  +-+-+-+
  | | | |
  +-+-+-+
  | | | |
  +-+-+-+
"]

puts f["
  +-+-+-+-+-+-+
  | | | | | | |
  +-+-+-+-+-+-+

"]

puts f["
  +-+-+
  | | |
  +-+-+
  | |
  +-+
  | |
  +-+
  | |
  +-+
  | |
  +-+
"]

puts f["
  +-+-+-+-+-+
  | | | | | |
  +-+-+-+-+-+
    | |
    +-+
"]

puts f["
      +-+
      | |
  +-+-+-+-+-+
  | | | | | |
  +-+-+-+-+-+
"]

puts f["
  +-+-+-+-+
  | | | | |
  +-+-+-+-+-+
        | | |
        +-+-+"]

puts f["
  +-+-+-+-+
  | | | | |
  +-+-+-+-+
      | | |
      +-+-+
"]

puts f["
  +-+-+-+-+
  | | | | |
  +-+-+-+-+
  | | | |
  +-+ +-+
"]

puts f["
 +-+   +-+
 | |   | |
 +-+-+-+-+
 | | | | |
 +-+-+-+-+
"]

puts f["
   +-+-+
   | | |
 +-+-+-+-+
 | | | | |
 +-+-+-+-+
"]

puts f["
  +-+
  | |
  +-+
  | |
  +-+-+-+-+
  | | | | |
  +-+-+-+-+
"]

puts f["
  +-+
  | |
  +-+-+-+
  | | | |
  +-+-+-+
  | |
  +-+
  | |
  +-+
"]

puts f["
  +-+
  | |
+-+-+-+
| | | |
+-+-+-+
| |
+-+
| |
+-+"]

puts f["
  +-+-+
  | | |
  +-+-+
  | |
  +-+-+
  | | |
  +-+-+
    | |
    +-+
"]

puts f["
  +-+-+-+
  | | | |
  +-+-+-+-+
    | | | |
    +-+-+-+
"]

puts f["
  +-+-+-+
  | | | |
  +-+-+-+
      | |
      +-+-+
      | | |
      +-+-+
"]

puts f["
  +-+-+-+
  | | | |
  +-+-+-+-+
      | | |
      +-+-+
        | |
        +-+
"]

```
> 5 votes

# Answer
# JavaScript (ES6), 443 ~~431~~

*Edit* bug fix, problem during input parse, removing blank columns

```
F=t=>(a=b=c=d=e=f=g=h=0,M=Math.min,
t=t.split('\n').filter(r=>r.trim()>''),
t=t.map(r=>r.slice(M(...t.map(r=>r.search(/\S/))))),
t.map((r,i)=>i&1&&[...r].map((_,j)=>j&1&&r[j-1]==r[j+1]&t[i-1][j]==t[i+1][j]&r[j-1]=='|'
&&(y=i>>1,x=j>>1,z=y*5,w=x*5,a|=1<<(z+x),e|=1<<(w+y),b|=1<<(4+z-x),f|=1<<(4+w-y),c|=1<<(20-z+x),g|=1<<(20-w+y),d|=1<<(24-z-x),h|=1<<(24-w-y)
))),~[1505,2530,3024,4578,252,6552,2529,4577,2499,4547,7056].indexOf(M(a,b,c,d,e,f,g,h)))

```

That's very long, and even longer as parsing input is a big part of the task.

What I do is verifyng if the given input is one of the 11 foldable hexominoes.

Each foldable hexomino can be mapped to some 5x5 bitmap (up to 8 different, with simmetry and rotations). Taken the bitmaps as 25bit number, I have found the min values for the 11 noted hexominoes, using the following code (with very simple input format)

```
h=[ // Foldable hexominoes
'o\noooo\no', ' o\noooo\n o', // pink
'o\noooo\n   o', ' o\noooo\n  o', 'ooo\n  ooo', 'oo\n oo\n  oo', //blue
'o\noooo\n o', 'o\noooo\n  o', 'oo\n ooo\n o', 'oo\n ooo\n  o', 'o\nooo\n  oo' // gray
]
n=[]
h.forEach(t=>(
  a=[],
  t.split('\n')
    .map((r,y)=>[...r]
      .map((s,x)=>s>' '&&(
         a[0]|=1<<(y*5+x),a[1]|=1<<(x*5+y),
         a[2]|=1<<(y*5+4-x),a[3]|=1<<(x*5+4-y),
         a[4]|=1<<(20-y*5+x),a[5]|=1<<(20-x*5+y),
         a[6]|=1<<(24-y*5-x),a[7]|=1<<(24-x*5-y))
     )
  ),
n.push(Math.min(...a))
))

```

That gives `[1505,2530,3024,4578,252,6552,2529,4577,2499,4547,7056]`

So, given the input string, I have to do the same to find the min bitmap, then return true if this number is present in my precalc list.

```
// Not so golfed

F=t=>(
  a=b=c=d=e=f=g=h=0,M=Math.min,
  t=t.split('\n').filter(r=>r.trim()>''), // remove blank lines
  t=t.map(r=>r.slice(M(...t.map(r=>r.search(/\S/))))), // remove blank colums to the left
  t.map((r,i)=>i&1&&[...r] // only odd rows
   .map((_,j)=>j&1&& // only odd columns
      r[j-1]==r[j+1]&t[i-1][j]==t[i+1][j]&r[j-1]=='|' // found a cell
         &&(y=i>>1,x=j>>1,z=y*5,w=x*5, // find bitmaps for 8 rotations/simmetries
            a|=1<<(z+x),e|=1<<(w+y),
            b|=1<<(4+z-x),f|=1<<(4+w-y),
            c|=1<<(20-z+x),g|=1<<(20-w+y),
            d|=1<<(24-z-x),h|=1<<(24-w-y)
    ))),
   ~[1505,2530,3024,4578,252,6552,2529,4577,2499,4547,7056].indexOf(Math.min(a,b,c,d,e,f,g,h)) // look for min
)

```

Run snippet to test in Firefox

```
F=t=>(a=b=c=d=e=f=g=h=0,M=Math.min,
t=t.split('\n').filter(r=>r.trim()>''),
t=t.map(r=>r.slice(M(...t.map(r=>r.search(/\S/))))),
t.map((r,i)=>i&1&&[...r]
.map((_,j)=>j&1&&r[j-1]==r[j+1]&t[i-1][j]==t[i+1][j]&r[j-1]=='|'
&&(y=i>>1,x=j>>1,z=y*5,w=x*5,
a|=1<<(z+x),e|=1<<(w+y),b|=1<<(4+z-x),f|=1<<(4+w-y),c|=1<<(20-z+x),g|=1<<(20-w+y),d|=1<<(24-z-x),h|=1<<(24-w-y)
))),~[1505,2530,3024,4578,252,6552,2529,4577,2499,4547,7056].indexOf(M(a,b,c,d,e,f,g,h)))

s=[...'      \n      \n      \n  2   \n      \n      '],o=7,l=5,k={},t=0

out=[[],[]]

Test=s=>k[s]?0 // filter duplicates, but allow same shape in different position
  :k[s]=(
  p=Array(13).fill(0).map(x=>Array(13).fill(' ')), // build string to test in long format
  s.map((v,i)=>(x=2*(i%7),y=2*(i/7|0),-v&&(
    p[y][x]=p[y][x+2]=p[y+2][x]=p[y+2][x+2]='+',
    p[y][x+1]=p[y+2][x+1]='-',
    p[y+1][x]=p[y+1][x+2]='|'
  ))),
  s=p.map(r=>r.join('')).join('\n'),
  ok=F(s), // test

  out[!ok|0].push('\n'+s+-ok),
  1
)

Fill=(z,p)=>(
  s[p]=2,
  z>l?Test(s):s.forEach((v,i)=>v==' '&(s[i+o]==2|s[i-o]==2|s[i-1]==2|s[i+1]==2)?Fill(z+1,i):0),
  s[p]=' '
)

Fill(1,s.indexOf('2'))

OV.innerHTML=out[0].join('\n')
OI.innerHTML=out[1].join('\n')
```

```
pre {
  overflow: auto;
  font-size: 9px;
  height: 500px;
  display: block;
  border: 1px solid #888;
  padding: 6px 20px;
  line-height: 6px;
}
```

```
Verify all hexominoes possible in a 6x6 grid (Better full page) <br>
<table><tr>
  <th>VALID</th><th>INVALID</th>
</tr><tr>
  <td><pre id=OV></pre></td>
  <td><pre id=OI></pre></td>
</tr></table>
```
> 3 votes

---
Tags: code-golf, ascii-art, kolmogorov-complexity, geometry
---


title: Iterative binary search

text:
# Question
Title: Iterative binary search
Binary search is an algorithm that looks for an element in a sorted data-structure by constantly dividing the search space in half.

### Rosetta Code

> A binary search divides a range of values into halves, and continues to narrow down the field of search until the unknown value is found. It is the classic example of a "divide and conquer" algorithm.

### Wikipedia

> In computer science, a binary search or half-interval search algorithm finds the position of a target value within a sorted array. The binary search algorithm can be classified as a dichotomic divide-and-conquer search algorithm and executes in logarithmic time.

---

Smallest # of bytes wins

### Clarifications

* Example of calling the function/lambda/macro should be included, but don't count those chars!
* Output should be `> -1` if found, and `<=-1` otherwise
* `import binary_search` (20 bytes) DOES NOT count!
* Implementation should run in O(log n), as algorithm dictates

Also see the code-golf StackExchange FAQ.

### Example

```
> binary_search([1,3,5,6,7,8,8,10], 5);
4
> binary_search([1,3,5,6,7,8,8,10], 543);
-1

```

# Answer
> 2 votes
### JavaScript (94 bytes)

```
(a,e)=>{u=a.length,m=0;for(l=0;l<=u;)e>a[m=(l+u)>>1]?l=m+1:u=e==a[m]?-2:m-1;return u==-2?m:-1}

```

Expanded out a little so you can see what's going on:

```
function binary_search(array, elem) {
    let u = array.length, m;
    for (let l = 0; l <= u;)
        if (elem > array[(m = (l + u) >> 1)]) l = m + 1;
        else u = (elem == array[m]) ? -2 : m - 1;
    return (u == -2) ? m : -1;
}

```

Example usage:

```
> a = [1,2,3,4,5,6,7,8,9,10]
> binary_search(a, 5)
4
> binary_search(a, 15)
-1

```

# Answer
> 2 votes
# C – 119 ~~115~~ bytes

Iterative solution at 119 bytes:

```
f(a,x,l,h)int*a,x,l,h;{while(l<h){int m=(h+l)/2;if(a[m]>x)h=m;else if(a[m]<x)l=m+1;else return m;}return a[l]==x?l:-1;}

```

Recursive solution at 115 bytes:

```
f(a,x,l,h)int*a,x,l,h;{if(l==h)return a[l]==x?l:-1;int m=(h+l)/2;return a[m]>x?f(a,x,l,m):(a[m]<x?f(a,x,m+1,h):m);}

```

You can precede with `int`  to prevent compiler warnings or if you're using `gcc` compile with `-Wno-implicit-int`. Sample:

```
#include <stdio.h>

f(a,x,l,h)int*a,x,l,h;{while(l<h){int m=(h+l)/2;if(a[m]>x)h=m;else if(a[m]<x)l=m+1;else return m;}return a[l]==x?l:-1;}

int main()
{
    int x, a[] = {-10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10};

    for (x = -15; x <= 15; x++)
        printf("%d\t%d\n", x, f(a, x, 0, 10));

    return 0;
}

```

# Answer
> 2 votes
# Python 112 bytes

```
def b(A,k):
 l,h=0,len(A)
 while l<h:
  m=(l+h)/2
  if A[m]>k:h=m
  elif A[m]<k:l=m+1
  else:return m
 return -1

```

**Example:**

`print b([1,3,5,6,7,8,8,10], 5)`

`2`

# Answer
> 1 votes
## AutoIt, 92 bytes

This function binary searches an array in-memory and replaces it with an integer holding the index (or -1 if not found). Array needs to be sorted to work with the binary search:

```
#include <Array.au3>
Func b(ByRef $a,$n)
_ArraySort($a)
$a=_ArrayBinarySearch($a,$n)
EndFunc

```

Testing:

```
Local $a = [1,2,3,4,5,6,7,8,9,10]
b($a,5)
ConsoleWrite($a & @LF)

```

Output: `4`

# Answer
> 1 votes
# C++14, ~~87~~ 85 bytes

```
#include<algorithm>
[](int i,auto v){return std::binary_search(begin(v),end(v),i)-1;}

```

Assumes a sorted data structure which has iterators as input.

**Example:**

```
#include<algorithm>
#include<iostream>

auto f = [](int i, auto v){ return std::binary_search(begin(v), end(v), i) - 1; };

int main()
{
    std::vector<int> v = { 1, 2, 3, 4, 5 };

    std::cout << f(3, v);
}

```

# Answer
> 1 votes
# Prolog, 146 bytes

I made the assumption that a program returning easy to understand truthy/falsy values is OK, as adding code just to return -1/1 instead of true/false in a code-golf challenge seems counter-productive.
So the program returns **true** if the value is present in the list, otherwise **false**.

```
s(F,S,L):-append(F,S,L),length(F,G),length(S,T),T>=G,T-G<2.
c(L,X):-s(_,[X|_],L).
c(L,X):-s(_,[M|T],L),X>M,c(T,X).
c(L,X):-s(F,[_|_],L),c(F,X).

```

**How it works**

```
s(F,S,L):-append(F,S,L),length(F,G),length(S,T),T>=G,T-G<2.

```

Helper function that takes the list **L** and splits it in the middle into the lists **F** and **S** where **F** is the lower part of the list. If **L** has an odd number of elements, **S** is one element larger than **F**.

```
c(L,X):-s(_,[X|_],L).

```

Succeeds if the sought after element **X** is in the middle of list **L**.

```
c(L,X):-s(_,[M|T],L),X>M,c(T,X).

```

Checks for **X** in the higher part of the list if **X** is bigger than the middle element of list **L**.

```
c(L,X):-s(F,[_|_],L),c(F,X).

```

Checks for **X** in the lower part of the list if **X** is smaller than the middle element of list **L**.
As the previous predicates are checked first we can save a few bytes by not doing a comparison here.
**Examples:**

```
> c([1,3,5,6,7,8,8,10],5).
true

> c([1,3,5,6,7,8,8,10],543).
false

```

# Answer
> 1 votes
## Common Lisp, ~~142~~ 143 bytes

*Having seen some of the comments about recursive vs iterative, I'd point out that in any implementation with tail-call optimization, the second (original) solution* is *iterative.*

### pure iterative, with `do` loop (143):

```
(lambda(a e)(do((l 0)(h(length a)))((<= h l)-1)(let*((m(ash(+ h l)-1))(x(aref a m)))(if(= x e)(return m)(if(< e x)(setf h m)(setf l(1+ m)))))))

```

```
(lambda (a e)
    (do ((l 0)
         (h (length a)))
        ((<= h l) -1)
      (let* ((m (ash (+ h l) -1))
             (x (aref a m)))
        (if (= x e)
            (return m)
            (if (< e x)
                (setf h m)
                (setf l (1+ m)))))))

```

### recursive (142)

```
(defun b(a e &optional(l 0)(h(length a)))(if(<= h l)-1(let*((m(ash(+ h l)-1))(x(aref a m)))(if(= x e)m(if(< e x)(b a e l m)(b a e(1+ m)h))))))

```

```
(defun b (a e &optional (l 0) (h (length a)))
  (if (<= h l) -1
      (let* ((m (ash (+ h l) -1))
             (x (aref a m)))
        (if (= x e) m
            (if (< e x)
                (b a e l m)
                (b a e (1+ m) h))))))

```

```
CL-USER> (loop with array = #(1 3 5 6 7 8 8 10)
            for element in '(1 7 5 3 2 4 6)
            collect (b array element))
(0 4 2 1 -1 -1 3)

```

---
Tags: code-golf, search
---


title: Compile Regexes (By Substitution)

text:
# Question
Title: Compile Regexes (By Substitution)
Your task is to compile regexes... by specifying a substitution for each character in a regex.

## Regexes

The regexes support these

```
REGEX       = (LITERAL REGEX / GROUP REGEX / STAR REGEX / ALTERNATIVE)
LITERAL     = 1 / 0
GROUP       = '(' REGEX ')'
STAR        = (LITERAL / GROUP) '*'
ALTERNATIVE = '('REGEX ('|' REGEX)*')'

```

Why only 1 or 0? It is for simplification. The regex thus has only the following characters:

```
*()|10

```

It is interpreted as follows:

1. `*` is Kleene star (repeat left group or literal 0 or more times).
2. `|` is alternation (match if either the regex to the left or the regex to the right matches).
3. `()` is grouping.
4. `1` matches character 1.
5. `0` matches character 0.

## How to compile?

You specify six code snippets: one to replace each regex character. For example, if your answer is:

> `*` : `FSAGFSDVADFS`
> `|` : `GSDGSAG`
> `(` : `GSDG`
> `)` : `GDSIH`
> `1` : `RGIHAIGH`
> `0` : `GIHEBN`

Then you replace each regex with its respective code snippet, so:

```
(0|11)*

```

is turned into:

```
GSDGGIHEBNGSDGSAGRGIHAIGHRGIHAIGHGDSIHFSAGFSDVADFS

```

## What is the resulting program supposed to do?

Your program will:

1. Take the input.
2. Output a truthy value if the regex matches whole input.
3. Else output a falsy value.

Input outside `01` is consindered undefined behavior. Input can be empty.

## Additional rules

1. For a given regex character, the resulting snippet must always be the same.
2. There is no prefix or suffix character added afterwards.
3. The regex is guaranteed to be nonempty.

## Scoring

The least combined snippet is the winner. So the score for the example case would be calculated as follows:

`FSAGFSDVADFS` \+ `GSDGSAG` \+ `GSDG` \+ `GDSIH` \+ `RGIHAIGH` \+ `GIHEBN`

12 + 7 + 4 + 5 + 8 + 6 = 42

# Answer
> 9 votes
# Snails, 48 bytes

`0` -\> `)0(\0!(l.)(~`

`1` -\> `)0(\1!(l.)(~`

`(` -\> `)0({{(`

`)` -\> `)0}}(~`

`|` -\> `)0}|{(`

`*` -\> `)0),(~`

If we had to search for partial matches rather than matching only the full input, then it would be very easy. `0` would become `\0`, `1` would become `\1`, `*` would become `,`, and the others would map to themselves. Instead there are a lot of shenanigans to prevent matches from starting somewhere other than the beginning or ending somewhere other than the end. `!(l.)` is an assertion that will fail if the beginning of the match is not at the beginning of the input. `~` matches a cell outside of the input, so it is added to all the characters that are allowed to be at the end of the regex. If there is another regex character following, it is canceled out by a numerical quantifier `0` which requires it to be matched 0 times, essentially commenting it out. To allow `*` (`,`) to work correctly despite the dummy out-of-bounds test being in the way, the language's bracket matching rules are heavily used. From the documentation:

> Matching pairs of parentheses `()` or curly braces `{}` will behave as expected (like parentheses in regex), but it is also possible to leave out one half of a pair and have it inferred, according to the following rules. `)` or `}` groups everything to the left until the nearest unclosed group opening instruction of the same type(`(` or `{` respectively), or the beginning of the pattern if none exists. It closes any unclosed opening instructions of the opposite type in the middle of this range. An otherwise unmatched `(` or `{` is closed by the end of the pattern.

Clear as mud, right?

# Answer
> 8 votes
# CJam, 151 bytes

```
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

```

The lines correspond to the characters `01(|)*` (in that order). Try it online!

This uses no built-in regular expression or other types of pattern matching. In fact, CJam has neither of these features. Instead, it starts from the regular expression it represents and builds all possible strings it *could* match, to finally check if the user input is one of them.

### Test runs

The following uses a program that reads a regular expression from STDIN, replaces each of its characters by the proper snippet, and finally evaluates the generated code to see if it matches the input specified in the command line argument.

```
$ cat regex.cjam
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

"N%ers~
$ cjam regex.cjam '' <<< '(|)'
1
$ cjam regex.cjam '0' <<< '(|)'
0
$ cjam regex.cjam '' <<< '0(|)'
0
$ cjam regex.cjam '0' <<< '0(|)'
1
$ cjam regex.cjam '' <<< '(0|11)*'
1
$ cjam regex.cjam '0' <<< '(0|11)*'
1
$ cjam regex.cjam '11' <<< '(0|11)*'
1
$ cjam regex.cjam '011011000' <<< '(0|11)*'
1
$ cjam regex.cjam '1010' <<< '(0|11)*'
0

```

Unfortunately, this isn't particularly fast. It will choke rather quickly if there are more than 9 characters in the input or more than a single Kleene star in the regex.

At the cost of 5 extra bytes – for a total of **156 bytes** – we can generate shorter strings to match the potential input against and deduplicate them. This doesn't change how the code works; it just makes it more efficient.

```
$ cat regex-fast.cjam
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+eas,)m*:sSf-L|\"T

"N%ers~
$ cjam regex-fast.cjam '0101001010' <<< '(01|10)*'
0
$ cjam regex-fast.cjam '011001101001' <<< '(01|10)*'
1
$ cjam regex-fast.cjam '0' <<< '(0*1)*'
0
$ time cjam regex-fast.cjam '101001' <<< '(0*1)*'
1

```

---
Tags: code-golf, source-layout, regular-expression
---


title: Shortened words

text:
# Question
Title: Shortened words
My cell phone carrier charges a cent per character in a text! I need a program to shorten the words for me, while still being understandable. I will be texting this program to my friends, so it needs to be as short as possible.

Your program will take a String (a word is separated by a non-alphanumeric character) of words from `STDIN` (or closest alternative) reduce any similar (`a` and `A` are similar, `b` and `a` are not, `1` is similar only to itself) consecutive alphanumeric characters down to one character, and remove all the vowels (`aeiou`), and print it to `STDOUT` (or closest alternative), only letters, numbers, and spaces are kept: everything else is removed at the end. The first character of a word must remain the same, and only shorten the word if the resulting shortened word is 4 or more characters long. Examples:

```
homework -> hmwrk
llamas -> llamas (lms<4 characters)
botany -> btny
y3333llow -> y3lw
shorten -> shrtn
aabcddde -> abcd
abb'bbc -> abbbbc (abb -> abb and bbc -> bbc = abb'bbc --(remove non-alphanumeric-space characters)-> abbbbc)
SHARRRKnado -> shrknd (or with capitalization bonus: SHrKnd)
abracadabra -> abrcdbr
everything is awesome! -> evrythng is awsm
you can't break what is already broken -> you cant break what is alrdy brkn
the person's cat's bed's blanket's poka-dots are orangy-yellow -> the prsns cats beds blnkts pokadots are orngyyellow

```

-5% bonus if kept `a i o` or `u` at end of word

```
sharknado -> shrkndo
abracadabra -> abrcdbra

```

-10% bonus if kept capitalization of non-consecutive characters

```
aAbCDdDE -> abCd

```

This is so the shortest program in bytes wins.

# Answer
# CJam, 54 bytes

```
qelS/" ,"*__eu&S-A,s-NerN%{_(\"aeiou"-+e`1f=_S-Z>\@?}/

```

Try this fiddle or this test suite in the CJam interpreter.

### How it works

```
qel        e# Read all input and cast to lowercase.
S/" ,"*    e# Replace spaces with " ,". This way, we don't have to consider
           e# spaces word delimiters, which will make them easier to preserve.
__eu       e# Push two copies and convert the second one to uppercase.
&          e# Intersect the copies. This will keep only non-letters.
S-A,s-     e# Remove spaces and digits from the non-letters.
Ner        e# Replace their occurrences in the input with linefeeds.
N%         e# Split at linefeeds.
{          e# For each resulting chunk:
  _(\      e#   Push a copy and shift out the first character.
  "aeiou"- e#   Remove all vowels from the tail.
  +        e#   Concatenate the result with the first character.
  e`       e#   Perform run-length encoding.
  1f=      e#   Select all characters.
  _S-      e#   Push a copy and remove spaces.
           e#   This is for the length check; spaces don't actually form part
           e#   of the word.
  Z>       e#   Discard the first three characters.
  \@?      e#   If there are characters left, pick the modified word; else
           e#   pick the unmodified one.
}/         e#

```
> 2 votes

# Answer
# Japt, 57 bytes ~~58 80 88 90 95 98~~

*Saved 6 bytes thanks to @ETHproductions*

**Japt** is a shortened version of **Ja**vaScri**pt**. Interpreter

```
Uv qS m@(A=Xg0 +Xs1 r"(.)\\1+",@Y r"[aeiou]",P)g3 ?A:X)qS

```

Uses RegExp to do most of the work.

Try it online

## Explanation

This explanation is old but the method used is still generally the same.

```
UqS       // Splits input
   m@     // Loops through words
     Xr"(.)\\1+","$1"     // Removes consecutive sequences
      r"[aeiouAEIOU]",P   // Removes vowels
   m@     // Loops again
     Xl >3?               // If length of word is greater than 3
           X[0]==UqS [Y][0]?  // If first letter is right, keep it
              X
           :UqS [Y][0]+X      // Otherwise, use the correct first letter
     :UqS [Y]  qS v       // Otherwise return the original word

```
> 5 votes

# Answer
# TeaScript, 60 bytes ~~64 58 63 70~~

```
xL¡l»(b=l0+lS(1)g(/(.)\1+/,"$1")g`[aeiou]`)n>3?b:l,ø)O`a-z `

```

I should be able to use the unique function to get rid of repeated characters but for now I'm using a regex.

I believe this should work fine. I'll be heading off to sleep so notify me if anything is wrong and I'll address it next morning.

### Ungolfed

```
xL()l(#(b=l0+lS(1)g(/(.)\1+/,"$1")g`[aeiou]`)n>3?b:l,` `)O`a-z `

```
> 4 votes

# Answer
# C# - 404 bytes

```
using System;using System.Text;using System.Text.RegularExpressions;class j{static bool v(char l){return l=='e'||l=='a'||l=='o'||l=='i'||l=='u';}static void Main(){string a=Console.ReadLine();string z=Regex.Replace(a,"[^a-zA-Z ]","");string[]b=z.Split(' ');string c="";foreach(string d in b)    {if(d.Length>4){foreach(char e in d.ToCharArray()){if(!v(e))c+=e;}}else{c+=d;}c+=' ';}Console.WriteLine(c);}}

```

It takes input from Console.ReadLine(). I used a regex to find the non alphanumeric characters and spaces and I calculated if the size is less than 4. I tested using the final example.

# C# - 279 bytes (from LegionMammal798)

```
using C=System.Console;class j{static void Main(){var c="";foreach(var d in System.Text.RegularExpressions.Regex.Replace(C.ReadLine(),"[^a-zA-Z0-9 ]",c).Split(' ')){if(d.Length>4){foreach(var e in d)if(!"aeiou".Contains(e.ToString()))c+=e;}else c+=d;c+=' ';}C.Write(c);}}

```

Thank you for the golfing tips!
> 2 votes

# Answer
# , 57 chars / 97 bytes (noncompetitive)

```
Ɱ(ï,↪(a=$ù⬮ċ/⊙\1+⌿,`⑴”ċ/[ᶌ]⌿,⬯⸩Ꝉ>3?a⎖0≔$⎖0?a:$⎖0+a:$,⬭,⬭)

```

`Try it here (Firefox only).`

Uses regex aliasing and other syntax made after the challenge was posted.
> 2 votes

# Answer
# Haskell, ~~187~~ 176 bytes

Adhering to written description, not given examples:

```
import Data.List
import Data.Char
f=filter
d w@(_:_:_:_)=map head$groupBy(\a b->toLower a==toLower b)w
d w=w
s=unwords.map(f isAlphaNum.d.(\(h:t)->h:f(`notElem`"aeiou")t)).words

```

Call `s`.

Improved late after vote reminded me of its existence.
> 2 votes

---
Tags: code-golf, string
---


title: Digital Cellular Automata

text:
# Question
Title: Digital Cellular Automata
Write a program or function that takes in an odd positive integer N and a string of decimal digits (`0123456789`). The string represents a ten-state one-dimensional cellular automaton. Each digit occupies one cell and the update rule from one generation to the next is that every cell becomes the digit resulting from the sum of the N cells centered on the cell, modulo 10.

The first and last cells wrap around as if neighbors, so cells can always have N cells centered on them. Note that N may be larger than the length of the string, which means it could wrap around multiple times and some digits will accordingly be in the sum multiple times.

As an example, if N is 7 and the string is `038`, to visualize the cells to sum we can write `038` repeating infinitely in both directions

```
...038038038038038...

```

then the digit that the `0` will change into is the sum of the 7 digits centered around any `0`, modulo 10:

```
...038038038038038...
      ^_____^
         |
    sum all these

```

This is `(0+3+8+0+3+8+0)%10`, which is `2`.

Similarly the digits the `3` and `8` change into are defined by `(3+8+0+3+8+0+3)%10` = `5` and `(8+0+3+8+0+3+8)%10` = `0` respectively.

Thus, the generation after `038` is `250` when N is 7.

Your program or function needs to print or return the digit string of the very next generation of the input digit string. i.e. apply the update rule once to each cell and give the output. **The shortest code in bytes wins.**

# Test Cases

```
[digit string] -> [N = 1], [N = 3], [N = 5], [N = 7], [N = 9], [N = 43]
0 -> 0, 0, 0, 0, 0, 0
1 -> 1, 3, 5, 7, 9, 3
2 -> 2, 6, 0, 4, 8, 6
3 -> 3, 9, 5, 1, 7, 9
4 -> 4, 2, 0, 8, 6, 2
5 -> 5, 5, 5, 5, 5, 5
6 -> 6, 8, 0, 2, 4, 8
7 -> 7, 1, 5, 9, 3, 1
8 -> 8, 4, 0, 6, 2, 4
9 -> 9, 7, 5, 3, 1, 7
00 -> 00, 00, 00, 00, 00, 00
07 -> 07, 47, 41, 81, 85, 47
10 -> 10, 12, 32, 34, 54, 12
11 -> 11, 33, 55, 77, 99, 33
12 -> 12, 54, 78, 10, 34, 54
34 -> 34, 10, 78, 54, 12, 10
66 -> 66, 88, 00, 22, 44, 88
80 -> 80, 86, 46, 42, 02, 86
038 -> 038, 111, 294, 250, 333, 472
101 -> 101, 222, 343, 545, 666, 989
987 -> 987, 444, 901, 765, 222, 543
1234 -> 1234, 7698, 3412, 9876, 1234, 7698
26697 -> 26697, 54128, 00000, 56982, 84413, 54128
001002 -> 001002, 211122, 331332, 335334, 455544, 113112
129577020 -> 129577020, 326194923, 474081605, 961120291, 333333333, 183342413
6023845292173530 -> 6023845292173530, 6853571632015189, 1197228291289874, 9238433109901549, 0110956118726779, 1982123699138828
```

# Answer
# Pyth, ~~20~~ 19 bytes

*1 byte thanks to @FryAmTheEggman.*

```
sm`esmv@z-+dk/Q2Qlz

```

Try it online. Test suite.
> 7 votes

# Answer
## CJam, 21 bytes

```
l~_,\2/f-l:~fm>:.+Af%

```

Test it here.

### Explanation

```
l~   e# Read and evaluate N.
_,   e# Duplicate and turn into range [0 1 ... N-1]
\2/  e# Swap with other copy and (integer) divide by 2.
f-   e# Subtract this from each element in the range to get
     e# [-(N-1)/2 ... -1 0 1 ... (N-1)/2]
l:~  e# Read string and evaluate each digit separately.
fm>  e# Make one copy of the result for each element i in the range, shifting the array
     e# i cells to the right, cyclically.
:.+  e# Sum the columns of the resulting matrix.
Af%  e# Take each of those sums modulo 10.

```
> 10 votes

# Answer
# Mathematica, 85 bytes

```
""<>ToString/@CellularAutomaton[{Tr@#~Mod~10&,{},#/2-1/2},FromDigits/@Characters@#2]&

```
> 5 votes

# Answer
## Python 3, ~~114~~ ~~92~~ ~~86~~ 80 bytes

Took off 6 bytes thanks to **Sp3000** and another 6 bytes thanks to **xnor**!

```
a=lambda N,D,i=0:D[i:]and str(int((D*N)[(i-N//2)%len(D):][:N],11)%10)+a(N,D,i+1)

```

Defines a named function `a` that takes `N` and `D` as parameters, the N and digit string defined in the challenge.

### Explanation

In Python 3, `and` between two strings will end up being the latter. Hence, `D[i:]and ...` short-circuits once all center positions have been iterated over as `D[i:]` will be an empty string and therefore falsy. `(D*N)[(i-N//2)%len(D):][:N]` duplicates the digit string a bunch of times, then slices it in the right places to give the substring that has the correct digit as the center. Recall for a moment that the sum of the digits of a base 10 number modulo 9 is the same as the number itself modulo 9. `str(int(...,10)%10)` treats the resulting number-string as if it was base 11 and gets the remainder modulo 10, then converts back to string. Finally, `a(N,D,i+1)` moves on to the next center position. Because of the `+`, once the recursion is done, all of the resulting digits are lumped together and returned.
> 4 votes

# Answer
## Haskell, 92 bytes

String conversion is really expensive in Haskell...

```
x!n=last.show.sum.map(read.pure).take n.(`drop`cycle x).fst<$>zip[div(1-n)2`mod`length x..]x

```

This defines an infix function `!`, used as follows:

```
> "1234"!3
"7698"

```

## Explanation

On the right we have `[div(1-n)2`mod`length x..]`, which is just the infinite list of integers starting from `(1-n)/2` modulo `length(x)` (we take the modulus, since we want the first element to be non-negative). These correspond to the starting indices of the CA neighborhoods. We zip it with `x` just to obtain a list of the correct length.

The function `<$>` is the infix version of `map`, and its left argument is a function composition read from right to left. Thus for each integer in the above list (extracted with `fst`), we drop that many characters from `cycle x` (which is the concatenation of infinitely may copies of `x`), take `n` characters from the remainder, convert them to strings and then integers with `read.pure`, take their sum, convert that to string with `show`, and take the last character of that, which corresponds to the remainder mod 10.
> 3 votes

# Answer
# NARS2000 APL, 37 characters (72 bytes)

```
⎕←10⊥10∣+⌿⊃({⍵..-⍵}⌊⎕÷2)∘.⌽⊂49-⍨⎕AV⍳⍞

```

Explanation:

```
  ⎕←10⊥10∣+⌿⊃({⍵..-⍵}⌊⎕÷2)∘.⌽⊂49-⍨⎕AV⍳⍞
⍝ ⎕←                                    output
⍝   10⊥                                 the base-10 digits in
⍝      10∣                              the modulo-10
⍝         +⌿                            column-wise sum of
⍝           ⊃                           the matrix version of
⍝                         ∘.⌽           the outer-product rotation of
⍝                            ⊂            the scalar version of
⍝                                 ⎕AV⍳    the index in the atomic vector of
⍝                                     ⍞   an input string
⍝                             49-⍨        minus 49 ('0' + 1)
⍝                                       by
⍝             {⍵..-⍵}                     the range ⍵ to -⍵, where ⍵ is
⍝                    ⌊                    the floor of
⍝                     ⎕                   an input integer
⍝                      ÷2                 divided by 2

```
> 2 votes

# Answer
# Octave, 64 bytes

```
@(s,n)["" mod(sum(bsxfun(@shift,s'-48,(1:n)-ceil(n/2))'),10)+48]

```
> 1 votes

# Answer
# J, 41 bytes

```
"."0@]{~(1":10|+/@:)#@]|-:@<:@[-~(+/&i.#)

```

Turned out longer than I expected. Should be golfable.

We generate a matrix with elements in a row showing the positions whose values should be added (mod 10) to get sum for a position.

Usage:

```
   7 ("."0@]{~(1":10|+/@:)#@]|-:@<:@[-~(+/&i.#)) '038'
250

```

Try it online here.
> 1 votes

---
Tags: code-golf, number, arithmetic, sequence, cellular-automata
---


title: Reverse Boustrophedon Text

text:
# Question
Title: Reverse Boustrophedon Text
Boustrophedon is a type of bi-directional text where successive lines alternate between reading left-to-right and right-to-left. Character direction was also mirrored with respect to reading direction. In reverse boustrophedon writing systems, characters were rotated 180 instead of mirrored.

# Challenge

Write a program/function that accepts a string of text and a number of columns, and outputs the string formatted into the specified number of columns with alternating lines flipped upside down.

# Input

Your program should accept two arguments:

* S, the string of text to format
* N, the number of columns

# Output

Your program should output S wrapped in N columns with alternating lines flipped 180 degrees.

* The reading direction of the first line is always left-to-right.
* Don't worry about where to place line breaks, lines can be split at any character, no hypenation of words required.
* You may assume input string will not contain any line breaks.

Here are the characters your program should support with their flipped counterparts:

```
Uppercase:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
∀qƆpƎℲפHIſʞ˥WNOԀQɹS┴∩ΛMX⅄Z

Lowercase:
abcdefghijklmnopqrstuvwxyz
ɐqɔpǝɟƃɥᴉɾʞlɯuodbɹsʇnʌʍxʎz

Punctuation:
&_?!"'.,
⅋‾¿¡„,˙'

```

# Test Cases

```
S: The quick brown fox jumps over the lazy dog.
N: 30
Output:
The quick brown fox jumps over
                ˙ƃop ʎzɐl ǝɥʇ

```

---

```
S: Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque vel libero arcu. Nunc dictum elementum lectus nec aliquet. Donec dolor nunc, sodales at dolor rhoncus, hendrerit scelerisque purus. Pellentesque vel sagittis libero, et rutrum leo. Nullam vulputate enim et massa dictum, vitae venenatis augue lobortis. Fusce sollicitudin ultrices consequat. Vestibulum quis nunc non tortor eleifend facilisis. In at nunc elit. Aliquam pellentesque, lectus quis aliquam posuere, quam lectus sagittis metus, ut auctor sem quam a neque. Integer rhoncus lobortis nisl. Pellentesque mi dui, laoreet in metus quis, mollis accumsan est. Nunc dignissim tortor ac eleifend tempus. Ut ut tellus aliquam, luctus nulla quis, consectetur nunc. Suspendisse viverra molestie condimentum. Curabitur et hendrerit augue.
N: 50
Output:
Lorem ipsum dolor sit amet, consectetur adipiscing
uǝɯǝlǝ ɯnʇɔᴉp ɔunN ˙nɔɹɐ oɹǝqᴉl lǝʌ ǝnbsᴉnQ ˙ʇᴉlǝ
tum lectus nec aliquet. Donec dolor nunc, sodales
lǝԀ ˙snɹnd ǝnbsᴉɹǝlǝɔs ʇᴉɹǝɹpuǝɥ 'snɔuoɥɹ ɹolop ʇɐ
lentesque vel sagittis libero, et rutrum leo. Null
sᴉʇɐuǝuǝʌ ǝɐʇᴉʌ 'ɯnʇɔᴉp ɐssɐɯ ʇǝ ɯᴉuǝ ǝʇɐʇndlnʌ ɯɐ
 augue lobortis. Fusce sollicitudin ultrices conse
ɔɐɟ puǝɟᴉǝlǝ ɹoʇɹoʇ uou ɔunu sᴉnb ɯnlnqᴉʇsǝΛ ˙ʇɐnb
ilisis. In at nunc elit. Aliquam pellentesque, lec
ʇǝɯ sᴉʇʇᴉƃɐs snʇɔǝl ɯɐnb 'ǝɹǝnsod ɯɐnbᴉlɐ sᴉnb snʇ
us, ut auctor sem quam a neque. Integer rhoncus lo
snʇǝɯ uᴉ ʇǝǝɹoɐl 'ᴉnp ᴉɯ ǝnbsǝʇuǝllǝԀ ˙lsᴉu sᴉʇɹoq
 quis, mollis accumsan est. Nunc dignissim tortor
u snʇɔnl 'ɯɐnbᴉlɐ snllǝʇ ʇn ʇ∩ ˙sndɯǝʇ puǝɟᴉǝlǝ ɔɐ
ulla quis, consectetur nunc. Suspendisse viverra m
˙ǝnƃnɐ ʇᴉɹǝɹpuǝɥ ʇǝ ɹnʇᴉqɐɹnƆ ˙ɯnʇuǝɯᴉpuoɔ ǝᴉʇsǝlo

```

# Answer
> 5 votes
# Bash + GNU utilities, 204

```
fold -$1|sed 2~2{s/.\\+/printf\ %$1's "`echo "&"|rev`"/e
y/'`printf %s {A..Z} {a..z}`"&_?!\"'.,/∀qƆpƎℲפHIſʞ˥WNOԀQɹS┴∩ΛMX⅄Zɐqɔpǝɟƃɥᴉɾʞlɯuodbɹsʇnʌʍxʎz⅋‾¿¡„,˙'/
}"

```

N is given on the command line and S is given via STDIN:

```
$ echo "The quick brown fox jumps over the lazy dog." | ./boustrophedon.sh 30
The quick brown fox jumps over
                ˙ƃop ʎzɐl ǝɥʇ
$

```

### Explanation

* `fold -N` splits the input into lines of length N.
* The rest of the processing is done by sed, line-by-line:
    + `2~2` matches every other line, starting at line 2
    + `s/.+/printf %'N's "`echo "&"|rev`"/e` uses GNU Sed's exec feature to call a shell to reverse the line and left-pad it with up to N spaces
    + `y/ABC.../∀qƆ.../` transform characters

Note `ABC...` is generated using a bash expansion and printf. Also some fancy quoting for all the different characters.

# Answer
> 3 votes
# Japt, ~~182~~ 179 bytes

**Japt** is a shortened version of **Ja**vaScri**pt**. Interpreter

```
Ur'.+".?"pV-1 ,@A++%2?SpV-Xl)+Xw m@"„\xA1⅋,'˙¿∀qƆpƎℲפHIſʞ˥WNOԀQɹS┴∩ΛMX⅄Z[\\]^‾`ɐqɔpǝɟƃɥᴉɾʞlɯuodbɹsʇnʌʍxʎz"g(Q+"!&',.?"+65o124 m@Xd)a)bX)||X +R:X+R

```

### How it works

```
             // Implicit: U = input string, V = input number, A = 10
Ur           // Take U and replace each group X of:
'.+".?"pV-1  //  at least one char, followed by up to V-1 other chars
             //   literally: RegExp("." + ".?".repeat(V-1))
@            // with: (@ is compiled to (X,Y,Z)=>)
A++%2?       //  If we're on an odd row:
SpV-Xl)+     //   Pad it with spaces, then concatenate it with
Xw m@        //   X reversed, with each character X mapped to:
"..."g       //   The character at position N in the string, where N is:
(Q+"!&',.?"  //    Build a string from a quote mark and these chars,
65o124 m@Xd)a) //   and all chars from A..z.
bX)          //    Return the index of X in this string.
||X          //   or if this number is outside the string, default to the original char.
+R           //   Either way, add a newline.
:X+R         //  Otherwise, return the original row text plus a newline.
             // Implicit: output last expression

```

There are a couple of problems, but they shouldn't affect the validity of the program:

1. User @Vɪʜᴀɴ has recently helped me implement Unicode Shortcuts, or single characters in the range 00A1-00FF that stand in for commonly-used several-char sequences. The problem with this is that it currently replaces inside strings, so we can't use ¡ directly in the string for now. The safe alternative, `\xA1`, is three bytes longer.
2. It's currently impossible to input a double-quote character. This will be fixed shortly.

Perhaps there's a way to shorten the string. Suggestions are welcome!

# Answer
> 2 votes
## Javascript (ES6), ~~407~~ ~~400~~ ~~366~~ ~~360~~ 353 bytes

I'm counting only the first two "lines" in this snippet as the total count, as the rest of it is code to run it.

```
s=`ABCDEFGHIJKLMNOPQRSTUVWXYZ∀qƆpƎℲפHIſʞ˥WNOԀQɹS┴∩ΛMX⅄Zabcdefghijklmnopqrstuvwxyzɐqɔpǝɟƃɥᴉɾʞlɯuodbɹsʇnʌʍxʎz&_?!"'.,⅋‾¿¡„,˙'`,f=(i,w)=>(i=i.match(RegExp(`.{1,${w}}`,"g")),i.map((c,x)=>x%2?" ".repeat(w-c.length)+[...c].reverse().map(b=>(d=s.indexOf(b),"A"<=b&&"z">=b?s[d+26]:" "==b?b:s[d+8])).join``:c).join`
`)

let input = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque vel libero arcu. Nunc dictum elementum lectus nec aliquet. Donec dolor nunc, sodales at dolor rhoncus, hendrerit scelerisque purus. Pellentesque vel sagittis libero, et rutrum leo. Nullam vulputate enim et massa dictum, vitae venenatis augue lobortis. Fusce sollicitudin ultrices consequat. Vestibulum quis nunc non tortor eleifend facilisis. In at nunc elit. Aliquam pellentesque, lectus quis aliquam posuere, quam lectus sagittis metus, ut auctor sem quam a neque. Integer rhoncus lobortis nisl. Pellentesque mi dui, laoreet in metus quis, mollis accumsan est. Nunc dignissim tortor ac eleifend tempus. Ut ut tellus aliquam, luctus nulla quis, consectetur nunc. Suspendisse viverra molestie condimentum. Curabitur et hendrerit augue.";
console.log(f(input, 50));
```

### Explanation

```
s=`A∀ .. ZZaɐ .. &⅋ ..`,                            //Character translation "map"
f=(i,w)=>                                           //Create a function named "f" that takes an (i)nput string and (w)idth
    (                                               //Implicitly return
        i=i.match(RegExp(`.{1,${w}}`,"g")),         //Cut string into arrays every w-th match of anything
        i.map((c,x)=>                               //Loop through each element in array by (c)ut at inde(x)
            x%2                                     //If the index is odd
                ?" ".repeat(w-c.length)                 //Output spaces for padding
                    +[...c].reverse()                   //Split this cut into each character, and read it backwards
                    .map((b,d)=>(                       //Translate each character
                        d=s.indexOf(b),                 //Save where this character appears in the mapping
                        "A"<=b&&"z">=b                  //If the character is a-zA-Z
                        ?s[d+26]                            //Print the flipped character by looking 26 characters ahead of where this character is found
                        :" "==b                             //Else, if it's a space
                            ?b                              //Output the space
                            :s[d+8]))                   //Else, print the flipped punctuation character (only 8 of these)
                    .join``                         //Join everything back into a continuous string
                :c                                  //Else just output the whole cut
            ).join`
`)                                                  //Finally join each cut by a newline

```

---

* Thanks to Dendrobium for -6 bytes!
* Thanks to the Closure Compiler for -34 bytes!
* Thanks to ןnɟuɐɯɹɐןoɯ for -7 bytes!

# Answer
> 2 votes
# CJam, 152

```
l~_q/\f{Se]}2/{)26,'Af+_el+"&_?!'.,"`+"∀qƆpƎℲפHIſʞ˥WNOԀQɹS┴∩ΛMX⅄Zɐqɔpǝɟƃɥᴉɾʞlɯuodbɹsʇnʌʍxʎz„⅋‾¿¡,˙'"erW%}%N*

```

Test it here.

I guess I should look into compressing that Unicode string a bit...

# Answer
> 1 votes
# Pyth, 141 bytes

```
FNrZlKczQI%N2X.[" "Q_@KN++GrG1"&_?!\"'.,""ɐqɔpǝɟƃɥᴉɾʞlɯuodbɹsʇnʌʍxʎz∀qƆpƎℲפHIſʞ˥WNOԀQɹS┴∩ΛMX⅄Z⅋‾¿¡„,˙'")E@KN

```

Tested with an online Pyth Compiler.

**How it Works**

```
FNrZlKczQI%N2X.[" "Q_@KN)E@KN    █
                                 █
FN                               █ For N in
  r                              █  ├ Range
   Z                             █  |  ・Start: 0
                                 █  |  ・End:
    l                            █  |     Length of
     K                           █  |      └─K =
      c                          █  |         Split
       z                         █  |           ・String z
        Q                        █  |           ・By input int Q
         I%N2                    █  └─If divisible by 2
             X                   █     └─Translate
                                 █         ├─Source:
              .[                 █         | ├─Pad left
                " "              █         | |   ・With spaces
                   Q             █         | |   ・Until input int Q
                    _            █         | └──Reverse
                     @KN         █         |     ・Nth line of K
                        ++GrG1...█         ├─From: Normal  (See below)
                        "ɐqɔpǝ...█         └─To:   Flipped (See below)
                        )E@KN    █     Else print Nth line of K

```

**Map**

Normal

```
++                               █　Append:
  G                              █  1) a to z
   rG1                           █  2) A to Z
      "&_?!\"'.,"                █  3) Punctuation

```

Flipped (Nothing fancy)

```
"ɐqɔpǝɟƃɥᴉɾʞlɯuodbɹsʇnʌʍxʎz∀qƆpƎℲפHIſʞ˥WNOԀQɹS┴∩ΛMX⅄Z⅋‾¿¡„,˙'"

```

# Answer
> 0 votes
# Python, ~~453~~ 363 bytes

```
s,n=input()
o="""ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz&_?!"'.,"""
p="""∀qƆpƎℲפHIſʞ˥WNOԀQɹS┴∩ΛMX⅄Zɐqɔpǝɟƃɥᴉɾʞlɯuodbɹsʇnʌʍxʎz⅋‾¿¡„,˙'""".decode('utf8')
s=map(''.join,zip(*[iter(s+' '*(n-1))]*n))
for i in range(len(s)):
 if i%2:s[i]=''.join(p[o.find(c)].encode('utf8')for c in s[i][::-1])
for l in s:print l

```

---
Tags: code-golf, unicode, typography
---


title: Drawing Lewis Structures of Alkanes

text:
# Question
Title: Drawing Lewis Structures of Alkanes
I just had a lesson in school about alkanes and figured it would probably make for a great code golf challenge! Don't worry, it isn't as complicated as it may look!

# A Quick Rehash

(Please Note: To keep this brief, not all information is 100% accurate.)

Alkanes are strings of carbon and hydrogen. Every carbon atom has 4 bonds, and every hydrogen atom 1 bond. All the carbon atoms of the alkane form a string where each C-atom is connected to 2 other C-atoms (left and right in the Lewis structure) and 2 H-atoms (up and down), except for the ends of the string, where the C-atom is connected to only 1 other C but 3 Hs. Here's a basic example for pentane (an alkane with 5 C-atoms and 12 H-atoms):

```
  H H H H H
  | | | | |
H-C-C-C-C-C-H
  | | | | |
  H H H H H

```

Alkanes also can have branches. But don't worry, all alkanes in this challenge can be expressed with only 1 level of branching. Example:

```
        H
        |
      H-C-H
  H H H | H
  | | | | |
H-C-C-C-C-C-H
  | | | | |
  H H H H H

```

For completing this challenge you also must understand the IUPAC naming convention for branched alkanes. First of there's the root alkane. In our previous example, this would be the "C-C-C-C-C" part. Depending on how long this chain is, it has a different name. 1 C is called methane, 2 C ethane, 3 C propane, then butane, pentane, hexane, heptane, octane, nonane and decane (10 C). Then, for each branch, there's a certain prefix to that: First of, there's the index (offset) of the C-atom the branch is appended to (count from the left). In the example, this would be 4 (aka it's the 4th C-atom from the left). Then there's a hyphen (this symbol: "-") and after that another name indicating the size of the branch. The naming of the size of the branch is almost same like the naming of the size of the root, just that instead of "ane" you append "yl". With that the full name of the example would be

```
4-methylpentane

```

If you have multiple branches, then they are prepended as well, separated by another hyphen. Example:

```
2-butyl-5-methylhexane

```

One last thing: if you have multiple branches of the same size, they get grouped; their offsets are separated by comma and they share the same size-name, which gets prepended by an extra syllable depending on how many branches are grouped: "di" for 2 branches, "tri" for 3, "tetra" for 4 (you don't need more for this challenge). Example:

```
2-ethyl-2,4,6-trimethyldecane

```

FYI, this *could* look somewhat like this: (Omitted H-atoms)

```
   |
  -C-
   |       |
  -C-     -C-
 | | | | | | | | | |
-C-C-C-C-C-C-C-C-C-C-
 | | | | | | | | | |
  -C- -C-
   |   |

```

# Nomenclature Cheatsheet

```
Prefixes indicating numbers:
| Num  | Prefix |
|------|--------|
| 1    | meth   |
| 2    | eth    |
| 3    | prop   |
| 4    | but    |
| 5    | pent   |
| 6    | hex    |
| 7    | hept   |
| 8    | oct    |
| 9    | non    |
| 10   | dec    |
Suffix root:   ane
Suffix branch: yl
Prefixes grouping: di, tri, tetra

```

# The Rules

Write a program that reads in such an IUPAC name from STDIN, program arguments or equivalent and draws it as an ASCII-art lewis structure to STDOUT (or equivalent).

* For simplicity, you DO NOT have to draw the H-atoms (Else you will run into spacing issues)
* You are NOT allowed to print any empty leading or trailing horizontal lines
* The chains you have to parse won't be any longer than 10, and the maximum of branches in a "group" is limited to 4.
* The maximum "offset" of a branch is 9 (meaning that you don't have to parse more than 1 digit)
* Your branches have to alternate between going up and down after every new branch. In case this space is already taken by another branch at the same offset, you have to draw it on the other side of the root. (up-\>down, down-\>up)
* On corrupt, not-correctly-formatted or otherwise not-drawable input, your program may behave unspecified.

This is code golf, shortest code in bytes wins!

Happy golfing! :)

# Answer
# Python 2, 620 bytes

```
import re
i=input()
s='m|e|pr|b|p|hex|h|o|n|de';d=dict(zip(s.split('|'),range(1,11)))
z=[[eval('['+a+']'),d[b]]for a,b in re.findall('(?:(\d[,\d]*).*?[\-ia]|l)('+s+')',i[:-3])]
v=z[-1][1]
l=[[0,0]for _ in range(v)]
c=0
for a,b in sorted([(i,b)for a,b in z[:-1]for i in a]):l[a-1][c]=b;c=~c
m=[max(x) for x in zip(*l)]
L,R=[[[' 'for _ in '_'*2*i]for _ in '_'*(2*v+1)]for i in m]
c=[' |'*v+' ']
C=c+['-C'*v+'-']+c
for i in range(len(l)):
 X=L;q=2*i+1
 for a in l[i]:
  if a>0:
   for j in range(0,2*a,2):
    X[q][j]='C'
    X[q-1][j]=X[q+1][j]='-'
    X[q][j+1]='|'
  X=R
for l in zip(*L)[::-1]+C+zip(*R):print ''.join(l)

```

---

### Explanation

Input: `'2-ethyl-2,4,6-trimethyldecane'`

First parses to string with regex (last group is root):

`[[[2], 2], [[2, 4, 6], 1], [[], 10]]`

Each branch is written in an array of length `len(root)` (Alternating up/down is handled here):

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

'Left' and 'Right'(`L,R`) and 'root' (`C`) string branches are initialized.

Each branch is then added to the corresponding 'string' branch (big loop).

The two sides and center are printed at the end:

```
   |   |
  -C- -C-
 | | | | | | | | | |
-C-C-C-C-C-C-C-C-C-C-
 | | | | | | | | | |
  -C-     -C-
   |       |
  -C-
   |

```
> 5 votes

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


title: A game of locks and keys

text:
# Question
Title: A game of locks and keys
There are *n* boxes, numbered *1-n*. Each box is locked, such that it can be opened by only one corresponding type of key (also numbered *1-n*). These keys are randomly scattered in the boxes (one box may have any number of keys, one key may have any number of duplicates), and then all boxes are shut. A treasure (numbered *0*) has also been locked in many of the boxes.

You have hired a locksmith to retrieve all the treasure. He charges for each box he cracks open. There is no charge for opening a box for which the key is already available.

Input is the contents of each box. You can decide the format of the input.

**Output the minimum cost required to get the treasures.**

*Notes*

1. Your algorithm may take a long time, but that is irrelevant.
2. Shortest code wins.
3. No need to bother about invalid input.

**Sample data**

Here line *i* represents the keys present in box *i*.

Input

```
2 0
3
4 0
5 6 0
6
0

```

Output

```
1

```

Input

```
2 0
3 0

4 0
6
5 0

```

Output

```
3

```

Input

```
2 4 0
3 0

1 0
6
5 0

```

Output

```
2

```

Input

```
1
3 4

2 6
5

```

Output

```
0

```

# Answer
# CJam, ~~59~~ ~~52~~ ~~50~~ ~~49~~ ~~45~~ ~~43~~ 42 bytes

```
qN/ee::~e!{_0+{0a&}#>W%_{1$|(z@-},,\;}%:e<

```

*Thanks to @MartinBüttner for golfing off 3 bytes and paving the way for 4 more!*

Try it online in the CJam interpreter.

### How it works

```
qN/      e# Read all input and split it at linefeeds.
ee       e# Enumerate the lines.
         e# STACK: [[0 "i0 i1 ..."] [1 "j0 j1 ..."] ...]
::~      e# Apply ~ (bitwise NOT/evaluate) to each item of the pairs.
         e# STACK: [[-1 i0 i1 ...] [-2 j0 j1 ...] ...]
e!       e# Push all unique permutations of the resulting array.
{        e# For each permutation:
  _0+    e#   Push a copy and append 0 to it.
  {0a&}# e#   Find the first index of an element that contains 0.
  >      e#   Discard all previous elements of the array.
  W%     e#   Reverse the resulting array.
         e#   We now have a (partial) permutation that contains
         e#   all treasures and ends with a treasure.
  _      e#   Push a copy. The original (which contains lists, but no
              numbers) will serve as accumulator.
  {      e#   Filter; for each list in the array:
    1$|  e#     Push a copy of the accumulator and perform set union.
    (    e#     Shift out the first element (bitwise NOT of 0-based index).
    z    e#     Apply absolute value to push the 1-based index.
    @-   e#     Perform set difference with the former state of the
         e#     accumulator. This pushes an empty list iff the 1-based
         e#     index was already in the accumulator, i.e., iff we already
         e#     had a key.
  },     e#   Keep the element if we did not have the key.
  ,      e#   Count the kept elements.
  \;     e#   Discard the accumulator from the stack.
}%       e#
:e<      e# Get the minimum of all results.

```
> 6 votes

# Answer
## CJam (53 bytes)

```
Nq+N/:a::~:A,_m*_.&{,}$_{{_Af=e_|}:PA,*A,,^0-P0&!}#=,

```

This is rather too slow for the online interpreter.

### Dissection

```
Nq+N/:a::~:A      e# Parse the input into arrays and store in A
,_m*_.&           e# Generate (with duplicates) a powerset of [0 1 ... n]
{,}$              e# Sort by size
_{                e# Create a copy and search for first index satisfying...
  {_Af=e_|}:P     e#   Store in P a block which does a reachability expansion
  A,*             e#   Apply it n times (no path can be longer than n)
  A,,^0-          e#   Invert to get the unreached nodes (except 0)
  P               e#   Apply P again to see what's reached from the unreached nodes
  0&!             e#   Check that it doesn't include [0]
}#
=,                e# Look up the powerset element at that index and find length

```
> 2 votes

# Answer
# Haskell, 173 bytes

`l` is the one you wanna call.

Not sure whether I shouldn't use a pseudo-`Map` instead (`[(Int,[Int])]` instead of `[[Int]]`).

```
l=o[].map(map read).map words.lines
o[]b|0`notElem`concat b=0|0<1=1+minimum[o[n]b|n<-[1..length b],b!!(n-1)/=[]]
o(n:k)b=o(filter(/=0)(k++b!!(n-1)))(take(n-1)b++[]:drop n b)

```
> 0 votes

---
Tags: code-golf, graph-theory
---


title: Make America(n Maps) Great Again

text:
# Question
Title: Make America(n Maps) Great Again
### New Bonus! (See below)

The cartography team of U.S. Republican presidential hopeful Ben Carson is having some trouble with their maps (image via Washington Post):

The problem is they don't have the Right Tool For The Job™. They need the most compact and reliable program possible, so they never have to worry about making maps again. That's why they hired you. You need to take this map and output it again with the desired coloring:

> By Theshibboleth \[GFDL (http://www.gnu.org/copyleft/fdl.html) or CC-BY-SA-3.0 (http://creativecommons.org/licenses/by-sa/3.0/)\], via Wikimedia Commons

If you don't know where all the states are (because you are not an American...or you are an American), here is a map with all the names (Washington D.C. is not required for this challenge):

> "Map of USA with state names 2". Licensed under CC BY-SA 3.0 via Wikimedia Commons - https://commons.wikimedia.org/wiki/File:Map\_of\_USA\_with\_state\_names\_2.svg#/media/File:Map\_of\_USA\_with\_state\_names\_2.svg

For example if the input is `Ohio, Indiana, Illinois;New York, New Jersey, Florida`, you output:

The blank map image is available in SVG and PNG formats. For your convenience, here is a list of all 50 states in alphabetical order

This is a and challenge. Output must be as a SVG or image file. Simply displaying the output on the screen is not enough. Input must be taken from STDIN or by reading a text file. I am flexible with how you format the input, although it should contain the full names of each state, with red (Republican) states listed first and blue (Democratic) states second. Any two distinct shades of red and blue are acceptable for the coloring. Of course, you can have the blank map image in the same folder as your program with whatever file name you want.

## Accuracy Criteria

If your output is a raster file, it must be at least 800px by 495px, and the lines should not deviate from the result of scaling up the SVG to the same size by more than 1.5 pixels. If your output is a vector file, the lines should not deviate from the SVG by more than 1.5 pixels when both are scaled to 800px by 495px.

## Bonus!

Ben is trying to cut down dependence on foreign libraries, and is now offering a **-50%** bonus to anyone who uses only a raster graphics version of the map as input and creates their own algorithm for region detection. Ultimately, it is my judgment that determines whether your approach counts as "writing your own" algorithm.

Good Luck!

# Answer
# Python 626

In the approach below, I added .rstate and .bstate based on .state in the CSS description. In my I renamed the provided .svg file to `v.svg`. It takes an input as described below and writes to a file `w.png`. To transfer from the full state name to the abbreviated version I look them up based on the first and last two letters of the states.

```
r='Ama,Aka,Ana,Aas,Cia,Cdo,Cut,Dre,Fda,Gia,Hii,Iho,Iis,Ina,Iwa,Kas,Kky,Lna,Mne,Mnd,Mts,Man,Mta,Mpi,Mri,Mna,Nka,Nda,Nre,Ney,Nco,Nrk,Nna,Nta,Oio,Oma,Oon,Pia,Rnd,Sna,Sta,Tee,Tas,Uah,Vnt,Via,Won,Wia,Win,Wng'.split(',')
y='lkzraotelaidlnasyaedainsotevhjmycdhkraicdnxttaaviy'
v=open('v.svg','r')
s=v.read()
v.close()
k=s.find('.state')
j=s.find('.',k+1)
t=input().split(';')
w=open('w.svg','w')
k+=1
c='#E0E0E0'
s=s[:j]+'.r'+s[k:j].replace(c,'red')+'.b'+s[k:j].replace(c,'blue')+s[j:]
c='rb'
for j in range(2):
 for d in t[j].split(','):k=s.find('state '+d[0].lower()+y[r.index(d[0]+d[-2:])]);s=s[:k]+c[j]+s[k:]
w.write(s)
w.close()

```

Example input:

```
'California,Illinois,Iowa,Mississippi;New Mexico,Pennsylvania,South Dakota,Vermont'

```

Example output:

Or inspired by the flag of France:
> 8 votes

# Answer
# Processing, 425 bytes (259 bytes + 1 +165 byte file)

Code:

```
size(959,593);String[]a=loadStrings("a"),b=loadStrings("b");PShape m=loadShape("M.svg");m.disableStyle();for(int i=0;i<51;i++){fill(255);int r=0;for(String j:a){if(j.isEmpty())r++;if(j.contains(b[i]))fill(r>0?#0000FF:#FF0000);}shape(m.getChild(i));}save("m");

```

Blank map should be named "**M.svg**" and stored in a folder called **/data** (all other files are in the same folder as the program.)

Input File ("**a**"):

```
Mississippi
California
Connecticut

Delaware
Florida
Wyoming
Hawaii

```

Key File ("**b**"): http://pastebin.com/0pNufAH9

Output ("**m.tif**"):

Ok, here is my try at my own challenge. Some notes:

* The output map looks different from the input map in the following ways
    1. The input map had grey filling on a transparent background. The output has white filling on a gray background. I think this should be allowed, because white, gray, and transparency are all neutral.
    2. The output map is missing the lines around Hawaii and Alaska that the input had. Once again, I think this is ok because the lines are not a significant part of the map.
* The program uses an external file to hold keys. According to this meta post, I just need to add 1 byte for one additional file.

If anyone has any discrepancies with my self-adjudication of my code, feel free to leave a comment.

Also, if anyone is curious about trying this challenge in Processing, it supports both reading SVG files into `PShape`'s, as well as parsing SVG files as XML.
> 7 votes

# Answer
## PHP, 714 bytes

The output is the blank SVG file, which should be stored in a file named `a`, with additional CSS to colour the states, which should be stored in a file named `b` in the following format:

```
Ohio0Indiana0Illinois1New York0New Jersey0Florida

```

I've added some newlines for readability.

```
<?
$x=str_replace;echo$x('.b','#'.$x([0,1],[',#','{fill:red}#'],$x(split(0,'Alabama0Alaska0
Arizona0Arkansas0California0Colorado0Connecticut0Delaware0Florida0Georgia0Hawaii0Idaho0Illin
ois0Indiana0Iowa0Kansas0Kentucky0Louisiana0Maine0Maryland0Massachusetts0Michigan0Minnesota0M
ississippi0Missouri0Montana0Nebraska0Nevada0New Hampshire0New Jersey0New Mexico0New York0Nor
th Carolina0North Dakota0Ohio0Oklahoma0Oregon0Pennsylvania0Rhode Island0South Carolina0South
 Dakota0Tennessee0Texas0Utah0Vermont0Virginia0Washington0West Virginia0Wisconsin0Wyoming'),s
tr_split(ALAKAZARCACOCTDEFLGAHIIDILINIAKSKYLAMEMDMAMIMNMSMOMTNENVNHNJNMNYNCNDOHOKORPARISCSDT
NTXUTVTVAWAWVWIWY,2),file(b)[0])).'{fill:blue}.b',implode('',file(a)));

```

Here is the ungolfed version:

```
<?php
$stateNames = 'Alabama0Alaska0Arizona0Arkansas0California0Colorado0Connecticut0Delaware0Florida0Georgia0Hawaii0Idaho0Illinois0Indiana0Iowa0Kansas0Kentucky0Louisiana0Maine0Maryland0Massachusetts0Michigan0Minnesota0Mississippi0Missouri0Montana0Nebraska0Nevada0New Hampshire0New Jersey0New Mexico0New York0North Carolina0North Dakota0Ohio0Oklahoma0Oregon0Pennsylvania0Rhode Island0South Carolina0South Dakota0Tennessee0Texas0Utah0Vermont0Virginia0Washington0West Virginia0Wisconsin0Wyoming';
$statesAbbreviations = 'ALAKAZARCACOCTDEFLGAHIIDILINIAKSKYLAMEMDMAMIMNMSMOMTNENVNHNJNMNYNCNDOHOKORPARISCSDTNTXUTVTVAWAWVWIWY';

$blankSVG = implode('', file('a'));

$inputWithStateNames = file('b')[0];
$inputWithStateAbbreviations = str_replace(
    explode('0', $stateNames),
    str_split($statesAbbreviations, 2),
    $inputWithStateNames
);

echo str_replace(
    '.border',
    '#'. str_replace(
        [
            '0',
            '1'
        ],
        [
            ',#',
            '{fill:red}#'
        ],
        $inputWithStateAbbreviations
    ) .'{fill:blue}.border',
    $blankSVG
);

```

The principle is simple: in the blank SVG, each path has an ID corresponding to the abbreviation of the state that it represents (for instance, `<path d="…" id="HI" />` for Hawaii).

All we have to do is to add some CSS to colour this path in the appropriate shade. But there is already some CSS in the blank file (in particular the `<style type="text/css">…</style>` tag already exists), so it's really easy and short to do it. We can notice than the string `.b` is only found in the CSS for `.border`. Good news! We'll just replace `.b` with `OUR_WONDERFUL_CSS.b`.

Creating "our wonderful CSS" is not really more difficult:

1. Read the input from the file:
`Ohio0Indiana0Illinois1New York0New Jersey0Florida`.
2. Replace the names of the states with their abbreviations:
`OH0IN0IL1NY0NJ0FL`.
3. Replace the `0` characters with `,#`:
`OH,#IN,#IL1NY,#NJ,#FL`.
4. Replace the `1` character with `{fill:red}#`:
`OH,#IN,#IL{fill:red}#NY,#NJ,#FL`.
5. Add `#` at the beginning and `{fill:blue}` at the end:
`#OH,#IN,#IL{fill:red}#NY,#NJ,#FL{fill:blue}`.
> 5 votes

# Answer
# Mathematica 1025

Not elegant but it works.

I wasn't aware that SVG files had paths for each state, so I found the states using `MorphologicalComponents` and then associated each component with its respective state. States like Michigan (with upper and lower peninsulas) and Hawaii (multiple islands) have more than one component.

The code assumes that the map file is contained in the variable, *m*.

```
r=Thread[{"Washington","Montana","Maine","Minnesota","North Dakota","Oregon","Michigan","New Hampshire","Vermont","Wisconsin","New York","Idaho","South Dakota","Wyoming","Massachusetts","California","Connecticut","Nevada","Pennsylvania","Iowa","New Mexico","New Jersey","Ohio","Nebraska","Illinois","Indiana","Colorado","Delaware","Maryland","West Virginia","Virginia","Missouri","Washington, D.C.","Kansas","Kentucky","North Carolina","New Mexico","Tennessee","Arizona","Oklahoma","Arkansas","South Carolina","Georgia","Alabama","Mississippi","Texas","Louisiana","Alaska","Florida","Hawaii"}->{6,7,8,9,10,11,{13,23},14,16,18,{19,39},20,24,25,26,27,31,32,36,37,38,40,41,42,43,44,45,46,{47,55},49,50,51,52,53,56,57,58,59,60,61,62,65,66,67,69,{71,80,87},72,{73,75,82,93,101,104},74,{79,81,83,84,85,89,92}}];
v=Flatten;c=MorphologicalComponents@Binarize@m;
h@s_:=v[((Reverse/@Position[c,#])/.{x_,y_}:>{x,1241-y})&/@s,1]
k@{s_,c_}:=Thread[(h@s)->c]
f@{a_,b_}:=Export["f.jpg",(ReplacePixelValue[map,v[k[{v[#/.r],#2}]&@@@{{a,Red},{b,Blue}}]])]

```

Below is the image that will be exported by the following input:

```
f[{{"Ohio", "Indiana", "Illinois", "Alaska"}, {"New York", "Michigan","Oregon", "New Jersey", "Florida"}}]

```
> 3 votes

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


title: DCSS morgue file parser

text:
# Question
Title: DCSS morgue file parser
In this challenge, you need to parse morgue files from the roguelike game Dungeon Crawl Stone Soup and output it to STDOUT.

## What are these morgue files??

When you die, a text file is generated with that character's data inside. You can see what equipment the character had, what happened during the last few turns, and how many monsters he has killed.

You can find a example morgue file here

## The challenge

Your job is to make a program that takes one of those files from STDIN, parses it, and outputs the data to STDOUT.

To make this challenge a bit easier, you only have to parse the first block of text. (up until `The game lasted <time> (<turns> turns).`

You need to parse and output the following information:

* The version number.
* The score.
* The character name, title, race and class.
* The character level.
* The cause of death/victory.
* The amount of turns the run lasted.

Example:

```
Dungeon Crawl Stone Soup version <version number> character file.

<score> <name> the <title> (level <level>, 224/224 HPs)
         Began as a <race> <class> on Mar 16, 2015.
         Was the Champion of the Shining One.
         <cause of death/victory>

         The game lasted 16:11:01 (<turns> turns).

```

## Test Cases

### Test case 1 - Victory

**Input file**

Example output - Victory:

```
Version: 0.16.0-8-gd9ae3a8 (webtiles)
Score: 16059087
Name: Ryuzilla the Conqueror
Character: Gargoyle Berserker
Level: 27
Cause of Death/Victory: Escaped with the Orb and 15 runes on Mar 17 2015!
Turns: 97605

```

### Test case 2 - Death

**Input file**

Example output - Death:

```
Version: 0.16-a0-3667-g690a316 (webtiles)
Score: 462
Name: 8Escape the Ruffian
Character: Bearkin Transmuter
Level: 6
Cause of Death/Victory: Slain by an orc wielding a +0 trident (3 damage) on level 4 of the Dungeon.
Turns: 3698

```

## Rules

* This is so the shortest code wins.
* In the event of a tie, the oldest answer wins.
* No standard loopholes.
* File input must be taken from STDIN
* Output must be sent to STDOUT
* The labels before the output (ex. `Turns:`) are optional.

### Ungolfed sample code for inspiration

### Morgue file generation code in DCSS

# Answer
# Perl, 151 bytes

148 code + 3 switches (`-0, -l, -p`). I'm sure this can be improved :)

Takes input from STDIN and prints the result on receiving EOF.

```
perl -lp0e 's/\.{3}|\s/ /g;y/ //s;$_=join$\,(/(\d.*?).{15}\..(\d+).(.+?).\(.+?(\d+).+?\b(?:a|an) (.+?) o.+? ([^.!]+[.!])[^.!]*?(\d+)[^(]+\)..\3/)[0..2,4,3,5..7]'

```

Ungolfed:

```
use strict;
use warnings;

# set the input record separator to undef (the -0 switch)
$/=undef;
# read the text (the -l switch)
$_=<STDIN>;

# replace all '...' and spaces by a ' '
s/\.{3}|\s/ /g;
# squeeze all contiguous spaces into a single space
y/ //s;
# collect the captured groups into @p
my @p=
/(\d.*?).{15}\..      # version is the first string starting with a digit and ending 15 characters before the period
 (\d+).               # points is the next string with only digits
 (.+?).\(.+?          # name starts after a gap of one character
 (\d+).+?\b(?:a|an)\s # level is inside the next open paranthesis
 (.+?)\so.+?\s        # race, class occur after the 'a' or 'an' and end before ' o' i.e. (' on')
 ([^.!]+[.!])[^.!]*?  # cause of death is the a sentence ending with '.' or '!'
 (\d+)[^(]+\)..\3     # turns is the next sentence with digits within parantheses, followed by 2 characters and the player's name
/x;
$_=join"\n",@p[0..2,4,3,5..7]; # the level and race lines need to be swapped

# print the output (the -p switch)
print $_;

```

ideone.com
> 3 votes

# Answer
# F#, 377 bytes

```
open System.Text.RegularExpressions
let s=System.String.IsNullOrWhiteSpace>>not
let m f=Regex.Match((f+"").Split[|'\r';'\n'|]|>Seq.filter s|>Seq.take 8|>Seq.reduce(fun a z->a+z.Trim()), ".*n (.*) c.*\.([0-9]+) (.*) \(l.* (.*),.*a (.*) o.*\.(?:(S.*)|W.*(E.*)).*.T.*\((.*) .*\).").Groups|>Seq.cast<Group>|>Seq.skip 1|>Seq.map(fun z ->z.Value)|>Seq.filter s|>Seq.iter(printfn"%s")

```
> 3 votes

# Answer
# Javascript (ES6), ~~297~~ 230 bytes

For now, this is a test-driven regular expression.

It simply replaces the unwanted info and keeps the important stuff.

It creates an anonymous function that simply returns the wanted text.

```
_=>_.replace(/^.+version(.*) character file\.([\n\r]+)(\d+)([^\(]+) \([^\d]+( \d+),.+\n\s+.+as a(.+) on.+\n\s+(?:Was.+One\.\n)?((?:.|\n)+[!.])\n(?:.|\n)+\((\d+)(?:.|\n)+$/,'$1\n$3\n$4\n$6\n$5\n$7\n$8').replace(/\s+(\.{3} ?)?/,' ')

```

Isn't it a beast?

---

Thanks for sysreq's tip about the labels being optional. That saved me **67 bytes**!

---

You can test the resulgar expression on: https://regex101.com/r/zY0sQ0/1
> 3 votes

# Answer
# Go, ~~589~~ ~~502~~ ~~489~~ 487 bytes

```
package main;import(."fmt";."io/ioutil";"os";."strings");func d(z,ch string)string{return Map(func(r rune)rune{if IndexRune(ch,r)<0{return r};return -1},z)};func main(){x:=Split;f,_:=ReadFile(os.Args[1]);n:="\n";l:=" ";m:=",";h:=".";q:=x(string(f),n)[:11];k:=x(q[0],l);y:=x(q[10],l);u:=x(q[2],l);g:="";for _,e:=range Fields(d(q[4],n+h)+l+d(q[5],n+h)+l+d(q[6],n+h)+l+d(q[7],n+h)){g=g+e+l};Print(k[6]+l+k[7]+n+u[0]+n+y[0]+l+y[1]+l+y[2]+n+d(y[3]+l+y[4],"()")+n+d(u[5],m)+n+g+n+d(y[17],m))}

```

after running `go fmt`, `go fix`, and `go vet` here is the "ungolfed" version:

```
package main

import (
    . "fmt"
    . "io/ioutil"
    "os"
    . "strings"
)

func d(z, ch string) string {
    return Map(func(r rune) rune {
        if IndexRune(ch, r) < 0 {
            return r
        }
        return -1
    }, z)
}
func main() {
    x := Split
    f, _ := ReadFile(os.Args[1])
    n := "\n"
    l := " "
    m := ","
    h := "."
    q := x(string(f), n)[:11]
    k := x(q[0], l)
    y := x(q[10], l)
    u := x(q[2], l)
    g := ""
    for _, e := range Fields(d(q[4], n+h) + l + d(q[5], n+h) + l + d(q[6], n+h) + l + d(q[7], n+h)) {
        g = g + e + l
    }
    Print(k[6] + l + k[7] + n + u[0] + n + y[0] + l + y[1] + l + y[2] + n + d(y[3]+l+y[4], "()") + n + d(u[5], m) + n + g + n + d(y[17], m))
}

```

*Edit:* using dot-imports helps a lot.

Pretty self-explanatory but I can explain if need be. This is my first 'real' Go program and I'm still a beginner at codegolf so tips are welcome!

*Edit:* you said "take a file from STDIN", and you can run this script (if you have go installed) by running `go install <foldername>` and then `<binaryname> morgue-file.txt` or `go run main.go morgue.txt`
> 2 votes

# Answer
# Python3, 472 bytes

I thought I'd be able to get this far shorter. Not surprised I beat my own submission, though. Run it like `python3 dcss.py morgue-file.txt`.

```
import sys
n="\n"
s=" "
f=open(sys.argv[1],'r').read().split(n)[:11]
m=range
a=len
d=","
for i in m(a(f)):
 f[i]=f[i].split(s)
 for x in m(a(f[i])):
  f[i][x]=f[i][x].strip()
h=f[0]
g=f[10]
k=f[2]
def r(j,u):
 j=list(j)
 while u in j:
  j.remove(u)
 return"".join(j)
def l(x):
 c=s
 for i in m(a(x)):
  c+=x[i]+s
 return c.strip()
print(h[6]+s+h[7]+n+k[0]+n+g[0]+s+g[1]+s+g[2]+n+r(g[3],"(")+s+r(g[4],")")+n+r(k[5],d)+n+r(l(f[4])+l(f[5])+l(f[6])+l(f[7]),".")+n+r(g[17],d))

```
> 2 votes

---
Tags: code-golf, parsing
---


title: Help me manage my time

text:
# Question
Title: Help me manage my time
I have been recently told to read an entire physics textbook by the new year (true story, unfortunately). I need your help to determine what chapters I should read each day. This is where you come in.

## Input

* Two dates, in any format. The second date will always be later than the first.
* A list of chapter numbers. This comma-separated list can contain single chapters (`12`) or inclusive ranges (`1-3`). Ex. `1-3,5,6,10-13`.
* A list of weekdays (represented by the first two letters of the name: `Monday -> Mo`) to exclude from the schedule. Ex. `Mo,Tu,Fr`.

## Output

Output will be a newline-separated list of dates and chapter numbers (see format below). The chapters should be evenly distributed over all days in the range, excluding the weekdays provided. If the chapters do not distribute evenly, have the days with lower amounts of chapters at the end of the period of time. Dates in output can be in a different format than input. Days with no chapters can be ommited, or just have no chapters with it.

Example:

Input: `9/17/2015 9/27/2015 1-15 Tu`

Output:

```
9/17/2015: 1 2
9/18/2015: 3 4
9/19/2015: 5 6
9/20/2015: 7 8
9/21/2015: 9 10
9/23/2015: 11
9/24/2015: 12
9/25/2015: 13
9/26/2015: 14
9/27/2015: 15

```

# Answer
## PowerShell v4, ~~367~~ ~~357~~ ~~323~~ ~~313~~ ~~308~~ ~~307~~ ~~305~~ 277 Bytes

```
param($a,$b,$c,$d)$e=@();$c=-split('('+($c-replace'-','..'-replace',','),(')+')'|iex|%{$_-join' '});while($a-le$b){if(-join"$($a.DayOfWeek)"[0,1]-notin$d){$e+=$a;$z++}$a=$a.AddDays(1)}$g=,0*$z;$c|%{$g[$c.IndexOf($_)%$z]++};1..$z|%{"$($e[$_-1]): "+$c[$i..($i+=$g[$_-1]-1)];$i++}

```

Edit - golfed 28 bytes by using explicit input formatting.

### Explained:

```
param($a,$b,$c,$d)    # Parameters, takes our four inputs
$e=@()                # This is our array of valid output dates

$c=-split('('+($c-replace'-','..'-replace',','),(')+')'|iex|%{$_-join' '})
# Ridiculously complex way to turn the input chapters into an int array
# The first part changes "1,5-9,12" into a "(1),(5..9),(12)" format that
# PowerShell understands, then executes that with iex, which creates an
# array of arrays. Then iterate through each inner array and joins them all
# together with spaces, then finally splits on spaces to create a 1D array

while($a-le$b){       # Until we reach the end day
  if(-join"$($a.DayOfWeek)"[0,1]-notin$d){
    # Not an excluded day of the week
    $e+=$a            # Add it to our list of days
    $z++              # Increment our count of total days
  }
  $a=$a.AddDays(1)    # Move to the next day in the range
}

$g=,0*$z              # Populate a new array with zeroes, same length as $e

$c|%{$g[$c.IndexOf($_)%$z]++}
# This populates $g for how many chapters we need each day

1..$z|%{"$($e[$_-1]): "+$c[$i..($i+=$g[$_-1]-1)];$i++}
# Goes through the days in $e, prints them, and slices $c based on $g

```

### Usage

Expects the dates to be in .NET `DateTime` format. Expects the "skipped" days to be in an array (PowerShell equivalent of a list).

```
PS C:\Tools\Scripts\golfing> .\help-me-manage-my-time.ps1 (Get-Date '9/17/2015') (Get-Date '9/27/2015') '5,1-3,6,10-13,20-27' @('Su','Tu')
09/17/2015 00:00:00: 5 1 2
09/18/2015 00:00:00: 3 6
09/19/2015 00:00:00: 10 11
09/21/2015 00:00:00: 12 13
09/23/2015 00:00:00: 20 21
09/24/2015 00:00:00: 22 23
09/25/2015 00:00:00: 24 25
09/26/2015 00:00:00: 26 27

```
> 2 votes

# Answer
# JavaScript (ES6), ~~317~~ ~~310~~ 291 bytes

```
(a,b,c,d)=>{u=0;c.split`,`.map(m=>{p=m[s]`-`;for(q=n=p[0];n<=(p[1]||q);r=++u)c+=","+n++},c="");c=c.split`,`;x=d.map(p=>"SuMoTuWeThFrSa".search(p)/2);for(g=[];a<b;a.setTime(+a+864e5))x.indexOf(a.getDay())<0&&(t=y=g.push(a+" "));return g.map(w=>w+c.slice(u-r+1,u-(r-=r/y--+.99|0)+1)).join`
`}

```

## Usage

```
f(new Date("2015-09-17"),new Date("2015-09-27"),"5,1-4,6,10-13,20-27",["Su","Tu"])
=> "Thu Sep 17 2015 10:00:00 GMT+1000 (AUS Eastern Standard Time) 5,1,2
Fri Sep 18 2015 10:00:00 GMT+1000 (AUS Eastern Standard Time) 3,4,6
Sat Sep 19 2015 10:00:00 GMT+1000 (AUS Eastern Standard Time) 10,11
Mon Sep 21 2015 10:00:00 GMT+1000 (AUS Eastern Standard Time) 12,13
Wed Sep 23 2015 10:00:00 GMT+1000 (AUS Eastern Standard Time) 20,21
Thu Sep 24 2015 10:00:00 GMT+1000 (AUS Eastern Standard Time) 22,23
Fri Sep 25 2015 10:00:00 GMT+1000 (AUS Eastern Standard Time) 24,25
Sat Sep 26 2015 10:00:00 GMT+1000 (AUS Eastern Standard Time) 26,27"

```

## Explanation

```
(a,b,c,d)=>{

  u=0;                                                 // u = total chapters
  c.split`,`.map(m=>{                                  // c = array of each chapter
    p=m[s]`-`;
    for(q=n=p[0];n<=(p[1]||q);r=++u)                   // get each chapter from ranges
      c+=","+n++
  },c="");
  c=c.split`,`;

  x=d.map(p=>"SuMoTuWeThFrSa".search(p)/2);            // x = days to skip
  for(g=[];a<b;a.setTime(+a+864e5))                    // for each day between a and b
    x.indexOf(a.getDay())<0&&                          // if this day is not skipped
      (t=y=g.push(a+" "));                             // add it to the list of days
                                                       // t = total days
                                                       // y = days remaining

  return g.map(w=>w+
    c.slice(u-r+1,u-(r-=r/y--+.99|0)+1)                // add the chapters of the day
  ).join`
`
}

```
> 3 votes

# Answer
# Python 2 - ~~338~~ ~~317~~ ~~308~~ ~~304~~ 300

Here we go to get the ball rolling ...

```
def f(a,b,c,d):
 from pandas import*;import numpy as n
 s=str.split;e=n.array([])
 for g in s(c,','):h=s(g,'-');e=n.append(e,range(int(h[0]),int(h[-1])+1))
 k=[t for t in date_range(a,b) if s('Mo Tu We Th Fr Sa Su')[t.weekday()]not in d];j=len(k);e=array_split(e,j)
 for u in range(j):print k[u],e[u]

```

Example input:

```
f('9/17/2015','9/27/2015','5,1-3,6,10-13,20-27',['Su','Tu'])

```

Example Output:

```
2015-09-17 00:00:00 [ 5.  1.  2.]
2015-09-18 00:00:00 [ 3.  6.]
2015-09-19 00:00:00 [ 10.  11.]
2015-09-21 00:00:00 [ 12.  13.]
2015-09-23 00:00:00 [ 20.  21.]
2015-09-24 00:00:00 [ 22.  23.]
2015-09-25 00:00:00 [ 24.  25.]
2015-09-26 00:00:00 [ 26.  27.]

```
> 2 votes

---
Tags: code-golf, date, parsing
---