title: Play the word chain

text:
# Question
Title: Play the word chain
When I was younger, I use to play a word game called Word chain. It was very simple. The first player chooses a word; the next player says another word that starts with the same letter the previous word ended with. This goes on forever until somebody gives up! Trick is, you cannot use the same word twice (unless everybody forgot that word was even used!). Usually we play with a certain topic to make it harder. But now, I want you to make a program to do this for me.

## Challenge

Write a full program or function to find all longest possible word chains using a given set of words and start word.

This is , so the shortest code wins!

### Input

There are two inputs: a list and a start word. The start word will not be in the list. The inputs are all lowercase ASCII, and the list will not contain duplicate words.

### Output

All sequences of words from the list such that:

* The start word is the first word in the sequence.
* Each subsequent word starts with the same letter as the last letter of the previous word.
* The length of the sequence is the **longest possible**.

If there are multiple longest sequences, output all of them.

The sequence does not necessarily need to contain all of the list words. Sometimes that is not possible (see testcases). Again, no word can be used twice!

**Testcases**

```
In: [hello, turtle, eat, cat, people] artistic
Out:  [artistic, cat, turtle, eat]
In: [lemonade, meatball, egg, grape] ham
Out: [ham, meatball, lemonade, egg, grape]
In: [cat, cute, ewok] attic
Out: [attic, cute, ewok]
In:[cat, cute, ewok, kilo, to, otter] attic
Out: [attic, cute, ewok, kilo, otter]
In:[cat, today, yoda, attic] ferret
Out: [ferret, today, yoda, attic, cat]
In: [cancel, loitering, gnocchi, improv, vivic, child, despair, rat, tragic, chimney, rex, xylophone] attic
Out: [[attic, child, despair, rat, tragic, cancel, loitering, gnocchi, improv, vivic, chimney], [attic, cancel, loitering, gnocchi, improv, vivic, child, despair, ra', tragic, chimney]]
In: [cat, today, yoda, artistic, cute, ewok, kilo, to, otter] attic
Out: [attic, cat, today, yoda, artistic, cute, ewok, kilo, otter]

```

# Answer
> 9 votes
# Pyth, ~~25~~ 23 bytes

```
.MlZfqhMtTeMPT+Lzs.pMyQ

```

Test suite

A brute force solution. Far too slow for some of the larger test cases.

Input in the form:

```
attic
["cat", "today", "yoda", "to", "otter"]

```

Output in the form:

```
[['attic', 'cat', 'today', 'yoda'], ['attic', 'cat', 'to', 'otter']]

```

**Explanation:**

```
.MlZfqhMtTeMPT+Lzs.pMyQ
                           Q = eval(input()) (The list of words)
                           z = input()       (The starting word)
                     yQ    All subsets of the input.
                  .pM      All permutations of the subsets.
                 s         Flatten.
              +Lz          Add the starting word to the front of each list.
                           This is all possible sequences.
    f                      Filter on
     q                     The equality of
      hMtT                 The first character of each word but the first
          eMPT             The last character of each word but the last
.MlZ                       Take only the lists of maximal length.

```

# Answer
> 4 votes
# JavaScript (ES6), 164 bytes

```
f=(l,s,r=[[]])=>l.map((w,i)=>w[0]==s.slice(-1)&&(x=l.slice(),x.splice(i,1),o=f(x,w),a=o[0].length,b=r[0].length,r=a>b?o:a<b?r:r.concat(o)))&&r.map(q=>[s].concat(q))

```

## Explanation

A recursive function that checks how long the output list will for all possible choices.

Returns an array of arrays of words.

```
f=(l,s,r=[[]])=>            // l = list, s = starting word, r is not passed (it is
                            //     here so that it is not defined globally)
  l.map((w,i)=>             // for each word w at index i
    w[0]==s.slice(-1)&&(    // if the first letter is the same as the last letter:
      x=l.slice(),          // x = clone of the list of words
      x.splice(i,1),        // remove the current word
      o=f(x,w),             // get the list of words starting from the current word
      a=o[0].length,
      b=r[0].length,
      r=a>b?o:              // if o is longer, set r to o
        a<b?r:              // if o is shorter, keep r
        r.concat(o)         // if o is same, add it to r
    )
  )
  &&r.map(q=>[s].concat(q)) // return a list of longest lists with the starting word

```

## Test

Default parameter not used in test to make it more cross-browser compatible.

```
f=(l,s,r)=>l.map((w,i)=>w[0]==s.slice(-1)&&(x=l.slice(),x.splice(i,1),o=f(x,w),a=o[0].length,b=r[0].length,r=a>b?o:a<b?r:r.concat(o)),r=[[]])&&r.map(q=>[s].concat(q))
```

```
Word list (space separated) = <input type="text" id="list" value="cancel loitering gnocchi improv vivic child despair rat tragic chimney rex xylophone" /><br />
Starting word = <input type="text" id="word" value="attic" /><br />
<button onclick="result.textContent=f(list.value.split(' '),word.value).join('\n')">Go</button>
<pre id="result"></pre>
```

# Answer
> 4 votes
## Python, 104

```
def f(d,w):
 a=[[w]]
 while a:b=a;a=[x+[y]for x in a for y in set(d)-set(x)if x[-1][-1]==y[0]]
 return b

```

I think it should work now...

Try it online.

# Answer
> 1 votes
# Perl 5 , 275 bytes

Probably not golfed as much as it can be, but, hey, it's nonwinning anyway, right?

```
use List::Util max;use List::MoreUtils uniq,before;use Algorithm::Permute permute;$i=pop;permute{push@c,[@ARGV]}@ARGV;for$c(@c){unshift@$c,$i;push @{$d{before{(substr$c->[$_],-1)ne(substr$c->[1+$_],0,1)}keys$c}},$c}for$m(max keys%d){say for uniq map{"@$_[0..$m+1]"}@{$d{$m}}}

```

Use it thus:

```
$ perl -M5.010 chain.pl cat tin cot arc
arc cat tin
arc cot tin

```

Warning! Use of this script on a long list requires lots of memory! It worked great for me on seven (six plus the extra one) but not on thirteen (twelve plus one).

It removes the final input, generates an array of arrayrefs, where the arrayrefs are all the permutations, and adds the initial word back on at the start. Then it pushes each such permutation onto another arrayref which is the value of a hash with key the amount of the array that has the chaining property desired. It then finds the maximum such key and prints out all the arrays.

# Answer
> 0 votes
## C, 373 bytes

```
g(char*y){printf("%s, ",y);}z(char*w){int i,k=-1,v=0,j=sizeof(c)/sizeof(c[0]);int m[j],b=0;for(i=0;i<j;i++){m[v++]=c[i][0]==w[strlen(w)-1]?2:1;if(u[i]==6)m[v-1]=1;if(strcmp(w,c[i]))k=i;}printf("%s",w);for(i=0;i<j;i++){if(m[i]!=1){if(v+i!=j){g(s);for(;b<j;b++){if(u[b]==6)g(c[b]);}}else printf(", ");u[i]=6;z(c[i]);u[i]=1;}else v+=-1;}if(k!=-1)u[k]=1;if(v==0)printf(" ; ");}

```

I believe there is probably a lot more golfing I could do here so I will probably update it.

De-golf

```
char *c[9]={"cat","today","yoda","artistic","cute","ewok","kilo","to","otter"};
u[9]={-1};
char *s="attic";

g(char*y){printf("%s, ",y);}
z(char*w){
   int i,k=-1,v=0,j=sizeof(c)/sizeof(c[0]);
   int m[j],b=0;
   for(i=0;i<j;i++){
      m[v++]=c[i][0]==w[strlen(w)-1]?i:-1;
      if(u[i]==6)m[v-1]=-1;
      if(strcmp(w,c[i]))k=i;
   }
   printf("%s",w);
   for(i=0;i<j;i++){
      if(m[i]!=-1){
         if(v+i!=j){
            g(s);
            for(;b<j;b++){
                if(u[b]==6)g(c[b]);
             }
         }else printf(", ");
         u[i]=6;
         z(c[i]);
         u[i]=-1;
      } else v+=-1;
   }
   if(k!=-1)u[k]=-1;
   if(v==0)printf(" ; ");
}

main(){
   z(s);
   printf("\n");
   return 0;
}

```

Ideone link \- If I didn't do this right just let me know :D

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


# Question
Title: Use xkcd's formula to approximate the world population
In xkcd 1047, Randall Munroe lists "slightly wrong" approximations of assorted quantities and numbers with varying precision and complexity, such as that the number of liters in a gallon is very close to 3 + π4. In the middle of the comic, he gives an intermission: a way to estimate the world (and United States) population based for a given year.

(Cropped from xkcd: Approximations by Randall Munroe)

Your task is to write a program that implements these formulas to approximate the current world and U.S. populations, replicated as follows.

## World population

1. Take the last two digits of the current year.
2. Subtract the number of leap years (including the current year) since Hurricane Katrina (2005). For these purposes, any year divisible by 4 is considered a leap year.
3. Add a decimal point between the two numbers (the same as dividing by 10).
4. Add 6. This gives the result in billions of people.

## U.S. population

1. Take the last two digits of the current year.
2. Subtract 10.
3. Multiply by 3.
4. Add 10.
5. Add 3 to the beginning (for this challenge, some numbers will be negative, so add 300 instead). Somehow I didn't notice that just concatenating wouldn't work because the program I used to generate the results just added 300.
6. This gives the result in millions of people.

# Details

This formula "should stay current for a decade or two," but you must be able to theoretically handle any year 2000–2039 inclusive. For some cases, the leap years since Katrina will have a negative or zero value.

You are free to simplify the formula in any way, as long as all outputs match the ones below.

**For the year, use the year according to the computer's clock.** It must work next year and any other year this century, so you cannot simply hardcode 2015. For convenience, you might want to include a way to specify the year as a variable or input to test other years.

The output should be the approximated world population (in billions of people), followed by some delimiter (e.g. space or comma), followed by the U.S. population (in millions of people). You may also write a function that returns or prints a string or an array of numbers or strings.

This is code golf, so shortest code in bytes wins. Tiebreaker is earliest post.

# Test cases

This is a list of all possible years, followed by the two outputs.

```
Year   World  U.S.
2000    6.1   280
2001    6.2   283
2002    6.3   286
2003    6.4   289
2004    6.4   292
2005    6.5   295
2006    6.6   298
2007    6.7   301
2008    6.7   304
2009    6.8   307
2010    6.9   310
2011    7     313
2012    7     316
2013    7.1   319
2014    7.2   322
2015    7.3   325
2016    7.3   328
2017    7.4   331
2018    7.5   334
2019    7.6   337
2020    7.6   340
2021    7.7   343
2022    7.8   346
2023    7.9   349
2024    7.9   352
2025    8     355
2026    8.1   358
2027    8.2   361
2028    8.2   364
2029    8.3   367
2030    8.4   370
2031    8.5   373
2032    8.5   376
2033    8.6   379
2034    8.7   382
2035    8.8   385
2036    8.8   388
2037    8.9   391
2038    9     394
2039    9.1   397

```

# Answer
# Pyth, ~~21~~ 20 bytes

*-1 byte by Dennis*

```
c/J-*3.d3C\ᙹ4T+33J

```

These have the same byte count but are ASCII-only:

```
c/J%*3.d3 523 4T+33J
c/-J%*3.d3*44T33 4TJ

```

I don't know Pyth, so still ~~probably~~ possibly golfable. Using the same algorithm:

# TI-BASIC, 23 bytes

```
max(3getDate-5753
{.1int(Ans/4),Ans+33

```

`getDate` returns a list of three floats `{YYYY,MM,DD}` in some order depending on the date format setting (TI-84s don't have a true int datatype); the `max(` will be the year. Multiplying and subtracting inside the `max(` saves a close-paren.
> 23 votes

# Answer
# Javascript (ES6), ~~55~~ ~~54~~ 48 bytes

```
-~((n=Date().substr(13,2)*3+280)/4-9.1)/10+' '+n

```

Works in Firefox 33; theoretically supports all years from 2000 to 2099. If programs that dump the result onto the console are not allowed, use this 51-byte function:

```
(n=Date().substr(13,2)*3+280)=>-~(n/4-9.1)/10+' '+n

```

Full program, 55 bytes:

```
n=Date().substr(13,2)*3+280,alert(-~(n/4-9.1)/10+' '+n)

```

~~Getting the year was quite expensive, but after using the deprecated `getYear()` instead of `getFullYear()`, all of the numbers in the equation became smaller, saving a lot of bytes.~~ **EDIT:** Thanks to an eeevil trick, I skipped `new` and `getYear()` altogether. \>:D

Suggestions welcome!
> 16 votes

# Answer
# Python 2, 80 bytes

```
from datetime import*
y=date.today().year%40
print int(61.55+.75*y)/10.,y*3+280

```

Now rounds!
> 10 votes

# Answer
# Pyth, 30 bytes

```
.R+*.075J%.d3C\d6.105 1+*3J280

```

My first Pyth program!

Thanks @Jakube for some hints (I would never have thought of those!)
> 10 votes

# Answer
# CJam, 28 bytes

```
et0=100%__4/(-Ad/6+S@3*280+

```

Try it online

To try years other than the current one, replace the `et0=` at the start with the literal value of the year.
> 6 votes

# Answer
# Python 3, 134 bytes

Works well but seems a bit long

```
from datetime import*
y=str(date.today().year)
z=int(y[2:])
m=str(60+(z-int((int(y)-2005)/4)))
print("%s.%s"%(m[0],m[1]),310+(z-10)*3)

```
> 5 votes

# Answer
## AutoIt - ~~60~~ ~~58~~ 56 bytes

```
$_=@YEAR-2e3
ClipPut(($_-Int($_/4-1))/10+6&' 3'&3*$_-20)

```

~~The rounding eats bytes~~ (not anymore). I have now tweaked both formulas. Some sample outputs:

```
7.3 325 // 2015
7.3 328
7.4 331
7.5 334 // 2018
8.4 370 // 2030

```

They all seem to be accurate.

A tip: Order of execution saves bytes on parentheses. For example: `(a-4)/4 = a/4-1` :-).
> 5 votes

# Answer
# PowerShell, ~~53~~ 45 Bytes

```
$n=date -f yy;.1*[int](61.45+.75*$n);280+3*$n

```

Uses a similar rounding trick as muddyfish's Python 2 answer to simplify the world population calculation, since PowerShell implicitly `Round()`s when you cast from a `[double]` to an `[int]`, rather than truncating.

For the output, we assume that *"followed by some delimiter (e.g. space or comma)"* can also mean "newline", so we execute one result and then the second. PowerShell implicitly writes out results, so we don't need to explicitly call any printing commands.
> 4 votes

# Answer
# Mathematica, 50 bytes

```
n=Today["YearShort"];{.1*(61+n-Floor[n/4]),280+3n}

```

Note that this is dependent on having a Wolfram Engine with Version number 10+ (released 2014) due to dependence on `DateObjects`.

# R, 64 bytes

```
n=as.numeric(format(Sys.time(),"%y"))
c(.1*(61+n-n%/%4),280+3*n)

```

Direct port of Mathematica code, think I had a shorter solution but dependent on packages whereas this works with base R.
> 3 votes

# Answer
# Java, ~~180~~ ~~177~~ ~~166~~ ~~152~~ 143 bytes

Thanks Thomas for helping a noob out :)

```
class D{public static void main(String[]a){int f=java.time.LocalDate.now().getYear();System.out.printf("%.1f %d\n",(3.*f-5755)/40,3*f-5720);}}

```

Ungolfed version:

```
class D {
  public static void main(String[]a) {
    int f = java.time.LocalDate.now().getYear();
    System.out.printf("%.1f %d\n",(3.*f-5755)/40,3*f-5720);
  }
}

```

Requires Java 8.
> 3 votes

# Answer
# JavaScript (ES6) 52

A function returning the output as an array.

```
(y=(new Date).getYear())=>[(y+~(y/4)-13)/10,y*3-20]

```

Just for testing purpose, the function accepts an input equals to current year - 1900 (e.g. 105 for 2015)

That's in the line of the ETHproductions' answer (the math is the math) but avoding the *evil trick* it is more portable in different locales. And as a function it's 1 byte shorter.

Test snippet:

```
f=(y=(new Date).getYear())=>[(y+~(y/4)-13)/10,y*3-20]

o=[];
for(a=2000;a<2050;a++)o.push(`<td>${a}</td><td>${f(a-1900)}</td>`);
document.write(`<table><tr>${o.join`</tr><tr>`}</tr></table>`)
```

```
td { text-align:right; font-family:monospace }
```
> 3 votes

# Answer
# Desmos, 140 Bytes

I'm counting a newline to be a signal for a new equation. Folders on the link are just for organization.

## Golfed, 140 Bytes

Click `add slider` when prompted.

```
a=6+.1b-.1c
d=280+3b
c=\sum_{n=2005}^q\left\{0=\operatorname{mod}\left(n,4\right),0\right\}
b=100\left|\operatorname{floor}\left(.01q\right)-.01q\right|

```

# Ungolfed, 261 Bytes

```
p_{world}=6+\frac{l_{astdig}-l_{eap}}{10}
p_{us}=310+3\left(l_{astdig}-10\right)
y_{ear}=2039
l_{eap}=\sum _{n=2005}^{y_{ear}}\left\{0=\operatorname{mod}\left(n,4\right),0\right\}
l_{astdig}=100\left|\operatorname{floor}\left(\frac{y_{ear}}{100}\right)-\frac{y_{ear}}{100}\right|

```
> 3 votes

# Answer
# Ruby, 57 bytes

```
y=Time.now.year%40;puts "#{6+(y-(y-5)/4)*0.1} #{3*y+280}"

```

Unfortunately, `Time.now.year` really costs some characters.
> 2 votes

# Answer
# Glava, 77 bytes

```
i|f=java.time.LocalDate.now().getYear();F("%.1f %d\n",(3.*f-5755)/40,3*f-5720

```

A translation of my Java answer.
> 2 votes

# Answer
# APL, ~~25~~ ~~23~~ 29 bytes

```
{(10÷⍨⌊⍵÷4),⍵+33}⊃¯5753+3×⎕TS

```

TryAPL

Yes, it's 29 *bytes*.
> 1 votes

# Answer
# PHP, 45 bytes

The code:

```
echo(int)(($x=3*date(y)+247)/4)*.1," ",$x+33;

```

Because `y` (the argument of `date()`) is an undefined constant, PHP triggers a notice (that can be muted) and converts it to a string (as we need); this PHP courtesy allows saving 2 bytes.

In order to suppress the notice, the program needs to be run using the `error_reporting=0` runtime directive, like this:

```
$ php -d error_reporting=0 -r 'echo(int)(($x=3*date(y)+247)/4)*.1," ",$x+33;'
7.3 325

```

### For testing

By replacing the call to `date(y)` with `$argv[1]` (the first command line argument), the program length increases with 1 byte but it can get the year from the command line.

The expected argument is the year minus 2000; it also works for negative values (years before 2000) or values greater than 40 (after year 2040).

```
$ php -r 'echo(int)(($x=3*$argv[1]+247)/4)*.1," ",$x+33;' 00
6.1 280

$ php -r 'echo(int)(($x=3*$argv[1]+247)/4)*.1," ",$x+33;' 01
6.2 283

$ php -r 'echo(int)(($x=3*$argv[1]+247)/4)*.1," ",$x+33;' 02
6.3 286

$ php -r 'echo(int)(($x=3*$argv[1]+247)/4)*.1," ",$x+33;' 03
6.4 289

$ php -r 'echo(int)(($x=3*$argv[1]+247)/4)*.1," ",$x+33;' 04
6.4 292

$ php -r 'echo(int)(($x=3*$argv[1]+247)/4)*.1," ",$x+33;' 15
7.3 325

$ php -r 'echo(int)(($x=3*$argv[1]+247)/4)*.1," ",$x+33;' 39
9.1 397

```
> 1 votes

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


title: Forgotten Realms date calculator

text:
# Question
Title: Forgotten Realms date calculator
In an effort to level the playing field between languages with built-in date libraries and those without, let's work with a fictional calendar. The Forgotten Realms are a (*the?*) campaign setting for Dungeons & Dragons. Of course, each have their own calendar.

## The Calendar of Harptos

Conveniently, a year in the Forgotten Realms also has 365 days. Furthermore, the calendar also has 12 months. However, this is where it gets interesting. Each month is exactly 30 days long. The remaining 5 days are holidays which fall *between* the months. Here are the months and holidays in order (with holidays indented):

```
1   Deepwinter
        Midwinter
2   The Claw of Winter
3   The Claw of the Sunsets
4   The Claw of the Storms
        Greengrass
5   The Melting
6   The Time of Flowers
7   Summertide
        Midsummer
        [Shieldmeet]
8   Highsun
9   The Fading
        Highharvestide
10  Leaffall
11  The Rotting
        The Feast of the Moon
12  The Drawing Down

```

Notice that I've inserted a sixth holiday in brackets. This is the leap day which only occurs every four years (yes, that's it — there are no additional shenanigans with the centuries).

Side note about month names: each month has a formal and a common name. The above are the common names. I've picked those because I think they allow for more interesting compression.

There are several numberings of the years, but the most widespread one is *Dalereckoning*, shortened to *DR*. (Also, every year has one or more names, but we're not going to bother with that.)

The components of a date should be separated by a comma and a space. All in all, a valid date might look like:

```
4, The Melting, 1491 DR

```

or

```
Shieldmeet, 1464 DR

```

Note that there is no day number for the holidays. (I suppose `4th of The Melting` would be nicer for the days of the months, but I don't want to drag ordinal numbers into this.)

Footnote: I came up with this when xnor complained that every single date challenge needs the leap year computation. I've failed in eliminating it completely, but at least it's only a single modulo in this calendar.

## The Challenge

Given a valid date of the Calendar of Harptos, as well as an integer `D`, output the date `D` days later. Note that `D` may be negative, in which case you should return the date `D` days earlier.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You may assume that the year is positive and less than 2000.

Standard rules apply.

## Test Cases

The first dozen or so test cases should test all the edge cases surrounding holidays and leap years. The next set are to test that ranges across multiple years work and all months and holidays have been implemented. The second half is all the same test cases again but with negative offsets.

```
"30, Summertide, 1491 DR" 1                 => "Midsummer, 1491 DR"
"30, Summertide, 1491 DR" 2                 => "1, Highsun, 1491 DR"
"Midsummer, 1491 DR" 1                      => "1, Highsun, 1491 DR"
"30, Summertide, 1492 DR" 1                 => "Midsummer, 1492 DR"
"30, Summertide, 1492 DR" 2                 => "Shieldmeet, 1492 DR"
"30, Summertide, 1492 DR" 3                 => "1, Highsun, 1492 DR"
"Midsummer, 1492 DR" 1                      => "Shieldmeet, 1492 DR"
"Midsummer, 1492 DR" 2                      => "1, Highsun, 1492 DR"
"Shieldmeet, 1492 DR" 1                     => "1, Highsun, 1492 DR"
"1, Highsun, 1490 DR" 365                   => "1, Highsun, 1491 DR"
"1, Highsun, 1491 DR" 365                   => "Shieldmeet, 1492 DR"
"Shieldmeet, 1492 DR" 365                   => "Midsummer, 1493 DR"
"Midsummer, 1493 DR" 365                    => "Midsummer, 1494 DR"
"Shieldmeet, 1500 DR" 365                   => "Midsummer, 1501 DR"

"14, Deepwinter, 654 DR" 5069               => "The Feast of the Moon, 667 DR"
"Midwinter, 17 DR" 7897                     => "15, The Fading, 38 DR"
"3, The Claw of Winter, 1000 DR" 813        => "25, The Claw of the Storms, 1002 DR"
"Greengrass, 5 DR" 26246                    => "9, The Claw of the Sunsets, 77 DR"
"30, The Melting, 321 DR" 394               => "29, The Time of Flowers, 322 DR"
"17, The Time of Flowers, 867 DR" 13579     => "20, Highsun, 904 DR"
"Highharvestide, 1814 DR" 456               => "30, The Drawing Down, 1815 DR"
"23, The Rotting, 1814 DR" 3616             => "16, Leaffall, 1824 DR"
"1, Deepwinter, 1 DR" 730499                => "30, The Drawing Down, 2000 DR"

"Midsummer, 1491 DR" -1                     => "30, Summertide, 1491 DR"
"1, Highsun, 1491 DR" -2                    => "30, Summertide, 1491 DR"
"1, Highsun, 1491 DR" -1                    => "Midsummer, 1491 DR"
"Midsummer, 1492 DR" -1                     => "30, Summertide, 1492 DR"
"Shieldmeet, 1492 DR" -2                    => "30, Summertide, 1492 DR"
"1, Highsun, 1492 DR" -3                    => "30, Summertide, 1492 DR"
"Shieldmeet, 1492 DR" -1                    => "Midsummer, 1492 DR"
"1, Highsun, 1492 DR" -2                    => "Midsummer, 1492 DR"
"1, Highsun, 1492 DR" -1                    => "Shieldmeet, 1492 DR"
"1, Highsun, 1491 DR" -365                  => "1, Highsun, 1490 DR"
"Shieldmeet, 1492 DR" -365                  => "1, Highsun, 1491 DR"
"Midsummer, 1493 DR" -365                   => "Shieldmeet, 1492 DR"
"Midsummer, 1494 DR" -365                   => "Midsummer, 1493 DR"
"Midsummer, 1501 DR" -365                   => "Shieldmeet, 1500 DR"

"The Feast of the Moon, 667 DR" -5069       => "14, Deepwinter, 654 DR"
"15, The Fading, 38 DR" -7897               => "Midwinter, 17 DR"
"25, The Claw of the Storms, 1002 DR" -813  => "3, The Claw of Winter, 1000 DR"
"9, The Claw of the Sunsets, 77 DR" -26246  => "Greengrass, 5 DR"
"29, The Time of Flowers, 322 DR" -394      => "30, The Melting, 321 DR"
"20, Highsun, 904 DR" -13579                => "17, The Time of Flowers, 867 DR"
"30, The Drawing Down, 1815 DR" -456        => "Highharvestide, 1814 DR"
"16, Leaffall, 1824 DR" -3616               => "23, The Rotting, 1814 DR"
"30, The Drawing Down, 2000 DR" -730499     => "1, Deepwinter, 1 DR"

```

# Answer
> 5 votes
# Ruby, ~~543~~ ~~523~~ ~~521~~ ~~498~~ ~~511~~ 509 bytes

To encourage more answers to this question, I'm going to post a Ruby version of my Python answer, since I figured it would be shorter. This answer *is* shorter but not by much. Can *you* do better?

**Edit:** With thanks to Martin Büttner and his suggestion here.

**Edit:** I golfed the "number of days in a month" list down considerably.

**Edit:** While golfing down how I handled `d[10]=r%4<1?1:0` to `d[10]=0**(r%4)` for a byte, I noticed I'd introduced a bug while golfing down `d`, the number of days list, so that Shieldmeet had 30 days by accident. And so, the byte count has come back up. I will also edit the Python answer to fix this bug there.

**Edit:** I forgot that functions don't need to be named in this question.

```
->s,n{x=s[0..-4].split(", ");x=x[2]?x:[1,*x];t=(["Deepwinter,Midwinter","Winter","Sunsets","the Storms,Greengrass,The Melting,The Time of Flowers,Summertide,Midsummer,Shieldmeet,Highsun,The Fading,Highharvestide,Leaffall,The Rotting,The Feast of the Moon,The Drawing Down"]*',The Claw of ').split(?,);p,q,r=x[0].to_i+n,t.index(x[1]),x[2].to_i;d=[30,1,30,30]*4+[1,30];d[10]=0**(r%4);(a=p<1?1:-1;q=(q-a)%18;p+=a*d[a<0?q-1:q];r-=a*0**q;d[10]=0**(r%4))until(1..d[q])===p;z=d[q]<2?[t[q],r]:[p,t[q],r];z*", "+" DR"}

```

Ungolfed:

```
def h(s,n)
  x=s[0..-4].split(", ")
  x=x[2]?x:[1,*x]
  t=["Deepwinter,Midwinter","Winter","Sunsets","the Storms,Greengrass,The Melting,The Time of Flowers,Summertide,Midsummer,Shieldmeet,Highsun,The Fading,Highharvestide,Leaffall,The Rotting,The Feast of the Moon,The Drawing Down"]
  t=t*',The Claw of '           # turns the above array into a string with "Claw"s inserted
  t=t.split(?,)                 # then splits that string back up again by ","
  p=x[0].to_i+n
  q=t.index(x[1])
  r=x[2].to_i
  d=[30,1,30,30]*4+[1,30]
  d[10]=0**(r%4)
  until(1..d[q])===p
    a=p<1?1:-1
    q=(q-a)%18
    p+=a*d[a<0?q-1:q]
    r-=a*0**q
    d[10]=0**(r%4)
  end
  z=d[q]<2?[t[q],r]:[p,t[q],r]  # putting z=[t[q],r] on another line saved me no bytes
  z*", "+" DR"
end

```

# Answer
> 5 votes
# Python 3, ~~712~~ ~~652~~ ~~636~~ ~~567~~ ~~563~~ ~~552~~ ~~550~~ ~~548~~ ~~529~~ 540 bytes

At last, I found time to write an answer for this excellent question. It isn't very golfed yet (the month names list ~~and the number of days list are~~ is particularly egregious in this case~~, and the fact that handling negative `D` requires a separate while loop~~) but at least it's an answer.

**Edit:** Fixing a bug

```
def h(s,n):
 x=s[:-3].split(", ");x=[1]*(len(x)<3)+x;t="Deepwinter,Midwinter,The Claw of Winter,The Claw of the Sunsets,The Claw of the Storms,Greengrass,The Melting,The Time of Flowers,Summertide,Midsummer,Shieldmeet,Highsun,The Fading,Highharvestide,Leaffall,The Rotting,The Feast of the Moon,The Drawing Down".split(",");p,q,r=int(x[0])+n,t.index(x[1]),int(x[2]);d=[30,1,30,30]*4+[1,30];d[10]=r%4<1
 while p>d[q]or p<1:a=[-1,1][p<1];q=(q-a)%18;p+=a*d[q-(a<0)];r-=a*0**q;d[10]=r%4<1
 return', '.join([str(p)]*(d[q]>2)+[t[q],str(r)])+" DR"

```

Ungolfed:

```
def harptos(date, num):
    t = "Deepwinter,Midwinter,The Claw of Winter,The Claw of the Sunsets,The Claw of the Storms,Greengrass,The Melting,The Time of Flowers,Summertide,Midsummer,Shieldmeet,Highsun,The Fading,Highharvestide,Leaffall,The Rotting,The Feast of the Moon,The Drawing Down"
    t = t.split(",")        # split up the names of the months
    x = date[:-3]           # removes " DR"
    x = x.split(", ")
    if len(x) < 3:
        x = [1] + x         # if we have two items (holiday), append a "day of the month"
    p = int(x[0]) + num     # initialize the "date" by adding num to it
    q = t.index(x[1])
    r = int(x[2])
    d=[30,1,30,30]*4+[1,30] # all the month lengths
    d[10] = r%4 < 1         # leap year toggle
    while p > d[q]:         # while the "date" > the number of days in the current month
        p -= d[q]           # decrement by number of days in current month
        q = (q+1)%18        # increment month
        r += 0**q           # increment year if the incremented month == the first month
        d[10] = r%4 < 1     # leap year toggle
    while p < 1:            # while the "date" is negative
        q = (q-1)%18        # decrement month first
        p += d[q]           # add the number of days in the decremented month
        r -= 0**q            # decrement year if the decremented month == the first month
        d[10] = r%4 < 1     # leap year toggle
    m = [t[q],str(r)]       # start the result array
    if d[q] > 2:
        m = [str(p)] + m    # if the month is NOT a holiday, add the day
    return ", ".join(m) + " DR"

```

---
Tags: code-golf, kolmogorov-complexity, date
---


# Question
Title: Mine for 2016 in Bitcoins! PCG.SE New Year's Puzzle 2016
In the Bitcoin protocol, **2016** is a very special number. The "difficulty" of finding a hash to create a new block is adjusted every 2,016 blocks to approximate changing once every two weeks.

This number was chosen is because the difficulty adjusts itself so that every block takes about 10 minutes to be found, and in two weeks, there are 2 × 7 × 24 × 6 = 2,016 ten-minute periods.

---

To commemorate this numerical coincidence, this year's New Year's problem is about Bitcoin — specifically, the hashing algorithm it uses to sign blocks, SHA-256.

Your task is to create a program that will take byte input (in at least ASCII) and output a nonce in bytes (in the format of your choice) that will produce a SHA-256 hash containing `2016` in its *base64* representation when appended to the original byte input.

Here are some examples of valid solutions, courtesy of the engines people have already generated, as well as the hashes they produced:

```
> foo
Nonce: 196870
SHA256 hash: OCUdDDtQ42wUlKz2016x+NROo8P2lbJf8F4yCKedTLE=

> bar
Nonce: 48230
SHA256 hash: CNcaOCQgT7bnlQzQPXNwuBu8/LYEdk2016khRaROyZk=

> happynewyear
Nonce: 1740131
SHA256 hash: XsKke6z2016BzB+wRNCm53LKJ6TW6ir66GwuC8oz1nQ=

> 2016
Nonce: 494069
SHA256 hash: rWAHW2YFhHCr22016zw+Sog6aW76eImgO5Lh72u6o5s=

(note: the nonces don't actually have to be ASCII numbers; you can do
 any byte input you find convenient.)

```

The only pre-built library (other than standard input and output functions) your program may use is a `SHA256(bytes)` function that takes byte input and returns a SHA256 hash, in any format including base64.

The program to do this in the fewest bytes of source code wins.

# Answer
> 7 votes
# Perl 5.10+, 39 + 18 = 57 bytes

```
sha256_base64($_.++$i)!~2016?redo:say$i

```

This needs to be run with the `-nMDigest::SHA=/./` command line switch, which is included in the byte count. It also uses the Perl 5.10+ `say` feature, and so needs to be run with the `-M5.010` (or `-E`) command line switch, which is considered free. The input should be provided on stdin, without a trailing newline (unless you want the newline to be considered part of the input).

Examples:

```
$ echo -n foo | perl -nMDigest::SHA=/./ -E 'sha256_base64($_.++$i)!~2016?redo:say$i'
196870
$ echo -n bar | perl -nMDigest::SHA=/./ -E 'sha256_base64($_.++$i)!~2016?redo:say$i'
48230
$ echo -n happynewyear | perl -nMDigest::SHA=/./ -E 'sha256_base64($_.++$i)!~2016?redo:say$i'
1740131
$ echo -n 2016 | perl -nMDigest::SHA=/./ -E 'sha256_base64($_.++$i)!~2016?redo:say$i'
494069

```

# Answer
> 8 votes
# Mathematica, 94

```
(For[i=0,IntegerDigits[4Hash[#<>ToString@++i,"SHA256"],64]~SequenceCount~{54,52,53,58}<1,];i)&

```

This function will try positive integers as candidates. It takes over 4 minutes on my laptop to get the correct answer.

```
%["foo"]
(* 196870 *)

```

Longer however faster (`~5x`) implementation makes use of parallelization:

```
f[k_]:=
    Do[If[Length@#>0,Return[i+#[[1,1]]]]&@
        Position[ParallelMap[IntegerDigits[4Hash[k<>ToString@#,"SHA256"],64]
            ~SequenceCount~{54,52,53,58}&,i+Range@1*^4],1]
        ,{i,0,∞,1*^4}]

```

# Answer
> 5 votes
# Ruby, ~~87~~ 86 bytes

I'm not sure if I understood the challenge correctly, but it finds `196870` in a few seconds if you input `foo`.

```
require"digest"
gets.chop!
$.+=1until/2016/=~Digest::SHA256.base64digest("#$_#$.")
p$.

```

# Answer
> 5 votes
# PowerShell, 150 ~~152~~ ~~153~~ bytes

```
while([Convert]::ToBase64String([Security.Cryptography.SHA256]::Create().ComputeHash([Text.Encoding]::UTF8.GetBytes("$args$i")))-notmatch2016){$i++}$i

```

# Example

```
PS > .\BitCoin.ps1 foo
196870

PS > .\BitCoin.ps1 bar
48230

PS > .\BitCoin.ps1 happynewyear
1740131

PS > .\BitCoin.ps1 2016
494069

```

# Answer
> 2 votes
# C#, 179 bytes

```
s=>{int i=0;while(!System.Convert.ToBase64String(System.Security.Cryptography.SHA256.Create().ComputeHash(System.Text.Encoding.UTF8.GetBytes(s+i))).Contains("2016"))i++;return i;}

```

Similar to the PowerShell solution, just longer.

---
Tags: hashing, code-golf
---


title: Euclidean Vectors

text:
# Question
Title: Euclidean Vectors
Given the ASCII art of two vectors, find the resultant vector's magnitude and degree.

---

## Input

This can be received via STDIN, read from a local file, or provided through a function call. Here is an example of a two vector input:

```
^------>
|
|
|
x

```

This represents a change of 4 units north and 7 units east. Every input's starting point will be represented by an `x` (decimal `120`).

* All vectors are horizontal or vertical lines.
* Each vector has one of these four endpoints: `^v<>`, and is made up of either a dash (`-`, decimal 45) or a vertical bar (`|`, decimal 124).
* Empty points on the plane are filled with spaces (, decimal 32).
* The input may be a single `x`.
* Adjacent vectors are always perpendicular to each other.
* All vectors are tip-to-tail.

---

## Output

This will be the displacement of the resulting point (distance from the starting point) and the degree to which it has moved, relative to the starting point.

For the above input, the output should be `8.06` units and `60.3` degrees. Each should have exactly 3 significant figures. Here are a few examples of numbers with 3 significant digits:

* 1.00
* 60.1
* 453
* 7.08
* 4.50
* 349

All unit measurements will be `<= 999`.

---

These numbers should be output in the below format. This is using the numbers from above.

```
8.06 units @ 60.3 degrees

```

This may be followed by a single trailing space or newline.

---

If the input is a single `x`, with no displacement and hence no angle of displacement, the output should be either an empty line (a single newline character) or in the following format:

```
0 units @ - degrees

```

If you're trying to qualify for the bonus, the direction should be `-` as well.

---

In the case that bonuses 2, 3, or both are completed, the output should follow the below model and abide by the same restrictions as the above.

```
8.06 units @ 60.3 degrees NE

```

---

Degrees should be measured according to the standard plane.

```
       90
  135  |  45
      \|/
180 ---x---- 0
      /|\
  225  |  315
      270

```

`0` degrees is east, `1 - 89` degrees is northeast, `90` is north, etc.

---

## Bonuses

The following are worth a total of -50%.

1. Take a -10% bonus for each additional vector that can be handled. This bonus can be applied to up to 3 times. Vectors will never overlap or cross.
2. Take a -10% bonus if your output includes the cardinal direction of the angle (north, south, east, west).
3. Take a -10% bonus if your output includes the intermediate directions of the angle (northeast, northwest, southeast, southwest).

---

## Examples

In:

```
x---->
     |
     v

```

Out:

```
5.39 units @ 338 degrees

```

Optionally `SE`

---

In:

```
<--------------^
               |
               |
               x

```

Out:

```
15.3 units @ 169 degrees

```

Optionally `NW`

---

In:

```
x
|
|<-----^
|      |
v------>

```

Out:

```
2.24 units @ 297 degrees

```

Optionally `SE`

---

## Examples (multiple vectors)

In:

```
x--->
    |
    |
    v----------->

```

Out:

```
16.3 units @ 349 degrees

```

Optionally `SE`

---

In:

```
<-------^
|       |
|       |
v       |
        |
        |
        x

```

Out:

```
8.54 units @ 159 degrees

```

Optionally `NW`

---

In:

```
^-->
|  |
|  v
|
<--------x

```

Out:

```
6.32 units @ 162 degrees

```

Optionally `NW`

# Answer
> 2 votes
# JavaScript (ES6), 305 bytes - 50% bonus = 152.5 score

```
v=>(l=v.search`
`+1,s=v.search`x`,u=0,d="-",v.replace(/[<>v^]/g,(p,i)=>{c=o=>v[i+o]!=q;with(Math)if(p<"?"?c(l,q="|")&c(-l):c(1,q="-")&c(-1))d=(atan2(x=i%l-s%l,y=(i/l|0)-(s/l|0))*180/PI+270)%360,u=sqrt(x*x+y*y)}),u[p="toPrecision"](3)+` units @ ${d[p](3)} degrees`)

```

## Explanation

Input must be padded with spaces. Uses all bonuses.

```
v=>(
  l=v.search`
`+1,                                                     // l = line length
  s=v.search`x`,                                         // s = index of start point
  u=0,                                                   // u = units
  d=                                                     // d = degrees
  w="-",                                                 // w = cardinal direction
  v.replace(/[<>v^]/g,(p,i)=>{                           // for each endpoint
    c=o=>v[i+o]!=q;                                      // compares cell at offset to char
    with(Math)                                           // save having to write "Math."
      if(p<"?"?c(l,q="|")&c(-l):c(1,q="-")&c(-1))        // check for line branching off
        d=(atan2(
          x=i%l-s%l,                                     // x = relative x
          y=(i/l|0)-(s/l|0)                              // y = relative y
        )*180/PI+270)%360,                               // convert to degrees
        u=sqrt(x*x+y*y),
        w="N S"[sign(y)+1]+"W E"[sign(x)+1]              // get cardinal direction
  }),
  u[p="toPrecision"](3)+` units @ ${d[p](3)} degrees `+w // format output
)

```

## Test

```
var solution = v=>(l=v.search`
`+1,s=v.search`x`,u=0,d=w="-",v.replace(/[<>v^]/g,(p,i)=>{c=o=>v[i+o]!=q;with(Math)if(p<"?"?c(l,q="|")&c(-l):c(1,q="-")&c(-1))d=(atan2(x=i%l-s%l,y=(i/l|0)-(s/l|0))*180/PI+270)%360,u=sqrt(x*x+y*y),w="N S"[sign(y)+1]+"W E"[sign(x)+1]}),u[p="toPrecision"](3)+` units @ ${d[p](3)} degrees `+w)
```

```
<textarea id="input" rows="6" cols="60">x
|
|<-----^
|      |
v------></textarea><br />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>
```

# Answer
> 3 votes
## Python 2, 238.5 (~~594~~ ~~562~~ ~~482~~ 477-50%) bytes

```
from math import*
def F(x):s='%.3g'%x;return[[s+'.',s]['.'in s].ljust(4,'0'),s][x>99]
I=input()
V=I.split('\n');N=len(V)
l=max(len(x)for x in V)
q=[' '*(l+2)];V=q+[' '+x.ljust(l+1)for x in V]+q
for k in range(N*l):
 i,j=k/l,k%l;c=V[i+1][j+1]
 if c in'<>^v'and['|'not in zip(*V)[j+1][i:i+3],'-'not in V[i+1][j:j+3]][c>'?']:a,b=i,j
 if c=='x':A,B=i,j
Y=A-a;X=b-B;a=atan2(Y,X)/pi*180%360
print[F(hypot(X,Y))+' units @ '+F(a)+' degrees '+' NS'[cmp(Y,0)]+' EW'[cmp(X,0)],''][I=='x']

```

---

**Explanation**

Finds the start and end positions by looking at each character in the input.

Start is `x`

End is found by looking at each arrow (`<>^v`), and their neighbors. If neighbors are continuing vectors, ignore. Else, this is the end.

Look at the neighbors perpendicular to the arrow direction.

If they contain a perpendicular line, then it is a continuing vector.

Examples (`_` indicates space):

```
_#_
->_   Neighbors marked by #
_#_

___
->_   (end)
___

_|_
->_   (not end)
___

___
->|   (end)
___

---
->_   (end)
___

```

Because the end point is found, there can be any number of vectors (**30% bonus**).

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


title: Make Bracket Squares

text:
# Question
Title: Make Bracket Squares
Every programmer knows that brackets `[]{}()<>` are really fun. To exacerbate this fun, groups of interwoven brackets can be transformed into cute and fuzzy diagrams.

Let's say that you have a string that contains balanced brackets, like `[{][<(]})>(())`. Step one is to rotate the string 45 degrees clockwise. (In Mathematica, this can be almost done with `Rotate[ur_string,-pi/4]`). Here is the result of the first step:

```
[
 {
  ]
   [
    <
     (
      ]
       }
        )
         >
          (
           (
            )
             )

```

Next add a diagonal space between each character.

```
[

  {

    ]

      [

        <

          (

            ]

              }

                )

                  >

                    (

                      (

                        )

                          )

```

Next, start with the left-most bracket and draw a square between it and its partner in crime.

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

      [

        <

          (

            ]

              }

                )

                  >

                    (

                      (

                        )

                          )

```

Repeat this process with each pair of brackets, overwriting previous characters with `+`s if need be.

```
+---+
|   |
| +-+---------+
| | |         |
+-+-+         |
  |           |
  |   [       |
  |           |
  |     <     |
  |           |
  |       (   |
  |           |
  |         ] |
  |           |
  +-----------+

                )

                  >

                    (

                      (

                        )

                          )

```

Continue until you have made everything nice and square.

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

                    +-----+
                    |     |
                    | +-+ |
                    | | | |
                    | +-+ |
                    |     |
                    +-----+

```

**Input**

Input will be a single line of balanced brackets and no other characters, with each bracket being one of `[]{}()<>`. Each *type* of bracket is balanced individually, though different types may overlap (this is what makes the squares look interesting). A trailing newline is optional.

**Output**

Output will be the interlocking square pattern generated from the bracket string. Trailing spaces and trailing newline are optional, but there mustn't be leading whitespace.

**Goal**

This is code-golf, fewest bytes wins.

# Answer
# JavaScript (ES6), ~~269 274 278 296~~ 261 bytes

**Edit** Saved 4 bytes thx @Neil

```
x=>[...x].map(c=>{g.push([],[]),z='<{[(>}])'.indexOf(c);if(z>3)for(j=a=o[z-4].pop();j<=b;j++)S(j,a,'|'),S(j,b,'|'),S(a),S(b);else o[z].push(b);b+=2},S=(y,x=j,c='-')=>g[y][x]=g[y][x]?'+':c,o=[[],[],[],[]],g=[],b=0)&&g.map(r=>[...r].map(c=>c||' ').join``).join`
`

```

**TEST**

```
F=x=>[...x].map(c=>{g.push([],[]),z='<{[(>}])'.indexOf(c);if(z>3)for(j=a=o[z-4].pop();j<=b;j++)S(j,a,'|'),S(j,b,'|'),S(a),S(b);else o[z].push(b);b+=2},S=(y,x=j,c='-')=>g[y][x]=g[y][x]?'+':c,o=[[],[],[],[]],g=[],b=0)&&g.map(r=>[...r].map(c=>c||' ').join``).join`
`

// Less golfed
U=x=>(
  S = (y,x=j,c='-')=>g[y][x]=g[y][x]?'+':c,
  o = [[],[],[],[]],
  g = [],
  b = 0,
  [...x].map(c=>
  {
    g.push([],[]),
    z='<{[(>}])'.indexOf(c);
    if(z>3)
      for(j = a =o[z-4].pop(); j <= b; j++)
        S(j,a,'|'),
        S(j,b,'|'),
        S(a),
        S(b)
    else
      o[z].push(b);
    b += 2
  }),
  g.map(r=>
    [...r].map(c=>c||' ').join``
  ).join`\n`
)

function test() {
  O.textContent=F(I.value)
}

test()
```

```
Input:<input id=I value='[{][<(]})>(())' oninput='test()'>
<pre id=O></pre>
```
> 7 votes

# Answer
## Python 3, 226

```
n,p,*t=0,[],0,[],[],[],[]
for b in input():
 r=t[ord(b)//30];r+=[n];n+=2
 if b in'])}>':p+=[r[-2:]];del r[-2:]
R=range(n-1)
for y in R:print(''.join(' -|+'[sum((y in q)+2*(x in q)for q in p if x>=q[0]<=y<=q[1]>=x)]for x in R))

```

Example. Explanation:

```
n,p,*t=0,[],0,[],[],[],[]   # n -> counter for input
                            # p -> bracket pairs
                            # t -> four stacks [unused, (), <>, [], {}]

for b in input():           # for each bracket b of input
  r=t[ord(b)//30];          # r -> alias for b's stack
  r+=[n];                   # push bracket's index
  n+=2                      # increase counter by 2 (to add diagonal gaps)

  if b in'])}>':            # if b is a closing bracket
    p+=[r[-2:]];            # pair the top 2 brackets on stack
    del r[-2:]              # pop them from stack

R=range(n-1)                # n-1 is now the width/height of output

for y in R:
  print(''.join(' -|+'[
    sum((y in{a,b})+2*(x in{a,b})for a,b in p if x>=a<=y<=b>=x)
  ]for x in R))

# three nested loops:
# 1) for each line y
#   2) for each character x
#     3) for each bracket pair (a, b)

if x>=a<=y<=b>=x
# if x or y isn't in the inclusive range [a, b], we can skip it

(y in{a,b})
# if y is a or b, then the character lies on a horizontal edge of that square
# so we add 1 to the sum

2*(x in{a,b})
# if x is a or b, then the character lies on a vertical edge of that square
# so we add 2 to the sum

' -|+'[sum()]
# if it lies on a single edge, the sum will be 1 or 2 -> '-' or '|'
# if it lies on two edges, the sum will be 1 + 2 == 3 -> '+'

```
> 4 votes

# Answer
# pb \- 449 bytes

```
^w[B!0]{w[B=40]{b[39]}t[B]w[B!0]{w[B=T]{^b[1]}w[B=T+1]{^b[1]}w[B=T+2]{^b[2]}^[Y]^>}<[X]^w[B!1]{>}t[1]b[0]w[T!0]{>w[B=1]{t[T+1]b[0]}w[B=2]{t[T-1]b[0]}}b[3]vw[B!0]{>}^w[B!3]{b[0]<}b[0]vb[1]>[X]vv[X]b[43]t[X]^[Y]^<[X]w[B=0]{>}>[X]vv[X]b[43]w[Y!T-1]{vw[B=45]{b[43]}w[B=0]{b[124]}}vb[43]t[1]>w[B!43]{t[T+1]w[B=124]{b[43]}w[B=0]{b[45]}>}w[T!0]{^t[T-1]w[B=45]{b[43]}w[B=0]{b[124]}}w[B!43]{w[B=124]{b[43]}w[B=0]{b[45]}<}<[X]^[Y]^w[B=0]{>}b[0]>w[B=1]{b[0]>}}

```

I was all excited when I read this because I have a language that prints directly to a position! This challenge about positioning outputs should be easy and short!

Then I remembered pb is longwinded anyway.

With comments:

```
^w[B!0]{
    w[B=40]{b[39]}                       # change ( to ' to make closing bracket calculation work
    t[B]

    # this used to just find the first matching bracket
    # but then op clarified we had to use depth
    # whoops
    # <fix>

    w[B!0]{
        w[B=T]{^b[1]}                        # put a 1 above opening brackets of this type
        w[B=T+1]{^b[1]}                      # same as before, but ugly hack to make ( work
        w[B=T+2]{^b[2]}                      # put a 2 above closing brackets of this type
        ^[Y]^                                # return to input line
    >}
    <[X]^w[B!1]{>}t[1]b[0]               # set T to 1 above the opening bracket
    w[T!0]{>                             # until T (depth) == 0:
        w[B=1]{t[T+1]b[0]}                   # add 1 to T if 1
        w[B=2]{t[T-1]b[0]}                   # subtract 1 from T if 2
    }
    b[3]                                 # when T is 0, we've found the right one
    vw[B!0]{>}                           # go to the end of the input
    ^w[B!3]{b[0]<}b[0]v                  # clean up the row above
    # </fix>

    b[1]                                 # replace it with 1 so it's not confusing later
    >[X]vv[X]b[43]t[X]                   # put a + at its output position and save coord
    ^[Y]^<[X]w[B=0]{>}>[X]vv[X]b[43]     # put a + at opening bracket's output position
    w[Y!T-1]{v
        w[B=45]{b[43]}                       # replace - with +
        w[B=0]{b[124]}                       # otherwise put |
    }
    vb[43]                               # put a + at lower left corner
    t[1]                                 # count side length + 1
    >w[B!43]{
        t[T+1]
        w[B=124]{b[43]}                      # replace | with +
        w[B=0]{b[45]}                        # otherwise put -
    >}
    w[T!0]{^                             # create right side
        t[T-1]
        w[B=45]{b[43]}
        w[B=0]{b[124]}
    }
    w[B!43]{                             # create top side
        w[B=124]{b[43]}                      # this replacement saves us from putting the last + explicitly
                                             # which is why we counted the side length + 1, to get that
                                             # extra char to replace
        w[B=0]{b[45]}
    <}
    <[X]^[Y]^w[B=0]{>}b[0]>w[B=1]{b[0]>}# Go to next character (skipping 1s)
}

```
> 3 votes

# Answer
# CJam, 117 bytes

```
q_,2*:M2#0a*\:iee{1=K/}${~)4%1>{a+aL+:L;}*}/L{2f*__~,>m*5Zb\m*{~W2$#%Mb\}%\2m*Mfb3am*}%e_2/{~2$2$=+3e<t}/" |-+"f=M/N*

```

Try it here.
> 2 votes

# Answer
# Ruby, 268

```
->z{a=(2..2*t=z.size).map{'  '*t}
g=->y,x{a[y][x]=(a[y][x-1]+a[y][x+1]).sum>64??+:?|}
2.times{|h|s=z*1
t.times{|i|c=s[i]
c>?$&&(j=s.index(c.tr('[]{}()<>','][}{)(><'))
(m=i*2).upto(n=j*2){|k|k%n>m ?g[k,m]+g[k,n]:h<1&&a[k][m..n]=?++?-*(n-m-1)+?+}
s[i]=s[j]=?!)}}
puts a}

```

**ungolfed in test program**

```
f=->z{
  a=(2..2*t=z.size).map{'  '*t}                       #make an array of strings of spaces
  g=->y,x{a[y][x]=(a[y][x-1]+a[y][x+1]).sum>64??+:?|} #function for printing verticals: | if adjacent cells spaces (32+32) otherwise +

  2.times{|h|                                         #run through the array twice
    s=z*1                                             #make a duplicate of the input (*1 is a dummy operation to avoid passing just pointer)
    t.times{|i|                                       #for each index in input
    c=s[i]                                            #take the character
    c>?$&&(                                           #if ascii value higher than for $
      j=s.index(c.tr('[]{}()<>','][}{)(><'))          #it must be a braket so find its match
      (m=i*2).upto(n=j*2){|k|                         #loop through the relevant rows of array
        k%n>m ?g[k,m]+g[k,n]:                         #if k!=n and k!m draw verticals
        h<1&&a[k][m..n]=?++?-*(n-m-1)+?+              #otherwise draw horizontals (but only on 1st pass)
      }
      s[i]=s[j]=?!)                                   #we are done with this set of brackets, replace them with ! so they will be ignored in next call of index
    }
  }
  puts a
}

z=gets.chop
f[z]

```
> 1 votes

---
Tags: code-golf, string, ascii-art, balanced-string
---


title: Digital Clock Matches Puzzle

text:
# Question
Title: Digital Clock Matches Puzzle
There are many puzzles with matches that involve adding, removing, or moving a certain number of matches to create new numbers or shapes. This is like that with a digital clock.

Given a valid time on a 12-hour digital clock, output the digit that requires moving the fewest lines to make it so every visible digit on the clock becomes that digit. If more than one digit is the minimum, output them all. If it is impossible to make every digit the same, output `-1` or a falsy value other than 0 (you'll get a lot of these).

The clock digits look like this:

```
  |
  |
 _
 _|
|_
 _
 _|
 _|

|_|
  |
 _
|_
 _|
 _
|_
|_|
 _
  |
  |
 _
|_|
|_|
 _
|_|
 _|
 _
| |
|_|

```

## Test Cases:

Input: `123`

Clock Display:

```
       _   _
  | :  _|  _|
  | : |_   _|

```

Output: `4`

Explanation: The display for `1:23` requires a total of 12 lines to be drawn. Therefore, for every digit to be the same, each digit would have to have 4 lines. The only digit that has 4 lines is `4`. Therefore, the answer has to be `4`.

Input: `1212`

Clock Display:

```
     _        _
  |  _| :  |  _|
  | |_  :  | |_

```

Output: `-1`

Explanation: The display for `12:12` requires 14 lines. 14 divided by 4 is not an integer, therefore it is impossible for every digit to be the same.

Input: `654`

Clock Display:

```
 _     _
|_  : |_  |_|
|_| :  _|   |

```

Output: `5`

Explanation: The total number of lines is 15. 15 divided by 3 is 5, so each digit must have 5 lines. The only digits that have 5 lines are `2`,`3`, and `5`. The answer is `5` because it only requires 2 moves to make every digit 5. Simply move the line at the bottom left of the 6 to the bottom of the 4, then you have:

```
 _     _
|_  : |_  |_|
 _| :  _|  _|

```

Then, as you can see, all you need to do is move the line at the top right of the digit that was originally 4 to the top, and you get `5:55`. To make every digit a `2` or `3` would require more than 2 moves.

Input: `609`

Clock Display:

```
 _     _   _
|_  : | | |_|
|_| : |_|  _|

```

Output: `609` (`6,0,9` or `[6,0,9]` also ok).

Explanation: `6`, `0`, and `9` are the only digits that have 6 lines. As such, they are also the only possible solutions. It's not hard to see that it would take two moves to make any of these the only digit. Therefore, you output all three digits.

## Notes:

* Although the input time must be valid, the output time does not (e.g. `999` as an output is OK.)
* I am very flexible with input. You can require a leading 0. You can use a number with a decimal point. You can use a string. You can use an array. You can have a parameter for every digit.

# Answer
# Julia, ~~160~~ ~~157~~ 154

```
x->(c=count_ones;l=[119;36;93;109;46;107;123;37;127;111];m=l[x+1];n=map(a->c(a)==mean(map(c,m))?sum(map(b->c(a$b),m)):1/0,l);find(n.==minimum(n).!=1/0)-1)

```

This is a lambda function. Assign it to a variable to call it. Accepts a vector of integers in range `0-9` of any length and returns a (possibly empty) vector of results.

## Test cases

```
julia> clock = x->(c=co...        # assign function to variable
(anonymous function)

julia> clock([1 2 3])
1-element Array{Int64,1}:
 4

julia> clock([1 2 1 2])
0-element Array{Int64,1}

julia> clock([6 5 4])
1-element Array{Int64,1}:
 5

clock([6 0 9])
3-element Array{Int64,1}:
 0
 6
 9

```

## Explanation

Enumerate the seven segments and represent them as a bit vector.

```
+---+                     +-0-+
|   |      Enumerate      1   2
+---+   >  the seven  >   +-3-+
|   |      segments       4   5
+---+                     +-6-+

```

*Example:* `1` (segments 2 + 5 enabled) becomes `36` (bits 2 + 5 set).
Here are the representations for digits `0-9`.

```
l=[119;36;93;109;46;107;123;37;127;111];
m=l[x+1];

```

We can use the digit as index to get it's bit vector representation. `+1` because of 1-based indexing in julia.

The function `c=count_ones;` counts the number of 1-bits in an integer. We assign an alias because we need it more often.

**The full program, somewhat ungolfed:**

```
x->(
  c=count_ones;
  l=[119;36;93;109;46;107;123;37;127;111];
  m=l[x+1];
  n=map(a->c(a)==mean(map(c,m))?sum(map(b->c(a$b),m)):1/0,l);
  find(n.==minimum(n).!=1/0)-1
)

```

Now, the last two lines in detail:

`mean(map(c,m))` calculates the average number of lines per input digit.

`n=map(a->...,l)` loops over the vector representation of all digits.

If the number of lines of our current digit `a` is unequal to the average linecount of the input, return `inf`.

```
c(a)==mean(map(c,m))?...:1/0

```

If not, return the sum of the *Hamming Distances* between our current and all input digits.

```
sum(map(b->c(a$b),m))

```

We now have a vector `n` of length `10` representing the numbers `0-9` that gives us the total number of additions/deletions we have to perform to tranform all input digits to that number, or `inf`, if such a transformation is impossible without changing the number of lines.

```
find(n.==minimum(n).!=1/0)-1

```

Finally, output the locations (0-based) of all minima that are not `inf`.
> 1 votes

---
Tags: code-golf, number, clock
---


title: Inject Textual Rickrolls

text:
# Question
Title: Inject Textual Rickrolls
Because rickrolling is the greatest meme on Earth, you *\[know the rules and so do I\]* are to write the shortest code that can textually rickroll the unsuspecting reader. Let *\[you down\]* there be an input text which contains letters, punctuation, and spaces. Anytime a *\[lie and hurt you\]* phrase from the first two stanzas appears in the text...

```
We're no strangers to love
You know the rules and so do I
A full commitment's what I'm thinking of
You wouldn't get this from any other guy
I just wanna tell you how I'm feeling
Gotta make you understand

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

```

...insert the rest of the line in brackets afterwards.

**Input**

Input is a single line string containing only printable ASCII with optional trailing newline.

**Output**

Output is a single-line string. Any time that a group of words (defined as the input string split on spaces) matches a group of words in lines of the lyrics above, insert the remaining words of the line into the string, grouped in square brackets.

**Additional Description:**

This is **code-golf**, fewest bytes wins. You may write a program or function.

* matching should be case insensitive: `we're` is converted to `we're [no strangers to love]` even though `We're` is capitalized in the lyrics.
* matching should be greedy. `Does he know the answer?` should be converted to `Does he know the [rules and so do I] answer?` instead of `Does he know [the rules and so do I] the [rules and so do I] answer?`
* If a word appears more than once in the provided lyrics, choose any of the occurrences to complete the line.
* If a word is the last word in the lyric line, don't insert anything after it.
* Punctuation is included as part of a "word." `I'm` is a single word and cannot match with `I`. Similarly, `you.` doesn't match with any lyrics because of the period.

Some words like `I` appear multiple times throughout the lyrics as well as at the end of a line. Since the rule is that any occurrence in the above lyrics can be used, and one of those occurrences is at the end of a line, no matching of `I` is necessary. The other option for `I` is `[just wanna tell you how I'm feeling]`.

If two matches overlap, you may choose either one. This means that `how I'm thinking` could become `how I'm [feeling] thinking [of]` OR `how [I'm feeling] I'm thinking [of]` since the `I'm` could be part of either `how I'm` or `I'm thinking`. If, however the input text was simply `I'm thinking`, then the output should be `I'm thinking [of]`.

## Additional test cases:

```
I don't know what I'm doing with my life.
is converted to
I [just wanna tell you how I'm feeling] don't know [the rules and so do I] what I'm [thinking of] doing with my life.
Many additional solutions are possible, since words like `I` appear multiple times.

Will someone please save me from these memes?
is converted to
Will someone please save me from [any other guy] these memes?

Two strangers walked into a bar.  One said "hello."  The other said "goodbye."
is converted to
Two strangers [to love] walked into a [lie and hurt you] bar.  One said "hello."  The [rules and so do I] other [guy] said "goodbye."

```

---

Challenge inspired by this dude.

# Answer
> 7 votes
# gawk, 316+377 = 693

First command line parameter is the lyrics' filename (375 bytes + 2 for invocation = 377). Rickrolls all other files. Prints to `stdout`.

```
BEGIN{FPAT="[^ ]+ *";OFS=""}func d(a){b=tolower(a);sub(/ *$/,"",b);return b}FNR==NR{for(s=$0;NF;$0=s=$0){for(i=1;i<NF;i++){k=k $i;$i="";v[d(k)]="["$0"] "}$0=s;k=$1=""}next}{for(s=$0;NF;$0=s=$0){for(j=NF;(--j)>0&&!(d($0) in v);$(j+1)="");k=v[d($0)];if($0!~/ $/)k=" "k;printf($0 k);for($0=s;j-->=0;$(j+2)="");}print""}

```

## Ungolfed

```
BEGIN{FPAT="[^ ]+ *";OFS=""}
func d(a){b=tolower(a);sub(/ *$/,"",b);return b}
FNR==NR{
  for(s=$0;NF;$0=s=$0){
    for(i=1;i<NF;i++)
    {
      k=k $i;
      $i="";
      v[d(k)]="["$0"] "
    }
    $0=s;
    k=$1=""
  }
  next
}
{
  for(s=$0;NF;$0=s=$0){
    for(j=NF;(--j)>0&&!(d($0) in v);$(j+1)="");
    k=v[d($0)];
    if($0!~/ $/)k=" "k;
    printf($0 k);
    for($0=s;j-->=0;$(j+2)="");
  }
  print""
}

```

## Test results

Input:

```
we're
We're
Does he know the answer?
I
how I'm thinking
I'm thinking
I don't know what I'm doing with my life.
Will someone please save me from these memes?
Two strangers walked into a bar.  One said "hello."  The other said "goodbye."
gonna run

```

Output:

```
we're [no strangers to love]
We're [no strangers to love]
Does he know the [rules and so do I] answer?
I [just wanna tell you how I'm feeling]
how I'm [feeling] thinking [of]
I'm thinking [of]
I [just wanna tell you how I'm feeling] don't know [the rules and so do I] what I'm [thinking of] doing with my life.
Will someone please save me from [any other guy] these memes?
Two strangers [to love] walked into a [lie and hurt you] bar.  One said "hello."  The [rules and so do I] other [guy] said "goodbye."
gonna run [around and desert you]

```

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


title: What size is the digit?

text:
# Question
Title: What size is the digit?
7-segment digits can be represented in ASCII using `_|` characters. Here are the size `1` digits:

```
   _  _       _   _   _   _   _   _
|  _| _| |_| |_  |_    | |_| |_| | |
| |_  _|   |  _| |_|   | |_|  _| |_|

```

Larger sizes are formed by making each segment proportionately longer. Here are a couple size 3 digits.

```
 ___    ___    ___    ___    ___    ___    ___
|   |  |          |  |          |  |   |  |   |
|   |  |          |  |          |  |   |  |   |
|___|  |___       |  |___    ___|  |   |  |___|
|   |  |   |      |      |      |  |   |      |
|   |  |   |      |      |      |  |   |      |
|___|  |___|      |   ___|   ___|  |___|   ___|

```

## Goal

In this challenge, you are to write a program/function that can take a single digit as input and identify its size. The catch: if the input is not a valid digit, then your program should output `0`.

This is **code-golf**, fewest bytes wins.

You can write either a program or a function, which can receive the digit either as STDIN or an argument, and print/return the value.

Digits will be provided as a multi-line string, padded with the minimal amount of trailing whitespace needed to make it a perfect rectangle. The trailing newline is an optional part of input. There will be no unneeded leading spaces.

When a non-digit is passed, it will still be comprised of `_|` characters, padded to a rectangle, and have no unneeded leading spaces. There will be no blank lines. You won't have to deal with empty input.

Output should be a single non-negative integer, with optional trailing newline. If the input is not a proper digit of any size, output `0`. Else, output the size.

Here is a handy guide for the widths and heights of each digit for a given size `N`.

```
Digit  Height  Width (not counting newlines)
1      2N      1
2      2N+1    N+2
3      2N+1    N+1
4      2N      N+2
5      2N+1    N+2
6      2N+1    N+2
7      2N+1    N+1
8      2N+1    N+2
9      2N+1    N+2
0      2N+1    N+2

```

## I/O Examples

In:

```
__
  |
__|
  |
__|

```

Out:

```
2

```

In:

```
|
|
|

```

Out:

```
0  //because it is of an invalid height.  Either 1 char too short or tall.

```

In:

```
|    |
|    |
|    |
|____|
     |
     |
     |
     |

```

Out:

```
4

```

In:

```
 ___
|
|___
|   |
|___|

```

Out:

```
0 //1 char too wide

```

In:

```
 _
|_|
| |

```

Out:

```
0 //it's not a digit

```

In:

```
 __
|
|__
   |
 __|

```

Out:

```
2

```

In:

```
 _  _
 _| _|
|_  _|

```

Out:

```
0  //both would be valid individually, but input should be a *single* digit

```

In:

```
 _
|_|
|_|

```

Out:

```
1

```

In:

```
|
|

```

Out:

```
1

```

In:

```
__|_
 |
 _ |
  _
|__

```

Out:

```
0

```

---

This is approximately the *inverse* of Transform number into 7-segment display pattern, from 3 years back.

# Answer
> 1 votes
# Ruby, 250

```
->x{d=y=0
x.size.downto(0){|n|y=n
a=["|
"*2*n]
"XNRDqpm@A".bytes{|z|p=[?|,' ','']
h=s=""
(n*2).times{|i|
i%n<1&&(d=z>>i/n*3&7)&&h=[?_,' '][d/3%2]*n
s=p[d%3]+h+p[d/6]+"
"+s
h=' '*n}
z!=68&&s=' '*(1-d%3/2)+?_*n+"
"+s
a<<s};puts a
a.index(x)&&break}
y}

```

Given that there are so many possible invalid inputs, the only way to do this was to generate all the correct digits and check to see if the input matches.

I build each digit up from bottom to top, in 2 halves plus the top line. Although there are 12 possibilities (considering that the left segment can be on, off, or in the case of `3`and `7`completely absent) only 7 are actually present and careful choice of encoding enables all info (except the top line) to be encoded into a single character.

the digit `1` doesn't really fit the pattern and is handled separately, being used to initialize the array.

**Ungolfed in test program**

This version uses `.` instead of spaces for diagnostic reasons.

```
#Encoding used for half-digits (radix 3,2,2 most significant digit at right)

#000    |_|  0

#100    ._|  1  . = space

#200    X_|  2  X = no space (for digits 3 and 7)

#010    |.|  3

#110    ..|  4

#210    X.|  5

#001    |_.  6

f=->x{d=y=0                                        #d and y required to be intialized for scoping reasons
  x.size.downto(0){|n|y=n                          #Assume max possible size of character = length of input and iterate down through all possible sizes n
    a=["|\n"*2*n]                                  #Make an array containing the digit 1 (different shape to others)
    "XNRDqpm@A".bytes{|z|                          #Each character encodes the pattern for a digit. Iterate through them
      p=['|','.','']                               #Possible components for left and right of digit
      h=s=""                                       #h initialized for scoping reasons. s will contain the digit string
      (n*2).times{|i|                              #For each row
        i%n<1&&                                    #If i%n==1 we are at the bottom of a half digit
        (d=z>>i/n*3&7)&&                           #so extract info from z and store in d
        h=[?_,'.'][d/3%2]*n                        #h is the horizontal part of the half digit, either _ or spaces
        s=p[d%3]+h+p[d/6]+"\n"+s                   #Build one row of digit, working upwards: left,middle,right
        h='.'*n                                    #If row i%n!=0 (not bottom row of half digit)the middle section must contain spaces
      }                                            #We now have both halves of the digit, only the top segment missing
      z!=68&&s='.'*(1-d%3/2)+?_*n+".\n"+s          #If z!=68 (digit 4) add a top to the digit, with appropriate leading and trailing spaces
      a<<s                                         #Add the completed digit of size n to a
    }
    #puts a                                        #Diagnostic: uncomment to print all the strings checked
    a.index(x)&&break                              #If string x is in a, break

  }
y                                                  #and return last value of n
}

# digit 7, size 2. Trailing newline required. Outputs 2
puts f[
"__.
..|
..|
..|
..|
"]

```

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


title: Count common Game of Life patterns

text:
# Question
Title: Count common Game of Life patterns
The task here is to read from a Golly `.rle` or plaintext file (your choice) whose filename is provided (on STDIN or as a command line argument) and identify and count the common patterns in the grid encoded therein.

Alternatively, you may choose to have the contents of the file provided directly over STDIN instead.

Your program should be able to identify and distinguish at least the fifteen most common strict still lifes and the five most common oscillators, plus gliders.

All phases of these oscillators should be recognized, as should all four phases of the glider.

It should output a list containing the final count of each pattern, with the name and quantity of each pattern on a separate line. Your program may include in the ouput list either all of these patterns or only the ones of which at least one was found.

Patterns which are part of other patterns being counted should not be counted. (for example, the 8-cell phase of a beacon should not also be counted as two blocks, and a ship-tie should not also be counted as two ships)

You may assume that the input has already stabilized and contains no patterns not in the aformentioned set. You may also assume that the input grid will fit within a 1024x1024 box.

This is , so the shortest program wins.

**RLE file format description**

An RLE file contains a run-length encoded life grid. All lines starting with `#` are comments and should be ignored.

The first non-empty, non-comment line is of the form `x=<width>,y=<height>,rule=<rule>`. For the purposes of this task, the rule will always be `B3/S23`. It may contain spaces which should be stripped before processing this line (of course, it is not necessary to process this line at all.)

Non-comment lines after the first should be treated as a single string. This should consist only of decimal digits, the characters `$`, `b`, and `o`, and line breaks, and will not end with a digit. Line breaks are to be ignored, but you may assume that line breaks will not interrupt strings of digits.

This may be terminated by a single `!`.

`b` represents a dead cell, `o` represents a live cell, and `$` represents the end of a row. Any decimal number indicates that the following symbol is to be treated as repeating that many times.

**Plaintext pattern encoding**

The other option is to read the pattern in another plaintext format described here. In this encoding, off cells are represented with hyphens and on cells are represented with uppercase Os, with newlines separating rows.

You may assume that all non-comment lines will be padded to equal length with hyphens.

Lines starting with `!` are comments and are to be ignored.

**Some test cases**

RLE:

```
#This is a comment
x = 35, y = 16, rule = B3/S23
bo$2o$obo5$22bo$22bo$22bo2$18b3o3b3o2$22bo$22bo10b2o$22bo10b2o!

```

Plaintext:

```
!This is a comment
-O---------------------------------
OO---------------------------------
O-O--------------------------------
-----------------------------------
-----------------------------------
-----------------------------------
-----------------------------------
----------------------O------------
----------------------O------------
----------------------O------------
-----------------------------------
------------------OOO---OOO--------
-----------------------------------
----------------------O------------
----------------------O----------OO
----------------------O----------OO

```

Results:

```
Glider 1
Blinker 4
Block 1

```

RLE:

```
x = 27, y = 15, rule = B3/S23
5b2o$5b2o9$11bo$o9bobo$o9bobo$o10bo12b3o!
#Here's a comment at the end

```

Plaintext:

```
-----OO--------------------
-----OO--------------------
---------------------------
---------------------------
---------------------------
---------------------------
---------------------------
---------------------------
---------------------------
---------------------------
-----------O---------------
O---------O-O--------------
O---------O-O--------------
O----------O------------OOO
!Here's a comment at the end

```

Results:

```
Block 1
Blinker 2
Beehive 1

```

RLE:

```
#You may have multiple comments
#As shown here
x = 13, y = 11, rule = B3/S23
2o$2o2$12bo$12bo$12bo$2b2o$2b2o4b2o$7bo2bo$7bobo$8bo!

```

Plaintext:

```
!You may have multiple comments
!As shown here
OO-----------
OO-----------
-------------
------------O
------------O
------------O
--OO---------
--OO----OO---
-------O--O--
-------O-O---
--------O----

```

Results:

```
Block 2
Blinker 1
Loaf 1

```

RLE:

```
# Pentadecathlon
# Discovered by John Conway
# www.conwaylife.com/wiki/index.php?title=Pentadecathlon
x = 10, y = 3, rule = B3/S23
2bo4bo2b$2ob4ob2o$2bo4bo!

```

Plaintext:

```
! Pentadecathlon
! Discovered by John Conway
! www.conwaylife.com/wiki/index.php?title=Pentadecathlon
--O----O--
OO-OOOO-OO
--O----O--

```

Results:

```
Pentadecathlon 1

```

**Bonus**

If you support *both* input formats (using the file extension \[`.rle` for rle files and `.cells` for plaintext- how other extensions are to be read is undefined\] or a command line flag to distinguish between them) you may subtract 5% from your score.

# Answer
> 13 votes
## Haskell, 2417 bytes

This took quite a while and there are still a few bugs, but I got several tricks working so it was worth it.

Notes:

* It only accepts the plaintext format, passed to STDIN
* It takes something like O(n^20) time
* I assumed that the number of characters in non-comment lines is constant (within a specific input), as that's how it is in the examples
* Craziest trick was how the patterns are unpacked, extracting the elements at positions (column number) modulo (the length of the output) to build the array.

It combines a few key ideas:

* patterns and symmetries can be pre-computed
* a single pattern can be packed into an integer, with dimensions known
* finding all submatrices is easy
* counting equalities is easy

Here's the code:

```
r=[1..20]
a!0=a!!0
a!x=tail a!(x-1)
u[_,x,y,l]=[[odd$div l$2^i|i<-[0..y],mod i x==j]|j<-[0..x-1]]
main=interact(\s->let q=[map(=='O')l|l<-lines s,l!0/='!']in let g=[i|i<-[[[0,3,11,3339,0,4,11,924,0,4,11,3219,0,3,11,1638,1,4,15,19026,1,4,15,9636,2,3,11,1386,2,4,11,1686,3,7,48,143505703994502,3,7,48,26700311308320,3,7,48,213590917399170,3,7,48,8970354435120,4,2,3,15,5,3,8,171,5,3,8,174,5,3,8,426,5,3,8,234,6,4,15,36371,6,4,15,12972,6,4,15,51313,6,4,15,13644,6,4,15,50259,6,4,15,12776,6,4,15,51747,6,4,15,6028,7,4,15,26962,7,4,15,9622,7,4,15,19094,7,4,15,27044,8,5,24,9054370,8,5,24,2271880,9,4,15,51794,9,4,15,13732,9,4,15,19027,9,4,15,9644,10,4,19,305490,10,5,19,206412,10,5,19,411942,10,4,19,154020,11,3,8,427,11,3,8,238,12,6,35,52217012547,12,6,35,3306785328,13,3,8,170,14,3,8,428,14,3,8,458,14,3,8,107,14,3,8,167,14,3,8,482,14,3,8,302,14,3,8,143,14,3,8,233,14,3,8,241,14,3,8,157,14,3,8,286,14,3,8,370,14,3,8,181,14,3,8,115,14,3,8,346,14,3,8,412,15,4,15,51219,15,4,15,12684,15,4,15,52275,15,4,15,13260,16,1,2,7,16,3,2,7,17,3,29,313075026,17,10,29,139324548,17,3,23,16252911,17,8,23,16760319,17,5,49,152335562622276,17,10,49,277354493774076,17,7,69,75835515713922895368,17,10,69,138634868908666122360,17,9,89,135722011765098439128942648,17,10,89,58184575467336340020006960,17,5,59,160968502306438596,17,12,59,145347113669124612,17,5,59,524156984170595886,17,12,59,434193401052698118,17,5,69,164495599269019571652,17,14,69,222245969722444385292,17,5,69,517140479305239282702,17,14,69,222262922122170485772,17,3,47,83020951028178,17,16,47,39740928107556,17,3,35,62664969879,17,12,35,40432499049,17,3,41,1581499314234,17,14,41,1293532058322,17,3,41,4349006881983,17,14,41,3376910168355,17,3,47,92426891685930,17,16,47,83780021865522,17,3,47,79346167206930,17,16,47,11342241794640,18,13,168,166245817041425752669390138490014048702557312780060,18,15,224,1711376967527965679922107419525530922835414769336784993839766570000,18,13,168,141409121010242927634239017227763246261766273041932,19,2,7,126,19,4,7,231,19,4,7,126,19,2,7,189,19,4,15,24966,19,4,15,18834,19,4,15,10644,19,4,15,26646]!p|p<-[h..h+3]]|h<-[0,4..424]],j<-[[[q!y!x|x<-[a..a+c]]|y<-[b..b+d]]|c<-r,d<-r,a<-[0..(length$q!0)-c-1],b<-[0..length q-d-1]],u i==j]in show[(words"aircraftcarrier barge beehive biloaf1 block boat eater1 loaf longbarge longboat mango ship shiptie tub glider beacon blinker pentadecathlon pulsar toad"!(e!0),sum[1|f<-g,e!0==f!0])|e<-g])

```

Here's the Mathematica code used to pack an array of 0,1's into the format later unpacked by the haskell program:

```
rotate[m_]:=Transpose[Map[Reverse,m]]
findInversePermutation[m_]:=Block[{y=Length[First[m]], x=Length[m]}, InversePermutation[FindPermutation[Flatten[m], Flatten[Table[Table[Flatten[m][[i+1]], {i, Select[Range[0, x * y - 1], Mod[#, x]==j&]}], {j, 0, x - 1}]]]]]
enumShape[m_]:=Partition[Range[1, Length[Flatten[m]]], Length[m[[1]]]]
pack[m_]:={Length[rotate[rotate[m]]], Length[Flatten[rotate[rotate[m]]]], FromDigits[Permute[Flatten[rotate[rotate[m]]], findInversePermutation[enumShape[rotate[rotate[m]]]]], 2]}

```

Here's a much more complete ungolfing of the code:

```
range = [1..16]          -- all of the patterns fall within this range

list ! 0        = list !! 0           -- this is a simple generic (!!)
list ! position = (tail list) ! (position - 1)

unpack [_, unpackedLength, unpackedSize, packed] = [ [odd $ div packed (2^i) | i <- [0..unpackedSize], (mod i unpackedLength) == j] | j <- [0..unpackedLength - 1]]

main=interact doer

doer input = show $ tallyByFirst (words nameString) foundPatterns -- this counts equalities between the list of patterns and the submatrices of the input
  where
    parsed = parse input -- this selects the non-comment lines and converts to an array of Bool's
    foundPatterns = countOccurrences partitioned subArrays
    subArrays     = allSubArrays parsed
    partitioned   = modPartition compressed 428 4 -- this partitions the compressed patterns into the form [name number, x length, x length * y length, packed integer]

countOccurrences patterns subArrays = [pattern | pattern <- patterns, subArray <- allSubArrays q, unpack pattern == subArray]

subArray m offsetX subSizeX offsetY subSizeY = [[m ! y ! x | x <- [offsetX..offsetX + subSizeX]] | y <- [offsetY..offsetY + subSizeY]]

allSubArrays m = [subArray m offsetX subSizeX offsetY subSizeY | subSizeX <- range, subSizeY <- range, offsetX <- [0.. (length $ head m) - subSizeX - 1], offsetY <- [0..(length m) - subSizeY - 1]]

tallyByFirst names list = [ (names ! (a ! 0), sum [1 | a <- list, (head a) == (head b)]) | b <- list]

parse string = [map (=='O') line | line <- lines string, head line /= '!']

modPartition list chunksize = [ [list ! position | position <- [offset..offset + chunksize - 1]] | offset <- [0, chunksize..(length list) - chunksize]]

```

---
Tags: code-golf, parsing, game-of-life
---


title: 9 Deaths of the Ninja

text:
# Question
Title: 9 Deaths of the Ninja
*Inspired by this conversation in chat.*

Your goal in this challenge is to emulate a ninja and count how many deaths he has left.

## Specs

You ninja starts out with 9 deaths left. He also gets an integral starting health as an input.

Then, he takes as input a list of events in his life that alter his health. These can be negative, positive, or zero integers.

At any point, if his health reaches at or below zero, he loses a life and his health goes back to the starting health.

Your program should report the number of deaths he has left. If he has zero or less left, you should output `dead` instead.

This is , so shortest code in **bytes** wins!

## Test Cases

```
3, [] -> 9
100, [-20, 5, -50, 15, -30, -30, 10] -> 8
10, [-10, -10, -10, -10] -> 5
10, [-10, -10, -10, -10, -10, -10, -10, -10, -10] -> dead
0, [] -> dead
0, [1] -> dead
100, [10, -100] -> 9

```

# Answer
> 8 votes
# Jelly, ~~30~~ ~~28~~ 26 bytes

```
»0o⁴+
;@ñ\<1S_9«0N“dead”×?

```

Try it online!

### How it works

```
;@ñ\<1S_9«0N“dead”×?  Main link. Input: e (events), h (initial health)

;@                    Prepend h to e.
  ñ\                  Reduce the resulting array by the next, dyadic link.
                      This returns the array of intermediate results.
    <1                Check each intermediate value for non-positivity.
      S               Sum. This calculates the number of event deaths.
       _9             Subtract 9 from the result.
         «0           Take the minimum of the result and 0. This yields 0 if no
                      lives are left, the negated amount of lives otherwise.
                   ?  Conditional:
                  ×     If the product of the minimum and h is non-zero:
           N              Return the negated minimum.
            “dead”      Else, return "dead".

»0o⁴+                 Dyadic helper link. Arguments: x, y

»0                    Take the maximum of x and 0.
                      This yields x if x > 0 and 0 otherwise.
  o⁴                  Take the logical OR of the result and the second input (h).
    +                 Take the sum of the result and y.

```

# Answer
> 7 votes
# Japt, ~~40~~ ~~39~~ 32 bytes

```
U¬©(9-Vf@T=X+(T¬²ªU)<1} l)¬²ª`Ü%

```

Try it online!

### How it works

While trying to golf this last night (away from a computer, no less), I ran across an interesting replacement for `>0`: `¬`. On numbers, this takes the square root, which returns `NaN` for negative numbers. `NaN` is falsy, so this returns exactly the same truthily/falsily as `>0`.

Extending this trick a little further, we can reset T to U iff it's `>=0` in only five bytes: `T¬²ªU`. How does this work? Let's take a look:

```
T    ¬      ²       ªU
     sqrt   square  if falsy, set to U (JS's || operator)
4    2      4       4
7   ~2.646  7       7
0    0      0       U
-4   NaN    NaN     U
-7   NaN    NaN     U

```

As you can see, `T¬²` returns `NaN` if `T` is negative; otherwise, it returns `T`. Since `NaN` and `0` are both falsy, this provides an easy way to reset the ninja's health with `ªU`. This trick is also used to return the ninja's lives left if that number is positive, or `"dead"` if negative.

Putting this all together:

```
           // Implicit: U = starting health, V = events, T = 0
U¬©        // If U is positive,
Vf@     }  // Filter out the items X in V that return truthily from this function:
 T=X+      //  Set T to X plus
 (T¬²ªU)   //   If T is positive, T; otherwise, U.
           //  This keeps a running total of the ninja's health, resetting upon death.
 <1        //  Return (T < 1).
9-    l)   // Take the length of the resulting array and subtract from 9.
           // This returns the number of lives the ninja has left.
¬²         // If the result is negative, set it to NaN.
ª`Ü%       // If the result of EITHER of the two parts above is falsy, return "dead".
           //  (`Ü%` is "dead" compressed.)
           // Otherwise, return the result of the middle part (lives left).
           // Implicit: output last expression

```

If the input is guaranteed to be non-negative, or even positive, we can golf of 1 or 4 bytes:

```
U©(9-Vf@T=X+(T¬²ªU)<1} l)¬²ª`Ü%  // U is non-negative
9-Vf@T=X+(T¬²ªU)<1} l)¬²ª`Ü%     // U is positive

```

# Answer
> 6 votes
## JavaScript ES6, ~~62 60~~ 58 bytes

*Saved 4 bytes thanks to @ETHproductions*

```
(a,b,d=9,l=a)=>b.map(i=>l=l+i<1?d--&&a:l+i,a)|d<1?"dead":d

```

Try it online (All browsers work)

## Explanation

```
(a,b,    // a = 1st input, b = 2nd input
 d=9)=>  // Lives counter

  (b.reduce((l,i)=>     // Loop through all the health changes
    l+i<1                 // If (health + health change) < 1
    ?(d--,a)              // Decrease life, reset health
    :l+i                  // Return new health
  ,a)                   // Sets starting health to `a`
  ,d<1?        // Lives is less than 1
   "dead":d);  // Output "dead" otherwise lives left

```

# Answer
> 4 votes
# CJam, 35 bytes

```
q~_@{+_1<{W$}&}/](\,_A<@*A@-"dead"?

```

Try it online!

# Answer
> 2 votes
## Haskell, ~~81~~ ~~77~~ 75 bytes

```
p l i h a|l<1="dead"|i<1=p(l-1)h h a|[]<-a=show l|x:y<-a=p l(i+x)h y
p 10 0

```

Usage example: `p 10 0 100 [-20, 5, -50, 15, -30, -30, 10]` -\> `"8"`

# Answer
> 1 votes
# TeaScript, ~~36 34~~ 31 bytes

```
yR#l+i<1?e─·x:l+i,x);e≥0?e:D`Ü%

```

Similar to my JavaScript answer. the last 4 characters are the decompression of the string "dead".

TeaScript's online interpreter doesn't support array input so you're going to need to open the console, and run this by typing:

```
TeaScript( `yR#l+i<1?(e─,x):l+i,x);─e>0?e:D\`Ü%` ,[
  10, [-10, -10, -10, -10]
],{},TEASCRIPT_PROPS);

```

### Explanation

```
      // Implicit: x = 1st input, y = 2nd input
yR#   // Reduce over 2nd input
  l+i<1?  // If pending health is less then 1
  (e─,x): // then, decrease life counter, reset health
  l+i     // else, modify health
,x);  // Set starting health
─e>0? // Ninja is alive?
e:    // Output lives left
D`Ü%  // Decompress and output "dead"

```

# Answer
> 1 votes
# Pyth, 32

```
 u+?>GZG&=hZQH+E0Q?&Q<Z9-9Z"dead

```

Note that there is a leading space. This probably isn't the best approach, but it was the first thing that came to mind. It reduces over input by adding the values to the ninja's health, and incrementing a counter and resetting the health when it drops below zero. We add a zero to the end of the list to count if the last change kills the ninja, and then just do some checking to see if the ninja is dead. The zero starting health case is hard coded.

Test Suite

# Answer
> 1 votes
# MATL, 32

```
9yi"@+t0>~?x1-y]]g*wxt0>~?x'dead'

```

## Explanation

```
9        # push 9
y        # duplicate 2nd value to top (there is none -> get it from input first)
i        # get input and push it

```

The stack now looks like this (for input `100, [-20, 5, -50, 15, -30, -30, 10]`):

```
100        9        100        [-20, 5, -50, 15, -30, -30, 10]

reload   deaths    health
value    left

```

Pop the array and loop

```
"            ]    # loop
 @+               # add to health
   t0>~?    ]     # if health is zero or less
        x1-y      # delete health counter, decrement life counter, reload health

```

If the health is zero, set death counter to zero. Special case handling for `initial health = 0`.

```
g        # health to bool
*        # multiply with death counter

```

Delete the reload value from stack

```
wx

```

If the death counter is zero or less, delete it and print 'dead' instead.

```
t0>~?x'dead'

```

# Answer
> 1 votes
## Python 2.7, 82 66 55 106 bytes

*Thanks to @RikerW for -16 bytes.:(*

*Thanks to @Maltysen for -11 bytes. :(*

```
i=input;h=[i()]*9;d=i()
if 0==h[0]:print'dead';exit()
for x in d:
 h[0]+=x
 if h[0]<=0:h=h[1:]
y=len(h)
print['dead',y][y!=0]

```

First type health, then enter, then events in list form.

# Answer
> 0 votes
## C# 207

```
class P{static void Main(string[]a){int h=int.Parse(a[0]),H=h,l=9,i=1;if(a.Length!=1){for(;i<a.Length;i++){H+=int.Parse(a[i]);if(H<=0){l--;H=h;}}}System.Console.Write(h==0?"dead":l<=0?"dead":l.ToString());}}

```

Takes the input through argument stream. The first argument is the amount of health and all the rest is the list of events.

Readable / ungolfed version

```
class Program
{
    static void Main(string[]a)
    {
        int health = int.Parse(a[0]);
        int Health = health;
        int lives = 9;

        if(a.Length!=1)
        {
            for (int i = 1;i < a.Length;i++)
            {
                Health += int.Parse(a[i]);
                if (Health <= 0)
                {
                    lives--;
                    Health = health;
                }
            }
        }

        System.Console.Write(health == 0 ? "dead" : lives <= 0 ? "dead" : lives.ToString());
    }
}

```

Examples:

* CSharp.exe 3 =\> 9
* CSharp.exe 100 -20 5 -50 15 -30 -30 10 =\> 8

(Psst.) CSharp.exe is name used as an example. You have to call like this in reality: \[program\_name.exe\] arguments, without the square parentheses.

---
Tags: code-golf, number, simulation
---


title: The absent-minded linguist

text:
# Question
Title: The absent-minded linguist
## Background

Your friend, a linguist, has recorded and analyzed some simple conversation snippets in various languages. Being quite absent-minded, they have forgotten which language each snippet was in. You must help them by creating a program that analyzes the sentence structures and rules out impossible cases.

## Input

Your input is a non-empty string containing the characters `SVO`, which stand for *subject*, *verb*, and *object*. It represents a conversation snippet analyzed by the linguist.

## Output

Your task is to break the string into sentences, and enter a period `.` after each sentence. A sentence contains either a verb, OR a verb and a subject, OR a verb, a subject and an object. However, you don't know which word order the original language uses; English uses subject-verb-object, but other languages, like Latin, use subject-object-verb. In fact, all six permutations exist in natural languages, so you must check each of them.

Your output shall contain, in a newline-separated string, each applicable word order, a colon `:`, and the input string broken into sentences according to that order. If the string cannot be parsed in some word order, the corresponding line shall be omitted. The order of the lines does not matter, and it is guaranteed that at least one word order can be parsed.

## Example

Consider the input

```
VSVOSV

```

In the `VOS` order, the snipped can be parsed as `VS.VOS.V.`, and in the `SVO` order, it can be parsed as `V.SVO.SV.`. The order `OSV` also works, and the full output is

```
VOS:VS.VOS.V.
SVO:V.SVO.SV.
OSV:V.SV.OSV.

```

## Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. Regular expressions and all built-ins are allowed.

## Test cases

```
Input:
V
Output:
VSO:V.
VOS:V.
SVO:V.
OVS:V.
SOV:V.
OSV:V.

Input:
SVV
Output:
SVO:SV.V.
SOV:SV.V.
OSV:SV.V.

Input:
VSVOV
Output:
SVO:V.SVO.V.

Input:
VSOVS
Output:
VSO:VSO.VS.
OVS:VS.OVS.

Input:
SVOSV
Output:
SVO:SVO.SV.
OSV:SV.OSV.

Input:
VSVOSV
Output:
VOS:VS.VOS.V.
SVO:V.SVO.SV.
OSV:V.SV.OSV.

Input:
VSVVSOVSV
Output:
VSO:VS.V.VSO.VS.V.
OVS:VS.V.VS.OVS.V.
SOV:V.SV.V.SOV.SV.

Input:
SVVSVSOVSVV
Output:
SOV:SV.V.SV.SOV.SV.V.

Input:
VSOVSVSOVSVVS
Output:
VSO:VSO.VS.VSO.VS.V.VS.
OVS:VS.OVS.VS.OVS.V.VS.

```

# Answer
> 1 votes
# Perl 5 - 104 bytes

```
$a=<>;for(qw/VSO VOS SVO OVS SOV OSV/){$s=s/O//r;print"$_:".$a=~s/($_|$s|V)/$1./gr if$a=~/^($_|$s|V)*$/}

```

# Answer
> 1 votes
# JavaScript (ES7), 172 bytes

```
x=>[for(i of"V(SO?)?0V(O?S)?0(SVO?|V)0(O?VS|V)0(SO?)?V0(O?S)?V".split(0))if((y=x.match(RegExp(i,"g"))).join``==x)i.match(/\w/g).slice(0,3).join``+":"+y.join`.`+"."].join`
`

```

Could probably be golfed further. Suggestions welcome!

---
Tags: code-golf, string, parsing, permutations, set-partitions
---