title: Make me a fence!

text:
# Question
Title: Make me a fence!
## Challenge

This is a simple challenge. Given **two positive integers** `w` and `h` create an ASCII fence with a width of `w` and a height of `h`. The fence should be constructed using the following rules:

* The `+` character will represent a post.
* The `-` character will be used to represent the width of the fence.
* The `|` will be used to represent the height of the fence.
* After *exactly* three `-` characters have been outputted, a `+` character *must* be outputted afterward. Excluding the four corners, any other time you output a `+` would be invalid. You are allowed to follow this rule starting either from the left or the right (see examples), but you must be consistent.
* After *exactly* two `|` characters have been outputted, a `+` character *must* be outputted afterward. Excluding the four corners, any other time you output a `+` would be invalid. You are allowed to follow this rule starting either from the top or bottom (see examples), but you must be consistent.
* Each fence will have exactly four corners, and each corner will be represented with a `+`.

In other words: At every three `-` characters, you must output a `+`. And at every two `|` characters, you must output a `+`.

You can assume that the fence will **always** be a rectangle, and that both `w` and `h` will never be greater than `100` or less than `1`. Trailing and/or preceding whitespace is allowed.

## Examples/Test Cases

```
w = 1
h = 1

+-+
| |
+-+

w = 3
h = 2

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

w = 5
h = 7

+---+--+ or +--+---+
|      |    |      |
|      |    +      +
+      +    |      |
|      |    |      |
|      |    +      +
+      +    |      |
|      |    |      |
|      |    +      +
+      +    |      |
|      |    |      |
+---+--+    +--+---+

w = 10
h = 5

+---+---+---+-+  or +-+---+---+---+
|             |     |             |
|             |     +             +
+             +     |             |
|             |     |             |
|             |     +             +
+             +     |             |
|             |     |             |
+---+---+---+-+     +-+---+---+---+

w = 4
h = 4

+---+-+ or +-+---+
|     |    |     |
|     |    |     |
+     +    +     +
|     |    |     |
|     |    |     |
+---+-+    +-+---+

```

## Rules

# Answer
> 9 votes
# C, 131 bytes

```
#define L for(i=0,j=w;j;)putchar(i++%4?--j,45:43);puts("+")
f(w,h,i,j,c){L;for(j=1;h;printf("%c%*c\n",c,i,c))c=j++%3?--h,124:43;L;}

```

Try it online!

**Explanation:**

```
// The first and the last line are always similar, so let's use a macro
// to avoid code duplication.
#define L

// Let's initialize 'i' and 'j'. 'i' will be used to keep track of which
// character ('+' or '-') we should print, whereas 'j' starts from the
// input width and the loop terminates when 'j' reaches zero.
for(i=0,j=w;j;)

// We post-increment 'i' and take a modulo 4 of its previous value.
// If i%4 == 0, we print '+' (ASCII 43), otherwise we decrement 'j'
// and print '-' (ASCII 45).
putchar(i++%4?--j,45:43);

// After the loop we print one more '+' and newline.
puts("+")

// The function declaration which takes the two input parameters, and
// also declares three integer variables. These three variables could
// also be declared as global variables with the same bytecount.
f(w,h,i,j,c)

// The start of the function body. We use the macro 'L' to print the
// first line along with a newline.
{L;

// This loop prints all the lines between the first and the last. 'j'
// keeps track of when we should output a '+' instead of a '|'. 'h',
// which is the input parameter for height, serves as a terminator
// for the loop as it reaches zero.
for(j=1;h;<stuff missing from here>)

// We post-increment 'j' and check if its previous value is divisible
// by three, and if it isn't, we decrement 'h' and assign 124 (ASCII
// value for '|') to 'c'. Otherwise we assign '+' (ASCII 43) to 'c'.
c=j++%3?--h,124:43;

// The following is inside the 'increment' part of the 'for' loop.
// We print the character corresponding to the value of 'c', then
// the same character again, but padded with i-1  spaces before it
// ('i' hasn't been touched since the first loop, so it still stores
// the length of the first line), then a newline.
printf("%c%*c\n",c,i,c)

// Lastly we print the first line again using the same macro 'L'.
L;}

```

# Answer
> 5 votes
# Python 3, ~~140~~ ~~137~~ ~~128~~ ~~119~~ ~~106~~ 105 bytes

```
def f(w,h):a=~-w//3-~w;b=("+---"*w)[:a]+'+';print(b,*[i+' '*~-a+i for i in"||+"*h][:h+~-h//2],b,sep='\n')

```

Try it online!

# Answer
> 5 votes
# Pip, 38 bytes

37 bytes of code, +1 for `-n` flag.

```
Ph:'-Xa<>3JW'+PsX#h-2WR:'|Xb<>2J'+^xh

```

Takes width and height as command-line arguments. Try it online!

### Explanation

```
                         a,b are cmdline args; s is space; x is empty string (implicit)
Ph:'-Xa<>3JW'+
   '-Xa                  String of hyphens of length a
       <>3               grouped into substrings of (maximum) length 3
          JW'+           Join on +, also wrapping the result in +
 h:                      Assign that string to h (mnemonic: "header")
P                        and print it (with newline)

PsX#h-2WR:'|Xb<>2J'+^xh
          '|Xb           String of pipes of length b
              <>2        grouped into substrings of (maximum) length 2
                 J'+     joined on +
                    ^x   and split on empty string (i.e. converted to list of chars)
 sX#h-2                  String of len(h)-2 spaces
       WR:               Wrap the spaces with the list of chars
                         Note 1: WR operates itemwise on lists, so the result is a list,
                          each item of which consists of the spaces wrapped in an item
                          from the list of chars
                         Note 2: the : compute-and-assign meta-operator is here abused
                          to give WR: lower precedence than J and ^ and avoid parentheses
P                        Print that list, newline-separated (-n flag)
                      h  Autoprint the header a second time as the footer

```

# Answer
> 4 votes
# Charcoal, ~~47~~ ~~45~~ 40 bytes

```
Ｆ⁴«¿﹪ι³ＦＩη↓⁺×+¬﹪κ²|ＦＩθ⁺×+¬﹪κ³-Ｐ+¿⁼ι¹Ｊ⁰¦⁰

```

Explanation: Works by drawing each side's `-`s/`|`s in turn, inserting `+`s where necessary, then finishing with a `+`. After drawing the top and right sides, jumps back to the start to draw them in reverse order, effectively drawing the left and bottom sides. I don't know whether rotational symmetry is permitted, but if so, then for ~~27~~ 25 bytes:

```
Ｆ⁴«ＦＩ⎇﹪ι²ηθ⁺×+¬﹪κ⁻³﹪ι²-⟲Ｔ

```

Takes the above idea to the extreme by drawing the top side, rotating left, drawing the right side, rotating again, and then repeating to draw the bottom and left sides in reverse.

# Answer
> 4 votes
# Mathematica, 165 bytes

```
v=Column;d[w_,y_,m_,n_]:=Table[If[Mod[i,y]==0&&i!=w,m,n],{i,w}];(a="+"<>d[#,3,"-+","-"]<>"+";b=v@d[#2,2,"|\n+","|"];v[{a,Row[{b,""<>Table[" ",#+Floor[#/3]],b}],a}])&

```

# Answer
> 4 votes
# JavaScript (ES6), ~~133~~ 132 bytes

```
w=>h=>(a="-".repeat(w).replace(/--?-?/g,"+$&")+`+`)+(`
|`.padEnd(a.length)+`|`).repeat(h).replace(/(\|( +)\|\n)\1/g,`$&+$2+
`)+`
`+a

```

Takes input in currying syntax: `f(width)(height)`.

## Test Snippet

```
f=
w=>h=>(a="-".repeat(w).replace(/--?-?/g,"+$&")+`+`)+(`
|`.padEnd(a.length)+`|`).repeat(h).replace(/(\|( +)\|\n)\1/g,`$&+$2+
`)+`
`+a
O.innerHTML=f(W.value=5)(H.value=10)
```

```
<div oninput="O.innerHTML=f(+W.value)(+H.value)">
W <input id=W type=number min=1> H <input id=H type=number min=1>
</div>
<pre id=O>
```

# Answer
> 2 votes
# Pyth, 40 bytes

```
AQj++KjJj\+c*\-G3"++"m++d*lJ;dj\+c*\|H2K

```

Test suite.

# Answer
> 2 votes
# Java (OpenJDK 8), ~~178~~ 177 bytes

```
w->h->{int i=0;String t="",m,r;for(;i<w;)t+=i++%3<1?"+-":"-";r=t+="+\n";m=t.format("|%"+(t.length()-3)+"s|\n","");for(i=0;i<h;)r+=i++%2<1&i>1?m.replace("|","+")+m:m;return r+t;}

```

Try it online!

-1 byte thanks to @KevinCruijssen

# Answer
> 1 votes
# Charcoal, 47 45 37 bytes

```
Ａ…+---÷⁺²×⁴Ｎ³αＡ…+||÷⁺¹×³Ｎ²βＰα↓βα+↖↑⮌β

```

Try it online!

* 2 bytes saved after playing with the signs in the string creation.
* 8 bytes saved thanks to Neil, who came up with a much simpler way to calculate the lengths of the fences.

A different approach from @Neil's: first I create the strings `α` and `β` containing the chars in the horizontal and vertical borders, using the `Range` operator that creates a repetition of a string until a given length is reached. Then I print them in the proper order:

* Print α without moving the cursor.
* Print β downwards.
* Print α.
* Print a "+".
* Move the cursor up and to the left.
* Print β upwards, reversed.

Link to a verbose version.

# Answer
> 0 votes
# 05AB1E, 58 bytes

```
D3/ó+DU'-×'+.ø©'|DXú«²D2/ó+.D®»'-4×D'+3ǝ.:¶¡ø'|3×D'+2ǝ.:ø»

```

Try it online!

Harder in 05AB1E than I thought.

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


title: Those Greedy Romans!

text:
# Question
Title: Those Greedy Romans!
Given a strictly positive integer, return the shortest possible Roman numeral using only the additive rule. Output must consist of zero or more of each of the characters `MDCLXVI` in that order. The number `14` must therefore give `XIIII` rather than `XIV`.

The characters' numeric values are `M`=1000, `D`=500, `C`=100, `L`=50, `X`=10, `V`=5, `I`=1.

### Examples

`3``III`

`4` → `IIII`

`9``VIIII`

`42``XXXXII`

`796``DCCLXXXXVI`

`2017``MMXVII`

`16807``MMMMMMMMMMMMMMMMDCCCVII`

# Answer
# Plain English, ~~1059~~ ~~1025~~ ~~678~~ ~~641~~ ~~451~~ 399 bytes

Saved 34 bytes by removing an error trap. Then saved 384 bytes by golfing. Then saved 190 bytes by combining the division operation with the append operation ("z") into a new operation ("p"). Then saved 52 bytes by golfing.

```
A s is a string.
To p a r remainder a s a x string a n number:
If the x is "", exit.
Divide the r by the n giving a q quotient and the r.
Fill a t s with the x's first's target given the q.
Append the t to the s.
To convert a r number to a s:
p the r the s "M" 1000.
p the r the s "D" 500.
p the r the s "C" 100.
p the r the s "L" 50.
p the r the s "X" 10.
p the r the s "V" 5.
p the r the s "I" 1.

```

Here is the ungolfed version of the final code, plus an error trap for a negative number:

```
A roman numeral is a string.

To process a remainder given a roman numeral and a letter string is a number:
  If the letter is "", exit.
  Divide the remainder by the number giving a quotient and the remainder.
  Fill a temp string with the letter's first's target given the quotient.
  Append the temp string to the roman numeral.

To convert a number to a roman numeral:
  If the number is negative, exit.
  Put the number in a remainder.
  Process the remainder given the roman numeral and "M" is 1000.
  Process the remainder given the roman numeral and "D" is  500.
  Process the remainder given the roman numeral and "C" is  100.
  Process the remainder given the roman numeral and "L" is   50.
  Process the remainder given the roman numeral and "X" is   10.
  Process the remainder given the roman numeral and "V" is    5.
  Process the remainder given the roman numeral and "I" is    1.

```
> 12 votes

# Answer
# APL (Dyalog), ~~25~~ 22 bytes

```
'MDCLXVI'/⍨(0,6⍴2 5)∘⊤

```

Try it online!
> 5 votes

# Answer
# Retina, ~~57~~ 42 bytes

Converts to unary, then greedily replaces bunches of `I`s with the higher denominations in order.

```
.*
$*I
I{5}
V
VV
X
X{5}
L
LL
C
C{5}
D
DD
M

```

**Try it online**

<sub>*Saved 15 bytes thanks to Martin*</sub>
> 5 votes

# Answer
# Python 2, 64 bytes

```
f=lambda n,d=5,r='IVXLCD':r and f(n/d,7-d,r[1:])+n%d*r[0]or'M'*n

```

Try it online!

Rather than creating the output string from the start by greedily taking the largest part, this creates it from the end. For instance, the number of `I`'s is `n%5`, then the number of `V`'s is `n/5%2`, and so on. This is mixed base conversion with successive ratios of 5 and 2 alternating.

Here's an iterative equivalent:

**Python 2, 68 bytes**

```
n=input();s='';d=5
for c in'IVXLCD':s=n%d*c+s;n/=d;d^=7
print'M'*n+s

```

Try it online!

The `M`'s need to be handled separately because any number of them could be present as there's no larger digit. So, after the other place values have been assigned, the value remaining is converted to `M`'s.

For comparison, a greedy strategy (69 bytes):

**Python 2, 69 bytes**

```
f=lambda n,d=1000,r='MDCLXVI':r and n/d*r[0]+f(n%d,d/(d%3*3-1),r[1:])

```

Try it online!

The current digit value `d` is divided by either 2 or 5 to produce the next digit. The value of `d%3` tell us which one: if `d%3==1`, divide by `2`; and if `d%3==2`, divide by 5.
> 5 votes

# Answer
## Mathematica, 81 bytes

```
Table@@@Thread@{r=Characters@"MDCLXVI",#~NumberDecompose~FromRomanNumeral@r}<>""&

```

Explicitly using the values and deriving the corresponding numerals seems to be one byte longer:

```
Table@@@Thread@{RomanNumeral[n={1000,500,100,50,10,5,1}],#~NumberDecompose~n}<>""&

```
> 4 votes

# Answer
# Excel, ~~236~~ ~~193~~ 161 bytes

~~43 bytes saved thanks to @BradC~~

At this point, the answer really belongs totally to @BradC. Another 32 bytes saved.

```
=REPT("M",A1/1E3)&REPT("D",MOD(A1,1E3)/500)&REPT("C",MOD(A1,500)/100)&REPT("L",MOD(A1,100)/50)&REPT("X",MOD(A1,50)/10)&REPT("V",MOD(A1,10)/5)&REPT("I",MOD(A1,5))

```

Formatted:

```
=REPT("M",A1/1E3)
    &REPT("D",MOD(A1,1E3)/500)
    &REPT("C",MOD(A1,500)/100)
    &REPT("L",MOD(A1,100)/50)
    &REPT("X",MOD(A1,50)/10)
    &REPT("V",MOD(A1,10)/5)
    &REPT("I",MOD(A1,5))

```
> 4 votes

# Answer
# 05AB1E, ~~29~~ ~~26~~ 25 bytes

```
¸5n3×Rvćy‰ì}"MDCLXVI"Ss×J

```

Try it online!

**Explanation**

```
¸                           # wrap input in a list
 5n                         # push 5**2
   3×                       # repeat it 3 times
     Rv                     # for each digit y in its reverse
       ć                    # extract the head of the list
                            # (div result of the previous iteration, initially input)
        y‰                  # divmod with y
          ì                 # prepend to the list
           }                # end loop
            "MDCLXVI"S      # push a list of roman numerals
                      s×    # repeat each a number of times corresponding to the result
                            # of the modulus operations
                        J   # join to string

```
> 3 votes

# Answer
# CJam, ~~35~~ 28 bytes

*-7 bytes thanks to Martin Ender*

```
q~{5md\2md\}3*]W%"MDCLXVI".*

```

Try it online!

### Explanation

```
q~         e# Read and eval input (push the input as an integer).
{          e# Open a block:
 5md\      e#  Divmod the top value by 5, and bring the quotient to the top.
 2md\      e#  Divmod that by 2, and bring the quotient to the top.
}3*        e# Run this block 3 times.
]W%        e# Wrap the stack in an array and reverse it. Now we've performed the mixed-base
           e# conversion.
"MDCLXVI"  e# Push this string.
.*         e# Element-wise repetition of each character by the numbers in the other array.
           e# Implicitly join and print.

```
> 3 votes

# Answer
# Perl 5, 66 bytes

65 bytes of code + `-p` flag.

```
$s=1e3;for$@(MDCLXVI=~/./g){$\.=$@x($_/$s);$_%=$s;$s/=--$|?2:5}}{

```

Try it online!

Without changing the byte count, `MDCLXVI=~/./g` can be replaced by `M,D,C,L,X,V,I`; and `--$|?2:5` by `$|--*3+2`.

Much longer (99 bytes), there is:

```
$_=M x($_/1e3).D x($_%1e3/500).C x($_%500/100).L x($_%100/50).X x($_%50/10).V x($_%10/5).I x($_%5)

```
> 3 votes

# Answer
# C#, 127 bytes

```
f=n=>n>999?"M"+f(n-1000):n>499?"D"+f(n-500):n>99?"C"+f(n-100):n>49?"L"+f(n-50):n>9?"X"+f(n-10):n>4?"V"+f(n-5):n>0?"I"+f(n-1):""

```

A purely hard coded ternary statement using recursion.

Full/Formatted version:

```
using System;

class P
{
    static void Main()
    {
        Func<int, string> f = null;
        f = n => n > 999 ? "M" + f(n - 1000)
                         : n > 499 ? "D" + f(n - 500)
                                   : n > 99 ? "C" + f(n - 100)
                                            : n > 49 ? "L" + f(n - 50)
                                                     : n > 9 ? "X" + f(n - 10)
                                                             : n > 4 ? "V" + f(n - 5)
                                                                     : n > 0 ? "I" + f(n - 1)
                                                                             : "";

        Console.WriteLine(f(3));
        Console.WriteLine(f(4));
        Console.WriteLine(f(42));
        Console.WriteLine(f(796));
        Console.WriteLine(f(2017));
        Console.WriteLine(f(16807));

        Console.ReadLine();
    }
}

```
> 3 votes

# Answer
# JavaScript (ES6), ~~81~~ ~~75~~ 69 Bytes

Saved 6 bytes thanks to @Neil for porting @Jörg Hülsermann's answer

Saved 6 bytes thanks to @Shaggy

```
n=>'MDCLXVI'.replace(/./g,(c,i)=>c.repeat(n/a,n%=a,a/=i%2?5:2),a=1e3)

```

**Test cases:**

```
f=
n=>'MDCLXVI'.replace(/./g,(c,i)=>c.repeat(n/a,n%=a,a/=i%2?5:2),a=1e3)

const testCases = [3, 4, 42, 796, 2017, 16807]
testCases.forEach(testCase => console.log(f(testCase)))
```
> 3 votes

# Answer
# Python 3, ~~100 97 96 94 93 91~~ 90 bytes

* saved 4+2 bytes: use of `def`; array as default parameter reduced an indentation space; unwanted variable declaration removed
* @shooqie saved 1 byte `a%=` shorthand
* saved 2 bytes: rearranged and braces in `(a//i)` got removed
* @Wondercricket saved 1 byte: move the array from default parameter to within the function which removed `[]` at the cost of one indentation space, thus saving 1 byte.

```
def f(a):
 b=1000,500,100,50,10,5,1
 for i in b:print(end=a//i*'MDCLXVI'[b.index(i)]);a%=i

```

Try it online!
> 2 votes

# Answer
# ///, 50 bytes

```
/1/I//IIIII/V//VV/X//XXXXX/L//LL/C//CCCCC/D//DD/M/

```

Try it online!

Takes input in unary, and I'm (ab)using the footer field on TIO for input so output is preceded by a newline.
> 2 votes

# Answer
# Cubix, 69 ~~74~~ ~~80~~ bytes

```
/.UI,..N&..0\0&/52"IVXLCDM"U,r%ws;rr3tu;pw..u;qrUosv!s.u\psq,!@Us(0;U

```

Try it online!

```
        / . U I
        , . . N
        & . . 0
        \ 0 & /
5 2 " I V X L C D M " U , r % w
s ; r r 3 t u ; p w . . u ; q r
U o s v ! s . u \ p s q , ! @ U
s ( 0 ; U . . . . . . . . . . .
        . . . .
        . . . .
        . . . .
        . . . .

```

Watch It Running

I have managed to compress it a bit more, but there is still some pesky no-ops, especially on the top face.

* `52"IVXLCDM"U` put the necessary divisors and characters on the stack. The 5 and 2 will be used to reduce the div/mod value and the characters will be discarded after use.
* `UIN0/&0\&,/U` u-turns onto the top face and starts a long tour to get the input and push 1000 onto the stack. An initial divide is done and a u-turn onto the `r` of the next snippet. This was an area I was looking at to make some savings.
* `,r%ws;rr` beginning of the divmod loop. integer divide, rotate the result away mod, then rearrange top of stack to be reduced input, current divisor and divide result.
* `3tus` bring the current character to the top and swap it with the divide result.
* `!vsoUs(0;U` this is the print loop. while the div result is more than 0, swap with character output, swap back, decrement, push a 0 and drop it. On 0 redirect over the pop stack (remove divide result) and around the cube.
* `\u;pwpsq,!@Urq;u` with a bit of redirection, this removes the character from the stack, brings the 5 and 2 to the top, swaps them and pushes one back down. The remaining is used to reduce the divisor. Halt if it reduces to 0, otherwise push the 5 or 2 to the bottom and re-enter the loop.
> 2 votes

# Answer
# Python 2, ~~109~~ 90 bytes

```
lambda n,r=[1000,500,100,50,10,5,1]:''.join(n%a/b*c for a,b,c in zip([n+1]+r,r,'MDCLXVI'))

```

Try it online!
> 1 votes

# Answer
# Mathematica, 130 bytes

```
(f=#~NumberDecompose~{1000,500,100,50,10,5,1};""<>{Flatten@Table[Table[{"M","D","C","L","X","V","I"}[[i]],f[[i]]],{i,Length@f}]})&

```
> 1 votes

# Answer
# PHP, 70 bytes

```
for($r=1e3;$a=&$argn;)$a/$r<1?$r/=++$i%2?2:5:$a-=$r*print MDCLXVI[$i];

```

Try it online!
> 1 votes

# Answer
# T-SQL, 164 bytes

```
SELECT REPLICATE('M',n/1000)+IIF(n%1000>499,'D','')
      +REPLICATE('C',n%500/100)+IIF(n%100>49,'L','')
      +REPLICATE('X',n%50/10)+IIF(n%10>4,'V','')
      +REPLICATE('I',n%5)
FROM t

```

Line breaks added for readability only.

This version is a lot longer (230 characters), but feels much more "SQL-like":

```
DECLARE @ INT,@r varchar(99)=''SELECT @=n FROM t
SELECT'I's,1v INTO m
INSERT m VALUES('V',5),('X',10),('L',50),('C',100),('D',500),('M',1000)
L:
    SELECT @-=v,@r+=s
    FROM m WHERE v=(SELECT MAX(v)FROM m WHERE v<=@)
IF @>0GOTO L
SELECT @r

```

Makes a table *m* with all the char-value mappings, and then loops through finding the largest value \<= the number, concatenating the matching character.
> 1 votes

# Answer
# Japt, 34 bytes

```
"IVXLCD"£%(U/=Y=v *3+2Y)îXÃw i'MpU

```

Test it online!

```
"IVXLCD"£    %(U/=Y=v  *3+2Y )îXÃ w i'MpU
"IVXLCD"mXY{U%(U/=Y=Yv *3+2,Y)îX} w i'MpU : Ungolfed
                                          : Implicit: U = input number
"IVXLCD"mXY{                    }         : Map each char X and its index Y in this string to:
                  Y=Yv *3+2               :   Set Y to 5 for even indexes, 2 for odd.
               U/=                        :   Divide U by this amount.
            U%(            ,Y)            :   Modulate the old value of U by 5.
                              îX          :   Repeat the character that many times.
                                          : This returns e.g. "IIVCCCD" for 16807.
                                  w       : Reverse the entire string.
                                    i'MpU : Prepend U copies of 'M' (remember U is now the input / 1000).
                                          : Implicit: output result of last expression

```
> 1 votes

# Answer
## JavaScript (ES6), 65 bytes

A recursive function.

```
f=(n,a=(i=0,1e3))=>n?a>n?f(n,a/=i++&1?5:2):'MDCLXVI'[i]+f(n-a):''

```

### How?

The second recursive call `f(n-a)` really should be `f(n-a,a)`. By omitting the 2nd parameter, `a` and `i` are reinitialized (to 1000 and 0 respectively) each time a new Roman digit is appended to the final result. This causes more recursion than needed but doesn't alter the outcome of the function and saves 2 bytes.

### Test cases

```
f=(n,a=(i=0,1e3))=>n?a>n?f(n,a/=i++&1?5:2):'MDCLXVI'[i]+f(n-a):''

console.log(f(3))
console.log(f(4))
console.log(f(9))
console.log(f(42))
console.log(f(796))
console.log(f(2017))
console.log(f(16807))
```
> 1 votes

# Answer
# , ~~26~~ 23 bytes

3 bytes saved thanks to Adám.

```
'MDCLXVI'#~(_,6$2 5)&#:

```

Try it online!

~~Similar to the APL answer~~ basically the same thing.

```
'MDCLXVI'#~(_,6$2 5)&#:
           (       )&#:   mixed base conversion from decimal
              6$2 5       2 5 2 5 2 5
            _,            infinity 2 5 2 5 2 5
                          this gives us e.g. `0 0 0 0 1 0 4` for input `14`
'MDCLXVI'#~               shape each according to the number of times on the right
                          this is greedy roman numeral base conversion

```
> 1 votes

# Answer
## Batch, 164 bytes

```
@set/pn=
@set s=
@for %%a in (1000.M 500.D 100.C 50.L 10.X 5.V 1.I)do @call:c %%~na %%~xa
@echo %s:.=%
@exit/b
:c
@if %n% geq %1 set s=%s%%2&set/an-=%1&goto c

```

Takes input on STDIN.
> 1 votes

# Answer
# Oracle SQL, 456 bytes

```
select listagg((select listagg(l)within group(order by 1)from dual start with trunc((n-nvl(n-mod(n,p),0))/v)>0 connect by level<=trunc((n-nvl(n-mod(n,p),0))/v)))within group(order by v desc)from (select 2849n from dual)cross join(select 1000v,null p,'m'l from dual union select 500,1000,'d'from dual union select 100,500,'c'from dual union select 50,100,'l'from dual union select 10,50,'x'from dual union select 5,10,'v'from dual union select 1,5,'i'from dual)

```

Outputs:

```
mmdcccxxxxviiii

```

Please note the actual size of the line is 460bytes, because it includes the input number (2849).

Ungolfed:

```
select listagg(
            (select listagg(l, '') within group(order by 1)
             from dual
             start with trunc((n-nvl(p*trunc(n/p),0))/v) > 0
             connect by level <= trunc((n-nvl(p*trunc(n/p),0))/v) )
        ) within group(order by v desc)
from (select 2348 n
    from dual
) cross join (
    select 1000v, null p, 'm' l from dual union
    select 500, 1000, 'd' from dual union
    select 100, 500, 'c' from dual union
    select 50, 100, 'l' from dual union
    select 10, 50, 'x' from dual union
    select 5, 10, 'v' from dual union
    select 1, 5, 'i' from dual
)

```

How it works: I calculate how many of each letter I need, by calculating the most I can get to with the higher value one (infinity for M), and then doing an integer division between the current letter's value and the result of that.

E.g. 2348, how many `C`s do I need? `trunc((2348-mod(2348,500))/100)` = 3.

Then, I `listagg` that letter together 3 times (exploiting `CONNECT BY` to generate the 3 rows I need). Finally, I `listagg` everything together.

Kinda bulky, but most of it is the `select from dual`s in the conversion table and I can't really do much about that...
> 1 votes

# Answer
# Charcoal, 61 50 46 bytes

```
ＮνＡ⁰χＷφ«Ｗ¬‹νφ«§MDCLXVIχＡ⁻νφν»Ａ⁺¹χχＡ÷φ⎇﹪χ²¦²¦⁵φ

```

Try it online!

Explanation:

```
Ｎν                   Take input as number and assign it to ν
Ａ⁰χ                  Let χ=0
Ｗφ«                  While φ>0 (φ has a predefined value of 1000)
    Ｗ¬‹νφ«               While v>=φ
        §MDCLXVIχ             Take the char from string "MDCLXVI" at position χ
        Ａ⁻νφν»               Let ν=ν-φ
    Ａ⁺¹χχ                Increment χ
    Ａ÷φ⎇﹪χ²¦²¦⁵φ        If χ is odd, divide φ by 5, else divide φ by 2

```
* 4 bytes saved thanks to Neil, while I am still trying to figure out how to proceed with the second part of his comment.
> 0 votes

# Answer
# Java (OpenJDK 8), ~~119~~ 118 bytes

```
n->{String s="";for(int v[]={1,5,10,50,100,500,1000},i=7;i-->0;)for(;n>=v[i];n-=v[i])s+="IVXLCDM".charAt(i);return s;}

```

Try it online!

Saved a byte thanks to @TheLethalCoder
> 0 votes

# Answer
# Charcoal, 34 bytes

```
ＮςＡ²ξＦMDCLXVI«×ι÷ςφＡ﹪ςφςＡ÷φξφＡ÷χξξ

```

Originally based on @CarlosAlego's answer. A port of @xnor's Python solution is also 34 bytes:

```
ＮθＡ⁵ξＦIVXLCD«←×ι﹪θξＡ÷θξθＡ÷χξξ»←×Mθ

```

Edit: A port of @xnor's other Python solution turns out to be 33 bytes!

```
ＮθＦMDCLXVI«×ι÷θφＡ﹪θφθＡ÷φ⁺×³﹪φ³±¹φ

```

Try it online! Link is to verbose version of code. Note that I've used `⁺×³﹪φ³±¹` instead of `⁻×³﹪φ³¦¹` because the deverbosifier is currently failing to insert the separator.
> 0 votes

# Answer
# C++, 272 Bytes

```
#include <cstdio>
#include <map>
std::map<int,char> m = {{1000,'M'},{500,'D'},{100,'C'},{50,'L'},{10,'X'},{5,'V'},{1,'I'}};
int main(){unsigned long x;scanf("%d",&x);for(auto i=m.rbegin();i!=m.rend();++i)while(x>=i->first){printf("%c", i->second);x=x-i->first;}return 0;}

```
> 0 votes

# Answer
# C, 183 Bytes

```
#include <stdio.h>
int v[]={1000,500,100,50,10,5,1};
char*c="MDCLXVI";
int main(){int x;scanf("%d",&x);for(int i=0;i<sizeof v/sizeof(int);i++)for(;x>=v[i];x-=v[i])putc(c[i],stdout);}

```

Same algorithm as before, just using plain c arrays instead of an std::map, partially inspired by @xnor's answer and using a string to store the letters.
> 0 votes

# Answer
## Common Lisp, 113 bytes

This is an anonymous function, returning the result as a string.

```
(lambda(value)(setf(values a b)(floor v 1000))(concatenate 'string(format()"~v,,,v<~>"a #\M)(format nil"~@:r"b)))

```

Ungolfed, with descriptive variable names and comments:

```
(defun format-roman (value)
  ;; Get "value integer-divided by 1000" and "value mod 1000"
  (setf (values n_thousands remainder) (floor value 1000))
  (concatenate 'string
               ;; Pad the empty string n_thousands times, using "M" as the
               ;; padding character
               (format () "~v,,,v<~>" n_thousands #\M)
               ;; Format the remainder using "old-style" Roman numerals, i.e.
               ;; numerals with "IIII" instead of "IV"
               (format nil "~@:r" remainder)))

```

CL has built-in Roman numeral formatter. Sadly it doesn't work for numbers larger than 3999.
> 0 votes

---
Tags: code-golf, math, arithmetic, base-conversion, roman-numerals
---


title: Fire propagation simulator

text:
# Question
Title: Fire propagation simulator
Suppose we have a matrix like this:

```
11111
12221
12321
12221
11111

```

This matrix represents a terrain, and each cell represents a portion of terrain. The number in each cell represents the time the portion of terrain needs to be completely burnt (in minutes, if a measurement unit is needed), according to its combustibility. If a fire starts at any given position (cell), that cell needs to be completely burnt before the fire propagates to the adjacent cells (horizontal and vertical only, not diagonal). So, if a fire is started at the center position, the fire needs:

```
11111        11111        11111        11011        10001        00000
12221  3 m.  12221  2 m.  12021  1 m.  11011  1 m.  00000  1 m.  00000
12321 -----> 12021 -----> 10001 -----> 00000 -----> 00000 -----> 00000
12221        12221        12021        11011        00000        00000
11111        11111        11111        11011        10001        00000

```

Explanation:

* Fire starts at \[2,2\] (0-based), which has a burn time of 3.
* After 3 minutes, \[1,2\],\[2,1\],\[2,3\],\[3,2\] start to burn.
* After 2 minutes, those cells end burning and fire propagates to all adjacent cells, but \[0,2\],\[2,0\],\[2,4\],\[0,4\] need only 1 more minute to burn, so
* After 1 minute, those cells are burnt and the cell propagates to their adjacent cells.
* After 1 more minute, the rest of cells from step 3 end burning and fire propagates to their adjacent cells (that are already burnt, so nothing happens).
* After 1 last minute, fire ends burning the whole terrain.

So the solution to that case is 8 minutes. If the fire starts in the top leftmost cell \[0,0\]:

```
11111     01111     00111     00011     00001     00000
12221  1  12221  1  02221  1  01221  1  00121  1  00011   1
12321 --> 12321 --> 12321 --> 02321 --> 01321 --> 00321  -->
12221     12221     12221     12221     02221     01221
11111     11111     11111     11111     11111     01111

00000     00000     00000     00000     00000
00000  1  00000  1  00000  1  00000  1  00000
00221 --> 00110 --> 00000 --> 00000 --> 00000
00221     00121     00020     00010     00000
00111     00011     00001     00000     00000

```

So now the total time is 10 minutes.

### The challenge

Given a NxM matrix (N\>0, M\>0) of integer values that represent the time every cell needs to be completely consumed, write the shortest program/function that takes that matrix and a pair of integers with the position the fire starts in, and returns/prints the time needed for the fire to completely consume the whole terrain.

* Every cell will have a positive (non-zero) burn time. You cannot assume a maximum value for the cells.
* The matrix does not need to be square nor symmetric.
* The matrix can be 0-indexed or 1-indexed, as you like.
* The position can be given as a single parameter with a tuple of integers, two separate parameters of whatever other reasonable format.
* The dimensions of the matrix cannot be specified as input parameters.
* You do not need to output every intermediate step, just the amount of time asked. But I won't complain if the steps are visualized in any way.

### Another example:

```
Fire starts at [1,1] (a '>' represents a minute):

4253   4253   4253   4153   4043   3033   2023    0001   0000
2213 > 2113 > 2013 > 1003 > 0002 > 0001 > 0000 >> 0000 > 0000
1211   1211   1211   1111   1001   0000   0000    0000   0000

Output: 9

```

This is , so may the shortest program for each language win!

# Answer
> 12 votes
## Matlab, ~~235~~ ~~257~~ ~~190~~ ~~182~~ 178 bytes

Input: Matrix `A`, 1x2 vector `p` containing the starting coordinates.

```
function t=F(A,p)
[n,m]=size(A);x=2:n*m;x(mod(x,n)==1)=0;B=diag(x,1)+diag(n+1:n*m,n);k=sub2ind([n m],p(1),p(2));t=max(distances(digraph(bsxfun(@times,((B+B')~=0),A(:))'),k))+A(k)

```

### Explanation:

Instead of simulating the the fire propagation, we can also understand this as a "find the longest shortest path" problem. The matrix is converted into a weighted directed graph. The weights of the paths to a single node correspond to the time to burn said node. E.g. for a matrix

```
5   7   7   10
5   2   2   10
4   5   2   6

```

we get the connected graph:

Where node 1 is the upper left matrix element and node 12 the lower right element. Given starting coordinates `p`, the shortest path to all other nodes is calculated. Then the length of the longest path of those shortest paths + the time to burn the initial node equals to the time to burn the whole matrix.

Ungolfed and commented version with sample starting values:

```
% some starting point
p = [3 2];
% some random 5x6 starting map, integers between 1:10
A = randi(10,5,6);

function t=F(A,p)
% dimensions of A
[n,m] = size(A);
% create adjacency matrix
x=2:n*m;
x(mod(x,n)==1)=0;
B = diag(x,1)+diag(n+1:n*m,n);
B = B+B';
B = bsxfun(@times,(B~=0),A(:))';
% make graph object with it
G = digraph(B);
% starting node
k = sub2ind([n m], p(1), p(2));
% calculate the shortest distance to all nodes from starting point
d = distances(G,k);
% the largest smallest distance will burn down last. Add burntime of initial point
t = max(d)+A(k);

```

# Answer
> 9 votes
## JavaScript (ES6), ~~156~~ ~~152~~ ~~146~~ ~~144~~ 143 bytes

*Saved 1 byte thanks to Kevin Cruijssen*

A rather naive implementation. Takes input in currying syntax `(a)(s)`, where ***a*** is a 2D-array and ***s*** is an array of two integers \[***x, y***\] representing the 0-based coordinates of the starting position.

```
a=>s=>(g=t=>(a=a.map((r,y)=>r.map((c,x)=>(z=(h,v)=>(a[y+~~v]||[])[x+h]<1)(-1)|z(1)|z(0,-1)|z(0,1)|x+','+y==s&&c?u=c-1:c),u=-1),~u?g(t+1):t))(0)

```

### Formatted and commented

```
a => s => (                                // given a and s
  g = t => (                               // g = recursive function with t = time counter
    a = a.map((r, y) =>                    // for each row r of the input array:
      r.map((c, x) =>                      //   for each cell c in this row:
        (                                  //     z = function that takes
          z = (h, v) =>                    //         2 signed offsets h and v and checks
            (a[y + ~~v] || [])[x + h] < 1  //         whether the corresponding cell is 0
        )(-1) | z(1) |                     //     test left/right neighbors
        z(0, -1) | z(0, 1) |               //     test top/bottom neighbors
        x + ',' + y == s                   //     test whether c is the starting cell
        && c ?                             //     if at least one test passes and c != 0:
          u = c - 1                        //       decrement the current cell / update u
        :                                  //     else:
          c                                //       let the current cell unchanged
      ),                                   //   end of r.map()
      u = -1                               //   start with u = -1
    ),                                     // end of a.map() --> assign result to a
    ~u ?                                   // if at least one cell was updated:
      g(t + 1)                             //   increment t and do a recursive call
    :                                      // else:
      t                                    //   stop recursion and return t
  )                                        // end of g() definition
)(0)                                       // initial call to g() with t = 0

```

### Test cases

```
let f =

a=>s=>(g=t=>(a=a.map((r,y)=>r.map((c,x)=>(z=(h,v)=>(a[y+~~v]||[])[x+h]<1)(-1)|z(1)|z(0,-1)|z(0,1)|x+','+y==s&&c?u=c-1:c),u=-1),~u?g(t+1):t))(0)

console.log(f([
  [1,1,1,1,1],
  [1,2,2,2,1],
  [1,2,3,2,1],
  [1,2,2,2,1],
  [1,1,1,1,1]
])([2, 2]))

console.log(f([
  [1,1,1,1,1],
  [1,2,2,2,1],
  [1,2,3,2,1],
  [1,2,2,2,1],
  [1,1,1,1,1]
])([0, 0]))

console.log(f([
  [4,2,5,3],
  [2,2,1,3],
  [1,2,1,1]
])([1, 1]))
```

# Answer
> 8 votes
# Octave, 67 bytes

```
function n=F(s,a)n=0;do++n;until~(s-=a|=imdilate(~s,~(z=-1:1)|~z')

```

Try it online!

To visualize intermediate results you can Try this!

A function that take as input matrix of terrain `a` and initial coordinate as a matrix of 0&1 with the same size as terrain.

Actually there is no need to `endfunction` however to run the example in tio it should be added.

Explanation:

Repeatedly apply morphological image dilation on the terrain and subtract the burned areas from it.

Ungolfed answer:

```
function n = Fire(terrain,burned)
    n = 0;
    mask = [...
            0  1  0
            1  1  1
            0  1  0];
    while true
        n = n + 1;
        propagation = imdilate(~terrain, mask);
        burned = burned | propagation;
        terrain = terrain - burned;
        if all(terrain(:) == 0)
            break;
        end
    end
end

```

# Answer
> 7 votes
# MATL, ~~26~~ 25 bytes

> I really wanted to see some more answers using the golfiest languages around here

```
`yy)qw(8My~1Y6Z+fhy0>z}@&

```

Input format is:

* First input is a matrix using `;` as row separator.
* Second input is a single number which addresses an entry of the matrix in 1-based column-major order (allowed by the challenge). For example, the column-major coordinate of each entry in a 3×4 matrix is given by

```
1  4  7 10
2  5  8 11
3  6  9 12

```

So for instance 1-based coordinates (2,2) correspond to `5`.

**Try it online!** Or **verify all test cases**.

### Explanation

The code maintains a list of entries that are burning. At each iteration, all entries of that list are decremented. When an entry reaches zero, its neighbouring entries are added to the list. To save bytes, entries that reach zero are not removed from the list; instead, they keep "burning" with negative values. The loop is exited when none of the entries have positive values.

See the program **running step by step** with slightly modified code.

Commented code:

```
`      % Do...while
  yy   %   Duplicate top two arrays (matrix and array of positions to be decremented)
       %   In the first iteration this implicitly takes the two inputs
  )    %   Reference indexing. This gives the values that need to be decremented
  q    %   Decrement
  w    %   Swap. This brings the array of positions that have been decremented to top
  (    %   Assignment indexing. This writes the decremented values back into their
       %   positions
  8M   %   Push array of positions again
  y    %   Duplicate decremented matrix
  ~    %   Negate. This replaces zeros by 1, and nonzeros by 0
  1Y6  %   Push predefined literal [0 1 0; 1 0 1; 0 1 0] (4-neighbourhood)
  Z+   %   2D convolution, maintaining size
  f    %   Find: gives column-major indices of neighbours of totally burnt entries
  h    %   Concatenate. This updates the array of positions to be decremented
  y    %   Duplicate decremented matrix
  0>   %   This gives 1 for positive entries, and 0 for the rest
  z    %   Number of nonzeros. This is the loop condition (*)
}      % Finally (execute before exiting loop)
  @    %   Push iteration number. This is the output
  &    %   Specify that the final implicit display function will display only the top
       %   of the stack
       % Implicit end. If the top of the stack (*) is not 0 (i.e. there are entries
       % that have not been totally burnt) the loop proceeds with the next iteration.
       % Else the "finally" branch is executed and the loop is exited
       % Implicit display (only top of the stack)

```

# Answer
> 5 votes
# Python 3, ~~277~~ 266 bytes

```
def f(m,s):
 p={s};w=len(m);t=0
 while sum(sum(m,[])):
  t+=1;i=0
  for x,y in p:
   try:m[x][y]=max(0,m[x][y]-1)
   except:0
  for v in sum(m,[]):
   if v<1:
    for l in[(1,0),(-1,0),(0,1),(0,-1)]:a,b=max(0,i%w+l[0]),max(0,i//w+l[1]);p.add((a,b))
   i+=1
 print(t)

```

Try it online!

Defines a function `f` that takes a 2D matrix and a tuple of points. The first thing the function does is define a set of tuples containing the initial tuple value passed in: `p={s}`. The function then goes through every tuple of points in `p` and subtracts one from the matrix `m` at that point, unless the value is already zero. It then loops through `m` again finding all points with the value zero and adding the four neighbors of that point to the set `p`. This is why I chose to use a set, because sets in Python don't allow duplicate values (which would screw up the subtraction a lot). Unfortunately, due to list index wrapping (e.g: `list[-1] == list[len(list)-1]`) the indices need to be constrained so they do not go negative and add the wrong coordinates to `p`.

Nothing special, still getting used to golfing. Definitely room for improvement here, I'm going to keep cracking at it.

# Answer
> 4 votes
# Python 2, 170 bytes

```
s,m=input()
t={s}
r=0
while max(sum(m,[]))>0:
 r+=1
 for a,b in t|t:
	try:a<0<x;b<0<x;m[a][b]-=1;t|=m[a][b]==0and{(a+1,b),(a-1,b),(a,b+1),(a,b-1)}or t^t
	except:0
print r

```

Try it online!

# Answer
> 4 votes
# APL (Dyalog), ~~93~~ ~~66~~ 57 bytes

```
{⍵{^/,0≥⍺:0⋄1+x∇⍵∨{∨/,⍵∧⍲/¨2|⍳3 3}⌺3 3⊢0=x←⍺-⍵}(⊂⍺)≡¨⍳⍴⍵}

```

Try it online! or Visualize it online!

---

This function takes the terrain matrix as right argument and the coordinates (1-based) of first fire as left argument. Returns the number of minutes needed to burn everything.

---

# Updates

Finally found a way to golf down the spread function.
\*Sigh\* it would be so much easier if the world was toroidal.

---

TIO just upgraded to Dyalog 16.0, which means now we have the shiny new stencil operator

# Answer
> 2 votes
# Python 2, 268 bytes

```
def f(m,y,x):t,m[y][x]=m[y][x],0;g(m,t)
def g(m,t):
	n,h,w=map(lambda r:r[:],m),len(m),len(m[0])
	for l in range(h*w):r,c=l/h,l%h;n[r][c]-=m[r][c]and not all(m[r][max(c-1,0):min(c+2,w+1)]+[m[max(r-1,0)][c],m[min(r+1,h-1)][c]])
	if sum(sum(m,[])):g(n,t+1)
	else:print t

```

Try it online!

Recursively iterate over time steps in which every tile's number is reduced if it is cardinally adjacent to a 0. Very straightforward algorithm that, I believe, can still be golfed for boolean efficiency...

\*note: my 'Try it online!' code includes bonus debug logging in the footer. I like to watch the algorithm progress.

# Answer
> 2 votes
# Haskell, 138 133 bytes

```
u#g|all((<=0).snd)g=0|2>1=1+(u:[[(x+1,y),(x-1,y),(x,y-1),(x,y+1)]|((x,y),0)<-n]>>=id)#n where n=d<$>g;d p|elem(fst p)u=pred<$>p|2>1=p

```

Try it online!

Assumes input is a list of ((x,y),cell). Ungolfed:

```
type Pos = (Int, Int)

ungolfed :: [Pos] -> [(Pos, Int)] -> Int
ungolfed burning grid
  | all ((<=0).snd) grid = 0
  | otherwise = 1 + ungolfed (burning ++ newburning) newgrid
 where
  newgrid = map burn grid
  burn (pos,cell) | pos `elem` burning = (pos, cell - 1)
                  | otherwise = (pos, cell)
  newburning = do
    ((x,y),cell) <- newgrid
    guard (cell <= 0)
    [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]

```

---
Tags: code-golf, matrix, simulation
---


# Question
Title: Playing with robots for kids - Which letter will I reach?
> **TL;DR:** Given an array of chars and a robot in a starting position of the array, write an algorithm than can read a string with movements (`F` for "go forward", `R` for "rotate 90 degrees right" and `L` for "rotate 90 degrees left") and calculate the ending position of the robot. More details in the complete text.

We have at home a very simple programmable device for kids: a small vehicle with buttons to make the vehicle go forward, turn 90 degrees left or turn 90 degrees right. Something similar to this:

We also have a foam mat with letters like this:

The purpose of all this is to teach the kids both the alphabet and the rudiments of programming, all at once.

### The challenge

Suppose we have randomly arranged our foam mat like this:

```
+---+---+---+---+---+---+---+
| E | R | L | B | I | X | N |
+---+---+---+---+---+---+---+
| O | A | Q | Y | C | T | G |
+---+---+---+---+---+---+---+
| F | W | H | P | D | Z | S |
+---+---+---+---+---+---+---+
    | K | V | U | M | J |
    +---+---+---+---+---+
            |   |
            +---+

```

Suppose also we have modified the vehicle so that when we program a "go forward" command, the vehicle goes forward exactly size of one square in the mat. So, if the vehicle is in the `U` square and goes north, it stops exactly in the `P` square.

The instructions are all given to the vehicle before it starts to move, and those are:

* `F`: The vehicle goes forward into the next square.
* `R`: The vehicle turns 90 degrees right in its place (no further movement).
* `L`: The vehicle turns 90 degrees left in its place (no further movement).

Once the instructions are given, you can press the "GO" button and send the vehicle to a given position as it will follow every instruction in the given order. So, you can tell the kid to insert the needed instructions for the vehicle to go to a given letter.

You must write the shortest program/function that processes a `string` (input parameter) with a set of instructions and calculates the letter the vehicle stops over (output `string`).

Details:

* The vehicle always starts at the blank square at the bottom, and facing north (towards the `U` square).
* The input string will contain only the letters `F`, `R`, `L` and `G` (for the "go" button). You can use lowercase letters for the mat and the instructions, if you prefer so.
* The algorithm must obey every instruction in the string before the first `G` (every instruction after that is ignored as the vehicle has started moving).
* If the vehicle goes out of the mat at any given moment (even if the input string has not been completely processed), the algorithm must return the string `Out of mat`.
* If not, the algorithm must return the letter the vehicle has stopped over. The starting point counts as a  char (or an empty string).

### Examples:

```
Input: FFG
Output: P

Input: FRFRFG
Output: Out of mat

Input: RRFFG
Output: Out of mat

Input: FFFRFFLFG
Output: X

Input: FFFRFFLF
Output:      <-- Nothing or a whitespace (the robot has not started moving)

Input: FFFRRFFFG
Output:      <-- Nothing or a whitespace (the robot has returned to the starting point)

Input: RRRRRLFFFLFFRFRFGFFRRGRFF
Output: L    (Everything after the first G is ignored)

```

This is , so may the shortest program for each language win!

# Answer
> 3 votes
# JavaScript (ES6), ~~194~~ ~~176~~ ~~169~~ 163 bytes

Saved some bytes thanks to @Luke and @Arnauld.

```
s=>(p=35,d=3,t='ERLBIXN1OAQYCTG1FWHPDZS11KVUMJ11111 11',[...s].every(i=>i=='L'?d--:i>'Q'?d++:i<'G'?+t[p+=[1,8,-1,-8][d%4]]||!t[p]?p=1/0:p:0)?'':t[p]||'Out of mat')

```

Ungolfed:

```
s=>(
  p=35,
  d=3,
  t='ERLBIXN1OAQYCTG1FWHPDZS11KVUMJ11111 11',
  [...s].every(i=>i=='L'?d--:
                  i<'Q'?d++:
                  i<'G'?+t[p+=[1,8,-1,-8][d%4]]||!t[p]?p=1/0:p:
                  0
              )?'':
               t[p]||'Out of mat'
)

```

```
f=
s=>(p=35,d=3,t='ERLBIXN1OAQYCTG1FWHPDZS11KVUMJ11111 11',[...s].every(i=>i=='L'?d--:i>'Q'?d++:i<'G'?+t[p+=[1,8,-1,-8][d%4]]||!t[p]?p=1/0:p:0)?'':t[p]||'Out of mat')

console.log(f('FFG')); //P
console.log(f('FRFRFG')); //Out of mat
console.log(f('RRFFG')); //Out of mat
console.log(f('FFFRFFLFG')); //X
console.log(f('FFFRFFLF')); //(space)
console.log(f('FFFRRFFFG')); //(space)
console.log(f('RRRRRLFFFLFFRFRFGFFRRGRFF')); //L
console.log(f('FFFFFRRFG')); //Out of mat
```

# Answer
> 2 votes
# Python 3, ~~226~~ ~~231~~ 241 bytes

Second edit; should work now. Again, plenty of optimization to be done.

```
n=input();s="0ERLBIXN00OAQYCTG00FWHPDZS000KVUMJ000000 00000";d=1;c=40;i=0;w=[-1,-9,1,9]
while n[i]!="G"and c>=0:
 if n[i]=="F":c+=w[d]
 else:d=[d+[-1,3][d<0],-~d%4][n[i]=="R"]
 i+=1
print(["Out of mat",s[c]][c in range(len(s))and s[c]!="0"])

```

Try it online!

# Answer
> 2 votes
# Python 2, 235 bytes

```
x=0;y=1;a=4;b=3
p='ERLBIXN','OAQYCTG','FWHPDZS','aKVUMJ','aaa '
r=''
for i in input():
 if'G'==i:r=p[a][b];break
 elif'G'>i:
  b+=x;a-=y;
  if(-1<a<5)-1or(''<p[a][b:]<'a')-1:r='Out of mat';break
 else:x,y=[[y,-x],[-y,x]][i<'R']
print r

```

Try it online!

# Answer
> 0 votes
# Wolfram Language/Mathematica, 300 Bytes

```
p=Re[(1-7I)#[[1]]]&;d=Drop;t=Throw;s=Switch;s[#,0,"Out of mat",_,StringPart["000 0000KVUMJ0FWHPDZSOAQYCTGERLBIXN",p@#]]&@Catch@Fold[If[MemberQ[d[d[Range[4,35],{2,5}],{7}],p@#],#,t@0]&@(s[#2,"F",#+{#[[2]],0},"R",#{1,-I},"L",#{1,I},_,t[#]]&)[#1,#2]&,{4,I},If[StringFreeQ["G"]@#,{"G"},Characters@#]&@#]&

```

Ungolfed:

```
p = Re[(1 - 7 I) #[[1]]] &;
d = Drop;
t = Throw;
s = Switch;
s[#,
    0, "Out of mat",
    _, StringPart["000 0000KVUMJ0FWHPDZSOAQYCTGERLBIXN", p@#]] &@
  Catch@
  Fold[
    If[MemberQ[d[d[Range[4, 35], {2, 5}], {7}], p@#], #,
        t@0] &@(s[#2, "F", # + {#[[2]], 0}, "R", # {1, -I},
          "L", # {1, I}, _, t[#]] &)[#1, #2] &,
    {4, I},
    If[StringFreeQ["G"]@#, {"G"}, Characters@#] &@#] &

```

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


title: Short Date into English Long Date

text:
# Question
Title: Short Date into English Long Date
Convert short date format into English long date in as few bytes as possible.

# Input

Input will be in the form of a string with format, `yyyy-mm-dd`, with zero padding optional for all values. You can assume that this is syntactically correct, but not necessarily a valid date. Negative year values do not need to be supported.

# Output

You must convert the date into the English long date format (e.g. `14th February 2017`). Zero padding here is not allowed.

If the date is invalid (e.g. `2011-02-29`), then this must be recognised in some way. Throwing an exception is allowed.

More examples can be seen below.

# Test Cases

```
"1980-05-12" -> 12th May 1980
"2005-12-3"  -> 3rd December 2005
"150-4-21"   -> 21st April 150
"2011-2-29"  -> (error/invalid)
"1999-10-35" -> (error/invalid)

```

# Answer
# PostgreSQL, 61 characters

```
prepare f(date)as select to_char($1,'fmDDth fmMonth fmYYYY');

```

Prepared statement, takes input as parameter.

Sample run:

```
Tuples only is on.
Output format is unaligned.
psql (9.6.3, server 9.4.8)
Type "help" for help.

psql=# prepare f(date)as select to_char($1,'fmDDth fmMonth fmYYYY');
PREPARE

psql=# execute f('1980-05-12');
12th May 1980

psql=# execute f('2005-12-3');
3rd December 2005

psql=# execute f('150-4-21');
21st April 150

psql=# execute f('2011-2-29');
ERROR:  date/time field value out of range: "2011-2-29"
LINE 1: execute f('2011-2-29');
                  ^
psql=# execute f('1999-10-35');
ERROR:  date/time field value out of range: "1999-10-35"
LINE 1: execute f('1999-10-35');
                  ^
HINT:  Perhaps you need a different "datestyle" setting.

```
> 5 votes

# Answer
# Python 3.6, ~~137~~ 129 bytes

```
from datetime import*
def f(k):g=[*map(int,k.split('-'))];n=g[2];return f"{date(*g):%-d{'tsnrhtdd'[n%5*(n^15>4>n%10)::4]} %B %Y}"

```

Try it online!
> 7 votes

# Answer
# Python 3.6, 154 bytes

```
from datetime import*
s=[*map(int,input().split('-'))]
b=s[2]
print(date(*s).strftime(f"%-d{'th'if(3<b<21)+(23<b<31)else('st','nd','rd')[b%10-1]} %B %Y"))

```

Try it online! (Set input stream and then run.)

Thanks to good suggestions from commenters below.
> 5 votes

# Answer
# JavaScript (ES6), ~~142~~ 140 bytes

Outputs `NaNth Invalid Date` for invalid dates.

The code for ordinal numbers was adapted from this answer.

```
d=>`${s=(D=new Date(d)).getDate()+''}${[,'st','nd','rd'][s.match`1?.$`]||'th'} `+D.toLocaleDateString('en-GB',{month:'long',year:'numeric'})

```

```
f=
d=>`${s=(D=new Date(d)).getDate()+''}${[,'st','nd','rd'][s.match`1?.$`]||'th'} `+D.toLocaleDateString('en-GB',{month:'long',year:'numeric'})

console.log(
  f('2005-12-3'),
  f('1980-05-12'),
  f('2005-12-3'),
  f('150-4-21'),
  f('2011-2-29'),
  f('1999-10-35')
)
```
> 5 votes

# Answer
# Bash + coreutils, 115 78

* 2 bytes saved thanks to @manatwork.

```
d="date -d$1 +%-e"
t=`$d`
f=thstndrd
$d"${f:t/10-1?t%10<4?t%10*2:0:0:2} %B %Y"

```

Try it online.
> 5 votes

# Answer
# PHP, 87 bytes

```
<?=checkdate(($a=explode("-",$argn))[1],$a[2],$a[0])?date("jS F Y",strtotime($argn)):E;

```

Run as pipe with `-F` or test it online. Always prints a 4 digit year; fails for years \> 9999.

**no validity check, 35 bytes:**

```
<?=date("jS F Y",strtotime($argn));

```
> 5 votes

# Answer
# C#, ~~147~~ 143 bytes

```
s=>{var t=System.DateTime.Parse(s);int d=t.Day,o=d%10;return d+((d/10)%10==1?"th":o==1?"st":o==2?"nd":o==3?"rd":"th")+t.ToString(" MMMM yyy");}

```

*Saved 4 bytes thanks to @The\_Lone\_Devil.*
> 4 votes

# Answer
## mIRC version 7.49 (197 bytes)

```
//tokenize 45 2-2-2 | say $iif($3 isnum 1- $iif($2 = 2,$iif(4 // $1 && 25 \\ $1||16//$1,29,28),$iif($or($2,6) isin 615,30,31))&&$2 isnum1-12&&1//$1,$asctime($ctime($+($1,-,$2,-,$3)date), doo mmmm yyyy))

```
> 4 votes

# Answer
# Ruby, ~~104~~ ~~103~~ 102+8 = ~~112~~ ~~111~~ 110 bytes

Uses `-rdate -p` program flags.

-1 byte from manatwork.

```
sub(/.*-(\d*)/){Date.parse($&).strftime"%-d#{d=eval$1;(d<4||d>20)&&"..stndrd"[d%10*2,2]||:th} %B %-Y"}

```

Try it online!
> 3 votes

# Answer
# C# (.NET Core), 167 197 bytes

```
s=>s.Equals(DateTime.MinValue)?"":s.Day+((s.Day%10==1&s.Day!=11)?"st":(s.Day%10==2&s.Day!=12)?"nd":(s.Day%10==3&s.Day!=13)?"rd":"th")+" "+s.ToString("MMMM")+" "+s.Year

```

Try it online!

+30 bytes for

`using System;`

`DateTime.Parse()`
> 2 votes

# Answer
# Excel, 212 bytes

```
=ABS(RIGHT(A1,2))&IF(ABS(ABS(RIGHT(A1,2))-12)<2,"th",SWITCH(RIGHT(A1,1),"1","st","2","nd","3","rd","th"))&TEXT(MID(A1,FIND("-",A1)+1,FIND("-",REPLACE(A1,1,FIND("-",A1),""))-1)*30," mmmm ")&LEFT(A1,FIND("-",A1)-1)

```

If you break it into chunks at every ampersand, you get these pieces:

* `ABS()` pulls the day number from the last two characters in the string. Since that may include a hyphen, `ABS` converts it to positive.
* `IF((ABS-12)<2,"th",SWITCH())` adds the ordinal. The `-12` bit is because 11, 12, and 13 don't follow the normal rule and they all get `th` instead of `st`, `nd`, and `rd`. This corrects for that.
    + Note: The `SWITCH` function is only available in Excel 2016 and later. (Source) It's shorter than `CHOOSE` in this case because it can return a value if no match is found whereas `CHOOSE` requires numeric input and must have a corresponding return for each possible value.
* `TEXT(MID()*30," mmmm ")` extracts the month name. `MID()` pulls out the month number as a string and multiplying by 30 returns a number. Excel sees that number as a date (1900-01-30, 1900-02-29, 1900-03-30, etc.) and `TEXT()` formats it as a month name with a space on both ends. 28 and 29 would have also works but 30 looks "nicer".
* `LEFT()` extracts the year number.

---

Now, given all that, it would have been way easier if the test cases were all in a date range that Excel can handle as an actual date: 1900-01-01 to 9999-12-31. The big advantage is that the entire date is formatted at once. That solution is **133 bytes**:

```
=TEXT(DATEVALUE(A1),"d""" & IF(ABS(ABS(RIGHT(A1,2))-12)<2,"th",SWITCH(RIGHT(A1,1),"1","st","2","nd","3","rd","th")) & """ mmmm yyyy")

```

The other big hurdle was having to include the ordinal. Without that, the solution is just **34 bytes**:

```
=TEXT(DATEVALUE(A1),"d mmmm yyyy")

```
> 2 votes

# Answer
## Swift 3 : 298 bytes

```
let d=DateFormatter()
d.dateFormat="yyyy-MM-dd"
if let m=d.date(from:"1999-10-3"){let n=NumberFormatter()
n.numberStyle = .ordinal
let s=n.string(from:NSNumber(value:Calendar.current.component(.day, from:m)))
d.dateFormat="MMMM YYY"
print("\(s!) \(d.string(from:m))")}else{print("(error/invalid)")}

```

Try it online!
> 1 votes

# Answer
# T-SQL, 194 bytes

```
DECLARE @ DATE;SELECT @=PARSE('00'+i AS DATE)FROM t;PRINT DATENAME(d,@)+CASE WHEN DAY(@)IN(1,21,31)THEN'st'WHEN DAY(@)IN(2,22)THEN'nd'WHEN DAY(@)IN(3,23)THEN'rd'ELSE'th'END+FORMAT(@,' MMMM yyy')

```

Input is via text column *i* in pre-existing table *t*, per our IO standards.

Works for dates from Jan 1, 0001 to Dec 31, 9999. The year is output with at least 3 digits (per 150AD example).

Invalid dates will result in the following ugly error:

```
Error converting string value 'foo' into data type date using culture ''.

```

Different default language/culture settings might change this behavior. If you want a slightly more graceful error output (NULL), add 4 bytes by changing `PARSE()` to `TRY_PARSE()`.

Format and explanation:

```
DECLARE @ DATE;
SELECT @=PARSE('00'+i AS DATE)FROM t;
PRINT DATENAME(d,@) +
    CASE WHEN DAY(@) IN (1,21,31) THEN 'st'
         WHEN DAY(@) IN (2,22)    THEN 'nd'
         WHEN DAY(@) IN (3,23)    THEN 'rd'
         ELSE 'th' END
    + FORMAT(@, ' MMMM yyy')

```

The `DATE` data type introduced in SQL 2008 allows much wider range than `DATETIME`, from Jan 1, 0001 to Dec 31, 9999.

Some very early dates can be parsed wrong with my US locality settings ("01-02-03" becomes "Jan 2 2003"), so I pre-pended a couple extra zeros so it knows that first value is the year.

After that, its just a messy `CASE` statement to add the ordinal suffix to the day. Annoyingly, the SQL `FORMAT` command has no way to do that automatically.
> 1 votes

# Answer
# q/kdb+ 210 bytes, non-competing

**Solution:**

```
f:{a:"I"$"-"vs x;if[(12<a 1)|31<d:a 2;:0];" "sv(raze($)d,$[d in 1 21 31;`st;d in 2 22;`nd;d in 3 23;`rd;`th];$:[``January`February`March`April`May`June`July`August`September`October`November`December]a 1;($)a 0)};

```

**Examples:**

```
q)f "2017-08-03"
"3rd August 2017"
q)f "1980-05-12"
"12th May 1980"
q)f "2005-12-3"
"3rd December 2005"
q)f "150-4-21"
"21st April 150"
q)f "2011-2-29"       / yes it's wrong :(
"29th February 2011"
q)f "1999-10-35"
0

```

**Explanation:**

This is a horrible challenge as there is no date formatting, so I have to create months from scratch (95 bytes) as well as generating the suffix.

Ungolfed solution is below, basically split the input string and then join back together after we've added the suffix and switched out the month.

```
f:{
   // split input on "-", cast to integers, save as variable a
   a:"I"$ "-" vs x;
   // if a[1] (month) > 12 or a[2] (day) > 31 return 0; note: save day in variable d for later
   if[(12<a 1) | 31<d:a 2;
     :0];
   // joins the list on " " (like " ".join(...) in python)
   " " sv (
           // the day with suffix
           raze string d,$[d in 1 21 31;`st;d in 2 22;`nd;d in 3 23;`rd;`th];
           // index into a of months, start with 0 as null, to mimic 1-indexing
           string[``January`February`March`April`May`June`July`August`September`October`November`December]a 1;
           // the year cast back to a string (removes any leading zeroes)
           string a 0)
  };

```

**Notes:**

Dates in **q** only go back to ~1709 so I don't have a trivial way of validating the date, hence this is a non-competing entry... The best I can do is check whether the day is \> 31 or month is \> 12 and return 0.
> 1 votes

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


title: A lean, mean bean machine

text:
# Question
Title: A lean, mean bean machine
A classic example to introduce people to the concept of a discrete probability distribution is the bean machine. This machine has a large amount of marbles fall from a narrow passageway at the top, after which they hit rows of interlaced pins, where at each pin the marble hits it might fall to the left or the right of the pin. Finally, the pins are collected in vertical bins at the bottom of the machine. A simple diagram of this machine looks like this:

```
|     O     |
|     ^     |
|    ^ ^    |
|   ^ ^ ^   |
|  ^ ^ ^ ^  |
| ^ ^ ^ ^ ^ |
|_|_|_|_|_|_|

```

In this diagram, the `O` signifies the location from which the marbles fall. Each `^` is a pin at which the marble has a 50% chance to move to the square either to the left or the right of the pin. The marbles then gather at the bins on the bottom of the device, and for a large enough number of marbles, the height of the marble stacks in the bins will resemble a discrete binomial distribution.

### Challenge

For this challenge, you will be calculating the resulting probability distribution of bean machines based on diagrams like the above one. The diagrams are interpreted as a two-dimensional 'program' that the marbles pass through, either towards fields at the side or fields below the current field. When the marbles reach the bottom of the machine they are counted for the probability distribution. To keep it interesting, these diagrams will contain a few more fields than just the simple source and pins. An example diagram is:

```
|     O     |
|     ^     |
|    ^ /    |
|   ^ | ^   |
|  <^- =  v |
| ^ ^ ^ ^ ^ |

```

Furthermore, the marbles now each have a rotation direction. This direction is set by some fields and determines to which next field the marble moves in several other fields.

The following fields are defined:

* `O`: Source. Spawns marbles directly below it. The direction of these marbles is 50% left, 50% right. Each source produces the same amount of marbles.
* `U`: Sink. Any marbles which enter this field are removed from the bean machine.
* : Empty space. If a marble arrives at this field, it will move to the field below.
* `-`: Floor. If a marble arrives at this field, it will move to either the field to the left or the field on the right, depending on its current direction.
* `^`: Splitter. If a marble arrives at this field, it has a 50% of moving to the field to the right or the field to the left of the splitter. This also determines the direction of the marble.
* `v`: Join. If a marble arrives at this field, it will move to the field below.
* `/`: Slanted pad. If a marble arrives at this field, it will move to the field on the left of the pad, setting the direction of the marble.
* `\`: Same as the previous, but to the right.
* `|`: Reflector. If a marble arrives at this field, it will reverse the direction of the marble, and move the marble to the field to the right or the left, based on this reversed direction.
* `=`: Cannon. If a marble arrives at this field, it will move it to the right or the left in the current direction, until the marble encounters a field that is not , `-` or `O`.
* `<`: Same as the previous, but will always set the direction and move towards the left.
* `>`: Same as the previous, but to the right.

The following guarantees are given regarding the diagram.

* Each input row will have exactly the same length in fields.
* The leftmost and rightmost field of each row will always be a `|`.
* The diagram will not contain any possible paths through which marbles can get stuck in the machine for an indeterminate amount of iterations, like `\/` or `^^`.
* The diagram will only contain the above mentioned fields.
* There are one or more sources

### Result

Your task will be to generate an 16-line tall ASCII bar graph of the probability distribution in which the marbles exit the bottom side of the graph, scaled so the largest probability covers all 16 characters. So for the following problem:

```
|     O     |
|     ^     |
|    ^ ^    |
|   ^ ^ ^   |
|  ^ ^ ^ ^  |
| ^ ^ ^ ^ ^ |

```

Your program should produce the following solution (note that it should have the same width as the input program, including the pipes to the side:

```
     # #
     # #
     # #
     # #
     # #
     # #
     # #
     # #
   # # # #
   # # # #
   # # # #
   # # # #
   # # # #
   # # # #
 # # # # # #
 # # # # # #

```

### Examples

The following is an example that should test the functionality of all different field types:

```
|     O     O         |
|  O  ^ /  <^\\\      |
|    ^ >            ^ |
|   ^ ^ ^            =|
|  ^ ^ | ^    <^   O  |
| ^ > ^ | ^   O ^> v  |
||  ^U  ^  |  =    ^\ |
|  ^ ^ ^ ^U ^\ ---^   |
| = ^   ^     =    v  |

```

It should result in the following output:

```
                     #
                     #
                     #
                     #
                   # #
                   # #
                   # #
       # #         # #
       # #         # #
       # #         # #
       # #         # #
      ## #         # #
      ## # #       # #
   # ### # #       # #
 # # ### # #       # #
 # # ### # #       # #

```

### Rules

Both functions and full programs constitute valid answers for this challenge. You will receive the diagram as a newline-separated string, and you should return the output graph in the given format. Default input/output rules apply. While trailing and leading newlines are allowed in the output, each row should have exactly the same width as the input.

As to allow more creative solutions, it is only required that your program outputs the correct result more than 90% of the time for the same diagram. It is a probability simulation after all.

### Scoring

This is , so the lowest score in bytes wins.

# Answer
> 8 votes
# Python 3, ~~431~~ ~~429~~ 410 bytes

```
def t(a):e=enumerate;p=a.split("\n");o=[0]*len(p[0]);{m(i,j,p,o,1):m(i,j,p,o,-1)for i,r in e(p)for j,c in e(r)if"O"==c};[print("".join(" #"[round(16*r/max(o)+i)>15]for r in o))for i in range(16)]
def m(r,k,p,o,l,x=1):
 while r<len(p):
  c=p[r][k]
  if"^"==c:x/=2;m(r,k-l,p,o,l,x)
  if"U"==c:return
  if c in" vO":r+=1;continue
  l=[1,l,-1,l,-l,1][ord(c)%6];k-=l
  while";"<c<"?"and p[r][k]in" O-":k-=l
 o[k]+=x

```

Try it online!

This answer is a collaborative effort between Wheat Wizard and CensoredUsername. For reference, this is the ungolfed algorithm.

*-2 bytes from Mr. Xcoder*

*-19 bytes from CensoredUsername*

# Answer
> 4 votes
# Python 2, 731 bytes

```
i=raw_input
l=i()
c=[]
while l:c,l=c+[l],i()
p=[[0]*len(l)for l in c]+[[0]*max(map(len,c))]
S=lambda r,C,p:r>=0and C>=0and r<len(p)and C<len(p[r])
def U(r,C,P,D,N=0):
 if S(r,C,p):p[r][C]+=P
 if S(r,C,c):
	K=c[r][C]
	if K in' O':U(r+1-N,C+D*N,P,D,N)
	elif'v'==K:U(r+1,C,P,D)
	elif'-'==K:U(r,C+D,P,D,N)
	elif'^'==K:U(r,C-1,P/2,-1);U(r,C+1,P/2,1)
	elif'/'==K:U(r,C-1,P,-1)
	elif'\\'==K:U(r,C+1,P,1)
	elif'='==K:U(r,C+D,P,D,1)
	elif'>'==K:U(r,C+1,P,1,1)
	elif'<'==K:U(r,C-1,P,-1,1)
	elif'|'==K:U(r,C-D,P,-D)
for r in range(len(c)):
 for C in range(len(c[r])):
	if'O'==c[r][C]:U(r+1,C,1.,1);U(r+1,C,1.,-1)
p=p[-1][::-1]
s=16/max(p)
f=['#'*min(int(n*s),16)+' '*min(int(16-n*s),16)for n in p]
print('\n'.join(map(''.join,zip(*f)))[::-1])

```

Try it online!

-17 bytes thanks to caird coinheringaahing

-12 bytes thanks to Nathan Shiraini

-56 bytes by switching to mixed indentation (Python 2)

-28 thanks to CensoredUsername because the probabilities are normalized in the end, so it's not necessary that the end probabilities always add up to 1.

-7 bytes thanks to Calculator Feline by using a shorter ending `elif` statement.

-218 bytes by merging the two functions

# Answer
> 3 votes
# C, ~~569~~ ~~568~~ 556 Bytes

## Golfed

```
#define A s[1]
#define c(i,j,k) break;case i:x=j;y=k;
w,S,i,j,d,x,y,z;main(int*a,char**s){w=strchr(&A[1],'|')+2-A;a=calloc(w,4);for(;i++<'~~';j=0){for(;A[j];){if(A[z=j++]==79){d=rand()%2;x=4;y=7;z+=w;for(;z<strlen(A);){z+=x%3-1+(y%3-1)*w;switch(A[z]){case 85:goto e;c(32,x/3*(3+1),y/3*(3+1))c(45,d*2+3,7)c(94,(d=rand()%2)*2+3,7)c(118,4,8)c(47,3,7)d=0;c(92,5,7)d=1;c(124,(d=!d)*2+3,7)c(60,x,y)case 62:d=A[z]/2%2;case 61:x=d*8;y=4;}}a[z%w]++;e:;}}}for(i=-1;++i<w;S=a[i]>S?a[i]:S);for(j=17;j-->1;puts(""))for(i=0;i<w-1;printf("%c",a[i++]*16./S+0.6<j?32:35));}

```

## Ungolfed

```
//Variable Definitions
//direction - marbles current direction, 0 -> left, 1-> right
//arrwidth - width of array
//x - change in x of marble in base 3 - 0 -> Left, 1 -> stay, 2-> right
//y - change in y of marble in base 3 - 0 -> Up, 1 -> stay, 2-> Down
//z - position of marble
//i - iterator on runs of program
//j - iterator on string
//k - iterator on outputstring
//argc - array holding all buckets

#define c(i,j,k) break;case i:x=j;y=k;

arrwidth,scale,i,j,direction,x,y,z;

main(int *argc, char**argv){
  arrwidth=strchr(&A[1],'|')+2 - A; //get width
  argc=calloc(arrwidth,4);
  for(;i++<'~~';j=0){
    for(;A[j];){
      if(A[z=j++] == 79){ //if it finds an O, start sim
        direction=rand()%2;
        x=4;
        y=7;
        z+=arrwidth;
        for(;z<strlen(A);){
          z+=x%3-1 + (y%3-1)*arrwidth;
          switch (A[z]){
            case 85://marble dies dont record
              goto e;
            c(32,x/3*(3+1),y/3*(3+1)) //case ' '
            c(45,direction*2+3,7)    //case -
            c(94,(direction=rand()%2)*2+3,7)    //case ^
            c(118,4,8)    //case v
            c(47,3,7)    //case /
              direction=0;
            c(92,5,7)   //case '\'
              direction=1;
            c(124,(direction=!direction)*2+3,7)
            c(60,x,y)    //case <
            case 62:    //case >
              direction=A[z]/2%2;
            case 61:  //case =
              x=direction*8;
              y=4;
          }
        }
        argc[z%arrwidth]++;
        e:;
      }
    }
  }
  //get output answer in terms of '#'
  for(i=-1;++i<arrwidth;scale=argc[i]>scale?argc[i]:scale);
  for(j=17;j-->1;puts(""))
    for(i=0; i < arrwidth-1;printf("%c",argc[i++]*16./scale+0.6<j?32:35));
}

```

## Edits

Saved 12 bytes by changing my case macro.

## Notes

My code uses a system of base 3 integers to determine where the marble is headed and will be headed after (for cannons and stuff).

I tried so had to beat that python solution, I really did.

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


title: Draw an ASCII contour plot

text:
# Question
Title: Draw an ASCII contour plot
Consider the following 3x3 blocks which the marching squares algorithm would identify for every cell (with 0-based labeled ID):

```
0:
...
...
...

1:
...
...
\..

2:
...
...
../

3:
...
---
...

4:
..\
...
...

5:
/..
...
../

6:
.|.
.|.
.|.

7:
/..
...
...

8:
/..
...
...

9:
.|.
.|.
.|.

10:
..\
...
\..

11:
..\
...
...

12:
...
---
...

13:
...
...
../

14:
...
...
\..

15:
...
...
...

```

The goal of this challenge is given a 2D matrix of block ID's, draw the full contour plot by tiling these smaller cells together. Note that there are some repeated cases (ex.: 0 and 15 visually are the same)

## Input

Your program/function should take as input a 2D rectangular matrix of integers in the range `[0+a,15+a]` (where `a` is an arbitrary integer shift of your choice; this allows you to use zero-based indexing or 1-based indexing for the blocks). This may be from any source desired (stdin, function parameter, etc.).

## Output

Your program/function should output a single string representing the full contour plot. There should be no extra leading/trailing whitespace, but a single trailing newline is allowed. There should be no separation between adjacent blocks vertically or horizontally.

Note that you do not have to do any kind of special treatment for blocks which map to a "saddle"; just draw the block with the given ID as-is.

The output may be to any sink desired (stdout, return value, etc.)

## Examples

All examples below use 0-based block ID's.

```
case 1:

2 1
4 8

......
......
../\..
..\/..
......
......

case 2:

15 13 12 14 15
13 8 0 4 14
11 1 0 2 7
15 11 3 7 15

...............
......---......
...../...\.....
.../.......\...
...............
../.........\..
..\........./..
...............
...\......./...
.....\.../.....
......---......
...............

case 3:

12 12 12 8 4
0 0 0 0 2
0 0 0 2 7
0 2 3 7 15

........./....\
---------......
...............
...............
...............
............../
............/..
...............
.........../...
........./.....
......---......
...../.........

case 4:

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

............
.........---
...\..../...
..\/...|./..
.......|....
...../.|....
/...|...\..\
....|.......
....|.\.....
............
---.........
...../\.....

case 5:

0 0 0 0 6 15 15
0 0 0 0 6 15 15
0 0 0 0 6 15 15
0 0 0 2 7 15 15
0 0 2 5 14 15 15
0 2 5 8 4 12 14
0 4 8 0 0 0 6
0 0 0 0 0 0 4

.............|.......
.............|.......
.............|.......
.............|.......
.............|.......
.............|.......
.............|.......
.............|.......
.............|.......
............/........
.....................
.........../.........
........./...........
.....................
......../../\........
....../../....\......
...............---...
...../../.........\..
.....\/............|.
...................|.
...................|.
....................\
.....................
.....................

```

## Scoring

This is code golf; shortest code in bytes wins. Standard loopholes apply.

# Answer
> 2 votes
# Mathematica, ~~353~~ 326 bytes

```
s=Table[".",3,3];z=Reverse;l@0=l@15=s;y=s;y[[3,1]]="\\";l@1=l@14=y;y=s;y[[3,3]]="/";l@2=l@13=y;y=s;y[[2,All]]="-";l@3=l@12=y;y=l@4=l@11=z/@z@l@1;y[[3,1]]="\\";l@10=y;y=s;y[[All,2]]="|";l@6=l@9=y;y=l@7=l@8=z/@z@l@2;y[[3,3]]="/";l@5=y;StringReplace[ToString@Grid@Map[Column,Map[StringJoin,Map[l,#,{2}],{3}],{2}],{"\n\n"->"\n"}]&

```

**input**

> \[{{15, 13, 12, 14, 15}, {13, 8, 0, 4, 14}, {11, 1, 0, 2, 7}, {15, 11, 3, 7, 15}}\]

# Answer
> 2 votes
## Mathematica, 173 bytes

```
StringRiffle[ArrayFlatten[ReplacePart[Table[".",16,3,3],{{2|11|15,3,1}|{5|11|12,1,3}->"\\",{3|6|14,3,3}|{6|8|9,1,1}->"/",{4|13,2,_}->"-",{7|10,_,2}->"|"}][[#]]&/@#],"\n",""]&

```

Try it at the Wolfram sandbox!

The "`\n`" should be replaced by an actual newline. The input is 1-indexed — for example, the third test case becomes `{{13,13,13,9,5},{1,1,1,1,3},{1,1,1,3,8},{1,3,4,8,16}}`. The output is a string.

The idea is basically the same as Jenny\_mathy's answer — make the sixteen squares by taking a 3x3 grid of `"."`s and replacing some of the characters, then stitch the squares together — but using slightly shorter functions to do it. (Thanks to alephalpha for reminding me that `ArrayFlatten` exists!)

It's possible that this can be done in fewer bytes by making the squares cleverly instead of basically hardcoding them, but that would require much more effort…

# Answer
> 2 votes
## JavaScript (ES6), 195 bytes

```
a=>a.map((r,y)=>r.map((i,x)=>[...s='76843210_'].map((_,j)=>(o[Y=y*3+j/3|0]=o[Y]||[])[x*3+j%3]='.\\/-\\/|/\\'[[0,64,256,56,4,257,146,1,68][k=s[i-8]||i]>>j&1&&k])),o=[])&&o.map(r=>r.join``).join`
`

```

### Test cases

```
let f =

a=>a.map((r,y)=>r.map((i,x)=>[...s='76843210_'].map((_,j)=>(o[Y=y*3+j/3|0]=o[Y]||[])[x*3+j%3]='.\\/-\\/|/\\'[[0,64,256,56,4,257,146,1,68][k=s[i-8]||i]>>j&1&&k])),o=[])&&o.map(r=>r.join``).join`
`

console.log(f([
  [ 2, 1 ],
  [ 4, 8 ]
]));

console.log(f([
  [ 15, 13, 12, 14, 15 ],
  [ 13,  8,  0,  4, 14 ],
  [ 11,  1,  0,  2,  7 ],
  [ 15, 11,  3,  7, 15 ]
]));

console.log(f([
  [ 12, 12, 12,  8,  4 ],
  [  0,  0,  0,  0,  2 ],
  [  0,  0,  0,  2,  7 ],
  [  0,  2,  3,  7, 15 ]
]));

console.log(f([
  [  0,  1,  2,  3 ],
  [  4,  5,  6,  7 ],
  [  8,  9, 10, 11 ],
  [ 12, 13, 14, 15 ]
]));

console.log(f([
  [  0,  0,  0,  0,  6, 15, 15 ],
  [  0,  0,  0,  0,  6, 15, 15 ],
  [  0,  0,  0,  0,  6, 15, 15 ],
  [  0,  0,  0,  2,  7, 15, 15 ],
  [  0,  0,  2,  5, 14, 15, 15 ],
  [  0,  2,  5,  8,  4, 12, 14 ],
  [  0,  4,  8,  0,  0,  0,  6 ],
  [  0,  0,  0,  0,  0,  0,  4 ]
]));
```

# Answer
> 2 votes
# Retina, 165 bytes

```
T`d`L`1\d
 |\bB\B

.+
X$&¶Y$&¶Z$&
%{`[XYZ]$

([XYZ])[69]
.|.$1
X[^4-B]
...X
X[4AB]
..\X
X[578]
/..X
Y[^369C]
...Y
Y[3C]
---Y
Z[03478BCF]
...Z
Z[1AE]
\..Z
Z[25D]
../Z

```

Try it online! Link includes second example. Explanation: The first two stages convert from decimal to hexadecimal, allowing the spaces to be deleted. The third stage then triplicates each line, giving each new line a separate marker. These markers then traverse the hex digits, converting them into the contour plot as they go, until they reach the end of the line, at which point they are deleted.

# Answer
> 1 votes
# Python 2, 247 bytes

```
J='...'
print'\n'.join(map(''.join,sum([[sum([f[i*3:][:3]for i in j],[])for f in map(list,[J*4+'..\\/...|./../...|...\\..\\'+J*4,J*3+'---.......|........|.......---'+J*3,'...\\..../......../.|........|.\\'+J*3+'./\\.....'])]for j in input()],[])))

```

Try it online!

-1 byte thanks to LeakyNun

# Answer
> 1 votes
# SOGL V0.12, ~~106~~ 89 bytes

```
žj}² ³
ē0=?²
{ā;{"⁰9═‼pnk№Ο|╚φ;“2─6nwEX .9*3n²Xƨ.ƨ-¹╬-}²X"č7_#‘3n}² /33³\13³\31³/11žj}┼}O

```

Try it Here! (that has an extra byte  for ease of input. This otherwise would expect the array already on stack)

# Answer
> 1 votes
# Python 2, ~~196~~ ~~191~~ ~~181~~ 176 bytes

Try it online!

A function which takes an array of arrays of ints and returns a string:

```
J=''.join;N='\n'.join
f=lambda I:N(N(J(J('\/|-.'[C/16-2]*(C%16)for C in map(ord,'o!j1cSe!f1g1aAbAbAa1h1iAbAbAc!c!d!iSk1f!k'))[c*9+3*j:][:3]for c in r)for j in[0,1,2])for r in I)

```

EDIT: saved 5 bytes by assigning J,N; another 10 bytes because I forgot the input is already assumed to be an array of arrays of ints; and then another 5 bytes saved by smarter slicing...

The concatenated string of all 16 3x3 cells (144 bytes, omitting linebreaks) is run-length-encoded to the 41 byte string:

`o!j1cSe!f1g1aAbAbAa1h1iAbAbAc!c!d!iSk1f!k`

where each RLE element `(cellType, length)` is encoded to the character `chr(32+16*cellType+length)` (it is handy that the maximum run is 15; and that `ord(' ')==32` is divisble by 16). When decoding, we take `'\/|-.'[cellType]` as the printable character.

Nothing particularly clever after that...

# Answer
> 1 votes
# 05AB1E, 61 bytes

```
v•2mßklJFΘõÿ|åU‚ιØØ•6B5¡∊¶¡110bTǝ.BJ3ô3ôyèøJ»}»4ÝJð«"\./-|."‡

```

Try it online!

---

The first half of the pattern can be compressed as:

```
5
11111105
1111111125
1113335
1105
2111111125
141141145
25

```

The second half would need to be:

```
25
141141145
11011105
1105
1113335
1111111125
11111105
5

```

We can just vertically mirror the first half, and insert `binary 110 (1101110)` in for the `2111111125`.

---

Next we take this pattern and split on fives, then pad it with ones:

```
1 = 111111111
2 = 111111011
3 = 111111112
4 = 111333111
5 = 110111111
6 = 211111112
7 = 141141141
8 = 211111111
9 = 141141141
A = 110111011
B = 110111111
C = 111333111
D = 111111112
E = 111111111

```

Now we have our building blocks, the last parts just replace the matrix entries with the appropriate building blocks, zip together the rows and print to the user with replaced symbols:

```
0 = .........
1 = ......\..
2 = ......../
3 = ...---...
4 = ..\......
5 = /......./
6 = .|..|..|.
7 = /........
8 = /........
9 = .|..|..|.
A = ..\...\..
B = ..\......
C = ...---...
D = ......../
E = .........

```

Can post formal operation explanation if anyone wants it, thanks.

# Answer
> 1 votes
# Jelly, 64 bytes

```
“¡_ḟ5⁸ṫ⁺Y"⁷ƘzƬɼ¥@TR/ṖQ½3yİ>ẎḄT¥⁹iḟQ¬Ɠl¹µŒ’ṃ“/-\|.”s3s3ṙ9ị@³ZY$€Y

```

Try it online!

This uses a naive compression and could probably save many bytes with run-length encoding.

**How it Works**

```
“¡_ḟ5⁸ṫ⁺Y"⁷ƘzƬɼ¥@TR/ṖQ½3yİ>ẎḄT¥⁹iḟQ¬Ɠl¹µŒ’ṃ“/-\|.”s3s3ṙ9ị@³ZY$€Y
“¡_ḟ5⁸ṫ⁺Y"⁷ƘzƬɼ¥@TR/ṖQ½3yİ>ẎḄT¥⁹iḟQ¬Ɠl¹µŒ’ encodes the integer 4591777158889232952973696500124538798606476761349931038636020730336909822188496590423586252520
ṃ“/-\|.”                   - convert to base 5 and index into the string to get "/......../.........|..|..|...\...\....\.........---.........../......\.................\........../...---.....\....../......./.|..|..|."
        s3s3               - split every 9 characters into a 3x3 square submatrix
            ṙ9             - rotate left by 9 to line up the submatrix for 1 with index 1
              ị@³          - index the input into this
                 ZY$€Y     - format

```

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


title: Regular expression parser

text:
# Question
Title: Regular expression parser
This task is a classic programming task: Implement a regular expression parser. That is, write a program or function which takes a string describing a regular expression and a candidate string, and test whether the complete candidate string matches the regular expression. You may assume that the regular expression passed is valid.

If your programming language offers regular expression matching or string parsing, you are not allowed to use that. Also you are not allowed to use libraries other than the standard library of your programming language. Also forbidden is to access an external tool to do the work (e.g. accessing a web server, or calling another executable). In addition, use of reflection or any other functionality that allows the program to access its own source code, the names of individual identifiers or similar information is explicitly forbidden to prevent gaming the scoring rules (thanks to ais523 in the comments for making me aware of the latter possibility).

This is an atomic code golf contest, it's not the character count that has to be minimized, but a modified token count (for details, see below).

## Input

The regular expression is not enclosed in slashes (`/`), any slashes appearing in the regular expression string are part of the regular expression itself (that is, the string `/.*/` denotes not the regular expression `.*`, but the regular expression `/.*/` which will match the string `/abc/`, but *not* the string `abc`).

Both the regular expression string and the candidate string will consist solely of ASCII characters in the range 32 (space) to 126 (tilde).

### The regular expression syntax

Your program only needs to parse the following minimal regular expression syntax:

* Anything except the letters `.`, `*`, `|`, `(`, `)` and `\` matches literally.
* A backslash (`\`) followed by any of the above characters literally matches the second character.
* A dot (`.`) matches any character.
* The star (`*`) matches zero or more consecutive strings each matching the regular expression preceding it. It cannot appear at the beginning.
* The pipe (`|`) matches either the regular expression before it, or the regular expression following it.
* Parentheses (`(`, `)`) themselves don't match anything, but are used to group expressions (e.g. `ab*` matches `abbbbb`, while `(ab)*` matches `abababab`).

## Output

Your program or function must give one of two results, one indicating that the *complete* candidate string matches, one indicating that it doesn't. How the output is given (function return variable, global variable setting, text output, program status code, ...) is up to you (and the capabilities of your chosen programming language). Explain how the output is to be interpreted.

## Scoring

Of course, this being a code golf, the minimal score wins. The score is calculated as follows:

* Start with score 0.
* Comments and whitespace characters that are not part of a token are ignored.

> **Rationale:** I don't want to penalize pretty formatting. The token exception covers both spaces inside string and character constants, and special cases like the Whitespace language where each single whitespace character constitutes a token (so writing a program in Whitespace won't give you a score of 0).

* For any statement/declaration/etc. which makes available a standard library component to the code (like `#include` in C, `use` in Perl or `import` in Java), add 5 point per imported standard library package.

> **Rationale:** I don't want to make the scoring dependent on how verbose the import syntax of a language is. Also, there shall be a slight (but not too strong) discourage of using library components (direct code is preferred, unless the library makes a big difference; however note the restrictions on library use outlines above). The "per standard library package" part is so that you cannot reduce your point by combining several imports by one (e.g. in Turbo Pascal, you could write `uses dos, crt;` instead of `uses dos; uses crt;`. With the rule as given, both would add 10 points. (Of course, both `dos` and `crt` would be pointless for the given task.)

* For any string, add one more than the number of characters in the string (that is, the empty string gets 1 point, a one character string gets 2 points, etc.). If the language has single-token literals for other complex types (like lists, dictionaries, etc.), it is one point per character in the literal. (thanks to ais523 in the comments for telling me about such complex literals).

> **Rationale:** This is mainly to prevent tricks like `eval("long program code")` which is four tokens. With this rule, doing such a trick actually penalizes your code, because you're back to character counting instead of token counting.

* For any number, add as many points as the minimal number of bytes needed to represent the number as either signed or unsigned two's-complement number. That is, numbers from -128 to 255 (including both values) get 1 point, otherwise numbers in the range -32768 to 65535 get 2 points, otherwise numbers in the range -8388608 to 16777215 get 3 points, and so on.

> **Rationale:** This is to prevent similar tricks in languages supporting arbitrary large numbers, where the whole program might be encoded in a number that is then reinterpreted as a string and passed to `eval` or an equivalent function.

* Any token not covered in the list above gives 1 point.

> **Rationale:** This is to avoid penalizing verbose languages (e.g. Pascal with `begin`/`end` vs. C with `{`/`}`), and especially to avoid giving esoteric languages (Golfscript!) an advantage just for having one-character tokens. Also, it allows meaningful variable names without being penalized.

Note: This challenge was posted in the sandbox

# Answer
> 5 votes
# Python 3, 445\* points

This is a fairly straightforward approach: it uses a basic recursive descent parser, and a regex engine implemented using Brzozowski derivatives (which I just learned about, and which I think are super elegant); it takes two strings as input via STDIN – first a string representing the regex in question, then a string containing the text to match, and prints `True` to STDOUT if the regex matches and `False` if it doesn't.

```
class Nil:nullable,derive = False,lambda *self: Nil
class Empty(Nil):nullable = True
class And:
    def __init__(self, first, second=None):self.first,self.second = first,second
    nullable = property(lambda self: self.first.nullable and self.second.nullable)
    def derive(self, c):
        dxy = And(self.first.derive(c), self.second)
        return Or(dxy, self.second.derive(c)) if self.first.nullable else dxy
class Or(And):nullable,derive = property(lambda self: self.first.nullable or self.second.nullable),lambda self, c: Or(self.first.derive(c), self.second.derive(c))
class Star(And):nullable,derive = True,lambda self, c: And(self.first, Star(self.first)).derive(c)
class Plus(Star):nullable = False
class Char(Plus):derive = lambda self, c: Empty if self.first in 'µ'+c else Nil
expr = input()
index = len(expr)
peek = lambda: index and expr[-index] or ''
def advance():
    global index
    item = peek()
    index -= True
    return item
def regex():
    factor = Empty
    while peek() not in ')|':
        current = advance()
        base = Char(current)
        if current == '(':
            base = regex()
            advance()
        elif current == '\\':base = Char(advance())
        elif current == '.':base = Char('µ')
        while '' < peek() in '*+':
            base = (Star if peek() == '*' else Plus)(base)
            advance()
        factor = And(factor, base)
    return Or(factor, regex()) if peek() == '|' == advance() else factor
derivative = regex()
for c in input(): derivative = derivative.derive(c)
print(derivative.nullable)

```

Try it online!

---

***** I'll be honest: I'm not totally sure if I've scored this correctly, because the scoring rules for this submission are at once both rather complex and also imprecise. Their goals are certainly admirable, but I think the range of possible situations they try to cover is too vast.

As an example of what I mean: "Tokens" aren't necessarily a consistently defined concept in many programming languages, and this challenge doesn't clarify. In Python, for instance, they're implementation-defined.

Similarly, and among other such things, the challenge doesn't count whitespace against a score unless it's part of a token, but CPython generates tokens for certain non-meaningful whitespace, which leads to a contradiction with the scoring rule's stated intent of "avoiding penalizing pretty formatting."

Consequently, this could actually be anywhere from 407-533 points.

---
Tags: parsing, regular-expression, atomic-code-golf
---


title: Sinusoidal ASCII-art animated text

text:
# Question
Title: Sinusoidal ASCII-art animated text
I somewhat miss those old demos showing the capabilities of computers when they were called x86 instead of i3, i5 and i7. One of the first I watched in my 386 was the Unreal demo from Future Crew that is now celebrating its 25th anniversary. At minute 0:43 the first part of the demo starts and we see a scrolling text following a sinusoidal path. Let's try to imitate that effect in ASCII art!

### The challenge

Given this path:

```
***                                ***
   ***                          ***
      **                      **
        *                    *
         *                  *
         *                  *
          *                *
           **            **
             ***      ***
                ******

```

and an input text, draw the text following that path, like this:

```
Thi                                Golf!
   s i                          de       Yay
      s                       Co            !
        P
         r                  d
         o                  n
          g                a
           ra            s
             mmi      zle
                ng Puz

```

Note that the spaces count as characters in the path, and that the path repeats itself if the text is longer than the sample.

### The animation part

Once you have drawn the text, wait for 100 ms (to create an animation of around 10 fps) and draw the text again but starting from the next position of the path. So, for frame `#n`, calculate `n modulo 40` and start drawing in the following position of the path with the text always aligned to the left of the canvas:

```
***                                ***
|  ***                          ***  |
|     **                      **     |
|       *                    *       |
|        *                  *        |
|        *                  *        |
|         *                *         |
|          **            **          |
|            ***      ***            |
|               ******               |
Position 0                 Position 39

```

So for frame 10 we will have:

```
                           and Co
                        es       de
                      zl            Go
                     z                l
                    u                  f
T                   P                  !
 h
  is             ng                       Ya
     is       mmi                           y!
        Progra

```

### Notes

* Input will be a single `string` (or `char` array, whatever) with the text to animate, and will always have at least 1 character.
* Valid characters to animate are those in the printable ASCII set.
* The path to follow will be exactly as given.
* Text will always be aligned to the left of the canvas, so the effect will be the text waving like a flag, with no text displacement. And by canvas I mean screen or whatever you will use to show the text. ;-)
* Frames must be clear of any characters/pixels from previous frames unless the character/pixel is the same in both frames.
* The speed of the animation does not matter as long as it runs smoothly or as fast as your device can (we can set a minimum of 5 fps, but this is not a requirement). Just adjust the speed to make it fluid and do not worry if the waiting times are not exactly the same.
* The animation will loop endlessly.

This is , so may the shortest program or function capable of animating the text win!

# Answer
> 9 votes
## HTML + ES6, ~~241~~ ~~244~~ 237 bytes

Breakdown:

* HTML: 16 bytes
* JS function: 221 bytes

```
let f =

s=>setInterval(_=>o.innerHTML=[...s].map((c,i)=>([j,y]=[...Array(40)].map((_,k)=>[j=k%20,y,y+=77732>>j&1?k<20||-1:0],y=0)[(i+p)%40],a[y]=a[y]||[...s].fill` `)[x]=(x+=j!=9,c),x=0,a=[],p++)&&a.map(r=>r.join``).join`
`,p=30)

f("This is Programming Puzzles and Code Golf! Yay!")
```

```
<pre id=o></pre>
```

### How?

**Building the path**

The following code builds the path:

```
[...Array(40)].map((_, k) =>
  [
    j = k % 20,
    y,
    y += 77732 >> j & 1 ? k < 20 || -1 : 0
  ],
  y = 0
)

```

This gives an array of arrays `[j, y, z]` where ***j*** is the position modulo 20, ***y*** is the y-coordinate at this position and ***z*** is not used later (it just happens to be computed here to save some bytes).

Because the path is symmetric, we only need to encode the 20 first positions. We do that by using a binary number where each `1` bit means that ***y*** must be updated (+1 for the first half, -1 for the second half).

```
001
   001
      01
        1
         1
         1
          1
           01
             001
                000

```

With the first position being mapped to the least significant bit, this gives:

```
00010010111110100100 as binary = 77732 as decimal

```

Because this binary number is itself also symmetric, we can read it in the same order for the 2nd half.

Hence the formula:

```
y += (77732 >> j) & 1 ? (k < 20 ? 1 : -1) : 0

```

which can also be written as:

```
y += (77732 >> j) & 1 ? k < 20 || -1 : 0

```

where ***k*** is the position and ***j*** is the position modulo 20.

Updating ***x*** is much easier: we just have one special case to detect by comparing the position modulo 20 with 9.

**Drawing the text**

In the following code, the path building code described above has been replaced by a `path` variable for readability.

```
s => setInterval(                       // set a periodic timer:
  _ =>                                  //   with an anonymous callback
    o.innerHTML =                       //   which updates the content of 'o'
      [...s].map((c, i) => (            //   for each character c of the string s
          [j, y] = path[(i + p) % 40],  //     retrieve j and y from the path
          a[y] = a[y] || [...s].fill` ` //     initialize a[y] if it's undefined
        )[x] = (x += j! = 9, c),        //     update a[y][x] / update x
        x = 0,                          //     initialize x
        a = [],                         //     initialize a[]
        p++                             //     increment the phase
      ) &&                              //   end of map()
      a.map(r => r.join``).join`\n`,    //   join everything together
  p = 30                                //   initial phase = interval period = 30
)                                       // end of timer definition

```

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


# Question
Title: Find a number which generates all the integers mod q
Consider the integers modulo `q` where `q` is prime, a generator is any integer `1 < x < q` so that `x^1, x^2, ..., x^(q-1)` covers all `q-1` of the integers between `1` and `q-1`. For example, consider the integers modulo 7 (which we write as `Z_7`). Then `3, 3^2 mod 7 = 2, 3^3 = 27 mod 7 = 6, 3^4 = 81 mod 7 = 4, 3^5 = 243 mod 7 = 5, 3^6 = 729 mod 7 = 1` covers all the values `3, 2, 6, 4, 5, 1` covers all the integers `1..6` as required.

The task is to write code that takes an input `n` and outputs a generator for `Z_n`. You cannot use any builtin or library that does this for you of course.

The only restriction on the performance of your code is that you must have tested it to completion with `n = 4257452468389`.

Note that `2^n` means `2` to the power of `n`. That is `^` represents exponentiation.

# Answer
# Pyth, ~~16~~ 15 bytes

```
f-1m.^T/tQdQPtQ

```

Test suite

If p is the input, we know that g^(p-1) = 1 mod p, so we just need to check that g^a != 1 mod p for any smaller a. But a must be a factor of p-1 for that to be possible, and any multiple of an a with that property will also have that property, so we only need to check that g^((p-1)/q) != 1 mod p for all prime factors q of p-1. So, we check all integers g in increasing order until we find one that works.

Explanation:

```
f-1m.^T/tQdQPtQ
f                  Return the first value T such that the following is truthy:
            PtQ    Take the prime factorization of the input - 1.
   m               Map those prime factors to
       /tQd        Take the input - 1 divided by the factor
    .^T    Q       Raise T to that exponent mod input,
                   performed as modular exponentiation, for performance.
 -1                Check that 1 is not found among the results.

```
> 14 votes

# Answer
# Mathematica, 52 bytes

Inspired by isaacg's answer.

```
1//.i_/;PowerMod[i,Divisors[#-1],#]~Count~1!=1:>i+1&

```
> 5 votes

---
Tags: code-golf, math, number-theory, restricted-time
---