# Question
Title: Print all domino tilings of 4x6 rectangle
This is an extension of Fibonacci Domino Tiling. Your goal is to print all 281 ways to tile a 4x6 rectangle with 1x2 and 2x1 dominoes. Fewest bytes wins.

Use the vertical bar `|` to indicate a space covered by the vertical domino, and an em-dash  (count it as if it were ASCII) or hyphen `-` for horizontal ones.

**Example output: (281 tilings, 1405 lines)**

```
——————
——————
——————
——————

||————
||————
——————
——————

|——|——
|——|——
——————
——————

——||——
——||——
——————
——————

|————|
|————|
——————
——————

——|——|
——|——|
——————
——————

————||
————||
——————
——————

||||——
||||——
——————
——————

|||——|
|||——|
——————
——————

——————
||————
||————
——————

||——||
||——||
——————
——————

|——|||
|——|||
——————
——————

——||||
——||||
——————
——————

——————
|——|——
|——|——
——————

——————
——||——
——||——
——————

||————
||||——
——||——
——————

——||——
||||——
||————
——————

——|——|
|||——|
||————
——————

————||
||——||
||————
——————

||||||
||||||
——————
——————

——————
|————|
|————|
——————

——————
——|——|
——|——|
——————

||————
|||——|
——|——|
——————

————||
|——|||
|——|——
——————

——————
————||
————||
——————

||————
||——||
————||
——————

|——|——
|——|||
————||
——————

——||——
——||||
————||
——————

————||
——||||
——||——
——————

||||——
||||||
————||
——————

——————
||||——
||||——
——————

||——||
||||||
——||——
——————

——||||
||||||
||————
——————

——————
|||——|
|||——|
——————

——————
——————
||————
||————

||————
||————
||————
||————

|——|——
|——|——
||————
||————

——||——
——||——
||————
||————

|————|
|————|
||————
||————

——|——|
——|——|
||————
||————

————||
————||
||————
||————

||||——
||||——
||————
||————

|||——|
|||——|
||————
||————

——————
||——||
||——||
——————

||——||
||——||
||————
||————

|——|||
|——|||
||————
||————

——||||
——||||
||————
||————

——————
|——|||
|——|||
——————

——————
——||||
——||||
——————

||————
||||||
——||||
——————

——||——
||||||
||——||
——————

————||
||||||
||||——
——————

||||||
||||||
||————
||————

——————
——————
|——|——
|——|——

||————
||————
|——|——
|——|——

|——|——
|——|——
|——|——
|——|——

——||——
——||——
|——|——
|——|——

|————|
|————|
|——|——
|——|——

——|——|
——|——|
|——|——
|——|——

————||
————||
|——|——
|——|——

||||——
||||——
|——|——
|——|——

|||——|
|||——|
|——|——
|——|——

||——||
||——||
|——|——
|——|——

|——|||
|——|||
|——|——
|——|——

——||||
——||||
|——|——
|——|——

||||||
||||||
|——|——
|——|——

——————
——————
——||——
——||——

||————
||————
——||——
——||——

|——|——
|——|——
——||——
——||——

——||——
——||——
——||——
——||——

|————|
|————|
——||——
——||——

——|——|
——|——|
——||——
——||——

————||
————||
——||——
——||——

||||——
||||——
——||——
——||——

|||——|
|||——|
——||——
——||——

——————
||————
||||——
——||——

||——||
||——||
——||——
——||——

|——|||
|——|||
——||——
——||——

——||||
——||||
——||——
——||——

——————
——||——
||||——
||————

||————
||||——
||||——
||————

|——|——
||||——
||||——
|——|——

——||——
||||——
||||——
——||——

|————|
|||——|
||||——
|——|——

——|——|
|||——|
||||——
——||——

————||
||——||
||||——
——||——

||||||
||||||
——||——
——||——

——————
——|——|
|||——|
||————

||————
|||——|
|||——|
||————

——————
————||
||——||
||————

||————
||——||
||——||
||————

|——|——
|——|||
||——||
||————

——||——
——||||
||——||
||————

————||
——||||
||||——
||————

||||——
||||||
||——||
||————

——————
||||||
||||||
——————

||——||
||||||
||||——
||————

|——|||
||||||
||||——
|——|——

——||||
||||||
||||——
——||——

——————
——————
|————|
|————|

||————
||————
|————|
|————|

|——|——
|——|——
|————|
|————|

——||——
——||——
|————|
|————|

|————|
|————|
|————|
|————|

——|——|
——|——|
|————|
|————|

————||
————||
|————|
|————|

||||——
||||——
|————|
|————|

|||——|
|||——|
|————|
|————|

||——||
||——||
|————|
|————|

|——|||
|——|||
|————|
|————|

——||||
——||||
|————|
|————|

||||||
||||||
|————|
|————|

——————
——————
——|——|
——|——|

||————
||————
——|——|
——|——|

|——|——
|——|——
——|——|
——|——|

——||——
——||——
——|——|
——|——|

|————|
|————|
——|——|
——|——|

——|——|
——|——|
——|——|
——|——|

————||
————||
——|——|
——|——|

||||——
||||——
——|——|
——|——|

|||——|
|||——|
——|——|
——|——|

——————
||————
|||——|
——|——|

||——||
||——||
——|——|
——|——|

|——|||
|——|||
——|——|
——|——|

——||||
——||||
——|——|
——|——|

|——|——
||||——
|||——|
|————|

——||——
||||——
|||——|
——|——|

|————|
|||——|
|||——|
|————|

——|——|
|||——|
|||——|
——|——|

————||
||——||
|||——|
——|——|

||||||
||||||
——|——|
——|——|

|————|
||——||
||——||
|————|

——————
————||
|——|||
|——|——

||————
||——||
|——|||
|——|——

|——|——
|——|||
|——|||
|——|——

——||——
——||||
|——|||
|——|——

|————|
|——|||
|——|||
|————|

——|——|
——||||
|——|||
|————|

||||——
||||||
|——|||
|——|——

|||——|
||||||
|——|||
|————|

|——|||
||||||
|||——|
|————|

——||||
||||||
|||——|
——|——|

——————
——————
————||
————||

||————
||————
————||
————||

|——|——
|——|——
————||
————||

——||——
——||——
————||
————||

|————|
|————|
————||
————||

——|——|
——|——|
————||
————||

————||
————||
————||
————||

||||——
||||——
————||
————||

|||——|
|||——|
————||
————||

——————
||————
||——||
————||

||——||
||——||
————||
————||

|——|||
|——|||
————||
————||

——||||
——||||
————||
————||

——————
|——|——
|——|||
————||

——————
——||——
——||||
————||

||————
||||——
——||||
————||

——||——
||||——
||——||
————||

——|——|
|||——|
||——||
————||

————||
||——||
||——||
————||

||||||
||||||
————||
————||

————||
|——|||
|——|||
————||

——————
————||
——||||
——||——

||————
||——||
——||||
——||——

|——|——
|——|||
——||||
——||——

——||——
——||||
——||||
——||——

|————|
|——|||
——||||
——|——|

——|——|
——||||
——||||
——|——|

————||
——||||
——||||
————||

||||——
||||||
——||||
——||——

|||——|
||||||
——||||
——|——|

——————
||||——
||||||
————||

||——||
||||||
——||||
————||

——||||
||||||
||——||
————||

——————
——————
||||——
||||——

||————
||————
||||——
||||——

|——|——
|——|——
||||——
||||——

——||——
——||——
||||——
||||——

|————|
|————|
||||——
||||——

——|——|
——|——|
||||——
||||——

————||
————||
||||——
||||——

||||——
||||——
||||——
||||——

|||——|
|||——|
||||——
||||——

——————
||——||
||||||
——||——

||——||
||——||
||||——
||||——

|——|||
|——|||
||||——
||||——

——||||
——||||
||||——
||||——

——————
——||||
||||||
||————

||————
||||||
||||||
||————

|——|——
||||||
||||||
|——|——

——||——
||||||
||||||
——||——

|————|
||||||
||||||
|————|

——|——|
||||||
||||||
——|——|

————||
||||||
||||||
————||

||||||
||||||
||||——
||||——

——————
——————
|||——|
|||——|

||————
||————
|||——|
|||——|

|——|——
|——|——
|||——|
|||——|

——||——
——||——
|||——|
|||——|

|————|
|————|
|||——|
|||——|

——|——|
——|——|
|||——|
|||——|

————||
————||
|||——|
|||——|

||||——
||||——
|||——|
|||——|

|||——|
|||——|
|||——|
|||——|

||——||
||——||
|||——|
|||——|

|——|||
|——|||
|||——|
|||——|

——||||
——||||
|||——|
|||——|

||||||
||||||
|||——|
|||——|

——————
——————
||——||
||——||

||————
||————
||——||
||——||

|——|——
|——|——
||——||
||——||

——||——
——||——
||——||
||——||

|————|
|————|
||——||
||——||

——|——|
——|——|
||——||
||——||

————||
————||
||——||
||——||

||||——
||||——
||——||
||——||

|||——|
|||——|
||——||
||——||

||——||
||——||
||——||
||——||

|——|||
|——|||
||——||
||——||

——||||
——||||
||——||
||——||

||||||
||||||
||——||
||——||

——————
——————
|——|||
|——|||

||————
||————
|——|||
|——|||

|——|——
|——|——
|——|||
|——|||

——||——
——||——
|——|||
|——|||

|————|
|————|
|——|||
|——|||

——|——|
——|——|
|——|||
|——|||

————||
————||
|——|||
|——|||

||||——
||||——
|——|||
|——|||

|||——|
|||——|
|——|||
|——|||

||——||
||——||
|——|||
|——|||

|——|||
|——|||
|——|||
|——|||

——||||
——||||
|——|||
|——|||

||||||
||||||
|——|||
|——|||

——————
——————
——||||
——||||

||————
||————
——||||
——||||

|——|——
|——|——
——||||
——||||

——||——
——||——
——||||
——||||

|————|
|————|
——||||
——||||

——|——|
——|——|
——||||
——||||

————||
————||
——||||
——||||

||||——
||||——
——||||
——||||

|||——|
|||——|
——||||
——||||

——————
||————
||||||
——||||

||——||
||——||
——||||
——||||

|——|||
|——|||
——||||
——||||

——||||
——||||
——||||
——||||

——————
——||——
||||||
||——||

||————
||||——
||||||
||——||

|——|——
||||——
||||||
|——|||

——||——
||||——
||||||
——||||

|————|
|||——|
||||||
|——|||

——|——|
|||——|
||||||
——||||

————||
||——||
||||||
——||||

||||||
||||||
——||||
——||||

——————
————||
||||||
||||——

||————
||——||
||||||
||||——

|——|——
|——|||
||||||
||||——

——||——
——||||
||||||
||||——

|————|
|——|||
||||||
|||——|

——|——|
——||||
||||||
|||——|

————||
——||||
||||||
||——||

||||——
||||||
||||||
||||——

|||——|
||||||
||||||
|||——|

||——||
||||||
||||||
||——||

|——|||
||||||
||||||
|——|||

——||||
||||||
||||||
——||||

——————
——————
||||||
||||||

||————
||————
||||||
||||||

|——|——
|——|——
||||||
||||||

——||——
——||——
||||||
||||||

|————|
|————|
||||||
||||||

——|——|
——|——|
||||||
||||||

————||
————||
||||||
||||||

||||——
||||——
||||||
||||||

|||——|
|||——|
||||||
||||||

||——||
||——||
||||||
||||||

|——|||
|——|||
||||||
||||||

——||||
——||||
||||||
||||||

||||||
||||||
||||||
||||||

```

**Input**

There is no input -- you only have to print 4x6 tilings. In theory, you could hardcode an output, but that would likely take more bytes that producing it.

**Output**

Print the 281 tilings in any order in the format shown in the example, with each one appearing exactly once. There must be exactly one empty line between tilings. Any other whitespace is OK if it doesn't affect the visible output. Empty lines at the start and end are also OK.

**Other requirements**

Your code should not be horribly slow; it should produce output within 10 minutes, which should be ample time. Functions to produce or enumerate tilings are disallowed.

In case people are wondering if this is sufficiently distinct from Fibonacci Domino Tiling, I expect the answers to use a different strategies as one can no longer take advantage of the particular Fibonacci structure of 2-by-n domino tilings and them being specified by their top row.

# Answer
> 6 votes
# CJam, ~~75~~ ~~67~~ ~~63~~ ~~58~~ 57 bytes

```
La'|a{_'|f+@:C"--"f++}5*\;_m*_m*{~+}%{zC{81f^}%-!},Nf+Nf*

```

Try it online.

### Example run

```
$ cjam 4x6.cjam | head -9
||||||
||||||
||||||
||||||

||||||
||||||
--||||
--||||
$ cjam 4x6.cjam | tail -10
------
------
||----
||----

------
------
------
------

$ cjam 4x6.cjam | wc -l
1405
$ cjam 4x6.cjam | md5sum
83b5de42157ace906ed5c0173fb99027  -

```

### Background

A covering of the rectangle by domino halves is a valid tiling if:

1. Horizontal domino halves occur in pairs in each row.
2. Vertical domino halves occur in pairs in each column.

The valid configurations for rows of length *n* can be obtained by adding a vertical domino half to the valid configurations for *n - 1* and a two horizontal domino halves to the valid configurations for *n - 2*.

The valid configurations for columns of length *n* can be computed as the configurations of rows of the same length, exchanging vertical domino halves and horizontal domino halves.

To generate all 281 possible tilings, it suffices to generate all possible combinations of rows, all possible combinations of columns and intersect the two sets.

### Implementation

Rather than generating combinations twice and intersecting, we can generate all possible combinations of rows and check if their columns have a valid pattern.

```
" Leave an array of valid row configurations of length 6 on the stack and save the valid
  row configurations of length 4 in C. In http://codegolf.stackexchange.com/a/38000,
  I explain in detail how this is achieved.                                               ";

La'|a{_'|f+@:C"--"f++}5*\;

" Compute the Cartesian product of four copies of the array.                              ";

_m*_m*

" Flatten the arrays of strings of the Cartesian product.                                 ";

{~+}%

" Transpose rows and columns, swap vertical bars and hyphens in C (note that ord('-') ==
 ord('-') ^ 81) and check if all rows of the first array belong to the second.            ";

{zC{81f^}%-!},

" Separate the rows of a tiling and the tilings from each other.                          ";

Nf+ Nf*

```

# Answer
> 4 votes
# C, 282 bytes ungolfed

```
i,j,p[4],q,t,a,b,c,d;
main(){
  char s[]="UTRQPJIHEDBA@";
  for(i=64*169;i--;){
    a=p[0]=s[i%13]*3,d=p[3]=s[i/13%13]*3,q=i/169;
    b=p[1]=p[0]&q;c=p[2]=p[3]&q;
    if((a|q)==255&(d|q)==255 & (b/3|b/3*2)==b & (c/3|c/3*2)==c)
      for(j=24;j--;)putchar(p[j/6]>>j%6&1?45:124),j%6||printf(j?"\n":" %d\n\n",t+=!j);
  }
}

```

This works in a similar way to my answer to the previous question, with 1 representing `-` and 0 representing `|`. In fact the 13 valid combinations for n=6 in the previous question are encoded in `s[]`, having had binary `11000000` added to them to bring them into a convenient ASCII range, then divided by 3.

A logical way to proceed is to place the vertical dominoes that straddle the centreline, then place the remaining vertical dominoes, and finally place the horizontal dominoes. That's basically how my code proceeds. The 13x13=169 possible tilings with no vertical dominoes crossing the centreline are listed first, then the different combinations of vertical dominoes crossing the centreline are explored.

`q` contains the pattern for vertical centre dominoes (all 64 combinations of 1's and 0's are allowed in principle.) `a` and `d` store the top and bottom rows (only those 13 combinations from the previous question are allowed, as they are the only ones that give complete horizontal dominoes.) `b` and `c` hold the calculated values for the centre rows (made by ANDing `q` with `a` and `d`) and the following rules are applied:

1: no vertical dominoes may overlap. `a` and `d` when ORed with `q` must give `11111111`. (Remember due to the compression method, each domino in `a` and `d`is carrying an additional 11000000.)

2: rows `b` and `c` must hold complete horizontal dominoes. The code for checking this is `(b/3|b/3*2)==b` and is explained in my answer to the previous question.

**output**

in addition to `a,b,c,d`, the four rows are stored in an array `p[]` for printing via a loop. Currently each pattern is numbered. The numbering will be removed as part of the golfing process.

```
||||||
||||||
||||||
|||||| 1

||||||
||||||
||||--
||||-- 2

||||||
||||||
|||--|
|||--| 3

||||||
||||||
||--||
||--|| 4

||||||
||||||
||----
||---- 5

||||||
||||||
|--|||
|--||| 6

||||||
||||||
|--|--
|--|-- 7

||||||
||||||
|----|
|----| 8

||||||
||||||
--||||
--|||| 9

||||||
||||||
--||--
--||-- 10

||||||
||||||
--|--|
--|--| 11

||||||
||||||
----||
----|| 12

||||||
||||||
------
------ 13

||||--
||||--
||||||
|||||| 14

||||--
||||--
||||--
||||-- 15

||||--
||||--
|||--|
|||--| 16

||||--
||||--
||--||
||--|| 17

||||--
||||--
||----
||---- 18

||||--
||||--
|--|||
|--||| 19

||||--
||||--
|--|--
|--|-- 20

||||--
||||--
|----|
|----| 21

||||--
||||--
--||||
--|||| 22

||||--
||||--
--||--
--||-- 23

||||--
||||--
--|--|
--|--| 24

||||--
||||--
----||
----|| 25

||||--
||||--
------
------ 26

|||--|
|||--|
||||||
|||||| 27

|||--|
|||--|
||||--
||||-- 28

|||--|
|||--|
|||--|
|||--| 29

|||--|
|||--|
||--||
||--|| 30

|||--|
|||--|
||----
||---- 31

|||--|
|||--|
|--|||
|--||| 32

|||--|
|||--|
|--|--
|--|-- 33

|||--|
|||--|
|----|
|----| 34

|||--|
|||--|
--||||
--|||| 35

|||--|
|||--|
--||--
--||-- 36

|||--|
|||--|
--|--|
--|--| 37

|||--|
|||--|
----||
----|| 38

|||--|
|||--|
------
------ 39

||--||
||--||
||||||
|||||| 40

||--||
||--||
||||--
||||-- 41

||--||
||--||
|||--|
|||--| 42

||--||
||--||
||--||
||--|| 43

||--||
||--||
||----
||---- 44

||--||
||--||
|--|||
|--||| 45

||--||
||--||
|--|--
|--|-- 46

||--||
||--||
|----|
|----| 47

||--||
||--||
--||||
--|||| 48

||--||
||--||
--||--
--||-- 49

||--||
||--||
--|--|
--|--| 50

||--||
||--||
----||
----|| 51

||--||
||--||
------
------ 52

||----
||----
||||||
|||||| 53

||----
||----
||||--
||||-- 54

||----
||----
|||--|
|||--| 55

||----
||----
||--||
||--|| 56

||----
||----
||----
||---- 57

||----
||----
|--|||
|--||| 58

||----
||----
|--|--
|--|-- 59

||----
||----
|----|
|----| 60

||----
||----
--||||
--|||| 61

||----
||----
--||--
--||-- 62

||----
||----
--|--|
--|--| 63

||----
||----
----||
----|| 64

||----
||----
------
------ 65

|--|||
|--|||
||||||
|||||| 66

|--|||
|--|||
||||--
||||-- 67

|--|||
|--|||
|||--|
|||--| 68

|--|||
|--|||
||--||
||--|| 69

|--|||
|--|||
||----
||---- 70

|--|||
|--|||
|--|||
|--||| 71

|--|||
|--|||
|--|--
|--|-- 72

|--|||
|--|||
|----|
|----| 73

|--|||
|--|||
--||||
--|||| 74

|--|||
|--|||
--||--
--||-- 75

|--|||
|--|||
--|--|
--|--| 76

|--|||
|--|||
----||
----|| 77

|--|||
|--|||
------
------ 78

|--|--
|--|--
||||||
|||||| 79

|--|--
|--|--
||||--
||||-- 80

|--|--
|--|--
|||--|
|||--| 81

|--|--
|--|--
||--||
||--|| 82

|--|--
|--|--
||----
||---- 83

|--|--
|--|--
|--|||
|--||| 84

|--|--
|--|--
|--|--
|--|-- 85

|--|--
|--|--
|----|
|----| 86

|--|--
|--|--
--||||
--|||| 87

|--|--
|--|--
--||--
--||-- 88

|--|--
|--|--
--|--|
--|--| 89

|--|--
|--|--
----||
----|| 90

|--|--
|--|--
------
------ 91

|----|
|----|
||||||
|||||| 92

|----|
|----|
||||--
||||-- 93

|----|
|----|
|||--|
|||--| 94

|----|
|----|
||--||
||--|| 95

|----|
|----|
||----
||---- 96

|----|
|----|
|--|||
|--||| 97

|----|
|----|
|--|--
|--|-- 98

|----|
|----|
|----|
|----| 99

|----|
|----|
--||||
--|||| 100

|----|
|----|
--||--
--||-- 101

|----|
|----|
--|--|
--|--| 102

|----|
|----|
----||
----|| 103

|----|
|----|
------
------ 104

--||||
--||||
||||||
|||||| 105

--||||
--||||
||||--
||||-- 106

--||||
--||||
|||--|
|||--| 107

--||||
--||||
||--||
||--|| 108

--||||
--||||
||----
||---- 109

--||||
--||||
|--|||
|--||| 110

--||||
--||||
|--|--
|--|-- 111

--||||
--||||
|----|
|----| 112

--||||
--||||
--||||
--|||| 113

--||||
--||||
--||--
--||-- 114

--||||
--||||
--|--|
--|--| 115

--||||
--||||
----||
----|| 116

--||||
--||||
------
------ 117

--||--
--||--
||||||
|||||| 118

--||--
--||--
||||--
||||-- 119

--||--
--||--
|||--|
|||--| 120

--||--
--||--
||--||
||--|| 121

--||--
--||--
||----
||---- 122

--||--
--||--
|--|||
|--||| 123

--||--
--||--
|--|--
|--|-- 124

--||--
--||--
|----|
|----| 125

--||--
--||--
--||||
--|||| 126

--||--
--||--
--||--
--||-- 127

--||--
--||--
--|--|
--|--| 128

--||--
--||--
----||
----|| 129

--||--
--||--
------
------ 130

--|--|
--|--|
||||||
|||||| 131

--|--|
--|--|
||||--
||||-- 132

--|--|
--|--|
|||--|
|||--| 133

--|--|
--|--|
||--||
||--|| 134

--|--|
--|--|
||----
||---- 135

--|--|
--|--|
|--|||
|--||| 136

--|--|
--|--|
|--|--
|--|-- 137

--|--|
--|--|
|----|
|----| 138

--|--|
--|--|
--||||
--|||| 139

--|--|
--|--|
--||--
--||-- 140

--|--|
--|--|
--|--|
--|--| 141

--|--|
--|--|
----||
----|| 142

--|--|
--|--|
------
------ 143

----||
----||
||||||
|||||| 144

----||
----||
||||--
||||-- 145

----||
----||
|||--|
|||--| 146

----||
----||
||--||
||--|| 147

----||
----||
||----
||---- 148

----||
----||
|--|||
|--||| 149

----||
----||
|--|--
|--|-- 150

----||
----||
|----|
|----| 151

----||
----||
--||||
--|||| 152

----||
----||
--||--
--||-- 153

----||
----||
--|--|
--|--| 154

----||
----||
----||
----|| 155

----||
----||
------
------ 156

------
------
||||||
|||||| 157

------
------
||||--
||||-- 158

------
------
|||--|
|||--| 159

------
------
||--||
||--|| 160

------
------
||----
||---- 161

------
------
|--|||
|--||| 162

------
------
|--|--
|--|-- 163

------
------
|----|
|----| 164

------
------
--||||
--|||| 165

------
------
--||--
--||-- 166

------
------
--|--|
--|--| 167

------
------
----||
----|| 168

------
------
------
------ 169

||||--
||||||
||||||
||||-- 170

||||--
||||||
||--||
||---- 171

||||--
||||||
|--|||
|--|-- 172

||||--
||||||
--||||
--||-- 173

||||--
||||||
----||
------ 174

||----
||--||
||||||
||||-- 175

||----
||--||
||--||
||---- 176

||----
||--||
|--|||
|--|-- 177

||----
||--||
--||||
--||-- 178

||----
||--||
----||
------ 179

|--|--
|--|||
||||||
||||-- 180

|--|--
|--|||
||--||
||---- 181

|--|--
|--|||
|--|||
|--|-- 182

|--|--
|--|||
--||||
--||-- 183

|--|--
|--|||
----||
------ 184

--||--
--||||
||||||
||||-- 185

--||--
--||||
||--||
||---- 186

--||--
--||||
|--|||
|--|-- 187

--||--
--||||
--||||
--||-- 188

--||--
--||||
----||
------ 189

------
----||
||||||
||||-- 190

------
----||
||--||
||---- 191

------
----||
|--|||
|--|-- 192

------
----||
--||||
--||-- 193

------
----||
----||
------ 194

|||--|
||||||
||||||
|||--| 195

|||--|
||||||
|--|||
|----| 196

|||--|
||||||
--||||
--|--| 197

|----|
|--|||
||||||
|||--| 198

|----|
|--|||
|--|||
|----| 199

|----|
|--|||
--||||
--|--| 200

--|--|
--||||
||||||
|||--| 201

--|--|
--||||
|--|||
|----| 202

--|--|
--||||
--||||
--|--| 203

||----
|||--|
|||--|
||---- 204

||----
|||--|
--|--|
------ 205

------
--|--|
|||--|
||---- 206

------
--|--|
--|--|
------ 207

||--||
||||||
||||||
||--|| 208

||--||
||||||
||||--
||---- 209

||--||
||||||
--||||
----|| 210

||--||
||||||
--||--
------ 211

||----
||||--
||||||
||--|| 212

||----
||||--
||||--
||---- 213

||----
||||--
--||||
----|| 214

||----
||||--
--||--
------ 215

----||
--||||
||||||
||--|| 216

----||
--||||
||||--
||---- 217

----||
--||||
--||||
----|| 218

----||
--||||
--||--
------ 219

------
--||--
||||||
||--|| 220

------
--||--
||||--
||---- 221

------
--||--
--||||
----|| 222

------
--||--
--||--
------ 223

||----
||||||
||||||
||---- 224

||----
||||||
--||||
------ 225

------
--||||
||||||
||---- 226

------
--||||
--||||
------ 227

|----|
||--||
||--||
|----| 228

|--|||
||||||
||||||
|--||| 229

|--|||
||||||
||||--
|--|-- 230

|--|||
||||||
|||--|
|----| 231

|--|--
||||--
||||||
|--||| 232

|--|--
||||--
||||--
|--|-- 233

|--|--
||||--
|||--|
|----| 234

|----|
|||--|
||||||
|--||| 235

|----|
|||--|
||||--
|--|-- 236

|----|
|||--|
|||--|
|----| 237

|--|--
||||||
||||||
|--|-- 238

|----|
||||||
||||||
|----| 239

------
|----|
|----|
------ 240

----||
|--|||
|--|||
----|| 241

----||
|--|||
|--|--
------ 242

------
|--|--
|--|||
----|| 243

------
|--|--
|--|--
------ 244

------
|--|||
|--|||
------ 245

--||||
||||||
||||||
--|||| 246

--||||
||||||
||||--
--||-- 247

--||||
||||||
|||--|
--|--| 248

--||||
||||||
||--||
----|| 249

--||||
||||||
||----
------ 250

--||--
||||--
||||||
--|||| 251

--||--
||||--
||||--
--||-- 252

--||--
||||--
|||--|
--|--| 253

--||--
||||--
||--||
----|| 254

--||--
||||--
||----
------ 255

--|--|
|||--|
||||||
--|||| 256

--|--|
|||--|
||||--
--||-- 257

--|--|
|||--|
|||--|
--|--| 258

--|--|
|||--|
||--||
----|| 259

--|--|
|||--|
||----
------ 260

----||
||--||
||||||
--|||| 261

----||
||--||
||||--
--||-- 262

----||
||--||
|||--|
--|--| 263

----||
||--||
||--||
----|| 264

----||
||--||
||----
------ 265

------
||----
||||||
--|||| 266

------
||----
||||--
--||-- 267

------
||----
|||--|
--|--| 268

------
||----
||--||
----|| 269

------
||----
||----
------ 270

--||--
||||||
||||||
--||-- 271

--||--
||||||
||--||
------ 272

------
||--||
||||||
--||-- 273

------
||--||
||--||
------ 274

--|--|
||||||
||||||
--|--| 275

------
|||--|
|||--|
------ 276

----||
||||||
||||||
----|| 277

----||
||||||
||||--
------ 278

------
||||--
||||||
----|| 279

------
||||--
||||--
------ 280

------
||||||
||||||
------ 281

```

# Answer
> 3 votes
# C, 216 bytes

```
#define M:++B:++B:8;for(k=0
j,k,B;char*c,s[99];main(i){for(i<<=24;i--;B||puts(s)){for(B=k=0;j=i>>k++;)j&1?k%6?j&2?k++M;k^29;k+=6)j=~i>>(k-=k/24*23),j&1?k<18?j&64?k+=6
M,c=s;k<24;++k%6||(*c++=10))*c++=1<<k&i?45:'|';}}

```

Sadly it took over 200 bytes. My approach was to view the grid as 24 bits which can each be either part of a horizontal piece or part of a vertical piece. It generates all `1<<24` combinations and then goes down the rows and columns munching the dominos to see whether each one is valid.

# Answer
> 2 votes
# Python 2: 130 bytes

```
for i in range(4096):
 G=([0]*6+["\n"])*4;exec"b=i%2;j=G.index(0);G[j]=G[(j+7**b)%28]='-|'[b];i/=2;"*12
 if all(G):print"".join(G)

```

I use a different encoding of tilings than has been posted so far, one that is more efficient timewise in that it needs only 12 bits to represent a valid tiling, though in retrospect perhaps not the golfiest one.

If you "read" through the 4x6 grid from left to right, top to bottom, each domino you encounter in order is either vertical or horizontal. (Of course, you encounter each domino twice, but only the first encounter of the top or left corner matters). This gives a sequence of 12 bits.

For example, the tiling

```
——|——|
|||——|
||||——
——||——

```

corresponds to `HVHVVVVHVHHH`.

Conversely, each sequence of 12 corresponds to a unique tiling, created by repeatedly adding a tile of the specified orientation with it's top or right cell as the first unoccupied cell in reading order. Some, though, are not legal tilings because a domino is placed with its other half off the board or overlapping with an existing domino.

The code tries every possible sequence, represented by a `12`-bit number `0` to `4095`, reading off bits one at a time with `%2` and `/2`. The board, initialized with zeroes for empty cells, is stored with rows concatenated into a single list. That way, it's easy to find the first zero element to place the domino. The other domino half is either one row or column down, and so found by adding `1` or `6` to the index. These two cells are filled with the proper character `-` or `|`. This list could have been a string except that Python strings are immutable.

Rather than checking for a collision, we place the dominoes allowing overlaps, and see at the end whether the board is filled by whether any zeroes remain (`all`). We actually make the board 4x7, filling the right row with `\n` for two reasons. The first is that the padding lets horizontal dominoes go off the end without cycling over to the left edge (dominoes that go off the bottom edge *are* wrapped around with `%28`, but that's fine because they overlap with the the first row which has been filled by then). The other reason is so that in a legal configuration, the newlines remain and cause the lines to be printed separately when the characters are joined.

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


title: Pirrational Numbers

text:
# Question
Title: Pirrational Numbers
Pi is an irrational number, which means that its decimal representation never terminates or repeats itself.

Pi truncated to 41 decimal digits (40 places) is `3.1415926535897932384626433832795028841971`.

If we ignore the decimal point and list the digits as a sequence of positive integers, **avoiding duplicates**, we get `3 1 4 15 9 2 6 5 35 8 97 93 23 84 62 64 33 83 27 950 28 841 971` (OEIS A064809).
(Notice that `15` appears in the sequence instead of `1 5` because `1` had already occurred.
Also note that `0` does not occur because it is not positive; `950` contains the first zero.)

To construct the first ***pirrational number*** we use this sequence to index into the digits of Pi (the first digit being 3, the second 1, etc.).

So the first digit of the first pirrational number is the 3rd digit of Pi,
the second digit is the 1st digit of Pi,
the third digit is the 4th digit of Pi,
the fourth is the **15th** digit of Pi,
and so on.
A decimal point is added after the first digit to mimic Pi.

Thus the first pirrational number to 41 digits is `4.3195195867462520687356193644029372991880`.
(Note that for the 30th digit I had to go all the way to the 974th digit of Pi.)

To construct the second pirrational number the process is repeated using the first pirrational number instead of Pi. (Pi itself may be called the zeroth pirrational number.) So the new sequence is `4 3 1 9 5 19 58 ...` and the first piirational number is indexed to produce the second, which starts `9.14858...`.

Further pirrational numbers are created in the same way, each being generated from the one before.

# Challenge

Your task is to write the shortest program possible that takes in two integers, `N` and `D`, and outputs the `N`th pirrational number truncated to `D` decimal digits.

`D` is always positive but `N` is non-negative, and `D` digits of Pi should be output when `N` is 0.
When `D` is 1 it does not matter if the decimal point is present or not.

The input should come from stdin or the command line and output should go to stdout (or your language's closest alternatives).

Your program should work for all input values of `N` and `D` below 216, but it needn't be timely or efficient.

The shortest code in bytes wins.

(Note that pirrational numbers exits in other bases but everything in this challenge is done in base 10.)

# Answer
> 3 votes
# Python 292 bytes

Quite inefficient, I've only been able to get a few digits of N=3 and none of N=4.

```
import sympy
def P(N,D,s=''):
 if N<1:return'3'+`sympy.pi.evalf(D+9)`[2:-9]
 for i in range(D):
    h=[];l='';j=i;x=0
    while-~j:
     x+=1;d=P(N-1,x)[-1];l+=d
     while'1'>P(N-1,x+1)[-1]:x+=1;l+='0'
     if(l in h)<1:h+=[l];l='';j-=1
    s+=P(N-1,int(h[i]))[-1]
 return s
s=P(*input())
print s[0]+'.'+s[1:]

```

Sample input:

```
0,20
3.1415926535897932384

1,20
4.3195195867462520687

2,10
9.148583196

3,5
9.9815

```

# Answer
> 4 votes
# Haskell, 431 400 369

```
import Data.List
g(q,r,t,k,n,l)|4*q+r-t<n*t=n:g(q#0,(r-n*t)#0,t,k,div(r#(30*q))t-n#0,l)|1<2=g(q*k,(2*q+r)*l,t*l,k+1,div(q*(7*k+2)+r*l)(t*l),l+2)
u w@(x:y:xs)=x:v y xs 0 w
v a(r:s)n w|a`elem`take n(u w)||r==0=v(a#r)s n w|1<2=a:v r s(n+1)w
m p=map(genericIndex p.pred)$u p
a#b=a*10+b
(x:s)%n=show x++'.':show(foldl1(#)$n`take`s)
f n d=print$iterate m(g(1,0,1,1,3,3))!!n%d

```

Gotta love infinite lists! Given enough time and memory, this program will eventually calculate the right answer for any N and D (I assume).

I'm generating the digits of pi with `g` using a spigot algorithm (shamelessly stolen from a guy called Stanley Rabinowitz), grouping the digits/creating the sequence using `v` and generating a pirrational number from these using `m`.

Here it is in action:

```
λ> f 0 10
"3.1415926535"
λ> f 1 10
"4.3195195867"
λ> f 2 10
"9.Interrupted. --didn't have the time to wait for this to finish
λ> f 2 4
"9.1485"

```

---
Tags: code-golf, pi
---


# Question
Title: m3ph1st0s's programming puzzle 3 (C): “Easy bug”
This is the 3rd of my series of C/C++ puzzles; in case you missed the first 2 they are here: (1) m3ph1st0s's programming puzzle 1 (C++) (2) m3ph1st0s's programming puzzle 2 (C++): "Call hard!"

I must say that my puzzles are 100% original. If not, I will always state so in the text. My 3rd puzzle has 2 parts as follows:

Puzzle 3.1

This part (3.1) is not an original puzzle of mine, it is collected from some internet page I've read a while ago. I use it here as a starting point and a warm-up for you. Solve this one and then move on to the 2nd part.

Some one tried to print the "+" sign 20 times and came up with the following program:

```
#include <stdio.h>
int main() {
   int i;
   int n = 20;
   for( i = 0; i < n; i-- )
      printf("+");
   return 0;
}

```

The fact that it did not have the expected result is obvious - the program never ends. Fix it! Easy? Now fix the program by changing ONLY ONE CHARACTER - non-space character of course! For this challenge there are 3 solutions. Find all 3 of them. Just to make it clear: the program must output 20 "+" signs and must end fast. Before criticizing me on what "fast" means, I'll say it means at most a couple of seconds (which by the way is too much but just to make it crystal clear).

Puzzle 3.2

**EDITED** ***It was pointed to me earlier that the solution for the 3.2.2 puzzle might be compiler-dependent. In order to eliminate any possible discussion on the subject, I'll modify the idea and improve it on a next puzzle when I'll take extra care not to generate controversy. However, in order to keep this puzzle going, I'll make a small modification for 3.2.2 (the solution will be easier but cleaner).***

When I first saw the puzzle I found it pretty awesome. I did manage to solve it but not immediately since it requires some careful attention. If you are here it means you too solved it. If you did so by writing a program to replace all possible characters with all possible values and test every solution, you are lost. Hard working guy though. Now having corrected the program that writes 20 "+" signs:

3.2.1: Insert **one single letter** and nothing more in the code so that the result is valid and outputs the same thing in all 3 corrected programs. Needless to say, the letter must be before the enclosing } of main (I say that because I don't want to hear people who just put a letter after the program and somehow their compiler was very friendly).

**EDITED (see bellow) - For these final questions consider that the counter i starts from -1 instead of 0.**

3.2.1.5: Repeat all previous problems with the condition that the output is at least 19 "+" signs (but still a finite output). Changing spaces is allowed. Now you might have found more solutions than in the first case. Some of these will most definitely fit for the 3.2.2 question.

3.2.2: Choose another value to initialize the variable n so that the resulting output will remain the same for at least one corrected programs in 3.2.1.5(not necessarily for all of them).

**LAST EDIT1**: changing the program so that it outputs 21 "+" signs is still a good solution, as the original text did not say "exactly" 20 signs. However, the infinite output is forbidden. Obviously this doesn't mean let's all start outputting hundreds of "+"signs since it's not forbidden. But eliminating a beautiful 21 output would not be in the spirit of this competition.

**LAST EDIT2**: considering LAST EDIT1 and **accepting space changing** it seems that now we have 5 possible solutions, four of which have already been pointed out in the responses. The last challenge however hasn't been touched and I must make it clear once more: **n** must be assigned **another value**, solutions that assign 20 to n by some tricks won't do it (like n=20L). Also I prefer to see the 3rd solution that does not change spaces.

**LAST EDIT3**: I've edited the last questions, please read!

The challenge is to solve both parts of the puzzle. The first one to do it wins.

I hope it's all clear, if not please post any questions and I'll edit as quickly as possible. Cheers. *emphasized text*

# Answer
> 8 votes
## 3.1

```
for( i = 0;-i < n; i-- )
for( i = 0; i < n; n-- )
for( i = 0; i + n; i-- )

```

Any of these changes will make the program output 20 '+' signs. This one is close:

```
for( i = 0;~i < n; i-- )

```

It outputs 21 '+' signs.

## 3.2.1

I found at least 112 ways to solve this problem inserting one letter. Not all of them may work on all compilers.

```
int n = 20L;
int n = 20f;
int n = 20d;
uint n = 20;

for( i = 0L; ... )
for( i = 0f; ... )
for( i = 0d; ... )

iprintf("+");
printf("+x");
printf("x+");

```

For the last two, substitute any letter for `x` to give you 104 possible solutions. Using either of the last two lines will change the output, but the output will still be the same for all 3 corrected programs.

## 3.2.2

All I've come up with are some things that get cast back to the number 20 on assignment to `int`.

```
int n = 20L;
int n = 20.001;
int n = 20.999;
int n = 20 + 0x100000000L;

```

# Answer
> 2 votes
3.1

Yet another puzzle. But normal solutions are boring, what about something special?

Solution one:

```
#include <stdio.h>
int main() {
   int i;
   int n = 20;
   for( i = 0; i < n; i++ )
      printf("+");
   return 0;
}

```

I decided to change ONLY ONE CHARACTER, that is, `-`. No characters other than `-` were changed.

Solution two:

```
#include <stdio.h>
int main() {
   int i=printf("++++++++++++++++++++");exit(0);
   int n = 20;
   for( i = 0; i < n; i-- )
      printf("+");
   return 0;
}

```

This changes exactly one character - the semicolon after `int i` into `=printf("++++++++++++++++++++");exit(0);`.

Solution three:

```
#include <stdix.h>
int main() {
   int i;
   int n = 20;
   for( i = 0; i < n; i-- )
      printf("+");
   return 0;
}

```

This loads the `stdix.h` system header. In the system include path, insert the following file, called stdix.h. It has to contain the following contents.

```
static inline void printf(const char *string) {
    int i;
    for(i = 0; i < 20; i--)
        putchar('+');
    exit(0);
}

```

---

3.2

Now to insert one letter. Well, that's simple, replace `int main()` with `int main(a)`. This is not valid according to standards, but who cares?

# Answer
> 0 votes
## Puzzle 3.1 Answers

1. Change `i--` to `n--` (demo: http://ideone.com/l0Y10)
2. Change `i < n` to `i + n` (demo: http://ideone.com/CAqWO)
3. Change `[SPACE]i < n` to `-i < n`. (demo: http://ideone.com/s5Z2r)

## Puzzle 3.2.1

Change `int n = 20` to `int n = 20L` (add an `L` to the end).

## Puzzle 3.2.2

Haven't found an answer yet...

# Answer
> 0 votes
3.1

1. Change `i--` to `n--`
2. `i<n` to `-i<n`
3. (Unfortunately invalid answer because I wasn't checking with compiler before seeing other answers)

3.2.1

```
int n = 20

```

to

```
uint n = 20

```

(Compiler dependent...)

3.2.2

```
int n =-20L;

for(i = -1; i%n; i--)

```

prints 19 + signs, same as with `int n = 20L;`. However, I wouldn't have come up with it if I hadn't seen other answers to 3.2.1

# Answer
> 0 votes
```
#include <stdio.h>
int main() {
   int i;
   int n = 20;
   for( i = 0; i < n; i++  )
      printf("+");
        printf("\n");
   return 0;
}

```

---
Tags: code-challenge, c, c++, programming-puzzle
---


title: Fake the forecast

text:
# Question
Title: Fake the forecast
The new weather predicting supercomputer has arrived, and it doesn't work.

In the meantime your boss wants you to buy the technicians some time by faking the daily wind maps.

**Your task is to draw a grid of arrows representing wind direction.**

The grid is:

* made up of 15px square tiles
* 8 tiles by 8 tiles
* 120px square total
* # 000 background

Each grid tile has 8 potential orientations, representing wind direction:

1. North
2. Northeast
3. East
4. Southeast
5. South
6. Southwest
7. West
8. Northwest

Which must be depicted as follows:

N NE E SE S SW W NW

**The maps must vary gradually**, in order to be believable.

This means each tile may only differ from its neighbour by one step. Specifically:

* A tile can only differ by one increment or decrement from each of the 4 adjoining tiles. (or 3 for side tiles, 2 for corner tiles).
* e.g. a tile with neighbour E could be NE, E or SE (assuming it accords with its other neighbours).
* Orientations can loop back around, i.e. N -\> NW and NW -\> N.

To illustrate, the following map is valid :

```
NW  N NE NE NE NE NE NE
 N NE NE NE NE NE NE  E
NE NE NE NE NE NE  E SE
 E NE NE NE NE  E SE  S
SE  E  E  E  E SE  S SE
 S SE SE SE SE  S SE  E
SW  S  S  S  S SE  E NE
SW SW  S  S SE  E NE  N

```

**Maps must be unique**, don't generate the same map for different inputs.

* Input is an integer corresponding to the days between now and your forecast (e.g. 1 is tomorrow's forecast, 365 is a year's time).
* Output is the map as an image.
* Output should be reproducible, the same input will always give the same output
* You must give unique maps for at least 8 years - i.e. no identical output for any input between 1 and 2920 (I'm ignoring leap years).
* There is no defined output for any input greater than 2920.

The winning submission will produce valid maps (up to day 2920) with the fewest bytes of source code.

# Answer
# BBC Basic, 83 ASCII characters, tokenised filesize 72

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

```
  INPUTn:VDU23,48,516;543;4;0;23,49,783;5,9;0;0:WIDTH8FORi=1TO64PRINT;1ANDn;:n/=2NEXT

```

This is basically a port of Martin's concept, but the implementation in BBC basic is very different. I reprogram the font for the numbers `0` and `1` then output the binary digits of `n` in reverse order.

Ungolfed code is below. In BBC basic you can print individual ASCII characters using the `VDU` command, but the language has a series of machine-specific codes similar to escape sequences but starting with unprintable characters. For reprogramming the font, we start with ASCII 23. Normally 8-bit values are taken, but if you use a semicolon as a separator instead of a comma, it takes 16-bit little endian values (as used in the golfed version.)

```
  INPUTn
  VDU23,48,4,2,31,2,4,0,0,0         :REM redefine font for "0" as an east facing arrow, with an 8x8 bitmap
  VDU23,49,15,3,5,9,0,0,0,0         :REM redefine font for "1" as a northeast facing arrow, with an 8x8 bitmap
  WIDTH8                            :REM set print width to 8 characters
  FORi=1TO64PRINT;1ANDn;:n/=2:NEXT  :REM print the binary digits of n in reverse order from least significant to most significant.

```

**Output**

For the numbers 0 to 7. Note that the font is not reset at the end of the program, hence the numbers 0 and 1 appear as arrows in the first two examples.
> 4 votes

# Answer
# Matlab (182\*)

It is assumed that the input is stored in `n`. hen looking at the algorithm, it is not sure that the results will be unique, but I checked for `n=1 upto 3000` that they are unique and satisfy the rules. I basically just use complex numbers of the unit circle and 'smoothen' them by conv2 with a gaussian filter. After that they get 'rounded' to the 8 possible directions.

\*I know no way how to scale the output to a certain number of pixels, so that has to be done manually=/

*EDIT: I just discovered that there are cases where my checking program didn't recognise wrong solutions (changes by more than 1 step), but I am trying to find another solution.*

Input:

```
n = 1

```

Code:

```
rand('seed',0);
for x=1:n
    b = exp(1i*rand(8)*2*pi);
end
for k=1:12
    b = conv2(b,[1,2,1]'*[1,2,1],'same');b=b./abs(b);
end
c = exp(1i*round(angle(b)*4/pi)*pi/4)/3;
quiver(real(c),imag(c));

```
> 23 votes

# Answer
## Mathematica, ~~116~~ 115 bytes

```
f@n_:=Graphics[Array[(d=n~BitGet~#;Arrow@{1+{w=15#~Mod~8+6.5d,h=15Floor[#/8]},14+{w-13d,h}})&,64,0],ImageSize->120]

```

I suppose a good horse never jumps higher than it has to. 2920 different grids are very easily achieved with using only two directions (I'm using `N` and `NE`), which makes satisfying the continuity rule trivial. I'm simply choosing between N and NE based on the bits of `n`, so this will actually produce 264 different wind maps.

Here are the first ten maps:

PS: My original idea was to enumerate all 84 combinations for the 4 corners and "linearly" interpolation the rest of the grid. That probably would have resulted in nicer maps, but this is code golf after all, so I went with the what fulfils the minimum requirements.
> 15 votes

# Answer
# PHP 5.4, 549 bytes

Somewhat hindered by the need to define arrows as graphics, here is my PHP code:

```
<? $i=$argv[1];$p="R0lGODdhBQAFAIAAAP///wAAACwAAAAABQAFAAAC";$a=[$p."BwRiicGsDwoAOw",$p."CEQeoLfmlhQoADs",$p."CARiF8hnmGABADs",$p."CIwDBouYvGIoADs",$p."BwRil8Gs+QoAOw",$p."CIQRYcqrnkABADs",$p."CARihscYn1YBADs",$p."CAx+Bmq6HWIBADs"];$c=[$i&7,$i>>3&7,$i>>6&7,$i>>9];$m=imagecreate(120,120);imagecolorallocate($m,255,255,255);foreach($a as$_)$z[]=imagecreatefromstring(base64_decode($_));for($y=0;$y<8;$y++)for($x=0;$x<8;$x++)imagecopy($m,$z[($c[0]*(7-$x)*(7-$y)+$c[1]*$x*(7-$y)+$c[2]*(7-$x)*$y+$c[3]*$x*$y)/49%8],$x*15+5,$y*15+5,0,0,5,5);imagepng($m);

```

Takes its argument from the command line, such as:

> `php windmap.php 123`

This solution will use the input as the definition of the four corners. The rest of the map will be smoothly interpolated between values. It has defined results for all values from 0 to 4095, a grand total of ~11.25 years of fake forecast, which should be more than enough time to fix the weather software!

Here's a GIF of all the results:

And a ZIP containing each map can be downloaded here

(Small note: My domain recently expired because I wasn't paying attention. I've renewed it, but the above image and link may not work until the DNS updates)

Unsquishified:

```
<?php
$input = $argv[1];
$prefix = "R0lGODdhBQAFAIAAAP///wAAACwAAAAABQAFAAAC";
$arrows = [
    $prefix."BwRiicGsDwoAOw", // E
    $prefix."CEQeoLfmlhQoADs", // NE
    $prefix."CARiF8hnmGABADs", // N
    $prefix."CIwDBouYvGIoADs", // NW
    $prefix."BwRil8Gs+QoAOw", // W
    $prefix."CIQRYcqrnkABADs", // SW
    $prefix."CARihscYn1YBADs", // S
    $prefix."CAx+Bmq6HWIBADs", // SE
];
$points = [
    $input & 7,
    $input >> 3 & 7,
    $input >> 6 & 7,
    $input >> 9 // input beyond 0o7777 (4095) will be undefined due to lack of & 7 here
];
$img = imagecreate(120,120);
imagecolorallocate($img,255,255,255);
$arrowimgs = [];
foreach($arrows as $src) {
    $arrowimgs[] = imagecreatefromstring(base64_decode($src));
}
for($y=0; $y<8; $y++) {
    for($x=0; $x<8; $x++) {
        $point = (
              $points[0] * (7-$x)/7 * (7-$y)/7
            + $points[1] *   $x  /7 * (7-$y)/7
            + $points[2] * (7-$x)/7 *   $y  /7
            + $points[3] *   $x  /7 *   $y  /7
        ) % 8;
        imagecopy($img,$arrowimgs[$point],$x*15+5,$y*15+5,0,0,5,5);
    }
}
imagepng($img,"out.png");

```
> 5 votes

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


title: The color spelling game

text:
# Question
Title: The color spelling game
In the color spelling game, you are shown a list of color names, but rather than reading the words that are written, you have to say the name of the color of the letters. The game is over as soon as you say the wrong color, and the player who spelled the most words correctly wins. To make the game more challeging, each word is written on a different background color.

And here is your challenge:

Write a program that creates a color spelling game.

* Print every second or so the name of a color.
* Use different colors for the background and the foreground.
* The name of the color you print should be different than both the background and the foreground.
* Do not repeat the same color name, foreground or background color in two consecutive rows. It's still ok to reuse the same color in succession for different purposes, like printing the word "red" after a word on a red background.
* Choose each color (pseudo)randomly from a palette of at least 6 colors.
* Use a programming language of your choice.

Here is my solution for JavaScript, change as you like: http://jsfiddle.net/xb8rqsbr/

This is a code golf challenge, so keep your code short.

Have fun!

# Answer
# BBC Basic, ~~187~~ 176 ASCII characters, tokenised filesize ~~155~~ 140

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

Saved some characters: instead of using MOD to always generate random numbers that differ than the previous value, I simply generate any number and perform a check instead.

```
b=0f=0w=0REPEATc=b g=f x=w REPEATb=RND(6)f=RND(6)w=RND(6)UNTIL(b-f)*(f-w)*(w-b)*(b-c)*(f-g)*(w-x)VDU17,b+128,17,f:PRINTMID$("Red LimeGoldBluePinkAqua",w*4-3,4):WAIT 99UNTIL0

```

I used the original BBC Basic 3-bit colour codings, which are based on 1's bit=Red, 2's bit=Green, 4's bit=Blue. I renamed Yellow as `Gold`, Magenta as `Pink` and Green as `Lime` (justifiable given the shade produced) in order to shorten colour names. I also renamed Cyan as `Aqua` just because. Therefore I use colours 1 to 6 from the 3-bit scheme. I exclude 0=black and 7=white (a very light grey, as the full white belongs to the extended 16-colour set in which the 8\`s bit refers to brightness.)

```
b=0 f=0 w=0                                     :REM initialise "old" values for background, foreground and word.
REPEAT
  c=b g=f x=w                                   :REM c,g and x contain the old values for background, foreground and word.
  REPEAT
    b=RND(6)f=RND(6)w=RND(6)                    :REM pick random numbers between 1 and 6
  UNTIL(b-f)*(f-w)*(w-b)*(b-c)*(f-g)*(w-x)      :REM until all colours are different from each other and their previous values
  VDU17,b+128,17,f,12                           :REM VDU 17 sets colour, using the 128's bit to say if it is foreground or background. VDU 12 clears the screen.
  PRINTMID$("Red LimeGoldBluePinkAqua",w*4-3,4) :REM MID$ picks the colour. The string is considered 1-indexed.
  WAIT 99                                       :REM wait 99 centiseconds
UNTIL0

```

**Output**

The first few images show the program as written, running in screen mode 6. The bottom image shows the program with the `,12` removed so that the screen is not cleared in between word printings. That way it is easier to verify that the colours comply with the rules.
> 3 votes

# Answer
# Algoid - 349

Although Algoid isn't the best for golfing, it's perfect for these types of challenges.

```
set x=math.random;set m;while(true){set c=array{{"black",0},{"brown",6},{"blue",8},{"green",10},{"red",12},{"yellow",14},{"white",15}};set l=c.length();algo.clear();algo.hide();set b=0;set t=0;set w=0;while(b==t||w==t||b==w){b=c[x(l-1)];t=c[x(l-1)];w=c[x(l-1)]}if(m!=w){algo.setColor(t[1]);algo.setBgColor(b[1]);algo.text(w[0]);util.wait(2000);m=w}}

```

## Example outputs
> 2 votes

# Answer
## JavaScript ES6 - 163

Test on Firefox console. I'll try golfing it more later.

```
setInterval(s=>{c="Red0Lime0Gold0Blue0Pink0Aqua".split(0);r=x=>c.splice(~~(Math.random()*9)%c.length,1);console.log('%c'+r(),'background:'+r()+';color:'+r())},999)

```
> 2 votes

# Answer
## Ruby 165

```
x,y,z=9
loop{f,b,t=(0..5).to_a.sample 3
x!=f&&y!=b&&z!=t&&(puts %W{\e[0 \e[3#{f} \e[4#{b} #{%w/black red green brown blue magenta/[t]}}.join ?m
sleep 1
x,y,z=f,b,t)}

```

### Screenshot:
> 1 votes

# Answer
# Python - 260

Not amazing, but it works

```
from random import randint
ps = ['pink','green','yellow','red'];cs=['\033[94m','\033[92m','\033[93m','\033[91m']
print "1 pink, 2 green, 3 yellow, 4 red"
while True:
    c=randint(0,3);p=randint(0,3);g=raw_input(cs[c]+ps[p]+'\033[0m')
    if int(g)!=c+1:
        exit()

```
> 0 votes

---
Tags: code-golf, game
---


title: Un-round fractions

text:
# Question
Title: Un-round fractions
When you convert a fraction to a decimal number and you want to store that number, you often have to round it, because you only want to use a certain amount of memory. Let's say you can only store 5 decimal digits, then 5/3 becomes 1.6667. If you can store only 2 decimal digits it will be 1.7 (now assuming that it is always between 0 and 9.99...).

If you now try to reverse that process with 1.7 and you want to get your fraction back, that can be difficult, since you know that 1.7 is only a rounded number. Of course you can try 17/10 but that is rather an 'ugly' fraction compared to the 'elegant' 5/3.

So the goal is now finding the fraction a/b with the least denominator b, that results in the rounded decimal number when correctly rounded.

## Details

The input contains a string with a number of 1 up to 5 digits that is between 0 (including) and 10 (not including) with a '.' after the first digit. Let's say `n` denotes the number of digits. The output must be a list/array of two integers `[numerator, denominator]` or a rational datatype (you can create your own or use built-in) where the numerator is non-negative and the denominator is positive. The fraction numerator/denominator must be equal to the input when correctly rounded to `n` digits (which means `n-1` digits after the decimal point).

**Restriction: only one loop statement allowed.** This means that you can use only one single looping statement (like `for` or `while` or `goto` etc. as well as functional loops like `map` or `fold` that apply code to every element of a list/array) in your whole code, but you are free to 'abuse' it or use recursion etc.

You should write a function. If your language does not have functions (or even if it does), you can alternatively assume that the input is stored in a variable (or input via stdin) and print the result or write it to a file. The lowest number of bytes wins.

### Rounding

The rounding should follow the 'conventional' rounding rules, i.e. if the last digit that will be cut off is 5 or greater, you will round up, and you will round down for any other cases, so e.g:

4.5494 will result when rounding to

* 1 digit: 5
* 2 digits: 4.5
* 3 digits: 4.55
* 4 digits: 4.549

## Examples

Please include following test cases and other 'interesting' ones:

```
Input 1.7     Output 5/3
Input 0.      Output 0/1
Input 0.001   Output 1/667
Input 3.1416  Output 355/113

```

# Answer
> 4 votes
# CJam, ~~41~~ ~~40~~ 36 bytes

```
Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@

```

Asuumes the input string is stored in Q, which is explicitly allowed by the question. Try it online.

### Test cases

```
$ for d in 1.7 0. 0.001 3.1416; do cjam <(echo "\"$d\":Q;
> Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@
> "); echo; done
5/3
0/1
1/667
355/113

```

### How it works

```
Q'./1=,:L  " Count the number of characters after the dot and store it in L.     ";
0\         " Push 0 (denominator) and swap it with L (dummy value).              ";
{          "                                                                     ";
  ;        " Discard the topmost item from the stack (numerator or dummy value). ";
  )        " Increment the denominator.                                          ";
  _Qd*mo   " Multiply a copy by Double(Q) and round.                             ";
  _d2$/    " Cast a copy to Double and it divide it by the denominator.          ";
  LmO      " Round to L digits.                                                  ";
  Qd       " If the result is not Double(Q),                                     ";
}g         " repeat the loop.                                                    ";
./@        " Push a slash and rotate the denominator on top of it.               ";

```

# Answer
> 15 votes
## T-SQL 254

While T-SQL isn't really suited to this sort of thing, it wa fun to try. The performance gets real bad the higher the denominator. It is limited to a denominator of 1000.

Input is a float variable @

```
WITH e AS(SELECT *FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)),t AS(SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N FROM e a,e b,e c,e d)SELECT TOP 1concat(n.n,'/',d.n)FROM t d,t n WHERE round(n.n/(d.n+.0),len(parsename(@,1)))=@ ORDER BY d.n,n.n

```

A breakdown of the query

```
WITH                                      -- Start CTE(Common Table Expression)
 e AS(                                    --Create a set of 10 rows
   SELECT *
   FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)
 ),
 t AS(
   SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N
   FROM e a,e b,e c,e d                   --Cross join e to produce 1000 numbered rows
 )
SELECT
  TOP 1                                   --Grab first result
  concat(n.n,'/',d.n)                     --Build output
FROM t d,t n                              --Cross join t against itself for denominator and numerator
WHERE round(
  n.n/(d.n+.0),                           --Force float division with +.0
  len(parsename(@,1))                     --Get rounding length
  )=@                                     --Filter where the rounded result = input
ORDER BY d.n,n.n                          --Order by denominator then numerator

```

# Answer
> 12 votes
# Haskell, ~~62~~ 59

if only the names weren't so long...

```
import Data.Ratio
f s=approxRational(read s)$50/10^length s

```

this is a function returning a `Rational` value.

**explanation:** the function `approxRational` is a function which takes a float number and a float epsilon and returns the most simple rational which is in distance epsilon of the input. basically, returns the most simple approximation of the float to a rational in a "forgivable error" distance.

let's exploit this function for our use. for this we will need to figure out what is the area of the floats that round up to the given number. then getting this into the `approxRational` function will get us the answer.

let's try 1.7, for example. the lowest float that rounds to 1.7 is 1.65. any lower will not round to 1.7. similarly, the upper bound of the floats that round to 1.7 is 1.75.
both limits are the bounds are the input number +/- 0.05. it can be easily shown that this distance is always `5 * 10 ^ -(the length of the input - 1)` (the -1 is because there is always a '.' in the input). from here the code is quite simple.

**test cases:**

```
*Main> map f ["1.7", "0.001", "3.1416"]
[5 % 3,1 % 667,355 % 113]

```

unfortunately it doesn't work on "0." because Haskell's parser function doesn't recognize a `.` at the end of a float. this can be fixed for 5 bytes by replacing `read s` by `read$s++"0"`.

# Answer
> 7 votes
## Ruby, ~~127~~ 125 bytes

```
f=->n{b=q=r=(m=n.sub(?.,'').to_r)/d=10**p=n.count('0-9')-1
b=r if(r=(q*d-=1).round.to_r/d).round(p).to_f.to_s==n while d>1
b}

```

Defines a function `f` which returns the result as a `Rational`. E.g. if you append this code

```
p f["1.7"]
p f["0."]
p f["0.001"]
p f["3.1416"]

```

You get

```
(5/3)
(0/1)
(1/667)
(355/113)

```

The loop is over denominators. I'm starting with the full fraction, e.g. `31416/10000` for the last example. Then I'm decrementing the denominator, proportionally decrement the numerator (and round it). If the resulting rational rounds to the same as the input number, I'm remembering a new best fraction.

# Answer
> 5 votes
# Python 2.7+, 111 characters

Proof that you can write horrible code in any language:

```
def f(s):
 t,e,y=float(s),50*10**-len(s),1;n=d=x=0
 while x|y:n,d=n+x,d+y;a=1.*n/d;x,y=a<t-e,a>t+e
 return n,d

```

## Output

```
>>> [f(s) for s in ("1.7", "0.", "0.001", "3.1416")]
[(5, 3), (0, 1), (1, 667), (355, 113)]

```

# Answer
> 4 votes
## Mathematica, 49 53 characters

```
Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@

```

Usage:

```
Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@"1.7"

```

Output:

```
5/3

```

Test cases:

```
input: 1.7     output: 5/3
input: 0.      output: 0
input: 0.001   output: 1/999
input: 3.1416  output: 355/113

```

The 0.001 case strikes me as odd; as the rationalize function didn't work according to its description, when it didn't find the 1/667 case. It should output the number with the smallest denominator that is within specified bounds.

# Answer
> 3 votes
## APL, 50

```
2↑⍎⍕(⍎x←⍞){50>|(10*⍴x)×⍺-⍵÷⍨n←⌊.5+⍺×⍵:n ⍵⋄''}¨⍳1e5

```

As long as you don't count `eval` and `toString` as loops

**Explanation**

The approach is to iterate over 1 to 10000 as denominator and calculate the numerator that most closely match the float, then check if the error is within bounds. Lastly, select the smallest pair from all the fractions found.

`(⍎x←⍞)` Take string input from screen, assign to `x`, and eval
`⍳1e5` Generate array from 1 to 10000
`{...}¨` For each element of the array, call function with it and `(⍎x←⍞)` and arguments **(loop)**

`⍺×⍵` Multiply the arguments
`⌊.5+` Round off (by adding 0.5 then rounding down)
`n←` Assign to `n`
`⍺-⍵÷⍨` Divide by right argument, then subtract from left argument
`(10*⍴x)×` Multiply by 10 to the power of "length of `x`"
`|` Take absolute value
`50>` Check if less than 50 (length of `x` is 2 more than the no. of d.p., so use 50 here instead of 0.5)
`:n ⍵⋄''` If the previous check returns true, then return the array of `n` and the right argument, else return empty string.

`⍎⍕` `toString` and then `eval` to get an array of all the numbers in the array
`2↑` Select only the first 2 elements, which is the first numerator-denominator pair found

# Answer
> 2 votes
# BC, ~~151~~ 148 bytes

# Edit - faster and shorter version

```
define f(v){s=scale(x=v);for(i=r=1;i<=10^s;i+=1){t=v*i+1/2;scale=0;p=t/=1;scale=s+1;t=t/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=p;d=i}}}

```

same test case.

A lot is similar to the previous version, but instead of trying all possible n / d combinations, we hill-climb over the residues of v and backward quotients of multiples m==v\*d and denominators d. Again the precision of the computation is the same.

Here is it untangled:

```
define f(v)
{
    s= scale(x=v)
    for( i=r=1; i <= 10^s; i+=1 ){
        t= v * i +1/2
        scale=0
        m=t/=1 # this rounded multiple becomes nominator if
               # backward quotient is first closest to an integer
        scale=s+1
        t= t / i +10^-s/2 # divide multiple back by denominator, start rounding again...
        scale=s
        t= t/1 - v # ...rounding done. Signed residue of backward quotient
        if( (t*= -1^(t < 0)) < r ){
            r=t
            n=m
            d=i
        }
    }
}

```

This version really has a mere single loop and does only $\Theta\left(\operatorname{fractional\_decimals}(v)\right)$ arithmetic operations.

# Original - slow version

This functions computes the smallest nominator n and denominator d such that the fraction n / d rounded to fractional\_decimals(v) digits is equal to a given decimal value v.

```
define f(v){s=scale(v);j=0;for(i=r=1;j<=v*10^s;){scale=s+1;t=j/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=j;d=i};if((i+=1)>10^s){i=1;j+=1}};v}

```

test case:

```
define o(){ print "Input ",x,"\tOutput ",n,"/",d,"\n" }
f(1.7); o()
> 0
> Input 1.7       Output 5/3
> 0
f(0.); o()
> 0
> Input 0 Output 0/1
> 0
f(0.001); o()
> 0
> Input .001      Output 1/667
> 0
f(3.1416); o()
> 0
> Input 3.1416    Output 355/113
> 0

```

And here is it untangled:

```
define f(v)
{
    s=scale(x=v) # save in global for later print
    j=0
    # do a full sequential hill-climb over the residues r of v and all possible
    # fractions n / d with fractional_decimals(v) == s precision.
    for( i=r=1; j <= v * 10^s; ){
        scale=s+1
        t= j / i +10^-s/2 # start rounding...
        scale=s
        t= t/1 - v # ...rounding done. New residue, but still signed
        if( (t*= -1^(t < 0)) < r ){ # absolute residue better?
            # climb hill
            r=t
            n=j
            d=i
        }
        if( (i+=1) > 10^s ){ # next inner step. End?
            # next outer step
            i=1
            j+=1
        }
    }
    v
}

```

I admit, I cheated a little by emulating a second inner loop inside a single outer loop, but without using any further loop statements. And that's why it actually does $\Theta\left(v \operatorname{fractional\_decimals}(v)^2\right)$ arithmetic operations.

# Answer
> 2 votes
# GNU dc, 72 bytes

No loops - dc doesn't even have them. Instead the control comes from a single tail-recursive macro - idiomatic for dc.

```
?dXAr^d2*sf*sq1sd0[ld1+sd]sD[r1+r]sN[dlf*ld/1+2/dlq>Ndlq<Dlq!=m]dsmxpldp

```

## Output:

```
$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; dc unround.dc <<< $n; done
    n = 1.7:
5
3
    n = 0.:
0
1
    n = 0.001:
1
667
    n = 3.1416:
355
113
$

```

Phew. Partial explanation in this answer.

# Answer
> 2 votes
# Mathematica, 111 characters

```
f=Module[{a=0,b=1,k},While[Round[a/b,10^-(StringLength[#]-2)]!=(k=ToExpression)@#,If[N[a/b]>k@#,b++,a++]];a/b]&

```

Pretty simple really, and I don't think it converges anywhere as fast as the other solutions, since the numerator and denominator only increment by one. I mostly wanted to find the simple solution to this. I'll have to see the other answers and see what clever stuff happens there.

## Output

```
f/@{"1.7","0.0","0.001","3.1416","3.14"}
{5/3, 0, 1/667, 355/113, 22/7}

```

Does anyone here celebrate Pi Approximation Day?

# Answer
> 2 votes
# Applescript, \>300 bytes

I wanted to do this in a language that natively does the type of rounding required. Turns out Applescript fits the bill. Then I saw the enum `rounding as taught in school`, and couldn't resist the using it, despite the blatant uncompetitiveness of Applescript for golfing purposes:

```
on u(q)
    set n to 0
    set d to 1
    set x to 0
    set AppleScript's text item delimiters to "."
    set f to 10 ^ (q's text item 2's length)
    repeat until x = q as real
        set x to (round n * f / d rounding as taught in school) / f
        if x < q then set n to n + 1
        if x > q then set d to d + 1
    end repeat
    return {n, d}
end u

log my u("1.7")
log my u("0.")
log my u("0.001")
log my u("3.1416")

```

This can be golfed a bit more, but probably not worth it.

### Output:

```
(*5, 3*)
(*0, 1*)
(*1, 667*)
(*355, 113*)

```

# Answer
> 1 votes
# C, 233

This works by calling a rationalization function r() with a starting denominator of 1. The function begins incrementing a numerator, and checking at every increment whether the resulting number, when rounded to the same number of digits as the original, has the same string representation as the original. Once the numerator has been incremented so much that the result is greater than the original, the function increments the denominator and calls itself.

This of course uses much more code, but I think the spirit of the problem exonerates this bare-bones approach; for all we know, the internal rationalize() functions of modern languages have lots of internal loops.

Note that this doesn't work for an input of "0." because that is not a standard way to write a float, so when it re-writes the float to string, the result will never be a "0.".

The specs want a function that returns values instead of just printing to screen, hence the argument-passing.

Code (ungolfed):

```
void r(char* x, int* a, int* b) {
    int i = -1;
    char z[32];
    double v =atof(x);
    while(1) {
        i++;
        double y = ((double)i)/((double)(*b));
        double w;
        sprintf(z, "%.*f", strlen(strchr(x,'.'))-1, y);
        if(strcmp(x, z)==0) {
            *a = i;
            return;
        }
        w = atof(z);
        if(w > v) {
            (*b)++;
            r(x, a, b);
            return;
        }
    }
}

```

Usage:

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

int main(int argc, char* argv[]) {
    int num;
    int denom = 1; // start with a denominator of 1
    r(argv[1], &num, &denom);
    printf("%d/%d\n", num, denom);
    return 0;
}

```

Golfed code:

```
typedef double D;
void r(char*x,int*a,int*b){int i=-1;char z[32];D v=atof(x);while(1){i++;D y=((D)i)/((D)(*b));D w;sprintf(z,"%.*f",strlen(strchr(x,'.'))-1,y);if(!strcmp(x,z)){*a=i;return;}w=atof(z);if(w>v){(*b)++;r(x,a,b);return;}}}

```

# Answer
> 1 votes
# Pure Bash, 92 bytes

As a partial explanation for this answer, here it is ported to bash:

```
f=${1#*.}
q=${1//.}
for((n=0,d=1;x-q;x=2*10**${#f}*n/d+1>>1,n+=x<q,d+=x>q));{ :;}
echo $n/$d

```

Notably:

* bash has integer-only arithmetic. So we appropriately scale everything up by 2\*10^(number of fractional digits).
* bash rounds *down* to nearest integer; the 2 in the expression above is so we can instead round to nearest integer (*up or down*).
* Just one loop
* we check if the rational overshoots or undershoots the decimal and increment the denominator or numerator accordingly.

### Output:

```
$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; ./unround.sh $n; done
    n = 1.7:
5/3
    n = 0.:
0/1
    n = 0.001:
1/667
    n = 3.1416:
355/113
$

```

# Answer
> 1 votes
# JavaScript (E6) 85

```
F=r=>(l=>{for(n=r,d=1;l&&r!=((n=r*d+1/2|0)/d).toFixed(l);d++);})(r.length-2)||[n|0,d]

```

**Ungolfed**

```
F=r=>{
  l = r.length-2; // decimal digits
  if (l==0) return [r|0, 1] // if no decimal return the same (conv to number) with denominator 1

  // loop for increasing denominator
  for(d = 2;
      r != ( // loop until find an equal result
      // given R=N/D ==> N=R*D
      (n=r*d+1/2|0) // find possible numerator, rounding (+0.5 and trunc)
      /d).toFixed(l); // calc result to given decimals
      d++);
  return [n,d]
}

```

**Test** In FireFox/FireBug console

```
;["1.7","0.","0.001","3.1416","9.9999"].forEach(v => console.log(v,F(v)))

```

*Output*

```
1.7 [5, 3]
0. [0, 1]
0.001 [1, 667]
3.1416 [355, 113]
9.9999 [66669, 6667]

```

---
Tags: code-golf, math, restricted-source, arithmetic, rational-numbers
---


title: How long is your (language) snake?

text:
# Question
Title: How long is your (language) snake?
Following on from the third order quine challenge, your task is to write an Ouroboros program that uses as many languages as possible.

That is, in language A, write a program pA which outputs program pB in language B. Program pB should output program pC in language C, and so on until eventually a program outputs the original program pA in language A.

No two languages in your loop can be the same or subsets or supersets of each other. **None of the programs in the loop may be identical.**

The longest chain of languages win. The length of the source code will be the tie-breaker.

Here is an example solution of length 3 given by Ventero.

```
s='print q<puts %%q{s=%r;print s%%s}>';print s%s

```

with Python generates this Perl snippet

```
print q<puts %q{s='print q<puts %%q{s=%r;print s%%s}>';print s%s}>

```

which generates the following Ruby code

```
puts %q{s='print q<puts %%q{s=%r;print s%%s}>';print s%s}

```

which then prints the original Python snippet:

```
s='print q<puts %%q{s=%r;print s%%s}>';print s%s

```

# Answer
> 8 votes
Here's a loop of 4 languages:

C -\> Bash -\> Batch -\> Python -\> C

C

```
main(){char *c="echo %cecho print %cmain(){char *c=%c%c%s%c%c;printf(c,34,39,92,34,c,92,34,39,34);}%c%c";printf(c,34,39,92,34,c,92,34,39,34);}

```

Bash

```
echo "echo print 'main(){char *c=\"echo %cecho print %cmain(){char *c=%c%c%s%c%c;printf(c,34,39,92,34,c,92,34,39,34);}%c%c\";printf(c,34,39,92,34,c,92,34,39,34);}'"

```

Batch

```
echo print 'main(){char *c="echo %cecho print %cmain(){char *c=%c%c%s%c%c;printf(c,34,39,92,34,c,92,34,39,34);}%c%c";printf(c,34,39,92,34,c,92,34,39,34);}'

```

Python

```
print 'main(){char *c="echo %cecho print %cmain(){char *c=%c%c%s%c%c;printf(c,34,39,92,34,c,92,34,39,34);}%c%c";printf(c,34,39,92,34,c,92,34,39,34);}'

```

---
Tags: code-challenge, quine
---


title: Rotate a Block of Text

text:
# Question
Title: Rotate a Block of Text
## Rules

* Write a program in a language of your choice.
* That program is designed to rotate a block of text. Example:

```
BOB   90 deg  DCB
CAT    -->    OAO
DOG    CW     GTB

```
* You may assume the blocks of text are loaded into a variable `block`.
* You may assume a square block, but of any size.
* You may assume the line-endings are `\n`.
* You're not allowed to use a library that already rotates blocks of text.
* Code Golf rules, shortest program wins.

# Answer
> 2 votes
# GolfScript, 11 characters

```
n/-1%zip n*

```

Explanation:

```
n/  # split on newline
-1% # reverse array
zip # "rotate" (will turn ['abc' 'def' 'ghi'] into ['adg' 'beh' 'cfi'])
n*  # join with newline again

```

# Answer
> -4 votes
# Python, 0 bytes

My program rotates the block of text by 720 degrees.

---
Tags: code-golf
---


title: Play the Chaos Game

text:
# Question
Title: Play the Chaos Game
The Chaos Game is a simple method to generate fractals. Given a starting point, a length ratio *r* and a set of 2D points, repeatedly do the following:

* From your set of points, pick one at random (uniformly).
* Average that point and the last drawn point (or the starting point) using *r* and *1 - r* as the weights (i.e. *r = 0* means you get the starting point, *r = 1* means you get the random point and *r = 0.5* means you get the point halfway in between.)
* Draw the resultant point.

For instance, if you picked the vertices of an equilateral triangle and *r = 0.5*, the plotted points would map out a Sierpinski triangle:

Image found on Wikipedia

You're to write a program or function which "plays" the chaos game to create a fractal.

## Input

You may write either a program or a function, and take following inputs via ARGV, STDIN or function argument:

* The number of points to plot.
* The starting coordinate (which has to be plotted, too!).
* The averaging weight *r* in the interval *\[0,1\]*.
* A list of points to choose from.

## Output

You may render on screen or write an image file. If the result is rasterised, it needs to be at least 600 pixels on each side, all points must be on the canvas, and at least 75% of the horizontal and vertical extent of the image must be used for points (this is to avoid answers with a single black pixels saying "it's really far zoomed out"). The *x* and *y* axis must be on the same scale (that is the line from (0,0) to (1,1) must be at a 45 degree angle) and each point plotted in the chaos game must be represented as a single pixel (if your plotting method anti-aliases the point, it may be spread over 2x2 pixels).

Colours are your choice, but you need at least two distinguishable colours: one for the background and one for the dots plotted during the chaos game. You may but don't have to plot the input points.

Please include *three* interesting example outputs in your answer.

## Scoring

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

**Edit:** You no longer need to plot the input points, as they aren't really visible as single pixels anyway.

# Answer
> 8 votes
# Mathematica, 89

```
f[n_,s_,r_,p_]:=Graphics@{AbsolutePointSize@1,Point@NestList[#-r#+r RandomChoice@p&,s,n]}

f[10000, {0, 0}, .5, {{-(1/2), Sqrt[3]/2}, {-(1/2), -(Sqrt[3]/2)}, {1, 0}}]

```

## How it works

In Mathematica the `Graphics[]` function produces scalable graphics, you render it to whatever size you want by simply dragging the picture corners. In fact, the initial size of all displayed graphics is a ".ini" setting that you may set at 600 or at any other value you wish. So there is no need to do anything special for the 600x600 requirement.

The `AbsolutePointSize[]` thing specifies that the point size will not be modified by enlarging the image size.

The core construct is

```
 NestList[#-r#+r RandomChoice@p&,s,n]

```

or in non-golfed pseudo-code:

```
 NestList[(previous point)*(1-r) + (random vertex point)*(r), (start point), (iterations)]

```

It is recursively building a list starting from `(start point)` and applying the (vectorial) function in the first argument to each successive point, finally returning the list of all calculated points to be plotted by `Point[]`

## Some self-replication examples:

```
Grid@Partition[Table[
   pts = N@{Re@#, Im@#} & /@ Table[E^(2 I Pi r/n), {r, 0, n - 1}];
   Framed@f[10000, {0, 0}, 1/n^(1/n), pts], {n, 3, 11}], 3]

```

# Answer
> 9 votes
# Java : 246 ~~253~~ ~~447~~

As a function `m()`:

```
void m(float[]a){new java.awt.Frame(){public void paint(java.awt.Graphics g){int i=0,x=i,y=i,v;for(setSize(832,864),x+=a[1],y+=a[2];i++<=a[0];v=a.length/2-2,v*=Math.random(),x+=(a[v+=v+4]-x)*a[3],y+=(a[v+1]-y)*a[3])g.drawLine(x,y,x,y);}}.show();}

```

Line breaks (within a program to show usage):

```
class P{
    public static void main(String[]a){
        new P().m(new float[]{1000000,            // iterations
                              416,432,            // start
                              0.6f,               // r
                              416,32,16,432,      // point list...
                              416,832,816,432,
                              366,382,366,482,
                              466,382,466,482});
    }

    void m(float[]a){
        new java.awt.Frame(){
            public void paint(java.awt.Graphics g){
                int i=0,x=i,y=i,v;
                for(setSize(832,864),x+=a[1],y+=a[2];
                    i++<=a[0];
                    v=a.length/2-2,v*=Math.random(),
                    x+=(a[v+=v+4]-x)*a[3],
                    y+=(a[v+1]-y)*a[3])
                    g.drawLine(x,y,x,y);
            }
        }.show();
    }
}

```

Drawing input points was removed from the requirements (yay 80 bytes!). They're still shown in the old screenshots below, but won't show up if you run it. See revision history if interested.

The inputs are given as an array of floats. The first is iterations, the next two are starting `x y`. Fourth is `r`, and last comes the list of coordinates, in `x1 y1 x2 y2 ...` fashion.

**Ninja Star**

```
1000000 400 400 0.6 400 0 0 400 400 800 800 400 350 350 350 450 450 350 450 450

```

**Cross**

```
1000000 400 400 0.8 300 0 500 0 500 300 800 300 800 500 500 500 500 800 300 800 300 500 0 500 0 300 300 300

```

**Octochains**

```
1000000 400 400 0.75 200 0 600 0 800 200 800 600 600 800 200 800 0 600 0 200

```

# Answer
> 8 votes
# JavaScript (E6) + Html 173  ~~176 193~~

Edit: big cut, thanks to William Barbosa

Edit: 3 bytes less, thanks to DocMax

173 bytes counting the function and the canvas element needed to show the output.

**Test** save as html file and open in FireFox.

JSFiddle

---

---

---

---

```
<canvas id=C>
<script>
F=(n,x,y,r,p)=>{
  for(t=C.getContext("2d"),C.width=C.height=600;n--;x-=(x-p[i])*r,y-=(y-p[i+1])*r)
    i=Math.random(t.fillRect(x,y,1,1))*p.length&~1
}
F(100000, 300, 300, 0.66, [100,500, 500,100, 500,500, 100,100, 300,150, 150,300, 300,450, 450,300]) // Function call, not counted
</script>

```

# Answer
> 6 votes
# Python - ~~200~~ 189

```
import os,random as v
def a(n,s,r,z):
    p=[255]*360000
    for i in[1]*(n+1):
        p[600*s[0]+s[1]]=0;k=v.choice(z);s=[int(k[i]*r+s[i]*(1-r))for i in(0,1)]
    os.write(1,b'P5 600 600 255 '+bytes(p))

```

Takes input as function arguments to a, writes result to stdout as pgm file. `n` is iterations, `s` is starting point, `r` is r, and `z` is list of input points.

Edit: No longer draws input points in gray.

## Interesting outputs:

```
Iterations: 100000
Starting Point: (200, 200)
r: 0.8
Points: [(0, 0), (0, 599), (599, 0), (599, 599), (300, 300)]

```

---

```
Iterations: 100000
Starting Point: (100, 300)
r: 0.6
Points: [(0, 0), (0, 599), (599, 0), (300, 0), (300, 300), (0, 300)]

```

---

```
Iterations: 100000
Starting Point: (450, 599)
r: 0.75
Points: [(0, 0), (0, 300), (0, 599), (300, 0), (599, 300), (150, 450)]

```

# Answer
> 6 votes
# Python, ~~189~~ ~~183~~ 175

**Edit:** fixed the inversed *r* ratio, and switched to B&W image in order to save a few bytes.

Takes the number of points as `n`, first point as `p`, ratio as `r` and list of points as `l`. Needs the module Pillow.

```
import random,PIL.Image as I
s=850
def c(n,p,r,l):
    i=I.new('L',(s,s));x,y=p;
    for j in range(n):w,z=random.choice(l);w*=r;z*=r;x,y=x-x*r+w,y-y*r+z;i.load()[x,s-y]=s
    i.show()

```

Examples:

I am generating points in circle around the image's center

```
points = [(425+s*cos(a)/2, 425+s*sin(a)/2) for a in frange(.0, 2*pi, pi/2)]
c(1000000, (425, 425), 0.4, points)

```

XOXO repetitions, just changing ratio from 0.4 to 0.6

Some sort of snow flake

```
stars = [(425+s*cos(a)/2,425+s*sin(a)/2) for a in frange(.0,2*pi, pi/4)]
c(1000000, (425, 425), 0.6, stars)

```

# Answer
> 6 votes
## SuperCollider - 106

SuperCollider is a language for generating music, but it can do graphics at a pinch.

```
f={|n,p,r,l|Window().front.drawHook_({{Pen.addRect(Rect(x(p=l.choose*(1-r)+(p*r)),p.y,1,1))}!n;Pen.fill})}

```

I've used some obscure syntax shortcuts to save a few bytes - a more readable and more memory-efficient version is

```
f={|n,p,r,l|Window().front.drawHook_({n.do{Pen.addRect(Rect(p.x,p.y,1,1));p=l.choose*(1-r)+(p*r)};Pen.fill})}

```

at 109 chars.

As with the Mathematica example, you have to manually resize the window to get 600x600 pixels. You have to wait for it to re-draw when you do this.

This generates a basic Sierpinsky triangle (not shown because you've seen it before)

```
f.(20000,100@100,0.5,[0@600,600@600,300@0])

```

This makes a kind of Sierpinsky pentagon type thing:

```
f.(100000,100@100,1-(2/(1+sqrt(5))),{|i| (sin(i*2pi/5)+1*300)@(1-cos(i*2pi/5)*300)}!5)

```

The same thing with 6 points leaves an inverted Koch snowflake in the middle:

```
f.(100000,100@100,1/3,{|i| (sin(i*2pi/6)+1*300)@(1-cos(i*2pi/6)*300)}!6)

```

Finally, here's a riff on the 3D pyramids from ace's answer. (Note that I've used one of the points twice, to get the shading effect.)

```
f.(150000,100@100,0.49,[300@180, 0@500,0@500,350@400,600@500,250@600])

```

# Answer
> 4 votes
# JavaScript (407) (190)

I'm happy to get any feedback on my script and on golfing since I am not comfortable with JS=) (Feel free to use this/change it for your own submission!)

**Reading Input** (To be comparable to edc65's entry I do not count the the input.):

```
p=prompt;n=p();[x,y]=p().split(',');r=p();l=p().split(';').map(e=>e.split(','));

```

**Canvas Setup & Calculation**

```
d=document;d.body.appendChild(c=d.createElement('canvas'));c.width=c.height=1000;c=c.getContext('2d');
for(;n--;c.fillRect(x,y,2,2),[e,f]= l[Math.random()*l.length|0],x-=x*r-e*r,y-=y*r-f*r);

```

Somewhat more ungolfed (including an example input where the real input promts are just commented out, so ready to use):

```
p=prompt;
n=p('n','4000');
[x,y]=p('start','1,1').split(',');
r=p('r','0.5');
l=p('list','1,300;300,1;300,600;600,300').split(';').map(e=>e.split(','));d=document;
d.body.appendChild(c=d.createElement('canvas'));
c.width=c.height=1000;c=c.getContext('2d');
for(;n--;c.fillRect(x,y,2,2),[e,f]= l[Math.random()*l.length|0],x-=x*r-e*r,y-=y*r-f*r);

```

## Examples

```
for(k = 0; k<50; k++){
rad = 10;
l.push([350+rad*k*Math.cos(6.28*k/10),350+rad*k*Math.sin(6.28*k/10)]);
}
r = 1.13;

```

```
r = 0.5;list = [[1,1],[300,522],[600,1],[300,177]];

```

```
r = 0.5
list = [[350+350*Math.sin(6.28*1/5),350+350*Math.cos(6.28*1/5)],
[350+350*Math.sin(6.28*2/5),350+350*Math.cos(6.28*2/5)],
[350+350*Math.sin(6.28*3/5),350+350*Math.cos(6.28*3/5)],
[350+350*Math.sin(6.28*4/5),350+350*Math.cos(6.28*4/5)],
[350+350*Math.sin(6.28*5/5),350+350*Math.cos(6.28*5/5)],

[350+90*Math.sin(6.28*1.5/5),350+90*Math.cos(6.28*1.5/5)],
[350+90*Math.sin(6.28*2.5/5),350+90*Math.cos(6.28*2.5/5)],
[350+90*Math.sin(6.28*3.5/5),350+90*Math.cos(6.28*3.5/5)],
[350+90*Math.sin(6.28*4.5/5),350+90*Math.cos(6.28*4.5/5)],
[350+90*Math.sin(6.28*5.5/5),350+90*Math.cos(6.28*5.5/5)]];

```

# Answer
> 3 votes
## Processing, 153

Ported @Geobits' Java answer to Processing and did some more golfing, resulting in a reduction of 100 chars. I originally intended to animate the process, but the input constraints are too harsh on this (Processing does not have stdin or argv, which means that I must write my own function instead of using Processing's native `draw()` loop).

```
void d(float[]a){int v;size(600,600);for(float i=0,x=a[1],y=a[2];i++<a[0];v=(int)random(a.length/2-2),point(x+=(a[v*2+4]-x)*a[3],y+=(a[v*2+5]-y)*a[3]));}

```

Complete program with line breaks:

```
void setup() {
  d(new float[]{100000,300,300,.7,0,600,600,0,600,600,0,0,400,400,200,200,400,200,200,400});
}
void d(float[]a){
  int v;
  size(600,600);
  for(float i=0,x=a[1],y=a[2];
      i++<a[0];
      v=(int)random(a.length/2-2),point(x+=(a[v*2+4]-x)*a[3],y+=(a[v*2+5]-y)*a[3]));
}

```

Above program gives Crosses:

```
d(new float[]{100000,300,300,.65,142,257,112,358,256,512,216,36,547,234,180,360});

```

This gives Pyramids:

```
d(new float[]{100000,100,500,.5,100,300,500,100,500,500});

```

This gives Sierpinski triangle:

# Answer
> 1 votes
## Ungolfed "reference implementation", Python

**Update**: much, much faster (by orders of magnitude)

**Check out the interactive shell!**

Edit the file and set `interactive` to `True`, then do one of these:

`polygon numberOfPoints numeratorOfWeight denominatorOfWeight startX startY numberOfSides` generates, saves and displays a polygon.

`points numberOfPoints numeratorOfWeight denominatorOfWeight startX startY point1X point1Y point2X point2Y ...` does what the spec asks for.

```
import matplotlib.pyplot as plt
import numpy as np
from fractions import Fraction as F
import random
from matplotlib.colors import ColorConverter
from time import sleep
import math
import sys
import cmd
import time

def plot_saved(n, r, start, points, filetype='png', barsize=30, dpi=100, poly=True, show=False):
    printed_len = 0

    plt.figure(figsize=(6,6))
    plt.axis('off')

    start_time = time.clock()
    f = F.from_float(r).limit_denominator()

    spts = []
    for i in range(len(points)):
        spts.append(tuple([round(points[i].real,1), round(points[i].imag,1)]))

    if poly:
        s = "{}-gon ({}, r = {}|{})".format(len(points), n, f.numerator, f.denominator)
    else:
        s = "{} ({}, r = {}|{})".format(spts, n, f.numerator, f.denominator)

    step = math.floor(n / 50)

    for i in range(len(points)):
        plt.scatter(points[i].real, points[i].imag, color='#ff2222', s=50, alpha=0.7)

    point = start
    t = time.clock()

    xs = []
    ys = []

    for i in range(n+1):
        elapsed = time.clock() - t
        #Extrapolation
        eta = (n+1-i)*(elapsed/(i+1))
        printed_len = rewrite("{:>29}: {} of {} ({:.3f}%) ETA: {:.3f}s".format(
                s, i, n, i*100/n, eta), printed_len)
        xs.append(point.real)
        ys.append(point.imag)
        point = point * r + random.choice(points) * (1 - r)

    printed_len = rewrite("{:>29}: plotting...".format(s), printed_len)
    plt.scatter(xs, ys, s=0.5, marker=',', alpha=0.3)

    presave = time.clock()
    printed_len = rewrite("{:>29}: saving...".format(s), printed_len)
    plt.savefig(s + "." + filetype, bbox_inches='tight', dpi=dpi)

    postsave = time.clock()
    printed_len = rewrite("{:>29}: done in {:.3f}s (save took {:.3f}s)".format(
                            s, postsave - start_time, postsave - presave),
                            printed_len)

    if show:
        plt.show()
    print()
    plt.clf()

def rewrite(s, prev):
    spaces = prev - len(s)
    sys.stdout.write('\r')
    sys.stdout.write(s + ' '*(0 if spaces < 0 else spaces))
    sys.stdout.flush()
    return len(s)

class InteractiveChaosGame(cmd.Cmd):
    def do_polygon(self, args):
        (n, num, den, sx, sy, deg) = map(int, args.split())
        plot_saved(n, (num + 0.0)/den, np.complex(sx, sy), list(np.roots([1] + [0]*(deg - 1) + [-1])), show=True)

    def do_points(self, args):
        l = list(map(int, args.split()))
        (n, num, den, sx, sy) = tuple(l[:5])
        l = l[5:]
        points = []
        for i in range(len(l)//2):
            points.append(complex(*tuple([l[2*i], l[2*i + 1]])))
        plot_saved(n, (num + 0.0)/den, np.complex(sx, sy), points, poly=False, show=True)

    def do_pointsdpi(self, args):
        l = list(map(int, args.split()))
        (dpi, n, num, den, sx, sy) = tuple(l[:6])
        l = l[6:]
        points = []
        for i in range(len(l)//2):
            points.append(complex(*tuple([l[2*i], l[2*i + 1]])))
        plot_saved(n, (num + 0.0)/den, np.complex(sx, sy), points, poly=False, show=True, dpi=dpi)

    def do_default(self, args):
        do_generate(self, args)

    def do_EOF(self):
        return True

if __name__ == '__main__':
    interactive = False
    if interactive:
        i = InteractiveChaosGame()
        i.prompt = ": "
        i.completekey='tab'
        i.cmdloop()
    else:
        rs = [1/2, 1/3, 2/3, 3/8, 5/8, 5/6, 9/10]
        for i in range(3, 15):
            for r in rs:
                plot_saved(20000, r, np.complex(0,0),
                            list(np.roots([1] + [0] * (i - 1) + [-1])),
                            filetype='png', dpi=300)

```

# Answer
> -2 votes
## Python (202 chars)

Takes the number of points as `n`, the averaging weight as `r`, the starting point as a `tuple` `s` and the list of points as a list of XY `tuple`s called `l`.

```
import random as v,matplotlib.pyplot as p
def t(n,r,s,l):
 q=complex;s=q(*s);l=[q(*i)for i in l];p.figure(figsize=(6,6))
 for i in range(n):p.scatter(s.real,s.imag,s=1,marker=',');s=s*r+v.choice(l)*(1-r)
 p.show()

```

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