title: Write a Clem interpreter

text:
# Question
Title: Write a Clem interpreter
Clem is a minimal stack-based programming language featuring first-class functions. Your objective is to write an interpreter for the Clem language. It should properly execute all examples included in the reference implementation, which is available here.

## The Clem language

Clem is a stack based programming language with first-class functions. The best way to learn Clem is to run the `clem` interpreter with no arguments. It will start in interactive mode, allowing you to play with the available commands. To run the example programs, type `clem example.clm` where example is the name of the program. This brief tutorial should be enough to get you started.

There are two main classes of functions. Atomic functions and compound functions. Compound functions are lists composed of other compound functions and atomic functions. Note that a compound function cannot contain itself.

## Atomic Functions

The first type of atomic function is the *constant*. A *constant* is simply an integer value. For example, -10. When the interpreter encounters a *constant*, it pushes it to the stack. Run `clem` now. Type `-10` at the prompt. You should see

```
> -10
001: (-10)
>

```

The value `001` describes the position of the function in the stack and `(-10)` is the *constant* you just entered. Now enter `+11` at the prompt. You should see

```
> +11
002: (-10)
001: (11)
>

```

Notice that `(-10)` has moved to the second position in the stack and `(11)` now occupies the first. This is the nature of a stack! You will notice that `-` is also the decrement command. Whenever `-` or `+` precede a number, they denote the sign of that number and not the corresponding command. All other atomic functions are *commands*. There are 14 in total:

```
@  Rotate the top three functions on the stack
#  Pop the function on top of the stack and push it twice
$  Swap the top two functions on top of the stack
%  Pop the function on top of the stack and throw it away
/  Pop a compound function. Split off the first function, push what's left,
   then push the first function.
.  Pop two functions, concatenate them and push the result
+  Pop a function. If its a constant then increment it. Push it
-  Pop a function. If its a constant then decrement it. Push it
<  Get a character from STDIN and push it to the stack. Pushes -1 on EOF.
>  Pop a function and print its ASCII character if its a constant
c  Pop a function and print its value if its a constant
w  Pop a function from the stack. Peek at the top of the stack. While it is
   a non-zero constant, execute the function.

```

Typing a command at the prompt will execute the command. Type `#` at the prompt (the duplicate command). You should see

```
> #
003: (-10)
002: (11)
001: (11)
>

```

Notice that the (11) has been duplicated. Now type `%` at the prompt (the drop command). You should see

```
> %
002: (-10)
001: (11)
>

```

To push a command to the stack, simply enclose it in parenthesis. Type `(-)` at the prompt. This will push the decrement operator to the stack. You should see

```
> (-)
003: (-10)
002: (11)
001: (-)
>

```

## Compound functions

You may also enclose multiple atomic functions in parenthesis to form a compound function. When you enter a compound function at the prompt, it is pushed to the stack. Type `($+$)` at the prompt. You should see

```
> ($+$)
004: (-10)
003: (11)
002: (-)
001: ($ + $)
>

```

Technically, everything on the stack is a compound function. However, some of the compound functions on the stack consist of a single atomic function (in which case, we will consider them to be atomic functions for the sake of convenience). When manipulating compound functions on the stack, the `.` command (concatenation) is frequently useful. Type `.` now. You should see

```
> .
003: (-10)
002: (11)
001: (- $ + $)
>

```

Notice that the first and second functions on the stack were concatenated, and that the second function on the stack comes first in the resulting list. To execute a function that is on the stack (whether it is atomic or compound), we must issue the `w` command (while). The `w` command will pop the first function on the stack and execute it repeatedly so long as the second function on the stack is a non-zero constant. Try to predict what will happen if we type `w`. Now, type `w`. You should see

```
> w
002: (1)
001: (0)
>

```

Is that what you expected? The two numbers sitting on top of the stack were added and their sum remains. Let's try it again. First we'll drop the zero and push a 10 by typing `%10`. You should see

```
> %10
002: (1)
001: (10)
>

```

Now we'll type the entire function in one shot, but we'll add an extra `%` at the end to get rid of the zero. Type `(-$+$)w%` at the prompt. You should see

```
> (-$+$)w%
001: (11)
>

```

(Note this algorithm only works if the first constant on the stack is positive).

## Strings

Strings are also present. They are mostly syntactic sugar, but can be quite useful. When the interpreter encounters a string, it pushes each character from last to first onto the stack. Type `%` to drop the 11 from the previous example. Now, type `0 10 "Hi!"` on the prompt. The `0` will insert a NULL terminator and the `10` will insert a new-line character. You should see

```
> 0 10 "Hi!"
005: (0)
004: (10)
003: (33)
002: (105)
001: (72)
>

```

Type `(>)w` to print characters from the stack until we encounter the NULL terminator. You should see

```
> (>)w
Hi!
001: (0)
>

```

## Conclusions

Hopefully this should be enough to get you started with the interpreter. The language design should be relatively straight-forward. Let me know if anything is terribly unclear :) A few things have been left intentionally vague: values must be signed and *at least* 16 bits, the stack must be large enough to run all reference programs, etc. Many details haven't been carved out here because a full blown language specification would be prohibitively large to post (and I haven't written one yet :P). When in doubt, mimic the reference implementation.

The esolangs.org page for Clem

The reference implementation in C

# Answer
> 5 votes
# Haskell, ~~931~~ ~~921~~ 875

this isn't fully golfed yet but it will probably never be. Still, it is already shorter than all other solutions. ~~I will golf this more soon.~~ I don't feel like golfing it any more than this.

probably has a few subtle bugs because I didn't play with the C reference implementation.

this solution uses the type `StateT [String] IO ()` to store a "runnable" clem program. most the program is a parser which parses the "runnable program".

in order to run this use `r "<insert clem program here>"`.

```
import Text.Parsec
import Control.Monad.State
import Control.Monad.Trans.Class
import Data.Char
'#'%(x:y)=x:x:y
'%'%(x:y)=y
'@'%(x:y:z:w)=y:z:x:w
'$'%(x:y:z)=y:x:z
'/'%((a:b):s)=[a]:b:s
'+'%(a:b)=i a(show.succ)a:b
'.'%(a:b:c)=(a++b):c
_%x=x
b=concat&between(s"(")(s")")(many$many1(noneOf"()")<|>('(':)&((++")")&b))
e=choice[s"w">>c(do p<-t;let d=h>>= \x->if x=="0"then a else u p>>d in d),m&k,s"-">>(m&(' ':)&k<|>c(o(\(a:b)->i a(show.pred)a:b))),s"c">>c(do
 d<-t
 i d(j.putStr.show)a),o&(++)&map(show.ord)&between(s"\"")(s"\"")(many$noneOf"\""),(do
 s"<"
 c$j getChar>>=m.show.ord),(do
 s">"
 c$do
 g<-t
 i g(j.putChar.chr)a),m&b,o&(%)&anyChar]
k=many1 digit
i s f g|(reads s::[(Int,String)])>[]=f$(read s::Int)|0<1=g
t=h>>=(o tail>>).c
c n=return n
a=c()
h=head&get
(&)f=fmap f
m=o.(:)
o=modify
u=(\(Right r)->r).parse(sequence_&many e)""
r=(`runStateT`[]).u
s=string
j=lift

```

# Answer
> 7 votes
# Python, ~~1684~~ 1281 characters

Got all the basic golf stuff done. It runs all the example programs and matches the output character-for-character.

```
import sys,os,copy as C
L=len
S=[]
n=[S]
Q=lambda:S and S.pop()or 0
def P(o):
 if o:n[0].append(o)
def X():x=Q();P(x);P(C.deepcopy(x))
def W():S[-2::]=S[-1:-3:-1]
def R():a,b,c=Q(),Q(),Q();P(a);P(c);P(b)
def A(d):
 a=Q()
 if a and a[0]:a=[1,a[1]+d,lambda:P(a)]
 P(a)
def V():
 a=Q();P(a)
 if a and a[0]-1and L(a[2])>1:r=a[2].pop(0);P(r)
def T():
 b,a=Q(),Q()
 if a!=b:P([0,0,(a[2],[a])[a[0]]+(b[2],[b])[b[0]]])
 else:P(a);P(b)
def r():a=os.read(0,1);F(ord(a)if a else-1)
def q(f):
 a=Q()
 if a and a[0]:os.write(1,(chr(a[1]%256),str(a[1]))[f])
def e(f,x=0):f[2]()if f[0]+f[1]else([e(z)for z in f[2]]if x else P(f))
def w():
 a=Q()
 while a and S and S[-1][0]and S[-1][1]:e(a,1)
def Y():n[:0]=[[]]
def Z():
 x=n.pop(0)
 if x:n[0]+=([[0,0,x]],x)[L(x)+L(n)==2]
D={'%':Q,'#':X,'$':W,'@':R,'+':lambda:A(1),'-':lambda:A(-1),'/':V,'.':T,'<':r,'>':lambda:q(0),'c':lambda:q(1),'w':w,'(':Y,')':Z}
def g(c):D[c]()if L(n)<2or c in'()'else P([0,1,D[c]])
N=['']
def F(x):a=[1,x,lambda:P(a)];a[2]()
def E():
 if'-'==N[0]:g('-')
 elif N[0]:F(int(N[0]))
 N[0]=''
s=j=""
for c in open(sys.argv[1]).read()+' ':
 if j:j=c!="\n"
 elif'"'==c:E();s and map(F,map(ord,s[:0:-1]));s=(c,'')[L(s)>0]
 elif s:s+=c
 elif';'==c:E();j=1
 else:
    if'-'==c:E()
    if c in'-0123456789':N[0]+=c
    else:E();c in D and g(c)

```

**Testing**:

Gather clemint.py, clemtest\_data.py, clemtest.py, and a compiled `clem` binary into a directory and run `clemtest.py`.

**Expanation**:

The most ungolfed version is this one. Follow along with that one.

`S` is the main stack. Each item of the stack is a 3-list, one of:

```
Constant: [1, value, f]
Atomic: [0, 1, f]
Compound: [0, 0, fs]

```

For the constants, `f` is a function which pushes the constant onto the stack. For the atmoics, `f` is a function which executes one of the operations (e.g. `-`, `+`). For the compounds, `fs` is a list of items.

`xec` executes an item. If it's a constant or an atomic, it just executes the function. If it's a compound, if there has been no recursion yet, it executes each function. So executing `(10 20 - 30)` will execute each of the functions `10`, `20`, `-`, and `30`, leaving `10 19 30` on the stack. If there has been recursion, then it just pushes the compound function onto the stack. For example, when executing `(10 20 (3 4) 30)`, the result should be `10 20 (3 4) 30`, not `10 20 3 4 30`.

Nesting was a bit tricky. What do you do while reading off `(1 (2 (3 4)))`? The solution is to have a stack of stacks. At each nesting level, a new stack is pushed on the stack of stacks, and all push operations go onto this stack. Further, if there has been nesting, then atomic functions are pushed instead of executed. So if you see `10 20 (- 30) 40`, `10` is pushed, then `20`, then a new stack is created, `-` and `30` are pushed onto the new stack, and `)` pops off the new stack, turns it into an item, and pushes it onto the stack one level down. `endnest()` handles `)`. It was a bit tricky since there's a special case when only one item has been pushed and we're pushing back onto the main stack. That is, `(10)` should push the constant `10`, not a composite with the one constant, because then `-` and `+` don't work. I'm not sure whether this is principled but it's the way it works...

My interpreter is a character-by-character processor - it doesn't create tokens - so numbers, strings, and comments were somewhat annoying to deal with. There's a separate stack, `N`, for a currently-being-processed-number, and anytime a character which isn't a number is processed, I have to call `endnum()` to see whether I should first complete that number and put it on the stack. Whether we're in a string or a comment is kept track of by boolean variables; when a string is closed it pushes all the innards on the stack. Negative numbers required some special handling as well.

That's about it for the overview. The rest was implementing all the built-ins, and making sure to do deep copies in `+`, `-`, and `#`.

# Answer
> 7 votes
# C 832

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

This treats everything as simple strings - all stack items are strings, even constants are strings.

```
#define Q strcpy
#define F(x)bcopy(b,f,p-b);f[p-b x]=!Q(r,p);
#define C(x,y)Q(S[s-x],S[s-y]);
#define N[99]
#define A Q(S[s++]
#define D sprintf(S[s++],"%d"
#define G(x);}if(*f==x){
#define H(x)G(x)s--;
#define R return
#define Z(x)T(t,u,v)-1||putchar(x)H(
z=1,*y;char S N N;s;c;T(b,f,r,p)char*b,*f,*r,*p;{strtol(b+=strspn(b," "),&p,0);if(p>b){F()R 1;}if(c=*b==40){for(p=++b;c;p++)if(z^=*p==34)c+=*p-41?*p==40:-1;F(-1)R-1;}p++;F()*r*=!!*b;R 0;}*P(char*p){R*p-34?y=P(p+1),D,*p),y:++p;}E(int*x){char*p,c N,f N,r N,t N,u N,v N;for(Q(c,x);*c;Q(c,p)){Q(t,S[s-1]);if(T(c,f,p=r))A,f);else{{G(64)C(0,1)C(1,2)C(2,3)C(3,0)G(35)A,t)G(36)C(0,2)C(2,1)C(1,0)H(37)H(47)T(t,u,v);*v&&A,v);A,u)H(46)strcat(strcat(S[s-1]," "),t)H(43)D,atoi(t)+1)H(45)D,atoi(t)-1)G(60)D,getchar())H(62)Z(atoi(u))99)Z(*u)119)for(Q(u,t);atoi(S[s-1]);)E(u)G(34)p=P(p);}}}}

```

Try it online!

A less golfed version of my original (unlike the golfed version this one prints the stack when it ends if it is not empty and takes a -e parameter so you can specify the script on the command line instead of reading from a file):

```
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define FIRST_REST(x) memcpy(first, b, p - b); first[p - b - x] = '\0'; strcpy(rest, p);
#define COPY(dest,src) strcpy(stack[size + dest], stack[size + src]);
char stack[9999][9999]; int size = 0;
int token(char *b, char *first, char *rest)
{
    while (*b == 32) b++;
    char *p; int x = strtol(b, &p, 0);
    if (p > b) { FIRST_REST(0) return 1; }
    if (*b == '(') { int c = 1; for (p = ++b; c; ++p) c += (*p == '(') - (*p == ')'); FIRST_REST(1) return -1; }
    p++; FIRST_REST(0) if (!*b) *rest = '\0'; return 0;
}
char *push(char *pointer)
{
    if (*pointer == '\"') return pointer+1;
    char *result = push(pointer+1);
    sprintf(stack[size++], "%d", *pointer);
    return result;
}
void eval(char *x)
{
    char program[9999], first[9999], rest[9999], tos[9999], tmp1[9999], tmp2[9999];
    char *pointer;
    for (strcpy(program, x); *program; strcpy(program, pointer))
    {
        *stack[size] = '\0';
        strcpy(tos, stack[size-1]);
        if (token(program, first, rest))
        {
            pointer = rest;
            strcpy(stack[size++], first);
        }
        else
        {
            pointer = rest;
            if (*first == '@'){
                COPY(0, -1) COPY(-1, -2) COPY(-2, -3) COPY(-3, 0) }
            if (*first == '#')
                strcpy(stack[size++], tos);
            if (*first == '$'){
                COPY(0, -2) COPY(-2, -1) COPY(-1, 0) }
            if (*first == '%')
                size--;
            if (*first == '/'){
                size--; token(tos, tmp1, tmp2); if (*tmp2) strcpy(stack[size++], tmp2); strcpy(stack[size++], tmp1); }
            if (*first == '.'){
                size--; strcat(stack[size - 1], " "); strcat(stack[size - 1], tos); }
            if (*first == '+'){
                size--; sprintf(stack[size++], "%d", atoi(tos) + 1); }
            if (*first == '-'){
                size--; sprintf(stack[size++], "%d", atoi(tos) - 1); }
            if (*first == '<')
                sprintf(stack[size++], "%d", getchar());
            if (*first == '>'){
                size--; if (token(tos, tmp1, tmp2) == 1) putchar(atoi(tmp1)); }
            if (*first == 'c'){
                size--; if (token(tos, tmp1, tmp2) == 1) printf("%s", tmp1); }
            if (*first == 'w'){
                size--; strcpy(tmp1, tos); while (atoi(stack[size - 1])) eval(tmp1); }
            if (*first == '\"')
                pointer=push(pointer);
        }
    }
}
int main(int argc, char **argv)
{
    char program[9999] = "";
    int i = 0, comment = 0, quote = 0, space = 0;
    if (!strcmp(argv[1], "-e"))
        strcpy(program, argv[2]);
    else
    {
        FILE* f = fopen(argv[1], "r");
        for (;;) {
            char ch = fgetc(f);
            if (ch < 0) break;
            if (!quote) {
                if (ch == '\n') comment = 0;
                if (ch == ';') comment = 1;
                if (comment) continue;
                if (ch <= ' ') { ch = ' '; if (space++) continue; }
                else space = 0;
            }
            if (ch == '\"') quote = 1 - quote;
            program[i++] = ch;
        }
        fclose(f);
    }
    eval(program);
    for (int i = 0; i < size; i++) printf("%03d: (%s)\r\n",size-i,stack[i]);
    return 0;
}

```

# Answer
> 1 votes
# Scala, ~~1014~~ 1009 bytes

```
import util._
val n="([+-]?\\d+)(.*)".r
def c(z:String):(String,String)=z.trim match{
case s"($x"=>var i,b=0
while(-1<b&i<x.size){if(x(i)=='(')b+=1
if(x(i)==')')b-=1
i+=1}
(x.slice(0,i-1),x drop i)case n(x,t)=>(x,t)case x=>x.slice(0,1)->x.tail}
def f(z:String,r:List[String]=Nil):List[String]="\"([^\"]*)\"".r.replaceAllIn(z.trim,m=>m.group(1).reverse.flatMap(" " + _.toInt + " "))match{case ""=>r
case s"($x"=>val(a,b)=c(z.trim);f(b,a::r)case n(x,t)=>f(t,""+x.toInt::r)case s"@$t"=>val a::b::c::d=r
f(t,b::c::a::d)case s"#$t"=>f(t,r.head::r)case s"$$$t"=>val a::b::c=r
f(t,b::a::c)case s"%$t"=>f(t,r.tail)case s"/$t"=>val(a,b)=c(r.head.trim)
f(t,a::b.trim::r.tail)case s".$t"=>val a::b::c=r
f(t,s"$a$b"::c)case s"<$t"=>f(t,Try{""+io.StdIn.readChar}.getOrElse("-1")::r)case s">$t"=>Try{print(r.head.toInt.toChar)}
f(t,r.tail)case s"c$t"=>Try{print(r.head.toInt)}
f(t,r.tail)case s"w$t"=>var h::u=r
while(u.head!="0")u=f(h,u)
f(t,u)case x=>f(x.tail,""+(Try{r.head.toInt+s"${x(0)}1".toInt}getOrElse-1)::r.tail)}

```

Try it online

Wow, this got long. I'll add an explanation later.

Ungolfed

---
Tags: code-golf, interpreter, stack
---


title: Arranging Fenceposts

text:
# Question
Title: Arranging Fenceposts
If you want to build a fence and have different length boards available, there are many different ways to set up your posts. So, given a minimum and maximum board length, a number of boards, and the total length, count how many ways you can arrange them.

**Input**

Input is four positive integers:

* **min:** The smallest board usable. Will be `>0`.
* **max:** The largest board available. Will be `>min`.
* **count:** Number of boards to use. Will be `>0`.
* **length:** Total length of the fence. For a valid fence, this should be `>=min*count` and `<=max*count`

Individual boards can be any *integer* length between `min` and `max` (inclusive).

**Output**

Output a single number representing the number of ways you can arrange the fence.

**Examples**

For input (in order listed above) `2 3 4 10`, you can arrange the boards six ways:

```
2233
2323
2332
3223
3232
3322

```

So the output is `6`. If your input was `1 3 4 6`, the output is `10`, since there are ten ways to do it:

```
1113   1212
1131   1221
1311   2112
3111   2121
1122   2211

Input          Output
5 10 6 45      4332
1 100 6 302    1204782674
27 53 8 315    4899086560
1 10 11 70     2570003777
1 6 15 47      20114111295
4 8 150 600    1              // all boards length 4
1 10 100 80    0              // invalid, you can't put 100 boards in 80 length

```

Of course, there's a naive method to do this:

```
long f(int min, int max, int count, int length){
    if(count==1)
        return 1;
    long num = 0;
    for(int i=min;i<=max;i++){
        int goal = length - i;
        if(goal <= max*(count-1) && goal >= min*(count-1)){
            num += f(min,max,count-1,goal);
        }
    }
    return num;
}

```

**Rules**

The algorithm given above works fine for small inputs, but it can easily overflow the `long` with larger inputs. Even with arbitrary-length numbers, it's incredibly inefficient. I believe it's `O((max-min+1)^count)`.

To be considered valid for this challenge, you should be able to compute input `1 10 100 700` in under one hour on my i7. Given a more efficient algorithm than the one above, this should not be a problem. I will test any entries I believe may come close to the limit. If your algorithm takes more than a few minutes to run, you should use a freely available language (on linux) to facilitate testing.

Code may take the form of a complete program or function, with input/output as any of the standard methods. Shortest code in bytes wins.

# Answer
> 4 votes
# Ruby: ~~106~~ ~~98~~ 93 bytes

*Update:* Changed cache key type from strings to arrays. (**-5**)

*Update:* Storing the initial condition in the cache payed out quite well. (**-8**) However, it increases the runtime for the test case to roughly 2 seconds.

I simply use memoization. I guess it can be further golfed as my Ruby skills are far from perfect.

```
@m={[0,0]=>1}
def f(l,u,c,s)
  @m[[c,s]]||=s<0?0:(l..u).map{|x|f(l,u,c-1,s-x)}.reduce(:+)
end

```

Note that it runs for only one test case at a time, since I don't cache the min and max values (`l` and `u`, respectively). Here is my output for `1 10 100 700`:

```
121130639107583774681451741625922964085713989291260198434849317132762403014516376282321342995

real    0m0.316s
user    0m0.312s
sys     0m0.004s

```

# Answer
> 2 votes
# APL (Dyalog Unicode), 55 bytes

```
⎕CY'dfns'
{0::0⋄⍺⊃⍵{+big⌿↑(⍳1+¯1⊥⍺)⌽¨⊂0,⍣(⊢/⍺)⊢⍵}⍣⍺⍺⊢1}

```

Try it online! (without big, so fast but inaccurate)

The time complexity of the algorithm is \\$O(m(m-n)c^2)\\$, where \\$m\\$ and \\$n\\$ are max and min, and \\$c\\$ is the count, ignoring the cost of bigint addition (which is not a language built-in, and therefore horribly inefficient). It is nowhere close to the fastest, but it's still much faster than brute-force, as it returns the correct result for `1 10 100 700` in 3 minutes on my PC.

To use, assign the inline operator to `f` and call it in the form of `length (count f) min max`.

```
⎕CY'dfns'  ⍝ Load dfns library, so we can use `+big`

{0::0⋄...}  ⍝ If any error occurs, return 0
⍺⊃⍵{...}⍣⍺⍺⊢1  ⍝ Build the vector of all possible combinations by
               ⍝ taking the polynomial represented by ⍵ raised to the power of ⍺⍺,
               ⍝ then fetch the ⍺-th coefficient (might error if ⍺ is out of range)
0,⍣(⊢/⍺)⊢⍵    ⍝ Prepend "max" copies of 0s to the current polynomial
(⍳1+¯1⊥⍺)⌽¨⊂  ⍝ Generate the list of ^ rotated 0..(max-min) times
+big⌿↑        ⍝ Promote to matrix and sum the numbers vertically

```

---
Tags: code-golf, combinatorics
---


title: De-Snakify a String

text:
# Question
Title: De-Snakify a String
A regular string looks like this:

```
Hello,IAmAStringSnake!

```

And a string snake looks something like this:

```
Hel
  l      rin
  o,IAmASt g
           S
       !ekan

```

## Your Task

String snakes are dangerous, so you must make a program that takes a string snake as input and outputs it as a regular string.

## Specifications

* Input can be a multiline string or an array of strings.
* Each line of the input will be padded with spaces to form a rectangular grid.
* Characters in the snake can only connect to adjacent characters above, below, left or right of them (just like in the game Snake). They cannot go diagonal.
* The snake characters will never be adjacent to another part of the snake, only the connected characters.
* The first character of the string is the end character with the shortest Manhattan distance from the top-left corner of the input grid (i.e. the minimum number of moves it would take for a snake to go directly from the end character to the top-left corner). Both ends will never have the same distance.
* The string can contain any ASCII character between code points 33 and 126 inclusive (no spaces or newlines).
* The string will be between 2 and 100 characters long.
* Shortest code in bytes wins.

## Test Cases

*(Input grid, followed by the output string)*

```
Hel
  l      rin
  o,IAmASt g
           S
       !ekan

Hello,IAmAStringSnake!

----------

Python

Python

----------

P  ngPu  Code
r  i  z  d  G
o  m  z  n  o
gram  lesA  lf

ProgrammingPuzzlesAndCodeGolf

----------

   ~ zyx tsr XWVUTSR
   }|{ wvu q Y     Q
!          p Z `ab P
"#$ 6789:; o [ _ c O
  % 5    < n \]^ d N
('& 432  = m     e M
)     1  > lkjihgf L
*+,-./0  ?         K
         @ABCDEFGHIJ

!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

----------

  tSyrep
  r    p
  in Sli
   g    Sile
   Snakes  n
Ser      ylt
a eh   ilS
fe w   t
   emo h
     Sre

SlipperyStringSnakesSilentlySlitherSomewhereSafe

```

# Answer
# APL, 55 bytes

```
{⍵[1↓(⊂0 0){1<⍴⍵:⍺,∆[⊃⍋+/¨|⍺-∆]∇∆←⍵~⍺⋄⍺}(,⍵≠' ')/,⍳⍴⍵]}

```

This function takes a character matrix with the string snake in it.

Example:

```
      s1 s2 s3
┌────────────┬──────────────┬────────────────────┐
│Hel         │P  ngPu  Code │   ~ zyx tsr XWVUTSR│
│  l      rin│r  i  z  d  G │   }|{ wvu q Y     Q│
│  o,IAmAst g│o  m  z  n  o │!          p Z `ab P│
│           S│gram  lesA  lf│"#$ 6789;: o [ _ c O│
│       !ekan│              │  % 5    < n \]^ d N│
│            │              │('& 432  = m     e M│
│            │              │)     1  > lkjighf L│
│            │              │*+,-./0  ?         K│
│            │              │         @ABCDEFGHIJ│
└────────────┴──────────────┴────────────────────┘
      ↑ {⍵[1↓(⊂0 0){1<⍴⍵:⍺,∆[⊃⍋+/¨|⍺-∆]∇∆←⍵~⍺⋄⍺}(,⍵≠' ')/,⍳⍴⍵]} ¨ s1 s2 s3
Hello,IAmAstringSnake!
ProgrammingPuzzlesAndCodeGolf
!"#$%&'()*+,-./0123456789;:<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefhgijklmnopqrstuvwxyz{|}~

```

Explanation:

* `(,⍵≠' ')/,⍳⍴⍵`: get the coordinates of all non-spaces
* `(⊂0 0)`: begin at (0,0) (which is an invalid coordinate)
* `{`...`}`: follow the snake, given position and snake:
    + `1<⍴⍵:`: if there is more than 1 element left:
        - `∆←⍵~⍺`: remove the current position from the snake and store it in .
        - `+/¨|⍺-∆`: find the distance between the current position and each point in the rest of the snake
        - `∆[⊃⍋...`\]\`: get the closest point on the snake
        - : run the function again, with the closest point as the new current point and the shortened snake as the new snake.
        - `⍺,`: add the current position to the result of that
    + `⋄⍺`: otherwise, just return the current position
* `1↓`: drop the first item from the result (which is the (0,0) position)
* `⍵[`...`]`: get those elements from ⍵, in that order
> 12 votes

# Answer
# JavaScript (ES6) + SnakeEx, 176 bytes

```
a=b=>snakeEx.run("s{A}:<+>([^ ]<P>)+",b).reduce((c,d)=>(e=c.marks.length-d.marks.length)>0?c:e?d:c.x+c.y>d.x+d.y?d:c).marks.reduce((c,d,e,f)=>e%2?c+b.split`\n`[d][f[e-1]]:c,"")

```

Remember SnakeEx? Good, because neither do I! Golfing suggestions welcome.
> 25 votes

# Answer
# MATL, 80 bytes

*Thanks to @LevelRiverSt for a correction*

```
32>2#fJ*+X:4Mt1Y6Z+l=*2#fJ*+ttXjwYj+K#X<)wt!"tbb6#Yk2#)yw]xxvtXjwYjqGZy1)*+Gw)1e

```

Input is as a 2D array of char, with rows separated by `;`. The test cases in this format are

```
['Hel         ';'  l      rin';'  o,IAmASt g';'           S';'       !ekan']
['Python']
['P  ngPu  Code ';'r  i  z  d  G ';'o  m  z  n  o ';'gram  lesA  lf']
['   ~ zyx tsr XWVUTSR';'   }|{ wvu q Y     Q';'!          p Z `ab P';'"#$ 6789:; o [ _ c O';'  % 5    < n \]^ d N';'(''& 432  = m     e M';')     1  > lkjihgf L';'*+,-./0  ?         K';'         @ABCDEFGHIJ']
['  tSyrep    ';'  r    p    ';'  in Sli    ';'   g    Sile';'   Snakes  n';'Ser      ylt';'a eh   ilS  ';'fe w   t    ';'   emo h    ';'     Sre    ']

```

**Try it online!**

### Explanation

The coordinates of each nonspace character is represented by a complex number. For each current character, the next is obtained as that which is closest (minimum absolute difference of their complex coordinates).

To determine the initial char, the two endpoints need to be found. This is done as follows. An endpoint is a nonspace char that has exactly one nonspace neighbour. The number of neighbours is obtained by 2D convolution with a suitable mask. The initial point is the endpoint whose complex coordinate has the least sum of real and imaginary parts; i.e. is closest in Manhattan distance to the complex number 0, or equivalently to 1+1j, which is the complex coordinate of the upper left corner.

```
32>      % Take input as 2D char array. Compute 2D array with true for nonspace,
         % false for space
2#f      % Arrays of row and column indices of nonspaces
J*+      % Convert to complex array. Real part is row, imaginary part is column
X:       % Convert to column array
4Mt      % Push arrays of zeros and ones again. Duplicate
1Y6      % Push array [0 1 0; 1 0 1; 0 1 0]. Used as convolution mask to detect
         % neighbours that are nonspace
Z+       % 2D convolution with same size as the input
1=       % True for chars that have only one neighbour (endpoints)
*        % Multiply (logical and): we want nonspaces that are endpoints
2#fJ*+   % Find complex coordinates (as before)
ttXjwYj  % Duplicate. Take real and imaginary parts
+        % Add: gives Manhattan distance to (0,0)
K#X<     % Arg min. Entry with minimum absolute value has least Manhattan
         % distance to (0,0), and thus to (1,1) (top left corner)
)        % Apply as an index, to yield complex coordinate of initial endpoint
wt!      % Swap, duplicate, transpose.
         % The stack contains, bottom to top: complex coordinates of initial
         % endpoint, column array with all complex coordinates, row array of all
         % coordinates. The latter is used (and consumed) by the next "for"
         % statement to generate that many iterations
"        % For loop. Number of iterations is number of nonspaces
  tbb    %   Duplicate, bubble up twice (rearrange is stack)
  6#Yk   %   Find which of the remaining points is closest to current point. This
         %   is the next char in the string
  2#)    %   Remove the point with that index from the array of complex
         %   coordinates. Push that point and the rest of the array
  yw     %   Duplicate extracted point, swap
]        % End for
xx       % Delete top two elements of the stack
v        % Concatenate all stack contents into a column array. This array
         % contains the complex coordinates of chars sorted to form the string
tXjwYj   % Extract real part and imaginary part
GZy1)    % Number of rows of input. Needed to convert to linear index
*+       % Convert rows and columns to linear index
Gw       % Push input below that
)        % Index to get the original chars with the computed order
1e       % Force the result to be a row array (string). Implicitly display

```
> 21 votes

# Answer
# C  ~~198~~   ~~190~~   ~~179~~   ~~180~~  181 bytes

Edit: Used the tip by user81655 and removed the parenthesis in the ternary operator, thanks! I also changed the cumbersome (S&1) test for evenness for the more appropriate (and shorter!) S%2.

Edit2: Using the \*a addressing style heavily, made me blind to the obvious optimizations in the definition of S, i.e., replacing \*(a+m) by a\[m\] etc. I then replaced S itself by T, which essentially does half of what S does. The code also now takes advantage of the return value of putchar.

Edit3: Fixed bug that has been around from the beginning, the Manhattan-search stopping criteria a \< b+m is correct only if a has already been decremented. This adds 2 bytes, but one is regained by making the definition of m global.

Edit4: My golfing has passed the minimum and is going the wrong way now. Another bug fix related to the Manhattan-search. I originally had in-bound checks in place and without those the search continues for large input arrays (somewhere round 50x50) beyond the array b. Hence that array has to be expanded to at least twice the previous size, which adds one more byte.

```
#define T(x)+x*((a[x]>32)-(a[-x]>32))
m=103;main(){char b[m<<8],*e=b,*a=e+m;while(gets(e+=m));for(e=a;(T(1)T(m))%2**a<33;a=a<b+m?e+=m:a)a-=m-1;for(;*a;a+=T(1)T(m))*a-=putchar(*a);}

```

Ungolfed and explained:

```
/* T(1)T(m) (formerly S) is used in two ways (we implicitly assume that each cell has
   one or two neighbors to begin with):
   1. (in the first for-loop) T(1)T(m) returns an odd (even) number if cell a has one (two)
      neighbors with ASCII value > 32. For this to work m must be odd.
   2. (in the second for-loop) at this stage each cell a in the array at which T(1)T(m) is
      evaluated has at most one neighboring cell with ASCII value > 32. T(1)T(m) returns the
      offset in memory to reach this cell from a or 0 if there is no such cell.
      Putting the + in front of x here saves one byte (one + here replaces two
      + in the main part)

#define T(x)+x*((a[x]>32)-(a[-x]>32))

  /* A snake of length 100 together with the newlines (replaced by 0:s in memory) fits
     an array of size 100x101, but to avoid having to perform out-of-bounds checks we
     want to have an empty line above and the array width amount of empty lines below
     the input array. Hence an array of size 202x101 would suffice. However, we save
     a (few) bytes if we express the array size as m<<8, and since m must be odd
     (see 1. above), we put m = 103. Here b and e point to the beginning of the (now)
     256x103 array and a points to the beginning of the input array therein */

m=103;
main()
{

  char b[m<<8],*e=b,*a=e+m;

  /* This reads the input array into the 256x103 array */

  while(gets(e+=m));

  /* Here we traverse the cells in the input array one
     constant-Manhattan-distance-from-top-left diagonal at a time starting at the top-left
     singleton. Each diagonal is traversed from bottom-left to top-right since the starting point
     (memory location e) is easily obtained by moving one line downwards for each diagonal
     (+m) and the stopping point is found by comparing the present location a to the input array
     starting position (b+m). The traversal is continued as long as the cell has either
     an ASCII value < 33 or it has two neighbors with ASCII value > 32 each (T(1)T(m)
     is even so that (T(1)T(m))%2=0).
     Note that the pointer e will for wide input arrays stray way outside (below) the
     input array itself, so that for a 100 cell wide (the maximum width) input array
     with only two occupied cells in the bottom-right corner, the starting cell
     will be discovered 98 lines below the bottom line of the input array.
     Note also that in these cases the traversal of the diagonals will pass through the
     right-hand side of the 103-wide array and enter on the left-hand side. This, however,
     is not a problem since the cells that the traversal then passes have a lower
     Manhattan distance and have thereby already been analyzed and found not to contain
     the starting cell. */

  for(e=a;(T(1)T(m))%2**a<33;a=a<b+m?e+=m:a)a-=m-1;

  /* We traverse the snake and output each character as we find them, beginning at the
     previously found starting point. Here we utilize the function T(1)T(m), which
     gives the offset to the next cell in the snake (or 0 if none), provided that
     the current cell has at most one neighbor. This is automatically true for the
     first cell in the snake, and to ensure it for the rest of the cells we put the
     ASCII value of the current cell to 0 (*a-=putchar(*a)), where we use the fact
     that putchar returns its argument. The value 0 is convenient, since it makes the
     stopping condition (offset = 0, we stay in place) easy to test for (*a == 0). */

  for(;*a;a+=T(1)T(m))
    *a-=putchar(*a);
}

```
> 16 votes

# Answer
# C, 272 bytes

```
#define E j+(p/2*i+1)*(p%2*2-1)
#define X(Y) a[Y]&&a[Y]-32
char A[999],*a=A+99;j,p,t;i;main(c){for(;gets(++j+a);j+=i)i=strlen(a+j);for(c=j;j--;){for(t=p=4;p--;)t-=X(E);t==3&&X(j)?c=c%i+c/i<j%i+j/i?c:j:0;}for(j=c;c;){putchar(a[j]),a[j]=0;for(c=0,p=4;!c*p--;)X(E)?c=j=E:0;}}

```

Look at @Zunga's source. Now look at mine. Want to know how I got the extra 91-bytes?
Ungolfed:

```
#define E j+(p/2*i+1)*(p%2*2-1)
#define X(Y) a[Y]&&a[Y]-32  //can be more concise, see @Zunga's
  //and then doesn't need the define
char A[999],*a=A+99;j,p,t;i;
main(c){for(;gets(++j+a);j+=i)
i=strlen(a+j); //we don't need to know the length of a line
  //in @Zunga's solution, lines are spaced a constant distance apart
for(c=j;j--;){
for(t=p=4;p--;)t-=X(E);  //a ton of bytes can be saved with determining
  //the neighbors, see @Zunga's source
t==3&&X(j)?
c=c%i+c/i<j%i+j/i?c:j:0;}  //we search for ends of the snake,
  //and compute the Manhattan distance
for(j=c;c;){putchar(a[j]),a[j]=0;
for(c=0,p=4;!c*p--;)  //determining the neighbors again
X(E)?c=j=E:0;}}

```
> 9 votes

# Answer
## Python (2 and 3), 640 624 604 583 575 561 546 538 bytes

I'm still a golfing n00b so this is a bit large.

Edit: Thanks to @porglezomp for the suggestions! I didn't remove all the 'and' operators as that would break Python 3.

Edit2: Thanks to @Aleksi Torhamo for the comment about isspace(). The resulting reduction compensates for the bugfix I put in. Also thanks to anonymous for the syntax highlighting!

Edit3: Thanks to @mbomb007 for a few additional bytes.

```
import sys;s=sys.stdin.read().split('\n');m={};q=[];o=len;j=o(s);r=range;g='!'
for y in r(j):
 v=s[y];f=o(v);d=y+1
 for x in r(f):
  n=[];a=n.append;U=s[y-1]
  if v[x]>=g:j>=y>0==(U[x]<g)<=x<o(U)and a((x,y-1));j>y>=0==(v[x-1]<g)<x<=f and a((x-1,y));j>y>-1<x+1<f>(v[x+1]<g)<1and a((x+1,y));j>d>-1<x<o(s[d])>(s[d][x]<g)<1and a((x,d));m[x,y]=[v[x],n];o(n)-1or q.append((x,y))
t=min(q,key=sum);w=sys.stdout.write;w(m[t][0]);c=m[t][1][0]
while o(m[c][1])>1:
 b=m[c][1];w(m[c][0])
 for k in r(o(b)):
  if b[k]!=t:t=c;c=b[k];break
print(m[c][0])

```

And here's my pre-golf version

```
import sys

lines = sys.stdin.read().split('\n')
startend = []
mydict = {}
for y in range( 0, len(lines)):
  for x in range( 0, len(lines[y])):
    if not lines[y][x].isspace():
      neighbors = []
      if x>=0 and x<len(lines[y-1]) and y-1>=0 and y-1<len(lines):
        if not lines[y-1][x].isspace():
          neighbors.append( (x,y-1) )
      if x-1>=0 and x-1<len(lines[y]) and y>=0 and y<len(lines):
        if not lines[y][x-1].isspace():
          neighbors.append( (x-1,y) )
      if x+1>=0 and x+1<len(lines[y]) and y>=0 and y<len(lines):
        if not lines[y][x+1].isspace():
          neighbors.append( (x+1,y) )
      if x>=0 and x<len(lines[y+1]) and y+1>=0 and y+1<len(lines):
        if not lines[y+1][x].isspace():
          neighbors.append( (x,y+1) )
      mydict[(x,y)] = [ lines[y][x], neighbors ]

      if len( neighbors ) == 1:
        startend.append( (x,y) )

startend.sort( key=lambda x : x[0]*x[0] + x[1]*x[1] )

last = startend[0]
sys.stdout.write( mydict[ last ][0] )
current = mydict[last][1][0]
while len( mydict[current][1] ) > 1:
  sys.stdout.write( mydict[current][0] )
  for k in range( 0, len( mydict[current][1] ) ):
    if mydict[current][1][k] != last:
      last = current
      current = mydict[current][1][k]
      break

print(mydict[current][0])

```
> 5 votes

# Answer
# JavaScript (ES6), 195

See explanation inside the test snippet

```
s=>[...s].map((c,i)=>{if(c>' '&([n=-1,1,o=-~s.search('\n'),-o].map(d=>n+=s[i+d]>' '&&!!(e=d)),n<1)&m>(w=i/o+i%o|0))for(m=w,r=c,p=i+e;r+=s[i=p],[e,o/e,-o/e].some(d=>s[p=i+(e=d)]>' '););},m=1/0)&&r

```

**Test**

```
f=s=>[...s].map((c,i)=>{if(c>' '&([n=-1,1,o=-~s.search('\n'),-o].map(d=>n+=s[i+d]>' '&&!!(e=d)),n<1)&m>(w=i/o+i%o|0))for(m=w,r=c,p=i+e;r+=s[i=p],[e,o/e,-o/e].some(d=>s[p=i+(e=d)]>' '););},m=1/0)&&r

// Less golfed

u=s=>(
  o = -~s.search('\n'), // offset between lines
  m = 1/0, // current min manhattan distance, init at infinity
  // scan input looking for the 2 ends of the string
  [...s].map((c,i)=>{ // for each char c at position i
     if(c > ' ' // check if part of the string
        & ( [-1,1,o,-o] // scan in 4 directions and count neighbors
             .map(d=> n+=s[i+d]>' '&&!!(e=d), n=0), // remember direction in e
          n < 2) // if at end of string will have exactly 1 neighbor
        & (w = i/o + i%o |0) < m) // manhattan distance in w, must be less than current min
       // found one of the ends, follow the path and build the string in r
       for(m = w, r = c, p = i+e;
           r += s[i=p],
           [e,o/e,-o/e] // check 3 directions, avoiding to go back
           .some(d=>s[p=i+(e=d)]>' '); // save candidate position and direction in p and e
          ); // empty for body, all the work is inside the condition
  }),
  r
)

console.log=x=>O.textContent+=x+'\n'

;[`Hel
  l      rin
  o,IAmASt g
           S
       !ekan`,
 `   ~ zyx tsr XWVUTSR
   }|{ wvu q Y     Q
!          p Z \`ab P
"#$ 6789:; o [ _ c O
  % 5    < n \\]^ d N
('& 432  = m     e M
)     1  > lkjihgf L
*+,-./0  ?         K
         @ABCDEFGHIJ`].forEach(t=>{
  console.log(t+'\n\n'+f(t)+'\n')
  })
```

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

# Answer
# APL (Dyalog Unicode), 59 bytes

```
{⍵[i][{⍵∪⍸∨⌿g[⍵;]}⍣≡,j⊃⍨⊃⍋+/↑i[j←⍸≠/g←1=+/|↑∘.-⍨i←⍸' '≠⍵]]}

```

Try it online!
> 4 votes

# Answer
## Lua, ~~562~~ ~~535~~ ~~529~~ ~~513~~ ~~507~~ ~~504~~ ~~466~~ 458 Bytes

By far my most massive golf at the moment, ~~I think I can still cut off 100 bytes, which I'll work toward, but posting it as an answer as it already took some time :).~~ I was right, I've cutted down more than 100 bytes! I don't think there's lot of room for improvement.

this function have to be called with a 2D array containing one character per cell.

**Saved 40 bytes while working with @KennyLau, thanks to him!**

**Woohoo! Under 500!**

```
function f(m)t=2u=1i=1j=1s=" "::a::if s~=m[i][j]and(i<#m and m[i+1][j]~=s)~=(j<#m[i]and m[i][j+1]~=s)~=(i>1 and m[i-1][j]~=s)~=(j>1 and m[i][j-1]~=s)then goto b end
i,t=i%t+1,#m>t and t==i and t+1or t j=j>1 and j-1or u u=u<#m[1]and j==1 and u+1or u goto a::b::io.write(m[i][j])m[i][j]=s
i,j=i<#m and s~=m[i+1][j]and i+1or i>1 and s~=m[i-1][j]and i-1or i,j<#m[i]and s~=m[i][j+1]and j+1or j>1 and s~=m[i][j-1]and j-1or j
if s==m[i][j]then return end goto b end

```

## Ungolfed

~~Explanations will come once I'm done golfing this, for the moment, i'll lend you a readable version of this source code :D~~ Here comes the explanations!

**Edit: not updated with the latest modification, still golfing before updating. Same goes for the explanations**

```
function f(m)                    -- declare the function f which takes a matrix of characters
  t=2                            -- initialise the treshold for i
                                 -- when looking for the first end of the snake
  u=1                            -- same thing for j
  i,j=1,1                        -- initialise i and j,our position in the matrix
  s=" "                          -- shorthand for a space
  ::a::                          -- label a, start of an infinite loop
    if m[i][j]~=s                -- check if the current character isn't a space
      and(i<#m                   -- and weither it is surrounded by exactly
          and m[i+1][j]~=s)      -- 3 spaces or not
      ~=(j<#m[i]
          and m[i][j+1]~=s)      -- (more explanations below)
      ~=(i>1
          and m[i-1][j]~=s)
      ~=(j>1
          and m[i][j-1]~=s)
      then goto b end            -- if it is, go to the label b, we found the head
    i,t=                         -- at the same time
      i%t+1,                     -- increment i
      #m>t and t==i and t+1or t  -- if we checked all chars in the current range, t++
    j=j>1 and j-1or u            -- decrement j
    u=u>#m[1]and j==1 and u+1or u-- if we checked all chars in the current range, u++
  goto a                         -- loop back to label a

  ::b::                          -- label b, start of infinite loop
  io.write(m[i][j])                    -- output the current char
    m[i][j]=s                    -- and set it to a space
    i,j=i<#m                     -- change i and j to find the next character in the snake
          and m[i+1][j]~=s       -- this nested ternary is also explained below
            and i+1              -- as it takes a lot of lines in comment ^^'
          or i>1
            and m[i-1][j]~=s
            and i-1
          or i,
       j<#m[i]
         and m[i][j+1]~=s
           and j+1
         or j>1
           and m[i][j-1]~=s
           and j-1
         or j
    if m[i][j]==s                -- if the new char is a space
    then                         -- it means we finished
      return                  -- exit properly to avoid infinite
    end                          -- printing of spaces
  goto b                         -- else, loop back to label b
end

```

So here comes some detailed explanations about how this program works.

First of all, let's consider the loop labeled `a`, it allows us to find the closest end to the top-left corner. It will loop forever if there's no end, but that's not a problem :D.

On a 4x4 grid, it here are the snake distances(left), and the order they are looked at (right)

```
1  2  3  4    |     1  2  4  7
2  3  4  5    |     3  5  8 11
3  4  5  6    |     6  9 12 14
4  5  6  7    |    10 13 15 16

```

For each of this character, to be the end, it have to check two conditions: \- Not being a space \- Being surrounded by exactly 3 spaces (or exactly 1 non-space)

These conditions are checked the following piece of code

```
r=m[i][j]~=s
    and(i<#m and m[i+1][j]~=s)
    ==not(j<#m[i] and m[i][j+1]~=s)
    ==not(i-1>0 and m[i-1][j]~=s)
    ==not(j-1>0 and m[i][j-1]~=s)
    and m[i][j]
    or r
  -- special note: "==not" is used as an equivalent to xor
  -- as Lua doesn't know what is a xor...

```

Checking if the char isn't a space is achieved by the expression `m[i][j]~=s`.

Checking if w're surrounded by only 1 non-space is achived by xor-ing the above conditions for our surrounding, this could be written as

```
m[i+1][j]~=" " ⊕ m[i][j+1]~=" " ⊕ m[i-1][j]~=" " ⊕ m[i][j-1]~=" "

```

And finally, if all the above is evaluated to true, the ternary will return what's in the last `and` -\> `m[i][j]`. Else , we let `r` unset :)

Now that we have the head of the snake, let's get all the way to the other end! Iterating the snake is mainly achieved by the following nested ternaries:

```
i,j=i<#m and m[i+1][j]~=s and i+1or i-1>0 and m[i-1][j]~=s and i-1or i,
    j<#m[i]and m[i][j+1]~=s and j+1or j-1>0 and m[i][j-1]~=s and j-1or j

```

We re-set `i` and `j` at the same time to avoid needing dummies to store the old values They both have the exact same structure, and use simple conditions, so I'll present them in the form of nested `if`, it should allow you to read them more easily. :)

```
i=i<#m and m[i+1][j]~=s and i+1or i-1>0 and m[i-1][j]~=s and i-1or i

```

Can be translated to:

```
if(i<#m)
then
  if(m[i+1][j]~=" ")
  then
    i=i+1
  end
elseif(i-1>0)
then
  if(m[i-1][j]~=" ")
  then
    i=i-1
  end
end

```

### Test it!

Here's the code I use to run this, you can test it online by copy-pasting it.

```
function f(m)t=2u=1i=1j=1s=" "::a::if s~=m[i][j]and(i<#m and m[i+1][j]~=s)~=(j<#m[i]and m[i][j+1]~=s)~=(i>1 and m[i-1][j]~=s)~=(j>1 and m[i][j-1]~=s)then goto b end
i,t=i%t+1,#m>t and t==i and t+1or t j=j>1 and j-1or u u=u<#m[1]and j==1 and u+1or u goto a::b::io.write(m[i][j])m[i][j]=s
i,j=i<#m and s~=m[i+1][j]and i+1or i>1 and s~=m[i-1][j]and i-1or i,j<#m[i]and s~=m[i][j+1]and j+1or j>1 and s~=m[i][j-1]and j-1or j
if s==m[i][j]then return end goto b end

test1={}
s1={
"  tSyrep    ",
"  r    p    ",
"  in Sli    ",
"   g    Sile",
"   Snakes  n",
"Ser      ylt",
"a eh   ilS  ",
"fe w   t    ",
"   emo h    ",
"     Sre    ",
     }
for i=1,#s1
do
  test1[i]={}
  s1[i]:gsub(".",function(c)test1[i][#test1[i]+1]=c end)
end
f(test1)

```
> 3 votes

# Answer
## Lua, 267 bytes

Lua 5.3 is required.

```
e=" "w=#arg[1]+1i=1/0q=0s=table.concat(arg,e)s=e:rep(#s)..s
m,n=i,{}for p in s:gmatch"()%g"do u=-1
for _,d in ipairs{-1,1,-w,w}do u=u+(s:find("^%S",d+p)or 0)end
n[p]=u+1m=math.min(m,p*i^(u//#s)+(p%w*w+p)*#s)end
p=m%#s repeat q,p=p,n[p]-q io.write(s:sub(q,q))until p<1

```

Usage:

```
$ lua desnakify.lua \
>    "  tSyrep    " \
>    "  r    p    " \
>    "  in Sli    " \
>    "   g    Sile" \
>    "   Snakes  n" \
>    "Ser      ylt" \
>    "a eh   ilS  " \
>    "fe w   t    " \
>    "   emo h    " \
>    "     Sre    "
SlipperyStringSnakesSilentlySlitherSomewhereSafe

```
> 3 votes

# Answer
# Python 3, ~~245~~ ~~243~~ ~~241~~ 236 bytes

`s` is the input string, `n` is the output printed to stdout:

```
f=s.find
w,l=f('\n')+1,len(s)
t=1,w,-1,-w
y=z=f(s.strip()[0]);n=s[y];v={y}
for i in range(l*l):
 i%=l;c=s[i]
 if c>' 'and i not in v:
  if i-y in t:y=i;n=c+n;v|={i}
  elif i-z in t:z=i;n+=c;v|={i}
if y%w+y//w>z%w+z//w:n=n[::-1]
print(n)

```

**Edit:** Thanks to @Cees Timmerman for saving 5 bytes!
> 2 votes

# Answer
## Python, 537

My initial solution:

```
from itertools import chain, product, ifilter
from operator import add
moves = ((1,0),(0,1),(-1,0),(0,-1))
h = dict(ifilter(lambda (p,v):not v.isspace(),chain(*map(lambda (i,r):map(lambda (j,c):((i,j),c),enumerate(r)),enumerate(s)))))
n = defaultdict(list)
for m,p in product(moves, h):
    np = tuple(map(add,m,p))
    if np in h:
        n[p].append(np)
def pr(nx):
    return(lambda l:(h[l[0]], h.pop(l[0]))[0] + pr(l[0]) if l else '')([x for x in n[nx] if x in h])
(lambda y: h[y]+ pr(y))(next(x for x in n if len(n[x])==1))

```

Compacted a bit, but left it as a method:

```
from itertools import chain, product
from operator import add
def unsnake(s):
    (h,n) = (dict(filter(lambda (p,v):not v.isspace(),chain(*map(lambda (i,r):map(lambda (j,c):((i,j),c),enumerate(r)),enumerate(s))))),defaultdict(list))
    for m,p in product(((1,0),(0,1),(-1,0),(0,-1)), h):(lambda np: n[p].append(np) if np in h else 0)(tuple(map(add,m,p)))
    def pr(nx):return(lambda l:(h[l[0]], h.pop(l[0]))[0] + pr(l[0]) if l else '')([x for x in n[nx] if x in h])
    return(lambda y: h[y]+ pr(y))(next(x for x in n if len(n[x])==1))

```
> 1 votes

# Answer
# Python 2, 251 bytes

```
w=s.find('\n')+1;q=' ';p=q*w+'\n';s=list(p+s+p);d=-w,1,w,-1
def r(x):c=s[x];s[x]=q;v=[c+r(x+o)for o in d if s[x+o]>q];return v[0]if v else c
e=[x for x in range(len(s))if s[x]>q and sum([s[x+o]>q for o in d])<2]
print r(e[e[0]/w+e[0]%w>e[1]/w+e[1]%w])

```

Or, if you want leading newlines in your testcases, 257 bytes:

```
w=s.find('\n',1);q=' ';p=q*-~w+'\n';s=list(p+s[1:]+p);d=-w,1,w,-1
def r(x):c=s[x];s[x]=q;v=[c+r(x+o)for o in d if s[x+o]>q];return v[0]if v else c
e=[x for x in range(len(s))if s[x]>q and sum([s[x+o]>q for o in d])<2]
print r(e[e[0]/w+e[0]%w>e[1]/w+e[1]%w])

```

Passes all testcases.

```
s="""
  tSyrep
  r    p
  in Sli
   g    Sile
   Snakes  n
Ser      ylt
a eh   ilS
fe w   t
   emo h
     Sre
"""

```

Results in:

```
SlipperyStringSnakesSilentlySlitherSomewhereSafe

```
> 1 votes

# Answer
# Java 7, ~~927~~ ~~924~~ 923 bytes

```
import java.util.*;int l,k;char[][]z;Set p=new HashSet();String c(String[]a){int x=0,y=0,n,t,u,v,w=t=u=v=-1;l=a.length;k=a[0].length();z=new char[l][k];for(String s:a){for(char c:s.toCharArray())z[x][y++]=c;}x++;y=0;}for(x=0;x<l;x++)for(y=0;y<k;y++){n=0;if(z[x][y]>32){if(x<1|(x>0&&z[x-1][y]<33))n++;if(y<1|(y>0&&z[x][y-1]<33))n++;if(x>l-2|(x<l-1&&z[x+1][y]<33))n++;if(y>k-2|(y<k-1&&z[x][y+1]<33))n++;}if(n>2&t<0){t=x;u=y;}if(n>2&t>v){v=x;w=y;}}if(v+w>t+u){p(t,u);return n(""+z[t][u],t,u);}p(v,w);return n(""+z[v][w],v,w);}String n(String r,int x,int y){int a,b;if(x>0&&z[a=x-1][b=y]>32&q(a,b)){p(a,b);return n(r+z[a][b],a,b);}if(y>0&&z[a=x][b=y-1]>32&q(a,b)){p(a,b);return n(r+z[a][b],a,b);}if(x<l-1&&z[a=x+1][b=y]>32&q(a,b)){p(a,b);return n(r+z[a][b],a,b);}if(y<k-1&&z[a=x][b=y+1]>32&q(a,b)){p(a,b);return n(r+z[a][b],a,b);}return r;}boolean q(int x,int y){return!p.contains(x+","+y);}void p(int x,int y){p.add(x+","+y);}

```

Ok, that took a while.. In some programming languages it doesn't matter if your array x and y are outside the boundaries of a 2D-array, but with Java it'll throw `ArrayIndexOutOfBoundsExceptions`, so everything has to be checked..

I first determine the starting point, and then use a recursive method to build the string from there. In addition, I use a list to keep track of the coordinations I've already encountered, so it won't go into a loop back-forth-back-forth (resulting in a StackOverflowException).

This is probably the longest answer I've posted so far, but although some parts can be golfed, I don't think this challenge can be that much shorter in Java. Java just isn't suitable for following a path in a grid.. It was a fun challenge to figure out nonetheless. :)

**Ungolfed & test cases:**

Try it here.

```
import java.util.*;
class M{
  static int l,
             k;
  static char[][] z;
  static Set p = new HashSet();

  static String c(String[] a){
    int x=0,
        y=0,
        n,
        t,
        u,
        v,
        w = t = u = v = -1;
    l = a.length;
    k = a[0].length();
    z = new char[l][k];
    for(String s:a){
      for(char c:s.toCharArray()){
        z[x][y++] = c;
      }
      x++;
      y = 0;
    }
    for(x=0; x<l; x++){
      for(y=0; y<k; y++){
        n = 0;
        if(z[x][y] > 32){ // [x,y] is not a space
          if(x < 1 | (x > 0 && z[x-1][y] < 33)){
            n++;
          }
          if(y < 1 | (y > 0 && z[x][y-1] < 33)){
            n++;
          }
          if(x > l-2 | (x < l-1 && z[x+1][y] < 33)){
            n++;
          }
          if(y > k-2 | (y < k-1 && z[x][y+1] < 33)){
            n++;
          }
        }
        if(n > 2 & t < 0){
          t = x;
          u = y;
        }
        if(n > 2 & t > v){
          v = x;
          w = y;
        }
      }
    }
    if(v+w > t+u){
      p(t, u);
      return n(""+z[t][u], t, u);
    }
    p(v, w);
    return n(""+z[v][w], v, w);
  }

  static String n(String r, int x, int y){
    int a,b;
    if(x > 0 && z[a=x-1][b=y] > 32 & q(a,b)){
      p(a, b);
      return n(r+z[a][b], a, b);
    }
    if(y > 0 && z[a=x][b=y-1] > 32 & q(a,b)){
      p(a, b);
      return n(r+z[a][b], a, b);
    }
    if(x < l-1 && z[a=x+1][b=y] > 32 & q(a,b)){
      p(a, b);
      return n(r+z[a][b], a, b);
    }
    if(y < k-1 && z[a=x][b=y+1] > 32 & q(a, b)){
      p(a, b);
      return n(r+z[a][b], a, b);
    }
    return r;
  }

  static boolean q(int x, int y){
    return !p.contains(x+","+y);
  }

  static void p(int x, int y){
    p.add(x+","+y);
  }

  public static void main(String[] a){
    System.out.println(c(new String[]{ "Hel         ",
      "  l      rin",
      "  o,IAmASt g",
      "           S",
      "       !ekan" }));
    p = new HashSet();
    System.out.println(c(new String[]{ "Python" }));
    p = new HashSet();
    System.out.println(c(new String[]{ "P  ngPu  Code ",
      "r  i  z  d  G",
      "o  m  z  n  o",
      "gram  lesA  lf" }));
    p = new HashSet();
    System.out.println(c(new String[]{ "   ~ zyx tsr XWVUTSR",
      "   }|{ wvu q Y     Q",
      "!          p Z `ab P",
      "\"#$ 6789:; o [ _ c O",
      "  % 5    < n \\]^ d N",
      "('& 432  = m     e M",
      ")     1  > lkjihgf L",
      "*+,-./0  ?         K",
      "         @ABCDEFGHIJ" }));
    p = new HashSet();
    System.out.println(c(new String[]{ "  tSyrep    ",
      "  r    p   ",
      "  in Sli   ",
      "   g    Sile",
      "   Snakes  n",
      "Ser      ylt",
      "a eh   ilS ",
      "fe w   t   ",
      "   emo h   ",
      "     Sre    " }));
  }
}

```

**Output:**

```
Hello,IAmAStringSnake!
Python
ProgrammingPuzzlesAndCodeGolf
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
SlipperyStringSnakesSilentlySlitherSomewhereSafe

```
> 1 votes

# Answer
# C#, 310

(Edit: bug fix)

A function with a multiline string parameter, returning a string.

Including the requested `using` in the byte count.

This is a porting of my javascript answer.

```
using System.Linq;
string f(string s){int o=-~s.IndexOf('\n'),m=99;var r=new string(' ',o);(s=r+s+r).Select((c,i)=>{int n=2,e=0,p,w=i%o+i/o;if(c>' '&w<m&&new[]{-1,1,o,-o}.All(d=>(s[i+d]>' '?(e=d)*--n:n)>0))for(m=w,r=""+c+s[p=i+e];new[]{e,o/e,-o/e}.Any(d=>s[p+(e=d)]>' ');)r+=s[p+=e];return i;}).Max();return r;}

```

*Test* on ideone

*With spaces*

```
    string f(string s)
    {
        int o = -~s.IndexOf('\n');
        var r = new string(' ', o);
        var m = 99;
        (s = r + s + r).Select((c, i) =>
        {
            int n = 2, e = 0, p, w = i % o + i / o;
            if (c > ' ' & w < m & new[] { -1, 1, o, -o }.All(d => (s[i + d] > ' ' ? (e = d) * --n : n) > 0))
                for (m = w, r = "" + c + s[p = i + e];
                     new[] { e, o / e, -o / e }.Any(d => s[p + (e = d)] > ' ');
                     )
                   r += s[p += e];
            return i;
        }
        ).Max();
        return r;
    }

```
> 1 votes

# Answer
## PHP, ~~199~~ ~~184~~ 182 bytes

may still have a little golfing potential

```
for($w=strpos($i=$argv[1],"
");;)for($y=++$n;$y--;)if($i[$p=$y*$w+$n-1]>" ")break 2;for($p-=$d=$w++;$d&&print$i[$p+=$e=$d];)foreach([-$w,-1,1,$w,0]as$d)if($d+$e&&" "<$i[$d+$p])break;

```

takes input as multiline string from command line, expects linux style linebreaks.
Run `php -r '<code>' '<string>'`; escape linebreaks.

**breakdown**

```
for(
    // find width
    $w=strpos($i=$argv[1],"\n")
    ;
    // find first character: initialize $p(osition)
    ;
)
    for($y=++$n             // increase distance
        ;$y--;)             // loop $y from (old)$n to 0
        if(" "<$i[$p=$y*$w+$n   // if character at $y*($width+1)+$x(=$d-$y) is no space
            -1                  // (adjust for the premature increment)
        ])
            break 2;                    // break loops

for(
    $p-=            // b) reverse the increment that follows in the pre-condition
    $d=             // a) initialize $d to anything!=0 to enable the first iteration
    $w++;           // c) increase $w for easier directions
    $d              // loop while direction is not 0 (cursor has moved)
    &&
    print$i[$p+=$e=$d]              // remember direction, move cursor, print character
    ;
)
    foreach([-$w,-1,1,$w,0]as$d)// loop through directions
        if($d+$e                    // if not opposite previous direction
            &&" "<$i[$d+$p]         // and character in that direction is not space
        )break;                     // break this loop

```
> 1 votes

# Answer
# Japt `-P`, 106 bytes

```
K=U·ÌÊÄ ç iU ¬mx T=[-KJ1K]
ËÊ*Tm+E è@gX
[]V£YÃf@gXÃrQ@WpQ Tm+Q kW fZ Ì}V£[XYuK YzK]ÃkÈv ÉÃñx v rÈ+Y*K
W£gX

```

Try it online!

It's... um... an abomination.

### Unpacked & How it works

```
K=UqR gJ l +1 ç iU q mx
  UqR gJ l +1            Split the input by newline, take last item's length +1
K=                       Assign to K
              ç iU       Generate a string of K spaces, and append to U
                   q mx  Split into chars, and trim whitespaces on each item
                         Implicit assign to U

T=[-KJ1K]  Assign an array [-K, -1, 1, K] to T (this represents 4-way movement)
           I could use implicit assignment, but then 4-argument function below is broken

UmDEF{Dl *Tm+E èXYZ{UgX
UmDEF{                   Map over the list of one- or zero-length strings...
      Dl *                 If the length is zero, return zero
          Tm+E             Add the index to each element of T
               èXYZ{UgX    Count truthy elements at these indices
                         The result is an array of 0(space/newline), 1(start/end), or 2(body)
                         Implicit assign to V

[]  Implicit assign to W

VmXYZ{Y} fXYZ{UgX} rQXYZ{WpQ Tm+Q kW fZ gJ }
VmXYZ{Y}                                      Map V into indices
         fXYZ{UgX}                            Filter the indices by truthiness of U's element
                   rQXYZ{                     Reduce on the indices... (Q=last item, Z=array)
                         WpQ                    Push Q to W
                             Tm+Q               Take 4-way movements from Q
                                  kW fZ gJ }    Exclude visited ones, take last one in Z

VmXYZ{[XYuK YzK]} kXYZ{Xv -1} ñx v rXYZ{X+Y*K  Starting point of reduce
VmXYZ{[XYuK YzK]}                              Convert elements of V to [elem, col, row]
                  kXYZ{Xv -1}                  Take the ones where elem(popped)=1
                              ñx v             Sort by row+col and take first one
                                   rXYZ{X+Y*K  Convert [row,col] back to the index

WmXYZ{UgX  Map indices back to chars

-P  Join with empty string

```

One notable point is that I used the operator precedence between assignment and comma operators in JS, in order to pack some lines and keep the shortcut `@` (`XYZ{`) usable.
> 0 votes

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


title: Cartesian LCM of two arrays

text:
# Question
Title: Cartesian LCM of two arrays
Given two nonempty arrays of natural numbers \\$a\\$ and \\$b\\$, return the shortest nonempty array of pairs of natural numbers \\$q\\$ such that the sequence of first elements of \\$q\\$ consists of a whole number of repeated copies of \\$a\\$, and the sequence of second elements of \\$q\\$ consists of a whole number of repeated copies of \\$b\\$.

When \\$a\\$ and \\$b\\$ have the same length, this acts like a zip, but when the lengths of \\$a\\$ and \\$b\\$ are coprime, this acts like a Cartesian product.

You can use any reasonable input and output format for arrays (pointers, lists, space-separated strings, strings of char codes, etc.)

This is , so the shortest valid answer (measured in bytes) wins.

## Test Cases

```
[1],          [2]       -> [(1, 2)]
[1, 2],       [3]       -> [(1, 3), (2, 3)]
[1, 2],       [3, 4]    -> [(1, 3), (2, 4)]
[1, 2, 3, 4], [5, 6]    -> [(1, 5), (2, 6), (3, 5), (4, 6)]
[5, 5, 5],    [5, 5, 5] -> [(5, 5), (5, 5), (5, 5)]
[5, 5],       [5, 5, 5] -> [(5, 5), (5, 5), (5, 5), (5, 5), (5, 5), (5, 5)]
[1, 2, 3, 4], [1, 2, 3, 4, 5, 6] ->
    [(1, 1), (2, 2), (3, 3), (4, 4),
     (1, 5), (2, 6), (3, 1), (4, 2),
     (1, 3), (2, 4), (3, 5), (4, 6)]

```

# Answer
> 5 votes
# , ~~14~~ 13 bytes

```
,./@($&>~*./)

```

Try it online!

*-1 byte thanks to Bubbler*

This answer takes the two lists as its left arg, and the two list lengths as its right arg.

* `($&>~*./)` is a dyadic hook which applies gcd between the two right arg lengths `*./` and the reshapes the two left arg lists `$` to that length after opening them `&>`. At this point they'll be the same length so boxing is no longer needed.
* `[:,./` so now we can just zip them `,.`

---

## original answer taking the lists directly

## , ~~17~~ 16 bytes

```
(*.&#$[),.*.&#$]

```

Try it online!

* `*.&#` is the gcd `*.` after taking length `#` of both args

It turns out to be shorter to repeat this phrase than to remain DRY.

* `,.` is zip and and `$` is shape. So we shape the left arg `[` by the gcd of the list lengths, do the same to the right arg `]`, and zip them.

# Answer
> 4 votes
# C (clang), ~~70~~ 68 bytes

```
i;f(*a,*b,x,y){for(i=0;printf("(%d,%d)",a[i%x],b[i%y]),++i%x+i%y;);}

```

Try it online!

Takes input as pointer to `a` and `b` and the lengths, prints `q` to std out.

We use the modulo of an iterator by the data lengths e.g. `i % x` and `i % y` to access data, when both modules are equal to 0 , `i` is LCM and the function terminates.

# Answer
> 3 votes
# Jelly, 7 bytes

```
ṁ€æl/}Z

```

A dyadic Link accepting a list of the two lists on the left and a list of their respective lengths on the right which yields a lists of lists.
(A monadic Link accepting only the left argument costs 8 bytes, `ṁ€Ẉæl/$Z`)

**Try it online!** Or see the test-suite.

### How?

```
ṁ€æl/}Z - Link: list of lists [a, b], list [length(a), length(b)]
     }  - use the right argument as the left argument of:
    /   -   reduce by:
  æl    -     least common multiple (i.e. LCM(length(a), length(b))
 €      - for each list in the left argument (i.e. for x in [a,b]):
ṁ       -   mould like (i.e. repeat x cyclically until its length is the calculated LCM)
      Z - transpose

```

# Answer
> 3 votes
# , ~~69~~ ~~60~~ ~~54~~ 51 bytes

```
function(a,b,x,y)cbind(rep(a,y/sum(!(1:x*y)%%x)),b)

```

Try it online!

Loosely based on my answer to this question. Takes `a`,`b`, and the lengths as `x` and `y`, respectively.

Returns a two-column matrix.

Thanks to Robin Ryder for saving 4 bytes, and then another 3.

Relies on the identity \\$xy=GCD(x,y)\cdot LCM(x,y)\\$; repeats `a` by \\$y/GCD(x,y)\\$ times to get it to the LCM length, and `cbind` automatically recycles `b` accordingly.

# Answer
> 3 votes
# , 8 bytes

```
*.&#$&>;

```

Try it online!

Takes two vectors as left/right args and gives a two-row matrix where each column represents a pair. If you insist a two-column matrix, prepend `[:|:` to the code, which is still shorter than previous J answer.

### How it works

```
*.&#$&>;  NB. Tacit function; left=vector 1, right=vector 2
       ;  NB. Nested 2-item vector of two vectors
    $&>   NB. Disclose each and recycle to the length of...
*.&#      NB. LCM of the lengths
          NB. Two disclosed vectors automatically form a 2-row matrix

```

# Answer
> 2 votes
# C (gcc), ~~85~~ 76 bytes

```
n;z(a,i,j)int*a;{for(n=0;a[n*2+i+j]=a[n%i],a[n+++n+i+j]=a[n%j+i],n%i+n%j;);}

```

Try it online!

Thanks to ceilingcat for reduction 85-\>76 bytes.

The code above is golfed so that all the information is stored in a single integer array, which saves 2 bytes; the logic though is the same as previously with three arrays.

Try code with three arrays online this code has less bytes, but the arrays are global so that information is not directly passed in or out of function.

# How

description of algorithm with ungolfed code or at least less golfed code.

setup (see online code)

* `a[],b[]` input data - `q[]` output data
* `i,j` length of `a,b`
* `n` loop counter

```
do{                              }while(n%i+n%j);}
 // open loop that ends when counter mod i and j =0
   q[n*2]=a[n%i];
 // q[0,2,4...]=a[0,1,2...]
                 q[n+++n]=b[n%j];
 // q[1,3,5...]=b[0,1,2...]  and increase loop counter

```

In the golfing process all the data input and output was put into a single `int` array. The first `i` members are the contents of `a`, the next `j` members are the contents of `b` and the remainder of the array is filled with zeroes so that when `q` is calculated it can be placed directly after the `b` items in the same array the first zero in the array indicates `q` end. This use of a single integer array for data input and output saves 2 bytes. OP has indicated that this approach is acceptable for this challenge.

# Answer
> 2 votes
# Perl 6, ~~39~~ ~~36~~ 25 bytes

*-3 bytes thanks to Jo King*

```
{zip $_>>[^[lcm]($_)X%*]}

```

Try it online!

### Explanation

```
{                       }  # Anonymous block
     $_>>[             ]   # Index into both input arrays
          ^[lcm]($_)       # Range [0,lcm)
                    X%*    # modulo array size
 zip  # Zip

```

# Answer
> 2 votes
# Perl 6, 35 bytes

```
{$^a <<,<<flat $^b xx($a lcm$b)/$b}

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 7 bytes

```
€g.¿δ∍ø

```

Takes the input as a pair of lists of integers.

Try it online or verify all test cases.

**Explanation:**

```
€g       # Get the length of each inner list in the (implicit) input-pair of lists
  .¿     # Take the Least Common Multiple for the two values in this pair of lengths
    δ∍   # Extend both inner list in the (implicit) input-pair of lists to this length
      ø  # Then zip/transpose the (now equal-length) list of lists, swapping rows/columns
         # (after which the result is output implicitly)

```

# Answer
> 1 votes
# Charcoal, 21 bytes

```
≔¹ηＷ⊙θ﹪ηＬκ≦⊕ηＩＥηＥθ§λκ

```

Try it online! Link is to verbose version of code. Takes input as an array of arrays and outputs as a double-spaced list of pairs. Explanation:

```
≔¹ηＷ⊙θ﹪ηＬκ≦⊕η

```

Count up from 1 until the LCM of the lengths of the arrays has been reached. (This O(n²) but even O(n) would cost 3 bytes.)

```
ＩＥηＥθ§λκ

```

Map over the implicit range and cyclically index both arrays.

# Answer
> 1 votes
# Wolfram Language (Mathematica), 42 bytes

```
Thread@PadRight[#,{2,LCM@@(Length/@#)},#]&

```

Try it online!

# Answer
> 1 votes
# Python 3.8 (pre-release), ~~78~~ 76 bytes

-2 bytes thanks to Noodle9

```
lambda a,b:zip((x:=len(b))//(g:=math.gcd(y:=len(a),x))*a,y//g*b)
import math

```

Try it online!

# Answer
> 1 votes
# JavaScript (ES6),  ~~77 68 64~~  58 bytes

*Saved 6 bytes thanks to @AZTECCO*

Takes input as `(a, b, a_length, b_length)`.

```
(a,b,n,N)=>(g=i=>[[a[i%n],b[i%N]],...++i%n+i%N?g(i):[]])``

```

Try it online!

# Answer
> 1 votes
# APL (Dyalog Extended), 9 bytes

```
,¨/∧⍥≢⍴¨⍮

```

Try it online!

Takes two input strings as left and right arguments respectively. Being able to take lengths as separate arguments doesn't really help.

### How it works

```
,¨/∧⍥≢⍴¨⍮  ⍝ left: string a, right: string b
        ⍮  ⍝ 2-item nested array of [a, b]
      ⍴¨   ⍝ Reshape (by cycling elements) each of [a, b] to the length of...
   ∧⍥≢     ⍝   LCM of lengths of a and b
,¨/        ⍝ Reduce by "pair up element-wise"

```

# Answer
> 1 votes
# Brachylog, 15 bytes

```
{l×↙X}ᵛḃ₁g,?zbᵐ

```

Try it online!

Initially, I thought "it's funny, Brachylog has a cycling zip builtin but I don't think I'll need it", but my various attempts at `j` and `z₂`-based solutions have simply refused to terminate on test cases where the second list is longer than the first.

```
{    }ᵛ            For each element of the input,
 l                 the length
  ×                multiplied by
   ↙X              something
{    }ᵛ            comes out to the same value.
       ḃ₁          Convert that value to unary,
         g         wrap it in a list,
          ,?       append the elements of the input,
            z      cycling zip,
             bᵐ    and remove the first element from each element of the result.

```

Note that `{×↙Xℕ₁}ᵛ` calculates LCM, but the `ℕ₁` constraint isn't necessary in this case because `z` fails if any element of its input is empty (since it can't be cycled).

# Answer
> 0 votes
# Perl 5, 104 bytes

```
sub f{($A,$B,%s)=@_;map[$$A[$$_[0]],$$B[$$_[1]]],grep!$s{$$_[0],$$_[1]}++,map[$_%@$A,$_%@$B],0..@$A*@$B}

```

Try it online!

Slightly ungolfed:

```
sub f {
  ($A,$B,%s) = @_;                #input A and B, %s is the "seen" dictionary
  map [$$A[$$_[0]], $$B[$$_[1]]], #convert indexes to values from input A and B, return that.
  grep !$s{$$_[0],$$_[1]}++,      #filter out index pairs seen before
  map [$_%@$A,$_%@$B],            #make array of pairs where 1st elem is
                                  #...index of A and 2nd is index of B,
                                  #...but modulo their size respectively
  0..@$A*@$B                      #loop from 0 to size_of_A * size_of_B
}

```

# Answer
> 0 votes
# Ruby, 52 bytes

```
->x,y{a=x.size;a/=g=a.gcd b=y.size;(x*b/=g).zip y*a}

```

Try it online!

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


title: Code (Mini) Golf

text:
# Question
Title: Code (Mini) Golf
Given a side-view of a mini-golf course and the power of the swing, determine if the ball will make it into the hole.

---

A course will be in this format:

```
      ____       ____ _
   __/    \     /    U \
__/        \   /        \_
            \_/

```

The ball starts directly **before** the first piece of ground on the left and follows the contour of the course until it reaches the hole (an upper-case `U` below the current level of the ground). If it reaches the hole, output a truthy value. The power of the swing will be the initial speed of the ball. The ball moves to the next character on the right at each iteration, then the speed is altered depending on the character it is now on. If the speed reaches `0` or less before the hole, output a falsey value.

* `_` decreases the speed by `1`
* `/` decreases the speed by `5`
* `\` increases the speed by `4`

Courses can optionally be padded with spaces. The power of the swing will always be a positive integer.

You do not need to worry about the ball going too fast to enter the hole, rolling backwards or jumping/bouncing off hills.

## Test Cases

```
Input: 27
      ____       ____ _
   __/    \     /    U \
__/        \   /        \_
            \_/
Output: true

----------

Input: 26
      ____       ____ _
   __/    \     /    U \
__/        \   /        \_
            \_/
Output: false

----------

Input: 1

U
Output: true

----------

Input: 1
_
 U
Output: false

----------

Input: 22

     /U
    /
   /
  /
\/
Output: true

----------

Input: 999
_       _
 \     /
  \   /
   \ /
    U
Output: true

----------

Input: 5
  /
/U
Output: false

----------

Input: 9

/\/\/\/\/U
Output: false

----------

Input: 16

_/\                                         _
   \      __       /\/\/\                  /
    \    /  \     /      \                /
     \__/    \   /        \____________ _/
              \_/                      U

Output: true

```

This is code mini-golf, shortest answer in bytes wins!

# Answer
# Pyth, 27 bytes

```
.Am<sXsd"_\ /"[1_4Z5)Q._C.z

```

Demonstration

This code does something very clever and not at all type-safe with `X`. Check it out below.

**Explanation:**

```
.Am<sXsd"_\ /"[1_4Z5)Q._C.z
                               Implicit: Z = 0, Q = eval(input())
                               Q is the initial power.
                         .z    Take all input, as a list of lines.
                        C      Transpose, giving all columns.
                      ._       Form all prefixes.
  m                            Map over the prefixes.
      sd                       Concatenate the prefix.
     X  "_\ /"[1_4Z5)          Change '_' to 1, '\' to -4, ' ' to 0, and '/' to 5.
                               In particular, 'U' is left unchanged.
    s                          Reduce on addition.
                               If all elements were numbers,
                               this results in the total change in power.
                               If there was a 'U', it results in a string.
   <                 Q         If the previous result was a number, this compares
                               it with the initial input to see if the ball is
                               still rolling.
                               If the previous result was a string, this slices off
                               the first Q characters, which always has a truthy
                               result.
.A                             Test whether all of the prefixes mapped to a thruthy
                               result.

```
> 17 votes

# Answer
## Haskell, ~~111~~ 109 bytes

```
import Data.List
g"_"=1
g"/"=5
g _= -4
f n=all(>0).scanl(-)n.map g.fst.span(/="U").(>>=words).transpose.lines

```

Usage example:

```
*Main> f 27 "      ____       ____ _   \n   __/    \\     /    U \\  \n__/        \\   /        \\_\n            \\_/           "
True
*Main> f 26 "      ____       ____ _   \n   __/    \\     /    U \\  \n__/        \\   /        \\_\n            \\_/           "
False

```

How it works:

```
                            lines  -- split into list of lines at nl
                       transpose   -- transpose
                  (>>=words)       -- turn each line into words (i.e. remove spaces)
            fst.span(/="U")        -- take all words up to but excluding "U"
         map g                     -- turn each word into the speed modifier
    scanl(-)n                      -- build list of partial sums starting with n
                                   --   note: speed modifiers are negative so we
                                   --   use (-) with scanl to build sums
all(>0)                            -- return true if all sums are greater than 0

```

Edit: @user81655 found 2 bytes to save. Thanks!
> 14 votes

# Answer
# Ruby, ~~104~~ 87 characters

```
->s,t{t.lines.map(&:bytes).transpose.map{|o|(c=o.max)==85||s<0?break: s+=c*3%14-6}
s>0}

```

Sample run:

```
2.1.5 :001 > track = '      ____       ____ _
2.1.5 :002'>    __/    \     /    U \
2.1.5 :003'> __/        \   /        \_
2.1.5 :004'>             \_/
2.1.5 :005'> '
 => "      ____       ____ _   \n   __/    \\     /    U \\  \n__/        \\   /        \\_\n            \\_/           \n"

2.1.5 :006 > ->s,t{t.lines.map(&:bytes).transpose.map{|o|(c=o.max)==85||s<0?break: s+=c*3%14-6};s>0}[27, track]
 => true

2.1.5 :007 > ->s,t{t.lines.map(&:bytes).transpose.map{|o|(c=o.max)==85||s<0?break: s+=c*3%14-6};s>0}[26, track]
 => false

```
> 7 votes

# Answer
# Japt, 38 bytes

```
Vz r"%s|U[^]*" ¬e@UµX¥'_?1:X¥'/?5:-4 ¬

```

`Try it here!`

Beating CJam!

# Explanation

Basically takes the string input, rotates it 90deg clockwise, strips out spaces and newlines, removes the hole and everything after it, and splits along chars. Then checks if ball ever gets to zero or below using the `every` function.
> 6 votes

# Answer
## CJam, ~~40~~ 39 bytes

```
liqN/:.e>'U/0="\_/"[4W-5]er{1$+}/]:e<0>

```

Input has the power on the first line and the course starting on the second line. Output is `0` or `1`.

Test it here.

### Explanation

```
li    e# Read power and convert to integer.
qN/   e# Read course and split into lines.
:.e>  e# Flatten course by folding maximum over columns.
'U/   e# Split around the hole.
0=    e# Keep the first chunk.
"\_/"[4W-5]er
      e# Replace \, _, / with 4, -1, 5, respectively.
{     e# For each of those costs...
  1$+ e#   Copy the previous power and add the cost.
}/    e# This leaves all partial sums on the stack.
]     e# Wrap them in an array.
:e<   e# Find the minimum.
0>    e# Check whether it's positive.

```
> 6 votes

# Answer
## Retina, ~~82~~ ~~81~~ ~~77~~ ~~74~~ ~~68~~ ~~67~~ 68 bytes

```
+`(?<=(.)*) (?=.*¶(?<-1>.)*(.))
$2
\\
>>>>
+`>_|>{5}/|>¶

^>*U

```

Try it online

* Input is represented in *unary base*, as n `>`s - for example, 4 is `>>>>\n`. (is this legal?)
* `+`(?<=(.)*) (?=.*¶(?<-1>.)*(.))` `$2` \- flatten the course - replace spaces with the character below them.

After this stage the data will look like this:

```
>>>>>>>>>>>>>>>>>>>>>>>>>>
__/__/____\\\_///____U_\\_
__/__/    \\\_///    U \\_
__/        \\_//        \_
            \_/

```

We can just ignore everything after the first `U`, we will not reach there anyway.
* `>` represent a step we are allowed to make, or the remaining energy.
* Replace each `\` with four `>` \- a slope gives us additional energy.
* Loop: contentiously remove `>_` or `>>>>>/` until there are none left. `_`s and `/`s *consume* energy.
* Finally, try to match `^>*U` \- check if we can reach `U` with positive energy (or no energy).
This will output `0` or `1`.

---

Another close option with ~~91~~ 79 bytes is:

```
+`(?<=¶(.)*) (?=.*¶(?<-1>.)*(.))
$2
^(>)+\n(?<-1>_|/(?<-1>){4}|\\(?<1>){5})+U

```

Try it online

This is the same approach but with a balancing group instead of a contentious replace.

I'm sure both of these can be golfed further, so any one of them may end up shorter.
> 5 votes

# Answer
## Python (3.5) ~~169~~ 160 bytes

A recursive solution without the transpose function (zip)

```
def f(c,p):c=c.splitlines();l=len(c);f=lambda x,h,v:v if'U'==c[h][x]or v<1 else f(x+(h==l-1),(h+1)%l,v+{"_":-1,"\\":4,"/":-5," ":0}[c[h][x]]);return f(0,0,p)>0

```

## Ungolfed

c for course, p for power, v for speed, h for height

```
def f(c,p):
    c=c.splitlines()
    l=len(c)
    tmp = {"_":-1,"\\":4,"/":-5," ":0}
    f=lambda x,h,v:v if'U'==c[h][x]or v<1 else f(x+(h==l-1),(h+1)%l,v+tmp[c[h][x]])
    return f(0,0,p)>0

```

## Usage

```
f(16,"_/\                                         _\n   \      __       /\/\/\                  / \n    \    /  \     /      \                /  \n     \__/    \   /        \____________ _/   \n              \_/                      U     ")
f(9,"/\/\/\/\/U")

```
> 3 votes

# Answer
## ES6, 117 bytes

```
(c,p)=>c.split`
`.map(s=>[...s.slice(0,c.match(/^.*U/m)[0].length-1)].map(c=>p+=c=='/'?-5:'    \\'.indexOf(c)))&&p>0

```

Ungolfed:

```
function hole(course, power) {
    width = course.match(/^.*U/m)[0].length - 1; // calculate width to hole
    lines = course.split("\n");
    for (i = 0; i < lines.length; i++) {
        line = lines[i].slice(0, width); // ignore extraneous parts of the course
        for (j = 0; j < line.length; j++) {
            switch (line[j]) { // accumulate remaining power
            case '/': power -= 5; break;
            case '\\': power += 4; break;
            case ' ': break;
            default: power--; break;
            }
        }
    }
    return power > 0;
}

```

Edit: Saved 4 bytes thanks to ՊՓԼՃՐՊՃՈԲՍԼ.
> 3 votes

# Answer
# JavaScript (ES6), ~~108~~ ~~107~~ 106 bytes

This is the solution I came up with when I created the challenge.

```
(p,c)=>[...(l=c.split`
`)[w=0]].map((_,i)=>l.map(t=>(g=t[i])-1|p<=0?0:p-=g>"]"?1:g>"U"?-4:g>"/"?w=1:5))&&w

```

## Explanation

Takes the power as a number and the course as a string. Returns `1` for `true` or `0` for `false`. The course must be padded with spaces.

```
(p,c)=>
  [...(l=c.split`
`)                          // l = array of lines
  [w=0]]                    // w = true if the ball has entered the hole
.map((_,i)=>                // for each index i
  l.map(t=>                 // for each line t
    (g=t[i])                // g = the character at the current index
    -1|p<=0?0:              // do nothing if g is a space or the ball has no speed left
    p-=
      g>"]"?1               // case _: subtract 1 from p
      :g>"U"?-4             // case \: add 4 to p
      :g>"/"?w=1            // case U: set w to true (it doesn't matter what happens to p)
      :5                    // case /: subtract 5 from p
  )
)
&&w                         // return w

```

## Test

```
var solution = (p,c)=>[...(l=c.split`
`)[w=0]].map((_,i)=>l.map(t=>(g=t[i])-1|p<=0?0:p-=g>"]"?1:g>"U"?-4:g>"/"?w=1:5))&&w
```

```
Power = <input type="number" id="power" value="16" /><br />
<textarea id="course" rows="6" cols="50">_/\                                         _
   \      __       /\/\/\                  /
    \    /  \     /      \                /
     \__/    \   /        \____________ _/
              \_/                      U     </textarea><br />
<button onclick="result.textContent=solution(+power.value,course.value)">Go</button>
<pre id="result"></pre>
```
> 3 votes

# Answer
## Pyth, 35 bytes

```
VC.z=-Q@(1_4 5)x"_\\/"JrN6IqJ\U>Q_5

```

Explanation

```
                                    - Autoassign Q = eval(input())
                                    - Autoassign .z = rest of input
VC.z                                - For N in zip(*.z)
    =-Q                             - Q -= ...
                      JrN6          - Autoassign J to N.strip() (get rid of spaces)
       @(1_4 5)x"_\\/"              - {"_":1, "\\": -4, "/": 5, "U":5}[J] ("U" isn't defined but that's what it is according to how str.index works)
                          IqJ\U     - If J == "U"
                               >Q_5 - print Q > -5 ()

```
> 2 votes

# Answer
**JavaScript, ~~266~~ ~~263~~ 244 bytes**

```
(s,a)=>{var f=(e,x)=>{for(var i=1;D=e[i][x],i<e.length;i++)if(D!=" ")return D},o=a.split(`
`),l=o.reduce((a,b)=>Math.max(a.length||a,b.length)),b="";for(i=0;i<l;i)b+=f(o,i++);for(i=0;b[i]!="U"&&s>0;i++)s-=b[i]=="_"?1:b[i]=="/"?5:-4;return s>0}

```

**Ungolfed**

```
(s,a)=>{
    var f=(e,x)=>{
        for(var i=1;D=e[i][x],i<e.length;i++)
            if(D!=" ")
                return D
    },
    o=a.split(`
`),
    l=o.reduce((a,b)=>Math.max(a.length||a,b.length)),
    b="";
    for(i=0;i<l;)
        b+=f(o,i++);
    for(i=0;b[i]!="U"&&s>0;i++)
        s-=b[i]=="_"?1:b[i]=="/"?5:-4;
    return s>0
}

```

**Usage**

```
var o = (s,a)=>{var f=(e,x)=>{for(var i=1;D=e[i][x],i<e.length;i++)if(D!=" ")return D},o=a.split(`
`),l=o.reduce((a,b)=>Math.max(a.length||a,b.length)),b="";for(i=0;i<l;)b+=f(o,i++);for(i=0;b[i]!="U"&&s>0;i++)s-=b[i]=="_"?1:b[i]=="/"?5:-4;return s>0}

o(27, `
      ____       ____ _
   __/    \\     /    U \\
__/        \\   /        \\_
            \\_/           `); // will return true

```
> 1 votes

# Answer
# Ruby, 85 characters

```
->i,s{s.lines.map(&:bytes).transpose.any?{|o|(c=o.max)==85||i<0||!(i+=c*3%14-6)};i>0}

```

Adapted @manatwork's answer
> 1 votes

# Answer
# Java, 219 Bytes

```
boolean p(int v,String c){int z=c.length(),f[]=new int[z],e,i,k;for(String r:c.split("\n"))for(i=-1;++i<r.length();)if((e=r.charAt(i))>32)f[i]=e;for(i=-1,e=0;++i<z&v>0;)v-=(k=f[i])>94?1:k>91?-4:k>84?(e=1):5;return 0<e;}

```
* Flatten the course, because the y-coordinate doesn't matter, unfortunately Java doesn't have a vertical trim. It also doesn't have a String-transpose.
* Iterate over the flattened course and keep track of the ball speed.
> 1 votes

# Answer
# Octave, ~~111~~ 110 bytes

```
function g(v,s) A([95,47,92])=[1,5,-4];all(v>cumsum(A(m=max(cat(1,strsplit(s,'\n'){:}),[],1)))(1:find(m==85)))

```

### Explanation:

* Split the input on newlines and convert that annoying cell array to a matrix
* Flatten the matrix by finding the `max` for each column
* Map the characters `'_/\'` to `[1, 5, -4]` (all other characters less than `'_'` are mapped to `0`)
* Calculate the cumulative sum of all elements of the mapped array
* Output `True` if all cumulative sums from the beginning of the course to the cup are less than the start velocity (`False` otherwise).

---

Here is a test case that I had already developed similar to the second one proposed by @Erwan and a couple of results:

```
s9 =
   /\
  /  \
_/    \
       \
        \
         U

g(11,s9) %False
ans = 0
g(17,s9) %True
ans =  1

```

And here's the first test case:

```
s10 =
  _
 / U\
/    \
      \
       \
        \
         \
          \_

>> g(11,s10)
ans = 0
>> g(12,s10)
ans =  1

```
> 1 votes

# Answer
# Python, ~~212~~ ~~201~~ ~~188~~ 143 bytes

Much of the credit for this iteration of this script goes to @Erwan, who gave me an entirely different approach to try and some tips that saved me 55 bytes in the end.

Not recursive, so should be substantially different from the other python solution.

```
def g(c,p):
 o=[''.join(x).split()[0] for x in zip(*c.split('\n'))]
 t={"_":1,"/":5,"\\":-4}
 for v in o:
    if v=="U" or p<1:return p>0
    p-=t[v]

```

Ungolfed a bit:

```
def g(course,power):
  course=course.split('\n') # split into lines
  course=zip(*course)

  #transpose and flatten course, then remove spaces
  one_line_course=[''.join(x).split[0] for x in zip(*course)]

  terrain_values={"_":1,"/":5,"\\":-4}
  for char in one_line_course:
    if char=="U" or power<1:
      return power>0 # true when power remains, false otherwise
    power-=terrain_values[char]

```
> 0 votes

# Answer
## C, 629 Bytes

```
#include <string.h>
#include <stdlib.h>
#include <string.h>

bool swing(char *c, unsigned int p)
{
    char *olc = calloc(strlen(c), 1);
    int x = 0;
    char *n = c;

    while(1) {
        if(*n == '\0')  break;
        else if(*n == ' ') x += 1;
        else if(*n == '\n') x = 0;
        else {
            olc[x] = *n;
            x += 1;
        }
        n++;
    }

    int hd = 0;
    for(char *i = olc; i != strchr(olc, 'U'); i++) {
        if(*i == '_') hd += 1;
        else if(*i == '/') hd += 5;
        else hd -= 4;
    }

    free(olc);
    if(hd < p) return 1;
    return 0;
}

```

Ungolfed:

```
bool swing(char *course, unsigned int power)
{
    const size_t course_len = strlen(course);
    char *one_line_course = calloc(course_len, sizeof(char));
    assert(one_line_course);
    int x_pos = 0;
    char *next = course;

    //Convert to one line representation
    while(1) {
        if(*next == '\0') {
            break;
        }
        else if(*next == ' ') {
            x_pos += 1;
        }
        else if((*next == '\n') || (*next == '\r')) {
            x_pos = 0;
        }
        else {
            one_line_course[x_pos] = *next;
            x_pos += 1;
        }
        next++;
    }

    //Calculate power vs distance
    const char *hole_location = strchr(one_line_course, 'U');
    int hole_distance = 0;
    for(char *i = one_line_course; i != hole_location; i++) {
        if(*i == '_') {
            hole_distance += 1;
        }
        else if(*i == '/') {
            hole_distance += 5;
        }
        else {
            hole_distance -= 4;
        }
    }

    free(one_line_course);
    if(hole_distance < power) {
        return true;
    }
    else {
        return false;
    }
}

```

Basically I just make one pass to convert the input string to fit everything in one line, then
> 0 votes

# Answer
# , 47 bytes

```
1 e.(<:4([:+/\1 5 _4{~i.&3{.])@-.~'_/\U',@i.|:)

```

Try it online!
> 0 votes

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