# Question
Title: Find the last Sunday in every month of a given year
F# solutions known inside 140 chars, and this is a Rosetta Code problem.

Required result on stdout or in a string variable for input year `2014`:

```
2014-01-26 2014-02-23 2014-03-30 2014-04-27 2014-05-25 2014-06-29 2014-07-27 2014-08-31 2014-09-28 2014-10-26 2014-11-30 2014-12-28

```

As it was requested, for 1900:

```
1900-01-28 1900-02-25 1900-03-25 1900-04-29 1900-05-27 1900-06-24 1900-07-29 1900-08-26 1900-09-30 1900-10-28 1900-11-25 1900-12-30

```

And 2000:

```
2000-01-30 2000-02-27 2000-03-26 2000-04-30 2000-05-28 2000-06-25 2000-07-30 2000-08-27 2000-09-24 2000-10-29 2000-11-26 2000-12-31

```

Posed because dates seem to bring out awkwardness in most languages. More than permitting date libraries, I hope to see them! But if external to the base language, declare in the name of the post (e.g. C# + Jon Skeet's NodaTime).

Clarifications:

* Year range 1900 to 3015
* Gregorian calendar
* If it otherwise matters, whatever is conventional for UK/London.
* A program taking a commandline switch or stdin is fine, producing the result to stdout
* A function taking a value for the year and returning a string is also fine.

Standard loopholes excluded. Looking forward to the APL, J, K solutions, and seeing some new date libraries.

# Answer
# Dyalog APL with cal from dfns, 19 bytes

Better late than never!

Prompts for year, returns list of dates in *yyyy m d* format.

```
⎕{⍺⍵,2↑⊢⌿cal⍺⍵}¨⍳12

```

prompt for numeric input and let that be the left argument to the

`{` ...  anonymous function (found below) applied to each of

`⍳12` the numbers from 1 to 12 (the months)

The above anonymous function is as follows:

`⍺⍵,` prepend the left and right arguments (i.e. year and month) to

`2↑` the first two characters of

`⊢⌿` the bottom-most row of

`cal` the calendar for

`⍺⍵` left argument and right argument (year and month)

### TryAPL online:

1. Return to this page after clicking here to import `cal` and its dependencies.
2. Click here to run the test cases.
> 1 votes

# Answer
# Ruby, 91+6=97

```
#!ruby -prdate
$_=(Date.new(y=$_.to_i)...Date.new(y+1)).select(&:sunday?).chunk(&:mon).map{|k,v|v[-1]}*' '

```

Works out pretty well. `select(&:sunday?)` is pretty, and surprisingly, `*' '` does all of the formatting by itself.
> 7 votes

# Answer
# Bash 4.x + ncal, 57

If newline separators are OK instead of spaces, then we can remove the `-n` switch and trailing space from the `echo` statement. And I guess it will still work without the shebang, so I removed that too:

```
for i in {01..12};{ echo "$1-$i-`ncal $i $1|tail -c-3`";}

```

Original script (73 bytes):

```
#!/bin/bash
for i in {01..12};{ echo -n "$1-$i-`ncal $i $1|tail -c-3` ";}

```

### Usage:

```
$ bash sundays.sh 2014
2014-01-26
2014-02-23
2014-03-30
2014-04-27
2014-05-25
2014-06-29
2014-07-27
2014-08-31
2014-09-28
2014-10-26
2014-11-30
2014-12-28
$

```

**Note:** Bash versions prior to 4.0 will omit the leading zeroes from the months. This can be fixed with the addition of 5 characters by changing `{01..12}` to ``seq -w 1 12)``. Also, `tail -c-3` might cause problems on some systems where the output of `ncal` includes trailing spaces, but I'm not aware of any that do.
> 6 votes

# Answer
# IBM DFSORT, ~~11~~ 3 lines of 71, 72 or 80 characters

```
 OPTION COPY
 OUTFIL REPEAT=12,OVERLAY=(5:SEQNUM,2,ZD,5,2,1,8,Y4T,LASTDAYM,TOJUL=Y4T*
 ,9,7,Y4T,ADDDAYS,+1,TOJUL=Y4T,1:16,7,Y4T,PREVDSUN,TOGREG=Y4T(-),12X)

```

The two answers with columnar output format have stood the test of time. That gives me a "loop", sort of, in that on OUTFIL REPEAT= copies the current record that many times.

Different technique to get to the value, which seems longer but is shorter as I can't work out any unconditional way to deal with the 12th record being in the following year, and making it conditional means including `IFTHEN=(WHEN=`, twice, and some other stuff. Gain on the swings (first of month is simplest way to do it) lose heavily on the roundabouts (particular syntax requirements).

This uses an inbuilt function (all functions in DFSORT are inbuilt) to find the last day of the month. Then adds one day (function) to get to first of following month and uses the PREVDSUN function to get the previous Sunday (which will always be the last Sunday in the previous month, as before).

When turning the year (input) into a valid date, a two-digit sequence number is used for the month, and that value is copied for the day as well, since the starting point does not matter as long as valid, as we are after the last day of the month initially: `5,2` is shorter than `C'01'`.

Here's the detail:

OPTION COPY - copy input file to output

OUTFIL - to allow multiple output files, with different selection and formatting, produce formatted reports. Used in preference to the shorter `INREC` because of the use of `REPEAT=`.

REPEAT=12 - produce 12 copies of each record. In this example, there can be only one input record (unlike the previous version) because of the SEQNUM.

5: - start at column 5 on the record.

SEQNUM,2,ZD - sequence number, defaults to start at one, two digits, "zoned decimal" (for unsigned, which they will be, same as character).

1,8 - copy bytes 1 for length 8 to current location (9). This is because the Y4T need to see that 8, else a different date format will be used.

Y4T - ccyymmdd-format date (due to the 8 immediately in front of it).

LASTDAYM - Last day of Month (also possible of Week, Quarter and Year).

TOJUL= - output date-conversion for date functions (TOJUL is one character less than TOGREG)

9,7 - now that it is 7 long, Y4T is going to be CCYYDDD.

ADDDAYS - adds a number of days, adjusting automatically if goes into following month/year (could also be ADDMONS and ADDYEARS)

PREVDSUN - the Julian date comes in, previous Sunday is located, TOGREG to get the correct output format, with the "-" seperator (could be anything you like as separator)

12X - blanks to clear up the mess which has allowed us to do it in such a short way

The output from the above, for 2014, is:

```
2014-01-26
2014-02-23
2014-03-30
2014-04-27
2014-05-25
2014-06-29
2014-07-27
2014-08-31
2014-09-28
2014-10-26
2014-11-23
2014-12-28

```

Something is required to tell the SORT what to do. There is no default. `OPTION COPY` is the shortest, `SORT FIELDS=COPY` is equivalent but longer.

The work itself it done this time in `OUTFIL` (to allow the use of REPEAT). The working code is arguably any of 160 (2 * 80), 144 (2 * 72), 140 (72 + 69), or 138 (70 + 68) (excluding the leading blanks, forced continuation and trailing blanks).

Given that the receiver would have to know what they are doing, I think I can say that the DFSORT code to list the last Sunday of each month for any year from 1900 (will run from year 0001, but I'm avoiding the research as well) up to 9999 (although DFSORT supports years up to 9999, previous solution would not work in year 9999 since the 12th date goes into the following year) can be Tweeted.

Why is the code so long, if there are especially apt inbuilt-functions?

Field-definitions are ephemeral. A field is only defined as a particular location within the data (which is a record) for its immediate use. To put it another way, fields are not defined as such, but are defined for each use and only for use. Date functions need to know which (of many) formats of date are used for the source, and the output must be in a date format, so that has to be specified.

Now that we have a Julian date.... TBC?

---

```
 OPTION COPY
 INREC OVERLAY=(1,4,C'0201',1,8,1,8,1,8,1,8,1,8,1,8,1,8,1,8,1,8,1,8,1,8*
 ,94:C'1',89:1,4,ZD,ADD,+1,ZD,LENGTH=4,14:C'3',22:C'4',30:C'5',38:C'6',*
 46:C'7',54:C'8',62:C'9',69:C'10',77:C'11',85:C'12',127:X,89,8,Y4T,PREV*
 DSUN,TOGREG=Y4T(-),116:X,81,8,Y4T,PREVDSUN,TOGREG=Y4T(-),105:X,73,8,Y4*
 T,PREVDSUN,TOGREG=Y4T(-),94:X,65,8,Y4T,PREVDSUN,TOGREG=Y4T(-),83:X,57,*
 8,Y4T,PREVDSUN,TOGREG=Y4T(-),72:X,49,8,Y4T,PREVDSUN,TOGREG=Y4T(-),61:X*
 ,41,8,Y4T,PREVDSUN,TOGREG=Y4T(-),50:X,33,8,Y4T,PREVDSUN,TOGREG=Y4T(-),*
 39:X,25,8,Y4T,PREVDSUN,TOGREG=Y4T(-),28:X,17,8,Y4T,PREVDSUN,TOGREG=Y4T*
 (-),17:X,09,8,Y4T,PREVDSUN,TOGREG=Y4T(-),1:1,8,Y4T,PREVDSUN,TOGREG=Y4T*
 (-),11:X,18,120,6X)

```

Needs some `JCL`

```
//LASTSUNG EXEC PGM=SORT
//SYSOUT   DD SYSOUT=*
//SORTOUT  DD SYSOUT=*
//SYSIN    DD *

```

And an input file (another line of JCL and three instream items of data):

```
//SORTIN DD *
2014
1900
2000

```

Produces:

```
2014-01-26 2014-02-23 2014-03-30 2014-04-27 2014-05-25 2014-06-29 2014-07-27 2014-08-31 2014-09-28 2014-10-26 2014-11-30 2014-12-28
1900-01-28 1900-02-25 1900-03-25 1900-04-29 1900-05-27 1900-06-24 1900-07-29 1900-08-26 1900-09-30 1900-10-28 1900-11-25 1900-12-30
2000-01-30 2000-02-27 2000-03-26 2000-04-30 2000-05-28 2000-06-25 2000-07-30 2000-08-27 2000-09-24 2000-10-29 2000-11-26 2000-12-31

```

Will actually work up to the year 9999.

DFSORT is IBM's Mainframe sorting product. Data can be manipulated, but since sorting is key and sorts are often large and long-running, the DFSORT control cards have no looping constructs, so we can't put a SORT into a loop. Makes things a bit long-winded for tasks like Golf.

Why to post the answer, is because DFSORT has a `PREVDday` function. So last Sunday in a month is easy. It is the Sunday previous (PREVDSUN) to the first day of the following month.

It was also fun to do it within one "operand" (OVERLAY), a bit like doing it all within `sprintf` or similar.

Here it is ungolfed:

```
 OPTION COPY

 INREC OVERLAY=(1,4,C'0201',1,8,1,8,1,8,1,8,1,8,1,8,
         1,8,1,8,1,8,1,8,
         1,8,94:C'1',89:1,4,ZD,ADD,+1,ZD,LENGTH=4,
         14:C'3',22:C'4',30:C'5',38:C'6',46:C'7',54:C'8',
         62:C'9',69:C'10',77:C'11',85:C'12',
        127:X,89,8,Y4T,PREVDSUN,TOGREG=Y4T(-),
        116:X,81,8,Y4T,PREVDSUN,TOGREG=Y4T(-),
        105:X,73,8,Y4T,PREVDSUN,TOGREG=Y4T(-),
         94:X,65,8,Y4T,PREVDSUN,TOGREG=Y4T(-),
         83:X,57,8,Y4T,PREVDSUN,TOGREG=Y4T(-),
         72:X,49,8,Y4T,PREVDSUN,TOGREG=Y4T(-),
         61:X,41,8,Y4T,PREVDSUN,TOGREG=Y4T(-),
         50:X,33,8,Y4T,PREVDSUN,TOGREG=Y4T(-),
         39:X,25,8,Y4T,PREVDSUN,TOGREG=Y4T(-),
         28:X,17,8,Y4T,PREVDSUN,TOGREG=Y4T(-),
         17:X,09,8,Y4T,PREVDSUN,TOGREG=Y4T(-),
          1:1,8,Y4T,PREVDSUN,TOGREG=Y4T(-),
         11:X,18,120,6X)

```

Whilst not quite abuse, it wouldn't be usual to attempt to cram all this into one OVERLAY, and there is some seemingly unnecessary stuff which is needed to allow it all to go into one OVERLAY. There is some room for golfing, but since it would only remove one line at most, I'm not tempted.

The INREC is processed for each record.

OVERLAY allows the content of an existing record to be changed. If the record is extended beyond its length in the process, that is not a problem.

1,4 is the year coming in. It has a literal of 0201 appended to it, and then the successive 1,8s repeat it 11 times to give one long chuck of 96 bytes,

The 12th year on the extended current record gets 1 added to it, and its month made to 1 (January).

The remaining 10 months are changed to 3 through 11.

Then there are 12, in reverse order (due to OVERLAY) of these type of thing:

```
127:X,89,8,Y4T,PREVDSUN,TOGREG=Y4T(-),

```

The n: is a column-number on the record. The X inserts a blank. 89,8 takes the data from that column/length, Y4T treats it as a CCYYMMDD date, PREVDSUM works out the previous Sunday,TOGREG=Y4T(-) outputs it as a Gregorian CCYY-MM-DD date.

Because you get rubbish if the source and target of a particular part of an OVERLAY overlap destructively, the final `11:X,18,120,6X)` rearranges and masks a bit of mess.

Manuals and papers can be found at: http://www-01.ibm.com/support/docview.wss?uid=isg3T7000080, and includes the 900+ page DFSORT Application Programming Guide.

As with all IBM products all manuals are available for free (except an excruciatingly small amount of very expensive ones which only a very small number of people in the world would even pretend to understand).

All DFSORT Control Cards must start with a blank. Column 72 is only used for continuation (any non-blank will do, but * is conventional). Column 72 is followed by a sequence number area which is ignored, making the each record 80 bytes.

Another couple of solutions to come, maybe.
> 6 votes

# Answer
# Bash, 63 bytes

```
for i in {01..12};{  date -v30d -v${i}m  -v2014y  -vsun +%Y-%m-%d;}

```

Output:

```
2014-01-26
2014-02-23
2014-03-30
2014-04-27
2014-05-25
2014-06-29
2014-07-27
2014-08-24
2014-09-28
2014-10-26
2014-11-30
2014-12-28

```
> 5 votes

# Answer
# Python 2 - 189 bytes

```
y=input()
for m in range(12):
 d=[31-(1322>>m&1),28+(y%400<1or 1>y%4<y%100)][m==1];Y=y-(m<2);Z=Y%100;C=Y/100
 while(d+13*((m-2)%12+4)/5+Z+Z/4+C/4-2*C)%7-1:d-=1
 print"%d-%02d-%d"%(y,m+1,d),

```

Enter the date via STDIN.

Still a lot more golfing that can be done. The program goes a little overboard, just for fun:

* No imports, in particular not using any built-in date functions
* Uses Zeller's congruence for calculating days of the week

## Notes

* 1322 is a magic lookup table for determining whether a non-February month has 30 or 31 days
* No `zfill` is needed for years due to the input range, nor days as they will always be over 20

---

# Python 2 - 106 bytes

The not-as-fun solution:

```
from calendar import*
y=input();m=1
while m<13:w,n=monthrange(y,m);print"%d-%02d-%d"%(y,m,n-(n+w)%7),;m+=1

```

`calendar.monthrange` returns two numbers: the weekday the month starts on (`w`) and the number of days in the month (`n`). The solution is a little counterintuitive due to a catch — the weekday returned starts at 0 for *Monday*, not Sunday! However, this is offset by the fact that `n` is 1-based.
> 4 votes

# Answer
# JavaScript, ES6, ~~222 219~~ 199 bytes

I did not see any JavaScript answer in the rosetta wiki.

Here we go:

```
S=Y=>{for(l=[],p=new Date(Y,i=0);i<365+!(Y%4);)if(!(d=new Date(Y,0,++i,9)).getDay()){p.getMonth()-d.getMonth()&&l.push(p);p=new Date(d)}return[...l,p].map(x=>x.toISOString().split("T")[0]).join(" ")}

```

This creates a function `S` which returns a string with the desired output. the function also takes care of leap years.

Due to ES6, this only works in a latest Firefox.

*Thanks to apsillers for the tip which got it reduced to 200 bytes*

Find the ungolfed version below as a stack snippet which you can run here itself:

```
S=Y=>{
  for(l=[],p=new Date(Y,i=0);i<365+!(Y%4);)
    if(!(d=new Date(Y,0,++i,9)).getDay()){
      p.getMonth()-d.getMonth()&&l.push(p);
      p=new Date(d)
    }
  return[...l,p].map(x=>x.toISOString().split("T")[0]).join(" ")
}

alert(S(parseInt(prompt())))
```
> 3 votes

# Answer
# JavaScript (ES6) 155 ~~145~~

**Edit** Fixed timezone problems Could be shorter if made recursive. Maybe.

```
F=y=>{
  for(n=i=o=[];!o[11];)
    d=new Date(Date.UTC(y,0,++i)),m=d.getMonth(),
    d.getDay()||(m!=n&&o.push(p.toISOString().slice(0,10)),p=d,n=m);
  return o.join(' ')
}

```
> 3 votes

# Answer
# Rebol - 120 116 80 79 76

```
d: do join"1-1-"input print collect[for m 2 13 1[d/2: m keep d - d/weekday]]

```

Ungolfed + some annotations:

```
d: do join "1-1-" input         ;; golfy way to create Rebol date! datatype 1-Jan-(year)

print collect [
    for m 2 13 1 [              ;; loop thru months 2 to 13!
        d/2: m                  ;; move to (1st of) next month
        keep d - d/weekday      ;; collect/keep last sunday of month
    ]
]

```

Example of the sunday calculation in Rebol console:

```
>> ; get last sunday of Jan 2014

>> d: 1-1-2014
== 1-Jan-2014

>> d/month: d/month + 1
== 2

>> d
== 1-Feb-2014

>> d/weekday
== 6

>> d - d/weekday
== 26-Jan-2014

>> ; above is last sunday of Jan 2014
>> ; and when pass end of year (ie. month 13!)

>> d/month: 13
== 13

>> d
== 1-Jan-2015

```
> 3 votes

# Answer
# CJam, ~~122~~ 102 bytes

```
30li:X400%){[1387Yb30f+~28I!I4%!I100%e&|g+\]W%{\_2$>7*-\7%7\m1$+}/}fI;]12/W=12,{101+s1>}%]z{X+W%'-*S}/

```

This does not use any form of date library. It can be also still be golfed a lot, I think.

Test it here.
> 2 votes

# Answer
# R, 128 chars

```
P=paste;f=format;a=strptime(P(1:366,scan()),"%j %Y");cat(sort(sapply(split(a,f(a,"%B")),function(x)P(tail(x[f(x,"%u")==7],1)))))

```

With line breaks:

```
P=paste
f=format
a=strptime(P(1:366,scan()),"%j %Y")
cat(sort(sapply(split(a,f(a,"%B")),function(x)P(tail(x[f(x,"%u")==7],1)))))

```
> 1 votes

# Answer
## C# 255

Ungolfed

```
static void Main(string[] a)
    {
        int y = Int32.Parse(Console.ReadLine());
        DateTime d = new DateTime(y, 1, 1);
        while (d.Year == y)
        {
            if (d.DayOfWeek == DayOfWeek.Sunday && d.Day>(DateTime.DaysInMonth(y,d.Month)-7))
                Console.WriteLine(d.ToShortDateString());
            d = d.AddDays(1);
        }
        Console.ReadKey();
    }

```

Edit: modified to print only the **last** Sunday :)
> 1 votes

# Answer
"Oh, no, him again!"

# Java - ~~259~~ 246 bytes

```
void g(int y){for(int i=;i<12;i++){GregorianCalendar c=new GregorianCalendar(y,i,0);c.set(c.DAY_OF_WEEK,c.SUNDAY);c.set(c.DAY_OF_WEEK_IN_MONTH,-1);System.out.print(y+"-"+String.format("%02d",(c.get(c.MONTH)+1))+"-"+(c.get(c.DAY_OF_MONTH))+" ");}}

```

Ungolfed version:

```
void g(int y){
    for (int i = 0; i < 12;i++) {
        GregorianCalendar c = new GregorianCalendar(y, i, 0);
        c.set(c.DAY_OF_WEEK, c.SUNDAY);
        c.set(c.DAY_OF_WEEK_IN_MONTH, -1);
        System.out.print(y+"-"+String.format("%02d",(c.get(c.MONTH)+1))+"-"+(c.get(c.DAY_OF_MONTH))+" ");
    }
}

```

Usage:

```
import java.util.GregorianCalendar;
import java.util.Scanner;

public class LastSundayInYear {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Year?");
        int year = scanner.nextInt();
        LastSundayInYear sunday = new LastSundayInYear();
        sunday.g(year);
    }

    void g(int y){
        for (int i = -1; ++i < 12;) {
            GregorianCalendar c = new GregorianCalendar(y, i, 0);
            c.set(c.DAY_OF_WEEK, c.SUNDAY);
            c.set(c.DAY_OF_WEEK_IN_MONTH, -1);
            System.out.print(y+"-"+String.format("%02d",(c.get(c.MONTH)+1))+"-"+(c.get(c.DAY_OF_MONTH))+" ");
        }
    }
}

```

Output:

```
2014-01-26 2014-02-23 2014-03-30 2014-04-27 2014-05-25 2014-06-29 2014-07-27 2014-08-31 2014-09-28 2014-10-26 2014-11-30 2014-12-28

```

Yet another "let's put a Java reply just for kicks" answer. Oh well. But, at least, since you bothered to reach this point of my answer, I'll try to bore you some more and explain my reasoning.

The method `g` receives the desired year and, for each month, creates a `GregorianCalendar` object (months go from 0 to 11). Then, the first `c.set` sets the day of the week as a Sunday and the second declares that we want the *last* week of the month - as seen on the official documentation. The `System.out.println` prints out the date of that Sunday (if we were doing this right, the year would be printed as `c.get(c.YEAR)`, but using `y` again shaves off 13 characters), the month has to be formatted to add a leading zero from January to September (and the value is incremented because, well, months in here are represented 0-11) and the day of last Sunday is printed. And this procedure is repeated for the other eleven months.
> 1 votes

# Answer
# q, 67

```
{({{1<>x mod 7}-[;1]/x}')14h$1_til[13]+13h$"D"$(($)x),".01.01"}

```
> 1 votes

# Answer
## C#, 212, 237

```
string x(int y){var s="";var t="";var d=new DateTime(y,1,1);for(;;){if(d.Year!=y){return s;}t=(d.DayOfWeek==DayOfWeek.Sunday)?t=string.Format("{0}-{1}-{2} ",d.Year,d.Month,d.Day):t;s=(d.AddDays(1).Month!=d.Month)?s+=t:s;d=d.AddDays(1);}}

```

With line breaks

```
string x(int y)
    {
        var s = "";
        var t = "";
        var d = new DateTime(y,1,1);
        for (;;)
        {
            if (d.Year != y) {
                return s;
            }
            t = (d.DayOfWeek == DayOfWeek.Sunday) ? t = string.Format("{0}-{1}-{2} ", d.Year, d.Month, d.Day) : t;
            s=(d.AddDays(1).Month!=d.Month)?s+=t:s;
            d=d.AddDays(1);
        }
    }

```

Output for 2014

```
"2015-1-25 2015-2-22 2015-3-29 2015-4-26 2015-5-31 2015-6-28 2015-7-26 2015-8-30 2015-9-27 2015-10-25 2015-11-29 2015-12-27"

```
> 0 votes

# Answer
# C# 171

Function returning a string.

```
string S(int y){var r="";for(int m=1;m<13;++m){var d=new System.DateTime(y,1,1).AddMonths(m).AddDays(-1);r+=y+string.Format("-{0:00}-{1} ",m,d.Day-d.DayOfWeek);}return r;}

```

**Ungolfed**

```
string S(int y)
{
    var r="";
    for (int m=1;m<13;++m)
    {
        var d = new System.DateTime(y, 1, 1).AddMonths(m).AddDays(-1);
        r += y + string.Format("-{0:00}-{1} ", m, d.Day - d.DayOfWeek);
    }
    return r;
}

```
> 0 votes

# Answer
**VB-192**

```
Function z(y)
For i = 1 To 11
a = 0
s = IIf(i <> 11, DateSerial(y, i + 1, 1), DateSerial(y + 1, 1, 1))
While Weekday(s - a) <> 1
a = a + 1
Wend
r = r + Str(s - a) + " "
Next
z = r
End Function

```

Could be worse ^^

My second and last entry (don't think i can get it smaller)

**142**

```
Function z(y)
Dim m(12)
For i = 1 To 366
s = DateSerial(y, 1, 1) + i
If Weekday(s) = 1 Then m(Month(s)) = s
Next
z = Join(m, " ")
End Function

```
> 0 votes

# Answer
# C# 194

using Linq:

```
string d(int y){return string.Join(" ",Enumerable.Range(1,12).Select(m=>new DateTime(y,m,DateTime.DaysInMonth(y,m))).Select(d=>d.AddDays(-(int)d.DayOfWeek)).Select(d=>d.ToString("yyy-MM-dd")));}

```

**Ungolfed**

```
string d(int y)
{
    return string.Join(" ",Enumerable.Range(1,12)
        .Select(m => new DateTime(y, m, DateTime.DaysInMonth(y, m)))
        .Select(d => d.AddDays(-(int)d.DayOfWeek))
        .Select(d => d.ToString("yyy-MM-dd")));
}

```

**Output**

```
2013-01-27 2013-02-24 2013-03-31 2013-04-28 2013-05-26 2013-06-30 2013-07-28 2013-08-25 2013-09-29 2013-10-27 2013-11-24 2013-12-29

```
> 0 votes

# Answer
# Mathematica - 171

Wrapped in an anonymous function, returns the string

```
StringJoin[Last@#~DateString~{"Year","-","Month","-","Day"," "}&/@GatherBy[Select[DateRange[DateObject[{#}],DateObject[{#+1}]],DayName@#==Sunday&],DateValue[#,"Month"]&]]&

```

First mathematica golf. I feel like it could be substantially reduced.
> 0 votes

# Answer
# Ruby 76

Uses a commandline parameter `ruby sundays.rb 1900`. Uses the Date library.

```
require'date';puts (1..12).map{|m|d=Date.new($*[0].to_i,m,-1);d-d.wday}*" "

```
> 0 votes

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


title: Generate a map for a roguelike

text:
# Question
Title: Generate a map for a roguelike
# Today, we'll be generating a map for a roguelike RPG!

## Example Map:

```
##########
####    F#
####    ##
##    C#C#
#     ## #
# C   #E #
####  #  #
#        #
#P       #
##########

```

`#` are walls, `P` is the player's starting location, `F` is the finish that must be reached, `C` are coins that can be collected, and `E` are enemies that can be fought.

## Map specifications:

* Height and Width should both be between 10 and 39, inclusive. Height does not have to equal width.
* The maps borders should be filled in with walls.
* `P` should be placed in the bottom left corner.
* `F` should be placed in the top right corner.
* There should be between 1 and 3 enemies.
* There should be between 2 and 4 coins.
* There should be some amount of walls in the middle. There should be a path to get from `P` to Every `C`, `E`, and `F`, keeping in mind that the player cannot move diagonally.
* Every possible combination should have some chance of occurring.

## Rules

* Fewest byte program wins.
* Your program should not take any input.
* Your program may not exit with an error (non-fatal output is `STDERR` is ok, but we can't have our rogue-like crash after map generation!)
* A single trailing newline is allowed and trailing space is allowed.
* No other output is allowed.

# Answer
## Perl, 293 bytes

*-9 bytes thanks to @Dom Hastings*

```
{$==7+rand 30;@r=$"=();@a=((C)x4,(E)x3,("#")x1369,(" ")x1369);for$i(0..7+rand 30){$r[$i][$_]=splice@a,rand@a,1for 0..$=}$r[0][$=]=F;$r[-1][0]=P;$_=$r=join$/,$v="#"x($=+=3),(map"#@$_#",@r),$v;1while$r=~s/F(.{$=})?[^#F]/F$1F/s||$r=~s/[^#F](.{$=})?F/F$1F/s;$r!~/[CEP]/&&/C.*C/s&&/E/?last:redo}say

```

Add `-E` flag to run it:

```
perl -E '{$==7+rand 30;@r=$"=();@a=((C)x4,(E)x3,("#")x1369,(" ")x1369);for$i(0..7+rand 30){$r[$i][$_]=splice@a,rand@a,1for 0..$=}$r[0][$=]=F;$r[-1][0]=P;$_=$r=join$/,$v="#"x($=+=3),(map"#@$_#",@r),$v;1while$r=~s/F(.{$=})?[^#F]/F$1F/s||$r=~s/[^#F](.{$=})?F/F$1F/s;$r!~/[CEP]/&&/C.*C/s&&/E/?last:redo}say'

```

However, it takes a long time to run, so I recommend using this version instead:

```
perl -E '{${$_}=8+rand 30for"=","%";@r=$"=();@a=((C)x4,(E)x3,("#")x($v=rand $=*$%),(" ")x($=*$%-$v));for$i(0..$%-1){$r[$i][$_]=splice@a,rand@a,1for 0..$=-1}$r[0][$=-1]=F;$r[$%-1][0]=P;$_=$r=join$/,$v="#"x($=+=2),(map"#@$_#",@r),$v;1while$r=~s/F(.{$=})?[^#F]/F$1F/s||$r=~s/[^#F](.{$=})?F/F$1F/s;$r!~/[CEP]/&&/C.*C/s&&/E/?last:redo}say'

```

Try it online!

**Explanation**

```
{                     # enter a block (which is used as a loop)
    {$==7+rand 30;                   # randomly select the width of the map -2
                                     # (-2 because we don't include the borders yet)
    @r=$"=();                        # reset @r, and set $" to undef
    @a=(                             # create a list of the character that can be on the board
     (C)x4,                          #  4 coins 'C'
     (E)x3,                          #  3 enemies 'E'
     ("#")x1369,                     #  37*37 '#'
     (" ")x1369);                    #  37*37 spaces
    for$i(0..7+rand 30)                # create the 2D map (7+rand 30 is the height, which is generated just now)
      for$_(0..$=-1){
        $r[$i][$_]=                    # index [$i][$_] receives ...
           splice@a,rand@a,1           # .. a random character from the list previously generated
                                       # (the character is then removed from the list thanks to 'splice')
      }
    }
    $r[0][$=]=F;                       # add the finish cell
    $r[-1][0]=P;                       # add the start cell
    $_=$r=                             # here we generate a string representation of the map
          join$/,                      # join the following elements with newlines
            $v="#"x($=+=3),            # a first line of # only
            (map"#@$_#",@r),           # add a # to the beginning and the end of each line
            $v;                        # the last line of #

    1while                # the following regex will replace every accessible cell with a F
       $r=~s/F(.{$=})?[^#F]/F$1F/s  # a cell on the right or the bottom of a F cell is replaced
         ||                         # or
       $r=~s/[^#F](.{$=})?F/F$1F/s; # a cell on the left or the top of a F cell is replaced
    $r!~/[CEP]/         # if there is no C, E or P on the map (meaning they were all accessible)
     && /C.*C/s         #  and there are at least 2 coins
     && /E/ ?           #  and 1 enemy
      last:             # the the map is valid, we exit the loop
      redo              # else, start over
}
say                     # and print the board

```

It takes a long time to run, because the list from which we randomly pick the characters to put on the board (`@a`) contains 1369 whitespaces and `#`, and only 4 coins and 3 enemies. So if the size of the width and height are small, there are a lot of spaces and `#` compared to the coin and the enemies, so it's quite likely that a random map won't be valid. That's why the "optimized" version is faster: the list from which we pick the characters is just a little bigger than the map (the list is `@a=((C)x4,(E)x3,("#")x($v=rand $=*$%),($")x($=*$%-$v))` : a random number `$v` of `#` (inferior to the size of the map), and `size of the map - $v` whitespaces).
> 5 votes

# Answer
# PHP, ~~422~~ ~~417~~ ~~415~~ ~~309~~ ~~373~~ ~~369~~ ~~364~~ 361 bytes

```
function w($p){global$r,$h,$w;for($q=$p;$r[$q]<A;)for($r[$p=$q]=" ";($q=$p+(1-(2&$m=rand()))*($m&1?:$w))%$w%($w-1)<1|$q/$w%$h<1;);}$r=str_pad("",($w=rand(10,39))*$h=rand(10,39),"#");$r[$w*2-2]=F;w($p=$q=$w*(--$h-1)+1);$r[$p]=P;for($c=rand(2,4);$i<$c+rand(1,3);$p=rand($w,$h*$w))if($r[$p]<A&&$p%$w%($w-1)){w($p);$r[$p]=EC[$i++<$c];w($p);}echo chunk_split($r,$w);

```

operates on a string without linebreaks; digs random paths between the extras. Run with `-r`.

**Note:** The paths are created by walking in random directions. The choice of direction for every step will mostly generate maps that are wide open; and the example map is very unlikely to appear; but it *is* possible.

**breakdown**

```
// aux function: randomly walk away from $p placing spaces, stop when a special is reached
function w($p)
{global$r,$h,$w;
    for($q=$p;
        $r[$q]<A;                               // while $q is not special
    )
        for($r[$p=$q]=" ";                          // 3. replace with space
            ($q=$p+(1-(2&$m=rand()))*($m&1?:$w))    // 1. pick random $q next to $p
            %$w%($w-1)<1|$q/$w%$h<1;                // 2. that is not on the borders
        );
}

// initialize map
$r=str_pad("",
    ($w=rand(10,39))*$h=rand(10,39) // random width and height
    ,"#");                          // fill with "#"
$r[$w*2-2]=F;                       // place Finish
w($p=$q=$w*(--$h-1)+1);             // build path from Player position to F
// $h is now height -1 !
$r[$p]=P;                           // place Player

// place Coins ans Enemies
for($c=rand(2,4);$i<$c+rand(1,3);   // while $i has not reached no. of coins+no. of enemies
    $p=rand($w,$h*$w))              // pick a random position
    if($r[$p]<A&&$p%$w%($w-1))      // that is neither special nor out of bounds
    {
        w($p);                      // build path from there to another special
        $r[$p]=EC[$i++<$c];         // place this special
        w($p);      // additional path to allow special in the middle of a dead end tunnel
    }

// insert linebreaks and print
echo chunk_split($r,$w);

```
> 5 votes

# Answer
# C# (Visual C# Interactive Compiler), 730 bytes

```
var R=new Random();for(;;){char P='P',C='C',E='E',Q='#';int w=R.Next(8,37),h=R.Next(8,37),H=h,t,g=99,W,i,j,r;string l,s,p=new string(Q,w+2);var m=new List<string>();for(;H>0;H--){l="";for(W=w;W>0;W--){r=R.Next(999);l+=r<3?C:r<6?E:r<g?Q:' ';}m.Add(l);}m[0]=m[0].Substring(0,w-1)+'F';m[h-1]=P+m[h-1].Substring(1);s=String.Join("#\n#",m);t=s.Split(E).Length-1;if(t<1||t>3)continue;t=s.Split(C).Length-1;if(t<2||t>4)continue;while(g>0){g--;for(i=0;i<h;i++)for(j=0;j<w;j++)if(m[i][j]!=Q&&m[i][j]!=P&&(i>0&&m[i-1][j]==P)||(i<h-1&&m[i+1][j]==P)||(j>0&&m[i][j-1]==P)||(j<w-1&&m[i][j+1]==P))m[i]=m[i].Substring(0,j)+P+m[i].Substring(j+1,w-j-1);}if(String.Join("",m).Split(E,C,'F').Length>1)continue;Console.Write(p+"\n#"+s+"#\n"+p);break;}

```

Try it online!

Ungolfed:

```
var R = new Random();
for (;;)
{
    char P = 'P', C = 'C', E = 'E', poundSymbol = '#';
    int width = R.Next(8, 37), height = R.Next(8, 37), HeightTemp = height, testVariable, goThroughLoop = 99, WidthTemp, i, j, rand;
    string line, strMap, poundSymbolPadding = new string(poundSymbol, width + 2);

    var map = new List<string>(); //initialize map
    for (; HeightTemp > 0; HeightTemp--)
    {
        line = "";
        for (WidthTemp = width; WidthTemp > 0; WidthTemp--)
        {
            rand = R.Next(999);
            //add a character randomly.  Re-use the goThroughLoop variable here, which gives approx. 1 wall per 10 spaces.
            line += rand < 3 ? C : rand < 6 ? E : rand < goThroughLoop ? poundSymbol : ' ';
        }
        map.Add(line);
    }
    //add finish and player
    map[0] = map[0].Substring(0, width - 1) + 'F';
    map[height - 1] = P + map[height - 1].Substring(1);

    strMap = String.Join("#\n#", map);
    //check proper # of enemies, regenerate if invalid
    testVariable = strMap.Split(E).Length - 1;
    if (testVariable < 1 || testVariable > 3)
        continue;
    //check proper # of coins, regenerate if invalid
    testVariable = strMap.Split(C).Length - 1;
    if (testVariable < 2 || testVariable > 4)
        continue;
    //map out areas Player can access.  Iterates until all accessible places have been marked as such.
    while (goThroughLoop > 0)
    {
        goThroughLoop--;
        for (i = 0; i < height; i++)
            for (j = 0; j < width; j++)
                if (map[i][j] != poundSymbol && map[i][j] != P && ((i > 0 && map[i - 1][j] == P) || (i < height - 1 && map[i + 1][j] == P) || (j > 0 && map[i][j - 1] == P) || (j < width - 1 && map[i][j + 1] == P)))
                    //mark this space as accessible
                    map[i] = map[i].Substring(0, j) + P + map[i].Substring(j + 1, width - j - 1);
    }
    //if player cannot access all features (defeated enmies, collected coins, arrived at finish), regenerate map.
    if (String.Join("", map).Split(E, C, 'F').Length > 1)
        continue;

    //output our final map
    Console.Write(poundSymbolPadding + "\n#" + strMap + "#\n" + poundSymbolPadding);

    break;
}

```

Edit: saved 8 bytes, made it slightly less efficient by locking the player accessible test loop to 99 iterations. I know it'll never really compete with the other answers here, but I'm having fun!
> 3 votes

---
Tags: code-golf, ascii-art, path-finding, maze
---


title: Partition a map of water flows

text:
# Question
Title: Partition a map of water flows
This is a challenge on the internet asked by Palantir Technologies in their interviews.

> A group of farmers has some elevation data, and we’re going to help them understand how rainfall flows over their farmland. We’ll represent the land as a two-dimensional array of altitudes and use the following model, based on the idea that water flows downhill:
>
> If a cell’s four neighboring cells all have higher altitudes, we call this cell a sink; water collects in sinks. Otherwise, water will flow to the neighboring cell with the lowest altitude. If a cell is not a sink, you may assume it has a unique lowest neighbor and that this neighbor will be lower than the cell.
>
> Cells that drain into the same sink – directly or indirectly – are said to be part of the same basin.
>
> Your challenge is to partition the map into basins. In particular, given a map of elevations, your code should partition the map into basins and output the sizes of the basins, in descending order.
>
> Assume the elevation maps are square. Input will begin with a line with one integer, S, the height (and width) of the map. The next S lines will each contain a row of the map, each with S integers – the elevations of the S cells in the row. Some farmers have small land plots such as the examples below, while some have larger plots. However, in no case will a farmer have a plot of land larger than S = 5000.
>
> Your code should output a space-separated list of the basin sizes, in descending order. (Trailing spaces are ignored.)
>
> A few examples are below.
>
> Input:

```
3
1 5 2
2 4 7
3 6 9

```

> Output: `7 2`
>
> The basins, labeled with A’s and B’s, are:

```
A A B
A A B
A A A

```

> Input:

```
1
10

```

> Output: `1`
>
> There is only one basin in this case.
>
> Input:

```
5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4 2
3 3 5 2 1

```

> Output: `11 7 7`
>
> The basins, labeled with A’s, B’s, and C’s, are:

```
A A A A A
A A A A A
B B A C C
B B B C C
B B C C C

```

> Input:

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

```

> Output: `7 5 4`
>
> The basins, labeled with A’s, B’s, and C’s, are:

```
A A B B
A B B B
A B B C
A C C C

```

# Answer
> 8 votes
**Mathematica**

The basin size list can be gotten by

```
WatershedComponents[
 Image[Rest@ImportString[m,"Table"]] // ImageAdjust,
 CornerNeighbors -> False,
 Method -> "Basins"
 ] // Reverse@Sort@Part[Tally[Flatten@#], All, 2] &

```

where `m` is the given input data. To display a matrix like the ones in the question one can replace `// Reverse@Sort@Part[Tally[Flatten@#], All, 2] &` with `/. {1 -> "A", 2 -> "B", 3 -> "C"} // MatrixForm` or one can display it as an image instead using `//ImageAdjust//Image`.

# Answer
> 2 votes
### JavaScript - 673 ~~707 ~~730~~ 751~~

`e=[],g=[],h=[],m=[],q=[];function r(){a=s,b=t;function d(d,A){n=a+d,p=b+A;c>e[n][p]&&(u=!1,v>e[n][p]&&(v=e[n][p],w=n,k=p))}c=e[a][b],u=!0,v=c,w=a,k=b;0!=a&&d(-1,0);a!=l&&d(1,0);0!=b&&d(0,-1);b!=l&&d(0,1);g[a][b]=w;h[a][b]=k;return u}function x(a,b,d){function c(a,b,c,k){g[a+b][c+k]==a&&h[a+b][c+k]==c&&(d=x(a+b,c+k,d))}d++;0!=a&&c(a,-1,b,0);a!=l&&c(a,1,b,0);0!=b&&c(a,0,b,-1);b!=l&&c(a,0,b,1);return d}y=$EXEC('cat "'+$ARG[0]+'"').split("\n");l=y[0]-1;for(z=-1;z++<l;)e[z]=y[z+1].split(" "),g[z]=[],h[z]=[];for(s=-1;s++<l;)for(t=-1;t++<l;)r()&&m.push([s,t]);for(z=m.length-1;0<=z;--z)s=m[z][0],t=m[z][1],q.push(x(s,t,0));print(q.sort(function(a,b){return b-a}).join(" "));`

Test results (using Nashorn):

```
$ for i in A B C D; do jjs -scripting minlm.js -- "test$i"; done
7 2
1
11 7 7
7 5 4
$

```

There would probably be stack problems for maps of size 5000 (but that's an implementation detail :).
The unminified source in all it's fugliness:

```
// lm.js - find the local minima

//  Globalization of variables.

/*
    The map is a 2 dimensional array. Indices for the elements map as:

    [0,0] ... [0,n]
    ...
    [n,0] ... [n,n]

Each element of the array is a structure. The structure for each element is:

Item    Purpose         Range       Comment
----    -------         -----       -------
h   Height of cell      integers
s   Is it a sink?       boolean
x   X of downhill cell  (0..maxIndex)   if s is true, x&y point to self
y   Y of downhill cell  (0..maxIndex)

Debugging only:
b   Basin name      ('A'..'A'+# of basins)

Use a separate array-of-arrays for each structure item. The index range is
0..maxIndex.
*/
var height = [];
var sink = [];
var downhillX = [];
var downhillY = [];
//var basin = [];
var maxIndex;

//  A list of sinks in the map. Each element is an array of [ x, y ], where
// both x & y are in the range 0..maxIndex.
var basinList = [];

//  An unordered list of basin sizes.
var basinSize = [];

//  Functions.

function isSink(x,y) {
    var myHeight = height[x][y];
    var imaSink = true;
    var bestDownhillHeight = myHeight;
    var bestDownhillX = x;
    var bestDownhillY = y;

    /*
        Visit the neighbors. If this cell is the lowest, then it's the
    sink. If not, find the steepest downhill direction.

        This would be the place to test the assumption that "If a cell
    is not a sink, you may assume it has a unique lowest neighbor and
    that this neighbor will be lower than the cell." But right now, we'll
    take that on faith.
    */
    function visit(deltaX,deltaY) {
        var neighborX = x+deltaX;
        var neighborY = y+deltaY;
        if (myHeight > height[neighborX][neighborY]) {
            imaSink = false;
            if (bestDownhillHeight > height[neighborX][neighborY]) {
                bestDownhillHeight = height[neighborX][neighborY];
                bestDownhillX = neighborX;
                bestDownhillY = neighborY;
            }
        }
    }
    if (x !== 0) {
        // upwards neighbor exists
        visit(-1,0);
    }
    if (x !== maxIndex) {
        // downwards neighbor exists
    visit(1,0);
    }
    if (y !== 0) {
        // left-hand neighbor exists
        visit(0,-1);
    }
    if (y !== maxIndex) {
        // right-hand neighbor exists
        visit(0,1);
    }

    downhillX[x][y] = bestDownhillX;
    downhillY[x][y] = bestDownhillY;
    return imaSink;
}

function exploreBasin(x,y,currentSize) {//,basinName) {
    //  This cell is in the basin.
    //basin[x][y] = basinName;
    currentSize++;

    /*
        Visit all neighbors that have this cell as the best downhill
    path and add them to the basin.
    */
    function visit(x,deltaX,y,deltaY) {
        if ((downhillX[x+deltaX][y+deltaY] === x) && (downhillY[x+deltaX][y+deltaY] === y)) {
            currentSize = exploreBasin(x+deltaX,y+deltaY,currentSize); //,basinName);
        }
        return 0;
    }
    if (x !== 0) {
        // upwards neighbor exists
        visit(x,-1,y,0);
    }
    if (x !== maxIndex) {
        // downwards neighbor exists
        visit(x,1,y,0);
    }
    if (y !== 0) {
        // left-hand neighbor exists
        visit(x,0,y,-1);
    }
    if (y !== maxIndex) {
        // right-hand neighbor exists
        visit(x,0,y,1);
    }

    return currentSize;
}

//  Read map from file (1st argument).
var lines = $EXEC('cat "' + $ARG[0] + '"').split('\n');
maxIndex = lines.shift() - 1;
for (var i = 0; i<=maxIndex; i++) {
    height[i] = lines.shift().split(' ');
    //  Create all other 2D arrays.
    sink[i] = [];
    downhillX[i] = [];
    downhillY[i] = [];
    //basin[i] = [];
}

//  Everyone decides if they are a sink. Create list of sinks (i.e. roots).
for (var x=0; x<=maxIndex; x++) {
    for (var y=0; y<=maxIndex; y++) {
        if (sink[x][y] = isSink(x,y)) {
            //  This node is a root (AKA sink).
            basinList.push([x,y]);
        }
    }
}
//for (var i = 0; i<=maxIndex; i++) { print(sink[i]); }

//  Each root explores it's basin.
//var basinName = 'A';
for (var i=basinList.length-1; i>=0; --i) { // i-- makes Closure Compiler sad
    var x = basinList[i][0];
    var y = basinList[i][1];
    basinSize.push(exploreBasin(x,y,0)); //,basinName));
    //basinName = String.fromCharCode(basinName.charCodeAt() + 1);
}
//for (var i = 0; i<=maxIndex; i++) { print(basin[i]); }

//  Done.
print(basinSize.sort(function(a, b){return b-a}).join(' '));

```

I got better minimization results by breaking up the element objects into separate arrays, globalizing everywhere possible and embracing side-effects. NSFW.
The effects of code minimization:

* 4537 bytes, unminified
* 1180 bytes, packer
* 855 bytes, packer + hand optimizations (1 character global names)
* 751 bytes, Google Closure Compiler with ADVANCED\_OPTIMIZATIONS (NB, it elided a vestigial "return 0" as dead code)
* 730 bytes, reckless hand optimization (I'm not changing the unminified source, so NSFW)
* 707 bytes, more reckless hand optimization (remove all references to sink\[\]);
* 673 bytes, remove all "var"s, drop Nashorn -strict flag

I could have achieved close to 700 bytes without editing the minimized code if I'd been willing to modify the original source. But I didn't because I think leaving it as-is gives an interesting view from the starting point.

# Answer
> 1 votes
### Python: 276 306 365 bytes

This is my first golf attempt. Suggestions are appreciated!

*edit:* imports and closing files take too many characters! So does storing files in variables and nested list comprehension.

```
t=map(int,open('a').read().split());n=t.pop(0);q=n*n;r,b,u=range(q),[1]*q,1
while u!=0:
    u=0
    for j in r:
        d=min((t[x],x)for x in [j,j-1,j+1,j-n,j+n]if int(abs(j/n-x/n))+abs(j%n-x%n)<=1 and x in r)[1]
        if j-d:u|=b[j];b[d]+=b[j];b[j]=0
for x in sorted(b)[::-1]:print x or '',

```

**fully commented (2130 bytes...)**

```
from math import floor
with open('a') as f:
    l = f.read()
    terrain = map(int,l.split()) # read in all the numbers into an array (treating the 2D array as flattened 1D)
    n = terrain.pop(0) # pop the first value: the size of the input
    valid_indices = range(n*n) # 0..(n*n)-1 are the valid indices of this grid
    water=[1]*(n*n) # start with 1 unit of water at each grid space. it will trickle down and sum in the basins.
    updates=1 # keep track of whether each iteration included an update

    # helper functions
    def dist(i,j):
        # returns the manhattan (L1) distance between two indices
        row_dist = abs(floor(j/n) - floor(i/n))
        col_dist = abs(j % n - i % n)
        return row_dist + col_dist

    def neighbors(j):
        # returns j plus up to 4 valid neighbor indices
        possible = [j,j-1,j+1,j-n,j+n]
        # validity criteria: neighbor must be in valid_indices, and it must be one space away from j
        return [x for x in possible if dist(x,j)<=1 and x in valid_indices]

    def down(j):
        # returns j iff j is a sink, otherwise the minimum neighbor of j
        # (works by constructing tuples of (value, index) which are min'd
        # by their value, then the [1] at the end returns its index)
        return min((terrain[i],i) for i in neighbors(j))[1]

    while updates!=0: # break when there are no further updates
        updates=0 # reset the update count for this iteration
        for j in valid_indices: # for each grid space, shift its water
            d =down(j)
            if j!=d: # only do flow if j is not a sink
                updates += water[j] # count update (water[j] is zero for all non-sinks when the sinks are full!)
                water[d] += water[j] # move all of j's water into the next lowest spot
                water[j] = 0 # indicate that all water has flown out of j
    # at this point, `water` is zeros everywhere but the sinks.
    # the sinks have a value equal to the size of their watershed.
    # so, sorting `water` and printing nonzero answers gives us the result we want!
    water = sorted(water)[::-1] # [::-1] reverses the array (high to low)
    nonzero_water = [w for w in water if w] # 0 evaulates to false.
    print " ".join([str(w) for w in nonzero_water]) # format as a space-separated list

```

# Answer
> 1 votes
## Ruby, 216

```
r=[]
M=gets('').split.map &:to_i
N=M.shift
g=M.map{1}
M.sort.reverse.map{|w|t=[c=M.index(w),c%N<0?c:c-1,c%N<N-1?c+1:c,c+N,c-N].min_by{|y|M[y]&&y>=0?M[y]:M.max}
M[c]+=1
t!=c ?g[t]+=g[c]:r<<g[c]}
$><<r.sort.reverse*' '

```

It's a slightly different approach, only invoking "flow" on each square once (performance depends what the performance of Array::index is). It goes from the highest elevation to the lowest, emptying out one cell at a time into its lowest neighbor and marking the cell done (by adding 1 to the elevation) when it's done.

Commented and spaced:

```
results=[]
ELEVATIONS = gets('').split.map &:to_i  # ELEVATIONS is the input map
MAP_SIZE = ELEVATIONS.shift             # MAP_SIZE is the first line of input
watershed_size = ELEVATIONS.map{1}      # watershed_size is the size of the watershed of each cell

ELEVATIONS.sort.reverse.map { |water_level|
    # target_index is where the water flows to.  It's the minimum elevation of the (up to) 5 cells:
    target_index = [
        current_index = ELEVATIONS.index(water_level),                              # this cell
        (current_index % MAP_SIZE) < 0           ? current_index : current_index-1, # left if possible
        (current_index % MAP_SIZE) >= MAP_SIZE-1 ? current_index : current_index+1, # right if possible
        current_index + MAP_SIZE,                                                   # below
        current_index - MAP_SIZE                                                    # above
    ].min_by{ |y|
        # if y is out of range, use max. Else, use ELEVATIONS[y]
        (ELEVATIONS[y] && y>=0) ? ELEVATIONS[y] : ELEVATIONS.max
    }
# done with this cell.
# increment the elevation to mark done since it no longer matters
ELEVATIONS[current_index] += 1

# if this is not a sink
(target_index != current_index) ?
    # add my watershed size to the target's
    watershed_size[target_index] += watershed_size[current_index]
    # else, push my watershed size onto results
    : results << watershed_size[current_index]}

```

### Changelog:

216 - better way to deselect out-of-bounds indices

221 - turns out, "11" comes before "2"... revert to `to_i`, but save some space on our `gets`es.

224 - Why declare `s`, anyway? And `each` =\> `map`

229 - massive golfing - sort the elevations first into `s` (and thereby drop the `while` clause), use `min_by` instead of `sort_by{...}[0]`, don't bother `to_i` for elevations, use `flat_map`, and shrink `select{}` block

271 - moved watershed size into new array and used sort\_by

315 - moved results to array which gave all sorts of benefits, and shortened neighbor index listing. also gained one char in index lambda.

355 - first commit

# Answer
> 1 votes
## Haskell, 271 286

```
import Data.List
m=map
q[i,j]=[-1..1]>>= \d->[[i+d,j],[i,j+d]]
x%z=m(\i->snd.fst.minimum.filter((`elem`q i).snd)$zip(zip z[0..])x)x
g(n:z)=iterate(\v->m(v!!)v)(sequence[[1..n],[1..n]]%z)!!(n*n)
main=interact$unwords.m show.reverse.sort.m length.group.sort.g.m read.words

```

Might be still some code to be golf'd here.

```
& runhaskell 19188-Partition.hs <<INPUT
> 5
> 1 0 2 5 8
> 2 3 4 7 9
> 3 5 7 8 9
> 1 2 5 4 2
> 3 3 5 2 1
INPUT
11 7 7

```

**Explanation**

Basic idea: For each cell *(i,j)* find the lowest cell in the "neighborhood". This gives a graph \[*(i,j)**(mi,mj)*\]. If a cell is the lowest cell itself, then *(i,j)* == *(mi,mj)*.

This graph can be iterated: For each *a → b* in the graph, replace it with *a → c* where *b → c* is in the graph. When this iteration yields no more changes, then each cell in the graph points at the lowest cell it will flow to.

To golf this, several changes have been made: First, coordinates are represented as a list of length 2, rather than a pair. Second, once the neighbors have been found, cells are represented by their index into a linear array of the cells, not 2D coordinates. Third, as there are n\*n cells, after n\*n iterations, the graph must be stable.

**Ungolf'd**

```
type Altitude = Int     -- altitude of a cell

type Coord = Int        -- single axis coordinate: 1..n
type Coords = [Coord]   -- 2D location, a pair of Coord
    -- (Int,Int) would be much more natural, but Coords are syntehsized
    -- later using sequence, which produces lists

type Index = Int        -- cell index
type Graph = [Index]    -- for each cell, the index of a lower cell it flows to

neighborhood :: Coords -> [Coords]                              -- golf'd as q
neighborhood [i,j] = concatMap (\d -> [[i+d,j], [i,j+d]]) [-1..1]
    -- computes [i-1,j] [i,j-1] [i,j] [i+1,j] [i,j+1]
    -- [i,j] is returned twice, but that won't matter for our purposes

flowsTo :: [Coords] -> [Altitude] -> Graph                      -- golf'd as (%)
flowsTo cs vs = map lowIndex cs
  where
    lowIndex is = snd . fst                          -- take just the Index of
                  . minimum                          -- the lowest of
                  . filter (inNeighborhood is . snd) -- those with coords nearby
                  $ gv                               -- from the data

    inNeighborhood :: Coords -> Coords -> Bool
    inNeighborhood is ds = ds `elem` neighborhood is

    gv :: [((Altitude, Index), Coords)]
        -- the altitudes paired with their index and coordinates
    gv = zip (zip vs [0..]) cs

flowInput :: [Int] -> Graph                                     -- golf'd as g
flowInput (size:vs) = iterate step (flowsTo coords vs) !! (size * size)
  where
    coords = sequence [[1..size],[1..size]]
        -- generates [1,1], [1,2] ... [size,size]

    step :: Graph -> Graph
    step v = map (v!!) v
        -- follow each arc one step

main' :: IO ()
main' = interact $
            unwords . map show      -- counts a single line of text
            . reverse . sort        -- counts from hi to lo
            . map length            -- for each common group, get the count
            . group . sort          -- order cells by common final cell index
            . flowInput             -- compute the final cell index graph
            . map read . words      -- all input as a list of Int

```

# Answer
> 1 votes
# Python - 470 447 445 393 392 378 376 375 374 369 bytes

I can't stop myself!

Not a winning solution, but I had a lot of fun creating it. This version does not assume the input to be stored anywhere and instead reads it from stdin. Maximum recursion depth = longest distance from a point to it's sink.

```
def f(x,m=[],d=[],s=[]):
 n=[e[a]if b else 99for a,b in(x-1,x%z),(x+1,x%z<z-1),(x-z,x/z),(x+z,x/z<z-1)];t=min(n)
 if t<e[x]:r=f(x+(-1,1,-z,z)[n.index(t)])[0];s[r]+=x not in m;m+=[x]
 else:c=x not in d;d+=[x]*c;r=d.index(x);s+=[1]*c
 return r,s
z,e=input(),[]
exec'e+=map(int,raw_input().split());'*z
for x in range(z*z):s=f(x)[1]
print' '.join(map(str,sorted(s)[::-1]))

```

I don't have time to explain it today, but here's the ungolfed code:

It actually is quite different than the original code. I read S lines from the stdin, split, map to ints and flatten the lists to get the flattened field. Then I loop through all tiles (let me call them tiles) once. The flow-function checks the neighboring tiles and picks the one with the smallest value. If it's smaller than value of the current tile, move to it and recurse. If not, the current tile is a sink and new basin is created. The return value of the recursion is the id of the basin.

```
# --- ORIGINAL SOURCE ---

# lowest neighboring cell = unique and next
# neihboring cells all higher = sink and end

basinm = [] # list of the used tiles
basins = {} # list of basin sizes
basinf = [] # tuples of basin sinks
field = []  # 2d-list representing the elevation map
size = 0

def flow(x, y):
    global basinf, basinm
    print "Coordinate: ", x, y
    nearby = []
    nearby += [field[y][x-1] if x > 0 else 99]
    nearby += [field[y][x+1] if x < size-1 else 99]
    nearby += [field[y-1][x] if y > 0 else 99]
    nearby += [field[y+1][x] if y < size-1 else 99]
    print nearby
    next = min(nearby)
    if next < field[y][x]:
        i = nearby.index(next)
        r = flow(x+(-1,1,0,0)[i], y+(0,0,-1,1)[i])
        if (x,y) not in basinm:
            basins[r] += 1
            basinm += [(x,y)]
    else:
        c = (x,y) not in basinf
        if c:
            basinf += [(x,y)]
        r = basinf.index((x,y))
        if c: basins[r] = 1
    return r

size = input()
field = [map(int,raw_input().split()) for _ in range(size)]
print field
for y in range(size):
    for x in range(size):
        flow(x, y)
print
print ' '.join(map(str,sorted(basins.values(),reverse=1)))

```

# Answer
> 1 votes
# JavaScript (ECMAScript 6) - 226 Characters

```
s=S.split(/\s/);n=s.shift(k=[]);u=k.a;t=s.map((v,i)=>[v,i,1]);t.slice().sort(X=(a,b)=>a[0]-b[0]).reverse().map(v=>{i=v[1];p=[v,i%n?t[i-1]:u,t[i-n],(i+1)%n?t[i+1]:u,t[+n+i]].sort(X)[0];p==v?k.push(v[2]):p[2]+=v[2]});k.join(' ')

```

**Explanation**

```
s=S.split(/\s/);                  // split S into an array using whitespace as the boundary.
n=s.shift();                      // remove the grid size from s and put it into n.
k=[];                             // an empty array to hold the position of the sinks.
u=k.a;                            // An undefined variable
t=s.map((v,i)=>[v,i,1]);          // map s to an array of:
                                  // - the elevation
                                  // - the position of this grid square
                                  // - the number of grid squares which have flowed into
                                  //      this grid square (initially 1).
X=(a,b)=>a[0]-b[0];               // A comparator function for sorting.
t.slice()                         // Take a copy of t
 .sort(X)                         // Then sort it by ascending elevation
 .reverse()                       // Reverse it to be sorted in descending order
 .map(v=>{                        // For each grid square (starting with highest elevation)
   i=v[1];                        // Get the position within the grid
   p=[v,i%n?t[i-1]:u,t[i-n],(i+1)%n?t[i+1]:u,t[+n+i]]
                                  // Create an array of the grid square and 4 adjacent
                                  //   squares (or undefined if off the edge of the grid)
     .sort(X)                     // Then sort by ascending elevation
     [0];                         // Then get the square with the lowest elevation.
   p==v                           // If the current grid square has the lowest elevation
     ?k.push(v[2])                // Then add the number of grid square which have
                                  //   flowed into it to k
     :p[2]+=v[2]});               // Else flow the current grid square into its lowest
                                  //   neighbour.
k.join(' ')                       // Output the sizes of the block with  space separation.

```

# Previous Version - 286 Characters

```
s=S.split(/\s/);n=s.shift()*1;k=[];u=k[1];t=s.map((v,i)=>({v:v,p:i,o:[]}));for(i in t){t[p=[t[i],i%n?t[i-1]:u,t[i-n],(+i+1)%n?t[+i+1]:u,t[+i+n]].sort((a,b)=>(a.v-b.v))[0].p].o.push([i]);p==i&&k.push([i])}k.map(x=>{while(x[L="length"]<(x=[].concat(...x.map(y=>t[y].o)))[L]);return x[L]})

```

Assumes that the input is in a variable `S`;

**Explanation**

```
s=S.split(/\s/);                  // split S into an array using whitespace as the boundary.
n=s.shift()*1;                    // remove the grid size from s and put it into n.
k=[];                             // an empty array to hold the position of the sinks.
u=k[1];                           // Undefined
t=s.map((v,i)=>({v:v,p:i,o:[]})); // map s to an Object with attributes:
                                  // - v: the elevation
                                  // - p: the position of this grid square
                                  // - o: an array of positions of neighbours which
                                  //      flow into this grid square.
for(i in t){                      // for each grid square
  p=[t[i],i%n?t[i-1]:u,t[i-n],(+i+1)%n?t[+i+1]:u,t[+i+n]]
                                  // start with an array containing the objects
                                  //   representing that grid square and its 4 neighbours
                                  //   (or undefined for those neighbours which are
                                  //   outside the grid)
      .sort((a,b)=>(a.v-b.v))     // then sort that array in ascending order of elevation
      [0].p                       // then get the first array element (with lowest
                                  //   elevation) and get the position of that grid square.
  t[p].o.push([i]);               // Add the position of the current grid square to the
                                  //   array of neighbours which flow into the grid square
                                  //   we've just found.
  p==i&&k.push([i])               // Finally, if the two positions are identical then
                                  //   we've found a sink so add it to the array of sinks (k)
}
k.map(x=>{                        // For each sink start with an array, x, containing the
                                  //   position of the sink.
  while(x.length<(x=[].concat(...x.map(y=>t[y].o))).length);
                                  // Compare x to the concatenation of x with all the
                                  //   positions of grid squares which flow into squares
                                  //   in x and loop until it stops growing.
  return x.length                 // Then return the number of grid squares.
})

```

**Test**

```
S="3\n1 5 2\n2 4 7\n3 6 9";
s=S.split(/\s/);n=s.shift()*1;k=[];u=k[1];t=s.map((v,i)=>({v:v,p:i,o:[]}));for(i in t){t[p=[t[i],i%n?t[i-1]:u,t[i-n],(+i+1)%n?t[+i+1]:u,t[+i+n]].sort((a,b)=>(a.v-b.v))[0].p].o.push([i]);p==i&&k.push([i])}k.map(x=>{while(x[L="length"]<(x=[].concat(...x.map(y=>t[y].o)))[L]);return x[L]})

```

Outputs: `[7, 2]`

```
S="5\n1 0 2 5 8\n2 3 4 7 9\n3 5 7 8 9\n1 2 5 4 2\n3 3 5 2 1"
s=S.split(/\s/);n=s.shift()*1;k=[];u=k[1];t=s.map((v,i)=>({v:v,p:i,o:[]}));for(i in t){t[p=[t[i],i%n?t[i-1]:u,t[i-n],(+i+1)%n?t[+i+1]:u,t[+i+n]].sort((a,b)=>(a.v-b.v))[0].p].o.push([i]);p==i&&k.push([i])}k.map(x=>{while(x[L="length"]<(x=[].concat(...x.map(y=>t[y].o)))[L]);return x[L]})

```

Outputs: `[11, 7, 7]`

```
S="4\n0 2 1 3\n2 1 0 4\n3 3 3 3\n5 5 2 1"
s=S.split(/\s/);n=s.shift()*1;k=[];u=k[1];t=s.map((v,i)=>({v:v,p:i,o:[]}));for(i in t){t[p=[t[i],i%n?t[i-1]:u,t[i-n],(+i+1)%n?t[+i+1]:u,t[+i+n]].sort((a,b)=>(a.v-b.v))[0].p].o.push([i]);p==i&&k.push([i])}k.map(x=>{while(x[L="length"]<(x=[].concat(...x.map(y=>t[y].o)))[L]);return x[L]})

```

Outputs: `[5, 7, 4]`

# Answer
> 1 votes
# Julia, 315

```
function f(a,i,j)
    z=size(a,1)
    n=filter((x)->0<x[1]<=z&&0<x[2]<=z,[(i+1,j),(i-1,j),(i,j-1),(i,j+1)])
    v=[a[b...] for b in n]
    all(v.>a[i,j]) && (return i,j)
    f(a,n[indmin(v)]...)
end
p(a)=prod(["$n " for n=(b=[f(a,i,j) for i=1:size(a,1),j=1:size(a,2)];sort([sum(b.==s) for s=unique(b)],rev=true))])

```

Just a recursive function that either determines the current cell is a sink or finds the drain, then call that on every set of indices. Didn't bother to do the input part since I wasn't going to win anyway, and that part isn't fun.

# Answer
> 1 votes
# JavaScript (ES6) 190 ~~203~~

**Edit** A little more ES6ish (1 year later...)

Define a function with input rows as a string, including newlines, return output as string with trailing blanks

```
F=l=>{[s,...m]=l.split(/\s+/);for(j=t=[];k=j<s*s;t[i]=-~t[i])for(i=j++;k;i+=k)k=r=0,[for(z of[-s,+s,i%s?-1:+s,(i+1)%s?1:+s])(q=m[z+i]-m[i])<r&&(k=z,r=q)];return t.sort((a,b)=>b-a).join(' ')}

// Less golfed
U=l=>{
      [s,...m] = l.split(/\s+/);
      for (j=t=[]; k=j<s*s; t[i]=-~t[i])
        for(i=j++; k; i+=k)
          k=r=0,
          [for(z of [-s,+s,i%s?-1:+s,(i+1)%s?1:+s]) (q=m[z+i]-m[i]) < r && (k=z,r=q)];
      return t.sort((a,b)=>b-a).join(' ')
    }

// TEST
out=x=>O.innerHTML += x + '\n';

out(F('5\n1 0 2 5 8\n 2 3 4 7 9\n 3 5 7 8 9\n 1 2 5 4 2\n 3 3 5 2 1'))// "11 7 7"

out(F('4\n0 2 1 3\n2 1 0 4\n3 3 3 3\n5 5 2 1')) //"7 5 4"
```

```
<pre id=O></pre>
```

# Answer
> 0 votes
## Perl 6, ~~419~~ 404

Newlines added for clarity. You can safely remove them.

```
my \d=$*IN.lines[0];my @a=$*IN.lines.map(*.trim.split(" "));my @b;my $i=0;my $j=0;
for @a {for @$_ {my $c=$_;my $p=$i;my $q=$j;my &y={@a[$p+$_[0]][$q+$_[1]]//Inf};
loop {my @n=(0,1),(1,0);push @n,(-1,0) if $p;push @n,(0,-1) if $q;my \o=@n.sort(
&y)[0];my \h=y(o);last if h>$c;$c=h;$p+=o[0];$q+=o[1]};@b[$i][$j]=($p,$q);++$j};
$j=0;++$i};say join " ",bag(@b.map(*.flat).flat.map(~*)).values.sort: {$^b <=>$^a}

```

Old solution:

```
my \d=$*IN.lines[0];my @a=$*IN.lines.map(*.trim.split(" "));my @b;my $i=0;my $j=0;
for @a {for @$_ {
my $c=$_;my $p=$i;my $q=$j;
loop {my @n=(0,1),(1,0);@n.push: (-1,0) if $p;@n.push: (0,-1) if $q;
my \o=@n.sort({@a[$p+$_[0]][$q+$_[1]]//Inf})[0];
my \h=@a[$p+o[0]][$q+o[1]];last if h>$c;
$c=h;$p+=o[0];$q+=o[1]};@b[$i][$j]=($p,$q);++$j};$j=0;++$i};
say join " ",bag(@b.map(*.flat.flat).flat.map(~*)).values.sort: {$^b <=>$^a}

```

And yet I get beaten by Python and JavaScript solutions.

---
Tags: code-golf, set-partitions
---


title: Labyrinth Polyglot

text:
# Question
Title: Labyrinth Polyglot
Create a program that can create a randomly arranged maze (The path of the maze changes each time) with exactly 1 exit and one enterance and a minimum size of 8x4 and max size of 32x32, with the exact dimensions x and y as input

Submissions can be original code, but to score higher add onto a submission with another language (polyglot)

Writing code in labyrinth gives brownie points as suggested by Mistah Figgins :)

---

Example Case (8x4):

```
__   _____
| | | __ |
|_____|  |
|  |  _| |
|____|   |

```

Non-Examples:

```
__
|_|
Too Small
__   _____
| | | __ |
|___|_|  |
|  |  _| |
|____|   |
No Solution

```

---

Apologies if challenge is confusing or cumbersome, this is my first PCG and after reading up on the meta I still had some blurry regions.

# Answer
> 1 votes
## C and C++, 603 bytes

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define Y x+1+rand()%(y/2-1)*2
#define C(n,i) if(j n&&M[i])c[b++]=i;
typedef int I;I m;I main(I argc, char**argv){srand(time(0));I x=atoi(argv[1]),y=atoi(argv[2]),*L=(I*)malloc(2*x*y*sizeof(I)),j=Y;char*M=(char*)malloc(x*y);memset(M,1,x*y);M[j]=0;for(;;){I b=0,c[4];C(%x>1,j-2)C(>2*x,j-2*x)C(%x<x-3,j+2)C(/x<y-3,j+2*x)if(b){I z=c[rand()%b];M[z]=M[z+j>>1]=0;L[m++]=j=z;}else if(m)j=L[--m];else break;}for(;;){I j=Y;if(!M[j]){M[j-x]=0;break;}}for(j=0;j<y;++j){for(m=0;m<x;++m)putchar(M[j*x+m]?88:32);puts("");}free(M);free(L);}

```

Edit: this was written before the prompt was revised. This program just outputs X for the walls and places only one door.

---
Tags: ascii-art, random, polyglot, maze, answer-chaining
---


# Question
Title: Ways of specifying random generation in challenges
> **Note**: As per consensus on Meta, questions are on topic here.

In light of this "thing to avoid when writing challenges", I started to think about challenges involving random generation of certain kinds of objects.

It sometimes happens that I want to post a challenge that involves randomly generating a foo, where

1. it's very easy to check whether a given thing is a foo, and
2. it's a little harder to quickly generate a "good-quality" random foo.

As an example, a foo might be a binary matrix where there are no segments of 4 equal bits in any direction. It's easy to check whether a given binary matrix is a foo, but generating a random foo with a nicely spread distribution seems to require a backtracking algorithm or something similar.

Anyway, now I'll need to objectively specify what qualifies as a random foo, and I'd like it to be "unpredictable" in the intuitive sense that when I run the program several times, the results always look different. The most restrictive approach is to require that the output is uniformly random: all valid foos have the same probability of being generated. This is usually too restrictive, because I have no idea how to do it save for generating all valid foos, removing duplicates and choosing one, which is boring and slow.

My next idea is to require that all valid foos have a positive probability of being generated. However, this means that the following approach is valid: generate a random foo-like thing (in our example, a random binary matrix), if it's a foo then return it, otherwise return a hard-coded foo (say, the identity matrix). This is also somewhat boring, since it's basically just a recognizer of foos tacked to a random matrix generator.

Could there be a nice general definition for an unpredictably random foo?

### TL;DR

Is there a good way for specifying an "unpredictable" randomly generated object that doesn't fix the distribution but discourages hard-coding?

# Answer
**Return a thousand different foos**

This makes it impossible to return hardcoded values and have a half decent golf. However, a legit foo generator does have a small chance of outputting duplicate foos unless it is actually checking them. To remove the burden of checking, an empirically tested failure rate, say 10%, could be specified as acceptable.

Be aware of the birthday paradox, that the probability of duplicates may be higher than you think. If there are only a million possible foos, a thousand random foos will have a probability of about 0.6 that there is a duplicate in there somewhere, and that's assuming that foo generation is completely uniform. If this could be an issue, require say 900 unique foos for every 1000 generated, which is far more generous for a genuine foo generator but still impractical for hardcoding.

This also allows you to repeatedly generate foo-like things and check fooness until you get foos. I think this is a valid solution myself, but if you don't like it:

**Do it quickly**

The chances of a completely random foo-like thing being foo are probably quite low, so specifying a time limit is likely to force a genuine attempt at foo generation.

To accomodate the speed differences between different languages, you may want to have different time limits depending on the language like Hackerrank: https://www.hackerrank.com/environment . However if you specify large enough foos the probability of random foo-like things being foo might be really low, so a "before the heat death of the Universe" rule might be sufficient.
> 5 votes

# Answer
I don't claim to have the ultimate solution to the problem (or that this list is exhaustive), but I want to outline some possible approaches that come to mind and why they would or wouldn't work. I also won't address tangential issues like whether using the current timestamp as a source of randomness is sufficiently "unpredictable" and how to enforce certain properties of the probability distribution — I'll just focus on avoiding solutions that use hardcoding.

### Not a solution: disallow hard-coding explicitly

This is a bad idea. It's a non-observable requirement (which means you can't determine whether it's satisfied just by running the program), which is strongly discouraged on PPCG and may be outright impossible if running the program on any other platform, where submissions are verified in an automated manner. The problem with a requirement like this is that you'd have to start by finding an objective definition for "hard-coding". In general, if you try this, you're only going to make things worse.

### Make hard-coding infeasible

If you can't disallow it completely, but you don't want people to use it, then you can try to design the challenge such that hard-coding is simply not a competitive approach. This is possible if the objects that should be generated are sufficiently large and incompressible that putting one example into the code would require a lot more bytes than writing an algorithm that generates valid solutions randomly. In your specific example, that's not the case of course, because identity matrices are valid and are generally easy to generate, but for other problems, that might not be the case. If the target objects are sufficiently irregular, just require them to be of a large size, which probably won't affect the byte count of an actual algorithm but will blow up the hard-coded part.

### Parameterise the output

Often, these problems come with one or more natural parameter, like the size of the matrix in your example. If so, making that parameter an input can be sufficient to make hard-coding impossible or at least impractical. In some cases, it might be easy to hard-code one specific solution for a given parameter value that has been found manually or via extensive search, but maybe there is no simple closed form for an instance of these solution in general, so it's not possible to generate a default value for arbitrary inputs easily. Again, this is not the case for the example you mention, because the identity matrix works at any size, but an optimal solution for this related problem is usually highly irregular, so it's not possible to have default value without actively searching for valid values anyway. You can combine this with a time-limit to avoid a brute force search for a default value.

### Put *some* restriction on the probability distribution

If you're willing to give up a *completely* unrestricted probability distribution, you can put some constraints on it, that still give answerers a lot of freedom in choosing their distribution but which make hard-coding a difficult or impossible:

* The simplest constraint that comes to mind is to require the difference between minimum and maximum probability for any possible output to be below a certain threshold. A hard-coded approach will likely have almost-zero probabilities for almost all outputs and a probability close to 1 for the default value. If you require the maximum difference to be below 0.1 say, there would need to be 10 (randomly chosen) default values to make the approach an option. Similarly you could also just require a minimum probability for each possible output, e.g. 1/(2\*N\*), where *N* is the number of possible outputs.
* Alternatively, you can require that there are no (likelihood) gaps in the distribution, so that there is no interval of size *δ* (chosen by you) such that both higher and lower probabilities exist. That means there can't be any outliers in terms of likelihood, which are likely generated by a hard-coding approach.

The main issue with these approaches is that they're a lot harder to reason about, proving correctness of answers is difficult, and experimentally verifying the correctness can be impossible for large output spaces. Still, they provide a principally observable requirement for the program which can make hardcoding impossible.

These approaches may also need a time limit, because one way to increase the probability of the non-default values would be to attempt finding a random foo multiple times before falling back to the default value.
> 2 votes

---
Tags: random, generation, challenge-writing
---


title: URL-Friendly Titles

text:
# Question
Title: URL-Friendly Titles
People on this site really love to embellish their post titles...

```
Stewie's sequence: + * - / + * - /

```

However, when this title needs to be included in the page URL, it is simplified:

```
stewies-sequence

```

---

# The Challenge

Your task is to create a program or function which, given a string representing a post title, outputs/returns its "URL-Friendly" conversion.

**The algorithm is:**

* Convert to lowercase (where applicable)
* Replace every space (), period (`.`), comma(`,`) or slash (`/`) with a dash (`-`)
* Remove any non-alphanumeric characters, except dashes.
* Minify groups of adjacent dashes (`a---b -> a-b`), remove any that are leading/trailing.

Please note that this algorithm is a simplification, and may not always produce the same results as the site's real method.

---

# Rules

* You can assume that input:
    + Will not be empty.
    + Will contain at least one alphanumeric character.
    + Will only contain characters in the ASCII range 32-126 (printable)
* Full programs or functions are permitted.
* A builtin which does the exact task specification is *not* permitted.
* **This is , so the shortest solution (in bytes) wins!**

---

# Test Cases

Most posts on this site will serve as tests, but here's a handy list:

```
Loading... Forever       -> loading-forever
N(e(s(t))) a string      -> nest-a-string
"Hello, World!"          -> hello-world
URL-Friendly titles      -> url-friendly-titles

C.U.S.R.S                -> c-u-s-r-s
1+2+3+4+...+n = -1/12?   -> 1234-n-1-12
How can I use cmp(a,b)   -> how-can-i-use-cmpa-b

```

Some longer ones...

```
Export The $PATH Variable, Line-By-Line   -> export-the-path-variable-line-by-line
Do n and n^3 have the same set of digits? -> do-n-and-n3-have-the-same-set-of-digits
Quine Anagrams! (Cops' Thread)            -> quine-anagrams-cops-thread
The Golfer Adventure - Chapter 1          -> the-golfer-adventure-chapter-1
Bootloader golf: Brainf***                -> bootloader-golf-brainf

```

And some edge-case checking samples (feel free to suggest more):

```
0123   ->   0123
a a1   ->   a-a1
2-1=1  ->   2-11

```

# Answer
> 7 votes
# Retina, ~~33~~ 31 bytes

```
T`L`l
[^a-z ,-9]+

\W+
-
^-|-$

```

(The program has a trailing newline)

I'm not sure I can squeeze more out of this. This should cover everything. Came similar to Mama Fun Roll's. Another 33 bytes version using recursive regexes

Try it online!

## Explanation

```
T`L`l

```

This line is simple, it converts to lowercase by **T**ransliterating `A-Z` (`L`) to `a-z` (`l`, lowercase).

---

This stage is simple, it essentially gets rid of all unneeded characters to save ourselves a lot of trouble later on

```
[^a-z ,-9]+

```

`[^a-z ,-9]` Matches any character that is NOT:

* `a-z`: lowercase alphabet (remember entire string is lowercase because of previous item)
* : space chacacter
* `,-9` this is char code range of `,` to `9` which happens to be `,-./0123456789`, exactly the characters we need

---

Next we convert all non alphanumeric chars to dashes (which is now just  and `,./-`.

```
\W+
-

```

This won't (not) match `_` which is included in `\w` (negation of `\W`) because it was removed in the previous stage

# Answer
> 9 votes
## JavaScript (ES6), ~~90~~ ~~82~~ ~~79~~ 75 bytes

This is an attempt to do the job with a single `replace()`. This code extracts only the characters that we're interested in and ignores everything else. There's some additional logic to process the hyphens.

```
s=>(s.toLowerCase().replace(/[ a-z,-9]/g,c=>S=c<'0'?s+'-':s=s?S+c:c,s=0),s)

```

### Test cases

```
let f =

s=>(s.toLowerCase().replace(/[ a-z,-9]/g,c=>S=c<'0'?s+'-':s=s?S+c:c,s=0),s)

console.log(f(`Loading... Forever`));                         // -> loading-forever
console.log(f(`N(e(s(t))) a string`));                        // -> nest-a-string
console.log(f(`"Hello, World!"`));                            // -> hello-world
console.log(f(`URL-Friendly titles`));                        // -> url-friendly-titles
console.log(f(`C.U.S.R.S`));                                  // -> c-u-s-r-s
console.log(f(`1+2+3+4+...+n = -1/12?`));                     // -> 1234-n-1-12
console.log(f(`How can I use cmp(a,b)`));                     // -> how-can-i-use-cmpa-b
console.log(f(`Export The $PATH Variable, Line-By-Line`));    // -> export-the-path-variable-line-by-line
console.log(f(`Do n and n^3 have the same set of digits?`));  // -> do-n-and-n3-have-the-same-set-of-digits
console.log(f(`Quine Anagrams! (Cops' Thread)`));             // -> quine-anagrams-cops-thread
console.log(f(`The Golfer Adventure - Chapter 1`));           // -> the-golfer-adventure-chapter-1
console.log(f(`Bootloader golf: Brainf***`));                 // -> bootloader-golf-brainf
console.log(f(`0123`));                                       // -> 0123
console.log(f(`a a1`));                                       // -> a-a1
console.log(f(`2-1=1`));                                      // -> 2-11
console.log(f(',a^a,'));                                      // -> aa
```

# Answer
> 9 votes
# , ~~41, 40, 37~~, 36 bytes

```
VuÍ[ .,\/]/-
Í0-9a-z]
Í-«/-
Í^-ü-$

```

Try it online! or Check all test cases at once!

As usual, here this contains a bunch of unprintable and non-ASCII characters, so here is a hexdump:

```
0000000: 5675 cd5b 202e 2c5c 2f5d 2f2d 0acd 8430  Vu.[ .,\/]/-...0
0000010: 2d39 612d 7aad 5d0a cd2d ab2f 2d0a cd5e  -9a-z.]..-./-..^
0000020: 2dfc 2d24                                -.-$

```

It's challenges like these where V's "Compressed regex" system come in handy.

# Explanation

First things first, we will convert everything to lowercase. Fortunately there is a really convenient way to do this in two bytes. I wrote a tip about that here. So we do

```
V           " Visually select this whole line
 u          " Convert this whole line to lowercase

```

After that we do a bunch of compressed substitute commands. A nice overview of how V's compressed regex works can be foud here, but the basic idea is we can set the high-bit to avoid having to escape certain characters. Another convenience is that ranges (like `:%`) and flags (like `/g`) are automagically filled in. But in the end, it all translates to vim substitute commands. In fact, we could even directly translate the rest of the program to vim. That would give us this:

```
:%s/[ .,/]/-/g
:%s/[^0-9a-z\-]//g
:%s/-\+/-
:%s/^-\|-$//g

```

If you speak vim-regex, it should be more clear what the rest of the program does now. So here is the rest of the program:

```
Í               " Substitute:
 [ .,\/]        "   a space, period, comma or forward slash. (Due to a strange bug, this needs to be escaped)
        /-      "   with a dash
Í               " Remove:
 [^0-9a-z]     "   Any character that is not a dash or alpha-numeric
Í               " Substitute:
 -«             "   One or more dashes
   /-           "   with one dash
Í               " Remove:
 ^-             "   A dash at the beginning of a line
   ü            "   OR
    -$          "   a dash at the end of a line

```

# Answer
> 8 votes
# JavaScript (ES6) 91 ~~96~~

*1 bytes saved* thx @ETHproductions

```
s=>s.toLowerCase().replace(/([ .,/-])|\W|_/g,(c,d)=>d?'-':'').replace(/^-*|-*$|-(?=-)/g,'')

```

**Test**

```
F=
s=>s.toLowerCase().replace(/([ .,/-])|\W|_/g,(c,d)=>d?'-':'').replace(/^-*|-*$|-(?=-)/g,'')

;[['Loading... Forever.....', 'loading-forever'],
['N(e(s(t))) a string', 'nest-a-string'],
['"Hello, World!"', 'hello-world'],
['URL-Friendly titles', 'url-friendly-titles'],
['C.U.S.R.S','c-u-s-r-s'],
['1+2+3+4+...+n = -1/12?', '1234-n-1-12'],
['How can I use cmp(a,b)', 'how-can-i-use-cmpa-b'],
['Export The $PATH Variable, Line-By-Line', 'export-the-path-variable-line-by-line'],
['Do n and n^3 have the same set of digits?', 'do-n-and-n3-have-the-same-set-of-digits'],
['Quine Anagrams! (Cops\' Thread)', 'quine-anagrams-cops-thread'],
['The Golfer Adventure - Chapter 1', 'the-golfer-adventure-chapter-1'],
['Bootloader golf: Brainf***', 'bootloader-golf-brainf'],
['0123', '0123'],
['a a1', 'a-a1'],
['2-1=1', '2-11']]
.forEach(t=>{
  var i=t[0],k=t[1],r=F(i)
  console.log(r==k?'OK':'KO',i+' -> '+r,r==k?'':k)
})
```

# Answer
> 4 votes
# Python 3, ~~103~~ ~~100~~ ~~96~~ 95 bytes

*5 bytes saved thanks to Flp.Tkc*

```
import re
lambda s,y=re.sub,d='-':y('-+',d,y('[^0-9a-z-]','',y('[ .,/]',d,s.lower()))).strip(d)

```

# Answer
> 4 votes
# Retina, 34 bytes

```
T`L`l
[^a-z\d .,/-]+

\W+
-
^-|-$

```

Try it online!

Note the trailing newline. Essentially the OP's implementation.

# Answer
> 3 votes
# MATL, 38 bytes

```
'-'jyvk45y' .,/'m(t8Y245hm)'-*'45YX6L)

```

Try it online! Or verify all test cases.

### Explanation

```
'-'jyv       % Take input line. Append and prepend a dash. Gives a char column vector
k            % Convert to lowercase
45y' .,/'m(  % Replace any of ' .,/' by a dash, using assignment indexing
t8Y245hm)    % Keep only alphanumeric chars or dashes, using reference indexing
'-*'45YX     % Replace each run of dashes by a single dash, using a regular expression
6L)          % Remove first and last chars, which are always dashes. Implicitly display

```

# Answer
> 3 votes
## JavaScript (ES6), ~~74~~ 69 bytes

```
f=
s=>s.toLowerCase().replace(/[^-/,. a-z\d]/g,``).match(/\w+/g).join`-`
```

```
<input oninput=o.textContent=/[a-z\d]/i.test(this.value)?f(this.value):``><pre id=o>
```

Edit: Saved 5 bytes by realising that I had already deleted all characters except `-/,. 0-9a-z` so I can use `\w` to match the remaining words.

# Answer
> 3 votes
# Ruby, ~~61~~ ~~60~~ ~~61~~ ~~64~~ 53 bytes

(52 bytes of code plus one byte for the `-p`)

```
$_=$_.tr("A-Z ,-/","a-z ").gsub(/[^\w ]/){}.split*?-

```

Try it online!

> **`tr(`****`)`** – convert upper case characters, space, comma, period, and slash. Temporarily substitute the `-` with whitespace so I can use `strip` later on.
> Note the `-` character in the `"A-Z ,-/"` expression is actually a range operator, which also makes the `.` character subject to transformation. This maneuver won’t actually shave off bytes but it’s fancy so it gets to stay.
>
> **`gsub(/[^\w ]/){}`** – remove all characters not in the allowed set.
>
> **`split`** – technically, we don’t exactly need that array but `split` eliminates leading and trailing whitespace (which is actually `-` characters in disguise). As a bonus, this squeezes together runs of multiple spaces.
>
> **`*?-`** – Shorthand for `.join("-")`; this reverses both the preceding `split` operation *and* the whitespace transformation at the same time. One more byte is saved by using the abbreviated notation for character literals, which makes the program require Ruby 1.9 or newer.

**Update 1:** ~~Using `gets` instead of Ruby’s stream editing mode saves one byte.~~
Reverted as per ValueInk’s suggestion.

**Update 2:** **(+3 bytes overall)**

* Fixed edge case `..--hi, $/` (→ `hi`) **(+10 bytes)** – once again courtesy of user ValueInk
* Took malus for `-p` **(+1 byte)**
* Got rid of `squeeze` and used `gsub` instead **(+2 bytes)**, which allowed me to:
* Use `strip` to handle the leading and trailing dashes **(-10 bytes)**.

**Update 3:** Hattrick by ValueInk. We save 11 bytes by leveraging `String#split`’s habit of auto-squeezing runs of the same separator, which enables us to ditch the whole final `strip`/`gsub` chain and replace it by a `split`/`join` combo. **(-11 bytes)**

# Answer
> 2 votes
# JavaScript, ~~90~~ ~~98~~ ~~94~~ ~~93~~ ~~91~~ ~~90~~ 91 bytes

*1 byte saved thanks to @edc65!*

*1 byte saved thanks to @IsmaelMiguel for spotting a leading semi-colon!*

*1 byte gained after failing for* `,a-^-a,`

```
f=s=>s.toLowerCase().replace(/[^ a-z,-9]/g,"").replace(/[ ,-/]+/g,"-").replace(/^-|-$/g,"")

```

The thing I like most about this particular submission are the ranges. In the first `replace`, we remove anything that is not alphanumeric and not a `,`,`-`,`.`,`/` and not a space. We use `a-z` for detecting the letters, and we use `,-9` to detect those special characters *and* numbers since the character codes of these ASCII literals all line up!

```
, = 44
- = 45
. = 46
/ = 47
0 = 48
...
9 = 57

```

```
f=s=>s.toLowerCase().replace(/[^ a-z,-9]/g,"").replace(/[ ,-/]+/g,"-").replace(/^-|-$/g,"")

console.log(f("---"));//TEST
console.log(f("!@#$%ˆ&*()_+"));//TEST

console.log(f("Stewie's sequence: + * - / + * - /-"));

console.log(f("Loading... Forever"));
console.log(f("N(e(s(t))) a string"));
console.log(f("\"Hello, World!\""));
console.log(f("URL-Friendly titles"));

console.log(f("C.U.S.R.S"));
console.log(f("1+2+3+4+...+n = -1/12?"));
console.log(f("How can I use cmp(a,b)"));

console.log(f("Export The $PATH Variable, Line-By-Line"));
console.log(f("Do n and n^3 have the same set of digits?"));
console.log(f("Quine Anagrams! (Cops' Thread)"));
console.log(f("The Golfer Adventure - Chapter 1"));
console.log(f("Bootloader golf: Brainf***--"));

console.log(f("0123"));
console.log(f("a a1"));
console.log(f("2-1=1"));
```

```
<input oninput=a.textContent=f(this.value)><pre id=a>
```

# Answer
> 2 votes
# PHP, 87 bytes

The idea of the regular expressions come from existing answers.

```
<?=trim(preg_replace(['@[^ a-z,-9]@','@[ ,-/]+@'],['','-'],strtolower($_GET[T])),'-');

```

It requires you to have a server running PHP, and access over HTTP.

The title must be on the key `T`, and the result will be printed on the screen.

Example: `http://localhost/title.php?T=<my shiny title>`

# Answer
> 2 votes
# bash/Unix tools, 56 bytes

```
tr A-Z\ .,/ a-z-|tr -cds a-z0-9- -|sed s/^-//|sed s/-$//

```

Replace upper-case with lower-case letters, and the required special characters with dashes.

Delete (-d option to tr) characters other than letters, digits, and dashes, and then squeeze (-s option to tr) multiple dashes in a row into a single dash.

Delete dashes at the beginning, and then at the end.

# Answer
> 2 votes
## Powershell, 85 Bytes

```
($args[0].ToLower()-replace'[ .,/]','-'-replace'[^a-z,-9]'-replace'-+','-').Trim('-')

```

make it lowercase, then 3 regex replaces in a row, and trim any trailing `-`'s

# Answer
> 1 votes
# Lua, 91 bytes

```
a=a:lower():gsub( '[ .,/]', '-' ):gsub( '[^%w-]', '' ):gsub( '%-+', '-' ):match'%-?(.*)%-?'

```

Where `a` is the URL string.

Explanation:

* Most of it's pretty straight forward. `a:lower()` returns the lower-case function
* `:gsub` finds the match of the pattern and replaces it with the string.
* `'[ .,/]'`: Brackets mean "or", so this matches space, period, comma, and slash. No need to be greedy because `:gsub` does all occurrences.
* `'[^%w-]'`: `^` means "not" when inside brackets, `%w` means anything alphanumeric. So `'[^%w-]` matches anything that's *not* alphanumeric or a dash.
* `'%-+'`: Match as many dashes as you can and replace them with just one dash.
* `match'%-?(.*)%-?'`: In Lua, if a string is the function's only argument, no parenthesis are needed. Only needs to check for one dash at the start and end because dashes have been minimized already. No need for anchor characters because `.*` is match everything, greedy.

# Answer
> 1 votes
# C, 194 bytes

```
i,j;f(char*s,char*d){if(*s>47&*s<58|*s>96&*s<123)d[i++]=*s;if(*s>64&*s<91)d[i++]=*s+32;if(i-j&&*s>43&*s<48|*s==32&&*(s+1)&&*(s+1)>47|(*(s+1)<44&&*(s+1)^32)){d[i++]=45;j=i;}*++s?f(s,d):(d[i]=0);}

```

Call with:

```
int main()
{
    char *in="Loading... Forever";
    char out[128];
    f(in,out);
    puts(out);
}

```

# Answer
> 1 votes
## SAS, 108

One of the less competitive answers here due to the verbose syntax of SAS - the 9 character penalty per regex really hurts - but it was a good regex learning exercise:

```
t=prxchange('s/^-|-$//',-1,prxchange('s/-+/-/',-1,compress(translate(lowcase(t),'----',' .,/'),'-','adk')));

```

# Answer
> 1 votes
## Pyth, 35 bytes

```
:r::rQ0"[-.,/]"d"[^\w ]"k6"[ -]+"\-

```

### Explanation

```
    rQ0                              Convert letters to lower case
   :   "[-.,/]"d                     Replace all -.,/ with spaces
  :             "[^\w ]"k            Remove all remaining symbols
 r                       6           Remove leading and trailing spaces
:                         "[ -]+"\-  Turn runs of spaces and dashes to one dash

```

# Answer
> 1 votes
## Perl 6, 75

```
{lc .subst(/<[\ .,/]>/,"-"):g.subst(/<[\W]-[\-]>/,""):g.subst(/\-+/,"-"):g}

```

# Answer
> 0 votes
## GNU Sed, 65 bytes

```
s/.*/\L\0/
s@[ .,/]@-@g
s/[^-a-z0-9]//g
s/-\+/-/g
s/^-\|-$//g

```

A series of regex substitutions. Uses non-portable `\L` from GNU sed to lowercase the input. Run from a file using `sed -f`.

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


title: Roll cake phrases

text:
# Question
Title: Roll cake phrases
Roll cakes are delicious sweets made with a layer of sponge cake, a layer of cream (or icecream), rolled as a spiral, see Wikipedia.

Your task is to get a non-empty phrase string from standard input, strip the spaces out, and roll it as a roll cake starting from the center in right to left in a counterclockwise direction, while the spaces starts at the bottom of the first phrase character, from the center left to right, as in the following example.

Please note that the phrase will be the layer of sponge cake and the cream layer will be represented as empty spaces.

```
Input: Lorem ipsum dolor sit amet, consectetu adipiscing elit, sed do eiusmod

Output with spaces ' ' represented as _

ilegnicsip
t________i
,_srolod_d
s_i____m_a
e_t_oL_u_u
d_a_r__s_t
d_m_emip_e
o_e______t
e_t,consec
i____
usmod

```

**Test cases**

```
Input: Lorem ipsum dolor sit amet, consectetu adipiscing elit, sed do eiusmod

Output:

ilegnicsip
t        i
, srolod d
s i    m a
e t oL u u
d a r  s t
d m emip e
o e      t
e t,consec
i
usmod

Input: Sandbox for Proposed Challenges

Output:

soporp
e    r
d aS o
c n  f
h dbox
a
llenges

Input: Cake

Output:

aC
k
e

Input: it

Output:

ti

```

**Rules:**

# Answer
> 2 votes
## Python 2, ~~202~~ 200 bytes

<sup>-2 bytes thanks to LevitatingLion</sup>

```
c=[];s=n=0
a=input().replace(' ','')
#Calculate the ammount of rotations
l=len(a)
while s<l:s=n*(1+n)/2;n+=1
#Add trailing spaces to not break the rolling
a+=' '*(s-l)
#Add a cream layer on top and a cake layer on bottom of the cake and roll 90 degrees
for i in range(1,n):c=[' '*i]+zip(*c[::-1])+[a[:i]];a=a[i:]
#Finish the rolling to match the pattern
exec~i%4*'c=zip(*c[::-1]);'
#Serve the cake
for i in c:print''.join(i)

```

# Answer
> 2 votes
# Befunge, ~~260~~ 250 bytes

```
"'"::00p09p19p35*::10p29pv
 v`*84:~<0p041p031p020p93<
v_0`!#v_^*!p04+g04:p03%4+g03:p02%4+g02:!%g04:+1pp01+%2-1g03p\3+<
>00g:: :09g\`8+0\p::19g`8+1\p20g1-2%+00p10g:::29g\`8+2\p::39g`8^
9g\-\v>29g:39g\->\:50p09g:1
$$1+\:!#@_1-55+,^>
,gg05<:+1\-1_:$#\^#

```

Try it online!

The basic idea is that we build up the spiral in the lower half of the playfield, keeping tracking of the min and max coordinates as we go along. Once all the input has been processed, we iterate over the range of coordinates and write out the content that was saved.

**Detailed Explanation**

Note that the *dx* and *dy* values are in the range 0 to 3, corresponding to the relative offsets -1, 0, 1, 0. Updating the direction is thus done by adding 1, modulo 4. Converting to a relative offset is done by subtracting 1, modulo 2.

```
"'"::00p09p19p      Set x, minx, and maxx to 39.
35*::10p29p39p      Set y, miny, and maxy to 15.
020p130p            Set dx to 0 (relative offset -1) and dy to 1 (relative offset 0).
140p                Set the segment length to 1.
0                   Set the index to 0 (on the stack).

                    -- The main input loop start here --
~                   Read a character from stdin.
:48*`_              If it's greater than 32 (i.e. not whitespace or EOL)...
  00g:              Get the current value of x and make a duplicate.
  ::09g\`8+0\p      If it's less than minx, update minx.
  ::19g`8+1\p       If it's greater than maxx, update maxx.
  20g1-2%           Calculate (dx-1)%2, which converts dx into the range -1 to 1.
  +00p              Add that to x and save (leaving the original x on the stack).
  10g:              Get the currrent value of y and make a duplicate.
  ::29g\`8+2\p      If it's less than miny, update miny.
  ::39g`8+3\p       If it's greater than maxy, update maxy.
  30g1-2%           Calculate (dy-1)%2, which converts dy into the range -1 to 1.
  +10p              Add that to y and save (leaving the original y on the stack).
  p                 Store the character we read at the original x,y coordinates.
  1+                Increment the index by 1.
  :40g%!            Mod that with the current segment len; if zero it's time to turn.
  :20g+4%20p        Add the turn condition to the dx value, thus turning if needed.
  :30g+4%30p        Similarly add the turn condition to the dy value.
  :40g+40p          Also add it to the segment length, so it gets longer every turn.
  !*                Multiply the index by !turn, so it's reset to zero on every turn.
  ^                 Repeat the loop, reading another character.
0`!#v_^             If the char <= 32, we test for EOF and repeat the loop if not.

>                   If it is EOF, we start the output routine.
29g                 Initialise the y coordinate with miny.
:39g\-              Calculate maxy - miny to use as the height countdown.

                    -- The outer output loop starts here --
\:50p               Swap y to the top and save in a temporary variable.
09g                 Initialise the x coordinate with minx.
:19g\-              Calculate maxx - miny to use as our width countdown.
\                   Swap x to the top of the stack.

                    -- The inner output loop starts here --
  :50g              Take a copy of x and the y save in the temporary variable.
  g,                Read the character at those coordinate and write to stdout.
  \:_               Swap the width countdown to the top of the stack and break if zero.
  1-                Otherwise decrement the width countdown.
  \1+               Swap the x value back to the top and increment it.
  <                 Repeat the inner loop.

$$                  Clear the width countdown and x value from the stack.
1+                  Increment the y value.
\                   Swap the height countdown to the top of the stack.
:¬#@_               If it's zero, exit.
1-                  Otherwise decrement it.
55+,                Output a line break.
^                   Repeat the outer loop.

```

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