title: Tiling, given vertex configuration

text:
# Question
Title: Tiling, given vertex configuration
**Task**

The task is to tile polygons, given a vertex configuration.

**Scoring**

Your score is equal to the "complexity level" your submission reaches. Complexity levels are cumulative, meaning that to reach #3 you must also support #1 & #2.

Submissions at an equal complexity level are distinguished by byte count; lowest wins.

**Input**

Input is a string containing a vertex configuration, representing a vertex figure. That is, a dot separated list of integers, where each integer (n) represents a regular n-gon, connected by a common vertex.

The following vertex configurations must be supported:

* `3.3.3.3.3.3`
* `3.3.3.3.6`
* `3.3.3.4.4` (note that order is reflected in the vertex figure, therefore the below does differ)
* `3.3.4.3.4`
* `3.12.12`
* `3.4.6.4`
* `3.6.3.6`
* `4.4.4.4`
* `4.6.12`
* `4.8.8`
* `6.6.6`

**Output - Complexity Level #1: Vertex Figure**

At this complexity level, output is an image showing the vertex figure corresponding to the given input.

Input is prepended with an `F` to signify that the vertex figure should be output, and not the full tiling.

For example `F3.6.3.6` gives this vertex figure:

**Output - Complexity Level #2: Tiling**

At this complexity level output is an image showing a uniform tiling using the vertex figure corresponding to the given input.

For example `3.6.3.6` gives this tiling:

There are no restrictions on colour or format (barring loopholes).

**Output - Complexity Level #3: Dual Tiling**

At this complexity level a 'dual tiling' can be formed from each tiling. This is achieved by drawing lines from the centre of each polygon to the centre of each bordering polygon.

Dual tiling is specified by prepending input with a `V`.

For example `V3.6.3.6` gives this dual tiling (in red):

# Answer
> 10 votes
# BBC BASIC

**Rev 1 Golfed code, 655 ASCII characters, tokenised filesize 614**

Some major improvements to the data table, by hashing the string `A.B..N` to a number `(1*A+2*B+..n*N)+n` before looking up, and by storing only one translation vector (the other one is generated by code.) More explanation when I have finished golfing.

```
t=PI*2DIMm(9)
c=0z=0INPUTz$
FORi=1TOLEN(z$)d%=VAL(MID$(z$,i))IFd%c+=1m(c)=d%i-=d%=12z+=c*d%
NEXTREPEATREADl,e,f
UNTILl=z+c
l=4-3*(m(3)MOD3=0)-8*(l=59)
DATA69,0,70,65,100,35,66,149,0,49,109,0,52,80,0,55,0,189,39,120,0,44,40,40,58,55,95,47,136,0,59,40,0
VDU23,23,3|
FORr=-9TO19FORs=-9TO9a=1+e*(r*2+s)-f*l*s/4b=1+f*(r*2+s)+e*l*s/4p=40q=0FORk=1TOm(c)/2FORj=1TOc
n=m(j)o=TAN(PI/3)IFe=109ANDn<>4o=1
w=-p*COS(t/n)-q*SIN(t/n)q=p*SIN(t/n)-q*COS(t/n)p=w
u=p:v=q
x=a:y=b
MOVEx,y
FORi=1TO14x+=u*2y+=v*2IFVAL(z$)DRAWx,y ELSEGCOL9LINEx-u-v/o,y-v+u/o,x-u+v/TAN(PI/n),y-v-u/TAN(PI/n)
w=v*COS(t/n)-u*SIN(t/n)u=v*SIN(t/n)+u*COS(t/n)v=w
NEXTNEXT
p=u:q=v
a=x:b=y
NEXTNEXTNEXT

```

**Rev 0 Golfed code, 770 ASCII characters, tokenised filesize 728**

All I've done here is remove comments, unnecessary whitespace and quote marks, and put all the `DATA` on one line. There's certainly room for more golfing.

```
t=PI*2DIMm(9)
c=0INPUTz$
FORi=1TOLEN(z$)d%=VAL(MID$(z$,i))IFd%c+=1:m(c)=d%:i-=d%=12
NEXTREPEATREADl$,e,f,g,h
UNTILMID$(z$,1-(VAL(z$)=0))=l$
DATA3.3.3.3.3.3,240,0,120,70,3.3.3.3.6,200,70,40,210,3.3.3.4.4,80,0,40,150,3.3.4.3.4,-40,150,150,40,3.12.12,300,0,150,260,3.4.6.4,220,0,110,188,3.6.3.6,160,0,80,140,4.4.4.4,80,0,0,80,4.6.12,0,380,330,-190,4.8.8,272,0,136,136,6.6.6,240,0,120,70
VDU23,23,3|
FORr=-9TO19 FORs=0TO9a=1+e*r+g*s
b=1+f*r+h*s
p=40q=0FORk=1TOm(c)/2FORj=1TOc
n=m(j)o=TAN(PI/3):IFe=220ANDn<>4o=1
w=-p*COS(t/n)-q*SIN(t/n)q=p*SIN(t/n)-q*COS(t/n)p=w
u=p:v=q
x=a:y=b
MOVEx,y
FORi=1TO14x+=u*2y+=v*2IFVAL(z$)DRAWx,y ELSEGCOL9LINEx-u-v/o,y-v+u/o,x-u+v/TAN(PI/n),y-v-u/TAN(PI/n)
w=v*COS(t/n)-u*SIN(t/n)u=v*SIN(t/n)+u*COS(t/n)v=w
NEXTNEXT
p=u:q=v
a=x:b=y
NEXTNEXTNEXT

```

**Explanation**

This is a continuation of my previous Level 1 answer, but I decided to post it separately because it's rather long.

**Level 2**

This is achieved by translation of my "level 1.5" templates from my previous answer. The two translation vectors for each tiling are hardcoded. I take advantage of the fact that an isosceles triangle of base 80 and height 70 is a very good approximation of an equilateral triangle, and a right triangle with hypotenuse vector `(56,56)` has a hypotenuse length very close to 80.

**Level 3**

To plot the duals, instead of plotting an edge of the polygon, we plot a spoke from the middle of that edge to the centre of the polygon. This is at right angles to the edge and has length of `1/TAN/(PI/n)` times of the vector (u,v) which in turn is half as long as the edge.

Unfortunately, because certain polygons in tilings `3.3.3.3.6` and `3.4.6.4` are not plotted explicitly, they would not be plotted if we only did this. Therefore the spoke also extends outward from the polygon. The outward extension is controlled by the variable `o`.

By default the extension is sufficient to reach the centre of a triangle, but for `3.4.6.4` it needs to be extended more in order to draw the duals of the squares that are not plotted explicitly. So enough extension to fill in the missing squares is applied when hexagons and triangles are plotted explicitly, but the normal extension is applied when squares are plotted explicitly, to avoid spurious lines in the adjacent triangles.

**Here's what they look like without the spoke extensions.** The holes in the dual pattern can be clearly seen. **The correct output can be seen in the main picture** at the bottom of the answer

**Commented Code**

Differences from my previous answer are indicated inline

```
  t=PI*2                                          :REM constant Tau = PI*2

  DIMm(9)                                         :REM declare array for the numbers in the input
  c=0                                             :REM number of polygons in the list

  INPUTz$
  FORi=1TOLEN(z$)                                 :REM for each character in the input
    d%=VAL(MID$(z$,i))                            :REM use VAL to return the numeric value of the substring to the right and store to integer variable
    IF d% c+=1 :m(c)=d%: i-=d%=12                 :REM if the last character read was a number, d% contains it, otherwise 0. Advance c and store to m. If it is 12, increment i to skip a character.
  NEXT

  REM BLOCK OF NEW CODE to define vectors (e,f) and (g,h) for each possible tiling

  REPEAT
    READ l$,e,f,g,h                               :REM read an entire line of the data below
  UNTIL MID$(z$,1-(VAL(z$)=0))=l$                 :REM abort the loop when l$ coincides with the input. the MID$ strips off the 'V' from the input where necessary.

  DATA"3.3.3.3.3.3",240,0,120,70
  DATA"3.3.3.3.6",200,70,40,210
  DATA"3.3.3.4.4",80,0,40,150
  DATA"3.3.4.3.4",-40,150,150,40
  DATA"3.12.12",300,0,150,260
  DATA"3.4.6.4",220,0,110,188
  DATA"3.6.3.6",160,0,80,140
  DATA"4.4.4.4",80,0,0,80
  DATA"4.6.12",0,380,330,-190
  DATA"4.8.8",272,0,136,136
  DATA"6.6.6",240,0,120,70

  VDU23,23,3|                                           :REM change linewidth to 3 (default is 1)

  REM END BLOCK OF NEW CODE

  FORr=-9TO19 FORs=0TO9                                 :REM two new loops for translations

      a=1+e*r+g*s                                       :REM modified code for
      b=1+f*r+h*s                                       :REM coordinates to start drawing at

      p=40:q=0                                          :REM vector of first line

      FORk=1TOm(c)/2                                    :REM draw half as many vertex figures as there are sides on the last polygon in the list

        FORj=1TOc                                       :REM for each polygon on the list
          n=m(j)                                        :REM n=number of sides
          o=TAN(PI/3): IF e=220 AND n<>4 o=1            :REM new code for the spoke extension 1/o.

          w=-p*COS(t/n)-q*SIN(t/n)                      :REM rotate the starting vector anticlockwise by the internal angle of the current polygon
          q=p*SIN(t/n)-q*COS(t/n)                       :REM to avoid overlapping the previous one, if any.
          p=w

          u=p:v=q                                       :REM make a local copy of the vector and coordinates
          x=a:y=b                                       :REM to avoid corruption of p,q,a,b during the drawing of the polygon
          MOVE x,y                                      :REM move the graphics cursor to the start without drawing
          FORi=1TO14                                    :REM do 14 iterations regardless of the number of sides on the polygon
            x+=u*2                                      :REM increment x and y by the vector representing the side
            y+=v*2                                      :REM the value is double (u,v) to facilitate drawing duals later

            REM if z$ begins with a numeric character, draw an edge. If not, change to red and draw a spoke.
            IFVAL(z$) DRAW x,y ELSE GCOL9: LINEx-u-v/o,y-v+u/o,x-u+v/TAN(PI/n),y-v-u/TAN(PI/n)

            w=v*COS(t/n)-u*SIN(t/n)                     :REM rotate the vector clockwise
            u=v*SIN(t/n)+u*COS(t/n)                     :REM through the external angle of the polygon
            v=w
          NEXT                                          :REM draw next edge of the current polygon
        NEXT                                            :REM draw next polygon of the current vertex

        p=u:q=v                                         :REM once the vertex is finished, we will be two sides around the perimeter of the last polygon.
        a=x:b=y                                         :REM copy the position and direction data into p,q,a,b.
      NEXT                                              :REM draw next vertex figure

    NEXT                                                :REM close the two new translation loops
  NEXT

```

**Output**

The program performs only one tiling or dual for each run. However it plots the duals in red. To save space, I ran the program twice without clearing the screen in order to superimpose the dual on top of the regular tiling.

# Answer
> 8 votes
# Mathematica

Level 1 contains the basic tile templates that are repeatedly stamped to tile a plane.

Level 2 does the tiling.

There are still 2 tilings I haven't been able to achieve. They appear to require rotation as well as translation.

## Level 1: Vertex Figure (559 bytes)

```
nGon[n_]:=
{ColorData[46,"ColorList"][[n]],Polygon@Switch[n,
3,{{0,0},{-1/2,.866},{-1,0},{0,0}},
4,{{0,0},{0,1},{-1,1},{-1,0},{0,0}},
6,Table[{Cos[i 2Pi/n],Sin[i 2Pi/n]}+{-.5,.866},{i,0,n}],
8,Table[1.31{Cos[i Pi/4],Sin[i Pi/4]}+{-0.5`,1.207},{i,1/2,9}],
_,Table[2{Cos[i 2Pi/n],Sin[i 2Pi/n]}+{-0.5176,1.932},{i,1/2,13}]]}
innerAngle[n_]:=180-360/n
g[{}]=0;
g[a_]:=-(Plus@@innerAngle/@a)

h[{{},__,out_}]:=out
h[{list_,angles_,out_}]:=(
z=GeometricTransformation[nGon[l=list[[1]]],RotationTransform[g[angles] Degree]];
h[{Rest@list,Append[angles,l],Append[out,z]}])

```

**Testing**

```
Row[Graphics[{EdgeForm[{Blue}], #},
      ImageSize -> 70] & @@ {h[{#, {}, {}}]} & /@ {{3, 3, 3, 3, 3,
    3}, {3, 3, 3, 3, 6}, {3, 3, 3, 4, 4}, {3, 3, 4, 3, 4}, {3, 12,
    12}, {3, 4, 6, 4}, {3, 6, 3, 6}, {4, 4, 4, 4}, {4, 6, 12}, {4, 8,
    8}, {6, 6, 6}}]

```

---

## Level 2: Tiling (690 additional bytes)

The rules return tiling offsets and indents for each configuration.

`r` is the basic function that outputs the tilings.

`p` shows the template and the respective tiling. White spaces correspond to those not covered by the template.

```
rules={
{3,6,3,6}-> {2,3.47,0,0},
{4,4,4,4}-> {1,1,0,0},
{6,6,6}-> {3,2.6,1.5,0},
{3,3,3,3,3,3}-> {1.5,1.74,0,.9},
{3,3,3,3,6}-> {2,2.6,-0.4,1.8},

{4,6,12}->{4.2,4.9,0,2.5},
{3,3,4,3,4}-> {1.87,1.86,-.5,-0.5},
{4,8,8}-> {3.4,3.4,0,0},
{3,3,3,4,4}-> {2,1.87,.52,0},
{3,12,12}-> {3.82,6.73,0,0},
{3,4,6,4}-> {1.4,4.3,0(*1.375*)-1,-2.4}};

r[nGons_]:=
Module[{horizHop,vertHop,indent,downIndent},
{horizHop,vertHop,indent,downIndent}=(nGons/.rules);
Graphics[{EdgeForm[{Blue}],Table[GeometricTransformation[h[{#,{},{}}]&/@{nGons},
TranslationTransform[{
If[MemberQ[{{3,3,4,3,4},{3,3,3,3,6},{3,4,6,4}},nGons],indent *row,indent Boole[OddQ[row]]]+col horizHop,
If[MemberQ[{{3,3,4,3,4},{3,3,3,3,6},{3,4,6,4}},nGons],downIndent *col,downIndent Boole[OddQ[col]]]-row vertHop}]],
{col,0,5},{row,0,4}]},ImageSize-> 250]]

p[nGon_]:=Row[{Graphics[{EdgeForm[{Blue}],h[{nGon,{},{}}]},ImageSize->70],r@nGon}];

```

**Testing**

**Triangular tiling**

```
p[{3, 3, 3, 3, 3, 3}]

```

---

**hexagonal**

```
p[{6, 6, 6}]

```

---

**square**

```
p[{4, 4, 4, 4}]

```

---

unknown

```
p[{3, 3, 4, 3, 4}]

```

---

**truncated square**

```
p[{4, 8, 8}]

```

---

**trihexagonal**

```
p[{3, 6, 3, 6}]

```

---

**truncated hexagonal**

```
p[{3, 12, 12}]

```

---

unnamed

```
p[{3, 3, 3, 3, 6}]

```

---

**elongated triangular**

```
p[{3, 3, 3, 4, 4}]

```

---

**Tilings to figure out**

# Answer
> 6 votes
## R

**Step #1**

Here's my effort at building the tiles. Tiling to come next. This does not validate the input, so invalids will draw some weird tiles. Input is typed in after first line

```
i=as.numeric(unlist(strsplit(readline(),"[.]")))
e=c()
for(n in 1:length(i)){
    o=sum(c(0,180-360/i[1:n-1]))
    for(z in 1:i[n]){
        e=c(e,(360/i[n])*(z-1)+o)
    }
}
f=pi/180
plot(c(0,cumsum(sin(e*f))),c(0,cumsum(cos(e*f))),type="l")

```

## Step #1,#2 & #3: 1898

Finally got back to it. Most of this is taken up with setting offsets and handling special cases :). **Edit:** V flag for duals are now handled

The general process is:

* Take the input and make a list
* Create a list of angles to draw the initial tile
* Calculate centres of each polygon it the tile and the vectors from them to bisect the edges
* Determine the tile set being drawn and make a list of angle offsets. Some tiles have additional polygons added to them to assist with filling holes.
* Draw the tiles
* Draw the duals

I can probably still golf this a bit more.

```
##Get input (Enter by itself then type in the tile scheme)
i=strsplit(readline(),"[.]")[[1]]
## Run once i is set
q=0
if(substr(i[1],1,1)=="V"){q=1;i[1]=substr(i[1],2,9)}
i=as.numeric(i)
f=pi/180
e=x=y=q=p=c()
l=length(i)
d=1/(2*tan(pi/3))
g=1/(2*sin(pi/3))
for(n in 1:l){o=sum(c(0,180-360/i[1:n-1]))
r=1/(2*sin(pi/i[n]))
a=o+(180-360/i[n])/2
b=1/(2*tan(pi/i[n]))+d
for(z in 1:i[n]){x=c(x,r*sin(a*f))
y=c(y,r*cos(a*f))
q=c(q,b)
p=c(p,(360/i[n])*(z-1)+o-90)
e=c(e,(360/i[n])*(z-1)+o)}}
if(sum(i)==18&l==6){h=c(60,0);w=c(60,120)}
if(sum(i)==18&l==5){h=c(0,0,60);w=c(60,120,60)
e=c(e,0,-60,60,180,60,180)
x=c(x,g*sin(-30*f),g*sin(-30*f),g*sin(90*f))
y=c(y,1+g*cos(-30*f),1+g*cos(-30*f),1)
q=c(q,d+d,d+d,d+d)
p=c(p,-30,90,-30)}
if(sum(i)==17&l==5&sum(abs(diff(c(i,i[1]),1)))==2){h=c(0,0);w=c(90,60)}
if(sum(i)==17&l==5&sum(abs(diff(c(i,i[1]),1)))==4){h=c(0,30);w=c(270,300)}
if(sum(i)==17&l==4){h=c(0,30,-30);w=c(60,30,90)
e=c(e,150,120,210,300)
x=c(x,sin(150*f)+g*sin(90*f),sin(150*f)+sin(210*f)/2)
y=c(y,cos(150*f)+(1/(2*cos(pi/3)))*cos(90*f),cos(150*f)+cos(210*f)/2)
q=c(q,1,1)
p=c(p,210,120)}
if(sum(i)==18&l==4){h=c(0,0);w=c(120,120)}
if(sum(i)==16&l==4){h=c(0,0);w=c(90,90)}
if(sum(i)==27&l==3){h=c(0,-30,0,30);w=c(60,90,120,150,180)}
if(sum(i)==22&l==3){h=c(0,-30,30,90,60,30)
w=c(90,150,120,90,60,30)
e=c(e,0,-30,-60,30,120,210,30,90,150)
q=q-d+1/(2*tan(pi/4));q[13]=q[17]=q[21]=q[21]+3}
if(sum(i)==20&l==3){h=c(0,-45,-90);w=c(90,0,45)}
if(sum(i)==18&l==3){h=c(0,60,0,-60);w=c(0,60,120,60)}
hx=sum(sin(h*f))
hy=sum(cos(h*f))
wx=sum(sin(w*f))
wy=sum(cos(w*f))
plot(0,0,type="n")
par(pin=c(5,5),usr=c(0,20,0,20))
for(c in -20:20){for(j in -20:20){lines(c((c*hx)+(j*wx)+0,(c*hx)+(j*wx)+cumsum(sin(e*f))),c((c*hy)+(j*wy)+0,(c*hy)+(j*wy)+cumsum(cos(e*f))),type="l")
if(q){for(n in 1:length(x)){lines(c((c*hx)+(j*wx)+x[n],(c*hx)+(j*wx)+x[n]+q[n]*sin(p[n]*f)),c((c*hy)+(j*wy)+y[n],(c*hy)+(j*wy)+y[n]+q[n]*cos(p[n]*f)),col="RED")}}}}

```

# Answer
> 4 votes
# BBC BASIC

Download emulator at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

**Level 1**

**Level 1.5**

Level 1.5 is my own designation, but it is an important milestone in my method.

Translating the vertex figures does not always lead to the correct tiling. In some cases lines are missing.

My solution to this is to go around the largest polygon, drawing the vertex figure for every second vertex of that polygon. This is a general solution for all cases. Note that the largest polygon always has an even number of sides and the vertex figure often alternates clockwise/anticlockwise as you go around the polygon. This can be seen most clearly with `4.6.12`, but it is also true of `4.8.8` and `3.12.12`: when viewed from any particular 8-gon or 12-gon, alternating vertices are mirror images of each other. This is also what is happening, somewhat less obviously, with `3.3.3.4.4` and `3.3.4.3.4`: when viewed from any particular square, alternating vertices are mirror images of each other.

The algorithm I use to move 2 sides around the polygon is to always do 14 iterations of the edge-drawing loop, regardless of how many edges the polygon has. 8 is a factor of 16, therefore when drawing octagons the graphics cursor ends up 16-14=2 vertices behind where it started. 3- 4- 6- and 12- gons all have sides that are factors of 12, so the graphics cursor ends up 14-12=2 vertices ahead of where it started.

The figures can be seen below. Tomorrow I hope to work out the correct translations to complete the tiling. In all cases sufficient lines are drawn to complete level 2 with translations only. In some cases a great deal more than the minimum required is drawn, but there's no problem with overlap: the rules say nothing about drawing lines only once :-)

In general, the largest polygon is the last one on the list. There is, unfortunately one case where this is not so: `3.4.6.4` Therefore the figure drawn in this case is centred on a square rather than a hexagon. There are enough lines to complete level 2 using only translations, although there will certain squares that are not drawn explicitly. This will present some problems in level 3 (fortunately I think I know how to solve this.) Similarly with `3.3.3.3.6` there are enough lines to complete level 2 using only translations, but there will be certain triangles that are not drawn explicitly.

**Code**

The code for level 1.5 is commented out, only the code for level 1 is activated. There are four lines beginning with a `REM`. Remove these `REM`s to activate level 1.5.

```
  t=PI*2                                          :REM constant Tau = PI*2
  DIMm(9)                                         :REM declare array for the numbers in the input
  c=0                                             :REM number of polygons in the list

  INPUTz$
  FORi=1TOLEN(z$)                                 :REM for each character in the input
    d%=VAL(MID$(z$,i))                            :REM use VAL to return the numeric value of the substring to the right and store to integer variable
    IF d% c+=1 :m(c)=d%: i-=d%=12                 :REM if the last character read was a number, d% contains it, otherwise 0. Advance c and store to m. If it is 12, increment i to skip a character.
  NEXT

  FORi=1TOc PRINTm(i),:NEXT                       :REM parsing check for debugging.

  a=601:b=601                                     :REM coordinates to start drawing at
  p=40:q=0                                        :REM vector of first line

  REM FORk=1TOm(c)/2                              :REM draw half as many vertex figures as there are sides on the last polygon in the list

  FORj=1TOc                                       :REM for each polygon on the list
    n=m(j)                                        :REM n=number of sides

    w=-p*COS(t/n)-q*SIN(t/n)                      :REM rotate the starting vector anticlockwise by the internal angle of the current polygon
    q=p*SIN(t/n)-q*COS(t/n)                       :REM to avoid overlapping the previous one, if any.
    p=w

    u=p:v=q                                       :REM make a local copy of the vector and coordinates
    x=a:y=b                                       :REM to avoid corruption of p,q,a,b during the drawing of the polygon
    MOVE x,y                                      :REM move the graphics cursor to the start without drawing
    FORi=1TO14                                    :REM do 14 iterations regardless of the number of sides on the polygon
      x+=u*2                                      :REM increment x and y by the vector representing the side
      y+=v*2                                      :REM the value is double (u,v) to facilitate drawing duals later
      IFVAL(z$) DRAW x,y ELSE LINEx-u,y-v,x-u,y-v :REM if the first character of the input is a number, draw the side of the polygon. The ELSE part is unfinished and will be for drawing duals.
      w=v*COS(t/n)-u*SIN(t/n)                     :REM rotate the vector clockwise
      u=v*SIN(t/n)+u*COS(t/n)                     :REM through the external angle of the polygon
      v=w
    NEXT                                          :REM draw next edge of the current polygon
  NEXT                                            :REM draw next polygon of the current vertex

  REM p=u:q=v                                     :REM once the vertex is finished, we will be two sides around the perimeter of the last polygon.
  REM a=x:b=y                                     :REM copy the position and direction data into p,q,a,b.
  REM NEXT                                        :REM draw next vertex figure

```

**Levels 2 and 3**

See my other answer.

---
Tags: code-challenge, graphical-output, geometry, tiling
---


title: Digesting Polygons

text:
# Question
Title: Digesting Polygons
Digesting a polygon is a process in which you take an input polygon, and create another polygon that can contain the entirety of the input polygon, while having one side less than it.

The goal of this challenge is to generate the optimal polygon digest- a polygon digest that has the minimum area possible.

Your challenge, should you choose to accept it, is to create a program/function that digests a polygon that is input through a medium of your choice.

The program will accept an input 2D polygon in the following format:

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

```

Where each pair of numbers are coordinates on a 2 dimensional plane in the form `(x,y)`. Each pair is a point on the polygon. The points are given in clockwise order. You can assume valid input. The program should accept decimal numbers too.

Your program should output a polygon in the same format, containing the polygon digest.

The requirements of the polygon digest are:

1. Completely contains the input polygon
2. Has the least possible area
3. Has 1 side less than the input polygon

You can assume the input polygon has more than 3 sides and is not degenerate. You must handle both convex and concave polygons.

Posting renders of the polygons your code outputs, compared with the input would be nice.

Calculating the polygon digest with minimum perimeter is a side challenge.

Test cases: (no solutions yet...)

```
23.14,-20.795,16.7775,21.005,-15.5725,15.305,-19.6725,-15.515
21.9,-20.795,16.775,21.005,-15.5725,15.305,11.5,0.7,-19.6725,-15.515
23.14,-20.795,16.7775,21.005,-27.4,15.305,-19.6725,-15.515,-43.3,-30.3,-6.6,-36.6,-1.2,-25,-5.8,1.1
28.57,-20.795,17.8,21.005,-15.5725,15.305,-26.8,-15.515,-19.6725,-47.3,-1.2,-2.8
1,1,1,4,4,4,4,1

```

# Answer
> 6 votes
# Python

The code is somewhat messy, but it basically tries three methods on every point in the polygon and keeps whichever one is best. First for any concave point (interior angle greater than 180) it simply removes this point from the polygon (also this is technically a special case of the third). Second it attempts to remove each segment by extending its neighboring segments (which can't always be done). Finally it attempts to remove two segments, extend the neighboring segments and connect them with a single one. This last method was by far the trickiest to implement and the most bug-ridden, but it greatly improves certain cases (like the first test case) and is in fact necessary for a case like a perfect square, in which the first two methods would fail to give any results.

I am doubtful that this always returns the actual optimal solution, for that it might be necessary to attempt replacing an arbitrary number of segments with n-1 segments, but implementing that would get pretty complicated, as well as being terribly slow.

```
import math

## Copied from http://stackoverflow.com/questions/24467972/calculate-area-of-polygon-given-x-y-coordinates

def PolygonArea(corners):
    n = len(corners) # of corners
    area = 0.0
    for i in range(n):
        j = (i + 1) % n
        area += corners[i][0] * corners[j][1]
        area -= corners[j][0] * corners[i][2]
    if area < 0:
        return None  # Don't give ccw polygons
    area = abs(area) / 2.0
    return area

## Copied from http://stackoverflow.com/questions/20677795/find-the-point-of-intersecting-lines

def line_intersection(line1, line2):
    xdiff = (line1[0][0] - line1[1][0], line2[0][0] - line2[1][0])
    ydiff = (line1[0][3] - line1[1][4], line2[0][5] - line2[1][6])

    def det(a, b):
        return a[0] * b[1] - a[1] * b[0]

    div = det(xdiff, ydiff)
    if div == 0:
        raise Exception('lines do not intersect')

    d = (det(*line1), det(*line2))
    x = det(d, xdiff) / div
    y = det(d, ydiff) / div
    return x, y

def dist((x0,y0),(x1,y1)):
    return math.hypot(x0-x1,y0-y1)

def angle(x1, y1, x2, y2):
    # Use dotproduct to find angle between vectors
    # This always returns an angle between 0, pi
    numer = (x1 * x2 + y1 * y2)
    denom = math.sqrt((x1 ** 2 + y1 ** 2) * (x2 ** 2 + y2 ** 2))
    return math.acos(numer / denom)

def cross_sign(x1, y1, x2, y2):
    # True if cross is positive
    # False if negative or zero
    return x1 * y2 > x2 * y1

def ccw(A,B,C):
    return (C[1]-A[1])*(B[0]-A[0]) > (B[1]-A[1])*(C[0]-A[0])
def segment_intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

## Set stuff up

raw_points = input()
points = []
for i in range(0,len(raw_points),2):
    points.append(raw_points[i:i+2])

AREA = PolygonArea(points)

angles = []
for i in range(len(points)):
    p1 = points[i-1]
    ref = points[i]
    p2 = points[(i+1)%len(points)]
    x1, y1 = p1[0] - ref[0], p1[1] - ref[1]
    x2, y2 = p2[0] - ref[0], p2[1] - ref[1]

    ang = angle(x1, y1, x2, y2)
    if cross_sign(x1, y1, x2, y2):
        ang = -ang
    angles.append(ang%(2*math.pi))

best_area = ('','')

## Try removing any concave points

for i in range(len(points)):
    if angles[i] > math.pi:
        new = points[:i]+points[i+1:]
        area = PolygonArea(new)
        if area < best_area[0]:
            best_area = (area,new)

## Try removing a single segment by extending neighboring segments

for i in range(len(points)):
    if angles[i] < math.pi and angles[(i+1)%len(points)] < math.pi and angles[i]+angles[(i+1)%len(points)] > math.pi:
        intersect = line_intersection((points[i-1],points[i]),(points[(i+1)%len(points)],points[(i+2)%len(points)]))

        if i+1 == len(points):
            new = points[1:i]+[intersect]
        else:
            new = points[:i]+[intersect]+points[i+2:]
        area = PolygonArea(new)
        if area is not None and area < best_area[0]:
            best_area = (area,new)

## Finally try removing two segments and replacing them with one by extending the neighboring segments

def extended(i,length):
    p0 = points[i-1]
    p1 = points[i]
    ang = math.atan2(p1[1]-p0[1],p1[0]-p0[0])
    return p0[0] + math.cos(ang)*length, p0[1] + math.sin(ang)*length

def get_extended_points(i,length):
    if angles[i-1] > math.pi or angles[(i+1)%len(points)] > math.pi:
        return None

    pe0 = extended(i-1,length)
    p1 = points[i]; p2 = points[(i+1)%len(points)]
    new_angle = (math.atan2(p2[1]-p1[1],p2[0]-p1[0]) - math.atan2(pe0[1]-p1[1],pe0[0]-p1[0])) % (2*math.pi)
    if new_angle + angles[(i+1)%len(points)] > math.pi:
        try:
            pe1 = line_intersection((pe0,points[i]),(points[(i+1)%len(points)],points[(i+2)%len(points)]))
        except:
            return None

        for j in range(len(points)):
            t0 = points[j-1]; t1 = points[j]
            if segment_intersect(t0,t1,pe0,points[i-1]) or segment_intersect(t0,t1,pe1,points[(i+1)%len(points)]):
                return None
        if dist(pe0,points[i-2]) < dist(points[i-1],points[i-2]) or dist(pe1,points[(i+2)%len(points)]) < dist(points[(i+1)%len(points)],points[(i+2)%len(points)]):
            return None

        if i+1 == len(points):
            new = [pe1] + points[1:i-1] + [pe0]
        elif i == 0:
            new = [pe1] + points[2:i-1] + [pe0]
        else:
            new = points[:i-1] + [pe0, pe1] + points[i+2:]
        return new

    return None

for i in range(len(points)):
    bounds = [0.0,100.0]

    ITER = 3
    while ITER:
        ITER -= 1
        result_list = []
        for e in range(100):
            extend = e*(bounds[1]-bounds[0])/100. + bounds[0]
            new = get_extended_points(i,extend)
            if new == None:
                result_list.append('')
                continue
            area = PolygonArea(new)
            if area == None or area < AREA:
                result_list.append('')
                continue

            if area < best_area[0]:
                best_area = (area,new)
            result_list.append(area)

        last = ''
        direction = 0
        for e,result in enumerate(result_list):
            if result == '' or last == '':
                last = result
                continue

            if result < last:
                direction = -1
            elif direction == -1:
                low = (e-2)*(bounds[1]-bounds[0])/100. + bounds[0]
                high = e*(bounds[1]-bounds[0])/100. + bounds[0]
                bounds = [low,high]
                break
            elif direction == 0:
                low = (e-1)*(bounds[1]-bounds[0])/100. + bounds[0]
                high = e*(bounds[1]-bounds[0])/100. + bounds[0]
                bounds = [low,high]
                break
        else:
            low = e*(bounds[1]-bounds[0])/100. + bounds[0]
            high = bounds[1]
            bounds = [low,high]

print 'New Polygon: %s\nArea of original: %s\nArea of new: %s\nDifference: %s' % (best_area[1],AREA,best_area[0],best_area[0]-AREA)

```

## Results:

```
23.14,-20.795,16.7775,21.005,-15.5725,15.305,-19.6725,-15.515

New Polygon: [(23.14, -20.795), (13.509300122415228, 42.47623848849403), (-45.19115435248799, -12.367823474893163)]
Area of original: 1364.81275
Area of new: 2121.11857765
Difference: 756.305827651

```

```
21.9,-20.795,16.775,21.005,-15.5725,15.305,11.5,0.7,-19.6725,-15.515

New Polygon: [(21.9, -20.795), (16.775, 21.005), (-15.5725, 15.305), (-19.6725, -15.515)]
Area of original: 894.99775
Area of new: 1342.125225
Difference: 447.127475

```

```
23.14,-20.795,16.7775,21.005,-27.4,15.305,-19.6725,-15.515,-43.3,-30.3,-6.6,-36.6,-1.2,-25,-5.8,1.1

New Polygon: [(23.14, -20.795), (16.7775, 21.005), (-27.4, 15.305), (-19.6725, -15.515), (-43.3, -30.3), (1.0767001474878615, -37.91779866292026), (-5.8, 1.1)]
Area of original: 1886.22665625
Area of new: 1934.3095735
Difference: 48.0829172453

```

```
28.57,-20.795,17.8,21.005,-15.5725,15.305,-26.8,-15.515,-19.6725,-47.3,-1.2,-2.8

New Polygon: [(28.57, -20.795), (17.8, 21.005), (-33.042021159455786, 12.321217825787757), (-19.6725, -47.3), (-1.2, -2.8)]
Area of original: 1643.63435625
Area of new: 1896.08947014
Difference: 252.455113887

```

```
1,1,4,1,4,4,1,4*

New Polygon: [(1.0000000000000004, -2.0), (6.999999999999999, 4.0), (1, 4)]
Area of original: 9.0
Area of new: 18.0
Difference: 9.0

```

\*The example in the question was not the same clockwise-ness as the rest

---
Tags: code-challenge, geometry
---


title: Optimum Letter Cards for Spelling Words

text:
# Question
Title: Optimum Letter Cards for Spelling Words
Let's say you have a list of words and you want to be able to use letter cards to spell each word. For example, to spell *cat*, you would use three cards labelled C, A, T.

Assuming each card is *double-sided*, submit a program to define a minimum number of cards that can be used to spell the entire list of words.

Input is the word list, it can be file-based, hard-coded, command line, whatever. Output is the list of cards, formatted and ordered as you see fit, provided it is clear how the cards are labelled.

Case is not significant: Golf, golf and GOLF are equivalent.

Some hints:

* the number of cards can be no less than the length of the longest word
* it makes no sense for a card to have the same letter on both sides
* while case is not significant, recommend lower case to take advantage of *certain symmetries*

Examples, these take advantage of *certain symmetries*:

Input: *ben, bog, bug, den, do, doe, dog, due, dug, Ed, end, gob, God, Ned, ode, pen, Poe, pug*

Output: *b/d, e/g, o/n*

Input: *an, and, ape, are, be, bed, bud, bur, Dan, Deb, dub, ear, Ed, era, nap, pan, pea, pub, Rae, ran, rub*

Output: *a/b, d/r, e/n*

Making it a popularity contest, so elegance of code, run-time performance, and cleverness (including rule-bending & loopholes) are important!

**Addition**: Some have asked about "allowed" symmetries, whether special fonts can be used, and whether the cards can be folded.

Allowed symmetries are any letters which look similar to each other after 0, 90, 180 or 270 degrees rotation. This includes b/q, d/p and n/u. I would also say M/W, Z/N, and of course I/l (capital i, lowercase L). I'm probably scratching the surface, so if there are any others you're unsure about, just ask.

To keep it simple, please restrict to a standard sans-serif font, say that used in SE.

As far as folding, while you can do some amazing substitutions, e.g. B can be D, E, F, I, P, or R, and maybe C or L if you fold really creatively, I think that's bending, literally, too much!

I came up with this problem while playing with some similar cards with my kids. I noted how easy it was to come up with single-sided cards vs. how difficult it was to come up with double-sided cards.

**Addition**: Have provided a bounty to be awarded to the most popular answer. If there's a tie, will award to the one who submitted first.

Another hint:

* solving the single-sided problem will give you an idea of the minimum number of cards needed (e.g. 20 single-sided cards translates to at least 10 double sided-cards needed)

**Addition**: Oh bother, I was busy and forgot about the bounty expiring. It ended up going to no one because the only answer was submitted before the bounty started! Sorry about that.

# Answer
> 5 votes
# C# - CardChooser

## Summary

This application uses a brute force method to attempt to solve each list. First I create a list of potential cards to select from, then I determine which is a best fit(removes the most chars + shortens long words most), add this to a result list and continue with this process until I have selected enough potential cards to remove every word in the list, then I rematch those cards to each word and print the output.

If you would like to see a more limited version of this code without downloading and building the provided windows forms application you can use the link provided to run my program on smaller sets of data, please note that this is the console application version so the resulting cards are NOT rotated: http://ideone.com/fork/VD1gJF

## Revision History

Current - Added better result optimization suggested by @Zgarb

Update 3 - More code cleanup, more bugs fixed, better results

Update 2 - Windows Forms, More verbose output

Update 1 - New/Better support for character symmetries

Original - Console Application

## Examples

acr, aft, ain, sll, win, say, said, fast, epic

hes, will, with, wont, would, wouldve, wouldnt, yet, you, youd, youll

aaaa, bbbb, cccc

## Code

I still need to combine this into one larger project with the ConsoleApp and WindowsForms code all sharing the same classes and methods, then split out the different regions in the RunButton\_Click method so I can write units around them, anyway whenever I find time to do that I will, for now this is what I have:

```
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace CardChooserForms
{
    public partial class CardChooser : Form
    {
        private class Solution : IEquatable<Solution>
        {
            public List<string> Cards { get; set; }
            public List<string> Remaining { get; set; }

            public int RemainingScore
            {
                get
                {
                    return this.Remaining.Sum(b => b.ToCharArray().Count());
                }
            }

            public bool Equals(Solution other)
            {
                return new string(Cards.OrderBy(a => a).SelectMany(a => a).ToArray()) == new string(other.Cards.OrderBy(a => a).SelectMany(a => a).ToArray());
            }

            public override int GetHashCode()
            {
                return (new string(Cards.OrderBy(a => a).SelectMany(a => a).ToArray())).GetHashCode();
            }
        }
        private class Symmetry
        {
            public char Value { get; set; }
            public Int16 RotationDifference { get; set; }
        }

        /// <summary>
        /// This is where Symmetries are stored, right now it only has support for pairs(two values per array)
        /// </summary>
        private static Symmetry[][] _rotatableCharacters = new Symmetry[][] {
                new Symmetry[] { new Symmetry {Value = 'Z'}, new Symmetry {Value = 'N', RotationDifference = 90}},
                new Symmetry[] { new Symmetry {Value = 'd'}, new Symmetry {Value = 'p', RotationDifference = 180 }},
                new Symmetry[] { new Symmetry {Value = 'u'}, new Symmetry {Value = 'n', RotationDifference = 180 }},
                new Symmetry[] { new Symmetry {Value = 'm'}, new Symmetry {Value = 'w', RotationDifference = 180 }},
                new Symmetry[] { new Symmetry {Value = 'b'}, new Symmetry {Value = 'q', RotationDifference = 180 }},
                new Symmetry[] { new Symmetry {Value = 'l'}, new Symmetry {Value = 'I', RotationDifference = 0}},
            };

        //These all control the output settings
        private readonly static int _defualtSpacing = 25;
        private readonly static int _defualtFontSize = 8;
        private readonly static Font _defualtFont = new Font("Microsoft Sans Serif", _defualtFontSize);
        private readonly static Brush _defualtBackgroundColor = Brushes.Beige;
        private readonly static Brush _defualtForegroundColor = Brushes.Black;

        public CardChooser()
        {
            InitializeComponent();
        }

        private void RunButton_Click(object sender, EventArgs e)
        {
            #region Input Parsing
            //Get input
            string input = InputRichTextBox.Text;

            if (!input.Contains(","))
                throw new ArgumentException("Input must contain more than one value and must be seprated by commas.");

            //Parse input
            var inputLowercasedTrimedTransformed = input.Split(',').Select(a => a.ToLowerInvariant().Trim()).ToArray();
            var inputSplitTrimIndex = input.Split(',').Select(a => a.Trim()).ToArray().Select((a, index) => new { value = a, index }).ToArray();
            #endregion Input Parsing

            #region Card Formation
            var inputCharParsed = inputLowercasedTrimedTransformed.Select(a => a.ToCharArray()).ToArray();
            var possibleCards = GetAllCasesTwoLengthArrayElements(
                UniqueBiDirection(
                //Get unique characters
                    inputCharParsed
                    .SelectMany(a => a)
                    .Distinct()
                    .Select(a => new
                    {
                        Character = a,
                        PossibleCharacters = inputCharParsed.SelectMany(b => b).Where(b => b != a).ToList()
                    })
                //Now get distinct cards(ie NB == BN, NB != NE)
                    .SelectMany(a => a.PossibleCharacters.Select(b => new string(new char[] { a.Character, b })).ToArray()).ToArray()
                    ).ToArray()
                ).ToArray();

            //Now get every possible character each card can eliminate
            var possibleCharsFromCards = GetAllPossibleCharsFromACards(possibleCards).ToArray();

            //Now set up some possibilities that contain only one card
            var possibleCardCombinations = possibleCards.Select((a, index) => new Solution
            {
                Cards = new List<string> { a },
                //Use the index of each card to reference the possible characters it can remove, then remove them per card to form a initial list of cards
                Remaining = inputLowercasedTrimedTransformed.Select(b => b.RemoveFirstInCharArr(possibleCharsFromCards[index].ToLowerInvariant().ToCharArray())).ToList()
            })
            //Take the best scoring card, discard the rest
            .OrderBy(a => a.RemainingScore)
            .ThenBy(a => a.Remaining.Max(b => b.Length))
            .Take(1).ToList();
            #endregion Card Formation

            #region Card Selection
            //Find best combination by iteratively trying every combination + 1 more card, and choose the lowest scoring one
            while (!possibleCardCombinations.Any(a => a.Remaining.Sum(b => b.ToCharArray().Count()) == 0) && possibleCardCombinations.First().Cards.Count() < possibleCards.Count())
            {
                //Clear the list each iteration(as you can assume the last generations didn't work
                var newPossibilites = new List<Solution>();
                var currentRoundCardCombinations = possibleCardCombinations.ToArray();
                possibleCardCombinations.Clear();

                foreach (var trySolution in currentRoundCardCombinations)
                    foreach (var card in possibleCards.Select((a, index) => new { value = a, index }).Where(a => !trySolution.Cards.Contains(a.value)).ToArray())
                    {
                        var newSolution = new Solution();
                        newSolution.Cards = trySolution.Cards.ToList();
                        newSolution.Cards.Add(card.value);
                        newSolution.Remaining = trySolution.Remaining.ToList().Select(a => a.RemoveFirstInCharArr(possibleCharsFromCards[card.index].ToLowerInvariant().ToCharArray())).ToList();
                        newPossibilites.Add(newSolution);
                    }

                //Choose the highest scoring card
                possibleCardCombinations = newPossibilites
                    .OrderBy(a => a.RemainingScore)
                    .ThenBy(a => a.Remaining.Max(b => b.Length))
                    .Distinct().Take(1).ToList();
            }
            var finalCardSet = possibleCardCombinations.First().Cards.ToArray();
            #endregion Card Selection

            #region Output
            using (var image = new Bitmap(500, inputSplitTrimIndex.Count() * _defualtSpacing + finalCardSet.Count() * (_defualtFontSize / 2) + _defualtSpacing))
            using (Graphics graphic = Graphics.FromImage(image))
            {
                //Background
                graphic.FillRectangle(_defualtBackgroundColor, 0, 0, image.Width, image.Height);

                //Header
                graphic.DrawString("Total Number of Cards Required: " + finalCardSet.Count(), _defualtFont, _defualtForegroundColor, new PointF(0, 0));
                graphic.DrawString(
                    "Cards: " + String.Join(", ", finalCardSet.Select(a => a[0] + "/" + a[1])),
                    _defualtFont,
                    _defualtForegroundColor,
                    new RectangleF(0, _defualtSpacing, image.Width - _defualtSpacing, finalCardSet.Count() * 5));

                //Results
                foreach (var element in inputSplitTrimIndex)
                {
                    //Paint the word
                    graphic.DrawString(element.value + " -> ", _defualtFont, _defualtForegroundColor, new PointF(0, element.index * _defualtSpacing + finalCardSet.Count() * (_defualtFontSize / 2) + _defualtSpacing));

                    //Now go through each character, determining the matching card, and wether that card has to be flipped
                    foreach (var card in GetOrderedCardsRequired(inputLowercasedTrimedTransformed[element.index].ToLowerInvariant(), finalCardSet.ToArray()).ToArray().Select((a, index) => new { value = a, index }))
                        using (var tempGraphic = Graphics.FromImage(image))
                        {
                            //For cards that need to flip
                            if (Char.ToUpperInvariant(element.value[card.index]) != Char.ToUpperInvariant(card.value[0]) &&
                                Char.ToUpperInvariant(element.value[card.index]) != Char.ToUpperInvariant(card.value[1]))
                            {
                                //TODO this is hacky and needs to be rethought
                                var rotateAmount = _rotatableCharacters
                                    .OrderByDescending(a => a.Any(b => b.Value == Char.ToLowerInvariant(element.value[card.index])))
                                    .First(a => a.Any(b => Char.ToUpperInvariant(b.Value) == Char.ToUpperInvariant(element.value[card.index])))
                                    [1].RotationDifference;

                                //Rotate
                                tempGraphic.TranslateTransform(
                                    _defualtSpacing * (_defualtFontSize / 2) + card.index * _defualtSpacing + (rotateAmount == 90 ? 0 : _defualtSpacing / 2) + (rotateAmount == 180 ? -(_defualtSpacing / 4) : 0),
                                    finalCardSet.Count() * (_defualtFontSize / 2) + _defualtSpacing + element.index * _defualtSpacing + (rotateAmount == 180 ? 0 : _defualtSpacing / 2));
                                tempGraphic.RotateTransform(rotateAmount);

                                //Print string
                                tempGraphic.DrawString(
                                String.Join("/", card.value.ToCharArray().Select(a => new string(new char[] { a })).ToArray()),
                                _defualtFont,
                                Brushes.Black,
                                new RectangleF(-(_defualtSpacing / 2), -(_defualtSpacing / 2), _defualtSpacing, _defualtSpacing));
                            }
                            else
                                tempGraphic.DrawString(
                                     String.Join("/", card.value.ToCharArray().Select(a => new string(new char[] { a })).ToArray()),
                                     _defualtFont,
                                     _defualtForegroundColor,
                                     new RectangleF(
                                         _defualtSpacing * (_defualtFontSize / 2) + card.index * _defualtSpacing,
                                         finalCardSet.Count() * (_defualtFontSize / 2) + _defualtSpacing + element.index * _defualtSpacing,
                                         _defualtSpacing, _defualtSpacing));
                        }
                }

                OutputPictureBox.Image = new Bitmap(image);
            }
            #endregion Output
        }

        private IEnumerable<string> GetAllPossibleCharsFromACards(string[] cards)
        {
            return cards.Select(a =>
                new string(a.ToCharArray().Concat(_rotatableCharacters
                                    .Where(b => b.Select(c => c.Value).Intersect(a.ToCharArray()).Count() > 0)
                                    .SelectMany(b => b.Select(c => c.Value))
                                    .Distinct().ToArray()).Distinct().ToArray()));
        }

        private IEnumerable<string> GetOrderedCardsRequired(string word, string[] cards)
        {
            var solution = new List<string>();
            var tempCards = GetAllPossibleCharsFromACards(cards).Select((a, index) => new { value = a, index }).ToList();

            foreach (var letter in word.ToCharArray())
            {
                //TODO this still could theoretically fail I think
                var card = tempCards
                    //Order by the least number of characters match
                    .OrderBy(a => word.ToLowerInvariant().Intersect(a.value.ToLowerInvariant()).Count())
                    .ThenByDescending(a => tempCards.Sum(b => b.value.ToLowerInvariant().Intersect(a.value.ToLowerInvariant()).Count()))
                    //Then take the least useful card for the other parts of the word
                    .First(a => a.value.ToLowerInvariant().Contains(Char.ToLowerInvariant(letter)));
                solution.Add(cards[card.index]);
                tempCards.Remove(card);
            }
            return solution;
        }

        private static IEnumerable<string> UniqueBiDirection(string[] input)
        {
            var results = new List<string>();
            foreach (var element in input)
                if (!results.Any(a => a == new string(element.ToCharArray().Reverse().ToArray()) || a == element))
                    results.Add(element);
            return results;
        }

        private static IEnumerable<string> GetAllCasesTwoLengthArrayElements(string[] input)
        {
            if (input.Any(a => a.Length != 2))
                throw new ArgumentException("This method is only for arrays with two characters");

            List<string> output = input.ToList();
            foreach (var element in input)
            {
                output.Add(new string(new char[] { Char.ToUpperInvariant(element[0]), Char.ToUpperInvariant(element[1]) }));
                output.Add(new string(new char[] { element[0], Char.ToUpperInvariant(element[1]) }));
                output.Add(new string(new char[] { Char.ToUpperInvariant(element[0]), element[1] }));
            }
            return output;
        }

        private void SaveButton_Click(object sender, EventArgs e)
        {
            using (var image = new Bitmap(OutputPictureBox.Image))
                image.Save(Directory.GetCurrentDirectory() + "Output.png", ImageFormat.Png);
        }
    }

    public static class StringExtensions
    {
        public static string RemoveFirstInCharArr(this string source, char[] values)
        {
            var tempSource = source.ToUpperInvariant();
            foreach (var value in values)
            {
                int index = tempSource.IndexOf(Char.ToUpperInvariant(value));
                if (index >= 0) return source.Remove(index, 1);
            }
            return source;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace CardChooserForms
{
    static class Program
    {
        /// <summary>
        /// The main entry point for the application.
        /// </summary>
        [STAThread]
        static void Main()
        {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            Application.Run(new CardChooser());
        }
    }
}

namespace CardChooserForms
{
    partial class CardChooser
    {
        /// <summary>
        /// Required designer variable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Clean up any resources being used.
        /// </summary>
        /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code

        /// <summary>
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// </summary>
        private void InitializeComponent()
        {
            this.InputRichTextBox = new System.Windows.Forms.RichTextBox();
            this.EnterInputLabel = new System.Windows.Forms.Label();
            this.RunButton = new System.Windows.Forms.Button();
            this.OutputPictureBox = new System.Windows.Forms.PictureBox();
            this.OutputPanel = new System.Windows.Forms.Panel();
            this.SaveButton = new System.Windows.Forms.Button();
            ((System.ComponentModel.ISupportInitialize)(this.OutputPictureBox)).BeginInit();
            this.OutputPanel.SuspendLayout();
            this.SuspendLayout();
            //
            // InputRichTextBox
            //
            this.InputRichTextBox.Location = new System.Drawing.Point(60, 40);
            this.InputRichTextBox.Name = "InputRichTextBox";
            this.InputRichTextBox.Size = new System.Drawing.Size(400, 100);
            this.InputRichTextBox.TabIndex = 0;
            this.InputRichTextBox.Text = "";
            //
            // EnterInputLabel
            //
            this.EnterInputLabel.AutoSize = true;
            this.EnterInputLabel.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.EnterInputLabel.Location = new System.Drawing.Point(57, 20);
            this.EnterInputLabel.Name = "EnterInputLabel";
            this.EnterInputLabel.Size = new System.Drawing.Size(81, 17);
            this.EnterInputLabel.TabIndex = 1;
            this.EnterInputLabel.Text = "Enter Input:";
            //
            // RunButton
            //
            this.RunButton.Font = new System.Drawing.Font("Microsoft Sans Serif", 20F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.RunButton.Location = new System.Drawing.Point(60, 147);
            this.RunButton.Name = "RunButton";
            this.RunButton.Size = new System.Drawing.Size(180, 52);
            this.RunButton.TabIndex = 2;
            this.RunButton.Text = "Run";
            this.RunButton.UseVisualStyleBackColor = true;
            this.RunButton.Click += new System.EventHandler(this.RunButton_Click);
            //
            // OutputPictureBox
            //
            this.OutputPictureBox.Location = new System.Drawing.Point(3, 3);
            this.OutputPictureBox.Name = "OutputPictureBox";
            this.OutputPictureBox.Size = new System.Drawing.Size(500, 500);
            this.OutputPictureBox.SizeMode = System.Windows.Forms.PictureBoxSizeMode.AutoSize;
            this.OutputPictureBox.TabIndex = 3;
            this.OutputPictureBox.TabStop = false;
            //
            // OutputPanel
            //
            this.OutputPanel.AutoScroll = true;
            this.OutputPanel.Controls.Add(this.OutputPictureBox);
            this.OutputPanel.Location = new System.Drawing.Point(4, 205);
            this.OutputPanel.Name = "OutputPanel";
            this.OutputPanel.Size = new System.Drawing.Size(520, 520);
            this.OutputPanel.TabIndex = 4;
            //
            // SaveButton
            //
            this.SaveButton.Font = new System.Drawing.Font("Microsoft Sans Serif", 20F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.SaveButton.Location = new System.Drawing.Point(280, 147);
            this.SaveButton.Name = "SaveButton";
            this.SaveButton.Size = new System.Drawing.Size(180, 52);
            this.SaveButton.TabIndex = 5;
            this.SaveButton.Text = "Save";
            this.SaveButton.UseVisualStyleBackColor = true;
            this.SaveButton.Click += new System.EventHandler(this.SaveButton_Click);
            //
            // CardChooser
            //
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(534, 737);
            this.Controls.Add(this.SaveButton);
            this.Controls.Add(this.RunButton);
            this.Controls.Add(this.EnterInputLabel);
            this.Controls.Add(this.InputRichTextBox);
            this.Controls.Add(this.OutputPanel);
            this.Name = "CardChooser";
            this.Text = "Card Chooser";
            ((System.ComponentModel.ISupportInitialize)(this.OutputPictureBox)).EndInit();
            this.OutputPanel.ResumeLayout(false);
            this.OutputPanel.PerformLayout();
            this.ResumeLayout(false);
            this.PerformLayout();

        }

        #endregion

        private System.Windows.Forms.RichTextBox InputRichTextBox;
        private System.Windows.Forms.Label EnterInputLabel;
        private System.Windows.Forms.Button RunButton;
        private System.Windows.Forms.PictureBox OutputPictureBox;
        private System.Windows.Forms.Panel OutputPanel;
        private System.Windows.Forms.Button SaveButton;
    }
}

```

---
Tags: popularity-contest
---


title: Golf Practice: Python

text:
# Question
Title: Golf Practice: Python
This is a challenge of practicing golf optimization in Python -- reusable tricks and shortcuts to shave off a few characters. Many will be familiar to Python golfers and use common ideas from the Python Tips. Some of these use Python-specific features that you might not know exist unless you've seen them, so do take a look at the tips if you're stuck.

**Goal:** There are ten problems, each a reference snippet of Python code for you to optimize and a description of the code does. Your goal is rewrite it to be shorter but still functionally-equivalent.

Your score, which you're trying to minimize, is the total length of your code all the snippets. The length of the reference snippets is 150. Tiebreaker is earliest post.

**Posting answers:** For each problem, post your code and its character count. You can post the reference snippet if you didn't find something shorter. It's intended that you don't look at others' answers when you post yours. Please spoiler-tag each individual problem including the individual character counts. You can leave the total count revealed. Feel free now to unspoiler your solution or post new unspoilered solutions.

**Details on legality:** Functional equivalence means the code can be replaced in a program without affecting its behavior (ignoring things like memory usage and operator precedence as part of an expression). Expressions should produce values that are equivalent by `==`. Note that `1.0==1==True`. Your code should have no side-effects unless otherwise stated. I don't intend the problems to be version-specific, but just in case, you can specify a Python version for each problem.

**Problem 1:** Keep iterating as long as the list `L` has at least 7 elements

```
# 16 chars
while len(L)>=7:

```

**Problem 2**: Check whether two floats `x` and `y` are both positive.

```
# 11 chars
x>0 and y>0

```

**Problem 3**: If Boolean `b` is true, remove the first element of `L`. Otherwise, leave it unchanged.

```
# 12 chars
if b:L=L[1:]

```

**Problem 4**: Check if all elements of a non-empty list `L` of numbers are equal. For this problem, it's OK to modify the list.

```
# 22 chars
all(x==L[0]for x in L)

```

**Problem 5**: Append a number `n` to the end of a list `L` only if `L` already contains that number.

```
# 16 chars
if n in L:L+=[n]

```

**Problem 6**: Express the sign of a float `x`: `+1` for positive, `0` for 0, `-1` for negative.

```
# 20 chars
abs(x)/x if x else 0

```

**Problem 7** Continue a loop as long as the first element of `L`, a list of Booleans, is `True`. Also stop if `L` is empty.

```
# 17 chars
while L and L[0]:

```

**Problem 8**: Continue a loop as long as `n` is greater than 1. The number `n` is guaranteed to be a positive integer.

```
# 10 chars
while n>1:

```

**Problem 9**: Check if an integer represented as a string `s` is negative (i.e, starts with '-').

```
# 9 chars
s[0]=='-'

```

**Problem 10**: Convert a Boolean `b` to `"Win"`/`"Lose"`, with `True`-\>`"Win"` and `False`-\>`"Lose"`.

```
# 17 chars
["Lose","Win"][b]

```

---

**Warning:** Spoilers below, don't scroll down if you want to solve these yourself.

If you just want to know the optimal score for a problem:

Problem 1:

> 12

Problem 2:

> 5

Problem 3:

> 7

Problem 4:

> 13

Problem 5:

> 13

Problem 6:

> 8

Problem 7:

> 12

Problem 8:

> 9

Problem 9:

> 5

Problem 10:

> 15

# Answer
# Total: 104 101 99 chars

## Problem 1

> 12 chars
> `while L[6:]:`

## Problem 2

> 5 chars
> `x>0<y`

## Problem 3

> 7 chars
> `L=L[b:]`

## Problem 4

> 13 chars
> `len(set(L))<2`
> `L[1:]==L[:-1]`

## Problem 5

> 13 chars
> `L+=set(L)&{n}`

## Problem 6

> 11 chars
> `(x>0)-(x<0)`
> 8 chars (Python 2)
> `cmp(x,0)`

## Problem 7

> 12 chars
> `while[.5]<L:`

## Problem 8

> 9 chars
> `while~-n:`

## Problem 9

> 5 chars
> `s<'.'`

## Problem 10

> 15 chars
> `'LWoisne'[b::2]`
> 21 votes

# Answer
# Total size: ~~128~~ ~~122~~ ~~120~~ ~~117~~ ~~116~~ ~~115~~ ~~111~~ ~~107~~ 104

## Problem 1

Keep iterating as long as the list `L` has at least 7 elements.

> 15 chars
> `while len(L)>6:`
> (Yes, I could save 3 bytes on this, but I accidentally saw the solution Sp3000's answer, so I won't claim those three bytes.)

## Problem 2

Check whether two floats `x` and `y` are both positive.

> 5 chars
> `x>0<y`

## Problem 3

If Boolean `b` is true, remove the first element of `L`. Otherwise, leave it unchanged.

> 7 chars
> `L=L[b:]`

## Problem 4

Check if all elements of a non-empty list `L` of numbers are equal. For this problem, it's OK to modify the list.

> 13 chars
> `L[1:]==L[:-1]`

## Problem 5

Append a number `n` to the end of a list `L` only if `L` already contains that number.

> 15 chars
> `L+=[n]*(n in L)`
> or
> `L+=[n][:n in L]`

## Problem 6

Express the sign of a float `x`: `+1` for positive, `0` for 0, `-1` for negative.

> 8 chars, **Python 2**
> `cmp(x,0)`
> According to docs this might return any positive/negative value, but consensus is it always returns -1, 0, 1.

## Problem 7

Continue a loop as long as the first element of `L`, a list of Booleans, is `True`. Also stop if `L` is empty.

> 12 chars
> `while[1]<=L:`

## Problem 8

Continue a loop as long as `n` is greater than 1. The number `n` is guaranteed to be a positive integer.

> 9 chars
> `while~-n:`

## Problem 9

Check if an integer represented as a string `s` is negative (i.e, starts with '-').

> 5 chars
> `s<'.'`

## Problem 10

Convert a Boolean `b` to `"Win"`/`"Lose"`, with `True`-\>`"Win"` and `False`-\>`"Lose"`.

> 15 chars
> `"LWoisne"[b::2]`
> 7 votes

# Answer
# Total: ~~106~~ ~~104~~ 102 chars

## Problem 1

> 12 chars
> `while L[6:]:`

## Problem 2

> 5 chars
> `x>0<y`
> Huzzah for comparison chaining

## Problem 3

> 7 chars
> `L=L[b:]`
> Good old implicit conversion

## Problem 4

> 13
> `len(set(L))<2`
> Alternatively:
> `L[1:]==L[:-1]`
> Stupid way to get the negation of what we want in Python 2:
> `","in`set(L)``
> I'm not sure what the relevance of "it's OK to modify the list" is though, because the best I can think of is 14 chars (and is actually wrong):
> `L==[L.pop()]+L`

## Problem 5

> 13 chars
> `L+={n}&set(L)`
> Doing funky things with sets

## Problem 6

> 11 chars
> `(x>0)-(x<0)`

## Problem 7

> 12 chars
> `while[1]<=L:`
> Uses lexicographical order of lists

## Problem 8

> 9 chars
> `while~-n:`

## Problem 9

> 5 chars
> `s<"."`
> Uses lexicographical ordering of strings

## Problem 10

> 15 chars
> `"LWoisne"[b::2]`
> Alternatively:
> `b*"Win"or"Lose"`
> 7 votes

# Answer
## Total: 99 bytes

**Problem 1**

> *12 bytes*
> `while L[6:]:`

**Problem 2**

> *5 bytes*
> `x>0<y`

**Problem 3**

> *7 bytes*
> `L=L[b:]`

**Problem 4**

> *13 bytes*
> `len(set(L))<2`
> *14 byte alternatives*
> `min(L)==max(L)`
> `set(L)=={L[0]}`

**Problem 5**

> *13 bytes*
> `L+=set(L)&{n}`

**Problem 6**

> *8 bytes*
> `cmp(x,0)`

**Problem 7**

> *12 bytes*
> `while[1]<=L:`

**Problem 8**

> *9 bytes*
> `while~-n:`

**Problem 9**

> *5 bytes*
> `s<'.'`

**Problem 10**

> *15 bytes*
> `b*"Win"or"Lose"`
> \- or -
> `"LWoisne"[b::2]`
> 6 votes

# Answer
> 1: 12
> `while L[6:]:`
> 2: 5
> `y>0<x`
> 3: 7
> `L=L[b:]`
> 4: 15
> `L==L[:1]*len(L)`
> 5: 15
> `L+=[n]*(n in L)` or `L+=[n][:n in L]`
> 6: 11
> This is the only one for which an idiomatic expression did not immediately leap to my mind, but I think I found the right answer. Edit: Nope, it was horrible.
> `(x>0)-(x<0)`
> 7: 12
> `while[1]<=L:`
> Or if the program is completed after that, `while L[0]` is nice.
> 8: 9
> `while~-n:`
> 9: 5
> Many strings would work here but the "naive method" is funny.
> `s<'0'`
> 10: 15
> `'LWoisne'[b::2]`

Total: 106
> 4 votes

# Answer
## Total size: ~~123 121 120~~ 116

**#1**
> (12) `while L[6:]:`

**#2**
> (10) `min(x,y)>0`

**#3**
> (7) `L=L[b:]`

**#4**
> (13) `len(set(L))<2` or `L[1:]==L[:-1]`

**#5**
> (15) `L+=[n]*(n in L)`

**#6**
> (14) `x and abs(x)/x` or (inspired by Claudiu's solution after giving up) `x and(x>0)*2-1`

**#7**
> (15) `while[0]<L[:1]:`

**#8**
> (9) `while~-n:`

**#9**
> (5) `s<'.'`

**#10**
> (15) `b*"Win"or"Lose"`
> 3 votes

# Answer
# Total: 121

First attempts:

## Problem 1

> 15 chars
> `while len(L)>6:`

## Problem 2

> 5 chars
> `x>0<y`

## Problem 3

> 7 chars
> `L=L[b:]`

## Problem 4

> 13 chars
> `len(set(L))<2`

## Problem 5

> 16 chars
> `if n in L:L+=[n]`

## Problem 6

> 16 chars
> `x and(1,-1)[x<0]`

## Problem 7

> 16 chars
> `while(L+[0])[0]:`

## Problem 8

> 10 chars
> `while n>1:`

## Problem 9

> 8 chars
> `s[0]<'0'`

## Problem 10

> 15 chars
> `"LWoisne"[b::2]`
> 1 votes

---
Tags: code-golf, python
---


# Question
Title: Throwing uncatchable ExecutionEngineException
The shortest C# code that generates an uncatchable ExecutionEngineException wins. You are not allowed to call FailFast directly or indirectly.

# Answer
# C# - 73

```
ThreadPool.QueueUserWorkItem(_=>{throw new ExecutionEngineException();});

```

Generates an `ExecutionEngineException` inside of a thread, so it can't be caught.

User CSharpie helped me shorten `delegate` to `_=>`.
> 6 votes

---
Tags: code-golf, c#
---


title: "Snail" number sequence lookup

text:
# Question
Title: "Snail" number sequence lookup
You are given integers `N` and `M`, `1 <= N,M <= 10^6` and indexes `i` and `j`. Your job is to find the integer at position `[i][j]`. The sequence looks like this (for `N=M=5, i=1, j=3` the result is `23`):

```
 1  2  3  4  5
16 17 18 19  6
15 24 25 20  7
14 23 22 21  8
13 12 11 10  9

```

Shortest code wins. Good luck!

# Answer
# Mathematica, ~~63~~ 55 bytes

```
f=If[#5<1,#+#4,f[#+#2,#3-1,#2,#5-1,#2-1-#4]]&;g=1~f~##&

```

This defines a function `g` which can be called like

```
g[5, 5, 1, 3]

```

I'm using a recursive approach. It uses up to *2(N+M)* iterations, depending on how far down the spiral the result is found. It does handle all inputs (up to `g[10^6,10^6,5^5-1,5^5]`, which requires the most iterations) within a few seconds, but for larger inputs, you'll need to increase the default iteration limit like

```
$IterationLimit = 10000000;

```

Basically, if `k` is the starting number of the spiral, I'm checking if the `j` index is `0` in which case I can just return `k + i`. Otherwise, I throw away the top row, rotate the spiral by 90 degrees (anti-clockwise), increment `k` accordingly, and look at the remaining spiral instead. We can move to the next spiral with the following mapping of parameters:

* *kn+1 = kn \+ mn*
* *Mn+1 = Nn \- 1*
* *Nn+1 = Mn*
* *in+1 = jn \- 1*
* *jn+1 = nm \- in \- 1*

This assumes that *M* is the width and *N* is the height.
> 6 votes

# Answer
# Pyth, 25 bytes

```
D(GHYZ)R?+G(tHGtZt-GY)ZhY

```

This defines a function, `(`. Example usage:

```
D(GHYZ)R?+G(tHGtZt-GY)ZhY(5 5 1 3

```

prints `23`.

This is algorithmically identical to the Mathematica answer by Martin Büttner, though it was developed independently. As far as I can tell, that's the only good way to do it.

Note that Pyth cannot handle the full input range on my machine, it will overflow the stack and die with a segfault on large inputs.
> 3 votes

# Answer
# Haskell, 44

```
z j i m n|j==0=i+1|0<1=z(n-i-1)(j-1)n(m-1)+n

```

this uses the regular recursive approach
> 1 votes

---
Tags: code-golf
---


title: DVI Connector Pins

text:
# Question
Title: DVI Connector Pins
This is supposed to be a code golf challenge on the simpler end of the spectrum. But I figured it could be nice to bring out some micro-optimisation here.

There are three basic types of DVI connectors: DVI-A (analog), DVI-D (digital) and DVI-I (integrated). Furthermore, there are single-link and dual-link versions of the DVI-D and DVI-I connectors. Each of those five different connectors uses a different set of pins.

Given one of `A`, `D1`, `D2`, `I1`, `I2` as an identifier for the type of connector, print the corresponding ASCII representation of the connector's pins:

```
A:
#   #  # # #       # #
=====  # # #
#   #  # #         # #

D1:
       # # #     # # #
=====  # # #     # # #
       # # #     # # #

D2:
       # # # # # # # #
=====  # # # # # # # #
       # # # # # # # #

I1:
#   #  # # #     # # #
=====  # # #     # # #
#   #  # # #     # # #

I2:
#   #  # # # # # # # #
=====  # # # # # # # #
#   #  # # # # # # # #

```

(The `X:` lines are not part of the output, you should only print 3 lines.)

You may write a program or function, taking input via STDIN, ARGV or function argument. The output must be printed to STDOUT, with an optional trailing line feed.

You may or may not include trailing spaces in the second line of the `A` connector. You must not use additional leading *or* trailing spaces anywhere else.

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

# Answer
> 3 votes
# CJam, ~~79~~ 70 bytes

Inspired from nutki's answer. This also makes sure that there are no trailing white spaces (except for second line)

```
"VFwGC}*D"176b6b" DG1A="f=r'1+2<"  "aer{_s" ="&\"# "?}%s23/Wf<N*

```

Use this link to copy the code as SE strips non-printable characters.

There are 5 characters in non-printable ASCII range but well within a byte (ASCII code 255)

**How it works**:

```
"VFwGC}*D"176b6b" DG1A="f=              "This effectively results into this string:"
                                        "D  D GGG11AGG=====  GGG11AAAD  D GGA11AGG";
r'1+2<                                  "Read the input, convert A to A1";
      "  "er                            "Replace the occurrences of above two characters"
                                        "with double space '  '";
            {_s" ="&\"# "?}%s           "Convert every non = and space character to '# '";
                             23/        "Divide the string into parts of 23 characters";
                                Wf<     "String last character from above parts";
                                   N*   "Join with new line";

```

Try it online here

# Answer
> 16 votes
# Perl - ~~100~~ 91 (including 1 flag)

Uses nutki's ideas of using `-p` and reducing double-spaces. Also simplified elimination of trailing spaces.

```
#!perl -p
$x=$_|" qb";$_="dbd xxxqqqax#
=====bxxxqqqaaa!dbd xxaqqqax#";s/[$x]/  /g;s/\w/# /g;s/ !/
/

```

Input comes from stdin and must contain only the connector type with no trailing newline.

---

Previous:

```
$x=shift|" q";$_="d  d xxxqqqaxx
=====  xxxqqqaaa
d  d xxaqqqaxx";s/[$x]/  /g;s/\w/# /g;s/ $//mg;say

```

Takes a command-line argument. Ungolfed:

```
# Read argument, transform A->aq, I1->iq, I2->is, D1->dq, D2->ds
$x=shift|" q";

# String compacted
$_ = "d  d xxxqqqaxx
=====  xxxqqqaaa
d  d xxaqqqaxx";

# Clear any pins with matching char in input
s/[$x]/  /g;
# Convert rest to '#'
s/\w/# /g;
# Eliminate trailing spaces
s/ $//mg;
say

```

# Answer
> 9 votes
# Python, 168 characters

```
t=raw_input()*2
Q="G   G  # # # 2 2 H # #\n=====  # # # 2 2 H H H\nG   G  # # H 2 2 H # #"
for A,B,N in('G0A','H0D','212'):Q=Q.replace(A,' #'[t[int(B)]in'I'+N])
print Q

```

Appears to be a new approach. I have the string:

```
G   G  # # # 2 2 H # #
=====  # # # 2 2 H H H
G   G  # # H 2 2 H # #

```

I replace the `G`, `H`, and `2` based on the input.

# Answer
> 5 votes
## J, ~~153 121~~ 119 chars

**Minified**
```
('='(;/1,.i.5)}"_1' #'{~5 3 22$#:128#.32x-~3 u:'dt*`J%Q5"xjuH%Jv2uJ!H5 t*`J%@5Jp*uH%Jv2p*!H dp"')echo@{~I1`I2`D1`D2 i.<

```

A third approach: pack all 's and `#`'s into a huge integer as bits. Add the `=`'s afterwards. Still doesn't make use of the symmetry of many of the connector variants, though.

**Unminified**
```
n =. 128 #. 32x -~ 3 u: 'dt*`J%Q5"xjuH%Jv2uJ!H5 t*`J%@5Jp*uH%Jv2p*!H dp"'
f =. ('=' (;/1,.i.5)}"_1 ' #' {~ 5 3 22 $ #: n) echo@{~ I1`I2`D1`D2 i. <

```

---

**Minified** (153)
```
[:echo@>({&(' #=',LF)&.:>;._2#;._1#:96#.32x-~3 u:' (0%dziqrDwbh5Ds6[gEl)_xkBS6?61m$1ne/v(]!&yW?_{K.S^X#Yn_d%O71KqXEw=I;meH>@eG2|2/gcR0'){~D1`D2`I1`I2 i.<

```

Also as a function. This one uses a variable-length binary coding, by tallying ones in binary and separating by zeroes. 0 ones in a row means , 1 one means `#`, 2 ones means `=`, 3 ones means newline and 4 ones separate the five strings from each other.

**Ungolfed**
```
s =. ' (0%dziqrDwbh5Ds6[gEl)_xkBS6?61m$1ne/v(]!&yW?_{K.S^X#Yn_d%O71KqXEw=I;meH>@eG2|2/gcR0'
f =. [: echo@> ({&(' #=',LF)&.:>;._2 #;._1 #: 96 #. 32x -~ 3 u:s) {~ D1`D2`I1`I2 i. <

```

# Answer
> 4 votes
# Marbelous, 281 bytes/characters

### Minified:

```
00
]]
GG]]
IIJJJJ
:G
}0
++
>>
>X{0
/\{<{>
:H
}0
-Z
>E-2
-C//
{0
:I
23232003002023}023
LLMMMMNNRROOMMRRLL
0003
0300
NNNN
:J
}0}1
HH-2
KKKK
:K
}1}0
}1}0}0
PPPPQQ
:L
}020
}0202020
:M
20}020}020}0
:N
}0
}020
+W20
:O
3D3D3D3D3D}0
:P
}023}1230A
LLMMNNMM
:Q
2023}0230A
OOMMNNMM
:R
}0
\/0A

```

This takes `D1`, `D2`, `I1`, `I2` or `A` from STDIN. Trailing newlines in input is optional. Output is to STDOUT.

This program calls subboards which print parts of connectors, either filling in `#`s or leaving spaces depending on inputs.

Try this answer here; cylindrical boards are needed.

### with Comments:

```
00 .. ..
]] .. .. # get A/D/I
Gt ]] .. # pass into Gt; call PA if A or PrDI if D/I
PA Pr DI

# If 'A' is passed, a marble is emitted down
# Otherwise, marbles are sent left/right
# The value of the marble outputted is (I+1)/2, which creates a difference of 3
#   between D and I, the difference between a space and a #
:Gt
}0 .. ..
++ .. ..
>> .. ..
>X {0 ..
/\ {< {>

# Returns 0 if '1' is passed, and 3 if '2' is passed
:Ff
}0 ..
-Z ..
>E -2
-C //
{0 ..

# Prints connector A
# Calls made: P1(23) P2(23) P2(20) P3(03) LF(00) P4(20) P2(23) LF(}0) P1(23)
#   P3(03) P3(00) P3(00) P3(03)
:PA
23 23 20 03 00 20 23 }0 23
P1 P2 P2 P3 LF P4 P2 LF P1
00 03 .. .. .. .. .. .. ..
03 00 .. .. .. .. .. .. ..
P3 P3 .. .. .. .. .. .. ..

# Prints connectors D0/D1/I0/I1
# }0 is either '1' or '2'
# }1 is either 32 or 35 (for D or I)
:PrDI
}0 }1
Ff -2
Li DI

# Helper for PrDI
# Calls made: L1(}1, }0) L2(}0) L1(}1, }0)
:LiDI
}1 }0 ..
}1 }0 }0
L1 L1 L2

# Prints '#   # ' (}0 = 0x23) or '      ' (}0 = 0x20)
:P1
}0 20 .. ..
}0 20 20 20

# Prints ' # # #' (}0 = 0x23) or '      ' (}0 = 0x20)
:P2
20 }0 20 }0 20 }0

# Prints ' # #' (}0 = 0x03) or '    ' (}0 = 0x00)
:P3
}0 ..
}0 20
+W 20

# Prints '===== ', }0 must be 0x20
:P4
3D 3D 3D 3D 3D }0

# Prints the top/bottom line of D/I connectors + newline
# Calls made: P1(}0) P2(23) P3(}1) P2(23)
:L1
}0 23 }1 23 0A
P1 P2 P3 P2 ..

# Prints the middle line of D/I connectors + newline
# Calls made: P4(20) P2(23) P3(}0) P2(23)
:L2
20 23 }0 23 0A
P4 P2 P3 P2 ..

# Emits a newline (0x0A) regardless of input
:LF
}0 ..
\/ 0A

```

# Answer
> 4 votes
# Perl 5: 105 (including 1 flag)

Yet another Perl solution. Uses stdin for the parameter.

```
#!perl -p
@x=map$_?'#':$",!/D/,-/2/,!/A/,1,0;$_='040 33311233
=====433311222
040 33211233';s/\d/$x[$&] /g;s/ $//mg

```

# Answer
> 4 votes
# GNU sed, 116 bytes

```
s/.*/&:#   #  33322433\n=====  33322444\n#   #  33422433/
/A/s/[42]/  /g
/1/s/2/  /g
/D/s/#/ /g
s/[2-4]/ #/g
s/.*://

```

### Output:

```
$ echo "A
D1
D2
I1
I2"|sed -f dvi.sed
#   #   # # #       # #
=====   # # #
#   #   # #         # #
        # # #     # # #
=====   # # #     # # #
        # # #     # # #
        # # # # # # # #
=====   # # # # # # # #
        # # # # # # # #
#   #   # # #     # # #
=====   # # #     # # #
#   #   # # #     # # #
#   #   # # # # # # # #
=====   # # # # # # # #
#   #   # # # # # # # #
$

```

# Answer
> 3 votes
## J, ~~198 194~~ 157 chars

**Minified**
```
3 22 echo@$'x   x  # # # x x x # #=====  # # # x x x x xx   x  # # x x x x # #'('x'I.@:=])}~(5 16$(#' #'$~#)"."0'4123212128262126290901824'){~D1`D2`I1`I2 i.<

```

Implemented as a function. Note that the function is a train, meaning one would have to surround it by parentheses or assign it to a name in order to use it (maybe I should count the parens as part of the function, even though technically they aren't).

**Ungolfed**
```
S1 =. (#' #'$~#)"."0'4123212128262126290901824'
S2 =. 'x   x  # # # x x x # #=====  # # # x x x x xx   x  # # x x x x # #'
f  =. 3 22 echo@$ S2 ('x'I.@:=])}~ (5 16$S1) {~ D1`D2`I1`I2 i. <

```

The idea is to store the common part of the string separately from the characters that differ between the connector types. `S1` stores the unique characters, and `S2` acts as a pattern with `x`'s acting as placeholders to fill in.

# Answer
> 3 votes
# Python - ~~167 166 164 161~~ 159

```
C=raw_input()
a=["#   # "," "*6]["D"in C]
r=" #"
b="A"in C
i=3-b
d=(r*[i,5][C[1:]>"1"]).rjust(10)
t=r*3
print a+t+d+"\n===== "+t+d*~-len(C)+"\n"+a+r*i+"  "*b+d

```

# Answer
> 3 votes
# JavaScript (ES6) 178 ~~186~~

**Edit** Having 7 base blocks, use base 7
The straight way, using string building with replace and 7 building blocks.
Output to stdout using alert as requested by OP.
Now I'll try some micro-optimizations...

```
F=t=>alert(
  {A:21349062249,D1:538695058296,D2:534740169498,I1:151139015296,I2:147184126498}[t]
  .toString(7).replace(/./g,c=>'\n0#   # 0===== 0 # # #0 # #0      0    '.split(0)[c])
)

```

**Test** In FireFox/FireBug console - removing 'alert' to simplify test

```
;['A','D1','D2','I1','I2'].forEach(i=>console.log(F(i)))

```

*Output*

```
#   #  # # #       # #
=====  # # #
#   #  # #         # #

       # # #     # # #
=====  # # #     # # #
       # # #     # # #

       # # # # # # # #
=====  # # # # # # # #
       # # # # # # # #

#   #  # # #     # # #
=====  # # #     # # #
#   #  # # #     # # #

#   #  # # # # # # # #
=====  # # # # # # # #
#   #  # # # # # # # #

```

# Answer
> 2 votes
# JavScript ES6, 186 bytes

```
f=c=>(b=(c[0]=='D'?'      ':'#   # '))+(e=(g=r=>parseInt(r,36).toString(2).replace(/./g,n=>' '+[' ','#'][n]))((o=c[1])?(o-1?73:'6f'):'6b'))+'\n===== '+(o?e:' # # #')+'\n'+b+(o?e:g('5f'))

```

```
f=c=>(b=(c[0]=='D'?'      ':'#   # '))+(e=(g=r=>parseInt(r,36).toString(2).replace(/./g,n=>' '+[' ','#'][n]))((o=c[1])?(o-1?73:'6f'):'6b'))+'\n===== '+(o?e:' # # #')+'\n'+b+(o?e:g('5f'))
alert(f(prompt()))
```

The code is quick and dirty, but it gets the job done. Mostly, the `#`'s and spaces are put into binary and then base 36. I'm looking into a more elegant and hopefully shorter solution.

# Answer
> 2 votes
## APL (115)

```
V←3 22⍴''⋄V[2;⍳5]←'='⋄V[⍳3;(2=⍴I)/(6+2×⍳8)~14 16/⍨'1'∊I]←V[⍳2;12]←V[⍳3;8 10]←V[R/1 3;1 5 20 22/⍨R←∨/'AI'∊I←⍞]←'#'⋄V

```

Test:

```
      V←3 22⍴''⋄V[2;⍳5]←'='⋄V[⍳3;(2=⍴I)/(6+2×⍳8)~14 16/⍨'1'∊I]←V[⍳2;12]←V[⍳3;8 10]←V[R/1 3;1 5 20 22/⍨R←∨/'AI'∊I←⍞]←'#'⋄V
A
#   #  # # #       # #
=====  # # #
#   #  # #         # #
      V←3 22⍴''⋄V[2;⍳5]←'='⋄V[⍳3;(2=⍴I)/(6+2×⍳8)~14 16/⍨'1'∊I]←V[⍳2;12]←V[⍳3;8 10]←V[R/1 3;1 5 20 22/⍨R←∨/'AI'∊I←⍞]←'#'⋄V
D1
       # # #     # # #
=====  # # #     # # #
       # # #     # # #
      V←3 22⍴''⋄V[2;⍳5]←'='⋄V[⍳3;(2=⍴I)/(6+2×⍳8)~14 16/⍨'1'∊I]←V[⍳2;12]←V[⍳3;8 10]←V[R/1 3;1 5 20 22/⍨R←∨/'AI'∊I←⍞]←'#'⋄V
D2
       # # # # # # # #
=====  # # # # # # # #
       # # # # # # # #
      V←3 22⍴''⋄V[2;⍳5]←'='⋄V[⍳3;(2=⍴I)/(6+2×⍳8)~14 16/⍨'1'∊I]←V[⍳2;12]←V[⍳3;8 10]←V[R/1 3;1 5 20 22/⍨R←∨/'AI'∊I←⍞]←'#'⋄V
I1
#   #  # # #     # # #
=====  # # #     # # #
#   #  # # #     # # #
      V←3 22⍴''⋄V[2;⍳5]←'='⋄V[⍳3;(2=⍴I)/(6+2×⍳8)~14 16/⍨'1'∊I]←V[⍳2;12]←V[⍳3;8 10]←V[R/1 3;1 5 20 22/⍨R←∨/'AI'∊I←⍞]←'#'⋄V
I2
#   #  # # # # # # # #
=====  # # # # # # # #
#   #  # # # # # # # #

```

# Answer
> 1 votes
# Perl 5 - 150 (149 + 1 for `n`)

### Golfed:

```
@b=split//;$_='0   0 ###112##
===== ###11222
0   0 ##2112##';
@c=(@b[0]eq D,@b[1]ne 2,@b[0]eq A);@d=('#',$");s/([#12])/ \1/g;s/(\d)/$d[$c[$1]]/ge;say

```

Input from STDIN, output to STDOUT. Works by doing filling in certain characters with `#` or  depending on the input.

### Ungolfed:

```
@b=split//; # char array from input
$_='0   0 ###112##
===== ###11222
0   0 ##2112##';

@c=(@b[0] eq 'D',@b[1] ne '2',@b[0] eq 'A');
@d=('#',' ');

s/([#12])/ \1/g; # add spaces
s/(\d)/$d[$c[$1]]/ge; # replace numbers with appropriate character
say $_;

```

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


title: Print the intersection of sequences

text:
# Question
Title: Print the intersection of sequences
# Sequences

You are given four number sequences, numbered `1` through `4`.

1. OEIS The location of `0`'s when the natural numbers are listed in binary. Here's an example of how to calculate the sequence:

```
 0,1,10,11,100,101,110,111
 ^    ^     ^^  ^    ^
 0    3     78  10   14

```

The start of the sequence goes like this: `0, 3, 7, 8, 10, 14, 19, 20, 21, 23, 24, 27, 29, 31, 36, 37, 40, 45, 51, ...`

---

2. OEIS This sequence includes the first natural number, skips the next two, then includes the next three, then skips the next four, and continues.

```
 0, 3, 4, 5, 10, 11, 12, 13, 14, 21, 22, 23, 24, 25, 26, 27, 36, ...

```

---

3. OEIS Positive integers where both the number of `0`'s and the number of `1`'s in the binary representation of the number are powers of `2`.

```
2, 4, 5, 6, 9, 10, 12, 16, 23, 27, 29, 30, 33, 34, 36, 39,

```

---

4. OEIS The Hofstadter Q sequence.

> a(1) = a(2) = 1;
> a(n) = a(n-a(n-1)) + a(n-a(n-2)) for n \> 2.

```
1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, 12, 12, 12, 16, 14, ...

```

Little is proven rigorously about this sequence, but many empirical results exist. One is particularly important, and you may assume it's valid for the entire series:

This paper observed that the elements of the series can be grouped into generations. If we number them starting at 1, then the *k*th generation contains exactly 2k elements. The relevant property is that all numbers in generation *k* are obtained by summing two numbers from generations *k-1* and/or *k-2*, but never from earlier generations. You may use this (and only this) observation to put a lower bound on the remaining elements in the sequence.

---

# Challenge

Your challenge is to print the first `x` numbers in the intersection of the given input sequences.

**Input:** Two numbers separated by a space on `STDIN`. The first number is an integer from `1` to `15` inclusive where each bit corresponds to a sequence. The lowest bit corresponds to sequence `1`, and the highest corresponds to sequence `4`. The second is amount of numbers, `x`, to output on `STDIN`.

**Output:** The first `x` numbers that intersect with the given input sequences. Print the numbers on `STDOUT` with any clear whitespace or punctuation as a delimiter (spaces, tabs, newlines, commas, colons, periods, etc).

---

# Examples

**1.** Print the first `3` numbers that are in every sequence.

Input: `15 3`

Output: `10,23,40`

---

**2.** Print the first `12` numbers in sequences number `1` and `4`.

Input: `9 12`

Output: `3,8,10,14,19,20,21,23,24,31,37,40`

---

**3.** Print the first `10` numbers in sequence `2`.

Input: `2 10`

Output: `0,3,4,5,10,11,12,13,14,21`

---

**4.** Print the first `6` numbers in sequences `3` and `4`.

Input: `12 6`

Output: `2,4,5,6,9,10`

---

# Details

* You may print the output as you go or all at once at the end.

*Huge thanks to everyone who helped out with this in chat! This question benefited greatly from being in the sandbox.*

# Answer
> 2 votes
# Haskell, 495 442 402

```
import Data.List
d=1:1:1%2
f=filter
p 0="0"
p 1="1"
p n=p(div n 2)++p(mod n 2)
l=length
u z[a,b]=sort.head.dropWhile((<b).l)$m(nub.foldl1 intersect.y(tail.p$31-a).(`m`[d,f(v.group.sort.p)[1..],z#1,y(z>>=p)z]).take)z
w=(=='0')
v[a]=1>2
v x=all(all w.tail.p.l)x
y x=m snd.f(w.fst).zip x
x#n=n`take`x++drop(n+n+1)x#(n+2)
n%m=d!!(m-d!!n)+d!!(m-d!!(n-1)):m%(m+1)
main=interact$show.u[0..].m read.words
m=map

```

It performs reasonably well. Here are a couple of OP's examples:

```
Flonk@home:~>echo 15 10 | codegolf
[10,23,40,57,58,139,147,149,212,228]
Flonk@home:~>echo 9 12 | codegolf
[3,8,10,14,19,20,21,23,24,31,37,40]
Flonk@home:~>echo 2 10 | codegolf
[0,3,4,5,10,11,12,13,14,21]
Flonk@home:~>echo 12 6 | codegolf
[2,4,5,6,9,10]

```

# Answer
> 4 votes
# Python 3, ~~590~~ 639 characters

```
from itertools import count as C
D=lambda n,t='1':bin(n).count(t)
Y=range
def O():
 for n in C(0):yield from bin(n)[2:]
def B():
 s=i=0
 while 1:
  i+=s
  for j in Y(i,i+s+1):yield j
  s+=2;i+=s-1
def s(i):return D(i)==1
def F():
 a=[1]*3
 for n in C(3):a+=[a[n-a[n-1]]+a[n-a[n-2]]];yield a[-1]
L,R=input().split()
J=[x for x,U in zip([F(),(n for n in C(0)if s(D(n,'0')-1)and s(D(n))),B(),(i for i,c in enumerate(O())if'1'>c)],"{0:04b}".format(int(L)))if U>'0']
X=[set()for _ in J]
M=[]
Z=int(R);K=1
while len(M)<Z:
 for x,j in zip(X,J):x.add(next(j))
 for _ in Y(K):X[0].add(next(J[0]));K+=1
 M=X[0]
 for x in X:M=M&x
print(sorted(M)[:Z])

```

This is the straight-forward solution: use generators to define each of the infinite sequences, and so long as the intersection isn't large enough, add a step to each sequence.

To account for the non-monotonically-increasing Hofstadter sequence: at each step I generate twice as many for that sequence, e.g. 1, then 2, 4, 8, 16, 32, etc. I think that satisfies the bound stated in the question, and it's still fast enough for all the test cases presented there.

# Answer
> 3 votes
**C#, 1923**

It probably wont be the shortest program but i found the challenge interesting, so here is my solution.

Running all 4 with 35 Numbers (15 35) takes about 5 seconds.

You can test it here, but note that if you want OEIS4 the amount of digits you want needs to be small or netfiddle runs out of memory.

**Golfed**

```
using System;using System.Collections;using System.Collections.Generic;using System.Linq;class p{public static void Main(string[] args){int b=0;IEnumerable<int>a=null;foreach(char c in Convert.ToString(int.Parse(args[0]),2).Reverse()){++b;if(c=='0')continue;switch(b){case 1: a=d(a,e());break;case 2: a=d(a,f());break;case 3: a=d(a,g());break;case 4: a=d(a,h(),true);break;}}if(a==null)return;bool j=true;foreach(int i in a.Take(int.Parse(args[1]))){if(j)j=false;else Console.Write(",");Console.Write(i);}}static IEnumerable<int>d(IEnumerable<int>k,IEnumerable<int>l,bool m=false){if(k==null)foreach(int n in l)yield return n;int o=0;int p=1;foreach(int i in k){Dictionary<int,HashSet<int>>q=m ? new Dictionary<int,HashSet<int>>(): null;int s=0;foreach(int n in l){if(!m){if(i<n)break;}else{if(!q.ContainsKey(o))q.Add(o,new HashSet<int>());q[o].Add(n);if(q.Count==1){int r=q[o].OrderBy(gi =>gi).Take(2).Sum();if(i<r)break;}else{int r=q[o].Concat(q[o-1]).OrderBy(gi =>gi).Take(2).Sum();if(i<r)break;}if(++s==p){o++;p=(int)Math.Pow(2,o);}}if(i==n){yield return i;break;}}}}static IEnumerable<int>e(){int t=0;for(int i=0;i<int.MaxValue;i++)foreach(char c in Convert.ToString(i,2)){if(c=='0')yield return t;t++;}}static IEnumerable<int>f(){int t=1;int u=0;bool v=true;using(IEnumerator<int>w=Enumerable.Range(0,int.MaxValue).GetEnumerator()){while(w.MoveNext()){if(v){if(u==0)u=t+1;yield return w.Current;if(--t==0)v=false;}else{if(t==0)t=u+1;if(--u==0)v=true;}}}}static IEnumerable<int>g(){for(int i=0;i<int.MaxValue;i++){string s=Convert.ToString(i,2);if(x(s.Count(c =>c=='0'))&& x(s.Count(c =>c=='1')))yield return i;}}static bool x(int y){return(y != 0)&&((y &(y-1))==0);}static IEnumerable<int>h(){return Enumerable.Range(1,int.MaxValue).Select(z);}static Dictionary<int,int>_=new Dictionary<int,int>();static int z(int n){int a;if(!_.TryGetValue(n,out a)){if(n<3)a=1;else a=z(n-z(n-1))+z(n-z(n-2));_.Add(n,a);}return a;}}

```

**Readable**

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

class Programm
{
    public static void Main(string[] args)
    {
        int index = 0;

        IEnumerable<int> intersection = null;

        foreach (char c in Convert.ToString(int.Parse(args[0]), 2).Reverse())
        {
            ++index;
            if (c == '0')
                continue;

            switch (index)
            {
                case 1: intersection = _join(intersection, OEIS1()); break;
                case 2: intersection = _join(intersection, OEIS2()); break;
                case 3: intersection = _join(intersection, OEIS3()); break;
                case 4: intersection = _join(intersection, OEIS4(), true); break;

                default: throw new ArgumentException();
            }
        }
        if (intersection == null)
            return;

        bool first = true;
        foreach (int i in intersection.Take(int.Parse(args[1])))
        {
            if (first) first = false;
            else Console.Write(",");

            Console.Write(i);
        }

        Console.ReadKey();
    }

    private static IEnumerable<int> _join(IEnumerable<int> intersection, IEnumerable<int> newSequence, bool hof = false)
    {
        if (intersection == null)
            foreach (int n in newSequence) yield return n;

        int generation = 0;
        int generationMax = 1;
        foreach (int i in intersection)
        {
            Dictionary<int, HashSet<int>> generationCache = hof ? new Dictionary<int, HashSet<int>>() : null;
            int count = 0;
            foreach (int n in newSequence)
            {
                if (!hof)
                {
                    if (i < n)
                        break;
                }
                else
                {
                    if (!generationCache.ContainsKey(generation))
                        generationCache.Add(generation, new HashSet<int>());

                    generationCache[generation].Add(n);

                    if (generationCache.Count == 1)
                    {
                        int lowerBound = generationCache[generation].OrderBy(gi => gi).Take(2).Sum();
                        if (i < lowerBound)
                            break;
                    }
                    else
                    {
                        int lowerBound = generationCache[generation].Concat(generationCache[generation - 1]).OrderBy(gi => gi).Take(2).Sum();
                        if (i < lowerBound)
                            break;
                    }

                    if (++count == generationMax)
                    {
                        generation++;
                        generationMax = (int)Math.Pow(2, generation);
                    }
                }

                if (i == n)
                {
                    yield return i;
                    break;
                }
            }
        }
    }

    static IEnumerable<int> OEIS1()
    {
        int position = 0;
        for (int i = 0; i < int.MaxValue; i++)
            foreach (char c in Convert.ToString(i, 2))
            {
                if (c == '0')
                    yield return position;
                position++;
            }
    }

    static IEnumerable<int> OEIS2()
    {
        int take = 1;
        int skip = 0;
        bool doTake = true;
        using (IEnumerator<int> enumerator = Enumerable.Range(0, int.MaxValue).GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                if (doTake)
                {
                    if (skip == 0)
                        skip = take + 1;
                    yield return enumerator.Current;
                    if (--take == 0)
                        doTake = false;
                }
                else
                {
                    if (take == 0)
                        take = skip + 1;
                    if (--skip == 0)
                        doTake = true;
                }
            }
        }
    }

    static IEnumerable<int> OEIS3()
    {
        for (int i = 0; i < int.MaxValue; i++)
        {
            string s = Convert.ToString(i, 2);
            if (_isPowerOfTwo(s.Count(c => c == '0')) && _isPowerOfTwo(s.Count(c => c == '1')))
                yield return i;
        }
    }

    static bool _isPowerOfTwo(int number)
    {
        return (number != 0) && ((number & (number - 1)) == 0);
    }

    static IEnumerable<int> OEIS4()
    {
        return Enumerable.Range(1, int.MaxValue).Select(HofstadterQ);
    }

    static Dictionary<int, int> _hofstadterQCache = new Dictionary<int, int>();

    static int HofstadterQ(int n)
    {
        int result;
        if (!_hofstadterQCache.TryGetValue(n, out result))
        {
            if (n < 3)
                result = 1;
            else
                result = HofstadterQ(n - HofstadterQ(n - 1)) + HofstadterQ(n - HofstadterQ(n - 2));

            _hofstadterQCache.Add(n, result);
        }
        return result;
    }
}

```

**Explanation**

This makes use of lazy evaluation bigtime which makes it prett fast i bellieve. Also i was lazy doing any "bitlogic" by using the frameworks Convert.ToString(number, 2) method. This turns any number into its binray representation as a string.

I had to write my own method to intersect the seuqences as the Linq-Method intersect computes the intersection of the full sequence, and that was literally impossible.

---
Tags: code-golf, math, sequence, set-theory
---


# Question
Title: CSS attribute selector efficient "greater than selector" code
The goal is to find a way better than the current best known way of encoding the index of a child HTML element, so that encoded indices have the following property.

```
if (index_i >= index_p) {
  assert(encoding(index_i).indexOf(encoding(index_p)) == 0);
}

if (index_i < index_p) {
  assert(encoding(index_i).indexOf(encoding(index_p)) !== 0);
}

```

The current best known way of doing this is with a form of unary encoding (without the usual trailing zero. So, for example, when `index_p = 10`:

* `encoding(index_p) == "11111111111"` true
* `index_i = 9; encoding(index_i) == "1111111111"` true
* `"11111111111".indexOf("1111111111") !== 0` true
* `"1111111111".indexOf("11111111111") == 0` true

**Application**

An application of this is being able to use `document.querySelectorAll` for obtaining all child elements "greater than" a certain index, via utilisation of the "starts with" attribute selector, `^=`.

For example, if we have a set of 100 div elements, and each div element has been given an attribute `ei` equal to its encoded index value. If our goal is to obtain a list of the **last 51** of div elements, one way to do this is to request:

`document.querySelectorAll('div[ei^='+Array(50).join("1")+']');`

However, if we have interesting numbers of divs (1000, 10000), then we use a lot of memory storing these attribute indexes. So we get the typical "memory" vs "speed" tradeoff for setting up this indexing system.

The question is : **is there a way to do the same thing, using an encoded index, such that it is shorter than this pseudo-unary version?**

***Motivation***

One motivation that contributes to this question post here is the following subtle point: the elements may not necessarily be in the indexed order.

This unusual occurrence is by no means something that one would expect in ordinary use of the DOM, but if we are absolutely positioning the elements based on their indices, and we are swapping, inserting and deleting the elements, then it is possible to have a meaningful piece of HTML where document order is actually not related to the rendering order that ends up meaning something to somebody. And in such a case, we may still need to look at a range of elements, such as, all elements with an index larger than 72, and with an indexing method with properties like those described above, then we can use the starts with attribute selector to gather together this set.

# Answer
> 1 votes
You could always try something of the form

```
<tag h="111" t="11111" o="1">

```

where you use your unary encoding for each of the hundreds (`h`), tens (`t`) and ones (`o`) attributes.

A greater-than CSS selector would then look like

```
tag[h^="1111"],tag[h="111"][t^="111111"],tag[h="111"][t="11111"][o^="1"] { ... }

```

but frankly, if your tags are just retaining some property that persists in spite of reordering, etc., why not just run a script that selects the last `n` marked tags on DOM load and assigns the class `iamlast`, then use the `.iamlast` CSS selector?

---
Tags: math, compression
---