title: Calculate longest Stack Exchange streak

text:
# Question
Title: Calculate longest Stack Exchange streak
### Introduction

This challenge is inspired by the Meta Stack Exchange question The longest consecutive days streak; it turns out that the URL `https://codegolf.stackexchange.com/users/daily-site-access/[user id]`, where the last number is your user ID (found in the URL of your profile) contains information about which days you visited the site, in the following format:

```
var visited = {2015:{6:{3:1,8:1,12:1,13:1,18:1,19:1,21:1,22:1,23:1,24:1,26:1},7:{7:1,8:1,9:1,10:1,11:1,12:1,14:1,16:1,19:1,21:1,23:1,27:1,28:1,29:1,30:1},8:{1:1,2:1,3:1,5:1,7:1,17:1,19:1,23:1,26:1,28:1,30:1},9:{5:1,6:1,7:1,14:1,22:1,25:1,29:1,30:1},10: ...

```

(When viewed in a browser, the document seems empty; try viewing the source instead. Unless you are a ♦ moderator, you can only see this information for your own account.)

The string has a rather peculiar format but presumably it's an easy way to populate the calendar:

The information can be used to calculate the longest consecutive days streak, i.e. the one that determines if you get the Fanatic badge. The linked question has a working JavaScript example by user @ShadowWizard.

Standard rules apply: the shortest code wins.

### Input

A string with the exact format provided by Stack Exchange, e.g. `{2015:{6:{3:1}}}`. Top level keys are years, second level keys are months, third level keys are days. All values are `1`. You may assume the dates are not earlier than July 31st, 2008, which is when the first Stack Overflow question was posted. You may also assume there's at least one day in the input; the information is only provided to registered users, who must have visited the site at least once.

### Output

The length of the longest streak, i.e. consecutive days in the input. You may choose to return it as a number or a string.

### Test cases

(besides your own streak on CGCC of course; you should be able to verify if you're eligible for the Enthusiast and Fanatic badges or not)

| Input | Output |
| --- | --- |
| `{2015:{6:{3:1}}}` | 1 |
| `{2015:{6:{3:1}},2016:{6:{3:1}}}` | 1 |
| `{2015:{6:{3:1},7:{3:1}}}` | 1 |
| `{2015:{6:{3:1,5:1}}}` | 1 |
| `{2015:{6:{3:1,4:1}}}` | 2 |
| `{2015:{2:{28:1},3:{1:1}}}` | 2 |
| `{2016:{2:{28:1},3:{1:1}}}` | 1 |
| `{2016:{1:{30:1},2:{1:1}}}` | 1 |
| `{2016:{4:{30:1},5:{1:1}}}` | 2 |
| `{2016:{4:{30:1},6:{1:1}}}` | 1 |
| `{2016:{12:{31:1}},2017:{1:{1:1}}}` | 2 |
| `{2016:{12:{31:1}},2018:{1:{1:1}}}` | 1 |
| `{2016:{11:{29:1},12:{30:1,31:1}},2017:{1:{1:1,2:1,4:1}}}` | 4 |
| `{2100:{2:{28:1},3:{1:1}}}` | 2 |
| `{2400:{2:{28:1},3:{1:1}}}` | 1 |

# Answer
> 6 votes
# MATL, ~~45~~ 43 bytes

*Thanks to Jonathan Allan for pointing out a mistake, now corrected.*

```
j':1?'0YXU2e"@Y:wXHx2e"H@Y:g3$YO]]vtf-FT#XM

```

Try it online! Or verify all test cases.

### How it works

```
j         % Input as (unevaluated) string
':1?'     % Push this string. Will be interpreted as regexp
0         % Push 0. Will be interpreted as character 0 (equivalent to space)
YX        % Regexprep: replace ':' or ':1' by character 0
U         % Evaluate string. Gives nested cell array
2e        % Reshape as a 2D cell array with 2 rows (in column major order)
"         % For each column. Each column contains a year and a (nested) cell array
  @       %   Push current column, as a cell array
  Y:      %   Unbox: pushes year, then the cell array
  w       %   Swap
  XHx     %   Copy to clipboard H and delete
  2e      %   Reshape cell array as a 2D cell array with 2 rows
  "       %   For each column. Each column contains month and a cell array (of days)
    H     %     Push year from clipboard
    @     %     Push current column, as a cell array
    Y:    %     Unbox: pushes month, then the cell array of days
    g     %     Convert cell array to numerical vector of days
    3$YO  %     3-input datenum: converts year, month, days to serial date numbers
  ]       %   End
]         % End
v         % Concatenate stack into numerical vector of serial date numbers
tf        % Duplicate, find. Gives vector of the same size containing 1, 2, 3...
-         % Subtract, element-wise
FT#XM     % Second output of mode function: number of repetitions of the mode
          % Implicit display

```

# Answer
> 17 votes
# Python 2,  ~~186 184 179 177 173 172~~  162 bytes

-10 thanks to ovs! (avoiding use of `.items`)

```
x=input()
from datetime import*
a=sorted(date(y,m,d)for y in x for m in x[y]for d in x[y][m])
print max(map(len,`[d+timedelta(1)in a for d in a*2]`.split('s')))/6

```

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

### Huh, how?

In Python 2 `input` implicitly attempts an `eval` on the string which, in this case, will produce a nested dictionary.

`a` is then a list of the dates in order (`sorted(...)`), this is formed by inspecting the nested dictionaries in a nested `for` loop, and passing the resulting parts of the dates to `date(year, month, day)`.

`[d+timedelta(1)in a for d in a*2]` forms a list of `boolean`s which identify whether the next date is present for each date in the sorted dates repeated twice, `a*2`.

Note that the final value of `a` will always be `False`. The reason for repeating `a` is to avoid something later (see the final paragraph).

``[...]`` gets the Python string representation (AKA `repr`) of that list - for example, something like `"[False, True, True, False, False, False, True, True, False, False]"` for an input with three consecutive dates between two others.

`.split('s')` splits the resulting string at occurrences of the `'s'` character - so for the above, that would be `['[Fal', 'e, True, True, Fal', 'e, Fal', 'e, Fal', 'e, True, True, Fal', 'e, Fal', 'e]']`.

`map(len,...)` simply gives us a list of the lengths of the strings in the above list - so for the above, that would be `[4, 18, 6, 6, 18, 6, 2]`.

`max(...)` gives the maximum value of that list - so for the above, that would be `18`.

To find the number of consecutive days we want to count how many `True`s there were in that longest section and then add one. In the above example, we can simply divide by six (the length of either `'True, '` or `'e, Fal'`), hence the `/6` at the end.

If the longest run of consecutive dates is at the left of the sorted dates we'd get something like `'[True, True, Fal'` (or `'[Fal'` when no dates at all are consecutive), which would be two shy of what we need, so if we were to perform all of this across `a` rather than `a*2` we'd need to add two before performing the integer division (e.g. `(...+2)/6`). This wouldn't affect any other results but costs one more byte than simply repeating `a` with `a*2`, whereupon we'll get the longer string later on - this is guaranteed by the fact that `d+timedelta(1)` for the maximal `d` will give `False`.

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

*Thanks to @tsh for a bug fix and some optimizations*

```
o=>(D=k=1,M=g=(o,c)=>Object.keys(o).map(c))(o,y=>g(Y=o[y],m=>g(Y[m],d=>M>(D-(D=Date.UTC(y,m-1,d))<-1e8?k=1:++k)?0:M=k)))|M

```

Try it online!

### Commented

```
o => (                  // o = input object
  D =                   // D = previous day, as an integer
  k = 1,                // k = streak length
  M =                   // M = maximum streak length
  g = (o, c) =>         // g is a helper function which applies a callback
  Object.keys(o).map(c) // function c to each key of an object o
)(                      // 1st call to g with ...
  o,                    //   ... the input object o
  y =>                  //   for each year y,
  g(                    //   do a 2nd call to g with ...
    Y = o[y],           //     ... the object of months o[y]
    m =>                //     for each month m,
    g(                  //     do a 3rd call to g with ...
      Y[m],             //       ... the object of days Y[m]
      d =>              //       for each day d,
      M > (             //       test whether M is greater than the updated k
        D - (           //         subtract from D ...
          D = Date.UTC( //         ... the new D corresponding to
            y, m - 1, d //         this year, this month and this day
          )             //
        ) < -1e8 ?      //         if the difference is less than -10**8 ms:
          k = 1         //           reset k to 1
        :               //         else:
          ++k           //           increment k
      ) ?               //       if M is greater than the new value of k:
        0               //         do nothing
      :                 //       else:
        M = k           //         update M to k
    )                   //     end of 3rd call
  )                     //   end of 2nd call
) | M                   // end of 1st call; return M

```

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


title: Sticky polyhexes

text:
# Question
Title: Sticky polyhexes
## Background

A **polyhex** of size \\$n\\$ is a contiguous shape made from joining \\$n\\$ unit regular hexagons side-by-side. As an example, the following image (from Wikipedia) contains all 7 distinct tetrahexes (polyhexes of size 4):

A **dihex** is a polyhex of size 2.

Now, let's define a **sticky polyhex** as follows:

* A single dihex is a sticky polyhex.
* If a polyhex X is sticky, X plus a dihex Y is also sticky if X and Y share at least two unit sides.
* Any polyhex that cannot be formed by the above definition is not sticky.

The following is the only size-2 sticky polyhex:

```
 _
/ \
\ /
/ \
\_/

```

The following are the only two essentially different size-4 sticky polyhexes:

```
 _   _
/ \_/ \
\ /  _/
/ \_/
\_/
   _
 _/ \
/ \ /
\ / \
/ \_/
\_/

```

The following is a simplified illustration of all 15 size-6 sticky polyhexes:

```
    * * *    * * *    *        * * * *    * * *
     * *      * *    * * * *    * *          * * *
      *          *        *

    * *       *        * *       * *     * * *
     * * *   * * * *    * * *   * * *       * *
        *       *      *         *         *

    * * *    * * *    * * * *   * * *    * * *
       * *    * * *    *   *       *        * *
          *                       * *        *

```

## Challenge

Given a positive integer \\$n\\$, count the number of sticky polyhexes of size \\$2n\\$. Two polyhexes which are equivalent under rotation and reflection are counted only once.

If you want, you may take the value of \\$2n\\$ as input instead (and assume the value is always even).

Standard rules apply. The shortest code wins.

## Test cases

The following are the expected results for \\$1 \le n \le 7\\$. Generated using reference implementation in Python (it times out shortly after calculating \\$n = 6\\$; the result for \\$n = 7\\$ was found on my local machine, and the program segfaulted while calculating \\$n = 8\\$).

```
1, 2, 15, 110, 1051, 10636, 113290

```

This sequence is now on OEIS as A342963.

# Answer
> 24 votes
# Haskell, ~~320~~~~236~~ 230 bytes

```
length<$>iterate(\h->nub[r$x:y:u|u<-h,t<-u,x<-n t\\u,y<-n x\\u,([x,x,y]\\(u>>=n))/=[x,y]])[[l,0<$l]]
r u=minimum[sort$(!!i).p.map(*j).m a<$>u|a<-u,j<-l,i<-[0..5]]
n=(<$>p l).m
m=zipWith(-)
p=permutations
l=[-1..1]
import Data.List

```

Try it online!

An infinite list whose \\$n\\$-th element (1-indexed) is the number of sticky polyhexes of size \\$2n\\$.

This is probably the longest I've ever spent golfing a single program, and at the same time it's the answer I'm most proud of. After golfing 90 bytes off of the first iteration, it's time explain in some depth how this solution works and share the things I've learned.

## The grid

The first thing to decide is how to handle the hexagonal grid. At first I was demotivated by the apparent lack of regularity in any coordinate system I could find, but then I stumbled across this website1. Along with some amazing visualization tools, which helped me later in debugging my code, it describes several reasonable coordinate systems for a hexagonal grid. The one I settled for in the end is called cube coordinates and is very clever. The following animation (taken from the same website) explains the concept beautifully.

We start from the standard lattice grid in \\$3\\$-dimensional space, and then we cut along the plane \\$x+y+z=0\\$. On this plane, we get a hexagonal grid, where each hexagon is encoded as a triplet of integers \\$\[x:y:z\]\\$ with the constraint that \\$x+y+z=0\\$. Coordinate systems such as this one are called *homogeneous*, since they have one extra degree of freedom (three numbers for two dimensions) but they also have one additional constraint. While using three numbers to represent two dimensions may seem wasteful, the redundancy of cube coordinates is abundantly outweighted by the elegance and symmetry they provide. The main advantage is that, since we are operating in a *vector subspace*2 of \\$\mathbb{R}^3\\$, all the linear operations we may want to perform (translations, rotations, reflections) become astoundly straightforward (more on this later). For now, the following picture3 should give you an intuition of how cube coordinates work.

Before moving on to the actual problem, let's code(golf) a few grid-related functions. As anticipated, each hexagon is encoded as a triplet of integers with sum equal to \\$0\\$. In Haskell4, we will represent it as a list `[x,y,z]`.

* Since, as I said, we are working in a vector subspace, there is a well-defined notion of *displacement vector* between two points: coordinate-wise, we just take the difference of each coordinate. The relevant function is `m=zipWith(-)` (mnemonic: **m**inus), and it works as follows: `m[x1,y1,z1][x2,y2,z2] ≡ [x1-x2,y1-y2,z1-z2]`.
* Unsurprisingly, we will later need a function to compute the neighboring hexes of a given hexagon. By looking at the above picture, it's easy to see that all the neighbors of point \\$\[x:y:z\]\\$ can be obtained by summing (coordinate-wise) \\$\[-1:0:1\]\\$ or a permutation thereof. After importing `Data.List` (I know, that's very costly, but totally worth it5) and creating the aliases `p=permutations` (mnemonic: **p**ermutations) and `l=[-1..1]≡[-1,0,1]` (mnemonic: **l**ist6), we can define our function `n=(<$>p l).m` (mnemonic: **n**eighbors). If you're not fluent in Haskell, this is what `n` would look like if I weren't codegolfing: `n x=[m x y|y<-p l]`. In other words, we take each permutation `y` of `l` and subtract it (coordinate-wise) from `x`; adding or subtracting is the same thing, since `-l` is a permutation of `l`.

## Attaching dihexes

Now that we have our grid set up, it's time to move on to the actual problem. A polyhex will be very naturally represented as a list of hexes, i.e. a list of lists of integers. Assume we are given a list `h` containing all the sticky polyhexes of size \\$2n\\$. Our task for this section will be to compute a list of all the sticky polyhexes of size \\$2n+2\\$, possibly with duplicates. This is the relevant code, where we abuse7 the list difference operator `(\\)`.

```
[x:y:u|                         -- the list of  polyhexes obtained by adding x and y to u, where
    u<-h,                       -- u is a polyhex in h
    t<-u,                       -- t is a hexagon in u
    x<-n t\\u,                  -- x is a neighbor of t not in u
    y<-n x\\u,                  -- y is a neighbor of x not in u
    ([x,x,y]\\(u>>=n))/=[x,y]   -- ?? see below
]

```

Everything should be pretty straightforward. The only thing that's missing is checking that the polyhex `x:y:u` is actually sticky, i.e. that the dihex `[x,y]` has at least two sides in common with `u`. The most concise way of checking this I could find is `([x,x,y]\\(u>>=n))/=[x,y]`. How does it work? `u>>=n` is the list of neighbors of `u`, counted with multiplicity. Since `x` appears at least once in this list (by definition `x` is a neighbor of `t`), the difference `[x,x,y]\\(u>>=n)` is equal to `[x,y]` if and only if the dihex `[x,y]` shares exactly one (i.e. less than two) side with `u`.

## Canonical representatives

The only thing that's left is to remove duplicates. We say that two polyhexes are *equivalent* if they are related by a finite sequence of translations, rotations and reflections. A standard approach for this kind of task is to choose a *canonical representative* for every polyhex, with two rules in mind:

1. a polyhex is equivalent to its canonical representative;
2. if two polyhexes are equivalent, then they have the same canonical representative (by rule 1., the converse also holds).

If we find a suitable canonical representative for every polyhex, the task is solved: simply replace each polyhex with its representative, and then remove duplicates the standard way (which, in Haskell, is `nub`).

A reasonable choice for canonical representatives is the following: given a polyhex \\$u\\$, we define its representative \\$r(u)\\$ as the lexicographically minimum polyhex which is equivalent to \\$u\\$ and contains the hex \\$\[0:0:0\]\\$. We will always assume that the hexes in a polyhex are lexicographically sorted, so that this definition is well-posed.

This choice of representatives may seem somewhat arbitrary, but the idea behind it is really simple: given a polyhex \\$u\\$, we generate the set of all the equivalent polyhexes (with the restriction of containing \\$\[0:0:0\]\\$, otherwise there would be infinitely many). Clearly, if we apply this procedure to every polyhex equivalent to \\$u\\$ we will end up with the same set. Now we just need to pick a fixed element of this set, and (with bytes in mind) we select the minimum.

Now that we have an objective in mind, how do we implement it? This is where the linearity of cube coordinates comes into play. Equivalent polyhexes are always related by linear8 transformations, which should be relatively easy to implement. Before we look at the code, let's analyze these transformations in detail. Translations are trivial: the translation sending hexagon `x` to `[0,0,0]` is just `m x`.

As far as rotations and reflections are concerned, by looking at the picture above you can convince yourself that they all behave as follows: permute the three coordinates and, possibly, flip all the signs. For instance, the following are rotations or reflections: $$ \[x:y:z\]\longmapsto\[y:z:x\]\\ \[x:y:z\]\longmapsto\[-x:-z:-y\]. $$

We are now ready to implement the function `r` (mnemonic: **r**epresentative).

```
r u=minimum[sort$(!!i).p.map(*j).m a<$>u|a<-u,j<-l,i<-[0..5]]

```

In plain English, the code does the following. Given a polyhex `u`, we want to compute its canonical representative as defined above, so we generate a list of all the polyhexes containing `[0,0,0]` and equivalent to `u`. To this aim, we fix:

* a hexagon `a` in `u` (which will be mapped to `[0,0,0]` with a translation);
* a sign `j` in `[-1,1]`;
* a permutation index `i` in `[0,1,2,3,4,5]`.

The code `(!!i).p.map(*j).m a<$>u` takes `u` and applies a translation (`m a`, mapping `a` to `[0,0,0]`), possibly a sign flip (`map(*j)`), and finally a permutation of the coordinates (`(!!i).p`). The `sort` ensures that the polyhex we obtain is "normalized" (i.e. lexicographically sorted). Finally, we take the lexicographically `minimum` polyhex in our list, and this is the canonical representative of `u`.

A small codegolfing note: you may have noticed the `j<-l` instead of the expected `j<-[-1,1]`. This saves 5 bytes at the cost of producing some "degenerate" polyhexes, but the output is the same since a degenerate polyhex will never be selected as the minimum.

## Conclusion

Now that we have all the ingredients, let's put them together! This is the last bit of code (with ellipses instead of the section already explained above).

```
length<$>                   -- take the length of each list in
iterate(                    -- the list generated by repeatedly applying
    \h->                    --     the function that takes the list h of sticky polyhexes of size 2*n
        nub[                --     and removes duplicates from
            r$              --     the list of canonical representatives of
            x:y:u|...])     --     all the polyhexes obtained by suitably attaching dihexes to elements of h
    [[l,0<$l]]              -- starting from the list of sticky dihexes (there is just one)

```

`0<$l` is short for `[0,0,0]`.

**And that's it!** Thanks for reading through this huge post (or just skipping to the end to read the footnotes, most likely). Despite having spent several hours golfing this program, I believe there are still at least a few bytes that can be somehow shaved off: if you have any ideas, please let me know!

---

---

1 Ok maybe I should've resorted to Google earlier, it's literally the first result for "hex grid".
2 Don't worry if you don't know what I'm talking about, I have this bad habit of inserting random mathematical terms even when it's completely unnecessary.
3 Guess where it's taken from.
4 Please don't stop reading, I promise there will be no catamorphisms.
5 Trust me, I've spent several hours trying every possible variation of the code.
6 Creativity is my middle name.
7 Can you blame me? It's just two bytes and it's *amazing*!
8 +10 internet points if you shouted "Translations aren't linear!" with a disgusted voice.

# Answer
> 10 votes
# C++, Not competing

After spending so long on the golfing side of this challenge, I was curious to see what I could do from a perspective. Here is my C++ attempt, which should be able to run up to \\$n=8\\$ on every computer, and \\$n=9\\$ if you have enough RAM and patience. The approach is the same as my other answer, but optimized for speed instead of bytecount. Here are the results I got so far.

| \\$n\\$ | Number of sticky polihexes of size \\$2n\\$ |
| --- | --- |
| 1 | 1 |
| 2 | 2 |
| 3 | 15 |
| 4 | 110 |
| 5 | 1051 |
| 6 | 10636 |
| 7 | 113290 |
| 8 | 1234189 |
| 9 | 13674761 |
| 10 | 153289285 |

It's highly unlikely I'll ever be able to go further, it looks like 256GB of RAM are not enough to compute the list of sticky polyhexes for \\$n=11\\$.

```
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using T = char;

struct hex {
    T x, y;
    constexpr T z() const {
        return -x -y;
    }
    bool operator < (const hex& other) const {
        return x < other.x or (x == other.x and y < other.y);
    }
    bool operator == (const hex& other) const {
        return x == other.x and y == other.y;
    }
    template<typename F>
    void on_neighbors(F f) const {
        f(hex{ x + 1, y });
        f(hex{ x + 1, y - 1});
        f(hex{ x, y + 1 });
        f(hex{ x, y - 1 });
        f(hex{ x - 1, y + 1 });
        f(hex{ x - 1, y });
    }
};

using polyhex = std::vector<hex>;

std::vector<polyhex> extend(const std::vector<polyhex>& h) {
    auto nub = [&](auto& v) {
        std::sort(v.begin(), v.end());
        v.erase(std::unique(v.begin(), v.end()), v.end());
    };
    auto in = [&](const auto& v, const hex& a) {
        return binary_search(v.begin(), v.end(), a);
    };
    std::vector<polyhex> ans0;
    for(const auto& u : h) {
        std::vector<hex> layer;
        for(const hex& t : u) {
            t.on_neighbors([&](hex&& a) {
                if(not in(u, a)) {
                    layer.push_back(a);
                }
            });
        }
        nub(layer);
        std::vector<polyhex> ans1;
        for(const hex& a : layer) {
            int cnt0 = 0;
            a.on_neighbors([&](hex&& b) {
                if(in(u, b)) {
                    ++cnt0;
                }
            });
            a.on_neighbors([&](hex&& b) {
                if(not in(u, b) and (a < b or not in(layer, b))) {
                    int cnt = cnt0;
                    b.on_neighbors([&](hex&& c) {
                        if(in(u, c)) {
                            ++cnt;
                        }
                    });
                    if(cnt < 2) {
                        return;
                    }
                    polyhex v = u;
                    v.push_back(a);
                    v.push_back(b);
                    v.shrink_to_fit();
                    std::sort(v.begin(), v.end());
                    ans1.push_back(v);
                }
            });
        }
        nub(ans1);
        ans0.insert(ans0.end(), std::make_move_iterator(ans1.begin()), std::make_move_iterator(ans1.end()));
    }
    nub(ans0);
    std::vector<polyhex> ans;
    for(auto it = std::make_move_iterator(ans0.begin()); it != std::make_move_iterator(ans0.end()); ++it) {
        polyhex v = *it, best = v;
        auto trans = [&](auto&& f) {
            polyhex vv = v;
            for(auto& c : vv) {
                c = f(c);
            }
            std::sort(vv.begin(), vv.end());
            hex m = vv.back();
            for(auto& c : vv) {
                c = hex{ c.x - m.x, c.y - m.y };
            }
            if(vv < best) {
                best = std::move(vv);
            }
        };
        for(int s = -1; s <= 1; s += 2) {
            trans([&](hex& c) { return hex{ s * c.x, s * c.y }; });
            trans([&](hex& c) { return hex{ s * c.x, s * c.z() }; });
            trans([&](hex& c) { return hex{ s * c.y, s * c.x }; });
            trans([&](hex& c) { return hex{ s * c.y, s * c.z() }; });
            trans([&](hex& c) { return hex{ s * c.z(), s * c.x }; });
            trans([&](hex& c) { return hex{ s * c.z(), s * c.y }; });
        }
        ans.push_back(best);
    }
    nub(ans);
    return ans;
}

int main() {
    std::vector<polyhex> h = { { hex{ -1, 0 }, hex{ 0, 0 } } };
    for(int n = 1; ; ++n) {
        std::cout << "n=" << n << " -> " << h.size() << std::endl;
        h = extend(h);
    }
    return 0;
}

```

Try it online!

# Answer
> 8 votes
# Ruby, ~~290~~ 270 bytes

```
->n,p=[[2,3]],s=2{s<n ?(q=[]
p.map{|a|a.product(d=[w=n*3,1,~w,-w,-1,-~w],d).map{|i|r=[];t=0
c=a+b=[i[0]+i[1],i.sum]
a&b==r&&12.times{|j|t+=a.count b[j%2]+d[j/2];c=c.map!{|k|j%2<1?k%w*(2+w)-k:k/w+k%w*w}.sort!.map{|m|m-c[0]+n};r<<c*1}
t>1&&q<<r.min}}
f[n,q&q,s+2]):p.size}

```

Try it online!

A function that accepts the **total** number of hexagons as an argument `n` (as permitted by the rules) and returns the number of sticky polyhexes. Will run up to 6 dihexes / 12 hexes on TIO in about 7 seconds.

This is about 3 times faster than the old version, because the code now checks if the new hexes overlap with the old hexes **before** calculating all 12 symmetries and 12 possible shared edges, hence saving a lot of wasted time. It also saves a byte, because `r` is empty at this stage, so we can use it to compare with `a&b` to ensure this array intersection is empty, instead of comparing with the literal empty array `[]`.

**Explanation**

Each hex is saved as a single number; polyhexes are saved as arrays.

The coordinate system is a square grid of infinite height, and width `w` three times the number of hexes in the last generation to be investigated. The hexagonal grid is mapped onto this. Hexes with coordinates that differ by the following amounts are considered adjacent: `1`=horizontal, `w`= vertical, and `~w` = `-w-1`= diagonal. As it is a hexagonal grid, coordinates on the other diagonal are not considered adjacent.

The function proceeds by adding a pair of hexes to the previous generation and checking if the new hexes share at least 2 edges with the old ones; this requires 6 directions x 2 new hexes = 12 checks. To ensure the newly added hexes do not wrap around the grid, the old polyhex is positioned such that the hex with the lowest coordinate is at `n` (where n is the total number of hexes in the last generation to be investigated.)

**Symmetries**

Coincidentally, there are also 12 symmetries to be checked, so the same loop performs both duties. All symmetries are cycled through by alternately performing 2 different reflections. After each reflection, the hexes are sorted and the coordinates are adjusted so that the lowest coordinate is equal to `n`.

The first reflection is a vertical flip  `k = k%w - k/w*w + k%w*w` . The first term keeps the x coordinate the same and the second one (with integer division to discard the x coordinate) flips the y coordinate. The third term is a correction to maintain the skew. This formula can be simplified to `k = k%w*(2+w)-k`. This reflection is done first in case any new hexes have negative y coordinates.

The second is a diagonal flip which swaps the x and y coordinates: `k = k/w+k%w*w`. Doing this second ensures there are no negative y coordinates to handle (because after every reflection, the lowest hex's coordinate is adjusted to be equal to `n`.)

These two reflections combined give a 1/6 rotation (see below) hence 12 reflections cycle through all symmetries.

```
 SYMMETRY EXAMPLE
 Start    Flip      Skew          Flip
 Pattern  Vertical  Correction    Diagonal
 01         43      54            50
 5 2   ->  5 2  ->  0 3  ------>  4 1
  43       01        12            32

```

Once the polyhex's coordinates under all 12 symmetry operations have been generated, the lexically lowest set of coordinates is added to the list of polyhexes.

**Commented code (original version)**

```
f=->n,p=[[2,3]]{                               #Assume initial hexes are at 2 and 3 if no info provided.
 s=p[0].size                                   #Check size of first polyhex in list, others should be the same.
 d=[w=n*3,1,~w,-w,-1,-~w]                      #d contains offsets for the six possible directions of travel. w is the width of the grid.
 s<n ?(q=[]                                    #If size of polyhex less than required n, make array q to hold new generation.
  p.map{|a|                                    #Iterate through list p of previous generation polyhexes a.
   (s*36).times{|i|r=[];t=0                    #Try adding a chain of two hexes in 6*6 possible directions to each existing hex.
    c=a+b=[g=a[i/36]+d[i/6%6],g+d[i%6]]        #b contains the new hexes chained onto old hex a[i/36]. Add them to existing polyhex a to make new polyhex c.
    12.times{|j|t+=a.count(b[j%2]+d[j/2])      #Iterate through 2 new hexes x 6 directions = 12 to find the number of edges shared with the old polyhex.
     c=c.map!{|k|j%2<1?k%w*(2+w)-k:k/w+k%w*w}. #Reflect the new polyhex...
     sort!.map{|m|m-c[0]+n}                    #...sort the coordinates, and adjust them so that the smallest equals n
     r<<c*1}                                   #Add the current symmetry of the new polyhex to r (the c*1 ensures a new copy is added, not just a pointer)
   a&b==[]&&t>1&&q<<r.min                      #If new hexes b don't overlap old hexes a && there's more than one common edge add lowest value by symmetry to q
   }
  }
  f[n,q&q]):p(p.size)                          #q&q to remove duplicates. Recursively call to build next generation. If s already equal to n, output the total.
}

```

---
Tags: code-golf, math, combinatorics, hexagonal-grid, polyomino
---


title: Is there a face in this image?

text:
# Question
Title: Is there a face in this image?
Help, I've been diagnosed with prosopagnosia! This means I'm no longer able to recognise faces.... :(

Can you help me?

# The challenge

You will be given an image as a matrix of regular ASCII characters separated by new line characters, and your task is to determine if it contains a face. Faces will look something like the following:

```
o.o
.7.
___

```

Of course, people all look different - the only features that virtually everyone has are two eyes, a nose, and a mouth. For this challenge, eyes will be a lower-case `o`, a nose will be a `7`, and the mouth will be a line of underscores `_`. For this challenge, faces must have all of these features.

To be specific, a face must have two eyes in the same row of the matrix, with a nose centred horizontally between them somewhere between the rows with the eyes and the mouth, and a mouth at the bottom of the face that is a row of underscores that extends all the way from the column of one eye to the other. Since a face must have a horizontally-centred nose, all faces must be an odd number of characters wide. Please note: The nose does not have to be centred vertically so long as it is between the rows of the eyes and mouth (exclusive). No other features of the face matter so long as the face has only two eyes, one nose, and one mouth - the "fill" of the face can be anything but the characters `o`, `7`, or `_`

The output format is flexible - all you must be able to do is distinguish whether the image from the input has a face. You may use any output values to represent whether an image has a face (e.g. 1 if it does, 0 if it does not)

# Examples/Test Cases

```
...o.....o.
......7....
..._______.

```

^ contains a face

```
...o.....o.o.o
......7.....7.
..._______.___

```

^ contains a face (actually contains two but your program does not need to care about any additional faces)

```
o.o...o..o
o.7.7._.7.
.._____7__

```

^ does not contain a face

```
o.o...o..o
o...7...7.
.._____7__

```

^ contains a face (notice the two differences between this case and the one above)

```
o...o
.7...
_____

```

^ does not contain a face, as the nose is not centred horizontally

```
..o...o
.......
.......
.......
....7..
.______

```

^ contains a face formed by the last five columns

```
,/o[]8o
o198yH3
f_3j`~9
()**&#^
*#&^79%
2______

```

^ contains a face (the last five columns form a face just like in the previous example, except with different filler characters that make it less human-readable)

```
o..o.o..o.o...o..o.o.o..o...o.o.o.o.o
......7....o7......7......7......7...
..7...............___......7....___..
____.____.___._.._____.._____._______

```

^ contains a face (only the 3x3 face in the fifth-last through third-last columns is a face - all the other potential faces break one or more rules)

```
.....
.o.o.
..7..
.....
.___.

```

^ contains a face

```
o7o
...
___

```

^ does not contain a face

# A few extra clarifications

-Faces will never be rotated

-The `.`'s in the test cases could be any regular ASCII characters other than the three special characters, they are periods just for better readability

-You can assume all matrices will be smaller than 100 x 100

# Scoring

This is . Shortest code wins!

# Answer
# 05AB1E, ~~61~~ ~~60~~ 57 bytes

```
3тŸãε`I€Œsδùø€Œsδù€`}€`ʒćÁ„ooÅ?sRćÙ'_Qs€Ås7¢y¨J…_7oS¢2ÝQP

```

Input as a list of lines. Outputs a list of valid faces as truthy, or an empty list `[]` as falsey. If this is not allowed, the `ʒ` can be `ε` and a trailing  has to be added, to output `1` for truthy and `0` for falsey.

Try it online or verify all test cases. (Sometimes times out for the last biggest test case.)

**Explanation:**

Step 1: Transform the input into \\$n\\$ by \\$m\\$ blocks:

```
3тŸ              # Push a list in the range [3,100]
   ã             # Create all possible pairs by taking the cartesian product
ε                # Map each pair [m,n] to:
 `               #  Pop and push the m,n separated to the stack
  I              #  Push the input-list
   €             #  For each row:
    Œ            #   Get all substrings
      δ          #  For each list of substrings:
     s ù         #   Keep those of a length equal to `n` (using a swap beforehand)
        ø        #  Zip/transpose; swapping rows/columns
                 #  (we now have a list of columns, each with a width of size `n`)
         €       #  For each column of width `n`:
          Œ      #   Get all sublists
            δ    #  For each list of sublists:
           s ù   #   Keep those of a length equal to `m` (using a swap beforehand)
              €` #  And flatten the list of list of lists of strings one level down
}€`              # After the map: flatten the list of list of strings one level down

```

Try just this first step online.

Step 2: Keep the \\$n\\$ by \\$m\\$ blocks which are valid faces:

```
ʒ                # Filter the list of blocks by:
 ć               #  Extract the first row; pop and push the remainder-list and first row
                 #  separated to the stack
  Á              #  Rotate the characters in the string once towards the right
   „ooÅ?         #  Check if the string now starts with a leading "oo"
 s               #  Swap to get the remaining list of rows
  R              #  Reverse the list
   ć             #  Extract head again, to get the last row separated to the stack
    Ù            #  Uniquify this string
     '_Q        '#  And check if it's now equal to "_"
 s               #  Swap to get the remaining list of rows
  €              #  For each row:
   Ås            #   Only leave the middle character (or middle 2 for even-sized rows)
     7¢          #  Count the amount of 7s in this list
 y               #  Push the entire block again
  ¨              #  Remove the last row (the mouth)
   J             #  Join everything else together
    …_7oS        #  Push string "_7o" as a list of characters: ["_","7","o"]
         ¢       #  Count each in the joined string
          2Ý     #  Push the list [0,1,2]
            Q    #  Check if the two lists are equal
 P               #  And finally, check if all checks on the stack are truthy
                 # (after which the filtered result is output implicitly)

```
> 6 votes

# Answer
# JavaScript (ES6),  ~~147 ... 140~~  139 bytes

Returns either *false* or a truthy value.

```
s=>(p='',g=k=>s.replace(/[^7o_]/g,0).match(`o${p}${p+=0}o${S=`.{${w=s.search`
`-k}}(0${p+p}.{${w}})*`}${p+7+p+S}__{${k}}`)||w>0&&g(k+2))(2)

```

Try it online!

### How?

We start with \\$k=2\\$ and \\$p\\$ set to an empty string.

At each iteration, we first replace all characters in the input string \\$s\\$ other than `"o"`, `"7"` or `"_"` with zeros. This includes linefeeds. So the first test case:

```
...o.....o.
......7....
..._______.

```

is turned into:

```
flat representation: "...o.....o.¶......7....¶..._______."
after replace()    : "000o00000o00000000700000000_______0"

```

We then attempt to match the 3 parts of a face of width \\$k+1\\$.

**Eyes**

An `"o"` followed by \\$k-1\\$ zeros, followed by another `"o"`:

```
`o${p}${p+=0}o`

```

Followed by the padding string \\$S\\$ defined as:

```
`.{${w=s.search('\n')-k}}(0${p+p}.{${w}})*`
 \______________________/ \____________/ |
   right / left padding      k+1 zeros   +--> repeated any
                          + same padding      number of times

```

**Nose**

\\$k/2\\$ zeros, followed by a `"7"`, followed by \\$k/2\\$ zeros, followed by the same padding string \\$S\\$ as above:

```
`${p+7+p+S}`

```

**Mouth**

\\$k+1\\$ underscores:

```
`__{${k}}`

```

In case of failure, we try again with \\$k+2\\$. Or we stop as soon as the variable \\$w\\$ used to build \\$S\\$ is less than \\$1\\$, meaning that the padding string would become inconsistent at the next iteration.

For the first test case, we successively get the following patterns:

```
o0o.{9}(000.{9})*070.{9}(000.{9})*__{2}
o000o.{7}(00000.{7})*00700.{7}(00000.{7})*__{4}
o00000o.{5}(0000000.{5})*0007000.{5}(0000000.{5})*__{6}

```

The 3rd one is a match.
> 13 votes

# Answer
# Python 3.8, ~~264~~ \\$\cdots\\$ ~~223~~ 222 bytes

Saved a whopping 16 bytes thanks to Kevin Cruijssen!!!

Saved a byte thanks to Tanmay!!!

```
import re
b='[^o7_]'
def f(l):
 while l:
  s,p=l.pop(0),1
  while m:=re.compile(f'o{b}+o').search(s,p-1):
   a,p=m.span();d=p-a;e=d//2
   if re.match(f'({b*d})*{b*e}7{b*e}({b*d})*'+'_'*d,''.join(s[a:p]for s in l)):return 1

```

Try it online!

Inputs a list of strings.
Outputs \\$1\\$ for a face, `None` otherwise.

**How**

Looks for pairs of eyes in each row, starting from the top, by repeatedly removing the top row from the input list. If a pair is found, the columns forming the pair are taken from the remaining rows and concatenated together. This string is then tested against a regex constructed from the distance separating the eyes to see if we've found a face. If not, we continue scanning the current line, beginning at the stage-left eye, looking for more pairs before moving onto the next row.
> 6 votes

# Answer
# Regex (PCRE2), ~~203~~ ~~193~~ ~~177~~ 181 bytes

```
/((?|^()|^(?:.(?=.*
(\2.)))+){2}(?(8)(?=\8$)(?|()|(?:(?6)(?=.+((?6)\3)\7$))++){2}((?6)|(?!\5)7())\3(?=\7$)|o([^o7_])+o)(?|()|\7(?:.(?=.*
.*(.\7)))+){2}
(?=\2(.*)))+\5.*(?=\8)_+\7$/m

```

Try it on regex101

### Explanation

`((?|^()|^(?:.(?=.*\n(\2.)))+){2}(?(8)(?=\8$)(?|()|(?:(?6)(?=.+((?6)\3)\7$))++){2}((?6)|(?!\5)7())\3(?=\7$)|o([^o7_])+o)(?|()|\7(?:.(?=.*\n.*(.\7)))+){2}\n(?=\2(.*)))+`

Main loop. Matches everything except for the mouth:

`(?|^()|^(?:.(?=.*\n(\2.)))+){2}` \- on each line, match the padding to the left of the face, while counting a matching number of characters of padding into `\2` from the start of the next line. This needs to use a Branch Reset Group `(?|`...`)` in order to initialize `\2` to empty with `^()` before building it up one character at a time with `(\2.)`. The `{2}` guarantees that both stages will execute exactly once, and do so in the correct order due to each one having a `^` anchor (which matches the start of any line due to the `/m` flag). Replacing the `{2}` with `+` wouldn't work because a loop will immediately terminate after any optional iteration that matches zero characters. Note that in the case of zero padding, the first stage will execute twice in a row.

`(?(8)`...`|`...eyes...`)` \- Only allow matching the eyes if we haven't already captured `\8`, i.e. iterated through the main loop at least once.

`(?!\7)o([^o7_])+o` \- match the eyes, and define the subroutine `(?6)` to do `[^o7_]`.

`(?=\8$)(?|()|(?:(?6)(?=.+((?6)\3)\7$))++){2}((?6)|(?!\5)7())\3(?=\7$)` \- Match the facial part of a row either containing no facial features, or containing the nose.
`(?=\8$)` \- assert that we're starting at the proper column, which was marked when the previous row was processed
`(?|()|(?:(?6)(?=.+((?6)\3)\7$))++){2}` \- build up the facial part of the row one character at a time on the left and right ends. The right part is built up in `\3`. Both ends a built towards the center. The `++` ensures this is done the maximum number of times; with an even length both ends would meet, and with an odd length one character is left between them.
This uses a Branch Reset Group and `{2}` the same way as before, except that we guarantee both stages execute in the correct order differently. The `++` guarantees the second stage won't execute twice. The fact that an empty match would result in `(?=\7$)` failing to match guarantees that the first stage executes first. The fact that executing the two stages in the wrong order would result in too-long row (with the previous value of `\3` tacked in) guarantees the stages execute in the correct order.
`((?6)|(?!\5)7())` \- match either the absence of a nose or a nose. `(?6)` matches the absence of a nose, and `(?!\5)7()` matches a nose; `()` here sets `\5` to mark the fact that we've matched a nose, and `(?!\5)` prevents matching a nose if we've already done so.
`\3` \- match the right half of the facial part of the row, which we built up.
`(?=\7$)` \- assert that we're now at the first column directly to the right of the face.

`(?|()|\7(?:.(?=.*\n.*(.\7)))+){2}` \- match the padding to the right of the facial part of this line, while counting a matching number of characters of padding into `\7` from the corresponding part of the next line. Uses the same Branch Reset Group `{2}` trick as before, except that we guarantee both stages execute in the correct order in yet another different way. Sticking a `\7` in front of the second stage forces it to match too many characters if it tries to execute the second stage first, because the previous value of `\7` will be concatenated to the desired number of characters, which would only match in invalid input that has a line longer than the previous line. And the subsequent `\n` (seen below) prevents the first stage from executing twice on any valid input, because that would only match on a line shorter than the previous line. Note that in the case of zero padding, the first stage will execute twice in a row.

`\n(?=\2(.*))` \- match the end of the current line, and capture a marker for the desired starting column of the facial part of the next row in `\8`.

Upon finishing the main loop, we reach `\5.*(?=\8)_+\7$`:

`\5` \- assert that we matched a nose.
`.*(?=\8)` \- skip to the correct starting column, as marked when the previous line was processed.
`_+` \- match the mouth.
`\7$` \- assert that the mouth ended at the proper column.

# Regex (PCRE2), ~~363~~ ~~322~~ ~~283~~ ~~199~~ ~~182~~ ~~184~~ 186 bytes

This version goes above and beyond the problem statement, allowing the input to have variable-length lines.

```
/((?|^()|^(?:.(?=.*
(\2.)))+){2}(?=(?(8)(?=\8\9)(?|()|(?:(?6)(?=.+((?6)\3)\9))++){2}((?6)|(?!\5)7())\3(?=\9)|o([^o7_
])+o)(.*))(?|()|\8(?:.(?=.*
\2(\8.)(\C*)))+){2}\7
)+\5.*(?=\8)_+\9$/m

```

Try it on regex101

### Explanation

`((?|^()|^(?:.(?=.*\n(\2.)))+){2}(?=(?(8)(?=\8\9)(?|()|(?:(?6)(?=.+((?6)\3)\9))++){2}((?6)|(?!\5)7())\3(?=\9)|o([^o7_\n])+o)(.*))(?|()|\8(?:.(?=.*\n\2(\8.)(\C*)))+){2}\7\n)+`

Main loop. Matches everything except for the mouth:

`(?|^()|^(?:.(?=.*\n(\2.)))+){2}` \- on each line, match the padding to the left of the face, while counting a matching number of characters of padding into `\2` from the start of the next line. This needs to use a Branch Reset Group `(?|`...`)` in order to initialize `\2` to empty with `^()` before building it up one character at a time with `(\2.)`. The `{2}` guarantees that both stages will execute exactly once, and do so in the correct order due to each one having a `^` anchor (which matches the start of any line due to the `/m` flag). Replacing the `{2}` with `+` wouldn't work because a loop will immediately terminate after any optional iteration that matches zero characters. Note that in the case of zero padding, the first stage will execute twice in a row.

`(?(8)`...`|`...eyes...`)` \- Only allow matching the eyes if we haven't already captured `\8`, i.e. iterated through the main loop at least once.

`o([^o7_\n])+o` \- match the eyes, and define the subroutine `(?6)` to do `[^o7_\n]`. We need to explicitly exclude `\n` because otherwise the first row of the facing (containing the eyes) could be matched with newline(s) included between the eyes, which if orchestrated just right, could result in fooling the rest of the algorithm into matching a face. An alternative way of preventing this would be to capture `\7` using `(\C*)` instead of `(.*)` (which a previous version did), i.e. capturing everything to the end of the string (including newlines) instead of just to the end of the current line, but this results in worse golf, because we would also need to do `(?=\7).*\n` instead of `\7\n`, costing 6 bytes total.

`(?=\8\9)(?|()|(?:(?6)(?=.+((?6)\3)\9))++){2}((?6)|(?!\5)7())\3(?=\9)` \- Match the facial part of a row either containing no facial features, or containing the nose. (Do this in a lookahead so that we can iterate a second time over the same characters, in order to count them.)
`(?=\8\9)` \- assert that we're starting at the proper column, which was marked when the previous row was processed
`(?|()|(?:(?6)(?=.+((?6)\3)\9))++){2}` \- build up the facial part of the row one character at a time on the left and right ends. The right part is built up in `\3`. Both ends a built towards the center. The `++` ensures this is done the maximum number of times; with an even length both ends would meet, and with an odd length one character is left between them.
This uses a Branch Reset Group and `{2}` the same way as before, except that we guarantee both stages execute in the correct order differently. The `++` guarantees the second stage won't execute twice. The fact that an empty match would result in `(?=\9)` failing to match guarantees that the first stage executes first. The fact that executing the two stages in the wrong order would result in too-long row (with the previous value of `\3` tacked in) guarantees the stages execute in the correct order.
`((?6)|(?!\5)7())` \- match either the absence of a nose or a nose. `(?6)` matches the absence of a nose, and `(?!\5)7())` matches a nose; `()` here sets `\5` to mark the fact that we've matched a nose, and `(?!\5)` prevents matching a nose if we've already done so.
`\3` \- match the right half of the facial part of the row, which we built up.
`(?=\9)` \- assert that we're now at the first column directly to the right of the face.

`(.*)` \- capture a marker `\7` for the column directly to the right of the facial part of the current line

`(?|()|\8(?:.(?=.*\n\2(\8.)(\C*)))+){2}` \- match the facial part of the current line again, this time to count the characters in it, so as to build up a capture in `\8` of a matching number of characters from the facial part of the next line, as a marker for column alignment, and capture in `\9` a marker for the column directly to the right of the facial part of that line. Uses the same Branch Reset Group `{2}` trick as before, and a very similar way of guaranteeing that both stages execute in the correct order. Sticking a `\8` in front of the second stage forces it to match too many characters if it tries to execute the second stage first, because the previous value of `\8`, not having been emptied by running the first stage, will be concatenated to the desired number of characters; this prevents `\7\n` from matching later. And a match can't result from executing the first stage twice – doing so would match an empty row, but the lookahead that matched the facial row the first time already guaranteed that it's of nonzero length.

`\7\n` \- match the non-facial ending of the current line, ensuring that we ended on the correct column.

Upon finishing the main loop, we reach `\5.*(?=\8)_+\9$`:

`\5` \- assert that we matched a nose.
`.*(?=\8)` \- skip to the correct starting column, as marked when the previous line was processed.
`_+` \- match the mouth.
`\9$` \- assert that the mouth ended at the proper column.

*+2 bytes (184 → 186) to fix a bug found by jaytea*
> 6 votes

# Answer
# Retina 0.8.2, ~~129~~ 120 bytes

```
T`o7\_p`o7=-
((?<=(.)*)(?(1)\3-7-\3|o((-)*)-\3o).*¶(?>(?<-2>.)*)((?<=(.)*)-\3-\3-.*¶(?>(?<-6>.)*))*){2}(?>(?<-4>==)*)===

```

Try it online! Outputs 0 if there is no face, otherwise a positive integer number of nonoverlapping faces. Edit: Bug fix for minimal-width faces and saved 9 bytes thanks to @Deadcode. Explanation:

```
T`o7\_p`o7=-

```

Transliterate everything other than `o`, `7` and `_` to `-`. `_` gets transliterated to `=` as that avoids having to quote it again. (I used `-` as I find spaces confusing.) The next stage then defaults to a match count stage.

```
(

```

Group 1 is just here so that it can be repeated.

```
(?<=(.)*)

```

Count the current indentation into capture group 2.

```
(?(1)\3-7-\3|o((-)*)-\3o)

```

If capture group 1 has already been matched, then match `-7-` surrounded by capture group 3 (the nose), otherwise match `o`, a string of `-`s into capture group 3 and its count into capture group 4, another `-`, a copy of capture group 3, and a final `o` (the eyes).

```
.*¶(?>(?<-2>.)*)

```

Match until the same amount of indentation on the next line.

```
((?<=(.)*)-\3-\3-.*¶(?>(?<-6>.)*))*

```

Optionally match any number of lines containing three `-`s and two copies of capture group 3 (empty line), keeping track of and advancing to the same amount of indentation on the next line using capture group 6.

```
){2}

```

Match this whole group twice.

```
(?>(?<-4>==)*)===

```

Match two `=`s for each `-` captured in capture group 4, plus a final three `=`s (mouth). Here as in the previous two cases of balancing groups, the atomic group requires that any available `=`s are matched against the balancing group, so that the whole regex fails if there aren't three `=`s left over.
> 5 votes

# Answer
# APL (Dyalog Unicode), ~~85~~ 77 bytes (SBCS)

Anonymous monadic function taking a matrix of characters as argument.

```
1∊∊{⍵∘{(⍉3,⍨a⍪⍵⍪⊖a←2↑⍨2 1÷⍨⍺-1)⍷4-'_o7'⍳A}¨0,¨↓∘.=⍨⍳¯2+2⌷⍵}¨1 2∘+¨2 1∘×¨⍳⍴A←⎕

```

Try it online!

*-8 bytes thanks to @Adám*

### Interesting Bits

This ends up encoding `eyes=2, nose=1, underscore=3`.

```
1 2∘+¨2 1∘×¨⍳⍴A←⎕ ⍝ Get at least all sizes (m,n) that fit in A such that
                       ⍝ m is odd and n≥3 (surely this can be done shorter)
                       ⍝ The search arrays are constructed transposed, so m ends
                       ⍝ up being the width
0,¨↓∘.=⍨⍳¯2+2⌷⍵      ⍝ For a given height m, get all nose positions
                       ⍝ e.g. m=3 gives (0 1 0 0)(0 0 1 0)(0 0 0 1)
(2 1÷⍨⍺-1)↑2         ⍝ My favorite expression. Generates one-half of the face
                       ⍝ ⍺ is (m,n), so (2 1÷⍨⍺-1) gives dimension pair ((⍺-1)÷2) (⍺-1)

```
> 5 votes

# Answer
# APL (Dyalog Unicode), ~~90~~ 85 bytes (SBCS)

Anonymous tacit prefix function taking a character matrix argument. Requires `⎕IO←0` (0-based indexing).

```
1∊∘∊{(∊¨1↑¨¨⍨1+⍳1,⍨⊣\⍴⍵)∘.⍀{'_'⍪⍨(⊢,0 1↓⌽)' 7',⍨2↑'o',1⍵⍴''}¨⍳⊢/⍴⍵}⍷¨∘⊂' '@(~∊∘'o7_')

```

Try it online!

This works by brute force; generating all possible faces and looking for them in turn.

`' '@()` amend with spaces **at** the locations indicated by the following mask:

`∊∘'o7_'` membership of the set of special symbols

`~` negate that

This replaces all non-special characters with spaces.

`{``}⍷¨∘⊂` mask where each of the following have a top-left corner in the entirety of that:

`⍴⍵` the shape of the argument (rows, columns)

`⊢/` the rightmost element of that (columns)

the indices 0…n-1 of that.

`{` apply the following function on each index:

`1⍵⍴''` create 1-row argument-column matrix of spaces

`'o',` prepend a column of eyes

`2↑` append a blank row (lit. take the first two rows)

`' 7',⍨` append a column consisting of a space above a nose

`(``)` apply the following tacit function to that:

mirror the argument (puts the nose column on the left)

`0 1↓` drop no rows but one column (removes the nose column)

`⊢,` prepend the argument (this creates the full eye and nose rows)

`'_'⍪⍨` append a row of underscores (to form the mouth)

This gives us a collection of all possible three-row faces.

`(``)∘.⍀` create all combinations of the following masks expanding (inserting blank rows on zeros) those faces:

`⍴⍵` the shape of the argument

`⊣\` two copies of the row-count (lit. cumulative left-argument reduction)

`1,⍨` append a one

the Cartesian coordinates of an array of that size

`1+` increment

`1↑¨¨⍨` for each of each of those, create a mask of length with a single leading one (lit. take that many elements from one)

`∊¨`**ϵ**nlist (flatten) each

This gives us all the possible expansion masks

**ϵ**nlist (flatten)

`1∊∘` is one a member thereof?
> 4 votes

# Answer
# Python 3, 213 bytes

Returns `False` when it finds a face and `True` when it doesn't.

```
lambda s:all(re.subn(f"\\n.{{{p}}}[^o_7]{{{g}}}7[^o_7]{{{g}}}",'',x)[1]-1for p in range(len(s))for g in range(len(s))for x in re.findall(f"^.{{{p}}}o[^o_7]{{{2*g-1}}}o([\S\s]+)^.{{{p}}}__{{{2*g}}}",s,8))
import re

```

The idea is that for each possible face size and indention, we look for eyes and a mouth in correct location (ignoring noses), then make sure there is exactly one nose that is centered.

`p` is the left padding of the face, `g` is the gap from face edge to nose, and `8` is the value of `re.MULTILINE`.

Try it online!
> 3 votes

# Answer
# PCRE2, 168 bytes

```
(?=(?13)(.*))o(?6)*(?=(?13)(.*))o((?=(.*?)(.\5|(?13)\2$)|)([^7o_]|(?!\7|(?5))\4()7)(((?=(?13)(.+\1|(?!.*\2)))\C)+(_+()((.(?=(.*+\C+?)(.\16?$)))*+\15?+)(?10))?)?)++\7\12

```

https://regex101.com/r/dHsdBq/2

@Deadcode made me do it :P

It's theoretically valid but fails that one test because of catastrophic backtracking.

Bonus: https://regex101.com/r/dHsdBq/3 166 bytes, PCRE1 (dropped both possessive `+`s in `(?13)`)

The general method: `(?13)` will jump from the current point to the same position on the very last line of the subject. So, at any point in the face, you can compare what is captured in `(?=(?13)(.*))` to that captured at any other point in the face, particularly following the eyes (`\1` and `\2`, in order to determine whether or not you're in the face.

`(?=(?13)(.+\1|(?!.*\2))` is therefore true when you're not in a face. The regex goes through face characters one at a time, but consumes at once characters from the end of the face on one line to the start of the face on the next. While doing so, it also optionally tests for a mouth.

`(?=(.*?)(.\5|(?13)\2$)|)` is used to locate the nose in the middle of the face. It collects in `\5` characters from the end of the face on the current line, so that `(.*?)` finally matches the empty string once the middle of the face is reached.
> 3 votes

# Answer
# , 101 93 99 97 bytes

```
1 e.[:,>@{@;&(1+i.)/@$(((-:1 2 3*[:#:i:@_1+2^<:,<.@-:,])*2|]){:@$)@((4|'ao7_'&i.)-.0{0:"+);._3"$]

```

Try it online!
> 2 votes

# Answer
# Java (OpenJDK 8), 290 bytes

```
int D(String[]t){for(int a=0,z=t.length,y=t[0].length();a<z;a++)for(int b=0;b<y;b++)for(int c=b+2;c<y;c+=2)for(int d=a+1;d<z;d++)for(int e=d+1;e<z;e++)if(t[a].charAt(b)=='o'&&t[a].charAt(c)=='o'&&t[d].charAt((b+c)/2)=='7'&&t[e].substring(b,c+1).replace("_","").isEmpty())return 1;return 0;}

```

Try it online!

Takes a String\[\] broken at the lines as input and outputs 1 and 0 for true and false
> 2 votes

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


title: Get thee behind me Satan-Prime!

text:
# Question
Title: Get thee behind me Satan-Prime!
# Satan-Primes

who are they?
they are `Primes` containing `666`
these are Satan-Primes:`[46663,266677,666599,666683,616669]`
these are **NOT** :`[462667,665669,36363631,555]`

# Plot

*Every number bigger than 6661 has Satan-Primes behind him*

# The Challenge

Given an integer `n>6661` find the Satan-Prime **behind (or equal) and closest** to itself.

# Examples

Integer `n=30000` has 3 Satan-Primes(SP) behind it:`[6661, 16661, 26669]`.
Your code must return `26669` which is the closest behind it

# Test Cases

Input-\>Output

```
6662->6661
10000->6661
66697->66697 (a SP returns himself)
328765->326663
678987->676661
969696->966677

```

# Rules

Yor code should work for any `n` in the range of your language.

This is , so the shortest answer in bytes wins!

# Answer
# Neim, 9 bytes

```
>ͻ:D+6S÷

```

Explanation:

```
>         Increment input
 ͻ        Start infinite loop
  :        Previous prime
   D       Duplicate
    +6     Push 666
      S    Swap
          See if 666 is a substring of the top of the stack
        ÷  If true, break

```

Try it online!
> 8 votes

# Answer
# Mathematica, 82 bytes

```
Last@Select[Prime@Range@PrimePi@#,!FreeQ[Subsequences[IntegerDigits@#],{6,6,6}]&]&

```
> 7 votes

# Answer
# Jelly, ~~10~~ 9 bytes

Saved 10% thanks to @Dennis!

```
ÆRwÐf666Ṫ

```

Try it online!

### Explanation

```
ÆR          # All primes in range [2, input]
   Ðf      # Keep those which satisfy
  w        # truthy if y is in x
     666   #           ^ (this is y)
        Ṫ  # Tail (take the last element)

```
> 7 votes

# Answer
# Pyth, ~~15~~ 14 bytes

*Saved 1 byte with help from Dave*.

Memory errors for `969696` and anything higher on my machine, but it is fine if it is given enough memory.

```
ef&/`T*3\6P_TS

```

**Try it here or check out the Test Suite.**

---

# How?

```
ef&/`T*3\6P_TSQ - Full program, with implicit input (Q) at the end

             SQ - Range [1,Q]
 f              - Filter.
          P_T   - Is prime?
  &             - And
   /`T*3\6      - It contains 666.
e               - Last element.
                - Implicitly output the result.

```

# Pyth, 14 bytes

```
ef/`T*\63fP_TS

```

**Try it here!**
> 5 votes

# Answer
# Bash + Core Utils, 51 49 Bytes

```
seq $1|tac|factor|awk 'NF==2&&/666/&&!a--&&$0=$2'

```

Takes command line argument. Can be quite slow with larger numbers.
> 4 votes

# Answer
# 05AB1E, 11 bytes

```
ƒNpN666å*iN

```

Try it online!
> 4 votes

# Answer
# Mathematica, ~~64~~ ~~62~~ ~~61~~ 53 bytes

```
#//.i_/;!PrimeQ@i||ToString@i~StringFreeQ~"666":>i-1&

```

*-1 byte thanks to @KellyLowder*

*-8 bytes (wow) thanks to @Notatree*

## Explanation

Take an input. We decrement it under these conditions:

* the input is not prime, OR
* the digits of the inputs does not contain three 6s in a row.

We repeat that until a Satan prime is reached.
> 4 votes

# Answer
# Japt, 14 bytes

```
õ fj w æ_sø666

```

Test it

Seeing as there *was* a 50% time-based bonus: Completes test case `969696` in under half a second.

---

## Explanation

Implicit input of integer `U`.

```
õ

```

Generate an array of integers from `1` to `U`.

```
fj

```

Filter (`f`) primes.

```
w

```

Reverse.

```
æ_

```

Return the first element that returns a truthy value (in this case `1`) when passed through a function that checks if ...

```
sø666

```

The integer converted to a string (`s`) contains (`ø`) 666.

---

## Faster Alternative, 15 bytes

Again, seeing as there was originally a time-based bonus, here's an alternative, and much faster, solution which I can't seem to golf any further.

```
U-@j *U´sø666}a

```

Test it
> 3 votes

# Answer
# Perl 5, 47 bytes

46 bytes of code + 1 for `-p`

```
{$f=0|sqrt;1while$_%$f--;/666/*!$f||$_--*redo}

```

Try it online!
> 3 votes

# Answer
# PowerShell, 128 bytes

```
param($n)function f($a){for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}for(){if($n-match666-and($n-eq(f $n))){$n;exit}$n--}

```

Try it online!

PowerShell doesn't have any prime factorization built-ins, so this borrows code from my answer on Prime Factors Buddies.

We take input `$n`, then declare a new `function f` that calculates out the factors of input `$a`. If the input `$a` is prime, then this will return just `$a`.

The main part of the program is the infinite `for()` loop. Inside the loop, we check if `$n` `-match`es against `666` and whether `$n` is prime (i.e., `$n` matches all of the factors of `$n`). If it is, we place `$n` on the pipeline and `exit`, with implicit output. Otherwise, we decrement `$n--` and continue the loop.
> 2 votes

# Answer
# Python 2, 77 76 bytes

**Edit:** -1 byte thanks to @Mr.Xcoder

Slow running time, runs in `O(n^2)`

```
lambda x:max(q for q in range(x+1)if"666"in`q`*all(q%t for t in range(2,q)))

```

Try it online!

## Another 76 bytes solution

```
lambda x:max(q*("666"in`q`*all(q%t for t in range(2,q)))for q in range(x+1))

```

Try it online!

# With SymPy 73 bytes

```
lambda x:max(q for q in primerange(0,x+1)if"666"in`q`)
from sympy import*

```

Try it online!
> 2 votes

# Answer
# Bash + bsd-games package, 33

* 2 bytes saved thanks to @FedericoPoloni.

```
primes 2 $[$1+1]|grep 666|tail -1

```

Try it online.
> 2 votes

# Answer
# PowerShell, 71 69 64 bytes

```
param($s)for(;$s-notmatch666-or(2..($s/2)|?{!($s%$_)});$s--){}$s

```

Try it online!

* 328765 takes ~30 seconds on my machine, but times out the 60 second limit on Tio.run.
* 678987 takes ~1.5 minutes.
* 969696 takes ~4.5 minutes.
> 2 votes

# Answer
# MATL, 16 bytes

```
ZqP"@V'666'Xf?@.

```

Try it at MATL Online

**Explanation**

```
         Implicitly grab input (n)
Zq       Compute the primes up to n (output is in increasing order)
P        Flip the array (so larger primes come first)
"        For each prime
  @V     Convert it to a string
  '666'  Push the string literal '666' to the stack
  Xf     Find the location of '666' in the prime
  ?      If it was present...
    @.   Push it to the stack and break
         Implicitly display the stack contents

```
> 2 votes

# Answer
# C++ 389 bytes

```
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
using namespace boost::random;typedef boost::multiprecision::cpp_int Z;int main(int,char**v){mt19937 m(clock());independent_bits_engine<mt11213b,256,Z>g(m);Z n{v[1]},p;while(p++<=n)if(miller_rabin_test(p,25,g)&&p.convert_to<std::string>().find( "666" )!=-1)std::cout<<p<<" ";}

```

This is a full program!
You'll need Boost to compile it. (Or copy and paste into your favorite online C++ shell.)
Run it from the command-line giving ***n*** as argument.

Ungolfed:

```
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
using namespace boost::random;

typedef boost::multiprecision::cpp_int integer;

int main( int argc, char** argv )
{
  mt19937 mt( clock() );
  independent_bits_engine <mt11213b, 256, integer> rng( mt );

  integer input {argv[ 1 ]};
  integer possible;

  while (possible++ <= input)
    if (
      // is_prime( possible )
      miller_rabin_test( possible, 25, rng )
    &&
      // possible has "666" in it
      (possible.convert_to <std::string> ().find( "666" ) != std::string::npos))

    std::cout << possible << " ";
}

```

Shortcuts were made in terms of random number testing. The original code started testing possible primes at 6661 and incremented by two. You'll also get a compiler warning because of that (-1) there instead of npos.

Still, this runs pretty quickly. It only took about 40 seconds to find all 214 satan primes under 1,000,000 on my old AMD Sempron 130.

:^D
> 2 votes

# Answer
# Stax, 10 bytes

```
ü>:Ñb/VP6─

```

Run and debug it

Explanation (unpacked):

```
^w:pc$666$#! Full program, implicit input-parsing
^            Increment input
 w           do-while:
  :p           Previous prime
    c$         Copy and stringify
      666$     Push "666"
          #    Number of occurences
           !   Logical not
             Implicit output

```
> 2 votes

# Answer
# , 57 bytes

```
(a=conf.design::primes(scan():1))[which(grepl(666,a))[1]]

```

-42 bytes from Dominic Van Essen's enormous golf.

uses `grepl` to coerce values to string(since 666 cannot be considered a regex) and check for truthy values.

Runs through the array in reverse to save 2 bytes.

# \+ `conf.design`, <sup>~~81 78~~</sup> 99 bytes

```
library(conf.design);function(n){a=primes(1:n)
a[max(which(grepl("666",as.character(a),fixed=T)))]}

```

Try it on rdrr.io!

My first R solution.

+21 bytes after including library name.

A simple filter. grepl returns true at indices with 666, which returns the truthy indices, and max gets the required index of the prime.
> 2 votes

# Answer
# Python 3, ~~85 83~~ 80 bytes

Halvard's is 4 bytes shorter because it's done in Python 2.

```
lambda k:max(x for x in range(k+1)if"666"in str(x)*all(x%i for i in range(2,x)))

```

Try it online!

Give it some time, it's extremely slow because of its `O(n^2)` complexity.
> 1 votes

# Answer
# JavaScript (ES6), ~~55~~ 54 bytes

*-1 byte thanks to @ThePirateBay.*

```
f=n=>/666/.test(d=n)&eval("while(n%--d);d<2")?n:f(n-1)

```

**Very** slow with large inputs. Primality test adapted from this code golf answer.

## Timings

* Input `10000` took 10 seconds
* Input `328765` took 3 minutes
* Input `678987` took 9 minutes
* Input `969696` took 16 minutes

## Tests

Some of these will hang your browser for several minutes.

```
f=n=>/666/.test(d=n)&eval("while(n%--d);d<2")?n:f(n-1)

function test(n) {
  O.value="Working..."
  setTimeout(_=>{
    let t = Date.now()
    O.value=`f(${n}) = ${f(n)} in ${(Date.now()-t)/1000}s`
  }, 10)
}
```

```
Tests<br>
<button onclick="test(6662)">6662</button>
<button onclick="test(10000)">10000</button>
<button onclick="test(328765)">328765</button>
<button onclick="test(678987)">678987</button>
<button onclick="test(969696)">6662</button><br>
Result<br>
<input id=O type=text size=25 readonly>
```

## Faster Version, 56 bytes

Completes each test case in under a second.

```
f=n=>/666/.test(n)&&eval("for(d=2;n%d++;);d>n")?n:f(n-1)

;[6662, 10000, 328765, 678987, 969696].forEach(n=>console.log(`f(${n}) -> ${f(n)}`))
```
> 1 votes

# Answer
# Ruby, ~~67~~, ~~66~~, ~~58~~, 56 bytes

Includes `+7` bytes for `-rprime`

```
->z{z.downto(1).find{|x|/666/=~x.to_s&&x.prime?}}

```

It's pretty fast, computing values up to `~2^52` in about a second and `2^64` in under 5 minutes (2011 MBP, Ruby 2.3.1).
> 1 votes

# Answer
# PHP, 148 bytes

```
<?php $p=[2];$s=[];for($i=3;$i<=$argv[1];$i++){foreach($p as $q)if($i%$q===0)continue 2;$p[]=$i;if(strpos($i,'666')!==false)$s[]=$i;}echo end($s);?>

```

Try it online!
> 0 votes

# Answer
# Perl 6, 35 bytes

```
my&f={/666/&&.is-prime??$_!!f $_-1}

```

Try it online!

Straightforward recursive solution.
> 0 votes

# Answer
# C# (.NET Core), 117 115 112 bytes

```
f=>{for(int i=f;i>1;i--){int p=1,j=2;while(j<i)if(i%j++<1)p=0;if(p>0&$"{i}".Contains("666"))return i;}return 0;}

```

Try it online!

* 2 bytes saved by removing unnecessary braces.
* 3 bytes saved by combining `int` declarations.

I'm sure this could be made shorter; maybe by recursively calling `func f` and removing the outer `for`-loop.

### Recursive Approach, 85 bytes

```
i=>{int p=1,j=2;while(j<i)if(i%j++<1)p=0;return p>0&$"{i}".Contains("666")?i:f(--i);}

```

Try it online!

I'm unsure how well this approach fits within the bounds of code-golf due to having to set the `Func<int,int> f = null` first, and that `f` is called again, but not counted towards the bytes. Any clarification would be appreciated.
> 0 votes

# Answer
# 05AB1E, 9 bytes

```
ÅPR.Δ666å

```

Try it online. (No test suite with all test cases, because it's a bit too slow.)

**Explanation:**

```
ÅP         # Push a list of primes below or equal to the (implicit) input-integer
  R        # Reverse this list
   .Δ      # Find the first value which is truthy for:
     666å  #  Check whether it contains "666" as substring
           # (after which the found result is output implicitly)

```

The `666` can alternatively be `Ž2ć` (compressed 666) or `Ƶé·` (compressed 333 and then doubled).
> 0 votes

# Answer
# Java 8, 77 bytes

```
n->{for(int i=++n;i>1|!(n+"").contains("666");)for(i=--n;n%--i>0;);return n;}

```

Try it online.

**Explanation:**

```
n->{               // Method with integer as both parameter and return-type
  for(int i=++n;   //  Increase the input by 1
                   //  Set `i` to this input+1 (setting `i` to anything above 1 is fine)
      i>1          //  Continue looping as long as `i` is not 0 nor 1
      |!(n+"").contains("666");)
                   //  or if `n` as String does not contain "666" as substring:
    for(i=--n;     //   Decrease `n` by 1 first
                   //   And then set `i` to this new `n`
        n%--i      //   Decrease `i` by 1 before every iteration
             >0;); //   And continue looping as long as `n` does NOT evenly divide `i`
  return n;}       //  After both loops, return the modified `n` as result

```

If `for(i=n;n%--i>0;);` results in \\$i\<2\\$, it means \\$n\\$ is a prime number (note: this prime checker only works for \\$n\geq2\\$, which is fine in this case).
> 0 votes

# Answer
# Husk, 12 bytes

```
ḟo`€d666dfṗṫ

```

Try it online!
> 0 votes

---
Tags: code-golf, primes
---


title: It's Your Turn ! (Renju)

text:
# Question
Title: It's Your Turn ! (Renju)
*EDITS*:

* Added link to the plain-text (multiple strings) test data
* Added BLANK,EDGE and TIE2 test cases (see Test Data section) (11/25)
* Updated the JSON test cases (some lines were ill-formatted) (11/24)

Renju match gone bad ! (well, technically these guys are playing Go, but who cares) Wikisource

# TL;DR

Take a 15x15 grid of characters (made of **'.'**, **'0'** and **'\*'**), as an input, replace one of **'.'** s with **'\*'**, in such a way that an unbroken horizontal, vertical or diagonal line of exactly five '\*' chars is formed.

```
           *        *    *
           *       *      *
 ******    *      *        *
           *     *          *
           *    *            *

```

Output the coordinates of your **'\*'**, or string - **'T'** if there is no solution.

Creating a line of more than 5 **'\*'** long (directly or indirectly) is not allowed, this is called an "overline".

Some examples of overlines:

```
 ****.** - replacing . with * will result in a horizontal overline

 *.***  - replacing . with * will result in a diagonal overline
   *
    *
     *
      *
       *

```

# Full Version

**Abstract**

Renju \- is an abstract strategy board game (a simpler version of it is also known as Gomoku).

The game is played with *black* and *white* stones on a 15×15 gridded *Go* board.

*Black* plays first if *white* did not just win, and players alternate in placing a stone of their color on an empty intersection. The winner is the first player to get an unbroken row of five stones horizontally, vertically, or diagonally.

Computer search by L. Victor Allis has shown that on a 15×15 board, *black* wins with perfect play. This applies regardless of whether overlines are considered as wins.

Renju eliminates the "Perfect Win" situation in Gomoku by adding special conditions for the first player (*Black*).

(c) Wikipedia

**Objective**

Consider you are a part of a Renju match, you are playing black, and there is just one turn left for you to win.

Take the current board position as an input, identify one of the winning moves (if there is one), and output it (see below for the data formats and restrictions).

Sample input board:

```
    A B C D E F G H J K L M N O P       . - vacant spot (intersection)
 15 . . . . . . . . . . . . . . . 15    0 - white stone
 14 . . . . . . . . . . . . . . . 14    * - black stone
 13 . . . . . . . . . . . . . . . 13    X - the winning move
 12 . . . . . . . . . . . . . . . 12
 11 . . . . . . . . . . . . . . . 11
 10 . . . . . . . 0 . . . . . . . 10
  9 . . . . . . . * . . . . . . .  9
  8 . . . . . . . * . . . . . . .  8
  7 . . . 0 . . . * . . . . . . .  7
  6 . . . 0 0 . . * . . . . . . .  6
  5 . . . . . . . X . . . . . . .  5
  4 . . . . . . . . . . . . . . .  4
  3 . . . . . . . . . . . . . . .  3
  2 . . . . . . . . . . . . . . .  2
  1 . . . . . . . . . . . . . . .  1
    A B C D E F G H J K L M N O P

```

(axis labels are for illustration purposes only and *are not* part of the input)

Sample output:

```
H5

```

**Rules**

For the purpose of this challenge, only the following subset of Renju rules apply:

* You can place your stone on any vacant intersection (spot);
* Player who achieved an unbroken row of five stones horizontally, vertically, or diagonally, wins;
* Black (you) may not make a move which will result (directly or indirectly) in creation of an "overline" i.e. six or more black stones in a row.

**Data Formats**

Input data is a 15x15 grid of characters (".","\*","0"\]), ASCII-encoded, in any acceptable format, e.g. a two-dimensional character array or a newline separated set of strings e.t.c.

You *may not* however modify the input alphabet in any way.

Output data is a string, denoting the alpha-numeric board position, as illustrated by the sample board above.

Note that original horizontal axis numeration (A..P), does not include 'I', you *MAY* use 'A..O' instead, w/o penalty.

If there is no winning move available, output "T" instead.

**Scoring**

This is , so the shortest answer in bytes wins !

**Some Tests Cases**

*Tie*

Input:

```
    A B C D E F G H J K L M N O P
 15 . . . . . . . . . . . . . . . 15
 14 . . . . . . . . . . . . . . . 14
 13 . . . . . . . . . . . . . . . 13
 12 . . . . . . . . . . . . . . . 12
 11 . . . . . . . . . . . . . . . 11
 10 . . . . . . . 0 . . . . . . . 10
  9 . . . . . . . * . . . . . . .  9
  8 . . . . . . . * . . . . . . .  8
  7 . . . 0 . . . * . . . . . . .  7
  6 . . . 0 0 . . * . . . . . . .  6
  5 . . . . . . . Z . . . . . . .  5
  4 . . . . . . . * . . . . . . .  4
  3 . . . . . . . . . . . . . . .  3
  2 . . . . . . . . . . . . . . .  2
  1 . . . . . . . . . . . . . . .  1
    A B C D E F G H J K L M N O P

```

Output:

```
 "T", the only "winning move" is H5 (denoted with "Z"), but that would create an overline H4-H9

```

*Overline*

Input:

```
    A B C D E F G H J K L M N O P
 15 . . . . . . . . . . . . . . . 15
 14 . . . . . . . . . . . . . . . 14
 13 . . . . . . . . . . . . . . . 13
 12 . . . . . . . . . . . . . . . 12
 11 . . . . . . . . . . . . . . . 11
 10 . . . . . . . . . . . . . . . 10
  9 . . . . . 0 . . . . 0 . . . .  9
  8 . . 0 . . . . . . * 0 0 . . .  8
  7 . . 0 . . . . . * . . 0 . . .  7
  6 . . 0 * . 0 . * . . 0 0 . . .  6
  5 . . 0 . * . * X * * * . . . .  5
  4 . . . . . Z . . . . . . . . .  4
  3 . . . . . . * . . . . . . . .  3
  2 . . . . . . . * . . . . . . .  2
  1 . . . . . . . . * . . . . . .  1
    A B C D E F G H J K L M N O P

```

Output:

```
 "H5", the other possible winning move is "F4", but that would result in J1-D6 diagonal overline.

```

*Multiple winning moves*

Input:

```
    A B C D E F G H J K L M N O P
 15 . * * * . . * * * . . . . . . 15
 14 . * . . . . . * . . * . . . . 14
 13 . * . . . . . . . . . . . * . 13
 12 . . . . . 0 0 0 0 0 0 0 . * . 12
 11 . . . . 0 . . X . . . 0 . * * 11
 10 . . . . 0 X * * * * X 0 . . * 10
  9 . . . . 0 . . * . . . 0 . * *  9
  8 . . . . 0 0 . * . . 0 0 . * .  8
  7 . . . . . 0 . * . . 0 . . * .  7
  6 . . . . . 0 . X . . 0 . . . .  6
  5 . . . . . 0 0 0 0 0 0 . . . *  5
  4 . . . . . . . . . . . . . . .  4
  3 . . . . . . . . . . . . . . .  3
  2 . . . . . . . . . . . . . . .  2
  1 . . . . . . . . . . . . . . .  1
    A B C D E F G H J K L M N O P

```

Output:

```
"H6" or "H11" or "F10" or "L10" (one of)

```

**Test Data**

The test data in a bit more machine-friendly form (JSON) is available HERE

Added BLANK,EDGE and TIE2 test cases: UPDATED TEST SUITE

You can use the following JS snippet to convert it to multiline strings, if necessary:

```
for(B in RENJU) { console.log(B+"\n"+RENJU[B].map(l=>l.join``).join`\n`); }

```

or just download them here

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

Input as multiline string.

Note: could save 1 byte using `A..O` instead of `A..P`

```
s=>[...s].some((q,p)=>([1,15,16,17].map(d=>x=(q=((r=p=>s[p-d]=='*'?r(p-d):p)(a=p)-r(p,d=-d))/d)>x?q:x,x=q!='.'&&5),x==4))?'ABCDEFGHJKLMNOP'[a%16]+(15-(a>>4)):'T'

```

*Less golfed*

```
s=>
[...s].some(
  (q, p) => // execute for each character q in position p, stop when true
  (
    [1, 15, 16, 17].map( // offset for 4 directions
      d => // for each direction d
      (
        // recursive function to find adjacent '*' in direction -d
        r = p => s[p-d] == '*' ? r(p-d) : p,
        // I need 4 adjacent '*' in at least 1 direction
        // but no more in any direction
        a = p, // current position in a, could be the answer
        q = r(p), // look back (reuse variable q)
        d = -d, q -= r(p), // then look forward
        q = q/d, // number of '*' in q
        x = q > x ? q : x // keep the max in any direction
      ),
      // init x to 0 if the current position is empty
      // else init x to 5, so it will be not valid in any case (too big)
      x = q !='.' && 5
    ),
    // if 4 '*' found, exit the loop
    x==4
  )
) // return true if solution found (solution in a)
? 'ABCDEFGHJKLMNOP'[a % 16] + (15 - ( a >> 4))
: 'T'

```

**Test**

```
F=
s=>[...s].some((q,p)=>([1,15,16,17].map(d=>x=(q=((r=p=>s[p-d]=='*'?r(p-d):p)(a=p)-r(p,d=-d))/d)>x?q:x,x=q!='.'&&5),x==4))?'ABCDEFGHJKLMNOP'[a%16]+(15-(a>>4)):'T'

out=x=>O.textContent+=x+'\n\n'

;renju = {
"BLANK":"...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............",
"EDGE":"...........****\n.0.............\n.0.............\n.0.............\n.00000.........\n.....0.........\n.....0.........\n.....0.........\n.....0.........\n...............\n...............\n.....*........*\n....*.........*\n...*..........*\n..*...........*",
"TIE":"...............\n...............\n...............\n...............\n...............\n.......0.......\n.......*.......\n.......*.......\n...0...*.......\n...00..*.......\n...............\n.......*.......\n...............\n...............\n...............",
"TIE2":"...............\n.....0****000..\n...............\n.*0............\n..*.0..........\n..0*...0.......\n.......*.......\n.......*.......\n.......*.00....\n.......*.......\n.......0.......\n...............\n...............\n...............\n...............",
"OVERLINE":"...............\n...............\n...............\n...............\n...............\n...............\n.....0....0....\n..0......*00...\n..0.....*..0...\n..0*.0.*..00...\n..0.*.*.***....\n...............\n......*........\n.......*.......\n........*......",
"MULTIPLE":"...............\n...............\n...............\n.....0000000...\n....0......0...\n....0.****.0...\n....0..*...0...\n....00.*..00...\n.....0.*..0....\n.....0....0....\n.....000000....\n...............\n...............\n...............\n..............."
};

for(k in renju) {
  var r=F(renju[k])
  out(k+' '+r+'\n   ABCDEFGHJKLMNOP\n'+renju[k].split`\n`.map((v,i)=>(115-i+' ').slice(1)+v).join`\n`)
}
```

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

# Answer
> 2 votes
# PHP, ~~205~~ ~~203~~ ~~201~~ ~~246~~ ~~257~~ 238 bytes

requires PHP\<7.1 (relies on empty negative string offsets)

third approach, finally really complete, and I think I have left nothing to golf.

```
for($p=240;(!$l|$o)&&$p--;)for($k=4,$l=$o=0;$k--;$l|=preg_match("#\*{5}#",$s),$o+=preg_match("#\*{6}#",$s))for($s="*",$i=0;"."==($g=$argv[1])[$p]&&$i++<5;)$s=$g[$p-$i*$d=!$k?:$k+14].$s.$g[$p+$d*$i];echo$p<0?T:chr(65+$p%16).(15-($p/16|0));

```

takes multiline string with Linux style linebreaks (1 character) from command line argument.
For 2 character linebreak: add one each to `14`, `15` and `16` and replace `240` with `255`.

Run with `-r`.

**breakdown**

```
for($p=240;(!$l|$o)&&$p--;)     // loop through positions while (no line or has overlines)
    for($k=4,$l=$o=0;$k--;          // loop through four directions
        $l|=preg_match("#\*{5}#",$s),   // post condition: set flag for line
        $o+=preg_match("#\*{6}#",$s)    // and count overlines
        )
        for($s="*",                     // assume asterisk at current position
            $i=0;
            "."==($g=$argv[1])[$p]      // if character is "."
            &&$i++<5;)                  // look 5 fields in +/- direction:
            $s=$g[$p-$i*
                $d=!$k?:$k+14               // map [3,2,1,0] to offset [17,16,15,1]
            ].$s.$g[$p+$d*$i];              // add characters
                                // output
echo$p<0?T:chr(65+$p%16).(15-($p/16|0));

```

uses columns `A..O`. For `A..H`+`J..P`, append `+($p/8&1)` to the `chr` parameter.

# Answer
> 1 votes
# Jelly, 46 bytes

```
ṭ³Ṛœẹ”*¤ŒṬµ;Z;ŒD;ŒdŒrẎḢƇṀf5
Ṛœẹ”.ÇƇḢṚịØA,ɗ/ȯ”T

```

Try it online! (OVERLINE testcase)

44 bytes if you allow indexing the rows from top to bottom or taking them in reverse order.

TIE testcase

MULTIPLE testcase

## Explanation

```
ṭ³Ṛœẹ”*¤ŒṬµ;Z;ŒD;ŒdŒrẎḢƇṀf5   Auxiliary monadic link, takes a pair of coordinates
ṭ                             Append the pair to
       ¤                      (
 ³                              The input
  Ṛ                             Reverse
   œẹ”*                         Find all coordinates of "*"
       ¤                      )
        ŒṬ                    Create a matrix with 1s at these coordinates and 0s everywhere else
          µ                   With this matrix:
           ;                  Join with
            Z                   the columns
             ;                Join with
              ŒD                diagonals
                ;             Join with
                 Œd             antidiagonals
                   Œr         Run-length encode each subarray into pairs of [item, length]
                     Ẏ        Shallow flatten
                       Ƈ      Find pairs where
                      Ḣ         the first item is truthy (and remove the item)
                        Ṁ     Maximum (by the length, since the item has been removed)
                         f5   Filter 5. This creates [5] (truthy) if the longest run has length exactly 5, and [] (falsy) otherwise.

Ṛœẹ”.ÇƇḢṚịØA,ɗ/ȯ”T   Main monadic link, takes a list of strings
Ṛ                    Reverse
 œẹ”.                Find all coordinates of "."
      Ƈ              Find those for which
     Ç                 the auxiliary link gives a truthy result
       Ḣ             First item, or 0 if the list is empty
        Ṛ            Reverse
              /      Fold under the following operation
             ɗ       (
         ị             Index the first item into
          ØA             the uppercase alphabet
            ,          Pair with the second item
             ɗ       )
               ȯ     Logical OR with
                ”T   "T"

```

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


title: Decode an URL string

text:
# Question
Title: Decode an URL string
### Challenge

I think everyone of us heard of URL encoding mechanism - it's basically everywhere.

Given an URLEncoded string on stdin, decode it, and output the decoded form to stdout.

The encoding is very simple, `+` or `%20` is representing space. Every percent followed by two hex digits (uppercase or lowercase) has to be replaced with ASCII character code of this number.

Related, but it's the other way round

### Example

```
100%25+working
=>
100% working

%24+%26+%3C+%3E+%3F+%3B+%23+%3A+%3D+%2C+%22+%27+%7E+%2B+%25
=>
$ & < > ? ; # : = , " ' ~ + %

%414243
=>
A4243

```

Test case that fails:

```
%24%XY+%%%
   ^~~~~~~
=>
$

```

### Rules

* Loopholes are forbidden.
* If your programming language has built-in function to decode the URL, using it *(the function)* is forbidden.
* Assume ASCII character set. No Unicode and all that stuff.
* This is a code-golf, so the answer with the fewest bytes used to accomplish the task wins.
* Please include a link to an online interpreter for your code.
* Your program has to decode until EOF or an error (eg. percent without valid hex digits - `%xy`) is spotted (you can safetly terminate).
* If anything is unclear, please let me know down in the comments.

# Answer
> 4 votes
# 05AB1E, ~~41~~ 30 bytes

```
'+ð:Δć©'%Qi2ôćuDHç©Ç`hÊiq}J}®?

```

-11 bytes thanks to *@Grimy*.

Try it online or verify all test cases.

**Explanation:**

```
'+ð:                  '# Replace all "+" in the (implicit) input with spaces
Δ                      # Loop until the result no longer changes:
 ć                     #  Extract head; pop and push remainder-string and first character
  ©                    #  Store the character in variable `®` (without popping)
   '%Qi               '#  If this character is a "%":
       2ô              #   Split the remainder-string into parts of size 2
                       #    i.e. "abcde" → ["ab","cd","e"]
         ć             #   Extract head again
          u            #   Convert it to uppercase
           D           #   Duplicate it
            H          #   Convert it from hexadecimal to integer
                       #   (NOTE: even if it isn't a valid hexadecimal string,
                       #    it will still result in an integer regardless)
             ç         #   And then from integer to ASCII-character with this codepoint
              ©        #   Replace variable `®` with this (without popping)
               Ç`h     #   Reverse process: ASCII-character → integer → hexadecimal string
                  Êi   #   If both are NOT equal (so it initially was invalid hexadecimal):
                    q  #    Stop the program
                   }J  #   And join the list of 2-char strings back together
      }®?              #  And then print `®` without newline

```

# Answer
> 4 votes
# JavaScript (V8), 112 bytes

```
u=>u.match(/([^%]|%[\da-f]{2})*/i)[0].replace(/%..|./g,d=>d=="+"?" ":d[1]?String.fromCharCode("0x"+d[1]+d[2]):d)

```

Try it online!

Noticed Arnauld's 92 byte Node.js answer shortly after spending some time golfing this. Porting that method would save quite a few bytes (with the main difference being `Buffer` vs. `String.fromCharCode`), but I wanted to post this one as it's more interesting and the V8 port wouldn't be worth a separate answer.

This challenge requires input validation, so the first `.match` takes only the valid part of the URL. Then, each part of it is `replace`d using a function. One trick I used that's kind of neat is the `"0x"+d[1]+d[2]`. Ordinarily you can convert hexadecimal to decimal using `+("0x"+n)`, but it seems `String.fromCharCode` casts to number on its own, saving three bytes. Instead of slicing the initial `%`, I just concatenate the second and third characters, which is shorter.

# Answer
> 3 votes
# Gema, 45 characters

```
+=
%<X2>=@int-char{@radix{16;10;$1}}
%=@fail

```

Insensitive on hexadecimal case.

Sample run:

```
bash-5.0$ gema '+= ;%<X2>=@int-char{@radix{16;10;$1}};%=@fail' <<< $'100%25+working\n%24+%26+%3C+%3E+%3F+%3B+%23+%3A+%3D+%2C+%22+%27+%7E+%2B+%25\n%414243\n%24+%XY+%%%'
100% working
$ & < > ? ; # : = , " ' ~ + %
A4243
$

```

Try it online!

# Answer
> 3 votes
# Perl 5 (`-0777p -Mre=/si`), 45 bytes

```
s/%.?[^\da-f].*//;y/+/ /;s/%(..)/chr hex$1/ge

```

TIO

# Answer
> 2 votes
# Python 3, 90 bytes

```
def d(s):t='%'!=s[0];print(end=t*s[0].replace('+',' ')or chr(int(s[1:3],16)));d(s[3-2*t:])

```

Try it online!

# Explanation

Checks if the first character is `%`. If that is the case, it will try to hex-decode the following two characters and print the result. If not, it will just print the first character and replaces `x` with  if necessary.

If the first character was `%`, the first three characters are sliced off the string and the function is called recursively. If not, only the first character is sliced off and the function is called again.

Raises an error if the hex string cannot be decoded or if end of line is reached.

# Answer
> 2 votes
# JavaScript (Node.js), 92 bytes

```
f=([x,y,z,...a])=>x=='%'?1/(n='0x'+y+z)?Buffer([n])+f(a):'':x?(x=='+'?' ':x)+f([y,z,...a]):a

```

Try it online!

# Answer
> 1 votes
# Jelly, 35 bytes

```
ṣ”+Kṣ”%µḊḢ;ḢƊ€ŒuØHiⱮⱮ’ḅ⁴⁸żFO<0œṗƊḢỌ

```

Try it online!

A monadic link that takes a string as its argument and returns the decoded string, terminating early at any invalid hex.

I’ve assumed for now that standard I/O rules apply. If it really has to be stdin, that will cost a byte.

# Answer
> 0 votes
# Perl 6, 62 bytes

```
{S:g{(<-[%]>*)\%?(..)?}={TR/+/ /}($0).print+print chr "0x"~$1}

```

Try it online!

Anonymous code block that outputs to STDOUT and then errors. This assumes that the input cannot contain spaces.

# Answer
> 0 votes
# Charcoal, 65 bytes

```
≔Ｅ¹⁶⍘ιφθＷθ«≔⮌⪪Ｓ%ι⊟ιＷ∧ι⊟ι«¿∧›Ｌκ¹⬤01№θ↧§κμ«℅⍘↧…κ²¦¹⁶✂κ²»«≔υι≔υθ»»Ｄ⎚

```

Try it online! Link is to verbose version of code. Note that Charcoal prompts "Enter input:" if it runs out of input. Explanation:

```
≔Ｅ¹⁶⍘ιφθ

```

Grab the list of hex digits into a variable.

```
Ｗθ«

```

Repeat while the variable is not empty. This is used as a flag to break out of the loop, since Charcoal has no other way of terminating the loop.

```
≔⮌⪪Ｓ%ι

```

Read the next line of text and split it on `%`s.

```
⊟ι

```

Output the first split.

```
Ｗ∧ι⊟ι«

```

Repeat while there are more splits to process, but stop if any of them are empty.

```
¿∧›Ｌκ¹⬤01№θ↧§κμ«

```

Also check that the length of the split is at least 2 and that the first 2 characters are hex digits. (Inconveniently I can't use a literal `2`, I have to use a string of length 2 instead.)

```
℅⍘↧…κ²¦¹⁶

```

Convert the first two characters from hex and output the character with that code.

```
✂κ²

```

Output the rest of that split.

```
»«≔υι≔υθ»»Ｄ⎚

```

Otherwise clear the loop variables so that we terminate processing. The canvas is also printed after each loop as otherwise Charcoal's input handling gets in the way again.

# Answer
> 0 votes
# Python 3, 91 bytes

```
lambda s:re.sub('%([A-Fa-f\d]{2})',lambda t:chr(int(t[1],16)),s.replace('+',' '))
import re

```

Try it online!

Approach this with regular expressions.

# Answer
> 0 votes
# Stax, 29 bytes

```
í☼∩ò☺µ◘Γπ╓l▄╓█₧ß:♦+ÇP¢Y╚↑░ºHÑ

```

Run and debug it

It's mostly regex.

---
Tags: code-golf, encoding
---