title: Wolves and Chickens

text:
# Question
Title: Wolves and Chickens
There's a river and there are wolves and chickens on one side of the river. They have a raft and they all need to get to the other side. However, the raft cannot travel on its own. The raft will sink if more than two animals are on it. None of the animals want to get wet because the river's cold and dirty. None of the animals can jump or fly over the river. Also, if there are chickens on one side, there cannot be more wolves on that side than there are chickens on that side -- the wolves will then decide to eat the chickens. This means that you cannot take two wolves on the raft to a side with one chicken.

Your task is to make a program/function that takes a number of wolves and a number of chickens (greater than or equal to the number of wolves) as input and finds the smallest number of times the raft has to move across the river. If the task is not possible, the program/function should output/return an empty string. It will then print/return one method as to how this is done in the following way:

```
W if a wolf crosses the river on its own
C if a chicken crosses the river on its own
CW if a chicken and a wolf cross the river -- WC is also fine
CC if two chickens cross the river
WW if two wolves cross the river

```

As you can deduce, the raft will automatically move in alternating directions (left and right, starting from left to right as the first one or two animals cross the river). This doesn't need to be outputted/returned. 'W', 'C', 'CW', 'CC' or 'WW' in the output may be separated by at least one of the following:

```
spaces (' ')
commas (',')
newlines

```

Alternatively, you may store the directions as items in a list (an empty list means no solution).

Test cases (output separated by commas -- input takes the form `wolves,chickens`):

```
1,1 -> CW

2,2 -> CW,C,CC,C,CW

1,2 -> CW,W,CW

0,10 -> CC,C,CC,C,CC,C,CC,C,CC,C,CC,C,CC,C,CC,C,CC

3,2 -> no solution

```

Try to make your code as short in bytes as possible.

# Answer
> 5 votes
# Perl, ~~179~~ ~~165~~ ~~164~~ ~~163~~ ~~157~~ 156 bytes

Includes +4 for `-p`

Give wolves followed by chickens on STDIN

```
river.pl <<< "2 3"

```

Outputs the boat contents per line. For this example it gives:

```
WC
C
CC
C
CC
W
WW

```

`river.pl`:

```
#!/usr/bin/perl -p
/ /;@F=w x$`.c x$'."\xaf\n";$a{$`x/\n/}++||grep(y/c//<y/w//&/c/,$_,~$_)or$\||=$' x/^\w*\n|(\w?)(.*)(c|w)(.+)\n(?{push@F,$1.$3.~"$`$2$4\xf5".uc"$'$1$3\n"})^/ for@F}{

```

Works as shown, but replace `\xhh` and `\n` by their literal versions to get the claimed score.

This will probably be beaten by a program that solves the general case (C\>W\>0)

```
* output `WC W WC C` until there is only one wolf left on the left bank (--w, --c)
* output `CC C` until there is only one chicken left on the left bank (--c)
* output `WC`

```

Add to that the trivial solutions for only wolves and only chickens and a hardcoded special case for `2 2` and `3 3` (`4 4` and higher have no solution). But that would be a boring program.

## Explanation

The current state of the field is stored as a single string consisting of:

* `w` for a wolf on the bank with the boat
* `c` for a chicken on the bank with the boat
* `\x88` (bit reversed `w`) for a wolf on the other bank
* `\x9c` (bit reversed `c`) for a chicken on the other bank
* A character indicating the side the boat is on `P` for the right bank, `\xaf` (bit reversed `P`) for the left bank (starting side)
* a newline `\n`
* all the moves that have been done upto now terminated with newlines, e.g. something like `WC\nW\nWC\nC\n` (notice the `W`s and `C` are in uppercase here)

The array `@F` will contain all reachable states. It is initialised by the starting string `wolves times "w", chickens times "c", \xaf \n`

The program then loops over `@F` which will get extended during the looping so new states get processed too. For every element it then does:

* Look at the string part left of the first `\n` which represents the current position of the animals and the boat. If that has been seen before skip `$a{$`x/\n/}++`
* Check if there are chickens together with more wolves on any side. Skip if so `grep(y/c//<y/w//&/c/,$_,~$_)`
* Check if the boat is the far side together with all animals. If so we have a solution. Store that in `$\` and keep that since the first solution found is the shortest `$\||=$' x/^\w*\n/`
* Otherwise try all ways of selecting 1 or 2 animals on the side with the boat. These are the `c` and `w` characters. (The animals at the other side won't match `\w`) `/(\w?)(.*)(c|w)(.+)\n(?{code})^/`. Then bit reverse the whole string before the `\n` except the animals that were selected for the boat `push@F,$1.$3.~"$`$2$4\xf5"`. Add the selected animals to the moves by uppercasing them: `uc"$'$1$3\n"`

The animal selection process effectively shuffles the string part representing them in many ways. So e.g. `wcwc` and `wwcc` can both get to represent 2 wolves and 2 chickens. The state check `$a{$`x/\n/}++` will unnessarily distinguish these two so many more states than necessary will be generated and checked. Therefore the program will run out of memory and time as soon as the number of different animals gets larger. This is mitigated only a bit by the fact that the current version will stop adding new states once a solution is found

# Answer
> 4 votes
## JavaScript (ES6), ~~251~~ ~~264~~ ... ~~244~~ 240 bytes

Takes the number of wolves and chickens `(w, c)` and returns one of the optimal solutions, or `undefined` if there's no solution.

```
(w,c,v={},B=1/0,S)=>(r=(s,w,c,W=0,C=0,d=1,N=0,k=w+'|'+c+d)=>v[k]|c*w>c*c|C*W>C*C|w<0|c<0|W<0|C<0?0:w|c?[v[k]=1,2,4,8,5].map(n=>r(s+'C'.repeat(b=n>>2)+'W'.repeat(a=n&3)+' ',w-d*a,c-d*b,W+d*a,C+d*b,-d,N+1))&(v[k]=0):N<B&&(B=N,S=s))('',w,c)||S

```

### Formatted and commented

Wrapper function:

```
(                                    // given:
  w,                                 // - w : # of wolves
  c,                                 // - c : # of chickens
  v = {},                            // - v : object keeping track of visited nodes
  B = 1 / 0,                         // - B : length of best solution
  S                                  // - S : best solution
) => (                               //
r = (...) => ...                     // process recursive calls (see below)
)('', w, c) || S                     // return the best solution

```

Main recursive function:

```
r = (                                // given:
  s,                                 // - s : current solution (as text)
  w, c,                              // - w/c : # of chickens/wolves on the left side
  W = 0, C = 0,                      // - W/C : # of chickens/wolves on the right side
  d = 1,                             // - d : direction (1:left to right, -1:right to left)
  N = 0,                             // - N : length of current solution
  k = w + '|' + c + d                // - k : key identifying the current node
) =>                                 //
v[k] |                               // abort if this node was already visited
c * w > c * c | C * W > C * C |      // or there are more wolves than chickens somewhere
w < 0 | c < 0 | W < 0 | C < 0 ?      // or we have created antimatter animals
  0                                  //
:                                    // else:
  w | c ?                            //   if there are still animals on the left side:
    [v[k] = 1, 2, 4, 8, 5].map(n =>  //     set node as visited and do a recursive call
      r(                             //     for each combination: W, WW, C, CC and CW
        s + 'C'.repeat(b = n >> 2) + //     append used combination to current solution
        'W'.repeat(a = n & 3) + ' ', //     wolves = bits 0-1 of n / chickens = bits 2-3
        w - d * a,                   //     update wolves on the left side
        c - d * b,                   //     update chickens on the left side
        W + d * a,                   //     update wolves on the right side
        C + d * b,                   //     update chickens on the right side
        -d,                          //     use opposite direction for the next turn
        N + 1                        //     increment length of current solution
      )                              //
    ) &                              //     once we're done,
    (v[k] = 0)                       //     set this node back to 'not visited'
  :                                  //   else:
    N < B &&                         //     save this solution if it's shorter than the
    (B = N, S = s)                   //     best solution encountered so far

```

### Test cases

```
let f =

(w,c,v={},B=1/0,S)=>(r=(s,w,c,W=0,C=0,d=1,N=0,k=w+'|'+c+d)=>v[k]|c*w>c*c|C*W>C*C|w<0|c<0|W<0|C<0?0:w|c?[v[k]=1,2,4,8,5].map(n=>r(s+'C'.repeat(b=n>>2)+'W'.repeat(a=n&3)+' ',w-d*a,c-d*b,W+d*a,C+d*b,-d,N+1))&(v[k]=0):N<B&&(B=N,S=s))('',w,c)||S

console.log(f(1, 1));
console.log(f(2, 2));
console.log(f(1, 2));
console.log(f(0, 10));
console.log(f(3, 2));
```

# Answer
> 2 votes
# CJam, 133

```
q~[0_]]_0+a:A;a{{28e3Zb2/{[YT2*(f*_Wf*]X..+:Bs'-&B2<{~_@<*},+{B2<T!+a:CA&{AC+:A;BY"WC".*a+}|}|}fY}fX]T!:T;__!\{0=:+!},e|:R!}g;R0=2>S*

```

Try it online

**Explanation:**

Basically the program does a BFS and remembers every state it reached in order to avoid infinite cycles. The working states are represented like \[\[Wl Cl\] \[Wr Cr\] M1 M2 … Mn\] where W = wolves, C = chickens, l = left side, r = right side, M = moves made so far (initially none), and the moves are like "C", "WC" or "WW" etc (practically more like \["" "C"\], \["W" "C"\], \["WW" ""\], but it's the same when printing). The remembered states are represented like \[\[Wl Cl\] \[Wr Cr\] S\] where S is the side with the boat (0=left, 1=right).

```
q~                 read and evaluate the input ([Wl Cl] array)
[0_]               push [0 0] as the initial [Wr Cr] array
]_                 wrap both in an array (initial working state) and duplicate it
0+a                append 0 (representing left side) and wrap in an array
:A;                store in A and pop; this is the array of remembered states
a                  wrap the working state in an array
{…}g               do … while
  {…}fX            for each working state X
    28e3Zb2/       convert 28000 to base 3 and group the digits into pairs
                    this generates [[1 1] [0 2] [1 0] [2 0] [0 1]]
                    which are all possible moves represented as [Wb Cb] (b=boat)
    {…}fY          for each "numeric move" pair Y
      […]          make an array of…
        YT2*(f*    Y negated if T=0 (T is the current boat side, initially 0)
        _Wf*       and the (arithmetic) negation of the previous pair
      X..+         add the 2 pairs to X, element by element
                    this performs the move by adding & subtracting the numbers
                    from the appropriate sides, determined by T
      :Bs          store the updated state in B, then convert to string
      '-&          intersect with "-" to see if there was any negative number
      B2<          also get just the animal counts from B (first 2 pairs)
      {…},         filter the 2 sides by checking…
        ~_@<*      if W>C>0 (it calculates (C<W)*C)
      +            concatenate the results from the negative test and eating test
      {…}|         if it comes up empty (valid state)…
        B2<        get the animal counts from B (first 2 pairs)
        T!+        append !T (opposite side)
        a:C        wrap in an array and store in C
        A&         intersect with A to see if we already reached that state
        {…}|       if not, then…
          AC+:A;   append C to A
          BY       push B and Y (updated state and numeric move)
          "WC".*   repeat "W" and "C" the corresponding numbers of times from Y
                    to generate the alphabetic move
          a+       wrap in array and append to B (adding the current move)
  ]                collect all the derived states in an array
  T!:T;            reverse the side with the boat
  __!              make 2 copies of the state array, and check if it's empty
  \{…},            filter another copy of it, checking for each state…
    0=:+!          if the left side adds up to 0
  e|:R             logical "or" the two and store the result in R
  !                (logically) negate R, using it as a do-while condition
                    the loop ends when there are no more working states
                    or there are states with the left side empty
;                  after the loop, pop the last state array
R0=2>S*            if the problem is solved, R has solution states,
                    and this extracts the moves from the first state
                    and joins them with space
                   if there's no solution, R=1
                    and this repeats a space 0 times, resulting in empty string

```

# Answer
> 0 votes
# Perl 6, 268 bytes

```
->*@a {(
[X](0 X..@a)[1..*-2]
.grep({![>](|$_,0)&![>](|(@a Z-$_),0)})
.combinations(2)
.combinations
.map(|*.permutations)
.map({.map(|*)»[*]})
.map({((|$_,(0,0)ZZ-@a,|$_)ZX*|(-1,1)xx*)»[*]})
.grep({.all.&{.all>=0&&3>.sum>0}})
.map({.map:{[~](<W C>Zx$_)}})
if [<=] @a
)[0]//()}

```

Generates increasingly longer chains of `(wolf count, chicken count)` states for the left bank, and returns the first one that matches all the rules.

Turns out this approach is neither efficient nor very concise, but at least it was fun to write.
I don't think I've never stacked the `Z` (zip) and `X` (cross) meta-operators before, like the `ZZ-` and `ZX*` here - kinda surprised that actually worked.

*(The newlines are just added for display purposes, and aren't part of the byte count.)*

# Answer
> 0 votes
# JavaScript (ES6), 227 ~~237~~

Basically it does a BFS and remembers every state it reached in order to avoid infinite cycles. ~~Unlike @aditsu's, I don't think there's any room for golfing~~

```
v=>g=>eval("o=[],s=[[v,g,0,k=[]]];for(i=0;y=s[i++];k[y]=k[y]||['WW','C','CC','W','CW'].map((u,j)=>(r=w-(j?j/3|0:2),q=c-j%3,d=g-q,e=v-r,r<0|q<0|!!q&r>q|!!d&e>d)||s.push([e,d,!z,[...p,u]])))o=([w,c,z,p]=y,y[3]=!z|c-g|w-v)?o:i=p")

```

*Less golfed*

```
(v,g) => {
  o = []; // output
  k = []; // hashtable to check states already seen
  s=[[v, g, 0, []]]; // states list: each element is wolves,chickens,side,path
  for(i = 0;
      y = s[i++]; // exit loop when there are no more states to expand
     )
  {
    [w, c, z, p] = x; // wolves on this side, chickens on this side, side, path
    if (z && c==g && w==v) // if all chicken and wolves on the other side
      o = p, // the current path is the output
      i = p  // this will force the loop to terminate
    y[3] = 0; // forget the path, now I can use y as the key to check state and avoid cycles
    if (! k[y]) // it's a new state
    {
       k[y] = 1; // remember it
       ['WW','C','CC','W','CW'].map( (u,j)=> (
          a = j ? j/3|0 : 2, // wolves to move
          b = j % 3, // chicken to move
          r = w - a, // new number of wolves on this side
          q = c - b, // new number of chickens on this side
          e = v - r, // new number of wolves on other side
          d = g - q, // new number of chickens on other side
          // check condition about the number of animals together
          // if ok, push a new state
          r<0 |q<0 | !!q&r>q | !!d&e>d ||
            s.push([e, d, !z, [...p,u])
       )
    }
  }
  return o
}

```

**Test**

```
F=
v=>g=>eval("o=[],s=[[v,g,0,k=[]]];for(i=0;y=s[i++];k[y]=k[y]||['WW','C','CC','W','CW'].map((u,j)=>(r=w-(j?j/3|0:2),q=c-j%3,d=g-q,e=v-r,r<0|q<0|!!q&r>q|!!d&e>d)||s.push([e,d,!z,[...p,u]])))o=([w,c,z,p]=y,y[3]=!z|c-g|w-v)?o:i=p")

function update() {
  var c=+C.value, w=+W.value
  O.textContent=F(w)(c)
}

update()
```

```
input { width: 4em }
```

```
Chickens <input id=C value=2 type=number min=0 oninput='update()'>
Wolves <input id=W value=2 type=number min=0 oninput='update()'>
<pre id=O></pre>
```

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


title: Detect if your program has been mutated

text:
# Question
Title: Detect if your program has been mutated
Write a program that terminates without an error.

If any single byte is substituted by any other byte the program should output

```
CORRUPTED

```
* Do not read your source code from a file
* Your program should not produce any other output

This is so the shortest answer in bytes wins.

**Edit:** removed "NOT CORRUPTED" requirement

# Answer
> 31 votes
# A Pear Tree, 76 bytes

```
$@='NOT ';print"$@CORRUPTED"__DATA__ =®®”print"$@CORRUPTED"__DATA__ =®®”Ê®›~

```

This program contains a few stray octets that aren't valid UTF-8. As such, it's shown as it looks in Windows-1252. (By default, if A Pear Tree sees a non-ASCII octet in a string literal or the like it treats it as an opaque object and doesn't try to understand it beyond being aware of what its character code is; this behaviour can be changed via an encoding declaration but the program doesn't have one. So the program is logically in "unspecified ASCII-compatible character set". All the non-ASCII octets are in comments anyway, so it doesn't really matter.)

## Explanation

A Pear Tree checksums the program, looking for the longest substring that has a CRC-32 of `00000000`. (If there's a tie, it picks the octetbetically first.) Then the program gets rotated to put it at the start. Finally, the program gets interpreted as a language that's almost a superset of Perl, defining a few things that are undefined in Perl to work the same way as in Python (and with a few minor changes, e.g. `print` prints a final newline in A Pear Tree but not in Perl). This mechanism (and the language as a whole) was designed for and problems; this isn't the former, but it's definitely the latter.

In this program, we have two notable substrings that CRC-32 to `00000000`; the entire program does, and so does `print"$@CORRUPTED"__DATA__ =®®` by itself (which appears twice). As such, if the program is uncorrupted, it'll set `$@` to `NOT`  and then print it followed by `CORRUPTED`. If the program is corrupted, then the CRC-32 of the program as a whole will fail to match, but one of the shorter sections will remain uncorrupted. Whichever one is rotated to the start of the program will just print `CORRUPTED`, as `$@` will be the null string.

Once the string's been printed, `__DATA__` is used to prevent the rest of the program running. (It crosses my mind writing this that `__END__` could be used instead, which would clearly save two bytes. But I may as well post this version now, because I've spent a bunch of time verifying it, and a modified version would have to be re-verified due to the CRC changes; and I haven't put a huge amount of effort into golfing the "payload" yet, so I want to see if anyone has other improvements in the comments that I can incorporate at the same time. Note that `#` doesn't work in the situation where a character is corrupted into a newline.)

You might be wondering how I managed to control the CRC-32 of my code in the first place. This is a fairly simple mathematical trick based on the way that CRC-32 is defined: you take the CRC-32 of the code, write it in little-endian order (the reverse of the byte order that's normally used by CRC-32 calculation programs), and XOR with `9D 0A D9 6D`. Then you append that to the program, and you'll have a program with a CRC-32 of 0. (As the simplest example possible, the null string has a CRC-32 of 0, thus `9D 0A D9 6D` also has a CRC-32 of 0.)

## Verification

A Pear Tree can handle most sorts of mutations, but I'm assuming "changed" means "replaced with an arbitrary octet". It's theoretically possible (although unlikely in a program this short) that there could be a hash collision somewhere that lead to the wrong program running, so I had to check via brute force that all possible octet substitutions would leave the program working correctly. Here's the verification script (written in Perl) that I used:

```
use 5.010;
use IPC::Run qw/run/;
use warnings;
use strict;
undef $/;
$| = 1;
my $program = <>;
for my $x (0 .. (length $program - 1)) {
    for my $a (0 .. 255) {
        print "$x $a    \r";
        my $p = $program;
        substr $p, $x, 1, chr $a;
        $p eq $program and next;
        alarm 4;
        run [$^X, '-M5.010', 'apeartree.pl'], '<', \$p, '>', \my $out, '2>', \my $err;
        if ($out ne "CORRUPTED\n") {
            print "Failed mutating $x to $a\n";
            print "Output: {{{\n$out}}}\n";
            print "Errors: {{{\n$err}}}\n";
            exit;
        }
    }
}

say "All OK!    ";

```

---
Tags: code-golf, radiation-hardening
---


title: Write an Incident tokeniser

text:
# Question
Title: Write an Incident tokeniser
## Background

Incident is a fairly unusual programming language, in that its list of tokens is not predetermined, but rather inferred from the input. As such, tokenising an Incident program can be fairly difficult, especially if you want to do so efficiently. This task is about doing that yourself.

## The task

Your program will be given a string as input. Here's the algorithm that Incident uses to tokenise it:

1. Identify all strings that occur as a substring of the input in exactly three ways (i.e. there are exactly three occurrences of that string within the input).
2. Discard any of these strings that are a substring of another such string (e.g. for input `ababab`, the only remaining string would be `ab`, not `a` or `b`, because `a` and `b` are both substrings of `ab`).
3. Discard any strings that overlap within the input. (For example, `aaaa` contains exactly three copies of `aa`, but these copies overlap at the second and third characters, so would be discarded. Likewise, in `abababa`, there are three copies of `ab` and three copies of `ba`, but the second to sixth characters are each at the overlap of an `ab` and a `ba`, so both `ab` and `ba` would be discarded).
4. Any strings that remain at this point are the tokens used by the program. Tokenise the original input into a sequence of these tokens (due to the discarding in the previous step, there will only be one way to do it). Any characters in the input that aren't part of any token are treated as comments and discarded.

Your program has to take a string as input, and return the corresponding tokenisation of the string (a list of tokens, each of which are expressed as strings) as output. Additionally, this has to be done at least moderately efficiently; specifically, the program has to run in **quadratic time** ("O(n²)") or better. (Incidentally, it's almost certainly possible to go faster than quadratic, but this is not , so feel free to use the tersest algorithm you can find that fits within the complexity bounds.)

## Clarifications

* Although Incident programs can in theory contain any of the 256 octets, it's acceptable for the purpose of this challenge for your program to handle only inputs formed out of printable ASCII (including space), plus newline and tab. (All known Incident programs restrict themselves to this subset). Note that space/newline/tab aren't special and can appear in the middle of tokens; Incident treats all 256 octets as opaque.
* The definition of "quadratic time" is "if the size of the input is doubled, the program will run slower by no more than a constant plus a factor of 4", i.e. if *t*(*x*) is the maximum time your program takes to process an input of size *x*, then there must be some constant *k* such that *t*(2 *x*) \< 4 *t*(*x*) + *k* for all *x*. Bear in mind that comparing strings takes time proportional to the length of the strings.
* Your program should theoretically be able to handle input programs of any length if run in a (possibly hypothetical) variant of your language that has unlimited memory and uses unbounded integers (it's OK if the program fails to achieve this goal when run in practice due to the language's integers or memory actually being finitely large). You may assume (for the purpose of calculating the complexity) that integers that are no greater than the length of the input can be compared in constant time (although bear in mind that if you use larger values, e.g. due to converting the input into a single integer, they will take a length of time to compare proportional to the number of digits they have).
* You can use any algorithm that fits within the complexity bounds, even if it doesn't follow the same steps as the algorithm posted above, so long as it produces the same results.
* This puzzle is about tokenising the input, not really about formatting the output. If the most natural way to output a list in your language involves an ambiguous format (e.g. newline-separated when the strings contain literal newlines, or without delimiters between the strings), don't worry about the fact that the output ends up ambiguous (so long as the list is actually constructed). You may want to make a second version of your submission that produces unambiguous output, to aid in testing, but the original version is the version that counts for the scoring.

## Test case

For the following input string:

```
aaabcbcbcdefdfefedghijghighjkllkklmmmmonono-nonppqpq-pqprsrsrstststuvuvu

```

your program should produce the following output list:

```
a a a bc bc bc d e f d f e f e d gh gh gh k l l k k l pq pq pq u u u

```

## Victory condition

This is , so the shortest valid (i.e. correct input/output behaviour and sufficiently fast to execute) program, measured in bytes, wins.

# Answer
> 14 votes
# C (gcc), 324 bytes

The function `f` takes a null-terminated string and prints the tokens to stdout. All newlines can be removed from the code below.

```
f(char*s){
int n=strlen(s),b=0,z[n-~n],F[n+1],u,a,x=0,l,m,*t=z+n;
int K(i){~m&&s[i]^s[a+m]?m=t[m],K(i):++m;}
for(;b<2*n;){
for(a=b++%n,m=l=-1;a+l<n;K(a+l))t[++l]=m;
for(l=0;l<n;++F[m])K(l++),F[l]=z[a]*=b>n?m^z[a]||~(m=t[z[l-m]]):0;
for(printf("%.*s",z[a],s+a);n/b*l&&a+l>x;l--)F[l]^3?F[t[l]]+=F[l]:(a<x?z[u]=0:(z[u=a]=l),x=a+l);
}
}

```

This older 376-byte version is a little easier to read; the explanation below applies to it.

```
*t,m;
char*p;
K(c){for(;~m&&c^p[m];)m=t[m];++m;}
k(i){for(*t=m=-1;p[i];t[++i]=m)K(p[i]);m=0;}
f(char*s){
int n=strlen(s),z[n-~n],F[n+1],u,*Z=z,a=0,x=0,l;
for(t=z+n;a<n;a++){
p=s+a;
for(k(l=z[a]=0);l<n;++F[m])K(s[l++]),F[l]=0;
for(;l&&a+l>x;l--)F[l]^3?F[t[l]]+=F[l]:(a<x?z[u]=0:(z[u=a]=l),x=a+l);
}
for(p=s;*p;printf("%.*s",*Z++,p++))
for(k(x=0);x<n;m==*Z?*Z*=!!z[x-m],m=t[m]:0)
K(s[x++]);
}

```

`k(0)` generates the table `t` for pattern `p` for the Knuth–Morris–Pratt algorithm. `K(c)` process the next character `c` of the search string and updates `m`, the length of the largest prefix of `p` which can be found ending at the most recently processed character.

In the first `for` loop, for each index `a` in the string, we count the number of times each possible value of `m` occurs when searching in the entire string for the substring beginning at `a`. Then we look for the largest `l` such that the length-`l` substring starting at `a` occurred exactly 3 times. If it's short enough to be entirely contained by a string found for a previous `a`, we ignore it. If it overlaps, we delete the previous string from `z`, the array recording which tokens will be kept. Otherwise, its length is stored in `z`.

Then, we use KMP again to search the string for the tokens recorded in `z`. If one of them is found at a location with a 0 entry in `z`, we know that this token was deleted due to overlap. If the token was not deleted, it is printed.

# Answer
> 7 votes
## JavaScript, ~~878~~ ~~867~~ ~~842~~ ~~825~~ ~~775~~ ~~752~~ ~~717~~ ~~712~~ ~~704~~ ~~673~~ ~~664~~ ~~650~~ 641 bytes

Thanks to @Kritixi Lithos for helping golf the code
Thanks to @User2428118 for golfing off 14 bytes

(Will not work in IE7) (Newlines should be entered as "`\n`" and tab as "`\t`" in the input string, any unicode characters should be entered as `\u####`)

```
w=>{for(a=[],b=[],c=[],d=[],f=[],e=[],k=0;k<(g=w.length);a[k++]=h)for(b[R='push']([]),h=[d[k]=f[k]=j=i=0];i++<g-k;){while(j&&w[k+i]!=w[k+j])j=h[j-1];w[k+i]==w[k+j]&&j++,h[R](j)}for(k=0;k<g;k++)for(j=i=0;i<g;i++)if(w[i]!=w[k+j]){while(j&&w[i]!=w[k+j])j=a[k][j-1];w[i]==w[k+j]?i--:b[k][R](j)}else b[k][R](++j);for(k=0;k<g;c[k++]=l){for(h=f.map(Q=>i=l=0);i<g;)h[b[k][i++]]++;for(;i;)h[i]==3?(l=i,i=0):a[k][--i]?h[a[k][i]]+=h[i+1]:0}for(k=0;g>k++;)for(i=0;(S=c[k])&&i<g;)b[k][i++]==S?d[i-S]=S:0;for(k=0;k<g;k++)for(e[R](w.slice(k,(S=d[k])+k)),i=1;i<S;)f[k+i]=1,f[k]|=S<d[k+i]+i++;f.map((X,i)=>(P=e[i],X?e=e.map(Y=>P==Y?"":Y):0));return e.join``}

```

Try it Online

## Explanation of how it works and ungolfed code

First, the program generates Knuth Morris Pratt arrays for every possible substring;

```
for(index=0;index<word.length;index++){
  kmpArray=[0];
  j=0;
  for(i=1;i<word.length-index;i++){
    while(j&&word.charAt(index+i)!=word.charAt(index+j)){
      j=kmpArray[j-1];
    }
    if(word.charAt(index+i)==word.charAt(index+j)){
      j++;
    }
    kmpArray.push(j);
  }
  kmpArrays.push(kmpArray);
}

```

Next, the program finds the maximum matching lengths at every single index in the word with each substring. (this is O(n^2) time)

```
for(index=0;index<word.length;index++){
  j=0;
  matchLength=[];
  for(i=0;i<word.length;i++){
    if(word.charAt(i)!=word.charAt(index+j)){
      while(j&&word.charAt(i)!=word.charAt(index+j)){
        j=kmpArrays[index][j-1];
      }
      if(word.charAt(i)==word.charAt(index+j)){
        i--;
      }else{
        matchLength.push(j);
      }
    }else{
      j++;
      matchLength.push(j);
      if(j==kmpArrays[index].length){
        j=kmpArrays[index][j-1];
      }
    }
  }
  matchLengths.push(matchLength);
}

```

The program uses this data to find the longest substrings that appear three times for each starting character in the string.

```
for(index=0;index<word.length;index++){
  counts=[]
  max=0;
  for(i=0;i<=word.length;i++){
    counts.push(0);
  }
  for(i=0;i<word.length;i++){
    counts[matchLengths[index][i]]++;
  }
  for(i=word.length-1;i>0;i--){
    if(counts[i]==3){
      max=i;
      break;
    }
    if(kmpArrays[index][i-1]){ //if this value has a smaller value it could be as well
      counts[kmpArrays[index][i]]+=counts[i-1];
    }
  }
  maxLengths.push(max);
}

```

The program uses this data to eliminate all substrings that do not appear exactly three times and all substrings of the longest valid substrings.

```
for(index=0;index<word.length;index++){
  if(!maxLengths[index])
    continue;
  for(i=0;i<word.length;i++){
    if(matchLengths[index][i]==maxLengths[index]){
      tokens[i-maxLengths[index]+1]=maxLengths[index];
    }
  }
}

```

Next, the program sets all overlapping or partial substrings as to be removed.

```
for(index=0;index<word.length;index++){
  sStrs.push(word.substring(index,tokens[index]+index));
  for(i=1;i<tokens[index];i++){
    toRemove[index+i]=1;
    if(tokens[index]<tokens[index+i]+i){
      toRemove[index]=1;
    }
  }
}

```

For each of the to be removed values, all equivalent substrings are removed as well.

```
for(index=0;index<word.length;index++){
  if(toRemove[index]){
    removal=sStrs[index];
    for(i=0;i<3;i++){
      indxOf=sStrs.indexOf(removal);
      sStrs[indxOf]="";
      toRemove[indxOf]=0;
    }
  }
}

```

Finally, the program joins the array of substrings together and outputs it.

---
Tags: code-golf, string, parsing, restricted-complexity
---


title: Match coordinates with their values

text:
# Question
Title: Match coordinates with their values
Given 3 input items, a list of coordinate pairs, a 2D string, and a single-character string, output whether the character at each coordinate of the 2D string is equal to the single character. You can take the input in any order and the coordinates may be 1-indexed.

You may take the 2D string as a 2D list, a list of lines, or a 2D string.

Example: `(0,0), "#_\n__", "#" -> True`

The string is

```
#_
__

```

The char at the coordinate `(0,0)` (from the top left) is `#`. This is equal to the third input item, `#`, so you output `True` (or any truthy value)

Example: `[(0,0), (1,1)], "#_\n_#", "#" -> True`

The string is

```
#_
_#

```

The characters at the coordinates of `(0,0)` and `(1,1)` are both `#`, so the output is true.

The output is only true iff every coordinate matches a hash. Not every hash has to have a matching coordinate though. If there are no occurrences of the single char (`#` in some of the test cases) in the 2D string, the output is still just falsy.

You can assume the coordinates will always be within the bounds of the 2D string.

More test cases: (I put the single char second for ease of readability)

```
[(0,0), (2,1), (3,0)], #

#_##
#_##

True

[(0,0), (1,1), (3,0)], #

#_##
#_##

False (1,1 is not a hash)

[(1,1)], a

#a##
#a##

True

[(4, 0), (3, 0), (2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 2), (3, 2), (4, 2), (4, 3)], ' '

 ####
 #
   #

True

```

Note the last test case uses spaces as the single char string, and hashes around the spaces.

Related. (inverse of this challenge)

# Answer
> 1 votes
# Dyalog APL, 8 bytes

Prompts for list of coordinate pairs (row,column), then 2D array, then character.

```
∧/⎕=⎕[⎕]

```

`[⎕]` prompt for coordinates and use them to scatter pick from

prompted input (2D array)

`=` compare the selected elements to

input (the character)

`∧/` check if all are true (AND-reduction)

**Test cases** (`⎕IO←0` to match examples, but this is not necessary):

First example

Second example

Third example

Fourth example

Fifth example

# Answer
> 6 votes
# Python, 39 bytes

Takes the inputs:

1. `a` list of `(x, y)` integer coordinates
2. `b` list of strings
3. `c` single character string

---

```
lambda a,b,c:{b[y][x]for x,y in a}=={c}

```

# Answer
> 4 votes
# Octave, ~~45~~ ~~38~~ 29 bytes

```
@(A,B,C)A(1+B*[rows(A);1])==C

```

A function that takes a 2D array of chars as `A` and coordinates(0 based) `B` as a two column matrix of `[col row]` and the matching character as `C`. The two element coordinates(using matrix multiplication) converted to linear index.

Note: Previous answer that made use of sparse matrix was wrong.

Other Contributors:

Stewie Griffin for saving 5 bytes noting that \[0 1 0\] can be regarded as false value!!

Luis Mendo for saving 2 bytes that `~0 == true` and notification about sparse matrix.

Try it Online

# Answer
> 4 votes
# JavaScript (ES6), 37 bytes

Takes the inputs:

1. `a` array of `[x, y]` integer coordinates
2. `s` array of strings
3. `c` single character string

---

```
(a,s,c)=>a.every(([x,y])=>s[y][x]==c)

```

# Answer
> 3 votes
# Mathematica, 28 bytes

```
#3~Extract~#~MatchQ~{#2...}&

```

1-indexed. Due to how arrays are structured in Mathematica, the input coordinates must be reversed (i.e. `(row, column)`)

**Usage**

```
#3~Extract~#~MatchQ~{#2...}&[{{1, 1}, {2, 3}, {1, 4}}, "#", {{"#", "_", "#", "#"}, {"#", "_", "#", "#"}}]

```

> `True`

# Answer
> 2 votes
# Perl 6, ~~41~~ 40 bytes

~~```
->\c,\h,\n{all map {n eq h[.[0];.[1]]},c}

```~~
```
->$_,\h,\n{all .map:{n eq h[.[0];.[1]]}}

```

Expects the 2D string as a 2D list.

*Thanks to b2gills for -1 byte.*

# Answer
> 2 votes
## Haskell, 27 bytes

```
s!c=all(\(x,y)->s!!y!!x==c)

```

Usage example: `( ["#_##","#_##"] ! '#' ) [(0,0), (2,1), (3,0)]` -\> `True`.

# Answer
> 2 votes
## C#, ~~80~~ 77 bytes

Saved 3 bytes, thanks to pinkfloydx33

```
a=>b=>c=>{foreach(var i in a){if(b[i[0]][i[1]]!=c){return 1<0;}}return 1>0;};

```

a is the pairs of coordinate, b is the list of lines, and c is the single-character string.

# Answer
> 2 votes
# Jelly, 10 bytes

```
ịṪ⁸ịḢð€Q⁼⁵

```

This only works as a full program. Input order is indices, string array, singleton string.

Try it online!

### How it works

```
ịṪ⁸ịḢð€Q⁼⁵  Main link.
            Left argument:  P (array of coordinate pairs)
            Right argument: S (array of strings)
            Third argument: C (singleton string)

     ð€     Combine the links to the left into a dyadic chain and call it with each
            p = (x, y) in P as left argument and S as the right one.
ị             Unindex; retrieve the strings of S at indices x and y.
 Ṫ            Tail; yield s, the string of S at index y.
  ⁸ị          Unindex; retrieve the characters of s at indices x and y.
    Ḣ         Head; yield the character of s at index x.
       Q    Unique; deduplicate the resulting string/array of characters.
        ⁼⁵  Compare the result with the third argument.

```

# Answer
> 1 votes
# Haskell, ~~72~~ 63 bytes

```
c [] _ _ =1<2;c ((f,s):t) m n |n/=lines m!!s!!f=1>2|1>0=c t m n

```

Input of `c [(0,0), (1,0), (3,0)] "#_##\n#_##" '#'` Outputs `False`

Input `c [(4, 0), (3, 0), (2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 2), (3, 2), (4, 2), (4, 3)] " \n ####\n # \n # " ' '`

Output `True`

UnGolfed

```
checkfunc :: [(Int,Int)] -> String -> Char -> Bool
checkfunc [] _ _ = True
checkfunc (x:xs) string char | char /= ((lines string)!!(snd x))!!(fst x)= False  -- Checks first coordinates and returns False if no match
                             | otherwise = checkfunc xs string char --Otherwise iterate over remaining coordinate pairs

```

# Answer
> 1 votes
# Scala, 68 bytes

```
def f(l:(Int,Int)*)(s:String*)(c:Char)=l forall{x=>s(x._2)(x._1)==c}

```

# Answer
> 1 votes
## Clojure, 39 bytes

```
#(apply = %3(map(fn[[x y]]((%2 y)x))%))

```

Example (string input is a vec of vec of characters):

```
(def f #(apply = %3(map(fn[[x y]]((%2 y)x))%)))
(f [[0 0] [1 1] [3 0]] (mapv vec ["#_##" "#_##"]) \#)

```

---
Tags: code-golf, ascii-art, grid, maze
---


title: Hidden Inversions (Robbers' Thread)

text:
# Question
Title: Hidden Inversions (Robbers' Thread)
This is a puzzle, the cops' thread can be found here.

Your task will be to find an anagram of the provided programs in the cops' thread that performs its left inverse.

Once you crack an answer post the solution as an answer below and notify the original answerer.

You will be scored on the number of programs you are the first to crack.

# Answer
> 21 votes
## Python 3, 46 bytes, Lynn

```
lambda x0223334566789:(x0223334566789*89)//178

```

# Answer
> 15 votes
## Python 2, 225 bytes, orlp

```
p=90930641353124136621573325641513715557077985927835294018496194596645372722158;q=101979812089012306249375934082966806799688507587087308196267706260111970225882#--223444799
lambda n:pow(n,pow(65537,(p*q-2*(p+q))/4,p*q),~p*~q)

```

Guess I got lucky after guessing random prime divisors all day...

 (Default c4.8xlarge spot limit is 4, but I managed to bump it to 10 last year. Had to tweak the FAAS config from 16 slaves to 6 though (+3 mpi, 1 master). 20m polyselect, 12h 50m sieving, 2h 25m linalg, 30m sqrt. Total cost ~$70. At least @orlp was nice enough to pick a solvable size, but I'm not doing this again! Thanks to @IlmariKaronen for the last step, and yes I'm joking about the guessing :P)

# Answer
> 11 votes
# Python 2, 83 bytes, orlp

**Original:**

```
#((()))****+,,---/2289;==oppppppqqqqqw~~
lambda n:pow(n,65537,10998167423251438693)

```

**Crack:**

```
p=3207399658;q=3428998126#--11
lambda n:pow(n,pow(65537,(p*q-2*(p+q))/4,p*q),~p*~q)

```

Try it online!

RSA cracking done by Wolfram Alpha. ;)

# Answer
> 7 votes
## Python 3, 80 bytes, Wolfram

```
from bisect import*
q=int(input())
print(bisect([(h+1)**2 for h in range(q)],q))

```

This was really hard to crack! I use the bisect library, which is included in the Python 3 distribution. The `bisect` function takes a sorted list and an element, and returns the rightmost index where the element could be inserted to maintain order. We just give it the length-`q` list of squares starting from `1` and the element `q`.

# Answer
> 6 votes
# Javascript, 21 bytes, Arnauld

**Original**

```
b=>Math.pow(b,torc=3)

```

**Crack**

```
o=>Math.cbrt(o,pbw=3)

```

Returns the cube root.

# Answer
> 5 votes
## 7, 9 bytes, ais523

```
00000000: 0173 dc25 7e13 dcb6 1f                   .s.%~....

```

Because brute force always wins, and 9! is only 362880

# Answer
> 4 votes
# Processing.js, 59 bytes, Kritixi Lithos

**Original:**

```
float igetuwebaoli(int p){return p*(((17*-4*-3)))+0+0;}//,,

```

**Crack:**

```
int loabewuteg(float p,i){return (i+0**+0,(p/17/(-4*-3)));}

```

Well, that was easy enough. The hardest part was figuring out where to stick the extra commas and asterisks. Fortunately, it seems that Processing allows extra unused function parameters as well as C-style comma expressions.

# Answer
> 4 votes
# JavaScript (ES6), 63 bytes, SLuck49

**Original:**

```
x=>eval(atob`eCp4KzEvLyAgfXBModLS4TvEn4wp1iys9YRRKC85KLIhNMC=`)

```

**Crack:**

```
x=>eval(atob`CgpNYXRoLnBvdyh4LTEsMC41KSAvLw4589CEIKKMRefipyz=`)

```

The base64 code above decodes to:

```

Math.pow(x-1,0.5) //...

```

where the `...` stands for a bunch of random garbage that is ignored by the JS interpreter, since it's in a comment.

I found this solution by trial and error. In the end, the only really tricky part were the two newlines at the beginning of the code, needed to make the rest line up properly and to get the `M` in `Math` to base64-encode into something that was available in the original character set. I first tried spaces, but `" M"` base64-encodes into `"ICBN"` and I needed the only available `B` to encode `".po"` later in the code. `"0+M"`, `"1*M"`, `"1?M"` or any other similar no-op prefixes I could think of didn't work either, but newlines did.

I suspect this may not be exactly the intended solution, but whatever — it works. :)

**Demo:**

```
var f = x=>eval(atob`eCp4KzEvLyAgfXBModLS4TvEn4wp1iys9YRRKC85KLIhNMC=`)
var g = x=>eval(atob`CgpNYXRoLnBvdyh4LTEsMC41KSAvLw4589CEIKKMRefipyz=`)
for (var i = -0; i <= 10; i++) console.log(i, '->', f(i), '->', g(f(i)))
```

# Answer
> 3 votes
# Brain-Flak, 26 bytes, Wheat Wizard

### Original (adds 13)

```
((((()()())){}[()]){}{}{})

```

### Crack (subtracts 13)

```
([(((()())()){}){}{}](){})

```

# Answer
> 3 votes
# J, 8 bytes, miles

```
[:]-:[+:

```

Simple swapping of `+:` for `-:` (double for halve).

# Answer
> 3 votes
# Javascript, 15 bytes, insertusernamehere

**Original**

```
t=>(!!0+~~t+~0)

```

**Crack**

```
t=>(~~!!~0+t+0)

```

# Answer
> 3 votes
# Python 2, 47 bytes, Wheat Wizard

```
lambda x:sorted(a**2for a in range(x)).index(x)

```

# Answer
> 3 votes
# JavaScript (ES6), 46 bytes, SLuck49

**Original (calculates ln(x+1))**

```
x=>Math.log(x+(+String(t=985921996597669)[5]))

```

**Crack**

```
x=>Math[(lg=19979699+55686).toString(9+25)](x)

```

I never would have cracked this if I hadn't realized that the inverse is a `Math` built-in. `(lg=19979699+55686).toString(9+25)` is just a convoluted way of returning `"expm1"`.

# Answer
> 2 votes
## J, 10 bytes, miles

```
1%:@*~>:[<

```

I have to write something here because the answer is too short.

# Answer
> 2 votes
# J, 29 bytes, Zgarb

## Original

```
5#.[:,(3 5&#:(-$]-)7)#.inv"0]

```

## Crack

```
[:(](07-5)"3 #.-:&#$,)5#.inv]

```

Try it online!

Another crack equivalent is

```
[:((3 ]7-5)#.-:&#$,)5#.inv"0]

```

## Explanation

```
[:(](07-5)"3 #.-:&#$,)5#.inv]  Input: integer n
                            ]  Get n
                      5        The constant 5
                       #.inv   Get the digits of n in base 5
[:(                  )         Operate on those digits D
                    ,            Flatten D (does nothing since it is already a list)
                  #              Get the length of D
               -:&               Halve it
                   $             Reshape D to half its length (only the base 2 digits)
    (07-5)"3                     The constant 2 with rank 3
             #.                  Convert the front-half of D to a decimal from base 2
   ]                             Return the right result

```

---
Tags: permutations, source-layout, cops-and-robbers
---


title: Longest Cycle in a Graph

text:
# Question
Title: Longest Cycle in a Graph
Given a directed graph, output the longest cycle.

## Rules

* Any reasonable input format is allowed (e.g. list of edges, connectivity matrix).
* The labels are not important, so you may impose any restrictions on the labels that you need and/or desire, so long as they do not contain additional information not given in the input (e.g. you can't require that the nodes in cycles are labeled with integers, and other nodes are labeled with alphabetic strings).
* A cycle is a sequence of nodes that are all connected, and no node is repeated, other than the node that is the start and end of the cycle (`[1, 2, 3, 1]` is a cycle, but `[1, 2, 3, 2, 1]` is not).
* If the graph is acyclic, the longest cycle has length 0, and thus should yield an empty output (e.g. empty list, no output at all).
* Repeating the first node at the end of the list of nodes in the cycle is optional (`[1, 2, 3, 1]` and `[1, 2, 3]` denote the same cycle).
* If there are multiple cycles of the same length, any one or all of them may be output.
* Builtins are allowed, but if your solution uses one, you are encouraged to include an alternate solution that does not use trivializing builtins (e.g. a builtin that outputs all cycles). However, the alternate solution will not count towards your score at all, so it is entirely optional.

## Test Cases

In these test cases, input is given as a list of edges (where the first element is the source node and the second element is the destination node), and the output is a list of nodes without repetition of the first/last node.

```
[(0, 0), (0, 1)] -> [0]
[(0, 1), (1, 2)] -> []
[(0, 1), (1, 0)] -> [0, 1]
[(0, 1), (1, 2), (1, 3), (2, 4), (4, 5), (5, 1)] -> [1, 2, 4, 5]
[(0, 1), (0, 2), (1, 3), (2, 4), (3, 0), (4, 6), (6, 8), (8, 0)] -> [0, 2, 4, 6, 8]
[(0, 0), (0, 8), (0, 2), (0, 3), (0, 9), (1, 0), (1, 1), (1, 6), (1, 7), (1, 8), (1, 9), (2, 1), (2, 3), (2, 4), (2, 5), (3, 8), (3, 1), (3, 6), (3, 7), (4, 1), (4, 3), (4, 4), (4, 5), (4, 6), (4, 8), (5, 0), (5, 8), (5, 4), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 9), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 8), (7, 9), (8, 0), (8, 1), (8, 2), (8, 5), (8, 9), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6)] -> [0, 9, 6, 7, 8, 2, 5, 4, 3, 1]
[(0, 0), (0, 2), (0, 4), (0, 5), (0, 7), (0, 9), (0, 11), (1, 2), (1, 4), (1, 5), (1, 8), (1, 9), (1, 10), (2, 0), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (3, 0), (3, 1), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 11), (4, 1), (4, 3), (4, 7), (4, 8), (4, 9), (4, 10), (4, 11), (5, 0), (5, 4), (5, 6), (5, 7), (5, 8), (5, 11), (6, 0), (6, 8), (6, 10), (6, 3), (6, 9), (7, 8), (7, 9), (7, 2), (7, 4), (7, 5), (8, 8), (8, 9), (8, 2), (8, 4), (8, 7), (9, 0), (9, 1), (9, 2), (9, 3), (9, 6), (9, 10), (9, 11), (10, 8), (10, 3), (10, 5), (10, 6), (11, 2), (11, 4), (11, 5), (11, 9), (11, 10), (11, 11)] -> [0, 11, 10, 6, 9, 3, 8, 7, 5, 4, 1, 2]

```

# Answer
> 4 votes
## Mathematica, 80 58 bytes

*Saved a whopping 22 bytes thanks to JungHwan Min*

```
(FindCycle[#,∞,All]/.{}->{Cases[#,v_v_]})[[-1,;;,1]]&

```

is the three byte private use character `U+F3D5` representing `\[DirectedEdge]`. Pure function with first argument `#` expected to be a list of directed edges. Finds `All` cycles of length at most `Infinity` in `Graph@#`, then replaces the empty list with the list of self-loops. Cycles are represented as lists of edges and sorted by length, so we take the last such cycle, then from all of its edges we take the first argument so that we get a list of vertices in the specified output format.

If only Mathematica treated loops as a cycle of length `1` (`AcyclicGraphQ @ CycleGraph[1, DirectedEdges -> True]` gives `True`, seriously), then we could save another `26` bytes:

```
FindCycle[#,∞,All][[-1,;;,1]]&

```

# Answer
> 3 votes
# Haskell, ~~157 154~~ 150 bytes

```
import Data.List
g#l=nub[last$(e:d):[d|p==last q||e`elem`init d]|d@(p:q)<-l,[e,f]<-g,p==f]
h g=snd$maximum$((,)=<<length)<$>[]:until((==)=<<(g#))(g#)g

```

Try it online!

Thanks @Laikoni and @Zgrab for saving a bunch of bytes!

This is a very inefficient program:

The first function `#` takes a list of paths `l` (a list of lists of numbers) and tries to extend the elements of `l` by prepending every possible edge (a list of length 2) of `g` to each element of `l`. This happens only if the element of `l` isn't already a cycle *and* if the new node that would be prepended is not already contained in the element of `l`. If it is already a cycle, we do not prepend anything but add it again to the new list of paths, if we can extend it, we add the extended path to the new list, otherwise we don't add it to the new list.

Now the function `h` repeatedly tries to extend those paths (starting with the list of edges itself) until we reach a fixed point, i.e. we cannot extend any path any further. At this point we only have cycles in our list. Then it is just a matter of picking the longest cycle. Obviously the cycles appear multiple times in this list since every possible cyclic rotation of a cycle is again a cycle.

# Answer
> 2 votes
# JavaScript (ES6), ~~173~~ ~~163~~ ~~156~~ ~~145~~ 139 bytes

*Saved 5 bytes thanks to @Neil*

```
f=(a,m,b=[])=>a.map(z=>!([x,y]=z,m&&x-m.slice(-1))&&b.length in(c=(n=m||[x],q=n.indexOf(y))?~q?b:f(a.filter(q=>q!=z),[...n,y]):n)?b=c:0)&&b

```

### Test snippet

```
f=(a,m,b=[])=>a.map(z=>!([x,y]=z,m&&x-m.slice(-1))&&b.length in(c=(n=m||[x],q=n.indexOf(y))?~q?b:f(a.filter(q=>q!=z),[...n,y]):n)?b=c:0)&&b

g=a=>console.log("Input:",JSON.stringify(a),"Output:",JSON.stringify(f(a)))

g([[0,0]])
g([[0,1],[1,2]])
g([[0,1],[1,0]])
g([[0,1],[1,2],[2,0]])
g([[0,1],[1,2],[1,3],[2,4],[4,5],[5,1]])
g([[0,1],[0,2],[1,3],[2,4],[3,0],[4,6],[6,8],[8,0]])
```

# Answer
> 2 votes
# Pyth, 20 bytes

```
eMefqhMT.>{eMT1s.pMy

```

Test suite

Takes a list of edges, like in the examples.

Explanation:

```
eMefqhMT.>{eMT1s.pMy
eMefqhMT.>{eMT1s.pMyQ    Variable introduction
                   yQ    Take all subsets of the input, ordered by length
                .pM      Reorder the subsets in all possible ways
               s         Flatten
                         (This should be a built in, I'm going to make it one.)
   f                     Filter on (This tests that we've found a cycle)
    qhMT                 The list of first elements of edges equals
           eMT           The last elements
         .>   1          Rotated right by 1
        {                Deduplicated (ensures no repeats, which would not be a
                         simple cycle)
  e                      Take the last element, which will be the longest one.
eM                       Take the last element of each edge, output.

```

# Answer
> 2 votes
# Bash + bsdutils, 129 bytes

```
sed 's/^\(.*\) \1$/x \1 \1 x/'|sort|(tsort -l>&-)|&tr c\\n '
 '|sed 's/x //g'|awk 'm<NF{m=NF;gsub(/[^0-9 ] ?/,"");print}'|tail -1

```

tsort does all the heavy lifting, but its output format is rather unique and it doesn't detect cycles of length 1. Note that this doesn't work with GNU tsort.

### Verification

```
--- t1 ---
0
--- t2 ---
--- t3 ---
0 1
--- t4 ---
1 2 4 5
--- t5 ---
0 2 4 6 8
--- t6 ---
0 2 1 6 3 7 4 8 9 5
--- t7 ---
0 11 10 3 1 2 4 7 5 8 9 6

```

# Answer
> 2 votes
# Haskell, ~~109~~ 108 bytes

```
import Data.List
f g=last$[]:[b|n<-[1..length g],e:c<-mapM(\_->g)[1..n],b<-[snd<$>e:c],b==nub(fst<$>c++[e])]

```

A brute force solution: generate all lists of edges of increasing lengths until the length of the input, keep those that are cycles, return the last one. Takes the graph in the format `[(1,2),(2,3),(2,4),(4,1)]`. Try it online!

## Explanation

```
f g=                    -- Define function f on input g as
  last$                 -- the last element of the following list
  []:                   -- (or [], if the list is empty):
  [b|                   --  lists of vertices b where
   n<-[1..length g],    --  n is between 1 and length of input,
   e:c<-                --  list of edges with head e and tail c is drawn from
    mapM(\_->g)[1..n],  --  all possible ways of choosing n edges from g,
   b<-[snd<$>e:c],      --  b is the list of second elements in e:c,
   b==                  --  and b equals
    nub(fst<$>c++[e])]  --  the de-duplicated list of first elements
                        --  in the cyclic shift of e:c.

```

# Answer
> 0 votes
# MATLAB, ~~291~~ 260 bytes

Takes an adjecency matrix `A` where an edge `(i,j)` is denoted by a `1` in `A(i,j)`, and `A` is zero in all other entries. The output is a list of a longest cycle. The list is empty if there is no cycle at all, and the list includes start and endpoint if there is a cycle. It uses `1`-based indexing.

This solution does not use any built-in functions related to graphs.

```
function c=f(A);N=size(A,1);E=eye(N);c=[];for j=1:N;l=g(j);if numel(l)>numel(c);c=l;end;end;function p=g(p)if ~any(find(p(2:end)==p(1)))e=E(p(end),:)Q=find(e*A)k=[];for q=Q;if ~ismember(q,p(2:end))n=g([p,q]);if numel(n)>numel(k);k=n;end;end;end;p=k;end;end;end

```

Unfortunately this does not run in TryItOnline as it uses a function within a function, which is recursive. A little bit of modification allows you to try it on octave-online.net.

For the very last test case I found an alternative longest cycle `[0 2 1 4 3 5 7 8 9 11 10 6 0]` (this notation uses 0-based indexing)

### Explanation

The basic approach here is that we perform a BFS from every node and take care that we do not visit any of the intermediate nodes again except the start node. With that idea we can collect all possible cycles, and easily pick the longest one.

```
function c=f(A);
N=size(A,1);
E=eye(N);
c=[]; % current longest cycle
for j=1:N;                                      % iterate over all nodes
    l=getLongestCycle(j);                       % search the longest cycle through the current node
    if numel(l)>numel(c);                       % if we find a longer cycle, update our current longest cycle
        c=l;
    end;

end;

    function p=getLongestCycle(p);              % get longest cycle from p(1) using recursion
        if ~any(find(p(2:end)==p(1)));          % if we just found a cycle, return the cycle do nothing else, OTHERWISE:
            e=E(p(end),:);                      % from the last node, compute all outgoing edges
            Q=find(e*A);
            k=[];
            for q=Q;                            % iterate over all outogoin edges
                if ~ismember(q,p(2:end));       % if we haven't already visited this edge,
                    n=getLongestCycle([p,q]);   % recursively search from the end node of this edge
                    if numel(n)>numel(k);       % if this results in a longer cycle, update our current longest cycle
                        k=n;
                    end;
                end;
            end;
            p=k;
        end;
    end;
end

```

---
Tags: code-golf, graph-theory
---


title: Hidden Inversions (Cops' Thread)

text:
# Question
Title: Hidden Inversions (Cops' Thread)
This is a puzzle the robbers' thread can be found here.

Your task will be two write two programs (or functions) such that they are anagrams of each other and one performs the left inverse of the other. These programs may accept and output as many *integers* or complex numbers as you wish. If you choose take numbers as character points or any other reasonable means you must indicate you are doing so in your answer. If you choose to restrict the domain of your function you must also indicate the restricted domain in your answer.

You will then present the first program in the form of an answer with left inverse hidden for robbers to find.

The shown program must implement a injective function (otherwise it would be impossible for a hidden answer to exist).

If your answer has not been cracked in one week you may reveal the hidden answer and mark it as **safe**. Safe answers cannot be cracked by robbers and will remain un-cracked indefinitely.

The goal will be to create the shortest un-cracked answer in bytes.

### Example

You could show the following python program that adds one to the input

```
lambda x:~-x

```

A solution could be:

```
lambda x:-~x

```

This subtracts one from the input

# Answer
> 12 votes
## Python 3, 80 bytes (Cracked)

```
bhmq = int(input())
print(bhmq ** 2)
(1 or [(sqrt),(specification+of*integerr)])

```

Domain: positive integers. Function is just squaring of a number. Input to stdin, output to stdout, as well as in the inverse function. Note that Python ignores the third line here, because it is syntactically valid and 1 is already a truthy value, so Python doesn't even look whether the right part of 'or' is well-defined.

Robbers should write a sqrt function that will work correct on all non-zero squares, printing integer value as is, without floating point (so on input '4' output should be '2' or '2\n', not '2.0' or '2.0\n').

# Answer
> 11 votes
# Python 3, 46 bytes, cracked

```
lambda x:x*(1999888577766665//844333333222200)

```

Doubles the input.

# Answer
> 11 votes
# , 9 bytes, Cracked

This program's full of nonprintable characters, so here's a hexdump:

```
00000000: 2573 dc01 7e13 dcb6 1f                   %s..~....

```

Note: this uses a numeric input routine that's incapable of inputting negative numbers, so this submission is restricted to nonnegative integers only.

One problem with challenges is that you don't write explanations of the code (to make it harder to crack). On the other hand, this means that I don't have to go to to the trouble here.

I picked 7 as the language because, especially in its compressed notation, it's pretty hard to read, and I don't see why it should be only *me* who has to go to the trouble of moving around 8-bit chunks of programs written in a 3-bit encoding. Good luck!

## Explanation

Now that the program's been cracked (by brute force, unfortunately; that's always a danger in these short solutions), I may as well explain what I was getting at. This was actually fairly solvable by reading the program; I could have made it much more difficult, but that felt like a bad idea when brute-force cracks exist.

We'll start by representing the program in a more natural encoding. As usual, bolded numbers indicate commands that run immediately (not all of which are representable in a program; **`6`** and **`7`** are but **`2`** to **`5`** aren't), unbolded numbers represent their escaped equivalents (`0` to `5`, all of which are representable in the original program; note that `0` is an escaped **`6`** and `1` is an escaped **`7`**):

```
112**7**1**7**34002**77**023**67**13303

```

The set of commands available in a 7 program source mean that it's basically just a literal that represents the original stack (there's nothing else you can do with just escaped commands, **`6`** and **`7`**). So the first thing a program will do is push a bunch of stuff onto the stack. Here's how the stack looks after the program's run (`|` separates stack elements, as usual in 7):

```
**772**|**7**|**34662**|023|**73363**

```

The final stack element then gets copied to become the code to run (while remaining on the stack). As it happens, this is the only part of the program that's code; everything else is just data. Here's what it translates to:

```
**73363**
**7**      Push an empty element onto the stack
 **3**     Output the top stack element, discard the element below
**73**     Combined effect of these: discard the top stack element
  **3**    Output the top stack element, discard the element below
   **6**   Escape the top stack element, then append it to the element below
    **3**  Output the top stack element, discard the element below

```

In other words, this is mostly just a bunch of I/O instructions. Let's analyse this in detail:

* **`73`** discards the **`73363`** that's still on top of the stack.
* **`3`** outputs the `023`, and discards the **`34662`**. It can thus be seen that the **`34662`** is a comment, which was used to store the bytes needed in the other version of the program. As for what `023` does when output, it selects I/O format 0 (integers), then `23` is a directive which requests the implementation to input an integer (in 7, you do input via outputting specific codes that request input). The input is done by making copies of the stack element below, e.g. if the input integer is 10, the next stack element (currently **`7`**) will become **`7777777777`**. Thus, we're accepting input from the user in decimal, but it's being stored as unary.
* **`6`** escapes the top stack element (changing each instance of **`7`** to `1`; this is how strings consisting entirely of **`7`**s are escaped), then appends it to the stack element before (**`772`**). So our data is now something like `**772**1111111111`.
* Finally, **`3`** outputs the stack element in question (and pops a blank stack element that's part of the default initial stack). Its value is calculated by taking the number of `1`s and **`7`**s, and subtracting the number of `0`s and **`6`**s. (The **`2`** in the middle is ignored in most cases; if it's at the end of the string, it'll become a trailing newline instead of being ignored, but PPCG rules don't care about that.) Thus, the output is the original input plus 2.

At this point, there's nothing useful on the stack and nothing in the program, so the program exits.

How do we reverse this? It's a simple matter of changing the `11` to `00`, so that we're prepending characters to the input that make it 2 lower, rather than 2 higher. There's a `00` conveniently hidden eight octal digits further on in the program (so that octal digits and bytes line up with each other), so we can simply swap it with the `11` at the start.

# Answer
> 7 votes
## JavaScript (ES6), 21 bytes, Cracked

This is an easy one.

```
b=>Math.pow(b,torc=3)

```

Returns the cube of the input.

# Answer
> 6 votes
# Python 2, 83 bytes, cracked

```
#((()))****+,,---/2289;==oppppppqqqqqw~~
lambda n:pow(n,65537,10998167423251438693)

```

This is similar to my other answer. However, this uses 64-bit RSA, and is cryptographically quite weak. If you can rob this answer, you can theoretically rob my other one as well, given enough time.

# Answer
> 5 votes
# JavaScript (ES6), 46 bytes, Cracked

```
x=>Math.log(x+(+String(t=985921996597669)[5]))

```

This function returns `ln(x+1)` where `x` is a non-negative number.

### Usage

```
(x=>Math.log(x+(+String(t=985921996597669)[5])))(5)

```

**Note:** Due to the nature of floating point numbers `f(g(x))` may not exactly equal `x`. Example: `f(g(4))=3.9999999999999996`

# Answer
> 5 votes
# Python 2, 47 bytes, Cracked

```
lambda x:x**2or (iron() and saxifrage.extend())

```

The domain for this function is {x ∈ ℤ | x \> 0}. It squares its input.

---

nmjcman101 found the intended solution:

> `lambda x:sorted(a**2for a in range(x)).index(x)`

# Answer
> 4 votes
# J, 8 bytes, cracked

Another simple one to start off with.

```
[:]+:[-:

```

Doubles the input.

# Answer
> 4 votes
# Processing.js, 59 bytes, Cracked!

```
float igetuwebaoli(int p){return p*(((17*-4*-3)))+0+0;}//,,

```

This function multiplies the input by `204` (`17*-4*-3=204`). It takes in an int as input and outputs a float. As expected, the inverse divides the input by `204`.

An online interpreter for processing-js can be found here.

# Answer
> 4 votes
# Processing (java), 59 bytes, SAFE

```
float igetuwebaoli(int p){return p*(((17*-4*-3)))+0+0;}//,,

```

This function multiplies the input by `204` (`17*-4*-3=204`). It takes in an int as input and outputs a float. As expected, the inverse divides the input by `204`. Note: both programs take an int as input and output a float.

This answer is exactly the same as my other answer, except that my other answer was written in Processing.js. Meet Processing-java, the less verbose cousin of Java. You can download Processing here at processing.org.

### The Crack

```
float ap(int i){return i*pow(blue(get(0,0)),-1);}//++7*4*-3

```

This program divides the argument by `204`. But how? Let's go inside the function.

```
i *                              //multiply i by
         blue( get(0, 0) )       //this (evaluates to 204)
    pow(                  , -1)  //raises to the -1 power (ie its reciprocal)

```

Simple enough, but how does `blue( get(0, 0) )` become `204`? This is the centrepiece of this submission. First of all, `get(0,0)` gets the colour of the pixel located at `(0,0)` (the top left corner of the window, which always opens in a Processing sketch). Next, `blue()` gets the blue value of that pixel, which is `204`!

To come up with this submission, I experimented by printing the different attributes of the colour obtained by `get(0,0)`. I have found out that the red, green, blue, alpha values are `204`, `204`, `204` and `255` respectively. From this, I decided to do a simple operation with this number and ended up with this post.

# Answer
> 4 votes
# J, 10 bytes, cracked

```
1%~<:[@*>:

```

Another simple one. Returns *n*2-1.

# Answer
> 4 votes
# JavaScript (ES6), 15 bytes, cracked by Emigna

```
t=>(!!0+~~t+~0)

```

> This functions returns `n-1`.

---

You can test it like:

```
(t=>(!!0+~~t+~0))(6)

```

---

**Cracked**

My intended solution is a bit different than Emigna's crack:

> `t=>t+(+!!~~~00)`

# Answer
> 4 votes
# , 29 bytes (Cracked by miles)

```
5#.[:,(3 5&#:(-$]-)7)#.inv"0]

```

This is a verb that takes a **positive integer** as input, and does the following:

1. Convert to bases 2 and 4.
2. Pad the base-4 representation with 0s to have the same length as the base-2 representation.
3. Concatenate the two representations (base-2 first).
4. Interpret the concatenation as a base-5 representation and convert to integer.

Try it online!

## My solution

The logic is pretty much the same as in the crack. The rank conjunction `"` can be stuck in many different places (and I use it to get rid of the unnecessary `0` and `3`), since it doesn't really do anything in the solution.

```
(7-5)#.[:(]-:&#$,)5#.inv"0 3]

```

# Answer
> 3 votes
# Brain-Flak, 26 bytes, Cracked

## Original

```
((((()()())){}[()]){}{}{})

```

## My Crack

> `([(((()())){}()){}{}()]{})`

## 1000000000's Crack

> `([(((()())()){}){}{}](){})`

# Answer
> 3 votes
# JavaScript (ES6), 63 bytes Cracked by Ilmari Karonen

```
x=>eval(atob`eCp4KzEvLyAgfXBModLS4TvEn4wp1iys9YRRKC85KLIhNMC=`)

```

Time for some `atob` nonesense. This function returns `x*x+1` where `x` is a non-negative number.

### Usage

```
(x=>eval(atob`eCp4KzEvLyAgfXBModLS4TvEn4wp1iys9YRRKC85KLIhNMC=`))(5)

```

### Intended

> `x=>eval(atob`Lyp5fMRwICAgKi9NYXRoLnBvdyh4LTEsMC41KS8veCp4KzE=`)`

There's a large number of potential solutions, but I was hoping that the leading characters would throw off the byte order enough to make this harder. C'est la `atob`

# Answer
> 2 votes
# Python 2, 225 bytes, cracked by Sp3000

```
#((()))****+,,---/000555666888;==oppppppqqqqqw~~
lambda n:pow(n,65537,9273089718324971160906816222280219512637222672577602579509954532420895497077475973192045191331307498433055746131266769952623190481881511473086869829441397)

```

Domain of this function is \[0, n), where n is the huge number above. Yes, this function is invertible on this domain. And unless I messed up, breaking this answer is as hard as breaking 512 bit RSA.

# Answer
> 0 votes
# J, 15 bytes

```
(".&,'10.')#.#:

```

Takes a non-negative integer *n*, converts it to a list of binary digits, and combines those digits as a base 10 number.

Try it online!

---
Tags: permutations, source-layout, cops-and-robbers
---


title: Sort characters by darkness

text:
# Question
Title: Sort characters by darkness
Your program must take as input a line of characters, like this:

```
@+.0

```

And output the characters sorted by how dark they are, like this:

```
.+0@

```

Requirements:

* You must use a monospaced font for darkness detection.
* You must find out how many pixels each character takes up. You must actually draw the character and count pixels, i.e. you can't just hardcode pixel amounts.

+ As a more concrete rule: if you switched fonts, your program should still work. Furthermore, your program should be able to switch fonts by simply changing a variable or value or string in the code.
* If you use antialiasing, you must count pixels as percentages of a fully black pixel. For example, an `rgb(32, 32, 32)` pixel will count as 1/8 of a full pixel. Disregard this rule if your characters are not antialiased.
* After counting pixels, you must sort the characters by the amount of pixels, and output them in order.
* This is , so the shortest code in bytes will win.

# Answer
## Mathematica, 112 110 108 bytes

This can still likely be golfed further. Assumes the string is in variable s.

And now uses a correct syntax to sort one list by another list.
Lucky test cases -\> "Oh yeah, that works" -\> *Facepalm*
Thanks for the sharp eyes, David Carraher.

**Update:** Replaced OCR A with Menlo because I realized that on OSX the OCR A font family name is actually OCR A Std. So I was sorting a default font instead of the real deal. Menlo is also monospaced with the same byte count, so no net gain or loss.

I've put up a hosted CDF export of the notebook, so you can see the code in action if you wish. I'm still figuring out how to add some interactivity to web-hosted CDFs, so for now it's just static.

```
c=Characters@s;Last/@Sort[Transpose@{Total[1-#&/@ImageData@Rasterize@Style[#,FontFamily->"Menlo"],3]&/@c,c}]

```

Output for `s = FromCharacterCode /@ Range[33, 135];` with "Courier"

Output for same, but with FontFamily "Monospace":

Note that the final results are shown in MM's internal font, not in the font being sorted. Hence, you see the differences in the font chosen reflected in the sort. The CDF link shows both, though, for the completists.

Ungolfed code:

```
s = FromCharacterCode /@ Range[33, 135];
c = Characters@s;
Last /@ Sort[
    Transpose@{Total[1 - # & /@
        ImageData@Rasterize@Style[#, FontFamily -> "Menlo"], 3] & /@ c, c}]

```
> 22 votes

# Answer
# Bash + ImageMagick: ~~164~~ ~~147~~ 148 characters

```
while read -n1 c
do
o=`convert -size 20x15 xc: +antialias -font cour.ttf -draw "text 0,10 '$c'" xpm:-`
o=${o//[^ ]}
a[${#o}]+=$c
done
echo "${a[@]}"

```

Sample run:

```
bash-4.1$ echo -n '@+.0' | bash graysort.sh
. + 0 @

```

Separators are inserted between grayness groups. Characters with identical grayness level are not separated:

```
bash-4.1$ echo -n 'abcdefghijklmnopqrstuvwxyz' | bash graysort.sh
i cl jortz esv ax u df bgnpq y hk w m

```
> 26 votes

# Answer
## QBasic, 259 bytes

```
SCREEN 1
DIM a(255)
FOR i = 32 TO 255
    CLS
    PRINT CHR$(i);
    FOR p = 0 TO 64
        a(i) = a(i) + POINT(p MOD 8, p \ 8)
    NEXT p
NEXT i
FOR p = 0 TO 96
    FOR i = 32 TO 255
        IF a(i) = p THEN PRINT CHR$(i);
    NEXT i
NEXT p

```

I did this for fun, so it's technically non-compliant to the rules in one way. It doesn't take a list of characters, but instead prints all characters from 32-255 and uses that instead. If you really want to see a version which complies with this rule, please tell me.

It also fails another technicality: "Furthermore, your program should be able to switch fonts by simply changing a variable or value or string in the code." There is no easy way to do this from within QBasic. However, the program will of course work fine with any codepage of your choosing.

Lastly, I could squeeze away a few characters (mostly whitespace that the QBasic IDE helpfully inserts,) but it's probably not worth it since this answer stands no chance of winning anyway.
> 10 votes

# Answer
# Javascript + Canvas and Browser DOM (280 237 235 bytes)

*Updated version with suggetions from Fors and toothbrush in comments:*

```
function m(x){a=document.createElement('canvas').getContext('2d');a.font='9px Monaco';a.fillText(x,y=i=0,20);for(;i<3600;)y+=a.getImageData(0,0,30,30).data[i++];return y}alert(s.split('').sort(function(a,b){return m(a)-m(b)}).join(''))

```

More readable version:

```
// Scoring function - Calculates darkness for single character
function m(x) {
    a = document.createElement('canvas').getContext('2d');
    a.font = '9px Monaco';
    a.fillText(x, y = i = 0, 20);
    for (; i < 3600;) y += a.getImageData(0, 0, 30, 30).data[i++];
    return y
}
// Assume input is in variable s and alert as output. Comparison function now expression.
alert(s.split('').sort(function (a, b) {
    return m(a) - m(b)
}).join(''))

```

Can maybe be golfed more.

I'm new to this site, so I am unsure how input is normally read for Javascript answers. I assume input is contained in a variable named `s`. If this is not OK, I will update the answer and the char count.

JSFiddle of updated version.

JSFiddle of first version.
> 9 votes

# Answer
# PHP, 298 characters

I've added a few line breaks so you can see it in all its hideousness:

```
<?php
$s=@$_GET[s];$a=array();$v=imagecreate(16,16);$f='imagecolorallocate';
$f($v,0,0,0);for($i=0;$i<strlen($s);$i++){$c=$f($v,$i,0,1);
imagechar($v,5,2,$n=0,$s[$i],$c);for($y=16;$y--;)
for($x=16;$x--;)$n+=($c==imagecolorat($v,$x,$y));
$a[]=ord($s[$i])+($n<<8);}sort($a);foreach($a as $v)echo chr($v);

```

This code uses the GD fonts that come built-in with PHP. The second argument of `imagechar()` selects the font (numbers from 1 to 5 are valid).

**Example:**

```
Input:  !@#$%^&*-=WEIX,./'
Output: '-.,^=!/*IE%X#$&@W

```

If you insert the following on top of the code shown above, then you'll be able to supply the list of characters in your web browser.

```
<?php
define("FONT_SIZE",5);
if(@$_SERVER['PATH_INFO']=='/a.png') {
  $s = $_GET['s'];
  $im = imagecreate(strlen($s)*(FONT_SIZE+4)+4,FONT_SIZE+12);
  imagecolorallocate($im,255,255,128);
  $c = imagecolorallocate($im,0,0,0);
  imagestring($im,FONT_SIZE,2,0,$s,$c);
  header("Content-Type: image/png");
  imagepng($im);
  imagedestroy($im);
  exit();
}
$me = $_SERVER['PHP_SELF'];
$t1 = $img = "";
if ($t1=htmlspecialchars(@$_GET['s'])) {
  $t2=urlencode($_GET['s']);
  $img="<p><img src=\"$me/a.png?s=$t2\" /></p>";
}
echo <<<END_HTML
<html>
<body>
$img
<form action="$me" method="get">
<input type="text" name="s" size="40" value="$t1" />
<input type="submit" value="Go" />
</form>
END_HTML;
if(!isset($_GET['s'])) exit();
?>

```
> 3 votes

# Answer
## Java - ~~468 450~~ 444

```
public static void main(String[]a){class c implements Comparable<c>{char d;c(char e){d=e;}public int compareTo(c o){return e(d)>e(o.d)?1:-1;}int e(char f){int a=0,x,y;BufferedImage img=new BufferedImage(99,99,1);img.getGraphics().drawString(""+f,9,80);for(y=0;y<99;y++)for(x=0;x<99;x++)a+=img.getRGB(x,y);return a;}}c[]s=new c[a[0].length()];int i=0;for(char d:a[0].toCharArray())s[i++]=new c(d);Arrays.sort(s);for(c d:s)System.out.print(d.d);}

```

`@+.0abcdefghijklmnopqrstuvwxyz` -\> `.irl+jcvtfxyzsuonkheaqpdb0wgm@`

Ungolfed:

```
    public static void main(String[] a) {
    a = new String[]{"@+.0abcdefghijklmnopqrstuvwxyz"};
    class c implements Comparable<c> {
        char    d;

        c(char e) {
            d = e;
        }

        @Override
        public int compareTo(c o) {
            return e(d) > e(o.d)? 1 : -1;
        }

        int e(char f) {
            int a = 0, x, y;
            BufferedImage img = new BufferedImage(99, 99, 1);
            img.getGraphics().drawString("" + f, 9, 80);
            for (y = 0; y < 99; y++)
                for (x = 0; x < 99; x++)
                    a += img.getRGB(x, y);
            return a;
        }
    }
    c[] s = new c[a[0].length()];
    int i = 0;
    for (char d : a[0].toCharArray())
        s[i++] = new c(d);
    Arrays.sort(s);
    for (c d : s)
        System.out.print(d.d);
}

```
> 3 votes

# Answer
## GTB

This has code to be the second hardest code I've ever written for a calculator. No hard-coded pixel values, it actually draws the text on a graph and loops to count each pixel.

```
0→I`_%I<l?_T;1,1,s;_,I,1
C;pT;{0,1,2,3,4,5},{0,1,2}→L1(I
0→I%I<l?_T;1,C;L1(I)>L1,I

```

**Input**

```
,O.i

```

**Output**

```
.,iO

```
> 3 votes

# Answer
## Postscript, 381

Here's something completely different, just for fun. As most fonts are vector anyway, 'counting pixels' is a little odd, isn't it. Calculating glyph shape area, while being correct way, is not that easy. An alternative can be scanning a rectangle and counting 'hits' when a point is inside a glyph shape, and Postscript has operators for this kind of checks. Though, true, scanning and insideness-testing is just a weird way of counting pixels.

```
(%stdin)(r)file token pop/Courier 99 selectfont[1 index length{0}repeat]0 1 99{0 1 99{0 1 5 index length 1 sub{newpath 9 19 moveto 3 copy 7 index exch 1 getinterval false charpath infill{3 index exch 2 copy get 1 add put}{pop}ifelse}for pop}for pop}for 0 1 99 dup mul{0 1 3 index length 1 sub{dup 3 index exch get 2 index eq{3 index exch 1 getinterval print}{pop}ifelse}for pop}for

```

.

```
(%stdin) (r) file token pop
/Courier 99 selectfont
%/DejaVuSansMono 99 selectfont
%/UbuntuMono-Regular 99 selectfont
[ 1 index length {0} repeat ]   % str []
0 1 99 {
    0 1 99 {
        0 1 5 index length 1 sub {
            newpath
            9 19 moveto
            3 copy              % str [] n m i n m i
            7 index exch        % str [] n m i n m str i
            1 getinterval       % str [] n m i n m s
            false charpath      % str [] n m i n m
            infill              % str [] n m i bool
            {3 index exch 2 copy get 1 add put} {pop} ifelse
        } for
        pop
    } for
    pop
} for
% un-comment next line to print number of 'hits' for each glyph
%
% dup {=} forall
%
% next is 'lazy sort'
0 1 99 dup mul {                % str [] i
    0 1 3 index length 1 sub {  % str [] i j
        dup 3 index exch        % str [] i j [] j
        get 2 index eq          % str [] i j bool
        {3 index exch 1 getinterval print} {pop} ifelse
    } for
    pop
} for
()=

```

And here are results for 3 different fonts (selection of which can be un-commented, above):

```
$ echo '(.-?@AByz01)' | gs -q -dBATCH d.ps
.-?1z0yA@B
$ echo '(.-?@AByz01)' | gs -q -dBATCH d.ps
.-?z1yA0B@
$ echo '(.-?@AByz01)' | gs -q -dBATCH d.ps
.-?1zyA0B@

```
> 3 votes

# Answer
# Perl (with GD) (159)

```
use GD;sub i{$i=new GD'Image 5,8;$B=colorExact$i 9,9,9;colorExact$i 0,0,0;char$i gdTinyFont,0,0,@_,1;$_=unpack"B*",wbmp$i 0;y/0//c}print+sort{i($a)-i($b)}@ARGV

```

usage:

```
> perl dark.pl 1 2 3 @ # . , : ~ $ M i I s S
.,~:i13Is2S$M@#

```

edit: shortened to 159 chars
> 2 votes

# Answer
# Java, 584

Wow... This was not a good language to do this in.

```
import java.awt.geom.*;import java.util.*;class F{static void n(final String f,List<Character> s){Collections.sort(s,new Comparator<Character>(){public int compare(Character a,Character b){return d(f,""+a) - d(f,""+b);}});}static int d(String f,String s){int i=0;PathIterator p=new java.awt.Font(f,0,12).createGlyphVector(((java.awt.Graphics2D)new java.awt.image.BufferedImage(8,8,2).getGraphics()).getFontRenderContext(),s).getGlyphOutline(0).getPathIterator(AffineTransform.getRotateInstance(0.0, 0.0));while(!p.isDone()){i+=p.currentSegment(new double[99])/2;p.next();}return i;}}

```

Usage:

```
import java.awt.geom.*;
import java.util.*;
public class F {
    public static void main(String[]args){
        List<Character> s = new ArrayList<Character>(0);
        s.add('@');
        s.add('+');
        s.add('.');
        s.add('0');
        n("Calibri", s);
        System.out.println(s);
    }
    static void n(final String f,List<Character> s){
        Collections.sort(s,new Comparator<Character>(){
            public int compare(Character a,Character b){
                return d(f,""+a) - d(f,""+b);
            }
        });
    }

    static int d(String f,String s){
        int i=0;
        PathIterator p=new java.awt.Font(f,0,12).createGlyphVector(((java.awt.Graphics2D)new java.awt.image.BufferedImage(8,8,2).getGraphics()).getFontRenderContext(),s).getGlyphOutline(0).getPathIterator(AffineTransform.getRotateInstance(0.0, 0.0));
        while(!p.isDone()){
            i+=p.currentSegment(new double[99])/2;
            p.next();
        }
        return i;
    }
}

```

This setup results in:

```
[., +, 0, @]

```

---

The only line here that needs explanation:

```
PathIterator p=new java.awt.Font(f,0,12).createGlyphVector(((java.awt.Graphics2D)new java.awt.image.BufferedImage(8,8,2).getGraphics()).getFontRenderContext(),s).getGlyphOutline(0).getPathIterator(AffineTransform.getRotateInstance(0.0, 0.0));

```
* Initialize the 12pt font object with the passed font.
* Create a new BufferedImage obejct to create a Graphics2D object linked to a GraphicsContext.
* Get the font rendering context of the 2D graphics context for the string s.
* Get the first glyph (only glyph) in the string.
* Get the path iterator (list of points).

Then this final piece brings it together...

```
while(!p.isDone()){
    i+=p.currentSegment(new double[99])/2;
    p.next();
}

```

By iterating through all points and summing count of points. This density information is passed back up to the comparator and is used for sorting.
> 2 votes

# Answer
### R, 195 characters

```
A=strsplit(scan(,""),"")[[1]];cat(A[order(sapply(A,function(x){png('a',a='none',fa='monospace');frame();text(0,0,x);dev.off();sum(apply(png::readPNG('a'),c(1,2),function(x)any(x!=1)))}))],sep="")

```

Indented with comments:

```
A=strsplit(scan(,""),"")[[1]] #Take characters as strings and split into single chars
cat(A[order(sapply(A,function(x){ #Apply the following function to each char and order accordingly
                 png('a',a='none',fa='monospace'); #Open empty png without antialiasing and with monospace font
                 frame(); #create empty plot
                 text(0,0,x); #add the char as text to the plot
                 dev.off(); #close png device
                 sum(apply(png::readPNG('a'), #read it back as rbga 3d matrix
                           c(1,2), #check every layer (R, G, B, A)
                           function(x)any(x!=1))) #if any are not 1, send TRUE
                 }))], #Sum all TRUEs
    sep="") #Prints to output

```

Example:

```
> A=strsplit(scan(,""),"")[[1]];cat(A[order(sapply(A,function(x){png('a',a='none',fa='monospace');frame();text(0,0,x);dev.off();sum(apply(png::readPNG('a'),c(1,2),function(x)any(x!=1)))}))],sep="")
1: @+.0
2:
Read 1 item
.+0@
> A=strsplit(scan(,""),"")[[1]];cat(A[order(sapply(A,function(x){png('a',a='none',fa='monospace');frame();text(0,0,x);dev.off();sum(apply(png::readPNG('a'),c(1,2),function(x)any(x!=1)))}))],sep="")
1: 1234567890
2:
Read 1 item
1723450689

```

The gestion of fonts in R plots being platform-dependent, I cannot guarantee that it works on PC, but it does on a Mac (OS X 10.7.5, R 2.14.2).
> 1 votes

# Answer
# SmileBASIC, ~~179~~ ~~176~~ 173 bytes

```
INPUT S$DIM Q$[0],A[0],Z[0]WHILE""<S$C$=POP(S$)GCLS
PUSH Q$,C$
GPUTCHR.,0,C$
GSAVE.,0,8,8,A,0S=0FOR I=0TO 63S=S+A[I]NEXT
PUSH Z,S
WEND
RSORT Z,Q$
WHILE LEN(Q$)?POP(Q$);
WEND

```

Uses the currently loaded font. Fonts can be loaded with `LOAD"GRPF:filename"`.

More readable code:

```
INPUT STRING$
DIM CHARS$[0],PIXELS[0],SIZES[0]
WHILE STRING$>""
 CHAR$=POP(STRING$)
 PUSH CHARS$,CHAR$
 GCLS
 GPUTCHR 0,0,CHAR$
 GSAVE 0,0,8,8,PIXELS
 SIZE=0
 FOR I=0 TO 63
  INC SIZE,PIXELS[I]
 NEXT
 PUSH SIZES,SIZE
WEND
RSORT SIZES,CHARS$
WHILE LEN(CHARS$)
 PRINT POP(CHARS$);
WEND

```
> 1 votes

# Answer
# PHP - 485

Demo:

```
$ php pcg-23362.php "@+.0"
.+0@

```

Code:

```
<?php $f='x.ttf';$d=array();foreach(str_split($argv[1]) as$_){$B=imagettfbbox(50,0,$f,$_);$w=abs($B[4]-$B[0]);$h=abs($B[5]-$B[1]);$im=imagecreate($w,$h);imagecolorallocate($im,255,255,255);imagettftext($im,50,0,0,$h-$B[1],imagecolorallocate($im,0,0,0),$f,$_);$b=$w*$h;for($x=0;$x<$w;$x++)for($y=0;$y<$h;$y++){$z=imagecolorsforindex($im,imagecolorat($im,$x,$y));$color=$z['red']*$z['green']*$z['blue'];$b-=$color/0x1000000;}$d[$_]=$b / ($w * $h);}asort($d);echo implode(array_keys($d));

```
> 0 votes

# Answer
## Python + freetype-py: 147

```
import sys,freetype as F;f=F.Face('m.ttf');f.set_char_size(99);print(sorted([(f.load_char(c)or sum(f.glyph.bitmap.buffer),c)for c in raw_input()]))

```
> 0 votes

---
Tags: code-golf
---


title: Longest common substring in linear time

text:
# Question
Title: Longest common substring in linear time
This challenge is about writing code to solve the following problem.

Given two strings A and B, your code should output the start and end indices of a substring of A with the following properties.

* The substring of A should also match some substring of B.
* There should be no longer substring of A that satisfies the first property.

For example:

```
A = xxxappleyyyyyyy

B = zapplezzz

```

The substring `apple` with indices `4 8` (indexing from 1) would be a valid output.

**Functionality**

You can assume the input will be on standard in or in a file in the local directory, that is your choice. The file format will simply be two strings, separated by a new line. The answer should be a full program and not just a function.

I would eventually like to test your code on two substrings taken from the strings in http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ .

**Score**

This is code-golf with a twist. Your code must be run in `O(n)` time, where `n` is the total length of the input.

**Languages and libraries**

You can use any language which has a freely available compiler/interpreter/etc. for Linux. You should only use standard open source libraries not designed to solve this task. In case of dispute, I will count this as any library which either comes as standard with your language or one that you can install in a default ubuntu machine from a default repository.

**Useful information**

There are at least two ways to solve this problem in linear time. One is to first compute the suffix tree and the second is to first compute the suffix array and the LCP array.

# Answer
> 44 votes
## Python 2, 646 bytes

```
G=range;w=raw_input;z=L,m,h=[0]*3
s=w();t=len(s);s+='!%s#'%w();u=len(s);I=z*u
def f(s,n):
 def r(o):
	b=[[]for _ in s];c=[]
	for x in B[:N]:b[s[x+o]]+=x,
	map(c.extend,b);B[:N]=c
 M=N=n--~n/3;t=n%3%2;B=G(n+t);del B[::3];r(2);u=m=p=r(1)>r(0);N-=n/3
 for x in B*1:v=s[x:x+3];m+=u<v;u=v;B[x/3+x%3/2*N]=m
 A=1/M*z or f(B+z,M)+z;B=[x*3for x in A if x<N];J=I[r(0):n];C=G(n)
 for k in C:b=A[t]/N;a=i,j=A[t]%N*3-~b,B[p];q=p<N<(s[i:i-~b],J[i/3+b+N-b*N])>(s[j+t/M:j-~b],J[j/3+b*N]);C[k]=x=a[q];I[x]=k;p+=q;t+=1-q
 return C
S=f(map(ord,s)+z*40,u)
for i in G(u):
 h-=h>0;j=S[I[i]-1]
 while s[i+h]==s[j+h]:h+=1
 if(i<t)==(t<j)<=h>m:m=h;L=min(i,j)
print-~L,L+m

```

Try it online

This uses the skew algorithm described in "Simple Linear Work Suffix Array Construction" by Kärkkäinen and Sanders. The C++ implementation included in that paper already feels a little "golfy", but there is still plenty of room for making it shorter. For example, we can recurse until arriving at an array of length one, instead of short circuiting as in the paper, without violating the `O(n)` requirement.

For the LCP part, I followed "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications" by Kasai et al.

The program outputs `1 0` if the longest common substring is empty.

Here is some development code that includes an earlier version of the program that follows the C++ implementation a bit more closely, some slower approaches for comparison, and a simple test case generator:

```
from random import *

def brute(a,b):
    L=R=m=0

    for i in range(len(a)):
        for j in range(i+m+1,len(a)+1):
            if a[i:j] in b:
                m=j-i
                L,R=i,j

    return L+1,R

def suffix_array_slow(s):
    S=[]
    for i in range(len(s)):
        S+=[(s[i:],i)]
    S.sort()
    return [x[1] for x in S]

def slow1(a,b):
    # slow suffix array, slow lcp

    s=a+'!'+b
    S=suffix_array_slow(s)

    L=R=m=0

    for i in range(1,len(S)):
        x=S[i-1]
        y=S[i]
        p=s[x:]+'#'
        q=s[y:]+'$'
        h=0
        while p[h]==q[h]:
            h+=1
        if h>m and len(a)==sorted([x,y,len(a)])[1]:
            m=h
            L=min(x,y)
            R=L+h

    return L+1,R

def verify(a,b,L,R):
    if L<1 or R>len(a) or a[L-1:R] not in b:
        return 0
    LL,RR=brute(a,b)
    return R-L==RR-LL

def rand_string():
    if randint(0,1):
        n=randint(0,8)
    else:
        n=randint(0,24)
    a='zyxwvutsrq'[:randint(1,10)]
    s=''
    for _ in range(n):
        s+=choice(a)
    return s

def stress_test(f):
    numtrials=2000
    for trial in range(numtrials):
        a=rand_string()
        b=rand_string()
        L,R=f(a,b)
        if not verify(a,b,L,R):
            LL,RR=brute(a,b)
            print 'failed on',(a,b)
            print 'expected:',LL,RR
            print 'actual:',L,R
            return
    print 'ok'

def slow2(a,b):
    # slow suffix array, linear lcp

    s=a+'!'+b+'#'
    S=suffix_array_slow(s)

    I=S*1
    for i in range(len(S)):
        I[S[i]]=i

    L=R=m=h=0

    for i in range(len(S)):
        if I[i]:
            j=S[I[i]-1]
            while s[i+h]==s[j+h]:
                h+=1
            if h>m and len(a)==sorted([i,j,len(a)])[1]:
                m=h
                L=min(i,j)
                R=L+h
            h-=h>0

    return L+1,R

def suffix_array(s,K):
    # skew algorithm

    n=len(s)
    s+=[0]*3
    n0=(n+2)/3
    n1=(n+1)/3
    n2=n/3
    n02=n0+n2
    adj=n0-n1

    def radix_pass(a,o,n=n02):
        c=[0]*(K+3)
        for x in a[:n]:
            c[s[x+o]+1]+=1
        for i in range(K+3):
            c[i]+=c[i-1]
        for x in a[:n]:
            j=s[x+o]
            a[c[j]]=x
            c[j]+=1

    A=[x for x in range(n+adj) if x%3]+[0]*3

    radix_pass(A,2)
    radix_pass(A,1)
    radix_pass(A,0)

    B=[0]*n02
    t=m=0

    for x in A[:n02]:
        u=s[x:x+3]
        m+=t<u
        t=u
        B[x/3+x%3/2*n0]=m

    A[:n02]=1/n02*[0]or suffix_array(B,m)
    I=A*1
    for i in range(n02):
        I[A[i]]=i+1

    B=[3*x for x in A if x<n0]
    radix_pass(B,0,n0)

    R=[]

    p=0
    t=adj
    while t<n02:
        x=A[t]
        b=x>=n0
        i=(x-b*n0)*3-~b
        j=B[p]
        if p==n0 or ((s[i:i+2],I[A[t]-n0+1])<(s[j:j+2],I[j/3+n0]) if b else (s[i],I[A[t]+n0])<(s[j],I[j/3])):R+=i,;t+=1
        else:R+=j,;p+=1

    return R+B[p:n0]

def solve(a,b):
    # linear

    s=a+'!'+b+'#'
    S=suffix_array(map(ord,s),128)

    I=S*1
    for i in range(len(S)):
        I[S[i]]=i

    L=R=m=h=0

    for i in range(len(S)):
        if I[i]:
            j=S[I[i]-1]
            while s[i+h]==s[j+h]:
                h+=1
            if h>m and len(a)==sorted([i,j,len(a)])[1]:
                m=h
                L=min(i,j)
                R=L+h
            h-=h>0

    return L+1,R

stress_test(solve)

```

---
Tags: code-golf, string, subsequence, restricted-complexity
---


title: Split a grid into a grid

text:
# Question
Title: Split a grid into a grid
## Introduction

There is a small village with nothing but a few houses and empty fields. The local bureaucrats want to divide the village into lots so that each lot contains exactly one house, and the borders of the lots form a nice straight-line grid. Your task is to determine whether this is possible.

## The task

Your input is a rectangular 2D array of bits; 1 represents a house and 0 an empty field. Its size will be at least **1×1**, and it will contain at least one 1. You can take the input in any reasonable format (nested list of integers, list of strings, multiline string etc).

Your program shall determine whether the array can be divided into grid cells using straight horizontal and vertical lines so that each grid cell contains exactly one 1. The grid cells may have different sizes and shapes, although they will always be rectangular. The lines must run from one edge of the array to the opposite edge.

For example, the following is a valid division of an array:

```
00|0010|01|1
01|0000|00|0
--+----+--+-
00|0000|00|1
01|0010|01|0
--+----+--+-
01|1000|10|1

```

whereas the following division is not valid, since there are grid cells with no 1s or more than one 1:

```
00|0010|01|1
--+----+--+-
01|0000|00|0
00|0000|00|1
01|0010|01|0
--+----+--+-
00|1000|10|1

```

If a valid division exists, you shall output a truthy value, and otherwise a falsy value.

## Rules and scoring

You can write a full program or a function. The lowest byte count wins.

## Test cases

```
[[1]] -> True
[[0,1],[1,0]] -> True
[[1,1],[1,0]] -> False
[[1,0,1],[0,1,0]] -> True
[[1,0],[0,1],[0,1]] -> True
[[1,0,0],[0,0,1],[0,1,1]] -> True
[[1,1,1],[1,1,1],[1,1,1]] -> True
[[1,0,1],[0,1,0],[1,0,0]] -> True
[[1,0,0],[1,0,0],[0,1,1]] -> False
[[0,0,0,0,1],[1,0,0,1,0],[0,0,0,1,0]] -> False
[[0,0,1,0,1],[0,0,0,1,0],[0,0,0,0,0]] -> True
[[1,1,0,0,0],[0,0,0,0,0],[1,0,1,0,0]] -> True
[[1,1,0,1,1],[0,1,0,1,1],[1,0,0,0,0]] -> True
[[0,0,0,0,0,0,0],[0,1,1,1,0,1,0],[0,1,0,0,1,0,0],[0,0,0,0,0,0,1],[0,0,1,0,0,0,1],[1,1,0,1,1,0,0]] -> False
[[1,1,0,0,0,0,0],[1,0,1,1,0,1,0],[0,0,0,0,1,0,0],[0,1,0,1,1,0,0],[1,0,0,0,1,1,0],[0,0,0,0,0,1,0]] -> False
[[0,1,0,1,1,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,0],[1,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,1]] -> True
[[0,1,0,0,1,0,1],[1,0,0,0,1,0,1],[0,0,1,0,1,0,1],[1,0,0,0,1,1,0],[0,0,0,1,1,1,0],[0,1,0,0,1,0,1]] -> True
[[0,1,0,0,1,0,0,1,0],[0,0,0,0,1,1,0,1,0],[1,1,0,0,1,0,0,0,0],[0,0,1,0,1,0,1,0,0],[0,0,1,0,1,0,1,0,0],[0,1,0,0,0,1,0,0,1],[0,1,0,0,0,0,1,0,0]] -> False
[[1,0,1,0,0,1,1,0,1],[0,1,1,0,0,1,1,0,1],[1,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,1,1],[0,1,1,0,1,0,1,0,1],[1,0,1,0,0,1,1,0,1]] -> True

```

# Answer
# Pyth, ~~30~~ ~~29~~ ~~26~~ ~~24~~ 23 bytes

```
sm.Asmmq1ssbCkds./MC./M

```

Try it online.

I'm sure this will get shorter. This is **O(2*mn*)**, where *m* and *n* are the width and height of the array, but completes the last two test cases in 45 seconds on my laptop on battery (i5-5200U with limited performance).

Outputs the number of solutions.

### Explanation

Five-dimensional arrays are really fun to work with.\</sarcasm\> You are not supposed to understand how this works even with the explanation.

```
                    ./M    Find all partitions of each row. Now we have a list of rows,
                           each containing the ways to split the row, each containing
                           the parts of the split (3D).
                   C       Transpose. Now we have a list of ways to split the columns,
                           each containing the rows, each containing the parts of the
                           row (3D).
                ./M        Find all partitions of each row list. Now we have a list of
                           ways to split the columns, each containing the ways to split
                           the rows, each containing the bunch of rows, each containing
                           the rows in the bunch, each containing the parts of the row
                           (6D).
               s           Combine the ways to split rows & columns into one array (5D).
 m            d            Do the following for each way to split rows & columns (4D):
     m       k                 Do the following for each bunch of rows (3D):
            C                      Transpose the array. We now have a list of column
                                   groups, each containing the row parts (3D).
      m    b                       Do the following for each column group (2D):
          s                            Combine the row parts in the column group. We now
                                       have the list of cells in this row/column group
                                       (1D).
         s                             Sum the cells.
       q1                              Check if the sum is one.
                                   We now have the list of booleans that tell if each
                                   row/column group is valid (1D).
                               We now have the 2D list of booleans that tell if each
                               row/column group in each bunch of rows is valid. (2D)
    s                          Combine the 2D list of booleans to 1D.
  .A                           Check if all values are truthy; if the split is valid.
                           We now have the validity of each split.
s                          Sum the list to get the number of valid solutions.

```
> 7 votes

# Answer
# Jelly, 22 bytes

```
ŒṖḅ1S€€=1Ȧ€
SŒṖ⁸ṁþÇ€FS

```

Try it online!
> 3 votes

# Answer
# Haskell, 116 bytes

```
import Data.List
m(a:b)=[a:e|e<-m b]++[zipWith(+)a d:e|d:e<-m b];m e=[e]
d=(any$any$all$all(==1)).map(m.transpose).m

```

Try it online!
> 2 votes

# Answer
# Jelly, 20 bytes

```
ŒṖS€€ỊȦ$ÐfZ€µ⁺€Ȧ€€FS

```

This is still a brute-force solution, but it's quite a bit faster than my other answer – which cannot cope with the last two test cases on TIO – and handles all test cases in ~4 seconds.

Try it online!

### How it works

```
ŒṖS€€ỊȦ$ÐfZ€µ⁺€Ȧ€€FS  Main link. Argument: M (matrix, array of rows)

ŒṖ                    Compute all partitions, i.e., all groupings of M's rows.
  S€€                 Map sum over all individual groupings, collapsing the grouped
                      rows into a single row.
        Ðf            Filter; keep only those partially collapsed matrices for
                      which the link to the left returns a truthy value.
       $                Group the two links to the left into a monadic chain.
     Ị                    Insignificant; map 0 and 1 to 1, greater integers to 0.
      Ȧ                   All; return 1 iff the matrix contains no zeroes.
          Z€          Zip/transpose all kept matrices,
            µ         Combine all links to the left into a monadic chain.
             ⁺€       Duplicate the chain and map it over the individual results
                      from the first call. We now have all possible combinations
                      of row and column groupings (represented by the corresponding
                      matrices of collapsed rows and columns) that do not have a
                      2 anywhere. However, they still may contain zeroes.
               Ȧ€€    Map the all atom over the matrices, returning 1 only for
                      matrices that consist entirely of ones.
                  FS  Flatten and sum, counting the number of valid divisions.

```
> 1 votes

---
Tags: code-golf, grid, decision-problem, set-partitions
---