title: Generate a looping array

text:
# Question
Title: Generate a looping array
## Introduction

A *pointer array* is an array `L` of nonzero integers where `0 ≤ L[i]+i < len(L)` holds for all indices `i` (assuming 0-based indexing). We say that the index `i` *points* to the index `L[i]+i`. A pointer array is a *loop* if the indices form a single cycle of length `len(L)`. Here are some examples:

* `[1,2,-1,3]` is not a pointer array, because the `3` does not point to an index.
* `[1,2,-1,-3]` is a pointer array, but not a loop, because no index points to the `-1`.
* `[2,2,-2,-2]` is a pointer array, but not a loop, because the indices form two cycles.
* `[2,2,-1,-3]` is a loop.

## Input

Your input is a non-empty list of nonzero integers, in any reasonable format. It may be unsorted and/or contain duplicates.

## Output

Your output shall be a loop that contains all the integers in the input list (and possibly other integers too), counting multiplicities. They need not occur in the same order as in the input, and the output need not be minimal in any sense.

## Example

For the input `[2,-4,2]`, an acceptable output would be `[2,2,-1,1,-4]`.

## Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. Including a couple of example inputs and outputs in your answer is appreciated.

## Test cases

These are given in the format `input -> some possible output(s)`.

```
[1] -> [1,-1] or [1,1,1,-3]
[2] -> [2,-1,-1] or [1,2,-2,-1]
[-2] -> [1,1,-2] or [3,1,2,-2,-4]
[2,-2] -> [2,-1,1,-2] or [2,-1,2,-2,-1]
[2,2,2] -> [2,-1,2,-2,2,-2,-1] or [2,2,2,2,-3,-5]
[2,-4,2] -> [2,2,-1,1,-4] or [2,5,1,1,1,-4,2,-7,-1]
[3,-1,2,-2,-1,-5] -> [2,3,-1,2,-1,-5] or [3,3,-1,-1,2,2,-1,6,1,1,1,1,-12,-5]
[-2,-2,10,-2,-2,-2] -> [10,-1,1,-2,-2,1,-2,-2,1,-2,-2]
[-15,15,-15] -> [15,-1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,-15,-15]
[1,2,3,4,5] -> [1,2,3,-1,4,-1,5,-1,-1,-9,-1,-1]

```

# Answer
# Jelly, 12 bytes

```
ż~Ṣ€FxA$;L$U

```

Try it online!

### Background

Consider the pair of integers **n, ~n**, where **n ≥ 0** and **~** denotes bitwise NOT, i.e., **~n = -(n + 1)**.

By placing **n** copies of **n** to the left of **n + 1** copies of **~n**, if we start traversing the pointer array from the rightmost **~n**, we'll traverse all **2n + 1** elements and find ourselves at the left of the leftmost **n**.

For example, if **n = 4**:

```
X  4  4  4  4  -5 -5 -5 -5 -5
                            ^
            ^
                         ^
         ^
                      ^
      ^
                   ^
   ^
                ^
^

```

For the special case **n = 0**, the element **n** itself is repeated **0** times, leaving this:

```
X -1
   ^
^

```

For each integer **k** in the input, we can form a pair **n, ~n** that contains **k** by setting **n = k** if **k \> 0** and **n = ~k** if **k \< 0**. This works because **~** is an involution, i.e., **~~k = k**.

All that's left to do is chain the generated tuples and prepend their combined lengths, so the leftmost element takes us back to the rightmost one.

### Examples

```
[1] -> [3, 1, -2, -2]
[2] -> [5, 2, 2, -3, -3, -3]
[-2] -> [3, 1, -2, -2]
[2, -2] -> [8, 1, -2, -2, 2, 2, -3, -3, -3]
[2, 2, 2] -> [15, 2, 2, -3, -3, -3, 2, 2, -3, -3, -3, 2, 2, -3, -3, -3]
[2, -4, 2] -> [17, 2, 2, -3, -3, -3, 3, 3, 3, -4, -4, -4, -4, 2, 2, -3, -3, -3]
[3, -1, 2, -2, -1, -5] -> [26, 4, 4, 4, 4, -5, -5, -5, -5, -5, -1, 1, -2, -2, 2, 2, -3, -3, -3, -1, 3, 3, 3, -4, -4, -4, -4]
[-2, -2, 10, -2, -2, -2] -> [36, 1, -2, -2, 1, -2, -2, 1, -2, -2, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, -11, 1, -2, -2, 1, -2, -2]
[-15, 15, -15] -> [89, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, -16, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15]
[1, 2, 3, 4, 5] -> [35, 5, 5, 5, 5, 5, -6, -6, -6, -6, -6, -6, 4, 4, 4, 4, -5, -5, -5, -5, -5, 3, 3, 3, -4, -4, -4, -4, 2, 2, -3, -3, -3, 1, -2, -2]

```

### How it works

```
ż~Ṣ€FxA$;L$U  Main link. Argument: A (list of integers)

 ~            Yield the bitwise not of each k in A.
ż             Zipwith; pair each k in A with ~k.
  Ṣ€          Sort each pair, yielding [~n, n] with n ≥ 0.
    F         Flatten the list of pairs.
       $      Combine the previous two links into a monadic chain:
      A         Yield the absolute values of all integers in the list.
                |n| = n and |~n| = |-(n + 1)| = n + 1
     x          Repeat each integer m a total of |m| times.
          $   Combine the previous two links into a monadic chain:
         L      Yield the length of the generated list.
        ;       Append the length to the list.
           U  Upend; reverse the generated list.

```
> 11 votes

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


# Question
Title: Shorten an already short mathematical expression
For once, I was doing some real work, updating old code, and bumped into an expression that is equivalent to what would be written as ***πx + ex*** in good old-fashioned math. I thought it would be possible to write it shorter than it was written in the language I work with (APL), and therefore present this very simple challenge:

Write a function or program that (by any means) accepts zero or more numbers, and returns (by any means) the result of the above expression for ***x =*** *each of the given numbers* with at least 3 significant digits for each result.

If your language does not have ***π*** and/or ***e***, use the values 3.142 and 2.718.

Scoring is number of bytes, so preface your answer with `# LanguageName, 00 bytes`.

Standard loop-holes are not allowed.

---

Edit: Now the solution I came up with, `○+*`, has been found. The original code was `(○x)+*x`.

# Answer
> 21 votes
# Dyalog APL, 3 characters

As a tacit phrase.

```
○+*

```

Monadic  multiplies its argument with π, monadic `*` is the exponential function `exp`. `○+*` is a train such that `(○+*)ω` is equal to `(○ω)+(*ω)`. Since this is APL, the phrase works for arguments of arbitrary shape, e. g. you can pass a vector of arbitrary length.

The same solution is possible in J as `o.+^` with `o.` being  and `^` being `*`.

# Answer
> 29 votes
# Emotinomicon, 48 bytes / 13 characters

*I do it, not because it is short, but because it is fun.* Try it here. You'll have to copy+paste it into the textbox.

```
⏪✖➕⏩

```

Explanation:

```
  ⏪       ✖       ➕         ⏩   explanation
                                              take numeric input
    ⏪                                           open loop
                                              duplicate top of stack
                                              push pi
                ✖                               multiply top two elements on stack
                                              reverse stack
                                              pop N, push e^N
                            ➕                   add top two elements on stack
                                              take numeric input
                                              duplicate top of stack
                                              pop N, push N+1
                                            ⏩   close loop

```

Here is the program in its native environment, the mobile phone:

# Answer
> 9 votes
# R, ~~25~~ 24 bytes

```
cat(exp(x<-scan())+pi*x)

```

Is this it? It gets input from user, assign it to `x`, calculates its exponential multiply it to `pi`, and finally `cat()`prints the result.

edit: 1 bytes saved thanks to Alex A.

# Answer
> 7 votes
# JavaScript (ES6), ~~39~~ 34 bytes

*Saved 5 bytes thanks to @edc65*

```
a=>a.map(x=>x*Math.PI+Math.exp(x))

```

Takes input as an array of numbers, and outputs in the same format.

Thanks to the reduction, there are now three equivalent 45-byte programs, all ES5-compliant:

```
for(;x=prompt();)alert(x*Math.PI+Math.exp(x))
for(M=Math;x=prompt();)alert(x*M.PI+M.exp(x))
with(Math)for(;x=prompt();)alert(x*PI+exp(x))

```

Inputs should be entered one at a time. Press OK without entering anything to quit.

The third one highlights an interesting feature in JS: the `with` statement. While sometimes unsafe to use (thus disabled in strict mode), it can still be used to save typing out an object name and period every time you need to access it. For example, you can do this:

```
x=[];with(x)for(i=0;i<5;i++)push(length);

```

`push` and `length` are then used as properties of `x`, which will result with `x` being `[0,1,2,3,4]`.

This works on *any* object, even non-variables, so for example, you can do this:

```
with("0123456789ABCDEF")for(i=0;i<length;i++)alert("0x"+charAt(i)-0);

```

`charAt` and `length` are called as properties of the string. `"0x"+x-0` converts `x` from a hex value to a number, so this `alert`s the numbers 0 through 15.

# Answer
> 6 votes
# Pyth, ~~11~~ 13

```
VQ+*N.n0^.n1N

```

Now takes `x` as a list, e.g. `[1.25, 2.38, 25]`

Previous (11 bytes): `+*Q.n0^.n1Q`

```
VQ            +       * N .n0            ^ .n1 N
For each      Add     List Item * Pi     e ^ List Item
input item

```

# Answer
> 6 votes
# Mathematica, ~~11~~ 10 bytes

```
N@Pi#+E^#&

```

With 1 byte saved thanks to LegionMammal978.

# Answer
> 5 votes
## Seriously, 10 bytes

```
,`;e(╦*+`M

```

Hex Dump:

```
2c603b6528cb2a2b604d

```

Try It Online

Takes inputs as a list (see link for example).

Explanation:

```
,                               Get input list
 `      `M                      Map this function over it
  ;                             Copy the input value.
   e                            exponentiate
    (                           dig up the other copy
     ╦*                         multiply by pi
       +                        add

```

# Answer
> 5 votes
# Python 2, 38 bytes (~~52~~ 49 bytes w. math)

```
lambda l:[3.142*x+2.718**x for x in l]

```

If I have to use the math module:

```
from math import*
lambda l:[pi*x+e**x for x in l]

```

Input should be a list of numbers

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

> [5.8599999999999994, 13.671524, 29.505290232, 67.143510850576007, 164.04623849186558]

```

# Answer
> 5 votes
# MATLAB, 15 bytes

```
@(x)pi*x+exp(x)

```

# Answer
> 5 votes
# TI-BASIC, 5 bytes

```
πAns+e^(Ans

```

TI-BASIC doesn't use ASCII bytes, so each of these is stored as one byte in the calculator: `π`, `Ans`, `+`, `e^(`, and `Ans`. It assumes the previous expression is the input (like `{1,2,3}`).

# Answer
> 4 votes
# MATL, 9 bytes

This answer uses the current version of the language (3.1.0), which is earlier than the challenge.

```
itYP*wZe+

```

Input is a vector containing all numbers (list enclosed by square brackets and separated by spaces, commas of semicolons), such as `[5.3 -7 3+2j]`. Complex values are allowed. Output has 15 significant digits.

### Example

```
>> matl itYP*wZe+
> [1 2 3]
5.859874482048839 13.67224140611024 29.51031488395705

```

### Explanation

Straightforward operations:

```
i       % input
t       % duplicate
YP      % pi
*       % multiplication
w       % swap elements in stack
Ze      % exponential
+       % addition

```

# Answer
> 4 votes
## MATLAB: 70 bytes

```
@(x)num2str(arrayfun(@(x)(round(pi*x+exp(x),2-floor(log10(pi*x+exp(x))))),x))

```

Test:

```
ans(1:10)
5.86            13.7            29.5            67.2             164             422            1120            3010            8130           22100

```

Explanation: There were several issues with number formatting.

Firstly, the question requires 3 sig-figs. Matlab has no built-in function for rounding by sig-figs (only by decimal places), so the following workaround was required:

`floor(log10(pi*x+exp(x))))` computes the largest significant digit.

`@(x)(round(pi*x+exp(x),2-floor(log10(pi*x+exp(x))))),x))` takes input `x` and rounds to 3 significant digits.

Another requirement was to handle multiple inputs. The above code can work only with single number. To mitigate this, we use `arrayfun` to evaluate the function for each vector element.

The last problem, Matlab displays the result of arrayfun with its own rounding that leads to outputs like `1.0e+04 * 0.0006` which violates the 3 sig-fig requirement. So, `num2str` was used to turn array into `char` format.

Matlab is good for numerical analysis, but, frankly, it sucks when it comes to fine number formatting

UPD: well, that's embarrassing that I confused

> with at least 3 significant digits

with

> with 3 significant digits

Anyway, I'll leave my answer in this form because the 15 bytes Matlab solution is already given by @costrom

# Answer
> 4 votes
# Julia, 12 bytes

```
x->π*x+e.^x

```

This is an anonymous function that accepts an array and returns an array of floats. To call it, give it a name, e.g. `f=x->...`.

Julia has built-in constants `π` and `e` for—you guessed it—π and e, respectively. The `.^` operator is vectorized exponentiation.

# Answer
> 3 votes
## Haskell, ~~22~~ 19 bytes

```
map(\x->pi*x+exp x)

```

Try it online!

Edit: -3 bytes thanks to @H.PWiz

# Answer
> 3 votes
# Japt, 12 bytes

```
N®*M.P+M.EpZ

```

Takes input as space-separated numbers. Try it online!

### How it works

```
N®   *M.P+M.EpZ
NmZ{Z*M.P+M.EpZ

        // Implicit: N = array of inputs, M = Math object
NmZ{    // Map each item Z in N to:
Z*M.P+  //  Z times PI, plus
M.EpZ   //  E to the power of Z.
        // Implicit: output last expression

```

# Answer
> 3 votes
# J, 4 bytes

```
o.+^

```

Same as APL `○+*`, but J's `pi times` function is called `o.`, which is one byte longer.

# Answer
> 2 votes
# Par, 8 bytes

```
✶[″℗↔π*+

```

Accepts input as `(1 2 3)`

## Explanation

```
               ## [implicit: read line]
✶              ## Parse input as array of numbers
[              ## Map
 ″             ## Duplicate
 ℗             ## e to the power
 ↔             ## Swap
 π*            ## Multiply by π
 +             ## Add

```

# Answer
> 2 votes
# CJam, 13 bytes

```
q~{_P*\me+}%p

```

Takes input as an array separated by spaces (e.g. `[1 2 3]`). Try it online.

### Explanation

```
q~    e# Read the input and evaluate it as an array
{     e# Do this for each number x in the array...
  _P* e# Multiply x by pi
  \me e# Take the exponential of x (same as e^x)
  +   e# Add the two results together
}%
p     e# Pretty print the final array with spaces

```

# Answer
> 2 votes
# Racket, 27 bytes

```
map(λ(x)(+(* pi x)(exp x)))

```

when put in the function position of an expression:

```
(map(λ(x)(+(* pi x)(exp x))) '(1 2 3 4))

> '(5.859874482048838 13.672241406110237 29.510314883957047 67.16452064750341)

```

# Answer
> 1 votes
# Reng v.3.3, 53 bytes

Noncompeting because it postdates the challenge, but hey, not winning any awards for brevity. :P Try it here!

```
2²5³*:"G"(%3+i#II*ZA*9+(%2+#E1II0e1+ø
1-)E*(:0eø
$+n~

```

## Line 0

Here is a view of the stack in line 0:

```
Sequence read | Stack
2²            | 4
5³            | 4 125
*             | 500
:             | 500 500
"G"           | 500 500 71
(             | 500 71 500
%             | 500 0.142
3+            | 500 3.142
i             | 500 3.142 <i>
#I            | 500 3.142     ; I <- i
I             | 500 3.142 <i>
*             | 500 3.142*<i>
ZA            | 500 3.142*<i> 35 10
*             | 500 3.142*<i> 350
9+            | 500 3.142*<i> 359
(             | 3.142*<i> 359 500
%             | 3.142*<i> 0.718
2+            | 3.142*<i> 2.718
#E            | 3.142*<i>     ; E <- 2.718
1II0          | 3.142*<i> 1 <i> <i> 0
e             | 3.142*<i> 1 <i> <i>==0
1+            | 3.142*<i> 1 <i> (<i>==0)+1

```

`ø` then goes to the next Nth line. When `0` is input, this goes straight to line 2. Otherwise, we go to line 1.

## Line 1

```
1-)E*(:0eø

```

This multiples E `i` times, which is `e^i`. We decrement the counter (initially `I`), multiply the STOS (our running `e` power) by E, go back to the counter, and do this (`i'` is the current counter):

```
Sequence read | Stack (partial)
              | i'
:             | i' i'
0             | i' i' 0
e             | i' i'==0

```

`ø` then does one of two things. If the counter is not 0, then we go to the "next" 0th line, i.e., the beginning of the current line. If it is zero, then `0e` yields 1, and goes to the next line.

## Line 2

```
$+n~

```

`$` drops the counter (ON THE FLOOR!). `+` adds the top two results, `n` outputs that number, and `~` quits the program.

Case 1: input is 0. The TOS is 1 ("e^0") and the STOS is 0 (pi\*0). Adding them yields the correct result.

Case 2: input is not 0. The result is as you might expect.

---
Tags: code-golf, math, number, pi
---


# Question
Title: Create your own Gym Exercise and follow along irl
Let's do an exercise together, shall we? Simply follow the movements of the stickman. What stickman you ask? The one we are about to create!

Make a program that allows for a string-input only containing integers, and outputs the following nine stick-figures with an interval in between:

```
 @  \@/ |@_ _@| @/   \@ |@| \@\ /@/
/|\  |   |   |   |   |   |   |   |
/ \ / \ / \ / \ /|\ /|\ / \ / \ / \
 1   2   3   4   5   6   7   8   9

```

This will result in an animation, which we can then follow along irl.

Here is an example of the output created when the input is "`123245762`":

**Some rules:**

* This is tagged , so shortest code in bytes wins
* The input is a `string` only containing `[1-9]` with a length potentially varying from 2 to 100 characters \**
* The animation must be an endless loop
* The interval time must be 750 ms
* No duplicated adjacent integers are allowed in the input - this also includes the first and last integers of the input (see the seventh and eight test cases) \**

\** How it fails in case of invalid input is completely up to you, but **it should be clear that it fails**. It could throw an exception; simply return at the start; reboot your PC; delete it's own source-/compile-code; hack into the military and shoots a rocket to the compiling GPS-location. Your call. **EDIT:** It's not allowed to simply display a (correct / half) animation as failing input. It must be clear that something is wrong with the input for the failing testcases below. Thanks to *@user81655* for bringing this to my attention, hence the edit.

**Subrules:**

* Please post the gif for one of the (non-failing) test cases below in your answer, which you can make very easy with the following program: screentogif.codeplex.com (Any other gif-creating program is also allowed of course.)
* ***Bonus points if you actually do the exercise alongside the animation irl when it's finished. ;)***

**Correct testcases:**

1. `123245762`
2. `65`
3. `121234346565879879132418791576`

**Failing testcases:**

4. `2` // Too few characters
5. `7282918274959292747383785189478174826894958127476192947512897571298593912374857471978269591928974518735891891723878` // Too much characters
6. `1232405762` // Containing invalid input (the `0`)
7. `112212` // Fails because of the `11` and `22` present
8. `1232457621` // Fails because of the starting and leading `1`

# Answer
## Pyth, 114 bytes

```
.V0j@cv.Z"xÚí» À0DW¹NM@+Üñ\">íÂA¸êÄÓw»`3±2þ&'NövfAé8é~0,p'ÆìÞúr_'¥,d!YÈBíéqs"3tv@zb.d.75

```

Try it here

(No pausing, non-infinite)
> 0 votes

# Answer
# SpecBAS - 387 bytes

```
1 DIM m$=" @"#13"/|\"#13"/ \","\@/"#13" |"#13"/ \","|@_"#13" |"#13"/ \","_@|"#13" |"#13"/ \","@/"#13" |"#13"/|\"," \@"#13" |"#13"/|\","|@|"#13" |"#13"/ \","\@\"#13" |"#13"/ \","/@/"#13" |"#13"/ \"
2 INPUT a$: o=0
3 IF LEN a$<2 OR LEN a$>100 THEN 10
4 FOR i=1 TO LEN a$
5 n=VAL(a$(i))
6 IF n=0 OR n=o THEN 10
7 CLS : ?m$(n): o=n: WAIT 750
8 NEXT i
9 GO TO 4
10 CLS : ?" @"#13"-O-"#13"/ \"#13"FAT"

```

Keeps looping until you press ESC. Failure to exercise properly (incorrect input - in this example a 0 as one of the steps) leads to fatness. The GIF loops, in the program it just stops at that point.

`#13` is the SpecBAS equivalent to `\n` and lets you include line feed in strings.
> 4 votes

# Answer
## JavaScript (ES6), 165 bytes

```
f=s=>{n=s[0];e.textContent=' @ \\@/|@__@|@/  \\@|@|\\@\\/@/'.substr(n*3-3,3)+(n>1?`
 |
`:`
/|\\
`)+(n<5|n>6?'/ \\':'/|\\');s=s.slice(1)+n;s[0]-n&&setTimeout(f,750,s)}
f("123245762")
```

```
<pre id=e>
```
> 2 votes

# Answer
# JavaScript (ES6), 210 bytes

```
s=>setInterval(_=>(c=console).clear(i=0)&c.log(`, @
/|\\
/ \\,\\@/
 |
/ \\,|@_
 |
/ \\,_@|
 |
/ \\,@/
 |
/|\\, \\@
 |
/|\\,|@|
 |
/ \\,\\@\\
 |
/ \\,/@/
 |
/ \\`.split`,`[s[i++%s.length]]),750)

```
> 1 votes

# Answer
# Java 8, ~~663~~ ~~636~~ ~~634~~ ~~631~~ ~~596~~ ~~355~~ ~~354~~ 343 bytes

Just for the lols I tried to make the program in Java. ~~Admittedly I'm pretty bad at golfing and regexes, so it can most likely be golfed (a lot?) more. Nevertheless, here it is in Java 7.~~
Now almost two years later and I almost halved the code in Java 8. Why did I ever made those rules about validating the input and requiring a full program, though... \>.\> I hate my past self now..

```
interface M{static void main(String[]a)throws Exception{for(;a[0].matches("[1-9]{2,100}")&!a[0].matches(".*(.)\\2.*|(.).*\\1");)for(int c:a[0].getBytes()){c-=48;System.out.printf("%s%n%s%n%s%n",c<2?" @ ":c<3?"\\@/":c<4?"|@_":c<5?"_@|":c<6?"@/ ":c<7?" \\@":c<8?"|@|":c<9?"\\@\\":"/@/",c<2?"/|\\":" | ",c%7>4?"/|\\":"/ \\");Thread.sleep(750);}}}

```

-11 bytes thanks to *@ceilingcat*.

**Explanation:**

Try it online. (After it has timed out after 60 sec.)

```
interface M{                     // Class
  static void main(String[]a)    //  Mandatory main-method
      throws Exception{          //    Required throws for the `Thread.sleep`
    for(;a[0].matches("[1-9]{2,100}")
                                 //   Validate 2-100 integers only containing 1-9
         &!a[0].matches(".*(.)\\2.*|(.).*\\1")
                                 //   Validate no adjacent duplicated char (with wrap-around)
        ;)                       //   And start an infinite loop if it's valid:
      for(int c:a[0].getBytes()){//    Inner loop over the characters of the input:
        c-=48;                   //     Convert the character-code to an integer
        System.out.printf("%s%n%s%n%s%n",
                                 //     Print:
          c<2?" @ ":c<3?"\\@/":c<4?"|@_":c<5?"_@|":c<6?"@/ ":c<7?" \\@":c<8?"|@|":c<9?"\\@\\":"/@/",
                                 //      The top part of the stick figure
          c<2?"/|\\":" | ",      //      The middle part of the stick figure
          c%7>4?"/|\\":"/ \\");  //      The bottom part of the stick figure
        Thread.sleep(750);}}}    //     Sleep 750 ms

```

**Gif:**
*(Note: Old gif, since it's clearly jdk1.8+ now.)*
> 1 votes

# Answer
# Mathematica, 252 bytes

```
i=0;Dynamic[Uncompress["1:eJxTTMoPSuNkYGAoZgESPpnFJcFCQIaCQ4yBoZF+TUwMmFaIiQELx8Q46IMEFGrgwoJA4RqHeCyi8Q41aKICQFEUA2qg5gIlHdCEIeaimyAMcQTEWWj26aO7DQDaqDEh"][[FromDigits[#~StringTake~{i=i~Mod~StringLength@#+1}]]],UpdateInterval->3/4,TrackedSymbols->{}]&

```

Would be nice if someone could create a GIF. Run in a notebook.
> 0 votes

# Answer
# Python3, 338 bytes

```
import os,time
p=" @ \n/|\\\n/ \\","\\@/\n | \n/ \\","|@_\n | \n/ \\","_@|\n | \n/ \\","@/ \n | \n/|\\"," \\@\n | \n/|\\","|@|\n | \n/ \\","\\@\\\n | \n/ \\","/@/\n | \n/ \\"
i=input()
for j in range(len(i)):(i[j]in"123456789"and i[j]!=i[(j+1)%len(i)])or exit()
while 1:[[time.sleep(0.75),os.system("clear"),print(p[int(j)-1])]for j in i]

```
> 0 votes

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


title: Snakify a String

text:
# Question
Title: Snakify a String
A snakified string looks like this:

```
T AnE eOf ifi ing
h s x l A k e r
isI amp Sna dSt

```

## Your Task

Take a string `s` and a size `n`, then output the snakified string. The inputs `ThisIsAnExampleOfaSnakifiedString` and `3` would produce the example above.

## Specifications

* `s` will only contain ASCII characters between code points 33 and 126 inclusive (no spaces or newlines).
* `s` will be between 1 and 100 characters long.
* `n` is an integer representing the size of each output string segment. Each line of characters (up/down or left/right) that make up the curves in the "snake" is `n` characters long. See the test cases for examples.
* `n` will be between 3 and 10 inclusive.
* The output string always starts pointing downwards.
* Trailing spaces on each line are allowed.
* Trailing newlines at the end of the output are also allowed.
* Leading spaces are not allowed.
* means shortest code in bytes wins.

## Test Cases

```
a 3

a

----------

Hello,World! 3

H Wor
e , l
llo d!

----------

ProgrammingPuzzlesAndCodeGolf 4

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

----------

IHopeYourProgramWorksForInputStringsWhichAre100CharactersLongBecauseThisTestCaseWillFailIfItDoesNot. 5

I   gramW   tStri   100Ch   gBeca   CaseW   DoesN
H   o   o   u   n   e   a   n   u   t   i   t   o
o   r   r   p   g   r   r   o   s   s   l   I   t
p   P   k   n   s   A   a   L   e   e   l   f   .
eYour   sForI   Which   cters   ThisT   FailI

----------

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

!        <=>?@ABCDE        `abcdefghi
"        ;        F        _        j
#        :        G        ^        k
$        9        H        ]        l
%        8        I        \        m
&        7        J        [        n
'        6        K        Z        o        ~
(        5        L        Y        p        }
)        4        M        X        q        |
*+,-./0123        NOPQRSTUVW        rstuvwxyz{

```

# Answer
> 9 votes
# Pyth, ~~48~~ ~~45~~ ~~44~~ ~~43~~ 42 bytes

```
=Y0juXGZX@G~+Z-!J%/HtQ4q2J~+Y%J2@zHlzm*;lz

```

Try it online.

This approach does the same trailing whitespace abuse as the Ruby answer.

# Answer
> 13 votes
# Ruby, 87 bytes

```
->s,n{p=0
a=(' '*(w=s.size)+$/)*n
w.times{|i|a[p]=s[i];p+=[w+1,1,-w-1,1][i/(n-1)%4]}
a}

```

Some minor abuse of the rule `Trailing spaces on each line are allowed.` Each line of output is `w` characters long, plus a newline, where `w` is the length of the original string, i.e. long enough to hold the whole input. Hence there is quite a lot of unnecessary whitespace to the right for large `n`.

**Ungolfed in test program**

```
f=->s,n{
  p=0                            #pointer to where the next character must be plotted to
  a=(' '*(w=s.size)+$/)*n        #w=length of input. make a string of n lines of w spaces, newline terminated
  w.times{|i|                    #for each character in the input (index i)
    a[p]=s[i]                    #copy the character to the position of the pointer
    p+=[w+1,1,-w-1,1][i/(n-1)%4] #move down,right,up,right and repeat. change direction every n-1 characters
  }
a}                               #return a

puts $/,f['a',3]

puts $/,f['Hello,World!',3]

puts $/,f['ProgrammingPuzzlesAndCodeGolf',4]

puts $/,f['IHopeYourProgramWorksForInputStringsWhichAre100CharactersLongBecauseThisTestCaseWillFailIfItDoesNot.',5]

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

```

# Answer
> 7 votes
## JavaScript (ES6), 143 bytes

```
(s,n)=>[...s].map((c,i)=>(a[x][y]=c,i/=n)&1?y++:i&2?x--:x++,a=[...Array(n--)].map(_=>[]),x=y=0)&&a.map(b=>[...b].map(c=>c||' ').join``).join`\n`

```

Where `\n` represents a literal newline. Ungolfed:

```
function snakify(string, width) {
    var i;
    var result = new Array(width);
    for (i = 0; i < width; i++) result[i] = [];
    var x = 0;
    var y = 0;
    for (i = 0; i < string.length; i++) {
       result[x][y] = string[i];
       switch (i / (width - 1) & 3) {
       case 0: x++; break;
       case 1: y++; break;
       case 2: x--; break;
       case 3: y++; break;
    }
    for (i = 0; i < width; i++) {
        for (j = 0; j < r[i].length; j++) {
            if (!r[i][j]) r[i][j] = " ";
        }
        r[i] = r[i].join("");
    }
    return r.join("\n");
}

```

# Answer
> 7 votes
## Pyth, ~~85~~ ~~74~~ 59 bytes

~~`Kl@Q0J0=Y*]d-+*@Q1K@Q1 1FNr1@Q1=XY-+*KNN1b;VK=XYJ@@Q0N=+J@[+K1 1-_K1 1).&3/N-@Q1 1;sY`~~

~~`=G@Q1=H@Q0KlHJ0=Y*]dt+*GKGFNr1G=XYt+*KNNb;VK=XYJ@HN=+J@[hK1t_K1).&3/NtG;sY`~~

```
Klz=Ym;+*QKQVQ=XYt+*KhNhNb;VK=XYZ@zN=+Z@[hK1_hK1).&3/NtQ;sY

```

Thanks to @FryAmTheEggman for greatly helping me !

Golfed as much as I could. Try it here ! For some reason, line wrapping make the output weird. You may want to have a look at the output on full page

## Explanation

Breathe a second, and focus. This can be broken down in three sections, like almost any "classic" algorithm.

### The first section

It's where variables are initialized. It can be splitted into two parts :

```
Klz=Ym;+*QKQ
Klz                Assign len(input[0]) to K. (length of input String)
   =Ym;+*QKQ       Assign an empty list to Y of length K*input[1]-input[1]-1, where input[1] is the size of the snake
                   (thus the height of the final string)

```

the second part :

```
VQ=XYt+*KhNhNb;
VQ                       For N in range(0, input[1]), where input[1] is the size of the snake
  =                        Assign to Y. Y is implicit, it is the last variable we used.
   XYt+*KhNhNb               Y[K*N+N-1]="\n". Can be broken down in four parts :
   X                           Replace function. X <A: list> <B: int> <C: any> is A[B]=C
    Y                          A: The array we initialized in the first section.
     t+*KhNhN                  B: K*(N+1)+N+1 (N is the for loop variable)
             b                 C: Newline character ("\n")
              ;          End the loop.

```

### The second section

It contains the actual logic.

```
VK=XYZ@zN=+Z@[hK1_hK1).&3/NtQ;
VK                                         For N in range(0, K), where K is the length of the input string (see first section)
  =                                          Assign to Y. Y is implicit, it is the last variable we used.
   XYZ@zN                                    Same as in section 2. This is a replacement function. Y[Z] = input[0][N]. Z is initially 0.
         =+Z@[hK1_hK1).&3/NtQ                Again this can be broken down :
         =+Z                                   Add to Z
             [hK1_hK1)                         Array containing directions. Respectively [K+1, 1, -K-1, 1]
            @         .&3/NtQ                  Lookup in the array, on index .&3/N-@Q1 1:
                      .&3                        Bitwise AND. .& <int> <int>
                         /NtQ                    (input[1]-1)/N, where input[1] is the size of the snake
                             ;             End the loop

```

### The third section

This is the output part. Not really interesting...

```
sY    Join the array Y. Implicitly print.

```

## BONUS

I wrote the pyth program from this python script.

```
input=["ThisIsAnExampleOfASnakifiedString", 4];
width=len(input[0]);
height=input[1];
pointer=0;
directions = [width+1,1,-width-1,1] #Respectively Down, right, up, right (left is replaced by right because of snake's nature. Doesn't go left).
output=[' ' for i in range(0, width*height+height-1)];
for N in range(1, height):
    output[width*N+N-1]="\n";
for N in range(0, len(input[0])):
    output[pointer]=input[0][N];
    pointer+=directions[3&(N/(height-1))];
print "".join(output);

```

# Answer
> 5 votes
# JavaScript (ES6), 122 bytes

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

// --- Solution ---
s=>n=>[...s].map((c,i)=>(a[p]=c,p+=[l+1,1,-l-1,1][i/n%4|0]),p=0,a=[...(" ".repeat(l=s.length)+`
`).repeat(n--)])&&a.join``
// ----------------

)("IHopeYourProgramWorksForInputStringsWhichAre100CharactersLongBecauseThisTestCaseWillFailIfItDoesNot.")(5))
```

Same algorithm as @LevelRiverSt's answer.

# Answer
> 4 votes
# C, 138 bytes

```
char*h[]={"\e[B\e[D","","\e[A\e[D",""},t[999];i;main(n){system("clear");for(scanf("%s%d",t,&n),--n;t[i];++i)printf("%c%s",t[i],h[i/n%4]);}

```

This uses ANSI escapes. Works in linux terminal.

Ungolfed:

```
char*h[]={"\e[B\e[D","","\e[A\e[D",""},
    /* cursor movement - h[0] moves the cursor one down and one left,
    h[2] moves the cursor one up and one left. */
t[999];i;
main(n){
    system("clear");
    for(scanf("%s%d",t,&n),--n;t[i];++i)
        printf("%c%s",t[i],h[i/n%4]);
}

```

# Answer
> 1 votes
# JavaScript (ES6), 131

Algorithm: mapping the position `x,y` in output to the index in the input string, somehow like this (unrelated) answer.

I borrowed from @LevelRiverSt the trick of keeping the horizontal width equal to the input length.

```
a=>m=>eval('for(--m,t=y=``;y<=m;++y,t+=`\n`)for(x=0;a[x];)t+=a[2*(x-x%m)+((h=x++%(2*m))?h-m?!y&h>m?h:y<m|h>m?NaN:m+h:m-y:y)]||`.`')

```

**Less golfed**

This was the first working draft before golfing

```
f=(a,n)=>{
  l=a.length
  m=n-1
  s=m*2 // horizontal period

  b=-~(~-l/s)*m // total horizontal len, useless in golfed version
  t=''
  for(y=0;y<n;y++)
  {
    for(x=0;x<b;x++)
    {
      k = x / m | 0
      h = x % s
      if (h ==0 )
        c=k*s+y
      else if (h == m)
        c=k*s+m-y
      else if (y == 0 && h>m)
        c=k*s+h
      else if (y == m && h<m)
        c=k*s+m+h
      else
        c=-1
      t+=a[c]||' '
    }
    t+='\n'
  }
  return t
}

```

**Test**

```
F=a=>m=>eval('for(--m,t=y=``;y<=m;++y,t+=`\n`)for(x=0;a[x];)t+=a[2*(x-x%m)+((h=x++%(2*m))?h-m?!y&h>m?h:y<m|h>m?NaN:m+h:m-y:y)]||` `')

function test()
{
  var n=+N.value
  var s=S.value
  O.textContent=F(s)(n)
}

test()
```

```
#S {width:80%}
#N {width:5%}
```

```
<input id=N value=5 type=number oninput='test()'>
<input id=S 5 oninput='test()'
value='IHopeYourProgramWorksForInputStringsWhichAre100CharactersLongBecauseThisTestCaseWillFailIfItDoesNot.'>
<pre id=O></pre>
```

# Answer
> 0 votes
## Pyth, 122 bytes

```
=k@Q0J-@Q1 1K*4J=T*@Q1[*lkd;Vlk=Z+*%NJ/%N*J2J*/N*J2J=Y.a-+**/%N*J2J!/%NK*J2J*%NJ!/%N*J2J**!/%N*J2J/%NK*J2J XTYX@TYZ@kN;jbT

```

I've made a formula to calculate the x, y positions of each character based on the segment size / modulo, but they got larger than I expected :c

Explanation:

```
=k@Q0                                                                                # Initialize var with the text
     J-@Q1 1                                                                                # Initialize var with the segment size (minus 1)
            K*4J                                                                                # Initialize var with the "block" size (where the pattern start to repeat)
                =T*@Q1[*lkd;                                                                                # Initialize output var with an empty array of strings
                            Vlk                                                                                # Interate over the text
                               =Z+*%NJ/%N*J2J*/N*J2J                                                                      # Matemagics to calculate X position
                                                    =Y.a-+**/%N*J2J!/%NK*J2J*%NJ!/%N*J2J**!/%N*J2J/%NK*J2J                # Matemagics to calculate Y position
                                                                                XTYX@TYZ@kN;    # Assign the letter being iterated at x,y in the output
                                                                                jbT # Join with newlines and print the output

```

Test here

For the Math formulas, I used mod to generate 0/1 flags and then multiplied by a factor based on the input `n`, added the spreadsheet with each step on the snippet bellow

```
td{padding-top:1px;padding-right:1px;padding-left:1px;color:black;font-size:11.0pt;font-weight:400;font-style:normal;text-decoration:none;font-family:Calibri,sans-serif}.x1{text-align:general;vertical-align:bottom;white-space:nowrap}.x2{text-align:general;vertical-align:bottom;border-right:.5pt solid gray;border-bottom:.5pt solid gray;border-left:.5pt solid gray;white-space:nowrap}.x3{text-align:general;vertical-align:bottom;border-top:.5pt solid gray;border-right:.5pt solid gray;border-bottom:.5pt solid gray;border-left:.5pt solid windowtext;white-space:nowrap}.x4{text-align:general;vertical-align:bottom;border:.5pt solid gray;white-space:nowrap}.x5{text-align:general;vertical-align:bottom;border:.5pt solid gray;background:#c5d9f1;white-space:nowrap}.x6{text-align:general;vertical-align:bottom;border:.5pt solid gray;background:#ebf1de;white-space:nowrap}.x7{text-align:general;vertical-align:bottom;border-top:.5pt solid gray;border-right:.5pt solid windowtext;border-bottom:.5pt solid gray;border-left:.5pt solid gray;background:#ebf1de;white-space:nowrap}.x8{text-align:general;vertical-align:bottom;border-top:.5pt solid gray;border-right:.5pt solid gray;border-bottom:.5pt solid gray;border-left:.5pt solid windowtext;background:#d9d9d9;white-space:nowrap}.x9{text-align:general;vertical-align:bottom;border:.5pt solid gray;background:#d9d9d9;white-space:nowrap}.x10{text-align:right;vertical-align:bottom;border:.5pt solid gray;white-space:nowrap}.x11{text-align:general;vertical-align:bottom;border-top:.5pt solid gray;border-right:.5pt solid gray;border-bottom:.5pt solid windowtext;border-left:.5pt solid windowtext;background:#d9d9d9;white-space:nowrap}.x12{text-align:general;vertical-align:bottom;border-top:.5pt solid gray;border-right:.5pt solid gray;border-bottom:.5pt solid windowtext;border-left:.5pt solid gray;background:#d9d9d9;white-space:nowrap}.x13{text-align:right;vertical-align:bottom;border-top:.5pt solid gray;border-right:.5pt solid gray;border-bottom:.5pt solid windowtext;border-left:.5pt solid gray;white-space:nowrap}.x14{text-align:general;vertical-align:bottom;border-top:.5pt solid gray;border-right:.5pt solid gray;border-bottom:.5pt solid windowtext;border-left:.5pt solid gray;white-space:nowrap}.x15{text-align:general;vertical-align:bottom;border-top:.5pt solid gray;border-right:.5pt solid gray;border-bottom:.5pt solid windowtext;border-left:.5pt solid gray;background:#c5d9f1;white-space:nowrap}.x16{text-align:general;vertical-align:bottom;border-top:.5pt solid gray;border-right:.5pt solid gray;border-bottom:.5pt solid windowtext;border-left:.5pt solid gray;background:#ebf1de;white-space:nowrap}.x17{text-align:general;vertical-align:bottom;border-top:.5pt solid gray;border-right:.5pt solid windowtext;border-bottom:.5pt solid windowtext;border-left:.5pt solid gray;background:#ebf1de;white-space:nowrap}.x18{text-align:general;vertical-align:bottom;border-right:.5pt solid gray;border-bottom:0;border-left:.5pt solid gray;white-space:nowrap}.x19{text-align:general;vertical-align:bottom;border-right:.5pt solid gray;border-bottom:.5pt solid gray;border-left:.5pt solid windowtext;white-space:nowrap}.x20{text-align:general;vertical-align:bottom;border-right:.5pt solid gray;border-bottom:.5pt solid gray;border-left:.5pt solid gray;background:#c5d9f1;white-space:nowrap}.x21{text-align:general;vertical-align:bottom;border-right:.5pt solid gray;border-bottom:.5pt solid gray;border-left:.5pt solid gray;background:#ebf1de;white-space:nowrap}.x22{text-align:general;vertical-align:bottom;border-right:.5pt solid windowtext;border-bottom:.5pt solid gray;border-left:.5pt solid gray;background:#ebf1de;white-space:nowrap}.x23{text-align:center;vertical-align:bottom;border:.5pt solid windowtext;white-space:nowrap}.x24{text-align:center;vertical-align:bottom;border-right:.5pt solid windowtext;border-bottom:0;border-left:.5pt solid windowtext;white-space:nowrap}
```

```
<table style="border-collapse:collapse;table-layout:fixed;width:761pt" border="0" cellpadding="0" cellspacing="0" width="1015">
<colgroup><col style="width:16pt" width="21">
<col style="mso-width-alt:2742;width:56pt" span="2" width="75">
<col style="width:23pt" width="31">
<col style="width:50pt" width="67">
<col style="width:60pt" width="80">
<col style="width:85pt" width="113">
<col style="width:26pt" width="35">
<col style="width:41pt" width="54">
<col style="width:29pt" width="39">
<col style="width:41pt" width="55">
<col style="width:104pt" width="138">
<col style="width:29pt" width="39">
<col style="width:41pt" width="54">
<col style="width:65pt" width="87">
<col style="width:39pt" width="52">
</colgroup><tbody><tr style="height:15.0pt" height="20">
<td class="x23" style="height:15.0pt;width:16pt" width="21" height="20">d</td>
<td class="x23" style="width:56pt" width="75">e</td>
<td class="x23" style="width:56pt" width="75">f</td>
<td class="x24" style="width:23pt" width="31"> </td>
<td class="x23" style="width:50pt" width="67">h</td>
<td class="x23" style="width:60pt" width="80">i</td>
<td class="x23" style="width:85pt" width="113">j</td>
<td class="x23" style="width:26pt" width="35">k</td>
<td class="x23" style="width:41pt" width="54">l</td>
<td class="x23" style="width:29pt" width="39">m</td>
<td class="x23" style="width:41pt" width="55">n</td>
<td class="x23" style="width:104pt" width="138">o</td>
<td class="x23" style="width:29pt" width="39">p</td>
<td class="x23" style="width:41pt" width="54">q</td>
<td class="x23" style="width:65pt" width="87">r</td>
<td class="x23" style="width:39pt" width="52">s</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x23" style="height:15.0pt" height="20">i</td>
<td class="x23">expected x</td>
<td class="x23">expected y</td>
<td class="x24" style=""> </td>
<td class="x23">pos % seg</td>
<td class="x23">pos/(seg*2)</td>
<td class="x23">pos%(seg*2)/seg</td>
<td class="x23">not j</td>
<td class="x23">seg*i+h</td>
<td class="x23">i*seg</td>
<td class="x23">j*l+k*m</td>
<td class="x23">pos%(seg*4)/(seg*2)</td>
<td class="x23">not o</td>
<td class="x23">j*p*seg</td>
<td class="x23">abs(o*seg-h)</td>
<td class="x23">q*j+r*k</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x19" style="height:15.0pt" align="right" height="20">0</td>
<td class="x2" style="" align="right">0</td>
<td class="x2" style="" align="right">0</td>
<td class="x18" style=""> </td>
<td class="x2" style="" align="right">0</td>
<td class="x2" style="" align="right">0</td>
<td class="x2" style="" align="right">0</td>
<td class="x2" style="" align="right">1</td>
<td class="x2" style="" align="right">0</td>
<td class="x20" style="" align="right">0</td>
<td class="x21" style="" align="right">0</td>
<td class="x2" style="" align="right">0</td>
<td class="x2" style="" align="right">1</td>
<td class="x2" style="" align="right">0</td>
<td class="x20" style="" align="right">0</td>
<td class="x22" style="" align="right">0</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x3" style="height:15.0pt;border-top:none" align="right" height="20">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x18" style=""> </td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">1</td>
<td class="x5" align="right">0</td>
<td class="x6" align="right">0</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">1</td>
<td class="x7" align="right">1</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x3" style="height:15.0pt;border-top:none" align="right" height="20">2</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">2</td>
<td class="x18" style=""> </td>
<td class="x4" align="right">2</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">2</td>
<td class="x5" align="right">0</td>
<td class="x6" align="right">0</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">2</td>
<td class="x7" align="right">2</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x8" style="height:15.0pt;border-top:none" align="right" height="20">3</td>
<td class="x9" align="right">0</td>
<td class="x9" align="right">3</td>
<td class="x18" style=""> </td>
<td class="x10">0</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">0</td>
<td class="x4" align="right">0</td>
<td class="x6" align="right">0</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x5" align="right">3</td>
<td class="x4" align="right">0</td>
<td class="x7" align="right">3</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x8" style="height:15.0pt;border-top:none" align="right" height="20">4</td>
<td class="x9" align="right">1</td>
<td class="x9" align="right">3</td>
<td class="x18" style=""> </td>
<td class="x10">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x6" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x5" align="right">3</td>
<td class="x4" align="right">1</td>
<td class="x7" align="right">3</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x8" style="height:15.0pt;border-top:none" align="right" height="20">5</td>
<td class="x9" align="right">2</td>
<td class="x9" align="right">3</td>
<td class="x18" style=""> </td>
<td class="x10">2</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">2</td>
<td class="x4" align="right">0</td>
<td class="x6" align="right">2</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x5" align="right">3</td>
<td class="x4" align="right">2</td>
<td class="x7" align="right">3</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x3" style="height:15.0pt;border-top:none" align="right" height="20">6</td>
<td class="x4" align="right">3</td>
<td class="x4" align="right">3</td>
<td class="x18" style=""> </td>
<td class="x10">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">3</td>
<td class="x5" align="right">3</td>
<td class="x6" align="right">3</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">3</td>
<td class="x7" align="right">3</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x3" style="height:15.0pt;border-top:none" align="right" height="20">7</td>
<td class="x4" align="right">3</td>
<td class="x4" align="right">2</td>
<td class="x18" style=""> </td>
<td class="x10">1</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">4</td>
<td class="x5" align="right">3</td>
<td class="x6" align="right">3</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">2</td>
<td class="x7" align="right">2</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x3" style="height:15.0pt;border-top:none" align="right" height="20">8</td>
<td class="x4" align="right">3</td>
<td class="x4" align="right">1</td>
<td class="x18" style=""> </td>
<td class="x10">2</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">5</td>
<td class="x5" align="right">3</td>
<td class="x6" align="right">3</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">1</td>
<td class="x7" align="right">1</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x8" style="height:15.0pt;border-top:none" align="right" height="20">9</td>
<td class="x9" align="right">3</td>
<td class="x9" align="right">0</td>
<td class="x18" style=""> </td>
<td class="x10">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">3</td>
<td class="x4" align="right">3</td>
<td class="x6" align="right">3</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">0</td>
<td class="x4" align="right">3</td>
<td class="x7" align="right">0</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x8" style="height:15.0pt;border-top:none" align="right" height="20">10</td>
<td class="x9" align="right">4</td>
<td class="x9" align="right">0</td>
<td class="x18" style=""> </td>
<td class="x10">1</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">4</td>
<td class="x4" align="right">3</td>
<td class="x6" align="right">4</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">0</td>
<td class="x4" align="right">2</td>
<td class="x7" align="right">0</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x8" style="height:15.0pt;border-top:none" align="right" height="20">11</td>
<td class="x9" align="right">5</td>
<td class="x9" align="right">0</td>
<td class="x18" style=""> </td>
<td class="x10">2</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">5</td>
<td class="x4" align="right">3</td>
<td class="x6" align="right">5</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x7" align="right">0</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x3" style="height:15.0pt;border-top:none" align="right" height="20">12</td>
<td class="x4" align="right">6</td>
<td class="x4" align="right">0</td>
<td class="x18" style=""> </td>
<td class="x10">0</td>
<td class="x4" align="right">2</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">6</td>
<td class="x5" align="right">6</td>
<td class="x6" align="right">6</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">0</td>
<td class="x7" align="right">0</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x3" style="height:15.0pt;border-top:none" align="right" height="20">13</td>
<td class="x4" align="right">6</td>
<td class="x4" align="right">1</td>
<td class="x18" style=""> </td>
<td class="x10">1</td>
<td class="x4" align="right">2</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">7</td>
<td class="x5" align="right">6</td>
<td class="x6" align="right">6</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">1</td>
<td class="x7" align="right">1</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x3" style="height:15.0pt;border-top:none" align="right" height="20">14</td>
<td class="x4" align="right">6</td>
<td class="x4" align="right">2</td>
<td class="x18" style=""> </td>
<td class="x10">2</td>
<td class="x4" align="right">2</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">8</td>
<td class="x5" align="right">6</td>
<td class="x6" align="right">6</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">2</td>
<td class="x7" align="right">2</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x8" style="height:15.0pt;border-top:none" align="right" height="20">15</td>
<td class="x9" align="right">6</td>
<td class="x9" align="right">3</td>
<td class="x18" style=""> </td>
<td class="x10">0</td>
<td class="x4" align="right">2</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">6</td>
<td class="x4" align="right">6</td>
<td class="x6" align="right">6</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x5" align="right">3</td>
<td class="x4" align="right">0</td>
<td class="x7" align="right">3</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x8" style="height:15.0pt;border-top:none" align="right" height="20">16</td>
<td class="x9" align="right">7</td>
<td class="x9" align="right">3</td>
<td class="x18" style=""> </td>
<td class="x10">1</td>
<td class="x4" align="right">2</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">7</td>
<td class="x4" align="right">6</td>
<td class="x6" align="right">7</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x5" align="right">3</td>
<td class="x4" align="right">1</td>
<td class="x7" align="right">3</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x8" style="height:15.0pt;border-top:none" align="right" height="20">17</td>
<td class="x9" align="right">8</td>
<td class="x9" align="right">3</td>
<td class="x18" style=""> </td>
<td class="x10">2</td>
<td class="x4" align="right">2</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">8</td>
<td class="x4" align="right">6</td>
<td class="x6" align="right">8</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x5" align="right">3</td>
<td class="x4" align="right">2</td>
<td class="x7" align="right">3</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x3" style="height:15.0pt;border-top:none" align="right" height="20">18</td>
<td class="x4" align="right">9</td>
<td class="x4" align="right">3</td>
<td class="x18" style=""> </td>
<td class="x10">0</td>
<td class="x4" align="right">3</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">9</td>
<td class="x5" align="right">9</td>
<td class="x6" align="right">9</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">3</td>
<td class="x7" align="right">3</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x3" style="height:15.0pt;border-top:none" align="right" height="20">19</td>
<td class="x4" align="right">9</td>
<td class="x4" align="right">2</td>
<td class="x18" style=""> </td>
<td class="x10">1</td>
<td class="x4" align="right">3</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">10</td>
<td class="x5" align="right">9</td>
<td class="x6" align="right">9</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">2</td>
<td class="x7" align="right">2</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x3" style="height:15.0pt;border-top:none" align="right" height="20">20</td>
<td class="x4" align="right">9</td>
<td class="x4" align="right">1</td>
<td class="x18" style=""> </td>
<td class="x10">2</td>
<td class="x4" align="right">3</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">11</td>
<td class="x5" align="right">9</td>
<td class="x6" align="right">9</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">1</td>
<td class="x7" align="right">1</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x8" style="height:15.0pt;border-top:none" align="right" height="20">21</td>
<td class="x9" align="right">9</td>
<td class="x9" align="right">0</td>
<td class="x18" style=""> </td>
<td class="x10">0</td>
<td class="x4" align="right">3</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">9</td>
<td class="x4" align="right">9</td>
<td class="x6" align="right">9</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">0</td>
<td class="x4" align="right">3</td>
<td class="x7" align="right">0</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x8" style="height:15.0pt;border-top:none" align="right" height="20">22</td>
<td class="x9" align="right">10</td>
<td class="x9" align="right">0</td>
<td class="x18" style=""> </td>
<td class="x10">1</td>
<td class="x4" align="right">3</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">10</td>
<td class="x4" align="right">9</td>
<td class="x6" align="right">10</td>
<td class="x4" align="right">1</td>
<td class="x4" align="right">0</td>
<td class="x5" align="right">0</td>
<td class="x4" align="right">2</td>
<td class="x7" align="right">0</td>
</tr>
<tr style="height:15.0pt" height="20">
<td class="x11" style="height:15.0pt;border-top:none" align="right" height="20">23</td>
<td class="x12" align="right">11</td>
<td class="x12" align="right">0</td>
<td class="x18" style=""> </td>
<td class="x13">2</td>
<td class="x14" align="right">3</td>
<td class="x14" align="right">1</td>
<td class="x14" align="right">0</td>
<td class="x15" align="right">11</td>
<td class="x14" align="right">9</td>
<td class="x16" align="right">11</td>
<td class="x14" align="right">1</td>
<td class="x14" align="right">0</td>
<td class="x15" align="right">0</td>
<td class="x14" align="right">1</td>
<td class="x17" align="right">0</td>
</tr>
</tr>
</tbody></table>
```

# Answer
> 0 votes
# PHP, ~~127~~ ~~126~~ ~~124~~ ~~120~~ ~~119~~ ~~118~~ ~~117~~ ~~110~~ 106 bytes

Uses ISO-8859-1 encoding.

```
for(;($q=&$o[$y+=$d]||$q=~ÿ)&&~Ï^$q[$x+=!$d]=$argv[1][$a];$a++%($argv[2]-1)?:$d-=-!$y?:1)?><?=join(~õ,$o);

```

Run like this (`-d` added for aesthetics only):

```
php -r 'for(;($q=&$o[$y+=$d]||$q=~ÿ)&&~Ï^$q[$x+=!$d]=$argv[1][$a];$a++%($argv[2]-1)?:$d-=-!$y?:1)?><?=join(~õ,$o);' "Hello W0rld!" 3 2>/dev/null;echo

```

Ungolfed:

```
// Iterate over ...
for (
    ;
    // ... the characters of the input string. Prepend `0` so a 0 in the input
    // becomes truthy.
    0 . $char = $argv[1][$a];

    // Use modulo to determine the end of a stretch (where direction is
    // changed).
    // Change direction (`0` is right, `-1` is up and `1` is down). When
    // y coordinate is `0`, increment the direction, else decrement.
    $a++ % ($argv[2] - 1) ?: $direction += $y ? -1 : 1
)

    (
        // Increase or decrease y coordinate for direction -1 or 1 respectively.
        // Check whether the array index at new y coordinate is already set.
        $reference =& $output[$y += $direction] ||
        // If not, create it as a string (otherwise would be array of chars).
        // Null byte, won't be printed to prevent leading char.
        $reference = ~ÿ;

        // Increment x coordinate for direction 0. Set the output char at the
        // current coordinates to the char of the current iteration.
    ) & $reference[$x += !$direction] = $char;

// Output all lines, separated by a newline.
echo join(~õ, $output);

```

## Tweaks

* Saved a byte by using `<` instead of `!=`
* Saved 2 bytes by setting the string to `0` at first, so I don't have to prepend another `0` (in case the first output in a line was a `0`), yielding truthy `00`.
* Saved 4 bytes by using a reference instead of repeating `$o[$y]`
* Saved a byte by using modulo instead of `==` for comparing direction with 1 to change x coordinate
* Saved a byte by removing type cast `null` to `int` for string offset, as string offset is cast to int anyway
* Saved a byte by using short print tag
* Saved 7 bytes by improving the direction logic
* Saved 4 bytes by directly assigning the char to prevent intermediate `$c`

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


title: Is the path correct?

text:
# Question
Title: Is the path correct?
# Is the path correct ?

Given a string, your program must determine whether or not Alice can reach Bob, following the signs on the map. You must return a truthy or falsy value.

The input string will contain the following characters :

* (space) and `\n`. Only used for padding.
* `>`, `<`, `^`, `v`, are the "signs". They show the direction.
* `&`. Ignore next char, whatever it is (including spaces **and `Bob`**)
* `A` and `B` respectively Alice and Bob.

The map is a torus. If Alice reaches the end of a row, then she is teleported back to the beginning of that row. Same applies for columns.

## Examples

Given those examples as input, your program must return a truthy value (each input is separated with a `-` line):

```
A>B
-----------------
<BA
-----------------
A       B
-----------------
BA
-----------------
Av  >B
 >  ^
-----------------
Av
 B
-----------------
A>v
  >B
-----------------
A>v>   v>B
 v< > &<^
 > ^
-----------------
A>v>   v
 v< >B&<
 > ^
-----------------
A&<B
-----------------
A&B<
-----------------
<A       &B

```

For the following, your program must output a falsy value or nothing :

```
AvB
-----------------
A&B
-----------------
A><B
-----------------
A>v
 ^<B

```

## Path viewer

You can have a visual representation of the input here. Thanks to arnemart for this.

## Some rules

* The input may be padded with spaces to form a rectangle
* Initially, Alice goes straight forward (from above, she goes to the right)
* Your program ***should*** handle infinite loop cases (see Hint)
* `A` is not always the first character, as you may have seen, however, you may write a program that handles only input with `A` being the first char, but 20 bytes will be added to your score.
* A map (the input) is considered invalid in case there are other characters than those specified above. Your program won't have to handle them.
* This is , so shortest code in bytes wins.

## Hint

Your program will most likely be a loop, unless you find a more mathematical solution to this challenge. To handle infinite path, I recommend using a finite loop (e.g `for`) instead of a potentially infinite one (e.g `while`).

Therefore, the maximum iteration of the loop I can think of (I did not do any maths, any correction is welcome) is `(length of input)*4`

# Answer
> 2 votes
# C, 250 bytes

```
#define h x=(j+x-1+d%3)%j,i=(j+i+(d=='v')-(d==94))%j
char a[999],b[999];x,i,d=2,k,f;main(j){for(;gets(a+j*i);)j=strlen(a+j*i++);for(x=strchr(a,65)-a,i=x/j,x=x%j;!k*d;h)k|=b[f=j*i+x]&1<<d%5,b[f]|=1<<d%5,(f=a[f])&16?d=f:f&4?h:f&2?d=0:0;putchar(48+!k);}

```

This also requires that the input is padded with spaces.

Ungolfed:

```
#define h x=(j+x-1+d%3)%j,i=(j+i+(d=='v')-(d==94))%j
char a[999],b[999];x,i,d=2,k,f;
main(j){
 for(;gets(a+j*i);)j=strlen(a+j*i++); //read lines and determine line length
 for(x=strchr(a,65)-a,i=x/j,x=x%j;    //the current position is 'A'
 !k*d; //as long as we have not arrived at 'B'
       //and not travelled through the same cell and in the same direction twice
 h)    //advance one in the current direction
   k|=b[f=j*i+x]&1<<d%5,b[f]|=1<<d%5,  //if we have already travelled
                                       //through this cell in this direction
   (f=a[f])&16?d=f //change direction if this cell is one of <>^v
   :f&4?h          //if this cell is '&', advance one in the current direction
   :f&2?d=0:0;     //if we have reached 'B'
 putchar(48+!k);
}

```

# Answer
> 1 votes
# JavaScript (ES6), 176 bytes

```
m=>[...m,q=~m.length,l=~m.search`
`||q,a=m.search`A`,p=d=r=1].map(_=>(a+=d,a-=d*((a-l+1)%l?m[a]?0:q/l:~l),c=m[a],p=="&"?0:d={">":1,"<":-1,"^":l,v:-l}[c=="B"?r=0:c]||d,p=c))&&!r

```

## Explanation

Requires the input to be space-padded to form a rectangle (I hope this is OK).

```
var solution =

m=>[
    ...m,                           // iterate m.length times
    q=~m.length,                    // q = total length of m
    l=~m.search`\n`||q,             // l = line length
    a=m.search`A`,                  // a = index of Alice
    p=                              // p = previous character
    d=                              // d = direction offset
    r=1                             // r = result
  ].map(_=>(                        // loop
    a+=d,                           // move Alice
    a-=d*((a-l+1)%l?m[a]?0:q/l:~l), // wrap
    c=m[a],
    p=="&"?0:                       // do nothing after &
    d={">":1,"<":-1,"^":l,v:-l}     // set the new direction
      [c=="B"?r=0:c]                // if on Bob, r = 0
    ||d,
    p=c
  ))&&!r                            // return result

var testCasesTrue =
`A>B
-----------------
<BA
-----------------
A       B
-----------------
BA
-----------------
Av  >B
 >  ^
-----------------
Av
 B
-----------------
A>v
  >B
-----------------
A>v>   v>B
 v< > &<^
 > ^
-----------------
A>v>   v
 v< >B&<
 > ^
-----------------
A&<B
-----------------
A&B<
-----------------
<A       &B`
.split("\n-----------------\n");

var testCasesFalse =
`AvB
-----------------
A&B
-----------------
A><B
-----------------
A>v
 ^<B`
.split("\n-----------------\n");

var test = (cases, expected) => cases.map((t,i)=>++i+": "+(solution(t)==expected?"Pass":"Fail")).join`\n`;
document.write(`<pre>${test(testCasesTrue,true)}\n\n${test(testCasesFalse,false)}</pre>`);
```

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


title: Ponderous primality testing

text:
# Question
Title: Ponderous primality testing
One of my favorite algorithms was posted on Stack Overflow as an answer to What is the fastest way to generate prime number recursively?. In pseudocode:

## Nathan's algorithm

```
bool isPrime(int n):
    if (n < 2) return false
    for p in 2..n-1:
        if (isPrime(p) && n%p == 0) return false
    return true

```

This program is lovely because it doesn't have any wasted steps (in the author's words, "it's quite efficient because it only needs to test the prime factors") but still manages to take far longer than any reasonable algorithm. For example, compare the naive algorithm:

## Unoptimized trial division

```
bool isPrime(int n):
    if (n < 2) return false
    for p in 2..n-1:
        if (n%p == 0) return false
    return true

```

This requires 10005 ≈ 104 divisions to test 10007, the smallest 5-digit prime. By contrast, Nathan's algorithm takes more than 10370 divisions, making it 10366 times slower. If every electron was a 1-googol GHz computer, and this program had been running across all electrons in the universe since the Big Bang, it wouldn't even be close to 1% done.

---

The task is to write a program, in the language of your choice to test if a given number is prime as slowly as possible. The programs may not simply waste time by idling or executing unused loops; it should be clever in its sloth.

# Scoring

This is a , so the (valid) answer with the most votes wins. Golfing is neither required nor recommended. Suggested criteria for voting:

* Creativity: *How* does the program manage to do so much work?
* Originality: Does the program use a novel approach?
* Reasonableness: Does the code look reasonable at a glance? It's best if there are not sections which could obviously be excised to speed it up.
* Simplicity: A single, well-executed idea is better than a combination of unrelated ideas (though cleverly combining approaches is encouraged).

I consider Nathan's program to embody all four principles. As such, if the original author posts the original program here I will upvote it.

# Answer
> 4 votes
# Python 2, Really slow

```
import time

def isPrime(n):
    if type(n) is not int: return False
    if n < 2: return False
    if n == 2: return True
    has_composite_factor = False
    for i in range(2, n):
        i_is_prime = isPrime(i)
        if n % i == 0:
            if not has_composite_factor and i_is_prime:
                has_composite_factor  = True
    return not has_composite_factor

def time_it(n):
    start = time.clock()
    prime = isPrime(n)
    end = time.clock()

    return end - start

for i in range(20, 30):
    print "{}: {}".format(i, time_it(i))

```

If a number is prime, it stands to reason that all of it's factors must also be prime. If we can find a single composite factor, then this number cleary isn't prime. We must also check to see if the number is valid, which is why we check `type(n)` and `n < 2`.

This runs decently fast on `n < 20` but takes several seconds once you hit 25. Here is how long it takes to calculate 20-30:

```
20: 0.141494
21: 0.282143
22: 0.565975
23: 1.132836
24: 2.266971
25: 4.525667
26: 9.050018
27: 18.110675
28: 36.372516
29: 72.920298

```

---
Tags: math, popularity-contest, number-theory, primes, busy-beaver
---


title: N-queen-and-equine quine

text:
# Question
Title: N-queen-and-equine quine
There is a variant of the well-known N-queens problem which involves queens and knights and is said to be *"considerably more difficult"* **1**. The problem statement is as follows:

> You must place an equal number of knights ♞ and queens ♛ on a chessboard such that no piece attacks any other piece. What is the maximum number of pieces you can so place on the board, and how many different ways can you do it?

In this challenge, you will be given an input *n* between 3 and 32 (in a way that is the most suitable for your language). For a given *n*, there might be zero or more solutions to the above problem. In case there is no solution, you must output/return *nothing* (*nil*, *empty string*, *false*, ...). Otherwise, you must give two results:

1. A solution board (see below) for size *n* where it is not possible to add a queen or a knight chess piece without having any piece being under attack. **There must be an equal number of queens and knights**.
2. The source of a program to be run which accepts no input and gives (i) *another* solution (or *nothing*) for the same size *n*, in the same format, as well as (ii) another program for the next solution (and so on...).

Note that:

* The sequence of programs must never return the same board twice, must cover all possible solutions for the problem of size *n* and eventually has to terminate (producing no output).
* You can either return two values, return one and print the other, or print the two return values.
* *However*, if you print both the board and the next program, the board must not be considered to be a part of the next program (I'd recommend printing the board in comment, or use both standard output and error streams).
* The program-as-a-return-value must be a string, not a closure.

### Board format

* A board is a square of size *n*.
* A board cell can be empty, a queen or a knight.
* You must choose distinct values for each kind of cells (i.e. you can use other symbols than Q, N when printing the board).
* If you return a non-string board, it must be an *ordered* collection of the *n2* values of the board (e.g. matrix, vector or list in row/column-major order, ...).
* If you print the board, you can either print it squared, or as a line. For example, a solution board of size 4 can be printed as follows (spaces not required; symbols at your discretion):

```
Q - - -
- - - -
- - - -
- - N -

```

If you feel so, you can also output:

```
♛ · · ·
· · · ·
· · · ·
· · ♞ ·

```

... but this is sufficient:

```
Q-------------N-

```

It does not matter if you iterate through cells in a row-major or column-major order, because there are symmetrical solutions. For example, the solutions for n=4 are:

```
Q------N--------
Q----------N----
Q------------N--
Q-------------N-
-Q----------N---
-Q------------N-
-Q-------------N
--Q---------N---
--Q----------N--
--Q------------N
---QN-----------
---Q----N-------
---Q---------N--
---Q----------N-
---NQ-----------
----Q------N----
----Q----------N
N------Q--------
-------QN-------
-------Q----N---
---N----Q-------
-------NQ-------
--------Q------N
N----------Q----
----N------Q----
-----------QN---
-N----------Q---
--N---------Q---
-------N----Q---
-----------NQ---
N------------Q--
--N----------Q--
---N---------Q--
N-------------Q-
-N------------Q-
---N----------Q-
-N-------------Q
--N------------Q
----N----------Q
--------N------Q

```

You can also look at the solutions for n=5 as matrices; the boards contains `#`, `q` and `n` symbols, which are empty cells of different kinds (see my answer below). I count 2836 boards for *n=6*, like in Sleafar's answer (I introduced a bug when reducing byte count, but it is fixed now).

*Many thanks to Sleafar for finding not one but two bugs in my code.*

### Score

Shortest code in bytes win.

We measure the size of the first program, the one which accepts *n*.

---

**1**. Queens and Knights, by Roger K.W. Hui **(beware! contains a solution)**

# Answer
# Groovy, 515 bytes

```
X=0;Y="N="+args[0]+";M=N*N;S=[];def f(b,i,j,v){(i..<j).findAll{k->!(0..<M).any{l->w=b[l];r=(k.intdiv(N)-l.intdiv(N)).abs();c=(k%N-l%N).abs();s=v+w;w>0&&(k==l||(r==0||c==0||r==c?s<4:r<3&&c<3&&s>2))}}.collect{a=b.clone();a[it]=v;[it,a]}};def r(b,q,n){f(b,q,M,1).each{i->f(i[1],n,M,2).each{j->if(f(j[1],0,M,1).any{f(it[1],0,M,2)}){r(j[1],i[0],j[0])}else{S.add(j[1])}}}};r(new int[M],0,0);if(x<S.size()){sprintf('//%s%cX=%d;Y=%c%s%c;print(Eval.xy(X,Y,Y))',S[x].toString(),10,x+1,34,y,34)}else{''}";print(Eval.xy(X,Y,Y))

```

## Testing

Provide **n** as a command line argument:

```
groovy qak.groovy 4

```

The first line of the output is always a solution as a comment (0=empty, 1=queen, 2=knight), followed by the code in the second line:

```
//[1, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0]
X=1;Y="N=4;M=N*N;S=[];def f(b,i,j,v){(i..<j).findAll{k->!(0..<M).any{l->w=b[l];r=(k.intdiv(N)-l.intdiv(N)).abs();c=(k%N-l%N).abs();s=v+w;w>0&&(k==l||(r==0||c==0||r==c?s<4:r<3&&c<3&&s>2))}}.collect{a=b.clone();a[it]=v;[it,a]}};def r(b,q,n){f(b,q,M,1).each{i->f(i[1],n,M,2).each{j->if(f(j[1],0,M,1).any{f(it[1],0,M,2)}){r(j[1],i[0],j[0])}else{S.add(j[1])}}}};r(new int[M],0,0);if(x<S.size()){sprintf('//%s%cX=%d;Y=%c%s%c;print(Eval.xy(X,Y,Y))',S[x].toString(),10,x+1,34,y,34)}else{''}";print(Eval.xy(X,Y,Y))

```

The following script can be used for automated testing (provide **n** as an argument again):

```
#!/bin/bash
set -e
test -n "$1"
groovy qak.groovy "$1" > t
while test -s t; do
    head -n1 t
    groovy t > t2
    mv t2 t
done

```

Because I tried to make the solution as small as possible, it is **very slow** (see below for details). I tested only n=4 with this version to see if the quineification works.

## Results

**n=4:** 40 solutions (converted format)
**n=5:** 172 solutions (converted format)
**n=6:** 2836 solutions (converted format)

## Algorithm

This is a slightly ungolfed non-quine version of the solution:

```
N=args[0] as int
M=N*N
S=[]

/**
 * Generate a list of valid posibilities to place a new piece.
 * @param b Starting board.
 * @param i Start of the index range to check (inclusive).
 * @param j End of the index range to check (exclusive).
 * @param v Value of the new piece (1=queen, 2=knight).
 * @return A pair with the index of the new piece and a corresponding board for each possibility.
 */
def f(b,i,j,v){
    (i..<j).findAll{k->
        !(0..<M).any{l->
            w=b[l]
            r=(k.intdiv(N)-l.intdiv(N)).abs()
            c=(k%N-l%N).abs()
            s=v+w
            w>0&&(k==l||(r==0||c==0||r==c?s<4:r<3&&c<3&&s>2))
        }
    }.collect{
        a=b.clone();a[it]=v;[it,a]
    }
}

/**
 * Recursively look for solutions.
 * @param b Starting board.
 * @param q Start of the index range to check for queens.
 * @param n Start of the index range to check for knights.
 */
def r(b,q,n){
    f(b,q,M,1).each{i->
        f(i[1],n,M,2).each{j->
            if(f(j[1],0,M,1).any{f(it[1],0,M,2)}){
                r(j[1],i[0],j[0])
            }else{
                S.add(j[1])
            }
        }
    }
}

r(new int[M],0,0)
S.each{println(it)}

```

## Quineification

I used a very simple approach here to keep the code size low.

```
X=0;Y="...";print(Eval.xy(X,Y,Y))

```

The variable **X** holds the index of the solution to print next. **Y** holds a modified copy of the algorithm above, which is used to calculate **all** solutions and then select only one of them, which is the reason for it being so slow. The advantage of this solution is, that it doesn't require much additional code. The code stored in **Y** is executed with help of the **Eval** class (a true quine is not required).

The modified code prints the solution pointed to by **X**, increases **X** and appends a copy of itself:

```
//[...]
X=1;Y="...";print(Eval.xy(X,Y,Y))

```

I also tried to output all solutions as code for the second step, but for n=6 it was producing too much code for Groovy to handle.
> 3 votes

# Answer
## Common Lisp, 737

self-answer

```
(lambda(n &aux(d 1))#2=(catch'$(let((s(* n n))(c d))(labels((R(w % @ b ! &aux r h v a)(loop for u from % below s do(setf h(mod u n)v(floor u n)a #4=(aref b u))(when(< 0(logand a w)4)(and(= 6 w)!(throw'! t))(let((b(copy-seq b))(o 5))(loop for(K D)on'(-1 -2 -1 2 1 -2 1 2)for y =(+ K v)for x =(+(or D -1)h)for u =(and(< -1 y n)(< -1 x n)(+(* y n)x))if u do #1=(if(< #4#4)(setf #4#(logand #4#o(if(= w o)3 0)))))(#8=dotimes(y N)(#8#(x N)(let((u(+(* y n)x))(o 6))(if(or(= x h)(= y v)(=(abs(- h x))(abs(- v y))))#1#))))(setf #4#w r(or(cond((= w 5)(R 6 @ U b !))((R 5 @ U b())t)((catch'!(R 5 0 0 b t))t)(t(and(=(decf c)0)(incf d)(or(format t"~%(lambda(&aux(n ~A)(d ~A))~%~S)"n d'#2#)(throw'$ B)))t))r)))))r))(R 5 0 0(fill(make-array s)3)())))))

```

## Example

Paste the above in the REPL, which returns a function object:

```
#<FUNCTION (LAMBDA (N &AUX (D 1))) {1006D1010B}>

```

Call it (the star is bound to the last returned value):

```
QN> (funcall * 4)

```

This prints the following to the standard output:

```
(lambda(&aux(n 4)(d 2))
#1=(CATCH '$
 (LET ((S (* N N)) (C D))
   (LABELS ((R (W % @ B ! &AUX R H V A)
              (LOOP FOR U FROM % BELOW S
                    DO (SETF H (MOD U N)
                             V (FLOOR U N)
                             A #2=(AREF B U)) (WHEN (< 0 (LOGAND A W) 4)
                                                (AND (= 6 W) !
                                                     (THROW '! T))
                                                (LET ((B (COPY-SEQ B))
                                                      (O 5))
                                                  (LOOP FOR (K D) ON '(-1
                                                                       -2
                                                                       -1 2
                                                                       1 -2
                                                                       1 2)
                                                        FOR Y = (+ K V)
                                                        FOR X = (+
                                                                 (OR D -1)
                                                                 H)
                                                        FOR U = (AND
                                                                 (< -1 Y N)
                                                                 (< -1 X N)
                                                                 (+ (* Y N)
                                                                    X))
                                                        IF U
                                                        DO #3=(IF (< #2# 4)
                                                                  (SETF #2#
                                                                          (LOGAND
                                                                           #2#
                                                                           O
                                                                           (IF (=
                                                                                W
                                                                                O)
                                                                               3
                                                                               0)))))
                                                  (DOTIMES (Y N)
                                                    (DOTIMES (X N)
                                                      (LET ((U
                                                             (+ (* Y N) X))
                                                            (O 6))
                                                        (IF (OR (= X H)
                                                                (= Y V)
                                                                (=
                                                                 (ABS
                                                                  (- H X))
                                                                 (ABS
                                                                  (- V
                                                                     Y))))
                                                            #3#))))
                                                  (SETF #2# W
                                                        R
                                                          (OR
                                                           (COND
                                                            ((= W 5)
                                                             (R 6 @ U B !))
                                                            ((R 5 @ U B
                                                                NIL)
                                                             T)
                                                            ((CATCH '!
                                                               (R 5 0 0 B
                                                                  T))
                                                             T)
                                                            (T
                                                             (AND
                                                              (= (DECF C)
                                                                 0)
                                                              (INCF D)
                                                              (OR
                                                               (FORMAT T
                                                                       "~%(lambda(&aux(n ~A)(d ~A))~%~S)"
                                                                       N D
                                                                       '#1#)
                                                               (THROW '$
                                                                 B)))
                                                             T))
                                                           R)))))
              R))
     (R 5 0 0 (FILL (MAKE-ARRAY S) 3) NIL)))))

```

Also, the value returned by this function is:

```
#(5 0 0 0 0 0 0 6 0 0 0 2 0 2 0 0)

```

... which is an array literal. Number 5 represents queens, 6 is for knights and anything else stands for an empty cell, except there are more informations stored internally. If we copy-paste the returned function to the repl, we obtain a new function.

```
#<FUNCTION (LAMBDA (&AUX (N 4) (D 2))) {100819148B}>

```

And we can call it to, without arguments:

```
QN> (funcall * )

```

This call returns a new solution `#(5 0 0 0 0 0 0 2 0 0 0 6 0 0 2 0)` and the source of another function (not shown here). In case the original function or the last generated one does not find a solution, nothing is printed and nothing is returned.

## Internal values

```
|----------+--------+---------+--------+-----------------|
|          | Binary | Decimal | Symbol | Meaning         |
|----------+--------+---------+--------+-----------------|
| Empty    |    000 |       0 | -      | safe for none   |
|          |    001 |       1 | q      | safe for queen  |
|          |    010 |       2 | n      | safe for knight |
|          |    011 |       3 | #      | safe for both   |
|----------+--------+---------+--------+-----------------|
| Occupied |    101 |       5 | Q      | a queen         |
|          |    110 |       6 | K      | a knight        |
|----------+--------+---------+--------+-----------------|

```

I used to generate too few solutions. Now, I propagate what cell is safe for a queen and for a knight, independently. For example, here is an output for n=5 with pretty-printing:

```
Q - - - -
- - - n N
- q - n n
- # n - n
- n # # -

```

When we placed the queen `Q`, positions that are a knight-move away from this queen are still safe for queens and denoted `q`. Likewise, knights that are reachable only by queens are safe for other knights. Values are bitwise *and*-ed to represent the possible moves and some cells are reachable by no kind of piece.

More precisely, here is the sequence of boards leading to the following solution (from left to right), where free cells are gradually constrained with different values:

```
# # # # # #     q - - - q #     - - - - - #     - - - - - #     - - - - - n
# # # # # #     - - Q - - -     - - Q - - -     - - Q - - -     - - Q - - -
# # # # # #     q - - - q #     q - - - - -     Q - - - - -     Q - - - - -
# # # # # #     - q - q - #     - q - - - n     - - - - - n     - - - - - n
# # # # # #     # # - # # -     n n - n N -     - - - n N -     - - - - N -
# # # # # #     # # - # # #     # # - n n n     - # - - n n     - n - - n N

```

## Non-quine approach

### Ungolfed, commented version

```
(defun queens-and-knights
    (n    ; size of problem
     fn   ; function called for each solution

     ;; AUX parameters are like LET* bindings but shorter.
     &aux
       ;; total number of cells in a board
       (s (* n n)))

  (labels
      ;; Define recursive function R
      ((R (w      ; what piece to place: 5=queen, 6=knight
           %      ; min position for piece of type W
           @      ; min position for the other kind of piece
           b      ; current board
           !      ; T iff we are in "check" mode (see below)
           &aux
           r      ; result of this function: will be "true" iff we can
                  ; place at least one piece of type W on the board b
           h      ; current horizontal position
           v      ; current vertical position
           a      ; current piece at position (h,v)
           )

         (loop
            ;; only consider position U starting from position %,
            ;; because any other position below % was already visited
            ;; at a higher level of recursion (e.g. the second queen
            ;; we place is being placed in a recursive call, and we
            ;; don't visit position before the first queen).
            for u from % below s

            do
              (setf h (mod u n)         ; Intialize H, V and A
                    v (floor u n)       ;
                    a (aref b u))       ;

            ;; Apply an AND mask to current value A in the board
            ;; with the type of chess piece W. In order to consider
            ;; position U as "safe", the result of the bitwise AND
            ;; must be below 4 (empty cell) and non-null.
              (when (< 0 (logand a w) 4)

                ;; WE FOUND A SAFE PLACE TO PUT PIECE W

                (when (and ! (= 6 w))
                  ;; In "check" mode, when we place a knight, we knwo
                  ;; that the check is successful. In other words, it
                  ;; is possible to place an additional queen and
                  ;; knight in some board up the call stack. Instead
                  ;; of updating the board we can directly exit from
                  ;; here (that gave a major speed improvement since
                  ;; we do this a lot). Here we do a non-local exit to
                  ;; the catch named "!".
                  (throw '! t))

                ;; We make a copy of current board b and bind it to the
                ;; same symbol b. This allocates a lot of memory
                ;; compared to the previous approach where I used a
                ;; single board and an "undo" list, but it is shorter
                ;; both in code size and in runtime.
                (let ((b (copy-seq b)))

                  ;; Propagate knights' constraints
                  (loop
                     ;; O is the other kind of piece, i.e. queen here
                     ;; because be propagate knights. This is used as
                     ;; a mask to remove knights pieces as possible
                     ;; choices.
                     with o = 5

                     ;; The list below is arranged so that two
                     ;; consecutive numbers form a knight-move. The ON
                     ;; iteration keyword descend sublist by sublist,
                     ;; i.e. (-1 -2), (-2 -1), (-1 2), ..., (2 NIL). We
                     ;; destructure each list being iterated as (K D),
                     ;; and when D is NIL, we use value -1.
                     for (K D) on '(-1 -2 -1 2 1 -2 1 2)

                     ;; Compute position X, Y and index U in board,
                     ;; while checking that the position is inside the
                     ;; board.
                     for y = (+ K v)
                     for x = (+ (or D -1) h)
                     for u = (and (< -1 y n)
                                  (< -1 x n)
                                  (+(* y n)x))

                     ;; if U is a valid position...
                     if u
                     do
                     ;; The reader variable #1# is affected to the
                     ;; following expression and reused below for
                     ;; queens. That's why the expression is not
                     ;; specific to knights. The trick here is to
                     ;; use the symbols with different lexical
                     ;; bindings.
                       #1=(when (< (aref b u) 4) ; empty?
                            (setf (aref b u)

                                  (logand
                                   ;; Bitwise AND of current value ...
                                   (aref b u)

                                   ;; ... with o: position U is not a
                                   ;; safe place for W (inverse of O)
                                   ;; anymore, because if we put a W
                                   ;; there, it would attack our
                                   ;; current cell (H,V).
                                   o

                                   ;; ... and with zero (unsafe for
                                   ;; all) if our piece W is also a
                                   ;; knight (resp. queen). Indeed, we
                                   ;; cannot put anything at position
                                   ;; U because we are attacking it.
                                   (if (= w o) 3 0)))))

                  ;; Propagate queens' constraints
                  (dotimes (y N)
                    (dotimes (x N)
                      (let ((u(+(* y n)x))(o 6))
                        (if (or (= x h)
                                (= y v)
                                (= (abs(- h x)) (abs(- v y))))

                            ;; Same code as above #1=(if ...)
                            #1#))))

                  (setf
                   ;; Place piece
                   (aref b u) w

                   ;; Set result value
                   r (or (cond
                           ;; Queen? Try to place a Knight and maybe
                           ;; other queens. The result is true only if
                           ;; the recursive call is.
                           ((= w 5) (R 6 @ U b !))

                           ;; Not a queen, so all below concern
                           ;; knights: we always return T because
                           ;; we found a safe position.
                           ;; But we still need to know if
                           ;; board B is an actual solution and
                           ;; call FN if it is.
                           ;; ------------------------------------

                           ;; Can be place a queen too? then current
                           ;; board is not a solution.
                           ((R 5 @ U b()) t)

                           ;; Try to place a queen and a knight
                           ;; without constraining the min positions
                           ;; (% and @); this is the "check" mode that
                           ;; is represented by the last argument to
                           ;; R, set to T here. If it throws true,
                           ;; then board B is a duplicate of a
                           ;; previous one, except that it is missing
                           ;; pieces due to constraints % and @. The
                           ;; "check" mode is a fix to a bug where we
                           ;; reported as solutions boards where there
                           ;; was still room for other pieces.
                           ((catch'!(R 5 0 0 b t)) t)

                           ;; Default case: we could not add one more
                           ;; layer of pieces, and so current board B
                           ;; is a solution. Call function FN.
                           (t (funcall fn b) t))

                         ;; R keeps being true if it already was for
                         ;; another position.
                         r)))))

         ;; Return result R
         r))

    ;; Start search with a queen and an empty board.
    (R 5 0 0 (fill (make-array s) 3)  nil)))

```

### Duplicates and bugs

My very first solution outputted duplicate solutions. In order to solve it, I introduced two counters for queens and knights. The counter for queens (resp. knights) keep track of the first position in the board where a queen (resp. knight) exists: I add a queen (resp. a knight) only at positions that follow that minimal position.

That methods prevents me from revisiting solutions that were already found in previous iterations, because I iterate with an increasing queen (resp. knight) position.

However, Sleafar noticed that there were solutions for which there could be room for queens and knights, which is against the rules. For a while I though I had to revert to a normal search and store all the known solutions to prevent duplicates, which felt too costly (both in terms of bytes and memory usage).

Instead, here is what I do now: when a potential solution board is found, I try to add exactly *one* queen and *one* knight, without taking into account the counters (i.e. for all cells on the board). If this is possible, then current board is a duplicate of a previous one, and I reject the solution.

### Tests

```
|---+---------+------------+--------------|
| N |  boards |    seconds |        bytes |
|---+---------+------------+--------------|
| 3 |       0 |          0 |        32768 |
| 4 |      40 |          0 |       360416 |
| 5 |     172 |          0 |      3440016 |
| 6 |    2836 |   0.085907 |     61251584 |
| 7 |   23876 |   1.265178 |    869666288 |
| 8 |  383586 |  24.991300 |  17235142848 |
| 9 | 6064506 | 524.982987 | 359952648832 |
|---+---------+------------+--------------|

```

## Quine-ification

I had different ideas to make successive quines. The easiest one is probably to generate all solutions first as a list of strings and write sequential quines which pop from that list at each generation. However this did not seem to be shorter than current approach. Alternatively, I tried to rewrite the recursive code with a custom stack and dump all the state variables each time I find a solution; the goal is that the next step can be processed as a continuation of current step. Maybe this would be better suited for a stack based language. The current one is quite simple and rely on Common Lisp reader variables, which are always fun to use.
> 6 votes

---
Tags: code-golf, quine, chess
---