title: Temperature Converter

text:
# Question
Title: Temperature Converter
This is a byte sized challenge where you have to convert an input temperature in one of the three units (Celsius, Kelvin and Fahrenheit) to the other two.

# Input

You would be provided with a temperature as a number followed by a unit (separated by space). The temperature can be an integer or a floating point number (23 vs 23.0 or 23.678).

You can submit a function or a full program that reads the space separated string from STDIN/ARGV/function argument or the closest equivalent and prints the output to STDOUT or closest equivalent.

# Output

Your output should be the temperature converted to the other two formats, separated by a newline and followed by the corresponding unit character on each line (optionally separated by a space). The order of the two units does not matter.

**Output precision**

* The converted number should be accurate to at least 4 decimal places without rounding.
* Trailing zeroes or decimal places are optional as long as first 4 decimal places (without rounding) are precise. You can also skip the 4 zeroes and/or the decimal point in case the actual answer has 4 zeroes after the decimal point.
* There should not be any leading zeroes
* Any number format is acceptable as long as it fulfills the above three requirements.

# Unit representation

Unit of temperature can only be one of the following:

* `C` for Celsius
* `K` for Kelvin
* `F` for Fahrenheit

# Examples

Input:

```
23 C

```

Output:

```
73.4 F
296.15 K

```

Input:

```
86.987 F

```

Output:

```
303.6983 K
30.5483 C

```

Input:

```
56.99999999 K

```

Output:

```
-216.1500 C
-357.0700 F

```

This is so shortest entry in bytes wins! Happy Golfing!

# Leaderboard

```
<script>site = 'meta.codegolf',postID = 5314,isAnswer = true,QUESTION_ID = 50740</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)<\\/code><\/pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>
```

# Answer
> 13 votes
# CJam, ~~77~~ ~~65~~ ~~60~~ ~~59~~ ~~55~~ ~~54~~ 52 bytes

```
l~2|"459.67+1.8/'K 273.15-'C 1.8*32+'F"S/m<{~N2$}%6<

```

Try it online in the CJam interpreter.

### How it works

```
l~    e# Read and evaluate the input: F, K, C -> 15, 20, 12
2|    e# Bitwise OR with 2: F, K, C -> 15, 22, 14 = 0, 1, 2 (mod 3)

"459.67+1.8/'K 273.15-'C 1.8*32+'F"S/

      e# Push ["459.67+1.8/K" "273.15-C" "1.8*32+F"].
      e# These commands convert from F to K, K to C and C to F.

m<    e# Rotate the array of commands by 15, 22 or 14 units to the left.
{     e# For each command:
  ~   e#     Execute it.
  N   e#     Push a linefeed.
  2$  e#     Copy the temperature for the next iteration.
}%    e# Collect all results in an array.
6<    e# Keep only the first 8 elements.

```

# Answer
> 32 votes
# Python 3, ~~118~~ 116 bytes

```
I=input()
t=eval(I[:-1])
u=ord(I[-1])%7
exec("u=-~u%3;t=[t*1.8-459.67,(t-32)/1.8,t+273.15][u];print(t,'FCK'[u]);"*2)

```

Performs the conversions in a rotary order `K -> F -> C -> K` twice.

# Answer
> 10 votes
# JavaScript (*ES6*), 127  ~~130 132~~ bytes

Waiting for some amazing esolanguage answer, I did not find much to golf here.

Using template string, the 3 newlines are significant and counted.

Run snippet in Firefox to test.

```
F=x=>([t,u]=x.split(' '),z=273.15,y=9/5,u<'F'?`${t*y+32} F
${+t+z} K`:u<'K'?`${t=(t-32)/y} C
${t+z} K`:`${t-=z} C
${t*y+32} F`)

// Predefined tests

;['23 C','86.987 F','56.99999999 K']
.forEach(v=>O.innerHTML += v+' ->\n'+F(v)+'\n\n')
```

```
<input id=I><button onclick='O.innerHTML=F(I.value)'>-></button><br>
<pre id=O></pre>
```

# Answer
> 7 votes
# Pip, ~~58~~ 57 bytes

```
Ft"CFK"RMbP(a-(o:[32i273.15]Ab%7))*$/95@A[tb]+(oAt%7).s.t

```

Takes input from command-line arguments.

Formatted and slightly ungolfed:

```
o:[32 0 273.15]
F t ("CFK" RM b)
  P (a - o@(Ab % 7))
    * "95"@At / "95"@Ab
    + o@(At%7)
    . s . t

```

**Explanation:**

The general conversion formula between unit 1 and unit 2 is `temp2 = (temp1 - offset1) * mult2 / mult1 + offset2`. The offsets could be to absolute zero or to any other convenient temperature; let's use 0 °C.

```
Unit Mult Offset
C    5    0
K    5    273.15
F    9    32

```

We'll build lists of these values and index into them based on which unit we're dealing with. Pip doesn't have associative arrays/hashes/dictionaries, so we need to convert the characters into integer indices. Maybe there will be helpful patterns with the ASCII values.

```
Unit Asc A%2 Mult A%7 A%7%3 Offset
C    67  1   5    4   1     0
K    75  1   5    5   2     273.15
F    70  0   9    0   0     32

```

This looks promising. One more useful fact: indices in Pip wrap around. So we don't actually need the `%3` as long as we're indexing into something of length 3. Defining `o:[32 0 273.15]` and using `(o (Ab)%7)` will do the trick. (`A` gets the ASCII value of a character. The `(l i)` syntax is used for indexing into iterables, as well as for function calls.)

For the multipliers, we only need the two numbers 9 and 5. Since numbers are the same as strings in Pip, and thus are indexable, getting the multiplier is as simple as `95@Ab` (using the other method of indexing, the `@` operator).

Using Pip's array-programming features, we can save a character over the naive method:

```
95@At/95@Ab
$/95@A[tb]    Make a list of t and b, apply 95@A(...) to each item, and fold on /

```

Finally, add the offset for the new unit, concatenate a space and the new unit's symbol onto the end, and print.

We do this for each `t` in `"CFK" RM b`, thus converting to each unit except the original.

**Sample invocation:**

```
C:\Golf> pip.py tempConv.pip 86.987 F
30.548333333333332 C
303.6983333333333 K

```

(For more on Pip, see the repository.)

# Answer
> 6 votes
# dc, 102 bytes

I'm pretty sure this can be golfed more, but here's a start:

```
4k[9*5/32+dn[ F
]n]sf[459.67+5*9/dn[ K
]n]sk[273.15-1/dn[ C
]n]sc[rlfxlkxq]sC[lkxlcxq]sF?dC=CF=Flcxlfx

```

dc barely makes the grade on this one. Specifically dc string handling isn't really up to the job. But all we need to do is differentiate between "C", "F" and "K". Fortunately dc parses "C" and "F" as hex numerals 12 and 15. And fo "K" it just leaves 0 on the stack.

### Output:

```
$ dc -f tempconv.dc <<< "23 C"
73.4000 F
296.1500 K
$ dc -f tempconv.dc <<< "86.987 F"
303.6983 K
30.5483 C
$ dc -f tempconv.dc <<< "56.99999999 K"
-216.1500 C
-357.0700 F
$

```

# Answer
> 5 votes
## C, 160 bytes

```
float v,f[]={1,1.8,1},d[]={0,32,273.15};u,t,j;main(){scanf("%f %c",&v,&u);for(u=u/5-13,v=(v-d[u])/f[u];j<2;)t=(++j+u)%3,printf("%f %c\n",f[t]*v+d[t],"CFK"[t]);}

```

This reads from stdin. No output precision is specified, so it prints whatever `printf()` feels like printing, which is mostly more than 4 digits.

Ungolfed version:

```
#include <stdio.h>

float v, f[] = {1.0f, 1.8f, 1.0f}, d[] = {0.0f, 32.0f, 273.15f};
char u;
int t, j;

int main() {
    scanf("%f %c", &v, &u);
    u = u / 5 - 13;
    v = (v - d[u]) / f[u];
    for( ; j < 2; ) {
        t = (++j + u) % 3;
        printf("%f %c\n", f[t] * v + d[t], "CFK"[t]);
    }

    return 0;
}

```

Some explanations/remarks:

* This is based on lookup tables `f` and `d` that contains the multiplication factors and offsets to convert Celsius to any other unit (including Celsius itself, to avoid special cases).
* If `u` is the input unit, `u / 5 - 13` maps `C` to 0, `F` to 1, and `K` to 2.
* Input is always converted to Celsius.
* Loop iterates over the two units that are not the input, and converts the Celsius value to that unit.
* The golfed version uses an `int` variable instead of a `char` variable to receive the `scanf()` input. This is a type mismatch, which will only produce correct results on little endian machines (which is almost all of them these days).

# Answer
> 4 votes
# Python 2, 168 Bytes

I saw the Python 3 solution just as I was about to post this, but whatever, I'm just practicing golfing.

```
s=raw_input().split();v=eval(s[0]);c,t=(v-32)/1.8,v-273.15
print[["%fC\n%fF"%(t,t*1.8+32),"%fK\n%fC"%(c+273.15,c)][s[1]=="F"],"%fK\n%fF"%(v+273.15,v*1.8+32)][s[1]=="C"]

```

Ungolfed:

```
def conv(s):
    s = s.split()
    v = float(s[0])
    if s[1]=="C":
        print "%f K\n%f F"%(v+273.15,v*1.8+32)
    elif s[1]=="F":
        v = (v-32)/1.8
        print "%f K\n%f C"%(v+274.15,v)
    else:
        c = v-273.15
        print "%f C\n%f F"%(c,c*1.8+32)

```

# Answer
> 3 votes
# Perl, ~~85 80~~ 76

```
#!perl -nl
print$_=/C/?$_+273.15." K":/K/?$_*9/5-459.67." F":5/9*($_-32)." C"for$_,$_

```

Test me.

# Answer
> 3 votes
# PHP, ~~161~~ 153

```
function f($i){list($v,$u)=split(" ",$i);$u==C||print($v=$u==K?$v-273.15:($v-32)*5/9)."C\n";$u!=K&&print $v+273.15 ."K\n";$u!=F&&print $v*9/5+32 ."F\n";}

```

http://3v4l.org/CpvG7

~~Would be nice to golf out two more characters to get in the top ten...~~

# Answer
> 3 votes
# Python 2, 167

```
s=raw_input();i=eval(s.split()[0]);d={"C":"%f K\n%f F"%(i+273,32+i*1.8),"K":"%f C\n%f F"%(i-273,i*1.8-459.4),"F":"%f C\n%f K"%(i/1.8-17.78,i/1.8+255.2)};print d[s[-1]]`

```

This is my first try on CodeGolf.

# Answer
> 2 votes
# Pyth, 126 bytes

```
AYZczdJvY=Y*JK1.8
?%"%f F\n%f K",+32Y+J273.15qZ"C"?%"%f F\n%f C",-Y459.67-J273.15qZ"K"?%"%f C\n%f K",c-J32K*+J459.67c5 9qZ"F"

```

This feels really long to me...oh well.

# Answer
> 2 votes
# R, ~~150~~ ~~144~~ 141 bytes

```
a=scan(,"");U=c("C","K","F");i=which(U==a[2]);Z=273.15;x=scan(t=a[1]);cat(paste(c(C<-c(x,x-Z,5*(x-32)/9)[i],C+Z,32+C*9/5)[-i],U[-i]),sep="\n")

```

Indented, with new lines:

```
a=scan(,"")
U=c("C","K","F")
i=which(U==a[2])
Z=273.15
x=as.double(a[1])
cat(paste(c(C<-c(x,x-Z,5*(x-32)/9)[i],C+Z,32+C*9/5)[-i],
            U[-i]),
    sep="\n")

```

Usage:

```
> a=scan(,"");U=c("C","K","F");i=which(U==a[2]);Z=273.15;x=scan(t=a[1]);cat(paste(c(C<-c(x,x-Z,5*(x-32)/9)[i],C+Z,32+C*9/5)[-i],U[-i]),sep="\n")
1: 23 C
3:
Read 2 items
Read 1 item
296.15 K
73.4 F
> a=scan(,"");U=c("C","K","F");i=which(U==a[2]);Z=273.15;x=scan(t=a[1]);cat(paste(c(C<-c(x,x-Z,5*(x-32)/9)[i],C+Z,32+C*9/5)[-i],U[-i]),sep="\n")
1: 56.9999999 K
3:
Read 2 items
Read 1 item
-216.1500001 C
-357.07000018 F
> a=scan(,"");U=c("C","K","F");i=which(U==a[2]);Z=273.15;x=scan(t=a[1]);cat(paste(c(C<-c(x,x-Z,5*(x-32)/9)[i],C+Z,32+C*9/5)[-i],U[-i]),sep="\n")
1: 86.987 F
3:
Read 2 items
Read 1 item
30.5483333333333 C
303.698333333333 K

```

Thanks to @AlexA. & @MickyT. !

# Answer
> 2 votes
# Javascript, ~~206~~ ~~193~~ ~~187~~ ~~175~~ ~~162~~ ~~159~~ 156

```
e=273.15,a=prompt(f=1.8).split(" "),b=+a[0],X=b-32,c=a[1];alert(c=="F"&&(X/f+"C\n"+(X/f+e+"K"))||(c=="C"?b*f+32+"F\n"+(b+e+"K"):b*f-459.67+"F\n"+(b-e+"C")))

```

Thanks goes to Optimizer and Ismael Miguel for helping me golf it a little further.

# Answer
> 2 votes
## Mathematica, 66

Hopefully correct this time.

```
Print[1##]&@@@Reduce[F==1.8K-459.67&&C==K-273.15&&#==#2,,#2];&@@#&

```

Example

```
%[37 C]   (* % represents the function above *)

```

> 310.15 K
>
> 98.6 F

# Answer
> 1 votes
# Excel, 239 bytes

```
=IF(RIGHT(A1,1)="C",LEFT(A1,LEN(A1)-2)+273.15&"K
"&9*LEFT(A1,LEN(A1)-2)/5+32&"F",IF(RIGHT(A1,1)="K",LEFT(A1,LEN(A1)-2)-273.15&"C
"&(LEFT(A1,LEN(A1)-2)*9/5-459.67&"F",(LEFT(A1,LEN(A1)-2)+459.67)*5/9&"K
"&(LEFT(A1,LEN(A1)-2)-32)*5/9&"C"))

```

112 bytes of which are used to seperate Value and Unit. Anybody know a better solution?

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


title: Convert between SI prefixes

text:
# Question
Title: Convert between SI prefixes
## Introduction

The International System of Units is a system of measuring all around the world, except for a few countries *including the US*. The SI system (or metric system) is based on powers of ten, listed below (note that this is an incomplete table):

```
femto(f) pico(p) nano(n) micro(μ) milli(m) centi(c) (base unit) hecto(h) kilo(k) mega(M) giga(G) tera(T) peta(P)
10^-15   10^-12  10^-9   10^-6    10^-3    10^-2    10^0        10^2     10^3    10^6    10^9    10^12   10^15

```

Your job will to be to take in one of these measures and convert it into another.

## Input

Input will be a decimal number `10^-16 < x < 2^31 - 1`, an SI prefix, a letter representing a quantity, another SI prefix to convert to, and the same quantity letter. Input will be in the format `1234.56 mC to TC`, and will always match with the regex `^\d+(\.\d+)? [fpnμmchkMGTP](?'letter'[a-zA-Z]) to [fpnμmchkMGTP](?P=letter)$`. You will never have to convert to/from the base unit (`10^0`)

## Output

Output will be the same number as the input, just converted to a new SI prefix. Specifically, the program should convert the number from `SI prefix 1` to `SI prefix 2` in the input. Examples:

```
Input: 1 nm to μm
Output: 0.001

Input: 82 kC to cC
Output: 8200000

Input: 6.54 MK to hK
Output: 65400

Input: 2000 MB to GB
Output: 2

```

This is , so shortest code in bytes wins!

# Answer
> 1 votes
# Pyth, ~~46~~ 44 bytes

The program assumes that the character `µ` (`U+00B5 MICRO SIGN`) is used for the micro sign. On Windows, this is what you get by pressing `Alt Gr` \+ `M`.

The source code contains some unprintables, so here is a reversible `xxd` hex dump.

```
0000000: 2a76 684a 637a 645e 542d 466d 406a 4322  *vhJczd^T-Fm@jC"
0000010: 5c72 575d d623 8b9e 53bb 4c09 b275 2233  \rW].#..S.L..u"3
0000020: 3125 7443 6864 3137 2532 744a            1%tChd17%2tJ

```

Here's a copy-friendly version:

```
*vhJczd^T-Fm@j1057004749883241517573776978549 31%tChd17%2tJ

```

You can try the demo or use the test suite. If these links fail, use the copy-friendly version (demo, test suite).

# Answer
> 4 votes
# JavaScript (ES7), ~~113~~ 109 bytes

```
s=>(p=s.split` `)[m={f:-9,p:-6,n:-3,µ:0,m:3,c:4,h:8,k:9,M:12,G:15,T:18,P:21},0]/(10**(m[p[3][0]]-m[p[1][0]]))

```

Edit: Apparently we can use `µ`(`U+00B5 MICRO SIGN`) for the micro sign now, so replacing with that saves a byte.

For ES6 compatibility `(10**(m[p[3][0]]-m[p[1][0]]))` can be replaced with `Math.pow(10,m[p[3][0]]-m[p[1][0]])` for 114 bytes.

## Explanation

```
s=>                                  // s = input string
  (p=s.split` `)                     // p = input parts

    // m = dictionary of SI prefix digit powers of 10
    //     the exact values don't matter as long as they are relative to each other
    [m={f:-9,p:-6,n:-3,µ:0,m:3,c:4,h:8,k:9,M:12,G:15,T:18,P:21},

    0]                               // get the number
      /(10**(m[p[3][0]]-m[p[1][0]])) // get the factor to divide by from the difference
                                     //     between the SI prefix powers of 10

```

## Test

This test uses `Math.pow` instead of `**` so that common browsers can test it.

```
<input type="text" id="input" value="2000 MB to GB" /><button onclick="result.innerHTML=(

  s=>(p=s.split` `)[m={f:-9,p:-6,n:-3,µ:0,m:3,c:4,h:8,k:9,M:12,G:15,T:18,P:21},0]/Math.pow(10,m[p[3][0]]-m[p[1][0]])

)(input.value)">Go</button><pre id="result"></pre>
```

# Answer
> 2 votes
# Ruby (2.2.1), ~~126~~ 123 bytes

```
r={f:-9,p:-6,n:-3,µ:0,m:3,c:4,h:8,k:9,M:12,G:15,T:18,P:21};p ($*[0].to_r/10**(r[$*[3][0].to_sym]-r[$*[1][0].to_sym])).to_f

```

Saved 3 bytes thanks to user81655

## Explanation

```
# Hash of prefixes to relative powers
r={f:-9,p:-6,n:-3,µ:0,m:3,c:4,h:8,k:9,M:12,G:15,T:18,P:21};
p (                      # print (inspect)
  $*[0].to_r             # input value
  / 10 ** (              # divided by 10^...
    r[$*[3][0].to_sym]   # first prefix symbol
    -
    r[$*[1][0].to_sym]   # second prefix symbol
  )
).to_f                   # convert to float for proper format on output

```

Takes input from the command line e.g `ruby si.rb 1 nm to μm`

This is my first golf!

# Answer
> 2 votes
# Haskell, 143 bytes

Call `s`.

```
import Data.List
s=i.words
i(n:f:_:[t])=read n*10**(x f-x t)
x=j.flip elemIndex"f  p  n  µ  mc   hk  M  G  T  P".head
j(Just n)=fromIntegral n

```

# Answer
> 2 votes
# CJam, 67 bytes

```
lS%:I0=dA"fpnµmchkMGTP"[-7 -4WY5 6ABEHK23]+:AAI3=c#C+=AAI1=c#C+=-#/

```

Try it online!

Uses `µ` (`U+00B5`) for the micro sign so make sure you use this in your input instead of the `μ` (`U+03BC`) in the question.

My first attempt at using CJam. Feel free to suggest improvements because I'm sure there are many!

## Explanation

Same method as my JavaScript answer.

```
lS%:P                    e# P = input parts separated by space
0=d                      e# get number as double
  A
  "fpnµmchkMGTP"
    [-7 -4WY5 6ABEHK23]+
      :A                 e# A = array of SI prefixes followed by their (relative) values
   AP3=c                 e# desired SI prefix
     #C+=                e# get SI value of prefix
   AAP1=c                e# current SI prefix
     #C+=-               e# subtract value of prefix
   #                     e# get power of SI prefix difference
/                        e# divide value by 10 ^ SI prefix difference

```

# Answer
> 1 votes
# Haskell, 121 bytes

```
(e:l:i)!d|e==d=fromEnum l|0<1=i!d
b#i="f`pcnfµimlcmhqkrMuGxT{P~"!(b!!i)
g[(a,b)]=10**fromIntegral(b#1-b#7)*read a
f=g.lex

```

Defines a function `f :: String -> Double`. For example:

```
*Main> f "6.54 MK to hK"
65400.0

```

# Answer
> 0 votes
# Perl 5, 113 + 8 (-p -Mutf8) = 121 bytes

```
%c=(f,-15,p,-12,n,-9,µ,-6,'m',-3,c,-2,h,2,k,3,M,6,G,9,T,12,P,15);/([0-9.]+) (.).*(.)./;$_=$1*10**($c{$2}-$c{$3})

```

Try it online!

---
Tags: code-golf, parsing, conversion
---


title: Code-Golf: Count Islands

text:
# Question
Title: Code-Golf: Count Islands
A simple contest, inspired by this stackoverflow question:

> You are given an image of a surface photographed by a satellite.The image is a bitmap where water is marked by '`.`' and land is marked by '`*`'. Groups of adjacent '`*`'s form an island. (Two '`*`' are adjacent if they are horizontal, vertical or diagonal neighbours). Your task is to print the number of islands in the bitmap.

A single `*` also counts as an island.

Sample Input:

```
.........**
**......***
...........
...*.......
*........*.
*.........*

```

Sample Output:

```
5

```

Winner is entry with smallest number of bytes in the code.

# Answer
> 32 votes
# Mathematica 188 185 170 115 130 46 48 chars

**Explanation**

In earlier versions, I made a graph of positions having a chessboard distance of 1 from each other. `GraphComponents` then revealed the number of islands, one per component.

The present version uses `MorphologicalComponents` to find and number clusters of ones in the array--regions where `1`'s are physically contiguous. Because graphing is unnecessary, this results in a huge economy of code.

---

**Code**

```
Max@MorphologicalComponents[#/.{"."->0,"*"->1}]&

```

---

## Example

```
Max@MorphologicalComponents[#/.{"."->0,"*"->1}]&[{{".", ".", ".", ".", ".", ".", ".", ".", ".", "*", "*"}, {"*", "*", ".", ".", ".", ".", ".", ".", "*", "*", "*"}, {".", ".", ".", ".", ".", ".", ".", ".", ".", ".", "."}, {".", ".", ".", "*", ".", ".", ".", ".", ".", ".", "."}, {"*", ".", ".", ".", ".", ".", ".", ".", ".", "*", "."}, {"*", ".", ".", ".", ".", ".", ".", ".", ".", ".", "*"}}]

```

5

---

**How it works**

Data are input as an array; in Mathematica, this is a list of lists.

In the input array, data are converted to `1`'s and `0`'s by the replacement

```
/.{"."->0,"*"->1}

```

where `/.` is an infix form of `ReplaceAll` followed by replacement rules. This essentially converts the array into a black and white image. All we need to do is apply the function, `Image`.

```
Image[{{".", ".", ".", ".", ".", ".", ".", ".", ".", "*", "*"}, {"*", "*", ".", ".", ".", ".", ".", ".", "*", "*", "*"}, {".", ".", ".", ".", ".", ".", ".", ".", ".", ".", "."}, {".", ".", ".", "*", ".", ".", ".", ".", ".", ".", "."}, {"*", ".", ".", ".", ".", ".", ".", ".", ".", "*", "."}, {"*", ".", ".", ".", ".", ".", ".", ".", ".", ".", "*"}} /. {"." -> 0, "*" -> 1}]

```

The white squares correspond to the cells having the value, 1.

The picture below shows a some steps the approach uses. The input matrix contains only `1`'s and `0`'s. The output matrix labels each morphological cluster with a number. (I wrapped both the input and output matrices in `MatrixForm` to highlight their two dimensional structure.)

`MorphologicalComponents` replaces `1`s with an integer corresponding to the cluster number of each cell.

`Max` returns the largest cluster number.

---

**Displaying the Islands**

`Colorize` will color each island uniquely.

# Answer
> 9 votes
## Ruby 1.9 (~~134~~ ~~121~~ ~~113~~ 110)

Takes the map on stdin or the file name of the map as the first command-line argument, and prints the number of islands to stdout. Using a basic recursive flood-fill. Improvements welcome as always!

```
c=0
gets$!
c+=1while(f=->i{9.times{|o|$_[i]=?.;f[o]if$_[o=i+(o/3-1)*(~/$/+1)+o%3-1]==?*&&o>0}if i})[~/\*/]
p c

```

Similar to David's colorize, you can also get it to display the different islands by changing `$_[i]=?.` to `$_[i]=c.to_s` and `p c` to `puts$_`, which would give you something like this:

```
.........00
11......000
...........
...2.......
3........4.
3.........4

```

(at least until you run out of digits!)

Some test cases:

```
.........**
**......***
...........
...*.......
*........*.
*.........*

```

5

```
......*..**....*
**...*..***....*
....*..........*
...*.*.........*
*........***....
*.....*...***...
*.....*...*....*
****..........**
*.........*.....

```

9

```
*

```

1

```
****
****
....
****

```

2

```
**********
*........*
*.******.*
*.*....*.*
*.*.**.*.*
*.*.**.*.*
*.*....*.*
*.******.*
*........*
**********

```

3

# Answer
> 1 votes
## C, 169 chars

Reads map from stdin. Had no luck improving the recursive flood-fill function `r(j)` although it looks like it could be.

```
c,g,x,w;char m[9999];r(j){if(m[j]==42)m[j]=c,r(j+1),r(j+w-1),r(j+w),r(j+w+1),c+=j==g;}main(){while((m[x++]=g=getchar())+1)w=g<11*!w?x:w;for(;g++<x;)r(g);printf("%i",c);}

```

# Answer
> 1 votes
# Python 2, ~~223~~ 203 Bytes

Thank you to Step Hen and Arnold Palmer for shaving off 20 characters of spaces and unnecessary parenthesis!

```
s=input()
c=[(s.index(l),i)for l in s for i,v in enumerate(l)if'*'==v]
n=[set([d for d in c if-2<d[0]-v[0]<2and-2<d[1]-v[1]<2])for v in c]
f=lambda x,p=0:p if x&n[p]else f(x,p+1)
print len(set(map(f,n)))

```

I thought that using list comprehensions might decrease the number of bytes, but it didn't provide any significant improvement.

Try it here.

I keep trying to trim it around the n (neighbors) list, but I haven't been successful. Maybe someone else will have some ideas for that section.

# Answer
> 0 votes
# Perl 5, 100 bytes

98 bytes of code + 2 bytes for `-p0` flags.

```
/.*/;$@="@+"-1;$~="(.?.?.{$@})?";(s/X$~\*/X$1X/s||s/\*$~X/X$1X/s)&&redo;s/\*/X/&&++$\&&redo}{$\|=0

```

Try it online!

An adaptation (or rather a simplification) of my answer to the challenge How Many Holes?. You can find explanations of how this code works on this other answer (it's a bit long to explain, so I prefer not to retype the entire explanations).

# Answer
> 0 votes
## Python 2, 233 bytes

Too long, compared to other answers. Port of my answer to this question.
Try it online

```
A=input()
c=0
X=len(A[0])-1
Y=len(A)-1
def C(T):
 x,y=T
 if A[y][x]<'.':A[y][x]='.';map(C,zip([x]*3+[min(x+1,X)]*3+[max(x-1,0)]*3,[y,min(y+1,Y),max(y-1,0)]*3))
while'*'in sum(A,[]):i=sum(A,[]).index('*');c+=1;C((i%-~X,i/-~X))
print c

```

# Answer
> 0 votes
## JavaScript, 158 bytes

```
function f(s){w=s.search('\n');t=s.replace(RegExp('([*@])([^]{'+w+','+(w+2)+'})?(?!\\1)[*@]'),'@$2@');return t!=s?f(t):/\*/.test(s)?f(s.replace('*','@'))+1:0}

```

Noncompeting ES6 answer (language postdates challenge) for 132 bytes:

```
f=s=>s!=(s=s.replace(RegExp(`([*@])([^]{${w=s.search`
`},${w+2}})?(?!\\1)[*@]`),`@$2@`))?f(s):/\*/.test(s)?f(s.replace(`*`,`@`))+1:0

```

Port of my answer to How Many Holes? (yes I'm jumping on the bandwagon, now that I've seen two other people port their answers).

# Answer
> 0 votes
# Python 2, 225 bytes

```
g=map(list,input())
q,w,t,r=len(g),len(g[0]),0,range
def l(i,j):
 if 0<=i<q and 0<=j<w and g[i][j]=='1':g[i][j]=0;l(i+1,j);l(i-1,j);l(i,j+1);l(i,j-1)
 return 1
print sum(l(i,j)if g[i][j]=='1'else 0 for j in r(w)for i in r(q))

```

Try it online!

---
Tags: code-golf
---


title: Zippered Paragraph

text:
# Question
Title: Zippered Paragraph
*(Inspired by this challenge)*

Given two input strings, one of which is exactly one character longer than the other, arrange the strings into ASCII art as if they are two halves of a zipper that is only halfway zippered. The longer word forms the bottom of the zipper, and is the first and last character of the combined zippered portion. Since that paragraph is hard to understand, take a look at some examples:

```
zippered
paragraph

 z
   i
     p
       p
        gerraepdh
      a
    r
  a
p

```

Note how `paragraph` (the longer word) forms the bottom zipper, and the `g r a p h` portion encapsulates the `e r e d` portion of `zippered`, and the `z i p p` and `p a r a` portions are offset from each other.

## Input

* Two ASCII strings in any convenient format, with one guaranteed to be even in length and the other exactly one character longer.
* Neither string will contain whitespace, but may contain any other printable ASCII value.
* You can take the input in either order. Please state in your submission the input order.

## Output

The resulting ASCII art representation of the zippered words, as described above, again in any convenient format.

## Rules

* Leading or trailing newlines or whitespace are all optional, so long as the characters themselves line up correctly.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* If possible, please include a link to an online testing environment so other people can try out your code!
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

## Examples

```
ppcg
tests

 p
   p
    sctgs
  e
t

string
strings

 s
   t
     r
      iinnggs
    r
  t
s

```

# Answer
# Japt, ~~31~~ 28 bytes

```
N®¬£ç iXYm½*Ul
uUo mw
y c ·y

```

Test it online! Takes the shorter string first.

### Explanation

```
N®¬£ç iXYm½*Ul    First line: Set U to the result.
N®                Map each item (there's exactly 2 of them) in the input to
  ¬                 the item split into chars,
   £                with each item X and index Y mapped to
    ç                 the first input filled with spaces,
      iX              with X inserted at index
        Ym½*Ul          min(Y, 0.5 * U.length).
                  At the end each input is an array like
                  ["p    ", " p   ", "  c  ", "  g  "]
                  ["t    ", " e   ", "  s  ", "  t  ", "  s  "]

uUo mw    Second line: Set V to the result (though that's not important).
 Uo       Pop the last item (the array representing the second string) from U.
    m     Map each item by
     w      reversing.
u         Push the result to the beginning of U.
          At the end we have e.g.
          ["    t", "   e ", "  s  ", "  t  ", "  s  "]
          ["p    ", " p   ", "  c  ", "  g  "]

y c ·y    Last line: Output the result of this line.
y         Transpose: map [[A,B,C,...],[a,b,c,...]] to [[A,a],[B,b],[C,c],...].
  c       Flatten into one array. [A,a,B,b,C,c,...]
    ·     Join on newlines. Now we have the output transposed.
     y    Transpose rows with columns.

```
> 7 votes

# Answer
# Charcoal, ~~33~~ 31 bytes

```
→Ｆ²«ＦＬθ«§θκ→¿‹κ÷Ｌθ²¿ι↑↓»Ｊ⁰ＬθＡηθ

```

Try it online! Link is to verbose version of code. Takes the shorter string first. Edit: Saved 2 bytes by tweaking the midpoint detection. Explanation:

```
→Ｆ²«

```

Loop over each string in turn.

```
ＦＬθ«

```

Loop over each character of the string in turn.

```
§θκ→

```

Print the character and move an extra square to the right.

```
¿‹κ÷Ｌθ²¿ι↑↓»

```

For the first half of the string, also move the cursor down or up as appropriate.

```
Ｊ⁰ＬθＡηθ

```

After printing the first string, jump to the second string's starting point, and replace the first string with the second, so that it gets printed for the second loop. (The code runs on both loops, but the second time it's a no-op.)
> 6 votes

# Answer
# Pyth, 35 bytes

```
AQj.t.e+*d+lG*<klH*^_1k/h-lGk2b.iHG

```

Try it online!
> 4 votes

# Answer
# Jelly,  ~~27~~  26 bytes

-1 byte thanks to Erik the Outgolfer (use repeat, `¡`, to replace if, `?`, and a passed else clause `¹`)

```
JCḂ¡€ṚH
żµL⁶ẋ;Ð€Fṙ"ÇZṙÇṀ$Y

```

A full program that prints the result with leading white-space, as allowed in the question (or a dyadic link returning a list of characters).

**Try it online!**

### How?

```
JCḂ¡€ṚH - Link 1, get rotations: list p        e.g.: ["a1","b2","c3","d4","e5","f6","g"]
J       - range of length of p                       [ 1, 2, 3, 4, 5, 6, 7]
    €   - for €ach:
   ¡    -   repeat link:
  Ḃ     - ...# of times: modulo 2                      1  0  1  0  1  0  1
 C      - ...link: complement (1-x)                    0  2 -2  4 -4  6 -6
     Ṛ  - reverse                                    [-6, 6,-4, 4,-2, 2, 0]
      H - halve                                      [-3, 3,-2, 2,-1, 1, 0]

żµL⁶ẋ;Ð€Fṙ"ÇZṙÇṀ$Y - Main link: longer (odd length); shorter (even length)
                   -                           e.g.: "abcdefg", "123456"
ż                  - zip them together               ["a1","b2","c3","d4","e5","f6","g"]
 µ                 - monadic chain separation, call that p
  L                - length of p                     7
   ⁶               - literal space character         ' '
    ẋ              - repeat                          "       "
        F          - flatten p                       "a1b2c3d4e5f"
      Ð€           - map with:
     ;             -   concatenation                 ["       a","       1","       b","       2","       c","       3","       d","       4","       e","       5","       f","       6","       g"]
           Ç       - call last link (1) as a monad with argument p
          "        - zip with (no action on left by trailing values of right):
         ṙ         -   rotate left by                ["  a     ","    1   "," b      ","     2  ","c       ","      3 ","       d","       4","       e","       5","       f","       6","       g"]
            Z      - transpose                       ["    c        ","  b          ","a            ","             "," 1           ","   2         ","     3       ","      d4e5f6g"]
                $  - last two links as a monad:
              Ç    -   call last link (1) as a monad with argument p
               Ṁ   -   maximum                       3
             ṙ     - rotate left by                  ["             "," 1           ","   2         ","     3       ","      d4e5f6g","    c        ","  b          ","a            "]
                 Y - join with newlines            '''             \n
                                                       1           \n
                                                         2         \n
                                                           3       \n
                                                            d4e5f6g\n
                                                          c        \n
                                                        b          \n
                                                      a            '''
                   - as full program: implicit print

```
> 4 votes

# Answer
# Python 2, ~~128~~ 119 bytes

```
f=lambda a,b,n=0:n/2<len(a)and' '*-~n+a[0]+'\n'+f(a[1:],b[1:],n+2)+'\n'+' '*n+b[0]or' '*n+''.join(sum(zip(b,a+' '),()))

```

Try it online!
> 3 votes

# Answer
# , ~~47~~ ~~38~~ ~~30~~ ~~27~~ ~~26~~ 25 bytes

Finally beat the current Jelly answer \o/

Takes input with the longer word on top

Explanation coming, don't think there's much more to golf.

```
òGxplòxãòd|>HÏpd|>GGÏphl

```

Try it online!

### Explanation

```
ò     ò      ' <M-r>ecursively
             |abc
             def
 Gx          ' (G)oto the last line and (x) the first character
             abc
             |ef
            ' <C-O> Go back to the previous location
             |abc
             ef
    p        ' (p)aste the character cut
             a|dbc
             ef
     l       ' move one character right
             ad|bc
             ef

```

```
x                  ' (x) the last extraneous character from the previous loop
 ã                 ' <M-c>enter the cursor
  ò                ' <M-r>ecursively
   d|              ' (d)elete to the first co(|)umn
     >H            ' (>) Indent every line from here to (H)ome (first line)
                   ' this leaves the cursor on the first line
       Ïp          ' <M-O>n a newline above this (the first) (p)aste the deleted section
                   ' this leaves the cursor on the last character
         d|        ' (d)elete to the first co(|)umn
           >G      ' (>) Indent every line from here to the end (G)
                   ' unfortunately the cursor stays on the first line
             G     ' (G)oto the last line
              Ïp   ' <M-O>n a newline above this (the last) (p)aste the deleted section
                hl ' move left and then right (break the loop at the end)

```
> 3 votes

# Answer
# , 79 bytes

```
ãl}dÍ./ &
XòYf D"0Pr -Y;D"0pr +òGï"1pÓ./&ò
}dGÓ/&ò
{jpògJòÓó
|DÇ./d
MÙ"-pBr

```

Try it online!

The following should be read with plenty of sarcasm and *air-quotes*.

> Here's an answer in my *golfing-language* that's *good* at *short* answers to *string-based and ASCII-art challenges*.

Why do I keep doing this to myself?

Hexdump:

```
00000000: e36c 167d 64cd 2e2f 2026 0a58 f259 6620  .l.}d../ &.X.Yf
00000010: 4422 3050 7220 2d59 3b44 2230 7072 202b  D"0Pr -Y;D"0pr +
00000020: f247 ef22 3170 d32e 2f26 f20a 0f16 7d64  .G."1p../&....}d
00000030: 47d3 2f26 f20a 7b6a 70f2 674a f2d3 f30a  G./&..{jp.gJ....
00000040: 7c44 c72e 2f64 0a4d d922 2d70 4272 20    |D../d.M."-pBr

```
> 2 votes

# Answer
# Jelly, 28 bytes

```
HĊ©«Rµ®Ḥ_,Ṗ
ZLÇṬ€a"¥"o⁶ZẎz⁶Y

```

Try it online!

Woo Jelly is actually competing in a *and* challenge! \o/
> 2 votes

# Answer
# 05AB1E, ~~26~~ 23 bytes

```
øS2ä`JIθ«¸«vyNúr})2äR˜»

```

Try it online!

**Explanation**

With example input = `ppcg, tests`

```
ø                           # zip the input strings
                            # STACK: ['tp', 'ep', 'sc', 'tg']
 S                          # split to a list of characters
                            # STACK: ['t', 'p', 'e', 'p', 's', 'c', 't', 'g'
  2ä                        # divide the list into 2 parts
    `                       # push them as separate to stack
                            # STACK: ['t', 'p', 'e', 'p'], ['s', 'c', 't', 'g']
     J                      # join the second part to a single string
      Iθ«                   # append the tail of the second input
         ¸«                 # concatenate the 2 lists
                            # STACK: ['t', 'p', 'e', 'p', 'sctgs']
           v                # for each y,N (element, index) in the list
            yNú             # prepend N spaces to y
               r            # reverse the stack
                })          # end loop and wrap the stack in a list
                            # STACK: ['    sctgs', '  e', 't', ' p', '   p']
                  2ä        # split the list into 2 parts
                    R       # reverse the list
                            # STACK: [[' p', '   p'], ['    sctgs', '  e', 't']]
                     ˜»     # flatten the list and join on newlines

```
> 2 votes

# Answer
# C# (.NET Core), 163 bytes

```
(l,s)=>{var o="";int i=0,k=s.Length;for(;i<k;)o+=i<k/2?s[i++]+"\n"+"".PadLeft(i):l[i]+""+s[i++];o+=l[i]+"\n";for(i=k/2;i>0;)o+="".PadLeft(--i)+l[i]+"\n";return o;}

```

Try it online!

Probably a lot of golfing to do here, but here's an initial non-LINQ attempt. Lambda function that takes the longer word first, and returns a string with the ouput.
> 1 votes

# Answer
# Java 8, 216 bytes

A curried lambda: takes `String` and returns a lambda from `String` to `String`. The parameter to the outer lambda is the shorter string.

Not being able to index into `String`s with array syntax is...unfortunate.

```
s->t->{int l=s.length(),i=l/2;String o="",p=o,n="\n";for(;i<l;p+="  ")o=o+t.charAt(i)+s.charAt(i++);o=p+o+t.charAt(i)+n;for(;i-->0;)o=p.substring(l-i--)+s.charAt(i/2)+n+o+p.substring(l-i)+t.charAt(i/2)+n;return o;}

```

## Ungolfed lambda

```
s ->
    t -> {
        int
            l = s.length(),
            i = l / 2
        ;
        String
            o = "",
            p = o,
            n = "\n"
        ;
        for (; i < l; p += "  ")
            o = o + t.charAt(i) + s.charAt(i++);
        o = p + o + t.charAt(i) + n;
        for (; i-- > 0; )
            o =
                p.substring(l-i--)
                + s.charAt(i / 2)
                + n
                + o
                + p.substring(l-i)
                + t.charAt(i / 2)
                + n
            ;
        return o;
    }

```

## Explanation

`l` is the length of the shorter input and `i` is a multipurpose index, initialized to refer to the first character of the second half of the shorter input. `o` accumulates the result, `p` ultimately stores spaces for padding, and `n` is an alias for `"\n"`.

The first loop interleaves the second halves of the two strings (excluding the last character of the longer input) and builds `p` to the proper amount of padding for the middle line.

The next line completes the middle line of output.

I would like to apologize to James Gosling for the second loop. It adds the lines above and below the middle line from the inside out. Entering the loop, `i` is `l - 1`, so one character of padding is prepended along with the last character of the first half of the shorter string. `i` is decremented so that the next padding (appended to the result) is a character shorter. By integer division, the same position character of the longer string is appended. This repeats, and the completed result is returned.

## Cool stuff

Line 13 used to be

```
o+=t.charAt(i)+""+s.charAt(i++);

```

because without the empty string, `+` added the character values together and appended a numeric string. By expanding the compound assignment, the concatenation of `o` and `t.charAt(i)` is evaluated first, which yields the desired result without need for the empty string, saving 2 bytes. This is the first time I've seen a compound assignment behave differently from its expansion.
> 1 votes

# Answer
# Javascript (ES6), ~~140 137~~ 133 bytes

```
A=(a,b,c=0)=>a[c/2]?` `[d=`repeat`](c+1)+a[0]+`
`+A(a.slice(1),b.slice(1),c+2)+`
`+` `[d](c)+b[0]:` `[d](c)+[...a].map((e,f)=>e+b[f])

```

Quite sure this can be golfed further
> 0 votes

# Answer
# Mathematica, 174 bytes

```
(a=(c=Characters)@#;b=c@#2;T=Table;Column[Join[T[T["  ",i]<>a[[i]],{i,g=Length@a/2}],{T["  ",g+1]<>Riffle[b[[-g-1;;]],a[[-g;;]]]},Reverse@T[T["  ",i]<>b[[i+1]],{i,0,g-1}]]])&

```

**Input**

> \["zippered", "paragraph"\]
> 0 votes

# Answer
## TXR Lisp, 126 bytes

```
(defun f(a b :(n 0))(if(<(/ n 2)(length a))` @{""n}@[a 0]\n@(f(cdr a)(cdr b)(+ n 2))\n@{""n}@[b 0]``@{""n}@{(zip b`@a `)""}`))

```
> 0 votes

# Answer
# PHP, ~~149~~ 129 bytes

```
for($r=" ";$x+1<$w=2*$e=strlen($argv[2]);++$x&1||$r[++$i*$w-1]="
")$r[$w*($x&1?$y-1:$e-$y+=$y<$e/2)+$x]=$argv[2-$x%2][$i];echo$r;

```

Run with `-nr` or try it online.
> 0 votes

# Answer
# Perl 5, 163 bytes

```
@a=map{$s=.5*length;[/./g]}<>;say(($"x(2*$_)).$a[0][$_])for 0..$s-1;print$"x(2*$s);print$a[0][$_].$a[1][$_]for$s..@{$a[1]};print$/.($"x(1+2*$s)).$a[1][$s]while$s--

```

Try it online!

Takes the longer string first.
> 0 votes

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


title: Seeking Secret Swapping Sequences

text:
# Question
Title: Seeking Secret Swapping Sequences
> This is a challenge, the robbers thread can be found here.

Your task is to write some code that outputs an OEIS sequence, and contains the name of the sequence in the code (`A______`) and outputs a second separate sequence when the name of the sequence in the code is changed to the name of the second sequence.

Here's an example in Haskell that works for A000217 and A000290.

```
f x|last"A000217"=='0'=x^2|1>0=sum[1..x]

```

Try it online!

You are then to reveal one of the two sequences, and the code keeping the second sequence a secret. Robbers will attempt to figure out what the hidden sequence is. If a robber manages to determine what your sequence is (or another sequence that fits the criteria) you answer is cracked. If none do so in a week of your answer being posted you may mark your answer as **Safe** and reveal the intended solution for verification. **Safe** answers cannot be cracked.

## Input Output

Taken from here

Your code can be a function or complete program that takes **n** via a standard input method and outputs the **n**th term of the sequence as indexed by the provided index on the OEIS page.

You must support all values provided in the OEIS b files for that sequence, any number not in the b files need not be supported.

## Scoring

Your score will be the number of bytes in your code, with less bytes being better.

# Answer
> 9 votes
# Python 3, 59 bytes, A162626, cracked

```
lambda n:n*(n+1)*(n+2)/3if 0<=n<=3else n*(n**2+5)/3#A162626

```

This ~~is~~ was supposed to be impossible, wasn't it?

# Answer
> 5 votes
# Python 3, 62 bytes, A017016 (Cracked)

```
n=int(input())
print(sum(1for i in"A017016"if i>"0")*-~n//-~n)

```

Try it online!

# Answer
> 4 votes
# Japt, 13 bytes (Cracked)

There is (at least) one other solution, if anyone else wants to take a stab at it.

```
p#A000012uCnG

```

Try it online
A000012

---

## Explanation

> `#` followed by a character in Japt gives us the charcode of that character, so `#A=65`, which the rest of the number then gets appended to, giving us `65000012` or `65000290`.
> `u` is the modulo method (it differs from `%` in that it will always return a positive number).
> The `n` method subtracts the number it is applied to from the number passed to it. `C` and `G` are the Japt constants for 11 & 15, respectively. So, `CnG` gives us `4`.
> We now have `65000012%4=0` and `65000290%4=2`. The `p` method raises the number it's applied to (in this case that is, implicitly, the input integer `U`) to the power of the number passed to it, giving us the 2 final formulas of `U**0` and `U**2`.

# Answer
> 4 votes
# MATL, ~~30~~ 29 bytes (Cracked)

```
A077430I\2-|Gw^1Mwx*10&Ylk1+&

```

A077430

Try it online!

-1 byte thanks to @Sanchises

# Answer
> 3 votes
# C#, 28 bytes (Cracked)

```
n=>n*n*("A000290"[6]<49?1:n)

```

Works with A000290.

An easy one to get this started.

Try it online!

# Answer
> 3 votes
# C#, 75 bytes, (Cracked)

```
n=>{int r=1,e=3-0xA000244%2;for(;n>0;e*=e){r*=(n%2>0?e:1);n>>=1;}return r;}

```

A000244

Try it online!

# Answer
> 3 votes
# Python 2, 43 bytes, A000079 (Cracked)

Try it online

```
lambda n:((sum(map(ord,'A000079'))*2)%8)**n

```

# Answer
> 2 votes
# Python 2, 53 bytes, A000012 \[cracked\]

```
lambda x:len(`x**(sum(map(int,'A000012'[1:]))==22)`)

```

Try it online!

> The next sequence is A055642(length of digits in a decimal number). For which the number evaluates to itself, since sum of the digits in OEIS equals 22; the len(...) thus calculates to actual length of the input number for 'A055642'. For sequences A000012(or any other than A055642. The len will always equal to one, since the number evaluted will be '1'.

# Answer
> 2 votes
## Haskell, 226 bytes, safe!

Not sure if clever or ugly, maybe both...

```
o n=read.pure.(!!n)$"A001906"
m::Integral a=>[a->a->a]
m=[const,(+),(-),(*),div,(^)]++(flip<$>m)
l=o 1:o 3-o 1:zipWith(m!!(o 6+o 3-o 2))(tail l)l
f=(l!!).((m!!(o 4+o 5+o 6-2*o 1-o 2))$sum[1|n<-[1..6],odd(o n)]).((m!!o 6)$o 3)

```

So now this computes A001906, but it should be able to generate a lot of sequences.

Try it online!

---

Solution: A131078

Wondering if this was too difficult or no one tried?

`o 1` to `o 6` are the digits of the series number, `m` is a list of operations. `l` is a recursively defined infinite list with the first two values derived from the series number and the remaining ones computed from the previous two using a fixed operation from `m`. In the case of A001906, the definition can be simplified to

```
l=0:1:zipWith(flip(+))(tail l)l

```

`(flip(+))` is (usually) the same as `(+)`, and we get a well known (but not the shortest) definition of the Fibonacci numbers. This recursion scheme could directly compute A001906, but that needs an operation more complicated than those in `m`. Another example: using starting values `1` and `2` and the operation `(*)` gives the series A000301. It is computed by our code when the series number is replaced with `?103206`.

Finally, the function `f` indexes into the list `l`, but only after some transformation of the input. For A001906, the middle part reduces to `(*)2`, so that we only get the Fibonacci numbers at even positions. The right part becomes `flip const 1`, which is the identity function and does not further interfere.

For the solution `A131078`, the starting values of `l` are `1` and `0`, and the operation is `flip const`, which lets `l` be `1,0,1,0,...`. The middle part of `f` becomes `(flip div 4)`, resulting in `1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,...`. This looked like a nice answer, but then I saw that A131078 starts at `n=1`, so I added the right part of `f`, which here is `flip(-)1` to subtract one.

My idea was to make it a bit obfuscated by using `m` and indexing into it with digits from the series numbers, then it became more obfuscated (complicated terms) to make it work (maybe I wasn't searching long enough for alternatives); and then it became even more obfuscated (right part of `f`) to make it really work. Still I think some guessing and trying could have cracked it.

# Answer
> 1 votes
# Python 3, 65 bytes, A000027, cracked

```
a=lambda a,n=((int("A000027",11)-0x103519a)%100%30+1)/2:a//(14-n)

```

Yay crazy arithmetic!

# Answer
> 1 votes
# Smalltalk, 148 bytes, safe!

```
|x o|x:=(16rA018253*0.00861-1445345)floor. o:=OrderedCollection new. 1 to:x/2 do:[:i|x\\i=0 ifTrue:[o add:i]].o add:x.^o at:stdin nextLine asInteger

```

A018253

Takes an integer as input, sequence is 1-based.

> The intended second sequence is A133020. In the writeup for A018253 is a link to a list of entries for sequences related to the divisors of numbers. In that list, A133020 is under *divisors of squares: 100²*. If you want to see the entire sequence, insert `Transcript show: o printString; cr.` before the return `^` statement in the code.

# Answer
> 0 votes
# dc, 52 bytes, cracked

This one works with A000217:

```
?SaA000217d8d1+Sb%1r-dScla*r10 7^-Lb%+la*1+Lc+La*2/p

```

Try it online!

# Answer
> 0 votes
# Chip, 67 bytes, cracked by Yimin Rong

```
2D5B#{*Cm49!}E-7
(A000012d#,zkmsh
b-\6/e2)[1Zv^~^S
33a#kcf3g88taz1@

```

A000012. A bit cheeky, yes.

Try it online!

Uses bytes for i/o, so I was nice and built a bashy/pythony wrapper.

---

> Alternate sequence is A060843. Try it online for inputs `1..4`.
> Yimin Rong hunched right, such a short Chip program can only calculate very simple things. The original sequence is all one's, and the alternate sequence is the busy beaver numbers, of which only 4 are known.
> These numbers, `1, 6, 21, 107`, are simply hard-coded for the inputs `1..4`.
> One interesting thing about using Chip for this challenge is that the digits `0`-`9` are not numbers, but logical elements. Specifically, `0`-`7` are the eight bits addressing the head of the stack, and `8` and `9` are the read and write toggles. That made this a bit more interesting and much more obfuscated.
> A potential giveaway is that only `A`-`D` appear, meaning that we only have 4 bits for indexing the sequence. This meant that there could be at most 16 different values. In fact, only `A`-`C` are actually used for the alternate sequence, giving at most 8 different values.
> For any who might be interested, here is the same code, stripped of the no-ops and unused elements:

.

> ```
>    B  *C 49!
>  A000012d ,z  s
> b-\6/e   1Zv-~^S
> `3a`-cf3g`8taz1
>
> ```

# Answer
> 0 votes
# Python 3.6, 114 bytes, cracked

```
from random import*
g=lambda n:eval(''.join(Random("A005843").choices('n8-9+17n#8*+26%n1 32-3+4-545*-#6*7',k=34)))

```

A005843

`g(n)` returns the n-th value of the sequence for n \>= 0.

`random.choices(s,k)` is new in Python 3.6, it returns `k` items selected from `s` with replacement.

---
Tags: code-golf, sequence, cops-and-robbers
---


title: your Uncle help Drunk needs

text:
# Question
Title: your Uncle help Drunk needs
Drunk Uncle (sorry M.E. and AUS for region lock) is a fictional character from Saturday Night Live. He often confuses words for others that sound like them. For this challenge you need to convert normal speech into drunkspeak.

# Algorithm

Translating to drunkspeak requires swapping the order of words in the text. Swapping is based on the *drunkenness similarity* of two words. Drunkenness similarity is defined as **the number of letters that two words have occuring at the same indices**. However, **two identical words have a drunkenness similarity of -1**. For example, `tree` and `friend` have a drunkenness similarity of 2, because they both have an 'r' at index 1, and an 'e' at index 3.

All you have to do is find the two words in the text with the highest drunkenness similarity, then swap them. Once you swap two terms, they do not move any more. Then you look at the remaining swappable terms and swap the two that have the highest drunkenness similarity. You keep doing this until you can't swap any more. Then you output (or return, for a function) the updated text.

# Specifics

* For simplicity, input is a list of words consisting of characters in \[A-Za-z\]
* Every input contains at least one word
* Letter matching is case-insensitive: `A` matches with `a` (**Note:** Due to this rule `Dog` and `dog` are identical, and thus have a D.S. of -1)
* If multiple pairs have the highest drunkenness similarity:
    1. Of the words, that can maximize drunkenness similarity, pick the one with the lowest index in the list
    2. Pair that word with the lowest-index word that maximizes drunkenness similarity

# Examples

1. `Drunk Uncle needs your help` (title)

* S1: Drunk\<=\>your (DS: 1) `your Uncle needs Drunk help`
    * S2: needs\<=\>help (DS: 1) `your Uncle help Drunk needs`
    * Output: `your Uncle help Drunk needs`
2. `I love fidget spinners` (boring example)

* S1: I\<=\>love (DS: 0) `love I fidget spinners`
    * S2: fidget\<=\>spinners (DS: 0) `love I spinners fidget`
3. `dog eat dog ear`

* S1: eat\<=\>ear (DS: 2) `dog ear dog eat`
    * S2: dog\<=\>dog (DS: -1) `dog ear dog eat` (this step just formality)
4. `Let me tell you a story`

* S1: Let\<=\>me (DS: 1) `me Let tell you a story`
    * S2: tell\<=\>you (DS: 0) `me Let you tell a story`
    * S3: a\<=\>story (DS: 0) `me Let you tell story a`
5. `Too many money and purple people`

* S1: purple\<=\>people (DS: 4) `Too many money and people purple`
    * S2: many\<=\>money (DS: 2) `Too money many and people purple`
    * S3: Too\<=\>and (DS: 0) `and money many Too people purple`

Let me know if there are more examples you want me to cover.

# Answer
# JavaScript - ~~286~~ 279 bytes

```
f=(a,n=(a=a.split` `).length)=>{for(d=n>>1;w=-2,d--;){for(i=n;i--;)for(j=n;j--;)s=((a,f,v=0)=>{for(u=s=a!=f;(r=a[v])&&(t=f[v++]);s+=(p=a=>a.toLowerCase())(r)==p(t));return u*s-1})(a[i],a[j]),!(f[i]|f[j])&&s>=w&&(w=s,x=i,y=j);f[x]=f[y]=1,[a[x],a[y]]=[a[y],a[x]];}return a.join` `}

```

You can try it on JSFiddle.
> 3 votes

# Answer
# Python 3, ~~285~~ ~~277~~ ~~270~~ 267 Bytes, not working

```
i=input().split();r=range;l=len;t=y=z=-1;n=str.lower
for p in r(l(i)):
 for q in r(p):
  b=min(l(i[p]),l(i[q]));x=0
  for s in r(b):
   if n(i[p][s])==n(i[q][s]):
    x=x+1
  if n(i[p])==n(i[q]):
   x=-1
  if x>t:
   t=x;y=p;z=q
i[y],i[z]=i[z],i[y]
print(" ".join(i))
```

I tried to make the output match the challenge, not the test cases, as a couple of the test cases contradict the challenge.

Edit: golfed the 'lower' thingy.

Edit: changed split(" ") to split()

Edit: I realised this doesn't actually complete all the thingys, and while I might come up with a full working answer, in the meantime I might as well add that this only completes one iteration.
> 2 votes

---
Tags: code-golf, natural-language
---


title: Compute the Discrete Cosine Transform

text:
# Question
Title: Compute the Discrete Cosine Transform
Implement the Discrete Cosine Transform (DCT). This may implemented as either a function or a program and the sequence can be given as either an argument or using standard input. Your program must be able to handle sequences of any length (assuming a hypothetical version of your language which has no limits on things like memory and integer size).

There was a previous challenge for DFT, now lets compute DCT! ;-)

Use the DCT-II definition from Wikipedia:

Your program takes a sequence *x**n* as input, and must produce the corresponding sequence *X**k*. In this formula, the cosine is in radians.

## Rules

* This is so the shortest solution wins.
* Builtins that compute the DCT in forward or backward (also known as inverse) directions are not allowed.
* Floating-point inaccuracies will not be counted against you.
* You don't have to use the exact algorithm shown here, as long as you produce the same results.

# Answer
> 3 votes
# Jelly, 15 bytes

```
LḶµ+.×þ÷L-*Ḟ³æ.

```

Try it online!

This uses the identity that `cos(pi * x) = real(e^(i * pi * x)) = real((-1)^x)`

## Explanation

```
LḶµ+.×þ÷L-*Ḟ³æ.  Input: array A
L                Length
 Ḷ               Lowered range - [0, 1, ..., len(A)-1]
  µ              Begin a new monadic chain
   +.            Add 0.5
     ×þ          Outer product using multiplication
       ÷         Divide by
        L        Length
         -*      Compute (-1)^x
           Ḟ     Real part
             æ.  Dot product with
            ³    The first argument (A)

```

# Answer
> 2 votes
# Mathematica, 79 bytes

```
Tr/@(s=#;x=Length@s;Table[s[[n+1]]Cos[Pi/x(n+1/2)#],{n,0,x-1}]&/@Range[0,x-1])&

```

Since there are (currently) no test cases, as it turns out, there *is* a built-in for this: `FourierDCT`. However, the function "normalizes" the result by dividing it by a value before returning it. Thankfully, the documentation specifies that this division factor is just the square root of the input list's length (for DCT-II).

So, we can verify our results by multiplying the output of `FourierDCT` by the square root of the length of our input list. For anyone else who tries this problem, here are some test cases:

`FourierDCT@{1,3,2,4}*Sqrt@4`

> {10, -2.38896, 0, -2.07193}

`FourierDCT@{1,1,1,1,1}*Sqrt@5`

> {5, 0, 0, 0, 0}

Note that I've slightly edited the output of the last one; the last four values output as very small decimals, around 10-16, due to floating point precision errors around 0. My answer does give 0 for them, if you convert it to a decimal.

This solution gives exact answers when Mathematica can do so. If that's not okay and you want decimals, let me know.

# Answer
> 1 votes
# C (gcc), ~~88 83 78~~ 77 bytes

```
k;d(a,b,c)float*a,*b;{for(k=c*c;k--;)b[k/c]+=a[k%c]*cpow(-1,k/c*(.5+k%c)/c);}

```

Try it online!

This assumes the output vector is cleared before use.

Thanks to @Peter Taylor for -5

# Answer
> 1 votes
## Clojure, 100 bytes

```
#(for[c[(count %)]k(range c)](apply +(map(fn[n x](*(Math/cos(*(/ c)Math/PI(+ n 0.5)k))x))(range)%)))

```

Sometimes it is difficult to be creative.

# Answer
> 1 votes
# Octave, ~~49 46 45~~ 42 bytes

Here we consider the DCT as a matrix multiplication. The matrix is basically the entry-wise cosine of a rank 1 matrix which is very simple to construct.

Thanks @Cowsquack for -1 byte, thanks @ceilingcat for another -3 bytes!

```
@(x)cos(pi/(n=numel(x))*(0:n-1)'*(.5:n))*x

```

Try it online!

# Answer
> 1 votes
# Mathematica, ~~51~~ 49 bytes

```
Re@Total[I^Array[(2##+#2)/n&,{n=Length@#,n},0]#]&

```

Try it online! (Using Mathics)

Based on my solution to DFT.

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


title: Will I make it out in time?

text:
# Question
Title: Will I make it out in time?
*Inspired by this.*

## Background

The evil farmer has decided to burn your wheat field down in order to drive up the prices. To ensure total destruction, he has also soaked your field in gasoline. Even more unfortunately, you happened to be walking on the field when it was lit on fire, and you must get out quickly to survive.

## Challenge

Given a field containing wheat, fire and your location, determine if you can make it out of the field in time.

A field consists of wheat (here represented by `.`) and fire (`F`). Here your location is marked with a `O`. For example:

```
...F...F
F.......
........
.F......
....O...
...F....
........
.F....F.

```

Every second you move to any adjacent cell (but not diagonally), and every fire spreads to every adjacent cell. If you can't move to a cell that will not be on fire, you die. If you make it out of the field, you survive. Let's see what happens in this example:

```
...F...F
F.......
........
.F......
....O...
...F....
........
.F....F.

..FFF.FF
FF.F...F
FF......
FFF.....
.F.F.O..
..FFF...
.F.F..F.
FFF..FFF

FFFFFFFF
FFFFF.FF
FFFF...F
FFFF....
FF.FF.O.
.FFFFFF.
FFFFFFFF
FFFFFFFF

FFFFFFFF
FFFFFFFF
FFFFF.FF
FFFFF.FF
FFFFFFFO
FFFFFFFF
FFFFFFFF
FFFFFFFF

FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFF
FFFFFFFFO <-- you made it out and survived, barely
FFFFFFFF
FFFFFFFF
FFFFFFFF

```

## Rules

* Your input is the field as a grid. You may choose any input format, including a string with line separators or a 2D array.
    + You may **not** take as input the locations for fire and/or yourself.
    + You may use any 3 distinct values as wheat, fire and your position, including non-strings for array input.
    + Fields are always at least 1x1 in size, rectangular and contain no invalid characters.
    + Any field will contain exactly one of the value representing your location, and every other position may or may not be fire.
* Your output is one of two distinct values for "you survive" or "you die", as usual in .
* Standard rules apply.

## Test cases

### Survived

```
O

```

```
....
.O..
....

```

```
FFFFF
.....
..O..
.....

```

```
FFFF
FFFO
FFFF

```

```
.F....
......
......
.F....
..O...
.FF...
.F....
..FF..

```

```
...F...F
F.......
........
.F......
....O...
...F....
........
.F....F.

```

### Didn't survive

```
FFF
FOF
FFF

```

```
F.F
.O.
F.F

```

```
....F
.....
..O..
.....
F....

```

```
.F....F.
........
........
F..O....
........
.....F..

```

```
...F...F
F......F
........
.F......
....O...
...F....
........
.F....F.

```

```
F..F
.O..
FF..

```

# Answer
> 27 votes
# Snails, 15 bytes

```
\Oo!{.,fee7.,\F

```

Try it online!

`1` means survival while `0` means death.

Since it is impossible to outrun the fire, it is never useful to try to go around it. The best route is always a straight line. So there are only four possible choices of escape route. To determine if a direction is safe, we check for any `F` in the "fire cone" pointing in that direction.

# Answer
> 12 votes
# Python 2, ~~283~~ ~~218~~ ~~209~~ 208 bytes

```
lambda F:f(F)&f(F[::-1])
def f(F):l=F.split();w=len(l[0])+1;i=F.index('O');x,y=i/w,i%w;r=range(len(l));return all('F'in''.join(n)for n in[[l[i][x+abs(i-y):]for i in r],[l[i][max(0,y+x-i):i+x-y+1]for i in r]])

```

Try it online!

Takes input as a newlines separated string, and returns `True/False` for `Dead/Alive`

Works by checking each direction(udlr) for `F`ire in by looking outward:

Example:

Input:

```
FFFFF
.....
..O..
.....

```

Fire checks:

```
Up:       Down:     Left:     Right:

FFFFF               F             F
 ...                ..           ..
  O         O       ..O         O..
           ...      ..           ..

```

If all directions contain fire you die, otherwise there is an escape.

Edit: Back to taking a string as input, and now only checks for up/right, but also checks the input backwards (giving down/left)

Saved a lot of bytes thanks to Mr. Xcoder and Felipe Nardi Batista

# Answer
> 2 votes
# JavaScript, 174 bytes

```
a=>+(t=>g=a=>t--?g(a.map((l,y)=>l.map((c,x)=>(h=v=>[(a[y-1]||[])[x],(a[y+1]||[])[x],a[y][x+1],a[y][x-1],c].includes(v),!c&&h()?p=1:[2,0,1].find(h))))):p)((p=a+'!').length)(a)

```

Input format:

* Array of Array of Integers
* 2 for `F`, 1 for `.`, 0 for `O`

Output:

* Truthy value (1) for survive
* Falsy value (NaN) for die

Try It:

```
f=a=>+(t=>g=a=>t--?g(a.map((l,y)=>l.map((c,x)=>(h=v=>[(a[y-1]||[])[x],(a[y+1]||[])[x],a[y][x+1],a[y][x-1],c].includes(v),!c&&h()?p=1:[2,0,1].find(h))))):p)((p=a+'!').length)(a)
t=s=>f(s.trim().split('\n').map(x=>x.split('').map(n=>({F:2,'.':1,O:0}[n]))))

console.log(t(`
FFFFF
.....
..O..
.....
`))

console.log(t(`
FFFF
FFFO
FFFF
`))

console.log(t(`
.F....
......
......
.F....
..O...
.FF...
.F....
..FF..
`))

console.log(t(`
...F...F
F.......
........
.F......
....O...
...F....
........
.F....F.
`))

console.log(t(`
FFF
FOF
FFF
`))

console.log(t(`
F.F
.O.
F.F
`))

console.log(t(`
....F
.....
..O..
.....
F....
`))

console.log(t(`
.F....F.
........
........
F..O....
........
.....F..
`))

console.log(t(`
...F...F
F......F
........
.F......
....O...
...F....
........
.F....F.
`))
```

Consider a cellular automaton. There are 3 states for a cell `O` (reachable by people), `F` (catch fired), `.` (nothing just happened). The rule for create next generation is:

```
for each cell:
  me and my 4 neighborhoods,
    if anyone is `F` then result is `F`,
    otherwise, if anyone is `O` then result is `O`
    otherwise, keep state `.`

```

Once there is an cell on edge has `O` state, the people survive. If this not happened in enough amount generation, then the people died.

```
// check for all neighbors:
h=v=>[(a[y-1]||[])[x],(a[y+1]||[])[x],a[y][x+1],a[y][x-1],c].includes(v)
// if me == 'O' and i'm edge (neighbors contain _undefined_), then survive
!c&&h()?p=1
// Otherwise apply the given rule
:[2,0,1].find(h)

```

# Answer
> 2 votes
# Octave, 71 bytes

```
@(a)(A=blkdiag(0,a,0))<3||any((bwdist(A>2,'ci')>bwdist(A==2,'ci'))(!A))

```

Try it online!

or

Verify all test cases!

Input format:

* 2D array of integers
* `1` for `.`, `2` for `O` and `3` for `F`

Output:

* `true` and `false`

Explanation:

Explanation:

```
A=blkdiag(0,a,0)    % add a boundary of 0s around the array
A<3                 % return truthy when there is no fire
bwdist(A>2,'ci')    % city block distance transform of binary map of fire
bwdist(A==2,'ci')   % city block distance transform of binary map of your location
any(...)(!A)        % check if there is at least one element on the boundary of
                    % the fire distance map has its distance greater than
                    % that of distance map of your location

```

# Answer
> 1 votes
# Retina, 243 bytes

```
^.*O(.|¶)*|(.|¶)*O.*$|(.|¶)*(¶O|O¶)(.|¶)*
O
m`^((.)*) (.*¶(?<-2>.)*(?(2)(?!))O)
$1#$3
m`^((.)*O.*¶(?<-2>.)*(?(2)(?!)))
$1#
T`p`\O`#| ?O ?
+m`^((.)*)[O ](.*¶(?<-2>.)*(?(2)(?!))F)
$1#$3
+m`^((.)*F.*¶(?<-2>.)*(?(2)(?!)))[O ]
$1#
}T`p`F`#|.?F.?
O

```

Try it online! Requires the background to be spaces rather than `.`s (or some other regexp-safe character could be used). Explanation:

```
^.*O(.|¶)*|(.|¶)*O.*$|(.|¶)*(¶O|O¶)(.|¶)*
O

```

If there is an `O` on any edge, delete everything else (survival case)

```
m`^((.)*) (.*¶(?<-2>.)*(?(2)(?!))O)
$1#$3

```

Place a `#` in any space above an existing `O`.

```
m`^((.)*O.*¶(?<-2>.)*(?(2)(?!)))
$1#

```

And a `#` in any space below an existing `O`.

```
T`p`\O`#| ?O ?

```

Change the `#`s to `O`s, and also any space to the left or right of an existing `O`.

```
+m`^((.)*)[O ](.*¶(?<-2>.)*(?(2)(?!))F)
$1#$3

```

Place `#`s above any existing `F`s. These can overwrite `O`s as well as spaces.

```
+m`^((.)*F.*¶(?<-2>.)*(?(2)(?!)))[O ]
$1#

```

Place `#`s below any existing `F`s, also overwriting `O`s as well as spaces.

```
}T`p`F`#|.?F.?

```

Change the `#`s to `F`s, and also any `O` or space to the left or right of an existing `F`. Repeat until the `F`s have consumed everything.

```
O

```

Return `1` for survival, `0` if not.

---
Tags: code-golf, decision-problem, grid, simulation
---


# Question
Title: Life is a Maze: We take the wrong Path before we learnt to walk
# Input:

A maze containing the characters:

* `--` (horizontal wall);
* `|` (vertical wall);
* `+` (connection);
* (walking space);
* `I` (entrance);
* `U` (exit).

I.e. an input could look like this:

```
 +--+--+--+--+--+--+--+--+--+--+
I               |     |        |
 +  +--+--+--+  +  +  +  +--+  +
 |           |     |  |  |     |
 +--+--+--+  +--+--+  +  +  +--+
 |           |     |     |     |
 +  +--+--+  +  +--+--+  +--+  +
 |     |     |     |     |     |
 +--+  +  +--+--+  +--+--+  +  +
 |     |        |        |  |  |
 +  +--+--+--+  +--+--+  +  +  +
 |     |     |     |        |  |
 +--+  +  +--+--+  +--+--+--+--+
 |  |  |                 |     |
 +  +  +--+--+--+  +--+  +  +  +
 |     |        |  |  |  |  |  |
 +--+--+  +  +--+  +  +  +--+  +
 |        |     |     |  |     |
 +  +--+--+--+  +  +  +  +  +--+
 |           |     |  |         U
 +--+--+--+--+--+--+--+--+--+--+

```

# Output:

The *most efficient* path you should walk to get from the entrance to the exit of the maze (through the maze), indicated by the characters indicating left, right, up and down (i.e. `>`; `<`; `^`; `v`).

**Challenge rules:**

* You can take the input in any reasonable format. String-array, single String with new-lines, 2D char-array, etc. are all possible input formats.
* The output can consist of any four distinct characters. I.e. `><^v`; `→←↑↓`; `⇒⇐⇑⇓`; `RLUD`; `0123`; `ABCD`; etc.).
* You are allowed to add spaces or trailing new-line to the output if preferred; this is optional.
* The steps are counted per square (see four `+`-symbols for the squares), and not per character.
* The maze can be of size 5x5 through 15x15, and will always be a square (so there won't be any test cases for 5x10 mazes).
* You can assume that every maze has one or more valid paths from start to finish, and you always output the shortest (see test cases 4 and 5).
* If there are multiple paths with the same length, you can choose which one to output (see test case 6).
* You cannot 'walk' outside the borders of the maze (see test cases 7 and 8).

**General rules:**

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code.
* Also, please add an explanation if necessary.

**Test cases:**

```
1. Input:
 +--+--+--+--+--+--+--+--+--+--+
I               |     |        |
 +  +--+--+--+  +  +  +  +--+  +
 |           |     |  |  |     |
 +--+--+--+  +--+--+  +  +  +--+
 |           |     |     |     |
 +  +--+--+  +  +--+--+  +--+  +
 |     |     |     |     |     |
 +--+  +  +--+--+  +--+--+  +  +
 |     |        |        |  |  |
 +  +--+--+--+  +--+--+  +  +  +
 |     |     |     |        |  |
 +--+  +  +--+--+  +--+--+--+--+
 |  |  |                 |     |
 +  +  +--+--+--+  +--+  +  +  +
 |     |        |  |  |  |  |  |
 +--+--+  +  +--+  +  +  +--+  +
 |        |     |     |  |     |
 +  +--+--+--+  +  +  +  +  +--+
 |           |     |  |         U
 +--+--+--+--+--+--+--+--+--+--+

1. Output:
>v>>>vv<v>>v>v>>vvv>>>

2. Input:
 +--+--+--+--+--+
I   |        |  |
 +  +--+--+  +  +
 |        |  |  |
 +  +--+  +  +  +
 |  |  |     |  |
 +  +  +--+  +  +
 |        |     |
 +--+  +  +--+--+
 |     |         U
 +--+--+--+--+--+

2. Output:
>vvv>>v>>>

3. Input:
 +--+--+--+--+--+
U      |        |
 +  +  +--+--+  +
 |  |     |     |
 +--+--+  +  +--+
 |        |     |
 +  +--+--+--+  +
 |  |     |     |
 +  +  +  +  +--+
 |     |         I
 +--+--+--+--+--+

3. Output:
<<<^<v<^^>>^<^<<

4. Input (test case with two valid paths):
 +--+--+--+--+--+
U      |        |
 +  +  +--+--+  +
 |  |           |
 +--+--+  +  +--+
 |        |     |
 +  +--+--+--+  +
 |  |     |     |
 +  +  +  +  +--+
 |     |         I
 +--+--+--+--+--+

4. Output:
<<^>^<^<<^<<     (<<<^<v<^^>>^<^<< is less efficient, and therefore not a valid output)

5. Input (test case with two valid paths):
                               I
+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+
|     |              |                    |  |
+  +  +  +--+--+--+  +  +--+--+  +--+--+  +  +
|  |     |        |     |        |     |     |
+--+--+--+  +--+  +  +--+--+--+--+  +--+--+--+
|     |  |  |  |     |     |           |     |
+  +  +  +  +  +--+  +  +  +  +--+--+  +--+  +
|  |        |        |  |     |        |     |
+  +--+--+--+  +--+--+  +  +--+  +--+--+  +--+
|  |     |     |        |  |     |     |     |
+  +--+  +  +--+  +--+--+  +--+--+  +  +--+  +
|  |     |        |     |           |        |
+  +  +--+--+--+--+  +  +--+--+--+  +--+  +--+
|     |     |        |        |  |     |     |
+--+--+--+  +  +--+--+  +--+  +  +--+  +--+  +
|              |     |     |        |  |  |  |
+  +--+--+--+--+  +  +  +--+--+--+  +  +  +  +
|     |  |     |  |  |        |        |  |  |
+--+  +  +  +  +  +  +--+--+  +  +  +--+  +  +
|     |     |  |  |  |           |  |     |  |
+--+  +--+--+  +  +  +  +--+--+--+  +  +  +  +
|     |        |  |  |     |        |  |  |  |
+  +--+  +--+--+  +  +--+--+  +  +--+  +  +  +
|        |     |  |     |     |  |     |  |  |
+--+--+--+  +  +  +--+  +  +--+--+  +--+  +  +
|  |        |        |     |        |     |  |
+  +  +--+--+--+--+  +--+--+  +--+--+  +--+  +
|  |              |              |     |     |
+  +  +  +--+--+--+--+--+--+--+--+  +--+  +--+
|     |                                |     |
+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+
                            U

5. Output:
v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv<^<v<<v>v>>>>>>>v     (v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv>v>>>^>>^>^^>vvv<v<v<<v is less efficient, and therefore not a valid output)

6. Input:
 +--+--+--+--+--+
I               |
 +  +  +  +  +  +
 |              |
 +  +  +  +  +  +
 |              |
 +  +  +  +  +  +
 |              |
 +  +  +  +  +  +
 |               U
 +--+--+--+--+--+

6. Output:
>>v>v>v>v> or >v>v>v>v>> or >>>>>vvvv> or etc. (all are equally efficient, so all 10-length outputs are valid)

7. Input:
 I  U
+  +  +--+--+--+
|  |        |  |
+  +--+--+  +  +
|     |     |  |
+--+  +  +--+  +
|        |  |  |
+  +--+  +  +  +
|     |        |
+--+  +--+--+  +
|     |        |
+--+--+--+--+--+

7. Output:
vv>v>^>^<<^

8. Input:
 +--+--+--+--+--+
 |     |        |
 +  +--+  +--+  +
I   |     |  |  |
 +  +  +--+  +  +
U   |     |  |  |
 +--+--+  +  +  +
 |     |     |  |
 +  +--+--+--+  +
 |
 +--+--+--+--+--+

8. Output:
>v<

```

Mazes generated using this tool (and in some cases slightly modified).

# Answer
> 8 votes
# Retina, ~~338~~ ~~281~~ ~~275~~ ~~273~~ 261 bytes

```
¶U
¶&
+`·(\w.+)$
|$1
((.)+I.+¶.+¶(?<-2>.)+)·
$1v
+`((.)*)\+(.).*(¶(?<-2>.)*.)((\w)|·)·?
$1$4$.4$3$6
·v
-v
G`1
·U
&
{`\B·\d+.(\w+)
$1K$&
(\w+)·\d+.\B
$&$1r
(?<=\D\2.(\w+).+?¶.*\D(\d+)[·&])\B
$1v
)`\D(\d+).\B(?=.+¶.*\D\1·(\w+))
$&$2A
^.+\d·(\w+)
&$1A
M!`&\w+
I|&

```

Try it online!

---

**Notes**

* Due to significant whitespaces, all spaces (`0x20`) are replaced with interpunct (`·`) both in this answer and the TIO link. The program works fine if the spaces are restored.
* Uses `AvKr` for up, down, left, and right, respectively. Those can be replaced with any **letters** except `I`.
* ~~Takes about 40s on TIO for the 15×15 test case. Be patient.~~ Reworked the part for finding the shortest path once the path reached the exit. Turns out that was taking a lot of time.
* Could completely break on mazes that are 66 or more cells wide but can handle mazes of arbitrary height. A fix for arbitrary width takes +1 byte.

---

# Explanation

The program consists of 3 phases:

* A **construction phase** to convert the maze to a compact format that is easier to work with (detailed below).
* A **fill phase** to actually solve the maze using a flood fill algorithm.
* A **return phase** to return the shortest path at the exit.

---

# Format

Since the original maze format is quite unwieldy, the first part of the program converts it into a different format.

**Cells**

In the original format, each cell is represented as a 2×3 region:

```
+               <top wall>      <top wall>
<left wall>     <data/space>    <space>

```

Since the right column contains no information, the program identifies cells as any 2×2 region with a `+` at the top-left.

This leaves us with 3 kinds of cells:

* **I Cells**: Cells that are properly inside the maze.
* **R Cells**: Cells that are to the right of the maze. These are created by the padding used to house the entrance or exit. For example, the exit `U` in test case 1 is in an R-Cell.
* **B Cells**: Cells that are below the maze. Like R-Cells, these are created by padding.

In the new format, cells are represented as a variable-length string:

```
<left wall> <column number> <top wall/exit marker> <path>

```

The left and top wall are copied from the original format. The column number is based on the horizontal position of the cell and is used for alignment (identifying cells directly on top of/beneath each other). Path is an alphabetical string used during the fill phase to save the shortest path to reach that cell. Path and exit marker will be further explained.

**Half-cells**

Although most of the maze are cells, there are regions of the maze that are not cells:

* **R Half-cells**: If there is no right padding, the `+`s along the right wall does not form cells since they are on the last column.
* **L Half-cells**: If there is left padding, cells cannot form there since there are no `+` to the left of them. For example, the entrance `I` in test case 1 is in an L Half-cell.

Technically, there are **T half-cells** above the maze (when there is top padding) and **B half-cells** (along the bottom wall when there is no bottom padding) but they are not represented in the new format.

The top row of a half-cell would be removed as part of constructing full cells in the same row, so half-cells are represented in the new format as

```
<wall/exit marker>? <path>

```

An R Half-cells is just `|`. An L Half-cells has just `I` as the path, just the exit marker and an empty path, or just an empty wall.

**Entrances and exits**

If the entrance is to the left, right or bottom of the maze, then the entrance marker `I` would naturally be included in the (half-)cell as the path, which can be removed when returning the final path.

If the entrance is above the maze, the first (downward) step is taken during the construction phase since T half-cells are removed during construction. This keeps a workable path in a full cell. The top wall is closed afterwards.

If the exit is to the left, right or bottom of the maze, then `U` would naturally be included in the (half-)cell. To avoid being mistaken as a path, the non-alphanum exit marker `&` is used instead of `U`. The exit marker is embedded into a cell or half-cell (as specified above).

If the exit is above the maze, then it would be the only hole that can go above the top row of cells (since the one for the entrance, if present, would be closed already). Any path reaching that hole can exit the maze by taking an upward step.

Lastly, any B Cell containing the entrance or exit must close its left wall to prevent "solving" the maze by walking along the B Cells. Entrances and exits in R Cells or L Half-cells need no further processing since the flood fill algorithm does not permit vertical movements to/from them.

**Example**

As an example, the first test case

```
·+--+--+--+--+--+--+--+--+--+--+·
I···············|·····|········|·
·+··+--+--+--+··+··+··+··+--+··+·
·|···········|·····|··|··|·····|·
·+--+--+--+··+--+--+··+··+··+--+·
·|···········|·····|·····|·····|·
·+··+--+--+··+··+--+--+··+--+··+·
·|·····|·····|·····|·····|·····|·
·+--+··+··+--+--+··+--+--+··+··+·
·|·····|········|········|··|··|·
·+··+--+--+--+··+--+--+··+··+··+·
·|·····|·····|·····|········|··|·
·+--+··+··+--+--+··+--+--+--+--+·
·|··|··|·················|·····|·
·+··+··+--+--+--+··+--+··+··+··+·
·|·····|········|··|··|··|··|··|·
·+--+--+··+··+--+··+··+··+--+··+·
·|········|·····|·····|··|·····|·
·+··+--+--+--+··+··+··+··+··+--+·
·|···········|·····|··|·········U
·+--+--+--+--+--+--+--+--+--+--+·

```

is

```
I·3-·6-·9-·12-·15-|18-·21-|24-·27-·30-|33·
·|3··6-·9-·12-|15··18·|21·|24·|27-·30·|33·
·|3-·6-·9-·12·|15-·18-|21··24·|27··30-|33·
·|3··6-|9-·12·|15··18-|21-·24·|27-·30·|33·
·|3-·6·|9··12-·15-|18··21-·24-|27·|30·|33·
·|3··6-|9-·12-|15··18-|21-·24··27·|30·|33·
·|3-|6·|9··12-·15-·18··21-·24-|27-·30-|33·
·|3··6·|9-·12-·15-|18·|21-|24·|27·|30·|33·
·|3-·6-·9·|12··15-|18··21·|24·|27-·30·|33·
·|3··6-·9-·12-|15··18·|21·|24··27··30-·33&

```

in the new format. You can convert other mazes here.

---

# Construction phase

The construction phase makes up the first 13 lines of the program.

```
¶U
¶&

```

Converts exit in L Half-cell to exit marker

```
+`·(\w.+)$
|$1

```

Adds walls to the left of entrance and exit in B Cells

```
((.)+I.+¶.+¶(?<-2>.)+)·
$1v

```

Takes the first step if entrance is above the maze

```
+`((.)*)\+(.).*(¶(?<-2>.)*.)((\w)|·)·?
$1$4$.4$3$6

```

Performs the actual conversion

```
·v
-v

```

Closes the top-entrance hole

```
G`1

```

Keeps only lines with a `1`. Since mazes are at least 5 cells wide and column numbers occurs at increments of 3, a line with new-format cells must have a contain a column number between 10 and 19.

```
·U
&

```

Converts exit in R Cell or B Cell to exit marker

---

# Fill phase

The fill phase makes up the next 8 lines of the program. It uses a flood fill algorithm to fill all cells with the shortest path to reach there from the entrance.

```
{`

```

Puts the whole fill phase on a loop to fill the whole maze.

```
\B·\d+.(\w+)
$1K$&

```

Each cell able to move left does so. A cell is able to move left if

1. it has a non-empty path
2. it has an empty left wall; and
3. the cell or L half-cell to its left has an empty path

```
(\w+)·\d+.\B
$&$1r

```

Then, each cell able to move right does so. A cell is able to move right if

1. it has a non-empty path
2. the cell to its right has an empty left wall; and
3. the cell to its right has an empty path

```
(?<=\D\2.(\w+).+?¶.*\D(\d+)[·&])\B
$1v

```

Then, each cell able to move down does so. A cell is able to move down if

1. it has a non-empty path
2. it has at least one cell or half-cell to its right (i.e. it is not an R Cell)
3. the cell below it (i.e. the cell on the next line with the same column number) has an empty top wall or has the exit marker; and
4. the cell below it has an empty path

Note that L Half-cells cannot move down since they don't have column numbers.

```
\D(\d+).\B(?=.+¶.*\D\1·(\w+))
$&$2A

```

Then, each cell able to move up does so. A cell is able to move up if

1. it has a non-empty path
2. it has an empty top wall
3. the cell above it has at least one cell or half-cell to its right; and
4. the cell above it has an empty path

---

# Return phase

The return phase makes up the last 5 lines of the program. This phase searches for and returns the path filled into the exit cell.

The pattern of the path at the exit depends on where the exit is:

1. If the exit is in an L Half-cell, then that half-cell would be `& <path>`
2. If the exit is in an R Cell or B Cell, then that cell would be `<left wall> <column number> & <path>`
3. If the exit is in a T Half-cell, then as noted above, the the I Cell leading to the exit would be `<left wall> <column number> · <path>` and on the top row.

```
^.+\d·(\w+)
&$1A

```

Finds a cell on the top line with an empty top wall and a non-empty path. This takes care of the last case by adding the last step and the exit marker.

```
M!`&\w+

```

Matches and returns a non-empty path following an exit marker.

```
I|&

```

Removes the exit marker and the `I` prefix of the path.

# Answer
> 13 votes
# Perl 6, ~~259~~ 295 bytes

```
{my \a=S:g/(.)$0+/{$0 x($/.comb+.5)*2/3}/;sub f (\c,\v,*@p) {with (c ne any v)&&a.lines».comb[+c[0];+c[1]] ->$_ {for (/\s/??10011221!!/I/??a~~/^\N*I|I\N*$/??2101!!1012!!'').comb X-1 {f [c Z+$^a,$^b],(|v,c),@p,chr 8592+$++}
take @p if /U/}}
[~] (gather f a~~/(\N+\n)*(.)*I/,[]).min(+*)[1,3...*]}

```

### How it works

1. ```
my \a = S:g/ (.) $0+ /{ $0 x ($/.chars + .5) * 2/3 }/;
```

This squeezes the maze so that the inside of each cell is 1x1 instead of 2x1 space characters:

```
 +--+--+--+--+--+             +-+-+-+-+-+
I   |        |  |            I  |     | |
 +  +--+--+  +  +             + +-+-+ + +
 |        |  |  |             |     | | |
 +  +--+  +  +  +             + +-+ + + +
 |  |  |     |  |     -->     | | |   | |
 +  +  +--+  +  +             + + +-+ + +
 |        |     |             |     |   |
 +--+  +  +--+--+             +-+ + +-+-+
 |     |         U            |   |      U
 +--+--+--+--+--+             +-+-+-+-+-+
```
2. ```
sub f (\c,\v,*@p) {
    with (c ne any v) &&                   # If the coordinate wasn't visited yet
         lines».comb[+c[0];+c[1]] -> $_ {  # and a character exists there...
        for (                          # For each vector...
             /\s/ ?? 10011221 !!       #  from a cell: (0,-1), (-1,0), (0,1), (1,0)
             /I/  ?? a~~/^\N*I|I\N*$/
                      ?? 2101          #  from a top/bottom entrance: (1,0), (-1,0)
                      !! 1012          #  from a left/right entrance: (0,-1), (0,1)
                  !! ''                #  otherwise: none
            ).comb X-1 {
            f                       #   Recurse with arguments:
                [c Z+ $^a, $^b],    #     c plus the vector
                (|v, c),            #     v with c appended
                @p, chr 8592 + $++  #     p with the correct Unicode arrow appended
        }
        take @p if /U/
    }
}
```

This is the recursive path-finding function. It takes three parameters: The current coordinate `c=(y,x)`, the list of already visited coordinates `v`, and the path `p` taken so far (as a list of arrow characters).

If the character at the current coordinate is a space, it recurses to its four neighbors.
If the character at the current coordinate is a `I`, it recurses to the two neighbors that aren't "along the edge", to force solutions to go through the maze and not around it.
If the character at the current coordinate is a `U`, it calls `take` on the accumulated path string.

3. ```
[~] (gather f a ~~ /(\N+\n)*(.)*I/, []).min(+*)[1,3...*]
```

The recursive function is initially called with the coordinate of the letter `I`, which is found using a regex.

The `gather` keyword collects all values on which `take` was called inside the function, i.e. all valid non-cyclical paths through the maze.

The shortest path is chosen, every second arrow is dropped to account for the fact that two identical moves are required to get from one cell to the next, and the remaining arrows are concatenated to form the string that is returned from the lambda.

# Answer
> 6 votes
# Python 2: 302 bytes

```
from re import*
r=lambda x:[''.join(_)for _ in zip(*x)][::-1]
z=',l)for l in s]'
def f(s,b=1,o=0,n=0):
 exec("s=[sub('(..).(?!$)',r'\\1'%s;"%z+"s=r([sub(' I ','+I+'%s);"%z*4)*b+"t=[sub('I  ','@@I'"+z
 if'I U'in`s`or n>3:return`o%4`+n/4*`s`
 return min(`o%4`+f(t,0,o,4*(t==s)),f(r(s),0,o+1,n+1),key=len)

```

Takes input as an array of strings all with the same length. Prints `0` for right, `1` for down, `2` for left, and `3` for up.

### Explanation

I took a different approach than the other answers. General idea: recursively search by finding the shortest path between going straight forward and rotating the board 90 degrees.

```
from re import*
r=lambda x:[''.join(_)for _ in zip(*x)][::-1] #Rotates the board counterclockwise
z=',l)for l in s]'    #Suffix for hacky exec golfing
def f(s,b=1,o=0,n=0): #b is 1 on initial call, 0 on every recursion
                      #o is orientation
                      #n is number of rotations
 exec("s=[sub('(..).(?!$)',r'\\1'%s;"%z  #Squeeze the maze
      +"s=r([sub(' I ','+I+'%s);"%z*4)   #Add walls around the I to keep it in the maze
      *b                                 #Only if b is 1
      +"t=[sub('I  ','@@I'"+z            #Attempt to move right

 if'I U'in`s`or n>3:return`o%4`+n/4*`s`  #If the I is next to the U, return the orientation
                                         #If there were 4 rotations, return a long string
 return min(                             #Return the path with the shortest length:
            `o%4`+f(t,0,o,4*(t==s)),       #Moving forward if possible
            f(r(s),0,o+1,n+1),             #Rotating the board
        key=len)

```

Try it online!

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

```
a=>(a=a.map(s=>s.filter((_,i)=>!i|i%3)),g=([x,y])=>a[y]&&a[y][x],o=[],c=([x,y],m="",v=[])=>[[0,1],[1,0],[0,-1],[-1,0]].map(([j,k],i)=>(p=[x+j,y+k],!m&(!y|y>a[l="length"]-2)==i%2|v.includes(""+p)||(g(p)<"!"?c(p,m+"v>^<"[i],[...v,""+p]):g(p)=="U"?o.push(m.replace(/(.)\1/g,"$1")):0))),a.map((h,i)=>h.map((k,j)=>k=="I"&&c([j,i]))),o.sort((a,b)=>a[l]-b[l])[0])

```

Takes input as a 2D array of characters. Each line must be left-padded by one space and have no trailing space, no matter where the start/end points are.

Uses smls's idea of squishing the maze to make each cell 1x1 and removing repeated arrows from the output.

## Ungolfed and Explained

```
a=>(
    a=a.map(s=>s.filter((_,i)=>!i|i%3)),    // squish the maze to 1x1 cells
    g=([x,y])=>a[y]&&a[y][x],               // helper func to get maze value
    o=[],                                   // resulting movesets
    c=([x,y], m="", v=[]) =>                // recursive func to search
                                            // takes current point, moves, and visited spots
        [[0,1],[1,0],[0,-1],[-1,0]].map(([j,k],i)=>(// for each direction
            p=[x+j,y+k],
            !m & (!y | y>a[l="length"]-2) == i%2 |  // if first move, prevent moving out of maze
                v.includes(""+p) || (               // also prevent if already visited
                    g(p)<"!" ?                      // is this a space?
                        c(p, m+"v>^<"[i], [...v,""+p]) // check this spot recursively
                    : g(p)=="U" ?                   // if this the end?
                        o.push(                     // add moves to moveset
                            m.replace(/(.)\1/g,"$1")) // with double arrows removed
                    : 0
                )
        )),

    a.map((h,i)=>h.map((k,j)=>      // find the starting "I" and
        k=="I" && c([j,i])          // begin recursion at that point
    )),

    o.sort((a,b)=>a[l]-b[l])[0]     // get shortest path
)

```

## Test Snippet

```
f=
a=>(a=a.map(s=>s.filter((_,i)=>!i|i%3)),g=([x,y])=>a[y]&&a[y][x],o=[],c=([x,y],m="",v=[])=>[[0,1],[1,0],[0,-1],[-1,0]].map(([j,k],i)=>(p=[x+j,y+k],!m&(!y|y>a[l="length"]-2)==i%2|v.includes(""+p)||(g(p)<"!"?c(p,m+"v>^<"[i],[...v,""+p]):g(p)=="U"?o.push(m.replace(/(.)\1/g,"$1")):0))),a.map((h,i)=>h.map((k,j)=>k=="I"&&c([j,i]))),o.sort((a,b)=>a[l]-b[l])[0])

let tests = [" +--+--+--+--+--+--+--+--+--+--+\nI               |     |        |\n +  +--+--+--+  +  +  +  +--+  +\n |           |     |  |  |     |\n +--+--+--+  +--+--+  +  +  +--+\n |           |     |     |     |\n +  +--+--+  +  +--+--+  +--+  +\n |     |     |     |     |     |\n +--+  +  +--+--+  +--+--+  +  +\n |     |        |        |  |  |\n +  +--+--+--+  +--+--+  +  +  +\n |     |     |     |        |  |\n +--+  +  +--+--+  +--+--+--+--+\n |  |  |                 |     |\n +  +  +--+--+--+  +--+  +  +  +\n |     |        |  |  |  |  |  |\n +--+--+  +  +--+  +  +  +--+  +\n |        |     |     |  |     |\n +  +--+--+--+  +  +  +  +  +--+\n |           |     |  |         U\n +--+--+--+--+--+--+--+--+--+--+"," +--+--+--+--+--+\nI   |        |  |\n +  +--+--+  +  +\n |        |  |  |\n +  +--+  +  +  +\n |  |  |     |  |\n +  +  +--+  +  +\n |        |     |\n +--+  +  +--+--+\n |     |         U\n +--+--+--+--+--+"," +--+--+--+--+--+\nU      |        |\n +  +  +--+--+  +\n |  |     |     |\n +--+--+  +  +--+\n |        |     |\n +  +--+--+--+  +\n |  |     |     |\n +  +  +  +  +--+\n |     |         I\n +--+--+--+--+--+"," +--+--+--+--+--+\nU      |        |\n +  +  +--+--+  +\n |  |           |\n +--+--+  +  +--+\n |        |     |\n +  +--+--+--+  +\n |  |     |     |\n +  +  +  +  +--+\n |     |         I\n +--+--+--+--+--+","                                I\n +--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+\n |     |              |                    |  |\n +  +  +  +--+--+--+  +  +--+--+  +--+--+  +  +\n |  |     |        |     |        |     |     |\n +--+--+--+  +--+  +  +--+--+--+--+  +--+--+--+\n |     |  |  |  |     |     |           |     |\n +  +  +  +  +  +--+  +  +  +  +--+--+  +--+  +\n |  |        |        |  |     |        |     |\n +  +--+--+--+  +--+--+  +  +--+  +--+--+  +--+\n |  |     |     |        |  |     |     |     |\n +  +--+  +  +--+  +--+--+  +--+--+  +  +--+  +\n |  |     |        |     |           |        |\n +  +  +--+--+--+--+  +  +--+--+--+  +--+  +--+\n |     |     |        |        |  |     |     |\n +--+--+--+  +  +--+--+  +--+  +  +--+  +--+  +\n |              |     |     |        |  |  |  |\n +  +--+--+--+--+  +  +  +--+--+--+  +  +  +  +\n |     |  |     |  |  |        |        |  |  |\n +--+  +  +  +  +  +  +--+--+  +  +  +--+  +  +\n |     |     |  |  |  |           |  |     |  |\n +--+  +--+--+  +  +  +  +--+--+--+  +  +  +  +\n |     |        |  |  |     |        |  |  |  |\n +  +--+  +--+--+  +  +--+--+  +  +--+  +  +  +\n |        |     |  |     |     |  |     |  |  |\n +--+--+--+  +  +  +--+  +  +--+--+  +--+  +  +\n |  |        |        |     |        |     |  |\n +  +  +--+--+--+--+  +--+--+  +--+--+  +--+  +\n |  |              |              |     |     |\n +  +  +  +--+--+--+--+--+--+--+--+  +--+  +--+\n |     |                                |     |\n +--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+\n                             U"," +--+--+--+--+--+\nI               |\n +  +  +  +  +  +\n |              |\n +  +  +  +  +  +\n |              |\n +  +  +  +  +  +\n |              |\n +  +  +  +  +  +\n |               U\n +--+--+--+--+--+","  I  U\n +  +  +--+--+--+\n |  |        |  |\n +  +--+--+  +  +\n |     |     |  |\n +--+  +  +--+  +\n |        |  |  |\n +  +--+  +  +  +\n |     |        |\n +--+  +--+--+  +\n |     |        |\n +--+--+--+--+--+"," +--+--+--+--+--+\n |     |        |\n +  +--+  +--+  +\nI   |     |  |  |\n +  +  +--+  +  +\nU   |     |  |  |\n +--+--+  +  +  +\n |     |     |  |\n +  +--+--+--+  +\n |               \n +--+--+--+--+--+"];
S.innerHTML="<option>Tests"+Array(tests.length).fill().map((_,i)=>"<option>"+(i+1)).join``;
```

```
<select id=S oninput="I.value=S.selectedIndex?tests[S.value-1]:''"></select><br>
<textarea id=I rows=20 cols=50></textarea><br><button onclick="O.innerHTML=f(I.value.split`\n`.map(x=>[...x]))">Run</button>
<pre id=O>
```

# Answer
> 2 votes
# Retina, 416 bytes

```
T` `+`^.*| ?¶.|.*$
I
#
{+` (\w)
d$1
+`(\w)
$1a
+`(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}+m`(^(.)*\w.*¶(?<-2>.)*(?(2)(?!)))
$1w
^
w¶
w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))
$4$5$6¶$1
{`^(.*d)(¶(.|¶)*)#(\w)
$1$4$2 #
^(.*a)(¶(.|¶)*)(\w)#
$1$4$2#
^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)
$1$6$2 $5#
}`^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#
$1$5$2#$6
s`U.*

(a|d)\1\1?
$1
ss
s
ww
w

```

Try it online! Had I seen this question when it was originally posted, this is probably the answer I would have given, so I'm posting it anyway, even though there's a much better answer in Retina. Explanation:

```
T` `+`^.*| ?¶.|.*$

```

Fill in the border. This avoids walking around the outside of the maze (e.g. for test case 7).

```
I
#

```

Place a non-alphabetic marker at the entrance.

```
{+` (\w)
d$1
+`(\w)
$1a
+`(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}+m`(^(.)*\w.*¶(?<-2>.)*(?(2)(?!)))
$1w

```

Flood fill from the exit to the entrance. At each step, use a letter to indicate the best direction to go (wasd - this might be familiar to gamers; I had also considered hjkl but I found it too confusing). Additionally, prefer to repeat the same direction; this avoids going left/right in between two vertically adjacent cells.

```
^
w¶

```

Assume the first step is down.

```
w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))
$4$5$6¶$1

```

But if there's a letter above, left or right of the entrance, change that to the first step.

```
{`^(.*d)(¶(.|¶)*)#(\w)
$1$4$2 #
^(.*a)(¶(.|¶)*)(\w)#
$1$4$2#
^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)
$1$6$2 $5#
}`^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#
$1$5$2#$6

```

Move the marker in the direction of the last move, reading the direction of the next move from the square that the marker is moving to, and add that to the list of directions. This repeats until the `U` is reached.

```
s`U.*

```

Delete everything after the directions as it's not needed any more.

```
(a|d)\1\1?
$1
ss
s
ww
w

```

The original grid is on a 3×2 layout. While moving vertically if we zig-zag horizontally the flood fill will optimise the movement and only move 3n-1 characters horizontally, so when dividing by three, we need to round up. Vertically we just divide by 2.

I also investigated a true square grid solution i.e where the character matrix is itself square rather than being a 3×2 layout with an optional border. While probably nonconforming to the question, the ability to transpose reduced the byte count to 350: Try it online!

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