title: Operations of order

text:
# Question
Title: Operations of order
## Introduction

There comes a point in childhood when you think you've mastered adding and multiplying, then someone comes along and informs you that:

a * b + c = (a * b) + c != a * (b + c),

and that it wasn't as simple or linear a process as you were earlier taught. You learn that there exists something called the order of operations. This is a very important way of keeping some level of consistency and in expressions, without having parentheses getting in the way of everything.

## Generic storyline

One day, you wake up to the sound of panic in the streets. An extremist group under the name "*The 2560*" (Short for "Organisation Against the Order of Operations", with a dorky hex-ish twist) have used their evil methods to take control over all of the nuclear weapons in the world. They are holding the whole planet hostage, and they have a simple demand: reverse the accepted order of operations or face eradication (parentheses are to maintain their priority). The new system is called PSADME (parentheses, subtraction/addition, division/multiplication, exponents), and expressions evaluate right-to-left:

```
a - b - c = a - (b - c) = a + c - b

```

Days pass, and the transition is in progress. Whilst mathematicians and physicists are all busy rewriting their equations, the computer scientists are faced with the task of changing the fashion in which mathematical expressions are interpreted by computers. You belong to a secret rebel programming group which aims to cause as much torment for the new global overlords - and, by chance, you are randomly selected by *The 2560* and tasked to produce the benchmark calculation program.

## Your mission

Write a program (or function) which takes a (numerical) mathematical expression as input, calculates the expression using **PSADME** as the order of operations and outputs the result. Expressions should evaluate right-to-left, so $$1 - 3 + 4 = 1 - 7 = -6.$$

For simplicity, all numbers provided will be integers, and the calculations will produce integer outcomes.

## Rules and scoring

* The program should accept input up to 128 characters in length - if your language/platform has a lower maximum input length, that is an acceptable excuse.
* Standard loopholes are forbidden.
* The winning code will be chosen on 18th November (4 weeks from this post date).
* Feel free to post code that would not be considered golf-worthy. This is about fun. If you have an interesting way of doing this but can't golf it yourself (or by the nature of your method), you can post it anyway.

As per usual, the winning code is the one with least number of bytes, with some entertainment-value bonuses:

* **-5** for avoiding any use of the characters in the provided expression: **+**,**-**,**(**,**)**,**^**,*****,**/**
* **-5** for making the calculations take more than 5 minutes (but no more than 10 minutes) to calculate on a standard computer, without the method being obvious (using the clock or unnecessary loops); The aim is to convince the new overlords that you are not *trying* to disrupt their calculations of doom.
* **-(5+N)** for a direct offensive message (of length N, not including leading/trailing whitespace) about the members of The 2560 to be written in plain sight within your code, with some ridiculous explanation as to why it needs to be there. If it is removed, the code **must not** function correctly. Yes, free points for entertainment value.

## Examples and explanations

```
[program] 2 - 2 - 2
2

```

2 - (2 - 2) = 2

```
[program] (2 + 2 * 3 + 3) / 3 + 3
4

```

(4 * 6)/(3 + 3) = 4

```
[program] 3 + 2 + 1 ^ 3
216

```

(3 + 2 + 1)^3 = 216

```
[program] -5^2
25

```

(-5)^2 = 25

```
[program] 32 / 8 * 3 - 1
2

```

32 / (8 * (3 - 1)) = 32 / 16 = 2

# Answer
> 9 votes
# Haskell, 134 bytes

```
import qualified Prelude as P
infixl 6 ^
(^)=(P.^)
infixr 8 +
(+)=(P.+)
infixr 8 -
(-)=(P.-)
infixr 7 /
(/)=P.div
infixr 7 *
(*)=(P.*)

```

Redefining the math operators with new fixities and priorities. Now:

```
*Main> 32 / 8 * 3 - 1
2

```

# Answer
> 2 votes
# GNU sed -r with exec extension, 398

```
s@ *\^ *@ ** @
:
s@\((-?[0-9]+)\)@\1@
t
s@(-?[0-9]+ - )+(-?[0-9]+ - -?[0-9]+)@\1(\2)@
t
s@(.*(^| |\())(-?[0-9]+ [-+] -?[0-9]+)(.*)@echo '\1'$((\3))'\4'@e
t
s@(-?[0-9]+ / )+(-?[0-9]+ / -?[0-9]+)@\1(\2)@
t
s@(.*(^| |\())(-?[0-9]+ [*/] -?[0-9]+)(.*)@echo '\1'$((\3))'\4'@e
t
s@(-?[0-9]+ \*\* )+(-?[0-9]+ \*\* -?[0-9]+)@\1(\2)@
t
s@(.*(^| |\())(-?[0-9]+ \*\* -?[0-9]+)(.*)@bash -c 'echo \1$[\3]\4'@e
t

```

Not especially short, but gets the job done.

sed is OK for parsing out the precedence but doesn't do arithmetic. So we use the GNU sed exec extension to the `s` command to outsource the necessary arithmetic to the shell.

For now assumes all operators, with the exception of `^` have exactly one space in front and behind.

### Test output:

```
$ cat psadme.txt
2 - 2 - 2
(2 + 2 * 3 + 3) / 3 + 3
3 + 2 + 1 ^ 3
-5^2
32 / 8 * 3 - 1
$ sed -rf psadme.sed psadme.txt
2
4
216
25
2
$

```

# Answer
> 1 votes
# JavaScript (ES6) 287 ~~300~~

**Edit** Bug fixed (just a typo, 6 should have been 4) - Added a complete explanation at the end of the snippet

**Edit 2** Found some improvement working on another challenge

Yet another porting of the same parser with just some minimal difference. (compare with this)

```
f=(x,W=[],Q=['('],z=1,h=p=>'+-*/^^))('.indexOf(p)>>1,C=n=>{for(;h(q=Q.pop())<h(n);W.push(q=='^'?Math.pow(a,b):eval(`a${q}b`)))a=W.pop(b=W.pop());z&&Q.push(q,n)})=>((x+')').replace(/\d+|\S/g,t=>t>'('?t>'('?~h(t)?z&&t=='-'?z=-z:C(t,z=1):(W.push(z*t),z=0):C(t,z=0):(Q.push(t),z=1)),W.pop())

// More readable
U=(x,W=[],Q=['('],z=1,
  h=p=>'+-*/^^))('.indexOf(p)>>1,
  C=n=>{
    for(;h(q=Q.pop())<h(n);
        W.push(q=='^'?Math.pow(a,b):eval(`a${q}b`)))
      a=W.pop(b=W.pop());
    z&&Q.push(q,n)
  }
)=>(
  (x+')')
  .replace(/\d+|\S/g,t=>
       t>'('
       ?t>'('
       ?~h(t)
       ?z&&t=='-'?z=-z:C(t,z=1)
       :(W.push(z*t),z=0)
       :C(t,z=0)
       :(Q.push(t),z=1)
  ),
  W.pop()
)

// TEST
console.log=(...x)=>O.innerHTML+=x.join` `+'\n'

console.log(f('1 - 3 + 4')) // -6
console.log(f('2-2-2')) // 2
console.log(f('(2 + 2 * 3 + 3) / 3 + 3')) // 4
console.log(f('3 + 2 + 1 ^ 3')) // 216
console.log(f('-5^2')) // 25
console.log(f('32 / 8 * 3 - 1')) // 2

// Explained
X=(x,W=[],Q=['('],z=1,
  h=p=> // operator priority '+-:1, */:3, ^:5, ):7, (:9. If an operand then -1
     '+-*/^^))('.indexOf(p)>>1,
  C=n=>{ // Evaluate operators present on stack if they have upper priority, then push new operator on stack
    //console.log('Operand '+n)
    while( h(q = Q.pop()) < h(n) ) // pop operator from op stack and compare priority with current
    {
      // Pop operands from stack and push result
      b = W.pop();
      a = W.pop();
      r = q=='^' ? Math.pow(a,b) : eval('a'+q+'b')
      // console.log('Evaluate '+a+q+b+'='+r)
      W.push(r);
    }
    // if z == 0 do nothing, because the current operands are '(' and ')' that must be discarded
    // else Push again the last operator popped and the current one
    z && Q.push(q, n) //
  }
)=>(
  (x+')')
  .replace(/[\d.]+|\S/g,t=> {
    //console.log('Q:'+Q,'W:'+W,'T:'+t,'U:'+h(t),'Z:'+z), // display status
    if (t == '(')
    { // open parenthesis
      z = 1
      Q.push(t) // push a operator, its the highest priority
    }
    else if (t == ')')
    { //close parenthesis
      z = 0
      C(t)
    }
    else if (h(t) < 0)
    { // operand
      W.push(z*t) // push operand with right sign
      z = 0 // set z to 0 to mark that we just pushed an operand, so next '-' (if present) is a binary operator
    }
    else
    { // operator
      if (z && t=='-') // the minus is an unary operator (the only unary operator allowed is '-', '+' will not work)
        z =-z // change the sign
      else
        z = 1, // no unary minus
        C(t)
    }
  }),
  W.pop() // return the value at top of operand stack
)
```

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

---
Tags: code-golf
---


# Question
Title: Solving less-than inequalities with positive integers
Write a program or function that takes in a nonempty list of mathematical inequalities that use the less than operator (`<`). Each line in the list will have the form

```
[variable] < [variable]

```

where a `[variable]` may be any nonempty string of lowercase a-z characters. As in normal math and programming, variables with the same name are identical.

If a **positive integer** can be assigned to each variable such that **all** the inequalities are satisfied, then print or return a list of the variables with such an assignment. Each line in this list should have the form

```
[variable] = [positive integer]

```

and all variables must occur exactly once in any order.

Note that there may be many possible positive integer solutions to the set of inequalities. Any one of them is valid output.

If there are no solutions to the inequalities, then either don't output anything or output a falsy value (it's up to you).

**The shortest code in bytes wins.**

## Examples

If the input were

```
mouse < cat
mouse < dog

```

then all of these would be valid outputs:

```
mouse = 1
cat = 2
dog = 2
```

```
mouse = 37
cat = 194
dog = 204
```

```
mouse = 2
cat = 2000000004
dog = 3
```

If the input were

```
rickon < bran
bran < arya
arya < sansa
sansa < robb
robb < rickon

```

then no assignment is possible because it boils down to `rickon < rickon`, so there either is no output or a falsy output.

**More examples with solutions:**

```
x < y

x = 90
y = 91

---

p < q
p < q

p = 1
q = 2

---

q < p
q < p

p = 2
q = 1

---

abcdefghijklmnopqrstuvwxyz < abcdefghijklmnopqrstuvwxyzz

abcdefghijklmnopqrstuvwxyz = 123456789
abcdefghijklmnopqrstuvwxyzz = 1234567890

---

pot < spot
pot < spot
pot < spots

pot = 5
spot = 7
spots = 6

---

d < a
d < b
d < c
d < e

d = 1
a = 4
b = 4
c = 5
e = 4

---

aa < aaaaa
a < aa
aaa < aaaa
aa < aaaa
a < aaa
aaaa < aaaaa
aaa < aaaaa
a < aaaaa

aaaa = 4
aa = 2
aaaaa = 5
a = 1
aaa = 3

---

frog < toad
frog < toaster
toad < llama
llama < hippo
raccoon < science
science < toast
toaster < toad
tuna < salmon
hippo < science
toasted < toast

raccoon = 1
frog = 2
toaster = 3
toasted = 4
toad = 5
llama = 6
hippo = 7
science = 8
toast = 9
tuna = 10
salmon = 11

```

**More examples with no solutions:** (separated by empty lines)

```
z < z

ps < ps
ps < ps

q < p
p < q

p < q
q < p

a < b
b < c
c < a

d < a
d < b
d < c
d < d

abcdefghijklmnopqrstuvwxyz < abcdefghijklmnopqrstuvwxyz

bolero < minuet
minuet < bolero

aa < aaaaa
a < aa
aaa < aaaa
aa < aaaa
aaaaa < aaaa
a < aaa
aaaa < aaaaa
aaa < aaaaa
a < aaaaa

g < c
a < g
b < a
c < a

g < b
a < g
b < a
c < a

g < b
a < g
b < a
c < b

g < c
a < g
b < a
c < b

geobits < geoborts
geobrits < geoborts
geology < geobits
geoborts < geology

```

# Answer
# Pyth, 39 bytes

```
V>1f.A<MxMLTN.pS{s=Nm%2cd).zVNjd[H\==hZ

```

Try it online: Demonstration

Brute-forces through all possible permutations (and interpret them as sortings), check if they match the inequalities, and assign them the values `1, 2, ...., n`.

### Explanation

```
f.A<MxMLTN.pS{s=Nm%2cd).z
                 m     .z  map each input line d to:
                    cd)       split d by spaces
                  %2          and remove the second element
               =N          save this list of pairs to N
              s            combine these pairs to a big list of variable names
             {             set (remove duplicates)
          .pS              generate all permutations
f                          filter for permutations T, which satisfy:
     xMLTN                    replace each variable in N by their index in T
 .A<M                         check if each pair is ascending

V>1...VNjd[H\==hZ          implicit: Z = 0
 >1                        remove all but the last filtered permutation (if any)
V                          for each permutation N in ^ (runs zero times or once):
      VN                      for each variable H in N:
          [                      generate a list containing:
           H                        H
            \=                      "="
              =hZ                   Z incremented by 1 (and update Z)
        jd                       join this list by spaces and print

```
> 4 votes

# Answer
## CJam (53 52 49 bytes)

```
qS-N/'<f/:A:|e!{A{1$1$&=!},!*},:ee{()" = "\N}f%1<

```

Online demo

This brute-forces all permutations of the distinct tokens, filtering for those assignments of the numbers `0` to `n-1` which obey all of the constraints, and then formats them, incrementing the numbers, and presents the first one. This is certain to find a solution if there is one, because it's essentially a topological sort.

Thanks to Reto Koradi for 3 chars and Martin Büttner for 1.
> 3 votes

# Answer
# Mathematica, 83 bytes

```
Quiet@Check[Equal@@@FindInstance[Join[#,#>0&/@(v=Sequence@@@#)],v,Integers][[1]],]&

```

Takes input as a list of inequalities. Either outputs a list of assignments or `Null` if it is impossible.
> 2 votes

---
Tags: code-golf, math
---


# Question
Title: A calculator as a list of numbers and operators
Your task is to take a list of arguments that are either integers or operators, and parse them like so:

1. There is a current operator, which starts as +.
2. Each time an operator is found, the current operator will change to it.
3. The possible operators are: "+", "-", "\*", "/", and "%", which correspond to their meanings in C and most languages.
4. There is a running solution kept, which starts at 0.
5. Each time an integer is found, the solution is modified by the number depending on the operator; e.g. if the operator is "/" then the solution is divided by the number.
6. If an operation would result in a mixed number (i.e. with a decimal) then it must be floored back to an integer (i.e. the decimal must be chopped off).
7. Output the final solution.

For example:

The arguments `5 8 25 * 9 6 2 - 104 / 4 7 + 6 % 14` would result in:

```
  5 8  25 * 9   6    2    - 104  / 4    7      + 6 % 14
0 5 13 38   342 2052 4104   4000   1000 142   148    8  -> 8

```

The inputs will be as command-line or function arguments, or an equivalent for your language.

Shortest code wins!

# Answer
# Pyth - ~~24~~ ~~23~~ ~~22~~ 20 bytes

*2 bytes saved thanks to @issacg and 1 thanks to @orlp!*

Uses reduce with base case of `0` and checks for `'` being in repr to detect string vs. int.

```
u.xsv++GbH&=bHG+\+QZ

```

Does not work online because I use full eval which is disabled online for security reasons. Takes input from stdin in a list as such: `5, 8, 25, "*", 9, 6, 2, "-", 104, "/", 4, 7, "+", 6`.
> 6 votes

# Answer
# JavaScript (ES6) 53

A function taking an array as input.

Run the snippet in Firefox to test.

```
f=a=>a.map(t=>t<'0'?o=t:v=eval(v+o+t)|0,v=0,o='+')&&v

// TEST
out=x=>O.innerHTML=x;

input = [5,8,25,"*",9,6,2,"-",104,"/",4,7,"+",6,"%",14];
out(input.join(' ')+' -> '+f(input));

function go() {
  i=I.value.split(/ +/),out(I.value+' -> '+f(i))
}
```

```
<pre id=O></pre>
Your test:<input id=I><button onclick='go()'>GO</button>
```
> 7 votes

# Answer
# Julia, ~~85~~ 83 bytes

```
s->(o=0;p="+";for i=split(s) isdigit(i)?o=eval(parse("ifloor($o$p$i)")):(p=i)end;o)

```

This creates an unnamed function that accepts a string as input and returns an integer.

Ungolfed:

```
function f(s::String)
    # Assign the starting output value o and operator p
    o = 0
    p = "+"

    # Split the input string into an array on spaces
    for i = split(s)
        if isdigit(i)
            # Assign o using string interpolation
            o = eval(parse("ifloor($o $p $i)"))
        else
            # Assign p to the new operator
            p = i
        end
    end
end

```

Fixed issue and saved 2 bytes thanks to Glen O.
> 5 votes

# Answer
# CJam, 24 bytes

```
0'+ea+{_A,s&O{:O;}?S}%s~

```

This is a full program that reads the input as command-line arguments.

To try the code online in the CJam interpreter (which doesn't support command-line arguments), replace `ea` with `lS/` to read from simulated STDIN.

### How it works

```
0'+                       Push a 0 and the character '+'.
   ea                     Push the array of command-line arguments.
     +                    Prepend the character to the array.
      {             }%    For each element:
       _                    Push a copy.
        A,s                 Push "0123456789".
           &                Intersect the copy with the string of digits.
             {   }?         If the intersection is non-empty:
            O                 The element is a number. Push O.
              :O;             The element is an operator. Save it in O.
                   S        Push a space.
                      s~  Flatten the array of strings and evaluate it.

```
> 4 votes

# Answer
# elisp, 101 bytes

With the arguments passed as a quoted list: e.g. `(c '(5 5 * 10))`

```
    (defun c(a)(let((f 0)(o '+))(dolist(x a)(if(not(integerp x))(setf o x)(setq f (eval(list o f x)))))f))

```

Version with new lines:

```
    (defun c (a)
      (let ((f 0)
            (o '+))
        (dolist (x a)
          (if (not (integerp x))
              (setf o x)
            (setq f (eval (list o f x)))))
        f))

```
> 4 votes

# Answer
# JavaScript, 85 bytes

```
r=0;o="+";prompt().split(" ").forEach(t=>+t+1?r=parseInt(eval(r+o+ +t)):o=t);alert(r)

```
> 3 votes

# Answer
# Lua, 142 bytes

```
function f(s)o="+"r=0 for c in s:gmatch"%S+" do if tonumber(c)~=nil then loadstring("r=r"..o..c)() else o=c end r=math.floor(r)end print(r)end

```

Ungolfed:

```
function f(s)
    o="+" --original operator
    r=0 --return value
    for c in s:gmatch"%S+" do --split by spaces
        if tonumber(c)~=nil then --check if the current character is a number
            loadstring("r=r"..o..c)() --appends the current operator and current character ex "r=r+5" and then evaluates as another Lua script
        else
            o=c --if the character is not a number, it is the new operator
        end
        r=math.floor(r) --floor after each operation
    end
    print(r) --print the result
end

```
> 3 votes

# Answer
# Powershell, 57 bytes

```
$o="+"
$args|%{$r=iex "$r$o$_"
if(!$?){$o=$_}$r-=$r%1}
$r

```

ungolfed;

```
$operator="+"
$args | ForEach-Object
{
    $result = Invoke-Expression "$result $operator $_"
    if(!$?)
    {
        $operator=$_
    }
    $result -= $result % 1
}
$result

```

If the implicit variable in the for-each is an operator rather than number, Invoke-Expression (POSH's `eval()`) will fail and the execution status `$?` will be false.

Floor in POSH is unwieldy - `$foo=[math]::floor($foo)` and `$foo-=$foo%1` was the golfiest alternative I could think of.
> 3 votes

# Answer
# GNU Sed (with the eval extension, + dc), 102

(Score includes +1 for the -r option to sed.)

```
s/.*/0 + &p/
s/([-+/*%]) ([0-9]+)/\2 \1/g
:
s/([-+/*%] )([0-9]+ )([0-9]+)/\1\2\1\3/
t
s/.*/dc<<<'&'/e

```

Transforms the input expression to reverse polish notation, and then uses `dc` to evaluate it.

### Test output:

```
$ sed -rf calclist.sed <<< '5 8 25 * 9 6 2 - 104 / 4 7 + 6 % 14'
8
$

```
> 3 votes

# Answer
## Python 3 - ~~131 bytes~~ ~~129 bytes~~ ~~121 bytes~~ 116 Bytes

Thanks to Maltysen for shaving off two bytes, Beta Decay for shaving off 8, and Steven Rumbalski for shaving off 5.

```
def f(x):
    a,b="+",0
    for i in x:
        if i in"+-*/%":a=i
        else:b=int(eval(str(b)+a+i))
    return b

```

I'm trying to figure out a way to reduce the length of the if statement, but for now this seems about as golfed as I can get it. Takes input as a list.
> 2 votes

# Answer
# CJam, 34 bytes

```
'+0lS/{"+-*/%"1$#){@;\}{i2$~}?}/\;

```

Try it online

I thought this was going to be fairly reasonable. But I wasn't fast enough posting it to be the shortest CJam answer at least for a moment. :(
> 2 votes

# Answer
# Bash, 69

```
set -f
for t in $*
do
((1${t}1>2))&&((r${o-+}=$t))||o=$t
done
echo $r

```

This only works with non-negative integers - its not clear in the question if this is ok or not.
> 2 votes

# Answer
# Groovy, 79 bytes

```
def f(x,a=0,b='+'){x.each{z->a=z=~/\d/?Eval.me(a+b+z)as int:a;b=z=~/\d/?b:z};a}

```

Demo:

```
groovy> f([5,8,25,'*',9,6,2,'-',104,'/',4,7,'+',6,'%', 14])
Result: 8

```

Ungolfed:

```
def f(x, a=0, b='+') {
    x.each {z->
        a = z =~ /\d/ ? Eval.me(a+b+z) as int : a
        b = z =~ /\d/ ? b : z
    }
    a
}

```
> 2 votes

# Answer
# C 122

**Thanks to @ceilingcat for finding a much better (and shorter) version**

```
#define A atoi(*a):s
o,s;main(z,a)char**a;{for(;*++a;)**a<48?o=**a-43:(1?s=o+6?o-4?~o?o-2?o?:s+A-A*A/A%A);printf("%d",s);}

```

Try it online!

But if you are compiling it with mingw32 you need to turn off globbing (see https://www.cygwin.com/ml/cygwin/1999-11/msg00052.html) by compiling like this:

```
gcc x.c C:\Applications\mingw32\i686-w64-mingw32\lib\CRT_noglob.o

```
> 1 votes

# Answer
# Perl 5.10+, 52 bytes

```
perl -E '$o="+";/\D/?$o=$_:eval"\$x=int\$x$o$_"for@ARGV;say$x'

```

Demo:

```
$ perl -E '$o="+";/\D/?$o=$_:eval"\x=int\$x$o$_"for@ARGV;say$x' 5 8 25 \* 9 6 2 - 104 / 4 7 + 6 % 14
8

```

(Note that `*` has to be escaped in my shell so it's not interpreted as a glob pattern.)

## Ungolfed:

```
$o="+";                      # Start with addition
/\D/ ? $o=$_                 # If not a number, update the current operator
     : eval"\$x=int\$x$o$_"  # Otherwise, make a string like '$x=int$x+1' and eval it
for@ARGV;                    # Repeat for each item in the argument list
say$x                        # Print the result

```
> 1 votes

# Answer
# C#, 132 ~~165 168~~ bytes

This function assumes the input is valid. This is tough for C# given there's no `eval` equivalent.

Thanks edc65 for saving 33 bytes!

Indented for clarity.

```
int C(string[]a){
    int o=1,r=0,n;
    foreach(var b in a)
        n=int.TryParse(b,out n)
            ?r=o<0?r%n
              :o<1?r*n
              :o<2?r+n
              :o<4?r-n
                  :r/n
            :o=b[0]-42;
    return r;
}

```
> 1 votes

# Answer
# Ruby, 59 bytes

```
a=0
o=?+
gets.split.map{|s|s=~/\d/?a=eval([a,s]*o):o=s}
p a

```

Test run:

```
$ ruby calc.rb <<< "5 8 25 * 9 6 2 - 104 / 4 7 + 6 % 14"
8

```
> 1 votes

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


title: 2D Inequalities

text:
# Question
Title: 2D Inequalities
**Objective**

Given a grid of numbers, fill in the inequalities.

**Assumptions**

The number of columns and rows in the grid are equal.
The maximum size of the grid is 12x12.
The grid only consists of integers 0-9.
The output may contain a trailing newline.
The input is exactly as written below, including spaces and newlines.

**Example Input**

```
4 2 3 1

6 2 3 1

6 9 2 1

0 2 1 6

```

**Example Output**

```
4>2<3>1
^ " " "
6>2<3>1
" ^ v "
6<9>2>1
v v v ^
0<2>1<6

```

**Example Input (2)**

```
1 2 3 4 5

5 4 3 2 1

0 0 0 3 2

3 2 0 0 0

2 1 3 1 5

```

**Example Output (2)**

```
1<2<3<4<5
^ ^ " v v
5>4>3>2>1
v v v ^ ^
0=0=0<3>2
^ ^ " v v
3>2>0=0=0
v v ^ ^ ^
2>1<3>1<5

```

**Example Input (3)**

```
8

```

**Example Output (3)**

```
8

```

**Example Input (4)**

```
0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 1 1 1 1 1 1 0

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

0 1 3 9 8 7 6 5 4 8 1 0

0 1 4 8 9 8 7 6 5 7 1 0

0 1 5 7 8 9 9 7 6 6 1 0

0 1 6 6 7 9 9 8 7 5 1 0

0 1 7 5 6 7 8 9 8 4 1 0

0 1 8 4 5 6 7 8 9 3 1 0

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

0 1 1 1 1 1 1 1 1 1 1 0

0 0 0 0 0 0 0 0 0 0 0 0

```

**Example Output (4)**

```
0=0=0=0=0=0=0=0=0=0=0=0
" ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ "
0<1=1=1=1=1=1=1=1=1=1>0
" " ^ ^ ^ ^ ^ ^ ^ ^ " "
0<1<2<3<4<5<6<7<8<9>1>0
" " ^ ^ ^ ^ " v v v " "
0<1<3<9>8>7>6>5>4<8>1>0
" " ^ v ^ ^ ^ ^ ^ v " "
0<1<4<8<9>8>7>6>5<7>1>0
" " ^ v v ^ ^ ^ ^ v " "
0<1<5<7<8<9=9>7>6=6>1>0
" " ^ v v " " ^ ^ v " "
0<1<6=6<7<9=9>8>7>5>1>0
" " ^ v v v v ^ ^ v " "
0<1<7>5<6<7<8<9>8>4>1>0
" " ^ v v v v v ^ v " "
0<1<8>4<5<6<7<8<9>3>1>0
" " ^ ^ ^ " v v v v " "
0<1<9>8>7>6>5>4>3>2>1>0
" " v v v v v v v v " "
0<1=1=1=1=1=1=1=1=1=1>0
" v v v v v v v v v v "
0=0=0=0=0=0=0=0=0=0=0=0

```

# Answer
> 3 votes
# Pyth, 46 bytes

```
juCms.iJ-d\ m.x@H._-FsMk\ .:J2Gc2"=><\"v^"%2.z

```

Try it online: Demonstration

# Answer
> 7 votes
# CJam, 52 bytes

```
qN%::~_z_2{{_1>.-W<:g}%\z}*@@..{'=+}.{N@"\"v^"f=S*N}

```

Try it online in the CJam interpreter.

*Thanks to @CroCo for pointing out a bug in revision 3.*

*Thanks to @Pyrrha for pointing out a bug in revision 6.*

### How it works

```
qN%        e# Read all input and split it at runs of linefeeds.
::~        e# Evaluate each character separately.
           e# This turns non-empty lines into arrays of integers.
_z_        e# Copy, transpose rows and columns, and copy again.
2{         e# Do the following twice:
  {        e#   For each row:
    _1>    e#     Copy the row and remove the copy's first element.
    .-     e#     Perform vectorized subtraction.
    W<     e#     Remove the last element.
           e#     This pushes the array of increments of the row.
    :g     e#     Replace each difference with its sign (-1, 0 or 1).
  }%       e#
  \        e#   Swap the two topmost arrays on the stack.
  z        e#   Transpose rows and columns of the topmost array.
}*         e#
           e# The topmost result has been transposed before and after computing
           e# the increments of its rows. It holds the increments of it columns.
           e# The result below it has been transposed twice (therefore not at
           e# all) before computing the increments of its rows.
@@         e# Rotate the number array and the row increment array on top.
..{        e# For each number and the corresponding increment, push both; then:
  '=+      e#   Add the increment to the character '='.
}          e#
.{         e# For each row of the column increment array and corresponding row
           e# of the last result, push both rows; then:
  N@       e#   Push a linefeed and rotate the column increments on top.
  "\"v^"f= e#   For each, select the appropriate comparison character.
  S*       e#   Join those characters, separated by spaces.
  N        e#   Push another linefeed.
 }         e#

```

# Answer
> 4 votes
# Python 2, ~~207~~ 197 bytes

```
f=lambda a:''.join(['=><'[cmp(a[i-1],a[i+1])]if c==' 'else'\n'+' '.join('"v^'[cmp(a[j-a.index('\n')],a[j+2])]for j in range(i,i+a.index('\n'),2))if a[i:i+2]=='\n\n'else c for i,c in enumerate(a)])

```

This one creates a function **f** which takes the grid of numbers as a string and returns the corresponding string with filled inequalities.

The function iterates over each character in the string. If the character is a space, it is replaced with the inequality for the numbers on either side. If the character and the next character are newlines, the whole line is replaced with the inequalities for all the numbers above and below.

Here is the output of the function for each of the examples in the question, except the really long one:

```
>>> print f("""\
... 4 2 3 1
...
... 6 2 3 1
...
... 6 9 2 1""")
4>2<3>1
^ " " "
6>2<3>1
" ^ v "
6<9>2>1
>>> print f("""\
... 1 2 3 4 5
...
... 5 4 3 2 1
...
... 0 0 0 3 2
...
... 3 2 0 0 0
...
... 2 1 3 1 5""")
1<2<3<4<5
^ ^ " v v
5>4>3>2>1
v v v ^ ^
0=0=0<3>2
^ ^ " v v
3>2>0=0=0
v v ^ ^ ^
2>1<3>1<5
>>> print f("8")
8

```

# Answer
> 3 votes
## C, ~~552~~ 408 bytes

This is a mess, but it does work with the test cases (for the solo `8`, the input has to be followed by a newline to work properly)

```
#define P putchar
main(n,z)char**z;{char*t=*++z;n=0;while(*(*z)++!=10)if(**z!=32)n++;char a[n][n];int r=-1,c=0;n--;do*t>32?c?:r++,a[c][r]=*t:*t==10?c=0:c++;while(*++t);r=c=0;do{int j=a[c][r],s=61,k=a[c+1][r];P(j);if (c==n){if(r==n)break;c=0;r++;P(10);for(int t=a[c][r-1],b=a[c][r];c<n+1;t=a[c][r-1],b=a[c][r])s=t>b?118:t<b?94:34,printf("%c ",s),c++;c=0;P(10);continue;}s=j>k?62:j<k?60:s;P(s);c++;}while(1);}

```

Here's the expanded version; I'd love to here ways on how I could golf this more effectively. I know that there is much to be improved on here.

```
#define P putchar
main(n,z)char**z; {
    char *t = *++z;
    n = 0;
    while (*(*z)++!=10)
        if (**z!=32)
            n++;
    char a[n][n];
    int c,r=c=0;
    r = -1,n--;
    do
        *t>32?c?:r++, a[c][r] = *t:*t==10?c=0:c++; //32 is ASCII for space
    while (*++t);
    r=c=0;
    do {
        int j = a[c][r],s=61,k = a[c+1][r];P(j);
        if (c==n)
        {
            if (r==n)break;
            c=0;r++;P(10);
            for (int t=a[c][r-1],b=a[c][r];c<n+1; t = a[c][r-1],b = a[c][r])
                s=t>b?118:t<b?94:34,printf("%c ",s),c++;
            c = 0;
            P(10);
            continue;
        }
        s=j>k?62:j<k?60:s;

        P(s);
        c++;
    } while (1);
}

```

# Answer
> 2 votes
# JavaScript (ES6) 162

```
f=s=>(s=s.split`
`).map((r,i)=>r?(w=r).replace(/ /g,(c,j)=>x('<=>',r[j-1]-r[j+1])):w.replace(/\d/g,(c,j)=>x('^"v', c-s[i+1][j]))  ,x=(y,v)=>y[-~(v>0)-(v<0)]).join`
`

// more readeable
u=s=>(
  x=(y,v)=>y[-~(v>0)-(v<0)],
  s=s.split`\n`,
  s.map((r,i)=>r
    ?(w=r).replace(/ /g,(c,j)=>x('<=>',r[j-1]-r[j+1]))
    :w.replace(/\d/g,(c,j)=>x('^"v', c-s[i+1][j]))
  ).join`\n`
)

//TEST
console.log=x=>O.innerHTML+=x+'\n'

;[
 '4 2 3 1\n\n6 2 3 1\n\n6 9 2 1\n\n0 2 1 6'
,'1 2 3 4 5\n\n5 4 3 2 1\n\n0 0 0 3 2\n\n3 2 0 0 0\n\n2 1 3 1 5'
,'8',
,'0 0 0 0 0 0 0 0 0 0 0 0\n\n0 1 1 1 1 1 1 1 1 1 1 0\n\n0 1 2 3 4 5 6 7 8 9 1 0\n\n0 1 3 9 8 7 6 5 4 8 1 0\n\n0 1 4 8 9 8 7 6 5 7 1 0\n\n0 1 5 7 8 9 9 7 6 6 1 0\n\n0 1 6 6 7 9 9 8 7 5 1 0\n\n0 1 7 5 6 7 8 9 8 4 1 0\n\n0 1 8 4 5 6 7 8 9 3 1 0\n\n0 1 9 8 7 6 5 4 3 2 1 0\n\n0 1 1 1 1 1 1 1 1 1 1 0\n\n0 0 0 0 0 0 0 0 0 0 0 0'
].forEach(t=>console.log(t+'\n\n'+f(t)+'\n\n'))
```

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

# Answer
> 1 votes
# Haskell, 201 bytes

```
import Data.List
t=transpose
g=mapM_ putStrLn.t.map(h 1).t.map(h 0).lines
h n s@(a:_:b:r)|'/'<a&&a<':'=a:(o n a b):h n(b:r)
 |0<1=s
h n r=r
f=fromEnum
o n a b=l!!n!!(1+signum(f a-f b))
l=["<=>","^\"v"]

```

`g` expects a string.

---
Tags: code-golf
---


# Question
Title: Fifth Grade Math Problem for the Week: Automated Decryption of Caesar Ciphers
My fifth-grade daughter is learning about codes and ciphers. She has reached the point of decoding a ciphertext that has been encoded with the Caesar cipher where the offset is not provided in advance.

Without computers this can be time-consuming, especially for long blocks of text. Luckily, we do have computers, and let's prove it.

Cipher definition and other bounds:

1. Every letter is offset by a fixed (but unknown) number of characters, while retaining the same case. Spaces and punctuation marks are unaffected. Thus, with offset 1, "A"→"B" and "c"→"d" but "," stays as ",".
2. Offset will be a positive integer.
3. English plaintexts only, and no accent marks in the ciphertext or the plaintext.

Your task: Given a ciphertext, determine the most likely correct plaintext via brute force with a dictionary lookup. Thus, generate all 26 possible solutions, then check for the presence of every word in each potential decryption in an English dictionary and select the potential solution with the highest percentage of words that are found there.

The ciphertext should be the only input to your program, and the plaintext should be the only output.

For the sake of this challenge: garbage in, garbage out — given an undecryptable input, your code can return any output. And if multiple solutions tie for % found in the dictionary, you can return any of them.

Sample inputs:

```
"Fsyvoxmo kxn mywwsddoo woodsxqc."

"Gwbqs Sadwfs Ghfwysg Poqy, Ghof Kofg vog pssb bchvwbu pih o pzif ct wbobs waousg kwhv ob slqszzsbh gcibrhfoqy."

"Pda pnqpd sehh oap ukq bnaa. Xqp jkp qjpeh ep eo bejeodaz sepd ukq."

```

Your system should accept any string as input and attempt to decode it, and must be able to decode these examples correctly. I completed an ungolfed solution in Mathematica in about 700 characters. Standard rules apply; no hard-coded solutions, etc. Smallest number of bytes wins.

# Answer
## Python 2, ~~384~~ 319

```
a=raw_input()
e=lambda v,b:(ord(v)+b-65-32*(v>"``"))%26+65+32*(v>"``")
c=lambda b:''.join(chr(e(f,b))if f.isalpha() else f for f in a)
p=map(c,range(26))
w=map(str.strip,open('w'))
l=[0]*26
for k,i in enumerate(p):
    for j in i.split():
        if j.lower() in w:l[k]+=1
m=[i for i,j in enumerate(l)if j==max(l)][0]
print p[m]

```

I named my wordlist `w`, which is a newline-separated list of lowercase words.
> 1 votes

# Answer
# Pyth, ~~39~~ ~~34~~ 31 bytes

```
h.Msm}@Grd0'\wcZd.u.r.rNrG1G25z

```

Solves all test cases. Expects the newline-separated lowercase word list to be in the file `w`.

You can also try it online. The online version expects input on the first line and the dictionary words in lowercase on the next lines. Note that trying to send a large dictionary to the server may not be a good idea.

The algorithm tries to maximize the amount of correct words in the text, so if there are impossible-to-decipher words they are just ignored. In case of completely impossible input just outputs it back.

### Explanation

* `z` is preinitialized to input.
* `.u ... 25z` repeats the following process 25 times, starting with the input, and returns all 26 results:
    + `.rNrG1` shifts uppercase letters (`rG1`) by one
    + `.r.rNrG1G` shifts all letters by one
* `.M` finds the ones from said results that produce the maximum result for:
    + `cZd` splits the current string by spaces
    + `sm` counts the occurrences where:
        - `rd0` lowercases the word
        - `@G` removes non-alphabetic letters
        - `} ... '\w` checks whether the word is in the file `w`
> 1 votes

---
Tags: code-golf, word-puzzle
---


title: The obstacle course

text:
# Question
Title: The obstacle course
# The obstacle course

You are currently stuck in some kind of course and you have to escape. However, if you do not choose the fastest way then the exit will close in front of you. Your challenge is to find the fastest route in an obstacle course.

**Input**

Your input consists of a list with lists in it, a 2D grid containing only positive integers. For example, it might look as follows:

eg. `[[0,1,2],[0,3,5],[2,6,1]]` which visually looks like:

```
0  1  2
0  3  5
2  6  1

```

Each number represents the time that is needed to pass the location. For example, `(1,2)` takes 6 seconds to pass. Your code can take for granted that no conversions of the input have to be made to make it a list that works with your language.

**Computing**

Your starting position will also be `(1,1)`, which in the input above is 2. You *have to* include those seconds in your final answer. From your starting position your goal is to work to `(xmax, ymax)`, which in the input above is `(3,3)`. You have to find the fastest route to get there, so the sum of your numbers must be minimal.

*Note for example understanding: the grid is from 1 and on-wards, (0,0) is not the starting position. (1,1) is bottom left and (3,3) is top right in this example.*

**Output**

Your code must output the minimal time it takes to reach the top right corner from the bottom left corner. In the input above this is `2 + 0 + 0 + 1 + 2 = 5` seconds. Your code should output nothing else than a whole integer.

**Additional specifications**

* Your may not move diagonally; only left, right, down, up
* This is , shortest code in bytes wins
* The grid wont always be square, but the start will always be connected to the end
* minimum input is a 1x1 grid
* grid will only contain positive integers

To sum up the given example:

```
Input: [[0,1,2],[0,3,5],[2,6,1]] // any format you like
Output: 5

How:
2 + 0 + 0 + 1 + 2 = 5

```

# Answer
> 2 votes
# Matlab, ~~207~~ 199 bytes

Given the matrix with all the times `A`, the idea is using a new `B` matrix that has every entry set to `Inf` except the initial entry. Then we generate a new matrix `C` where we apply following formula to each pair of coordinates `(i,j)`

```
 C(i,j) = min( B(i,j), B(i-1,j)+A(i,j), B(i+1,j)+A(i,j), B(i,j-1)+A(i,j), B(i,j+1)+A(i,j) );

```

This means: either B(i,j) already represents the minimum time to get to `(i,j)` or we can get to `B(i,j)` quicker via one of the neighbours.

Then we replace B with C and repeat this step enough times (until nothing changes anymore), and `#rows + #columns` is an upper bound for this.

After that, we just need to print the top right element (or in *matrix-speak*: bottom right) element.

This idea is basically stolen from the Floyd-Warshall algorithm.

Note that for doing this, I need also to consider some technical details, namely that I should not access elements outside the matrix, that is why I need the zero padding and shift of coordinates.

```
a=input('');
[r,c]=size(a);
A=padarray(a,[1,1]);
C=A+Inf;C(2,2)=A(2,2);
for i=1:r+c
    B=C;
    for i=2:r+1;
        for j=2:c+1;
            v=[-1,1];
            C(i,j)=min([B(i,j)-A(i,j),B(i+v,j)',B(i,j+v)]+A(i,j));
        end;
    end;
end;
disp(A(r+1,c+1))

```

Input: We need to reverse the order of the rows due to indexing, so the example given would be

```
[[2,6,1];[0,3,5];[0,1,2]]

```

or alternatively

```
[2,6,1;0,3,5;0,1,2]

```

So for this example we get following intermediate steps that will show the progression quite nicely (I removed the padding):

```
 2     Inf   Inf
 Inf   Inf   Inf
 Inf   Inf   Inf

 2     8     Inf
 2     Inf   Inf
 Inf   Inf   Inf

 2     8     9
 2     5     Inf
 2     Inf   Inf

 2     8     9
 2     5    10
 2     3    Inf

 2     8     9
 2     5    10
 2     3     5

```

PS: I love challenges like this one=)

---
Tags: code-golf, path-finding
---


# Question
Title: Reading the news is boring. Help me out!
Everyone knows that the news is boring. *Really boring*. Unless if it's about Politicians and their scandals. That is fun! But alas, Politicians can commit only so many scandals. So, I am employing you to make the news more interesting.

**Objective** Given an HTML snippet, perform all the substitutions found here, that is, in this picture:

BUT you should not edit any HTML tags themselves. I call a valid word any word that is not found within any HTML tag or their attributes. That is, you shouldn't replace `<div class="smartphone">iPhone</div>` with `<div class="pokedex">iPhone</div>`, but should replace `<div>election</div>` with `<div>eating contest</div>`.

# Parsing rules

* **EDIT** You should only match words delineated by a non-word. That is, you should only match full words. (E.g., match "Hello witness" but not "Hellowitness", "Hellow itness", or "Witnesspacelection."
* If you can't type out the character on your keyboard, you should display the closest equivalent. (E.g., "Smartphone" would really become "Pokedex")
* First-letter case or all-letter case must be retained. (E.g., "Allegedly, they died" becomes "Kinda probably, they died", "They allegedly died" becomes "They kinda probably died", and "THE ELECTION!" becomes "THE EATING CONTEST!", while "SpAcE" becomes "Spaaace" and "nEW STUDY" becomes "tumblr post")
* All cases must be matched. (I.e., you must match a word, regardless of its capitalization.)
* Any instance in which `a <vowel>` is met should become `an <vowel>` and *vice versa*. (E.g., "A senator" becomes "An elf-lord") You do not have to do this for every instance, but at least for your own replacements.
* Anything plural must also retain pluralization in the translation (E.g., "Smartphones" becomes "pokedex" and "Spaces" becomes "Spaaaces")
* Anything in a certain tense must remain in that tense in the translation. (E.g., "Rebuilt" becomes "Avenged", "Rebuilds" becomes "Avenges", etc.)
* Anything in the singular must remain singular in the translation (E.g., "Congressional leader" becomes "River spirit")
* If the entry spans multiple HTML elements, you should still match it, but you may "throw away" any intermediate elements. (E.g., `S<b>pa</b>ace` should become simply "spaaace"). If the entry is self-contained within a single element, it should be matched properly and the tag retained.
* "The witnesses" should become "Those dudes I know"
* "witness" should become "This dude I know"
* "The witness" should become "That dude I know"
* "Couldn't be reached for comment" should become "Is guilty and everyone knows it"
* "Cannot be reached for comment" should become "Are guilty and everyone knows it"

# Bonuses

If you meet a `-N%` bonus, your `new amount = (old amount) * (1 - N/100)`. So, if you met a `-5%` bonus with a 500 byte code, your `new amount = 500 * (1 - 5/100) = 500 * .95 = 475`.

* -5% bonus if, for every instance of "space" after the first replacement, an extra "a" is added. So, the first replacement would be "spaaace", the second would be "spaaaace", the third would be "spaaaaace", etc.
* -5% bonus if, for every valid number, you replace that number with a link to the respective XKCD comic. (It doesn't have to yet exist). If you do go for this bonus, you should match numbers such as `500`, `3,000`, `4 523`, and `5.324`. (You may opt to replace, instead, the number with the image of the comic. If you do this, instead of a `-5%` bonus, you will get a `-15% bonus`. Another extra `-15%` bonus if you can add the title-text to the picture, if any.)
* -25% bonus if you can replace simultaneously all instances on the right side of the image with those on the left. (E.g., "spaaace" becomes "space", "eating contest" becomes "election", etc.) If you opt for any of the bonuses, you should be able to revert those to their respective entries. (E.g., `http://www.xkcd.com/542` should become "542", and "spaaaaaaaace" should become "space".)
* ***You may choose to do a minimum of 6 substitutions, but for each substitution not done (exclusive of bonus substitutions), you will receive an additional +10% penalty.***

# Example IOs (no bonuses)

```
Input: Witnesses allegedly used their smartphones to commit the crime.
Output: These dudes I know kinda probably used their pokedex to commit the crime.

Input: Mayor Golfalot rebuilt the city after the fatal election.
Output: Mayor Golfalot avenged the city after the fatal eating contest.

Input: This <b>new study</b> shows that people in <span class="space">space</span> cannot be reached for comment.
Output: This <b>tumblr post</b> shows that people in <span class="space">spaaace</span> are guilty and everyone knows it.

Input: <b>g</b><i>oo</i><s>g</s><u>le</u> glass is terrible. :(
Output: virtual boy is terrible. :(

Input: Electric SMARTPHONES have been shown to be more productive when not used by Senators and when not used in cars.
Output: Atomic POKEDEX have been shown to be more productive when not used by Elf-lords and when not used in cats.

Input: Homeland Security has been established as an evil foundation, especially in space.
Output: Homestar runner has been established as an evil foundation, especially in spaaace.

Input: The congressional leaders are testy today.
Output: The river spirits are testy today.

Input: SPACE is not a Senator or a cAR.
Output: SPAAACE is not an Elf-lord or a cat.

Input: Mr. Biz is running for reelection.
Output: Mr. Biz is running for reelection.

Input: Google   glass !
Output: Virtual boy !

Input: New (or old) study
Output: New (or old) study

```

---

This is a , so the shortest program in bytes wins.

# Answer
> 7 votes
# Perl 5, 850

Lots of regex used or generated.
The %l hash is used for repeated words.

```
%l=qw(A avenge B _be_reached_for_comment C could D dude E pokedex G google_glass I _I_know K river_spirit L congressional_leader P smartphone 4 rebuil N new_stud T tumblr_post V virtual_boy W witness Y _guilty_and_everyone_knows_it);$t="G,V;Ges,Vs;Ps,E;P,E;4d,A;4t,Ad;Nies,Ts;Ny,T;Wes,these DsI;W,this DI;allegedly,kinda probably;cannotB,areY;car,cat;cars,cats;Ls,Ks;L,K;C notB,isY;Cn'tB,isY;election,eating contest;electric,atomic;homeland Security,homestar runner;senator,elf-lord;senators,elf-lords;space,spaaace";$o=$s=$_;$s=~s/\s\s*/ /g;map{$t=~s/$_/$l{$_}/g}keys%l;$t=~s/_/ /g;@L=split/;/,$t;map{my@T=split/,/;push@W,\@T}@L;map{$e=$a=$W[$_][0];$b=$W[$_][1];$U=uc$a;$u=ucfirst$a;$s=~s/(?<![\w"])$U(?![\w"])/\U$b/g;$s=~s/(?<![\w"])$u(?![\w"])/\u$b/g;$s=~s/(?<![\w"])$a(?![\w"])/$b/gi;$e=~s@.@(<.*?>)?$&(</.*?>)?@g;$s=~s/$e /$b /ig;}0..@W;$_=$s.$/

```

### Test

```
$ cat news.txt |perl -p readingnews.pl
These dudes I know kinda probably used their pokedex to commit the crime.
Mayor Golfalot avenged the city after the fatal eating contest.
This <b>tumblr post</b> shows that people in <span class="space">spaaace</span> are guilty and everyone knows it.
virtual boy is terrible. :(
Atomic POKEDEX have been shown to be more productive when not used by Elf-lords and when not used in cats.
Homestar runner has been established as an evil foundation, especially in spaaace.
The river spirits are testy today.
SPAAACE is not a Elf-lord or a cat.
Mr. Biz is running for reelection.
Virtual boy !
New (or old) study

```

# Answer
> 9 votes
## JavaScript ES6, 954 bytes

I thought this was going to be a lot easier than it was! I originally used JavaScript so I could easily descend only into text nodes and replace the text there, but that wasn't what the question was after, so I've ended up with this monstrosity! It passes all the test cases except for `<b>g</b><i>oo</i><s>g</s><u>le</u> glass is terrible. :(` where the whole string comes back in a `<b>` tag due to the tags getting balanced. The bulk of the code is the lookup table, and I'm probably still missing some edge cases, but I couldn't come up with a nicer way to handle the tense correctly and I'm sure I could compress that more, but I'm running out of ideas... I'm sure I'll come back to this later though. Should've used Perl, better choice @LukStorms!

```
d=document.createElement`div`,u='toUpperCase'
d[i='innerHTML']=prompt``;`the ${w='witness'}es,those dudes I know|${w}es,these dudes I know|the ${w},this dude I know|${w},dude I know|allegedly,kinda probably|new study,tumblr post|new studies,tumblr posts|rebuild,avenge|rebuilt,avenged|space,spaaace|${g='google glass'},virtual boy|${g}es,virtual boys|smartphones,pokédex|smartphone,pokédex|electric,atomic|senator,elf-lord|car,cat|election,eating contest|congressional leader,river spirit|homeland security,homestar runner|could not ${b='be reached for comment'},is${g=' guilty and everyone knows it'}|couldn't be reached for comment,is${g}|cannot be reached for comment,are${g}`[v='split']`|`.map(w=>d[i]=d[i][r='replace'](eval(`/(<[^>]+)?\\b${(w=w[v]`,`)[0][v]``.join`(?:<\\/?[^>]+>)*`[r](/ /g,'\\s+')}(s?)\\b/gi`),(s,q,t)=>[q?s:((!s.match(/[^A-Z]/)?w[1][u]():s.match(/^[A-Z]/)?w[1][r](/^./,q=>q[u]()):w[1])+t),q?0:w[1]=w[1][r](/ce$/,'ace')][0])[r](/\ba(?= [aeiou])/gi,s=>s=="a"?"an":"AN"))
alert(d[i])

```

I applied one bonus for 5% of `spaaace` getting an additional `a` after each successful match. Uses `alert()` as suggested by @sysreq, thanks!

### Examples

```
Input: <b>g</b><i>oo</i><s>g</s><u>le</u> glass is terrible. :(
Output: <b>virtual boy is terrible. :(</b>

```

```
Input: space. Space? Space! SPACE!
Output: spaaace. Spaaaace? Spaaaaace! SPAAAAAACE!

```

```
Input: Smartphones aren't really smart phones, but: SMARTPHONES!
Output: Pokédex aren't really smart phones, but: POKÉDEX!

```

```
Input: Senator John Doe was arrested today after attempting to write a new study on the danger of smartphones being used in the car, on his smartphone whilst driving his car. A witness testified to having seen the senator committing the crime. When questioned, Senator Doe "could not be reached for comment". It's unknown if his reputation can be rebuilt and this puts new doubts on the upcoming election. Congressional leaders have yet to comment.
Output: Elf-lord John Doe was arrested today after attempting to write a tumblr post on the danger of pokédex being used in the cat, on his pokédex whilst driving his cat. A dude I know testified to having seen the elf-lord committing the crime. When questioned, Elf-lord Doe "is guilty and everyone knows it". It's unknown if his reputation can be avenged and this puts new doubts on the upcoming eating contest. River spirits have yet to comment.

```

---

### Bonus: bookmarklet

Run this in your console to have the body text updated in-place:

```
d=document.body;`the ${w='witness'}es,those dudes I know|${w}es,these dudes I know|the ${w},this dude I know|${w},dude I know|allegedly,kinda probably|new study,tumblr post|new studies,tumblr posts|rebuild,avenge|rebuilt,avenged|space,spaaace|${g='google glass'},virtual boy|${g}es,virtual boys|smartphones,pokédex|smartphone,pokédex|electric,atomic|senator,elf-lord|car,cat|election,eating contest|congressional leader,river spirit|homeland security,homestar runner|could not ${b='be reached for comment'},is${g=' guilty and everyone knows it'}|couldn't be reached for comment,is${g}|cannot be reached for comment,are${g}`[v='split']`|`.map(w=>d[i='innerHTML']=d[i][r='replace'](eval('/(<[^>]+)?\\b'+(w=w[v]`,`)[0][v]``.join`(?:<\\/?[^>]+>)*`[r](/ /g,'\\s+')+'(s)?\\b/gi'),(s,q,t)=>[q?s:((s.match(/^[A-Z]+$/)?w[1].toUpperCase():s.match(/^[A-Z]/)?w[1][r](/^./,q=>q.toUpperCase()):w[1])+(t||"")),q?0:w[1]=w[1][r](/ce$/,'ace')][0])[r](/\ba ([aeiou])/gi,(s,t)=>s[0]=="a"?"an "+t:"AN "+t))

```

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


title: "cat"-like program

text:
# Question
Title: "cat"-like program
The mission is to implement a `cat`-like program (copy all STDIN to STDOUT).

Rules:

* You may only use standard libraries
* Indentation must be either two spaces or a single tab (in languages which require indentation)
* Scripts must use shebangs
* The result of `cat anything.txt | ./yourprogram | diff anything.txt -` should be nothing and should not be an infinite loop

`Go` example (84 bytes)

```
package main
import (
  "os"
  "io"
)
func main() {
  io.Copy(os.Stdout,os.Stdin)
}

```

`C++` example (78 bytes)

```
#include<iostream>
using namespace std;
int main() {
  cout << cin.rdbuf();
}

```

`Ruby` example (44 bytes)

```
#!/usr/bin/env ruby
$stdout << $stdin.read

```

Shortest code (by bytes) wins.

# Answer
> 44 votes
# GolfScript, 0 characters / bytes

This could technically be considered invalid since GolfScript will append a `\n`, but that can be fixed with `:n;` (3 bytes).

# Answer
> 24 votes
# sed - 0 bytes

No command needed to cat a file with `sed`: all lines of input are printed without modification, so

```
sed ''

```

will act like `cat` for standard input, and

```
sed '' /etc/fstab

```

will print content of file.

# Answer
> 19 votes
# ΒrainFuck (5 bytes)

```
,[.,]

```

**Explanation:**

```
,  Read first byte of input and place on stack
[  While top byte is not 0...
 . Print top byte from stack as ASCII and remove
 , Read next byte of input and place on stack
]  ...loop

```

# Answer
> 16 votes
# Haskell - 17 bytes

```
main=interact id

```

`id` is the identity function and from the documentation :

> The `interact` function takes a function of type `String->String` as its argument. The entire input from the standard input device is passed to this function as its argument, and the resulting string is output on the standard output device.

# Answer
> 10 votes
# x86\_64 NASM Assembly for Linux - 125 / 100

```
r:mov ax,0
mov di,0
mov rsi,c
mov dx,1
syscall
cmp ax,0
je e
mov di,1
syscall
jg r
e:mov ax,60
syscall
SECTION .bss
c:resw 1

```

I couldn't get it to fit in 100 bytes, but it is assembly. Eight bytes could be saved at the cost of changing the return status to 1 instead of 0:

```
r:mov ax,0
mov di,0
mov rsi,c
mov dx,1
syscall
cmp ax,0
mov di,1
jg s
mov ax,60
s:syscall
jg r
SECTION .bss
c:resw 1

```

Now, if you really want 100 bytes, here is one in exactly 100 bytes. The problem is that it doesn't exit correctly, it just segfaults:

```
r:mov ax,0
mov di,0
mov rsi,c
mov dx,1
syscall
cmp ax,0
mov di,1
syscall
jg r
SECTION .bss
c:resw 1

```

The instructions say to only use standard libraries; is there extra credit for using no libraries at all?

# Answer
> 6 votes
# C 43

```
main(c){while((c=getchar())>=0)putchar(c);}

```

# Answer
> 5 votes
## Linux/Unix tools, 16 bytes

```
#!/bin/sh
grep $

```

Other tools that work when called by bash/sh are

```
tr . .

```

and (15 bytes)

```
sed n

```

EDIT: Changed title from "bash/sh" to "Linux/Unix tools" because although the tools can be called by bash or sh they aren't actually part of bash or sh.

# Answer
> 5 votes
# Node.js 55

```
#!/usr/bin/env node
process.stdin.pipe(process.stdout);

```

# Answer
> 5 votes
# Bash, 3

If you need a shebang, `#!/bin/sh` or `#!/bin/bash` is probably fine.

Had to be done. Hopelessly uncreative.

```
cat

```

Slightly more interesting:

```
tee

```

Normally, `tee FILENAME` sends its input both to the file and to standard output. Without an argument, it seems to behave like `cat`.

# Bash, 2

...if you don't mind the status message at the end and the fact that the output only comes after EOF on standard input!

```
dd

```

Removing the status message costs 4 chars for a total of 6 chars:

```
dd 2>a

```

The message is sent to the file `a` instead of standard output.

If you dispose of the message entirely, the total length is ~~14~~ 7:

```
dd 2>&-

```

# Bash/SHELF, 1

For the shebang, try

```
#!/bin/sh
. shelf.sh

```

where `shelf.sh` is the location of your SHELF file.

SHELF is my PYG-like golfing library for Bash.

```
D

```

`D` just aliases to `cat`. Also uncreative.

And the alias for `tee` is...

```
5

```

# Answer
> 5 votes
## Perl (1)

0+1 for the -p parameter

If really the shebang counts, invoke it like this: `perl -p nul` on M$ or `perl -p /dev/null` on \*nix so no shebang is involved :P

```
D:\>copy con cat.pl
#!perl -p
^Z
        1 file(s) copied.

D:\>type cat.pl
#!perl -p

D:\>type cat.pl | cat.pl
#!perl -p

D:\>

```

# Answer
> 4 votes
# CJam - 1

```
q

```

No extra newline :)

# Answer
> 3 votes
# AWK - ???

The complete program in `awk` has only 1 char:

```
1

```

Unluckily the shebang stuff lets kinda explode it's length :(

```
#!/usr/bin/awk -f
1

```

May I copy `awk` into the filesystem root? \>;-)

As oneliner it is shorter:

```
$ awk 1 </etc/hostname
darkstar

```

I'm not sure what counts and what not...

# Answer
> 3 votes
# Ruby, 2 bytes (or 1?)

```
#!/usr/bin/env ruby -p

```

The question states that the shabang needs to be included. The 2 bytes counted is the `-p` part of the shebang. The otherwise empty script makes Ruby behave *exactly* likes `cat` when run with the `p` switch: Run it without arguments and it will take input from stdin, or with arguments and it print the contents of those files.

**edit:**

# Ruby, 8 bytes

@core1024 had already posted a solution in Perl similar to the one above, so here is another attempt. Note that the following are not scripts, they are Ruby *programs* ;)

```
puts *$<

```

# Ruby, 16 bytes

I think this one is cute

```
print while gets

```

# Answer
> 3 votes
# 16 bit .com binary for MSDOS - 31 Bytes (112 Byte NASM Source)

```
00 00 BA 00 00 B9 01 00 B4 3F BB 00 00 CD 21 83 F8 00 74 09 B4 40 BB 01 00 CD 21 EB EB CD 20

```

The nasm source code:

```
c:resw 1
mov dx,c
mov cx,1
r:
mov ah,63
mov bx,0
int 33
cmp ax,0
je e
mov ah,64
mov bx,1
int 33
jmp r
e:
int 32

```

Build with "nasm -f bin -o cat.com cat-msdos.s".

I already provided a solution for x86\_64 Linux, but was unable to get it under 100 bytes. This is over 100 bytes of assembly, but the actually binary is only 31 bytes! This must be the simplest solution here.

# Answer
> 2 votes
# Python 2.x - 56 or 61 bytes

Input limited to 10^9 bytes.

```
#!/usr/bin/python
from os import*
write(1,read(0,10**9))

```

Or for infinite input (61 bytes):

```
#!/usr/bin/python
from sys import*
stdout.write(stdin.read())

```

Not much to say, is there?

# Answer
> 2 votes
# Common Lisp

## ECL, 106

```
#!/usr/local/bin/ecl -shell
(ignore-errors(loop(write-byte(read-byte *standard-input*)*standard-output*)))

```

## SBCL, 109

```
#!/usr/local/bin/sbcl --script
(ignore-errors(loop(write-byte(read-byte *standard-input*)*standard-output*)))

```

## CLISP, ~~188~~ 180

```
#!/usr/local/bin/clisp
(let((i(make-stream 0 :element-type'(mod 256)))(o(make-stream 1
:direction :output :element-type'(mod
256))))(ignore-errors(loop(write-byte(read-byte i)o))))

```

These are the shortest programs that I can make, yet none are under 100 bytes.

The main problem is that `*standard-input*` and `*standard-output*` are character streams, not byte streams. A simple `(loop(write-char(read-char))` would copy the characters but would fail to preserve bytes that did not form valid characters. Now my Common Lisp implementations want to use UTF-8 (perhaps because my locale is UTF-8), but I want to copy binary files that my not be valid UTF-8. Therefore I must copy bytes, not characters.

In ECL and SBCL, standard input and output are bivalent for both bytes and characters. I may use `read-byte` and `write-byte`, but those functions lack default streams, so I must pass `*standard-input*` and `*standard-output*` as arguments.

CLISP insists that `*standard-input*` and `*standard-output*` transport only characters. The way around this is to call `ext:make-stream` on file descriptor 0 (standard input) and file descriptor 1 (standard output) to make binary streams.

All three programs loop byte by byte. This is a **slow** way to copy bytes. A faster way would use a vector of 16384 bytes with `read-sequence` and `write-sequence`, but the program would be longer.

# Answer
> 2 votes
# Batch (8)

```
type CON

```

Type writes file content to the console and CON is treated as a file containing all console input.

# Answer
> 2 votes
# TI-BASIC, 12

```
While 1:Input Str1:Disp Str1:End

```

# Answer
> 2 votes
# Java ~~68~~ 104

My first approach at this:

~~`class a{public static void main(String[]a){System.out.print(a[0]);}}`~~

EDIT: Yeah, I misunderstood the concept, here is another attempt, I couldn't get it done in less than 100 chars so I'd appreciate any suggestion:

```
class a{public static void main(String[]a)throws Exception{for(;;)System.out.write(System.in.read());}}

```

# Answer
> 2 votes
# zsh, 15 bytes

```
#!/bin/zsh
1<&1

```

Note that there is **no** newline at the end of the file.

# Answer
> 2 votes
Some Perl:

```
#!/usr/bin/perl
print<>;

```

25 bytes with shebang. This can also be much smaller with die(), and by bending the rules ever so slightly:

```
die<>

```

Executing the 4th test could only be done like this:

```
cat bla|perl ./perlcat 2>&1|diff bla -

```

\<\> is an abbreviation for `<STDIN>`. The 25 byte print example is pretty self explanatory. die() is normally used for exiting non-zero and outputting an error message, hence using the 2\>&1 to bend the rules around the 4th test.

It also appears that the semicolon is not required for the last statement in Perl, so the first example could be brought down to 24 bytes.

# Answer
> 2 votes
### Perl6, 14 bytes:

```
.say for lines

```

And, if it doesn't need to be deterministically printing it in the correct order (hehe), you can use the auto-threading "map-apply"

```
lines>>.say

```

# Answer
> 2 votes
# \>\<\>, 7 bytes

I know a \>\<\> solution already exists, but I figured it would be welcome.

```
i:0(?;o

```

Click here to try it

# Answer
> 1 votes
# GML, 37

```
while(1)show_message(keyboard_string)

```

# Answer
> 1 votes
# Rust - 74

Really generic...

```
use std::io;fn main(){for l in io::stdin().lines(){io::print(l.unwrap())}}

```

## No Comment - 12

```
'=|@^:'&|:'&

```

Unimplemented, so, yeah.

# Answer
> 1 votes
## Dart - 48

```
import"dart:io";main(){stdout.addStream(stdin);}

```

# Answer
> 1 votes
## Groovy - 45 bytes

```
#!/usr/bin/env groovy
System.out << System.in

```

And test:

```
$ cat FirstJsonObj.groovy | ./Cats.groovy | diff FirstJsonObj.groovy  -
$

```

# Answer
> 1 votes
# Tcl 57

```
#!/usr/bin/env expect
while {[gets stdin d]>=0} {puts $d}

```

# Answer
> 1 votes
# Swift, 32

```
while let l=readLine(){print(l)}

```

Prints every line until EOF is reached

If you're really picky that this doesn't work with an empty line at the end or whatever you can use this:

```
while let l=readLine(stripNewline:false){print(l,terminator:"")}

```

# Answer
> 1 votes
# MATLAB, 18 bytes

```
fprintf(input(''))

```

Cannot use `disp` as it appends a newline to the output.

# Answer
> 1 votes
# Simplex v.0.7

```
bg
b  ~~ take string input
 g ~~ output strip

```

Simple enough.

# Answer
> 1 votes
# TeaScript, 1 byte

```
x

```

Input is given in the first input field. Compile online here.

# Answer
> 0 votes
# Shell script, 11 bytes (including shebang)

```
#!/bin/cat

```

# Answer
> 0 votes
# Hassium, 52 Bytes

```
use IO;func main(){println(File.readText(args[0]));}

```

Expanded:

```
use IO;

func main () {
    println(File.readText(args[0]));
}

```

# Answer
> -1 votes
# grep - 2 or 7 bytes

```
grep ''

```

Tested on Linux.

The "program" of '' is two bytes but the complete command is 7 bytes.

# Answer
> -2 votes
## Many languages (49)

```
print("\\    /\\\n )  ( \')\n(  /  )\n \\(__)|");

```

> Because :3 is more like a tame lion.

# Answer
> -2 votes
# Ruby, 21 characters

```
#!/usr/bin/env ruby
while 1;puts gets;end

```

---
Tags: code-golf
---


title: Insert a given pattern at a given point

text:
# Question
Title: Insert a given pattern at a given point
# The challenge

Insert one string into another at a given index.

Given a string input in the format:

```
#:Pattern:Word

```

Where:

* `#` is a positive integer marking the index
* `Pattern` is the string (whose length is undefined) to insert
* `:` is a delimiter
* `Word` is the string to insert into.

Assume that a `:` will not be used in either string.

For example, if your input was

```
3:A2C:Hello World!

```

The output would be

```
HelA2Clo World!

```

If an invalid index is provided, the program must respond with an error. For example

```
12:!*!:Hello

```

is a valid input and must be explicitly handled somehow. For example, printing "Invalid input!" (or nothing at all!) is a valid way to catch, however crashing is not valid.

# Answer
# CJam, 20 bytes

```
q':/~La+@~/(@@_{];}|

```

Try it online in the CJam interpreter.

### How it works

```
q':/                e# Read all input and split it at colons.
    ~                e# Dump index, pattern and word on the stack.
     La+             e# Append the array [""] to the word.
                     e#   This increases the word's length by 1 (to deal with the
                     e#   highest index possible index) without affecting output.
        @~           e# Rotate the index on top and evaluate it.
          /          e# Split the word into chunks of that length.
           (         e# Shift out the first chunk.
            @@       e# Rotate pattern and remaining chunks on top.
              _      e# Copy the array of remaining chunks.
                     e#   This array will be empty if the index was too high.
               {];}| e# If the array if falsy, clear the stack.

```
> 5 votes

# Answer
## Python 3, 65 bytes

```
a,b,c=input().split(':')
a=int(a)
if c[a-1:]:print(c[:a]+b+c[a:])

```

Does nothing if the index is past the end of the string. Try it online.
> 3 votes

# Answer
# CJam, 34 bytes

Terribly ungolfed, but its my first CJam golf ever! Thanks to sp3000 for helping me with this on The Nineteenth Byte chat!

```
l':/~_,W$i>{W$i/(:+-2$+-3$+:+p}&];

```

**EDIT:** oops, I was in the process of posting this and I didn't see Dennis' CJam post. If the answers do end up using the same process, just count mine as a non-competitive answer. Sorry for the confusion.
> 3 votes

# Answer
# JavaScript ES6, 49 bytes

```
s=>([a,b,c]=s.split`:`,c.slice(0,a)+b+c.slice(a))

```

Very straightforward. Slices the string and inserts the new substring in the middle
> 3 votes

# Answer
# Ruby, 43 bytes

37 bytes of code:

```
G,O,L=$F
$_=(L[G.to_i,0]=O;L)rescue p

```

and 6 bytes of flags:

```
$ ruby -apF: code.rb < input
       ^^^^^^

```
> 3 votes

# Answer
# Pyth, 33

```
=Ycw\:JvhYp?>leYJjk[<eYJ@Y1>eYJ)Z

```

Prints `0` if the index is past the end of the string

Try is online
> 2 votes

# Answer
# Perl 5, 41 Bytes (40 + 1)

Outputs 0 when a replacement couldn't be made.

```
($n,$s,$_)=split/:/;$_=0if!s/.{$n}/$&$s/

```

### Test

```
$ echo "6:Online :Hello World!" |perl -p -e '($n,$s,$_)=split/:/;$_=0if!s/.{$n}/$&$s/'
$ Hello Online World!

```
> 2 votes

# Answer
# Pyth, 32 bytes

Beats the other Pyth answer! Still needs a lot of golfing though. Took the naïve approach.

```
?gleJcz":"KvhJ++:eJ0KhtJ:eJKleJ"

```

Try it online.
> 2 votes

# Answer
# Pyth, 23

```
*sX0ceJcz\:KvhJhtJgleJK

```

Unfortunately (in this scenario anyway), Pyth doesn't error on chopping a string by too large a value. Otherwise the check would go from 6 bytes to 2.

I'm unsure if this is the most optimal approach, but this chops the word after the number of characters from the input. Then it does a `+=` on the first element of the list and returns the sum. It multiplies the resulting string by a boolean representing if the value was out of range.

Also note that this does not work if the input is 0. The OP said we could assume the number is positive, so I believe this is ok.

Try it online
> 2 votes

# Answer
# Perl, 34 bytes

(includes 1 switch)

```
perl -pe '$x="."x$_;s/.*:(.*):($x)|.*/$2$1/'

```

Prints an empty line on error.
> 2 votes

# Answer
# C++11, 186 bytes

Golfed

```
#include<iostream>
#include<regex>
int main(){std::string p,w;int i,j;std::getline(std::cin>>i,p);j=p.find(58,1);w=p.substr(j+1);if(i<=w.length())std::cout<<w.insert(i,p.substr(1,j-1));}

```

Ungolfed

```
#include <iostream>
#include <regex>

int main()
{
    std::string p, w;
    int i, j;
    std::getline(std::cin >> i, p);
    j = p.find(':', 1);
    w = p.substr(j + 1);
    if (i <= w.length())
        std::cout << w.insert(i, p.substr(1, j - 1));
}

```

Looking for: Improvements and someone who can do Shakespear, so that I am not last again :)
> 1 votes

# Answer
# Retina, 38 bytes

```
(()1)*:(.+):((?<-2>.)*)(?!\2)|^.+
$4$3

```

Run the code from a single file with the `-s` flag. This takes input in unary, e.g.

```
111:A2C:Hello World!

```

yields

```
HelA2Clo World!

```

If the index is too large, an empty line will be printed.
> 1 votes

# Answer
# Haskell, 97 bytes

```
a=fmap tail.span(/=':')
m!(n,e)|m>length e=""|0<1=take m e++n++drop m e
f l|(o,r)<-a l=read o!a r

```

Defines `f`, a function that takes a string like `"2:x:ABC"` and returns `"ABxC"`.
> 1 votes

# Answer
# Julia, 66 bytes

```
s->(x=split(s,":");i=parse(Int,x[1]);x[3][1:i]*x[2]*x[3][i+1:end])

```

This creates an unnamed function that accepts a string and returns a string. It errors if the index is out of bounds.

Ungolfed:

```
function f(s::AbstractString)
    # Split the input on the colon
    x = split(s, ":")

    # Convert the first element of x to an integer
    i = parse(Int, x[1])

    # Join the pieces
    return x[3][1:i] * x[2] * x[3][i+1:end]
end

```
> 0 votes

# Answer
# Ruby, 55 bytes

```
a,b,c=gets.split ?:;(c[a,0]=b;p c)if c.size>=(a=a.to_i)

```

It's been a while since I've golfed in Ruby... this feels a bit suboptimal.
> 0 votes

# Answer
# Gema: 47 characters

```
*\:*\:*=@subst{<U$1>\*=\$1@quote{$2}\*\;\*=;$3}

```

Sample run:

```
bash-4.3$ gema '*\:*\:*=@subst{<U$1>\*=\$1@quote{$2}\*\;\*=;$3}' <<< '3:!*!:Hello'
Hel!*!lo

bash-4.3$ gema '*\:*\:*=@subst{<U$1>\*=\$1@quote{$2}\*\;\*=;$3}' <<< '13:!*!:Hello'

```

(If you want an explicit error message, just insert it after the last `=` sign.)
> 0 votes

# Answer
# MUMPS, 70 bytes

```
a(s) s w=$P(s,":",3) q:s>$L(w)  w $E(w,1,s)_$P(s,":",2)_$E(w,s+1,9**9)

```

There is no output if an invalid index is provided.

This code is *basically* ANSI-compliant; the only issue is that I've saved a byte by taking advantage of the fact that the maximum length of a string on the two major surviving MUMPS platforms is less than 99 bytes: InterSystems Caché caps strings at 32 KiB, and GT.M caps strings at 1 MiB. Nonetheless, in principle, some jerk could write an implementation that allows strings over ~369 MiB, in which case there would be valid inputs for which this code fails.

We can save 3 additional bytes, bringing us down to 67, if we use non-ANSI Caché ObjectScript-specific extensions to `$EXTRACT`:

```
a(s) s w=$P(s,":",3) q:s>$L(w)  w $E(w,1,s)_$P(s,":",2)_$E(w,s+1,*)

```
> 0 votes

# Answer
## Perl 6, 58 bytes

```
$_=[split ':',@*ARGS];substr-rw(.[2],.[0],0)=.[1];.[2].say

```
> 0 votes

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


title: An elementary challenge

text:
# Question
Title: An elementary challenge
This challenge is inspired by this Oliver Sacks quote:

> “At 11, I could say ‘I am sodium’ (Element 11), and now at 79, I am gold.” ― Oliver Sacks

I want you you find numbers in a string and replace them with their corresponding elements' symbols. (1 is H, 2 is He, 3 is Li, etc.) There are a few rules to follow:

* Single and double digits get replaced with their corresponding elements as normal. Ignore 0s at the start of numbers. If there are just 0s in a number, ignore it. E.g. `1 01 10 0 00` becomes `H H Ne 0 00`
* More than 2 digits together get divided into groups of 2. An odd number of digits should have the extra single digit at the end. E.g. `0153 5301 153` would become `HI IH PLi` Because of this rule, you will only need to know the elements from 1 to 99
* Numbers shall be treated the same no matter what characters surround them and commas and decimal points are not parts of numbers. `P90X
42,800 3.14159` would become `PThX Mo,Hg0 Li.SiPF`

Example Inputs/Outputs (I/O):

```
I: 32289216
O: GeNiUS

I: J08017 5811
O: JOHN CeNa

I: M18227 0592tt10r
O: MArTiN BUttNer

I: De072816
O: DeNNiS

I: D088r1907085
O: DOOrKNOB

I: 13ex A.
O: Alex A.

```

Input will be in the closest format to a string that your language has.

A periodic table for reference:

This is , so your program will be scored in bytes.

# Answer
> 7 votes
# Mathematica, ~~96~~ ~~94~~ 89 bytes

```
StringReplace[#,n:DigitCharacter~Repeated~2/;(d=FromDigits@n)>0:>d~ElementData~"Symbol"]&

```

Mma has several datasets...

# Answer
> 3 votes
# JavaScript (ES6), 202 bytes

```
x=>x.replace(/\d\d?/g,y=>+y?btoa`(139 bytes; see hexdump below)`.match(/[A-Z][a-z]?/g)[+y]:y)

```

The omitted string contains unprintable characters, so here is a (hopefully reversible) hexdump:

```
00000000: 0071 de2e 205e 0423 4e14 d78d 68c8 0095 288f  .qÞ. ^.#N.×.hÈ..(.
00000012: 4829 40ac a09a 49c4 e254 2acc 9c57 82a0 d882  H)@¬ .IÄâT*Ì.W. Ø.
00000024: b999 c668 6780 b127 81ac aad1 6d2a d866 b35b  ¹.Æhg.±'.¬ªÑm*Øf³[
00000036: 3284 dc46 e461 3dd0 2009 d227 4a74 9b4d e217  2.ÜFäa=Ð .Ò'Jt.Mâ.
00000048: 782b 0168 b682 78fa cd74 f992 984b 8675 36c3  x+.h¶.xúÍtù..K.u6Ã
0000005a: c87a 04ad 3998 6cbb 877d 3696 45e3 ac22 b3ed  Èz..9.l».}6.Eã¬"³í
0000006c: 02e1 e04e 53db 0623 e802 d467 16b4 5a01 c4e1  .áàNSÛ.#è.Ôg.´Z.Äá
0000007e: 3da5 0da4 fb80 9829 8190 27c4 b0              =¥.¤û..)..'Ä°

```

The technique here was to put all the element abbreviations in one string, separated by nothing—that's what the second regex `/[A-Z][a-z]?/g` is for; it matches each capital letter, optionally followed by a lowercase letter. The first regex, `/\d\d?/g`, matches each set of 2 (or 1) digits in the input, so this replaces each set of digits *N* with the element at index *N* in the decompressed, matched string.

Here's the original string, if anyone else would like to use it: (the `A`'s at the ends are fillers)

```
AHHeLiBeBCNOFNeNaMgAlSiPSClArKCaScTiVCrMnFeCoNiCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbTeIXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcThPaUNpPuAmCmBkCfEsA

```

Questions and suggestions welcome!

# Answer
> 1 votes
# Python 3, ~~278~~ 285 bytes

```
import re;f=lambda a:re.sub('(?!00)\d\d?',lambda m:'0HHLBBCNOFNNMASPSCAKCSTVCMFCNCZGGASBKRSYZNMTRRPACISSTIXCBLCPNPSEGTDHETYLHTWROIPAHTPBPARFRATPUNPACBCE  eie     eagli  lr aci rneoiunaeserrbr rbocuhdgdnnbe esaaerdmmudbyormbufa esrtuglbiotnracha pummkfs'[int(m.group())::100].strip(),a)

```

Test cases:

```
>>> f('32289216')
'GeNiUS'
>>> f('J08017 5811')
'JOHN CeNa'
>>> f('M18227 0592tt10r')
'MArTiN BUttNer'
>>> f('De072816')
'DeNNiS'
>>> f('D088r1907085')
'DOOrKNOB'
>>> f('13ex A.')
'Alex A.'
>>> f('P90X 42,800 3.14159')
'PThX Mo,Hg0 Li.SiPF'
>>> f('1 01 10 0 00')
'H H Ne 0 00'

```

# Answer
> 0 votes
# Python 2, ~~312~~ 304 bytes

```
import re
f=lambda a:''.join([j or'0HHLBBCNOFNNMASPSCAKCSTVCMFCNCZGGASBKRSYZNMTRRPACISSTIXCBLCPNPSEGTDHETYLHTWROIPAHTPBPARFRATPUNPACBCE0 eie     eagli  lr aci rneoiunaeserrbr rbocuhdgdnnbe esaaerdmmudbyormbufa esrtuglbiotnracha pummkfs'[int(i)::100].strip() for i,j in re.findall('(\d\d|[1-9])|(.)',a)])

```

This one creates a function **f** which takes a string of numbers as argument and returns the corresponding string with element symbols replaced.

The function iterates over strings of one to two digits (**'1'**, **'01'**, **'10'**, **'00'** but not **'0'**) or one character (**'a'**, **'0'** but not **'1'**). In the case of digits, the string is converted to an integer and looked up in a concatenated string of element symbols where each symbol is padded to two characters. In the case of characters, the string is simply used without lookup.

The tests for each example in the question all pass:

```
assert f('P90X 42,800 3.14159') == 'PThX Mo,Hg0 Li.SiPF'
assert f('1 01 10 0 00') == 'H H Ne 0 00'
assert f('0153 5301 153') == 'HI IH PLi'
assert f('32289216') == 'GeNiUS'
assert f('J08017 5811') == 'JOHN CeNa'
assert f('M18227 0592tt10r') == 'MArTiN BUttNer'
assert f('De072816') == 'DeNNiS'
assert f('D088r1907085') == 'DOOrKNOB'
assert f('13ex A.') == 'Alex A.'

```

---
Tags: code-golf, string, number, chemistry
---


title: The Combinatorics of Transistor

text:
# Question
Title: The Combinatorics of Transistor
The video game Transistor features a very interesting ability system. You collect 16 "Functions" which you can use in 16 different slots. What's interesting is that there are 3 types of slots and every Function behaves differently according to which slot you use it in:

* There are **4 Passive Slots**.
* There are **4 Active Slots**.
* **Each Active Slot** has **2 Upgrade Slots**.

We want to figure out how many different skill sets that gives us.

However, some combinations are equivalent. In particular, within each of those groups of slots, the specific position of a Function doesn't matter. On the other hand, the effect of a Function in an Upgrade Slot *does* depend on the specific Function used in the parent Active Slot.

Therefore, using hexadecimal digits to stand in for the Functions, the following combinations are all equivalent:

```
Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    2     0     1     3    # Permutation of passive slots.
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    0     1     2     3
Active Slots:     5     6     4     7    # Permutation of active slots together
Upgrade Slots:   A B   C D   8 9   E F   # with their upgrade slots.

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   B A   C D   F E   # Permutation within upgrade slots.

```

as well as any combination of these rearrangings. Note that in the third case the Upgrade Slots were swapped along with the Active Slots to maintain the same overall effect.

On the other hand, the following combinations are all different from the above set:

```
Passive Slots:    4     5     6     7    # Passive slots swapped
Active Slots:     0     1     2     3    # with active slots.
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    0     1     2     3
Active Slots:     5     4     6     7    # Permutation of active slots without
Upgrade Slots:   8 9   A B   C D   E F   # changing upgrade slots.

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 A   9 B   C D   E F   # Permutation between different upgrade slots.

```

By my count that gives you 2,270,268,000 possible (functionally distinct) combinations, assuming all Functions are used.

If you have less than 16 Functions at your disposal, some of the slots will remain empty. However, note that **you can't place a Function in an Upgrade Slot if the parent Active Slot is empty.**

## The Challenge

You're to determine the number of possible configurations depending on how many functions you have. Furthermore, I will generalise the problem slightly by making the number of slots variable, in order to prevent trivial hardcoding solutions.

Write a program or function which, given two positive integers `M ≥ 1` and `1 ≤ N ≤ 4M`, determines the number of possible (functionally distinct) skill sets assuming exactly `N` different Functions are used to fill as many as possible of `M` Passive, `M` Active and `2M` Upgrade Slots.

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

Your code must be able to handle any input up to and including `M = 8` within one minute on a reasonable desktop machine. There is some leeway in this, but it should rule out brute force solutions. In principle it should be no issue to solve any of those inputs in less than a second.

This is code golf, the shortest answer (in bytes) wins.

## Test Cases

Each test case is in the form `M N => Result`.

```
1 1 => 2
1 2 => 4
1 3 => 9
1 4 => 12
2 1 => 2
2 2 => 6
2 3 => 21
2 4 => 78
2 5 => 270
2 6 => 810
2 7 => 1890
2 8 => 2520
3 1 => 2
3 2 => 6
3 3 => 23
3 4 => 98
3 5 => 460
3 6 => 2210
3 7 => 10290
3 8 => 44520
3 9 => 168840
3 10 => 529200
3 11 => 1247400
3 12 => 1663200
4 1 => 2
4 2 => 6
4 3 => 23
4 4 => 100
4 5 => 490
4 6 => 2630
4 7 => 14875
4 8 => 86030
4 9 => 490140
4 10 => 2652300
4 11 => 13236300
4 12 => 59043600
4 13 => 227026800
4 14 => 718918200
4 15 => 1702701000
4 16 => 2270268000
5 1 => 2
5 2 => 6
5 3 => 23
5 4 => 100
5 5 => 492
5 6 => 2672
5 7 => 15694
5 8 => 98406
5 9 => 644868
5 10 => 4306932
5 11 => 28544670
5 12 => 182702520
5 13 => 1101620520
5 14 => 6122156040
5 15 => 30739428720
5 16 => 136670133600
5 17 => 524885961600
5 18 => 1667284819200
5 19 => 3959801445600
5 20 => 5279735260800
6 1 => 2
6 2 => 6
6 3 => 23
6 4 => 100
6 5 => 492
6 6 => 2674
6 7 => 15750
6 8 => 99862
6 9 => 674016
6 10 => 4787412
6 11 => 35304654
6 12 => 265314588
6 13 => 1989295308
6 14 => 14559228684
6 15 => 101830348620
6 16 => 667943115840
6 17 => 4042651092480
6 18 => 22264427465280
6 19 => 110258471363040
6 20 => 484855688116800
6 21 => 1854067032417600
6 22 => 5894824418683200
6 23 => 14025616720315200
6 24 => 18700822293753600
7 1 => 2
7 2 => 6
7 3 => 23
7 4 => 100
7 5 => 492
7 6 => 2674
7 7 => 15752
7 8 => 99934
7 9 => 676428
7 10 => 4849212
7 11 => 36601554
7 12 => 288486132
7 13 => 2349550632
7 14 => 19504692636
7 15 => 162272450340
7 16 => 1328431104000
7 17 => 10507447510560
7 18 => 78942848624640
7 19 => 554967220167360
7 20 => 3604592589998400
7 21 => 21411337810262400
7 22 => 115428212139240000
7 23 => 561247297649438400
7 24 => 2439121536313862400
7 25 => 9283622495827680000
7 26 => 29520583763711040000
7 27 => 70328449554723360000
7 28 => 93771266072964480000
8 1 => 2
8 2 => 6
8 3 => 23
8 4 => 100
8 5 => 492
8 6 => 2674
8 7 => 15752
8 8 => 99936
8 9 => 676518
8 10 => 4852992
8 11 => 36722169
8 12 => 291621462
8 13 => 2418755196
8 14 => 20834571186
8 15 => 184894557705
8 16 => 1672561326150
8 17 => 15217247948760
8 18 => 137122338089880
8 19 => 1204392465876600
8 20 => 10153538495100000
8 21 => 81007229522419200
8 22 => 604136189949692400
8 23 => 4168645459350372000
8 24 => 26403795950145213600
8 25 => 152700324078982680000
8 26 => 803784718213396920000
8 27 => 3838761204861983400000
8 28 => 16503742828841748480000
8 29 => 62545434470667308160000
8 30 => 198853691115980300400000
8 31 => 474189571122722254800000
8 32 => 632252761496963006400000

```

These are all the inputs your code has to handle within one minute (each), but it should in principle work for larger inputs. You can use some of the following `M = 10` test cases to check that:

```
10 1 => 2
10 2 => 6
10 3 => 23
10 4 => 100
10 5 => 492
10 6 => 2674
10 7 => 15752
10 8 => 99936
10 9 => 676520
10 10 => 4853104
10 11 => 36727966
10 12 => 291849866
10 13 => 2426074222
10 14 => 21033972388
10 15 => 189645995396
10 16 => 1773525588406
10 17 => 17155884420532
10 18 => 171073929494468
10 19 => 1750412561088334
10 20 => 18258387148774916
10 21 => 192475976310317700
10 22 => 2028834600633220380
10 23 => 21127206177119902860
10 24 => 214639961631544809360
10 25 => 2101478398293813739200
10 26 => 19602967930531817832000
10 27 => 172444768103233181556000
10 28 => 1417975382888905296456000
10 29 => 10820259026484304813416000
10 30 => 76213534343700480310584000
10 31 => 493916052421168703366040000
10 32 => 2941900199368102067135040000
10 33 => 16113144277547868007416960000
10 34 => 81222252655277786422930560000
10 35 => 376309102059179385262246080000
10 36 => 1589579966324953534441910400000
10 37 => 5981477408861097281112374400000
10 38 => 19005991357166148698688124800000
10 39 => 45381652832417130566255318400000
10 40 => 60508870443222840755007091200000

```

# Answer
## CJam (56 bytes)

```
q~4@:Nm*:$_&{:+1$\-N),&},f{1$1$:+-\0-:(_e`0f=+++:m!:/}:+

```

Online demo

This is an optimised version of the reference implementation I wrote for the sandbox. Note: I use `N` in the code because in a Real Combinatorics Question™ the parameters are \\$n\\$ and \\$k\\$, not `m` and `n`, but I'll use \\$M\\$ and \\$N\\$ in the explanation to avoid further confusion.

Suppose that we assign \\$X\\$ functions to the passive slots (where obviously \\$0 \le X \le M\\$). Then we have \\$N-X\\$ functions left for the active + upgrade slots (and we can choose those functions in \\$\frac{N!}{X!(N-X)!}\\$ ways). Because the order of the slot constellations is irrelevant, we want to consider each partition of \\$N-X\\$ into at most \\$M\\$ parts each of at most \\$3\\$ exactly once.

Take partition \\$λ\_0, λ\_1, \ldots, λ\_k\\$. We can assign \\$λ\_0\\$ parts to the first slot constellation, \\$λ\_1\\$ to the second, etc. in \\$\frac{(N-X)!}{λ\_0! λ\_1! ... λ\_k!}\\$ ways (multinomial), but we need to compensate for two factors. Firstly, if we have \\$λ\_i = λ\_j\\$ then the constellations are interchangeable, so we further divide by the factorials of the multiplicities of each part, \\$μ\_i\\$. (E.g. the partition `3 2 2 1` has \\$μ\_3 = 1\\$, \\$μ\_2 = 2\\$, \\$μ\_1 = 1\\$). Secondly, we have a designated "active" slot in each constellation, so for each \\$λ\_i\\$ we multiply by \\$λ\_i\\$ ways to select the active function.

So for each partition the number of distributions of functions is

$$\frac{N!}{X! (λ\_0-1)! \ldots (λ\_k-1)! μ\_1! μ\_2! μ\_3!}$$

The code above computes the partitions using the same approach as Dennis (it's obvious and short, although not very scalable) and then processes each partition into an array similar to `[N X λ_0-1 ... λ_k-1 μ_1 μ_2 μ_3]` over which it can lift the factorial function and then fold division.
> 20 votes

# Answer
# CJam, ~~74~~ 67 bytes

```
q~4@:Mm*:$L|{:+W$\-M),&},f{0-:F1@@{_m!\I-:Nm!/I(m!/*N}fI;Fm!Fe=/}:+

```

I've verified all test cases on my desktop computer using the Java interpreter. This took 2.2 seconds for **1 ≤ M ≤ 8** and 3.5 minutes for **M = 10**.

Try this fiddle in the CJam interpreter or verify the first 84 test cases at once.

### Idea

In principle, we can fill each active slot and its corresponding upgrade slots with **0**, **1**, **2** or **3** functions. For **4M** slots in total, we take all vectors **V** of **{0, 1, 2, 3}M** and filter out those for which **sum(V) \> N** (more functions in non-passive slots than total functions available) or **sum(V) + M \< N** (not enough passive slots for non-active functions). We sort and deduplicate all kept vectors, since the order of the slot families in not important.

With **N** functions and **V = (x1, …, xM)** functions in the non-passive parts of the slot families, we calculate the number of combinations as follows:

1. If **x1 = 0**, there is only one possibility for that slot family.

If **x1 = 1**, there are **N** possibilities, since we have **N** functions, and the function must go in the active slot.

If **x1 = 2**, we must place one function in the active slot and another in an upgrade slot (it doesn't matter which). There are **N** choices for the active slot and **N-1** remaining choices for the upgrade slot, giving a total of **N(N-1)** combinations.

If **x1 = 3**, there are **N** choices for the active slot, **N - 1** remaining choices for the first upgrade slot and **N - 2** for the second upgrade slot. Since the upgrade slots have no order, this counts every combination twice, so there are **N(N - 1)(N - 2)** unique combinations.

In any case, there are **N! / ((N - x1)! × (x1 \- 1)!** combinations for this family.
2. We have used up **x1** functions, so set **N := N - x1** and repeat step 1 for **x2**, then **x3**, etc.
3. If **V** contains duplicates, the product of the above results will have counted all combinations multiple times. For each unique element of **V**, if it occurs **r** times in **V**, there are **r!** equivalent ways to arrange these slot families, so the result from above must be devided by **r!**.
4. The final result is the number of unique combinations for that **V**.

To calculate the total number of unique combinations, all that's left to do is to compute the sum of the results for each **V**.

### Code

```
q~        e# Read an evaluate all input from STDIN. Pushes M and N.
4@:M      e# Push 4, rotate the M, and formally save it in M.
m*        e# Push {0, 1, 2, 3}^M.
:$        e# Sort each vector.
L|        e# Perform set union with the empty list (deduplicates).
{         e# For each sorted vector:
  :+      e#   Compute the sum of its coordinates.
  W$\-    e#   Subtract the sum from N (bottom of the stack).
  M),&    e#   Push [0 ... M] and intersect.
},        e# If the intersection was not empty, keep the vector.
f{        e# For each kept vector, push N and V; then:
  0-:F    e#   Save the non-zero elements of V in F.
  1@@     e#   Push 1 (accumulator), and rotate N and F on top of it.
  {       e#   For each I in F:
    _m!   e#     Push I and push factorial(I).
    \I-:N e#     Subtract I from N and update N.
    m!/   e#     Divide factorial(N) (original N) by factorial(N) (updated N).
    I(m!/ e#     Divide the quotient by factorial(I - 1).
    *     e#    Multiply the accumulator by the resulting quotient.
    N     e#    Push N for the next iteration.
  }fI     e#
  ;       e#   Pop N.
  Fm!     e#   Push all non-unique permutations of F.
  Fe=     e#   Count the number of times F appears.
  /       e#   Divide the accumulator by the result.
}         e#
:+        e# Add all resulting quotients.

```
> 9 votes

---
Tags: code-golf, combinatorics, game, permutations, restricted-time
---