title: Get happy and mad

text:
# Question
Title: Get happy and mad
**Requirements**

You need to make a smiley face go from smiling to frowning and back. There needs to the below faces in the code: **Smiling, no expression, frowning, no expression, and then back to smiling.** The new face needs to replace the old face flipbook style so that there's only one face on the screen at a time. There is no input required it will just be a loop that displays one face, pauses for 200 milliseconds, and replaces the current face with the next and so on looping forever.

**Faces to use:**

```
                      __ooooooooo__
                 oOOOOOOOOOOOOOOOOOOOOOo
             oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
          oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
        oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
      oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
     oOOOOOOOOOOO*  *OOOOOOOOOOOOOO*  *OOOOOOOOOOOOo
    oOOOOOOOOOOO      OOOOOOOOOOOO      OOOOOOOOOOOOo
    oOOOOOOOOOOOOo  oOOOOOOOOOOOOOOo  oOOOOOOOOOOOOOo
   oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
   oOOOO     OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO     OOOOo
   oOOOOOO OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO OOOOOOo
    *OOOOO  OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO  OOOOO*
    *OOOOOO  *OOOOOOOOOOOOOOOOOOOOOOOOOOOOO*  OOOOOO*
     *OOOOOO  *OOOOOOOOOOOOOOOOOOOOOOOOOOO*  OOOOOO*
      *OOOOOOo  *OOOOOOOOOOOOOOOOOOOOOOO*  oOOOOOO*
        *OOOOOOOo  *OOOOOOOOOOOOOOOOO*  oOOOOOOO*
          *OOOOOOOOo  *OOOOOOOOOOO*  oOOOOOOOO*
             *OOOOOOOOo           oOOOOOOOO*
                 *OOOOOOOOOOOOOOOOOOOOO*
                      ""ooooooooo""

                      __ooooooooo__
                 oOOOOOOOOOOOOOOOOOOOOOo
             oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
          oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
        oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
      oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
     oOOOOOOOOOOO*  *OOOOOOOOOOOOOO*  *OOOOOOOOOOOOo
    oOOOOOOOOOOO      OOOOOOOOOOOO      OOOOOOOOOOOOo
    oOOOOOOOOOOOOo  oOOOOOOOOOOOOOOo  oOOOOOOOOOOOOOo
   oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
   oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
   oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
    *OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO*
    *OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO*
     *OOOOOOOOoOOOOOOOOOOOOOOOOOOOOOOOOOOOoOOOOOOOO*
      *OOOOOOo                             oOOOOOO*
        *OOOOOoOOOOOOOOOOOOOOOOOOOOOOOOOOOoOOOOOO*
          *OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO*
             *OOOOOOOOOOOOOOOOOOOOOOOOOOOOO*
                 *OOOOOOOOOOOOOOOOOOOOO*
                      ""ooooooooo""

                      __ooooooooo__
                 oOOOOOOOOOOOOOOOOOOOOOo
             oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
          oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
        oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
      oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
     oOOOOOOOOOOO*  *OOOOOOOOOOOOOO*  *OOOOOOOOOOOOo
    oOOOOOOOOOOO      OOOOOOOOOOOO      OOOOOOOOOOOOo
    oOOOOOOOOOOOOo  oOOOOOOOOOOOOOOo  oOOOOOOOOOOOOOo
   oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
   oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
   oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
    *OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO*
    *OOOOOOOOOOOOOO                  OOOOOOOOOOOOOOO*
     *OOOOOOOOOOO                      OOOoOOOOOOOO*
      *OOOOOO       OOOOOOOOOOOOOOOO        OOOOOO*
        *OOOOO   OOOOOOOOOOOOOOOOOOOOOO   OOOOOO*
          *OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO*
             *OOOOOOOOOOOOOOOOOOOOOOOOOOOOO*
                 *OOOOOOOOOOOOOOOOOOOOO*
                      ""ooooooooo""

                      __ooooooooo__
                 oOOOOOOOOOOOOOOOOOOOOOo
             oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
          oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
        oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
      oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
     oOOOOOOOOOOO*  *OOOOOOOOOOOOOO*  *OOOOOOOOOOOOo
    oOOOOOOOOOOO      OOOOOOOOOOOO      OOOOOOOOOOOOo
    oOOOOOOOOOOOOo  oOOOOOOOOOOOOOOo  oOOOOOOOOOOOOOo
   oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
   oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
   oOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOo
    *OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO*
    *OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO*
     *OOOOOOOOoOOOOOOOOOOOOOOOOOOOOOOOOOOOoOOOOOOOO*
      *OOOOOOo                             oOOOOOO*
        *OOOOOoOOOOOOOOOOOOOOOOOOOOOOOOOOOoOOOOOO*
          *OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO*
             *OOOOOOOOOOOOOOOOOOOOOOOOOOOOO*
                 *OOOOOOOOOOOOOOOOOOOOO*
                      ""ooooooooo""

```

Only one face shows up at a time and it should loop forever cycling between happy indifferent and sad.

**Goal**

Have the shortest code is always the goal but being able to tell that the output is actual a face is quite important.

# Answer
# Python 2 - 461/442 bytes

461 bytes:

```
f='eNrtlkEOwyAMBO+8wuLoz/gJPIH/3yKVhC62AVeVKrUNR7KDceJdhchbpdRrlZLM4yreqikg8sRr\npdZH1EhE9cAgwkQ8ivROg5BphWW5Yymp5rJm50G90pHGzD2c1TVYjQJlCFvj86w91SQMlJiXLuYb\nCFAxTEOXuM4x7v1zH0CWBfYEgAChgkA+6BVircLWlTzrgCi5Lqecu81zThPRnQW/mgUfwzZmdob2\nDQqMs7qXNhJbs9Fs2HUWBAq5YRBoJsbcaXCnwZ+lgR3NTRq4zMnN0sA/WcaKOg2mP1gO8R1hcACw\nDCfh\n'.decode('base64').decode('zlib').split("\n\n");import os,time;f+=[f[1]];i=0
while 1:os.system('cls');print f[i];i=(i+1)%4;time.sleep(.2)

```

442 bytes requiring ansi code support:

```
f='eNrtlkEOwyAMBO+8wuLoz/gJPIH/3yKVhC62AVeVKrUNR7KDceJdhchbpdRrlZLM4yreqikg8sRr\npdZH1EhE9cAgwkQ8ivROg5BphWW5Yymp5rJm50G90pHGzD2c1TVYjQJlCFvj86w91SQMlJiXLuYb\nCFAxTEOXuM4x7v1zH0CWBfYEgAChgkA+6BVircLWlTzrgCi5Lqecu81zThPRnQW/mgUfwzZmdob2\nDQqMs7qXNhJbs9Fs2HUWBAq5YRBoJsbcaXCnwZ+lgR3NTRq4zMnN0sA/WcaKOg2mP1gO8R1hcACw\nDCfh\n'.decode('base64').decode('zlib').split("\n\n");import time;f+=[f[1]];i=0
while 1:print'<ESC>[f'+f[i];i=(i+1)%4;time.sleep(.2)

```

`<ESC>` is a literal escape character (code 27). This program assumes that the terminal it is running on starts out blank
> 2 votes

# Answer
# Mathematica, ~~478~~ 470 bytes

```
i=0;Dynamic[Uncompress["1:eJzt1rsKwjAUBuAOPkjNmEl9BHUUAnYVAg6CU4b6/nhNPLekR6hCJWcQqf/XpFp/Oj+G/WnWNE1/f9md+0u3vr1rxfE+xPH+sFiuWCI4aQLLyrlMvhwWiAYQpCWYQWXb1uIcPZIcZM/lXfGICF1gu2ZHIiQ5xSDJNiRMypA1hxzIpMu0rzMOw2fEYujYL0HGxlMnqJOCi/mQlzZ9FxbepDEuyrfBCGSJA4ISovj/iueRwTsTs48xJtWDMd221oiWQfXHNfJjOVACfGiNfA7B/6y0Qe5AjRQmMBahYrlcj+guTMe+UiSbWiRaBlUtkrHkaEXC7+AcRFK++V2xSOTzuxYdF4pEMA5/MNkeqQ8kagZV7ZGxZH0gQctNtUiuFNCEqg=="][[i=i~Mod~4+1]],UpdateInterval->.2,TrackedSymbols->{}]

```
> 2 votes

# Answer
# JavaScript (ES6), 613 bytes

```
setInterval(_=>(c=console).clear()||c.log((` 16__o6__
 11oO18o
 7oO26o
 4oO32o
 2oO36o
 0oO40o
  oO8*  *O11*  *O9o
 oO8 3O9 3O9o
 oO9o  oO11o  oO10o
oO46o
`+[`oO1 2O28 2O1o
oO3 O32 O3o
 *O2  O30  O2*
 *O3  *O26*  O3*
  *O3  *O24*  O3*
 0*O3o  *O20*  oO3*
 2*O4o  *O14*  oO4*
 4*O5o  *O8*  oO5*
 7*O5o 8oO5*`,n=`oO46o
oO46o
 *O44*
 *O44*
  *O5oO24oO5*
 0*O3o 26oO3*
 2*O2oO24oO2*
 4*O32*
 7*O26*`,`oO46o
oO46o
 *O44*
 *O11 15O12*
  *O8 19O9*
 0*O3 4O13 5O3*
 2*O2 0O19 0O3*
 4*O32*
 7*O26*`,n][i++%4]+`
 11*O18*
 16""o6""`).replace(/.\d+/g,r=>r[0].repeat(+r.slice(1)+3))),i=200)

```

## Explanation

Uses a simple run-length encoding scheme to compress the string. Any character can optionally have a number directly after it which tells the decompressor to print that character `n + 3` times (eg. `ab4c` will become `abbbbbbbc`).

Without this compression the code size is just over 2000 bytes.

```
setInterval(
  _=>(c=console).clear()||c.log(            // clear and display the face in the console
    (                                       // piece together the appropriate string
      `TOP`+                                // run-length encoded face top string
      [`HAPPY`,n=`NEUTRAL`,`SAD`,n][i++%4]+ // encoded mouth string
      `BOTTOM`                              // encoded face bottom string
    )
      .replace(/.\d+/g,                     // search for each character-number instance
        r=>r[0].repeat(+r.slice(1)+3)       // repeat the character n + 3 times
      )
  ),
  i=                                        // i = iterator
    200                                     // set interval to 200ms
)

```
> 1 votes

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


title: Carrot Popularity Statistics

text:
# Question
Title: Carrot Popularity Statistics
In the PPCG chatroom the Nineteenth Byte, using carets `^` (or carrots) is a way of indicating that you agree with one of the previously made comments just above yours.

A caret message consists solely of N `^` characters (where N is a positive integer) and it means agreement with the Nth previous message. So a single `^` means agreement with the message immediately previous, `^^` means agreement with the message two lines up, `^^^` means agreement with the message three lines up, and so on.

Additionally, when a caret message X is in agreement (a.k.a. pointing towards) another caret message Y, then X is said to be in agreement with what Y is in agreement with. There may be multiple layers of this and, in the end, all caret messages are indicating agreement with one non-caret message.

For example, if a chat transcript looks like this: (one message per line)

```
I like dogs           [line 1]
I like cats           [line 2]
^                     [line 3]
^^^                   [line 4]
^^                    [line 5]
I like turtles        [line 6]
^                     [line 7]
^^^                   [line 8]
^^                    [line 9]

```

Then lines 1, 2, and 6 are non-caret messages and all the others are caret messages which point to non-caret messages:

* Line 3 points directly to line 2.
* Line 4 points directly to line 1.
* Line 5 points to line 3, which points to line 2.
* Line 7 points to line 6.
* Line 8 points to line 5, which points to line 3, which points to line 2.
* Line 9 points to line 7, which points to line 6.

Thus, including the users who wrote the non-caret message (and assuming people don't caret their own message) we can conclude that:

* 2 people agree with `I like dogs` (Lines 1 and 4.)
* 4 people agree with `I like cats` (Lines 2, 3, 5, and 8.)
* 3 people agree with `I like turtles` (Lines 6, 7, and 9.)

# Challenge

Write a program or function that takes in a multiline string similar to the example above where every line represents a chat message, with older messages coming first.

Every line will have at least one character and there will be at least one line. All messages will either be caret messages consisting solely of `^`'s, or be non-caret messages consisting of letters and spaces (`[ a-zA-Z]+` in regex).

For every non-caret message, in any order, output the number of people that agree with it in some clear format that contains the message text, e.g.

```
2 - I like dogs
4 - I like cats
3 - I like turtles

```

or

```
I like cats (4)
I like dogs (2)
I like turtles (3)

```

or

```
{"I like cats" : 4, "I like turtles" : 3, "I like dogs" : 2}

```

You can assume that:

* People always agree with their own messages and do not caret themselves.
* No two non-caret messages are identical.
* Caret messages won't point to things before the first message.
* Lines will not contain leading or trailing spaces.

**The shortest code in bytes wins.**

# Test Cases

```
bread is bread

1 - bread is bread

---

animals are fuzzy
^
^
^
^^^
^^
^^^^^^

7 - animals are fuzzy

---

pie
^
^^
pi
^
^^
^^^^
^
^^^^^
^^^^^
^^^
^^^^
^^
^
^^^^^^^^^

9 - pie
6 - pi

---

a
b
c
^
^
^

1 - a
1 - b
4 - c

---

a
b
c
^
^^
^^^

1 - a
1 - b
4 - c

---

a
b
c
^^^
^^^^
^^^^^

4 - a
1 - b
1 - c

---

W
^
^^
X
^^^
^^^^
Y
^^^^^
^^^^^^
Z
^^^^^^^
^^^^^^^^

1 - Y
3 - X
1 - Z
7 - W

---

ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqretuvwxyz
^
ABCDEFGHIJKLMNOPQRSTUVWXYZ  abcdefghijklmnopqretuvwxyz

2 - ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqretuvwxyz
1 - ABCDEFGHIJKLMNOPQRSTUVWXYZ  abcdefghijklmnopqretuvwxyz

---

I like dogs
I like cats
^
^^^
^^
I like turtles
^
^^^
^^

2 - I like dogs
4 - I like cats
3 - I like turtles
```

# Answer
# CJam, 18

```
qN/{_'^e=$\;}%$e`p

```

2 bytes eliminated thanks to Martin :)
Try it online

**Explanation:**

```
q         read the input
N/        split into lines
{…}%      transform each line as follows:
  _       make a copy
  '^e=    count '^' characters in the string
  $       copy the corresponding earlier line from the stack
           if 0, it copies the current line again
  \;      discard the current line (from before the copied line)
          * after the loop, all caret lines have been replaced
          * with the original messages they agree with
$         sort the messages
e`        RLE encode
p         pretty print

```
> 11 votes

# Answer
# Pyth, ~~19~~ 18 bytes

```
rSu+G@+HG_/H\^.zY8

```

Demonstration

A similar approach to aditsu, especially the rle part.

```
rSu+G@+HG_/H\^.zY8
  u           .zY      Reduce over the list input lines, starting with [].
                       G is the working value, H is the next input line.
   +G                  Append to the current value
      +HG              H prependeded to G
     @   _/H\^         Indexed at -(H.count('^')). This is H if no carets are in H,
                       or the appropiate distance from the end of G otherwise.
 S                     Sort
r                 8    Run length encode

```
> 8 votes

# Answer
# JavaScript (ES6), 110 bytes

```
x=>(r={},l=x.split`
`,l.map((_,i)=>(a=n=>(m=l[n])[0]=="^"?a(n-m.length):r[m]=r[m]+1||1)(i)),JSON.stringify(r))

```

## Explanation

```
x=>(
  r={},                   // r = results
  l=x.split`
`,                        // l = array of messages
  l.map((_,i)=>           // check each message
    (a=n=>                // n = index of the message to agree with
      (m=l[n])            // m = message
        [0]=="^"          // if this is a caret message
          ?a(n-m.length)  // agree with the message it points to
          :r[m]=r[m]+1||1 // else add one to this message's agreements
    )(i)
  ),
  JSON.stringify(r)       // return the results as a string
)

```

## Test

```
<textarea id="input" rows="7">I like dogs
I like cats
^
^^^
^^
I like turtles
^
^^^
^^</textarea>
<br />
<button onclick='result.textContent=(

x=>(r={},l=x.split`
`,l.map((_,i)=>(a=n=>(m=l[n])[0]=="^"?a(n-m.length):r[m]=r[m]+1||1)(i)),JSON.stringify(r))

)(input.value)'>Go</button>
<pre id="result"></pre>
```
> 4 votes

# Answer
## Python 2.7 - ~~122~~ 114 bytes

```
def c(s):
 l=s.split('\n');c=len(l);d=[1]*c
 while c:
  c-=1
  if'^'in l[c]:d[c-len(l[c])]+=d[c]
  else:print l[c],d[c]

```

Pretty much the most straightforward solution there is, and not particularly golfed.
> 2 votes

# Answer
# Mathematica, ~~83~~ 77 bytes

```
Tally@#[[Range@Length@#-#~StringCount~"^"//.x_:>x[[x]]]]&@StringSplit[#,"
"]&

```
> 2 votes

# Answer
# Ruby 89

```
m={}
v={}
i=0
$<.map{|l|(t=l.chop![/\^+/])?v[m[i]=o=m[i-t.size]]+=1:v[m[i]=l]=1;i+=1}
p v

```

This is a program that gets input from STDIN and prints out the result. It keeps track of the messages and their vote counts in the variable `v`, which is a `Hash`.

Online demos:
> 2 votes

# Answer
**Python 2.7 96 bytes**

```
l=s.split();b={}
for i in l:_=l.index(i);l[_]=l[_-i.count('^')];b[l[_]]=b.get(l[_],0)+1
print b

```

explanation: in-place overwrite of l, each call of `l[_] = ...` stores the word pointed to, and a dictionary is used to tally the results by initializing or adding to the current count of `b[l[_]]`
> 1 votes

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


title: Average Color of an Image

text:
# Question
Title: Average Color of an Image
# Average color of an image

Scientists have been able to determine the average color of the universe but in how many bytes can we find the average color on an image?

### Your task

Your input will be a single image which you will need to find the average of the colors in the image and output a hex color-string (`#??????`). The image can be any of the following formats

* JPEG/JFIF
    + JPEG 2000
* TIFF
* GIF
* BMP
* PNG
* PNM
    + PPM

The input can also be taken as a URL/URI to the image.

Build-in functions which calculate averages or sample the image at once such as `ImageMeasurements` are not allowed.

### Examples

Results will differ slightly depending on how you calculate the average and which color models you use. I've added RGB and LCH (HSV) values for the images below.

output: `#53715F` RGB, may also be `#3B7D3D` LCH (HSV)

---

output: `#8B7D41` RGB, `#96753C` LCH (HSV)

# Answer
# Pyth - 23 22 19 18 16 bytes

Transposes to get all channels, then sums, divides, and hexifies each. Finishes by concatenating and prepending a `#`.

```
+\#sm.H/sdldCs'z

```

Takes an image file name (any type) from stdin and outputs to stdout. **VERY SLOW**.

```
+               String concat
 \#             "#"
 s              String concat all channels
 m              Map
  .H            Hex string
    /  ld       Divided by length of channel
     sd         Sum of channel
  C             Transpose to separate into channels
   s            Concatenate all rows
    'z          Read image with filename input

```

## Sample run

```
>>>pyth avg.pyth
V5VAR.jpg
#8b7d41

```
> 19 votes

# Answer
# Bash, 46 bytes

ImageMagick scales image to one pixel which contains average of the colors in the image then outputs it as text.

```
convert $1 -scale 1x1\! txt:-|egrep -o '#\w+'

```
> 22 votes

# Answer
# MATLAB - 68 bytes

The image is read in with `imread` combined with `uigetfile` to open up a GUI to choose the image you want to load in. The assumption with this code is that all images are RGB, and to calculate the average colour, we sum over each channel individually then divide by as many elements as there are in one channel, which is the total number of pixels in the RGB image (`numel``(I)`) divided by 3. Because the average can possibly generate floating point values, a call to `fix` is required to round the number down towards zero. `sprintf` combined with the hexadecimal formatting string (`%x`) is used to print out each integer value in the average into its hex equivalent. However, the `02` is there to ensure that an extra 0 is padded to the left should the average value for any channel be less than 16*.

```
I=imread(uigetfile);
['#' sprintf('%02x',fix(sum(sum(I))*3/numel(I)))]

```

# Sample Runs

The nice thing about `imread` is that you can read in images directly from URLs. As a reproducible example, let's assume you have downloaded the images on your computer and have run the above code... but for demonstration, I'll read the images directly from Code Golf:

## First Image

```
>> I=imread('https://i.stack.imgur.com/dkShg.jpg');
>> ['#' sprintf('%02x',fix(sum(sum(I))*3/numel(I)))]

ans =

#53715f

```

## Second Image

```
>> I=imread('https://i.stack.imgur.com/V5VAR.jpg');
>> ['#' sprintf('%02x',fix(sum(sum(I))*3/numel(I)))]

ans =

#8b7d41

```

\*Note: This was a collaborative effort made by StackOverflow users on the MATLAB and Octave chat room.
> 10 votes

# Answer
# CJam, 27 bytes

```
'#[q~]5>3/_:.+\,f/"%02X"fe%

```

This read a PPM image from STDIN.

CJam has no built-in image processing, so this code expects an ASCII Portable PixMap (magic number P3) with full 24-bit palette (maximum value 255) and no comments.

### Test run

```
$ cjam avg.cjam < dkShg.ppm
#53715F

```

### How it works

```
'#     e# Push that character.
[q~]   e# Evaluate the input and collect the results in an array.
5>     e# Discard the first first results (Pi, 3, width, height, range).
3/     e# Split into chunks of length 3 (RGB).
_:.+   e# Push a copy and add across the columns (RGB).
\,f/   e# Divide each sum by the length of the array (number of pixels).
"%02X" e# Push that format string (hexadecimal integer, zero-pad to two digits).
fe%    e# Format each integer, using the format string.

```
> 7 votes

# Answer
## HTML5 + JavaScript (ES6), 335 bytes

This is not going to win but I had fun doing it anyways.

Uses the HTML5 Canvas API. Input is a URL of a CORS-enabled image.

```
f=(u,i=new Image)=>{i.crossOrigin='';i.src=u;i.onload=e=>{x=(c=document.createElement('canvas')).getContext('2d');a=w=c.width=i.width;a*=h=c.height=i.height;x.drawImage(i,0,0);for(d=x.getImageData(m=0,0,w,h).data,r=[0,0,0];m<d.length;m+=4){r[0]+=d[m];r[1]+=d[m+1];r[2]+=d[m+2]}console.log('#'+r.map(v=>(~~(v/a)).toString(16)).join``)}}

```

### Demo

As it is ES6, it currently only works in Firefox and Edge.

```
f = (u,i = new Image) => {
  i.crossOrigin = '';
  i.src = u;
  i.onload = e => {
    x = (c = document.createElement('canvas')).getContext('2d');
    a = w = c.width = i.width;
    a *= h = c.height = i.height;
    x.drawImage(i, 0, 0);
    for (d = x.getImageData(m = 0, 0, w, h).data, r = [0, 0, 0]; m < d.length; m += 4) {
      r[0] += d[m]
      r[1] += d[m + 1];
      r[2] += d[m + 2];
    }
    console.log('#' + r.map(v => (~~(v/a)).toString(16)).join``)
  }
}

// Snippet stuff
console.log = x => document.body.innerHTML += x + '<br>';

f('http://crossorigin.me/https://i.stack.imgur.com/dkShg.jpg');

f('http://crossorigin.me/https://i.stack.imgur.com/V5VAR.jpg');
```
> 7 votes

# Answer
# Python \[3\] + SciPy, 144 133 121

Loads pixel data, sums for each channel, divides by size\*, formats. Values are rounded towards zero.

\*size = width * height * channels, thus multiplied by 3

```
from scipy import misc,sum
i=misc.imread(input())
print('#'+(3*'{:2x}').format(*sum(i.astype(int),axis=(0,1))*3//i.size))

```
> 6 votes

# Answer
# R, 90 bytes

```
rgb(matrix(apply(png::readPNG(scan(,"")),3,function(x)sum(x*255)%/%length(x)),nc=3),m=255)

```

Path to PNG file is read from STDIN. Package `png` needs to be installed.

Step-by-step:

```
#Reads path from stdin and feeds it to function readPNG from package png
p = png::readPNG(scan(,""))
#The result is a 3d matrix (1 layer for each color channel) filled with [0,1] values
#So next step, we compute the mean on each layer using apply(X,3,FUN)
#after moving the value to range [0,255] and keeping it as an integer.
a = apply(p,3,function(x)sum(x*255)%/%length(x))
#The result is then moved to a matrix of 3 columns:
m = matrix(a, nc=3)
#Which we feed to function rgb, while specifying that we're working on range [0,255]
rgb(m, m=255)

# Example:
rgb(matrix(apply(png::readPNG(scan(,"")),3,function(x)sum(x*255)%/%length(x)),nc=3),m=255)
# 1: ~/Desktop/dkShg.png
# 2:
# Read 1 item
# [1] "#53715F"

```
> 3 votes

# Answer
# Cobra - 371

```
@ref 'System.Numerics'
use System.Drawing
use System.Numerics
class P
    def main
        i,d=Bitmap(Console.readLine?''),BigInteger
        r,g,b,c=d(),d(),d(),d()
        for x in i.width,for y in i.height,r,g,b,c=for n in 4 get BigInteger.add([r,g,b,c][n],d([(p=i.getPixel(x,y)).r,p.g,p.b,1][n]))
        print'#'+(for k in[r,g,b]get Convert.toString(BigInteger.divide(k,c)to int,16)).join('')

```
> 2 votes

# Answer
# C, 259 Bytes

Takes a PPM file **with no comments**.

```
double*f,r,g,b;x,y,z,i;char*s="%d %d %d";main(a,_){(a-2)?(feof(f)?0:(fscanf(f,s,&x,&y,&z),r+=(x-r)/i,g+=(y-g)/i,b+=(z-b)/i++,main(0,0))):(f=fopen(((char**)_)[1],"r"),fscanf(f,"%*s%*d%*d%*d"),r=g=b=0.,i=1,main(0,0),printf(s,(int)r,(int)g,(int)b),fclose(f));}

```

## Process

Initial code:

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

int main(int argc, char *argv[])
{
    FILE *f = fopen(argv[1],"r");
    int w,h,d,x,y,z,i;
    double r,g,b;
    fscanf(f,"%*s %d %d %d",&w,&h,&d);//get width, height, depth, ignore P6
    r = g = b = 0.0; //zero r, g, and b totals
    for (i=1; i<=w*h; ++i) {
        fscanf(f,"%d %d %d",&x,&y,&z);//get next pixel
        r+=(x-r)/i;//update averages
        g+=(y-g)/i;
        b+=(z-b)/i;
    }
    printf("%d %d %d",(int)r,(int)g,(int)b);//print result
    fclose(f);
    return 0;
}

```

Trim variables and remove loop:

```
double r,g,b;
FILE *f;
int i;
int main(int argc, char *argv[])
{
    if (argc==2) { // {./me} {file.ppm}
        f = fopen(argv[1],"r");
        fscanf(f,"%*s%*d%*d%*d");//drop info
        r = g = b = 0.0;
        i = 1;
        main(0,0);//begin load loop
        printf("%d %d %d",(int)r,(int)g,(int)b);
        fclose(f)
    } else {
        if (feof(f)) return 0;
        fscanf(f,"%d%d%d",&x,&y,&z);
        r+=(x-r)/i;
        g+=(y-g)/i;
        b+=(z-b)/i;
        i++;
        main(0,0);
    }
    return 0;
}

```

From there I combined the various statements into a single return statement. Removed it and any other extraneous type info, renamed variables, and cut the whitespace.
> 2 votes

# Answer
# Java, ~~449~~ ~~447~~ ~~446~~ ~~430~~ 426 bytes

```
import java.awt.*;interface A{static void main(String[]a)throws Exception{java.awt.image.BufferedImage i=javax.imageio.ImageIO.read(new java.io.File(new java.util.Scanner(System.in).nextLine()));int r=0,g=0,b=0,k=0,x,y;for(x=0;x<i.getWidth();x++)for(y=0;y<i.getHeight();k++){Color c=new Color(i.getRGB(x,y++));r+=c.getRed();g+=c.getGreen();b+=c.getBlue();}System.out.printf("#%06X",0xFFFFFF&new Color(r/k,g/k,b/k).getRGB());}}

```

Thanks to this answer over on stack overflow for the `String.format` trick.
> 2 votes

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


title: Generate Toothpick Sequence

text:
# Question
Title: Generate Toothpick Sequence
## What is Toothpick Sequence?

According to Wikipedia

> In geometry, the toothpick sequence is a sequence of 2-dimensional patterns which can be formed by repeatedly adding line segments ("toothpicks") to the previous pattern in the sequence.
>
> The first stage of the design is a single "toothpick", or line segment. Each stage after the first is formed by taking the previous design and, for every exposed toothpick end, placing another toothpick centered at a right angle on that end.
>
> This process results in a pattern of growth in which the number of segments at stage n oscillates with a fractal pattern between 0.45n2 and 0.67n2. If T(n) denotes the number of segments at stage n, then values of n for which T(n)/n2 is near its maximum occur when n is near a power of two, while the values for which it is near its minimum occur near numbers that are approximately 1.43 times a power of two. The structure of stages in the toothpick sequence often resemble the T-square fractal, or the arrangement of cells in the Ulam–Warburton cellular automaton.
>
> All of the bounded regions surrounded by toothpicks in the pattern, but not themselves crossed by toothpicks, must be squares or rectangles. It has been conjectured that every open rectangle in the toothpick pattern (that is, a rectangle that is completely surrounded by toothpicks, but has no toothpick crossing its interior) has side lengths and areas that are powers of two, with one of the side lengths being at most two.

## Task

You must make a program or function that take input from STDIN, function argument, or commandline argument and make a tootpick fractal at that stage. Leading and trailing newline is prohibited except if it is unavoidable. Bounding box must be at minimum, including leading and trailing space. For inital line, we make two `\` diagonal in space. The input is guaranteed to be less than two thousand. At least one line have non-space character. Trailing space is allowed.

## Test Cases

```
1
\
 \

5
    \
    /\
   /\
  / /\
\/\/\ \ \
 \ \ \/\/\
    \/ /
     \/
    \/
     \

```

# Answer
> 6 votes
## CJam, ~~99~~ 93 bytes

This got rather long...

```
"\ "_W%]{{Sf+W%z}4*2ew{2fewz{_sa"\//\\"4S**4/^_,3={:.e>W%2/\}&;}%z{\)a@.e>+}:Ff*}%{F}*}q~(*N*

```

Test it here. If you want to test larger inputs, like the 89 on Wikipedia, Dennis's TryItOnline uses the much faster Java interpreter under the hood and can handle inputs like that in a few seconds.

I'm sure there is a lot of room for improvement, and I'll add an explanation once I'm happier with the score...

Here is the output for `N = 13`:

```
            \
            /\
           /\
          / /\
        \/\/\ \ \
         \ \/\/\/\
           /\/\/
          / /\ \
    \    /\/\ \     \
    /\  /  \/\/\    /\
   /\  /\  /\/  \ \/\
  / /\/ /\/ /\  /\ \/\
\/\/\/\/\/\/\ \/\ \/\ \ \
 \ \ \/\ \/\ \/\/\/\/\/\/\
    \/\ \/  \/ /\/ /\/ /
     \/\ \  /\/  \/  \/
    \/    \/\/\  /  \/
     \     \ \/\/    \
          \ \/ /
          /\/\/
        \/\/\/\ \
         \ \ \/\/\
            \/ /
             \/
            \/
             \

```

For my own reference when golfing this further, some other ideas:

```
"\ "_W%]{{Sf+W%z}4*2few2ew::.{+_a"\//\\"4S**4/^_,3={:.e>W%\}&;2/}:z{\)a@.e>+}ff*{\)a@..e>+}*}ri(*N*

```

```
"\ "_W%]{{Sf+W%z}4*2ew{2fewz{_sa"\//\\"4S**4/^_,3={:.e>W%2/\}&;}%{.{\)a@.e>+}}*}%{\)a@.e>+}*}q~(*N*

```

# Answer
> 1 votes
# JavaScript (ES6), 263 bytes

```
n=>(o=(o=[..." ".repeat(n*2)]).map(_=>o.map(_=>s=c=" ")),(g=a=>s++<n&&g(q=[],a.map(p=>o[p[4]][p[3]]==c&&(o[y=p[1]][x=p[0]]=o[y-1][(b=+p[2])?x-1:x+1]="/\\"[b],q.push([x,++y,!b,b?x+1:x-1,y],[b?x-=2:x+=2,y-2,!b,x,y-3])))))([[n,n,1,n,n]]),o.map(r=>r.join``).join`
`)

```

## Explanation

```
n=>(                           // n = desired stage

  o=                           // o = output grid
                               //     [ [ "\\", " " ], [ " ", "\\" ], etc... ]
    (o=[..." ".repeat(n*2)])   // create an array the size of the grid
    .map(_=>o.map(_=>          // loop over it and return the output grid
      s=                       // s = current stage (" " acts the same as 0)
        c=                     // c = blank character
          " "                  // initialise each element to " "
    )),

  (g=                          // g = compute stage function
    a=>                        // a = positions to place toothpicks
                               //     [ x, y, isBackslash, checkX, checkY ]
      s++<n&&                  // do nothing if we have reached the desired stage
      g(q=[],                  // q = positions for the next stage's toothpicks
        a.map(p=>              // p = current potential toothpick position
          o[p[4]][p[3]]==c&&(  // check the position to make sure it is clear

            o[y=p[1]][x=p[0]]= // place bottom toothpick, x/y = position x/y
            o[y-1][            // place top toothpick
              (b=+p[2])        // b = isBackslash
              ?x-1:x+1         // top toothpick x depends on direction
            ]="/\\"[b],        // set the location to the appropriate character

            // Add the next toothpick positions
            q.push([x,++y,!b,b?x+1:x-1,y],
              [b?x-=2:x+=2,y-2,!b,x,y-3])
          )
        )
      )
  )([[n,n,1,n,n]]),            // place the initial toothpicks
  o.map(r=>r.join``).join`
` // return the grid converted to a string
)

```

## Test

```
Stages: <input type="number" oninput='result.innerHTML=(

n=>(o=(o=[..." ".repeat(n*2)]).map(_=>o.map(_=>s=c=" ")),(g=a=>s++<n&&g(q=[],a.map(p=>o[p[4]][p[3]]==c&&(o[y=p[1]][x=p[0]]=o[y-1][(b=+p[2])?x-1:x+1]="/\\"[b],q.push([x,++y,!b,b?x+1:x-1,y],[b?x-=2:x+=2,y-2,!b,x,y-3])))))([[n,n,1,n,n]]),o.map(r=>r.join``).join`
`)

)(+this.value)' /><pre id="result"></pre>
```

# Answer
> 1 votes
# Ruby, 151 bytes

Golfed version uses only one loop, `j`, with `i` and `k` calculated on the fly.

```
->n{m=n*2
s=(' '*m+$/)*m
l=m*m+m
s[l/2+n]=s[l/2-n-2]=?\\
(n*l-l).times{|j|(s[i=j%l]+s[i-m-2+2*k=j/l%2]).sum==124-k*45&&s[i-m-1]=s[i-1+2*k]="/\\"[k]}
s}

```

**Ungolfed in test program**

This version uses 2 nested loops.

A rarely used builtin is `sum` which returns a crude checksum by adding all the bytes of an ascii string.

```
f=->n{
  m=n*2                                       #calculate grid height / width
  s=(' '*m+$/)*m                              #fill grid with spaces, separated by newlines
  l=m*m+m                                     #calculate length of string s
  s[l/2+n]=s[l/2-n-2]=?\\                     #draw the first toothpick
  (n-1).times{|j|                             #iterate n-1 times
    l.times{|i|                               #for each character in the string
      (s[i]+s[i-m-2+2*k=j%2]).sum==124-k*45&& #if checksum of current character + character diagonally above indicates the end of a toothpick
         s[i-m-1]=s[i-1+2*k]="/\\"[k]         #draw another toothpick at the end
    }
  }
s}                                            #return value = s

puts f[gets.to_i]

```

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


title: Quine Pride Parade!

text:
# Question
Title: Quine Pride Parade!
These days, I watched on TV a Gay Pride parade; at the time, I was thinking about quines and how they're a bit queer, outputting themselves (out of the closet?) and, well, why not combine both things into a Quine Pride Parade?

The challenge is to write a program that:

1. Is a quine.
2. Prints the sentence `I am a quine written in <language name>, and very proud of it!` with the name of the language you're using in place of `language name`.
3. Contains the sentence within a rectangular frame of non-whitespace characters, with at least one row/column of spaces above, below, before and after it.
4. Contains the sentence in three rows, with centered text, like in my entry below. You can add at most one space before the language name, to align the second line within the frame.

The program itself does not need to have a rectangular form, but must frame the sentence.

**Scoring**

As Dennis pointed out, languages with shorter names have an advantage, and most bytes will go into the frame.

So, the scoring will be as follows: size of the program (in bytes), minus the size of the language's name, minus 140 (a tweet's size). The following bonuses are applied after that:

* -50% if the program also accepts a custom sentence, outputs it on the generated program's frame instead of the default message, and the generated program is still a quine. Assume a tweet-sized sentence (140 chars max). Without input, it can output, either the default sentence above, or an empty frame.
* -30% if the program shows only one copy of the sentence (the other should be obfuscated).

The bonuses stack: getting both does (n - 50%) - 30% = 0.5n - 30% = 0.35n.

The smallest score wins.

Here is my entry, in Ruby - should have a linebreak at the end. No bonus, score 399 = 543 bytes - 4 - 140.

```
q=34.chr;e=10.chr;prideful=''+
'                         '+e+
'      I am a quine       '+e+
'    written in  Ruby,    '+e+
'  and very proud of it!  '+e+
'                         '+e;s=[
"q=34.chr;e=10.chr;prideful=''+",
"'                         '+e+",
"'      I am a quine       '+e+",
"'    written in  Ruby,    '+e+",
"'  and very proud of it!  '+e+",
"'                         '+e;s=[",
"@",
"];t=s.map{|x|q+x+q}.join(','+e)",
"s.each{|y|puts(y!='@'?y:t)}"
];t=s.map{|x|q+x+q}.join(','+e)
s.each{|y|puts(y!='@'?y:t)}

```

It is a classic quine format: `s` contains itself, as an array (one element per line), except for itself's quote (the `@`); then, joins `s`, substituting `@` by the join, quoted.

The program can clearly be golfed further: I went for a nice rectangular format instead.

# Answer
## Aubergine, 7\*24+1-9=160-140=20-30%=14 bytes

```
-a1+a1=oA=Bi-BA:bB=iaooo
o                      o
o I am a quine written o
o  in Aubergine, and   o
o  very proud of it!   o
o                      o
oooooooooooooooooooooooo    (removethis)

```

The (removethis) is not code, but is just there to protect the trailing whitespace.

It's just my standard aubergine quine with all the extra stuff stuck in it to meet requirements.
> 3 votes

---
Tags: code-challenge, ascii-art, quine
---


title: Quiz Program Compiler

text:
# Question
Title: Quiz Program Compiler
A fun programming exercise is to write a program that quizzes the user from a set list of questions and answers. However, this task goes a level beyond that.

## Your task

* Write a program/func/etc. that takes two lists: A list of questions and a list of answers.
* Output a program that quizzes the user.
* The output program should ask each question on a separate line, which each question with a colon and space at the end like, `What is 2+2:`.
* After the user answers all the questions, output a newline, and then one on each line, questions correct, questions wrong, and percentage calculation (rounded to 2 decimal places) as such (the brackets are user input):

```
What is the meaning of life, the universe, and everything: <42>
Am I awesome(Yes/No): <No>
What is 2+2: <4>

Number Correct: 2
Number Wrong: 1
Score: 2 / 3 * 100 = 66.67%

```

## Scoring

* You are scored on the size of your compiler program.
* This is so shortes code in **bytes** wins!
* **Bonus**: Score \*.9 if you implement a flag in your compiler that makes the output program randomize question order.

# Answer
> 3 votes
# CJam, ~~105~~ 99 bytes

```
{{": "+ol}%.=_:+\,:LX$-X$LX$e2Ld/]"
Number Correct: %d
Number Wrong: %d
Score: %d / %d * 100 = %.2f%%"e%}

```

This defines an anonymous function.

The code is **110 bytes** long and qualifies for the **× 0.9** randomization bonus.

### Test run

```
$ cat qna.cjam
[
  [
    "42"
    "Yes"
    "4"
  ]

  [
    "What is the meaning of life, the universe, and everything"
    "Am I awesome(Yes/No)"
    "What is 2+2"
  ]
]

{zmrz~{": "+ol}%.=_:+\,:LX$-X$LX$e2Ld/]"
Number Correct: %d
Number Wrong: %d
Score: %d / %d * 100 = %.2f%%"e%}

~

$ cjam qna.cjam
What is 2+2: 4
Am I awesome(Yes/No): No
What is the meaning of life, the universe, and everything: 42

Number Correct: 2
Number Wrong: 1
Score: 2 / 3 * 100 = 66.67%

```

---
Tags: code-golf, compiler
---


title: List numbers within given ranges

text:
# Question
Title: List numbers within given ranges
## Goal:

Your goal is to print out numbers within a given range (*Also including given values*).

## Input Format:

The input will look like: `(int-int, int-int, ...)`

`...` meaning the user can add as many `int-int` as they'd like.

## Other Info:

* You will only have to handle *non-negative* integer numbers.
* The first integer in `int-int` will always be smaller, or the same, then the next integer in `int-int`
* The input will *always have at least two* `int-int`
* Each `int-int` will followed by a comma and a space, except for the last one.
* This is meaning the shortest answer wins!

## Examples / Test Cases:

* Example 1:
* Input: `(10-13, 11-15, 0-3)`
* Output: `10 11 12 13 11 12 13 14 15 0 1 2 3`
* Example 2:
* Input: `(1-5, 1-15)`
* Output: `1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15`
* Example 3:
* Input: `(1-2, 1-3, 1-3, 1-2)`
* Output: `1 2 1 2 3 1 2 3 1 2`
* Example 4:
* Input: `(4-6, 0-1, 9-9)`
* Output: `4 5 6 0 1 9`

# Answer
# CJam, 19

```
qS/{'.,Ser~),>~}%S*

```

Martin Büttner killed 2 bytes again, thanks :)
Try it online

**Explanation:**

```
q       read input
S/      split by space
{…}%    transform each string (containing a pair of numbers and some other chars)
  '.,   enumerate all characters smaller than '.'
  Ser   replace them all with a space in the string
  ~     evaluate the resulting string, pushing the 2 numbers on the stack
         let's call them A and B
  ),    create an array [0 1 … B]
  >     slice it from A: [A … B]
  ~     dump it onto the stack
S*      join the resulting array with spaces

```
> 2 votes

# Answer
## Minkolang 0.13, 12 bytes

```
nd1+?.n~Lr$N

```

Try it here.

### Explanation

```
n      Take number from input (-1 if input is devoid of numbers)
d1+    Duplicate and add 1
?.     If this is 0, stop.
n~     Get number from input and negate it (because of the '-')
L      Pops b,a and pushes a,a+1,a+2,...,b-1,b
r      Reverses list
$N     Outputs whole stack as numbers

```
> 3 votes

# Answer
# Julia, 75 bytes

```
s->print((j=join)(map(i->j(i," "),eval(parse(replace(s,"-",":"))))," "))

```

This is an anonymous function that accepts a string and prints to STDOUT. To call it, give it a name, e.g. `f=s->...`.

Ungolfed:

```
function f(s::AbstractString)
    # Replace dashes with colons in the input
    c = replace(s, "-", ":")

    # Parse as a tuple of UnitRange objects
    r = eval(parse(c))

    # Join each range with spaces
    m = map(i -> join(i, " "), r)

    # Join into one string and print
    print(join(m, " "))
end

```
> 2 votes

# Answer
## Javascript (ES 2015), ~~86~~ 83 bytes

```
f=r=>{z="";r.replace(/(?:(\d+).(\d+))/g,(m,n,x)=>{do{z+=n+" "}while(n++<x)});alert(z)}

```

Live Demo: http://codepen.io/anon/pen/BoeEGO?editors=001

---

**Edit 1**: saved 3 bytes changing the body of the inner function into `for(;n<=x;)z+=n+++" "` (and I feel good when the horizontal scrollbar of my snippet at last disappears :) )

```
f=r=>{z="";r.replace(/(?:(\d+).(\d+))/g,(m,n,x)=>{for(;n<=x;)z+=n+++" "});alert(z)}

```

---

Ungolfed

```
f=r=>{                                       // define a function with 'r' arg

  z="";                                      // initialize a variable to collect
                                             // the output

  r.replace(/(?:(\d+).(\d+))/g,(m,n,x)=>{    // for each range
                                             // where (m=range, n=min, x=max)
    for(; n<=x; ) {                          // until min <= max
      z += n++ + " "                         // add to z the value and a space
    }
  });

  alert(z)                                   // alert the output
}

```

---

```
f("(10-13, 11-15, 0-3, 9-9)");  // Output: 10 11 12 13 11 12 13 14 15 0 1 2 3 9

```
> 2 votes

# Answer
# TeaScript, 18 + 1 = 19 bytes ~~20~~

<sup>+1 byte for "Inputs are arrays / lists?" checkbox</sup>

Such abuse...

```
xße`r(${ls`-`}¬)`)

```

I've never abused JavaScript's casting more in my life.

Try it online

## Ungolfed && Explanation

My favorite part is JavaScript arrays when cast to a string have commas auto-inserted. We abuse this so the array elements are inserted as numbers *and* as separate arguments. So `1-2`, would become `['1','2']` but when string casted `1,2` and this can be put directly in a function.

```
xm(#e`r(${ls`-`}+1)`)

                        // The checkbox makes the input like ['1-2','3-4']
xm(#                )   // Loop through input
    e`             `    // Eval string...
      r(        +1)     // range function...
        ${ls`-`}        // Convert range -> args
                        // See above for more details

```
> 1 votes

# Answer
## Python 2, 125 bytes

```
import re
print' '.join(map(lambda x:' '.join([str(y)for y in x]),eval(re.sub('(\d+)-(\d+)',r'range(\1,\2+1)',raw_input()))))

```

Try it online

I'm certain this could be golfed more...
> 1 votes

# Answer
## CJam, 41 bytes (too long!)

Definitely can be golfed, but its a start. Test it online here.

```
l'(/e_')/e_',/{['-' er~]2,.+:,W%:-}%e_' *

l                                           e# Take string input
 '(/e_                                      e# Remove '( characters
      ')/e_                                 e# Remove ') characters
           ',/                              e# Split on commas
              {                   }%        e# Map over array...
               ['-' er~]                       e# Convert A-B to [A B]
                        2,.+                   e# Convert [A B] to [A B+1]
                            :,W%               e# Convert [A B+1] to [[0,1,2, ... B][0, 1, 2, ... A]]
                                :-             e# Remove element 1 of the previous array from element 2
                                    e_' *   e# Format nicely
                                            e# CJam prints stack after execution

```
> 1 votes

# Answer
# , ~~75~~ 74 bytes

```
I'(-')-", "/]{[[n'-/]{n#}d[$,.$.0=0={.@=0={;.@=0=}w;}{;;}?r]]{n{noTo}d}d}d

```

This makes logical sense to anyone who built the language (i.e. me). The logic behind this is intense and I'm just happy that I got it working.

Try it online or RUN EVERY TEST CASE AT THE SAME TIME

Explanation:

```
I'(-')-", "/]    Format inputs into array
{                 Iterate over each input range
 [[n'-/]{n#}d     Split ranges into sets of numbers
 [$,              Get the second number and get a range from 0 to it
 .$.0=0=          Is the first number 0?
 {.@=0={;.@=0=}w;} True: Remove any unneeded numbers
 {;;}?             False: Pop some random stuff that shouldn't have been on there to begin with
 r]]              Reverse the range and close some array stuff or whatever
 {n{noTo}d}d}     Format output
}d

```
> 1 votes

# Answer
## Python 3, 76 bytes

```
l=eval(input().replace(*'-,'))
while l:a,b,*l=l;print(*range(a,b+1),end=' ')

```

The input is evaluated as a tuple by replacing each `-` with `,`

```
(10-13, 11-15, 0-3) --> (10,13, 11,15, 0,3)

```

Then, the first two elements of the list are repeatedly lopped off and the numbers between them are printed.

Saved 2 bytes thanks to xsot.
> 1 votes

# Answer
# Mathematica, 80 bytes

```
Join@@BlockMap[Range@@FromDigits/@#&,StringCases[#,DigitCharacter..],2]~Row~" "&

```
> 1 votes

---
Tags: code-golf, number, sequence
---


title: Lenient typing test

text:
# Question
Title: Lenient typing test
A typing speed test loads up a dictionary of words, and gives you one to type: `pinball`. You, with your fast but inaccurate fingers, type in `pinbnal`. Darn it!

Make a program that will print out a random word from a dictionary, then ask for the user to type this word back, and finally return whether or not they got the word right. The catch is: the program must accept minor typos.

Accept a typo if it has only one of the following:

* one letter is repeated in the input 1 or 2 more times. Only accept the letter if it is directly adjacent to a letter it is next to.
* one letter in the word is repeated 1 time.
* 2-4 of the letters in the input are scrambled.

Some acceptable typos of the word `pinball` are:
`pingball pinbala pinbanll`
Some unacceptable typos:
`pibnannl maxwell pinbalgl`

Shortest code wins. Good luck.

# Answer
> 4 votes
# Mathematica 179

Edit: As Primo correctly notes, the following does not adhere to the constraint of pardoning only those intrusions from QWERTY neighbors. DL distance, of course, has nothing to do with distance on a keyboard. Oh, well. I'll leave up my response, which someone with more patience will easily better.

---

Code

```
d = DictionaryLookup[]; i = d[[RandomInteger@{1, Length@d}]];o = InputString["Type: " <> i];
Print["in: ", i, "\nout: ", o, "\n", Switch[i~DamerauLevenshteinDistance~o, 0, "perfect",
1, "ok", _, "wrong"]]

```

---

Explanation

1. `d = DictionaryLookup[]` stores a built-in dictionary of 92 k English words in `d`.
2. `i = d[[RandomInteger@{1, Length@d}]]` selects a random word and stores it in `i`.
3. `o = InputString["Type: " <> i];` opens a dialog window (see figure) with the prompt "Type \[i\]."
4. `i~DamerauLevenshteinDistance~o` computes the Damerau-Levenshtein distance beween the requested word and the word typed by the user. If the DL distance = 0, "perfect"; if the DL distance = 1, "ok"; otherwise, "wrong".

---

Test Results

For the first 7 tests, the input string, i, was manually set to "pinball". The results were as desired with the exception of "pinbalgl", which was considered acceptable because it returns a DL distance value of 1.

> in: pinball
> out: pinball
> perfect
>
> in: pinball
> out: pingball
> ok
>
> in: pinball
> out: pinbala
> ok
>
> in: pinball
> out: pinbanll
> ok
>
> in: pinball
> out: pinbannl
> wrong
>
> in: pinball
> out: maxwell
> wrong
>
> in: pinball
> out: pinbalgl
> ok
>
> in: tureen
> out: turen
> ok
>
> in: feeder
> out: feedr
> ok
>
> in: tarmacs
> out: tarmax
> wrong

# Answer
> 2 votes
## Python 2, ~~634~~ ~~581~~ ~~568~~ 565 bytes

```
import random
s="aszaqwsxdswedcfderfvgfrtgbhgtyhnjhyujmkjuikiopolkmnbvcx"
s+='z'+s[::-1]
d={}
for j in range(len(s)-1):d[s[j]]=d.get(s[j],"")+s[j+1]
v=random.choice(open("d","r").read().split())
u=list(raw_input(v+':'))
v=list(v)
e=sorted
i=n=r=b=0;l=len(v);g=1
q=any([v[:j]+e(v[j:j+4])+v[j+4:]==u[:j]+e(u[j:j+4])+u[j+4:]for j in range(l-3)])
while i<l*g:
 g*=i<len(u)
 if v[i]!=u[i]:
  if any([0<=i<l and u[i]in d[v[i+c]]for c in-1,0]):n+=1;g-=(b and u[i]!=b);b=u[i];del u[i]
  elif u[i]in v:r+=1;del u[i]
  else:g=0
 else:i+=1
print'good'if q+g*(n+2*r<3)else'bad'

```

It took a heck of lot of bytes to meet every single little special case and exception that this problem called for, and that's reflected in the size. There's probably some optimizations I'm missing, but I'm just happy that I met all the requirements.

To run it, put your list of lowercase words in a file called `d` in the same directory and just run.

It should be clear how this works once you know what each variable is:

* `s`: a String of adjacent keys used to construct `d`
* `d`: a Dictionary encoding a graph of key adjacencies, according to the keyboard i'm using right now. Lines 1 through 4 set this up.
* `v`: the random word, first as a string, then as a list of characters
* `u`: the User input, as a list of characters
* `e`: the `sortEd` built-in
* `i`: the Index into the correct word
* `n`: the number of times an incorrect character that is Next to a correct character appears
* `r`: the number of times an incorrect character that is in the word Repeats
* `g`: whether the input is currently believed to be Good
* `l`: the correct Length of the word
* `q`: whether some shuffling of four adjacent letters in the user input would yield the correct word
* `j`: a temp used in the creation of `q`

The important parts are:

* the for at the top, which maps each letter in `s` to the next character. At the end, each lowercase letter is mapped to a string containing all letters adjacent on the keyboard (some with several repeats, but it doesn't matter).
* the line where q is evaluated, which basically just sorts each set of four adjacent characters in both the input and correct word while leaving the rest of the lists alone. If sorting any such part results in both lists being the same, this is an allowed typo according to rule 3
* the while loop, which iterates over both strings, looking for mismatches. Where one is found, it determines whether its of type 1 or type 2, preferring the former since we're allowed more type 1 errors than type 2 errors. The numbers of errors of type 1 and 2 are counted in `n` and `r` respectively. Errors which don't fall into either of these categories set `g` to 0 which breaks the loop. Notice the `g-=(b and u[i]!=b);b=u[i]`. This checks that this type 1 error involved the same character (saved in `b`) as last time (if there was a last time). This is because the first rule allows us to repeat the *same* character 1 or 2 times, but not two different characters.
* the final line outputs good if and only if `q` OR (`g` AND (`n<3` AND `r==0`) OR (`r<2` AND `n==0`) ). Type 3 errors are mutually exclusive with the other types, but it is possible to have both type 1 and 2 in the same input. The condition is complex to allow one or the other but not both.

NB: this program will NOT accept "pinbala" as a correct spelling of "pinball", as it does not fall into any of the three described typo categories, as pointed out by ceased to turn counterclockwis

---
Tags: code-golf
---


title: Black Friday Queue Managment

text:
# Question
Title: Black Friday Queue Managment
# Introduction

You are the manager of the electronics department in a major retail store and the biggest sales day of the year is this Friday. To help manage the crowds, your store is implementing a ticket system for the biggest deals, where customers must present a ticket before purchasing an item. Your job is to write a program to validate the tickets.

Since the only available computer in the store (due to budget cuts) is a dinosaur with a broken keyboard, (and all you have is USB keyboards, which aren't compatible) you'll have to input your program with a mouse. Therefore, your program should be as short as possible.

# Products

You store is running sales on the five different products listed below. Each product has an all lowercase name and different rules on how many can be purchased and at what time of day.

* `television`: There are `5` flat-screen televisions in stock that may be purchased from `00:00:00` (midnight) to `00:59:59`.
* `smartphone`: There are `10` smartphones in stock, but any customer in line from `00:00:00` (midnight) to `00:59:59` receives a voucher for one once they run out.
* `tablet`: There are `10` tablets that may be purchased at anytime.
* `laptop`: There are an unlimited number of laptops that may be purchased from `00:00:00` (midnight) to `07:59:59`.
* `lightbulb`: There are an unlimited number of light bulbs that may be purchased at anytime.

# Input

A multi-line string with each line in the following format. Lines are sorted by the time-stamp.

```
<time stamp> <product name> <ticket number>

```
* The ticket number is 8 digits long. The last digit is a check-digit equal to the sum of the first seven digits modulo 10. To be valid, a ticket number must have the correct check-digit and must be strictly greater than all previous ticket numbers.
* The product name is one of the string listed above.
* The time stamp is the time of day in the format `HH:MM:SS` where `HH` is the two-digit hour from 00-23, and `MM` and `SS` are the two-digit minute and second respectively.

# Output

The output is one of the following strings, with one line per ticket. The conditions must be applied **in order**.

1. `Expired offer` (Applies to televisions, smartphones, and laptops.) The time-stamp of the ticket is after the cutoff to buy the product.
2. `Invalid ticket` Either the ticket number is less than or equal to the number of the previous ticket, or the check-digit is invalid.
3. `Give voucher` (Applies to smartphones.) The product is out of stock, but all the customers in line before the offer expires get a rain check.
4. `Out of stock` (Applies to televisions and tablets.) All of the product has been sold. Sorry, quantity was limited.
5. `Accepted` All conditions are met, so give them the product. Note that only accepted tickets reduce the number of items in stock.

# Example

```
Input                           Output
----------------------------    --------------
00:00:00 television 00010001    Accepted
00:00:25 smartphone 00011697    Accepted
00:01:25 laptop 00030238        Accepted
00:02:11 smartphone 00037291    Accepted
00:02:37 lightbulb 00073469     Invalid ticket
00:03:54 smartphone 00096319    Accepted
00:05:26 tablet 00152514        Accepted
00:06:21 tablet 00169893        Accepted
00:07:10 television 00190268    Accepted
00:07:47 smartphone 00194486    Accepted
00:07:55 tablet 00220071        Accepted
00:08:20 lightbulb 00321332     Accepted
00:10:01 smartphone 00409867    Accepted
00:11:10 tablet 00394210        Invalid ticket
00:11:46 television 00581060    Accepted
00:12:44 lightbulb 00606327     Accepted
00:13:16 tablet 00709253        Accepted
00:13:53 television 00801874    Accepted
00:14:47 laptop 00832058        Accepted
00:15:34 smartphone 00963682    Accepted
00:16:24 smartphone 01050275    Accepted
00:17:45 tablet 01117167        Accepted
00:18:05 laptop 01107548        Invalid ticket
00:19:00 lightbulb 01107605     Invalid ticket
00:19:47 lightbulb 01492983     Accepted
00:19:50 smartphone 01561609    Accepted
00:21:09 television 01567098    Accepted
00:21:42 laptop 01597046        Accepted
00:22:17 smartphone 01666313    Accepted
00:24:12 tablet 01924859        Accepted
00:24:12 smartphone 02151571    Accepted
00:25:38 smartphone 02428286    Give voucher
00:31:58 television 02435284    Out of stock
00:35:25 television 02435295    Out of stock
00:52:43 laptop 02657911        Invalid ticket
00:53:55 smartphone 02695990    Give voucher
01:08:19 tablet 02767103        Accepted
01:34:03 television 02834850    Expired offer
01:56:46 laptop 02896263        Accepted
02:02:41 smartphone 03028788    Expired offer
02:30:59 television 03142550    Expired offer
02:51:23 tablet 03428805        Accepted
03:14:57 smartphone 03602315    Expired offer
03:27:12 television 03739585    Expired offer
03:56:52 smartphone 03997615    Expired offer
04:07:52 tablet 04149301        Accepted
04:12:05 lightbulb 04300460     Invalid ticket
04:24:21 laptop 04389172        Accepted
04:40:23 lightbulb 04814175     Accepted
04:40:55 tablet 04817853        Accepted
04:42:18 smartphone 04927332    Expired offer
05:06:43 tablet 05079393        Out of stock
05:16:48 tablet 05513150        Out of stock
05:33:02 television 05760312    Expired offer
05:43:32 tablet 06037905        Out of stock
06:12:48 smartphone 06440172    Expired offer
06:35:25 laptop 06507277        Accepted
06:42:29 lightbulb 06586255     Invalid ticket
06:55:31 lightbulb 06905583     Accepted
06:55:33 lightbulb 06905583     Invalid ticket
07:40:05 smartphone 07428006    Expired offer
07:49:12 television 07588086    Expired offer
08:14:56 laptop 08111865        Expired offer

```

I have tried to make the example cover every possible output scenario, but please leave a comment if anything is unclear.

This is , you may write a program or function, and standard loop-holes are disallowed.

# Answer
# Javascript(ES6), ~~396~~ ~~433~~ 419 bytes

```
h=0;f=1/0;i={television:{c:5,s:0,e:1},smartphone:{c:10,s:0,e:1,v:1},tablet:{c:10,s:0,e:24},laptop:{c:f,s:0,e:8},lightbulb:{c:f,s:0,e:24}};while(1){t=prompt().split(' ');a=t[0];r=a[0]+a[1]-0;o=i[t[1]];m=0;z='Accepted';u=t[2]-0;u<=h||(u-u%10+'').split('').reduce((p,c)=>-(-p-c))%10!=u%10?m='Invalid ticket':0;r<o.s||r>=o.e?m='Expired offer':0;if(!m)o.c?o.c--:(o.v?z='Give voucher':m='Out of stock');!m?h=u:0;alert(m?m:z)}

```

**Edit:** Reduced size by using es6 big arrow function

### More readable:

```
h=0
f=1/0
i={television:{c:5,s:0,e:1},smartphone:{c:10,s:0,e:1,v:1},tablet:{c:10,s:0,e:24},laptop:{c:f,s:0,e:8},lightbulb:{c:f,s:0,e:24}}
while(1){t=prompt().split(' ')
a=t[0]
r=a[0]+a[1]-0
o=i[t[1]]
m=0
z='Accepted'
u=t[2]
if(u<=h||(u-u%10+'').split('').reduce(function(p,c){return-(-p-c)})%10!=u%10)m='Invalid ticket'
if(r<o.s||r>=o.e)m='Expired offer'
if(!m){if(o.c)o.c--
else o.v?z='Give voucher':m='Out of stock'}if(!m)h=u
alert(m?m:z)}

```

Interestingly the longer code is faster: http://jsperf.com/compare-read

### GUI with same logic:

```
var app = angular.module('app', []);

app.controller('MainCtrl', function MainCtrl ($scope) {
  $scope.items = {
    television: {c: 5, s:0, e: 1},
    smartphone: {c: 10, s:0, e: 1},
    tablet: {c:10, s:0, e: 24},
    laptop: {c:Infinity, s: 0, e: 8},
    lightbulb: {c: Infinity, s: 0, e: 24},
  };

  var h = -1;//highest

  $scope.hours_offset = 0;

  $scope.ticket = {};
  for (var i = 0; i < 8; i++) $scope.ticket[i] = 0;

  $scope.selected_item = -1;

  $scope.nums = new Array(10);

  $scope.history = [];

  $scope.buy = function() {

  }
  $scope.selectItem = function($i) {
    $scope.selected_item = $i;
  }

  $scope.purchase = function() {
    if ($scope.selected_item === -1)
      return;

    var ticnum = '';
    var msg = 'Accepted';

    for(var key in $scope.ticket)
      ticnum+=$scope.ticket[key];

    var d = new Date();

    //Variable declarations to setup for code like the code I designed for console
    r = d.getHours()-$scope.hours_offset;//hour
    o = $scope.items[$scope.selected_item];//item
    m = 0//msg
    z = 'Accepted'//default_msg
    u=ticnum

    //This is copied from my console code
    if(ticnum<=h||(ticnum-ticnum%10+'').split('').reduce(function(p,c){return-(-p-c)})%10!=ticnum%10)m='Invalid ticket'
 if(r<o.s||r>=o.e)m='Expired offer'
 if(!m){if(o.c)o.c--
 else o.v?z='Give voucher':m='Out of stock'}if(!m)h=ticnum

    msg = m?m:z;

    $scope.history.unshift({
      time: time(d),
      item: $scope.selected_item,
      ticket_num: ticnum,
      message: msg
    });

  }
});

function time(date) {
  return padToTwo(date.getHours()) + ':' + padToTwo(date.getMinutes()) + ':' + padToTwo(date.getSeconds());
}

function padToTwo(number) {
  return number = ("00"+number).slice(-2);
}
```

```
#parent {
  width: 100vw;
  height: 100vh;

  padding-bottom: 25vh;
}
#parent > div {
  padding-top: 25vh;

  -webkit-display: flex;
  display: flex;

  -webkit-flex-direction: row;
  flex-direction: row;

  -webkit-align-items: flex-start;
  align-items: flex-start;
  -webkit-justify-content: center;
  justify-content: center;
}

#items {
  width: 15vw;
  min-width: 110px;
  margin-right: 4vw;
  background-color: #222223;
  color: #eeeeef;
  border-radius: 4px;
  border: 2px solid black;
}

#items > span {
  box-sizing: border-box;
  display: block;
  padding: 5px;

  -webkit-transition: .2s background-color ease-in-out;
  transition: .2s background-color ease-in-out;

  text-align: center;

  width: 100%;

  border-radius: 4px;
}
#items > span:hover, #ticket p:hover {
  background-color: gray;
}
#items > span.selected, #ticket p.selected {
  background-color: #999999;
}
#ticket {
  -webkit-display: flex;
  display: flex;

  -webkit-flex-direction: row;
  flex-direction: row;

  margin-right: 4vw;

  color: #eeeeef;
}

#ticket p {
  margin: 1px;
  padding: 3px;
  width: 20px;
  text-align: center;
  background-color: #22222f;
  border: 2px solid black;
  border-radius: 3px;
}

#purchase {
  padding: 15px;
  padding-top: 6px;
  padding-bottom: 6px;

  background-color: #22222f;
  border: 2px solid black;
  border-radius: 3px;
  color: #eeeeef;
}
#purchase:active {
  background-color: gray;
}

#error {
  margin-top: 15px;
  color: red;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/angularjs/1.4.8/angular.js"></script>
<div id="parent" ng-app="app" ng-controller="MainCtrl">
  For testing hours-offset (If it's 6:00 setting this to 18 would simulate it being midnight): <input ng-model="hours_offset" type="number"></input>
  <div>
    <div id="items">
      <span ng-attr-class="{{selected_item===name ? 'selected' : ''}}" ng-repeat="(name, obj) in ::items track by $index" ng-click="selectItem(name)">{{::name}}<br></span>
    </div>
    <div id="ticket">
      <span ng-repeat="(ticket_index, val) in ::ticket">
        <p ng-attr-class="{{ticket[ticket_index]===$index ? 'selected' : ''}}" ng-repeat="nothing in ::nums track by $index" ng-click="ticket[ticket_index] = $index">{{::$index}}</p>
      </span>
    </div>
    <span id="purchase" ng-click="purchase()">Purchase</span>
  </div>
  <div id="error">{{error_msg}}</div>
  <table id="output">
    <tr ng-repeat="item in history track by $index">
      <td ng-repeat="(key, value) in item track by $index">{{value}}</td>
    </tr>
  </span>
</div>
```
> 5 votes

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


# Question
Title: Solve the eight queens problem at compile-time
Can you solve the eight queens puzzle at compile-time?

Pick any suitable output format.

I'm particularly interested in a C++ template metaprogramming solution, but you can use languages that have similar constructs, like, for example, Haskell's type system.

Ideally your metaprogram would output all solutions. No hardcoding.

# Answer
> 53 votes
My meta-program finds all 92 solutions. They are printed as error messages:

```
error: ‘solution’ is not a member of ‘std::integral_constant<int, 15863724>’

```

This means the first queen should be placed at y=1, the second at y=5, the third at y=8 and so on.

The meta-program consists of two mutually recursive meta-functions `put_queen` and `put_queens`:

```
#include <type_traits>

template<int queens, int rows, int sums, int difs, int x, int y>
struct put_queen;

template<int queens, int rows, int sums, int difs, int x>
struct put_queens : std::integral_constant<int,
    // try all 8 possible values for y
       put_queen<queens, rows, sums, difs, x, 1>::value
     | put_queen<queens, rows, sums, difs, x, 2>::value
     | put_queen<queens, rows, sums, difs, x, 3>::value
     | put_queen<queens, rows, sums, difs, x, 4>::value
     | put_queen<queens, rows, sums, difs, x, 5>::value
     | put_queen<queens, rows, sums, difs, x, 6>::value
     | put_queen<queens, rows, sums, difs, x, 7>::value
     | put_queen<queens, rows, sums, difs, x, 8>::value
> {};

template<int queens, int rows, int sums, int difs, int x, int y>
struct put_queen : std::conditional<
    // if blocked
    rows & (1 << y)
 || sums & (1 << (x + y))
 || difs & (1 << (x - y + 8)),
    // then backtrack
    std::integral_constant<int, 0>,
    // else recurse
    put_queens<queens * 10 + y,
               rows | (1 << y),
               sums | (1 << (x + y)),
               difs | (1 << (x - y + 8)),
               x + 1
    >
>::type {};

```

The variable `queens` stores the y coordinates of the queens placed on the board so far. The following three variables store the rows and diagonals that are already occupied by queens. `x` and `y` should be self-explanatory.

The first argument to `conditional` checks whether the current position is blocked. If it is, we backtrack by returning the (meaningless) result 0. Otherwise, the queen is placed on the board, and the recursion continues with the next column.

When `x` reaches 8, we have found a solution:

```
template<int queens, int rows, int sums, int difs>
struct put_queens<queens, rows, sums, difs, 8> {
    // print solution as error message by accessing non-existent member
    enum { value = std::integral_constant<int, queens>::solution };
};

```

Since `integral_constant` has no member `solution`, the compiler prints `queens` as an error message.

To start the recursion, we inspect the `value` member of the empty board:

```
int go = put_queens<0, 0, 0, 0, 0>::value;

```

The complete program can be found at ideone.

# Answer
> 22 votes
I came up with a solution that uses the Haskell type system. I googled a bit for an existing solution to the problem *at the value level*, changed it a bit, and then lifted it to the type level. It took a lot of reinventing. I also had to enable a bunch of GHC extensions.

First, since integers are not allowed at the type level, I needed to reinvent the natural numbers once more, this time as types:

```
data Zero -- type that represents zero
data S n  -- type constructor that constructs the successor of another natural number
-- Some numbers shortcuts
type One = S Zero
type Two = S One
type Three = S Two
type Four = S Three
type Five = S Four
type Six = S Five
type Seven = S Six
type Eight = S Seven

```

The algorithm I adapted makes additions and subtractions on naturals, so I had to reinvent these as well. Functions at the type level are defined with resort to type classes. This requires the extensions for multiple parameter type classes and functional dependencies. Type classes cannot "return values", so we use an extra parameter for that, in a manner similar to PROLOG.

```
class Add a b r | a b -> r -- last param is the result
instance Add Zero b b                     -- 0 + b = b
instance (Add a b r) => Add (S a) b (S r) -- S(a) + b = S(a + b)

class Sub a b r | a b -> r
instance Sub a Zero a                     -- a - 0 = a
instance (Sub a b r) => Sub (S a) (S b) r -- S(a) - S(b) = a - b

```

Recursion is implemented with class assertions, so the syntax looks a bit backward.

Next up were booleans:

```
data True  -- type that represents truth
data False -- type that represents falsehood

```

And a function to do inequality comparisons:

```
class NotEq a b r | a b -> r
instance NotEq Zero Zero False                -- 0 /= 0 = False
instance NotEq (S a) Zero True                -- S(a) /= 0 = True
instance NotEq Zero (S a) True                -- 0 /= S(a) = True
instance (NotEq a b r) => NotEq (S a) (S b) r -- S(a) /= S(b) = a /= b

```

And lists...

```
data Nil
data h ::: t
infixr 0 :::

class Append xs ys r | xs ys -> r
instance Append Nil ys ys                                       -- [] ++ _ = []
instance (Append xs ys rec) => Append (x ::: xs) ys (x ::: rec) -- (x:xs) ++ ys = x:(xs ++ ys)

class Concat xs r | xs -> r
instance Concat Nil Nil                                         -- concat [] = []
instance (Concat xs rec, Append x rec r) => Concat (x ::: xs) r -- concat (x:xs) = x ++ concat xs

class And l r | l -> r
instance And Nil True                    -- and [] = True
instance And (False ::: t) False         -- and (False:_) = False
instance (And t r) => And (True ::: t) r -- and (True:t) = and t

```

`if`s are also missing at the type level...

```
class Cond c t e r | c t e -> r
instance Cond True t e t  -- cond True t _ = t
instance Cond False t e e -- cond False _ e = e

```

And with that, all the supporting machinery I used was in place. Time to tackle the problem itself!

Starting with a function to test if adding a queen to an existing board is ok:

```
-- Testing if it's safe to add a queen
class Safe x b n r | x b n -> r
instance Safe x Nil n True    -- safe x [] n = True
instance (Safe x y (S n) rec,
          Add c n cpn, Sub c n cmn,
          NotEq x c c1, NotEq x cpn c2, NotEq x cmn c3,
          And (c1 ::: c2 ::: c3 ::: rec ::: Nil) r) => Safe x (c ::: y) n r
    -- safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]

```

Notice the use of class assertions to obtain intermediate results. Because the return values are actually an extra parameter, we can't just call the assertions directly from each other. Again, if you've used PROLOG before you may find this style a bit familiar.

After I made a few changes to remove the need for lambdas (which I could have implemented, but I decided to leave for another day), this is what the original solution looked like:

```
queens 0 = [[]]
-- The original used the list monad. I "unrolled" bind into concat & map.
queens n = concat $ map f $ queens (n-1)
g y x = if safe x y 1 then [x:y] else []
f y = concat $ map (g y) [1..8]

```

`map` is a higher order function. I thought implementing *higher order meta-functions* would be too much hassle (again the lambdas) so I just went with a simpler solution: since I know what functions will be mapped, I can implement specialized versions of `map` for each, so that those are not higher-order functions.

```
-- Auxiliary meta-functions
class G y x r | y x -> r
instance (Safe x y One s, Cond s ((x ::: y) ::: Nil) Nil r) => G y x r

class MapG y l r | y l -> r
instance MapG y Nil Nil
instance (MapG y xs rec, G y x g) => MapG y (x ::: xs) (g ::: rec)

-- Shortcut for [1..8]
type OneToEight = One ::: Two ::: Three ::: Four ::: Five ::: Six ::: Seven ::: Eight ::: Nil

class F y r | y -> r
instance (MapG y OneToEight m, Concat m r) => F y r -- f y = concat $ map (g y) [1..8]

class MapF l r | l -> r
instance MapF Nil Nil
instance (MapF xs rec, F x f) => MapF (x ::: xs) (f ::: rec)

```

And the last meta-function can be written now:

```
class Queens n r | n -> r
instance Queens Zero (Nil ::: Nil)
instance (Queens n rec, MapF rec m, Concat m r) => Queens (S n) r

```

All that's left is some kind of driver to coax the type-checking machinery to work out the solutions.

```
-- dummy value of type Eight
eight = undefined :: Eight
-- dummy function that asserts the Queens class
queens :: Queens n r => n -> r
queens = const undefined

```

This meta-program is supposed to run on the type checker, so one can fire up `ghci` and ask for the type of `queens eight`:

```
> :t queens eight

```

This will exceed the default recursion limit rather fast (it's a measly 20). To increase this limit, we need to invoke `ghci` with the `-fcontext-stack=N` option, where `N` is the desired stack depth (N=1000 and fifteen minutes is not enough). I haven't seen this run to completion yet, as it takes a very long time, but I've managed to run up to `queens four`.

There's a full program on ideone with some machinery for pretty printing the result types, but there only `queens two` can run without exceeding the limits :(

# Answer
> 10 votes
## C, via the preprocessor

I think the ANSI committee made a conscious choice not to extend the C preprocessor to the point of being Turing-complete. In any case, it's not really powerful enough to solve the eight queens problem. Not in any sort of general fashion.

But it can be done, if you're willing to hard-code the loop counters. There's no real way to loop, of course, but you can use self-inclusion (via `#include __FILE__`) to get a limited sort of recursion.

```
#ifdef i
# if (r_(i) & 1 << j_(i)) == 0 && (p_(i) & 1 << i + j_(i)) == 0 \
                               && (n_(i) & 1 << 7 + i - j_(i)) == 0
#  if i == 0
#   undef i
#   define i 1
#   undef r1
#   undef p1
#   undef n1
#   define r1 (r0 | (1 << j0))
#   define p1 (p0 | (1 << j0))
#   define n1 (n0 | (1 << 7 - j0))
#   undef j1
#   define j1 0
#   include __FILE__
#   undef j1
#   define j1 1
#   include __FILE__
#   undef j1
#   define j1 2
#   include __FILE__
#   undef j1
#   define j1 3
#   include __FILE__
#   undef j1
#   define j1 4
#   include __FILE__
#   undef j1
#   define j1 5
#   include __FILE__
#   undef j1
#   define j1 6
#   include __FILE__
#   undef j1
#   define j1 7
#   include __FILE__
#   undef i
#   define i 0
#  elif i == 1
#   undef i
#   define i 2
#   undef r2
#   undef p2
#   undef n2
#   define r2 (r1 | (1 << j1))
#   define p2 (p1 | (1 << 1 + j1))
#   define n2 (n1 | (1 << 8 - j1))
#   undef j2
#   define j2 0
#   include __FILE__
#   undef j2
#   define j2 1
#   include __FILE__
#   undef j2
#   define j2 2
#   include __FILE__
#   undef j2
#   define j2 3
#   include __FILE__
#   undef j2
#   define j2 4
#   include __FILE__
#   undef j2
#   define j2 5
#   include __FILE__
#   undef j2
#   define j2 6
#   include __FILE__
#   undef j2
#   define j2 7
#   include __FILE__
#   undef i
#   define i 1
#  elif i == 2
#   undef i
#   define i 3
#   undef r3
#   undef p3
#   undef n3
#   define r3 (r2 | (1 << j2))
#   define p3 (p2 | (1 << 2 + j2))
#   define n3 (n2 | (1 << 9 - j2))
#   undef j3
#   define j3 0
#   include __FILE__
#   undef j3
#   define j3 1
#   include __FILE__
#   undef j3
#   define j3 2
#   include __FILE__
#   undef j3
#   define j3 3
#   include __FILE__
#   undef j3
#   define j3 4
#   include __FILE__
#   undef j3
#   define j3 5
#   include __FILE__
#   undef j3
#   define j3 6
#   include __FILE__
#   undef j3
#   define j3 7
#   include __FILE__
#   undef i
#   define i 2
#  elif i == 3
#   undef i
#   define i 4
#   undef r4
#   undef p4
#   undef n4
#   define r4 (r3 | (1 << j3))
#   define p4 (p3 | (1 << 3 + j3))
#   define n4 (n3 | (1 << 10 - j3))
#   undef j4
#   define j4 0
#   include __FILE__
#   undef j4
#   define j4 1
#   include __FILE__
#   undef j4
#   define j4 2
#   include __FILE__
#   undef j4
#   define j4 3
#   include __FILE__
#   undef j4
#   define j4 4
#   include __FILE__
#   undef j4
#   define j4 5
#   include __FILE__
#   undef j4
#   define j4 6
#   include __FILE__
#   undef j4
#   define j4 7
#   include __FILE__
#   undef i
#   define i 3
#  elif i == 4
#   undef i
#   define i 5
#   undef r5
#   undef p5
#   undef n5
#   define r5 (r4 | (1 << j4))
#   define p5 (p4 | (1 << 4 + j4))
#   define n5 (n4 | (1 << 11 - j4))
#   undef j5
#   define j5 0
#   include __FILE__
#   undef j5
#   define j5 1
#   include __FILE__
#   undef j5
#   define j5 2
#   include __FILE__
#   undef j5
#   define j5 3
#   include __FILE__
#   undef j5
#   define j5 4
#   include __FILE__
#   undef j5
#   define j5 5
#   include __FILE__
#   undef j5
#   define j5 6
#   include __FILE__
#   undef j5
#   define j5 7
#   include __FILE__
#   undef i
#   define i 4
#  elif i == 5
#   undef i
#   define i 6
#   undef r6
#   undef p6
#   undef n6
#   define r6 (r5 | (1 << j5))
#   define p6 (p5 | (1 << 5 + j5))
#   define n6 (n5 | (1 << 12 - j5))
#   undef j6
#   define j6 0
#   include __FILE__
#   undef j6
#   define j6 1
#   include __FILE__
#   undef j6
#   define j6 2
#   include __FILE__
#   undef j6
#   define j6 3
#   include __FILE__
#   undef j6
#   define j6 4
#   include __FILE__
#   undef j6
#   define j6 5
#   include __FILE__
#   undef j6
#   define j6 6
#   include __FILE__
#   undef j6
#   define j6 7
#   include __FILE__
#   undef i
#   define i 5
#  elif i == 6
#   undef i
#   define i 7
#   undef r7
#   undef p7
#   undef n7
#   define r7 (r6 | (1 << j6))
#   define p7 (p6 | (1 << 6 + j6))
#   define n7 (n6 | (1 << 13 - j6))
#   undef j7
#   define j7 0
#   include __FILE__
#   undef j7
#   define j7 1
#   include __FILE__
#   undef j7
#   define j7 2
#   include __FILE__
#   undef j7
#   define j7 3
#   include __FILE__
#   undef j7
#   define j7 4
#   include __FILE__
#   undef j7
#   define j7 5
#   include __FILE__
#   undef j7
#   define j7 6
#   include __FILE__
#   undef j7
#   define j7 7
#   include __FILE__
#   undef i
#   define i 6
#  elif i == 7
    printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)\n",
           j0 + 1, j1 + 1, j2 + 1, j3 + 1, j4 + 1, j5 + 1, j6 + 1, j7 + 1);
#  endif
# endif
#else
#include <stdio.h>
#define _cat(a, b) a ## b
#define j_(i) _cat(j, i)
#define n_(i) _cat(n, i)
#define p_(i) _cat(p, i)
#define r_(i) _cat(r, i)
int main(void)
{
# define i 0
# define j0 0
# include __FILE__
# undef j0
# define j0 1
# include __FILE__
# undef j0
# define j0 2
# include __FILE__
# undef j0
# define j0 3
# include __FILE__
# undef j0
# define j0 4
# include __FILE__
# undef j0
# define j0 5
# include __FILE__
# undef j0
# define j0 6
# include __FILE__
# undef j0
# define j0 7
# include __FILE__
# undef j0
    return 0;
}
#endif

```

Despite the horrific amount of repetitive content, let me assure you that it truly is solving the eight queens problem algorithmically. Unfortunately the one thing that I couldn't do with the preprocessor is implement a general push-down stack data structure. The upshot is that I had to hard-code the value of `i` wherever it was used to select another value to set. (As opposed to retrieving values, which could be done completely generally. That's why the `#if` at the top of the file, which is what decides if a queen can be added at the current position, didn't need to be repeated eight times.)

Within the preprocessor code, `i` and `j` indicate the current position being considered, while `r`, `p`, and `n` keep track of which ranks and diagonals are currently unavailable for placement. However, `i` also doubles as the counter marking the current depth of recursion, so really all the other values actually use i as a sort of subscript, so that their values are preserved when resuming from a recursion. (And also because of the serious difficulty of modifying the value of a preprocessor symbol without completely replacing it.)

The compiled program prints all 92 solutions. The solutions are embedded directly into the executable; the preprocessor output looks like this:

```
/* ... #included content from <stdio.h> ... */
int main(void)
{
    printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)\n",
           0 + 1, 4 + 1, 7 + 1, 5 + 1, 2 + 1, 6 + 1, 1 + 1, 3 + 1);
    printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)\n",
           0 + 1, 5 + 1, 7 + 1, 2 + 1, 6 + 1, 3 + 1, 1 + 1, 4 + 1);
    printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)\n",
           0 + 1, 6 + 1, 3 + 1, 5 + 1, 7 + 1, 1 + 1, 4 + 1, 2 + 1);
    /* ... 88 more solutions ... */
    printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)\n",
           7 + 1, 3 + 1, 0 + 1, 2 + 1, 5 + 1, 1 + 1, 6 + 1, 4 + 1);
    return 0;
}

```

It can be done, even though it clearly shouldn't.

# Answer
> 8 votes
Here's a C++11 solution without any templates:

```
constexpr int trypos(
    int work, int col, int row, int rows, int diags1, int diags2,
    int rowbit, int diag1bit, int diag2bit);

constexpr int place(
    int result, int work, int col, int row, int rows, int diags1, int diags2)
{
    return result != 0 ? result
        : col == 8 ? work
        : row == 8 ? 0
        : trypos(work, col, row, rows, diags1, diags2,
                 1 << row, 1 << (7 + col - row), 1 << (14 - col - row));
}

constexpr int trypos(
    int work, int col, int row, int rows, int diags1, int diags2,
    int rowbit, int diag1bit, int diag2bit)
{
    return !(rows & rowbit) && !(diags1 & diag1bit) && !(diags2 & diag2bit)
        ? place(
            place(0, work*10 + 8-row, col + 1, 0,
                  rows | rowbit, diags1 | diag1bit, diags2 | diag2bit),
            work, col, row + 1, rows, diags1, diags2)
        : place(0, work, col, row + 1, rows, diags1, diags2);
}

int places = place(0, 0, 0, 0, 0, 0, 0);

```

The solution is encoded as decimal digits, as in FredOverflow's answers. GCC 4.7.1 compiles the above file into the following assembly source with `g++ -S -std=c++11 8q.cpp`:

```
    .file   "8q.cpp"
    .globl  places
    .data
    .align 4
    .type   places, @object
    .size   places, 4
places:
    .long   84136275
    .ident  "GCC: (GNU) 4.7.1"
    .section    .note.GNU-stack,"",@progbits

```

The value of the symbol `places` is 84136275, i.e. the first queen is at a8, the second at b4 etc.

# Answer
> 0 votes
c++ template, with only one template class is defined:

```
template <int N, int mask, int mask2, int mask3, int remainDigit, bool fail>
struct EQ;

template <int N, int mask, int mask2, int mask3>
struct EQ<N, mask, mask2, mask3, 0, false> {
    enum _ { Output = (char [N])1 };
};

template <int N, int mask, int mask2, int mask3, int i>
struct EQ<N, mask, mask2, mask3, i, true> { };

template <int N, int mask, int mask2, int mask3, int i>
struct EQ<N, mask, mask2, mask3, i, false> {
    enum _ { _ =
             sizeof(EQ<N*10+1, mask|(1<<1), mask2|(1<<(1+i)), mask3|(1<<(1+8-i)), i-1,
               (bool)(mask&(1<<1)) || (bool)(mask2&(1<<(1+i))) || (bool)(mask3&(1<<(1+8-i)))>) +
             sizeof(EQ<N*10+2, mask|(1<<2), mask2|(1<<(2+i)), mask3|(1<<(2+8-i)), i-1,
               (bool)(mask&(1<<2)) || (bool)(mask2&(1<<(2+i))) || (bool)(mask3&(1<<(2+8-i)))>) +
             sizeof(EQ<N*10+3, mask|(1<<3), mask2|(1<<(3+i)), mask3|(1<<(3+8-i)), i-1,
               (bool)(mask&(1<<3)) || (bool)(mask2&(1<<(3+i))) || (bool)(mask3&(1<<(3+8-i)))>) +
             sizeof(EQ<N*10+4, mask|(1<<4), mask2|(1<<(4+i)), mask3|(1<<(4+8-i)), i-1,
               (bool)(mask&(1<<4)) || (bool)(mask2&(1<<(4+i))) || (bool)(mask3&(1<<(4+8-i)))>) +
             sizeof(EQ<N*10+5, mask|(1<<5), mask2|(1<<(5+i)), mask3|(1<<(5+8-i)), i-1,
               (bool)(mask&(1<<5)) || (bool)(mask2&(1<<(5+i))) || (bool)(mask3&(1<<(5+8-i)))>) +
             sizeof(EQ<N*10+6, mask|(1<<6), mask2|(1<<(6+i)), mask3|(1<<(6+8-i)), i-1,
               (bool)(mask&(1<<6)) || (bool)(mask2&(1<<(6+i))) || (bool)(mask3&(1<<(6+8-i)))>) +
             sizeof(EQ<N*10+7, mask|(1<<7), mask2|(1<<(7+i)), mask3|(1<<(7+8-i)), i-1,
               (bool)(mask&(1<<7)) || (bool)(mask2&(1<<(7+i))) || (bool)(mask3&(1<<(7+8-i)))>) +
             sizeof(EQ<N*10+8, mask|(1<<8), mask2|(1<<(8+i)), mask3|(1<<(8+8-i)), i-1,
               (bool)(mask&(1<<8)) || (bool)(mask2&(1<<(8+i))) || (bool)(mask3&(1<<(8+8-i)))>)};
};
int main(int argc, _TCHAR* argv[])
{
    // output all solutions to eight queens problems as error messages
    sizeof(EQ<0, 0, 0, 0, 8, false>);
    return 0;
}

```

so the error message will be looked like:

error C2440: 'type cast' : cannot convert from 'int' to 'char \[15863724\]'

---
Tags: puzzle-solver, compile-time
---


title: All primes from 0 to 1000

text:
# Question
Title: All primes from 0 to 1000
Is it possible to make this C code smaller? It prints out all primes from 0 to 1000.

**C, 89 chars**

```
int i,p,c;for(i=2;i<1e3;i++){c=0;for(p=2;p<i;p++)if(i%p==0)c++;if(c==0)printf("%u\n",i);}

```

# Answer
**~~59~~ 57 bytes**

Based on @feersum solution but the primality check can be golfed further

```
for(int p=1,d;d=p++%999;d||printf("%d\n",p))for(;p%d--;);

```

Edited based on Runer112's comments
> 7 votes

# Answer
# 67 bytes

In C there's no real alternative to trial division, but it can certainly be golfed a bit.

```
for(int p=1,d;p++<999;d&&printf("%d\n",p))for(d=p;--d>1;)d=p%d?d:1;

```

Requires C99 initial declarations, which saves 1 byte.
> 10 votes

# Answer
*(I wrote this not realizing the size limitations on integers in C, so it's likely not actually useful for shortening the code.)*

First, a word about algorithm. Before golfing your code, you should think about the best overall strategy to get the result.

You're checking primality by doing trial division -- testing each potential divisor `p` of `i`. That's costly in characters because it takes two loops. So, testing primality without a loop is likely to save characters.

An often shorter approach is to use Wilson's Theorem: the number `n` is prime if and only if

```
fact(n-1)%n == n-1

```

where `fact` is the factorial function. Since you're testing all possible `n` from `1` to `1000`, it's easy to avoid implementing factorial by keeping track of the running product `P` and updating it by `P*=n` after each loop. Here's a Python implementation of this strategy to print primes up to a million.

Alternatively, the fact that your program only has to be right up to 1000 opens up another strategy: the Fermat primality test. For some `a`, every prime `n` satisfies

```
pow(a,n-1)%n == 1

```

Unfortunately, some composites `n` also pass this test for some `a`. These are called Fermat pseudoprimes. But, `a=2` and `a=3` don't fail together until `n=1105`, so they suffice for your purpose of checking primes until 1000. (If 1000 were instead 100, you'd be able to use only `a=2`.) So, we check primality with (ungolfed code)

```
pow(2,n-1)%n == 1 and pow(3,n-1)%n == 1

```

This also fails to recognize primes 2 and 3, so those would need to be special-cased.

Are these approaches shorter? I don't know because I don't code in C. But, they're ideas you should try before you settle on a piece of code to start eking out characters.
> 6 votes

# Answer
# ~~78~~ 77 characters

(Just applied some tricks learned in other languages.)

```
int i=0,p,c;for(;i<1e3;i++){c=0;for(p=2;p<i;)c+=i%p++<1;c||printf("%u\n",i);}

```

## 76 characters in C99 mode

```
for(int i=0,p,c;i<1e3;i++){c=0;for(p=2;p<i;)c+=i%p++<1;c||printf("%u\n",i);}

```
> 4 votes

# Answer
## 58 chars (or 61 for a complete program)

Another reuse of my answer to a similar question.
**EDIT**: stand-alone code piece, no function to call.

```
for(int m,n=2;n<999;m>1?m=n%m--?m:n++:printf("%d\n",m=n));

```

Complete program:

```
n=2;main(m){n<999&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}

```
> 2 votes

# Answer
# ~~67~~ 64 bytes

Inspired by Alchymist's solution :

```
int i=1,p;for(;i++<1e3;p-i||printf("%d\n",i)){p=1;while(i%++p);}

```
> 1 votes

---
Tags: code-golf, number, tips, primes, c
---


title: Flaming Doorknob Keyboards!

text:
# Question
Title: Flaming Doorknob Keyboards!
Well, turns out Doorknob's username on GitHub, Reddit, and other sites is KeyboardFire. That gives me an idea...

## The task

You work at KeyboardFire Inc., a company that makes special keyboards. And, by "special", I mean that, whenever you press a key, something in your house lights on fire! With the new KeyboardFire Doorknob series, the objects that light on fire are doorknobs.

*However*, because of stupid government regulations, your users need to know which doorknobs in their house wil light on fire.

Consider this ASCII art of a portion of a QWERTY keyboard:

```
1|2|3|4|5|6|7|8|9|0
 q|w|e|r|t|y|u|i|o|p
  a|s|d|f|g|h|j|k|l
   z|x|c|v|b|n|m

```

(The `|`'s represent the boundaries between keys.)

We can treat this exact ASCII drawing as a "graph" of sorts, where each character in the range `[a-z0-9]` has an x (horizontal) and y (vertical) index, where `(0,0)` is `1`. For instance, the letter `d` has the coordinates `(2,6)` (pipes and spaces are included in the coordinate calculation).

Now let's think about each user's house. Every house can be drawn top-down view as a 20x4 ASCII art (in this world where it's legal to sell destructive keyboards, every house is the same size). We can use `D`'s to mark the positions of each doorknob in the house. Here's an example:

```
D         D  D     D
    D

              D  D

```

We'll call this the "house map". (Yes, that's a lot of doorknobs!)

Pressing any key will light the nearest doorknob on fire. For instance, if we take the previous coordinates of the letter `d`, the nearest doorknob (by Manhattan distance) is at the coordinates `(1,4)`. This is the doorknob that will light on fire when the letter `d` is hit. If we were to mark the flaming doorknob with an `F`, the result would be:

```
D         D  D     D
    F

              D  D

```

## The specs

Your program will take two inputs:

* A string that matches the pattern `[a-z0-9]+`.
* A house map. This can be a string, a list of strings, or something equivalent.

You need to go through each letter of the string and light the respective doorknob on fire (change its letter to an `F`). If the nearest doorknob is already on fire, leave it as-is. If there is more than 1 doorknob that could be lit on fire using the this method, you can light whichever one you want.

After the whole string is processed in this manner, you need to print the resulting house map.

Code-golf, so shortest program wins. Standard loopholes banned as usual.

## Example

String:

```
helloworld123

```

House map:

```
D    D       D     D
    D

              D  D

```

Possible results:

```
F    F       F     D
    F

              D  F

```

Or:

```
F    D       F     D
    F

              D  F

```

Or:

```
F    F       D     D
    F

              F  F

```

Or:

```
F    D       D     D
    F

              F  F

```

**EDIT:** Uh...is there a reason I have one answer, even with a +50 bounty? If you find the directions complicated/vague, I'd be glad if you posted in the comments or something...or of I'm doing anything wrong...

**EDIT 2:** Bounty expires in under a day! Post something else! Please! PLEASE!!!! :(

# Answer
# JavaScript (ES6), 204 bytes

```
(s,h)=>[...s].map(c=>(o="1234567890qwertyuiopasdfghjkl_zxcvbnm".search(c),y=o/10|0,x=o%10*2+y,n=a=Math.abs,h.map((k,i)=>k.match(/\s/)||(d=a(x-i%21)+a(y-i/21|0))>n||(n=d,p=i)),h[p]="F"),h=[...h])&&h.join``

```

Fine, I'll answer it. ;)

## Explanation

```
(s,h)=>
  [...s].map(c=>(                     // iterate through each character of the input

    // Get X and Y coordinates of the character input
    o="1234567890qwertyuiopasdfghjkl_zxcvbnm".search(c),
    y=o/10|0,
    x=o%10*2+y,

    // Find the nearest doorknob
    n=                                // n = Manhattan distance to nearest doorknob
      a=Math.abs,
    h.map((k,i)=>                     // iterate through each character of the house
      k.match(/\s/)||                 // do not check distance to whitespace characters
        (d=a(x-i%21)+a(y-i/21|0))>n|| // d = distance to the current doorknob
          (n=d,                       // set the nearest doorknob to this one
          p=i)                        // p = position of the doorknob
    ),
    h[p]="F"                          // update the doorknob to "F" in the house string
  ),h=[...h])&&h.join``               // return the house map as a string

```

## Test

```
<input type="text" id="input" value="helloworld123" /><br />
<textarea id="house" rows="4" cols="20">D    D       D     D
    D

              D  D  </textarea><br />
<button onclick='result.innerHTML=(

(s,h)=>[...s].map(c=>(o="1234567890qwertyuiopasdfghjkl_zxcvbnm".search(c),y=o/10|0,x=o%10*2+y,n=a=Math.abs,h.map((k,i)=>k.match(/\s/)||(d=a(x-i%21)+a(y-i/21|0))>n||(n=d,p=i)),h[p]="F"),h=[...h])&&h.join``

)(input.value,house.value)'>Go</button>
<pre id="result"></pre>
```
> 3 votes

# Answer
## Ruby, 229 bytes

```
->s,m{c=m.flat_map.with_index{|x,i|x.size.times.select{|j|x[j]==?D}.map{|y|[i,y]}}
s.chars{|h|x='1234567890qwertyuiop*asdfghjkl*zxcvbnm'.index h
x,y=(x%10)*2,x/10
a,b=c.min_by{|a,b|(y-a).abs+((y%2>0?x+1:x)-b).abs}
m[a][b]='F'}
m}

```

Not very good, but I just *had* to get the first answer in.

Slightly ungolfed / commented version:

```
#!/usr/bin/ruby

f = -> s, m {
    # get knob coords
    c = m.flat_map.with_index {|x, i| x.size.times.select{|j| x[j] == ?D }.map{|y| [i, y] } }
    # for each char in the string
    s.chars {|h|
        # note the asterisks to correct for offsets
        x = '1234567890qwertyuiop*asdfghjkl*zxcvbnm'.index h
        # get un-"staggered" x and y coords
        x, y = (x % 10) * 2, x / 10
        # add one to x for every other row to fit keyboard
        x += 1 if y % 2 > 0
        # find closest knob by Manhattan distance
        a, b = c.min_by{|a, b| (y - a).abs + (x - b).abs }
        # LIGHT IT ON FIRE!
        m[a][b] = 'F'
    }
    # return new map
    m
}

puts f['helloworld123', ['D    D       D     D', '    D', '', '              D  D']]

```
> 12 votes

---
Tags: code-golf, keyboard
---