title: The Doughnut Shop™

text:
# Question
Title: The Doughnut Shop™
Being short of cash, you have signed up to build donuts for The Doughnut Shop™, the biggest digital doughnut company in the world, mostly because they sell every size of doughnut imaginable.

Now, given that trading standards nowadays is very tough, you need to write a piece of code as short as possible to create these doughnuts so that the source code that created them can be put on the outside of the packet.

# Challenge

Given 4 inputs, radius of the outer ring, radius of the inner ring, the possible sprinkles and the chance of a cell having a sprinkle, output a doughnut covered in those sprinkles which has the correct inner and outer radii.

* The input may be taken how you wish (arguments to a function, stdin, program arguments) and in any order.
    + The sprinkles will be given in the form of 1 character per sprinkle type
    + `^+*-` as sprinkle input would be a list of 4 sprinkles, `^`, `+`, `*`, `-`
    + The chance of a sprinkle will be entered as a floating point value between 0 and 1. eg: `0.1`, `0.23`
* You must print out the output to stdout or equivalent.
* Sprinkles can't be on the edges of the doughnut.
* Each type of sprinkle must have an equally likely chance of being on each cell.
* The radii are given in 1-cell units.
* If the inner radius equals either 0 OR the outer radius, the doughnut is said to have no ring.
* Both radii will be non-negative integers.
* The inner and outer edges of the doughnut must be represented using hashes (`#`)
* A test to see if a point is in a circle, given a radius and the center of the circle is:

`(x-center)**2+(y-center)**2 < radius**2`

### Example input with output

(outer radius, inner radius, sprinkles, chance of sprinkle)

* 10, 4, "^+\*-", 0.1

```
     #########
    #         #
  ##  ++   *  *##
  #             #
 #       ^^ - *  #
#      #####   ^  #
#+    #     #     #
#    #       #-   #
#    #       #  * #
#    #       #+   #
#    #       #    #
#^  +#       #    #
#     #     #     #
# *    #####      #
 #       +  -    #
  #        ^    #
  ##  ^  +     ##
    #       ^ #
     #########

```
* 5, 2, ":^+\*", 0.9

```
  #####
 #^^+ ^#
#**###  #
#:#   #^#
#^#   #*#
#:#   #*#
#:+###* #
 # *:^:#
  #####

```

**This is code golf, the shortest answer in bytes wins**

# Answer
## MATLAB, 231 bytes

Here a matlab solution:

```
function g=z(r,q,s,p);[x,y]=meshgrid(1:2*r,1:2*r);d=(x-r).^2+(y-r).^2;h=size(d);e=zeros(h);e(d<r^2 & d>=q^2)=1;f=bwperim(e,4);k=rand(h);j=numel(s);l=changem(randi(j,h),s,1:j);g=char(e);g(:,:)=' ';g(k<=p)=l(k<=p);g(f)='#';g(~e)=' ';

```

Some examples:

```
>> z(10, 4, '^+*-', 0.1)

ans =

     #########
    #         #
  ##           ##
  #    -       -#
 #               #
#   -  #####    ^ #
#     #     #     #
#   -#       #    #
# *  #       #+   #
#**  #       #    #
#  * #       # -  #
#+  *#       #    #
#     #     #     #
#      #####      #
 #           ^   #
  #     *       #
  ##+          ##
    #         #
     #########

>> z(5, 2, ':^+*', 0.9)

ans =

  #####
 #++::*#
#^^###++#
# #   #+#
#^#   #^#
#*#   #*#
#+:###^*#
 #*:^+^#
  #####

>> z(20,6, 'erthhjjjjkjkk', 0.4)

ans =

             #############
           ##jh  k  k  k  ##
         ##  jjj    j khh   ##
        #r kj h   k tjhj j    #
      ##jk    t k  jh j       h##
     #k       rre            k j #
    # j   j j  j  khtkt jr     kj #
    #  k   rk je    j      h   j  #
   # j   k   k  jth e k j   j    j #
  #h   h h e     t e ej  j  r k r e #
  #    j   r  jh  jk     j  kk   j  #
 #      k     k    h k  jk     k j   #
 #  jjk   hh k hj  r  j  je rjj k j  #
#  ek  j j jj  h#######          hke  #
#hj      k j j #       #ke jhkt  jee  #
#        jk  k#         # k    j   t  #
#k        j  #           #khk  r     j#
#   tj  j te #           # j  r j j   #
#e   je   jhk#           #        t j #
#jj    j  h  #           #     k jj e #
# j j   hj j #           # jkt kjjjr e#
#j k    e    #           #       r   k#
#jj  k    ek #           # hj  j rtj  #
#   k j   hk h#         #     j  h j  #
#   h trt  jrht#       #   et        k#
#j  ehjj      j #######ett  kh kjj k  #
 #   r  jj    ekk jk    th k   kkk h #
 #hj       khe kj hr  jj   kk  r j   #
  #r t    k j  k r  j  jk k hh    jj#
  #  kjj  h k j       j rrr j  r j  #
   #j kej  jj    t       h  j   hh #
    #  he   e  tje j  tjhkjk kj   #
    #j kt rjk    j j  ee    rkj   #
     #   jjr e  j jkt j   e  j  j#
      ##k  thhjj je   kj  kh   ##
        # hje  j     jj kk t j#
         ## k       h     e ##
           ## e jje   kkhj##
             #############

```
> 2 votes

# Answer
# Python, 263 bytes

So I saw a challenge with no answers that looked relatively easy but also interesting and thought to myself:

*Hmm... If I'm the only one with an answer, I'll be winning until a better answer inevitably shows up.*

So I sat down with Python for a few minutes and came up with a rough draft which, with the help of the community's suggestions, I have been tweaking to reduce its size.

```
from random import*
def D(O,I,S,P):
 a=range(-O,O+1);C=lambda x,y,z,n:(n-.5)**2<x*x+y*y<(z+.5)**2
 if I>=O:I=0
 for y in a:
  R=''
  for x in a:
   if C(x,y,O,O)+(C(x,y,I,I)&(I!=0)):R+='#'
   elif C(x,y,O,I)&(uniform(0,1)<P):R+=choice(s)
   else:R+=' '
  print(R)

```

For the examples above, this creates

```
>>> D(10, 4, "^+*-", 0.1)
       #######
     ##       ##
    #         * #
   #             #
  #          + ^  #
 # +               #
 #   + +#####   -  #
#      ##   ##    ^ #
#     ##     ##  *  #
#-    #       #     #
#     #       #  +  #
# +   #       #     #
#     ##     ##     #
#      ##   ##  *   #
 #+-    #####      #
 #             - - #
  #   -    -     +#
   #      ^      #
    # -    +    #
     ## *     ##
       #######
>>>

```

and

```
>>> D(5, 2, ":^+*", 0.9)
   #####
  #*^:* #
 #^::*:^*#
#* :###+*:#
#:*#   #+:#
#::#   #+ #
#+:#   #*:#
#^^:###::^#
 # + :*^ #
  # *:+*#
   #####
>>>

```

I highly doubt that this is the shortest possible solution, but I think it worked out pretty well for a self-taught teenager's attempt to kill time. Since this was designed to be as small as possible, I have not included comments and have taken shortcuts on every variable name and as such, this program is more for usability than readability.

Should you want to use this code for some reason unbeknownst to me, just run it in IDLE and type the command

```
D(Outer Radius, Inner Radius, Sprinkles, Chance of Sprinkle)

```

in the format described above.
> 8 votes

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


title: Falling ASCII balls

text:
# Question
Title: Falling ASCII balls
## Input

You are given a 2D map with balls and ground in it. It looks like this:

```
  1         5          2
                 3
     4

__________________________

```

Each number is a ball, and the `_` is ground level. The underscore `_` character is not allowed in any other line than ground level line. There are only spaces, newlines and digits `0-9` allowed above ground level. You cannot assume that last line is the ground level - empty lines below ground level are allowed. You can also add spaces, to fill empty lines, if that does help you.

Balls can have numbers from `0` to `9`, can be placed above each other, but not under ground. The ball's numbers will be unique.

Assume that each character is **one meter**.

Get map from pastebin!
Test case 1 \- should output something like this
Test case 2 \- should produce same results as first map

## Challenge

Your challenge is to read a map like that from a file or from `stdin` — you are allowed to use `cat balls.txt | ./yourexecutable` — and output velocity of each ball when it hits the ground.

Here's the formula for velocity:

Assume that `h` is the line number difference between the ground's line number, and the ball's line number, and that `g` equals `10m/s^2`.

## Output

You should output each balls number and velocity in `m/s` at ground level. For example `N - Vm/s`, where `N` is ball number and `V` is its velocity. You can also output an array if you want.

Happy coding! :)

# Answer
> 8 votes
# MATL, ~~31~~ ~~30~~ ~~27~~ 25 bytes

```
95\16\5B#fG&X>1)b- 20*X^h

```

Input is a 2D char array with `;` as row separator:

```
['  1         5          2  ';'                 3        ';'     4                    ';'                          ';'                          ';'__________________________']

```

Try it online! Or include an initial `t` in the code to display the map for greater clarity.

Here are the other test cases: first, second.

### Explanation

```
95\      % Take input implicitly. Modulo 95: convert to numbers and map '_' into 0
16\      % Modulo 16: map space into 0 and digit chars into corresponding numbers
5B#f     % Find row indices and values of nonzero entries
G        % Push input again
&X>      % Index of maximum of each column. This finds character '_'
1)       % Get first value (they are all equal)
b        % Bubble row indices of numbers up in the stack
-        % Subtract to get distance from each number to the ground
20*X^    % Multiply by 20, take sqrt. This gives the velocity values
h        % Horizontally concat numbers and velocities. Display implicitly

```

# Answer
> 7 votes
# C, 125 122 121 bytes

```
b[99]={};main(l,c){for(;(c=getchar())<95u;)b[c]=(l+=c==10);for(c=47;++c<58;)b[c]&&printf("%c,%f\n",c,sqrt((l-b[c])*20));}

```

Compile & run with `gcc -w golf.c -lm && cat balls.txt | ./a.out`.

# Answer
> 6 votes
# C -~~194(-5)~~ ~~150~~ 137 bytes

*With a little bit more time and thinking, I golfed off 44 bytes*
*Thanks to **orlp** for helping me to save 13 bytes*

I'll start with my C code:

```
b[256]={},n,i=47;main(l,c){for(;~(c=getchar());n=c==95?l:n)b[c]=(l+=c==10);for(;++i<58;)b[i]&&printf("%d %f\n",i-48,sqrt((n-b[i])*20));}

```

And human readable version:

```
//Throws many warnings, but lack of libraries is tolerated

/*
    c - current character
    l - line number (starts at 1)
    n - ground level
    i - iterator
    b - balls array
*/

b[256] = {}, n, i = 47; //That actually works, as long as you are using ASCII

main( l, c )
{
    for ( ;~( c = getchar( ) ); n = c == 95 ? l : n ) //Read stdin and search for ground
        b[c] = ( l += c == 10 ); //Increment lines counter on newlines, and save line numbers

    for ( ; ++i < 58; ) //Iterate through balls
        b[i] && printf( "%d %f\n", i - 48, sqrt( ( n - b[i] ) * 20 ) ); //Print out data
}

```

Compile and run like that: `gcc -o balls ballsgolf.c -lm && cat 1.txt | ./balls`

## Output

```
1 10.000000
2 10.000000
3 8.944272
4 7.745967
5 10.000000

```

# Answer
> 4 votes
# Pyth, ~~27~~ ~~26~~ ~~25~~ 24 bytes

```
~~smf-hT" _".e,b@*20-xd\_k2dC~~
~~smf@hT`M;.e,b@*20-xd\_k2dC~~
~~smf@T`M;.e,b@*20-xd\_k2dC~~
sm@#`M;.e,b@*20-xd\_k2dC

```

Try it online!

# Answer
> 3 votes
## Matlab, ~~100~~ ~~96~~ ~~89~~ 90 bytes

```
s=input('');X=find(s==95);for i=0:9
[x y]=find(s==48+i);if(x)[i sqrt(20*(X(1)-x))]
end
end

```

Many bytes saved thanks to Luis Mendo

Input format:

```
['  1         9          2  ';'                 3        ';'     4                    ';'                          ';'                          ';'__________________________']

```

**Explanation:**

```
X=find(s==95)         -- finds '_', we'll need X(1) to determine max height
for i=0:9             -- loops through balls' numbers
[x y]=find(s==48+i)   -- finds the ball
if(x)                 -- if it is present
[i sqrt(20*(X(1)-x))] -- output its number and velocity

```

# Answer
> 3 votes
## Python 3, 84 bytes

Version 6, 84 bytes: (Thanks to Leaky Nun!)

```
lambda a:[(c,(~-(len(a)-i)*20)**.5)for i,s in enumerate(a)for c in s if c.isdigit()]

```

Version 5, 91 bytes:

```
lambda a:[c+":"+str((~-(len(a)-i)*20)**.5)for i,s in enumerate(a)for c in s if c.isdigit()]

```

Version 4, 92 bytes:

```
lambda i:[c+":"+str((~-(len(i)-n)*20)**.5)for n in range(len(i))for c in i[n]if c.isdigit()]

```

Version 3, 99 bytes:

```
def r(i):x=len(i);print([c+":"+str((~-(x-n)*20)**.5)for n in range(x)for c in i[n] if c.isdigit()])

```

Version 2, 102 bytes:

```
def r(i):
 n=len(i)
 for l in i:
  for c in l:
   if c.isdigit():print(c+":"+str((~-n*20)**.5))
  n-=1

```

The above versions take an array of strings as input.

Version 1, 140 bytes:

```
with open(input(),"r")as i:
 n=sum(1for l in i);i.seek(0)
 for l in i:
  for c in l:
   if c.isdigit():print(c+":"+str((~-n*20)**.5))
  n-=1

```

This takes the directory of the file as input from the user.

# Answer
> 2 votes
# Python 3, 84 bytes

```
lambda x:[[i,(20*x[x.find(i):x.find('_')].count('\n'))**.5]for i in x if i.isdigit()]

```

An anonymous function that accepts input by argument as a multi-line string with all empty lines filled with spaces, and returns an array where each element is of the form \[ball number, speed\].

**How it works**

```
lambda x                      Function with input x
...for i in x if i.isdigit()  Loop through all characters i in x for which i is a digit,
                              and hence one of the balls
x[x.find(i):x.find('_')]      Slice x to give the substring between the ball and the ground
....count('\n')               Count the number of newlines in the substring to give the
                              height of the ball
(20*...)**.5                  Calculate the speed of the ball as it hits the ground
[i,...]                       Package the ball number and speed into a list
:[...]                        Return all ball-speed pairs as a list with elements [ball
                              number, speed]

```

Try it on Ideone

# Answer
> 2 votes
# JavaScript (ES6) 93

*Edit* 2 bytes saved thx @Jacajack

A function with a multiline string as input parameter. Output is not sorted (as this in not requested)

```
a=>[...a].reverse().map(c=>c>'Z'?b=i:c<' '?++i:c>' '&&console.log(c,Math.sqrt((i-b)*20)),i=0)

```

**Test**

```
F=
a=>[...a].reverse().map(c=>c>'Z'?b=i:c<' '?++i:c>' '&&console.log(c,Math.sqrt((i-b)*20)),i=0)

function test()
{
  F(I.value);
}

test()
```

```
#I { height: 12em; width: 30em}
```

```
<textarea id=I>

  1         5          2
                 3
     4

__________________________

</textarea>
<button onclick="test()"></button>
```

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


# Question
Title: Ninja Assassins - which ninja stays alive?
## Ninja Assassins - which ninja stays alive

**some basic information**

* given an int N as the number of ninjas, return the number of the winning ninja.
* At the end only 1 ninja survives,the question is which one? what was his number?.
* Each ninja kills the ninja who stands after him. Afterwards, he passes the sword to the first alive ninja who stood after the killed one.

## **Explenation - How the Game Works**

The ninjas are numbered from 1 to N and stand in a circle according to the numbers. The circle goes clockwise: ninja 2 is left to ninja 1, ninja 3 is left to ninja 2, ninja 4 is left to ninja 3.... ninja 1 is left to ninja N.
Ninja 1 gets a sword and the game begins:
Each ninja (starting from ninja 1) kills the closest and alive ninja he has to the left (clockwise) . Afterwards, he passes the sword to the 2nd closest and alive ninja he has to the left.The 2nd ninja does the same (kills and passes) (as an example: N=3(we have 3 ninjas), ninja 1 kills ninja 2 and gives the sword to ninja 3. Ninja 3 has ninja 1 as his closest and alive ninja to the left(clockwise - its a circle) so he kills ninja 1, stays the last ninja alive and wins (so the output\return is 3, as the number of the ninja)).
**A more detailed example below**

## Example - Word-detailed scenario

**N = 7 (we got 7 ninjas) :**

```
1 2 3 4 5 6 7 (L=alive, D=dead)
L D L L L L L The first ninja gets the sword and kills the 2nd ninja.
              The first ninja passes the sword to the 3rd ninja.
L D L D L L L The 3rd ninja gets the sword and kills the 4th ninja.
              The 3rd Ninja passes the sword to the 5th ninja.
L D L D L D L The 5th ninja gets the sword and kills the 6th ninja.
              The 5th Ninja passes the sword to the 7th ninja.
D D L D L D L The 7th ninja gets the sword and kills the first(1st) ninja.
              The 7th ninja passes the sword to the 3rd ninja.
D D L D D D L The 3rd ninja gets the sword and kills the 5th ninja.
              The 3rd ninja passes the sword to the 7th ninja.
D D D D D D L The 7th ninja gets the sword and kills the 3rd ninja,
              stays as the last one alive and wins (the final result /
              the output is 7).

```

## More scenarios without words

**N=3 :** 1 2 3 - 1 3 - 3 wins
**N=4 :** 1 2 3 4 - 1 3 - 1 wins
**N=5 :** 1 2 3 4 5 - 1 3 5 - 3 5 - 3 wins
**N=6 :** 1 2 3 4 5 6 - 1 3 5 - 1 5 - 5 wins
**N=7 :** 1 2 3 4 5 6 7 - 1 3 5 7 - 3 7 - 7 wins

**Scoring is based on the least number of bytes used, as this is a code-golf question.**

# Answer
## Python 2, 30 bytes

```
lambda n:int(bin(n)[3:]+'1',2)

```

Takes the binary expansion of `n` and moves the initial `1` to the end.
> 8 votes

# Answer
## Python 2, 32 bytes

```
a=lambda n:n and(n%2+a(n/2))*2-1

```

---

**33 bytes:**

```
a=lambda n:n and 2*a(n/2)-(-1)**n

```

Uses the recursive formula on the OEIS page.

* `a(2*n) = 2*a(n)-1`
* `a(2*n+1) = 2*a(n)+1`
> 4 votes

# Answer
## Java 7, ~~65~~ 53 bytes

```
int f(int n){return(n-Integer.highestOneBit(n))*2+1;}

```

Using the algorithm for k=2 Josephus from Wikipedia. Thanks to Leaky Nun for finding the builtin.
> 2 votes

# Answer
# Pyth, ~~22~~ ~~13~~ ~~12~~ 9 bytes

Credits to Geobit's algorithm for saving 9 bytes. It works like magic.

Credits to xnor's witchcraft for saving 3 bytes. It is simply witchcraft.

```
~~heu+G=Z%e.f!/G%ZQ2ZQQY~~
~~u?sIlH1+2GSQ1~~
~~hyaefgQT^L2~~
i.<.BQ1 2

```

Test suite.
> 2 votes

# Answer
# Jelly, 4 bytes

Since xnor came up with this algorithm, I will make this community wiki.

```
Bṙ1Ḅ

```

Try it online!

## Explanation

```
Bṙ1Ḅ
B     convert to binary
 ṙ1   left-rotate by 1
   Ḅ  convert from binary

```
> 2 votes

# Answer
# VBA, 57 67 bytes

Well, this technically ought to work (57 bytes):

```
Function Z(N):Z=2*(N-2^Int(Log(N)/Log(2)))+1:End Function

```

But actually, because occasionally the log value of a power of two is not quite an exact multiple of the log of 2, we need a few more bytes:

```
Function Z(N):Z=2*(N-2^Int(Log(N)/Log(2))):Z=1-Z*(Z<N):End Function

```

If there were a built-in binary converter, it would be much shorter.

The recursion version is a tie, basically, but needs a line-feed for the IF

```
Function Y(N):Y=1:If N>1 Then Y=2*Y(N\2)+2*(N\2=N/2)+1
End Function

```
> 1 votes

# Answer
# J, 10 bytes

```
(1&|.)&.#:

```

Using the formula where *a*(*n*) = *n* written in binary and rotated left by 1 place. Similar to what is used in @xnor's solution.

Using **19 bytes**, we can play the game according to the rules in the challenge.

```
[:(2&}.,{.)^:_>:@i.

```

This solution only performs array manipulation in order to reach a final player.

## Usage

Extra commands used for formatting multiple input/output with multiple functions.

```
   f =: (1&|.)&.#:
   g =: [:(2&}.,{.)^:_>:@i.
   (,.f"0,.g"0) i. 10
0 0 0
1 1 1
2 1 1
3 3 3
4 1 1
5 3 3
6 5 5
7 7 7
8 1 1
9 3 3

```

## Explanation

```
(1&|.)&.#:  Input: n
        #:  Convert to binary
(    )&.    Compose next function on the binary value
 1&|.       Rotate left by 1 place
(    )&.    Compose the inverse of the previous function on the result
        #:  The inverse: convert from binary to decimal and return result

[:(2&}.,{.)^:_>:@i.  Input: n
                 i.  Creates the range [0, 1, ..., n-1]
              >:@    Increment each in the range to get [1, 2, ..., n]
[:(       )^:_       Nest the function until the result does not change and return
   2&}.              Drop the first two items in the list
        {.           Get the head of the list
       ,             Join them together. This makes it so that the head of the list
                     is always the current player and the one after the head is the
                     player to be removed

```
> 0 votes

# Answer
## Python, 29 bytes

```
f=lambda n:n&n-1<1or f(n-1)+2

```

Outputs 1 as `True` when `n` is a power of 2, checked by `n&n-1` being 0. Otherwise, outputs `2` higher than the previous value.

---

**28 bytes:**

Adapting grc's general solution to the case `k=2` gives a better solution

```
f=lambda n:n and-~f(n-1)%n+1

```

Rather than explicitly checking for powers of `2`, it zeroes out the result before incrementing each time `f(n-1)` catches up to `n-1`
> 0 votes

---
Tags: code-golf
---


title: Exploded substrings

text:
# Question
Title: Exploded substrings
### Introduction

Let's observe the string `abc`. The substrings that can be made from this are:

```
a, ab, abc, b, bc, c

```

We now need to align them under the initial string, like this:

```
abc
a
 b
  c
ab
 bc
abc

```

The order of the string doesn't matter, so this is also perfectly valid:

```
abc
a
ab
abc
 b
 bc
  c

```

So, the substring is positioned under the location of the substring in the initial string. So for `abcdef` and the substring `cde`, it would look like this:

```
abcdef
  cde

```

### The Task

The task is to align all substrings **with a length greater than 0**, like shown above. You can assume that the string itself will only contain **alphabetic characters** and has at least 1 character. For the padding, you can use a space or some other non-alphabetic printable ASCII character (`32 - 127`). Maybe not necessary to mention, but the string itself will only contain unique characters, so not like `aba`, since the `a` occurs twice.

### Test cases

Input: `abcde`

Possible output:

```
a
ab
abc
abcd
abcde
 b
 bc
 bcd
 bcde
  c
  cd
  cde
   d
   de
    e

```

Input: `abcdefghij`

Possible output:

```
a
ab
abc
abcd
abcde
abcdef
abcdefg
abcdefgh
abcdefghi
abcdefghij
 b
 bc
 bcd
 bcde
 bcdef
 bcdefg
 bcdefgh
 bcdefghi
 bcdefghij
  c
  cd
  cde
  cdef
  cdefg
  cdefgh
  cdefghi
  cdefghij
   d
   de
   def
   defg
   defgh
   defghi
   defghij
    e
    ef
    efg
    efgh
    efghi
    efghij
     f
     fg
     fgh
     fghi
     fghij
      g
      gh
      ghi
      ghij
       h
       hi
       hij
        i
        ij
         j

```

This is , so the submission with the least amount of bytes wins!

# Answer
> 13 votes
# Pyth, ~~14~~ ~~13~~ 10 bytes

*Thanks to* @FryAmTheEggman *for saving 3 bytes.*

```
jmXQ-Qd;.:

```

Try it online!

# Answer
> 22 votes
# Perl, ~~32~~ ~~28~~ 24 bytes

Includes +1 for `-n`

Code:

```
/.+(??{say$"x"@-".$&})/

```

Run with the string on STDIN:

```
perl -nE '/.+(??{say$"x"@-".$&})/' <<< abcd

```

The golfing languages are so close and yet so far away...

## Explanation

`/.+/` matches a substring. Unfortunately it stops once it matched one. So I use the runtime regex construct `(??{})` to extend the regex so it fails and backtracking will try the following substring, in the end trying them all before giving up in disgust.

Inside the `(??{})` I print the current substring prefixed by as many spaces as the offset of the substring using `$"x"@-"`

So the output neatly documents how regex backtracking works:

```
abcd
abc
ab
a
 bcd
 bc
 b
  cd
  c
   d

```

# Answer
> 14 votes
# MATL, ~~20~~ 18 bytes

*Inspired by the pattern of substrings generated by @aditsu's answer*

```
tt!+gR*c`t3Lt3$)tn

```

**Try it online!**

The pattern of substrings is generated by an upper triangular matrix the same size as the input, and all submatrices obtained by successively removing the last row and column.

**Explanation**

```
t         % implicit input. Duplicate
t!+g      % square matrix with size as input
R         % keep upper triangular part
*c        % multiply element-wise with broadcast. Convert to char
`         % do...while
  t       %   duplicate
  3Lt3$)  %   remove last row and column
  tn      %   number of remaining elements. Used as loop condition
          % implicitly end loop and display

```

---

### Old approach (Cartesian power)

*I'm keeping this approach in case it serves as inspiration for other answers*

```
tn0:2Z^!S!2\Xu4LY)*c

```

In the online compiler this runs out of memory for the longest test case.

**Try it online!**

**Explanation**

This generates all patterns of values `0`, `1` and `2` in increasing order, and then transforms `2` into `0`. This gives all possible patterns of `0` and `1` where the `1` values are contiguous. These are used to mark which characters are taken from the original string.

As an example, for string `'abc'` the patterns are generated as follows. First the Cartesian power of `[0 1 2]` raised to the number of input characters is obtained:

```
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
···
2 2 1
2 2 2

```

Sorting each row gives

```
0 0 0
0 0 1
0 0 2
0 0 1
0 1 1
···
1 2 2
2 2 2

```

Transforming `2` into `0` (i.e. `mod(...,2)`) and removing duplicate rows gives the final pattern

```
0 0 0
0 0 1
0 1 1
0 1 0
1 1 1
1 1 0
1 0 0

```

in which each row is a mask corresponding to a (contiguous) substring. The first row needs to be removed because it corresponds to the empty substring.

```
t      % Implicitly get input. Duplicate
n      % Number of elements
0:2    % Vector [0 1 2]
Z^     % Cartesian power. Each result is a row
!S!    % Sort each row
2\     % Modulo 2: transform 2 into 0
Xu     % Unique rows
4LY)   % Remove first (corresponds to the empty substring)
*      % Element-wise multiplication by original string
c      % Convert to char. Implicitly display

```

# Answer
> 14 votes
## Retina, ~~48~~ ~~32~~ 31 bytes

*Thanks to Kenny Lau for saving 3 bytes and paving the way for many more.*

Byte count assumes ISO 8859-1 encoding.

```
M&!r`.+
%+`( *)\S(.+)$
$&¶$1 $2

```

Try it online!

Order of the generated substrings:

```
abcde
 bcde
  cde
   de
    e
abcd
 bcd
  cd
   d
abc
 bc
  c
ab
 b
a

```

### Explanation

```
M&!r`.+

```

This gets us all the prefixes of the input. This is done by matching (`M`) any substring (`.+`) starting from the end (`r`), considering overlapping matches (`&`) and returning all of those matches joined with linefeeds (`!`).

Now all we need to do is carve out the successive prefixes *of those prefixes* (by replacing them with spaces). We do this step by step with a loop:

```
%+`( *)\S(.+)$
$&¶$1 $2

```

The `%` means that this entire thing is done to each line individually (considering it a separate string for time being, and joining it all back together with linefeeds at the end). The `+` tells Retina to run this substitution in a loop until the output stops changing (which in this case means that the regex no longer matches). The regex then tries to match the last line of the input with at least two non-space characters, and appends a new row where the first of those is replaced with a space.

# Answer
> 11 votes
# Oracle SQL 11.2, 146 bytes

```
WITH v AS(SELECT LEVEL i FROM DUAL CONNECT BY LEVEL<=LENGTH(:1))SELECT LPAD(SUBSTR(:1,s.i,l.i),s.i+l.i-1)FROM v s,v l WHERE s.i+l.i<=LENGTH(:1)+1;

```

Un-golfed

```
WITH v AS(SELECT LEVEL i FROM DUAL CONNECT BY LEVEL<=LENGTH(:1))
SELECT LPAD(SUBSTR(:1,s.i,l.i),s.i+l.i-1)
FROM   v s, v l
WHERE  s.i+l.i<=LENGTH(:1)+1

```

# Answer
> 9 votes
# CJam, 20

```
q{__,{\_N+oSt}/;W<}h

```

Try it online

**Explanation:**

```
q           read the input (initial string)
{…}h        do … while
  _         copy the current string
  _,        copy and get the length
  {…}/      for each value (say i) from 0 to length-1
    \       bring the string to the top
    _N+o    make a copy, append a newline and print
    St      set the i'th element to S=" "
  ;         pop the last result (array full of spaces)
  W<        remove the last character of the current string
             if the string is empty, the do-while loop terminates

```

# Answer
> 8 votes
## Python, 57 bytes

```
f=lambda s,p='':set(s)and{p+s}|f(s[1:],' '+p)|f(s[:-1],p)

```

Outputs a `set` like `{' b', 'a', 'ab'}`. The idea is to recurse down two branched that cut off the first or last character. The gives redundant outputs, but the `set` automatically removes duplicates. For alignment, every time the first character is cut off, a space is added to the prefix `p`, which is concatenated onto the front.

# Answer
> 7 votes
## C#, ~~136~~ ~~132~~ 131 bytes

---

**Golfed**

```
String m(String s){String o="",e=o;for(int i=0,a,l=s.Length;i<l;i++,e+=" ")for(a=1;a+i<=l;a++)o+=e+s.Substring(i,a)+"\n";return o;}

```

---

**Ungolfed**

```
String m( String s ) {
    String o = "", e = o;

    for (int i = 0, a, l = s.Length; i < l; i++, e += " ")
        for (a = 1; a + i <= l; a++)
            o += e + s.Substring( i, a ) + "\n";

    return o;
}

```

---

**Full code**

```
    using System;
using System.Collections.Generic;

namespace Namespace {
    class Program {
        static void Main( string[] args ) {
            List<String> ls = new List<String>() {
                    "abcde",
                    "abcdefghijklmnop",
                    "0123456789",
                };

            foreach (String s in ls) {
                Console.WriteLine( s );
                Console.WriteLine( m( s ) );
                Console.WriteLine( "" );
            }

            Console.ReadLine();
        }

        static String m( String s ) {
            String o = "", e = o;

            for (int i = 0, a, l = s.Length; i < l; i++, e += " ")
                for (a = 1; a + i <= l; a++)
                    o += e + s.Substring( i, a ) + "\n";

            return o;
        }
    }
}

```

---

**Releases**

* **v1.2** \- `-1 byte` \- Changed the `String o="",e="";` to `String o="",e=o;` to save 1 byte. The idea was from Gallant ( *I forgot to apply this part in the last update, I apologize.* ).
* **v1.1** \-  `-4 bytes` \- Droped the brackets from the `for` loops and moved the `e` var *space increment* to the iterator zone of the outer `for` loop. The idea was from Gallant.
* **v1.0** \- `136 bytes` \- Initial solution.

# Answer
> 7 votes
## PowerShell v2+, 69 bytes

```
param($a)0..($b=$a.length-1)|%{($i=$_)..$b|%{" "*$i+-join$a[$i..$_]}}

```

Takes input `$a`, loops over the length (setting `$b` in the process for use later). Each outer loop, we loop up to `$b` again, setting `$i` for use later. Each inner loop, we output `$i` number of spaces concatenated with a slice of the input string. Since we're just looping through the string, this will actually handle any arbitrary string (duplicate letters, spaces, whatever).

### Example

```
PS C:\Tools\Scripts\golfing> .\exploded-substrings.ps1 "Golfing"
G
Go
Gol
Golf
Golfi
Golfin
Golfing
 o
 ol
 olf
 olfi
 olfin
 olfing
  l
  lf
  lfi
  lfin
  lfing
   f
   fi
   fin
   fing
    i
    in
    ing
     n
     ng
      g

```

# Answer
> 5 votes
# Python 2.7, ~~70~~ 82 bytes

I couldn't figure out how to get it on 1 line. Call with `e("abcde",0)`

```
def e(s,p):
 f=len(s)
 for x in range(f):print(' '*p+s[:x+1])
 if f>1:e(s[1:],p+1)

```

# Answer
> 4 votes
# Python 3, ~~80~~ 78 bytes

Loop through the number of spaces to prefix with and then the number of characters to end with.

```
lambda x:[print(' '*i+x[i:j+1])for i in range(len(x))for j in range(i,len(x))]

```

**Edit:** Removed spaces before the for loops.

# Answer
> 4 votes
# MATL, ~~15~~ 14 bytes

Saved one byte due to @LuisMendo's tip here!

```
tfWt2/!-RXzB*c

```

So many ways... had to find a new one. Happy bits! :)

Try it online!

**Exploded**

```
t       % duplicate input
f       % get indices of nonzero elements in vector (i.e. 1:n)
W       % 2 raised to array, element-wise: 2^(1:n)
t       % duplicate array
2/      % divide by 2: 2^(0:n-1)
!       % transpose array
-       % element-wise subtraction (w/singleton expansion)
R       % upper triangular part
Xz      % nonzero elements
B       % convert from decimal to binary. Produces a logical array
*       % array product (element-wise, singleton expansion)
c       % convert to character array; 0's automatically converted to spaces

```

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

```
document.write("<pre>"+(

s=>(a=[...s]).map((_,i)=>a.map((_,j)=>++j>i?r+=" ".repeat(i)+s.slice(i,j)+`
`:0),r="")&&r

)("abcde"))
```

Straight-forward approach. Output has a trailing newline.

# Answer
> 3 votes
# Pyth, 12 11 bytes

```
jm+*;xQdd.:

```

Sadly the question allows us to assume unique characters, so I just lookup the first position of the substring, and pad with spaces.

# Answer
> 3 votes
# JavaScript (ES6), 72

```
s=>{for(i=j=0;s[j]||s[j=++i];)console.log(' '.repeat(i)+s.slice(i,++j))}

```

# Answer
> 3 votes
## JavaScript (Firefox 30-57), ~~65~~ 63 bytes

```
s=>[for(c of(i=0,s))for(d of(t=r=i?t+' ':'',s.slice(i++)))r+=d]

```

Returns an array of strings. As ES6 it's 78 bytes:

```
s=>[...s].map((_,i,a)=>a.slice(i).map(c=>r.push(u+=c),t=u=i?t+' ':''),r=[])&&r

```

# Answer
> 3 votes
# Mathematica 89 bytes

```
r@i_:=StringReplace[i,#->" "]&/@(Complement[y,#]&/@Subsequences[y=Characters@i])//Column

```

---

**Explanation**

`i` refers to the input string

`Subsequences[y=Characters@i]` returns all subsequences (represented lists of characters) of the input. (`Subsequences` was introduced in v. 10.4)

For each subsequence, `Complement...` returns those characters from the input string that are **not** present. Each of those characters is replaced by an empty space via `StringReplace[i,#->" "]`.

`Column` displays the results in a single column. Each output string has the same number of characters, resulting in aligned letters.

---

```
r@"abcdefgh"

```

# Answer
> 3 votes
## J, ~~32 29~~ 28 bytes

```
(-@{.@i.|.])"1 a:>@-.~&,<\\.

```

This evaluates to a monadic verb. Try it here. Usage:

```
   f =: (-@{.@i.|.])"1 a:>@-.~&,<\\.
   f 'abe'
a
ab
abe
 b
 be
  e

```

## Explanation

As some other answers, I compute the index of occurrence of the first character of each substring. The substrings are stored in a matrix with trailing spaces, so I rotate them to the right by their index to get the right amount of padding. That one piece of whitespace between `"1` and `a:` is really annoying...

```
(-@{.@i.|.])"1 a:>@-.~&,<\\.  Input is y
                        <\\.  Compute suffixes of prefixes of y, and put them in boxes.
                              This gives a 2D array of substrings in boxes.
                      &,      Flatten the array of boxes,
               a:  -.~        remove all empty strings, and
                 >@           open each box. This places the strings in a 2D matrix of
                              characters, with trailing spaces to make it rectangular.
(          )"1                Do this for each line x in the matrix:
      i.                        The index of every character of x in y.
 -@{.@                          Take the first one and negate it.
        |.]                     Rotate x to the left by that amount.
                                Since we negated the index, this rotates to the right.

```

# Answer
> 2 votes
# QBasic, 75 bytes

```
INPUT s$
FOR i=1TO LEN(s$)
FOR j=1TO i
LOCATE,j
?MID$(s$,j,i+1-j)
NEXT
NEXT

```

The basic double-`FOR`-loop strategy, modified a bit for QBasic's 1-based indexing. The main trick is `LOCATE,j`, which moves the cursor over to column `j` of the current line before printing. Since column 1 is the first column, this is equivalent to printing `j-1` leading spaces.

# Answer
> 2 votes
# Perl 6, 34 bytes

```
perl6 -ne 'm/^(.*)(.+)<{+put " "x$0.to,$1}>/'

```

```
m/       # match the input line
  ^      # from the start
  ( .* ) # 0 or more characters ( $0 )
  ( .+ ) # 1 or more characters ( $1 )

  <{ # match against the result of:

    +put # print with a trailing newline:
      " " x $0.to, # add the leading spaces
      $1           # the substring
  }>
/

```

The reason for the `+` before `put` is so that it returns `1` instead of `True`, which is guaranteed not to be in the input so it always has to backtrack.

```
$ perl6 -ne 'm/^(.*)(.+)<{+put " "x$0.to,$1}>/' <<< abcd

```

```
   d
  cd
  c
 bcd
 bc
 b
abcd
abc
ab
a

```

( If you want it in the opposite order use `(.*?)(.+?)` instead of `(.*)(.+)` )

This was inspired by the Perl 5 answer.

# Answer
> 2 votes
# J, ~~35~~ ~~23~~ 22 bytes

```
[:;#\.<@{."_1|.\."1^:2

```

It took me a while but I finally optimized it.

## Usage

```
   f =: [:;#\.<@{."_1|.\."1^:2
   f 'abcde'
abcde
abcd
abc
ab
a
 bcde
 bcd
 bc
 b
  cde
  cd
  c
   de
   d
    e

```

## Explanation

```
[:;#\.<@{."_1|.\."1^:2  Input: s
             |.\."1     For each suffix of s, reverse it
                   ^:2  Repeat that twice to create all exploded substrings
   #\.                  Get the length of each suffix. This is
                        used to make the range [len(s), len(s)-1, ..., 1]
        {."_1           For each value in the range, take that many strings from
                        the list of exploded substrings. This avoids blank substrings
      <@                Box each set of strings
[:;                     Unbox and join the strings together and return

```

# Answer
> 2 votes
# Java, 138 bytes

```
String e(String s){int l=s.length(),a=0,i,j;for(;++a<l;)for(i=0;i<=l-a;){s+="\n";for(j=0;j++<i;)s+=" ";s+=s.substring(i,i+++a);}return s;}

```

Formatted:

```
String e(String s) {
    int l = s.length(), a = 0, i, j;
    for (; ++a < l;)
        for (i = 0; i <= l - a;) {
            s += "\n";
            for (j = 0; j++ < i;)
                s += " ";
            s += s.substring(i, i++ + a);
        }
    return s;
}

```

# Answer
> 1 votes
## Pyke, 15 bytes

```
QlFUQRd:DlRF2h<

```

Try it here!

Assumes array of padded strings is acceptable

Pads first and then chops.

# Answer
> 1 votes
# Haskell, 65 bytes

```
(>>=zipWith((++).(`replicate`' '))[0..].init.tails).reverse.inits

```

It requires `inits` and `tails` from Data.List, though. To output it, add `mapM_ putStrLn.` to the front.

Relatively straightforward; the `reverse` is to make sure the original string is first.

```
GHCi> mapM_ putStrLn.(>>=zipWith((++).(`replicate`' '))[0..].init.tails).reverse.inits$"abcde"
abcde
 bcde
  cde
   de
    e
abcd
 bcd
  cd
   d
abc
 bc
  c
ab
 b
a
it :: ()
(0.02 secs, 0 bytes)

```

# Answer
> 1 votes
# Ruby, ~~75~~ 67 bytes

Anonymous function. ~~Uses regex substitution to align the substrings.~~ `.` is the filler character.

```
->s{(l=s.size).times{|i|(l-i).times{|j|puts s.tr(?^+s[j,i+1],?.)}}}

```

# Answer
> 1 votes
# bash + GNU coreutils, 109 Bytes

```
l=${#1}
for i in `seq 0 $l`;{
for j in `seq $((l-i))`;{
for k in `seq $i`;{ printf ' ';}
echo ${1:i:j}
}; }

```

Maybe there is a shorter solution, but this is the best that came into my mind. Uniqueness of chracters does not matter here.

# Answer
> 1 votes
# PHP, 151 chars

## Ungolfed

```
<?php
$input = $argv[1];
foreach(str_split($input) as $p=>$letter)
{
    $spaces = str_repeat(" ", $p);
    echo $spaces.$letter."\n";
    $p++;
    for($i=$p;$i<strlen($input);$i++)
    {
        echo $spaces.$letter.substr($input, $p, $i)."\n";
    }
}
?>

```

## Golfed

```
<?$c=$argv[1];foreach(str_split($c)as$d=>$b){$a=str_repeat(" ",$d);echo$a.$b."\n";$d++;for($e=$d;$e<strlen($c);$e++){echo$a.$b.substr($c,$d,$e)."\n";}}

```

## Example

```
php explodesub.php 'abc'
a
ab
abc
 b
 bc
  c

```

# Answer
> 1 votes
# C++, 145 Bytes

the first start parameter is used as input, console as output

```
#include<iostream>
#define f(y,b,d) for(int y=b;r[0][y];y++){d;}
int main(int,char*r[]){f(x,0,f(y,x+1,std::cout.write(r[0],y)<<'\n')r[0][x]=32)}

```

# Answer
> 1 votes
**Python 2 (Ungolfed) 99 Bytes**

```
t=raw_input()
l=len(t)
for j in range(l):
 for i in range(l):
  if i>=j:print j*' '+t[j:i+1]

```

Result:

```
>>python codegolf.py
abc
a
ab
abc
 b
 bc
  c

>>python codegolf.py
abcdef
a
ab
abc
abcd
abcde
abcdef
 b
 bc
 bcd
 bcde
 bcdef
  c
  cd
  cde
  cdef
   d
   de
   def
    e
    ef
     f

>>python codegolf.py
lmnopqrst
l
lm
lmn
lmno
lmnop
lmnopq
lmnopqr
lmnopqrs
lmnopqrst
 m
 mn
 mno
 mnop
 mnopq
 mnopqr
 mnopqrs
 mnopqrst
  n
  no
  nop
  nopq
  nopqr
  nopqrs
  nopqrst
   o
   op
   opq
   opqr
   opqrs
   opqrst
    p
    pq
    pqr
    pqrs
    pqrst
     q
     qr
     qrs
     qrst
      r
      rs
      rst
       s
       st
        t

```

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


title: Time for some TEA!

text:
# Question
Title: Time for some TEA!
## Introduction

A while back I stumbled across the *tiny encryption algorithm* (TEA) and since then I have recommended it whenever special cryptographic security properties were un-needed and a self-implementation was a requirement.
Now today, we want to take the name *\*tiny\* encryption algorithm* literally and your task will be to implement the *tiniest* encryption algorithm!

## Specification

### Input

The input is a list of 8 bytes (or your language equivalent), this is the *plaintext*, and another list of 16 bytes (or your language equivalent), this is the *key*.
Input conversion from decimal, hexadecimal, octal or binary is allowed.
Reading 1 64-bit, 2 32-bit or 4 16-bit integers as output (optionally as a list) is allowed (for the plaintext, double the numbers for the key)

### Output

The output is a list of 8 bytes (or your language equivalent), this is the *ciphertext*.
Output conversion to decimal, hexadecimal, octal or binary is allowed, but not mandatory.
Writing 1 64-bit, 2 32-bit or 4 16-bit integers as output (optionally as a list) is allowed.

### What to do?

Your task is to implement the *encryption direction* of the tiny encryption algorithm (TEA), note XTEA and XXTEA are other algorithms.
Wikipedia has a C-code example and a list of references to some implementations in other languages, this is the original description (PDF).

### More Formally:

```
Let k1, k2, k3, k4, v1, v2, sum be unsigned 32-bit integers.
(k1,k2,k3,k4) <- key input
(v1,v2) <- plaintext input
sum <- 0
repeat 32 times:
    sum <- ( sum + 0x9e3779b9 ) mod 2^32
    v0  <- ( v0 + ( ((v1 << 4) + k0) XOR (v1 + sum) XOR ((v1 >> 5) + k1) ) ) mod 2^32
    v1  <- ( v1 + ( ((v0 << 4) + k2) XOR (v0 + sum) XOR ((v0 >> 5) + k3) ) ) mod 2^32
output <- (v0,v1)

where 0x9e3779b9 is a hexadecimal constant and
"<<" denotes logical left shift and ">>" denotes logical right shift.

```

### Potential corner cases

`\0` is a valid character and you may not shorten your input nor output.
Integer encoding is assumed to be little-endian (e.g. what you probably already have).

### Who wins?

This is code-golf so the shortest answer in bytes wins!
Standard rules apply of course.

## Test-cases

Test vectors were generated using the Wikipedia C code example.

```
Key: all zero (16x \0)
Plaintext -> Ciphertext (all values as two 32-bit hexadecimal words)
00000000 00000000 -> 41ea3a0a 94baa940
3778001e 2bf2226f -> 96269d3e 82680480
48da9c6a fbcbe120 -> 2cc31f2e 228ad143
9bf3ceb8 1e076ffd -> 4931fc15 22550a01
ac6dd615 9c593455 -> 392eabb4 505e0755
ebad4b59 7b962f3c -> b0dbe165 cfdba177
ca2d9099 a18d3188 -> d4641d84 a4bccce6
b495318a 23a1d131 -> 39f73ca0 bda2d96c
bd7ce8da b69267bf -> e80efb71 84336af3
235eaa32 c670cdcf -> 80e59ecd 6944f065
762f9c23 f767ea2c -> 3f370ca2 23def34c

```

Here are some self-generated test vectors with non-zero keys:

```
format: ( 4x 32-bit word key , 2x 32-bit word plaintext ) -> ( 2x 32-bit word ciphertext )
(all in hexadecimal)

( 4300e123 e39877ae 7c4d7a3c 98335923 , a9afc671 79dcdb73 ) -> ( 5d357799 2ac30c80 )
( 4332fe8f 3a127ee4 a9ca9de9 dad404ad , d1fe145a c84694ee ) -> ( a70b1d53 e7a9c00e )
( 7f62ac9b 2a0771f4 647db7f8 62619859 , 618f1ac2 67c3e795 ) -> ( 0780b34d 2ca7d378 )
( 0462183a ce7edfc6 27abbd9a a634d96e , 887a585d a3f83ef2 ) -> ( d246366c 81b87462 )
( 34c7b65d 78aa9068 599d1582 c42b7e33 , 4e81fa1b 3d22ecd8 ) -> ( 9d5ecc3b 947fa620 )
( f36c977a 0606b8a0 9e3fe947 6e46237b , 5d8e0fbe 2d3b259a ) -> ( f974c6b3 67e2decf )
( cd4b3820 b2f1e5a2 485dc7b3 843690d0 , 48db41bb 5ad77d7a ) -> ( b4add44a 0c401e70 )
( ee2744ac ef5f53ec 7dab871d d58b3f70 , 70c94e92 802f6c66 ) -> ( 61e14e3f 89408981 )
( 58fda015 c4ce0afb 49c71f9c 7e0a16f0 , 6ecdfbfa a705a912 ) -> ( 8c2a9f0c 2f56c18e )
( 87132255 41623986 bcc3fb61 7e6142ce , 9d0eff09 55ac6631 ) -> ( 8919ea55 c7d430c6 )

```

# Answer
> 6 votes
## JavaScript (ES6), ~~122~~ ~~118~~ ~~114~~ 113 bytes

```
f=
(v,w,k,l,m,n)=>{for(s=0;s<84e9;v+=w*16+k^w+s^(w>>>5)+l,w+=v*16+m^v+s^(v>>>5)+n)s+=0x9e3779b9;return[v>>>0,w>>>0]}
;
```

```
<div oninput="[r0.value,r1.value]=f(...[v0,v1,k0,k1,k2,k3].map(i=>parseInt(i.value,16))).map(i=>(i+(1<<30)*4).toString(16).slice(1))">
Plain 0: <input id=v0><br>
Plain 1: <input id=v1><br>
Key 0: <input id=k0><br>
Key 1: <input id=k1><br>
Key 2: <input id=k2><br>
Key 3: <input id=k3><br>
</div>
Cipher 0: <input id=r0 readonly><br>
Cipher 1: <input id=r1 readonly><br>
```

Note: Uses little-endian arithmetic. Accepts and returns unsigned 32-bit integer values. Edit: Saved 4 bytes by using multiplication instead of left shift. Saved 4 bytes by testing on `s` thus avoiding a separate loop variable. Saved 1 byte by moving the `+=`s inside the `for`.

# Answer
> 5 votes
# Ruby, ~~114~~ ~~113~~ 106 bytes

Because Ruby doesn't have 32-bit arithmetic, the extra mod operations caused it to *almost* tie with Javascript anyways despite the other byte-saving operations Ruby has...

* *(-1 byte from extra semicolon)*
* *(-7 bytes from trimming out unnecessary mod operations and shifting stuff around)*

Try it online!

```
->v,w,a,b,c,d{s=0
32.times{s+=0x9e3779b9;v+=w*16+a^w+s^w/32+b;v%=m=2**32;w+=v*16+c^v+s^v/32+d;w%=m}
[v,w]}

```

# Answer
> 3 votes
# C, 116 bytes

```
T(v,w,k,l,m,n,s)unsigned*v,*w;{for(s=0;s+957401312;*v+=*w*16+k^*w+s^*w/32+l,*w+=*v*16+m^*v+s^*v/32+n)s+=2654435769;}

```

Takes plaintext as **v** and **w**; key as **k**, **l**, **m**, and **n**; and stores the ciphertext in **v** and **w**.

Test it on Ideone.

# Answer
> 3 votes
# J, 149 bytes

```
4 :0
'u v'=.y
s=.0
m=.2x^32
for.i.32
do.s=.m|s+2654435769
u=.m|u+(22 b.)/(s+v),(2{.x)+4 _5(33 b.)v
v=.m|v+(22 b.)/(s+u),(2}.x)+4 _5(33 b.)u
end.u,v
)

```

Yay! explicit (Boo!) J! I think there's a way to do this tacitly, but it'd probably become unreadable.

## Usage

Takes the keys as four 32-bit integers on the LHS and the plaintext as two 32-bit integers on the RHS. The prefix `16b` is equivalent to `0x` in other languages and represents a hex value. The builtin `hfd` formats the output into a hex string for ease in testing.

```
    f =: 4 :0
'u v'=.y
s=.0
m=.2x^32
for.i.32
do.s=.m|s+2654435769
u=.m|u+(22 b.)/(s+v),(2{.x)+4 _5(33 b.)v
v=.m|v+(22 b.)/(s+u),(2}.x)+4 _5(33 b.)u
end.u,v
)
   hfd 0 0 0 0 f 0 0
41ea3a0a
94baa940
   hfd 0 0 0 0 f 16b3778001e 16b2bf2226f
96269d3e
82680480
   hfd 16b4300e123 16be39877ae 16b7c4d7a3c 16b98335923 f 16ba9afc671 16b79dcdb73
5d357799
2ac30c80

```

---
Tags: code-golf, cryptography
---


title: Merge two sorted lists

text:
# Question
Title: Merge two sorted lists
# Merge Sort

In this challenge, you will implement the merge subroutine of merge sort. Specifically, you must create a function or program or verb or similar which takes two lists, each sorted in increasing order, and combines them into one list sorted in increasing order. Requirements:

# \- Your algorithm must take an asymptotically linear amount of time in the size of the input. Please stop giving O(n^2) solutions.

* You may not use any built-in functions capable of sorting a list, or merging a list, or anything like that. Author's discretion.
* The code should be able to handle repeated elements.
* Don't worry about empty lists.

# Examples:

```
merge([1],[0,2,3,4])
[0,1,2,3,4]

merge([1,5,10,17,19],[2,5,9,11,13,20])
[1, 2, 5, 5, 9, 10, 11, 13, 17, 19, 20]

```

This is , so may the shortest code win!

# Answer
> 8 votes
# Rebmu (35 32 chars)

```
u[iG^aNXa[rvA]apGtkFaM?fA]apGscA

```

**Test**

```
>> rebmu/args [u[iG^aNXa[rvA]apGtkFaM?fA]apGscA] [[1 5 10 17 19] [2 5 9 11 13 20]]
== [1 2 5 5 9 10 11 13 17 19 20]

>> rebmu/args [u[iG^aNXa[rvA]apGtkFaM?fA]apGscA] [[2 5 9 11 13 20] [1 5 10 17 19]]
== [1 2 5 5 9 10 11 13 17 19 20]

```

**About**

Rebmu is a dialect of Rebol that permits 'mushing' of regular code for situations that require brevity. Unmushed, the code works somewhat like:

```
u [                     ; until
    i g^ a nx a [       ; if greater? args next args
       rv a             ; reverse args
    ]                   ; (we want the block containing the next value first)

    ap g tk f a         ; append output take first args
    m? f a              ; empty? first args
]                       ; (first block is now empty)

ap g sc a               ; append output second args
                        ; (add the remainder of the second)

```

I believe this satisfies the **O(n)** requirement as the until block is at most looped as many times as the length of the input (and the `reverse` only switches the order of the container of the input blocks, not the blocks themselves). Using `take` is perhaps a liberty, but is still a minor efficiency hit.

# Rebol (83 75 chars)

Just a wee bit different: in Rebol, paths are a shorter expression than `first` or `second`. `a` is the input block containing the two blocks:

```
until[if a/2/1 < a/1/1[reverse a]append o:[]take a/1 tail? a/1]append o a/2

```

# Answer
> 5 votes
# OP's solutions:

# Haskell 49 44 40

```
k@(p:r)%l@(q:s)|p>=q=q:k%s|0<1=l%k
a%_=a

```

# Python 131 105 101 99 93

With thanks to @Evpok:

```
f=lambda u,v:v and(v[-1]<u[-1]and f(v,u)or[b.append(a)for a,b in[(v.pop(),f(u,v))]]and b)or u

```

# Answer
> 4 votes
# Python (79)

```
from itertools import*
def m(*a):
 while any(a):yield min(compress(a,a)).pop(0)

```

## Python (95, if we're not allowed to return a generator)

```
from itertools import*
def m(*a):
 r=[]
 while any(a):r+=[min(compress(a,a)).pop(0)]
 return r

```

Itertools is the solution for all worldy problems.

Bonus: the two of these work on an arbitrary number of lists, and DO worry about empty lists (as in, they'll happily take 2 empty lists, and return an empty list, or take 1 empty and 1 non-empty list, and they'll return the non-empty one. Another added feature of the 2 non-yielded ones: they'll also run with no arguments, and just return an empty list.)

Ungolfed:

```
from itertools import *  # Import all items from itertools
def m(*a):               # Define the function m, that takes any number of arguments,
                         #  and stores those arguments in list a
    r=[]                 # Create an empty list r
    while any(a):        # While any element in a returns True as value:
        b=compress(a,a)  # Remove any element from a that isn't True (empty lists)
                         #  The example in the official documentation is this one:
                         #  compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F
        c=min(b)         # Sort the lists by first value, and take the first one of these.
        d=c.pop(0)       # Take the first element from c
        r.append(d)      # Append this first element to r
    return r             # Gives back r

```

# Answer
> 3 votes
# C - 75

This operates on `NULL` terminated arrays of `int *`, though it would work equally well for pointers to other types by substituting the appropriate comparison function for `**b < **a` (e.g., `strcmp(*b, *a) < 0`).

```
void m(int**a,int**b,int**c){while(*a||*b)*c++=!*a||*b&&**b<**a?*b++:*a++;}

```

Ungolfed:

```
void merge(int **a, int **b, int **c)
{
    while(*a || *b)
        *c++ = !*a || *b && **b < **a
            ? *b++
            : *a++;
}

```

# Answer
> 3 votes
# Golfscript, ~~29~~ ~~27~~ ~~30~~ ~~29~~ 26 bytes

```
~{.0=@.0=@<{}{\}if(@@.}do;~]p

```

or

```
~{.0=@.0=@>{\}*(@@.}do;~]p

```

### How it works

The command

```
golfscript merge.gs <<< '[2 3] [1 4]'

```

will get processed as follows:

```
~            # Interpret the input string.
             #
             # STACK: [2 3] [1 4]
{            #
    .@=0.@=0 # Duplicate the two topmost arrays of the stack and extract their first
             # elements. This reverses the original order of the first copy.
             #
             # STACK: [1 4] [2 3] 2 1
             #
    >        # Check if the respective first elements of the arrays are ordered.
             #
             # STACK: [1 4] [2 3] 1
             #
    {\}*     # If they are not, swap the arrays. This brings the array with the smallest
             # element to the top of the stack.
             #
             # STACK: [2 3] [1 4]
             #
    (@@      # Shift the first element of the array on top of the stack and rotate it
             # behind the arrays.
             #
             # STACK: 1 [2 3] [4]
             #
    .        # Duplicate the topmost array.
             #
             # STACK: 1 [2 3] [4] [4]
             #
}do          # Repeat this process if the array is non-empty.
             #
             # STACK: 1 [2 3] [4] -> 1 2 [4] [3] -> 1 2 3 [4] []
             #
;~           # Delete the empty array from the stack and dump the non-empty array.
             #
             # STACK: 1 2 3 4
             #
]p           # Combine all elements on the stack into a single array, the to a string and
             # print.

```

The output is:

```
[1 2 3 4]

```

# Answer
> 3 votes
# Python (63)(69)(71)

```
def m(a,b):
 if a[0]>b[0]:a,b=b,a
 return[a.pop(0)]+(m(a,b)if a else b)

```

I wrote this before seeing OP's comments on runtimes of other answers, so this is another solution that's O(n) in algorithm but not implementation.

# Answer
> 2 votes
# JavaScript (ES6), ~~69~~ 79 bytes

```
f=(a,b,c=[])=>(x=a[0]<b[0]?a:b).length?f(a,b,c.concat(x.shift())):c.concat(a,b)

```

### How it works

```
f = (a, b, c = []) =>          // `f' is a function that takes arguments `a', `b' and `c' -
                               // `c' defaults to `[]' - which returns the following
                               // expression:
                               //
 (x = a[0] < b[0] ? a : b)     // Store the array among `a' and `b' with the smaller first
                               // element in `x'.
                               //
 .length ?                     // If it's non-empty,
                               //
  f(a, b, c.concat(x.shift())) // append the first element of array `x' to array `c' and run
                               // `f' again;
                               //
  : c.concat(a,b)              // otherwise, append the arrays `a' and `b' to `c'.
                               //
)

```

# Answer
> 2 votes
## J - ~~42~~ 33

Modified version from here \+ the comment of @algorithmshark

```
k=:(m}.),~0{]
m=:k~`k@.(>&{.) ::,

```

`k` prepends the head of the right array to the merged tails of both arrays. `k~` is the same, but with arrays flipped. `(>&{.)` is comparing the heads. The code will throw an error if one of the arrays is empty, in that case we return just their concatenation `,`.

# Answer
> 2 votes
# Haskell, 35 bytes

```
a#b@(c:d)|a<[c]=b#a|0<1=c:a#d
a#_=a

```

### Haskell, 30 bytes (non-competing)

This non-competing version only guarantees linear runtime if `a` and `b` have disjoint elements; otherwise it still runs correctly but may use quadratic time.

```
a#b|a<b=b#a|c:d<-b=c:a#d
a#_=a

```

# Answer
> 2 votes
# PHP ~~91 98~~ 91 bytes

edit #1: Empty `$b` requires an addional condition in the curly braces (+7).
edit #2: minor golfings
edit #3: added second version

pretty straight forward. The nicest part is the ternary inside the `array_shift`
(which fails if you try it without the curlys)

```
function m($a,$b){for($c=[];$a|$b;)$c[]=array_shift(${$a&(!$b|$a[0]<$b[0])?a:b});return$c;}

```

or

```
function m($a,$b){for($c=[];$a|$b;)$c[]=array_shift(${$a?!$b|$a[0]<$b[0]?a:b:b});return$c;}

```

**ungolfed**

```
function m($a,$b)
{
    $c=[];
    while($a||$b)
    {
        $c[] = array_shift(${
            $a&&(!$b||$a[0]<$b[0])
                ?a
                :b
        });
#       echo '<br>', outA($a), ' / ', outA($b) , ' -> ', outA($c);
    }
    return $c;
}

```

**test**

```
$cases = array (
    [1],[0,2,3,4], [0,1,2,3,4],
    [1,5,10,17,19],[2,5,9,11,13,20], [1, 2, 5, 5, 9, 10, 11, 13, 17, 19, 20],
    [1,2,3],[], [1,2,3],
    [],[4,5,6], [4,5,6],
);
function outA($a) { return '['. implode(',',$a). ']'; }
echo '<table border=1><tr><th>A</th><th>B</th><th>expected</th><th>actual result</th></tr>';
while ($cases)
{
    $a = array_shift($cases);
    $b = array_shift($cases);
#   echo '<hr>', outA($a), ' / ', outA($b) , ' -> ', outA($c);
    $expect = array_shift($cases);
    $result=m($a,$b);
    echo '<tr><td>',outA($a),'</td><td>',outA($b),'</td><td>', outA($expect), '</td><td>', outA($result),'</td></tr>';
}
echo '</table>';

```

# Answer
> 1 votes
## Go, 124 chars

```
func m(a,b[]int)(r[]int){for len(a)>0{if len(b)==0||a[0]>b[0]{a,b=b,a}else{r=append(r,a[0]);a=a[1:]}};return append(r,b...)}

```

# Answer
> 1 votes
# JavaScript - 133

```
function m(a,b){c=[];for(i=j=0;i<a.length&j<b.length;)c.push(a[i]<b[j]?a[i++]:b[j++]);return c.concat(a.slice(i)).concat(b.slice(j))}

```

Same sort of approach as OP's.

# Answer
> 1 votes
# perl, 87 chars / perl 5.14, 78+1=79 chars

This implementation clobbers the input array references. Other than that, it's pretty straight-forward: while both arrays have something, shift off the lower of the two. Then return the merged bit joined with any remaining bits (only one of @$x or @$y will remain). Straight-up perl5, 87 chars:

```
sub M{($x,$y,@o)=@_;push@o,$$x[0]>$$y[0]?shift@$y:shift@$x while@$x&&@$y;@o,@$x,@$y}

```

Using perl 5.14.0 and its newfangled arrayref shift: 78 chars + 1 char penalty = 79 chars:

```
sub M{($x,$y,@o)=@_;push@o,shift($$x[0]>$$y[0]?$y:$x)while@$x&&@$y;@o,@$x,@$y}

```

# Answer
> 1 votes
# Java: 144

This is pretty straightforward. A function that takes two arrays and returns one, the merged version, golfed and without compilation wrapper:

```
int[]m(int[]a,int[]b){int A=a.length,B=b.length,i,j;int[]c=new int[A+B];for(i=j=0;i+j<A+B;c[i+j]=j==B||i<A&&a[i]<b[j]?a[i++]:b[j++]);return c;}

```

Ungolfed (with compile-able and runnable wrapper):

```
class M{
    public static void main(String[]args){
        int[]a=new int[args[0].split(",").length];
        int i=0;
        for(String arg:args[0].split(","))
            a[i++]=Integer.valueOf(arg);
        int[]b=new int[args[1].split(",").length];
        int j=0;
        for(String arg:args[1].split(","))
            b[j++]=Integer.valueOf(arg);
        int[]c=(new M()).m(a,b);
        for(int d:c)
            System.out.printf(" %d",d);
        System.out.println();
    }
    int[]m(int[]a,int[]b){
        int A=a.length,B=b.length,i,j;
        int[]c=new int[A+B];
        for(i=j=0;i+j<A+B;c[i+j]=j==B||i<A&&a[i]<b[j]?a[i++]:b[j++]);
        return c;
    }
}

```

Example executions:

```
$ javac M.java
$ java M 10,11,12 0,1,2,20,30
 0 1 2 10 11 12 20 30
$ java M 10,11,12,25,26 0,1,2,20,30
 0 1 2 10 11 12 20 25 26 30

```

Any tips to shorten would be appreciated.

# Answer
> 1 votes
# Scala, 97 bytes

Recursive solution with O(n). To shorten the code, sometimes an operation is done by switching the 2 interchangeable parameters, i.e. f(a,b) calls f(b,a).

```
type L=List[Int];def f(a:L,b:L):L=if(a==Nil)b else if(a(0)<=b(0))a(0)::f(a.drop(1),b) else f(b,a)

```

Ungolfed:

```
type L=List[Int]

def f(a:L, b:L) : L =
  if (a == Nil)
    b
  else
    if (a(0) <= b(0))
      a(0) :: f(a.drop(1), b)
    else
      f(b,a)

```

# Answer
> 1 votes
## APL (32)

```
{⍺⍵∊⍨⊂⍬:⍺,⍵⋄g[⍋g←⊃¨⍺⍵],⊃∇/1↓¨⍺⍵}

```

Explanation:

```
{⍺⍵∊⍨⊂⍬                               if one or both of the arrays are empty
        :⍺,⍵                           then return the concatenation of the arrays
             ⋄g[⍋g←⊃¨⍺⍵]              otherwise return the sorted first elements of both arrays
                          ,⊃∇/        followed by the result of running the function with
                               1↓¨⍺⍵}  both arrays minus their first element

```

# Answer
> 1 votes
## LISP, 117 bytes

The algorithm ends in `n + 1` iterations, where `n` is the length of the shortest list in input.

```
(defun o(a b)(let((c(car a))(d(car b)))(if(null a)b(if(null b)a(if(< c d)(cons c(o(cdr a)b))(cons d(o a(cdr b))))))))

```

# Answer
> 0 votes
# PYG (50)

```
def m(*a):
 while An(a):yield Mn(ItCo(a,a)).pop(0)

```

## PYG (64, again, if no generators are allowed.):

```
def m(*a):
 r=[]
 while An(a):r+=[(Mn(ItCo(a,a)).pop(0)]
 return r

```

An adaptation of my Python answer.

# Answer
> 0 votes
# JavaScript (ES5) 90 86 90 bytes

```
function f(a,b){for(o=[];(x=a[0]<b[0]?a:b).length;)o.push(x.shift());return o.concat(a,b)}

```

**edit:** (90 - \>86) Moved the ternary into the for loop condition. Idea stolen from Dennis.

**edit:** (86 -\> 90) Removed Array to String cast, as it breaks the *O(n)* requirement.

# Answer
> 0 votes
# Python – 69 bytes

```
def m(A,B):
    C=[]
    while A and B:C+=[[A,B][A>B].pop(0)]
    return C+A+B

```

If the order of input and output were descending, this could be shortened to **61 bytes**:

```
def m(A,B):
    C=[]
    while A+B:C+=[[A,B][A<B].pop(0)]
    return C

```

And further down to **45 bytes** if generators are allowed:

```
def m(A,B):
    while A+B:yield[A,B][A<B].pop(0)

```

# Answer
> 0 votes
# Perl 6: 53 characters

```
sub M(\a,\b){{shift a[0]>b[0]??b!!a}...{a^b},a[],b[]}

```

Shift from whichever of `a` or `b` has the smaller value, until `a` XOR `b` (`a^b`) is true. Then return whatever is left, flattening (`[]`) the arrays into the list (`a[],b[]`).

Assuming shifting from the start of an array is O(n), the worst case is two comparisons and one shift per element, so the algorithm is O(n).

# Answer
> 0 votes
# Mathematica, 137 135

```
m[a_,b_]:=(l=a;Do[Do[If[b[[f]]<=l[[s]],(l=Insert[l,b[[f]],s];Break[]),If[s==Length@l,l=l~Append~b[[f]]]],{s,Length@l}],{f,Length@b}];l)

```

Input:

```
m[{2,2,4,6,7,11},{1,2,3,3,3,3,7}]

```

Output:

```
{1, 2, 2, 2, 3, 3, 3, 3, 4, 6, 7, 7, 11}

```

Ungolfed:

```
mergeList[a_, b_] := (
    list = a;
    Do[
        Do[(
            If[
                b[[f]] <= list[[s]],
                (list = Insert[list, b[[f]], s]; Break[]),
                If[
                    s == Length@list,
                    list = list~Append~b[[f]]
                ]
        ]),
        {s, Length@list}
    ],
    {f, Length@b}
    ];
    list
)

```

Could probably do better.

# Answer
> 0 votes
# R, 80

Same solution as in Scala and other languages. I am not so sure about x\[-1\] is O(1).

```
f=function(a,b)if(length(a)){if(a[1]<=b[1])c(a[1],f(a[-1],b))else f(b,a)}else b

```

# Answer
> 0 votes
## Mathematica, 104 bytes

```
Reap[{m,n}=Length/@{##};i=k=1;Do[If[k>n||TrueQ[#[[i]]<#2[[k]]],Sow@#[[i++]],Sow@#2[[k++]]],n+m]][[2,1]]&

```

Anonymous function, stores the length of the two input lists in the variables `m` and `n`, then each iteration of the `Do` loop `Sow`s an element of one the lists incrementing the counter for that list (`i` for the first, `k` for the second) by one. If one of the counters exceeds the length of the list, the `If` statement will always `Sow` the element from the other list. After `n+m` operations, all the elements have been taken care of. `Reap` or rather part `[[2,1]]` of its output is a list of elements in the order they have been `Sow`n.

I'm not sure of the internals (is accessing a part of a list a `O(1)` operation or not), but timings looked quite linear on my machine with respect to input list length.

---
Tags: code-golf, sorting, restricted-complexity
---


# Question
Title: Design and Solve a Maze [on hold while sandboxing]
Your task is to play the roles of **both** characters in this scene from Inception. In it, Cobb gives Ariadne a challenge:

> You have two minutes to design a maze that takes one minute to solve.

Some liberties will be taken on that description. Most importantly, this challenge is not time-based, rather scores are based on the effectiveness of your mazes and maze-solvers.

*I apologize for the many edits to this challenge as we iterate towards an easy and fair format..*

### Part I: Maze format

All mazes are square. A cell in the maze is represented as a zero-indexed tuple `row column`.

Walls are represented by two binary strings: one for horizontal walls (which block movement between rows) and vertical walls (vice versa). On an `NxN` maze, there are `Nx(N-1)` possible walls of each type. Let's take a 3x3 example where the cells are labelled:

```
A   B | C
   ---
D | E   F
   ---
G   H | I

```

all possible vertical walls are: `AB BC DE EF GH HI`. Translated into a string, the walls shown are `011001` for vertical walls and `010010` for horizontal walls. Also, by "binary string" I mean "the characters '0' and '1'".

The full maze format is a string which contains, in this order:

* width
* start cell tuple
* end cell tuple
* horizontal walls
* vertical walls

For example, this maze:

```
   0 1 2 3 4
   _________
0 | |  E|  _|
1 |  _|_|_  |
2 |_ _ _  | |
3 |  _ _  | |
4 |____S|___|
start:(4,2)
end:(0,2)

```

is formatted to this:

```
5
4 2
0 2
00001011101110001100
10100110000100010010

```

### Part II: The Architect

The Architect program creates the maze. It must play by the rules and provide a valid maze (one where a solution exists, and the end is not on top of the start).

**Input:** Two positive integers:

```
size [random seed]

```

Where `size` will be in `[15, 50]`. You are encouraged to make use of the random seed so that matches can be replayed, although it is not required.

**Output:** A valid size x size (square) maze using the format described in Part I. "valid" means that a solution exists, and the start cell is not equal to the end cell.

The score of an Architect on a given maze is

```
   # steps taken to solve
–––––––––––––––––––––––––––––
max(dist(start,end),(# walls))

```

So architects are rewarded for complex mazes, but penalized for each wall built (this is a substitute for Ariadne's time restriction). The `dist()` function ensures that a maze with no walls does not get an infinite score. The outside borders of the maze do not contribute to the wall count.

### Part III: The Solver

The Solver attempts to solve mazes generated by others' architects. There is a sort of fog-of-war: only walls adjacent to visited cells are included (all others are replaced with '?')

**input:** the same maze format, but with '?' where walls are unknown, an extra line for the current location, and a comma-separated list of valid choices from this location. (This is a big edit that is meant to make it simpler to write a maze-parsing function)

example (same as the above 5x5 maze after taking one step left)

```
5
4 2
0 2
???????????????011??
????????????????001?
4 1
4 0,4 2

```

Which corresponds something like this, where `?` is fog:

```
   0 1 2 3 4
   _________
0 |????E????|
1 |?????????|
2 |?????????|
3 | ?_?_????|
4 |__C_S|_?_|

```

**output:** One of the tuples from the list of valid choices

Each Solver's score is the inverse of the Architect's score.

### Part IV: King of the Hill

Architects and Solvers are given separate scores, so there could potentially be two winners.

Each pair of architects and solvers will have many chances to outwit each other. Scores will be averaged over all tests and opponents. Contrary to code golf conventions, highest average score wins!

I intend for this to be ongoing, but I can't guarantee continued testing forever! Let's say for now that a winner will be declared in one week.

### Part V: Submitting

* I maintain veto power over all submissions - cleverness is encouraged, but not if it breaks the competition or my computer! (If I can't tell what your code does, I will probably veto it)
* Come up with a name for your Architect/Solver pair. Post your code along with instructions on how to run it.

Coming soon: an updated python test kit for the new format. Big changes happened to allow any language submissions.

# Answer
# BuildFun and SolveFun

Well, this took quite a while and I'm not entirely sure if the solver is cheating or not. While it has access to the entire maze all of the time, it only looks at the cell it's in, the walls surrounding it and, if there isn't a wall between them, the cells adjacent to it. If this is against the rules please let me know and I'll try to change it.

Anyway, here's the code:

```
#Architect function
def BuildFun(size,seed):
   #Initialise grid and ensure inputs are valid
   if size<15:size=15
   if size>50:size=50
   if seed<4:seed=4
   if seed>size:seed=size
   grid=[]
   for x in range(size):
      gridbuilder=[]
      for y in range(size):gridbuilder.append([0,1,1])
      grid.append(gridbuilder)
   coords=[0,0]
   grid[0][0][0]=1
   #Generate maze
   while 1:
      #Choose a preffered direction based on location in grid and seed
      pref=((((coords[0]+coords[1]+2)*int(size/2))%seed)+(seed%(abs(coords[0]-coords[1])+1)))%4
      #Find legal moves
      opt=[]
      if coords[0]>0:opt+=[0] if grid[coords[0]-1][coords[1]][0]==0 else []
      if coords[1]<size-1:opt+=[1] if grid[coords[0]][coords[1]+1][0]==0 else []
      if coords[0]<size-1:opt+=[2] if grid[coords[0]+1][coords[1]][0]==0 else []
      if coords[1]>0:opt+=[3] if grid[coords[0]][coords[1]-1][0]==0 else []
      #There are legal moves
      if len(opt)>0:
         moved=False
         while not moved:
            #Try to move in preffered direction
            if pref in opt:
               if pref==0:
                  coords[0]-=1
                  grid[coords[0]][coords[1]][0]=1
                  grid[coords[0]][coords[1]][2]=0
               elif pref==1:
                  grid[coords[0]][coords[1]][1]=0
                  coords[1]+=1
                  grid[coords[0]][coords[1]][0]=1
               elif pref==2:
                  grid[coords[0]][coords[1]][2]=0
                  coords[0]+=1
                  grid[coords[0]][coords[1]][0]=1
               else:
                  coords[1]-=1
                  grid[coords[0]][coords[1]][0]=1
                  grid[coords[0]][coords[1]][1]=0
               moved=True
            #Change preferred direction if unable to move
            else:
               pref+=1
               if pref==4:pref=0
      #There aren't legal moves
      else:
         moved=False
         #Return to a previously visited location
         if not moved:
            try:
               if grid[coords[0]-1][coords[1]][0]==1 and grid[coords[0]-1][coords[1]][2]==0:
                  grid[coords[0]][coords[1]][0]=2
                  coords[0]-=1
                  moved=True
            except:pass
         if not moved:
            try:
               if grid[coords[0]][coords[1]+1][0]==1 and grid[coords[0]][coords[1]][1]==0:
                  grid[coords[0]][coords[1]][0]=2
                  coords[1]+=1
                  moved=True
            except:pass
         if not moved:
            try:
               if grid[coords[0]+1][coords[1]][0]==1 and grid[coords[0]][coords[1]][2]==0:
                  grid[coords[0]][coords[1]][0]=2
                  coords[0]+=1
                  moved=True
            except:pass
         if not moved:
            try:
               if grid[coords[0]][coords[1]-1][0]==1 and grid[coords[0]][coords[1]-1][1]==0:
                  grid[coords[0]][coords[1]][0]=2
                  coords[1]-=1
                  moved=True
            except:pass
      #Check if finished
      fin=True
      for x in grid:
         for y in x:
            if y[0]==0:
               fin=False
               break
         if not fin:break
      if fin:break
   for x in grid:
      for y in x:
         y[0]=0
   #Find positions for start and finish such that the route between them is as long as possible
   lsf=[[0,0],[0,0],0]
   for y in range(size):
      for x in range(size):
         #Check all start positions
         lengths=[]
         coords=[[y,x,4,0]]
         while len(coords)>0:
            #Spread tracers out from start to the rest of the maze
            for coord in coords:
               opt=[]
               if coord[0]>0:opt+=[0] if grid[coord[0]-1][coord[1]][2]==0 else []
               opt+=[1] if grid[coord[0]][coord[1]][1]==0 else []
               opt+=[2] if grid[coord[0]][coord[1]][2]==0 else []
               if coord[1]>0:opt+=[3] if grid[coord[0]][coord[1]-1][1]==0 else []
               try:opt.remove(coord[2])
               except:pass
               #Dead end, tracer dies and possible end point is recorded along with length
               if len(opt)==0:
                  lengths.append([coord[0],coord[1],coord[3]])
                  coords.remove(coord)
               else:
                  #Create more tracers at branch points
                  while len(opt)>1:
                     if opt[0]==0:coords.append([coord[0]-1,coord[1],2,coord[3]+1])
                     elif opt[0]==1:coords.append([coord[0],coord[1]+1,3,coord[3]+1])
                     elif opt[0]==2:coords.append([coord[0]+1,coord[1],0,coord[3]+1])
                     else:coords.append([coord[0],coord[1]-1,1,coord[3]+1])
                     del opt[0]
                  if opt[0]==0:
                     coord[0]-=1
                     coord[2]=2
                     coord[3]+=1
                  elif opt[0]==1:
                     coord[1]+=1
                     coord[2]=3
                     coord[3]+=1
                  elif opt[0]==2:
                     coord[0]+=1
                     coord[2]=0
                     coord[3]+=1
                  else:
                     coord[1]-=1
                     coord[2]=1
                     coord[3]+=1
         #Find furthest distance and, if it's longer than the previous one, the start/end positions get updated
         lengths=sorted(lengths,key=lambda x:x[2],reverse=True)
         if lengths[0][2]>lsf[2]:lsf=[[y,x],[lengths[0][0],lengths[0][1]],lengths[0][2]]
   #Find number of walls and output maze
   w=draw(grid,size,lsf[0],lsf[1])
   #Output maze information
   print('Start = '+str(lsf[0]))
   print('End = '+str(lsf[1]))
   print('Distance = '+str(lsf[2]))
   print('Walls = '+str(w))
   print('Score = '+str(float(lsf[2])/float(w))[:5])
   #Convert array grid to binary strings horizontal and vertical
   horizontal=vertical=''
   for y in range(size):
      for x in range(size-1):vertical+=str(grid[y][x][1])
   for y in range(size-1):
      for x in range(size):horizontal+=str(grid[y][x][2])
   #Save maze information to text file for use with SolveFun
   save=open('Maze.txt','w')
   save.write(str(size)+'\n'+str(lsf[0][0])+' '+str(lsf[0][1])+'\n'+str(lsf[1][0])+' '+str(lsf[1][1])+'\n'+horizontal+'\n'+vertical)
   save.close()
#Solver function
def SolveFun():
   try:
      #Get maze information from text file
      save=open('Maze.txt','r')
      data=save.readlines()
      save.close()
      size=int(data[0])
      s=data[1].rsplit(' ')
      start=[int(s[0]),int(s[1])]
      e=data[2].rsplit(' ')
      end=[int(e[0]),int(e[1])]
      horizontal=data[3].rstrip('\n')
      vertical=data[4]
      #Build maze from information
      grid=[]
      for y in range(size):
         grid.append([])
         for x in range(size):
            grid[y].append([0,1,1])
      for y in range(size):
         for x in range(size-1):
            grid[y][x][1]=int(vertical[y*(size-1)+x])
      for y in range(size-1):
          for x in range(size):
            grid[y][x][2]=int(horizontal[y*size+x])
      path=''
      cpath=''
      bs=0
      pos=start[:]
      grid[pos[0]][pos[1]][0]=1
      while pos!=end:
         #Want to move in direction of finish
         if end[0]<pos[0] and pos[0]-end[0]>=abs(pos[1]-end[1]):pref=0
         elif end[1]>pos[1] and end[1]-pos[1]>=abs(pos[0]-end[0]):pref=1
         elif end[0]>pos[0] and end[0]-pos[0]>=abs(pos[1]-end[1]):pref=2
         else:pref=3
         #Find legal moves
         opt=[]
         if pos[0]>0:
            if grid[pos[0]-1][pos[1]][2]==0:opt+=[0]if grid[pos[0]-1][pos[1]][0]==0 else[]
         if pos[1]>0:
            if grid[pos[0]][pos[1]-1][1]==0:opt+=[3]if grid[pos[0]][pos[1]-1][0]==0 else[]
         if grid[pos[0]][pos[1]][2]==0:opt+=[2]if grid[pos[0]+1][pos[1]][0]==0 else[]
         if grid[pos[0]][pos[1]][1]==0:opt+=[1]if grid[pos[0]][pos[1]+1][0]==0 else[]
         if len(opt)>0:
            moved=False
            while not moved:
               #Try to move in preferred direction
               if pref in opt:
                  if pref==0:
                     pos[0]-=1
                     path+='0'
                     cpath+='0'
                  elif pref==1:
                     pos[1]+=1
                     path+='1'
                     cpath+='1'
                  elif pref==2:
                     pos[0]+=1
                     path+='2'
                     cpath+='2'
                  else:
                     pos[1]-=1
                     path+='3'
                     cpath+='3'
                  grid[pos[0]][pos[1]][0]=1
                  moved=True
               #Change preferred direction by 1
               else:
                  pref=(pref+1)%4
         #No legal moves, backtrack
         else:
            bs+=1
            grid[pos[0]][pos[1]][0]=2
            if int(cpath[len(cpath)-1])==0:
               pos[0]+=1
               path+='2'
            elif int(cpath[len(cpath)-1])==1:
               pos[1]-=1
               path+='3'
            elif int(cpath[len(cpath)-1])==2:
               pos[0]-=1
               path+='0'
            else:
               pos[1]+=1
               path+='1'
            cpath=cpath[:len(cpath)-1]
      #Output maze with solution as well as total steps and wasted steps
      draw(grid,size,start,end)
      print('\nPath taken:')
      print(str(len(path))+' steps')
      print(str(bs)+' backsteps')
      print(str(bs*2)+' wasted steps')
   except:print('Could not find maze')
def draw(grid,size,start,end):
   #Build output in string d
   d='   '
   for x in range(size):d+=' '+str(x)[0]
   d+='\n   '
   for x in range(size):d+='  ' if len(str(x))==1 else ' '+str(x)[1]
   d+='\n    '+'_'*(size*2-1)
   w=0
   for y in range(size):
      d+='\n'+str(y)+'  |' if len(str(y))==1 else '\n'+str(y)+' |'
      for x in range(size):
         if grid[y][x][2]:
            if start==[y,x]:d+=UL.S+'S'+UL.E
            elif end==[y,x]:d+=UL.S+'F'+UL.E
            elif grid[y][x][0]==1:d+=UL.S+'*'+UL.E
            else:d+='_'
            w+=1
         else:
            if start==[y,x]:d+='S'
            elif end==[y,x]:d+='F'
            elif grid[y][x][0]==1:d+='*'
            else:d+=' '
         if grid[y][x][1]:
            d+='|'
            w+=1
         else:d+=' '
   #Output maze and return number of walls
   print(d)
   w-=size*2
   return w
#Underlines text
class UL:
   S = '\033[4m'
   E = '\033[0m'

```

I realise that this is ridiculously long and not particularly easy to read, but I'm lazy so this is how it's staying.

# BuildFun

The architect, BuildFun, is a fairly simple maze generating program that will always create a 'perfect' maze (one with no loops and where any two points will always have exactly one path between them). It bases its logic off of the seed input meaning that the mazes generated are pseudo-random with what often appear to be repeating patterns and, with the same seed and size, the same maze will be created.

Once the maze is generated, the program will attempt to maximise the maze's score by searching for the start point and end point that result in the longest path between them. To do this, it runs through every start point, spreads out tracers to find the end point furthest from it, and picks the combination with the longest path.

After this, it draws the maze, counts the walls and outputs the maze's information. This is the start point, end point, distance between them, number of walls and score. It also formats this information into the style described above for size, start and end, horizontal walls and vertical walls and saves this into a text file called Maze.txt for use later.

# SolveFun

The solver, SolveFun, uses the text file Maze.txt as the input and works in a very similar way to the architect. For every move, it will choose a direction that it wants to go based on its relative position to the end and then it will look at the walls surrounding it. If a wall is not there, it will check to see if it has been in the cell adjacent to it and, if not, it will be added as possible option. It will then move in the direction closest to its preferred direction provided it has options. If it doesn't have options, it will backtrack until it does. This continues until it reaches the end.

As it moves, it records the path it is taking in the variable path which is used at the end to output the total number of steps. It also records the amount of times it had to backtrack used to calculate wasted steps at the end. When it reaches the end, it will output the maze with the shortest path from start to end marked on with `*`s.

# How to Run

Due to the method of outputting the maze (which includes underlining certain characters), this has to be run from a command line in the form

`python -c 'import filename;filename.BuildFun(Size, Seed)'`

and

`python -c 'import filename;filename.SolveFun()'`

where Size is an integer between 15 and 50 (inclusive) and Seed is an integer between 4 and Size (inclusive).
> 1 votes

---
Tags: king-of-the-hill, maze
---


# Question
Title: Professor Schwartzman's Acme Canine Decoder 2000
# Introduction

We -- especially the geeks among us, who tend to be fans -- all remember this old *Far Side* cartoon:

Clearly, Professor Schwartzman could have brushed up on his programming skills just a wee bit more before he put his invention to use. But can you replicate it yourself... using as few bytes as possible?

# Input Specs

You must create a script that translates dog sounds into appropriately intonated "Hey"s. This is pure code golf; the lowest number of bytes wins.

Your input will consist of some combination of the following tokens:

* `Bark`, `Baark`, `Baaark`, `Baaaark`, ... (that is, `B*rk` with at least 1 `a` replacing the asterisk)
* `Woof`, `Wooof`, `Woooof`, ... (`W*f` with at least **2** `o`s replacing the asterisk)
* `Grr`, `Grrr`, `Grrrr`, ..., (`G` followed by at least **2** `r`s)
* Any number of `.` (period), `!` (exclamation mark) and/or `?` (question mark) characters, which may occur anywhere in the input

Note, again, that the `Woof`-based and `Grr`-based tokens always require at least **two** `o`s and `r`s respectively; `Wof` and `Gr` are *not* valid tokens.

There is no limit on how long a token can be (e.g., how many repeated `a`s there can be in a `Bark` token); however, your decoder only needs to work correctly for input tokens with **up to 10** total `a`s, `o`s, or `r`s to pass this challenge.

# Output Specs

Faithful to Schwartzman's design, your canine decoder program must process it into output text as follows:

* `Bark`, `Woof`, and `Grr` become `Hey`;
* `Baark`, `Wooof`, and `Grrr` become `Heyy`;
* `Baaark`, `Woooof`, and `Grrrr` become `Heyyy`; etc.
* For all `Bark`-based tokens, the number of `y`s in the output `Hey`-based token must be equal to the number of `a`s;
* For all `Woof`-based tokens, the number of `y`s in the output `Hey`-based token must be **one less than** the number of `o`s;
* For all `Grr`-based tokens, the number of `y`s in the output `Hey`-based token must be **one less than** the number of `r`s;
* All punctuation (`.`, `!`, and `?`) is left unchanged.

Remember to drop one `y` from the output for `Woof`s and `Grr`s only! The input `Baaaaaaaark?`, with 8 `a`s, will become `Heyyyyyyyy?`, with a matching set of 8 `y`s. However, `Woooooooof?` becomes only `Heyyyyyyy?`, with 7 `y`s.

Again, if you can get your program to work for input tokens of unlimited size, that's great, but for purposes of this challenge, your program will only be checked to ensure that it works properly for input tokens that have no more than 10 repeated letters.

All `Bark`-, `Woof`-, and `Grr`-based tokens in your input are assumed to begin with capital letters. Therefore, there is *no need* to handle turning `Bark grrr` into `Hey heyy` or anything similar.

# Example Inputs and Outputs

1. * Input: `Bark. Bark! Bark!!`
    * Output: `Hey. Hey! Hey!!`
2. * Input: `Baaaaaark?` (six `a`s)
    * Output: `Heyyyyyy?` (six `y`s)
3. * Input: `Grrrrrrrr...` (eight `r`s)
    * Output: `Heyyyyyyy...` (**seven** `y`s)
4. * Input: `?...!`
    * Output: `?...!`
5. * Input: `Wooof Woof? Grrrr. Baaaark Grr!`
    * Output: `Heyy Hey? Heyyy. Heyyyy Hey!`

# Answer
> 16 votes
## Retina, ~~24~~ ~~18~~ ~~17~~ 16 bytes

*1 byte saved based on an idea in MT0's answer.*

```
\wf?k?
y
\byy
He

```

Try it online!

### Explanation

```
\wf?k?
y

```

This simply turns all letters into `y`, but if they are followed by an `f` or `k` we immediately replace that as well. By removing `f` and `k` we "normalise" the lengths of the words so that they now all have two more `y`s than they need.

```
\byy
He

```

This turns the first two `y` of every word into `He`, completing the transformation.

# Answer
> 10 votes
## Perl, 51 41 39 bytes

```
s/(G.|[BW]..)(\w+)/He."y"x length$2/ge

```

### Usage

```
perl -pE 's/(G.|[BW]..)(\w+)/He."y"x length$2/ge'

```

### Input

```
Bark. Bark! Bark!!
Baaaaaark?
Grrrrrrrr...
?...!
Wooof Woof? Grrrr. Baaaark Grr!

```

### Output

```
Hey. Hey! Hey!!
Heyyyyyy?
Heyyyyyyy...
?...!
Heyy Hey? Heyyy. Heyyyy Hey!

```

### How it works

Simple regexp substitution using the auto-printing `-p` adding 1 byte to the count. `/ge` executes the substitution for every pattern, and runs the replacement as code.

---

An older version used a three-way detection, but Martin Ender noticed that I was not aggressive enough, which saved me 10 bytes.

msh210 informed me that you don't need quotes around the string `He`, saving two bytes.

# Answer
> 5 votes
# Python, 106 bytes

```
f=lambda s,a="B,He,Gr,He,Wo,He,a,y,r,y,o,y,f,,yk,".split(","):s if a==[]else f(s.replace(a[0],a[1]),a[2:])

```

**Demo**

https://repl.it/C6Rr

# Answer
> 5 votes
# Vimscript, ~~51~~ ~~39~~ ~~37~~ ~~33~~ ~~32~~ ~~29~~ 28 bytes,

```
%s/\hk\?f\?/y/g|%s/\<yy/He/g

```

Regex credits for shaving 9 more bytes: MT0, Martin Ender, msh210

*Demo*

Explanation:

```
                               1. Normalize words to same length & replace letters with ys

%s                             Regex search and replace
  /                            Regex search begin
   \hk\?f\?                    Find any letter (\h) optionally followed by k or f
           /                   Regex search end and replace start
            y                  Replace with y
             /                 Replace end
              g                Replace globally

               |               New command

                               2. Overwrite first two y of every word with He

                %s             Regex search and replace
                  /            Regex search begin
                   \<yy        Find yy at a word's beginning
                        /      Regex search end and replace start
                         He    replace with He
                           /   Replace end
                            g  Replace globally

```

# Answer
> 4 votes
# JavaScript (ES6) - ~~57~~ ~~55~~ ~~52~~ 51 Bytes

```
f=s=>s.replace(/\wk?f?/g,'y').replace(/\byy/g,'He')

```

Test:

```
f=s=>s.replace(/\wk?f?/g,'y').replace(/\byy/g,'He');

[
  'Bark. Bark! Bark!!',
  'Baaaaaark?',
  'Grrrrrrrr...',
  '?...!',
  'Wooof Woof? Grrrr. Baaaark Grr!'
].forEach( s=>{console.log( f(s) );} );
```

Thanks to @MartinEnder for bytes 56 & 51 and the inspiration for some of the other shavings.

# Answer
> 3 votes
# Perl 5, 25 bytes

A Perl copy of Martin Ender's Retina answer. 24 bytes, plus 1 for `-pe` instead of `-e`.

```
s;\wf?k?;y;g;s;\byy;He;g

```

# Answer
> 2 votes
# Javascript, ~~72~~ ~~66~~ 64 Bytes

```
f=
t=>t.replace(/k|f/g,'').replace(/\w/g,'y').replace(/\byy/g,'He')

```

Edit: separated `f=` and function + reduced byte count

# Answer
> 1 votes
## Pyke, 35 bytes

```
.cFDlR\G.^+3-\y*"He"R+)Rdc~lL-],AsJ

```

Try it here!

Generates Heys, Generates punctuation, zips together, joins

# Answer
> 1 votes
# Python 3, ~~140~~ ~~135~~ 134 bytes

```
from re import*
f=lambda s:''.join('He'+'y'*len(x)+y for x,y in[(a+b+c,d)for a,b,c,d in findall('(?:Wo(o+)f|Gr(r+)|B(a+)rk)(\W+)',s)])

```

Using regex to find occurences of replacable characters.

**Edit:** Golfed 1 byte whitespace and 4 bytes on getting the values from findall result.

**Edit2:** Golfed 1 byte (Bark's "a" was not counted properly)

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


title: Evaluate a Stratego Battle

text:
# Question
Title: Evaluate a Stratego Battle
In the game Stratego, the main game mechanic is when you attack an opponent's piece with yours. In this challenge, you job is to simulate one of these battles and say who survives.

# Specs

You will get as input a pair of string representing Stratego pieces. The pieces are one of `"S 1 2 3 4 5 6 7 8 9 10 B"` (`S` is the Spy, and `B` are bombs). The first of the pair will be the attacker, and the second the attacked.

Here are the rules for determining the results of a battle:

* The higher number beats the lower number: `["4", "6"] -> ["6"]`.
* If both are the same, then both die: `["7", "7"] -> []`.
* Spies are at the bottom, underneath even `1`: `["S", "2"] -> ["2"]`.
* However, if a spy attacks the `10`, then the spy wins: `["S", "10"] -> ["S"]`.
* But the normal rules still apply if the `10` is the one attacking: `["10", "S"] -> ["10"]`.
* If anything attacks a bomb, the bomb wins: `["5", "B"] -> ["B"]`.
* However, a miner (a `3`), can defuse a bomb: `["3", "B"] -> ["3"]`.
* A bomb will never be the attacker.
* A spotter (a `1`), can attack using the normal mechanism, but they can also try to "guess" the rank of the other player, which can be denoted with any sane notation.
* If they guess correctly, the other piece dies: `["1(5)", "5"] -> ["1"]`.
* If they guess wrong, nothing happens: `["1(3)", "5"] -> ["1", "5"]`.
* Spotters can spot bombs: `["1(B)", "B"] -> ["1"]`.

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

(You can use the examples up there as test-cases, because I'm too lazy to put them all together in one list).

# Answer
> 3 votes
# Haskell, 131 bytes

This solution is in the form of an infix function `#` with type `String -> String -> String`

Input is accepted through the two string arguments. The format for spotter input is `1 x` where `x` is the guess.Output is given as a string. In the case where both units survive, the returned string contains both separated by a space.

My original solution was unfortunately bugged and the fix cost me a few bytes.

```
('1':' ':x)#y|x==y="1"|1>0="1 "++y
"S"#"10"="S"
"3"#"B"="3"
_#"B"="B"
x#y|x==y=[]
t@"10"#_=t
_#t@"10"=t
"S"#x=x
x#"S"=x
x#y=max x y

```

# Answer
> 1 votes
# Python, ~~180~~ 153 bytes

```
def f(a,d,g=0):T=([[d]],[[a]]);return([[a]+[d]*(g!=d)]*(g!=0)+[[]]*(a==d)+T[d=="10"]*(a=="S")+T[1]*(d=="S")+T[a=="3"]*(d=="B")+T[int(a,36)>int(d,36)])[0]

```

The function takes the attacker, defender and optionally the spotter's guess (if the attacker is the spotter) as arguments. It returns an array containing the live pieces that remain.

**Ungolfed**

```
def f(a,d,g=0):
 if g: return [a] if g==d else [a,d]
 if a==d: return []
 if a=="S": return [a] if d=="10" else [d]
 if d=="S": return[a]
 if d=="B": return [a] if a=="3" else [d]
 return [a] if int(a)>int(d) else [d]

```

**Demo**

https://repl.it/C6Oz/2

# Answer
> 1 votes
# Javascript ES6, ~~98~~ 86 bytes

```
(a,b,g)=>a==1?b==g?a:[a,b]:b=="B"?a==3?a:b:a=="S"?b==10?a:b:b=="S"?a:a==b?[]:+a>+b?a:b

```

Accepts 3 args (attacker, defender, spotter guess).

Example runs:

```
f("4","6")     -> "6"
f("7","7")     -> []
f("S","2")     -> "2"
f("S","10")    -> "S"
f("10","S")    -> "10"
f("5","B")     -> "B"
f("3","B")     -> "3"
f("1","5","5") -> "1"
f("1","5","3") -> ["1","5"]
f("1","B","B") -> "1"

```

# Answer
> 0 votes
# Javascript, ~~179~~ ~~166~~ 160 bytes

```
f=(a,c,b,n="")=>{if(c)if(c==b)return[a];else return[a,b];if(a==b)return[];a+b=="3B"&&(b=n);a=b=="B"?n:a;b=b=="S"?n:b;a+b=="S10"&&(a=n,b="S");return[+a>+b?a:b]}

```

This function takes 3 arguments - first one is attacker, second is used for spotters (their guess) and third is defender.

```
f = ( a, c, b, n = "" ) =>
{
 //Takes attacker (a), guess (c) and defender (b), n is only declaration
 //c should never be set unless a == 1
 if ( c )
  if ( c == b ) return [ a ];
  else return[ a, b ]; //Spotters

 if( a == b ) return [ ]; //Kill each other if same

 a + b == "3B" && ( b = n ); //Miners destroy bombs
 a = b == "B" ? n : a; //Bomb kills almost everything
 b = b == "S" ? n : b; //Spy dies if anything attacks him
 a + b == "S10" && ( a = n, b = "S" ); //Spies kill 10s

 console.log( JSON.stringify( [a,b] ) );

 return [ +a > +b ? a : b ] //Higher number wins
}

function fight( )
{
 var input = [ [ attacker.value, guess.value], defender.value ];
 out.innerHTML += JSON.stringify( input ) + "   ->   " + JSON.stringify( f( input[0][0], input[0][1], input[1] ) ) + "<br>";
}
```

```
#sword
{
 width: 40px;
 height: auto;
 margin: 10px;
 cursor: pointer;

}

#guess
{
 width: 40px;
}

textarea
{
 height: 20px;
 margin-top: 0px;
}

.panel
{
 background-color: #DDDDDD;
 padding: 5px;
 border: 3px solid black;
}

#out
{
 border: 3px solid black;
 font-family: monospace;
 padding: 10px;
}
```

```
<table>
 <tr>
  <td class=panel>
   <textarea id=attacker placeholder="Attacker"></textarea>
   <textarea id=guess></textarea>
  </td>

  <td>
   <img onclick="fight()" id=sword src="http://cliparts.co/cliparts/8cx/Kjq/8cxKjqAKi.png"></img>
  </td>

  <td class=panel>
   <textarea id=defender placeholder="Defender"></textarea>
  </td>
 </tr>

 <tr>
  <td colspan=3>
   <div id=out></div>
  </td>
 </tr>
</table>
```

Sword icon comes from cliparts.co

# Answer
> 0 votes
# TSQL, ~~162~~ 124 bytes

Golfed:

```
DECLARE @1 varchar(2)='1',@ varchar(2)='3',@s varchar(2)='4'

PRINT IIF(@s>'',IIF(@=@s,@1,@1+','+@),IIF(@1=@,'',IIF(@1+@
IN('S10','3B')or'S'=@,@1,IIF(@='B'or'S'=@1,@,IIF(@1/1<@,@1,@)))))

```

Ungolfed:

```
DECLARE
  @1 varchar(2)='1', -- first piece
  @  varchar(2)='3',  -- second piece
  @s varchar(2)='4'  -- spotter(only fill this value for spotters)

PRINT
  IIF(@s>'',
    IIF(@=@s,@1,@1+','+@),
      IIF(@1=@,'',
        IIF(@1+@ IN('S10','3B')or'S'=@,@1,
          IIF(@='B'or'S'=@1,@,
            IIF(@1/1<@,@1,@)))))

```

Fiddle

---
Tags: code-golf, game, board-game
---


title: Rotate simple ASCII art

text:
# Question
Title: Rotate simple ASCII art
This is similar to a previous question on this site, but with much simpler rules, so we should get much shorter results (in bytes):

* **Input:** ASCII art with only *two* possible characters: space and '#'.
* **Output:** Input sequence rotated 90 degrees counter-clockwise.

Winner is answer with least number of bytes including length of language name.

# Answer
# K, 1+1

```
+

```

.

```
k)+("# # #";" # # ";"#####")
"# #"
" ##"
"# #"
" ##"
"# #"

```
> 10 votes

# Answer
## GolfScript (10 chars + 10)

```
n/zip-1%n*

```

Online demo

Note: as Tomas correctly observed in the comments, I'm assuming that the input is rectangular. This seems reasonable, because it is explicitly stated in the specification of the question which this one aims to simplify.
> 4 votes

# Answer
# MATLAB - 14

```
rot90(a)

```

Where 'a' is the input art, in matrix form. 8 characters in the code, 6 in the name. 8 + 6 = 14.
> 4 votes

# Answer
## J, 16+1 characters

```
|.|:[;._2[1!:1[3

```

Usage (first 3 lines of `#` is the input, the rest is the output):

```
   |.|:[;._2[1!:1[3
# # #
 # #
#####
# #
 ##
# #
 ##
# #

```

**Explanation:**

`1!:1[3` take multi-line input from the keyboard
`[` used as a separator
`[;._2` chop the string into lines
`|:` transpose
`|.` reverse

12 characters to take an process the input, and 4 characters to complete the task.
> 3 votes

# Answer
**Python 3.X 56-Chars**

```
print('\n'.join(map(''.join,zip(*input().split('\n')))))

```

**Demo**

```
>>> print '\n'.join(map(''.join,zip(*raw_input().split('\n'))))
# # #
 # #
#####
# #
 ##
# #
 ##
# #
# ## # #
 ## # #
# ######
 ##
# #

```
> 3 votes

# Answer
# R, 4+1

```
t(a)

```

Where 'a' is the input art, in matrix form. Language is Cran R, function to transform/rotate a martix is t.
> 2 votes

# Answer
# Ruby 56

```
s=[*$<];s[0].size.downto(1){|i|puts s.map{|l|l[i-1]}*''}

```
> 1 votes

# Answer
# Perl, 44 chars

```
$/=$i--;$_=<>;say/(.).{$i}$/gmwhile!++$i||$1

```

Assuming all rows have equal length.
> 1 votes

# Answer
# J (4+1)

```
|:|.

```

Expected input as a string matrix. Usage:

```
   a=: >'# # #';' # #';'#####'
   a
# # #
 # #
#####
   |:|.a
# #
##
# #
##
# #

```
> 1 votes

# Answer
## Bash ~~(144 + 4)~~ (131 + 4)

Assumes input is in a file with newlines to delimit end of row.
Assumes each row has the same number of characters.
Assumes first argument is path to file.

```
t=`sed 's/\(.\)/\1\t/g' $1` n=$(expr $(head -n1 $1|wc -c) \- 1);for i in $(seq 1 $n);do echo "$t"|cut -f$i|tac|tr -d '\n';echo;done

```

Un-golfed:

```
t=$(sed 's/\(.\)/\1\t/g' $1) # Add a tab after every character.
n=$(expr $(head -n 1 $1 | wc -c) \- 1) # Count the number of characters in a row.
for i in $(seq 1 $n); do # For each row.
    echo "$t"|cut -f "$i" |tac|tr -d '\n' # Cut the i^th column, print, reverse and delete newline.
    echo # Finished processing i^th row. Emit newline.
done

```
> 1 votes

# Answer
# JavaScript (ES6), 83

```
f=(s,o=[],a='')=>/./.test(s)?f(s.replace(/^./gm,x=>(a=x+a)&&''),[...o,a]):o.join`\n`

G.onclick=g=>X.innerHTML=f(X.innerHTML)
```

```
textarea{
  height:100px;
  line-height:7px;
}
```

```
<button id=G>Rotate</button>
<textarea id=X>
#
# #
#   #
#     #
#       #
#         #
#       #
#     #
#   #
# #
#
</textarea>
```
> 0 votes

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


title: Write a AZERTY to QWERTY converter

text:
# Question
Title: Write a AZERTY to QWERTY converter
Your task is to create a program will transform each letter of a text typed on a AZERTY keyboard to the equivalent on a QWERTY keyboard, using the same keystrokes.

Example: `Hello; Zorld1 => Hello, World!`

List of character to convert:

* `A <=> Q`
* `Z <=> W`
* `, => m`
* `? => M`
* `M => :`
* `1 => !`
* `9 => (`
* `; => ,`
* `§ => ?`
* `0 => )`
* `) => -`
* `ù => '`

QWERTY keyboard:

AZERTY keyboard:

Test cases:

```
Input: This is q text zritten zith q QWERTY keyboqrd:
Output: This is a text written with a AZERTY keyboard.

Input: Hello zorld in PythonM print9ùHello; Zorld1ù0
Output: Hello world in Python: print('Hello, World!')

Input: Zikipediq is q free online enciclopediq
Output: Wikipedia is a free online enciclopedia

Input: Progrq,,ing puwwles qnd code)golf
Output: Programming puzzles and code-golf

Input: Zhy ,y lqyout hqve szitched to QWERTY §
Output: Why my layout have switched to AZERTY ?

```

This is code golf, so the answer with the shortest byte count win.

# Answer
# Python 3, 70 132 bytes

My first try in code-golfing, so please be kind :):

```
print(input().translate(str.maketrans('azqwAZQW&é"\'(-è_çà)^$Mù,?;:!§1234567890','qwazQWAZ1234567890-[]:\'mM,./?!@#$%^&*()')))

```

Try it online!
> 7 votes

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