title: Play Wythoff's Nim perfectly

text:
# Question
Title: Play Wythoff's Nim perfectly
Your goal is to write a perfect player for the game of Wythoff's Nim.

## Rules of Wythoff's Nim

Wythoff's Nim is a deterministic two-player game played with two piles of identical counters. Players alternate turns, in which they do one of these:

1. Remove one or more counters from the first pile
2. Remove one or more counters from the second pile
3. Remove an equal number of counters (one or more), from both the first pile and the second pile.

Of course, piles can't go negative, but they can to 0. Whichever player removes the last counter overall wins the game.

For the more geometrically-minded, here is an equivalent formulation of the game that you can play on this applet. A single queen starts on some square of a quarter-infinite chessboard whose corner is in the bottom-left. Players alternate moving the queen, which moves like a chess queen but restricted to three directions:

1. Down
2. Left
3. Diagonally down and left

Whoever moves the queen to the corner wins.

Associating the queen's coordinates (with corner `(0,0)`) to the sizes of the respective piles, it's easy to see both games are the same.

## Perfect play

*(You can skip this if familiar with the notions of perfect play and winning moves.)*

Since Wythoff's Nim is a finite and deterministic game, it has a notion of perfect play. A perfect player is a strategy that will always win from a theoretically won position, meaning a position in which there exists a strategy that guarantees a win.

To be a winning strategy, it suffices to move to always move to a theoretical winning position for the player who just moved, and thus the player not going next. The first of these winning positions (also called *cold positions*) are `(0,0), (1,2), (2,1), (3,5), (5,3)`. See the Wikipedia article for an explanation of an algorithm to find a winning strategy for Wythoff's Nim, as well as a formula to generate win positions.

## Program requirements

Write a program or function takes a position as input and outputs a winning move in the form of the position after that move. Fewest bytes wins.

If no winning move exists, i.e., the position is a theoretical loss, your program should indicate so and forfeit.

Your program must run within a reasonable amount of time. So, an exponential recursive game tree search will not suffice. If you want to precompute and hard-code a strategy, that's fine.

**Input**

A pair `(i,j)` of non-negative numbers representing pile sizes, each at most `99`. This can be two numbers, a tuple, a list, or whatever container you prefer.

**Output**

Print or output the position after your move, again as two numbers or a container thereof. This must be a legal move to a winning position. If there's multiple such moves, any one is fine, but only one.

If there's no winning move, you must indicate this in the output. Any output like `False`, `None`, 0, or `(-1,-1)` will do, as long as it's not a legal position, and is the same for every losing input.

**Example runs**

```
f(5,0)   = (0,0)
f(2,2)   = (1,2)   # Or (2,1) or (0,0)
f(1,2)   = False
f(13,9)  = (13,8)  # Or (10,6)
f(10,6)  = False
f(5,10)  = (5,3)
f(25,30) = (8,13)

```

# Answer
> 6 votes
# Haskell, ~~167~~ 165 characters

```
c p=o p:c(o p:p)
o p=[(a,b)|a<-[0..],b<-[0..a],(a,b)?p==[]]!!0
(a,b)?p=[y|y@(c,d)<-p,c==a||c==b||d==b||a+d==b+c]
f x@(a,b)|a<b=f(b,a)|x?c[]!!0==x=(0,-1)|1>0=x?c[]!!0

```

The algorithm is inefficient, but it still runs within a second (though not in the interactive console) for inputs \< 100.

### Explanation:

```
c p=o p:c(o p:p)

```

The list of cold positions given a set of previous cold positions is one cold position followed by the list of cold positions given this position and the previous ones (Inefficiency: this position is generated twice)

```
o p=[(a,b)|a<-[0..],b<-[0..a],(a,b)?p==[]]!!0

```

One cold position is the first pair such that there are no cold positions reachable from that pair (Inefficiency: we should search from the previous pair instead)

```
(a,b)?p=[y|y@(c,d)<-p,c==a||c==b||d==b||a+d==b+c]

```

Positions reachable from a pair are those such that their first elements match, their second elements match, their difference matches, or the smaller heap before removal is the larger heap after removal.

```
f x@(a,b)|a<b=f(b,a)
         |x?c[]!!0==x=(0,-1)
         |1>0=x?c[]!!0

```

(main method) If the heaps are in the wrong order, swap them. Else, if the first cold position reachable from a position is the position itself, indicate failure (ideally, one would return `Maybe (Int,Int)` instead). Else return that cold position (Inefficiency: said pair is looked up twice. Worse, the list of cold positions is generated twice)

# Answer
> 5 votes
## GolfScript (63 57 bytes)

```
{\]zip{~-}%0|$(!*,1=}+1,4*{..,,^[(.@,2/+.2$]+}38*2/?0]0=`

```

Expects input from stdin in the form `[a b]`, and leaves output on stdout in that form or `0` if it's a losing position. Online demo

### Overview

```
,4*{..,,^[(.@,2/+.2$]+}38*2/

```

computes a list of cold positions (including the flipped version `[b a]` for each cold position `[a b]`) using the Beatty sequence property.

Then `?` searches for the first cold position satisfying the block created by

```
{\]zip{~-}%0|$(!*,1=}+

```

which basically checks that the position is reachable from the input position by computing the vector difference and then verifying that it's either `[0 x]`, `[x 0]`, or `[x x]` for some `x > 0`. IMO that test is the cleverest bit: `0|$` forces any array in one of those formats into the form `[0 x]` while mapping `[0 0]` to `[0]`, `[a b]` where neither `a` nor `b` is `0` to a three-element array, and `[-x 0]` or `[-x -x]` to `[-x 0]`. Then `(!*,1=` checks that we have `[0 x]`.

Finally `0]0=`` does the fallback case and formatting for output.

# Answer
> 4 votes
## Pyth 57 ~~58 61 62~~

```
K1.618Jm,s*dKs*d*KKU39M<smf|}TJ}_TJm,-Ghb-Hebt^,0hk2U99 1

```

Try it online.

Pretty similar to other answers, but that wikipedia page didn't give much else to go on ;) The magic number `39` is the number of cold positions with values \< `99`.

Defines a function `g` that you can call like `g 30 25`. Returns `[]` for failure, `[(13,8)]` on success.

Explanation

```
K1.618                            : K=phi (close enough for first 39 values)
      Jm,s*dKs*d*KKU39            : J=cold positions with the form (small,big)
M<s                              1: Define g(G,H) to return this slice: [:1] of the list below
   mf|}TJ}_TJ                     : map(filter: T or reversed(T) in J, where T is each member of..
             m,-Ghb-Hebt^,0hk2    : [(G H) - (0 x+1),(x+1 0) and (x+1 x+1)]
                              U99 : for each x from 0 - 98

```

# Answer
> 2 votes
# Javascript ES6 - 280 bytes

Minified

```
r=x=>~~(x*1.618);g=(y,x)=>y(x)?g(y,x+1):x;s=A=>A?[A[1],A[0]]:A;f=(a,b)=>j([a,b])||j([a,b],1);j=(A,F)=>l(A,F)||s(l(s(A),F));l=(A,F)=>([a,b]=A,c=(F&&a+b>=r(b)&&(e=g(x=>a+b-2*x-r(b-x),0))?[a-e,b-e]:(e=g(x=>r(a+x)-2*a-x,0))+a<b?[a,a+e]:(e=r(b)-b)<a?[e,b]:0),c&&r(c[1]-c[0])==c[0]?c:0)

```

Expanded

```
r = x => ~~(x*1.618);
g = (y,x) => y(x) ? g(y,x+1) : x;
s = A =>A ? [A[1],A[0]] : A;
f = (a,b) => j([a,b]) || j([a,b],1);
j = (A,F) => l(A,F) || s(l(s(A),F));
l = (A,F) => (
    [a,b] = A,
    c = (
        F && a+b >= r(b) && (e = g( x => a+b - 2*x - r(b - x), 0 )) ? [a-e,b-e] :
        (e = g( x => r(a+x) - 2*a - x, 0)) + a < b ? [a,a+e] :
        (e = r(b) - b) < a ? [e,b] : 0
    ),
    c && r(c[1] - c[0]) == c[0] ? c : 0
);

```

Nice and quick algorithm. Runs in O(n), but would run in constant time if not for a byte-saving loop. The loop is implemented as a recursive incrementer, hence the script will eventually fail with a recursion error for *n* in the hundreds or thousands. Uses the same Beatty sequence property that Mr. Taylor mentions, but rather than computing the sequence, it simply steps up to the correct term(s).

Runs properly on all of the test inputs and many dozens besides that I tested.

The function to invoke is `f`. It returns an array on success and a `0` upon giving up.

# Answer
> 1 votes
# Perl 5 - 109 (with 2 flags)

```
#!perl -pl
for$a(@v=0..99){for$b(@v){$c=$a;$d=$b;${$:="$a $b"}||
map{$$_||=$:for++$c.$".++$d,"$a $d","$c $b"}@v}}$_=$$_

```

Usage:

```
$ perl wyt.pl <<<'3 5'

$ perl wyt.pl <<<'4 5'
1 2

```

Simply calculates solution for each possible input then just does a single lookup.

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


title: A Different Kind of Meta Regex Golf

text:
# Question
Title: A Different Kind of Meta Regex Golf
> **Notice:** Following popular demand I have slightly relaxed the rules:
>
> * The maximum regex size grows by 1 byte **every 5 answers**. Answer **N** may use up to **29 + ⌈N/5⌉** bytes.
> * The score of each answer will be **(M/(30+N/5))N**

In regex golf, you're given two sets of strings, and are asked to create the shortest regex which matches all strings in the first set, but fails on all strings in the second set.

That is what we're going to do, but each time someone answers, their regex itself will be added to one of the two sets of strings (of their own choice). **Therefore, there is a strict order to answers in this challenge.**

Let's go through an example:

* Say I start this with `abc` (which I won't), and put it in the *match* set.
* Then a valid second answer would be `a`, as it matches the above (and there are no strings that need to fail yet). Say this answer goes in the *fail* set.
* Now the third answer has to match `abc` but fail on `a`. A possible third answer is therefore `b`. Let's put this in the *match* set.
* The fourth answer now has to match `abc` and `b`, but fail on `a`. We'll disallow duplicate answers, so a valid regex would be `c|b`.

What's important is that your answer should be as short as possible. This may be trivial for the first few answers, but once we get a few answers, it should get harder and harder to get the desired match in as few characters as possible.

For the actual challenge, initially the match set contains `PPCG` and the fail set contains `[PPCG]`, and I have already provided the first answer.

## Answering

The key thing to understand about this challenge is that **only one person can answer at a time and each answer depends on the one before it**.

There should never be two answers with the same `N`. If two people happen to simultaneously answer for some `N`, the one who answered later (even if it's a few seconds difference) should graciously delete their answer.

To make this run a bit smoother, try to stick to the following steps when posting your answer:

* Make sure that someone has independently verified the correctness of the previous answer (and left a corresponding comment).
* Take the two test sets found in the previous answer, and write a regex which matches all strings in one set and none in the other.
* Post your answer in the following format:

```
# N. [regex flavour] - [regex size in bytes]

    [regex]

[link to online regex tester]

[notes, explanation, observations, whatever]

### The next answer has to match the following strings:

    [match set]

### And fail on these strings:

    [fail set]

```

where `N` is the number of your answer. Please copy `[match set]` and `[fail set]` from the previous answer, and append your regex to *one* of them.

**This is absolutely vital to the challenge!** I've provided a dashboard tool for the challenge to help with the bookkeeping, and it relies on the above template. (See bottom of the post.)
* Another user should now review your submission and leave a comment "Correctness verified" if your answer follows all the rules (see below). If it doesn't, they should leave a comment pointing out any flaws. You've then got *15 minutes* to fix those issues. If you don't, your answer will be deemed invalid, should be deleted, and someone else may post a follow-up answer to the previous one. (If this happens, you're free to submit a new answer any time.)

These regulations may seem rather strict, but they are necessary to avoid invalid answers somewhere up the chain.

## Rules

* **A user may only submit one answer per 4 hour period.** (This is to prevent users from constantly watching the question and answering as much as possible.)
* A user may not submit two answers in a row. (e.g. since I submitted answer 1 I can't do answer 2, but I could do 3.)
* **Do not edit answers that have been verified.** (Even if you find a way to shorten it!)
* Should a mistake be discovered *earlier* in the chain (i.e. after follow-up answers have been posted), the offending answer should be deleted and will be removed from the set of strings that new submissions should fail on. *However*, all answers that have been posted since should *not* be changed to reflect.
* Clearly state one flavour your regex is valid in. You may choose any flavour that is freely testable online. There's a good list of online testers over on StackOverflow. In particular, **Regex101** and **RegexPlanet** should be useful, as they support a wide variety of flavours. Please include a link to the tester you chose in your answer. By switching on the `g`lobal and `m`ultiline modifiers in the tester, you can test all strings at once, one on each line (these modifiers are not counted towards your regex size, because they aren't needed on any individual string).
* Your regex must not be empty.
* Your regex for answer **N** must not be longer than **29 + ⌈N/5⌉** bytes. I.e. answers 1 to 5 may use up to 30 bytes (inclusive), answers 6 to 10 may use up to 31 bytes... answers 31 to 35 may use up to 36 bytes. Check the dashboard to see how many characters the next answer may use.
* Your regex must not be identical to any string in either test set.
* Do not include delimiters in your submission or byte count, even if the relevant host language uses them. If your regex uses modifiers, add one byte per modifier to the regex size. E.g. `/foo/i` would be 4 bytes.

## Scoring

Each answer's score is calculated as **(M/(30+N/5))N**, where **M** is the size of the regex in bytes, and **N** is it's number. Each user's score is the product of all their answers. The user with the lowest overall score wins. In the unlikely event of a tie, the user with the *latest* submission wins. I will accept that user's latest answer.

If you prefer summing scores, you can calculate each answer's score as **N * (log(M) - log(30))** and sum those up over all answers. That will give the same leaderboard order.

There is no need to include an answer's score in the answer, just report **M**. The challenge dashboard at the bottom of the question will compute the scores, and in the event of two very close scores, I'll double check the results using arbitrary-precision types.

Note that the score of each answer is less than 1, so you can improve your overall score by providing a new answer. However, the shorter each of your submissions, the more efficiently you can lower your score. Furthermore, later answers can achieve a lower score although being longer, due to the increasing exponent.

## Dashboard

I've written a little Dashboard tool, using Stack Snippets, based on Optimizer's work over here. I hope this will help us get some order into these answer-dependent challenges.

This will display the current status of the challenge - in particular, if there are conflicting answers, if an answer needs to be verified, or if the next answer can be posted.

It also produces a list of all answers with scores, as well as a leaderboard of all users. Please stick to the challenge format above, so the dashboard can read out the relevant strings from your answers. Otherwise you might not be included in the leaderboard.

Please let me know (ideally in chat) if you spot any bugs or have some ideas how the usefulness of the tool could be improved.

```
function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentsUrl(e,t){return"http://api.stackexchange.com/2.2/answers/"+e+"/comments?page="+t+"&pagesize=100&order=asc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else{page=1;getFinalComments()}}})}function getFinalComments(){answers=answers.filter(shouldHaveHeading);answers=answers.filter(shouldHaveScore);$.ajax({url:commentsUrl(answers[0].answer_id,page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){comments.push.apply(comments,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;try{t|=/^(#|<h).*/.test(e.body_markdown);t|=["-","="].indexOf(e.body_markdown.split("\n")[1][0])>-1}catch(n){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function findDuplicates(e){var t=false;var n={};e.forEach(function(e){var r=e.body_markdown.split("\n")[0].match(NUMBER_REG)[0];if(n[r])t=t||r;n[r]=true});return t}function hasBeenVerified(e,t){var n=false;t.forEach(function(t){n|=/correctness verified/i.test(t.body_markdown)&&e!=t.owner.user_id});return n}function userTimedOut(e){return NOW-e.creation_date*1e3<MSEC_PER_ANSWER}function getAuthorName(e){return e.owner.display_name}function getAnswerScore(e,t){e=parseInt(e);t=parseInt(t);return Math.pow(t/(30+e/5),e)}function process(){$("#last-user").append(answers[0].owner.display_name);var e=answers.slice(1).filter(userTimedOut).map(getAuthorName).join(", ");if(e)$("#timed-out-users").append(e);else $("#timed-out-notice").hide();var t=answers[0].body_markdown.split("\n")[0].match(NUMBER_REG)[0];var n=findDuplicates(answers);if(n){var r=$("#status-conflict-template").html();$("#challenge-status").append(r.replace("{{NUMBER}}",n));$("#challenge-status").addClass("conflict")}else if(!hasBeenVerified(answers[0].owner.user_id,comments)){var r=$("#status-verification-template").html();$("#challenge-status").append(r.replace("{{NUMBER}}",t));$("#challenge-status").addClass("verification")}else{var r=$("#status-next-template").html();$("#challenge-status").append(r.replace("{{NUMBER}}",t).replace("{{NEXT}}",parseInt(t)+1).replace("{{SIZE}}",29+Math.ceil((parseInt(t)+1)/5)));$("#challenge-status").addClass("next")}var i={};var s={};answers.forEach(function(e){var t=e.body_markdown.split("\n")[0];var n=$("#answer-template").html();var r=t.match(NUMBER_REG)[0];var o=(t.match(SIZE_REG)||[0])[0];var u=getAnswerScore(r,o);var a=getAuthorName(e);n=n.replace("{{NAME}}",a).replace("{{NUMBER}}",r).replace("{{SIZE}}",o).replace("{{SCORE}}",u.toExponential(5)).replace("{{LINK}}",e.share_link);n=$(n);$("#answers").append(n);i[a]=(i[a]||1)*u;s[a]=(s[a]||0)+1});var o=[];for(var u in i)if(i.hasOwnProperty(u)){o.push({name:u,numAnswers:s[u],score:i[u]})}o.sort(function(e,t){return e.score-t.score});var a=1;o.forEach(function(e){var t=$("#user-template").html();t=t.replace("{{NAME}}",e.name).replace("{{NUMBER}}",a++).replace("{{COUNT}}",e.numAnswers).replace("{{SCORE}}",e.score.toExponential(5));t=$(t);$("#users").append(t)})}var QUESTION_ID=41462;var ANSWER_FILTER="!*cCFgu5yS6BFQP8Z)xIZ.qGoikO4jB.Ahv_g-";var COMMENT_FILTER="!)Q2B_A497Z2O1kEH(Of5MUPK";var HOURS_PER_ANSWER=4;var MSEC_PER_ANSWER=HOURS_PER_ANSWER*60*60*1e3;var NOW=Date.now();var answers=[],comments=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/;var NUMBER_REG=/\d+/
```

```
body{text-align:left!important}#challenge-status{font-weight:700;padding:10px;width:620px}#blocked-users{padding:10px;width:620px}.conflict{background:#994343;color:#fff}.verification{background:#FFDB12}.next{background:#75FF6E}#last-user,#timed-out-users{font-weight:700}#answer-list{padding:10px;width:300px;float:left}#leaderboard{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="challenge-status"> </div><div id="blocked-users"> User <span id="last-user"></span> has posted the last answer, and may not post the next one. <div id="timed-out-notice"><span id="timed-out-users"></span> have answered within the last four hours and may not answer again yet. (If a user appears in this list twice, they must have answered twice within four hours!)</div></div><div id="answer-list"> <h2>List of Answers (newest first)</h2> <table class="answer-list"> <thead> <tr><td>No.</td><td>Author</td><td>Size</td><td>Score</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="leaderboard"> <h2>Leaderboard</h2> <table class="leaderboard"> <thead> <tr><td>No.</td><td>User</td><td>Answers</td><td>Score</td></tr></thead> <tbody id="users"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{NUMBER}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td>{{SCORE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="user-template"> <tr><td>{{NUMBER}}</td><td>{{NAME}}</td><td>{{COUNT}}</td><td>{{SCORE}}</td></tr></tbody> </table> <div id="status-conflict-template" style="display: none"> There is more than one answer with number {{NUMBER}}!<br>Please resolve this conflict before posting any further answer. </div><div id="status-verification-template" style="display: none"> Answer {{NUMBER}} has not been verified!<br>Please review the answer and post a comment reading "Correctness verified." on the answer if it is valid. Note that this has to be done by a different user than the author of the answer! </div><div id="status-next-template" style="display: none"> Answer {{NUMBER}} has been verified!<br>You may now post answer {{NEXT}}, using up to {{SIZE}} bytes. </div>
```

# Answer
# 42. Python flavour - 38

```
\?[^w$]*\$$|^P|\w.\)|w.?\+|w\^|[^?P]P$

```

Tested on Regex101

The lack of entropy in the last few answers was getting to me... (should have done this sooner)

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)
\?[^w$]*\$$|[]^C]\w+$|w\^|\|..\)
\w.\)|\?[^-$]*\$$|[]^C]\w$|w[+^]
[]^C]\w$|\w.\)|-\$|w[+^]|\?[^w$]*\$$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$
[?[CP(].[-<)|w]|^P|^[^C|\\]*$
^..(.{7}$|.[3Gw!^)]|$)|G.?.?\)
^...[3w!G)]|^[^\\C|]*$|G.?.?\)
^[^C\\|]+$|G.\)|\.\)|w\^|^P|\...?]
^P|!.3|w\^|^[^C\\|]+$|\.[)$-](?!.!)
\?[^$w]*\$$|[]C^]\w$|w.]|\w.\)
\$..\\|\?[^w$]*\$$|w\^|[]^C]\w$
[]^C]\w$|\w.\)|w[[+^]|\?[^w$]*\$$
\?[^w$]*\$$|^P|\w.\)|w.?\+|w\^|[^?P]P$

```
> 5 votes

# Answer
# 28. Python flavour - 29

```
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P

```

Tested on Regex101

Lots of fiddling around was done - #4 in the pass set's probably the biggest pain, as it's a substring of a regex in the fail set, and also shares a suffix with another regex in the fail set.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\

```
> 11 votes

# Answer
# 24 - Python flavour - 29

```
^(..[^^].{4,22}\$|[^?]+\w)$|2

```

Tested here

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2

```
> 9 votes

# Answer
# 8. ECMAScript flavour - 14 bytes

```
[^?][PG]$|<|PG

```

Demo

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG

```
> 8 votes

# Answer
# 10. Python flavor - 19

```
^[\w^]*$|!|]P|G]\$$

```

Tested on Regex101.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)*[^\\|]*[^\]]$

```
> 8 votes

# Answer
# 2. ECMAScript flavour - 6 bytes

```
^[P\^]

```

Test it here

### The next answer has to match the following strings:

```
PPCG
^P

```

### And fail on these strings:

```
[PPCG]
^[P\^]

```
> 7 votes

# Answer
# 9. Python flavour - 28

```
^[^\\|]*(\\\\)*[^\\|]*[^\]]$

```

Tested on Regex101

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)*[^\\|]*[^\]]$

```
> 7 votes

# Answer
# 11. Python - 29

```
^(.{,4}|.{9}|.{16,19}|.{5}P)$

```

► Test at RegexPlanet

Almost all invalid answers have a different length than all the valid ones. This regex makes use of that.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$

```
> 7 votes

# Answer
# 23. PCRE flavour - 28

```
([^\\}<]{3}|][^]]|^).?[$PG]$

```

Tested on Regex101.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$

```
> 7 votes

# Answer
# 29. PCRE flavour - 28

```
^..(.[!)3G^w]|$)|\^.{7}$|G\)

```

Tested on Regex101

This answer still works...

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\

```
> 7 votes

# Answer
## 31. Perl flavour - 29

`[?[CP(].[-<)|w]|^P|^[^C|\\]*$`

I don't know how it works, it was produced by my the first foray into genetic algoritms. There is program output that mentions the answer.

The next answer has to match:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)

```

and to fail:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$
[?[CP(].[-<)|w]|^P|^[^C|\\]*$

```
> 6 votes

# Answer
## 32. PCRE — 30 bytes

```
^..(.{7}$|.[3Gw!^)]|$)|G.?.?\)

```

Tested on Regex101

**The next answer has to match the following strings**:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)

```

**And fail on these strings**:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$
[?[CP(].[-<)|w]|^P|^[^C|\\]*$
^..(.{7}$|.[3Gw!^)]|$)|G.?.?\)

```
> 6 votes

# Answer
# 1. ECMAScript flavour - 2 bytes

```
^P

```

Test it on Regex101.

The initial matching set is `PPCG` and the failing set `[PPCG]`. Therefore, this regex simply tests that the string *starts* with `P`.

### The next answer has to match the following strings:

```
PPCG
^P

```

### And fail on these strings:

```
[PPCG]

```
> 5 votes

# Answer
# 3. ECMAScript flavour - 6 bytes

```
[^\]]$

```

Test it here

### The next answer has to match the following strings:

```
PPCG
^P

```

### And fail on the these strings:

```
[PPCG]
^[P\^]
[^\]]$

```
> 5 votes

# Answer
# 7. Python flavour - 16

```
(?<!\\..)(?!]).$

```

Tested on Regex101

Gotta add a \ to the match list :)

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P

```
> 5 votes

# Answer
# 12. ECMAScript flavor - 17

```
!|[^?]P(CG|G..)?$

```

Test it here.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$

```
> 5 votes

# Answer
# 22. PCRE Flavor – 29 bytes

Since the original #22 is not modified for 1 hour I assume it has become invalid.

```
^.{3,23}[.-~]..\$$|[^P?][PG]$

```

Demo

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P

```
> 5 votes

# Answer
# 26. Python flavor - 28

```
^..(.[!G)(3w^]|.{7}$|$)|\$\?

```

Test on Regex101

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~

```
> 5 votes

# Answer
# 30. Python flavour - 28

```
[[?C(].[-!)|w]|^P|^[^C|\\]*$

```

Tested on Regex101

When there's a will...

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$

```
> 5 votes

# Answer
# 37. Perl flavour - 30

```
\?[^$w]*\$$|[]C^]\w$|w.]|\w.\)

```

Submission on Regex101.

The solution was produced by the the same program as before. The program has also printed 29-character solution `\?[^$w]*\$|[]^C]\w)$|w.]|\w.\`, I don't know why, as it looks like a malformed regex...

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)
\?[^w$]*\$$|[]^C]\w+$|w\^|\|..\)

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$
[?[CP(].[-<)|w]|^P|^[^C|\\]*$
^..(.{7}$|.[3Gw!^)]|$)|G.?.?\)
^...[3w!G)]|^[^\\C|]*$|G.?.?\)
^[^C\\|]+$|G.\)|\.\)|w\^|^P|\...?]
^P|!.3|w\^|^[^C\\|]+$|\.[)$-](?!.!)
\?[^$w]*\$$|[]C^]\w$|w.]|\w.\)

```
> 5 votes

# Answer
## 40. PCRE — 33 bytes

```
[]^C]\w$|\w.\)|w[[+^]|\?[^w$]*\$$

```

Tested on Regex101

**The next answer has to match the following strings**:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)
\?[^w$]*\$$|[]^C]\w+$|w\^|\|..\)
\w.\)|\?[^-$]*\$$|[]^C]\w$|w[+^]

```

**And fail on these strings**:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$
[?[CP(].[-<)|w]|^P|^[^C|\\]*$
^..(.{7}$|.[3Gw!^)]|$)|G.?.?\)
^...[3w!G)]|^[^\\C|]*$|G.?.?\)
^[^C\\|]+$|G.\)|\.\)|w\^|^P|\...?]
^P|!.3|w\^|^[^C\\|]+$|\.[)$-](?!.!)
\?[^$w]*\$$|[]C^]\w$|w.]|\w.\)
\$..\\|\?[^w$]*\$$|w\^|[]^C]\w$
[]^C]\w$|\w.\)|w[[+^]|\?[^w$]*\$$

```
> 5 votes

# Answer
# 4. ECMAScript flavour - 5 bytes

```
^\^?P

```

Test it here.

### The next answer has to match the following strings:

```
PPCG
^P

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P

```
> 4 votes

# Answer
# 5. ECMAScript flavour - 6 bytes

```
^[P^]P

```

Tested on Regex101.

Time to spice things up a bit with the success set.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P

```
> 4 votes

# Answer
# 6. ECMAScript flavour - 9 bytes

```
[^?][PG]$

```

Tested on Regex101.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P

```
> 4 votes

# Answer
# 14. PCRE flavour - 25

```
([.$?]|G\])\$$|^\^?P|\]P$

```

Tested on Regex101

This is starting to get quite hard.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$

```
> 4 votes

# Answer
# 15. PCRE flavour - 26

```
([P.$?]\$|[]^]P|G\]\$|CG)$

```

Tested on Regex101

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$

```
> 4 votes

# Answer
# 16. PCRE flavor - 21

```
^[^?]*[PG]$|[?$].*\$$

```

Tested on Regex 101.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$

```

## And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$

```
> 4 votes

# Answer
# 25. PCRE flavour - 29

```
^(..[^^].{4,22}\$|[^?]+\w)$|~

```

Tested here. (The test regex contains an additional `\n` to make sure that no match spans multiple lines. This is not necessary to match each individual string.)

That was a low-hanging fruit! :) I have to congratulate plannapus though, this regex is amazingly elegant for the current test sets. If you want to upvote this answer, make sure to upvote the previous one, too!

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~

```
> 4 votes

# Answer
## 35. PCRE — 35 bytes

```
^P|!.3|w\^|^[^C\\|]+$|\.[)$-](?!.!)

```

Tested on Regex101

**The next answer has to match the following strings**:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)

```

**And fail on these strings**:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$
[?[CP(].[-<)|w]|^P|^[^C|\\]*$
^..(.{7}$|.[3Gw!^)]|$)|G.?.?\)
^...[3w!G)]|^[^\\C|]*$|G.?.?\)
^[^C\\|]+$|G.\)|\.\)|w\^|^P|\...?]
^P|!.3|w\^|^[^C\\|]+$|\.[)$-](?!.!)

```
> 4 votes

# Answer
# 36. Python flavour - 32

```
\?[^w$]*\$$|[]^C]\w+$|w\^|\|..\)

```

Tested on Regex101

I had three 32-byte regexes ready, and luckily one of them still works :D

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)
\?[^w$]*\$$|[]^C]\w+$|w\^|\|..\)

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$
[?[CP(].[-<)|w]|^P|^[^C|\\]*$
^..(.{7}$|.[3Gw!^)]|$)|G.?.?\)
^...[3w!G)]|^[^\\C|]*$|G.?.?\)
^[^C\\|]+$|G.\)|\.\)|w\^|^P|\...?]
^P|!.3|w\^|^[^C\\|]+$|\.[)$-](?!.!)

```
> 4 votes

# Answer
# 38. Python flavour - 31

```
\$..\\|\?[^w$]*\$$|w\^|[]^C]\w$

```

Tested on Regex101

I'm feeling pretty silly now, because Vi. golfed out a useless `+` from my last answer.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)
\?[^w$]*\$$|[]^C]\w+$|w\^|\|..\)

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$
[?[CP(].[-<)|w]|^P|^[^C|\\]*$
^..(.{7}$|.[3Gw!^)]|$)|G.?.?\)
^...[3w!G)]|^[^\\C|]*$|G.?.?\)
^[^C\\|]+$|G.\)|\.\)|w\^|^P|\...?]
^P|!.3|w\^|^[^C\\|]+$|\.[)$-](?!.!)
\?[^$w]*\$$|[]C^]\w$|w.]|\w.\)
\$..\\|\?[^w$]*\$$|w\^|[]^C]\w$

```
> 4 votes

# Answer
# 39. Perl flavour - 32

```
\w.\)|\?[^-$]*\$$|[]^C]\w$|w[+^]

```

Regex101 submission

Generated by the program. There are also 2 competing 32-character solutions.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)
\?[^w$]*\$$|[]^C]\w+$|w\^|\|..\)
\w.\)|\?[^-$]*\$$|[]^C]\w$|w[+^]

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$
[?[CP(].[-<)|w]|^P|^[^C|\\]*$
^..(.{7}$|.[3Gw!^)]|$)|G.?.?\)
^...[3w!G)]|^[^\\C|]*$|G.?.?\)
^[^C\\|]+$|G.\)|\.\)|w\^|^P|\...?]
^P|!.3|w\^|^[^C\\|]+$|\.[)$-](?!.!)
\?[^$w]*\$$|[]C^]\w$|w.]|\w.\)
\$..\\|\?[^w$]*\$$|w\^|[]^C]\w$

```
> 4 votes

# Answer
# 41. PCRE - 36

```
[]^C]\w$|\w.\)|-\$|w[+^]|\?[^w$]*\$$

```

Tested on Regex101

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)
\?[^w$]*\$$|[]^C]\w+$|w\^|\|..\)
\w.\)|\?[^-$]*\$$|[]^C]\w$|w[+^]
[]^C]\w$|\w.\)|-\$|w[+^]|\?[^w$]*\$$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$
[?[CP(].[-<)|w]|^P|^[^C|\\]*$
^..(.{7}$|.[3Gw!^)]|$)|G.?.?\)
^...[3w!G)]|^[^\\C|]*$|G.?.?\)
^[^C\\|]+$|G.\)|\.\)|w\^|^P|\...?]
^P|!.3|w\^|^[^C\\|]+$|\.[)$-](?!.!)
\?[^$w]*\$$|[]C^]\w$|w.]|\w.\)
\$..\\|\?[^w$]*\$$|w\^|[]^C]\w$
[]^C]\w$|\w.\)|w[[+^]|\?[^w$]*\$$

```
> 4 votes

# Answer
# 13. PCRE flavor - 20

```
[^])]\$|^\^?P|P.\].$

```

Test it here.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$

```
> 3 votes

# Answer
# 17. Python flavor - 21

```
^[^[]P|]P|(G]|[.])\$$

```

Tested on Regex 101.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$

```

## And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$

```
> 3 votes

# Answer
# 18. PCRE Flavor - 25 bytes

```
!|((G.|P|\.)\$|[^?]P|CG)$

```

Tested on Regex 101.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$

```

## And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$

```
> 3 votes

# Answer
# 19. Python flavour - 28

```
\..$|!|\|G|^[\^P]P|P\^|G.\$$

```

Tested on Regex101.

I tried so many different ways. All 28 characters. :'(

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$

```
> 3 votes

# Answer
# 20. PCRE flavour - 27

```
...\^.P|^!|G]\$$|w|<!|^\^?P

```

Tested on Regex101.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P

```
> 3 votes

# Answer
# 21. ECMAScript flavour - 24 bytes

... The moment when you see one accept string is the prefix of a reject string, and realize that the longer one is from your earlier answer.

```
^[(!P]|G..$|]..\||[^?]P$

```

Demo

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P

```
> 3 votes

# Answer
# 27. PCRE Flavor - 27

```
^..(.[!()3G^w]|.{7}$|$)|G\\

```

Demo. The previous answer clearly works, so... thanks? :)

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\

```
> 3 votes

# Answer
# 33. Python flavour - 30

```
^...[3w!G)]|^[^\\C|]*$|G.?.?\)

```

Tested on Regex101

Originally I had the 30 char `[.!w].[]?3P]|^P|^[^C|\\]*$|\?<` for the previous set, but I took too long trying to find a 29 and hwnd inadvertedly ruled out my submission.

So instead I mashed together two common themes we've had so far, just for fun :)

*Note:* Please remember that when testing `^[^C|\\]*$` or anything else that uses `[^...]`, put a `\n` in the character set. Otherwise Regex101 may match over lines.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$
[?[CP(].[-<)|w]|^P|^[^C|\\]*$
^..(.{7}$|.[3Gw!^)]|$)|G.?.?\)
^...[3w!G)]|^[^\\C|]*$|G.?.?\)

```
> 3 votes

# Answer
# 34. Perl flavour - 34

```
^[^C\\|]+$|G.\)|\.\)|w\^|^P|\...?]

```

Submission on Regex101 \- there is additional `\n` added for Regex101 there, as previous answer suggested

The solution was produced by the the same program as before (with little tweaks). 35-character solutions were easy to find, but I waited for 34 version to make 34'th answer be 34 characters.

### The next answer has to match the following strings:

```
PPCG
^P
^[P^]P
[^?][PG]$
(?<!\\..)(?!]).$
^[\w^]*$|!|]P|G]\$$
!|[^?]P(CG|G..)?$
[^])]\$|^\^?P|P.\].$
([.$?]|G\])\$$|^\^?P|\]P$
([P.$?]\$|[]^]P|G\]\$|CG)$
!|((G.|P|\.)\$|[^?]P|CG)$
^[(!P]|G..$|]..\||[^?]P$
^.{3,23}[.-~]..\$$|[^P?][PG]$
^..(.[!G)(3w^]|.{7}$|$)|\$\?
\.\)|P[.$?]|w\^|^[^|C\\]*$|^P
^..(.[!)3G^w]|$)|\^.{7}$|G\)

```

### And fail on these strings:

```
[PPCG]
^[P\^]
[^\]]$
^\^?P
[^?][PG]$|<|PG
^[^\\|]*(\\\\)+[^\\|]*[^\]]$
^(.{,4}|.{9}|.{16,19}|.{5}P)$
^[^?]*[PG]$|[?$].*\$$
^[^[]P|]P|(G]|[.])\$$
\..$|!|\|G|^[\^P]P|P\^|G.\$$
...\^.P|^!|G]\$$|w|<!|^\^?P
([^\\}<]{3}|][^]]|^).?[$PG]$
^(..[^^].{4,22}\$|[^?]+\w)$|2
^(..[^^].{4,22}\$|[^?]+\w)$|~
^..(.[!()3G^w]|.{7}$|$)|G\\
[[?C(].[-!)|w]|^P|^[^C|\\]*$
[?[CP(].[-<)|w]|^P|^[^C|\\]*$
^..(.{7}$|.[3Gw!^)]|$)|G.?.?\)
^...[3w!G)]|^[^\\C|]*$|G.?.?\)
^[^C\\|]+$|G.\)|\.\)|w\^|^P|\...?]

```
> 3 votes

---
Tags: code-golf, regular-expression, answer-chaining
---


# Question
Title: Detect the character encoding of the input
Your task is to golf a program that prints which character encoding, if any, the data read from the input represents. It should be able to detect the following encodings:

One of the above names of character encodings should be printed (in the same way) if it can be determined which is used. If the input is not ASCII, but it's ambiguous which of the other encodings is used, a `?` should be printed. If none of the encodings can be valid, `X` must be printed.

Furthermore, the following should be taken into account:

* **If the input is valid ASCII, ASCII should be printed**. Even though this means the other encodings are also valid. When the input is not ASCII, `?` should printed in case of any ambiguity.
* The UTF's are not required to start with a BOM.
* UTF-16 can be either big or little endian. This means there are actually five different encodings to detect.
* If UTF-8 or UTF-16 data encodes a number between 0 and 0x10FFFF you may consider it valid, even if it represents a Unicode code point that is technically not allowed in this encoding. Therefore **you do not have to worry about unassigned code points and such.**
* ISO 8859-1 is considered invalid when any of its undefined bytes (positions 0-31 and 127-159, except 9, 10 and 13) are used.
* This is code golf.

Happy golfing!

# Answer
> 3 votes
## Tcl, 247

```
set i [read [open f rb]];foreach n\ d {ascii ASCII utf-8 UTF-8 unicode UTF-16 iso8859-1 ISO\ 8859-1} {if {[encoding convertt $n [encoding convertf $n $i]]eq$i&&($n!="iso8895-1"||[regexp {[\1-\10\13\14\16-\37\177-\237]} $i])} {puts $d;exit}};puts X

```

Reads the input from the file `f` in the current directory.

It works by decoding and re-encoding the input into the different charsets and check if the input and the re-encoded input is equal.

I believe that valid UTF-8 is also valid (but useless) ISO 8859-1, so I print UTF-8 then.

# Answer
> 0 votes
## Scala, 505 bytes (w/o using built-in encoders)

```
def e(s:Array[Byte])=if(s.forall(_>0))"ASCII"else{var a=true;var b=true;var p=0;var q=false;var v=0;var t=false;for(c<-s){if(a){if(c== -64||c== -63||c> -12)a=false else{if(p==0)p=if(c>0)0 else if(c< -32)1 else if(c< -16)2 else 3 else a=c<= -64}};if(b){val x=(c+256)%256;if(q){v=v*256+x;if(v>55295&&v<56320)t= !t;b=t;if(v>56319&&v<57344)t= !t}else v=x}};b=b&& !t;val c=s.forall{x=>x==9||x==10||x==13||x>=32&&(x> -97)};if(a&&b||b&&c||a&&c)"?"else if(a)"UTF-8"else if(b)"UTF-16"else if(c)"ISO 8859-1"else"X"}

```

Unfortunately doesn't detect overlong encodings in UTF-8.

---
Tags: code-golf
---


# Question
Title: Can you cancel the stackoverflow exception in the following code?
The following code will produce a run-time error, `stackoverflow` exception.

```
class Foo
{
    //static Foo foo = new Foo(); // you are not allowed using this approach
    //static readonly Foo foo = new Foo(); // you are not allowed using this approach
    Foo foo = new Foo();
}
class Program
{
    static void Main(string[] args)
    {
        new Foo();
    }
}

```

The objective is to cancel the exception without

* removing, modifying or commenting out the existing code,
* using the approaches mentioned (and their variants in access modifiers, `public`, `private`, etc) as the given comments,
* using `try-catch-finally` or its variants,
* using attributes,
* using compilation condition,

You are only allowed to add your own code inside the `Foo` class. How do you cancel the exception at run-time?

# Answer
Never wrote C# before, does this work ?

```
class Foo
{
    Foo fooExit = exitMe();
    //static Foo foo = new Foo(); // you are not allowed using this approach
    //static readonly Foo foo = new Foo(); // you are not allowed using this approach
    Foo foo = new Foo();

    static Foo exitMe()
    {
        System.Environment.Exit(0);
        return null;
    }
}
class Program
{
    static void Main(string[] args)
    {
        new Foo();
    }
}

```
> 9 votes

# Answer
Here, another try:

```
class Foo
{
    //static Foo foo = new Foo(); // you are not allowed using this approach
    //static readonly Foo foo = new Foo(); // you are not allowed using this approach
    Foo foo = new Foo();
    MWAHAHAHA, THIS LINE GIVES A COMPILE ERROR! NO STACKOVERFLOW EXCEPTION ANYMORE! LOL
}
class Program
{
    static void Main(string[] args)
    {
        new Foo();
    }
}

```
> 31 votes

# Answer
How about this?

```
class Foo
{
    //static Foo foo = new Foo(); // you are not allowed using this approach
    //static readonly Foo foo = new Foo(); // you are not allowed using this approach
    String str = @"
    Foo foo = new Foo();
    ";
}
class Program
{
    static void Main(string[] args)
    {
        new Foo();
    }
}

```
> 25 votes

# Answer
```
class Foo
{
    public class Bar
    {
        Foo foo = new Foo();
    }
}
class Program
{
    static void Main(string[] args)
    {
        new Foo();
    }
}

```

I don't have a C# compiler at hand, but I suspect this might work. The idea is to put the definition in a nested class, such that `foo` would only be assigned if an instance of `Bar` is created. Now, the problem is that (I believe) the nested class needs to be `public`. I don't know if this is a rule violation, i.e. that the rule applies to any use of an access modifier, or only if applied to `foo`. (Could someone who can compile C# please try this with and without the `public`?)
> 14 votes

# Answer
```
class Foo
{
    Foo(bool recursion = false)
    {
        if (recursion)
            Foo foo = new Foo();
    }
}
class Program
{
    static void Main(string[] args)
    {
        new Foo();
    }
}

```
> 8 votes

# Answer
To simplify Florent's code:

```
class Foo
{
    Foo foo = new Foo();

    static Foo() {
        System.Environment.Exit(1);
    }

}

```
> 8 votes

# Answer
```
class Foo
{
    while (true);
    Foo foo = new Foo();
}
class Program
{
    static void Main(string[] args)
    {
        new Foo();
    }
}

```

Its not a bug, it's a feature!

In case that doesn't work

```
class Foo
    if(false)
        Foo foo = new Foo();
}

class Program
{

    static void Main(string[] args)
    {
        new Foo();
    }
}

```
> 3 votes

# Answer
The Answer is:

```
class Foo
{
    //static Foo foo = new Foo(); // you are not allowed using this approach
    //static readonly Foo foo = new Foo(); // you are not allowed using this approach

    public void Method()
    {
    Foo foo = new Foo();
    }
}
class Program
{
    static void Main(string[] args)
    {
        new Foo();
        Console.ReadLine();
    }
}

```
> 3 votes

# Answer
**Note: The rules changed since I posted this.**

That is it:

```
class Foo
{
    //static Foo foo = new Foo(); // you are not allowed using this approach
    //static readonly Foo foo = new Foo(); // you are not allowed using this approach
    Foo foo = null; // Removing code != modifying.
}
class Program
{
    static void Main(string[] args)
    {
        new Foo();
    }
}

```
> 1 votes

# Answer
```
class Foo
{
    //static Foo foo = new Foo(); // you are not allowed using this approach
    //static readonly Foo foo = new Foo(); // you are not allowed using this approach
    Foo foo = true?null: new Foo();
}
class Program
{
    static void Main(string[] args)
    {
        new Foo();
    }
}

```
> 0 votes

---
Tags: programming-puzzle, c#
---


title: Concatenate Strings with Context

text:
# Question
Title: Concatenate Strings with Context
# Strings with Context

For the purposes of this challenge, a *string with context* is a triple of strings, called the *left context*, the *data part*, and the *right context*. It represents a substring of a longer string. We use the vertical pipe `|` as a separator, so an example of a string with context is `cod|e-go|lf`, where the left context is `cod`, the data is `e-go`, and the right context is `lf`. This example represents the substring `e-go` of `code-golf`.

Now, to concatenate two strings with context, we proceed as follows, using `aa|bcc|dee` and `cc|de|eee` as examples. We align the strings as in the diagram

```
a a|b c c|d e e
      c c|d e|e e e

```

so that their data parts are adjacent. The data part of the concatenation is the concatenation of the data parts, in this case `bccde`. The left context is the part that extends the furthers to the left of the first data part, in this case `aa`. Similarly, the right context is `eee`, so the concatenation is the string with context `aa|bccde|eee`. For a second example, consider `a|bb|cd` and `aabb|cd|`, where the second word has a empty right context. The alignment diagram is

```
  a|b b|c d
a a b b|c d|

```

where the left context of the second word extends further than that of the first. The concatenation is `aa|bbcd|`.

But wait, there's a gotcha: if the letters of the alignment diagram don't match, the concatenation doesn't exist! As an example, the diagram of `aa|bb|cc` and `c|c|c` is

```
a a|b b|c c
      c|c|c

```

where the `b` and `c` on the fourth column disagree, so they cannot be concatenated.

# The Task

Your job is to write a program that takes in two strings with context whose parts are separated by `|` as above, and outputs their concatenation if it exists, and something else if not. The "something else" can be any value, including no output, as long as it's not a valid string with context, and it is the same in all cases. However, throwing an error is not acceptable. You can give either a STDIN-to-STDOUT program or a function, and anonymous functions are accepted as well. The smallest byte count wins, and standard loopholes are disallowed.

# Test Cases

```
aa|bcc|dee cc|de|eee -> aa|bccde|eee
a|bb|cd    aabb|cd|  -> aa|bbcd|
a|b|cccd   aab|cc|c  -> aa|bcc|cd
a|b|c      b||cd     -> a|b|cd
aa|bb|cc   c|c|c     -> None
aaa|b|c    abb|cd|d  -> None
|bb|cd     abb|c|ed  -> None
a|b|c      a||cd     -> None

```

# Answer
# Haskell, ~~184~~ ~~182~~ ~~201~~ ~~199~~ 155

```
s&t|(a,'|':b)<-f t,(x,'|':y)<-f$r s,x#b,a#y=r(y!r a)++b!r x|0<1=""
r=reverse
a!b=a++drop(length a-1)b
(#)a=and.zipWith(==)(r a).filter h
f=span h
h=(/='|')

```

example run:

```
"|a|"&"|b|" -- returns "|ab|"
"|a|x"&"|b|" -- returns ""

```

if there isn't a match an empty string will be returned. otherwise the result would be returned.

**partial explanation:**

`#` is a function which gets two strings, and returns whether or not they match.

`!` gets two strings and returns the first one concatenated with extra character from the second (if there are any).

the main function `&` uses `span (/='|')` to split the inputs into two parts, `a|b|c` to `a, b|c`, checks if the contexts match, and then uses `!` twice to assemble the output.

**Edit:** mage-late regolfing seems to be pretty effective.
> 4 votes

# Answer
# Python (242 bytes)

```
import itertools as i
s='|'
j=''.join
r=reversed
m=lambda a,b:j(j(*set(p+q))for p,q in i.izip_longest(a,b,fillvalue=''))
def c(A,B):
 u,v,w,x,y,z=(A+s+B).split(s)
 try:return j(r(m(r(u+v),r(x))))[:-len(v)]+s+v+y+s+m(w,y+z)[len(y):]
 except:0

```

## Explanation

The lambda function `m` returns the longer of two strings as long as they share a common prefix. It does this by concatenating the empty string `''` in place of any missing values, then turning the result (which may take the forms `aa`, `ab`, `a`, or `b` in cases of match/mismatch/unequal lengths) into a set of unique characters at each position. `join` expects a single argument, so unpacking a set with more than one element will cause it to raise a `TypeError`.

The main function then

* uses `m` to combine the *left context and data part* the first word with the *left context* of the second (from right to left over reversed strings)
* concatenates data parts,
* and again uses `m` to combine the *right context of the first word* with the *data part and right context* of the second

The two original words' data parts are trimmed from the right and left sides of the new contexts.

Since we know that misalignments cause `m` to raise a `TypeError`, in these cases we catch the exception and implicitly return `None`.

## Testing

```
TESTCASES = [
    ('aa|bcc|dee', 'cc|de|eee', 'aa|bccde|eee'),
    ('a|bb|cd', 'aabb|cd|', 'aa|bbcd|'),
    ('a|b|cccd', 'aab|cc|c', 'aa|bcc|cd'),
    ('a|b|c', 'b||cd', 'a|b|cd'),
    ('aa|bb|cc', 'c|c|c', None),
    ('aaa|b|c', 'abb|cd|d', None),
    ('|bb|cd', 'abb|c|ed', None),
    ('a|b|c', 'a||cd', None),
]

for A, B, R in TESTCASES:
    print '{:<10} {:<9} -> {}'.format(A, B, c(A, B))

```

## Output

```
aa|bcc|dee cc|de|eee -> aa|bccde|eee
a|bb|cd    aabb|cd|  -> aa|bbcd|
a|b|cccd   aab|cc|c  -> aa|bcc|cd
a|b|c      b||cd     -> a|b|cd
aa|bb|cc   c|c|c     -> None
aaa|b|c    abb|cd|d  -> None
|bb|cd     abb|c|ed  -> None
a|b|c      a||cd     -> None

```
> 3 votes

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


title: Mobius inversion

text:
# Question
Title: Mobius inversion
Your goal is to implement Möbius inversion, a linear operation on a sequence of numbers that is used in combinatorics and number theory. Fewest bytes wins.

**What is Möbius inversion?**

Given a (finite) integer sequence `f_1, f_2, ..., f_N`, we can compute its divisor-partial-sum `g`, whose `n`th element `g_n` is the sum of all terms `f_d` whose index `d` is a divisor of `n`.

```
g_n = sum_(d with d|n) [f_d]

g_1 = f_1
g_2 = f_1 + f_2
g_3 = f_1 + f_3
g_4 = f_1 + f_2 + f_ 4
g_5 = f_1 + f_5
g_6 = f_1 + f_2 + f_3 + f_6
...

```

The sequence `g` has the same length as `f`.

Möbius inversion is the process of inverting this operation -- recovering `f` from `g`. This inverse is unique and produces an integer sequence. A explicit but complicated way to compute it is the Möbius inversion formula, which expresses `f_n` as a weighted sum over divisors `d` of `n`:

```
f_n = sum_(d with d|n) [μ(d) * g_(n/d)]

```

and `μ` is the Möbius function:

```
μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
μ(n) = 0 if n has a squared prime factor.

```

**Program requirements**

Write a function or program to perform Möbius inversion. Fewest bytes wins. Built-in methods to perform Möbius inversion, do sequence convolution, compute the Möbius function (or related thing like checking squarefreeness), or solve systems of equations are not allowed.

**Input**

A sequence of integers of length at least 1. Can be any format that represents an ordered sequence: array, list, stack, token-separated string, etc. Unordered maps from the index to the element like dictionaries and functions are not OK. You're not given the length of the input sequence separately.

**Output**

Return or print the output sequence in any format, with same restrictions as input. It should be the same length as the input sequence.

**Test cases**

```
Input: [1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6]
Output:[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Input: [0, -3, 6, 5, 1, 7, 5, 0, 4, 0]
Output: [0, -3, 6, 8, 1, 4, 5, -5, -2, 2]

Input: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Output: [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1]

```

# Answer
> 5 votes
# J - 13 char

Anonymous function Mobius-inverting a sequence.

```
(%.0=#\|~/#\)

```

Here's what's going on:

* `#\` gets indices from 1 to the length of the input list, inclusive.
* `|~/` makes a table of indices modulo themselves.
* `0=` checks for equality to zero, 1 for true, 0 for false. On the table of moduli, this checks divisibility, returning a matrix like

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

```
* Finally, `%.` takes the input sequence and this matrix, and solves it as a linear system: `x` equal to `b %. A` is the solution to `Ax=b` if it exists. Our `b` is the input sequence and `A` is this divisibility matrix above.

In use: (Note that J spells its negative sign `_`)

```
   (%.0=#\|~/#\) 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 2 6 2 6
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
   (%.0=#\|~/#\) 0 _3 6 5 1 7 5 0 4 0
0 _3 6 8 1 4 5 _5 _2 2
   (%.0=#\|~/#\) 1 0 0 0 0 0 0 0 0 0 0 0 0
1 _1 _1 0 _1 1 _1 0 0 1 _1 0 _1

```

# Answer
> 2 votes
# Matlab/Octave (56)(53)(51)

51 chars:

```
i=input('');x=1:numel(i);disp(i/~bsxfun(@mod,x,x'))

```

53 chars:

```
i=input('');x=meshgrid(1:numel(i));disp(i/~mod(x,x'))

```

I basically set up system of linear equations in matrix form where the matrix looks like this (depending on the length, here the length is 6:

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

```

Then I just solve the corresponding system of equations.

The command `meshgrid(x)` is primarly inteded for producing matrices like

```
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

```

and

```
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

```

which can then be used as e.g. x and y coordinates for plotting 2d functions. I just use one of them for ceating a matrix with where the k-th column has is 0 every k-th element via elementwise remainder division (modulo). `~` as the logical `not` which replaces nonzero values with zeros and vice versa, which then results in the matrix above.

# Answer
> 2 votes
## Python, 99 chars

```
def I(g):
 f,e=[],enumerate
 for n,v in e(g):f+=[v-sum(x for i,x in e(f)if(n+1)%(i+1)<1)]
 return f

```

Computes `f` from `g` incrementally, so we can use the `f`s we've already calculated to compute larger `f`s.

# Answer
> 2 votes
# CJam, 67 bytes

This can be golfed further, but given that so many languages can solve linear equations with 1 character, I don't see a point in answering with any non-maths oriented language.

```
l~:F,,{):N,:){N\%!},{__mF{W=1>},,{;0}{_mF,\1=m2%W1?}?N@/(F=*}%:+}%p

```

This is the exact implementation of the Möbius inversion formula.

Try it online here

Takes input from STDIN in the following format:

```
[1 0 0 0 0 0 0 0 0 0 0 0 0]

```

and gives output line

```
[1 -1 -1 0 -1 1 -1 0 0 1 -1 0 -1]

```

# Answer
> 2 votes
# Haskell, 61

```
h g=[v-sum[h g!!n|n<-[0..i-2],rem i(n+1)<1]|(i,v)<-zip[1..]g]

```

this solves the equations one at a time using the already known values of `f`, using laziness.

this is inefficient in space and time complexity because it recomputes the result several times ( it's like the difference between `fix f=f(fix f)` and `fix f=r where r=f r`). a simple fix:

```
h g=r where [v-sum[r!!n|n<-[0..i-2],rem i(n+1)<1]|(i,v)<-zip[1..]g]

```

# Answer
> 1 votes
# Python 2, 84 chars

```
g=input()
i=1
for _ in g:g[i-1]-=sum(g[j-1]*(i%j<1)for j in range(1,i));i+=1
print g

```

Iterates through the entries, making each one what it needs to be for the sum to work out. Modifies the input list directly rather than making a new list.

---
Tags: code-golf, math, sequence
---


title: Undo the square roots

text:
# Question
Title: Undo the square roots
Your job is to convert decimals back into the sum of the square roots of integers. The result has to have an accuracy of at least 6 significant decimal digits.

**Input**:

A number indicating the number of square roots and a decimal indicating the number to approximate.

Example input:

```
2 3.414213562373095

```

**Output**: Integers separated by spaces that, when square rooted and added, are approximately the original decimal accurate to at least 6 significant decimal digits.

Zeros are not allowed in the solution.

If there are multiple solutions, you only have to print one.

Example output (in any order):

```
4 2

```

This works because `Math.sqrt(4) + Math.sqrt(2) == 3.414213562373095`.

This is code golf. Shortest code (with optional bonus) wins!

There is always going to be a solution but -10 if your program prints "No" when there is no solution with integers. In addition, -10 if your program prints all solutions (separated by newlines or semicolons or whatever) instead of just one.

Test cases:

```
3 7.923668178593959 --> 6 7 8
2 2.8284271247461903 --> 2 2
5 5.0 --> 1 1 1 1 1
5 13.0 --> 4 4 9 9 9 --> 81 1 1 1 1 --> 36 9 4 1 1 etc. [print any, but print all for the "all solutions bonus"]

```

And yes, your program has to finish in finite time using finite memory on any reasonable machine. It can't just work "in theory," you have to be able to actually test it.

# Answer
> 9 votes
# Python 3, 90 - 10 = 80

```
def S(N,x,n=[],i=1):
 if x*x<1e-12>N==0:print(*n)
 while.1+x*x>i:S(N-1,x-i**.5,n+[i]);i+=1

```

*(Mega thanks to @xnor for tips, especially the restructuring of the for loop into a while)*

A simple recursive attempt. It starts off with the target number and continuously subtracts square roots until it hits 0 or lower. The function `S` can be called like `S(2,3.414213562373095)` (the second argument is assumed to be positive).

The program doesn't just print out all solutions, it prints out all *permutations* of solutions (a little extraneous, I know). Here's the output for the last case: Pastebin.

A slight tweak gives a **98 - 10 = 88** solution which doesn't print permutations, making it more efficient:

```
def S(N,x,n=[]):
 *_,i=[1]+n
 if x*x<1e-12>N==0:print(*n)
 while.1+x*x>i:S(N-1,x-i**.5,n+[i]);i+=1

```

And just for fun, this **99 - 10 = 89** one is about as efficient as it gets (unlike the others, it doesn't blow the stack on `S(1,1000)`:

```
def S(N,x,n=[]):
 *_,i=[1]+n
 if x*x<1e-12>N:print(*n)
 while(.1+x*x>i)*N:S(N-1,x-i**.5,n+[i]);i+=1

```

*Note that, although we have a mutable default argument, this never causes a problem if we rerun the function since `n+[i]` creates a new list.*

---

## Proof of correctness

In order to end up in an infinite loop, we must hit some point where *x \< 0* and *0.1 + x2 \> 1*. This is satisfied by *x \< -0.948...*.

But note that we start from positive *x* and *x* is always decreasing, so in order to hit *x \< -0.948...* we must have had *x' - i0.5 \< -0.948...* for some *x' \> -0.948...* before *x* and positive integer *i*. For the while loop to run, we must also have had *0.1 + x'2 \> i*.

Rearranging we get *x'2 \+ 1.897x' + 0.948 \< i \< 0.1 + x'2*, the outer parts implying that *x' \< -0.447*. But if *-0.948 \< x' \< -0.447*, then no positive integer *i* can fit the gap in the above inequality.

Hence we'll never end up in an infinite loop.

# Answer
> 6 votes
## ECLiPSe Prolog - 118 (138-20)

I used the following implementation of Prolog: http://eclipseclp.org/

```
:-lib(util).
t(0,S,[]):-!,S<0.00001,S> -0.00001.
t(N,S,[X|Y]):-A is integer(ceiling(S*S)),between(1,A,X),M is N-1,T is S-sqrt(X),t(M,T,Y).

```

This is a very naive, exponential approach. Listing all possible solutions takes time to cover all combinations (*edit*: the range of visited integers now decreases at each step, which removes a lot of useless combinations).

Here follows a transcript of a test session. By default, the environment will try to find all possible solutions (-10) and prints "No" when it fails to do so (-10).

As Sp3000 properly noted in the comment, it also prints "Yes" when it succeeds. That surely means I can remove 10 more points ;-)

```
[eclipse 19]: t(1,0.5,R).

No (0.00s cpu)
[eclipse 20]: t(2,3.414213562373095,R).

R = [2, 4]
Yes (0.00s cpu, solution 1, maybe more) ? ;

R = [4, 2]
Yes (0.00s cpu, solution 2, maybe more) ? ;

No (0.01s cpu)
[eclipse 21]: t(3,7.923668178593959,R).

R = [6, 7, 8]
Yes (0.02s cpu, solution 1, maybe more) ? ;

R = [6, 8, 7]
Yes (0.02s cpu, solution 2, maybe more) ? ;

R = [7, 6, 8]
Yes (0.02s cpu, solution 3, maybe more) ?
[eclipse 22]: t(5,5.0,R).

R = [1, 1, 1, 1, 1]
Yes (0.00s cpu, solution 1, maybe more) ? ;
^C

interruption: type a, b, c, e, or h for help : ? abort
Aborting execution ...
Abort
[eclipse 23]: t(5,13.0,R).

R = [1, 1, 1, 1, 81]
Yes (0.00s cpu, solution 1, maybe more) ? ;

R = [1, 1, 1, 4, 64]
Yes (0.00s cpu, solution 2, maybe more) ? ;

R = [1, 1, 1, 9, 49]
Yes (0.00s cpu, solution 3, maybe more) ?
[eclipse 24]:

```

---

**(Edit)** Regarding performance, it is quite good, at least compared to other ones (see for example this comment from FryAmTheEggman). First, if you want to print all results, add the following predicate:

```
    p(N,S):-t(N,S,L),write(L),fail.
    p(_,_).

```

See http://pastebin.com/ugjfEHpw for the (5,13.0) case, which completes in 0.24 seconds and find 495 solutions (but maybe I am missing some solutions, I don't know).

# Answer
> 3 votes
# Erlang, ~~305-10~~ 302-10

```
f(M,D)->E=round(D*D),t(p(E,M,1),{M,E,D}).
p(_,0,A)->A;p(E,N,A)->p(E,N-1,A*E).
t(-1,_)->"No";t(I,{N,E,D}=T)->L=q(I,N,E,[]),V=lists:sum([math:sqrt(M)||M<-L])-D,if V*V<0.1e-9->lists:flatten([integer_to_list(J)++" "||J<-L]);true->t(I-1,T)end.
q(I,1,_,A)->[I+1|A];q(I,N,E,A)->q(I div E,N-1,E,[I rem E+1|A]).

```

This function returns string "No" or a string with values separated by spaces. It (inefficiently) processes every possible values encoding them into a large integer, and starting with higher values. 0 are not allowed in the solution, and encoded 0 represents all ones. Error is squared.

Example:

```
f(1,0.5).               % returns "No"
f(2,3.414213562373095). % returns "4 2 "
f(3,7.923668178593959). % returns "8 7 6 "
f(5,5.0).               % returns "1 1 1 1 1 "
f(5,13.0).              % returns "81 1 1 1 1 "

```

Please be patient with `f(5,13.0)` as function search space is 13^10. It can be made faster with 2 additional bytes.

# Answer
> 3 votes
### Python ~~3~~ 2: ~~173~~ 159 - 10 = 149

Explanation: Each solution is of the form x\_1 x\_2 ... x\_n with 1 \<= x\_1 \<= x^2 where x is the target sum. Therefore we can encode each solution as an integer in base x^2. The while loop iterates over all (x^2)^n possibilities. Then I convert the integer back and test the sum. Pretty straight forward.

```
i=input;n=int(i());x=float(i());m=int(x*x);a=m**n
while a:
 s=[a/m**b%m+1for b in range(n)];a-=1
 if abs(x-sum(b**.5for b in s))<1e-5:print' '.join(map(str,s))

```

It finds all solutions, but the last test case takes way too long.

# Answer
> 3 votes
# JavaScript (ES6) 162 (172 - 10) ~~173~~

*Edit* A little shorter, a little slower.

As a function with 2 parameters, output to javascript console. This prints all solutions with no repetitions (solutions tuples are generated already sorted).
I cared more about timing than about char count, so that it's easily tested in a browser console within the standard javascript time limit.

(Feb 2016 update) Current time for last test case: about 1 ~~150 secs~~. Memory requirements: negligible.

```
F=(k,t,z=t- --k,r=[])=>{
  for(r[k]=z=z*z|0;r[k];)
  {
    for(;k;)r[--k]=z;
    for(w=t,j=0;r[j];)w-=Math.sqrt(r[j++]);
    w*w<1e-12&&console.log(r.join(' '));
    for(--r[k];r[k]<1;)z=--r[++k];
  }
}

```

**ES 5 Version** Any browser

```
function F(k,t)
{
  var z=t- --k,r=[];
  for(r[k]=z=z*z|0;r[k];)
  {
    for(;k;)r[--k]=z;
    for(w=t,j=0;r[j];)w-=Math.sqrt(r[j++]);
    w*w<1e-12&&console.log(r.join(' '));
    for(--r[k];r[k]<1;)z=--r[++k];
  }
}

```

**Test Snippet** it should run on any *recent* browser

```
F=(k,t)=>
{
   z=t- --k,r=[];
   for(r[k]=z=z*z|0;r[k];)
   {
      for(;k;)r[--k]=z;
      for(w=t,j=0;r[j];)w-=Math.sqrt(r[j++]);
      w*w<1e-12&&console.log(r.join(' '));
      for(--r[k];r[k]<1;)z=--r[++k];
   }
}

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

t=~new Date
console.log('\n2, 3.414213562373095')
F(2, 3.414213562373095)
console.log('\n5, 5')
F(5, 5)
console.log('\n3, 7.923668178593959')
F(3, 7.923668178593959)
console.log('\n5, 13')
F(5, 13)

t-=~new Date
O.textContent = 'Total time (ms) '+t+ '\n'+O.textContent
```

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

(**Edit**) Below are the result on my PC when I posted this answer 15 months ago. I tried today and it is 100 times faster on the same PC, just with a 64 bit alpha version of Firefox (and Chrome lags well behind)! - current time with Firefox 40 Alpha 64 bit: ~2 sec, Chrome 48: ~29 sec

*Output* (on my PC - last number is runtime in milliseconds)

```
2 4
1 1 1 1 1
6 7 8
1 1 1 1 81
1 1 1 4 64
1 1 1 9 49
1 1 4 4 49
1 1 1 16 36
1 1 4 9 36
1 4 4 4 36
1 1 1 25 25
1 1 4 16 25
1 1 9 9 25
1 4 4 9 25
4 4 4 4 25
1 1 9 16 16
1 4 4 16 16
1 4 9 9 16
4 4 4 9 16
1 9 9 9 9
4 4 9 9 9
281889

```

# Answer
> 2 votes
## Pyth ~~55 54~~ 47-20 = 27

```
DgGHKf<^-Hsm^d.5T2^10_12^r1hh*HHGR?jbmjdkKK"No

```

Try it online.

Shamelessly *borrows* from xnor's comment ;)

This will run out of memory on any sane computer even for a value like `5,5.0`. Defines a function, `g`, that can be called like `g 3 7.923668178593959`.

This python 3 program uses essentially the same algorithm (just doesn't do the "No" printing at the end, which could be done by assigning a variable to all the results, then writing `print(K if K else "No")`), but uses a generator, so it doesn't get a memory error (it will still take extremely long, but I've made it print as it finds the values):

This gave the exact same results that @Sp3000 got. Also, this took several days to finish (I didn't time it, but around 72 hours).

```
from itertools import*
def g(G,H):
    for x in product(range(1,int(H*H+2)),repeat=G):
        if (H-sum(map(lambda n:n**.5,x)))**2<1e-12:print(*x)

```

# Answer
> 2 votes
# Mathematica - 76 - 20 = 56

```
f[n_,x_]:=Select[Union[Sort/@Range[x^2]~Tuples~{n}],Abs[Plus@@√#-x]<10^-12&]

```

Examples

```
f[2, 3.414213562373095]
> {{2, 4}}
f[3, 7.923668178593959]
> {{6, 7, 8}}
f[3, 12]
> {{1, 1, 100}, {1, 4, 81}, {1, 9, 64}, {1, 16, 49}, {1, 25, 36}, {4, 4, 64}, {4, 9, 49}, {4, 16, 36}, {4, 25, 25}, {9, 9, 36}, {9, 16, 25}, {16, 16, 16}}

```

# Answer
> 2 votes
# Haskell, 87 80 - 10 = 70

This is a recursive algorithm similar to the Python 3 program of @Sp3000. It consists of an infix function `#` that returns a list of all permutations of all solutions.

```
0#n=[[]|n^2<0.1^12]
m#n=[k:v|k<-[1..round$n^2],v<-(m-1)#(n-fromInteger k**0.5)]

```

With a score of **102 99 92 - 10 = 82** we can print each solution only once, sorted:

```
0#n=[[]|n^2<0.1^12]
m#n=[k:v|k<-[1..round$n^2],v<-(m-1)#(n-fromInteger k**0.5),m<2||[k]<=v]

```

# Answer
> 1 votes
# Python 3 - ~~157~~ ~~174~~ 169 - 10 = 159

Edit1: Changed the output format to space-separated integers instead of comma-separated. Thanks for the tip of removing the braces around (n,x).

Edit2: Thanks for the golfing tips! I can trim off another 9 chars if I just use an == test instead of testing for approximate equality to within 1e-6, but that would invalidate approximate solutions, if any such exist.

Uses itertools to generate all possible integer combinations, hopefully efficiently :)

I haven't found a way to add printing "No" efficiently, it always seems to take more than 10 extra characters.

```
from itertools import*
n,x=eval(input())
for c in combinations_with_replacement(range(1,int(x*x)),n):
 if abs(sum(z**.5for z in c)-x)<1e-6:print(' '.join(map(str,c)))

```

# Answer
> 0 votes
## Scala (397 bytes - 10)

```
import java.util.Scanner
object Z extends App{type S=Map[Int,Int]
def a(m:S,i:Int)=m updated(i,1+m.getOrElse(i,0))
def f(n:Int,x:Double):Set[S]={if(n==0){if(x.abs<1e-6)Set(Map())else Set()}
else((1 to(x*x+1).toInt)flatMap{(i:Int)=>f(n-1,x-Math.sqrt(i))map{(m:S)=>a(m,i)}}).toSet}
val s=new Scanner(System.in)
f(s.nextInt,s.nextDouble)foreach{(m:S)=>m foreach{case(k,v)=>print(s"$k "*v)};println}}

```

If there are no permutations, then this program prints nothing.

---
Tags: code-golf, arithmetic
---


title: Cyclically Equivalent Words

text:
# Question
Title: Cyclically Equivalent Words
# Cyclic Equivalence

Let `L` be a list of pairs of letters, for example `[(a,b), (a,c)]`. We call `L` a *list of commutators*. Two words are *cyclically equivalent over* `L`, if one can be transformed into the other using the following operations:

1. Cyclic shift: pop a letter from the beginning, and push it to the end.
2. Commutator swap: if the word begins with two letters that appear in `L` in either order, swap those letters.

For example, the words `acabd` and `dcaba` are cyclically equivalent over `L`, since we have the sequence of operations `acabd -> caabd -> aabdc -> abdca -> badca -> adcab -> dcaba`. However, the words `acabd` and `acdab` are not cyclically equivalent, since the letters `b`, `c` and `d` cannot be swapped with each other, so they can occur only in the order `cbd`, `dcb` or `bdc` in words that are cyclically equivalent to `acbad`.

# The Challenge

You are given as input two words, and a list of commutators. You program should output a truth-y value (`True`, `1`, etc.) if the words are cyclically equivalent over the list, and a false-y value (`False`, `0`, etc.) otherwise. You **don't** have to output a sequence of operations in the positive case. The shortest answer (in bytes) is the winner.

# Test Cases

```
[(a,b), (a,c)] acabd dcaba -> True
[(a,b), (a,c)] acabd acdab -> False
[(a,b), (a,d), (b,c), (b,d)] cdaddccabbdcddcababaaabbcbdccaccacdddacdbccbddaacccaddbdbbcadcccadadccbaaabdbcc ddcadbbcccdadbabcbcaadaccbbcdddaccdacddcababaaacbbdbccaccbacddadcdccaddabcbccda -> True
[(a,b), (a,d), (b,c), (b,d)] cdaddccabbdcddcababaaabbcbdcccacacdddacdbccbddaacccaddbdbbcadcccadadccbaaabdbcc ddcadbbcccdadbabcbcaadaccbbcdddaccdacddcababaaacbbdbccaccbacddadcdccaddabcbccda -> False

```

# Clarifications

* You can write either a function or a STDIN-to-STDOUT program.
* The list of commutators can be given as a comma-separated string, a list of length-two strings, or a list of pairs of characters.
* You can assume that the input words only contain alphanumeric ASCII symbols.
* Your program should be able to process inputs of length 100 in a matter of seconds.
* Standard loopholes are disallowed.

# Answer
> 3 votes
# Python 413

Pretty efficient, although it does sacrifice a small amount of speed for length, such as calculating things every pass of a small for loop rather than precalculating it. I̶t̶ ̶s̶t̶i̶l̶l̶ ̶o̶u̶t̶p̶u̶t̶s̶ ̶a̶l̶l̶ ̶t̶h̶e̶ ̶t̶e̶s̶t̶ ̶c̶a̶s̶e̶s̶ ̶i̶n̶ ̶w̶e̶l̶l̶ ̶u̶n̶d̶e̶r̶ ̶a̶ ̶s̶e̶c̶o̶n̶d̶.̶

**Edit:** I had to fix a bug which now makes it significantly less efficient for larger inputs.

```
X,Y,L=input();S=sorted;T=type
def E(s,c):
 l=[[]]
 for h in s:
    if h==c:l+=[h]
    elif all(h!=[b,a][j]for a,b in L for j,n in[(0,a),(1,b)]if n==c):
     if T(l[-1])==str:l+=[[]]
     l[-1]=S(l[-1]+[h])
 if T(l[0])==T(l[-1])!=str:return[l[0]+l[-1]]+l[1:-1]+[len(l[-1])]
 return l+[0]
print any(0==cmp(*[[E(s,c)for c in S(set(s))]for s in [X[j:]+X[:j],Y[i:]+Y[:i]]])for i in range(len(Y))for j in range(len(X)))

```

Test Cases

```
"acb", "abc", [('a','b')]
True (0 ms)

'acabd','dcaba',[('a','b'),('a','c')]
True (1 ms)

'acabd','acdab',[('a','b'),('a','c')]
False (2 ms)

'cdaddccabbdcddcababaaabbcbdccaccacdddacdbccbddaacccaddbdbbcadcccadadccbaaabdbcc','ddcadbbcccdadbabcbcaadaccbbcdddaccdacddcababaaacbbdbccaccbacddadcdccaddabcbccda',[('a','b'), ('a','d'), ('b','c'), ('b','d')]
True (62 ms)

'cdaddccabbdcddcababaaabbcbdcccacacdddacdbccbddaacccaddbdbbcadcccadadccbaaabdbcc','ddcadbbcccdadbabcbcaadaccbbcdddaccdacddcababaaacbbdbccaccbacddadcdccaddabcbccda',[('a','b'), ('a','d'), ('b','c'), ('b','d')]
False (6963 ms)

```

The basic algorithm does the following. For each letter, L, present, loop through the string constructing a list; anytime it encounters L it appends it to the list, any group of adjacent letters which can *not* be switched with L it appends to the list sorted, letters which can be switched with L are ignored.

For example when considering `'acabd'` with the pairs `[('a','b'),('a','c')]`, we would construct:

```
a : a, a, [d]
b : [c], b, [d] *
c : c, [b,d]
d : [a,a,b,c], d

```

which is equivalent to the result we get when we apply this to `'cabad'` (`'dcaba'` shifted)

\*Note here that the `[c]` and `[d]` should be considered one list

What is basically being done, is confirming for each letter that the order of it and the letters it can't switch with are the same. Since they cannot switch, they cannot 'pass' each other, so if the first string has two `a`s followed by two `d`s followed by one `a` followed by one `d` than no matter how it's manipulated it can't be transformed into a string which has three `a`s followed by three `d`s. Of course the order of the letters that it can't switch with is not an issue (they might be paired with each other and switchable), but their counts are, hence the sorting of the lists before comparison. In addition it's clear that any letters that *can* be switched don't matter at all for the purposed of comparison.

Using this algorithm the program could be made significantly more efficient; currently it loops through every possible transposition of *both* strings and compares them due to some issues with comparing cases in which there were lists bordering the beginning and end.

# Answer
> 1 votes
# Haskell, 409

not fully golfed yet.

```
import Data.List
r((c,h):s)|l<-r s,(x,y)<-partition(\s->any(`elem`s)[c,h])l=nub(c:h:concat x):y
r _=[]
k s d|l<-sort$nub s=r[(x,y)|x<-l,y<-l,notElem(x,y)d,notElem(y,x)d,x/=y]
m a b c|elem c[a,b]=c|0<1=' '
e s d=[nub[map(m x y)s|x<-g,y<-g,notElem(x,y)d,notElem(y,x)d,x/=y]|g<-k s d]
q a b=and$zipWith(\a b->or[n a==n[drop i s++take i s|s<-b]|i<-[0..length$a!!0]])a b
f a b d=q(e a d)(e b d)
n=map$filter(/=' ')

```

this works on all the test cases.

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


# Question
Title: Algorithm - Costliest Possible Route in Grid Puzzle
### Objective

Find the most expensive path from the top-left of a square grid to the bottom-right such that its total cost is below a given threshold.

### Scenario

1. You are given a square `NxN` grid.
2. You are given a maximum cost.
3. Every cell in the grid has a cost. The top-left cell has cost `0`.
4. The cost of a path is the sum of the costs of the cells in the path. Its "cost surplus" is the result of subtracting its cost from the maximum cost.
5. Movement is always either right one cell or down one cell.
6. The starting point is the top-left cell of the grid and the goal is the bottom-right cell.
7. You must output the smallest cost surplus of any path with a non-negative cost surplus, or -1 if there is no such path (The maximum cost is not enough).

### Input restrictions

1. `N` will be between 1 and 20 inclusive.
2. The maximum cost will be between 1 and 200 inclusive.
3. The cost of each cell will be between 0 and 10 inclusive.

### Examples

1. Maximum cost: 9
Grid:

```
0 1 5
2 3 2
2 3 2

```

Expected output: 0
Explanation: there is a path `0 2 2 3 2` with cost 9 and cost surplus 0.
2. Maximum cost: 15
Grid:

```
0 1 5
2 3 2
2 3 2

```

Expected output: 5
Explanation: the most expensive path is `0 1 5 2 2` with cost 10 and cost surplus 5.
3. Maximum cost: 6
Grid:

```
0 1 5
2 3 2
2 3 2

```

Expected output: -1
Explanation: the least expensive path is `0 1 3 2 2` with cost 8, which is greater than 6.

# Answer
> 3 votes
## GolfScript (53 bytes)

```
~.,[1]*\{[[\]0\zip{~2$|2@?*}/](;}/-1=2.$)?|2base\~>1?

```

Expects input in the format

```
15 [[0 1 5][2 3 2][2 3 2]]

```

Online demo which covers three test cases.

The approach is to build up a list of possible running totals to each cell as a bitmask, extract the relevant lower bits, base-convert to a list of `0` and `1`, and look for the index of the first `1`.

### Dissection

```
~              # Eval input: puts N and grid on the stack
.,[1]*         # Set up initial row cost bitmask: 2^0 for each column
\{             # For each row in grid:
  [            #   Stack: N prev-row-bitmask this-row-cost
    [\]0\zip   #   Pair up prev-row-bitmask and this-row-cost and push 0 under them
    {          #   For each pair:
      ~        #     Stack: N left-cell-bitmask cost up-cell-bitmask
      2$|2@?*  #     this-cell-bitmask = (left-cell-bitmask | up-cell-bitmask) << cost
    }/
  ](;          #   Gather row into an array and drop the 0 we inserted for the -1th cell
}/
-1=            # Take the bitmask of the bottom-right cell. Stack: N bottom-right-bitmask
2.$)?|         # Or 2^N to ensure that we get enough bits from the base conversion
2base          # Base conversion
\~>            # Take the last (least significant) N+1 bits
1?             # Find the first index (hence smallest cost surplus) of the value 1

```

# Answer
> 3 votes
# CJam, ~~72~~ 71 bytes

```
q~:Q,mqi:L(2*0aa\{{_[~__)L%1L?+]\[~__L/)L=1L?+]}%}*{Qf=:+}%f-{W>},$W+0=

```

This is really long and I think a different approach to the question is the only way to get it shorter.

Try it online here

Input is in the following format : `<Steps> [<Flat Grid>]` . For ex:

```
9 [0 1 5 2 3 2 2 3 2]

```

And output is the cost remaining, so `1` in above example.

\*Note that `[0 1 5 2 3 2 2 3 2]` is just a flat representation of the grid

```
0 1 5
2 3 2
2 3 2

```

**How it works** (slightly outdated):

```
q~                                     "Read the input and evaluate it";
  :Q                                   "Store the array in Q";
    ,mqi:L                             "Do floor of square root of its length";
          LL+((                        "Double length and decrease 2 from the double";
               0aa                     "Put [[0]] on stack. This is the starting index"
                                       "for any path in the grid";
                  \{ ... }*            "Swap to but L + L - 1 on top and run the code"
                                       "block that many times";
 {{_[~__)L%1L?+]\[~__L/)L=1L?+]}%}*    "This block calculates indexes of all possible";
                                       "paths from top left to bottom right of the grid";
 {                            }%       "Map each array based on this code block";
  _[~                                  "Copy the array and start a new array with the"
                                       "contents of the copied one";
     __                                "Make two copies of the last element of the array";
       )L%                             "Increment the element and calculate module L";
          1L?                          "Choose L if module is 0, 1 otherwise";
             +]                        "Add it to the copy of last array element. With"
                                       "this, we have created one of the two possible"
                                       "next step, that is going right. Except if we are"
                                       "on the last column, then go down";
               \[~                     "Swap and start a new array with contents of"
                                       "the original array";
                  __                   "Make two copies of the last element";
                    L/)                "Divide the 2nd copy by L and add 1 to the result";
                       L=1L?           "If index belongs to last row, choose 1, else L";
                            +]         "Add to the first copy of last element and close"
                                       "the array. Now we have the second possible next"
                                       "step, i.e. going down. But if we are on last row"
                                       "then go right";
{Qf=:+}%                               "Map this block on the array containing all"
                                       "possible path indexes";
 Qf=                                   "Get the corresponding cell amount array";
    :+                                 "Sum the array elements to get total path cost";
        {1$)<},                        "Filter out paths which are not possible. i.e."
                                       "paths having total cost more than first input";
               $W=                     "Sort and get the last (highest) path cost";
                  -                    "decrement from input to get remaining steps";

```

# Answer
> 2 votes
# VBScript 191

This assumes that the array is in a variable called A and the cost is in a variable called c.

```
Dim M
Sub f(s,i,j,v)
If i>s And j=s And v<=c And M<v Then M=v
If i>s Or j>s Then Exit Sub
f s,i+1,j,v+A(i)(j)
f s,i,j+1,v+A(i)(j)
End Sub
f UBound(A),0,0,0
If M=0Then MsgBox-1 Else MsgBox c-M

```

To run it put the following lines at the top of a file called x.vbs then paste in the code above and just double click or execute `cscript x.vbs`

```
A=Array(Array(0,1,5),Array(2,3,2),Array(2,3,2))
c=6

```

# Answer
> 1 votes
# CJam, ~~71~~ ~~69~~ 68 bytes

I didn't look at anything from Optimizer's answer, except its size and input format... so the size is complete coincidence. But I think this can be golfed a fair bit.

```
l~:L,mqi(:X2*2\#:Y[{IY+2b(;_:+X={0_@{X*)+_L=@+\}/}*;}fI]f-{W>},$W+0=

```

Test it here.

The input on STDIN is in the form of the maximum steps and the *unrolled* grid as a CJam array:

```
9 [0 1 5 2 3 2 2 3 2]

```

Explanation:

```
"Prepare input:";
l~:L,mqi(:X2*2\#:Y
l~                    "Read and eval input.";
  :L                  "Store grid in L.";
    ,mqi(:X           "Get length, square root, cast to int, decrement, store in X.";
           2*2\#:Y    "Multiply by 2, raise 2 to this power, store in Y.";

[{...}fI]             "For I in 0 to Y-1. Collect in array.";

"Determine path:";
IY+2b(;_:+X=
IY+                   "I + Y.";
   2b                 "Convert to base 2.";
     (;               "Drop leading 1.";
       _:+            "Duplicate and sum.";
          X=          "Check for equality with X.";

{...}*                "If equals, execute this (otherwise, don't).":

"Determine remaining weight:";
0_@{X*)+_L=@+\}/
0                     "Push 0. This is the sum.";
 _                    "Push another 0. This is the current position in the grid.";
  @                   "Pull up path description. 1 -> down, 0 -> right.";
   {          }/      "For each step...";
    X*)               "Multiply by X, increment.";
       +              "Add to current position.";
        _L=           "Duplicate and extract grid element.";
           @+         "Pull up sum and add.";
             \        "Swap with position.";

;                     "Pop... either the invalid path or the last position.";

f-                    "Subtract each sum from the maximum step number.";
  {W>},               "Filter out negative results.";
       $              "Sort.";
        W+            "Append a -1.";
          0=          "Take the first element.";

```

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