title: Group Therapy: Identify Groups

text:
# Question
Title: Group Therapy: Identify Groups
Write a program, that determines whether the multiplication table of the given finite magma represents a group. A magma is a set with a binary operation that is closed, that means

* for all \\$a,b\\$ in \\$G\\$, \\$a\*b\\$ is again in \\$G\\$ (Closedness)

Let \\$(G, * )\\$ be a magma. \\$(G, * )\\$ is a group if

* for all \\$a,b,c\\$ in \\$G\\$, \\$(a\*b) * c = a * (b\*c)\\$ (Associativity)
* there exists an element \\$e\\$ in \\$G\\$ such that \\$e * a = a * e = a\\$ for all \\$a\\$ in \\$G\\$ (Existence of neutral Element)
* for all \\$a\\$ in \\$G\\$ there is a \\$b\\$ in \\$G\\$ such that \\$a * b = b * a = e\\$ where \\$e\\$ is the neutral element (Existence of Inverse)

## Specs

The input is of a string of \\$n^2-1\\$ characters (one character for each element of the magma, allowed are `0-9`,`a-z`) and just represents the table read row by row, omitting the operator name. You can assume that the input represents a valid magma (that means each of the elements appears exactly once in the header row/column).

Example: Here we have the table of \\$\mathbb Z\_4\\$

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

```

The input string will be `012300123112302230133012`. (Or if we use symbols it could also be `nezdnnezdeezdnzzdneddnez`). Be aware that the sequence of the elements in the row and in the column do not have to be the same, so the table of \\$\mathbb Z\_4\\$ could also look like so:

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

```

This also means that the neutral element is not necessarily in the first column or first row.

If it is a group, the program has to return the character representing the neutral element. If not it has to return a falsy (distinct from the values `0-9a-z`) value

# Test cases

Non-groups can easily be constructed by just altering one digit of the string or by artificially altering the tables defining a operation that contradicts one of the group axioms.

## Groups

### Trivial

```
* | x
-----
x | x

xxx

Neutral Element: x

```

### \\$\mathbb H\\$ (quaternion group)

```
* | p t d k g b n m
-------------------
m | b d t g k p m n
p | m k g d t n p b
n | p t d k g b n m
b | n g k t d m b p
t | g m n p b k t d
d | k n m b p g d t
k | t b p m n d k g
g | d p b n m t g k

ptdkgbnmmbdtgkpmnpmkgdtnpbnptdkgbnmbngktdmbptgmnpbktddknmbpgdtktbpmndkggdpbnmtgk

Neutral Element: n

```

### \\$D\_4\\$

```
* | y r s t u v w x
-------------------
u | u x w v y t s r
v | v u x w r y t s
w | w v u x s r y t
x | x w v u t s r y
y | y r s t u v w x
r | r s t y v w x u
s | s t y r w x u v
t | t y r s x u v w

yrstuvwxuuxwvytsrvvuxwrytswwvuxsrytxxwvutsryyyrstuvwxrrstyvwxusstyrwxuvttyrsxuvw

Neutral Element: y

```

### \\$\mathbb Z\_6 \times \mathbb Z\_2\\$

```
x | 0 1 2 3 5 7 8 9 a b 4 6
---------------------------
0 | 0 1 2 3 5 7 8 9 a b 4 6
1 | 1 2 3 4 0 8 9 a b 6 5 7
2 | 2 3 4 5 1 9 a b 6 7 0 8
7 | 7 8 9 a 6 2 3 4 5 0 b 1
8 | 8 9 a b 7 3 4 5 0 1 6 2
9 | 9 a b 6 8 4 5 0 1 2 7 3
a | a b 6 7 9 5 0 1 2 3 8 4
b | b 6 7 8 a 0 1 2 3 4 9 5
3 | 3 4 5 0 2 a b 6 7 8 1 9
4 | 4 5 0 1 3 b 6 7 8 9 2 a
5 | 5 0 1 2 4 6 7 8 9 a 3 b
6 | 6 7 8 9 b 1 2 3 4 5 a 0

01235789ab46001235789ab4611234089ab6572234519ab67087789a623450b1889ab7345016299ab684501273aab6795012384bb678a0123495334502ab67819445013b67892a5501246789a3b66789b12345a0

Neutral Element: 0

```

### \\$A\_4\\$

```
* | i a b c d e f g h j k l
---------------------------
i | i a b c d e f g h j k l
a | a b i e c d g h f l j k
b | b i a d e c h f g k l j
c | c f j i g k a d l b e h
d | d h k b f l i e j a c g
e | e g l a h j b c k i d f
f | f j c k i g d l a h b e
g | g l e j a h c k b f i d
h | h k d l b f e j i g a c
j | j c f g k i l a d e h b
k | k d h f l b j i e c g a
l | l e g h j a k b c d f i

iabcdefghjkliiabcdefghjklaabiecdghfljkbbiadechfgkljccfjigkadlbehddhkbfliejacgeeglahjbckidfffjckigdlahbegglejahckbfidhhkdlbfejigacjjcfgkiladehbkkdhflbjiecgalleghjakbcdfi

Neutral Element: i

```

## Non-Groups

### A loop (Group missing associativity, or a Quasi-Group with neutral element)

```
* | 1 2 3 4 5
-------------
1 | 1 2 3 4 5
2 | 2 4 1 5 3
3 | 3 5 4 2 1
4 | 4 1 5 3 2
5 | 5 3 2 1 4

12345112345224153335421441532553214

Neutral Element: 1
(2*2)*3 = 4*3 = 5 != 2 = 2*1 = 2*(2*3)

```

An IP-loop (from http://www.quasigroups.eu/contents/download/2008/16\_2.pdf)

```
* | 1 2 3 4 5 6 7
-----------------
1 | 1 2 3 4 5 6 7
2 | 2 3 1 6 7 5 4
3 | 3 1 2 7 6 4 5
4 | 4 7 6 5 1 2 3
5 | 5 6 7 1 4 3 2
6 | 6 4 5 3 2 7 1
7 | 7 5 4 2 3 1 6

123456711234567223167543312764544765123556714326645327177542316

Neutral Element: 1
2*(2*4) = 2*6 = 5 != 7 = 3*4 = (2*2)*4

```

## Monoid (by Quincunx, thanks!)

Monoids are Magmas with associativity and a neutral element.

```
* | 0 1 2 3
-----------
0 | 0 1 2 3
1 | 1 3 1 3
2 | 2 1 0 3
3 | 3 3 3 3

012300123113132210333333

Neutral Element: 0

```

### Another Monoid

(Multiplication mod 10, without the 5) We obviously do not have inverses, and the associativity is given by the multiplication modulo 10.

```
* | 1 2 3 4 6 7 8 9
-------------------
1 | 1 2 3 4 6 7 8 9
2 | 2 4 6 8 2 4 6 8
3 | 3 6 9 2 8 1 4 7
4 | 4 8 2 6 4 8 2 6
6 | 6 2 8 4 6 2 8 4
7 | 7 4 1 8 2 9 6 3
8 | 8 6 4 2 8 6 4 2
9 | 9 8 7 6 4 3 2 1

Neutral Element: 1   12346789112346789224682468336928147448264826662846284774182963886428642998764321

```

# Answer
# Octave, 298 290 270 265 chars

```
function e=g(s)
c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')');
for i=2:b a(a==a(i))=i-1;end;
a=a(2:b,2:b--);u=1:b;
e=(isscalar(e=find(all(a==u')))&&a(e,:)==u&&sum(t=a==e)==1&&t==t')*e;
for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;e=d(e+1);

```

**265:** Removed unnecessary function handle.

**270:** After all, the check that `e==h` for **e** always satisfying **e·a=a** and **h** always satisfying **a·h=a** was not necessary. This is not possible for them to be different (**e·h=?**).

The details from the explanation for solution below are still relevant.

---

**290:**

```
function e=g(s)
c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')');
for i=2:b a(a==a(i))=i-1;end;
a=a(2:b,2:b--);u=1:b;
s=@isscalar;e=(s(e=find(all(a==u')))&&s(h=find(all(a'==u')'))&&sum(t=a==e)==1&&t==t')*e;
for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;e=d(e+1);

```

The first line

`c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')');` just stores the input into n x n table (with zero character at the place of operation mark), and then lexicographically sorts columns and rows, so that rows and columns receive the same order:

```
+ | z a t b                        + | a b t z
-----------                        -----------
z | t b a z         becomes        a | t a z b
b | z a t b      ============>     b | a b t z
t | a z b t                        t | z t b a
a | b t z a                        z | b z a t

```

Now, I remap `"a","b","t","z"` to standard `1, 2, 3, 4` , so that I can index the table efficiently. This is done by the line `for i=2:b a(a==a(i))=i-1;end;`. It yields table like

```
0   1   2   3   4
1   3   1   4   2
2   1   2   3   4
3   4   3   2   1
4   2   4   1   3

```

, where we can get rid of the first row and column with `a=a(2:b,2:b--);u=1:b;`:

```
3  1  4  2
1  2  3  4
4  3  2  1
2  4  1  3

```

This table has the given properties:

* if the neutral element **e** exists, **exactly one** (`isscalar`) row and one column have the value of row vector `u=[1 2 3 ... number-of-elements]`:

`s=@isscalar;e=(s(e=find(all(a==u')))&&s(h=find(all(a'==u')'))&&...`

* if each element **a** has a reverse element **a'**, two things hold: the neutral element **e** occurs only once each column and only once each row (`sum(t=a==e)==1`) and, to satisfy **a'·a = a·a'**, the occurences of **e** are symmetrical in respect to translation `t==t'`
* a·b can be retrieved by simple `t(a,b)` indexing. Then we check the associativity in the boring loop:

`for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;`

The function returns the neutral element the way it appeared in original table (`e=d(e+1)`) or nil character if the table does not describe a group.
> 5 votes

# Answer
# Ruby, ~~401~~ ... 272

```
f=->s{n=(s.size+1)**0.5
w=n.to_i-1
e=s[0,w].split''
s=s[w,n*n]
m={}
w.times{(1..w).each{|i|m[s[0]+e[i-1]]=s[i]}
s=s[n,n*n]}
s=e.find{|a|e.all?{|b|x=m[a+b]
x==m[b+a]&&x==b}}
e.all?{|a|t=!0
e.all?{|b|x=m[a+b]
t||=x==m[b+a]&&x==s
e.all?{|c|m[m[a+b]+c]==m[a+m[b+c]]}}&&t}&&s}

```

This is my first ruby program! This defines a lambda function that we can test by doing `puts f[gets.chomp]`. I return `false` for my false value. The first half of the function is simply parsing the input into a map, then the second half checks the possibilities.

```
f=->s{
    n=((s.size+1)**0.5).to_i
    w=n-1
    e=s[0,w].split'' # create an array of elements of the potential group
    s=s[w,n*n]
    m={} # this map is what defines our operation
    w.times{
        (1..w).each{               # for each element in the row of the table
            |i|m[s[0]+e[i-1]]=s[i] # put the value into the map
        }
        s=s[n,n*n]
    }
    s=e.find{|a| # s is the identity
        e.all?{|b|
            x=m[a+b]
            x==m[b+a]&&x==b # is a the identity?
        }
    }
    e.all?{|a| # implicit return statement
        t = !0 # t = false
        e.all?{|b| # check for inverses
            x=m[a+b]
            t ||= x==m[b+a]&&x==s # t is now true if b was a's inverse
            e.all?{|c|
                m[m[a+b]+c]==m[a+m[b+c]] # check associativity
            }
        } && t
    }&&s
}

```
> 6 votes

# Answer
# JavaScript (ES6) 285 ~~243 278~~

Run snippet to test (being ES6 it works only on Firefox)

**Edit 2** Bug fix. I was wrong in finding the neutral element, checking just one way. (Need better test cases!!!)

**Edit** Using simpler string concatenation instead of double index (like @Quincunx), I don't know what I was thinking. Also, simplified inverse check, it should still work.

```
F=t=>(
  e=t.slice(0,d=Math.sqrt(t.length)|0),
  t=t.slice(d).match('.'.repeat(d+1),'g'),
  t.map(r=>{
    for(v=r[i=0],
        j=e.search(v)+1, // column for current row  element
        r!=v+e|t.some(r=>r[j]!=r[0])?0:n=v; // find neutral
        c=r[++i];
       )h[v+e[i-1]]=c
  },h={},n=''),
  e=[...e],!e.some(a=>e.some(b=>(
    h[a+b]==n&&--d, // inverse
    e.some(c=>h[h[a+b]+c]!=h[a+h[b+c]]) // associativity
  )
  ))&&!d&&n
)
```

```
input { width: 400px; font-size:10px }
```

```
Click on textbox to test - Result : <span id=O></span><br>
<input value='...' onclick='O.innerHTML=F(this.value)'> (?)
<br>Groups<br>
<input value='nezdnnezdeezdnzzdneddnez' onclick='O.innerHTML=F(this.value)'> (n)<br>
<input value='ptdkgbnmmbdtgkpmnpmkgdtnpbnptdkgbnmbngktdmbptgmnpbktddknmbpgdtktbpmndkggdpbnmtgk' onclick='O.innerHTML=F(this.value)'> (n)<br>
<input value='yrstuvwxuuxwvytsrvvuxwrytswwvuxsrytxxwvutsryyyrstuvwxrrstyvwxusstyrwxuvttyrsxuvw' onclick='O.innerHTML=F(this.value)'> (y)<br>
<input value='01235789ab46001235789ab4611234089ab6572234519ab67087789a623450b1889ab7345016299ab684501273aab6795012384bb678a0123495334502ab67819445013b67892a5501246789a3b66789b12345a0'onclick='O.innerHTML=F(this.value)'> (0)<br>
Non groups <br>
<input value='12345112345224153335421441532553214' onclick='O.innerHTML=F(this.value)'> (FAIL)<br>
<input value='123456711234567223167543312764544765123556714326645327177542316' onclick='O.innerHTML=F(this.value)'> (FAIL)<br>
<input value='012300123113132210333333' onclick='O.innerHTML=F(this.value)'> (FAIL)<br>
```
> 4 votes

# Answer
# Haskell 391B

```
import Data.Maybe
import Data.List
o a b=elemIndex b a
l£a=fromJust.o a$l
a§b=[a!!i|i<-b]
f s|isJust j&&and(map(isJust.o h)s)&&and[or[p%q==e|q<-h]&&and[p%(q%r)==(p%q)%r|q<-h,r<-h]|p<-h]=[e]|True="!"where n=floor$(sqrt(fromIntegral$length s+1))-1;h=take n s;g=[s§[a..b]|(a,b)<-zip[1+n,2+n+n..][n+n,3*n+1..(n+1)^2]];v=s§[n,1+2*n..n+n*n];a%b=g!!(b£v)!!(a£h);j=o g h;e=v!!fromJust j

```

Curse those `import`s!

```
import Data.Maybe
import Data.List

{- rename elemIndex to save characters -}
o a b=elemIndex b a

{- get the index of l in a -}
l£a=fromJust.o a$l

{- extract a sublist of a with indices b -}
a§b=[a!!i|i<-b]

f s |isJust j {-Identity-}
     &&and (map (isJust.o h) s) {-Closure-}
     &&and[
        or [p%q==e|q<-h] {-Inverse-}
        && and [ p%(q%r)==(p%q)%r | q<-h,r<-h ] {-Associativity-}
     |
        p<-h
     ]=[e]
    |True="!"
    where
    {-size-}    n=floor$(sqrt(fromIntegral$length s+1))-1
    {-horiz-}   h=take n s
    {-table-}   g=[s§[a..b]|(a,b)<-zip[1+n,2+n+n..][n+n,3*n+1..(n+1)^2]]
    {-vert-}    v=s§[n,1+2*n..n+n*n]
    {-operate-} a%b=g!!(b£v)!!(a£h)
                j=o g h {-index of the first row identical to the top-}
    {-ident-}   e=v!!fromJust j

```

## Explanation

`f::String->String` maps the string to either `e::Char`, the identity element, or `!`.

The `where` clause creates a bunch of variables and functions, which I've commented; `v::[Int]` is the vertical list of elements, `h::[Int]` the horizontal one.

`%::Char->Char->Char` applies the group operation to its arguments.

`g::[[Int]]` is the group table (for dereferencing using `%`)

`j::Maybe Int` contains the index of the identity in `v` if it exists, otherwise `Nothing`, which is why `isJust j` is the condition in `f` for identity.
> 2 votes

---
Tags: code-golf, math, decision-problem, abstract-algebra
---


title: Prepare to... die?

text:
# Question
Title: Prepare to... die?
## Background

One source of ennui in tabletop role-playing games is dealing with rolls involving many dice. Casting a Disintegration spell may be instantaneous, but rolling and adding together 40 dice certainly isn't!

A number of suggestions for handling this are discussed at rpg.stackexchange.com. Some of them, however, such as using a roller program or averaging dice, take away some of the fun and sense of control from the players. Others, such as rolling 4 dice and multiplying the total by 10, make the results far more swingy (while averaging dice acts in the opposite direction).

This question concerns a method of reducing the number of dice rolls *without* changing either the average result (mean) or its swinginess (variance).

## Notation and math

In this question, we'll use the following notation to represent dice rolls:

* *n*d*k* (e.g. 40d6) refers to the sum of n rolls of a k-sided die.
* *n*d*k***c* (e.g. 4d6\*10) describes multiplying the result by a constant c.
* We can also add rolls (e.g. 4d6\*10 + 40d6) and constants (e.g. 4d6 + 10).

For a single die roll, we can show that:

* **Mean**: E\[1d*k*\] = (k+1)/2
* **Variance**: Var(1d*k*) = (k-1)(k+1)/12

Using the basic properties of mean and variance, we can furthermore infer that:

* **Mean**: E\[*m*d*k***a* \+ *n*d*l***b* \+ *c*\] = *a.m*.E\[1d*k*\] + *b.n*.\[1d*l*\] + *c*
* **Variance**: Var(*m*d*k***a* \+ *n*d*l***b* \+ *c*\] = *a*².*m*.Var(1d*k*) + *b*².*n*.Var(1d*l*)

## Task

Given three integers *n*, *k* and *r*, your program should output a way of approximating *n*d*k* in at most *r* rolls, with the following constraints:

* The solution should have the same mean and variance as *n*d*k*.
* The solution should contain the *largest possible number of rolls* less than or equal to *r*, as more rolls produces a smoother distribution.
* You should restrict your solutions to only using *k*-sided dice, unless you're aiming for the Bonus (see below).
* If there is no solution (as *r* is too small), the program should output the string "I AM A SEXY SHOELESS GOD OF WAR!".
* The parameters are passed in as a single space-separated string.
* You may assume that 1 ≤ *n* ≤ 100, 1 ≤ *r**n* and that *k* is one of 4, 6, 8, 10, 12 and 20 (the standard dice used in tabletops).
* The output should be in the format described in Notation (e.g. 4d6\*10+5), with optional spaces around +s but nowhere else. Unit multipliers are also optional: both 4d6\*1 and 4d6 are valid.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument. Results should be printed to STDOUT (or closest alternative) or returned as a string.

## Examples

```
>> "10 6 10"
10d6
>> "10 6 4"
2d6*2+2d6+14
>> "10 6 3"
1d6*3+1d6+21
>> "10 6 2"
1d6*3+1d6+21
>> "10 6 1"
I AM A SEXY SHOELESS GOD OF WAR!

```

## Scoring

Shortest code wins. Standard rules apply.

## Bonus

**-33%** (rounded down before subtraction) if your program also return solutions that include valid dice other than *k* (where the valid values, as mentioned above, are 4, 6, 8, 10, 12 and 20). If you choose to do so, then you should *always* return such solutions when appropriate, and handle solutions that use multiple types of die. Example:

```
>> "7 4 3"
3d6+7

```

# Answer
> 5 votes
## GolfScript (163 143 133 bytes)

```
~@:^\?,{^base 0-}%{0\{.*+}/^=},.{{,}$-1=..&{[[1$[1$]/,(3$@]'d*+'1/]zip}%^@{-}/@)*.2/\1&'.5'*}{];'I AM A SEXY SHOELESS GOD OF WAR!'}if

```

Online demo

When not mixing types of dice, the problem reduces to expressing `n` as a sum of no more than `r` squares, and `k` is irrelevant except for the calculation of the constant at the end. The bulk of this answer is the bookkeeping required to express the result in the desired format: the actual calculation is `^\?,{^base}%{0\{.*+}/^=},` to find the multiplication factors `a`, `b`, etc.; and `^@{-}/@)*.2/` to calculate the constant.

### Dissection

```
~                # Stack: n k r
@:^\?,{          # Store n in ^, and for 0 to n**r
  ^base 0-       #   convert to base n and remove 0s.
}%               # Stack: k [arrays of up to r values from 1 to n-1]
{0\{.*+}/^=},    # Filter them to arrays whose sum of squares is n,
                 #   i.e. to multipliers which have the right variance
.{               # If any multiplier array passes the filter...
  {,}$-1=        #   Pick one with the greater number of rolls
                 #   Stack: k [multipliers]
  ..&{           #   Map each distinct multiplier a...
    [[           #     Gather in nested array for later zip
      1$[1$]/,(  #       Split a copy of the multipliers around a to count the as
                 #       Let's denote that count as m
                 #       Stack: k [multipliers] a [ [ m
      3$@        #       Copy k and rotate the a inside the nested array
     ]           #       Stack: k [multipliers] [ [m k a]
      'd*+'1/    #       Push an array ['d' '*' '+'] and close nested array
    ]zip         #       Giving [[m 'd'] [k '*'] [a '+']]
                 #       which will be printed as mdk*a+
  }%             #   Stack: k [multipliers] [string representations of dice]
  ^@{-}/@)*      #   Compute (n - sum(multipliers)) * (k + 1)
                 #   That's twice the constant we need to add to fix the mean
  .2/\1&'.5'*    #   And convert it to a renderable form, including .5 if needed
}{               # Otherwise clear the stack and push the error message
  ];'I AM A SEXY SHOELESS GOD OF WAR!'
}if

```

# Answer
> 1 votes
## Python, ~~487~~ ~~461~~ 452 - 33% = 303 bytes

Since nobody else has done so, here is a solution that handles different types of dice. Like the other solution, it generates a range of possible solutions and filters them down. It uses the fact that (k+1)(k-1) = k^2-1 and two semi-loopholes in the spec (oops!): the lack of ban on printing the redundant form 0d*k***a* (which saves all of 5 bytes!), and the lack of running time restriction (it gets slow fairly quickly, though does run all the examples given).

```
from itertools import*
N,K,R=map(int,input().split())
S=lambda l:sum([x[0]for x in l])
s=[x for x in product(*[[(n,k,a)for n in range(N*(K**2-1)/((k**2-1)*a**2)+1)]for a in range(1,N+1)for k in[4,6,8,10,12,20]if a**2<=N])if sum([n*(k**2-1)*a**2 for n,k,a in x])==N*K**2-N and S(x)<=R]
if s:s=max(s,key=S);print"+".join(["%sd%s*%s"%x for x in s]+[str(int(N*(K+1)/2.-sum([n*a*(k+1)/2.for n,k,a in s])))])
else:print"I AM A SEXY SHOELESS GOD OF WAR!"

```

For prettier output add `if x[0]` after `"%sd%s*%s"%x for x in s`:

```
>> "7 4 3"
3d6+7
>> "10 6 3"
1d6*1+1d8*1+1d8*2+18
>> "10 6 2"
1d6*1+1d6*3+21
>> "10 6 1"
I AM A SEXY SHOELESS GOD OF WAR!

```

---
Tags: code-golf, number, game, probability-theory
---


title: Count the number of Hankelable matrices

text:
# Question
Title: Count the number of Hankelable matrices
## Background

A binary Hankel matrix is a matrix with constant skew-diagonals (positive sloping diagonals) containing only `0`s and `1`s. E.g. a 5x5 binary Hankel matrix looks like

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

```

where `a, b, c, d, e, f, g, h, i` are either `0` or `1`.

Let's define a matrix **M** as **Hankelable** if there is a permutation of the order of rows and columns of **M** so that **M** is a Hankel matrix. This means one can apply one permutation to the order of the rows and a possibly different one to the columns.

## The Challenge

The challenge is to count how many *Hankelable* `n` by `n` matrices there are for all `n` up to as large a value as possible.

### Output

For each integer n from 1 upwards, output the number of *Hankelable* `n` by `n` matrices with entries which are `0` or `1`.

For `n = 1,2,3,4,5` the answers should be `2,12,230,12076,1446672`. (Thanks to orlp for the code to produce these.)

### Time limit

I will run your code on my machine and stop it after 1 minute. The code that outputs the correct answers up to the largest value of n wins. The time limit is for everything from `n = 1` to the biggest value of `n` for which you give an answer.

The winner will be the best answer by the end of Saturday 18 April.

### Tie Breaker

In the case of a tie for some maximum `n` I will time how long it takes to give the outputs up to `n+1` and the quickest one wins. In the case that they run in the same time to within a second up to `n+1`, the first submission wins.

### Languages and libraries

You can use any language which has a freely available compiler/interpreter/etc. for Linux and any libraries which are also freely available for Linux.

### My machine

The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor on an Asus M5A78L-M/USB3 Motherboard (Socket AM3+, 8GB DDR3). This also means I need to be able to run your code. As a consequence, only use easily available free software and please include full instructions how to compile and run your code.

### Notes

I recommend against iterating over all n by n matrices and trying to detect if each one has the property I describe. First, there are too many and second, there seems to be no quick way to do this detection.

**Leading entries so far**

* n = 8 by Peter Taylor. **Java**
* n = 5 by orlp. **Python**

# Answer
> 7 votes
## Java (n=8)

```
import java.util.*;
import java.util.concurrent.*;

public class HankelCombinatorics {
    public static final int NUM_THREADS = 8;

    private static final int[] FACT = new int[13];
    static {
        FACT[0] = 1;
        for (int i = 1; i < FACT.length; i++) FACT[i] = i * FACT[i-1];
    }

    public static void main(String[] args) {
        long prevElapsed = 0, start = System.nanoTime();
        for (int i = 1; i < 12; i++) {
            long count = count(i), elapsed = System.nanoTime() - start;
            System.out.format("%d in %dms, total elapsed %dms\n", count, (elapsed - prevElapsed) / 1000000, elapsed / 1000000);
            prevElapsed = elapsed;
        }
    }

    @SuppressWarnings("unchecked")
    private static long count(int n) {
        int[][] perms = new int[FACT[n]][];
        genPermsInner(0, 0, new int[n], perms, 0);

        // We partition by canonical representation of the row sum multiset, discarding any with a density > 50%.
        Map<CanonicalMatrix, Map<CanonicalMatrix, Integer>> part = new HashMap<CanonicalMatrix, Map<CanonicalMatrix, Integer>>();
        for (int m = 0; m < 1 << (2*n-1); m++) {
            int density = 0;
            int[] key = new int[n];
            for (int i = 0; i < n; i++) {
                key[i] = Integer.bitCount((m >> i) & ((1 << n) - 1));
                density += key[i];
            }
            if (2 * density <= n * n) {
                CanonicalMatrix _key = new CanonicalMatrix(key);
                Map<CanonicalMatrix, Integer> map = part.get(_key);
                if (map == null) part.put(_key, map = new HashMap<CanonicalMatrix, Integer>());
                map.put(new CanonicalMatrix(m, perms[0]), m);
            }
        }

        List<Job> jobs = new ArrayList<Job>();
        ExecutorService pool = Executors.newFixedThreadPool(NUM_THREADS);

        for (Map.Entry<CanonicalMatrix, Map<CanonicalMatrix, Integer>> e : part.entrySet()) {
            Job job = new Job(n, perms, e.getKey().sum() << 1 == n * n ? 0 : 1, e.getValue());
            jobs.add(job);
            pool.execute(job);
        }

        pool.shutdown();
        try {
            pool.awaitTermination(1, TimeUnit.DAYS); // i.e. until it's finished - inaccurate results are useless
        }
        catch (InterruptedException ie) {
            throw new IllegalStateException(ie);
        }

        long total = 0;
        for (Job job : jobs) total += job.subtotal;
        return total;
    }

    private static int genPermsInner(int idx, int usedMask, int[] a, int[][] perms, int off) {
        if (idx == a.length) perms[off++] = a.clone();
        else for (int i = 0; i < a.length; i++) {
            int m = 1 << (a[idx] = i);
            if ((usedMask & m) == 0) off = genPermsInner(idx+1, usedMask | m, a, perms, off);
        }
        return off;
    }

    static class Job implements Runnable {
        private volatile long subtotal = 0;
        private final int n;
        private final int[][] perms;
        private final int shift;
        private final Map<CanonicalMatrix, Integer> unseen;

        public Job(int n, int[][] perms, int shift, Map<CanonicalMatrix, Integer> unseen) {
            this.n = n;
            this.perms = perms;
            this.shift = shift;
            this.unseen = unseen;
        }

        public void run() {
            long result = 0;
            int[][] perms = this.perms;
            Map<CanonicalMatrix, Integer> unseen = this.unseen;
            while (!unseen.isEmpty()) {
                int m = unseen.values().iterator().next();
                Set<CanonicalMatrix> equiv = new HashSet<CanonicalMatrix>();
                for (int[] perm : perms) {
                    CanonicalMatrix canonical = new CanonicalMatrix(m, perm);
                    if (equiv.add(canonical)) {
                        result += canonical.weight() << shift;
                        unseen.remove(canonical);
                    }
                }
            }

            subtotal = result;
        }
    }

    static class CanonicalMatrix {
        private final int[] a;
        private final int hash;

        public CanonicalMatrix(int m, int[] r) {
            this(permuteRows(m, r));
        }

        public CanonicalMatrix(int[] a) {
            this.a = a;
            Arrays.sort(a);

            int h = 0;
            for (int i : a) h = h * 37 + i;
            hash = h;
        }

        private static int[] permuteRows(int m, int[] perm) {
            int[] cols = new int[perm.length];
            for (int i = 0; i < perm.length; i++) {
                for (int j = 0; j < cols.length; j++) cols[j] |= ((m >> (perm[i] + j)) & 1L) << i;
            }
            return cols;
        }

        public int sum() {
            int sum = 0;
            for (int i : a) sum += i;
            return sum;
        }

        public int weight() {
            int prev = -1, count = 0, weight = FACT[a.length];
            for (int col : a) {
                if (col == prev) weight /= ++count;
                else {
                    prev = col;
                    count = 1;
                }
            }
            return weight;
        }

        @Override public boolean equals(Object obj) {
            // Deliberately unsuitable for general-purpose use, but helps catch bugs faster.
            CanonicalMatrix that = (CanonicalMatrix)obj;
            for (int i = 0; i < a.length; i++) {
                if (a[i] != that.a[i]) return false;
            }
            return true;
        }

        @Override public int hashCode() {
            return hash;
        }
    }
}

```

Save as `HankelCombinatorics.java`, compile as `javac HankelCombinatorics.java`, run as `java -Xmx2G HankelCombinatorics`.

With `NUM_THREADS = 4` on my quad-core machine it gets `20420819767436` for `n=8` in 50 to 55 seconds elapsed, with a fair amount of variability between runs; I expect that it should easily manage the same on your octa-core machine but will take an hour or more to get `n=9`.

### How it works

Given `n`, there are `2^(2n-1)` binary `n`x`n` Hankel matrices. The rows can be permuted in `n!` ways, and the columns in `n!` ways. All we need to do is to avoid double-counting...

If you calculate the sum of each row, then neither permuting the rows nor permuting the columns changes the multiset of sums. E.g.

```
0 1 1 0 1
1 1 0 1 0
1 0 1 0 0
0 1 0 0 1
1 0 0 1 0

```

has row sum multiset `{3, 3, 2, 2, 2}`, and so do all Hankelable matrices derived from it. This means that we can group the Hankel matrices by these row sum multisets and then handle each group independently, exploiting multiple processor cores.

There's also an exploitable symmetry: the matrices with more zeroes than ones are in bijection with the matrices with more ones than zeroes.

Double-counting occurs when Hankel matrix `M_1` with row permutation `r_1` and column permutation `c_1` matches Hankel matrix `M_2` with row permutation `r_2` and column permutation `c_2` (with up to two but not all three of `M_1 = M_2`, `r_1 = r_2`, `c_1 = c_2`). The row and column permutations are independent, so if we apply row permutation `r_1` to `M_1` and row permutation `r_2` to `M_2`, the columns *as multisets* must be equal. So for each group, I calculate all of the column multisets obtained by applying a row permutation to a matrix in the group. The easy way to get a canonical representation of the multisets is to sort the columns, and that is also useful in the next step.

Having obtained the distinct column multisets, we need to find how many of the `n!` permutations of each are unique. At this point, double-counting can only occur if a given column multiset has duplicate columns: what we need to do is to count the number of occurrences of each distinct column in the multiset and then calculate the corresponding multinomial coefficient. Since the columns are sorted, it's easy to do the count.

Finally we add them all up.

The asymptotic complexity isn't trivial to calculate to full precision, because we need to make some assumptions about the sets. We evaluate on the order of `2^(2n-2) n!` column multisets, taking `n^2 ln n` time for each (including the sorting); if grouping doesn't take more than a `ln n` factor, we have time complexity `Theta(4^n n! n^2 ln n)`. But since the exponential factors completely dominate the polynomial ones, it's `Theta(4^n n!) = Theta((4n/e)^n)`.

# Answer
> 3 votes
# Python2/3

Pretty naive approach, in a slow language:

```
import itertools

def permute_rows(m):
    for perm in itertools.permutations(m):
        yield perm

def permute_columns(m):
    T = zip(*m)
    for perm in itertools.permutations(T):
        yield zip(*perm)

N = 1
while True:
    base_template = ["abcdefghijklmnopqrstuvwxyz"[i:i+N] for i in range(N)]

    templates = set()
    for c in permute_rows(base_template):
        for m in permute_columns(c):
            templates.add("".join("".join(row) for row in m))

    def possibs(free, templates):
        if free == 2*N - 1:
            return set(int(t, 2) for t in templates)

        s = set()
        for b in "01":
            new_templates = set(t.replace("abcdefghijklmnopqrstuvwxyz"[free], b) for t in templates)
            s |= possibs(free + 1, new_templates)

        return s

    print(len(possibs(0, templates)))
    N += 1

```

Run by typing `python script.py`.

# Answer
> 2 votes
# Haskell

```
import Data.List
import Data.Hashable
import Control.Parallel.Strategies
import Control.Parallel
import qualified Data.HashSet as S

main = mapM putStrLn $ map (show.countHankellable) [1..]

a§b=[a!!i|i<-b]

hashNub :: (Hashable a, Eq a) => [a] -> [a]
hashNub l = go S.empty l
    where
      go _ []     = []
      go s (x:xs) = if x `S.member` s then go s xs
                                    else x : go (S.insert x s) xs

pmap = parMap rseq

makeMatrix :: Int->[Bool]->[[Bool]]
makeMatrix n vars = [vars§[i..i+n-1]|i<-[0..n-1]]

countHankellable :: Int -> Int
countHankellable n = let
    s = permutations [0..n-1]
    conjugates m = concat[permutations[r§q|r<-m]|q<-s]
    variableSets = sequence [[True,False]|x<-[0..2*(n-1)]]
 in
    length.hashNub.concat.pmap (conjugates.makeMatrix n ) $ variableSets

```

Nowhere near as fast as Peter's - that's a pretty impressive setup he's got there! Now with much more code copied from the internet. Usage:

```
$ ghc -threaded hankell.hs
$ ./hankell

```

---
Tags: math, fastest-code, combinatorics, permutations
---


title: Word fractal plotter

text:
# Question
Title: Word fractal plotter
## Iterated Function Systems

An Iterated Function System (IFS) is a method of constructing self-similar fractals. Each fractal is defined recursively as the union of several copies of itself, with each copy obtained by applying a transformation function to the whole. The functions are usually affine transformations of the form x↦Mx+b: i.e. a linear transformation such as a rotation, scaling or reflection, followed by a translation. Given a set of transformations, the fractal can then be obtained iteratively as follows: begin with a point (for example the origin) and repeatedly apply a randomly-selected transformation from the set. The sequence of points generated, which converges to the fixed point of the IFS, is then plotted.

The most famous example of an IFS is the Barnsley Fern. This is produced from four affine transformations, shown in the diagram below (taken from Wikipedia).

The affine transformations used in this questions involve only uniform scaling, rotation by a multiple of 90°, and translation. They can be implemented as follows, where n is the scale factor, θ is the rotation angle in radians and b is the translation in 'plot units' (e.g. pixels):

## Seven-segment displays

A seven-segment display (SSD) is a cheap and simple electronic display device often used in clocks, meters and calculators to display decimal numerals. Though it wasn't designed to display letters, it is sometimes used to do so. The resulting alphabet is often ambiguous and sometimes unintuitive, but is sufficient for certain status messages (e.g. "nO dISC" or "gOOdbYE"). Below is one way to represent the 26 letters and 10 numerals on a seven-segment display.

## Task

The aim of this challenge is to produce word fractals using IFSs and the SSD alphabet above.

* The input is a string of multiple alphanumeric characters. The string may contain both upper and lower case letters, though the SSD alphabet is case insensitive. The program need not support punctuation or whitespace characters.
* The output should be an IFS plot representing the string as rendered in the SSD alphabet above. Each lit segment in each character should correspond to an additional affine transformation mapping the bounding box of the rendered word to that of the segment. Horizontal segments should remain facing upwards, while vertical segments should face 'outwards' (i.e. left-side up on the left, right-side up on the right). The precise alignment/overlap of segments is left up to the solver, as long as the output is legible. For an example output showing one possible alignment, see below.
* There should be a constant non-empty gap between the letters, to make the output legible.
* The plot should contain enough points to be legible.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument. The output should be drawn either to screen or to a file in any standard graphic format. **As part of the answer you should include a screenshot of your output for the word "COdEgOLF".** Standard code golf restrictions apply.

## Example

## Scoring

Shortest code (in bytes) wins. Standard rules apply.

## Miscellania

For a good mathematical introduction to IFSs (including fractal compression) see these PDF lecture notes.

For a similar challenge concerning self-similar text see Words within words within words within words . . ..

# Answer
> 3 votes
# Python (518)

```
from pylab import*
D=dict(zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789',[map(int,bin(7145037215283832782017591362181079009730769141301710950254702714880607436795)[2+n*7:9+n*7])for n in range(36)]))
def T(A,C):y,x=A.shape;M=zeros((2*x-1,x+y));p=A[::-1].T;q=A.T[::-1];M[:y,:x]=C[0]*A;M[:x,:y]=C[1]*p;M[:x,-2*y:-y]=C[2]*q;M[x-1:x-1+y,:x]=C[3]*A;M[x-1:,:y]=C[4]*p;M[x-1:,-2*y:-y]=C[5]*q;M[2*x-1-y:2*x-1,:x]=C[6]*A;return M
def R(S,N):
 V=ones((1,3))
 for i in range(N):V=concatenate([T(V,D[C])for C in S],1)
 ion();imshow(V)

```

Call as `R('CODEGOLF', 3)`

first i make a dictionary that maps letters to their 7-bit SSD-representaion, where each bit stands for one bar, the `.`-corners are simply overwritten by the most recent bar

```
.000.
1   2
1   2
1   2
.333.
4   5
4   5
4   5
.666.

```

The function `T(BaseArray, BooleanArray)` makes a big empty array for one letter and puts rotated copies of BaseArray along the bars as indicated by BooleanArray. Finally `R(String, N_levels)` connects all the letters form the input and uses the result as BaseArray for the next iteration.
While technically correct, the result is quite ugly because of interpolation and the default colourmap

**Unglofed**

```
from pylab import*
D=dict(zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789',
           [map(int,bin(7145037215283832782017591362181079009730769141301710950254702714880607436795)[2+n*7:9+n*7])for n in range(36)]))

def T(A,C):
    y,x = A.shape
    M = zeros((2*x-1,x+y))
    if C[0]: M[:y,           :x] = A
    if C[1]: M[:x,           :y] = A[::-1].T
    if C[2]: M[:x,      -2*y:-y] = A.T[::-1]
    if C[3]: M[x-y+y/2:x+y/2,:x] = A # middle bar shifted upwards by half thickness
    if C[4]: M[x-1:,         :y] = A[::-1].T
    if C[5]: M[x-1:,    -2*y:-y] = A.T[::-1]
    if C[6]: M[2*x-1-y:2*x-1,:x] = A
    return M

def R(S,N):
    V = ones((1,3))
    for i in range(N):
        V = concatenate([T(V, D[C]) for C in S], 1)
    imsave('%s_%s.png'%(S,N), V ,cmap='gray')

```

The initial seed `V` kinda controls the font on the deepest level. `[1 1 1]` make the smallest possible 3x5 letters

With `V = ones((1,11))` you get long and thin letters

And with

```
V=array([[0,1,1,1,1,1,1,1,1,0],
         [1,0,0,0,0,0,0,0,0,1],
         [0,1,1,1,1,1,1,1,1,0]])

```

you can make hollow letters

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


title: Stringing a Pearl Necklace

text:
# Question
Title: Stringing a Pearl Necklace
### Overview

**Pearls** (or Masyu) is a logic game played on a grid. There are black and white pearls placed on the grid. The object is to form a *single, closed loop* that travels through each pearl using only straight line segments and right angles.

There are some rules that govern how the loop interacts with pearls:

* White pearls must be traveled **straight** through, but the loop must **turn** in the previous *and/or* next cell in its path.
* Black pearls must be **turned** upon, but the loop must travel **straight** through the next *and* previous cells in its path.
* The loop must **not** cross or otherwise intersect itself. All cells have exactly zero or two loop entry/exits.

An example puzzle from Wikipedia (and its solution):

Your objective is to solve a given puzzle. If there are multiple possible solutions, it does not matter which one you give.

### Input

Input will be an unsolved *square* grid. The example shown above would look like this:

```
..w.w.....
....w...b.
..b.b.w...
...w..w...
b....w...w
..w....w..
..b...w...
w...b....w
......ww..
..b......b

```

`w` is a white pearl, `b` is a black pearl, and `.` is an empty cell.

Assume input is valid. This means it is well formed, and at least one solution is possible. All valid puzzles are at least 3x3, and contain at least one pearl.

### Output

Output is a string of coordinates representing the path. The upper left corner of the grid is `0 0`, upper right is `n-1 0`, where *n* is the width of the grid.

A path is simply a series of ordered coordinates:

```
x1 y1 x2 y2 x3 y3 ...

```

The path is assumed to be closed, so you do not *need* to repeat the first coordinate at the end, but there is no penalty for doing so.

The output should consist of *at least* all corners in the path. You do not have to output every cell on the path if there is no turn. For instance, the output for the example could start with:

```
1 0 5 0 5 1 ...

```

or

```
1 0 2 0 3 0 4 0 5 0 5 1 ...

```

Output should *not* contain any cell not in the path. You may start at any cell in the path.

---

### Snippet

Here's a snippet you can use to visualize your solution. Just paste in the grid you're working on and the path you output. I'm aware that it's painful to look at my code, so I just suggest you don't ;)

```
function draw(){document.getElementById("output").innerHTML=gridSVG+pathSVG}function drawCoords(){coords=document.getElementById("coords").value;var e=prefix+'<path fill="none" d="';if(nums=coords.match(/[^\s]+/g),!(nums.length<2)){for(e+="M "+(nums[0]*scale+offset)+" "+(nums[1]*scale+offset),i=2;i<nums.length;i+=2)e+=" L "+(nums[i]*scale+offset)+" "+(nums[i+1]*scale+offset);e+=" L "+(nums[0]*scale+offset)+" "+(nums[1]*scale+offset),e+='" stroke="black" stroke-width="2"/>'+suffix,pathSVG=e,draw()}}function drawPath(){path=document.getElementById("path").value;var e=prefix+'<path fill="none" d="'+path+'" stroke="black" stroke-width="2"/>'+suffix;pathSVG=e,draw()}function drawGrid(){grid=document.getElementById("grid").value;var e=prefix;for(lines=grid.match(/[^\s]+/g),width=lines[0].length*scale,height=lines.length*scale,i=0;i<=lines.length;i++)e+='<path stroke="gray" d="M 0 '+i*scale+" L "+width+" "+i*scale+'"/>',e+='<path stroke="gray" d="M '+i*scale+" 0 L "+i*scale+" "+height+'"/>';for(j=0;j<lines.length;j++)for(line=lines[j],i=0;i<line.length;i++)"w"==line.charAt(i)&&(e+='<circle cx="'+(i*scale+offset)+'" cy="'+(j*scale+offset)+'" r="'+.8*offset+'" stroke="black" fill="white"/>'),"b"==line.charAt(i)&&(e+='<circle cx="'+(i*scale+offset)+'" cy="'+(j*scale+offset)+'" r="'+.8*offset+'" stroke="black" fill="black"/>');e+=suffix,gridSVG=e,draw()}var prefix='<svg height="400" width="400">',suffix="</svg>",scale=30,offset=scale/2,pathSVG="",gridSVG="";
```

```
svg{position: absolute;left: 50px;}
```

```
Paste grid input here<br><input id="grid" type="textarea" size="80" oninput='drawGrid()' /><br><br>Paste path output here<br><input id="coords" type="textarea" size="80" oninput='drawCoords()' /><br><br><div id="output"></div>
```

---

### Test Cases

These test cases show one possible output for each input (except the last, which is shown unsolved). There may be other valid paths, you might go CW or CCW or start at a different point, etc. Solutions should be able to solve the test cases in seconds/minutes/hours, not days/weeks/eons.

```
...
w..
..b

0 0 1 0 2 0 2 1 2 2 1 2 0 2 0 1

```

```
.wb..b
......
..b...
w.ww..
......
b....b

0 0 2 0 2 2 4 2 4 1 3 1 3 0 5 0 5 5 3 5 3 4 4 4 4 3 1 3 1 4 2 4 2 5 0 5 0 2 1 2 1 1 0 1

```

```
.....w.b.w..
ww..b...b...
.w.....b....
...wbww..b.b
....b.......
w.w.........
..w......b.b
.....bb.....
.....b.....w
w.ww..b.....
...w......w.
b..w.....b..

```

# Answer
# C, 590 ~~640 760 880 963 1018~~

Brute force is quite fast for this. The 12x12 test runs under 10ms. Knowing that could opt for some language more appropriate for golfing.

I don't assume the board is square as the larger puzzles tend not to be square.

The `W` define sets the limit on the board dimensions. The actual limit is smaller `W - 2` as I use extra rows for borders to avoid boundary checks.

```
#define W 40
int Y,X,T,P,Q[W*W],D[]={-W,-1,1,W};char B[W*W],K[W*W],I[W];
t(x,d,s){for(P=0;B[x];x*=x!=*Q)s-=K[Q[P++]=x]-1,
d=(54202126527627840ll>>2*(d*7+B[x+=D[d]]%8))&3;return x?0:s;}
m(x){int c=K[x],u=B[x-W],U=u&7,l=B[x-1],L=l&7,r=0,
i=U!=3&U!=4&L!=2&L!=4,o=(39>>U)&1?57:70;o&=(52>>L)&1?42:85;
if(x/W>Y+1){for(;P--;)printf("%d %d ",Q[P]%W-1,Q[P]/W-1);exit(0);}
if(u>7)o&=U>4?~64:~6;if(l>7)o&=L>4?~32:~10;
for(o&=c?c>1?c>2?(r=8*i,96):(r=8,i*30):~0:1;o;r++,o/=2)
if(o&1)if(B[x]=r,r%8!=1||!t(x,0,T))m(x+1);B[x]=0;}
main(){for(;gets(I);Y++)for(X=0;I[X];X++)
T+=(K[X+1+Y*W+W]=I[X]/36)-1;m(W);}

```

Test me.

Here is a more challenging test case:

```
.b.....b.b.......b..
.....w.....b.w....w.
....w.........w.....
..bb.....w.w.b....b.
.w.....b..b......w..
.....b..............
.b..........b.b..bw.
....w....w....b...w.
.......bb...b...w...
..b.......w.........
....b.w.....w.b...b.
w...b...w..b.w.w....
b.w....w............
...b.w......b..b...b
w......w.b.ww.......
.b....b..........b..
....b....w.bb.w...w.
w..b......w...b.....
b.....w.........w...
...b....w..w..b...w.
...................b
.b..w..bb.b..b..w...
........w......b....
b....w......b..b.b..
...b..bb.w.w........
...b.......w......w.
w...w.b.w.....b....b
............w..ww...
..b.b..b....b.......
....b.........w...b.
.ww.......b.w.w.....
b.....w..w.w...b....
....ww..b.b.w....w.w
.............bb..w..
.b....w.b.b........w
....bw..........b...

```

I was lucky my code finds the solution quite early in the run (\<5min), but the full search takes much longer (67min).
> 8 votes

# Answer
# Python - 1669

Still pretty long, but fast enough to run the last example in under a second on my computer. It's probably possible to make shorter at the cost of speed, but for now it is pretty much equivalent to the ungolfed code.

Example output for last test case:

```
0 11 1 11 2 11 3 11 4 11 4 10 3 10 2 10 1 10 1 9 2 9 3 9 4 9 4 8 3 8 3 7 4 7 5 7 5 6 5 5 6 5 6 6 6 7 7 7 8 7 8 8 7 8 6 8 5 8 5 9 5 10 5 11 6 11 6 10 6 9 7 9 8 9 8 10 7 10 7 11 8 11 9 11 9 10 9 9 10 9 10 10 10 11 11 11 11 10 11 9 11 8 11 7 10 7 10 8 9 8 9 7 9 6 10 6 11 6 11 5 11 4 11 3 10 3 9 3 9 4 9 5 8 5 8 4 8 3 8 2 8 1 9 1 10 1 10 0 9 0 8 0 7 0 7 1 7 2 6 2 5 2 5 1 6 1 6 0 5 0 4 0 3 0 2 0 2 1 3 1 4 1 4 2 4 3 5 3 6 3 7 3 7 4 6 4 5 4 4 4 4 5 4 6 3 6 3 5 3 4 3 3 3 2 2 2 2 3 1 3 1 2 1 1 1 0 0 0 0 1 0 2 0 3 0 4 0 5 0 6 1 6 1 5 1 4 2 4 2 5 2 6 2 7 1 7 1 8 0 8 0 9 0 10

```

Code:

```
I=raw_input().split('\n');X=len(I[0]);Y=len(I);R=range
def S(g=0,c=0,x=0,y=0):
    if y>=Y:return 0
    if g==0:g=[[-1]*X for i in R(Y)];c=[[-1]*X for i in R(Y)]
    o={'.':set(R(7)),'w':{1,2},'b':{3,4,5,6}}[I[y][x]].copy()
    o&={0,1,3,4}if y<1 or g[y-1][x]in[0,1,5,6]else{2,5,6}
    o&={0,2,4,5}if x<1 or g[y][x-1]in[0,2,3,6]else{1,3,6}
    if y>Y-2:o&={0,1,5,6}
    if x>X-2:o&={0,2,3,6}
    if y>0 and g[y-1][x]in[2,3,4]:
        if'b'==I[y][x]and g[y-1][x]!=2:return 0
        if'b'==I[y-1][x]:o&={2}
        elif'w'==I[y-1][x]and g[y-2][x]==2:o&={5,6}
    if x>0 and g[y][x-1]in[1,4,5]:
        if'b'==I[y][x]and g[y][x-1]!=1:return 0
        if'b'==I[y][x-1]:o&={1}
        elif'w'==I[y][x-1]and g[y][x-2]==1:o&={3,6}
    h=[r[:]for r in c]
    if y>0 and g[y-1][x]in[2,3,4]:
        if x>0 and g[y][x-1]in[1,4,5]:
            if c[y-1][x]==c[y][x-1]:
                if(6 not in o)+any(any(i!=c[y-1][x]and i!=-1 for i in r)for r in c)+any(I[v][u]!='.'and(v>y)+(u>x)for v in R(y,Y)for u in R(X)):return 0
                g[y][x]=6
                for v in R(y,Y):
                    for u in R(X):
                        if v!=y or u>x:g[v][u]=0
                for y in R(Y):
                    for x in R(X):
                        if g[y][x]>0:break
                f=[];d=-1;u,v=p,q=x,y
                while(u,v)!=(p,q)or-1==d:f+=[u,v];d=([0,{0,2},{1,3},{2,3},{0,3},{0,1},{1,2}][g[v][u]]-{(d+2)%4}).pop();i,j={0:(u+1,v),1:(u,v-1),2:(u-1,v),3:(u,v+1)}[d];u,v=i,j
                return f
            else:
                for v in R(y+1):
                    for u in R(X):
                        if h[v][u]==c[y][x-1]:h[v][u]=c[y-1][x]
                h[y][x]=c[y-1][x]
        else:h[y][x]=c[y-1][x]
    elif x>0 and g[y][x-1]in[1,4,5]:h[y][x]=c[y][x-1]
    else:h[y][x]=max(max(r)for r in c)+1
    for n in sorted(list(o))[::-1]:
        if n==0:h[y][x]=-1
        if x>X-2:i,j=0,y+1
        else:i,j=x+1,y
        g[y][x]=n;r=S(g,h,i,j)
        if r!=0:return r
    return 0
for i in S():print i,

```

Ungolfed:

```
class Grid:
    def __init__(self,input):
        self.input = input.split('\n')
        self.x = len(self.input[0])
        self.y = len(self.input)
        self.options = {'.':{0,1,2,3,4,5,6},'w':{1,2},'b':{3,4,5,6}}

    def convert(self,grid):
        directions = [None,{0,2},{1,3},{2,3},{0,3},{0,1},{1,2}]

        for y in range(self.y):
            for x in range(self.x):
                if grid[y][x] != 0:
                    break

        chain = []
        start_pos = (x,y)
        dir = -1
        pos = start_pos
        while dir == -1 or pos != start_pos:
            chain.extend(pos)
            x,y = pos
            next_dir = (directions[grid[y][x]]-{(dir+2)%4}).pop()
            if next_dir == 0: nx,ny = x+1,y
            elif next_dir == 1: nx,ny = x,y-1
            elif next_dir == 2: nx,ny = x-1,y
            elif next_dir == 3: nx,ny = x,y+1
            dir = next_dir
            pos = (nx,ny)

        return chain

    def solve(self,grid=None,chain_ids=None,pos=(0,0)):
        x,y = pos
        if y >= self.y:
            return None

        if grid is None:
            grid = [[-1]*self.x for i in range(self.y)]
        if chain_ids is None:
            chain_ids = [[-1]*self.x for i in range(self.y)]

        options = self.options[self.input[y][x]].copy()
        if y == 0 or grid[y-1][x] in [0,1,5,6]:
            options &= {0,1,3,4}
        else:
            options &= {2,5,6}
        if y == self.y-1:
            options &= {0,1,5,6}

        if x == 0 or grid[y][x-1] in [0,2,3,6]:
            options &= {0,2,4,5}
        else:
            options &= {1,3,6}
        if x == self.x-1:
            options &= {0,2,3,6}

        if y != 0 and grid[y-1][x] in [2,3,4]:
            if self.input[y][x] == 'b' and grid[y-1][x] != 2:
                return None
            if self.input[y-1][x] == 'b':
                options &= {2}
            elif self.input[y-1][x] == 'w':
                if grid[y-2][x] == 2:
                    options &= {5,6}
        if x != 0 and grid[y][x-1] in [1,4,5]:
            if self.input[y][x] == 'b' and grid[y][x-1] != 1:
                return None
            if self.input[y][x-1] == 'b':
                options &= {1}
            elif self.input[y][x-1] == 'w':
                if grid[y][x-2] == 1:
                    options &= {3,6}

        new_chain_ids = [[i for i in row] for row in chain_ids]
        if y != 0 and grid[y-1][x] in [2,3,4]:
            if x != 0 and grid[y][x-1] in [1,4,5]:

                if chain_ids[y-1][x] == chain_ids[y][x-1]:
                    if 6 not in options:
                        return None

                    if any(any(i != chain_ids[y-1][x] and i != -1 for i in row) for row in chain_ids) or \
                    any(self.input[v][u] != '.' and (v!=y or u>x) for v in range(y,self.y) for u in range(self.x)):
                        return None

                    grid[y][x] = 6
                    for v in range(y,self.y):
                        for u in range(self.x):
                            if v != y or u > x:
                                grid[v][u] = 0

                    return self.convert(grid)

                else:
                    for v in range(y+1):
                        for u in range(self.x):
                            if new_chain_ids[v][u] == chain_ids[y][x-1]:
                                new_chain_ids[v][u] = chain_ids[y-1][x]
                    new_chain_ids[y][x] = chain_ids[y-1][x]

            else:
                new_chain_ids[y][x] = chain_ids[y-1][x]
        elif x != 0 and grid[y][x-1] in [1,4,5]:
            new_chain_ids[y][x] = chain_ids[y][x-1]
        else:
            new_chain_ids[y][x] = max(max(row) for row in chain_ids)+1

        for n in sorted(list(options),key=lambda n: -n):
            grid[y][x] = n
            if n == 0:
                new_chain_ids[y][x] = -1

            if x == self.x-1:
                nx,ny = 0,y+1
            else:
                nx,ny = x+1,y

            result = self.solve(grid,new_chain_ids,(nx,ny))
            if result is not None:
                return result

input = """

.....w.b.w..
ww..b...b...
.w.....b....
...wbww..b.b
....b.......
w.w.........
..w......b.b
.....bb.....
.....b.....w
w.ww..b.....
...w......w.
b..w.....b..

""".strip()

def print_grid(grid):
    for y,row in enumerate(grid):
        s = ""
        for i in row:
            s += {-1:'xxx',0:'   ',1:'   ',2:' | ',3:'   ',4:'   ',5:' | ',6:' | '}[i]
        s += '\n'
        for x,i in enumerate(row):
            s += {-1:'x%sx',0:' %s ',1:'-%s-',2:' %s ',3:'-%s ',4:' %s-',5:' %s-',6:'-%s '}[i] % input.split('\n')[y][x]
        s += '\n'
        for i in row:
            s += {-1:'xxx',0:'   ',1:'   ',2:' | ',3:' | ',4:' | ',5:'   ',6:'   '}[i]
        s += '\n'
        print s

result = Grid(input).solve()
print result

```
> 10 votes

# Answer
# Lua, ~~830~~ ~~810~~ ~~765~~ ~~752~~ ~~739~~ ~~729~~ 710

Runs board1 and board2 just fine, but takes a while on board3.

It could save 9 bytes by outputting *every* path instead of just the first...

```
b={}s={0,0,0}R=table.insert Z=unpack for l in io.lines()do w=#l for i=1,w do
c=({b=1,w=2,['.']=3})[l:sub(i,i)]R(b,c)s[c]=s[c]+1 end end h=#b/w for e=0,w*h-1
do function g(p,d,X,t)local function G(I,r)T={Z(t)}a=b[I+1]T[a]=T[a]+1
P={Z(p)}D={Z(d)}R(P,I%w)R(P,I/w-I/w%1)R(D,r)l=#D for U=2,#p,2 do if
I==p[U-1]+w*p[U]then return end end if I==e then if T[1]==s[1]and T[2]==s[2]then
for k=1,l do K=D[k]M=D[(k-2)%l+1]N=D[k%l+1]O=D[(k+1)%l+1]if({K==N or K~=M or
N~=O,K~=N or(K==M and N==O)})[b[1+P[2*k-1]+w*P[2*k]]]then return end end
os.exit(print(table.concat(P,' ')))end else g(P,D,I,T)end end _=X%w<w-1 and
G(X+1,1)_=X/w-X/w%1<h-1 and G(X+w,2)_=X%w>0 and G(X-1,3)_=X/w-X/w%1>0 and
G(X-w,4)end g({},{},e,{0,0,0})end

```
> 2 votes

---
Tags: code-golf, puzzle-solver, grid
---


# Question
Title: Day of the week for a given date of this year. Do not use any date tools
Please write a program that takes as input two numbers 'day of the month' and 'month number' for any day of this year (2012) and outputs day of the week. Examples:

```
% ruby ./golf.rb 14 07 # 14th of July
"Sat"
% ruby ./golf.rb 14 7  # the same
"Sat"
% ruby ./golf.rb 01 12 # Dec 1
"Sat"
% ruby ./golf.rb 31 12 # Last day of the year
"Mon"

```
* Output format should be like `Mon, Tue, Wed, Thu, Fri, Sat, Sun`, not less than 3 letters
* Do not use date libs/modules, just math and logic
* Wins the shortest script in any language.

# Answer
> 4 votes
## GolfScript (46 44 chars)

```
~.5*1$8>+2/\3<++7%"WedThuFriSatSunMonTue"3/=

```

Calculation can be more efficient than lookup if the days are rotated. I doubt that the mapping to day names can get shorter, but it may still be possible to shave a character or two off the hash function.

However, my best idea for how to do it, finding a power which starts with a suitable string, doesn't look like a contender. After about 9 CPU-days of brute forcing I found a couple of solutions, but they're also 44 chars. The faster one is

```
~16795 33303?`=+7%"WedThuFriSatSunMonTue"3/=

```

# Answer
> 4 votes
# C++ (142) (135)  (129 chars)

```
main(){string s[]={"Mon","Tue","Wen","Thu","Fri","Sat","Sun"};int d,m,t[]={0,5,1,1,4,6,2,4,0,3,5,1,3};cin>>d>>m;cout<<s[(d+t[m]+15-(m<3))%7];}

```

The requirement that the letters Mon, Tue etc. appear made it quite bad, otherwise it would be only **84 chars**. I'll search a golf for the strings...

Hm, trying to golf the string only made it 2 chars longer, but I find it more aesthetically pleasing.

```
main(){char s[]={"MonTueWenThuFriSatSun"};int d,m,t[]={0,5,1,1,4,6,2,4,0,3,5,1,3};cin>>d>>m;d=((d+t[m]+15-(m<3))%7)*3;s[d+3]=0;printf("%s",s+d);}

```

Well, this for my first entry at a golf contest, I have still much to learn...

HA! Got it!

```
main(){char s[]={"MonTueWenThuFriSatSun"},t[]={"0511462403513"};int d,m;cin>>d>>m;d=((d+t[m]-33-(m<3))%7)*3;s[d+3]=0;printf("%s",s+d);}

```

with a well set compiler and some luck we might chop another 3 characters, by using char\* instead of char\[\], but it will crash on most systems. Anyway, it doesn't matter, as I believe soon someone will post a solution in J or K with less than 10 characters, as usual :P

I'll never give up!

```
main(){char s[]={"MonTueWenThuFriSatSun0511462403513"};int d,m;cin>>d>>m;d=((d+s[m+21]-33-(m<3))%7)*3;s[d+3]=0;printf("%s",s+d);}

```

# Answer
> 4 votes
# c, 101 chars

```
d,m;main(){scanf("%d %d",&d,&m);printf("%.3s\n","SunMonTueWedThuFriSat"+(d+".034025036146"[m])%7*3);}

```

# Answer
> 3 votes
## APL (~~57~~ 56)

```
D M←⎕⋄3↑'MonTueWedThuFriSatSun'↓⍨3×7|D+⍎M⌷'512503514624'

```

# Answer
> 3 votes
### Ruby, 75 74

Ok, my ruby:

```
a,b=$*.map &:to_i;p:MonTueWedThuFriSatSun[(a-:x365274263153[b].to_i)%7*3,3]

```

Saved one char:

```
a,b=$*;p:MonTueWedThuFriSatSun[(a.to_i-:x365274263153[b.to_i].to_i)%7*3,3]

```

# Answer
> 2 votes
## Python3 ~~(93)~~ (86)

```
print("MTWTFSSouehraunenuitn"[eval('%s+%s+14'%(input(),"0512573514624"[int(input())]))%7::7])

```

Thanks to `vsz`. That is just his idea translated to python (plus comments, plus python-tricks).

```
print("MTWTFSSouehraunenuitn"[(int(input())+int("0512573514624"[int(input())]))%7::7])

```

# Answer
> 2 votes
# Pip, 44

**Not a competing entry, language is newer than question.**

```
("SunMonTueWedThuFriSat"<>3a+562361462503@b)

```

Pip is my imperative code-golf language. The code above requires today's version of the interpreter (`0.15.04.23` or newer) for the `<>` operator.

Command-line arguments are stored into `a` and `b` automatically. The program uses a simple lookup-table approach; taking advantage of the fact that numbers and strings are the same data type in Pip, we can define the table via integer literal, get a digit out by subscripting, and again do math with the result. As in CJam, subscripts are cyclic; so when `b` is 12, `562361462503@b` gives `5`.

`<>` is the grouping operator: `"Hello"<>2` gives the list `["He";"ll";"o"]`, for instance. We then use the `( )` alternate subscripting syntax (again taking advantage of cyclic subscripts to avoid needing `%7`) to grab the appropriate day name, which is auto-printed.

(The main use of the `(x y z)` syntax--borrowed from Lisp--is to call a function `x` with args `y` and `z`; but if `x` is a list or string, the operation is subscripting instead. The typical subscript operator, `@`, is very high-precedence, so when the subscript or list are compound expressions like here, the function-call syntax saves on extra parentheses that `@` would require.)

# Answer
> 1 votes
## C, 96 chars

Reads from standard input. Usage: `echo 23 7 | ./a.out`

```
main(a,b){
    scanf("%d%d",&a,&b);
    a+=b*30.56-(b>2);
    puts("Thu\0Fri\0Sat\0Sun\0Mon\0Tue\0Wed"+a%7*4);
}

```

The formula `b*30.56`, rounded down, gives the accumulated number of days before each month, assuming a 30-day February. `-(b>2)` corrects for 2012's 29-day February.

# Answer
> 0 votes
Python (130 chars)

```
d=raw_input().split()
n=int(d[0])+sum([31,29,31,30,31,30,31,31,30,31,30,31][:int(d[1])-1])-1
print 'SMTWTFSuouehranneduit'[n%7::7]

```

It's rather longish for Python, but I like it.

# Answer
> 0 votes
# Factor 98

```
: day ( x x -- x )
{ 0 3 6 5 2 7 4 2 6 3 1 5 3 } nth - 7 mod "MonTueWedThuFriSatSun" 3 group nth ;

```

Output:

```
( scratchpad ) 23 7 day

--- Data stack:
"Mon"

```

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


title: Recognize Twin Primes by Crashing

text:
# Question
Title: Recognize Twin Primes by Crashing
# Background Story

Bob was handed the following assignment for his programming class. **Please note: this is not the actual challenge.**

> **Homework assignment 11: Twin primes**
>
> Input: an integer `n ≥ 8`, taken from STDIN.
>
> Output: a message to STDOUT, depending on `n`:
>
> * If `n` is not a prime number, output `Not prime.`
> * If `n` is a prime number, but neither of `n - 2` and `n + 2` is, output `Isolated prime.`
> * If `n` and `n + 2` are both prime numbers, output `Lower twin prime.`
> * If `n` and `n - 2` are both prime numbers, output `Upper twin prime.`

Bob tried hard to solve the assignment, but his program kept crashing, and in the end, he gave up and submitted it in hope of partial credit. Nevertheless, Bob's program has the curious property that even though it never does what it's supposed to, the input is still classified correctly depending on the program's behavior: non-primes result in no output, isolated primes in a crash, lower twin primes in an infinite loop with no output, and upper twin primes in an infinite loop that keeps printing the correct message.

# The Task

Your task is to replicate the behavior or Bob's solution. In other words, write a program that reads a single integer `n ≥ 8` from STDIN or closest equivalent, and does the following:

* If `n` is not a prime number, output nothing and exit gracefully.
* If `n` is a prime number, but none of `n - 2` or `n + 2` is, produce a runtime error of some kind. Stack overflows count as runtime errors.
* If `n` and `n + 2` are both prime numbers, output nothing, but keep running until the program is killed manually (or until you run out of memory).
* If `n` and `n - 2` are both prime numbers, repeatedly output `Upper twin prime.`, with or without a trailing newline, to STDOUT or closest equivalent until the program is killed manually (or until you run out of memory).

Incorrect inputs can be ignored.

# Scoring

The idea is that your program should appear correct, but contain hidden bugs that result in the above behavior. Your program should also be short (since programming assignments are graded by hand), but popularity is more important. Thus, your score is **number of upvotes - (byte count / 100)**, higher score being better. Note that your score can be negative.

# Answer
> 12 votes
# TI-BASIC, ~269

```
Input N
Lbl 1
2→P                                       :"  test N for divisibility by each prime
Lbl 2
If int(N/P)=N/P:Goto 3    :"composite"
If PP>N:Goto 4
P+1→P
Goto 2
Lbl 3
Disp "                NOT PRIME.               "
Stop
Lbl 4
If int((N+2)/3)=(N+2)/3                    :" determine which nearby value to test
Then:N-2→R
Else:N+2→R
End
2→P
Lbl 5
If int(R/P)=R/P:Goto 6    :"composite"
If PP>R:Goto 7
P+1→P
Goto 5
Lbl 6
Output("ISOLATED PRIME.")
Lbl 7          :" TI-BASIC how two ways of printing:
               :" Disp goes to the main screen,
               :" and Output goes to the graphical screen.
               :" This program uses both methods.
If R=N+2:Goto 5              :" go to print "lower twin prime"
Disp "UPPER TWIN PRIME"
Goto 7          :" only 16 chars can be printed per line, so we'll do the period separately (last line of program)
Lbl 5
Output("LOWER TWIN PRIME")
Lbl 7
Disp "."

```

> The NOT PRIME string has sixteen leading spaces, so nothing (except an ellipsis) will be printed, as noted in the comments.
> The ISOLATED PRIME string uses the `Output()` function, which requires two numbers (the coordinates of the printing location). This triggers an Argument Error.
> The LOWER TWIN PRIME string is indicated by the link to `Lbl 5`, which was already defined as the start of the twin prime test, causing an infinite loop.
> The UPPER TWIN PRIME string is followed by a link to the period, but `Lbl 7` was already defined above, triggering an infinite loop.

# Answer
> 5 votes
# CJam - 163 bytes

```
{:S;0:I;{SI=__31>\127<&{oI):I;}{S\-;0:I;}?IS,<}gNo}:P;ri:Xmp{X2+mp{"Lower twin prime."P}{X2-mp{"Upper twin prime."P}{"Isolated prime."P}?}?}{"Not prime":P}?;

```

You can try it at http://cjam.aditsu.net/ , but in the "upper twin prime" case, you can only see the output if you use the java interpreter as the online interpreter waits for the program to finish before showing the output.

Bob started to write the program in CJam, but kept getting some weird errors so he suspected that he got some invalid characters somewhere. In an attempt to debug the issue, he implemented his own print function that checks every character:

```
{                     begin
    :S;               store the argument in S
    0:I;              initialize I with 0
    {                 do..
        SI=__         get the I'th character and make 2 more copies
        31>\127<&     check that the character code is strictly between 31 and 127
        {             if true
            oI):I;    print the character and increment I
        }{            else
            S\-;      remove the character from S
            0:I;      start again from 0
        }?            end if
        IS,<          check if I < length(S)
    }g                ..while the above is true
    No                print a newline
}:P;                  end function P

```

He tested the function, e.g. `"foo"P`, and it worked fine.

Then he wrote the main code:

```
ri:X                                read token, convert to integer and store in X
mp{                                 if X is prime
    X2+mp{                          if X+2 is prime
        "Lower twin prime."P        print "Lower twin prime."
    }{                              else
        X2-mp{                      if X-2 is prime
            "Upper twin prime."P    print "Upper twin prime."
        }{                          else
            "Isolated prime."P      print "Isolated prime."
        }?                          end if
    }?                              end if
}{                                  else
    "Not prime."P                   print "Not prime."
}?                                  end if

```

The algorithm seems perfectly fine, yet the program does what the question says... so poor Bob is really stumped.

Hint 1:

> The program at the top is not 100% identical to the program in the explanation

Hint 2:

> While the P function works fine for normal strings, it has a bug when dealing with invalid characters

Hint 3:

> The number of characters in the code is not equal to the number of bytes

Full explanation:

> \- "S\\-;" does the character removal but does not modify S, so if S has invalid characters, P goes into an infinite loop.
> \- The "Lower twin prime." and "Upper twin prime." strings have a zero-width space (unicode character) at the beginning and end, respectively; thus the first one loops without printing anything and the 2nd one loops after printing the correct message
> \- The last lines in the explanation should actually be:
> "Not prime":P - store "Not prime" in variable P, leaving it on the stack
> }? - end if
> ; - pop value (resulting in no output for "Not prime":P and error for "Isolated prime."P since the stack is empty after printing)

# Answer
> 1 votes
# Tcl, 2416

```
# This function is copied from http://wiki.tcl.tk/5996,
# which is in public domain according to http://wiki.tcl.tk/4381
proc primetest n {
    set max [expr wide(sqrt($n))]
    if {$n%2==0} {return [list 2 [expr $n/2]]}
    for {set i 3} {$i<=$max} {incr i 2} {
        if {$n%$i==0} {return [list $i [expr $n/$i]]}
    }
    return 1
}

set n [gets stdin]
                                          # Input n.
set result ""
                                          # Some initialization which seemed to be useless.
if {[primetest $n]==1} {
                                          # In Tcl, { opens a string where everything in
  if {[primetest [expr {$n-2}]]==1||[primetest [expr {$n+2}]]==1} {
                                                                       # it isn't escaped.
    if {[primetest [expr {$n-2}]]==1} {
                                          # Needless to say, The closing character for
      set result "Upper twin prime.\n";
                                          # those strings is obviously }; while 1 {
      puts -nonewline $result
                                          # corresponds to the 1 matching }; there can
    } {
                                          # be more matching pairs of { } between them.
      set result "Lower twin prime.\n"
                                          # Escaped braces like \{ \} don't match each
      puts -nonewline $result
                                          # other, but the backslashes won't be removed
    }
                                          # so \{ won't become {. This kind of strings
  } {
                                          # worked well in representing blocks of code.
    set result "Isolated prime.\n"
                                          # And control structures like if, for, while,
    puts -nonewline $result
                                          # and even functions just take strings as
  }
                                          # parameters and evaluate them when necessary.
} {
                                          # After the } closing an if statement, there can
  set result "Not prime.\n"
                                          # be another parameter for the else block.
  puts -nonewline $result
                                          # Read the above comments carefully if you didn't
}
                                          # find the underhanded part yet.

```

I wrote this before realizing there can't be end of line comments in Tcl. So this became ugly and more suspicious. But well...

---
Tags: code-challenge, primes, underhanded
---


title: String to Image

text:
# Question
Title: String to Image
A bit of background:

When I first learned about Brainf\*ck, one of the first things I did was to write a Java application that would take in a string and create a, somewhat, optimized program to print said string.

Recently, I've been playing around with Piet, and I have been playing with doing the same thing. I have realized that Piet is a rather interesting language that adds a bit to this challenge.

So, I wanted to put the challenge out to my friends at SE. Let's see what you can do with this language.

## The Challenge

Write a program or function that takes in some non-empty string of ASCII characters. Process the string so that you generate a Piet program that will print the string and terminate.

Output is a piet source image in whatever format is best for you. PNG is preferred, but not mandatory.

Piet functionality can be tested here.

The Piet code **must** generate the output string itself. No input from users is allowed.

Only Piet-Approved colors may be used, as seen below:

As this is a popularity contest, winners will be chosen by votes. Ties will be broken by source code size.

Bonus points will be awarded at my discretion based on the creativity of the output images. These are pictures, after all.

# Answer
> 9 votes
## C, (78 + 26 * strlen) codels

This was surprisingly tricky to optimize, mostly because of the possibility of color collisions in neighbouring lines.

The characters are converted to base 12, so each character is a 2-digit number. Every standard line contains the following: pointer (now right for odd lines, left for even lines), duplicate (the number 12, which is first on the stack), push (1st digit), multiply, push (2nd digit), add, outc, push (1 for odd lines, 3 for even lines), duplicate, whitespace, pointer (now down at the end of the line).

To avoid color collisions in neighbouring lines the state after whitespace filling is remembered, and the generation is rolled back to it if a collision happens. The next try starts there with the next color.

Output for "Hello Piet!":

**asciipiet2.c**

```
#include "img.h"

#define WIDTH 26
#define OP(op, h, d) int op() { hue += h; dark += d; hue %= 6; dark %= 3; return setp(); }
#define CCMP(c1, c2) (((c1).r == (c2).r) && ((c1).g == (c2).g) && ((c1).b == (c2).b))
#define OPCNT(op) if(op) continue

Color piet[6][2] =
{
    {{0xff, 0xc0, 0xc0}, {0xff, 0x00, 0x00}, {0xc0, 0x00, 0x00}},
    {{0xff, 0xff, 0xc0}, {0xff, 0xff, 0x00}, {0xc0, 0xc0, 0x00}},
    {{0xc0, 0xff, 0xc0}, {0x00, 0xff, 0x00}, {0x00, 0xc0, 0x00}},
    {{0xc0, 0xff, 0xff}, {0x00, 0xff, 0xff}, {0x00, 0xc0, 0xc0}},
    {{0xc0, 0xc0, 0xff}, {0x00, 0x00, 0xff}, {0x00, 0x00, 0xc0}},
    {{0xff, 0xc0, 0xff}, {0xff, 0x00, 0xff}, {0xc0, 0x00, 0xc0}}
};

Color white = {0xff, 0xff, 0xff};

Image img;
int hue, dark, x, y, dx = 1;

void nextline()
{
    x -= dx;
    dx = -dx;
    y += 1;
}

int setp()
{
    if(y > 0 && CCMP(piet[hue][dark], imgGetP(img, x, y - 1)))
    {
        return 1;
    }
    imgSetP(img, x, y, piet[hue][dark]);
    x += dx;
    return 0;
}

void whiteto(int to)
{
    if(dx == 1)
    {
        while(x < to) imgSetP(img, x++, y, white);
    }
    else
    {
        while(x >= WIDTH - to) imgSetP(img, x--, y, white);
    }
}

OP(fill,    0, 0)
OP(pushraw, 0, 1)
OP(pop,     0, 2)
OP(add,     1, 0)
OP(sub,     1, 1)
OP(mul,     1, 2)
OP(divi,    2, 0)
OP(mod,     2, 1)
OP(not,     2, 2)
OP(gt,      3, 0)
OP(pnt,     3, 1)
OP(sw,      3, 2)
OP(dup,     4, 0)
OP(roll,    4, 1)
OP(in,      4, 2)
OP(inc,     5, 0)
OP(out,     5, 1)
OP(outc,    5, 2)

int push(int num);
int pushn(int num)  { int i; for(i = 0; i < num - 1; ++i) { if(fill()) return 1; } return pushraw(); }
int push0()         { return (push(1) || not()); }
int push8()         { return (push(2) || dup() || dup() || mul() || mul()); }
int push9()         { return (push(3) || dup() || mul()); }
int push10()        { return (push(9) || push(1) || add()); }
int push11()        { return (push(9) || push(2) || add()); }
int push(int num)
{
    switch(num)
    {
    case 0:  return push0();
    case 8:  return push8();
    case 9:  return push9();
    case 10: return push10();
    case 11: return push11();
    default: return pushn(num);
    }
}

int main(int argc, char* argv[])
{
    char* str;
    int len, i;

    if(argc != 2)
    {
        printf("Usage: %s \"string to print\"\n", argv[0]);
        return -1;
    }

    str = argv[1];
    len = strlen(str);

    imgCreate(img, WIDTH, len + 3);

    fill(); push(4); push(3); mul(); push(1); dup(); whiteto(WIDTH - 2);
    for(i = 0; i < len; ++i)
    {
        int var, sx = x, sy = y, sdx = dx, fin = 0, off = rand();
        for(var = 0; var < 18 && !fin; var++)
        {
            x = sx; y = sy; dx = sdx;
            hue = ((var + off) % 18) / 3; dark = ((var + off) % 18) % 3;

            OPCNT(fill()); OPCNT(pnt());
            nextline(); pnt(); dup();
            OPCNT(push(str[i] / 12)); OPCNT(mul()); OPCNT(push(str[i] % 12)); OPCNT(add()); OPCNT(outc()); OPCNT(push(2 - dx)); if(i != len - 1) { OPCNT(dup()); }
            whiteto(WIDTH - 2);
            fin = 1;
        }
        if (!fin)
        {
           printf("collision unavoidable\n");
           return -1;
        }
    }
    x -= dx;
    {
        int var, sx = x, sy = y, sdx = dx, fin = 0;
        for(var = 0; var < 18 && !fin; var++)
        {
            x = sx; y = sy; dx = sdx;
            hue = var / 3; dark = var % 3;
            OPCNT(fill()); OPCNT(pnt()); OPCNT(fill());
            fin = 1;
        }
        if (!fin)
        {
            printf("collision unavoidable\n");
            return -1;
        }
    }
    x -= 2 * dx;
    y += 1;
    imgSetP(img, x, y, white);
    x -= dx;
    y += 1;
    hue = 0; dark = 1;
    fill(); fill(); fill();

    imgSave(img, "piet.pnm");

    return 0;
}

```

**img.h**

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

typedef struct
{
   unsigned char r;
   unsigned char g;
   unsigned char b;
} Color;

typedef struct
{
   Color* data;
   int width;
   int height;
} Image;

#define imgCreate(img, w, h)           {\
                                          int length;\
                                          (img).width = (w);\
                                          (img).height = (h);\
                                          length = (img).width * (img).height * sizeof(Color);\
                                          (img).data = malloc(length);\
                                          memset((img).data, 0, length);\
                                       }

#define imgDestroy(img)                {\
                                          free((img).data);\
                                          (img).width = 0;\
                                          (img).height = 0;\
                                       }

#define imgGetP(img, x, y)             ((img).data[(int)(x) + (int)(y) * (img).width])

#define imgSetP(img, x, y, c)          {\
                                          (img).data[(int)(x) + (int)(y) * (img).width] = c;\
                                       }

#define imgLine(img, x, y, xx, yy, c)  {\
                                          int x0 = (x), y0 = (y), x1 = (xx), y1 = (yy);\
                                          int dx =  abs(x1 - x0), sx = x0 < x1 ? 1 : -1;\
                                          int dy = -abs(y1 - y0), sy = y0 < y1 ? 1 : -1;\
                                          int err = dx + dy, e2;\
                                          \
                                          for(;;)\
                                          {\
                                             imgSetP((img), x0, y0, c);\
                                             if (x0 == x1 && y0 == y1) break;\
                                             e2 = 2 * err;\
                                             if (e2 >= dy) {err += dy; x0 += sx;}\
                                             if (e2 <= dx) {err += dx; y0 += sy;}\
                                          }\
                                       }

#define imgSave(img, fname)            {\
                                          FILE* f = fopen((fname), "wb");\
                                          fprintf(f, "P6\n%d %d\n255\n", (img).width, (img).height);\
                                          fwrite((img).data, sizeof(Color), (img).width * (img).height, f);\
                                          fclose(f);\
                                       }

#define imgLoad(img, fname)            {\
                                          FILE* f = fopen((fname), "rb");\
                                          char buffer[16];\
                                          int index = 0;\
                                          int field = 0;\
                                          int isP5 = 0;\
                                          unsigned char c = ' ';\
                                          while(field < 4)\
                                          {\
                                             do\
                                             {\
                                                if(c == '#') while(c = fgetc(f), c != '\n');\
                                             } while(c = fgetc(f), isspace(c) || c == '#');\
                                             index = 0;\
                                             do\
                                             {\
                                                buffer[index++] = c;\
                                             } while(c = fgetc(f), !isspace(c) && c != '#' && index < 16);\
                                             buffer[index] = 0;\
                                             switch(field)\
                                             {\
                                                case 0:\
                                                   if (strcmp(buffer, "P5") == 0) isP5 = 1;\
                                                   else if (strcmp(buffer, "P6") == 0) isP5 = 0;\
                                                   else fprintf(stderr, "image format \"%s\" unsupported (not P5 or P6)\n", buffer), exit(1);\
                                                   break;\
                                                case 1:\
                                                   (img).width = atoi(buffer);\
                                                   break;\
                                                case 2:\
                                                   (img).height = atoi(buffer);\
                                                   break;\
                                                case 3:\
                                                   index = atoi(buffer);\
                                                   if (index != 255) fprintf(stderr, "image format unsupported (not 255 values per channel)\n"), exit(1);\
                                                   break;\
                                             }\
                                             field++;\
                                          }\
                                          imgCreate((img), (img).width, (img).height);\
                                          if (isP5)\
                                          {\
                                             int length = (img).width * (img).height;\
                                             for(index = 0; index < length; ++index)\
                                             {\
                                                (img).data[index].r = (img).data[index].g = (img).data[index].b = fgetc(f);\
                                             }\
                                          }\
                                          else\
                                          {\
                                             fread((img).data, sizeof(Color), (img).width * (img).height, f);\
                                          }\
                                          fclose(f);\
                                       }

```

# Answer
> 5 votes
## C, (384 + 256 * strlen) codels, no optimization

No clever hacking in this solution. Every character is represented by a single line with height in pixels = ascii value. Op sequence is then push, outc, push, outc, ...

Output for "Hello Piet!" (and zoom of top part):

**asciipiet.c**

```
#include "img.h"

Color piet[6][3] = {
    {{0xff,0xc0,0xc0},{0xff,0x00,0x00},{0xc0,0x00,0x00}},
    {{0xff,0xff,0xc0},{0xff,0xff,0x00},{0xc0,0xc0,0x00}},
    {{0xc0,0xff,0xc0},{0x00,0xff,0x00},{0x00,0xc0,0x00}},
    {{0xc0,0xff,0xff},{0x00,0xff,0xff},{0x00,0xc0,0xc0}},
    {{0xc0,0xc0,0xff},{0x00,0x00,0xff},{0x00,0x00,0xc0}},
    {{0xff,0xc0,0xff},{0xff,0x00,0xff},{0xc0,0x00,0xc0}}
};

Color white = {0xff,0xff,0xff};

int main(int argc, char* argv[])
{
    char* str;
    int len, i, hue, dark;
    Image out;

    if(argc != 2)
    {
        printf("Usage: %s \"string to print\"\n", argv[0]);
        return -1;
    }

    str = argv[1];
    len = strlen(str);

    imgCreate(out, len * 2 + 3, 128);

    hue = 0;
    dark = 1;
    for(i = 0; i < len; i++)
    {
        imgLine(out, i * 2, 0, i * 2, str[i] - 1, piet[hue][dark]);
        dark = (dark + 1) % 3;
        imgSetP(out, i * 2 + 1, 0, piet[hue][dark]);
        dark = (dark + 2) % 3;
        hue = (hue + 5) % 6;
    }
    imgSetP(out, len * 2, 0, piet[hue][dark]);
    imgSetP(out, len * 2 + 1, 0, white);
    imgSetP(out, len * 2 + 2, 0, white);
    imgSetP(out, len * 2 + 2, 1, white);
    imgSetP(out, len * 2 + 2, 2, white);
    imgSetP(out, len * 2 + 2, 3, white);
    imgSetP(out, len * 2 + 1, 3, white);
    imgSetP(out, len * 2, 2, piet[0][4]);
    imgSetP(out, len * 2, 3, piet[0][5]);
    imgSetP(out, len * 2, 4, piet[0][6]);

    imgSave(out, "piet.pnm");

    return 0;
}

```

**img.h**

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

typedef struct
{
   unsigned char r;
   unsigned char g;
   unsigned char b;
} Color;

typedef struct
{
   Color* data;
   int width;
   int height;
} Image;

#define imgCreate(img, w, h)           {\
                                          int length;\
                                          (img).width = (w);\
                                          (img).height = (h);\
                                          length = (img).width * (img).height * sizeof(Color);\
                                          (img).data = malloc(length);\
                                          memset((img).data, 0, length);\
                                       }

#define imgDestroy(img)                {\
                                          free((img).data);\
                                          (img).width = 0;\
                                          (img).height = 0;\
                                       }

#define imgGetP(img, x, y)             ((img).data[(int)(x) + (int)(y) * (img).width])

#define imgSetP(img, x, y, c)          {\
                                          (img).data[(int)(x) + (int)(y) * (img).width] = c;\
                                       }

#define imgLine(img, x, y, xx, yy, c)  {\
                                          int x0 = (x), y0 = (y), x1 = (xx), y1 = (yy);\
                                          int dx =  abs(x1 - x0), sx = x0 < x1 ? 1 : -1;\
                                          int dy = -abs(y1 - y0), sy = y0 < y1 ? 1 : -1;\
                                          int err = dx + dy, e2;\
                                          \
                                          for(;;)\
                                          {\
                                             imgSetP((img), x0, y0, c);\
                                             if (x0 == x1 && y0 == y1) break;\
                                             e2 = 2 * err;\
                                             if (e2 >= dy) {err += dy; x0 += sx;}\
                                             if (e2 <= dx) {err += dx; y0 += sy;}\
                                          }\
                                       }

#define imgSave(img, fname)            {\
                                          FILE* f = fopen((fname), "wb");\
                                          fprintf(f, "P6\n%d %d\n255\n", (img).width, (img).height);\
                                          fwrite((img).data, sizeof(Color), (img).width * (img).height, f);\
                                          fclose(f);\
                                       }

#define imgLoad(img, fname)            {\
                                          FILE* f = fopen((fname), "rb");\
                                          char buffer[16];\
                                          int index = 0;\
                                          int field = 0;\
                                          int isP5 = 0;\
                                          unsigned char c = ' ';\
                                          while(field < 4)\
                                          {\
                                             do\
                                             {\
                                                if(c == '#') while(c = fgetc(f), c != '\n');\
                                             } while(c = fgetc(f), isspace(c) || c == '#');\
                                             index = 0;\
                                             do\
                                             {\
                                                buffer[index++] = c;\
                                             } while(c = fgetc(f), !isspace(c) && c != '#' && index < 16);\
                                             buffer[index] = 0;\
                                             switch(field)\
                                             {\
                                                case 0:\
                                                   if (strcmp(buffer, "P5") == 0) isP5 = 1;\
                                                   else if (strcmp(buffer, "P6") == 0) isP5 = 0;\
                                                   else fprintf(stderr, "image format \"%s\" unsupported (not P5 or P6)\n", buffer), exit(1);\
                                                   break;\
                                                case 1:\
                                                   (img).width = atoi(buffer);\
                                                   break;\
                                                case 2:\
                                                   (img).height = atoi(buffer);\
                                                   break;\
                                                case 3:\
                                                   index = atoi(buffer);\
                                                   if (index != 255) fprintf(stderr, "image format unsupported (not 255 values per channel)\n"), exit(1);\
                                                   break;\
                                             }\
                                             field++;\
                                          }\
                                          imgCreate((img), (img).width, (img).height);\
                                          if (isP5)\
                                          {\
                                             int length = (img).width * (img).height;\
                                             for(index = 0; index < length; ++index)\
                                             {\
                                                (img).data[index].r = (img).data[index].g = (img).data[index].b = fgetc(f);\
                                             }\
                                          }\
                                          else\
                                          {\
                                             fread((img).data, sizeof(Color), (img).width * (img).height, f);\
                                          }\
                                          fclose(f);\
                                       }

```

---
Tags: popularity-contest, graphical-output, code-generation
---