title: TryItOnquine Challenge

text:
# Question
Title: TryItOnquine Challenge
*(based on this post and the ensuing discussion on chat -- also, much thanks to Dennis for TIO!)*

## The Challenge

Choose a language that's currently available on the TryItOnline site, for example PowerShell. Write code in that language on that page, that doesn't take any input, such that when the *Run* button is clicked, the output on that page is the *exact same* as what is in the "Plain URL" field when the *Save/Store* button is clicked instead.

For a fictitious example, suppose that `aaa` was the code for a solution to this in PowerShell. Then, the result of clicking *Run* with `aaa` as the code on `https://tio.run/#powershell` should output `https://tio.run/##K8gvTy0qzkjNyfn/PzEx8f9/AA`, which is also the "Plain URL" field when the *Save/Store* button is clicked.

## Scoring

The *resulting URL* is your submission to this challenge. The winner is the shortest URL measured in bytes. For the example above, the URL `https://tio.run/##K8gvTy0qzkjNyfn/PzEx8f9/AA` is the submission to the challenge, at **44 bytes**. The shortest URL that fulfills the rest of this challenge wins the challenge and earns brownie points (points not redeemable). Given that there is a distinct minimum possible length, if two submissions tie in length, the earlier submission wins.

## URL Generation

This is the start of the URL generation algorithm in the repository. You can see how the main code area is taken, any extra elements are appended, the string is deflated and Base64 converted, and then `##` prepended, etc. I won't go into full detail here; part of the challenge is to parse and understand how the URLs are generated in order to exploit any potential quirks in said algorithm.

## Rules / Clarifications

* The actual code should take no input and produce only the quine-URL as output.
-- This means the only text fields that should be populated when clicking into the URL are the `Code`, `Header`, `Footer` or corresponding "Compiler Flag" fields; the `Input` and `Arguments` fields are forbidden and must remain empty/unused. Clicking the *Run* button should only change the `Output` field. For this challenge, the `Debug` field is ignored in all situations.
* Usual quine rules apply to the code to the extent possible (for example, the code cannot read its own source code via `.code.tio`).
* Please include a description of how the code works in your submission.
* Submitting a "cheaty" quine by submitting a Git pull request to the TIO repository to create a "trick" URL or shortcut or the like is not allowed.
* Similarly, submitting a pull request to update a particular language to produce a "trick" URL is not allowed.
* Please be nice to Dennis' servers and don't abuse them or attempt exploits for the sake of this challenge.

# Answer
> 16 votes
# Python 2, URL length = 170 bytes

```
https://tio.run/##K6gsycjPM/r/v9hWqQDCjqlISwPhYlvVIuvM3IL8ohKFpMTiVDMT64KizLwS9YySkoJiK339ksx8vaLSPH1lZXVtiAK9JDOT1Lzk/JRUDY1iVdViTT0YT70qJzNJXVMz2shK1yRWE2aHEkUW4Db//38A

```

```
s="python2\xff\xffs=%r;import base64;print'https://tio.run/##'+base64.b64encode((s%%s).encode(('zlib'))[2:-4])\xff\xff";import base64;print'https://tio.run/##'+base64.b64encode((s%s).encode(('zlib'))[2:-4])

```

Try it online!

This relies on three coincidences:

1. The default zlib level 6 happens to give the same results as zlib level 9 for this string, modulo the header that I strip.
2. The compressed length is divisible by 3, so base64 does not generate any `=` padding characters.
3. The base64 output does not contain any `+` characters.

# Answer
> 15 votes
# Bash, ~~174~~ ~~166~~ ~~165~~ 157 bytes

```
https://tio.run/##S0oszvj/v6QosUBBV1dBvaAoM68kTSGjpKSg2EpfvyQzP0avqDRPX1lZRQMqp6RaHFORlgbCSgpJQO0KSgkg/QlKNelVmQU1JYmZOQq6ydqGhjVA2VQzEwXdckNjS011BdcIz5D//wE

```

This encodes the following Bash program.

```
trap -- 'printf https://tio\.run/##$(printf "%s\xff\xff" bash "`trap`"|gzip|tail -c+11|base64 -w139)' EXIT

```

Try it online!

*Thanks to @jimmy23013 for golfing 8 bytes off my original approach, for an approach that saved another byte, and for golfing another 8 bytes off that approach!*

# Answer
> 15 votes
# Pyth, URL length = 134 bytes

```
https://tio.run/##K6gsyfj/X68syy/ZS6lYmyujpKSg2EpfvyQzX6@oNE9fWZnLwae4OLrI3dA9NITLQZ9LM8vZxqSkRC@qOJqrAKiby9vZyNTUmwtiBpefl7e3ppnJ//8A

```

Code:

```
.vjNcJ"s+
https://tio.run/##
@Lss[rG1GUT
@/
)jC<4tt.Zs[
pyth
KC255K
.vjNcJ
NJKK)64

```

Try it online!

Uses Pyth’s zlib builtin (`.Z`), and an inline implementation of base64.

### How it works

The outer stage:

```
.vjNcJ"…
      "…    take this 75-byte string
     J      assign it to J
    c       split on whitespace
  jN        join on N = '"'
.v          evaluate as Pyth code

```

The inner stage, obtained by replacing whitespace in the string `J` with double quotes:

```
s+"https://tio.run/##"@Lss[rG1GUT"@/")jC<4tt.Zs["pyth"KC255K".vjNcJ"NJKK)64
                                               [                             begin a list:
                                                "pyth"                         string,
                                                       C255                    character 255
                                                      K                        assign that to K,
                                                           K                   K again,
                                                            ".vjNcJ"           string,
                                                                    N          '"',
                                                                     J         J (the 75-byte string),
                                                                      K        K again,
                                                                       K       K again
                                                                        )    end list
                                              s  concatenate
                                            .Z   compress with zlib
                                           t     remove first character
                                          t      remove first character
                                        <4       remove last 4 characters
                                       C         convert from base 256
                                      j                                  64
                                                 convert to base 64 digits
                      @L                         map d ↦ the following indexed at d:
                          [                        begin a list:
                            G                        alphabet ("abcdefghijklmnopqrstuvwxyz")
                           r 1                       uppercase,
                              G                      alphabet again,
                               UT                    unary range of length T = 10: [0, …, 9],
                                 "@/"                string,
                                     )             end list
                         s                         concatenate
                        s                          concatenate (we now have the base64 alphabet)
 +"https://tio.run/##"                           prepend string
s                                                concatenate

```

(It’s too bad the “Input” field is disallowed, or I’d have a 118 byte solution.)

# Answer
> 5 votes
# PowerShell, 274 bytes

```
https://tio.run/##TY/rCsIwDIVfZaiYFV2HooIbgu8xBrYzboXSljYq3p59VkHZjxAOJydf4uwVfehQ676fphO5e1TK8pPSWBfF1StCobW8EYYUJMyrphO@qmtw/xzMluv1t37maJoePpsm8sVGP5eV7V25JDslsozmgOJRHAcQ3t6BldARuVDkOcVBfzb5eAwRYM0FPcUQWSkCblaBvDJtPLxaLDmPnTf2bCjbsppxj06LBlPYwRxgoGdR74E9vw9mnQ2UZObF@v4N

```

It's all thanks to the following snippet:

```
&($b={[io.file]::writeallbytes('b',[char[]]'powershell'+255+255+[char[]]"&(`$b={$b})"+255+255);gzip -f b;$b=[io.file]::readallbytes('b.gz');'https://tio.run/##'+[convert]::tobase64string($b[12..($b.count-9)]).replace('=','').replace('+','@')|write-host -n})

```

Try it online!

# Answer
> 4 votes
# JavaScript (Node.js), 214 bytes

```
v=()=>console.log('https://tio.run/##'+require(`zlib`).deflateRawSync(Buffer.from(`javascript-node\xff\xffv=`+v+`;v()\xff\xff`,`ascii`)).toString("base64"));v()

```

Try it online!

---
Tags: code-challenge, quine, optimized-output
---


title: Within Fibonacci Numbers

text:
# Question
Title: Within Fibonacci Numbers
**The Challenge**

Given an integer input, return the first Fibonacci number that contains the input within itself along with the index of that Fibonacci number (indexes starting at 0 or 1 - up to you, but please mention which in your answer). For example, if given the input of 12, the program would return `26: 121393` as 12 is found within the number (**12**1393) and it is at index 26 of the Fibonacci numbers.

**Examples**

Given the input:

```
45

```

Your program should output:

```
33: 3524578

```

Input:

```
72

```

Output:

```
54: 86267571272

```

Input:

```
0

```

Output:

```
0: 0

```

Input:

```
144

```

Output:

```
12: 144

```

**Scoring**

This is , so the shortest answer in each language wins.

# Answer
# Jelly, 10 bytes

```
0ÆḞ©w¥1#;®

```

Try it online!

### How it works

```
0ÆḞ©w¥1#;®  Main link. Argument: n

0           Set the return value to 0.
       #    Call the second link to the left with arguments k = 0, 1, 2, ... until
      1     one match has been found.
     ¥        Combine the two links to the left into a dyadich chain.
 ÆḞ             Compute the k-th Fibonacci number...
   ©              and copy it to the register.
    w           Yield 1 if n occurs inside the Fibonacci number, 0 otherwise.
         ®  Yield the value stored in the register.
        ;   Concatenate the index and the Fibonacci number.

```
> 8 votes

# Answer
# Python 2, 56 bytes

```
f=lambda n,i=0,a=0,b=1:`n`in`a`and(i,a)or f(n,i+1,b,a+b)

```

Try it online!
> 4 votes

# Answer
# Perl 6, 30 bytes

```
{first :kv,/$_/,(0,1,*+*...*)}

```

Try it online!

`first` is a function that returns the first element of a sequence that passes a test, and it conveniently takes a `:kv` adverb that tells it to return both the key (index) and the matching value.
> 4 votes

# Answer
## Batch, 104 bytes

```
@set/an=x=0,y=1
:l
@call set t=%%x:%1=%%
@if "%t%"=="%x%" set/an+=1,x+=y,y=x-y&goto l
@echo %n%: %x%

```

Works for `n=0..45` due to the limited range of Batch's integer arithmetic. Explanation: Batch doesn't have a built-in match test, but it does have an operator that can replace literal strings with other literal strings, so for example `if "%s:l=%"=="%s%"` is true if `%s%` is not empty but does not contain `l`. The use of `call` is then a trick to substitute `%1` (the input) into the replacement operator, however `call` doesn't work on control flow statements so an intermediate temporary assignment is necessary.
> 3 votes

# Answer
# Jelly, 15 bytes

```
³DẇÆḞ¬
0‘Ç¿µ,ÆḞ

```

Try it online!
> 2 votes

# Answer
# Javascript ES6, 68 chars

```
n=>eval('for(q=x=0,y=1;!`${x}`.match(n);++q)[x,y]=[y,x+y];q+": "+x')

```

Test:

```
f=n=>eval('for(q=x=0,y=1;!`${x}`.match(n);++q)[x,y]=[y,x+y];q+": "+x')
console.log([45,72,0,144].map(f).join`
`)
```
> 2 votes

# Answer
# Python 3, 76 bytes

```
f=lambda n,l=[1,0]:str(n)in str(l[1])and(len(l)-2,l[1])or f(n,[l[0]+l[1]]+l)

```
> 2 votes

# Answer
# Emojicode, 133 bytes

```
a 0b 1i 0☁a 1010b➕a ba➖b ai➕1ii 10a 10

```

Try it online!
> 2 votes

# Answer
# Dyalog APL, 39 bytes

```
{⍺←0⋄∨/(⍕⍵)⍷⍕x←1∧+∘÷/0,⍺/1:⍺,x⋄(1+⍺)∇⍵}

```

Using tail recursion. Don't attempt 72, it'll break your machine because its recalculating fibonacci all over every call.

Try it online!
> 1 votes

# Answer
# JavaScript ES6, ~~79~~ ~~78~~ 75 bytes

-1 byte by *Step Hen*

-3 bytes by *Neil*

```
i=>eval('d=a=b=1;while(!~(a+"").indexOf(i)){c=b;b=a+b;a=c;d++};d+": "+a')

```
> 1 votes

# Answer
# Mathematica, 119 bytes

1-indexed

```
(T=ToString;If[(h=#)==0,"0:0",a=#&@@Select[k=T/@(Array[Fibonacci,9#]),StringContainsQ[#,T@h]&];Min@Position[k,a]":"a])&

```

Try it online!
> 1 votes

# Answer
# Actually, 13 bytes

```
╗1⌠F$╜@c⌡╓i;F

```

Try it online!

Explanation:

```
╗1⌠F$╜@c⌡╓i;F
╗              save input in register 0
 1⌠F$╜@c⌡╓     smallest non-negative integer n where the following function returns truthy:
   F$            nth Fibonacci number, stringified
     ╜@c         count occurrences of input
          i;F  flatten the list, duplicate the index, and push the Fibonacci number at that index

```
> 1 votes

# Answer
# R, 65 bytes

```
f=function(x,n=1,a=1,b=0)`if`(grepl(x,b),c(b,n-1),f(x,n+1,a+b,a))

```

Standard recursion to generate Fibnums, but instead of terminating based on `n`, terminates when `b` matches the regex `x`. This actually works surprisingly well. I assumed that using regex with numerics would require a lot of hassle converting them to strings, but that doesn't seem to be necessary :)

This also has to overshoot the recursion by 1 step, by checking on `b` instead of `a` and then substracting `1` from `n`. This is to make sure `f(0)` works properly.

This fails for most values when input exceeds `1001`, because of maxint. If we replace `a` and `b` for bigints, this works for higher inputs (current testing is at `x = 11451`)

```
f=function(x,n=1,a=gmp::as.bigz(1),b=gmp::as.bigz(0))`if`(grepl(x,b),c(b,n-1),f(x,n+1,a+b,a))

```
> 1 votes

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

```
n=>{int a=0,b=1,c,d=0;for(;b.ToString().IndexOf(n.ToString())<0;c=a,a=b,b+=c,d++);return d+": "+b;}

```

Try it online!

Takes input as an integer, returns a string with the output.
> 1 votes

# Answer
# Haskell, 84 bytes

```
import Data.List
f=0:scanl(+)1f
g n=filter(isInfixOf(show n).show.snd)(zip[0..]f)!!0

```

Try it online!
> 1 votes

# Answer
# Japt, ~~17~~ 14 bytes

*Saved 3 bytes thanks to @JustinMariner*

```
_Å¬øU}a@[XMgX]

```

Try it online!

### Explanation

```
_Å¬øU}a@[XMgX]      Implicit: U = input integer
      a@            For each integer X in [0, 1, 2, ...]:
        [XMgX]        take [X, Fibonacci(X)].
_    }a             Return the first pair where
 Å                    all but the first item
  ¬                   joined on the empty string (simply returns Fibonacci(X) as a string)
   øU                 contains U.
                    Implicit: output result of last expression

```
> 1 votes

# Answer
## PHP, 80 bytes

```
<?php for($a=1,$b=$n=0;strpos($a=-$a+$b=$a+$b,"$argv[1]")<-1;$n++);echo"$n: $a";

```

The script is quite straightforward, simply storing the current and next terms of the sequence in $a and $b throughout. To allow for the 0th term of 0, $a and $b are initially assigned the values for the -1th term (1) and 0th term (0) respectively.

Both values are recalculated in a single expression, which is two assignments in one; effectively:

```
$b = $a + $b; // The next term is the sum of the two previous terms
$a = $b - $a; // The current term is now recalculated from the next and the previous

```

If the input value matches the beginning of the term, the strpos() function will return 0 (which is falsey and would give a false negative), but in the Wonderphul World of PHP, although `false == 0` is true and `false < 0` is false, `false < -1` is true! And so, using this comparison saves five bytes compared to `!==false`.
> 1 votes

# Answer
# PHP, ~~163~~ 141 bytes

```
<?php $x=fgets(STDIN);$b=[0,1];if($x<1)$b=[0];for(;($c=count($b)-1)&&strpos($b[$c],$x)===false;){$b[]=$b[$c]+$b[$c-1];}die($c.': '.$b[$c]);?>

```

Try it online!

Uses `$b[0] = 0;` and `$b[1] = 1;` for the start of fib sequence
> 0 votes

# Answer
# Perl 5, 67 + 1 (-p) = 68 bytes

```
@f=(0,1);push@f,$f[-1]+$f[-2]while($f[-2]!~/$_/);$_=--$#f." $f[-1]"

```

Try it online!
> 0 votes

# Answer
# PHP, 93 bytes

```
for($a[0]=$a[1]++;!strpos(" $a[$i]","$argv[1]");$a[$i+2]=$a[$i+1]+$a[$i++]);echo"$i: $a[$i]";

```

Simple loop through the Fibonacci sequence. The check for our input number is done in `strpos(" $a[$i]","$argv[1]")`; the extra space is because `strpos` will return false-y if the 'needle' is found at the beginning of the string. We end if the input is found and echo out the required string.

Try it online!
> 0 votes

# Answer
# Common Lisp, 105 bytes

```
(lambda(x)(do((a 0 b)(b 1(+ a b))(i 0(1+ i)))((search(#1=format()"~a"x)(#1#()"~a"a))(#1#()"~a: ~a"i a))))

```

Try it online!
> 0 votes

---
Tags: code-golf, fibonacci
---


# Question
Title: Output a text that doesn't output any of the characters used in the instructions to output the text
**Main objective**

The main objective is to output a text, it doesn't mind which text or where the text gets its output (it can be on a browser window, the default console etc).

It just requires the condition that what is output must be indeed "real chars" (the ones in UNICODE for example), it's not considered valid to display graphics that simulate chars.

**Condition to program**

Now into the conditions to program:

None of the characters that appear in the code must appear in the output.

The created string cannot be infinite (continuosly being created in a loop without end)

**Test cases**

So let's say that you code is

```
abcdef

```

If that displayed

```
ghijk

```

The code would be valid, but if this displayed:

```
chiij

```

Then it would not be valid

Obviously something like

print("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");

That displays

```
 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

```

would be invalid.

**Challenge**

Write a code that displays a text as defined.

**Scoring**

In this , your answer is scored by the ratio between string length and number of bytes in code (string length / code length), where the highest score wins.

Good luck!

# Answer
> 3 votes
# Jelly, 0 bytes, score: 1/0 = ∞

Try it online!

That's right, the empty program in Jelly prints `0`.

# Jelly, 5 bytes, score: 1000.6

```
⁶³ȷ³x

```

Try it online!

# Jelly, 2 bytes, score: 95 / 2 = 47.5

```
ØṖ

```

Try it online!

This yields the set of all printable ASCII: `!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~` and a space (95 bytes)

# Answer
> 1 votes
# Pyth, 1 byte, score: 26

```
G

```

Try it online

This outputs: `abcdefghijklmnopqrstuvwxyz` (26 bytes).

# Answer
> 0 votes
# Python 2, 14 bytes, score 27672892.1429

```
print"\n"*9**9

```

Prints 387420490 newlines. Output truncated on TIO.

Try it online!

# Answer
> 0 votes
# cQuents, score: 1.8530202E33 / 9 bytes = 2.0589113E32

```
#9^8e9::n

```

Score is based on math, not runs of the program.

Prints `43046721000000000` copies of `43046721000000000` joined on `,`.

## Explanation

```
 #9^8e9      n = (9^8) * 10^9
       ::    Print the sequence from 1 to n
         n   Each item in the sequence equals n

```

Try it online! (truncated)

# Answer
> 0 votes
# Python 3, 91 bytes, score = 67067/91 = 737

```
s="s=forinage(35,127):chtp*0"
for f in range(35,127):
 if chr(f)not in s:print(chr(f)*1000)

```

Try it online!

---
Tags: string, code-challenge
---


title: Number of Managers

text:
# Question
Title: Number of Managers
A company is arranged in a heirarchical structure, with a layer of workers at the bottom. Each worker is managed by a manager. Consequently, each manager is managed by another manager until there is a company "boss". Each manager is restricted to managing, at most, `x` workers. For a company of size `y` calculate the number of managers required (including the boss)

Function should take two inputs. Eg non-golfed definition: `calc_num_managers(num_workers, num_workers_per_manager)`

You can assume that the number of workers per manager will be greater than 1.

Examples:

* A company with 0 workers needs 0 managers
* If the company has 4 workers, and each manager can manage 8 workers, then there is 1 manager.
* If the company has 4 workers, and each manager can manage 4 workers, then you need 1 manager
* If the company has 12 workers, and each manager can manage 8 workers, then there are 3 managers:

# Answer
## C, C++, Java, C#, D : ~~73~~ 69 bytes

-4 bytes thanks to Zacharý

Due to the similarities between theses languages, this answer works for each.
Maybe it works in processing too, but i can't test

```
int c(int w,int p){int r=0;do{w=(w+p-1)/p;r+=w;}while(w>1);return r;}

```

Here is an optimized version in **D : 62 bytes** thanks to Zacharý

```
T c(T)(T w,T p){T r;do{w=(w+p-1)/p;r+=w;}while(w>1);return r;}

```

T here is a type for template metaprogramming. This function is callable with `c(4,8);`
> 6 votes

# Answer
# Jelly, 14 bytes

```
Ṃ÷⁴Ċ0Ṃ’$?µÐĿḊS

```

Try it online!
> 1 votes

# Answer
# JavaScript, ~~46~~ 43 bytes

If scheme isn't solvable, there will be stack exeeded error

-3 bytes `ceil` trick inspired by *Cows quack*

```
f=(w,m)=>(r=0|(w+m-1)/m,r>1&&(r+=f(r,m)),r)

//test
;[[0,1],[4,8],[4,4],[12,8],[8,3],[10,3]]//0;1;1;3;4;7
.map(e=>console.log("w="+e[0]+" m="+e[1]+" result="+f(e[0],e[1])))
```

## Requirements

`w` count of workers, non-negative integer

`m` count of max workers per manager, positive integer
> 1 votes

# Answer
# Perl 5, 44 + 1 (-n) = 45bytes

```
$t=<>;$m+=$_=1+int$_/$t while($_>1);say$m|$_

```

Try it online!
> 1 votes

# Answer
# Husk, 7 bytes

```
ΣtU¡(⌈/

```

Try it online!

Repeatedly (`¡`) takes the ceiling () of the division (`/`) of the number of workers by the number of workers per manager and sums (`Σ`) all the unique results (`U`).
> 1 votes

---
Tags: code-golf
---


title: How many ways can a road cross a river?

text:
# Question
Title: How many ways can a road cross a river?
Imagine a straight river and a road that goes across the river **n** times through bridges. The road does not loop on itself and is infinitely long. This road would be considered an open meander. An open meander is an open curve, that does not intersect itself and extends infinitely at both ends, which intersects a line **n** times.

A valid meander may be described entirely by the order of the intersection points it visits.

The number of distinct patterns of intersection with **n** intersections a meander can be is the **nth meandric number**. For example, n = 4:

**The first few numbers of this sequence are:**

```
1, 1, 1, 2, 3, 8, 14, 42, 81, 262, 538, 1828, 3926, 13820, 30694, 110954...

```

This is OEIS sequence A005316.

## Challenge

Write a **program/function** that takes a positive integer **n** as input and prints the **nth meandric number**.

### Specifications

* Standard I/O rules apply.
* Standard loopholes are **forbidden**.
* Your solution **can either be 0-indexed or 1-indexed** but please specify which.
* This challenge is not about finding the shortest approach in all languages, rather, it is about finding the **shortest approach in each language**.
* Your code will be **scored in bytes**, usually in the encoding UTF-8, unless specified otherwise.
* Built-in functions that compute this sequence are **allowed** but including a solution that doesn't rely on a built-in is encouraged.
* Explanations, even for "practical" languages, are **encouraged**.

## Test cases

These are 0-indexed. Note that you need not handle numbers this big if your language cannot by default.

```
Input      Output

1          1
2          1
11         1828
14         30694
21         73424650
24         1649008456
31         5969806669034

```

In a few better formats:

```
1 2 11 14 21 24 31
1, 2, 11, 14, 21, 24, 31

```

# Answer
> 12 votes
# Python 3, 208 188 187 184 180 177 171 bytes

```
lambda n:sum(all(i-j&1or(x<a<y)==(x<b<y)for(i,(a,b)),(j,(x,y))in d(enumerate(map(sorted,zip((0,)+p,p+(n,)))),2))for p in d(range(n)))
from itertools import*;d=permutations

```

Try it online!

Now **1-indexed** (was previously 0-indexed but 1-indexing saved a byte due to a lucky quirk regarding the behavior of meanders).

### Explanation

This may be the same as the link posted by Jenny\_mathy, but I didn't end up reading the paper, so this is just the logic behind my method.

I will be using the following illustration provided on OEIS in order to visualize the results.

Each valid meander may be described entirely by the order of the intersection points it visits. This may be trivially observed in the image; the entry segment is always on the same side (otherwise the number would be double). We can represent the tendency of both the entry and exit segments to their respective infinities by simply adding to every order a point on either side - that is to say, the order `(2, 1, 0)` would become `(-1, 2, 1, 0, 3)`.

With this in mind, the task is to find the number of orders, or permutations of the range up to `n`, which do not intersect with themselves. Intersections are only an issue between pairs of points for which the connecting segment lies on the same side. For any two pairs of consecutive points in a permutation whose segments share a side, whether or not they intersect is equivalent to whether one, and only one, of the points of one pair is between the two elements of the other pair. As such, we can determine if an order is valid by whether there are no pairs with one point contained by another pair with a segment on the same side.

Finally, having determined the validity of each permutations, the output of the function comes down to the number of permutations found to be valid.

# Answer
> 6 votes
# Haskell, 199 bytes

```
1!x=x
-1!(-1:x)=1:x
n!(i:x)=i:(n-i)!x
0#([],[])=1
0#_=0
n#(a,b)=sum$((n-1)#)<$>(-1:a,-1:b):[(a,-i:b)|i:a<-[a]]++[(-j:a,b)|j:b<-[b]]++[(j!a,i!b)|i:a<-[a],j:b<-[b],i+j>=0]
f n=n#([],[-1,1])+n#([1],[1])

```

Try it online!

Based on an extension of the ideas in Iwan Jensen, Enumerations of plane meanders, 1999 to the case of open meanders. This runs through *n* = 1, …, 16 in about 20 seconds on TIO.

# Answer
> 1 votes
# APL (Dyalog Classic), ~~127~~ 115 bytes

```
⊃⊃⌽{↓⍉(⊃,/c),∘(+/)⌸(≢¨c←{1↓¨⍳¨⍨0,¨((×2↑¯1⌽⍵)/¯1 1⌽¨⊂⍵),(⊂∊#⍵#),(××/m,≠/m)/⊂1↓¯1↓(⊢-⍵×~)⍵∊m←2↑¯1⌽⍵}¨⊃⍵)/⊃⌽⍵}⍣⎕⌽1,⊂⍳2

```

Try it online!

---
Tags: code-golf, number, sequence, combinatorics
---


title: Capture The Flag

text:
# Question
Title: Capture The Flag
This is a game of capture the flag, heavily inspired and based off of Red vs. Blue - Pixel Team Battlebots. That was an awesome question (thank you very much Calvin'sHobbies; I hope you don't mind that I shamelessly stole a lot of code from you) -- here's another team based king-of-the-hill. Hopefully, capture the flag will require more team cooperation as well as more strategy.

To mix it up, you are considered on the red team if the last digit of your id is between `0` and `4` inclusive. This should prevent the exact same teams from battling again, if the same people decide to answer. The board is `350px` by `350px`. The blue team starts on the upper half of the board and the red team starts on the lower half.

The way you play capture the flag is as follows: the object of the game is to take the opposing team's flag and bring it back to your own side. If you are on their side, you can be tagged and sent to jail. If you are in jail, then you can't move. If you are on your side, your job is to tag opposing team members to send them to jail. The only way to get out of jail is for someone on your team who is free to tag everyone in jail. (Note that jail is located on the opposing team's side).

Specifically:

* There is a constant - `FIELD_PADDING` \- set to 20. This is the padding for the field. If it were zero, then the flags and jail would be exactly on the corners of the canvas. Since it is not, the flag and jail are 20 pixels away from the corners.
* The blue flag (remember: blue team is on the upper half) is located at `(WIDTH - FIELD_PADDING, FIELD_PADDING) = (330, 20)` i.e. top-right corner.
* The red flag is at `(FIELD_PADDING, HEIGHT - FIELD_PADDING) = (20, 330)`
* The blue jail (where red members are kept) is at `(20, 20)` i.e. blue side, top left.
* The red jail, where blue members are kept, is at `(330, 330)`

Every team member starts randomly at a position `45 < x < 305` and `45 < y < 175` for blue and `175 < y < 305` for red. No team member can go within `DEFENSE_RADIUS = 25` pixels of their own flag or their own jail (unless, of course, your own flag was taken by an opposing bot, in which case you need to tag that bot). This is to prevent puppy-guarding like bots. If you go within that range, you are "pushed" back. Similarly, no team member can go out of bounds (less than zero or more than 350) -- if you do, you are pushed back to the nearest legal place you can be.

Every time you move, you use up `strength`. Your `strength` starts out at `20` and is replenished by `2` every turn. The amount of strength you use is equal to the distance you travel. If your strength would become negative by moving to a certain place, you are prevented from making that move. It's probably a good idea to just go at speed `2` for normal chasing. You should only use higher speeds if you are close to winning and need the extra speed (in my opinion).

**Spec**:

The spec is quite similar to the Pixel Team Battlebots question. You should write a code block (remember, no global variables) in javascript. It should return an object with an `x`-value and `y`-value representing your change in x and change in y values. The following answer:

```
return {
  x: 0,
  y: -2
};

```

always moves up, until it hits a wall. **You may not edit 8 hours after posting** *(except for LegionMammal98 who thought that the controller wasn't loading his/her code and didn't test)*. You have access to the following variables in your code:

* `this` -- yourself, as a player (see below for what players are)
* `move` -- the round number, starting at 0
* `tJailed` -- an array of all players on your team that are jailed
* `eJailed` -- an array of all players on the opposing team that are jailed
* `team` -- an array of all players on your team, NOT just the ones near you
* `enemies` -- an array of all players on the other team, NOT just the ones near you
* `tFlag` -- your flag (you're trying to protect it)
* `eFlag` -- the other flag (you're trying to steal it)
* `messages` -- explained below
* A list of constants: `WIDTH = 350`, `HEIGHT = 350`, `FIELD_PADDING = 20`, `DEFENSE_RADIUS = 25`.

Every "player" is an object with the following properties:

* `x` and `y`
* `strength`
* `id`
* `isJailed` -- true if the player is in jail

Every flag has the following properties:

* `x` and `y`
* `pickedUpBy` -- the player who currently has the flag, or null if no player has the flag.

Now, `messages` is an object that is shared among your teammates. *I don't care what you do with it.* The same object is shared and passed to every one of your team members. This is the only way you can communicate. You can attach properties to it, share objects, etc. It can be as big as you want -- no size limit.

Every turn the following happens:

* The list of players (both red and blue) is randomly shuffled for turn order.
* Every player makes a move.
* If any red team members touch (within 10 pixels of) any blue team members on red's side, send the blue team members to jail, and vice versa. A jailed player drops his/her flag and has strength drop to zero. Note that the step function (code you provide) is *still* called -- so you can get/set messages, but you can't move while in jail.
* If any player is touching (within 10 pixels of) the other flag, then the other flag is marked as "picked up by" that player. When the player moves, the flag moves -- until the player is tagged and goes to jail, that is.
* If any player is touching the other side's jail, free everyone in that jail. When a player is freed from jail, he/she is teleported to a random location on his/her side.

Hints:

* At least in regular capture the flag, attacks work much better when many players go at once, because it tends to confuse defenders as to which player they should chase.
* Similarly, defenders might want to coordinate who they are chasing so that attacks don't go through

Stack snippet:

```
window.onload=function(){(function(){function p(a,b,c,e){return Math.sqrt((a-c)*(a-c)+(b-e)*(b-e))}function l(a,b){this.x=this.y=0;this.id=a.id;this.title=a.title+" ["+this.id+"]";this.link=a.link||"javascript:;";this.team=b;this.isJailed=!1;this.flag=null;this.moveFn=new Function("move","tJailed","eJailed","team","enemies","tFlag","eFlag","messages","WIDTH","HEIGHT","FIELD_PADDING","DEFENSE_RADIUS",a.code);this.init()}function x(a,b){return Math.floor(Math.random()*(b-a))+a}function q(a,b){this.startX=this.x=a;this.startY=
this.y=b;this.following=null}function t(a,b){return a===e&&b||a===h&&!b?{x:20,y:20}:{x:g.width-20,y:g.height-20}}function y(){var a,b=$("#redTeam"),c=$("#blueTeam");for(a=0;a<e.length;++a)e[a].addToDiv(b);for(a=0;a<h.length;++a)h[a].addToDiv(c)}function z(){d.clearRect(0,0,g.width,g.height);d.beginPath();d.moveTo(0,g.height/2);d.lineTo(g.width,g.height/2);d.stroke();var a=e.concat(h),b,c;for(b=a.length-1;0<b;b--){c=Math.floor(Math.random()*(b+1));var f=a[b];a[b]=a[c];a[c]=f}for(b=0;b<a.length;++b)a[b].step(u);
for(b=0;b<e.length;++b)for(c=0;c<h.length;++c)10>p(e[b].x,e[b].y,h[c].x,h[c].y)&&(e[b].y<g.height/2&&e[b].goToJail(),h[c].y>g.height/2&&h[c].goToJail());for(b=0;b<a.length;++b)c=a[b].team===e!==!0?m:n,!c.following&&10>p(a[b].x,a[b].y,c.x,c.y)&&(c.following=a[b]);for(b=0;b<a.length;++b)if(c=t(a[b].team,!0),!a[b].isJailed&&10>p(a[b].x,a[b].y,c.x,c.y))for(c=a[b].team,f=0;f<c.length;++f)c[f].isJailed&&(c[f].isJailed=!1,c[f].init());m.follow();n.follow();b=m.y<g.height/2;c=n.y>g.height/2;b&&c&&alert("EXACT TIE!!!! This is very unlikely to happen.");
b&&!c&&(alert("Blue wins!"),$("#playpause").click().hide());c&&!b&&(alert("Red wins!"),$("#playpause").click().hide());for(b=0;b<a.length;++b)a[b].draw(d);m.draw("red");n.draw("blue");u++}$.ajaxSetup({cache:!1});var e=[],h=[],g=$("canvas")[0],d=g.getContext("2d"),v,u=0,m={},n={},r=!0,A={},B={},w;l.prototype.init=function(){this.x=x(45,g.width-45);this.y=x(45,g.height/2);this.team===e&&(this.y+=g.height/2);this.strength=20};l.prototype.makeShallowCopy=function(){return{x:this.x,y:this.y,strength:this.strength,
id:this.id,isJailed:this.isJailed}};l.prototype.goToJail=function(){this.isJailed=!0;var a=this.team===e!==!0?m:n;(this.team===e!==!0?m:n).following===this&&(a.following=null);a=t(this.team,!0);this.x=a.x;this.y=a.y;this.strength=0};l.prototype.step=function(a){function b(a,b,c){var e,d,f;for(e=0;e<a.length;++e)d=a[e],d!==C&&(f=d.makeShallowCopy(),d.isJailed?b.push(f):c.push(f))}var c=[],f=[],d=[],k=[],l=this.team===e?h:e,C=this,q=this.team===e?m:n,r=this.team===e?n:m;b(this.team,c,d);b(l,f,k);f=
this.moveFn.call(this.makeShallowCopy(),a,c,f,d,k,q.copy(),r.copy(),this.team===e?A:B,g.width,g.height,20,25);"object"===typeof f&&"number"===typeof f.x&&"number"===typeof f.y&&(d=p(0,0,f.x,f.y),a=t(this.team,!1),c=this.team===e!==!1?m:n,d<=this.strength&&(this.strength-=d,this.x+=f.x,this.y+=f.y,0>this.x&&(this.x=0),0>this.y&&(this.y=0),this.x>g.width&&(this.x=g.width),this.y>g.height&&(this.y=g.height),f=p(this.x,this.y,c.x,c.y),d=p(this.x,this.y,a.x,a.y),25>f&&null===c.following&&(this.x=25*(this.x-
c.x)/f*1.3+c.x,this.y=25*(this.y-c.y)/f*1.3+c.y),25>d&&(this.x=25*(this.x-a.x)/d*1.3+a.x,this.y=25*(this.y-a.y)/d*1.3+a.y)),this.isJailed||(this.strength+=2),20<this.strength&&(this.strength=20))};l.prototype.addToDiv=function(a){var b=$("<option>").text(this.title).val(this.id);a.find(".playersContainer").append(b)};l.prototype.draw=function(a){a.fillStyle=this.team===e?"red":"blue";a.beginPath();a.arc(this.x,this.y,5,0,2*Math.PI,!0);a.fill();!this.isJailed&&$("#labels").is(":checked")&&a.fillText(this.title,
this.x+5,this.y+10)};q.prototype.draw=function(a){d.strokeStyle=a;d.beginPath();d.arc(this.x,this.y,5,0,2*Math.PI,!0);d.stroke();d.fillStyle=a;d.strokeRect(this.x-2,this.y-2,4,2);d.beginPath();d.moveTo(this.x-2,this.y);d.lineTo(this.x-2,this.y+3);d.stroke()};q.prototype.copy=function(){return{x:this.x,y:this.y,pickedUpBy:this.following&&this.following.makeShallowCopy()}};q.prototype.follow=function(){null!==this.following&&(this.x=this.following.x,this.y=this.following.y)};$("#newgame").click(function(){function a(a,
b){w?b(w):$.get("https://api.stackexchange.com/2.2/questions/"+(49028).toString()+"/answers",{page:a.toString(),pagesize:100,order:"asc",sort:"creation",site:"codegolf",filter:"!JDuPcYJfXobC6I9Y-*EgYWAe3jP_HxmEee"},b,"json")}function b(g){w=g;g.items.forEach(function(a){function b(a){return $("<textarea>").html(a).text()}var d=4>=a.owner.user_id%10?e:h;a.owner.display_name=b(a.owner.display_name);if(!(a.hasOwnProperty("last_edit_date")&&28800<a.last_edit_date-a.creation_date&&33208!==a.owner.user_id||
-1<p.indexOf(a.owner.user_id))){p.push(a.owner.user_id);var g=c.exec(a.body);if(!(null===g||1>=g.length)){var f={};f.id=a.owner.user_id;f.title=a.owner.display_name;f.code=b(g[1]);f.link=a.link;d.push(new l(f,d))}}});g.has_more?a(++d,b):(console.log("Red team",e),console.log("Blue team",h),y(),clearInterval(v),r=!0,$("#playpause").show().click())}var c=/<pre><code>((?:\n|.)*?)\n<\/code><\/pre>/,d=1,p=[];e=[];h=[];u=0;m=new q(20,g.height-20);n=new q(g.width-20,20);$(".teamColumn select").empty();var k=
$("#testbotCode").val();0<k.length&&(console.log("Using test entry"),k={title:"TEST ENTRY",link:"javascript:;",code:k},$("#testbotIsRed").is(":checked")&&(k.id=-1,e.push(new l(k,e)),k.id=-3,e.push(new l(k,e))),$("#testbotIsBlue").is(":checked")&&(k.id=-2,h.push(new l(k,h)),k.id=-4,h.push(new l(k,h))));a(1,b)});$("#playpause").hide().click(function(){r?(v=setInterval(z,25),$(this).text("Pause")):(clearInterval(v),$(this).text("Play"));r=!r})})();}
```

```
#main{padding:10px;text-align:center}#testbot{padding:10px;clear:both}.teamColumn{width:25%;padding:0 10px;border:3px solid;border-color:#000;text-align:center;height:500px;overflow:scroll;white-space:nowrap}.playersContainer p{padding:0;margin:0}#redTeam{float:left;border-color:red;color:red;background-color:#fee}#blueTeam{float:right;border-color:#00f;color:#00f;background-color:#fee}#arena{display:inline-block;width:40%;text-align:center}canvas{border:1px solid #000}select{width:100%}
```

```
<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><div id=main><div class=teamColumn id=redTeam><h1>Red Team</h1><select size=20 class=playersContainer></select></div><div id=arena><h1>Battlefield</h1><canvas width=350 height=350></canvas></div><div class=teamColumn id=blueTeam><h1>Blue Team</h1><select size=20 class=playersContainer></select></div><div id=loadingInfo><button id=newgame>New Game</button> <button id=playpause>Play</button><br><input type=checkbox id="labels"> Show labels</div></div><div id=testbot><textarea id=testbotCode placeholder="testbot code"></textarea><br><input type=checkbox id="testbotIsRed">Red Team<br><input type=checkbox id="testbotIsBlue">Blue Team<br></div>
```

Controller: http://jsfiddle.net/prankol57/4L7fdmkk/

Full screen controller: http://jsfiddle.net/prankol57/4L7fdmkk/embedded/result/

Let me know if there are any bugs in the controller.

Note: If you go to the controller and think that it isn't loading anything, press "New Game." It only loads everything after you press "New Game" so that it can load all the bots and possible test bots at once.

Good luck.

---

If anyone wants to see an example game, I made an example bot that you can copy and paste into the "testbot" textarea (the testbot creates two duplicates on each team; check both red team and blue team):

```
var r2 = Math.sqrt(2);
if (this.id === -1) {
  // red team 1
  // go after flag regardless of what is going on
  if (eFlag.pickedUpBy !== null && eFlag.pickedUpBy.id === this.id) {
    return {
      x: 0,
      y: 2
    };
  }
  return {
    x: this.x < eFlag.x ? r2 : -r2,
    y: this.y < eFlag.y ? r2 : -r2
  };
}
if (this.id === -2) {
  // blue team 1
  // a) go after opposing team members on your side b) get the other flag if no enemies on your side
  var closestEnemy = null;
  for (var i = 0; i < enemies.length; ++i) {
    if (enemies[i].y < HEIGHT/2 && (closestEnemy === null || enemies[i].y < closestEnemy.y)) {
      closestEnemy = enemies[i];
    }
  }
  if (closestEnemy !== null) {
    return {
      x: this.x < closestEnemy.x ? r2 : -r2,
      y: this.y < closestEnemy.y ? r2 : -r2
    };
  }
  if (eFlag.pickedUpBy !== null && eFlag.pickedUpBy.id === this.id) {
    return {
      x: 0,
      y: -2
    };
  }
  return {
    x: this.x < eFlag.x ? r2 : -r2,
    y: this.y < eFlag.y ? r2 : -r2
  };
}
if (this.id === -3) {
  // red team 2
  // a) defend the flag b) if at least half of enemies in jail and no enemies on this side, free jailed reds and quickly return
  var closestEnemy = null;
  for (var i = 0; i < enemies.length; ++i) {
    if (enemies[i].y > HEIGHT/2 && (closestEnemy === null || enemies[i].y > closestEnemy.y)) {
      closestEnemy = enemies[i];
    }
  }
  if (closestEnemy !== null) {
    return {
      x: this.x < closestEnemy.x ? r2 : -r2,
      y: this.y < closestEnemy.y ? r2 : -r2
    };
  }
  if (enemies.length / eJailed.length <= 1 && tJailed.length > 0) {
    return {
      x: this.x < FIELD_PADDING ? r2 : -r2,
      y: this.y < FIELD_PADDING ? r2 : -r2
    };
  }
  if (this.y < 350/2) return {x: 0, y: 2};
  return {
    x: this.x < tFlag.x ? r2 : -r2,
    y: this.y < tFlag.y ? r2 : -r2
  };
}
if (this.id === -4) {
  // blue team 2
  // a) try freeing jail if there are jailed team members b) capture the flag
  if (tJailed.length > 0) {
    return {
      x: this.x < WIDTH - FIELD_PADDING ? r2 : -r2,
      y: this.y < HEIGHT - FIELD_PADDING ? r2 : -r2
    };
  }
  if (eFlag.pickedUpBy !== null && eFlag.pickedUpBy.id === this.id) {
    return {
      x: 0,
      y: -2
    };
  }
  return {
    x: this.x < eFlag.x ? r2 : -r2,
    y: this.y < eFlag.y ? r2 : -r2
  };
}

```

# Answer
> 4 votes
# Blue - LegionMammal978

```
function repeat(el, n) // Helper function
{
    var rtn = [];
    for (var i = 0; i < n; i++)
        rtn.push(el);
    return rtn;
}
function sign(n) { return n ? n < 0 ? -1 : 1 : 0; } // Another helper function
if (!messages[this.id])
    messages[this.id] = { "dir": 1 };
if (this.isJailed) // Oh noes, I'm in jail!
{
    console.log(this.id, messages);
    if (!messages[this.id].jailTicks)
        messages[this.id].jailTicks = 0;
    messages[this.id].jailTicks++;
    // Call for help!
    messages.callsForHelp = repeat(["Help!", this.id, this.x, this.y], messages[this.id].jailTicks);
    return { "x": 0, "y": 0 };
}
if (messages[this.id].jailTicks)
    if (!(delete messages[this.id].jailTicks && delete messages.callsForHelp)) // Cleanliness
        messages[this.id].jailTicks = messages.callsForHelp = undefined;       // ...
var bounds = Math.floor(HEIGHT / 2); // Be safe with fractions
if (this.y > bounds - 5) // Get back to shelter!
    return { "x": 0, "y": this.y - this.strength <= bounds - 5 ? bounds - 5 - this.y : -4 };
var target = { "none": true, "x": WIDTH << 1, "y": HEIGHT << 1 };
enemies.forEach(function (en) { if (!en.isJailed && en.y < bounds - 5 && Math.abs(en.x - this.x) < Math.abs(target.x - this.x) && Math.abs(en.y - this.y) < Math.abs(target.y - this.y)) target = en; }, this);
if (target.none)
{
    if (this.y < bounds - 5)
        return { "x": 0, "y": 2 };
    var speed = this.strength < 30 ? 1 : 2;
    if (this.x == 5 || this.x == WIDTH - 5)
        messages[this.id].dir = -messages[this.id].dir;
    return { "x": speed * messages[this.id].dir, "y": 0 };
}
if (this.x - target.x >= 0 && this.x - target.x < this.strength)
{
    if (this.y - target.y > 0 && this.y - target.y < this.strength + target.x - this.x)
        return { "x": this.x - target.x, "y": this.y - target.y };
    if (target.y - this.y > 0 && target.y - this.y < this.strength + target.x - this.x)
        return { "x": this.x - target.x, "y": target.y - this.y };
}
if (target.x - this.x > 0 && target.x - this.x < this.strength)
{
    if (this.y - target.y > 0 && this.y - target.y < this.strength + this.x - target.x)
        return { "x": target.x - this.x, "y": this.y - target.y };
    if (target.y - this.y > 0 && target.y - this.y < this.strength + this.x - target.x)
        return { "x": target.x - this.x, "y": this.y - target.y };
}
return { "x": 6 * sign(target.x - this.x), "y": 6 * sign(target.y - this.y) };

```

Defense bot.

# Answer
> 4 votes
# Red - Lazy Jail Hog | Lazy Flagger

Moves towards the closer of these two: blue's jail, or blue's flag.

* If going for the jail, will move into the jail and stop. (Since blue can't touch its own jail, it will be invincible and automatically free all allies)
* If going for the flag, it will blindly move for the flag and return.

Finally, its brain is entirely stored in `messages[29354]` and initialized on the first move only. Thus, if allies find a better use for this bot, they can replace its brain for their higher purpose.

```
if (move === 0) {
    //On the first turn, set messages[this.id] to the function I will call to move me
    messages[this.id] = function(move, tJailed, eJailed, team, enemies, tFlag, eFlag, messages) {
        //Arbitrary function to move to a point at some speed, which may be in the point
        //  If we are at the point, undefined is returned
        var moveTo = function(p, max) {
            if (!p) {
                return {x:0, y:0};
            }
            max = Math.min(this.strength, max || p.max || 2);
            var dx = p.x - this.x;
            var dy = p.y - this.y;
            var dist = Math.abs(dx)+Math.abs(dy);
            if (dist === 0) {
                return undefined;
            } else if (dist < max) {
                return {x: dx, y: dy};
            }
            var ux = Math.floor(max * dx / dist);
            var uy = Math.floor(max * dy / dist);
            while (Math.abs(ux) + Math.abs(uy) < max) {
                if (ux + this.x !== p.x) {
                    ux += ux > 0 ? 1 : -1;
                } else if (uy + this.y !== p.y) {
                    uy += uy > 0 ? 1 : -1;
                } else {
                    break;
                }
            }
            return {x: ux, y:uy};
        }.bind(this);

        //Set the way points
        var points = [];
        if (this.x > WIDTH/2) {
            points.push({x: WIDTH-FIELD_PADDING, y:HEIGHT/2+5});
            points.push({x: WIDTH-FIELD_PADDING, y:FIELD_PADDING, max: 5});
            points.push({x: WIDTH-FIELD_PADDING, y:HEIGHT/2+25, max: 5});
        } else {
            points.push({x: FIELD_PADDING, y:HEIGHT/2+5});
            points.push({x: FIELD_PADDING, y:FIELD_PADDING, max: 5});
            points.push(undefined); //Special case to do nothing / hog the jail
        }

        //Move through the points
        var state = messages[this.id].state || 0;
        var ret;
        while (!ret) {
            //Special case: if we were doing nothing, make sure we're where we think we were
            if (!points[state]) {
                ret = moveTo(points[state-1]);
                if (ret) {
                    state = 0;
                }
            }

            //Move to the next point
            ret = moveTo(points[state]);
            if (!ret) {
                state = (state + 1) % points.length;
            }
        }
        messages[this.id].state = state;
        return ret;
    };
}
//Move me based on that function, which may be changed by my allies
return messages[this.id].call(this, move, tJailed, eJailed, team, enemies, tFlag, eFlag, messages);

```

# Answer
> 4 votes
# Red - The Guard

This bot will guard the flag pretty good. Don't get in its way...

```
if (!messages[this.id]) {
    //On the first turn, set messages[this.id] to the function I will call to move me. You can replace this function on subsequent turns
    //to control it. Additionally, you can use it as a library to find one of the best places to go to defend.
    messages[this.id] = function(move, tJailed, eJailed, team, enemies, tFlag, eFlag, messages, WIDTH, HEIGHT, FIELD_PADDING, DEFENSE_RADIUS) {
        var distance = function(p1, p2) {
            var dx = p1.x - p2.x;
            var dy = p1.y - p2.y;
            return Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
        }

        var moveTo = function(p) {
            if (!p) {
                return {x:0, y:0};
            }
            var dx = p.x - this.x;
            var dy = p.y - this.y;
            var max = this.strength;
            var dist = distance(p, this);
            if (dist < max) {
                return {x: dx, y: dy};
            }
            dx = dx * max / dist;
            dy = dy * max / dist;
            while (Math.sqrt(Math.abs(dx)+Math.abs(dy)) > max) {
                if (dx > dy) {
                    dx = dx - 0.001;
                } else {
                    dy = dy - 0.001;
                }
            }
            return {x: dx, y:dy};
        }.bind(this);

        if (tFlag.pickedUp) {
            if (tFlag.y - HEIGHT / 2 > distance(this, {x: tFlag.x, y: HEIGHT / 2})) {
                return moveTo(tFlag);
            } else {
                return moveTo({y: Math.min(this.y, tFlag.y), x: tFlag.x });
            }
        }

        if (eFlag.pickedUp == this.id) {
            return moveTo({x: x, y: HEIGHT / 2});
        }

        var targetPoints = [];
        var crossedBorder = false;

        var weightedMiddlePoint = function(enemy) {
            var x1 = (enemy.x + tFlag.x) / 2;
            var y1 = (enemy.y + tFlag.y) / 2;
            var w = 1/Math.pow(distance(enemy, tFlag),2);
            return {x:x1,y:y1,w:w};
        }

        for (var i = 0; i < enemies.length; i++) {
            var enemy = enemies[i];
            if (enemy.isJailed){
                continue;
            }
            if (enemy.y > HEIGHT / 2) {
                crossedBorder = true;
            }
        }

        for (var i = 0; i < enemies.length; i++) {
            enemy = enemies[i];
            if (enemy.isJailed){
                continue;
            }
            if (crossedBorder) {
                if (enemy.y > HEIGHT / 2) {
                    targetPoints.push(weightedMiddlePoint(enemy));
                }
            } else {
                targetPoints.push(weightedMiddlePoint(enemy));
            }
        }

        if (targetPoints.length == 0) {
            return moveTo(eFlag);
        }

        var sumX = 0;
        var sumY = 0;
        var sumW = 0;

        for (var i = 0; i < targetPoints.length; i++) {
            point = targetPoints[i];
            sumX += point.x * point.w;
            sumY += point.y * point.w;
            sumW += point.w;
        }

        var targetPoint = {x: sumX / sumW, y: sumY / sumW};

        return moveTo(targetPoint);

    };
}

return messages[this.id].call(this, move, tJailed, eJailed, team, enemies, tFlag, eFlag, messages, WIDTH, HEIGHT, FIELD_PADDING, DEFENSE_RADIUS);

```

# Answer
> 1 votes
# Red - Flag Hunter

```
var distance = function(x1, y1, x2, y2) {
    return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
var moveTo = function(x, y, max) {
    if (max > this.strength)
        max = this.strength;
    var dX = x - this.x;
    var dY = y - this.y;
    var dist = distance(x, y, this.x, this.y);
    if (dist <= max) {
        return {x: dX, y: dY};
    }
    dX = dX * max / dist;
    dY = dY * max / dist;
    while (Math.sqrt(Math.abs(dX)+Math.abs(dY)) > max) {
        if (dX > dY) {
            dX = dX - 0.001;
        } else {
            dY = dY - 0.001;
        }
    }
    return {x: dX, y:dY};
}.bind(this);

var getSurroundingPoints = function(x, y, dist) {
    var points = [];
    for (var i = x - dist; i <= x + dist; i+= 0.2) {
        for (var j = y - dist; j <= y + dist; j+= 0.2) {
            if (i >= 0 && j >= 0 && j <= 180 && distance(i,j,x,y) <= dist) {
                points.push({x: i, y: j, danger: 0});
            }
        }
    }
    return points;
}

if (this.isJailed) {
    return {x:0, y:0};
}

var destination = {x: eFlag.x, y: eFlag.y}; //default: try to get the flag
if (eFlag.pickedUpBy != null) { //we got the flag
    if (eFlag.pickedUpBy.id == this.id) { //I got the flag => get back to the red side
        if (distance(this.x, this.y, this.x, 175.1) <= this.strength) {
            return moveTo(this.x, 175.1, this.strength);
        }
        destination.x = this.x;
        destination.y = 180;
    } else { //someone else got the flag => free those in the jail
        destination.x = 20;
        destination.y = 20;
    }
} else if (this.y > HEIGHT / 2) { //I am on the red side
    return moveTo(175, 175, 2);
} else if (distance(this.x, this.y, eFlag.x, eFlag.y) <= 15)  { //I am in the safe zone (flag)
    if (this.strength < 20)
        return {x:0, y:0};
    return moveTo(eFlag.x, eFlag.y, 2); //get the flag
} else if (distance(this.x, this.y, eFlag.x, eFlag.y) - this.strength <= 15)  { //I can reach the safe zone (flag)
    return moveTo(eFlag.x, eFlag.y, distance(this.x, this.y, eFlag.x, eFlag.y) - 14);
} else if (distance(this.x, this.y, 20, 20) < 10)  { //I am in the safe zone (jail)
    if (this.strength < 20)
        return {x:0, y:0};
} else if (distance(this.x, this.y, eFlag.x, eFlag.y) - this.strength <= 15)  { //I can reach the safe zone (jail)
    return moveTo(20, 20, this.strength);
}

//I am somewhere on the blue side
var points = getSurroundingPoints(this.x, this.y, this.strength);
var me = this;
points.forEach(function(point) {
    if (point.y < 175) {
        enemies.forEach(function(enemy) {
            if (distance(enemy.x, enemy.y, point.x, point.y) <= enemy.strength+10) {
                point.danger += 5;
            }
        });
        if (distance(me.x, me.y, point.x, point.y) <= 2 && point.danger == 0) {
            point.danger--;
        }
    }
});
var bestPoint = points[0];
points.forEach(function(point) {
    if (point.danger < bestPoint.danger || (point.danger == bestPoint.danger && distance(point.x, point.y, destination.x, destination.y) < distance(bestPoint.x, bestPoint.y, destination.x, destination.y))) {
        bestPoint = point;
    }
});
return moveTo(bestPoint.x, bestPoint.y, this.strength);

```

Tries to get the flag. If someone else already got it, Flag Hunter walks towards the jail, either confusing the enemy or freeing his team members.

# Answer
> 1 votes
## Blue - A jolly good fellow

First attempt both at programming in Javascript, and at code-golf. It will chase anything that comes too close to the flag, trying to front-run their moves. Otherwise, it will run to rescue team-mates in jail, or lazily try to get to the other team's flag.

```
// Euclidean distance
var distance = function(p1,p2){
 return Math.sqrt( (p1.x - p2.x)**2 + (p1.y - p2.y)**2 );
}

// points from p1 to p2
var direction = function(p1, p2){
 return Math.atan2( p2.y - p1.y, p2.x - p1.x);
}

//moving
var move2 = function(dir, step){
    if(isNaN(dir)){   dir = 0; };
    if(isNaN(step)){ step = 0; };
    return {
        x: Math.cos(dir)*step,
        y: Math.sin(dir)*step
    };
}

var intercept_at = function(me, they, field){
    if ( distance(me, they)<me.strength ){
        return they;
    }

    //console.log("I am at (", me.x, me.y, ") ");
    //console.log("They are at (", they.x, they.y, ") ");

    //first goal
    if( field.my_flag.pickedUpBy == null ){
        their_goal = field.my_flag;
        eta = (distance(they, their_goal) - they.strength)/2;
        their_dir = direction(they, their_goal);
        for( var i=1; i<eta; i++){
          they_next = {
            x: they.x + Math.cos(their_dir)*(they.strength/2 + (i+1)*2),
            y: they.y + Math.sin(their_dir)*(they.strength/2 + (i+1)*2)
          };
          if( (distance(me, they_next) )<(1.95*i) ){
            //console.log("goal is flag at (", their_goal.x, their_goal.y, ") ");
            //console.log("I can reach it at (", they_next.x, they_next.y, ") in less than ", i);
            return they_next;
          }
        }
    // second goal
    }

    my_flag = field.my_flag;
    their_goal = { x: my_flag.x, y:field.h/2 - 5};
    eta = (distance(my_flag, their_goal) - they.strength)/2;
    their_dir = direction(my_flag, their_goal);
    for( var i=0; i<eta; i++){
        they_next = {
            x: my_flag.x + Math.cos(their_dir)*(they.strength/2 + (i+1)*2),
            y: my_flag.y + Math.sin(their_dir)*(they.strength/2 + (i+1)*2)
        };
        if( (distance(me, they_next) )<(1.95*i) ){
            //console.log("goal is escaping at (", their_goal.x, their_goal.y, ") ");
            //console.log("I can front-run it at (", they_next.x, they_next.y, ") in less than ", i);
            return they_next;
        }
    }
    //console.log("Goose chase at (", they.x, they.y, ") ");
    return they;
}

var intercept = function(me, they, field){
  they_at = intercept_at(me, they, field);
  they_at.y = Math.min(they_at.y, field.h/2-5)
  dist2me = distance(me, they_at);
  dir2me = direction(me, they_at);
  if ( dist2me<me.strength ){
    return move2(dir2me, dist2me);
  }else{
    return move2(dir2me, 2);
  }
}

var closest_enemy = function(my_flag, enemies){
    cur_tgt_num = null;
    cur_tgt_dst = 999;

    for( var i=0; i<enemies.length; i++){
      if(!enemies[i].isJailed){
        cur_dst = distance(enemies[i], my_flag);
        if ( cur_dst < cur_tgt_dst ){
          cur_tgt_dst = cur_dst;
          cur_tgt_num = i;
        }
      }
    }

    return enemies[cur_tgt_num];
}

var enemies_closer_than = function(enemies, radius, field){
    closer_than = 0;
    for( var i = 0; i<enemies.length; i++){
        if(!enemies[i].isJailed){
            closer_than = closer_than + ( distance(enemies[i], field.my_flag)<radius );
        }
    }
    return closer_than;
}

var team_jailed = function(team){
    for( var i = 0; i<team.length; i++){
        if(team[i].isJailed){
            return team[i];
        }
    }
    return null;
}

var bound_positions = function(p0, field){
    p0.x = Math.max(0, Math.min(p0.x, field.w));
    p0.y = Math.max(0, Math.min(p0.y, field.h));
    return p0;
}

var avoid_obstacle = function(me, goal, obstacle, field, can_run){
    //we know that there is a safe haven
    if( distance(me, goal)<me.strength && can_run){
        return move2(direction(me, goal), me.strength)
    }

    if( obstacle == null ){
        return move2(direction(me, goal), 2);
    }

    ob_dir = direction(me, obstacle);
    if( distance(me, obstacle) < Math.sqrt(2)*(4+obstacle.strength)){
        me_next1 = bound_positions({x: me.x - 4*Math.cos(ob_dir),y: me.y - 4*Math.sin(ob_dir)}, field);
        me_next2 = bound_positions({x: me.x - 4*Math.sin(ob_dir),y: me.y - 4*Math.cos(ob_dir)}, field);
        me_next3 = bound_positions({x: me.x - 4*Math.sin(ob_dir),y: me.y - 4*Math.cos(ob_dir)}, field);
        if( distance(goal, me_next1) < distance(goal, me_next2) ){
          if( distance(goal, me_next1) < distance(goal, me_next3) ){
            me_next = me_next1;
          }else{
            me_next = me_next3;
          }
        }else{
          if( distance(goal, me_next2) < distance(goal, me_next3) ){
            me_next = me_next2;
          }else{
            me_next = me_next3;
          }
        }

        //console.log("Escaping from (", obstacle.x, obstacle.y, ")");
        return move2(direction(me, me_next), 4);
    }

    eta = (distance(me, goal)/2);
    my_dir = direction(me, goal);
    me_next = me;
    i=0;
    while(i<eta && (distance(me_next, obstacle) > obstacle.strength+2*i)){
       i++;
       me_next = {x: me_next.x + i*Math.cos(my_dir),y: me_next.y + i*Math.sin(my_dir)};
       me_next = bound_positions(me_next, field);
       if( distance(me_next, obstacle) < obstacle.strength+2*i ){
         me_next1 = {x: me_next.x + i*Math.sin(ob_dir),y: me_next.y - i*Math.cos(ob_dir)};
         me_next2 = {x: me_next.x - i*Math.sin(ob_dir),y: me_next.y + i*Math.cos(ob_dir)};
         if( distance(goal, me_next1) > distance(goal, me_next2) ){
            me_next = bound_positions(me_next2, field);
         }else{
            me_next = bound_positions(me_next1, field);
         }
       }
    }
    if( distance(me_next, obstacle) > obstacle.strength+2*i ){
        //console.log("Trying to reach goal at (", goal.x, goal.y, ") by pointing at (",me_next.x, me_next.y,")");
        return move2(direction(me, me_next), 2);
    }

    //console.log("Waiting to reach (", goal.x, goal.y,")");
    my_dir = direction(me, goal);
    me_next = {
        x: me.x + Math.cos(my_dir)*6,
        y: me.y + Math.sin(my_dir)*6
    }
    for( var i=0; i<field.team.length; i++){
        me_next.x = me_next.x - Math.sign(field.team[i].x - me_next.x);
        me_next.y = me_next.y - Math.sign(field.team[i].y - me_next.y);
    }
    return move2(direction(me, me_next), Math.floor(Math.random() * 2));
}

var field = {
    w: WIDTH,
    h: HEIGHT,
    g: DEFENSE_RADIUS,
    my_flag: tFlag,
    their_flag: eFlag,
    team: team,
    enemies: enemies
    };

var n_enemy = enemies.length;

  if( enemies_closer_than(enemies, field.h*0.67, field)>0 || tFlag.pickedUpBy !== null){
    //console.log("My flag is in danger");

    // directive defend
    messages[123 + this.id] = 'defend_own_flag';
    if ( tFlag.pickedUpBy !== null ) {
      return intercept(this, tFlag.pickedUpBy, field);
    }else{
      return intercept(this, closest_enemy(tFlag, enemies), field);
    }
  }else{

    if( tJailed.length>0 ){

        // directive support
        console.log("rescueing team member");
        console.log(tJailed);
        return avoid_obstacle(this, tJailed[0], closest_enemy(this, enemies), field, 0);
    }else{

      // directive attack
      messages[123 + this.id] = 'capture_enemy_flag';
      if ( eFlag.pickedUpBy == null ){
        //console.log("Going to capture the flag");
        return avoid_obstacle(this, eFlag, closest_enemy(this, enemies), field, 0)

      }else if (this.id == eFlag.pickedUpBy.id){
        //console.log("I have the flag");
        return avoid_obstacle(this, {x:this.x, y:field.h/2 - 1}, closest_enemy(this, enemies), field, 1);

      }else {
        //console.log("Someone else has the flag");
        return avoid_obstacle(this, eFlag, closest_enemy(this, enemies), field, 0);

      }
    }
  }

return move2(0,0);

```

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


title: Check if string is a valid URL

text:
# Question
Title: Check if string is a valid URL
Your task is to write a program or function that checks if a string is a valid URL.

Given a string as input, you will output a truthy value if the input is a valid URL. If it is not, output a falsey value. An input string is considered a valid URL if all of the following criteria are met:

* Begins with `http://` or `https://`
* At least one and up to 128 labels (parts of URL delimited by a period)
    + Labels delimited by a period
    + Contain only letters, digits, and hyphens
    + Do not start nor end with a hyphen
    + Third and fourth characters cannot be a hyphen, unless the first two characters are 'xn'
    + A label may contain zero to 63 characters
* The length of the string does not exceed 253 characters

This is a code-golf, with standard rules.

---

https://en.wikipedia.org/wiki/Domain\_Name\_System#Domain\_name\_syntax

# Answer
# JavaScript, 114 bytes

```
x=>RegExp(`^(?!.*([./](-|(?!xn)[^/]{2}--)|-[./]|-$))https?://${a='[a-zA-Z0-9-]{0,63}'}(?:\\.${a}){0,127}`).test(x)

```

Hopes it works.

For *real* URLs, you should use:

```
x=>eval(`try{new URL(x)}catch(e){}`)

```

Thanks to ThePirateBay, construct regex from string save 3 bytes.
> 2 votes

---
Tags: code-golf
---